有没有一种不需要分配内存的方式来查找K个最近邻居？

Question

有没有一种不需要分配内存的方式来查找K个最近邻居？

3

我需要这个来进行模拟研究。

最小工作示例：

x = rand(10,4)
y = rand(5,4)

对于y中的每一行，我想在x中找到它的5个最近邻的索引，即结果应该是一个5x5的索引矩阵。

- هنروقتان

你能举个例子详细说明吗？KNN是一种预测算法。如果你想要预测x中的y类，结果应该是5x1。而且你没有标签。我不明白。 - phipsgabler

我只需要前5个最近邻，不需要预测。例如，对于y [1,:]，在x中应该有5行与其最接近（欧几里得距离）。 - هنروقتان

y[1,:] 有5个最近邻居，y[2,:] 有5个最近邻居，以此类推，因此是5乘5的。 - هنروقتان

1

我在这里进行了一些优化尝试：https://codereview.stackexchange.com/q/272777/180160。虽然Code Review上的Julia用户很少，但这已经可以使用了，也许还有更多的改进到来。 - phipsgabler

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phipsgabler · Accepted Answer

事实证明这是不完整的，但我仍会发布我的尝试。

将矩阵“重新解释”为一个向量，而无需分配内存，在概念上很简单，但需要实现一个新的数组类型。这样的类型由JuliennedArrays.jl中的Sliced提供。

我认为最简单的实现如下：

mapslices(y, dims=2) do row
    partialsortperm(Slices(x, 2), 1:5, by=x -> norm(x - row))
end

这还需要分配一些内容；这至少必须是partialsortperm和中间行所使用的索引向量。

我试图在这个函数中摆脱它。

function knnslice!(result, x, y, k)
    result_sliced = Slices(result, 2)
    x_sliced = Slices(x, 2)
    y_sliced = Slices(y, 2)
    indices = collect(axes(x, 1))
    for i in eachindex(result_sliced, y_sliced)
        result_sliced[i] .= partialsortperm!(indices, x_sliced, 1:k, by=x -> norm(x - y_sliced[i]))
    end
    return result
end
knnslice(x, y, k) = knnslice!(similar(x, Int, size(y, 1), k), x, y, k)

但结果并没有得到改善，至少与您的示例数据大小的数组相比如此。我不确定如何通过这种实现来进一步降低它。缺失的部分将是一个直接在切片上工作的sortperm实现。对于小的k值，可以通过对x进行一次迭代并将结果行作为缓冲区（甚至是小堆）维护该大小，而不是执行部分排序。类似于：

function knnslice!(result, x, y, k)
    for (i_r, i_y) in zip(axes(result, 1), axes(y, 1))
        result_row = @view(result[i_r, :])
        fill!(result_row, 1)
        f(r) = norm(@view(x[r, :]) - @view(y[i_y, :]))
        for j_x in axes(x, 1)
            heappush!(result_row, j_x; by=f)
        end
    end
    return result
end

在这里，heappush! 应该插入到一个有序的最小堆中，按照 by 的顺序排列（类似于Python中提供的 heapq，但保持队列大小不变）。