在 C++ 中执行 k 意味着在二进制向量上进行聚类的快速方法

Question

我想将二进制向量（数百万个）聚类成 k 个簇。我使用汉明距离来查找初始簇的最近邻居（这也很慢）。我认为 K 均值聚类并不适合这里。问题在于计算某个初始聚类中心的最近邻（二元向量）的平均值，以更新质心。

第二种选择是使用 K-medoids，其中新的聚类中心是从最近邻居之一（最接近特定聚类中心的所有邻居的中心）中选择的。但发现这是另一个问题，因为最近邻居的数量也相当大。

有人可以指导我吗？

Answer 1

可以通过二元特征向量的聚类来进行 k 均值。我与人合着的名为TopSig 的论文有详细信息。通过采用每个维度中最常出现的位来计算质心。TopSig 论文将其应用于文档聚类，其中我们通过稀疏高维词袋特征向量的随机投影创建了二进制特征向量。http://ktree.sf.net上有一个 java 实现。我们目前正在开发 C++ 版本，但它是非常早期的代码，仍然很混乱，并且可能包含错误，但您可以在http://github.com/cmdevries/LMW-tree找到它。如果您有任何疑问，请随时通过 chris@de-vries.id.au 与我联系。

如果您想要对大量二元向量进行聚类，还有更可扩展的基于树的 K 树、TSVQ 和 EM 树聚类算法。有关这些算法的更多详细信息，您可以参阅我最近提交的同行评审论文，该论文尚未发表，与EM-tree相关。