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

Question

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

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

有人可以指导我吗？

Answer 1

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

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