数据挖掘技术调研

1、定义：数据挖掘(Data Mining,或称DM)又称为数据库中的知识发现(Knowledge Discovery from Database，简称KDD)数据挖掘是一个从不完整的、不明确的、 大量的并且包含噪声，具有随机性的实际应用数据中，提取出隐含其中潜在有用 的知识或模式的过程。基本概念：文献：数据挖掘算法及其应用研究数据挖掘中聚类分析算法的研究与应用近十多年来，数据挖掘在全世界信息产业界受到了极大的关注，并飞速发展， 究其原因，在于全球信息技术的迅速发展和互联网的快速普及造成了数据过量和 信息爆炸，人们迫切需要有这样一种技术可以帮助他们从浩如烟海的信息中找出 他们真正需要的、有价值的那

2、一部分信息和知识。而数据挖掘正是解决以上问题 的有效手段。关于数据挖掘，最简单明确的表述是从海量、混杂的数据里挖掘或 者提取有用模式或知识的一个过程。数据挖掘可以说是一门跨多个学科和知识领 域的新兴课题，它将人们应用数据的方式从原本简单的查询提升至在数据里挖掘 与发现知识以对决策行为提供支持。而为了能满足人们从数据里发现知识的需 求，来自不同领域，如数据库领域、模式识别领域、机器学习领域、人工智能领 域、统计学领域、可视化领域和并行计算领域等的诸多优秀的研究者和技术专家 都致力于研究这个新兴的课题一一数据挖掘，不断研究和创造出优秀的研究成 果，也使得数据挖掘成为了新的技术热点。通过数据挖掘可得

3、到多种知识，而这 些知识最终可以应用到多个方面，包括给相关组织和个人提供决策支持。在一般 情况下用户并不了解大量的数据中蕴藏了哪些有意义有价值的信息，所以，对数 据挖掘系统来说，应该同时能够搜索发现多种形式的信息知识，进而满足用户的 实际要求和期望。其主要有三个特点：（1）海量数据。（2）未知的有价值的规律。数据挖掘所发现的规律，应该是有用的并且不应该 是显而易见的，应该是对不同的任务来说有意义的、隐藏的规律。（3）数据挖掘是一个过程。他需要数据理解、业务理解、数据准备、评估、建 模、部署等一系列步骤，数据挖掘人员的业务能力和分析能力对成功有重要的影 响。数据挖掘的主要有任务有两点：描述型和分

4、类预测型的任务。描述型的任务是指 通过数据库数据的自身内部联系，从而得到数据库中数据关系或者数据库的概要 描述。分类预测型的任务是指通过现有的已经知道的分类的数据学习模型以及类 的标签的区别，称作为预测型和分类型。数据挖掘的由来：上世纪九十年代，随着数据库系统的广泛应用和网络技术的高速发展，数据库技 术也进入一个全新的阶段，即从过去仅管理一些简单数据发展到管理由各种计 算机所产生的图形、图像、音频、视频、电子档案、Web页面等多种类型的复杂 数据，并且数据量也越来越大。在给我们提供丰富信息的同时，也体现出明显的 海量信息特征。信息爆炸时代，海量信息给人们带来许多负面影响，最主要的就 是有效信息

5、难以提炼。过多无用的信息必然会产生信息距离（信息状态转移距离, 是对一个事物信息状态转移所遇到障碍的测度，简称DIST或DIT ）和有用知识的 丢失。这也就是约翰内斯伯粮John Naisbert)称为的“信息丰富而知识贫乏” 窘境。因此，人们迫切希望能对海量数据进行深入分析，发现并提取隐藏在其中 的信息，以更好地利用这些数据。但仅以数据库系统的录入、查询、统计等功能, 无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势, 更缺乏挖掘数据背后隐藏知识的手段。正是在这样的条件下，数据挖掘技术应运 而生。数据挖掘的研究及其应用现状：文献：数据挖掘研究现状及发展趋势数据挖掘研究现状

6、综述数据挖 掘综述每年有KDD、PAKDD和ECML&PKDD三大学术会议KDD( Knowledge Discovery in Databases)国际学术大会数据挖掘技术出现于 20世纪80年代末，它促成了数据库中的知识发现(KDD)产生。在1989年美国 底特律召开的第十一届国际联合人工智能学术会议上首次提到知识发现这一概 念，到1993年，美国电气电子工程师学会(IEEE)的知识与数据工程(Knowledge and Data Engineering)会刊出版了 KDD技术专刊，发表的论文和摘要体现了当 时KDD的最新研究成果和动态。据统计显示，从1995年至2007年召开的13次 K

7、DD国际学术大会中，9次都在美国主要城市(如纽约、芝加哥、华盛顿等)举 办，其余4次均在加拿大举办，从未在北美以外地区举办过。表 1 KDD (Krukdge Discoveiy and Ehta Nfining) Xfeetings 问InreimtiaiiaJCflaference m KDDDateCity13*August 2007San Jose. CA. USAIFAiigii&t 2006Philadelphia. FA, USAll1Aiigii&t 2005Chicago, USA邮August 2004Seattle, WA. USAgnAiigii&t 2003Washi

8、ntnL DC. USAAugust 2002EdmcDttBJ, Alberta. Canada7*August 2001San FiBnciaca, CA. USAAl倒st 2000Easton. MA. USA并AiigiEt 1999San Di 渔 CA. USA41Ali号iEt 1998New York: NY: USAAli号iEt 1997Nirapcrt Beach. CAAAli号iEt 1996Parti and, ORI1August 1995XfcmreM CanadaPAKDD( Pacific- Asia Conference on KDD)学术会议1997年

9、，也就是首届蒙特利尔KDD国际学术大会召开之后的两年，PAKDD学术会议在亚太地区顺利召开，这标志着亚太地区数据挖掘研究进入发展时期。PAKDD会议每年召开一次，从1997年至2007年的11年中，亚洲和 大洋洲的主要国家都成功举办过该项会议。表2 Pacific- Asia Conference on KDD( PAKDD)45PAKDDDateCity11世May 2007Nanjing. China10*April 2006Singapore9血May 2005Hanoi, Vietnam8*May 2004Sydney, AustraUa7血April 2003Seoul, Koiea

10、6血May 2002Taipei, Taiwan5血April 2001Houg Koug, China铲April 2000Kyoto, Japan3血April 1999Beijing, China勺血April 1998Melbomne, Australia1血1997SingaporeECML/PKDD 学术会议(European Conference on Machine Learning&European Conference on Principles and Practice of Knowledge Discovery inDatabases)是主要由欧洲大陆范围内的一项关于

11、机器学习、数据库中知识发现的 原理与实践欧洲会议的国际会议。数据挖掘主要应用领域市场分析和预测:大型超市销售分析与预测、销售渠道与价格分析等；金融、银行；如自动投资系统、可预测最佳投资时机；工业生产：主要用于发现最佳生产过程；科学研究:天文定理的发现、用于分析地壳的构造活动等；Web数据挖掘；站点访问模式分析、网页内容自动分类;表1.数据挖掘应用比重表2.数据挖掘不同领域增长率liidustnes/fieldsPr叩 cation (%) 2003-2005Propoi1ian(%)June 2006Proportion%)June 2007CRM34.9038.7426.10Banking3

12、4.230.9023.90Direct MarketingFundraising22.8219.8220.30Science11 4110.8118.S0Fraud Detection20.8121.6218.80Telecom15 4412.6115.20Credit Scoraig23 4913.9213.80Othed7.3813.5113.00Biotech Genoniics73815.3211.60Web usage mining10.8110.10Retail16.789.9110.10liidustnes/fieldsProportion of growth fioin 200

13、6 to 2007Banking3200%Eutertaininent Music200%Science117%Health care,-HR100%Medical. Pharnia63%Jutik email Anti- spam50%Telecom50%Government Military43%E- commerce33%Manufectiiriiig29%数据挖掘的算法平台发展第一代数据挖掘软件，支持一个或少数几个数据挖掘算法，这些算法设计用于数 据向量挖掘，多用于商业系统。Salford Systems公司早期的CART系统就属于这 种系统。新加坡国立大学研制的CBA,其基于关联规则

14、的分类算法，能从关系数 据或者交易数据中挖掘关联规则，利用关联规则进行分类和预测。第二代数据挖掘软件系统与数据库管理系统(DBMS)集成，支持数据库和数据 仓库，具有高性能的接口，具有较高的可扩展性。能够挖掘大数据集以及更复杂 的数据集和高维数据，但这一代的数据挖掘软件只注重模型的生成，典型代表有DB Miner 和 SAS Enterprise Miner o第三代数据挖掘系统的特点是和预言模型系统之间能够实现无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到语言模型系统中，由数据挖 掘软件产生的预言模型能够自动地被操作系统吸收，从而与操作型系统中的语 言模型相联合提供决策支持的功

15、能。它能够挖掘网络环境下(Internet/Intranet/Extranet)的分布式和高度异质的数据，并且能够有效地和操作 型系统集成。其缺点是不能支持移动环境。这一代数据挖掘系统关键的技术之一 是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别的支持。SPSS Clementine就是属于这一代的产品。第四代软件能够挖掘嵌入式系统、移动系统和普遍存在的计算设备产生的各种类 型的数据。目前国外技术成熟、有较强产业化能力的数据挖掘软件，其中主要的有:SAS Enterprise Miner: SAS 系统全称为 Statistics Analysis System

16、,是美国使用 最为广泛的三大著名统计分析软件(SAS, SPSS和SYSTAT)之一，被誉为统计分 析的标准软件。1997年SAS发布了 SAS Enterprise Miner,这个工具为用户提供 了用于建模的一个图形化流程处理环境，并且它有一组常用的数据挖掘算法，包 括决策树、神经网络、回归、关联等，还支持文本挖掘。SAS主页地址： HYPERLINK / /SPSS Clementine: SPSS是世界上最早的统计分析软件之一。1998年末SPSS收购了英国ISL公司，通过继承获得了这家公司的Clementine数据挖 掘包。Clementine是首次引入数据挖掘流概念的产品之一。它允

17、许用户在同一个工作流环境中清理数据、转换数据和构建模型。 HYPERLINK /software/analytics/spss/ /software/analytics/spss/IBM Intelligent Miner:包括分析软件工具 Intelligent Miner for Data和 IntelligentMiner for Text,不仅可以寻找包含于传统文件、数据库、数据仓库和数据中心中的隐含信息，更允许企业从文本信息中获取有价值的客户信息。Intelligent Miner使用预测模型标记语言(Predictive Modeling Markup Language, PMML

18、)来导出 挖掘模型，这种语言由数据挖掘协会(Data Mining Group, DMG)定义。Insightful Miner( I-Miner):由美国Insightful公司开发的具有高度可扩展性的数据分析和数据挖掘软件。目前在金融、生物科技、政府机构等企事业单位应用非常广泛。此外，还有Oracle公司从Thinking Machines公司取得的Darwin; Unica公司开发 的 Affinium Model; Angoss Software所开发的 Knowledge SEEKER;加拿大 Simon Fraser大学开发的DBMiner;SGI公司和美国Standford大学联

19、合开发的Minset;HNC公司开发的用于信用卡诈骗分析的Database Mining Workstation;IBM公司 Almaden 研究中心开发的 Quest; Neo Vista 开发的 Decision Series;以及 KEFIR 系 统、SKICAT系统等。国内也有不少新兴的数据挖掘软件，如:D Miner , iD Miner , Ms Miner , AR Miner, Scope Miner ,Open Miner 等相关的一些企业、机构主要有：复旦德门，数海时代，华院数据，海尔青大， 宇动源，亦策，中科院计算技术所，东北大学等等。夕德黯 冬数据挖掘平台软件份额200

20、7截止排名前10位中没有国内研发的数据挖掘软件;我国研发的DM平台尚未被国际市场认可，国内DM软件产业还不够成熟5.数据挖掘常用建模算法文献：数据挖掘算法及其应用研究数据挖掘中聚类分析算法的研究与应用数据挖掘中的聚类方法及其应用聚类算法研究(1)决策树方法(Decision Tree)定义：决策树是一个利用像树一样的图形或决策模型的决策支持工具，包括随机事件结果，资源代价和实用性。决策树方法主要用于数据分类，一般分成两个阶段:树的构造和树的修剪。首先利用训练数据生成目标 问题 选择方案 效果 概率重要性 权衡 决定一个测试函数，根据不同取值建立树的分支;在每个分支子集中重复建立下层结点和分支，

21、从而生成一棵决策树。然后对决策树进行剪枝处理,最后把决策树转化为规则，利用这些规则可以对新事例进行分类。基于决策树的分类方法与其它分类 方法比较起来，具有速度较快!较易转化成简单且容易理解的分类规则。较易转换 成数据库查询语句等优点，尤其在问题维数高的领域可以得到很好的分类结果。特点在于简单易于理解且应用广泛，是一种分类函数逼近手段。缺点在于每个分 支的判定条件过于严格，实际应用中可能会带来麻烦。(2)遗传算法(Genetic Algorithm)遗传算法是一种优化技术，它利用生物进化的一系列概念进行问题的搜索，最终达 到优化的目的。在遗传算法的实施中，首先要对求解的问题进行编码（称为染色体）

22、, 产生初始群体，然后计算个体的适应度,再进行染色体的复制、交换、突变等操作, 产生新个体。重复这个操作，直到求得最佳或较佳个体。在数据挖掘中，往往把数 据挖掘任务表达为一种搜索问题，使用遗传算法强大的搜索能力，找到最优解。遗 传算法广泛地应用于组合优化、机器学习、信号处理、自适应控制等领域。算法主要步骤：把问题的解表示成“染色体”，在算法中以二进制编码成串。在执行遗传算法之前，给出一群“染色体”，也即是假设解。把这些假设解置于问题的“环境”中。按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交 叉，变异过程产生更适应环境的新一代“染色体”群。最后进化到最适应环境的一个“染色

23、体”上，它就是问题的最优解。关联挖掘数据中迅速找出各个数据对象之间潜在的有价值有意义联系，也就是在大型的数 据库中，快速找到各种事物之前潜在的有价值有意义的联系，并且用一定的规则 表现出来，通过推理、积累形成知识之后，得出非常重要的相关联的结论，进而 给当前的市场管理者提供决策依据。例如：沃尔玛进行的有关“牛奶与尿不湿” 的关联结果。因为在实际生活应用中有很多关联挖掘成功的范例，以及关联挖掘 非常好的实用性，使得目前有关关联挖掘的应用和研究成为一个研究非常深入和 十分活跃的研究领域，目前，已经研究出了很多关联挖掘的算法并且新的算法也 在不断的出现，并且实际应用的领域也在不断扩大。关联规则挖掘技

24、术已经被广 泛应用在商业金融行业中，一些知名的电子商务站点也从强大的关联规则挖掘中 的受益。神经网络法(Neural Networks )神经网络来源于神经生物学和生理学中有关神经细胞计算本质的研究工作。有很 多种不同的神经网络，可以给不同的学习目的提供应用。前馈神经网络是一种常 见的用于分类的算法。神经网络有很好的抗噪音的能力，并且针对未知数据也一 样有很好的预测分类能力，有很高的分类精准度。不过，训练过程一般比较长是神经网络的一大缺点。另外，神经网络算法所得到的结果可解释性很差，差不多相当于黑盒。已有近40种神经网络模型，包含反传网络、感知器、自组织映射、Hopfield网络、波耳兹曼机、

25、适应谐振理论等等。BP(Back Propagation)网络，又名误差 反向传播算法，是其中最为成熟的神经 网络算法，由Rumelhart等人于1985 年提出，它是一种通过误差反向传播算 法训练数据的多层前馈神经网络，同样 也是人们当前最广泛运用的神经网络模 型。BP神经网络可以学习和存储大量的输入-输出模式映射关系，而不需要预先 揭示表现此种映射关系的数学模型。其学习规则为最速下降法，利用反向传播来 不断修正网络的阈值和权值，使建立的神经网络误差的平方和最小。BP神经网 络的误差反向传播算法的学习过程包括信息的正向传播过程与误差的反向传播 过程。输入层的各个神经元接受外界的输入信息，再将

26、其传送到隐含层各个神经 元。中间的隐含层是内部信息转换层，对信息进行处理。依据对信息变化能力的 需要可以将中间层设计为单个隐含层或者多个隐含层的结构；最后的隐含层将信 息通过进一步处理之后传送给输出层各神经元，这样就完成了一次学习的正向传 播过程，最后输出层对外界输出信息处理后的结果。若实际的输出结果与预期不 同，则进行误差反向传播过程。误差首先通过输出层，再根据误差梯度下降的方 法调整各层神经元的权值，依次向隐含层和输入层逐层反向执行。反复进行信息 正向传播与误差反向传播是各层神经元不断修正权值的过程，也同样是神经网络 进行学习训练的过程，这个过程会不断执行到该网络的输出数据的误差减小至满

27、足需求的程度，或学习次数达到事先定义的值为止。只要给定足够多的隐含单元， BP神经网络可以逼近任何多元非线性连续函数。反向传播算法通过不断处理一 个训练样本集，将每次的处理结果与该样本已知类别进行比较，用所得的误差帮助 完成学习。对于每个训练样本，反向修改其权值，即从输出层开始，通过之后的 隐含层，直到最前面的隐含层，通过迭代修改，当权值收敛时学习过程终止，因 此它可以得出误差值非常小的输出结果，将其用于分类、预测等往往会达到非常 好的效果。聚类规则聚类分析是数据挖掘技术中非常重要的一个部分，而它的实现通常和最近邻技术 紧密相关。聚类分析指将物理或者抽象数据对象集合分组成由相似的数据对象组 成

28、的多个类的分析过程，它的目的就是在相似的基础上收集数据来进行分类。聚 类分析就是依据数据彼此之间的相似性将其分类到不同的类或簇（Cluster）这样 的一个过程，在同一个类中的对象彼此之间非常相似，而不同类间的对象之间具 有较高的相异性。聚类是一个与分类不同的无监督的学习过程，并且与分类不同， 分类学习必须事先对数据进行类别标记，而聚类的无监督学习则不需要预先对训 练数据进行预处理，如事先定义类以及对训练实例做类标记，它能够在聚类算法 执行过程中自动对数据进行标记。聚类不是示例型学习，是观察型学习。聚类分 析是一个不断探索的分析过程，分类时根据数据本身进行分类而无需预先确定分 类标准。采用不同

29、的方法进行聚类分析得到的结果往往不尽相同。从现实应用角 度分析，聚类无疑为数据挖掘的重要任务之一。它不仅可以作为一个单独的工具， 有效获取数据的分布状况，观察每个类中数据的特征，从而进一步分析所研究的 特定的聚类集合，也能够作为分类和相关性分析等其他算法的预处理步骤。聚类能够发现数据之间的潜在关系，从而进一步得到数据的分布模式，因此在数据分 析、图像处理、模式识别、市场分析等领域中它已被广泛应用。聚类分析所涉及 的领域包括：统计学、机器学习、市场学、生物学、空间数据技术和数据挖掘等。 因为聚类可以在多个领域广泛应用，至今相关研究者已提出了大量的、各不相同 的聚类算法，可以将其概括为五大类：划分

30、法、层次法、基于密度的方法、基于 网格的方法与基于模型的方法等。1）划分法（partitioning methods）给定一个数据集，共包含N条记录，划分法把它划分成K个分组，一个分组 即为一个聚类，K忍N。并且这K个分组满足以下条件：每个分组包含数据记录数目必须大于等于一；每条数据记录仅能属于一个分组。需要注意的是，部分模糊聚类算法可以不满足条件。预先设定K之后算法会 进行初始分组，然后反复迭代改变分组以使得每次改进的分组方法表现更好。标 准为：每个分组内的数据记录之间的距离越小越好，不同分组之间的数据记录的 距离越大越好。使用此基本思想的算法主要有K-MEANS 算法、CLARANS 算法

31、、K-MEDOIDS算法，由于K-MEANS算法是其中最著名也是最常用的，所以在此以K-MEANS算法为例进行分析。以数据点到所在类中心的某种距离（坐标中的欧氏 距离）作为优化的目标函数，并利用求函数极值的方 法得到迭代运算的调整规则。1）从N个数据对象中随机选取K个对象作为初始聚类的中心点（KN）2）根据每个聚类对象的中心点，计算每个类中对象与各自中心点的距离； 并根据最小距离重新对相应对象进行划分；3）重新计算已经得到的各个类的中心4）迭代循环23步直至每个聚类中心不再发生明显变化为止。此类算法的优点是可伸缩和效率高，并且在数据分布平均的情况下聚类效果良 好。但是它需要人工预先设定要得到的

32、类的数目k,在用于发现大小差别很大的 类、或者类呈现非凸面形状的情况下效果很不理想，而且它对于噪声和离群数据 敏感，即使只存在较少的该类数据也会对聚类效果产生很大的影响。2）层次法（hierarchical methods）层次法是将给定的数据集层次似的分解，直至满足某种条件为止。它可以分成“自 底向上”（合并）和“自顶向下（分裂）”两类方案。在“自底向上”方案中，初 始时每条数据记录都组成一个单独的组，在之后的迭代过程中，它将那些距离相 近的组合并为一个组，直至全部的记录组成一个分组或满足某个条件为止。而“自 顶向下”方案，初始时把全部数据对象放入一个组，在每一步迭代中将一个组分 裂成更小的

33、组，直至每条数据记录在单独的一个分组或满足某个条件为止。代表 算法有：BIRCH算法、CURE算法、CHAMELEON算法等，其中CURE算 法最具代表性。CURE算法是基于代表对象方法和基于质心方法中间的策略， 它选择数据空间中具有代表性的固定数目的点，而非单个对象或质心来代表一个 类。类的代表点产生方式：首先选择类中分散的数据对象，之后按照收缩因子（通 常取值为某个特定分数）向类的中心进行收缩。算法进行的每一步中有最小距离 的代表点对的两个类合并，其中每对点彼此来自不同的类。算法核心步骤如下：（1）从原始数据对象集中抽取部分数据对象作为一个随机样本S；（2）对样本S进行划分；（3）将每个划

34、分进行局部的聚类；（4）使用随机取样方法排除离群点。若某个类增长速度过慢，则删除它；（5）对局部的类再进行聚类。落在每个新形成的类中的代表点按照用户设定的 收缩因子a进行收缩即向类的中心移动；（6）使用对应的类标签标记数据。算法优点在于复杂度不高、高效；对离群点 的处理更为健壮；能够识别大小变化较大及数据分布呈非球形的类；对大型数据 库同样具有较好的伸缩性；支持不同大小及复杂形状的聚类；敏感度低。缺点为 不能处理分类属性。3）基于密度的方法（density-based methods）基于密度的方法和其它方法相比，最根本区别在于：它对数据对象聚类的依据是 基于密度，而并非基于各种各样的距离。因此，它可以解决基于距离一类的算法 仅能够发现接近圆形的凸面形聚类的问题。它的指导思想为只要某个区域内数据 点的密度大于某个设定阈值则该数据点就可以被添入与它相近的聚类中。代表算 法有：DBSCAN 算法、DENCLUE算法、OPTICS算法等，其中DBSCAN算 法是最具代表性和最被广泛应用的。4）基于网格的方法（grid-based methods）基于网格的方法把数据空间分割为具有有限个单元（cell）的网格结构，处理对象都 为单个单元