Giải thuật rừng ngẫu nhiên xiên phân (RF-ODT): Bài giảng phương pháp nghiên cứu khoa học cho phân lớp dữ liệu số chiều lớn

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

(cid:73) thời gian huấn luyện nhanh (cid:73) xử lý được dữ liệu liên tục, rời rạc (cid:73) mô hình dễ diễn dịch (luật if ... then ...) (cid:73) kết quả tốt cho phân lớp, hồi quy

Khuyết điểm của cây quyết định

(cid:73) hàm phân hoạch: đơn biến (cid:73) 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

(cid:73) #individus (cid:28) #dimensions (cid:73) vài trăm phần tử với hàng nghìn chiều (cid:73) dữ liệu hoàn toàn dễ tách biệt (cid:73) có nhiều lựa chọn mô hình (cid:73) mô hình học thường cho độ chính xác 100% trong tập học (cid:73) nhưng dự báo tập kiểm tra không tốt (cid:73) 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

(cid:73) lớp quan tâm chiếm tỷ lệ rất thấp (lớp dương, thiểu số) (cid:73) lớp còn lại chiếm tỷ lệ rất cao (lớp âm, đa số) (cid:73) giải thuật phân lớp: độ chính xác toàn cục (cid:73) không dự đoán được lớp thiểu số (dương) (cid:73) ví dụ: tỷ lệ lớp dương là 5% và lớp âm là 95% (cid:73) 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

(cid:73) xem xét sự phụ thuộc của các biến (cid:73) hàm phân hoạch: đa biến (xiên) (cid:73) 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 đề

(cid:73) phân lớp dữ liệu không cân bằng (cid:73) phân lớp đa lớp (cid:73) 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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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 (Breiman et al., 84), (Quinlan, 93)

Học phân lớp dữ liệu

(cid:73) xây dựng cây: phân hoạch dữ liệu (gini, entropy) (cid:73) gán nhãn ở nút lá: bình chọn số đông (cid:73) cắt nhánh: tránh học vẹt

hum. windy Play, Don’t Play

outlook sunny sunny overcast rain rain rain . . . . . .

temp. 85 80 83 70 68 65 . . . . . .

85 90 78 96 80 70 . . . . . .

false true false false false true . . . . . .

Don’t Play Don’t Play Play Play Play Don’t Play . . . . . .

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 8/ 40

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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

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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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 hợp mô hình

Nguyên lý

(cid:73) giảm thành phần lỗi bias và/hoặc variance (cid:73) chú ý: bias và variance tỷ lệ nghịch (cid:73) kết hợp các mô hình học yếu (không quá tệ) và đa dạng (cid:73) Bagging (Breiman, 96) (cid:73) Boosting (Freund & Schapire, 95), (Breiman, 97) (cid:73) 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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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 (Breiman, 01)

Nguyên lý

(cid:73) xây dựng tập cây quyết định đa dạng, không cắt nhánh (cid:73) không cắt nhánh: giữ bias thấp (cid:73) tính đa dạng (ngẫu nhiên): giảm variance

Hiệu năng

(cid:73) huấn luyện: nhanh, đơn giản (cid:73) kết quả tốt khi so với Boosting, SVM (cid:73) 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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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 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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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

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

Cây quyết định Rừng ngẫu nhiên Cây xiên phân 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 (Do et al., 09)

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 14/ 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

Đá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

(cid:73) cài đặt giải thuật RF-ODT: C/C++, ATLAS, BLAS/LAPACK (cid:73) cài đặt giải thuật RF-C4.5: C (cid:73) sử dụng dụng LibSVM (Chang & Lin, 01)

Tập dữ liệu

(cid:73) số chiều lớn: 20 tập dữ liệu y sinh (Jinyan & Huiqing, 02) (cid:73) đ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

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

Lung Cancer BrighamWomen Hospital

Classes tumor, normal ALL, AML MLL, rest relapse, non-relapse cancer, normal cancer, normal cancer, normal positive, negative positive, negative cancer, normal germinal, activated Hyperdip, rest TEL-AML1, rest TEL-ALL, rest

*Subtypes of Acute Lymphoblastic (Hyperdip) *Subtypes of Acute Lymphoblastic (TEL-AML1) *Subtypes of Acute Lymphoblastic (T-ALL) *Subtypes of Acute Lymphoblastic (Others)

ID Ensemble 1 Colon Tumor 2 ALL-AML-Leukemia 3 *MLL-Leukemia 4 Breast Cancer 5 Duke Breast Cancer 6 Prostate Cancer 7 8 Central Nervous System 9 Translation Initiation Site 10 Ovarian Cancer NCI-PBSII 11 Diffuse Large B-Cell Lymphoma 12 13 14 15 16 Ovarian Cancer NCI-QStar 17 18 19 20

Lung Cancer DanaFarberCancer Institute (ADEN) Lung Cancer DanaFarberCancer Institute (SQUA) Lung Cancer DanaFarberCancer Institute (COID) Lung Cancer DanaFarberCancer Institute (normal)

#Ind #Dim 2000 7129 12582 24481 7129 12600 12533 7129 927 15154 4026 12558 12558 12558 12558 Others, diagnostic groups 373410 12600 12600 12600 12600

62 72 72 97 42 136 181 60 13375 253 47 327 327 327 327 216 203 203 203 203

cancer, normal ADEN, rest SQUA, rest COID, rest normal, rest

Validation loo trn-tst trn-tst trn-tst loo trn-tst trn-tst loo 10-fold loo loo trn-tst trn-tst trn-tst trn-tst loo loo loo loo loo

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 16/ 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

Tiêu chí đánh giá

Bảng: Confusion matrix

Prediction

True class

positive negative

positive tp fp

negative fn tn

Recall, Precision, F1, Accuracy

tp+fn = tp

pos

(cid:73) Recall = tp (cid:73) Precision = tp tp+fp (cid:73) F 1 = 2×prec×rec prec+rec

tp+tn

(cid:73) Accuracy =

tp+fn+tn+fp = tp+tn

pos+neg (cid:73) 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

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

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)

LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5

86.88 13.80

91.14 13.01

93.56 9.10

2.42 6.95 1.56 0.1357

9 7 4 0.1334

6.68 8.44 3.54 0.0022 gain** 15 3 2 0.0012 gain**

Precision mean standard deviation student ratio p-value result of RF-ODT RF-ODT win RF-ODT tie RF-ODT defeat p-value result of RF-ODT

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 19/ 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

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

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)

LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5

87.77 16.62

83.90 22.59

90.45 12.89

2.68 6.38 1.88 0.0759

8 8 4 0.1938

6.55 10.41 2.81 0.0111 gain* 11 7 2 0.0112 gain*

Recall mean standard deviation student ratio p-value result of RF-ODT RF-ODT win RF-ODT tie RF-ODT defeat p-value result of RF-ODT

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 21/ 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

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

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)

LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5

86.50 14.15

85.88 18.13

91.49 10.14

5.00 6.20 3.61 0.0019 gain** 15 3 2 0.0012 gain**

5.62 8.60 2.92 0.0088 gain* 14 5 1 0.0005 gain***

F1-measure mean standard deviation student ratio p-value result of RF-ODT RF-ODT win RF-ODT tie RF-ODT defeat p-value result of RF-ODT

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 23/ 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

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

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)

LibSVM RF-C4.5 RF-ODT RF-ODT vs LibSVM RF-ODT vs RF-C4.5

89.70 12.53

91.38 9.91

94.64 6.73

4.94 8.27 2.67 0.0151 gain* 13 5 2 0.0037 gain**

3.27 5.08 2.87 0.0097 gain* 13 6 1 0.0009 gain**

Accuracy mean standard deviation student ratio p-value result of RF-ODT RF-ODT win RF-ODT tie RF-ODT defeat p-value result of RF-ODT

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 25/ 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

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 21 Bupa 22 Breast cancer 23 Pima 24 Segment 25 Spambase 26 Optdigits 27 Satimage 28 Pendigits 29 Letters 30 Shuttle

#Ind #Dim Classes 345 569 768 2310 4601 5620 6435 10992 20000 58000

1, 2 M, B 1, 2 1, rest spam, non 9, rest 4, rest 0, rest A, rest 1, rest

6 30 8 19 57 64 36 16 16 9

Validation 10-fold 10-fold 10-fold 10-fold 10-fold trn-tst trn-tst trn-tst 3-fold trn-tst

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 26/ 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

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 standard deviation student ratio p-value result of RF-ODT RF-ODT win RF-ODT tie RF-ODT defeat p-value result of RF-ODT

0.69 3.10 0.70 0.5001 non significant 8 0 2 0.1094 almost significant

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 27/ 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

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

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ử

(cid:73) Forest Cover Types từ kho UCI (cid:73) 500k ind., 54 dim. (cid:73) LibSVM: huấn luyện hơn 1 tháng (cid:73) RF-ODT: 801,61 giây (cid:73) RF-ODT nhanh hơn RF-C4.5 khoảng 22 lần (cid:73) 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

Phân lớp dữ liệu không cân bằng Phân lớp đa lớp Tăng khả năng chịu đựng nhiễu 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 không cân bằng

(cid:73) thay đổi phân bố lực lượng mẫu: lấy mẫu giảm (cid:73) chi phí khác nhau: lỗi của lớp thiểu số cao hơn (cid:73) 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

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 1

20-newsgrp

Letters

Abalone

Pendigits

Page blocks

Pima

German

Segment

10 Satimage

Methods Acc. min class Acc. maj class Accuracy RF-C4.5 RF-ODT Breast cancer RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT RF-C4.5 RF-ODT

99,11 98,32 97,74 98,56 99,97 99,97 98,48 93,75 99,81 99,56 99,00 97,90 84,63 82,91 89,26 84,36 99,95 99,90 98,49 95,03

97,97 98,36 95,61 97,54 99,65 99,82 92,01 90,22 99,23 99,43 97,70 97,31 75,97 78,57 76,77 77,50 99,61 99,87 94,40 93,13

76,83 99,12 92,28 95,75 92,22 96,30 23,93 53,02 93,75 98,21 86,19 92,20 59,94 70,19 46,56 60,73 97,74 99,68 59,72 77,25

AUC F1 99,65 79,51 99,46 86,11 94,13 98,19 96,70 99,64 99,97 95,59 100 97,74 33,07 87,64 48,41 89,26 95,89 99,64 97,06 99,82 88,43 99,23 99,23 87,54 83,63 63,29 82,49 69,42 79,04 52,99 60,32 79,52 99,97 98,66 100 99,57 69,23 96,16 70,41 96,53

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 31/ 40

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

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 1-layer Neural nets (LeCun et al., 1998) Nearest-neighbor (Euclidean L2) (LeCun et al., 1998) Nearest-neighbor (Euclidean L2, deskewing) (LeCun et al., 1998) Convolution net LeNet-1 (Subsampling) (LeCun et al., 1998) Convolution net LeNet-4 (LeCun et al., 1998) Convolution net LeNet-5 (Distortions) (LeCun et al., 1998) Convolution net Boosted LeNet-4 (Distortions) (LeCun et al., 1998) Convolution net, cross-entropy (Affine distortions) (Simard et al., 2003) LibSVM (RBF, γ = 0, 05, c = 105) LibSVM (Poly, deg = 5, c = 105) SVM (Poly, deg = 9, virtual SV, local) (Decoste & Scholkopf, 2002) AdaBoost.M1 (100 trees with C4.5) (Kegl & Busa-Fekete, 2009) Products of boosted stumps (haar) (Kegl & Busa-Fekete, 2009) RF-ODT (200 oblique decision trees, GIST)

Accuracy (%) 88.00 95.00 97.60 98.30 98.90 99.15 99.30 99.40 98.37 96.65 99.44 95.95 99.12 99.20

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 33/ 40

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 Human Performance (Bromley & Sackinger, 1991) Nearest-neighbor (Simard et al., 1993) LeNet-1 (LeCun et al., 1989) Boosted neural nets (LeCun et al., 1989) Tangent distance(Simard et al., 1993) AdaBoost.M1 (100 trees with C4.5) (Kegl & Busa-Fekete, 2009) Products of boosted stumps (Kegl & Busa-Fekete, 2009) Products of boosted stumps (haar) (Kegl & Busa-Fekete, 2009) SVM (Poly, deg = 9, virtual SV, local) (Decoste & Scholkopf, 2002) SVM (RBF, γ = 0.2, c = 105) SVM (Poly, deg = 5, c = 105) RF-ODT (200 trees, GIST)

Accuracy (%) 97.50 94.10 95.00 97.40 97.40 94.02 95.76 96.26 97.00 95.42 95.72 96.71

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 34/ 40

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 1 Nearest-neighbor (van der Maaten, 09) 3 Nearest-neighbor (van der Maaten, 09) 5 Nearest-neighbor (van der Maaten, 09) Linear kernel classifers (van der Maaten, 09) RF-ODT (100 trees, GIST)

Accuracy (%) 78,32 79,21 79,26 67,01 94,80

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 35/ 40

Giải thuật ArcX4-iODT

Nguyên lý của ArcX4-iODT

(cid:73) xây dựng tuần tự tập cây ngẫu nhiên xiên phân (cid:73) tập trung vào khắc phục lỗi từ các mô hình xây dựng trước đó (cid:73) điều khiển độ phức tạp: độ sâu cây, SVM (cid:73) 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

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

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

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 2 3 4 5 6 7 8 9 10 11 12 13 14 15

75,00 95,00 100 75,00 94,44 100 100 55,56 84,42 100 87,50 95,46 100 100 39,68

90,91 100 100 91,67 90,00 96,00 100 66,67 80,69 100 95,65 100 100 100 85,19

74,42 97,56 100 83,33 86,49 86,21 96,77 31,25 82,15 99,39 93,62 93,02 98,11 100 45,71

74,07 100 100 78,57 90,00 100 93,75 63,64 90,24 100 100 95,65 100 100 79,31

76,19 95,24 100 83,33 94,12 75,76 93,75 45,46 92,58 98,78 95,65 95,24 100 100 100

85,48 100 100 78,94 90,48 97,06 99,33 75,00 93,27 100 97,87 99,11 100 100 91,07

81,63 100 100 84,62 90,00 97,96 96,77 65,11 85,20 100 97,78 97,78 100 100 82,14

80,65 97,06 93,33 63,16 90,48 73,53 98,66 68,33 92,15 100 89,36 98,21 100 100 64,29

82,26 97,06 100 78,94 88,10 76,47 99,33 63,33 92,30 99,21 93,62 97,32 99,11 100 83,93

68,18 100 75,00 69,23 85,00 73,53 88,26 47,62 83,13 100 91,30 95,46 100 100 92,59

72,73 100 100 83,33 80,00 100 100 23,81 73,83 100 91,67 90,91 96,30 100 29,63

71,43 97,44 100 72,00 89,47 84,75 93,75 51,28 83,77 100 89,36 95,46 100 100 55,56

Đỗ Thanh Nghị RF-ODT cho phân lớp dữ liệu có số chiều lớn 38/ 40

Phát triển mở rộng của RF-ODT

Nghiên cứu đang thực hiện

(cid:73) các hàm phân hoạch đa biến khác (cid:73) các luật quyết định (cid:73) cài đặt song song (cid:73) hồi quy, gom nhóm (cid:73) 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