Trovare cluster di massa in una matrice / bitmap
https://stackoverflow.com/questions/411837
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Questo è in seguito alla domanda pubblicata qui: Trovare il centro di massa su una bitmap 2D che ha parlato di trovare il centro di massa in una matrice booleana, come è stato dato l'esempio.
Supponiamo ora di espandere la matrice in questo modulo:
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 . . .
Come puoi vedere ora abbiamo 4 centri di massa, per 4 diversi cluster.
Sappiamo già come trovare un centro di massa dato che ne esiste solo uno, se eseguiamo quell'algoritmo su questa matrice otterremo un punto nel mezzo della matrice che non ci aiuta.
Quale può essere un algoritmo buono, corretto e veloce per trovare questi cluster di massa?
Soluzione
Penso che controllerei ogni punto della matrice e capirei che è massa in base ai suoi vicini. La massa per i punti cadrebbe con dire il quadrato della distanza. È quindi possibile selezionare i primi quattro punti con una distanza minima l'uno dall'altro.
Ecco un po 'di codice Python che ho montato insieme per cercare di illustrare l'approccio per scoprire la massa per ogni punto. Alcuni setup usando la tua matrice di esempio:
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
Per calcolare la massa per un dato punto:
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
Nota: sto usando Manhattan distanze (aka Cityblock, aka Taxicab Geometry) qui perché non credo che l'accuratezza aggiunta usando le distanze euclide valga il costo di chiamare sqrt ().
Scorrendo la nostra matrice e costruendo un elenco di tuple come (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)))
Ordinamento dell'elenco sulla massa per ciascun punto:
from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)
Guardando i primi 9 punti in quell'elenco ordinato:
(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)
Se dovessimo lavorare dal più alto al più basso e filtrare via i punti che sono troppo vicini ai punti già visti, otterremo (lo sto facendo manualmente poiché non ho più tempo per farlo nel codice .. .):
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)
Che è un risultato piuttosto intuitivo dal solo guardare la tua matrice (nota che le coordinate sono basate su zero quando si confronta con il tuo esempio).
Altri suggerimenti
Hai bisogno di un algoritmo di clustering, questo è facile poiché hai solo una griglia bidimensionale e le voci si confinano tra loro. Puoi semplicemente utilizzare un algoritmo di flooding . Una volta che hai ciascun cluster, puoi trovare il centro come in Centro 2D dell'articolo di massa. .
Ecco una domanda simile con un algoritmo non così veloce e diverse altri modi migliori per farlo.
Il mio primo pensiero sarebbe quello di trovare prima qualsiasi cella con un valore diverso da zero. Da lì eseguono alcuni algoritmi di riempimento e calcolano il centro di massa delle celle trovate. Successivamente azzera le celle trovate dalla matrice e ricomincia da capo.
Questo ovviamente non si ridimensionerebbe così come il metodo di Google, che tuinstoel ha collegato, ma sarebbe più facile da implementare per matrici più piccole.
EDIT:
Disjoint sets (usando la compressione del percorso e l'unione per rango) potrebbero essere utili qui. Hanno O ( & # 945; ( n )) complessità temporale per unione e ricerca, dove
& # 945; ( n ) = min { k : A k (1) & # 8805; n }.
Ak ( n ) è la funzione di Ackerman, quindi & # 945; ( n ) sarà essenzialmente O (1) per qualsiasi valore ragionevole. L'unico problema è che gli insiemi disgiunti sono una mappatura unidirezionale degli elementi da impostare, ma questo non ha importanza se si attraversano tutti gli elementi.
Ecco un semplice script Python per dimostrazione:
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()
Output:
. 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
Lo scopo era dimostrare insiemi disgiunti. L'attuale algoritmo in find_clusters () potrebbe essere aggiornato a qualcosa di più robusto.
Riferimenti
- Introduzione agli algoritmi. 2a ed. Cormen et.al.
