數(shù)據(jù)挖掘之經(jīng)典算法

1、數(shù)據(jù)挖掘之經(jīng)典算法1 決策樹算法機(jī)器學(xué)習(xí)中，決策樹是一個預(yù)測模型；它代表的是對象屬性值與對象值之間的一種映射關(guān)系。樹中每個節(jié)點(diǎn)表示某個對象，每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點(diǎn)則對應(yīng)具有上述屬性值的子對象。決策樹僅有單一輸出；若需要多個輸出，可以建立獨(dú)立的決策樹以處理不同輸出。從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí), 通俗說就是決策樹。決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結(jié)構(gòu)，它由它的分支來對該類型的對象依靠屬性進(jìn)行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試。這個過程可以遞歸式的對樹進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個單獨(dú)的類可以

2、被應(yīng)用于某一分支時，遞歸過程就完成了。另外，隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。決策樹同時也可以依靠計(jì)算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計(jì)算方法可以取得更加理想的效果。1.1 決策樹的工作原理決策樹一般都是自上而下的來生成的。選擇分割的方法有多種，但是目的都是一致的，即對目標(biāo)類嘗試進(jìn)行最佳的分割。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)都有一條路徑，這條路徑就是一條“規(guī)則”。決策樹可以是二叉的，也可以是多叉的。對每個節(jié)點(diǎn)的衡量：1) 通過該節(jié)點(diǎn)的記錄數(shù)；2) 如果是葉子節(jié)點(diǎn)的話，分類的路徑；3) 對葉子節(jié)點(diǎn)正確分類的比例。有些規(guī)則的效果可以比其他的一些規(guī)則要好。YYYYNNNNw1Tx0 w4

3、Tx0 w3Tx0 w2Tx0 二叉決策樹框圖1.2 ID3算法 概念提取算法CLS 1) 初始化參數(shù)C=E，E包括所有的例子，為根；2) 如果C中的任一元素e同屬于同一個決策類則創(chuàng)建一個葉子節(jié)點(diǎn)YES終止；否則依啟發(fā)式標(biāo)準(zhǔn)，選擇特征Fi=V1, V2, V3, Vn并創(chuàng)建判定節(jié)點(diǎn)，劃分C為互不相交的N個集合C1，C2，C3，Cn； 3) 對任一個Ci遞歸。 ID3算法 1) 隨機(jī)選擇C的一個子集W (窗口)；2) 調(diào)用CLS生成W的分類樹DT(強(qiáng)調(diào)的啟發(fā)式標(biāo)準(zhǔn)在后)；3) 順序掃描C搜集DT的意外(即由DT無法確定的例子)； 4) 組合W與已發(fā)現(xiàn)的意外，形成新的W； 5) 重復(fù)2)到4)，直

4、到無例外為止。啟發(fā)式標(biāo)準(zhǔn)：只跟本身與其子樹有關(guān)，采取信息理論用熵來量度。 熵是選擇事件時選擇自由度的量度，其計(jì)算方法為：P=freq(Cj,S)/|S|；INFO(S)=-SUM(P*LOG(P)；SUM()函數(shù)是求j從1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM( (|Ti|/|T|)*Info(X)； 為保證生成的決策樹最小，ID3算法在生成子樹時，選取使生成的子樹的熵(即Gain(S)最小的特征來生成子樹。ID3算法對數(shù)據(jù)的要求：1) 所有屬性必須為離散量； 2) 所有的訓(xùn)練例的所有屬性必須有一個明確的值；3) 相同的因素必須得到相同的結(jié)論且訓(xùn)練

5、例必須唯一。1.3 C4.5算法由于ID3算法在實(shí)際應(yīng)用中存在一些問題，于是Quilan提出了C4.5算法，嚴(yán)格上說C4.5只能是ID3的一個改進(jìn)算法。C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對ID3算法進(jìn)行了改進(jìn)：1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2) 在樹構(gòu)造過程中進(jìn)行剪枝；3) 能夠完成對連續(xù)屬性的離散化處理；4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。C4.5算法有如下缺點(diǎn)：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留

6、于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運(yùn)行。分類決策樹算法：C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法，其核心算法是ID3算法。分類決策樹算法是從大量事例中進(jìn)行提取分類規(guī)則的自上而下的決策樹。決策樹的各部分是：根：學(xué)習(xí)的事例集；枝：分類的判定條件；葉：分好的各個類。 C4.5對ID3算法的改進(jìn) 1) 熵的改進(jìn)，加上了子樹的信息。Split_Infox(X)= -SUM( (|T|/|Ti|)*LOG(|Ti|/|T|)； Gain ratio(X)= Gain(X)/Split_Infox(X); 2) 在輸入數(shù)據(jù)上的改進(jìn) 因素屬性的值可以是連續(xù)量，C4.5對其排序并分成不

7、同的集合后按照ID3算法當(dāng)作離散量進(jìn)行處理，但結(jié)論屬性的值必須是離散值。 訓(xùn)練例的因素屬性值可以是不確定的，以?表示，但結(jié)論必須是確定的。 3) 對已生成的決策樹進(jìn)行裁剪，減小生成樹的規(guī)模。2 The k-means algorithm（k平均算法）k-means algorithm是一個聚類算法，把n個對象根據(jù)它們的屬性分為k個分割，k n。它與處理混合正態(tài)分布的最大期望算法很相似，因?yàn)樗麄兌荚噲D找到數(shù)據(jù)中自然聚類的中心。它假設(shè)對象屬性來自于空間向量，并且目標(biāo)是使各個群組內(nèi)部的均方誤差總和最小。假設(shè)有k個群組Si, i=1,2,.,k。i是群組Si內(nèi)所有元素xj的重心，或叫中心點(diǎn)。k平均聚類

8、發(fā)明于1956年，該算法最常見的形式是采用被稱為勞埃德算法(Lloyd algorithm)的迭代式改進(jìn)探索法。勞埃德算法首先把輸入點(diǎn)分成k個初始化分組，可以是隨機(jī)的或者使用一些啟發(fā)式數(shù)據(jù)。然后計(jì)算每組的中心點(diǎn)，根據(jù)中心點(diǎn)的位置把對象分到離它最近的中心，重新確定分組。繼續(xù)重復(fù)不斷地計(jì)算中心并重新分組，直到收斂，即對象不再改變分組（中心點(diǎn)位置不再改變）。勞埃德算法和k平均通常是緊密聯(lián)系的，但是在實(shí)際應(yīng)用中，勞埃德算法是解決k平均問題的啟發(fā)式法則，對于某些起始點(diǎn)和重心的組合，勞埃德算法可能實(shí)際上收斂于錯誤的結(jié)果。（上面函數(shù)中存在的不同的最優(yōu)解）雖然存在變異，但是勞埃德算法仍舊保持流行，因?yàn)樗趯?shí)際

9、中收斂非常快。實(shí)際上，觀察發(fā)現(xiàn)迭代次數(shù)遠(yuǎn)遠(yuǎn)少于點(diǎn)的數(shù)量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的點(diǎn)集使得k平均算法花費(fèi)超多項(xiàng)式時間達(dá)到收斂。近似的k平均算法已經(jīng)被設(shè)計(jì)用于原始數(shù)據(jù)子集的計(jì)算。從算法的表現(xiàn)上來說，它并不保證一定得到全局最優(yōu)解，最終解的質(zhì)量很大程度上取決于初始化的分組。由于該算法的速度很快，因此常用的一種方法是多次運(yùn)行k平均算法，選擇最優(yōu)解。k平均算法的一個缺點(diǎn)是，分組的數(shù)目k是一個輸入?yún)?shù)，不合適的k可能返回較差的結(jié)果。另外，算法還假設(shè)均方誤差是計(jì)算群組分散度的最佳參數(shù)。3 SVM（支持向量機(jī)）支持向量機(jī)，英文為Support V

10、ector Machine，簡稱SV機(jī)（論文中一般簡稱SVM）。它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。支持向量機(jī)屬于一般化線性分類器。它們也可以被認(rèn)為是提克洛夫規(guī)范化（Tikhonov Regularization）方法的一個特例。這種分類器的特點(diǎn)是他們能夠同時最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)。因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計(jì)的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)集聚（Data C

11、lustering）領(lǐng)域。最大期望算法經(jīng)過兩個步驟交替進(jìn)行計(jì)算，第一步是計(jì)算期望（E），也就是將隱藏變量像能夠觀測到的一樣包含在內(nèi)從而計(jì)算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值從而計(jì)算參數(shù)的最大似然估計(jì)。M 步上找到的參數(shù)然后用于另外一個 E 步計(jì)算，這個過程不斷交替進(jìn)行。Vapnik等人在多年研究統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上對線性分類器提出了另一種設(shè)計(jì)最佳準(zhǔn)則。其原理也從線性可分說起，然后擴(kuò)展到線性不可分的情況。甚至擴(kuò)展到使用非線性函數(shù)中去，這種分類器被稱為支持向量機(jī)(Support Vector Machine，簡稱SVM)。支持向量機(jī)的提出有很深的

12、理論背景。支持向量機(jī)方法是在近年來提出的一種新方法，但是進(jìn)展很快，已經(jīng)被廣泛應(yīng)用在各個領(lǐng)域之中。SVM的主要思想可以概括為兩點(diǎn)：(1) 它是針對線性可分情況進(jìn)行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進(jìn)行線性分析成為可能；(2) 它基于結(jié)構(gòu)風(fēng)險最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個樣本空間的期望風(fēng)險以某個概率滿足一定上界。在學(xué)習(xí)這種方法時，首先要弄清楚這種方法考慮問題的特點(diǎn)，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前

13、，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)在設(shè)計(jì)時，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對多數(shù)人來說，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時只要了解拉格朗日理論的有關(guān)結(jié)論就行。有很多個分類器(超平面）可以把數(shù)據(jù)分開，但是只有一個能夠達(dá)到最大分割。我們通常希望分類的過程是一個機(jī)器學(xué)習(xí)的過程。這些數(shù)據(jù)點(diǎn)并不需要是中的點(diǎn)，而可以是任意(統(tǒng)計(jì)學(xué)符號)中或者 (計(jì)算機(jī)科學(xué)符號) 的點(diǎn)。我們希望能夠把這些點(diǎn)通過一個n-1維的超平面分開，通常這個被稱為線性分類器。有很多分類器都符合這個要求，但是我們還希望找到分類最佳的平面，即使

14、得屬于兩個不同類的數(shù)據(jù)點(diǎn)間隔最大的那個面，該面亦稱為最大間隔超平面。如果我們能夠找到這個面，那么這個分類器就稱為最大間隔分類器。設(shè)樣本屬于兩個類，用該樣本訓(xùn)練SVM得到的最大間隔超平面。在超平面上的樣本點(diǎn)也稱為支持向量。SVM的優(yōu)勢：由于支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(Generalizatin Ability)。支持向量機(jī)方法的幾個主要優(yōu)點(diǎn)是：l 可以解決小樣本情況下的機(jī)器學(xué)習(xí)問題；l 可

15、以提高泛化性能；l 可以解決高維問題；l 可以解決非線性問題；l 可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點(diǎn)問題。4 貝葉斯（Bayes）分類器貝葉斯分類器的分類原理是通過某對象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：Naive Bayes、TAN、BAN和GBN。貝葉斯網(wǎng)絡(luò)是一個帶有概率注釋的有向無環(huán)圖，圖中的每一個結(jié)點(diǎn)均表示一個隨機(jī)變量，圖中兩結(jié)點(diǎn)間若存在著一條弧，則表示這兩結(jié)點(diǎn)相對應(yīng)的隨機(jī)變量是概率相依的，反之則說明這兩個隨機(jī)變量是條件獨(dú)立的。網(wǎng)絡(luò)中任意一個結(jié)點(diǎn)X 均有一個相

16、應(yīng)的條件概率表(Conditional Probability Table，CPT)，用以表示結(jié)點(diǎn)X 在其父結(jié)點(diǎn)取各可能值時的條件概率。若結(jié)點(diǎn)X 無父結(jié)點(diǎn)，則X 的CPT 為其先驗(yàn)概率分布。貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)及各結(jié)點(diǎn)的CPT 定義了網(wǎng)絡(luò)中各變量的概率分布。貝葉斯分類器是用于分類的貝葉斯網(wǎng)絡(luò)。該網(wǎng)絡(luò)中應(yīng)包含類結(jié)點(diǎn)C，其中C 的取值來自于類集合( c1 , c2 , . , cm)，還包含一組結(jié)點(diǎn)X = ( X1 , X2 , . , Xn)，表示用于分類的特征。對于貝葉斯網(wǎng)絡(luò)分類器，若某一待分類的樣本D，其分類特征向量為x = ( x1 , x2 , . , x n) ，則樣本D 屬于類別ci 的

17、概率為P( C = ci | X = x) = P( C = ci | X1 = x1 , X2 = x 2 , . , Xn = x n) ，( i = 1 ,2 , . , m) 。而由貝葉斯公式可得：P( C = ci | X = x) = P( X = x | C = ci) P( C = ci) / P( X = x)其中，P( C = ci) 可由領(lǐng)域?qū)＜业慕?jīng)驗(yàn)得到，稱為先驗(yàn)概率；而P( X = x | C = ci) 和P( X = x) 的計(jì)算則較困難；P( C = ci | X = x)稱為后驗(yàn)概率。應(yīng)用貝葉斯網(wǎng)絡(luò)分類器進(jìn)行分類主要分成兩階段。第一階段是貝葉斯網(wǎng)絡(luò)分類器的學(xué)習(xí)

18、，即從樣本數(shù)據(jù)中構(gòu)造分類器；第二階段是貝葉斯網(wǎng)絡(luò)分類器的推理，即計(jì)算類結(jié)點(diǎn)的條件概率，對分類數(shù)據(jù)進(jìn)行分類。這兩個階段的時間復(fù)雜性均取決于特征值間的依賴程度，甚至可以是NP完全問題（世界七大數(shù)學(xué)難題之一），因而在實(shí)際應(yīng)用中，往往需要對貝葉斯網(wǎng)絡(luò)分類器進(jìn)行簡化。根據(jù)對特征值間不同關(guān)聯(lián)程度的假設(shè)，可以得出各種貝葉斯分類器，Naive Bayes、TAN、BAN、GBN就是其中較典型、研究較深入的貝葉斯分類器。4.1 樸素貝葉斯（Naive Bayes）分類器分類是將一個未知樣本分到幾個預(yù)先已知類的過程。數(shù)據(jù)分類問題的解決是一個兩步過程：第一步，建立模型，描述預(yù)先的數(shù)據(jù)集或概念集。通過分析由屬性/特征

19、描述的樣本（或?qū)嵗瑢ο蟮龋﹣順?gòu)造模型。假定每一個樣本都有一個預(yù)先定義的類，由一個被稱為類標(biāo)簽的屬性確定。為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集，該步也稱作有指導(dǎo)的學(xué)習(xí)。在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。決策樹模型通過構(gòu)造樹來解決分類問題。首先利用訓(xùn)練數(shù)據(jù)集來構(gòu)造一棵決策樹，一旦樹建立起來，它就可為未知樣本產(chǎn)生一個分類。在分類問題中使用決策樹模型有很多的優(yōu)點(diǎn)，決策樹便于使用，而且高效；根據(jù)決策樹可以很容易地構(gòu)造出規(guī)則，而規(guī)則通常易于解釋和理解；決策樹可很好

20、地?cái)U(kuò)展到大型數(shù)據(jù)庫中，同時它的大小獨(dú)立于數(shù)據(jù)庫的大??；決策樹模型的另外一大優(yōu)點(diǎn)就是可以對有許多屬性的數(shù)據(jù)集構(gòu)造決策樹。決策樹模型也有一些缺點(diǎn)，比如處理缺失數(shù)據(jù)時的困難，過度擬合問題的出現(xiàn)，以及忽略數(shù)據(jù)集中屬性之間的相關(guān)性等。和決策樹模型相比，樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。同時，NBC模型所需估計(jì)的參數(shù)很少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實(shí)際上并非總是如此，這是因?yàn)镹BC模型假設(shè)屬性之間相互獨(dú)立，這個假設(shè)在實(shí)際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數(shù)比較多或

21、者屬性之間相關(guān)性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時，NBC模型的性能最為良好。樸素貝葉斯模型：Vmap=arg maxP( Vj | a1,a2.an)Vj屬于V集合，其中j=1,2,N，即共有N類；Vmap是給定一個example，得到的最可能的目標(biāo)值；a1.an是這個example里面的屬性/特征，共有n個特征。Vmap為目標(biāo)值，就是后面計(jì)算得出的概率最大的一個，所以用max 來表示，它意味著該example應(yīng)該/最可能為得到最大后驗(yàn)概率的那個類，這與前面講到的貝葉斯分類器是一致的。將貝葉斯公式應(yīng)用到 P( Vj | a1,a2.an)中，可得到：Vmap=

22、 arg maxP(a1,a2.an | Vj ) P( Vj ) / P (a1,a2.an)又因?yàn)闃闼刎惾~斯分類器默認(rèn)a1.an他們互相獨(dú)立的，所以P(a1,a2.an)對于結(jié)果沒有影響（因?yàn)樗械母怕识家粋€東西之后再比較大?。?。于是可得到：Vmap= arg maxP(a1,a2.an | Vj ) P( Vj )然后，樸素貝葉斯分類器基于一個簡單的假定：給定目標(biāo)值時屬性之間相互條件獨(dú)立。換言之，該假定說明給定實(shí)例的目標(biāo)值情況下，觀察到聯(lián)合的a1,a2.an的概率正好是對每個單獨(dú)屬性的概率乘積：P(a1,a2.an | Vj ) = i P( ai| Vj )。因此，樸素貝葉斯分類

23、器公式為：Vnb =arg maxP( Vj )i P ( ai | Vj )。5 鄰近算法（k-Nearest Neighbor algorithm，k最近鄰算法）下圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？如果K=3（即實(shí)線圓內(nèi)部），由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5（即虛線圓內(nèi)），由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近

24、)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該

25、樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個不足之處是計(jì)算量較大，因?yàn)閷γ恳粋€待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個最近鄰點(diǎn)。目前常用的解決方法是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。6 回歸樹分

26、類器如果要選擇在很大范圍的情形下性能都好的、同時不需要應(yīng)用開發(fā)者付出很多的努力并且易于被終端用戶理解的分類技術(shù)的話，那么Brieman, Friedman, Olshen和Stone（1984）提出的分類樹方法是一個強(qiáng)有力的競爭者。6.1 分類樹在分類樹下面有兩個關(guān)鍵的思想。第一個是關(guān)于遞歸地劃分自變量空間的想法；第二個想法是用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝。6.2 遞歸劃分讓我們用變量Y表示因變量（分類變量），用X1, X2, X3,.,Xp表示自變量。通過遞歸的方式把關(guān)于變量X的p維空間劃分為不重疊的矩形。首先，一個自變量被選擇，比如Xi和Xi的一個值xi，比方說選擇xi把p維空間為兩部分：一部分是p維

27、的超矩形，其中包含的點(diǎn)都滿足Xixi。接著，這兩部分中的一個部分通過選擇一個變量和該變量的劃分值以相似的方式被劃分。這導(dǎo)致了三個矩形區(qū)域。隨著這個過程的持續(xù)，我們得到的矩形越來越小。這個想法是把整個X空間劃分為矩形，其中的每個小矩形都盡可能是同構(gòu)的或“純”的?！凹儭钡囊馑际牵ň匦危┧狞c(diǎn)都屬于同一類。我們認(rèn)為包含的點(diǎn)都只屬于一個類（當(dāng)然，這并不總是可能的，因?yàn)榻?jīng)常存在一些屬于不同類的點(diǎn)，但這些點(diǎn)的自變量有完全相同的值）。7 Adaboost分類器Adaboost是adaptive boost的縮寫，它是一種迭代算法。其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類

28、器集合起來，構(gòu)成一個更強(qiáng)的最終分類器 (強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器融合起來，作為最后的決策分類器。使用Adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并將重點(diǎn)放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上。該算法其實(shí)是一個弱分類算法的提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能力。整個過程如下所示：l 先通過對N個數(shù)據(jù)的訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器；l 將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個數(shù)據(jù)的訓(xùn)練

29、樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器 ；l 將1.和2.都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個數(shù)據(jù)的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器 ；l 最終經(jīng)過提升的強(qiáng)分類器，即某個數(shù)據(jù)被分為哪一類要通過，的多數(shù)表決。對于boosting算法，存在兩個問題：l 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行；l 如何將訓(xùn)練得到的各個弱分類器聯(lián)合起來形成強(qiáng)分類器。針對以上兩個問題，adaboost算法進(jìn)行了調(diào)整：l 使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上；l 將弱分類器聯(lián)合起來，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制

30、。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。Adaboost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細(xì)分析了Adaboost算法錯誤率的上界，以及為了使強(qiáng)分類器達(dá)到要求的錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與Boosting算法不同的是，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。Adaboost算法中不同的訓(xùn)練集是通過調(diào)整每個樣本對應(yīng)的權(quán)重來實(shí)現(xiàn)的。開始時，每個樣本對應(yīng)的權(quán)重是相同的，即其中 n

31、為樣本個數(shù)，在此樣本分布下訓(xùn)練出一弱分類器。對于分類錯誤的樣本，加大其對應(yīng)的權(quán)重；而對于分類正確的樣本，降低其權(quán)重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進(jìn)行訓(xùn)練，得到弱分類器。依次類推，經(jīng)過T次循環(huán)，得到T個弱分類器，把這T個弱分類器按一定的權(quán)重疊加（boost）起來，得到最終想要的強(qiáng)分類器。8 人工神經(jīng)網(wǎng)絡(luò)（ANN, artificial neural network）人工神經(jīng)網(wǎng)絡(luò)是由具有適應(yīng)性的簡單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對真實(shí)世界物體所作出的交互反應(yīng)。神經(jīng)網(wǎng)絡(luò)基本模型人工神經(jīng)網(wǎng)絡(luò)研究的局限性：l 研究受到

32、腦科學(xué)研究成果的限制； l 缺少一個完整、成熟的理論體系；l 研究帶有濃厚的策略和經(jīng)驗(yàn)色彩；l 與傳統(tǒng)技術(shù)的接口不成熟。 一般而言, ANN與經(jīng)典計(jì)算方法相比并非優(yōu)越, 只有當(dāng)常規(guī)方法解決不了或效果不佳時ANN方法才能顯示出其優(yōu)越性。尤其對問題的機(jī)理不甚了解或不能用數(shù)學(xué)模型表示的系統(tǒng),如故障診斷、特征提取和預(yù)測等問題,ANN往往是最有利的工具。另一方面, ANN對處理大量原始數(shù)據(jù)而不能用規(guī)則或公式描述的問題, 表現(xiàn)出極大的靈活性和自適應(yīng)性。8.1 BP網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)以其具有自學(xué)習(xí)、自組織、較好的容錯性和優(yōu)良的非線性逼近能力，受到眾多領(lǐng)域?qū)W者的關(guān)注。在實(shí)際應(yīng)用中，80%90%的人工神經(jīng)網(wǎng)絡(luò)模型是采用誤差反傳算法