Gruppo n punti in k gruppi di uguali dimensioni

Question

Eventuali duplicati:
K-means algorithm variation with equal cluster size

EDIT: come casperOne punto a me questa domanda è un duplicato. Comunque ecco una domanda più generalizzata che copre questa: https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points

miei requisiti

In un progetto devo gruppo n punti (x, y) in k cluster di uguali dimensioni (n/k) . Dove xey sono numeri a virgola mobile, n può variare da 100 a 10000 e k può variare da 2 a 100. Anche k è noto prima dell'esecuzione dell'algoritmo.

mie sperimentazioni

ho iniziato a risolvere il problema utilizzando il http://en.wikipedia.org/wiki/K-means_clustering algoritmo, che funzionano molto bene e veloce per produrre esattamente k cluster di circa la stessa dimensione.

Ma il mio problema è questo, K-significa produrre gruppi di dimensioni approssimativamente uguali, dove ho bisogno che i cluster abbiano esattamente le stesse dimensioni (o per essere più precisi: ho bisogno che abbiano una dimensione tra il pavimento (n/k) e ceil (n/k)).

Prima di indicarmelo, sì ho provato la prima risposta qui K-means algorithm variation with equal cluster size, che suona come una buona idea.

L'idea principale è di elaborare l'array di prodotti cluster mediante K-means. Dal cluster più grande fino al più piccolo. Riduciamo le dimensioni dei cluster che hanno più di n/k membri spostando punti extra su un altro cluster più vicino. Lasciando da solo i cluster che sono già ridotti.

ecco il codice pseudo ho implementato:

n is the number of point 
k is the number of cluster 
m = n/k (the ideal cluster size) 
c is the array of cluster after K-means 
c' = c sorted by size in descending order 
for each cluster i in c' where i = 1 to k - 1 
    n = size of cluster i - m (the number of point to move) 
    loop n times 
     find a point p in cluster i with minimal distance to a cluster j in c' where j > i 
     move point p from cluster i to cluster j 
    end loop 
    recalculate centroids 
end for each 

Il problema di questo algoritmo è che verso la fine del processo (quando vengo vicino a k), dobbiamo scegliere un j cluster c '(dove j> i perché abbiamo bisogno di lasciare da solo i cluster già elaborati), ma questo cluster j che abbiamo trovato può essere lontano dal cluster i, rompendo così il concetto di cluster.

La mia domanda

C'è un post-K significa algoritmo o un K-medie variante in grado di soddisfare le mie esigenze, o mi sbaglio fin dall'inizio e ho bisogno di trovare un altro algoritmo di clustering?

PS: Non mi interessa implementare la soluzione da solo, ma sarebbe fantastico se potessi utilizzare una libreria e idealmente in JAVA.

Answer 1

Non essendo un esperto dell'argomento, una volta avevo bisogno di elaborare un semplice algoritmo per raggruppare le posizioni su una mappa, in cui ogni punto doveva essere parte di un cluster ei cluster erano vincolati in diversi modi (non solo in termini di dimensioni (ovvero conteggio dei punti), ma anche in alcune altre misure che dipendevano da vari fattori).

Prima di trovare i punti "difficili" e quindi i cluster in crescita da lì, ho ottenuto i migliori risultati. i punti "difficili" sarebbero punti difficili da raggiungere, ad es.perché si troverebbero soli nella periferia dell'area totale, o perché contribuirebbero a colpire un'altra condizione al contorno del cluster più di altri punti. Ciò ha contribuito a far crescere ordinatamente i cluster, lasciando pochissimi solitari e il lavoro manuale corrispondente per collocarli.

Questo può essere d'aiuto se l'algoritmo attuale dovesse trovare normalmente questi punti difficili.

Answer 2

Prova questa Kmeans variante:

inizializzazione:

• scegliere k centri dal set di dati in modo casuale, o meglio ancora usando Kmeans ++ strategia
• per ogni punto, calcolare la distanza al centro di cluster più vicino e creare un heap per questo
• disegnare i punti dall'heap e assegnarli al cluster più vicino, a meno che il cluster non sia già overfull. In tal caso, calcola il prossimo centro di cluster più vicino e reinserisci nell'heap

Alla fine, dovresti avere una partizione che soddisfi i tuoi requisiti del + -1 stesso numero di oggetti per cluster (assicurati che gli ultimi anche i cluster hanno il numero corretto. I primi cluster m devono avere gli oggetti ceil, il resto esattamente gli oggetti floor. Si noti che l'utilizzo di un heap garantisce che i cluster rimangano convessi: se non fossero più convessi, ci sarebbe stato un candidato di scambio migliore .

Iterazione passo:

Requisiti: una lista per ogni cluster con "proposte swap" (oggetti che preferirebbe essere in un cluster diverso).

E passo: calcolare i centri dei cluster aggiornati come regolari k-means

M passo: iterazione attraverso tutti i punti (o solo uno, o tutte in un unico lotto)

Calcola vicina centro di cluster su oggetto/tutti i centri di cluster più vicini rispetto ai cluster attuali. Se si tratta di un cluster diverso:

• Se l'altro cluster è più piccolo del cluster corrente, basta spostare al nuovo cluster
• Se c'è una proposta di scambio dall'altro grappolo (o qualsiasi cluster con un distanza inferiore), scambiare le due assegnazioni elemento a grappolo (se c'è più di una sola offerta, scegliere quello con il più grande miglioramento)
• in caso contrario, indicare una proposta di swap per l'altro gruppo rimangono

le dimensioni di cluster invariante (+ - la differenza tra ceil/pavimento), sono gli oggetti si è spostato da un cluster all'altro purché si ottenga un miglioramento della stima. Dovrebbe quindi convergere ad un certo punto come k-means. Potrebbe essere un po 'più lento (vale a dire più iterazioni) però.

Non so se questo è stato pubblicato o implementato prima. È proprio quello che vorrei provare (se provassi k-means, ci sono algoritmi di clustering molto migliori.)