PPT下載/xiazai/第五章:其他典型分類方法模式識別及Python實現(xiàn)123近鄰法支持向量機(jī)決策樹目錄

CONTENT4隨機(jī)森林5Boosting方法PART

1近鄰法PART01NearestNeighborMethod??

③壓縮近鄰法：基本思想：是在樣本剪輯的基礎(chǔ)上，再去掉一部分靠近兩類中心的樣本，有助于進(jìn)一步縮短計算時間和降低存儲要求。壓縮近鄰法中定義了兩個存儲器A和B，其中A用來存放即將生成的樣本集，B用來存放原樣本集。步驟：（1）隨機(jī)挑選一個樣本放在存儲器A中，其它樣本放在存儲器B中。（2）用當(dāng)前存儲器A中的樣本按最近鄰法對存儲器B中的樣本進(jìn)行分類，假如分類正確，該樣本放回存儲器B；否則放入存儲器A。（3）重復(fù)上述過程，直到在執(zhí)行中沒有一個樣本從存儲器B轉(zhuǎn)到存儲器A或者存儲器B為空為止。PART

2支持向量機(jī)PART02SupportVectorMachine1.線性可分的情況：SVM最初是從線性可分的情況發(fā)展而來的。如圖所示，圓點和方點各代表一類樣本，H為分界線，H1和H2分別為過兩類中距離分界線最近的樣本且與分界線平行的直線。H1和H2之間的距離稱為分類間隔，處在隔離帶的邊緣上的樣本稱為支持向量。最優(yōu)分類線就是要求分類線不但能將兩類樣本正確分類，而且使分類間隔最大。推廣到高維空間，最優(yōu)分類線就變?yōu)榱俗顑?yōu)分類面。線性可分情況下的SVM最優(yōu)分類

線性不可分問題非線性劃分

PART

3決策樹PART03DecisionTree?前面介紹的線性、非線性分類器等分類方法，針對的樣本特征都是數(shù)值特征。然而在實際生活中，對象的特征有些不是數(shù)值特征，如人的性別、國籍、等，只能比較相同或不相同，無法比較相似性和大小，這類特征叫做名義特征；還有一類特征有些是數(shù)值，如學(xué)號、手機(jī)號等，有些不是數(shù)值，如學(xué)歷的級別：初中、高中、本科都存在順序但沒有尺度，這類特征叫作序數(shù)特征。雖然有方法可以將非數(shù)值特征轉(zhuǎn)化為數(shù)值特征，但也存在相應(yīng)的弊端。直接利用非數(shù)值特征對樣本分類將有效避免部分問題。決策樹方法是一種針對非數(shù)值特征的分類方法。在日常生活中，我們常用決策樹的思想做出決策與分類。如左圖是某公司入職申請情況。小張打算入職該公司，而且他不知道面試官的決策思路，但他了解編號1到6員工的信息以及錄用結(jié)果。雖然沒有一例和小張情況相同，但他通過對表5-1進(jìn)行建模得到?jīng)Q策樹進(jìn)行分類，大致得到了自己的申請結(jié)果。表5-1某公司入職申請數(shù)據(jù)基本概念決策樹是常見的分類方法，是一種對實例進(jìn)行分類的樹形結(jié)構(gòu)。決策樹由一系列節(jié)點組成，節(jié)點分為內(nèi)部節(jié)點和葉結(jié)點，左圖為小張畫出的決策樹。方形的節(jié)點為內(nèi)部節(jié)點，橢圓的節(jié)點為葉節(jié)點，頂部的內(nèi)部節(jié)點稱為根節(jié)點。每一個內(nèi)部節(jié)點代表一個屬性和相應(yīng)的決策規(guī)則，內(nèi)部節(jié)點下面的分支表示不同的判斷結(jié)果，如果分支后面是葉節(jié)點，說明已經(jīng)能夠得到該樣例的分類；如果分支后面是內(nèi)部節(jié)點，則需要根據(jù)該樣例的其他屬性做出判斷，直到遇到葉節(jié)點。如果決策樹中每個內(nèi)部節(jié)點下都只有兩條分支，那么可以被稱為二叉樹，否則稱為多叉樹。如果樣例的分類只有兩種，那么該模型是二分類模型，否則是多分類模型。下圖的決策樹就是一個二叉樹，且該模型是二分類模型。需要注意的是，一個屬性可以在樹的多個不同分支出現(xiàn)，如果該公司面對一個月薪要求大于等于15000的博士應(yīng)屆生時，還要考慮年齡是否超過40歲，則決策過程可以表示為如右圖所示的模型。有多種構(gòu)造決策樹的方法，這些方法都是從根節(jié)點出發(fā)，依次對屬性進(jìn)行分類。分類決策樹的構(gòu)造分為以下3步。（1）確定分割規(guī)則?；蛘哒f確定劃分的屬性及其閾值，將數(shù)據(jù)劃分成不相交的子集，再為每個子集確定劃分屬性。如圖5-1所示，優(yōu)先選擇“月薪”這一屬性并以15000為閾值，將數(shù)據(jù)劃分為大于等于15000的2、3、5、6為一組；和小于15000的1、4為一組；再為小于15000的一組選擇“年齡”這一屬性并以25為閾值繼續(xù)劃分。（2）確定葉節(jié)點。確定當(dāng)前節(jié)點是繼續(xù)分割還是作為葉節(jié)點，判斷的標(biāo)準(zhǔn)是：如果當(dāng)前節(jié)點中每個成員都屬于相同的類，那么就可以當(dāng)作葉節(jié)點；否則繼續(xù)選擇屬性對該節(jié)點的成員進(jìn)行劃分。（3）把類別賦予葉節(jié)點。下圖是由前面表的數(shù)據(jù)歸納成的另一種決策樹。選擇哪一個屬性來劃分當(dāng)前節(jié)點成員直接決定決策樹的結(jié)構(gòu)。這就需要一種指標(biāo)來評價每個屬性，從中選取最優(yōu)者。評價指標(biāo)包括信息增益、信息增益率、基尼指數(shù)等，相應(yīng)的決策樹算法就分為ID3、C4.5、CART等。

5.剪枝處理決策樹龐大有可能導(dǎo)致在訓(xùn)練集上表現(xiàn)很好，但在測試數(shù)據(jù)上的表現(xiàn)與訓(xùn)練數(shù)據(jù)差別很大，即過擬合的情況。決策樹越復(fù)雜，過擬合的程度越高。為了避免過擬合，需要對決策樹進(jìn)行剪枝。一般情況下，有兩種剪枝策略，分別是預(yù)剪枝和后剪枝。預(yù)剪枝就是控制決策樹的生長。在決策樹生長過程中，每個節(jié)點在劃分前，先對其進(jìn)行估計，如果該節(jié)點的劃分不能提升決策樹的泛化性能，那么不再劃分該節(jié)點并設(shè)為葉節(jié)點。對于決策樹的泛化性能，可以將數(shù)據(jù)集分為訓(xùn)練集和測試集，使用節(jié)點劃分前后決策樹在測試集上的正確率來體現(xiàn)泛化性能。用表5-2和表5-3的蘋果數(shù)據(jù)集詳細(xì)說明剪枝過程。

預(yù)剪枝使得決策樹部分分支沒有生長，這一定程度上降低了過擬合的風(fēng)險。但有些分支的生長雖然不能提升決策樹的泛化性能，其后續(xù)的分支有可能提升泛化性能。預(yù)剪枝使這種類型的分支無法生長，導(dǎo)致決策樹有欠擬合的風(fēng)險。后剪枝是在決策樹生長完后再對其進(jìn)行修剪。其核心思想是：從葉節(jié)點出發(fā)，如果減去具有相同父節(jié)點的葉結(jié)點會使決策樹的泛化性能提升，則執(zhí)行剪枝，并將父節(jié)點作為新的葉節(jié)點。以回溯的形式剪去不必要的節(jié)點，直到?jīng)]有可剪枝的節(jié)點為止。表5-2的蘋果數(shù)據(jù)集不進(jìn)行剪枝，則可生成如下圖1所示的決策樹。對圖1所示決策樹進(jìn)行后剪枝操作，決策樹經(jīng)過一次后剪枝操作得到的決策樹，如圖2所示。剪枝后的決策樹在驗證集上的精度為85.71%，與沒有剪枝的決策樹的精度相同，決策樹的泛化性能沒有變化。這種情況下選擇更簡潔的決策樹，同時合并同一父節(jié)點下相同類別的葉節(jié)點，得到如圖2所示的決策樹。對于當(dāng)前決策樹，繼續(xù)判斷是否需要剪枝。如果繼續(xù)剪枝，決策樹僅剩根節(jié)點，根據(jù)訓(xùn)練集樣本類別數(shù)，根節(jié)點類別為“是”或“否”都可以，在驗證集上的精度分別為42.85%和57.14%，均小于剪枝前的85.71%，所以當(dāng)前決策樹不需要剪枝。一般情況下，后剪枝決策樹比預(yù)剪枝決策樹擁有更多分支，欠擬合風(fēng)險更小，泛化性能更好。但由于后剪枝前需要先生成完整決策樹，所以后剪枝決策樹訓(xùn)練時間更久。圖1蘋果數(shù)據(jù)集不剪枝時對應(yīng)的決策樹