數(shù)據(jù)挖掘常用的十大算法
數(shù)據(jù)挖掘（英語：Data mining），又譯為資料探勘、數(shù)據(jù)采礦。它是數(shù)據(jù)庫知識發(fā)現(xiàn)（英語：Knowledge-Discovery in Databases，簡稱：KDD）中的一個(gè)步驟。數(shù)據(jù)挖掘一般是指從大量的數(shù)據(jù)中通過算法搜索隱藏于其中信息的過程。數(shù)據(jù)挖掘通常與計(jì)算機(jī)科學(xué)有關(guān)，并通過統(tǒng)計(jì)、在線分析處理、情報(bào)檢索、機(jī)器學(xué)習(xí)、專家系統(tǒng)（依靠過去的經(jīng)驗(yàn)法則）和模式識別等諸多方法來實(shí)現(xiàn)上述目標(biāo)。
數(shù)據(jù)挖掘經(jīng)典算法 1. C4.5：是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法，其核心算法是ID3算法。
解析
C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法，其核心算法是ID3 算法。 C4.5算法繼承了ID3算法的長處。并在下面幾方面對ID3算法進(jìn)行了改進(jìn)：
1） 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。
2） 在樹構(gòu)造過程中進(jìn)行剪枝；
3） 可以完畢對連續(xù)屬性的離散化處理；
4） 可以對不完整數(shù)據(jù)進(jìn)行處理。
C4.5算法有例如以下長處：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過程中，須要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。
1、機(jī)器學(xué)習(xí)中。決策樹是一個(gè)預(yù)測模型。他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每一個(gè)節(jié)點(diǎn)表示某個(gè)對象，而每一個(gè)分叉路徑則代表的某個(gè)可能的屬性值，而每一個(gè)葉結(jié)點(diǎn)則
相應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出。若欲有復(fù)數(shù)輸出，能夠建立獨(dú)立的決策樹以處理不同輸出。
2、 從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí)， 通俗說就是決策樹。
3、決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個(gè)普通的方法。在這里，每一個(gè)決策樹都表述了一種樹型結(jié)構(gòu)，他由他的分支來對該類型的對象依靠屬性進(jìn)行分類。每一個(gè)決策樹能夠依靠對源數(shù)據(jù)庫的切割
進(jìn)行數(shù)據(jù)測試。
這個(gè)過程能夠遞歸式的對樹進(jìn)行修剪。
當(dāng)不能再進(jìn)行切割或一個(gè)單獨(dú)的類能夠被應(yīng)用于某一分支時(shí)。遞歸過程就完畢了。
另外。隨機(jī)森林分類器將很多決策樹結(jié)合起來
以提升分類的正確率。
2. K-means算法：是一種聚類算法。術(shù)語“k-means”最早是由James MacQueen在1967年提出的。這一觀點(diǎn)能夠追溯到1957年 Hugo Steinhaus所提出的想法。1957年。斯圖亞特·勞埃德最先提出這一標(biāo)準(zhǔn)算法，當(dāng)初是作為一門應(yīng)用于脈碼調(diào)制的技術(shù)，直到1982年，這一算法才在貝爾實(shí)驗(yàn)室被正式提出。1965年。 E.W.Forgy發(fā)表了一個(gè)本質(zhì)上是同樣的方法。1975年和1979年。HarTIgan和Wong分別提出了一個(gè)更高效的版本號。
算法描寫敘述
輸入：簇的數(shù)目k；包括n個(gè)對象的數(shù)據(jù)集D。
輸出：k個(gè)簇的集合。
方法：
從D中隨意選擇k個(gè)對象作為初始簇中心；
repeat;
依據(jù)簇中對象的均值。將每一個(gè)對象指派到最相似的簇；
更新簇均值。即計(jì)算每一個(gè)簇中對象的均值；
計(jì)算準(zhǔn)則函數(shù)；
unTIl準(zhǔn)則函數(shù)不再發(fā)生變化。
3. SVM：一種監(jiān)督式學(xué)習(xí)的方法
廣泛運(yùn)用于統(tǒng)計(jì)分類以及回歸分析中支持向量機(jī)，英文為Support Vector Machine，簡稱SV機(jī)（論文中一般簡稱SVM）。它是一
種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。
支持向量機(jī)屬于一般化線性分類器。他們也可以覺得是提克洛夫規(guī)范化（TIkhonov RegularizaTIon）方法的一個(gè)特例。這族分類器的特點(diǎn)是他們可以同一時(shí)候最小化經(jīng)驗(yàn)誤差與最大化
幾何邊緣區(qū)。因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然預(yù)計(jì)的算法。當(dāng)中概率模型依賴于無
法觀測的隱藏變量（Latent Variabl）。
最大期望經(jīng)經(jīng)常使用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)集聚（Data Clustering）領(lǐng)域。
最大期望算法經(jīng)過兩個(gè)步驟交替進(jìn)行計(jì)算：
第一步是計(jì)算期望（E），也就是將隱藏變量象可以觀測到的一樣包括在內(nèi)從而計(jì)算最大似然的期望值；
另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值從而計(jì)算參數(shù)的最大似然預(yù)計(jì)。
M 步上找到的參數(shù)然后用于另外一個(gè) E 步計(jì)算，這個(gè)過程不斷交替進(jìn)行。
Vapnik等人在多年研究統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上對線性分類器提出了還有一種設(shè)計(jì)最佳準(zhǔn)則。其原理也從線性可分說起，然后擴(kuò)展到線性不可分的情況。
甚至擴(kuò)展到使用非線性函數(shù)中去，這
種分類器被稱為支持向量機(jī)（Support Vector Machine，簡稱SVM）。支持向量機(jī)的提出有非常深的理論背景。支持向量機(jī)方法是在近年來提出的一種新方法。
SVM 的主要思想能夠概括為兩點(diǎn)：
（1） 它是針對線性可分情況進(jìn)行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使
其線性可分，從而使得高維特征空間採用線性算法對樣本的非線性特征進(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)，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)
在設(shè)計(jì)時(shí)。須要用到條件極值問題的求解。因此需用拉格朗日乘子理論。但對多數(shù)人來說。曾經(jīng)學(xué)到的或經(jīng)常使用的是約束條件為等式表示的方式。但在此要用到以不等式作為必須滿足的條件，此時(shí)僅僅要了解拉格朗日理論的有關(guān)結(jié)論即可。
4. Apriori ：是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori算法是種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。它的核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。
在這里，全部支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集（簡稱頻集），也常稱為最大項(xiàng)目集。
在Apriori算法中，尋找最大項(xiàng)目集（頻繁項(xiàng)集）的基本思想是：算法須要對數(shù)據(jù)集進(jìn)行多步處理。第一步，簡單統(tǒng)計(jì)全部含一個(gè)元素項(xiàng)目集出現(xiàn)的頻數(shù)，并找出那些不小于最小支持度的項(xiàng)目集，即一維最大項(xiàng)目集。從第二步開始循環(huán)處理直到再沒有最大項(xiàng)目集生成。循環(huán)過程是：第k步中，依據(jù)第k-1步生成的（k-1）維最大項(xiàng)目集產(chǎn)生k維侯選項(xiàng)目集。然后對數(shù)據(jù)庫進(jìn)行搜索，得到侯選項(xiàng)目集的項(xiàng)集支持度。與最小支持度進(jìn)行比較，從而找到k維最大項(xiàng)目集。
從算法的執(zhí)行過程。我們能夠看出該Apriori算法的長處：簡單、易理解、數(shù)據(jù)要求低。然而我們也能夠看到Apriori算法的缺點(diǎn)：
（1）在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素;
（2）每次計(jì)算項(xiàng)集的支持度時(shí)，都對數(shù)據(jù)庫D中的所有記錄進(jìn)行了一遍掃描比較。假設(shè)是一個(gè)大型的數(shù)據(jù)庫的話，這樣的掃描比較會大大添加計(jì)算機(jī)系統(tǒng)的I/O開銷。而這樣的代價(jià)是隨著數(shù)據(jù)庫的記錄的添加呈現(xiàn)出幾何級數(shù)的添加。
因此人們開始尋求更好性能的算法。如F-P算法。
5. EM：最大期望值法。最大期望算法（Expectation-maximization algorithm。又譯期望最大化算法）在統(tǒng)計(jì)中被用于尋找，依賴于不可觀察的隱性變量的概率模型中，參數(shù)的最大似然預(yù)計(jì)。
在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率模型中尋找參數(shù)最大似然預(yù)計(jì)或者最大后驗(yàn)預(yù)計(jì)的算法。當(dāng)中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。最大期望經(jīng)經(jīng)常使用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)聚類（Data Clustering）領(lǐng)域。
最大期望算法經(jīng)過兩個(gè)步驟交替進(jìn)行計(jì)算，第一步是計(jì)算期望（E），利用對隱藏變量的現(xiàn)有預(yù)計(jì)值，計(jì)算其最大似然預(yù)計(jì)值；第二步是最大化（M）。最大化在 E 步上求得的最大似然值來計(jì)算參數(shù)的值。M 步上找到的參數(shù)預(yù)計(jì)值被用于下一個(gè) E 步計(jì)算中，這個(gè)過程不斷交替進(jìn)行。
M是一個(gè)在已知部分相關(guān)變量的情況下，預(yù)計(jì)未知變量的迭代技術(shù)。EM的算法流程例如以下：
1. 初始化分布參數(shù)
2. 反復(fù)直到收斂：
E步驟：預(yù)計(jì)未知參數(shù)的期望值，給出當(dāng)前的參數(shù)預(yù)計(jì)。
M步驟：又一次預(yù)計(jì)分布參數(shù)，以使得數(shù)據(jù)的似然性最大，給出未知變量的期望預(yù)計(jì)。
應(yīng)用于缺失值
最大期望過程說明
我們用 表示可以觀察到的不完整的變量值，用 表示無法觀察到的變量值，這樣 和 一起組成了完整的數(shù)據(jù)。
可能是實(shí)際測量丟失的數(shù)據(jù)，也可能是可以簡化問題的隱藏變量，假設(shè)它的值可以知道的話。比如，在混合模型（Mixture Model）中，假設(shè)“產(chǎn)生”樣本的混合元素成分已知的話最大似然公式將變得更加便利（參見以下的樣例）。
6.pagerank：是google算法的重要內(nèi)容。
PageRank。網(wǎng)頁排名，又稱網(wǎng)頁級別、Google左側(cè)排名或佩奇排名，是一種由搜索引擎依據(jù)網(wǎng)頁之間相互的超鏈接計(jì)算的技術(shù)，而作為網(wǎng)頁排名的要素之中的一個(gè)，以Google公司創(chuàng)辦人拉里·佩奇（Larry Page）之姓來命名。Google用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性，在搜索引擎優(yōu)化操作中是常常被用來評估網(wǎng)頁優(yōu)化的成效因素之中的一個(gè)。Google的創(chuàng)始人拉里·佩奇和謝爾蓋·布林于1998年在斯坦福大學(xué)發(fā)明了這項(xiàng)技術(shù)。
PageRank通過網(wǎng)絡(luò)浩瀚的超鏈接關(guān)系來確定一個(gè)頁面的等級。
Google把從A頁面到B頁面的鏈接解釋為A頁面給B頁面投票。Google依據(jù)投票來源（甚至來源的來源，即鏈接到A頁面的頁面）和投票目標(biāo)的等級來決定新的等級。
簡單的說，一個(gè)高等級的頁面能夠使其它低等級頁面的等級提升。
7、Adaboost：是一種迭代算法，其核心思想是針對同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器然后把弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器。AdaBoost。是英文“Adaptive Boosting”（自適應(yīng)增強(qiáng)）的縮寫，是一種機(jī)器學(xué)習(xí)方法。由Yoav Freund和Robert Schapire提出。
AdaBoost方法的自適應(yīng)在于：前一個(gè)分類器分錯(cuò)的樣本會被用來訓(xùn)練下一個(gè)分類器。AdaBoost方法對于噪聲數(shù)據(jù)和異常數(shù)據(jù)非常敏感。但在一些問題中。AdaBoost方法相對于大多數(shù)其他學(xué)習(xí)算法而言。不會非常easy出現(xiàn)過擬合現(xiàn)象。
AdaBoost方法中使用的分類器可能非常弱（比方出現(xiàn)非常大錯(cuò)誤率），但僅僅要它的分類效果比隨機(jī)好一點(diǎn)（比方兩類問題分類錯(cuò)誤率略小于0.5），就行改善終于得到的模型。而錯(cuò)誤率高于隨機(jī)分類器的弱分類器也是實(shí)用的，由于在終于得到的多個(gè)分類器的線性組合中，可以給它們賦予負(fù)系數(shù)，相同也能提升分類效果。
AdaBoost方法是一種迭代算法。在每一輪中增加一個(gè)新的弱分類器，直到達(dá)到某個(gè)預(yù)定的足夠小的錯(cuò)誤率。每個(gè)訓(xùn)練樣本都被賦予一個(gè)權(quán)重。表明它被某個(gè)分類器選入訓(xùn)練集的概率。
假設(shè)某個(gè)樣本點(diǎn)已經(jīng)被準(zhǔn)確地分類，那么在構(gòu)造下一個(gè)訓(xùn)練集中，它被選中的概率就被減少；
相反。假設(shè)某個(gè)樣本點(diǎn)沒有被準(zhǔn)確地分類，那么它的權(quán)重就得到提高。通過這種方式，AdaBoost方法能“聚焦于”那些較難分（更富信息）的樣本上。
在詳細(xì)實(shí)現(xiàn)上，最初令每一個(gè)樣本的權(quán)重都相等，對于第k次迭代操作。我們就依據(jù)這些權(quán)重來選取樣本點(diǎn)，進(jìn)而訓(xùn)練分類器Ck。然后就依據(jù)這個(gè)分類器，來提高被它分錯(cuò)的的樣本的權(quán)重，并減少被正確分類的樣本權(quán)重。
然后，權(quán)重更新過的樣本集被用于訓(xùn)練下一個(gè)分類器Ck［2］。整個(gè)訓(xùn)練過程如此迭代地進(jìn)行下去。
8、KNN：是一個(gè)理論上比較成熟的的方法，也是最簡單的機(jī)器學(xué)習(xí)方法之一。1、K近期鄰（k-Nearest Neighbor。KNN）分類算法。是一個(gè)理論上比較成熟的方法。也是最簡單的機(jī)器學(xué)習(xí)算法之中的一個(gè)。該方法的思路是：假設(shè)一個(gè)樣本在特征空間中的k個(gè)最相似（即特征空
間中最鄰近）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。
2、KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。
該方法在定類決策上僅僅根據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。
KNN方法盡管從原理上也依賴于極限定理。但在類別決策時(shí)，僅僅與極少量的相鄰樣本有關(guān)。因?yàn)镵NN方法主要靠周圍有限的鄰近的樣本。
而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其它方法更為適合。
3、KNN算法不僅能夠用于分類，還能夠用于回歸。通過找出一個(gè)樣本的k個(gè)近期鄰居，將這些鄰居的屬性的平均值賦給該樣本，就能夠得到該樣本的屬性。
更實(shí)用的方法是將不同距離的
鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值（weight），如權(quán)值與距離成正比。
4、該算法在分類時(shí)有個(gè)基本的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量非常大，而其它類樣本容量非常小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。因此能夠採用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。
該方法不足之處是計(jì)算量較大，由于對每個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離。才干求得它的K個(gè)近期鄰點(diǎn)。
眼下經(jīng)常使用的解決方法是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自己主動分類，而那些樣本容量較小的類域採用這樣的算法比較easy產(chǎn)生誤分。
算法分類步驟例如以下：
1 首先我們事先定下k值（就是指k近鄰方法的k的大小。代表對于一個(gè)待分類的數(shù)據(jù)點(diǎn)，我們要尋找?guī)讉€(gè)它的鄰居）。這邊為了說明問題，我們?nèi)蓚€(gè)k值。分別為3和9；
2 依據(jù)事先確定的距離度量公式（如：歐氏距離）。得出待分類數(shù)據(jù)點(diǎn)和全部已知類別的樣本點(diǎn)中。距離近期的k個(gè)樣本。
3 統(tǒng)計(jì)這k個(gè)樣本點(diǎn)中。各個(gè)類別的數(shù)量。依據(jù)k個(gè)樣本中，數(shù)量最多的樣本是什么類別，我們就把這個(gè)數(shù)據(jù)點(diǎn)定為什么類別。
9、Naive Bayes：在眾多分類方法中，應(yīng)用最廣泛的有決策樹模型和樸素貝葉斯（Naive Bayes）貝葉斯分類的基礎(chǔ)是概率推理。就是在各種條件的存在不確定。僅知其出現(xiàn)概率的情況下，怎樣完畢推理和決策任務(wù)。概率推理是與確定性推理相相應(yīng)的。
而樸素貝葉斯分類器是基于獨(dú)立如果的，即如果樣本每一個(gè)特征與其它特征都不相關(guān)。舉個(gè)樣例，如果一種水果其具有紅。圓，直徑大概4英寸等特征。該水果能夠被判定為是蘋果。
雖然這些特征相互依賴或者有些特征由其它特征決定。然而樸素貝葉斯分類器覺得這些屬性在判定該水果是否為蘋果的概率分布上獨(dú)立的。樸素貝葉斯分類器依靠精確的自然概率模型，在有監(jiān)督學(xué)習(xí)的樣本集中能獲取得很好的分類效果。在很多實(shí)際應(yīng)用中。樸素貝葉斯模型參數(shù)預(yù)計(jì)使用最大似然預(yù)計(jì)方法。換而言之樸素貝葉斯模型能工作并沒實(shí)用到貝葉斯概率或者不論什么貝葉斯模型。
雖然是帶著這些樸素思想和過于簡單化的如果，但樸素貝葉斯分類器在非常多復(fù)雜的現(xiàn)實(shí)情形中仍可以取得相當(dāng)好的效果。2004年。一篇分析貝葉斯分類器問題的文章揭示了樸素貝葉斯分類器取得看上去不可思議的分類效果的若干理論上的原因。
雖然如此，2006年有一篇文章具體比較了各種分類方法，發(fā)現(xiàn)更新的方法（如boosted trees和隨機(jī)森林）的性能超過了貝葉斯分類器。
樸素貝葉斯分類器的一個(gè)優(yōu)勢在于僅僅須要依據(jù)少量的訓(xùn)練數(shù)據(jù)預(yù)計(jì)出必要的參數(shù)（變量的均值和方差）。因?yàn)樽兞开?dú)立如果，僅僅須要預(yù)計(jì)各個(gè)變量的方法。而不須要確定整個(gè)協(xié)方差矩陣。
10、Cart：分類與回歸樹，在分類樹下面有兩個(gè)關(guān)鍵的思想，第一個(gè)是關(guān)于遞歸地劃分自變量空間的想法，第二個(gè)是用驗(yàn)證數(shù)據(jù)進(jìn)行減枝。
決策樹生長的核心是確定決策樹的分枝準(zhǔn)則。
1、 怎樣從眾多的屬性變量中選擇一個(gè)當(dāng)前的最佳分支變量。
也就是選擇能使異質(zhì)性下降最快的變量。
異質(zhì)性的度量：GINI、TWOING、least squared deviation。
前兩種主要針對分類型變量，LSD針對連續(xù)性變量。
代理劃分、加權(quán)劃分、先驗(yàn)概率
2、 怎樣從分支變量的眾多取值中找到一個(gè)當(dāng)前的最佳切割點(diǎn)（切割閾值）。
（1） 切割閾值：
A、數(shù)值型變量——對記錄的值從小到大排序，計(jì)算每一個(gè)值作為臨界點(diǎn)產(chǎn)生的子節(jié)點(diǎn)的異質(zhì)性統(tǒng)計(jì)量。
可以使異質(zhì)性減小程度最大的臨界值便是最佳的劃分點(diǎn)。
B、分類型變量——列出劃分為兩個(gè)子集的全部可能組合。計(jì)算每種組合下生成子節(jié)點(diǎn)的異質(zhì)性。相同。找到使異質(zhì)性減小程度最大的組合作為最佳劃分點(diǎn)。
在決策樹的每個(gè)節(jié)點(diǎn)上我們能夠按任一個(gè)屬性的任一個(gè)值進(jìn)行劃分。按哪種劃分最好呢？有3個(gè)標(biāo)準(zhǔn)能夠用來衡量劃分的好壞：GINI指數(shù)、雙化指數(shù)、有序雙化指數(shù)。
下載文檔
