發(fā)信人: ashun (阿順), 信區(qū): DataMining
標  題: 數(shù)據(jù)挖掘入門（八）
發(fā)信站: 南京大學小百合站 (Mon Aug 20 10:17:05 2001)

決策樹


決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。比如，在貸款申
請中，要對申請的風險大小做出判斷，圖7是為了解決這個問題而建立的一棵決策樹，從中
我們可以看到?jīng)Q策樹的基本組成部分：決策節(jié)點、分支和葉子。

 

決策樹中最上面的節(jié)點稱為根節(jié)點，是整個決策樹的開始。本例中根節(jié)點是“收入>￥40,
000”，對此問題的不同回答產(chǎn)生了“是”和“否”兩個分支。


決策樹的每個節(jié)點子節(jié)點的個數(shù)與決策樹在用的算法有關(guān)。如CART算法得到的決策樹每個
節(jié)點有兩個分支，這種樹稱為二叉樹。允許節(jié)點含有多于兩個子節(jié)點的樹稱為多叉樹。



每個分支要么是一個新的決策節(jié)點，要么是樹的結(jié)尾，稱為葉子。在沿著決策樹從上到下
遍歷的過程中，在每個節(jié)點都會遇到一個問題，對每個節(jié)點上問題的不同回答導(dǎo)致不同的
分支，最后會到達一個葉子節(jié)點。這個過程就是利用決策樹進行分類的過程，利用幾個變
量（每個變量對應(yīng)一個問題）來判斷所屬的類別（最后每個葉子會對應(yīng)一個類別）。


假如負責借貸的銀行官員利用上面這棵決策樹來決定支持哪些貸款和拒絕哪些貸款，那么
他就可以用貸款申請表來運行這棵決策樹，用決策樹來判斷風險的大小。“年收入>￥40,
00”和“高負債”的用戶被認為是“高風險”，同時“收入<￥40,000”但“工作時間>5年
”的申請，則被認為“低風險”而建議貸款給他/她。


數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來作預(yù)測
（就像上面的銀行官員用他來預(yù)測貸款風險）。常用的算法有CHAID、 CART、 Quest 和C
5.0。


建立決策樹的過程，即樹的生長過程是不斷的把數(shù)據(jù)進行切分的過程，每次切分對應(yīng)一個
問題，也對應(yīng)著一個節(jié)點。對每個切分都要求分成的組之間的“差異”最大。


各種決策樹算法之間的主要區(qū)別就是對這個“差異”衡量方式的區(qū)別。對具體衡量方式算
法的討論超出了本文的范圍，在此我們只需要把切分看成是把一組數(shù)據(jù)分成幾份，份與份
之間盡量不同，而同一份內(nèi)的數(shù)據(jù)盡量相同。這個切分的過程也可稱為數(shù)據(jù)的“純化”。
看我們的例子，包含兩個類別--低風險和高風險。如果經(jīng)過一次切分后得到的分組，每個
分組中的數(shù)據(jù)都屬于同一個類別，顯然達到這樣效果的切分方法就是我們所追求的。


到現(xiàn)在為止我們所討論的例子都是非常簡單的，樹也容易理解，當然實際中應(yīng)用的決策樹
可能非常復(fù)雜。假定我們利用歷史數(shù)據(jù)建立了一個包含幾百個屬性、輸出的類有十幾種的
決策樹，這樣的一棵樹對人來說可能太復(fù)雜了，但每一條從根結(jié)點到葉子節(jié)點的路徑所描
述的含義仍然是可以理解的。決策樹的這種易理解性對數(shù)據(jù)挖掘的使用者來說是一個顯著
的優(yōu)點。


然而決策樹的這種明確性可能帶來誤導(dǎo)。比如，決策樹每個節(jié)點對應(yīng)分割的定義都是非常
明確毫不含糊的，但在實際生活中這種明確可能帶來麻煩（憑什么說年收入￥40,001的人
具有較小的信用風險而￥40,000的人就沒有）。


建立一顆決策樹可能只要對數(shù)據(jù)庫進行幾遍掃描之后就能完成，這也意味著需要的計算資
源較少，而且可以很容易的處理包含很多預(yù)測變量的情況，因此決策樹模型可以建立得很
快，并適合應(yīng)用到大量的數(shù)據(jù)上。


對最終要拿給人看的決策樹來說，在建立過程中讓其生長的太“枝繁葉茂”是沒有必要的
，這樣既降低了樹的可理解性和可用性，同時也使決策樹本身對歷史數(shù)據(jù)的依賴性增大，
也就是說這是這棵決策樹對此歷史數(shù)據(jù)可能非常準確，一旦應(yīng)用到新的數(shù)據(jù)時準確性卻急
劇下降，我們稱這種情況為訓(xùn)練過度。為了使得到的決策樹所蘊含的規(guī)則具有普遍意義，
必須防止訓(xùn)練過度，同時也減少了訓(xùn)練的時間。因此我們需要有一種方法能讓我們在適當
的時候停止樹的生長。常用的方法是設(shè)定決策樹的最大高度（層數(shù)）來限制樹的生長。還
有一種方法是設(shè)定每個節(jié)點必須包含的最少記錄數(shù)，當節(jié)點中記錄的個數(shù)小于這個數(shù)值時
就停止分割。


與設(shè)置停止增長條件相對應(yīng)的是在樹建立好之后對其進行修剪。先允許樹盡量生長，然后
再把樹修剪到較小的尺寸，當然在修剪的同時要求盡量保持決策樹的準確度盡量不要下降
太多。
--
業(yè)精于勤荒于嬉，行成于思毀于隨。 —— 韓愈
臨淵羨魚不如退而結(jié)網(wǎng)。           —— 班固
勿以惡小而為之，勿以善小而不為。 —— 劉備

※ 來源:．南京大學小百合站 http://bbs.nju.edu.cn [FROM: 202.119.80.20]