Luận văn thạc sĩ về phát hiện mô típ trong dữ liệu chuỗi thời gian

Khám phá luận văn thạc sĩ về phát hiện mô típ với chiều dài khác nhau trong dữ liệu chuỗi thời gian, ứng dụng trong khoa học máy tính.

• Tác giả: Lê Minh Nhựt
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - Đại học Quốc gia TP.HCM
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Phát hiện mô típ với chiều dài khác nhau trên 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.HCM

Tóm tắt

I. Giới thiệu về mô típ chuỗi thời gian

Mô típ chuỗi thời gian là một khái niệm quan trọng trong lĩnh vực khoa học máy tính. Nó đề cập đến việc tìm kiếm các mẫu lặp lại trong dữ liệu chuỗi thời gian. Việc phát hiện mô típ này không chỉ giúp hiểu rõ hơn về dữ liệu mà còn có thể dự đoán các xu hướng trong tương lai. Trong bối cảnh hiện nay, với sự gia tăng nhanh chóng của dữ liệu, việc phát hiện mô típ trở nên cần thiết hơn bao giờ hết. Các ứng dụng của nó rất đa dạng, từ phân tích tài chính đến y học. Đặc biệt, việc phát hiện mô típ với chiều dài khác nhau là một thách thức lớn, vì nhiều giải thuật hiện tại chỉ có thể phát hiện các mô típ có chiều dài cố định. Điều này dẫn đến việc bỏ lỡ nhiều thông tin quý giá trong dữ liệ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 sinh ra từ nhiều nguồn khác nhau, bao gồm các thí nghiệm khoa học và hoạt động kinh doanh. Việc khai thác dữ liệu này để tìm ra các mô típ có thể giúp các nhà nghiên cứu và doanh nghiệp đưa ra quyết định chính xác hơn. Ví dụ, trong lĩnh vực tài chính, việc phát hiện mô típ có thể giúp dự đoán biến động giá của chứng khoán. Hơn nữa, trong y học, việc phân tích dữ liệu chuỗi thời gian có thể giúp theo dõi diễn biến của bệnh tật. Do đó, việc phát hiện mô típ trong dữ liệu chuỗi thời gian không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn cao.

II. Các phương pháp phát hiện mô típ

Nhiều phương pháp đã được phát triển để phát hiện mô típ trong dữ liệu chuỗi thời gian. Một số phương pháp này bao gồm giải thuật EMMA, giải thuật chiếu ngẫu nhiên và giải thuật Mueen-Keogh. Tuy nhiên, một hạn chế lớn của các phương pháp này là chúng thường yêu cầu chiều dài của mô típ phải được xác định trước. Điều này có thể dẫn đến việc không phát hiện được các mô típ có chiều dài khác nhau, gây ra sự thiếu sót trong phân tích dữ liệu. Để khắc phục vấn đề này, nghiên cứu hiện tại tập trung vào việc phát triển một giải thuật có khả năng phát hiện mô típ mà không cần biết trước chiều dài của chúng. Giải thuật này dựa trên nền tảng của các phương pháp chiếu ngẫu nhiên và ma trận đụng độ, cho phép phát hiện hầu hết các mô típ trong dữ liệu chuỗi thời gian.

2.1. Giải thuật chiếu ngẫu nhiên

Giải thuật chiếu ngẫu nhiên là một trong những phương pháp hiệu quả để phát hiện mô típ trong dữ liệu chuỗi thời gian. Phương pháp này sử dụng các kỹ thuật ngẫu nhiên để giảm thiểu kích thước dữ liệu, từ đó giúp tăng tốc độ xử lý. Bằng cách này, nó có thể phát hiện các mô típ mà không cần biết trước chiều dài của chúng. Điều này rất quan trọng trong bối cảnh dữ liệu lớn, nơi mà việc xử lý dữ liệu một cách nhanh chóng và hiệu quả là rất cần thiết. Giải thuật này đã được thử nghiệm trên nhiều tập dữ liệu khác nhau và cho thấy khả năng phát hiện mô típ với độ chính xác cao.

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

Kết quả thực nghiệm cho thấy giải thuật phát hiện mô típ với chiều dài khác nhau có khả năng phát hiện hầu hết các mô típ trong dữ liệu chuỗi thời gian. Các thử nghiệm được thực hiện trên nhiều tập dữ liệu khác nhau, bao gồm dữ liệu điện tâm đồ và dữ liệu chứng khoán. Kết quả cho thấy giải thuật không chỉ phát hiện được các mô típ có chiều dài khác nhau mà còn có thể nhận diện các thể hiện trong mô típ với chiều dài khác nhau. Thời gian chạy của giải thuật cũng được đánh giá là tương đối nhanh, cho phép ứng dụng trong các tình huống thực tế. Điều này chứng tỏ rằng giải thuật có giá trị thực tiễn cao và có thể được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau.

3.1. So sánh với các giải thuật khác

Khi so sánh với các giải thuật phát hiện mô típ khác, giải thuật mới cho thấy ưu điểm vượt trội trong việc phát hiện các mô típ có chiều dài khác nhau. Các giải thuật truyền thống thường yêu cầu chiều dài mô típ phải được xác định trước, điều này có thể dẫn đến việc bỏ lỡ nhiều thông tin quan trọng. Ngược lại, giải thuật mới cho phép phát hiện các mô típ mà không cần biết trước chiều dài, từ đó mở rộng khả năng phân tích dữ liệu. Kết quả thực nghiệm cho thấy rằng giải thuật mới không chỉ hiệu quả hơn mà còn dễ dàng áp dụng trong thực tế.

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

Luận văn này đã trình bày một giải thuật mới có khả năng phát hiện mô típ với chiều dài khác nhau trong dữ liệu chuỗi thời gian. Giải thuật này không chỉ khắc phục được những hạn chế của các phương pháp hiện tại mà còn mở ra nhiều cơ hội mới trong việc khai thác dữ liệu. Hướng phát triển tiếp theo có thể bao gồm việc cải thiện độ chính xác của giải thuật và mở rộng ứng dụng của nó trong các lĩnh vực khác nhau. Việc phát triển các phương pháp mới để tối ưu hóa quá trình phát hiện mô típ cũng là một hướng nghiên cứu tiềm năng trong tương lai.

4.1. Đề xuất nghiên cứu tiếp theo

Các nghiên cứu tiếp theo có thể tập trung vào việc cải thiện hiệu suất của giải thuật, đặc biệt là trong các tình huống dữ liệu lớn. Việc áp dụng các kỹ thuật học máy để tối ưu hóa quá trình phát hiện mô típ cũng là một hướng đi hứa hẹn. Hơn nữa, việc mở rộng ứng dụng của giải thuật trong các lĩnh vực như y học, tài chính và khoa học xã hội có thể mang lại nhiều lợi ích thiết thực. Điều này không chỉ giúp nâng cao giá trị của nghiên cứu mà còn đóng góp vào sự phát triển của khoa học và công nghệ.

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

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này sẽ trình bày sơ lược về nội dung và mục tiêu của đề tài. Đồng thời chương này cũng nêu lên động cơ nghiên cứu, tầm quan trọng của những ứng dụng trong thực tiễn và hướng giải quyết vấn đề của đề tài.1 Dữ liệu chuỗi thời gian Ngày nay, với sự phát triển không ngừng của khoa học kỹ thuật, lượng dữ liệu được lưu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ …) không ngừng tăng lên. Qua thời gian, lượng dữ liệu này ngày càng phình to ra với tốc độ nhanh chóng. Vấn đề đặt ra cho con người là làm sao để thu được những thông tin hữu ích từ khối dữ liệu khổng lồ này.

Vì lý do đó, vấn đề khai phá dữ liệu để phục vụ nhu cầu nghiên cứu và sử dụng của con người đã trở thành một vấn đề quan trọng và cần thiết. Một trong những loại dữ liệu quan trọng cần được khai phá là dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian được sinh ra từ các thí nghiệm khoa học cũng như hoạt động sản xuất kinh doanh trong đời sống hằng ngày. Một số dạng dữ liệu chuỗi thời gian mà ta có thể bắt gặp trong thực tế như giá của một mã chứng khoán qua các ngày, giá cả của một mặt hàng trên thị trường qua từng ngày, doanh thu hoặc chi phí kinh doanh của công ty qua các thời kỳ, lượng mưa đo đạt được từng ngày, dữ liệu điện tâm đồ…Hình 1-1 minh họa một loại dữ liệu chuỗi thời gian được ghi nhận lại là dữ liệu chứng khoán Việt Nam.

Một cách tổng quát, một dữ liệu chuỗi thời gian là một tập có thứ tự các số thực, trong đó mỗi số thể hiện giá trị tại một thời điểm nào đó. Dữ liệu chuỗi thời gian thường có kích thước rất lớn. Việc khai phá nó để rút trích những thông tin có ích ngày càng trở thành một nhu cầu cần thiết và được nhiều nhà khoa học tham gia nghiên cứu, ứng dụng. Mặc dù dữ liệu chuỗi thời gian là một đề tài hấp dẫn nhưng việc nghiên cứu nó cũng gặp nhiều khó khăn và thách thức như dữ liệu quá lớn, phụ thuộc nhiều vào cách đánh giá độ tương tự, dữ liệu thường không đồng nhất… Lê Minh Nhựt – 10070491 Trang 1 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian Hình 1-1: Dữ liệu chứng khoán Việt Nam được ghi nhận lại.2 Phát hiện mô típ trên dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian tồn tại rất nhiều trong các ứ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, sinh học và y học.

Việc tìm kiếm những chuỗi con truy vấn có xuất hiện trong dữ liệu chuỗi thời gian lớn hơn là một công việc rất cần thiết. Đây là nền tảng cho việc phát triển cao hơn trong khai phá dữ liệu chuỗi thời gian. Trong đó, việc phát hiện sự lặp đi lặp lại nhiều lần của một chuỗi con (còn gọi là mô típ) trong một chuỗi thời gian lớn hơn đã trở thành một nhu cầu thực tế. Hình 1-2 minh họa sự xuất hiện của 3 chuỗi con tương tự nhau trên một dữ liệu chuỗi thời gian.

Một vài ứng dụng thực tế:  Dự đoán giá vàng, tiền tệ hay chứng khoán dựa vào mô hình biến động giá của nó trong quá khứ.  Dự đoán diễn biến của một căn bệnh dựa vào dữ liệu diễn biến của nó trong quá khứ.  Nhận dạng những công ty có kiểu mẫu tăng trưởng giống nhau.  Xác định những chứng khoán có giá biến động theo một kiểu cách giống nhau.

Lê Minh Nhựt – 10070491 Trang 2 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian  Phát hiện vi phạm bản quyền trong âm nhạc bằng cách tìm xem một đoạn nhạc có tương tự với một đoạn nhạc nào trong tập hợp những bản nhạc đã có bản quyền. Hình 1-2: Một chuỗi thời gian có sự xuất hiện của 3 chuỗi con tương tự nhau A,B,C (hình trên). Hình phóng to của 3 chuỗi con A,B,C (hình dưới) (nguồn [5]).3 Mục tiêu và giới hạn của đề tài Vấn đề phát hiện mô típ trong dữ liệu chuỗi thời gian là một vấn đề thú vị và mang tính thực tiễn cao. Nó thúc đẩy nhiều nhà khoa học tham gia nghiên cứu và họ đã đưa ra nhiều công trình nghiên cứu giải quyết được bài toán đặt ra.

Các công trình này đã nêu ra nhiều giải thuật khác nhau (EMMA [5], chiếu ngẫu nhiên [4], Mueen-Keogh [6]…), với cách tiếp cận khác nhau để giải quyết vần đề. Tuy nhiên, một hạn chế phổ biến trong các công trình nghiên cứu đã có là chỉ tập trung phát hiện những mô típ có chiều dài cố định. Điều này có nghĩa là chiều dài của mô típ cần tìm phải được xác định trước để cung cấp cho giải thuật hoạt động. Với cách tiếp cận này, giải thuật chỉ có thể phát hiện ra các mô típ có chiều dài đã định trước Lê Minh Nhựt – 10070491 Trang 3 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian trong chuỗi dữ liệu thời gian.

Chúng không thể phát hiện những mô típ khác có thể có, với chiều dài khác chiều dài được cung cấp. Một hạn chế khác là việc xác định trước chiều dài mô típ trong thực tế rất khó khăn và có thể không chính xác. Nếu chiều dài mô típ được cung cấp quá nhỏ so với thực tế thì sẽ chỉ phát hiện ra những mô típ nhỏ thuộc một mô típ lớn hơn. Nếu chiều dài mô típ được cung cấp quá lớn thì có khả năng giải thuật sẽ không phát hiện được mô típ.

Với những hạn chế của những giải thuật phát hiện mô típ dựa vào chiều dài cố định, một nhu cầu được đặt ra là tìm một giải thuật có thể phát hiện mô típ mà không cần biết trước chiều dài của nó. Đề tài này sẽ xem xét một giải thuật có khả năng khắc phục hạn chế này, nó có thể phát hiện tất cả các mô típ với chiều dài khác nhau trong chuỗi thời gian. Giải thuật được nêu ra bởi Heng Tang và Stephen Liao [7] có khả năng phát hiện mô típ mà không cần biết trước thông tin nào về dữ liệu đang xem xét. Giải thuật dựa vào nền tảng là giải thuật chiếu ngẫu nhiên và ma trận đụng độ của các chuỗi con để giải quyết vần đề.

Trong luận văn này chúng tôi sẽ so sánh kết quả thực nghiệm thu được với giải thuật nhận diện mô típ dựa vào điểm cực trị quan trọng vì đây là giải thuật có thể nhận thấy được các thể hiện không cùng chiều dài trong mô típ và có biên độ dao động khác nhau.4 Tóm lược những kết quả thu được Qua việc nghiên cứu, hiện thực đề tài này và sau đó thử nghiệm trên các tập dữ liệu mẫu, chúng tôi thu được các kết quả sau:  Giải thuật có khả năng phát hiện hầu hết các mô típ có trong dữ liệu chuỗi thời gian được thử nghiệm.  Phát hiện được các mô típ có chiều dài khác nhau, các thể hiện trong mô típ cũng có thể có chiều dài khác nhau. Lê Minh Nhựt – 10070491 Trang 4 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian  Thời gian chạy tương đối nhanh trên các tập dữ liệu vừa và nhỏ (vài chục ngàn điểm). Thời gian chạy chậm trên các tập dữ liệu lớn hoặc có hình thái biến đổi giống nhau xuyên suốt chuỗi thời gian.5 Cấu trúc luận văn Phần còn lại của luận văn được tổ chức theo cấu trúc như sau: Chương 2 trình bày tổng quan về các công trình liên quan đến bài toán phát hiện mô típ trên dữ liệu chuỗi thời gian.

Chương 3 giới thiệu những lý thuyết sẽ được sử dụng để thực hiện đề tài, đồng thời xác định hướng tiếp cận để giải quyết vấn đề của đề tài. Chương 4 tiến hành hiện thực và thực nghiệm giải thuật trên các tập dữ liệu chuỗi thời gian khác nhau. Sau đó, chúng tôi so sánh kết quả thu được với giải thuật nhận diện mô típ dựa vào điểm cực trị quan trọng về khả năng phát hiện mô típ có chiều dài khác nhau, độ chính xác, tốc độ của giải thuật. Chương 5 nêu lên một số kết luận sau khi thực hiện đề tài.

Lê Minh Nhựt – 10070491 Trang 5 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian CHƯƠNG 2: TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ trình bày các khái niệm căn bản và các lý thuyết liên quan đến vấn đề tìm kiếm tương tự và phát hiện mô típ trên dữ liệu chuỗi thời gian. Các khái niệm này bao gồm một số định nghĩa, phương pháp và giải thuật được sử dụng để xử lý chuỗi thời gian. Cuối chương là tổng hợp sơ bộ vài công trình liên quan đến đề tài cùng những ưu điểm và nhược điểm của chúng.1 Các độ đo tương tự Vấn đề quan trọng nhất của bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian là cách tính độ tương tự (thường là khoảng cách) của hai chuỗi con bất kỳ trong tập các chuỗi con. Trong trường hợp hai chuỗi này giống nhau thì khoảng cách này sẽ là 0 và ngược lại càng khác nhau thì khoảng cách sẽ càng lớn.1 Độ đo Euclid Để xác định độ tương tự của hai chuỗi thời gian, nhiều độ đo tương tự đã được sử dụng.

Trong đó, độ đo khoảng cách Euclid thường được sử dụng nhất. Cho hai chuỗi thời gian Q = q1,…,qn và C = c1,…,cn độ đo khoảng cách Euclid giữa hai chuỗi thời gian này được cho bởi công thức: ( , )= ( − ) Hình 2-1: Khoảng cách Euclid giữa hai chuỗi thời gian Q và C (Từ nguồn [5]). Lê Minh Nhựt – 10070491 Trang 6 Phát hiện mô típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian Hình 2-1 thể hiện một cách trực quan phương pháp tính độ tương tự của hai chuỗi thời gian sử dụng độ đo khoảng cách Euclid. Độ đo khoảng cách Euclid cho thấy sự đơn giản, 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 khác như gom cụm, phân lớp và đủ tốt để tính độ tương tự của hai chuỗi thời gian.

Độ đo khoảng cách Euclid cũng có ưu điểm là nó phù hợp với các phương pháp thu giảm số chiều DFT, DWT, PAA, APCA. Độ đo khoảng cách Euclid có nhược điểm là nhạy cảm với nhiễu và không thích hợp khi dữ liệu có đường cơ bản (base line) khác nhau.