Luận văn so sánh PAA, EPAA và SAX, ESAX trong chuỗi thời gian tại Đại học Bách Khoa

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

Mục lục chi tiết

• LỜI CAM ĐOAN
• TÓM TẮT LUẬN VĂN
• MỤC LỤC HÌNH
• MỤC LỤC BẢNG
• 1. Chương 1: Phát biểu vấn đề
• 1.1. Dữ liệu chuỗi thời gian
• 1.1.1. Tìm kiếm tương tự
• 1.1.2. Phát hiện chuỗi con “bất đồng”
• 1.1.3. Các phương pháp biểu diễn xấp xỉ
• 1.2. Mục tiêu và giới hạn của đề tài
• 1.2.1. Giải quyết vấn đề thứ nhất
• 1.2.2. Giải quyết vấn đề thứ hai
• 1.3. Tóm lược những kết quả đạt được
• 1.3.1. Hệ thống tìm kiếm tương tự
• 1.3.2. Hệ thống tìm chuỗi con “bất đồng”
• 1.4. Cấu trúc của luận văn
• 2. Chương 2: Các công trình liên quan
• 2.1. Các công trình về độ đo tương tự
• 2.1.1. Độ đo xoắn thời gian động DTW
• 2.2. Các công trình về biểu diễn chuỗi thời gian
• 2.2.1. Các phương pháp thu giảm số chiều
• 2.2.2. Các phương pháp rời rạc hóa
• 2.3. Các công trình về cấu trúc chỉ mục
• 2.4. Các thuật toán phát hiện chuỗi con “bất đồng”
• 2.4.1. Giải thuật hệ thống miễn dịch nhân tạo IMM
• 2.4.2. Giải thuật dựa trên cây TSA
• 2.4.3. Giải thuật Tarzan
• 2.4.4. Giải thuật BFDD
• 2.4.5. Giải thuật HDD
• 2.4.6. Giải thuật HOT SAX
• 3. Chương 3: Cơ sở lý thuyết
• 3.1. Phương pháp rời rạc hóa SAX
• 3.2. Phương pháp rời rạc ESAX
• 3.3. Giải thuật BFDD
• 3.4. Giải thuật HDD
• 3.5. Giải thuật HOT SAX
• 3.5.1. Mô tả cấu trúc dữ liệu
• 3.5.2. Xây dựng heuristic ngoài
• 3.5.3. Xây dựng heuristic trong
• 3.5.4. Cách tối ưu khác
• 3.6. Cấu trúc chỉ mục R*-tree
• 3.6.1. Thêm nút mới trên cây R*-tree
• 3.6.2. Tìm kiếm trên R*-tree
• 4. Chương 4: Hệ thống ứng dụng
• 4.1. Hệ thống tìm kiếm tương tự
• 4.1.1. Kiến trúc hệ thống
• 4.1.2. Khối tạo dữ liệu
• 4.1.3. Khối biểu diễn dữ liệu
• 4.1.4. Khối cấu trúc dữ liệu
• 4.1.5. Khối tìm kiếm tương tự
• 4.2. Hệ thống phát hiện chuỗi con bất đồng
• 4.2.1. Kiến trúc hệ thống
• 4.2.2. Khối tạo dữ liệu (như phần 4.1.2)
• 4.2.3. Khối biểu diễn dữ liệu
• 4.2.4. Khối cấu trúc dữ liệu
• 4.2.5. Khối tìm kiếm chuỗi con bất đồng
• 5. Chương 5: Thực nghiệm
• 5.1. Hệ thống tìm kiếm tương tự
• 5.1.1. Tiêu chuẩn tiến hành thực nghiệm
• 5.1.2. Đánh giá các kết quả thực nghiệm
• 5.2. Hệ thống tìm kiếm chuỗi con “bất đồng”
• 5.2.1. Tiêu chuẩn tiến hành thực nghiệm
• 5.2.2. Đánh giá các kết quả thực nghiệm
• 6. Chương 6: Kết luận
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triể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ề 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.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian là thành phần cốt lõi trong các hệ sinh thái công nghệ hiện đại, từ giám sát tài chính định lượng đến phân tích y tế kỹ thuật số. Dự án thiên văn học MACHO minh chứng cho thách thức này khi quản lý cơ sở dữ liệu lên đến 0,5 terabyte và ghi nhận tốc độ tăng trưởng từ 2 đến 5 gigabyte mỗi ngày. Khi kích thước dữ liệu mở rộng đến hàng triệu điểm đo, việc truy xuất đĩa ngoài liên tục tạo ra hiện tượng thắt cổ chai nghiêm trọng trong xử lý I/O. Hai tác vụ nền tảng trong khai phá dữ liệu là tìm kiếm tương tự và phát hiện chuỗi con bất đồng thường đối mặt với sự suy giảm hiệu năng do không gian dữ liệu nhiều chiều.

Mục tiêu trọng tâm của nghiên cứu là đánh giá thực nghiệm và định lượng hiệu quả giữa phương pháp xấp xỉ gộp từng đoạn truyền thống PAA với phiên bản mở rộng EPAA khi tích hợp cấu trúc chỉ mục không gian R*-tree. Đồng thời, đề tài tiến hành phân tích đối sánh giữa phương pháp rời rạc hóa ký hiệu SAX và phiên bản mở rộng ESAX trên nền giải thuật tìm kiếm heuristic HOT SAX. Phạm vi thực nghiệm bao quát 6 bộ dữ liệu chuẩn đa lĩnh vực gồm STOCK, ECG, EEG, ERP, POWER và BOULDERDAILY với kích thước mẫu từ 1.000 đến hơn 100.000 điểm thời gian.

Nghiên cứu mang ý nghĩa thực tiễn lớn khi cung cấp bằng chứng thực nghiệm cụ thể giúp giải quyết bài toán lựa chọn kiến trúc tối ưu trong khai phá dữ liệu lớn. Kết quả định lượng cho thấy phương pháp EPAA giúp tăng độ chặt của cận dưới khoảng 15% đến 35%, qua đó giảm tải từ 20% đến 45% số lượt truy xuất nút lá trên cây chỉ mục R*-tree so với PAA chuẩ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 được xây dựng dựa trên các nền tảng lý thuyết và mô hình giải thuật toán học chuẩn mực trong khai thác dữ liệu chuỗi thời gian:

1. Lý thuyết thu giảm số chiều chuỗi thời gian: Khảo sát mô hình xấp xỉ gộp từng đoạn PAA chia chuỗi thời gian độ dài $n$ thành $w$ phân đoạn bằng nhau và đại diện mỗi đoạn bằng một giá trị trung bình số học đơn lẻ. Đối trọng với PAA là phương pháp EPAA, trong đó mỗi phân đoạn được biểu diễn bởi một bộ ba giá trị gồm giá trị nhỏ nhất, giá trị trung bình và giá trị lớn nhất ($s_{\min}, s_{\text{mean}}, s_{\max}$).
2. Lý thuyết rời rạc hóa chuỗi ký hiệu: Phương pháp SAX chuẩn hóa chuỗi dữ liệu theo phân bố Gauss chuẩn $\mathcal{N}(0,1)$, chia không gian thành $a$ vùng xác suất tương đương ($a$ từ 3 đến 10 ký tự) thông qua bảng điểm ngắt cố định. Phương pháp mở rộng ESAX kế thừa cơ chế ánh xạ điểm ngắt nhưng mã hóa mỗi phân đoạn thành chuỗi 3 ký tự liên tiếp nhằm duy trì biên độ cực trị của tín hiệu.
3. Độ đo tương tự và hàm chặn dưới: Sử dụng độ đo khoảng cách Euclid trong không gian nguyên thủy cùng hàm khoảng cách $\text{MINDIST}$ và hàm khoảng cách $\text{DR}$ trong không gian thu giảm. Các hàm này đáp ứng điều kiện chặn dưới nghiêm ngặt nhằm triệt tiêu hoàn toàn sai số loại bỏ nhầm phần tử phù hợp.
4. Cấu trúc chỉ mục R-tree và giải thuật Heuristic HOT SAX*: Ứng dụng cấu trúc cây cân bằng đa chiều R*-tree để gom nhóm các hình chữ nhật bao nhỏ nhất MBR, kết hợp thuật toán HOT SAX dùng cấu trúc cây gia tố Augmented Trie nhằm thiết lập thứ tự duyệt chuỗi con ở vòng lặp ngoài và vòng lặp trong.

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

Nguồn dữ liệu thực nghiệm được thu thập từ kho dữ liệu chuỗi thời gian chuẩn của Đại học California Riverside (UCR) và các hệ thống đo đạc thực tế, đại diện cho 6 miền ứng dụng: dữ liệu tài chính STOCK, điện tâm đồ ECG, điện não đồ EEG, điện thế gợi liên quan sự kiện ERP, phụ tải điện lưới POWER và dữ liệu khí tượng BOULDERDAILY. Tổng dung lượng tập mẫu dao động từ 1.000 đến 100.000 điểm thời gian liên tục.

Phương pháp chọn mẫu sử dụng kỹ thuật cửa sổ trượt phân đoạn kết hợp trích xuất ngẫu nhiên các chuỗi con có chiều dài cố định $n \in {64, 128, 256, 512}$. Kỹ thuật này tái hiện chân thực các thao tác truy vấn chuỗi con và tìm kiếm mẫu bất thường cục bộ trong môi trường vận hành thực tế.

Quy trình phân tích được thiết kế theo mô hình 4 khối chức năng: Khối tạo dữ liệu thực nghiệm, Khối biểu diễn dữ liệu (PAA/EPAA, SAX/ESAX), Khối cấu trúc dữ liệu (R*-tree, Trie gia tố) và Khối tìm kiếm thực thi. Lý do lựa chọn mô hình này là khả năng cô lập các nhân tố ảnh hưởng, cho phép đo lường chính xác các chỉ số định lượng bao gồm độ chặt chặn dưới, tỷ lệ thu giảm truy xuất đĩa, số lần gọi hàm khoảng cách và thời gian CPU trên cùng một nền tảng phần cứng.

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

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

Quá trình kiểm chứng thực nghiệm trên 6 bộ dữ liệu đã xác lập 4 phát hiện quan trọng:

1. Độ chặt chặn dưới của EPAA vượt trội hoàn toàn so với PAA: Trên các tập dữ liệu có biên độ biến thiên mạnh như STOCK và POWER, hàm khoảng cách của EPAA đạt độ chặt tiệm cận khoảng cách Euclid cao hơn từ 15% đến 35% so với hàm khoảng cách PAA. Điều này giúp không gian biểu diễn phản ánh chính xác hình dạng gốc của dữ liệu.
2. Tối ưu hóa tỷ lệ thu giảm truy xuất trên cây chỉ mục R-tree*: Nhờ duy trì bộ ba giá trị cực trị và trung bình, EPAA tạo ra các vùng bao MBR chặt chẽ hơn. Khi thực hiện truy vấn so trùng chuỗi con, EPAA giúp cây R*-tree giảm từ 20% đến 45% số trang đĩa cần đọc vào bộ nhớ chính so với phương pháp PAA.
3. Tiết kiệm thời gian thực thi CPU trong bài toán tìm kiếm tương tự: Tổng thời gian xử lý truy vấn của hệ thống tích hợp EPAA và R*-tree giảm từ 18% đến 32% trên các tập dữ liệu EEG và AEM khi kích thước phân đoạn $w$ dao động từ 4 đến 16.
4. Hiệu năng phát hiện chuỗi con bất đồng của HOT ESAX: Trong bài toán nhận dạng dị thường bằng thuật toán HOT SAX, phương pháp mã hóa ESAX giúp giảm từ 30% đến 60% số lần gọi hàm tính khoảng cách trong không gian nguyên thủy trên tập dữ liệu y tế ECG và EEG. Nhờ khả năng phân biệt mẫu thức cao của 3 ký tự, heuristic vòng lặp ngoài xác định ứng viên bất đồng nhanh hơn, giúp thời gian thực thi CPU tổng thể giảm từ 22% đến 40%.

Thảo luận kết quả

Hiệu quả vượt trội của EPAA và ESAX xuất phát từ việc giải quyết triệt để sự mất mát thông tin cục bộ trong biểu diễn dữ liệu. Trong khi PAA chỉ tính toán một giá trị trung bình duy nhất khiến các dao động biên độ lớn bị làm phẳng, EPAA lưu giữ trực tiếp giá trị đỉnh cao nhất và đáy thấp nhất. Đối với các dữ liệu đặc thù như nhịp tim bất thường hoặc sóng điện não co giật, biên độ cực trị đóng vai trò quyết định để phân biệt chuỗi bình thường và chuỗi dị thường.

So với các công bố ban đầu của nhóm nghiên cứu Lin và Keogh vào năm 2003 vốn chỉ tập trung vào biểu diễn PAA và SAX nguyên bản, kết quả của luận văn này đã mở rộng phạm vi ứng dụng của đề xuất Lkhagva năm 2006 từ lĩnh vực tài chính sang toàn bộ các miền dữ liệu y sinh học và kỹ thuật điện. Mặc dù EPAA làm tăng số chiều biểu diễn cục bộ lên gấp 3 lần cho mỗi phân đoạn, nhưng sự thu hẹp không gian bao MBR trong cây R*-tree đã bù đắp hoàn toàn chi phí lưu trữ phụ trợ, mang lại lợi thế vượt trội về hiệu năng I/O.

Dữ liệu thực nghiệm được tổng hợp và biểu diễn trực quan thông qua các biểu đồ đường đối sánh đa trục. Trên đồ thị biểu diễn thời gian CPU theo chiều dài chuỗi con từ 64 đến 512 điểm, đường cong của HOT ESAX luôn nằm thấp hơn đáng kể so với HOT SAX chuẩn. Tương tự, biểu đồ cột so sánh tỷ lệ thu giảm truy xuất cho thấy các cột giá trị của EPAA duy trì mức độ cắt tỉa không gian tìm kiếm ổn định trên 75% xuyên suốt các tập kiểm thử STOCK và POWER.

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

Dựa trên kết quả nghiên cứu, 4 giải pháp công nghệ và lộ trình ứng dụng cụ thể được đề xuất:

1. Tích hợp EPAA vào hệ thống giao dịch tài chính định lượng: Đội ngũ kỹ sư dữ liệu tài chính cần triển khai biểu diễn EPAA vào các hệ thống giám sát giá chứng khoán thời gian thực. Mục tiêu giảm độ trễ phản hồi truy vấn xuống dưới 50 mili-giây trên tập dữ liệu 10 triệu biến động giá, thực hiện trong lộ trình 3 tháng.
2. Ứng dụng HOT ESAX trong thiết bị vi mạch y tế thông minh: Nhóm phát triển phần mềm thiết bị y tế nên nhúng giải thuật HOT ESAX vào các máy đo điện tâm đồ ECG và điện não đồ EEG cầm tay. Mục tiêu cắt giảm 30% mức tiêu thụ năng lượng tính toán và rút ngắn thời gian cảnh báo rối loạn nhịp tim xuống dưới 1 giây, thực hiện trong giai đoạn 6 tháng.
3. Chuẩn hóa cấu trúc chỉ mục R-tree cho hệ thống cơ sở dữ liệu IoT*: Bộ phận quản trị cơ sở dữ liệu công nghiệp cần áp dụng mô hình phân vùng chỉ mục không gian R*-tree kết hợp EPAA cho hệ thống cảm biến lưới điện thông minh. Mục tiêu tiết kiệm 40% chi phí đọc ghi bộ nhớ ngoài I/O với quy mô hơn 50.000 điểm đo, hoàn thành trong vòng 4 tháng.
4. Xây dựng khung xử lý chuỗi thời gian đa mức phân giải mở rộng: Các phòng thí nghiệm và trung tâm nghiên cứu AI nên kết hợp ưu điểm của chỉ mục đa phân giải iSAX với kỹ thuật mã hóa cực trị ESAX. Mục tiêu tăng gấp 2 lần thông lượng xử lý các truy vấn phân tán quy mô terabyte, triển khai trong khung thời gian 12 tháng.

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

Nội dung và mã nguồn thuật toán của luận văn là tài liệu tham khảo giá trị cho 4 nhóm chuyên môn:

1. Kỹ sư dữ liệu và chuyên gia AI trong lĩnh vực Fintech: Nắm bắt phương pháp biểu diễn dữ liệu tài chính không làm mất các bước nhảy giá cực trị, tối ưu hóa các mô hình truy vấn tương tự xu hướng thị trường và phát hiện giao dịch gian lận.
2. Lập trình viên và nhà nghiên cứu hệ thống y tế số: Ứng dụng giải thuật HOT ESAX để xây dựng các thuật toán tự động nhận diện sóng bệnh lý bất thường trong tín hiệu điện tâm đồ và điện não đồ thời gian thực.
3. Kiến trúc sư hệ thống IoT và phân tích dữ liệu lớn: Khai thác mô hình kết hợp giữa EPAA và cây chỉ mục R*-tree để tối ưu hóa việc lưu trữ, lập chỉ mục và truy xuất dữ liệu cảm biến đo đạc công nghiệp quy mô lớn.
4. 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ư một tài liệu chuẩn mực về phương pháp luận nghiên cứu thực nghiệm, thiết kế kiến trúc phân hệ xử lý dữ liệu chuỗi thời gian và cách thức đánh giá hiệu năng giải thuật khai phá dữ liệu.

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

Điểm khác biệt cốt lõi giữa phương pháp PAA và EPAA là gì?
PAA chỉ sử dụng một giá trị trung bình số học duy nhất để đại diện cho toàn bộ điểm dữ liệu trong một phân đoạn. Ngược lại, EPAA mở rộng biểu diễn thành một bộ ba giá trị gồm giá trị nhỏ nhất, trung bình và lớn nhất. Việc giữ lại hai điểm cực trị giúp EPAA bảo toàn hình thái biên độ, đạt độ chặt chặn dưới cao hơn từ 15% đến 35% trên các dữ liệu biến động mạnh.

Tại sao phương pháp rời rạc hóa SAX lại dựa trên phân bố chuẩn Gauss?
Nghiên cứu thực nghiệm trên nhiều tập dữ liệu chuẩn cho thấy khi các chuỗi con được chuẩn hóa về giá trị trung bình bằng 0 và độ lệch chuẩn bằng 1, phân bố biên độ tuân theo quy luật Gauss. Việc chia các điểm ngắt theo diện tích xác suất tương đương dưới đường cong Gauss đảm bảo các ký tự trong bảng chữ cái có tần suất xuất hiện đồng đều, tránh hiện tượng tập trung ký tự làm suy giảm hiệu quả tìm kiếm.

Giải thuật HOT ESAX tăng tốc độ phát hiện chuỗi con bất đồng bằng cơ chế nào?
HOT ESAX sử dụng 3 ký tự mã hóa cho mỗi đoạn để xây dựng cấu trúc cây gia tố Augmented Trie. Các chuỗi ký tự có tần suất xuất hiện thấp nhất được heuristic vòng lặp ngoài ưu tiên kiểm tra trước, giúp nhanh chóng tìm ra giá trị khoảng cách tốt nhất. Điều này tạo điều kiện cho vòng lặp trong ngắt sớm, giúp cắt giảm từ 30% đến 60% số lần tính toán khoảng cách thực tế.

Cấu trúc cây R-tree hỗ trợ gì cho bài toán tìm kiếm tương tự chuỗi thời gian?*
Cây R*-tree tổ chức dữ liệu thu giảm nhiều chiều dưới dạng các hình chữ nhật bao nhỏ nhất MBR phân tầng. Khi nhận truy vấn, hệ thống dựa vào hàm khoảng cách chặn dưới để loại bỏ hàng loạt các nhánh cây không chứa kết quả tiềm năng mà không cần giải mã dữ liệu gốc, giúp giảm từ 20% đến 45% số lượt truy cập đĩa ngoài.

Khi nào nên ưu tiên sử dụng SAX thay vì ESAX?
SAX là lựa chọn tối ưu khi xử lý các chuỗi thời gian có độ ồn thấp, phân bố dữ liệu phẳng và yêu cầu tiết kiệm tối đa không gian lưu trữ bộ nhớ (chỉ 1 byte cho mỗi phân đoạn thay vì 3 byte như ESAX). Với các bài toán phân lớp tổng quát không quá phụ thuộc vào giá trị cực trị, SAX giúp tối ưu hóa dung lượng lưu trữ trên các vi điều khiển có tài nguyên hạn chế.

Kết luận

• Nghiên cứu đã thực hiện đánh giá thực nghiệm toàn diện và có hệ thống giữa hai cặp phương pháp biểu diễn dữ liệu chuỗi thời gian tiêu biểu: PAA đối trọng EPAA và SAX đối trọng ESAX.
• Hệ thống tìm kiếm tương tự tích hợp EPAA và cấu trúc chỉ mục R*-tree đã chứng minh tính ưu việt khi cải thiện độ chặt chặn dưới lên đến 35% và giảm tải tối đa 45% chi phí I/O truy xuất đĩa ngoài.
• Giải thuật HOT ESAX thể hiện sự vượt trội trong phát hiện chuỗi con bất đồng khi cắt giảm tới 60% số lần gọi hàm đo khoảng cách nguyên thủy và tiết kiệm 40% thời gian thực thi CPU so với HOT SAX chuẩn.
• Kết quả nghiên cứu khẳng định tầm quan trọng của việc bảo tồn thông tin cực trị cục bộ trong các tác vụ khai phá dữ liệu có độ nhạy cảm cao như phân tích tài chính và chẩn đoán y sinh học.
• Lộ trình mở rộng nghiên cứu trong 6 đến 12 tháng tới sẽ tập trung vào việc tự động hóa tham số hóa kích thước phân đoạn $w$ và phát triển khung chỉ mục lai đa mức phân giải cho môi trường điện toán đám mây phân tán.

Để nâng cao hiệu năng cho hệ thống khai phá dữ liệu lớn của cơ quan hoặc doanh nghiệp, các kỹ sư và nhà nghiên cứu có thể tải về tài liệu toàn văn và áp dụng ngay mô hình thuật toán EPAA cùng HOT ESAX vào quy trình xử lý dữ liệu chuỗi thời gian thực tế.

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.