Thuật toán xây dựng cây quyết định (bằng tập thô)

Ví dụ 1

POSoutlook(PlayTennis) = {D3, D7, D12, D13}

POStemp(PlayTennis) = POShumidity(PlayTennis) = POSwind(PlayTennis) = {null}

=> Chọn thuộc tính chia là Outlook, xây dựng 3 bảng quyết định (root Outlook)

T0 (brand overcast)

U1	Temp	Humidity	Wind	Playtennis
D3	Hot	High	Weak	Yes
D7	Cool	Normal	Strong	Yes
D12	Mild	High	Strong	Yes
D13	Hot	Normal	Weak	Yes

 T1 (brand sunny)

U0	Temp	Humidity	Wind	Playtennis
D1	Hot	High	Weak	No
D2	Hot	High	Strong	No
D8	Mild	High	Weak	No
D9	Cool	Normal	Weak	Yes
D11	Mild	Normal	Strong	Yes

 T2 (brand rain)

U1	Temp	Humidity	Wind	Playtennis
D4	Mild	High	Weak	Yes
D5	Cool	Normal	Weak	Yes
D6	Cool	Normal	Strong	No
D10	Mild	Normal	Weak	Yes
D14	Mild	High	Strong	No

                                  Outlook

           /                          |                            \

overcast                      sunny                        rain

Xét bảng T0: 

Là hệ quyết định thuần khiết vì các đối tượng đều có kết quả là Yes (Brand Overcast have leaf is YES)

overcast                  

       /                             

    YES

Xét bảng T1:

Từ bảng T1 ta có

- POSwind(Playtennis) = {null}

- POStemp(Playtennis) = {D1, D2, D9}

- POShumidity(Playtennis) = {D1, D2, D8, D9, D11}

=> Chọn thuộc tính chia chính là Humidity, chia 2 bảng quyết định T10 và T11 (brand sunny have node Humidity)

Bảng T10:

U1	Temp	Humidity	Wind	Playtennis
D1	Hot	High	Weak	No
D2	Hot	High	Strong	No
D8	Mild	High	Weak	No

Bảng T11:

U1	Temp	Humidity	Wind	Playtennis
D9	Cool	Normal	Weak	Yes
D11	Mild	Normal	Strong	Yes

=> T10 là hệ thuần khiết vì các đối tượng có Humidity = High đều cho kết quả PlayTennis là No (brand High have leaf NO)

=> T11 là hệ thuần khiết vì các đối tượng có Humidity = Normal đều cho kết quả PlayTennis là Yes (brand Normal have leaf YES)

                                       sunny

                                        |                            

                               Humidity                       

                                    /    \                         

                               high    normal          

                                /            \                    

                            NO            YES

Xét bảng T2:

Từ bảng T2 ta có:

POSwind(playtennnis) = {D4, D5, D6, D10, D14}

POStemp(playtennnis) = {null}

POShumidity(playtennnis) = {null}

=> Chọn thuộc tính chia chính là Wind, chia 2 bảng quyết định T20 và T21 (brand rain have node Wind)

Bảng T₂₀:

U1	Temp	Humidity	Wind	Playtennis
D4	Mild	High	Weak	Yes
D5	Cool	Normal	Weak	Yes
D10	Mild	Normal	Weak	Yes

 

Bảng T₂₁:

U1	Temp	Humidity	Wind	Playtennis
D6	Cool	Normal	Strong	No
D14	Mild	High	Strong	No

=> T20 là hệ thuần khiết vì các đối tượng có Wind = Weak đều cho kết quả PlayTennis là Yes (brand weak have leaf YES)

=> T21 là hệ thuần khiết vì các đối tượng có Wind = Strong đều cho kết quả PlayTennis là No (brand strong have leaf  NO)

             rain

                \ 

               wind

              /        \

     weak       strong 

       /                \

YES            NO

Do các hệ quyết định cuối cùng đều là các hệ thuần khiết nên thuật toán xây dựng cây quyết định RDT dừng.

                                  Outlook

           /                          |                            \

overcast                      sunny                        rain

       /                                |                                \ 

    YES                    Humidity                       wind

                                    /    \                            /        \

                               high    normal           weak       strong 

                                /            \                     /                \

                            NO            YES          YES            NO

Ví dụ 2Armatage Shanks

Cho tập dữ liệu huấn luyện như sau :

RID	age	income	student	credit_rating	Class: bugs_computer
1	youth	high	no	fair	no
2	youth	high	no	excellent	no
3	middle_aged	high	no	fair	yes
4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no
7	middle_aged	low	yes	excellent	yes
8	youth	medium	no	fair	no
9	youth	low	yes	fair	yes
10	senior	medium	yes	fair	yes
11	youth	medium	yes	excellent	yes
12	middle_aged	medium	no	excellent	yes
13	middle_aged	high	yes	fair	yes
14	senior	medium	no	excellent	no

Giải

POSage(bugs_computer) = {D3, D7, D12, D13}

POSincome(income) =  POSincome(student) = POS(credit_rating) = {null}

=> Chọn age làm thuộc tính chính và xây dựng các bảng quyết định (chọn age làm root)

T0: (middle_aged)

3

middle_aged

high

no

fair

yes

7

middle_aged

low

yes

excellent

yes

12	middle_aged	medium	no	excellent	yes
13	middle_aged	high	yes	fair	yes

T1: (youth)

1	youth	high	no	fair	no
2	youth	high	no	excellent	no

8	youth	medium	no	fair	no
9	youth	low	yes	fair	yes

11

youth

medium

yes

excellent

yes

T2: (senior)

4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no

10

senior

medium

yes

fair

yes

14

senior

medium

no

excellent

no

Xét T0:

 Toàn bộ đội tượng đều trả về kết quả YES nên đây là hệ thuần khiết (nhánh middle_aged sẽ trả về node lá YES)

Xét T1:

POSincome(bugs_computer) = {D1, D2, D9}

POSstudent(bugs_computer) = {D1, D2, D8, D9, D11}

POScredit_rating(bugs_computer) = {null}

=> Chọn student làm thuộc tính chính, và xây dựng các bản quyết định (node student)

T10: (no)

1	youth	high	no	fair	no
2	youth	high	no	excellent	no

8

youth

medium

no

fair

no

T11: (yes)

    

9

youth

low

yes

fair

yes

11

youth

medium

yes

excellent

yes

Xét T10:    

- Toàn bộ đối tượng đều trả về kết quả no => Đây là hệ thuần khiết (node student có node lá NO)

Xét T11:    

- Toàn bộ đối tượng đều trả về kết quả yes => Đây là hệ thuần khiết (node student có node lá ÝES)

Xét T2: 

POSincome(bug_computer) = {null}

POSstudent(bugs_computer) = {null}

POScredit_rating(bugs_computer) = {D4, D5, D6, D10, D14}

=> Chọn credit_card làm thuộc tính chính, và xây dựng các bản quyết định (node credit_card)

T20:

4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes

10

senior

medium

yes

fair

yes

T21:

6

senior

low

yes

excellent

no

14

senior

medium

no

excellent

no

Xét T20:    

- Toàn bộ đối tượng đều trả về kết quả yes => Đây là hệ thuần khiết (nhánh fair có leaf YES)

Xét T21:    

- Toàn bộ đối tượng đều trả về kết quả no => Đây là hệ thuần khiết (nhánh excellent có leaf  NO)

                                    Age

           /                          |                            \

Middle_aged              youth                    senior

       /                                |                                \ 

    YES                    Student                    credit_card

                                    /    \                            /    \

                               no        yes                fair       excellent 

                                /            \                     /            \

                            NO            YES          YES            NO