Luận văn thạc sĩ: Nhận diện motif trên dữ liệu chuỗi thời gian qua điểm cực trị quan trọng

Khám phá luận văn thạc sĩ về nhận diện motif trong dữ liệu chuỗi thời gian, ứng dụng điểm cực trị quan trọng trong khoa học máy tính.

• Tác giả: Huỳnh Nguyễn Tín
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đạ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: Nhận diện motif trong chuỗi thời gian dựa vào điểm cực trị quan trọng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. HCM

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• DANH MỤC CÁC HÌNH
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Nhận diện Motif trong dữ liệu chuỗi thời gian
• 1.3. Mục tiêu và giới hạn của đề tài
• 1.4. Tóm lược những kết quả thu được
• 1.5. Cấu trúc luận văn
• 2. CHƯƠNG 2: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Độ đo tương tự
• 2.1.1. Độ đo Minkowski
• 2.2. Độ đo xoắn thời gian động
• 2.3. Các phương pháp thu giảm số chiều
• 2.3.1. Phương pháp không thích nghi dữ liệu
• 2.3.2. Phương pháp thích nghi dữ liệu
• 2.4. Rời rạc hóa dữ liệu bằng phương pháp xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate approximation - SAX)
• 2.5. Nhận diện mẫu lặp thường xuyên (motif) cho các dữ liệu chuỗi thời gian
• 2.6. Nhận diện motif dựa vào phương pháp chiếu ngẫu nhiên (Random Projection Algorithm)
• 2.7. Giải thuật nhận diện motif MK
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 3.1. Điểm cực trị quan trọng (Important Extreme Points)
• 3.2. Phương pháp nhận diện motif dựa vào Điểm Quan Trọng
• 3.2.1. Tìm ứng viên Motif
• 3.2.2. Giải thuật gom cụm phân cấp theo hướng từ dưới lên (Hierarchical Bottom-Up Algorithm)
• 3.3. Giải thuật gom cụm K-Means
• 4. CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Cải tiến giải thuật bằng phương pháp biến hình vị tự trên các motif ứng viên và công thức tính độ tương tự loại trừ độ lệch biên độ
• 4.1.1. Khái niệm về phép biến hình vị tự
• 4.1.2. Lấy mẫu các ứng viên motif bằng phép vị tự
• 4.2. Mô hình hiện thực các phương pháp
• 4.2.1. Mô hình nhận diện Motif dùng phép chiếu ngẫu nhiên
• 4.2.2. Mô hình giải thuật phân cấp từ dưới lên kết hợp với phương pháp tính độ tương tự dùng nội suy spline
• 4.2.3. Mô hình giải thuật HAC hoặc K-Means kết hợp với phương pháp tính độ tương tự được cải tiến
• 4.3. Kết quả thực nghiệm của các giải thuật
• 4.3.1. Dữ liệu ECG (Điện tâm đồ) với kích thước 7900 điểm
• 4.3.2. Dữ liệu Memory với kích thước 7000 điểm
• 4.3.3. Dữ liệu Power với kích thước 35000 điểm
• 4.3.4. Dữ liệu ECG với kích thước 140 000 điểm
• 4.4. Bảng tổng kết và nhận xét các kết quả thực nghiệm thu được trên các tập dữ liệu khác nhau
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.2. Những đóng góp của đề tài
• 5.3. Hướng phát triển của đề tài

Tóm tắt

I. Giới thiệu về nhận diện motif

Nhận diện motif trong chuỗi thời gian là một kỹ thuật quan trọng trong khai phá dữ liệu. Mục tiêu chính là tìm ra các chuỗi con tương tự nhau, từ đó nhận diện các đặc trưng của dữ liệu. Nhận diện motif giúp phân tích và đánh giá các mẫu lặp lại trong dữ liệu, điều này rất hữu ích trong nhiều lĩnh vực như tài chính, y tế và khoa học. Các phương pháp hiện có như Brute-Force và Random Projection thường gặp khó khăn khi xử lý dữ liệu lớn. Do đó, việc phát triển các phương pháp mới là cần thiết để cải thiện hiệu suất và độ chính xác trong việc nhận diện motif.

1.1. Tầm quan trọng của chuỗi thời gian

Chuỗi thời gian là tập hợp các quan sát được ghi lại theo thời gian. Chúng có thể là dữ liệu tài chính, dữ liệu y tế hoặc bất kỳ loại dữ liệu nào có tính chất tuần tự. Chuỗi thời gian thường rất lớn và phức tạp, đòi hỏi các phương pháp phân tích hiệu quả. Việc nhận diện motif trong chuỗi thời gian không chỉ giúp phát hiện các mẫu lặp lại mà còn hỗ trợ trong việc dự đoán và ra quyết định. Các ứng dụng thực tế của nhận diện motif bao gồm phân tích xu hướng thị trường, theo dõi sức khỏe bệnh nhân và tối ưu hóa quy trình sản xuất.

II. Phương pháp nhận diện motif dựa vào điểm cực trị

Phương pháp nhận diện motif dựa vào điểm cực trị quan trọng (Important Extreme Points) là một cách tiếp cận mới nhằm cải thiện độ chính xác và tốc độ của quá trình nhận diện. Bằng cách xác định các điểm cực trị trong chuỗi dữ liệu, các ứng viên motif được chọn ra và gom cụm bằng các thuật toán như K-Means hoặc phân cấp từ dưới lên. Phương pháp này giúp giảm thiểu thời gian xử lý và tăng cường khả năng phát hiện các motif có chiều dài và biên độ khác nhau. Điểm cực trị đóng vai trò quan trọng trong việc xác định các mẫu lặp lại, từ đó nâng cao hiệu quả của quá trình phân tích.

2.1. Cải tiến thuật toán EP_C

Thuật toán EP_C (Extreme Point Clustering) được đề xuất bởi Gruber và các cộng sự vào năm 2006. Thuật toán này tập trung vào việc gom cụm các ứng viên motif dựa trên các điểm cực trị. Việc cải tiến thuật toán này giúp tăng cường khả năng nhận diện các motif mà các phương pháp trước đó không thể phát hiện. Kỹ thuật này không chỉ giúp giảm thiểu độ phức tạp tính toán mà còn cải thiện độ chính xác của kết quả. Phương pháp phân tích này cho phép xử lý các chuỗi dữ liệu lớn một cách hiệu quả, từ đó mở rộng khả năng ứng dụng trong nhiều lĩnh vực khác nhau.

III. Kết quả thực nghiệm và ứng dụng

Kết quả thực nghiệm cho thấy phương pháp nhận diện motif dựa vào điểm cực trị cho thời gian chạy nhanh hơn và độ chính xác cao hơn so với các phương pháp truyền thống như Random Projection. Các thử nghiệm trên dữ liệu ECG, dữ liệu Memory và dữ liệu Power cho thấy khả năng nhận diện các motif không cùng chiều dài và biên độ khác nhau. Điều này chứng tỏ rằng phương pháp này có thể áp dụng rộng rãi trong các lĩnh vực như y tế, tài chính và phân tích dữ liệu lớn. Kết quả thực nghiệm không chỉ khẳng định tính khả thi của phương pháp mà còn mở ra hướng đi mới cho nghiên cứu trong lĩnh vực khai phá dữ liệu chuỗi thời gian.

3.1. Ứng dụng trong thực tiễn

Phương pháp nhận diện motif có thể được ứng dụng trong nhiều lĩnh vực khác nhau. Trong y tế, nó giúp theo dõi và phân tích các mẫu điện tâm đồ, từ đó phát hiện sớm các vấn đề sức khỏe. Trong tài chính, việc nhận diện các mẫu lặp lại trong dữ liệu giá cổ phiếu có thể hỗ trợ các nhà đầu tư đưa ra quyết định chính xác hơn. Ngoài ra, trong lĩnh vực sản xuất, việc phân tích chuỗi thời gian giúp tối ưu hóa quy trình và giảm thiểu lãng phí. Giá trị thực tiễn của phương pháp này không chỉ dừng lại ở việc nhận diện mà còn mở rộng ra việc dự đoán và ra quyết định dựa trên dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên số hóa, khối lượng dữ liệu chuỗi thời gian tăng trưởng theo cấp số nhân trên nhiều lĩnh vực trọng yếu. Đơn cử, việc theo dõi điện tâm đồ liên tục trong 1 giờ có thể tạo ra xấp xỉ 1 Gigabyte dữ liệu, trong khi các hệ thống giám sát công nghiệp ghi nhận hàng triệu điểm đo mỗi ngày. Khai phá dữ liệu chuỗi thời gian, đặc biệt là bài toán nhận diện các mẫu lặp thường xuyên (motif), đóng vai trò quyết định trong việc phát hiện quy luật, chẩn đoán sớm bất thường và nén dữ liệu. Tuy nhiên, các giải thuật truyền thống như duyệt toàn lực (Brute-Force), thuật toán MK hay phương pháp Chiếu ngẫu nhiên (Random Projection) bộc lộ hạn chế lớn: chi phí tính toán cao đối với tập dữ liệu quy mô lớn và không thể nhận diện được các motif có chiều dài hoặc biên độ dao động không đồng nhất.

Mục tiêu trọng tâm của nghiên cứu là xây dựng và hoàn thiện giải pháp nhận diện motif chuỗi thời gian hiệu quả dựa trên việc trích lược điểm cực trị quan trọng kết hợp thuật toán gom cụm phân cấp và K-Means. Đề tài được thực hiện bởi tác giả Huỳnh Nguyễn Tín dưới sự hướng dẫn của Phó Giáo sư Tiến sĩ Dương Tuấn Anh tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh, hoàn thành vào tháng 07 năm 2012. Nghiên cứu thực nghiệm trên 4 tập dữ liệu chuẩn bao gồm y tế (ECG với 7.900 điểm và 140.000 điểm), giám sát hệ thống (Memory với 6.800 điểm) và năng lượng (Power với 35.000 điểm). Đóng góp của luận văn thể hiện qua việc đạt tỷ lệ nén dữ liệu từ 91% đến 94%, đồng thời tối ưu hóa thời gian thực thi và cho phép phát hiện chính xác các thể hiện motif đa tỷ lệ, loại bỏ hoàn toàn độ lệch biên độ dao động.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự tích hợp của các trụ cột lý thuyết vững chắc trong lĩnh vực khai phá dữ liệu chuỗi thời gian:

• Lý thuyết biểu diễn và thu giảm số chiều chuỗi thời gian: Dữ liệu chuỗi thời gian gốc có $n$ chiều được chuyển đổi về không gian $k$ chiều thông qua các kỹ thuật thích nghi và không thích nghi dữ liệu, tiêu biểu như xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA), biến đổi Fourier rời rạc (DFT), biến đổi Wavelet rời rạc (DWT), xấp xỉ tuyến tính từng đoạn (PLA) và xấp xỉ hằng số từng đoạn thích nghi (APCA).
• Lý thuyết rời rạc hóa ký hiệu: Phương pháp xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate Approximation - SAX) của tác giả J. Lin và cộng sự (2003) được sử dụng nhằm biến đổi chuỗi dữ liệu liên tục thành chuỗi ký tự rời rạc theo phân phối chuẩn Gauss.
• Lý thuyết điểm cực trị quan trọng (Important Extreme Points - IEP): Dựa trên công trình của Kevin B. Pratt và Eugene Fink (2002), kỹ thuật trích xuất các điểm cực đại và cực tiểu then chốt theo hệ số tỷ lệ $R$, giúp lọc bỏ các dao động nhiễu nhỏ và nén chiều dài dữ liệu với thời gian tuyến tính $O(n)$.
• Mô hình gom cụm nhận diện Motif (EP_C): Dựa trên khung nền tảng của Gruber và cộng sự (2006), các ứng viên motif được xác định giữa các cặp điểm cực trị kế tiếp và gom cụm bằng thuật toán phân cấp từ dưới lên (Hierarchical Agglomerative Clustering - HAC) hoặc K-Means.
• Khái niệm cốt lõi: 1-Motif (mẫu lặp tối ưu nhất), K-Motif (tập hợp $K$ mẫu lặp có số lượng khớp không tầm thường lớn nhất), khớp tầm thường (Trivial Match) và phép biến hình vị tự (Homothetic Transformation) tâm $I$ tỷ số $k$ trong không gian affine.

Phương pháp nghiên cứu

Nghiên cứu áp dụng quy trình thực nghiệm định lượng khoa học trên các tập dữ liệu chuỗi thời gian thực tế:

• Nguồn dữ liệu và kích thước mẫu: Sử dụng 4 tập dữ liệu chuẩn từ các kho lưu trữ quốc tế gồm dữ liệu điện tâm đồ ECG (mẫu nhỏ 7.900 điểm và mẫu lớn 140.000 điểm), dữ liệu bộ nhớ máy tính Memory (6.800 điểm) và dữ liệu tiêu thụ điện năng Power (35.000 điểm). Phương pháp chọn mẫu chủ đích được áp dụng nhằm bao quát đa dạng các đặc tính tín hiệu từ tuần hoàn, dao động bán chu kỳ đến các chuỗi biến thiên ngẫu nhiên.
• Lý do lựa chọn phương pháp phân tích: Việc lựa chọn giải thuật trích chọn điểm cực trị quan trọng kết hợp phép biến hình vị tự xuất phát từ nhu cầu khắc phục triệt để hiện tượng biến dạng hình thái của phép nội suy spline bậc 1 khi co giãn chuỗi, đồng thời giảm độ phức tạp không gian và thời gian từ bậc hai $O(n^2)$ về tuyến tính $O(n)$ trong giai đoạn tạo ứng viên.
• Môi trường thử nghiệm và mốc thời gian: Thuật toán được lập trình bằng ngôn ngữ C# trên nền tảng .NET Framework và Visual Studio 2008, tích hợp thư viện đồ họa chuyên dụng DXperienceUniversal 10.4. Toàn bộ thử nghiệm thực thi trên phần cứng máy tính xách tay Lenovo trang bị vi xử lý Intel Core i5-2520M tốc độ 2.5 GHz, bộ nhớ trong 4 GB RAM chạy hệ điều hành Windows 7. Tiến trình nghiên cứu được triển khai đồng bộ từ rà soát lý thuyết (2011) đến thử nghiệm và bảo vệ thành công vào tháng 07 năm 2012.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu mang lại 4 phát hiện thực nghiệm mang tính đột phá trong bài toán nhận diện motif chuỗi thời gian:

• Tỷ lệ nén dữ liệu vượt trội: Phương pháp trích xuất điểm cực trị quan trọng đạt hiệu quả nén ấn tượng từ 91% đến 94% chiều dài chuỗi dữ liệu gốc tùy theo việc thiết lập hệ số ngưỡng $R$, giúp loại bỏ hơn 90% các điểm dữ liệu dư thừa nhưng vẫn lưu giữ trọn vẹn đặc trưng hình thái then chốt.
• Tăng tốc độ thực thi đáng kể: Trên tập dữ liệu quy mô vừa và lớn như Power (35.000 điểm) và ECG (140.000 điểm), các giải thuật cải tiến EP_C|HAC|HT và EP_C|K-Means|HT đạt thời gian xử lý nhanh gấp nhiều lần so với phương pháp Chiếu ngẫu nhiên (Random Projection). Cụ thể, trong khi phương pháp Chiếu ngẫu nhiên gặp hiện tượng bùng nổ thời gian tính toán và không thể hội tụ trên mẫu 140.000 điểm, các mô hình dựa trên điểm cực trị thực thi ổn định trong khoảng thời gian ngắn.
• Bảo toàn nguyên vẹn hình thái motif qua phép vị tự: Phép biến hình vị tự chứng minh ưu thế tuyệt đối khi lấy mẫu lại các ứng viên motif có chiều dài biến thiên (từ 470 điểm co về 150 điểm hoặc giãn ra 2.000 điểm). Kết quả bảo toàn 100% các góc uốn lượn và điểm ngoặt đặc trưng, khắc phục hoàn toàn tình trạng mất thông tin và biến dạng đường cong mà phương pháp nội suy spline bậc 1 gặp phải.
• Loại bỏ triệt để độ lệch biên độ: Việc bổ sung hệ số điều chỉnh $b$ vào hàm đo khoảng cách Euclid giúp thuật toán nhận diện chính xác các cặp motif tương đồng về dạng sóng dù biên độ dao động và đường cơ sở (baseline) có mức chênh lệch từ 20% đến trên 50%.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp mô hình đề xuất đạt hiệu năng vượt bậc nằm ở cơ chế phân tầng xử lý: trích xuất điểm cực trị giúp thu hẹp không gian tìm kiếm từ hàng chục nghìn chuỗi con trượt xuống còn vài trăm ứng viên motif thực sự mang đặc trưng hình học. So sánh với các công trình kinh điển, phương pháp Chiếu ngẫu nhiên của Chiu và cộng sự (2003) đòi hỏi quá trình thử và sai phức tạp để chọn kích thước cửa sổ trượt $w$, số từ vựng $a$ và phân đoạn PAA. Trong khi đó, giải thuật của Mueen và cộng sự (2009) dù tối ưu chặn dưới khoảng cách nhưng vẫn phụ thuộc vào chiều dài cố định. Luận văn đã giải quyết triệt để bài toán nhận diện motif đa tỷ lệ mà Gruber và cộng sự (2006) khởi xướng nhưng chưa hoàn thiện do hạn chế của phép nội suy spline.

Trong cấu trúc báo cáo, dữ liệu thực nghiệm được trực quan hóa mạch lạc qua hệ thống biểu đồ dạng sóng của 4 mô hình so sánh trên từng tập dữ liệu (từ Hình 4-10 đến Hình 4-27) cùng Bảng 4-1 tổng kết chi tiết thời gian thực thi theo từng giây. Sự kết hợp giữa biểu đồ trực quan và bảng số liệu định lượng làm nổi bật tính ưu việt của phương pháp đề xuất về độ chính xác nhận dạng và khả năng tiết kiệm tài nguyên tính toán.

Đề xuất và khuyến nghị

Dựa trên các phát hiện thực nghiệm, luận văn đưa ra 4 giải pháp ứng dụng và định hướng phát triển thực tiễn:

• Tích hợp giải thuật EP_C|HAC|HT vào các thiết bị y tế IoT theo dõi điện tim đeo tay: Nhằm rút ngắn trên 85% độ trễ xử lý và phát hiện tức thời các biến chứng loạn nhịp tim với ngưỡng phản hồi dưới 2 giây. Thời gian triển khai dự kiến trong vòng 6 đến 12 tháng tới do các nhóm kỹ sư y sinh và phát triển phần mềm nhúng đảm trách.
• Chuẩn hóa khung tham số nén cực trị $R$ trong khoảng 1.05 đến 1.20: Thiết lập hướng dẫn kỹ thuật cho các hệ thống giám sát lưới điện thông minh SCADA nhằm duy trì hệ số nén ổn định trên 90% và giảm 70% băng thông truyền tải dữ liệu đo đếm về trung tâm trong giai đoạn 1 đến 2 quý tới, do các chuyên gia phân tích dữ liệu năng lượng thực hiện.
• Mở rộng nghiên cứu sang nhận diện motif trên chuỗi thời gian đa biến (Multivariate Time Series): Nâng cao năng lực giám sát và dự báo lỗi tự động trong các trung tâm dữ liệu máy chủ đám mây, hướng tới mục tiêu đạt độ chính xác chẩn đoán trên 96% trước năm 2027 bởi các viện nghiên cứu trí tuệ nhân tạo và kỹ sư dữ liệu lớn.
• Tối ưu hóa thuật toán trên kiến trúc tính toán song song GPU và điện toán biên: Cho phép hệ thống xử lý các tập dữ liệu cực lớn vượt ngưỡng 1.000.000 điểm trong thời gian thực dưới 5 giây, do các kiến trúc sư hệ thống phân tán và kỹ sư hạ tầng phần mềm chủ trì triển khai.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng cụ thể:

• Nghiên cứu sinh, học viên cao học và giảng viên ngành Khoa học Máy tính: Cung cấp nguồn tài liệu học thuật chuyên sâu về kỹ thuật thu giảm số chiều, biểu diễn chuỗi thời gian (PAA, SAX, DWT) và các giải thuật gom cụm phân cấp cải tiến trong khai phá dữ liệu nâng cao.
• Kỹ sư phần mềm y tế và chuyên gia phân tích tín hiệu y sinh: Ứng dụng mô hình trích xuất cực trị và chuẩn hóa hình thái vị tự để xây dựng phần mềm phân tích điện tâm đồ (ECG), điện não đồ (EEG) tự động với độ chính xác cao trên các tập dữ liệu dài hơn 100.000 điểm.
• Chuyên gia dữ liệu lưới điện thông minh và giám sát công nghiệp SCADA: Vận dụng giải thuật để phát hiện mẫu phụ tải bất thường, tối ưu hóa biểu đồ tiêu thụ điện và ngăn ngừa sự cố lưới điện từ dữ liệu đo lường định kỳ 35.000 điểm trở lên.
• Kỹ sư tài chính định lượng và phân tích chuỗi thời gian thị trường: Khai thác phương pháp loại trừ độ lệch biên độ để nhận diện các mô hình kỹ thuật lặp lại trên biểu đồ biến động giá chứng khoán, chỉ số thị trường vốn có biên độ và chu kỳ dao động không đồng đều.

Câu hỏi thường gặp

• Khái niệm nhận diện motif trong chuỗi thời gian là gì và tại sao lại quan trọng? Nhận diện motif là quá trình tìm kiếm các chuỗi con xuất hiện lặp đi lặp lại nhiều lần và có độ tương đồng cao trong một chuỗi dữ liệu thời gian lớn. Quá trình này giữ vai trò cốt lõi trong việc nhận diện đặc trưng, gom cụm mẫu dữ liệu, khám phá luật kết hợp và phát hiện sớm các dấu hiệu bất thường trong y tế, tài chính và công nghiệp.

• Điểm cực trị quan trọng (IEP) mang lại ưu thế gì so với phương pháp Chiếu ngẫu nhiên? Kỹ thuật điểm cực trị quan trọng nén dữ liệu từ 91% đến 94% trong thời gian tuyến tính $O(n)$, giúp trích chọn trực tiếp các ứng viên motif mang ý nghĩa hình học. Cách tiếp cận này loại bỏ hoàn toàn quá trình thử và sai để chọn kích thước cửa sổ trượt $w$, giúp giảm mạnh chi phí tính toán trên các tập dữ liệu lớn hàng trăm nghìn điểm.

• Phép biến hình vị tự giải quyết nhược điểm gì của phương pháp nội suy spline? Nội suy spline bậc 1 làm mượt trung điểm khiến chuỗi con bị biến dạng nghiêm trọng khi co giãn tỷ lệ (từ 470 điểm xuống 300 điểm). Ngược lại, phép biến hình vị tự tâm $I$ bảo toàn nguyên vẹn hình dạng đường cong và các điểm uốn đặc trưng của motif bất kể hệ số co giãn $k$, đảm bảo độ chính xác tuyệt đối khi so khớp.

• Thuật toán xử lý thế nào khi hai chuỗi con có biên độ dao động và đường cơ sở khác nhau? Nghiên cứu bổ sung hệ số dịch chuyển $b$ được tính toán trực tiếp từ độ chênh lệch giá trị trung bình giữa hai chuỗi con vào công thức khoảng cách Euclid. Kỹ thuật này triệt tiêu hoàn toàn sai lệch về biên độ dao động, giúp phát hiện chính xác các motif tương đồng hình học dù biên độ chênh lệch từ 20% đến 50%.

• Giải thuật có khả năng mở rộng cho các tập dữ liệu quy mô trên 100.000 điểm không? Thực nghiệm trên mẫu ECG quy mô 140.000 điểm đã chứng minh thuật toán EP_C|HAC|HT và EP_C|K-Means|HT thực thi ổn định và cho kết quả rõ ràng trong thời gian ngắn. Điều này khẳng định khả năng thích ứng vượt bậc của giải thuật đối với dữ liệu chuỗi thời gian quy mô lớn mà phương pháp Chiếu ngẫu nhiên không thể đáp ứng.

Kết luận

• Đóng góp học thuật: Luận văn đã hoàn thiện thành công mô hình 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 kết hợp gom cụm phân cấp (HAC) và K-Means.
• Đổi mới phương pháp: Ứng dụng xuất sắc phép biến hình vị tự trong không gian affine và công thức khoảng cách cải tiến, giải quyết triệt để hạn chế biến dạng mẫu và loại bỏ độ lệch biên độ dao động.
• Hiệu năng thực nghiệm: Đạt tỷ lệ nén dữ liệu từ 91% đến 94%, duy trì thời gian thực thi tối ưu và nhận diện chính xác motif trên các tập dữ liệu thực tế lên tới 140.000 điểm.
• Lộ trình phát triển: Mở rộng giải thuật cho chuỗi thời gian đa biến và tích hợp kiến trúc xử lý song song trên phần cứng chuyên dụng trong giai đoạn tiếp theo.
• Khuyến nghị hành động: Các tổ chức y tế, doanh nghiệp năng lượng và đơn vị nghiên cứu công nghệ nên tham khảo, thử nghiệm và tích hợp mô hình này vào quy trình phân tích dữ liệu lớn thời gian thực nhằm tối ưu hóa chi phí vận hành và nâng cao độ chính xác cảnh báo.

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

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1.1 Dữ liệu chuỗi thời gian 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ác cách khác 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. Ví dụ chúng ta có chuỗi thời gian theo dõi quá trình đo nhiệt độ như sau: S=<14.1> Hình 1-1: Minh họa về dữ liệu chuỗi thời gian theo dõi quá trình đo nhiệt độ 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 tim đồ, 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 lĩnh vực trong những năm gần đây. Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Hình 1-2: Đồ thị biễu diễn chuỗi dữ liệu thời gian điện tâm đồ (ECG) Hình 1.2 mô tả quá trình đo nhiệt độ trong ngày và điện tâm đồ Một số vấn đề khi nghiên cứu chuỗi dữ liệu 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.2 Nhận diện Motif trong dữ liệu chuỗi thời gian Một trong những vấn đề được quan tâm trong việc khai phái dữ liệu chuỗi thời gian là nhận diện những chuỗi con tương tự xuất hiện thường xuyên (gọi là motif). Các phương pháp được ứng dụng trong bài toán này thường được dùng là Brute- Force được J.Lin và các cộng sự đề xuất năm 2002[3], phương pháp chiếu ngẫu nhiên (Random Projection) được B.Chiu và các cộng sự giới thiệu năm 2003[2], giải thuật MK của Mueen và các cộng sự đưa ra năm 2009[4] .Tuy nhiên khi áp dụng các phương pháp trên thì ta gặp phải các nhược điểm sau: o Không thích hợp khi chuỗi dữ liệu lớn. Huỳnh Nguyễn Tín – 09070469 2 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng o Cả ba phương pháp này không thể nhận ra được các motif có chiều dài hay biên độ khác nhau.

Hướng giải quyết : Dựa vào phương pháp nhận diện motif do Gruber và các cộng sự đưa ra năm 2006[1]: o Trích lược các điểm cực trị quan trọng của chuỗi dữ liệu thời gian, từ đó chọn ra những ứng viên motif. o Gom cụm các ứng viên motif bằng phương pháp phân cấp từ dưới lên (Hierarchical Bottom-Up) hoặc K-Means. o Cải tiến công thức tính độ tương tự hai ứng viên motif bằng phép biến hình vị tự (homothetic transformation) để đồng nhất chiều dài các ứng viên motif. Sau đó chúng tôi sẽ tiến hành gom cụm các ứng viên motif sau phép biến hình này.

o Sử dụng công thức tính độ tương tự cải tiến để loại trừ biên độ (range) của các ứng viên motif.3 Mục tiêu và giới hạn của đề tài Mục tiêu chính của đề tài là nghiên cứu phương pháp tìm kiếm motif trên dữ liệu chuỗi thời gian. Đề tài này dựa trên nghiên cứu của Gruber và các cộng sự. Phương pháp này dựa vào ý tưởng nén những chuỗi thời gian nhờ vào những điểm cực trị quan trọng (Cực đại và Cực tiểu). Kết quả thu được sẽ so sánh với phương pháp nhận diện motif dựa vào phép chiếu ngẫu nhiên và gom cụm phân cấp từ dưới lên dùng nội suy spline về hai phương diện: Thời gian chạy, sự chính xác của giải thuật… Chúng tôi chọn phương pháp chiếu ngẫu nhiên bởi vì phương pháp này được sử dụng rộng rãi và thường được sử dụng để so sánh với các giải thuật nhận diện motif khác.4 Tóm lược những kết quả thu được: Với việc tập trung vào mục đích chính của luận văn trong suốt quá trình thực hiện và thử nghiệm chúng tôi thấy được ưu điểm của phương pháp nhận diện motif dựa vào các điểm cực trị kết hợp với giải thuật gom cụm phân cấp từ dưới lên hay K-Means so với phương pháp chiếu ngẫu nhiên như sau: Thời gian đáp ứng rất nhanh.

Thích nghi được chuỗi dữ liệu lớn (lên đến hàng trăm ngàn). Có thể nhận thấy được các thể hiện motif không cùng chiều dài và có biên độ dao động khác nhau.5 Cấu trúc luận văn Huỳnh Nguyễn Tín – 09070469 3 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Chương II chúng tôi sẽ giới thiệu qua các công trình liên quan đến luận văn bao gồm giới thiệu về các phương pháp về độ đo tương tự giữa hai chuỗi thời gian, các phương pháp về thu giảm số chiều trên chuỗi thời gian ban đầu, cách tiếp cận về các phương pháp rời rạc hóa dữ liệu. Đồng thời, chúng tôi cũng giới thiệu lý thuyết về nhận diện motif trên dữ liệu chuỗi thời gian, phương pháp chiếu ngẫu nhiên và giải thuật MK [4]. Chương III chúng tôi sẽ tập trung vào cơ sở lý thuyết và phương pháp giải quyết vấn đề của luận văn bao gồm định nghĩa các điểm cực trị quan trọng, giải thuật gom cụm phân cấp từ dưới lên (HAC) do Gruber và các cộng sự giới thiệu năm 2006[1].

Chương IV chúng tôi giới thiệu một phương thức mới trong việc tính độ tương tự của hai chuỗi dữ liệu con dùng phép biến hình vị tự và loại trừ biên độ dao động. Cuối cùng, chúng tôi tiến hành thực nghiệm hệ thống nhận diện motif dựa vào phương pháp chiếu ngẫu nhiên và các điểm cực trị quan trọng kết hợp với HAC hay K-Means. So sánh kết quả thu được bao gồm thời gian chạy, độ chính xác và khả năng đáp ứng với chuỗi dữ liệu lớn giữa các phương pháp trên. Chương V là một số kết luận sau khi thực hiện đề tài.

Huỳnh Nguyễn Tín – 09070469 4 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng CHƯƠNG 2: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ giới thiệu tổng quan các công trình liên quan đã được nghiên cứu bao gồm các công trình về độ đo tương tự, phương pháp thu giảm số chiều, phương pháp rời rạc hóa dữ liệu, nhận diện mẫu lặp (motif) dựa trên phương pháp chiếu ngẫu nhiên và giải thuật nhận diện motif MK.1 Độ đo tương tự Trong các hầu hết các bài toán về chuỗi thời gian, bài toán tìm độ tương tự là một trong những bài toán quan trọng nhất. Cho hai đối tượng O1 và O2, khoảng cách giữa hai đối tượng này sẽ bằng 0 thì chúng được xem là giống nhau. Nếu khoảng cách giữa chúng nhỏ hơn một giá trị r cho trước thì khoảng cách giữa chúng là tương tự nhau. Gọi D(X, Y) là khoảng cách giữa hai đối tượng X và Y, ta có các tính chất sau: a) D(X,Y)=0 nếu và chỉ nếu X=Y b) D(X,Y)=D(Y,X) c) D(X,y)≥0 với mọi X,Y d) D(X,Y)<D(X,Z)+ D(Y,Z) Cho hai chuỗi thời gian X và Y có dạng X=<x1, x2…xn> và Y=<y1, y2,…yn>.

Độ tương tự giữa X và Y ký hiệu là Sim(X, Y). Sau đây là một số phương pháp dùng để xác định độ tương tự giữa hai chuỗi thời gian.1 Độ đo Minkowski Độ đo tương tự giữa hai chuỗi thời gian X và Y được xác định bằng công thức Minkowski như sau: ℎℎℎ Với, a) p=1: Độ đo Manhatan b) p=2: Độ đo Euclid c) p=3: Độ đo Max Ưu điểm Tính toán dễ dàng. Huỳnh Nguyễn Tín – 09070469 5 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Có khả năng mở rộng cho nhiều bài toán khác như gom cụm (clustering) và phân loại (classification) dữ liệu… và phù hợp với các phép biến đổi thu giảm số chiều như: DFT [18], DWT [6], PAA [7][8]… Nhược điểm: Nhạy cảm với nhiễu. Không thích hợp khi dữ liệu có đường cơ bản khác nhau (Hình 2.

Không thích hợp với dữ liệu có biên độ dao động khác nhau (Hình 2. Phương pháp khắc phục: Chuẩn hóa dữ liệu chuỗi thời gian trước khi áp dụng so trùng mẫu trên dữ liệu dựa trên giá trị trung bình và độ lệch chuẩn X’=X-mean(X) hay X’=(X-mean(X))/Var(X) [9]. Áp dụng phương pháp trung bình di chuyển [20] để làm trơn các đường biểu diễn chuỗi thời gian nghĩa là giá trị của chuỗi thời gian tại thời điểm i được tính như sau: = (2.2) 2 +1 Áp dụng độ đo tương tự có sửa đổi dựa trên khoảng cách Euclid như sau: 1 ( , )= ∑ (! − # ) − (!$ − #$ )% (2.3) & Trong đó: #$ = ∑) *( # , !$ = ∑) *( ! ( ( ) ) Huỳnh Nguyễn Tín – 09070469 6 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Hình 2-1: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau, nhưng đường cơ bản khác nhau. Hình 2-2: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau nhưng biên độ dao động khác nhau.

Huỳnh Nguyễn Tín – 09070469 7 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 2.