Cluster Analysis:聚类分析

gotea 2013-03-01

Cluster Analysis:聚类分析

 

Cluster analysis或者Clustering的任务是将对象集合分组,使其成为由类似的对象组成的多个类别的过程。Cluster分组的依据是对象数据的自身信息和对象数据之间的关系;分组目标是将当前Cluster中的数据跟其他簇中的数据最大程度上的区别开来。簇内的相似度越高,组件的差异性越大,分簇的效果越好。

聚类分析的目标就是在相似的基础上收集数据来分类,应用于多个领域:包括机器学习、模式识别、图像分析、信息检索等,在多个学科包括数学、计算机学、统计学、生物学、经济学、医学都有应用。在不同学科的不同领域,很多Clustering技术都得到了很大的发展。

Cluster Analysis的wiki地址见这里:http://en.wikipedia.org/wiki/Cluster_analysis

Cluster algorithm在某种程度上和分类算法类似,都是将数据分类。例如给数据打标签(Label),只是分类算法中这些标签Label是预先定义好的,在Cluster算法中,这些标签从数据本身中获取。所以Cluster算法被称为是Unsupervised classification。

 

对于“簇”来说很难精确定义,这也是有如此多的Clustering算法的原因之一。通用描述是一组对象为一个簇,不过很多的研究人员建立自己的簇模型,使用自己不同的Clustering算法。所以说,对于Clustering算法,没有好坏之分,只有是否合适场景的区别;不过对于Clustering算法有个熟悉的概念还是很关键的,也能熟练的区分出来不同的算法类型和适用场景。由于算法实在是太多,本文不可能做到大而全,因此只会对常用的Clustering算法做介绍,考虑其优点和缺点,方便在场景中选择。

 

Cluster Model很多,目前主要包括以下几种:

Connectivity Models:该模型主要基于对象之间的连接性,典型算法如Hierarchical Clustering

Centroid Models:该类模型的重点在于Centroid重心,代表算法为k-means algorithm

Distribution Models:使用统计分布模型,比如在EM算法中的Multivariate Normal Distribution

Density Models:数据空间使用密度区域来进行分簇的模型,如DBSCAN、OPTICS等

Subspace Models:典型算法如Biclustering,使用簇对象和相关属性来进行分簇

Group Models:算法提供分组信息(Group Information)都可以归于此类,很难用精确的定义来说明

Graph-Based Models:这个Graph模型是基于图论的,如Clique;对象归为同一簇的依据是其之间的连接性

 

下面我们来从多个方面来确定下Clustering的不同点:

Hierarchical vs. Partitional:Hierarchical和Partitional最大的区别就是簇集合是否嵌套(nested):Partitional Clustering将数据集合划分为非重叠(non-overlapping)子集合,其中每个数据都属于其中单个簇集合;而Hierarchical Clustering则是将嵌套簇组织为树形结构,每个右节点都是有子簇(subcluster)组成,根节点簇包含所有的数据集。

Exclusive vs. Overlapping vs. Fuzzy:Exclusive表示每个数据都必须归属于单个簇;但是在很多情况下单个数据可以属于多个簇,这种情况就是Non-Exclusive或者Overlapping;而在Fuzzy Clustering中,每个数据以一定的权重(weight)归属于每个簇,权重值位于0(不属于)和1(属于)之间表明数据属于簇的关系值;单个数据归属于簇的权重值和必须为1。基于概率(Probabilistic)分簇和Fuzzy Clustering有类似的思路,他们都能很好的将模型转往Exclusive Clustering,例如将数据赋给权重(weight)最大或者概率(Probability)最高那个簇。

Complete vs.Partial:Complete Clustering会将每个数据都分配给一个簇,而Partional则不然。Partional Clustering认为数据集合中的有些数据可能代表了噪音(Noise)、异常值(Outliers)、无意义的背景音(Uninteresting Background)等,所以这些异常数据可以不必属于任何簇。

Heterogeneous vs. Homogeneous:相同环境下测试获得的数据进行比较,是同构数据(Homogeneous)进行比较分簇;而如果数据采集于不同的环境,则是异构数据(Heterogeneous)。我们经常使用的数据集合是同构数据,来自于同一环境中的数据;在生物学、计算生物学、生物信息学中,计算植物、动物生态方面的信息时经常使用异构环境下的数据进行分析。

 

分簇的先验知识学习就这么多,先明白Cluster Analysis主要是干哪些事?有哪些分类模型?能解决什么问题。本文提到的Hierachical Clustering、K-means等算法都会在后面的学习中提到。对于每种算法,都有很多延伸和扩展的内容,针对每种算法,重点是理解:

算法的优势和劣势;

适合用于哪些场景;

在固定场景下能比其它算法有什么好处;

算法的参数调整对算法结果的影响;

算法的度量目标等

 

准确理解这些内容,才算真正的理解了Clustering算法,后面的文章学习我也是遵从这个思路来学习的。

相关推荐

EffortsRun / 0评论 2014-04-22