Matlab最近的鄰居/跟蹤點

我有一組n複雜的數字，從時間步驟1到nsampl，通過複雜的平面。我想繪製這些數字和它們隨時間的軌跡（y軸表示虛部，x軸表示實部）。這些數字存儲在n x nsampl向量中。然而，在每個時間步中，n點的順序是隨機的。因此，在每個時間步中，我會在上一個時間步中選取一個點，在當前時間步中找到其最近的鄰居，並將其放置在與當前點相同的位置。然後我重複所有其他n-1點並繼續下一個時間步驟。這樣，上一步中的每個點都與新步驟中的一個點（1：1關係）相關聯。我目前的實施和一個例子如下。但是，我的實現非常慢（10 x 4000複數需要大約10秒）。由於我想增加兩者，集合大小n和時間框架nsampl這對我來說非常重要。有沒有更聰明的方法來實現這一點，以獲得一些表現？Matlab最近的鄰居/跟蹤點

例，其中n = 3和nsampl = 2：

%manually create a test vector X 
X=zeros(3,2); % zeros(n,nsampl) 
X(:,1)=[1+1i; 2+2i; 3+3i]; 
X(:,2)=[2.1+2i; 5+5i; 1.1+1.1i]; % <-- this is my vector with complex numbers 

%vector sort algorithm 
for k=2:nsampl 
    Xlast=[real(X(:,k-1)) imag(X(:,k-1))];   % create vector with x/y-coords from last time step 
    Xcur=[real(X(:,k)) imag(X(:,k))];    % create vector with x/y-coords from current time step 
    for i=1:size(X,1) % loop over all n points 
     idx = knnsearch(Xcur(i:end,:),Xlast(i,:)); %find nearest neighbor to Xlast(i,:), but only use the points not already associated, thus Xcur(i:end,:) points 
     idx = idx + i - 1; 
     Xcur([i idx],:) = Xcur([idx i],:);   %sort nearest neighbor to the same position in the vector as it was in the last time step 
    end 
    X(:,k) = Xcur(:,1)+1i*Xcur(:,2);    %revert x/y coordinates to a complex number 
end

結果：

X(:,2)=[1.1+1.1i; 2.1+2i; 5+5i];

誰能幫我加快這個代碼？

來源

2015-09-01 DayAndNight

是否有必要精確地複製算法的行爲？特別是步驟k中的兩個點（可以說是第一個和第二個）具有第k + 1步的第7個點，因爲它是鄰居，將其移動兩次。 – Daniel

或者爲了進一步精確我之前的評論，您的描述聽起來像是「加權二分圖的匹配」（最小化權重），並且您的代碼會執行一個貪婪版本，這接近最佳解決方案。 – Daniel

我希望我能理解你的評論權利，因爲我對雙方圖表一無所知。我想我不需要複製完全相同的行爲，只要還有1：1的關係（即'X（：，2）= [1.1 + 1.1i; 2.1 + 2i; 2.1 + 2i]'因爲它爲兩個不同的祖先找到了兩次相同的最近鄰居 – DayAndNight

您正在試圖解決的問題是由the hungarian algorithm（又名munkres）解決的組合優化問題。幸運的是，有一個matlab實現available for download.下載文件，並將其放在搜索路徑或函數旁邊。使用它的代碼是：

for k=2:size(X,2) 
    %build up a cost matrix, here cost is the distance between two points. 
    pairwise_distances=abs(bsxfun(@minus,X(:,k-1),X(:,k).')); 
    %let the algorithm find the optimal pairing 
    permutation=munkres(pairwise_distances); 
    %apply it 
    X(:,k)=X(permutation,k); 
end

來源

2015-09-01 23:20:17 Daniel

Matlab最近的鄰居/跟蹤點

回答

相關問題