我想将二进制向量（数百万个）聚集成 k 个簇。我正在使用汉明距离来寻找与初始簇最近的邻居（这也很慢）。我认为 K-means 聚类并不适合这里。问题在于计算一些初始聚类中心的最近邻居（它们是二进制向量）的平均值，以更新质心。
第二种选择是使用 K-medoids，其中新的聚类中心是从最近的邻居之一（与特定聚类中心的所有邻居最近的邻居）中选择的。但发现这是另一个问题，因为最近邻居的数量也很大。
有人可以指导我吗？
问问题
1929 次
2 回答
5
可以使用二进制特征向量进行聚类来进行 k-means。我与人合着的名为TopSig的论文有详细信息。通过取每个维度中出现频率最高的位来计算质心。TopSig 论文将此应用于文档聚类，其中我们有通过稀疏高维词袋特征向量的随机投影创建的二进制特征向量。在http://ktree.sf.net有一个 java 实现。我们目前正在开发 C++ 版本，但它是非常早期的代码，仍然很混乱，并且可能包含错误，但您可以在http://github.com/cmdevries/LMW-tree找到它。如果您有任何问题，请随时通过 chris@de-vries.id.au 与我联系。
如果您想要对大量二元向量进行聚类，还有更多基于树的可扩展 K-tree、TSVQ 和 EM-tree 聚类算法。有关这些算法的更多详细信息，您可以查看我最近提交的一篇尚未发表的与EM-tree相关的论文以供同行评审。
于 2013-09-23T09:16:10.870 回答
2
实际上，k-means 在这里不太合适，因为该方法在二进制数据上是不合理的。
为什么你需要确切的k集群？这可能意味着某些向量不能很好地适应它们的集群。
您可以研究一些用于聚类的东西：minhash，局部敏感散列。
于 2013-06-11T06:08:38.793 回答