關(guān)于作者
一個畢業(yè)于北京大學數(shù)學力學系，在中國科學院計算所、計算中心和網(wǎng)絡中心工作過，在澳大利亞科工組織DMS、香港浸會學院數(shù)學系和中國21世紀議程管理中心等處工作過，多次獲國家和中科院科技獎并享受政府特殊津貼的退休老頭?，F(xiàn)在在【中國科普博覽】網(wǎng)“科學新語林”欄目里開設一個《數(shù)學與計算機》的個人專欄，愿和愛好數(shù)學與計算機的各界網(wǎng)友和青少年朋友，談談對數(shù)學與計算機的看法、想法。
機器學習與數(shù)據(jù)挖掘中的十大經(jīng)典算法
張建中
2016年03月24日數(shù)學技術(shù)之算法概論篇（5）
④機器學習與數(shù)據(jù)挖掘中的十大經(jīng)典算法
數(shù)年前，有人動議在機器學習與數(shù)據(jù)挖掘領域中找出十大算法，即建立該領域算法的一個top10。后在該領域選出部分專家學者，經(jīng)他們提名、匯總和篩選，在分類，聚類，圖挖掘，關(guān)聯(lián)分析等領域共選出18個算法。對這18個算法在更廣泛的領域內(nèi)，一人一票，最終得出了其中的10個作為最后的算法。應該說，受時間、經(jīng)驗、領域和參選人數(shù)等諸多限制，入選的十大算法，不一定個個都是最優(yōu)秀的；受條件所限沒有入選的有些算法，也不能說是不好的。下面列出這十大算法，供參考。一、分類決策樹算法C4.5
C4.5，是機器學習算法中的一個分類決策樹算法，它是決策樹(決策樹，就是做決策的節(jié)點間的組織方式像一棵倒栽樹)核心算法ID3的改進算法，所以基本上了解了一半決策樹構(gòu)造方法就能構(gòu)造它。決策樹構(gòu)造方法其實就是每次選擇一個好的特征以及分裂點作為當前節(jié)點的分類條件。
C4.5相比于ID3改進的地方有：
1、用信息增益率選擇屬性。
ID3選擇屬性用的是子樹的信息增益，這里可以用很多方法來定義信息，ID3使用的是熵，一種不純度度量準則，也就是熵的變化值，而C4.5用的是信息增益率。區(qū)別就在于一個是信息增益，一個是信息增益率。
2、 在樹構(gòu)造過程中進行剪枝，在構(gòu)造決策樹的時候，那些掛著幾個元素的節(jié)點，不考慮最好，不然容易導致過擬。
3、能對非離散數(shù)據(jù)和不完整數(shù)據(jù)進行處理。
二、 K平均算法
K平均算法（k-means algorithm）是一個聚類算法，把n個分類對象根據(jù)它們的屬性分為k類（k
近似的k平均算法已經(jīng)被設計用于原始數(shù)據(jù)子集的計算。
從算法的表現(xiàn)上來說，它并不保證一定得到全局最優(yōu)解，最終解的質(zhì)量很大程度上取決于初始化的分組。由于該算法的速度很快，因此常用的一種方法是多次運行k平均算法，選擇最優(yōu)解。
算法缺點是，分組的數(shù)目k是一個輸入?yún)?shù)，不合適的k可能返回較差的結(jié)果。另外，算法還假設均方誤差是計算群組分散度的最佳參數(shù)。
三、支持向量機算法
支持向量機(Support Vector Machine)算法，簡記為SVM，是一種監(jiān)督式學習的方法，廣泛用于統(tǒng)計分類以及回歸分析中。
支持向量機屬于一般化線性分類器。這類分類器的特點是他們能夠同時最小化經(jīng)驗誤差與最大化幾何邊緣區(qū)，因此支持向量機也被稱為最大邊緣區(qū)分類器。
Vapnik等人在多年研究統(tǒng)計學習理論基礎上對線性分類器提出了另一種設計最佳準則。其原理也從線性可分說起，然后擴展到線性不可分的情況，甚至擴展到使用非線性函數(shù)中去。支持向量機是一種有很深理論背景的一種新方法。
SVM的主要思想可以概括為兩點：(1)它是針對線性可分情況進行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進行線性分析成為可能；(2)它基于結(jié)構(gòu)風險最小化理論之上，在特征空間中建構(gòu)最優(yōu)分割超平面，使得學習器得到全局最優(yōu)化，并且在整個樣本空間的期望風險以某個概率滿足一定上界。
四、The Apriori algorithm
Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。
Apriori演算法所使用的前置統(tǒng)計量包括：
？最大規(guī)則物件數(shù)：規(guī)則中物件組所包含的最大物件數(shù)量；
？最小支援：規(guī)則中物件或是物件組必頇符合的最低案例數(shù)；
？最小信心水準：計算規(guī)則所必須符合的最低信心水準門檻。
該算法的基本思想是：首先找出所有的頻集，這些頻集出現(xiàn)的頻繁性至少和預定義的最小支持度一樣。然后由頻集產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推方法。
可能產(chǎn)生大量的候選集，以及可能需要重復掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點。
五、最大期望(EM) 算法
在統(tǒng)計計算中，最大期望（EM，Expectation–Maximization）算法是在概率模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量。最大期望經(jīng)常用在機器學習和計算機視覺的數(shù)據(jù)集聚領域。最大期望算法經(jīng)過兩個步驟交替進行計算，第一步是計算期望（E），也就是將隱藏變量象能夠觀測到的一樣包含在內(nèi)從而計算最大似然的期望值；第二步是最大化（M），也就是最大化在E步上找到的最大似然的期望值從而計算參數(shù)的最大似然估計。M步上找到的參數(shù)然后用于另外一個E步計算，這個過程不斷交替進行。
六、Page Rank 算法
Page Rank是Google算法的重要內(nèi)容。2001年9月被授予美國專利，專利人是Google創(chuàng)始人之一拉里？佩奇(Larry Page)。因此，Page Rank里的page不是網(wǎng)頁，而是佩奇，即這個方法是以佩奇來命名的。Page Rank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量，衡量網(wǎng)站的價值。Page Rank背后的概念是每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)站投票越多。這就是所謂的“鏈接流行度”——衡量多少人愿意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。Page Rank這個概念引自學術(shù)中一篇論文的被引述的頻度——即被別人引述的次數(shù)越多，一般判斷這篇論文的權(quán)威性就越高。
七、Ada Boost 迭代算法
Ada boost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。使用Ada boost分類器可以排除一些不必要的訓練數(shù)據(jù)特徵，并將關(guān)鍵放在關(guān)鍵的訓練數(shù)據(jù)上面。
目前，對Ada boost算法的研究以及應用大多集中于分類問題，同時近年也出現(xiàn)了一些在回歸問題上的應用。就其應用Ada boost系列主要解決兩類問題：多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。它用全部的訓練樣本進行學習。
該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓練，可以提高對數(shù)據(jù)的分類能力。整個過程如下所示：
1. 先通過對N個訓練樣本的學習得到第一個弱分類器；
2. 將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器；
3. 將和都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器；
4. 最終經(jīng)過提升的強分類器，即某個數(shù)據(jù)被分為哪一類要通過多數(shù)表決。
對于Ada boosting算法，存在兩個問題：
1. 如何調(diào)整訓練集，使得在訓練集上訓練的弱分類器得以進行；
2. 如何將訓練得到的各個弱分類器聯(lián)合起來形成強分類器。
針對以上兩個問題，Ada boost算法進行了調(diào)整：
1. 使用加權(quán)后選取的訓練數(shù)據(jù)代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數(shù)據(jù)樣本上；
2. 將弱分類器聯(lián)合起來，使用加權(quán)的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。
Ada boost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細分析了Ada boost算法錯誤率的上界，以及為了使強分類器達到錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與Boosting算法不同的是，Ada boost算法不需要預先知道弱學習算法學習正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。
Ada boost算法中不同的訓練集是通過調(diào)整每個樣本對應的權(quán)重來實現(xiàn)的。開始時，每個樣本對應的權(quán)重是相同的，即其中n為樣本個數(shù)，在此樣本分布下訓練出一弱分類器。對于分類錯誤的樣本，加大其對應的權(quán)重；而對于分類正確的樣本，降低其權(quán)重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進行訓練，得到弱分類器。依次類推，經(jīng)過T次循環(huán)，得到T個弱分類器，把這T個弱分類器按一定的權(quán)重疊加起來，得到最終想要的強分類器。
Ada boost算法的具體步驟如下：
1.給定訓練樣本集，其中分別對應于正例樣本和負例樣本；為訓練的最大循環(huán)次數(shù)；
2.初始化樣本權(quán)重，即為訓練樣本的初始概率分布；
3.第一次迭代：
(1) 訓練樣本的概率分布下，訓練弱分類器；
(2) 計算弱分類器的錯誤率；
(3) 選?。?
(4) 更新樣本權(quán)重；
(5) 最終得到的強分類器。
八、kNN: k-nearest neighbor classification 最近鄰分類算法
K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。
KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值，如權(quán)值與距離成正比。
該算法在分類時主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
九、Naive Bayes？ 樸素貝葉斯算法
在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型和樸素貝葉斯模型(Naive Bayesian Model，NBC)。樸素貝葉斯模型發(fā)源于古典數(shù)學理論，有著堅實的數(shù)學基礎以及穩(wěn)定的分類效率。同時，NBC模型所需估計的參數(shù)較少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率，但實際上并非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數(shù)比較多或者屬性之間相關(guān)性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時，NBC模型的性能最為良好。
十、CART: 分類與回歸樹算法
分類與回歸樹算法（CART，Classification and Regression Trees）是分類數(shù)據(jù)挖掘算法的一種，有兩個關(guān)鍵的思想：第一個是關(guān)于遞歸地劃分自變量空間的想法；第二個想法是用驗證數(shù)據(jù)進行剪枝。
讓我們用變量y表示因變量（分類變量），用x 1，x 2，x 3，...，x p表示自變量。通過遞歸的方式把關(guān)于變量x的p維空間劃分為不重疊的矩形。這個劃分是以遞歸方式完成的。首先，一個自變量被選擇，比如x i和x i的一個值s i，比方說選擇s i把p維空間為兩部分：一部分是p維的超矩形，其中包含的點都滿足x i≤s i，另一個p維超矩形包含所有的點滿足x i>s i。接著，這兩部分中的一個部分通過選擇一個變量和該變量的劃分值以相似的方式被劃分。這導致了三個矩形區(qū)域（從這里往后我們把超矩形都說成矩形）。隨著這個過程的持續(xù)，我們得到的矩形越來越小。這個想法是把整個x空間劃分為矩形，其中的每個小矩形都盡可能是同構(gòu)的或“純”的?！凹儭钡囊馑际牵ň匦危┧狞c都屬于同一類。我們認為包含的點都只屬于一個類（當然，這不總是可能的，因為經(jīng)常存在一些屬于不同類的點，但這些點的自變量有完全相同的值）。
分類與回歸樹CART描述給定預測向量值X后，變量Y條件分布的一個靈活的方法。該模型使用了二叉樹將預測空間遞歸劃分為若干子集，Y在這些子集的分布是連續(xù)均勻的。樹中的葉節(jié)點對應著劃分的不同區(qū)域，劃分是由與每個內(nèi)部節(jié)點相關(guān)的分支規(guī)則確定的。通過從樹根到葉節(jié)點移動，一個預測樣本被賦予一個惟一的葉節(jié)點，Y在該節(jié)點上的條件分布也被確定。CART模型最旱由Breman等人提出并己在統(tǒng)計學領域普遍應用。
剪枝是決策樹停止分支的方法之一，分為預先剪枝和后剪枝兩種。
預先剪枝是在樹的生長過程中設定一個指標，當達到該指標時就停止生長，這樣做容易產(chǎn)生“視界局限”，就是一旦停止分支，使得節(jié)點N成為葉節(jié)點，就斷絕了其后繼節(jié)點進行“好”的分支操作的任何可能性。不嚴格的說這些已停止的分支會誤導學習算法，導致產(chǎn)生的樹不純度降差最大的地方過分靠近根節(jié)點。
后剪枝中樹首先要充分生長，直到葉節(jié)點都有最小的不純度值為止，因而可以克服“視界局限”。然后對所有相鄰的成對葉節(jié)點考慮是否消去它們，如果消去能引起令人滿意的不純度增長，那么執(zhí)行消去，并令它們的公共父節(jié)點成為新的葉節(jié)點。這種“合并”葉節(jié)點的做法和節(jié)點分支的過程恰好相反，經(jīng)過剪枝后葉節(jié)點常常會分布在很寬的層次上，樹也變得非平衡。后剪枝技術(shù)的優(yōu)點是克服了“視界局限”效應，而且無需保留部分樣本用于交叉驗證，所以可以充分利用全部訓練集的信息。但后剪枝的計算量比預剪枝方法大得多，特別是在大樣本集中，不過對于小樣本的情況，后剪枝方法還是優(yōu)于預剪枝方法的。