聚类数据挖掘技术.ppt

《聚类数据挖掘技术.ppt》由会员分享，可在线阅读，更多相关《聚类数据挖掘技术.ppt（66页珍藏版）》请在三一办公上搜索。

1、第八章 聚类数据挖掘技术,，,一、聚类:,按照数据之间的相似性，对数据集进行分组或分类（簇,cluster）的过程，试图使类内差距最小化，类间差距最大化。利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行预测和分类。应用于数据挖掘、模式识别、图像处理、经济学,“物以类聚，人以群分”,聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要

2、求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。,二、聚类在数据挖掘中的典型应用：聚类分析可以作为其它算法的预处理步骤：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息。可以作为一个独立的工具来获得数据的分布情况：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用

3、前景。聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。,广泛的应用领域,商务：帮助市场分析人员从客户信息库中发现不同的客户群，用购买模式来刻画不同的客户群的特征土地使用：在地球观测数据库中识别土地使用情况相似的地区保险业：汽车保险单持有者的分组城市规划：根据房子的类型，价值和地理分布对房子分组生物学：推导植物和动物的分类，对基因进行分类,聚类分析的目标就是形成的数据簇，并且满足下面两个条件：一个簇内的数据尽量相似（high intra-class similarity）；不同簇的数

4、据尽量不相似（low inter-class similarity）。衡量一个聚类分析算法质量，依靠：相似度测量机制是否合适。是否能发现数据背后潜在的、手工难以发现的类知识。,三、聚类分析的目标:,四、聚类分析方法的分类:,按照聚类的标准，聚类方法可分为如下两种：统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。按照聚类算法所处理的数据类型，聚类方法可分为三种：数值型数据聚类方法：所分析的数据的属性只限于数值数据。离散型数据聚类方法：所分析的数据的属性只限于离散型数据。混合型数据聚类方法：能同时处理数值和离散数据。,按照聚类的尺度，聚

5、类方法可被分为以下三种：基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如k-means、k-medoids、BIRCH、CURE等算法。基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于互连性(Linkage-Based)的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。,按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。划分法（Partitioning Methods）：基于一定标准构建数据的划分。属于该类的聚类方法有：k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、

6、CLARANS等。层次法（Hierarchical Methods）：对给定数据对象集合进行层次的分解。密度法（density-based Methods）：基于数据对象的相连密度评价。网格法（Grid-based Methods）：将数据空间划分成为有限个单元（Cell）的网格结构，基于网格结构进行聚类。模型法（Model-Based Methods）：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。,五、数据相似性的度量-距离,距离越大，相似性越小。点间距离与类间距离 类间距离基于点间距离计算距离函数应同时满足 1.d(i,j)0 2.d(i,i)=0 3.d(i,j)=

7、d(j,i)4.d(i,j)d(i,k)+d(k,j),常用点间距离相异度,欧式距离,城区距离,切比雪夫距离,明科夫斯基距离,数据矢量x=(x1,x2,xn),y=(y1,y2,yn),.,常用类间距离,最短距离法,最长距离法,类平均法,重心法,两个聚类p和q,.,六、聚类方法,划分方法：构造数据的最优划分层次方法：对数据进行层次分解或合并基于密度的方法：（1）基于密度连通性，如DBSCAN,OPTICS；（2）基于密度分布函数，如DENCLUE基于网格的方法：采用多分辨率网格数据结构，如STING,BANG,CLIQUE,MAFIA基于模型的方法：SOM神经网络,(1)划分方法,给定一个有n

8、个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：每一个簇至少包含一个对象。每一个对象属于且仅属于一个簇。对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。,启发式方法:k-平均算法和k-中心点算法k-均值算法:每个簇用该簇中对象的平均值来表示。k-中心点算法:每个簇用接近聚类中心的一个对象来表示,k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。首先将所有对象

9、随机分配到k个非空的簇中。计算每个簇的平均值，并用该平均值代表相应的簇。根据每个对象与各个簇中心的距离，分配给最近的簇。然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。,K-均值算法,K-均值聚类示例,From“Data Mining:Concepts and Techniques”,J.Han and M.Kamber,算法 k-means算法输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使平方误差准则最小。（1)assign initial value for means;/*任意选择k个对象作为初始的簇中心*/(2)REPEAT(3)FOR j=

10、1 to n DO assign each xj to the closest clusters;(4)FOR i=1 to k DO/*更新簇平均值*/(5)Compute/*计算准则函数E*/(6)UNTIL E不再明显地发生变化。,算法首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。准则函数试图使生成的结果簇尽可能地紧凑和独立。,样本数据序号 属性 1 属性 21 1 12 2 13 1 24 2 25 4 36 5 37 4 48 5 4,迭代次

11、数 平均值平均值 产生的新簇 新平均值 新平均值（簇1）（簇2）（簇1）（簇2）1（1，1）（1，2）1，2，3，4，5，6，7，8（1.5，1）（3.5，3）2（1.5，1）（3.5，3）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5）3（1.5，1.5）（4.5，3.5）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5）,根据所给的数据通过对其实施k-means(设n=8，k=2)，其主要执行执行步骤：第一次迭代：假定随机选择的两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，并产生两个簇1，2和3，4，5，6，7，8。对于产生的簇分别计算平

12、均值，得到平均值点。对于1，2，平均值点为（1.5，1）（这里的平均值是简单的相加除2）；对于3，4，5，6，7，8，平均值点为（3.5，3）。第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（1.5，1）、（3.5，3）最近的原则重新分配。得到两个新的簇：1，2，3，4和5，6，7，8。重新计算簇平均值点，得到新的平均值点为（1.5，1.5）和（4.5，3.5）。第三次迭代：将所有点按离平均值点（1.5，1.5）和（4.5，3.5）最近的原则重新分配，调整对象，簇仍然为1，2，3，4和5，6，7，8，发现没有出现重新分配，而且准则函数收敛，程序结束。,实例,k-me

13、ans算法的性能分析,主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的，它的效果较好。主要缺点在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,k-means算法的几种改进方法,k-mode 算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据。k-prototype算法：可以对离散与数值

14、属性两种混合的数据进行聚类，在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。k-中心点算法k-means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。,k-中心点算法（k-medoids）,也称PAM算法（Partitioning Around Medoids）基于有代表性的数据（中心点），而不是均值代表每个簇。思路 1.为每个簇随机选择一个代表对象(中心点)；2.剩余的对象根据其与代表对象的距离分配给与其最近的一

15、个簇；3.反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。,PAM作为最早提出的k-中心点算法之一，它选用簇中位置最中心的对象作为代表对象，试图对n个对象给出k个划分。代表对象也被称为是中心点，其他对象则被称为非代表对象。最初随机选择k个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。对可能的各种组合，估算聚类结果的质量。一个对象Oi被可以产生最大平方-误差值减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。,计算

16、用非代表对象h替换代表对象i的总代价：,单个数据的替换代价：用h代替i后，j到中心点距离的变化,为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代，对于每一个非中心点对象Oj，下面的四种情况被考虑:第一种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh所代替作为中心点，且Oj离一个Om最近，im，那么Oj被重新分配给Om。第二种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oj被重新分配给Oh。第三种情况：Oj当前隶属于中心点Om，mi。如果Oi被Oh代替作为一个中心点，而Oj依然离Om最近，那么对象的隶属不发生变化。第四种情况：Oj

17、当前隶属于中心点Om，mi。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oi被重新分配给Oh。,每当重新分配发生时，平方-误差E所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方-误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。如果总代价是负的，那么实际的平方-误差将会减小，Oi可以被Oh替代。如果总代价是正的，则当前的中心点Oi被认为是可接受的，在本次迭代中没有变化。总代价定义如下：其中，Cjih表示Oj在Oi被Oh代替后产生的代价。下面介绍上面所述的四种情况中代价函数的计算公式，其中所引用的符号有：Oi和Om是

18、两个原中心点，Oh将替换Oi作为新的中心点。,第二种情况 Oj被重新分配给Oh，Cjih=d(j,h)-d(j,i),第一种情况 Oj被重新分配给Om，Cjih=d(j,m)-d(j,i),第三种情况 Oj的隶属不发生变化，Cjih=0,第四种情况 Oi被重新分配给Oh，Cjih=d(j,h)-d(j,m),算法 PAM（k-中心点算法）输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使得所有对象与其最近中心点的相异度总和最小。（1）任意选择k个对象作为初始的簇中心点；（2）REPEAT（3）指派每个剩余的对象给离它最近的中心点所代表的簇；（4）REPEAT（5）选择一个未被选择的中心点

19、Oi；（6）REPEAT（7）选择一个未被选择过的非中心点对象Oh；（8）计算用Oh代替Oi的总代价并记录在S中；（9）UNTIL 所有的非中心点都被选择过；（10）UNTIL 所有的中心点都被选择过；（11）IF 在S中的所有非中心点代替所有中心点后的计算出的总代价有小于0的存在 THEN 找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；（12）UNTIL 没有再发生簇的重新分配，即所有的S都大于0.,实例,假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设k=2）。样

20、本点间距离如下表所示:样本点 起始中心点为A,B,第一步 建立阶段：假如从5个对象中随机抽取的2个中心点为A，B,则样本被划分为A、C、D和B、E，如图所示。第二步 交换阶段：假定中心点A、B分别被非中心点C、D、E替换，根据PAM算法需要计算下列代价TCAC、TCAD、TCAE、TCBC、TCBD、TCBE。以TCAC为例说明计算过程：a)当A被C替换以后，A不再是一个中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。b)B是一个中心点，当A被C替换以后，B不受影响，CBAC=0。c)C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点

21、，符合PAM算法代价函数的第二种情况CCAC=d(C,C)-d(C,A)=0-2=-2。d)D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1。e)E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是 B，根据PAM算法代价函数的第三种情况CEAC=0。因此，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。,在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，选择第一个最小代价的替换（也就是C替换A），根据图（a）所示，样

22、本点被划分为 B、A、E和C、D两个簇。图（b）和图（c）分别表示了D替换A，E替换A的情况和相应的代价(a)C替换A,TCAC=-2(b)D替换A,TCAD=-2(c)E替换A,TCAE=-1图 替换中心点A,图（a）、（b）、（c）分别表示了用C、D、E替换B的情况和相应的代价。C替换B,TCBC=-2(b)D替换B,TCBD=-2(c)E替换B,TCBE=-2图 替换中心点B 通过上述计算，已经完成了PAM算法的第一次迭代。在下一迭代中，将用其他的非中心点A、D、E替换中心点B、C，找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。,PAM算法特点,比k-means健壮，但

23、对于大数据集效率不高。当存在“噪声”和离群数据时，k-中心点方法比k均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。k-中心点方法的执行代价比k-平均高。,改进算法,CLARA(Clustering Large Applications),1990 用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的中心点。如果样本是以非随机的方式选取，它应当足以代替原来的数据集合。从中选出的代表对象（中心点）很可能与从整个数据集合选出的代表相似。,改进算法,CLARANS(“随机化的”CLARA)，1994 利用多次不同抽样来改进CLARA。其聚类过程可

24、以被描述为对一个图的收索过程，图中的每一个节点都是一个潜在的解，即k个中心点的集合。在替换了一个中心点后得到的聚类结果被当成是前聚类结果的邻居。如果一个更好的邻居被发现，也就是说它有更小的平方误差值，clarans移到该邻居节点，处理过程重新开始，如果没有发现更好的邻居，则达到局部最优。,(2)层次聚类方法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇

25、，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,AGNES算法,AGNES(AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。,算法 AGNES（自底向上凝聚算法）输入：包含n个对象的数据库，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。(1)将每个对象当成一个初始簇；(2)REPEAT(3)根据两个簇中最近的数据点找到最近的两个簇；(4)合并两个簇，生成新的簇

26、的集合；(5)UNTIL 达到定义的簇的数目；,实例,序号属性 1属性 2111212321422534635744845,步骤最近的簇距离最近的两个簇合并后的新簇111，21，2，3，4，5，6，7，8213，41，2，3，4，5，6，7，8315，61，2，3，4，5，6，7，8417，81，2，3，4，5，6，7，8511，2，3，41，2，3，4，5，6，7，8615，6，7，81，2，3，4，5，6，7，8结束,第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。第2步：，对上一次合并后的簇计算簇间距离，找出距离最近的

27、两个簇进行合并，合并后3，4点成为一簇。第3步：重复第2步的工作，5，6点成为一簇。第4步：重复第2步的工作，7，8点成为一簇。第5步：合并1，2，3，4成为一个包含四个点的簇。第6步：合并5，6，7，8，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。,AGNES算法的性能分析,AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。这种聚类方法不具有很好的可伸缩性，因为合并的决定需要检查和估算大量的对象或簇。假定在开始

28、的时候有n个簇，在结束的时候有1个簇，因此在主循环中有n次迭代，在第i次迭代中，我们必须在n-i+1个簇中找到最靠近的两个聚类。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为 O(n2)，该算法对于n很大的情况是不适用的。,DIANA算法,DIANA(Divisive ANAlysis)算法是典型的分裂聚类方法。在聚类中，用户能定义希望得到的簇数目作为一个结束条件。同时，它使用下面两种测度方法：簇的直径：在一个簇中的任意两个数据点的距离中的最大值。平均相异度（平均距离）：,算法 DIANA（自顶向下分裂算法）输入：包含n个对象的数据库，终止条件簇的数目k。输出：k个簇，达到终止

29、条件规定簇数目。（1）将所有对象整个当成一个初始簇；（2）FOR（i=1;ik;i+)DO BEGIN（3）在所有簇中挑出具有最大直径的簇C；（4）找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中；（5）.REPEAT（6）在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。（7）UNTIL 没有新的old party的点被分配给splinter group；（8）splinter group和old party为被选中的簇

30、分裂成的两个簇，与其它簇一起组成新的簇集合。（9）END.,实例,序号属性 1属性 2111212321422534635744845,步骤具有最大直径的簇splinter groupOld party11，2，3，4，5，6，7，812，3，4，5，6，7，821，2，3，4，5，6，7，81，23，4，5，6，7，831，2，3，4，5，6，7，81，2，34，5，6，7，841，2，3，4，5，6，7，81，2，3，45，6，7，851，2，3，4，5，6，7，81，2，3，45，6，7，8 终止,第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。1的平均

31、距离：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96 类似地，2的平均距离为2.526；3的平均距离为2.68；4的平均距离为2.18；5的平均距离为2.18；6的平均距离为2.68；7的平均距离为2.526；8的平均距离为2.96。挑出平均相异度最大的点1放到splinter group中，剩余点在old party中。第2步，在old party里找出到最近的splinter group中的点的距离不大于到old party中最近的点的距离的点，将该点放入splinter group中，该点是2。第3步，重复第2步的工作，splinter group中放入点3。第4步

32、，重复第2步的工作，splinter group中放入点4。第5步，没有在old party中的点放入了splinter group中且达到终止条件（k=2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。下面介绍两个改进的层次聚类方法CURE和BIRTH。,BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特

33、征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。,BIRCH算法主要分两个阶段进行：阶段一：扫描数据库，建立一个初始的CF树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，CF树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。因此，BIRTH方法对增量或动态聚类也非常有效。阶段二：采用某个聚类算法对CF树的叶节点进行聚

34、类。在这个阶段可以执行任何聚类算法，例如典型的划分方法。,BIRCH算法具有可伸缩性，通过对数据集的首次扫描产生一个基本聚类，二次扫描则进一步改进聚类质量并处理孤立点。BIRCH算法处理速度较快，只是对非球形簇处理效果不好。,很多聚类算法只擅长处理球形或相似大小的聚类，另外有些聚类算法对孤立点比较敏感。CURE算法解决了上述两方面的问题，选择基于质心和基于代表对象方法之间的中间策略，即选择空间中固定数目的具有代表性的点，而不是用单个中心或对象来代表一个簇。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向簇中心“收缩”它们，即合并两个距离最近的代表点的簇。,CURE算法的主要步骤如下

35、：从源数据集中抽取一个随机样本S。为了加速聚类，把样本划分成p份，每份大小相等。对每个划分进行局部地聚类。根据局部聚类结果，通过随机抽样剔除孤立点。主要有两种措施：如果一个簇增长得太慢，就去掉它；在聚类结束的时候，非常小的类被剔除。对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。用相应的簇标签来标记数据。,由于CURE回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，

36、而且能识别非球形和大小变化比较大的簇。CURE的复杂度是O(n)，n是对象的数目，所以该算法适合大型数据的聚类。,(3)密度聚类,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。,DBSCAN（Densi

37、ty-Based Spatial Clustering of Applications with Noise）一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。,DBSCAN,定义 1 对象的-临域：给定对象在半径内的区域。定义 2 核心对象：如果一个对象的-临域至少包含最小数目MinPts个对象，则称该对象为核心对象。例如，在图中，=1cm，MinPts=5，q是一个核心对象。定义 3 直接密度可达：给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心

38、对象，我们说对象p从对象q出发是直接密度可达的。例如，在图中，=1cm，MinPts=5，q是一个核心对象，对象p从对象q出发是直接密度可达的。,图 直接密度可达,定义 4 密度可达的：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。例如，在图中，=1cm，MinPts=5，q是一个核心对象，p1是从q关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度可达，则对象p从对象q关于和MinPts密度可达的。,图 密度可达,定义 5 密度相连的：如果对

39、象集合D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的。定义 6 噪声:一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。,图 密度相连,图 噪声,DBSCAN通过检查数据集中每个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,DBSCAN算法描述算法5-5 DBSCA

40、N 输入：包含n个对象的数据库，半径，最少数目MinPts。输出：所有生成的簇，达到密度要求。1.REPEAT2.从数据库中抽取一个未处理过的点；3.IF 抽出的点是核心点 THEN找出所有从该点密度可达的对象，形成一个簇4.ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；5.UNTIL 所有点都被处理；,下面给出一个样本事务数据库（见左表），对它实施DBSCAN算法。根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入=1，MinPts=4）样本事务数据库DBSCAN算法执行过程示意 聚出的类为1，3，4，5，9，10，12，2，6，7，8，

41、11。,算法执行过程：,第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类1，3，4，5，9，10，12，选择下一个点。第5步，在数据库中选择一点5，已经

42、在簇1中，选择下一个点。第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类2，6，7，8，11，选择下一个点。第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都

43、已处理，程序终止。,OPTICS算法是对DBSCAN算法的改进，因为在DBSCAN算法中需要用户设定-邻域和MitPts，但是在实际应用中用户往往很难确定这些参数，而且这些参数设置的不同往往会导致聚类结果有很大差别。在OPTICS算法中认定对象应该以特定的顺序进行处理，这个顺序首先处理最小的值密度可达的对象，这样可以首先完成高密度的聚类。,DENCLUE算法的依据是某个数据点在邻域内的影响可以用一个数学函数来形式化地模拟，这个函数为影响函数。所聚类数据空间的整体密度看成是所有数据点影响函数的总和。在聚类时就根据全局密度函数的局部最大，即密度吸引点来确定。,将对象空间量化为有限数目的单元，形成一

44、个网格结构，所有的聚类都在这个网格结构中上进行。其优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING算法、用小波转换方法进行聚类的WaveCluster方法和在高维数据空间基于网格和密度的聚类方法。,(4)网格聚类,STING(Statistaical Information Grid_based method)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。

45、高层单元的统计参数可以很容易的从底层单元的计算得到。这些参数包括属性无关的参数count、属性相关的参数m（平均值）、s(标准偏差)、min(最小值)、max(最大值)以及该单元中属性值遵循的分布类型。STING算法采用了一种多分辨率的方法来进行聚类分析，该聚类算法的质量取决于网格结构最低层的粒度。如果粒度比较细，处理的代价会显著增加；但如果粒度较粗，则聚类质量会受到影响。,STING算法,STING算法的主要优点是效率高，通过对数据集的一次扫描来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)。在建立层次结构以后，查询的时间复杂度是O(g),g远小于n。STING算法采用网格结构，有利

46、于并行处理和增量更新。,WaveCluster方法首先通过在数据空间上强加一个多维网格结构来汇总数据，每个网格单元汇总了一组映射到该单元中的点的信息，然后采用一种小波变换对原特征空间进行变换，汇总信息在进行小波变换时使用，接着在变换后的空间中找到聚类区域。小波变换的聚类是无监督聚类，不用事先假定聚类的形状，可以发现任意形状的聚类，边界弱信号不会被屏蔽，可以剔除孤立点，本身运算开销不大。,基于网格和密度的聚类CLIQUE算法主要步骤是：将数据空间划分为互不相交的长方形单元，记录每个单元中的对象数。用先验性质识别包含簇的子空间。在符合兴趣度的子空间中先找出密集单元，再找出相连接的密集单元，以识别簇

47、。为每个簇生成最小化的描述。,基于模型的聚类方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。基于模型的聚类方法主要有统计学和神经网络两种。,(5)模型聚类,SOM神经网络是一种基于模型的聚类方法。SOM神经网络由输入层和竞争层组成。输入层由N个输入神经元组成，竞争层由mm=M个输出神经元组成，且形成一个二维平面阵列。输入层各神经元与竞争层各神经元之间实现全互连接。该网络根据其学习规则，通过对输入模式的反复学习，捕捉住各个输入模式中所含的模式特征，并对其进行自组织，在竞争层将聚类结果表现出来，进行自动聚类。竞争层的任

48、何一个神经元都可以代表聚类结果。,SOM神经网络,图1给出了SOM神经网络基本结构，图2给出了结构中各输入神经元与竞争层神经元j的连接情况。图1 SOM网络基本结构 图2 输入神经元与竞争层神经元j的连接情况设网络的输入模式为 k=1,2,p；竞争层神经元向量为Bj=(bj1,bj2,bjm)，j=1,2,m；其中Ak为连续值，Bj为数字量。网络的连接权为wij i=1,2,N；j=1,2,M。,SOM网络寻找与输入模式Ak最接近的连接权向量Wg=(wg1,wg2,wgN)，将该连接权向量Wg进一步朝与输入模式Ak接近的方向调整，而且还调整邻域内的各个连接权向量Wj，jNg(t)。随着学习次数的增加，邻域逐渐缩小。最终得到聚类结果。SOM类似于大脑的信息处理过程，对二维或三维数据的可视是非常有效的。SOM网络的最大局限性是，当学习模式较少时，网络的聚类效果取决于输入模式的先后顺序；且网络连接权向量的初始状态对网络的收敛性能有很大影响。,