Luận văn thạc sĩ: Gom cụm dữ liệu chuỗi thời gian dựa vào điểm cực đại mật độ

Luận văn thạc sĩ nghiên cứu máy tính gom cụm dữ liệu chuỗi thời gian dựa vào các điểm cực đại mật độ, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong

• Tác giả: Phan Thị Thanh Phương
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc Gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Gom Cụm Dữ Liệu Chuỗi Thời Gian Dựa Vào Các Điểm Cực Đại Mật Độ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Tổng quan về đề tài

Đề tài 'Gom cụm dữ liệu chuỗi thời gian bằng điểm cực đại mật độ' tập trung vào việc nghiên cứu và phát triển các phương pháp gom cụm dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian là một dãy các điểm dữ liệu được thu thập theo thứ tự thời gian, có ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, tài chính, y khoa, và sinh học. Việc gom cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu, nhằm phát hiện các mẫu và cấu trúc trong tập dữ liệu lớn. Đề tài này sẽ áp dụng giải thuật Density Peak để thực hiện việc gom cụm, với mục tiêu tạo ra các cụm dữ liệu ổn định và chất lượng cao.

1.1 Đối tượng nghiên cứu

Đối tượng nghiên cứu chính của đề tài là dữ liệu chuỗi thời gian. Dữ liệu này thường được sử dụng trong các lĩnh vực như tài chính, y tế, và sinh học. Việc phân tích và gom cụm dữ liệu chuỗi thời gian gặp nhiều thách thức do tính chất phức tạp và đa chiều của nó. Đề tài sẽ tìm hiểu các phương pháp gom cụm hiện có và đề xuất mô hình mới dựa trên các điểm cực đại mật độ, nhằm cải thiện hiệu quả và độ chính xác trong việc phân nhóm dữ liệu.

II. Phương pháp nghiên cứu

Phương pháp nghiên cứu được áp dụng trong đề tài bao gồm việc tìm hiểu và áp dụng giải thuật Density Peak cho việc gom cụm dữ liệu chuỗi thời gian. Đề tài sẽ sử dụng đo lường Euclid để tính toán khoảng cách giữa các điểm dữ liệu, từ đó xác định các cụm. Một trong những điểm nổi bật của phương pháp này là khả năng xử lý các dữ liệu có hình dạng phức tạp mà các phương pháp truyền thống như K-means không thể thực hiện. Việc cắt tỉa tính toán lân cận gần nhất từ danh sách mật độ cao hơn cũng sẽ được thực hiện để tăng tốc độ xử lý.

2.1 Giải thuật Density Peak

Giải thuật Density Peak được đề xuất bởi Rodriguez và Laio vào năm 2014, cho phép gom cụm dữ liệu mà không cần phải xác định số lượng cụm trước. Phương pháp này dựa trên việc xác định các điểm cực đại mật độ trong không gian dữ liệu, từ đó phân nhóm các điểm dữ liệu xung quanh chúng. Điều này giúp tạo ra các cụm có hình dạng tùy ý, phù hợp với đặc điểm của dữ liệu chuỗi thời gian.

III. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng mô hình gom cụm dựa trên các điểm cực đại mật độ cho kết quả ổn định và chất lượng cao. Các tiêu chí đánh giá chất lượng gom cụm cho thấy các chỉ số đánh giá tốt hơn so với các phương pháp gom cụm truyền thống. Việc áp dụng giải thuật này trên nhiều tập dữ liệu mẫu đã chứng minh tính khả thi và hiệu quả của nó trong việc xử lý dữ liệu chuỗi thời gian. Các cụm dữ liệu được tạo ra không chỉ chính xác mà còn có thể được trực quan hóa một cách dễ dàng.

3.1 So sánh với các phương pháp khác

Khi so sánh với các phương pháp gom cụm khác như K-means, giải thuật dựa trên điểm cực đại mật độ cho thấy ưu thế vượt trội trong việc xử lý các dữ liệu có hình dạng phức tạp. Kết quả thực nghiệm cho thấy rằng mô hình này không chỉ cải thiện độ chính xác mà còn giảm thiểu thời gian tính toán. Điều này mở ra hướng đi mới cho việc áp dụng các phương pháp gom cụm trong khai thác dữ liệu và học máy.

IV. Ý nghĩa và ứng dụng thực tiễn

Đề tài không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn cao trong nhiều lĩnh vực. Việc gom cụm dữ liệu chuỗi thời gian có thể hỗ trợ trong việc phát hiện các xu hướng, mẫu hình trong dữ liệu, từ đó giúp các nhà nghiên cứu và doanh nghiệp đưa ra quyết định chính xác hơn. Các ứng dụng có thể bao gồm phân tích tài chính, dự đoán xu hướng tiêu dùng, và phát hiện bất thường trong dữ liệu y tế.

4.1 Ứng dụng trong các lĩnh vực

Các kết quả đạt được từ nghiên cứu có thể được áp dụng trong nhiều lĩnh vực khác nhau như tài chính, y tế, và sinh học. Ví dụ, trong lĩnh vực tài chính, việc phân tích dữ liệu chuỗi thời gian có thể giúp dự đoán giá cổ phiếu, trong khi trong y tế, nó có thể hỗ trợ trong việc phát hiện các bất thường trong dữ liệu sức khỏe. Điều này cho thấy tầm quan trọng của việc phát triển các phương pháp gom cụm hiệu quả cho dữ liệu chuỗi thời gian.

Trích đoạn nội dung tài liệu

mở đầu cho bƣớc đột phá mới trong lĩnh vực khai phá dữ liệu. Đề tài vận dụng các kiến thức cơ bản và những vấn đề cần lƣu ý trong giải thuật này, đặc biệt việc áp dụng giải thuật trực tiếp trên dữ liệu chuỗi thời gian mang lại tính thực tế cao cho đề tài. Những kết quả đạt đƣợc của luận văn Sau một thời gian nghiên cứu và hiện thực, chúng tôi đã đạt đƣợc các kết quả tích cực, đó là: - Xây dựng đƣợc hệ thống gom cụm dữ liệu chuỗi thời gian dựa vào các điểm cực đại mật độ với độ đo Euclid. - Tính khoảng cách giới hạn dc dùng làm tham số đầu vào của giải thuật gom cụm các điểm mật độ cực đại.

- Tăng tốc độ thực thi thông qua việc cắt tỉa tính toán khoảng cách lân cận gần nhất từ danh sách mật độ cao hơn. - Kết quả của toàn bộ quá trình này, các cụm dữ liệu đƣợc tạo ra một cách ổn định, các tiêu chí đánh giá chất lƣợng gom cụm cho thấy các chỉ số đánh giá khá tốt so với với các phƣơng pháp gom cụm truyền thống. Cấu trúc luận văn Tổ chức của phần còn lại của luận văn gồm những phần sau: Chƣơng 2 là các cơ sở lý thuyết mà chúng tôi đã sử dụng trong nghiên cứu này. Phần này sẽ trình bày lý thuyết về độ đo khoảng cách, các tiêu chí đánh giá kết quả gom cụm.

Chƣơng 3 là tổng quan về các công trình có liên quan. Phần này trình bày về các nghiên cứu về gom cụm chuỗi thời gian. 5 Chƣơng 4 trình bày về hệ thống gom cụm dữ liệu chuỗi thời gian của chúng tôi. Chƣơng 5 trình bày các kết quả thực nghiệm trên các tập dữ liệu chuỗi thời gian, qua đó đánh giá kết quả đạt đƣợc so với giải thuật k-Means truyền thống.

Chƣơng 6 gồm một số kết luận, đóng góp của đề tài và hƣớng phát triển. CƠ SỞ LÝ THUYẾT Nội dung của phần cơ sở lý thuyết trình bày các kiến thức cơ sở của đề tài bao gồm tổng quát về dữ liệu chuỗi thời gian, bài toán gom cụm trong dữ liệu chuỗi thời gian, các tiêu chí đánh giá gom cụm và các độ đo khoảng cách trong dữ liệu chuỗi thời gian. Các độ đo khoảng cách chuỗi thời gian Để giải quyết các bài toán tìm kiếm mẫu, phân loại hay gom cụm dữ liệu chuỗi thời gian mà kiểu dữ liệu đƣợc biểu diễn thành một chuỗi các số thực, chúng ta phải sử dụng các độ đo khoảng cách giữa các cặp chuỗi thời gian với nhau. Giả sử hai chuỗi thời gian và với các độ dài n và m tƣơng ứng là và.

Chúng ta cần xác định độ đo khoảng cách ( ) của hai chuỗi thời gian này. Các độ đo trong không gian Euclid Độ đo trong không gian Euclid đƣợc sử dụng phổ biến trong gom cụm dữ liệu vì tính dễ hiểu, hiện thực đơn giản, tốc độ hội tụ nhanh và khả năng đáp ứng với dữ liệu thƣa thớt. Hiện nay, có rất nhiều độ đo khoảng cách đã đƣợc sử dụng cho gom cụm dữ liệu chuỗi thời gian tùy thuộc vào từng miền ứng dụng, trong đó độ đo trong không gian Euclid là đủ khả năng để giải quyết bài toán này. Sau đây, chúng tôi sẽ giới thiệu một vài độ đo trong không gian Euclid.

Độ đo Euclid: ( ) √∑ (| |) Độ đo Manhattan: ( ) ∑ (| |) Độ đo Minkowski: ( ) √∑ (| |) Độ đo Chebyshev: ( ) √∑ (| |) | | Tùy thuộc vào từng miền ứng dụng mà chúng ta sử dụng độ đo phù hợp nhƣng thông thƣờng độ đo Euclid là đủ tốt và có độ chính xác chấp nhận đƣợc để áp dụng. Ngoài ra, các độ đo trên phải thỏa mãn một số tính chất sau [10]: 7 - ( ) : khoảng cách phải là số không âm. - ( ) : khoảng cách từ một đối tƣợng tới chính nó là 0. - ( ) ( ): khoảng cách là hàm đối xứng.

- ( ) ( ) ( ): khoảng cách trực tiếp từ tới không lớn hơn khoảng cách đi qua các điểm trung gian khác. Ƣu điểm: thời gian tính toán nhanh, có thể áp dụng cho các bài toán khai phá dữ liệu khác và các độ đo thỏa mãn bất đẳng thức tam giác nên có thể dễ dàng lập chỉ mục, giảm thời gian tìm kiếm. Khuyết điểm: chỉ áp dụng khi những chuỗi có chiều dài bằng nhau [11], dễ bị ảnh hƣởng bởi nhiễu [12]. Độ đo xoắn thời gian động Trong trƣờng hợp dữ liệu chuỗi thời gian có hình dạng giống nhau nhƣng khác nhau về thời gian, độ đo xoắn thời gian động sẽ cho kết quả chính xác hơn độ đo Euclid vì cách ánh xạ điểm thứ của chuỗi này với điểm thứ của chuỗi khác sẽ cho kết quả khác nhau (hình 2.

Để sắp xếp đƣơc hai chuỗi này, chúng ta phải xây dựng ma trận nơi phần tử ( ) của ma trận là khoảng cách ( ) của hai điểm và mỗi điểm ( ) này là sự sắp xếp giữa hai điểm. Đường xoắn (warping path) đƣợc định nghĩa là sự sắp xếp của những phần tử trong hai chuỗi và , tức là ánh xạ giữa và. Từ đó, chúng ta có với ( ) và ( ) (hình 2. Do đó, chúng ta sẽ tìm đƣợc nhiều đƣờng xoắn khác nhau nhƣng chúng ta chỉ quan tâm tới đƣờng xoắn mà làm tối thiểu hóa chi phí xoắn nhất: 8 ( ) {√∑ Chúng ta có thể tính toán đƣợc DTW bằng giải thuật quy hoạch động (dynamic programming) gồm biến giai đoạn, biến trạng thái và biến quyết định để mô tả quá trình chuyển đổi trạng thái hợp lệ.

Trong đó, biến giai đoạn đơn giản chỉ là một sự tăng đơn điệu các sự kiện, biến trạng thái là các điểm ( ) trong ma trận và biến quyết định để giới hạn những đƣờng xoắn hợp lệ làm giảm không gian tìm kiếm. Việc giới hạn không gian tìm kiếm sẽ giúp tiết kiệm đƣợc chi phí tính toán và cải thiện đƣợc vấn đề hiệu suất, cho nên đƣờng xoắn thời gian phải tuân theo một vài ràng buộc sau: - Tính đơn điệu (monotonicity): những điểm phải đƣợc sắp thứ tự đơn điệu tƣơng ứng với thời gian, tức là cho ( ) thì ( ) với – và –. - Tính liên tục (continuity): từng bƣớc trong đƣờng xoắn phải liền kề nhau, tức là cho ( ) thì ( ) với – và –. - Cửa sổ xoắn (warping window): những điểm hợp lệ phải rơi vào khoảng cửa sổ xoắn cho trƣớc với | |.

- Ràng buộc độ dốc (slope constraint): những đƣờng xoắn hợp lệ phải bị ràng buộc về độ dốc, điều này giúp tránh trƣờng hợp những bƣớc di chuyển quá lớn theo một hƣớng. - Điều kiện biên (boundary conditions): ( ) và ( ) điều này giúp đƣờng xoắn bắt đầu và kết thúc tại các điểm nằm ở góc trên đƣờng chéo của ma trận. Tiếp theo, chúng ta sẽ tính toán khoảng cách DTW bằng quy hoạch động dựa vào mối quan hệ đệ quy sau, mà định nghĩa khoảng cách tích lũy ( ) của mỗi điểm: ( ) ( ) * ( ) ( ) ( )+ 9 Hình 2. Ma trận xoắn và đƣờng xoắn tối ƣu [16] Khoảng cách đó là tổng khoảng cách giữa các phần tử hiện tại với khoảng cách tích lũy nhỏ nhất của các điểm xung quanh.

Độ đo Euclid có thể xem nhƣ trƣờng hợp đặc biệt của DTW với ràng buộc ( ) và hai chuỗi có độ dài bằng nhau. Chi tiết giải thuật tính khoảng cách DTW nhƣ sau: Input , - , - , - Output: , - 1. return , - Ví dụ sau đây sẽ minh họa cho giải thuật tính khoảng cách DTW. Giả sử chúng ta có 2 chuỗi thời gian (đƣợc biểu diễn đồ thị bằng hình 2.

Đồ thị biểu diễn hai chuỗi thời gian Để tính khoảng cách DTW, chúng ta xây dựng ma trận tính khoảng cách tích lũy của hai chuỗi trên nhƣ hình 2. Mỗi ô trong ma trận sẽ chứa khoảng cách tích lũy tƣơng ứng của cặp điểm đó. Trong ma trận xoắn hình 2.4 thì các ô đƣợc tính toán nhƣ sau: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) * ( ) ( ) ( )+ ( ) Sau khi đã tính tất cả giá trị tích lũy cho các ô, chúng ta đƣợc một đƣờng xoắn tối ƣu bao gồm các ô tham gia tích lũy cho ô ( ). Trong hình trên thì đƣờng xoắn tối ƣu là các ô đƣợc tô màu.

Vậy khoảng cách DTW của hai chuỗi trên là √ , trong khi khoảng cách Euclid của hai chuỗi trên là √ Ƣu điểm: Phƣơng pháp DTW có ƣu điểm là cho kết quả chính xác hơn so với độ đo Euclid và cho phép nhận dạng mẫu có hình dạng giống nhau nhƣng chiều dài hình dạng về thời gian có thể khác nhau. Khuyết điểm: thời gian chạy lâu và độ phức tạp của DTW là ( ), tuy nhiên gần đây đã có những công trình tăng tốc độ tìm kiếm tƣơng tự dùng độ đo DTW. Ma trận xoắn DTW cho hai chuỗi thời gian 2. Bài toán gom cụm trong dữ liệu chuỗi thời gian Gom cụm dữ liệu chuỗi thời gian là một tiến trình rất quan trọng trong quá trình cô đọng và tổng quát hóa dữ liệu.

Gom cụm tƣơng tự nhƣ phân lớp ở chỗ phân loại dữ liệu vào các nhóm. Tuy nhiên, các nhóm này không đƣợc định nghĩa trƣớc, mà đƣợc định nghĩa bằng bản thân dữ liệu, dựa trên sự tƣơng tự giữa các chuỗi thời gian. Gom cụm thƣờng đƣợc xem nhƣ việc học không giám sát, dựa trên việc quyết định sự tƣơng tự giữa các dữ liệu ở một số thuộc tính định nghĩa trƣớc. Những dữ liệu tƣơng tự nhau nhất đƣợc nhóm vào các cụm, nhƣng các cụm đó phải rất khác biệt nhau.

Nhu cầu sử dụng kỹ thuật thu giảm số chiều xuất phát từ việc dữ liệu chuỗi thời gian thƣờng cực kỳ lớn và do đó tìm kiếm trực tiếp trên những dữ liệu này sẽ rất phức tạp và không hữu hiệu. Việc thu giảm số chiều của dữ liệu dẫn tới biểu diễn dữ liệu chuỗi thời gian thành các dạng khác. Sau đó, ta sẽ xây dựng các giải thuật tính toán, phân tích trên các dạng biểu diễn này. Minh họa gom cụm dữ liệu chuỗi thời gian Mục tiêu của gom cụm dữ liệu là để xác định các nhóm nội tại bên trong một bộ dữ liệu không có nhãn.

Tuy nhiên, không thể xác định tiêu chí nào đƣợc xem là tốt nhất để đánh giá hiệu quả của việc gom cụm. Có thể thấy, ngƣời thực hiện cần xác định tiêu chí theo mục đích của việc gom cụm để cho kết quả cuối cùng phù hợp với nhu cầu của họ.