Ch
ng 4:
ươ ớ
ữ ệ
Phân l p d li u (Data Classification)
N i dung
ộ
ự
ế ị
ng pháp phân l p khác
1. Phân l p và d đoán? ớ 2. Quy n p trên cây quy t đ nh ạ 3. Phân l p Bayes ớ 4. Các ph ươ
ớ
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 ể ớ các l p ớ ng d ữ ướ
ọ
l p mô hình/m u nh m mô t ả ẫ ậ quan tr ng hay d đoán khuynh h ự li u trong t ng lai. ệ
ươ
• Phân l p(classification) d đoán các nhãn
ự
ớ
phân lo i.ạ
• D đoán (prediction) hàm giá tr liên t c.
ự
ụ
ị
Phân lớp và Dự đoán
Phân l p d li u là ti n
ớ
ế
ữ ệ c phân
ượ
ữ ệ cướ trình có 2 b – Hu n luy n ệ : D li u ấ hu n luy n đ ệ ấ tích b i thu t tóan ở ậ phân l p ( có thu c ộ ớ tính nhãn l p) ớ – Phân l p:ớ D li u
ể
ữ ệ c dùng đ ể ượ ộ
ng đ chính ớ
ượ
ậ
c thì có ớ ẫ
ki m tra đ c l ướ ượ xác c a b phân l p. ủ ộ N u đ chính xác là ộ ch p nh n đ 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 và Dự đoán?
Độ 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
Accuracy =
correctly total number
classified test of test
sample sampl
Chu n b d li u
ị ữ ệ
ẩ
Làm sách d li u
ữ ệ
– Nhi uễ – Thi u giá tr ị ế
Phân tích liên quan (ch n đ c tr ng)
ư
ặ
ọ
ư ừ
Bi n đ i d li u
– Các thu c tính không liên quan – Các thu c tính d th a ế
ộ ộ ổ ữ ệ
So sánh các ph
ng pháp phân l p
ươ
ớ
ộ
ộ
ủ ả l p d đoán đúng d li u ch a th y ấ ớ ộ
ự ữ ệ ả
ớ
ự • Tính b n v ng ề ự
ự ế
ễ
• Đ chính xác c a d đoán : kh năng b phân ư ữ : kh năng c a b phân l p th c ủ hi n d đoán đúng v i d li u có nhi u hay thi u ớ ữ ệ ệ giá tr ị
: kh năng t o b phân ạ
ộ
ệ
i
ả ng d li u l n ữ ệ ớ ớ
ứ
ả
ấ
• Tính kích c (scalability) ỡ l p hi u qu v i s l ả ớ ố ượ ớ • Kh năng di n gi ả : b phân l p cung c p tri th c ộ ễ có th hi u đ c ượ ể ể
Cây quy t đ nh
ế ị
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 ớ
ứ
ể
ộ
ộ
ế
ể
ả
• 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
trên m t thu c tính ễ ễ
ộ ể ể
ớ
b l pố ớ
• Nút cao nh t trong cây là nút
ấ
g c.ố
Cây quy t đ nh
ế ị
Quy n p trên cây quy t đ nh
ế ị
ạ
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 nguợc lại lặp lại các bước 14 cho các
nút lá
5. Tỉa các nút lá không ổn định
Temperature
Headache
Temperature
Flu
normal
very high
high
{e1, e4}
{e3,e6}
{e2, e5}
e1 yes normal no
no
e2 yes high yes
Headache
Headache
no {e6}
yes {e2}
yes {e3}
no {e5}
e3 yes very high yes e4 no normal no e5 no high no
yes
no
yes
no
e6 no very high no
Chi n l
ế ượ
c c b n ơ ả
ể ề nút đ n bi u di n t ẫ t c các m u ẫ ễ ấ ả ở ộ ớ
• B t đ u t ắ ầ ừ • N u các m u thu c v cùng m t l p, nút tr thành nút lá ế và đ ằ
• Ng ơ ộ c gán nhãn b ng l p đó ộ i, dùng đ đo thu c tính đ ch n thu c tính s ẽ ể ộ
ượ c l ượ ạ phân tách t ố • M t nhánh đ c ượ ộ
ớ ọ ộ t nh t các m u vào các l p ấ ớ ẫ c t o cho t ng giá tr c a thu c tính đ ị ủ ừ ượ ạ ch n và các m u đ ẫ ộ ọ
ế ị ệ
• 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à ấ ể ạ ề c phân ho ch theo ạ ượ ộ ỉ ệ ế
c đ u thu c v cùng m t
ấ ả
ẫ
ộ
ướ
ề
ề
ộ
ộ
l p. ớ
– 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. ẫ
– Không còn m u nào cho nhánh test_attribute = a
i
ế đúng – T t c các m u cho m t nút cho tr
B ng d li u hu n luy n
ữ ệ
ệ
ấ
ả
Day
Outlook Temp Humidity Wind PlayTennis
No
Normal Normal Normal
No Strong Yes Weak Yes Weak Yes Weak Strong No Strong Yes No
Mild High Weak Normal Cool Mild Normal Mild Normal
Normal
D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14
Sunny Hot High Weak High Hot Sunny High Overcast Hot Mild High Rain Cool Rain Rain Cool Overcast Cool Sunny Sunny Rain Sunny Overcast Mild High Overcast Hot Rain
Mild High
Weak Weak Strong Strong Weak Strong
Yes Yes Yes Yes Yes No
Cây quy t đ nh cho bài toán ch i tennis
ế ị
ơ
temperature
cool hot mild {D5, D6, D7, D9} {D1, D2, D3, D13} {D4, D8, D10, D11,D12, D14}
outlook
wind
outlook
sunny o’cast rain {D8, D11} {D12} {D4, D10,D14}
sunny rain o’cast {D9} {D5, D6} {D7}
true false {D2} {D1, D3, D13}
no
yes
yes
wind
humidity
yes
wind
humidity
true false {D5} {D6}
high normal {D1, D3} {D3}
true false {D11} {D8} no
outlook
no
yes
yes
high normal {D4, D14} {D10} wind yes
yes
true false {D14} {D4}
sunny rain o’cast {D1} {D3}
yes
yes
no
null
no
Cây quy t đ nh đ n gi n
ế ị
ả
ơ
outlook
sunny o’cast rain {D1, D2, D8 {D3, D7, D12, D13} {D4, D5, D6, D10, D14} D9, D11}
humidity
wind
yes
high normal {D1, D2, D8} {D9, D10}
true false {D6, D14} {D4, D5, D10}
no
yes
no
yes
ượ ơ ế “outlook” đ
Cây s đ n gi n h n n u Cách ch n thu c tính t
ẽ ơ ọ ả ộ ố ể c ch n làm g c ố . ọ ế ị t đ tách nút quy t đ nh ?
Thu c tính nào là t
ộ
ố
t nh t? ấ
S có 19 m uẫ thu c l p c ng
ế ị ẫ ộ ộ ớ ộ (+) và 35 m u thu c
ừ (), ta ký hi uệ là [19+, 35]
ộ
c a m u d ẫ ươ ẫ ị ng và m u âm nh sau ,
Nút quy t đ nh l p tr ớ Nếu các thuộc tính A1 và A2 (m i thu c tính có 2 giá tr ) tách ỗ S l thành các nút con v i t ư ớ ỷ ệ ủ t h n thu c tính nào là t ố ơ ?
ộ
[19+, 35 ] [19+, 35 ] A2 = ? A1 = ?
[18+, 33] [11+, 2] [21+, 5] [8+, 30 ]
Entropy
ộ ấ ị ủ ậ ỗ ạ ư ặ ấ
Entropy đ c tr ng đ b t đ nh / h n t p 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 các m u thu c l p d ng trong S l ỷ ệ ộ ớ ẫ ươ
p log2p
p là t l ỷ ệ các m u thu c l p âm trong S ộ ớ ẫ
Entropy(S) = p log2p¯
Entropy
y p o r t n e
ng ng ươ ứ ớ boolean,khi
ng thay đ i ổ
c
Hàm entropy t v i phân l p ớ l ỷ ệ ủ p các ví d ụ c a t thu c l p d ộ ớ ươ gi a ữ 0 và 1.
Entropy(S)
logp i
p i2
= 1i
- ” (cid:229)
Ví dụ
ng và ộ ớ ươ
ẫ ủ ả PlayTennis, 9 thu c l p d T ừ 14 m u c a b ng (ký hi u là 5 m u âmẫ ệ [9+, 5] )
Entropy([9+, 5] ) = (9/14)log2(9/14) (5/14)log2(5/14)
ế ấ ả
ộ ớ
t c các thành viên đ u thu c v l p d
ộ ề ng
(p = 1) thì p là 0 và
ụ ế ấ ả
t c các thành viên c a S đ u thu c v cùng m t l p. ề ủ ộ ề ớ ươ
ề
L u ýư : 1. Entropy là 0 n u t Ví d , n u t Entropy(S) = 1. log2(1) 0. log2 (0) = 1.0 0 . log2 (0) = 0.
ứ ố ượ
ằ
ợ ế
ố
. N u các s này là khác nhau,
ng b ng nhau các thành viên thu c ộ entropy s n m gi a ữ 0 ẽ ằ
2. Entropy là 1 n u t p h p ch a s l ế ậ ng và l p âm l p d ớ ớ ươ và 1.
= 0.940
ủ
ả
ố
Information Gain đo s rút gi m mong mu n c a ự Entropy
ị ứ
ệ ộ ộ ả ớ
ở ự ả
information gain, ph n ánh m c đ Ta đ nh nghĩa đ đo ộ 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 ộ ụ ạ
Gain(S,
A)
Entropy(S)
)
Entropy(S v
- ” (cid:229)
S v S
v
Value(A)
˛
ậ ộ ị A, và
ậ ậ ủ S mà A nh n giá tr ể ị v. Gía tri Value(A) là t p các giá tr có th cho thu c tính Sv là t p con c a
ự
ả
Information Gain đo s rút gi m trong Entropy
Values(Wind) = {Weak, Strong}, S = [9+, 5]
ớ ị “weak” là [6+, 2]
ớ ị “strong”, là [3+, 3] Sweak là nút con v i tr Sstrong , là nút con v i tr
)
Gain(S, Wind) = Entropy(S)
Entropy(S v
(cid:229)
S v S
v
{Weak,
Strong}
= Entropy(S) (8/14)Entropy(Sweak) (6/14)Entropy(SStrong)
= 0.940 (8/14)0.811 (6/14)1.00 = 0.048
˛
Thu c tính nào là phân l p t
ớ ố
ộ
t nh t? ấ
S:[9+, 5] E = 0.940
S:[9+, 5] E = 0.940
Humidity
Wind
High Normal
Weak Strong
[3+, 4] [6+, 1] E = 0.985 E = 0.592
[6+, 2] [3+, 3] E = 0.811 E = 1.00
Gain(S, Humidity) = .940 (7/14).985 (7/14).592 = .151
Gain(S, Wind) = .940 (8/14).811 (6/14)1.00 = .048
Information gain c a t
ủ ấ ả
t 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
ng trên cây quy t ế ế ế ưở ế
B c k ti p trong ti n trình tăng tr ướ đ 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
?
?
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
Đi u ki n d ng ệ
ừ
ề
1. T ng thu c tính đã đ ộ cây
ng trên ừ ượ ư c đ a vào d c theo con đ ọ ườ
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 zero)
ệ ứ ẫ ấ ộ ị
ẳ ạ ằ
D3 dùng Information Gain và C4.5,
c phát tri n sau nó ể , dùng Gain Ratio (m t ộ
L u ýư : Thu t toán I ậ thu t toán đ ượ bi n th c a ậ ế ể ủ Information Gain)
Đ i cây thành lu t
ậ
ổ
outlook
sunny o’cast rain
wind
humidity
high normal
yes
true false no
yes no yes
(Outlook = Sunny) and (Humidity = High)
IF THEN PlayTennis = No
(Outlook = Sunny) and (Humidity = Normal)
IF THEN PlayTennis = Yes ........
Các thu c tính v i nhi u giá tr ị
ề
ớ
ộ
ế ụ ề
N u thu c tính có nhi u giá tr (ví d , các ngày trong tháng, ị ộ ID3 s ch n nó ẽ ọ C4.5 dùng GainRatio
Gain(S,
GainRatio(
A)S,
A) mation(S,
A)
SplitInfor
c
”
SplitInfor
mation(S,
A)
log 2
S i S
S i S
= 1i
where
subset
S of
with
A
has
value
v
is S i
i
- ” (cid:229)
Phân l p Bayes ớ
Phân l p Bayes ớ
Bộ phân l p Bayes ớ
ẳ
có th d báo các xác su t ấ ể ự là thành viên c a l p, ch ng h n xác su t ấ ủ ớ ạ c thu c v m t l p xác đ nh m u cho tr ề ộ ớ ộ
ướ
ẫ
ị
ớ
ể
ợ
ớ ộ
ế ị
ớ
ạ
ơ
Bộ phân l p Naïve Bayes l à có th so sánh đu c v ề công năng v i B phân l p v i cây quy t đ nh và ớ đ nh các thu c tính là đ c m ng n ron. Chúng gi ộ ộ ả ị l p nhau (đ c l p đi u ki n l p) ệ ớ ề ậ
ộ ậ
Đ nh lý Bayes
ị
t nhãn l p ế ư
thuy t sao cho X thu c v l p C ớ ề ớ ẫ ả
X là m u d li u ch a bi ữ ệ H là gi ế ị Ấ ấ ậ
c quan sát X (H conditioned
c mô t Gi ượ ả ẫ ồ
ỏ
ả ử ỉ
c X có
ả
t tr ế ướ
s X là màu đ và tròn - Gi - H là g a thuy t mà X là qu táo ả ế - Thì P(H|X) ph n ánh đ tin c y X là qu táo khi bi ậ ộ ả màu đ và tròn ỏ
ộ n đ nh xác su t h u nghi m posterior probability P(H|X) ệ sao cho H đúng khi cho tr ướ on X) s th gi ữ ệ ả ử ế ớ b ng màu s c và hình dáng. ằ i các m u d li u g m trái cây, đ ắ
Định lý Bayes
P(X|H) là xác suất hậu nghiệm của X có điều kiện
trên. Định lý Bayes
|P(X
=
|P(H
X)
H)P(H) P(X)
Khi có n giả thuyết
)
=
X)
|P(H i
)
H|P(X i n H|P(X j
)P(H i )P(H j
= 1j
(cid:229)
Phân l p Naïve Bayesian (NBC)
ớ
M i m u d li u đ c bi u di n b ng X= (x1, x2,…, xn) v i ớ ể ằ ẫ ượ
ữ ệ ộ
ỗ ễ các thu c tính A1, A2,…, An Các l p C1, C2, …, Cm. Cho tr c m u ch a bi ớ ướ ẫ
£ ế m, j „ ư j £
thuy t h u nghi m c c đ i ạ ớ ế ậ ạ ượ ự ả
)
)P(C i
=
X)
|P(C i
C|P(X i P(X)
t X. NBC gán X vào Ci iff P(Ci|X) > P(Cj|X) v i 1 ớ i. Do v y, chúng ta c c đ i P(Ci|X). L p Ci sao cho P(Ci|X) là ạ ự ậ c c đ i đ c g i là gi ọ ự (maximum posterior hypothesis). Theo đ nh lý Bayes ệ ị
Phân l p Naïve Bayesian
ớ
ằ
Do P(X) là h ng cho t
ớ t P(C
ế
ế
i, ta c c đ i P(X|C
c l ượ ạ
ạ
t c các l p, ch c n c c đ i ự ấ ả ạ ỉ ầ i) c n gi đ nh P(X|Ci) P(Ci). N u ch a bi ả ị ầ ư P(C1)=P(C2)=…= P(Cm) và chúng ta s c c đ i ạ ẽ ự i) P(Ci) P(X|Ci). Ng ự
N u m là l n, s r t t n kém khi tính P(X|C
i) P(Ci).
ế NBC gi
ớ đ nh đ c l p đi u ki n l p ả ị
ẽ ấ ố ộ ớ
ệ ớ
ề
n
=
)C|P(X i
P(x k
)C| i
= 1k
(cid:213)
Phân lớp Naïve Bayesian
Có th ph ng tính ỏ
ể
P(x1|Ci), …, P(xn|Ci) t c phân l p thì P(x ớ i có tr xị
k cho Ak và si là s các m u
N u Aế k đ ượ m u hu n luy n c a C ấ ệ thu c v l p C ề ớ
ẫ ừ ẫ ấ k|Ci) = sik/si v i sớ ố các m u hu n luy n ệ ik là s ố ẫ ủ
i
ộ
N u Ak là liên t c thì nó đ c gi ụ ế ượ ả ị đ nh có phân b ố
2
Gaussian
(x
k 2σ
)μ iC 2 iC
=
=
g(x
)σ,μ,
e
P(x k
)C| i
k
C i
C i
1 πσ
2
C i
- -
Phân l p Naïve Bayesian
ớ
ớ
ẫ
ế
ẫ
t X, ta tính P(X| c ượ j £
Đ phân l p m u ch a bi ư ể i. Sau đó m u X đ Ci) P(Ci) cho t ng Cừ gán vào Ci iff P(Ci|X) > P(Cj|X) for 1 £ m, j „
i
Nói cách khác, NBC gán X vào l p Cớ
i sao
cho P(X|Ci) P(Ci) là c c đ i ạ
ự
CSDL Customer
D báo nhãn l p v i phân l p Bayesian ớ
ự
ớ
ớ
X = (age = “<=30”, income = “fair”, student = “yes”, credit_rating = “fair”)
P(buys_computer = “yes”) = 9/14 = 0.643 P(buys_computer = “no”)
= 5/14 = 0.357
To compute P(X|Ci) P(Ci), for i = 1, 2, we compute
= 2/9 = 0.222 = 3/5 = 0.600 = 4/9 = 0.444 = 2/5 = 0.444 = 6/9 = 0.667
= 1/5 = 0.200
P(age = “<30”| buys_computer = “yes”) P(age = “<30”| buys_computer = “no”) P(income = “medium”| buys_computer = “yes”) P(income = “medium”| buys_computer = “no”) P(student = “yes”| buys_computer = “yes”) P(student = “yes”| buys_computer = “no”) P(credit_rating = “yes”| buys_computer = “yes”) P(credit_rating = “yes”| buys_computer = “no”)
= 6/9 = 0.667 = 2/5 = 0.400
D báo nhãn l p v i phân l p Naive Bayesian
ự
ớ
ớ
ớ
We obtain
P(X|buys_computer = “yes”) = 0.222 x 0.667 x 0.667 x 0.044 = 0.044
P(X|buys_computer = “no”) = 0.600 x 0.400 x 0.200 x 0.400 = 0.019
P(X|buys_computer = “yes”)P(buys_computer = “yes”) =
0.044 x 0.643 = 0.028
P(X|buys_computer = “no”)P(buys_computer = “no”) =
0.019 x 0.357 = 0.007
Therefore, NBC predicts buys_computer = “yes” for sample X
Các ph
ng pháp phân l p
ươ
ớ
k-Nearest Neighbor Classifiers Case-based Reasoning Genetic Algorithms Rough Set Approach Fuzzy Set Approaches
Rough sets: the basic idea
Equivalence classes [o]E defined by an equivalence relation E
Each set X is represented by a pair of two sets: a lower approximation X* and a upper approximation X*
lower approximation X* is the union of equivalence classes included in X
= ˝ ˛
X
E
is the upper approximation X* union of equivalence classes having non empty intersection with X
*
=
{o :O [o] X} (X)E *
E
(X)
{o
:O
[o]
X
/ }0
E
„ ˙ ˛
Fuzzy Set Approaches
IF (year_employed >= 2) (cid:217) (income >= $50K) THEN credit = “a
pproved”
A customer with at least two years at job and income $49K will not satisfy the rule. With fuzzy logic we can capture the notion that an income of $49K is, to some degree, high, although not as high as an income of $50K
