我正在使用具有欧几里得距离的KNN对简单数据进行分类。我已经看到了我想通过MATLAB knnsearch函数完成此操作的示例，如下所示：
load fisheriris
x = meas(:,3:4);
gscatter(x(:,1),x(:,2),species)
newpoint = [5 1.45];
[n,d] = knnsearch(x,newpoint,'k',10);
line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o','linestyle','none','markersize',10)
上面的代码获取一个新点，即
[5 1.45]并找到最接近该新点的10个值。谁能给我展示一个MATLAB算法，并详细说明knnsearch函数的作用吗？还有其他方法吗？ 最佳答案
K最近邻（KNN）算法的基础是，您拥有一个由N行和M列组成的数据矩阵，其中N是我们拥有的数据点数，而M是每个数据点的维数。例如，如果我们将笛卡尔坐标放置在数据矩阵内，则通常是N x 2或N x 3矩阵。使用此数据矩阵，您可以提供一个查询点，并在该数据矩阵中搜索与该查询点最接近的k点。
我们通常使用查询与数据矩阵中其余点之间的欧几里得距离来计算我们的距离。但是，也可以使用其他距离，例如L1或城市街区/曼哈顿距离。完成此操作后，您将具有N欧几里得距离或曼哈顿距离，这些距离表示查询与数据集中每个对应点之间的距离。找到这些后，您只需按距离升序排序并检索在数据集和查询之间具有最小距离的k点，即可搜索查询中最靠近的k点。
假设您的数据矩阵存储在x中，并且newpoint是其中具有M列（即1 x M）的示例点，这是您将采用点形式进行的常规过程：
查找newpoint与x中每个点之间的欧几里得距离或曼哈顿距离。
将这些距离按升序排序。
返回k中最接近x的newpoint数据点。
让我们慢慢地做每一步。
步骤1
某人可能执行此操作的一种方式可能是在for循环中，如下所示：
N = size(x,1);
dists = zeros(N,1);
for idx = 1 : N
dists(idx) = sqrt(sum((x(idx,:) - newpoint).^2));
end
如果要实现曼哈顿距离，则只需：
N = size(x,1);
dists = zeros(N,1);
for idx = 1 : N
dists(idx) = sum(abs(x(idx,:) - newpoint));
end
dists是一个N元素向量，其中包含x和newpoint中每个数据点之间的距离。我们在newpoint和x中的数据点之间进行逐元素减法，将差异平方，然后将它们全部在一起。然后，该和为平方根，从而完成欧几里得距离。对于曼哈顿距离，您将逐个元素相减，取绝对值，然后将所有分量求和。这可能是最简单易懂的实现，但可能效率最低...尤其是对于较大的数据集和较大的数据维。另一个可能的解决方案是复制
sum并使该矩阵的大小与newpoint相同，然后对该矩阵进行逐元素减法，然后对每一行的所有列求和，并求平方根。因此，我们可以执行以下操作：N = size(x, 1);
dists = sqrt(sum((x - repmat(newpoint, N, 1)).^2, 2));
对于曼哈顿距离，您可以执行以下操作：
N = size(x, 1);
dists = sum(abs(x - repmat(newpoint, N, 1)), 2);
x获取矩阵或向量，并在给定方向上重复一定次数。在我们的例子中，我们想取我们的repmat向量，并将这newpoint次叠加在一起以创建一个N矩阵，其中每行的长度为N x M个元素。我们将这两个矩阵相减，然后对每个分量求平方。完成此操作后，我们对每一行的所有列进行M运算，最后取所有结果的平方根。对于曼哈顿距离，我们进行减法运算，取绝对值，然后求和。但是，我认为最有效的方法是使用
sum。这实质上完成了我们在幕后通过单个函数调用所讨论的复制。因此，代码就是这样：dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2));
对我来说，这看起来更干净，而且很重要。对于曼哈顿距离，您可以执行以下操作：
dists = sum(abs(bsxfun(@minus, x, newpoint)), 2);
第2步
现在我们有了距离，我们只需对它们进行排序。我们可以使用
bsxfun对距离进行排序：[d,ind] = sort(dists);
sort将包含按升序排序的距离，而d会告诉您未排序数组中每个值在排序结果中出现的位置。我们需要使用ind，提取此向量的第一个ind元素，然后使用k索引到我们的ind数据矩阵中，以返回最接近x的那些点。步骤三
最后一步是现在返回最接近
newpoint的那些k数据点。我们可以很简单地做到这一点：ind_closest = ind(1:k);
x_closest = x(ind_closest,:);
newpoint应在原始数据矩阵ind_closest中包含最接近x的索引。具体来说，newpoint包含需要从ind_closest中进行采样的行，以获得与x最接近的点。 newpoint将包含这些实际数据点。为了您的复制和粘贴乐趣，代码如下所示：
dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2));
%// Or do this for Manhattan
% dists = sum(abs(bsxfun(@minus, x, newpoint)), 2);
[d,ind] = sort(dists);
ind_closest = ind(1:k);
x_closest = x(ind_closest,:);
在您的示例中运行，让我们看看实际的代码：
load fisheriris
x = meas(:,3:4);
newpoint = [5 1.45];
k = 10;
%// Use Euclidean
dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2));
[d,ind] = sort(dists);
ind_closest = ind(1:k);
x_closest = x(ind_closest,:);
通过检查
x_closest和ind_closest，我们得到的是：>> ind_closest
ind_closest =
120
53
73
134
84
77
78
51
64
87
>> x_closest
x_closest =
5.0000 1.5000
4.9000 1.5000
4.9000 1.5000
5.1000 1.5000
5.1000 1.6000
4.8000 1.4000
5.0000 1.7000
4.7000 1.4000
4.7000 1.4000
4.7000 1.5000
如果运行
x_closest，您将看到变量knnsearch与n匹配。但是，变量ind_closest返回从d到每个点newpoint的距离，而不是实际数据点本身。如果您想要实际的距离，只需在我编写的代码之后执行以下操作：dist_sorted = d(1:k);
请注意，以上答案在一批
x示例中仅使用一个查询点。 KNN通常同时用于多个示例。假设我们有要在KNN中测试的N个查询点。这将导致一个Q矩阵，其中对于每个示例或每个切片，我们将返回维度为k x M x Q的k最近点。或者，我们可以返回M最近点的ID，从而生成k矩阵。让我们计算两者。一个简单的方法是将上述代码循环应用到每个示例中。
这样的事情在我们分配一个
Q x k矩阵并应用基于Q x k的方法来将输出矩阵的每一行设置到数据集中的bsxfun最近点时将起作用，在这里我们将使用Fisher Iris数据集，就像我们以前所拥有的。我们还将保持与上一个示例相同的尺寸，我将使用四个示例，因此k和Q = 4：%// Load the data and create the query points
load fisheriris;
x = meas(:,3:4);
newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5];
%// Define k and the output matrices
Q = size(newpoints, 1);
M = size(x, 2);
k = 10;
x_closest = zeros(k, M, Q);
ind_closest = zeros(Q, k);
%// Loop through each point and do logic as seen above:
for ii = 1 : Q
%// Get the point
newpoint = newpoints(ii, :);
%// Use Euclidean
dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2));
[d,ind] = sort(dists);
%// New - Output the IDs of the match as well as the points themselves
ind_closest(ii, :) = ind(1 : k).';
x_closest(:, :, ii) = x(ind_closest(ii, :), :);
end
尽管这很好，但我们可以做得更好。有一种方法可以有效地计算两组向量之间的平方欧几里德距离。如果您想在曼哈顿进行此操作，我将其保留为练习。咨询
M = 2，假定A是一个Q1 x M矩阵，其中每行是具有M个点的维度点Q1，而B是一个Q2 x M矩阵，其中每行也是一个点具有M个点的维度Q2，我们可以有效地计算距离矩阵D(i, j)，其中行i和列j处的元素表示i的行A和行j之间的距离使用以下矩阵公式表示B：nA = sum(A.^2, 2); %// Sum of squares for each row of A
nB = sum(B.^2, 2); %// Sum of squares for each row of B
D = bsxfun(@plus, nA, nB.') - 2*A*B.'; %// Compute distance matrix
D = sqrt(D); %// Compute square root to complete calculation
因此，如果让
A为查询点矩阵，而让B为由原始数据组成的数据集，则可以通过分别对每行进行排序并确定每行的k位置来确定k最接近的点。最小的行。我们还可以另外使用它自己来检索实际点。因此：
%// Load the data and create the query points
load fisheriris;
x = meas(:,3:4);
newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5];
%// Define k and other variables
k = 10;
Q = size(newpoints, 1);
M = size(x, 2);
nA = sum(newpoints.^2, 2); %// Sum of squares for each row of A
nB = sum(x.^2, 2); %// Sum of squares for each row of B
D = bsxfun(@plus, nA, nB.') - 2*newpoints*x.'; %// Compute distance matrix
D = sqrt(D); %// Compute square root to complete calculation
%// Sort the distances
[d, ind] = sort(D, 2);
%// Get the indices of the closest distances
ind_closest = ind(:, 1:k);
%// Also get the nearest points
x_closest = permute(reshape(x(ind_closest(:), :).', M, k, []), [2 1 3]);
我们看到，用于计算距离矩阵的逻辑是相同的，但是一些变量已更改为适合示例。我们还使用
sort的两个输入版本对每一行进行独立排序，因此ind将包含每行的ID，而d将包含相应的距离。然后，我们可以通过将矩阵简单地截断为k列来找出最接近每个查询点的索引。然后，我们使用this blog和permute来确定相关的最接近点。我们首先使用所有最接近的索引，然后创建一个点矩阵，该点矩阵将所有ID相互堆叠，从而得到一个reshape矩阵。使用Q * k x M和reshape允许我们创建3D矩阵，使其变为我们指定的permute矩阵。如果您想自己获得实际的距离，我们可以索引k x M x Q并获取我们需要的东西。为此，您将需要使用d来获得线性索引，以便我们可以一次拍摄到sub2ind的索引。 d的值已经为我们提供了需要访问哪些列。我们需要访问的行仅是1，ind_closest次，2，k次，依此类推，直到k。 Q是要返回的点数：row_indices = repmat((1:Q).', 1, k);
linear_ind = sub2ind(size(d), row_indices, ind_closest);
dist_sorted = D(linear_ind);
当我们为上述查询点运行以上代码时，这些是我们获得的索引，点和距离：
>> ind_closest
ind_closest =
120 134 53 73 84 77 78 51 64 87
123 119 118 106 132 108 131 136 126 110
107 62 86 122 71 127 139 115 60 52
99 65 58 94 60 61 80 44 54 72
>> x_closest
x_closest(:,:,1) =
5.0000 1.5000
6.7000 2.0000
4.5000 1.7000
3.0000 1.1000
5.1000 1.5000
6.9000 2.3000
4.2000 1.5000
3.6000 1.3000
4.9000 1.5000
6.7000 2.2000
x_closest(:,:,2) =
4.5000 1.6000
3.3000 1.0000
4.9000 1.5000
6.6000 2.1000
4.9000 2.0000
3.3000 1.0000
5.1000 1.6000
6.4000 2.0000
4.8000 1.8000
3.9000 1.4000
x_closest(:,:,3) =
4.8000 1.4000
6.3000 1.8000
4.8000 1.8000
3.5000 1.0000
5.0000 1.7000
6.1000 1.9000
4.8000 1.8000
3.5000 1.0000
4.7000 1.4000
6.1000 2.3000
x_closest(:,:,4) =
5.1000 2.4000
1.6000 0.6000
4.7000 1.4000
6.0000 1.8000
3.9000 1.4000
4.0000 1.3000
4.7000 1.5000
6.1000 2.5000
4.5000 1.5000
4.0000 1.3000
>> dist_sorted
dist_sorted =
0.0500 0.1118 0.1118 0.1118 0.1803 0.2062 0.2500 0.3041 0.3041 0.3041
0.3000 0.3162 0.3606 0.4123 0.6000 0.7280 0.9055 0.9487 1.0198 1.0296
0.9434 1.0198 1.0296 1.0296 1.0630 1.0630 1.0630 1.1045 1.1045 1.1180
2.6000 2.7203 2.8178 2.8178 2.8320 2.9155 2.9155 2.9275 2.9732 2.9732
要将其与
k进行比较，您可以为第二个参数指定点矩阵，其中每行都是一个查询点，您将看到此实现和knnsearch之间的索引和排序距离匹配。希望这对您有帮助。祝好运！