数据挖掘十大算法及案例

数据挖掘十大算法及经典案例

一、数据挖掘十大经典算法

国际权威的学术组织theIEEEInternationalConferenceon

DataMining(ICDM)2006年12月评选出了数据挖掘领域的十大

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

AdaBoost,kNN,NaiveBayes,andCART。

不仅仅是选中的十大算法，其实参加评选的18种算法，实

际上随便拿出一种来都可以称得上是经典算法，它们在数据挖

掘领域都产生了极为深远的影响。

（一）C4.5

C4.5算法是机器学习算法中的一种分类决策树算法,其核

心算法是ID3算法。C4.5算法继承了ID3算法的优点，并在以

下几方面对ID3算法进行了改进：

1.用信息增益率来选择属性，克服了用信息增益选择属性

时偏向选择取值多的属性的不足；

2.在树构造过程中进行剪枝；

3.能够完成对连续属性的离散化处理；

4.能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率

较高。其缺点是：在构造树的过程中，需要对数据集进行多次

的顺序扫描和排序，因而导致算法的低效。

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

k-meansalgorithm算法是一个聚类算法，把n的对象根据他

们的属性分为k个分割，k<n。它与处理混合正态分布的最大

期望算法很相似，因为他们都试图找到数据中自然聚类的中心。

它假设对象属性来自于空间向量，并且目标是使各个群组内部

的均方误差总和最小。

（三）Supportvectormachines

支持向量机，英文为SupportVectorMachine，简称SV机（论

文中一般简称SVM）。它是一种監督式學習的方法，它广泛的

应用于统计分类以及回归分析中。支持向量机将向量映射到一

个更高维的空间里，在这个空间里建立有一个最大间隔超平

面。在分开数据的超平面的两边建有两个互相平行的超平面。

分隔超平面使两个平行超平面的距离最大化。假定平行超平面

间的距离或差距越大，分类器的总误差越小。一个极好的指南

是C.J.CBurges的《模式识别支持向量机指南》。vanderWalt和

Barnard将支持向量机和其他分类器进行了比较。

（四）TheApriorialgorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集

的算法。其核心是基于两阶段频集思想的递推算法。该关联规

则在分类上属于单维、单层、布尔关联规则。在这里，所有支

持度大于最小支持度的项集称为频繁项集，简称频集。

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

在统计计算中，最大期望（EM，Expectation–Maximization）

算法是在概率（probabilistic）模型中寻找参数最大似然估计的

算法，其中概率模型依赖于无法观测的隐藏变量（Latent

Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚

（DataClustering）领域。

（六）PageRank

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

美国专利，专利人是Google创始人之一拉里·佩奇（LarryPage）。

因此，PageRank里的page不是指网页，而是指佩奇，即这个等

级方法是以佩奇来命名的。

PageRank根据网站的外部链接和内部链接的数量和质量俩

衡量网站的价值。PageRank背后的概念是，每个到页面的链接

都是对该页面的一次投票，被链接的越多，就意味着被其他网

站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿

意将他们的网站和你的网站挂钩。PageRank这个概念引自学

术中一篇论文的被引述的频度——即被别人引述的次数越多，

一般判断这篇论文的权威性就越高。

（七）AdaBoost

Adaboost是一种迭代算法，其核心思想是针对同一个训练

集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起

来，构成一个更强的最终分类器(强分类器)。其算法本身是通

过改变数据分布来实现的，它根据每次训练集之中每个样本的

分类是否正确，以及上次的总体分类的准确率，来确定每个样

本的权值。将修改过权值的新数据集送给下层分类器进行训

练，最后将每次训练得到的分类器最后融合起来，作为最后的

决策分类器。

（八）kNN:k-nearestneighborclassification

K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论

上比较成熟的方法，也是最简单的机器学习算法之一。该方法

的思路是：如果一个样本在特征空间中的k个最相似(即特征空

间中最邻近)的样本中的大多数属于某一个类别，则该样本也属

于这个类别。

（九）NaiveBayes

在众多的分类模型中，应用最为广泛的两种分类模型是决

策树模型(DecisionTreeModel)和朴素贝叶斯模型（Naive

BayesianModel，NBC）。朴素贝叶斯模型发源于古典数学理论，

有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型

所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

理论上，NBC模型与其他分类方法相比具有最小的误差率。但

是实际上并非总是如此，这是因为NBC模型假设属性之间相互

独立，这个假设在实际应用中往往是不成立的，这给NBC模型

的正确分类带来了一定影响。在属性个数比较多或者属性之间

相关性较大时，NBC模型的分类效率比不上决策树模型。而在

属性相关性较小时，NBC模型的性能最为良好。

（十）CART:分类与回归树

CART,ClassificationandRegressionTrees。在分类树下面有

两个关键的思想。第一个是关于递归地划分自变量空间的想法；

第二个想法是用验证数据进行剪枝。

二、数据挖掘经典案例

当前，市场竞争异常激烈，各商家企业为了能在竞争中占

据优势，费劲心思。使用过OLAP技术的企业都知道，OLAP

技术能给企业带来新的生机和活力。OLAP技术把企业大量的

数据变成了客户需要的信息，把这些信息变成了价值，提高了

企业的产值和效益，增强了客户自身的竞争实力。

“啤酒与尿布”的故事家喻户晓，在IT界里，几乎是数据挖

掘的代名词，那么各商家企业受了多少启发，数据挖掘又给他

们带来了多少价值呢？

客户需求

客户面对大量的信息，用OLAP进行多维分析。如：一个

网上书店，用OLAP技术可以浏览到什么时间，那个类别的客

户买了多少书等信息，如果想动态的获得深层次的信息，比如：

哪些书籍可以打包推荐，哪些书籍可以在销售中关联推出等等，

就要用到数据挖掘技术了。

当客户在使用OLAＰ技术进行数据的多维分析的时候，联

想到“啤酒与尿布”的故事，客户不禁会有疑问，能不能通过数

据挖掘来对数据进行深层次的分析呢，能不能将数据挖掘和

OLAP结合起来进行分析呢？

SQLServer2005数据挖掘：

SQLServer2005的DataMining是SQLServer2005分析服

务（AnalysisServices）中的一部分。数据挖掘通常被称为“从大

型数据库提取有效、可信和可行信息的过程”。换言之，数据挖

掘派生数据中存在的模式和趋势。这些模式和趋势可以被收集

在一起并定义为挖掘模型。挖掘模型可以应用于特定的业务方

案，例如：预测销售额、向特定客户发送邮件、确定可能需要

搭售的产品、查找客户将产品放入购物车的顺序序列。

Microsoft决策树算法、MicrosoftNaiveBayes算法、

Microsoft聚类分析算法、Microsoft神经网络算法(SSAS)，可

以预测离散属性，例如，预测目标邮件活动的收件人是否会购

买某个产品。

Microsoft决策树算法、Microsoft时序算法可以预测连续

属性，预测连续属性，例如，预测下一年的销量。

Microsoft顺序分析和聚类分析算法预测顺序，例如，执行公司

网站的点击流分析。

Microsoft关联算法、Microsoft决策树算法查找交易中的

常见项的组，例如，使用市场篮分析来建议客户购买其他产品。

Microsoft聚类分析算法、Microsoft顺序分析和聚类分析

算法，查找相似项的组，例如，将人口统计数据分割为组以便

更好地理解属性之间的关系。

巅峰之旅之案例一：网上书店关联销售

提出问题

网上书店现在有了很强的市场和比较固定的大量的客户。为了

促进网上书店的销售量的增长，各网上书店采取了各种方式，

给客户提供更多更丰富的书籍，提供更优质服务，等方式吸引

更多的读者。

是不是这样就够了呢？这里，给众多网上书店的商家们提供一

种非常好的促进销售量增长，吸引读者的方法，就是关联销售

分析。这种方法就是给客户提供其他的相关书籍，也就是在客

户购买了一种书籍之后，推荐给客户其他的相关的书籍。这种

措施的运用给他们带来了可观的效益。

首先必须明确的是，这里介绍的关联销售并不是，根据网上书

店的销售记录进行的比例统计，也区别于简单的概率分析统计，

是用的关联规则算法。“啤酒和尿布”的故事足以证明了该算法

的强大功能和产生的震撼效果。

那么，怎么来实现这样一个效果呢？

解决步骤

首先，我们有数据源，也就是销售记录。这里我们做数据

挖掘模型，要用到两张表，一张表是我们的会员，用会员ID号

来代替；另一张表是我们那个会员买了什么书。我们应用SQL

Server2005的DataMining工具，建立数据挖掘模型。

具体步骤如下：

第一步：定义数据源。选取的为网上书店的销售记录数据

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

第二步：定义数据源视图。在此我们要建立好数据挖掘中

事例表和嵌套表，并定义两者之间的关系，定义User为事例表

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

第三步：选取MicrosoftAssociationRules（关联规则）算法，

建立挖掘模型。

第四步、设置算法参数，部署挖掘模型。

第五步、浏览察看挖掘模型。对于关联规则算法来说，三

个查看的选项卡。

A：项集：“项集”选项卡显示被模型识别为经常发现一起出

现的项集的列表。在这里指的是经过关联规则算法处理后，发

现关联在一起的书籍的集合。

B：规则：“规则”选项卡显示关联算法发现的规则。“规则”

选项卡包含一个具有以下列的网格：“概率”、“重要性”和“规则”。

概率说明出现规则结果的可能性。重要性用于度量规则的用途。

尽管规则出现的概率可能很高，但规则自身的用途可能并不重

要。重要性列就是说明这一情况的。例如，如果每个项集都包

含属性的某个特定状态，那么，即使概率非常高，预测状态的

规则也并不重要。重要性越高，规则越重要。

C：关联网络：节点间的箭头代表项之间有关联。箭头的方

向表示按照算法发现的规则确定的项之间的关联。

效果展示

1、我们可以看到在上图中，绿色的是我们选择的节点，橙

色的是可以预测所选节点的节点，也就是说如果消费者买了《月

光宝盒（2VCD）》的话，那么我们可以给该消费者推荐《乱世

佳人（上集，2VCD）》。紫色的是和所选节点能够双向预测的，

即买了《大圣娶亲》，推荐《乱世佳人（上集，2VCD）》；同样，

买了《乱世佳人（上集，2VCD）》，推荐《大圣娶亲》。这样我

们就很容易看到经过关联算法计算出来的书籍之间的关联性。

如图３所示效果。

2、我们也可以通过写DMX语句来实现预测查询。

SELECT

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

From

[User]

NATURALPREDICTIONJOIN

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

[Sales])ASt

巅峰之旅之案例二：客户类别销售分析

这个案例的前提是我们已经建立好了一个ＯＬＡＰ的多维

数据库Sales，事实表为FactInternetSales，有五个维度，分别

是DimCurrency，DimCustomer，DimProduct，DimTime，

DimPromotion。

提出问题

利用OLAP建立的多维数据库Sales，我们可以实现多角度

的浏览和分析。例如：我们可以分析2004年第一季度的M生

产线产品的销售量情况，还可以实现灵活的交叉分析，等等。

但是，如果我们要分析，某个维度的多个属性的综合的销售量，

例如：客户维度里有BirthDate、EnglishEducation、HouseOwner

Flag、NumberCarsOwned、YearlyIncome等属性，在多维数据

库里面分析的时候，

我们可以把客户维度的NumberCarsOwned属性放在展示

区域的行上，把度量值OrderQuantity放在列上，查看拥有0-4

辆汽车的客户的订购所有产品的数量。同样，我们也可以类似

的查看其他属性的情况。但是，如果我们要把客户维度的某些

属性综合考虑来分类，例如：我们要把高收入、高学历、高消

费的客户作为一个群体，把高收入，低学历、高消费的客户作

为一个群体，等等，然后，基于这些群体来浏览分析，销售情

况，如何来实现呢？

解决步骤

用过聚类算法的大概比较清楚，聚类算法，是用来给事物

分类的。那么怎么用聚类算法的这个特性，和OLAP进行正和

呢。请看下面这个案例：

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

建立数据挖掘模型的时候是基于关系型数据源。

A：而在这里，我们要基于多维数据库Sales，选取维度

DimCustomer为数据挖掘模型的数据源。

B：按照向导，选取事例键DimCustomer，

C：在选取事例级别列对话框里面，选择一些属性和度量值，

我们这里选取EnglishEducation、HouseOwnerFlag、Number

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

D：在完成对话框里面，我们输入挖掘结构名称

CustomerSturcture,输入