0

我有一组由 3D 点组成的集群。我想从每两个集群中获取最近的两个点。

例如：我有 5 个集群 C1 到 C5，由一个 3D 点组成。对于 C1 和 C2，有两个点 Pc1“C1 中的点”和 Pc2“C2 中的点”，它们是两个簇 C1 和 C2 之间最近的两个点，在 C1 和 C3..C5 之间相同，在 C2 和 C3 之间相同。 .C5 等等。之后，我将有 20 个点代表不同集群之间最近的点。

第二件事是，如果每个点与另一个点之间的距离小于某个距离“阈值”，我想将这些点连接在一起。

所以我问是否有人可以请教我

Update:

感谢 Amro 的回答，我已将其更新为 CIDX=kmeans(X, K,'distance','cityblock', 'replicates',5); 解决空簇错误。但是出现了另一个错误“pdistmex Out of memory. Type HELP MEMORY for your options。” 所以我在这里检查了你的答案：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
4

1 回答 1

1

您所要求的听起来类似于单链接聚类在每个步骤中所做的；自下而上，以最短距离分隔的簇被合并。

无论如何，下面是解决这个问题的蛮力方法。我确信有更有效的实现，但是这个很容易实现。

%// 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

3d 点

请注意，在上面的示例中，数据是随机生成的，不是很有趣，因此很难看到连接的最近点。

只是为了好玩，这里是另一个结果，我简单地将最小距离替换为集群对之间的最大距离（类似于完整链接聚类），即使用：

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

而不是以前的：

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

最大联动

这显示了我们如何连接每对集群之间的最远点。在我看来，这个可视化更有趣:)

于 2013-08-09T03:03:43.563 回答