發(fā)信人: GzLi (笑梨), 信區(qū): DataMining
標(biāo)  題: [轉(zhuǎn)載]  數(shù)據(jù)挖掘采用技術(shù)（一）：決策樹(shù)
發(fā)信站: 南京大學(xué)小百合站 (Fri Nov  1 22:35:20 2002), 站內(nèi)信件

【 以下文字轉(zhuǎn)載自 AI 討論區(qū) 】
【 原文由 Jove 所發(fā)表 】

決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能
處理連續(xù)屬性的C4.5。有名的決策樹(shù)方法還有CART和Assistant。
決策樹(shù)構(gòu)造的輸入是一組帶有類別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉或多叉樹(shù)。二叉
樹(shù)的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為(ai = vi )的邏輯判
斷，其中ai 是屬性，vi是該屬性的某個(gè)屬性值；樹(shù)的邊是邏輯判斷的分支結(jié)果。多叉樹(shù)
（ID3）的內(nèi)部節(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹(shù)的
葉子節(jié)點(diǎn)都是類別標(biāo)記。
構(gòu)造決策樹(shù)的方法是采用自上而下的遞歸構(gòu)造。以多叉樹(shù)為例，它的構(gòu)造思路是，如果
訓(xùn)練例子集合中的所有例子是同類的，則將之作為葉子節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)容即是該類別標(biāo)記
。否則，根據(jù)某種策略選擇一個(gè)屬性，按照屬性的各個(gè)取值，把例子集合劃分為若干子
集合，使得每個(gè)子集上的所有例子在該屬性上具有同樣的屬性值。然后再依次遞歸處理
各個(gè)子集。這種思路實(shí)際上就是“分而治之”（divide-and-conquer）的道理。二叉樹(shù)
同理，差別僅在于要選擇一個(gè)好的邏輯判斷。
屬性選擇
構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩浴?duì)于同樣一組例子，可以有
很多決策樹(shù)能符合這組例子。人們研究出，一般情況下或具有較大概率地說(shuō)，樹(shù)越小則
樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩浴?由于構(gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩浴?屬性選擇依賴于各種對(duì)例子子集的不純度（impurity）度量方法。不純度度量方法包括
信息增益（informatin gain）、信息增益比（gain ratio）、Gini-index、距離度量（
distance measure）、J-measure、G統(tǒng)計(jì)、χ2統(tǒng)計(jì)、證據(jù)權(quán)重（weight of evidence）
、最小描述長(zhǎng)（MLP）、正交法（ortogonality measure）、相關(guān)度（relevance）和 R
elief。不同的度量有不同的效果，特別是對(duì)于多值屬性。
噪聲與剪枝
真實(shí)世界的數(shù)據(jù)（數(shù)據(jù)開(kāi)采的對(duì)象顯然就是真實(shí)世界數(shù)據(jù)）一般不可能是完美的，①可
能某些屬性字段上缺值（missing values）；②可能缺少必須的數(shù)據(jù)而造成數(shù)據(jù)不完整
；③可能數(shù)據(jù)不準(zhǔn)確含有噪聲甚至是錯(cuò)誤的。我們?cè)诖酥饕懻撛肼晢?wèn)題。
基本的決策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合。有噪聲情況
下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很
好的預(yù)測(cè)性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理
解。有兩種剪枝策略：向前剪枝（forward pruning）和向后剪枝（backward pruning）
。向前剪枝方法是，在生成樹(shù)的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。
向后剪枝方法是一種兩階段法：擬合－化簡(jiǎn)（fitting-and-simplifying），首先生成與
訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹(shù)，然后從樹(shù)的葉子開(kāi)始剪枝，逐步向根的方向剪。剪枝
時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合（tuning set或adjusting set），如果存在某個(gè)葉子剪去后
能使得在測(cè)試集上的準(zhǔn)確度或其它測(cè)度不降低（不變得更壞），則剪去該葉子；否則停
機(jī)。理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。剪枝過(guò)程中一般要涉及一些
統(tǒng)計(jì)參數(shù)或閾值，如停機(jī)閾值；有人提出了一種和統(tǒng)計(jì)參數(shù)無(wú)關(guān)的基于最小描述長(zhǎng)（MD
L）的有效剪枝法。
值得注意的是，剪枝并不是對(duì)所有的數(shù)據(jù)集都好，就象最小樹(shù)并不是最好（具有最大的
預(yù)測(cè)率）的樹(shù)。當(dāng)數(shù)據(jù)稀疏時(shí)，要防止過(guò)分剪枝（over-pruning）。從某種意義上講，
剪枝也是一種偏向（bias），對(duì)有些數(shù)據(jù)效果好而有的數(shù)據(jù)則效果差。
子樹(shù)復(fù)制和碎片問(wèn)題
由于屬性間存在相關(guān)性和多項(xiàng)性（一個(gè)結(jié)果可由多個(gè)條件決定）。例如，如布爾函數(shù)f 
= x1x2+x3x4中屬性x1和x2，或?qū)傩詘3和x4間不是相互獨(dú)立的、而是存在相關(guān)性；另外，
該布爾函數(shù)有多個(gè)乘積項(xiàng) x1x2和x3x4。出現(xiàn)這種情況時(shí)，生成的決策樹(shù)會(huì)有子樹(shù)復(fù)制問(wèn)
題（replication problem）。復(fù)制現(xiàn)象導(dǎo)致決策樹(shù)不易理解，同時(shí)還導(dǎo)致碎片問(wèn)題：當(dāng)
樹(shù)很大時(shí)，會(huì)造成數(shù)據(jù)集的劃分越來(lái)越小，從而預(yù)測(cè)越差。
解決子樹(shù)復(fù)制和碎片問(wèn)題的方法主要是采取特征構(gòu)造。特征構(gòu)造一般計(jì)算復(fù)雜度高，為
了降低特征構(gòu)造的代價(jià)，先是選取重要特征（或去除不相關(guān)特征）形成初始相關(guān)特征集
，再在該初始特征集的基礎(chǔ)上構(gòu)造新的復(fù)雜特征（初始相關(guān)特征的各種組合）。
另外，最近研究人員又提出了一種新的表示方法－決策圖（decision graph）。決策圖
中沒(méi)有冗余結(jié)點(diǎn)，具有可讀性，既解決了復(fù)制問(wèn)題，同時(shí)還能解決碎片問(wèn)題。

--
            我看到一座座山,一座座山川

※ 來(lái)源:．南京大學(xué)小百合站 dii.nju.edu.cn．[FROM: graphics.nju.edu]
--
※ 轉(zhuǎn)載:．南京大學(xué)小百合站 bbs.nju.edu.cn．[FROM: 211.80.38.17]