cluster-analysis - 在线 k-means 聚类

Question

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

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

我自己写了一篇效果很好的文章，但我真的更希望有一些“标准化”的东西可以参考，因为它会在我的硕士论文中使用。

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

Answer 1

就在这里。谷歌没能找到它，因为它通常被称为“序列 k-means”。

您可以在Richard Duda的一些普林斯顿 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 的经典文本Pattern Classification and Scene Analysis或较新的版本Pattern Classification。如果它不存在，您可以尝试 Chris Bishop 的最新著作或 Daphne Koller 和 Nir ​​Friedman 最近的文本。