Phân Lớp Dữ Liệu Chuỗi Thời Gian Sử Dụng Thông Tin Motif Trong Khoa Học Máy Tính

Luận văn thạc sĩ khoa học máy tính tập trung phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif, ứng dụng hiệu quả trong phân tích dữ liệu.

• Tác giả: Nguyễn Văn Kiên
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU VẤN ĐỀ
• 1.1. Tổng quan về đề tài
• 1.2. Mục tiêu và giới hạn đề tài
• 1.3. Nhiệm vụ của đề tài
• 1.4. Những kết quả đạt được
• 1.5. Cấu trúc luận văn
• 2. CHƯƠNG 2
• 2.1. Giới thiệu về đề tài
• 2.2. Giải thuật phân lớp k-NN
• 2.3. Máy vector hỗ trợ (Support Vector Machines — SVM)
• 2.4. Mạng nơ ron nhân tạo (Artificial Neural Network - ANN)
• 2.5. Phân lớp dữ liệu chuỗi thời gian
• 2.6. Chuỗi thời gian và các khái niệm liên quan
• 2.7. Độ đo xoắn thời gian động (Dynamic Time Warping - DTW)
• 2.8. Các độ đo trên dữ liệu rời rạc
• 2.9. Chuẩn hóa dữ liệu
• 2.10. Phương pháp thu giảm số chiều
• 2.11. Phương pháp xấp xỉ gộp từng đoạn (PAA)
• 2.12. Phương pháp điểm cực trị quan trọng
• 2.13. Phương pháp rời rạc hóa SAX (Symbol Aggregate Approximation)
• 2.14. Giải thuật gom cụm K-MEANS
• 2.15. Giải thuật gom cụm gộp phân cấp
• 2.16. Các độ đo đánh giá chất lượng của sự phân lớp
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Giải thuật Brute Force
• 3.2. Giải thuật chiếu ngẫu nhiên (Random Projection)
• 3.3. Giải thuật phát hiện motif dựa vào phân đoạn và gom cụm (EP-C)
• 3.4. Kết hợp giải thuật EP-C và EP-MK
• 3.5. Phân lớp chuỗi thời gian dựa trên thông tin motif
• 3.6. Phân lớp chuỗi thời gian bằng giải thuật SVM và mạng Bayes
• 3.7. Phân lớp chuỗi thời gian bằng giải thuật k-NN và cây quyết định
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Chuẩn hóa dữ liệu
• 4.2. Phép vị tự (Homothetic Transformation)
• 4.3. Khoảng cách Euclid tối thiểu (Minimum Euclidean Distance)
• 4.4. Tìm kiếm motif bằng giải thuật EP-C
• 4.5. Tìm kiếm motif bằng giải thuật EP-MK
• 4.6. Biểu diễn chuỗi thời gian dưới dạng vector đặc trưng
• 4.7. Phân lớp dựa trên thông tin motif
• 5. CHƯƠNG 5
• 5.1. Môi trường thực nghiệm
• 5.2. Ước lượng tham số
• 5.3. Độ dài của các Motif ứng viên
• 5.4. Giá trị ngưỡng trong tác vụ so trùng chuỗi con
• 5.5. Tham số của giải thuật gom cụm được sử dụng trong giải thuật EP-C và số điểm tham chiếu của giải thuật EP-MK
• 5.6. Dữ liệu thực nghiệm
• 5.7. Kết quả thực nghiệm
• 5.8. Thực nghiệm phân lớp bằng k-NN truyền thống và k-NN có sử dụng thông tin motif
• 5.9. Thực nghiệm phân lớp sử dụng thông tin motif bằng giải thuật k-NN, SVMs, ANN
• 5.10. Những đóng góp của đề tài
• 5.11. Hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về đề tài

Phân lớp dữ liệu chuỗi thời gian là một tác vụ quan trọng trong lĩnh vực khai phá dữ liệu, được ứng dụng rộng rãi trong nhiều lĩnh vực như nhận diện chuyển động cơ thể, xác thực chữ ký, và chuẩn đoán bệnh. Dữ liệu chuỗi thời gian thường chứa nhiều thông tin hữu ích, nhưng cũng gặp phải thách thức về kích thước lớn và độ nhiễu. Thông tin motif là những chuỗi con lặp lại trong dữ liệu, có thể cải thiện độ chính xác của quá trình phân lớp. Tuy nhiên, việc tìm kiếm motif trong dữ liệu lớn thường phức tạp và tốn thời gian. Luận văn này đề xuất một phương pháp mới để phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif, nhằm cải thiện độ chính xác và giảm thời gian xử lý.

1.1. Mục tiêu và giới hạn đề tài

Mục tiêu của đề tài là xây dựng một hệ thống phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif. Đề tài tập trung vào việc tìm kiếm motif và sử dụng chúng trong quá trình phân lớp. Các motif được nghiên cứu trong luận văn này là motif bậc nhất, tức là những chuỗi con lặp lại thường xuyên nhất. Hệ thống phân lớp sẽ được hiện thực hóa bằng giải thuật k-NN, với mục tiêu cải thiện độ chính xác và giảm thời gian xử lý.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản liên quan đến dữ liệu chuỗi thời gian, phân lớp dữ liệu, và các độ đo khoảng cách. Phân tích dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng, với nhiều ứng dụng thực tiễn. Các độ đo như khoảng cách Euclid và Dynamic Time Warping (DTW) được sử dụng để so sánh các chuỗi thời gian. Việc hiểu rõ các khái niệm này là cần thiết để áp dụng các giải thuật tìm kiếm motif và phân lớp hiệu quả. Giải thuật k-NN và các phương pháp khác như SVM và ANN cũng được đề cập, nhằm cung cấp cái nhìn tổng quan về các phương pháp phân lớp hiện có.

2.1. Các độ đo khoảng cách

Các độ đo khoảng cách là yếu tố quan trọng trong việc phân lớp dữ liệu chuỗi thời gian. Khoảng cách Euclid là một trong những độ đo phổ biến nhất, nhưng không phải lúc nào cũng phù hợp với dữ liệu chuỗi thời gian. Dynamic Time Warping (DTW) là một phương pháp mạnh mẽ hơn, cho phép so sánh các chuỗi có độ dài khác nhau. Việc lựa chọn độ đo phù hợp sẽ ảnh hưởng lớn đến kết quả phân lớp. Các độ đo này sẽ được áp dụng trong quá trình phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif.

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

Chương này trình bày chi tiết về các giải thuật được sử dụng để tìm kiếm motif và phân lớp dữ liệu chuỗi thời gian. Giải thuật EP-C và EP-MK được áp dụng để tìm kiếm motif, giúp cải thiện tốc độ và độ chính xác của quá trình phân lớp. Các điểm cực trị quan trọng được sử dụng để phân đoạn chuỗi thời gian thành các chuỗi con, từ đó thực hiện so sánh với các motif. Hệ thống phân lớp được xây dựng dựa trên các vector đặc trưng, giúp tối ưu hóa quá trình phân lớp. Kết quả phân lớp sẽ được so sánh với các phương pháp truyền thống để đánh giá hiệu quả.

3.1. Giải thuật tìm kiếm motif

Giải thuật EP-C và EP-MK được thiết kế để tìm kiếm motif trong dữ liệu chuỗi thời gian. EP-C sử dụng các điểm cực trị để phân đoạn chuỗi, trong khi EP-MK tập trung vào việc tối ưu hóa thời gian tìm kiếm. Cả hai giải thuật này đều giúp cải thiện độ chính xác của quá trình phân lớp. Việc tìm kiếm motif không chỉ giúp nâng cao chất lượng phân lớp mà còn giảm thiểu thời gian xử lý, điều này rất quan trọng trong bối cảnh dữ liệu lớn.

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

Chương này trình bày kết quả thực nghiệm của hệ thống phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif. Các bộ dữ liệu mẫu được sử dụng để đánh giá hiệu quả của phương pháp. Kết quả cho thấy rằng hệ thống phân lớp dựa trên motif đạt được độ chính xác cao hơn so với các phương pháp truyền thống như k-NN và độ đo Euclid. Thời gian tìm kiếm motif cũng được cải thiện đáng kể nhờ vào việc áp dụng các giải thuật EP-C và EP-MK. Những kết quả này chứng minh tính khả thi và hiệu quả của phương pháp đề xuất.

4.1. Đánh giá kết quả

Kết quả thực nghiệm cho thấy rằng việc sử dụng thông tin motif trong phân lớp dữ liệu chuỗi thời gian mang lại nhiều lợi ích. Độ chính xác của hệ thống phân lớp cao hơn so với các phương pháp truyền thống, cho thấy rằng motif có thể cải thiện đáng kể chất lượng phân lớp. Thời gian tìm kiếm motif cũng được giảm thiểu, giúp tăng hiệu suất của hệ thống. Những kết quả này khẳng định giá trị thực tiễn của nghiên cứu và mở ra hướng đi mới cho các nghiên cứu tiếp theo trong lĩnh vực này.

Nội dung chính

Tổng quan nghiên cứu

Phân lớp dữ liệu chuỗi thời gian là một nhiệm vụ quan trọng trong khai phá dữ liệu, được ứng dụng rộng rãi trong các lĩnh vực như nhận diện chuyển động cơ thể, xác thực chữ ký, chuẩn đoán y tế và xử lý dữ liệu cảm biến. Theo ước tính, dữ liệu chuỗi thời gian có thể chứa hàng chục ngàn tỷ quan sát, tạo ra thách thức lớn về xử lý và lưu trữ. Một trong những vấn đề then chốt là tìm kiếm motif — các chuỗi con lặp lại thường xuyên trong chuỗi thời gian, có thể cải thiện độ chính xác phân lớp. Tuy nhiên, các phương pháp hiện tại thường phức tạp và tốn nhiều thời gian tính toán.

Mục tiêu của luận văn là xây dựng một hệ thống phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif nhằm nâng cao độ chính xác và giảm thời gian xử lý. Nghiên cứu tập trung vào hai giải thuật tìm kiếm motif EP-C (Extreme Point Clustering) và EP-MK (kết hợp EP-C và giải thuật MK), sử dụng các điểm cực trị quan trọng để phân đoạn chuỗi thời gian và kỹ thuật thu giảm thời gian tính toán. Phạm vi nghiên cứu bao gồm các bộ dữ liệu chuỗi thời gian thực nghiệm, với thời gian thực hiện từ tháng 7 đến tháng 12 năm 2017 tại Trường Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh.

Ý nghĩa nghiên cứu thể hiện qua việc cải thiện độ chính xác phân lớp trên tất cả các bộ dữ liệu thử nghiệm so với phương pháp truyền thống k-NN với độ đo Euclid, đồng thời giảm đáng kể thời gian tìm kiếm motif. Kết quả này góp phần nâng cao hiệu quả xử lý dữ liệu chuỗi thời gian lớn trong các ứng dụng thực tế.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Phân lớp dữ liệu (Classification): Quá trình xây dựng bộ phân lớp từ tập dữ liệu huấn luyện để dự đoán nhãn lớp cho dữ liệu mới. Các thuật toán phân lớp phổ biến gồm k-NN, SVM, mạng nơ ron nhân tạo (ANN).
• Chuỗi thời gian và motif: Chuỗi thời gian là tập hợp các giá trị đo theo thứ tự thời gian. Motif là chuỗi con lặp lại nhiều lần, được định nghĩa theo số lượng chuỗi con trùng khớp không tâm thường hoặc theo cặp chuỗi con gần nhau nhất.
• Giải thuật tìm kiếm motif EP-C và EP-MK: EP-C sử dụng điểm cực trị quan trọng để phân đoạn chuỗi thời gian thành các chuỗi con, sau đó gom cụm để tìm motif ứng viên. EP-MK kết hợp EP-C với giải thuật MK, tận dụng kỹ thuật loại bỏ sớm và điểm tham chiếu để tăng tốc độ tìm kiếm motif.
• Độ đo khoảng cách: Sử dụng độ đo Euclid, Dynamic Time Warping (DTW) cho dữ liệu liên tục và các độ đo trên dữ liệu rời rạc như Hamming cho vector đặc trưng nhị phân.
• Biểu diễn vector đặc trưng: Chuỗi thời gian được biểu diễn thành vector nhị phân dựa trên sự xuất hiện của các motif, giúp áp dụng các thuật toán phân lớp truyền thống dễ dàng hơn.

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

• Nguồn dữ liệu: Sử dụng các bộ dữ liệu chuỗi thời gian thực nghiệm đa dạng, bao gồm dữ liệu về chuyển động, y tế, cảm biến với kích thước và đặc điểm khác nhau.
• Phương pháp chọn mẫu: Tập dữ liệu huấn luyện và kiểm thử được phân chia theo tỷ lệ chuẩn, đảm bảo tính đại diện và khách quan trong đánh giá.
• Quy trình nghiên cứu:
  1. Tiền xử lý dữ liệu: chuẩn hóa min-max hoặc z-score để loại bỏ nhiễu và chuẩn hóa giá trị.
  2. Tìm kiếm motif bằng giải thuật EP-C và EP-MK dựa trên điểm cực trị quan trọng.
  3. Biểu diễn chuỗi thời gian thành vector đặc trưng nhị phân dựa trên sự xuất hiện của motif.
  4. Phân lớp dữ liệu bằng thuật toán k-NN với k=7, sử dụng độ đo trên dữ liệu rời rạc.
  5. So sánh kết quả với phương pháp phân lớp truyền thống k-NN sử dụng độ đo Euclid.
• Phương pháp phân tích: Đánh giá độ chính xác, tỷ lệ lỗi, thời gian tìm kiếm motif và phân lớp. Sử dụng ma trận nhầm lẫn để phân tích chi tiết hiệu suất phân lớp.
• Timeline nghiên cứu: Nghiên cứu và phát triển giải thuật từ tháng 7 đến tháng 12 năm 2017, bao gồm giai đoạn thu thập dữ liệu, thực hiện thử nghiệm và phân tích kết quả.

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

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

1. Cải thiện độ chính xác phân lớp: Phân lớp dựa trên thông tin motif cho độ chính xác cao hơn từ 5% đến 12% so với phân lớp truyền thống k-NN với độ đo Euclid trên tất cả các bộ dữ liệu thử nghiệm.
2. Hiệu quả tìm kiếm motif: Giải thuật EP-MK có thời gian tìm kiếm motif nhanh hơn EP-C khoảng 20-30%, trong khi độ chính xác phân lớp giữa hai giải thuật gần tương đương nhau.
3. Ảnh hưởng của tham số: Việc ước lượng tham số như tỷ lệ nén R, giá trị ngưỡng tương tự trong so trùng chuỗi con và số lượng cụm trong gom cụm ảnh hưởng lớn đến kết quả phân lớp, với các tham số được đề xuất phù hợp với mô hình.
4. Giảm thời gian xử lý: Phân đoạn chuỗi thời gian dựa trên điểm cực trị quan trọng giúp giảm đáng kể thời gian xử lý và loại bỏ dữ liệu nhiễu, tăng hiệu quả tính toán.

Thảo luận kết quả

Nguyên nhân cải thiện độ chính xác phân lớp là do việc sử dụng motif giúp trích xuất đặc trưng quan trọng, giảm ảnh hưởng của nhiễu và dữ liệu dư thừa. So với các nghiên cứu trước đây sử dụng giải thuật Brute Force hoặc Random Projection, EP-C và EP-MK tận dụng điểm cực trị quan trọng để phân đoạn chuỗi thời gian, giúp giảm số lượng chuỗi con cần xử lý, từ đó tăng tốc độ tìm kiếm motif.

Kết quả thực nghiệm cũng cho thấy EP-MK kết hợp ưu điểm của EP-C và MK, vừa phân đoạn hiệu quả vừa áp dụng kỹ thuật loại bỏ sớm và điểm tham chiếu để giảm thời gian tính toán. Biểu đồ so sánh thời gian tìm kiếm motif giữa EP-C và EP-MK minh họa rõ sự vượt trội về tốc độ của EP-MK.

Việc biểu diễn chuỗi thời gian thành vector đặc trưng nhị phân dựa trên motif giúp áp dụng các thuật toán phân lớp truyền thống như k-NN, SVM, ANN dễ dàng hơn, đồng thời nâng cao khả năng phân biệt các lớp dữ liệu. So sánh với các phương pháp phân lớp không sử dụng motif, cách tiếp cận này cho thấy sự vượt trội về độ chính xác và tính ổn định.

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

1. Áp dụng giải thuật EP-MK trong hệ thống phân lớp: Khuyến nghị sử dụng EP-MK để tìm kiếm motif nhằm giảm thời gian xử lý, đặc biệt với dữ liệu chuỗi thời gian lớn. Thời gian triển khai dự kiến trong vòng 3-6 tháng, do các nhóm nghiên cứu hoặc doanh nghiệp phát triển phần mềm.
2. Tối ưu tham số thuật toán: Đề xuất xây dựng quy trình ước lượng tham số tự động cho tỷ lệ nén R, ngưỡng tương tự và số lượng cụm nhằm tối ưu hóa kết quả phân lớp. Thời gian thực hiện khoảng 2-3 tháng, phù hợp cho các nhóm nghiên cứu hoặc kỹ sư dữ liệu.
3. Mở rộng ứng dụng sang các lĩnh vực mới: Khuyến khích áp dụng phương pháp phân lớp dựa trên motif trong các lĩnh vực như y tế, robot, khí tượng học để nâng cao hiệu quả phân tích dữ liệu chuỗi thời gian. Chủ thể thực hiện là các tổ chức nghiên cứu và doanh nghiệp công nghệ.
4. Phát triển công cụ phần mềm hỗ trợ: Đề xuất xây dựng phần mềm tích hợp giải thuật EP-MK và phân lớp k-NN với giao diện thân thiện, hỗ trợ người dùng trong việc phân tích dữ liệu chuỗi thời gian. Thời gian phát triển dự kiến 6-9 tháng, do các công ty phần mềm hoặc nhóm nghiên cứu đảm nhận.

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

1. Nhà nghiên cứu và sinh viên ngành Khoa học máy tính: Luận văn cung cấp kiến thức chuyên sâu về phân lớp dữ liệu chuỗi thời gian và kỹ thuật tìm kiếm motif, hỗ trợ nghiên cứu và phát triển các thuật toán mới.
2. Kỹ sư dữ liệu và chuyên gia phân tích dữ liệu: Áp dụng phương pháp biểu diễn vector đặc trưng và giải thuật EP-MK giúp cải thiện hiệu quả phân tích và phân lớp dữ liệu chuỗi thời gian trong thực tế.
3. Doanh nghiệp công nghệ và phát triển phần mềm: Tham khảo để tích hợp giải thuật phân lớp dựa trên motif vào các sản phẩm phân tích dữ liệu, nâng cao chất lượng dịch vụ và sản phẩm.
4. Ngành y tế và kỹ thuật: Sử dụng phương pháp phân lớp chuỗi thời gian để phân tích dữ liệu y sinh, chuẩn đoán bệnh hoặc xử lý tín hiệu cảm biến, góp phần nâng cao hiệu quả chẩn đoán và điều trị.

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

1. Motif là gì và tại sao quan trọng trong phân lớp chuỗi thời gian?
   Motif là chuỗi con lặp lại thường xuyên trong chuỗi thời gian, giúp trích xuất đặc trưng quan trọng, giảm nhiễu và tăng độ chính xác phân lớp. Ví dụ, trong nhận dạng chuyển động, motif thể hiện các mẫu chuyển động lặp lại.

2. Giải thuật EP-C và EP-MK khác nhau như thế nào?
   EP-C phân đoạn chuỗi thời gian dựa trên điểm cực trị quan trọng và gom cụm để tìm motif, trong khi EP-MK kết hợp EP-C với kỹ thuật loại bỏ sớm và điểm tham chiếu của giải thuật MK, giúp tăng tốc độ tìm kiếm motif.

3. Tại sao cần biểu diễn chuỗi thời gian thành vector đặc trưng?
   Việc này giúp chuyển dữ liệu chuỗi thời gian phức tạp thành dạng dễ xử lý bằng các thuật toán phân lớp truyền thống như k-NN, SVM, ANN, đồng thời giữ lại thông tin quan trọng từ motif.

4. Giải thuật k-NN được sử dụng như thế nào trong phân lớp?
   k-NN phân lớp dựa trên nhãn của k mẫu gần nhất trong không gian vector đặc trưng. Trong nghiên cứu này, k=7 được chọn để cân bằng giữa độ nhạy và khả năng chống nhiễu.

5. Phương pháp này có thể áp dụng cho dữ liệu lớn không?
   Có, nhờ sử dụng điểm cực trị quan trọng để phân đoạn và kỹ thuật thu giảm thời gian tính toán, phương pháp này phù hợp với dữ liệu chuỗi thời gian lớn, giảm đáng kể chi phí xử lý so với các phương pháp truyền thống.

Kết luận

• Luận văn đã xây dựng thành công hệ thống phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif, sử dụng giải thuật EP-C và EP-MK để tìm kiếm motif hiệu quả.
• Phương pháp biểu diễn chuỗi thời gian thành vector đặc trưng dựa trên motif giúp áp dụng các thuật toán phân lớp truyền thống dễ dàng và nâng cao độ chính xác.
• Kết quả thực nghiệm cho thấy phân lớp dựa trên motif cải thiện độ chính xác từ 5% đến 12% và giảm thời gian xử lý so với phương pháp truyền thống.
• EP-MK vượt trội về tốc độ tìm kiếm motif so với EP-C, trong khi chất lượng phân lớp tương đương.
• Hướng phát triển tiếp theo là tối ưu tham số thuật toán, mở rộng ứng dụng và phát triển công cụ phần mềm hỗ trợ.

Các nhà nghiên cứu và kỹ sư dữ liệu nên áp dụng và thử nghiệm giải thuật EP-MK trong các dự án phân tích dữ liệu chuỗi thời gian để nâng cao hiệu quả và độ chính xác phân lớp.

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

Chương 1. Giới thiệu van dé Giới thiệu sơ lược về bài toán phân lớp dữ liệu chuỗi thời gian dựa trên thông tin motif, mục tiêu, nhiệm vu, giới hạn của đề tài, những kết quả luận văn đã đạt được, cấu trúc và tong quan từng chương của luận văn. Cơ sở lý thuyết Trình bày về các khái niệm và các vẫn đề có liên quan đến dữ liệu chuỗi thời gian, phân lớp, gom cụm dir liệu, các độ đo khoảng cách. được sử dung trong các chương sau của đề tài luận văn.

Các công trình liên quan Trình bày về các công trình khoa học liên quan đến bài toán tìm kiếm motif và phân lớp dữ liệu dựa trên thông tin motif đồng thời đánh giá về những ưu điểm và hạn chế của những công trình này Chương 4. Phương pháp giải quyết van dé Từ những đánh giá về các công trình khoa học liên quan, chương 4 sẽ đưa ra hướng tiếp cận dé giải quyết bai toán phân lớp dựa trên thông tin motif của dé tài luận văn đồng thời chi tiết về cách áp dụng các giải thuật liên quan trong qua trình phân lớp dữ liệu. Thực nghiệm Đề xuất cách ước lượng các tham số sử dụng trong giải thuật tìm kiếm điểm cực trị quan trọng, so trùng chuỗi con, gom cụm và trình bày những kết qua phan lớp trên các bộ dữ liệu mau với các motif tim kiếm bang giải thuật EP-C, EP-MK đồng thời so sánh kết quả phân lớp với cách tiếp cận truyền thống phân lớp bang giải thuật #-NN và độ do Euclid cũng như so sánh kết quả phân lớp giữa motif tìm kiếm băng giải thuật EP-C và EP-MK. Kết luận Trình bày tóm lược lại những van dé chính của luận văn, những kết quả đã đạt được và hướng phát triển đề tài.

Tài liệu tham khảo Phụ lục CHƯƠNG 2. CƠ SỞ LÝ THUYET Chương nay sẽ trình bay các khái niệm va van dé có liên quan về phân lớp dữ liệu, chuỗi thời gian, gom cụm, các phương pháp thu giảm số chiều, rời rạc hóa chuỗi thời gian, các độ đo và cách đánh giá chất lượng của sự phân lớp. Phân lớp dữ liệu 2. Giới thiệu Phân lớp (classification) là dang phân tích dữ liệu nhằm rút trích các mô hình mô tả các lớp dữ liệu hoặc dự đoán xu hướng dữ liệu từ các mô hình đó.

Quá trình phan lớp gồm hai bước chính là hudn luyện (training) va phân lớp. Tại bước huẫn luyện sẽ tiến hành xây dựng Đô phân lớp (classifier) bang việc phân tích tập dữ liệu huấn luyện với các mẫu và nhãn lớp (class label) tương ứng. Một mẫu dữ liệu X được biểu diễn bởi một vecfor thuộc tính (attribute vector) X = (x1, X2, ., Xn) VỚI m là số lượng thuộc tính của tập dữ liệu huấn luyện. Bước huấn luyện có thé xem như là quá trình học của một ham ánh xạ: y = ƒ#{#) với y là nhãn lớp được dự đoán của mẫu X.

Thông thường ham ánh xạ được biểu diễn dưới dạng luật phân lớp, cây quyết định hoặc các công thức toán học. Tại bước phân lớp, bộ phân lớp được sử dụng dé thực hiện gan nhãn lớp cho các mau trong tap dit liệu kiểm thử (test set). Nếu độ chính xác của bộ phân lớp chấp nhận được thì bộ phân lớp có thể sử dụng để gán nhãn cho những mẫu chưa biết nhãn lớp. Trong lĩnh vực khai phá dữ liệu, phân lớp là một kỹ thuật rất phố biến, quan trọng và được áp dụng trong nhiều lĩnh vực như kinh tế, tài chính, y tế, an ninh,.

ƒ ‘yy ——_Ò_Ò _ | Classification algorithm XX J. al a = Training data -— | name age income loan_decision Sandy Jones youth low risky Bill Lee youth low risky ' Caroline Fox middle_aged high safe ————— Rick Field middle aged low risky —————— Susan Lake senior low safe Classification rules Claire Phips senior medium safe xui ==. Joe Smith middle_aged high safe ¬ * IF ave = youth THEN loan_decision = risky IF income = high THEN loan decision = safe IF age = middle_aged AND income = low THEN loan_ decision = risky Hình 2. Vi dụ về bai toán phân lớp dit liệu [7] 5 Hình 2.1 là ví dụ về ứng dung bai toán phân lớp trong van dé cho vay.

Từ tập dữ liệu về khách hàng cho vay trong quá khứ, giải thuật phân lớp sẽ thực hiện huấn luyện. Kết quả của quá trình huấn luyện là các luật phân lớp. Đối với phân lớp dữ liệu cũng như tác vụ khai phá dữ liệu khác, công việc xử lý dữ liệu trước khi đưa vào các mô hình là rất cần thiết, bước tiền xử lý giúp cho dữ liệu gốc có được qua thu thập có thể áp dụng được với các mô hình khai phá dữ liệu cụ thé. Tiền xử lý dữ liệu có thé giúp cải thiện kết qua phân lớp, một số kỹ thuật tiền xử lý thường được sử dụng gồm: = Làm sạch dữ liệu: các dữ liệu thu thập trong thực tế thường có xu hướng không day du, tồn tại dữ liệu nhiễu va dữ liệu không đồng nhất.

Làm sạch dit liệu có thé bồ sung những dữ liệu bị thiếu, loại bỏ nhiễu và khắc phục sự không đồng nhất. “ Tích hợp dữ liệu: dữ liệu có thé lẫy từ nhiều nguồn khác nhau. Tích hợp dữ liệu giúp giảm thiểu và hạn chế dư thừa dữ liệu. # Thu giảm dữ liệu: trường hop dữ liệu có kích thước lớn sẽ tăng độ phức tạp cho việc phân tích, tính toán.

Thu giảm dữ liệu giúp giảm kích thước dữ liệu bằng các loại bỏ những phan dư thừa va gift lai những đặc điểm chính của đữ liệu. = Biến đổi và rời rac hóa dữ liệu: giúp cho việc khai pha dữ liệu trở nên hiệu quả, và các mô hình trở nên dễ hiểu hơn, tăng độ tổng quát thông tin, giúp cho việc đơn giản hóa việc biểu diễn cũng như xử lý trên dữ liệu số. Giải thuật phan lớp k-NN Giải thuật &-NN (k-Nearest Neighbor) được sử dụng rat phố biến trong lĩnh vực khai phá dữ liệu nói chung và trong bài toán phân lớp nói riêng. Đây là phương pháp để phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần gán nhãn lớp và tất cả các đối tượng khác trong tập huấn luyện.

Với giải thuật #-NN thì một đối tượng sẽ được phân lớp theo lớp chiếm đa số trong & lân cận của nó, trong đó k là số nguyên dương được chọn khi thực hiện thuật toán. Việc chon giá tri k rat quan trong vi néu chon k qua nho thi két qua sé dé bi anh hưởng bởi nhiễu. còn nếu chọn k quá lớn thì nhiều phan tử lân cận chọn được có thé đến từ các lớp khác. Giải thuật k-NN [13] Trong hình 2.a với k = 1, mẫu ? sẽ thuộc lớp của lân cận gan nhất là lớp hình vuông.b với k = 4, mẫu ? sẽ thuộc lớp chiếm da số trong 4 lân cận gân nhất.

4 lân cận gần nhất của mẫu ? gồm 3 mẫu thuộc lớp hình vuông và 1 mẫu thuộc lớp tam giác, vì vậy mẫu ? thuộc lớp hình vuông. Máy vector hỗ trợ (Support Vector Machines — SVMs) SVMs là một phương pháp có thé phân lớp cho cả dir liệu tuyến tinh va dữ liệu phi tuyến. SVMs sử dụng một ham ánh xa phi tuyến dé ánh xạ dữ liệu gốc trong không gian ban đầu thành vào một không gian mới với số chiều nhiều hơn bằng cách sử dung các ham kernel phù hợp. Trong không gian mới SVMs sẽ tìm kiếm một siêu phang (hyperplane) dé phân tách tập dữ liệu thành hai lớp.

Ngoài sử dụng cho mục đích phân lớp, SVMs còn có thé sử dụng trong các tác vụ khai phá dữ liệu khác như hồi quy, gom cum,. Mac dù có thời gian huẫn luyện chậm nhưng phân lớp sử dung SVMs cho kết quả có độ chính xác cao và có khả năng phân lớp với những mô hình có đường biên quyết định (decision boundaries) phi tuyến phức tạp. Ngoài ra SVMs ít bị tình trạng gud khớp (overfitting) so với các phương pháp khác. SVMs được áp dụng trong một vai lĩnh vực thực tế như nhận dạng chữ số viết tay, nhận dạng giọng nói, nhận dạng đối tượng.

Mang nơ ron nhân tao (Artificial Neural Network - ANN). ANN là mô hình xử lý thông tin được mô phỏng dựa trên hoạt động của hệ thống thần kinh của sinh vật, bao gồm số lượng lớn các nơ ron được gan kết dé xử lý thông tin. ANN giống như bộ não con người, được học bởi kinh nghiệm thông qua huấn luyện, có khả năng lưu giữ những tri thức và sử dụng những tri thức đó trong việc phân lớp dữ liệu. ANN gồm tập hợp các nút được liên kết với nhau, mỗi liên kết giữa hai nút có một trọng số tương ứng.

Thông qua quá trình huấn luyện, ANN sẽ điều chỉnh các trọng số sao cho có thé dự đoán đúng nhãn lớp của các mẫu dữ liệu. Một trong những loại mạng no ron thông dung là mang nơ ron truyền thang da tang (Multilayer Feed-Forward Neural Network) (Hình 2. Input Hidden Output layer layer layer C : fey 1 K Hình 2. Mạng nơ ron truyền thăng đa tầng [7] Mạng nơ ron truyền thang đa tang gồm một fdng nhập (input layer), một hoặc nhiều fang ẩn (hidden layer) và một tang xuất (output layer).

Đối với bài toán phân lớp dữ liệu, số nút tại tầng nhập bang số lượng thuộc tính của mẫu dữ liệu huấn luyện, số nút tại tầng xuất tương ứng với số lượng lớp của bộ dữ liệu huấn luyện. số nút và số tầng của tầng ân được định nghĩa bởi người dùng. Mạng nơ ron có khả năng chịu đựng được đữ /iệu nhiễu (noisy data), có thể sử dụng trong trường hợp các thuộc tính của dit liệu có ít mối liên hệ và thích hợp với các dữ liệu có giá tri liên tuc (continuous-valued). Tuy nhiên nhược điểm của mạng nơ ron là khả năng diễn dịch kém.

Phân lớp dữ liệu chuỗi thời gian Khác với hầu hết các loại dữ liệu thông thường, dữ liệu chuỗi thời gian có ba đặc điêm đặc biệt như sau: dữ liệu chuỗi thời gian có sô chiêu lớn, các diém dir liệu trên chuỗi thời gian có sự tương quan cao và dir liệu có thé bị nhiễu. Chính ba đặc điểm này khiến cho việc phân lớp dữ liệu chuỗi thời gian băng các giải thuật phân lớp thông dụng như: SVMs, ANN, cây quyết định (Decision Tree) trở nên khó khăn và thường cho kết quả không tốt. Vi vậy để có thé dé dang áp dụng các giải thuật phân lớp trên dữ liệu thông thường, dữ liệu chuỗi thời gian cần phải biến đồi thành các vector đặc trưng trước khi thực hiện tác vụ phân lớp. Trong luận văn này, các chuỗi thời gian sẽ được biểu diễn thành các vector đặc trưng trước khi thực hiện phân lớp.