あなたが説明している問題は、一般的にクラスタリングまたはクラスター分析と呼ばれます。データセットと分析の制約によっては、非常に難しい場合があります。ただし、あなたの場合、使用するしきい値(5ピクセル)が難しいため、簡単です。
Aardvarkkはすでに優れたソリューションを発表していますが、クラスタリングのプロセスを実際に示しているわけではありません。これは、データをクラスター化してほぼ同じ結果を得ることができる非常に簡単な方法です。
- ポイント間のペアワイズ距離を計算します。Nポイントの場合、これはNxN行列になります
- そのマトリックスのしきい値
- 行列の行を反復処理します
各反復は次のようになります。
i
すでにクラスター化されている場合は、続行します
- がクラスター内にない場合
i
は、新しいクラスターを作成して割り当てi
ます
- ( 1に等しい
i
行の列)に近い他のすべてのポイントを検索しますi
- それらのポイントのいずれかがすでにクラスター内にあるかどうかを確認してください
- はいの場合、設定され、すべてのポイントが最小クラスターIDに
i
近いi
- セットがなく、すべてのポイントがクラスター
i
に近い場合i
i's
これが私が作った簡単な例です:
%Generate random points
nPts = 300;
clustId = zeros(nPts,1);
clusterCount = 0;
x = randi(3, [1, nPts])*10+ randn(1, nPts);
y = randi(3, [1, nPts])*10 + randn(1, nPts);
%Compute the distance matrix from http://goo.gl/8mAoC
dist = distance([x;y], [x;y]);
maxDist = 5;
binDist = dist <= maxDist;
for i = 1:nPts
% if this point is already clustered skip it
if clustId(i) ~= 0
continue;
end
%if the current point isn't in a cluster, create a new cluster and add
%the point to that cluster
if clustId(i) == 0
clusterCount = clusterCount+1;
clustId(i) = clusterCount;
fprintf('New point, creating cluster:%d\n', clusterCount);
end
% get the indices of the points that collide with the i
idx = binDist(:,i);
% check to see if idx contains points that already belong to another clustered
% if it doesn't collisionIdx will be equal to i
collisionIdx = idx & clustId>0;
%get the smallest cluster from collisionIdx
mergeClustId = min(clustId(collisionIdx));
%assing all the original points to that cluster
clustId(idx) = mergeClustId;
end
クラスターIDを繰り返し処理して、重心を計算します。
cx = [];
cy = [];
for i = 1:clusterCount
idx = clustId == i;
cx(i) = mean(x(idx));
cy(i) = mean(y(idx));
end
次に、結果を次のようにプロットします。
figure;
plot(cx,cy,'c.', 'markersize', 50); hold on;
plot(x,y,'.');
