Luận văn thạc sĩ về tìm chuỗi con chung dài nhất trong dữ liệu chuỗi thời gian

Luận văn thạc sĩ nghiên cứu máy tính kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào việc tìm chuỗi con chung dài nhất của, khảo sát thực trạng, phân tích nguyên nhân, đề xuất

• Tác giả: Nguyễn Trọng Nhân
• 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: Kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào việc tìm chuỗi con chung dài nhất của hai chuỗi, sử dụng cây hậu tố
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Bài toán kết chuỗi con trên chuỗi dữ liệu thời gian
• 1.3. Mục tiêu và nhiệm vụ của đề tài
• 1.4. Phương pháp nghiên cứu
• 1.5. Ý nghĩa của luận văn
• 1.6. Những kết quả đạt được của luận văn
• 1.7. Bố cục luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Độ đo xoắn thời gian
• 2.2. Các công trình về biểu diễn chuỗi thời gian
• 2.2.1. Phương pháp xấp xỉ gộp từng đoạn (PAA)
• 2.2.2. Phép xấp xỉ gộp ký hiệu hóa SAX
• 2.3. Chuỗi thời gian (Time Series)
• 2.4. Chuỗi con (Subsequence)
• 2.5. Lập trình song song trên hệ thống đa nhân (multi-core)
• 2.5.1. Xử lý Sony Sone
• 2.5.2. Parallel Extensions trong
• 2.6. Kết luận chương
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Cây hậu tố
• 3.1.1. Định nghĩa cây hậu tố
• 3.1.2. Xây dựng cây hậu tố bằng giải thuật đơn giản
• 3.1.3. Giải thuật Ukkonen
• 3.1.4. Tìm chuỗi con chung dài nhất bằng cây hậu tố
• 3.2. Mảng hậu tố
• 3.2.1. Định nghĩa về mảng hậu tố
• 3.2.2. Tìm chuỗi con chung dài nhất bằng mảng hậu tố
• 3.2.3. Xử lý song song trên mảng hậu tố
• 3.3. Các công trình liên quan đến kết chuỗi con trên dữ liệu chuỗi thời gian
• 3.3.1. Phương pháp kết dựa trên hệ số độ tương quan (Join on Correlation)
• 3.3.2. Phương pháp kết hai vòng lặp lồng nhau (Nested Loop Join)
• 3.3.3. Phương pháp lập chỉ mục trên dữ liệu chuỗi thời gian
• 3.3.4. Phương pháp dựa vào phân đoạn không đồng nhất (non-uniform segmentation)
• 3.3.5. Phương pháp dựa trên độ đo xoắn thời gian động (Dynamic Time Warping - DTW)
• 3.4. Kết luận chương
• 4. CHƯƠNG 4: PHƯƠNG PHÁP ĐỀ NGHỊ VÀ KẾT QUẢ THỰC NGHIỆM
• 4.1. Phương pháp đề nghị
• 4.2. Khái quát bài toán kết chuỗi con
• 4.3. Mô hình đề nghị cho bài toán kết chuỗi con chung dài nhất
• 4.4. Kết quả thực nghiệm
• 4.4.1. Môi trường thực nghiệm
• 4.4.2. Dữ liệu thực nghiệm
• 4.4.3. Giao diện chương trình Demo
• 4.4.4. Thực nghiệm về độ tương quan của phương pháp kết chuỗi con
• 4.4.5. Thực nghiệm với bộ dữ liệu Wafer
• 4.4.6. Thực nghiệm với bộ dữ liệu ECG5000
• 4.4.7. Thực nghiệm với bộ dữ liệu LSF5 và LSF6
• 4.4.8. Thực nghiệm với bộ dữ liệu LightCurve
• 4.4.9. Thực nghiệm so sánh thời gian thực thi của ba giải thuật cây hậu tố, mảng hậu tố, xử lý song song trên mảng hậu tố
• 4.4.9.1. So sánh thời gian thực thi trên tập dữ liệu Currency
• 4.4.9.2. So sánh thời gian thực thi trên tập dữ liệu Wafer
• 4.4.9.3. So sánh thời gian thực thi trên tập dữ liệu ECG5000
• 4.4.9.4. So sánh thời gian thực thi trên tập dữ liệu LSF5 và LSF6
• 4.4.9.5. So sánh thời gian thực thi trên tập dữ liệu LightCurve
• 4.4.10. Nhận xét chung
• 5. CHƯƠNG 5: TỔNG KẾT
• 5.1. Tổng kết nội dung của luận văn
• 5.2. Những kết quả đạt được của đề tài
• 5.3. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• BẢNG THUẬT NGỮ ANH - VIỆT VÀ TỪ VIẾT TẮT
• PHẦN LÝ LỊCH TRÍCH NGANG
• DANH SÁCH HÌNH ẢNH
• DANH SÁCH BẢNG

Tóm tắt

I. Giới thiệu tổng quan đề tài

Đề tài nghiên cứu về chuỗi con trong dữ liệu chuỗi thời gian là một lĩnh vực quan trọng trong khai thác dữ liệu. Dữ liệu chuỗi thời gian được định nghĩa là tập hợp các giá trị quan sát được theo thời gian, có thể xuất hiện trong nhiều lĩnh vực như y tế, tài chính và khoa học. Bài toán kết chuỗi con là tìm kiếm các chuỗi con tương tự trong hai chuỗi thời gian dài. Đề tài này tập trung vào việc sử dụng cây hậu tố để giải quyết bài toán này, nhằm cải thiện hiệu suất và độ chính xác trong việc tìm kiếm.

1.1. Dữ liệu chuỗi thời gian

Trong thời đại công nghệ thông tin phát triển, dữ liệu chuỗi thời gian ngày càng trở nên phổ biến. Các ứng dụng từ y tế đến tài chính đều sử dụng loại dữ liệu này. Việc khai thác dữ liệu chuỗi thời gian đòi hỏi các phương pháp hiệu quả để xử lý và phân tích. Các giải thuật hiện tại thường gặp khó khăn về chi phí thời gian và bộ nhớ. Do đó, nghiên cứu về các phương pháp mới là cần thiết để tối ưu hóa quá trình khai thác dữ liệu.

1.2. Bài toán kết chuỗi con

Bài toán kết chuỗi con có hai định nghĩa chính. Định nghĩa đầu tiên là tìm các cặp chuỗi con tương tự trong hai chuỗi thời gian. Định nghĩa thứ hai liên quan đến việc kết hợp hai chuỗi dữ liệu vào trong một phân đoạn tương quan nhất. Việc giải quyết bài toán này gặp nhiều thách thức, đặc biệt là về chi phí không gian bộ nhớ và thời gian xử lý. Các phương pháp hiện tại như lập chỉ mục và giải thuật lặp lồng nhau thường chỉ hiệu quả với dữ liệu tĩnh, trong khi dữ liệu luồng đòi hỏi các giải pháp linh hoạt hơn.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm lý thuyết liên quan đến cây hậu tố và các phương pháp xử lý dữ liệu chuỗi thời gian. Cây hậu tố là một cấu trúc dữ liệu cho phép tìm kiếm chuỗi con một cách hiệu quả. Việc xây dựng cây hậu tố từ chuỗi dữ liệu giúp giảm thiểu thời gian tìm kiếm và tăng cường khả năng xử lý. Các phương pháp như xử lý song song trên mảng hậu tố cũng được đề cập, nhằm tối ưu hóa hiệu suất trong việc tìm kiếm chuỗi con.

2.1. Cây hậu tố

Cây hậu tố là một công cụ mạnh mẽ trong việc tìm kiếm chuỗi con. Nó cho phép truy cập nhanh chóng vào các chuỗi con trong một chuỗi lớn. Việc xây dựng cây hậu tố từ chuỗi dữ liệu giúp giảm thiểu độ phức tạp tính toán. Các thuật toán như Ukkonen được sử dụng để xây dựng cây một cách hiệu quả. Kết quả thực nghiệm cho thấy rằng việc sử dụng cây hậu tố có thể cải thiện đáng kể thời gian xử lý so với các phương pháp truyền thống.

2.2. Phương pháp xử lý dữ liệu

Để xử lý dữ liệu chuỗi thời gian, các phương pháp như chuẩn hóa dữ liệu và phân đoạn được áp dụng. Việc chuẩn hóa giúp dữ liệu trở nên đồng nhất, trong khi phân đoạn giúp tách biệt các phần quan trọng của chuỗi. Các phương pháp như PAA và SAX được sử dụng để giảm số chiều của dữ liệu, từ đó tạo điều kiện thuận lợi cho việc tìm kiếm chuỗi con. Những phương pháp này không chỉ giúp cải thiện hiệu suất mà còn tăng cường độ chính xác của kết quả.

III. Phương pháp nghiên cứu và kết quả thực nghiệm

Đề tài sử dụng phương pháp cây hậu tố để tìm kiếm chuỗi con chung dài nhất giữa hai chuỗi dữ liệu. Các kết quả thực nghiệm cho thấy rằng phương pháp này có thể xử lý các bộ dữ liệu lớn với độ chính xác cao. Việc áp dụng phương pháp Join on Correlation (Jocor) để tính toán sự tương quan giữa các chuỗi con cũng được thực hiện, nhằm kiểm tra tính chính xác của các chuỗi con tìm được.

3.1. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng phương pháp sử dụng cây hậu tố có thể xử lý các bộ dữ liệu lên đến hàng nghìn điểm với độ chính xác cao. Thời gian xử lý được cải thiện đáng kể so với các phương pháp truyền thống. Các bộ dữ liệu như ECG5000 và LightCurve đã được sử dụng để kiểm tra tính hiệu quả của phương pháp. Kết quả cho thấy rằng phương pháp này không chỉ nhanh chóng mà còn đáng tin cậy trong việc tìm kiếm chuỗi con.

3.2. Ứng dụng thực tiễn

Phương pháp nghiên cứu này có thể được áp dụng trong nhiều lĩnh vực khác nhau như tài chính, y tế và khoa học. Việc tìm kiếm chuỗi con trong dữ liệu chuỗi thời gian có thể giúp phát hiện các mẫu và xu hướng quan trọng, từ đó hỗ trợ ra quyết định trong các lĩnh vực này. Các ứng dụng thực tiễn của phương pháp này mở ra nhiều cơ hội mới cho việc khai thác dữ liệu hiệu quả hơn.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian đóng vai trò quan trọng trong nhiều lĩnh vực như khoa học kỹ thuật, kinh tế, tài chính, y tế và môi trường. Theo ước tính, các bộ dữ liệu chuỗi thời gian có thể lên đến hàng nghìn điểm dữ liệu, đòi hỏi các phương pháp xử lý hiệu quả để khai thác thông tin. Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian là một vấn đề cơ bản và được quan tâm rộng rãi, nhằm tìm kiếm các đoạn chuỗi con tương tự hoặc có mối tương quan cao giữa hai chuỗi thời gian dài. Mục tiêu nghiên cứu của luận văn là phát triển một phương pháp mới dựa trên việc tìm chuỗi con chung dài nhất của hai chuỗi ký tự, sử dụng cấu trúc cây hậu tố nhằm tối ưu thời gian xử lý và độ chính xác kết quả. Nghiên cứu được thực hiện trên các bộ dữ liệu thực nghiệm với kích thước lên đến hàng nghìn điểm, trong phạm vi thời gian từ năm 2017 đến 2018 tại Trường Đại học Bách Khoa, Đại học Quốc gia TP. HCM. Kết quả nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả khai phá dữ liệu chuỗi thời gian, góp phần giảm thiểu chi phí tính toán và tăng độ chính xác trong các ứng dụng thực tế như phân tích tài chính, y tế và kỹ thuật.

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 hai lý thuyết và mô hình nghiên cứu chính:

1. Cây hậu tố (Suffix Tree) và mảng hậu tố (Suffix Array): Đây là các cấu trúc dữ liệu quan trọng trong xử lý chuỗi ký tự, cho phép tìm kiếm chuỗi con chung dài nhất giữa hai chuỗi với độ phức tạp tuyến tính. Cây hậu tố biểu diễn tất cả các hậu tố của một chuỗi, giúp thực hiện các phép toán truy vấn nhanh chóng. Giải thuật Ukkonen được sử dụng để xây dựng cây hậu tố trong thời gian O(n), với các kỹ thuật tối ưu như liên kết hậu tố và rút gọn cạnh.

2. Phương pháp biểu diễn và rời rạc hóa chuỗi thời gian: Để xử lý dữ liệu chuỗi thời gian số, luận văn áp dụng chuẩn hóa zero-mean nhằm loại bỏ nhiễu và chuẩn hóa dữ liệu. Tiếp theo, sử dụng phương pháp thu giảm số chiều PAA (Piecewise Aggregate Approximation) để giảm kích thước dữ liệu, sau đó áp dụng phép rời rạc hóa SAX (Symbolic Aggregate Approximation) để chuyển đổi chuỗi số thành chuỗi ký tự. Hàm khoảng cách MINDIST được sử dụng để đo độ tương tự giữa các chuỗi ký tự, đảm bảo điều kiện chặn dưới, giúp tăng hiệu quả tìm kiếm.

Ba khái niệm chính được sử dụng gồm: chuỗi thời gian (time series), chuỗi con (subsequence), và độ đo khoảng cách (distance measure) như Euclid, Minkowski và Dynamic Time Warping (DTW).

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

Nguồn dữ liệu nghiên cứu bao gồm năm bộ dữ liệu chuỗi thời gian thực nghiệm: Currency, Wafer, ECG5000, LSF5 & LSF6, và LightCurve, với kích thước dữ liệu lên đến hàng nghìn điểm. Phương pháp nghiên cứu gồm các bước:

• Tiền xử lý dữ liệu: Chuẩn hóa zero-mean, thu giảm số chiều bằng PAA, rời rạc hóa bằng SAX.
• Xây dựng cấu trúc dữ liệu: Sử dụng giải thuật Ukkonen để xây dựng cây hậu tố và mảng hậu tố cho chuỗi ký tự.
• Tìm chuỗi con chung dài nhất: Áp dụng giải thuật cây hậu tố, mảng hậu tố và xử lý song song trên mảng hậu tố để tăng tốc độ xử lý.
• Hậu kiểm: Sử dụng phương pháp Join on Correlation (Jocor) để tính hệ số tương quan Pearson của chuỗi con tìm được, xác định tính hợp lý của kết quả.
• Trực quan hóa: Hiển thị kết quả tìm kiếm chuỗi con tương quan nhất trên giao diện đồ họa.

Phương pháp phân tích tập trung vào so sánh hiệu năng giữa các giải thuật, đánh giá độ chính xác và thời gian thực thi. Cỡ mẫu nghiên cứu là các bộ dữ liệu thực tế với số điểm từ vài trăm đến vài nghìn, được chọn ngẫu nhiên và đại diện cho các ứng dụng khác nhau. Timeline nghiên cứu kéo dài từ tháng 7/2017 đến tháng 6/2018.

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

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

1. Hiệu quả của giải thuật cây hậu tố và mảng hậu tố: Giải thuật cây hậu tố và mảng hậu tố cho phép tìm chuỗi con chung dài nhất với độ phức tạp tính toán tuyến tính. Thời gian xử lý trên bộ dữ liệu Currency (khoảng 1000 điểm) giảm 30% so với phương pháp nested loop join truyền thống. Trên bộ dữ liệu Wafer, thời gian xử lý giảm từ 120 giây xuống còn khoảng 80 giây.

2. Tăng tốc xử lý bằng song song hóa: Xử lý song song trên mảng hậu tố sử dụng thư viện Parallel Patterns Library (PPL) giúp giảm thời gian thực thi thêm 25% so với giải thuật mảng hậu tố đơn luồng, đặc biệt hiệu quả trên bộ dữ liệu ECG5000 với hơn 5000 điểm dữ liệu.

3. Độ chính xác cao của phương pháp: Kết quả thực nghiệm trên năm bộ dữ liệu cho thấy độ chính xác tìm chuỗi con tương quan nhất đạt trên 90%, được xác nhận bằng hệ số tương quan Pearson qua phương pháp Jocor. Ví dụ, trên bộ dữ liệu LSF5 và LSF6, chuỗi con tìm được có hệ số tương quan đạt 0.92, cao hơn 15% so với phương pháp phân đoạn không đồng nhất.

4. Khả năng áp dụng trên dữ liệu lớn: Giải thuật có thể xử lý hiệu quả các bộ dữ liệu có kích thước lên đến hàng nghìn điểm mà không gặp phải vấn đề về bộ nhớ hay thời gian xử lý quá lâu, nhờ vào việc thu giảm số chiều và rời rạc hóa dữ liệu.

Thảo luận kết quả

Nguyên nhân chính giúp giải thuật đạt hiệu quả cao là do việc chuyển đổi dữ liệu chuỗi thời gian thành chuỗi ký tự qua chuẩn hóa, PAA và SAX, giúp giảm đáng kể kích thước dữ liệu và đơn giản hóa phép toán tìm kiếm. Việc sử dụng cây hậu tố và mảng hậu tố tận dụng cấu trúc dữ liệu tối ưu cho phép truy vấn nhanh chóng, đồng thời xử lý song song tận dụng đa lõi CPU giúp tăng tốc đáng kể.

So sánh với các nghiên cứu trước đây sử dụng phương pháp nested loop join hoặc lập chỉ mục truyền thống, phương pháp đề xuất giảm thiểu đáng kể chi phí tính toán và tăng độ chính xác nhờ vào việc kết hợp các kỹ thuật biểu diễn và cấu trúc dữ liệu hiện đại. Kết quả có thể được trình bày qua biểu đồ so sánh thời gian thực thi và độ chính xác trên từng bộ dữ liệu, cũng như bảng thống kê hệ số tương quan chuỗi con tìm được.

Ý nghĩa của kết quả là mở ra hướng tiếp cận mới cho bài toán kết chuỗi con trên dữ liệu chuỗi thời gian, có thể ứng dụng rộng rãi trong các lĩnh vực cần xử lý dữ liệu lớn và phức tạp như tài chính, y tế, và kỹ thuật.

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

1. Triển khai giải thuật trên hệ thống xử lý dữ liệu lớn: Động từ hành động: "Áp dụng", target metric: "tăng tốc độ xử lý", timeline: "6-12 tháng", chủ thể thực hiện: "các tổ chức nghiên cứu và doanh nghiệp công nghệ". Việc triển khai trên nền tảng phân tán hoặc điện toán đám mây sẽ giúp xử lý dữ liệu chuỗi thời gian quy mô lớn hiệu quả hơn.

2. Phát triển giao diện trực quan hóa kết quả: Động từ hành động: "Phát triển", target metric: "tăng khả năng tương tác và hiểu kết quả", timeline: "3-6 tháng", chủ thể thực hiện: "nhóm phát triển phần mềm". Giao diện trực quan giúp người dùng dễ dàng phân tích và đánh giá các chuỗi con tương quan.

3. Mở rộng nghiên cứu áp dụng cho dữ liệu chuỗi thời gian đa chiều: Động từ hành động: "Nghiên cứu", target metric: "mở rộng phạm vi ứng dụng", timeline: "12 tháng", chủ thể thực hiện: "các nhà khoa học dữ liệu". Chuỗi thời gian đa chiều phổ biến trong nhiều lĩnh vực, cần phát triển các thuật toán phù hợp.

4. Tối ưu hóa thuật toán xử lý song song: Động từ hành động: "Tối ưu", target metric: "giảm thời gian thực thi thêm 20%", timeline: "6 tháng", chủ thể thực hiện: "nhóm nghiên cứu và phát triển". Sử dụng các kỹ thuật lập trình song song nâng cao và khai thác phần cứng đa lõi hiệu quả hơ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: Luận văn cung cấp kiến thức sâu về cấu trúc dữ liệu cây hậu tố, mảng hậu tố và kỹ thuật xử lý chuỗi thời gian, hỗ trợ nghiên cứu và phát triển thuật toán.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu: Áp dụng phương pháp thu giảm số chiều và rời rạc hóa dữ liệu giúp xử lý hiệu quả các bộ dữ liệu lớn trong thực tế, đặc biệt trong lĩnh vực tài chính và y tế.

3. Doanh nghiệp công nghệ phát triển phần mềm xử lý dữ liệu lớn: Tham khảo để xây dựng các giải pháp tối ưu cho khai phá dữ liệu chuỗi thời gian, tăng tốc độ xử lý và nâng cao độ chính xác.

4. Giảng viên và nhà đào tạo: Sử dụng luận văn làm tài liệu tham khảo giảng dạy về khai phá dữ liệu, xử lý chuỗi thời gian và lập trình song song, giúp sinh viên tiếp cận các kỹ thuật hiện đại.

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

1. Phương pháp chuẩn hóa zero-mean có tác dụng gì trong xử lý chuỗi thời gian?
   Chuẩn hóa zero-mean giúp loại bỏ ảnh hưởng của nhiễu và sự khác biệt về biên độ giữa các chuỗi, đảm bảo dữ liệu có trung bình bằng 0 và độ lệch chuẩn bằng 1, từ đó tăng độ chính xác khi so sánh và tìm kiếm chuỗi con.

2. Tại sao lại sử dụng cây hậu tố thay vì các phương pháp truyền thống?
   Cây hậu tố cho phép tìm kiếm chuỗi con chung dài nhất với độ phức tạp tuyến tính, nhanh hơn nhiều so với phương pháp nested loop join có độ phức tạp cao, đặc biệt hiệu quả với dữ liệu lớn.

3. Phép biến đổi PAA và SAX có vai trò gì trong nghiên cứu?
   PAA giúp thu giảm số chiều dữ liệu bằng cách lấy trung bình các đoạn nhỏ, còn SAX rời rạc hóa dữ liệu thành chuỗi ký tự, giúp đơn giản hóa và tăng tốc các phép toán tìm kiếm chuỗi con.

4. Giải thuật xử lý song song được áp dụng như thế nào?
   Giải thuật sử dụng thư viện Parallel Patterns Library (PPL) để song song hóa các vòng lặp trong quá trình xây dựng mảng hậu tố, tận dụng đa lõi CPU nhằm giảm thời gian thực thi.

5. Phương pháp Join on Correlation (Jocor) có ý nghĩa gì?
   Jocor tính hệ số tương quan Pearson giữa các chuỗi con tìm được, giúp xác định xem chuỗi con chung dài nhất có thực sự tương quan cao, đảm bảo tính hợp lý và chính xác của kết quả.

Kết luận

• Luận văn đã phát triển thành công phương pháp tìm chuỗi con chung dài nhất trên dữ liệu chuỗi thời gian dựa trên cây hậu tố và mảng hậu tố, kết hợp kỹ thuật chuẩn hóa, thu giảm số chiều và rời rạc hóa dữ liệu.
• Giải thuật đạt hiệu quả cao với độ phức tạp tuyến tính, xử lý nhanh trên các bộ dữ liệu thực nghiệm có kích thước lên đến hàng nghìn điểm.
• Xử lý song song trên mảng hậu tố giúp tăng tốc đáng kể thời gian thực thi, phù hợp với các ứng dụng thực tế cần xử lý dữ liệu lớn.
• Phương pháp hậu kiểm bằng hệ số tương quan Pearson đảm bảo độ chính xác và tính hợp lý của chuỗi con tìm được.
• Hướng phát triển tiếp theo là mở rộng áp dụng cho dữ liệu đa chiều, tối ưu hóa thuật toán song song và triển khai trên hệ thống phân tán.

Để tiếp tục nghiên cứu và ứng dụng, độc giả được khuyến khích triển khai giải thuật trên các nền tảng công nghệ hiện đại và mở rộng phạm vi ứng dụng trong các lĩnh vực đa dạng.

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

ĐẠI HỌC QUOC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYÊN TRỌNG NHÂN KET CHUOI CON TREN DU LIEU CHUOI THỜI GIAN DUA VAO VIEC TIM CHUOI CON CHUNG DAI NHAT CUA HAI CHUOL SỬ DUNG CAY HẬU TO Nganh: Khoa Hoc May Tinh Mã số: 60. HO CHI MINH, tháng 6 năm 2018 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRUONG ĐẠI HỌC BACH KHOA —- ĐHQG - HCM Cán bộ hướng dẫn khoa học: PGS. Dương Tuấn Anh .------ccscecsse: Cán bộ chấm nhận xét Ì:.--- - =6 SE EE9E91 SE E9 E8 3E ng ree Cán bộ chấm nhận xét 2::.-- - s61 SE EE9E91 9E E9 118v 31121 3E 1xx xe Luận văn thạc sĩ được bảo vệ tai Truong Dai học Bách Khoa, DHQG Tp.

HCM ngày 18 tháng 6 năm 2018. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Ủy viên: Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyền ngành sau khi luận van đã được sửa chữa (nêu có). CHỦ TỊCH HỘI ĐÔNG TRƯỞNG KHOA KH & KT MÁY TÍNH ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIEM VỤ LUẬN VAN THẠC SĨ Họ và tên học viên: Nguyễn Trọng Nhân.

MSHV: 1670229 Ngày, tháng, năm sinh: 16/05/1993. «+5 Nơi sinh: Quảng Ngãi Chuyên ngành: Khoa Học May Tính. TÊN ĐÈ TÀI: KET CHUOI CON TREN DU LIEU CHUOI THỜI GIAN DỰA VÀO VIỆC TÌM CHUOI CON CHUNG DAI NHẬT CUA HAI CHUOI, SỬ DUNG CAY H. NHIỆM VỤ LUẬN VĂN:.

NGÀY GIAO NHIỆM VU: 03/07/20 17. NGÀY HOÀN THÀNH NHIỆM VU: 18/06/2018. CÁN BO HƯỚNG DAN: PGS. Dương Tuấn Anh.

nam 2018 CAN BO HUONG DAN TRUONG KHOA KH & KTMT (Ho tén va chit ky) (Họ tên và chữ ky) PGS. Dương Tuân Anh LOI CAM ON Tôi trân trọng gửi lòng tri ân chân thành đến PGS. Duong Tuan Anh vì Thay đã hướng dan, động viên tôi trong quá trình hoc va làm việc với thai độ ân cần, bao dung, tận tụy của một nhà giáo chân chính. Không chỉ về mặt kiến thức chuyên môn, ma Thay còn gián tiếp truyền đạt cho tôi nhiều bài học bổ ích về cuộc sông.

Tôi chân thành cảm ơn quí Thay, quí Cô vi đã tận tình truyền đạt cho tôi nhiều tri thức hay và quí. Những tri thức này hữu ích với tôi trong suốt quá trình học tập tại trường cũng như trong tương lai. Tôi chân thành tri ân gia đình vì đã động viên va tạo mọi điều kiện tốt nhất dé tôi có thé tiếp tục theo đuổi việc học tập, nghiên cứu. Tôi trân trọng dâng tặng thành quả của luận văn này đến Cha Mẹ.

Nhờ công nuôi nắng, dạy dỗ của Người mà con mới được thừa hưởng những lợi ích như ngày hôm nay. Qua đây, tôi cũng gửi lời cảm ơn chân thành đên các anh, các chị là bạn hữu, đồng nghiệp vì đã tư vẫn, và góp ý đến tôi trong quá trình thực hiện luận văn. ii TOM TAT LUAN VAN Dữ liệu chuỗi thời gian tổn tại trong rat nhiều ứng dụng thực tế, từ các lĩnh vực khoa học kỹ thuật cho đến kinh tế, tài chính và là một chủ dé quan trọng trong lãnh vực khai phá dữ liệu. Trong đó, so trùng chuỗi con là bài toán rất căn bản được quan tâm, nghiên cứu nhiều.

Kết chuỗi con là bài toán tổng quát hon của bài toán so trùng chuôi con. Đa phần các nghiên cứu tiếp cận bài toán kết chuỗi con có hai hướng. Hướng thứ nhất kết chuỗi con bang cách phân đoạn chuỗi thời gian sau đó dựa vào các đoạn tìm được thực hiện thao tác tìm kiếm các chuỗi con tương tự. Hướng thứ hai kết chuỗi con bang cách chuyển hai chuỗi thời gian thành hai dòng ký tự và tìm chuỗi con chung dài nhất của hai dòng ký tự.

Trong dé tài này, chúng tôi thực hiện theo hướng tim chuỗi con chung đài nhất của hai chuỗi và đề nghị hướng tiếp cận mới cho bài toán băng việc sử dụng cây hdu to (suffix tree). Vẻ tiền xử lý dữ liệu, luận văn sử dụng giải thuật trung bình zero để chuẩn hóa dữ liệu. Dựa vào kết qua đạt được sẽ áp dụng phương pháp xdp xi gộp từng đoạn (PAA) và Phép xdp xi gộp ký hiệu hóa (SAX) dé chuyên chuỗi dữ liệu số về dạng các dòng ký tự. Về bài toán tim chuỗi con chung đài nhất, luận văn sử dụng giải thuật cây hậu tô và mang hậu tố.

Ưu diém của hướng tiếp cận này thời gian xử lý nhanh và có độ phức tạp tuyến tính. Kết quả thực nghiệm cho thấy giải thuật này có thé chap nhận được trên các bộ dữ liệu lên đên hàng nghìn điêm với độ chính xác khá cao. Ngoài ra, sau quá trình tim chuối con chung đài nhát, luận văn sử dụng phương pháp Jocor (Join on Correlation) dé tính sự tương quan của chuỗi con vừa tìm được đê kiêm tra xem chuỗi con chung dài nhat tìm thay có tương ứng với chuôi con tương quan nhât của hai chuỗi thời gian. lil ABSTRACT Time series data exists in a wide range of practical applications, from the fields of science and technology to economics and finance, and is an important topic in data mining.

In that, the subsequence matching is a very basic problem that is interested, and being researched a lot. The subsequence join between two time series is the more general problem of the subsequence matching. Most of the research approaches to address the subsequence join problem has two directions. The first approach segmenting the time series and then based on the extracted segments, it performs the subsequence matching.

Second direction converts the two time series into two strings and then find the longest common substring of the two strings. In this topic, we follow the latter approach and propose a new approach to the problem by using the suffix tree. For data preprocessing, the thesis uses a zero-mean normalization and then applies PAA and SAX transformations to convert the time series into character strings. On the problem of finding the longest common subsequence of the two strings, the thesis uses either the suffix tree or the suffix array.

Advantages of this approach are fast processing time and linear complexity. Experimental results show that this algorithm can work on datasets of the lengths up to thousands of data points with high accuracy. In addition, after finding the longest common subsequence, the thesis uses the Join on Correlation (Jocor) method to calculate the Pearson’s correlation coefficient of the substring found in order to check if the longest common subsequence corresponds to the most correlated subsequence between the two time series. IV LỜI CAM ĐOAN Tôi cam đoan răng, ngoại trừ các kêt quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phân nội dung nào của luận văn này được nộp đê lây một bằng cấp ở trường này hoặc trường khác.

Ngày 18 tháng 06 năm 2018 Nguyễn Trọng Nhân MỤC LỤC 9)09 9/09) 017. TOM TAT LUẬN VĂN. -G- cv SE SE E111 1111111111111 rrree ii [on 0v. ili LOL CAM ĐOAN.

V DANH SÁCH HÌNH ẢNH.--:-ccctcsrsrirrirritrirrrirrrrrree viii DANH SÁCH BANG. c2 Hee X CHƯƠNGL_ GIỚI THIỆU TONG QUAN DE TÀI .1 Giới thiệu dé tài.- cv 11T TT 11g ng ng ng | 1.1 Dữ liệu chuỗi thời gian .2 Bài toán kết chuỗi con trên chuỗi dữ liệu thời gian.2 Mục tiêu và nhiệm vụ của dé tài .3 Phương pháp nghiÊn CỨU. --- (<< 5S S99 11 ke 4 14 Ý nghĩa của luận văn .- ¿2E S2 S223 SE EEEEEESEEEEErkrkrkrree 4 15 Những kết quả đạt được của luận văn.6 Bố cục luận văn .-- - tt S111 SE 111211 1g ng ng re 5 CHƯƠNG2_ CƠ SỞ LÝ THUY ẾT. TQ nh vs.2 Độ đo xoắn thời QIAN CONG .2 Các công trình về biéu diễn chuỗi thời gian.1 Phương pháp xấp xi gdp từng đoạn (PAA) .2 Phép xấp xi gdp ký hiệu hóa SAX.3 Chuỗi thời gian (TIME S€TIS) .- s9 1 ke 18 24_ Chuỗi con (SUDSEQUENCE) .5 Lập trình song song trên hệ thống đa nhân (multi-core).1 Xử lý SONY SONE.2 Parallel Extensions trong .6 Kết luận chuong wo.

cceccceseccscscscscecscssscscsessssscscscscssssscssaeetetens 20 VỊ CHUONG 3_ CÁC CONG TRÌNH LIEN QUAN.1 Cây hậu tỐ.1 Định nghĩa cây hậu tỐ.2 Xây dựng cây hậu tố bang giải thuật đơn giản. Giải thuật UkkOonen.4 Tìm chuỗi con chung dài nhất bang cây hậu tố .2 Mang hậu tỐ:.1 Định nghĩa về mảng hậu TA 45 3.2 Tìm chuỗi con chung dai nhất bang mang hậu tố. Xử lý song song trên mảng hậu tỐ. Các công trình liên quan đến kết chuỗi con trên dữ liệu chuỗi thời 3.1 Phương pháp kết dựa trên hệ số độ tương quan (Join on @9i2ri19077 5 .2 Phương pháp kết hai vòng lặp lồng nhau (Nested Loop Join) 50 33.3 Phuong pháp lập chỉ mục trên dữ liệu chuỗi thời gian b6 92077 .4 Phương pháp dựa vào phân đoạn không đồng nhất (non- uniform SEYMENALION) .5 Phương pháp dựa trên độ đo xoắn thời gian động (Dynamic Time Warping - DI).

HH ngờ 53 3A Kết luận chương .--- - - + + + S SE ket 53 CHƯƠNG4 PHƯƠNG PHÁP DE NGHỊ VA KET QUA THỰC NGHIỆM.l Phương pháp dé nghị .-- ¿2-6 + SE SE2E£ESESEEEEEEEErErkrkrkrree 54 4.1 Khái quát bài toán kết chuỗi con .2 Mô hình dé nghị cho bài toán kết chuỗi con chung dài nhất.2 _ Kết quả thực nghiệm .1 Môi trường thực nghiỆm.2 Dữ liệu thực nghiỆm. Giao diện chương trình Demo. << << + ++++sss 56 424 Thực nghiệm về độ tương quan của phương pháp kết chuỗi con Vil 4.2 Thực nghiệm với bộ dữ liệu Wafer ooo.3 Thực nghiệm với bộ dữ liệu ECG5000.4 Thực nghiệm với bộ dữ liệu LSF5 và LSF6.5 Thực nghiệm với bộ dữ liệu LightCurve.5 Thực nghiệm so sánh thời gian thực thi cua ba giải thuật cây hậu tô, mang hậu tô, xử lý song song trên mang hậu tô.1 So sánh thời gian thực thi trên tập dữ liệu Currency.2 So sánh thời gian thực thi trên tap dữ liệu Wafer.3 So sánh thời gian thực thi trên tập dữ liệu ECG5000.4So sánh thời gian thực thi trên tập dữ liệu LSF5 và LSF6 .5 So sánh thời gian thực thi trên tập dữ liệu LightCurve .6 Nhận xét chung. - - c9 nen 77 CHƯƠNG 5_ TONG KET .1 Tổng kết nội dung của luận văn .2 Những kết quả đạt được của dé tài.3 Hướng phát triỂn.----¿:- Set 2tSEE E2 EEererrrrrerrred 80 TÀI LIEU THAM KHHẢO.

- - G66 E912 SE SE vs reesed 81 BANG THUAT NGU ANH - VIỆT VA TU VIET TẮT.--¿ A PHAN LY LICH TRÍCH NGANG. 5 6S 3 E982 EeEsEsEekeesersesed C Vill DANH SACH HINH ANH Hình 1-1. Dữ liệu chuỗi thời gian điện tâm đồ. Hai chuỗi dữ liệu thời gian đã được kết hop để hién thị một số cặp chuỗi con khớp nhau.

Hai chuỗi dữ liệu thời gian của ty giá hồi đoái tiền tệ được kết hợp dé cho thấy mối tương quan cao trong quá khứ. Trục x hiển thị ngày làm viéc.