これは、ここに投稿された質問の続き です。例として、ブール行列で重心を見つけることについて説明した2Dビットマップでの重心の検索。
ここで、行列を次の形式に展開するとします。
0 1 2 3 4 5 6 7 8 9
1 . X X . . . . . .
2 . X X X . . X . .
3 . . . . . X X X .
4 . . . . . . X . .
5 . X X . . . . . .
6 . X . . . . . . .
7 . X . . . . . . .
8 . . . . X X . . .
9 . . . . X X . . .
ご覧のとおり、4つの異なるクラスターに対して4つの重心があります。
重心が1つしかない場合、重心を見つける方法はすでにわかっています。この行列でそのアルゴリズムを実行すると、行列の中央にある点が得られますが、これは役に立ちません。
これらの質量のクラスターを見つけるための、優れた、正確で高速なアルゴリズムは何でしょうか？
マトリックスの各ポイントをチェックして、隣接するポイントに基づいて質量を計算すると思います。ポイントの質量は、たとえば距離の2乗になります。次に、互いに最小の距離で上位4つのポイントを選択できます。
これは、各ポイントの質量を見つけるためのアプローチを説明するために一緒に作成したPythonコードです。サンプルマトリックスを使用したセットアップ：
matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT / 2
X_RADIUS = WIDTH / 2
特定の点の質量を計算するには：
def distance(x1, y1, x2, y2):
'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
return abs(y1 - y2) + abs(x1 - x2)
def mass(m, x, y):
_mass = m[y][x]
for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
d = max(1, distance(x, y, _x, _y))
_mass += m[_y][_x] / (d * d)
return _mass
注：ここではマンハッタン距離（別名Cityblock、別名Taxicab Geometry）を使用しています。これは、ユークリッド距離を使用して追加された精度がsqrt（）を呼び出すコストに見合うとは思わないためです。
マトリックスを反復処理し、（x、y、mass（x、y））のようなタプルのリストを作成します。
point_mass = []
for y in range(0, HEIGHT):
for x in range(0, WIDTH):
point_mass.append((x, y, mass(matrix, x, y)))
各ポイントの質量でリストを並べ替えます。
from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)
そのソートされたリストの上位9ポイントを見てください。
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)
最高から最低まで作業し、すでに表示されているポイントに近すぎるポイントを除外すると、取得できます（コードで実行する時間がなくなったため、手動で実行しています...）：
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)
これは、マトリックスを見るだけで非常に直感的な結果です（例と比較すると、座標はゼロに基づいていることに注意してください）。
クラスタリング アルゴリズムが必要です。2 次元のグリッドがあり、エントリが互いに隣接しているので、これは簡単です。フラッドフィル アルゴリズムを使用できます。各クラスターを取得したら、2D 重心の記事のように中心を見つけることができます。.
私の最初の考えは、ゼロ以外の値を持つセルを最初に見つけることです。そこからいくつかのフラッドフィルアルゴリズムを実行し、見つかったセルの重心を計算します。次に、マトリックスから見つかったセルをゼロにし、上からやり直します。
もちろん、これは、tuinstoelがリンクしているGoogleの方法ほど拡張性はありませんが、より小さな行列に実装する方が簡単です。
編集：
ここでは、互いに素なセット（パス圧縮とランクごとの和集合を使用）が役立つ場合があります。それらは、和集合と素集合に対してO（α（n））時間計算量を持ちます。
α（n）= min { k：A k（1）≥n }。
a k（n）はアッカーマン関数であるため、任意の妥当な値に対して、 α（n）は基本的にO （1）になります。唯一の問題は、互いに素なセットがアイテムからセットへの一方向のマッピングであるということですが、すべてのアイテムを通過する場合、これは問題ではありません。
これがデモンストレーション用の簡単なPythonスクリプトです。
from collections import defaultdict
class DisjointSets(object):
def __init__(self):
self.item_map = defaultdict(DisjointNode)
def add(self,item):
"""Add item to the forest."""
# It's gets initialized to a new node when
# trying to access a non-existant item.
return self.item_map[item]
def __contains__(self,item):
return (item in self.item_map)
def __getitem__(self,item):
if item not in self:
raise KeyError
return self.item_map[item]
def __delitem__(self,item):
del self.item_map[item]
def __iter__(self):
# sort all items into real sets
all_sets = defaultdict(set)
for item,node in self.item_map.iteritems():
all_sets[node.find_set()].add(item)
return all_sets.itervalues()
class DisjointNode(object):
def __init__(self,parent=None,rank=0):
if parent is None:
self.parent = self
else:
self.parent = parent
self.rank = rank
def union(self,other):
"""Join two sets."""
node1 = self.find_set()
node2 = other.find_set()
# union by rank
if node1.rank > node2.rank:
node2.parent = node1
else:
node1.parent = node2
if node1.rank == node2.rank:
node2.rank += 1
return node1
def find_set(self):
"""Finds the root node of this set."""
node = self
while node is not node.parent:
node = node.parent
# path compression
root, node = node, self
while node is not node.parent:
node, node.parent = node.parent, root
return root
def find_clusters(grid):
disj = DisjointSets()
for y,row in enumerate(grid):
for x,cell in enumerate(row):
if cell:
node = disj.add((x,y))
for dx,dy in ((-1,0),(-1,-1),(0,-1),(1,-1)):
if (x+dx,y+dy) in disj:
node.union(disj[x+dx,y+dy])
for index,set_ in enumerate(disj):
sum_x, sum_y, count = 0, 0, 0
for x,y in set_:
sum_x += x
sum_y += y
count += 1
yield 1.0 * sum_x / count, 1.0 * sum_y / count
def main():
grid = [[('.' != cell) for cell in row if not cell.isspace()] for row in (
". X X . . . . . .",
". X X X . . X . .",
". . . . . X X X .",
". . . . . . X . .",
". X X . . . . . .",
". X . . . . . . .",
". X . . . . . . .",
". . . . X X . . .",
". . . . X X . . .",
)]
coordinates = list(find_clusters(grid))
centers = dict(((round(x),round(y)),i) for i,(x,y) in enumerate(coordinates))
for y,row in enumerate(grid):
for x,cell in enumerate(row):
if (x,y) in centers:
print centers[x,y]+1,
elif cell:
print 'X',
else:
print '.',
print
print
print '%4s | %7s %7s' % ('i','x','y')
print '-'*22
for i,(x,y) in enumerate(coordinates):
print '%4d | %7.4f %7.4f' % (i+1,x,y)
if __name__ == '__main__':
main()
出力：
. X X . . . . . .
. X 3 X . . X . .
. . . . . X 4 X .
. . . . . . X . .
. X X . . . . . .
. 2 . . . . . . .
. X . . . . . . .
. . . . X X . . .
. . . . X 1 . . .
i | x y
----------------------
1 | 4.5000 7.5000
2 | 1.2500 4.7500
3 | 1.8000 0.6000
4 | 6.0000 2.0000
これのポイントは、互いに素なセットを示すことでした。の実際のアルゴリズムは、find_clusters()より堅牢なものにアップグレードできます。
参考文献