數據挖掘算法:創建數據挖掘模型的算法-中文百科頻道

簡介

國際權威的學術組織the IEEE International Conference on Data Mining(ICDM)評選出了數據挖掘領域的十大經典算法：C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,Naive Bayes,and CART.

算法分類

C4.5

C4.5就是一個決策樹算法，它是決策樹（決策樹也就是做決策的節點間像一棵樹一樣的組織方式，其實是一個倒樹）核心算法ID3的改進算法，所以基本上了解了一半決策樹構造方法就能構造它。決策樹構造方法其實就是每次選擇一個好的特征以及分裂點作為當前節點的分類條件。C4.5比ID3改進的地方時：

CART

CART也是一種決策樹算法！相對于上着有條件實現一個節點下面有多個子樹的多元分類，CART隻是分類兩個子樹，這樣實現起來稍稍簡便些。所以說CART算法生成的決策樹是結構簡潔的二叉樹。

KNN(KNearestNeighbours)

這個很簡單，就是看你周圍的K個人（樣本）中哪個類别的人占的多，哪個多，那我就是多的那個。實現起來就是對每個訓練樣本都計算與其相似度，是Top-K個訓練樣本出來，看這K個樣本中哪個類别的多些，誰多跟誰。

NaiveBayes

(樸素貝葉斯NB)

NB認為各個特征是獨立的，誰也不關誰的事。所以一個樣本（特征值的集合，比如“數據結構”出現2詞，“文件”出現1詞），可以通過對其所有出現特征在給定類别的概率相乘。比如“數據結構”出現在類1的概率為0.5，“文件”出現在類1的概率為0.3，則可認為其屬于類1的概率為0.5*0.5*0.3。

SupportVectorMachine

(支持向量機SVM)

SVM就是想找一個分類得最”好”的分類線/分類面（最近的一些兩類樣本到這個”線”的距離最遠）。這個沒具體實現過，上次聽課，那位老師自稱自己實現了SVM，敬佩其鑽研精神。常用的工具包是LibSVM、SVMLight、MySVM。

EM(期望最大化)

這個我認為就是假設數據時由幾個高斯分布組成的，所以最後就是要求幾個高斯分布的參數。通過先假設幾個值，然後通過反複叠代，以期望得到最好的拟合。

Apriori

這個是做關聯規則用的。不知道為什麼，一提高關聯規則我就想到購物籃數據。這個沒實現過，不過也還要理解，它就是通過支持度和置信度兩個量來工作，不過對于Apriori，它通過頻繁項集的一些規律（頻繁項集的子集必定是頻繁項集等等啦）來減少計算複雜度。

FP-Tree

(Mining frequent patterns without candidate generation)

PageRank

大名鼎鼎的PageRank大家應該都知道（Google靠此專利發家，其實也不能說發家啦!）。對于這個算法我的理解就是：如果我指向你（網頁間的連接）則表示我承認你，則在計算你的重要性的時候可以加上我的一部分重要性（到底多少，要看我自己有多少和我共承認多少個人）。通過反複這樣來，可以求的一個穩定的衡量各個人（網頁）重要性的值。不過這裡必須要做些限制（一個人的開始默認重要性都是1），不然那些值會越來越大越來越大。

HITS

HITS也是一個連接分析算法，它是由IBM首先提出的。在HITS，每個節點（網頁）都有一個重要度和權威度（Hubs and authorities,我也忘了具體的翻譯是什麼了）。通過反複通過權威度來求重要度，通過重要度來求權威度得到最後的權威度和重要度。

K-Means

K-Means是一種最經典也是使用最廣泛的聚類方法，時至今日任然有很多基于其的改進模型提出。K-Means的思想很簡單，對于一個聚類任務（你需要指明聚成幾個類，當然按照自然想法來說不應該需要指明類數，這個問題也是當前聚類任務的一個值得研究的課題），首先随機選擇K個簇中心，然後反複計算下面的過程直到所有簇中心不改變（簇集合不改變）為止：步驟1：對于每個對象，計算其與每個簇中心的相似度，把其歸入與其最相似的那個簇中。

步驟2：更新簇中心，新的簇中心通過計算所有屬于該簇的對象的平均值得到。

BIRCH

BIRCH也是一種聚類算法，其全稱是Balanced Iterative Reducing and Clustering using Hierarchies。BIRCH也是隻是看了理論沒具體實現過。是一個綜合的層次聚類特征(Clustering Feature,CF)和聚類特征樹(CF Tree)兩個概念，用于概括聚類描述。聚類特征樹概括了聚類的有用信息，并且占用空間較元數據集合小得多，可以存放在内存中，從而可以提高算法在大型數據集合上的聚類速度及可伸縮性。

BIRCH算法包括以下兩個階段：

1）掃描數據庫，建立動态的一棵存放在内存的CF Tree。如果内存不夠，則增大阈值，在原樹基礎上構造一棵較小的樹。

2）對葉節點進一步利用一個全局性的聚類算法，改進聚類質量。

由于CF Tree的葉節點代表的聚類可能不是自然的聚類結果，原因是給定的阈值限制了簇的大小，并且數據的輸入順序也會影響到聚類結果。因此需要對葉節點進一步利用一個全局性的聚類算法，改進聚類質量。

daBoost

AdaBoost做分類的一般知道，它是一種boosting方法。這個不能說是一種算法，應該是一種方法，因為它可以建立在任何一種分類算法上，可以是決策樹，NB，SVM等。

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