Bài giảng Trí tuệ nhân tạo - Nguyễn Thị Thúy Loan

192
Vương Hạo – Nhận xét
 Vương Hạo dựa vào phương pháp chia để trị
nhằm giải quyết bài toán. Mục đích là chia 
nhỏ vấn đề để giải quyết một cách độc lập và 
sau đó tổng hợp kết quả.
 Độ phức tạp của thuật toán tùy thuộc vào số
phép tuyển tồn tại trong KB.
6/8/2010 Nguyễn Thị Thúy Loan 193
Suy diễn trong logic mệnh đề
Suy diễn tiến:
Kích hoạt các luật mà vế trái thỏa trong KB. Bổ
sung phần kết luận vào KB cho đến khi tìm thấy 
kết luận cần tìm.
6/8/2010 Nguyễn Thị Thúy Loan 194
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 195
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 196
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 197
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 198
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 199
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 200
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 201
Là phương pháp biểu diễn 
tri thức bằng đồ thị
Các đối tượng Các mối liên hệ
Đỉnh Cung
Ví dụ:
Chích Chòe Hót
Tổ Cánh
Chim
là
biết
làm có
Đỉnh
Cung
Mạng ngữ nghĩa
6/8/2010 Nguyễn Thị Thúy Loan 202
Ví dụ về mạng tam giác
Nêu bài toán: Trong tam giác cho 3 yếu tố 
(không đồng thời 3 đỉnh). Tìm một yếu tố còn 
lại nào đó?
Ví dụ: Trong tam giác cho góc A, B và cạnh c. 
Tìm diện tích S?
6/8/2010 Nguyễn Thị Thúy Loan 203
Cách xây dựng:
1. Đỉnh: Có 2 loại đỉnh
a. Đỉnh hình tròn: chứa các biến hay các yếu tố 
liên quan đến cạnh và góc của tam giác.
b. Đỉnh hình chữ nhật: chứa các công thức
2. Cung: Nối giữa đỉnh hình tròn và đỉnh hình chữ
nhật cho biết biến nào nằm trong công thức nào.
Ví dụ về mạng tam giác
6/8/2010 Nguyễn Thị Thúy Loan 204
Mô hình: Trong tam giác cho các công thức
1. A + B + C = 1800
2. a*sinB = b*sinA
3. b * sinC = c * sinB
4. p = (a + b + c)/2
5. hc = a*sinB
6. S = hc*c/2
7. S = 
Trong đó: A, B, C là 3 góc trong của tam giác; a, 
b, c là 3 cạnh của tam giác.
))()(( cpbpapp 
Ví dụ về mạng tam giác
6/8/2010 Nguyễn Thị Thúy Loan 205
Xây dựng mô hình MNN
Xác định đỉnh: có 16 đỉnh trong đó có 9 đỉnh 
hình tròn (9 biến!?) và 7 đỉnh hình chữ nhật (7 
công thức). 
6/8/2010 Nguyễn Thị Thúy Loan 206
A + B + C – 180=0
a*sinB – b*sinA=0 hc – a*sinB=0 b*sinC – c*sinB=0
S – hc*c/2=0p – (a+b+c)/2=0 S– =0))()(( cpbpapp 
A B C
a b hc c
p S
6/8/2010 Nguyễn Thị Thúy Loan 207
Cơ chế suy diễn MNN
1. Kích hoạt các biến đã cho ban đầu.
2. Các biến được kích hoạt sẽ truyền động theo 
cung dẫn đến các đỉnh khác.
3. Đỉnh hình chữ nhật được kích hoạt khi có n – 1 
cung trong số n cung có liên hệ với nó được 
kích hoạt.
4. Đỉnh hình tròn được kích hoạt khi đỉnh hình chữ
nhật có cung liên hệ với nó được kích hoạt.
6/8/2010 Nguyễn Thị Thúy Loan 208
A + B + C – 180=0
a*sinB – b*sinA=0 hc – a*sinB=0 b*sinC – c*sinB=0
S – hc*c/2=0p – (a+b+c)/2=0 S– =0))()(( cpbpapp 
A B C
a b hc c
p S
 c c/
6/8/2010 Nguyễn Thị Thúy Loan 209
MNN – Một số câu hỏi
1. Khi nào thất bại?
2. Làm thế nào để tìm được tất cả các lời giải?
3. Lời giải ngắn nhất (số công thức được áp 
dụng là ít nhất)?
ThS. Nguyễn Thị Thúy Loan
Chương IV
PHÂN LỚP VÀ DỰ 
ĐOÁN
6/8/2010 Nguyễn Thị Thúy Loan 211
NỘI DUNG
 Phân lớp và dự đoán?
 Các vấn đề về phân lớp và dự đoán 
 Quy nạp trên cây quyết định
 Các phương pháp phân lớp khác
6/8/2010 Nguyễn Thị Thúy Loan 212
Phân lớp là gì?Dự đoán là gì?
 Có thể dùng phân lớp và dự đoán để xác lập 
mô hình nhằm mô tả các lớp quan trọng hay 
dự đoán khuynh hướng dữ liệu trong tương lai 
 Phân lớp (classification): Tạo ra bộ phân lớp/ 
mô hình.
 Dự đoán (prediction): Dựa vào bộ phân lớp để
dự đoán nhãn của các mẫu chưa biết nhãn.
6/8/2010 Nguyễn Thị Thúy Loan 213
Phân lớp dữ liệu là tiến trình có 2 bước
 Huấn luyện: Dữ liệu huấn luyện được 
phân tích bởi thuật toán phân lớp (có thuộc 
tính nhãn lớp) để tạo ra bộ phân lớp.
 Phân lớp: Dữ liệu kiểm tra được dùng để 
ước lượng độ chính xác của bộ phân lớp. 
Nếu độ chính xác là chấp nhận được thì có
thể dùng bộ phân lớp để phân lớp các mẫu 
dữ liệu mới. 
Phân lớp là gì?Dự đoán là gì?
6/8/2010 Nguyễn Thị Thúy Loan 214
Phân lớp là gì?Dự đoán là gì?
6/8/2010 Nguyễn Thị Thúy Loan 215
 Độ chính xác (accuracy) của bộ phân lớp 
trên tập kiểm tra cho trước là phần trăm 
của các mẫu trong tập kiểm tra được bộ
phân lớp xếp lớp đúng
sampletest ofnumber total
sampletest classifiedcorrectly 
 Accuracy 
Phân lớp là gì?Dự đoán là gì?
6/8/2010 Nguyễn Thị Thúy Loan 216
Chuẩn bị dữ liệu
 Làm sạch dữ liệu
o Nhiễu
o Thiếu giá trị
 Phân tích liên quan (chọn đặc trưng)
o Các thuộc tính không liên quan
o Các thuộc tính dư thừa
 Biến đổi dữ liệu 
So sánh các phương pháp 
phân lớp 
 Độ chính xác của dự đoán: khả năng bộ
phân lớp dự đoán đúng dữ liệu chưa biết 
trước nhãn
 Tính bền vững: khả năng của bộ phân lớp 
thực hiện dự đoán đúng với dữ liệu nhiễu 
hay thiếu giá trị
 Tính kích cỡ (scalability): khả năng tạo bộ
phân lớp hiệu quả với số lượng dữ liệu lớn
 Khả năng diễn giải: bộ phân lớp cung cấp tri 
thức có thể hiểu được
6/8/2010 Nguyễn Thị Thúy Loan 218
CÂY QUYẾT ĐỊNH
6/8/2010 Nguyễn Thị Thúy Loan 219
Cây quyết định
Cây quyết định là cấu trúc cây sao cho:
 Mỗi nút trong ứng với một phép kiểm tra 
trên một thuộc tính
 Mỗi nhánh biểu diễn kết quả phép kiểm tra
 Các nút lá biểu diễn các lớp hay các phân 
bố lớp
 Nút cao nhất trong cây là nút gốc.
6/8/2010 Nguyễn Thị Thúy Loan 220
Ví dụ
Cây quyết định: có mua computer? Dựa 
vào các thuộc tính tuổi, sinh viên, uy tín.
6/8/2010 Nguyễn Thị Thúy Loan 221
Sườn chung về quy nạp 
trên cây quyết định
6/8/2010 Nguyễn Thị Thúy Loan 222
1. Chọn thuộc tính “tốt nhất” theo một độ đo chọn lựa cho 
trước
2. Mở rộng cây bằng cách thêm các nhánh mới cho từng giá
trị thuộc tính
3. Sắp xếp các ví dụ học vào nút lá
4. Nếu các ví dụ được phân lớp rõ thì Stop ngược lại lặp lại 
các bước 1-4 cho mỗi nút lá
5. Tỉa các nút lá không ổn định
Headache Temperature Flu
e1 yes normal no
e2 yes high yes
e3 yes very high yes
e4 no normal no
e5 no high no
e6 no very high no
Temperature
yes
Headache
normal
high very high
Headacheno
no yes no
yes
{e2} no{e5}
yes
{e3}
no
{e6}
{e1, e4}
{e2, e5} {e3,e6}
6/8/2010 Nguyễn Thị Thúy Loan 223
Chiến lược cơ bản
 Bắt đầu từ nút đơn biểu diễn tất cả các mẫu 
 Nếu các mẫu thuộc về cùng một lớp, nút trở
thành nút lá và được gán nhãn bằng lớp đó
 Ngược lại, dùng độ đo thuộc tính để chọn 
thuộc tính sẽ phân tách tốt nhất các mẫu 
vào các lớp
 Một nhánh được tạo cho từng giá trị của 
thuộc tính được chọn và các mẫu được 
phân hoạch theo 
 Dùng đệ quy cùng một quá trình để tạo cây 
quyết định 
 Tiến trình kết thúc chỉ khi bất kỳ điều kiện 
nào sau đây là đúng
o Tất cả các mẫu cho một nút cho trước đều 
thuộc về cùng một lớp. 
o Không còn thuộc tính nào mà mẫu có thể dựa 
vào để phân hoạch xa hơn.
o Không còn mẫu nào cho nhánh 
test_attribute = ai
Chiến lược cơ bản
Bảng dữ liệu huấn luyện
Day Outlook Temp Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No 6/8/2010 Nguyễn Thị Thúy Loan 226
Cây quyết định chơi Tennis
temperature
sunny rain o’cast
{D9} {D5, D6} {D7}
outlook outlookwind
cool hot mild
{D5, D6, D7, D9} {D1, D2, D3, D13} {D4, D8, D10, D11,D12, D14}
true false
{D2} {D1, D3, D13}
true false
{D5} {D6}
wind
high normal
{D1, D3} {D3}
humidity
sunny rain o’cast
{D1} {D3}
outlook
sunny o’cast rain
{D8, D11} {D12} {D4, D10,D14}
true false
{D11} {D8}
windyes yes
no yes
yesno null
yes
no yes
high normal
{D4, D14} {D10}
humidity
yes
true false
{D14} {D4}
wind
no yes
noyes
6/8/2010 Nguyễn Thị Thúy Loan 227
Cây quyết định đơn giản
sunny o’cast rain
{D1, D2, D8 {D3, D7, D12, D13} {D4, D5, D6, D10, D14} 
D9, D11}
outlook
high normal
{D1, D2, D8} {D9, D10}
humidity
no yes
yes
true false
{D6, D14} {D4, D5, D10}
wind
no yes
Cây sẽ đơn giản hơn nếu “outlook” được chọn làm gốc.
Cách chọn thuộc tính tốt để tách nút quyết định?
Thuộc tính nào là tốt nhất 
[29+, 35 -]
[21+, 5-] [8+, 30 -]
A1 = ?
[29+, 35 -]
[18+, 33-] [11+, 2-]
A2 = ?
 Nút quyết định S có 29 mẫu thuộc lớp cộng (+) 
và 35 mẫu thuộc lớp trừ (-), ta ký hiệu là [29+, 
35-]
 Nếu các thuộc tính A1 và A2 (mỗi thuộc tính có 2 
giá trị) tách S thành các nút con với tỷ lệ của 
mẫu dương và mẫu âm như sau, thuộc tính nào 
là tốt hơn?
6/8/2010 Nguyễn Thị Thúy Loan 229
Độ đo V(Quinlan)
6/8/2010 Nguyễn Thị Thúy Loan 230
Outlook(O):
V(O=Sunny) = (2/5,3/5)
V(O=Overcast)=(4/4,0/4)=(1,0)
V(O=Rain)=(3/5,2/5)
Temp(T):
V(T=Hot) = (2/4,2/4)
V(T=Cool)=(3/4,1/4)
V(T=Mild)=(4/6,2/6)
Humidity(H):
V(H=High) = (3/7,4/7)
V(H=Normal)=(6/7,1/7)
Wind(W):
V(W=Weak) = (6/8,2/8)
V(W=Strong)=(3/6,3/6)
Day Outloook Temp Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
 Chọn Outlook vì có
nhiều vectơ đơn vị nhất.
6/8/2010 Nguyễn Thị Thúy Loan 231
Độ đo V
{D1, D2, ..., D14} [9+, 5-]
Outlook
Sunny Overcast Rain
{D1, D2, D8, D9, D11}
[2+, 3-]
{D3, D7, D12, D13}
[4+, 0-]
{D4, D5, D6, D10, D14}
[3+, 2-]
? Yes ?
Cây quyết định 
cuối cùng
Sunny Overcast Rain
{D1, D2, D8 {D3, D7, D12, D13} {D4, D5, D6, D10, D14} 
D9, D11}
Outlook
high normal
{D1, D2, D8} {D9, D10}
Humidity
no yes
yes
Strong Weak
{D6, D14} {D4, D5, D10}
Wind
no yes
Từ cây ta có 5 luật:
1.If Outlook = Overcast then Yes
2.If Outlook = Sunny and Humidity = High then No
3.If Outlook = Sunny and Humidity = Normal then Yes
4.If Outlook = Rain and Wind = Strong then No
5.If Outlook = Rain and Wind= Weak then Yes
Day 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
4 Mild Yes
5 Cool Normal Weak Yes
6 Cool Normal Strong
D10 Mild Nor al eak Yes
D14 ild High Strong No
6/8/2010 Nguyễn Thị Thúy Loan 233
Entropy
 Entropy đặc trưng độ hỗn tạp (tinh khiết) 
của tập bất kỳ các ví dụ.
 S là tập các mẫu thuộc lớp âm và lớp 
dương
 P là tỷ lệ các mẫu thuộc lớp dương trong S
 p là tỷ lệ các mẫu thuộc lớp âm trong S
Entropy(S) = -p log2p -p log2p 
6/8/2010 Nguyễn Thị Thúy Loan 234
Ví dụ
Từ 14 mẫu của bảng Play-Tennis, 9 thuộc 
lớp dương và 5 mẫu âm (ký hiệu là [9+, 5-])
Entropy([9+, 5-] ) = 
- (9/14)log2(9/14) - (5/14)log2(5/14)
= 0.940
6/8/2010 Nguyễn Thị Thúy Loan 235
Lưu ý: 
1. Entropy là 0 nếu tất cả các thành viên của S 
đều thuộc về cùng một lớp. Ví dụ, nếu tất cả
các thành viên đều thuộc về lớp dương thì :
Entropy(S) = -N/N. log2(N/N) - 0 = -1.0 – 0 = 
0 (N là số mẫu).
2. Entropy là 1 nếu tập hợp chứa số lượng 
bằng nhau các thành viên thuộc lớp dương 
và lớp âm. Nếu các số này là khác nhau, 
entropy sẽ nằm giữa 0 và 1.
Ví dụ
6/8/2010 Nguyễn Thị Thúy Loan 236
INFORMATION GAIN 
(CÂY ĐỊNH DANH)
Information Gain 
Ta định nghĩa độ đo information gain, phản 
ánh mức độ hiệu quả của một thuộc tính trong 
phân lớp. Đó là sự rút giảm mong muốn của 
entropy gây ra bởi sự phân hoạch các ví dụ
theo thuộc tính này.
Giá trị Value(A) là tập các giá trị có thể cho 
thuộc tính A, và Sv là tập con của S mà A nhận 
giá trị v.
)Entropy(S
S
S
Entropy(S)A)Gain(S, v
Value(A)v
v


6/8/2010 Nguyễn Thị Thúy Loan 238
Values(Wind) = {Weak, Strong}, S = [9+, 5-]
Sweak là nút con với trị “weak” là [6+, 2-] 
Sstrong là nút con với trị “strong”, là [3+, 3-] 
Gain(S, Wind) = Entropy(S) - )Entropy(S
S
S
Strong} {Weak,v
v
v

= Entropy(S) - (8/14)Entropy(Sweak)
- (6/14)Entropy(SStrong)
= 0.940 - (8/14)0.811 - (6/14)1.00
= 0.048
Information Gain 
6/8/2010 Nguyễn Thị Thúy Loan 239
239
Thuộc tính nào là phân lớp 
tốt nhất?
S:[9+, 5-]
E = 0.940
Humidity
High Normal
[3+, 4-] [6+, 1-]
E = 0.985 E = 0.592
Gain(S, Humidity)
= .940 - (7/14).985 - (7/14).592
= .151
S:[9+, 5-]
E = 0.940
Wind
Weak Strong
[6+, 2-] [3+, 3-]
E = 0.811 E = 1.00
Gain(S, Wind)
= .940 - (8/14).811 - (6/14)1.00
= .048
6/8/2010 Nguyễn Thị Thúy Loan 240
Information Gain của tất cả
các thuộc tính 
Gain (S, Outlook) = 0.246
Gain (S, Humidity) = 0.151
Gain (S, Wind) = 0.048
Gain (S, Temperature) = 0.029
Chọn
6/8/2010 Nguyễn Thị Thúy Loan 241
Bước kế tiếp trong tiến 
trình tăng trưởng trên cây 
quyết định
{D1, D2, ..., D14} [9+, 5-]
Outlook
Sunny Overcast Rain
{D1, D2, D8, D9, D11}
[2+, 3-]
{D3, D7, D12, D13}
[4+, 0-]
{D4, D5, D6, D10, D14}
[3+, 2-]
? Yes ?
6/8/2010 Nguyễn Thị Thúy Loan 242
Bước kế tiếp trong tiến 
trình tăng trưởng trên cây 
quyết định
Thuộc tính nào cần được kiểm tra?
Ssunny = {D1, D2, D3, D9, D11}
Gain(Ssunny, Humidity) = .970 - (3/5)0.0 - (2/5)0.0 = 0.970
Gain(Ssunny, Temperature) = .970 - (2/5)0.0 - (2/5)1.0 -
(1/5)0.0 = 0.570
Gain(Ssunny, Wind) = .970 - (2/5)1.0 - (3/5)0.918 = 0.019
6/8/2010 Nguyễn Thị Thúy Loan 243
Điều kiện dừng 
1. Từng thuộc tính đã được đưa vào dọc 
theo con đường trên cây.
2. Các mẫu huấn luyện ứng với nút lá có
cùng giá trị thuộc tính đích (chẳng hạn, 
chúng có entropy bằng 0).
Lưu ý: Thuật toán ID3 dùng Information 
Gain và C4.5, thuật toán được phát triển 
sau nó, dùng Gain Ratio (một biến thể
của Information Gain)
6/8/2010 Nguyễn Thị Thúy Loan 244
Thuật giải Học Quy nạp 
(ILA: Inductive Learning 
Algorithm)
6/8/2010 Nguyễn Thị Thúy Loan 245
ILA
1. Chia bảng con có chứa m mẫu thành n 
bảng con. Một bảng con ứng với một giá
trị của thuộc tính phân lớp. (Lặp lại từ 
bước 2 đến bước 8 cho mỗi bảng con).
2. Khởi tạo số lượng thuộc tính kết hợp j 
với j =1.
6/8/2010 Nguyễn Thị Thúy Loan 246
3. Với mỗi bảng con đang xét, phân chia 
các thuộc tính của nó thành một danh 
sách các thuộc tính kết hợp, mỗi thành 
phần của danh sách có j thuộc tính phân 
biệt.
ILA
6/8/2010 Nguyễn Thị Thúy Loan 247
ILA
4. Với mỗi kết hợp các thuộc tính trong 
danh sách trên, đếm số lần xuất hiện các 
giá trị cho các thuộc tính trong kết hợp 
đó ở các dòng chưa bị khóa của bảng 
đang xét nhưng nó không được xuất 
hiện cùng giá trị ở những bảng con khác. 
Chọn ra một kết hợp trong danh sách 
sao cho nó có giá trị tương ứng xuất 
hiện nhiều nhất và được gọi là
Max_combination.
6/8/2010 Nguyễn Thị Thúy Loan 248
ILA
5. Nếu Max_combination =0 thì j = j+1 quay 
lại bước 3.
6. Khóa các difng ở bảng con đang xét mà
tại đó giá trị bằng với giá trị tạo ra 
max_combination.
6/8/2010 Nguyễn Thị Thúy Loan 249
ILA
7. Thêm vào R luật mới với giả thuyết là
các giá trị tạo ra Max_combination kết 
nối các bộ này bằng phép AND, kết luận 
là giá trị của thuộc tính quyết định trong 
bảng con đang xét.
6/8/2010 Nguyễn Thị Thúy Loan 250
ILA
8. Nếu tất cả các dòng đều khóa:
o Nếu còn bảng con thì qua bảng con tiếp 
theo và quay lại bước 2.
o Ngược lại chấm dứt thuật toán.
Ngược lại thì quay lại bước 4.
6/8/2010 Nguyễn Thị Thúy Loan 251
STT Kích cỡ Màu sắc Hình dáng Quyết định
1 Vừa Xanh dương Hộp Mua
2 Nhỏ Đỏ Nón Không mua
3 Nhỏ Đỏ Cầu Mua
4 Lớn Đỏ Nón Không mua
5 Lớn Xanh lá Trụ Mua
6 Lớn Đỏ Trụ Không mua
7 Lớn Xanh lá Cầu Mua
Ví dụ minh họa ILA
6/8/2010 Nguyễn Thị Thúy Loan 252
STT Kích cỡ Màu sắc Hình dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
STT Kích cỡ Màu sắc Hình dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Ví dụ minh họa ILA
6/8/2010 Nguyễn Thị Thúy Loan 253
253
Xét bảng con 1
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 2: j = 1
Bước 3: các kết hợp có 1 thuộc tính là [kích cỡ], [màu sắc], [hình dáng]
Bước 4: Đếm các giá trị
[kích cỡ] = {{vừa}:1}
[màu sắc] = {{xanh dương}:1, {xanh lá}:2}
[hình dáng] = {{hộp}:1, {cầu}:2}
Vậy: max_com = 2 tương ứng với màu sắc = xanh lá
Bước 6: Khóa các dòng có STT là 5,7
Bước 7: Tạo ra luật R1: IF màu sắc = xanh lá THEN Quyết định = Mua
Bước 8: Quay lại bước 4
6/8/2010 Nguyễn Thị Thúy Loan 254
254
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 4: Đếm các giá trị
[kích cỡ] = {{vừa}:1}
[màu sắc] = {{xanh dương}:1}
[hình dáng] = {{hộp}:1, {cầu}:1}
Vậy: max_com = 1 tương ứng với kích cỡ = vừa
Bước 6: Khóa dòng có STT là 1
Bước 7: Tạo ra luật R2: IF kích cỡ = vừa THEN Quyết định = Mua
Bước 8: Quay lại bước 4
Xét bảng con 1
6/8/2010 Nguyễn Thị Thúy Loan 255
255
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
ST
T
Kích 
cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 4: Đếm các giá trị
[kích cỡ] = {}
[màu sắc] = {}
[hình dáng] = {{cầu}:1}
Vậy: max_com = 1 tương ứng với Hình dáng= cầu
Bước 6: Khóa dòng có STT là 3
Bước 7: Tạo ra luật R3: IF hình dáng = cầu THEN Quyết định = 
Mua
Bước 8: tất cả các dòng đều bị khóa, xét bảng con kế
Xét bảng con 1
6/8/2010 Nguyễn Thị Thúy Loan 256
256
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
ST
T
Kích 
cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 2: j = 1
Bước 3: các kết hợp có 1 thuộc tính là [kích cỡ], [màu sắc], [hình dáng]
Bước 4: Đếm các giá trị
[kích cỡ] = {}
[màu sắc] = {}
[hình dáng] = {{nón}:2}
Vậy: max_com = 2 tương ứng với hình dáng = nón
Bước 6: Khóa các dòng có STT là 2,4
Bước 7: Tạo ra luật R4: IF hình dáng = nón THEN QĐ = Không mua
Bước 8: Quay lại bước 4
Xét bảng con 2
6/8/2010 Nguyễn Thị Thúy Loan 257
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
ST
T
Kích 
cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 4: Đếm các giá trị [kích cỡ] = {}; [màu sắc] = {}; [hình dáng] ={}
Vậy: max_com = 0
Bước 5: Do max_com = 0 nên j = 2 và quay lại bước 3
Bước 3: Các kết hợp có 2 thuộc tính là [kích cỡ, màu sắc], [kích cỡ, hình 
dáng], [màu sắc, hình dáng]
Bước 4: Đếm số lần xuất hiện của các giá trị
[kích cỡ, màu sắc] = {{lớn, đỏ}:1}
[kích cỡ, hình dáng] = {}
[màu sắc, hình dáng] = {{đỏ, trụ}:1}
max_com = 1 ứng với kích cỡ = lớn và màu sắc = đỏ
Xét bảng con 2
6/8/2010 Nguyễn Thị Thúy Loan 258
258
STT Kích cỡ Màu sắc
Hình 
dáng Quyết định
1 Vừa Xanh dương Hộp Mua
3 Nhỏ Đỏ Cầu Mua
5 Lớn Xanh lá Trụ Mua
7 Lớn Xanh lá Cầu Mua
ST
T
Kích 
cỡ Màu sắc
Hình 
dáng Quyết định
2 Nhỏ Đỏ Nón Không mua
4 Lớn Đỏ Nón Không mua
6 Lớn Đỏ Trụ Không mua
Bước 4: Đếm số lần xuất hiện của các giá trị
[kích cỡ, màu sắc] = {{lớn, đỏ}:1}
[kích cỡ, hình dáng] = {}
[màu sắc, hình dáng] = {{đỏ, trụ}:1}
max_com = 1 ứng với kích cỡ = lớn và màu sắc = đỏ
Bước 6: Khóa dòng có STT = 6
Bước 7: Tạo ra luật R5: IF Kích cỡ = lớn AND Màu sắc = đỏ THEN 
Quyết định = Không mua 
Bước 8: Tất cả các dòng đều khóa, ngừng thuật toán
Xét bảng con 2