聚类评估

聚类概念

聚类是一个把数据对象划分为多个簇或者多个组的过程，使得一个簇内的对象具有很高的相似性，但与其他簇内的对象不相似。聚类算法属于无监督学习

聚类分析概念

聚类分析是一个把数据对象划分为子集的过程，每个子集是一个簇，使得簇中的对象彼此相似，但与其他簇中的对象不相似，由聚类分析产生簇的集合叫做聚类。至关重要的区别是，聚类可以自动地发现这些分组是聚类分析的突出优点。

应用场景

客户分类
文本分类
基因识别
空间数据处理
卫星图片识别
数据分析，统计学，机器学习，空间数据库技术，生物学和市场学

聚类的依据–距离

聚类分析是研究对样本或变量的聚类，在进行聚类的时候，方法很多，而这些方法的选择往往与变量的类型是有关的，由于数据的来源以及测量方法的不同，变量大致可以分为两类：

1）定量变量：可就是通常所说的连续变量

2）定性变量：这些量并非真有数量上的变化，而只有性质上的差异，这些变量可以分为有序变量和名义变量

对于连续型变量，有一些典型的距离定义：

绝对值距离	绝对值距离是在一维空间下进行的距离计算
欧式距离	欧式距离是在二维空间下进行的距离计算
闵可夫斯基距离	闵可夫斯基距离是在n维空间下进行的距离计算
切比雪夫距离	是闵可夫斯基距离在n取无穷大时的距离
Lance距离	减弱极端值的影响力

基本聚类方法概述

聚类方法主要划分为：划分聚类，层次聚类，基于密度聚类，基于网格聚类，基于概率模型聚类

方法	一般特点
划分方法	1：发现球形互斥的簇 2：基于距离 3：可以用均值或中心点等代表簇中心 4：对中小规模数据集有效
层次方法	1：聚类是一个层次分解(即多层) 2：不能纠正错误的合并或分析 3：可以集成其他技术，如微聚类或考虑对象"连接"
基于密度的方法	1：可以发现任意形状的簇 2：簇是对象空间中被低密度区域分割的稠密区域 3：簇密度：每个点的"领域"内必须具有最少个数的点 4：可能过滤离群点
基于网格的方法	1：使用一种多分辨率网格数据结构 2：快速处理

划分聚类

给定一个n个对象的集合，划分方法构建数据的k个分区，其中每个分区表示一个簇，使得每个簇内至少包含一个对象。换言之，划分方法在数据集上进行一层划分。

大部分划分方法是基于距离的。给定要构建的分区数k，划分方法首先创建一个初始化分，然后采用一种迭代的重定位技术，通过把对象从一个组迁移到另一个组来改进划分。一个好的划分的一般准则是：同一个簇中的对象尽可能相互靠近或相关，而不同簇中的对象尽可能远离或不同。为了达到全局最优，基于划分的聚类可能需要穷举所有可能的划分，计算量极大。实际上，大多数应用都采用了这两种流行的启发式方法：K-means和K-medoids

算法	描述
k-means	典型的聚类方法，是一种基于形心的技术，使用簇Ci的形心代表该簇
k-modes	是k-means的一个变体，用簇的众数取代簇均值来聚类标称数据
k-prototypes	集成k-means和k-modes，对混合了数值和标称值的数据进行聚类
k-medoids	一种基于代表对象的技术，选择簇中某点作为聚点，PAM是典型的k-medoids算法
PAM	使用迭代和贪心的方法来处理聚类问题
CLARA	在PAM的基础上采取了抽样，为了处理大数据集
CLARANS	CLARANS算法融合了PAM和CLARA两者的优点，是第一个用于空间数据库的聚类算法
PCM	模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法

层次聚类

尽管划分方法满足把对象集划分成一些互斥的族群的基本聚类要求，但是在某些情况下，我们想把数据划分成不同层上的组群。层次聚类方法将数据对象组成层次结构或簇的"树"。层次聚类分为凝聚和分裂两种。凝聚层次聚类使用自底向上的策略把对象组织到层次结构中，从每一个对象都作为一个簇开始，迭代地合并，形成更大的簇。分裂层次聚类使用自顶而下的策略把对象组织到层次结构中，开始令所有给定的对象形成一个簇，迭代地分裂，形成较小的簇。

层次聚类方法可能在合并或分裂点的选择方法上遇到困难。这种决定是至关重要的，因为一旦对象的组群被合并或被分裂，则下一步处理将在新产生的簇上进行。它既不会撤销先前所做的工作，也不会在簇之间进行对象交换。一种提高层次聚类质量的有希望的方向是集成层次聚类和其他聚类技术，形成多阶段聚类。

主要的聚类方法有：BIRCH，Chameleon，CURE，ROCK等

算法	描述
BIRCH	BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程
Chameleon	首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇

基于密度的聚类方法

划分和层次方法旨在发现球状簇，他们很难发现任意形状的簇。为了发现任意形状的簇，作为选择，我们可以把簇看成数据空间中被稀疏区域分开的稠密区域，这是基于密度的聚类方法的主要策略。其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。常见的基于密度的聚类算法有DBSCAN,OPTICS,DENCLUE等。

算法	描述
DBSCAN	DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇
OPTICS	OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果
DENCLUE	是一种基于密度分布函数的聚类算法

基于网格的聚类方法

迄今为止所讨论的方法都是数据驱动的-她们划分对象集并且自动适应嵌入空间中的数据分布。基于网格的聚类方法采用空间驱动的方法，把嵌入空间划分成独立于输入对象分布的单元。

基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。基于网格的聚类算法主要有STING, WaveCluster, CLIQUE等。

算法	描述
STING	利用网格单元保存数据统计信息，从而实现多分辨率的聚类
CLIQUE	在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。
WaveCluster	是一种结合了网格和密度的聚类算法

当我们在数据机上使用一种聚类方法时，我们如何评估聚类的结果是否好？

一般而言，聚类评估估计在数据集上进行聚类的可行性和被聚类方法产生的结果的质量。聚类评估主要包括如下任务：

估计聚类趋势
确定数据集中的簇数
测定聚类质量

估计聚类趋势

聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结构。考虑一下没有任何非随机结构的数据集，如数据空间中均匀分布的点，尽管聚类算法可以为该数据集返回簇，但是这些簇是随机的，没有任何意义。

聚类评估

所以聚类要求数据的非均匀分布。

如何评估数据集的聚类趋势？直观的看，我们可以评估数据集被均匀分布产生的概率，这可以通过空间随机性的统计检验来实现，一种简单但有效的统计量-霍普金斯统计量：

霍普金斯统计量是一种空间统计量，检验空间分布的变量的空间随机性。给定数据集D，它可以看作是随机变量o的一个样本，我们想要确定o在多大程度上不同于数据空间中的均匀分布。可以按照以下步骤计算霍金斯统计量：

$均匀地从D的空间中抽取n个点p_1,p_2,...,p_n。对每个点p_i，我们找出p_i在D中的最邻近，并令x_i为p_i与它在D中最邻近之间的距离，即x_i=min\{disct(p_i，v)\}$
$均匀地从D中抽取n个点q_1,q_2,...,q_n。对每个点q_i，我们找出q_i在D-{q_i}中的最邻近，并令y_i为q_i与它在D-{q_i}中的最邻近距离，即y_i=min\{dist(q_i，v)\}$
$计算霍普金斯统计量H = \frac{\sum_{i=1}^{n}y_i}{\sum_{i=1}^{n}x_i + \sum_{i=1}^{n}y_i}$

如果D是均匀分布的，则 $\sum_{i=1}^{n}{y_i}和\sum_{i=1}^{n}{x_i}$ 将会很接近，因而H大约为0.5,。然而，如果D是高度倾斜的，则 $\sum_{i=1}^{n}{y_i}$ 将显著地小于 $\sum_{i=1}^{n}{x_i}$ ，因为H将接近于0

确定簇数

确定数据集中“正确的”簇数是重要的，不仅因为像k-均值这样的聚类算法需要这种参数，而且因为合适的簇数可以控制适当的聚类分析粒度。这可以看做在聚类分析的可压缩性与准确性之间寻找好的平衡点。

一种简单的经验方法是：对于n个点的数据集，设置簇数p大约为。在期望下，每个簇大约有个点。
肘方法：一种选择正确的簇数的启发式方法是，使用簇内方差和关于簇数的曲线的拐点
交叉验证：把给定的数据集D划分为m个部分，然后使用m-1个部分建立一个聚类模型，并使用剩下的一部分检验聚类的质量

测定聚类质量

如果有可用的基准，则外在方法可以使用它。外在方法比较聚类结果和基准。如果没有基准可用，则我们可以使用内在方法

外在方法又称监督方法，内在方法又称为无监督方法

外在方法

当有基准可以用时，我们可以把它与聚类进行比较，以评估聚类。这样，外在方法的核心任务是，给定基准 $C_g$ ,对聚类C赋予一个评价 $Q（C，C_g）$ 。一种外在方法是否有效很大程度依赖于该方法使用的度量Q.
BCubed精度和召回率。精度是簇中一个特定的类的对象所占的比例，召回率反应有多少同一类别的对象被分配在相同的簇中。