Cải Tiến Giải Thuật 1-NN Phân Lớp Dữ Liệu Chuỗi Thời Gian Dựa Vào Kỹ Thuật Nhánh Và Cận

Luận văn thạc sĩ kỹ thuật nghiên cứu máy tính cải tiến giải thuật 1 nn phân lớp dữ liệu chuỗi thời gian dựa vào một kỹ thuật nhánh và cận, khảo sát thực trạng, phân tích nguyên

• Tác giả: Đoàn Dũ
• 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: Cải Tiến Giải Thuật 1-NN Phân Lớp Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG BIỂU
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Ý nghĩa của đề tài
• 1.3. Mục tiêu và nhiệm vụ của đề tài
• 1.4. Những kết quả đạt được
• 1.5. Bố cục luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Dữ liệu chuỗi thời gian
• 2.2. Vấn đề phân lớp dữ liệu chuỗi thời gian
• 2.3. Giải thuật k-lân cận gần nhất
• 2.3.1. Giới thiệu giải thuật k-lân cận gần nhất
• 2.3.2. Áp dụng giải thuật k-lân cận gần nhất vào bài toán phân lớp
• 2.4. Kỹ thuật nhánh-và-cận
• 2.5. Giải thuật k-means
• 2.5.1. Giới thiệu về kỹ thuật gom cụm
• 2.5.2. Giải thuật k-means
• 2.6. Độ đo khoảng cách Euclid
• 2.7. Độ đo xoắn thời gian động
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Kỹ thuật nhánh-và-cận để tăng tốc giải thuật k-lân cận gần nhất
• 3.1.1. Phân rã tập thiết kế
• 3.1.2. Tìm kiếm cây bằng kỹ thuật nhánh-và-cận
• 3.2. Độ đo CID cho dữ liệu chuỗi thời gian
• 3.2.1. Một vài bất biến
• 3.2.2. CID cho chuỗi thời gian
• 3.3. Độ đo CRD cho dữ liệu chuỗi thời gian
• 3.3.1. Nguyên lý độ dài mô tả tối thiểu (Minimum Description Length - MDL)
• 3.3.2. Độ đo khoảng cách tỉ lệ nén (Compression Rate Distance - CRD)
• 4. CHƯƠNG 4: PHƯƠNG PHÁP TIẾP CẬN
• 4.1. Sơ đồ tổng quát của hệ thống
• 4.2. Giải thích sơ đồ trình tự của hệ thống
• 4.2.1. Phân rã tập dữ liệu và quy trình tổng quát của hệ thống
• 4.2.2. Phân lớp dữ liệu 1-lân cận gần nhất áp dụng giải thuật nhánh và cận
• 5. CHƯƠNG 5: HIỆN THỰC VÀ THỰC NGHIỆM
• 5.1. Môi trường thực nghiệm
• 5.2. Các giải thuật và các bộ dữ liệu thực nghiệm
• 5.2.1. Bộ dữ liệu Gun Point
• 5.2.2. Bộ dữ liệu CBF
• 5.2.3. Bộ dữ liệu Trace
• 5.2.4. Bộ dữ liệu Fish
• 5.3. Kết quả thực nghiệm
• 5.3.1. Thực nghiệm với bộ dữ liệu 50Words
• 5.3.2. Thực nghiệm với bộ dữ liệu CinC_ECG_torso
• 5.3.3. Thực nghiệm với bộ dữ liệu Face (all)
• 5.3.4. Thực nghiệm với bộ dữ liệu Swedish Leaf
• 5.3.5. Thực nghiệm với bộ dữ liệu MedicalImages
• 5.3.6. Thực nghiệm với bộ dữ liệu ECG5000
• 5.3.7. Thực nghiệm với bộ dữ liệu Yoga
• 5.3.8. Thực nghiệm với bộ dữ liệu Adiac
• 5.3.9. Thực nghiệm với bộ dữ liệu FacesUCR
• 5.3.10. Thực nghiệm với bộ dữ liệu ProximalPhalanxOutlineCorrect
• 5.3.11. Thực nghiệm với bộ dữ liệu DistalPhalanxOutlineCorrect
• 5.3.12. Thực nghiệm với bộ dữ liệu Strawberry
• 5.3.13. Thực nghiệm với bộ dữ liệu Gun Point
• 5.3.14. Thực nghiệm với bộ dữ liệu CBF
• 5.3.15. Thực nghiệm với bộ dữ liệu Trace
• 5.3.16. Thực nghiệm với bộ dữ liệu Fish
• 5.4. Bảng tóm tắt các thông số sử dụng và tóm tắt các kết quả thực nghiệm
• 5.4.1. Bảng tóm tắt các thông số
• 5.4.2. Bảng tóm tắt kết quả thực nghiệm
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 6.1. Những kết luận của luận văn
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT

Tóm tắt

I. Giới Thiệu Tổng Quan Về Bài Toán Phân Lớp Chuỗi Thời Gian

Dữ liệu chuỗi thời gian (Time Series Data) ngày càng trở nên phổ biến nhờ sự phát triển của các thiết bị ghi nhận dữ liệu. Dữ liệu này xuất hiện trong nhiều lĩnh vực như kinh tế, y học, và môi trường. Chuỗi thời gian là chuỗi các số thực đo được theo thời gian. Phân tích dữ liệu chuỗi thời gian đóng vai trò quan trọng, giúp trích xuất thông tin có ý nghĩa để dự đoán sự kiện và đưa ra quyết định. Phân lớp dữ liệu chuỗi thời gian là việc xây dựng một bộ phân lớp dựa trên các chuỗi thời gian đã được phân lớp, từ đó xác định nhãn cho dữ liệu mới. Trong lĩnh vực khai phá dữ liệu, đây là một vấn đề quan trọng. Nhiều thuật toán phân lớp đã được phát triển, trong đó giải thuật k-lân cận gần nhất (k-NN) thường được sử dụng cho dữ liệu chuỗi thời gian. Tuy nhiên, k-NN có nhược điểm là chi phí tính toán cao, đòi hỏi cải tiến để giảm thời gian thực thi.

1.1. Ứng Dụng Thực Tế của Dữ Liệu Chuỗi Thời Gian

Dữ liệu chuỗi thời gian xuất hiện rộng rãi trong nhiều lĩnh vực. Trong kinh tế, nó được sử dụng để phân tích biến động thị trường chứng khoán và dự báo tăng trưởng kinh tế. Trong y học, dữ liệu điện tim (ECG) là một ví dụ điển hình của chuỗi thời gian, được sử dụng để chẩn đoán bệnh tim. Các hệ thống xử lý tín hiệu trong các thiết bị IoT cũng dựa vào việc phân tích chuỗi thời gian thu thập từ các cảm biến. Ngoài ra, dự báo thời tiết và phân tích môi trường cũng sử dụng dữ liệu chuỗi thời gian để đưa ra các dự đoán và cảnh báo kịp thời. Ứng dụng này cho thấy tầm quan trọng của việc phát triển các giải thuật hiệu quả để phân lớp dữ liệu chuỗi thời gian.

1.2. Thách Thức Khi Phân Lớp Dữ Liệu Chuỗi Thời Gian

Phân lớp dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Đầu tiên, dữ liệu có thể có độ dài khác nhau, đòi hỏi các phương pháp xử lý đặc biệt. Thứ hai, độ đo tương đồng giữa các chuỗi thời gian có thể phức tạp, đặc biệt khi có sự khác biệt về thời gian hoặc biên độ. Thứ ba, thời gian tính toán có thể tăng lên đáng kể khi kích thước dữ liệu lớn. Các phương pháp truyền thống như k-NN có thể không hiệu quả trong trường hợp này. Cuối cùng, việc trích chọn đặc trưng phù hợp từ chuỗi thời gian là một bài toán quan trọng, ảnh hưởng đến độ chính xác của phân lớp. Cần có những giải pháp cải tiến thuật toán để vượt qua những thách thức này.

II. Vấn Đề Chi Phí Tính Toán Cao của Giải Thuật 1 NN

Giải thuật 1-NN (1-Nearest Neighbor) là một phương pháp đơn giản và hiệu quả cho bài toán phân lớp dữ liệu. Tuy nhiên, nó có một hạn chế lớn: thời gian tính toán tăng tuyến tính theo kích thước tập dữ liệu. Để phân lớp một điểm dữ liệu mới, thuật toán cần tính khoảng cách đến tất cả các điểm dữ liệu trong tập huấn luyện và chọn ra điểm gần nhất. Điều này trở nên tốn kém khi tập dữ liệu lớn hoặc khi độ đo khoảng cách phức tạp, như khoảng cách động thời gian (DTW). Trong bối cảnh dữ liệu chuỗi thời gian, với kích thước ngày càng tăng, việc cải thiện hiệu suất của 1-NN là vô cùng cần thiết. Các phương pháp như kỹ thuật nhánh và cận được sử dụng để giảm số lượng phép tính khoảng cách cần thiết.

2.1. Tại Sao Cần Cải Tiến Giải Thuật 1 NN cho Chuỗi Thời Gian

Việc cải tiến giải thuật 1-NN cho dữ liệu chuỗi thời gian là cần thiết vì nhiều lý do. Thứ nhất, dữ liệu chuỗi thời gian thường có kích thước lớn, dẫn đến chi phí tính toán cao cho 1-NN. Thứ hai, nhiều ứng dụng thực tế đòi hỏi phân lớp thời gian thực, yêu cầu thuật toán phải nhanh chóng và hiệu quả. Thứ ba, các phương pháp cải tiến thuật toán có thể giúp giảm thời gian tính toán mà không ảnh hưởng đến độ chính xác phân lớp. Cuối cùng, các kỹ thuật như nhánh và cận có thể được kết hợp với các độ đo tương đồng khác nhau để tối ưu hóa hiệu suất.

2.2. Ảnh Hưởng của Độ Đo Khoảng Cách Đến Hiệu Suất 1 NN

Độ đo khoảng cách đóng vai trò quan trọng trong hiệu suất của giải thuật 1-NN. Các độ đo đơn giản như khoảng cách Euclide có thể nhanh chóng nhưng không hiệu quả cho các chuỗi thời gian có biến dạng thời gian. Các độ đo phức tạp hơn như DTW có thể chính xác hơn nhưng lại tốn kém hơn về mặt tính toán. Việc lựa chọn độ đo khoảng cách phù hợp là một bài toán quan trọng, cần cân bằng giữa độ chính xác và thời gian tính toán. Các phương pháp cải tiến có thể giúp giảm chi phí tính toán cho các độ đo phức tạp, làm cho 1-NN trở nên khả thi hơn cho các ứng dụng thực tế. Phân tích Wavelet và Biến đổi Fourier có thể được sử dụng để trích chọn đặc trưng, giảm chiều dữ liệu.

III. Kỹ Thuật Nhánh Và Cận Tăng Tốc Phân Lớp 1 NN Hiệu Quả

Kỹ thuật nhánh và cận (Branch and Bound) là một phương pháp hiệu quả để giảm thời gian tính toán của giải thuật 1-NN. Ý tưởng chính là loại bỏ các ứng cử viên không tiềm năng trong quá trình tìm kiếm láng giềng gần nhất. Kỹ thuật này sử dụng một cận dưới (lower bound) của khoảng cách để loại bỏ các điểm dữ liệu mà chắc chắn không phải là láng giềng gần nhất. Thuật toán bắt đầu với một cận trên (upper bound) ban đầu, sau đó cập nhật cận trên này khi tìm thấy các điểm dữ liệu gần hơn. Bằng cách này, nhiều phép tính khoảng cách không cần thiết có thể được bỏ qua. Kỹ thuật nhánh và cận đặc biệt hiệu quả khi kết hợp với các độ đo khoảng cách phức tạp.

3.1. Cơ Chế Hoạt Động của Kỹ Thuật Nhánh Và Cận trong 1 NN

Trong 1-NN, kỹ thuật nhánh và cận hoạt động bằng cách duy trì một khoảng cách tốt nhất hiện tại đến đối tượng cần phân loại. Khi xét một đối tượng khác trong tập huấn luyện, thuật toán tính toán một cận dưới (lower bound) của khoảng cách giữa hai đối tượng. Nếu cận dưới này lớn hơn khoảng cách tốt nhất hiện tại, thuật toán có thể bỏ qua đối tượng đó mà không cần tính toán khoảng cách đầy đủ. Bằng cách này, số lượng tính toán khoảng cách giảm đáng kể, đặc biệt là khi có nhiều đối tượng trong tập huấn luyện nằm xa đối tượng cần phân loại. Độ chính xác phân lớp vẫn được đảm bảo do thuật toán chỉ loại bỏ những đối tượng chắc chắn không phải là láng giềng gần nhất. Tối ưu hóa tham số của kỹ thuật này cũng quan trọng.

3.2. Ưu Điểm và Hạn Chế của Kỹ Thuật Nhánh và Cận

Ưu điểm chính của kỹ thuật nhánh và cận là giảm đáng kể thời gian tính toán của 1-NN, đặc biệt khi tập dữ liệu lớn. Nó cũng có thể được kết hợp với nhiều độ đo khoảng cách khác nhau để tối ưu hóa hiệu suất. Tuy nhiên, kỹ thuật này cũng có một số hạn chế. Việc tính toán cận dưới (lower bound) có thể tốn kém, đặc biệt nếu cận dưới không chặt. Hiệu quả của kỹ thuật phụ thuộc vào thứ tự duyệt các điểm dữ liệu trong tập huấn luyện. Các phương pháp tối ưu hóa có thể được sử dụng để cải thiện hiệu quả của kỹ thuật này. Việc lựa chọn độ đo tương đồng cũng ảnh hưởng đến hiệu quả.

IV. Ứng Dụng và Kết Quả Nghiên Cứu Cải Tiến Thuật Toán 1 NN

Nghiên cứu này tập trung vào việc cải tiến giải thuật 1-NN để phân lớp dữ liệu chuỗi thời gian bằng cách sử dụng kỹ thuật nhánh và cận. Mục tiêu là giảm thời gian tính toán mà không làm giảm độ chính xác phân lớp. Nghiên cứu cũng khảo sát các độ đo khác nhau như CID (Complexity-Invariant Distance) và CRD (Compression Rate Distance) để so sánh độ chính xác của giải thuật. Các kết quả thực nghiệm cho thấy giải thuật được cải tiến có thời gian thực hiện nhanh hơn so với 1-NN truyền thống. Ngoài ra, các độ đo CID và CRD cho kết quả phân lớp với độ chính xác cao hơn so với Euclid.

4.1. Đánh Giá Hiệu Quả Của Thuật Toán Cải Tiến Trên Các Bộ Dữ Liệu

Hiệu quả của thuật toán cải tiến được đánh giá trên nhiều bộ dữ liệu khác nhau từ kho lưu trữ UCR Time Series Classification Archive. Các bộ dữ liệu này đại diện cho nhiều lĩnh vực và độ phức tạp khác nhau. Các kết quả cho thấy thuật toán cải tiến vượt trội so với 1-NN truyền thống về thời gian tính toán mà không làm giảm độ chính xác. Các độ đo CID và CRD cho kết quả tốt hơn Euclid trên một số bộ dữ liệu. Các kết quả này chứng minh tính hiệu quả của kỹ thuật nhánh và cận và tầm quan trọng của việc lựa chọn độ đo tương đồng phù hợp. ROC curve và AUC score có thể được sử dụng để đánh giá hiệu năng.

4.2. So Sánh Các Độ Đo Khoảng Cách Euclid CID và CRD

Nghiên cứu so sánh ba độ đo khoảng cách: Euclid, CID, và CRD. Euclid là một độ đo đơn giản và nhanh chóng, nhưng không hiệu quả cho các chuỗi thời gian có biến dạng. CID là một độ đo bất biến với độ phức tạp, có thể hiệu quả hơn cho các chuỗi thời gian có độ phức tạp khác nhau. CRD dựa trên nguyên lý độ dài mô tả tối thiểu (MDL), có thể hiệu quả cho các chuỗi thời gian có cấu trúc phức tạp. Các kết quả cho thấy CID và CRD cho kết quả tốt hơn Euclid trên một số bộ dữ liệu, cho thấy tầm quan trọng của việc lựa chọn độ đo tương đồng phù hợp cho từng ứng dụng cụ thể. Chuẩn hóa dữ liệu cũng có thể ảnh hưởng đến kết quả.

V. Kết Luận và Hướng Phát Triển Tiềm Năng Thuật Toán 1 NN

Luận văn đã trình bày một phương pháp cải tiến giải thuật 1-NN để phân lớp dữ liệu chuỗi thời gian bằng cách sử dụng kỹ thuật nhánh và cận. Phương pháp này giúp giảm thời gian tính toán mà không làm giảm độ chính xác phân lớp. Luận văn cũng khảo sát các độ đo khác nhau như CID và CRD để so sánh độ chính xác của giải thuật. Các kết quả thực nghiệm cho thấy giải thuật được cải tiến có thời gian thực hiện nhanh hơn và độ chính xác cao hơn so với 1-NN truyền thống. Các hướng phát triển tiềm năng bao gồm việc kết hợp kỹ thuật nhánh và cận với các phương pháp trích chọn đặc trưng và các độ đo khác.

5.1. Tổng Kết Các Kết Quả Đạt Được và Đóng Góp Của Nghiên Cứu

Nghiên cứu này đã đạt được các kết quả quan trọng trong việc cải tiến thuật toán 1-NN cho dữ liệu chuỗi thời gian. Cụ thể, việc áp dụng kỹ thuật nhánh và cận đã giúp giảm đáng kể thời gian tính toán, đồng thời duy trì được độ chính xác phân lớp. Nghiên cứu cũng đã chứng minh tính hiệu quả của các độ đo CID và CRD so với Euclid trên một số bộ dữ liệu. Các đóng góp của nghiên cứu bao gồm việc cung cấp một phương pháp hiệu quả để phân lớp dữ liệu chuỗi thời gian trong các ứng dụng thực tế và việc so sánh các độ đo tương đồng khác nhau. Cross-validation được sử dụng để đánh giá khách quan.

5.2. Các Hướng Nghiên Cứu Tiếp Theo và Ứng Dụng Mở Rộng

Các hướng nghiên cứu tiếp theo có thể tập trung vào việc cải thiện hiệu quả của kỹ thuật nhánh và cận bằng cách sử dụng các phương pháp tối ưu hóa. Việc kết hợp kỹ thuật này với các phương pháp trích chọn đặc trưng như biến đổi Fourier hoặc phân tích Wavelet cũng có thể mang lại kết quả tốt hơn. Ngoài ra, nghiên cứu có thể được mở rộng để xử lý các bài toán phân loại đa lớp hoặc dữ liệu chuỗi thời gian đa biến. Ứng dụng của giải thuật được cải tiến có thể được mở rộng sang các lĩnh vực như học máy, data mining, xử lý tín hiệu, phân loại đa lớp, và dữ liệu chuỗi thời gian đa biến.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian xuất hiện phổ biến trong kỷ nguyên số thông qua các thiết bị đo cảm biến hiện đại, trải dài từ các chỉ số tài chính như giá cổ phiếu Đường Biên Hòa biến động từ 12.000 đến 22.300 đồng trong giai đoạn 6 tháng cuối năm 2015, cho đến hàng triệu điểm dữ liệu tín hiệu điện tâm đồ y tế. Vấn đề cốt lõi của bài toán phân lớp dữ liệu chuỗi thời gian là xác định chính xác nhãn phân lớp cho các mẫu chưa biết dựa trên tập huấn luyện đã được gán nhãn trước đó. Trong số các thuật toán học máy kinh điển, phương pháp phân lớp 1 lân cận gần nhất (1-NN) được đánh giá mang lại hiệu quả vượt trội, song lại đối mặt với rào cản nghiêm trọng về chi phí tính toán khoảng cách và tài nguyên bộ nhớ khi kích thước tập dữ liệu tăng cao.

Mục tiêu nghiên cứu trọng tâm của luận văn là hoàn thiện và ứng dụng kỹ thuật nhánh và cận nhằm tăng tốc độ tính toán cho giải thuật phân lớp 1-NN, đồng thời khảo sát các độ đo khoảng cách tiên tiến để tối ưu hóa độ chính xác. Phạm vi nghiên cứu được thực hiện xuyên suốt 16 tháng từ tháng 8/2015 đến tháng 12/2016 tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh, thực nghiệm kiểm chứng trên 16 bộ dữ liệu chuẩn thuộc kho lưu trữ UCR Time Series Classification Archive. Nghiên cứu mang ý nghĩa thực tiễn lớn khi giúp giảm số phép tính khoảng cách từ quy mô toàn bộ mẫu xuống chỉ còn khoảng 61 phép tính trên 1.000 mẫu thiết kế, duy trì 100% độ chính xác tối ưu của thuật toán vét cạn mà vẫn rút ngắn thời gian xử lý tổng thể.

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 trên nền tảng kỹ thuật nhánh và cận do Fukunaga và Narendra đề xuất năm 1975, kết hợp với các lý thuyết phân lớp dữ liệu nhiều chiều. Kỹ thuật này phân rã không gian tìm kiếm thành cấu trúc cây phân cấp và áp dụng hai quy tắc cắt tỉa nhánh nghiêm ngặt:

• Quy tắc 1 loại bỏ toàn bộ tập mẫu con nếu khoảng cách từ mẫu thử đến tâm cụm trừ đi bán kính cực đại của cụm lớn hơn khoảng cách lân cận gần nhất hiện thời.
• Quy tắc 2 loại trừ trực tiếp từng mẫu riêng lẻ ở nút lá nếu tổng khoảng cách từ mẫu đó đến tâm cụm và khoảng cách lân cận hiện thời nhỏ hơn khoảng cách từ mẫu thử đến tâm cụm.

Bên cạnh đó, nghiên cứu tích hợp nguyên lý Độ dài mô tả tối thiểu (Minimum Description Length - MDL) để triển khai độ đo khoảng cách tỉ lệ nén (Compression Rate Distance - CRD) do Võ Thanh Vinh và Dương Tuấn Anh công bố năm 2015, cùng với lý thuyết Bất biến độ phức tạp (Complexity Invariance) định hình nên độ đo CID của Batista năm 2014. Các khái niệm nền tảng bao gồm: chuỗi thời gian đa chiều n điểm, độ đo khoảng cách Euclid trong không gian n chiều, ước lượng entropy thông tin và hệ số điều chỉnh độ phức tạp.

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

Nguồn dữ liệu thực nghiệm gồm 16 bộ dữ liệu chuẩn quốc tế trích xuất từ kho lưu trữ UCR Time Series Classification Archive, bao gồm các tập dữ liệu đa dạng như Gun Point, CBF, Trace, Fish, ECG5000, 50Words và Swedish Leaf với kích thước mẫu từ vài chục đến hơn 5.000 chuỗi thời gian. Phương pháp chọn mẫu tuân thủ phân vùng huấn luyện và kiểm thử chuẩn hóa có sẵn của từng bộ dữ liệu nhằm đảm bảo tính khách quan và khả năng so sánh khoa học.

Phương pháp phân tích được thực hiện qua hai giai đoạn chính:

1. Giai đoạn 1 sử dụng thuật toán phân cụm k-means để phân rã tập dữ liệu huấn luyện thành cây phân cấp với độ phức tạp tuyến tính O(nkt), trong đó n là số đối tượng, k là số cụm và t là số lần lặp.
2. Giai đoạn 2 vận hành giải thuật tìm kiếm quay lui kết hợp nhánh và cận trên cây phân rã để xác định lân cận gần nhất.

Lý do lựa chọn k-means là nhờ chi phí tính toán thấp, tốc độ thực thi nhanh hơn so với các phương pháp gom cụm phân cấp khác. Nghiên cứu tiến hành đánh giá đối chuẩn 3 độ đo khoảng cách là Euclid, CID và CRD dựa trên hai tiêu chí định lượng: Tỉ lệ lỗi phân lớp (Error Rate) và Thời gian thực thi (Execution Time) trên máy tính đo bằng giây.

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 chứng trên 16 bộ dữ liệu chuỗi thời gian đã ghi nhận 4 phát hiện quan trọng:

• Thứ nhất, kỹ thuật nhánh và cận giúp giảm thiểu vượt bậc thời gian phân lớp 1-NN so với phương pháp vét cạn truyền thống trên toàn bộ các bộ dữ liệu, đặc biệt đối với các tập dữ liệu có quy mô lớn như ECG5000 và 50Words. Thời gian thực thi giảm từ 40% đến hơn 70% tùy thuộc vào cấu trúc phân bố dữ liệu.
• Thứ hai, độ chính xác phân lớp của giải thuật 1-NN nhánh và cận sử dụng độ đo Euclid hoàn toàn trùng khớp 100% với kết quả của giải thuật vét cạn cổ điển, chứng minh các quy tắc cắt tỉa không hề bỏ sót nghiệm tối ưu toàn cục.
• Thứ ba, việc áp dụng hai độ đo mới CID và CRD đem lại tỉ lệ lỗi phân lớp thấp hơn rõ rệt so với độ đo Euclid truyền thống. Ví dụ trên các tập dữ liệu có dạng sóng phức tạp như CinC_ECG_torso hay Swedish Leaf, độ đo CRD và CID giúp cải thiện độ chính xác phân lớp từ 3% đến 12% so với khoảng cách Euclid.
• Thứ tư, so sánh giữa hai độ đo cải tiến cho thấy độ đo CRD nhìn chung đạt độ chính xác phân lớp cao hơn độ đo CID trên đa số tập dữ liệu, dù thời gian tính toán của CRD cao hơn khoảng 15% đến 25% do phải thực hiện các phép tính entropy và nén chuỗi.

Thảo luận kết quả

Hiệu năng vượt trội về tốc độ của thuật toán bắt nguồn từ cơ chế phân rã cây k-means kết hợp hai quy tắc cắt tỉa của Fukunaga và Narendra. Khi tập dữ liệu có hàng ngàn mẫu, giải thuật chỉ cần duyệt qua các tâm cụm đại diện và nhanh chóng loại bỏ hàng loạt nhánh không chứa lân cận tiềm năng, từ đó giảm thiểu hàng chục ngàn phép tính khoảng cách không cần thiết. Kết quả thực nghiệm có thể được tổng hợp trực quan thông qua bảng so sánh tỉ lệ lỗi và biểu đồ cột biểu diễn thời gian thực thi giữa 1-NN truyền thống và 1-NN nhánh và cận trên 3 độ đo.

Nguyên nhân độ đo CID và CRD vượt trội hơn độ đo Euclid nằm ở khả năng bù trừ các biến dạng và khác biệt về độ phức tạp hình học của chuỗi thời gian. Khoảng cách Euclid thông thường rất nhạy cảm với nhiễu và sự lệch pha biên độ, trong khi CID điều chỉnh khoảng cách dựa trên tổng biến thiên đạo hàm bậc một và CRD khai thác tỉ lệ nén thông tin theo nguyên lý MDL. Đáng chú ý, cả 3 độ đo đều duy trì độ phức tạp tính toán tuyến tính O(n), khắc phục hoàn toàn điểm nghẽn chi phí bậc hai O(m*n) của độ đo xoắn thời gian động DTW, tạo ra sự cân bằng hoàn hảo giữa tốc độ và độ chính xác cho bài toán phân lớp.

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

Dựa trên các kết quả đạt được, nghiên cứu đưa ra 4 khuyến nghị và giải pháp hành động cụ thể:

• Mở rộng cấu trúc phân rã tập mẫu: Thay thế thuật toán k-means bằng các cấu trúc chỉ mục nâng cao như BIRCH, Cover Tree hoặc VP-Tree nhằm giảm thiểu thời gian xây dựng cây ban đầu từ 20% đến 30%, hoàn thành thử nghiệm trong vòng 6 tháng tới do nhóm nghiên cứu thuật toán chủ trì.
• Ứng dụng phân tích dữ liệu y tế thời gian thực: Triển khai giải thuật 1-NN nhánh và cận tích hợp độ đo CRD vào các thiết bị theo dõi tín hiệu điện tim ECG và điện não EEG, hướng tới mục tiêu xử lý cảnh báo nhịp tim bất thường dưới 0,5 giây với độ chính xác đạt trên 95%, thực hiện bởi các kỹ sư hệ thống nhúng y tế trong quý 2 năm 2017.
• Tự động hóa việc lựa chọn tham số và độ đo: Xây dựng module nhận diện đặc trưng dữ liệu để tự động chọn tham số độ lệch alpha, tham số làm mịn b-bit của độ đo CRD và số nhánh cây tối ưu cho từng tập dữ liệu, giảm thiểu thời gian tinh chỉnh thủ công khoảng 50% trong lộ trình 9 tháng.
• Tối ưu hóa trên phần cứng tính toán song song: Chuyển đổi mã nguồn giải thuật sang kiến trúc xử lý song song GPU và FPGA để tăng tốc độ phân lớp dữ liệu chuỗi thời gian quy mô lớn trong ngành tài chính và giám sát công nghiệp, do các chuyên gia điện toán hiệu năng cao thực hiện trong vòng 12 tháng.

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

Tài liệu này cung cấp giá trị học thuật và ứng dụng thực tiễn sâu rộng cho 4 nhóm đối tượng chính:

• Sinh viên và học viên cao học chuyên ngành Khoa học Máy tính và Công nghệ Thông tin: Nắm vững phương pháp phân lớp dữ liệu chuỗi thời gian, hiểu sâu cơ chế cắt tỉa không gian trạng thái của kỹ thuật nhánh và cận, cũng như phương pháp thiết lập nghiên cứu thực nghiệm chuẩn mực.
• Kỹ sư dữ liệu và chuyên gia Học máy (Machine Learning Engineers): Khai thác giải thuật 1-NN tối ưu để ứng dụng vào các bài toán tìm kiếm tương đồng quy mô lớn, xây dựng hệ thống gợi ý và phân loại mẫu chuỗi thời gian với độ trễ thấp.
• Các nhà nghiên cứu và kỹ sư y sinh: Áp dụng trực tiếp độ đo CRD và CID vào việc phân tích, sàng lọc và phân loại các tín hiệu sinh học phức tạp như điện tâm đồ, điện não đồ và chuyển động cơ thể người.
• Chuyên gia phân tích dữ liệu tài chính - chứng khoán: Vận dụng mô hình để nhận dạng các mẫu hình nến, phân tích biến động giá cổ phiếu và dự báo xu hướng thị trường tài chính dựa trên dữ liệu chuỗi thời gian lịch sử.

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

• Kỹ thuật nhánh và cận có làm giảm độ chính xác của giải thuật 1-NN so với phương pháp vét cạn không? Không. Kỹ thuật nhánh và cận dựa trên các bất đẳng thức tam giác và cận khoảng cách chặt chẽ để loại bỏ các điểm chắc chắn không thể là lân cận gần nhất. Kết quả tìm kiếm lân cận gần nhất của 1-NN nhánh và cận hoàn toàn trùng khớp 100% với phương pháp vét cạn, giữ nguyên vẹn độ chính xác tối ưu.

• Vì sao độ đo khoảng cách tỉ lệ nén CRD lại phân lớp chính xác hơn độ đo Euclid? Độ đo Euclid chỉ so sánh từng cặp điểm tương ứng tại cùng một vị trí thời gian nên rất dễ bị sai lệch khi có nhiễu hoặc biến động cục bộ. Ngược lại, CRD dựa trên nguyên lý độ dài mô tả tối thiểu MDL để đánh giá lượng thông tin chia sẻ giữa hai chuỗi thông qua tỉ lệ nén, giúp nhận diện chính xác bản chất tương đồng của tín hiệu.

• Khi nào nên ưu tiên sử dụng độ đo CID thay vì độ đo CRD? Nên ưu tiên độ đo CID khi hệ thống yêu cầu tốc độ phản hồi nhanh hơn và dữ liệu có sự chênh lệch lớn về độ phức tạp hình học nhưng không đòi hỏi mức độ nén sâu. CID tính toán đơn giản hơn CRD nhờ công thức ước lượng độ phức tạp trực tiếp, giúp tiết kiệm từ 15% đến 25% thời gian tính toán khoảng cách.

• Số lượng mẫu trong mỗi cụm ở nút lá ảnh hưởng như thế nào đến hiệu năng của cây tìm kiếm? Nếu số lượng mẫu trong cụm nút lá quá lớn (trên 60 mẫu), số nút trên cây sẽ ít nhưng chi phí tính toán vét cạn ở tầng lá sẽ tăng cao. Ngược lại, nếu số mẫu ở nút lá quá ít, cấu trúc cây sẽ phình to gây tốn bộ nhớ. Việc lựa chọn tham số phân rã k phù hợp trong k-means giúp cân bằng tối ưu giữa chiều cao cây và tốc độ tìm kiếm.

• Luận văn đã kiểm thử giải thuật trên những bộ dữ liệu thực nghiệm tiêu biểu nào? Nghiên cứu đã thử nghiệm toàn diện trên 16 bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCR Time Series Archive, bao gồm dữ liệu cử động tay Gun Point, dữ liệu dạng hình học tổng hợp CBF, tín hiệu thiết bị Trace, dữ liệu y tế ECG5000, nhận diện chữ viết 50Words và phân loại lá cây Swedish Leaf.

Kết luận

• Luận văn đã hiện thực thành công giải thuật phân lớp 1-NN tối ưu hóa dựa trên kỹ thuật nhánh và cận kết hợp cấu trúc cây phân rã k-means cho dữ liệu chuỗi thời gian.
• Tốc độ phân lớp của 1-NN nhánh và cận nhanh hơn vượt trội so với 1-NN vét cạn truyền thống mà vẫn bảo toàn 100% độ chính xác phân lớp của mô hình.
• Hai độ đo khoảng cách CID và CRD được chứng minh có độ chính xác phân lớp cao hơn rõ rệt so với độ đo khoảng cách Euclid kinh điển.
• Trong các độ đo cải tiến, độ đo CRD đạt độ chính xác cao nhất trên đại đa số các tập dữ liệu thử nghiệm nhờ tận dụng hiệu quả nguyên lý độ dài mô tả tối thiểu MDL.
• Toàn bộ các thuật toán và độ đo đều duy trì độ phức tạp tính toán tuyến tính, đảm bảo tính khả thi cao khi ứng dụng trong các hệ thống xử lý dữ liệu lớn thực tế.

Đóng góp cốt lõi của công trình là mở ra giải pháp phân lớp chuỗi thời gian nhanh và chính xác, khắc phục triệt để hạn chế tính toán của thuật toán 1-NN cổ điển. Lộ trình phát triển tiếp theo trong 12 tháng tới sẽ tập trung vào việc thử nghiệm các cấu trúc cây chỉ mục tiên tiến và triển khai hệ thống trên phần cứng xử lý song song. Hãy ứng dụng ngay giải thuật 1-NN nhánh và cận kết hợp độ đo CRD vào các dự án phân tích dữ liệu chuỗi thời gian của bạn để tối ưu hóa hiệu năng và độ chính xác vượt trội.