决策树资料汇总
2012年8月26日 決策樹（Decision tree） 決策樹是以實例為基礎(chǔ)的歸納學(xué)習(xí)算法。 它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值的比較，并根據(jù)不同的屬性值從該結(jié)點向下分支，葉結(jié)點是要學(xué)習(xí)劃分的類。從根到葉結(jié)點的一條路徑就對應(yīng)著一條合取規(guī)則，整個決策樹就對應(yīng)著一組析取表達式規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進的算法，其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比較有代表性的兩個算法。 ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實現(xiàn)對數(shù)據(jù)的歸納分類。以下是一些信息論的基本概念： 定義1：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為Log2(n) 定義2：若有n個消息，其給定概率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為 I(p)=-(i=1 to n求和)piLog2(pi)。 定義3：若一個記錄集合T根據(jù)類別屬性的值被分成互相獨立的類C1C2..Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|) 定義4：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為： Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti)) 定義5：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為： Gain(X, T)=Info(T)-Info(X, T) ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創(chuàng)建一個節(jié)點，并以該節(jié)點的屬性標(biāo)記，對該屬性的每個值創(chuàng)建一個分支據(jù)此劃分樣本. 決策樹的構(gòu)造 ? 這個數(shù)據(jù)集來自Mitchell的機器學(xué)習(xí)，叫做是否去打網(wǎng)球play-tennis,以下數(shù)據(jù)仍然是從帶逗號分割的文本文件，復(fù)制到紀(jì)事本，把后綴直接改為.csv就可以拿Excel打開： *play-tennis data，其中6個變量依次為：編號、天氣{Sunny、Overcast、Rain}、溫度{熱、冷、適中}、濕度{高、正常}、風(fēng)力{強、弱}以及最后是否去玩的決策{是、否}。一個建議是把這些數(shù)據(jù)導(dǎo)入Excel后，另復(fù)制一份去掉變量的數(shù)據(jù)到另外一個工作簿，即只保留14個觀測值。這樣可以方便地使用Excel的排序功能，隨時查看每個變量的取值到底有多少。*/ NO. , Outlook , Temperature , Humidity , Wind , Play 1 , Sunny , Hot , High , Weak , No 2 , Sunny , Hot , High , Strong , No 3 , Overcast , Hot , High , Weak , Yes 4 , Rain , Mild , High , Weak , Yes 5 , Rain , Cool , Normal , Weak , Yes 6 , Rain , Cool , Normal , Strong , No 7 , Overcast , Cool , Normal , Strong , Yes 8 , Sunny , Mild , High , Weak , No 9 , Sunny , Cool , Normal , Weak , Yes 10 , Rain , Mild , Normal , Weak , Yes 11 , Sunny , Mild , Normal , Strong , Yes 12 , Overcast , Mild , High , Strong , Yes 13 , Overcast , Hot , Normal , Weak , Yes 14 , Rain , Mild , High , Strong , No 這里我們先不討論算法（這里用的是ID3/C4.5），把一棵決策樹建立起來再說。我們要建立的決策樹的形式類似于“如果天氣怎么樣，去玩；否則，怎么著怎么著”的樹形分叉。那么問題是用哪個屬性（即變量，如天氣、溫度、濕度和風(fēng)力）最適合充當(dāng)這顆樹的根節(jié)點，在它上面沒有其他節(jié)點，其他的屬性都是它的后續(xù)節(jié)點。借用信息論的概念，我們用一個統(tǒng)計量，“信息增益”（Information Gain）來衡量一個屬性區(qū)分以上數(shù)據(jù)樣本的能力。信息增益量越大，這個屬性作為一棵樹的根節(jié)點就能使這棵樹更簡潔，比如說一棵樹可以這么讀成，如果風(fēng)力弱，就去玩；風(fēng)力強，再按天氣、溫度等分情況討論，此時用風(fēng)力作為這棵樹的根節(jié)點就很有價值。如果說，風(fēng)力弱，再又天氣晴朗，就去玩；如果風(fēng)力強，再又怎么怎么分情況討論，這棵樹相比就不夠簡潔了。計算信息增益的公式需要用到“熵”（Entropy）。名詞越來越多，讓我們通過手工計算記住它們的計算方法，把Excel打開： 1 計算熵 我們檢查的屬性是是否出去玩。用Excel對上面數(shù)據(jù)的play變量的各個取值排個序（這個工作簿里把“play”這個詞去掉），一共是14條記錄，你能數(shù)出取值為yes的記錄有9個，取值為no的有5個，我們說這個樣本里有9個正例，5 個負例，記為S(9+,5-)，S是樣本的意思(Sample)。這里熵記為Entropy(S),計算公式為： Entropy(S)= -(9/14)*log(9/14)-(5/14)*log(5/14) 解釋一下，9/14是正例的個數(shù)與總記錄之比，同樣5/14是負例占總記錄的比例。log(.)是以2為底的對數(shù)（我們知道以e為底的對數(shù)稱為自然對數(shù)，記為ln(.),lg(.)表示以10為底的對數(shù)）。在Excel里我們可以隨便找一個空白的單元格，鍵入以下公式即得0.940： =-(9/14)*LOG(9/14,2)-(5/14)*LOG(5/14,2) 這里L(fēng)OG(9/14,2)中的“2”表示以2為底。類似地，如果你習(xí)慣用Matlab做數(shù)學(xué)運算本，公式為 -(9/14)*log2(9/14)-(5/14)*log2(5/14) 其中“2”的含義與上同。 總結(jié)：在這個例子中，我們的輸出屬性（我們要檢查的屬性）“play”只有兩個取值，同樣地，如果輸出屬性的取值大于2，公式是對成的，一樣的形式，連加就是，找到各個取值的個數(shù)，求出各自的比例。如果樣本具有二元輸出屬性，其熵的公式為 ? Entropy(S) =-(p+)*log(p+)-(p-)*log(p-) 其中，p+、p-分別為正例和負例占總記錄的比例。輸出屬性取值大于2的情況，公式是對稱的。 ? 2 分別以Wind、Humidity、Outlook和Temperature作為根節(jié)點，計算其信息增益 ? 可以數(shù)得，屬性Wind中取值為Weak的記錄有Normal的記錄有8條，其中正例6個，負例2個；同樣，取值為Strong的記錄6個，正例負例個3個。我們可以計算相應(yīng)的熵為： Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811 Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0 現(xiàn)在就可以計算出相應(yīng)的信息增益了： Gain(Wind)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940-(8/14)*0.811-(6/14)*1.0=0.048 這個公式的奧秘在于，8/14是屬性Wind取值為Weak的個數(shù)占總記錄的比例，同樣6/14是其取值為Strong的記錄個數(shù)與總記錄數(shù)之比。 同理，如果以Humidity作為根節(jié)點： Entropy(High)=0.985 ; Entropy(Normal)=0.592 Gain(Humidity)=0.940-(7/14)*Entropy(High)-(7/14)*Entropy(Normal)=0.151 以O(shè)utlook作為根節(jié)點： Entropy(Sunny)=0.971 ; Entropy(Overcast)=0.0 ; Entropy(Rain)=0.971 Gain(Outlook)=0.940-(5/14)*Entropy(Sunny)-(4/14)*Entropy(Overcast)-(5/14)*Entropy(Rain)=0.247 以Temperature作為根節(jié)點： Entropy(Cool)=0.811 ; Entropy(Hot)=1.0 ; Entropy(Mild)=0.918 Gain(Temperature)=0.940-(4/14)*Entropy(Cool)-(4/14)*Entropy(Hot)-(6/14)*Entropy(Mild)=0.029 這樣我們就得到了以上四個屬性相應(yīng)的信息增益值： Gain(Wind)=0.048 ；Gain(Humidity)=0.151 ； Gain(Outlook)=0.247 ；Gain(Temperature)=0.029 最后按照信息增益最大的原則選Outlook為根節(jié)點。子節(jié)點重復(fù)上面的步驟。這顆樹可以是這樣的，它讀起來就跟你認為的那樣： ? 參考資料： 1.王厚峰，“機器學(xué)習(xí)‘課程講義，2007年春季學(xué)期，北京大學(xué)軟件與微電子學(xué)院 2.Mitchell,《機器學(xué)習(xí)》，曾華軍等譯，北京：機械工業(yè)出版社，2003 ? ? (2) C4.5算法 C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進： 1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足； 2) 在樹構(gòu)造過程中進行剪枝； 3) 能夠完成對連續(xù)屬性的離散化處理； 4) 能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。 C4.5算法與其它分類算法如統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)等比較起來有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。 (3) SLIQ算法 SLIQ算法對C4.5決策樹分類算法的實現(xiàn)方法進行了改進，在決策樹的構(gòu)造過程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。 1)預(yù)排序。對于連續(xù)屬性在每個內(nèi)部結(jié)點尋找其最優(yōu)分裂標(biāo)準(zhǔn)時，都需要對訓(xùn)練集按照該屬性的取值進行排序，而排序是很浪費時間的操作。為此，SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對每個屬性的取值，把所有的記錄按照從小到大的順序進行排序，以消除在決策樹的每個結(jié)點對數(shù)據(jù)集進行的排序。具體實現(xiàn)時，需要為訓(xùn)練數(shù)據(jù)集的每個屬性創(chuàng)建一個屬性列表，為類別屬性創(chuàng)建一個類別列表。 2)廣度優(yōu)先策略。在C4.5算法中，樹的構(gòu)造是按照深度優(yōu)先策略完成的，需要對每個屬性列表在每個結(jié)點處都進行一遍掃描，費時很多，為此，SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹，即在決策樹的每一層只需對每個屬性列表掃描一次，就可以為當(dāng)前決策樹中每個葉子結(jié)點找到最優(yōu)分裂標(biāo)準(zhǔn)。 SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個數(shù)和屬性個數(shù)增長的可伸縮性。 然而它仍然存在如下缺點： 1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。 2)由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達到隨記錄數(shù)目增長的線性可伸縮性。 (4)SPRINT算法 為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進一步改進了決策樹算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個屬性列表中。這樣，在遍歷每個屬性列表尋找當(dāng)前結(jié)點的最優(yōu)分裂標(biāo)準(zhǔn)時，不必參照其他信息，將對結(jié)點的分裂表現(xiàn)在對屬性列表的分裂，即將每個屬性列表分成兩個，分別存放屬于各個結(jié)點的記錄。 SPRINT算法的優(yōu)點是在尋找每個結(jié)點的最優(yōu)分裂標(biāo)準(zhǔn)時變得更簡單。其缺點是對非分裂屬性的屬性列表進行分裂變得很困難。解決的辦法是對分裂屬性進行分裂時用哈希表記錄下每個記錄屬于哪個孩子結(jié)點，若內(nèi)存能夠容納下整個哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時，哈希表可能無法在內(nèi)存容納，此時分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。 其他資料： 本文是《Mitchell機器學(xué)習(xí)》《JiaweiHan數(shù)據(jù)挖掘概念與技術(shù)》的學(xué)習(xí)筆記 概覽一 1 決策樹就是實例屬性值約束的合取的析取式。從樹根到樹葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取。 2 決策樹建立時，使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力，在每個結(jié)點選取能最好地分類樣例的屬性，且從不回溯重新考慮以前的選擇。因此，決策樹學(xué)習(xí)是一個自頂向下的貪婪搜索算法。 3 每一步都使用統(tǒng)計測試使決策樹學(xué)習(xí)對錯誤有很好的健壯性。 4 決策樹學(xué)習(xí)的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間。每個有限離散值函數(shù)都可被表示為某個決策樹。因此，決策樹學(xué)習(xí)(ID3)的歸納偏置來自它的搜索策略，即較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根結(jié)點的樹優(yōu)先。這種類型的偏置稱為優(yōu)選偏置或搜索偏置。而候選消除算法的歸納偏置來自它對搜索空間的定義，被稱為限定偏置或語言偏置。 5 奧坎姆剃刀：優(yōu)先選擇擬合數(shù)據(jù)的最簡單假設(shè)。 一個解釋： 找到一個短的但同時與訓(xùn)練數(shù)據(jù)擬合的假設(shè)的可能性較小，不太可能是統(tǒng)計巧合。 兩個難題： I． ? ? ? ? ? ? ? 根據(jù)什么相信短描述的決策樹組成的小假設(shè)集合比其它眾多可定義的小假設(shè)集合更適當(dāng)？ II． ? ? ? ? ? ?假設(shè)的大小由學(xué)習(xí)器內(nèi)部使用的特定表示決定。不同的內(nèi)部表示方式，據(jù)奧坎姆剃刀產(chǎn)生兩個不同的假設(shè)。 6 處理不同代價屬性 使屬性代價參與屬性選擇度量，如將信息增益除以屬性代價。這在考慮獲取屬性的不同代價的現(xiàn)實條件時是很有用處的。 概覽二 1 在決策樹歸納分類之前，假設(shè)數(shù)據(jù)是預(yù)處理過的。不可忽略地，這其中包括數(shù)據(jù)清理，相關(guān)分析，數(shù)據(jù)變換與歸約。具體實現(xiàn)及方法另述。 2 (離散)分類和（數(shù)值）預(yù)測是預(yù)測問題的兩種主要類型，決策樹一般用于分類。 3 歸納決策樹時對于樹的每一層都需要掃描一遍D中的元組，因此算法的計算復(fù)雜度為O(n*|D|*log|D|)。 4 決策樹歸納的scalability （1）SLIQ使用若干駐留磁盤的屬性列表和單個駐留內(nèi)存的類列表 （2）SPRINT使用另一種屬性列表，易于并行，消除了所有內(nèi)存限制，但需要正比于訓(xùn)練集的散列樹。 （3）RainForest對每個屬性維護一個AVC（屬性-值-類）集，可以選擇任何屬性度量。 （4）BOAT使用稱作bootstrap的統(tǒng)計學(xué)技術(shù)，從子集構(gòu)造多棵樹后合并構(gòu)造接近于真實樹的新樹。可使用二元分裂的屬性選擇度量，如Gini指標(biāo)。只需掃描訓(xùn)練集兩次，可以增量更新。 綜述 1 屬性選擇度量：信息增益（ID3使用） I 熵(entropy)刻畫了任意樣例集的純度，熵值越大表示越不純，識別其中元組分類所需要的平均信息量就越大。公式如下： 熵的最大可能為logc。信息論中熵的一種解釋是，確定要編碼集合S中任意成員的分類所需要的最少二進制位數(shù)。所以底數(shù)都是2。 II 信息增益Gain(S,A)有幾種解釋： 由于知道屬性A的值而導(dǎo)致的期望熵減少； 原來的信息需求與新的需求的差，即信息需求的期望減少。 公式如下，第二項描述的是每個子集的熵的加權(quán)和： 2 屬性選擇度量：增益率（C4.5使用） I 信息增益度量存在一個內(nèi)在偏置，它偏袒具有較多值的屬性。 II 分裂信息：S關(guān)于屬性A的各值的熵，用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性，懲罰可取較多值的屬性。公式如下： III 增益率： IV 增益率存在的問題：當(dāng)Si約等于S時，分裂信息趨向于0，GainRatio變得不穩(wěn)定。可以先計算每個屬性的增益，僅對增益高過平均值的屬性應(yīng)用增益比率測試。 3 屬性選擇度量：Gini指標(biāo)（CART使用） I Gini指標(biāo)度量數(shù)據(jù)劃分或訓(xùn)練元組集D的不純度，如下，其中pi=|C(i,D)|/|D|： II 只考慮屬性的二元劃分。因此對于有v個值的屬性A，存在2^v-2中劃分。從中選擇該屬性產(chǎn)生最小Gini指標(biāo)的子集作為分裂子集。 III 對連續(xù)值屬性，考慮每對（排序的）相鄰值之間的中點取作可能的分裂點。可以證明，產(chǎn)生最大信息增益的分裂點必定位于這樣的邊界中。 4 樹剪枝 (1) 當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少時，決策樹歸納算法會出現(xiàn)過度擬合。另外決策樹可能很大，很復(fù)雜，難以理解。因此需要修剪決策樹。 (2) 兩種常用的剪枝方法：先剪枝(即提前停止樹增長)，后剪枝。對于前者，精確地估計何時停止樹增長非常困難，一般進行統(tǒng)計測試來估計擴展一個特定的節(jié)點是否可能改善質(zhì)量，如用卡方測試統(tǒng)計顯著性，另外可以使用信息增益，Gini指標(biāo)及預(yù)定義的閾值。后剪枝更常用。 (3) 代價復(fù)雜度后剪枝(CART使用)。代價復(fù)雜度是樹葉結(jié)點個數(shù)與錯誤率的函數(shù)，使用與訓(xùn)練和測試集合完全不同的修剪驗證集合來評估。 (4) 悲觀剪枝（C4.5使用）。不需要剪枝集，使用訓(xùn)練集評估錯誤率，但是假定此估計精度為二項分布，計算標(biāo)準(zhǔn)差，對于一個給定的置信區(qū)間，采用下界來估計錯誤率。雖然這種啟發(fā)式方法不是統(tǒng)計有效的，但是它在實踐中是有效的。 (5) 規(guī)則后修剪。將決策樹轉(zhuǎn)化為等價的IF-THEN規(guī)則，如何提取另述，并嘗試修剪每個規(guī)則的每個前件(preconditions)。這樣的好處是使對于決策樹上不同的路徑，關(guān)于一個屬性測試的修剪決策可以不同。另外避免了修剪根結(jié)點后如何組織其子節(jié)點的問題。 (6) 以明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，如最小描述長度準(zhǔn)則（MDL），而不是根據(jù)估計的錯誤率。 問題： 1 關(guān)于奧坎姆剃刀的第II個難題，進化產(chǎn)生的內(nèi)部表示使得學(xué)習(xí)算法的歸納偏置成為seft-fulfilling prophecy。只因為它改變內(nèi)部表示比改變學(xué)習(xí)算法更容易。推理中盡是假設(shè)？進化何以成立？ 2 證明決策樹學(xué)習(xí)的時間復(fù)雜度為O（n*|D|*log|D|）？ 3 信息論中的熵？ 4 為什么Gini指標(biāo)只能用作二元劃分？ 5 證明產(chǎn)生最大信息增益的分裂點必定位于相鄰值之間的中點中？ 6 MDL準(zhǔn)則如何用于樹剪枝？ http://www.cnblogs.com/zhaoqian/archive/2011/01/25/1944717.html http://www.docin.com/p-113903819.html 決策樹構(gòu)造法ID 如果學(xué)習(xí)的任務(wù)是對一個大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結(jié)構(gòu)的屬性值對來表示，則可以采用示例學(xué)習(xí)方法的一個變種──決策樹學(xué)習(xí)，其代表性的算法是昆蘭（J.R.Quinlan，1986）提出的ID3。 ID3的輸入是描述各種已知類別實例的列表。例子由預(yù)先定義的屬性值對來表示。歸納推理產(chǎn)生的結(jié)果不是以往討論的那種合取表達式，而是一棵決策樹（也稱判別樹，并可轉(zhuǎn)而表示為決策規(guī)則的一個集合），用它可正確地區(qū)分所有給定例子的類屬。 樹中的每一非葉節(jié)點對應(yīng)一個需測試的屬性，每個分叉就是該屬性可能的取值；樹的葉節(jié)點則指示一個例子事物的類別。ID3的顯著優(yōu)點是歸納學(xué)習(xí)花費的時間和所給任務(wù)的困難度（取決于例子個數(shù)，用來描述對象的屬性數(shù)，所學(xué)習(xí)概念的復(fù)雜度即決策樹的節(jié)點數(shù)等）僅成線性增長關(guān)系。當(dāng)然，ID3只能處理用屬性-值對表示的例子。 在ID3中, 每一個例子用相同的一組屬性來表示，每一個屬性又有自身的屬性值集，如"顏色"屬性可取值是{紅、綠、蘭}等。構(gòu)造決策樹的目的是為了對事物作出正確的分類。決策樹形式的分類規(guī)則適用于任何的對象集Ｃ。如Ｃ是空的，那么它無需分類，對應(yīng)的決策樹也為空；如Ｃ中的對象是同一類的，那么決策樹就一個葉節(jié)點，即該類名；如果Ｃ集中的對象屬于二個不同的類別，那未我們可以選取一個對象的屬性，隨后按其可能值把Ｃ劃分成一些不相交的子集C1，C2，…，Cn，其中Ci是含有所選屬性的第ｉ個值的那些對象集。對每一個這樣的子集又可以用同樣的策略處理，最后的結(jié)果是一棵樹。 下面給出一個關(guān)于人分類的例子（對象）集，并預(yù)先定義了指定的一組屬性及其可取值：高度{高，矮}，發(fā)色{黑色, 紅色，金色}和眼睛{蘭色，棕色}。這里，將人分為兩類，分別以＋、－來指示。 高度 發(fā)色 眼睛 類別 ─────────────────────────── 矮 黑色 蘭色 － 高 黑色 蘭色 － 矮 金色 蘭色 ＋ 高 金色 棕色 － 高 黑色 棕色 － 矮 金色 棕色 － 高 金色 蘭色 ＋ 高 紅色 蘭色 ＋ 如我們首先選取"發(fā)色"為樹的根節(jié)點，即可獲得圖6.11所示的決策樹。 相應(yīng)于"黑色"，"紅色"和"金色"三值都有一個對象子集。隨后我們再測試"金色"這一分支，又按屬性"眼睛"把其所含的對象集劃分成蘭色和棕色二類。至此，所有葉結(jié)點相應(yīng)的對象子集只含同一類的對象，我們就可以用相應(yīng)的類別名（本例中的+ 和 -）來取代各子集，得到一決策樹，如圖6.12所示。 一個對象所屬類的判別從決策樹的根開始，首先依據(jù)根節(jié)點指示的屬性（發(fā)色），選擇與該對象屬性值相應(yīng)的分支；然后，以同樣的方式進行下去, 一直到達葉節(jié)點。有時判別一個對象的類別，由于從根到葉節(jié)點的路徑較短，只要測試少量的屬性。如上例中，若"發(fā)色"的值是"黑色"或"紅色"，則對象就可以直接歸屬相應(yīng)的類別，而不必再去判定其它屬性的取值；若為"金色"，則再測試一次"眼睛"的值（而不必考慮"高度"）就可以進行判別。 若不存在這樣的二個對象:它們在每個屬性上都具有相同的值，卻屬于不同的類別，那么這種生成決策樹的過程是可行的。產(chǎn)生這種歸納學(xué)習(xí)方法的關(guān)鍵在于如何選擇一系列有用的屬性來測試一個對象集，以使生成的決策樹是最小的。ID3采用了香農(nóng)（Shannon）信息論中的方法以使分類時期望（平均）的測試次數(shù)最小。 一個決策樹可看成一個信息源，即給定一個對象，可從決策樹產(chǎn)生一個該對象所屬類別的消息(比如類別"+"或"-")。決策樹的復(fù)雜程度與借助這個消息所傳遞的信息量密切相關(guān)。若決策樹傳遞的不同類別消息的概率用P+ (對應(yīng)于"+"類)和P-表示(對應(yīng)于"-"類)，那么這個消息的期望信息量為: - P+log2P+ - P-log2P- 對給定的物體集C，我們可以把這概率近似地表示為相對頻率, 此時P+和P-分別等于C中類別為"+"和"-"的對象所占的比例。 從C集對應(yīng)的決策樹中得到消息的期望信息量記為M(C)，并定義M({})=0。 對于上述例子，C集有八個例子，三個為"+"，五為"-"，則 M(C) = -（3/8）log2（3/8）-（5/8）log2（5/8）= 0.954 bits 圖6.13是一個局部決策樹，A為構(gòu)造決策樹時下一個可能選取的屬性，Ai為屬性A的值且是互斥的。屬性A將集合C劃分為若干個子集合{C1，C2，...，Cn}。設(shè)M(Ci)是值為Ai的子集Ci所對應(yīng)決策樹的期望信息量，則確定以屬性A作為樹根的決策樹的期望信息量B(C, A)可通過權(quán)值平均而得到: B(C, A)＝∑(A值為Ai的概率) * M(Ci) 同樣我們把Ai的概率用相對比例來代替，即在所有對象中具有Ai值所占的相對比例。 我們希望待選的測試屬性能使決策樹獲得最大的信息增益即M(C)-B(C, A)為最大值。因為M(C)為判別一個對象的類屬所要求的總的期望信息量，B(C,A)為按屬性A構(gòu)造局部決策樹后還需要的期望信息量。二者的差越大，說明測試這個屬性所能傳遞的信息量越大,則判別的速度也就越快。 例如，圖6.14中，我們選取的屬性為"高度"，對高度值為"高"的分支的所需期望信息量為： -（2/5）log2（2/5）-（3/5）log2（3/5）= 0.971 bits 同樣對值為"矮"的分支為: -（1/3）log2（1/3）-（2/3）log2（2/3）= 0.918 bits 則以屬性"高度"作劃分后進一步判別所需的期望信息量為： B(C,"高度") = 5/8 * 0.971 + 3/8 * 0.918 = 0.951 則測試這屬性傳遞的信息為: M(C)-B(C,"高度") = 0.954 - 0.951 = 0.003 bits。 如果我們不是選擇"高度"而選用屬性"頭發(fā)"，如圖6.12所示, 則有: B(C,"頭發(fā)") = 3/8 * 0 + 1/8 * 0 + 4/8 * 1 = 0.5 bits 則測試屬性"頭發(fā)"獲取的信息為M(C)-B(C,"頭發(fā)") = 0.945 - 0.5 = 0.45 bits。 同樣對屬性"眼睛"測試，獲得信息為0.347bits。根據(jù)最大信息量原理,ID3就選取"頭發(fā)"為決策樹的根節(jié)點屬性。 ID3通過不斷的循環(huán)處理，逐步求精決策樹，直到形成一棵完整的決策樹，即樹的葉節(jié)點所對應(yīng)的對象（例子）均屬于同一類。 這篇文章也不錯?http://blog.csdn.net/v_july_v/article/details/7577684
| ? |
|
|
轉(zhuǎn)載于:https://www.cnblogs.com/zhangleisanshi/p/5168991.html
總結(jié)
- 上一篇： 魅族MX2,小米2S,三星GT
- 下一篇： 天运旅游怎么样?好不好?值不值得报团参加