Clustering-Vorgang, bei dem jeder Cluster die gleiche Anzahl von Punkten hat?

25

Ich habe einige Punkte in und möchte die Punkte so gruppieren, dass:X={x1,...,xn}Rp

  1. Jeder Cluster enthält eine gleiche Anzahl von Elementen von . (Angenommen, die Anzahl der Cluster teilt .)Xn

  2. Jeder Cluster ist in gewissem Sinne "räumlich kohäsiv", wie die Cluster aus Mitteln.k

Es ist leicht, sich eine Menge Clustering-Verfahren vorzustellen, die die eine oder andere dieser Anforderungen erfüllen, aber kennt jemand einen Weg, um beide gleichzeitig zu erreichen?

Nicht Durrett
quelle
2
Wird auch die Clustergröße angegeben? Dann scheint mir das Problem, wie gesagt, unlösbar zu sein. Betrachten Sie den folgenden Fall mit : . Wenn Sie 2 Cluster möchten, erhalten Sie entweder unterschiedliche Größen oder nicht "räumlich zusammenhängend". Oder möchten Sie so etwas wie "so räumlich kohäsiv wie möglich" - den maximalen Abstand zwischen den Clustern minimieren oder so? Die andere Lösung wäre, jeden Divisor von als Clustergröße zuzulassen - aber dann gibt es immer die triviale Lösung von Clustern der Größe . n=4,p=1X={-1,0,99,1,1,01}nn1
Erik P.
1
Guter Punkt. Idealerweise möchte ich etwas, das "so räumlich zusammenhängend wie möglich" ist und gleichzeitig die gleiche Kardinalitätsbedingung erfüllt. Aber ich würde gerne mehr über Verfahren erfahren, die auch andere Kompromisse eingehen, da sie möglicherweise angepasst werden können.
Nicht Durrett
Würde eine Aufteilung der Daten nach Quantilen ausreichen? Wenn die Werte nicht monoton zueinander sind, verstehe ich nicht, wie sie sonst "räumlich zusammenhängend" sein könnten.
Celenius
4
Es wurden kürzlich einige Untersuchungen zu eingeschränktem Clustering durchgeführt. Google google.com/search?q=constrained+k-means .
Whuber
Nur eine nicht getestete Idee. Beim Clustering wird häufig eine sogenannte Silhouette-Statistik verwendet. Es zeigt Ihnen , wie gut ein Objekt gruppiert ist und was ist der beste anderer Nachbar - Cluster in. So eingeschrieben werden könnte, um Sie mit K-Means oder anderer Klassifizierung mit unterschiedlichen Cluster beginnen konnten n ‚s. Dann Objekte bewegen sich nicht sehr gut eingestuft (accorging auf die Statistik) , um ihren besten Nachbarn - Cluster mit weniger n , bis Sie gleich erhalten n . Ich erwarte Iterationen: verschiebe einige Objekte, berechne die Statistik neu, verschiebe einige Objekte usw. Das wird ein Kompromiss sein.
TTNPHNS

Antworten:

6

Ich schlage einen zweistufigen Ansatz vor:

  1. Erhalten Sie eine gute erste Einschätzung der Cluster-Zentren, z. B. mit harten oder unscharfen K-Mitteln.

  2. Verwenden Sie die Zuweisung "Globaler nächster Nachbar", um Punkte mit Clusterzentren zu verknüpfen: Berechnen Sie eine Abstandsmatrix zwischen jedem Punkt und jedem Clusterzentrum (Sie können das Problem ein wenig verkleinern, indem Sie nur angemessene Abstände berechnen), replizieren Sie jedes Clusterzentrum X-mal und lösen Sie die lineare Zuweisungsproblem . Sie erhalten für jedes Clusterzentrum genau X Übereinstimmungen mit Datenpunkten, sodass der Abstand zwischen Datenpunkten und Clusterzentren global minimiert wird.

Beachten Sie, dass Sie Cluster-Zentren nach Schritt 2 aktualisieren und Schritt 2 wiederholen können, um grundsätzlich K-means mit einer festen Anzahl von Punkten pro Cluster auszuführen. Trotzdem ist es eine gute Idee, zuerst eine erste Vermutung anzustellen.

Jonas
quelle
4

Probieren Sie diese k-means Variante:

Initialisierung :

  • Wählen Sie kZentren aus dem Datensatz nach dem Zufallsprinzip oder noch besser mithilfe der Strategie kmeans ++
  • Berechnen Sie für jeden Punkt die Entfernung zum nächstgelegenen Cluster-Zentrum und bauen Sie dafür einen Heap auf
  • Zeichnen Sie Punkte aus dem Heap und weisen Sie sie dem nächsten Cluster zu, es sei denn, der Cluster ist bereits überfüllt. Wenn ja, berechnen Sie das nächstgelegene Cluster-Center und fügen Sie es erneut in den Heap ein

Am Ende sollten Sie eine Partitionierung haben, die Ihren Anforderungen von + -1 der gleichen Anzahl von Objekten pro Cluster entspricht. (Stellen Sie sicher, dass die letzten Cluster auch die richtige Anzahl haben. Die ersten mCluster sollten ceilObjekte haben, der Rest genau floorObjekte.)

Iterationsschritt :

Voraussetzungen: Eine Liste für jeden Cluster mit "Tauschvorschlägen" (Objekte, die sich lieber in einem anderen Cluster befinden würden).

Schritt E : Berechnen Sie die aktualisierten Cluster-Zentren wie in regulären k-Mitteln

M- Schritt: Durchlaufen aller Punkte (entweder nur einer oder alle in einem Stapel)

Berechnen Sie das nächstgelegene Clusterzentrum für Objekte / alle Clusterzentren, die näher an den aktuellen Clustern liegen. Wenn es sich um einen anderen Cluster handelt:

  • Wenn der andere Cluster kleiner als der aktuelle Cluster ist, verschieben Sie ihn einfach in den neuen Cluster
  • Wenn es einen Tauschvorschlag des anderen Clusters (oder eines Clusters mit einer geringeren Entfernung) gibt, tauschen Sie die beiden Elementclusterzuweisungen aus (wenn es mehr als ein Angebot gibt, wählen Sie das mit der größten Verbesserung aus).
  • Andernfalls geben Sie einen Tauschvorschlag für den anderen Cluster an

Die Clustergrößen bleiben unveränderlich (+ - der Decken- / Bodendifferenz), ein Objekt wird nur von einem Cluster zu einem anderen verschoben, solange dies zu einer Verbesserung der Schätzung führt. Es sollte daher irgendwann konvergieren wie k-means. Es könnte allerdings etwas langsamer sein (dh mehr Iterationen).

Ich weiß nicht, ob dies bereits veröffentlicht oder implementiert wurde. Es ist genau das, was ich versuchen würde (wenn ich k-means versuchen würde. Es gibt viel bessere Clustering-Algorithmen.)

Ein guter Ausgangspunkt könnte die Implementierung von k-means in ELKI sein , die anscheinend bereits drei verschiedene Initialisierungen unterstützt (einschließlich k-means ++), und die Autoren sagten, dass sie auch unterschiedliche Iterationsstrategien haben möchten, um alle verschiedenen allgemeinen abzudecken modulare Varianten (z. B. Lloyd, MacQueen, ...).

Anony-Mousse
quelle
2
Ein ähnlicher Ansatz ist in ELKI als Tutorial und im Tutorial-Modul "Erweiterung" enthalten: elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans
Erich Schubert
3

Dies ist ein Optimierungsproblem. Wir haben eine Open-Source-Java-Bibliothek, die dieses Problem löst (Clustering, bei dem die Menge pro Cluster zwischen festgelegten Bereichen liegen muss). Die Gesamtpunktzahl sollte jedoch maximal einige Tausend betragen - nicht mehr als 5000 oder vielleicht 10000.

Die Bibliothek ist hier:

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

Die Bibliothek selbst ist für Probleme mit geografischen / GIS-Typen eingerichtet. Sie sehen also Verweise auf X und Y, Breiten- und Längengrade, Kunden, Entfernung und Zeit usw. Sie können die "geografischen" Elemente jedoch einfach ignorieren und als reine Elemente verwenden Clusterer.

Sie stellen eine Reihe von anfänglich leeren Eingabe-Clustern mit jeweils einer minimalen und einer maximalen Zielmenge bereit. Der Clusterer weist Ihren Eingabe-Clustern mithilfe eines heuristischen Optimierungsalgorithmus (Swaps, Moves usw.) Punkte zu. Bei der Optimierung wird zum einen die Priorität festgelegt, dass jeder Cluster innerhalb seines minimalen und maximalen Mengenbereichs bleibt. Zum anderen werden die Abstände zwischen allen Punkten im Cluster und dem zentralen Punkt des Clusters minimiert, sodass ein Cluster räumlich zusammenhängend ist.

Über diese Schnittstelle geben Sie dem Löser eine metrische Funktion (dh Distanzfunktion) zwischen Punkten:

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

Die Metrik ist so strukturiert, dass sie sowohl eine Entfernung als auch eine "Zeit" zurückgibt, da sie für reisebasierte geografische Probleme entwickelt wurde. Bei beliebigen Clustering-Problemen setzen Sie "Zeit" einfach auf Null und die Entfernung auf die tatsächliche Metrik, die Sie zwischen den beiden verwenden Punkte.

Sie würden Ihr Problem in dieser Klasse einrichten:

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

Ihre Punkte lauten "Kunden" und ihre Anzahl "1". Stellen Sie in der Kundenklasse sicher, dass Sie costPerUnitTime = 0 und costPerUnitDistance = 1 festlegen, vorausgesetzt, Sie geben Ihre metrische Entfernung in das von der TravelMatrix zurückgegebene Feld "Entfernung" ein.

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

Ein Beispiel zum Ausführen des Solvers finden Sie hier:

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

Offene Tür Logistik
quelle
2

Vor kurzem brauchte ich das selbst für einen nicht sehr großen Datensatz. Obwohl meine Antwort eine relativ lange Laufzeit hat, wird sie garantiert zu einem lokalen Optimum konvergieren.

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
quelle
1
Danke für diesen Beitrag, @ user2341646. Würde es Ihnen etwas ausmachen, eine Erklärung hinzuzufügen, die erklärt, was diese Lösung ist, wie sie funktioniert und warum sie eine Lösung ist?
gung - Wiedereinsetzung von Monica
OKAY. Grundsätzlich beginnt der Algorithmus mit zufälligen Zuordnungen von Mitgliedern, aber es gibt fast G Mitglieder in einem Cluster und insgesamt gibt es K Cluster. Wir definieren die Fehlerfunktion, die die durchschnittlichen Abstände zwischen Daten in einem Cluster misst, gemittelt über alle Cluster. Wenn wir alle Datenpaare systematisch durchgehen, sehen wir, ob der Austausch der Mitgliedschaft dieser beiden Daten zu einem geringeren Fehler führt. In diesem Fall aktualisieren wir den niedrigstmöglichen Fehler, andernfalls machen wir den Mitgliedschaftswechsel rückgängig. Wir tun dies, bis für einen ganzen Durchgang keine Züge mehr übrig sind.
Alexander Kain