聚类算法

读书笔记

---

概念介绍

我们常说的“物以类聚，人以群分”就是聚类最直观的解释。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法。聚类（Cluster）分析是由若干模式（Pattern）组成的，通常，模式是一个度量（Measurement）的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。

距离测度

距离测度	Mahout的实现	简介
欧氏距离测度	EuclideanDistanceMeasure	最直观的的距离，两个n维向量之间的欧式距离就是各个维度上的坐标差值的平方和的开方
平方欧氏距离测度	SquaredEuclideanDistanceMeasure	两个n维向量之间的平方欧式距离就是各个维度上的坐标差值的平方和
曼哈顿距离度量	ManhattanDistanceMeasure	曼哈顿距离度量下，任意两点之间的距离是其坐标的绝对差异的总和
余弦距离度量	CosineDistanceMeasure	余弦距离要求我们把点当作向量来看，在这些向量之间有一个夹角
谷本距离度量	TanimotoDistanceMeasure	谷本距离测度又称Jaccard的距离测度，能捕捉角度和点之间的相对距离有关的信息
加权距离度度	WeightedDistanceMeasure	加权距离度量是Mahout的高级特征，它能让你在不同维上赋予不同的权重，以此对距离度量信息产生影响

算法

K-means聚类

K-means是典型的基于距离的排他的划分方法：给定一个n个对象的数据集，它可以构建数据的k个划分，每个划分就是一个聚类，并且k<=n，同时还需要满足两个要求：
1、每个组至少包含一个对象
2、每个对象必须属于且仅属于一个组。
K-means的基本原理是这样的，给定k，即要构建的划分的数目，首先创建一个初始划分，随机地选择k个对象，每个对象初始地代表了一个簇中心。对于其他的对象，根据其与各个簇中心的距离，将它们赋给最近的簇。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。所谓重定位技术，就是当有新的对象加入簇或者已有对象离开簇的时候，重新计算簇的平均值，然后对对象进行重新分配。这个过程不断重复，直到没有簇中对象的变化。
K-means的最大问题是要求用户必须事先给出k的个数，k的选择一般都基于一些经验值和多次实验结果，对于不同的数据集，k的取值没有可借鉴性。另外，K-means对“噪音”和孤立点数据是敏感的，少量这类的数据就能对平均值造成极大的影响。

canopy聚类

Canopy聚类算法的基本原则是：首先应用成本低的近似的距离计算方法高效的将数据分为多个组，这里称为一个Canopy，Canopy之间可以有重叠的部分；然后采用严格的距离计算方式准确的计算在同一Canopy中的点，将他们分配与最合适的簇中。Canopy聚类算法经常用于K-means聚类算法的预处理，用来找合适的k值和簇中心。
下面详细介绍一下创建Canopy的过程：初始，假设我们有一组点集S，并且预设了两个距离阈值，T1，T2（T1>T2）；然后选择一个点，计算它与S中其他点的距离（这里采用成本很低的计算方法），将距离在T1以内的放入一个Canopy中，同时从S中去掉那些与此点距离在T2以内的点（这里是为了保证和中心距离在T2以内的点不能再作为其他Canopy的中心），重复整个过程直到S为空为止。

模糊K-means聚类

模糊K-means聚类算法是K-means聚类的扩展，它的基本原理和K-means一样，只是它的聚类结果允许存在对象属于多个簇，也就是说：它是一种非排他性的聚类算法。

狄利克雷聚类

前面介绍的三种聚类算法都是基于划分的，下面我们简要介绍一个基于概率分布模型的聚类算法，狄利克雷聚类（Dirichlet Processes Clustering）。
首先我们先简要介绍一下基于概率分布模型的聚类算法（后面简称基于模型的聚类算法）的原理：首先需要定义一个分布模型，简单的例如：圆形，三角形等，复杂的例如正则分布，泊松分布等；然后按照模型对数据进行分类，将不同的对象加入一个模型，模型会增长或者收缩；每一轮过后需要对模型的各个参数进行重新计算，同时估计对象属于这个模型的概率。所以说，基于模型的聚类算法的核心是定义模型，对于一个聚类问题，模型定义的优劣直接影响了聚类的结果。

质量评估

在聚类的评估中，有基于外部数据的评价，也有单纯的基于聚类本身的评价，其基本思想就是：在同一类中，各个数据点越近越好，并且和类外的数据点越远越好；前者称为内聚因子（cohension），后者称为离散因子（separation）。把这两者结合起来，就形成了评价聚类效果的Silhouette因子。
首先看如何评价一个点的聚类效果：
a = 一个点到同一聚类内其它点的平均距离
b = min（一个点到其他聚类内的点的平均距离）
Silhouette因子

$$s = 1 – a/b (a<b)$$
或
$$s = b/a - 1 (a>=b)$$
衡量整体聚类的效果，则是所有点的Silhouette因子的平均值。范围应该在(-1,1), 值越大则说明聚类效果越好。