数据挖掘之分类

Size: px

Start display at page:

Download "数据挖掘之分类"

巽坦焦
4 years ago
Views:

3 ID3

5 5 4050

6 VS. (prediction)

7 (1)

8 (2)

9 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

10 (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?

11 VS.

14 age income student credit_rating buys_computer <=30 high no fair no <=30 high no excellent no high no fair yes >40 medium no fair yes >40 low yes fair yes >40 low yes excellent no low yes excellent yes <=30 medium no fair no <=30 low yes fair yes >40 medium yes fair yes <=30 medium yes excellent yes medium no excellent yes high yes fair yes >40 medium no excellent no

15 buys_computer age? <=30 overcast >40 student? yes credit rating? no yes fair excellent no yes no yes

16 ID3 ID3

17 ID3(1)

18 ID3(2) 5. 6.

19 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;

20 ID3

21 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 )

22 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)

23 SS = {E 1,...,E n }, P = {p 1,..., p n } I(e i ) = - log 2 p i

24 26 : I(e) = -log 2 (1/26) = I(e) = -log 2 (1/2500) = 11.3

25 1 Ssm mc i (i=1,,m)s i C i p i C i s i /s

26 2 Av{a1,a2,,av} ASv{S1,S2,,Sv}SiS AajA Ssij SjCiA

27 3

28 -- (Gain) =

29 --

31 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

32 (m=2): / s 1 = 641, s 2 = 383 s = s 1 + s 2 = 1024 p 1 = s 1 /s = 641/1024 = p 2 = s 2 /s = 383/1024 = I(s 1, s 2 ) = I(641, 383) = - (p 1 log 2 (p 1 ) + p 2 log 2 (p 2 )) =

33 E 1. : I(128,256)= : I(256,0)=0 : I(257,127)= : ( )/1024=0.375 : 256/1024=0.25 : ( )/1024=0.375 E(= 0.375* * * = Gain() = I(641, 383)-E() = =

34 2. : I(160,128)= : I(289,191)= : I(192,64)= : 288/1024= : 480/1024= : 256/1024=0.25 E(= * * * = Gain() = I(641, 383)-E() = =

35 -- 3. : I(420,64)= : I(221,319)= : 484/1024= : 540/1024= E(= * * = Gain() = I(641, 383)-E() = =

36 -- 4. : I(480,192)= : I(161,191)= : 672/1024= : 352/1024= E(= * * = Gain() = I(641, 383)-E() = =

37 -- E(= Gain() = E(= Gain() = E(= Gain() = E(= Gain() =

40 -- 1. I(128,256) = I(0,128)=0 : 128/384= I(64,128)= : 192/384=0.5 I(64,0)=0 : 64/384= E(= * * * 0 = Gain() = I(128, 256) - E()= =

41 -- 2. I(128,256) = I(128,0)=0 : 128/384= I(0,256)=0 : 256/384= E(= * * 0 = 0 Gain() = I(128, 256) - E()= = :

44 -- 1. I(257,127) = I(64,64)=1 : 128/384= I(193,63)= : 256/384= E(= * * = Gain() = I(257, 127) - E()= =

45 -- 2. I(257,127) = I(196,64)= : 260/384= I(61,63)= : 124/384= E(= * * = Gain() = I(257, 127) - E()= =

46 -- 3. I(257,127) = I(256,0)=0 : 256/384= I(1,127)= : 128/384= E(= * * = Gain() = I(257, 127) - E()= = :

49 age income student credit_rating buys_computer <=30 high no fair no <=30 high no excellent no high no fair yes >40 medium no fair yes >40 low yes fair yes >40 low yes excellent no low yes excellent yes <=30 medium no fair no <=30 low yes fair yes >40 medium yes fair yes <=30 medium yes excellent yes medium no excellent yes high yes fair yes >40 medium no excellent no

50 ID3 (1) 12 3 Gain(age)=0.246 Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048

51 ID3 (2)

52 ID3 (3) age? <=30 overcast >40 student? yes credit rating? no yes fair excellent no yes no yes

53 e.g.

54 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 = 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

55 P ( h D) = P( D h) P( h) P( D) P(h) P(h D)

56 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

57 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

59 C1 C2 = 21 = = X={ = 21 = = }

60 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.06 P(X C2)P(C2)= =0.02 XC1

62 ID3 ID3 (1) (2)

63 (1) (2) (3) ID3 (4) ID3

64 (1) (2) (3)

65 k- k- kk

Microsoft Word - 21??¡N??`?C?~??-1.doc, page Normalize ( Microsoft Word - 21ºÝ¤È¸`§C¦~¯Å-1.doc )

Microsoft Word - 21??¡N??`?C?~??-1.doc, page Normalize ( Microsoft Word - 21ºÝ¤È¸`§C¦~¯Å-1.doc ) 守護神 VS 幸運蛋壹設計理念農曆五月五日, 就是民間所稱的端午節, 有關端午節的傳說及習俗不勝枚舉, 而最為一般大眾所熟知的莫過於屈原投江的傳說故事屈原是西元前三世紀中國偉大的愛國詩人, 因得罪了王公貴人最後被驅逐出