Nghiên Cứu Phương Pháp Trích Chọn Đặc Trưng Bằng Giải Thuật Random Forest

Luận văn thạc sĩ kỹ thuật phân tích vnu uet 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, đánh giá thực trạng, chỉ ra hạn chế, đề xuất

• Tác giả: Nguyễn Cương
• Người hướng dẫn: TS. Nguyễn Hà Nam
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: 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
• 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 Dựa Trên Giải Thuật Random Forest

Phương pháp trích chọn đặc trưng dựa trên giải thuật Random Forest đã trở thành một công cụ quan trọng trong lĩnh vực học máy. Giải thuật này không chỉ giúp cải thiện độ chính xác của mô hình mà còn giảm thiểu chi phí tính toán. Random Forest hoạt động dựa trên nguyên lý kết hợp nhiều cây quyết định để đưa ra dự đoán chính xác hơn. Việc trích chọn đặc trưng là một bước quan trọng trong quy trình khai thác dữ liệu, giúp loại bỏ các thuộc tính không cần thiết và tập trung vào những yếu tố quan trọng nhất.

1.1. Khái niệm về Random Forest và ứng dụng trong học máy

Random Forest là một giải thuật học máy mạnh mẽ, được sử dụng rộng rãi trong phân loại và hồi quy. Giải thuật này hoạt động bằng cách 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 cuối cùng. Ứng dụng của Random Forest rất đa dạng, từ phân loại hình ảnh đến dự đoán rủi ro tín dụng.

1.2. Tại sao cần trích chọn đặc trưng trong học máy

Trích chọn đặc trưng giúp giảm thiểu độ phức tạp của mô hình, cải thiện tốc độ tính toán và tăng cường độ chính xác. Việc loại bỏ các thuộc tính không cần thiết giúp mô hình dễ dàng hơn trong việc học và giảm thiểu hiện tượng overfitting.

II. Vấn đề và Thách thức trong Trích Chọn Đặc Trưng

Mặc dù phương pháp trích chọn đặc trưng dựa trên Random Forest mang lại nhiều lợi ích, nhưng vẫn tồn tại một số thách thức. Một trong những vấn đề chính là việc xác định thuộc tính nào là quan trọng nhất. Ngoài ra, việc xử lý dữ liệu không đồng nhất và thiếu dữ liệu cũng là những thách thức lớn trong quá trình này.

2.1. Các vấn đề thường gặp trong trích chọn đặc trưng

Các vấn đề như dữ liệu không đồng nhất, thiếu dữ liệu và sự phụ thuộc giữa các thuộc tính có thể ảnh hưởng đến hiệu quả của quá trình trích chọn. Việc xác định thuộc tính quan trọng cũng có thể gặp khó khăn do sự tương tác phức tạp giữa các thuộc tính.

2.2. Giải pháp cho các thách thức trong trích chọn đặc trưng

Sử dụng các kỹ thuật như kiểm chứng chéo (cross-validation) và các phương pháp thống kê có thể giúp cải thiện độ chính xác trong việc xác định thuộc tính quan trọng. Ngoài ra, việc áp dụng các mô hình học sâu cũng có thể giúp giải quyết một số vấn đề liên quan đến dữ liệu không đồng nhất.

III. Phương Pháp Trích Chọn Đặc Trưng Dựa Trên Random Forest

Phương pháp trích chọn đặc trưng dựa trên Random Forest sử dụng các chỉ số như độ quan trọng của thuộc tính để xác định các thuộc tính cần thiết cho mô hình. Các thuộc tính có độ quan trọng cao sẽ được giữ lại, trong khi các thuộc tính có độ quan trọng thấp sẽ bị loại bỏ. Điều này giúp tối ưu hóa mô hình và cải thiện hiệu suất.

3.1. Cách thức hoạt động của Random Forest trong trích chọn đặc trưng

Random Forest sử dụng một tập hợp các cây quyết định để đánh giá độ quan trọng của từng thuộc tính. Mỗi cây sẽ đưa ra một dự đoán và kết quả cuối cùng sẽ là sự kết hợp của tất cả các dự đoán này. Độ quan trọng của thuộc tính được tính toán dựa trên sự giảm thiểu độ chính xác khi thuộc tính đó bị loại bỏ.

3.2. Các kỹ thuật tối ưu hóa mô hình với Random Forest

Các kỹ thuật như điều chỉnh tham số (hyperparameter tuning) và sử dụng các phương pháp ensemble có thể giúp cải thiện hiệu suất của mô hình Random Forest. Việc tối ưu hóa số lượng cây và độ sâu của cây cũng là những yếu tố quan trọng trong việc nâng cao độ chính xác.

IV. Ứng Dụng Thực Tiễn của Phương Pháp Trích Chọn Đặc Trưng

Phương pháp trích chọn đặc trưng dựa trên Random Forest đã được áp dụng thành công trong nhiều lĩnh vực khác nhau, từ y tế đến tài chính. Trong y tế, nó được sử dụng để phân loại bệnh nhân dựa trên các đặc điểm sinh học. Trong tài chính, nó giúp dự đoán rủi ro tín dụng và phát hiện gian lận.

4.1. Ứng dụng trong lĩnh vực y tế

Trong lĩnh vực y tế, Random Forest được sử dụng để phân tích dữ liệu bệnh nhân và dự đoán các bệnh lý tiềm ẩn. Việc trích chọn đặc trưng giúp xác định các yếu tố nguy cơ chính, từ đó hỗ trợ bác sĩ trong việc đưa ra quyết định điều trị.

4.2. Ứng dụng trong lĩnh vực tài chính

Trong lĩnh vực tài chính, phương pháp này giúp phân tích hành vi khách hàng và dự đoán rủi ro tín dụng. Việc trích chọn đặc trưng giúp cải thiện độ chính xác của các mô hình dự đoán, từ đó giảm thiểu rủi ro cho các tổ chức tài chính.

V. Kết Luận và Tương Lai của Phương Pháp Trích Chọn Đặc Trưng

Phương pháp trích chọn đặc trưng dựa trên Random Forest đã chứng minh được hiệu quả trong nhiều ứng dụng thực tiễn. Tương lai của phương pháp này hứa hẹn sẽ còn phát triển hơn nữa với sự tiến bộ của công nghệ học máy và trí tuệ nhân tạo. Việc kết hợp Random Forest với các kỹ thuật học sâu có thể mở ra nhiều cơ hội mới trong việc khai thác dữ liệu.

5.1. Xu hướng phát triển trong nghiên cứu

Nghiên cứu về Random Forest và trích chọn đặc trưng đang ngày càng được quan tâm. Các nghiên cứu mới sẽ tập trung vào việc cải thiện độ chính xác và hiệu suất của mô hình, cũng như ứng dụng trong các lĩnh vực mới.

5.2. Tương lai của học máy và trích chọn đặc trưng

Tương lai của học máy sẽ chứng kiến sự phát triển mạnh mẽ của các phương pháp trích chọn đặc trưng. Việc kết hợp các kỹ thuật học sâu với Random Forest có thể tạo ra những mô hình mạnh mẽ hơn, giúp giải quyết các bài toán phức tạp trong khai thác dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ công nghệ thông tin, khối lượng dữ liệu số toàn cầu gia tăng với tốc độ hơn 40% mỗi năm, đặt ra thách thức nghiêm trọng cho các hệ thống phát hiện tri thức và khai phá dữ liệu (KDD). Vấn đề cốt lõi của các bài toán học máy hiện đại là sự xuất hiện của các tập dữ liệu có số chiều cực lớn, trong đó không gian tìm kiếm thuộc tính tăng trưởng theo hàm mũ với quy mô $2^N$ trạng thái. Sự hiện diện của hàng loạt biến dư thừa và không liên quan làm gia tăng nguy cơ quá khớp (overfitting), đồng thời làm tăng chi phí tính toán lên hơn 70% trong quá trình huấn luyện mô hình.

Trước thực trạng đó, nghiên cứu tập trung giải quyết bài toán giảm chiều dữ liệu thông qua việc xây dựng và hoàn thiện phương pháp trích chọn đặc trưng dựa trên giải thuật phân lớp rừng ngẫu nhiên (Random Forest). Mục tiêu cụ thể của đề tài là khai thác sức mạnh của tập hợp cây quyết định kết hợp cùng chỉ số suy giảm Gini và kỹ thuật kiểm chứng chéo (cross-validation) để tự động sàng lọc không gian đặc trưng tối ưu.

Nghiên cứu được triển khai thực hiện tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội vào năm 2010. Phạm vi thực nghiệm tập trung vào các tập dữ liệu chuẩn đa chiều, bao gồm tập dữ liệu Madelon (chứa 500 thuộc tính tổng hợp) và tập dữ liệu sinh học Colon Tumor (với hơn 2000 thuộc tính biểu hiện gen tế bào ung thư đại trực tràng). Kết quả nghiên cứu chứng minh phương pháp đề xuất giúp loại bỏ hơn 60% số lượng biến dư thừa, cải thiện độ chính xác phân lớp từ 3% đến 8% so với mô hình gốc, đồng thời duy trì độ ổn định phân loại trên 95% trên các tập kiểm thử độc lập.

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 lý thuyết phát hiện tri thức trong cơ sở dữ liệu (KDD) với chu trình 4 giai đoạn chuẩn mực: kho dữ liệu, tiền xử lý, khai phá dữ liệu và hậu xử lý. Mô hình phân lớp cốt lõi là giải thuật rừng ngẫu nhiên (Random Forest) do Leo Breiman đề xuất, kết hợp nguyên lý cây quyết định CART (Classification and Regression Trees) với kỹ thuật học quần thể (ensemble learning) và tổng hợp lấy mẫu Bootstrap (Bagging). Bên cạnh đó, đề tài vận dụng lý thuyết xác suất Bayes nhằm phân tích mối quan hệ phụ thuộc giữa các biến thuộc tính và lớp nhãn đầu ra.

Hệ thống khái niệm chính của nghiên cứu bao gồm:

1. Trích chọn thuộc tính (Feature Selection): Quá trình xác định một tập con gồm $m$ thuộc tính từ tập $N$ thuộc tính ban đầu ($m \ll N$) nhằm tối ưu hóa hiệu năng của bộ phân lớp mà không làm thay đổi bản chất ngữ nghĩa của dữ liệu.
2. Độ quan trọng Gini (Gini Importance): Thước đo mức độ suy giảm độ không thuần khiết (impurity) tại mỗi nút phân nhánh của cây quyết định, cho phép định lượng mức độ đóng góp của từng biến vào việc phân tách các lớp.
3. Tỷ lệ lỗi ngoài túi (Out-Of-Bag Error - OOB): Cơ chế ước lượng lỗi nội tại dựa trên khoảng 36.8% mẫu dữ liệu không được lựa chọn trong quá trình tạo mẫu Bootstrap (chiếm xấp xỉ 1/3 tập huấn luyện ban đầu).
4. Mô hình Filter và Wrapper: Hai phương pháp luận kinh điển trong chọn lựa thuộc tính, trong đó Filter đánh giá dữ liệu độc lập với thuật toán học, còn Wrapper sử dụng trực tiếp độ chính xác của bộ phân lớp làm tiêu chuẩn đánh giá tập con.

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

Nguồn dữ liệu thực nghiệm được thu thập từ hai tập dữ liệu benchmark chuẩn quốc tế:

• Bộ dữ liệu Madelon gồm 2600 mẫu dữ liệu nhân tạo với 500 thuộc tính liên tục, được thiết kế chuyên biệt để đánh giá khả năng nhận diện các tương tác phi tuyến phức tạp.
• Bộ dữ liệu Colon Tumor bao gồm 62 mẫu sinh học thực tế (40 mẫu u ác tính và 22 mẫu mô bình thường) với 2000 thuộc tính đo lường mức độ biểu hiện của gen.

Phương pháp nghiên cứu chủ đạo là mô hình lai Dynamic Feature Elimination based on Random Forest (DFE-RF / RF_CT). Lý do lựa chọn phương pháp này xuất phát từ khả năng vượt trội của Random Forest trong việc xử lý dữ liệu phi tuyến tính, hạn chế hiện tượng quá khớp và tự động cung cấp độ đo quan trọng thuộc tính thông qua OOB và Gini. Quy trình phân tích tích hợp kỹ thuật kiểm chứng chéo N-Fold Cross-Validation (với $N=5$ đến $N=10$) và Leave-One-Out nhằm đảm bảo tính khách quan trong việc tinh chỉnh tham số và đánh giá sai số mô hình. Phương pháp chọn mẫu áp dụng kỹ thuật phân tầng ngẫu nhiên kết hợp Bootstrap có hoàn lại. Toàn bộ quá trình nghiên cứu, xây dựng thuật toán và đánh giá thực nghiệm được thực hiện liên tục trong khoảng thời gian 12 tháng.

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 sánh giữa thuật toán Random Forest tiêu chuẩn (RF) và thuật toán đề xuất (RF_CT) mang lại các phát hiện cụ thể:

1. Nâng cao độ chính xác phân lớp trên dữ liệu Madelon: Qua 50 lần chạy thử nghiệm độc lập ở các mức số cây khác nhau (100, 150, 200 và 250 cây), mô hình RF_CT liên tục cho kết quả vượt trội. Tại cấu hình 200 cây, tỷ lệ lỗi phân lớp trung bình trên tập kiểm chứng của RF_CT giảm xuống còn 12.4%, thấp hơn đáng kể so với mức 16.8% của thuật toán RF tiêu chuẩn (tương đương mức cải thiện hiệu năng tương đối đạt 26.19%).
2. Khả năng tinh gọn chiều dữ liệu sinh học Colon Tumor: Trong 20 lần thử nghiệm với số lượng cây từ 800 đến 1700 cây, phương pháp đề xuất đã loại bỏ thành công hơn 85% các gen không liên quan và gen nhiễu (thu gọn từ 2000 gen ban đầu xuống dưới 300 gen then chốt). Độ chính xác phân loại các mô bệnh học tăng từ 82.26% ở mô hình truyền thống lên mức 88.71% ở mô hình RF_CT.
3. Độ hội tụ ổn định của sai số ngoài túi (OOB): Đường cong sai số OOB của mô hình RF_CT đạt trạng thái ổn định sớm hơn khoảng 1.4 lần so với RF thông thường khi số lượng cây đạt mốc 250 cây trên tập Madelon và 1400 cây trên tập Colon Tumor.
4. Chi phí thời gian xử lý được kiểm soát: Do phải thực hiện lặp lại quá trình tính toán kiểm chứng chéo và xếp hạng chỉ số Gini, thời gian thực thi của RF_CT cao hơn từ 18% đến 32% so với RF tiêu chuẩn. Tuy nhiên, sự gia tăng thời gian này được bù đắp xứng đáng bằng việc dung lượng bộ nhớ lưu trữ mô hình giảm tới 65%.

Thảo luận kết quả

Dữ liệu thực nghiệm được biểu diễn trực quan thông qua hệ thống biểu đồ đường thể hiện sự suy giảm của hàm tỷ lệ lỗi OOB tương ứng với số lượng cây được sinh ra (từ 100 đến 250 cây trên tập Madelon và từ 800 đến 1700 cây trên tập Colon Tumor). Đồng thời, các bảng đối sánh đa biến trình bày chi tiết mối tương quan giữa thời gian chạy (tính bằng giây) và độ chính xác phân lớp trên cả tập huấn luyện lẫn tập kiểm chứng độc lập.

Nguyên nhân chính dẫn đến sự vượt trội của phương pháp học máy đề xuất là sự kết hợp chặt chẽ giữa cơ chế loại bỏ thuộc tính động và trọng số suy giảm Gini. Các phương pháp tìm kiếm truyền thống như Focus hay ABB bị giới hạn bởi độ phức tạp tính toán lớn $O(2^N)$ khi số lượng thuộc tính tăng cao. Trong khi đó, các phương pháp trọng số như Relief của Kira và Rendell hay phương pháp LVW của Liu thường gặp khó khăn trước các tập dữ liệu có nhiễu cao hoặc dữ liệu chỉ có hai lớp. Giải thuật RF_CT khắc phục triệt để các rào cản này bằng cách khai thác sự đồng thuận của tập hợp cây và cơ chế ngẫu nhiên hóa không gian biến. Nghiên cứu mang ý nghĩa học thuật sâu sắc khi cung cấp một giải pháp khả thi cho các bài toán phân lớp dữ liệu nhiều chiều trong y sinh học và xử lý dữ liệu lớn.

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

1. Tích hợp giải thuật RF_CT vào quy trình tiền xử lý dữ liệu lớn: Các phòng phân tích dữ liệu và trung tâm công nghệ thông tin cần áp dụng thuật toán đề xuất vào các đường ống (pipelines) xử lý dữ liệu tự động trong vòng 6 tháng tới, hướng tới mục tiêu cắt giảm ít nhất 50% số chiều dữ liệu trước khi đưa vào các mô hình học sâu.
2. Chuẩn hóa bộ tham số cấu hình số lượng cây và ngưỡng Gini: Nhóm kỹ sư học máy và khoa học dữ liệu cần xây dựng bộ quy chuẩn thiết lập tham số linh hoạt, duy trì số lượng cây tối ưu trong khoảng từ 200 đến 1500 cây tùy theo độ phức tạp của bài toán, hoàn thiện tài liệu hướng dẫn kỹ thuật trong thời hạn 3 tháng.
3. Triển khai ứng dụng trong chẩn đoán y sinh học phân tử: Các viện nghiên cứu y dược phối hợp cùng các đơn vị công nghệ thông tin ứng dụng phương pháp vào việc phân tích dữ liệu microarray biểu hiện gen ung thư, đặt mục tiêu nâng cao độ nhạy trong phát hiện dấu ấn sinh học sớm lên trên 90% trong lộ trình 12 tháng.
4. Tối ưu hóa mã nguồn bằng kỹ thuật tính toán song song: Đội ngũ phát triển thuật toán cần tái cấu trúc chương trình dựa trên các nền tảng tính toán phân tán (như Apache Spark hoặc xử lý đa luồng trên GPU) nhằm giảm từ 30% đến 40% thời gian thực thi của bước kiểm chứng chéo trong thời gian 9 tháng.

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

1. Học viên cao học và nghiên cứu sinh ngành Hệ thống thông tin và Khoa học máy tính: Tài liệu cung cấp cơ sở toán học vững chắc về chu trình KDD, phân tích chi tiết các thuật toán trích chọn cổ điển (Focus, ABB, LVF, LVW, Relief, QBB) và kỹ thuật học máy hiện đại; hỗ trợ trực tiếp cho quá trình xây dựng đề cương nghiên cứu và luận văn chuyên ngành.
2. Kỹ sư học máy (Machine Learning Engineers) và Data Scientists: Tài liệu mang lại giải pháp thực tế để xử lý các tập dữ liệu có số chiều cao trên 500 thuộc tính, giúp kiểm soát hiện tượng quá khớp và tiết kiệm hơn 40% tài nguyên tính toán của hệ thống máy chủ.
3. Các nhà nghiên cứu trong lĩnh vực Tin sinh học (Bioinformatics): Cung cấp phương pháp luận chuẩn xác để trích xuất top 50 đến 100 gen chỉ thị sinh học có ý nghĩa từ các bộ dữ liệu microarray chứa hàng nghìn chiều, phục vụ nghiên cứu điều trị ung thư và bệnh lý di truyền.
4. Chuyên gia phân tích rủi ro tài chính và ngân hàng: Vận dụng cơ chế xếp hạng thuộc tính để xác định các đặc trưng quyết định hành vi tín dụng của khách hàng, nâng cao độ chính xác trong phân nhóm khách hàng rủi ro lên trên 85%.

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

Tại sao cần trích chọn thuộc tính thay vì sử dụng toàn bộ dữ liệu ban đầu? Trong các tập dữ liệu nhiều chiều như Madelon (500 thuộc tính), việc sử dụng toàn bộ biến gây ra hiện tượng bùng nổ không gian $2^N$ và quá khớp mô hình. Trích chọn thuộc tính giúp loại bỏ hơn 60% dữ liệu nhiễu, tăng tốc độ huấn luyện lên hơn 30% và giúp mô hình trở nên dễ giải thích hơn trong thực tế.

Sự khác biệt cốt lõi giữa mô hình Filter và Wrapper trong trích chọn đặc trưng là gì? Mô hình Filter đánh giá biến độc lập với thuật toán phân lớp dựa trên các độ đo thông tin hoặc khoảng cách với chi phí tính toán thấp. Ngược lại, mô hình Wrapper (như phương pháp RF_CT) sử dụng trực tiếp độ chính xác của bộ phân lớp để đánh giá tập con, giúp nâng cao độ chính xác dự đoán thêm 5% đến 10%.

Chỉ số Gini Importance trong Random Forest đóng vai trò như thế nào? Chỉ số Gini đo lường mức độ thuần khiết của các nút phân nhánh trong cây quyết định. Bằng cách tính toán tổng mức độ suy giảm chỉ số Gini của từng biến trên toàn bộ rừng gồm 100 đến 1700 cây, thuật toán định lượng chính xác tầm quan trọng của từng thuộc tính để loại bỏ các biến không đóng góp vào việc phân lớp.

Dữ liệu Out-Of-Bag (OOB) được sử dụng để làm gì trong nghiên cứu này? Trong quá trình tạo mẫu Bootstrap, khoảng 36.8% số lượng phần tử không nằm trong tập mẫu huấn luyện của một cây cụ thể và được gọi là dữ liệu OOB. Dữ liệu này được dùng như một tập kiểm chứng tự nhiên để ước lượng tỷ lệ lỗi phân lớp và tính toán độ quan trọng hoán vị mà không cần chia tách tập dữ liệu ban đầu.

Phương pháp đề xuất RF_CT phù hợp nhất với những loại dữ liệu nào? Thuật toán phát huy hiệu quả tối đa trên các bộ dữ liệu có số chiều lớn và mối tương tác phi tuyến phức tạp giữa các thuộc tính, điển hình là dữ liệu biểu hiện gen microarray (hơn 2000 chiều) hoặc các bài toán phân loại văn bản đa lớp. Trong thực tế, mô hình giúp giảm chiều dữ liệu mạnh mẽ mà vẫn duy trì độ chính xác phân loại trên 88%.

Kết luận

• Hệ thống hóa toàn diện cơ sở lý thuyết về trích chọn thuộc tính, từ các giải thuật cổ điển (Focus, ABB, Relief) đến các mô hình học quần thể hiện đại.
• Đề xuất thành công phương pháp trích chọn đặc trưng cải tiến RF_CT dựa trên thuật toán Random Forest, kết hợp kiểm chứng chéo và đo lường độ suy giảm chỉ số Gini.
• Thực nghiệm chứng minh hiệu quả vượt trội trên hai tập dữ liệu benchmark Madelon và Colon Tumor, nâng cao độ chính xác phân lớp từ 3% đến 8%.
• Cắt giảm thành công từ 60% đến 85% các thuộc tính dư thừa, tối ưu hóa không gian lưu trữ và cải thiện độ ổn định của mô hình phân lớp.
• Xác lập định hướng nghiên cứu và ứng dụng trong lộ trình 12 đến 24 tháng tới nhằm mở rộng thuật toán trên nền tảng tính toán song song phân tán.

Công trình luận văn là tài liệu tham khảo học thuật có giá trị cao, mở ra hướng giải quyết triệt để cho các bài toán phân lớp dữ liệu lớn và tin sinh học phức tạp. Quý độc giả, các nhà nghiên cứu và doanh nghiệp quan tâm có thể khai thác mã nguồn và tài liệu toàn văn để ứng dụng vào thực tiễn tối ưu hóa dữ liệu.

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

Chương 1: Tổng quan Trang 16 LUAN VAN CHAT LUONG download : add [e-mail] 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 LUAN VAN CHAT LUONG download : add [e-mail] 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 LUAN VAN CHAT LUONG download : add [e-mail] 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 LUAN VAN CHAT LUONG download : add [e-mail] 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 LUAN VAN CHAT LUONG download : add [e-mail] 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.