常见聚类策略[转贴]

frogfish

聚类策略是聚类的关键技术，策略的选择取决于聚类对象的数据类型、应用目的和限定条件，目前较常见的聚类策略类型如下图。               

聚类策略

系统聚类法

划分聚类法

基于密度聚类法

基于网格聚类法

基于模型聚类法



分解法



聚合法

STING

K-MEANS算法

K-MEDOIDS算法
  

单遍法

SOMS

DBSCAN[1]聚类法

CLIQUE算法

启发式聚类法

Chameleon

frogfish

等级聚类法(hierarchical Clustering methods)

等级聚类法，又称层次聚类法。根据聚类过程方向的不同，可以分为分解法（divisively ）和聚合法（agglomeratively）两类。分解法把整个集合看作一个整体（类），再逐步划分为更小的部分（小类）。聚合法刚好相反，是把每一个个体都看成一个单独的类，尔后从文档相似度入手，通过粘连操作聚集相似度足够大的文档，逐步聚成更大的组（类）。等级聚合聚类法是目前使用最多、研究最为充分的算法，其基本思想，是通过建立并逐步更新距离系数矩阵(或相似系数矩阵)，找出合并最接近的两类，直到全部聚类对象被合并为一类为止。根据类合并时所采用的相似度测算方法的不同，等级聚类又可分为：单链法（single linkage method）、全链法（complete linkage method）、组平均聚类法（average linkage method）。

等级聚合聚类法的突出优点是它能够生成比较规整的类集合，聚类结果不依赖文档的初始排列或输入次序，与聚类过程的先后次序无关，聚类结果比较稳定，不易导致类的重构。但它有不足之处为：①它是“贪心”的，每一聚类步骤都是将两个文档(或文档类)聚集成一个新类，因此，全部聚类过程需要n-1次循环，计算开销较大。如以O表示参加聚类的文献数，n表示文献中的词数，则单链法与组平均法的计算复杂性为O(n2)，全链法则为O(n3) ，较大的计算量，有可能影响实时处理的速度；②一种资源通常只能归入相应类，对多主题文献揭示往往有一定局限性；③不是以主题内容为中心聚类的，聚类结果并不必然符合主题检索的特点；④这一方式通常首先根据相似性确定类，然后再确定类名，因此类名语词在对资源内容的确定和表达上往往有一定的差距。⑤这种算法得到的是球状的、相等大小的聚集，对异常数据比较脆弱，一旦一个步骤（合并或分裂）完成，就不能被撤销或修正。因此也产生了改进的层次聚类方法，如BIRCH算法[1][2]，CURE算法[3]等。BIRCH算法把层次聚集的形成过程到结果看作一棵树，然后结合其他的聚集方法进行修剪。CURE算法选择基于质心和基于代表对象方法之间的中间策略，可以有效的处理大数据集和以种形状分布的数据，可以识别任意形状的簇而且不降低聚集的质量；能更好地过滤异常点，并提高了效率，减少了时间复杂度。一般认为，传统等级聚类也可以使用区分的方式，从资源的整体通过对资源属性差异的层层区分建立等级聚类系统。但在文献两两比较的基础上采用greedy法建立的区分聚类系统，具有与聚合聚类法系统基本相同的特点、问题以及算法复杂性。但也有学者对传统聚类方法的特点与不足存在着不同看法，如在计算开销问题上，有学者就认为，自动聚类的关键是聚类结果的有效性，在目前条件下其计算开销并非主要问题。[4]



划分聚类法(partitioning Clustering methods)

划分聚类法，又称动态聚类法、逐步聚类法，其基本思想是，在一个平面层次上对所有的样本点先作出某种较为粗略的划分，然后按照某种最优的准则进行修正，通过算法的迭代执行，得到一个较为合理的有K个类的聚类结果。近年来研究一直较受关注，其中最为典型的为K-MEANS算法[5]和k-中心点（k-modoid）方法。

K-Means法使用随机方式选择K篇文档作为初始的聚类中心，按照算法的迭代执行，整个算法的结束条件是类的重心(或凝聚点)不再改变。K-means的计算复杂性是O(nkt)，其中，ｎ为文献数量，k为类的数量，t为迭代次数。较之系统聚类法，划分聚类法明显的优势是运算量小，能用于处理庞大的样本数据，也为实时处理提供了一定的可能性。但其缺点是1）K-Means法要求用户必须事先给出要生成的簇的数目，选择初始划分的最佳方向、更新分区和停止准则。且其结果与数据输入顺序有关，不同的初始值可能会导致不同的结果；2）对于噪声和孤立点敏感，很容易受例外情况的影响。适用于发现球状类，但不适合发现非凸面状的簇。不适合大小差别较大的簇。3）这一方式通常首先根据距离来调整确定类，然后再确定类名，因此也存在着类名语词表达问题。4）一个对象只能属于一个类中，不能多维揭示其多重属性。基于K-means法，也提出一些改进形式，如Buckshot 和 Fractation法[6]、二分k-Means法等。

PAM（partitioning around medoid）是最早提出的k-modoid之一，它选用簇中位置最靠近中心的对象作为代表对象（中心点）, 然后反复用非代表对象（非中心点）代替中心点，直到找到最合适的中心点。PAM法有效地消除了对孤立点数据的敏感性，比k-means方法更健壮，不易受极端数据的影响。但PAM只对小数据集非常有效（如100个对象聚成5类），对大数据集效率并不高。CLARA（Cluster LARger Application），也是基于k-medoid类型的算法，是对PAM的改进，Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids，能处理较大的数据集合。复杂度是O（ks2+k(n-k)）,其中s是样本大小。



启发聚式类法（Heuristic Clustering Methods）

最典型的是单遍法(single-pass)[7]。这种方法按照一定的次序，将第一篇文献作为聚类依据，将其余文献按次序依次对其进行相似性比较，如相似性达到系统设定的要求，即将其归入该类，并重新计算其类心（centroid），作为其他文献的匹配依据；如未达到系统要求的阈值，则直接将该文献作为新类的聚类依据，所有文献均依次按这一方式聚类。单遍法的计算复杂性是O(nk)，其中k为类的数量，其计算开销远低于传统的聚类算法。其不足主要有二：一是，这一方法具有明显的次序依赖，对于同一聚类对象按不同的次序聚类，会出现不同的聚类结果，但在检索排序的基础上聚类，由于最重要的资源排列在前，理论上这一方法会具有较强的适应性；另一个不足是，容易出现类目分布不均衡的问题，往往会出现集中形成某些大类的倾向。



基于密度的方法 (density-based Clustering methods)

基于样本之间的距离的聚类方法只能发现球状的簇，基于密度的方法可用来过滤“噪声”孤立点数据，以发现任意形状的簇。其主要思想是只要临近区域的密度（样本的数目）超过某个阈值则继续聚类。即对于给定簇中的每个样本，在一个给定范围的区域中必须至少包含某个数目的样本。包括基于高密度连接区域的DBSCAN[8]聚类方法，通过对象排序识别聚类结构的OPTICS聚类方法，基于密度分布函数的DENCLUE聚类方法。其缺点是也要求用户对初值的设定，而不同的初值会影响聚类的质量；不能处理高纬度的数据。



基于网格聚类法 (grid-based Clustering methods)

这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。其突出的优点就是处理速度快，通常与目标数据库中记录的个数无关的，而只与数据空间的单元有关。代表算法有：基于网格的多分辨率方法，在网格单元中收集统计信息的STING算法、综合了基于密度和基于网格方法的聚类算法，对于大型数据库中的高维数据的聚类非常有效的CLIQUE算法[9]、，通过小波变换来转换原始的特征空间能很好的处理高维数据和大数据集的数据表格的WAVE-CLUSTER算法。



基于模型的方法(model-based methods)

基于模型的方法首先是基于这样一个假定：目标数据集是由一系列的概率分布所决定的。那么，可以在空间中寻找诸如密度分布函数这样的模型来实现聚类。统计的方案和神经网络的方案是近些年两种不同的尝试方向。  

  SOMS(Self organizing Map)[10]是芬兰赫尔辛基大学神经网络专家Kohonen教授在1981年提出的一种基于神经网络模型的聚类方法，它模拟大脑神经系统自组织特征映射的功能，在训练中能无监督地进行自组织学习。生物神经系统进化的过程是空间上相邻的神经元功能慢慢演慢慢相近的过程，相应的，SOM的训练过程，即是将领域上相邻但在n维欧氏空间并不相邻的权值向量wj调整到在欧氏空间也相邻。即权值向量集{wj/j=1,2,……，l，l为输出神经元个数}是对训练样本集中所有样本的描述，权值wj逐渐向样本集中的某些样本靠近，而单个权值向量可看作是以它为获胜神经元（Winner node）的所有样本的聚类中心。神经元之间的距离可以用欧几里德距离、位置向量之间距离、Manhattan距离等来表示。SOMS的优点为：可以实时学习，具有稳定性，无须外界给出评价函数，能够识别向量空间中最又意义的特征，抗噪音能力强。不足之出为：当网络的连接过多，节点数目庞大时，其计算量大;需要较长的学习时间; 网络连接权向量初值的选取对网络收敛性影响很大。

Chameleon（变色龙）方法是一个在层次聚类中采用动态模型的层次聚类算法。它将互连性和近似性都大的簇合并，可以发现高质量的任意形状的簇。但k-最近邻居图中k值和最小二等分、用户指定方式中阈值的选取仍是个难题。在最坏情况下，高维数据的处理代价可能需要O(n2)的时间，效率仍然不够。

转自：http://www.penna.cn/key/article.asp?id=121

风飘云

不错，楼主辛苦了！