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

问题描述 投票:0回答:1

我必须在数千个不均匀数组上计算相似性度量。天真的实现方式基本上是在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.
python arrays nearest-neighbor
1个回答
0
投票

NearestNeighbour算法基于将数组抽象为n维点。因此,具有不同维度的点将使该算法不为所动,即使您设法实现该算法,也可能无法满足您的需求。

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

© www.soinside.com 2019 - 2024. All rights reserved.