“聚类”（clustering）算法是“无监督学习”算法中研究最多、应用最广的算法，它试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”（cluster）
因为聚类是在未标注样本上的分类算法，所以不像之前我们介绍的其它算法一样，我们可以直观的知道训练出来的模型的好坏，即我们不能通过比对测试样本的预测结果和真实预测结果误差值来近似泛化误差。
一 、 聚类结果好坏的评估指标：性能度量
聚类性能度量亦称聚类“有效性指标”（validity index），与监督学习一样，它的目的是为了用来评估聚类结果的好坏，当我们能通过性能度量来评估聚类的好坏时，我们就可以通过将这个性能度量作为优化目标来生成更好的聚类结果。
那么，对于聚类算法来说，什么样的结果是好的呢？
即想要---------聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低！！
按照这样的定义，我们将聚类的性能度量大致划分为了以下两类：
1、外部指标
这一类的性能度量是将聚类结果与某个“参考模型”（reference model）进行比较，比如与领域专家的划分结果进行比较（其实这已经算是某种程度上对数据进行标注了），称为“外部指标”（external index）
基于对参考模型权威的信任，我们可以认为参考模型对样本的划分是满足簇内相似度高且簇间相似度低的。所以对于“外部指标”，我们的度量目的就是要使得我们的聚类结果与参考模型尽可能相近，通常通过将聚类结果与参考模型结果对应的簇标记向量进行两两比对，来生成具体的性能度量，其度量的中心思想是：聚类结果中被划分到同一簇中的样本在参考模型中也被划分到同一簇的概率越高代表聚类结果越好。常用的性能指标有：Jaccard系数、FM指数、Rand指数。（图片来自网上）
2、内部指标
这一类的性能度量是直接考察聚类结果而不利用任何参考模型，称为“内部指标”
“内部指标”通过计算簇内的样本距离，以及簇间的样本距离来对聚类结果进行评估。其度量的中心思想是：簇内的样本距离近似于簇内相似度，簇间样本距离近似于簇间相似度，通过计算并组合这些样本/簇距离的值来构建一个符合需要的性能度量指标。常用的性能指标有：DB指数、Dunn指数
以DB指数为例，其代表的是：任意两个簇 Ci 和 Cj，它们的簇内平均距离的和（ avg(Ci) + avg(Cj) ）与它们簇间距离 dist( center(Ci), center(Cj) ) 的比值的最大值。这个指数越小，代表聚类结果的簇间距离越大，而簇内距离越小。
在理解了距离度量是聚类算法中对相似度的近似之后，我们下一节好好介绍以下距离计算的概念、性质以及具体形式
二、 聚类介绍
聚类划分：
（1）划分聚类 k-means、k-medoids、k-modes、k-medians、kernel k-means
（2）层次聚类 Agglomerative 、divisive、BIRCH、ROCK、Chameleon
（3）密度聚类 DBSCAN、OPTICS
（4）网格聚类 STING
（5）模型聚类 GMM
（6）图聚类 Spectral Clustering（谱聚类）
关于具体的聚类算法介绍可以看这个帖子：用于数据挖掘的聚类算法有哪些，各有何优势？ - 郭小贤的回答 - 知乎 https://www.zhihu.com/question/34554321/answer/64372216。
1、原型聚类：
算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、求解方式，将产生不同的算法
1.1 k均值（k-means）算法
“k均值”算法的选定参数 k 将数据集划分为 k 个簇，并通过迭代更新使得簇划分最小化平方误差。
算法步骤如下：
-> 首先，初始化 k 个簇，随机选择 k 个样本作为 k 个簇的初始均值向量
-> 然后，不断迭代以下几步步骤
>> 对每个样本 x ，计算其与每个簇均值向量的距离 d，
>> 选择最近的簇 i 作为 x 的簇标记，并将 x 放入该簇集合 Ci 中
>> 对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量
>> 当均值向量均未更新时，退出迭代步骤
-> 最终，我们获得了聚类计算的结果簇划分
需注意，k是靠人工选择的结果，大家可以通过对不同的 k 值进行试验，或通过对数据集的理解来找到最合适的 k 的取值。
1.2 学习向量量化（Learning Vector Quantization，简称LVQ）
与k均值算法类似，LVQ也是试图找到一组原型向量（k均值算法中的簇均值向量集合就是一组原型向量）来刻画聚类结构，但与一般聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类
-> 首先，初始化 p 个原型向量（数据集中有几个类别，p就为几），随机从每个类别中选择一个数据样本作为该类别的初始原型向量
-> 然后，不断迭代以下几个步骤
>> 从样本集中随机选取样本 x，并计算它与每个原型向量的距离，
并找出最近距离 d 所对应的原型向量 pi
>> 如果 pi 的类标记等于 x 的类标记，则原型向量 pi 向 x 方向按
学习率移动
>> 如果 pi 的类标记不等于 x 的类标记，则原型向量 pi 向 x 反方
向按学习率移动
>> 当原型向量满足条件时（如达到迭代次数、原型向量更新很小）
退出迭代
-> 最终，我们获得了聚类计算的结果原型向量
1.3 高斯混合聚类
与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合聚类采用概率模型来表达聚类原型。相对于k均值聚类算法使用 k 个原型向量来表达聚类结构，高斯混合聚类使用 k 个高斯概率密度函数混合来表达聚类结构
于是迭代更新 k 个簇原型向量的工作转换为了迭代更新 k 个高斯概率密度函数的任务。每个高斯概率密度函数代表一个簇，当一个新的样本进来时，我们可以通过这 k 的函数的值来为新样本分类
高斯混合聚类的算法步骤如下：
-> 首先，初始化高斯混合分布的模型参数
-> 然后，不断迭代以下几个步骤
>> 对数据集中的每一个样本 x，计算其在每一个混合成份上的后验概率
>> 根据算好的后验概率，更新高斯混合分布每一个混合成份上的参数
>> 当满足停止条件，如达到迭代次数、似然函数更新很小时退出迭代
-> 接着，根据最后的混合成份，我们将数据集划分到不同的簇中
-> 最终，我们获得簇划分以及高斯混合分布函数模型
2 密度聚类
密度聚类假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种著名的密度聚类算法，它基于一组“邻域”参数来刻画样本分布的紧密程度。DBSCAN算法的中心思想是将满足一定可达关系能导出的最大密度相连样本定义为一个簇，其通过两个基本参数 e 和 MinPts 来定义这个可达关系。要理解 DBSCAN 算法，我们先了解下边这些概念：
［1］“e - 邻域”：e为邻域半径，任意一个样本 xj 的 “e - 邻域” 包含样本集 D 中与样本 xj 的距离不大于 e 的样本集合；
［2］核心对象：当一个样本 x 的 “e - 邻域”内含有至少 MinPts 个样本时，该样本 x 是一个核心对象；
［3］密度直达：若 xj 位于 xi 的 “e - 邻域”中，且 xi 是核心对象，则称 xj 与 xi 密度直达
［4］密度可达：若 xi 与 xj 能通过一系列密度直达的点关联起来，则 xi 与 xj 密度可达
［5］密度相连：若 xi 与 xj 都能通过 xk 密度可达，则称 xi 与 xj 密度相连
DBSCAN算法的步骤如下：
-> 首先，初始化核心对象集合为空
-> 然后，对每个样本计算其邻域空间集合，并根据邻域所含结点判断是否为
核心对象，如果是则加入核心对象集合
-> 接着，当核心对象集合不为空时，不断重复迭代以下几个步骤
>> 随机从核心对象集合中抽取出一个核心对象
>> 根据这个核心对象找出其密度相连的所有样本集合
>> 将这些样本集合设定为一个簇
>> 将该簇集合中出现的核心对象从核心对象集合中移除
-> 最终，我们获得聚类计算的结果簇划分
需注意的是，在完成计算之后，可能会存在一些数据是不属于任何簇的，这些样本被认为是噪声或异常样本。在个别应用场景下，这部分样本将具有较高的价值，比如在反欺诈场景下，这部分不合群的样本数据是欺诈行为数据的概率较高。
3 层次聚类（Hierarchical clustering）
层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。
AGNES（AGglomerative NESting）是一种采用自底向上聚合策略的层次聚类算法，它的算法十分简单，那就是先将每个样本看作一个初始聚类簇，然后在算法运行的每一步找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数。
这个算法十分简单，其中的关键是如何计算两个聚类簇之间的距离。根据以下不同的距离定义，我们将得到不同分类结果：
［1］最小距离：两个聚类簇样本之间的最小距离，使用该距离定义的算法被称为“单链接”算法
［2］最大距离：两个聚类簇样本之间的最大距离，使用该距离定义的算法被称为“全链接”算法
［3］平均距离：两个聚类簇样本之间的距离之和的平均，使用该距离定义的算法被称为“均链接”算法