【3】无监督学习--3--聚类--概述
聚类(clustering)，就是根据数据的“相 似性”将数据分为多类的过程。 评估两个不同样本之间的“相似性” ，通 常使用的方法就是计算两个样本之间的“距离”。 使用不同的方法计算样本间的距离会关系到聚类 结果的好坏。
聚类分析是数据挖掘及机器学习领域内的重点问题之一，在数据挖掘、模式识别、决策支持、机器学习及图像分割等领域有广泛的应用，是最重要的数据分析方法之一。聚类是在给定的数据集合中寻找同类的数据子集合，每一个子集合形成一个类簇，同类簇中的数据具有更大的相似性。聚类算法大体上可分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法以及基于模型的方法。
一、主要聚类算法的分类
- 层次的方法（也称系统聚类法）（hierarchical method）
- 划分方法（partitioning method）
- 基于密度的方法（density-based method）
- 基于网格的方法（grid-based method）
- 基于模型的方法（model-based method）
…… 其中，前两种算法是利用统计学定义的距离进行度量
1. 层次的方法（也称系统聚类法）（hierarchical method）
定义：对给定的数据进行层次的分解
分类：凝聚的（agglomerative）方法（自底向上）（案例介绍）
思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。
2.分裂的方法（divisive）（自顶向下）
思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件
特点：
类的个数不需事先定好
需确定距离矩阵
运算量要大，适用于处理小样本数据
3. 划分方法（Partitioning method）
较流行的方法有:动态聚类法（也称逐步聚类法），如k－均值算法、k－中心点算法
思想：随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。
特点：
k事先定好
创建一个初始划分，再采用迭代的重定位技术
不必确定距离矩阵
比系统聚类法运算量要小，适用于处理庞大的样本数据
适用于发现球状类
缺陷：
不同的初始值，结果可能不同
有些k均值算法的结果与数据输入顺序有关，如在线k均值算法
用爬山式技术（hill-climbing）来寻找最优解，容易陷入局部极小值
4. 基于密度的方法（density-based method）
主要有DBSCAN，OPTICS法
思想：
只要临近区域的密度超过一定的阀值，就继续聚类
特点：
可以过滤噪声和孤立点outlier，发现任意形状的类
5. 基于网格的方法（grid-based method）
把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构（即量化空间）上进行
6. 基于模型的方法（model-based method）
n 为每个类假定一个模型，寻找数据对给定模型的最佳拟合。
n 此不详述，有兴趣可以参考《DataMing Concepts and Techniques》即《数据挖掘概念于技术》Jiawei Han Micheline Kamber机械工业出版社
7. 不稳定的聚类方法
受所选择变量的影响
如果去掉或者增加一些变量,结果会很不同.因此，聚类之前一定要明确目标，选择有意义的变量。 变量之间的相关性也会影响聚类结果，因此可以先用主成分或因子分析法把众多变量压缩为若干个相互独立的并包含大部分信息的指标，然后再进行聚类
输入参数凭主观导致难以控制聚类的质量
很多聚类算法要求输入一定的参数，如希望产生的类的数目，使得聚类的质量难以控制，尤其是对于高维的，没有先验信息的庞大数据。
首先要明确聚类的目的，就是要使各个类之间的距离尽可能远，类中的距离尽可能近，聚类算法可以根据研究目的确定类的数目，但分类的结果要有令人信服的解释。
在实际操作中，更多的是凭经验来确定类的数目，测试不同类数的聚类效果，直到选择较理想的分类。
二、聚类常用的距离
欧氏距离
欧氏距离是最常用的一种距离度量方法，源于欧式空间中两点的距离。 其计算方法如下:
曼哈顿距离
曼哈顿距离也称作“城市街区距 离”，类似于在城市之中驾车行驶， 从一个十字路口到另外一个十字楼口 的距离。其计算方法如下:
马氏距离
马氏距离表示数据的协方差距离， 是一种尺度无关的度量方式。也就是 说马氏距离会先将样本点的各个属性 标准化，再计算样本间的距离。其计 算方式如下:(s是协方差矩阵，如 图)
夹角余弦
余弦相似度用向量空间中两个向 量夹角的余弦值作为衡量两个样本差 异的大小。余弦值越接近1，说明两 个向量夹角越接近0度，表明两个向 量越相似。
三、Sklearn vs. 聚类
scikit-learn库(以后简称sklearn库)提 供的常用聚类算法函数包含在 sklearn.cluster这个模块中，如:K-Means， 近邻传播算法，DBSCAN，等 以同样的数据集应用于不同的算法，可能会得 到不同的结果，算法所耗费的时间也不尽相同， 这是由算法的特性决定的。
sklearn.cluster模块提供的各聚类算法函数可以使用不同的数据形式作为 输入:
标准数据输入格式:[样本个数，特征个数]定义的矩阵形式。
相似性矩阵输入格式:即由[样本数目，样本数目]定义的矩阵形式，矩阵中 的每一个元素为两个样本的相似度，如DBSCAN， AffinityPropagation(近邻传 播算法)接受这种输入。如果以余弦相似度为例，则对角线元素全为1. 矩阵中每 个元素的取值范围为[0,1]。
| 算法名称 | 参数 | 可扩展性 | 用集 | 几何（相似性度量） |
|---|---|---|---|---|
| K-Means | 群集数 | 非常大n_samples，中型n_clusters有 MiniBatch代码 | 通用，甚至集群大小，平面几何，集群不太多 | 点之间的距离 |
| Affinity propagation | 阻尼，样品偏好 | 不可扩展的n_samples | 许多簇，群集大小不均匀，非平面几何 | 图距离（例如最近邻图） |
| Mean-shift | 带宽 | 不可扩展 n_samples | 许多簇，群集大小不均匀，非平面几何 | 点之间的距离 |
| Spectral clustering | 群集数 | 中等n_samples，小n_clusters | 几个簇，甚至簇大小，非平面几何 | 图距离（例如最近邻图） |
| Ward hierarchical clustering | 群集数 | 大n_samples和n_clusters | 许多集群，可能连接限制 | 点之间的距离 |
| Agglomerative clustering | 簇数，链接类型，距离 | 大n_samples和n_clusters | 许多集群，可能是连接约束，非欧几里德距离 | 任何成对距离 |
| Gaussian mixtures | 聚类个数及其他；超参 | 不可扩展 | 平面几何，适合密度估算；复杂度高，不适合处理大规模数据 | 马氏距离 |
| DBSCAN | 社区大小 | 非常大n_samples，中等n_clusters | 非平面几何，不均匀的簇大小 | 点间距离 |
| Birch | 分支因子，阈值等其他超参 | 大n_clusters和n_samples | 大数据集，异常值去除，数据简化 | 两点间的欧式距离 |
四、讨论
算法的选择没有绝对
当聚类结果被用作描述或探查工具时，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。
聚类分析中权重的确定 当各指标重要性不同的时候，需要根据需要调整权重。如加权欧式距离，权重可以用专家法确定。
参考资料：
- 上海财经大学统计学系 吕江平
- 北京理工大学 礼欣 www.python123.org
