ch8聚类数据挖掘技术.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,ch8聚类数据挖掘技术,聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。,数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。,二、聚类在数据挖掘中的典型应用：聚类分析可以作为其它算法的预处理步骤,：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息。,可以作为一个独立的工具来获得数据的分布情况,：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。,聚类分析可以完成孤立点挖掘,：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。,广泛的应用领域,商务：,帮助市场分析人员从客户信息库中发现不同的客户群,，,用购买模式来刻画不同的客户群的特征,土地使用：,在地球观测数据库中识别土地使用情况相似的地区,保险业：,汽车保险单持有者的分组,城市规划：,根据,房子的类型，价值和地理分布对房子分组,生物学：,推导植物和动物的分类，对基因进行分类,聚类分析的目标就是形成的数据簇，并且满足下面两个条件：,一个簇内的数据尽量相似（,high,intra-class,similarity,）；,不同簇的数据尽量不相似（,low,inter-class,similarity,）。,衡量一个聚类分析算法质量，依靠：,相似度测量机制是否合适是否能发现数据背后潜在的、手工难以发现的类知识。,三、聚类分析的目标:,四、聚类分析方法的分类:,按照聚类的标准，聚类方法可分为如下两种：,统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。,概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。,按照聚类算法所处理的数据类型，聚类方法可分为三种：,数值型数据聚类方法：所分析的数据的属性只限于数值数据。,离散型数据聚类方法：所分析的数据的属性只限于离散型数据。,混合型数据聚类方法：能同时处理数值和离散数据。,按照聚类的尺度，聚类方法可被分为以下三种：,基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如,k,-meansk,-medoids,、,BIRCH,、,CURE,等算法。,基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。,基于互连性,(Linkage-Based),的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。,按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。,划分法（,Partitioning Methods,）：,基于一定标准构建数据的划分。属于该类的聚类方法有：,k-means,、,k-modes,、,k-prototypes,、,k-medoids,、,PAM,、,CLARA,、,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)=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,个对象的数据集，划分聚类技术将构造数据,k,个划分，每一个划分就代表一个簇，,k,n,。,也就是说，它将数据划分为,k,个簇，而且这,k,个划分满足下列条件：,每一个簇至少包含一个对象。,每一个对象属于且仅属于一个簇。,对于给定的,k,，,算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。,启发式方法,:k-,平均算法和,k-,中心点算法,k-,均值算法,:,每个簇用该簇中对象的平均值来表示。,k-,中心点算法,:,每个簇用接近聚类中心的一个对象来表示,k,-means,算法，也被称为,k,-,平均或,k,-,均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。,首先将所有对象随机分配到,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,=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 属性 2,1 1 1,2 2 1,3 1 2,4 2 2,5 4 3,6 5 3,7 4 4,8 5 4,迭代次数 平均值平均值 产生的新簇 新平均值 新平均值,（簇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。,对于产生的簇分别计算平均值，得到平均值点。,对于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,-means算法的性能分析,主要优点：,是解决聚类问题的一种经典算法，简单、快速。,对处理大数据集，该算法是相对可伸缩和高效率的。,当结果簇是密集的，它的效果较好。,主要缺点,在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。,必须事先给出,k,（,要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。,不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,k,-means算法的几种改进方法,k,-mode,算法：实现对离散数据的快速聚类，保留了,k,-means,算法的效率同时将,k,-means,的应用范围扩大到离散数据。,k,-prototype,算法：可以对离散与数值属性两种混合的数据进行聚类，在,k,-prototype,中定义了一个对数值与离散属性都计算的相异性度量标准。,k,-,中心点算法,k,-means,算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。,k-中心点算法（k-medoids）,也称PAM算法（,Partitioning Around Medoids）,基于有代表性的数据（,中心点,），而不是均值代表每个簇。,思路,1.为每个簇随机选择一个代表对象(中心点)；,2.剩余的对象根据其与代表对象的距离分配给与其最近的一个簇；,3.反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。,PAM,作为最早提出的,k,-,中心点算法之一，它选用簇中位置最中心的对象作为代表对象，试图对,n,个对象给出,k,个划分。,代表对象也被称为是中心点，其他对象则被称为非代表对象。,最初随机选择,k,个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。,在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。,对可能的各种组合，估算聚类结果的质量。一个对象,O,i,被可以产生最大平方,-,误差值减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。,计算用非代表对象,h,替换代表对象,i,的,总代价,：,单个数据的,替换代价,：用,h,代替,i,后，,j,到中心点距离的变化,为了判定一个非代表对象,O,h,是否是当前一个代表对象,O,i,的好的替代，对于每一个非中心点对象,O,j,，下面的四种情况被考虑:,第一种情况：,O,j,当前隶属于中心点对象,O,i,。如果,O,i,被,O,h,所代替作为中心点，且,O,j,离一个,O,m,最近，,i,m,，那么,O,j,被重新分配给,O,m,。第二种情况：,O,j,当前隶属于中心点对象,O,i,。如果,O,i,被,O,h,代替作为一个中心点，且,O,j,离,O,h,最近，那么,O,j,被重新分配给,O,h,。第三种情况：,O,j,当前隶属于中心点,O,m,，,m,i,。如果,O,i,被,O,h,代替作为一个中心点，而,O,j,依然离,O,m,最近，那么对象的隶属不发生变化。第四种情况：,O,j,当前隶属于中心点,O,m,，,m,i如果,O,i,被,O,h,代替作为一个中心点，且,O,j,离,O,h,最近，那么,O,i,被重新分配给,O,h,。,每当重新分配发生时，平方,-,误差,E,所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方,-,误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。,如果总代价是负的，那么实际的平方,-,误差将会减小，,O,i,可以被,O,h,替代。,如果总代价是正的，则当前的中心点,O,i,被认为是可接受的，在本次迭代中没有变化。,总代价定义如下：,其中，,C,jih,表示,O,j,在,O,i,被,O,h,代替后产生的代价。下面介绍上面所述的四种情况中代价函数的计算公式，其中所引用的符号有：,O,i,和,O,m,是两个原中心点，,O,h,将替换,O,i,作为新的中心点。,第二种情况,O,j,被重新分配给,O,h,，,C,jih,=,d,(,j,h,)-,d,(,j,i,),第一种情况,O,j,被重新分配给,O,m,，,C,jih,=,d,(,j,m,)-,d,(,j,i,),第三种情况,O,j,的隶属不发生变化，,C,jih,=,0,第四种情况,O,i,被重新分配给,O,h,，,C,jih,=,d,(,j,h,)-,d,(,j,m,),算法 PAM（,k,-中心点算法）,输入：簇的数目,k,和包含,n,个对象的数据库。,输出：,k,个簇，使得所有对象与其最近中心点的相异度总和最小。,（1）任意选择,k,个对象作为初始的簇中心点；,（2）REPEAT,（3）指派每个剩余的对象给离它最近的中心点所代表的簇；,（4）REPEAT,（5）选择一个未被选择的中心点,O,i,；,（6）REPEAT,（7）选择一个未被选择过的非中心点对象,O,h,；,（8）计算用,O,h,代替,O,i,的总代价并记录在,S,中；,（9）UNTIL 所有的非中心点都被选择过；,（10）UNTIL 所有的中心点都被选择过；,（11）IF 在,S,中的所有非中心点代替所有中心点后的计算出的总代价有小于0的存在 THEN 找出,S,中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的,k,个中心点的集合；,（12）UNTIL 没有再发生簇的重新分配，即所有的,S,都大于0.,实例,假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设,k,=2）。样本点间距离如下表所示:,样本点 起始中心点为A,B,样本点,A,B,C,D,E,A,0,1,2,2,3,B,1,0,2,4,3,C,2,2,0,1,5,D,2,4,1,0,3,E,3,3,5,3,0,第一步 建立阶段：假如从5个对象中随机抽取的2个中心点为A，B,则样本被划分为A、C、D和B、E，如图所示。,第二步 交换阶段：假定中心点A、B分别被非中心点C、D、E替换，根据PAM算法需要计算下列代价,TC,AC,、,TC,AD,、,TC,AE,、,TC,BC,、,TC,BD,、,TC,BE,。,以,TC,AC,为例说明计算过程：,a)当A被C替换以后，A不再是一个中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，,C,AAC,=,d,(,A,B,)-,d,(,A,A,)=1。,b)B是一个中心点，当A被C替换以后，B不受影响，,C,BAC,=,0,。,c)C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算法代价函数的第二种情况,C,CAC,=,d,(C,C,)-,d,(,C,A,)=0-2=-2。,d)D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况,C,DAC,=,d,(,D,C,)-,d,(,D,A,)=1-2=-1。,e)E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是 B，根据PAM算法代价函数的第三种情况,C,EAC,=0。,因此，,T,C,AC,=,C,A,AC,+,C,B,AC,+,CB,AC,+,CD,AC,+CE,AC,=1+0-2-1+0=-2。,在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，选择第一个最小代价的替换（也就是C替换A），根据图（a）所示，样本点被划分为 B、A、E和C、D两个簇。图（b）和图（c）分别表示了D替换A，E替换A的情况和相应的代价,(a)C替换A,TC,AC,=,-2 (b)D替换A,TC,AD,=,-2 (c)E替换A,TC,AE,=,-1,图 替换中心点A,图（a）、（b）、（c）分别表示了用C、D、E替换B的情况和相应的代价。,C,替换,B,TC,BC,=,-2 (b)D,替换,B,TC,BD,=,-2 (c)E,替换,B,TC,BE,=,-2,图,替换中心点,B,通过上述计算，已经完成了,PAM,算法的第一次迭代。在下一迭代中，将用其他的非中心点,A,、,D,、,E,替换中心点,B,、,C,，,找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。,PAM算法特点,比k-means健壮，但对于大数据集效率不高。,当存在“噪声”和离群数据时，k-中心点方法比k均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。,k-中心点方法的执行代价比k-平均高。,改进算法,CLARA,(Clustering Large Applications),1990,用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的中心点。,如果样本是以非随机的方式选取，它应当足以代替原来的数据集合。从中选出的代表对象（中心点）很可能与从整个数据集合选出的代表相似。,改进算法,CLARANS,(“随机化的”CLARA)，1994,利用多次不同抽样来改进CLARA。,其聚类过程可以被描述为对一个图的收索过程，图中的每一个节点都是一个潜在的解，即k个中心点的集合。在替换了一个中心点后得到的聚类结果被当成是前聚类结果的邻居。如果一个更好的邻居被发现，也就是说它有更小的平方误差值，clarans移到该邻居节点，处理过程重新开始，如果没有发现更好的邻居，则达到局部最优。,(2)层次聚类方法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：,凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。,分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。,层次凝聚的代表是,AGNES,算法。层次分裂的代表是,DIANA,算法。,AGNES算法,AGNES(,AGglomerative,NESting,),算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。,算法 AGNES（自底向上凝聚算法）,输入：包含n个对象的数据库，终止条件簇的数目k。,输出：k个簇，达到终止条件规定簇数目。,(1)将每个对象当成一个初始簇；,(2)REPEAT,(3)根据两个簇中最近的数据点找到最近的两个簇；,(4)合并两个簇，生成新的簇的集合；,(5)UNTIL 达到定义的簇的数目；,实例,序号属性 1属性 2,111,212,321,422,534,635,744,845,步骤最近的簇距离最近的两个簇合并后的新簇,111，21，2，3，4，5，6，7，8,213，41，2，3，4，5，6，7，8,315，61，2，3，4，5，6，7，8,417，81，2，3，4，5，6，7，8,511，2，3，41，2，3，4，5，6，7，8,615，6，7，81，2，3，4，5，6，7，8结束,第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。,第2步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇。,第3步：重复第2步的工作，5，6点成为一簇。,第4步：重复第2步的工作，7，8点成为一簇。,第5步：合并1，2，3，4成为一个包含四个点的簇。,第6步：合并5，6，7，8，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。,AGNES算法的性能分析,AGNES,算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。,这种聚类方法不具有很好的可伸缩性，因为合并的决定需要检查和估算大量的对象或簇。,假定在开始的时候有,n,个簇，在结束的时候有,1,个簇，因此在主循环中有,n,次迭代，在第,i,次迭代中，我们必须在,n-i+,1,个簇中找到最靠近的两个聚类。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为,O,(,n,2,),，,该算法对于,n,很大的情况是不适用的。,DIANA算法,DIANA(Divisive,ANAlysis,),算法是典型的分裂聚类方法。,在聚类中用户能定义希望得到的簇数目作为一个结束条件。同时，它使用下面两种测度方法：,簇的直径：在一个簇中的任意两个数据点的距离中的最大值。,平均相异度（平均距离）：,算法 DIANA（自顶向下分裂算法）,输入：包含n个对象的数据库，终止条件簇的数目k。,输出：k个簇，达到终止条件规定簇数目。,（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为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。,（9）END.,实例,序号属性 1属性 2,111,212,321,422,534,635,744,845,步骤具有最大直径的簇splinter groupOld party,11，2，3，4，5，6，7，812，3，4，5，6，7，8,21，2，3，4，5，6，7，81，23，4，5，6，7，8,31，2，3，4，5，6，7，81，2，34，5，6，7，8,41，2，3，4，5，6，7，81，2，3，45，6，7，8,51，2，3，4，5，6，7，81，2，3，45，6，7，8 终止,第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。,1的平均距离：（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步，重复第2步的工作，splinter group中放入点4。,第5步，没有在old party中的点放入了splinter group中且达到终止条件（k=2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。,改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。,下面介绍两个改进的层次聚类方法,CURE,和,BIRTH,。,BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子,B,和阂值,T,的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。,BIRCH算法主要分两个阶段进行：,阶段一：扫描数据库，建立一个初始的,CF,树，,它可以被,看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，,随着对象的插入，,CF,树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。因此，,BIRTH,方法对增量或动态聚类也非常有效。,阶段二：采用某个聚类算法对,CF,树的叶节点进行聚类。,在这个阶段可以执行任何聚类算法，例如典型的划分方法。,BIRCH算法具有可伸缩性，通过对数据集的首次扫描产生一个基本聚类，二次扫描则进一步改进聚类质量并处理孤立点。BIRCH算法处理速度较快，只是对非球形簇处理效果不好。,很多聚类算法只擅长处理球形或相似大小的聚类，另外有些聚类算法对孤立点比较敏感。CURE算法解决了上述两方面的问题，选择基于质心和基于代表对象方法之间的中间策略，即选择空间中固定数目的具有代表性的点，而不是用单个中心或对象来代表一个簇。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向簇中心“收缩”它们，即合并两个距离最近的代表点的簇。,CURE算法的主要步骤如下：,从源数据集中抽取一个随机样本S。,为了加速聚类，把样本划分成,p,份，每份大小相等。,对每个划分进行局部地聚类。,根据局部聚类结果，通过随机抽样剔除孤立点。主要有两种措施：如果一个簇增长得太慢，就去掉它；在聚类结束的时候，非常小的类被剔除。,对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子,收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。,用相应的簇标签来标记数据。,由于CURE回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。CURE的复杂度是,O,(,n,)，,n,是对象的数目，所以该算法适合大型数据的聚类。,(3)密度聚类,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的,I,/,O,操作。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。,DBSCAN,（,Density-Based Spatial Clustering of Applications with Noise,）,一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。,DBSCAN,定义,1,对象的,-,临域：给定对象在半径,内的区域。,定义,2,核心对象：如果一个对象的,-,临域至少包含最小数目,MinPts,个对象，则称该对象为核心对象。,例如，在图中，,=1cm,，,MinPts,=5,，,q,是一个核心对象。,定义,3,直接密度可达：给定一个对象集合,D,，,如果,p,是在,q,的,-,邻域内，而,q,是一个核心对象，我们说对象,p,从对象,q,出发是直接密度可达的。,例如，在图中，,=1cm,，,MinPts,=5,，,q,是一个核心对象，对象,p,从对象,q,出发是直接密度可达的。,图 直接密度可达,定义,4,密度可达的：如果存在一个对象链,p,1,，,p,2,，,，,p,n,，,p,1,=,q,，,p,n,=,p,，对,p,i,D,，（,1=,i,=,n,），,p,i+1,是从,p,i,关于,和,MitPts,直接密度可达的，则对象,p,是从对象,q,关于,和,MinPts,密度可达的。,例如，在图中，,=1cm,，,MinPts,=5,，,q,是一个核心对象，,p,1,是从,q,关于,和,MitPts,直接密度可达，,p,是从,p,1,关于,和,MitPts,直接密度可达，则对象,p,从对象,q,关于,和,MinPts,密度可达的。,图 密度可达,定义,5,密度相连的：如果对象集合,D,中存在一个对象,o,，,使得对象,p,和,q,是从,o,关于,和,MinPts,密度可达的，那么对象,p,和,q,是关于,和,MinPts,密度相连的。,定义,6,噪声,:,一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。,图 密度相连,图 噪声,DBSCAN,通过检查数据集中每个对象的,-,邻域来寻找聚类。如果一个点,p,的,-,邻域包含多于,MinPts,个对象，则创建一个,p,作为核心对象的新簇。然后，,DBSCAN,反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,DBSCAN算法描述,算法5-5 DBSCAN,输入：包含,n,个对象的数据库，半径,，最少数目MinPts。,输出：所有生成的簇，达到密度要求。,1.REPEAT,2.从数据库中抽取一个未处理过的点；,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，11。,序号,属性 1,属性 2,1,1,0,2,4,0,3,0,1,4,1,1,5,2,1,6,3,1,7,4,1,8,5,1,9,0,2,10,1,2,11,4,2,12,1,3,步骤,选择的点,在中点的个数,通过计算可达点而找到的新簇,1,1,2,无,2,2,2,无,3,3,3,无,4,4,5,簇C,1,：1，3，4，5，9，10，12,5,5,3,已在一个簇C,1,中,6,6,3,无,7,7,5,簇C,2,：2，6，7，811,8,8,2,已在一个簇C,2,中,9,9,3,已在一个簇C,1,中,10,10,4,已在一个簇C,1,中，,11,11,2,已在一个簇C,2,中,12,12,2,已在一个簇C,1,中,算法执行过程：,第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，已经在簇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中，由于这已经是最后一点所有点都已处理，程序终止。,步骤,选择的点,在中点的个数,通过计算可达点而找到的新簇,1,1,2,无,2,2,2,无,3,3,3,无,4,4,5,簇C,1,：1，3，4，5，9，10，12,5,5,3,已在一个簇C,1,中,6,6,3,无,7,7,5,簇C,2,：2，6，7，8，11,8,8,2,已在一个簇C,2,中,9,9,3,已在一个簇C,1,中,10,10,4,已在一个簇C,1,中，,11,11,2,已在一个簇C,2,中,12,12,2,已在一个簇C,1,中,OPTICS,算法,是对,DBSCAN,算法的改进，因为在,DBSCAN,算法中需要用户设定,-,邻域和,MitPts,，,但是在实际应用中用户往往很难确定这些参数，而且这些参数设置的不同往往会导致聚类结果有很大差别。在,OPTICS,算法中认定对象应该以特定的顺序进行处理，这个顺序首先处理最小的,值密度可达的对象，这样可以首先完成高密度的聚类。,DENCLUE,算法,的依据是某个数据点在邻域内的影响可以用一个数学函数来形式化地模拟，这个函数为影响函数。所聚类数据空间的整体密度看成是所有数据点影响函数的总和。在聚类时就根据全局密度函数的局部最大，即密度吸引点来确定。,将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类都在这个网格结构中上进行。,其优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。,在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING算法、用小波转换方法进行聚类的WaveCluster方法和在高维数据空间基于网格和密度的聚类方法。,(4)网格聚类,STING(Statistaical,Information Grid_based method),是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的,矩形,单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易的从底层单元的计算得到。这些参数包括属性无关的参数,count,、,属性相关的参数,m,（,平均值）、,s,(,标准偏差,),、,min,(,最小值,),、,max,(,最大值,),以及该单元中属性值遵循的分布类型。,STING,算法采用了一种多分辨率的方法来进行聚类分析，该聚类算法的质量取决于网格结构最低层的粒度。如果粒度比较细，处理的代价会显著增加；但如果粒度较粗，则聚类质量会受到影响。,STING算法,STING,算法的主要优点是效率高，通过对数据集的一次扫描来计算单元的