数据挖掘十大算法及案例

1、数据挖掘十大算法及经典案例一、数据挖掘十大经典算法国际权威的学术组织 the IEEE International Conference on Data Mining (ICDM) 2006 年12 月评选出了数据挖掘领域的十大经典算法： C4.5, k-Means, SVM, Apriori, EM, PageRank,AdaBoost, kNN, Naive Bayes, and CART。不仅仅是选中的十大算法，其实参加评选的 18 种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖 掘领域都产生了极为深远的影响。（一）C4.5C4.5 算法是机器学习算法中的一种分类决策树

2、算法,其核心算法是ID3 算法。 C4.5 算法继承了 ID3 算法的优点，并在以下几方面对ID3 算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次 的顺序扫描和排序，因而导致算法的低效。（二）The k-means algorithm 即K-Means 算法k-means algorithm 算法是一个聚类算法，把 n 的对象根据他们的属性分为k 个分割，k

3、 n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。 它假设对象属性来自于空间向量，并且目标是使各个群组内部的均 方误差总和最小。（三）Support vector machines支持向量机，英文为 Support Vector Machine，简称 SV 机（论文中一般简称 SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一 个更 高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。 分隔超平面使两个平行超平面的距离最大化。假 定平行超平面间的距离或差距越大

4、，分类器的总误差越小。一个极好的指南 是 C.J.C Burges 的模式识别支持向量机指南。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。（四）The Apriori algorithmApriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规 则在分类上属于单维、单层、布尔关联规则。在这里，所有支 持度大于最小支持度的项集称为频繁项集，简称频集。（五）最大期望(EM)算法在统计计算中，最大期望（EM，ExpectationMaximization） 算法是在概率（probabilistic）模型中寻找

5、参数最大似然 估计的算法， 其中概率模型依赖于无法观测的隐藏变量（ Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。（六）PageRankPageRank 是 Google 算法的重要内容。2001 年 9 月被授予美国专利，专利人是 Google 创始人之一拉里佩奇（Larry Page）。因此，PageRank 里的page 不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。PageRank 根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank 背后的概念是，每个到页面的链接都是对该页面的一次

6、投票，被链接的越多，就意味着被其他网 站投票越多。这个就是所谓的“链接流行度”衡量多少人愿 意将他们的网站和你的网站挂钩。PageRank 这个概念引自 学术中一篇论文的被引述的频度即被别人引述的次数越多， 一般判断这篇论文的权威性就越高。（七）AdaBoostAdaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起 来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样 本的权 值。将修改过权值的新数据集送给下层分类器进行

7、训练，最后将每次训练得到的分类器最后融合起来，作为最后的 决策分类器。（八）kNN: k-nearest neighbor classificationK 最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法 的思路是：如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属 于这个类别。（九）Naive Bayes在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel) 和朴素贝叶斯模型（ Naive Bayesian Mode

8、l，NBC）。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC 模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。 理论上，NBC 模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为 NBC 模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给 NBC 模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC 模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC 模型的性能最为良好。（十）CART: 分类与回归树CART, Classification and Regressio

9、n Trees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法； 第二个想法是用验证数据进行剪枝。二、数据挖掘经典案例当前，市场竞争异常激烈，各商家企业为了能在竞争中占 据优势，费劲心思。使用过 OLAP 技术的企业都知道，OLAP 技术能给企业带来新的生机和活力。OLAP 技术把企业大量的数据变成了客户需要的信息，把这些信息变成了价值，提高了 企业的产值和效益，增强了客户自身的竞争实力。“啤酒与尿布”的故事家喻户晓，在IT 界里，几乎是数据挖掘的代名词，那么各商家企业受了多少启发，数据挖掘又给他 们带来了多少价值呢？客户需求客户面对大量的信息，用 OLAP 进行多维分析

10、。如：一个网上书店，用 OLAP 技术可以浏览到什么时间，那个类别的客户买了多少书等信息，如果想动态的获得深层次的信息，比如： 哪些书籍可以打包推荐，哪些书籍可以在销售中关联推出等等， 就要用到数据挖掘技术了。当客户在使用 OLA技术进行数据的多维分析的时候，联想到“啤酒与尿布”的故事，客户不禁会有疑问，能不能通过数 据挖掘来对数据进行深层次的分析呢，能不能将数据挖掘和OLAP 结合起来进行分析呢？SQL Server 2005 数据挖掘：SQL Server 2005 的Data Mining 是 SQL Server2005 分析服务（Analysis Services）中的一部分。数据挖

11、掘通常被称为“从大型数据库提取有效、可信和可行信息的过程”。换言之，数据挖 掘派生数据中存在的模式和趋势。这些模式和趋势可以被收集 在一起并定义为挖掘模型。挖掘模型可以应用于特定的业务方 案，例如：预测销售额、向特定客户发送邮件、确定可能需要 搭售的产品、查找客户将产品放入购物车的顺序序列。Microsoft 决策树算法、Microsoft Naive Bayes 算法、Microsoft 聚类分析算法、Microsoft 神经网络算法(SSAS)，可以预测离散属性，例如，预测目标邮件活动的收件人是否会购 买某个产品。Microsoft 决策树算法、Microsoft 时序算法可以预测连续属性

12、，预测连续属性，例如，预测下一年的销量。Microsoft 顺序分析和聚类分析算法预测顺序，例如，执行公司网站的点击流分析。Microsoft 关联算法、Microsoft 决策树算法查找交易中的常见项的组，例如，使用市场篮分析来建议客户购买其他产品。Microsoft 聚类分析算法、Microsoft 顺序分析和聚类分析算法，查找相似项的组，例如，将人口统计数据分割为组以便 更好地理解属性之间的关系。巅峰之旅之案例一：网上书店关联销售提出问题网上书店现在有了很强的市场和比较固定的大量的客户。为了 促进网上书店的销售量的增长，各网上书店采取了各种方式， 给客户提供更多更丰富的书籍，提供更优质服

13、务，等方式吸引 更多的读者。是不是这样就够了呢？这里，给众多网上书店的商家们提供一 种非常好的促进销售量增长，吸引读者的方法，就是关联销售 分析。这种方法就是给客户提供其他的相关书籍，也就是在客 户购买了一种书籍之后，推荐给客户其他的相关的书籍。这种 措施的运用给他们带来了可观的效益。首先必须明确的是，这里介绍的关联销售并不是，根据网上书店的销售记录进行的比例统计，也区别于简单的概率分析统计， 是用的关联规则算法。“啤酒和尿布”的故事足以证明了该算法的强大功能和产生的震撼效果。那么，怎么来实现这样一个效果呢？解决步骤首先，我们有数据源，也就是销售记录。这里我们做数据 挖掘模型，要用到两张表，一

14、张表是我们的会员，用会员 ID 号来代替；另一张表是我们那个会员买了什么书。我们应用 SQL Server 2005 的Data Mining 工具，建立数据挖掘模型。具体步骤如下：第一步：定义数据源。选取的为网上书店的销售记录数据 源（最主要的是 User 表和Sales 表）。第二步：定义数据源视图。在此我们要建立好数据挖掘中事例表和嵌套表，并定义两者之间的关系，定义 User 为事例表（Case Table），Sales 为嵌套表（Nested Table）。第三步：选取 Microsoft Association Rules（关联规则）算法， 建立挖掘模型。第四步、设置算法参数，部署挖

15、掘模型。第五步、浏览察看挖掘模型。对于关联规则算法来说，三个查看的选项卡。A：项集：“项集”选项卡显示被模型识别为经常发现一起出现的项集的列表。在这里指的是经过关联规则算法处理后，发 现关联在一起的书籍的集合。B：规则：“规则”选项卡显示关联算法发现的规则。“规则”选项卡包含一个具有以下列的网格：“概率”、“重要性”和“规则”。概率说明出现规则结果的可能性。重要性用于度量规则的用途。 尽管规则出现的概率可能很高，但规则自身的用途可能并不重要。重要性列就是说明这一情况的。例如，如果每个项集都包含属性的某个特定状态，那么，即使概率非常高，预测状态的规则也并不重要。重要性越高，规则越重要。C：关联网

16、络：节点间的箭头代表项之间有关联。箭头的方向表示按照算法发现的规则确定的项之间的关联。效果展示1、我们可以看到在上图中，绿色的是我们选择的节点，橙色的是可以预测所选节点的节点，也就是说如果消费者买了月光宝盒（2VCD）的话，那么我们可以给该消费者推荐乱世佳人（上集，2VCD）。紫色的是和所选节点能够双向预测的，即买了大圣娶亲，推荐乱世佳人（上集，2VCD）；同样，买了乱世佳人（上集，2VCD），推荐大圣娶亲。这样我们就很容易看到经过关联算法计算出来的书籍之间的关联性。如图所示效果。2、我们也可以通过写 DMX 语句来实现预测查询。SELECTPredictAssociation(User.Sa

17、les,include_statistics,10) FromUserNATURAL PREDICTION JOIN(SELECT (SELECT 月光宝盒(2VCD) AS Book Name) ASSales) AS t巅峰之旅之案例二：客户类别销售分析这个案例的前提是我们已经建立好了一个的多维 数据库 Sales，事实表为 FactInternetSales，有 五个维度，分别是DimCurrency ， DimCustomer ， DimProduct ， DimTime ，DimPromotion。提出问题利用OLAP 建立的多维数据库 Sales，我们可以实现多角度的浏览和分析。例

18、如：我们可以分析 2004 年第一季度的 M 生产线产品的销售量情况，还可以实现灵活的交叉分析，等等。但是，如果我们要分析，某个维度的多个属性的综合的销售量， 例如：客户维度里有 Birth Date、English Education、House Owner Flag、Number Cars Owned、Yearly Income 等属性，在多维数据库里面分析的时候，我们可以把客户维度的 Number Cars Owned 属性放在展示区域的行上，把度量值 Order Quantity 放在列上，查看拥有 0-4 辆汽车的客户的订购所有产品的数量。同样，我们也可以类似 的查看其他属性的情况。

19、但是，如果我们要把客户维度的某些 属性综合考虑来分类，例如：我们要把高收入、高学历、高消 费的客户作为一个群体，把高收入，低学历、高消费的客户作 为一个群体，等等，然后，基于这些群体来浏览分析，销售情 况，如何来实现呢？解决步骤用过聚类算法的大概比较清楚，聚类算法，是用来给事物 分类的。那么怎么用聚类算法的这个特性，和 OLAP 进行正和呢。 请看下面这个案例：第一步：建立挖掘模型。这里需要注意的是：以前我们在 建立数据挖掘模型的时候是基于关系型数据源。A：而在这里，我们要基于多维数据库 Sales，选取维度DimCustomer 为数据挖掘模型的数据源。B：按照向导，选取事例键 Dim Customer，C：在选取事例级别列对话框里面，选择一些属性和度量值，我们这里选取 English Education、House Owner Flag、Number Cars Owned、Yearly Income、Sales Amount。如图 5 所示。D ： 在完成对话框里面， 我们输入挖掘结构名称CustomerStu