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

Tengo algunos puntos en , y quiero agrupar los puntos para que:$X=\{x_1,...,x_n\}$$R^p$

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

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?

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.

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

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

Sugiero el reciente artículo Discriminative Clustering by Regularized Information Maximization (y referencias en él). Específicamente, la Sección 2 habla sobre el equilibrio de clase y el supuesto de agrupación.

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)