09
星期五
年12月
Birdsofafeatherflocktogether，深入浅出，聚类分析
数据分析
深入浅出，聚类分析：介绍
聚类分析(clusteranalysis)即根据事物的某方面特征把它们划分成为若干小类。其目标是使隶属于同一类中的对象具有较高的相似度（相关的），而不同类中的对象具有较低的相似度（不相关的）。类内的同质性越大，类间的差异性越大，则聚类效果越好。
分类是“监督学习”，根据对象信息和已知的类标记为对象开发模型，用以对新的、无标记的对象进行标记；而聚类则是“无监督学习”，即将本身没有类别属性的对象根据一定特征划分为不同的类别，所谓Birdsofafeatherflocktogether，“物以类聚，人以群分”。聚类可看作是一种分类[1]，但一般意义上的“分类”是监督分类（supervisedclassification），而“聚类”则是非监督分类（unsupervisedclassification），它们分属不同概念范畴。
目前，聚类算法多达百余种，可以从不同角度对其进行划分：层次的（嵌套的）与划分的（非嵌套的），互斥的、重叠的与模糊的，完全的与部分的。可从字面上简单理解上述划分的含义，对其进行阐释和分析不是本文所要讨论的重点。本文将从较一般的角度，即从聚类算法/模型的角度[2]，对聚类进行介绍，旨在更加理性地认识“聚类”本身。
○
基于质心的聚类模型（centroidmodels）。
○
基于统计分布的聚类模型（distributionmodels）。
○
基于连通性的聚类模型（connectivitymodels）。
○
基于统计分布的聚类模型（distributionmodels）。
○
基于密度的聚类模型（densitymodels）。
○
其他聚类模型。如两步聚类（twostepclustering）、自组织（self-organizing）聚类、子空间聚类模型（subspacemodels）、组模型（groupmodels）聚类、基于图的聚类模型（graph-basedmodels）。
关键词：基于质心的聚类模型
聚类是为了发现不同的簇（cluster，即类），而这些簇具有不同类型。其中，可基于原型划分不同的对象，具体而言，每个对象到其所属簇的原型的距离比到其他簇的原型的距离更“近”。对于连续属性的数据，簇的原型通常是质心，基于质心的聚类模型即用质心来定义了原型。
此划分的典型算法是K-means聚类，也被称为快速聚类。这是一种基于距离的聚类算法，认为对象间的距离越近，相似度就越大，从而将空间中距质心较近的观测点视为同类。其优点在于快速、简洁、高效，而缺点在于K值和初始质心的选择难以给定（后文将着重讨论如何确定K的取值）、不适用于非数值型变量的情况（如分类变量）、对噪声数据和孤立点敏感，以及无法处理非球形的、不同尺寸的和不同密度的簇。
正因为k-means以均值点作为质心，所以该算法易受噪声干扰，从而降低了其解的稳健性。PAM（partitioningaroundmedoids）聚类在K-means的基础上克服了该缺点，其不选择均值而选择中心点作为参照点（mediod，即簇中位置最中心的对象），这也是它与k-means聚类的最大区别。
关键词：基于连通性的聚类模型
层次聚类从距离和连通性的角度设计算法，一般包括自上而下的聚合型聚类和自下而上的拆分型聚类。简单理解，聚合型聚类开始将每个对象都视为一个簇，逐步合并两个最接近的簇，最终所有对象被凝聚为一个簇；而拆分型聚类开始则将所有对象视为一个簇，逐步分裂距离尽可能远的一个簇，最终所有对象都被分裂成一个簇。该类算法聚类的结果一般表现为确定的层次关系，又被称为系统聚类，常见的算法包括CURE，BIRCH，MST分裂层次聚类算法等。其缺点在于缺乏全局目标函数，合并一旦执行便无法撤销，因而阻碍全局最优标准的现实，且时间复杂度和空间复杂度高，计算代价昂贵。
关键词：基于统计分布的聚类模型
基于统计模型设计聚类算法，其思想是，如果对象存在于某一类中，则从某小类中所观测到的数据应服从于某种统计分布，即假设数据是由一个统计过程产生的，则可以通过拟合数据的统计模型来描述数据。这种聚类的结果一般是不确定的。
这里讨论混合模型（mixturemodels）,其使用若干统计分布对数据建模，通过估计统计模型的参数来描述不同的类。典型的算法是EM聚类，E代表expectation，即期望，M代表maximization，即最大化。EM聚类算法认为不同类中的对象服从不同的统计分布，而整体则是来自于多个分布的一个混合，每一个分布中的对象即为一个子类，其通过对象落入不同分布的概率来判定该对象应属于哪一个子类，进而实现聚类。
关键词：基于密度的聚类模型
基于密度的聚类模型将观测点分布密集的区域视为一类，寻找被低密度区域分离的高密度区域。在聚类中，有关密度的定义方法有多种，这里将提到被讨论较多的基于中心的方法。DBSCAN（densitybasedspatialclusteringofapplicationswithnoise）算法正是使用这种方法进行聚类。首先，明确核心点（corepoint）、边界点（borderpoint）和噪声点（noisepoint）的概念，简单理解，核心点即密集区域中的点，边界点即密集区域边界上的点，噪声点即非密集区域中的点，对其详细定义可参考数据挖掘经典教材——Pang-NingTan的《数据挖掘导论：完整版》。现在，简单讨论DBSCAN算法的聚类过程，标记所有样本点，删除噪声点，将距离足够靠近的核心点或与核心点足够靠近的边界点视为同一类，最后将靠近不同核心点的边界点指派到不同的类中。
基于密度的聚类模型的优点是显而易见的，如它可以很好的处理含有噪声的数据，能够发现不同形状和大小的类，解决k-means算法无法克服的问题。但缺点同样表现在开销上，而对密度的定义则是该类算法所面对的主要困难。
关键词：其他聚类模型
基于前述划分，在其他聚类模型中，本文仅对SOM（self-organizingmap）自组织映射作简要介绍。SOM是本世纪出由Kohonen提出的一种基于神经网络的可视化数据技术，被广泛应用于聚类分析中。在该背景下讨论的SOM是一种基于原型的聚类算法，其目标在于发现质心的集合，并将每个对象指派到最合适的质心上。具体的算法和实现过程可参考维基百科self-organizingmap(som)（