Filtraggio di punti vicini da un elenco

Question

I ho risposto a metà di una domanda sulla ricerca di cluster di massa in una bitmap . Dico a metà risposta perché l'ho lasciato in una condizione in cui avevo tutti i punti della bitmap ordinati per massa e l'ho lasciato al lettore per filtrare l'elenco rimuovendo i punti dallo stesso cluster.

Poi, quando ho pensato a quel passaggio, ho scoperto che la soluzione non mi è saltata addosso come pensavo. Quindi ora sto chiedendo aiuto a voi ragazzi. Abbiamo un elenco di punti con masse simili (un elenco di tuple Python, ma puoi rappresentarlo come ritieni opportuno in qualsiasi lingua):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Ogni tupla ha la forma:

(x, y, mass)

Nota che l'elenco è ordinato qui. Se la tua soluzione preferisce non averli ordinati, è perfettamente OK.

La sfida, se ricordi , è trova i principali gruppi di massa. Il numero di cluster non è noto. Ma conosci le dimensioni della bitmap. A volte diversi punti all'interno di un cluster hanno una massa maggiore rispetto al centro del cluster (di dimensioni) successivo. Quindi quello che voglio fare è andare dai punti di massa superiore e rimuovere i punti nello stesso cluster (punti nelle vicinanze).

Quando ho provato questo ho finito per dover scorrere continuamente parti dell'elenco. Ho la sensazione di essere solo stupido. Come lo faresti? Pseudo codice o codice reale. Naturalmente, se riesci a decollare da dove ho lasciato quella risposta con il codice Python, è più facile per me sperimentarlo.

Il prossimo passo è capire quanti cluster ci sono davvero nella bitmap. Sto ancora lottando per definire quel problema, quindi potrei tornare con una domanda al riguardo.

MODIFICA: Dovrei chiarire che so che non c'è " corretto " rispondere a questa domanda. E il nome della domanda è la chiave. La fase uno del mio clustering è terminata. Sono alla ricerca di un veloce, accurato "abbastanza" metodo di filtraggio dei punti vicini.

Fammi sapere se riesco a rendere più chiara la domanda.

Answer 1

Solo per quello che sai, stai chiedendo una soluzione per un mal-posed problema: non esiste una soluzione definitiva. Va bene ... lo rende solo più divertente. Il tuo problema è per lo più mal posto perché non sai quanti cluster vuoi. Il clustering è una delle aree chiave dell'apprendimento automatico e alcuni approcci sono stati sviluppati nel corso degli anni.

Come ha sottolineato Arachnid, l'algoritmo k-means tende a essere buono e è abbastanza facile da implementare. I risultati dipendono in modo critico dall'ipotesi iniziale fatta e dal numero di cluster desiderati. Per superare il problema di ipotesi iniziale, è comune eseguire l'algoritmo molte volte con inizializzazioni casuali e scegliere il risultato migliore. Devi definire ciò che " migliore " si intende. Una misura sarebbe la distanza media quadrata di ciascun punto dal suo centro del cluster. Se vuoi indovinare automaticamente quanti cluster ci sono, dovresti eseguire l'algoritmo con un'intera gamma di numeri di cluster. Per ogni bene "migliore" misura, più cluster avranno sempre un aspetto migliore rispetto a un numero inferiore, quindi avrai bisogno di un modo per penalizzare il fatto di avere troppi cluster. La discussione MDL su wikipedia è un buon punto di partenza.

Il clustering K-significa sostanzialmente il modello di miscela . A volte è utile passare a una combinazione di gaussiani appresi dalla massimizzazione delle aspettative (descritta nel link appena indicato). Questo può essere più robusto di k-mean. Ci vuole un po 'più di sforzo per capirlo, ma quando lo fai, non è molto più difficile di k-significa implementarlo.

Esistono molte altre tecniche di clustering come il clustering agglomerativo e il clustering spettrale. Il clustering agglomerativo è piuttosto semplice da implementare, ma scegliere quando interrompere la creazione dei cluster può essere complicato. Se esegui un cluster agglomerativo, probabilmente vorrai guardare kd trees per una più veloce ricerche del vicino più vicino. La risposta di smacl descrive un modo leggermente diverso di fare un cluster agglomerativo usando un diagramma Voronoi.

Esistono modelli che possono scegliere automaticamente il numero di cluster per te come quelli basati su Allocazione latente di Dirichlet , ma sono molto più difficili da capire correttamente un attrezzo.

Potresti anche dare un'occhiata al mean-shift per vedere se è più vicino a quello che vuoi davvero.

Answer 2

Mi sembra che tu stia cercando l'algoritmo K-mean .

Answer 3

Come ho detto nel commento alla tua domanda, la risposta si basa sul fatto che la massa possa essere considerata scalare in questo contesto. In tal caso, le soluzioni basate sul colore probabilmente non funzioneranno poiché spesso il colore non viene considerato scalare.

Ad esempio, se ho una determinata area con 1 punto di massa elevata, è la stessa che avere la stessa area con 10 punti di 1/10 della massa? Se questo è vero, la massa non è scalare in questo contesto e tenderei a guardare un algoritmo usato per spaziare spazialmente valori simili non scalabili, ad es. diagrammi voronoi .

In questo caso, dove due aree voronoi adiacenti hanno una corrispondenza e una distanza di massa abbastanza vicine, possono essere raggruppate insieme. Potresti ripetere questo per trovare tutti i cluster.

Se, d'altra parte, la tua massa è scalabile o che la massa in una posizione sconosciuta può essere interpolata dai punti circostanti, tenderei a triangulate e contorna i dati di input e usa le aree tra i contorni per trovare cluster di massa simile.

Answer 4

Sembra una quantizzazione del colore, in cui riduci il numero di colori in un'immagine. Un modo sarebbe quello di tracciare i colori nello spazio e combinare i cluster al centro (o una media ponderata) di un cluster.

Il nome esatto dell'algoritmo che ha attivato questa memoria non mi riesce, ma modificherò la risposta se si apre, ma nel frattempo, dovresti guardare la quantizzazione del colore e vedere se alcuni degli algoritmi sono utili.

Answer 5

Inizia con il " Scafo convesso " problema. Stai anche cercando alcuni cluster simili a "scafo convesso".

Tieni presente che "i cluster" sono quotati è vago. Hai una massa media nel tuo campo. Alcuni punti hanno una massa sopra la media e altri sotto la media. Quanto sopra la media significa che hai trovato un cluster? Quanto distanti devono essere i nodi per far parte di un cluster o di un cluster separato?

Qual è la differenza tra due picchi di montagna e una cresta?

Devi calcolare una "topografia" - unendo tutti i punti con uguale densità in regioni. Ciò richiede che tu scelga un punto e risolva il tuo desiderio da un punto radialmente, individuando posizioni in cui le densità sono uguali. Puoi collegare quei punti in regioni.

Se hai scelto il punto iniziale con saggezza, le regioni dovrebbero annidarsi. Scegliere il tuo punto di partenza è facile perché inizi dai massimi locali.

Answer 6

Dato che stai già parlando di massa, perché non una soluzione basata sulla gravità. Un semplice sistema di particelle non avrebbe bisogno di essere estremamente preciso e non dovresti farlo funzionare troppo a lungo prima di poter fare un'ipotesi molto migliore sul numero di cluster.

Se hai un'idea migliore dei numeri dei cluster, k-significa che il vicino più vicino diventa possibile.