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.
