python - 根据距离和出现频率选择一个项目(从一组项目中)

Question

存在一组点(或项目，无关紧要)。每点a与集合中的其他点有特定距离。可以通过函数 retrieve_dist(a, b) 检索距离。 .

这个问题是关于(在 Python 中)编程一种算法，从这组点中选择一个点，并进行替换。选取点:

i) 必须与所有已选择的点保持最大可能的距离，同时遵守 (ii) 中的要求

ii) 样本中已选点出现的次数在此计算中必须具有权重。 IE。应该对更频繁选择的点进行更重的权衡。

例如想象a和 b已经被选中(分别为 100 次和 10 次)。然后当要选择下一个点时，它与a的距离比它与 b 的距离更重要, 符合 a 的出现频率在已经选择的样本中。

---

我可以尝试什么:

如果不考虑权重/频率，这将很容易实现。我可以这样做:

distances = defaultdict(int)
for new_point in set_of_points:
    for already_selected_point in selected_points:
        distances[new_point] += retrieve_dist(new_point, already_selected_point)

然后我会排序 distances.items()通过每个元组中的第二个条目，并获得所需的项目进行选择。

但是，当已经选择的点的频率开始起作用时，我似乎无法解决这个问题。

有专家帮忙吗？提前致谢。

Answer 1

您的问题的解决方案是将 selected_points 设为 list 而不是 set。在这种情况下，每个新点都会与 a 和 b(以及所有其他点)进行比较，次数与它们已经找到的次数一样多。

如果每个点通常被多次找到，则可以使用 dict 来提高性能，键是点，值是每个点被选择的次数.在那种情况下，我认为您的算法将是

distances = defaultdict(int)

for new_point in set_of_points:
    for already_selected_point, occurances in selected_points.items():
        distances[new_point] += occurances * retrieve_dist(new_point, already_selected_point)