c++ - 知道其公共(public) ID 的拆分数据

Question

我想拆分这些数据，

ID x    y
1  2.5  3.5
1  85.1 74.1
2  2.6  3.4
2  86.0 69.8
3  25.8 32.9
3  84.4 68.2
4  2.8  3.2
4  24.1 31.8
4  83.2 67.4

我能够，与他们的搭档配对，例如，

ID x    y    ID x    y   
1  2.5  3.5  1  85.1 74.1
2  2.6  3.4  2  86.0 69.8
             3  25.8 32.9
             4  24.1 31.8

但是，正如您所注意到的，ID 4 中的一些新行放错了，因为它只是被添加到接下来的几行中。我想正确地拆分它们而不必使用我已经在使用的复杂逻辑...有人可以给我一个算法或想法吗？

它应该看起来像，

ID x    y    ID x    y      ID x    y 
1  2.5  3.5  1  85.1 74.1   3  25.8 32.9
2  2.6  3.4  2  86.0 69.8   4  24.1 31.8
4  2.8  3.2  3  84.4 68.2
             4  83.2 67.4

Answer 1

看来您的问题实际上是关于聚类的，而 ID 列与确定哪些点对应于哪些无关。

实现该目标的常见算法是 k-means clustering .但是，您的问题暗示您事先不知道集群的数量。这使事情变得复杂，并且已经在 StackOverflow 上提出了很多关于此问题的问题:

1. Kmeans without knowing the number of clusters?
2. compute clustersize automatically for kmeans
3. How do I determine k when using k-means clustering?
4. How to optimal K in K - Means Algorithm
5. K-Means Algorithm

不幸的是，对此没有“正确”的解决方案。一个特定问题中的两个集群确实可以被视为另一个问题中的一个集群。这就是为什么您必须自己决定的原因。

不过，如果您正在寻找简单的东西(并且可能不准确)，您可以使用欧氏距离作为衡量标准。计算点之间的距离(例如使用 pdist )，并将距离低于特定阈值的点分组。

例子

%// Sample input
A = [1,  2.5,  3.5;
     1,  85.1, 74.1;
     2,  2.6,  3.4;
     2,  86.0, 69.8;
     3,  25.8, 32.9;
     3,  84.4, 68.2;
     4,  2.8,  3.2;
     4,  24.1, 31.8;
     4,  83.2, 67.4];

%// Cluster points
pairs = nchoosek(1:size(A, 1), 2); %// Rows of pairs
d = sqrt(sum((A(pairs(:, 1), :) - A(pairs(:, 2), :)) .^ 2, 2)); %// d = pdist(A)
thr = d < 10;                      %// Distances below threshold
kk = 1;
idx = 1:size(A, 1);
C = cell(size(idx));               %// Preallocate memory
while any(idx)
     x = unique(pairs(pairs(:, 1) == find(idx, 1) & thr, :));
     C{kk} = A(x, :);
     idx(x) = 0;                   %// Remove indices from list
     kk = kk + 1;
end
C = C(~cellfun(@isempty, C));      %// Remove empty cells

结果是一个元胞数组C，每个元胞代表一个簇:

C{1} =
    1.0000    2.5000    3.5000
    2.0000    2.6000    3.4000
    4.0000    2.8000    3.2000

C{2} =
    1.0000   85.1000   74.1000
    2.0000   86.0000   69.8000
    3.0000   84.4000   68.2000
    4.0000   83.2000   67.4000

C{3} = 
    3.0000   25.8000   32.9000
    4.0000   24.1000   31.8000

请注意，这种简单的方法存在将簇半径限制为阈值的缺陷。但是，您想要一个简单的解决方案，因此请记住，当您向算法中添加更多“聚类逻辑”时，它会变得复杂。