文献综述Word文件下载.docx

1、GarMer Group的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首1，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 数据挖掘诞生于上世纪80年代，在1989年召开的第11届国际人工智能联合会议上，首次以专题形式对数据库中知识发现（KDD，Knowledge Discovery in Database）进行了讨论，即最初的数据挖掘2。在此之后又多次召开国际性会议对数据挖掘进行专门的讨论研究。数据挖掘在其产生之初就是面向应用的，并且已在商业、金融等领域发挥着积极作用。在商业市场上数据挖掘的应用需求很大，而聚类分析

2、作为数据挖掘的重要分支技术已被国内外众多学者广泛研究了多年，其研究最早可追溯至上世纪40年代。 1995年在美国计算机年会上，提出了数据挖掘的概念，即通过从数据库中抽取隐含的、未知的、具有潜在使用价值信息的过程。数据挖掘是KDD过程中最为关键的步骤3。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1993年国家自然科学基金首次支持对该领域的研究项目，1999年 ，第三届PAKDD（Pacific-Asia conference on Knowledge Discovery And Data Mining）会议在北京召开，加快了国内在该领域的研究步伐。目前，国内许多科研单位和高等院校

3、竞相开展数据挖掘的基础理论及其应用研究，如清华大学、中科院计算技术研究所、空军第三研究所 、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中科技大学 、复旦大学、浙江大学 、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和改造;南京大学、四川大学和上海交通大学等单位探讨、研究 了非结构化数据的知识发现以及 Web数据挖掘。数据库知识发现（knowledge Discovery in Databases，KDD）及其核心技术数据挖掘 （Data Mining，DM）4应运而生。数

4、据挖掘是指通过采用自动或半自的手段,从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 。发现知识的方法可以是数学的，也可以是非数学的; 可以是演绎的，也可以是归纳的。挖掘出的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此 ，数据挖掘是一门交叉学科，涉及人工智能技术，统计技术与数据库技术等多种技术 。在聚类分析应用的诸多领域人们提出了大量的聚类算法，并形成了系统的方法体系 。在机器学习领域，聚类属于无监督学习。在模式识别领域，聚类是非监督模式识别的一个重要分支。目前数据挖掘的相关文献中

5、存在的大量聚类方法，大体可以划分为层次的方法、划分的方法、基于密度的方法、基于网格的方法、神经网络的方法、模糊聚类方法以及基于统计学的方法等。所有聚类方法在实际的应用中具有各自的优点，但同时也存在着不同方面的缺陷。因此，尽管已存在众多的聚类方法，但是人们仍在坚持不断的研究聚类能力强、执行效率高，设计简单易行的聚类方法。从目前的情况来看，聚类方法的研究大部分集中在计算机科学领域，更多的侧重点放在了聚类算法的研究上，或者通过结合其他方法对现有的聚类方法进行算法上的改进。但是有时许多算法的改进是以牺牲执行效率为代价的 。2数据挖掘相关内容介绍2.1 数据挖掘数据挖掘（Data mining），又译为

6、资料探勘、数据采矿。它是数据库知识发现（Knowledge-Discovery in Databases，简称：KDD）中的一个步骤5。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠过去的经验法则）和模式识别等诸多方法来实现上述目标。通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示3个步骤。数据挖掘的任务有关联分析、聚类分析、分类分析、异常分析、特异群组分析和演变分析等。数据挖掘任务有六项 : 关联分析、时序模式、聚类、分类、偏差检测和预测。

7、数据挖掘任务和过程概述如下:（l）关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度 。 （2）时序模式 通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。聚类分析与分类分析在轨道交通系统中的应用在时序模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分比（阀值）的规则。这些规则会随着形式的变化做适当的调整。时序模式中，一个有重要影响的方法

8、是“相似时序”。用“相似时序”的方法，要按时间顺序查看时间事件数据库 ，从中找出另一个或多个相似的时序事件 。 （3）聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。在 同一类别中，个体之间的距离较小，而不同类别上的个体之间的距离偏大。聚类增强了人们对客观现实的认识，即通过聚类建立宏观概念。聚类方法包括统计分析方法，机器学习方法，神经网络方法等。80年代初，Michal提出的概念聚类技术及其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。 （4）分类 分类是数据挖掘中应用最多的任务。分类是找出一个类别的概念描述，它代表了这

9、类数据的整体信息，既该类的内涵描述。一般用规则或决策树模式表示。该模式能把数据库中的元组映射到给定类别中的某一个分类组当中。一个类的内涵描述分为特征描述和辨别性描述。特征描述是对类中对象的共同特征的描述。辨别性描述是对两个或多个类之间的区别的描述。特征描述允许不同类中具有共同特征。而辨别性描述对不同类不能有相同特征。辨别性描述用的更多。分类是利用训练样本集（己知数据库元组和类别所组成的样本）通过有关算法而求得。目前，分类方法的研究成果较多，判别方法的好坏，可从三个方面进行:预测准确度（对非样本数据的判别准确度）、计算复杂度（方法实现时时间和空间的复杂度）、模式的简洁度（在同样效果情况下，希望决

10、策树小或规则少）。 在数据库中，往往存在噪声数据（错误数据）、缺损值、疏密不均匀等问题。他们对分类算法获取的知识将产生坏的影响。（5）偏差检测 数据库中的数据常有一些异常记录 ，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。（6）预测 预测是利用历史数据找出变化规律 ，建立模型，并用此模型来预测未来数据的种类、特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变量建立线性聚类分析与分类分析在轨道交通系统中的应用或非线性回归方程。预

11、测时，只要输入任意的时间值，通过回归方程就可求出该时间的状态 。近年来，发展起来的神经网络方法，比如模型的方法，它实现了非线性样本的学习，能进行非线性函数的判别。分类也能进行预测，但分类一般用于离散数值。回归预测用于连续数值。神经网络方法预测既可用于连续数值，也可以用于离散数值。2.2 数据挖掘方法： （1）分类（Classification） （2）估计（Estimation） （3）预测（Prediction） （4）相关性分组或关联规则（Affinity grouping or association rules） （5）聚类（Clustering） （6）描述和可视化（Descript

12、ion and Visualization） （7）复杂数据类型挖掘（Text, Web ,图形图像，视频，音频等） 2.3数据挖掘步骤： （1）数据收集 大量丰富的数据是数据挖掘的前提，没有数据,数据挖掘也就无从谈起。因此数据收集是数据挖掘的首要步骤。数据可以来自于现有事务处理系统，也可以从数据仓库中得到。（2）数据整理 数据整理就是消除噪声或不一致数据，是数据挖掘的必要环节。由数据收集阶段得到的数据可能有一定的“污染”，表现在数据可能存在自身的不一致性 ，或者有缺失数据的存在等，因此数据的整理是必须的。通过数据整理，可以对数据做简单的泛化处理，从而在原始数据的基础之上得到更为丰富的数据信息

13、，进而便于下一步数据挖掘的顺利进行。（3）数据挖掘 聚类分析与分类分析在轨道交通系统中的应用，利用各种数据挖掘方法和工具对数据进行分析。（4）信息表示 信息表示是使用可视化和知识信息表示技术，向用户提供挖掘的知识信息，是数据挖掘结果呈现的重要手段。有效清晰的挖掘结果信息表示将极大地促进决策的准确性和高效性。（5）分析决策 数据挖掘的最终目的是辅助决策。决策者可以分析数据挖掘的结果，结合实际情况，调整决策策略等。总之数据挖掘过程需要多次的循环反复，才有可能达到预期的效果 。由上述步骤可看出，数据挖掘牵涉了大量的准备工作与规划工作，事实上许多专家都认为整套数据挖掘的过程中，有80%的时间和精力是花

14、费在数据预处理阶段，其中包括数据的净化、数据格式转换、变量整合，以及数据表的链接。可见，在进行数据挖掘技术的分析之前，还有许多准备工作要完成。3.5四种聚类分析方法3.51层次聚类方法 层次聚类算法（Hierarchical Clustering）是一种常见的聚类分析算法，层次的方法对给定的数据集合进行层次的分解。根据层次分解方式的不同可以分为凝聚和分裂两大类。层次聚类算法中将数据集分层建立簇，形成一棵以簇为节点的树。凝聚的层次聚类方法按自底向上进行层次分解，而分裂的层次聚类方法按自顶向下进行的层次分解。凝聚层次聚类方法，首先将每个对象作为单独的一个类，计算类间的距离，然后逐渐合并距离相近的类

15、为较大的类，方法结束时所有的对象都在一个类中，或者满足某个终止条件。分裂的层次聚类方法与凝聚方法正好相反，开始时将所有的数据对象置于一个类中，然后类被逐渐分裂为更小的类，直到每个类只包含一个对象为止，或者达到了某个终止条件。在上述两类方法中通常以用户自定义希望得到的类的数目作为终止条件。基本的层次聚类方法是由Kaufman和Rousseeu提出的凝聚方法 AGNES（Agglomerative Nesting）7和分裂方法DIANA（Divisive Analysis）8。层次聚类方法虽然简单但计算复杂度比较高，很难应用于大型数据集。此外单纯的层次聚类算法的终止条件模糊，而且执行合并或分裂类的

16、操作不可撤销，因为一旦一组对象被合并或分裂，下面的处理将在新生成的类的基础上进行，类之间也不能交换对象，因此可能导致低质量的聚类结果。另外，由于需要对大量的对象或类进行检查和估算才能确定类的合并或分裂，所以这种方法不具有很好的可伸缩性。针对这些不足人们提出大量改进的层次聚类算法来以提高聚类速度，改善聚类质量。这类方法包括 BIRCH、CURE、ROCK、Chameleon算法等。BIRCH是由Zhang，Ramakrishnan和Linvy 提出的一种综合的方法9，它首先将对象划分成树形结构，然后利用其他的聚类算法对叶结点进行聚类。此方法中引进了两个概念：聚类特征（CF，Cluster Fea

17、ture）和聚类特征树（CF树），用来概括聚类描述。CF树使一个类可以用对应的聚类特征来表示，而不必用具体的数据点表示，提高了算法的性能和可扩展性。CURE 算法是一个自底向上的层次聚类算法，它是由Guha，Rastogi和Shim提出的（Clustering Using Representatives）10，该算法和划分算法结合在一起来克服易发现球形簇的缺陷。CURE算法在计算类间的距离时，它不用单个质心或对象来表示一个类，也不是用所有的点，而是选取数据集中一组固定数目的具有代表性的点来表示一个类。换言之它是用多个对象而不是单个对象来代表一个类。CURE算法弥补了利用单个代表点或基于质心的方

18、法的缺陷，能够识别非球形及大小不同的类。同时类或离散点的收缩能很好地过滤孤立点，降低了算法对孤立点的敏感性。ROCK方法11是在CURE方法的基础上改进的适用于分类数据的一种层次方法。ROCK算法通过比较两个类的聚集的互连性与用户定义的静态互连性模型来度量两个类之间的相似度。CURE算法忽略了两个不同类中对象的聚集互连性，ROCK 算法虽然强调了对象间的互连性，却忽略了对象间的近似度。基于对CURE和ROCK缺点的观察，Karypis，Han和Kumar（1999）提出了Chameleon 方法12。Chameleon 是一个在层次聚类中采用动态模型的聚类算法。在它的聚类过程中既考虑了互连性，

19、又考虑到了近似度，尤其是类内部的特征，来确定高相似度的子类。由于动态模型的合并过程有利于自然的和同构的聚类的发现，因此Chameleon算法在发现高质量的任意形状的数据集的聚类方面有更强的能力12。上述几种层次聚类方法有效的提高了算法的聚类能力，但同时延长了算法的执行时间。因此为了进一步提高算法的效率人们又提出许多新的算法，但都是对算法聚类能力和执行效率的一个折中，提高速率的同时聚类结果的准确性相应的降低了。3.52基于密度的方法 很多聚类算法使用距离来描述数据对象之间的相似性从而对数据集进行聚类，这样的方法易发现球状的类。但是，对于非球状的数据集仅用距离来描述是不够的。针对这种情况，提出了基

20、于密度的聚类方法（density-based method）。这类算法从数据对象的分布密度出发，将类看作是数据空间中被低密度区域分割开的高密度对象区域。算法的主要思想是当邻近区域的密度（数据对象或数据点的数目）大于某个阈值时，就继续对其聚类。也就是说，对于给定类中的每个数据点，在给定半径的区域内必须至少包含最少数目的点。因此该算法可以用来过滤孤立点数据，发现任意形状的簇。DBSCAN和其扩展算法OPTICS是两个典型的基于密度的方法。DBSCAN（Density-Based Spatial Clustering of Application with Noise，具有噪声的基于密度的聚类应用）

21、算法13是一个基于高密度连接区域的聚类方法。该算法根据一个密度的闭值来控制类的增长，它把类定义为密度相连的点的最大集合。每个类的内部点的密度比类外点的密度要高得多。DBSCAN算法能够在具有噪声的空间数据库中识别各种复杂形状的簇类且聚类结果不受输入顺序的影响。但是该算法对参数的设置敏感，参数值的微小变化常常会导致聚类结果的巨大差异。为了进一步提高算法的执行效率，周水庚14等人从不同方面对DBSCAN算法进行了相应的改进，改进后算法的效率明显提高，且降低了对设置参数的敏感性。由Ankerst15等提出的OPTICS（Ordering Points to Identify the Clusteri

22、ng Structure，通过点排序识别聚类结构）算法33是一种基于类排序的聚类分析方法。OPTICS算法类似于DBSCAN算法，可看作对DBSCAN的扩展。但是它并不显示地产生数据集聚类，而是为自动和交互的聚类分析计算一个类次序，这个次序代表数据的密度的聚类结构。它所包含的信息等价于从一个宽广的参数设置所获得的基于密度的聚类。OPTICS算法和DBSCAN算法在结构上是等价的，因此算法的时间复杂度相同。此外OPTICS算法克服了DBSCAN参数设置复杂的缺点。3.53基于网格的方法 基于网格的算法也是一种常见的聚类分析算法。该算法使用一种多分辨率的网格数据结构，把空间量化为有限数目的单元，形

23、成了一个网格结构。然后对量化后的网格结构进行聚类。此类算法处理速度很快，处理时间独立于数据对象的数目。算法还存在一些不足，只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此外，聚类的精度取决于网格单元的大小。因此该算法不适用于发现高维数据的情况，因为网格单元的数目会随着数据维数的增加而成指数增长。STING算法和CLIQUE算法是两种典型的基于网格的聚类算法。STING16（Statistical Information Grid，统计信息网格）是基于网格的多分辨率聚类分析算法。算法将数据空间划分为若干个矩形单元。对于不同级别的分辨率，通常会存在多级矩形单元，这些单元形成了一个层次结构。其

24、中每个高层的单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息，如最大值、最小值、均值等会被预先计算和 存储以便用于查询处理。与其他聚类方法相比，STING 算法的网格结构有利于并行处理和增量更新，算法效率高。该算法聚类的质量取决于网格结构最底层单元的粒度。粒度较小时，聚类质量较高，同时处理的代价也会显著增加。网格结构的低层粒度较大时，速度非常快但会降低聚类分析的质量。CLIQUE17（Clustering with wavelets）算法是另一个常用的基于网格的算法。它综合了基于密度和基于网格的聚类方法，用于对高维数据进行聚类。算法利用了关联规则挖掘中的先验性质：如果一个 m维单元

25、是密集的，那么它的 m-1 维上的投影也是密集的。CLIQUE算法的基本思想为：给定一个多维数据点的大集合，通常情况数据点在数据空间中的分布不均衡，CLIQUE 算法区分空间中稀疏的和密集的区域，以发现集合的全局分布模式。若一个单元中包含的数据点数目超过了某个输入的模型参数，则该单元是密集的。在算法中类被定义为相连的密集单元的最大集合。CLIQUE 算法能够自动地发现高维的子空间，这些子空间中存在着高密度聚类。算法对数据的输入顺序敏感性较低，同时当数据的维数增加时表现出良好的可伸缩性。但是由于算法的简化聚类结果的精确性将会降低。3.54基于模型的方法 基于模型的聚类方法为每个簇类假定了一个模型

26、，然后试图在给定的数据和某些数据模型之间寻求他们的最佳拟合。该方法经常是基于下面的假设，即数据是根据潜在的概率分布生成的。基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。也能基于标准的统计数字自动的决定聚类数目，同时会考虑到噪声数据或离群点，进而产生健壮的聚类分析方法。基于模型的方法主要有两类：统计学方法和神经网络方法。大部分概念聚类都采用了统计方法，这类聚类方法大都是建立在数据与潜在的概率分 布相拟合这一假设基础之上的，它利用概率参数来帮助确定概念或聚类。COBWEB算法 18是一种常用的增量式概念聚类方法，方法采用符号量来描述输入对象，并采用分类树 的形式创建一个层次聚类

27、。每一个划分相当于分类树中的一层。该算法不需要提供相应的参数，可以自动修正划分类的数目，但是COBWEB算法的存在一定的局限性，它假设每个属性上的概率分布相互独立，而实际上属性之间常常是相关联的。神经网络方法中每个聚类被描述成一个标本，然后将每个标本作为聚类的原型，根据 某种度量，将新的对象分配到与标本最相似的聚类之中。主要的方法包括：竞争学习方法 和自组织特征映射方法（SOFM，Self-Organizing Feature Map）。4.3两步聚类 构建聚类特征树（CFT），开始时，把某个观测量放在树的根节点处，它记录有该观测量的变量信息，然后根据指定的距离测度作为相似性依据，使每个后续观

28、测量根据它与已有节点的相似性，放到最相似的节点中，如果没有找到某个相似性的节点，就为它形成一个新的节点。 使用凝聚聚类法对聚类特征树的节点进行分组，它通过比较BIC AIC ,确定最优的聚类个数建CFT树时，如果指定了聚类个数等变量，而观测量又很多的话，可能发生CFT树长满不能再生长的情况，那些没有长在树上的观测叫做噪声，可以调整参数重新计算让CFT树可以容纳更多的观测，也可以把它们直接归入某个类或者直接丢弃。被丢弃的观测量生物称为局外者（outlier）20。参考文献1 陈婧.基于数据挖掘的网络安全态势预测研究D.扬州.扬州大学.20102李雄飞，李军.知识发现与数据挖掘M.北京.高等教育出

29、版社.2003.113毛国军.数据挖掘技术与关联规则挖掘算法研究D.北京.北京工业大学. 2003.4王莉.数据挖掘中聚类方法的研究D.天津.天津大学.2003.5张宾,贺昌政.自组织数据挖掘方法研究综述 J.哈尔滨工业大学学报,2006,10（4）:35-47 6石云平. 数据挖掘与统计学的关系研究J.国外电子测量技术.2009,（6）:65-677 Kaufman L. Rousseeuw P.J. Finding Groups in Data:An Introduction to Cluster Analysis M.New York:John Wiley&Sons, 1990.8 R. Ng,J. Han. Efficient and effective clustering method for spatial data miningC.Proc.1