【公式】聚类-细说各种类别距离

在聚类算法中，一般都要计算类别之间的距离，而不同的距离计算又会影响聚类算法的效果，所以这里整理了各种类别之间的距离计算方法，例如：NPA、FPA、UPGMA、UPGMC、WPGMC、WPGMA、ward等等，方便大家使用时参考与理解。

一、 聚类算法中的各种距离

在聚类算法中，往往要计算类别之间的距离。样本与样本之间，已经有欧氏距离之类的距离了，但是类别与类别之间，每个类别包含多个样本，那这时候距离应该怎么计算呢？

一般来说，类别与类别的距离，有NPA、FPA、UPGMA、UPGMC、WPGMC、WPGMA、ward等等计算方法，下面我们就一个一个的来介绍它们。

1.1. NPA(single)

NPA(Nearest Point Algorithm) ，也就是：最近邻算法，它的计算方法如下：

 ,其中
 解释：u的样本与v的样本两两计算距离 ，取最小距离

1.2. FPA(complete)

FPA(Farthest Point Algorithm) ，也就是最远邻算法，它的计算方法如下：

 ,其中 
解释：u的样本与v的样本两两计算距离 ，取最大距离

1.3. UPGMA(average)

UPGMA(Unweighted Pair-Group Methodusing the Average approach)，也就是等权均值法，如下：

  ,其中 
解释：u的样本与v的样本两两计算距离 ，取平均距离

1.4. UPGMC(centroid)

UPGMC(Unweighted Paire-Group Method using Centroid approach)，也就是等权质心法，如下：

                        
解释：类别u的质心(样本均值)与类别v的质心的距离

1.5. WPGMC(median)

WPGMC(Weighted Pair-Group Method using Centroid approach)，也就是加权质心法，如下：

距离的计算与centroid相同,只是将u,v合并时，新类别的位置为u,v质心均值

1.6. WPGMA(weighted)

WPGMA(Weighted Pair Group Method with Arithmetic mean)，也就是加权均值法，如下：

 u是刚由s、t两个类别组成的新类别，则u与v的距离计算如下：
        
解释：两个旧类别s,t与v的距离的平均值          

1.7. ward ：ward方差法

ward方差中的距离d指的是：如果u类别与v类别合并时，类内方差SSE的增加量，即： 
类内方差SSE是指该类的样本与该类中心的方差之和。
 如果每次按上述定义计算，计算量会较大，所以一般使用如下迭代公式：

其中，u由s、t两个类别合并而成，代表的样本个数，。

好了，以上就是较常用的类别与类别之间的距离计算方法了，使用不同的距离计算方法，聚类算法的最终的效果就不一样，根据实际情况来选择距离计算方法。

总结

总的来说，有类别的距离计算方法有NPA、FPA、UPGMA、UPGMC、WPGMC、WPGMA、ward等等，它们大多都是基于单样本的距离来进一步得到类别之间的距离，好了，多的也不说了，毕竟理解了它们的意义，然后再按公式去计算就行了。