Python數(shù)據(jù)挖掘算法與應(yīng)用 課件 劉金嶺 第6-10章 分類模型-深度學(xué)習(xí)簡(jiǎn)介

第6章

分類模型KNN分類模型6.2Rocchio分類器模型6.3

決策樹模型6.4貝葉斯分類模型6.5

概述6.1

支持向量機(jī)6.6

分類模型的評(píng)估與選擇6.7學(xué)習(xí)目標(biāo)1概述summarize6.1基本概念

訓(xùn)練集和測(cè)試集機(jī)器學(xué)習(xí)常常需要處理的一個(gè)問題是劃分訓(xùn)練集和測(cè)試集。訓(xùn)練集是用來訓(xùn)練模型的，給模型輸入和對(duì)應(yīng)的輸出，讓模型學(xué)習(xí)它們之間的關(guān)系。測(cè)試集是用來估計(jì)模型的訓(xùn)練水平，比如分類器的分類精確度、預(yù)測(cè)的誤差等，可以根據(jù)測(cè)試集的表現(xiàn)來選擇最好的模型。機(jī)器學(xué)習(xí)就是利用訓(xùn)練集訓(xùn)練出分類模型后，再用測(cè)試集來評(píng)估其誤差，作為對(duì)泛化誤差的估計(jì)。給定一個(gè)只包含樣本對(duì)象的數(shù)據(jù)集，如何從中產(chǎn)生訓(xùn)練集和測(cè)試集呢?

下面介紹三種常見的做法。1.留出法留出法（Hold-out）是直接將數(shù)據(jù)集劃分成兩個(gè)互斥的集合，其中一個(gè)集合作為訓(xùn)練集，留下的集合作為測(cè)試集。常見做法將大約2/3~4/5的樣本作為訓(xùn)練集，剩下的作為測(cè)試集。以二分類任務(wù)為例，假設(shè)數(shù)據(jù)集包含1000個(gè)樣本，我們采取7:3分樣，將訓(xùn)練集劃分為包含700個(gè)樣本，測(cè)試集包含300個(gè)樣本。Python通過調(diào)用train_test_split()函數(shù)按比例劃分訓(xùn)練集和測(cè)試集，該函數(shù)在sklearn中屬于model_slection模塊，常用形式為：X_train,X_test,Y_train,Y_test=sklearn.model_selection.train_test_split(train_data,train_target,test_size=0.4,random_state=0,stratify=y_train)例6.1留出法生成訓(xùn)練集和測(cè)試集示例。importnumpyasnpfromsklearn.model_selectionimporttrain_test_splitX,Y=np.arange(10).reshape(5,2),range(5)print('X=\n',X)print('Y=\n',Y)X_train,X_test,Y_train,Y_test=train_test_split(X,Y,test_size=0.30,random_state=42)print('X_train=\n',X_train)print('X_test=\n',X_test)print('Y_train=\n',Y_train)print('Y_test=\n',Y_test)2.交叉驗(yàn)證法交叉驗(yàn)證法（CrossValidation）將源數(shù)據(jù)集劃分為大小相似的若干互斥子集，每個(gè)子集都盡可能地保持?jǐn)?shù)據(jù)分布的一致性。然后，將每個(gè)子集數(shù)據(jù)分別做一次測(cè)試集，其余的K-1組子集數(shù)據(jù)作為訓(xùn)練集，這樣會(huì)得到K個(gè)模型，用這K個(gè)模型分類準(zhǔn)確率的平均數(shù)作為此交叉驗(yàn)證法的性能指標(biāo)。交叉驗(yàn)證法評(píng)估結(jié)果的穩(wěn)定性和保真性在很大程度上取決于K的取值，最常用的取值是10，有時(shí)也取5或20等。通過調(diào)用KFold()函數(shù)按交叉驗(yàn)證法劃分訓(xùn)練集和測(cè)試集，KFold()在sklearn中屬于model_slection模塊，常用形式為：KFold(n_splits=’warn’,shuffle=False,random_state=None)常用方法：(1)get_n_splits([X,y,groups])返回劃分的子集數(shù)。(2)split(X[,Y,groups])返回分類后數(shù)據(jù)集的index。例6.2交叉驗(yàn)證法生成訓(xùn)練集和測(cè)試集示例。importnumpyasnpfromsklearn.model_selectionimportKFoldX=np.arange(60).reshape(30,2)print('X=\n',X)kf=KFold(n_splits=10)fortrain_index,test_indexinkf.split(X):print('X_train:\n%s'%X[train_index])print('X_test:\n%s'%X[test_index])3.自助法自助法（Self-help）適用于樣本量較小，并且難以劃分時(shí)。自助法產(chǎn)生的樣本改變了數(shù)據(jù)的分布，會(huì)引入估計(jì)偏差。給定包含n個(gè)樣本的數(shù)據(jù)集D，我們對(duì)它進(jìn)行采樣產(chǎn)生數(shù)據(jù)集D’：每次隨機(jī)從D中挑選一個(gè)樣本，將其復(fù)制到D’中，然后再將其樣本放回原始數(shù)據(jù)集D中，使得該樣本在下次采樣的時(shí)候也可能被采集到；這個(gè)過程重復(fù)執(zhí)行m次，就得到了包含m個(gè)樣本的數(shù)據(jù)集D’。簡(jiǎn)言之，就是從數(shù)據(jù)集D中，有放回隨機(jī)采樣m次，組成一個(gè)新樣本集D’。用采樣所得的D’作為訓(xùn)練集，D-D’作為樣本的測(cè)試集。由此可以看出，有一部分樣本沒有出現(xiàn)在D’中，會(huì)有一部分樣本重復(fù)出現(xiàn)。一個(gè)樣本在m次采樣過程中始終沒有被采集到的概率是

。當(dāng)樣本量m=10時(shí)，沒有被采集到的概率p=0.3487；當(dāng)樣本量趨于無窮時(shí)，

。所以，采用自助法采樣時(shí)，大約會(huì)有35%的數(shù)據(jù)沒有出現(xiàn)在D’中。例6.3自助法生成訓(xùn)練集和測(cè)試集示例。importnumpyasnpX=[1,4,3,23,4,6,7,8,9,45,67,89,34,54,76,98,43,52]#設(shè)置一個(gè)數(shù)據(jù)集bootstrapping=[]#通過產(chǎn)生的隨機(jī)數(shù)獲得采集樣本的序號(hào)foriinrange(len(X)):bootstrapping.append(np.floor(np.random.random()*len(X)))D_1=[]foriinrange(len(X)):D_1.append(X[int(bootstrapping[i])])print('生成的訓(xùn)練集：\n',D_1)D=[itemforiteminXifitemnotinset(D_1)]print('生成的測(cè)試集：\n',D)在前兩種方法中都保留部分樣本用于測(cè)試，因此實(shí)際評(píng)估模型使用的訓(xùn)練集總是比期望評(píng)估模型使用的訓(xùn)練集小，這樣會(huì)引入一些因訓(xùn)練樣本規(guī)模不同而導(dǎo)致的估計(jì)偏差。分類流程分類訓(xùn)練的結(jié)果是產(chǎn)生一個(gè)分類器或分類模型，進(jìn)而根據(jù)構(gòu)建的模型對(duì)測(cè)試數(shù)據(jù)進(jìn)行預(yù)測(cè)，得到相應(yīng)的類標(biāo)簽。類標(biāo)簽的數(shù)據(jù)種類可以有二分類或多分類。學(xué)習(xí)利用數(shù)據(jù)進(jìn)行模型參數(shù)的調(diào)節(jié)過程稱為訓(xùn)練或?qū)W習(xí)是否

分類器選擇模型訓(xùn)練獲取分類模型分類模型訓(xùn)練性能指標(biāo)選擇性能評(píng)估是否繼續(xù)迭代調(diào)整模型預(yù)測(cè)數(shù)據(jù)調(diào)整參數(shù)訓(xùn)練數(shù)據(jù)集測(cè)試數(shù)據(jù)集數(shù)據(jù)集類標(biāo)簽圖6.1分類預(yù)測(cè)的一般流程2KNN分類模型6.2K-NearestNeighboralgorithmKNN算法概述KNN是一種基于類比學(xué)習(xí)的分類算法，其算法原理是在訓(xùn)練數(shù)據(jù)集中找出K個(gè)與預(yù)測(cè)樣本距離最近且最相似的樣本，這些樣本大部分屬于哪個(gè)類別，則該預(yù)測(cè)樣本也屬于哪個(gè)類別。例6.4表6.1中有11個(gè)同學(xué)的小學(xué)畢業(yè)成績(jī)和6年后高考錄取的情況，現(xiàn)在已知“李玉嬌”同學(xué)的小學(xué)畢業(yè)成績(jī)了，可以根據(jù)KNN算法來預(yù)測(cè)未來高考錄取的情況。姓名語(yǔ)文數(shù)學(xué)英語(yǔ)6年后高考錄取情況趙曉晴100100100重點(diǎn)院校錢小偉909897本科院校孫曉麗909085?？圃盒＠钭雍?009093本科院校周武809070?？圃盒莿佘?0080100本科院校鄭明959595重點(diǎn)院校王欣麗959080?？圃盒ｑT麗君907590?？圃盒ｊ悅}(cāng)959590本科院校儲(chǔ)云峰10010095重點(diǎn)院校李玉嬌979692？姓名6年后高考錄取情況與李玉嬌同學(xué)距離趙曉晴重點(diǎn)院校9.434錢小偉本科院校8.832孫曉麗專科院校11.576李子航本科院校12.207周武?？圃盒?8.443吳勝軍本科院校18.138鄭明重點(diǎn)院校3.724王欣麗?？圃盒?3.565馮麗君專科院校22.226陳倉(cāng)本科院校3.000儲(chǔ)云峰重點(diǎn)院校5.831表6.1小學(xué)畢業(yè)主要科目成績(jī)表表6.2“李玉嬌”同學(xué)與各位同學(xué)的距離逐一計(jì)算各位同學(xué)與“李玉嬌”同學(xué)的距離，如表6.2所示。然后我們選定3位（即這里的K=3）最為鄰近的同學(xué)，預(yù)測(cè)“李玉嬌”同學(xué)最終高考可能錄取的情況。距離“李玉嬌”同學(xué)最近的3名同學(xué)中有2名被“重點(diǎn)院?！薄?名被“本科院?！变浫。灶A(yù)測(cè)李玉嬌同學(xué)6年后高考最有可能被“重點(diǎn)院?！变浫?。KNN算法描述

KNN算法描述如下：step1計(jì)算預(yù)測(cè)數(shù)據(jù)樣本與各個(gè)訓(xùn)練數(shù)據(jù)樣本之間的距離；step2按照距離的遞增關(guān)系進(jìn)行排序；step3選取距離最小的K個(gè)數(shù)據(jù)樣本（前面K個(gè)）；step4確定前K個(gè)數(shù)據(jù)樣本所在類別的出現(xiàn)頻率；step5前K個(gè)數(shù)據(jù)樣本中出現(xiàn)頻率最高的類別作為預(yù)測(cè)數(shù)據(jù)樣本的類別。KNN算法是目前較為常用且成熟的分類算法，但是KNN算法也有一定的不足。KNN算法描述KNN主要優(yōu)點(diǎn)(1)簡(jiǎn)單好用，容易理解，精度高，理論成熟，既可以用來做分類也可以用來做回歸。(2)可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)。(3)訓(xùn)練時(shí)間復(fù)雜度為O(n)，無數(shù)據(jù)輸入假定。(4)對(duì)異常值不敏感。KNN主要缺點(diǎn)：(1)計(jì)算復(fù)雜性高、空間復(fù)雜性高。(2)當(dāng)樣本不平衡（有些類別的樣本數(shù)量很大，而其它樣本的數(shù)量又很少）時(shí)，容易產(chǎn)生誤分。(3)一般樣本數(shù)量很大的時(shí)候不用KNN，因?yàn)橛?jì)算量很大。但是數(shù)據(jù)樣本量又不能太少，此時(shí)容易產(chǎn)生誤分。(4)無法給出數(shù)據(jù)的內(nèi)在含義。Python實(shí)現(xiàn)KNN分類算法例6.5Python編程實(shí)現(xiàn)KNN分類算法示例。訓(xùn)練數(shù)據(jù)集如例6.4中表6.1所示。#trainData-訓(xùn)練集、testData-測(cè)試集、labels-分類defknn(trainData,testData,labels,k):rowSize=trainData.shape[0]#計(jì)算訓(xùn)練樣本的行數(shù)diff=np.tile(testData,(rowSize,1))-trainData#計(jì)算訓(xùn)練樣本和測(cè)試樣本的差值sqrDiff=diff**2#計(jì)算差值的平方和sqrDiffSum=sqrDiff.sum(axis=1)distances=sqrDiffSum**0.5#計(jì)算距離sortDistance=distances.argsort()#對(duì)所得的距離從低到高進(jìn)行排序count={}foriinrange(k):vote=labels[sortDistance[i]]count[vote]=count.get(vote,0)+1

01KNN算法實(shí)現(xiàn)sortCount=sorted(count.items(),reverse=True)#對(duì)類別出現(xiàn)的頻數(shù)從高到低進(jìn)行排序returnsortCount[0][0]#返回出現(xiàn)頻數(shù)最高的類別importnumpyasnptrainData=np.array([[100,100,100],[90,98,97],[90,90,85],[100,90,93],[80,90,70],[100,80,100],[95,95,95],[95,90,80],[90,75,90],[95,95,90],[100,100,95]])labels=['重點(diǎn)院校','本科院校','?？圃盒?,'本科院校','?？圃盒?,'本科院校','重點(diǎn)院校','?？圃盒?,'專科院校','本科院校','重點(diǎn)院校']testData=[97,96,92]X=knn(trainData,testData,labels,3)print(X)Python實(shí)現(xiàn)KNN分類算法02KNeighborsClassifier()在scikit-learn中，與KNN法這一大類相關(guān)的類庫(kù)都在sklearn.neighbors包之中。當(dāng)使用函數(shù)KNeighborsClassifier()進(jìn)行分類時(shí)，需要導(dǎo)入相關(guān)的類庫(kù)，語(yǔ)句為：fromsklearnimportneighbors。常用形式為：KNeighborsClassifier(n_neighbors=5,weights=’uniform’)參數(shù)說明：(1)n_neighbors：KNN中的k值，默認(rèn)為5。(2)weights：用于標(biāo)識(shí)最近鄰樣本的權(quán)重，取值為：’uniform’和’distance’。默認(rèn)’uniform’，表示所有最近鄰樣本權(quán)重都一樣；當(dāng)取值為’distance’時(shí)，表示自定義權(quán)重。如果樣本分布是比較均勻的，取值’uniform’效果較好；如果樣本分布比較亂，規(guī)律不好尋找時(shí)，取值’distance’效果比較好。例6.6用KNN對(duì)鳶尾花數(shù)據(jù)集進(jìn)行分類。importmatplotlib.pyplotaspltimportnumpyasnpfrommatplotlib.colorsimportListedColormapfromsklearnimportneighbors,datasetsn_neighbors=11#取k=11iris=datasets.load_iris()#導(dǎo)入鳶尾花數(shù)據(jù)集x=iris.data[:,:2]#取前兩個(gè)feature,方便在二維平面上畫圖y=iris.targeth=.02#網(wǎng)格中的步長(zhǎng)cmap_light=ListedColormap(['#FFAAAA','#AAFFAA','#AAAAFF'])#創(chuàng)建彩色的圖cmap_bold=ListedColormap(['#FF0000','#00FF00','#0000FF'])forweightsin['uniform','distance']:#繪制兩種weights參數(shù)的KNN效果圖clf=neighbors.KNeighborsClassifier(n_neighbors,weights=weights)#創(chuàng)建了一個(gè)KNN分類器的實(shí)例，并擬合數(shù)據(jù)clf.fit(x,y)#繪制決策邊界。為此，將為每個(gè)數(shù)據(jù)對(duì)分配一個(gè)顏色來繪制網(wǎng)格中的點(diǎn)[x_min,x_max]、[y_min,y_max]x_min,x_max=x[:,0].min()-1,x[:,0].max()+1y_min,y_max=x[:,1].min()-1,x[:,1].max()+1xx,yy=np.meshgrid(np.arange(x_min,x_max,h),np.arange(y_min,y_max,h))Z=clf.predict(np.c_[xx.ravel(),yy.ravel()])#將結(jié)果放入一個(gè)彩色圖中Z=Z.reshape(xx.shape)plt.figure()plt.pcolormesh(xx,yy,Z,cmap=cmap_light)#繪制訓(xùn)練點(diǎn)

plt.scatter(x[:,0],x[:,1],c=y,cmap=cmap_bold)plt.xlim(xx.min(),xx.max())plt.ylim(yy.min(),yy.max())plt.title("3-Classclassification(k=%i,weights='%s')"%(n_neighbors,weights))plt.show()程序運(yùn)行結(jié)果圖之一如圖6.2所示。圖6.2例6.6程序運(yùn)行結(jié)果K值的確定KNN算法中只有一個(gè)超參數(shù)K，K值的確定對(duì)KNN算法的預(yù)測(cè)結(jié)果有著至關(guān)重要的影響。如圖6.3所示。？圖6.3k值對(duì)分類影響的示意圖如圖6.3所示，小圓要被決定賦予哪個(gè)類，是小三角形還是小正方形？如果K=3，由于小三角形所占比例為2/3，小圓將被賦予小三角形那個(gè)類標(biāo)簽；如果K=7，由于小正方形比例為4/7，因此小圓被賦予小正方形類別標(biāo)簽。K值的確定如果K值比較小，相當(dāng)于在較小的領(lǐng)域內(nèi)訓(xùn)練樣本并對(duì)實(shí)例（預(yù)測(cè)樣本）進(jìn)行預(yù)測(cè)。這時(shí)，算法的近似誤差會(huì)比較小，因?yàn)橹挥信c實(shí)例相近的訓(xùn)練樣本才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用。但是，它也有明顯的缺點(diǎn)：算法的估計(jì)誤差比較大，預(yù)測(cè)結(jié)果會(huì)對(duì)鄰近點(diǎn)十分敏感，如果鄰近點(diǎn)是噪聲點(diǎn)的話，預(yù)測(cè)就會(huì)出錯(cuò)。因此，K值過小容易導(dǎo)致KNN算法的過擬合。同理，如果K值選擇較大的話，距離較遠(yuǎn)的訓(xùn)練樣本也能夠?qū)?shí)例預(yù)測(cè)結(jié)果產(chǎn)生影響。這時(shí)候，模型相對(duì)比較魯棒，不會(huì)因?yàn)閭€(gè)別噪聲對(duì)最終預(yù)測(cè)結(jié)果產(chǎn)生影響。但是缺點(diǎn)也十分明顯：算法的鄰近誤差會(huì)偏大，距離較遠(yuǎn)的點(diǎn)（與預(yù)測(cè)實(shí)例不相似）也會(huì)同樣對(duì)預(yù)測(cè)結(jié)果產(chǎn)生影響，使得預(yù)測(cè)結(jié)果產(chǎn)生較大偏差，此時(shí)模型容易發(fā)生欠擬合。在實(shí)際工程實(shí)踐中，一般采用交叉驗(yàn)證的方式選取K值。通過以上分析可知，一般盡量在較小范圍內(nèi)選取K值，同時(shí)把測(cè)試集上準(zhǔn)確率最高的那個(gè)K值確定為最終算法的參數(shù)K。例6.7使用交叉驗(yàn)證方法確定K值示例。fromsklearn.datasetsimportload_irisfromsklearn.model_selectionimportcross_val_scoreimportmatplotlib.pyplotaspltfromsklearn.neighborsimportKNeighborsClassifieriris=load_iris()#讀取鳶尾花數(shù)據(jù)集x=iris.datay=iris.targetk_range=range(1,31)k_error=[]forkink_range:#循環(huán)，取K=1到K=31，查看誤差效果knn=KNeighborsClassifier(n_neighbors=k)scores=cross_val_score(knn,x,y,cv=6,scoring='accuracy')#cv參數(shù)決定數(shù)據(jù)集劃分比例k_error.append(1-scores.mean())plt.plot(k_range,k_error)#畫圖，x軸為k值，y值為誤差值plt.xlabel('ValueofKforKNN')plt.ylabel('Error')plt.show()程序運(yùn)行結(jié)果如圖6.4所示。圖6.4例6.7程序運(yùn)行結(jié)果由圖6.4能夠明顯看出K值取12的時(shí)候誤差最小。當(dāng)然在實(shí)際問題中，如果數(shù)據(jù)集比較大，為了減少訓(xùn)練時(shí)間，K的取值范圍可以縮小，例如K取值范圍為[10,15]。3Rocchio分類器模型6.3RocchioclassifiermodelRocchio算法簡(jiǎn)述02應(yīng)用于文本分類

Rocchio算法基本的思路是把一個(gè)類別里文檔的各特征詞取平均值（例如把所有“體育”類文檔中詞匯“籃球”出現(xiàn)的次數(shù)取平均值，再把“裁判”取平均值，依次做下去），可以得到一個(gè)新的向量，形象的稱之為“質(zhì)心”，質(zhì)心就成了這個(gè)類別中最具有代表性的向量表示。如果有新文檔需要判斷的時(shí)候，只需要計(jì)算新文檔和質(zhì)心的相似度（或計(jì)算它們之間的距離）就可以確定新文檔是否屬于這個(gè)類。改進(jìn)的Rocchio算法不僅考慮屬于這個(gè)類別的文檔（稱為正樣本），也考慮不屬于這個(gè)類別的文檔（稱為負(fù)樣本）。計(jì)算出來的質(zhì)心在靠近正樣本的同時(shí)盡量遠(yuǎn)離負(fù)樣本。Rocchio算法是信息檢索中處理相關(guān)反饋的一個(gè)著名算法。01應(yīng)用于信息檢索03Rocchio算法的優(yōu)缺點(diǎn)Rocchio算法的優(yōu)缺點(diǎn)如下：優(yōu)點(diǎn)：算法很容易理解，也容易實(shí)現(xiàn)；訓(xùn)練和分類計(jì)算特別簡(jiǎn)單；常用來實(shí)現(xiàn)衡量分類系統(tǒng)性能的基準(zhǔn)系統(tǒng)。缺點(diǎn)：算法源于兩個(gè)假設(shè)。一是假設(shè)同類別的文檔僅僅聚集在一個(gè)質(zhì)心的周圍，但對(duì)于線性不可分的文檔集失效；二是假設(shè)訓(xùn)練數(shù)據(jù)是絕對(duì)正確的，但對(duì)于含有噪聲的數(shù)據(jù)算法效果較差。Rocchio算法原理及分類器構(gòu)建Rocchio算法是信息檢索中通過查詢的初始匹配文檔對(duì)原始查詢進(jìn)行修改以優(yōu)化查詢的方法。它是相關(guān)反饋實(shí)現(xiàn)中的一個(gè)經(jīng)典算法，提供了一種將相關(guān)反饋信息融合到向量空間模型的方法?；纠碚摚杭俣ㄒ乙粋€(gè)最優(yōu)查詢向量，它與相關(guān)文檔之間的相似度最大且同時(shí)又和不相關(guān)文檔之間的相似度最小。假定有一個(gè)用戶查詢，并知道部分相關(guān)文檔和不相關(guān)文檔的信息，則可以通過如下公式得到修改后的查詢向量：其中是原始的查詢向量，Dr和Dnr是已知的相關(guān)和不相關(guān)文檔集合。α、β及γ是上述三者的權(quán)重。這些權(quán)重能夠控制判定結(jié)果和原始查詢向量之間的平衡：如果存在大量已判斷的文檔，那么會(huì)給β及γ賦予較高的權(quán)重。修改后的新查詢從開始，向著相關(guān)文檔的質(zhì)心向量靠近了一段距離，而同時(shí)又于不相關(guān)文檔的質(zhì)心向量遠(yuǎn)離了一段距離。新查詢可以采用常規(guī)的向量空間模型進(jìn)行檢索。通過減去不相關(guān)文檔的向量，很容易保留向量空間的正值分量。在Rocchio算法中，文檔向量中的權(quán)重分量如果為負(fù)值，那么該分量將會(huì)被忽略，也就是說，此時(shí)會(huì)將該分量權(quán)重設(shè)為0。圖6.5給出了應(yīng)用相關(guān)反饋技術(shù)的效果示意圖?！痢痢痢痢痢痢痢痢痢痢痢脸跏疾樵冃薷暮蟮牟樵儭翞橐阎牟幌嚓P(guān)文檔為已知的相關(guān)文檔圖6.5應(yīng)用相關(guān)反饋技術(shù)的效果示意圖Rocchio算法原理及分類器構(gòu)建相關(guān)反饋可以同時(shí)提高召回率和正確率。這其中的部分原因在于它對(duì)查詢進(jìn)行了擴(kuò)展，另一個(gè)原因是應(yīng)用的場(chǎng)景所帶來的結(jié)果：在期望高召回率的情況下，可以預(yù)計(jì)用戶可能會(huì)花費(fèi)更多時(shí)間來瀏覽結(jié)果并進(jìn)行反復(fù)搜索。正反饋往往比負(fù)反饋更有價(jià)值，因此在很多信息檢索系統(tǒng)中，會(huì)將參數(shù)設(shè)置成γ<β。一個(gè)合理的取值是α=1、β=0.75及γ=0.15。實(shí)際上，有很多系統(tǒng)都只允許進(jìn)行正反饋，即相當(dāng)于設(shè)置γ=0。還有一種做法是，只取檢索系統(tǒng)返回結(jié)果中排名最高的標(biāo)記為不相關(guān)的文檔進(jìn)行負(fù)反饋，此時(shí)，公式中的|Dnr|=1。盡管上述相關(guān)反饋方法存在各種變形，并且很多比較實(shí)驗(yàn)也沒有取得一致性的結(jié)論，但是一些研究卻認(rèn)為一種稱為Idedec-hi的公式最有效或至少在性能上表現(xiàn)最穩(wěn)定。Idedec-hi的公式如下：

（6-2）Python實(shí)現(xiàn)Rocchio文本分類例6.8Rocchio文本分類示例。假設(shè)文檔集合TxtSet={Doc1,Doc2,Doc3,Doc4,Doc5,Doc6,Doc7,Doc8,Doc9}，特征詞詞頻統(tǒng)計(jì)矩陣如表6.3所示。

表6.3文檔-特征詞詞頻統(tǒng)計(jì)表利用訓(xùn)練集（Doc1-Doc7）中的文檔構(gòu)造Rocchio文本分類模型，對(duì)測(cè)試集（Doc8-Doc9）進(jìn)行文本分類測(cè)試，其中文本特征詞的權(quán)值由tf-idf公式給出。

W1W2W3W4W5W6W7W8Doc120430102Doc202402300Doc340130101Doc401020010Doc500200400Doc611020113Doc721340202Doc831041021Doc9003015014決策樹模型6.4DecisionTree，DT決策樹分類概述（一）概述所謂決策樹分類器是一種描述對(duì)數(shù)據(jù)樣本進(jìn)行分類的樹形結(jié)構(gòu)。決策樹由節(jié)點(diǎn)（Node）和邊（DirectedEdge）組成。節(jié)點(diǎn)有兩種類型：內(nèi)部節(jié)點(diǎn)（InternalNode）和葉節(jié)點(diǎn)（LeafNode）。內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩裕~節(jié)點(diǎn)表示一個(gè)類別。在決策樹中數(shù)據(jù)樣本的類別是通過從樹根開始根據(jù)數(shù)據(jù)樣本滿足的條件依次向下移動(dòng)直到樹葉節(jié)點(diǎn)為止，數(shù)據(jù)樣本的類別就是相應(yīng)葉節(jié)點(diǎn)的類別。（二）示意圖圖6.6就是一個(gè)決策樹示意圖，它描述了一個(gè)顧客購(gòu)買電腦的分類模型，利用它可以對(duì)一個(gè)顧客是否會(huì)在本商場(chǎng)購(gòu)買電腦進(jìn)行分類預(yù)測(cè)。決策樹的內(nèi)部節(jié)點(diǎn)通常用矩形表示而葉子節(jié)點(diǎn)常用橢圓表示。年齡學(xué)生<30NOYESYESNOYES信用等級(jí)>4030-40否是一般良好圖6.6沿著根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑有五條，形成了五條分類規(guī)則：規(guī)則1：if年齡<30and是學(xué)生then會(huì)購(gòu)買電腦規(guī)則2：if年齡<30and不是學(xué)生then不會(huì)購(gòu)買電腦規(guī)則3：if年齡在30到40之間then會(huì)購(gòu)買電腦規(guī)則4：if年齡>40and信用等級(jí)良好then會(huì)購(gòu)買電腦規(guī)則5：if年齡>40and信用等級(jí)一般then不會(huì)購(gòu)買電腦決策樹生成原理在訓(xùn)練樣本集合上生成決策樹的基本步驟step1根據(jù)實(shí)際需求以及所處理樣本的特性，選擇合適的屬性集合作為決策樹的候選屬性集。step2在候選屬性集合中選擇最有分類能力的屬性作為當(dāng)前決策節(jié)點(diǎn)的分裂依據(jù)（第一個(gè)決策節(jié)點(diǎn)稱為根節(jié)點(diǎn)），節(jié)點(diǎn)上被選中的候選屬性也稱為測(cè)試屬性。step3根據(jù)當(dāng)前決策節(jié)點(diǎn)測(cè)試屬性取值的不同，將訓(xùn)練屬性集劃分為若干個(gè)子集。針對(duì)劃分的每一個(gè)子集，重復(fù)進(jìn)行上述的step2、step3兩個(gè)步驟，直到最后的子集符合下面的三個(gè)條件之一條件一：子集中的所有樣本都屬于同一類。條件二：子集是遍歷了所有候選屬性得到的。條件三：子集中的所有剩余屬性取值完全相同，已經(jīng)不能夠再根據(jù)這些屬性進(jìn)行子集劃分了。step4確定葉節(jié)點(diǎn)的類別。對(duì)“條件一”所產(chǎn)生的葉子節(jié)點(diǎn)，直接根據(jù)其中的樣本所屬類別進(jìn)行類別標(biāo)識(shí)；對(duì)“條件二”或“條件三”所產(chǎn)生的葉子節(jié)點(diǎn)，選取子集所含樣本的代表性類別屬性進(jìn)行類別標(biāo)識(shí)，一般是把樣本個(gè)數(shù)最多的類別進(jìn)行類別標(biāo)識(shí)。通過上述步驟，對(duì)樣本集建立了可進(jìn)行分類的決策樹。在決策樹中，每一個(gè)從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的分枝都可以得到一條用于判斷樣本類別歸屬的初步規(guī)則，但在得到的初步規(guī)則中，有一些規(guī)則準(zhǔn)確率較低，因此需要對(duì)上述得到的決策樹進(jìn)行“剪枝”。決策樹算法的核心問題是分裂屬性的選取和決策樹的剪枝。ID3/ID4.5/CART算法決策樹學(xué)習(xí)通常包括3個(gè)步驟：特征選擇，決策樹的生成和決策樹的修剪。這些決策樹學(xué)習(xí)的思想主要來源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。本部分有如下約定：X={(xi,yi)|i=1,2,…,n}是給定的樣本數(shù)據(jù)集，D={(xi,yi)|i=1,2,…,N}是樣本訓(xùn)練集，{Yi|i=1,2,…,S}是對(duì)應(yīng)分類的類別，{Aj|j=1,2,…,K}是所有樣本屬性A取值的集合，Di.是所有類別為Yi的訓(xùn)練子集，D.j是所有屬性A值為Aj的訓(xùn)練樣本子集，Dij是所有類別為Yi且屬性A值為Aj的訓(xùn)練樣本子集，|D|是樣本訓(xùn)練集D中包含的樣本個(gè)數(shù)。(一)ID3算法ID3（IterativeDichotomiser3）算法的核心思想就是以信息增益來度量屬性的選擇，選擇信息增益最大的屬性進(jìn)行分裂。該算法采用自頂向下的貪婪搜索遍歷決策空間。(1)信息熵與信息增益在信息增益中，重要性的衡量標(biāo)準(zhǔn)就是看樣本屬性能夠?yàn)榉诸愊到y(tǒng)帶來多少信息，帶來的信息越多，該屬性越重要。在認(rèn)識(shí)信息增益之前，先來看看信息熵的定義。在1948年，香農(nóng)引入了信息熵，將其定義為離散隨機(jī)事件出現(xiàn)的概率，一個(gè)系統(tǒng)越是有序，信息熵就越低，反之一個(gè)系統(tǒng)越是混亂，它的信息熵就越高。所以信息熵可以被認(rèn)為是系統(tǒng)有序化程度的一個(gè)度量。已知訓(xùn)練樣本集D，則D的信息熵定義為：

（6-3）式（6-3）說明一個(gè)變量的變化情況可能越多，那么它攜帶的信息量就越大，當(dāng)這個(gè)H(D)的值越小，說明訓(xùn)練樣本集合D的純度就越高。特征A對(duì)于數(shù)據(jù)樣本集D的條件熵定義為：

（6-4）特征A的信息增益等于數(shù)據(jù)集D的熵減去特征A對(duì)于數(shù)據(jù)集D的條件熵。

（6-5）信息增益是相對(duì)于特征而言的，信息增益越大，特征對(duì)最終的分類結(jié)果影響也就越大，因此應(yīng)該選擇對(duì)最終分類結(jié)果影響最大的那個(gè)特征作為分類特征。例6.9信息增益計(jì)算示例。訓(xùn)練集D為貸款申請(qǐng)樣本數(shù)據(jù)，如表6.4所示。表6.4貸款申請(qǐng)樣本數(shù)據(jù)表序號(hào)年齡工作房子信貸類別

序號(hào)年齡工作房子信貸類別1青年否否一般否9中年否是非常好是2青年否否好否10中年否是非常好是3青年是否好是11老年否是非常好是4青年是是一般是12老年否是好是5青年否否一般否13老年是否好是6中年否否一般否14老年是否非常好是7中年否否好否15老年否否一般否8中年是是好是

根據(jù)公式（6-3）計(jì)算信息熵H(D)以分析貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)。最終分類結(jié)果只有兩類，即放貸（類別為“是”）和不放貸（類別為“否”）。根據(jù)表中的數(shù)據(jù)統(tǒng)計(jì)可知，在15個(gè)數(shù)據(jù)中，9個(gè)數(shù)據(jù)的結(jié)果為放貸，6個(gè)數(shù)據(jù)的結(jié)果為不放貸。所以訓(xùn)練數(shù)據(jù)集D的信息熵H(D)為：

設(shè)A1=“年齡”，一共有三個(gè)類別，分別是：青年、中年和老年。年齡是青年的數(shù)據(jù)一共有5個(gè)，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是十五分之五，也就是三分之一。同理，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是三分之一?，F(xiàn)在我們只看年齡是青年數(shù)據(jù)的最終得到貸款的概率為五分之二，因?yàn)樵谖鍌€(gè)數(shù)據(jù)中，只有兩個(gè)數(shù)據(jù)顯示拿到了最終的貸款，同理，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為五分之三、五分之四。所以計(jì)算年齡的信息增益，過程如下：D1、D2、D3分別是D中A1（年齡）取值為青年、中年和老年的樣本子集，類似地可以計(jì)算出A2=“工作”、A3=“房子”、A4=“信貸”的信息增益?？梢钥闯觯珹3=“房子”的信息增益最大，因此應(yīng)該把A3屬性作為最優(yōu)特征。(一)ID3算法輸入訓(xùn)練樣本集D，屬性集A，閾值ε輸出決策樹T。處理流程：step1若D中所有樣本屬于同一類Ck，則T為單節(jié)點(diǎn)樹，并將類Ck作為該節(jié)點(diǎn)的類標(biāo)記，返回T；step2若A=φ，則T為單節(jié)點(diǎn)樹，并將D中樣本數(shù)最大的類Ck作為該節(jié)點(diǎn)的類標(biāo)記，返回T；step3否則，按式（6-5）計(jì)算A中各特征對(duì)D的信息增益，選擇信息增益最大的特征Ag；step4如果Ag的信息增益小于閾值ε，則置T為單節(jié)點(diǎn)樹，并將D中樣本數(shù)最大的類Ck作為該節(jié)點(diǎn)的類標(biāo)記，返回T；step5否則，對(duì)Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中樣本數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)，由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)成樹T，返回T；step6對(duì)第i個(gè)子節(jié)點(diǎn)，以Di為訓(xùn)練集，以A-{Ag}為屬性集，遞歸地調(diào)用step1~step5，得到子樹Ti，返回Ti。例6.10對(duì)于表6.4的訓(xùn)練數(shù)據(jù)集，利用ID3算法建立決策樹。利用例6.9的結(jié)果，由于特征A3（房子）的信息增益值最大，所以選擇屬性A3作為根節(jié)點(diǎn)的特征。它將訓(xùn)練數(shù)據(jù)集D劃為兩個(gè)子集D1（A3取值為“是”）和D2（A3取值為“否”）。由于D1只有同一類的樣本點(diǎn)，所以它稱為一個(gè)葉節(jié)點(diǎn)，節(jié)點(diǎn)的類別標(biāo)記為“是”。對(duì)D2則需從特征A1（年齡），A2（工作）和A4（信貸）中選擇新的特征。計(jì)算各個(gè)特征的信息增益：Gain(D2,A1)=H(D2)-H(D2/A1)=0.918-0.667=0.251Gain(D2,A2)=H(D2)-H(D2/A2)=0.918Gain(D2,A4)=H(D2)-H(D2/A4)=0.474選擇信息增益最大的特征A2（工作）作為節(jié)點(diǎn)的特征。由于A2有兩個(gè)可能的取值，從這一節(jié)點(diǎn)引出兩個(gè)子節(jié)點(diǎn)：一個(gè)對(duì)應(yīng)“是”（有工作）的子節(jié)點(diǎn)，包含了3個(gè)樣本，它們屬于同一類，所以這是一個(gè)葉節(jié)點(diǎn)，類標(biāo)記為“是”；另一個(gè)是對(duì)應(yīng)“否”（無工作）的子節(jié)點(diǎn)，包含6個(gè)樣本，它們也屬于同一類，所以這也是一個(gè)葉節(jié)點(diǎn)，類標(biāo)記為“否”。生成的決策樹如圖6.7所示。

圖6.7例6.10生成的決策樹房子是是工作否有無有無(二)C4.5算法算法原理：在ID3算法中，樹節(jié)點(diǎn)的選擇是通過計(jì)算屬性的信息增益，繼而比較信息增益最大的則被選為分裂節(jié)點(diǎn)。而C4.5算法中引進(jìn)信息增益率來解決這個(gè)問題，這里信息增益率等于信息增益與分割信息量的比值。特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益率G_R(D,A)定義為其信息增益Gain(D,A)與訓(xùn)練數(shù)據(jù)集D關(guān)于特征A值的熵HA(D)之比：（6-6）其中，k是特征A取值的個(gè)數(shù)。在節(jié)點(diǎn)分裂屬性的時(shí)候，根據(jù)這個(gè)信息增益率來判斷，選取屬性信息增益率最大的屬性作為分裂屬性，這就可以解決算法偏向于屬性取多值的問題。但是每個(gè)屬性的信息熵相當(dāng)于一種條件熵。它表示的是在某種屬性的條件下，各種類別出現(xiàn)的不確定性之和。(二)C4.5算法算法實(shí)現(xiàn)：假設(shè)D為訓(xùn)練數(shù)據(jù)樣本集，D的候選屬性集用A表示，則C4.5算法C4.5formtree(D,D.A)描述如下：輸入：訓(xùn)練樣本集D，候選屬性的集合A輸出：一棵決策樹處理流程：step1創(chuàng)建根節(jié)點(diǎn)N；step2IFD都屬于同一類Ci，則返回N為葉節(jié)點(diǎn)，標(biāo)記為類Ci；step3IFA為空或D中所剩余樣本數(shù)少于某個(gè)給定值則返回N為葉節(jié)點(diǎn)，標(biāo)記N為D中出現(xiàn)最多的類；step4FORA中的每一個(gè)屬性Ai計(jì)算信息增益率G_R(H,Ai)；step5N的測(cè)試屬性test.A=<屬性列表>具有最高信息增益率的屬性；step6IF測(cè)試屬性為連續(xù)型則找到該屬性的分割閾值；step7FOR每一個(gè)由節(jié)點(diǎn)N生成的新葉子節(jié)點(diǎn)IF該葉子節(jié)點(diǎn)對(duì)應(yīng)的樣本子集D’為空則分裂此葉子節(jié)點(diǎn)生成新葉節(jié)點(diǎn)，將其標(biāo)記為D中出現(xiàn)最多的類ELSE在該葉子節(jié)點(diǎn)上執(zhí)行C4.5formtree(D’,D’.<屬性列表>)，繼續(xù)對(duì)它分裂；step8計(jì)算每個(gè)節(jié)點(diǎn)的分類錯(cuò)誤，進(jìn)行剪枝。(二)C4.5算法C4.5算法剪枝：①預(yù)剪枝法。此方法通過提前停止樹的構(gòu)造而實(shí)現(xiàn)對(duì)樹枝進(jìn)行修剪。一旦停止，節(jié)點(diǎn)成為樹葉。葉子節(jié)點(diǎn)取子集中頻率最大的類作為子集的標(biāo)識(shí)，或者僅僅存儲(chǔ)這些數(shù)據(jù)樣本的概率分布函數(shù)。②后剪枝方法。它是在樹構(gòu)建之后才進(jìn)行剪枝。通過對(duì)分枝節(jié)點(diǎn)的刪除，剪去樹節(jié)點(diǎn)，比較常用的是代價(jià)復(fù)雜性剪枝算法。在該算法中，最底層的沒有被剪枝的節(jié)點(diǎn)作為樹葉，并把它標(biāo)記為先前分枝中最頻繁的類。針對(duì)樹中所有的非樹葉節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)上的子樹被剪枝后可能出現(xiàn)的期望錯(cuò)誤率，然后，利用每個(gè)分枝的錯(cuò)誤率，結(jié)合對(duì)每個(gè)分枝觀察的權(quán)重評(píng)估，計(jì)算不對(duì)此節(jié)點(diǎn)剪枝的期望錯(cuò)誤率。假如剪去此節(jié)點(diǎn)會(huì)導(dǎo)致較高的期望錯(cuò)誤率，那就保留該子樹；否則就剪去此子樹。產(chǎn)生一組逐漸被剪枝的樹后，使用一個(gè)獨(dú)特的測(cè)試集評(píng)估每棵樹的準(zhǔn)確率，即可得到具有最小期望錯(cuò)誤率的決策樹。大部分情況下，這兩種剪枝方法是交叉使用的，形成組合式方法，但后剪枝所需要的計(jì)算量比預(yù)剪枝大，可產(chǎn)生的樹通常更可靠。C4.5算法使用悲觀剪枝方法，它類似于代價(jià)復(fù)雜度方法，同樣使用錯(cuò)誤率評(píng)估，對(duì)子樹剪枝作出決定。然而，悲觀剪枝不需要使用剪枝集，而是使用訓(xùn)練集評(píng)估錯(cuò)誤率。基于訓(xùn)練集評(píng)估準(zhǔn)確率或者錯(cuò)誤率是過于樂觀的，所以具有較大的偏倚。也可以根據(jù)樹編碼所需的二進(jìn)位位數(shù)，而不是根據(jù)估計(jì)的錯(cuò)誤率，對(duì)樹進(jìn)行剪枝?！白罴选奔糁涫亲钚』幋a二進(jìn)位位數(shù)的樹。這種方法采用最小長(zhǎng)度原則，其基本思想是：首選最簡(jiǎn)單的解。C4.5算法的優(yōu)缺點(diǎn)C4.5優(yōu)點(diǎn)C4.5算法產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：①用信息增益率來選擇分裂屬性，克服了用信息增益選擇屬性時(shí)偏向選擇多屬性的不足。②在樹構(gòu)造過程中進(jìn)行剪枝。③能夠完成對(duì)連續(xù)屬性的離散化處理。④能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5缺點(diǎn)：在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。(三)CART算法分類原理：CART分類時(shí)，使用基尼系數(shù)（Gini）來選擇最好的數(shù)據(jù)分割特征，Gini描述的是純度，與信息熵的含義相似。CART中每一次迭代都會(huì)降低Gini系數(shù)。CART生成分類樹是采用基尼系數(shù)來選擇劃分屬性及劃分點(diǎn)。對(duì)于給定的樣本集合D，其基尼系數(shù)為：

其中，Ck是數(shù)據(jù)樣本集D分類的第k類，K是類別總數(shù)。如果樣本集合D根據(jù)特征A是否取某一可能值A(chǔ)i被分割成D1和D2兩部分，則在特征A的條件下，集合D的基尼系數(shù)定義為：（6-7）CART是一棵二叉樹，采用二元切分法，即每次把數(shù)據(jù)切成兩份，分別進(jìn)入左子樹、右子樹。(三)CART分類算法輸入訓(xùn)練數(shù)據(jù)集D，閾值（停止條件）輸出CART決策樹構(gòu)建二叉決策樹：step1設(shè)節(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D，計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的基尼系數(shù)。此時(shí)，對(duì)每一個(gè)特征A，對(duì)其可能取的每個(gè)值A(chǔ)i，根據(jù)樣本點(diǎn)對(duì)A=Ai的測(cè)試為“是”或“否”將D分割成D1和D2兩部分，利用式（6-8）計(jì)算A=Ai時(shí)的基尼系數(shù)。step2在所有可能的特征A以及它們所有可能的切分點(diǎn)Ai中，選擇基尼系數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依據(jù)最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)節(jié)點(diǎn)生成兩個(gè)子節(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依據(jù)特征分配到兩個(gè)子節(jié)點(diǎn)中去。step3對(duì)兩個(gè)子節(jié)點(diǎn)遞歸地調(diào)用step1、step2，直至滿足停止條件。step4生成CART決策樹。算法停止計(jì)算的條件是節(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，或樣本集的基尼系數(shù)小于預(yù)定閾值（樣本基本屬于同一類），或者沒有更多特征。例6.11對(duì)于表6.4的訓(xùn)練數(shù)據(jù)集，應(yīng)用CART算法生成決策樹。

表6.4貸款申請(qǐng)樣本數(shù)據(jù)表序號(hào)年齡工作房子信貸類別

序號(hào)年齡工作房子信貸類別1青年否否一般否9中年否是非常好是2青年否否好否10中年否是非常好是3青年是否好是11老年否是非常好是4青年是是一般是12老年否是好是5青年否否一般否13老年是否好是6中年否否一般否14老年是否非常好是7中年否否好否15老年否否一般否8中年是是好是

求特征A1的基尼系數(shù)：同樣可得：

，Gini(D,A1=0)分為是青年或不是青年；Gini(D,A1=1)分為是中年或不是中年；Gini(D,A1=2)分為是老年或不是老年。由于Gini(D,A1=0)和Gini(D,A1=2)相等，且最小，所以A1=0和A1=2都可以選作A1的最優(yōu)切分點(diǎn)。求特征A2和A3的基尼系數(shù)：Gini(D,A2=0)=0.32，Gini(D,A3=0)=0.27由于A2和A3只有一個(gè)切分點(diǎn)，所以它們就是最優(yōu)切分點(diǎn)。求特征A4的基尼系數(shù)：Gini(D,A4=2)=0.36，Gini(D,A4=1)=0.47，Gini(D,A4=0)=0.32因?yàn)镚ini(D,A4=0)=0.32最小，所以A4=0可以選作A4的最優(yōu)切分點(diǎn)。在A1、A2、A3、A4幾個(gè)特征中，Gini(D,A3=0)=0.27最小，所以選擇特征A3為最優(yōu)特征，A3=0為其最優(yōu)切分點(diǎn)。于是根節(jié)點(diǎn)生成兩個(gè)子節(jié)點(diǎn)，一個(gè)是葉節(jié)點(diǎn)。對(duì)于另一個(gè)節(jié)點(diǎn)繼續(xù)使用以上方法在A1、A2、A4中選擇最優(yōu)特征及其最優(yōu)切分點(diǎn)，結(jié)果是A2=0。依此計(jì)算得知，所得的節(jié)點(diǎn)都是葉節(jié)點(diǎn)。首先計(jì)算各特征的基尼系數(shù)，選擇最優(yōu)特征以及最優(yōu)切分點(diǎn)。仍然采用例6.9的記號(hào)，分別以A1、A2、A3、A4表示年齡、工作、房子和信貸4個(gè)特征，并以0、1、2表示年齡取值為青年、中年、老年，以0、1分別表示有工作和有房子的值為是或否，以0、1、2表示信貸情況的值為一般、好、非常好。CART算法的優(yōu)缺點(diǎn)CART優(yōu)點(diǎn)：①生成可以理解的規(guī)則。②計(jì)算量相對(duì)來說較小。③可以處理值為連續(xù)型和離散型字段。④決策樹可以清晰的顯示哪些字段比較重要。CART缺點(diǎn)：①對(duì)連續(xù)型的字段比較難預(yù)測(cè)。②對(duì)有時(shí)間順序的數(shù)據(jù)，預(yù)處理工作比較復(fù)雜。③當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快。ID3、C4.5、CART比較

03決策樹產(chǎn)生過程

04應(yīng)用C4.5是通過剪枝來修正樹的準(zhǔn)確性，而CART是直接利用全部數(shù)據(jù)與所有樹的結(jié)構(gòu)進(jìn)行對(duì)比。ID3和C4.5只能做分類，CART不僅可以做分類還可以做回歸。ID3和C4.5節(jié)點(diǎn)上可以產(chǎn)出多叉（低、中、高），而CART節(jié)點(diǎn)上永遠(yuǎn)是二叉（低、非低）。CART、ID3和C4.5算法過程都包含特征選擇、樹的生成、剪枝等步驟。

01

最優(yōu)特征選擇

02

樣本數(shù)據(jù)CART分類樹通過基尼系數(shù)選擇最優(yōu)特征，同時(shí)決定該特征的最優(yōu)二值切分點(diǎn)，而ID3和C4.5直接選擇最優(yōu)特征，不用劃分。ID3是用屬性A對(duì)數(shù)據(jù)樣本集D的信息增益大的屬性來進(jìn)行劃分，C4.5選擇增益率最高的屬性來作為劃分樣本的依據(jù)，而CART在候選屬性中選擇基尼系數(shù)最小的屬性作為最優(yōu)劃分屬性。ID3只能對(duì)離散變量進(jìn)行處理，C4.5和CART可以處理連續(xù)和離散兩種變量。ID3對(duì)缺失值敏感，而C4.5和CART對(duì)缺失值可以進(jìn)行多種方式的處理。如果只從樣本量考慮，小樣本建議使用C4.5、大樣本建議使用CART。C4.5處理過程中需對(duì)數(shù)據(jù)集進(jìn)行多次排序，處理成本耗時(shí)較高，而CART本身是一種大樣本的統(tǒng)計(jì)方法，小樣本處理下泛化誤差較大。例6.12對(duì)例6.9中的數(shù)據(jù)集，用ID3算法建立決策樹，并進(jìn)行預(yù)測(cè)。

表6.4貸款申請(qǐng)樣本數(shù)據(jù)表序號(hào)年齡工作房子信貸類別

序號(hào)年齡工作房子信貸類別1青年否否一般否9中年否是非常好是2青年否否好否10中年否是非常好是3青年是否好是11老年否是非常好是4青年是是一般是12老年否是好是5青年否否一般否13老年是否好是6中年否否一般否14老年是否非常好是7中年否否好否15老年否否一般否8中年是是好是

先對(duì)表6.4的數(shù)據(jù)集進(jìn)行屬性標(biāo)注：年齡：0代表青年，1代表中年，2代表老年；有工作：0代表否，1代表是；有自己的房子：0代表否，1代表是；信貸情況：0代表一般，1代表好，2代表非常好；類別(是否給予貸款)：no代表否，yes代表是。例6.13C4.5建立決策樹應(yīng)用示例。訓(xùn)練集與測(cè)試集如表6.5和表6.6所示。編程序給出決策樹的圖形表示。

表

表6.5訓(xùn)練集數(shù)據(jù)表表6.6測(cè)試集數(shù)據(jù)表outlooktemperaturehumiditywindyresultsunnyhothighfalseNsunnyhothightrueNovercasthothighfalseYrainmildhighfalseYraincoolnormalfalseYraincoolnormaltrueNovercastcoolnormaltrueYoutlooktemperaturehumiditywindysunnymildhighfalsesunnycoolnormalfalserainmildnormalfalsesunnymildnormaltrueovercastmildhightrueovercasthotnormalfalserainmildhightrue5貝葉斯分類模型6.5NaiveBayes，NB貝葉斯分類述概樸素貝葉斯分類器素貝葉斯分類器原理是對(duì)于給出的待分類樣本，求解在此樣本出現(xiàn)的條件下各個(gè)類別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此待分類樣本屬于哪個(gè)類別。它在求解過程中假設(shè)各分類樣本的特征是相互獨(dú)立的。例如，短信文本一般都不超過70個(gè)漢字，如“首付至少10萬，最多住30年，翡翠公館，長(zhǎng)江路CBD精裝小戶，準(zhǔn)現(xiàn)房發(fā)售，投資自住皆宜會(huì)員優(yōu)惠中！電，通過提取特征詞可以判定為售樓類廣告。盡管這些特征詞相互依賴或者有些特征詞由其它特征詞確定，然而樸素貝葉斯分類器認(rèn)為這些特征詞在判定該短信為售樓類廣告的概率分布上是獨(dú)立的。貝葉斯分類器分為樸素貝葉斯分類器和貝葉斯網(wǎng)絡(luò)分類器兩種。貝葉斯網(wǎng)絡(luò)分類器貝葉斯網(wǎng)絡(luò)分類器原理是由圖論和概率論結(jié)合而成的描述多元統(tǒng)計(jì)關(guān)系的模型，它借助有向無環(huán)圖來刻畫屬性之間的依賴關(guān)系，并使用條件概率表來描述屬性的聯(lián)合概率分布。貝葉斯網(wǎng)絡(luò)分類器為多個(gè)變量之間復(fù)雜依賴關(guān)系的表示提供了統(tǒng)一的框架，具有緊湊有效、簡(jiǎn)潔直觀的特點(diǎn)。利用貝葉斯網(wǎng)絡(luò)分類需要考慮樣本屬性之間的依賴程度，其計(jì)算復(fù)雜度比樸素貝葉斯高得多，更能反映真實(shí)樣本的情況。貝葉斯網(wǎng)絡(luò)分類器實(shí)現(xiàn)十分復(fù)雜。樸素貝葉斯分類器使用樸素貝葉斯分類器需要一個(gè)前提：樣本的屬性之間必須是相互獨(dú)立的。通過使用樸素貝葉斯分類器，可以來預(yù)測(cè)屬性與類別存在關(guān)系的可能性，求得樣本屬于某一類別的概率，根據(jù)概率的大小將樣本分類到概率最大的類別中。樸素貝葉斯分類器一個(gè)很經(jīng)典的應(yīng)用就是用來進(jìn)行垃圾郵件過濾。每一封郵件都包含了一系列特征詞，這些特征詞就構(gòu)成特征向量。我們只需要計(jì)算在該特征向量出現(xiàn)的前提下此郵件為垃圾郵件的概率就可以進(jìn)行判別了。樸素貝葉斯分類的算法原理依賴于概率論中的貝葉斯定理。樸素貝葉斯分類原理假設(shè)A和B為兩個(gè)不相互獨(dú)立的事件，事件B發(fā)生的條件下事件A發(fā)生的概率（也稱為后驗(yàn)概率）為：（6-9）稱為貝葉斯定理。其中，P(A)表示事件A發(fā)生的概率（也稱為先驗(yàn)概率），P(B)表示事件B發(fā)生的概率，P(AB)表示事件A、B同時(shí)發(fā)生的概率，P(B|A)表示在A發(fā)生的條件下隨機(jī)事件出現(xiàn)B情況的概率。假設(shè)B有多個(gè)需要考慮的因素：B=(b1,b2,…,bn)，“樸素”的意義就在于假設(shè)這些因素是相互獨(dú)立的，即有：

（6-10）貝葉斯定理輸入樣本X={x1,x2,…,xn}，xi（i=1,2,…,n）是X的屬性，類別集合C={c1,c2,…,cs}輸出X屬于的類別ckstep1計(jì)算X為各個(gè)類別的概率：P(c1|X)，P(c2|X)，…，P(cs|X)。step2如果P(ck|X)=max{P(c1|X)，P(c2|X)，…，P(cs|X)}，則X的類別為ck。樸素貝葉斯分類算法原始的樸素貝葉斯分類只能處理離散數(shù)據(jù)。在估計(jì)條件概率P(xi|c)時(shí)，如果xi為離散值，則只需要計(jì)算每個(gè)值占所有樣本的數(shù)量比例就可以了。（6-11）其中，|Dc|表示訓(xùn)練集D中第c類樣本組成集合的樣本數(shù)量。表示的是Dc中在第i個(gè)值上取值為xi樣本組成集合的樣本數(shù)量。離散值的概率高斯樸素貝葉斯分類在估計(jì)條件概率P(xi|c)時(shí)，如果xi為連續(xù)值，可以使用高斯樸素貝葉斯（GaussianNa?veBayes）分類模型，它是基于一種經(jīng)典的假設(shè)：與每個(gè)類相關(guān)的連續(xù)變量的分布是屬于高斯分布的。假設(shè)，其中和分別是第c類樣本在第i個(gè)值的均值和方差，則有：（6-12）多項(xiàng)式樸素貝葉斯分類多項(xiàng)式樸素貝葉斯（MultinomialNa?veBayes）經(jīng)常被用于離散特征的多分類問題，比起原始的樸素貝葉斯分類效果有了較大的提升。其公式如下：

（6-13）其中，a>0表示平滑系數(shù)，其意義是防止零概率的出現(xiàn)，當(dāng)a=1時(shí)稱為拉普拉斯平滑，當(dāng)a<0時(shí)稱為L(zhǎng)idstone平滑。例6.14根據(jù)一個(gè)西瓜的特征來判斷它是否是個(gè)好瓜。數(shù)據(jù)集如表6.7所示。

表6.7西瓜數(shù)據(jù)表編號(hào)色澤瓜蒂敲聲紋理臍部觸感密度含糖率好瓜1青綠蜷縮濁響清晰凹陷硬滑0.6970.460是2烏黑蜷縮沉悶清晰凹陷硬滑0.7740.376是3烏黑蜷縮濁響清晰凹陷硬滑0.6340.264是4青綠蜷縮沉悶清晰凹陷硬滑0.6080.318是5淺白蜷縮濁響清晰凹陷硬滑0.5560.215是6青綠稍蜷濁響清晰稍凹軟粘0.4030.237是7烏黑稍蜷濁響稍糊稍凹軟粘0.4810.149是8烏黑稍蜷濁響清晰稍凹硬滑0.4370.211是9烏黑稍蜷沉悶稍糊稍凹硬滑0.6660.091否10青綠硬挺清脆清晰平坦軟粘0.2430.267否11淺白硬挺清脆模糊平坦硬滑0.2450.057否12淺白蜷縮濁響模糊平坦軟粘0.3430.099否13青綠稍蜷濁響稍糊凹陷硬滑0.6390.161否14淺白稍蜷沉悶稍糊凹陷硬滑0.6570.198否15烏黑稍蜷濁響清晰稍凹軟粘0.3600.370否16淺白蜷縮濁響模糊平坦硬滑0.5930.042否17青綠蜷縮沉悶稍糊稍凹硬滑0.7190.103否對(duì)于連續(xù)值屬性密度、含糖率：計(jì)算測(cè)試瓜xtest={色澤=青綠，瓜蒂=蜷縮，敲聲=濁響，紋理=清晰，臍部=凹陷，觸感=硬滑，密度=0.697，含糖率=0.460}分別屬于好瓜和壞瓜的概率。P(好瓜=”是”)×P青綠|是×P蜷縮|是×P濁響|是×P清晰|是×P凹陷|是×P硬滑|是×P密度:0.697|是×P含糖:0.460|是≈0.0028P(好瓜=”否”)×P青綠|否×P蜷縮|否×P濁響|否×P清晰|否×P凹陷|否×P硬滑|否×P密度:0.697|否×P含糖:0.460|否≈6.80×10-5很明顯，測(cè)試樣例西瓜xtest是好瓜的概率0.028遠(yuǎn)大于xtest是壞瓜的概率6.80×10?5，于是分類器判斷xtest為好瓜。例6.14根據(jù)一個(gè)西瓜的特征來判斷它是否是個(gè)好瓜。數(shù)據(jù)集如表6.7所示。

表6.7西瓜數(shù)據(jù)表編號(hào)色澤瓜蒂敲聲紋理臍部觸感密度含糖率好瓜1青綠蜷縮濁響清晰凹陷硬滑0.6970.460是2烏黑蜷縮沉悶清晰凹陷硬滑0.7740.376是3烏黑蜷縮濁響清晰凹陷硬滑0.6340.264是4青綠蜷縮沉悶清晰凹陷硬滑0.6080.318是5淺白蜷縮濁響清晰凹陷硬滑0.5560.215是6青綠稍蜷濁響清晰稍凹軟粘0.4030.237是7烏黑稍蜷濁響稍糊稍凹軟粘0.4810.149是8烏黑稍蜷濁響清晰稍凹硬滑0.4370.211是9烏黑稍蜷沉悶稍糊稍凹硬滑0.6660.091否10青綠硬挺清脆清晰平坦軟粘0.2430.267否11淺白硬挺清脆模糊平坦硬滑0.2450.057否12淺白蜷縮濁響模糊平坦軟粘0.3430.099否13青綠稍蜷濁響稍糊凹陷硬滑0.6390.161否14淺白稍蜷沉悶稍糊凹陷硬滑0.6570.198否15烏黑稍蜷濁響清晰稍凹軟粘0.3600.370否16淺白蜷縮濁響模糊平坦硬滑0.5930.042否17青綠蜷縮沉悶稍糊稍凹硬滑0.7190.103否利用樸素貝葉斯算法訓(xùn)練出一個(gè){“好瓜”、“壞瓜”}的分類器，測(cè)試樣例西瓜xtest={色澤=青綠，瓜蒂=蜷縮，敲聲=濁響，紋理=清晰，臍部=凹陷，觸感=硬滑，密度=0.697，含糖率=0.460}的是否為好瓜。估計(jì)先驗(yàn)概率

：

，其次，計(jì)算每個(gè)屬性值的條件概率P(xi|c)，對(duì)于離散屬性色澤、瓜蒂、敲聲、紋理、臍部、觸感：樸素貝葉斯模型優(yōu)缺點(diǎn)樸素貝葉斯分類的主要優(yōu)點(diǎn)：(1)樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有穩(wěn)定的分類效率。(2)對(duì)小規(guī)模的數(shù)據(jù)集表現(xiàn)很好，可以處理多分類任務(wù)。適合增量式訓(xùn)練，尤其是數(shù)據(jù)量超出內(nèi)存時(shí)，可以一批批的去增量訓(xùn)練。(3)對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單，常用于文本分類。樸素貝葉斯的主要缺點(diǎn)：(1)理論上，樸素貝葉斯模型與其它分類方法相比具有最小的誤差率。但是實(shí)際上并非總是如此，這是因?yàn)闃闼刎惾~斯模型假設(shè)屬性之間相互獨(dú)立，這個(gè)假設(shè)在實(shí)際應(yīng)用中往往是不成立的，在屬性個(gè)數(shù)比較多或者屬性之間相關(guān)性較大時(shí)，分類效果不好。而在屬性相關(guān)性較小時(shí)，樸素貝葉斯性能最為良好。對(duì)于這一點(diǎn)，有半樸素貝葉斯之類的算法是通過考慮部分關(guān)聯(lián)性適度改進(jìn)的。(2)需要知道先驗(yàn)概率，且先驗(yàn)概率很多時(shí)候取決于假設(shè)，假設(shè)的模型可以有很多種，因此在某些時(shí)候會(huì)由于假設(shè)的先驗(yàn)?zāi)Ｐ驮驅(qū)е骂A(yù)測(cè)效果不佳。(3)由于我們是通過先驗(yàn)概率來決定后驗(yàn)概率從而決定分類，所以分類決策存在一定的錯(cuò)誤率。(4)對(duì)輸入數(shù)據(jù)的表達(dá)形式很敏感。例6.16利用scikit-learn中樸素貝葉斯的分類算法。(1)高斯分布樸素貝葉斯GaussianNB()分類示例。fromsklearn.datasetsimportload_irisfromsklearn.naive_bayesimportGaussianNBiris=load_iris()clf=GaussianNB()#設(shè)置高斯貝葉斯分類器clf.fit(iris.data,iris.target)#訓(xùn)練分類器y_pred=clf.predict(iris.data)#預(yù)測(cè)print("Numberofmislabeledpointsoutof%dpoints:%d"%(iris.data.shape[0],(iris.target!=y_pred).sum()))(2)先驗(yàn)為多項(xiàng)式分布的樸素貝葉斯分類MultinomialNB()示例。fromsklearn.datasetsimportload_irisfromsklearn.naive_bayesimportMultinomialNBiris=load_iris()gnb=MultinomialNB()#設(shè)置多項(xiàng)式貝葉斯分類器gnb.fit(iris.data,iris.target)y_pred=gnb.predict(iris.data)print('Numberofmislabeledpointsoutofatotal%dpoints:%d'%(iris.data.shape[0],(iris.target!=y_pred).sum()))6支持向量機(jī)6.6SupportVectorMachines，SVMSVM的基本原理SVM是基于超平面的一個(gè)二分類模型，通過最大化間隔邊界到超平面的距離實(shí)現(xiàn)數(shù)據(jù)的分類。二分類模型在二維空間里就是線性分類器，如圖6.10所示。圖6.10支持向量機(jī)分類示意圖圖6.10中用一條直線把兩個(gè)類別分開。如果存在某一線性函數(shù)能把數(shù)據(jù)樣本集分成兩個(gè)類別，則稱為線性可分。如果在三維空間里，這條直線就變成一個(gè)平面，即超平面。支持向量機(jī)方法試圖在向量空間中尋找一個(gè)最優(yōu)分類平面，該平面切分兩類數(shù)據(jù)并且使其分開的間隔最大。在進(jìn)行樣本分類時(shí)，樣本由一個(gè)標(biāo)記（標(biāo)記樣本的類別）和一個(gè)向量（即樣本形式化向量）組成。形式如下：Di=(xi,yi)（6-14）在二元線性分類中，向量用xi表示，類別標(biāo)記用yi表示。其中yi只有兩個(gè)值+1和-1（表示是否屬于該類別），這樣就可以定義某個(gè)樣本距離最優(yōu)分類平面的間隔。δi=yi(txi+b)（6-15）

式中，t是分類權(quán)重向量，b是分類閾值。SVM的基本原理樣本集距離最優(yōu)分類平面最近點(diǎn)的距離就是樣本集到最優(yōu)分類平面的距離。如圖6.11所示。圖6.11最優(yōu)分類平面示意圖空心點(diǎn)和實(shí)心點(diǎn)分別表示不同的類別，H為分割超平面，H1和H2分別表示各類中離分割超平面最近且平行的平面。H1和H2上的點(diǎn)被稱作支持向量，H1和H2之間的間距被稱為分類間隔。最優(yōu)分割超平面就是要求在正確分開不同類別的前提下，分類間隔最大。

H1HH2SVM分類的基本方法SVM分類模型可概括為：線性可分支持向量機(jī)、線性不可分支持向量機(jī)和非線性支持向量機(jī)，其中線性可分支持向量機(jī)模型分類的直觀表示如圖6.11所示，其它兩種模型分類的直觀表示如圖6.12、圖6.13所示。

圖6.11最優(yōu)分類平面示意圖圖6.13非線性支持向量機(jī)

H1HH2

線性可分支持向量機(jī)根據(jù)以上討論，構(gòu)建最優(yōu)分類面進(jìn)行分類的問題，可以轉(zhuǎn)化為二次規(guī)劃問題，但是直接求解較繁瑣，常用的方法是將其轉(zhuǎn)化為對(duì)偶問題優(yōu)化求解。所用優(yōu)化方法是拉格朗日乘子法，而且與KKT條件（KarushKuhnTuckerConditions）有關(guān)，本部分不列出公式推導(dǎo)過程。直接應(yīng)用其拉格朗日目標(biāo)函數(shù)，如公式（6-16）所示。（6-16）αi≥0是Lagrange系數(shù)。下面求Lagrange函數(shù)最小值：根據(jù)多元微積分求極值的方法，先分別求b、t和αi的偏微分，之后再令偏微分等于0，有：;（6-17）結(jié)合上述公式，即求出原問題的對(duì)偶問題，如式（6-18）所示。（6-18）

線性可分支持向量機(jī)設(shè)最優(yōu)解為

，可以得到如下公式：