Python:最近邻(或最接近匹配)过滤数据记录(元组列表)

Question

我正在尝试编写一个函数来过滤元组列表(模拟内存数据库)，使用“最近邻”或“最近匹配”类型的算法。

我想知道执行此操作的最佳(即最 Pythonic)方法。下面的示例代码有望说明我正在尝试做的事情。

datarows = [(10,2.0,3.4,100),
            (11,2.0,5.4,120),
            (17,12.9,42,123)]

filter_record = (9,1.9,2.9,99) # record that we are seeking to retrieve from 'database' (or nearest match)
weights = (1,1,1,1) # weights to approportion to each field in the filter

def get_nearest_neighbour(data, criteria, weights):
    for each row in data:
        # calculate 'distance metric' (e.g. simple differencing) and multiply by relevant weight
    # determine the row which was either an exact match or was 'least dissimilar'
    # return the match (or nearest match)
    pass

if __name__ == '__main__':
    result = get_nearest_neighbour(datarow, filter_record, weights)
    print result

对于上面的代码片段，输出应该是:

(10,2.0,3.4,100)

因为它是传递给函数 get_nearest_neighbor() 的样本数据的“最近”。

那么我的问题是，实现 get_nearest_neighbour() 的最佳方法是什么？。为了简洁等目的，假设我们只处理数值，并且我们使用的“距离度量”只是从当前行中输入数据的算术减法。

Answer 1

简单的开箱即用解决方案:

import math

def distance(row_a, row_b, weights):
    diffs = [math.fabs(a-b) for a,b in zip(row_a, row_b)]
    return sum([v*w for v,w in zip(diffs, weights)])

def get_nearest_neighbour(data, criteria, weights):
    def sort_func(row):
        return distance(row, criteria, weights)
    return min(data, key=sort_func)
    

如果您需要处理庞大的数据集，您应该考虑切换到 Numpy并使用 Numpy 的 KDTree寻找最近的邻居。使用 Numpy 的优势在于它不仅使用了更高级的算法，而且还实现了高度优化的顶部 LAPACK (Linear Algebra PACKage) .