【文章內(nèi)容簡介】 ,Lux ury }{Fa mi ly }C1 3 1C2 2 4Gin i 0. 400CarT yp e{Spo rts}{ Fa mi ly ,Lux ury }C1 2 2C2 1 5Gin i 0. 419CarT yp eFa mi ly Spo rts Lux uryC1 1 2 1C2 4 1 1Gin i 0. 393Multiway split Twoway split (find best partition of values) 連續(xù)屬性 : 計算 Gini ? 使用二元劃分 ? 劃分點 v選擇 – N個記錄中所有屬性值作為劃分點 ? 對每個劃分進行類計數(shù) , A v and A ? v ? 計算每個候選點 v的 Gini指標，并從中選擇具有最小值的候選劃分點 ? 時間復雜度為 (n2) Tid Re f und Marital Stat u s Taxable In e Che a t 1 Yes Single 125K No 2 No Marr i ed 100K No 3 No Single 70K No 4 Yes Marr i ed 120K No 5 No Divor ce d 95K Yes 6 No Marr i ed 60K No 7 Yes Divor ce d 220K No 8 No Single 85K Yes 9 No Marr i ed 75K No 10 No Singl e 90K Yes 10 TaxableIne 80K?Yes No連續(xù)屬性 : 計算 Gini... ? 降低計算復雜性的方法 , – 將記錄進行排序 – 從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點 – 計算每個候選點的 Gini值 – 時間復雜度為 nlogn Cheat No No No Yes Yes Yes No No No No Taxabl e Inc om e 60 70 75 85 90 95 100 120 125 220 55 65 72 80 87 92 97 110 122 172 230 = = = = = = = = = = = Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0 G ini 劃分點 排序后的值 ? 定義：給定一個概率空間 事件 { , , ( )}X q x?kx ?的自信息定義為 因 I ( ) l ogkkxq??[ 0 , 1 ]kq ? 故I( ) 0kx ?自信息反映了事件 發(fā)生所需要的信息量。 值越大說明需要越多的信息才能確定事件 的發(fā)生，其隨機性也越大，而當 發(fā)生時所攜帶的信息量也越大。反過來， 值越小，需要較少信息量就能確定 的發(fā)生，即事件 隨機性較小。當其發(fā)生時所攜信息量就少。 是對不確定性大小的一種刻畫 kxI( )kx kxk I( )kxkxI( )kx熵 定義 熵 定義 ? ：在概率空間 上定義的隨機變量 I( X)的數(shù)學期望 { , , ( ) }X q x?E( I ( x ) ) ( ) ( ) ( ) l og ( )xxq x I x q x q x????? ? ???稱為隨機變量 X的平均自信息，又稱 X的信息熵或熵記為 H(x) ? 非負性： H大于等于 0 ? 連續(xù)性： H對任意 q連續(xù) ? 極值性：當 q都等于 1\K時 H達到最大值 logK 熵 定義 基于 Information Gain的劃分 ? 給定結(jié)點 t的 Entropy值計算 : (p( j | t) 是在結(jié)點 t中，類 j發(fā)生的概率 ). – 當類分布均衡時， Entropy值達到最大值 (log nc) – 相反當只有一個類時， Gini值達到最小值 0 – Entropy 與 GINI相似 ??? j tjptjptEntropy )|(log)|()(計算 Entropy的例子 C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = – 0 log 0 – 1 log 1 = – 0 – 0 = 0 P(C1) = 1/6 P(C2) = 5/6 Entropy = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = P(C1) = 2/6 P(C2) = 4/6 Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = ??? j tjptjptEntropy )|(log)|()( 2基于 Information Gain的劃分 ... ? Information Gain: ni = 孩子結(jié)點 i的記錄數(shù) , n = 結(jié)點 p的記錄數(shù) . – 在 ID3 and ???????? ??ki is pli t iEntropynnpEntropyGAIN 1 )()(基于 Information Gain的劃分 ... ? 增益率（ Gain Ratio） : – 熵和 Gini指標等不純性趨向于有利于具有大量不同值的屬性 !如：利用雇員 id產(chǎn)生更純的劃分，但它卻毫無用處 – 每個劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測 – 解決該問題的策略有兩種： – 限制測試條件只能是二元劃分 – 使用增益率。 K越大 Split Info越大增益率越小 SplitINFOGAINGainRATIO Spli ts pli t ????? kiiinnnnSplitINFO1log基于 Classification Error的劃分 ? 給定結(jié)點 t的 Classification Error值計算 : ? 當類分布均衡時， error值達到最大值 (1 1/nc) ? 相反當只有一個類時， error值達到最小值 0 )|(max1)( tiPtError i??例子 C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Error = 1 – max (0, 1) = 1 – 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6 P(C1) = 2/6 P(C2) = 4/6 Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3 )|(max1)( tiPtError i??不純性度量之間的比較 二元分類問題 : 決策樹 ? Hunt算法采用貪心策略構(gòu)建決策樹 . – 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹 . ? 決策樹歸納的設(shè)計問題 – 如何分裂訓練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 停止分裂過程 ? 當所有的記錄屬于同一類時，停止分裂 ? 當所有的記錄都有相同的屬性時，停止分裂 ? 提前終止樹的生長 三種著名的決策樹 ? Cart：基本的決策樹算法 ? Id3：利用增益比不純性，樹采用二叉樹，停止準則為當所有的記錄屬于同一類時，停止分裂，或當所有的記錄都有相同的屬性時，停止分裂 ? ： id3的改進版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。 決策樹 ? 特點 : – 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 – 不需要昂貴的的計算代價 – 決策樹相對容易解釋 – 決策樹是學習離散值函數(shù)的典型代表 – 決策數(shù)對于噪聲的干擾具有相當好的魯棒性 – 冗余屬性不會對決策樹的準確率造成不利影響 – 數(shù)據(jù)碎片問題。隨著數(shù)的生長，可能導致葉結(jié)點記錄數(shù)太少，對于葉結(jié)點代表的類，不能做出具有統(tǒng)計意義的判決 – 子樹可能在決策樹中重復多次。使決策樹過于復雜 子樹重復問題 PQ RS 0 10 1QS 00 1? Same subtree appears in multiple branches 決策邊界 y 0 . 3 3 ? : 0 : 3 : 4 : 0y 0 . 4 7 ? : 4 : 0 : 0 : 4x 0 . 4 3 ?Y e sY e sN oN o Y e s N o0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 100 . 10 . 20 . 30 . 40 . 50 . 60 . 70 . 80 . 91xy? 斜決策樹 x + y 1 Class = + Class = Bayes Classifier ? A probabilistic framework for solving classification problems ? Conditional Probability: ? Bayes theorem: )()()|()|(APCPCAPACP ?)(),()|()(),()|(CPCAPCAPAPCAPACP??Example of Bayes Theorem ? Given: – A doctor knows that meningitis causes stiff neck 50% of the time – Prior probability of any patient having meningitis is 1/50,000 – Prior probability of any patient having stiff neck is 1/20 ? If a patient has stiff neck, what’s the probability he/she has meningitis? )( )()|()|( ???? SP MPMSPSMPBayesian Classifiers ? Consider each attribute and class label as random variables ? Given a record with attributes (A1, A2,…,An) – Goal is to predict class C – Specifically, we want to find the value of C that maximizes P(C| A1, A