Python數(shù)據(jù)挖掘算法與應用 課件 第6、7章 分類模型、聚類分析

第6章

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

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

概述6.1

支持向量機6.6

分類模型的評估與選擇6.7學習目標1概述summarize6.1基本概念

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

下面介紹三種常見的做法。1.留出法留出法（Hold-out）是直接將數(shù)據(jù)集劃分成兩個互斥的集合，其中一個集合作為訓練集，留下的集合作為測試集。常見做法將大約2/3~4/5的樣本作為訓練集，剩下的作為測試集。以二分類任務為例，假設數(shù)據(jù)集包含1000個樣本，我們采取7:3分樣，將訓練集劃分為包含700個樣本，測試集包含300個樣本。Python通過調用train_test_split()函數(shù)按比例劃分訓練集和測試集，該函數(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留出法生成訓練集和測試集示例。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.交叉驗證法交叉驗證法（CrossValidation）將源數(shù)據(jù)集劃分為大小相似的若干互斥子集，每個子集都盡可能地保持數(shù)據(jù)分布的一致性。然后，將每個子集數(shù)據(jù)分別做一次測試集，其余的K-1組子集數(shù)據(jù)作為訓練集，這樣會得到K個模型，用這K個模型分類準確率的平均數(shù)作為此交叉驗證法的性能指標。交叉驗證法評估結果的穩(wěn)定性和保真性在很大程度上取決于K的取值，最常用的取值是10，有時也取5或20等。通過調用KFold()函數(shù)按交叉驗證法劃分訓練集和測試集，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交叉驗證法生成訓練集和測試集示例。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）適用于樣本量較小，并且難以劃分時。自助法產(chǎn)生的樣本改變了數(shù)據(jù)的分布，會引入估計偏差。給定包含n個樣本的數(shù)據(jù)集D，我們對它進行采樣產(chǎn)生數(shù)據(jù)集D’：每次隨機從D中挑選一個樣本，將其復制到D’中，然后再將其樣本放回原始數(shù)據(jù)集D中，使得該樣本在下次采樣的時候也可能被采集到；這個過程重復執(zhí)行m次，就得到了包含m個樣本的數(shù)據(jù)集D’。簡言之，就是從數(shù)據(jù)集D中，有放回隨機采樣m次，組成一個新樣本集D’。用采樣所得的D’作為訓練集，D-D’作為樣本的測試集。由此可以看出，有一部分樣本沒有出現(xiàn)在D’中，會有一部分樣本重復出現(xiàn)。一個樣本在m次采樣過程中始終沒有被采集到的概率是

。當樣本量m=10時，沒有被采集到的概率p=0.3487；當樣本量趨于無窮時，

。所以，采用自助法采樣時，大約會有35%的數(shù)據(jù)沒有出現(xiàn)在D’中。例6.3自助法生成訓練集和測試集示例。importnumpyasnpX=[1,4,3,23,4,6,7,8,9,45,67,89,34,54,76,98,43,52]#設置一個數(shù)據(jù)集bootstrapping=[]#通過產(chǎn)生的隨機數(shù)獲得采集樣本的序號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('生成的訓練集：\n',D_1)D=[itemforiteminXifitemnotinset(D_1)]print('生成的測試集：\n',D)在前兩種方法中都保留部分樣本用于測試，因此實際評估模型使用的訓練集總是比期望評估模型使用的訓練集小，這樣會引入一些因訓練樣本規(guī)模不同而導致的估計偏差。分類流程分類訓練的結果是產(chǎn)生一個分類器或分類模型，進而根據(jù)構建的模型對測試數(shù)據(jù)進行預測，得到相應的類標簽。類標簽的數(shù)據(jù)種類可以有二分類或多分類。學習利用數(shù)據(jù)進行模型參數(shù)的調節(jié)過程稱為訓練或學習是否

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

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

01KNN算法實現(xiàn)sortCount=sorted(count.items(),reverse=True)#對類別出現(xiàn)的頻數(shù)從高到低進行排序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=['重點院校','本科院校','專科院校','本科院校','?？圃盒?,'本科院校','重點院校','?？圃盒?,'?？圃盒?,'本科院校','重點院校']testData=[97,96,92]X=knn(trainData,testData,labels,3)print(X)Python實現(xiàn)KNN分類算法02KNeighborsClassifier()在scikit-learn中，與KNN法這一大類相關的類庫都在sklearn.neighbors包之中。當使用函數(shù)KNeighborsClassifier()進行分類時，需要導入相關的類庫，語句為：fromsklearnimportneighbors。常用形式為：KNeighborsClassifier(n_neighbors=5,weights=’uniform’)參數(shù)說明：(1)n_neighbors：KNN中的k值，默認為5。(2)weights：用于標識最近鄰樣本的權重，取值為：’uniform’和’distance’。默認’uniform’，表示所有最近鄰樣本權重都一樣；當取值為’distance’時，表示自定義權重。如果樣本分布是比較均勻的，取值’uniform’效果較好；如果樣本分布比較亂，規(guī)律不好尋找時，取值’distance’效果比較好。例6.6用KNN對鳶尾花數(shù)據(jù)集進行分類。importmatplotlib.pyplotaspltimportnumpyasnpfrommatplotlib.colorsimportListedColormapfromsklearnimportneighbors,datasetsn_neighbors=11#取k=11iris=datasets.load_iris()#導入鳶尾花數(shù)據(jù)集x=iris.data[:,:2]#取前兩個feature,方便在二維平面上畫圖y=iris.targeth=.02#網(wǎ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)建了一個KNN分類器的實例，并擬合數(shù)據(jù)clf.fit(x,y)#繪制決策邊界。為此，將為每個數(shù)據(jù)對分配一個顏色來繪制網(wǎng)格中的點[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()])#將結果放入一個彩色圖中Z=Z.reshape(xx.shape)plt.figure()plt.pcolormesh(xx,yy,Z,cmap=cmap_light)#繪制訓練點

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()程序運行結果圖之一如圖6.2所示。圖6.2例6.6程序運行結果K值的確定KNN算法中只有一個超參數(shù)K，K值的確定對KNN算法的預測結果有著至關重要的影響。如圖6.3所示。？圖6.3k值對分類影響的示意圖如圖6.3所示，小圓要被決定賦予哪個類，是小三角形還是小正方形？如果K=3，由于小三角形所占比例為2/3，小圓將被賦予小三角形那個類標簽；如果K=7，由于小正方形比例為4/7，因此小圓被賦予小正方形類別標簽。K值的確定如果K值比較小，相當于在較小的領域內訓練樣本并對實例（預測樣本）進行預測。這時，算法的近似誤差會比較小，因為只有與實例相近的訓練樣本才會對預測結果起作用。但是，它也有明顯的缺點：算法的估計誤差比較大，預測結果會對鄰近點十分敏感，如果鄰近點是噪聲點的話，預測就會出錯。因此，K值過小容易導致KNN算法的過擬合。同理，如果K值選擇較大的話，距離較遠的訓練樣本也能夠對實例預測結果產(chǎn)生影響。這時候，模型相對比較魯棒，不會因為個別噪聲對最終預測結果產(chǎn)生影響。但是缺點也十分明顯：算法的鄰近誤差會偏大，距離較遠的點（與預測實例不相似）也會同樣對預測結果產(chǎn)生影響，使得預測結果產(chǎn)生較大偏差，此時模型容易發(fā)生欠擬合。在實際工程實踐中，一般采用交叉驗證的方式選取K值。通過以上分析可知，一般盡量在較小范圍內選取K值，同時把測試集上準確率最高的那個K值確定為最終算法的參數(shù)K。例6.7使用交叉驗證方法確定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()程序運行結果如圖6.4所示。圖6.4例6.7程序運行結果由圖6.4能夠明顯看出K值取12的時候誤差最小。當然在實際問題中，如果數(shù)據(jù)集比較大，為了減少訓練時間，K的取值范圍可以縮小，例如K取值范圍為[10,15]。3Rocchio分類器模型6.3RocchioclassifiermodelRocchio算法簡述02應用于文本分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

01

最優(yōu)特征選擇

02

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

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

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

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

表

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

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

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

表6.7西瓜數(shù)據(jù)表編號色澤瓜蒂敲聲紋理臍部觸感密度含糖率好瓜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ù)值屬性密度、含糖率：計算測試瓜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很明顯，測試樣例西瓜xtest是好瓜的概率0.028遠大于xtest是壞瓜的概率6.80×10?5，于是分類器判斷xtest為好瓜。例6.14根據(jù)一個西瓜的特征來判斷它是否是個好瓜。數(shù)據(jù)集如表6.7所示。

表6.7西瓜數(shù)據(jù)表編號色澤瓜蒂敲聲紋理臍部觸感密度含糖率好瓜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否利用樸素貝葉斯算法訓練出一個{“好瓜”、“壞瓜”}的分類器，測試樣例西瓜xtest={色澤=青綠，瓜蒂=蜷縮，敲聲=濁響，紋理=清晰，臍部=凹陷，觸感=硬滑，密度=0.697，含糖率=0.460}的是否為好瓜。估計先驗概率

：

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

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

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

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

H1HH2

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

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

，可以得到如下公式：