我正在尝试对数据进行聚类以提高蛮力 kNN 的效率。数据集由大量二进制特征描述的对象组成，每个特征都由 32 位哈希码标识。数据点可以理解为一个2^32元素长的非常稀疏的二进制向量，在特征的哈希码表示的位置上位设置为 1。为简化起见，每个数据点都表示为一个哈希数组——如果我们知道哪些位设置为 1，我们就知道其中哪些位设置为 0。
我有一个工作距离函数（在此处提到），但很难在合理的时间内对数据集进行聚类。由于数据的二进制性质，不可能基于数据点的集合创建任何类型的平均值，因此 k-Centroids 不是一种选择。我尝试了 k-Clustroids，但它没有收敛，分层方法效率太低。您是否碰巧知道任何可以有效处理固定大小数据集的聚类算法，使用自定义度量计算方法而无需创建任何临时的质心数据点？
非常感谢。
您可以在稀疏数据上有效地实现例如欧几里得距离或余弦（仅迭代非零值！）。然后你可以使用例如层次聚类。
但也要考虑频繁项集挖掘。通常，在稀疏二进制数据上，频繁项集优于聚类。
我是一名神经科学家，我遇到了我认为类似的问题。只是提供一点背景知识：大脑分为约 200k 体素。使用称为 DTI 的技术，寻找纤维。纤维要么通过某个体素 (1)，要么不通过 (0)。因此，给定一个体素，与大脑其他部分的连接模式是一个 200k 的向量；它的组成部分大多是 0，有时是 1。
a）要么计算数据集的所有向量之间的互相关矩阵，要么计算距离矩阵；在这两种情况下，你都会得到一个方阵。选择哪个距离：我建议使用 Jaccard 距离，非常适合二进制、稀疏的特征向量。
b1) 使用光谱重新排序算法，如http://www.pnas.org/content/suppl/2004/08/20/0403743101.DC1/03743SuppText.pdf中所述（也阅读论文，非常棒）分离您的数据到集群中（每个正方形将是一个），或者至少了解集群的数量。可选地，
b2）应用k-means对您选择的矩阵的行（或列；没关系，是上述cc/距离矩阵对称）进行聚类。
HTH，亲切的问候，卢卡