从大量项目(比如 500 万个)中选择一小部分项目(比如 50 个)同时最小化目标函数的好方法是什么?

计算科学 优化
2021-12-21 01:30:19

我有 500 万个项目,每个项目有 10 个特征(都是连续的,不是分类的),我想选择这些项目的一小部分。理想情况下,我想预先手动指定我自己的 10 个特性,并在池中找到一个与我指定的特性都很接近的项目子集。最接近的意思是我指定的数字与从池中选择的项目特征之间的距离。

2个回答

简单的方法:

计算每个项目与目标特征规范之间的欧几里得距离。按距离排序。取前 50 个元素。

任意目标特征的快速方法:

由于您的参数是连续的,您可以使用网格间距定义 10 维特征空间的网格化di,i=1,,10. 通过划分特征值找到每个项目的网格坐标xi由每个di并对结果发表意见。将具有相同网格坐标的项目合并在一起。接下来,对于您描述的每个目标特征,您可以以相同的方式快速计算其网格坐标,并从该单元格或其邻居中选择项目以快速找到您正在寻找的子集,而无需计算全部 500 万每次要指定要素时的(或许多)距离。

使用Kd 树Python scipy 有一个快速的实现,见它的 文档
Fwiw,我的 2.7 GHz iMac 上的运行时间:
~ 23 秒在 10d 内构建具有 5M 随机点的树,柯西分布
~ 500 毫秒查询 50 个点,每个点 5 个最近邻。

顺便查询的两倍快,250 毫秒2