最近在探索单细胞 rare cell 鉴定相关软件，接触到很多聚类方面的知识，故参考其他学习笔记进行整合整理，原始内容详见参考链接。
常用聚类算法
通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解。
- K-means 算法
- 学习向量量化（Learning Vector Quantization，简称 LVQ）
- 高斯混合聚类
- 密度聚类
- 层次聚类（Hierarchical clustering）
密度聚类可能会有样本不属于任何一个簇，这部分数据可被认为是噪声或异常数据。
原型聚类和层次聚类的簇数量是由使用者自己设定的，而密度聚类则是由算法自己学习得来。
聚类的度量指标
好的聚类算法,一般要求类簇具有：
- 高的类内 (intra-cluster) 相似度 (documents within a cluster are similar)
- 低的类间 (inter-cluster) 相似度 (documents from different clusters are dissimilar)
聚类算法的度量标准存在三种：External(外部评价指标),Internal(内部评价指标),Relative()。
外部评价指标
原理：给定一个基准, 根据这个基准对聚类结果进行评价。
常见的指标有：Jaccard 系数，FM 指数，Rand 指数。
内部评价指标
原理：直接考察聚类结果而不利用任何参考模型。中心思想是：簇内的样本距离近似于簇内相似度，簇间样本距离近似于簇间相似度，通过计算并组合这些样本/簇距离的值来构建一个符合需要的性能度量指标。常用的性能指标有：DB 指数、Dunn 指数。
距离度量是聚类算法中对相似度的近似.
距离计算
“距离度量”(distance measure)基本特性：
- 非负性：两点之间距离不为负;
- 同一性：两个点只有在样本空间上重合才可能距离为零；
- 对称性：a 到 b 的距离等于 b 到 a 的距离;
- 直递性：a 到 c 的距离加上 c 到 b 的距离大于等于 a 直接到 b 的距离;
[1] 连续属性上的距离计算
在连续属性上，给定样本 xi 和 xj，一般通过“闵科夫斯基距离”来计算，它计算样本 xi 和 xj 在每一个属性上的数值差值的 p 次方的和的开 p 次方。当 p = 2 时，“闵科夫斯基距离”即欧式距离。
[2] 离散属性上的距离计算 在离散属性上，因为其在定义域上只有有限个取值，当这些取值是有序的时，如 {1, 2, 3}，同样用“闵科夫斯基距离”来计算，但当取值为无序时，如 {苹果, 香蕉, 桃子}使用 VDM（Value Difference Metric）来计算。VDMp(a, b)代表的是在属性 u 上，取值为 a 和 b 的样本在不同簇上分布比例的差值的 p 次方。它是通过分布比例的不同来对属性上的相似度来进行近似的。
具体评价指标学习
内部指标
- Compactness 紧密型(CP)
计算每一个类中各点到聚类中心的平均距离，不考虑类间效果。 - Separation(间隔性)(SP)
计算各聚类中心两两之间平均距离，不考虑类内效果。 - Davies-Bouldin Index(戴维森堡丁指数)(分类适确性指标)(DB)(DBI)
计算任意两类别的类内距离平均距离(CP)之和除以两聚类中心距离求最大值，DB 越小意味着类内距离越小，同时类间距离越大。因使用欧式距离，所以对于环状分布，聚类评测很差。 - Dunn Validity Index (邓恩指数)(DVI) 计算任意两个簇元素的最短距离(类间)除以任意簇中的最大距离(类内)，DVI 越大意味着类间距离越大 同时类内距离越小，对离散点的聚类测评很高、对环状分布测评效果差.
- Cluster Accuracy (准确性)(CA) 仅仅计算聚类正确的百分比。
外部指标
详解：通过聚类给出的簇划分为 C，参考模型（ground truth）给出的簇划分为 K，通常 K 与 C 给出的簇类别数量不相同。定义 a, b, c, d 如下： a: 在 C 中属于同一类别且在 K 中属于同一类别的样本对数量 b: 在 C 中属于同一类别且在 K 中属于不同类别的样本对数量 c: 在 C 中属于不同类别且在 K 中属于同一类别的样本对数量 d: 在 C 中属于不同类别且在 K 中属于不同类别的样本对数量 m: 总样本数量
- Jaccard 系数
$JC = \frac{a}{a+b+c}$ - FM 指数
$FMI = \sqrt(\frac{a}{a+b} * \frac{a}{a+c})$ - Rand 指数
$RI = \frac{2(a+d)}{m(m-1)}$ - Normalized Mutual Information 归一化互信息 用于度量 2 个聚类结果的相近程度， 上述性能度量的结果值均在 [0,1] 区间，值越大越好。
参考链接
https://zhuanlan.zhihu.com/p/53840697
https://www.jianshu.com/p/499b2f32a662
