最近邻算法(一般近邻算法、正向最近算法或后最近算法)

Question

我试图写一个算法，可以找到用户指定的最近的邻居。通过用户指定，我的意思是用户可以指定它是一般最近的邻居，前向最近的邻居，还是后向最近的邻居。

这段代码的灵感来源于这是如此的帖子。虽然搜索整个数组并不理想(也许可以使用搜索排序作为替代)，但我希望在给定的数据数组中找到用户指定的最近值的所有出现。虽然还可以使用其他技术来实现相同的目标(例如，使用参数排序值的差异的累积和)，但我觉得下面的代码更容易阅读/理解，而且可能更快，因为它执行的操作更少，需要遍历整个数据数组。尽管如此，我想知道是否有更好的方法(就速度而言)来实现相同的输出，因为这段代码将应用于至少70,000个数据点的数据集。与值本身相比，我更关心的是值发生的指数。

import numpy as np

样本数据

sample = np.array([300, 800, 200, 500, 600, 750, 700, 450, 400, 550, 350, 900])
# sample = np.array([300, 800, 200, 500, 600, 750, 700, 450, 400, 550, 350, 900] * 2)

主要算法

def search_nearest(data, search_value, direction=None):
    """ 
    This function can find the nearest, forward-nearest, or 
    backward-nearest value in data relative to the given search value.
    """

    if not isinstance(data, np.ndarray):
        data = np.array(data)

    print("\n>>     DATA\n{}\n".format(data))
    print(">>     SEARCH VALUE\n{}\n".format(search_value))

    if direction is None:
        delta = np.abs(data - search_value)
        res = np.where(delta == np.min(delta))[0]

    elif direction == 'forward':
        delta = data - search_value
        try:
            res = np.where(delta == np.min(delta[delta >= 0]))[0]
        except:
            raise ValueError("no forward nearest match exists")

    elif direction == 'backward':
        delta = search_value - data
        try:
            res = np.where(delta == np.min(delta[delta >= 0]))[0]
        except:
            raise ValueError("no backward nearest match exists")

    print(" .. INDEX OF NEAREST NUMBER\n{}\n".format(res))
    print(" .. NUMBER AT THAT INDEX\n{}\n".format(data[res]))
    print("--------------------")

调用主函数

# crd = None
crd = 'forward'
# crd = 'backward'

for val in (799, 301, 800, 250, 8, 901):
    search_nearest(sample, search_value=val, direction=crd)

Answer 1

码

您的一些程序是复制n粘贴的代码；有机会进行重构。

您的docstring几乎没有提供有效方向值的指导。考虑使用enum.Enum。如果没有一个变成0，那么1和-1可以表示方向，用δ乘以符号，用一块石头杀死两箱。

结果的标识符res很好，但是考虑使用像idx这样的缩写来索引，说明它不是docstring所表示的要计算的“值”。更好的方法是，将其转换为文档化的函数，以返回索引，并将print语句推入调用函数。

crd = 'forward'

我愿意相信"d“表示”方向“，但是标识符的"cr”部分是模糊的。

算法

如果有更好的方法(就速度而言)来实现相同的输出

您的主要功能表明，您将反复询问具有不同搜索值的大型(70k) sample。在这种情况下，您的数据结构不适合您的任务。

您正在强迫熊猫读取每个查询中的所有N值。别干那事。

生成存储输入(索引、值)的两列副本。按价值分类。到目前为止，费用是N对数N。

现在，对于每个查询，二进制搜索search_value在result_index上登陆，代价是log N。想要的答案是在result_index，或者它前面的条目，或者后面的条目。然后使用存储的索引在原始输入数据中报告相应的索引。

Answer 2

除了@J_H的建议之外，您还可以稍微简化这个函数。因为我只需要索引，所以如果在给定的方向上没有最近的值，则函数返回索引号或-1。

# Find nearest number in array and return index
def find_nearest(array, number, direction=None):
    idx = -1
    if array.empty:
        return idx
    if direction is None:
        idx = (np.abs(array - number)).idxmin()
    elif direction == 'backward':
        _delta = number - array
        _delta_positive = _delta[_delta > 0]
        if not _delta_positive.empty:
            idx = _delta_positive.idxmin()
    elif direction == 'forward':
        _delta = array - number
        _delta_positive = _delta[_delta > 0]
        if not _delta_positive.empty:
            idx = _delta_positive.idxmin()
    return idx