algorithm - 如何选择部分密集数据集的均匀分布子集？

Question

P 是一个 n*d 矩阵，包含 n d 维样本。 P 在某些区域的密度是其他区域的数倍。我想选择 P 的一个子集，其中任何样本对之间的距离都大于 d0，并且我需要它遍布整个区域。所有样本都具有相同的优先级，无需优化任何内容(例如覆盖区域或成对距离之和)。

这是一个示例代码，但它确实很慢。我需要更高效的代码，因为我需要多次调用它。

%% generating sample data
n_4 = 1000; n_2 = n_4*2;n = n_4*4;
x1=[ randn(n_4, 1)*10+30; randn(n_4, 1)*3 + 60];
y1=[ randn(n_4, 1)*5 + 35; randn(n_4, 1)*20 + 80 ];
x2 = rand(n_2, 1)*(max(x1)-min(x1)) + min(x1);
y2 = rand(n_2, 1)*(max(y1)-min(y1)) + min(y1);
P = [x1,y1;x2, y2];
%% eliminating close ones
tic
d0 = 1.5;
D = pdist2(P, P);D(1:n+1:end) = inf;
E = zeros(n, 1); % eliminated ones
for i=1:n-1
    if ~E(i)
        CloseOnes = (D(i,:)<d0) & ((1:n)>i) & (~E');
        E(CloseOnes) = 1;
    end
end
P2 = P(~E, :);
toc
%% plotting samples
subplot(121); scatter(P(:, 1), P(:, 2)); axis equal;
subplot(122); scatter(P2(:, 1), P2(:, 2)); axis equal;

编辑:子集应该有多大？

作为j_random_hacker在评论中指出，如果我们不对所选样本的数量定义约束，则可以说 P(1, :) 是最快的答案。它巧妙地显示了标题的不连贯性!但我认为当前的标题更好地描述了目的。因此，让我们定义一个约束条件:“如果可能，请尝试选择 m 个样本”。现在有了 m=n 的隐含假设，我们可以获得最大可能的子集。正如我之前提到的，一种更快的方法优于找到最佳答案的方法。

Answer 1

一遍又一遍地寻找最近的点表明了一种针对空间搜索进行了优化的不同数据结构。我建议使用 delaunay 三角剖分。

以下解决方案是“近似”的，因为它可能会删除比绝对必要的更多的点。我对所有计算进行批处理，并在每次迭代中移除导致距离过长的所有点，并且在许多情况下，移除一个点可能会移除同一迭代中稍后出现的边。如果这很重要，可以进一步处理边缘列表以避免重复，或者甚至找到要删除的点，这将影响最大距离。

这很快。

dt = delaunayTriangulation(P(:,1), P(:,2));
d0 = 1.5;

while 1
    edge = edges(dt);  % vertex ids in pairs

    % Lookup the actual locations of each point and reorganize
    pwise = reshape(dt.Points(edge.', :), 2, size(edge,1), 2);
    % Compute length of each edge
    difference = pwise(1,:,:) - pwise(2,:,:);
    edge_lengths = sqrt(difference(1,:,1).^2 + difference(1,:,2).^2);

    % Find edges less than minimum length
    idx = find(edge_lengths < d0);
    if(isempty(idx))
        break;
    end

    % pick first vertex of each too-short edge for deletion
    % This could be smarter to avoid overdeleting
    points_to_delete = unique(edge(idx, 1));

    % remove them.  triangulation auto-updates
    dt.Points(points_to_delete, :) = [];

    % repeat until no edge is too short
end

P2 = dt.Points;