Nghiên cứu phương pháp trích chọn đặc trưng dựa trên giải thuật phân lớp random forest

Luận văn thạc sĩ nghiên cứu nghiên cứu xây dựng phương pháp trích chọn đặc trưng dựa trên giải thuật phân lớp random forest, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Nguyễn Cương
• Người hướng dẫn: TS. Nguyễn Hà Nam
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phương Pháp Trích Chọn Đặc Trưng Hiệu Quả Với Giải Thuật Random Forest
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Phát hiện tri thức và khai phá dữ liệu
• 1.2. Chọn lựa thuộc tính (CLTT) và vai trò của CLTT trong KDD
• 1.3. Chọn lựa thuộc tính và bài toán phân lớp
• 2. CHƯƠNG 2: TRÍCH CHỌN THUỘC TÍNH
• 2.1. Chiến lược tìm kiếm
• 2.2. Các chiến lược tìm kiếm
• 2.3. Tiêu chuẩn chọn lựa
• 2.4. Đo lường thông tin
• 2.5. Đo lường khoảng cách
• 2.6. Đo lường phụ thuộc
• 2.7. Đo lường độ đồng nhất
• 2.8. Đo lường chính xác
• 2.9. Mô hình Filter và Wrapper
• 2.9.1. Mô hình Wrapper
• 2.9.2. Mô hình Filter
• 3. CHƯƠNG 3: MỘT SỐ GIẢI THUẬT TRÍCH CHỌN THUỘC TÍNH
• 3.1. Tìm kiếm toàn bộ
• 3.2. Phương pháp Focus
• 3.3. Phương pháp ABB
• 3.4. Tìm kiếm theo kinh nghiệm
• 3.5. Phương pháp LVF
• 3.6. Phương pháp LVW
• 3.7. Phương pháp trọng số thuộc tính
• 3.8. Phương pháp lai
• 3.9. Phương pháp lớn dần
• 4. CHƯƠNG 4: GIẢI THUẬT RANDOM FOREST
• 4.1. Bootstrap và Bagging
• 4.2. Một số điểm cần chú ý của giải thuật Random Forest
• 4.3. Thuộc tính quan trọng
• 5. CHƯƠNG 5: PHƯƠNG PHÁP HỌC MÁY ĐỀ XUẤT
• 5.1. Một số kỹ thuật sử dụng trong phương pháp đề xuất
• 5.2. Kiểm chứng chéo (cross-validation)
• 5.3. Phân lớp Native Bayes
• 5.4. Sơ đồ khối và mô hình phương pháp học máy đề xuất
• 5.5. Mô tả phương pháp học máy đề xuất
• 6. CHƯƠNG 6: KẾT QUẢ THỰC NGHIỆM
• 6.1. Dữ liệu Madelon
• 6.2. Mô tả bộ dữ liệu Madelon
• 6.3. Kết quả thực nghiệm với bộ dữ liệu Madelon
• 6.4. Bộ dữ liệu Colon Turmo
• 6.5. Mô tả bộ dữ liệu Colon Turmo
• 6.6. Kết quả thực nghiệm với bộ dữ liệu Colon Turmo
• DANH MỤC TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về phương pháp trích chọn đặc trưng

Phương pháp trích chọn đặc trưng là một bước quan trọng trong quy trình khai phá dữ liệu, giúp giảm chiều dữ liệu và nâng cao hiệu suất của các mô hình học máy. Việc trích chọn đặc trưng không chỉ giúp loại bỏ các thuộc tính không cần thiết mà còn cải thiện độ chính xác của các mô hình phân lớp. Trong bối cảnh hiện nay, với sự phát triển mạnh mẽ của công nghệ thông tin, việc xử lý và phân tích dữ liệu lớn trở thành một thách thức lớn. Do đó, việc áp dụng các giải thuật như giải thuật random forest để thực hiện trích chọn đặc trưng là rất cần thiết. Giải thuật này không chỉ giúp xác định các thuộc tính quan trọng mà còn hỗ trợ trong việc phân loại dữ liệu một cách hiệu quả.

1.1. Vai trò của trích chọn đặc trưng trong khai phá dữ liệu

Trích chọn đặc trưng đóng vai trò quan trọng trong việc cải thiện hiệu suất của các mô hình học máy. Việc giảm số lượng thuộc tính không chỉ giúp giảm thiểu chi phí tính toán mà còn làm tăng độ chính xác của các mô hình. Các kỹ thuật như học máy và học sâu thường gặp khó khăn khi phải xử lý dữ liệu lớn với nhiều thuộc tính không liên quan. Do đó, việc áp dụng các phương pháp trích chọn đặc trưng giúp tối ưu hóa quy trình phân tích dữ liệu, từ đó nâng cao khả năng dự đoán của các mô hình. Các nghiên cứu đã chỉ ra rằng việc sử dụng giải thuật random forest trong trích chọn đặc trưng có thể mang lại kết quả tốt hơn so với các phương pháp truyền thống.

II. Giải thuật random forest và ứng dụng trong trích chọn đặc trưng

Giải thuật random forest là một trong những phương pháp học máy mạnh mẽ, được sử dụng rộng rãi trong việc phân loại và hồi quy. Giải thuật này hoạt động dựa trên nguyên tắc xây dựng nhiều cây quyết định và kết hợp kết quả của chúng để đưa ra dự đoán chính xác hơn. Trong bối cảnh trích chọn đặc trưng, random forest có khả năng đánh giá tầm quan trọng của từng thuộc tính trong tập dữ liệu. Điều này giúp xác định các thuộc tính có ảnh hưởng lớn đến kết quả phân lớp, từ đó loại bỏ các thuộc tính không cần thiết. Việc sử dụng random forest trong trích chọn đặc trưng không chỉ giúp cải thiện độ chính xác mà còn giảm thiểu thời gian tính toán.

2.1. Cách thức hoạt động của random forest trong trích chọn đặc trưng

Giải thuật random forest sử dụng phương pháp bootstrap để tạo ra nhiều mẫu dữ liệu khác nhau từ tập dữ liệu gốc. Mỗi mẫu này sẽ được sử dụng để xây dựng một cây quyết định riêng biệt. Sau khi tất cả các cây được xây dựng, kết quả của chúng sẽ được kết hợp lại để đưa ra dự đoán cuối cùng. Trong quá trình này, mỗi thuộc tính sẽ được đánh giá dựa trên tần suất mà nó được sử dụng để phân loại đúng các mẫu. Các thuộc tính có tầm quan trọng cao sẽ được giữ lại, trong khi các thuộc tính không quan trọng sẽ bị loại bỏ. Điều này không chỉ giúp tối ưu hóa mô hình mà còn làm cho mô hình dễ hiểu hơn.

III. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm cho thấy việc áp dụng giải thuật random forest trong trích chọn đặc trưng mang lại nhiều lợi ích. Các thử nghiệm trên các bộ dữ liệu như Madelon và Colon Tumor cho thấy độ chính xác của mô hình được cải thiện đáng kể khi chỉ sử dụng các thuộc tính quan trọng. Việc giảm số lượng thuộc tính không chỉ giúp tăng tốc độ tính toán mà còn làm cho mô hình dễ dàng hơn trong việc giải thích. Các kết quả này khẳng định giá trị thực tiễn của phương pháp trích chọn đặc trưng dựa trên random forest trong các ứng dụng thực tế, từ phân tích dữ liệu đến dự đoán trong các lĩnh vực khác nhau.

3.1. Đánh giá hiệu quả của phương pháp

Các kết quả thực nghiệm cho thấy rằng việc sử dụng random forest trong trích chọn đặc trưng không chỉ cải thiện độ chính xác mà còn giảm thiểu thời gian xử lý. Các mô hình được xây dựng từ các thuộc tính đã được chọn lọc cho thấy khả năng dự đoán tốt hơn so với các mô hình sử dụng toàn bộ thuộc tính. Điều này chứng tỏ rằng trích chọn đặc trưng là một bước quan trọng trong quy trình khai phá dữ liệu, giúp tối ưu hóa hiệu suất của các mô hình học máy. Hơn nữa, việc áp dụng phương pháp này trong các lĩnh vực như y tế, tài chính và marketing có thể mang lại những giá trị thực tiễn to lớn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ thông tin và truyền thông, lượng dữ liệu được thu thập ngày càng tăng lên nhanh chóng, dẫn đến nhu cầu khai phá tri thức từ dữ liệu lớn trở thành một thách thức quan trọng. Việc trích chọn đặc trưng (feature selection) đóng vai trò then chốt trong khai phá dữ liệu, giúp giảm chiều dữ liệu, loại bỏ thuộc tính không liên quan, từ đó nâng cao hiệu quả và độ chính xác của các mô hình phân lớp. Nghiên cứu này tập trung xây dựng phương pháp trích chọn đặc trưng dựa trên giải thuật phân lớp Random Forest (RF), một trong những giải thuật học máy mạnh mẽ và phổ biến nhất hiện nay.

Mục tiêu chính của luận văn là phát triển một phương pháp học máy kết hợp giữa độ quan trọng thuộc tính được đánh giá bởi chỉ số GINI trong RF và kỹ thuật kiểm chứng chéo (cross-validation) nhằm tối ưu hóa tập thuộc tính đầu vào, từ đó cải thiện hiệu suất phân lớp. Nghiên cứu được thực hiện trên các bộ dữ liệu thực nghiệm như Madelon và Colon Tumor, với số lượng thuộc tính và mẫu đa dạng, giúp đánh giá tính khả thi và hiệu quả của phương pháp đề xuất.

Phạm vi nghiên cứu tập trung vào lĩnh vực Công nghệ Thông tin, chuyên ngành Hệ thống Thông tin, với dữ liệu thu thập và phân tích trong khoảng thời gian gần đây. Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao độ chính xác phân lớp, giảm chi phí tính toán và tăng khả năng giải thích mô hình, góp phần thúc đẩy ứng dụng khai phá dữ liệu trong các lĩnh vực như y tế, tài chính và thương mại điện tử.

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 dựa trên các lý thuyết và mô hình sau:

• Phát hiện tri thức và khai phá dữ liệu (KDD): Quá trình trích xuất tri thức có ích từ dữ liệu lớn, trong đó trích chọn thuộc tính là bước quan trọng nhằm giảm chiều dữ liệu và nâng cao hiệu quả phân lớp.
• Chọn lựa thuộc tính (Feature Selection): Quá trình chọn ra tập con thuộc tính tối ưu từ tập thuộc tính ban đầu, giúp giảm nhiễu và tăng độ chính xác mô hình. Các phương pháp chọn lựa thuộc tính được phân thành mô hình Filter (dựa trên các tiêu chí thống kê) và Wrapper (dựa trên hiệu quả của bộ phân lớp).
• Giải thuật Random Forest (RF): Một tập hợp các cây phân lớp được xây dựng trên các mẫu bootstrap khác nhau, sử dụng kỹ thuật bagging và lựa chọn ngẫu nhiên thuộc tính tại mỗi nút phân chia. RF giảm thiểu phương sai và mối tương quan giữa các cây, đồng thời cung cấp chỉ số đánh giá độ quan trọng của từng thuộc tính dựa trên chỉ số GINI và phương pháp hoán vị.
• Kiểm chứng chéo (Cross-validation): Phương pháp đánh giá mô hình bằng cách chia dữ liệu thành N tập con, luân phiên sử dụng tập con làm tập kiểm tra và các tập còn lại làm tập huấn luyện, giúp giảm thiểu hiện tượng overfitting và lựa chọn tham số mô hình tối ưu.
• Lý thuyết Bayes: Cơ sở xác suất để tính toán hậu xác suất của một giả thiết dựa trên dữ liệu quan sát, hỗ trợ trong việc xây dựng các mô hình phân lớp như Naive Bayes.

Các khái niệm chính bao gồm: trích chọn thuộc tính, mô hình Filter và Wrapper, kỹ thuật bootstrap và bagging, chỉ số GINI, kiểm chứng chéo, và phân lớp Random Forest.

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

Nghiên cứu sử dụng dữ liệu thực nghiệm từ hai bộ dữ liệu chuẩn là Madelon và Colon Tumor, với kích thước và số lượng thuộc tính đa dạng, phù hợp để đánh giá hiệu quả của phương pháp trích chọn đặc trưng.

Phương pháp phân tích chính bao gồm:

• Xây dựng mô hình Random Forest: Sử dụng kỹ thuật bootstrap để tạo ra các mẫu huấn luyện, phát triển các cây phân lớp không tỉa, tại mỗi nút chọn ngẫu nhiên m thuộc tính để phân chia.
• Đánh giá độ quan trọng thuộc tính: Tính toán chỉ số GINI và sử dụng dữ liệu out-of-bag (OOB) để ước lượng sai số và độ quan trọng của từng thuộc tính thông qua hoán vị giá trị thuộc tính.
• Phương pháp học máy đề xuất: Kết hợp độ quan trọng thuộc tính với kỹ thuật kiểm chứng chéo n-fold để lựa chọn tập con thuộc tính tối ưu, nhằm cải thiện độ chính xác phân lớp.
• Kiểm chứng chéo: Áp dụng n-fold cross-validation để đánh giá hiệu quả mô hình trên các tập dữ liệu huấn luyện và kiểm tra, đảm bảo tính tổng quát và tránh overfitting.
• So sánh kết quả: Thực hiện so sánh hiệu quả phân lớp giữa phương pháp Random Forest truyền thống và phương pháp đề xuất trên các bộ dữ liệu thực nghiệm.

Quá trình nghiên cứu được thực hiện theo timeline gồm: thu thập và tiền xử lý dữ liệu, xây dựng và huấn luyện mô hình, đánh giá và so sánh kết quả, tổng hợp và phân tích dữ liệu.

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

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

1. Hiệu quả trích chọn đặc trưng dựa trên Random Forest: Phương pháp đề xuất đã giảm số lượng thuộc tính cần thiết từ hàng trăm xuống còn khoảng 10-20% số thuộc tính ban đầu, đồng thời duy trì hoặc cải thiện độ chính xác phân lớp. Ví dụ, trên bộ dữ liệu Madelon, độ chính xác phân lớp tăng từ khoảng 75% lên 82% sau khi áp dụng phương pháp trích chọn đặc trưng.

2. Tăng độ chính xác phân lớp: So với Random Forest truyền thống, phương pháp đề xuất cải thiện độ chính xác phân lớp trung bình từ 3-7% trên các bộ dữ liệu Madelon và Colon Tumor, với độ lệch chuẩn nhỏ, thể hiện tính ổn định của mô hình.

3. Giảm thời gian tính toán: Mặc dù phương pháp đề xuất có thêm bước kiểm chứng chéo, tổng thời gian huấn luyện giảm khoảng 20-30% do giảm số lượng thuộc tính đầu vào, giúp tiết kiệm tài nguyên tính toán.

4. Độ quan trọng thuộc tính phản ánh chính xác: Chỉ số GINI và phương pháp hoán vị cho thấy sự nhất quán trong việc xác định các thuộc tính quan trọng, giúp loại bỏ các thuộc tính không liên quan hoặc nhiễu hiệu quả.

Thảo luận kết quả

Nguyên nhân của các phát hiện trên xuất phát từ việc kết hợp hiệu quả giữa đánh giá độ quan trọng thuộc tính dựa trên chỉ số GINI trong Random Forest và kỹ thuật kiểm chứng chéo nhằm lựa chọn tập thuộc tính tối ưu. Việc giảm chiều dữ liệu giúp mô hình tránh hiện tượng overfitting, tăng khả năng tổng quát hóa và cải thiện độ chính xác phân lớp.

So sánh với các nghiên cứu trước đây, phương pháp đề xuất vượt trội hơn về khả năng cân bằng giữa độ chính xác và chi phí tính toán. Các biểu đồ so sánh độ chính xác và thời gian huấn luyện minh họa rõ ràng sự cải thiện này, đồng thời bảng số liệu chi tiết thể hiện sự ổn định qua nhiều lần chạy thử.

Ý nghĩa của kết quả là phương pháp có thể áp dụng rộng rãi trong các bài toán phân lớp phức tạp với dữ liệu đa chiều lớn, đặc biệt trong các lĩnh vực y tế, tài chính và phân tích hành vi khách hàng.

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

1. Áp dụng phương pháp trích chọn đặc trưng dựa trên Random Forest trong các hệ thống phân lớp: Động từ hành động là "triển khai", mục tiêu là tăng độ chính xác phân lớp lên ít nhất 5%, thời gian thực hiện trong vòng 6 tháng, chủ thể thực hiện là các nhóm nghiên cứu và phát triển trong lĩnh vực khai phá dữ liệu.

2. Tích hợp kỹ thuật kiểm chứng chéo n-fold trong quá trình huấn luyện mô hình: Động từ "ứng dụng", nhằm giảm thiểu hiện tượng overfitting và tăng tính tổng quát của mô hình, thời gian thực hiện 3 tháng, chủ thể là các nhà phát triển phần mềm và nhà khoa học dữ liệu.

3. Phát triển công cụ tự động đánh giá độ quan trọng thuộc tính dựa trên chỉ số GINI: Động từ "phát triển", mục tiêu hỗ trợ người dùng lựa chọn thuộc tính hiệu quả, thời gian 9 tháng, chủ thể là các nhóm nghiên cứu công nghệ thông tin.

4. Khuyến nghị sử dụng phương pháp trên các bộ dữ liệu đa chiều lớn trong y tế và tài chính: Động từ "khuyến nghị", nhằm nâng cao hiệu quả phân lớp và giảm chi phí tính toán, thời gian áp dụng liên tục, chủ thể là các tổ chức nghiên cứu và doanh nghiệp.

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

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Thông tin, đặc biệt chuyên ngành Hệ thống Thông tin: Giúp hiểu sâu về các phương pháp trích chọn đặc trưng và ứng dụng Random Forest trong khai phá dữ liệu.

2. Chuyên gia phân tích dữ liệu và khoa học dữ liệu: Cung cấp công cụ và phương pháp nâng cao hiệu quả phân lớp, giảm chiều dữ liệu và cải thiện độ chính xác mô hình.

3. Doanh nghiệp và tổ chức ứng dụng khai phá dữ liệu: Hỗ trợ trong việc xây dựng các hệ thống phân lớp chính xác, tiết kiệm chi phí tính toán và nâng cao hiệu quả kinh doanh.

4. Nhà phát triển phần mềm và kỹ sư học máy: Tham khảo để phát triển các thuật toán và công cụ hỗ trợ trích chọn đặc trưng, tích hợp kỹ thuật kiểm chứng chéo và đánh giá độ quan trọng thuộc tính.

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

1. Phương pháp trích chọn đặc trưng dựa trên Random Forest có ưu điểm gì so với các phương pháp khác?
   Phương pháp này tận dụng khả năng đánh giá độ quan trọng thuộc tính của Random Forest kết hợp với kiểm chứng chéo giúp chọn tập thuộc tính tối ưu, giảm chiều dữ liệu, tăng độ chính xác và giảm thời gian tính toán so với các phương pháp truyền thống.

2. Kiểm chứng chéo n-fold giúp gì trong việc xây dựng mô hình?
   Kiểm chứng chéo n-fold giúp đánh giá mô hình một cách khách quan, giảm thiểu hiện tượng overfitting bằng cách sử dụng toàn bộ dữ liệu cho cả huấn luyện và kiểm tra, từ đó chọn tham số mô hình tối ưu.

3. Chỉ số GINI được sử dụng như thế nào để đánh giá độ quan trọng thuộc tính?
   Chỉ số GINI đo độ đồng nhất của các nút trong cây phân lớp; thuộc tính làm giảm chỉ số GINI nhiều nhất được xem là quan trọng, giúp loại bỏ các thuộc tính không liên quan hoặc nhiễu.

4. Phương pháp đề xuất có thể áp dụng cho những loại dữ liệu nào?
   Phương pháp phù hợp với dữ liệu đa chiều lớn, có thể là dữ liệu rời rạc hoặc liên tục, đặc biệt hữu ích trong các bài toán phân lớp phức tạp như y tế, tài chính, và phân tích hành vi khách hàng.

5. Làm thế nào để xác định số lượng cây trong Random Forest phù hợp?
   Số lượng cây được chọn dựa trên việc cân bằng giữa độ chính xác và chi phí tính toán; thường thử nghiệm với các giá trị khác nhau và sử dụng kiểm chứng chéo để chọn số cây tối ưu, ví dụ từ 100 đến 1700 cây tùy bộ dữ liệu.

Kết luận

• Phương pháp trích chọn đặc trưng dựa trên giải thuật Random Forest kết hợp kiểm chứng chéo n-fold và chỉ số GINI đã nâng cao đáng kể hiệu quả phân lớp trên các bộ dữ liệu thực nghiệm.
• Giảm chiều dữ liệu giúp tiết kiệm thời gian tính toán và tăng độ chính xác mô hình, đồng thời cải thiện khả năng giải thích kết quả phân lớp.
• Kết quả thực nghiệm trên bộ dữ liệu Madelon và Colon Tumor cho thấy sự ổn định và tính khả thi của phương pháp đề xuất.
• Phương pháp có thể ứng dụng rộng rãi trong các lĩnh vực khai phá dữ liệu đa chiều lớn như y tế, tài chính và thương mại điện tử.
• Các bước tiếp theo bao gồm phát triển công cụ tự động hóa trích chọn đặc trưng và mở rộng thử nghiệm trên các bộ dữ liệu thực tế khác; mời các nhà nghiên cứu và chuyên gia ứng dụng tham gia hợp tác phát triển.

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

Chương 1: Tổng quan Trang 16 z Chương 2: Trích chọn thuộc tính Trích chọn thuộc tính được xem như là sự tổng hợp của ba thành phần chính: (1)Tìm kiếm, Đánh ra, Chọn lựa mô hình.1 dưới đây [3] thể hiện trích chọn thuộc tính theo 3 thành phần nói trên. 1: Ba thành phần chính của chọn lựa thuộc tính: Chiến lược tìm kiếm, Đánh giá, Chọn lựa mô hình 2. Chiến lược tìm kiếm Chọn lựa thuộc tính có thể được xem dưới góc độ như là một vấn đề tìm kiếm, trong đó mỗi bước trong không gian tìm kiếm xác định ra một tập con thuộc tính liên quan. Giả sử ta có một tập dữ liệu với 3 thuộc tính (A1, A2, A3).

Một mảng nhị phân mà mỗi thành phần của mảng được thiết lập là 1 nếu thuộc tính có chỉ số tương ứng trong mảng nhị phân được chọn. Nếu mảng có giá trị (1, 1, 1) có nghĩa là cả 3 thuộc tính được chọn và (1, 0, 0) có nghĩa là chỉ thuộc tính A1 được chọn. Do đó, sẽ có tất cả 2N tập con có thể có, trong đó N là số lượng thuộc tính của tập dữ liệu. Trong trường hợp có 3 thuộc tính sẽ có tất cả 8 trạng thái (tập con).

Một tập con tối ưu thường nằm đâu đó giữa điểm đầu và điểm cuối cây. Câu hỏi đặt ra ở đây là: Chúng ta nên bắt đầu tìm kiếm từ đâu. Vấn đề sẽ rất đơn giản nếu không gian tìm kiếm nhỏ. Tuy nhiên, trên thực tế không gian tìm kiếm thường rất lớn (2N), bắt đầu từ câu hỏi “Đâu là điểm tìm Chương 2: Trích chọn thuộc tính Trang 17 z kiếm phù hợp” sẽ xuất hiện các câu hỏi khác: Chiến lược tìm kiếm phù hợp là gì ?.

Trên thực tế chiến lược tìm kiếm lại bị ảnh hưởng bởi hướng tìm kiếm, dưới đây chúng ta sẽ lần lượt xem xét hướng tìm kiếm và chiến lược tìm kiếm. Hướng tìm kiếm Giả sử chúng ta ban đầu chưa có một khái niệm cụ thể nào về tập thuộc tính tối ưu trong không gian tìm kiếm, thì sẽ không có sự khác biệt trong việc xác định điểm xuất phát nên bắt đầu từ đâu (một tập rỗng hay một tập đủ các thuộc tính). Do đó, đối với phần lớn các vấn đề trong tìm kiếm thì trung bình thời gian để tìm ra tập con tối ưu giữa các hướng tìm kiếm khác nhau không có sự khác biệt. Tuy nhiên, hướng tìm kiếm lại có mối liên hệ chặt chẽ trong việc tạo ra tập con thuộc tính.

Một phương pháp tìm kiếm là tìm ra tập con tối ưu bắt đầu từ một tập rỗng các thuộc tính (Ví dụ: Sequential Forward Generation), phương pháp còn lại là tìm ra tập con tối ưu bằng cách lần lượt loại bỏ các thuộc tính ít quan trọng từ một tập đủ các thuộc tính ban đầu (Ví dụ: Sequential Backward Generation). Sequential forward generation (SFG): Được bắt đầu bằng một tập rỗng các thuộc tính, Sselect. Ở mỗi lần tìm kiếm một thuộc tính được thêm vào tập Sselect (do đó gọi là tuần tự). Trong mỗi lần tìm kiếm dựa trên một số tiêu chí, một thuộc tính tốt nhất trong số các thuộc tính chưa được chọn lựa sẽ được chọn để thêm vào tập Sselect.

Quá trình tìm kiếm này sẽ dừng lại khi tất cả các thuộc tính trong tập thuộc tính ban đầu được thêm vào Sselect. Một danh sách xếp hạng các thuộc tính được tạo ra theo trình tự thời gian các thuộc tính được thêm vào tập Sselect. Nếu ta biết trước một số thông tin về số lượng thuộc tính liên quan, thì một cách đơn giản chúng ta có thể chọn m thuộc tính đầu tiên trong danh sách xếp hạng. Sequential backward generation (SBG): Được bắt đầu với một tập đủ các thuộc tính, tại mỗi lần tìm kiếm dựa vào một số tiêu chí nào đó, một thuộc tính ít quan trọng sẽ bị loại bỏ.

Do đó, các thuộc tính trong tập thuộc tính sẽ dần dần bị loại bỏ cho tới khi trong tập thuộc tính chỉ còn lại một thuộc tính. Một danh sách xếp hạng các thuộc tính theo thời gian bị loại bỏ từ thấp đến cao được tạo ra. Thuộc tính bị loại bỏ cuối cùng sẽ là thuộc tính quan trọng nhất. SBG và SFG là hai phương pháp bổ xung cho nhau vì đôi khi tìm ra thuộc tính quan trọng nhất là dễ dàng hơn so với tìm ra thuộc tính ít quan trọng và ngược lại.

Nếu trong trường hợp tồn tại một tập thuộc tính tối ưu mà tập thuộc tính này lại không nằm trong khu vực giữa của không gian tìm kiếm, thì việc chúng ta bắt đầu tìm kiếm từ cả hai phía của không gian tìm kiếm là giải pháp tối ưu. Một cách trực quan, Chương 2: Trích chọn thuộc tính Trang 18 z chúng ta thấy rằng phương pháp này sẽ chạy nhanh hơn phương pháp tìm kiếm theo một hướng. Dưới đây, ta sẽ sem xét phương pháp này. Birectional Generation(BG): Được bắt đầu ở cả hai hướng trong không gian tìm kiếm, ví dụ hai quá trình tìm kiếm được thực hiện đồng thời.

Quá trình tìm kiếm sẽ dừng lại khi gặp một trong hai trường hợp sau: (1) Khi một trong hai chiều tìm kiếm tìm được tập m thuộc tính tốt nhất trước khi đi đến điểm giữa trong không gian tìm kiếm, hoặc (2) Cả hai chiều tìm kiếm đến điểm giữa trong không gian tìm kiếm. Nếu giả sử giả thuyết là chúng ta hoàn toàn chưa có thông tin về m thuộc tính tốt nhất là đúng thì trong mọi trường hợp, tìm kiếm theo một chiều sẽ mất một nửa thời gian để đi đến điểm giữa của không gian tìm kiếm. Phương pháp BG sẽ tránh được nhược điểm trên. Random Generation(RG): Bắt đầu tìm kiếm theo một hướng ngẫu nhiên.

Thêm hay loại bỏ bớt một thuộc tính cũng được thực hiện một cách ngẫu nhiên. RG cố gắng tránh việc gặp tối ưu địa phương do việc cố định chỉ đi theo một chiều nào đó trong việc tạo ra tập thuộc tính tối ưu. Không giống như FSG hay FBG, kích cỡ của tập con thuộc tính được tạo ra tiếp theo không được xác định. Tuy nhiên, chúng ta có thể thấy được xu hướng của số lượng thuộc tính được chọn là tăng lên hay giảm đi.

Các chiến lược tìm kiếm Trong trường hợp số lượng thuộc tính (N) là nhỏ thì không gian tìm kiếm là không lớn. Tuy nhiên không gian tìm kiếm sẽ tăng theo hàm mũ khi N tăng do mối quan hệ S=2N, trong đó S là không gian tìm kiếm với N thuộc tính và 2 biểu thị việc chọn hay không chọn một thuộc tính. Câu hỏi về chiến lược tìm kiếm nào được chọn đặt ra trong trường hợp không gian tìm kiếm là lớn. Cũng cần lưu ý rằng trong một không gian tìm kiếm nếu tìm kiếm càng nhiều (càng kỹ) có nghĩa là sẽ tìm được một tập con tốt hơn.

Tuy nhiên, tìm kiếm nhiều có nghĩa là sẽ mất nhiều thời gian và nguồn lực mà chúng ta lại thường luôn hạn chế về nguồn lực. Do vậy, mục đích là tìm được một tập con tối ưu nhất có thể trong thời gian ít nhất có thể. Các chiến lược tìm kiếm có thể được chia thành 3 nhóm dưới đây. Tìm kiếm toàn bộ (Exhausive/Complete Search): Đây là phương pháp tìm tất cả các khả năng có thể của các tập con sau đó tìm một tập con tối ưu nhất.

Nhìn chung, độ phức tạp không gian của phương pháp này (số lượng tập con cần tạo ra) là O(2N). Nếu chúng ta biết được hướng tìm kiếm, thì không gian tìm kiếm là (N0) + (N1) + …+ (NM), trong đó M là số lượng thuộc tính tối thiểu của một tập con thỏa mãn một số tiêu chí đánh giá nào đó. Chương 2: Trích chọn thuộc tính Trang 19 z Tìm kiếm theo kinh nghiệm (Heuristic Search): Như tên gọi của phương pháp, phương pháp tìm kiếm theo kinh nghiệm được triển khai trong khi tìm kiếm, điều này tránh được việc tìm kiếm một cách khô cứng, máy móc (brute-force search) nhưng phương pháp này cũng đi cùng với nguy cơ không tìm được các tập con tối ưu. Độ phức tạp không gian của phương pháp tìm kiếm theo kinh nhiệm là đường đi nối từ điểm bắt đầu đến điểm kết thúc (điểm tìm ra tập con tối ưu).

Độ dài tối đa của đường đi này là N và số lượng tập con được tạo ra là O(N). Phương pháp tìm kiếm theo kinh nghiệm cho ra kết quả nhanh hơn so với phương pháp tìm kiếm toàn bộ, do phương pháp này chỉ tìm kiếm theo một đường đi cụ thể và tìm ra một tập con gần tối ưu. Tìm kiếm không xác đinh(Nondeterministic Search): Không giống như hai chiến lược tìm kiếm được trình bày ở trên, chiến lược này tìm kiếm tập con kế tiếp theo kiểu ngẫu nhiên. Có hai đặc điểm chính của chiến lược tìm kiếm này: (1) Chúng ta không cần phải đợi cho đến khi tìm kiếm kết thúc; và (2) Chúng ta không biết khi nào tập tối ưu được xuất hiện mặc dù chúng ta biết rằng tại mỗi bước có một tập tốt hơn xuất hiện.2 dưới đây thể hiện mối quan hệ giữa hướng tìm kiếm và chiến lược tìm kiếm.

X thể hiện sự kết hợp giữa chiến lược tìm kiếm và hướng tìm kiếm là không khả thi. Chiến lược tìm kiếm Hướng tìm kiếm Toàn bộ Kinh nghiệm Không xác định SFG √ √ × SBG √ √ × BG √ √ × RG × √ √ Bảng 2. 1 : Chiến lược tìm kiếm và hướng tìm kiếm 2. Tiêu chuẩn chọn lựa Tất cả các chiến lược tìm kiếm đều có nhu cầu đánh giá một thuộc tính hoặc một tập con thuộc tính để xác định thuộc tính/tập con đó là tốt hay không tốt.

Việc đánh giá này thường là phức tạp và có nhiều chiều đánh giá. Ví dụ, đánh giá có thể được đo lường theo những khía cạnh (1) Các thuộc tính được chọn lựa có làm tăng độ chính Chương 2: Trích chọn thuộc tính Trang 20 z xác của bộ phân lớp hay không và (2) Các thuộc tính được chọn lựa có giúp làm đơn giản các kết quả học do đó sẽ các kết quả này có thể dễ dàng để hiểu hay không… Dưới đây là một số đo lường thường được sử dụng trong trích chọn thuộc tính. Đo lường thông tin Thông tin là một cách đo lường độ không ổn định của người nhận tin khi một người nhận tất cả các tin nhắn. Nếu người nhận tin biết được tin nhắn nào đang đến thì sự ngạc nhiên (uncertainty) của anh ta sẽ thấp.

Trong trường hợp anh ta hoàn toàn không biết tin nhắn nào đang đến, chúng ta giả sử rằng tất có các tin nhắn có xác suất đến bằng nhau, thì sự ngạc nhiên của anh ta đối với tin nhắn đó là cao. Trong ngữ cảnh của phân lớp, các tin nhắn là các lớp.