whgong@zjut.edu.cn
ID3
5 4050
VS. (prediction)
(1)
(2)
NAME RANK YEARS TENURED Mike Assistant Prof 3 no Mary Assistant Prof 7 yes Bill Professor 2 yes Jim Associate Prof 7 yes Dave Assistant Prof 6 no Anne Associate Prof 3 no IF rank = professor OR years > 6 THEN tenured = yes
(Jeff, Professor, 4) NAME RANK YEARS TENURED Tom Assistant Prof 2 no Merlisa Associate Prof 7 no George Professor 5 yes Joseph Assistant Prof 7 yes Tenured?
VS.
age income student credit_rating buys_computer <=30 high no fair no <=30 high no excellent no 31 40 high no fair yes >40 medium no fair yes >40 low yes fair yes >40 low yes excellent no 31 40 low yes excellent yes <=30 medium no fair no <=30 low yes fair yes >40 medium yes fair yes <=30 medium yes excellent yes 31 40 medium no excellent yes 31 40 high yes fair yes >40 medium no excellent no
buys_computer age? <=30 overcast 30..40 >40 student? yes credit rating? no yes fair excellent no yes no yes
ID3 ID3
ID3(1) 1. 2. 3. 4.
ID3(2) 5. 6.
function ID3 (R:, C:, S: ) returns ; begin If S return Failure; If S return ; If R return S; // D = RGain(D,S); {dj j=1,2,.., m} = D; {Sj j=1,2,.., m} = SSjDdj Dd1, d2,.., dm ID3(R-{D}, C, S1), ID3(R-{D}, C, S2),.., ID3(R-{D}, C, Sm); end ID3;
ID3
1np 1/nLog 2 (n) 2nP=(p 1,p 2 p n ) P 3T C 1 C 2..C k T Info(T)=E(p)PC 1 C 2..C k P=( C 1 / T,.. C k / T )
4XT T 1,T 2 T n TT i Info(T i ) Info(X,T)= (( T i / T )Info(T i )) 5 T XT Gain(X,T)=Info(T)-Info(X,T)
SS = {E 1,...,E n }, P = {p 1,..., p n } I(e i ) = - log 2 p i
26 : I(e) = -log 2 (1/26) = 4.7 2500 I(e) = -log 2 (1/2500) = 11.3
1 Ssm mc i (i=1,,m)s i C i p i C i s i /s
2 Av{a1,a2,,av} ASv{S1,S2,,Sv}SiS AajA Ssij SjCiA
3
-- (Gain) =
--
-- 64 64 128 64 64 128 64 32 32 60 64 64 132 63 1
64 64 12 8 60 64 64 64 12 8 64 13 2 64 32 32 63 1 -- m s 1, s 2, s m s = s 1 + s 2 + +s m I(s 1, s 2, s m ) = -p i log 2 (p i ) p i = s i /s
64 64 128 60 64 64 64 128 64 132 64 32 32 63 1 -- (m=2): / s 1 = 641, s 2 = 383 s = s 1 + s 2 = 1024 p 1 = s 1 /s = 641/1024 = 0.6260 p 2 = s 2 /s = 383/1024 = 0.3740 I(s 1, s 2 ) = I(641, 383) = - (p 1 log 2 (p 1 ) + p 2 log 2 (p 2 )) = 0.9537
E 1. : I(128,256)=0.9183 : I(256,0)=0 : I(257,127)=0.9157 : (128+256)/1024=0.375 : 256/1024=0.25 : (257+127)/1024=0.375 E(= 0.375*0.9183 +0.25*0+0.375*0.9157 = 0.6877 Gain() = I(641, 383)-E() =0.9537 0.6877 = 0.2660 -- 64 64 128 64 64 128 64 32 32 60 64 64 132 63 1
2. : I(160,128)=0.9911 : I(289,191)=0.9697 : I(192,64)=0.8133 : 288/1024=0.2813 : 480/1024=0.4687 : 256/1024=0.25 E(= 0.2813 * 0.9911 + 0.4687 * 0.9697 + 0.25 * 0.8133 = 0.9361 Gain() = I(641, 383)-E() =0.9537 0.9361= 0.0176 -- 64 64 128 32 60 128 132 64 32 63 1 64 64 64 64
-- 3. : I(420,64)=0.5635 : I(221,319)=0.9761 : 484/1024=0.4727 : 540/1024=0.5273 E(= 0.4727 * 0.5635 + 0.5273 * 0.9761 = 0.7811 Gain() = I(641, 383)-E() =0.9537 0.7811= 0.1726 64 64 64 64 132 64 32 64 64 128 60 128 32 63 1
-- 4. : I(480,192)=0.8631 : I(161,191)=0.9948 : 672/1024=0.6563 : 352/1024=0.3437 E(= 0.6563 * 0.8631 + 0.3437 * 0.9948 = 0.9048 Gain() = I(641, 383)-E() =0.9537 0.9048= 0.0453 64 128 60 64 128 64 132 32 64 64 64 64 32 63 1
-- E(= 0.6877 Gain() = 0.2660 E(= 0.9361Gain() = 0.0176 E(= 0.7811Gain() = 0.1726 E(= 0.9048Gain() = 0.0453
-- 64 60 64 64 128 64 64 132 64 63 1 128 64 32 32
-- 64 64 128 64 64 60 64 64 132 63 1
-- 1. I(128,256) = 0.9183 64 64 12 8 64 64 64 64 128 64 64 I(0,128)=0 : 128/384=0.3333 I(64,128)=0.9183 : 192/384=0.5 I(64,0)=0 : 64/384=0.1667 E(= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain() = I(128, 256) - E()=0.9183 0.4592 = 0.4591
-- 2. I(128,256) = 0.9183 64 64 64 I(128,0)=0 : 128/384=0.3333 I(0,256)=0 : 256/384=0.6667 64 12 8 64 64 64 64 128 E(= 0.3333 * 0 + 0.6667 * 0 = 0 Gain() = I(128, 256) - E()=0.9183 0 = 0.9183 :
-- 60 64 64 132 64 64 128 64 64 63 1
-- 60 64 64 132 63 1
-- 1. I(257,127) = 0.9157 60 64 64 132 63 1 64 64 60 132 I(64,64)=1 : 128/384=0.3333 I(193,63)=0.8050 : 256/384=0.6667 63 1 E(= 0.3333 * 1 + 0.6667 * 0.8050 = 0.8700 Gain() = I(257, 127) - E()=0.9157 0.8700 = 0.0457
-- 2. I(257,127) = 0.9157 60 64 64 132 64 64 132 60 I(196,64)=0.8051 : 260/384=0.6771 I(61,63)=0.9998 : 124/384=0.3229 63 1 63 1 E(= 0.6771 * 0.8051 + 0.3229 * 0.9998 = 0.8680 Gain() = I(257, 127) - E()=0.9157 0.8680= 0.0477
-- 3. I(257,127) = 0.9157 60 64 64 132 63 1 60 64 132 64 63 1 I(256,0)=0 : 256/384=0.6667 I(1,127)=0.0659 : 128/384=0.3333 E(= 0.6667 * 0 + 0.3333 * 0.0659 = 0.0220 Gain() = I(257, 127) - E()=0.9157 0.0220 = 0.8937 :
-- 64 60 63 64 1 132
-- 64 63 1
age income student credit_rating buys_computer <=30 high no fair no <=30 high no excellent no 31 40 high no fair yes >40 medium no fair yes >40 low yes fair yes >40 low yes excellent no 31 40 low yes excellent yes <=30 medium no fair no <=30 low yes fair yes >40 medium yes fair yes <=30 medium yes excellent yes 31 40 medium no excellent yes 31 40 high yes fair yes >40 medium no excellent no
ID3 (1) 12 3 Gain(age)=0.246 Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048
ID3 (2)
ID3 (3) age? <=30 overcast 30..40 >40 student? yes credit rating? no yes fair excellent no yes no yes
e.g.
IF-THEN -"IF" "THEN" IF-THEN IF age = <=30 AND student = no THEN buys_computer = no IF age = <=30 AND student = yes THEN buys_computer = yes IF age = 31 40 THEN buys_computer = yes IF age = >40 AND credit_rating = excellent THEN buys_computer = yes IF age = >40 AND credit_rating = fair THEN buys_computer = no
P ( h D) = P( D h) P( h) P( D) P(h) P(h D)
nx{x 1,x 2,,x n }x k A k mc 1,C 2,,C m C i P(C i X)>P(C j X) 1jm, ji XC i C i
P(x)P(X C i )P(C i ) P(C i )s i /ss i C i s P(x 1 C i ) P(x 2 C i ) P(x n C i ) P(x k C i )=s ik /s i 1kn s ik A k x k C i s i C i s
C1 C2 = 21 = = X={ = 21 = = }
P(X C 1 )P(C 1 )P(X C 2 )P(C 2 ) P(C1)=9/14=0.64 P(C2)=5/14=0.36 P( = <=30 C1)=2/9=0.22 P( = <=30 C2)=3/5=0.60 P( = C1)=6/9=0.67 P( = C2)=1/5=0.20 P( = C1)=6/9=0.67 P( = C2)=2/5=0.40 P(X C1)P(C1)=0.220.670.670.64=0.06 P(X C2)P(C2)=0.600.200.400.36=0.02 XC1
ID3 ID3 (1) (2)
(1) (2) (3) ID3 (4) ID3
(1) (2) (3)
k- k- kk