在线k-means聚类

Question

是否有k-Means聚类算法的在线版本？

在线我的意思是每个数据点都是串行处理的,一旦进入系统就会一次处理,从而节省了实时使用时的计算时间.

我写了一篇自我并取得了不错的成绩,但我真的更喜欢有一些"标准化"的东西来引用,因为它将在我的硕士论文中使用.

此外,有没有人有其他在线群集算法的建议？(lmgtfy失败;))

Answer 1

就在这里.谷歌未能找到它,因为它通常被称为"顺序k-means".

你可以在Richard Duda 的一些Princeton CS课堂笔记的这一部分找到两个连续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的经典文本模式分类和场景分析或更新版的模式分类.如果它不在那里,你可以试试Chris Bishop的最新书或Daphne Koller和Nir Friedman最近的文章.