Procedimiento de agrupamiento donde cada grupo tiene el mismo número de puntos?

25

Tengo algunos puntos en , y quiero agrupar los puntos para que:X={X1,...,Xnorte}Rpags

  1. Cada grupo contiene un número igual de elementos de . (Suponga que el número de grupos divide .)Xnorte

  2. Cada grupo es "espacialmente cohesivo" en algún sentido, como los grupos de significa.k

Es fácil pensar en muchos procedimientos de agrupamiento que satisfacen uno u otro de estos, pero ¿alguien sabe de una manera de obtener ambos a la vez?

No Durrett
fuente
2
¿También se especifica el tamaño del clúster? Entonces, como se dijo, el problema me parece insoluble. Considere el siguiente caso con : . Si desea 2 grupos, obtendrá diferentes tamaños o no "espacialmente cohesivos". ¿O quieres algo como "lo más cohesionado espacialmente posible", minimizando la distancia máxima dentro del cluster o algo así? La otra solución sería permitir cualquier divisor de n como tamaño de clúster, pero siempre está la solución trivial de n clústeres de tamaño 1 . norte=4 4,pags=1X={-1,0,99,1,1.01}nortenorte1
Erik P.
1
Buen punto. Idealmente, me gustaría algo que sea "tan cohesivo espacialmente como sea posible" mientras satisfaga la restricción de cardinalidad igual. Pero me interesaría saber sobre cualquier procedimiento que haga otras compensaciones aquí también, ya que tal vez puedan adaptarse.
No Durrett
¿Sería suficiente dividir los datos por cuantiles? Si los valores no son monótonos entre sí, no veo de qué otra manera podrían ser 'espacialmente cohesivos'.
celenius
44
Ha habido algunas investigaciones recientes sobre agrupamiento restringido. Google google.com/search?q=constrained+k-means .
whuber
Solo una idea no probada. En la agrupación, a menudo se usa una llamada estadística de silueta. Le muestra qué tan bien está agrupado un objeto y cuál es el mejor otro clúster vecino en el que podría inscribirse. Por lo tanto, puede comenzar con K-MEANS u otra clasificación con diferentes grupos n . Luego mueva objetos no muy bien clasificados (de acuerdo con la estadística) a sus mejores grupos vecinos con menor n hasta obtener n igual . Espero iteraciones: mover algunos objetos, recalcular las estadísticas, mover algunos objetos, etc. Ese será un proceso de compensación.
ttnphns

Respuestas:

6

Sugiero un enfoque de dos pasos:

  1. Obtenga una buena estimación inicial de los centros de los conglomerados, por ejemplo, utilizando K-medias difusos o difusos.

  2. Use la asignación de Vecino más cercano global para asociar puntos con centros de clúster: Calcule una matriz de distancia entre cada punto y cada centro de clúster (puede hacer que el problema sea un poco más pequeño calculando solo distancias razonables), replique cada centro de clúster X veces y resuelva el lineal problema de asignación . Obtendrá, para cada centro de clúster, exactamente X coincide con los puntos de datos, de modo que, globalmente, se minimiza la distancia entre los puntos de datos y los centros de clúster.

Tenga en cuenta que puede actualizar los centros de clúster después del paso 2 y repetir el paso 2 para ejecutar básicamente K-means con un número fijo de puntos por clúster. Aún así, será una buena idea obtener una buena suposición inicial primero.

Jonas
fuente
4

Pruebe esta variación k-means:

Inicializacion :

  • elegir kcentros del conjunto de datos al azar, o incluso mejor usando la estrategia kmeans ++
  • para cada punto, calcule la distancia al centro de clúster más cercano y cree un montón para esto
  • dibuje puntos del montón y asígnelos al grupo más cercano, a menos que el grupo ya esté sobrecargado. 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 partición que satisfaga sus requisitos del + -1 mismo número de objetos por grupo (asegúrese de que los últimos grupos también tengan el número correcto. Los primeros mgrupos deben tener ceilobjetos, el resto exactamente floorobjetos).

Paso de iteración :

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

Paso E : calcule los centros de clúster actualizados como en k-means regulares

Paso M : iterando a través de todos los puntos (ya sea solo uno 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 grupo es más pequeño que el grupo actual, simplemente muévalo al nuevo grupo
  • Si hay una propuesta de intercambio del otro clúster (o cualquier clúster con una distancia menor), intercambie las asignaciones de clúster de dos elementos (si hay más de una oferta, elija la que tenga la mayor mejora)
  • de lo contrario, indique una propuesta de intercambio para el otro clúster

Los tamaños de los conglomerados permanecen invariables (+ - la diferencia de techo / piso), los objetos solo se mueven de un conglomerado a otro siempre que resulte en 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 justo lo que intentaría (si intentara k-means. Hay algoritmos de agrupamiento mucho mejores).

Un buen lugar para comenzar podría ser con la implementación de k-means en ELKI , que ya parece admitir tres inicializaciones diferentes (incluyendo k-means ++), y los autores dijeron que también quieren tener diferentes estrategias de iteración, para cubrir todas las diversas variantes de forma modular (por ejemplo, Lloyd, MacQueen, ...).

Anony-Mousse
fuente
2
Se incluye un enfoque similar en ELKI como tutorial y en el módulo de "extensión" del tutorial: elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans
Erich Schubert
3

Este es un problema de optimización. Tenemos una biblioteca Java de código abierto que resuelve este problema (agrupamiento donde la cantidad por grupo debe estar entre los rangos establecidos). Sin embargo, necesitaría que su número total de puntos sea un máximo de unos pocos miles, no más de 5000 o quizás 10000.

La biblioteca está aquí:

https://github.com/PGWelch/territorium/tree/master/territorium.core

La biblioteca en sí está configurada para problemas geográficos / tipo SIG, por lo que verá referencias a X e Ys, latitudes y longitudes, clientes, distancia y tiempo, etc. Sin embargo, puede ignorar los elementos 'geográficos' y usarlo como un puro clusterer

Proporciona un conjunto de grupos de entrada inicialmente vacíos, cada uno con una cantidad objetivo mínima y máxima. El clusterer asignará puntos a sus grupos de entrada, utilizando un algoritmo de optimización basado en heurística (swaps, movimientos, etc.). En la optimización, prioriza en primer lugar mantener cada grupo dentro de su rango de cantidad mínima y máxima y luego minimiza en segundo lugar las distancias entre todos los puntos en el grupo y el punto central del grupo, por lo que un grupo es espacialmente cohesivo.

Usted le da al solucionador una función métrica (es decir, función de distancia) entre puntos usando esta interfaz:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/TravelMatrix.java

La métrica en realidad está estructurada para devolver tanto la distancia como el 'tiempo', porque está diseñada para problemas geográficos basados ​​en viajes, pero para problemas de agrupamiento arbitrario simplemente establece que 'tiempo' sea cero y la distancia sea la métrica real que estás usando entre puntos.

Configuraría su problema en esta clase:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Problem.java

Sus puntos serían los 'Clientes' y su cantidad sería 1. En la clase de cliente, asegúrese de establecer costPerUnitTime = 0 y costPerUnitDistance = 1 suponiendo que devuelve su distancia métrica en el campo 'distancia' devuelta por TravelMatrix.

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Customer.java

Vea aquí un ejemplo de ejecución del solucionador:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/test/java/com/opendoorlogistics/territorium/TestSolver.java

Open Door Logistics
fuente
2

Recientemente, yo mismo necesitaba 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)
Alexander Kain
fuente
1
Gracias por esta contribución, @ user2341646. ¿Le importaría agregar una exposición que explique qué es esta solución, cómo funciona y por qué es una solución?
gung - Restablece a Monica
OKAY. Básicamente, el algoritmo comienza con asignaciones de membresía que son aleatorias, pero hay cerca de miembros G en un clúster, y hay K clústeres en general. Definimos la función de error que mide las distancias promedio entre los datos en un grupo, promediados en todos los grupos. Al revisar sistemáticamente todos los pares de datos, vemos si intercambiar la membresía de esos dos datos da como resultado un error menor. Si es así, actualizamos el error más bajo posible, de lo contrario deshacemos el cambio de membresía. Hacemos esto hasta que no queden más movimientos para un pase completo.
Alexander Kain