ch8 聚类数据挖掘技术优秀课件.pptVIP

第八章 聚类数据挖掘技术 k-中心点算法（k-medoids） 也称PAM算法（Partitioning Around Medoids） 基于有代表性的数据（中心点），而不是均值代表每个簇。 思路 1.为每个簇随机选择一个代表对象 中心点 ； 2.剩余的对象根据其与代表对象的距离分配给与其最近的一个簇； 3.反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。 为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代，对于每一个非中心点对象Oj，下面的四种情况被考虑:第一种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh所代替作为中心点，且Oj离一个Om最近，i≠m，那么Oj被重新分配给Om。第二种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oj被重新分配给Oh。第三种情况：Oj当前隶属于中心点Om，m≠i。如果Oi被Oh代替作为一个中心点，而Oj依然离Om最近，那么对象的隶属不发生变化。第四种情况：Oj当前隶属于中心点Om，m≠i。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oi被重新分配给Oh。 PAM算法特点 比k-means健壮，但对于大数据集效率不高。 当存在 “噪声”和离群数据时，k-中心点方法比k均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。 k-中心点方法的执行代价比k-平均高。 改进算法 CLARA Clustering Large Applications ,1990 用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的中心点 。 如果样本是以非随机的方式选取，它应当足以代替原来的数据集合。从中选出的代表对象（中心点）很可能与从整个数据集合选出的代表相似。 改进算法 CLARANS “随机化的”CLARA ，1994 利用多次不同抽样来改进CLARA。 其聚类过程可以被描述为对一个图的收索过程，图中的每一个节点都是一个潜在的解，即k个中心点的集合。在替换了一个中心点后得到的聚类结果被当成是前聚类结果的邻居。如果一个更好的邻居被发现，也就是说它有更小的平方误差值，clarans移到该邻居节点，处理过程重新开始，如果没有发现更好的邻居，则达到局部最优。 BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。 CURE算法的主要步骤如下： ⑴从源数据集中抽取一个随机样本S。 ⑵为了加速聚类，把样本划分成p份，每份大小相等。 ⑶对每个划分进行局部地聚类。 ⑷根据局部聚类结果，通过随机抽样剔除孤立点。主要有两种措施：如果一个簇增长得太慢，就去掉它；在聚类结束的时候，非常小的类被剔除。 ⑸对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子?收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。 ⑹用相应的簇标签来标记数据。 密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。 OPTICS算法是对DBSCAN算法的改进，因为在DBSCAN算法中需要用户设定ε-邻域和MitPts，但是在实际应用中用户往往很难确定这些参数，而且这些参数设置的不同往往会导致聚类结果有很大差别。在OPTICS算法中认定对象应该以特定的顺序进行处理，这个顺序首先处理最小的ε值密度可达的对象，这样可以首先完成高密度的聚类。 将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类都在这个网格结构中上进行。 其优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING算法、用小波转换方法进行聚类的WaveCluster方法和在高维数据空间基于网格和密度的聚类方法。 WaveCluster方法首先通过在数据空间上强加一个多维网格结