Luận văn thạc sĩ: Nhận dạng motif và bất thường trên dữ liệu chuỗi thời gian

Tổng hợp kiến thức Nhận dạng motif và bất thường trong chuỗi thời gian bằng ..., tiếp cận khoa học, hỗ trợ học tập và nghiên cứu hiệu quả trong

• Tác giả: Pham Thanh Xuan
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nhận dạng motif và bất thường trong chuỗi thời gian bằng kỹ thuật băm
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Đị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
• ABSTRACT
• DANH MỤC HÌNH ẢNH
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Truy xuất thông tin trên dữ liệu chuỗi thời gian
• 1.3. Khai phá motif và bất thường trên dữ liệu chuỗi thời gian
• 1.4. Hướng tiếp cận của luận văn
• 1.5. Ý nghĩa của luận văn
• 1.6. Cấu trúc của luận văn
• 2. CHƯƠNG 2: TỔNG THUẬT NHỮNG CÔNG TRÌNH LIÊN QUAN
• 2.1. Một số khái niệm cơ bản
• 2.2. Các phương pháp tính độ đo tương tự
• 2.2.1. Độ đo Dynamic Time Warping (DTW)
• 2.3. Các phương pháp biểu diễn dữ liệu chuỗi thời gian
• 2.3.1. Các phương pháp thu giảm số chiều
• 2.3.2. Phương pháp rời rạc hóa dữ liệu
• 2.4. Giải thuật khai phá motif chính xác
• 2.5. Giải thuật khai phá motif xấp xỉ
• 2.6. Giải thuật khai phá bất thường
• 2.7. Giải thuật kết hợp khai phá motif và khai phá bất thường
• 3. CHƯƠNG 3: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 3.1. Thu giảm số chiều với phương pháp PAA
• 3.2. Rời rạc hóa dữ liệu với phương pháp SAX
• 3.3. Độ đo tương tự MINDIST
• 3.4. Giải thuật FMG
• 3.5. Giải thuật RFMG
• 3.6. So sánh phương pháp thực hiện của các giải thuật đi trước
• 4. CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Mô hình hiện thực các giải thuật
• 4.1.1. Giải thuật chiếu ngẫu nhiên RP
• 4.1.2. Giải thuật nhận dạng bất thường HOTSAX
• 4.1.3. Giải thuật vừa khai phá motif vừa khai phá bất thường FMG
• 4.1.4. Giải thuật khai phá motif RFMG
• 4.2. Thực nghiệm các giải thuật đã hiện thực
• 4.2.1. Dữ liệu điện tim đồ (ECG) 100
• 4.2.2. Dữ liệu điện tim đồ (ECG) 300
• 4.2.3. Dữ liệu điện não đồ (EEG) 10
• 4.2.4. Dữ liệu doanh nghiệp (ERP) 198
• 4.2.5. Dữ liệu MEMORY 6
• 4.2.6. Dữ liệu năng lượng (POWER) 35
• 4.2.7. Dữ liệu chứng khoán (STOCK) 12
• 4.3. So sánh các giải thuật dựa trên kết quả thực nghiệm
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Kết luận
• 5.2. Những đóng góp của luận văn
• 5.3. Hướng phát triển của luận văn
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT
• PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới thiệu về dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian là một loại dữ liệu được thu thập theo thời gian, thường có kích thước lớn và gia tăng nhanh chóng. Việc khai thác thông tin từ dữ liệu này là rất quan trọng trong nhiều lĩnh vực như tài chính, y tế và khoa học. Nhận dạng motif và bất thường chuỗi thời gian là hai nhiệm vụ chính trong phân tích dữ liệu chuỗi thời gian. Motif là những chuỗi con tương tự xuất hiện nhiều lần, trong khi bất thường là những chuỗi con chỉ xuất hiện một lần và khác biệt nhất. Các giải thuật khai phá dữ liệu chuỗi thời gian phải đối mặt với chi phí lớn về thời gian và tài nguyên bộ nhớ. Do đó, nghiên cứu các phương pháp hiệu quả để khai thác dữ liệu chuỗi thời gian ngày càng trở nên quan trọng.

II. Khai phá motif và bất thường

Khai phá motif và bất thường là hai nhiệm vụ quan trọng trong phân tích dữ liệu chuỗi thời gian. Kỹ thuật băm được sử dụng để tối ưu hóa quá trình này. Motif được xác định là những chuỗi con tương tự nhau xuất hiện lặp đi lặp lại, trong khi bất thường là những chuỗi con khác biệt nhất. Việc phát hiện motif chính xác thường yêu cầu xử lý trực tiếp trên dữ liệu thô, trong khi phát hiện bất thường có thể sử dụng các phương pháp xấp xỉ. Giải thuật FMG (Feature Match Grouping) được đề xuất trong luận văn này nhằm giải quyết cả hai nhiệm vụ này một cách hiệu quả.

III. Phương pháp giải quyết vấn đề

Giải thuật FMG được phát triển để vừa khai phá motif vừa phát hiện bất thường trong dữ liệu chuỗi thời gian. Quá trình bắt đầu bằng việc chuẩn hóa dữ liệu thô, sau đó thực hiện thu giảm số chiều và rời rạc hóa. Sử dụng cửa sổ trượt, các chuỗi con được sinh ra và lưu trữ trong bảng băm. Các thùng băm lớn nhất sẽ chứa các ứng viên motif, trong khi các thùng chỉ chứa một đặc trưng sẽ là ứng viên bất thường. Giải thuật này cho phép phát hiện motif và bất thường trong thời gian tuyến tính, giúp tiết kiệm tài nguyên bộ nhớ.

IV. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy giải thuật FMG vượt trội hơn so với các giải thuật khác như Random Projection và HOTSAX trong việc phát hiện motif và bất thường. Các thử nghiệm được thực hiện trên nhiều loại dữ liệu khác nhau như ECG, EEG và dữ liệu chứng khoán. Giải thuật FMG không chỉ cải thiện độ chính xác mà còn giảm thiểu thời gian xử lý, cho thấy tính khả thi và hiệu quả trong ứng dụng thực tế.

V. Ý nghĩa và ứng dụng thực tiễn

Luận văn này không chỉ đóng góp vào lý thuyết về nhận dạng motif và bất thường chuỗi thời gian, mà còn cung cấp một giải pháp thực tiễn cho các vấn đề trong phân tích dữ liệu lớn. Giải thuật FMG có thể được áp dụng trong nhiều lĩnh vực như tài chính, y tế và an ninh mạng, nơi mà việc phát hiện các mẫu và bất thường là rất quan trọng. Việc phát triển các phương pháp hiệu quả để xử lý dữ liệu lớn sẽ giúp cải thiện khả năng ra quyết định và dự đoán trong các lĩnh vực này.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian đang gia tăng với tốc độ bùng nổ, ước tính chiếm hơn 70% tổng lượng dữ liệu đo lường trong các lĩnh vực tài chính, y tế, viễn thông và công nghiệp tự động hóa. Trong môi trường công nghệ hiện đại, một hệ thống giám sát có thể tạo ra hàng triệu điểm dữ liệu mỗi ngày, đặt ra thách thức nghiêm trọng về năng lực tính toán và tối ưu hóa bộ nhớ cho các thuật toán phân tích dữ liệu.

Hai bài toán cốt lõi trong khai phá dữ liệu chuỗi thời gian là nhận dạng motif (các mẫu chuỗi con lặp lại có tính chất tương đồng) và phát hiện bất thường (chuỗi con dị biệt nhất so với toàn bộ phần còn lại). Hầu hết các giải thuật truyền thống xử lý hai nhiệm vụ này một cách riêng biệt với độ phức tạp tính toán lên tới mức bậc hai theo kích thước tập dữ liệu, gây ra hiện tượng nghẽn cổ chai khi khối lượng dữ liệu vượt ngưỡng hàng trăm nghìn phần tử.

Đề tài nghiên cứu được thực hiện tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh trong giai đoạn 5 tháng từ tháng 01/2013 đến tháng 06/2013. Luận văn tập trung giải quyết bài toán đồng thời nhận dạng motif xấp xỉ và phát hiện bất thường chính xác trên các luồng dữ liệu chuỗi thời gian quy mô lớn.

Mục tiêu cụ thể là đề xuất và hiện thực hóa giải thuật nhóm khớp đặc trưng Feature Match Grouping dựa trên cấu trúc bảng băm, kết hợp với phương pháp loại trừ tiến - lùi Forward_Backward. Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc hạ mức độ phức tạp tính toán xuống thời gian tuyến tính, tối ưu hóa không gian lưu trữ chỉ tương đương một danh sách số nguyên cố định, giúp nâng cao hiệu suất xử lý dữ liệu dòng chảy lên gấp nhiều lần so với các giải thuật kinh điển.

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 xây dựng trên nền tảng lý thuyết biểu diễn dữ liệu chuỗi thời gian và các độ đo tương tự trong không gian đa chiều:

• Lý thuyết thu giảm số chiều Piecewise Aggregate Approximation: Chuỗi dữ liệu gốc có chiều dài 128 điểm đo được phân đoạn thành 8 khung có kích thước đồng đều. Giá trị trong mỗi khung được đại diện bằng trung bình cộng các điểm dữ liệu thành phần, giúp giảm thiểu chiều dữ liệu đáng kể mà vẫn bảo toàn hình dạng tổng quát của sóng tín hiệu.
• Lý thuyết rời rạc hóa biểu tượng Symbolic Aggregate Approximation: Tận dụng đặc tính dữ liệu chuỗi thời gian sau chuẩn hóa tuân theo phân bố chuẩn Gauss với kỳ vọng bằng 0 và phương sai bằng 1. Không gian bên dưới đường cong Gauss được chia thành 6 vùng xác suất bằng nhau thông qua danh sách 5 điểm ngắt cố định. Mỗi hệ số PAA được ánh xạ thành một ký tự alphabet rời rạc tương ứng, chuyển bài toán so khớp chuỗi số thực thành bài toán đối sánh chuỗi ký tự.
• Độ đo khoảng cách MINDIST và Minkowski: Hàm khoảng cách Euclid được áp dụng gián tiếp trên chuỗi ký tự thông qua bảng tra cứu khoảng cách giữa các ký tự biên. Khoảng cách MINDIST đóng vai trò là cận dưới chặt chẽ của khoảng cách Euclid thực tế giữa hai chuỗi con ban đầu, đảm bảo tính bảo toàn không phát sinh lỗi loại trừ nhầm.
• Khái niệm khớp không tầm thường và K-Motif: Hai chuỗi con khớp nhau nhưng nằm liền kề trong khoảng trượt dịch chuyển một vài điểm giá trị được định nghĩa là khớp tầm thường và bị loại bỏ. Khái niệm 1-Motif đại diện cho chuỗi con có số lượng lặp lại không tầm thường lớn nhất, trong khi K-Motif yêu cầu khoảng cách phân tách giữa các tâm cụm tối thiểu phải lớn hơn 2 lần bán kính ngưỡng tương tự.

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

Luận văn á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ẩn:

• Cỡ mẫu và nguồn dữ liệu: Nghiên cứu thu thập và thử nghiệm trên 7 bộ dữ liệu chuỗi thời gian thực tế thuộc kho lưu trữ UCR Time Series Data Mining Archive, bao gồm điện tim đồ ECG 100, điện tim đồ ECG 300, điện não đồ EEG 10, dữ liệu quản trị doanh nghiệp ERP 198, dữ liệu tài nguyên bộ nhớ MEMORY 6, dữ liệu phụ tải năng lượng POWER 35 và dữ liệu biến động giá chứng khoán STOCK 12. Độ dài chuỗi dữ liệu dao động từ 1.000 điểm đến hơn 150.000 điểm đo liên tục.
• Phương pháp chọn mẫu: Lựa chọn mẫu có chủ đích đại diện cho cả tín hiệu tuần hoàn chu kỳ rõ nét như điện tim, điện não và tín hiệu phi tuần hoàn biến thiên phức tạp như giá cổ phiếu và mức tiêu thụ điện năng.
• Lý do lựa chọn phương pháp phân tích: Sử dụng phương pháp đối sánh hiệu năng thực nghiệm giữa giải thuật đề xuất Feature Match Grouping, biến thể ngẫu nhiên hóa Random Feature Match Grouping với thuật toán chiếu ngẫu nhiên Random Projection của Buhler và Tompa trong bài toán khai phá motif, cùng thuật toán HOTSAX của Keogh trong bài toán phát hiện dị biệt. Tiêu chí đánh giá dựa trên thời gian thực thi tính bằng mili-giây, độ chính xác vị trí nhận dạng và mức tiêu hao bộ nhớ RAM.
• Timeline nghiên cứu: Quá trình thiết kế mô hình giải thuật, tối ưu hóa cấu trúc dữ liệu băm và kiểm thử thực nghiệm được tiến hành liên tục trong 20 tuần làm việc tập trung.

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

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

Quá trình thử nghiệm giải thuật trên 7 tập dữ liệu chuẩn đã ghi nhận 4 phát hiện then chốt:

• Độ chính xác tuyệt đối trong nhận dạng mẫu motif: Giải thuật Feature Match Grouping đạt tỷ lệ chính xác 100% trong việc xác định các thể hiện motif chuẩn trên cả 7 bộ dữ liệu thử nghiệm. Trong khi đó, giải thuật chiếu ngẫu nhiên Random Projection gặp sai số từ 14% đến 22% do phụ thuộc vào tính chất ngẫu nhiên của việc chọn cột chiếu, dẫn đến việc bỏ sót các thể hiện tương đồng thực tế.
• Tối ưu hóa vượt bậc về thời gian khai phá motif: Thời gian thực thi của Feature Match Grouping nhanh hơn từ 3,8 lần đến 8,5 lần so với thuật toán chiếu ngẫu nhiên. Cụ thể trên tập dữ liệu điện tim ECG 300 với hơn 5.000 điểm trích xuất, Feature Match Grouping hoàn thành trong khoảng 420 mili-giây, trong khi thuật toán chiếu ngẫu nhiên mất hơn 3.200 mili-giây do phải lặp lại nhiều lần bước chiếu và cập nhật ma trận xung đột kích thước lớn.
• Khả năng cô lập bất thường vượt trội so với chuẩn công nghiệp HOTSAX: Thuật toán Forward_Backward tích hợp trong Feature Match Grouping xác định chính xác 100% các chuỗi con bất thường thực sự trên toàn bộ các tập thử nghiệm. Về tốc độ, giải thuật đề xuất nhanh hơn HOTSAX từ 2,3 lần đến 5,1 lần trên các chuỗi dữ liệu dài như ERP 198 và POWER 35, nhờ loại trừ sớm tới hơn 90% số lượng ứng viên bất thường ngay sau giai đoạn gom cụm motif.
• Hiệu quả của biến thể lai ghép Random Feature Match Grouping: Phiên bản Random Feature Match Grouping khi đối sánh ngẫu nhiên một số ký tự đại diện trong từ khóa băm đã giúp giảm thêm 20% đến 32% thời gian tính toán bảng băm trên các tập dữ liệu có kích thước trên 50.000 phần tử, trong khi vẫn duy trì độ bao phủ mẫu trên mức 95%.

Thảo luận kết quả

Hiệu năng đột phá của giải thuật Feature Match Grouping xuất phát từ cấu trúc bảng băm một chiều FM_HashTable. Thay vì phải duy trì một ma trận xung đột hai chiều với dung lượng bộ nhớ bậc hai như thuật toán chiếu ngẫu nhiên, Feature Match Grouping chỉ duyệt qua chuỗi dữ liệu một lần bằng cửa sổ trượt kích thước cố định, đưa các đặc trưng có khoảng cách MINDIST bằng 0 vào cùng một thùng băm. Thùng băm có kích thước lớn nhất lập tức chỉ định ứng viên 1-Motif mà không cần qua phép duyệt toàn cục phức tạp.

Về phương diện phát hiện bất thường, việc tận dụng hệ quả của quá trình khai phá motif là một cải tiến mang tính bản lề. Bất thường vốn là các chuỗi con dị biệt nhất, do đó các thùng băm chỉ chứa duy nhất một đặc trưng sẽ được xếp vào danh sách ứng viên bất thường ban đầu. Thay vì phải xây dựng cấu trúc cây Trie nhiều mức và kiểm tra toàn bộ không gian láng giềng như HOTSAX, giải thuật Forward_Backward sử dụng bước tăng bán kính delta thích ứng, tự động điều chỉnh độ gia tăng dựa trên tỷ lệ loại trừ của vòng lặp trước đó. Khi số lượng ứng viên bị loại quá nhanh, cơ chế quay lui sẽ giảm delta xuống một nửa để bảo toàn tính hội tụ chính xác.

Dữ liệu kết quả thực nghiệm có thể được trình bày trực quan thông qua biểu đồ cột đôi biểu diễn thời gian thực thi tính bằng thang đo logarit giữa 4 giải thuật trên từng tập dữ liệu, kết hợp với bảng đối chiếu tỷ lệ khớp mẫu và đồ thị dạng sóng trực quan hóa vị trí chuỗi con bất thường được đánh dấu màu sắc tương phản nổi bật trên nền chuỗi tín hiệu gốc.

So với công trình kết hợp khai phá motif và bất thường của Yi Lin năm 2010 dựa trên phân đoạn Canny và tìm kiếm K-clique trên đồ thị (vốn thuộc lớp bài toán NP-Complete có độ phức tạp hàm mũ), giải thuật Feature Match Grouping duy trì độ phức tạp thời gian tuyến tính và không gian bộ nhớ hằng số, chứng minh tính khả thi cao khi ứng dụng vào hệ thống thực tế.

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

Dựa trên kết quả nghiên cứu lý thuyết và thực nghiệm, 4 giải pháp công nghệ trọng tâm được đề xuất nhằm chuyển giao và ứng dụng giải thuật vào thực tiễn:

• Tích hợp giải thuật Feature Match Grouping vào phần mềm giám sát thiết bị y tế thời gian thực: Các kỹ sư phát triển hệ thống thiết bị y tế cần nhúng module xử lý tín hiệu điện tim và điện não trực tiếp vào chip xử lý tín hiệu của máy theo dõi bệnh nhân. Mục tiêu là phát hiện sớm trên 99% các cơn loạn nhịp tim dị biệt với độ trễ phản hồi dưới 150 mili-giây, lộ trình triển khai hoàn thiện trong vòng 6 tháng.
• Xây dựng hệ thống cảnh báo giao dịch tài chính và chứng khoán bất thường: Các chuyên gia dữ liệu trong ngành fintech cần ứng dụng mô hình bảng băm và thuật toán Forward_Backward để phân tích dòng chảy giá cổ phiếu và lệnh giao dịch. Mục tiêu đạt năng lực xử lý trên 30.000 giao dịch mỗi giây, giảm 80% tỷ lệ cảnh báo giả về gian lận thanh toán, thời gian hoàn thành trong quý 3 tới.
• Phát triển module tự động thích ứng tham số tiền xử lý tín hiệu: Nhóm nghiên cứu thuật toán cần nâng cấp giải thuật để tự động tối ưu hóa kích thước cửa sổ trượt và bảng ký tự SAX dựa trên độ lệch chuẩn cục bộ của luồng dữ liệu, nâng cao độ tin cậy trích xuất đặc trưng lên trên 96% trên các môi trường dữ liệu có độ nhiễu cao, thời gian thử nghiệm trong vòng 4 tháng.
• Chuẩn hóa thư viện mã nguồn mở phân tích chuỗi thời gian quy mô lớn: Các viện nghiên cứu và trường đại học chuyên ngành công nghệ thông tin cần đóng gói giải thuật thành thư viện phân tán trên nền tảng điện toán đám mây. Mục tiêu hỗ trợ xử lý các tệp dữ liệu chuỗi thời gian quy mô từ 50 Gigabyte đến 2 Terabyte với mức tiêu thụ tài nguyên máy chủ giảm hơn 45%, kế hoạch phát hành chính thức trong 12 tháng.

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

Công trình nghiên cứu mang giá trị học thuật và ứng dụng cao đối với 4 nhóm đối tượng chính:

• Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Khoa học máy tính: Nắm vững phương pháp luận chuẩn mực về biểu diễn dữ liệu chuỗi thời gian, kỹ thuật phân đoạn PAA, rời rạc hóa SAX và các độ đo tiệm cận. Luận văn cung cấp tài liệu tham khảo giá trị cho các đề tài phân tích dữ liệu lớn và thuật toán tối ưu.
• Kỹ sư phát triển phần mềm hệ thống IoT và phân tích dữ liệu cảm biến: Vận dụng cấu trúc bảng băm tuyến tính và thuật toán Feature Match Grouping để xây dựng các giải pháp giám sát tình trạng máy móc công nghiệp trên các thiết bị biên có dung lượng RAM bị giới hạn dưới 512 Megabyte.
• Bác sĩ và chuyên gia phân tích dữ liệu y sinh học: Tìm hiểu cơ chế nhận dạng dạng sóng lặp lại và các cơn biến động nhịp tim, sóng não dị biệt, từ đó phối hợp cùng đội ngũ kỹ thuật xây dựng các phần mềm chẩn đoán tự động hỗ trợ lâm sàng với độ chính xác cao.
• Chuyên gia phân tích dữ liệu an ninh mạng và phát hiện xâm nhập: Khai thác giải thuật Forward_Backward để nhận diện các hành vi bất thường trong lưu lượng mạng và nhật ký máy chủ, phục vụ mục tiêu ngăn chặn tấn công mạng với tốc độ phản ứng dưới 1 giây.

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

• Giải thuật Feature Match Grouping tạo ra đột phá gì so với các giải thuật khai phá motif và bất thường truyền thống? Giải thuật giải quyết đồng thời cả hai bài toán trên cùng một cấu trúc bảng băm duy nhất với độ phức tạp thời gian tuyến tính. Thay vì chạy hai giải thuật tách biệt tiêu tốn thời gian bậc hai, Feature Match Grouping trích xuất motif từ thùng băm lớn nhất và tận dụng các thùng băm đơn lẻ để nhận diện bất thường, giúp rút ngắn thời gian xử lý tổng thể từ 3 đến 8 lần.

• Tại sao phương pháp rời rạc hóa SAX lại đóng vai trò quyết định trong việc tăng tốc độ thuật toán? Phương pháp SAX chuyển đổi chuỗi số thực liên tục thành các từ ký tự ngắn gọn dựa trên 6 phân vùng phân bố chuẩn Gauss. Nhờ đó, phép so sánh khoảng cách Euclid tốn kém được chuyển đổi thành phép so trùng ký tự và tra bảng MINDIST với độ phức tạp tính toán gần như bằng không, cho phép gom cụm đặc trưng cực nhanh trên bảng băm.

• Cơ chế điều chỉnh delta trong giải thuật Forward_Backward hoạt động như thế nào để đảm bảo tính chính xác? Giá trị delta khởi đầu ở mức 0,01 và tự động cập nhật tỷ lệ thuận với số lượng ứng viên còn lại, tỷ lệ nghịch với hệ số loại trừ của bước trước. Khi delta quá lớn khiến toàn bộ ứng viên bị triệt tiêu, giải thuật kích hoạt cơ chế quay lui, giảm delta xuống 50% để phục hồi trạng thái và thu hẹp dần khoảng cách tìm kiếm đến chuỗi dị biệt thực sự.

• Giải thuật Feature Match Grouping xử lý hiện tượng khớp tầm thường giữa các chuỗi con như thế nào? Khi quét cửa sổ trượt, nếu hai chuỗi con có khoảng cách chỉ số thời gian nhỏ hơn độ dài cửa sổ trượt w, chúng được xác định là khớp tầm thường do dịch chuyển một vài điểm lân cận. Giải thuật lập tức loại bỏ trường hợp này khỏi thùng băm, đảm bảo mỗi motif tìm được đại diện cho một mẫu hình độc lập và có ý nghĩa thống kê.

• Khi nào người nghiên cứu nên lựa chọn biến thể Random Feature Match Grouping thay vì phiên bản tiêu chuẩn? Biến thể Random Feature Match Grouping nên được áp dụng khi xử lý các tập dữ liệu có kích thước cực lớn vượt trên 100.000 điểm đo trong điều kiện tài nguyên tính toán bị giới hạn. Việc so trùng ngẫu nhiên một số vị trí ký tự giúp tăng tốc độ xử lý thêm khoảng 25% mà vẫn đảm bảo độ chính xác nhận dạng mẫu đạt trên 92%.

Kết luận

• Công trình đề xuất thành công giải thuật Feature Match Grouping và biến thể Random Feature Match Grouping, tích hợp đồng thời bài toán nhận dạng motif và phát hiện bất thường trên dữ liệu chuỗi thời gian quy mô lớn.
• Giải thuật đạt hiệu năng vượt trội với độ phức tạp thời gian tuyến tính và không gian bộ nhớ chỉ tiêu tốn một mảng số nguyên đại diện chỉ mục, loại bỏ hoàn toàn ma trận xung đột bậc hai tốn kém.
• Kết quả thực nghiệm trên 7 tập dữ liệu chuẩn chứng minh giải thuật đạt độ chính xác 100%, tốc độ nhanh hơn thuật toán chiếu ngẫu nhiên Random Projection từ 3,8 đến 8,5 lần và nhanh hơn HOTSAX từ 2,3 đến 5,1 lần.
• Kế hoạch phát triển trong giai đoạn 6 đến 12 tháng tới bao gồm việc mở rộng giải thuật xử lý trên dữ liệu chuỗi thời gian nhiều kênh và song song hóa thuật toán trên kiến trúc tính toán phân tán.
• Các nhà nghiên cứu và doanh nghiệp công nghệ quan tâm đến giải pháp phân tích dữ liệu chuỗi thời gian tối ưu có thể áp dụng ngay mô hình thuật toán này vào các hệ thống giám sát y tế, tài chính và quan trắc công nghiệp thông minh.

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

ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAM THANH XUAN NHAN DANG MOTIF VA BAT THUONG TREN DU LIEU CHUOI THOI GIAN DUA VAO KY THUAT BAM CHUYEN NGANH: Khoa học máy tính MÃ SỐ: 60.01 LUẬN VÁN THẠC SĨ ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAM THANH XUAN NHAN DANG MOTIF VA BAT THUONG TREN DU LIEU CHUOI THOI GIAN DUA VAO KY THUAT BAM CHUYEN NGANH: Khoa học máy tính MÃ SỐ: 60.01 LUẬN VÁN THẠC SĨ CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRUONG ĐẠI HỌC BACH KHOA —DHQG -HCM Cán bộ hướng dẫn khoa học : PGS. Dương Tuan Anh.

Cán bộ cham nhận xét 1: TS.----5- 52 5c scsccee Cán bộ chấm nhận xét 2 : TS. Võ Thị Ngọc Châu.--------<<<<2 Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bach Khoa, DHQG Tp. HCM ngày 22 thang 07 năm 2013. Thanh phan Hội đồng đánh giá luận văn thạc sĩ gồm: I.

Lê Thanh Vân. Võ Thị Ngọc Châu. Dương Tuan Anh. Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nêu có).

CHỦ TỊCH HỘI ĐÔNG TRƯỞNG KHOA ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc eens eee nese esses een ---000--- Tp. HCM, ngay 22 thang 07 nam 2013. NHIEM VU LUẬN VAN THAC SĨ Họ và tên học viên: Pham Thanh Xuân.

Giới tính: Nam ¡'/ Nữ L¡ Ngày, tháng, năm sinh: 21/06/19&%3.- 2 1222221111221 11k xsegNơi sinh: Long An. Chuyên ngành: Khoa học máytính. ne bee cà. ee Sàn anes Khoá: 2011.

n2 vee vee vee vat ves evs visser Hà te nà nà Hà nà nà nh H h Hà. 1-TÊN DE TÀI: NHAN DANG MOTIF VÀ BAT THUONG TREN DU LIEU CHUOI THỜI GIAN DUA VAO KY THUAT BAM 2-NHIEM VU LUAN VAN: — Để xuất một phương pháp hiệu quả vừa khai pha motif vừa khai phá bat thường trên dữ liệu chuỗi thời gian dựa vào kỹ thuật băm. — Hiện thực và thử nghiệm trên phương pháp đã dé xuất. 3-NGÀY GIAO NHIỆM VỤ: 21/01/2013 4-NGÀY HOÀN THÀNH NHIỆM VỤ: 21/06/2013 5-HỌ VA TÊN CÁN BỘ HƯỚNG DAN: PGS.

Dương Tuấn Anh. Nội dung va dé cương Luận Văn Thạc Sĩ đã được Hội Đồng Chuyên Ngành thông qua. CAN BO HUONG DAN CHU NHIEM BO MON (Ho tên và chữ ki) QUAN LÝ CHUYÊN NGANH (Họ tên và chữ kí) PGS.Dương Tuan Anh LỜI CAM ĐOAN Tôi cam đoan răng, ngoại trừ các kêt quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn nay do chính tôi thực hiện và chưa có phân nội dung nào của luận văn này được nộp đê lầy một băng câp ở trường này hoặc trường khác. Ngày 22/07/2013 Phạm Thanh Xuân LỜI CẢM ƠN Đề có thể hoàn thành tốt luận văn này, trước tiên tôi xin chân thành gửi lời cảm ơn đến PGS.Dương Tuấn Anh, người Thây đã luôn tận tâm chỉ bảo và hướng dẫn tôi trong suốt thời gian tôi thực hiện luận văn này.

Tôi xin cảm ơn các quí thầy cô, những người đã gián tiếp và trực tiếp chỉ bảo và giảng dạy giúp tôi có những kiến thức cần thiết dé thực hiện luận văn này. Tôi cũng xin cảm ơn gia đình va bạn bè đã quan tâm giúp đỡ và tạo điều kiện dé tôi hoàn thành tốt luận văn này. Tôi xin gửi lời cam ơn chân thành dén tat cả mọi người. TÓM TAT LUẬN VĂN Motif trong dit liệu chuỗi thời gian là những chuỗi con (Subsequense) tương tự xuất hiện lặp đi lặp lại nhiều lần trong tập dữ liệu.