如何在 10,000 个点的池中找到 100 个最不同的点？
How do I find the 100 most different points within a pool of 10,000 points?
我有一组 10,000 个点，每个点由 70 个布尔维度组成。从这组10000中，我想select100个点代表整组10000。换句话说，我想挑出100个最不一样的点。
是否有一些既定的方法可以做到这一点？我首先想到的是贪心算法，开始时随机 selecting 一个点，然后下一个点 selected 作为离第一个点最远的点，然后第二点被 select 编辑为与前两个点的平均距离最长，依此类推。此解决方案不需要完美，只需大致正确即可。最好这个100分的解也能在~10分钟内找到，但24小时内完成也可以。
我不在乎距离，特别是，这只是我想到的一种捕捉“差异”的方式。
如果重要的话，每个点都有 10 个 TRUE 值和 60 个 FALSE 值。
一些已经构建的 Python 包来执行此操作将是理想的，但我也很乐意自己编写代码，如果有人可以将我指向维基百科文章。
谢谢
您对“代表性”的使用不是标准术语，但我阅读您的问题是因为您希望从您的数据集中找到涵盖广泛 范围 的不同示例的 100 个项目。因此，如果您的 10000 件商品中有 5000 件几乎相同，您宁愿只看到那么大的一件或两件商品 sub-group。根据通常的定义，一个 100 人的代表性样本将包含来自该组的 ~50 项。
可能符合您既定目标的一种方法是识别数据中的不同子集或组，然后从每个组中选择一个示例。
您可以使用聚类算法在数据集中为固定数量的组建立组身份 - 每个组允许不同的成员大小。对您来说，一个不错的选择可能是 k-means clustering，其中 k=100。这将在您的数据中找到 100 个组，并根据简单的距离度量将所有 10,000 个项目分配给这 100 个组中的一个。然后，您可以从每组中取中心点或从每组中随机抽取样本来找到您的 100 组。
k-means 算法基于最小化成本函数，该函数是每个组成员与其组中心的平均距离。组中心和成员资格都可以更改，以交替方式更新，直到无法进一步降低成本。
通常，您首先将每个项目随机分配到一个组中。然后计算每组的中心。然后 re-assign 项根据最近的中心进行分组。然后重新计算中心等。最终这应该收敛。可能需要多次运行才能找到一组好的最佳中心（它可能会陷入局部最优）。
在 Python 中有几种此算法的实现。您可以从 scikit learn library implementation.
开始
根据an IBM support page (from comment by sascha), k-means may not work well with binary data. Other clustering algorithms may work better. You could also try to convert your records to a space where Euclidean distance is more useful and continue to use k-means clustering. An algorithm that may do that for you is principle component analysis (PCA) which is also implemented in scikit learn。
图分割工具METIS声称能够在几秒内将具有数百万个顶点的图分割成256个部分。
您可以将 10.000 个点视为无向图的顶点。具有 5000 万条边的完全连接图可能太大了。因此，您可以将边缘限制为 Hamming distance 低于特定阈值的点之间的“相似性链接”。
一般来说，70 位字的汉明距离值介于 0 和 70 之间。在您的情况下，上限为 20，因为每个点有 10 个真坐标和 60 个假坐标。如果两个点的所有真实坐标都位于不同的位置，则会出现最大距离。
图表的创建是 O(n^2) 的昂贵操作。但在您设想的时间范围内完成它也许是可能的。
我有一组 10,000 个点，每个点由 70 个布尔维度组成。从这组10000中，我想select100个点代表整组10000。换句话说，我想挑出100个最不一样的点。
是否有一些既定的方法可以做到这一点？我首先想到的是贪心算法，开始时随机 selecting 一个点，然后下一个点 selected 作为离第一个点最远的点，然后第二点被 select 编辑为与前两个点的平均距离最长，依此类推。此解决方案不需要完美，只需大致正确即可。最好这个100分的解也能在~10分钟内找到，但24小时内完成也可以。
我不在乎距离，特别是，这只是我想到的一种捕捉“差异”的方式。
如果重要的话，每个点都有 10 个 TRUE 值和 60 个 FALSE 值。
一些已经构建的 Python 包来执行此操作将是理想的，但我也很乐意自己编写代码，如果有人可以将我指向维基百科文章。
谢谢
您对“代表性”的使用不是标准术语，但我阅读您的问题是因为您希望从您的数据集中找到涵盖广泛 范围 的不同示例的 100 个项目。因此，如果您的 10000 件商品中有 5000 件几乎相同，您宁愿只看到那么大的一件或两件商品 sub-group。根据通常的定义，一个 100 人的代表性样本将包含来自该组的 ~50 项。
可能符合您既定目标的一种方法是识别数据中的不同子集或组，然后从每个组中选择一个示例。
您可以使用聚类算法在数据集中为固定数量的组建立组身份 - 每个组允许不同的成员大小。对您来说，一个不错的选择可能是 k-means clustering，其中 k=100。这将在您的数据中找到 100 个组，并根据简单的距离度量将所有 10,000 个项目分配给这 100 个组中的一个。然后，您可以从每组中取中心点或从每组中随机抽取样本来找到您的 100 组。
k-means 算法基于最小化成本函数，该函数是每个组成员与其组中心的平均距离。组中心和成员资格都可以更改，以交替方式更新，直到无法进一步降低成本。
通常，您首先将每个项目随机分配到一个组中。然后计算每组的中心。然后 re-assign 项根据最近的中心进行分组。然后重新计算中心等。最终这应该收敛。可能需要多次运行才能找到一组好的最佳中心（它可能会陷入局部最优）。
在 Python 中有几种此算法的实现。您可以从 scikit learn library implementation.
开始根据an IBM support page (from comment by sascha), k-means may not work well with binary data. Other clustering algorithms may work better. You could also try to convert your records to a space where Euclidean distance is more useful and continue to use k-means clustering. An algorithm that may do that for you is principle component analysis (PCA) which is also implemented in scikit learn。
图分割工具METIS声称能够在几秒内将具有数百万个顶点的图分割成256个部分。
您可以将 10.000 个点视为无向图的顶点。具有 5000 万条边的完全连接图可能太大了。因此，您可以将边缘限制为 Hamming distance 低于特定阈值的点之间的“相似性链接”。
一般来说，70 位字的汉明距离值介于 0 和 70 之间。在您的情况下，上限为 20，因为每个点有 10 个真坐标和 60 个假坐标。如果两个点的所有真实坐标都位于不同的位置，则会出现最大距离。
图表的创建是 O(n^2) 的昂贵操作。但在您设想的时间范围内完成它也许是可能的。