3.4.2.4 Giải thuật cắt tỉa PruneTree
Algorithm 5. PruneTree
Input: full_tree cây quyết định đã xây dựng
Output: candidate_trees tập các cây quyết định ứng viên
(1) 𝑖←1
(2) tree(i) ← full_tree
(3) repeat
(4) 𝑃𝑟𝑢𝑛𝑒𝑆𝑒𝑡𝑖 consisting of parent nodes which child nodes are leaf nodes (5) for each node 𝑗 in 𝑃𝑟𝑢𝑛𝑒𝑆𝑒𝑡𝑖 do
(6) pruned_tree(j) ← Pruned tree at node j
(7) ∆𝐴𝑈𝐶𝑗← AUC of tree(i) ‒ AUC of pruned_tree(j)
(8) end for
(9) Find pruned_tree(j) corresponding to smallest ∆𝐴𝑈𝐶𝑗 (10) 𝑖←𝑖+1
(11) tree(i) ← pruned_tree(j)
(12) if tree(i) is the root node of full_tree then
(13) break
(14) end if
(15) end repeat
(16) Returrn candidate_trees ← {tree(i)}
Giải thuật PruneTree được dùng để tỉa cây full_tree, cây này được tạo bởi giải thuật GrowTree. Tại mỗi bước lặp của PruneTree, các nhánh dùng để tỉa thì được quyết định xem xét bởi giá trị AUC khác nhau nhỏ nhất giữa trước và sau khi tỉa nhánh. Sau đó chúng ta thu được một tập cây ứng viên candidate_trees.
Cuối cùng chúng ta dùng giải thuật ValidTrees để chọn ra cây quyết định cuối cùng final_tree
từ tập cây ứng viên candidate_trees. Tại bước này, chúng ta sử dụng tập dữ liệu đã chuẩn bị
trước Dvalid với tất cả các cây ứng viên candidate_trees để chọn ra một cây mà có giá trị AUC lớn nhất.
3.4.2.5 Giải thuật ValidTrees
Algorithm 6. ValidTrees
Input: tập cây ứng viên candidate_trees, {𝐷valid}
Output: Một cây quyết định cuối cùng final_tree
(1) for each tree(i)candidate_trees do
Compute AUC of tree(i) using Dvalid
(2) end for
(3) Return final_tree ← tree(i) corresponding to maximum AUC
3.5 Ví dụ minh hoạ cho thuật toán AUC4.5
Để rõ hơn về thuật toán AUC4.5, chúng ta xem ví dụ minh hoạ sau:
3.5.1 Dữ liệu minh hoạ
Bảng 3-2: Mô tả tập dữ liệu mất cân đối.
Attri1 | Attri2 | Class | |
I1 | 1 | 1 | negative |
I2 | 1 | 1 | negative |
I3 | 1 | 1 | positive |
I4 | 1 | 1 | positive |
I5 | 1 | 2 | positive |
I6 | 1 | 2 | negative |
I7 | 1 | 2 | negative |
I8 | 1 | 3 | negative |
I9 | 2 | 3 | negative |
I10 | 3 | 3 | negative |
I11 | 3 | 3 | positive |
Có thể bạn quan tâm!
-
Các Vấn Đề Trong Khai Thác Dữ Liệu Sử Dụng Cây Quyết Định -
Đánh Giá Độ Chính Xác Của Mô Hình Phân Lớp -
Phân Lớp Dữ Liệu Mất Cân Đối Bằng Cây Quyết Định -
Sử dụng cây quyết định phân lớp dữ liệu mất cân đối - 8 -
Sử dụng cây quyết định phân lớp dữ liệu mất cân đối - 9
Xem toàn bộ 81 trang tài liệu này.
Nguồn từ: nghiên cứu của tác giả.
Tập dữ liệu gồm 11 mẫu (4 positives và 7 negatives).
2 thuộc tính kiểu định danh (nominal type attributes)
3.5.2 Minh hoạ bằng thuật toán C4.5
Lý thuyết: Tham khảo phần 2.4.4.3
𝐼𝑛𝑓𝑜(𝑆) = − 4 𝑙𝑜𝑔 4 − 7 𝑙𝑜𝑔 7 = 0,95;
11 2 11 11 2 11
𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊1=1) = 0,95; 𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊1=2) = 0; 𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊1=3) = 1
0,95 − 8 ∗ 0,95 − 1 ∗ 0 − 2 ∗ 1
𝑰𝒏𝒇𝒐𝑮𝒂𝒊𝒏𝑹𝒂𝒕𝒊𝒐(𝑨𝒕𝒕𝒓𝒊𝟏) = 811
11 11
= 0,064
− 𝑙𝑜𝑔
8− 1𝑙𝑜𝑔
1− 2𝑙𝑜𝑔 2
11 2 11 11
2 11 11
2 11
𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊2=1) = 1; 𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊2=2) = 0,92; 𝐼𝑛𝑓𝑜(𝑆𝑨𝒕𝒕𝒓𝒊2=3) = 0,81
0,95 − 4 ∗ 1 − 3 ∗ 0,92 − 4 ∗ 0,82
𝑰𝒏𝒇𝒐𝑮𝒂𝒊𝒏𝑹𝒂𝒕𝒊𝒐(𝑨𝒕𝒕𝒓𝒊𝟐) = 411 11
11 = 0,023
− 𝑙𝑜𝑔
4− 3𝑙𝑜𝑔
3− 4𝑙𝑜𝑔 4
11 2 11 11
2 11 11
2 11
Ta chọn Attri1 là thuộc tính tốt nhất để phân nhánh vì giảm nhiều impurity
𝑰𝒏𝒇𝒐𝑮𝒂𝒊𝒏𝑹𝒂𝒕𝒊𝒐(𝑨𝒕𝒕𝒓𝒊𝟏) = 0,064 > 𝑰𝒏𝒇𝒐𝑮𝒂𝒊𝒏𝑹𝒂𝒕𝒊𝒐(𝑨𝒕𝒕𝒓𝒊𝟐) = 0,023
Ta được cây như sau: sau lần phân hoạch thứ nhất
Attri1
{P:4, N:7}
Attri1= 1
Attri1= 2
Attri1= 3
Attri2
{P:3, N:5}
N:1
Attri2
{P:1, N:1}
Hình 3-3: Cây quyết định với thuật toán C4.5 bằng cách giảm nhiều impurity
3.5.3 Minh hoạ bằng thuật toán AUC4.5
Từ Thuật toán 4 (MaxAUC). Tính AUC
Với Attri1: vì có 3 nút con được tạo (P:3; N:5) - (P:0; N:1) và (P:1; N:1) từ nút cha (Gốc), nên có 6 trường hợp gán nhãn lớp thứ tự như sau.
{+, , } {, +, } {, , +} {+, +, } {+, , +} và {, +, +}.
Tính AUC cho mỗi trường hợp và chọn max(AUC) để chọn dự đoán tốt nhất: 1. {+, , }
Predicted Class | |||
True Class | Positive | Negative | |
Positive | TP=3 | FN=1 | |
Negative | FP=5 | TN=2 |
𝑇𝑃𝑅 =
𝑇𝑃
𝑇𝑃 + 𝐹𝑁
3
= = 0,75 𝑣à 𝐹𝑃𝑅 = 4
𝐹𝑃
𝐹𝑃 + 𝑇𝑁
5
= = 0,71
7
𝑚𝐴𝑈𝐶1 =
2. {, +, }
1 + 𝑇𝑃𝑅 − 𝐹𝑃𝑅
=
2
1 + 0,75 − 0,71
= 0,52
2
Predicted Class | |||
True Class | Positive | Negative | |
Positive | TP=0 | FN=4 | |
Negative | FP=1 | TN=6 |
𝑇𝑃𝑅 =
𝑇𝑃
𝑇𝑃 + 𝐹𝑁
0
= = 0 𝑣à 𝐹𝑃𝑅 = 4
𝐹𝑃
𝐹𝑃 + 𝑇𝑁
1
= = 0,14
7
𝑚𝐴𝑈𝐶2 =
1 + 𝑇𝑃𝑅 − 𝐹𝑃𝑅
=
2
1 + 0 − 0,14
= 0,43
2
Tương tự tính cho 4 trường hợp còn lại.
3. {, , +}
𝑚𝐴𝑈𝐶3 = 0,56; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,25; 𝐹𝑃𝑅 = 0,14
4. {+, +, }
𝑚𝐴𝑈𝐶4 = 0,46; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,75; 𝐹𝑃𝑅 = 0,86
5. {+, , +}
𝑚𝐴𝑈𝐶5 = 0,57; 𝑣ớ𝑖 𝑇𝑃𝑅 = 1; 𝐹𝑃𝑅 = 0,83
6. {, +, +}
𝑚𝐴𝑈𝐶6 = 0,48; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,25; 𝐹𝑃𝑅 = 0,28
Line 1: AUCSplit()
Baseline = 0.5
Chọn 𝒎𝑨𝑼𝑪𝟓 = 𝟎, 𝟓𝟕 lớn nhất với nhãn lớp được gán {+, , +}. Tính AUCGainRatio của Attri1:
0,57 − 0,5
𝐴𝑈𝐶𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜(𝑨𝒕𝒕𝒓𝒊1) = 8
8 1 1 2
2 = 0,065
− 11 𝑙𝑜𝑔2 11 − 11 𝑙𝑜𝑔2 11 − 11 𝑙𝑜𝑔2 11
Với Attri2: vì có 3 nút con được tạo (P:2; N:2) - (P:1; N:2) và (P:1; N:3) từ nút cha (Gốc), nên có 6 trường hợp gán nhãn lớp thứ tự như sau:
{+, , } {, +, } {, , +} {+, +, } {+, , +} và {, +, +}.
Tính AUC cho mỗi trường hợp và chọn max(AUC) để chọn dự đoán tốt nhất: 1. {+, , }
Predicted Class | |||
True Class | Positive | Negative | |
Positive | TP=2 | FN=2 | |
Negative | FP=2 | TN=5 |
𝑇𝑃𝑅 =
𝑇𝑃
𝑇𝑃 + 𝐹𝑁
2
= = 0,50 𝑣à 𝐹𝑃𝑅 = 4
𝐹𝑃
𝐹𝑃 + 𝑇𝑁
2
= = 0,286
7
𝑚𝐴𝐶𝑈1 =
1 + 𝑇𝑃𝑅 − 𝐹𝑃𝑅
=
2
1 + 0,50 − 0,286
= 0,607
2
Tương tự tính cho các trường hợp còn lại.
2. {, +, }: 𝑚𝐴𝑈𝐶2 = 0,482 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,25; 𝐹𝑃𝑅 = 0,286
3. {, , +}: 𝑚𝐴𝑈𝐶3 = 0,410; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,25; 𝐹𝑃𝑅 = 0,428
4. {+, +, }: 𝑚𝐴𝑈𝐶4 = 0,482; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,75; 𝐹𝑃𝑅 = 0,571
5. {+, , +}: 𝑚𝐴𝑈𝐶5 = 0,517; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,75; 𝐹𝑃𝑅 = 0,714
6. {, +, +}: 𝑚𝐴𝑈𝐶6 = 0,393; 𝑣ớ𝑖 𝑇𝑃𝑅 = 0,50; 𝐹𝑃𝑅 = 0,714
Line 1: AUCSplit()
Baseline = 0.5
Chọn 𝒎𝑨𝑼𝑪𝟏 = 𝟎, 𝟔𝟎𝟕 lớn nhất với nhãn lớp được gán {+, , }. Tính AUCGainRatio của Attri2:
0,607 − 0,5
𝐴𝑈𝐶𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜(𝑨𝒕𝒕𝒓𝒊2) = 4
4 3 3 4
4 = 0,068
Lần phân hoạch đầu tiên với
− 11 𝑙𝑜𝑔2 11 − 11 𝑙𝑜𝑔2 11 − 11 𝑙𝑜𝑔2 11
𝐴𝑈𝐶𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜(𝑨𝒕𝒕𝒓𝒊1) = 0,065 < 𝐴𝑈𝐶𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜(𝑨𝒕𝒕𝒓𝒊2) = 𝟎, 𝟎𝟔𝟖
Ta chọn Attri2 là thuộc tính tốt nhất để phân nhánh, với nhãn {+, , }, có nhiều lợi ích trong việc gia tăng giá trị AUC của việc phân lớp. AUC4.5 tạo phân nhánh sau:
Attri2
{P:4, N:7}
{+}
Attri2= 1
{}
Attri2= 2
{}
Attri2= 3
Attri1
{P:2, N:2}
Attri1
{P:1, N:2}
Attri1
{P:1, N:3}
Hình 3-4: Cây quyết định với thuật toán AUC4.5 bằng cách gia tăng giá trị AUC
CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ
Để đánh giá hiệu quả thuật toán của thuật toán đề xuất AUC4.5, tác giả đã tiến hành thực nghiệm trên tám tập dữ liệu thực từ kho học máy UCI [28]. Bảng III là thông tin về các tập dữ liệu mà luận văn nghiên cứu và sử dụng trong quá trình thực nghiệm, đây đều là các tập dữ liệu có sự mất cân bằng giữa các lớp khá lớn.
4.1 Mô tả tập dữ liệu
Bộ dữ liệu thực từ kho học máy UCI [28]
Bảng 4-1: Tập dữ liệu với số phần tử lớp thiểu số
Tập dữ liệu | Tỷ lệ Lớp thiểu số | Thuộc tính | Số Phần tử | ||
Liên tục | Rời rạc | ||||
1 | Wine Quality - Red | 1.13% | 12 | 0 | 1599 |
2 | Nursey | 2.53% | 0 | 9 | 12960 |
3 | Car Evaluation | 3.76% | 0 | 6 | 1728 |
4 | Ecoli | 5.95% | 8 | 1 | 336 |
5 | Mushroom | 7.60% | 0 | 22 | 4554 |
6 | Wine Quality – White | 17.97% | 12 | 0 | 4898 |
7 | Contraceptive Method Choice | 22.61% | 9 | 0 | 1473 |
8 | Tic-Tac-Toe Endgame | 34.62% | 0 | 9 | 958 |
4.2 Môi trường thực nghiệm
Thuật toán AUC4.5 được thực nghiệm trên:
+ Bộ dữ liệu thực nghiệm được lấy từ kho học máy UCI
+ Hệ thống:
- Macbook Pro 15-inch, Processor 2.5 GHz Intel Core i7, RAM 16 GB
- Graphic Card AMD Radeon R9 M370X 2GB
- macOS High Sierra, version 10.13.5
+ Ngôn ngữ lập trình hỗ trợ:
- Python 3.6
- IDE PyCharm Professional Edition 2017.3, x64
+ Một số ứng dụng khác:
- Microsoft Excel: Hỗ trợ phân tích kết quả và vẽ biểu đồ
- Weka: Xử lý, chuẩn hóa dữ liệu
4.3 Kiểm chứng mô hình bằng phương pháp Hold-out
Chia dữ liệu D thành 2 phần: 𝐷𝑇𝑟𝑎𝑖𝑛và 𝐷𝑇𝑒𝑠𝑡 bằng phương pháp stratified random partitioning.
𝐷𝑇𝑟𝑎𝑖𝑛: 66,7% để xây dựng mô hình tập học (hoặc tập huấn luyện): chia tiếp dữ liệu học thành 2 phần.
- 𝐷𝐺𝑟𝑜𝑤𝑛 : 66,7% dùng để xây dựng cây
- 𝐷𝑉𝑎𝑙𝑖𝑑𝑎𝑡𝑖𝑜𝑛: 33,3% dùng để kiểm tra cây đã được huấn luyện
𝐷𝑇𝑒𝑠𝑡 : 33,3% để kiểm tra (tập kiểm tra – tập test).
- Thuật toán được hiện thực trên tập kiểm tra 𝐷𝑇𝑒𝑠𝑡 10 lần và lấy kết quả trung bình.
4.4 Kết quả thực nghiệm
Cuối cùng, nghiên cứu sẽ hiện thực và thực nghiệm những cải tiến để so sánh với thuật toán Standard C4.5 (SC4.5) và Cost-Sensitive C4.5 (CSC4.5). Với thuật toán SC4.5 và CSC4.5 kết quả dựa trên bài báo gốc [29] để so sánh với AUC4.5, từ đó đưa ra kết luận và hướng phát triển phân lớp cho tập dữ liệu mất cân đối bằng cây quyết định.
4.4.1 Phương sai, độ lệch chuẩn
Bảng 4-2: Phương sai, độ lệch chuẩn trên toàn bộ các tập dữ liệu
Tập dữ liệu | Thuộc tính | Phương sai | Độ lệch chuẩn | |
1 | Car-Evaluation | Rời rạc | 0.00000 | 0.00000 |
2 | Mushroom | Rời rạc | 0.00000 | 0.00000 |
3 | Nursery | Rời rạc | 0.00010 | 0.00988 |
4 | Tic-Tac-Toe | Rời rạc | 0.00017 | 0.01285 |
5 | Contraceptive-Method-Choice | Liên tục | 0.00041 | 0.02028 |
6 | Winequlity-White | Liên tục | 0.00069 | 0.02631 |
7 | Ecoli | Liên tục | 0.00091 | 0.03022 |
8 | Winequlity-Red | Liên tục | 0.00906 | 0.09520 |