运用三角不等式加速Kmeans聚类算法
引言：最近在刷《数据挖掘导论》，第九章, 9.5.1小节有提到，可以用三角不等式，减少不必要的距离计算，从而达到加速聚类算法的目的。这在超大数据量的情况下，尤为重要。但是书中并没有给出解释和证明。本文以k-means聚类算法为代表，讲解下怎么利用三角不等式减少计算过程。
三角不等式
任一三角形，两边之和大于第三边，两边之差小于第三边。可以从欧式距离扩展到多维欧几里得空间：设任意三个向量a,b,c。d(x,y)代表x,y在空间上的距离,则三角不等式满足：
\[d(a,b)+d(b,c)\ge d(a,c) , d(a,b) - d(b,c) \le d(a,c)\]
K-means算法
K-mean算法
- 随机选择K个数据点作为初始质心
- repeat：
- 计算每一个数据点计算到现有K个质心的距离，将它归属到距离最近质心的所在簇中
- 重新计算质心。
- until 所有质心不再变动
定义
\[假设存在数据点集 X=\{x_1, x_2,..,x_n\} , 质心的集合C=\{ C_1,C_2,...,C_m\}, 对应的簇集合为S=\{ S_1,S_2,...,S_m\}。\]
三角不等式推出的引理
引理1：
\[设 C_i ,C_j(i\neq j )\in C, x \in X。如果2 d(x,C_i) \le d(C_i,C_j) ,那么d(C_i,x) \le d(C_j,x) 。
\]
引理2：
\[ 设C_i \in C, \exists C_j \in C,使得d(C_i,C_j) = min \ d(C_i,C)。对于数据点x \in X,若有2 d(x,C_i) \le d(C_i,C_j)，\
那么min \ d(x,C) = d(C_i,x)。（记d(x,C)是x到所有质心的距离）\]
证明引理1：
因为有 \[2 d(C_i,x) \le d(C_i,C_j) \ (1)\]
且由三角不等式：\[ d(C_i,C_j) \le d(x,C_i) + d(x,C_j) \ (2)\]
所以 \[2 d(C_i,x) \le d(x,C_i) + d(x,C_j)，即d(C_i,x) \le d(C_j,x)\]
证明引理2：
运用反证法：
假设 \[ \exists C_k \in C,使得d(C_k,x) < d(C_i,x), \]
由题干有:
\[ d(C_k,C_i) \ge d(C_i,C_j) (1) , d(x,C_i) \le d(C_i,C_j) (2)\]
又因为 \[ d(C_k,x) +d (C_i,x) \ge d(C_k,C_i) (3)\]
所以结合(1)(3)：
\[ d(C_k,x) +d (C_i,x) \ge d(C_i,C_j) (4)\]
又由假设:
\[ 2d(C_i,x) > d(C_i,C_j) （5）\]
这与条件中\[2 d(x,C_i) \le d(C_i,C_j)\]相矛盾，所以可知假设不成立。
即 \[min \ d(x,C) = d(C_i,x)\]
运用引理1，引理2减少不必要的距离计算
\[对于每一个C_i,用一个hash表存放与它最近的距离 d(C_i,C_j)。\]
1.如果数据点x已经被分配
\[ 则x与它目前所在簇的质心的距离为d(C_i,x)，与d(C_i,C_j)比较。 \\
如果 2 d(C_i,x) \le d(C_i,C_j),则说明不需要更换x的归属。（注意反之： 2 d(C_i,x) \gt d(C_i,C_j)），并不能说明x应该数据 C_j所在的簇，所以还需要继续计算x与每个质心的距离。）\]
2.如果数据点x还未被分配
\[ 则需要遍历计算, \forall C_i \in C, 比较 2 d(C_i ,x) \le d(C_i,C_j)是否成立，若成立，说明x应当归属 C_i ,无需再计算其他距离。\]
改进的K-means算法
K-mean算法
- 随机选择K个数据点作为初始质心
- repeat
- 计算k个质心间的距离，并且用hash表保存每个质心的到其他质心的最短距离。（用d(Ci,Cj)表示质心Ci和它最近质心是Cj的距离）。
4. repeat
对于每个数据点x
if(数据点x已分配在质心Ci所在簇)
if 2d(Ci,x) <=d(Ci,Cj)
x分配无需变动;
else
继续计算x到现有K个质心的距离，将它归属到距离最近质心的所在簇中
end if
else(数据点x未分配到任何簇)
for i from 0 to K do
if 2d(Ci,x) <=d(Ci,Cj)
将x归属到Ci所在簇中
退出for循环
end if
end for
end if - 重新计算质心。
- until 所有质心不再变动
引申
本文中只举例了使用欧几里得距离的K-means算法。其实本文中的d(x,y)不仅可以指代distance，更广义的可以指代dissimilarity。任何通过度量相异性的聚类算法都可以使用三角不等式，避免多余的计算，例如计算最近邻的DBSCAN。感兴趣的读者可以自己推导改进。