如何在 10,000 个点中找到 100 个最不同的点？

Question

我有一组 10,000 个点，每个点由 70 个布尔维度组成。我想从这 10,000 个集合中选择 100 个点来代表整个 10,000 个集合。换句话说，我想选出彼此最不同的 100 个点。有一些既定的方法可以做到这一点吗？我首先想到的是贪心算法，它首先随机选择一个点，然后选择下一个点作为距离第一个点最远的点，然后选择第二个点作为具有最长平均值的点与前两个的距离等。这个解决方案不需要完美，只要大致正确即可。最好，这个 100 分的解决方案也可以在大约 10 分钟内找到，但在 24 小时内完成也可以。我并不关心距离，特别是，这只是我想到的捕捉“差异”的一种方式。如果重要的话，每个点都有 10 个 TRUE 值和 60 个 FALSE 值。一些已经构建的 Python 包来执行此操作将是理想的选择，但如果有人可以向我指出维基百科文章，我也很乐意自己编写代码。

Answer 1

您使用的“代表性”不是标准术语，但我读了您的问题，因为您希望找到 100 个项目，涵盖数据集中各种不同的示例。因此，如果 10000 件商品中的 5000 件几乎相同，您可能更愿意只看到该大子组中的一两个商品。根据通常的定义，100 个代表性样本将包含该组中的约 50 个项目。

可能符合您既定目标的一种方法是识别数据中的不同子集或组，然后从每个组中选取一个示例。

您可以使用聚类算法在数据集中为固定数量的组建立组标识（每个组允许不同的成员资格大小）。k=100 的k 均值聚类可能是一个不错的选择。这将在您的数据中找到 100 个组，并根据简单的距离指标将所有 10,000 个项目分配给这 100 个组之一。然后，您可以从每组中选取中心点，也可以从每组中随机抽取样本来找到 100 组。

k 均值算法基于最小化成本函数，该函数是每个组成员与其组中心的平均距离。团体中心和成员资格都可以改变，交替更新，直到成本不能再降低为止。

通常，您首先将每个项目随机分配到一个组中。然后计算每组的中心。然后根据最近的中心将项目重新分配到组中。然后重新计算中心等。最终应该收敛。可能需要多次运行才能找到一组良好的最佳中心（它可能会陷入局部最优）。

该算法在 Python 中有多种实现。您可以从scikit learn 库实现开始。

根据IBM 支持页面（来自sascha的评论），k-means 可能无法很好地处理二进制数据。其他聚类算法可能效果更好。您还可以尝试将记录转换为欧氏距离更有用的空间，并继续使用 k 均值聚类。可以为您做到这一点的算法是主成分分析 (PCA)，它也在 scikit learn 中实现。

Answer 2

图划分工具METIS声称能够在几秒钟内将具有数百万个顶点的图划分为 256 个部分。

您可以将 10.000 个点视为无向图的顶点。具有 5000 万条边的全连接图可能太大了。因此，您可以将边限制为汉明距离低于某个阈值的点之间的“相似性链接”。

一般来说，70 位字的汉明距离值介于 0 和 70 之间。在您的情况下，上限为 20，因为每个点有 10 个真坐标和 60 个假坐标。如果两个点的所有真实坐标都位于不同的位置，则会出现最大距离。

图的创建是一个 O(n^2) 的昂贵操作。但也许可以在您设想的时间内完成它。