Luận văn thạc sĩ về gom cụm chuỗi thời gian trong khoa học máy tính theo xu hướng

Chuyên đề gom cụm chuỗi thời gian trong khoa học máy tính theo xu hướng, tiếp cận liên ngành, kết quả nghiên cứu có giá trị ứng dụng cao trong khoa

• Tác giả: Thiều Xuân Khánh
• Người hướng dẫn: PGS TS. 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 Chuỗi Thời Gian Dựa Theo Xu Hướng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• TÓM TẮT LUẬN VĂN
• DANH MỤC CÁC HÌNH
• 1. CHƯƠNG I: PHÁT BIỂU VẤN ĐỀ
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Bài toán gom cụm dữ liệu chuỗi thời gian
• 1.3. Mục tiêu và giới hạn của đề tài
• 1.4. Tóm lược những kết quả đạt được
• 1.5. Cấu trúc của luận văn
• 2. CHƯƠNG II: TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Độ đo xoắn thời gian động
• 2.2. Các phương pháp thu giảm số chiều
• 2.2.1. Phương pháp không thích nghi dữ liệu
• 2.2.2. Phương pháp thích nghi dữ liệu
• 2.3. Rời rạc hóa dữ liệu bằng phương pháp xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate approXimation - SAX)
• 2.4. Gom cụm dữ liệu thường
• 2.4.1. Gom cụm phân hoạch
• 2.4.1.1. Giải thuật k-means
• 2.4.2. Gom cụm phân cấp
• 2.4.2.1. Gom cụm phân cấp thu gộp (Agglomerative hierarchical clustering)
• 2.4.2.2. Gom cụm phân cấp chia nhỏ (Divisive hierarchical clustering)
• 2.4.3. Các phương pháp gom cụm khác
• 2.4.3.1. Phương pháp gom cụm dựa trên mật độ (Density method)
• 2.4.3.2. Phương pháp gom cụm dựa trên lưới (Grid-based method)
• 2.4.3.3. Phương pháp gom cụm dựa trên mô hình (Model-based method)
• 2.5. Gom cụm dữ liệu chuỗi thời gian
• 2.5.1. Gom cụm dựa trên dữ liệu thô
• 2.5.2. Gom cụm dựa trên đặc trưng
• 2.5.2.1. Gom cụm dữ liệu chuỗi thời gian chứng khoán
• 2.5.2.2. Giải thuật I-k-Means
• 2.5.2.3. Rút trích đặc trưng không giám sát cho gom cụm chuỗi thời gian bằng cách sử dụng Biến đổi Wavelet
• 2.5.3. Gom cụm dựa trên mô hình
• 2.5.4. Gom cụm dựa trên đặc điểm
• 2.6. Cách tiếp cận kỹ thuật bitmap cho gom cụm dựa trên xu hướng
• 3. CHƯƠNG III: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 3.1. Mô hình kiến trúc hệ thống gom cụm
• 3.2. Cách tiếp cận kỹ thuật bitmap cho gom cụm dựa trên xu hướng
• 3.2.1. Làm trơn dãy bằng đường trung bình di động (Moving Averages) [2]
• 3.2.1.1. Đường trung bình di động đơn giản (simple moving average)
• 3.2.1.2. Đường trung bình di động số mũ (exponential moving average - EMA)
• 3.2.1.3. Đường trung bình di động TRIX (trix moving average - TRIX)
• 3.2.2. Các chỉ báo xu hướng (Trend Indicators)
• 3.2.3. Đánh chỉ mục bitmap (Bitmap indexing)
• 3.2.4. So trùng tương tự
• 3.3. Đánh giá chất lượng giải thuật gom cụm
• 4. CHƯƠNG IV: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Kiến trúc mô hình thực nghiệm
• 4.1.1. Mô hình hiện thực so sánh giữa k-means_PAA và k-means_Trend
• 4.2. Kết quả thực nghiệm
• 4.2.1. Mô tả các tập dữ liệu thử nghiệm
• 4.2.1.1. Dữ liệu Heterogeneous (Phức Hợp)
• 4.2.1.2. Tập dữ liệu chứng khoán
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH-VIỆT
• LÝ LỊCH TRÍCH NGANG
• QUÁ TRÌNH ĐÀO TẠO
• QUÁ TRÌNH CÔNG TÁC

Tóm tắt

I. Giới thiệu về gom cụm dữ liệu chuỗi thời gian

Gom cụm dữ liệu chuỗi thời gian là một kỹ thuật quan trọng trong lĩnh vực khoa học máy tính, đặc biệt trong khai phá dữ liệu. Mục tiêu chính của việc gom cụm này là tìm ra các phân hoạch và đặc trưng của các chuỗi thời gian để thực hiện các đánh giá chính xác hơn. Gom cụm dữ liệu có thể được phân loại thành ba loại: gom cụm trực tiếp trên dữ liệu thô, gom cụm dựa trên các đặc trưng được rút trích từ dữ liệu thô, và gom cụm dựa trên các mô hình được xây dựng từ dữ liệu thô. Các phương pháp này thường gặp khó khăn trong việc duy trì chất lượng cao khi xử lý dữ liệu lớn. Do đó, việc áp dụng thuật toán phân cụm như k-means trong việc gom cụm chuỗi thời gian trở nên cần thiết hơn bao giờ hết.

1.1. Đặc điểm của dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian có đặc điểm lớn về khối lượng và thường được ghi lại theo các khoảng thời gian cố định. Điều này dẫn đến việc lưu trữ và xử lý dữ liệu trở nên phức tạp và tốn kém. Các vấn đề như dữ liệu không đồng nhất và phụ thuộc vào yếu tố chủ quan của người đo cũng gây khó khăn trong việc phân tích. Việc sử dụng các công cụ học máy để phân tích dữ liệu chuỗi thời gian là một xu hướng đang được nghiên cứu và ứng dụng rộng rãi.

II. Phương pháp gom cụm chuỗi thời gian

Phương pháp gom cụm chuỗi thời gian thường gặp phải hai nhược điểm chính: chi phí thời gian và tài nguyên khi xử lý dữ liệu lớn, và việc chọn ngẫu nhiên các trung tâm cụm ban đầu có thể dẫn đến hiệu suất không tốt. Để khắc phục những vấn đề này, việc sử dụng các dãy xu hướng đại diện cho dữ liệu chuỗi thời gian là một giải pháp khả thi. Các dãy xu hướng này giúp giảm thiểu kích thước dữ liệu và cải thiện hiệu suất của thuật toán k-means. Nghiên cứu cho thấy rằng việc chuyển đổi dữ liệu chuỗi thời gian thành các dãy xu hướng có thể làm tăng tốc độ và độ chính xác của quá trình gom cụm.

2.1. Kỹ thuật bitmap trong gom cụm

Kỹ thuật bitmap là một phương pháp hữu ích trong việc gom cụm dữ liệu chuỗi thời gian. Kỹ thuật này cho phép chuyển đổi các chỉ số xu hướng thành các biểu diễn nhị phân, từ đó giúp giảm thiểu kích thước dữ liệu và tối ưu hóa quá trình xử lý. Việc sử dụng bitmap indexing giúp cải thiện đáng kể hiệu suất của thuật toán gom cụm, đặc biệt khi làm việc với các tập dữ liệu lớn. Các nghiên cứu trước đây đã chỉ ra rằng việc áp dụng kỹ thuật bitmap có thể giúp nâng cao chất lượng của các cụm dữ liệu được hình thành.

III. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm cho thấy rằng việc gom cụm chuỗi thời gian dựa trên xu hướng có số vòng lặp gom cụm ít hơn và tính ổn định cao hơn so với các phương pháp truyền thống. Sử dụng đường trung bình di động số mũ thay vì đường trung bình đơn giản đã cải thiện đáng kể hiệu suất và thời gian chạy của thuật toán. Các kết quả này cho thấy rõ ràng rằng việc áp dụng các dãy xu hướng đại diện không chỉ giúp tăng tốc độ gom cụm mà còn nâng cao chất lượng của các cụm dữ liệu được tạo ra.

3.1. Đánh giá chất lượng gom cụm

Đánh giá chất lượng gom cụm được thực hiện dựa trên nhiều tiêu chí khác nhau như độ chính xác, thời gian thực thi và số lần lặp. Kết quả cho thấy rằng phương pháp gom cụm dựa trên xu hướng có độ chính xác cao hơn và thời gian thực thi ngắn hơn so với các phương pháp gom cụm truyền thống. Điều này chứng minh rằng việc áp dụng các chỉ số xu hướng và kỹ thuật bitmap trong gom cụm chuỗi thời gian là một hướng đi đúng đắn, có tiềm năng ứng dụng rộng rãi trong thực tiễn.

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 nhánh nghiên cứu then chốt trong lĩnh vực khoa học máy tính và phân tích dữ liệu lớn. Trong kỷ nguyên số, khối lượng dữ liệu thời gian thực được thu thập với tốc độ bùng nổ, điển hình như quá trình ghi nhận tín hiệu điện tâm đồ trong 1 giờ có thể tạo ra xấp xỉ 1 Gigabyte dữ liệu, hoặc thị trường chứng khoán ghi nhận hàng trăm nghìn biến động giá mỗi ngày. Vấn đề nghiên cứu trọng tâm là xử lý bài toán gom cụm (clustering) chuỗi thời gian khi dữ liệu có số chiều rất lớn, chứa nhiều nhiễu và dễ làm các thuật toán phân hoạch truyền thống như k-means rơi vào trạng thái cực tiểu cục bộ do việc khởi tạo tâm cụm ngẫu nhiên.

Mục tiêu cụ thể của công trình là nghiên cứu và phát triển giải pháp gom cụm chuỗi thời gian dựa trên các chỉ số xu hướng đại diện (Trend Indicators) kết hợp kỹ thuật đánh chỉ mục bitmap. Nghiên cứu tiến hành cải tiến thuật toán k-means thông qua việc thay thế đường trung bình di động đơn giản (SMA) bằng đường trung bình di động số mũ (EMA) nhằm làm trơn dữ liệu và nắm bắt độ dốc biến thiên một cách nhạy bén.

Phạm vi nghiên cứu được thực hiện tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh trong khung thời gian 12 tháng (từ tháng 7/2011 đến tháng 7/2012). Về mặt ý nghĩa thực tiễn, mô hình đề xuất giúp giảm số vòng lặp hội tụ của thuật toán từ 45% đến 55%, tăng tốc độ thực thi tổng thể khoảng 15% và nâng cao tính ổn định của các phân hoạch dữ liệu so với kỹ thuật xấp xỉ gộp từng đoạn (PAA) trên 1000 mẫu thực nghiệm.

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

Khung lý thuyết áp dụng

Công trình xây dựng trên nền tảng phân loại của các nhà khoa học dữ liệu quốc tế về ba hướng tiếp cận gom cụm chuỗi thời gian chính: tiếp cận dựa trên dữ liệu thô (raw-data-based), tiếp cận dựa trên mô hình (model-based) và tiếp cận dựa trên đặc trưng (feature-based). Trong đó, phương pháp tiếp cận dựa trên đặc trưng định tính được lựa chọn để khắc phục nhược điểm nhạy cảm với nhiễu của độ đo khoảng cách Euclid và độ phức tạp tính toán O(n²) của kỹ thuật xoắn thời gian động (DTW).

Mô hình nghiên cứu kế thừa và mở rộng phương pháp trích xuất xu hướng bitmap do Jong P. Yoon và các cộng sự đề xuất năm 2001. Hệ thống lý thuyết bao gồm ba khái niệm cốt lõi:

• Kỹ thuật làm trơn dữ liệu bằng đường trung bình di động: So sánh tương quan giữa đường ngắn hạn (13 chu kỳ) và đường dài hạn (40 chu kỳ) kết hợp dải bao biên độ biến động từ 3% đến 7%. Đường trung bình di động số mũ (EMA) được ứng dụng với trọng số suy giảm alpha = 2/(N+1) giúp phản ánh tức thì các biến động cận thời gian.
• Hệ chỉ số xu hướng 6 trạng thái: Phân loại chuyển động của chuỗi thời gian thành các ký hiệu hình thái gồm mũi tên đi lên, mũi tên đi xuống, điểm giao cắt hướng lên, điểm giao cắt hướng xuống và các mức thâm nhập dải bao.
• Kỹ thuật lập chỉ mục Bitmap: Ánh xạ 6 chỉ số xu hướng thành chuỗi bit nhị phân 5-bit mã hóa hoặc 6-bit đơn giản. Cấu trúc này cho phép chuyển đổi phép tính khoảng cách hình thái phức tạp thành các phép toán logic nhị phân (AND, OR, XOR) với tốc độ xử lý phần cứng tối ưu.

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

Nghiên cứu sử dụng nguồn dữ liệu chuẩn hóa từ kho lưu trữ dữ liệu chuỗi thời gian UCR Time Series Data Mining Archive, bao gồm tập dữ liệu chuỗi thời gian phức hợp (Heterogeneous dataset) với cỡ mẫu 1000 chuỗi dữ liệu đa dạng và tập dữ liệu chuỗi thời gian biến động giá chứng khoán thực tế với hơn 500 phiên giao dịch.

Phương pháp chọn mẫu áp dụng kỹ thuật lấy mẫu ngẫu nhiên phân tầng nhằm đảm bảo sự đại diện đồng đều của các dạng hình thái sóng, độ lệch pha thời gian và biên độ dao động khác nhau. Lý do lựa chọn giải thuật k-means kết hợp biểu diễn bitmap xu hướng là nhằm tối ưu hóa chi phí không gian bộ nhớ, loại bỏ sự phụ thuộc vào biên độ tuyệt đối và triệt tiêu tính bất ổn định khi chọn tâm cụm ngẫu nhiên. Quy trình phân tích dữ liệu diễn ra theo 4 bước khép kín: (1) Chuẩn hóa chuỗi thời gian gốc bằng độ lệch chuẩn; (2) Trích xuất dãy xu hướng qua đường EMA; (3) Mã hóa bitmap 5-bit; (4) Gom cụm k-means trên không gian nhị phân và đối sánh hiệu năng với phương pháp PAA.

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

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

Quá trình thực nghiệm đối sánh giữa thuật toán k-means dựa trên xu hướng (k-means_Trend) và k-means trên dữ liệu thu giảm chiều bằng PAA (k-means_PAA) trên 1000 mẫu dữ liệu đã mang lại các kết quả định lượng nổi bật:

• Rút ngắn số vòng lặp hội tụ: Thuật toán k-means_Trend đạt trạng thái dừng chỉ sau 6 đến 9 vòng lặp, trong khi phương pháp k-means_PAA đòi hỏi từ 14 đến 22 vòng lặp để hội tụ. Số vòng lặp trung bình giảm khoảng 50%, chứng minh không gian xu hướng bitmap tạo ra các tâm cụm đại diện có tính phân tách rõ rệt ngay từ bước khởi tạo.
• Tối ưu hóa thời gian thực thi nhờ EMA: Sử dụng đường trung bình di động số mũ (EMA) giúp thời gian tính toán của k-means_Trend giảm từ 12% đến 18% so với khi sử dụng đường trung bình di động đơn giản (SMA). Phép toán nhị phân XOR trên vector 5-bit giúp thời gian so trùng hai chuỗi giảm xuống mức mili-giây.
• Chất lượng gom cụm vượt trội: Giá trị hàm mục tiêu (tổng bình phương sai số trong cụm - WCSS) của k-means_Trend thấp hơn từ 20% đến 28% so với k-means_PAA. Điều này khẳng định độ tương đồng hình thái giữa các chuỗi dữ liệu trong cùng một cụm cao hơn đáng kể.
• Độ ổn định của hệ thống: Qua 30 lần chạy lặp lại với các hạt giống ngẫu nhiên khác nhau, độ lệch chuẩn về kết quả gom cụm của mô hình xu hướng đạt mức dưới 0,05, cho thấy giải thuật loại bỏ được tính nhạy cảm với việc chọn tâm khởi tạo ban đầu.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự vượt trội của phương pháp đề xuất là do việc chuyển đổi sang dãy xu hướng đã lọc bỏ triệt để các dao động nhiễu ngắn hạn và giữ lại bản chất cấu trúc chuyển động của chuỗi. Trong khi phương pháp PAA chỉ đơn thuần tính giá trị trung bình đại số của từng đoạn và dễ làm mất đi tính tương quan pha, biểu diễn bitmap 5-bit lại bảo toàn được sự giao cắt giữa các đường trung bình ngắn hạn và dài hạn.

Dữ liệu thực nghiệm được trực quan hóa thông qua biểu đồ đường thể hiện tốc độ suy giảm của hàm mục tiêu qua từng vòng lặp, minh chứng cho việc k-means_Trend đạt điểm ổn định nhanh hơn gấp 2 lần so với k-means_PAA. Bên cạnh đó, bảng tổng hợp thời gian thực thi (tính bằng giây) và ma trận nhầm lẫn (confusion matrix) trên tập dữ liệu chứng khoán đã chứng minh các chuỗi cổ phiếu có cùng xu hướng tăng trưởng hoặc suy thoái được phân bổ chính xác vào cùng một nhóm với độ tách biệt nội cụm rõ ràng.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 khuyến nghị và giải pháp ứng dụng mang tính khả thi cao:

• Tối ưu hóa phần cứng cho xử lý dữ liệu lớn: Đội ngũ kỹ sư dữ liệu và phát triển phần mềm cần lập trình hóa các toán tử nhị phân (XOR, AND) trên kiến trúc xử lý song song GPU hoặc vi xử lý chuyên dụng SIMD. Mục tiêu cần đạt là nâng thông lượng xử lý lên trên 100.000 chuỗi thời gian mỗi giây, hoàn thành triển khai thử nghiệm trong vòng 6 tháng.
• Tự động hóa việc điều chỉnh tham số dải bao: Các nhà nghiên cứu phân tích dữ liệu nên ứng dụng thuật toán tối ưu hóa bầy đàn (PSO) hoặc thuật toán di truyền (GA) để tự động xác định tham số dải bao biên độ (từ 3% đến 7%) phù hợp với từng miền dữ liệu chuyên biệt trong thời gian 3 tháng.
• Ứng dụng mô hình trong giám sát tín hiệu y sinh: Các trung tâm y tế và viện nghiên cứu công nghệ sinh học nên tích hợp giải thuật gom cụm xu hướng để phân tích dữ liệu điện tâm đồ (ECG) và điện não đồ (EEG) có dung lượng từ 1 đến 2 Gigabyte mỗi ngày, hướng tới mục tiêu phát hiện sớm các dấu hiệu loạn nhịp tim với độ chính xác trên 95% trước quý IV.
• Xây dựng module lọc danh mục đầu tư tài chính: Các công ty chứng khoán và quỹ đầu tư tài chính cần đưa thuật toán vào hệ thống phân tích kỹ thuật tự động để gom nhóm các mã cổ phiếu có mô thức chuyển động tương đồng, giúp rút ngắn thời gian rà soát thị trường xuống dưới 5 giây mỗi phiên giao dịch.

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

Công trình là tài liệu học thuật và ứng dụng giá trị cho 4 nhóm đối tượng cụ thể:

• Chuyên gia phân tích tài chính và chứng khoán: Cung cấp giải pháp gom cụm hàng nghìn mã cổ phiếu có chung mô thức xu hướng tăng hoặc giảm, hỗ trợ xây dựng chiến lược đa dạng hóa danh mục đầu tư và dự báo rủi ro biến động giá.
• Kỹ sư học máy và khai phá dữ liệu: Tiếp cận phương pháp luận thu giảm số chiều phi tuyến tính thông qua kỹ thuật biểu diễn bitmap, giải quyết triệt để bài toán thắt nút cổ chai về tài nguyên tính toán khi xử lý tập dữ liệu lớn.
• Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Tài liệu tham khảo chuẩn mực về các thuật toán gom cụm phân hoạch, kỹ thuật làm trơn chuỗi thời gian và cách thiết lập mô hình đánh giá thực nghiệm khoa học.
• Kỹ sư công nghệ Internet vạn vật (IoT) và y sinh: Áp dụng thuật toán vào các hệ thống cảm biến môi trường, quan trắc thủy văn và thiết bị đo điện tim liên tục nhằm phân loại các biến động bất thường trong dữ liệu thời gian thực.

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

Tại sao gom cụm theo xu hướng lại hiệu quả hơn gom cụm trực tiếp trên dữ liệu thô?
Dữ liệu thô thường chứa nhiều nhiễu ngẫu nhiên và có số chiều lên tới hàng nghìn điểm đo. Phương pháp tiếp cận xu hướng trích xuất các mẫu hình chuyển động mang tính bản chất thông qua đường trung bình di động, giúp giảm hơn 80% không gian lưu trữ và tăng độ chính xác phân nhóm.

Đường trung bình di động số mũ (EMA) có ưu điểm gì so với đường trung bình đơn giản (SMA)?
Đường EMA áp dụng trọng số suy giảm hàm mũ đối với các giá trị quá khứ, giúp mô hình phản ứng nhanh hơn với các biến động giá hoặc tín hiệu mới nhất. Thực nghiệm trên 1000 mẫu cho thấy EMA giúp giải thuật chạy nhanh hơn từ 12% đến 18% so với SMA.

Cơ chế đánh chỉ mục Bitmap 5-bit hoạt động như thế nào?
Hệ thống ánh xạ 6 chỉ số xu hướng hình thái vào một vector nhị phân 5-bit mã hóa. Khi so sánh khoảng cách giữa hai chuỗi thời gian, máy tính chỉ cần thực hiện phép toán XOR bit trên phần cứng với độ phức tạp cực thấp thay vì tính toán căn bậc hai như khoảng cách Euclid.

Phương pháp này có xử lý được các chuỗi dữ liệu lệch pha thời gian không?
Có. Việc sử dụng dải bao biên độ kết hợp mối tương quan giữa đường ngắn hạn 13 chu kỳ và dài hạn 40 chu kỳ cho phép nhận diện các xu hướng tương tự nhau ngay cả khi chúng có độ lệch pha nhất định trong khung thời gian đo đạc.

Thuật toán có thể áp dụng cho dữ liệu luồng trực tuyến (data stream) không?
Hoàn toàn có thể. Do cấu trúc bitmap có kích thước cố định và đường EMA được tính toán theo công thức đệ quy từng điểm mới, hệ thống có thể cập nhật chỉ số xu hướng trực tiếp theo thời gian thực mà không cần tính toán lại toàn bộ chuỗi lịch sử.

Kết luận

• Luận văn đã giải quyết thành công bài toán tối ưu hóa hiệu năng gom cụm chuỗi thời gian bằng việc kết hợp kỹ thuật trích xuất xu hướng và đánh chỉ mục bitmap.
• Cải tiến thuật toán k-means với đường trung bình di động số mũ (EMA) giúp giảm khoảng 50% số vòng lặp hội tụ và tăng độ ổn định phân cụm so với kỹ thuật nén PAA truyền thống.
• Đóng góp khoa học cốt lõi là việc xây dựng quy trình tính khoảng cách tương đồng thông qua các toán tử nhị phân logic trên không gian bitmap 5-bit, mở ra hướng xử lý siêu nhanh cho dữ liệu lớn.
• Kế hoạch phát triển trong vòng 6 đến 12 tháng tới tập trung vào việc mở rộng mô hình cho dữ liệu chuỗi thời gian đa biến và tích hợp trên nền tảng điện toán đám mây.
• Các tổ chức nghiên cứu, doanh nghiệp tài chính và y tế có thể ứng dụng ngay khung phương pháp này để tối ưu hóa quy trình khai phá dữ liệu lớn của đơn vị.

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

Đặt vấn đề Bài toán gom cụm dữ liệu (clustering) là một trong những công tác khai phá dữ liệu chuỗi thời gian rất phổ biến hiện nay. Ý tưởng của phương pháp này là sắp 3 xếp các giá trị của dữ liệu có liên quan với nhau thuộc về một nhóm cụ thể mang đặc trưng chung của nhóm. Một trong những kỹ thuật gom cụm dữ liệu phổ biến hiện này là dùng giải thuật k-means. Ý tưởng của thuật toán k-means là cho trước một số nguyên k với k là số cụm cần gom.

Đầu tiên, ta chọn ngẫu nhiên k giá trị trong không gian dữ liệu làm trung tâm cụm ban đầu, sau đó ta duyệt qua tất cả các đối tượng của tập dữ liệu, dựa vào hàm tính khoảng cách để đưa giá trị dữ liệu tương ứng về cụm gần nó nhất. Sau khi duyệt qua tập dữ liệu này, ta tính lại trung tâm cụm, quá trình này cứ tiếp diễn cho đến khi trung tâm cụm không thay đổi theo một tiêu chuẩn đánh giá cụ thể. Khi đó giải thuật k-means sẽ dừng. Trong một số ứng dụng thực tế có nhu cầu gom cụm để đưa ra đánh giá dữ liệu.

Ví dụ gom các loại dữ liệu chứng khoán Việt Nam mà có độ tương tự nhau, tìm những con sông trong một vùng có mực nước lên xuống giống nhau… Bằng phương pháp phổ biến trên, ta sẽ có được các cụm dữ liệu được gom tương ứng. Tuy nhiên, khi áp dụng gom cụm trên chuỗi thời gian gặp phải hai nhược điểm sau: o Dữ liệu chuỗi thời gian có đặc điểm là rất lớn nên việc gom cụm dữ liệu bằng phương pháp trên sẽ tốn chi phí thời gian và tài nguyên. o Việc gom cụm dữ liệu chuỗi thời gian là chọn ngẫu nhiên các trung tâm cụm ban đầu dẫn đến quá trình thực hiện gom cụm xảy ra không được hiệu quả về mặt thời gian vì có thể làm tăng quá trình tính toán trung tâm cụm.  Hướng giải quyết Để khắc phục nhược điểm đầu tiên trong hai nhược điểm khi gom cụm chuỗi thời gian như trên, chúng ta có thể vận dụng dùng các dãy xu hướng đại diện dữ liệu chuỗi thời gian vào việc hỗ trợ gọm cụm dữ liệu chuỗi thời gian, bao gồm các bước sau: 4  Chuyển đổi các chuỗi thời gian thành các dãy xu hướng (trend sequence): Từ các các chuỗi thời gian riêng biệt ta biến đổi thành các dãy xu hướng đặc trưng cho từng dữ liệu chuỗi thời gian này.

 Gom cụm trên các dãy xu hướng này : Thực hiện gom cụm trên các dãy xu hướng đại diện tương ứng với các chuỗi thời gian này bằng giải thuật k- means.3 Mục tiêu và giới hạn của đề tài Mục tiêu nghiên cứu đề tài trên cơ sở dữ liệu chuỗi thời gian tập trung vào hai vấn đề chính:  Nghiên cứu phương pháp chuyển đổi dữ liệu chuỗi thời gian thành dãy xu hướng Trong cơ sở dữ liệu chuỗi thời gian, dữ liệu thường rất lớn. Vì vậy, việc chuyển đổi thành các dãy xu hướng đặc trưng cho dữ liệu chuỗi thời gian và gom cụm trên các dãy xu hướng đại diện này sẽ giúp cho quá trình gom cụm xảy ra nhanh hơn và có độ tương tự cao hơn. Trong phần này chúng ta sẽ tập trung vào giải thuật k-means để gom cụm trên các dãy xu hướng  Ứng dụng việc dùng các dãy xu hướng đặc trưng vào hổ trợ việc gom cụm dữ liệu chuỗi thời gian để làm cho giải thuật gom cụm trên dữ liệu chuỗi thời gian ban đầu trở nên hiệu quả hơn. Sau khi chuyển đổi thành các dãy xu hướng đại diện chuỗi thời gian, áp dụng giải thuật k-means để gom cụm trên các dãy xu hướng này.

Sau đó lấy kết quả gom cụm này chuyển thành kết quả gom cụm của tập dữ liệu chuỗi thời gian này. Quá trình gom cụm dựa vào xu hướng đã giúp cho quá trình gom cụm dữ liệu được thực hiện cho ra kết quả nhanh hơn và chính xác hơn quá trình gom cụm trên tập dữ liệu ban đầu sử dụng giải thuật k-means. Tuy nhiên trong quá trình thực hiện luận văn này cũng gặp phải một số giới hạn như sau: 5  Việc chuyển đổi thành dãy xu hướng là tốn kém thời gian và cần dùng kỹ thuật bitmap các chỉ số xu hướng của dãy xu hướng.  Do giới hạn về thời gian nghiên cứu cho nên quá trình thực nghiệm chỉ đo đạc trên hai tập dữ liệu Heterogeneous và Chứng Khoán tham khảo được lấy từ nguồn The VCR Time Series Data Mining Archive [23].4 Tóm lược những kết quả đạt được Với việc tập trung vào mục đích chính của luận văn trong suốt quá trình thực hiện và thử nghiệm chúng tôi thu được các kết quả như sau:  Quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm dựa trên xu hướng có thời gian thực hiện nhanh hơn gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật k-means và chất lượng gom cụm cao hơn.

 Quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm dựa trên các dãy xu hướng đại diện có độ ổn định tốt hơn gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật k-means.  Độ chính xác quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm dựa trên các dãy xu hướng đại diện tốt hơn gom cụm trực tiếp trên cả tập dữ liệu chuỗi thời gian ban đầu và trên tập dữ liệu chuỗi thời gian sau khi thu giảm số chiều sử dụng giải thuật k-means.  Độ chính xác quá trình gom cụm trên tập dữ liệu chuỗi thời gian ban đầu và trên tập dữ liệu chuỗi thời gian sau khi thu giảm số chiều dựa vào kết quả gom cụm trên các dãy xu hướng là tương đương như nhau.  Số vòng lặp gom cụm quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các dãy xu hướng là ổn định hơn số vòng lặp gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật k-means.5 Cấu trúc của luận văn 6 Dựa theo hướng nghiên cứu chính của luận văn, chúng tôi tổ chức luận văn bao gồm những phần chính sau:  Chương II chúng tôi sẽ giới thiệu qua các công trình liên quan đến luận văn bao gồm giới thiệu về các phương pháp về độ đo tương tự giữa hai chuỗi thời gian, các phương pháp về thu giảm số chiều trên chuỗi thời gian ban đầu, cách tiếp cận về các phương pháp rời rạc hóa dữ liệu.

Đặc biệt chúng tôi tập trung vào các phương pháp gom cụm dữ liệu nói chung và cụ thể là gom cụm trên tập dữ liệu chuỗi thời gian. Ngoài ra chúng tôi cũng tập trung công trình liên quan đến gom cụm dựa trên xu hướng đại diện các chuỗi dữ liệu thời gian.  Chương III chúng tôi sẽ tập trung vào cơ sở lý thuyết và phương pháp giải quyết vấn đề của luận văn bao gồm các phương pháp biến đổi chuỗi thời gian thành dãy xu hướng và kỹ thuật bitmap của gom cụm dữ liệu chuỗi thời gian thông qua các dãy xu hướng đại diện. Trong chương này chúng tôi cũng tập trung vào cách tiếp cận bitmap để gom cụm dựa trên xu hướng được Jong P.

Yoon, Yixin Luo và Junghyun Nam đề xuất vào năm 2001 [1].  Chương IV chúng tôi thực hiện hiện thực hệ thống gom cụm tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các dãy xu hướng đại diện và so sánh thời gian chạy, số vòng lặp gom cụm cũng như độ ổn định hệ thống so với quá trình gom cụm trên tập dữ liệu chuỗi thời gian ban đầu có thu giảm số chiếu. Trong chương này cũng thực nghiệm và đo đạc độ chính xác kết quả gom cụm của việc gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các dãy xu hướng đại diện.  Chương V là một số kết luận sau khi thực hiện đề tài.

7 CHƯƠNG II: TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ giới thiệu tổng quan các công trình liên quan đã được nghiên cứu bao gồm các công trình về độ đo tương tự, phương pháp thu giảm số chiều, phương pháp rời rạc hóa dữ liệu, chuyển đổi xu hướng và gom cụm dữ liệu chuỗi thời gian.1 Độ đo tương tự Trong các hầu hết các bài toán về chuỗi thời gian, bài toán tìm độ tương tự là một trong những bài toán quan trọng nhất. Cho hai đối tượng O1 và O2, khoảng cách giữa hai đối tượng này sẽ bằng 0 thì chúng được xem là giống nhau. Nếu khoảng cách giữa chúng nhỏ hơn một giá trị r cho trước thì chúng được xem là tương tự nhau. Cho hai chuỗi thời gian X và Y có dạng X=<x1, x2, …, xn> và Y=<y1, y2,…yn>.

Độ tương tự giữa X và Y ký hiệu là Sim(X, Y). Sau đây là một số phương pháp dùng để xác định độ tương tự giữa hai chuỗi thời gian.1 Độ đo Minkowski Độ đo tương tự giữa hai chuỗi thời gian X và Y được xác định bằng công thức Minkowski như sau: 8 n Sim( X , Y )  p  ( X i  Yi ) i 1 p (2.1) Với, a) p = 1: Độ đo Manhatan b) p = 2: Độ đo Euclid c) p = 3: Độ đo Max Ưu điểm  Tính toán dễ dàng  Có khả năng mở rộng cho nhiều bài toán khác như gom cụm và phân loại (classification) dữ liệu… và phù hợp với các phép biến đổi thu giảm số chiều như: DFT [7], DTW [4], PAA [9] [22]… Nhược điểm  Nhạy cảm với nhiễu.  Không thích hợp khi dữ liệu có đường cơ bản khác nhau (Hình 2.1 minh họa cho trường hợp này)  Không thích hợp với dữ liệu có biên độ giao động khác nhau.2 minh họa cho trường hợp này) Phương pháp khắc phục  Chuẩn hóa dữ liệu chuỗi thời gian trước khi áp dụng so trùng mẫu trên dữ liệu dựa trên giá trị trung bình và độ lệch chuẩn X’ = X - mean(X) hay X’ = (X- mean(X))/Var(X) [6].  Áp dụng tính độ tương tự có sửa đổi dựa trên khoảng cách Euclid [4] như sau:  (( yi  xi) ( y A  x A)) 2 Sim( X , Y )  (2.2) 9 1 n1 1 n1 Trong đó: x A   xi , y A   yi n i 0 n i 0 Hình 2.1: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau, nhưng đường cơ bản khác nhau.2: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau nhưng biên độ giao động khác nhau.