在线k-means聚类

Question

有没有k-Means clustering算法的在线版本？

所谓在线，我的意思是每个数据点都是串行处理的，当它们进入系统时，一次一个，因此在实时使用时节省了计算时间。

我自己写了一个，结果很好，但我真的更喜欢有一些“标准化”的东西来参考，因为它将在我的硕士论文中使用。

另外，有没有人对其他在线聚类算法有建议？(lmgtfy失败；)

Answer 1

是的有。谷歌未能找到它，因为它更为人所知的是“序列k-means”。

您可以在Richard Duda的this section of some Princeton CS class notes中找到两个序列K-means的伪代码实现。我已经复制了下面两个实现中的一个：

Make initial guesses for the means m1, m2, ..., mk
Set the counts n1, n2, ..., nk to zero
Until interrupted
    Acquire the next example, x
    If mi is closest to x
        Increment ni
        Replace mi by mi + (1/ni)*( x - mi)
    end_if
end_until

它的美妙之处在于，您只需要记住每个聚类的平均值和分配给该聚类的数据点的数量。一旦更新了这两个变量，就可以丢弃数据点。

我不确定你在哪里能找到它的引用。我会开始在Duda的经典文本Pattern Classification and Scene Analysis或更新版本的Pattern Classification中查找。如果没有，你可以试试克里斯·毕晓普的新书或者达芙妮·科勒和尼尔·弗里德曼的新书。