python - 查找不同维度数组的最近邻居

Question

我必须计算数千个不均匀数组的相似性度量。 简单的实现基本上是 O(n²) ，对于我拥有的数组数量来说，它花费的时间太长了。 希望我只对最相似数组的相似性感兴趣。 到目前为止，我使用了 NearestNeighbors 的 sci-kit learn 实现，它可以处理具有相同维数的数组。但是，NearestNeighbors 基于 KD 树，我认为不可能将此算法应用于不均匀数组。

对于不同维度的数组有其他选择吗？

这里是总结问题的代码片段:

import numpy as np

from sklearn.neighbors.unsupervised import NearestNeighbors


def partial_mse(a: np.array, b: np.array) -> float:
    def mse(a: np.array, b: np.array) -> float:
        mse = (np.square(a - b)).mean()
        return -np.sqrt(mse)

    if a.size == b.size:
        return mse(a, b)

    # a is always the bigger one
    if a.size < b.size:
        a, b = b, a

    partial_mse = [mse(a[i:i + b.size], b) for i in range(a.size - b.size + 1)]
    return np.max(partial_mse)

uneven_array = np.array([[1, 2, 3, 4], [3, 4], [3, 2, 6], [2, 1, 3], [3]])
even_array = np.array([[1, 2, 3, 4], [3,2, 4, 1], [3, 2, 6, 1], [2, 6, 1, 3], [3, 5, 2, 0]])


nnfit = NearestNeighbors(n_neighbors=2, algorithm='auto', n_jobs=-1,
                         metric=partial_mse, metric_params={}).fit(uneven_array)

ValueError: setting an array element with a sequence.

Answer 1

NearestNeighbour 算法基于将数组抽象为 n 维点。因此，拥有不同维度的点将使算法变得不正常，并且即使您设法实现它，也可能无法为您提供所需的内容。

如果 n 是最大维度数，则每个较低维度 (k) 的点实际上对应于较高维度空间中的 (n-k+1) 个可能的点(通过用数组 a 的元素填充缺失的维度) ，您选择的指标将返回 (n-k+1) 个点中的最大相似度。