数据挖掘算法综述

数据挖掘算法综述摘要：数据挖掘技术在当前研究领域中算是比较热门的一项技术，从国外发展到中国，具有广阔的商业应用前景。本文主要概述了当前数据挖掘的七大方法（分类、回归分析、聚类、关联规则、特征、变化和偏差分析、Web页挖掘）和十大经典算法（C4.5,K-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,NaiveBayes,CART），以及数据挖掘的发展趋势。关键词：数据挖掘，常用方法，经典算法1引言在当今信息爆炸的时代，伴随着社会事件和自然活动的大量产生（数据的海量增长），人类正面临着“被信息所淹没，但却饥渴于知识”的困境。随着计算机软硬件技术的快速发展、企业信息化水平的不断提高和数据库技术的日臻完善，人类积累的数据量正以指数方式增长。面对海量的、杂乱无序的数据，人们迫切需要一种将传统的数据分析方法与处理海量数据的复杂算法有机结合的技术。数据挖掘技术就是在这样的背景下产生的。它可以从大量的数据中去伪存真，提取有用的信息，并将其转换成知识。数据挖掘是一个多学科领域，它融合了数据库技术、人工智能、机器学习、模式识别、模糊数学和数理统计等最新技术的研究成果，可以用来支持商业智能应用和决策分析。例如顾客细分、交叉销售、欺诈检测、顾客流失分析、商品销量预测等等，目前广泛应用于银行、金融、医疗、工业、零售和电信等行业。数据挖掘技术的发展对于各行各业来说，都具有重要的现实意义。2数据挖掘的概念2.1什么是数据挖掘数据挖掘(DataMining)，也叫数据开采，数据采掘等，是按照既定的业务目标从海量数据中提取出潜在、有效并能被人理解的模式的高级处理过程．在较浅的层次上，它利用现有数据库管理系统的查询、检索及报表功能，与多维分析、统计分析方法相结合，进行联机分析处理(O乙心)，从而得出可供决策参考的统计分析数据．在深层次上，则从数据库中发现前所未有的、隐含的知识．OLAF'的出现早于数据挖掘，它们都是从数据库中抽取有用信息的方法，就决策支持的需要而言两者是相辅相成的。OLAP可以看作一种广义的数据挖掘方法，它旨在简化和支持联机分析，而数据挖掘的目的是便这一过程尽可能自动化。数据挖掘基于的数据库类型主要有：关系型数据库、面向对象数据库、事务数据库、演绎数据库、时态数据库、多媒体数据库、主动数据库、空间数据库、遗留数据库、异质数据库、文本型、Internet信息库以及新兴的数据仓库。而挖掘后获得的知识包括关联规则、特征规则、区分规则、分类规则、总结规则、偏差规则、聚类规则、模式分析及趋势分析等。2.2数据挖掘的特点数据挖掘技术具有以下特点：1.处理的数据规模十分庞大，达到GB、TB数量级，甚至更大。2.查询一般是决策制定者(用户)提出的即时随机查询，往往不能形成精确的查询要求，需要靠系统本身寻找其可能感兴趣的东西。3.在一些应用(如商业投资等)中，由于数据变化迅速，因此要求数据挖掘能快速做出相应反应以随时提供决策支持。4.数据挖掘中，规则的发现基于统计规律．因此，所发现的规则不必适用于所有数据，而是当达到某一临界值时，即认为有效．因此，利用数据挖掘技术可能会发现大量的规则。5.数据挖掘所发现的规则是动态的，它只反映了当前状态的数据库具有的规则，随着不断地向数据库中加入新数据，需要随时对其进行更新。2.3数据挖掘的应用基础数据挖掘是一种获得知识的技术。它的基础是数据，手段是各种算法，目的是获得数据中蕴含的知识。发现知识并非易事，人们总是受到各种各样的局限，目前数据缺乏仍然是发现知识的瓶颈。随着数据采集和存储技术的发展，对大量数据的分析和使用成为一个新的难题。对数据挖掘应用而言，知识的发现存在两个极限，一个是数据极限，即数据要么非常庞大，要么数据量足够小，或者数据量小但维度非常大；另一个是算法极限，即针对很多数据（不同的性质，不同的形式）和很多需求，目前所有的算法尚不能很好地解决某些问题。因此，数据挖掘应用具有三个要素：数据，算法，知识。数据挖掘应用是一个多层次、流程化的工程任务，开展数据挖掘应用也需要从每个层面加以处理，才能保证整个数据挖掘的成功运行。数据挖掘应用从上到下可分为三个大层面，具体结构如下图1所示：图1数据挖掘应用的三大层面应用层：把数据挖掘结果应用于实践。算法层：提供算法、引擎和界面。数据层：提供数据源、数据探索、数据准备。3数据挖掘的常用方法数据挖掘从一个新的视角将数据库技术、统计学、机器学习、信息检索技术、数据可视化和模式识别与人工智能等领域有机结合起来，它能组合各个领域的优点，从而能从数据中挖掘到其他传统方法不能发现的有用知识。利用数据挖掘进行数据分析常用的方法主要有分类、回归分析、聚类、关联规则、特征、变化和偏差分析、Web页挖掘等，它们分别从不同的角度对数据进行挖掘。1.分类分类就是应用已知的一些属性数据去推测一个未知的离散型属性数据，而这个被推测的属性数据的可取值是预先定义的。要很好地实现这种推测，就需要事先在已知的一些属性和未知的离散型属性之间建立一个有效的模型，即分类模型。它可以应用到客户的分类、客户的属性和特征分析、客户满意度分析、客户的购买趋势预测等，如一个汽车零售商将客户按照对汽车的喜好划分成不同的类，这样营销人员就可以将新型汽车的广告手册直接邮寄到有这种喜好的客户手中，从而大大增加了商业机会。2.回归分析回归分析方法反映的是事务数据库中属性值在时间上的特征，产生一个将数据项映射到一个实值预测变量的函数，发现变量或属性间的依赖关系，其主要研究问题包括数据序列的趋势特征、数据序列的预测以及数据间的相关关系等。它可以应用到市场营销的各个方面，如客户寻求、保持和预防客户流失活动、产品生命周期分析、销售趋势预测及有针对性的促销活动等。3.聚类聚类是将数据划分为簇的过程，根据数据本身的自然分布性质，数据变量之间存在的程度不同的相似性（亲属关系），按一定的准则将最相似的数据聚集成簇。使得属于同一类别的数据间的相似性尽可能大，不同类别中的数据间的相似性尽可能小。它可以应用到客户群体的分类、客户背景分析、客户购买趋势预测、市场的细分等。4.关联规则关联规则是描述数据库中数据项之间所存在的关系的规则，即根据一个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系。在客户关系管理中，通过对企业的客户数据库里的大量数据进行挖掘，可以从大量的记录中发现有趣的关联关系，找出影响市场营销效果的关键因素，为产品定位、定价与定制客户群，客户寻求、细分与保持，市场营销与推销，营销风险评估和诈骗预测等决策支持提供参考依据。5.特征分析特征分析是从数据库中的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征。如营销人员通过对客户流失因素的特征提取，可以得到导致客户流失的一系列原因和主要特征，利用这些特征可以有效地预防客户的流失。6.变化和偏差分析偏差包括很大一类潜在有趣的知识，如分类中的反常实例，模式的例外，观察结果对期望的偏差等，其目的是寻找观察结果与参照量之间有意义的差别。在企业危机管理及其预警中，管理者更感兴趣的是那些意外规则。意外规则的挖掘可以应用到各种异常信息的发现、分析、识别、评价和预警等方面。7.Web页挖掘随着Internet的迅速发展及Web的全球普及，使得Web上的信息量无比丰富，通过对Web的挖掘，可以利用Web的海量数据进行分析，收集政治、经济、政策、科技、金融、各种市场、竞争对手、供求信息、客户等有关的信息，集中精力分析和处理那些对企业有重大或潜在重大影响的外部环境信息和内部经营信息，并根据分析结果找出企业管理过程中出现的各种问题和可能引起危机的先兆，对这些信息进行分析和处理，以便识别、分析、评价和管理危机。数据挖掘是一种决策支持过程，它通过高度自动化地分析企业的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，做出正确的决策。这对于一个企业的发展十分重要。4数据挖掘的算法1.C4.5算法C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2)在树构造过程中进行剪枝；3)能够完成对连续属性的离散化处理；4)能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。2.K-Means算法k-means算法是一个聚类算法。给定一个含有N个数据点的数据集，以及要生成的簇的数目K。每一个分组就代表一个聚类，KN。而N得数量不能过少，否则聚类的效果就会大打折扣，一般实践中N最好大于K×10.K个分组满足每一个分组至少包含一条数据记录，每一个数据记录属于且仅属于一个分组。对于给定的K，算法首先得任务就是将数据构建成K个划分，以后通过反复迭代以改变分组的重定位技术，使得每一次改进之后的分组方案都较前一次的好。一个好的划分准则是同一簇中数据点尽可能“相似”，不同数据点中的数据尽可能“相异”。3.支持向量机支持向量机简称SVM，它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。平行超平面间的距离或差距越大，分类器的总误差越小。支持向量机可以很好地解决小样本、非线性及高维数据识别分类问题，在实践应用中与其他算法比较时，总能表现出表现出更好的性能和效果。4.Apriori算法Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法基于先验原理，它反映了子集与超集之间的关系：即频繁项集的所有非空子集都必须是频繁的，非频繁项集的所有超集都必须是非频繁的。如果项集I不满最小支持度阈值s，则I不是频繁的，即P(I)s。如果A添加到I，则结果项集（AI）不可能比I更频繁出现。因此，（I,A）也不是频繁的，即P(AI)s。因此，Apriori算法的性质主要是用于搜索频繁项集的时候对候选式的筛选过程。利用Apriori性质，能够比较好的避免盲目的搜索，提高频繁项集的查找效率。5.最大期望(EM)算法在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。最大期望经常用在机器学习和计算机视觉的数据集聚领域。6.PageRank算法如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/C(T)。其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。算法的优点是该算法是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。算法的缺点是人们的查询具有主题特征PageRank忽略了主题相关性，导致结果的相关性和主题性降低；另外，PageRank有很严重的对新网页的歧视。7.AdaBoost算法AdaBoostt是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进