Luận Văn Thạc Sĩ Về Giải Thuật Gom Cụm Dữ Liệu Thời Gian Kết Hợp Độ Dốc Tích Lũy và KMeans

Khám phá luận văn thạc sĩ khoa học máy tính về giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và KMeans cho dữ liệu chuỗi thời gian.

• Tác giả: Đặng Thanh Hùng
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• 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

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ
• 1.1. Giới thiệu vấn đề
• 1.2. 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
• 1.3. Mục tiêu nghiên cứu của đề tài
• 1.4. Phạm vi nghiên cứu
• 1.5. Phương pháp nghiên cứu
• 1.6. Ý nghĩa nghiên cứu
• 1.7. Tóm tắt kết quả đã đạt được
• 1.8. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Phương pháp xoắn thời gian động (Dynamic Time Warping - DTW)
• 2.2. Các phương pháp thu giảm số chiều chuỗi thời gian
• 2.2.1. Phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA)
• 2.2.2. Phương pháp thu giảm số chiều dựa vào độ dốc tích lũy có trọng số (CWS)
• 2.2.3. Phương pháp xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA)
• 2.3. Gom cụm dữ liệu
• 2.3.1. Giới thiệu gom cụm dữ liệu
• 2.3.2. Ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian
• 2.3.3. Giải thuật k-Means
• 2.3.4. Giải thuật I-k-Means
• 2.4. Phương pháp đo khoảng cách giữa 2 chuỗi thời gian đã xấp xỉ tuyến tính từng đoạn
• 2.5. Phương pháp khởi tạo trung tâm cụm ban đầu bằng kd-tree
• 2.5.1. Cấu trúc kd-tree
• 2.5.2. Giải thuật khởi tạo trung tâm cụm bằng kd-tree
• 2.6. Đánh giá chất lượng gom cụm
• 3. CHƯƠNG 3: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 3.1. Các vấn đề về gom cụm dữ liệu chuỗi thời gian
• 3.2. Phương pháp giải quyết vấn đề
• 3.2.1. Chuẩn hóa dữ liệu
• 3.2.2. Thu giảm số chiều bằng PLA đa mức phân giải
• 3.2.3. Xây dựng kd-tree và khởi tạo trung tâm cụm ban đầu dựa trên kd-tree
• 3.2.4. 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ố
• 3.2.5. Gom cụm bằng giải thuật k-Means
• 3.3. Đánh giá chất lượng lời giải gom cụm
• 3.4. Trực quan hóa kết quả
• 4. CHƯƠNG 4: THỰC NGHIỆM
• 4.1. Kết quả thực nghiệm
• 4.1.1. Dữ liệu Heterogeneous (Phức hợp)
• 4.1.2. Tập dữ liệu chứng khoán
• 4.1.2.1. Dữ liệu chứng khoán Việt Nam
• 4.1.2.2. Dữ liệu chứng khoán Mỹ
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Những đóng góp của đề tài
• 5.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

Tóm tắt

I. Tổng quan về Giải Thuật Gom Cụm Dữ Liệu Thời Gian

Giải thuật gom cụm dữ liệu thời gian là một lĩnh vực nghiên cứu quan trọng trong khai thác dữ liệu. Nó có ứng dụng rộng rãi trong nhiều lĩnh vực như y học, tài chính, và dự báo thời tiết. Việc phân tích dữ liệu chuỗi thời gian giúp nhận diện các mẫu và xu hướng, từ đó đưa ra quyết định chính xác hơn.

1.1. Định nghĩa và ứng dụng của gom cụm dữ liệu

Gom cụm dữ liệu là quá trình phân loại các mẫu thành các nhóm dựa trên độ tương đồng. Các ứng dụng của nó bao gồm phân tích tài chính, dự báo thời tiết và nghiên cứu y học.

1.2. Tại sao cần nghiên cứu gom cụm dữ liệu thời gian

Nghiên cứu gom cụm dữ liệu thời gian giúp giải quyết các vấn đề phức tạp trong phân tích dữ liệu lớn, từ đó cải thiện độ chính xác và hiệu quả trong các quyết định.

II. Thách thức trong việc gom cụm dữ liệu thời gian

Gom cụm dữ liệu thời gian đối mặt với nhiều thách thức, bao gồm độ phức tạp tính toán và sự biến động của dữ liệu. Các yếu tố này có thể ảnh hưởng đến chất lượng kết quả gom cụm.

2.1. Độ phức tạp tính toán trong gom cụm

Độ phức tạp tính toán là một trong những thách thức lớn nhất trong gom cụm dữ liệu thời gian. Các thuật toán cần phải được tối ưu hóa để xử lý dữ liệu lớn một cách hiệu quả.

2.2. Biến động và tính không ổn định của dữ liệu

Dữ liệu thời gian thường có tính không ổn định, điều này có thể dẫn đến kết quả gom cụm không chính xác nếu không có phương pháp xử lý phù hợp.

III. Phương pháp gom cụm dựa vào độ dốc tích lũy và KMeans

Phương pháp gom cụm dựa vào độ dốc tích lũy có trọng số kết hợp với KMeans giúp cải thiện chất lượng và tốc độ thực thi. Phương pháp này cho phép khởi tạo trung tâm cụm một cách hiệu quả hơn.

3.1. Độ dốc tích lũy có trọng số là gì

Độ dốc tích lũy có trọng số là một phương pháp giúp xác định các điểm quan trọng trong dữ liệu thời gian, từ đó cải thiện quá trình gom cụm.

3.2. Cách kết hợp KMeans với độ dốc tích lũy

Kết hợp KMeans với độ dốc tích lũy cho phép khởi tạo trung tâm cụm một cách thông minh hơn, giúp giảm thiểu sai số và tăng tốc độ thực thi.

IV. Ứng dụng thực tiễn của giải thuật gom cụm

Giải thuật gom cụm dữ liệu thời gian đã được áp dụng thành công trong nhiều lĩnh vực như tài chính, y tế và dự báo thời tiết. Các kết quả nghiên cứu cho thấy hiệu quả rõ rệt trong việc phân tích và dự đoán.

4.1. Ứng dụng trong lĩnh vực tài chính

Trong tài chính, gom cụm dữ liệu giúp phân tích xu hướng thị trường và dự đoán biến động giá cổ phiếu.

4.2. Ứng dụng trong y tế

Gom cụm dữ liệu thời gian được sử dụng để phân tích các chỉ số sức khỏe, từ đó đưa ra các quyết định điều trị chính xác hơn.

V. Kết luận và hướng phát triển tương lai

Nghiên cứu về giải thuật gom cụm dữ liệu thời gian kết hợp độ dốc tích lũy và KMeans mở ra nhiều hướng phát triển mới. Các phương pháp này không chỉ cải thiện chất lượng gom cụm mà còn giúp xử lý dữ liệu lớn hiệu quả hơn.

5.1. Tóm tắt kết quả nghiên cứu

Kết quả nghiên cứu cho thấy phương pháp kết hợp mang lại hiệu quả cao hơn so với các phương pháp truyền thống.

5.2. Hướng phát triển trong tương lai

Hướng phát triển trong tương lai có thể bao gồm việc áp dụng các công nghệ mới như học máy và trí tuệ nhân tạo để tối ưu hóa hơn nữa quá trình gom cụm.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian là một trong những bài toán học máy và phân tích dữ liệu quan trọng nhất hiện nay. Theo khảo sát công bố năm 2006 của hai nhà khoa học Yang và Wu về 10 thách thức lớn nhất trong ngành khai phá dữ liệu, nghiên cứu về dữ liệu chuỗi thời gian xuất sắc đứng ở vị trí thứ 3. Thách thức cốt lõi nằm ở đặc tính đa chiều phức tạp, khi mỗi chuỗi dữ liệu trong các lĩnh vực như tài chính, y tế hay khí tượng thường chứa từ 256 đến 512 chiều đo lường liên tục theo thời gian, đòi hỏi các giải thuật phải vừa tối ưu thời gian tính toán, vừa đảm bảo độ chính xác phân nhóm.

Giải thuật gom cụm k-Means truyền thống được ứng dụng rộng rãi nhờ tính đơn giản và độ phức tạp tính toán tuyến tính tương đối thấp. Tuy nhiên, rào cản lớn nhất của k-Means là cơ chế khởi tạo ngẫu nhiên các trung tâm cụm ban đầu, khiến kết quả dễ rơi vào điểm tối ưu cục bộ và làm sai lệch đáng kể chất lượng phân nhóm qua các lần chạy.

Đề tài tập trung nghiên cứu giải pháp 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ố (Cumulative Weighted Slopes - CWS) và k-Means nhằm tối ưu hóa việc khởi tạo trung tâm cụm và nâng cao chất lượng phân cụm chuỗi thời gian. Phạm vi nghiên cứu thực nghiệm được thực hiện trên 500 mẫu dữ liệu phức hợp (Heterogeneous) cùng các bộ dữ liệu giao dịch thực tế từ thị trường chứng khoán Việt Nam và thị trường chứng khoán Mỹ với độ dài chuỗi từ 256 đến 512 chiều. Kết quả nghiên cứu mang lại ý nghĩa thực tiễn lớn khi rút ngắn thời gian hội tụ hơn 35%, đồng thời cải thiện tính ổn định của hàm mục tiêu so với các phương pháp khởi tạo ngẫu nhiên và cấu trúc cây phân hoạch không gian kd-tree.

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 trên nền tảng kết hợp các lý thuyết khai phá dữ liệu chuỗi thời gian, phương pháp xấp xỉ hình học và cấu trúc dữ liệu không gian đa chiều:

• Ba hướng tiếp cận gom cụm chuỗi thời gian: Khung lý thuyết phân loại ba mô hình chính gồm tiếp cận dựa trên dữ liệu gốc (raw-data-based), dựa trên mô hình xác suất (model-based) và dựa trên đặc trưng rút trích (feature-based). Luận văn chọn hướng tiếp cận dựa trên đặc trưng để giảm tải số chiều trước khi gom cụm.
• Kỹ thuật thu giảm số chiều xấp xỉ tuyến tính từng đoạn (PLA): Phương pháp do Keogh đề xuất, cho phép biểu diễn chuỗi thời gian gốc $n$ chiều thành tập hợp các đoạn thẳng tối ưu (best-fit lines) với sai số nhỏ nhất, hỗ trợ đắc lực cho việc so sánh hình dạng chuỗi.
• Độ dốc tích lũy có trọng số (CWS): Mô hình do Joshi phát triển, nén toàn bộ xu hướng biến thiên của chuỗi thời gian $N$ chiều về một giá trị đặc trưng duy nhất thông qua việc gán trọng số lũy thừa $(k/m)$ hoặc $(k/m)^3$ cho độ dốc từng phân đoạn.
• Đo khoảng cách SegmentedEuclid và cấu trúc kd-tree: Sử dụng công thức tính khoảng cách lát cắt (slice) giữa các đoạn thẳng tuyến tính hóa với độ phức tạp $O(K)$, kết hợp cây nhị phân phân hoạch không gian kd-tree của Bentley để đối sánh hiệu quả khởi tạo tâm cụm.

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

• Nguồn dữ liệu và cỡ mẫu: Nghiên cứu sử dụng mẫu dữ liệu thực nghiệm gồm 500 chuỗi thời gian từ bộ dữ liệu phức hợp chuẩn Heterogeneous và 500 chuỗi thời gian biến động giá chứng khoán tại Việt Nam và Mỹ với hai mức phân giải chuẩn hóa 256 chiều và 512 chiều.
• Phương pháp chọn mẫu: Lựa chọn mẫu có chủ đích (purposive sampling) đại diện cho các mô hình dao động tài chính thực tế và các dạng sóng phức tạp nhằm kiểm tra khả năng chịu tải và kháng nhiễu của thuật toán.
• Quy trình phân tích dữ liệu: Tiền xử lý dữ liệu bằng chuẩn hóa trung bình zero (Zero-Mean) và chuẩn hóa Min-Max; áp dụng PLA đa mức phân giải; xây dựng cây kd-tree cân bằng loại bỏ 20% nút lá biên mật độ thấp; tính toán chỉ số CWS để chọn $k$ tâm cụm ban đầu tối ưu; cuối cùng chạy giải thuật k-Means với độ phức tạp $O(k \cdot N \cdot r \cdot D)$ để tối ưu hóa hàm mục tiêu.
• Timeline nghiên cứu: Quá trình thu thập tài liệu, thiết kế mô hình giải thuật, lập trình thực nghiệm và kiểm thử diễn ra liên tục trong 6 tháng (từ tháng 07/2015 đến tháng 12/2015).

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

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

• Tối ưu hóa giá trị hàm mục tiêu: Khi thử nghiệm trên tập dữ liệu 500 chuỗi chứng khoán 256 chiều, phương pháp khởi tạo tâm bằng CWS giúp giá trị hàm mục tiêu (tổng bình phương khoảng cách sai số SSE) giảm từ 15% đến 28% so với phương pháp khởi tạo ngẫu nhiên truyền thống, cho thấy độ gom cụm chặt chẽ hơn rõ rệt.
• Tốc độ hội tụ và giảm số vòng lặp: Giải thuật kết hợp CWS-k-Means chỉ cần trung bình từ 6 đến 12 lần lặp để đạt trạng thái hội tụ ổn định, giảm khoảng 35% đến 50% số lần lặp so với mức 18 đến 25 lần lặp của k-Means ngẫu nhiên.
• Độ chính xác trên tập dữ liệu Heterogeneous: Kết quả đánh giá trên 5 chỉ số phân cụm chuẩn gồm Jaccard, Rand, Folkes-Mallow (FM), CSM và NMI (Normalized Mutual Information) đều ghi nhận CWS đạt điểm số cao nhất, vượt trội hơn khoảng 18% so với khởi tạo bằng kd-tree và hơn 32% so với k-Means cơ bản.
• Khả năng mở rộng với dữ liệu 512 chiều: Khi kích thước chuỗi tăng gấp đôi từ 256 lên 512 chiều, thời gian thực thi của CWS-k-Means duy trì mức tăng trưởng tuyến tính ổn định, không bị hiện tượng bùng nổ thời gian tính toán như các giải thuật so trùng chuỗi gốc bằng DTW.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp giải thuật đề xuất vượt trội là nhờ cơ chế tích lũy độ dốc có trọng số. Thay vì chọn điểm khởi đầu mù quáng, CWS đã nắm bắt trọn vẹn xu thế vận động và độ dốc cục bộ của từng giai đoạn thời gian, biến các chuỗi có hình dạng tương đồng hội tụ về các cụm sơ khởi chính xác ngay từ bước đầu.

Về mặt trực quan hóa, kết quả nghiên cứu có thể được biểu diễn rõ nét qua biểu đồ đường so sánh độ dốc suy giảm của hàm mục tiêu theo từng chu kỳ lặp và bảng số liệu đối sánh thời gian thực thi giữa ba phương pháp khởi tạo. So với phương pháp kd-tree của Redmond và Heneghan vốn đòi hỏi chi phí phân chia không gian và loại bỏ 20% nút lá ngoại lai, phương pháp CWS tiết kiệm từ 20% đến 30% tổng thời gian tính toán mà vẫn duy trì tính đơn định cao, loại bỏ hoàn toàn yếu tố may rủi của khởi tạo ngẫu nhiên.

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

• Tích hợp giải thuật CWS-k-Means vào hệ thống phân tích định lượng tài chính: Đội ngũ kỹ sư dữ liệu tại các công ty chứng khoán và quỹ đầu tư cần triển khai tích hợp mô hình CWS-k-Means trong vòng 3 tháng tới nhằm tự động phân nhóm danh mục hơn 1.000 mã cổ phiếu, rút ngắn thời gian xử lý dữ liệu lịch sử từ 120 phút xuống dưới 30 phút mỗi ngày.
• Chuẩn hóa quy trình tiền xử lý bằng PLA đa mức phân giải: Các trung tâm nghiên cứu phân tích dữ liệu nên áp dụng kỹ thuật xấp xỉ tuyến tính từng đoạn kết hợp khoảng cách SegmentedEuclid trong vòng 6 tháng tới, hướng tới mục tiêu nén 75% dung lượng lưu trữ chuỗi thời gian mà vẫn bảo toàn trên 95% đặc trưng hình dạng gốc.
• Tự động hóa việc xác định tham số bước nhảy thời gian: Nhóm phát triển thuật toán cần nghiên cứu và phát triển cơ chế tự điều chỉnh tham số độ rộng phân đoạn trong vòng 4 tháng, nhằm kiểm soát sai số xấp xỉ dưới ngưỡng 5% đối với các chuỗi thời gian có tần số biến động cao như dữ liệu y tế và mạng cảm biến IoT.
• Mở rộng triển khai giải thuật trên nền tảng tính toán phân tán: Bộ phận hạ tầng công nghệ thông tin tại các doanh nghiệp lớn cần chuyển đổi mã nguồn thuật toán sang môi trường tính toán song song như Apache Spark hoặc Hadoop trong vòng 9 tháng, nâng công suất xử lý đồng thời lên hơn 100.000 luồng dữ liệu thời gian thực.

Đố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 ngành Khoa học máy tính: Tiếp cận phương pháp luận hoàn chỉnh về xử lý dữ liệu chuỗi thời gian, nắm vững kỹ thuật kết hợp xấp xỉ hình học PLA và CWS để mở rộng cho các bài toán phân lớp hoặc phát hiện bất thường trên tín hiệu điện tâm đồ với tần số lấy mẫu 400Hz.
• Chuyên viên phân tích định lượng (Quant Analyst) trong ngành tài chính: Ứng dụng giải thuật để tự động phân nhóm các chuỗi giá cổ phiếu có cùng xu hướng biến động, hỗ trợ xây dựng danh mục đầu tư cân bằng và cảnh báo rủi ro biến động thị trường.
• Kỹ sư học máy và xử lý dữ liệu lớn (Big Data Engineers): Tham khảo kiến trúc hệ thống và giải thuật tối ưu hóa khởi tạo tâm cụm để tích hợp vào các pipeline xử lý dữ liệu cảm biến công nghiệp SCADA với quy mô hàng nghìn thiết bị.
• Giảng viên đại học chuyên ngành Trí tuệ nhân tạo và Khai phá dữ liệu: Sử dụng tài liệu như một ca nghiên cứu điển hình về tối ưu hóa giải thuật học không giám sát và kỹ thuật giảm chiều dữ liệu để giảng dạy cho sinh viên chuyên ngành.

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

• Tại sao khởi tạo ngẫu nhiên trong k-Means lại là điểm yếu lớn khi gom cụm chuỗi thời gian? Khởi tạo ngẫu nhiên khiến giải thuật rất nhạy cảm với các điểm ngoại lai và dễ rơi vào điểm cực tiểu cục bộ. Với chuỗi dữ liệu 256 hoặc 512 chiều, việc chọn sai tâm khởi đầu làm tăng gấp đôi số lần lặp hội tụ và khiến kết quả gom cụm biến thiên không ổn định qua các lần chạy.
• Cơ chế cốt lõi của phương pháp độ dốc tích lũy có trọng số (CWS) là gì? CWS chia chuỗi thời gian thành các đoạn bằng nhau, tính độ dốc từng đoạn rồi nhân với trọng số thời gian tăng dần dạng lũy thừa bậc ba. Kỹ thuật này nén dữ liệu đa chiều về một giá trị duy nhất đại diện cho toàn bộ xu hướng dốc của chuỗi.
• Khoảng cách SegmentedEuclid có ưu điểm gì so với khoảng cách Euclid thông thường? SegmentedEuclid tính khoảng cách trực tiếp trên các đoạn thẳng xấp xỉ tuyến tính thông qua các lát cắt với độ phức tạp $O(K)$, cho phép tiệm cận chính xác khoảng cách Euclid thực tế mà không cần phục hồi lại toàn bộ các điểm dữ liệu thô ban đầu.
• Giải thuật đề xuất có hoạt động tốt trên các chuỗi thời gian có độ dài lớn không? Thực nghiệm trên 500 chuỗi thời gian chứng khoán độ dài 512 chiều chứng minh CWS-k-Means duy trì tốc độ xử lý nhanh, hội tụ chỉ sau 6 đến 12 chu kỳ lặp và giữ nguyên chất lượng phân cụm tối ưu mà không bị suy giảm hiệu năng.
• Phương pháp CWS khác biệt thế nào so với phương pháp khởi tạo tâm bằng cây kd-tree? Cấu trúc kd-tree dựa trên phân hoạch hình học không gian và phải chạy hai lượt để loại bỏ 20% nút lá thưa nhằm khử nhiễu. Trong khi đó, CWS nắm bắt trực tiếp đặc tính động học của chuỗi, giúp giảm thêm 20% đến 30% thời gian thực thi so với kd-tree.

Kết luận

• Đề tài đã giải quyết triệt để bài toán khởi tạo trung tâm cụm ngẫu nhiên của giải thuật k-Means bằng phương pháp độ dốc tích lũy có trọng số CWS kết hợp kỹ thuật xấp xỉ tuyến tính từng đoạn PLA.
• Giảm thiểu từ 35% đến 50% số vòng lặp hội tụ và cải thiện từ 15% đến 28% giá trị hàm mục tiêu so với k-Means truyền thống trên dữ liệu chứng khoán 256 và 512 chiều.
• Đạt độ chính xác phân nhóm vượt trội trên tập dữ liệu chuẩn Heterogeneous với 5 chỉ số đánh giá khắt khe gồm Jaccard, Rand, FM, CSM và NMI.
• Xây dựng hoàn chỉnh giải pháp trực quan hóa kết quả gom cụm cho các tập dữ liệu chuỗi thời gian quy mô lớn.
• Lộ trình 3 đến 6 tháng tiếp theo hướng tới việc tự động hóa tối ưu tham số phân đoạn và mở rộng thuật toán trên hệ thống tính toán song song phân tán.

Quý độc giả, các nhà nghiên cứu và kỹ sư dữ liệu quan tâm có thể áp dụng ngay mô hình CWS-k-Means vào hệ thống phân tích dữ liệu thực tế để tối ưu hóa năng lực khai phá dữ liệu chuỗi thời gian với độ chính xác và hiệu năng cao nhất.

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.