機器學習與數據挖掘中的十大經典算法數年前，有人動議在機器學習與數據挖掘領域中找出十大算法，即建立該領域算法的一個top10。后在該領域選出部分專家學者，經他們提名、匯總和篩選，在分類，聚類，圖挖掘，關聯分析等領域共選出18個算法。對這18個算法在更廣泛的領域內，一人一票，最終得出了其中的10個作為最后的算法。應該說，受時間、經驗、領域和參選人數等諸多限制，入選的十大算法，不一定個個都是最優秀的;受條件所限沒有入選的有些算法，也不能說是不好的。下面列出這十大算法，供參考。一、分類決策樹算法C4.5C4.5，是機器學習算法中的一個分類決策樹算法，它是決策樹(決策樹，就是做決策的節點間的組織方式像一棵倒栽樹)核心算法ID3的改進算法，所以基本上了解了一半決策樹構造方法就能構造它。決策樹構造方法其實就是每次選擇一個好的特征以及分裂點作為當前節點的分類條件。C4.5相比于ID3改進的地方有：1、用信息增益率選擇屬性。ID3選擇屬性用的是子樹的信息增益，這里可以用很多方法來定義信息，ID3使用的是熵，一種不純度度量準則，也就是熵的變化值，而C4.5用的是信息增益率。區別就在于一個是信息增益，一個是信息增益率。2、在樹構造過程中進行剪枝，在構造決策樹的時候，那些掛著幾個元素的節點，不考慮最好，不然容易導致過擬。3、能對非離散數據和不完整數據進行處理。二、K平均算法K平均算法(k-meansalgorithm)是一個聚類算法，把n個分類對象根據它們的屬性分為k類(k<n)。它與處理混合正態分布的最大期望算法相似，因為他們都試圖找到數據中的自然聚類中心。它假設對象屬性來自于空間向量，并且目標是使各個群組內部的均方誤差總和最小。<p="">近似的k平均算法已經被設計用于原始數據子集的計算。從算法的表現上來說，它并不保證一定得到全局最優解，最終解的質量很大程度上取決于初始化的分組。由于該算法的速度很快，因此常用的一種方法是多次運行k平均算法，選擇最優解。算法缺點是，分組的數目k是一個輸入參數，不合適的k可能返回較差的結果。另外，算法還假設均方誤差是計算群組分散度的最佳參數。三、支持向量機算法支持向量機(SupportVectorMachine)算法，簡記為SVM，是一種監督式學習的方法，廣泛用于統計分類以及回歸分析中。支持向量機屬于一般化線性分類器。這類分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。Vapnik等人在多年研究統計學習理論基礎上對線性分類器提出了另一種設計最佳準則。其原理也從線性可分說起，然后擴展到線性不可分的情況，甚至擴展到使用非線性函數中去。支持向量機是一種有很深理論背景的一種新方法。SVM的主要思想可以概括為兩點：(1)它是針對線性可分情況進行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進行線性分析成為可能;(2)它基于結構風險最小化理論之上，在特征空間中建構最優分割超平面，使得學習器得到全局最優化，并且在整個樣本空間的期望風險以某個概率滿足一定上界。四、TheApriorialgorithmApriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法，核心是基于兩階段頻集思想的遞推算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。Apriori演算法所使用的前置統計量包括：·最大規則物件數：規則中物件組所包含的最大物件數量;·最小支援：規則中物件或是物件組必頇符合的最低案例數;·最小信心水準：計算規則所必須符合的最低信心水準門檻。該算法的基本思想是：首先找出所有的頻集，這些頻集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這里采用的是中規則的定義。一旦這些規則被生成，那么只有那些大于用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推方法?？赡墚a生大量的候選集，以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點。五、最大期望(EM)算法在統計計算中，最大期望(EM，Expectation–Maximization)算法是在概率模型中尋找參數最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量。最大期望經常用在機器學習和計算機視覺的數據集聚領域。最大期望算法經過兩個步驟交替進行計算，第一步是計算期望(E)，也就是將隱藏變量象能夠觀測到的一樣包含在內從而計算最大似然的期望值;第二步是最大化(M)，也就是最大化在E步上找到的最大似然的期望值從而計算參數的最大似然估計。M步上找到的參數然后用于另外一個E步計算，這個過程不斷交替進行。六、PageRank算法PageRank是Google算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里·佩奇(LarryPage)。因此，PageRank里的page不是網頁，而是佩奇，即這個方法是以佩奇來命名的。PageRank根據網站的外部鏈接和內部鏈接的數量和質量，衡量網站的價值。PageRank背后的概念是每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。這就是所謂的“鏈接流行度”——衡量多少人愿意將他們的網站和你的網站掛鉤。PageRank這個概念引自學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。七、AdaBoost迭代算法Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構成一個更強的最終分類器(強分類器)。其算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。使用Adaboost分類器可以排除一些不必要的訓練數據特徵，并將關鍵放在關鍵的訓練數據上面。目前，對Adaboost算法的研究以及應用大多集中于分類問題，同時近年也出現了一些在回歸問題上的應用。就其應用Adaboost系列主要解決兩類問題：多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。它用全部的訓練樣本進行學習。該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓練，可以提高對數據的分類能力。整個過程如下所示：1.先通過對N個訓練樣本的學習得到第一個弱分類器;2.將分錯的樣本和其他的新數據一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器;3.將和都分錯了的樣本加上其他的新樣本構成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器;4.最終經過提升的強分類器，即某個數據被分為哪一類要通過多數表決。對于Adaboosting算法，存在兩個問題：1.如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行;2.如何將訓練得到的各個弱分類器聯合起來形成強分類器。針對以上兩個問題，Adaboost算法進行了調整：1.使用加權后選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上;2.將弱分類器聯合起來，使用加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。Adaboost算法是Freund和Schapire根據在線分配算法提出的，他們詳細分析了Adaboost算法錯誤率的上界，以及為了使強分類器達到錯誤率，算法所需要的最多迭代次數等相關問題。與Boosting算法不同的是，Adaboost算法不需要預先知道弱學習算法學習正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。Adaboost算法中不同的訓練集是通過調整每個樣本對應的權重來實現的。開始時，每個樣本對應的權重是相同的，即其中n為樣本個數，在此樣本分布下訓練出一弱分類器。對于分類錯誤的樣本，加大其對應的權重;而對于分類正確的樣本，降低其權重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進行訓練，得到弱分類器。依次類推，經過T次循環，得到T個弱分類器，把這T個弱分類器按一定的權重疊加起來，得到最終想要的強分類器。Adaboost算法的具體步驟如下：1.給定訓練樣本集，其中分別對應于正例樣本和負例樣本;為訓練的最大循環次數;2.初始化樣本權重，即為訓練樣本的初始概率分布;3.第一次迭代：(1)訓練樣本的概率分布下，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取;(4)更新樣本權重;(5)最終得到的強分類器。八、kNN:k-nearestneighborclassification最近鄰分類算法K最近鄰(k-NearestNeighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值，如權值與距離成正比。該算法在分類時主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。因此可以采用權值的方法(和該樣本距離小的鄰居權值大)來改進。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。九、NaiveBayes樸素貝葉斯算法在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型和樸素貝葉斯模型(NaiveBayesianModel，NBC)。樸素貝葉斯模型發源于古典數學理論，有著堅實的數學基礎以及穩定的分類效率。同時，NBC模型所需估計的參數較少，對缺失數據不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率，但實際上并非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。十、CART:分類與回歸樹算法分類與回歸樹算法(CART，ClassificationandRegressionTrees)是分類數據挖掘算法的一種，有兩個關鍵的思想：第一個是關于遞歸地劃分自變量空間的想法;第二個想法是用驗證數據進行剪枝。讓我們用變量y表示因變量(分類變量)，用x1，x2，x3，…，xp表示自變量。通過遞歸的方式把關于變量x的p維空間劃分為不重疊的矩形。這個劃分是以遞歸方式完成的。首先，一個自變量被選擇，比如xi和xi的一個值si，比方說選擇si把p維空間為兩部分：一部分是p維的超矩形，其中包含的點都滿足xi≤si，另一個p維超矩形包含所有的點滿足xi>si。接著，這兩部分中的一個部分通過選擇一個變量和該變量的劃分值以相似的方式被劃分。這導致了三個矩形區域(從這里往后我們把超矩形都說成矩形)。隨著這個過程的持續，我們得到的矩形越來越小。這個想法是把整個x空間劃分為矩形，其中的每個小矩形都盡可能是同構的或“純”的?！凹儭钡囊馑际?矩形)所包含的點都屬于同一類。我們認為包含的點都只屬于一個類(當然，這不總是可能的，因為經常存在一些屬于不同類的點，但這些點的自變量有完全相同的值)。分類與回歸樹CART描述給定預測向量值X后，變量Y條件分布的一個靈活的方法。該模型使用了二叉樹將預測空間遞歸劃分為若干子集，Y在這些子集的分布是連續均勻的。樹中的葉節點對應著劃分的不同區域，劃分是由與每個內部節點相關的分支規則確定的。通過從樹根到葉節點移動，一個預測樣本被賦予一個惟一的葉節點，Y在該節點上的條件分布也被確定。CART模型最旱由Breman等人提出并己在統計學領域普遍應用。剪枝是決策樹停止分支的方法之一，分為預先剪枝和后剪枝兩種。預先剪枝是在樹的生長過程中設定一個指標，當達到該指標時就停止生長，這樣做容易產生“視界局限”，就是一旦停止分支，使得節點N成為葉節點，就斷絕了其后繼節點進行“好”的分支操作的任何可能性。不嚴格的說這些已停止的分支會誤導學習算法，