algorithm - algoritmo - k means python example

Variación del algoritmo K-means con igual tamaño de cluster

Question

Estoy buscando el algoritmo más rápido para agrupar puntos en un mapa en grupos de igual tamaño, por distancia. El algoritmo de clustering k-means se ve directo y prometedor, pero no produce grupos de igual tamaño.

¿Hay una variación de este algoritmo o una diferente que permita un conteo igual de miembros para todos los clusters?

Ver también: Agrupe n puntos en k grupos de igual tamaño

Answer 1

Agregado enero de 2012: Mejor que el posprocesamiento sería mantener los tamaños de los clústeres más o menos iguales a medida que crecen.
Por ejemplo, busque para cada X los 3 centros más cercanos, luego agregue X a la que tenga la mejor distancia - λ clustersize.

Un simple postproceso codicioso después de k-means puede ser lo suficientemente bueno, si sus clusters de k-means son aproximadamente del mismo tamaño.
(Esto se aproxima a un algoritmo de asignación en la matriz de distancia Npt x C de k-means).

Uno podría iterar

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)]
...

Me sorprendería si las iteraciones cambiaran mucho los centros, pero eso dependerá de ™.

¿Qué tan grande son tus Npoint Ncluster y 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
            e.g. 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

Answer 2

Considere alguna forma de combinación codiciosa recursiva: cada punto comienza como un clúster de singleton y fusiona repetidamente los dos más cercanos de forma tal que dicha fusión no exceda el máximo. tamaño. Si no le queda más remedio que exceder el tamaño máximo, entonces localmente recluster. Esta es una forma de clustering jerárquico de retroceso: http://en.wikipedia.org/wiki/Hierarchical_clustering

Answer 3

Desea echar un vistazo a la curva de relleno de espacio, por ejemplo, una curva z o una curva hilbert. Pienso en una curva de relleno de espacio para reducir el problema bidimensional a un problema unidimensional. Aunque el índice sfc es solo un reordenamiento de los datos bidimensionales y no un agrupamiento perfecto de los datos, puede ser útil cuando la solución no ha satisfecho un clúster perfecto y debe calcularse bastante rápido.

Answer 4

Después de leer esta pregunta y varias similares, creé una implementación de Python de los k-means del mismo tamaño usando el tutorial de Elki en https://elki-project.github.io/tutorial/same-size_k_means que utiliza el K de scikit-learn -Mecanismo de implementación para la mayoría de los métodos comunes y API familiar.

Mi implementación se encuentra aquí: https://github.com/ndanielsen/Same-Size-K-Means

La lógica de agrupamiento se encuentra en esta función: _labels_inertia_precompute_dense()

Answer 5

El marco de minería de datos ELKI tiene un tutorial sobre k-medias de igual tamaño .

Este no es un algoritmo particularmente bueno, pero es una variación de k-means bastante fácil para escribir un tutorial y enseñarle a las personas cómo implementar su propia variación de algoritmo de clúster; y aparentemente algunas personas realmente necesitan que sus grupos tengan el mismo tamaño, aunque la calidad del SSQ será peor que con los k-means normales.

Answer 6

En general, agrupar puntos en un mapa en grupos de igual tamaño, por distancia, es una misión imposible en teoría. Debido a que la agrupación de puntos en grupos de igual tamaño está en conflicto con los puntos de agrupamiento en grupos por distancia.

ver esta trama:

Hay cuatro puntos:

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

Si agrupamos estos puntos en dos grupos. Obviamente, (A, B, C) será el grupo 1, D será el grupo 2. Pero si necesitamos grupos de igual tamaño, (A, B) será un grupo, (C, D) será el otro. Esto infringe las reglas del clúster porque C está más cerca del centro de (A, B) pero pertenece al clúster (C, D). Por lo tanto, el requisito de clúster y grupos de igual tamaño no se puede satisfacer al mismo tiempo.

Answer 7

Esto podría hacer el truco: aplicar el algoritmo de Lloyd para obtener k centroides. Clasifique los centroides por el tamaño descendente de sus clústeres asociados en una matriz. Para i = 1 a k -1, empuje los puntos de datos en el cluster i con una distancia mínima a cualquier otro centroide j ( i < j ≤ k ) off a j y vuelva a calcular el centroide i (pero no recalcule el clúster) hasta que el el tamaño del clúster es n / k .

La complejidad de este paso de posprocesamiento es O ( k ² n lg n ).

Answer 8

Hay un postprocesamiento más limpio, dado centroides de clúster. Deje N ser el número de elementos, K el número de clústeres y S = ceil(N/K) tamaño máximo de clúster.

• Crea una lista de tuplas (item_id, cluster_id, distance)
• Ordenar tuplas con respecto a la distancia
• Para cada elemento (item_id, cluster_id, distance) en la lista ordenada de tuplas:
  • si el número de elementos en cluster_id excede S no haga nada
  • de lo contrario, agregue item_id al clúster cluster_id .

Esto se ejecuta en O (NK lg (N)), debería dar resultados comparables a la solución de @larsmans y es más fácil de implementar. En pseudo-pitón

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

Answer 9

He estado luchando sobre cómo resolver esta pregunta también. Sin embargo, me doy cuenta de que he usado la palabra clave incorrecta todo este tiempo. Si desea que el número de miembros del resultado del punto sea del mismo tamaño, estará agrupando, ya no agrupando. Finalmente pude resolver el problema usando una simple secuencia de comandos python y postgis.

Por ejemplo, tengo una tabla llamada tb_points que tiene 4000 puntos de coordenadas, y desea dividirla en 10 grupos del mismo tamaño, que contendrán 400 puntos de coordenadas cada uno. Aquí está el ejemplo de la estructura de la tabla

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

Entonces, lo que debes hacer es:

1. Encuentra la primera coordenada que será tu punto de partida
2. Encuentre la coordenada más cercana desde su punto de partida, ordene por distancia ascendente, limite el resultado por el número de su miembro preferido (en este caso 400)
3. Actualice el resultado actualizando la columna group_id
4. Haga 3 pasos por encima de 10 veces para el resto de los datos, cuya columna group_id todavía es NULL

Esta es la implementación en 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()

Espero eso ayude

Answer 10

Pruebe esta variación k-means:

Inicialización :

• elige k centros del conjunto de datos al azar, o incluso mejor usando la estrategia kmeans ++
• para cada punto, calcule la distancia a su centro de clúster más cercano y construya un montón para esto
• extraer puntos del montón y asignarlos al clúster más cercano, a menos que el clúster ya esté saturado. Si es así, calcule el siguiente centro de clúster más cercano y vuelva a insertarlo en el montón

Al final, debe tener una parición que satisfaga sus requisitos de +1 el mismo número de objetos por clúster (asegúrese de que los últimos clústeres también tengan el número correcto. Los primeros m racimos deben tener objetos ceil , el resto exactamente floor objetos.)

Paso de iteración :

Requisitos: una lista para cada grupo con "propuestas de intercambio" (objetos que preferirían estar en un grupo diferente).

E paso: calcular los centros de clúster actualizados como en k-means regulares

M paso: iterar a través de todos los puntos (ya sea uno solo o todo en un lote)

Calcule el centro de clúster más cercano al objeto / todos los centros de clúster que estén más cerca que los clústeres actuales. Si es un clúster diferente:

• Si el otro clúster es más pequeño que el clúster actual, simplemente muévalo al nuevo clúster
• Si hay una propuesta de intercambio del otro clúster (o cualquier clúster con una distancia inferior), cambie las asignaciones de clúster de dos elementos (si hay más de una oferta, elija la que tenga la mejora más grande)
• de lo contrario, indique una propuesta de canje para el otro grupo

Los tamaños de los conglomerados permanecen invariables (+ - la diferencia ceil / piso), y los objetos solo se mueven de un clúster a otro siempre que produzca una mejora de la estimación. Por lo tanto, debería converger en algún punto como k-means. Sin embargo, podría ser un poco más lento (es decir, más iteraciones).

No sé si esto se ha publicado o implementado antes. Es lo que probaría (si intentara k-means. Hay algoritmos de agrupamiento mucho mejores).

Answer 11

Puede ver las distancias como definiendo un gráfico ponderado. Bastantes algoritmos de partición de gráficos se basan explícitamente en intentar dividir los vértices de los gráficos en dos conjuntos de igual tamaño. Esto aparece, por ejemplo, en el algoritmo de Kernighan-Lin y en la partición del gráfico espectral utilizando el Laplaciano. Para obtener varios clústeres, puede aplicar recursivamente el algoritmo de partición; hay una buena discusión de esto en el enlace sobre particionamiento gráfico espectral.

Answer 12

Puedo humildemente sugerirle que pruebe este proyecto ekmeans .

Una implementación de K-means Clustering de Java con una opción especial opcional igual que aplica una restricción de cardinalidad igual en los clusters sin dejar de ser lo más cohesiva posible.

Todavía es experimental, así que ten en cuenta los errores conocidos .

Answer 13

Recientemente necesité esto para un conjunto de datos no muy grande. Mi respuesta, aunque tiene un tiempo de ejecución relativamente largo, está garantizado para converger a un óptimo local.

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)

Answer 14

También observe el árbol Kd que divide los datos hasta que los miembros de cada partición sean menores que BUCKET_SIZE, que es una entrada al algoritmo.

Esto no obliga a los cubos / particiones a ser exactamente del mismo tamaño, pero todos serán menores que BUCKET_SIZE.