jap*_*ata 14 python algorithm euclidean-distance python-3.x
我有一个MxN数组,其中M是观察数量,N是每个向量的维数.从该阵列矢量的,我需要计算mean和minimum欧几里得距离向量之间.
在我看来,这需要我计算M C 2距离,这是一个O(n min(k,nk))算法.我M的约为10,000,我N的约为1,000,这个计算需要约45秒.
是否有更有效的方法来计算mean和min距离？也许是一种概率方法？我不需要它准确,只需要关闭.
您没有描述您的向量来自哪里，也没有描述您将有何mean用途median。以下是对一般情况的一些观察。有限的范围、误差容限和离散值可能允许更有效的方法。
M 点之间的距离mean听起来是二次方的，O(M^2)。但 M / N 为 10，相当小，而 N 很大，因此数据可能类似于 1e3 空间中的毛球体。计算 M 个点的质心，然后计算 M 到质心的距离，可能会在您的问题领域中变得有用，但很难说。
M点之间的距离minimum更有趣。随机选择少量对，例如 100，计算它们的距离，并取最小值的一半作为全局最小距离的估计。（如果需要，可以通过与接下来的几个最小距离进行比较来进行验证。）现在使用空间UB 树将每个点建模为正整数。这涉及找到 M x N 值的 N 个最小值，添加常数，使 min 变为零，缩放，使估计的全局最小距离至少对应于 1.0，然后截断为整数。
有了这些转换后的向量，我们就可以将它们转换为可以排序的 UB 树表示，然后对排序后的值进行最近邻空间查询。对于每个点计算一个整数。将每个维度值的低位移入结果中，然后迭代。继续迭代所有维度，直到非零位全部被消耗并出现在结果中，然后继续下一个点。对整数结果值进行数字排序，生成类似于 PostGIS 索引的数据结构。
现在你有了一个离散化的表示，它支持对最近邻居的相当有效的查询（尽管不可否认 N=1e3 太大了，不方便）。找到两个或多个粗粒度的邻近邻居后，您可以查询原始向量表示以获得它们之间的高分辨率距离，以进行更精细的区分。如果您的数据分布结果有很大一部分点与最近邻居离散化了一位，例如氧原子的位置，每个点都有一个伙伴，那么增加全局最小距离估计，以便低阶位提供足够的歧视。
类似的离散化方法将适当地缩放例如二维输入并标记最初为空的网格，然后扫描直接邻域。由于适当的缩放，这依赖于全局最小值位于“小”邻域内。在您的情况下，您将标记一个 N 维网格。