Luận Văn Thạc Sĩ: Khai Phá Xu Hướng Tuần Tự Từ Dữ Liệu Chuỗi Thời Gian

• Tác giả: Nguyễn Thanh Vũ
• Người hướng dẫn: TS. Võ Thị Ngọc Châu
• 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: Khai Phá Mẫu Xu Hướng Tuần Tự Liên Đối Tượng Từ Tập 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: 2013
• Địa điểm: TP. Hồ Chí Minh

• LỜI CÁM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU DE TÀI
• 1.1. Giới thiệu vẫn đề
• 1.2. Mục tiêu dé tải
• 1.3. Pham Vi G6 ôn hố.4 Y nghĩa dé tai.5 Cấu trúc luận VAN
• 2. CHƯƠNG 2: CƠ SO LY THUYẾT
• 2.1. Dir li8u ChUG: thoi QIAN
• 2.2. Xử lý dữ liệu chuỗi thời gian
• 2.2.1. Chuẩn hóa dit liệu (Data Normalization)
• 2.3. Khai phá mẫu tuần tự phố biến
• 2.3.1. Một số khái niệm thường gap trong khai phá mẫu tuần tự pho biến
• 2.3.2. Phương pháp thu giảm số chiều xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate ADDTOXIITAfION)
• 2.3.3. Phương pháp biến đối chuỗi thời gian sang dạng kí tự SAX (Symbolic Aggregate ADDTOXIITAfION)
• 2.3.4. Phương pháp biến đối chuỗi thời gian sang dạng kí hiệu khuynh hướng
• 2.3.5. Đại số quan hệ thời gian Allen
• 2.3.6. Generic Dictionary trong C#
• 3. CHƯƠNG 3: CAC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 3.1. Các phương pháp tìm motif trong dữ liệu chuỗi thời gian
• 3.1.1. Phương pháp tìm motif đối với cơ sở dữ liệu chuỗi thời gian lớn
• 3.1.2. Phương pháp tìm motif dựa trên MÌDL
• 3.2. Một số giải thuật khai phá mẫu phổ biến
• 3.2.1. Giải thuật FP-Growth
• 3.2.2. Giải thuật ŒSTP
• 3.2.3. Giải thuật Prefix ŠpaIn
• 3.3. Một số công trình liên quan khác về khai phá mẫu trên dữ liệu chuỗi thời gian
• 4. CHƯƠNG 4: HƯỚNG TIẾP CÁN GIẢI QUYẾT VẤN ĐỀ
• 4.1. Giải thuật Brute Force
• 4.2. Giải thuật dựa trên cấu trúc cây
• 4.3. Quá trình khai phá mẫu xu hướng tuần tự liên đối tượng trên cơ sở dữ liệu chuỗi thời gian
• 4.3.1. Giai đoạn chuyển đổi sang chuỗi thời gian khuynh hướng
• 4.3.2. Giai đoạn tìm các chuỗi con phổ biến từ chuỗi thời gian khuynh hướng
• 4.3.3. Giai đoạn khai phá mẫu xu hướng tuần tự phổ biến liên đối tượng
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Tiền xử lý dữ liệu
• 5.2. Lưu trữ dữ liệu
• 5.3. Mô tả thực nghiệm
• 5.3.1. Thực nghiệm cố định
• 5.3.2. Thực nghiệm cố định chiều dài chuỗi thời gian
• 5.3.3. Thực hiện kiểm tra số lượng kết hợp được yêu cầu cao ra
• 5.3.4. Thực hiện kiểm tra số ứng viên của hai giải thuật
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Đóng góp của luận văn
• 6.2. Hướng phát triển trong tương lai
• TÀI LIỆU THAM KHẢO

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

Dữ liệu chuỗi thời gian hiện nay xuất hiện phổ biến trong nhiều lĩnh vực như tài chính, y học, địa chất và khí hậu. Khai phá dữ liệu từ các chuỗi thời gian giúp các nhà phân tích và quản lý có cái nhìn sâu sắc hơn về các mối quan hệ mang yếu tố thời gian giữa các đối tượng. Việc phân tích chuỗi thời gian không chỉ giúp phát hiện các mẫu xu hướng mà còn hỗ trợ trong việc ra quyết định. Theo Frawley và W.J (1991), khai phá tri thức trong các cơ sở dữ liệu là một quá trình không đơn giản, nhằm tìm ra các mẫu có tính hợp lệ và mang ý nghĩa. Điều này đặc biệt quan trọng trong lĩnh vực đầu tư chứng khoán, nơi mà việc áp dụng các kỹ thuật khai phá dữ liệu có thể giúp dự đoán sự biến động giá của cổ phiếu.

1.1 Tầm quan trọng của dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian có vai trò quan trọng trong việc phân tích và dự đoán các xu hướng trong tương lai. Các nhà nghiên cứu đã chỉ ra rằng, việc khai thác thông tin từ dữ liệu này có thể giúp phát hiện các mẫu và xu hướng tiềm ẩn. Phân tích dữ liệu chuỗi thời gian cho phép các nhà đầu tư và nhà phân tích có được cái nhìn tổng quan về các biến động trong thị trường, từ đó đưa ra các quyết định đầu tư chính xác hơn. Việc sử dụng các phương pháp như ARIMA hay mạng nơ-ron trong phân tích dữ liệu chứng khoán đã chứng minh được hiệu quả của chúng trong việc dự đoán giá cổ phiếu.

II. Các phương pháp khai phá mẫu xu hướng tuần tự

Luận văn đề xuất hai giải thuật để khai phá mẫu xu hướng tuần tự liên đối tượng từ tập dữ liệu chuỗi thời gian. Giải thuật đầu tiên là giải thuật brute-force, sử dụng phương pháp vét cạn để tìm kiếm các mẫu. Giải thuật thứ hai là giải thuật dựa trên cấu trúc cây, giúp tối ưu hóa quá trình tìm kiếm và phân tích. Cả hai giải thuật đều được xây dựng dựa trên hướng tiếp cận lặp từng mức từ dưới lên, nhằm xử lý vấn đề bùng nổ tổ hợp trong quá trình phân tích. Kết quả thực nghiệm cho thấy giải thuật dựa trên cấu trúc cây có hiệu quả cao hơn so với giải thuật brute-force, đặc biệt trong việc xử lý các tập dữ liệu lớn.

2.1 Giải thuật brute force

Giải thuật brute-force là một trong những phương pháp đơn giản nhưng hiệu quả trong việc khai thác thông tin từ dữ liệu chuỗi thời gian. Phương pháp này thực hiện việc tìm kiếm tất cả các mẫu có thể có trong tập dữ liệu mà không bỏ sót bất kỳ mẫu nào. Tuy nhiên, nhược điểm lớn của phương pháp này là thời gian tính toán có thể tăng nhanh chóng khi kích thước dữ liệu tăng lên. Do đó, việc áp dụng giải thuật này cần được cân nhắc kỹ lưỡng, đặc biệt trong các bài toán có kích thước dữ liệu lớn.

2.2 Giải thuật dựa trên cấu trúc cây

Giải thuật dựa trên cấu trúc cây được thiết kế để tối ưu hóa quá trình tìm kiếm mẫu trong dữ liệu chuỗi thời gian. Phương pháp này sử dụng cấu trúc cây để tổ chức và lưu trữ thông tin, giúp giảm thiểu thời gian tìm kiếm và phân tích. Kết quả thực nghiệm cho thấy giải thuật này không chỉ nhanh hơn mà còn chính xác hơn so với giải thuật brute-force. Việc áp dụng giải thuật này trong các bài toán thực tế có thể mang lại những lợi ích đáng kể trong việc phát hiện các mẫu xu hướng và mối quan hệ giữa các đối tượng.

III. Đánh giá và ứng dụng thực tiễn

Luận văn đã thực hiện đánh giá và so sánh các giải thuật đề xuất thông qua kết quả thực nghiệm. Kết quả cho thấy giải thuật dựa trên cấu trúc cây có hiệu quả cao hơn trong việc khai phá mẫu xu hướng tuần tự. Việc áp dụng các giải thuật này trong lĩnh vực tài chính, đặc biệt là trong phân tích dữ liệu chứng khoán, có thể giúp các nhà đầu tư đưa ra quyết định chính xác hơn. Khai thác thông tin từ dữ liệu chuỗi thời gian không chỉ giúp phát hiện các xu hướng mà còn hỗ trợ trong việc dự đoán các biến động trong tương lai.

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

Trong lĩnh vực tài chính, việc khai thác dữ liệu chuỗi thời gian có thể giúp các nhà đầu tư nhận diện các xu hướng và biến động của thị trường. Các giải thuật được đề xuất trong luận văn có thể được áp dụng để phân tích dữ liệu chứng khoán, từ đó đưa ra các quyết định đầu tư hợp lý. Việc sử dụng các mẫu xu hướng tuần tự liên đối tượng giúp các nhà đầu tư có cái nhìn rõ ràng hơn về mối quan hệ giữa các cổ phiếu, từ đó tối ưu hóa danh mục đầu tư của mình.

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian ngày càng phổ biến trong nhiều lĩnh vực như tài chính, y học, địa chất và khí hậu. Theo ước tính, khoảng 75% dữ liệu hình ảnh trong các tờ báo từ năm 1974 đến 1989 là dữ liệu chuỗi thời gian, cho thấy tầm quan trọng và mức độ phổ biến của loại dữ liệu này. Tuy nhiên, việc khai thác tri thức từ dữ liệu chuỗi thời gian vẫn là một thách thức lớn do tính chất phức tạp và khối lượng dữ liệu lớn. Luận văn tập trung vào khai phá mẫu xu hướng tuần tự liên đối tượng từ tập dữ liệu chuỗi thời gian, đặc biệt là dữ liệu chứng khoán, nhằm tìm ra các mẫu phổ biến mang yếu tố thời gian giữa nhiều đối tượng khác nhau.

Mục tiêu cụ thể của nghiên cứu là đề xuất một khuôn mẫu mới gọi là “mẫu xu hướng tuần tự phổ biến liên đối tượng” và phát triển hai giải thuật khai phá mẫu hiệu quả dựa trên phương pháp vét cạn (brute-force) và cấu trúc cây (tree-based). Phạm vi nghiên cứu áp dụng trên dữ liệu chuỗi thời gian chứng khoán quốc tế, với thời gian khảo sát từ năm 1982 đến 2010, nhằm đánh giá hiệu quả của các giải thuật trong việc phát hiện các mối quan hệ thời gian chính xác giữa các cổ phiếu. Kết quả nghiên cứu có ý nghĩa quan trọng trong việc hỗ trợ phân tích biến động thị trường, dự báo xu hướng và ra quyết định đầu tư hiệu quả, đồng thời mở rộng ứng dụng khai phá tri thức trên dữ liệu chuỗi thời gian đa đối tượng.

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

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Dữ liệu chuỗi thời gian (Time Series): Chuỗi các giá trị được ghi nhận theo thứ tự thời gian với khoảng cách đều nhau, bao gồm chuỗi đơn biến và đa biến. Các tính chất quan trọng như khuynh hướng (trend), tính mùa vụ, chu kỳ và tính ngẫu nhiên được xem xét để hiểu bản chất dữ liệu.

• Đại số quan hệ thời gian Allen: Định nghĩa 13 mối quan hệ cơ bản giữa các khoảng thời gian như precedes, meets, overlaps, starts, finishes, equals,... giúp mô tả chính xác các mối quan hệ thời gian giữa các sự kiện trong chuỗi.

• Khai phá mẫu tuần tự phổ biến (Frequent Sequential Pattern Mining): Quá trình tìm kiếm các chuỗi con xuất hiện thường xuyên theo thứ tự trong dữ liệu chuỗi thời gian. Các khái niệm chính gồm itemset, chuỗi con, độ hỗ trợ (support), và ngưỡng hỗ trợ tối thiểu (minSup).

• Phương pháp biến đổi dữ liệu: Sử dụng các kỹ thuật như chuẩn hóa dữ liệu (Z-score), thu giảm số chiều (PAA), biến đổi sang chuỗi ký tự (SAX), và ký hiệu khuynh hướng (trend indicator) để chuyển đổi dữ liệu chuỗi thời gian số thực thành dạng ký tự biểu diễn xu hướng, giúp giảm độ phức tạp và tăng hiệu quả khai phá.

• Cấu trúc dữ liệu và thuật toán: Áp dụng cấu trúc cây (tree-based) và phương pháp vét cạn (brute-force) để khai phá mẫu xu hướng tuần tự liên đối tượng, xử lý vấn đề bùng nổ tổ hợp trong khai phá dữ liệu.

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

• Nguồn dữ liệu: Tập dữ liệu chuỗi thời gian thực tế từ thị trường chứng khoán quốc tế, bao gồm các cổ phiếu như S&P500, Boeing (BA), Caterpillar (CAT), CSX, và Deere (DE), với dữ liệu từ năm 1982 đến 2010.

• Tiền xử lý dữ liệu: Chuẩn hóa dữ liệu, bổ sung giá trị thiếu, chuyển đổi dữ liệu số thực sang dạng chuỗi ký tự khuynh hướng gồm 6 ký hiệu biểu diễn các mức độ tăng giảm giá cổ phiếu trong ngắn hạn và dài hạn.

• Phương pháp phân tích:

  • Giai đoạn 1: Chuyển đổi dữ liệu chuỗi thời gian gốc sang chuỗi thời gian khuynh hướng.
  • Giai đoạn 2: Tìm các chuỗi con xu hướng phổ biến lặp lại nhiều lần trong từng chuỗi thời gian khuynh hướng.
  • Giai đoạn 3: Khai phá các mẫu xu hướng tuần tự phổ biến liên đối tượng từ tập các chuỗi con xu hướng của nhiều đối tượng khác nhau.

• Thuật toán khai phá: Phát triển hai giải thuật chính:

  • Giải thuật vét cạn (brute-force) dựa trên phương pháp lặp từng mức từ dưới lên.
  • Giải thuật dựa trên cấu trúc cây (tree-based) nhằm tối ưu hiệu suất và giảm thiểu bùng nổ tổ hợp.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong khoảng 6 tháng, từ tháng 1 đến tháng 6 năm 2013, bao gồm các bước thu thập, tiền xử lý, phát triển thuật toán, thực nghiệm và đánh giá kết quả.

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

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

1. Khả năng khai phá mẫu xu hướng liên đối tượng: Hai giải thuật đề xuất đã thành công trong việc tìm ra các mẫu xu hướng tuần tự phổ biến liên đối tượng trên tập dữ liệu chuỗi thời gian chứng khoán. Ví dụ, mẫu xu hướng thể hiện mối quan hệ giữa cổ phiếu S&P500 và Boeing với độ hỗ trợ tối thiểu 5% đã được phát hiện rõ ràng.

2. Hiệu quả của giải thuật cấu trúc cây: So với giải thuật vét cạn, giải thuật dựa trên cấu trúc cây cho thấy thời gian chạy giảm trung bình khoảng 30-40% khi xử lý từ 3 đến 5 chuỗi thời gian với chiều dài chuỗi 100. Điều này minh chứng cho khả năng xử lý bùng nổ tổ hợp hiệu quả hơn.

3. Ảnh hưởng của chiều dài chuỗi thời gian: Khi chiều dài chuỗi thời gian tăng từ 1 đến 100, thời gian thực thi của cả hai giải thuật tăng nhưng giải thuật cấu trúc cây duy trì hiệu suất tốt hơn, giảm thiểu đáng kể số lượng ứng viên cần kiểm tra.

4. Mức độ chi tiết của mẫu xu hướng: Các mẫu xu hướng tuần tự liên đối tượng cung cấp thông tin chi tiết về khoảng cách thời gian giữa các sự kiện, vượt trội hơn so với các mẫu tuần tự phổ biến truyền thống chỉ quan tâm đến thứ tự sự kiện mà không xét khoảng cách.

Thảo luận kết quả

Kết quả thực nghiệm cho thấy việc khai phá mẫu xu hướng tuần tự liên đối tượng trên dữ liệu chuỗi thời gian là khả thi và mang lại nhiều thông tin giá trị. Giải thuật cấu trúc cây tận dụng cấu trúc dữ liệu hiệu quả để giảm số lượng ứng viên và thời gian tính toán, phù hợp với các tập dữ liệu lớn và phức tạp. So sánh với các nghiên cứu trước đây chỉ khai phá mẫu tuần tự trên một chuỗi đơn lẻ hoặc bỏ qua yếu tố khoảng cách thời gian, luận văn đã mở rộng phạm vi khai phá trên nhiều chuỗi thời gian đồng thời và giữ lại thông tin thời gian chính xác.

Việc sử dụng đại số quan hệ thời gian Allen giúp mô tả đa dạng các mối quan hệ giữa các thành phần trong mẫu xu hướng, từ đó cung cấp góc nhìn sâu sắc hơn về sự tương tác giữa các đối tượng. Kết quả có thể được trình bày qua biểu đồ thời gian chạy và bảng so sánh số lượng ứng viên, minh họa rõ ràng hiệu quả của từng giải thuật.

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

1. Triển khai giải thuật cấu trúc cây trong hệ thống phân tích tài chính: Đề nghị các tổ chức tài chính áp dụng giải thuật này để khai thác tri thức từ dữ liệu chứng khoán, nhằm nâng cao khả năng dự báo biến động thị trường trong vòng 6-12 tháng tới.

2. Mở rộng ứng dụng sang các lĩnh vực khác: Khuyến nghị nghiên cứu áp dụng phương pháp khai phá mẫu xu hướng liên đối tượng trên dữ liệu chuỗi thời gian trong y tế, địa chất và môi trường để phát hiện các mối quan hệ phức tạp giữa các hiện tượng.

3. Phát triển giao diện trực quan hóa kết quả: Xây dựng công cụ trực quan hóa các mẫu xu hướng và mối quan hệ thời gian giúp người dùng dễ dàng hiểu và khai thác thông tin, dự kiến hoàn thành trong 3-6 tháng.

4. Nâng cao hiệu suất xử lý: Tiếp tục tối ưu thuật toán, đặc biệt là giải thuật cấu trúc cây, để xử lý dữ liệu lớn hơn với thời gian thực, đồng thời nghiên cứu áp dụng các kỹ thuật song song và phân tán.

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

1. Nhà nghiên cứu và sinh viên ngành Khoa học máy tính: Có thể sử dụng luận văn làm tài liệu tham khảo về khai phá dữ liệu chuỗi thời gian, phát triển thuật toán và ứng dụng trong phân tích dữ liệu phức tạp.

2. Chuyên gia phân tích tài chính và quản lý đầu tư: Áp dụng các kết quả khai phá mẫu xu hướng để dự báo biến động giá cổ phiếu, hỗ trợ ra quyết định đầu tư hiệu quả và giảm thiểu rủi ro.

3. Nhà phát triển phần mềm và kỹ sư dữ liệu: Tham khảo các giải thuật và cấu trúc dữ liệu được đề xuất để xây dựng các hệ thống khai phá tri thức trên dữ liệu chuỗi thời gian đa đối tượng.

4. Các tổ chức nghiên cứu và ứng dụng trong lĩnh vực y tế, địa chất, môi trường: Khai thác phương pháp để phân tích các dữ liệu chuỗi thời gian phức tạp, phát hiện các mẫu xu hướng liên quan đến sức khỏe, biến đổi khí hậu hoặc các hiện tượng tự nhiên.

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

1. Mẫu xu hướng tuần tự liên đối tượng là gì?
   Là các chuỗi con phổ biến xuất hiện trong nhiều chuỗi thời gian khác nhau, thể hiện mối quan hệ thời gian chính xác giữa các đối tượng, không chỉ quan tâm thứ tự mà còn khoảng cách thời gian giữa các sự kiện.

2. Tại sao cần chuyển đổi dữ liệu chuỗi thời gian sang dạng ký tự khuynh hướng?
   Việc này giúp giảm chiều dữ liệu, loại bỏ nhiễu và biểu diễn các xu hướng tăng giảm một cách rõ ràng, từ đó tăng hiệu quả và độ chính xác của quá trình khai phá mẫu.

3. Giải thuật cấu trúc cây có ưu điểm gì so với vét cạn?
   Giải thuật cấu trúc cây giảm thiểu số lượng ứng viên cần kiểm tra, tiết kiệm thời gian tính toán và xử lý hiệu quả hơn khi dữ liệu có kích thước lớn hoặc nhiều chuỗi thời gian.

4. Phạm vi ứng dụng của nghiên cứu này là gì?
   Ngoài tài chính, phương pháp có thể áp dụng cho các lĩnh vực như y tế, địa chất, môi trường, nơi dữ liệu chuỗi thời gian đa đối tượng và phức tạp cần được phân tích.

5. Làm thế nào để đánh giá mức độ phổ biến của mẫu xu hướng?
   Sử dụng độ đếm hỗ trợ (Support Count) là số lần xuất hiện của mẫu trong tập dữ liệu, so sánh với ngưỡng hỗ trợ tối thiểu do người dùng định nghĩa để xác định tính phổ biến.

Kết luận

• Đề xuất thành công khái niệm “mẫu xu hướng tuần tự phổ biến liên đối tượng” trên dữ liệu chuỗi thời gian đa đối tượng.
• Phát triển hai giải thuật khai phá mẫu hiệu quả, trong đó giải thuật cấu trúc cây vượt trội về hiệu suất so với vét cạn.
• Áp dụng thực nghiệm trên dữ liệu chứng khoán thực tế, chứng minh khả năng phát hiện các mối quan hệ thời gian chính xác và có ý nghĩa.
• Kết quả nghiên cứu hỗ trợ phân tích biến động thị trường, dự báo xu hướng và ra quyết định đầu tư hiệu quả.
• Đề xuất hướng phát triển tiếp theo bao gồm mở rộng ứng dụng, tối ưu thuật toán và phát triển công cụ trực quan hóa kết quả.

Luận văn mở ra hướng nghiên cứu mới trong khai phá dữ liệu chuỗi thời gian, khuyến khích các nhà nghiên cứu và chuyên gia ứng dụng tiếp tục phát triển và áp dụng trong nhiều lĩnh vực khác nhau nhằm nâng cao giá trị khai thác tri thức từ dữ liệu lớn.