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

uoifb46i 于 2023-03-16 发布在 Python

关注(0)|答案(3)|浏览(168)

我试图写一个函数，将过滤元组列表（模仿内存数据库），使用“最近邻居”或“最近匹配”类型的算法。
我想知道做这件事的最好（也就是最Python的）方法。下面的示例代码希望能说明我正在尝试做的事情。

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

对于上面的代码片段，输出应为：

（十、二、三、四、一百）

因为它"最接近“传递给函数get_nearest_neighbor（）的样本数据。
那么我的问题是，实现**get_nearest_neighbor（）**的最佳方法是什么？为了简洁等目的，假设我们只处理数值，并且我们使用的“距离度量”只是从当前行中减去输入数据的算术减法。

python

来源：https://stackoverflow.com/questions/9768823/python-nearest-neighbour-or-closest-match-filtering-on-data-records-list-of

3条答案

按热度按时间

ars1skjm1#

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

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的KDTree来寻找最近的邻居，Numpy的优势在于它不仅使用了更先进的算法，而且实现了高度优化的LAPACK (Linear Algebra PACKage)。

赞(0）回复(0）举报 2023-03-16

bpsygsoo2#

关于天真的NN *

许多其他的答案提出了“朴素最近邻”，这是一个O(N*d)-per-query算法（d是维度，在本例中似乎是常数，所以它是O(N)-per-query）。
虽然O(N)-per-query算法相当糟糕，但如果您的查询少于以下任何一个，您也许能够摆脱它（例如）：

10个查询和100000点
100个查询和10000个点
1000个查询和1000个点
10000个查询和100个点
10万次查询，10分
做得比天真好 *

否则，您将需要使用中列出的技术之一（尤其是最近邻数据结构）：

http://en.wikipedia.org/wiki/Nearest_neighbor_search（很可能是从该页链接出来的），链接了一些示例：
http://en.wikipedia.org/wiki/K-d_tree
http://en.wikipedia.org/wiki/Locality_sensitive_hashing
http://en.wikipedia.org/wiki/Cover_tree

特别是当你打算运行你的程序不止一次的时候。2很可能有一些可用的库。3如果你有一个很大的#queries * #points的乘积，不使用NN数据结构会花费太多的时间。4正如用户'dsign'在评论中指出的，你可以通过使用numpy库来挤出一个很大的额外的速度常数。
但是，如果您可以使用易于实现的naive-NN，那么您应该使用它。

赞(0）回复(0）举报 2023-03-16

kx7yvsdv3#

在生成器上使用heapq.nmaximum来计算每个记录的距离 * 权重。
比如：

heapq.nlargest(N, ((row, dist_function(row,criteria,weight)) for row in data), operator.itemgetter(1))

赞(0）回复(0）举报 2023-03-16

我来回答

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

3条答案

相关问题

热门标签

最新问答