时间戳

首页 > 解决方案 > 如何有效地选择降低与已知点的平均距离的点？

python - 如何有效地选择降低与已知点的平均距离的点？

问题描述

因此，您在空间中有一组“已探索”点，以及一组“未探索”点。您想选择 K 个未探索点进行探索，以使从未探索点到其最近探索点的平均距离最小化。

问题示意图

这是否比通过蛮力一一挑选未探索的点并测量平均距离更有效？

我有下面的python函数来完成工作。但这对于大型集合是不可行的，因为它变得非常慢。我想将其用于一组至少数十万个未探索点。所以它需要更有效。我不需要最佳解决方案，一个好的近似值就可以了！

如果没有嵌套的 for 循环，这能以某种方式完成吗？

还是只能选择最有可能的点进行评估？

所有的想法都将受到高度赞赏！

import numpy as np

explored = np.random.rand(100,3)
unexplored = np.random.rand(100000,3)

def k_anchors(explored, unexplored, K):

    anchors = np.empty((K, unexplored.shape[1]))

    for j in range(K):
        proximity_sum = np.zeros((len(unexplored),))

        for k in range(len(unexplored)):
            temp_results = np.concatenate(( explored, unexplored[k].reshape((-1,3)) ))
            proximity = np.zeros((len( unexplored ),))

            for i in range(len( unexplored )):
                i_prox = (abs((unexplored[i,:] - temp_results))).sum(axis=1)
                proximity[i] = i_prox.min()

            proximity_sum[k] = proximity.sum()

        idx = np.argmin( proximity_sum )
        anchors[j,:] = unexplored[ idx ]
        unexplored = np.delete(unexplored, idx, 0)
        explored = np.concatenate(( explored, unexplored[ idx ] ))

    return anchors

print( k_anchors(explored, unexplored, 5) )

解决方案

这个问题通过 Barış Can Tayiz 提出的 K 均值算法的变体得到了解决，它就像一个魅力。

简而言之，我将探索点初始化为质心，以及 K 个随机点。然后在拟合数据时仅改变 K 个随机点。对我来说，数字 K 不需要优化，因为我现在每次调用函数时我将能够探索多少点。

感谢所有抽出宝贵时间讨论和回答这个问题的人！

标签： pythonalgorithmnumpymathematical-optimizationgraph-algorithm

解决方案

您可以为此目的使用无监督学习算法。例如，如果您为 k 均值选择 k = 3，则必须探索离中心最近的点。选择 k 是另一个问题。您可以查看这篇文章https://medium.com/analytics-vidhya/how-to-determine-the-optimal-k-for-k-means-708505d204eb。您可以将 n+1th - nth / nth - n-1th 的差用于平方误差 (WSS) 的聚类内和。该比率将在测量 WSS 时给出最佳 k。

推荐阅读