두 클러스터 사이의 가장 가까운 지점 Matlab

Question

3D 점으로 구성된 클러스터 세트가 있습니다. 각 두 클러스터에서 가장 가까운 두 점을 얻고 싶습니다.

예 : 나는 3D 점들로 구성된 5 개의 클러스터 C1 ~ C5를 가지고 있습니다. C1과 C2의 경우 C1과 C2 사이의 두 지점 C1과 C2 사이의 두 점, 즉 C2와 C3 사이의 두 점인 Pc1 "C1 지점"과 Pc2 "C2 지점"이 있습니다. .C5 등등. 그 후에 다른 클러스터 사이의 가장 가까운 지점을 나타내는 20 점을 갖게됩니다.

둘째,이 점과 각 점 사이의 거리가 특정 거리 "임계 값"보다 작 으면이 점들을 연결하려고합니다. 누군가가 나에게

알려 주시기 바랍니다 수 있다면

그래서 부탁 해요

Update: 

암로가 당신의 대답을, 나는 CIDX = kmeans에 업데이트되었습니다 감사합니다 (X, K, '거리', 'cityblock' 'replicates', 5); 빈 클러스터 오류를 해결합니다. 그러나 "pdistmex 메모리가 부족합니다. 옵션에 대해 HELP MEMORY를 입력하십시오."라는 또 다른 오류가 나타납니다. 그래서 여기에 귀하의 답변을 확인했습니다 : Out of memory error while using clusterdata in MATLAB 및 아래 코드를 업데이트했지만 문제는 지금이 코드에 인덱싱 오류가 있다는 것입니다 mn = min(min(D(idx1,idx2))); 나는이 오류에 대한 해결책이 있는지 묻는거야?

코드 사용 :

%function single_linkage(depth,clrr) 
X = randn(5000,3); 
%X=XX; 
% clr = clrr; 
K=7; 
clr = jet(K); 
%// cluster into K=4 
K = 7; 
%CIDX = kmeans(X,K); 


%// pairwise distances 
SUBSET_SIZE = 1000;   %# subset size 
ind = randperm(size(X,1)); 
data = X(ind(1:SUBSET_SIZE), :); 
D = squareform(pdist(data)); 
subs = 1:size(D,1); 
CIDX=kmeans(D, K,'distance','sqEuclidean', 'replicates',5); 
centers = zeros(K, size(data,2)); 
for i=1:size(data,2) 
    centers(:,i) = accumarray(CIDX, data(:,i), [], @mean); 
end 

%# calculate distance of each instance to all cluster centers 
D = zeros(size(X,1), K); 
for k=1:K 
    D(:,k) = sum(bsxfun(@minus, X, centers(k,:)).^2, 2); 
end 
%D=squareform(D); 
%# assign each instance to the closest cluster 
[~,clustIDX] = min(D, [], 2); 
%// for each pair of clusters 
cpairs = nchoosek(1:K,2); 
pairs = zeros(size(cpairs)); 
dists = zeros(size(cpairs,1),1); 
for i=1:size(cpairs,1) 
    %// index of points assigned to each of the two cluster 
    idx1 = (clustIDX == cpairs(i,1)); 
    idx2 = (clustIDX == cpairs(i,2)); 

    %// shortest distance between the two clusters 
    mn = min(min(D(idx1,idx2))); 
    dists(i) = mn; 

    %// corresponding pair of points with the minimum distance 
    [r,c] = find(D(idx1,idx2)==mn); 
    s1 = subs(idx1); s2 = subs(idx2); 
    pairs(i,:) = [s1(r) s2(c)]; 
end 

%// filter pairs by keeping only those whose distances is below a threshold 
thresh = inf; 
cpairs(dist>thresh,:) = []; 

%// plot 3D points color-coded by clusters 
figure('renderer','zbuffer') 
%clr = lines(K); 
h = zeros(1,K); 
for i=1:K 
h(i) = line(X(CIDX==i,1), X(CIDX==i,2), X(CIDX==i,3), ... 
    'Color',clr(i,:), 'LineStyle','none', 'Marker','.', 'MarkerSize',5); 
end 
legend(h, num2str((1:K)', 'C%d')) %' 
view(3), axis vis3d, grid on 

%// mark and connect nearest points between each pair of clusters 
for i=1:size(pairs,1) 
    line(X(pairs(i,:),1), X(pairs(i,:),2), X(pairs(i,:),3), ... 
     'Color','k', 'LineStyle','-', 'LineWidth',3, ... 
     'Marker','o', 'MarkerSize',10); 
end 

Answer 1

당신은 무엇을 요구하는 것은 single-linkage clustering 각 단계에서 무엇을하는지와 비슷한 소리; 바텀 - 업 (top-up)으로부터, 최단 거리로 분리 된 클러스터가 결합된다.

다음은 어쨌든이 문제를 해결할 수있는 강력한 방법입니다. 더 효율적인 구현 방법이있을 것이라고 확신하지만 구현하기 쉽습니다.

상기 예에서 데이터를 랜덤하게 생성하고 흥미로운하지 않은 것

---

참고

%// data of 3D points 
X = randn(5000,3); 

%// cluster into K=4 
K = 4; 
CIDX = kmeans(X,K); 

%// pairwise distances 
D = squareform(pdist(X)); 
subs = 1:size(X,1); 

%// for each pair of clusters 
cpairs = nchoosek(1:K,2); 
pairs = zeros(size(cpairs)); 
dists = zeros(size(cpairs,1),1); 
for i=1:size(cpairs,1) 
    %// index of points assigned to each of the two cluster 
    idx1 = (CIDX == cpairs(i,1)); 
    idx2 = (CIDX == cpairs(i,2)); 

    %// shortest distance between the two clusters 
    mn = min(min(D(idx1,idx2))); 
    dists(i) = mn; 

    %// corresponding pair of points with the minimum distance 
    [r,c] = find(D(idx1,idx2)==mn); 
    s1 = subs(idx1); s2 = subs(idx2); 
    pairs(i,:) = [s1(r) s2(c)]; 
end 

%// filter pairs by keeping only those whose distances is below a threshold 
thresh = inf; %// use your threshold value instead 
cpairs(dists>thresh,:) = []; 

%// plot 3D points color-coded by clusters 
figure('renderer','zbuffer') 
clr = lines(K); 
h = zeros(1,K); 
for i=1:K 
    h(i) = line(X(CIDX==i,1), X(CIDX==i,2), X(CIDX==i,3), ... 
     'Color',clr(i,:), 'LineStyle','none', ... 
     'Marker','.', 'MarkerSize',5); 
end 
legend(h, num2str((1:K)', 'C%d')) %' 
view(3), axis vis3d, grid on 

%// mark and connect nearest points between each pair of clusters 
for i=1:size(pairs,1) 
    line(X(pairs(i,:),1), X(pairs(i,:),2), X(pairs(i,:),3), ... 
     'Color','k', 'LineStyle','-', 'LineWidth',3, ... 
     'Marker','o', 'MarkerSize',10); 
end 

때문에 연결된 가까운 지점을 참조하기 어렵다. 대신 이전의

mx = max(max(D(idx1,idx2))); 

:

그냥 재미를 위해, 여기에 내가 단순히 (complete-linkage clustering 유사) 클러스터의 쌍 사이의 최대 거리, 즉 사용하여 최소 거리를 교체 다른 결과이다 :

mn = min(min(D(idx1,idx2))); 

은 우리가 클러스터의 각 쌍 사이에서 가장 먼 점을 연결하는 방법을 보여준다. 이 시각화는 제 생각에 좀 더 흥미 롭습니다.