機(jī)器學(xué)習(xí)簡明教程-基于Python語言實(shí)現(xiàn) 課件 第4、5章 基于距離的算法、決策樹

基于距離的算法《機(jī)器學(xué)習(xí)簡明教程》高延增侯躍恩羅志堅(jiān)機(jī)械工業(yè)出版社04本章目標(biāo)?掌握分類和聚類的區(qū)別?理解幾種常用的距離度量方法?掌握K近鄰算法?掌握K均值算法邏輯回歸可以根據(jù)學(xué)生的作業(yè)成績和平時(shí)表現(xiàn)預(yù)測學(xué)生期末總評是否能及格，也就是說邏輯回歸算法將學(xué)生分成了“及格的”和“不及格的”兩種類別，類似這樣用已知標(biāo)簽的訓(xùn)練集訓(xùn)練一種機(jī)器學(xué)習(xí)算法給某個(gè)個(gè)體打上類別標(biāo)簽的過程稱為分類。還有一類問題，比如需要設(shè)計(jì)一套算法將學(xué)生按其特點(diǎn)歸類以制定個(gè)性化的人才培養(yǎng)方案，但算法事先并不知道訓(xùn)練樣本中的學(xué)生具體的類標(biāo)簽，類似這類問題被稱為聚類。分類是一種有監(jiān)督學(xué)習(xí)任務(wù)，其訓(xùn)練樣本有自變量及其對應(yīng)的因變量，即根據(jù)一堆已經(jīng)打上分類標(biāo)簽的訓(xùn)練數(shù)據(jù)尋找合適的分類算法；而聚類是一種無監(jiān)督學(xué)習(xí)任務(wù)，無監(jiān)督學(xué)習(xí)的處理對象是一堆無標(biāo)簽的數(shù)據(jù)，算法需要從數(shù)據(jù)集中發(fā)現(xiàn)和總結(jié)模式或者結(jié)構(gòu)來完成聚類任務(wù)。本章的重點(diǎn)是屬于有監(jiān)督學(xué)習(xí)的K近鄰算法、屬于無監(jiān)督學(xué)習(xí)的K均值算法。雖然K近鄰和K均值分別屬于有監(jiān)督、無監(jiān)督學(xué)習(xí)算法，但因其實(shí)現(xiàn)原理有一定相似性，本書將此兩種算法放在同一章節(jié)介紹。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.1分類與聚類的區(qū)別所謂分類就是從已知類別樣本組成的集合中訓(xùn)練出一種分類器，用這個(gè)分類器對未知類別的樣本進(jìn)行分類。分類算法的分類過程就是建立一種分類模型來描述預(yù)定的數(shù)據(jù)集或概念集，通過分析由屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型。分類的目的就是使用分類對新的數(shù)據(jù)集進(jìn)行劃分，其主要涉及分類規(guī)則的準(zhǔn)確性、過擬合、矛盾劃分的取舍等，分類問題示意如圖：“物以類聚、人以群分”，在一個(gè)空間中，如果兩個(gè)樣本距離較近，那它們同屬一個(gè)類別的可能性也較高。根據(jù)這一思想，在對一個(gè)新的、未知類別的樣本進(jìn)行分類時(shí)可以參考與它距離較近的一些樣本的類別，據(jù)此來對新樣本進(jìn)行分類表決，這就是K近鄰分類的基本思想。4.1分類與聚類的區(qū)別聚類算法分為層次聚類、劃分聚類兩種。層次聚類初始階段將每個(gè)樣本點(diǎn)看成一類，然后再對這些類每次迭代的時(shí)候都進(jìn)行兩兩合并，直到所有的類聚集完成；劃分聚類首先指定類的個(gè)數(shù)K，然后將樣本集隨機(jī)分成K類，在每次迭代的時(shí)候?qū)颖炯M(jìn)行重新優(yōu)化組合成為新的K類，最后使得類內(nèi)的相似度、類間的差異或迭代次數(shù)達(dá)到設(shè)定值。與分類類似，聚類任務(wù)的流程也可劃分為數(shù)據(jù)準(zhǔn)備、特征選擇、特征提取、聚類、聚類結(jié)果評估等幾個(gè)階段。假設(shè)有一組樣本如下圖（a）所示，事先不知道這些樣本的具體類別，如果指定要分為2類（K=2），分類結(jié)果如圖（b），這就是劃分聚類。各種劃分聚類算法中，K均值是最著名的一種。4.1分類與聚類的區(qū)別K均值聚類是一種迭代求解算法，首先，隨機(jī)選取K個(gè)中心，計(jì)算樣本點(diǎn)與K個(gè)中心的距離并將此樣本點(diǎn)暫時(shí)歸類為離它最近的那個(gè)中心，這樣處理完每個(gè)樣本點(diǎn)后就可以臨時(shí)將樣本空間分為K個(gè)類；然后，將這K個(gè)類的中心作為新的中心點(diǎn)，再重新按樣本點(diǎn)與新的中心的距離來重新聚類一次；循環(huán)往復(fù)，直至達(dá)到循環(huán)結(jié)束條件。K近鄰分類和K均值聚類算法的一個(gè)重要依據(jù)是距離。數(shù)據(jù)挖掘中的樣本通常由一個(gè)多維度的向量表示，而樣本的相似性大小的度量可以轉(zhuǎn)化為對應(yīng)向量之間的距離的求解。

對于距離概念的深入理解，是掌握數(shù)據(jù)挖掘算法的必要前提。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.2距離度量問題距離是一個(gè)函數(shù)，將樣本空間中的兩個(gè)樣本點(diǎn)映射為一個(gè)實(shí)數(shù)

機(jī)器學(xué)習(xí)中可能用到的距離函數(shù)有很多，包括歐式距離、曼哈頓距離、切比雪夫距離等。但一個(gè)距離函數(shù)又不是隨意的將兩個(gè)樣本點(diǎn)映射為一個(gè)實(shí)數(shù)，此映射函數(shù)只有在滿足一定前提條件后才能被當(dāng)成距離函數(shù)使用。4.2距離度量問題廣義的距離函數(shù)

描述樣本點(diǎn)的向量的維度值有兩類變量，表示身高、體重這一類屬性的數(shù)值型維度，以及表示性別、是否及格等的布爾型維度，根據(jù)向量的特點(diǎn)可以將距離函數(shù)分成數(shù)值向量距離和布爾向量距離兩類。4.2距離度量問題——數(shù)值向量距離數(shù)值向量距離函數(shù)有很多，常用的有歐式距離（Euclideandistance）、曼哈頓距離(Manhattandistance)、閔可夫斯基距離(Minkowskidistance)等。歐式距離(Euclideandistance)二維向量歐式距離示意圖

4.2距離度量問題——數(shù)值向量距離歐式距離簡明易懂，但在數(shù)據(jù)挖掘算法中使用時(shí)存在明顯缺陷。由歐式距離的計(jì)算公式知，它的結(jié)果與度量單位有關(guān)，這在應(yīng)用時(shí)往往會(huì)與實(shí)際意愿相背離。例如，在教育數(shù)據(jù)挖掘項(xiàng)目中要計(jì)算兩個(gè)學(xué)生的相似性，如果以米為單位他們的身高這一維度上可能有0.2的差距，但如果以厘米為單位，這一差距就變成20了，這樣和其他維度比如體重相結(jié)合計(jì)算兩個(gè)學(xué)生的相似性就沒有一致性。針對這一缺點(diǎn)，可以使用標(biāo)準(zhǔn)化歐式距離，先將向量的各個(gè)維度的數(shù)值都投影到[0,1]區(qū)間再進(jìn)行歐式距離計(jì)算。標(biāo)準(zhǔn)化歐式距離（StandardizedEuclideandistance）

經(jīng)過式（4.4）處理后，樣本空間中樣本向量的每個(gè)分量的均值都為0、方差為1。標(biāo)準(zhǔn)化后的樣本，進(jìn)行歐氏距離計(jì)算的公式如式

4.2距離度量問題——數(shù)值向量距離馬氏距離（MahalanobisDistance）

4.2距離度量問題——數(shù)值向量距離曼哈頓距離(Manhattandistance)前面的歐式距離是兩點(diǎn)之間的直線距離，但在路徑規(guī)劃這一類實(shí)際問題中，兩點(diǎn)之間很可能沒有直線相連，曼哈頓距離的定義就考慮到了這種情況。曼哈頓距離又稱城市區(qū)塊距離，在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)間的曼哈頓距離是這兩個(gè)點(diǎn)所形成的線段對坐標(biāo)軸產(chǎn)生的投影的距離總和。假設(shè)A、B兩點(diǎn)的坐標(biāo)分別為(x1,y1)和(x2,y2)，則AB兩點(diǎn)的曼哈頓距離如式

AB兩點(diǎn)間三條連接線，線1是歐式距離，線3是曼哈頓距離，而線2是與線3等效的一條曼哈頓距離線。從二維擴(kuò)展到更多維度時(shí)，曼哈頓距離的計(jì)算方式類似

相對于歐式距離，曼哈頓距離的求解只需要做加減法，不需要平方和開方運(yùn)算，使得計(jì)算效率提高的同時(shí)消除開方運(yùn)算的誤差影響。4.2距離度量問題——數(shù)值向量距離閔可夫斯基距離(Minkowskidistance)

除了上述歐式距離、馬氏距離、曼哈頓距離、閔可夫斯基距離外，常用的數(shù)值向量距離函數(shù)還有余弦相似度、切比雪夫距離、加權(quán)閔可夫斯基距離等。4.2距離度量問題——布爾向量距離0和1組成的字母“E”布爾向量又稱邏輯向量，與數(shù)值向量不同，一個(gè)邏輯向量儲(chǔ)存一組TRUE或FALSE值，即向量的各個(gè)維度的取值只能是0或1。例，如右圖所示為一個(gè)手寫大寫英文字母“E”圖像經(jīng)過預(yù)處理后的效果，圖中像素點(diǎn)的值全部是布爾值。常用的布爾向量函數(shù)包括漢明距離（HammingDistance）、杰卡德距離（JaccardDistance）、Dice系數(shù)（DiceDissimilarity）等。4.2距離度量問題——布爾向量距離漢明距離（HammingDistance）兩個(gè)等長字符串之間的漢明距離是兩個(gè)字符串對應(yīng)位置的不同字符的個(gè)數(shù)，就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。如果是兩個(gè)布爾向量，只需取異或運(yùn)算，結(jié)果中１的數(shù)目就是漢明距離，又稱漢明權(quán)重。漢明距離在數(shù)據(jù)處理與挖掘領(lǐng)域應(yīng)用非常廣泛，如Google、Baidu等搜索引擎都推出了“以圖搜圖”的功能，大致步驟如下：

最后，將兩張圖片的比較結(jié)果組合在一起，就構(gòu)成了一個(gè)64位的整數(shù)，這就是這張圖片的指紋。組合的次序并不重要，只要保證所有圖片都采用同樣次序就行了。得到指紋以后，就可以對比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同于計(jì)算"漢明距離"（Hammingdistance）。如果不相同的數(shù)據(jù)位不超過5，就說明兩張圖片很相似；如果大于10，就說明這是兩張不同的圖片。4.2距離度量問題——布爾向量距離杰卡德距離（JaccardDistance）給定兩個(gè)集合A、B，Jaccard系數(shù)定義為A與B交集的大小與A與B并集的大小的比值，當(dāng)集合A，B都為空時(shí)，J(A,B)定義為1

與Jaccard系數(shù)相關(guān)的指標(biāo)叫做Jaccard距離，用于描述集合之間的不相似程度。Jaccard距離越大，樣本相似度越低。

4.2距離度量問題——布爾向量距離使用Jaccard距離函數(shù)來計(jì)算布爾向量間的距離

Jaccard距離的應(yīng)用的場景包括：網(wǎng)頁去重、考試防作弊系統(tǒng)、論文查重等，特別適用于“文章查重”一類的稀疏度過高的向量相似性求解的領(lǐng)域。4.2距離度量問題——布爾向量距離Dice系數(shù)（DiceDissimilarity）與Jaccard系數(shù)類似，Dice系數(shù)本質(zhì)上也是一種集合相似度度量函數(shù)，通常用于計(jì)算兩個(gè)集合的相似度，計(jì)算方法如式Dice系數(shù)也可以用來測量兩個(gè)布爾型向量的相似性，其取值范圍在0-1之間。更一般的情況，Dice系數(shù)計(jì)算相似性的示意如下圖，Dice系數(shù)取值越大，表示兩個(gè)被比較的對象越相似。

除漢明距離、杰卡德差異、Dice系數(shù)外，常用的布爾型向量距離函數(shù)還有庫爾辛斯基差異（Kulsinskidissimilarity）、田本羅杰斯差異（Rogers-Tanimotodissimilarity）、拉塞爾差異（Russell-Raodissimilarity）、Yule差異（Yuledissimilarity）等。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.3K近鄰（K-NearestNeighbor,KNN）KNN在算法理論上較成熟，是最簡單、最流行的機(jī)器學(xué)習(xí)算法之一。KNN的基本思路是：如果已經(jīng)有一個(gè)分類好的樣本集，然后就可以用這個(gè)樣本集去對一個(gè)新的、未知分類標(biāo)簽的樣本點(diǎn)進(jìn)行分類，而分類的方式就是在這個(gè)樣本集中找到K個(gè)離新的樣本最近的點(diǎn)，然后利用一定的決策規(guī)則讓這個(gè)K個(gè)近鄰去決定新樣本點(diǎn)所屬類別。例如我們經(jīng)常通過地段來預(yù)估一個(gè)房子的價(jià)值。KNN算法既可以做分類也可以做回歸，主要區(qū)別在于最后做預(yù)測時(shí)的決策方式不同。KNN做分類預(yù)測時(shí)，一般是選擇多數(shù)表決法，即訓(xùn)練集里和預(yù)測的樣本特征最近的K個(gè)樣本，預(yù)測為里面有最多類別數(shù)的類別。而KNN做回歸時(shí)，一般是選擇平均法，即最近的K個(gè)樣本對應(yīng)輸出的平均值作為回歸預(yù)測值。KNN做分類和回歸的方法類似，本書只介紹KNN分類算法。4.3K近鄰——算法描述KNN是一種基于實(shí)例的算法，如下圖（a）有一個(gè)已知每個(gè)樣本所屬類別的樣本集，有了KNN算法就可以通過（a）中的樣本集來判斷一個(gè)新加入的點(diǎn)屬于哪一類（如下圖（b））。但是，在上圖（b）中，如果單看待識(shí)別點(diǎn)的一個(gè)最近鄰點(diǎn)可能并不能很準(zhǔn)確的對它進(jìn)行分類，因?yàn)樽罱哪莻€(gè)點(diǎn)有可能是噪聲點(diǎn)，一般會(huì)選擇K個(gè)點(diǎn)（K>1），然后讓這K個(gè)最近鄰的點(diǎn)進(jìn)行投票，以決定這個(gè)待識(shí)別的點(diǎn)到底屬于“矩形”類還是屬于“三角形”類。K值的選擇是由算法使用者自行決定的，兩分類問題，K應(yīng)該選為奇數(shù)值，投票的時(shí)候就不會(huì)出現(xiàn)兩個(gè)類別得票相等的情況。K值的選取需要視實(shí)際情況而定。多數(shù)實(shí)際應(yīng)用的場景中，樣本點(diǎn)的近鄰并不如二維平面直觀，需要根據(jù)4.2節(jié)中介紹的距離計(jì)算方案來求與待分類點(diǎn)距離最近的K個(gè)近鄰?？此泼裰鞯淖孠個(gè)近鄰點(diǎn)具有相同的投票權(quán)利可能未必合理，在一些應(yīng)用場景需要設(shè)計(jì)更加合理的投票機(jī)制。4.3K近鄰——三要素（1）k值的選取；（2）距離度量的方式；（3）分類決策規(guī)則。K值是待分類樣本點(diǎn)在訓(xùn)練集中選擇的近鄰點(diǎn)的個(gè)數(shù)，理論上講K越大分類錯(cuò)誤的可能性越小。但在工程實(shí)際中，K值增加并不能持續(xù)的降低錯(cuò)誤率，K值在增加到一定程度后反而會(huì)使錯(cuò)誤率變大。合理的解釋是，當(dāng)K值選擇過大時(shí)，將會(huì)引入和待分類點(diǎn)過遠(yuǎn)的點(diǎn)，而這些點(diǎn)和待分類點(diǎn)可能并沒有什么關(guān)聯(lián)，將過多的無關(guān)的點(diǎn)引入到投票中勢必會(huì)對分類產(chǎn)生干擾。4.3K近鄰——三要素（1）k值的選?。唬?）距離度量的方式；（3）分類決策規(guī)則。另外，如果樣本的維度選擇不合理可能會(huì)使兩個(gè)并不相似的點(diǎn)距離反而很小、而相似的點(diǎn)卻距離很大，因此在使用KNN算法時(shí)需要謹(jǐn)慎選擇距離度量函數(shù)。4.3K近鄰——三要素（1）k值的選?。唬?）距離度量的方式；（3）分類決策規(guī)則。使用的是5近鄰分類器，按照民主投票規(guī)則，待分類點(diǎn)被分為矩形類。但是，直觀上看，待識(shí)別點(diǎn)是三角形類的可能性更大。這是因?yàn)榇R(shí)別點(diǎn)的最近5個(gè)近鄰點(diǎn)中，3個(gè)矩形點(diǎn)距離待識(shí)別點(diǎn)較遠(yuǎn)而2個(gè)三角形點(diǎn)距離較近。針對這一問題，在實(shí)際應(yīng)用中KNN的決策規(guī)則多采用加權(quán)最近鄰。加權(quán)最近鄰，就是所選擇的K個(gè)近鄰點(diǎn)的第i個(gè)點(diǎn)在進(jìn)行投票決策時(shí)乘以一個(gè)系數(shù)后再進(jìn)行投票

加權(quán)K近鄰法的基本思想是距離待識(shí)別點(diǎn)越近的點(diǎn)在進(jìn)行投票決策時(shí)的話語權(quán)越大。4.3K近鄰——訓(xùn)練集對KNN的影響樣本訓(xùn)練集的預(yù)處理工作主要是對兩類樣本點(diǎn)的處理：（1）對KNN的分類結(jié)果可能產(chǎn)生錯(cuò)誤導(dǎo)向的樣本點(diǎn)；（2）雖然不會(huì)影響分類結(jié)果的正確性但是會(huì)降低分類效率的點(diǎn)，即移除這些點(diǎn)不會(huì)影響分類結(jié)果但是可以提高分類的速度。A、B區(qū)域中各有一個(gè)三角形點(diǎn)，A區(qū)域中的三角形點(diǎn)被矩形點(diǎn)包圍、B區(qū)域中的三角形點(diǎn)處在三角形區(qū)域和矩形區(qū)域的交界處。A區(qū)域中的三角形點(diǎn)，可能是由噪聲引起的，也可能是在類別標(biāo)簽階段誤處理造成的；而B區(qū)域中的三角形點(diǎn)是比較敏感的，因?yàn)樗硞€(gè)（些）屬性值的輕微變動(dòng)都可能會(huì)改變這個(gè)樣本點(diǎn)的類別。如果這兩種類別的點(diǎn)被包含在KNN的K近鄰點(diǎn)中，都有可能會(huì)對分類決策產(chǎn)生不好的影響，因此在進(jìn)行訓(xùn)練樣本集預(yù)處理時(shí)需要將這兩類點(diǎn)剔除。4.3K近鄰——訓(xùn)練集對KNN的影響多余樣例點(diǎn)，虛線圓中求圓形待識(shí)別點(diǎn)的K近鄰點(diǎn)，就需求解本集中所有點(diǎn)與待識(shí)別點(diǎn)的距離，運(yùn)算量較大。而且，如果將虛線圓框中的矩形點(diǎn)減少并不會(huì)影響待識(shí)別點(diǎn)的分類結(jié)果。有一些訓(xùn)練樣本點(diǎn)，如果剔除它們非但不會(huì)影響分類結(jié)果的正確性，還能降低計(jì)算復(fù)雜度，類似這樣的點(diǎn)就是多余點(diǎn)，在訓(xùn)練樣本集預(yù)處理時(shí)也要剔除4.3K近鄰——算法實(shí)現(xiàn)第一步，需要準(zhǔn)備合適的已知分類標(biāo)簽的訓(xùn)練樣本集；第二步，將待識(shí)別點(diǎn)輸入訓(xùn)練集用KNN算法進(jìn)行分類。KNN分類有兩個(gè)關(guān)鍵問題：（1）在分類樣本集中找出X的K個(gè)最近鄰點(diǎn)；（2）分類決策的實(shí)現(xiàn)。4.3K近鄰——算法實(shí)現(xiàn)最簡單的KNN分類決策4.3K近鄰——算法實(shí)現(xiàn)對訓(xùn)練樣本集預(yù)處理的流程，其關(guān)鍵步驟是：（1）有害點(diǎn)（容易使KNN分類結(jié)果出錯(cuò)的點(diǎn)）剔除；（2）多余點(diǎn)（剔除之后不影響KNN分類結(jié)果的點(diǎn)）剔除。剔除有害點(diǎn)的第一步檢測有害點(diǎn)，一種常用的辦法是通過托梅克（Tomek）連接技術(shù)來檢測有害點(diǎn)。所謂托梅克連接，是指樣本集中的兩個(gè)樣本點(diǎn)A和B，如果同時(shí)滿足兩個(gè)條件：（1）A和B互為最近鄰點(diǎn)、（2）A和B的類別不同，那A和B之間就構(gòu)成了托梅克連接。噪聲點(diǎn)、分界點(diǎn)有較大可能存在托梅克連接點(diǎn)。通過托梅克連接移除有害點(diǎn)的算法如下KNN的訓(xùn)練集可能會(huì)有大量的冗余點(diǎn)（刪除這些點(diǎn)不影響KNN分類的性能），而這些冗余點(diǎn)的存在使得K近鄰點(diǎn)的搜索運(yùn)算量大大增加。4.3K近鄰——算法實(shí)現(xiàn)

各種改進(jìn)型的KNN算法層出不窮，對于KNN的改進(jìn)主要包括：（1）對三要素的升級(jí)，包括K值選擇算法、距離度量算法、分類決策算法的改進(jìn)；（2）對訓(xùn)練樣本集的優(yōu)化處理，包括樣本屬性的預(yù)處理、有害樣本點(diǎn)和多余樣本點(diǎn)的預(yù)處理等。4.3K近鄰——應(yīng)用案例例：對用戶手寫的數(shù)字進(jìn)行識(shí)別。例如下圖中，計(jì)算機(jī)采集到用戶手寫的圖片，能夠?qū)⑵渥R(shí)別為數(shù)字“8”。

問題分析根據(jù)前面對K近鄰分類算法的介紹，使用K近鄰分類進(jìn)行手寫體數(shù)字識(shí)別的本質(zhì)是將用戶手寫的數(shù)字在0-9這十個(gè)類別上進(jìn)行分類。而訓(xùn)練樣本集是很多已經(jīng)處理好的手寫數(shù)字向量，每個(gè)向量的數(shù)字類別是已知的，待識(shí)別的手寫數(shù)字就是待分類的向量，將此向量放到訓(xùn)練集中尋找與之最近的K個(gè)點(diǎn)，最后根據(jù)制定好的決策規(guī)則來對待識(shí)別向量進(jìn)行分類。4.3K近鄰——應(yīng)用案例訓(xùn)練集中圖像的預(yù)處理包括大小統(tǒng)一、二值化處理、平滑去噪等。最終目標(biāo)是將每一張已知數(shù)字的手寫體照片轉(zhuǎn)變成形狀相等的布爾向量，將這些向量存為訓(xùn)練集。待識(shí)別的圖像需要經(jīng)過類似處理，成為與訓(xùn)練集中等長的布爾向量后才能進(jìn)行K近鄰法識(shí)別。訓(xùn)練集構(gòu)建要構(gòu)建訓(xùn)練集。從0-9十個(gè)阿拉伯?dāng)?shù)字，每個(gè)數(shù)字采集若干（200張左右）照片，然后將每張圖片都進(jìn)行圖像縮放、二值化、去噪處理。簡單起見，可將二值化后的向量存為文本文件，文本命名為“數(shù)字_編號(hào)”的樣式，如4.3K近鄰——應(yīng)用案例K近鄰識(shí)別測試機(jī)器學(xué)習(xí)算法的測試需要注意的內(nèi)容主要包括：屬性測試、測試組件、測試流程、應(yīng)用場景等幾個(gè)方面。屬性測試包括機(jī)器學(xué)習(xí)算法的正確性、健壯性、公平性等；測試組件包括測試過程中需要用到的數(shù)據(jù)、學(xué)習(xí)程序、框架等；測試流程則包括測試結(jié)果生成、測試評估等工作；應(yīng)用場景則是機(jī)器學(xué)習(xí)算法在自動(dòng)駕駛、機(jī)器翻譯、OCR識(shí)別等具體應(yīng)用場景中的測試。本案例僅對算法正確性進(jìn)行測試，測試數(shù)據(jù)集的構(gòu)建和訓(xùn)練集類似，測試集中的每一張手寫數(shù)字圖片向量都要與訓(xùn)練集中的所有向量計(jì)算距離，然后找出K（取K=3或5一類的奇數(shù)值）個(gè)最近的向量點(diǎn)，然后進(jìn)行投票決定測試向量的數(shù)字。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.4K均值“k-均值”聚類算法目的是把n個(gè)未標(biāo)記類別標(biāo)簽的點(diǎn)（可以是樣本的一次觀察或一個(gè)實(shí)例）劃分到K個(gè)聚類中，使得每個(gè)點(diǎn)都屬于離他最近的均值（此即聚類中心）對應(yīng)的聚類，以之作為聚類的標(biāo)準(zhǔn)，是一種無監(jiān)督學(xué)習(xí)算法。由此可以看出，K均值和K近鄰是兩種不同的機(jī)器學(xué)習(xí)算法。例

：快遞員設(shè)置自助取貨點(diǎn)問題。假設(shè)有個(gè)快遞員負(fù)責(zé)幾個(gè)挨著的農(nóng)村（共1000戶）的送貨任務(wù)，快遞員要設(shè)置4個(gè)自助取貨點(diǎn)，請問如何較好設(shè)置取貨點(diǎn)位置盡量照顧到所有的村民呢？4.4K均值一開始快遞員隨意選4個(gè)取貨點(diǎn)，并且把這4個(gè)點(diǎn)的位置公告給了所有的村民，于是每個(gè)村民到離自己家最近的取貨點(diǎn)取貨。一些村民覺得距離太遠(yuǎn)經(jīng)常投訴，于是快遞員統(tǒng)計(jì)到各取貨點(diǎn)取貨的村民的地址，然后將取貨點(diǎn)位置搬到對應(yīng)的村民地址的中心位置，并且再公告給所有村民?？爝f點(diǎn)的位置更新后，所有村民重新選擇離自己最近的快遞點(diǎn)。然后，又有村民投訴快遞點(diǎn)較遠(yuǎn)，快遞點(diǎn)重新更新位置。就這樣，快遞點(diǎn)每更新一次自己的位置，村民根據(jù)自己的情況重新選擇快遞點(diǎn)，直到最終穩(wěn)定下來。4.4K均值——算法描述

子集的均值向量μi又被稱為質(zhì)心，每次迭代都需要重新計(jì)算質(zhì)心的位置。因此，對于K均值聚類算法只需要找到K個(gè)合適的質(zhì)心就可以將n個(gè)點(diǎn)分成K個(gè)滿足條件的類。下圖展示了將一個(gè)未知類標(biāo)簽的集合如何通過不停優(yōu)化兩個(gè)質(zhì)心的位置分成2個(gè)類的過程（K=2），由圖中看出K均值式是一種啟發(fā)式的迭代方法。

4.4K均值——算法描述K均值聚類算法，首先要注意的是K值的選擇，一般根據(jù)對數(shù)據(jù)的先驗(yàn)經(jīng)驗(yàn)選擇一個(gè)合適的k值，如果沒有什么先驗(yàn)知識(shí)，則可以通過交叉驗(yàn)證選擇一個(gè)合適的k值。在確定了分類個(gè)數(shù)K后，需要選擇K個(gè)初始化的質(zhì)心，可以采用隨機(jī)質(zhì)心。因?yàn)槭菃l(fā)式算法，K個(gè)初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運(yùn)行時(shí)間都影響，這些質(zhì)心不應(yīng)太近。更一般地，K均值聚類算法描述如下：4.4K均值——算法描述K均值進(jìn)行集群聚類時(shí)做了一些假設(shè)：（1）數(shù)據(jù)集由K個(gè)聚類組成；（2）數(shù)據(jù)集是一個(gè)凸數(shù)據(jù)集，即聚類結(jié)果內(nèi)任意兩點(diǎn)的連線上所有點(diǎn)都在數(shù)據(jù)集內(nèi)，否則聚類效果差；（3）每個(gè)聚類中的元素個(gè)數(shù)幾乎一樣。錯(cuò)誤的聚類4.4K均值——算法描述傳統(tǒng)K-Means是個(gè)簡單實(shí)用的聚類算法，具有以下優(yōu)點(diǎn)：（1）原理比較簡單、實(shí)現(xiàn)容易；（2）收斂速度快；（3）算法的可解釋度比較強(qiáng)。同時(shí)，它也有幾個(gè)比較明顯的缺點(diǎn)：（1）K值不好選取；（2）采用迭代方法得到的結(jié)果容易陷入局部最優(yōu)；（3）對噪音和異常點(diǎn)比較的敏感；（4）無法完成對非凸數(shù)據(jù)集的聚類。4.4K均值——算法優(yōu)化K-Means++初始質(zhì)心的選取對K均值聚類結(jié)果影響較大，K-Means++的主要改進(jìn)就在初始質(zhì)心的合理選擇，其它步驟和經(jīng)典K-Means算法相同。K-Means++能顯著改善分類結(jié)果的最終誤差。盡管計(jì)算初始點(diǎn)時(shí)花費(fèi)了額外的時(shí)間，但在迭代過程中，由于初始中心選取更合理使得算法本身能快速收斂，因此算法實(shí)際上降低了計(jì)算時(shí)間。4.4K均值——算法優(yōu)化ISODATA經(jīng)典K-Means算法和K-Means++算法的K值是固定不變的，而ISODATA算法可以根據(jù)分類情況自動(dòng)調(diào)整K值的大小。ISODATA算法通過分裂操作增加K值、通過合并操作來減少K值，以此調(diào)整K值的大小。

4.4K均值——算法優(yōu)化ISODATA

4.4K均值——應(yīng)用案例例：通過地理位置對城市群進(jìn)行聚類。城市群是工業(yè)化、城市化進(jìn)程中，區(qū)域空間形態(tài)的高級(jí)現(xiàn)象，能夠產(chǎn)生巨大的集聚經(jīng)濟(jì)效益，是國民經(jīng)濟(jì)快速發(fā)展、現(xiàn)代化水平不斷提高的標(biāo)志之一。城市群是在特定的區(qū)域范圍內(nèi)云集形成，以一個(gè)或兩個(gè)特大城市為中心，依托一定的自然環(huán)境和交通條件，城市之間的內(nèi)在聯(lián)系不斷加強(qiáng)，共同構(gòu)成的一個(gè)相對完整的城市“集合體”。4.4K均值——應(yīng)用案例解題思路本例為使問題簡化，只研究省會(huì)城市，并以經(jīng)緯度為城市坐標(biāo)，另外僅將所有城市聚成2個(gè)類。城市名經(jīng)度緯度城市名經(jīng)度緯度北京E116°28′N39°54′上海E121°29′N31°14′天津E117°11′N39°09′重慶E106°32′N29°32′哈爾濱E126°41′N45°45′長春E125°19′N43°52′沈陽E123°24′N41°50′呼和浩特E111°48′N40°49′石家莊E114°28′N38°02′太原E112°34′N37°52′濟(jì)南E117°N36°38′鄭州E113°42′N34°48′西安E108°54′N34°16′蘭州E103°49′N36°03′銀川E106°16′N38°20′西寧E101°45′N36°38′烏魯木齊E87°36′N43°48′合肥E117°18′N31°51′南京E118°50′N32°02′杭州E120°09′N30°14′長沙E113°N28°11′南昌E115°52′N28°41′武漢E114°21′N30°37′成都E104°05′N30°39′貴陽E106°42′N26°35′福州E119°18′N26°05′臺(tái)北E121°31′N25°03′廣州E113°15′N23°08′?？贓110°20′N20°02′南寧E108°20′N22°48′昆明E102°41′N25°拉薩E?91°10′N29°40′香港E114°10′N22°18′澳門E113°5′N22°2′4.4K均值——應(yīng)用案例算法

4.4K均值——應(yīng)用案例效果以經(jīng)度作為橫軸、維度作為縱軸將城市散點(diǎn)圖繪制到一個(gè)直角坐標(biāo)系，并將每個(gè)散點(diǎn)代表的城市標(biāo)注上，如下圖：使用K-Means聚類對城市進(jìn)行聚類后的結(jié)果本章小結(jié)雖然本章同時(shí)介紹了KNN和K-Means算法，但它們是有本質(zhì)區(qū)別的。KNN是有監(jiān)督學(xué)習(xí)，而K-Means是無監(jiān)督學(xué)習(xí)；KNN是分類算法，而K-Means是聚類算法；KNN中的K是待分類點(diǎn)進(jìn)行類別決策時(shí)參與投票的最近鄰點(diǎn)個(gè)數(shù)，而K-Means中的K是聚類算法將輸入樣本集聚成的類別個(gè)數(shù)。KNN的特點(diǎn)：（1）一種監(jiān)督學(xué)習(xí)算法：訓(xùn)練樣本集中的樣本點(diǎn)帶有分類信息；（2）算法簡單易實(shí)現(xiàn)，可解釋性強(qiáng)；（3）結(jié)果受到K值的影響，K一般不超過20；（4）計(jì)算量大，需要計(jì)算與樣本集中每個(gè)樣本的距離；（5）訓(xùn)練樣本集不平衡容易導(dǎo)致結(jié)果不準(zhǔn)確。經(jīng)典K-Means算法的特點(diǎn)：（1）原理簡單、易實(shí)現(xiàn)；（2）需要調(diào)參的主要參數(shù)較少（K）；（3）K值選取困難；（4）使用迭代方法，容易得到局部最優(yōu)解；（5）對噪聲和異常點(diǎn)敏感。另外，本章介紹的K-Means聚類算法是一種“硬聚類”算法，即數(shù)據(jù)集中每一個(gè)樣本都是被百分百確定分到某個(gè)類別中，而與之相對的“軟聚類”可以理解為每個(gè)樣本是以一定的概率被分到某一個(gè)類別中。謝謝決策樹《機(jī)器學(xué)習(xí)簡明教程》高延增侯躍恩羅志堅(jiān)機(jī)械工業(yè)出版社05本章目標(biāo)?掌握決策樹的一般定義?理解信息熵與信息增益?掌握ID3、C4.5決策樹算法?理解決策樹剪枝樹狀結(jié)構(gòu)（Treestructure）或稱樹狀圖（Treediagram）是一種以圖像方式表現(xiàn)的層級(jí)結(jié)構(gòu)。它以樹的象征來表現(xiàn)構(gòu)造之間的關(guān)系，它在圖像的呈現(xiàn)上是一個(gè)倒立的樹，其根部在上，葉子在下。樹狀結(jié)構(gòu)只是一個(gè)概念，可以用許多種不同形式來展現(xiàn)，多以遞歸方式表示。決策樹也是一種樹狀結(jié)構(gòu)，在1963年由Morgan和Sonquist提出，決策樹上的節(jié)點(diǎn)代表某個(gè)屬性，一條邊代表屬性取值，而這棵決策樹就可以表示決策的過程。因?yàn)闃錉罱Y(jié)構(gòu)易于理解且可解釋性強(qiáng)，因此在規(guī)則可視化、回歸問題、分類問題等領(lǐng)域應(yīng)用廣泛。本章將詳細(xì)介紹數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)中的決策樹相關(guān)的基本概念，以及常用的決策樹生成算法ID3、C4.5、CART等。目錄/Contents5.15.2初識(shí)決策樹信息熵與信息增益5.3決策樹5.4CART5.1初識(shí)決策樹——一般樹簡介樹和圖一樣都是非線性結(jié)構(gòu)，樹是n(n>0)個(gè)結(jié)點(diǎn)和n-1條邊共同組成的有限集合。特殊的，當(dāng)樹的節(jié)點(diǎn)n=0時(shí)，稱這棵樹為空樹。非空樹有以下特征：（1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)（rootnode）；（2）如果n>1,除根結(jié)點(diǎn)以外其它結(jié)點(diǎn)可以分為m(m>0)個(gè)不相交的子集T1,T2,……,Tm，其中每一個(gè)集合都是一棵樹，稱為子樹（subtree）。下圖所示的樹中，各個(gè)節(jié)點(diǎn)通過邊相連，由于每個(gè)節(jié)點(diǎn)所處位置不同被分成不同的節(jié)點(diǎn)。如：A節(jié)點(diǎn)為整棵樹的根節(jié)點(diǎn)，同時(shí)A節(jié)點(diǎn)又是B、C節(jié)點(diǎn)的父節(jié)點(diǎn)（或稱雙親節(jié)點(diǎn)，parentnode），相應(yīng)的B、C節(jié)點(diǎn)為A的子節(jié)點(diǎn)，而一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)稱為這個(gè)節(jié)點(diǎn)的度，而樹的度被定義成整棵樹中度最大的那個(gè)節(jié)點(diǎn)的度。一般樹整棵樹中只有根節(jié)點(diǎn)A沒有父節(jié)點(diǎn)，而D、E、F、G這四個(gè)節(jié)點(diǎn)沒有子節(jié)點(diǎn)（即度為0），樹中度為0的節(jié)點(diǎn)被稱為葉節(jié)點(diǎn)（leafnode，或稱終端節(jié)點(diǎn)terminalnode）。像B、C節(jié)點(diǎn)這種具有同一個(gè)父節(jié)點(diǎn)的互為兄弟節(jié)點(diǎn)。此外，樹還有明顯的層級(jí)結(jié)構(gòu)，根為第1層、其子節(jié)點(diǎn)為第2層，以此類推。如何定位一個(gè)節(jié)點(diǎn)層級(jí)呢？如果從根節(jié)點(diǎn)開始算，用深度表示

；如果從葉節(jié)點(diǎn)開始算，則用高度來表示。5.1初識(shí)決策樹——一般樹簡介如果是由多顆樹組成一個(gè)集合，該集合稱為森林，如下圖。由森林的定義可知，任意一棵樹刪除掉根節(jié)點(diǎn)都會(huì)變成森林。

森林示意圖5.1初識(shí)決策樹——決策樹簡介決策樹是一個(gè)預(yù)測模型，它代表對象屬性與對象值之間的一種映射關(guān)系.如下圖所示為根據(jù)天氣情況決定是否去室外打籃球的決策樹。樹中每個(gè)節(jié)點(diǎn)表示某個(gè)對象，每個(gè)分叉路徑則代表某個(gè)可能的屬性值，而每個(gè)葉節(jié)點(diǎn)都可以找到一條從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)的路徑，這條路徑表示從根節(jié)點(diǎn)開始一直到該葉節(jié)點(diǎn)所經(jīng)歷的各種屬性及其取值。更詳細(xì)的將在5.3節(jié)介紹。

決策樹是一種經(jīng)常要用到的技術(shù)，根據(jù)所解決問題（輸出結(jié)果）的不同可分為回歸樹和分類樹?；貧w樹葉節(jié)點(diǎn)輸出為實(shí)數(shù)，而分類樹輸出為分類信息。目錄/Contents5.15.2初識(shí)決策樹信息熵與信息增益5.3決策樹5.4CART5.2信息熵與信息增益天氣溫度風(fēng)力是否室外打籃球有雨低大否有雨適中大否有雨適中小否無雨低大否無雨高小否無雨適中大否無雨適中小是與前面兩章介紹的機(jī)器學(xué)習(xí)算法類似，決策樹也是根據(jù)訓(xùn)練樣本集得到的。下表是對某人或某些人以往是否去室外打籃球與當(dāng)天的天氣情況的記錄。由左表繪制右圖的決策樹會(huì)碰到一個(gè)問題，該選哪一個(gè)屬性作為根節(jié)點(diǎn)呢？根節(jié)點(diǎn)確定后第2層的子節(jié)點(diǎn)又如何確定呢？一種較常用的辦法就是觀察屬性的熵值，依此制定屬性選擇策略。本小節(jié)主要介紹熵、信息增益的概念。5.2信息熵與信息增益——信息熵香農(nóng)將統(tǒng)計(jì)物理中熵的概念，引入到信道通信的過程中，從而開創(chuàng)了信息論，信息論中熵被稱為信息熵（或香農(nóng)熵）。從常識(shí)講，一條信息的不確定性越大，能預(yù)測它的價(jià)值也就越大。例如，如果一個(gè)算法能夠預(yù)測某支股票的漲跌情況，那這個(gè)算法就非常有價(jià)值；但預(yù)測早上太陽從哪邊升起的算法價(jià)值為0。但在香農(nóng)提出信息熵理論之前，信息的價(jià)值很難量化。信息熵第一次用數(shù)學(xué)語言定量描述了信息與概率之間的關(guān)系，其定義如下式：

5.2信息熵與信息增益——信息熵

隨機(jī)變量服從參數(shù)為p的伯努利分布是指，隨機(jī)變量X分別以概率p和1-p取1或0值。代入信息熵定義公式，求得其熵如式：

5.2信息熵與信息增益——信息熵

5.2信息熵與信息增益——條件熵現(xiàn)實(shí)世界中，經(jīng)常需要通過根據(jù)某個(gè)事件已經(jīng)確定出現(xiàn)的結(jié)果去預(yù)測另一個(gè)事件將要出現(xiàn)某種結(jié)果的可能性。例如，已經(jīng)知道明天天氣無雨、溫度適中、風(fēng)力小，問某個(gè)人在明天這樣天氣狀況條件下，是否會(huì)去室外打籃球？

結(jié)合信息熵定義公式

5.2信息熵與信息增益——條件熵現(xiàn)實(shí)世界中，經(jīng)常需要通過根據(jù)某個(gè)事件已經(jīng)確定出現(xiàn)的結(jié)果去預(yù)測另一個(gè)事件將要出現(xiàn)某種結(jié)果的可能性。例如，已經(jīng)知道明天天氣無雨、溫度適中、風(fēng)力小，問某個(gè)人在明天這樣天氣狀況條件下，是否會(huì)去室外打籃球？

結(jié)合信息熵定義公式

5.2信息熵與信息增益——信息增益兩個(gè)關(guān)聯(lián)的隨機(jī)變量X、Y，已知X的取值情況會(huì)使Y的不確定性減少，而這個(gè)減少程度的度量就靠信息增益。以“是否室外打籃球”那個(gè)表為例，是否室外打籃球這一列的標(biāo)簽值視為隨機(jī)變量，可以計(jì)算出一個(gè)熵H(D)（定義為集合D的經(jīng)驗(yàn)熵）。如果某列特征a（如天氣）給定，可以計(jì)算出條件熵H(D|a)。由前面分析知，條件熵不大于經(jīng)驗(yàn)熵，將經(jīng)驗(yàn)熵與條件熵的差值定義為特征a對訓(xùn)練數(shù)據(jù)集D的信息增益gain(D,a)，如式

計(jì)算信息增益的算法5.2信息熵與信息增益——信息增益計(jì)算訓(xùn)練集D的經(jīng)驗(yàn)熵H(D)：

將本頁ppt中的兩個(gè)公式代入上一頁ppt中的信息增益計(jì)算公式可以算出信息增益5.2信息熵與信息增益——信息增益例

計(jì)算下表中特征“天氣”對整個(gè)訓(xùn)練集的信息增益。

天氣溫度風(fēng)力是否室外打籃球有雨低大否有雨適中大否有雨適中小否無雨低大否無雨高小否無雨適中大否無雨適中小是

5.2信息熵與信息增益——信息增益

中：可求得天氣對于訓(xùn)練集的信息增益。5.2信息熵與信息增益——信息增益

目錄/Contents5.15.2初識(shí)決策樹信息熵與信息增益5.3決策樹5.4CART5.3決策樹——基本概念本節(jié)主要討論分類決策樹。用來描述對實(shí)例進(jìn)行分類的決策樹被稱為分類決策樹。決策樹由節(jié)點(diǎn)、有向邊兩部分組成，節(jié)點(diǎn)又分為內(nèi)部節(jié)點(diǎn)、葉節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)表示特征（或稱屬性），葉節(jié)點(diǎn)表示一個(gè)分類。決策樹的畫法有多種，有從左到右的橫向分布和從上到下的縱向分布兩種結(jié)構(gòu)，以從上到下的縱向分布為主。決策樹的內(nèi)部節(jié)點(diǎn)一般由圓或圓角矩形表示，葉節(jié)點(diǎn)一般由矩形或三角形表示，節(jié)點(diǎn)屬性的取值（有向邊）一般由有向線段表示，如右圖：5.3決策樹——基本概念右圖中，每個(gè)葉節(jié)點(diǎn)都可以通過一條支路追溯到根節(jié)點(diǎn)，而由根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)的路徑都可以較容易地簡化成IF-THEN規(guī)則。路徑上內(nèi)部節(jié)點(diǎn)的特征對應(yīng)規(guī)則的條件，有向邊對應(yīng)條件的取值，而葉節(jié)點(diǎn)對應(yīng)規(guī)則的結(jié)論。在一個(gè)完整的決策樹中，樣本集中的每一個(gè)實(shí)例都有且僅有一條路徑（或者說規(guī)則）覆蓋。由此可見，決策樹實(shí)際上是一個(gè)由若干IF-THEN規(guī)則組成的集合。ifA1==a11:ifA2==a21:#屬于類1else:#屬于類2else:ifA3==a31:#屬于類1elifA4==a41:#屬于類1else:#屬于類25.3決策樹——TDIDT算法由訓(xùn)練集構(gòu)建一個(gè)決策樹需要做那些事呢？決策樹生成一般包括3個(gè)步驟：（1）特征選擇。數(shù)據(jù)挖掘工作中碰到的數(shù)據(jù)大多是凌亂的、特征較多，但一般并不需要把所有的特征都繪入決策樹中，需要對這些特征進(jìn)行選擇，只選擇那些跟分類結(jié)果相關(guān)度較高的特征。常用的特征選擇參考指標(biāo)包括信息增益、信息增益率、基尼指數(shù)等。（2）生成決策樹。生成決策樹工作的本質(zhì)是對內(nèi)部節(jié)點(diǎn)按照重要性進(jìn)行排序，通過計(jì)算特征信息增益或其它指標(biāo)，選擇最佳特征。從根結(jié)點(diǎn)開始，遞歸地產(chǎn)生決策樹，再不斷選取局部最優(yōu)的特征，將訓(xùn)練集分割成能夠基本正確分類的子集，最終生成整棵決策樹。（3）對決策樹進(jìn)行剪枝操作。通過步驟（2）產(chǎn)生的決策樹容易產(chǎn)生過擬合，需要再對其進(jìn)行修剪去掉部分分支，以對抗過擬合。通過前面對決策樹生成的任務(wù)分析，自然能夠想到可以從選擇根節(jié)點(diǎn)開始逐步向下直到葉節(jié)點(diǎn)來生成決策樹，這就是著名的TDIDT算法（Top-DownInductionofDecisionTrees,決策樹的自頂向下歸納生成法）。該算法通過遞歸分裂（recursivepartitioning）方法反復(fù)根據(jù)屬性值進(jìn)行分裂，直到最終到達(dá)葉節(jié)點(diǎn)形成一個(gè)決策分支。5.3決策樹——TDIDT算法由訓(xùn)練集構(gòu)建一個(gè)決策樹需要做那些事呢？輸入一個(gè)訓(xùn)練集，生成一個(gè)決策樹：IF所有的特征對應(yīng)的分類標(biāo)簽相同THEN生成一個(gè)葉節(jié)點(diǎn)，結(jié)束本決策分支ELSE

（1）選擇一個(gè)待分裂的特征（2）

按照特征的取值將訓(xùn)練集分成對應(yīng)子集

（3）為（2）中的每個(gè)非空子集在決策樹上生成一個(gè)分支IF分支的分類標(biāo)簽相同THEN生成一個(gè)葉節(jié)點(diǎn)，結(jié)束本決策分支ELSE回到（1）

遞歸算法，直到遍歷整個(gè)訓(xùn)練集注意：每個(gè)屬性在一條決策分支上最多只能被選擇一次。上述基本TDIDT算法在每個(gè)非葉節(jié)點(diǎn)（即分類標(biāo)簽不同的子集）都需要再選擇屬性進(jìn)行分裂，所選擇的屬性任意，但某個(gè)屬性在同一分支中最多只能選擇一次。因?yàn)橛?xùn)練集中屬性的個(gè)數(shù)、每個(gè)屬性的取值個(gè)數(shù)都是有限的，所以算法是可以終止的。但是，基本TDIDT算法沒有涉及屬性選擇的順序、分支的后續(xù)處理等工作，因此該算法在實(shí)際數(shù)據(jù)挖掘工作中較少使用。5.3決策樹——ID3ID3算法（IterativeDichotomiser3,迭代二叉樹3代）是RossQuinlan發(fā)明的一種用于決策樹生成的貪心算法。受奧卡姆剃刀定律啟發(fā)，ID3算法的指導(dǎo)思想是小型的決策樹優(yōu)于大的決策樹。ID3算法根據(jù)特征的信息增益來選擇屬性分裂的走向，每次選擇信息增益最大的特征作為決策分支的分裂標(biāo)準(zhǔn)。ID3算法偽代碼中，最關(guān)鍵步驟是最優(yōu)特征的選擇，ID3算法最優(yōu)特征選取的標(biāo)準(zhǔn)是信息增益，即以信息增益最大的特征為最優(yōu)特征，然后遞歸。由此可知，ID3算法是一種貪婪算法，是TDIDT算法中的一種。5.3決策樹——ID3例：使用ID3算法，根據(jù)下表的訓(xùn)練集生成決策樹

天氣溫度濕度是否有風(fēng)室外籃球晴熱高無否晴熱高有否陰熱高無是雨適中高無是雨冷正常否是雨冷正常有否陰冷正常有是晴適中高否否晴冷正常否是雨適中正常否是晴適中正常是是陰適中高是是陰熱正常否是雨適中高是否訓(xùn)練集中，有4個(gè)特征“天氣”、“溫度”、“濕度”、“是否有風(fēng)”，分類標(biāo)簽是“是否室外籃球”。根據(jù)ID3算法，本例決策樹生成的步驟為：（1）首先要根據(jù)信息增益找到4個(gè)特征中的最優(yōu)特征，然后按最優(yōu)特征的取值將訓(xùn)練集劃分成若干子集；（2）在上一步分解的各個(gè)子集中繼續(xù)使用ID3算法進(jìn)行屬性分裂。5.3決策樹——ID3例：只示例如何計(jì)算“天氣”這一特征的信息增益，決策樹生成的其它工作由讀者自行完成。訓(xùn)練集中有14個(gè)樣本，標(biāo)簽為“是”的有9個(gè)、“否”的有5個(gè)，因此訓(xùn)練集的經(jīng)驗(yàn)熵為：

接下來以表中的“天氣”特征作為分支標(biāo)準(zhǔn)，根據(jù)“晴”、“陰”、“雨”這三個(gè)特征取值可將訓(xùn)練集分為三類，5.3決策樹——ID3例：

繼續(xù)計(jì)算“天氣”特征的條件熵

因此，“天氣”特征帶來的信息增益為

可以算出“溫度”、“濕度”、“是否有風(fēng)”的信息增益，然后找到信息增益最大的那個(gè)特征作為最優(yōu)特征。另外，由前面的計(jì)算結(jié)果知，“天氣”特征的“陰”這一取值可以生成一個(gè)葉節(jié)點(diǎn)，而另外兩個(gè)取值需要繼續(xù)分裂。5.3決策樹——ID3ID3算法的基本思想是：首先計(jì)算出原始數(shù)據(jù)集的信息熵，然后依次將數(shù)據(jù)中的每一個(gè)特征作為分支標(biāo)準(zhǔn)，并計(jì)算其相對于原始數(shù)據(jù)的信息增益，選擇最大信息增益的分支標(biāo)準(zhǔn)來劃分?jǐn)?shù)據(jù)，因?yàn)樾畔⒃鲆嬖酱?，區(qū)分樣本的能力就越強(qiáng)，越具有代表性，是一種典型的自頂向下的貪心策略。5.3決策樹——C4.5C4.5算法也是TDIDT算法的一種，和ID3一樣也是由RossQuinlan開發(fā)的，該算法是對ID3算法的改進(jìn)。該算法被排在《Top10algorithmsindatamining》（《數(shù)據(jù)挖掘十大算法》）第一位，此書出版后C4.5算法得到了更廣泛使用。相對于ID3，C4.5做了兩方面的改進(jìn)：（1）給出連續(xù)型特征值的處理方法；（2）在決策樹生成中的最優(yōu)特征選取、剪枝等具體方法上做了改進(jìn)。5.3決策樹——C4.5前面講解過程中默認(rèn)特征取值是離散型的，即特征的取值可能是有限的，如“天氣”、“是否有風(fēng)”這兩個(gè)特征。但像“溫度”、“濕度”這一類的特征值，它們實(shí)際上是數(shù)值型變量，它們的取值是連續(xù)的，C4.5算法先將這些連續(xù)型特征值離散化后再進(jìn)行決策樹學(xué)習(xí)。

5.3決策樹——C4.5左側(cè)偽代碼未涉及連續(xù)特征的離散化處理，默認(rèn)在進(jìn)行C4.5決策樹學(xué)習(xí)之前已經(jīng)將連續(xù)特征離散化了。為什么要對連續(xù)屬性進(jìn)行離散化呢？以溫度為例，可能的取值是“12℃”、“13℃”、“12.5℃”等，在進(jìn)行決策樹學(xué)習(xí)的時(shí)候這些值如果不進(jìn)行預(yù)處理會(huì)被看成不同的值，而這些精準(zhǔn)值出現(xiàn)的可能很少或者只出現(xiàn)一次，直接使用這些值進(jìn)行決策樹學(xué)習(xí)的意義不大。而且，在一些實(shí)際應(yīng)用中分類結(jié)果對這些連續(xù)值的差異并不敏感，因此需要對連續(xù)特征值進(jìn)行離散化處理。5.3決策樹——C4.5像天氣的溫度、年齡、身高這一類連續(xù)特征值，可以根據(jù)常識(shí)設(shè)置切割點(diǎn)；還有一類工業(yè)或?qū)Ｓ行袠I(yè)的連續(xù)特征值，可以根據(jù)一些行業(yè)標(biāo)準(zhǔn)之類的設(shè)置切割點(diǎn)。另外，還有很多連續(xù)特征值沒有什么可參照的切割點(diǎn)設(shè)置標(biāo)準(zhǔn)，針對這類連續(xù)特征常用的切割點(diǎn)設(shè)置方法有“等寬區(qū)間法”、“等頻區(qū)間法”兩種。等寬區(qū)間法是指根據(jù)需要在連續(xù)特征值的最大取值和最小取值之間等比例的設(shè)置若干區(qū)間，這種切割點(diǎn)設(shè)置方法簡單易用。但是它存在明顯問題：（1）具體切割成幾個(gè)區(qū)間很難有令人信服的方案；（2）很多值可能會(huì)擁擠在一個(gè)小的區(qū)間內(nèi)，樣本在這個(gè)特征值上并不是均勻分布的。等頻區(qū)間法不是按取值進(jìn)行切割，而是根據(jù)樣本在這個(gè)特征值上的分布進(jìn)行等頻切割。比如訓(xùn)練集中有100個(gè)樣本點(diǎn)，在某個(gè)連續(xù)特征值上從小到大排列，然后每25個(gè)點(diǎn)進(jìn)行切割，最后切割成4個(gè)區(qū)間，也就意味著將這個(gè)連續(xù)的特征值離散化為4個(gè)數(shù)值中的某個(gè)值。等頻區(qū)間法和等值區(qū)間法都存在相同的問題，即切割點(diǎn)附近的樣本點(diǎn)較難處理。以年齡為例，如果將超過35歲的定義為中年人，那35歲生日那一天的前后被切割為不同的離散值是比較沒有說服力的。連續(xù)特征值的離散化操作在整個(gè)決策樹學(xué)習(xí)過程中的進(jìn)行方式也有兩類：一種是在決策樹學(xué)習(xí)的各個(gè)階段分批進(jìn)行，即在決策樹節(jié)點(diǎn)分裂的時(shí)候才對相應(yīng)的連續(xù)特征進(jìn)行切割，被稱為“局部離散化”；另一種是在決策樹學(xué)習(xí)的主體進(jìn)行之前一次性的將連續(xù)特征轉(zhuǎn)換為離散特征，被稱為“全局離散化”5.3決策樹——C4.5決策樹學(xué)習(xí)還有一個(gè)可能碰到的問題被我們刻意回避了。訓(xùn)練集中可能會(huì)存在這樣的多個(gè)樣本點(diǎn)，它們各種特征的取值相同但是分類卻不同。造成這種沖突的原因有兩種：（1）可能是一些樣例的特征值或分類標(biāo)簽出錯(cuò)；（2）訓(xùn)練集的數(shù)據(jù)是正確的，但只靠現(xiàn)有的特征還不足以對樣本進(jìn)行分類。決策樹學(xué)習(xí)中常見的沖突點(diǎn)的處理方法有：（1）刪除有沖突的分支，很明顯這種處理方法可能會(huì)導(dǎo)致一些決策分支缺失，在實(shí)際應(yīng)用中可能會(huì)出現(xiàn)欠擬合；（2）采用類似K近鄰算法的多數(shù)表決策略。決策樹算法的另外一個(gè)常見問題是過擬合。TDIDT算法遞歸地生成決策樹，直到不能繼續(xù)分裂為止。這樣的算法生成的決策樹在訓(xùn)練集上表現(xiàn)良好，但是在測試數(shù)據(jù)分類的準(zhǔn)確率往往不理想，這就是所謂的過擬合現(xiàn)象。解決決策樹過擬合的有效方法是對決策樹進(jìn)行簡化，刪除不必要的子樹或葉節(jié)點(diǎn)，這一過程被稱作剪枝（pruning）。目錄/Contents5.15.2初識(shí)決策樹信息熵與信息增益5.3決策樹5.4CART5.4CARTCART（ClassificationAndRegressionTree，分類回歸樹）算法既可以用于創(chuàng)建分類樹，也可以用于創(chuàng)建回歸樹。CART算法實(shí)現(xiàn)也分成決策樹創(chuàng)建、決策樹剪枝兩個(gè)大的步驟進(jìn)行。CART算法將樣本集拆分成訓(xùn)練集、驗(yàn)證集兩部分。在決策樹創(chuàng)建階段，根據(jù)訓(xùn)練集生成盡量大的決策樹；在剪枝階段，用驗(yàn)證集對第一步生成的決策樹進(jìn)行剪枝，去除不必要的分支，剪枝的目標(biāo)是使得決策樹在驗(yàn)證集上的損失函數(shù)最小。此外，CART假定決策樹是二叉樹，所謂二叉決策樹的意思是決策樹的每個(gè)節(jié)點(diǎn)最多有左、右兩個(gè)子節(jié)點(diǎn)。因此，CART創(chuàng)建的決策樹內(nèi)部節(jié)點(diǎn)的特征取值為“是”和“否”（左分支“是”、右分支“否），在每次判斷過程中，都是對樣本數(shù)據(jù)進(jìn)行二分。CART算法本質(zhì)上是一種二分遞歸分割技術(shù)，把當(dāng)前樣本劃分為兩個(gè)子樣本，使得生成的每個(gè)非葉結(jié)點(diǎn)都有兩個(gè)分支，因此CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹，即使一個(gè)特征有多個(gè)取值，也把它分為兩部分。相對于ID3和C4.5，CART使用基尼（Giniindex）指數(shù)作為特征選取的指標(biāo)，減少了對數(shù)運(yùn)算。5.4CART——基尼指數(shù)不管是ID3中使用的信息增益還是C4.5中使用的信息增益率都存在大量的對數(shù)運(yùn)算，效率較低。CART采用基尼指數(shù)作為分裂規(guī)則，提高運(yùn)算效率。基尼指數(shù)（GiniIndex）又稱為基尼不純度（GiniImpurity），將熵計(jì)算式中的對數(shù)項(xiàng)進(jìn)行泰勒展開并忽略高次項(xiàng)，可以將信息熵的計(jì)算公式簡化為公式

5.4CART——基尼指數(shù)

5.4CART——生成決策樹CART算法生成決策樹有三大步驟：（1）分裂；（2）剪枝；（3）樹選擇。輸入：訓(xùn)練樣本集D；候選特征集A輸出：決策樹CARTTreeGenerate(D,A){根據(jù)最小基尼指數(shù)找到最佳的待分裂特征IF該節(jié)點(diǎn)不能再分THEN將該節(jié)點(diǎn)存為葉節(jié)點(diǎn)執(zhí)行二元切分在右子樹調(diào)用CARTTreeGenerate()方法在左子樹調(diào)用CARTTreeGenerate()方法}CART算法的決策樹分裂過程是二叉遞歸劃分的，特征和預(yù)測目標(biāo)既可以是連續(xù)的也可以是離散的。在樹的生成階段，CART算法會(huì)生成一棵最大尺寸的樹，然后使用專門的測試數(shù)據(jù)對生成的最大樹進(jìn)行測試并剪枝。另外，CART算法生成回歸樹和決策樹的算法在具體處理步驟上有所不同。5.4CART——生成決策樹CART生成分類決策樹要解決的關(guān)鍵問題：（1）選擇最優(yōu)特征；（2）如果最優(yōu)特征的取值可能多于兩個(gè)，需要選擇最優(yōu)二值切分點(diǎn)使這個(gè)特征節(jié)點(diǎn)只生長出左右兩個(gè)分支。這兩個(gè)問題的解決都依賴于前面介紹的基尼指數(shù)。CART分類樹生成算法的遞歸停止條件一般有三條：（1）節(jié)點(diǎn)中的樣本個(gè)數(shù)小于設(shè)定值；（2）樣本子集的基尼指數(shù)小于設(shè)定值；（3）特征集中的特征已被用完。5.4