基于层次的孤立点检测算法设计及实现.doc

毕业设计(论文)题 目 基于层次的孤立点检测算法设计及实现 学院名称 计算机科学与技术学院 指导教师 肖基毅 职 称 教授 班 级 本05计算04班 学 号 20054440428 学生姓名 李敬康 2009年5月29目 录摘要iiiAbstractiv第一章 绪论11.1研究背景及研究意义11.3论文组织结构2第二章 相关知识32.1数据挖掘概述32.1.1数据挖掘概念32.1.2数据挖掘过程42.1.2数据挖掘算法组成52.2聚类分析52.2.1聚类算法简介62.2.2基于层次的聚类方法82.2.3距离、相似系数及聚类分析中的数据类型142.3孤立点分析172.3.1基于统计的方法182.3.2基于距离的孤立点检测算法182.3.3基于偏离的孤立点探测202.4本章小结20第三章 算法设计与实现213.1算法相关定义213.2算法描述223.3算法实现243.3.1数据结构定义243.3.2算法函数说明253.4算法分析303.4.1算法复杂度303.4.2算法的局限性303.5本章小结30第四章 结论31参考文献32谢辞33摘要摘要：孤立点检测是数据挖掘的一个重要方面，因其独特的知识发现功能而得到较为深入的研究。孤立点检测算法己经在金融欺诈检测、网络入侵检测、生态系统失调天气预报等风险控制领域得到了广泛的应用。聚类分析和孤立点检测技术己经广泛应用于模式识别、数据分析、图像处理、市场研究等许多领域。聚类及孤立点检测算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。本文介绍了数据挖掘理论，在深入研究聚类分析和孤立点检测算法的基础上提出了基于层次的孤立点检测算法。给出了算法较为详细的描述，阐述了算法中各个函数的功能。该算法基于层次方法，采用欧几里得距离进行凝聚的层次聚类。根据聚类中含有单一数据元素的类数来确定初始孤立点个数，然后根据距离阀值判断是否为孤立点。通过对算法的性能进行分析，该算法的时间复杂度为，空间复杂度为，其中N是数据规模。试验结果表明，基于层次的孤立点检测算法能基本实现孤立点的检测，并对孤立点进行精确性分析。关键字：数据挖掘；层次聚类；凝聚；孤立点检测；距离AbstractAbstract: Outlier detection is an important aspect of Data Mining，which has get more depth research because of its unique knowledge discovery functions.Today，there are lots of efficient outlier detection algorithms which are widely used in financial fraud detection，network instruction detection，ecosystem imbalance，Weather forecast and other risk control areas.Clustering analysis and outlier detection,as important parts of data mining,are widely applied to the fields such as pattern recognition,data analysis ,image processing,and market research.Research on clustering analysis and outlier detection algorithms has become a highly active topic in the data mining research.In this thesis,the author presents the theory of data mining,and based on deeply analysis the algorithms of clustering and outlier detection,the author advances hierarchical-based outlier-detection algorithm. Elaborates the idea of the algorithm,expounds the functions of algorithm.The algorithm based on hierarchical clustering and used Euclid distance to agglomerated clustering. According to a single cluster contains several types of data elements to determine the initial number of outliers, then determine whether the outlier with the threshold distance.Through an analysis of the performance of algorithm,the computational complexity of the algorithm is ,and the spatial complexity of the algorithm is ,where N is the number dataset objects.Keywords: Data Ming ; Hierarchical Clustering; agglomeration;outlier detection;distance第一章 绪论1.1研究背景及研究意义由于计算技术和存储技术的飞速发展，使人们在短时间里就可以从各种信息源搜集和存储大量的人工难以管理的资料。虽然现代数据库技术可以对这些资料进行经济地存储，但还是需要一种技术来帮助人们分析、理解甚至可视化这些资料。因此就产生了KDD(Knowledge Discovery in Database)技术。它是一个从较低级资料中抽取高级知识的总体过程，就是从数据库中识别有效的，新颖的，潜在有用的并最终可被理解的模式的一个非平凡过程。KDD包括很多内容，其核心部分就是数据挖掘(DataMining)。近十多年来，数据挖掘逐渐成为数据库和人工智能等研究领域的一个热点。聚类（Clusetring)是数据挖掘中重要组成部分，所谓聚类，就是将数据对象分组成多个类或簇(Cluster)，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类源于许多研究领域，包括数据挖掘，统计学，机器学习，空间数据库，生物学和市场营销等。目前它己经广泛应用于模式识别、数据分析、图象处理和市场分析等。由于聚类被广泛地应用在许多领域，迄今为止，研究人员己经提出了许多聚类算法，聚类算法大体上主要可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。孤立点检测是数据挖掘中的一项重要技术，其目标是发现数据集中行为异常的少量的数据对象。在数据挖掘领域，孤立点检测的研究对象是数据集中偏离绝大多数对象的很小一部分。在很多KDD应用中，发现孤立点比发现普通情况更有用，更重要。例如在欺诈探测中，孤立点可能预示着欺诈行为。在市场分析中，可用于确定极低或极高收入的消费行为，或者在医疗分析中用于发现对多种治疗方式的不寻常的反映。孤立点挖掘还可应用于金融欺诈、网络监控、数据清洗、电子商务、职业运动员的成绩分析、故障检测、天气预报、医药研究、信贷信用等领域。在数据挖掘中，孤立点检测算法大体上可分为:基于统计学的方法、基于距离的方法、基于密度的方法、基于偏离的方法等。研究孤立点的异常活动有助于发现隐藏在数据集中有价值的知识。1.2研究内容及论文思路本文就以下内容进行了研究：1对数据挖掘理论、聚类分析算法、孤立点检测算法、聚类与孤立点检测的关系等进行了系统的研究学习，实现层次聚类的孤立点检测。系统地研究了数据挖掘理论、聚类算法、孤立点检测算法，在研究聚类算法和孤立点算法的基础上，将聚类和孤立点检测的过程相结合，实现了基于层次聚类的孤立点检测算法。2基于层次聚类的孤立点检测描述与实现。对基于层次的孤立点检测算法进行了系统描述，对算法中的数据结构及函数进行了说明，给出算法流程图，并分析了该算法的时间复杂度和空间复杂度，以及改算法进行孤立点检测精确性的分析。本文用C+实现该算法。3结果验证及分析。对比传统算法，对包括聚类及孤立点检测正确性、精度、算法执行时间、参数设置、数据输入顺序等，对实验结果进行对比分析，对算法进行测试、分析。1.3论文组织结构本文共分为五章。第二章系统研究了数据挖掘、聚类分析和孤立点检测理论，给出了一些基本概念描述，重点分析了层次聚类算法和孤立点检测算法。第三章在系统研究了层次聚类及孤立点检测算法的基础上，提出了层次聚类与孤立点检测算法想结合的基于层次的孤立点检测算法，对该算法进行了详细的描述，并进行了算法可行性及性能等分析。第四章综述基于算法的编程实现。详细介绍了系统设计流程图及功能模块。第五章对以上所做研究及设计进行了总结，并探讨孤立点检测的将来发展。第二章 相关知识2.1数据挖掘概述随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据急剧增加，可是能用于对这些数据进行分析处理的工具却很少。目前数据库系统所能做到的只是对数据库中己有的数据进行存取和简单的操作，人们通过这些数据所获得的信息量仅仅是整个数据库所包含的信息量的很少一部分，隐藏在这些数据之后的更重要的信息、是关于这些数据的整体特征的描述及对其发展趋势的预测，这些信息在决策生成的过程中具有重要的参考价值。这就引起了对强有力的数据分析工具的急切需求。面对这种挑战，数据库中的知识发现(KDD)技术逐渐发展起来。KDD就是从大量、不完全、有噪声的异质模糊数据中挖掘隐含的潜在有用知识的过程，它不但能够学习己有的知识，而且又可以发现未知的规律。同时，KDD也是一门新兴的交叉学科，汇聚了数据库、人工智能、统计、可视化和并行计算等不同领域的研究人员。一般将KDD中进行知识学习的阶段称为数据挖掘(DataMining)，它是整个数据库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一般而言，在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在人工智能和机器学习界等研究领域人们则称之为数据库中的知识发现。本文将不加区分地使用两者。2.1.1数据挖掘概念数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过程。简单的说KDD是指从大量数据中提取出可信的、新颖的、有效的、潜在有用的并能被人理解的模式的非平凡处理过程。这种处理过程是一种高级的处理过程。在上述定义中，数据是指有关事实的集合，记录和事物有关的原始信息。模式是一个用语言来表示的一个表达式，它可用来描述数据集的某个子集。我们所说的知识，是对数据包涵的信息更抽象的描述。对大量数据进行分析的过程，包括数据准备、模式搜索、知识评价，以及反复的修改求精。该过程要求是非平凡的，意思是要有一定程度的智能性、自动性(仅仅给出所有数据的总和不能算作是一个发现过程)。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效用，如用于决策支持系统里可提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要体现在简洁性上。2.1.2数据挖掘过程数据挖掘过程可粗略地分为按需选择数据、数据集成、数据预处理、数据转换、挖掘过程以及模式评估和知识表示等。(1)数据选择从数据源中检索与分析任务相关的数据。(2)数据集成建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集，并将不同数据源中的数据集成起来，以确定数据挖掘的操作对象，需要解决平台、操作系统和数据类型不同产生的数据物理格式差异。(3)数据预处理数据集中不可避免地存在着不完整、不一致、不精确和重复的数据，这些数据统称为脏数据。数据抽取之后须利用领域专门知识对脏数据进行清洗。通常采用基于规则的方法、神经网络方法和模糊匹配技术分析多数据源数据之间的联系，然后再对它们实施相应的处理。(4)数据转换根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚集等操作转换为适于数据挖掘处理的形式。(5)挖掘算法使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类等。(6)模式评估采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度量，识别表示知识的真正兴趣的模式。(7)知识表示使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解发现的模式。2.1.2数据挖掘算法组成数据挖掘算法是对某种数据挖掘方法的具体实现，可以看作是一些基本技术和原理的综合体。数据挖掘算法一般由三个部分组成模型;性能准则;搜索算法。数据挖掘有许多不同的算法。这些算法的区别在于它们作用的数据种类(如文件、事务数据库、事态数据库和空间数据库等)和发现的知识类型(如分类规则、聚类规则和序列模式等)各异。按照所发现知识类型的不同，比较成熟且应用广泛的数据挖掘算法主要有:分类规则挖掘算法、聚类规则挖掘算法、关联规则挖掘算法、序列模式挖掘算法。2.2聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，一个簇中的数据对象可以被作为一个整体来对待。聚类技术最早在统计学和人工智能等领域得到广泛的研究。在统计方法中，聚类是多元数据分析的三大方法之一(其它两种是回归分析和判别分析)。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。在人工智能中，聚类又称作无监督归纳（unsupervised induction）。因为和分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类(concept clustering)。因为这里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是概念形成(concept formation)。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析。此外，聚类分析可以作为其他算法（如分类等）的预处理步骤，这些算法再在生成的簇上进行处理。数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。2.2.1聚类算法简介目前在文献中存在大量的聚类算法算法的选择取决于数据的类型聚类的目的和应用。大体上，主要的聚类算法可以划分为如下几类:(1)划分方法(partitioning method)给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类簇，并且k=n。也就是说，它将数据划分为k个组，同时满足如下的要求:(i)每个组至少包含一个对象;(ii)每个对象必须属于且只属于一个组。注意在某些模糊划分技术中，第二个要求可以放宽。给定要构建的划分的数目k，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是:在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能“远离”或不同。还有许多其他划分质量的评判标准。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法:(i)k-平均算法，在该算法中，每个簇用该簇中对象的平均值来表示。(ii)k-中心点算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法，对在中小规模的数据库中，发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的改进。(2)层次的方法(hierarchical method)层次的方法对给定的数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次的方法的缺陷在于，一旦一个步骤(合并或分裂)完成，它就不能被撤销。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果:（i）在每层划分中，仔细分析对象间的“联接”，例如CURE和Chamelocn中的做法。(ii)综合层次聚类和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。例如在BIRCH中的方法。(3)基于密度的方法(density一basedmethod)绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是:只要临近区域的密度(对象或数据点的数目)超出某个闽值，就继续聚类。也就是说、对给定类中的每个数据点，在一个给定范围的区域中必须包含一定数目的点。这样的方法可以用来过虑“噪音”孤立点数据，发现任意形状的簇。DBSCAN是一个有代表性的基于密度的方法，它根据一个密度闭值来控制簇的增长。OTPICS是另一个基于密度的方法，它为自动的和交互的聚类分析提供一个聚类顺序。(4) 基于网格的方法(grid-basedmethod)基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STNIG是基于网格方法的一个典型例子。CLIQUE和waveCluster这两种算法既是基于网格的，又是基于密度的。(5) 基于模型的方法(model-basedmethod)基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据或孤立点，从而产生健壮的聚类方法。一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求综合多个聚类技术。下一节针对本文研究的方向，将详细讨论上述的基于层次的聚类算法。2.2.2基于层次的聚类方法基于层次的方法对给定的数据集进行层次分解。根据层次分解的方式，层次的方法可以分力凝聚的和分裂的两种类型。凝聚的层次聚类法(也称为自底向上的方法)，一开始将每个对象作为单独的一个簇，然后相继地合并最相似或相近的对象或簇，得到更大的簇，直到达到一个终止条件或者所有的对象都在一个簇中(层次的最上层)。这种方法需要对簇的相似性或簇间距离进行定义。绝大多数层次聚类方法属于这一类，它们只是在簇间的相似度或距离的定义上有所不同。分裂的层次聚类法(也称为自顶向下的方法)，一开始将所有的对象置于一个簇中，在迭代的每一步中，每个簇逐渐被细分为越来越小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。用户可以指定希望得到的簇的数目作为一个结束条件，也可以指定一个闰值，当两个最近的簇之间的距离超过了这个闽值时，结束分裂过程。这种方法要求预先设定每一步待分裂簇的选择依据以及如何实施这个分裂。待分裂簇的选择依据有很多，例如在每一步的分裂过程中可以选择最大的簇，可以选择总体相似性(Overall Similarity)最小的簇，或者使用一种同时基于大小和总体相似性的度量规则。大量的实验结果表明，这些选择所带来的效果差异不大，所以通常选择分裂现存的最大的簇。层次聚类方法使用距离来反映相似度。四个广泛使用的簇间距离度量方法是：最小距离： 最大距离： 平均值距离：平均距离： 这里是两个对象之间的距离， 是簇的平均值，是簇中对象的个数。表2.1四种簇间距离度量方法的比较方法空间性质单调性距离选择结果类型适用性备注最短距离法压缩是条形 S型唯一太压缩，不够灵敏最长距离法扩张是适用于椭球型距离表中有形同元素时可能出现不唯一的结果太压扩张，样本大时易失真平均值距离法守恒否欧氏距离的平方平均距离法守恒否同上不太压缩也不太扩张，效果较好，较常用以上四种方法是主要针对样品聚类并采用“距离”来衡量样品间的“靠近”程度的方法。在对变量进行聚类时，一般先求出变量间的相似系数。按照相似系数越大，两个变量越相近的原则，根据分层聚类的思想，聚类过程是完全相似的，也可以先将相似系数转化为距离，然后再聚类，转化公式为：或者其中c表示两个变量之间的某种相似系数。d为它们之间的某种距离。尽管层次的方法比较简单，但是没有良好的伸缩性，而且一旦一个合并或分裂被执行，就不能被撤消。为了改进层次方法的聚类效果，人们尝试着将层次聚类与其他聚类技术相结合，形成多阶段的聚类方法，代表性的算法有:BIRCH算法、CURE算法、ROCK算法和CHAMELEON算法。一 BIRCH算法BIRCH是一个综合的层次聚类方法，它的中文含义是利用层次方法的平衡迭代归约和聚类。它引人入聚类特征(Clustering feather)和聚类特征树(CF树)两个概念。引入CF树，可以使大型数据库中的聚类能取得高速度和可伸缩性，可以有效地进行增量聚类或动态聚类。一个聚类特征(CF)是一个三元组，给出对象子聚类的信息的汇总描述。假设某个子聚类中有N个d维的点或对象，则该子聚类的CF定义如下：其中，N是子类中点的数目，是N个点的线性和，即，SS是数据点的平方和即。CF树不是存储所有的对象，而是汇总了关于子聚类的信息，这些信息是计算聚类和有效利用存储的关键度量。每个叶节点包含一个或多个子聚类，每个子聚类中包含一个或多个对象。一个CF树有两个参数，即分支因子B和闭值T，这两个参数影响了结果树的大小。分支因子定义了每个非叶节点的后代的最大数目，闭值参数给出了存储在叶节点中的子聚类的最大直径。BIRCH法的分两个段：阶段一：BIRCH 扫描数据库，建立一个初始存放于内存的CF 树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构。在这个阶段，当一个对象被插入到最近的叶节点(子聚类)中时，如果在插入对象后，存储在叶节点中子聚类的直径大于阂值，那么该叶节点被分裂，也可能有其他节点被分裂。新对象插入后，关于该对象的信息向根节点传递。通过修改闲值，CF树的大小可以改变;阶段二：BIRCH 采用某个聚类算法对CF 树的叶节点进行聚类。BIRCH算法具有可伸缩性，数据集的单遍扫描产生了一个基本的聚类，二次扫描可以进一步改进聚类质量和处理孤立点。同时，该算法的速度快，计算复杂性只为O(n)。n是数据集中对象的个数。BIRCH的缺点是，对于非球状的簇不能很好地工作。二 CURE算法绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱。CURE 解决了偏好球形和相似大小的问题，在处理孤立点上也更加健壮。CURE(clustering using representative) 采用了一种新的层次聚类算法，该算法选择了位于基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择了数据空间中固定数目的具有代表性的点。一个簇的代表点通过如下方式产生：首先选择簇中分散的对象，然后根据一个特定的分数或收缩因子向簇中心“收缩”或移动它们。在算法的每一步，有最近距离的代表点对（每个点来自于一个不同的簇）的两个簇被合并。每个簇有多于一个的代表点使得 CURE 可以适应非球形的几何形状。簇的收缩或凝聚可以有助于控制孤立点的影响。因此，CURE 对孤立点的处理更加健壮，而且能够识别非球形和大小变化较大的簇。对于大规模数据库，它也具有良好的伸缩性，而且没有牺牲聚类质量。针对大数据库，CURE 采用了随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分被部分聚类。这些结果簇然后被聚类产生希望的结果。下面的步骤描述了 CURE 算法的核心：1从源数据对象中抽取一个随机样本S。2将样本S 划分为一组分块。3对每个划分局部地聚类。4通过随机取样剔除孤立点。如果一个簇增长得太慢，就去掉它。5对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子a 收缩或向簇中心移动。这些点描述和捕捉到了簇的形状。CURE算法的缺陷是不处理分类属性。三 ROCKROCK(Robust Clustering Of Links)是一个可选的凝聚层次聚类算法，适用于分类属性。它引入了一个新颖的概念，即交叉链(link)，利用交叉链来度量一对数据点之间的相似性，并根据交叉链而不是距离来进行簇的合并。在ROCK方法中，一个点的近邻是那些与它很相似的点。记是计量点对和之间接近程度的相似性函数。该函数可以是常用的距离公式，也可以是其他形式。相似性函数可以由领域专家指定。给定一个介于0到1之间的常数作为阀值，如果，那么就认为和是近邻。是两个点和共同近邻的个数。如果的值比较大，则点和更可能属于同一个簇。ROCK首先根据相似度阈值和共同邻居的概念从给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上运行一个层次聚类算法。四 ChameleonChameleon 是一个在层次聚类中采用动态模型的聚类算法。在它的聚类过程中，如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关，则合并这两个簇。基于动态模型的合并过程有利于自然的和相似的聚类的发现，而且只要定义了相似度函数就可应用于所有类型的数据。Chameleon 的产生是基于对两个层次聚类算法CURE 和ROCK 的缺点的观察。CURE 及其相关的方案忽略了关于两个不同簇中的对象的互连性的信息，而ROCK 及其相关的方案强调对象间互连性，却忽略了关于对象间近似度的信息。Chameleon 的主要思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子类。因此它不依赖于一个静态的，用户提供的模型，能够自动地适应被合并的簇的内部特征。Chameleon 基于通常采用的k 个最近的邻居图方法来描述它的对象。K 个最近的邻居图中的每个点代表一个数据对象，如果一个对象是另一个对象的k 个最类似的对象之一，在这两个点（对象）之间存在一条边。K 个最近邻居图动态地捕捉邻域的概念：一个对象的领域半径被对象所在区域的密度所决定。在一个密集区域，邻域的定义范围相对狭窄；在一个稀疏区域，它的定义范围相对较宽。与采用基于密度的全局邻域方法相比，该方法能产生更自然的聚类结果。而且，区域的密度作为边的权重被记录下来。就是说，一个密集区域的边趋向于比稀疏区域的边有更大的权重。Chameleon 通过两个簇的相对互连性RI 和相对近似性RC来决定簇间的相似度：其中是包含的簇分裂为截断边，（或）是（或）的最小截断等分线的大小(即将图划分为大致相等的部分需要切断的边的加权和)。其中是连接的顶点的边的平均权重。（或）是（或）的最小截断等分线的边的平均权重。可以看出，Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有高强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O（）的时间。2.2.3距离、相似系数及聚类分析中的数据类型我们研究在聚类分析中经常出现的数据类型，以及如何对其进行预处理。假设要聚类的数据集合包含n 个数据对象，这些数据对象可能表示人，房子，文档，国家等。许多基于内存的聚类算法选择如下两种有代表性的数据结构：(1)数据矩阵（Data matrix，或称为对象属性结构）它用p 个变量（也称为属性）来表现n 个对象，例如用年龄，身高，性别，种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看为n*p 维（n 个对象*p 个属性）的矩阵。(2)相异度矩阵（dissimilarity matrix，或称为对象-对象结构）：存储n 个对象两两之间的近似性，表现形式是一个n*n 维的矩阵。在这里d(i,j)是对象i 和对象j 之间相异性的量化表示，通常它是一个非负的数值，当对象i 和j 越相似，其值越接近0；两个对象越不同，其值越大。数据矩阵经常被称为二模（two-mode）矩阵，而相异度矩阵被称为单模（one-mode）矩阵。这是因为前者的行和列代表不同的实体，而后者的行和列代表相同的实体。许多聚类算法以相异度矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将其转化为相异度矩阵。许多聚类算法是以相异度矩阵为基础的。如果数据是以数据矩阵的形式给出，可以将数据矩阵转化为相异度矩阵。有的聚类算法以相似度矩阵为基础，而不是相异度矩阵。相似度矩阵通常用距离公式计算得到。一 距离与相似系数选用的度量单位将直接影响聚类分析的结果。一般而言，选用的单位越小，变量可能的值域就越大，这样对聚类结果的影响就越大。因此为了避免聚类结果对单位选择的依赖，数据应当标准化。标准化处理后，对象间的相异度是基于距离来计算的。最常用的距离度量方法是欧几里得距离，它的定义为:其中和是两个p维的数据对象。在使用欧几里得距离时，要特别注意样本诸测量值的选取，应是有效地反映类别属性的特征。还有一个就是曼哈顿距离：如果对每个变量根据其重要性赋予一个权重，加权的欧几里得距离可以计算如下：相似系数的表示形式常见有以下两种：1.夹角余弦2相关系数三 聚类分析中的数据类型(1) 区间标度（Interval-Scaled）变量是一个粗略线性标度的连续变量。典型的例子包括重量和高度，经度和纬度坐标以及大气温度。(2)二元变量（binary variable）一个二元变量只有两个状态:O或者1，0表示该变量为空，1表示该变量存在。例如，给出一个描述病人的变量Smoker，l表示病人抽烟，而O表示病人不抽烟。如果二元变量有相同的权重，则可以得到一个两行两列的可能性表2-l，这个表反映了两个对象的变量取值可能性情况。在表中，q是对象i和对象j值都为1的变量的数目，r是对象i值为1而对象j为0的变量的数目，s是对象i值为0而对于对象j为1的变量的数目，t是对象i和j值都为0的变量的数目。变量的总数是， 。如果二元变量的两个状态是同等价值的，并有相同的权重，则二元变量是对称的:基于对称二元变量的相似度称为恒定的相似度，对恒定的相似度来说，评价两个对象i和j的相异度的最著名的系数是简单匹配系数，其定义如下:如果二元变量的两个状态的输出不是同样重要，那么该二元变量是不对称的。例如一个疾病检查的肯定和否定的结果。根据惯例我们将比较重要的输出结果，通常也是出现几率比较小的结果编码为l，而将另一种结果编码为0。给定两个不对称的二元变量，两个都取l的情况被认为比两个都取0的情况更有意义.基于这样变量的相似度被称为非恒定的相似度。对非恒定的相似度，最著名的评价系数是Jaccard系数，其定义为:(3)标称型、序数型和比例标度型变量标称变量是二元变量的推广，它可以具有多于两个的状态值。例如color是一个标称变量，它可能有五个状态:红色，黄色，绿色，粉红色和色。假设一个标称变量的状态数目是M。每一个状态值可以用字母、符号或者一整数来表示，则两个对象i和j之间的相异度可以用简单匹配方法来计算：这里m是匹配数，即i和j之间的相异度可以用简单匹配方法来计算:这里m是匹配数，即i和j取值相同的变量的数目，而p是全部变量的数目。序数型变量序数型变量可以是离散的，也可以是连续的。在连续型的序变量中，值的相对顺序是必要的，而其实际的大小则不重要。在相异度的计算需要把每个变量的值域映射到0.0，1.0上，以便每个变量都有相同的权重。然后可以采用距离的计算方法进行相异度的计算。比例标度型变量比例标度型变量是非线性的标度取正的度量值计算时可以采用与处理区间标度变量相同的方法:也可以先进行对数变换，再进行计算；也可以借用序数性变量，采用秩作为区间标度的值来对待。(4)混合类型的变量在许多真实的数据库中，对象是由混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部类型。2.3孤立点分析Hawkins给出了孤立点的本质定义:孤立点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。聚类算法对孤立点的定义:孤立点是聚类嵌于其中的背景噪声。孤立点检测算法则认为孤立点是既不属于聚类也不属于背景噪声的点，它们的行为与正常的行为有很大不同。孤立点检测需要在多维数据集中发现与其它个体不同的对象。孤立点检测是数据挖掘中一个重要方面，在很多应用里，例外事件常常比普通的事件更有意义。孤立点检测大多用于电信和信用卡诈骗检测、贷款审批、医药研究、天气预报、电子贸易中的犯罪活动检测，在NBA比赛和NHL（Natial Hockey Legaue)数据中，孤立点检测也有应用。在数据仓库领域，孤立点检测被用来发现不一致的数据，以提高数据质量。从20世纪80年代起，孤立点检测问题就在统计学领域里得到广泛研究，通常用户用某个统计分布对数据点进行建模，再以假定的模型，根据点的分布来确定是否为孤立点。这些方法的最大缺陷是:在许多情况下，用户并不知道数据集的分布。而且现实数据也往往不符合任何一种理想状态的数学分布。Aggrawal和Ragaran在1996年提出过“序列孤立点”的概念。他们采用这样一个机制:扫描数据集并观测一系列相似数据，当发现一个数据点明显不同于前面的序列，这样的点就被认为是孤立点。这个算法复杂度与数据集大小呈线性关系，有优异的计算性能。但是序列孤立点对孤立点存在的情况的假设太理想化，对现实复杂数据效果不太好。Knorr和Ng在1998年提出了基于距离的孤立点检测算法。Rastogi和Ramaswamy改进了他们的孤立点定义。在聚类算法研究中，如DBSCAN，BRICH都具有一定的噪声处理能力。但是聚类中的噪声和孤立点在概念上还是有些偏差的。噪声是定义在聚类基础之上，即噪声是不隶属于任何聚类的数据;而孤立点的定义不依赖于是否存在聚类。而且上面的算法的最终目标是优化聚类查找，而不是孤立点检测。当然一般而言，假设聚类存在的话(低维数据集往往更容易定义聚类)，噪声和孤立点在概念上还是有很多重叠处的。Breunig和Kriegel作了将基于密度的聚类算法OPTICS与孤立点检测合并到一起的研究。在此基础上，Bruenig和Kriegel提出了局部孤立因子的概念。Aggaarwal和Yu提出了一个针对高维数据集进行降维的孤立点检测的新思路，利用遗传算法优化其性能。本节着重介绍基于距离的孤立点检测算法孤立点检测算法。2.3.1基于统计的方法基于统计的方法使用著名的标准统计分布(即正态分布，帕松等)来拟合数据点。孤立点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因数产生，而是产生于完全不同的统计分布。不一致检验是为了在不同条件下挖掘孤立点而设计的统计检验。2.3.2基于距离的孤立点检测算法基于距离的方法是通过数据点或对象之间的距离来检测孤立点的。如果数据集合X中对象至少有p部分与对象O的距离大于d，则对象O是一个带参数p和d的基于距离的孤立点，即DB（p,d）-Outlier。对于每个实体O，O的d邻域是一个包含所有在O的d距离以内的实体的集合。例如。分数p是一个孤立点的d邻域之外的实体的最小比例。为了讨论简单，假设M为一个孤立点的d邻域中实体的最大个数(显然，M=N（1-p）)。根据上面的公式，对于给定的p和d，找出孤立点的关键在于解决对每个以O为中心的d邻域的搜索，只要在O的d邻域中发现了（M+1）个实体，就可以停止搜索并且宣布O不是孤立点。否则，就认为O是一个孤立点。基于距离的孤立点检测算法设计了三种算法:基于索引的算法、嵌套循环算法及基于单元的算法，1.基于索引的距离算法该算法的主要思想是将数据实体存储在索引树中，判断一个对象是否是一个孤立点只需查询d-邻域内是否包含M个对象，如果是则该对象不是孤立点，否则该对象是孤立点。对于多维索引模式的分析说明，对于R*树的变种，k-d树，X树，一个范围查询的复杂度下限是。当维数(或属性) k增加时，范围查询迅速变为。N是数据实体的个数。然而使用上面的方法查询DB（p,d）-Outlier的过程最坏的复杂度情况是。2.嵌套循环算法(NL算法)为了避免查询DB（p,d）-Outlier中建立索引的花费，NL算法使用了一种基于块和循环的设计。假设有一个b%数据集大小的缓存，算法就将缓存划分为相等两个部分，称为第一和第二数组。它把数据集读入数组，直接计算每个实体对的距离。对于每个在第一个数组内的实体，它的d邻域被记录下来，当实体的d邻域中点的个数超过M时，则证明该点不是孤立点，这时停止计数，跳出现在的循环，比较下一个点。假设NL算法有50%的缓存，并用A，B，C，D来代表4个逻辑块，每个块记录了数据集1/4的实体。以下面的顺序来填充每个数组，并比较:(1)A和A，然后和B，C，D-总共有四个块被读；(2)D和D(不需要读)，然后和A(不用读)，B,C有两块被读；(3)C和C(不需要读)，然后和D(不用读)，A，B总共有两块被读；(4)B和B(不需要读)，然后和C(不用读)，A，D总共有两块被读。共有十块被读，相当于10/4次扫描数据集。和索引算法相比，NL算法避免了建立索引结构的花费。很容易看出它的复杂度是，k是数据维数(或属性个数)。与不考虑1/0效率的一个实体对一个实体的强制算法相比，NL算法有优势，因为它减少了读的次数。3.基于单元的算法:与前两种方法相比，基于单元的算法的计算复杂度较小。该方注把k维数据空间划分为边长为的单元，每个单元有两层围绕着，第一层的厚度为一个单元，第二层的厚度为。该方法统计单元中对象的数目、单元与第一层中对象的数目之和、单元与两个层次中对象的数目之和等三个统计数据。我们把他们分别记为c_count、c_