为不同维度的数组寻找最近的邻居

Question

我必须计算数千个不均匀数组的相似性度量。天真的实现基本上是 O(n²) 并且对于我拥有的数组数量来说花费的时间太长了。希望我只对最相似数组的相似性感兴趣。到目前为止，我使用了 NearestNeighbors 的 sci-kit 学习实现，它为具有相同维数的数组完成了工作。但是，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

最近邻算法基于将数组抽象为 n 维点。因此，具有不同维度的点会使算法失控，并且即使您设法实现它也可能不会给您想要的东西。

如果 n 是最大维数，那么每个较低维度 (k) 点实际上对应于较高维度 space 中的 (n-k+1) 个可能点（通过用数组 a) 的元素和您选择的指标将 return (n-k+1) 个点中的最大相似度。

Answer 2

经过几次尝试，我发现：

用默认值填充space是使用NearestNeighbors和KD-tree的唯一方法。但是，默认值会污染相似度函数。特征最相似的部分将是具有相同填充值的部分。

我通过将填充值添加为 partial_mse 的参数并在 partial_mse 中过滤掉该值来修复它。这个填充值应该是数组中不存在的值，否则会过滤掉真正的值！

def partial_mse(a: np.array, b: np.array, **kwargs) -> float:
    [...]
    fill_value = kwargs["fill_value"]
    a, b = a[a != fill_value], b[b != fill_value]
    [...]

nnfit = NearestNeighbors(n_neighbors=10, algorithm='auto', n_jobs=-1, \
 metric=partial_mse, metric_params={"fill_value": fill_value).fit(matrix_features)

为不同维度的数组寻找最近的邻居

Find nearest neighbors for arrays of different dimentions

python

arrays

nearest-neighbor