4.1預(yù)備知識：分類任務(wù)的輸入數(shù)據(jù)是記錄的集合绑蔫。每條記錄也稱實例或樣例运沦，用元組（x,y)表示，其中x是屬性的集=集合配深，而y是一個特殊的屬性携添，指出樣例的類標(biāo)號（也稱為分類屬性或目標(biāo)屬性）。
分類（classification）分類任務(wù)就是通過學(xué)習(xí)得到一個目標(biāo)函數(shù)（targetfunction）f篓叶，把每個屬性集x映射到一個預(yù)先定義的類別號y烈掠。目標(biāo)函數(shù)也稱分類模型（classification model）。分類模型可用于以下目的：描述性建模缸托、預(yù)測性建模
4.2解決分類問題的一般方法
分類技術(shù)(或分類法)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法左敌。分類法的例子包括決策樹分類法、基于規(guī)則的分類法嗦董、神經(jīng)網(wǎng)絡(luò)母谎、支持向量機(jī)和樸素貝葉斯分類法。
首先京革，需要一個訓(xùn)練集（training set),它又類標(biāo)號一致的記錄組成奇唤。使用訓(xùn)練集建立分類模型，該模型隨后運用于檢驗集（test set )匹摇，檢驗集由類標(biāo)號未知的記錄組成咬扇。
分類模型的性能根據(jù)模型正確和錯誤預(yù)的檢驗記錄計數(shù)進(jìn)行評估,這些計數(shù)存放在稱作混淆矩陣( confusion matrix)的表格中。表4-2描述二元分類問題的混滑矩陣廊勃。表中每個表項fij表示實際類標(biāo)號為i但被預(yù)測為類j的記錄數(shù),例如,f01代表原本屬于類0但被誤分為類1的記錄數(shù)懈贺。按照混淆矩陣中的表項,被分類模型正確預(yù)測的樣本總數(shù)是(f11+f00),而被錯誤預(yù)測的樣本總數(shù)是(f10+f01)经窖。
同樣梭灿，分類模型的性能可以用錯誤率（error rate）來表示画侣，其定義如下：
4.3決策樹歸納
4.3.1決策樹的工作原理
為了解釋決策樹分類的工作原理,考慮上一節(jié)中介紹的脊椎動物分類問題的簡化版本。這里我們不把脊椎動物分為五個不同的物種,而只考慮兩個類別:哺乳類動物和非哺乳類動物堡妒。假設(shè)科學(xué)家發(fā)現(xiàn)了一個新的物種,怎么判斷它是哺乳動物還是非哺乳動物呢?一種方法是針對物種的特征提出一系列問題配乱。第一個問題可能是,該物種是冷血動物還是恒溫動物。如果它是冷血的,則該物種肯定不是哺乳動物;否則它或者是某種鳥,或者是某種哺乳動物皮迟。如果它是恒溫的,需要接著問:該物種是由雌性產(chǎn)越進(jìn)行繁殖的嗎?如果是,則它肯定為哺乳動物,否則它有可能是非哺乳動物(鴨嘴獸和針鼴這些產(chǎn)蛋的哺乳動物除外)搬泥。
上面的例子表明,通過提出一系列精心構(gòu)思的關(guān)于檢驗記錄屬性的問題,可以解決分類問題。每當(dāng)一個問題得到答案,后續(xù)的問題將隨之而來,直到我們得到記錄的類標(biāo)號伏尼。這一系列的問題和這些問題的可能回答可以組織成決策樹的形式,決策樹是一種由結(jié)點和有向邊組成的層次結(jié)圖4-4顯示哺乳類動物分類問題的決策樹,樹中包含三種結(jié)點忿檩。
根節(jié)點（root node),它沒有入邊，但有零條或多條出邊爆阶。
內(nèi)部節(jié)點（internal node)燥透，恰有一條入邊和兩條或多條出邊。
葉節(jié)點（leaf node)或終結(jié)點（terminal node）扰她。恰有一條入邊兽掰，但沒有出邊。
在決策樹中,毎個葉結(jié)點都賦予一個類標(biāo)號徒役。非終結(jié)點(non- terminal node)(包括根結(jié)點和內(nèi)部結(jié)點)包含屬性測試條件,用以分開具有不同特性的記錄孽尽。例如,在圖44中,在根結(jié)點處,使用體溫這個屬性把冷血脊権動物和恒溫脊椎動物區(qū)別開來。因為所有的冷血脊椎動物都是非乳動物,所以用一個類稱號為非嘴乳動物的葉結(jié)點作為根結(jié)點的右子女忧勿。如果脊椎動物的體溫是恒溫的,則接下來用胎生這個屬性來區(qū)分乳動物與其他恒溫動物(主要是鳥類)杉女。
一旦構(gòu)造了決策樹,對檢驗記錄進(jìn)行分類就相當(dāng)容易了。從樹的根結(jié)點開始,將測試條件用于檢驗記錄,根據(jù)測試結(jié)果選擇適當(dāng)?shù)姆种?沿著該分支或者到達(dá)另一個內(nèi)部結(jié)點,使用新的測試條件,或者到達(dá)一個葉結(jié)點鸳吸。到達(dá)葉結(jié)點之后,葉結(jié)點的類稱號就被賦值給該檢驗記錄熏挎。例如圖45顯示應(yīng)用決策樹預(yù)測火烈鳥的類標(biāo)號所經(jīng)過的路徑,路徑終止于類稱號為非哺乳動物的葉結(jié)點。
4.3.2建立決策樹
1.hunt 算法
在 Hunt算法中,通過將訓(xùn)練記錄相繼劃分成較純的子集,以遞歸方式建立決策樹。設(shè)是與結(jié)點t相關(guān)聯(lián)的訓(xùn)練記錄集,而y={y1,y2…,yc}是類標(biāo)號,Humt算法的遞歸定義如下:
(1)如果中所有記錄都屬于同一個類
,則t是葉結(jié)點,用
標(biāo)記养匈。
(2)如果中包含屬于多個類的記錄,則選擇一個屬性測試條件( attribute test condition),將記錄劃分成較小的子集哼勇。對于測試條件的每個輸出,創(chuàng)建一個子女結(jié)點,并根據(jù)測試結(jié)果將
中的記錄分布到子女結(jié)點中。然后,對于每個子女結(jié)點,遞歸地調(diào)用該算法呕乎。為了解釋該算法如何執(zhí)行,考慮如下問題:預(yù)測貸款申請者是會按時歸還貸款,還是會拖欠貸款积担。對于這個問題,訓(xùn)練數(shù)據(jù)集可以通過考察以前貨款者的貸放記錄來構(gòu)造。在圖4-6所示的例子中,每條記錄都包含貸款者的個人信息,以及貨款者是否拖欠貨款的類標(biāo)號猬仁。
該分類問題的初始決策樹只有一個結(jié)點,類標(biāo)號為“拖欠款者=否”(見圖4-7a),意味大多數(shù)貸款者都按時歸還貸款易桃。然而,該樹需要進(jìn)一步的細(xì)化,因為根結(jié)點包含兩個類的記錄。根據(jù)“有房者”測試條件,這些記錄被劃分為較小的子集,如圖4-7b所示朽们。選取屬性測試條件的理由稍后討論,目前,我們假定此處這樣選是劃分?jǐn)?shù)據(jù)的最優(yōu)標(biāo)準(zhǔn)。接下來,對根結(jié)點的每個子女遞歸地調(diào)用Hunt算法褐耳。從圖4-6給出的訓(xùn)練數(shù)據(jù)集可以看出,有房的貨款者都按時償還了貸款,因此,根結(jié)點的左子女為葉結(jié)點,標(biāo)記為“抱欠款者=否”(見圖4-7b)。對于右子女,我們需要繼續(xù)遞歸調(diào)用Hunt算法,直到所有的記錄都屬于同一個類為止渴庆。每次遞歸調(diào)用所形成的決策樹顯示在圖4-7c和圖4-7d中漱病。
如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn),并且每種組合都具有算法是有效的。但是對于大多數(shù)實際情況,這些假設(shè)太苛刻了,因此,需要附加的條件來處理以下的情況把曼。
(1)算法的第二步所創(chuàng)建的子女結(jié)點可能為空,即不存在與這些結(jié)點相關(guān)聯(lián)的記錄。如果沒有一個訓(xùn)練記錄包含與這樣的結(jié)點相關(guān)聯(lián)的屬性值組合,這種情形就可能發(fā)生漓穿。這時,該結(jié)點成為葉結(jié)點,類標(biāo)號為其父結(jié)點上訓(xùn)練記錄中的多數(shù)類嗤军。
(2)在第二步,如果與D相關(guān)聯(lián)的所有記錄都具有相同的屬性值(目標(biāo)屬性除外),則不可能進(jìn)一步劃分這些記錄。在這種情況下,該結(jié)點為葉結(jié)點,其標(biāo)號為與該結(jié)點相關(guān)聯(lián)的訓(xùn)練記錄中的多數(shù)類晃危。
2.決策樹歸納的設(shè)計問題
決策樹歸納的學(xué)習(xí)算法必須解決下面兩個問題叙赚。
(1)如何分裂訓(xùn)練記最?樹增長過程的每個遞歸步都必須選擇一個屬性測試條件,將記錄劃分成較小的子集。為了實現(xiàn)這個步驟,算法必須提供為不同類型的屬性指定測試條件的方法,并且提供評估每種測試條件的客觀度量僚饭。
(2)如何停止分裂過程?需要有結(jié)束條件,以終止決策樹的生長過程震叮。一個可能的策略是分裂結(jié)點,直到所有的記錄都屬于同一個類,或者所有的記錄都具有相同的屬性值。盡管兩個結(jié)東條件對于結(jié)束決策樹歸納算法都是充分的,但是還可以使用其他的標(biāo)準(zhǔn)提前終止樹的生長過程鳍鸵。提前終止的優(yōu)點將在4.4.5節(jié)討論苇瓣。
4.3.3表示屬性測試條件的方法
決策樹歸納算法必須為不同類型的屬性提供表示屬性測試條件和其對應(yīng)輸出的方法。
二元屬性 二元屬性的測試條件產(chǎn)生兩個可能的輸出,如圖4-8所示偿乖。
標(biāo)稱屬性 由于標(biāo)稱屬性有多個屬性值,它的測試條件可以用兩種方法表示,如圖4-9所示對于多路劃分(圖4-9a),其輸出數(shù)取決于該屬性不同屬性值的個數(shù)击罪。例如,如果屬性婚姻狀況有三個不同的屬性值一單身、已婚贪薪、離異,則它的測試條件就會產(chǎn)生一個三路劃分媳禁。另一方面,某些決策樹算法(如CART)只產(chǎn)生二元劃分,它們考慮創(chuàng)建k個屬性值的二元劃分的所有+1種方法。圖4-9b顯示了把婚姻狀況的屬性值劃分為兩個子集的三種不同的分組方法画切。
序數(shù)屬性 序數(shù)屬性也可以產(chǎn)生二元或多路劃分,只要不違背序數(shù)屬性值的有序性,就可以對屬性值進(jìn)行分組竣稽。圖410顯示了技照屬性村衣尺嗎劃分訓(xùn)練記錄的不同的方法。圖4-10a和圖4-10b中的分組保持了屬性值間的序關(guān)系,而圖4-10c所示的分組則違反了這一性質(zhì),因為它把小號和大號分為一組,把中號和加大號放在另一組霍弹。
連續(xù)屬性對于連續(xù)屬性來說,測試條件可以是具有二元輸出的比較測試(A<v)或(A≥v),也可以是具有形如≤A<
(i=1,…,k)輸出的范查詢,圖4-11顯示了這些方法的差別毫别。對于二元劃分,決策樹算法必須考慮所有可能的劃分點v,并從中選擇產(chǎn)生最佳劃分的點v。對于多路劃分,算法必須考慮所有可能的連續(xù)值區(qū)間庞萍∨》常可以采用2.3.6節(jié)介紹的離歐化的策略,離散化之后,每個離散化區(qū)間賦予一個新的序數(shù)值,只要保持有序性,相鄰的值還可以聚集成較寬的間。
4.3.4選擇最佳劃分的度量
有很多度量可以用來確定劃分記錄的最佳方法,這些度量用劃分前和劃分后記錄的類分布定義钝计。設(shè)p(i|t)表示給定結(jié)點t中屬于類i的記錄所占的比例,有時,我們省略結(jié)點t,直接用表示該比例恋博。在兩類問題中,任意結(jié)點的類分布都可以記作(
,
),其中
=1-
齐佳。例如,考慮圖4-12中的測試條件,劃分前的類分布是(0.5,0.5),因為來自每個類的記錄數(shù)相等。如果使用性屬性來劃分?jǐn)?shù)據(jù),則子女結(jié)點的類分布分別為(0.6,0.4)和(0.4,0.6),雖然劃分后兩個類的分布不再平衡,但是子女結(jié)點仍然包含兩個類的記錄:按照第二個屬性車型進(jìn)行劃分,將得到純度更高的劃分债沮。
選擇最佳劃分的度量通常是根據(jù)劃分后子女結(jié)點不純性的程度炼吴。不純的程度越低,類分布就越傾斜。例如,類分布為(0,1)的結(jié)點具有零不純性,而均衡分布(0.5,0.5)的結(jié)點具有最高的不純性疫衩。不純性度量的例子包括：
圖4-13顯示了二元分類問題不純性度量值的比較,p表示屬于其中一個類的記錄所占的比例硅蹦。從圖中可以看出,三種方法都在類分布均衡時(即當(dāng)p=0.5時)達(dá)到最大值,而當(dāng)所有記錄都屬于同一個類時(p等于1或0)達(dá)到最小值。下面我們給出三種不純性度量方法的計算實例闷煤。
為了確定測試條件的效果,我們需要比較父結(jié)點(劃分前)的不純程度和子女結(jié)點(劃分后)的不純程度,它們的差越大,測試條件的效果就越好童芹。增益4是一種可以用來確定劃分效果的標(biāo)準(zhǔn):
1.二元屬性分劃分
考慮圖4-14中的圖表,假設(shè)有兩種方法將數(shù)據(jù)劃分成較小的子集假褪。劃分前,Gimi指標(biāo)等于0.5,因為屬于兩個類的記錄個數(shù)相等。如果選擇屬性A劃分?jǐn)?shù)據(jù),結(jié)點N1的Gi指標(biāo)等于0,.4898,而N2的Gimi指標(biāo)等于0.480,派生結(jié)點的Gini指標(biāo)的加權(quán)平均為(7/12)×0.4898+(5/2)×0.480=0.486近顷。類似的,我們可以計算屬性B的Gini指標(biāo)加權(quán)平均是0.371生音。因為屬性B具有更小的Gini指標(biāo),它比屬性A更可取。
2.標(biāo)稱屬性的劃分
3.連續(xù)屬性的劃分
4. 增益率
熵和Gini指標(biāo)等不純性度量趨向有利于具有大量不同值的屬性窒升。圖4-12顯示了三種可供選擇的測試條件,劃分本章習(xí)題2中的數(shù)據(jù)集缀遍。第一個測試條件性別與第二個測試條件車型相比,容易看出車型似乎提供了更好的劃分?jǐn)?shù)據(jù)的方法,因為它產(chǎn)生更純的派生結(jié)點。然而,如果將這兩個條件與顧客D相比,后者看來產(chǎn)生更純的劃分,但顧客D卻不是一個有預(yù)測性的屬性,因為每個樣本在該屬性上的值都是唯一的饱须。即使在不太極端情形下,也不會希望產(chǎn)生大量輸出的測試條件,因為與每個劃分相關(guān)聯(lián)的記錄太少,以致不能作出可靠的預(yù)測域醇。
解決該問題的策略有兩種。第一種策略是限制測試條件只能是二元劃分,CART這樣的決策樹算法采用的就是這種策略:另一種策略是修改評估劃分的標(biāo)準(zhǔn),把屬性測試條件產(chǎn)生的輸出數(shù)也考慮進(jìn)去,例如,決策樹算法C4.5采用稱作增益率( gain ratio)的劃分標(biāo)準(zhǔn)來評估劃分蓉媳。增益率定義如下:
4.3.5 決策樹歸納算法
建立決策樹之后,可以進(jìn)行樹剪枝( tree-pruning),以減小決策樹的規(guī)模。決策樹過大容易受所謂過分?jǐn)M合( overfitting)現(xiàn)象的影響督怜。通過修剪初始決策樹的分支,剪枝有助于提高決策樹的泛化能力殴瘦。過分?jǐn)M合和樹剪枝問題將在4.4節(jié)更詳細(xì)地討論。
4.3.6例子：Web機(jī)器人檢測
Web使用挖據(jù)就是利用數(shù)據(jù)挖據(jù)的技術(shù),從Web訪問日志中提取有用的模式号杠。這些模式能夠揭示站點訪問者的一些有趣特性:例如,一個人頻繁地訪問某個Web站點,并打開介紹同一產(chǎn)品的網(wǎng)頁,如果商家提供一些打折或免費運輸?shù)膬?yōu)惠,這個人很可能會購買這種商品蚪腋。
在Web使用挖掘中,重要的是要區(qū)分用戶訪問和Web機(jī)器人( Web robot)訪問,Web機(jī)器人(又稱Web爬蟲)是一個軟件程序,它可以自動跟蹤嵌入網(wǎng)頁中的超鏈接,定位和獲取 Iinternet上的信息。這些程序安裝在搜素引的入口,收集索引網(wǎng)頁必須的文檔姨蟋。在應(yīng)用Web挖掘技術(shù)分析人類的測覽習(xí)慣之前,必須過濾掉Web機(jī)器人的訪問屉凯。
4.3.7決策樹歸納特點
下面是對決策樹歸納算法重要特點的總結(jié)。
(1)決策樹歸納是一種構(gòu)建分類模型的非參數(shù)方法眼溶。換句話說,它不要求任何先驗假設(shè),不假定類和其他屬性服從一定的概率分布(不像第5章介紹的一些技術(shù))悠砚。
(2)找到最佳的決策樹是NP完全問題。許多決策樹算法都采取啟發(fā)式的方法指導(dǎo)對假設(shè)空間的搜索堂飞。例如,4.3.5節(jié)中介紹的算法就采用了一種貪心的灌旧、自頂向下的遞歸劃分策略建立決策樹
(3)已開發(fā)的構(gòu)建決策樹技術(shù)不需要昂貴的計算代價,即使訓(xùn)練集非常大,也可以快速建立模型绑咱。此外,決策樹一旦建立,未知樣本分類非常快,最壞情況下的時間復(fù)雜度是O(w),其中w是樹的最大深度枢泰。
(4)決策樹相對容易解釋,特別是小型的決策樹描融。在很多簡單的數(shù)據(jù)集上,決策樹的準(zhǔn)確率也可以與其他分類算法相媲美。
(5)決策樹是學(xué)習(xí)離散值函數(shù)的典型代表衡蚂。然而,它不能很好地推廣到某些特定的布爾問題窿克。個著名的例子是奇偶函數(shù),當(dāng)奇數(shù)(偶數(shù))個布爾屬性為真時其值為0(1)。對這樣的函數(shù)準(zhǔn)確建模需要一棵具有2^d個結(jié)點的滿決策樹,其中d是布爾屬性的個數(shù)(見本章習(xí)題1)
(6)決策樹算法對于噪聲的干擾具有相當(dāng)好的魯棒性,采用避免過分?jǐn)M合的方法之后尤其如此毛甲。避免過分?jǐn)M合的方法將在4.4節(jié)介紹年叮。
(7)元余屬性不會對決策樹的準(zhǔn)確率造成不利的影響。一個屬性如果在數(shù)據(jù)中它與另一個屬性是強(qiáng)相關(guān)的,那么它是冗余的玻募。在兩個冗余的屬性中,如果已經(jīng)選擇其中一個作為用于劃分的屬性,則另一個將被忽略谋右。然而,如果數(shù)據(jù)集中含有很多不相關(guān)的屬性(即對分類任務(wù)沒有用的屬性),則某些不相關(guān)屬性可能在樹的構(gòu)造過程中偶然被選中,導(dǎo)致決策樹過于龐大。通過在預(yù)處理階段刪除不相關(guān)屬性,特征選擇技術(shù)能夠幫助提高決策樹的準(zhǔn)確率补箍。我們將在4.4.3節(jié)考察不相關(guān)屬性過多的問題。
(8)由于大多數(shù)的決策樹算法都采用自頂向下的遞歸劃分方法,因此沿著樹向下,記錄會越來越少啸蜜。在葉結(jié)點,記錄可能太少,對于葉結(jié)點代表的類,不能做出具有統(tǒng)計意義的判決,這就是所謂的數(shù)據(jù)碎片( data fragmentation)問題,解決該問題的一種可行的方法是,當(dāng)樣本數(shù)小于某個特定值時停止分裂坑雅。
(9)子樹可能在決策樹中重復(fù)多次,如圖4-19所示,這使得決策樹過于復(fù)雜,并且可能更難解釋。當(dāng)決策樹的每個內(nèi)部結(jié)點都依賴單個屬性測試條件時,就會出現(xiàn)這種情形衬横。由于大多數(shù)的決策樹算法都采用分治劃分策略,因此在屬性空間的不同部分可以使用相同的測試條件,從而導(dǎo)致子樹重復(fù)問題裹粤。
(10)迄今為止,本章介紹的測試條件每次都只涉及一個屬性蜂林。這樣,可以將決策樹的生長過程看成劃分屬性空間為不相交的區(qū)域的過程,直到每個區(qū)域都只包含同一類的記錄(見圖4-20)遥诉。兩個不同類的相鄰區(qū)域之間的邊界稱作決策邊界( decision boundary),由于測試條涉及單個屬性,因此決策邊界是直線,即平行于“坐標(biāo)軸”,這就限制了決策樹對連續(xù)屬性之間復(fù)雜關(guān)系建模的表達(dá)能力。圖4-21顯示了一個數(shù)據(jù)集,使用一次只涉及一個屬性的測試條件的決策樹算法很難有效地對它進(jìn)行分類噪叙。
斜決策樹( oblique decision tree)可以克服以上的局限,因為它允許測試條件涉及多個屬性矮锈。圖4-21中的數(shù)據(jù)集可以很容易地用斜決策樹表示,該斜決策樹只有一個結(jié)點,其測試條件為:
x+y<1
盡管這種技術(shù)具有更強(qiáng)的表達(dá)能力,并且能夠產(chǎn)生更緊湊的決策樹,但是為給定的結(jié)點找出最佳測試條件的計算可能是相當(dāng)復(fù)雜的。
構(gòu)造歸納( constructive induction)提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法(見2.3.5節(jié)),該方法創(chuàng)建復(fù)合屬性,代表已有屬性的算術(shù)或邏輯組合睁蕾。新屬性提供了更好的類區(qū)分能力,并在決策樹歸納之前就增廣到數(shù)據(jù)集中苞笨。與斜決策樹不同,構(gòu)造歸納不需要昂貴的花費,因為在構(gòu)造決策樹之前,它只需要一次性地確定屬性的所有相關(guān)組合。相比之下,在擴(kuò)展每個內(nèi)部結(jié)點時,斜決策樹都需要動態(tài)地確定正確的屬性組合子眶。然而,構(gòu)造歸納會產(chǎn)生冗余的屬性,因為新創(chuàng)建的屬性是已有屬性的組合
(11)研究表明不純性度量方法的選擇對決策樹算法的性能影響很小,這是因為許多度量方法相互之間都是一致的,如圖4-13所示瀑凝。實際上,樹剪枝對最終決策樹的影響比不純性度量的選擇的影響更大。
