Luận Văn Thạc Sĩ Khoa Học Máy Tính: 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 Thời Gian Động

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.

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ự.

Độ đ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.

Độ đ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.

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.

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.

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.

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.