決策樹的主要算法及并行

1、決策樹生成的并行算法1、決策樹生成算法概覽當(dāng)今主要的決策樹生成算法有基于信息論的ID3算法和C4。5算法和基于GINI指標(biāo)的 CART、SLIQ、SPRINT、PUBLIC 算法。其中的 C4。 5 是 ID3 算法的改進(jìn)。最早出現(xiàn)的 ID3 算法采用信息熵原理選擇測(cè)試屬性分割樣本集，只能處理具有離散型屬性 和屬性值齊全的樣本，生成形如多叉樹的決策樹。后來出現(xiàn)的 C4。 5 算法經(jīng)過改進(jìn)，能夠 直接處理連續(xù)型屬性，也能夠處理屬性值空缺的訓(xùn)練樣本。ID3系列算法和C4。5系列算法 雖然在對(duì)訓(xùn)練樣本集的學(xué)習(xí)中盡可能多地挖掘信息，但其生成的決策樹分枝較多，規(guī)模較大。 為了簡(jiǎn)化決策樹的規(guī)模，提高生成決

2、策樹的效率，又出現(xiàn)了根據(jù)GINI系數(shù)來選擇測(cè)試屬性 的決策樹算法，使得生成的決策樹可以是結(jié)構(gòu)簡(jiǎn)單、易于理解的二叉樹。根據(jù)樹剪枝的出現(xiàn) 時(shí)間，決策樹算法使用的剪枝策略可以分為預(yù)剪枝和后剪枝。大多數(shù)決策樹算法都采用后剪 枝策略，但是，后剪枝策略明顯存在將己經(jīng)生成的分枝再剪去的重復(fù)勞動(dòng)，降低了決策樹的 生成效率，因此出現(xiàn)了以 PUBLIC 算法為代表的預(yù)剪枝決策樹算法。之后，為了增加決策 樹算法的可擴(kuò)展性和并行性，SLIQ和SPRINT等并行決策樹算法被提出。下表是幾種決策 樹生成算法的比較，其中SLIQ算法和SPRINT具有并行性。點(diǎn)決策樹的結(jié)構(gòu)選擇觀試屬性的技術(shù)違理辭性的處理剪枝算法是否必麵逆立

3、測(cè)試樣本集可伸劭性可井行性ID3算法離散化分類錯(cuò)誤是差| C4 5算注悟息增訖蕊備排序分類錯(cuò)誤差差1 CART算法|二靈樹ginf系數(shù)分類雷誤否差差即,LQ算逵義14gini系數(shù)預(yù)排序w.否良好良好SPRINT算法二叉樹git ii系數(shù)MDL好好PUBLIC算法二叉樹0旳泵數(shù)顱排庫WL筲差差2、并行性算法簡(jiǎn)介2.1 SLIQ算法簡(jiǎn)介IBM的研究人員于1996年提出了 SLIQ算法。它是一種快速的、可伸縮的決策樹算法。 它即可以處理離散屬性也可以處理連續(xù)屬性。 SLIQ 采用廣度優(yōu)先方法生成決策樹，采用基 于 MDL 的剪枝策略。 SLIQ 算法生成的是一棵二叉樹。在每個(gè)非葉節(jié)點(diǎn)需選擇一個(gè)測(cè)試屬

4、 性，形成一個(gè)測(cè)試條件，滿足此條件的樣本被分到左子樹，不滿足的被分到右子樹。對(duì)某連 續(xù)屬性a,假定其測(cè)試條件為a=v,v是屬性a的一個(gè)取值，假設(shè)a有n個(gè)值，則v是在比較 n-1種可能分割的GINI系數(shù)后得出的。這一過程中，對(duì)a的n個(gè)值排序是很耗時(shí)的工作， SLIQ算法為提高排序效率采用預(yù)排序方法：對(duì)離散屬性A,它的測(cè)試條件為,盧 是A的最佳測(cè)試子集，s是A的不同取值的集合。若A有n個(gè)不同取值，則s有甘個(gè)候選 子集，在其中選出具有最佳分割效果的子集也很耗時(shí)。SLIQ提出一種快速求S的方法：當(dāng) S的候選子集小于某一個(gè)閾值時(shí)，s的所有子集都作為候選；否則，采用貪心算法，S初始 為空，選出S的一個(gè)元素

5、加入S使得成為最佳分割，不斷補(bǔ)充S直到再增加任何元素到S都不能得到更好分割為止。SLIQ算法的具體描述如下：首先，在挖掘之前， SLIQ 縱向分割樣本集，為每個(gè)屬性建立一個(gè)屬性表，表項(xiàng)形如 ，屬性表按屬性值大小排序；為類別屬性建立一個(gè)類表，表項(xiàng)形如 類 別，樣本所在的葉節(jié)點(diǎn)），類表不需要事先排序，初始，類表中所有項(xiàng)都在根節(jié)點(diǎn)。類表必 須常駐主存，而屬性表則可放在輔存上，當(dāng)需要時(shí)再調(diào)入主存。然后，開始為當(dāng)前決策樹中尚待分裂的葉節(jié)點(diǎn)選擇測(cè)試屬性：依次掃描每個(gè)屬性表，對(duì)每個(gè)屬性表，每掃描一項(xiàng)時(shí)，根 據(jù)樣本序號(hào)找到相應(yīng)類表中的項(xiàng)，修改在當(dāng)前位置分割的類分布直方圖，如圖2。對(duì)于連續(xù) 屬性，每掃描屬性表中

6、的一項(xiàng)就計(jì)算當(dāng)前分割的 GINI 系數(shù)，所需的分布信息可由直方圖取 得：對(duì)于離散屬性，待掃描完屬性表后得出最佳分割子集?？梢钥闯觯琒LIQ在對(duì)所有屬性 表掃描完畢后，即可得到當(dāng)前決策樹中所有葉子節(jié)點(diǎn)的最佳分割方案。這是一種廣度優(yōu)先生 長(zhǎng)樹策略。接著，根據(jù)得到的分割方案，當(dāng)前決策樹生成新的葉子節(jié)點(diǎn)，將樣本按測(cè)試條件 重新分到新的葉子節(jié)點(diǎn)中，修改類表中的各項(xiàng)。最后，當(dāng)所有葉子節(jié)點(diǎn)中的樣本都屬于同一 類別時(shí)算法終止。為提高效率，在樹的每一層生長(zhǎng)過程中，如果有些葉子節(jié)點(diǎn)己經(jīng)不可分割， 則將此葉子節(jié)點(diǎn)中的所有樣本從各個(gè)屬性表中刪除。屬性表類表15屬性表類表152GN2404BN2606GN3651BN3

7、753GN31005GN3當(dāng)掃描到麻性我的第一項(xiàng)吋I測(cè)試條件為H2S方圖中.滿足 條件的樣本分布記錄在L行.不滿足的記錄在Rfn H2. H3為掃描 到屈性表第一項(xiàng)時(shí)，當(dāng)前樹各個(gè)葉節(jié)點(diǎn)的宜方圖，H2，H3列掃描 到屈性表第二項(xiàng)時(shí)的當(dāng)前樹各個(gè)葉節(jié)點(diǎn)的真方圖*圖 2 直方圖實(shí)例SLIQ算法可以處理大規(guī)模的訓(xùn)練樣本集，具有較好的伸縮性。SLIQ算法首次提出在算法中 運(yùn)用一些特殊數(shù)據(jù)結(jié)構(gòu)如屬性表和類表。 SLIQ 算法在執(zhí)行過程中需要隨時(shí)修改類表，因此 類表常駐內(nèi)存，而類表的大小會(huì)隨著訓(xùn)練樣本集的增大而增大，因此SLIQ算法依然不能擺 脫主存容量的限制。由于使用了新的數(shù)據(jù)結(jié)構(gòu)，SLIQ算法可并行化。在

8、有多處理器的并行 環(huán)境中，假設(shè)每個(gè)處理器都各自擁有獨(dú)立的主存和輔存。SLIQ算法可將屬性表平均分配給 各個(gè)處理器，使決策樹的生成并行進(jìn)行。對(duì)于類表，可以讓每個(gè)處理器都有一份，或?qū)⑺?割后分給各個(gè)處理器。根據(jù)對(duì)類表的不同處理，并行 SLIQ 算法可分為 SLIQ/R 和 SLIQ/D 兩種版本。 SLIQ/R 為每個(gè)處理器都拷貝一份全局的類表。在各個(gè)處理器并行掃描屬性表的 過程中，對(duì)某個(gè)處理器中的類表進(jìn)行的修改都要及時(shí)更新到各個(gè)處理器的類表中。處理器間 要不斷通信，保證每一時(shí)刻各個(gè)處理器上的類表一樣。 SLIQ/D 將類表分割后再平均分給各 個(gè)處理器。它的問題是，在某個(gè)處理器中掃描到的屬性項(xiàng)，

9、它對(duì)應(yīng)的類表可能在另一個(gè)處理 器中，處理器間也要通過通信來更新類表。2.2 SPRINT 算法簡(jiǎn)介SPRINT 算法的目的就是要徹底解決主存容量的限制，能夠處理其它任何算法都不適用的超 大規(guī)模訓(xùn)練樣本集，并能有效地生成決策樹。SPRINT算法的建樹過程類似SLIQ算法，偽 代碼描述如下，其中T表示當(dāng)前樣本集。創(chuàng)建糧節(jié)點(diǎn)N;IFT都黒于岡一類別則返回N為葉節(jié)點(diǎn)；(3 FOR EACH T中的屬性A執(zhí)行A上的所有可能劃分.找出最佳劃分將T分劃為TX T2;(7)調(diào)用 sprintformtree (T)；(S) 用 sprEntfarmtree (Tj;SPRINT算法使用了與SLIQ不同的數(shù)據(jù)結(jié)

10、構(gòu)。不使用獨(dú)立的類表，而是為每個(gè)屬性建立一 個(gè)屬性表，表項(xiàng)形如屬性值，類別，樣本序號(hào))。連續(xù)屬性的屬性表要按屬性值預(yù)排序；離 散屬性表則沒有預(yù)排序過程。屬性表不須常駐內(nèi)存。在建樹過程中，SPRINT為每個(gè)待分裂 節(jié)點(diǎn)設(shè)立一個(gè)類直方圖。連續(xù)屬性的直方圖結(jié)構(gòu)同SLIQ，離散屬性的直方圖，也稱計(jì)數(shù)矩 陣，記錄了每個(gè)不同取值的樣本在各個(gè)類別中的個(gè)數(shù)。當(dāng)測(cè)試條件形成，節(jié)點(diǎn)分裂時(shí)，屬性 表也分裂到新的葉節(jié)點(diǎn)中。每個(gè)待分裂的葉節(jié)點(diǎn)對(duì)應(yīng)一張屬性表，SPRINT掃描屬性表尋找 最佳分割，計(jì)算最佳分割的信息可從相應(yīng)的直方圖獲得，因此計(jì)算每次分割至多只需要一張 屬性表的直方圖常駐內(nèi)存。由于直方圖的大小不會(huì)隨屬性表的

11、增大而增大，SPRINT算法完 全擺脫了主存容量的限制。與SLIQ算法一樣，SPRINT算法也具有并行性。并行SPRINT 算法將訓(xùn)練樣本集平均分配給各個(gè)處理器，各個(gè)處理器可產(chǎn)生自己的屬性表。對(duì)離散屬性的 屬性表，不用再進(jìn)行處理，但對(duì)連續(xù)屬性的屬性表，需先綜合各個(gè)局部屬性表，按屬性值排 序后再分割分配到各個(gè)處理器。對(duì)當(dāng)前待分裂葉子節(jié)點(diǎn)，對(duì)應(yīng)的屬性表分散在各個(gè)處理器， 各個(gè)處理器可并行掃描各自的局部屬性表尋找局部最佳分割，為計(jì)算最佳分割，各個(gè)處理器 有一個(gè)局部直方圖，但直方圖需記錄反映全局的信息。各個(gè)處理器得到的局部最佳分割要進(jìn) 過再次比較得到全局最佳分割，用全局最佳分割來最終分裂葉節(jié)點(diǎn)，進(jìn)而分

12、割屬性表。2.3分布式ID3算法南京師范大學(xué)的戴南提出了一種在分布式數(shù)據(jù)庫環(huán)境下挖掘分類決策樹的算法：分布式 ID3 算法。它的具體過程如下：首先對(duì)分布存儲(chǔ)在各個(gè)局部站點(diǎn)的數(shù)據(jù)庫進(jìn)行預(yù)處理，形成 訓(xùn)練樣本集。然后，在各個(gè)局部站點(diǎn)上運(yùn)用一種可伸縮的 ID3 算法，對(duì)各自的局部樣本集 進(jìn)行分割?？缮炜s ID3 算法與傳統(tǒng) ID3 算法的區(qū)別在于它引進(jìn)了一種新的數(shù)據(jù)結(jié)構(gòu)屬性按 類別分布表，該表記錄了當(dāng)前待分割樣本集中所有屬性在各個(gè)類別上的分布計(jì)數(shù)。求當(dāng)前所 有屬性的信息增益所需要的信息全部可以從屬性按類別分布表中獲得。局部站點(diǎn)在選擇當(dāng)前 樣本集的測(cè)試屬性時(shí)，將當(dāng)前樣本集的屬性按類別分布表傳給全局站點(diǎn)

13、，全局站點(diǎn)通過綜合 局部站點(diǎn)傳來的，處在同一層次的所有待分割樣本集的屬性按類別分布表，求出這一層次的 全局屬性按類別分布表，并根據(jù)它求出具有最大信息增益的屬性作為最終測(cè)試屬性，再將它 發(fā)回給各個(gè)局部站點(diǎn)，各個(gè)局部站點(diǎn)使用從全局站點(diǎn)接收到的測(cè)試屬性繼續(xù)分割各自的樣本 集。在從全局站點(diǎn)接收到測(cè)試屬性之前，各個(gè)局部站點(diǎn)必須等待。這使得所有局部站點(diǎn)同步 處理的樣本集處在決策樹的同一層次，當(dāng)全局站點(diǎn)與所有局部站點(diǎn)完成一次通信，就有一層 全局決策樹的信息產(chǎn)生，每層決策樹信息都存放在全局站點(diǎn)上，當(dāng)所有局部站點(diǎn)上的樣本集 都分割完畢后，最終決策樹也在全局站點(diǎn)上生成。分布式ID3算法可由圖3描述。開始否是否否否

14、皓束結(jié)束超否從全局站點(diǎn)接 收到全局囂試展性斗前待分樣本卑 是苦不可再井別是否対腐性按類 別分布表是否還冇待分割 樣本集繪否所有陶部站點(diǎn) 都遞交了信息抱否時(shí)部站點(diǎn)上的 算法郁執(zhí)行完平形成決範(fàn)樹的一個(gè)葉節(jié)點(diǎn), 將相關(guān)信息傳給全局站點(diǎn)*開始計(jì)算全同測(cè)試屁性境送暗齊節(jié)同部站點(diǎn)從局部站點(diǎn)接收決聚樹信息向開始否是否否否皓束結(jié)束超否從全局站點(diǎn)接 收到全局囂試展性斗前待分樣本卑 是苦不可再井別是否対腐性按類 別分布表是否還冇待分割 樣本集繪否所有陶部站點(diǎn) 都遞交了信息抱否時(shí)部站點(diǎn)上的 算法郁執(zhí)行完平形成決範(fàn)樹的一個(gè)葉節(jié)點(diǎn), 將相關(guān)信息傳給全局站點(diǎn)*開始計(jì)算全同測(cè)試屁性境送暗齊節(jié)同部站點(diǎn)從局部站點(diǎn)接收決聚樹信息向全局站點(diǎn)傳送當(dāng)前屈 性按類別分布表從局部站點(diǎn)接收厲性按類別分布表辨別從同部站點(diǎn)接收的信息劃分當(dāng)前樣本集輸出垠終決簟擁圖 3 分布式 ID3 算法分布式ID3算法使用基于信息增益的方法求測(cè)試屬性，省去了 SLIQ和SPRINT對(duì)連續(xù) 屬性預(yù)排序所耗費(fèi)的時(shí)間。由于使用了新的數(shù)據(jù)結(jié)構(gòu)：屬性按類別分布表，分布式 ID3 算 法具有很好的伸縮性和并行性：一旦樣本集的數(shù)據(jù)庫結(jié)構(gòu)確定，樣本集的屬性按類別分布表 不會(huì)隨樣本集的增大而增大。因此分布式 ID3 算法可以突破主存容量的限制，處理超大規(guī) 模的樣本集；由于訓(xùn)練樣本集在各個(gè)局部站點(diǎn)上同構(gòu)分布，局部站點(diǎn)在分割每一