機器學習與數據挖掘中的十大經典演算法

機器學習與數據挖掘中的十大經典演算法

一、分類決策樹演算法C4.5

C4.5，是機器學習演算法中的一個分類決策樹演算法，它是決策樹(決策樹，就是做決策的節點間的組織方式像一棵倒栽樹)核心演算法ID3的改進演算法，所以基本上了解了一半決策樹構造方法就能構造它。決策樹構造方法其實就是每次選擇一個好的特徵以及分裂點作為當前節點的分類條件。

C4.5相比於ID3改進的地方有：

1、用信息增益率選擇屬性。

ID3選擇屬性用的是子樹的信息增益，這裡可以用很多方法來定義信息，ID3使用的是熵，一種不純度度量準則，也就是熵的變化值，而C4.5用的是信息增益率。區別就在於一個是信息增益，一個是信息增益率。

2、 在樹構造過程中進行剪枝，在構造決策樹的時候，那些掛著幾個元素的節點，不考慮最好，不然容易導致過擬。

3、能對非離散數據和不完整數據進行處理。

二、 K平均演算法

K平均演算法（k-means algorithm）是一個聚類演算法，把n個分類對象根據它們的屬性分為k類（k<n）。它與處理混合正態分布的最大期望演算法相似，因為他們都試圖找到數據中的自然聚類中心。它假設對象屬性來自於空間向量，並且目標是使各個群組內部的均方誤差總和最小。

近似的k平均演算法已經被設計用於原始數據子集的計算。

從演算法的表現上來說，它並不保證一定得到全局最優解，最終解的質量很大程度上取決於初始化的分組。由於該演算法的速度很快，因此常用的一種方法是多次運行k平均演算法，選擇最優解。

演算法缺點是，分組的數目k是一個輸入參數，不合適的k可能返回較差的結果。另外，演算法還假設均方誤差是計算群組分散度的最佳參數。

三、支持向量機演算法

支持向量機(Support Vector Machine)演算法，簡記為SVM，是一種監督式學習的方法，廣泛用於統計分類以及回歸分析中。

支持向量機屬於一般化線性分類器。這類分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。

Vapnik等人在多年研究統計學習理論基礎上對線性分類器提出了另一種設計最佳準則。其原理也從線性可分說起，然後擴展到線性不可分的情況，甚至擴展到使用非線性函數中去。支持向量機是一種有很深理論背景的一種新方法。

SVM的主要思想可以概括為兩點：(1)它是針對線性可分情況進行分析，對於線性不可分的情況，通過使用非線性映射演算法將低維輸入空間線性不可分的樣本轉化為高維特徵空間使其線性可分，從而使得高維特徵空間採用線性演算法對樣本的非線性特徵進行線性分析成為可能；(2)它基於結構風險最小化理論之上，在特徵空間中建構最優分割超平面，使得學習器得到全局最優化，並且在整個樣本空間的期望風險以某個概率滿足一定上界。

四、The Apriori algorithm

Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法，核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這裡，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。

Apriori演演算法所使用的前置統計量包括：

?最大規則物件數：規則中物件組所包含的最大物件數量；

?最小支援：規則中物件或是物件組必頇符合的最低案例數；

?最小信心水準：計算規則所必須符合的最低信心水準門檻。

該演算法的基本思想是：首先找出所有的頻集，這些頻集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這裡採用的是中規則的定義。一旦這些規則被生成，那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推方法。

可能產生大量的候選集，以及可能需要重複掃描資料庫，是Apriori演算法的兩大缺點。

五、最大期望(EM)演算法

在統計計算中，最大期望（EM，Expectation–Maximization）演算法是在概率模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數。最大期望經常用在機器學習和計算機視覺的數據集聚領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），也就是將隱藏變數象能夠觀測到的一樣包含在內從而計算最大似然的期望值；第二步是最大化（M），也就是最大化在E步上找到的最大似然的期望值從而計算參數的最大似然估計。M步上找到的參數然後用於另外一個E步計算，這個過程不斷交替進行。

六、Page Rank演算法

Page Rank是Google演算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里?佩奇(Larry Page)。因此，Page Rank里的page不是網頁，而是佩奇，即這個方法是以佩奇來命名的。Page Rank根據網站的外部鏈接和內部鏈接的數量和質量，衡量網站的價值。Page Rank背後的概念是每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。這就是所謂的「鏈接流行度」——衡量多少人願意將他們的網站和你的網站掛鉤。Page Rank這個概念引自學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。

七、Ada Boost 迭代演算法

Ada boost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器(強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。使用Ada boost分類器可以排除一些不必要的訓練數據特徵，並將關鍵放在關鍵的訓練數據上面。

目前，對Ada boost演算法的研究以及應用大多集中於分類問題，同時近年也出現了一些在回歸問題上的應用。就其應用Ada boost系列主要解決兩類問題：多類單標籤問題、多類多標籤問題、大類單標籤問題，回歸問題。它用全部的訓練樣本進行學習。

該演算法其實是一個簡單的弱分類演算法提升過程，這個過程通過不斷的訓練，可以提高對數據的分類能力。整個過程如下所示：

1. 先通過對N個訓練樣本的學習得到第一個弱分類器；

2. 將分錯的樣本和其他的新數據一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器；

3. 將和都分錯了的樣本加上其他的新樣本構成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器；

4. 最終經過提升的強分類器，即某個數據被分為哪一類要通過多數表決。

對於Ada boosting演算法，存在兩個問題：

1. 如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行；

2. 如何將訓練得到的各個弱分類器聯合起來形成強分類器。

針對以上兩個問題，Ada boost演算法進行了調整：

1. 使用加權後選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上；

2. 將弱分類器聯合起來，使用加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。

Ada boost演算法是Freund和Schapire根據在線分配演算法提出的，他們詳細分析了Ada boost演算法錯誤率的上界，以及為了使強分類器達到錯誤率，演算法所需要的最多迭代次數等相關問題。與Boosting演算法不同的是，Ada boost演算法不需要預先知道弱學習演算法學習正確率的下限即弱分類器的誤差，並且最後得到的強分類器的分類精度依賴於所有弱分類器的分類精度，這樣可以深入挖掘弱分類器演算法的能力。

Ada boost演算法中不同的訓練集是通過調整每個樣本對應的權重來實現的。開始時，每個樣本對應的權重是相同的，即其中n為樣本個數，在此樣本分布下訓練出一弱分類器。對於分類錯誤的樣本，加大其對應的權重；而對於分類正確的樣本，降低其權重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進行訓練，得到弱分類器。依次類推，經過T次循環，得到T個弱分類器，把這T個弱分類器按一定的權重疊加起來，得到最終想要的強分類器。

Ada boost演算法的具體步驟如下：

1.給定訓練樣本集，其中分別對應於正例樣本和負例樣本；為訓練的最大循環次數；

2.初始化樣本權重，即為訓練樣本的初始概率分布；

3.第一次迭代：

(1) 訓練樣本的概率分布下，訓練弱分類器；

(2) 計算弱分類器的錯誤率；

(3) 選取；

(4) 更新樣本權重；

(5) 最終得到的強分類器。

八、kNN: k-nearest neighbor classification 最近鄰分類演算法

K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值，如權值與距離成正比。

該演算法在分類時主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。因此可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

九、Naive Bayes 樸素貝葉斯演算法

在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型和樸素貝葉斯模型(Naive Bayesian Model，NBC)。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎以及穩定的分類效率。同時，NBC模型所需估計的參數較少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率，但實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。

十、CART: 分類與回歸樹演算法

分類與回歸樹演算法（CART，Classification and Regression Trees）是分類數據挖掘演算法的一種，有兩個關鍵的思想：第一個是關於遞歸地劃分自變數空間的想法；第二個想法是用驗證數據進行剪枝。

讓我們用變數y表示因變數（分類變數），用x 1 ，x 2 ，x 3 ，…，x p 表示自變數。通過遞歸的方式把關於變數x的p維空間劃分為不重疊的矩形。這個劃分是以遞歸方式完成的。首先，一個自變數被選擇，比如x i 和x i 的一個值s i ，比方說選擇s i 把p維空間為兩部分：一部分是p維的超矩形，其中包含的點都滿足x i ≤s i ，另一個p維超矩形包含所有的點滿足x i >s i 。接著，這兩部分中的一個部分通過選擇一個變數和該變數的劃分值以相似的方式被劃分。這導致了三個矩形區域（從這裡往後我們把超矩形都說成矩形）。隨著這個過程的持續，我們得到的矩形越來越小。這個想法是把整個x空間劃分為矩形，其中的每個小矩形都儘可能是同構的或「純」的。「純」的意思是（矩形）所包含的點都屬於同一類。我們認為包含的點都只屬於一個類（當然，這不總是可能的，因為經常存在一些屬於不同類的點，但這些點的自變數有完全相同的值）。

分類與回歸樹CART描述給定預測向量值X後，變數Y條件分布的一個靈活的方法。該模型使用了二叉樹將預測空間遞歸劃分為若干子集，Y在這些子集的分布是連續均勻的。樹中的葉節點對應著劃分的不同區域，劃分是由與每個內部節點相關的分支規則確定的。通過從樹根到葉節點移動，一個預測樣本被賦予一個惟一的葉節點，Y在該節點上的條件分布也被確定。CART模型最旱由Breman等人提出並己在統計學領域普遍應用。

剪枝是決策樹停止分支的方法之一，分為預先剪枝和後剪枝兩種。

預先剪枝是在樹的生長過程中設定一個指標，當達到該指標時就停止生長，這樣做容易產生「視界局限」，就是一旦停止分支，使得節點N成為葉節點，就斷絕了其後繼節點進行「好」的分支操作的任何可能性。不嚴格的說這些已停止的分支會誤導學習演算法，導致產生的樹不純度降差最大的地方過分靠近根節點。

後剪枝中樹首先要充分生長，直到葉節點都有最小的不純度值為止，因而可以克服「視界局限」。然後對所有相鄰的成對葉節點考慮是否消去它們，如果消去能引起令人滿意的不純度增長，那麼執行消去，並令它們的公共父節點成為新的葉節點。這種「合併」葉節點的做法和節點分支的過程恰好相反，經過剪枝後葉節點常常會分布在很寬的層次上，樹也變得非平衡。後剪枝技術的優點是克服了「視界局限」效應，而且無需保留部分樣本用於交叉驗證，所以可以充分利用全部訓練集的信息。但後剪枝的計算量比預剪枝方法大得多，特別是在大樣本集中，不過對於小樣本的情況，後剪枝方法還是優於預剪枝方法的。
推薦閱讀：