我在Matlab中使用k近邻算法进行数据分析。我的数据由大约11795 x 88个数据矩阵组成，其中行是观测值，列是变量。
我的任务是为n个选定的测试点找到k个最近的邻居。目前，我正在使用以下逻辑:
对于所有的测试点
LOOP all the data and find the k-closest neighbors (by euclidean distance)
换句话说，我循环所有的n个测试点。对于每个测试点，我通过欧几里得距离搜索数据(不包括测试点本身)以寻找k个最近的邻居。对于每个测试点，这大约需要k x 11794次迭代。所以整个过程大概需要n × k × 11794次迭代。如果n = 10000, k = 7，这将是大约8.2560亿次迭代。
是否有更有效的方法来计算k个最近邻?现在大部分的计算都浪费了，因为我的算法很简单:
计算到所有其他点的欧几里得距离，选择最近的点并排除最近的点，不再进一步考虑->计算到所有其他点的欧几里得距离，并选择最近的点->等等->等等。
有没有一种聪明的方法来摆脱这种"浪费计算"?
目前这个过程需要大约7个小时在我的电脑(3.2 GHz, 8gb RAM, 64位win7)…(
下面是一些显式说明的逻辑(这不是我的全部代码，但这是消耗性能的部分):
for i = 1:size(testpoints, 1) % Loop all the test points
neighborcandidates = all_data_excluding_testpoints; % Use the rest of the data excluding the test points in search of the k-nearest neighbors
testpoint = testpoints(i, :); % This is the test point for which we find k-nearest neighbors
kneighbors = []; % Store the k-nearest neighbors here.
for j = 1:k % Find k-nearest neighbors
bdist = Inf; % The distance of the closest neighbor
bind = 0; % The index of the closest neighbor
for n = 1:size(neighborcandidates, 1) % Loop all the candidates
if pdist([testpoint; neighborcandidates(n, :)]) < bdist % Check the euclidean distance
bdist = pdist([testpoint; neighborcandidates(n, :)]); % Update the best distance so far
bind = n; % Save the best found index so far
end
end
kneighbors = [kneighbors; neighborcandidates(bind, :)]; % Save the found neighbour
neighborcandidates(bind, :) = []; % Remove the neighbor from further consideration
end
end
使用pdist2:
A = rand(20,5); %// This is your 11795 x 88
B = A([1, 12, 4, 8], :); %// This is your n-by-88 subset, i.e. n=4 in this case
n = size(B,1);
D = pdist2(A,B);
[~, ind] = sort(D);
kneighbours = ind(2:2+k, :);
现在您可以使用kneighbours索引A中的一行。注意，kneighbours的列对应于B
但是既然你已经用pdist浸入了统计工具箱，为什么不使用Matlab的knnsearch呢?
kneighbours_matlab = knnsearch(A,B,'K',k+1);
注意kneighbours和kneighbours_matlab(:,2:end)'是一样的
我不熟悉特定的matlab函数，但您可以从公式中删除k。
有一个著名的选择算法
- 以数组A(大小为n)和数字k作为输入。
- 给出数组A的排列，使得第k个最大/最小元素位于第k位。
- 小元素在左边，大元素在右边。
。
A=2,4,6,8,10,1,3,5,7,9; k=5
output = 2,4,1,3,5,10,6,8,7,9
这是在O(n)步中完成的，不依赖于k。
EDIT1:您还可以预先计算所有距离，因为它看起来是您花费大部分计算的地方。它将是一个大约800M的矩阵，所以在现代机器上应该不会有问题。
我不确定它是否会加快代码，但它删除了内部的两个循环
for i = 1:size(testpoints, 1) % //Loop all the test points
temp = repmat(testpoints(i,:),size(neighborcandidates, 1),1);
euclead_dist = (sum((temp - neighborcandidates).^2,2).^(0.5));
[sort_dist ind] = sort(euclead_dist);
lowest_k_ind = ind(1:k);
kneighbors = neighborcandidates(lowest_k_ind, :);
neighborcandidates(lowest_k_ind, :) = [];
end
这样不行吗?
adjk = adj;
for i=1:k-1
adj_k = adj_k*adj;
end
kneigh = find(adj_k(n,:)>0)
给定节点n和索引k?
也许这是Matlab上下文中更快的代码。你也可以尝试并行函数、数据索引和近似最近邻算法，理论上会更有效率。
% a slightly faster way to find k nearest neighbors in matlab
% find neighbors for data Y from data X
m=size(X,1);
n=size(Y,1);
IDXs_out=zeros(n,k);
distM=(repmat(X(:,1),1,n)-repmat(Y(:,1)',m,1)).^2;
for d=2:size(Y,2)
distM=distM+(repmat(X(:,d),1,n)-repmat(Y(:,d)',m,1)).^2;
end
distM=sqrt(distM);
for i=1:k
[~,idx]=min(distM,[],1);
id=sub2ind(size(distM),idx',(1:n)');
distM(id)=inf;
IDXs_out(:,i)=idx';
end