Luận văn thạc sĩ khoa học máy tính kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k means để gom cụm dữ liệu chuỗi thời gian

Luận văn thạc sĩ về thuật toán gom cụm dữ liệu chuỗi thời gian, kết hợp độ dốc tích lũy có trọng số và K-Means. Nghiên cứu khoa học máy tính chuyên sâu.

• Tác giả: Đặng Thanh Hùng
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Trường Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Kết Hợp Giải Thuật Gom Cụm Dựa Vào Độ Dốc Tích Lũy Có Trọng Số Và K-Means Để Gom Cụm Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Gom Cụm Chuỗi Thời Gian và Bài Toán 55 ký tự

Dữ liệu chuỗi thời gian là chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo tại những thời điểm cách đều nhau. Khai thác dữ liệu thời gian bằng cách gom cụm dữ liệu là một lĩnh vực nghiên cứu trong nhiều thập kỷ qua với ứng dụng to lớn trong nhiều lĩnh vực như y học, tài chính ngân hàng, hệ thống bán hàng, dự báo thời tiết, chứng khoán, khoa học, kỹ thuật. Gom cụm dữ liệu được sử dụng như một công cụ phân tích dữ liệu hoặc được sử dụng trong bước tiền xử lý cho các giải thuật khai phá dữ liệu khác. Năm 2006, Yang và Wu thực hiện cuộc thăm dò ý kiến từ các nhà nghiên cứu hàng đầu về khai phá dữ liệu và máy học và kết quả là hướng nghiên cứu về khai phá dữ liệu chuỗi thời gian được xếp thứ 3 trong 10 hướng nghiên cứu quan trọng và thách thức nhất. Do đó gom cụm dữ liệu thời gian là một công trình khai thác dữ liệu quan trọng thỏa mãn tính hữu hiệu (độ phức tạp tính toán thấp) và đảm bảo kết quả đúng.

1.1. Gom Cụm Dữ Liệu Chuỗi Thời Gian Ứng Dụng Thực Tiễn

Gom cụm dữ liệu chuỗi thời gian được ứng dụng rộng rãi trong nhiều lĩnh vực. Trong y học, nó có thể được sử dụng để phân tích dữ liệu điện tâm đồ, điện não đồ để phát hiện các bất thường. Trong tài chính ngân hàng, nó có thể được sử dụng để phân tích biến động giá cổ phiếu, dự báo xu hướng thị trường. Trong dự báo thời tiết, nó giúp phân nhóm các khu vực có kiểu thời tiết tương tự. Trong chứng khoán, giúp phân tích biến động giá. Các ứng dụng này cho thấy tiềm năng lớn của việc khai thác thông tin từ dữ liệu chuỗi thời gian thông qua kỹ thuật gom cụm.

1.2. Thách Thức Trong Gom Cụm Dữ Liệu Chuỗi Thời Gian

Việc gom cụm dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Dữ liệu thường có số chiều rất lớn, đòi hỏi các thuật toán phải có độ phức tạp tính toán thấp và đảm bảo kết quả chính xác. Theo PGS. Dương Tuấn Anh, việc tìm kiếm các đặc trưng phù hợp và lựa chọn độ đo tương tự hiệu quả cũng là một vấn đề quan trọng. Ngoài ra, dữ liệu có thể chứa nhiễu, giá trị bị thiếu hoặc các mẫu không đồng đều, đòi hỏi các phương pháp tiền xử lý phù hợp. Các thách thức này đòi hỏi sự kết hợp giữa lý thuyết và thực tiễn để phát triển các giải pháp hiệu quả.

II. Vấn Đề Với K Means và Giải Pháp Độ Dốc Tích Lũy 59 ký tự

Gom cụm dữ liệu là quá trình phân loại các mẫu thành một tập các nhóm dựa trên một hàm đo khoảng cách nào đó, sao cho các phần tử trong cùng một nhóm sẽ rất giống nhau, các phần tử trong các nhóm khác sẽ rất khác nhau. Giải thuật gom cụm phổ biến nhất hiện nay đối với dữ liệu chuỗi thời gian là giải thuật K-Means, do giải thuật K-Means dễ hiện thực và có thời gian thực thi khá nhanh. Ý tưởng của giải thuật này cho trước một số nguyên dương k, với k là số cụm cần gom. Đầu tiên, chọn ngẫu nhiên k đối tượng trong không gian dữ liệu làm các trung tâm cụm ban đầu, sau đó duyệt qua các đối tượng dữ liệu còn lại và dựa trên một hàm tính khoảng cách để gán các đối tượng này vào cụm có trung tâm cụm gần nó nhất.

2.1. Hạn Chế Của K Means Khởi Tạo Tâm Cụm Ngẫu Nhiên

Mặc dù K-Means phổ biến, nhưng việc khởi tạo trung tâm cụm ban đầu ngẫu nhiên là một nhược điểm lớn. Theo tóm tắt luận văn, điều này có thể dẫn đến kết quả gom cụm không ổn định và chất lượng kém. Các cụm có thể bị chồng chéo hoặc không phản ánh đúng cấu trúc dữ liệu. Việc lặp lại thuật toán nhiều lần với các khởi tạo khác nhau có thể cải thiện kết quả, nhưng làm tăng đáng kể thời gian tính toán. Do đó, cần có các phương pháp khởi tạo thông minh hơn để khắc phục hạn chế này.

2.2. Giải Pháp Độ Dốc Tích Lũy Có Trọng Số CWS

Luận văn này đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số (CWS) để cải thiện chất lượng lời giải và thời gian thực thi cho thuật toán K-Means. Theo Đặng Thanh Hùng, CWS giúp thu giảm số chiều của dữ liệu thời gian, từ đó xác định các điểm dữ liệu quan trọng làm trung tâm cụm ban đầu. CWS giúp khai thác thông tin về xu hướng và biến động của chuỗi thời gian, từ đó chọn được các trung tâm cụm đại diện cho các mẫu dữ liệu khác nhau.

III. Hướng Dẫn Kết Hợp CWS và K Means Gom Cụm 53 ký tự

Ý tưởng chính của đề tài này là thực hiện gom cụm dữ liệu chuỗi thời gian với hai bước (1) dựa vào độ dốc tích lũy có trọng số (Cumulative Weighted Slopes) để thu giảm số chiều của dữ liệu thời gian từ một dữ liệu N chiều thu giảm thành một chiều duy nhất, với áp dụng giải thuật K-Means để gom cụm dữ liệu trên thành các trung tâm cụm ban đầu và (2) áp dụng giải thuật K-Means để gom cụm dữ liệu thời gian với các trung tâm cụm ban đầu được xác định bởi bước 1.

3.1. Bước 1 Tính Toán Độ Dốc Tích Lũy Có Trọng Số CWS

Bước đầu tiên là tính toán độ dốc tích lũy có trọng số cho mỗi chuỗi thời gian. CWS thể hiện xu hướng và biến động của chuỗi. Theo luận văn, CWS được sử dụng để giảm số chiều dữ liệu, giúp đơn giản hóa quá trình gom cụm. Các chuỗi thời gian có CWS tương tự sẽ có xu hướng thuộc cùng một cụm. Thuật toán CWS cần được lựa chọn và tối ưu hóa để phù hợp với đặc điểm của dữ liệu.

3.2. Bước 2 Sử Dụng K Means Với Tâm Cụm Khởi Tạo Từ CWS

Sau khi có được CWS cho mỗi chuỗi, thuật toán K-Means được sử dụng để gom cụm dữ liệu. Điểm khác biệt là các trung tâm cụm ban đầu không được chọn ngẫu nhiên, mà được xác định dựa trên giá trị CWS. Các chuỗi thời gian có giá trị CWS gần nhau sẽ được gán vào cùng một cụm. Việc này giúp cải thiện đáng kể chất lượng gom cụm so với khởi tạo ngẫu nhiên.

3.3. Xử Lý Dữ Liệu Chuỗi Thời Gian Trước Khi Gom Cụm

Bước đầu tiên là cần chuẩn hóa dữ liệu, đảm bảo các chuỗi thời gian có cùng tỷ lệ và phạm vi. Tiếp theo, có thể áp dụng các phương pháp làm mịn dữ liệu để loại bỏ nhiễu và làm nổi bật các xu hướng quan trọng. Các phương pháp phổ biến bao gồm trung bình trượt, bộ lọc Kalman và phân tích wavelet. Sau khi làm sạch dữ liệu, có thể áp dụng các kỹ thuật giảm chiều để giảm độ phức tạp tính toán. Các phương pháp phổ biến bao gồm phân tích thành phần chính (PCA) và phân tích thành phần độc lập (ICA).

IV. Ứng Dụng Thực Tế và Kết Quả Nghiên Cứu 56 ký tự

Luận văn cũng nghiên cứu ứng dụng phương pháp thu giảm số chiều xấp xỉ tuyến tính từng đoạn (PLA) để thu giảm số chiều của dữ liệu thời gian và nghiên cứu ứng dụng cấu trúc kd-tree vào vấn đề khởi tạo trung tâm cụm ban đầu. Cuối cùng, so sánh kết quả của các phương pháp dựa trên các tiêu chí đánh giá và hàm mục tiêu để đánh giá chất lượng gom cụm. Kết quả thực nghiệm cho thấy giải thuật K-Means có khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số là giải thuật hiệu quả nhất và lời giải ổn định qua các lần thực thi, thời gian thực thi không chịu ảnh hưởng nhiều bởi độ lớn của cơ sở dữ liệu.

4.1. So Sánh Với Các Phương Pháp Khởi Tạo Tâm Cụm Khác

Luận văn so sánh phương pháp khởi tạo tâm cụm dựa trên CWS với các phương pháp khác, bao gồm khởi tạo ngẫu nhiên và sử dụng kd-tree. Kết quả cho thấy CWS vượt trội hơn về cả chất lượng gom cụm và thời gian thực thi. Khởi tạo ngẫu nhiên thường dẫn đến kết quả không ổn định, trong khi kd-tree có thể hiệu quả trong một số trường hợp nhất định, nhưng không tổng quát bằng CWS. So sánh này khẳng định tính ưu việt của phương pháp đề xuất.

4.2. Áp Dụng Vào Dữ Liệu Chứng Khoán và Dữ Liệu Phức Hợp

Phương pháp được thử nghiệm trên nhiều bộ dữ liệu khác nhau, bao gồm dữ liệu chứng khoán Việt Nam, dữ liệu chứng khoán Mỹ và dữ liệu phức hợp. Theo Đặng Thanh Hùng, kết quả cho thấy phương pháp hoạt động hiệu quả trên cả dữ liệu có cấu trúc phức tạp và dữ liệu có số chiều lớn. Điều này cho thấy tính ứng dụng rộng rãi của phương pháp trong các bài toán thực tế.

4.3. Đánh Giá Chất Lượng Gom Cụm Dựa Trên Hàm Mục Tiêu

Chất lượng gom cụm có thể được đánh giá bằng cách sử dụng các hàm mục tiêu. Các hàm này đo lường mức độ tương đồng của các đối tượng trong cùng một cụm và mức độ khác biệt giữa các cụm khác nhau. Các hàm mục tiêu phổ biến bao gồm tổng bình phương lỗi (SSE), chỉ số Silhouette và chỉ số Davies-Bouldin. Bằng cách tối ưu hóa hàm mục tiêu, có thể cải thiện chất lượng gom cụm và đảm bảo các cụm được hình thành có ý nghĩa và dễ diễn giải.

V. Kết Luận và Hướng Phát Triển Gom Cụm 50 ký tự

Chúng tôi đã áp dụng phương pháp gom cụm dựa vào độ dốc tích lũy có trọng số để gom cụm dữ liệu chuỗi thời gian, đồng thời áp dụng cấu trúc kd-tree để khởi tạo trung tâm cụm ban đầu cho giải thuật K-Means, và đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số cho giải thuật K-Means, kết quả thu được là chất lượng lời giải khi khởi tạo trung tâm cụm bằng phương pháp dựa vào độ dốc tích lũy có trọng số tốt hơn về chất lượng lời giải lẫn thời gian thực thi so với giải thuật K-Means khởi tạo trung tâm cụm ban đầu một cách ngẫu nhiên hoặc khởi tạo trung tâm cụm ban đầu áp dụng cấu trúc kd-tree.

5.1. Đóng Góp Chính và Ưu Điểm Của Phương Pháp Đề Xuất

Đóng góp chính của luận văn là đề xuất phương pháp khởi tạo tâm cụm dựa trên CWS, giúp cải thiện đáng kể chất lượng và tốc độ của thuật toán K-Means trong gom cụm dữ liệu chuỗi thời gian. Theo kết quả thực nghiệm, phương pháp này vượt trội hơn so với các phương pháp khởi tạo khác và có tính ứng dụng rộng rãi. Phương pháp này giúp khai thác thông tin từ dữ liệu chuỗi thời gian một cách hiệu quả hơn và có thể được sử dụng trong nhiều lĩnh vực khác nhau.

5.2. Hướng Nghiên Cứu Tiếp Theo Tối Ưu và Mở Rộng

Hướng nghiên cứu tiếp theo có thể tập trung vào việc tối ưu hóa thuật toán CWS và mở rộng phương pháp cho các loại dữ liệu chuỗi thời gian phức tạp hơn. Nghiên cứu cũng có thể khám phá các phương pháp kết hợp CWS với các thuật toán gom cụm khác, như DBSCAN hoặc thuật toán gom cụm phân cấp, để tạo ra các giải pháp mạnh mẽ hơn. Ngoài ra, việc phát triển các công cụ trực quan hóa kết quả gom cụm cũng là một hướng đi tiềm năng.

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

CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ Trong chương này sẽ giới thiệu yêu cầu, mục tiêu và nội dung sơ lược của đề tài đồng thời cũng nêu lên sự cần thiết để thực hiện đề tài này. Giới thiệu vấn đề. Dữ liệu chuỗi thời gian (time series) là chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo tại những thời điểm cách đều nhau. Đường biểu diễn một chuỗi thời gian điện tâm đồ [1].

Khai thác dữ liệu thời gian bằng cách gom cụm dữ liệu là một lĩnh vực nghiên cứu trong nhiều thập kỷ qua. Nó có ứng dụng to lớn trong nhiều lĩnh vực khác nhau như y học, tài chính ngân hàng, hệ thống bán hàng, dự báo thời tiết, chứng khoán, khoa học, kỹ thuật. Có nhiều công trình nghiên cứu về gom cụm dữ liệu chuỗi thời gian [2], [3], [4]. Gom cụm dữ liệu được sử dụng như một công cụ phân tích dữ liệu hoặc được sử dụng trong bước tiền xử lý cho các giải thuật khai phá dữ liệu khác [5].

Gom cụm cũng được sử dụng để phân lớp trong một số trường hợp [6]. ĐẶNG THANH HÙNG 1 LUẬN VĂN CAO HỌC Năm 2006, Yang và Wu thực hiện cuộc thăm dò ý kiến từ các nhà nghiên cứu hàng đầu trong lĩnh vực khai phá dữ liệu và máy học nhằm xác định các hướng nghiên cứu nào sẽ là quan trọng và thách thức nhất cho các nghiên cứu trong tương lai thuộc lĩnh vực khai phá dữ liệu. Kết quả khảo sát nêu trong bài báo “10 Challenging Problems in Data Mining Research” cho thấy hướng nghiên cứu về khai phá dữ liệu chuỗi thời gian được xếp thứ 3 trong 10 hướng nghiên cứu sẽ là quan trọng và thách thức nhất [7]. Do đó gom cụm dữ liệu thời gian là một công trình khai thác dữ liệu quan trọng trong rất nhiều lĩnh vực nó là một hướng nghiên cứu rất quan trọng và thách thức vì dữ liệu chuỗi thời gian thì số chiều rất lớn nên việc khai thác dữ liệu chuỗi thời gian cần phải thỏa mãn tính hữu hiệu (có độ phức tạp tính toán thấp) và đảm bảo kết quả đúng.

Đây là một thách thức đã thúc đẩy chúng tôi thực hiện nghiên cứu về lĩnh vực này. Bài toán kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian. Gom cụm dữ liệu là quá trình phân loại các mẫu thành một tập các nhóm dựa trên một hàm đo khoảng cách nào đó, sao cho các phần tử trong cùng một nhóm sẽ rất giống nhau, các phần tử trong các nhóm khác sẽ rất khác nhau.2 minh họa cho kết quả gom cụm dữ liệu trên không gian 2 chiều. Giải thuật gom cụm phổ biến nhất hiện nay đối với dữ liệu chuỗi thời gian là giải thuật k-Means, do giải thuật k-Means dễ hiện thực và có thời gian thực thi khá nhanh.

Ý tưởng của giải thuật này cho trước một số nguyên dương k, với k là số cụm cần gom. Đầu tiên, ta chọn ngẫu nhiên k đối tượng trong không gian dữ liệu làm các trung tâm cụm ban đầu, sau đó duyệt qua các đối tượng dữ liệu còn lại và dựa trên một hàm tính khoảng cách để gán các đối tượng này vào cụm có trung tâm cụm gần nó nhất, sau đó tính toán lại trung tâm cụm và duyệt qua tất cả các đối tượng dữ liệu để gán lại vào cụm hợp lý cho đến khi không có phép gán nào được thực hiện nữa thì giải thuật dừng. ĐẶNG THANH HÙNG 2 LUẬN VĂN CAO HỌC Ý tưởng chính của đề tài này là thực hiện gom cụm dữ liệu chuỗi thời gian với hai bước (1) dựa vào độ dốc tích lũy có trọng số (Cumulative Weighted Slopes) [8] để thu giảm số chiều của dữ liệu thời gian từ một dữ liệu N chiều thu giảm thành một chiều duy nhất, với áp dụng giải thuật k-Means để gom cụm dữ liệu trên thành các trung tâm cụm ban đầu và (2) áp dụng giải thuật k-Means để gom cụm dữ liệu thời gian với các trung tâm cụm ban đầu được xác định bởi bước 1. Kết quả gom cụm của dữ liệu 2 chiều 1.

Mục tiêu nghiên cứu của đề tài. Mục tiêu nghiên cứu của đề tài trên cơ sở dữ liệu chuỗi thời gian tập trung vào các nội dung sau:  Nghiên cứu các phương pháp gom cụm dữ liệu chuỗi thời gian.  Nghiên cứu độ dốc tích lũy có trọng số.  Kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k- Means để gom cụm dữ liệu chuỗi thời gian.

 Nghiên cứu sử dụng kd-tree khởi tạo trung tâm cụm ban đầu.  Thử nghiệm trên các bộ dữ liệu mẫu và so sánh kết quả của khởi tạo trung tâm cụm ban đầu ngẫu nhiên, dựa vào kd-tree và khởi tạo trung tâm cụm ban đầu bằng độ dốc tích lũy có trọng số.  Trực quan hóa kết quả gom cụm dữ liệu chuỗi thời gian. ĐẶNG THANH HÙNG 3 LUẬN VĂN CAO HỌC 1.

Phạm vi nghiên cứu. Phương pháp thu giảm số chiều dựa vào độ dốc tích lũy có trọng số và kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian. Dữ liệu phân tích :  Tập dữ liệu phức hợp Heterogeneous.  Tập dữ liệu chứng khoán Mỹ.

 Tập dữ liệu chứng khoán Việt Nam. Phương pháp nghiên cứu. Sử dụng kết hợp giữa nghiên cứu lý thuyết và nghiên cứu thực tiễn. Nghiên cứu lý thuyết: thu thập các thông tin thông qua nghiên cứu các tài liệu về dữ liệu chuỗi thời gian, các phương pháp gom cụm dữ liệu chuỗi thời gian từ đó rút ra được phương pháp gom cụm chuỗi thời gian thích hợp.

Nghiên cứu thực tiễn: từ kết quả các cơ sở lý thuyết đã rút ra trong quá trình nghiên cứu lý thuyết để áp dụng vào thực tế xây dựng hệ thống gom cụm kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cum dữ liệu chuỗi thời gian. Quá trình nghiên cứu thực tiễn sẽ thực hiện các công việc:  Gom cụm với tập dữ liệu phức hợp dùng các tiêu chí đánh giá như: Jaccard, Rand, FM, CSM, NMI để đánh giá chất lượng gom cụm.  Gom cụm với các tập dữ liệu chứng khoán dùng hàm mục tiêu để đánh giá chất lượng gom cụm.  Điều chỉnh giải thuật và các tham số để đạt kết quả có độ chính xác cao.

Ý nghĩa nghiên cứu. Kết quả nghiên cứu giúp chúng ta đánh giá được chất lượng gom cum của giải thuật k-Means kết hợp với các phương pháp: ĐẶNG THANH HÙNG 4 LUẬN VĂN CAO HỌC  Thu giảm số chiều dựa vào độ dốc tích lũy có trọng số.  Khởi tạo trung tâm cụm ban đầu bằng độ dốc tích lũy có trọng số.  Khởi tạo trung tâm cụm ban đầu bằng kd-tree.

 Khởi tạo trung tâm cụm ban đầu bằng ngẫu nhiên. Từ kết quả đánh giá chất lượng gom cụm của các phương pháp giúp chúng ta lựa chọn phương pháp gom cụm thích hợp cho nhu cầu gom cụm dữ liệu chuỗi thời gian của chúng ta như cần thời gian thực thi nhanh hay cần độ chính xác cao… 1. Tóm tắt kết quả đã đạt được. Chúng tôi đã áp dụng phương pháp gom cụm dựa vào độ dốc tích lũy có trọng số để gom cụm dữ liệu chuỗi thời gian, đồng thời áp dụng cấu trúc kd-tree để khởi tạo trung tâm cụm ban đầu cho giải thuật k-Means, và đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số cho giải thuật k-Means, kết quả thu được là chất lượng lời giải khi khởi tạo trung tâm cụm bằng phương pháp dựa vào độ dốc tích lũy có trọng số tốt hơn về chất lượng lời giải lẫn thời gian thực thi so với giải thuật k-Means khởi tạo trung tâm cụm ban đầu một cách ngẫu nhiên hoặc khởi tạo trung tâm cụm ban đầu áp dụng cấu trúc kd-tree.

Ngoài ra chúng tôi xây dựng được một phương pháp trực quan hóa kết quả gom cụm phù hợp với tập dữ liệu lớn. Cấu trúc luận văn. Các phần còn lại của luận văn được tổ chức như sau: Chương 2: trình bày các lý thuyết và các công trình liên quan làm nguồn tham khảo và là cơ sở cho việc thực hiện luận văn, bao gồm các công trình về độ đo tương tự, các phương pháp thu giảm số chiều, ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian, giải thuật k-Means, giải thuật khởi tạo trung tâm cụm ban đầu và vấn đề chọn giá trị k (số lượng cụm cần gom) tối ưu. Chương 3: trình bày một số vấn đề về gom cụm dữ liệu chuỗi thời gian và đưa ra cách để giải quyết các vấn đề và phác họa kiến trúc tổng quát của hệ thống ĐẶNG THANH HÙNG 5 LUẬN VĂN CAO HỌC “Kết hợp gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian”.

Chương 4: trình bày một số kết quả thực nghiệm và đánh giá. Chương 5: trình bày kết luận của nghiên cứu những đóng góp của đề tài và hướng phát triển. ĐẶNG THANH HÙNG 6 LUẬN VĂN CAO HỌC CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN Chương này trình bày các lý thuyết và các công trình liên quan làm nguồn tham khảo và là cơ sở cho việc thực hiện luận văn, bao gồm các công trình về độ đo tương tự, các phương pháp thu giảm số chiều, ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian, giải thuật k-Means và giải thuật khởi tạo trung tâm cụm ban đầu. Để tính khoảng cách giữa 2 đối tượng X, Y ký hiệu là D(X, Y) có nhiều độ đo tương tự đã được sử dụng như độ đo Euclid, độ đo tương tự giữa các chuỗi nhị phân [9], độ đo tương tự giữa các hàm mật độ xác xuất [10], độ đo xoắn thời gian động [11], độ đo chuỗi con chung dài nhất [12].

Do đó việc lựa chọn một độ đo tương tự tùy thuộc rất nhiều vào lĩnh vực ứng dụng. Trong các bài toán về khai phá dữ liệu chuỗi thời gian, để so sánh hai chuỗi người ta thường sử dụng hai độ đo tương tự là Euclid và xoắn thời gian động (Dynamic Time Warping) để tính khoảng cách giữa 2 đối tượng. Cho hai chuỗi thời gian X = x1, x2, …,xn và Y = y1, y2,…,yn độ đo Euclid giữa hai chuỗi thời gian này được cho bởi công thức. Độ đo khoảng cách Euclid có ưu điểm là dễ hiểu, dễ tính toán, dễ mở rộng cho nhiều bài toán khai phá dữ liệu chuỗi thời gian như gom cụm, phân lớp, nhận dạng mô típ, v.