正文
聚类算法评价指标
聚类性能度量可以分为两类：
- 一类是将聚类结果与某个“参考模型”进行比较，称为“外部指标”(external index)
- 一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”(internal index)
对于
外部指标
对数据集D = { x 1 , x 2 , . . . , x m }，假定通过聚类算法将样本局为C = { C 1 , C 2 , . . . C k }将参考模型给出的簇划分为C ∗ = { C 1 ∗ , C 2 ∗ , . . . , C S ∗ }
相应的，另λ 与λ ∗分别表示与C 和 C^*对应的簇标记向量。将样本两两配对考虑，有如下定义：
集合S 1表示包含了在C 中属于相同的簇并且在C^*C 中也属于相同的簇的样本；
集合S 2 表示包含了在C中属于相同的簇但在C^* 中不属于相同的簇的样本；
……以此类推……
对每个样本对( x i , x j ) (i<j)仅能出现在一个集合中，因此有
基于以上定义，对无监督聚类算法的聚类结果有如下性能度量指标：
Jaccard系数(accard Coefficient，JCI)
所有属于同一类的样本对，同时在C ,C^∗ 中隶属于同一类的样本对的比例。
FM指数(Fowlkes and Mallows Index，FMI)
在C中属于同一类的样本对中，同时属于C 和C ∗ C^∗C的样本对的比例为p 1 在C^∗ 中属于同一类的样本对中，同时属于C和C^*C
的样本对的比例为p 2 ，FMI就是p 1 和p 2的几何平均。
Rand指数(Rand Index，RI）
很显然，上述性能度量指标的取值都在[ 0 , 1 ] 之间，并且取值越大越好。
内部指标
对于聚类结果C = { C 1 , C 2 , . . . , C k } ，作如下定义：
其中
基于上述定义，得到如下考量聚类性能的内部指标：
DB指数( Davies-Bouldin Index，DBI）
DBI的值越小越好
Dunn指数(Dunn Index，DI)
DI的值越大越好
距离度量
聚类算法的一个重要的度量目标是表示两个样本点之间的相似程度：距离越近，相似程度越高；距离越远，相似程度越低。
常用的距离度量方式：
闵可夫斯基距离；
欧氏距离；
曼哈顿距离；
切比雪夫距离；
余弦距离
其中最重要的是闵可夫斯基距离，闵可夫斯基距离是一类距离的定义。
对于n nn维空间中的两个点x ( x 1 , x 2 , . . . , x n )y ( y 1 , y 2 , . . . , y n ) ，x 、y 两点之间的闵可夫斯基距离表示为：
其中p 是一个可变参数。
当p = 1 时，称为 曼哈顿距离
当p = 2 时，称为 欧式距离
当p = ∞ 时，称为 切比雪夫距离
K-Means算法
对给定的样本集D = { x 1 , x 2 , . . . , x m }k均值算法根据聚类结果划分C = { C 1 , C 2 , . . . , C k }最小化平方误差：
其中
x是类C i 的均值向量。
MSE刻画了簇类样本围绕簇均值向量的紧密程度，越小代表样本距簇均值中心越靠近。
但最优化上式的值是一个NP难的问题，因为要精确地找到它的最优解需要对样本集D DD的所有划分情况进行一一列举。
因此，K-Means算法最终采用的是贪心的策略，通过迭代优化的方式来近似求解最优MES值。
