我必须在数千个不均匀数组上计算相似性度量。天真的实现方式基本上是在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.
NearestNeighbour算法基于将数组抽象为n维点。因此,具有不同维度的点将使该算法不为所动,即使您设法实现该算法,也可能无法满足您的需求。
如果n是最大维数,则每个较低维(k)点实际上对应于较高维空间中的(n-k + 1)个可能点(通过使用数组a的元素填充缺失的维),并且您选择的指标将返回(n-k + 1)个点中的最大相似度。