Gom Cụm Dữ Liệu Chuỗi Thời Gian Dựa Vào Xu Hướng: Nghiên Cứu Giải Thuật Squeezer

Luận văn thạc sĩ trình bày giải thuật squeezer gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng, ứng dụng trong khoa học máy tính.

• Tác giả: Huỳnh Trần Anh Vũ
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP.HCM
• 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 Xu Hướng Với Giải Thuật Squeezer
• 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. Giới Thiệu Tổng Quan về Gom Cụm Chuỗi Thời Gian

Kỷ nguyên số tạo ra lượng dữ liệu khổng lồ, phần lớn là chuỗi thời gian. Từ thông tin chứng khoán cập nhật liên tục đến biến động giá cả hàng hóa, nhu cầu phân tích chuỗi thời gian để hiểu và dự đoán xu hướng trở nên cấp thiết. Gom cụm chuỗi thời gian dựa vào xu hướng chuỗi thời gian là một hướng nghiên cứu tiềm năng, giúp doanh nghiệp nắm bắt thị trường. Tuy nhiên, việc gom cụm trực tiếp trên dữ liệu thô thường không hiệu quả. Luận văn này giới thiệu phương pháp chuyển đổi chuỗi thời gian thành chuỗi ký tự xu hướng, sau đó sử dụng giải thuật Squeezer để gom cụm chuỗi thời gian. Phương pháp này hứa hẹn kết quả gom cụm có ý nghĩa và thời gian thực thi chấp nhận được. "Với một khối lượng dữ liệu vô cùng lớn như vậy, nhu cầu đặt ra đối với con người là ‘học’ được gì từ đó."

1.1. Tầm Quan Trọng của Phân Tích Xu Hướng Chuỗi Thời Gian

Trong kinh tế thị trường, thông tin là sức mạnh. Khả năng dự báo xu hướng giá cả và chỉ số kinh tế giúp nhà đầu tư ra quyết định chính xác, tối đa hóa lợi nhuận và giảm thiểu rủi ro. Đánh giá xu hướng chuỗi thời gian là yếu tố then chốt trong dự báo, giúp nhà đầu tư kịp thời điều chỉnh chiến lược. Do đó, việc nghiên cứu và phát triển các phương pháp hiệu quả để gom cụm chuỗi thời gian dựa trên xu hướng là vô cùng quan trọng. Cần có công cụ hỗ trợ để phân loại xu hướng biến động của dữ liệu chuỗi thời gian.

1.2. Mục Tiêu và Phạm Vi Nghiên Cứu Đề Tài

Mục tiêu chính của luận văn là biến đổi dữ liệu chuỗi thời gian thành chuỗi ký tự thể hiện xu hướng chuỗi thời gian, sau đó áp dụng giải thuật Squeezer để gom cụm chuỗi thời gian. Nghiên cứu tập trung vào dữ liệu chứng khoán. Ưu điểm của giải thuật Squeezer là khả năng gom cụm chuỗi thời gian mà không cần biết trước số lượng cụm, khả năng gom nhóm dữ liệu chuỗi thời gian gia tăng và khả năng chống nhiễu tốt. Phạm vi nghiên cứu giới hạn ở các chuỗi thời gian có độ dài bằng nhau và chuỗi thời gian đơn biến.

II. Vấn Đề Với Gom Cụm Chuỗi Thời Gian Trực Tiếp

Gom cụm trực tiếp dữ liệu chuỗi thời gian thô thường không hiệu quả do dữ liệu có độ phức tạp cao và nhiễu. Việc so sánh trực tiếp các chuỗi thời gian dễ bị ảnh hưởng bởi các biến động nhỏ, không phản ánh đúng xu hướng chung. Biến đổi dữ liệu chuỗi thời gian thành dạng biểu diễn đơn giản hơn, như chuỗi ký tự xu hướng, giúp giảm độ phức tạp và tập trung vào xu hướng chính. Điều này tạo điều kiện thuận lợi cho giải thuật gom cụm hoạt động hiệu quả hơn, mang lại kết quả có ý nghĩa hơn. "Việc gom cụm dữ liệu trực tiếp trên tập dữ liệu ban đầu trên thường không đạt kết quả tốt."

2.1. Khó Khăn Trong Xử Lý Dữ Liệu Chuỗi Thời Gian Thô

Dữ liệu chuỗi thời gian thường có kích thước lớn và chứa nhiều nhiễu, gây khó khăn cho việc phân cụm chuỗi thời gian. Các phương pháp gom cụm chuỗi thời gian truyền thống gặp khó khăn trong việc xử lý dữ liệu có độ phức tạp cao. Do đó, cần có phương pháp tiền xử lý dữ liệu chuỗi thời gian để giảm nhiễu và đơn giản hóa dữ liệu.

2.2. Tại Sao Cần Biểu Diễn Xu Hướng Chuỗi Thời Gian

Biểu diễn chuỗi thời gian dưới dạng xu hướng chuỗi thời gian giúp tập trung vào đặc điểm quan trọng nhất của dữ liệu. Loại bỏ các chi tiết không cần thiết và làm nổi bật xu hướng chuỗi thời gian chung. Chuỗi ký tự xu hướng là một cách biểu diễn đơn giản, dễ xử lý và phù hợp với nhiều giải thuật gom cụm.

III. Giải Pháp Gom Cụm Chuỗi Thời Gian Dựa Trên Xu Hướng

Giải pháp đề xuất bao gồm ba bước chính: tiền xử lý dữ liệu chuỗi thời gian, chuyển đổi dữ liệu thành chuỗi ký tự xu hướng, và gom cụm chuỗi xu hướng bằng giải thuật Squeezer. Bước tiền xử lý dữ liệu chuỗi thời gian giúp loại bỏ nhiễu và chuẩn hóa dữ liệu. Việc chuyển đổi thành chuỗi ký tự xu hướng giúp đơn giản hóa dữ liệu và làm nổi bật xu hướng chính. Giải thuật Squeezer được chọn vì khả năng gom cụm chuỗi thời gian gia tăng, không cần biết trước số lượng cụm và khả năng chống nhiễu tốt. Kết quả thực nghiệm chứng minh tính hiệu quả của phương pháp này.

3.1. Các Bước Triển Khai Giải Pháp Gom Cụm

Giải pháp được chia thành ba bước chính: tiền xử lý dữ liệu, chuyển đổi dữ liệu thành chuỗi xu hướng, và gom cụm chuỗi xu hướng. Tiền xử lý dữ liệu giúp làm sạch và chuẩn hóa dữ liệu. Chuyển đổi dữ liệu thành chuỗi xu hướng giúp đơn giản hóa dữ liệu và làm nổi bật xu hướng chính. Gom cụm chuỗi xu hướng bằng giải thuật Squeezer giúp tìm ra các nhóm chuỗi thời gian có xu hướng chuỗi thời gian tương đồng.

3.2. Lựa Chọn Giải Thuật Squeezer để Gom Cụm

Giải thuật Squeezer được chọn vì khả năng gom cụm chuỗi thời gian gia tăng, không cần biết trước số lượng cụm và khả năng chống nhiễu tốt. Giải thuật Squeezer phù hợp với dữ liệu chuỗi thời gian có kích thước lớn và biến động liên tục. Giải thuật Squeezer có độ phức tạp thấp, phù hợp với ứng dụng thời gian thực.

3.3 Chuyển Đổi Dữ Liệu Thành Chuỗi Xu Hướng Bằng Trung Bình Trượt

Sử dụng trung bình trượt để làm mịn dữ liệu chuỗi thời gian và xác định xu hướng chuỗi thời gian. Trung bình trượt giản đơn (SMA), trung bình trượt hàm mũ (EMA), và trung bình trượt có trọng số (WMA) là các phương pháp phổ biến. Chọn phương pháp trung bình trượt phù hợp với đặc điểm của dữ liệu chuỗi thời gian. Chuyển đổi xu hướng chuỗi thời gian thành chuỗi ký tự giúp đơn giản hóa dữ liệu và dễ dàng so sánh.

IV. Ứng Dụng Thực Tế và Đánh Giá Gom Cụm Chuỗi Thời Gian

Phương pháp gom cụm chuỗi thời gian dựa vào xu hướng và giải thuật Squeezer được áp dụng vào dữ liệu chứng khoán Việt Nam và Mỹ. Kết quả thực nghiệm cho thấy phương pháp này có thể tìm ra các nhóm cổ phiếu có xu hướng tương đồng. So sánh kết quả với giải thuật K-Modes, cho thấy giải thuật Squeezer cho kết quả tốt hơn trong một số trường hợp. Đánh giá hiệu quả bằng các độ đo như Jaccard index, Rand index, và FM index.

4.1. Thực Nghiệm Trên Dữ Liệu Chứng Khoán Thực Tế

Áp dụng phương pháp gom cụm chuỗi thời gian dựa vào xu hướng và giải thuật Squeezer vào dữ liệu chứng khoán Việt Nam và Mỹ. Phân tích kết quả gom nhóm dữ liệu chuỗi thời gian để tìm ra các nhóm cổ phiếu có xu hướng tương đồng. So sánh kết quả với phân tích của chuyên gia tài chính.

4.2. So Sánh Với Các Phương Pháp Gom Cụm Chuỗi Thời Gian Khác

So sánh kết quả của giải thuật Squeezer với các phương pháp gom cụm chuỗi thời gian khác như K-means cho chuỗi thời gian hoặc K-Modes. Đánh giá ưu điểm và nhược điểm của từng phương pháp dựa trên các độ đo hiệu quả. Xác định điều kiện nào giải thuật Squeezer hoạt động tốt nhất.

4.3. Đánh Giá Chất Lượng Gom Cụm Bằng Các Độ Đo

Sử dụng các độ đo như Jaccard index, Rand index, và FM index để đánh giá chất lượng gom cụm. Phân tích ý nghĩa của các độ đo này trong việc đánh giá hiệu quả của giải thuật gom cụm. So sánh các độ đo này giữa các phương pháp gom cụm khác nhau.

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

Luận văn đã trình bày một phương pháp hiệu quả để gom cụm chuỗi thời gian dựa vào xu hướng sử dụng giải thuật Squeezer. Phương pháp này giúp giảm độ phức tạp của dữ liệu và tập trung vào xu hướng chính. Kết quả thực nghiệm cho thấy tính hiệu quả của phương pháp trong việc gom nhóm dữ liệu chuỗi thời gian chứng khoán. Hướng phát triển tiếp theo bao gồm cải tiến giải thuật Squeezer, mở rộng phạm vi nghiên cứu sang chuỗi thời gian đa biến, và áp dụng phương pháp vào các lĩnh vực khác.

5.1. Tổng Kết Những Kết Quả Đạt Được

Luận văn đã xây dựng một hệ thống gom cụm chuỗi thời gian khá hữu hiệu, có khả năng xử lý trên tập dữ liệu lớn với số điểm thời gian cả ngàn điểm. Qua việc thực nghiệm trên bốn tập dữ liệu mẫu cho thấy giải thuật Squeezer hoạt động tốt và có hiệu quả. Đã giải quyết được bài toán gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng sử dụng giải thuật Squeezer.

5.2. Các Hướng Nghiên Cứu Phát Triển Tiềm Năng

Nghiên cứu thêm về các phương pháp biểu diễn chuỗi thời gian khác như biểu diễn chuỗi thời gian theo hình dạng, hoặc sử dụng khoảng cách Dynamic Time Warping (DTW). Áp dụng phương pháp vào các lĩnh vực khác như y tế, năng lượng, và môi trường. Cải tiến giải thuật Squeezer để tăng tốc độ và độ chính xác.

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

CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI Giới thiệu sơ lược về đề tài, mục tiêu và phạm vi nghiên cứu cũng như cấu trúc của đề tài. CƠ SỞ LÝ THUYẾT Trình bày chi tiết về các vấn đề lý thuyết nền tảng trong lĩnh vực gom cụm dữ liệu nói chung, khái niệm dữ liệu chuỗi thời gian, một số giải thuật gom cụm dữ liệu chuỗi thời gian. NHỮNG CÔNG TRÌNH LIÊN QUAN Trình bày công trình có liên quan trực tiếp đề tài như việc gom cụm trên dữ liệu rời rạc: giải thuật k-Modes, giải thuật Squeezer; các nghiên cứu về trung bình trượt, cách biểu diễn xu hướng.

PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ Trình bày vấn đề nghiên cứu trong luận văn và phương pháp cụ thể giải quyết vấn đề được nêu ra trong luận văn CHƯƠNG 5. KẾT QUẢ THỰC NGHIỆM Trình bày các kết quả thực nghiệm so sánh hai giải thuật Squeezer và k- Modes qua một số bộ dữ liệu mẫu. KẾT LUẬN Huỳnh Trần Anh Vũ - 12070561 3 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Trình bày tổng quát các kết quả đạt được sau khi thực hiện đề tài, đồng thời nêu ra các hướng phát triển tiếp theo. Huỳnh Trần Anh Vũ - 12070561 4 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng CHƯƠNG 2.

CƠ SỞ LÝ THUYẾT Trong chương này, chúng tôi sẽ trình bày chi tiết về một số nội dung lý thuyết nền tảng trong lĩnh vực gom cụm dữ liệu. Sau đó, chúng tôi sẽ trình bày về khái niệm dữ liệu chuỗi thời gian đồng thời tìm hiểu một số giải thuật gom cụm dữ liệu chuỗi thời gian 2. CÁC GIẢI THUẬT GOM CỤM DỮ LIỆU NÓI CHUNG Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các lớp/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. Các giải thuật gom cụm được Han và Kamber [7] chia theo từng đặc trưng riêng biệt bao gồm: 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/đối tượng 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 and 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/đối tượng nhất.

Ở đây, chúng tôi chỉ đề cập đến các giải thuật gom cụm phổ biến là gom cụm phân hoạch và phân cấp. Giải thuật gom cụm phân hoạch Giải thuật gom cụm phân hoạch được sử dụng rất phổ biến vì nó đơn giản và là giải thuật gom cụm cơ bản nhất trong các phương pháp gom cụm. Giải thuật này Huỳnh Trần Anh Vũ - 12070561 5 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng yêu cầu trước tiên phải biết dữ liệu nhập ban đầu k (số cụm). Những cụm được hình thành thỏa điều kiện tối ưu hóa các tiêu chuẩn phân hoạch mục tiêu như độ đo tương tự dựa vào khoảng cách.

Hai phương pháp kinh điển đại diện cho nhóm giải thuật dạng phân hoạch này là k-Means và k-Medoids. Giải thuật k-Means Thuật toán k-Means lấy tham số đầu vào là k và phân chia một tập n đối tượng vào trong k cụm để cho kết quả độ tương đồng trong cụm là cao trong khi độ tương đồng ngoài cụm là thấp. Độ tương đồng cụm được đo khi đánh giá giá trị trung bình của các đối tượng trong cụm, nó có thể được quan sát như là “trọng tâm” của cụm. Giải thuật xử lý như sau: trước tiên nó lựa chọn ngẫu nhiên k đối tượng, mỗi đối tượng đại diện cho một trung bình cụm hay trung tâm cụm (center cluster).

Đối với những đối tượng còn lại, mỗi đối tượng sẽ được ấn định vào một cụm mà nó giống nhất dựa trên khoảng cách giữa đối tượng và trung bình cụm. Sau đó sẽ tính lại trung bình cụm mới cho mỗi cụm. Xử lý này sẽ được lặp lại cho tới khi hàm tiêu chuẩn hội tụ. Bình phương sai số thường dùng làm hàm tiêu chuẩn hội tụ, định nghĩa như sau : với E là tổng bình phương sai số của tất cả các đối tượng trong dữ liệu, p là điểm trong không gian đại diện cho đối tượng cho trước; m i là trung tâm của cụm C i (cả p và m i đều đa chiều).

Thuật toán k-Means gồm các bước sau: Đầu vào: số cụm k, tập dữ liệu n đối tượng Đầu ra: tập các k cụm Huỳnh Trần Anh Vũ - 12070561 6 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Begin 1. Chọn k đối tượng ngẫu nhiên trong tập dữ liệu cho trước 2. Đưa đối tượng nào tương tự nhất vào cụm tương ứng (dựa vào giá trị trung bình của các đối tượng trong cụm) 4. Tính lại giá trị trung tâm cho từng cụm.

Until: không có gì thay đổi End Hình 2.1 mô tả quá trình gom cụm sử dụng giải thuật k-Means Hình 2.1 Quá trình gom cụm k-Means:trung tâm cụm biểu diễn bằng dấu “+” (nguồn [7]) Ưu điểm: giải thuật có độ phức tạp nhỏ: O(n*t*k), trong đó n là số đối tượng, k là số cụm cần gom và t là số lần lặp, do đó thích hợp cho các dữ liệu có số đối tượng lớn. Khuyết điểm: phải xác định số cụm k trước, việc xác định giá trị trung bình trở nên phức tạp trong một số trường hợp, không phải dữ liệu nào cũng có thể tính được giá trị trung bình một các dễ dàng. Giải thuật bị ảnh hưởng khá lớn bởi nhiễu và cực trị cục bộ. Giải thuật k-Medoids Giải thuật k-Means rất nhạy với các phần tử nhiễu, do vậy một đối tượng giá trị cực lớn về cơ bản sẽ làm thay đổi tâm cụm và có thể bóp méo phân bổ của dữ liệu.

Huỳnh Trần Anh Vũ - 12070561 7 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Ý tưởng của k-Medoids thay vì lấy giá trị trung bình của các đối tượng trong cụm như một điểm tham khảo, k-medoids lấy một đối tượng đại diện trong cụm, gọi là medoid, nó là điểm đại diện được định vị trung tâm nhất trong cụm. Giải thuật PAM (Partition Around Medoids), đây là giải thuật tiêu biểu trong gom cụm kiểu k-Medoids. Nó tìm k cụm trong n đối tượng bằng cách trước tiên tìm một số đối tượng đại diện (medoid) cho mỗi cụm. Tập các medoid ban đầu được lựa chọn tuỳ ý.

Các đối tượng còn lại được gán vào cụm mà khoảng cách từ chúng tới đối tượng medoid là nhỏ nhất. Sau đó sự phân hoạch được thực hiện bằng cách tối thiểu hóa khoảng cách của đối tượng p với medoid tương ứng bằng công thức: Huỳnh Trần Anh Vũ - 12070561 8 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Hình 2.2 Các trường hợp thay thế của giải thuật K-medoids (nguồn [7]) Begin 1. Chọn tuỳ ý k đối tượng giữ vai trò là các medoid ban đầu; 2. Ấn định mỗi đối tượng vào cụm có medoid gần nó nhất; 4.

chọn ngẫu nhiên một đối tượng không là phần tử đại diện 5. Tính hàm chi phí; 6. Đổi medoid x bằng một đối tượng y nếu như việc thay đổi này làm giảm hàm chi phí; 7. Until : không có sự thay đổi nào End Khi có sự hiện diện của nhiễu và các phần tử nhiễu, phương pháp k-Medoids mạnh hơn k-Means bởi so với giá trị trung bình (mean), medoid ít bị ảnh hưởng hơn bởi các phần tử nhiễu hay các giá trị ở rất xa khác nữa, vì mỗi cụm được đại diện bởi phần tử chính giữa.

Huỳnh Trần Anh Vũ - 12070561 9 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Để khắc phục điểm yếu về độ phức tạp, năm 1990, Kaufman va Rousseeuw đã đưa ra một kỹ thuật được phát triển dựa trên việc lấy mẫu gọi là CLARA (Clustering large applications), Ý tưởng của CLARA như sau : thay vì lấy toàn bộdữ liệu vào xem xét, chỉ một phần nhỏ dữ liệu được chọn với vai trò là một đại diện của dữ liệu, và các medoid được chọn từ mẫu này bằng cách sử dụng PAM. Nếu như mẫu được chọn lựa khá ngẫu nhiên, nó đại diện phù hợp cho toàn bộ tập dữ liệu và các đối tượng đại diện (các medoid) được chọn do vậy sẽ giống với những cái được chọn lựa từ toàn bộ tập dữ liệu. CLARA đưa ra nhiều mẫu của tập dữ liệu, áp dụng PAM trên từng mẫu và mang lại phân cụm tốt cho đầu ra. Đúng như trông chờ, CLARA có thể giải quyết với các tập dữ liệu lớn hơn PAM.

Độ phức tạp của mỗi lần lặp bây giờ trở thành O(kS2+k(n –k)) với S là kích thước mẫu, k là số cụm, n là tổng số các phần tử. Giải thuật gom cụm phân cấp Mục đích của giải thuật này là nhóm các đối tượng lại với nhau theo từng mức khác nhau vào một cây phân cấp của các cụm. Hai chiến lược gom cụm phân cấp phổ biến đó là tổng hợp và phân tách, tức là tổ chức các đối tượng theo kiểu từ dưới lên hay từ trên xuống, đại diện cho hai chiến lược này là hai giải thuật AGNES - Agglomerative NESting (tổng hợp) và DIANA - Divisive ANAlysis (phân tách). Xem minh họa tại hình 2.

Giải thuật AGNES khởi đầu mỗi đối tượng khởi tạo một cụm riêng biệt, sau đó mỗi cụm được trộn lại theo một tiêu chí nào đó chẳng hạn như liên kết đơn (single-linkage) tức là hai cụm được trộn lại nếu khoảng cách giữa hai đối tượng từ hai cụm đó là ngắn nhất hay liên kết đầy đủ (complete-linkage) nghĩa là trộn hai cụm nếu khoảng cách từ hai đối tượng xa nhất trong hai cụm so với khoảng cách xa nhất của điểm trong cụm đó với điểm của các cụm khác là ngắn nhất. Quá trình được lặp đi lặp lại cho đến khi tất cả các đối tượng tạo thành một cụm duy nhất.4 mô minh họa liên kết đơn và liên kết đầy đủ. Huỳnh Trần Anh Vũ - 12070561 10 Gom cụm dữ liệu chuỗi thời gian dựa vào xu hướng Hình 2.3 Minh họa hai chiến lược gom cụm phân cấp (nguồn [7]) Giải thuật DIANA thì ngược lại với giải thuật AGNES, khởi đầu mọi đối tượng tạo thành một cụm duy nhất. Sau đó, các cụm được phân ra theo một tiêu chí nào đó đến mỗi cụm chỉ còn một đối tượng như khoảng cách lớn nhất giữa các đối tượng gần nhau nhất.

Kết quả gom cụm của giải thuật gom cụm phân cấp sinh ra một cây cấu trúc gọi là dendrogram. Cấu trúc này sẽ cho thấy quá trình trộn hay tách của giải thuật từng bước một.