PHÁT HIỆN MOTIF BẰNG THUẬT TOÁN SCRIMP++ CẢI TIẾN

Tóm tắt

Motif trên chuỗi thời gian là cặp chuỗi con giống nhau nhất trong một chuỗi thời gian hay các cặp chuỗi giống nhau nhất trong một cơ sở dữ liệu chuỗi thời gian. Khám phá motif trên chuỗi thời gian là bài toán quan trọng trong khai phá dữ liệu chuỗi thời gian. Gần đây, một số thuật toán mới đã được giới thiệu cho bài toán khám phá motif dựa vào vector chứa khoảng cách giữa một chuỗi con với lân cận gần nhất của nó. Các thuật toán này sử dụng kĩ thuật kết hợp việc chuẩn hóa chuỗi thời gian vào trong công thức tính độ đo khoảng cách Euclid khi tính toán ma trận khoảng cách. Phương pháp tiêu biểu cho cách tiếp cận này là thuật toán Scrimp++. Bài báo này giới thiệu một phiên bản cải tiến của thuật toán Scrimp++ cho bài toán khám phá motif nhằm cải thiện thời gian thực thi của thuật toán. Kết quả thực nghiệm cho thấy thuật toán đề xuất thực hiện tốt hơn thuật toán gốc về mặt thời gian nhưng vẫn đảm bảo về độ chính xác.