Procédure de clustering où chaque cluster a un nombre égal de points?

J'ai quelques points dans R p , et je veux regrouper les points de sorte que:$X=\{x_1,...,x_n\}$$R^p$

1. Chaque cluster contient un nombre égal d'éléments de . (Supposons que le nombre de clusters divise n .)$X$$n$

2. Chaque grappe est "spatialement cohérente" dans un certain sens, comme les grappes de moyens.$k$

Il est facile de penser à de nombreuses procédures de clustering qui satisfont à l'une ou à l'autre, mais quelqu'un connaît-il un moyen d'obtenir les deux à la fois?

Je suggère une approche en deux étapes:

1. obtenir une bonne estimation initiale des centres de cluster, par exemple en utilisant des K-moyennes dures ou floues.

2. Utilisez l'affectation de voisin le plus proche pour associer des points à des centres de cluster: calculez une matrice de distance entre chaque point et chaque centre de cluster (vous pouvez réduire le problème un peu en calculant uniquement des distances raisonnables), répliquer chaque centre de cluster X fois et résoudre le linéaire problème d'affectation . Vous obtiendrez, pour chaque centre de cluster, exactement X correspond aux points de données, de sorte que, globalement, la distance entre les points de données et les centres de cluster est minimisée.

Notez que vous pouvez mettre à jour les centres de cluster après l'étape 2 et répéter l'étape 2 pour exécuter essentiellement K-means avec un nombre fixe de points par cluster. Pourtant, ce sera une bonne idée d'obtenir une bonne estimation initiale en premier.

Essayez cette variation k-means:

Initialisation :

• choisissez des kcentres dans l'ensemble de données au hasard, ou mieux encore en utilisant la stratégie kmeans ++
• pour chaque point, calculez la distance jusqu'au centre de cluster le plus proche et créez un tas pour
• dessinez des points du tas et affectez-les au cluster le plus proche, sauf si le cluster est déjà saturé. Si tel est le cas, calculez le centre de cluster le plus proche et réinsérez-le dans le tas

En fin de compte, vous devriez avoir un partitionnement qui répond à vos exigences du + -1 même nombre d'objets par cluster (assurez-vous que les derniers clusters ont également le bon nombre. Les premiers mclusters doivent avoir des ceilobjets, le reste exactement des floorobjets.)

Étape d'itération :

Prérequis: une liste pour chaque cluster avec des «propositions d'échange» (objets qui préféreraient être dans un cluster différent).

Étape E : calculer les centres de cluster mis à jour comme dans les k-moyennes ordinaires

MÉtape : itération sur tous les points (soit un seul, soit tous en un seul lot)

Calculez le centre de cluster le plus proche de l'objet / tous les centres de cluster qui sont plus proches que les clusters actuels. S'il s'agit d'un cluster différent:

• Si l'autre cluster est plus petit que le cluster actuel, déplacez-le simplement vers le nouveau cluster
• S'il y a une proposition d'échange de l'autre cluster (ou de tout cluster avec une distance inférieure), échangez les affectations de cluster à deux éléments (s'il y a plus d'une offre, choisissez celle qui présente la plus grande amélioration)
• sinon, indiquez une proposition de swap pour l'autre cluster

Les tailles de cluster restent invariantes (+ - la différence plafond / sol), un objet n'est déplacé d'un cluster à un autre que tant qu'il en résulte une amélioration de l'estimation. Il devrait donc converger à un moment comme k-means. Cela pourrait être un peu plus lent (c'est-à-dire plus d'itérations).

Je ne sais pas si cela a été publié ou mis en œuvre auparavant. C'est juste ce que j'essaierais (si j'essayais k-means. Il y a de bien meilleurs algorithmes de clustering.)

Un bon point de départ pourrait être l'implémentation de k-means dans ELKI , qui semble déjà prendre en charge trois initialisations différentes (y compris k-means ++), et les auteurs ont dit qu'ils voulaient également avoir différentes stratégies d'itération, pour couvrir toutes les diverses variantes de façon modulaire (par exemple Lloyd, MacQueen, ...).

Il s'agit d'un problème d'optimisation. Nous avons une bibliothèque java open source qui résout ce problème (clustering où la quantité par cluster doit être comprise entre des plages définies). Vous auriez besoin que votre nombre total de points soit au maximum de quelques milliers - pas plus de 5000 ou peut-être 10000.

La bibliothèque est ici:

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

La bibliothèque elle-même est configurée pour les problèmes de type géographique / SIG - vous verrez donc des références aux X et Y, aux latitudes et longitudes, aux clients, à la distance et au temps, etc. Vous pouvez simplement ignorer les éléments «géographiques» et l'utiliser comme un pur clusterer.

Vous fournissez un ensemble de clusters d'entrée initialement vides, chacun avec une quantité cible min et max. Le clusterer attribuera des points à vos clusters d'entrée, en utilisant un algorithme d'optimisation basé sur l'heuristique (swaps, mouvements, etc.). Dans l'optimisation, il priorise d'abord le maintien de chaque cluster dans sa plage de quantité minimale et maximale, puis minimise ensuite les distances entre tous les points du cluster et le point central du cluster, de sorte qu'un cluster est spatialement cohérent.

Vous donnez au solveur une fonction métrique (c'est-à-dire une fonction de distance) entre les points en utilisant cette interface:

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

La métrique est en fait structurée pour renvoyer à la fois une distance et un `` temps '', car elle est conçue pour des problèmes géographiques basés sur les voyages, mais pour des problèmes de clustering arbitraires, définissez simplement le `` temps '' sur zéro et la distance sur votre métrique réelle que vous utilisez entre points.

Vous devez configurer votre problème dans cette classe:

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

Vos points seraient les «clients» et leur quantité serait 1. Dans la classe de clients, assurez-vous de définir costPerUnitTime = 0 et costPerUnitDistance = 1 en supposant que vous renvoyez votre distance métrique dans le champ «distance» renvoyé par TravelMatrix.

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

Voir ici pour un exemple d'exécution du solveur:

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

Je suggère le récent article Discriminative Clustering by Regularized Information Maximization (et les références qui y figurent). Plus précisément, la section 2 traite de l'équilibre des classes et de l'hypothèse de cluster.

Récemment, j'ai eu besoin de cela moi-même pour un ensemble de données peu volumineux. Ma réponse, bien qu'elle ait un temps de fonctionnement relativement long, est garantie de converger vers un optimum 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)