Nội dung

Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Giải thuật rừng ngẫu nhiên xiên phân (RF-ODT) cho phân lớp dữ liệu có số chiều lớn Đỗ Thanh Nghị Khoa CNTT-TT, ĐH. Cần Thơ Số 1 Lý Tự Trọng, Ninh Kiều, Cần Thơ Email: dtnghi@cit.ctu.edu.vn http://www.cit.ctu.edu.vn/∼dtnghi ĐHBK Tp.HCM, 27/03/2014 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 1/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Nội dung Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 2/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Cây quyết định: top 10 giải thuật khai mỏ dữ liệu hiệu quả (Wu et al., 08) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 3/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Cây quyết định: top 10 giải thuật khai mỏ dữ liệu hiệu quả (Wu et al., 08) Ưu điểm của cây quyết định I thời gian huấn luyện nhanh I xử lý được dữ liệu liên tục, rời rạc I mô hình dễ diễn dịch (luật if ... then ...) I kết quả tốt cho phân lớp, hồi quy Khuyết điểm của cây quyết định I hàm phân hoạch: đơn biến I không hiệu quả cho vấn đề phức tạp: số chiều rất lớn (nhiễu), mất cân bằng, phi tuyến Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 4/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Top 10 vấn đề khó của khai mỏ dữ liệu (Yang & Wu, 06) Phân lớp dữ liệu có số chiều lớn I #individus  #dimensions I vài trăm phần tử với hàng nghìn chiều I dữ liệu hoàn toàn dễ tách biệt I có nhiều lựa chọn mô hình I mô hình học thường cho độ chính xác 100% trong tập học I nhưng dự báo tập kiểm tra không tốt I mô hình tốt: dự báo tốt trong tương lai Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 5/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Top 10 vấn đề khó của khai mỏ dữ liệu (Yang & Wu, 06) Phân lớp dữ liệu không cân bằng I lớp quan tâm chiếm tỷ lệ rất thấp (lớp dương, thiểu số) I lớp còn lại chiếm tỷ lệ rất cao (lớp âm, đa số) I giải thuật phân lớp: độ chính xác toàn cục I không dự đoán được lớp thiểu số (dương) I ví dụ: tỷ lệ lớp dương là 5% và lớp âm là 95% I mô hình học M không dự đoán được lớp dương, chỉ luôn dự đoán là lớp âm, thì độ chính xác toàn cục vẫn là 95% Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 6/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp dữ liệu có số chiều lớn I xem xét sự phụ thuộc của các biến I hàm phân hoạch: đa biến (xiên) I phân lớp rất hiệu quả dữ liệu có số chiều lớn Mở rộng cho các vấn đề I phân lớp dữ liệu không cân bằng I phân lớp đa lớp I tăng khả năng chịu đựng nhiễu Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 7/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Cây quyết định Rừng ngẫu nhiên Cây xiên phân Cây quyết định (Breiman et al., 84), (Quinlan, 93) Học phân lớp dữ liệu I xây dựng cây: phân hoạch dữ liệu (gini, entropy) I gán nhãn ở nút lá: bình chọn số đông I cắt nhánh: tránh học vẹt outlook sunny sunny overcast rain rain rain ... ... temp. 85 80 83 70 68 65 ... ... hum. 85 90 78 96 80 70 ... ... windy false true false false false true ... ... Play, Don’t Play Don’t Play Don’t Play Play Play Play Don’t Play ... ... 5 Choose a descritor to split the data (outlook) 3 > 75 Rain Overcast Sunny Humidity 9 2 4 3 2 <= 75 We can stop Yes No When to stop? Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 8/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Cây quyết định Rừng ngẫu nhiên Cây xiên phân Phân tích hiệu quả của giải thuật học (Breiman, 96) Lỗi của giải thuật học: error = bias 2 + variance Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 9/ 40 Giới thiệu Rừng ngẫu nhiên xiên phân (RF-ODT) Kết quả thực nghiệm Hướng phát triển Cây quyết định Rừng ngẫu nhiên Cây xiên phân Tập hợp mô hình Nguyên lý I giảm thành phần lỗi bias và/hoặc variance I chú ý: bias và variance tỷ lệ nghịch I kết hợp các mô hình học yếu (không quá tệ) và đa dạng I Bagging (Breiman, 96) I Boosting (Freund & Schapire, 95), (Breiman, 97) I Rừng ngẫu nhiên (Breiman, 01) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 10/ 40