K-significa variazione dell’algoritmo con uguale dimensione del cluster

Sto cercando l’algoritmo più veloce per raggruppare i punti su una mappa in gruppi di dimensioni uguali, per distanza. L’ algoritmo di cluster k-means appare semplice e promettente, ma non produce gruppi di dimensioni uguali.

Esiste una variazione di questo algoritmo o un’altra che consente un conteggio uguale dei membri per tutti i cluster?

Vedi anche: Raggruppa i punti in k gruppi di uguali dimensioni

Questo potrebbe fare il trucco: applicare l’algoritmo di Lloyd per ottenere i centroidi k . Ordinare i centroidi discendendo le dimensioni dei cluster associati in un array. Per i = 1 fino a k -1, spingere i punti dati nel cluster i con distanza minima da qualsiasi altro centroide j ( i < jk ) off a j e ricalcolare il centroide i (ma non ricalcolare il cluster) fino a quando il la dimensione del cluster è n / k .

La complessità di questo passo di postprocessing è O ( k ² n lg n ).

È ansible visualizzare le distanze come definizione di un grafico ponderato. Parecchi algoritmi di partizionamento grafico sono esplicitamente basati sul tentativo di partizionare i vertici del grafico in due gruppi di dimensioni uguali. Questo appare, per esempio, nell’algoritmo di Kernighan-Lin e nel partizionamento del grafico spettrale usando il Laplaciano. Per ottenere più cluster, è ansible ricorrere in modo ricorsivo all’algoritmo di partizionamento; c’è una bella discussione al link sul partizionamento del grafico spettrale.

Il framework di data mining ELKI ha un tutorial su k-means di dimensioni uguali .

Questo non è un algoritmo particolarmente buono, ma è una variante di k-means abbastanza facile da scrivere un tutorial per insegnare alle persone come implementare la propria variazione dell’algoritmo di clustering; e apparentemente alcune persone hanno davvero bisogno che i loro cluster abbiano le stesse dimensioni, anche se la qualità SSQ sarà peggiore rispetto ai normali k-means.

Prova questa variazione di k-means:

Inizializzazione :

  • scegli k centri dal set di dati a caso, o ancora meglio usando la strategia kmeans ++
  • per ogni punto, calcolare la distanza dal centro del cluster più vicino e creare un heap per questo
  • disegnare punti dall’heap e assegnarli al cluster più vicino, a meno che il cluster non sia già pieno di risorse. In tal caso, calcolare il centro cluster successivo più vicino e reinserire nell’heap

Alla fine, dovresti avere una partizione che soddisfi i tuoi requisiti del + -1 stesso numero di oggetti per cluster (assicurati che anche gli ultimi cluster abbiano il numero giusto. I primi m cluster dovrebbero avere oggetti ceil , il resto esattamente floor oggetti.)

Fase di iterazione :

Requisiti: una lista per ogni cluster con “proposte di scambio” (oggetti che preferirebbero essere in un cluster diverso).

E step: calcola i centri di cluster aggiornati come nei normali k-means

M step: Iterating attraverso tutti i punti (uno solo o tutto in un lotto)

Calcola il centro del cluster più vicino all’object / tutti i centri del cluster più vicini rispetto ai cluster attuali. Se è un cluster diverso:

  • Se l’altro cluster è più piccolo del cluster corrente, spostalo nel nuovo cluster
  • Se è presente una proposta di scambio dall’altro cluster (o qualsiasi cluster con una distanza inferiore), scambiare le assegnazioni dei due elementi cluster (se è presente più di un’offerta, scegliere quella con il miglioramento maggiore)
  • in caso contrario, indicare una proposta di scambio per l’altro cluster

Le dimensioni dei cluster rimangono invarianti (+ – la differenza tra ceil / pavimento), gli oggetti vengono spostati 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 (cioè più iterazioni) però.

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

Considera una qualche forma di fusione grezza ricorsiva: ogni punto inizia come un cluster singleton e unisce ripetutamente i due più vicini in modo tale che tale unione non superi il massimo. dimensione. Se non hai altra scelta se non quella di superare la dimensione massima, allora il reclutatore locale. Questa è una forma di raggruppamento gerarchico di backtracking: http://en.wikipedia.org/wiki/Hierarchical_clustering

Dopo aver letto questa domanda e molti altri simili, ho creato un’implementazione python di k-medie della stessa dimensione usando il tutorial di Elki su https://elki-project.github.io/tutorial/same-size_k_means che utilizza scikit-learn’s K -Piega l’implementazione per la maggior parte dei metodi comuni e delle API familiari.

La mia implementazione si trova qui: https://github.com/ndanielsen/Same-Size-K-Means

La logica di clustering si trova in questa funzione: _labels_inertia_precompute_dense()

Aggiunto gen 2012: Meglio della poscanvasborazione sarebbe mantenere le dimensioni dei cluster all’incirca come crescono.
Ad esempio, trova per ogni X i 3 centri più vicini, quindi aggiungi X a quello con la distanza migliore – λ clustersize.


Un semplice postprocesso avido dopo k-means può essere abbastanza buono, se i tuoi cluster da k-means sono grosso modo uguali.
(Questo approssima un algoritmo di assegnazione sulla matrice di distanze Npt x C da k-means.)

Uno potrebbe iterare

 diffsizecentres = kmeans( X, centres, ... ) X_centre_distances = scipy.spatial.distance.cdist( X, diffsizecentres ) # or just the nearest few centres xtoc = samesizeclusters( X_centre_distances ) samesizecentres = [X[xtoc[c]].mean(axis=0) for c in range(k)] ... 

Sarei sorpreso se le iterazioni cambiassero molto i centri, ma dipenderà ™.

Quanto sono grandi il tuo Npoint Ncluster e Ndim?

 #!/usr/bin/env python from __future__ import division from operator import itemgetter import numpy as np __date__ = "2011-03-28 Mar denis" def samesizecluster( D ): """ in: point-to-cluster-centre distances D, Npt x C eg from scipy.spatial.distance.cdist out: xtoc, X -> C, equal-size clusters method: sort all D, greedy """ # could take only the nearest few x-to-C distances # add constraints to real assignment algorithm ? Npt, C = D.shape clustersize = (Npt + C - 1) // C xcd = list( np.ndenumerate(D) ) # ((0,0), d00), ((0,1), d01) ... xcd.sort( key=itemgetter(1) ) xtoc = np.ones( Npt, int ) * -1 nincluster = np.zeros( C, int ) nall = 0 for (x,c), d in xcd: if xtoc[x] < 0 and nincluster[c] < clustersize: xtoc[x] = c nincluster[c] += 1 nall += 1 if nall >= Npt: break return xtoc #............................................................................... if __name__ == "__main__": import random import sys from scipy.spatial import distance # http://docs.scipy.org/doc/scipy/reference/spatial.distance.html Npt = 100 C = 3 dim = 3 seed = 1 exec( "\n".join( sys.argv[1:] )) # run this.py N= ... np.set_printoptions( 2, threshold=200, edgeitems=5, suppress=True ) # .2f random.seed(seed) np.random.seed(seed) X = np.random.uniform( size=(Npt,dim) ) centres = random.sample( X, C ) D = distance.cdist( X, centres ) xtoc = samesizecluster( D ) print "samesizecluster sizes:", np.bincount(xtoc) # Npt=100 C=3 -> 32 34 34 

Recentemente ho avuto bisogno di questo me stesso per un dataset non molto grande. La mia risposta, sebbene abbia un tempo di esecuzione relativamente lungo, è garantita la convergenza verso un optimum locale.

 def eqsc(X, K=None, G=None): "equal-size clustering based on data exchanges between pairs of clusters" from scipy.spatial.distance import pdist, squareform from matplotlib import pyplot as plt from matplotlib import animation as ani from matplotlib.patches import Polygon from matplotlib.collections import PatchCollection def error(K, m, D): """return average distances between data in one cluster, averaged over all clusters""" E = 0 for k in range(K): i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k E += numpy.mean(D[numpy.meshgrid(i,i)]) return E / K numpy.random.seed(0) # repeatability N, n = X.shape if G is None and K is not None: G = N // K # group size elif K is None and G is not None: K = N // G # number of clusters else: raise Exception('must specify either K or G') D = squareform(pdist(X)) # distance matrix m = numpy.random.permutation(N) % K # initial membership E = error(K, m, D) # visualization #FFMpegWriter = ani.writers['ffmpeg'] #writer = FFMpegWriter(fps=15) #fig = plt.figure() #with writer.saving(fig, "ec.mp4", 100): t = 1 while True: E_p = E for a in range(N): # systematically for b in range(a): m[a], m[b] = m[b], m[a] # exchange membership E_t = error(K, m, D) if E_t < E: E = E_t print("{}: {}<->{} E={}".format(t, a, b, E)) #plt.clf() #for i in range(N): #plt.text(X[i,0], X[i,1], m[i]) #writer.grab_frame() else: m[a], m[b] = m[b], m[a] # put them back if E_p == E: break t += 1 fig, ax = plt.subplots() patches = [] for k in range(K): i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k x = X[i] patches.append(Polygon(x[:,:2], True)) # how to draw this clock-wise? u = numpy.mean(x, 0) plt.text(u[0], u[1], k) p = PatchCollection(patches, alpha=0.5) ax.add_collection(p) plt.show() if __name__ == "__main__": N, n = 100, 2 X = numpy.random.rand(N, n) eqsc(X, G=3) 

C’è una post-elaborazione più pulita, dati i centroidi del cluster. Sia N il numero di elementi, K il numero di cluster e S = ceil(N/K) dimensione massima del cluster.

  • Creare un elenco di tuple (item_id, cluster_id, distance)
  • Ordina le tuple rispetto alla distanza
  • Per ogni elemento (item_id, cluster_id, distance) nell’elenco di tuple ordinato:
    • se il numero di elementi in cluster_id supera S fare nulla
    • altrimenti aggiungi item_id al cluster cluster_id .

Questo funziona in O (NK lg (N)), dovrebbe dare risultati comparabili alla soluzione @larsmans ed è più facile da implementare. In pseudo-pitone

 dists = [] clusts = [None] * N counts = [0] * K for i, v in enumerate(items): dist = map( lambda x: dist(x, v), centroids ) dd = map( lambda (k, v): (i, k, v), enumerate(dist) ) dists.extend(dd) dists = sorted(dists, key = lambda (x,y,z): z) for (item_id, cluster_id, d) in dists: if counts[cluster_id] >= S: continue if clusts[item_id] == None: clusts[item_id] = cluster_id counts[cluster_id] = counts[cluster_id] + 1 

In generale, raggruppare i punti su una mappa in gruppi di dimensioni uguali, per distanza è una missione imansible in teoria. Perché raggruppare i punti in gruppi di dimensioni uguali è in conflitto con i punti di raggruppamento in cluster per distanza.

vedi questa trama: inserisci la descrizione dell'immagine qui

Ci sono quattro punti:

 A.[1,1] B.[1,2] C.[2,2] D.[5,5] 

Se raggruppiamo questi punti in due cluster. Ovviamente, (A, B, C) sarà il cluster 1, D sarà il cluster 2. Ma se abbiamo bisogno di gruppi di dimensioni uguali, (A, B) sarà un cluster, (C, D) sarà l’altro. Ciò viola le regole del cluster perché C è più vicino al centro di (A, B) ma appartiene al cluster (C, D). Quindi i requisiti di cluster e gruppi di dimensioni uguali non possono essere soddisfatti allo stesso tempo.

Osserva anche l’albero di Kd che partiziona i dati finché i membri di ogni partizione non sono inferiori a un BUCKET_SIZE che è un input dell’algoritmo.

Ciò non impone che i bucket / partizioni abbiano esattamente le stesse dimensioni ma saranno tutti inferiori a BUCKET_SIZE.

Posso umilmente suggerire di provare questo progetto ekmeans .

Un Java K-significa implementazione di Clustering con un’opzione opzionale speciale uguale che applica un vincolo di cardinalità uguale sui cluster pur rimanendo il più ansible spazialmente coesi.

È ancora sperimentale, quindi basta essere consapevoli dei bug conosciuti .

Ho faticato anche su come risolvere questa domanda. Tuttavia, mi rendo conto di aver usato la parola chiave sbagliata per tutto questo tempo. Se si desidera che il numero del membro del risultato del punto sia della stessa dimensione, si sta eseguendo un raggruppamento, non più il clustering. Finalmente sono riuscito a risolvere il problema usando semplici query python e postgis.

Ad esempio, ho una tabella chiamata tb_points che ha 4000 punti di coordinate, e tu vuoi dividerlo in 10 gruppi di stesse dimensioni, che conterranno 400 punti di coordinate ciascuno. Ecco l’esempio della struttura della tabella

 CREATE TABLE tb_points ( id SERIAL PRIMARY KEY, outlet_id INTEGER, longitude FLOAT, latitide FLOAT, group_id INTEGER ); 

Quindi quello che devi fare sono:

  1. Trova le prime coordinate che saranno il tuo punto di partenza
  2. Trova coordinate più vicine dal punto di partenza, ordine per distanza crescente, limita il risultato per il numero del tuo membro preferito (in questo caso 400)
  3. Aggiorna il risultato aggiornando la colonna group_id
  4. Fai 3 passaggi sopra le 10 volte per il resto dei dati, la cui colonna group_id è ancora NULL

Questa è l’implementazione in python:

 import psycopg2 dbhost = '' dbuser = '' dbpass = '' dbname = '' dbport = 5432 conn = psycopg2.connect(host = dbhost, user = dbuser, password = dbpass, database = dbname, port = dbport) def fetch(sql): cursor = conn.cursor() rs = None try: cursor.execute(sql) rs = cursor.fetchall() except psycopg2.Error as e: print(e.pgerror) rs = 'error' cursor.close() return rs def execScalar(sql): cursor = conn.cursor() try: cursor.execute(sql) conn.commit() rowsaffected = cursor.rowcount except psycopg2.Error as e: print(e.pgerror) rowsaffected = -1 conn.rollback() cursor.close() return rowsaffected def select_first_cluster_id(): sql = """ SELECT a.outlet_id as ori_id, a.longitude as ori_lon, a.latitude as ori_lat, b.outlet_id as dest_id, b.longitude as dest_lon, b.latitude as dest_lat, ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) AS geography), CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) AS air_distance FROM tb_points a CROSS JOIN tb_points b WHERE a.outlet_id != b.outlet_id and a.group_id is NULL and b.group_id is null order by air_distance desc limit 1 """ return sql def update_group_id(group_id, ori_id, limit_constraint): sql = """ UPDATE tb_points set group_id = %s where outlet_id in (select b.outlet_id from tb_points a, tb_points b where a.outlet_id = '%s' and a.group_id is null and b.group_id is null order by ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) AS geography), CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) asc limit %s) """ % (group_id, ori_id, limit_constraint) return sql def clustering(): data_constraint = [100] n = 1 while n <= 10: sql = select_first_cluster_id() res = fetch(sql) ori_id = res[0][0] sql = update_group_id(n, ori_id, data_constraint[0]) print(sql) execScalar(sql) n += 1 clustering() 

Spero che sia d'aiuto

Vuoi dare un’occhiata alla curva di riempimento dello spazio, per esempio una curva a z o una curva a stella. Penso ad una curva di riempimento dello spazio per ridurre il problema bidimensionale ad un problema 1-dimensionale. Sebbene l’indice sfc sia solo un riordino dei dati bidimensionali e non un perfetto raggruppamento dei dati, può essere utile quando la soluzione non ha soddisfatto un cluster perfetto e deve essere calcasting abbastanza velocemente.