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

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

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

國際權威的學術組織theIEEEInternationalConferenceon

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

經典算法：C4.5,k-Means,SVM,Apriori,EM,PageRank,

AdaBoost,kNN,NaiveBayes,andCART。

不僅僅是選中的十大算法，其實參加評選的18種算法，實

際上隨便拿出一種來都可以稱得上是經典算法，它們在數(shù)據(jù)挖

掘領域都產生了極為深遠的影響。

（一）C4.5

C4.5算法是機器學習算法中的一種分類決策樹算法,其核

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

下幾方面對ID3算法進行了改進：

1.用信息增益率來選擇屬性，克服了用信息增益選擇屬性

時偏向選擇取值多的屬性的不足；

2.在樹構造過程中進行剪枝；

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

4.能夠對不完整數(shù)據(jù)進行處理。

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

較高。其缺點是：在構造樹的過程中，需要對數(shù)據(jù)集進行多次

的順序掃描和排序，因而導致算法的低效。

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

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

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

期望算法很相似，因為他們都試圖找到數(shù)據(jù)中自然聚類的中心。

它假設對象屬性來自于空間向量，并且目標是使各個群組內部

的均方誤差總和最小。

（三）Supportvectormachines

支持向量機，英文為SupportVectorMachine，簡稱SV機（論

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

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

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

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

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

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

是C.J.CBurges的《模式識別支持向量機指南》。vanderWalt和

Barnard將支持向量機和其他分類器進行了比較。

（四）TheApriorialgorithm

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

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

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

持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。

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

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

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

算法，其中概率模型依賴于無法觀測的隱藏變量（Latent

Variabl）。最大期望經常用在機器學習和計算機視覺的數(shù)據(jù)集聚

（DataClustering）領域。

（六）PageRank

PageRank是Google算法的重要內容。2001年9月被授予

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

因此，PageRank里的page不是指網頁，而是指佩奇，即這個等

級方法是以佩奇來命名的。

PageRank根據(jù)網站的外部鏈接和內部鏈接的數(shù)量和質量倆

衡量網站的價值。PageRank背后的概念是，每個到頁面的鏈接

都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網

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

意將他們的網站和你的網站掛鉤。PageRank這個概念引自學

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

一般判斷這篇論文的權威性就越高。

（七）AdaBoost

Adaboost是一種迭代算法，其核心思想是針對同一個訓練

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

來，構成一個更強的最終分類器(強分類器)。其算法本身是通

過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的

分類是否正確，以及上次的總體分類的準確率，來確定每個樣

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

練，最后將每次訓練得到的分類器最后融合起來，作為最后的

決策分類器。

（八）kNN:k-nearestneighborclassification

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

上比較成熟的方法，也是最簡單的機器學習算法之一。該方法

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

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

于這個類別。

（九）NaiveBayes

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

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

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

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

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

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

是實際上并非總是如此，這是因為NBC模型假設屬性之間相互

獨立，這個假設在實際應用中往往是不成立的，這給NBC模型

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

相關性較大時，NBC模型的分類效率比不上決策樹模型。而在

屬性相關性較小時，NBC模型的性能最為良好。

（十）CART:分類與回歸樹

CART,ClassificationandRegressionTrees。在分類樹下面有

兩個關鍵的思想。第一個是關于遞歸地劃分自變量空間的想法；

第二個想法是用驗證數(shù)據(jù)進行剪枝。

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

當前，市場競爭異常激烈，各商家企業(yè)為了能在競爭中占

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

技術能給企業(yè)帶來新的生機和活力。OLAP技術把企業(yè)大量的

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

企業(yè)的產值和效益，增強了客戶自身的競爭實力。

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

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

們帶來了多少價值呢？

客戶需求

客戶面對大量的信息，用OLAP進行多維分析。如：一個

網上書店，用OLAP技術可以瀏覽到什么時間，那個類別的客

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

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

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

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

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

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

OLAP結合起來進行分析呢？

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

SQLServer2005的DataMining是SQLServer2005分析服

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

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

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

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

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

搭售的產品、查找客戶將產品放入購物車的順序序列。

Microsoft決策樹算法、MicrosoftNaiveBayes算法、

Microsoft聚類分析算法、Microsoft神經網絡算法(SSAS)，可

以預測離散屬性，例如，預測目標郵件活動的收件人是否會購

買某個產品。

Microsoft決策樹算法、Microsoft時序算法可以預測連續(xù)

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

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

網站的點擊流分析。

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

常見項的組，例如，使用市場籃分析來建議客戶購買其他產品。

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

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

更好地理解屬性之間的關系。

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

提出問題

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

促進網上書店的銷售量的增長，各網上書店采取了各種方式，

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

更多的讀者。

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

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

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

戶購買了一種書籍之后，推薦給客戶其他的相關的書籍。這種

措施的運用給他們帶來了可觀的效益。

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

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

是用的關聯(lián)規(guī)則算法。“啤酒和尿布”的故事足以證明了該算法

的強大功能和產生的震撼效果。

那么，怎么來實現(xiàn)這樣一個效果呢？

解決步驟

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

挖掘模型，要用到兩張表，一張表是我們的會員，用會員ID號

來代替；另一張表是我們那個會員買了什么書。我們應用SQL

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

具體步驟如下：

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

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

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

事例表和嵌套表，并定義兩者之間的關系，定義User為事例表

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

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

建立挖掘模型。

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

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

個查看的選項卡。

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

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

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

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

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

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

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

要。重要性列就是說明這一情況的。例如，如果每個項集都包

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

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

C：關聯(lián)網絡：節(jié)點間的箭頭代表項之間有關聯(lián)。箭頭的方

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

效果展示

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

色的是可以預測所選節(jié)點的節(jié)點，也就是說如果消費者買了《月

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

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

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

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

們就很容易看到經過關聯(lián)算法計算出來的書籍之間的關聯(lián)性。

如圖３所示效果。

2、我們也可以通過寫DMX語句來實現(xiàn)預測查詢。

SELECT

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

From

[User]

NATURALPREDICTIONJOIN

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

[Sales])ASt

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

這個案例的前提是我們已經建立好了一個ＯＬＡＰ的多維

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

是DimCurrency，DimCustomer，DimProduct，DimTime，

DimPromotion。

提出問題

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

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

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

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

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

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

庫里面分析的時候，

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

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

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

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

屬性綜合考慮來分類，例如：我們要把高收入、高學歷、高消

費的客戶作為一個群體，把高收入，低學歷、高消費的客戶作

為一個群體，等等，然后，基于這些群體來瀏覽分析，銷售情

況，如何來實現(xiàn)呢？

解決步驟

用過聚類算法的大概比較清楚，聚類算法，是用來給事物

分類的。那么怎么用聚類算法的這個特性，和OLAP進行正和

呢。請看下面這個案例：

第一步：建立挖掘模型。這里需要注意的是：以前我們在

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

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

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

B：按照向導，選取事例鍵DimCustomer，

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

我們這里選取EnglishEducation、HouseOwnerFlag、Number

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

D：在完成對話框里面，我們輸入挖掘結構名稱

CustomerSturcture,輸入