數(shù)據(jù)挖掘十大算法及案例

數(shù)據(jù)挖掘十大算法及經(jīng)典案例

一、數(shù)據(jù)挖掘十大經(jīng)典算法

國(guó)際權(quán)威的學(xué)術(shù)組織theIEEEInternationalConferenceon

DataMining(ICDM)2006年12月評(píng)選出了數(shù)據(jù)挖掘領(lǐng)域的十大

經(jīng)典算法：C4.5,k-Means,SVM,Apriori,EM,PageRank,

AdaBoost,kNN,NaiveBayes,andCART。

不僅僅是選中的十大算法，其實(shí)參加評(píng)選的18種算法，實(shí)

際上隨便拿出一種來(lái)都可以稱得上是經(jīng)典算法，它們?cè)跀?shù)據(jù)挖

掘領(lǐng)域都產(chǎn)生了極為深遠(yuǎn)的影響。

（一）C4.5

C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹(shù)算法,其核

心算法是ID3算法。C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以

下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：

1.用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性

時(shí)偏向選擇取值多的屬性的不足；

2.在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝；

3.能夠完成對(duì)連續(xù)屬性的離散化處理；

4.能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

C4.5算法有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率

較高。其缺點(diǎn)是：在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次

的順序掃描和排序，因而導(dǎo)致算法的低效。

（二）Thek-meansalgorithm即K-Means算法

k-meansalgorithm算法是一個(gè)聚類算法，把n的對(duì)象根據(jù)他

們的屬性分為k個(gè)分割，k<n。它與處理混合正態(tài)分布的最大

期望算法很相似，因?yàn)樗麄兌荚噲D找到數(shù)據(jù)中自然聚類的中心。

它假設(shè)對(duì)象屬性來(lái)自于空間向量，并且目標(biāo)是使各個(gè)群組內(nèi)部

的均方誤差總和最小。

（三）Supportvectormachines

支持向量機(jī)，英文為SupportVectorMachine，簡(jiǎn)稱SV機(jī)（論

文中一般簡(jiǎn)稱SVM）。它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的

應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。支持向量機(jī)將向量映射到一

個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平

面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。

分隔超平面使兩個(gè)平行超平面的距離最大化。假定平行超平面

間的距離或差距越大，分類器的總誤差越小。一個(gè)極好的指南

是C.J.CBurges的《模式識(shí)別支持向量機(jī)指南》。vanderWalt和

Barnard將支持向量機(jī)和其他分類器進(jìn)行了比較。

（四）TheApriorialgorithm

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集

的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)

則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支

持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡(jiǎn)稱頻集。

（五）最大期望(EM)算法

在統(tǒng)計(jì)計(jì)算中，最大期望（EM，Expectation–Maximization）

算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計(jì)的

算法，其中概率模型依賴于無(wú)法觀測(cè)的隱藏變量（Latent

Variabl）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)的數(shù)據(jù)集聚

（DataClustering）領(lǐng)域。

（六）PageRank

PageRank是Google算法的重要內(nèi)容。2001年9月被授予

美國(guó)專利，專利人是Google創(chuàng)始人之一拉里·佩奇（LarryPage）。

因此，PageRank里的page不是指網(wǎng)頁(yè)，而是指佩奇，即這個(gè)等

級(jí)方法是以佩奇來(lái)命名的。

PageRank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量倆

衡量網(wǎng)站的價(jià)值。PageRank背后的概念是，每個(gè)到頁(yè)面的鏈接

都是對(duì)該頁(yè)面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)

站投票越多。這個(gè)就是所謂的“鏈接流行度”——衡量多少人愿

意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。PageRank這個(gè)概念引自學(xué)

術(shù)中一篇論文的被引述的頻度——即被別人引述的次數(shù)越多，

一般判斷這篇論文的權(quán)威性就越高。

（七）AdaBoost

Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練

集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起

來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。其算法本身是通

過(guò)改變數(shù)據(jù)分布來(lái)實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的

分類是否正確，以及上次的總體分類的準(zhǔn)確率，來(lái)確定每個(gè)樣

本的權(quán)值。將修改過(guò)權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)

練，最后將每次訓(xùn)練得到的分類器最后融合起來(lái)，作為最后的

決策分類器。

（八）kNN:k-nearestneighborclassification

K最近鄰(k-NearestNeighbor，KNN)分類算法，是一個(gè)理論

上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法

的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空

間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬

于這個(gè)類別。

（九）NaiveBayes

在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決

策樹(shù)模型(DecisionTreeModel)和樸素貝葉斯模型（Naive

BayesianModel，NBC）。樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，

有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。同時(shí)，NBC模型

所需估計(jì)的參數(shù)很少，對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單。

理論上，NBC模型與其他分類方法相比具有最小的誤差率。但

是實(shí)際上并非總是如此，這是因?yàn)镹BC模型假設(shè)屬性之間相互

獨(dú)立，這個(gè)假設(shè)在實(shí)際應(yīng)用中往往是不成立的，這給NBC模型

的正確分類帶來(lái)了一定影響。在屬性個(gè)數(shù)比較多或者屬性之間

相關(guān)性較大時(shí)，NBC模型的分類效率比不上決策樹(shù)模型。而在

屬性相關(guān)性較小時(shí)，NBC模型的性能最為良好。

（十）CART:分類與回歸樹(shù)

CART,ClassificationandRegressionTrees。在分類樹(shù)下面有

兩個(gè)關(guān)鍵的思想。第一個(gè)是關(guān)于遞歸地劃分自變量空間的想法；

第二個(gè)想法是用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝。

二、數(shù)據(jù)挖掘經(jīng)典案例

當(dāng)前，市場(chǎng)競(jìng)爭(zhēng)異常激烈，各商家企業(yè)為了能在競(jìng)爭(zhēng)中占

據(jù)優(yōu)勢(shì)，費(fèi)勁心思。使用過(guò)OLAP技術(shù)的企業(yè)都知道，OLAP

技術(shù)能給企業(yè)帶來(lái)新的生機(jī)和活力。OLAP技術(shù)把企業(yè)大量的

數(shù)據(jù)變成了客戶需要的信息，把這些信息變成了價(jià)值，提高了

企業(yè)的產(chǎn)值和效益，增強(qiáng)了客戶自身的競(jìng)爭(zhēng)實(shí)力。

“啤酒與尿布”的故事家喻戶曉，在IT界里，幾乎是數(shù)據(jù)挖

掘的代名詞，那么各商家企業(yè)受了多少啟發(fā)，數(shù)據(jù)挖掘又給他

們帶來(lái)了多少價(jià)值呢？

客戶需求

客戶面對(duì)大量的信息，用OLAP進(jìn)行多維分析。如：一個(gè)

網(wǎng)上書店，用OLAP技術(shù)可以瀏覽到什么時(shí)間，那個(gè)類別的客

戶買了多少書等信息，如果想動(dòng)態(tài)的獲得深層次的信息，比如：

哪些書籍可以打包推薦，哪些書籍可以在銷售中關(guān)聯(lián)推出等等，

就要用到數(shù)據(jù)挖掘技術(shù)了。

當(dāng)客戶在使用OLAＰ技術(shù)進(jìn)行數(shù)據(jù)的多維分析的時(shí)候，聯(lián)

想到“啤酒與尿布”的故事，客戶不禁會(huì)有疑問(wèn)，能不能通過(guò)數(shù)

據(jù)挖掘來(lái)對(duì)數(shù)據(jù)進(jìn)行深層次的分析呢，能不能將數(shù)據(jù)挖掘和

OLAP結(jié)合起來(lái)進(jìn)行分析呢？

SQLServer2005數(shù)據(jù)挖掘：

SQLServer2005的DataMining是SQLServer2005分析服

務(wù)（AnalysisServices）中的一部分。數(shù)據(jù)挖掘通常被稱為“從大

型數(shù)據(jù)庫(kù)提取有效、可信和可行信息的過(guò)程”。換言之，數(shù)據(jù)挖

掘派生數(shù)據(jù)中存在的模式和趨勢(shì)。這些模式和趨勢(shì)可以被收集

在一起并定義為挖掘模型。挖掘模型可以應(yīng)用于特定的業(yè)務(wù)方

案，例如：預(yù)測(cè)銷售額、向特定客戶發(fā)送郵件、確定可能需要

搭售的產(chǎn)品、查找客戶將產(chǎn)品放入購(gòu)物車的順序序列。

Microsoft決策樹(shù)算法、MicrosoftNaiveBayes算法、

Microsoft聚類分析算法、Microsoft神經(jīng)網(wǎng)絡(luò)算法(SSAS)，可

以預(yù)測(cè)離散屬性，例如，預(yù)測(cè)目標(biāo)郵件活動(dòng)的收件人是否會(huì)購(gòu)

買某個(gè)產(chǎn)品。

Microsoft決策樹(shù)算法、Microsoft時(shí)序算法可以預(yù)測(cè)連續(xù)

屬性，預(yù)測(cè)連續(xù)屬性，例如，預(yù)測(cè)下一年的銷量。

Microsoft順序分析和聚類分析算法預(yù)測(cè)順序，例如，執(zhí)行公司

網(wǎng)站的點(diǎn)擊流分析。

Microsoft關(guān)聯(lián)算法、Microsoft決策樹(shù)算法查找交易中的

常見(jiàn)項(xiàng)的組，例如，使用市場(chǎng)籃分析來(lái)建議客戶購(gòu)買其他產(chǎn)品。

Microsoft聚類分析算法、Microsoft順序分析和聚類分析

算法，查找相似項(xiàng)的組，例如，將人口統(tǒng)計(jì)數(shù)據(jù)分割為組以便

更好地理解屬性之間的關(guān)系。

巔峰之旅之案例一：網(wǎng)上書店關(guān)聯(lián)銷售

提出問(wèn)題

網(wǎng)上書店現(xiàn)在有了很強(qiáng)的市場(chǎng)和比較固定的大量的客戶。為了

促進(jìn)網(wǎng)上書店的銷售量的增長(zhǎng)，各網(wǎng)上書店采取了各種方式，

給客戶提供更多更豐富的書籍，提供更優(yōu)質(zhì)服務(wù)，等方式吸引

更多的讀者。

是不是這樣就夠了呢？這里，給眾多網(wǎng)上書店的商家們提供一

種非常好的促進(jìn)銷售量增長(zhǎng)，吸引讀者的方法，就是關(guān)聯(lián)銷售

分析。這種方法就是給客戶提供其他的相關(guān)書籍，也就是在客

戶購(gòu)買了一種書籍之后，推薦給客戶其他的相關(guān)的書籍。這種

措施的運(yùn)用給他們帶來(lái)了可觀的效益。

首先必須明確的是，這里介紹的關(guān)聯(lián)銷售并不是，根據(jù)網(wǎng)上書

店的銷售記錄進(jìn)行的比例統(tǒng)計(jì)，也區(qū)別于簡(jiǎn)單的概率分析統(tǒng)計(jì)，

是用的關(guān)聯(lián)規(guī)則算法?！捌【坪湍虿肌钡墓适伦阋宰C明了該算法

的強(qiáng)大功能和產(chǎn)生的震撼效果。

那么，怎么來(lái)實(shí)現(xiàn)這樣一個(gè)效果呢？

解決步驟

首先，我們有數(shù)據(jù)源，也就是銷售記錄。這里我們做數(shù)據(jù)

挖掘模型，要用到兩張表，一張表是我們的會(huì)員，用會(huì)員ID號(hào)

來(lái)代替；另一張表是我們那個(gè)會(huì)員買了什么書。我們應(yīng)用SQL

Server2005的DataMining工具，建立數(shù)據(jù)挖掘模型。

具體步驟如下：

第一步：定義數(shù)據(jù)源。選取的為網(wǎng)上書店的銷售記錄數(shù)據(jù)

源（最主要的是User表和Sales表）。

第二步：定義數(shù)據(jù)源視圖。在此我們要建立好數(shù)據(jù)挖掘中

事例表和嵌套表，并定義兩者之間的關(guān)系，定義User為事例表

（CaseTable），Sales為嵌套表（NestedTable）。

第三步：選取MicrosoftAssociationRules（關(guān)聯(lián)規(guī)則）算法，

建立挖掘模型。

第四步、設(shè)置算法參數(shù)，部署挖掘模型。

第五步、瀏覽察看挖掘模型。對(duì)于關(guān)聯(lián)規(guī)則算法來(lái)說(shuō)，三

個(gè)查看的選項(xiàng)卡。

A：項(xiàng)集：“項(xiàng)集”選項(xiàng)卡顯示被模型識(shí)別為經(jīng)常發(fā)現(xiàn)一起出

現(xiàn)的項(xiàng)集的列表。在這里指的是經(jīng)過(guò)關(guān)聯(lián)規(guī)則算法處理后，發(fā)

現(xiàn)關(guān)聯(lián)在一起的書籍的集合。

B：規(guī)則：“規(guī)則”選項(xiàng)卡顯示關(guān)聯(lián)算法發(fā)現(xiàn)的規(guī)則。“規(guī)則”

選項(xiàng)卡包含一個(gè)具有以下列的網(wǎng)格：“概率”、“重要性”和“規(guī)則”。

概率說(shuō)明出現(xiàn)規(guī)則結(jié)果的可能性。重要性用于度量規(guī)則的用途。

盡管規(guī)則出現(xiàn)的概率可能很高，但規(guī)則自身的用途可能并不重

要。重要性列就是說(shuō)明這一情況的。例如，如果每個(gè)項(xiàng)集都包

含屬性的某個(gè)特定狀態(tài)，那么，即使概率非常高，預(yù)測(cè)狀態(tài)的

規(guī)則也并不重要。重要性越高，規(guī)則越重要。

C：關(guān)聯(lián)網(wǎng)絡(luò)：節(jié)點(diǎn)間的箭頭代表項(xiàng)之間有關(guān)聯(lián)。箭頭的方

向表示按照算法發(fā)現(xiàn)的規(guī)則確定的項(xiàng)之間的關(guān)聯(lián)。

效果展示

1、我們可以看到在上圖中，綠色的是我們選擇的節(jié)點(diǎn)，橙

色的是可以預(yù)測(cè)所選節(jié)點(diǎn)的節(jié)點(diǎn)，也就是說(shuō)如果消費(fèi)者買了《月

光寶盒（2VCD）》的話，那么我們可以給該消費(fèi)者推薦《亂世

佳人（上集，2VCD）》。紫色的是和所選節(jié)點(diǎn)能夠雙向預(yù)測(cè)的，

即買了《大圣娶親》，推薦《亂世佳人（上集，2VCD）》；同樣，

買了《亂世佳人（上集，2VCD）》，推薦《大圣娶親》。這樣我

們就很容易看到經(jīng)過(guò)關(guān)聯(lián)算法計(jì)算出來(lái)的書籍之間的關(guān)聯(lián)性。

如圖３所示效果。

2、我們也可以通過(guò)寫DMX語(yǔ)句來(lái)實(shí)現(xiàn)預(yù)測(cè)查詢。

SELECT

PredictAssociation([User].[Sales],include_statistics,10)

From

[User]

NATURALPREDICTIONJOIN

(SELECT(SELECT'月光寶盒(2VCD)'AS[BookName])AS

[Sales])ASt

巔峰之旅之案例二：客戶類別銷售分析

這個(gè)案例的前提是我們已經(jīng)建立好了一個(gè)ＯＬＡＰ的多維

數(shù)據(jù)庫(kù)Sales，事實(shí)表為FactInternetSales，有五個(gè)維度，分別

是DimCurrency，DimCustomer，DimProduct，DimTime，

DimPromotion。

提出問(wèn)題

利用OLAP建立的多維數(shù)據(jù)庫(kù)Sales，我們可以實(shí)現(xiàn)多角度

的瀏覽和分析。例如：我們可以分析2004年第一季度的M生

產(chǎn)線產(chǎn)品的銷售量情況，還可以實(shí)現(xiàn)靈活的交叉分析，等等。

但是，如果我們要分析，某個(gè)維度的多個(gè)屬性的綜合的銷售量，

例如：客戶維度里有BirthDate、EnglishEducation、HouseOwner

Flag、NumberCarsOwned、YearlyIncome等屬性，在多維數(shù)據(jù)

庫(kù)里面分析的時(shí)候，

我們可以把客戶維度的NumberCarsOwned屬性放在展示

區(qū)域的行上，把度量值OrderQuantity放在列上，查看擁有0-4

輛汽車的客戶的訂購(gòu)所有產(chǎn)品的數(shù)量。同樣，我們也可以類似

的查看其他屬性的情況。但是，如果我們要把客戶維度的某些

屬性綜合考慮來(lái)分類，例如：我們要把高收入、高學(xué)歷、高消

費(fèi)的客戶作為一個(gè)群體，把高收入，低學(xué)歷、高消費(fèi)的客戶作

為一個(gè)群體，等等，然后，基于這些群體來(lái)瀏覽分析，銷售情

況，如何來(lái)實(shí)現(xiàn)呢？

解決步驟

用過(guò)聚類算法的大概比較清楚，聚類算法，是用來(lái)給事物

分類的。那么怎么用聚類算法的這個(gè)特性，和OLAP進(jìn)行正和

呢。請(qǐng)看下面這個(gè)案例：

第一步：建立挖掘模型。這里需要注意的是：以前我們?cè)?/p>

建立數(shù)據(jù)挖掘模型的時(shí)候是基于關(guān)系型數(shù)據(jù)源。

A：而在這里，我們要基于多維數(shù)據(jù)庫(kù)Sales，選取維度

DimCustomer為數(shù)據(jù)挖掘模型的數(shù)據(jù)源。

B：按照向?qū)?，選取事例鍵DimCustomer，

C：在選取事例級(jí)別列對(duì)話框里面，選擇一些屬性和度量值，

我們這里選取EnglishEducation、HouseOwnerFlag、Number

CarsOwned、YearlyIncome、SalesAmount。如圖5所示。

D：在完成對(duì)話框里面，我們輸入挖掘結(jié)構(gòu)名稱

CustomerSturcture,輸入