一种更快的Kmeans原理与实现

发布时间:2024年01月20日

普通的k-means实现大多需要多轮迭代,一轮需要O(n * k)的复杂度,其中n是数据量,k是聚类的数量。观察到大部分地方的标准均值中的大多数距离计算都是冗余的。 所以Elkan-Kmeans通过三角不等式来优化这一过程,减少无效计算。

困难在于三角不等式给出了上界,但我们需要下界以避免计算。设p是一个点,c1和c2是中心,我们需要知道d(p,c1) ≤ d(p,c2)才能避免计算实际的d(p,c2)值。

第一种规律是对于一个样本点x和两个质心μj1,μj2。如果我们预先计算出了这两个质心之间的距离D(j1,j2),则如果计算发现2D(x,j1)≤D(j1,j2),就可以知道D(x,j1)≤D(x,j2)。此时我们不需要再计算D(x,j2)。
第二种规律是对于一个样本点x和两个质心μj1,μj2。我们可以得到
D(x,j2)≥max{0,D(x,j1)?D(j1,j2)}。

我们不维护每一对点的距离的上界,只维护一个数据点到它的锚定点的距离的上界u(x)。一开始数据点到锚定点的距离是确定的,上界也确定,若该点的锚定点发生了位移,根据定理1则 u(x)+=dis(m(c(x)),c(x))m(c)表示c位移后的位置(代码中为mean),c(x)表示x数据点点锚定的中点。同时当我们计算x到它锚定点的距离的时候,我们顺手更新一下这个上界为x到它当前的锚定点的距离,让它不会一直增大以至于算法后期失去约束能力。同时,我们可以记录一下这个点它的上界是否仍然是c到x的距离,如果是的话,我们又能省去一次计算距离。

我们维护每一个数据点x到中点c的距离的下界l(x,c),一开始赋值为距离,迭代的时候,根据定理2,

伪代码

1.先预处理dist c c'

2.然后根据 第一个规则优化出待选点

3.然后在当前可能中心点中,选择可能的中心点(u(x)上界,大于可能的收益,也就是l(x, c))或者根据规律1

a.然后r(x)来标记是否进行计算(是否u(x) 过期,同时减少u(x)膨胀失效)

如果不计算的话,直接用u(x)来代替计算距离(update l, u)

b.然后根据原来的距离是不是大于l(x,c) ,是否根据第一个规则是否有优化的可能。

如果有的话,进行计算((update l, u&#x

文章来源:https://blog.csdn.net/m0_63691156/article/details/135706180
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。