Cluster Analysis：聚类分析

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算法，后面的文章学习我也是遵从这个思路来学习的。