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ị

Nội dung text: 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ị

1. 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 ∼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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triể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 temp. hum. windy Play, Don’t Play sunny 85 85 false Don’t Play 5 sunny 80 90 true Don’t Play Choose a descritor overcast 83 78 false Play to split the data (outlook) 9 rain 70 96 false Play rain 68 80 false Play Sunny Overcast Rain 2 rain 65 70 true Don’t Play 3 4 Humidity 2 3 > 75 <= 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
9. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triể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 = bias2 + variance Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 9/ 40
10. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triể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
11. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triển Rừng ngẫu nhiên (Breiman, 01) Nguyên lý I xây dựng tập cây quyết định đa dạng, không cắt nhánh I không cắt nhánh: giữ bias thấp I tính đa dạng (ngẫu nhiên): giảm variance Hiệu năng I huấn luyện: nhanh, đơn giản I kết quả tốt khi so với Boosting, SVM I khả năng chịu đựng nhiễu cao Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 11/ 40
12. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triển Cây xiên phân (ODT) Kết hợp nhiều chiều: xử lý dữ liệu có số chiều lớn, phụ thuộc Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 12/ 40
13. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triển ODT: siêu phẳng phân hoạch tối ưu Máy học véc-tơ hỗ trợ - SVM (Vapnik, 95) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 13/ 40
14. Giới thiệu Cây quyết định Rừng ngẫu nhiên xiên phân (RF-ODT) Rừng ngẫu nhiên Kết quả thực nghiệm Cây xiên phân Hướng phát triển Rừng ngẫu nhiên xiên phân RF-ODT (Do et al., 09) Training set Learning set (m individuals, n dimensions) A bootstrap sample of m examples from the training set. Bootstrap 1 Bootstrap 2 Bootstrap k ODT 1 ODT 2 ODT k In each non terminal node Split function: a proximal x x x SVM to perform an oblique splitting using n' dimensions randomly chosen from the n x x x dimensions with costs re- balancing of individuals. ŷ (x) ŷ (x) ŷ (x) 1 2 k Decision for a new example X Classification: the majority class in {ŷ (x), ŷ (x), , ŷ (x)}. 1 2 k Regression: (ŷ (x) + ŷ (x) + + ŷ (x)) / k. 1 2 k Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 14/ 40
15. 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 Đánh giá hiệu quả của giải thuật RF-ODT So sánh RF-ODT với RF-C4.5 và Lib-SVM I cài đặt giải thuật RF-ODT: C/C++, ATLAS, BLAS/LAPACK I cài đặt giải thuật RF-C4.5: C I sử dụng dụng LibSVM (Chang & Lin, 01) Tập dữ liệu I số chiều lớn: 20 tập dữ liệu y sinh (Jinyan & Huiqing, 02) I đa chiều: 10 tập dữ liệu từ kho UCI (Asuncion & Newman, 07) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 15/ 40
16. 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 Tập dữ liệu y sinh có số chiều lớn Bảng: Mô tả 20 tập dữ liệu y sinh ID Ensemble #Ind #Dim Classes Validation 1 Colon Tumor 62 2000 tumor, normal loo 2 ALL-AML-Leukemia 72 7129 ALL, AML trn-tst 3 *MLL-Leukemia 72 12582 MLL, rest trn-tst 4 Breast Cancer 97 24481 relapse, non-relapse trn-tst 5 Duke Breast Cancer 42 7129 cancer, normal loo 6 Prostate Cancer 136 12600 cancer, normal trn-tst 7 Lung Cancer BrighamWomen Hospital 181 12533 cancer, normal trn-tst 8 Central Nervous System 60 7129 positive, negative loo 9 Translation Initiation Site 13375 927 positive, negative 10-fold 10 Ovarian Cancer NCI-PBSII 253 15154 cancer, normal loo 11 Diffuse Large B-Cell Lymphoma 47 4026 germinal, activated loo 12 *Subtypes of Acute Lymphoblastic (Hyperdip) 327 12558 Hyperdip, rest trn-tst 13 *Subtypes of Acute Lymphoblastic (TEL-AML1) 327 12558 TEL-AML1, rest trn-tst 14 *Subtypes of Acute Lymphoblastic (T-ALL) 327 12558 TEL-ALL, rest trn-tst 15 *Subtypes of Acute Lymphoblastic (Others) 327 12558 Others, diagnostic groups trn-tst 16 Ovarian Cancer NCI-QStar 216 373410 cancer, normal loo 17 Lung Cancer DanaFarberCancer Institute (ADEN) 203 12600 ADEN, rest loo 18 Lung Cancer DanaFarberCancer Institute (SQUA) 203 12600 SQUA, rest loo 19 Lung Cancer DanaFarberCancer Institute (COID) 203 12600 COID, rest loo 20 Lung Cancer DanaFarberCancer Institute (normal) 203 12600 normal, rest loo Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 16/ 40
17. 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 Tiêu chí đánh giá Bảng: Confusion matrix Prediction positive negative True class positive tp fn negative fp tn Recall, Precision, F1, Accuracy tp tp I Recall = tp+fn = pos tp I Precision = tp+fp 2×prec×rec I F 1 = prec+rec tp+tn tp+tn I Accuracy = tp+fn+tn+fp = pos+neg I thời gian huấn luyện: PC Pentium 2,4 GHz, 1 GB RAM, Linux Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 17/ 40
18. 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 Kết quả phân lớp (Precision) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 18/ 40
19. 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 Kết quả phân lớp (Precision) Bảng: So sánh kết quả phân lớp (Precision) Precision LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5 mean 86.88 91.14 93.56 6.68 2.42 standard deviation 13.80 13.01 9.10 8.44 6.95 student ratio 3.54 1.56 p-value 0.0022 0.1357 result of RF-ODT gain RF-ODT win 15 9 RF-ODT tie 3 7 RF-ODT defeat 2 4 p-value 0.0012 0.1334 result of RF-ODT gain Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 19/ 40
20. 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 Kết quả phân lớp (Recall) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 20/ 40
21. 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 Kết quả phân lớp (Recall) Bảng: So sánh kết quả phân lớp (Recall) Recall LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5 mean 87.77 83.90 90.45 2.68 6.55 standard deviation 16.62 22.59 12.89 6.38 10.41 student ratio 1.88 2.81 p-value 0.0759 0.0111 result of RF-ODT gain* RF-ODT win 8 11 RF-ODT tie 8 7 RF-ODT defeat 4 2 p-value 0.1938 0.0112 result of RF-ODT gain* Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 21/ 40
22. 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 Kết quả phân lớp (F1) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 22/ 40
23. 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 Kết quả phân lớp (F1) Bảng: So sánh kết quả phân lớp (F1) F1-measure LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5 mean 86.50 85.88 91.49 5.00 5.62 standard deviation 14.15 18.13 10.14 6.20 8.60 student ratio 3.61 2.92 p-value 0.0019 0.0088 result of RF-ODT gain gain* RF-ODT win 15 14 RF-ODT tie 3 5 RF-ODT defeat 2 1 p-value 0.0012 0.0005 result of RF-ODT gain gain Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 23/ 40
24. 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 Kết quả phân lớp (Accuracy) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 24/ 40
25. 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 Kết quả phân lớp (Accuracy) Bảng: So sánh kết quả phân lớp(Accuracy) Accuracy LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5 mean 89.70 91.38 94.64 4.94 3.27 standard deviation 12.53 9.91 6.73 8.27 5.08 student ratio 2.67 2.87 p-value 0.0151 0.0097 result of RF-ODT gain* gain* RF-ODT win 13 13 RF-ODT tie 5 6 RF-ODT defeat 2 1 p-value 0.0037 0.0009 result of RF-ODT gain gain Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 25/ 40
26. 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 Tập dữ liệu từ kho UCI Bảng: Mô tả 10 tập dữ liệu đa chiều từ kho UCI ID Ensemble #Ind #Dim Classes Validation 21 Bupa 345 6 1, 2 10-fold 22 Breast cancer 569 30 M, B 10-fold 23 Pima 768 8 1, 2 10-fold 24 Segment 2310 19 1, rest 10-fold 25 Spambase 4601 57 spam, non 10-fold 26 Optdigits 5620 64 9, rest trn-tst 27 Satimage 6435 36 4, rest trn-tst 28 Pendigits 10992 16 0, rest trn-tst 29 Letters 20000 16 A, rest 3-fold 30 Shuttle 58000 9 1, rest trn-tst Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 26/ 40
27. 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 Kết quả phân lớp Bảng: So sánh kết quả phân lớp (Accuracy) Accuracy RF-ODT vs RF-C4.5 mean 0.69 standard deviation 3.10 student ratio 0.70 p-value 0.5001 result of RF-ODT non significant RF-ODT win 8 RF-ODT tie 0 RF-ODT defeat 2 p-value 0.1094 result of RF-ODT almost significant Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 27/ 40
28. 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 Thời gian huấn luyện (secs) Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 28/ 40
29. 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 Thời gian huấn luyện (secs) Phân lớp tập dữ liệu có nhiều phần tử I Forest Cover Types từ kho UCI I 500k ind., 54 dim. I LibSVM: huấn luyện hơn 1 tháng I RF-ODT: 801,61 giây I RF-ODT nhanh hơn RF-C4.5 khoảng 22 lần I RF-ODT chính xác hơn RF-C4.5: 0.41% Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 29/ 40
30. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu 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 không cân bằng I thay đổi phân bố lực lượng mẫu: lấy mẫu giảm I chi phí khác nhau: lỗi của lớp thiểu số cao hơn I thay thế luật quyết định: luật cục bộ Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 30/ 40
31. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Phân lớp dữ liệu không cân bằng Bảng: So sánh kết quả phân lớp dữ liệu không cân bằng ID Ensemble Methods Acc. min class Acc. maj class Accuracy F1 AUC 1 20-newsgrp RF-C4.5 76,83 99,11 97,97 79,51 99,65 RF-ODT 99,12 98,32 98,36 86,11 99,46 2 Breast cancer RF-C4.5 92,28 97,74 95,61 94,13 98,19 RF-ODT 95,75 98,56 97,54 96,70 99,64 3 Letters RF-C4.5 92,22 99,97 99,65 95,59 99,97 RF-ODT 96,30 99,97 99,82 97,74 100 4 Abalone RF-C4.5 23,93 98,48 92,01 33,07 87,64 RF-ODT 53,02 93,75 90,22 48,41 89,26 5 Pendigits RF-C4.5 93,75 99,81 99,23 95,89 99,64 RF-ODT 98,21 99,56 99,43 97,06 99,82 6 Page blocks RF-C4.5 86,19 99,00 97,70 88,43 99,23 RF-ODT 92,20 97,90 97,31 87,54 99,23 7 Pima RF-C4.5 59,94 84,63 75,97 63,29 83,63 RF-ODT 70,19 82,91 78,57 69,42 82,49 8 German RF-C4.5 46,56 89,26 76,77 52,99 79,04 RF-ODT 60,73 84,36 77,50 60,32 79,52 9 Segment RF-C4.5 97,74 99,95 99,61 98,66 99,97 RF-ODT 99,68 99,90 99,87 99,57 100 10 Satimage RF-C4.5 59,72 98,49 94,40 69,23 96,16 RF-ODT 77,25 95,03 93,13 70,41 96,53 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 31/ 40
32. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 32/ 40
33. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển RF-ODT nhận dạng ký tự số viết tay MNIST Bảng: So sánh kết quả nhận dạng ký tự số viết tay MNIST Methods Accuracy (%) 1-layer Neural nets (LeCun et al., 1998) 88.00 Nearest-neighbor (Euclidean L2) (LeCun et al., 1998) 95.00 Nearest-neighbor (Euclidean L2, deskewing) (LeCun et al., 1998) 97.60 Convolution net LeNet-1 (Subsampling) (LeCun et al., 1998) 98.30 Convolution net LeNet-4 (LeCun et al., 1998) 98.90 Convolution net LeNet-5 (Distortions) (LeCun et al., 1998) 99.15 Convolution net Boosted LeNet-4 (Distortions) (LeCun et al., 1998) 99.30 Convolution net, cross-entropy (Affine distortions) (Simard et al., 2003) 99.40 LibSVM (RBF, γ = 0, 05, c = 105) 98.37 LibSVM (Poly, deg = 5, c = 105) 96.65 SVM (Poly, deg = 9, virtual SV, local) (Decoste & Scholkopf, 2002) 99.44 AdaBoost.M1 (100 trees with C4.5) (Kegl & Busa-Fekete, 2009) 95.95 Products of boosted stumps (haar) (Kegl & Busa-Fekete, 2009) 99.12 RF-ODT (200 oblique decision trees, GIST) 99.20 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 33/ 40
34. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển RF-ODT nhận dạng ký tự số viết tay USPS Bảng: So sánh kết quả nhận dạng ký tự số viết tay USPS Methods Accuracy (%) Human Performance (Bromley & Sackinger, 1991) 97.50 Nearest-neighbor (Simard et al., 1993) 94.10 LeNet-1 (LeCun et al., 1989) 95.00 Boosted neural nets (LeCun et al., 1989) 97.40 Tangent distance(Simard et al., 1993) 97.40 AdaBoost.M1 (100 trees with C4.5) (Kegl & Busa-Fekete, 2009) 94.02 Products of boosted stumps (Kegl & Busa-Fekete, 2009) 95.76 Products of boosted stumps (haar) (Kegl & Busa-Fekete, 2009) 96.26 SVM (Poly, deg = 9, virtual SV, local) (Decoste & Scholkopf, 2002) 97.00 SVM (RBF, γ = 0.2, c = 105) 95.42 SVM (Poly, deg = 5, c = 105) 95.72 RF-ODT (200 trees, GIST) 96.71 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 34/ 40
35. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển RF-ODT nhận dạng chữ viết tay New-bench-HCR Bảng: So sánh kết quả nhận dạng chữ viết tay New-bench-HCR Methods Accuracy (%) 1 Nearest-neighbor (van der Maaten, 09) 78,32 3 Nearest-neighbor (van der Maaten, 09) 79,21 5 Nearest-neighbor (van der Maaten, 09) 79,26 Linear kernel classifers (van der Maaten, 09) 67,01 RF-ODT (100 trees, GIST) 94,80 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 35/ 40
36. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Giải thuật ArcX4-iODT Nguyên lý của ArcX4-iODT I xây dựng tuần tự tập cây ngẫu nhiên xiên phân I tập trung vào khắc phục lỗi từ các mô hình xây dựng trước đó I điều khiển độ phức tạp: độ sâu cây, SVM I xử lý dữ liệu số chiều lớn, 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 36/ 40
37. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Giải thuật ArcX4-iODT: khi tăng số bước lặp Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 37/ 40
38. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển ArcX4-iODT cho phân lớp dữ liệu y sinh Bảng: So sánh kết quả phân lớp dữ liệu y sinh Ensemble Precision Recall F1 Accuracy ID LibSVM RF-C4,5 ArcX4-rODT LibSVM RF-C4,5 ArcX4-rODT LibSVM RF-C4,5 ArcX4-rODT LibSVM RF-C4,5 ArcX4-rODT 1 68,18 76,19 74,07 75,00 72,73 90,91 71,43 74,42 81,63 80,65 82,26 85,48 2 100 95,24 100 95,00 100 100 97,44 97,56 100 97,06 97,06 100 3 75,00 100 100 100 100 100 100 100 100 93,33 100 100 4 69,23 83,33 78,57 75,00 83,33 91,67 72,00 83,33 84,62 63,16 78,94 78,94 5 85,00 94,12 90,00 94,44 80,00 90,00 89,47 86,49 90,00 90,48 88,10 90,48 6 73,53 75,76 100 100 100 96,00 84,75 86,21 97,96 73,53 76,47 97,06 7 88,26 93,75 93,75 100 100 100 93,75 96,77 96,77 98,66 99,33 99,33 8 47,62 45,46 63,64 55,56 23,81 66,67 51,28 31,25 65,11 68,33 63,33 75,00 9 83,13 92,58 90,24 84,42 73,83 80,69 83,77 82,15 85,20 92,15 92,30 93,27 10 100 98,78 100 100 100 100 100 99,39 100 100 99,21 100 11 91,30 95,65 100 87,50 91,67 95,65 89,36 93,62 97,78 89,36 93,62 97,87 12 95,46 95,24 95,65 95,46 90,91 100 95,46 93,02 97,78 98,21 97,32 99,11 13 100 100 100 100 96,30 100 100 98,11 100 100 99,11 100 14 100 100 100 100 100 100 100 100 100 100 100 100 15 92,59 100 79,31 39,68 29,63 85,19 55,56 45,71 82,14 64,29 83,93 91,07 Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 38/ 40
39. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Phát triển mở rộng của RF-ODT Nghiên cứu đang thực hiện I các hàm phân hoạch đa biến khác I các luật quyết định I cài đặt song song I hồi quy, gom nhóm I phân loại ảnh, văn bản, etc. Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 39/ 40
40. Giới thiệu Phân lớp dữ liệu không cân bằng Rừng ngẫu nhiên xiên phân (RF-ODT) Phân lớp đa lớp Kết quả thực nghiệm Tăng khả năng chịu đựng nhiễu Hướng phát triển Cám ơn & câu hỏi thảo luận Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 40/ 40