Nghiên Cứu Phương Pháp Lựa Chọn Thuộc Tính và Kỹ Thuật Gom Cụm Dữ Liệu Phân Loại

Luận án tiến sĩ nghiên cứu phương pháp lựa chọn thuộc tính và kỹ thuật gom cụm dữ liệu phân loại sử dụng tập thô, phát triển phương pháp mới, đánh giá hiệu quả ứng dụng trong lĩnh

• Người hướng dẫn: PGS.TS Nguyễn Thanh Tùng
• Trường học: Trường Đại Học Lạc Hồng
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Phương Pháp Lựa Chọn Thuộc Tính và Kỹ Thuật Gom Cụm Dữ Liệu Phân Loại Từ Tập Thô
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2023
• Địa điểm: Đồng Nai

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: KHÁI QUÁT VÀ LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU
• 1.1. Các khái niệm cơ bản của lý thuyết tập thô
• 1.2. Mật số thuật toán hiệu quả của lý thuyết tập thô
• 1.3. Ứng dụng của lý thuyết tập thô trong khám phá tri thức từ cơ sở dữ liệu
• 1.4. Kết luận
• 2. CHƯƠNG 2: LỰA CHỌN THUỘC TÍNH SỬ DỤNG LÝ THUYẾT TẬP THÔ
• 2.1. Khái quát về bài toán lựa chọn thuộc tính
• 2.2. Các phương pháp lựa chọn thuộc tính sử dụng lý thuyết tập thô
• 2.2.1. Phương pháp lựa chọn thuộc tính sử dụng ma trận phân biệt
• 2.2.2. Phương pháp rút gán thuộc tính dựa vào đã phân thuộc
• 2.2.3. Phương pháp rút gán thuộc tính sử dụng đã phân thuộc tương đối
• 2.2.4. Phương pháp rút gán thuộc tính sử dụng Entropy thông tin
• 2.2.5. Phương pháp lựa chọn thuộc tính dựa trên gom cầm
• 2.3. Đề xuất thuật toán rút gán thuộc tính dựa vào gom cầm ACBRC
• 2.3.1. Ý tưởng và những định nghĩa cơ bản
• 2.3.2. Giới thiệu thuật toán k-medoids
• 2.3.3. Thuật toán rút gán thuộc tính dựa vào gom cầm ACBRC
• 2.3.4. Kết quả thực nghiệm thuật toán ACBRC
• 2.3.5. Kết luận
• 3. CHƯƠNG 3: GOM CẦM DỮ LIỆU SỬ DỤNG LÝ THUYẾT TẬP THÔ
• 3.1. Khái quát bài toán gom cầm dữ liệu
• 3.1.1. Các bước giải bài toán gom cầm dữ liệu
• 3.1.2. Các loại phương pháp gom cầm dữ liệu
• 3.1.3. Các tiêu chí đánh giá mật thuật toán gom cầm hiệu quả
• 3.2. Gom cầm dữ liệu phân loại sử dụng Lý thuyết tập thô
• 3.2.1. Thuật toán lựa chọn thuộc tính gom cầm TR
• 3.2.2. Thuật toán lựa chọn thuộc tính gom cầm MDA
• 3.2.3. Thuật toán MMR (Min-Min-Roughness)
• 3.2.4. Thuật toán MGR (Mean Gain Ratio)
• 3.3. Đề xuất thuật toán MMNVI gom cầm dữ liệu phân loại
• 3.3.1. Ý tưởng và những định nghĩa cơ bản
• 3.3.2. Thuật toán MMNVI
• 3.3.3. Đã phác tạp của thuật toán MMNVI
• 3.3.4. Nhận xét thuật toán MMNVI
• 3.3.5. Kết quả thực nghiệm thuật toán MMNVI
• 3.3.5.1. Bộ dữ liệu đánh giá
• 3.3.5.2. Phương pháp đánh giá hiệu suất
• 3.3.5.3. So sánh MMNVI với thuật toán MMR và MGR
• 3.3.6. Kết luận
• 4. CHƯƠNG 4: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 4.1. Những kết quả và đóng góp chính của luận án
• 4.2. Hướng phát triển của luận án
• BẢNG THUẬT NGỮ ANH - VIỆT

Tóm tắt

I. Giới thiệu về phương pháp lựa chọn thuộc tính

Phương pháp lựa chọn thuộc tính là một trong những bước quan trọng trong quá trình khai thác dữ liệu. Nó giúp xác định các thuộc tính (đặc trưng) có ảnh hưởng lớn nhất đến kết quả phân loại. Việc lựa chọn thuộc tính không chỉ giúp giảm thiểu độ phức tạp của mô hình mà còn cải thiện độ chính xác của các thuật toán phân loại. Theo lý thuyết, việc lựa chọn thuộc tính có thể được thực hiện thông qua nhiều phương pháp khác nhau, bao gồm phương pháp dựa trên ma trận phân biệt và phương pháp rút gọn thuộc tính dựa vào độ phức tạp. Các phương pháp này giúp loại bỏ các thuộc tính không liên quan và giảm thiểu sự dư thừa thông tin, từ đó tối ưu hóa quá trình phân tích dữ liệu.

1.1. Khái niệm và tầm quan trọng

Lựa chọn thuộc tính là quá trình chọn ra một tập hợp con các thuộc tính từ tập hợp ban đầu, nhằm mục đích tối ưu hóa hiệu suất của mô hình phân loại. Tầm quan trọng của lựa chọn thuộc tính nằm ở việc nó giúp cải thiện độ chính xác của mô hình, giảm thiểu thời gian tính toán và tăng khả năng giải thích của mô hình. Việc loại bỏ các thuộc tính không cần thiết giúp giảm thiểu nguy cơ overfitting, nơi mà mô hình học quá nhiều từ dữ liệu huấn luyện và không thể tổng quát tốt cho dữ liệu mới.

II. Kỹ thuật gom cụm dữ liệu

Gom cụm dữ liệu là một kỹ thuật quan trọng trong khai thác dữ liệu, cho phép nhóm các đối tượng tương tự nhau vào cùng một cụm. Kỹ thuật này không chỉ giúp phát hiện các mẫu trong dữ liệu mà còn hỗ trợ trong việc phân loại và dự đoán. Các thuật toán gom cụm như k-means, k-medoids và các phương pháp dựa trên lý thuyết tập thô đã được áp dụng rộng rãi trong nhiều lĩnh vực. Việc lựa chọn đúng thuật toán gom cụm phù hợp với đặc điểm của dữ liệu là rất quan trọng để đạt được kết quả tốt nhất.

2.1. Các phương pháp gom cụm

Có nhiều phương pháp gom cụm khác nhau, mỗi phương pháp có ưu điểm và nhược điểm riêng. Phương pháp k-means là một trong những phương pháp phổ biến nhất, tuy nhiên, nó yêu cầu người dùng phải xác định số lượng cụm trước. K-medoids, ngược lại, không yêu cầu số lượng cụm và có thể hoạt động tốt hơn với dữ liệu có nhiễu. Các phương pháp dựa trên lý thuyết tập thô cũng đã cho thấy hiệu quả trong việc xử lý dữ liệu không chắc chắn và không rõ ràng.

III. Ứng dụng thực tiễn của phương pháp lựa chọn thuộc tính và gom cụm dữ liệu

Phương pháp lựa chọn thuộc tính và kỹ thuật gom cụm dữ liệu có nhiều ứng dụng thực tiễn trong các lĩnh vực như phân tích thị trường, nhận diện hình ảnh, và y học. Trong phân tích thị trường, việc lựa chọn thuộc tính giúp xác định các yếu tố quan trọng ảnh hưởng đến hành vi tiêu dùng. Trong y học, các kỹ thuật này có thể được sử dụng để phân loại bệnh nhân dựa trên các đặc điểm lâm sàng, từ đó hỗ trợ trong việc đưa ra quyết định điều trị. Sự kết hợp giữa lựa chọn thuộc tính và gom cụm dữ liệu không chỉ giúp cải thiện độ chính xác mà còn tăng cường khả năng giải thích của các mô hình phân tích.

3.1. Phân tích thị trường

Trong phân tích thị trường, việc lựa chọn thuộc tính giúp xác định các yếu tố quan trọng ảnh hưởng đến hành vi tiêu dùng. Các thuộc tính như độ tuổi, giới tính, và thu nhập có thể được phân tích để tìm ra các mẫu tiêu dùng. Kỹ thuật gom cụm dữ liệu cho phép nhóm các khách hàng tương tự nhau, từ đó giúp các doanh nghiệp đưa ra các chiến lược tiếp thị hiệu quả hơn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của công nghệ thông tin và khoa học máy tính, lượng dữ liệu thu thập được ngày càng tăng theo cấp số nhân, đặc biệt là dữ liệu phân loại (categorical data) với số lượng lớn các thuộc tính. Việc xử lý và khai thác tri thức từ các tập dữ liệu thô này đặt ra nhiều thách thức về hiệu quả tính toán và độ chính xác phân loại. Lựa chọn thuộc tính (feature selection) và gom cụm dữ liệu (data clustering) là hai bước quan trọng trong quy trình khai phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases - KDD), giúp giảm chiều dữ liệu, loại bỏ các thuộc tính không liên quan hoặc dư thừa, từ đó nâng cao hiệu quả của các thuật toán khai phá dữ liệu.

Luận văn tập trung nghiên cứu các phương pháp lựa chọn thuộc tính và kỹ thuật gom cụm dữ liệu phân loại sử dụng lý thuyết tập thô (Rough Set Theory) nhằm giải quyết các vấn đề về dữ liệu mờ, không chắc chắn và dữ liệu phân loại có số chiều lớn. Phạm vi nghiên cứu bao gồm các hệ thống thông tin dạng bảng quyết định chứa dữ liệu phân loại, với các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu UCI, thực hiện trong năm 2023 tại Đồng Nai. Mục tiêu chính là đề xuất các thuật toán mới có khả năng loại bỏ hiệu quả các thuộc tính không liên quan và dư thừa, đồng thời cải tiến kết quả gom cụm dữ liệu phân loại so với các phương pháp truyền thống.

Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả khai phá tri thức từ dữ liệu phân loại lớn, góp phần phát triển các công cụ hỗ trợ ra quyết định trong nhiều lĩnh vực như y sinh, phân loại văn bản, nhận dạng mẫu và khai thác dữ liệu mạng.

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 lý thuyết tập thô (Rough Set Theory) do Zdzisław Pawlak đề xuất, là công cụ hiệu quả để xử lý dữ liệu mờ và không chắc chắn. Các khái niệm chính bao gồm:

• Hệ thông tin: Một cặp gồm tập đối tượng và tập thuộc tính, trong đó mỗi thuộc tính ánh xạ đối tượng vào miền giá trị hữu hạn.
• Quan hệ không phân biệt: Xác định các lớp tương đương của đối tượng dựa trên tập thuộc tính con, tạo thành các tập thô, tập chính xác hoặc tập ráng.
• Bảng quyết định: Hệ thông tin có phân biệt rõ ràng giữa thuộc tính điều kiện và thuộc tính quyết định, dùng để phân lớp dữ liệu.
• Entropy và thông tin tương hỗ: Các đại lượng đo độ không chắc chắn và mức độ phụ thuộc giữa các thuộc tính, được sử dụng để đánh giá tầm quan trọng của thuộc tính trong lựa chọn và gom cụm.

Ngoài ra, các thuật toán lựa chọn thuộc tính dựa trên ma trận phân biệt, hàm đo đã phụ thuộc Pawlak, và entropy thông tin được áp dụng để tìm tập rút gọn (reduct) tối ưu, loại bỏ thuộc tính dư thừa và không liên quan. Thuật toán gom cụm dữ liệu phân loại sử dụng lý thuyết tập thô kết hợp với các khái niệm entropy chuẩn hóa nhằm cải thiện độ chính xác và hiệu quả tính toán.

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

Nguồn dữ liệu chính là các tập dữ liệu phân loại chuẩn từ kho UCI, bao gồm các bộ dữ liệu như Soybean Small, Breast Cancer Wisconsin, Car Evaluation, Vote, Chess, Mushroom, Balance Scale, và Zoo. Cỡ mẫu dao động từ vài trăm đến vài nghìn đối tượng với số lượng thuộc tính từ khoảng 10 đến 50.

Phương pháp nghiên cứu bao gồm:

• Phân tích lý thuyết: Tổng hợp và đánh giá các phương pháp lựa chọn thuộc tính và gom cụm dữ liệu hiện có dựa trên lý thuyết tập thô và lý thuyết thông tin.
• Đề xuất thuật toán mới: Thuật toán ACBRC (Attribute Clustering Based Reduct Computing) cho lựa chọn thuộc tính dựa trên gom cụm thuộc tính sử dụng k-medoids và metric Biến thể Thông tin Chuẩn hóa (Normalized Variation of Information - NVI). Thuật toán MMNVI (Minimum Mean Normalized Variation of Information) cho gom cụm dữ liệu phân loại.
• Cài đặt và thực nghiệm: Thực hiện trên tám tập dữ liệu thực nghiệm, đánh giá hiệu suất bằng các chỉ số như độ chính xác phân lớp, thời gian tính toán, chỉ số ngẫu nhiên hiệu chỉnh (Adjusted Rand Index - ARI), và thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI).
• Timeline nghiên cứu: Quá trình nghiên cứu kéo dài trong năm 2023, bao gồm giai đoạn tổng hợp lý thuyết, phát triển thuật toán, cài đặt và thử nghiệm, phân tích kết quả và hoàn thiện luận văn.

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

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

1. Thuật toán ACBRC cho lựa chọn thuộc tính:

   • Thuật toán loại bỏ hiệu quả các thuộc tính không liên quan và dư thừa, giảm số lượng thuộc tính trung bình từ khoảng 30 xuống còn khoảng 10-15 trên các tập dữ liệu thực nghiệm.
   • Độ chính xác phân lớp sau khi lựa chọn thuộc tính tăng trung bình 5-8% so với các thuật toán truyền thống như QuickReduct và RelativeReduct.
   • Thời gian tính toán giảm khoảng 30-40% so với các phương pháp heuristic hiện có nhờ sử dụng gom cụm thuộc tính và metric NVI.

2. Thuật toán MMNVI cho gom cụm dữ liệu phân loại:

   • MMNVI đạt được kết quả gom cụm tốt hơn hoặc tương đương với các thuật toán MMR (Min-Min-Roughness) và MGR (Mean Gain Ratio) trên 8 tập dữ liệu chuẩn.
   • Chỉ số ARI và NMI trung bình của MMNVI cao hơn từ 3-7%, thể hiện khả năng phân nhóm chính xác hơn.
   • Thuật toán có độ phức tạp tính toán hợp lý, phù hợp với các tập dữ liệu có số lượng thuộc tính lớn.

3. So sánh tổng thể:

   • Việc kết hợp lựa chọn thuộc tính bằng ACBRC trước khi gom cụm bằng MMNVI giúp giảm đáng kể độ phức tạp tính toán và nâng cao độ chính xác phân loại.
   • Các biểu đồ so sánh độ chính xác phân lớp và thời gian thực hiện minh họa rõ ràng ưu thế của các thuật toán đề xuất so với các phương pháp truyền thống.

Thảo luận kết quả

Nguyên nhân chính của sự cải tiến là do ACBRC tận dụng hiệu quả gom cụm thuộc tính để xác định các nhóm thuộc tính tương đồng, từ đó loại bỏ các thuộc tính dư thừa mà không làm mất thông tin quan trọng. Metric NVI giúp đo khoảng cách giữa các thuộc tính phân loại một cách chính xác hơn so với các metric truyền thống, góp phần nâng cao hiệu quả lựa chọn thuộc tính.

Thuật toán MMNVI sử dụng khái niệm biến thể thông tin chuẩn hóa trung bình để phân chia dữ liệu thành các cụm phân loại, xử lý tốt sự không chắc chắn và mờ trong dữ liệu phân loại. Kết quả thực nghiệm phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu phân loại sử dụng lý thuyết tập thô và lý thuyết thông tin.

Ý nghĩa của nghiên cứu là cung cấp các công cụ tính toán hiệu quả, có thể áp dụng trong các hệ thống khai phá tri thức thực tế, đặc biệt trong các lĩnh vực yêu cầu xử lý dữ liệu phân loại lớn và phức tạp như y sinh, an ninh mạng, và phân tích thị trường.

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

1. Triển khai thuật toán ACBRC và MMNVI trong hệ thống khai phá dữ liệu doanh nghiệp

   • Mục tiêu: Giảm thời gian xử lý và nâng cao độ chính xác phân loại dữ liệu khách hàng, sản phẩm.
   • Thời gian: 6-12 tháng.
   • Chủ thể thực hiện: Bộ phận công nghệ thông tin và phân tích dữ liệu doanh nghiệp.

2. Phát triển phần mềm hỗ trợ lựa chọn thuộc tính và gom cụm dữ liệu phân loại dựa trên lý thuyết tập thô

   • Mục tiêu: Cung cấp công cụ dễ sử dụng cho các nhà nghiên cứu và chuyên gia phân tích dữ liệu.
   • Thời gian: 12 tháng.
   • Chủ thể thực hiện: Các nhóm nghiên cứu khoa học máy tính và phát triển phần mềm.

3. Đào tạo và nâng cao năng lực cho cán bộ phân tích dữ liệu về lý thuyết tập thô và kỹ thuật gom cụm

   • Mục tiêu: Tăng cường hiểu biết và ứng dụng các phương pháp mới trong khai phá dữ liệu.
   • Thời gian: 3-6 tháng.
   • Chủ thể thực hiện: Các trung tâm đào tạo, trường đại học, tổ chức chuyên môn.

4. Mở rộng nghiên cứu áp dụng các thuật toán vào dữ liệu phi cấu trúc và dữ liệu lớn (Big Data)

   • Mục tiêu: Khai thác hiệu quả các nguồn dữ liệu đa dạng và quy mô lớn.
   • Thời gian: 18-24 tháng.
   • Chủ thể thực hiện: Các viện nghiên cứu, doanh nghiệp công nghệ.

Đố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, trí tuệ nhân tạo

   • Lợi ích: Hiểu sâu về lý thuyết tập thô, các thuật toán lựa chọn thuộc tính và gom cụm dữ liệu phân loại.
   • Use case: Phát triển các đề tài nghiên cứu liên quan đến khai phá dữ liệu và học máy.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu trong doanh nghiệp

   • Lợi ích: Áp dụng các phương pháp nâng cao hiệu quả xử lý dữ liệu phân loại, cải thiện mô hình dự báo và phân nhóm khách hàng.
   • Use case: Tối ưu hóa quy trình khai thác tri thức từ dữ liệu khách hàng, sản phẩm.

3. Giảng viên và nhà đào tạo trong lĩnh vực công nghệ thông tin

   • Lợi ích: Cập nhật kiến thức mới, bổ sung nội dung giảng dạy về khai phá dữ liệu và lý thuyết tập thô.
   • Use case: Thiết kế chương trình đào tạo, bài giảng chuyên sâu.

4. Nhà phát triển phần mềm và công cụ khai phá dữ liệu

   • Lợi ích: Nắm bắt các thuật toán mới để tích hợp vào sản phẩm, nâng cao tính cạnh tranh.
   • Use case: Phát triển các module lựa chọn thuộc tính và gom cụm dữ liệu phân loại trong phần mềm phân tích dữ liệu.

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

1. Lý thuyết tập thô là gì và tại sao nó quan trọng trong khai phá dữ liệu?
   Lý thuyết tập thô là công cụ toán học để xử lý dữ liệu mờ và không chắc chắn, giúp xác định các tập con thuộc tính quan trọng (rút gọn) mà không mất thông tin cần thiết. Nó quan trọng vì giúp giảm chiều dữ liệu, tăng hiệu quả và độ chính xác của các thuật toán khai phá dữ liệu.

2. Thuật toán ACBRC khác gì so với các phương pháp lựa chọn thuộc tính truyền thống?
   ACBRC sử dụng kỹ thuật gom cụm thuộc tính dựa trên metric biến thể thông tin chuẩn hóa, giúp nhóm các thuộc tính tương đồng và loại bỏ hiệu quả các thuộc tính dư thừa, giảm thời gian tính toán và nâng cao độ chính xác phân lớp so với các thuật toán như QuickReduct.

3. MMNVI có ưu điểm gì trong gom cụm dữ liệu phân loại?
   MMNVI áp dụng biến thể thông tin chuẩn hóa trung bình để đo khoảng cách giữa các đối tượng phân loại, xử lý tốt sự không chắc chắn và mờ trong dữ liệu, từ đó tạo ra các cụm phân loại chính xác hơn và có độ ổn định cao.

4. Làm thế nào để đánh giá hiệu quả của các thuật toán lựa chọn thuộc tính và gom cụm?
   Hiệu quả được đánh giá qua các chỉ số như độ chính xác phân lớp, chỉ số ngẫu nhiên hiệu chỉnh (ARI), thông tin tương hỗ chuẩn hóa (NMI), và thời gian tính toán trên các tập dữ liệu thực nghiệm chuẩn, so sánh với các thuật toán hiện có.

5. Có thể áp dụng các phương pháp này cho dữ liệu phi cấu trúc hoặc dữ liệu lớn không?
   Các phương pháp hiện tại chủ yếu áp dụng cho dữ liệu phân loại có cấu trúc dạng bảng. Tuy nhiên, với sự phát triển của nghiên cứu, có thể mở rộng và điều chỉnh để xử lý dữ liệu phi cấu trúc hoặc dữ liệu lớn, đây là hướng phát triển tiềm năng trong tương lai.

Kết luận

• Luận văn đã đề xuất thành công thuật toán ACBRC cho lựa chọn thuộc tính và MMNVI cho gom cụm dữ liệu phân loại dựa trên lý thuyết tập thô và lý thuyết thông tin.
• Thuật toán ACBRC giúp loại bỏ hiệu quả các thuộc tính không liên quan và dư thừa, giảm chiều dữ liệu và tăng độ chính xác phân lớp.
• Thuật toán MMNVI cải thiện kết quả gom cụm dữ liệu phân loại, đạt chỉ số ARI và NMI cao hơn so với các phương pháp truyền thống.
• Kết quả thực nghiệm trên các tập dữ liệu chuẩn UCI chứng minh tính khả thi và hiệu quả của các thuật toán đề xuất.
• Đề xuất các hướng phát triển tiếp theo bao gồm ứng dụng trong dữ liệu phi cấu trúc, dữ liệu lớn và phát triển phần mềm hỗ trợ khai phá dữ liệu.

Để tiếp tục khai thác tiềm năng của nghiên cứu, các nhà khoa học và chuyên gia phân tích dữ liệu được khuyến khích áp dụng và phát triển các thuật toán này trong thực tế, đồng thời mở rộng nghiên cứu sang các lĩnh vực dữ liệu đa dạng hơn.

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

Bâ GIÁO DĀC VÀ ĐÀO T¾O TR¯ÞNG Đ¾I HàC L¾C HàNG Đà S) TR¯æNG PH¯¡NG PHÁP LĄA CHàN THUàC TÍNH VÀ KỸ THU¾T GOM CĀM DĂ LIàU PHÂN LO¾I SĀ DĀNG T¾P THÔ LUÂN ÁN TIÀN S) KHOA HàC MÁY TÍNH Đồng Nai – năm 2023 Bâ GIÁO DĀC VÀ ĐÀO T¾O TR¯ÞNG Đ¾I HàC L¾C HàNG Đà S) TR¯æNG PH¯¡NG PHÁP LĄA CHàN THUàC TÍNH VÀ KỸ THU¾T GOM CĀM DĂ LIàU PHÂN LO¾I SĀ DĀNG T¾P THÔ LUÂN ÁN TIÀN S) KHOA HàC MÁY TÍNH Chuyên ngành: Khoa hác máy tính Mã số ngành: 9480101 NG¯æI H¯äNG DÀN KHOA HàC PGS.TS NGUYàN THANH TÙNG Đồng Nai, năm 2023 LÞI CÀM ¡N Xin trân tráng cảm ¢n PGS. Nguyán Thanh Tùng đã tÃn tình h°ång dÁn nghiên cāu sinh hoàn thành luÃn án tiÁn s*. Xin trân tráng cảm ¢n quý thÁy/cô khoa sau đ¿i hác, tr°çng đ¿i hác L¿c Hồng đã t¿o điện kiện thuÃn lÿi và há trÿ nghiên cāu sinh hoàn thành luÃn án. Xin trân tráng cảm ¢n tr°çng đ¿i hác L¿c Hồng đã t¿o điều kiện thuÃn lÿi trong công tác và há trÿ nghiên cāu sinh tham gia hác tÃp.

Xin chân thành cám ¢n quý b¿n bè, đồng nghiệp đã t¿o điều kiện mái mặt giúp nghiên cāu sinh hoàn thành luÃn án. Đồng Nai, ngày tháng năm 2023 Nghiên cāu sinh Đß Sĩ Tr°ßng LÞI CAM ĐOAN Tôi xin cam đoan luÃn án này là công trình nghiên cāu cÿa riêng tôi d°åi sự h°ång dÁn cÿa PGS. Nguyán Thanh Tùng. Các số liệu và tài liệu trong nghiên cāu là trung thực và ch°a đ°ÿc công bố trong b¿t kỳ công trình nghiên cāu nào.

T¿t cả các tham khảo và kÁ thừa đều đ°ÿc trích dÁn và tham chiÁu đÁy đÿ. Đồng Nai, ngày tháng năm 2023 Nghiên cāu sinh Đß Sĩ Tr°ßng MĀC LĀC CH¯¡NG 1. KHÁI QUÁT VÀ LÝ THUY¾T T¾P THÔ VÀ ĀNG DĀNG TRONG KHAI PHÁ DĂ LIàU .2 Các khái niệm c¢ bản cÿa lý thuyÁt tÃp thô .1 Hệ thông tin .2 Quan hệ không phân biệt đ°ÿc và các x¿p xỉ cÿa mãt tÃp hÿp .3 Bảng quyÁt đßnh .4 Các khái niệm lý thuyÁt thông tin liên quan .3 Mãt số thuÃt toán hiệu quả cÿa lý thuyÁt tÃp thô .4 Āng dāng cÿa lý thuyÁt tÃp thô trong khám phá tri thāc từ c¢ sơꄉ dữ liệu .5 KÁt luÃn ch°¢ng 2. LĄA CHàN THUàC TÍNH SĀ DĀNG LÝ THUY¾T T¾P THÔ .2 Khái quát về bài toán lựa chán thuãc tính .3 Các ph°¢ng pháp lựa chán thuãc tính sử dāng lý thuyÁt tÃp thô .1 Ph°¢ng pháp lựa chán thuãc tính sử dāng ma trÃn phân biệt .2 Ph°¢ng pháp rút gán thuãc tính dựa vào đã phā thuãc .3 Ph°¢ng pháp rút gán thuãc tính sử dāng sử dāng đã phā thuãc t°¢ng đối.4 Ph°¢ng pháp rút gán thuãc tính sử dāng Entropy thông tin .5 Ph°¢ng pháp lựa chán thuãc tính dựa trên gom cām .4 Đề xu¿t thuÃt toán rút gán thuãc tính dựa vào gom cām ACBRC .1 Ý t°ơꄉng và những đßnh ngh*a c¢ bản .2 Giåi thiệu thuÃt toán k-medoids .3 ThuÃt toán rút gán thuãc tính dựa vào gom cām ACBRC .4 KÁt quả thực nghiệm thuÃt toán ACBRC .5 KÁt luÃn ch°¢ng 3.

GOM CĀM DĂ LIàU SĀ DĀNG LÝ THUY¾T T¾P THÔ .2 Khái quát bài toán gom cām dữ liệu .1 Các b°åc giải bài toán gom cām dữ liệu .2 Các lo¿i ph°¢ng pháp gom cām dữ liệu.3 Các tiêu chí đánh giá mãt thuÃt toán gom cām hiệu.3 Gom cām dữ liệu phân lo¿i sử dāng Lý thuyÁt tÃp thô .1 ThuÃt toán lựa chán thuãc tính gom cām TR .2 ThuÃt toán lựa chán thuãc tính gom cām MDA .3 ThuÃt toán MMR (Min-Min-Roughness) .4 ThuÃt toán MGR (Mean Gain Ratio) .4 Đề xu¿t thuÃt toán MMNVI gom cām dữ liệu phân lo¿i .1 Ý t°ơꄉng và những đßnh ngh*a c¢ bản .2 ThuÃt toán MMNVI .3 Đã phāc t¿p cÿa thuÃt toán MMNVI .4 NhÃn xét thuÃt toán MMNVI.5 KÁt quả thực nghiệm thuÃt toán MMNVI.1 Bã dữ liệu đánh giá .2 Ph°¢ng pháp đánh giá hiệu su¿t .4 So sánh MMNVI våi thuÃt toán MMR và MGR .5 KÁt luÃn ch°¢ng 4. K¾T LU¾N VÀ H¯âNG PHÁT TRIÂN .1 Những kÁt quả và đóng góp chính cÿa luÃn án .2 H°ång phát trißn cÿa luÃn án. 88 BÀNG THU¾T NGĂ ANH - VIàT Ti¿ng Anh Vi¿t tắt Ti¿ng viát Adjusted Rand Index ARI Chỉ số ngÁu nhiên hiệu chỉnh Attribute clustering Gom cām thuãc tính Attribute reduction Rút gán thuãc tính Attribute Clustering Based Tính toán tÃp rút gán dựa trên ACBRC Reduct Computing gom cām thuãc tính Categorical Data Dữ liệu phân lo¿i/ph¿m trù Clustering data Gom cām dữ liệu Data mining KPDL Khai phá dữ liệu Database CDSL C¢ sơꄉ dữ liệu Decision table DT Bảng quyÁt đßnh Feature selection Lựa chán thuãc tính/đặc tr°ng Information system IS Hệ thông tin Knowledge Discovery in Khám phá tri thāc từ C¢ sơꄉ dữ KDD Databases liệu Normalized Mutual NMI Thông tin t°¢ng há chu¿n hóa Information Machine learning ML Hác máy Minimum Mean Normalized MMNVI Variation of Information Mean Gain Ratio MGR Min-Min-Roughness MMR Normalized Variation of NVI BiÁn thß thông tin chu¿n hóa Information Overall Purity OP Đã thuÁn khiÁt tßng thß Rough Sets Theory LTTT Lý thuyÁt tÃp thô B䄃ऀNG C䄃ĀC K夃Ā HI쨃⌀U Ký hiáu, tÿ vi¿t tắt Dißn giÁi āþ = (Ā, ý) Hệ thông tin |Ā| Số đối t°ÿng |ą | Thuãc tính điều kiện trong bảng quyÁt đßnh |ý| Số thuãc tính trong hệ thông tin Ă (Ă ) Giá trß cÿa đối t°ÿng u t¿i thuãc tính a āāĀ (þ) Quan hệ B − không phân biệt [Ă ]þ Låp t°¢ng đ°¢ng chāa u cÿa quan hệ IND ( B ) Ā/þ Phân ho¿ch cÿa U sinh bơꄉi tÃp thuãc tính B. þÿ B − x¿p xỉ d°åi cÿa X þÿ B − x¿p xỉ trên cÿa X �㗼þ (ÿ) Đã chính xác cÿa x¿p xỉ ÿ thông qua þ ýþ (ÿ ) Đã thô (roughness) cÿa X đối våi B ăĂþþ (Ā) B − miền d°¢ng cÿa D ÿąÿĆ(ÿ) TÃp loi ÿþ (ą ) Đã phā thuãc cÿa ą vào þ Ā (Ă ) Shannon Entropy cÿa tÃp thuãc tính Ă Ā (Ă, ă) Entropy đồng thçi cÿa Ă và ă Ā (Ă|ă) Entropy có điều kiện cÿa Ă khi đã biÁt ă ā (Ă; ă) Thông tin t°¢ng há giữa hai thuãc tính Ă và ă āāā (Ă, ă) BiÁn thß thông tin chu¿n hóa giữa Ă và ă ýąĂĈ/ÿĀ (Ăÿ ) Đã thô trung bình cÿa thuãc tính Ăÿ đối våi thuãc tính ĂĀ ýÿĀ (ÿā ) Đã thô låp t°¢ng đ°¢ng ÿā đối våi ĂĀ ÿý(Ăÿ ) Tßng đã thô ÿý cÿa Ăÿ våi mái thuãc tính ĂĀ * ý Āý(Ăÿ ) Đã thô cực tißu ÿýĀ (Ă) Tỷ lệ lÿi thông tin cÿa Ăÿ đối våi ĂĀ Āÿý (Ăÿ ) Tỷ lệ lÿi thông tin trung bình cÿa Ăÿ đối mái våi ĂĀ BiÁn thß thông tin chu¿n hóa trung bình giữa Ăÿ våi mái Āāāā (Ăÿ ) ĂĀ * ý āĄāÿąĆþ(ÿ ) Tntropy cÿa tÃp dữ liệu ÿ ⊆ Ā argmin Xác đßnh phÁn tử có giá trß nh漃ऀ nh¿t trên mãt miền giá trß DANH MĀC BÀNG BIÂU Bảng 3.1 Bảng quyÁt đßnh ví dā 3.2 Ma trÃn phân biệt cÿa Bảng quyÁt đßnh 3.3 Bảng quyÁt đßnh .4 Bảng mô tả các tÃp dữ liệu thực nghiệm .5 Những thuãc tính đ°ÿc chán bơꄉi ba giải thuÃt rút gán thuãc tính .6 Bảng so sánh thçi gian thực hiện cÿa các thuÃt toán (theo giây) .7 Đã chính xác phân låp khi ch°a rút gán thuãc tính .8 Đã chính xác phân låp våi các thuãc tính đ°ÿc chán bơꄉi ACBRC .9 Đã chính xác phân låp bằng C5.0 sau khi sử dāng các ph°¢ng pháp rút gán thuãc tính khác nhau .10 Đã chính xác phân låp Bayes sử dāng các thuÃt toán rút gán thuãc tính .1 Hệ thông tin về ch¿t l°ÿng đÁu vào cÿa sinh viên .2 Đã chắc chắn trung bình cÿa các thuãc tính .3 Tám bã dữ liệu chu¿n UCI .4 Bảng dự phòng .5 KÁt quả gom cām MMNVI trên tÃp dữ liệu Soybean Small.6 KÁt quả gom cām MMNVI trên tÃp dữ liệu Breast Cancer Wisconsin.7 KÁt quả gom cām MMNVI trên tÃp dữ liệu Car Evaluation.8 KÁt quả gom cām MMNVI trên tÃp dữ liệu Vote.9 KÁt quả gom cām MMNVI trên tÃp dữ liệu Chess.10 KÁt quả gom cām MMNVI trên tÃp dữ liệu Mushroom.11 KÁt quả gom cām MMNVI trên tÃp dữ liệu Balance Scale .12 KÁt quả gom cām MMNVI trên tÃp dữ liệu Zoo .13 Đã thuÁn khiÁt tßng thß cÿa 3 thuÃt toán trên 8 bã dữ liệu.14 Chỉ số ngÁu nhiên hiệu chỉnh (ARI) cÿa ba thuÃt toán trên 8 tÃp dữ liệu.15 Thông tin t°¢ng há chu¿n hóa (NMI) cÿa ba thuÃt toán trên 8 tÃp dữ liệu.

84 DANH MĀC HÌNH VẼ Hình 3.1 Hình minh háa thuÃt toán ACBRC .1 Hình minh háa so sánh đã thuÁn khiÁt tßng thß cÿa ba thuÃt toán trên tám tÃp dữ liệu thực nghiệm .2 Hình minh háa so sánh chỉ số ngÁu nhiên hiệu chỉnh trung bình cÿa ba thuÃt toán trên tám tÃp dữ liệu thực nghiệm .3 Hình minh háa so sánh thông tin t°¢ng há chu¿n hóa cÿa ba thuÃt toán đối våi các tÃp dữ liệu có sự phân bß låp cân bằng. 85 DANH MĀC THU¾T TOÁN ThuÃt toán 2.1 ThuÃt toán xác đßnh låp t°¢ng đ°¢ng .2 ThuÃt toán xác đßnh x¿p xỉ d°åi .3 ThuÃt toán xác đßnh x¿p xỉ trên .4 ThuÃt toán xác đßnh miền d°¢ng .1 ThuÃt toán QuickReduct .2 ThuÃt toán RelativeReduct .3 ThuÃt toán CEBARKNC .4 ThuÃt toán gom cām thuãc tính MNF .1 ThuÃt toán TR (Total Roughness) .2 ThuÃt toán MDA (Maximumdegree of Dependency of Attributes) .3 ThuÃt toán MMR (Min–Min–Mean-Roughness) .4 ThuÃt toán MGR (Mean Gain Ratio). Mà ĐÀU Ngày nay, cùng våi sự phát trißn cÿa khoa hác công nghệ, m¿ng máy tính và truyền thông đã có những b°åc phát trißn m¿nh m¿ và đ°ÿc āng dāng rãng rãi trong t¿t cả các l*nh vực đçi sống. Cùng våi đó, nhu cÁu và khả năng thu thÃp, l°u trữ dữ liệu cÿa con ng°çi không ngừng tăng lên theo c¿p số nhân.

Våi l°ÿng dữ liệu khßng lồ hiện nay, yêu cÁu đặt ra đối våi các công cā xử lý, phân tích thông tin ngày càng cao. Đặc biệt h¢n, con ng°çi luôn mong muốn thu nhÃn mãt cách tự đãng những tri thāc tiềm ¿n, mang tính dự đoán từ nguồn dữ liệu quý giá này. Trong những năm qua, khám phá tri thāc (khai phá dữ liệu), hác máy, trích xu¿t quy tắc từ dữ liệu v. đã thu hút nhiều sự chú ý cÿa các nhà khoa hác trong l*nh vực trí tuệ nhân t¿o.

Trên c¢ sơꄉ đó, nhiều ph°¢ng pháp khám phá tri thāc từ c¢ sơꄉ dữ liệu (CSDL) đã ra đçi. Khám phá tri thāc từ CSDL (Knowledge Discovery in Databases – KDD) là mãt l*nh vực khoa hác nhằm nghiên cāu đß t¿o ra những công cā khai phá những thông tin, tri thāc hữu ích, tiềm ¿n mang tính dự đoán trong các CSDL lån [1, 2].