數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)new

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

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

3、1Tx0 w4Tx0 w3Tx0 w2Tx0 二叉決策樹框圖1.2 ID3算法 1.2.1 概念提取算法CLS 1) 初始化參數(shù)C=E，E包括所有的例子，為根；2) 如果C中的任一元素e同屬于同一個(gè)決策類則創(chuàng)建一個(gè)葉子節(jié)點(diǎn)YES終止；否則依啟發(fā)式標(biāo)準(zhǔn)，選擇特征Fi=V1, V2, V3, Vn并創(chuàng)建判定節(jié)點(diǎn)，劃分C為互不相交的N個(gè)集合C1，C2，C3，Cn； 3) 對(duì)任一個(gè)Ci遞歸。1.2.2 ID3算法 1) 隨機(jī)選擇C的一個(gè)子集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)的意外，形

4、成新的W； 5) 重復(fù)2)到4)，直到無例外為止。啟發(fā)式標(biāo)準(zhǔn)：只跟本身與其子樹有關(guān)，采取信息理論用熵來量度。 熵是選擇事件時(shí)選擇自由度的量度，其計(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算法在生成子樹時(shí)，選取使生成的子樹的熵(即Gain(S)最小的特征來生成子樹。ID3算法對(duì)數(shù)據(jù)的要求：1) 所有屬性必須為離散量； 2) 所有的訓(xùn)練例的所有屬性必須有一個(gè)明確的值；3)

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

6、低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。分類決策樹算法：C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法，其核心算法是ID3算法。分類決策樹算法是從大量事例中進(jìn)行提取分類規(guī)則的自上而下的決策樹。決策樹的各部分是：根：學(xué)習(xí)的事例集；枝：分類的判定條件；葉：分好的各個(gè)類。1.3.1 C4.5對(duì)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) 因素

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

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

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

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

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

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

13、性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)在設(shè)計(jì)時(shí)，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對(duì)多數(shù)人來說，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時(shí)只要了解拉格朗日理論的有關(guān)結(jié)論就行。支持向量機(jī)將向量映射到一個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。分隔超平面使兩個(gè)平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。一個(gè)極好的指南是C.J.C Burges的模式識(shí)別支持向量機(jī)指南。van

14、der Walt 和 Barnard 將支持向量機(jī)和其他分類器進(jìn)行了比較。有很多個(gè)分類器(超平面）可以把數(shù)據(jù)分開，但是只有一個(gè)能夠達(dá)到最大分割。我們通常希望分類的過程是一個(gè)機(jī)器學(xué)習(xí)的過程。這些數(shù)據(jù)點(diǎn)并不需要是中的點(diǎn)，而可以是任意(統(tǒng)計(jì)學(xué)符號(hào))中或者 (計(jì)算機(jī)科學(xué)符號(hào)) 的點(diǎn)。我們希望能夠把這些點(diǎn)通過一個(gè)n-1維的超平面分開，通常這個(gè)被稱為線性分類器。有很多分類器都符合這個(gè)要求，但是我們還希望找到分類最佳的平面，即使得屬于兩個(gè)不同類的數(shù)據(jù)點(diǎn)間隔最大的那個(gè)面，該面亦稱為最大間隔超平面。如果我們能夠找到這個(gè)面，那么這個(gè)分類器就稱為最大間隔分類器。設(shè)樣本屬于兩個(gè)類，用該樣本訓(xùn)練SVM得到的最大間隔超平

15、面。在超平面上的樣本點(diǎn)也稱為支持向量。SVM的優(yōu)勢(shì)：由于支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯(cuò)誤地識(shí)別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(Generalizatin Ability)。支持向量機(jī)方法的幾個(gè)主要優(yōu)點(diǎn)是：l 可以解決小樣本情況下的機(jī)器學(xué)習(xí)問題；l 可以提高泛化性能；l 可以解決高維問題；l 可以解決非線性問題；l 可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點(diǎn)問題。4 貝葉斯（Bayes）分類器貝葉斯分類器的分類原理是通過某對(duì)象的先驗(yàn)概率

16、，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對(duì)象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：Naive Bayes、TAN、BAN和GBN。貝葉斯網(wǎng)絡(luò)是一個(gè)帶有概率注釋的有向無環(huán)圖，圖中的每一個(gè)結(jié)點(diǎn)均表示一個(gè)隨機(jī)變量，圖中兩結(jié)點(diǎn)間若存在著一條弧，則表示這兩結(jié)點(diǎn)相對(duì)應(yīng)的隨機(jī)變量是概率相依的，反之則說明這兩個(gè)隨機(jī)變量是條件獨(dú)立的。網(wǎng)絡(luò)中任意一個(gè)結(jié)點(diǎn)X 均有一個(gè)相應(yīng)的條件概率表(Conditional Probability Table，CPT)，用以表示結(jié)點(diǎn)X 在其父結(jié)點(diǎn)取各可能值時(shí)的條件概率。若結(jié)點(diǎn)X 無父結(jié)點(diǎn)，則X 的CPT 為其先驗(yàn)概

17、率分布。貝葉斯網(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)，表示用于分類的特征。對(duì)于貝葉斯網(wǎng)絡(luò)分類器，若某一待分類的樣本D，其分類特征向量為x = ( x1 , x2 , . , x n) ，則樣本D 屬于類別ci 的概率為P( C = ci | X = x) = P( C = ci | X1 = x1 , X2 = x 2 , . , Xn = x n) ，( i = 1 ,2 , . , m)

18、 。而由貝葉斯公式可得：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í)，即從樣本數(shù)據(jù)中構(gòu)造分類器；第二階段是貝葉斯網(wǎng)絡(luò)分類器的推理，即計(jì)算類結(jié)點(diǎn)的條件概率，對(duì)分類數(shù)據(jù)進(jìn)行分類。這兩個(gè)階段的時(shí)間復(fù)雜性均取決于特征值間的依賴程度，甚至可以是NP完全問題（世

19、界七大數(shù)學(xué)難題之一），因而在實(shí)際應(yīng)用中，往往需要對(duì)貝葉斯網(wǎng)絡(luò)分類器進(jìn)行簡化。根據(jù)對(duì)特征值間不同關(guān)聯(lián)程度的假設(shè)，可以得出各種貝葉斯分類器，Naive Bayes、TAN、BAN、GBN就是其中較典型、研究較深入的貝葉斯分類器。4.1 樸素貝葉斯（Naive Bayes）分類器分類是將一個(gè)未知樣本分到幾個(gè)預(yù)先已知類的過程。數(shù)據(jù)分類問題的解決是一個(gè)兩步過程：第一步，建立模型，描述預(yù)先的數(shù)據(jù)集或概念集。通過分析由屬性/特征描述的樣本（或?qū)嵗?，?duì)象等）來構(gòu)造模型。假定每一個(gè)樣本都有一個(gè)預(yù)先定義的類，由一個(gè)被稱為類標(biāo)簽的屬性確定。為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集，該步也稱作有指導(dǎo)的學(xué)習(xí)。4.1.

20、1 決策樹模型和樸素貝葉斯模型的比較在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。決策樹模型通過構(gòu)造樹來解決分類問題。首先利用訓(xùn)練數(shù)據(jù)集來構(gòu)造一棵決策樹，一旦樹建立起來，它就可為未知樣本產(chǎn)生一個(gè)分類。在分類問題中使用決策樹模型有很多的優(yōu)點(diǎn)，決策樹便于使用，而且高效；根據(jù)決策樹可以很容易地構(gòu)造出規(guī)則，而規(guī)則通常易于解釋和理解；決策樹可很好地?cái)U(kuò)展到大型數(shù)據(jù)庫中，同時(shí)它的大小獨(dú)立于數(shù)據(jù)庫的大小；決策樹模型的另外一大優(yōu)點(diǎn)就是可以對(duì)有許多屬性的數(shù)據(jù)集構(gòu)造決策樹。決策樹模型也有一些缺

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

22、rg maxP( Vj | a1,a2.an)Vj屬于V集合，其中j=1,2,N，即共有N類；Vmap是給定一個(gè)example，得到的最可能的目標(biāo)值；a1.an是這個(gè)example里面的屬性/特征，共有n個(gè)特征。Vmap為目標(biāo)值，就是后面計(jì)算得出的概率最大的一個(gè)，所以用max 來表示，它意味著該example應(yīng)該/最可能為得到最大后驗(yàn)概率的那個(gè)類，這與前面講到的貝葉斯分類器是一致的。將貝葉斯公式應(yīng)用到 P( Vj | a1,a2.an)中，可得到：Vmap= arg maxP(a1,a2.an | Vj ) P( Vj ) / P (a1,a2.an)又因?yàn)闃闼刎惾~斯分類器默認(rèn)a1.an他們互

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

24、orithm，k最近鄰算法）下圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3（即實(shí)線圓內(nèi)部），由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5（即虛線圓內(nèi)），由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個(gè)理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近

25、的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，

26、而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。6 回歸樹分類器如果要選擇在很大范圍的情形下性能都好的、同時(shí)不需要應(yīng)用開發(fā)者付出很多的努力并且易于被終端用戶理解的分類技術(shù)的話，那么Brieman,

27、Friedman, Olshen和Stone（1984）提出的分類樹方法是一個(gè)強(qiáng)有力的競爭者。6.1 分類樹在分類樹下面有兩個(gè)關(guān)鍵的思想。第一個(gè)是關(guān)于遞歸地劃分自變量空間的想法；第二個(gè)想法是用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝。6.2 遞歸劃分讓我們用變量Y表示因變量（分類變量），用X1, X2, X3,.,Xp表示自變量。通過遞歸的方式把關(guān)于變量X的p維空間劃分為不重疊的矩形。首先，一個(gè)自變量被選擇，比如Xi和Xi的一個(gè)值xi，比方說選擇xi把p維空間為兩部分：一部分是p維的超矩形，其中包含的點(diǎn)都滿足Xixi。接著，這兩部分中的一個(gè)部分通過選擇一個(gè)變量和該變量的劃分值以相似的方式被劃分。這導(dǎo)致了三個(gè)矩形區(qū)域。

28、隨著這個(gè)過程的持續(xù)，我們得到的矩形越來越小。這個(gè)想法是把整個(gè)X空間劃分為矩形，其中的每個(gè)小矩形都盡可能是同構(gòu)的或“純”的?！凹儭钡囊馑际牵ň匦危┧狞c(diǎn)都屬于同一類。我們認(rèn)為包含的點(diǎn)都只屬于一個(gè)類（當(dāng)然，這并不總是可能的，因?yàn)榻?jīng)常存在一些屬于不同類的點(diǎn)，但這些點(diǎn)的自變量有完全相同的值）。7 Adaboost分類器Adaboost是adaptive boost的縮寫，它是一種迭代算法。其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器 (強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及

29、上次的總體分類的準(zhǔn)確率，來確定每個(gè)樣本的權(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í)是一個(gè)弱分類算法的提升過程，這個(gè)過程通過不斷的訓(xùn)練，可以提高對(duì)數(shù)據(jù)的分類能力。整個(gè)過程如下所示：l 先通過對(duì)N個(gè)數(shù)據(jù)的訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器；l 將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)數(shù)據(jù)的訓(xùn)練樣本，通過對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器 ；l 將1.和2.都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)數(shù)據(jù)的訓(xùn)練樣本，通過對(duì)這個(gè)

30、樣本的學(xué)習(xí)得到第三個(gè)弱分類器 ；l 最終經(jīng)過提升的強(qiáng)分類器，即某個(gè)數(shù)據(jù)被分為哪一類要通過，的多數(shù)表決。對(duì)于boosting算法，存在兩個(gè)問題：l 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行；l 如何將訓(xùn)練得到的各個(gè)弱分類器聯(lián)合起來形成強(qiáng)分類器。針對(duì)以上兩個(gè)問題，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ī)制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。Adaboost算法是Freund和Schapire根據(jù)在線分

31、配算法提出的，他們?cè)敿?xì)分析了Adaboost算法錯(cuò)誤率的上界，以及為了使強(qiáng)分類器達(dá)到要求的錯(cuò)誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與Boosting算法不同的是，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。Adaboost算法中不同的訓(xùn)練集是通過調(diào)整每個(gè)樣本對(duì)應(yīng)的權(quán)重來實(shí)現(xiàn)的。開始時(shí)，每個(gè)樣本對(duì)應(yīng)的權(quán)重是相同的，即其中 n 為樣本個(gè)數(shù)，在此樣本分布下訓(xùn)練出一弱分類器。對(duì)于分類錯(cuò)誤的樣本，加大其對(duì)應(yīng)的權(quán)重；而對(duì)于分類正確的樣本，降低其權(quán)重，這樣分錯(cuò)的樣本就被突出

32、出來，從而得到一個(gè)新的樣本分布。在新的樣本分布下，再次對(duì)弱分類器進(jìn)行訓(xùn)練，得到弱分類器。依次類推，經(jīng)過T次循環(huán)，得到T個(gè)弱分類器，把這T個(gè)弱分類器按一定的權(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)對(duì)真實(shí)世界物體所作出的交互反應(yīng)。神經(jīng)網(wǎng)絡(luò)基本模型人工神經(jīng)網(wǎng)絡(luò)研究的局限性：l 研究受到腦科學(xué)研究成果的限制； l 缺少一個(gè)完整、成熟的理論體系；l 研究帶有濃厚的策略和經(jīng)驗(yàn)色彩；l 與傳統(tǒng)技術(shù)的接口不成熟。 一般而言, AN

33、N與經(jīng)典計(jì)算方法相比并非優(yōu)越, 只有當(dāng)常規(guī)方法解決不了或效果不佳時(shí)ANN方法才能顯示出其優(yōu)越性。尤其對(duì)問題的機(jī)理不甚了解或不能用數(shù)學(xué)模型表示的系統(tǒng),如故障診斷、特征提取和預(yù)測(cè)等問題,ANN往往是最有利的工具。另一方面, ANN對(duì)處理大量原始數(shù)據(jù)而不能用規(guī)則或公式描述的問題, 表現(xiàn)出極大的靈活性和自適應(yīng)性。8.1 BP網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)以其具有自學(xué)習(xí)、自組織、較好的容錯(cuò)性和優(yōu)良的非線性逼近能力，受到眾多領(lǐng)域?qū)W者的關(guān)注。在實(shí)際應(yīng)用中，80%90%的人工神經(jīng)網(wǎng)絡(luò)模型是采用誤差反傳算法或其變化形式的網(wǎng)絡(luò)模型（簡稱BP網(wǎng)絡(luò)），目前主要應(yīng)用于函數(shù)逼近、模式識(shí)別、分類和數(shù)據(jù)壓縮或數(shù)據(jù)挖掘。 （1）BP網(wǎng)絡(luò)建模

34、特點(diǎn)：l 非線性映照能力：神經(jīng)網(wǎng)絡(luò)能以任意精度逼近任何非線性連續(xù)函數(shù)。在建模過程中的許多問題正是具有高度的非線性。l 并行分布處理方式：在神經(jīng)網(wǎng)絡(luò)中信息是分布儲(chǔ)存和并行處理的，這使它具有很強(qiáng)的容錯(cuò)性和很快的處理速度。l 自學(xué)習(xí)和自適應(yīng)能力：神經(jīng)網(wǎng)絡(luò)在訓(xùn)練時(shí)，能從輸入、輸出的數(shù)據(jù)中提取出規(guī)律性的知識(shí)，記憶于網(wǎng)絡(luò)的權(quán)值中，并具有泛化能力，即將這組權(quán)值應(yīng)用于一般情形的能力。神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)也可以在線進(jìn)行。l 數(shù)據(jù)融合的能力：神經(jīng)網(wǎng)絡(luò)可以同時(shí)處理定量信息和定性信息，因此它可以利用傳統(tǒng)的工程技術(shù)（數(shù)值運(yùn)算）和人工智能技術(shù)（符號(hào)處理）。l 多變量系統(tǒng)：神經(jīng)網(wǎng)絡(luò)的輸入和輸出變量的數(shù)目是任意的，對(duì)單變量系統(tǒng)與多

35、變量系統(tǒng)提供了一種通用的描述方式，不必考慮各子系統(tǒng)間的解耦問題。（2）樣本數(shù)據(jù)的收集和整理分組：采用BP神經(jīng)網(wǎng)絡(luò)方法建模的首要和前提條件是有足夠多典型性好和精度高的樣本。而且，為監(jiān)控訓(xùn)練（學(xué)習(xí)）過程使之不發(fā)生“過擬合”和評(píng)價(jià)建立的網(wǎng)絡(luò)模型的性能和泛化能力，必須將收集到的數(shù)據(jù)隨機(jī)分成訓(xùn)練樣本、檢驗(yàn)樣本（10%以上）和測(cè)試樣本（10%以上）3部分。此外，數(shù)據(jù)分組時(shí)還應(yīng)盡可能考慮樣本模式間的平衡。由于傳統(tǒng)的誤差反傳BP算法較為成熟，且應(yīng)用廣泛，因此努力提高該方法的學(xué)習(xí)速度具有較高的實(shí)用價(jià)值。BP算法中有幾個(gè)常用的參數(shù)，包括學(xué)習(xí)率，動(dòng)量因子，形狀因子及收斂誤差界值E等。這些參數(shù)對(duì)訓(xùn)練速度的影響最為關(guān)鍵

36、。9 Fisher分類器X空間：WTX-W0 0 X1 -WTX-W0 0 X1Y = WTX-W0 h where the threshold h is found by sorting S on the values of A and choosing the split between successive values that maximizes the criterion above. An attribute A with discrete values has by default one outcome for each value, but an option allows

37、 the values to be grouped into two or more subsets with one outcome for each subset. The initial tree is then pruned to avoid overfitting. The pruning algorithm is based on a pessimistic estimate of the error rate associated with a set of N cases, E of which do not belong to the most frequent class.

38、 Instead of E/N, C4.5 determines the upper limit of the binomial probability when E events have been observed in N trials, using a user-specified confidence whose default value is 0.25. Pruning is carried out from the leaves to the root. The estimated error at a leaf with N cases and E errors is N times the pessimistic error rate as above. For a subtree, C4.5 adds the estimated errors of the branches and compares this to the estimated er