Luận văn thạc sĩ khoa học máy tính ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian dùng độ đo xoắn thời gian động

Luận văn thạc sĩ phân tích máy tính ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian dùng độ đo xoắn thời gian, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải

• Tác giả: Nguyễn Quốc Việt
• Người hướng dẫn: PGS.TS Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc Gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian dùng độ đo xoắn thời gian động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Luận văn thạc sĩ này tập trung vào việc ứng dụng nhận dạng motif để hỗ trợ phân lớp dữ liệu chuỗi thời gian sử dụng độ đo xoắn động. Bài toán phân lớp dữ liệu chuỗi thời gian đóng vai trò quan trọng trong lĩnh vực khai phá dữ liệu và machine learning, đặc biệt trong các ứng dụng như tài chính và y học. Nhận dạng motif giúp rút ngắn thời gian huấn luyện và cải thiện hiệu suất của thuật toán phân lớp. Độ đo xoắn động được sử dụng để tính toán độ tương tự giữa các chuỗi thời gian, giúp tăng độ chính xác trong phân loại dữ liệu.

1.1 Phát biểu vấn đề

Dữ liệu chuỗi thời gian là tập hợp các giá trị được ghi lại theo thời gian, thường có kích thước lớn và phức tạp. Việc phân lớp dữ liệu chuỗi thời gian gặp nhiều thách thức do khối lượng dữ liệu lớn, sự phụ thuộc vào yếu tố chủ quan và tính không đồng nhất của dữ liệu. Nhận dạng motif được đề xuất như một giải pháp để giảm thiểu thời gian tính toán và cải thiện hiệu suất của thuật toán phân lớp. Độ đo xoắn động được sử dụng để đo lường độ tương tự giữa các chuỗi thời gian, giúp tăng độ chính xác trong phân loại dữ liệu.

1.2 Mục tiêu và giới hạn đề tài

Mục tiêu chính của luận văn thạc sĩ này là nghiên cứu và ứng dụng nhận dạng motif để cải tiến thuật toán phân lớp dữ liệu chuỗi thời gian sử dụng độ đo xoắn động. Đề tài tập trung vào việc phát triển một thuật toán phân lớp có thời gian thực thi tùy chọn, giúp đưa ra kết quả phân lớp trong thời gian ngắn với độ chính xác chấp nhận được. Giới hạn của đề tài là chỉ tập trung vào phân lớp dữ liệu chuỗi thời gian và sử dụng độ đo xoắn động làm phương pháp chính để tính toán độ tương tự.

II. Cơ sở lý thuyết

Chương này trình bày các lý thuyết nền tảng liên quan đến phân lớp dữ liệu chuỗi thời gian, bao gồm độ đo khoảng cách, độ đo xoắn động, và thuật toán phân lớp k láng giềng gần nhất. Độ đo khoảng cách được sử dụng để đo lường sự khác biệt giữa các chuỗi thời gian, trong khi độ đo xoắn động giúp xử lý sự lệch pha trong dữ liệu. Thuật toán phân lớp k láng giềng gần nhất là phương pháp phân lớp phổ biến dựa trên độ tương tự giữa các mẫu dữ liệu.

2.1 Độ đo khoảng cách

Độ đo khoảng cách là công cụ quan trọng trong phân tích dữ liệu chuỗi thời gian. Các độ đo phổ biến bao gồm khoảng cách Euclid và khoảng cách Minkowski. Khoảng cách Euclid được sử dụng để đo lường sự khác biệt giữa hai chuỗi thời gian có cùng độ dài, trong khi khoảng cách Minkowski là một tổng quát hóa của khoảng cách Euclid. Tuy nhiên, các độ đo này không xử lý được sự lệch pha trong dữ liệu, dẫn đến nhu cầu sử dụng độ đo xoắn động.

2.2 Độ đo xoắn động

Độ đo xoắn động (Dynamic Time Warping - DTW) là phương pháp đo lường độ tương tự giữa hai chuỗi thời gian có độ dài khác nhau. DTW cho phép xử lý sự lệch pha bằng cách tìm ra đường dẫn tối ưu giữa hai chuỗi. Phương pháp này được sử dụng rộng rãi trong phân tích chuỗi thời gian và phân loại dữ liệu. Tuy nhiên, DTW có chi phí tính toán cao, dẫn đến nhu cầu sử dụng các kỹ thuật tối ưu hóa như chặn dưới LB_Keogh.

III. Các công trình liên quan

Chương này trình bày các công trình nghiên cứu liên quan đến nhận dạng motif, phân lớp dữ liệu chuỗi thời gian, và độ đo xoắn động. Các công trình này bao gồm các phương pháp phân tích motif, thuật toán phân lớp, và các kỹ thuật tối ưu hóa trong tính toán độ tương tự. Nhận dạng motif được sử dụng để giảm thiểu thời gian tính toán trong phân lớp dữ liệu chuỗi thời gian, trong khi các kỹ thuật như chặn dưới LB_Keogh giúp cải thiện hiệu suất của độ đo xoắn động.

3.1 Nhận dạng motif

Nhận dạng motif là quá trình tìm kiếm các mẫu con lặp lại trong dữ liệu chuỗi thời gian. Các phương pháp phổ biến bao gồm giải thuật Brute-force, phương pháp chiếu ngẫu nhiên, và giải thuật MK cải tiến. Nhận dạng motif giúp giảm thiểu thời gian tính toán trong phân lớp dữ liệu chuỗi thời gian bằng cách sử dụng các mẫu đại diện thay vì toàn bộ chuỗi dữ liệu. Phương pháp này đặc biệt hữu ích trong các ứng dụng yêu cầu thời gian thực thi ngắn.

3.2 Thuật toán phân lớp

Thuật toán phân lớp được sử dụng trong đề tài là thuật toán k láng giềng gần nhất (k-NN). Phương pháp này dựa trên độ tương tự giữa các mẫu dữ liệu để phân loại. Thuật toán phân lớp có thời gian thực thi tùy chọn được đề xuất để đưa ra kết quả phân lớp trong thời gian ngắn với độ chính xác chấp nhận được. Phương pháp này kết hợp nhận dạng motif và độ đo xoắn động để cải thiện hiệu suất phân lớp.

IV. Hiện thực và thử nghiệm

Chương này trình bày quá trình hiện thực và thử nghiệm thuật toán phân lớp dữ liệu chuỗi thời gian sử dụng nhận dạng motif và độ đo xoắn động. Hệ thống được chia thành hai giai đoạn chính: huấn luyện và phân lớp. Giai đoạn huấn luyện tập trung vào việc sắp xếp tập dữ liệu dựa trên motif, trong khi giai đoạn phân lớp sử dụng tập dữ liệu đã sắp xếp để phân loại các chuỗi thời gian mới. Kết quả thử nghiệm cho thấy việc sử dụng nhận dạng motif giúp cải thiện đáng kể thời gian thực thi và độ chính xác của thuật toán phân lớp.

4.1 Giai đoạn huấn luyện

Giai đoạn huấn luyện bao gồm việc sắp xếp tập dữ liệu dựa trên motif của mỗi chuỗi thời gian. Giải thuật NN_LBKeogh được sử dụng để tính toán độ tương tự giữa các chuỗi, kết hợp với chặn dưới LB_Keogh để tối ưu hóa thời gian tính toán. Kết quả thử nghiệm cho thấy việc sử dụng nhận dạng motif giúp giảm thiểu thời gian huấn luyện mà vẫn đảm bảo độ chính xác cao.

4.2 Giai đoạn phân lớp

Giai đoạn phân lớp sử dụng tập dữ liệu đã sắp xếp để phân loại các chuỗi thời gian mới. Thuật toán phân lớp có thời gian thực thi tùy chọn được áp dụng để đưa ra kết quả trong thời gian ngắn. Kết quả thử nghiệm trên các tập dữ liệu TwoPat và Clustered cho thấy việc sử dụng nhận dạng motif giúp cải thiện đáng kể độ chính xác và thời gian thực thi của thuật toán phân lớp.

V. Kết luận

Luận văn thạc sĩ này đã thành công trong việc ứng dụng nhận dạng motif để cải tiến thuật toán phân lớp dữ liệu chuỗi thời gian sử dụng độ đo xoắn động. Kết quả thử nghiệm cho thấy việc sử dụng nhận dạng motif giúp giảm thiểu thời gian tính toán và cải thiện độ chính xác của thuật toán phân lớp. Các hướng phát triển trong tương lai bao gồm việc áp dụng phương pháp này vào các lĩnh vực khác như phân tích tài chính và y học, cũng như nghiên cứu các kỹ thuật tối ưu hóa mới để cải thiện hiệu suất của thuật toán phân lớp.

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

CHƯƠNG 1: GIỚI THIỆU 1. Phát biểu vấn đề Chuỗi dữ liệu thời gian hay chuỗi thời gian là sự quan sát các dữ liệu theo thời gian tuần tự. Đối với loại dữ liệu này, cấu trúc dữ liệu có thể là hai hay nhiều chiều trong đó có chiều thời gian, tức là dữ liệu được theo dõi và ghi lại tại một thời điểm nhất định. Tuy nhiên trong hầu hết các ứng dụng thực tế, dữ liệu được đo cách nhau trong một khoảng thời gian cố định nên để đơn giản hóa quá trình lưu trữ cũng như độ phức tạp của dữ liệu, người ta chỉ lưu lại thứ tự các giá trị dữ liệu theo một trình tự thời gian nhất định có dạng X=<x1, x2, …xn> trong đó xi là dữ liệu được đo ở thời điểm thứ i.

Hình 1-1 Đường biễu diễn dữ liệu chuỗi thời gian. Trong các ứng dụng thực tế, có rất nhiều loại dữ liệu chuỗi thời gian như sự theo dõi biến đổi giá của chứng khoán, dữ liệu đo điện tâm đồ, dữ liệu theo dõi mực nước sông hay là sự ghi lại việc truy cập các trang web của người dùng. Thông thường, các loại dữ liệu chuỗi thời gian này là rất lớn, được đo và lưu trữ lại trong một khoảng thời gian dài cho nên việc lưu trữ và khai phá dữ liệu này thường tốn kém chi phí thời gian. Do đó việc sử dụng các công cụ khai phá dữ liệu này được áp dụng trên nền máy tính đã thu hút sự quan tâm, nghiên cứu và ứng dụng trong rất nhiều các Nguyễn Quốc Việt 1 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian lĩnh vực trong những năm gần đây.

Một số vấn đề khi nghiên cứu chuỗi thời gian:  Khối lượng dữ liệu Một trong những đặc trưng của chuỗi thời gian là dữ liệu rất lớn. Ví dụ khi đo đạc dữ liệu điện tâm đồ trong 1 giờ khoảng 1 Gigabyte. Đây là một trong những vấn đề thách thức trong quá trình phân tích, tính toán và xử lý dữ liệu chuỗi thời gian trong việc tạo ra kết quả được chính xác trong thời gian hợp lý.  Phụ thuộc yếu tố chủ quan Trong thực tế, các kết quả dữ liệu chuỗi thời gian thu được chịu ảnh hưởng yếu tố chủ quan của người đo dữ liệu, điều kiện và các công cụ đo…  Dữ liệu không đồng nhất Quá trình thu thập dữ liệu chuỗi thời gian được đo trên những định dạng khác nhau, số lượng và tần số lấy mẫu không đồng nhất cũng ảnh hưởng đến tính toàn vẹn của dữ liệu.

Thêm vào đó quá trình đo đạc không chính xác do nhiễu, thiếu một vài giá trị hay dữ liệu không sạch. Tập hợp dữ liệu chuỗi thời gian liên quan đến một lĩnh vực hoặc một bài toán ứng dụng thường có kích thước rất lớn. Tuy nhiên, tập hợp dữ liệu này thường có mối liên hệ chặt chẽ với nhau. Dựa trên những mối liên hệ đó, người ta thường thống kê và phân loại dữ liệu thành một số lớp với một số đặc trưng nhất định.

Ví dụ, dữ liệu giá chứng khoán có thể phân loại thành các lớp: ổn định, tăng trưởng đều, không ổn định, … Nhu cầu đặt ra là dùng dữ liệu thống kê trong quá khứ để phân loại dữ liệu hiện tại hoặc tương lai. Việc phân loại này có ý nghĩa rất lớn trong nhiều lĩnh vực như: dự đoán tình trạng giá một chứng khoán, dự đoán kiểu thời tiết, … Hình 1-2 minh họa cơ Nguyễn Quốc Việt 2 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian sở dữ liệu thống kê có hai lớp dữ liệu và yêu cầu phân loại mẫu dữ liệu O thuộc lớp nào trong hai lớp đó. Mẫu dữ liệu O Hình 1-2 Bài toán phân lớp dữ liệu chuỗi thời gian. Bài toán phân lớp (classification) dữ liệu chuỗi thời gian được đặt ra để giải quyết vấn đề trên.

Phân lớp là quá trình học có giám sát bao gồm hai giai đoạn: huấn luyện và kiểm tra. Giai đoạn huấn luyện sẽ thực hiện việc học dựa trên tập huấn luyện. Giai đoạn kiểm tra sẽ thực hiện kiểm tra kết quả phân lớp cho một tập kiểm thử. Ngoài ra, có nhiều bài toán trên thực tế đòi hỏi chúng ta phải phân lớp khác nhau dựa trên tài nguyên tính toán được cấp phát.

Ví dụ, bài toán yêu cầu phải phân lớp tín hiệu trên đường truyền internet để xác định xem đó có phải là tín hiệu bất thường hay không, và chỉ có giới hạn trong khoảng thời gian nhất định để ta đua ra đáp án phân lớp. Như vậy ta sẽ không thể đợi giải thuật chạy xong hoàn toàn để kết luận, mà sẽ phải đưa ra kết luận trong khoảng thời gian tùy chọn với một mức độ chính xác có thể chấp nhận được, khi đó một giải thuật phân lớp có thời gian thực thi tùy chọn là rất cần thiết. Tuy nhiên, khi áp dụng phân lớp trên chuỗi thời gian ta thường gặp phải nhược điểm sau: dữ liệu chuỗi thời gian có đặc điểm là rất lớn nên việc phân lớp sẽ rất tốn chi phí thời gian và tài nguyên. Để khắc phục nhược điểm trên, chúng ta có thể vận dụng nhận dạng motif trên dữ liệu chuỗi thời gian để cải tiến giải thuật phân lớp dữ Nguyễn Quốc Việt 3 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian liệu chuỗi thời gian có thời gian thực thi tùy chọn giúp giải thuật thực thi hữu hiệu hơn.

Mục tiêu và giới hạn đề 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 các giải thuật nhận dạng motif trên dữ liệu chuỗi thời gian 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 nhận dạng các motif đặc trưng cho dữ liệu chuỗi thời gian và phân lớp dựa trên các motif đại diện này sẽ giúp quá trình phân lớp nhanh hơn.  Ứng dụng việc nhận dạng motif để cải tiến giải thuật phân lớp dữ liệu chuỗi thời gian có thời gian thực thi tùy chọn để làm cho giải thuật này trở nên hữu hiệu hơn. Sau khi nhận dạng motif đại diện chuỗi thời gian, ta xác định thứ hạng (rank) của các dữ liệu chuỗi thời gian dựa trên motíp đại diện.

Sau đó chúng ta áp dụng giải thuật phân lớp có thời gian thực thi tùy chọn (anytime classification algorithm) để phân lớp tập dữ liệu chuỗi thời gian này dựa vào thứ hạng (rank) các dữ liệu chuỗi thời gian đã tính trước đó. Tóm lược kết quả đạt được Với những yêu cầu của đề tài, sau thời gian nghiên cứu và hiện thực, chúng tôi đã xây dựng hệ thống phân lớp dữ liệu chuỗi thời gian. Hệ thống này gồm hai thành phần chính: Huấn luyện và Phân lớp. Thành phần Huấn luyện cho phép người dùng nhập vào một tập huấn luyện gồm m chuỗi thời gian có chiều dài bằng nhau.

Thành phần Huấn luyện sẽ thực hiện việc sắp xếp tập huấn luyện. Thành phần phân lớp sẽ cho phép người dùng nhập vào một chuỗi thời gian O, hệ thống sẽ sử dụng tập huấn luyện đã được sắp xếp để cho biết kết quả dự đoán lớp của O. Nguyễn Quốc Việt 4 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian Thành phần huấn luyện làm nhiệm vụ sắp xếp tập huấn luyện. Việc sắp xếp này chia làm hai giai đoạn: giai đoạn tìm kiếm motif cho mỗi thể hiện trong tập huấn luyện và giai đoạn sắp xếp tập huấn luyện dựa trên motif của mỗi thể hiện trong tập huấn luyện.

Để phát hiện motif chương trình sử dụng giải thuật nhận diện motif trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng. Để tính khoảng cách xoắn thời gian động của tất cả các cặp chuỗi, chương trình áp dụng kỹ thuật tính chặn dưới LB_Keogh để cải thiện thời gian thực thi. Thành phần phân lớp tìm chuỗi gần nhất của chuỗi mục tiêu O trong tập huấn luyện. Chương trình cũng áp dụng kỹ thuật tính chặn dưới trên để cải thiện thời gian thực thi.

Dựa trên chương trình đã hiện thực, đề tài tiến hành thực nghiệm trên hai tập dữ liệu mẫu và so sánh kết quả khi phân lớp không sử dụng thông tin motif và khi có sử dụng thông tin motif của các thể hiện trong tập huấn luyện trên cả hai giai đoạn huấn luyện và phân lớp: - Giai đoạn huấn luyện, đề tài so sánh thời gian thực thi quá trình sắp xếp tập huấn luyện khi không sử dụng thông tin motif và khi có sử dụng thông tin motif. - Giai đoạn phân lớp, đề tài so sánh độ chính xác của giải thuật phân lớp khi sử dụng motif và khi không sử dụng motif. Như vậy, hệ thống hiện thực sẽ được trình bày trong các chương sau đã đáp ứng được những yêu cầu và nhiệm vụ của đề tài. Cấu trúc của luận văn Đề cương được chia làm 3 phần chính: Chương 2 : Cơ sở lý thuyết Nguyễn Quốc Việt 5 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian Giới thiệu một số lý thuyết nền tảng được sử dụng trong đề tài bao gồm hai độ đo khoảng cách được sử dụng trong việc tìm khoảng cách trong miền dữ liệu chuỗi thời gian là khoảng cách Euclid và khoảng cách xoắn thời gian động (dynamic time warping).

Chương này cũng sẽ giới thiệu giải thuật phân lớp được sử dụng chính trong đề tài là giải thuật phân lớp k Láng giềng gần nhất (k-Nearest-Neighbor). Chương 3 : Các công trình nghiên cứu liên quan Chương này sẽ trình bày các công trình có liên quan đến đề tài. Các công trình này được trình bày trong bốn mục liên quan đến bốn chủ đề chính: ràng buộc đối với đường xoắn cho khoảng cách dynamic time warping (DTW), các kỹ thuật tăng tốc trong việc tính DTW, giải thuật phân lớp có thời gian thực thi tùy chọn và giải thuật tìm kiếm Motif trên dữ liệu chuỗi thời gian. Chương 4 : Giải quyết vấn đề và thực nghiệm Chương này tập trung vào cải thiện thời gian thực thi của giải thuật phân lớp có thời gian thực thi tùy chọn bằng cách sử dụng thông tin motif của chuỗi thời gian.

Kế tiếp trình bày kết quả thực nghiệm trên hai tập dữ liệu TwoPat và Clustered. Chương 5 : Kết luận Trình bày một số kết luận sau khi thực hiện đề tài. Nguyễn Quốc Việt 6 Ứng dụng nhận dạng motif hỗ trợ phân lớp dữ liệu chuỗi thời gian CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Để giải quyết bài toán phân lớp dữ liệu chuỗi thời gian, đề tài này sử dụng một số lý thuyết từ các lĩnh vực khác nhau. Do đó, chương này sẽ trình bày những điểm cơ bản của các lý thuyết đó.