Máy học và mạng neural - Bài 03 – Cây quyết định Decision tree learning
Cho tập các dữ liệu lưu trữ 10 ngày cuối tuần mà Mike đã làm gì như sau. Trong đó
thời tiết (Weather) có 3 thuộc tính, Cha me (Parents) có hoặc không có nhà và Tiền
(Money) có nhiều(rich) hoặc ít (poor). Có 4 lớp là xem phim (Cinema), chơi Tennis,
mua sắm (Shopping) hoặc ở nhà (Stay in). Hãy vẽ cây quyết định cho tập huấn luyện
trên (chỉ cần vẽ cây cho thuộc tính thứ nhất và thuộc tính thứ hai cho giá trị đầu tiên
cửa thuộc tính thứ nhất). (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến
kết luận)
36 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 2476 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Máy học và mạng neural - Bài 03 – Cây quyết định Decision tree learning, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
07/08/2013
1
Bài 03 – Cây quyết định
Decision tree learning
1
Nội dung
Định nghĩa, giới thiệu
Biểu diễn mô hình/giả thuyết bằng DT.
Khả năng ứng dụng của DT.
Giải thuật học cơ bản.
Các vấn đề học với cây quyết định
Thuật toán ID3.
Các vấn đề trong DT.
Giới thiệu C4.5.
2
07/08/2013
2
Định Nghĩa
Cây Quyết định là một cây phân lớp
Nút nội : là nút thử nghiệm
Nút lá : nút phân loại ( phân lớp )
Cây phân lớp bằng cách lọc mẫu nhập từ trên xuống
Kết quả là phân biệt và đầy đủ
3
Định Nghĩa
Cây quyết định có thể khác nhau trên một số khía
cạnh :
– Nút thử nghiệm có thể là đơn biến hay đa biến
– Có thể có 2 hoặc hơn 2 kết quả đầu ra
– Các đặc trưng hoặc thuộc tính có thể là phân loại hoặc là số
– Đầu ra (cuối cùng) có thể có hai hoặc nhiều lớp
4
07/08/2013
3
Định Nghĩa
Ví dụ
5
Giới thiệu
Cây quyết định là phương pháp suy luận qui nạp
được sử dụng và thực hành rộng rãi nhất.
Là một phương pháp xấp xỉ hàm mục tiêu của tập các
giá trị rời rạc.
Cách biểu diễn các hàm học được
– Cây quyết định hoặc
– Tập các luật if-then mà người có thể đọc được.
6
07/08/2013
4
Giới thiệu (tt)
Các phương pháp học được sử dụng rộng rãi:
– ID3
– ASSISTANT
– C4.5
Nhiệm vụ của các phương pháp học:
– Tìm kiếm không gian giả thuyết hoàn chỉnh
– Loại bỏ khó khăn của không gian giả thuyết có giới hạn.
7
Cách biểu diễn cây quyết định
Cây quyết định phân loại các thể hiện bằng cách sắp xếp
chúng vào một cây từ gốc đến lá
– Mỗi node trong cây là một thuộc tính của các thể hiện
– Mỗi nhánh là một giá trị có thể có của các thuộc tính này
Cây quyết định được sử dụng trong phân lớp bằng cách
duyệt từ nút gốc của cây cho đến khi đụng đến nút lá, từ
đó rút ra lớp của đối tượng cần xét
8
07/08/2013
5
Mô hình cây quyết định
Ví dụ 1: Playing Tennis.
Day Outlook Temp. Humidity Wind Play
tennis
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cold Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rain Mild High Strong No
9
Decision Tree for PlayTennis
Outlook
Sunny Overcast Rain
Humidity
High Normal
Wind
Strong Weak
No Yes
Yes
Yes No
10
07/08/2013
6
Decision Tree for PlayTennis
Outlook
Sunny Overcast Rain
Humidity
High Normal
No Yes
Each internal node tests an attribute
Each branch corresponds to an
attribute value node
Each leaf node assigns a classification
11
No
Decision Tree for PlayTennis
Outlook
Sunny Overcast Rain
Humidity
High Normal
Wind
Strong Weak
No Yes
Yes
Yes No
Outlook Temperature Humidity Wind PlayTennis
Sunny Hot High Weak ?
12
07/08/2013
7
Decision Tree for Conjunction
Outlook
Sunny Overcast Rain
Wind
Strong Weak
No Yes
No
Outlook=Sunny Wind=Weak
No
13
Decision Tree for Disjunction
Outlook
Sunny Overcast Rain
Yes
Outlook=Sunny Wind=Weak
Wind
Strong Weak
No Yes
Wind
Strong Weak
No Yes
14
07/08/2013
8
Decision Tree for XOR
Outlook
Sunny Overcast Rain
Wind
Strong Weak
Yes No
Outlook=Sunny XOR Wind=Weak
Wind
Strong Weak
No Yes
Wind
Strong Weak
No Yes
15
Decision Tree
Outlook
Sunny Overcast Rain
Humidity
High Normal
Wind
Strong Weak
No Yes
Yes
Yes No
decision trees represent disjunctions (or) of conjunctions (and)
(Outlook=Sunny Humidity=Normal)
(Outlook=Overcast)
(Outlook=Rain Wind=Weak) 16
07/08/2013
9
Mô hình cây quyết định
Ví dụ 2: Ngồi bàn đợi tại một restaurant:
Alternate: Có restaurant nào cạnh đây không?
Bar: Liệu có khu vực quầy bar có thể ngồi không?
Fri/Sat: hôm nay là thứ 8 hay thứ 7?
Hungry: có đang đói không?
Patrons: Số người trong restaurant (None, Some, Full)
Price: khoảng giá ($, $$, $$$)
Raining: ngoài trời có mưa không?
Reservation: đã đặt trước chưa?
Type: loại restaurant (French, Italian, Thai, Burger)
WaitEstimate: thời gian chờ đợi (0-10, 10-30, 30-60, >60)
17
Mô hình cây quyết định
Ví dụ 2: Ngồi bàn đợi tại một restaurant:
18
07/08/2013
10
Mô hình cây quyết định
Ví dụ 2: Ngồi bàn đợi tại một restaurant:
19
– D = {t1, , tn} trong đó ti=
– Cơ sở dữ liệu gồm có quan hệ {A1, A2, , Ah}
– Các lớp C={C1, ., Cm}
Một cây là cây quyết định (hay Cây phân lớp) của D nếu:
– Mỗi nút trong được gán nhãn thuộc tính Ai
– Mỗi cung được gán nhãn một mệnh đề thuộc tính-giá trị với thuộc tính là
nhãn nút xuất phát của cung.
– Mỗi nút lá được gán nhãn Cj.
Mô hình cây quyết định
20
07/08/2013
11
Khả năng biểu diễn
Cây quyết định có khả năng dùng để biểu diễn bất cứ hàm nào.
E.g. hàm Boolean:
Với một cây quyết định nhất quán với tập mẫu huấn luyện thì mỗi input,
output của hàm tương ứng với một đường đi trong cây. Nhưng cũng có thể
khả năng khái quát hoá không cao đối với các ví dụ mới chưa biết.
Mô hình cây quyết định
21
Các vấn đề thường dùng cây quyết định để giải
quyết
Các thể hiện được biểu diễn dưới dạng cặp thuộc tính – giá trị
– Các thuộc tính này thường là cố định (vd: nhiệt độ) và các giá trị của nó
cũng cố định (vd: nóng)
– Thuộc tính thường là các giá trị rời rạc nhưng cũng cho phép xử lý trên
các giá trị thực (phải mở rộng các thuật toán cơ bản).
Các hàm chức năng (target-functions) có các giá trị đầu ra là
rời rạc
– Trong ví dụ trên có 2 phân lớp là Yes và No
22
07/08/2013
12
Các vấn đề thường dùng cây quyết định để giải
quyết
Có thể yêu cầu biểu diễn dưới dạng biểu thức luận lý
Dữ liệu huấn luyện có thể có lỗi.
– Cây quyết định là một phương pháp xử lý tốt với các trường hợp lỗi
(lỗi trong phân lớp và lỗi trong giá trị thuộc tính)
Dữ liệu huấn luyện có thể bị khuyết giá trị
Ứng dụng:
– Classification.
– Medical diagnosis
– Credit risk analysis
– Object classification for robot manipulator (Tan 1993)
23
Giải thuật học cơ bản
Hầu hết các giải thuật học trên cây quyết định là các biến thể
của giải thuật học top-down, tìm kiếm tham lam (greedy
search)
Giải thuật học gồm các bước như sau:
– Cây được thiết lập từ trên xuống dưới
– Rời rạc hóa các thuộc tính dạng phi số
– Các mẫu huấn luyện nằm ở gốc của cây
– Chọn một thuộc tính để phân chia thành các nhánh. Thuộc tính
được chọn dựa trên độ đo thống kê hoặc độ đo heuristic
– Tiếp tục lặp lại việc xây dựng cây quyết định cho các nhánh
24
07/08/2013
13
Giải thuật học cơ bản
Điều kiện dừng
– Tất cả các mẫu rơi vào một nút thuộc về cùng một lớp (nút lá)
– Không còn thuộc tính nào có thể dùng để phân chia mẫu nữa
– Không còn lại mẫu nào tại nút
25
Lựa chọn thuộc tính phân lớp
Độ đo để lựa chọn thuộc tính:
Thuộc tính được chọn là thuộc tính có lợi nhất cho quá trình phân lớp
(tạo ra cây nhỏ nhất)
Có 2 độ đo thường dùng
– Độ lợi thông tin (Information gain)
• Giả sử tất cả các thuộc tính dạng phi số
• Có thể biến đổi để áp dụng cho thuộc tính số
• Xác định số bits tối thiểu của thông tin cần để mã hóa phân loại
một thành viên tùy ý của S
– Chỉ số Gini (Gini index)
• Giả sử tất cả các thuộc tính dạng số
• Giả sử tồn tại một vài giá trị có thể phân chia giá trị của từng thuộc
tính
• Có thể biến đổi để áp dụng cho thuộc tính phi số
26
07/08/2013
14
Một số vấn đề với DT
Không gian tìm kiếm khổng lồ.
Lựa chọn thuộc tính để phân hoạch ntn?
Cách phân hoạch ra sao?
Quản lý cấu trúc cây ntn?
Tiêu chuẩn dừng?
Các vấn đề với dữ liệu huấn luyện.
Các vấn đề với thuộc tính dữ liệu.
Over-fitting và nhu cầu đơn giản hoá mô hình.
27
Các vấn đề học với cây quyết định
Chọn lựa kiểu cho thử nghiệm
Dùng Độ lợi thông tin (information gain) để chọn thử nghiệm
Thuộc tính không phải nhị phân
(non-binary)
28
07/08/2013
15
Chọn lựa kiểu cho thử nghiệm
– Thông thường có n thuộc tính
– Thuộc tính nhị phân
• Giá trị thuộc tính ở nút thử nghiệm là 0 hoặc 1
– Thuộc tính phân loại ( không phải nhị phân )
• Chia giá trị thuộc tính vào các tập con phân biệt và đầy đủ
Các vấn đề học với cây quyết định
29
Các vấn đề học với cây quyết định
Ví dụ chọn lựa kiểu cho thử nghiệm
30
07/08/2013
16
Dùng Độ lợi thông tin (information gain) để chọn thử
nghiệm
– Vấn đề : chọn thứ tự các thử nghiệm
– Với các thuộc tính phân loại và số => chọn giá trị thích hợp cho thử
nghiệm
– Giải pháp : giảm tối đa entropy (đo tính thuần khiết)
Các vấn đề học với cây quyết định
31
Thuộc tính không phải nhị phân (non-binary)
– Vẫn sử dụng kỹ thuật trên
– Đặt ngưỡng với miền giá trị thực
– Chọn gom nhóm phân loại với những giá trị phân loại
Các vấn đề học với cây quyết định
32
07/08/2013
17
Mạng tương đương với cây Quyết định
Cây Quyết định luận lý đơn biến cài đặt hàm DNF (disjunctive
normal form) sẽ tương đương với mạng neuron truyền thẳng 2
lớp
33
Giải thuật ID3
Lựa chọn thuộc tính phân lớp dựa trên độ lợi thông tin
(Information gain)
Thuộc tính nào là tốt nhất?
Là giải thuật tham ăn (greedy) mở rộng cây từ gốc đến ngọn
A1=?
True False
[21+, 5-] [8+, 30-]
[29+,35-] A2=?
True False
[18+, 33-] [11+, 2-]
[29+,35-]
34
07/08/2013
18
Độ đo sự đồng nhất của mẫu
s
s
s
s
ppSentropy i
m
i
i
i
m
i
i 2
1
2
1
loglog)(
pi: tần suất xuất hiện của các mẫu trong lớp Ci với i = {1, ,
m}
S: số lượng tập huấn luyện
Si: số các mẫu của S nằm trong lớp Ci
Thông tin cần biết để phân lớp một mẫu
35
Một số lưu ý
Trong trường hợp phân lớp
nhị phân:
– Entropy = 0: khi tất cả thuộc về
1 lớp
– Entropy = 1: số lượng các ví dụ
ở cả hai lớp bằng nhau
– Còn lại: 0<entropy<1
ppppSentropy 22 loglog)(
36
07/08/2013
19
Độ lợi thông tin
)()(A),G(
)(
v
AValuesv
v
SEntropy
S
S
SEntropyS
Thuộc tính A có các giá trị {a1, a2, ,an}
Dùng thuộc tính A để phân chia tập huấn luyện thành n tập
con {S1, S2, , Sn}
Độ lợi thông tin dựa trên phân nhánh bằng thuộc tính A:
Tại mỗi cấp, chúng ta chọn thuộc tính có độ lợi lớn nhất để
phân nhánh cây hiện tại
37
Information Gain
Gain(S,A): expected reduction in entropy due to sorting S on
attribute A
A1=?
True False
[21+, 5-] [8+, 30-]
[29+,35-] A2=?
True False
[18+, 33-] [11+, 2-]
[29+,35-]
Gain(S,A)=Entropy(S) - vvalues(A) |Sv|/|S| Entropy(Sv)
Entropy([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64
= 0.99
s
s
s
s
ppSentropy i
m
i
i
i
m
i
i 2
1
2
1
loglog)(
38
07/08/2013
20
Information Gain
A1=?
True False
[21+, 5-] [8+, 30-]
[29+,35-]
Entropy([21+,5-]) = 0.71
Entropy([8+,30-]) = 0.74
Gain(S,A1)=Entropy(S)
-26/64*Entropy([21+,5-])
-38/64*Entropy([8+,30-])
=0.27
Entropy([18+,33-]) = 0.94
Entropy([8+,30-]) = 0.62
Gain(S,A2)=Entropy(S)
-51/64*Entropy([18+,33-])
-13/64*Entropy([11+,2-])
=0.12
A2=?
True False
[18+, 33-] [11+, 2-]
[29+,35-]
39
Ví dụ
Day Outlook Temp. Humidity Wind Play?
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cold Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rain Mild High Strong No
40
07/08/2013
21
Ví dụ
940.0
14
5
log
14
5
14
9
log
14
9
)5,9()S,Entropy(S
2221
Entropy
Ta có
– S = 14
– m = 2
– C1 = “Yes”, C2 = “No”
– S1 = 9, S2 = 5
41
Ví dụ
985.0
7
4
log
7
4
7
3
log
7
3
22
Gain(S,Humidity)
=0.940 – (7/14)*0.985 – (7/14)*0.592
=0.151
E=0.985 E=0.592
Humidity
Normal
[3+, 4-]
High
[6+, 1-]
592.0
7
1
log
7
1
7
6
log
7
6
22
42
07/08/2013
22
Ví dụ
811.0
8
2
log
8
2
8
6
log
8
6
22
Gain(S,Wind)
=0.940 – (8/14)*0.811 – (6/14)*1.000
=0.048
E=0.811 E=1.000
Wind
Strong
[6+, 2-]
Weak
[3+, 3-]
000.1
6
3
log
6
3
6
3
log
6
3
22
43
Ví dụ
Gain(S,Temperature) = 0.029
Temperature
Mild
[2+, 2-]
Hot
[4+, 2-] [3+, 1-]
Cold
44
07/08/2013
23
Ví dụ
Gain(S,Outlook)
=0.940 – (5/14)*0.971
– (4/14)*0.0 – (5/14)*0.0971
=0.247
E=0.971 E=0.000
Outlook
Overcast
[2+, 3-]
Sunny
[4+, 0-]
E=0.971
[3+, 2-]
Rain
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature) = 0.029
45
Ví dụ
??? ???
Outlook
Yes
Sunny Overcast Rain
Gain(Ssunny, Humidity)
= 0.971 – (3/5)*0.0 – (2/5)*0.0 = 0.971
Gain(Ssunny, Temperature)
= 0.971 – (2/5)*0.0 – (2/5)*1.0 – (1/5)*0.0 = 0.571
Gain(Ssunny, Wind)
= 0.971 – (2/5)*1.0 – (3/5)*0.918 = 0.02
Which attribute should be tested here?
46
07/08/2013
24
ID3 Algorithm
Outlook
Sunny Overcast Rain
Humidity
High Normal
Wind
Strong Weak
No Yes
Yes
Yes No
[D3,D7,D12,D13]
[D8,D9,D11] [D6,D14] [D1,D2]
[D4,D5,D10]
47
Biến đổi cây quyết định thành luật
Biểu diễn tri thức dưới dạng luật IF-THEN
Mỗi luật tạo ra từ mỗi đường dẫn từ gốc đến lá
Mỗi cặp giá trị thuộc tính dọc theo đường dẫn tạo nên phép kết
(phép AND – và)
Các nút lá mang tên của lớp
48
07/08/2013
25
Biến đổi cây quyết định thành luật
Wind Humidity
Outlook
Yes No
Yes
Sunny Overcast Rain
Yes No
High Normal Strong Weak
R1: If (Outlook=Sunny) (Humidity=High) Then Play=No
R2: If (Outlook=Sunny) (Humidity=Normal) Then Play=Yes
R3: If (Outlook=Overcast) Then Play=Yes
R4: If (Outlook=Rain) (Wind=Strong) Then Play=No
R5: If (Outlook=Rain) (Wind=Weak) Then Play=Yes
49
Ưu và khuyết điểm của ID3
Không gian giả thuyết:
là một tập hợp các cây
quyết định
50
07/08/2013
26
Ưu và khuyết điểm của ID3
Ưu điểm:
– Không gian giả thuyết này là đầy đủ (gồm các giá trị rời rạc
hữu hạn: Yes/ No) giả thuyết chắc chắn thuộc về không
gian này
– Tại mỗi bước, ID3 xét hết tất cả các mẫu huấn luyện, đưa
ra kết quả dựa vào thống kê kết quả ít bị lỗi
– Dễ xây dựng
– Phân lớp mẫu mới nhanh
– Dễ dàng diễn giải cho các cây kích thước nhỏ
51
Ưu và khuyết điểm của ID3
Khuyết điểm
– Phương pháp thực hiện của ID3 là phương pháp leo đồi đi
từ đơn giản đến phức tạp, chỉ duy trì một tình trạng giả
thuyết giả thuyết không có khả năng đại diện toàn cục
– Không quay lui (No Backtracking) cực tiểu địa phương
– Gặp tình trạng quá khớp (Overfitting)
52
07/08/2013
27
Cây quyết định học bởi ID3 từ ví dụ 2 mô hình cây
quyết định:
Nhỏ hơn cây quyết định đưa ra lúc đầu
Ví dụ Ngồi bàn đợi tại một restaurant
53
Thiên hướng quy nạp (Inductive Bias)
Vì dữ liệu huấn luyện thường hạn chế, nên thường được khái
quát hóa theo một số khía cạnh nào đóheuristic (sử dụng
inductive bias)
Inductive bias đề cập đến những giả định bổ sung (additional
assumptions) mà người học sẽ dùng để dự đoán đầu ra đúng
cho các tình huống chưa gặp phải trước đây.
• Inductive bias: thường sử dụng cho những cây quyết định nhỏ
Phân loại:
– Restriction Bias: giới hạn một số giả thuyết trong quá trình học
– Preference Bias: có sự ưu tiên cho một số giả thuyết
ID3 thuộc preference bias
54
07/08/2013
28
Occam’s razor
Thế giới vốn dĩ là đơn giản
Cách giải thích đơn giản nhất bao
phủ được toàn bộ dữ liệu là cách
hiệu quả nhất
Tại sao???
William of Ockham
(1285–1349)
55
Occam’s razor
Lí do:
– Số lượng giả thuyết ngắn, đơn giản thường ít hơn nhiều so với số lượng
các giả thuyết dài, phức tạp
– Các giả thuyết ngắn thường tránh được sự trùng hợp ngẫu nhiên
Hạn chế:
– Nếu có nhiều giả thuyết ngắn, thì cái nào là phù hợp???
– Kích thước của giả thuyết là bao nhiêu thì tốt? tùy thuộc vào cách
xác định của mỗi người có thể cho kết luận khác nhau trên cùng
một vấn đề
56
07/08/2013
29
Thiên hướng quy nạp của ID3
Ưu tiên chọn cây ngắn
Chọn cây với các thuộc tính có độ lợi thông tin lớn nhất mà
gần gốc nhất
57
Cây định danh (1)
Hair color
Lotion used
Emily
Alex
Pete
John
Sarah
Annie
Dana
Katie
blonde
red brown
No Yes
58
07/08/2013
30
Cây định danh (2)
Hair color
Weight
Alex
Annie
Blonde Red Brown
Height
Short Average
Tall
Weight
Dana
Pete
Sarah
Hair color
Blonde Red Brown
Katie
Emily John
Average
Heavy
Light
Average
Heavy
Light
59
Cây định danh (1)
Hair color
Lotion used
Emily
Alex
Pete
John
Sarah
Annie
Dana
Katie
blonde
red brown
No Yes
Chọn cây 1
60
07/08/2013
31
Cây định danh (3)
Hair color
Weight
Annie
Blonde Red Brown
Height
Short Average
Tall
Weight
Dana
Pete
Sarah
Hair color
Blonde Red Brown
Katie
Emily John
Average
Heavy
Light
Gain = 0.97
Gain =
0.85
61
Cây định danh (4)
Hair color
Weight
Annie
Blonde Red Brown
Height
Short
Heavy
Tall
Weight
Dana
Pete
Sarah
Hair color
Blonde Red Brown
Katie
Emily John
Average
Average
Light
Gain = 0.85
Gain =
0.95
62
07/08/2013
32
Cây định danh (3)
Hair color
Weight
Annie
Blonde Red Brown
Height
Short Average
Tall
Weight
Dana
Pete
Sarah
Hair color
Blonde Red Brown
Katie
Emily John
Average
Heavy
Light
Gain = 0.97
Gain = 0.85
Chọn
cây 3
63
Các vấn đề trong cây quyết định
Kết hợp các thuộc tính có giá trị liên tục
Lựa chọn thuộc tính bằng độ đo thay thế
Xử lý mẫu huấn luyện với thuộc tính có giá trị khuyết
Xử lý thuộc tính với chi phí khác nhau
Tập trung cho thuật toán ID3
64
07/08/2013
33
Thuộc tính có giá trị liên tục
Thuật toán ID3 bắt buộc dùng thuộc tính có giá trị rời
rạc
– Thuộc tính đích, dùng ra quyết định
– Thuộc tính dẫn dắt quyết định
Phân chia giá trị liên tục thành các khoảng rời rạc, và
có thể đưa vào cây quyết định
Cho A là thuộc tính có giá trị liên tục, việc phân tách
tạo 2 giá trị logic Ac với:
với c là điểm phân tách
Chọn giá trị c tối ưu?
cAfalse
cAtrue
Ac
,
,
65
Giới thiệu C4.5
Là phần mềm cài đặt và cải tiến ID3, tác giả Ross
Quinlan.
Địa chỉ download (program, source code in C,
documentation):
s/c4.5/tutorial.html
Gói phần mềm WEKA (source code in JAVA):
66
07/08/2013
34
Đọc thêm
Giáo trình - chương 3.
R. Quinlan, C4.5: Programs for Machine Learning,
Morgan Kaufmann, 1993.
67
Câu hỏi ôn tập
1. cây quyết định là gì?
2. Nêu các đặc điểm của các bài toàn giải bằng cây
quyết định
3. Trình bày thuật toán học cho cây quyết định?
4. Trình bày nội dung/đặc điểm của thuật toán ID3.
5. Nêu các vấn đề và giải pháp trong học/khái quát hoá
của ID3.
6. Nêu các vấn đề và giải pháp trong xử lý thuộc tính
của ID3.
7. Ứng dụng C4.5 để giải các bài toán thực tế.
68
07/08/2013
35
Bài tập mẫu 1
69
Dùng ID3 vẽ cây quyết định khi biết tập dữ liệu training sau:
Bài tập mẫu 2
An muốn áp dụng giải thuật ID3 để xây dựng cây quyết định với tập dữ liệu
rèn luyện trên. Áp dụng các công thức tính entropy và gain, hãy giúp An xác
định thuộc tính nào (A1, A2 hay A3) là thuộc tính tốt nhất để hỏi đầu tiên
nhằm tạo ra một cây quyết định đơn giản nhất.
(Lưu ý: phải trình bày các tính toán entropy và gain để đi đến kết luận).
70
07/08/2013
36
Bài tập mẫu 3
Cho tập các dữ liệu lưu trữ 10 ngày cuối tuần mà Mike đã làm gì như sau. Trong đó
thời tiết (Weather) có 3 thuộc tính, Cha mẹ (Parents) có hoặc không có nhà và Tiền
(Money) có nhiều(rich) hoặc ít (poor). Có 4 lớp là xem phim (Cinema), chơi Tennis,
mua sắm (Shopping) hoặc ở nhà (Stay in). Hãy vẽ cây quyết định cho tập huấn luyện
trên (chỉ cần vẽ cây cho thuộc tính thứ nhất và thuộc tính thứ hai cho giá trị đầu tiên
cửa thuộc tính thứ nhất). (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến
kết luận).
71
Weekend
(Example)
Weather Parents Money Decision
(Category)
W1 Sunny Yes Rich Cinema
W2 Sunny No Rich Tennis
W3 Windy Yes Rich Cinema
W4 Rainy Yes Poor Cinema
W5 Rainy No Rich Stay in
W6 Rainy Yes Poor Cinema
W7 Windy No Poor Cinema
W8 Windy No Rich Shopping
W9 Windy Yes Rich Cinema
W10 Sunny No Rich Tennis
Các file đính kèm theo tài liệu này:
- lecture03_decisiontreelearning_4364.pdf