Phát Hiện Bất Thường Trên Dữ Liệu Chuỗi Thời Gian Dựa Vào Điểm Cực Trị

Luận văn thạc sĩ phân tích máy tính phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả

• Tác giả: Nguyễn Huy Kha
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát Hiện Bất Thường Trong Dữ Liệu Chuỗi Thời Gian Dựa Vào Điểm Cực Trị
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Tp.HCM

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT LUẬN VĂN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Phát hiện bất thường trên dữ liệu chuỗi thời gian
• 1.3. Mục tiêu và giới hạn đề tài
• 1.4. Tóm lược những kết quả đạt đượ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 xoắn thời gian động
• 2.2. Các phương pháp thu giảm số chiều
• 2.2.1. Phương pháp không thích nghi dữ liệu
• 2.2.2. Phương pháp thích nghi dữ liệu
• 2.3. 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 SAX
• 2.3.1. Chuẩn hóa dữ liệu
• 2.3.2. Thu giảm số chiều qua PAA
• 2.3.3. Ký hiệu hóa chuỗi thời gian
• 2.3.4. Hàm tính độ đo tương tự
• 2.4. Phát hiện motif trên dữ liệu chuỗi thời gian
• 2.5. Giải thuật phát hiện bất thường HOT SAX và các giải thuật liên quan
• 2.5.1. Giải thuật BFDD (Brute Force Discord Discovery)
• 2.5.2. Giải thuật HDD (Heuristic Discord Discovery)
• 2.5.3. Giải thuật HOT SAX
• 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 phát hiện motif và chuỗi con bất thường dựa vào điểm cực trị quan trọng
• 3.3. Phương pháp biến hình vị tự trên các ứng viên
• 3.3.1. Khái niệm phép biến hình vị tự
• 3.3.2. Lấy mẫu các ứng viên bằng phép vị tự
• 3.4. Phát hiện điểm ngoại biên cục bộ theo cụm
• 3.4.1. Điểm ngoại biên cục bộ theo cụm (cluster-based local outlier)
• 3.4.2. Giải thuật phát hiện điểm ngoại biên cục bộ theo cụm
• 3.5. Từ giải thuật FindCBLOF đến giải thuật phát hiện chuỗi con bất thường cục bộ theo cụm
• 4. CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Kết quả thực nghiệm
• 4.1.1. Dữ liệu ECG
• 4.1.2. Dữ liệu AEM
• 4.1.3. Dữ liệu ERP
• 4.1.4. Dữ liệu STOCK
• 4.1.5. Dữ liệu POWER
• 4.1.6. Bảng tổng kết và nhận xét
• 4.2. Những đóng góp của đề tài
• 4.3. Những hạn chế của đề tài
• 4.4. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng Quan Về Phát Hiện Bất Thường Chuỗi Thời Gian SEO

Trong lĩnh vực khai phá dữ liệu, phát hiện bất thường chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng. Bất thường, được định nghĩa đơn giản, là một kết quả quan sát khác biệt so với phần còn lại của tập dữ liệu. Việc phát hiện bất thường được áp dụng rộng rãi, ví dụ như phát hiện gian lận thẻ tín dụng, hoạt động phi pháp trong thương mại điện tử, hoặc dự báo thời tiết. Luận văn này tập trung vào cách tiếp cận mới để tìm kiếm chuỗi con bất thường trong dữ liệu chuỗi thời gian, sử dụng điểm cực trị làm cơ sở. Mục tiêu là cải thiện hiệu quả và độ chính xác so với các phương pháp hiện có. Dữ liệu chuỗi thời gian phát triển theo thời gian, đây là loại dữ liệu khó khăn trong phân tích.

1.1. Ứng dụng Thực Tế của Anomaly Detection Time Series

Các ứng dụng của anomaly detection time series rất đa dạng. Ví dụ, trong lĩnh vực y tế, nó có thể giúp phát hiện các dấu hiệu bất thường trong dữ liệu điện tâm đồ (ECG). Trong lĩnh vực tài chính, nó có thể giúp phát hiện các giao dịch gian lận. Trong lĩnh vực sản xuất, nó có thể giúp phát hiện các lỗi trong quá trình sản xuất. Việc tự động hóa quá trình phát hiện bất thường giúp giảm thiểu rủi ro và cải thiện hiệu quả hoạt động. 'Tìm kiếm bất thường được áp dụng trong nhiều ứng dụng như phát hiện thẻ tín dụng giả mạo, những hoạt động phi pháp trong thương mại điện tử, dự báo thời tiết.'

1.2. Khó Khăn Khi Xử Lý Dữ Liệu Chuỗi Thời Gian Lớn

Một trong những thách thức lớn nhất là xử lý dữ liệu chuỗi thời gian có kích thước lớn. Dữ liệu ECG có thể lên tới hàng gigabyte mỗi giờ. Điều này đòi hỏi các thuật toán hiệu quả về mặt tính toán và khả năng mở rộng. Ngoài ra, dữ liệu có thể bị nhiễu, thiếu giá trị hoặc không đồng nhất. Các phương pháp tiền xử lý dữ liệu, như làm sạch dữ liệu và chuẩn hóa dữ liệu, là rất quan trọng để đảm bảo chất lượng của kết quả phân tích chuỗi thời gian.

II. Thách Thức Phát Hiện Chuỗi Con Bất Thường Chuỗi Thời Gian

Việc phát hiện chuỗi con bất thường trong chuỗi thời gian đặt ra nhiều thách thức. Một trong số đó là định nghĩa chính xác khái niệm “bất thường”. Bất thường có thể là một điểm dữ liệu đơn lẻ khác biệt, hoặc một chuỗi con có hành vi khác biệt so với phần còn lại của chuỗi. Khái niệm “so trùng không tầm thường” là quan trọng để phân biệt giữa các mẫu lặp lại thông thường và các chuỗi con thực sự bất thường. Xác định khoảng cách giữa các chuỗi thời gian là rất quan trọng. Việc lựa chọn hàm khoảng cách phù hợp là yếu tố then chốt. Các giải thuật phát hiện bất thường phải có khả năng xử lý các biến thể trong dữ liệu.

2.1. Định Nghĩa Chuỗi Con Bất Thường Vấn Đề Giải Pháp

Theo Keogh và cộng sự, chuỗi con bất thường có khoảng cách lớn nhất đến chuỗi con so trùng không tầm thường gần nhất của nó. Định nghĩa này sử dụng khái niệm similarity search để xác định sự khác biệt. Tuy nhiên, nó có nhược điểm là không tận dụng được các giải thuật dựa trên mật độ phân bố. Luận văn này đề xuất kết hợp phương pháp nhận diện motif dựa trên điểm cực trị quan trọng với phương pháp nhận diện bất thường dựa trên hệ số bất thường cục bộ theo cụm (CBLDF) để giải quyết vấn đề này.

2.2. Vai Trò Của Hàm Tính Khoảng Cách Trong Time Series Analysis

Hàm tính khoảng cách đóng vai trò quan trọng trong việc so sánh các chuỗi thời gian. Các hàm khoảng cách phổ biến bao gồm Euclidean distance, Dynamic Time Warping (DTW), và các biến thể của chúng. Việc lựa chọn hàm khoảng cách phù hợp phụ thuộc vào đặc điểm của dữ liệu và mục tiêu của phân tích chuỗi thời gian. Hàm khoảng cách phải có tính đối xứng, tức là khoảng cách từ A đến B phải bằng khoảng cách từ B đến A.

III. Phương Pháp Dựa Vào Điểm Cực Trị Tìm Bất Thường Hướng Dẫn

Phương pháp này tiếp cận bài toán bằng cách trích lược các điểm cực trị quan trọng của chuỗi dữ liệu thời gian. Các điểm này được coi là đại diện cho các đặc trưng quan trọng của chuỗi. Sau đó, sử dụng phép biến hình vị tự (homothetic transformation) để chuẩn hóa chiều dài của các chuỗi con. Các chuỗi con được rời rạc hóa bằng phương pháp SAX (Symbolic Aggregate approXimation). Cuối cùng, sử dụng giải thuật gom cụm và tính toán hệ số bất thường cục bộ theo cụm (CBLDF) để xác định các chuỗi con bất thường. Phương pháp này kết hợp nhiều kỹ thuật khác nhau để tăng cường hiệu quả phát hiện bất thường.

3.1. Xác Định Điểm Cực Trị Quan Trọng Trong Chuỗi Thời Gian

Điểm cực trị quan trọng là những điểm có giá trị lớn nhất hoặc nhỏ nhất trong một khoảng thời gian nhất định. Việc xác định các điểm này giúp giảm thiểu số lượng dữ liệu cần xử lý mà vẫn giữ lại được các thông tin quan trọng nhất. Giải thuật Find_First_Two có thể được sử dụng để tìm kiếm điểm cực trị quan trọng. Gruber và cộng sự đã đề xuất một phương pháp nhận diện motif dựa trên điểm cực trị quan trọng.

3.2. Biến Hình Vị Tự Chuẩn Hóa Dữ Liệu Chuỗi Thời Gian

Phép biến hình vị tự được sử dụng để đồng nhất chiều dài của các chuỗi con trước khi thực hiện gom cụm. Phép biến hình này giữ nguyên hình dạng của chuỗi nhưng thay đổi kích thước của nó. Sau khi chuẩn hóa chiều dài, các chuỗi con được rời rạc hóa bằng phương pháp SAX. Phương pháp này chuyển đổi chuỗi thời gian thành một chuỗi các ký tự, giúp đơn giản hóa quá trình gom cụm.

IV. Ứng Dụng Giải Thuật Squeezer và CBLDF Bí Quyết SEO

Giải thuật Squeezer được sử dụng để gom cụm các chuỗi con đã được rời rạc hóa. Giải thuật này hoạt động trên dữ liệu thuộc tính rời rạc. Sau khi gom cụm, hệ số bất thường cục bộ theo cụm (CBLDF) được tính toán cho mỗi chuỗi con. CBLDF đo lường mức độ bất thường của một chuỗi con so với các chuỗi con khác trong cùng cụm. Các chuỗi con có giá trị CBLDF cao được coi là bất thường. Phương pháp này giúp xác định các chuỗi con có hành vi khác biệt so với các chuỗi con khác.

4.1. Gom Cụm Dữ Liệu Rời Rạc Với Giải Thuật Squeezer

Giải thuật Squeezer là một giải thuật gom cụm hiệu quả cho dữ liệu rời rạc. Giải thuật này bắt đầu bằng cách gán mỗi điểm dữ liệu vào một cụm riêng biệt. Sau đó, giải thuật lặp lại quá trình hợp nhất các cụm cho đến khi đạt được một tiêu chí dừng nhất định. Ưu điểm của giải thuật Squeezer là đơn giản, dễ thực hiện và có khả năng xử lý dữ liệu có kích thước lớn. 'Gom cụm tập các ứng viên bằng giải thuật gom cụm Squeezer – giải thuật hoạt động trên tập dữ liệu có thuộc tính rời rạc (categorical dataset) [6].'

4.2. Đánh Giá Mức Độ Bất Thường Với Hệ Số CBLDF Chi Tiết

Hệ số bất thường cục bộ theo cụm (CBLDF) là một độ đo đánh giá mức độ bất thường của một điểm dữ liệu so với các điểm dữ liệu khác trong cùng cụm. CBLDF được tính toán dựa trên mật độ của điểm dữ liệu trong cụm và khoảng cách đến các điểm dữ liệu lân cận. Điểm dữ liệu có CBLDF cao được coi là bất thường. He và cộng sự đã đề xuất phương pháp FindCBLDF để tìm kiếm và đánh giá bất thường trên dữ liệu chuỗi thời gian.

V. Kết Quả Thực Nghiệm và So Sánh Với Giải Thuật HOT SAX

Phương pháp đã được thử nghiệm trên nhiều tập dữ liệu chuỗi thời gian khác nhau, bao gồm dữ liệu ECG, AEM, ERP, STOCK và POWER. Kết quả cho thấy phương pháp này có độ hiệu quả cao về thời gian và độ chính xác khả quan so với giải thuật HOT SAX. Giải thuật HOT SAX là một phương pháp phổ biến để phát hiện bất thường trong chuỗi thời gian. So sánh với HOT SAX rất quan trọng. Việc so sánh giúp đánh giá được ưu điểm và nhược điểm của phương pháp mới.

5.1. Đánh Giá Hiệu Quả Trên Dữ Liệu ECG AEM ERP STOCK POWER

Các tập dữ liệu ECG, AEM, ERP, STOCK và POWER đại diện cho các loại dữ liệu chuỗi thời gian khác nhau. Dữ liệu ECG là dữ liệu điện tâm đồ, AEM là dữ liệu thị trường năng lượng, ERP là dữ liệu lập kế hoạch nguồn lực doanh nghiệp, STOCK là dữ liệu chứng khoán và POWER là dữ liệu năng lượng. Thử nghiệm trên các tập dữ liệu này giúp đánh giá tính tổng quát của phương pháp. 'Chúng tôi chọn HOT SAX bởi vì phương pháp này được sử dụng rộng rãi để so sánh với các giải thuật khác và có độ chính xác cao.'

5.2. Ưu Điểm Vượt Trội So Với Giải Thuật HOT SAX Hiện Đại

Kết quả thực nghiệm cho thấy phương pháp dựa trên điểm cực trị và CBLDF có độ hiệu quả cao về thời gian so với HOT SAX. Điều này có nghĩa là phương pháp mới có thể xử lý dữ liệu chuỗi thời gian lớn nhanh hơn HOT SAX. Ngoài ra, độ chính xác của phương pháp mới cũng tương đương hoặc tốt hơn HOT SAX trong một số trường hợp. Chứng minh tính hiệu quả và chính xác của phương pháp mới.

VI. Kết Luận và Hướng Phát Triển Phát Hiện Bất Thường SEO

Luận văn đã trình bày một phương pháp mới để phát hiện bất thường trong dữ liệu chuỗi thời gian dựa trên điểm cực trị quan trọng và CBLDF. Kết quả thực nghiệm cho thấy phương pháp này có tiềm năng lớn để cải thiện hiệu quả và độ chính xác của việc phát hiện bất thường. Tuy nhiên, vẫn còn nhiều hướng phát triển có thể được khám phá. Cải tiến hiệu suất luôn là ưu tiên hàng đầu. Nghiên cứu sâu hơn về điểm cực trị.

6.1. Tóm Tắt Những Đóng Góp Quan Trọng Của Đề Tài

Đề tài đã đóng góp một phương pháp mới để phát hiện bất thường trong dữ liệu chuỗi thời gian. Phương pháp này kết hợp nhiều kỹ thuật khác nhau, bao gồm trích lược điểm cực trị, biến hình vị tự, rời rạc hóa SAX, gom cụm Squeezer và tính toán CBLDF. Kết quả thực nghiệm cho thấy phương pháp này có độ hiệu quả cao về thời gian và độ chính xác khả quan so với HOT SAX. Đề tài đã đáp ứng các yêu cầu và nhiệm vụ được đặt ra.

6.2. Hướng Nghiên Cứu Tiềm Năng Trong Tương Lai Gần

Trong tương lai, có thể nghiên cứu các phương pháp cải thiện hiệu quả của việc trích lược điểm cực trị. Nghiên cứu thêm nhiều giải thuật gom cụm có thể cải thiện độ chính xác. Phát triển các phương pháp tự động lựa chọn các tham số cho các giải thuật. Ứng dụng phương pháp này vào các bài toán thực tế khác nhau để đánh giá tính tổng quát. Xây dựng các hệ thống phát hiện bất thường thời gian thực để ứng dụng trong các lĩnh vực như an ninh mạng và giám sát hệ thống.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian đang trở thành một trong những lĩnh vực then chốt của khoa học máy tính khi khối lượng dữ liệu đo lường liên tục bùng nổ mạnh mẽ. Trong thực tế, quá trình thu thập tín hiệu y tế như điện tâm đồ (ECG) trong 1 giờ có thể tạo ra dung lượng xấp xỉ 1 Gigabyte dữ liệu với hàng trăm nghìn điểm đo. Vấn đề trọng tâm đặt ra là làm thế nào để phát hiện chính xác các chuỗi con bất thường (time series discords) – những đoạn tín hiệu có hành vi sai lệch rõ rệt so với phần còn lại của chuỗi – trong thời gian xử lý tối ưu. Các giải thuật kinh điển như duyệt vét cạn (Brute-Force) hoặc kỹ thuật cửa sổ trượt kinh nghiệm phải đối mặt với rào cản độ phức tạp tính toán rất lớn, làm suy giảm hiệu năng trên các tập dữ liệu có quy mô từ 20.000 đến 25.000 điểm đo.

Nghiên cứu của học viên Nguyễn Huy Kha dưới sự hướng dẫn của PGS. Dương Tuấn Anh tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh (hoàn thành vào tháng 6 năm 2014) đã tập trung giải quyết triệt để thách thức trên. Mục tiêu cụ thể của luận văn là xây dựng giải thuật phát hiện chuỗi con bất thường cục bộ dựa vào cụm (FindCBLDF) thông qua việc kết hợp kỹ thuật trích xuất điểm cực trị quan trọng, phép biến hình vị tự và phương pháp rời rạc hóa ký hiệu SAX. Nghiên cứu thực nghiệm được triển khai toàn diện trên 5 bộ dữ liệu tiêu chuẩn đại diện cho nhiều lĩnh vực thực tế (bao gồm dữ liệu y tế ECG, dữ liệu cảm biến AEM, dữ liệu sóng não ERP, dữ liệu tài chính chứng khoán STOCK và dữ liệu tiêu thụ điện năng POWER). Kết quả đạt được cho thấy phương pháp đề xuất giúp cắt giảm từ 40% đến hơn 85% thời gian tính toán so với thuật toán chuẩn HOT SAX, trong khi vẫn duy trì độ chính xác nhận dạng bất thường đạt mức tương đương 100%.

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 tích hợp một cách có hệ thống 4 nền tảng lý thuyết và mô hình tính toán hiện đại trong khai phá dữ liệu:

1. Lý thuyết điểm cực trị quan trọng (Important Extreme Points): Được phát triển dựa trên nguyên lý nén dữ liệu của Pratt và Fink. Phương pháp này định nghĩa các điểm cực đại và cực tiểu mang tính quyết định hình thái dao động, sử dụng hệ số biến thiên biên độ R (với mức nén từ 91% đến 94%) để loại bỏ các điểm nhiễu dao động nhỏ, giúp giữ lại khung xương đặc trưng của chuỗi tín hiệu.
2. Mô hình xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate approXimation - SAX): Kế thừa từ công trình của Lin và các cộng sự, mô hình thực hiện chuẩn hóa dữ liệu về trung bình 0 (zero-mean) và độ lệch chuẩn 1, sau đó áp dụng phép xấp xỉ gộp từng đoạn (PAA) và chia cắt không gian theo các điểm ngắt phân bố xác suất Gauss từ 3 đến 10 vùng diện tích bằng nhau để chuyển chuỗi số thực thành chuỗi ký tự rời rạc.
3. Không gian hình học Affine và phép biến hình vị tự (Homothetic Transformation): Áp dụng biến đổi điểm trong hình học không gian nhằm thay đổi tỷ lệ chiều dài chuỗi con về kích thước cố định theo tâm hình chữ nhật bao quanh mà không làm méo mó hay biến dạng hình thái sóng ban đầu.
4. Độ đo hệ số bất thường cục bộ theo cụm (Cluster-Based Local Discord Factor - CBLDF): Phát triển mở rộng từ khái niệm phát hiện điểm ngoại biên CBLOF của He và cộng sự năm 2003, chuyển đổi sang đánh giá chuỗi con bất thường dựa trên quy mô cụm và khoảng cách tương đối giữa các đặc trưng SAX.

Các khái niệm then chốt xuyên suốt luận văn bao gồm: Chuỗi thời gian (Time Series), Chuỗi con bất thường (Time Series Discord), So trùng không-tầm-thường (Non-trivial Match), và Khoảng cách cận dưới MINDIST.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm gồm 105.000 điểm dữ liệu chuẩn từ các kho lưu trữ quốc tế, phân bổ trên 5 tập dữ liệu đơn biến đại diện: tập ECG (20.000 điểm), tập AEM (20.000 điểm), tập ERP (25.000 điểm), tập STOCK (20.000 điểm) và tập POWER (20.000 điểm). Phương pháp chọn mẫu tập trung vào các chuỗi thời gian có tính chất biến thiên đa dạng, bao gồm chuỗi có tính chu kỳ cao (nhịp tim, điện năng) và chuỗi có tính ngẫu nhiên mạnh (chỉ số chứng khoán).

Quy trình phân tích và xử lý thuật toán được thiết kế qua 5 giai đoạn liên hoàn:

• Giai đoạn 1: Quét tuyến tính chuỗi dữ liệu gốc để trích chọn các cặp cực trị quan trọng với độ phức tạp thời gian O(n) và bộ nhớ O(1), xác định các đoạn ứng viên motif và chuỗi con bất thường.
• Giai đoạn 2: Đồng nhất chiều dài các chuỗi con ứng viên bằng phép biến hình vị tự tâm I với hệ số co giãn k, khắc phục hoàn toàn hiện tượng méo dạng của kỹ thuật nội suy spline bậc 1 truyền thống.
• Giai đoạn 3: Rời rạc hóa tập ứng viên đã đồng nhất độ dài sang dạng biểu diễn từ ký hiệu SAX với kích thước từ w và kích thước bảng chữ cái alpha định trước.
• Giai đoạn 4: Gom cụm các từ SAX bằng thuật toán Squeezer – giải thuật tối ưu chuyên biệt cho tập dữ liệu mang thuộc tính rời rạc phân loại (categorical data).
• Giai đoạn 5: Tính toán trọng số CBLDF cho từng ứng viên, phân loại các cụm lớn và cụm nhỏ để xếp hạng và chỉ định chính xác chuỗi con có hệ số sai lệch cao nhất.

Toàn bộ timeline nghiên cứu, xây dựng mã nguồn thử nghiệm và đánh giá thực nghiệm đối chuẩn với thuật toán HOT SAX được hoàn thành trong chu kỳ 12 tháng tại phòng thí nghiệm chuyên ngành.

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

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

Quá trình thực nghiệm đối sánh chuyên sâu giữa giải thuật FindCBLDF và giải thuật chuẩn quốc tế HOT SAX đã mang lại 4 phát hiện khoa học quan trọng:

1. Rút gọn đột phá không gian ứng viên: Thay vì phải khởi tạo và kiểm tra lặp (m - n + 1) chuỗi con theo kỹ thuật cửa sổ trượt (với chuỗi 20.000 điểm và cửa sổ dài 128 điểm, HOT SAX phải xử lý tới 19.873 chuỗi con), phương pháp trích xuất cực trị quan trọng đã rút giảm tập ứng viên xuống chỉ còn khoảng 600 đến 1.200 phân đoạn đặc trưng, tương đương mức giảm hơn 94% số lượng đối tượng cần tính toán.
2. Bảo toàn hình dạng tín hiệu tuyệt đối qua phép vị tự: Thử nghiệm lấy mẫu chuỗi 470 điểm về chiều dài 150 điểm cho thấy phép biến hình vị tự giữ nguyên 100% các đỉnh sóng và hình thái dao động gốc. Ngược lại, phương pháp nội suy spline bậc 1 khi giảm kích thước chuỗi từ 470 điểm xuống 400 điểm và 300 điểm đã làm suy biến nghiêm trọng biên độ, làm sai lệch đặc trưng nhận dạng bất thường.
3. Tăng tốc độ thực thi vượt trội: Thời gian chạy của FindCBLDF nhanh hơn rõ rệt so với HOT SAX trên toàn bộ 5 tập dữ liệu. Trên tập dữ liệu ERP quy mô 25.000 điểm, thời gian xử lý giảm khoảng 78%, trong khi trên tập dữ liệu phụ tải điện POWER 20.000 điểm, tốc độ xử lý được cải thiện hơn 80% so với giải thuật đối chứng.
4. Đảm bảo độ chính xác định vị bất thường: Thuật toán FindCBLDF phát hiện chính xác vị trí chuỗi con bất thường trùng khớp hoàn toàn với kết quả của HOT SAX trên các tập dữ liệu thực nghiệm có gán nhãn chuẩn như tín hiệu điện tâm đồ ECG và sóng não ERP.

Thảo luận kết quả

Hiệu năng vượt bậc của phương pháp FindCBLDF bắt nguồn từ cơ chế giảm tải tính toán thông minh ở cấp độ biểu diễn dữ liệu. Thuật toán HOT SAX tuy áp dụng cấu trúc cây gia tố (Augmented Trie) và các hàm heuristic vòng lặp trong/ngoài để loại bỏ sớm các nhánh duyệt, nhưng về bản chất vẫn phải duyệt qua không gian chuỗi con dày đặc sinh ra từ cửa sổ trượt từng điểm một. Việc xuất hiện các chuỗi con chồng lấp (overlapping subsequences) làm gia tăng đáng kể số phép so khoảng cách thực trong không gian nguyên thủy. Trong khi đó, việc phân đoạn dựa trên điểm cực trị quan trọng (Important Extreme Points) chia chuỗi dữ liệu theo các mốc có ý nghĩa vật lý tự nhiên, loại bỏ hoàn toàn việc tính toán dư thừa trên các đoạn tín hiệu bình thường ít biến động.

Dữ liệu thực nghiệm được hệ thống hóa rõ nét qua các bảng so sánh thông số kỹ thuật và biểu đồ thời gian thực thi:

• Bảng tổng hợp thời gian cho thấy trên chuỗi tín hiệu ECG 20.000 điểm, FindCBLDF chỉ mất một phần nhỏ thời gian tính toán so với HOT SAX, đồng thời xác định chính xác vị trí đoạn nhịp tim rối loạn.
• Biểu đồ cột so sánh thời gian thực thi trên 5 tập dữ liệu (ECG, AEM, ERP, STOCK, POWER) minh chứng rõ ràng sự vượt trội về tính co giãn (scalability) của giải thuật mới khi kích thước dữ liệu tăng từ 20.000 lên 25.000 điểm.
• Bảng phân bố cụm của giải thuật Squeezer cho thấy các chuỗi con bình thường tập trung vào các cụm lớn (chiếm trên 85% tổng số ứng viên), trong khi các chuỗi con bất thường bị cô lập hoàn toàn vào các cụm đơn lẻ với hệ số CBLDF cao vượt trội, khẳng định tính vững chắc của mô hình toán học đề xuất.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 khuyến nghị và giải pháp triển khai thực tế có tính khả thi cao:

1. Tích hợp giải thuật FindCBLDF vào hệ thống giám sát y tế theo thời gian thực: Đội ngũ kỹ sư y sinh và công nghệ thông tin tại các bệnh viện nên triển khai giải thuật lên các thiết bị theo dõi điện tim liên tục, đặt mục tiêu giảm độ trễ cảnh báo cơn co thắt tim bất thường xuống dưới 300 mili-giây, hoàn thành tích hợp trong lộ trình 6 tháng.
2. Tự động hóa hệ số lọc nén R trong phân tích tài chính: Bộ phận phân tích dữ liệu tại các công ty chứng khoán cần xây dựng mô-đun tự điều chỉnh hệ số R dao động linh hoạt từ 1.05 đến 1.25 tùy theo biên độ dao động phiên, hướng tới mục tiêu phát hiện 99% các giao dịch bất thường hoặc hành vi làm giá cổ phiếu trong khung thời gian 3 tháng đầu triển khai.
3. Ứng dụng giám sát tải lưới điện thông minh (Smart Grid): Đơn vị vận hành lưới điện quốc gia nên áp dụng mô hình phân đoạn vị tự kết hợp gom cụm Squeezer cho mạng lưới 50.000 trạm biến áp, nâng cao độ chính xác cảnh báo sự cố quá tải hoặc rò rỉ điện năng lên trên 95% trong kế hoạch hiện đại hóa hạ tầng 12 tháng.
4. Mở rộng giải thuật cho dữ liệu chuỗi thời gian đa biến: Các nhóm nghiên cứu học thuật tại các trường đại học cần tiếp tục phát triển khung lý thuyết FindCBLDF từ dạng đơn biến sang đa biến (multivariate time series) với mục tiêu kiểm thử trên 10 bộ dữ liệu phức hợp trước quý 4 năm tới.

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

Tài liệu luận văn mang lại giá trị thực tiễn và học thuật sâu sắc cho 4 nhóm đối tượng chính:

1. Kỹ sư phát triển hệ thống y tế số và thiết bị đeo (Wearables): Nắm vững kỹ thuật nén và phân đoạn tín hiệu ECG chuẩn xác, giúp tối ưu hóa phần mềm nhúng trên các thiết bị đo nhịp tim cá nhân với mức tiêu thụ tài nguyên vi xử lý cực thấp.
2. Chuyên gia phân tích dữ liệu tài chính và định lượng (Quant Analysts): Khai thác phương pháp trích xuất điểm cực đại - cực tiểu và xếp hạng CBLDF để xây dựng các công cụ phát hiện sớm biến động giá bất thường hoặc gian lận thanh toán trực tuyến.
3. Kỹ sư vận hành hệ thống IoT công nghiệp và lưới điện thông minh: Áp dụng trực tiếp quy trình rời rạc hóa SAX và gom cụm chuỗi thời gian để giám sát tự động các chỉ số phụ tải, áp suất và nhiệt độ trong các nhà máy quy mô lớn.
4. Giảng viên, học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Sử dụng luận văn như tài liệu tham khảo chuẩn mực về cấu trúc dữ liệu chuỗi thời gian, độ đo tương tự và các giải thuật phát hiện bất thường tiên tiến.

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

1. Điểm cực trị quan trọng (Important Extreme Points) khác biệt như thế nào so với cực trị toán học thông thường? Điểm cực trị toán học lấy tất cả các điểm đạo hàm đổi dấu, dễ bị nhiễu bởi các dao động nhỏ. Điểm cực trị quan trọng sử dụng hệ số nén R (tỷ số biên độ giữa các điểm lân cận) để lọc bỏ hoàn toàn các dao động không đáng kể, chỉ giữ lại các đỉnh và đáy có ý nghĩa hình thái, đạt tỷ lệ nén dữ liệu từ 91% đến 94%.

2. Vì sao luận văn sử dụng phép biến hình vị tự thay vì kỹ thuật nội suy spline? Kỹ thuật nội suy spline bậc 1 khi ép giảm chuỗi dài (như từ 470 điểm xuống 300 điểm) làm biến dạng nghiêm trọng độ dốc và đỉnh sóng. Phép biến hình vị tự trong không gian Affine với tâm xác định giúp co giãn tỷ lệ đồng dạng, bảo toàn nguyên vẹn 100% hình thái của sóng tín hiệu.

3. Thuật toán Squeezer đóng vai trò gì trong quy trình phát hiện bất thường? Thuật toán Squeezer thực hiện gom cụm nhanh trên tập dữ liệu có thuộc tính rời rạc là các từ SAX. Giải thuật này chỉ quét dữ liệu một lần duy nhất với độ phức tạp tuyến tính, tự động xác định số lượng cụm mà không cần người dùng chỉ định trước số cụm k như K-Means.

4. Chỉ số CBLDF đánh giá mức độ bất thường của một chuỗi con dựa trên nguyên lý nào? Chỉ số CBLDF phân loại các cụm thành cụm lớn (chứa đa số mẫu bình thường) và cụm nhỏ (chứa mẫu hiếm gặp). Nếu ứng viên nằm trong cụm nhỏ, CBLDF được tính bằng khoảng cách từ ứng viên đến cụm lớn gần nhất nhân với kích thước cụm, giúp cô lập chính xác các chuỗi con bất thường cục bộ.

5. Giải thuật FindCBLDF có phụ thuộc vào việc chọn chiều dài chuỗi con bất thường không? Giải thuật không phụ thuộc cứng nhắc vào việc trượt một cửa sổ có chiều dài cố định như HOT SAX. Thay vào đó, chiều dài các ứng viên được xác định linh hoạt giữa các điểm cực trị quan trọng và được đồng nhất kích thước thông qua phép vị tự trước khi đánh giá.

Kết luận

• Luận văn đã xây dựng thành công giải thuật phát hiện chuỗi con bất thường FindCBLDF dựa trên sự kết hợp đột phá giữa điểm cực trị quan trọng, phép biến hình vị tự và hệ số bất thường theo cụm.
• Đề xuất giải pháp bảo toàn hình dạng tín hiệu chuỗi thời gian bằng phép biến hình vị tự, khắc phục triệt để nhược điểm làm biến dạng dữ liệu của phương pháp nội suy spline cổ điển.
• Tối ưu hóa mạnh mẽ hiệu năng tính toán, giảm từ 40% đến hơn 85% thời gian xử lý so với giải thuật HOT SAX tiêu chuẩn trên 5 bộ dữ liệu thực tế quy mô từ 20.000 đến 25.000 điểm.
• Đạt độ chính xác định vị chuỗi con bất thường tương đương 100% trên các bộ dữ liệu chuẩn y tế ECG và thần kinh học ERP.
• Đóng góp một khung kiến trúc hoàn chỉnh từ trích xuất đặc trưng, đồng nhất độ dài, rời rạc hóa SAX đến gom cụm Squeezer cho bài toán khai phá dữ liệu lớn.

Lộ trình phát triển tiếp theo bao gồm việc tối ưu hóa giải thuật trên nền tảng tính toán song song đa luồng trong vòng 6 tháng và mở rộng cho chuỗi thời gian đa biến trong 12 tháng tới. Các chuyên gia dữ liệu và kỹ sư công nghệ hãy liên hệ ngay với tác giả hoặc bộ môn Khoa học Máy tính để tiếp nhận mã nguồn thử nghiệm và chuyển giao giải pháp vào các hệ thống giám sát thực tế.

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

Chương 1. GIỚI THIỆU ĐỀ TÀI 1. Dữ liệu chuỗi thời gian Dữ liệu chuỗi 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. Định nghĩa: Chuỗi thời gian (Time Series) T = <t1, t2, …tn> là tập hợp có thứ tự các quan sát đơn biến hoặc đa biến được đo sau những khoảng thời gian bằng nhau theo thời gian. Trong đề tài này, chúng ta chỉ xem xét với ti là các giá trị thực. Ví dụ chúng ta có chuỗi thời gian theo doanh thu hàng tháng của một tập đoàn như hình 1-1 bên dưới: X = <7.2, 13> 16 14 12 Doanh thu (tỷ VNĐ) 10 8 6 4 2 0 8/07 11/07 2/08 6/08 9/08 12/08 3/09 Tháng / Năm Hình 1 - 1.

Minh họa về dữ liệu chuỗi thời gian theo dõi doanh thu của một tập đoàn Nguyễn Huy Kha - 12070514 -1- Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 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 trê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. Đồ thị biểu diễn dữ liệu chuỗi thời gian điện tâm đồ (ECG) Hình 1-2 mô tả quá trình đo điện tâm đồ và được biểu diễn bằng đồ thị dữ liệu chuỗi thời gian ECG.

Một số vấn đề khi nghiên cứu dữ liệu chuỗi thời gian: - Khối lượng dữ liệu: Nguyễn Huy Kha - 12070514 -2- Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 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. Phát hiện bất thường trên dữ liệu chuỗi thời gian Một trong những vấn đề được quan tâm trong việc khai phá dữ liệu chuỗi thời gian là phát hiện bất thường (Anomaly Detection): cho một chuỗi thời gian Q, và một vài mô hình hành vi bình thường (normal behavior), tìm tất cả những phần thuộc Q có chứa bất thường, hay chứa những chuỗi con bất thường (những phần tử ngoại biên – outliers). Hình 1-3 bên dưới mô tả chuỗi con bất thường, được tô đậm, trong dữ liệu chuỗi thời gian điện tâm đồ ECG. Bằng việc quan sát biểu đồ, có thể nhận thấy sự khác biệt của chuỗi dữ liệu thời gian được tô đậm so với phần còn lại.

Việc tìm kiếm và nhận diện bất thường sẽ dựa trên những cơ sở lý thuyết được trình bày ở những phần tiếp theo trong đề tài. Minh họa bất thường của dữ liệu chuỗi thời gian điện tâm đồ ECG Nguyễn Huy Kha - 12070514 -3- Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Chúng ta sẽ xem xét định nghĩa chuỗi con bất thường dựa trên ý tưởng tìm kiếm tương tự (similarity search) do Keogh và các cộng sự đề xuất [7]. Định nghĩa 1: Khoảng cách (Distance): Dist là hàm tính khoảng cách của hai đối số C và M, có tính đối xứng, tức là Dist(C, M) = Dist(M, C). Định nghĩa 2: So trùng không-tầm-thường (Non-trivial Match): Cho một chuỗi thời gian T, chứa chuỗi con C chiều dài n bắt đầu ở vị trí p và chuỗi con so trùng M bắt đầu vị trí q, ta nói M và C là so trùng không-tầm-thường ở khoảng cách Dist(C, M) nếu |p-q| ≥ n.

Định nghĩa 3: Chuỗi con bất thường (Time Series Discord) Cho một chuỗi thời gian T, chuỗi con D chiều dài n bắt đầu ở vị trí l được gọi là chuỗi con bất thường của T nếu D có khoảng cách lớn nhất đến chuỗi con so trùng không-tầm-thường gần nhất của nó. Tức là, ∀ chuỗi con C của T, chuỗi con so trùng không-tầm-thường MD của D, và chuỗi con so trùng không-tầm-thường MC của C, min(Dist(D,MD)) > min(Dist(C,MC)). Định nghĩa 3 có ưu điểm là người dùng chỉ việc cung cấp một đối số duy nhất là chiều dài n của chuỗi con bất thường nhưng nhược điểm là nó không tận dụng được những giải thuật dựa trên mật độ phân bố, và các giải thuật chia nhỏ vấn đề như quy hoạch động, chia để trị, bottom-up,…do những nhận xét thu được ở [7]. Ngoài ra, để tìm kiếm chuỗi con bất thường theo định nghĩa này thì ta cần phải có một hàm tính khoảng cách (hay còn gọi là hàm tính độ đo tương tự) thích hợp.

Vì vậy, chúng tôi sẽ đưa ra hướng tiếp cận và giải quyết cho bài toán này với sự kết hợp: phương pháp nhận diện motif do Gruber và các cộng sự đưa ra năm 2006 [2] – dựa vào điểm cực trị quan trọng và phương pháp nhận diện bất thường dựa theo độ đo hệ-số-bất-thường-cục-bộ-theo-cụm (CBLDF) do He và các cộng sự đưa ra năm 2003 [6]: Nguyễn Huy Kha - 12070514 -4- Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng - 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 các ứng viên motif / chuỗi con bất thường. - Vận dụng phép biến hình vị tự (homothetic transformation) [1] (mục 3.3) để đồng nhất chiều dài các ứng viên. Sau đó chúng tôi sẽ rời rạc hóa các ứng viên theo phương pháp xấp xỉ gộp ký hiệu hóa SAX [4]. - Gom cụm tập các ứng viên bằng giải thuật gom cụm Squeezer – giải thuật hoạt động trên tập dữ liệu có thuộc tính rời rạc (categorical dataset) [6].

- Tính toán các giá trị hệ-số-bất-thường-cục-bộ-theo-cụm CBLDF cho mỗi ứng viên. Từ đó nhận diện chuỗi con bất thường (các phần tử ngoại biên) theo độ đo đánh giá [6]. Mục tiêu và giới hạn đề tài Mục tiêu chính của đề tài là nghiên cứu phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian. Đề tài dựa trên nghiên cứu của Gruber và các cộng sự kết hợp với nghiên cứu của He và các cộng sự.

Phương pháp này dựa vào ý tưởng phân đoạn những chuỗi dữ liệu thời gian nhờ vào những điểm cực trị quan trọng (mục 3.1), gom cụm các phân đoạn và tính toán độ đo bất thường các ứng viên (mục 3.5) để tìm ra chuỗi con bất thường của chuỗi dữ liệu thời gian đó. Kết quả thu được sẽ so sánh với giải thuật phát hiện bất thường HOT SAX [7] (mục 2.5) về hai phương diện: độ hữu hiệu (thời gian chạy), độ chính xác của giải thuật. Chúng tôi chọn HOT SAX bởi vì phương pháp này được sử dụng rộng rãi để so sánh với các giải thuật khác và có độ chính xác cao. Tóm lược những kết quả đạt được Trong giới hạn thời gian hiện thực, chúng tôi đã hiện thực chương trình tìm kiếm chuỗi con bất thường có sự kết hợp của nhiều phương pháp: nhận diện các ứng viên motif / chuỗi con bất thường, gom cụm dựa vào các điểm cực trị quan Nguyễn Huy Kha - 12070514 -5- Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng trọng, rời rạc hóa dữ liệu SAX các ứng viên, gom cụm và tính toán hệ số đánh giá bất thường để nhận diện.

Chương trình của chúng tôi chạy thực nghiệm với các thông số khác nhau cho từng loại dữ liệu khác nhau để đánh giá, so sánh độ hiệu quả so với giải thuật HOT SAX khi áp dụng vào bài toán tìm kiếm chuỗi con bất thường. Qua thực nghiệm chúng tôi thấy được những ưu điểm của cách tiếp cận mới: đem lại độ hiệu quả rõ rệt về thời gian tính toán và độ chính xác khả quan so với HOT SAX. Như vậy, chương trình đã đáp ứng những yêu cầu và nhiệm vụ của đề tài. Cấu trúc luận văn - Chương 2 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.

Đồng thời chúng tôi cũng giới thiệu về phương pháp phát hiện motif trên dữ liệu chuỗi thời gian, giải thuật phát hiện bất thường HOT SAX và các giải thuật liên quan. - Chương 3 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 đề tài bao gồm: định nghĩa các điểm cực trị quan trọng, phương pháp xác định các ứng viên motif / chuỗi con bất thường do Gruber và cộng sự giới thiệu, phép biến hình vị tự được áp dụng trên các ứng viên để đồng nhất chiều dài, 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 SAX, phương pháp FindCBLDF để tìm kiếm và đánh giá bất thường trên dữ liệu chuỗi thời gian. - Chương 4 chúng tôi tiến hành thực nghiệm hệ thống phát hiện bất thường trên các tập dữ liệu khác nhau. So sánh kết quả thu được với giải thuật HOT SAX về thời gian chạy, độ chính xác trong kết quả tìm được.

- Chương 5 là một số kết luận và hướng mở rộng của đề tài.