So sánh hiệu quả của PAA, EPA trong tìm kiếm tương tự và SAX, ESAX trong nhận dạng chuỗi thời gian

Luận văn thạc sĩ so sánh hiệu quả hai phương pháp paa, epaa trong tìm kiếm tương tự và sax, esax trong nhận dạng chuỗi con dữ liệu thời gian.

• Tác giả: Hà Ngọc Minh
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: So Sánh Hiệu Quả PAA Và EPA Trong Tìm Kiếm Tương Tự Và SAX, ESAX Trong Nhận Dạng Chuỗi Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: TP.Hồ Chí Minh

Tóm tắt

I. Giới thiệu về PAA và EPA

Phương pháp PAA (Piecewise Aggregate Approximation) và EPA (Enhanced PAA) là hai kỹ thuật quan trọng trong việc xử lý và phân tích dữ liệu chuỗi thời gian. PAA giúp giảm số chiều của dữ liệu bằng cách chia chuỗi thời gian thành các đoạn và tính giá trị trung bình của mỗi đoạn. Ngược lại, EPA cải thiện phương pháp này bằng cách áp dụng các thuật toán tối ưu hơn, cho phép giữ lại nhiều thông tin hơn trong quá trình xấp xỉ. Việc so sánh hiệu quả giữa hai phương pháp này là cần thiết để xác định phương pháp nào phù hợp hơn cho các bài toán tìm kiếm tương tự. Theo nghiên cứu, EPA cho thấy hiệu quả cao hơn trong việc duy trì độ chính xác khi tìm kiếm tương tự trong các tập dữ liệu lớn.

1.1. Tìm kiếm tương tự với PAA và EPA

Trong bối cảnh tìm kiếm tương tự, PAA thường gặp khó khăn trong việc duy trì độ chính xác khi dữ liệu có nhiều biến động. Ngược lại, EPA đã chứng minh khả năng vượt trội hơn trong việc tìm kiếm các mẫu tương tự, nhờ vào việc tối ưu hóa quá trình xấp xỉ. Các thử nghiệm cho thấy rằng EPA có thể giảm thiểu sai số trong việc tìm kiếm tương tự, từ đó cải thiện hiệu suất tổng thể của hệ thống. Điều này đặc biệt quan trọng trong các ứng dụng thực tế như phân tích tài chính và giám sát sức khỏe, nơi mà độ chính xác là yếu tố quyết định.

II. Phương pháp SAX và ESAX

Phương pháp SAX (Symbolic Aggregate approXimation) và ESAX (Enhanced SAX) là hai kỹ thuật rời rạc hóa dữ liệu chuỗi thời gian. SAX chuyển đổi dữ liệu thành các ký hiệu, giúp giảm kích thước dữ liệu và tăng tốc độ xử lý. ESAX cải thiện SAX bằng cách sử dụng các thuật toán tối ưu hơn để tăng cường độ chính xác trong việc nhận dạng chuỗi thời gian. Việc so sánh hiệu quả giữa SAX và ESAX là cần thiết để xác định phương pháp nào mang lại lợi ích tốt hơn trong việc phát hiện chuỗi con bất đồng. Nghiên cứu cho thấy rằng ESAX có khả năng phát hiện các chuỗi con bất đồng một cách hiệu quả hơn, nhờ vào việc tối ưu hóa quá trình rời rạc hóa.

2.1. Nhận dạng chuỗi thời gian với SAX và ESAX

Trong lĩnh vực nhận dạng chuỗi thời gian, SAX thường gặp khó khăn trong việc phát hiện các chuỗi con bất đồng do độ chính xác thấp. ESAX đã chứng minh khả năng vượt trội hơn trong việc phát hiện các chuỗi con bất đồng, nhờ vào việc cải thiện quy trình rời rạc hóa. Các thử nghiệm cho thấy rằng ESAX có thể phát hiện các mẫu bất đồng một cách chính xác hơn, từ đó cải thiện hiệu suất của hệ thống. Điều này đặc biệt quan trọng trong các ứng dụng như giám sát an ninh và phân tích dữ liệu tài chính, nơi mà việc phát hiện bất đồng có thể giúp phát hiện các hành vi bất thường.

III. So sánh hiệu quả giữa PAA EPA SAX và ESAX

Việc so sánh hiệu quả giữa PAA, EPA, SAX và ESAX cho thấy rằng EPA và ESAX đều có những ưu điểm vượt trội so với các phương pháp truyền thống. Cụ thể, EPA cho thấy khả năng duy trì độ chính xác cao hơn trong tìm kiếm tương tự, trong khi ESAX cải thiện khả năng phát hiện chuỗi con bất đồng. Các thử nghiệm thực nghiệm cho thấy rằng cả hai phương pháp này đều có thể xử lý dữ liệu lớn một cách hiệu quả, giảm thiểu thời gian xử lý và tăng cường độ chính xác. Điều này mở ra hướng đi mới cho việc áp dụng các phương pháp này trong các lĩnh vực khác nhau như tài chính, y tế và an ninh.

3.1. Ứng dụng thực tiễn của PAA EPA SAX và ESAX

Các ứng dụng thực tiễn của PAA, EPA, SAX và ESAX rất đa dạng. Trong lĩnh vực tài chính, các phương pháp này có thể được sử dụng để phân tích xu hướng thị trường và phát hiện các mẫu bất thường trong dữ liệu giao dịch. Trong y tế, chúng có thể giúp theo dõi các chỉ số sức khỏe và phát hiện các dấu hiệu bất thường trong dữ liệu bệnh nhân. Hơn nữa, trong lĩnh vực an ninh, các phương pháp này có thể được áp dụng để phát hiện các hành vi đáng ngờ trong dữ liệu giám sát. Sự phát triển của các phương pháp này không chỉ nâng cao hiệu quả xử lý dữ liệu mà còn mở ra nhiều cơ hội mới cho nghiên cứu và ứng dụng trong thực tiễn.

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 -------------------- HÀ NGỌC MINH SO SÁNH HIỆU QUẢ HAI PHƢƠNG PHÁP PAA VÀ EPAA TRONG BÀI TOÁN TÌM KIẾM TƢƠNG TỰ, VÀ HAI PHƢƠNG PHÁP SAX VÀ ESAX TRONG BÀI TOÁN NHẬN DẠNG CHUỖI CON BẤT ĐỒNG TRONG DỮ LIỆU CHUỖI THỜI GIAN Chuyên ngành : Khoa học máy tính Mã số : 60 48 01 LUẬN VĂN THẠC SĨ TP.HỒ CHÍ MINH, tháng 12 năm 2011 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM Cán bộ hƣớng dẫn khoa học :. (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1 :. (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2 :.

(Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ) 1. 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 HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Hà Ngọc Minh MSHV: 09070451 Ngày, tháng, năm sinh: 26/09/1982 Nơi sinh: Hải Phòng Chuyên ngành: Khoa học máy tính Mã số : 60 48 01 TÊN ĐỀ TÀI: SO SÁNH HIỆU QUẢ HAI PHƢƠNG PHÁP PAA VÀ EPAA TRONG BÀI TOÁN TÌM KIẾM TƢƠNG TỰ, VÀ HAI PHƢƠNG PHÁP SAX VÀ ESAX TRONG BÀI TOÁN NHẬN DẠNG CHUỖI CON BẤT ĐỒNG TRONG DỮ LIỆU CHUỖI THỜI GIAN NHIỆM VỤ VÀ NỘI DUNG:.

NGÀY GIAO NHIỆM VỤ :. NGÀY HOÀN THÀNH NHIỆM VỤ:. CÁN BỘ HƢỚNG DẪN: PGS.Dƣơng Tuấn Anh Tp. CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRƢỞNG KHOA KH & KTMT (Họ tên và chữ ký) i 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 này là 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.năm 2011 Hà Ngọc Minh ii LỜI CẢM ƠN Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến PGS.

Dƣơng Tuấn Anh, ngƣời thầy đã tận tình hƣớng dẫn tôi trong suốt quá trình thời gian học cao học và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này. Tôi cũng xin cảm ơn gia đình, bạn bè và đơn vị của tôi đã động viên và tạo mọi điều kiện tốt nhất để tôi có thể tiếp tục theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành tặng thành quả của luận văn này cho bố mẹ tôi. Nhờ công lao dƣỡng dục của bố mẹ mà con mới có đƣợc thành quả nhƣ ngày hôm nay.

Con xin hứa sẽ tiếp tục cố gắng phấn đấu để vƣơn cao hơn nữa. iii TÓM TẮT LUẬN VĂN Biểu diễn dữ liệu chuỗi thời gian ngày càng đóng vai trò quan trọng trong các bài toán khai phá dữ liệu chuỗi thời gian. Mặc dù trong thời gian qua có rất nhiều các phƣơng pháp biểu diễn dữ liệu chuỗi thời gian đƣợc đề xuất và cơ bản đã giải quyết đƣợc các bài toán thực tế liên quan đến dữ liệu chuỗi thời gian. Tuy nhiên, lĩnh vực nghiên cứu, so sánh bằng thực nghiệm hiệu quả của các phƣơng pháp biểu diễn dữ liệu chuỗi thời gian còn khiêm tốn và chƣa đƣợc quan tâm thích đáng.

Từ đó sự thiếu thông tin về ƣu khuyết điểm của các phƣơng pháp biểu diễn dữ liệu chuỗi thời gian sẽ gây khó khăn trong việc lựa chọn phƣơng pháp biểu diễn để làm các nhiệm vụ khai phá dữ liệu chuỗi thời gian. Xuất phát từ thực trạng trên, đề tài lần này sẽ tập trung vào lĩnh vực nghiên cứu, so sánh các phƣơng pháp biểu diễn dữ liệu chuỗi thời gian trong các nhiệm vụ khai phá dữ liệu chuỗi thời gian. Chúng tôi tiến hành so sánh hiệu quả của EPAA và PAA khi giải quyết bài toán tìm kiếm tƣơng tự có ứng dụng cấu trúc chỉ mục R*-tree; tiếp đó so sánh hiệu quả của ESAX và SAX khi giải quyết bài toán tìm chuỗi con bất đồng. Qua thực nghiệm cho thấy, phƣơng pháp EPAA hiệu quả hơn phƣơng pháp PAA khi ứng dụng vào bài toán tìm kiếm tƣơng tự; phƣơng pháp ESAX hiệu quả hơn phƣơng pháp SAX khi ứng dụng vào bải toán tìm chuỗi con bất đồng.

iv ABSTRACT The representation of time series plays more and more important role in time series data mining problems. Although recently several time series representation methods have been proposed and basically they helped to solve many problems related to time series data. However, the empirical comparison on the effectiveness of these time series representation methods still has been modest and has not attracted adequate attention. Therefore, the lack of information about the advantages/disadvantages of the representation methods may incur difficulties in choosing the suitable representation methods for mining time series data.

This thesis will focus on comparing the efficiency of some representation methods in the time series data. We empirically compare the effectiveness of the two dimensionality reduction methods, EPAA and PAA, in the similarity search with applying R*-tree index structure and the efficiency of the two discretization methods, ESAX and SAX, in the discord discovery. Experiments show that EPAA is more effective than PAA in the similarity search; and ESAX is more effective than SAX in the discord discovery. v MỤC LỤC LỜI CAM ĐOAN.

ii TÓM TẮT LUẬN VĂN. iv MỤC LỤC. v MỤC LỤC HÌNH .ix MỤC LỤC BẢNG. xii Chƣơng 1 Phát biểu vấn đề .1 Dữ liệu chuỗi thời gian .1 Tìm kiếm tƣơng tự: .2 Phát hiện chuỗi con “bất đồng”.3 Các phƣơng pháp biểu diễn xấp xỉ .2 Mục tiêu và giới hạn của đề tài.

Giải quyết vấn đề thứ nhất. Giải quyết vấn đề thứ hai .3 Tóm lƣợc những kết quả đạt đƣợc .1 Hệ thống tìm kiếm tƣơng tự .2 Hệ thống tìm chuỗi con “bất đồng” .4 Cấu trúc của luận văn .9 Chƣơng 2 Các công trình liên quan .1 Các công trình về độ đo tƣơng tự.2 Độ đo xoắn thời gian động DTW .2 Các công trình về biểu diễn chuỗi thời gian .1 Các phƣơng pháp thu gi ảm số chiều .2 Các phƣơng pháp rời rạc hóa .3 Các công trình về cấu trúc chỉ mục.4 Các thuật toán phát hiện chuỗi con “bất đồng” .1 Giải thuật hệ thống miễn dịch nhân tạo IMM .2 Giải thuật dựa trên cây TSA .3 Giải thuật Tarzan.4 Giải thuật BFDD .5 Giải thuật HDD .6 Giải thuật HOT SAX. 26 Chƣơng 3 Cơ sở lý thuyết .1 Phƣơng pháp rời rạc hóa SAX.2 Phƣơng pháp rời rạc ESAX .3 Giải thuật BFDD .4 Giải thuật HDD .5 Giải thuật HOT SAX .1 Mô tả cấu trúc dữ liệu.2 Xây dựng heuristic ngoài .3 Xây dựng heuristic trong .4 Cách tối ƣu khác .6 Cấu trúc chỉ mục R*-tree .1 Thêm nút mới trên cây R*-tree .2 Tìm kiếm trên R*-tree. 43 Chƣơng 4 Hệ thống ứng dụng .1 Hệ thống tìm kiếm tƣơng tự.1 Kiến trúc hệ thống .2 Khối tạo dữ liệu.3 Khối biểu diễn dữ liệu .4 Khối cấu trúc dữ liệu .5 Khối tìm kiếm tƣơng tự.2 Hệ thống phát hiện chuỗi con bất đồng .1 Kiến trúc hệ thống .2 Khối tạo dữ liệu (như phần 4.3 Khối biểu diễn dữ liệu .4 Khối cấu trúc dữ liệu .5 Khối tìm kiếm chuỗi con bất đồng.

55 Chƣơng 5 Thực nghiệm.1 Hệ thống tìm kiếm tƣơng tự.1 Tiêu chuẩn tiến hành thực nghiệm.2 Đánh giá các kết quả thực nghiệm.2 Hệ thống tìm kiếm chuỗi con “bất đồng” .1 Tiêu chuẩn tiến hành thực nghiệm.2 Đánh giá các kết quả thực nghiệm. 70 viii Chƣơng 6 Kết luận .2 Những đóng góp của đề tài .3 Hƣớng phát triển. 80 Tài liệu tham khảo. 81 PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT.

A PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG. C ix MỤC LỤC HÌNH Hình 1.1 Đƣờng cong biểu diễn chuỗi thời gian.2 Minh họa chuỗi con bất đồng trong dữ liệu điện tâm đồ của con ngƣời .1 Tính khoảng cách theo độ đo Euclid .2 Minh họa độ đo xoắn thời gian động DTW .3 Hàm chặn dƣới LB_Keogh .4 Chuối thời gian X đƣợc biểu diến bằng PAA.1 Chuỗi thời gian đƣợc rời rạc hóa theo SAX.2 Dữ liệu tài chính biểu diễn bằng SAX .3 Dữ liệu tài chính biểu diễn bằng ESAX .4 Hai cấu trúc dữ liệu hỗ trợ cho heuristics ngoài và trong.5 Cây R*-tree với 12 điểm.6 Lƣu đồ giải thuật thêm mới vào cây R*-tree .7 Chọn nút lá thêm một phần tử vào nút.8 Thêm một phần tử vào nút đã đầy .9 Cách chia nút thành 2 nhóm thành phần.10 Tìm kiếm vùng trên cây R*-tree.1 Kiến trúc hệ thống tìm kiếm tƣơng tự.2 Các bƣớc trong quá trình tìm kiếm tƣơng tự.Error! Bookmark not defined.3 Hệ thống phát hiện chuỗi con bất đồng .1 Độ chặt chặn dƣới của PAA và EPAA trên dữ liệu STOCK .2 Độ chặt chặn dƣới của PAA và EPAA trên dữ liệu AEM.3 Độ chặt chặn dƣới của PAA và EPAA trên dữ liệu EEG.4 Độ chặt chặn dƣới của PAA và EPAA trên dữ liệu POWER .5 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu AEM .6 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu EEG .7 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu ERP.8 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu POWER .9 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu BOUNDERDIALY .10 Tỷ lệ thu giảm truy suất của PAA và EPAA trên dữ liệu STOCK .11 Thời gian thực thi của PAA và EPAA trên dữ liệu AEM .12 Thời gian thực thi của PAA và EPAA trên dữ liệu EEG .12 Thời gian thực thi của PAA và EPAA trên dữ liệu ERP.13 Thời gian thực thi của PAA và EPAA trên dữ liệu POWER.14 Thời gian thực thi của PAA và EPAA trên dữ liệu BOUNDERDIALY 68 Hình 5.15 Thời gian thực thi của PAA và EPAA trên dữ liệu STOCK .16 Số lần gọi hàm tính khoảng cách của HOT SAX và HOTESAX trên dữ liệu AEM .17 Thời gian thực thi HOTSAX và HOTESAX trên dữ liệu AEM .18 Số lần gọi hàm tính khoảng cách của HOT SAX và HOTESAX trên dữ liệu ECG .19 Thời gian thực thi HOTSAX và HOTESAX trên dữ liệu STOCK .20 Số lần gọi hàm tính khoảng cách của HOT SAX và HOTESAX trên dữ liệu EEG.21 Thời gian thực thi HOTSAX và HOTESAX trên dữ liệu EEG.22 Số lần gọi hàm tính khoảng cách của HOT SAX và HOTESAX trên dữ liệu ERP .