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.
