Trang chủ / Công Nghệ Thông Tin

Cây Quyết Định Với Thuật Toán C4.5 Bằng Cách Giảm Nhiều Impurity


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.


Instance#

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!

Xem toàn bộ 81 trang tài liệu này.

Sử dụng cây quyết định phân lớp dữ liệu mất cân đối - 7

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

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 18/02/2023