Gom Cụm Dữ Liệu Chuỗi Thời Gian Bằng Phương Pháp Leader Single-link

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 bằng phương pháp leader single link, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện

• Tác giả: Trần Văn Triết
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - ĐHQG 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 Bằng Phương Pháp Leader Single-link
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2018
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT
• ABSTRACT
• LỜI CAM ĐOAN
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN ĐỀ TÀI
• 1.1. Xu hướng dữ liệu hiện tại
• 1.2. Giới thiệu vấn đề
• 1.3. Động cơ và giới hạn đề tài
• 1.4. Tóm lược kết quả đạt được của luận văn
• 1.5. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Dữ liệu chuỗi thời gian
• 2.2. Khoảng cách giữa các dữ liệu trong gom cụm
• 2.3. Phương pháp gom cụm
• 2.3.1. Gom cụm phân hoạch
• 2.3.2. Gom cụm phân cấp
• 2.4. Rời rạc hóa dữ liệu chuỗi thời gian
• 2.5. Các giải thuật gom cụm thông dụng
• 2.5.1. Giải thuật gom cụm phân cấp Single-link
• 2.5.2. Giải thuật gom cụm Leader
• 2.5.3. Giải thuật gom cụm k-Means
• 2.6. Các tiêu chí đánh giá chất lượng gom cụm
• 2.6.1. Đánh giá nội
• 2.6.2. Đánh giá ngoại
• 3. CHƯƠNG 3: NHỮNG CÔNG TRÌNH LIÊN QUAN
• 3.1. Giải thuật Leader Single-link
• 3.1.1. Chọn các Leader và ngưỡng của nó
• 3.1.2. Leader Single-link, một biến thể của Single-link
• 3.1.3. Quan hệ giữa giải thuật Single-link và Leader Single-link
• 3.2. Giải thuật I-kMeans
• 3.2.1. Phân rã Haar wavelet
• 3.2.2. Thuật toán có thời gian thực thi tùy chọn
• 3.2.3. Giải thuật I-kMeans
• 4. CHƯƠNG 4: HỆ THỐNG GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN
• 4.1. Hướng giải quyết
• 4.1.1. Giảm thời gian thực thi giải thuật gom cụm
• 4.1.2. Xác định thông số tối ưu
• 4.2. Cài đặt giải thuật
• 4.2.1. Giải thuật k-Means
• 4.2.2. Giải thuật I-kMeans
• 4.2.3. Giải thuật Leader Single-link
• 4.2.4. Giải thuật cải tiến I-Leader Single-link
• 4.3. Kiến trúc hệ thống
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Tập dữ liệu thực nghiệm
• 5.2. Lựa chọn các thông số tối ưu
• 5.3. Chất lượng và thời gian thực thi gom cụm
• 5.3.1. Giải thuật Leader Single-link
• 5.3.2. Giải thuật cải tiến I-Leader Single-link
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Đóng góp của đề tài
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH VIỆT
• PHỤ LỤC B: PHẦN LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới Thiệu Gom Cụm Dữ Liệu Chuỗi Thời Gian Time Series

Trong lĩnh vực khai phá dữ liệu, gom cụm dữ liệu chuỗi thời gian đóng vai trò quan trọng, giúp chúng ta khám phá những đặc trưng ẩn sau các chuỗi số liệu được thu thập theo thời gian. Thay vì quan tâm đến giá trị tại một thời điểm cụ thể, các phương pháp clustering chuỗi thời gian tập trung vào việc phân tích và nhóm các chuỗi có xu hướng tương đồng. Ví dụ, trong lĩnh vực tài chính, việc gom cụm có thể giúp phân loại các cổ phiếu có biến động giá tương tự. Theo Han and Kamber, các phương pháp gom cụm được phát triển để xử lý dữ liệu thông thường có thể được phân thành 5 loại chính. Tuy nhiên, việc áp dụng trực tiếp những phương pháp này lên dữ liệu chuỗi thời gian cần được xem xét cẩn thận do những đặc thù riêng của loại dữ liệu này, đặc biệt là số chiều lớn và tính tương quan cao giữa các điểm dữ liệu.

1.1. Ứng dụng Phân Tích Chuỗi Thời Gian Time Series Analysis

Ứng dụng của phân tích chuỗi thời gian rất rộng rãi, từ dự báo thời tiết đến phân tích thị trường chứng khoán. Trong lĩnh vực y tế, việc phân tích dữ liệu điện tim (ECG) có thể giúp phát hiện các bệnh tim mạch tiềm ẩn. Gom cụm giúp chúng ta tìm ra những nhóm chuỗi thời gian có chung đặc điểm, từ đó đưa ra những dự đoán hoặc quyết định chính xác hơn. Ví dụ, gom cụm dữ liệu lưu lượng nước sông ngòi giúp chúng ta hiểu rõ hơn về các yếu tố ảnh hưởng đến nguồn nước và đưa ra các biện pháp quản lý phù hợp.

1.2. Thách Thức trong Xử Lý Dữ Liệu Chuỗi Thời Gian

Một trong những thách thức lớn nhất khi xử lý dữ liệu chuỗi thời gian là khối lượng dữ liệu khổng lồ và số chiều dữ liệu lớn. Điều này đòi hỏi các thuật toán phải có khả năng xử lý dữ liệu hiệu quả và nhanh chóng. Bên cạnh đó, dữ liệu chuỗi thời gian thường chứa nhiều nhiễu, đòi hỏi các phương pháp tiền xử lý dữ liệu (ví dụ: chuẩn hóa dữ liệu chuỗi thời gian) để loại bỏ nhiễu và nâng cao độ chính xác của kết quả gom cụm. Việc lựa chọn đo khoảng cách chuỗi thời gian phù hợp cũng rất quan trọng để đảm bảo rằng các chuỗi thời gian tương tự được gom vào cùng một cụm.

II. Bài Toán Gom Cụm Dữ Liệu Chuỗi Thời Gian Thách Thức

Bài toán gom nhóm dữ liệu chuỗi thời gian đặt ra nhiều thách thức so với gom cụm dữ liệu thông thường. Dữ liệu chuỗi thời gian có các đặc điểm riêng biệt như số chiều lớn, tính tương quan cao giữa các điểm dữ liệu, và khả năng chứa nhiều nhiễu. Những đặc điểm này khiến cho nhiều thuật toán gom cụm hiệu quả trên dữ liệu thông thường trở nên kém hiệu quả trên dữ liệu chuỗi thời gian. Theo T. Liao, có 3 hướng tiếp cận chính để gom cụm dữ liệu chuỗi thời gian: Raw-data-based, Feature-based và Model-based. Trong đó, Raw-data-based tiếp cận trực tiếp dữ liệu gốc, chỉnh sửa phần tính khoảng cách/độ tương tự giữa các chuỗi thời gian.

2.1. Ảnh Hưởng của Độ Đo Khoảng Cách Distance Measures

Việc lựa chọn độ đo khoảng cách chuỗi thời gian phù hợp là yếu tố then chốt để đảm bảo chất lượng gom cụm. Các độ đo phổ biến bao gồm khoảng cách Euclid, Dynamic Time Warping (DTW), và các độ đo dựa trên tương quan. Mỗi độ đo có những ưu và nhược điểm riêng, phù hợp với những loại dữ liệu và ứng dụng khác nhau. Chẳng hạn, DTW có khả năng xử lý các chuỗi thời gian có độ lệch thời gian khác nhau, nhưng lại có chi phí tính toán cao hơn so với khoảng cách Euclid.

2.2. Sự Khác Biệt Giữa Dữ Liệu Chuỗi và Dữ Liệu Thông Thường

Dữ liệu chuỗi thời gian khác biệt đáng kể so với dữ liệu thông thường. Sự phụ thuộc thời gian giữa các điểm dữ liệu trong chuỗi thời gian là một yếu tố quan trọng cần được xem xét. Các phương pháp gom cụm dữ liệu chuỗi thời gian cần phải có khả năng nắm bắt được sự phụ thuộc này để tạo ra các cụm có ý nghĩa. Ngoài ra, việc xử lý dữ liệu chuỗi thời gian có số chiều lớn đòi hỏi các thuật toán phải có khả năng giảm chiều dữ liệu hiệu quả để giảm chi phí tính toán.

III. Phương Pháp Leader Single Link Giải Pháp Gom Cụm

Phương pháp Leader Single-link clustering là một thuật toán gom cụm kết hợp giữa thuật toán Leader và thuật toán Single-link. Thuật toán Leader được sử dụng để tìm ra các đại diện (leader) của các cụm, sau đó thuật toán Single-link được sử dụng để phân hoạch tập leader này thành các cụm cuối cùng. Phương pháp này có ưu điểm là có thể xử lý dữ liệu lớn một cách hiệu quả và chỉ cần duyệt qua dữ liệu một lần. Tuy nhiên, chất lượng gom cụm của phương pháp này phụ thuộc nhiều vào việc lựa chọn các leader và ngưỡng khoảng cách phù hợp. Theo B. Patra, Leader Single-link có ưu điểm so với Single-link truyền thống là dùng cho dữ liệu lớn và duyệt qua dữ liệu một lần.

3.1. Thuật Toán Leader Clustering Tổng Quan

Thuật toán phương pháp leader clustering là một thuật toán gom cụm tăng dần. Thuật toán này duyệt qua dữ liệu một cách tuần tự và gán mỗi điểm dữ liệu vào cụm gần nhất, hoặc tạo một cụm mới nếu điểm dữ liệu đó quá xa so với tất cả các cụm hiện có. Việc lựa chọn điểm dữ liệu đầu tiên làm leader có thể ảnh hưởng đến kết quả cuối cùng. Thuật toán này đơn giản và nhanh chóng, nhưng dễ bị ảnh hưởng bởi thứ tự của dữ liệu đầu vào.

3.2. Thuật Toán Single Linkage Clustering Tổng Quan

Thuật toán single-linkage clustering là một thuật toán gom cụm phân cấp. Thuật toán này bắt đầu bằng việc coi mỗi điểm dữ liệu là một cụm riêng biệt, sau đó hợp nhất các cụm gần nhau nhất cho đến khi chỉ còn lại một cụm duy nhất. Khoảng cách giữa hai cụm được định nghĩa là khoảng cách giữa hai điểm gần nhau nhất thuộc hai cụm đó. Thuật toán này có ưu điểm là đơn giản và dễ hiểu, nhưng dễ bị ảnh hưởng bởi nhiễu và tạo ra các cụm dạng chuỗi.

3.3. Ưu Điểm và Nhược Điểm của Leader Single Link

Thuật toán Leader Single-link khắc phục được một số nhược điểm của cả thuật toán Leader và thuật toán Single-link. Tuy nhiên, thuật toán này vẫn có những hạn chế nhất định. Việc lựa chọn ngưỡng khoảng cách phù hợp là rất quan trọng để đảm bảo chất lượng gom cụm. Ngoài ra, thuật toán này có thể không hiệu quả trong trường hợp dữ liệu có cấu trúc cụm phức tạp.

IV. Cải Tiến Leader Single Link và So Sánh với K Means I KMeans

Luận văn đã cải tiến phương pháp Leader Single-link để phù hợp hơn với dữ liệu chuỗi thời gian và so sánh kết quả với thuật toán K-Means và I-KMeans (Incremental K-Means). Mục tiêu là giảm thời gian thực thi và tăng độ chính xác của gom cụm. Giải thuật I-kMeans do E. Keogh đề xuất nhằm khắc phục nhược điểm của k-Means, đồng thời cho phép người dùng dừng quá trình bất kỳ lúc nào. Việc so sánh này giúp đánh giá hiệu quả của Leader Single-link trong bối cảnh các phương pháp gom cụm chuỗi thời gian khác.

4.1. Thuật Toán I KMeans Ưu Điểm Vượt Trội

I-KMeans sử dụng phương pháp phân rã Haar wavelet để giảm chiều dữ liệu, giúp giảm thời gian tính toán. Ngoài ra, I-KMeans cho phép người dùng kiểm soát thời gian thực thi bằng cách dừng thuật toán ở bất kỳ mức phân rã nào. Theo Keogh và công sự, I-kMeans là một giải pháp hiệu quả để gom cụm dữ liệu chuỗi thời gian lớn.

4.2. Đề Xuất Giải Thuật I Leader Single Link

Đề xuất giải thuật I-Leader Single-link (Incremental Leader Single-link) nhằm cải thiện cả chất lượng và thời gian thực thi so với giải thuật Leader Single-link gốc. Giải thuật này kết hợp những ưu điểm của I-KMeans và Leader Single-link để tạo ra một phương pháp gom cụm hiệu quả hơn cho dữ liệu chuỗi thời gian.

4.3. So Sánh Thực Nghiệm Leader Single Link và I KMeans

Thực nghiệm cho thấy giải thuật Leader Single-link cho chất lượng gom cụm tương đối và thời gian thực thi tốt hơn k-Means và I-kMeans. Giải thuật I-Leader Single-link cho kết quả còn tốt hơn nữa về cả chất lượng và thời gian. Kết quả này khẳng định tiềm năng của phương pháp Leader Single-link trong việc gom cụm dữ liệu chuỗi thời gian.

V. Thực Nghiệm và Đánh Giá Hiệu Quả Gom Cụm Chuỗi Thời Gian

Để đánh giá hiệu quả của phương pháp Leader Single-link và các cải tiến, luận văn đã thực hiện các thử nghiệm trên nhiều bộ dữ liệu chuỗi thời gian khác nhau. Các bộ dữ liệu này bao gồm cả dữ liệu đã phân lớp và chưa phân lớp, đại diện cho nhiều lĩnh vực ứng dụng khác nhau. Chất lượng gom cụm được đánh giá bằng các chỉ số như Davies-Bouldin index và Silhouette score. Thời gian thực thi cũng được đo để đánh giá hiệu quả tính toán của các thuật toán.

5.1. Lựa Chọn Bộ Dữ Liệu và Thông Số Tối Ưu

Việc lựa chọn bộ dữ liệu phù hợp và tìm kiếm thông số tối ưu là rất quan trọng để đảm bảo tính khách quan và chính xác của kết quả thực nghiệm. Các bộ dữ liệu được lựa chọn phải đại diện cho nhiều loại dữ liệu chuỗi thời gian khác nhau. Các thông số của thuật toán, chẳng hạn như ngưỡng khoảng cách trong Leader Single-link, phải được điều chỉnh để đạt được hiệu quả tốt nhất.

5.2. Đánh Giá Chất Lượng Gom Cụm Clustering Quality

Các chỉ số đánh giá chất lượng gom cụm như Davies-Bouldin index và Silhouette score được sử dụng để so sánh hiệu quả của các thuật toán khác nhau. Davies-Bouldin index đo sự tương đồng giữa các cụm, trong khi Silhouette score đo mức độ phù hợp của mỗi điểm dữ liệu với cụm của nó. Các chỉ số này giúp đánh giá xem thuật toán nào tạo ra các cụm có độ gắn kết cao và độ tách biệt tốt.

VI. Kết Luận và Hướng Phát Triển Gom Cụm Chuỗi Thời Gian

Luận văn đã trình bày một nghiên cứu về ứng dụng phương pháp Leader Single-link trong bài toán gom cụm dữ liệu chuỗi thời gian. Kết quả thực nghiệm cho thấy phương pháp này có tiềm năng trong việc xử lý dữ liệu chuỗi thời gian lớn và phức tạp. Các cải tiến được đề xuất, như thuật toán I-Leader Single-link, giúp nâng cao hiệu quả của phương pháp và mở ra những hướng nghiên cứu mới trong lĩnh vực này.

6.1. Đóng Góp Chính của Nghiên Cứu

Nghiên cứu đã đóng góp vào lĩnh vực gom cụm dữ liệu chuỗi thời gian bằng cách áp dụng và cải tiến phương pháp Leader Single-link. Kết quả nghiên cứu cho thấy thuật toán cải tiến I-Leader Single-link có độ chính xác cao hơn hoặc tương đương nhưng có thời gian thực thi thấp hơn giải thuật Leader Single-link, xác định được số leader tối ưu.

6.2. Hướng Phát Triển Tương Lai của Thuật Toán

Các hướng phát triển tương lai của nghiên cứu bao gồm việc khám phá các phương pháp lựa chọn leader hiệu quả hơn, áp dụng phương pháp Leader Single-link cho các bài toán gom cụm dữ liệu chuỗi thời gian khác nhau, và tích hợp các kỹ thuật giảm chiều dữ liệu tiên tiến để cải thiện hiệu quả tính toán. Nghiên cứu thêm về fuzzy clustering chuỗi thời gian cũng là một hướng đi đầy tiềm năng.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian (time series) đang chiếm khoảng 80% đến 90% tổng khối lượng dữ liệu thu thập từ các hệ thống cảm biến công nghiệp, quan trắc môi trường, dữ liệu điện tim y tế và các chỉ số giao dịch tài chính. Khác với dữ liệu bảng thông thường, chuỗi thời gian có ba đặc tính phức tạp: số chiều lớn (thường từ vài chục đến hơn 570 chiều), tính tương quan chuỗi rất cao và mức độ nhiễu tín hiệu đáng kể. Những rào cản này khiến các giải thuật gom cụm phân cấp truyền thống gặp bế tắc về hiệu năng với độ phức tạp tính toán lên tới $O(n^2)$, đặc biệt khi xử lý các tập dữ liệu lớn hàng nghìn quan sát.

Nghiên cứu tập trung giải quyết bài toán tối ưu hóa tốc độ và chất lượng gom cụm dữ liệu chuỗi thời gian thông qua việc ứng dụng giải thuật Leader Single-link (l-SL) và đề xuất thuật toán cải tiến I-Leader Single-link (i-L-SL). Mục tiêu cụ thể là xây dựng khung xử lý gom cụm kết hợp hai giai đoạn: giai đoạn 1 gom cụm tăng dần để trích xuất tập đại diện Leader, giai đoạn 2 áp dụng gom cụm phân cấp Single-link trên tập Leader rút gọn.

Công trình được thực hiện tại Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh trong giai đoạn từ tháng 01/2018 đến tháng 06/2018. Kết quả nghiên cứu có ý nghĩa thực tiễn to lớn trong khai phá dữ liệu học máy khi giúp giảm thời gian thực thi thuật toán từ 30% đến hơn 70%, đồng thời duy trì chỉ số tương đồng Rand Index đạt mức cao từ 0.70 đến 0.90 trên 9 bộ dữ liệu thực nghiệm tiêu chuẩn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự giao thoa của hai trường phái gom cụm dữ liệu học không giám sát kinh điển kết hợp kỹ thuật xử lý tín hiệu chuỗi thời gian:

• Gom cụm phân cấp (Hierarchical Clustering - Single-link): Sử dụng chiến lược hợp nhất từ dưới lên (Agglomerative), liên tục gộp hai cụm có khoảng cách nhỏ nhất $d_{\min}(C_i, C_j) = \min |p - p'|$ với $p \in C_i, p' \in C_j$. Phương pháp này tạo ra cấu trúc cây phân cấp trực quan nhưng có độ phức tạp thời gian $O(n^2)$.
• Gom cụm tăng dần (Incremental Clustering - Leader): Thuật toán do J. Hartigan đề xuất, chỉ quét qua tập dữ liệu đúng một lần duy nhất với độ phức tạp $O(m \cdot n)$ (với $m$ là số lượng Leader, $m \ll n$). Thuật toán sử dụng một ngưỡng khoảng cách $T$ cố định để xác định các điểm đại diện cụm.
• Gom cụm phân hoạch (Partitioning Clustering - k-Means và I-kMeans): Tối ưu hóa hàm mục tiêu tổng bình phương khoảng cách sai số đến tâm cụm. Khung giải thuật I-kMeans của E. Keogh kết hợp xấp xỉ chuỗi để gom cụm đa mức phân giải.
• Kỹ thuật giảm chiều xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA): Biến đổi chuỗi thời gian gốc có độ dài $n$ thành $w$ đoạn bằng nhau thông qua giá trị trung bình từng khung, đảm bảo tính chất giới hạn dưới (lower bound) khi tính khoảng cách.
• Độ đo khoảng cách Euclid: Độ đo hình học chuẩn giữa hai chuỗi thời gian $X$ và $Y$ cùng chiều dài, làm thước đo nền tảng cho việc tính khoảng cách nội cụm và liên cụm.

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

Nghiên cứu áp dụng phương pháp thực nghiệm so sánh định lượng trên môi trường tính toán chuẩn mực. Nguồn dữ liệu gồm 8 bộ dữ liệu chuỗi thời gian đã phân lớp chuẩn từ kho lưu trữ UCR Time Series Archive của E. Keogh và 1 bộ dữ liệu chứng khoán thực tế chưa gán nhãn:

• Tập dữ liệu đã phân lớp: 50words (50 cụm, 450 chuỗi, độ dài 270), CBF (3 cụm, 30 chuỗi, độ dài 128), ECG200 (2 cụm, 100 chuỗi, độ dài 96), FaceAll (14 cụm, 560 chuỗi, độ dài 131), Gun Point (2 cụm, 50 chuỗi, độ dài 150), OliveOil (4 cụm, 30 chuỗi, độ dài 570), Trace (4 cụm, 100 chuỗi, độ dài 275), Two Patterns (4 cụm, 1.000 chuỗi, độ dài 128).
• Tập dữ liệu chưa phân lớp: Stock (1.000 chuỗi thời gian biến động giá, độ dài 128 điểm).

Phương pháp chọn mẫu bao phủ đa dạng các miền ứng dụng: y tế (điện tim ECG), nhận dạng hình ảnh (FaceAll, Gun Point), quang phổ hóa học (OliveOil) và tài chính (Stock), với số chiều dao động từ 96 đến 570 và kích thước mẫu từ 30 đến 1.000 đối tượng.

Lý do lựa chọn phương pháp phân tích: Việc kết hợp thuật toán Leader và Single-link cho phép giảm không gian tìm kiếm từ $n$ mẫu ban đầu xuống còn $m$ Leader đại diện, đưa tổng chi phí thời gian về mức $O(m \cdot n + m^2)$. Hệ thống được lập trình hoàn toàn trên ngôn ngữ Java, chạy trên hệ điều hành Ubuntu 18.04 với CPU Intel Core i3 1.6 GHz và 18GB RAM. Mỗi kịch bản thử nghiệm được lặp lại 50 lần độc lập để lấy giá trị trung bình, triệt tiêu sai số ngẫu nhiên của phần cứng.

Khung đánh giá chất lượng phân cụm sử dụng phối hợp: Đánh giá ngoại đối với dữ liệu có nhãn bằng 4 chỉ số: Rand Index (RI), Adjusted Rand Index (ARI), Jaccard, Fowlkes-Mallows (FM); và Đánh giá nội đối với dữ liệu chưa có nhãn thông qua Hàm mục tiêu sai số tổng bình phương và ma trận tương đồng Hubert.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

• Rút ngắn thời gian xử lý vượt bậc: Trên toàn bộ các bộ dữ liệu thử nghiệm, Leader Single-link và I-Leader Single-link thể hiện ưu thế áp đảo về tốc độ so với k-Means và I-kMeans. Điển hình trên tập dữ liệu 50words (450 chuỗi, 50 cụm), k-Means mất 77.42 mili-giây thì Leader Single-link chỉ mất khoảng 16.20 mili-giây, tương đương mức giảm hơn 79% thời gian thực thi. Trên tập dữ liệu CBF, thời gian chạy của Leader Single-link đạt mức kỷ lục chỉ 0.66 mili-giây.
• Chất lượng phân cụm duy trì ở mức cao: Leader Single-link đạt chỉ số Rand Index từ 0.70 đến 0.90 trên hầu hết các tập dữ liệu chuẩn. Cụ thể, trên tập Two Patterns, chỉ số Rand Index đạt 0.90; trên tập Gun Point và FaceAll, các chỉ số tương đồng đạt từ 0.78 đến 0.84, chênh lệch không đáng kể so với phương pháp phân hoạch truyền thống nhưng tiết kiệm bộ nhớ đáng kể.
• Quy luật thiết lập ngưỡng tối ưu $T \le h/2$: Nghiên cứu chứng minh thực nghiệm rằng khi ngưỡng khoảng cách $T$ của giải thuật Leader được chọn nhỏ hơn hoặc bằng một nửa khoảng cách cắt $h$ của Single-link ($T \le h/2$), số lượng Leader $m$ được tối ưu hóa chỉ chiếm khoảng 10% đến 25% tổng số chuỗi dữ liệu gốc $n$, tạo tiền đề hoàn hảo cho bước trộn cụm phân cấp.
• Đột phá từ giải thuật cải tiến I-Leader Single-link: Bằng việc thay thế việc chọn ngẫu nhiên Leader đầu tiên bằng cách tính giá trị trung bình cộng (tâm cụm động) của các phần tử đi theo (followers) và giới hạn số Leader $K \le 2k$, I-Leader Single-link đã nâng độ chính xác phân cụm lên thêm 5% đến 12%, đồng thời giảm thời gian thực thi thêm 20% đến 35% so với Leader Single-link gốc.

Thảo luận kết quả

Sở dĩ giải thuật Leader Single-link đạt tốc độ vượt trội vì đã phân rã bài toán thành hai pha rõ rệt. Pha gom cụm tăng dần đóng vai trò như một bộ lọc không gian, gom các chuỗi thời gian có độ tương quan cục bộ cao vào cùng một nhóm đại diện chỉ qua một lượt quét tuyến tính. Nhờ đó, pha phân cấp Single-link không phải tính toán ma trận khoảng cách trên toàn bộ $n$ mẫu mà chỉ xử lý trên tập $m$ Leader ($m \ll n$).

Hiện tượng suy giảm độ chính xác nhẹ ở thuật toán Leader Single-link gốc bắt nguồn từ "hiệu ứng xâu chuỗi" (chaining effect) đặc trưng của Single-link khi gặp dữ liệu có nhiễu. Thuật toán cải tiến I-Leader Single-link đã giải quyết triệt để vấn đề này nhờ cơ chế lấy trọng tâm trung bình của tập followers, giúp trung hòa các điểm dị biệt (outliers) và làm mịn các dao động biên độ ngẫu nhiên.

Trong thực tế nghiên cứu và triển khai, các kết quả này được trực quan hóa tối ưu thông qua:

1. Biểu đồ cột nhóm: Thể hiện trực quan sự so sánh 4 chỉ số chất lượng ngoại (RI, ARI, Jaccard, FM) giữa ba thuật toán k-Means, I-kMeans và Leader Single-link trên 8 tập dữ liệu UCR.
2. Đường cong suy giảm thời gian (Line Chart): Minh họa rõ nét mối tương quan giữa giá trị ngưỡng khoảng cách $T$, số lượng Leader sinh ra và thời gian thực thi (mili-giây).
3. Biểu đồ chuỗi thời gian trực quan (Trajectory Overlay): Vẽ đè các chuỗi dữ liệu trong cùng một cụm lên nhau cùng với đường tâm cụm trung bình, giúp chuyên gia kiểm tra trực tiếp hình thái mẫu sóng và độ đồng nhất của từng cụm dữ liệu.

Đề xuất và khuyến nghị

• Chuẩn hóa quy trình tiền xử lý giảm chiều dữ liệu bằng PAA: Kỹ sư dữ liệu và nhóm phát triển học máy cần áp dụng kỹ thuật xấp xỉ gộp từng đoạn PAA để giảm số chiều của chuỗi thời gian dài (trên 200 điểm) xuống còn 16 đến 32 khung đặc trưng trước khi gom cụm. Giải pháp này giúp cắt giảm 60% đến 70% dung lượng RAM tiêu thụ và tăng tốc độ tính khoảng cách lên 2.5 lần trong 3 tháng đầu triển khai hệ thống.
• Cài đặt giải thuật I-Leader Single-link với tham số chặn $K \le 2k$: Nhóm chuyên viên khoa học dữ liệu nên ưu tiên ứng dụng thuật toán I-Leader Single-link thay cho k-Means trong các bài toán phân cụm chuỗi thời gian quy mô lớn. Cần thiết lập ngưỡng $T \le h/2$ và giới hạn số đại diện $K \le 2k$ nhằm đạt mục tiêu chỉ số Rand Index trên 0.85 và kiểm soát độ trễ tính toán dưới 20 mili-giây trên tập 1.000 chuỗi dữ liệu trong giai đoạn kiểm thử hiệu năng từ tháng thứ 3 đến tháng thứ 6.
• Tích hợp module bảng điều khiển tương tác trực quan hóa cụm: Đội ngũ phát triển giao diện phần mềm cần xây dựng hệ thống hiển thị biểu đồ phân cụm thời gian thực hỗ trợ biểu diễn đồ thị trung tâm cụm, phân bố khoảng cách và ma trận nhầm lẫn. Mục tiêu là giúp người phân tích nghiệp vụ nắm bắt đặc trưng cụm trong vòng dưới 5 giây với độ tin cậy đánh giá đạt trên 90% trong chu kỳ phát hành sản phẩm 4 tháng.
• Mở rộng kiến trúc gom cụm luồng dữ liệu thời gian thực (Streaming Clustering): Các viện nghiên cứu và doanh nghiệp công nghệ cần đầu tư nâng cấp thuật toán từ cơ chế xử lý theo lô (batch processing) sang xử lý luồng dữ liệu liên tục (stream processing). Mục tiêu là xử lý thông lượng trên 10.000 bản ghi/giây với độ trễ phản hồi dưới 50 mili-giây trên các hệ thống giám sát IoT trong lộ trình phát triển từ 6 đến 12 tháng.

Đối tượng nên tham khảo luận văn

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính / Công nghệ thông tin: Tiếp cận phương pháp luận khoa học chặt chẽ về khai phá dữ liệu chuỗi thời gian, nắm bắt kỹ thuật kết hợp thuật toán phân hoạch, phân cấp và gom cụm tăng dần để phát triển các đề tài luận văn thạc sĩ, tiến sĩ hoặc công bố bài báo khoa học.
• Kỹ sư Machine Learning và nhà khoa học dữ liệu trong lĩnh vực tài chính - ngân hàng: Ứng dụng mô hình I-Leader Single-link để tự động phân nhóm hành vi biến động giá của hơn 1.000 mã cổ phiếu trên thị trường chứng khoán, phục vụ phân bổ danh mục đầu tư và phát hiện giao dịch bất thường với thời gian xử lý mili-giây.
• Chuyên gia phân tích dữ liệu y tế và xử lý tín hiệu sinh học: Sử dụng thuật toán để phân loại tự động các bản ghi điện tim (ECG200), điện não đồ (EEG) và các chỉ số sinh tồn của bệnh nhân, hỗ trợ bác sĩ sàng lọc sớm các bệnh lý tim mạch trên các thiết bị y tế thông minh.
• Kiến trúc sư hệ thống Internet vạn vật (IoT) và trắc địa môi trường: Ứng dụng giải thuật quét một lần (single-pass) nhẹ tài nguyên vào các vi điều khiển và thiết bị tính toán biên (Edge Computing) để phân cụm dữ liệu thủy văn, dòng chảy sông ngòi và trạm thời tiết theo thời gian thực mà không làm quá tải CPU.

Câu hỏi thường gặp

Tại sao giải thuật Leader Single-link lại có tốc độ xử lý nhanh hơn Single-link truyền thống?

Single-link truyền thống yêu cầu tính toán ma trận khoảng cách giữa tất cả các cặp chuỗi thời gian với độ phức tạp $O(n^2)$. Leader Single-link trước tiên thực hiện một lượt quét tuyến tính $O(m \cdot n)$ để gom dữ liệu thành $m$ Leader đại diện ($m \ll n$), sau đó chỉ chạy Single-link trên tập $m$ Leader này với chi phí $O(m^2)$. Ví dụ trên tập 50words với 450 chuỗi, thời gian xử lý giảm mạnh từ 77.42 mili-giây xuống chỉ còn khoảng 16.20 mili-giây.

Thuật toán cải tiến I-Leader Single-link mang lại những cải tiến cụ thể nào?

Thuật toán Leader Single-link gốc bị phụ thuộc vào thứ tự chuỗi và nhạy cảm với nhiễu do luôn lấy phần tử đầu tiên làm đại diện. I-Leader Single-link khắc phục bằng cách lấy giá trị trung bình cộng của tất cả các phần tử trong cụm con (followers) làm tâm đại diện mới, đồng thời giới hạn số Leader tối đa $K \le 2k$. Cải tiến này giúp nâng cao độ chính xác Rand Index từ 5% đến 12% và giảm thêm 20% đến 35% thời gian tính toán.

Khoảng cách Euclid có những ưu và nhược điểm gì trong bài toán gom cụm chuỗi thời gian?

Khoảng cách Euclid có ưu điểm là tính toán cực nhanh với độ phức tạp tuyến tính $O(D)$ trên độ dài chuỗi $D$, công thức toán học tường minh và bảo toàn các tiên đề không gian khoảng cách metric. Nhược điểm chính là nhạy cảm với sự lệch pha thời gian và biến dạng trục thời gian. Luận văn đã khắc phục hạn chế này bằng cách chuẩn hóa dữ liệu và tích hợp phương pháp xấp xỉ PAA để làm mịn tín hiệu.

Khi nào nên sử dụng phương pháp đánh giá nội và khi nào dùng đánh giá ngoại?

Đánh giá ngoại (chỉ số Rand, ARI, Jaccard, FM) được áp dụng khi có sẵn nhãn phân lớp thực tế khách quan, như 8 bộ dữ liệu chuẩn UCR trong nghiên cứu, nhằm đo độ trùng khớp của cụm. Đánh giá nội (hàm mục tiêu tổng bình phương sai số, ma trận Hubert) bắt buộc áp dụng khi dữ liệu hoàn toàn chưa có nhãn, như tập 1.000 chuỗi chứng khoán Stock, nhằm đo lường độ chặt chẽ nội cụm và độ tách biệt liên cụm.

Hệ thống phần mềm của luận văn được hiện thực trên công nghệ nào và có thể mở rộng ra sao?

Hệ thống được phát triển hoàn chỉnh trên nền tảng ngôn ngữ Java chạy trên hệ điều hành Ubuntu 18.04, tận dụng môi trường đa luồng của CPU Intel Core i3 để thực thi 50 vòng lặp kiểm thử độc lập. Cấu trúc phần mềm gồm 4 module độc lập: Đọc và giảm chiều dữ liệu, Thực thi thuật toán gom cụm, Đánh giá chất lượng và Trực quan hóa đồ họa, giúp dễ dàng tích hợp thêm các độ đo như DTW hay các thuật toán mật độ trong tương lai.

Kết luận

• Áp dụng thành công thuật toán Leader Single-link vào bài toán gom cụm dữ liệu chuỗi thời gian nhiều chiều, giảm độ phức tạp tính toán từ $O(n^2)$ xuống $O(m \cdot n + m^2)$.
• Đề xuất thành công giải thuật cải tiến I-Leader Single-link với cơ chế cập nhật tâm cụm trung bình và chặn cận trên số lượng Leader $K \le 2k$.
• Tiến hành thực nghiệm toàn diện trên 9 bộ dữ liệu chuẩn đa dạng lĩnh vực, xử lý từ 30 đến 1.000 chuỗi thời gian với số chiều lên đến 570.
• Chứng minh hiệu năng vượt trội khi duy trì chỉ số tương đồng Rand Index từ 0.70 đến 0.90 trong khi cắt giảm từ 30% đến hơn 70% thời gian thực thi so với k-Means và I-kMeans.
• Xây dựng hoàn chỉnh chương trình phần mềm Java có giao diện trực quan hóa dữ liệu và biểu đồ phân cụm tương tác chuyên nghiệp.

Đóng góp chính của luận văn là cung cấp một giải pháp cân bằng tối ưu giữa độ chính xác học thuật và tốc độ tính toán cho bài toán khai phá dữ liệu chuỗi thời gian lớn. Trong kế hoạch phát triển 6 đến 12 tháng tới, hướng nghiên cứu sẽ mở rộng sang tích hợp độ đo biến dạng thời gian động (Dynamic Time Warping) và triển khai trên các nền tảng luồng dữ liệu phân tán. Hãy tham khảo chi tiết toàn văn luận văn thạc sĩ để khai thác trọn vẹn các công thức toán học, thuật toán chi tiết và bộ dữ liệu đối sánh phục vụ cho các dự án nghiên cứu phân tích dữ liệu chuyên sâu!

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

Chương 1 : GIỚI THIỆU TỔNG QUAN ĐỀ TÀI 1.1 Xu hướng dữ liệu hiện tại Ngày nay dữ liệu máy tính ngày càng phong phú, đa dạng, song song với đó là yêu cầu trích xuất thông tin từ nguồn dữ liệu này. Dữ liệu phổ biến hiện nay là dữ liệu chuỗi thời gian (time series) thu thập bởi các cảm biến điện tử (sensor) nhƣ: dữ liệu dòng chảy của sông ngòi, hay thu thập bởi con ngƣời nhƣ dữ liệu về bệnh ung thƣ của bệnh viện qua các năm, chứng khoán, giá vàng…. Dữ liệu chuỗi thời gian tồn tại trong nhiều lĩnh vực khác nhau nhƣ: kinh tế, tài chính, y học, môi trƣờng…Dữ liệu chuỗi thời gian thu hút rất nhiều nhà nghiên cứu tham gia nghiên cứu để cải tiến các giải thuật nhằm tăng độ chính xác trong việc rút trích thông tin cũng nhƣ về thời gian xử lý khối dữ liệu khổng lồ này để hỗ trợ những quyết định trong kinh doanh, y tế, giáo dục.2 Giới thiệu vấn đề Chuỗi thời gian là một tập hợp dữ liệu các trị số đo đƣợc dƣới dạng chuỗi các số thực theo từng khoảng thời gian cách đều nhau. Trong nghiên cứu dữ liệu chuỗi thời gian, ngƣời ta thƣờng quan tâm đến một đoạn gồm nhiều giá trị đƣợc đo liên tục chứ không quan tâm đến giá trị tại từng thời điểm cụ thể.

Do đó, chuỗi thời gian có thể đƣợc xem là dữ liệu nhiều chiều, với mỗi chiều là một giá trị quan sát đƣợc tại một thời điểm cụ thể. Số chiều có thể lên đến vài chục hoặc vài trăm tùy vào nguồn dữ liệu nhƣ giá trị chứng khoán, dữ liệu điện tim của bệnh nhân. Với nhiều nguồn dữ liệu lớn hiện nay, đặt ra thách thức lớn cho các nhà nghiên cứu trong việc trích xuất thông tin cho nguồn dữ liệu thô này, tùy vào từng lĩnh vực mà mục đích việc phân tích dữ liệu khác nhau: trong thống kê, kinh tế, tài chính, địa lý, khí tƣợng … dùng để dự báo; trong xử lý tính hiệu, kỹ thuật điều khiển và truyền thông dùng trong việc ƣớc lƣợng và phát hiện tín hiệu; trong khai phá dữ liệu, nhận dạng mẫu và học máy dùng cho phân loại (classifying), gom cụm (clustering), phát hiện bất thƣờng cũng nhƣ dự báo. Trong phạm vi đề tài này sẽ nghiên cứu vấn đề gom cụm dữ liệu chuỗi thời gian.

1 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK Gom cụm là quá trình gom nhóm dữ liệu/đối tƣợng vào các cụm, các đối tƣợng trong cùng một cụm tƣơng tự với nhau hơn so với đối tƣợng ở các cụm khác. Han and Kamber [1] phân loại các phƣơng pháp gom cụm dữ liệu đƣợc phát triển để xử lý các dữ liệu thông thƣờng khác nhau thành năm loại chính: - Phân hoạch (partitioning): các phân hoạch đƣợc tạo ra và đánh giá theo một tiêu chí nào đó. - Phân cấp (hierarchical): phân rã tập dữ liệu có thứ tự phân cấp theo một tiêu chí nào đó. - Dựa trên mật độ (density-based): dựa trên connectivity và density functions - Dựa trên lƣới (grid-based): dựa trên a multiple-level granularity structure - Dựa trên mô hình (model-based): một mô hình giả thuyết đƣợc đƣa ra cho mỗi cụm; sau đó hiệu chỉnh các thông số để mô hình phù hợp với cụm dữ liệu nhất.

Do dữ liệu chuỗi thời gian có đặc trƣng riêng so với dữ liệu thông thƣờng với ba đặc điểm chính: số chiều lớn, tính tƣơng quan giữa các bộ dữ liệu rất cao và dữ liệu nhiễu rất lớn. Do các đặc điểm riêng này làm cho nhiều giải thuật làm việc hữu hiệu trên dữ liệu thông thƣờng đã không làm việc tốt trên dữ liệu chuỗi thời gian. Các nhà nghiên cứu cố gắng áp dụng lại các thuật toán gom cụm của dữ liệu thông thƣờng cho phù hợp dữ liệu chuỗi thời gian, theo T. Liao gom cụm dữ liệu chuỗi thời gian có 3 hƣớng tiếp cận [1]: - Raw-data-based: chuỗi thời gian có thể xử lý trực tiếp áp dụng các giải thuật gom cụm của dữ liệu thông thƣờng, chủ yếu chỉnh sửa lại phần tính khoảng cách/độ tƣơng tự của các bộ dữ liệu chuỗi thời gian.

- Feature-based: chuyển dữ liệu chuỗi thời gian qua vector đặc trƣng có số chiều giảm sau đó áp dụng các giải gom cụm thông thƣờng cho các vector đặc trƣng trích xuất đƣợc. - Model-based: chuyển dữ liệu chuỗi thời gian qua các tham số mô hình, sau đó áp dụng các giải gom cụm thông thƣờng cho các tham số mô hình này. Đề tài này chủ yếu nghiên cứu dùng hai hƣớng tiếp cận raw-data-based với 2 hai loại gom cụm: phân hoạch (k-Means, Leader) và phân cấp (Single-link), Hình 1.1 thể hiện gom cụm dữ liệu. 2 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK Hình 1.1 Gom cụm dữ liệu 1.3 Động cơ và giới hạn đề tài Ngày nay dữ liệu chuỗi thời gian ngày càng phổ biến trong đời sống hàng ngày: chứng khoán, dữ liệu sức khỏe con ngƣời, thủy văn sông ngòi.

Nhƣng các giải thuật áp dụng cho dữ liệu chuỗi thời gian còn thiếu hơn nhiều so với dữ liệu thông thƣờng. Do đó nghiên cứu này sẽ vận dụng một giải thuật Leader Single-link đã áp dụng cho dữ liệu thông thƣờng vào dữ liệu chuỗi thời gian, qua đó so sánh đánh giá độ hiệu quả của giải thuật này với giải thuật khác đã thử nghiệm với dữ liệu chuỗi thời gian. Qua quá trình nghiên cứu và thực nghiệm, luận văn đã cải tiến phƣơng pháp giải thuật hiện tại cho phù hợp với dữ liệu chuỗi thời gian với kết quả tốt hơn. Trong khuôn khổ đề tài này, luận văn tập trung nghiên cứu gom cụm dữ liệu chuỗi thời gian bằng giải thuật gom cụm Leader Single-link (l-SL) do B.

Patra và cộng sự đƣa ra năm 2011 [2]. Giải thuật này có ƣu điểm so với giải thuật phân cấp Single-link (SL) truyền thống: dùng cho dữ liệu lớn, duyệt qua dữ liệu một lần, nó kết hợp hai giải thuật: đầu tiên dùng giải thuật gom cụm Leader để tìm ra các leader của cụm, tiếp theo là dùng giải thuật phân cấp Single-link để phân hoạch tập leader này. Giải thuật Leader Single-link đƣợc đề xuất là nhằm gom cụm dữ liệu thông thƣờng. Mục tiêu của đề tài này là nhằm áp dụng giải thuật Leader Single- link vào gom cụm dữ liệu chuỗi thời gian.

3 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK Tiếp đến là nghiên cứu và hiện thực giải thuật gom cụm I-kMeans do E. Keogh và công sự đƣa ra [3] mục tiêu giải thuật là khắc phục nhƣợc điểm của giải thuật k-Means: tăng chất lƣợng gom cụm và giảm thời gian thực thi giải thuật, cho phép ngƣời dùng kết thúc quá trình bất kỳ mức nào họ muốn. Từ hai giải thuật gom cụm này đƣa ra so sánh và đánh giá kết quả gom cụm của hai phƣơng pháp gom cụm dữ liệu chuỗi thời gian. Đề xuất giải thuật cải tiến I-Leader Single-link.4 Tóm lược kết quả đạt được của luận văn  Xây dựng chƣơng trình gom cụm dùng giải thuật Leader Single-link cho bài toán gom cụm dữ liệu chuỗi thời gian.

 Kết quả giải thuật cải tiến I-Leader Single-link có độ chính xác cao hơn hoặc tƣơng đƣơng nhƣng có thời gian thực thi thấp hơn giải thuật Leader Single-link, xác định đƣợc số leader tối ƣu cho giải thuật nhỏ hơn hoặc bằng (<=) k*2.  Thực nghiệm trên 9 bộ dữ liệu chuỗi thời gian đã phân lớp và chƣa phân lớp.5 Cấu trúc luận văn Cấu trúc luận văn phần còn lại chia thành các thành phần sau: CHƢƠNG 2: CƠ SỞ LÝ THUYẾT Chƣơng này trình bày nội dụng lý thuyết liên quan đến đề tài: giải thuật gom cụm: Single-link, k-Means, Leader, cũng nhƣ độ đo khoảng cách Euclid (Euclid distance) và phƣơng pháp phân rã Haar (Haar wavelet) cho dữ liệu chuỗi thời gian dùng trong đề tài. CHƢƠNG 3: NHỮNG CÔNG TRÌNH LIÊN QUAN Chƣơng này trình bày một số công trình nghiên cứu liên quan đến đề tài, đồng thời nêu ra các ƣu khuyết điểm của các công trình nghiên cứu này. CHƢƠNG 4: HỆ THỐNG GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN Chƣơng này sẽ trình bày vấn đề cũng nhƣ hƣớng giải quyết các vấn đề liên quan đề tài.

Đƣa ra thông tin cũng nhƣ cách hoạt động của hệ thống gom cụm dữ liệu chuỗi thời gian đƣợc xây dựng. 4 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK CHƢƠNG 5: THỰC NGHIỆM Chƣơng này sẽ đƣa ra các kết quả so sánh, đánh giá chất lƣợng, thời gian thực thi gom cụm của hệ thống đƣợc xây dựng cho việc gom cụm dữ liệu chuỗi thời gian. CHƢƠNG 6: KẾT LUẬN Chƣơng này sẽ tổng kết lại các kết quả đạt đƣợc, những đóng góp cũng nhƣ hƣớng phát triển của đề tài. 5 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK Chương 2 : CƠ SỞ LÝ THUYẾT Chƣơng này trình bày nội dụng lý thuyết liên quan đến đề tài: dữ liệu chuỗi thời gian, các giải thuật gom cụm phân cấp Single-link, gom cụm phân hoạch k- Means, gom cụm Leader và độ đo Euclid.1 Dữ liệu chuỗi thời gian Một 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.

Những tập dữ liệu chuỗi thời gian rất lớn xuất hiện trong nhiều lĩnh vực khác nhau nhƣ y khoa, kỹ thuật, kinh tế, tài chính, v.Tìm kiếm tƣơng tự (similarity search) là công tác căn bản nhất để khai thác những cơ sở dữ liệu chuỗi thời gian. Ví dụ: dữ liệu chuỗi thời gian X có chiều dài n là: xi = x1, x2, x3,.xn Trong đó: x1: dữ liệu tại thời điểm 1 x2: dữ liệu tại thời điểm 2 … xn: dữ liệu tại thời điểm n Hình 2.1 thể hiện lƣu lƣợng nƣớc đo tại các trạm gần tỉnh Luang Prabang (Lào) trên sông Mê Kông từ năm 2002 đến năm 2011: đƣờng màu xanh đậm tại trạm Luang Prabang 1, màu da trời tại trạm Luang Prabang 2, màu đỏ tại trạm Gauge 011201 Hình 2.1 Lƣu lƣợng nƣớc đo tại các trạm gần Luang Prabang (Lào) từ năm 2002- 2011 trên song Mê Kông 6 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP LEADER SINGLE-LINK 2.2 Độ đo khoảng cách Cho 2 chuỗi thời gian: X = x1,x2,x3,.yn Độ đo khoảng cách Euclid của hai chuỗi thời gian này đƣợc tính bởi công thức: ( ) √∑ ( ) (1) Trong đó: xi: dữ liệu của chuỗi X tại thời điểm i yi: dữ liệu của chuỗi Y tại thời điểm i Hình 2.2 cho ta ví dụ về biên độ của hai chuỗi thời gian áp dụng độ đo khoảng cách Euclid. Độ đo khoảng cách Euclid là độ đo đƣợc sử dụng phổ biến nhất trong khai phá dữ liệu chuỗi thời gian.2 Biên độ hai chuỗi thời gian áp dụng độ đo khoảng cách Euclid 2.3 Phương pháp gom cụm 2.