Raggruppamento di coordinate intere da 2d in serie di N al massimo

Question

Ho un numero di punti su una griglia bidimensionale relativamente piccola, che si avvolge in entrambe le dimensioni. Le coordinate possono essere solo numeri interi. Ho bisogno di dividerli in gruppi di N punti al massimo vicini, dove N sarà un bel po 'tagliato, sospetto che al massimo 10.

Sto progettando un'intelligenza artificiale per un gioco, e sono sicuro al 99% che usare minimix su tutti i pezzi del gioco mi darà un aspetto utilizzabile di circa 1 mossa, se è così. Comunque i pezzi di gioco distanti non dovrebbero influenzarsi a vicenda fino a quando non guardiamo avanti da un numero elevato di mosse, quindi voglio dividere il gioco in un numero di sotto-giochi di N pezzi alla volta. Tuttavia, ho bisogno di assicurarmi di selezionare un ragionevole N pezzi alla volta, cioè quelli che sono vicini tra loro.

Non mi interessa se i valori anomali vengono lasciati soli o raggruppati con il cluster meno distante. Rompere i gruppi naturali più grandi di N è inevitabile, e deve solo essere abbastanza ragionevole. Poiché viene utilizzato in un AI di gioco con un tempo di risposta limitato, sto cercando un algoritmo il più veloce possibile e disposto a scambiare la precisione per le prestazioni.

Qualcuno ha qualche suggerimento per gli algoritmi di guardare all'adattamento? K-means e parenti non sembrano appropriati, dato che non so quanti cluster voglio trovare ma ho un limite su quanto grandi cluster voglio. Ho visto alcune prove che l'approssimazione di una soluzione mediante l'aggancio di punti a una griglia può aiutare alcuni algoritmi di clustering, quindi spero che le coordinate intere rendano il problema più semplice. Il clustering gerarchico basato sulla distanza sarà facile da adattare alle coordinate del wrap-around, in quanto inserisco semplicemente una funzione di distanza diversa e anche relativamente facile da limitare la dimensione dei cluster. Ci sono altre idee che dovrei guardare?

Sono più interessato agli algoritmi che alle librerie, anche se le biblioteche con una buona documentazione di come funzionano sarebbero benvenute.

EDIT: Originariamente ho posto questa domanda mentre stavo lavorando su una voce per lo Fall 2011 AI Challenge, che purtroppo non ho mai finito. La pagina a cui mi sono collegato ha una descrizione ragionevolmente breve e di alto livello del gioco.

I due punti chiave sono:

1. Ogni giocatore ha un numero potenzialmente elevato di formiche
2. Ogni formica è dato ordini di ogni turno, spostando 1 quadrato o nord, sud, est o ovest; questo significa che il fattore di ramificazione del gioco è O (4 ^formiche).

Nel concorso c'erano anche rigidi limiti di tempo per ogni turno del robot. Avevo pensato di avvicinarmi al gioco usando minimax (i turni sono davvero simultanei, ma come euristica pensavo che sarebbe andato tutto bene), ma temevo che non ci sarebbe stato il tempo di guardare avanti molte mosse se considerassi l'intero gioco subito. Ma siccome ogni form si muove di un solo quadrato per turno, due formiche non possono N spazi separati per la via più breve che possono interferire tra loro fino a quando non guardiamo avanti N/2 mosse.

Quindi la soluzione che stavo cercando era un buon modo per selezionare gruppi più piccoli di formiche alla volta e minimax ogni gruppo separatamente. Speravo che questo mi avrebbe permesso di cercare più in profondità nell'albero di spostamento senza perdere molta precisione. Ma ovviamente non ha senso usare un algoritmo di clustering molto costoso come un'euristica che fa risparmiare tempo!

Sono ancora interessato alla risposta a questa domanda, anche se più in quello che posso imparare dalle tecniche che in questa particolare competizione, dato che è finita!Grazie per tutte le risposte finora.

Answer 1

costruzione di un grafico G = (V , E) sopra la griglia e partizionarlo. Dal momento che siete interessati ad algoritmi piuttosto che le biblioteche, ecco un articolo recente:

Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, e Renato F. Werneck. Partizionamento grafico con tagli naturali. In 25 ° Simposio internazionale di elaborazione parallela e distribuita (IPDPS'11). IEEE Computer Society, 2011. [PDF]

Dal testo:

L'obiettivo del problema grafico di partizionamento è quello di trovare una partizione di minimo costo P in modo tale che le dimensioni di ogni cella è delimitata da U.

Così si imposta U = 10.

Answer 2

L'algoritmo di riduzione mediana è molto semplice da implementare in 2D e funzionerebbe bene qui. I tuoi valori anomali finirebbero come gruppi di 1 che potresti scartare o qualsiasi altra cosa.

Ulteriori spiegazioni richieste: Il taglio mediano è un algoritmo di quantizzazione ma tutti gli algoritmi di quantizzazione sono algoritmi di clustering di casi particolari. In questo caso l'algoritmo è estremamente semplice: trova il riquadro di delimitazione più piccolo contenente tutti i punti, dividi il riquadro lungo il suo lato più lungo (e restringilo per adattarlo ai punti), ripeti fino a raggiungere il numero di caselle desiderato.

A more detailed description and coded example

Wiki on color quantization has some good visuals and links

Answer 3

Si può calcolare un albero di copertura minimo e rimuovere i bordi più lunghi. Quindi puoi calcolare i k-means. Rimuovi un altro lato lungo e calcola i k-medie. Risciacquare e ripetere fino ad avere N = 10. Credo che questo algoritmo sia chiamato single-link k-means e il cluster sia simile ai diagrammi di voronoi:

"L'algoritmo di k-clustering a collegamento singolo ... è esattamente l'algoritmo di Kruskal ... equivalente a trovare un MST e cancellando i bordi più costosi di k-1. "

Vedi per esempio qui: https://stats.stackexchange.com/questions/1475/visualization-software-for-clustering

Answer 4

Dal momento che si sta scrivendo un gioco in cui (presumo) solo un numero costante di pezzi si muovono tra ogni clusering, è possibile usufruire di un algoritmo di online per ottenere l'aggiornamento consant volte.

La proprietà di non bloccarsi a un numero di cluster si chiama Non stazionario, credo.

Questo documento contiene un buon algoritmo con entrambe le due proprietà precedenti: Improving the Robustness of 'Online Agglomerative Clustering Method' Based on Kernel-Induce Distance Measures (Potrebbe essere possibile trovarlo anche altrove).

Ecco a nice video showing l'algoritmo in opere:

Answer 5

Si consideri il caso in cui si desideri solo due cluster. Se esegui k-means, otterrai due punti e la divisione tra i due cluster è un piano ortogonale alla linea tra i centri dei due cluster. Puoi scoprire a quale gruppo si trova un punto proiettandolo sulla linea e poi confrontando la sua posizione sulla linea con una soglia (es. Prendi il prodotto punto tra la linea e un vettore da uno dei due centri del cluster e il punto).

Per due cluster, ciò significa che è possibile regolare le dimensioni dei cluster spostando la soglia. È possibile ordinare i punti sulla loro distanza lungo la linea che collega i due centri del cluster e quindi spostare la soglia lungo la linea abbastanza facilmente, eliminando la disuguaglianza della divisione con quanto siano ordinati i cluster.

Probabilmente non si dispone di k = 2, ma è possibile eseguirlo gerarchicamente, dividendo in due cluster e quindi suddividendo i cluster.

(dopo il commento)

Io non sono bravo con le immagini, ma qui è una certa algebra rilevante.

Con k-means dividiamo punti secondo la loro distanza dai centri di cluster, quindi per un punto Xi e due centri Ai e Bi potremmo essere interessati a

sum_i (Xi - Ai)^2 - sum_i (Xi - Bi)^2

Questo è sum_i ai^2 - sum_i Bi^2 + 2 sum_i (Bi - ai) Xi

Quindi, un punto viene assegnato a uno gruppo a seconda del segno di K + 2 (B - A) .X - una costante più il prodotto punto tra il vettore al punto e il vettore che unisce i due cerchi del cluster. In due dimensioni, la linea divisoria tra i punti sul piano che finiscono in un cluster e i punti sul piano che finiscono nell'altro cluster è una linea perpendicolare alla linea tra i due centri del cluster. Quello che sto suggerendo è che, per controllare il numero di punti dopo la divisione, calcoli (B - A) .X per ogni punto X e poi scegli una soglia che divide tutti i punti in un cluster da tutti i punti nell'altro grappolo. Ciò equivale a far scorrere la linea di divisione su o giù per la linea tra i due centri del cluster, mantenendola perpendicolare alla linea tra di essi.

Una volta che si hanno i prodotti punto Yi, dove Yi = SUM_j (Bj - Aj) Xij, una misura di quanto è raggruppato un cluster è SUM_i (Yi - Ym)^2, dove Ym è la media dello Yi in il cluster. Sto suggerendo di utilizzare la somma di questi valori per i due cluster per capire quanto è buona una divisione. Per spostare un punto dentro o fuori un cluster e ottenere la nuova somma di quadrati senza ricalcolare tutto da zero, nota che SUM_i (Si + T)^2 = SUM_i Si^2 + 2T SUM_i Si + T^2, quindi se tu tieni traccia delle somme e delle somme dei quadrati puoi calcolare cosa succede a una somma di quadrati quando aggiungi o sottrai un valore a ogni componente, poiché la media del cluster cambia quando aggiungi o rimuovi un punto.