热99re久久精品精品免费,深爱婷婷国产在线精品AV,最新免费国产精品大全高清

決策樹（decision tree）分類算法

2013/10/24 16:46:35

決策樹（decision tree）分類算法決策樹是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無(wú)次序、無(wú)規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較，并根據(jù)不同的屬性值從該結(jié)點(diǎn)向下分支，葉結(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整個(gè)決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來(lái)又提出了若干改進(jìn)的算法，其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比較有代表性的兩個(gè)算法。 (1) ID3算法ID3算法的核心是：在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益（information gain）作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。其具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來(lái)對(duì)新的樣本進(jìn)行分類。某屬性的信息增益按下列方法計(jì)算。通過(guò)計(jì)算每個(gè)屬性的信息增益，并比較它們的大小，就不難獲得具有最大信息增益的屬性。設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=1,…,m)。設(shè)si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式給出：其中pi=si/s是任意樣本屬于Ci的概率。注意，對(duì)數(shù)函數(shù)以2為底，其原因是信息用二進(jìn)制編碼。設(shè)屬性A具有v個(gè)不同值{a1,a2,……,av}。可以用屬性A將S劃分為v個(gè)子集{S1,S2,……,Sv}，其中Sj中的樣本在屬性A上具有相同的值aj（j=1,2,……,v）。設(shè)sij是子集Sj中類Ci的樣本數(shù)。由A劃分成子集的熵或信息期望由下式給出：熵值越小，子集劃分的純度越高。對(duì)于給定的子集Sj，其信息期望為其中pij=sij/sj 是Sj中樣本屬于Ci的概率。在屬性A上分枝將獲得的信息增益是Gain(A)= I(s1, s2, …,sm)-E(A)ID3算法的優(yōu)點(diǎn)是：算法的理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是：只對(duì)比較小的數(shù)據(jù)集有效，且對(duì)噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹可能會(huì)隨之改變。(2) C4.5算法C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：1) 用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；2) 在樹構(gòu)造過(guò)程中進(jìn)行剪枝；3) 能夠完成對(duì)連續(xù)屬性的離散化處理；4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比較起來(lái)有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。(3) SLIQ算法SLIQ算法對(duì)C4.5決策樹分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)，在決策樹的構(gòu)造過(guò)程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。1) 預(yù)排序。對(duì)于連續(xù)屬性在每個(gè)內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，都需要對(duì)訓(xùn)練集按照該屬性的取值進(jìn)行排序，而排序是很浪費(fèi)時(shí)間的操作。為此，SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。具體實(shí)現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)建一個(gè)屬性列表，為類別屬性創(chuàng)建一個(gè)類別列表。2) 廣度優(yōu)先策略。在C4.5算法中，樹的構(gòu)造是按照深度優(yōu)先策略完成的，需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描，費(fèi)時(shí)很多，為此，SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹，即在決策樹的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個(gè)數(shù)和屬性個(gè)數(shù)增長(zhǎng)的可伸縮性。然而它仍然存在如下缺點(diǎn)：1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。2) 由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長(zhǎng)的線性可伸縮性。(4) SPRINT算法為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進(jìn)一步改進(jìn)了決策樹算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個(gè)屬性列表中。這樣，在遍歷每個(gè)屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，不必參照其他信息，將對(duì)結(jié)點(diǎn)的分裂表現(xiàn)在對(duì)屬性列表的分裂，即將每個(gè)屬性列表分成兩個(gè)，分別存放屬于各個(gè)結(jié)點(diǎn)的記錄。SPRINT算法的優(yōu)點(diǎn)是在尋找每個(gè)結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)變得更簡(jiǎn)單。其缺點(diǎn)是對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的辦法是對(duì)分裂屬性進(jìn)行分裂時(shí)用哈希表記錄下每個(gè)記錄屬于哪個(gè)孩子結(jié)點(diǎn)，若內(nèi)存能夠容納下整個(gè)哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時(shí)，哈希表可能無(wú)法在內(nèi)存容納，此時(shí)分裂只能分批執(zhí)行，這使得SPRINT算法