Procedura grupowania, w której każdy klaster ma taką samą liczbę punktów?

Że pewne punkty w , i chcę skupić punkty, aby:$X=\{x_1,...,x_n\}$$R^p$

1. Każda grupa zawiera taką samą liczbę elementów . (Załóżmy, że liczba klastrów dzieli .)$X$$n$

2. Każda klaster jest w pewnym sensie „przestrzennie spójny”, podobnie jak klastry z średnich.$k$

Łatwo jest wymyślić wiele procedur klastrowania, które spełniają jedną lub drugą z nich, ale czy ktoś wie, jak uzyskać je jednocześnie?

Proponuję podejście dwuetapowe:

1. uzyskać dobre wstępne oszacowania centrów skupień, np. używając twardych lub rozmytych środków typu K.

2. Użyj przypisania Globalnego najbliższego sąsiada, aby powiązać punkty z centrami skupień: Oblicz macierz odległości między każdym punktem i każdym środkiem skupiska (możesz zmniejszyć problem, obliczając tylko rozsądne odległości), powtórz X każdego środka skupienia i rozwiąż liniowy problem z przypisaniem . Otrzymasz dla każdego centrum klastrów dokładnie X dopasowań do punktów danych, dzięki czemu globalnie odległość między punktami danych a centrami klastrów zostanie zminimalizowana.

Pamiętaj, że możesz zaktualizować centra klastrów po kroku 2 i powtórzyć krok 2, aby w zasadzie uruchomić K-średnich ze stałą liczbą punktów na klaster. Nadal dobrym pomysłem będzie najpierw odgadnąć.

Wypróbuj tę odmianę k-średnich:

Inicjalizacja :

• wybieraj kcentra z zestawu danych losowo, a nawet lepiej, korzystając ze strategii kmeans ++
• dla każdego punktu oblicz odległość do najbliższego centrum gromady i stwórz w tym celu stos
• narysuj punkty ze stosu i przypisz je do najbliższego klastra, chyba że klaster jest już przepełniony. Jeśli tak, oblicz następne najbliższe centrum klastra i włóż je ponownie do stosu

Na koniec powinieneś przeprowadzić parowanie, które spełni twoje wymagania + -1 tej samej liczby obiektów na klaster (upewnij się, że kilka ostatnich klastrów ma również odpowiednią liczbę. Pierwsze mklastry powinny mieć ceilobiekty, pozostałe dokładnie floorobiekty).

Krok iteracji :

Wymagania: lista dla każdego klastra z „propozycjami wymiany” (obiekty, które wolą być w innym klastrze).

Krok E : oblicz zaktualizowane centra skupień jak w zwykłych k-średnich

Krok M : Iterowanie przez wszystkie punkty (albo tylko jeden, albo wszystkie w jednej partii)

Oblicz najbliższe centrum klastrów, aby obiekt / wszystkie centra klastrów były bliżej niż bieżące klastry. Jeśli jest to inny klaster:

• Jeśli drugi klaster jest mniejszy niż bieżący, po prostu przenieś go do nowego
• Jeśli istnieje propozycja zamiany z drugiego klastra (lub dowolnego klastra z mniejszą odległością), zamień przypisania klastra z dwoma elementami (jeśli jest więcej niż jedna oferta, wybierz tę z największą poprawą)
• w przeciwnym razie wskaż propozycję zamiany dla drugiego klastra

Rozmiary skupień pozostają niezmienne (+ - różnica sufitu / podłogi), obiekty są przenoszone tylko z jednego skupienia do drugiego, o ile poprawia to oszacowanie. Dlatego powinien zbiegać się w pewnym momencie, jak k-średnie. Może to być nieco wolniejsze (tj. Więcej iteracji).

Nie wiem, czy zostało to wcześniej opublikowane lub wdrożone. Właśnie tego bym spróbował (gdybym spróbował k-średnich. Istnieją znacznie lepsze algorytmy grupowania).

Dobrym miejscem na początek może być wdrożenie k-średnich w ELKI , które już wydaje się wspierać trzy różne inicjalizacje (w tym k-średnie ++), a autorzy powiedzieli, że chcą mieć także różne strategie iteracji, aby objąć wszystkie różne wspólne warianty w sposób modułowy (np. Lloyd, MacQueen, ...).

Jest to problem z optymalizacją. Mamy bibliotekę Java typu open source, która rozwiązuje ten problem (grupowanie, w którym ilość na klaster musi znajdować się między ustawionymi zakresami). Będziesz potrzebował maksymalnej liczby punktów maksymalnie kilku tysięcy - nie więcej niż 5000, a może 10000.

Biblioteka jest tutaj:

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

Sama biblioteka jest skonfigurowana pod kątem problemów związanych z typem geograficznym / GIS - zobaczysz zatem odniesienia do X i Y, szerokości i długości geograficznej, klientów, odległości i czasu itp. Możesz po prostu zignorować elementy „geograficzne” i użyć go jako czystego klaster.

Zapewniasz zestaw początkowo pustych klastrów wejściowych, każdy z minimalną i maksymalną ilością docelową. Klaster przypisze punkty do twoich klastrów wejściowych, używając heurystycznego algorytmu optymalizacji (swapy, ruchy itp.). W optymalizacji optymalizuje przede wszystkim utrzymanie każdego skupiska w zakresie minimalnej i maksymalnej ilości, a następnie minimalizuje odległości między wszystkimi punktami skupienia i centralnym punktem skupienia, aby skupisko było spójne przestrzennie.

Nadajesz solverowi funkcję metryczną (tj. Funkcję odległości) między punktami za pomocą tego interfejsu:

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

Metryka jest tak skonstruowana, aby zwracała zarówno odległość, jak i „czas”, ponieważ została zaprojektowana z myślą o problemach geograficznych związanych z podróżą, ale w przypadku dowolnych problemów związanych z klastrowaniem wystarczy ustawić „czas” na zero, a odległość jest faktyczną metryką, której używasz między zwrotnica.

Skonfigurowałbyś swój problem w tej klasie:

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

Twoje punkty to „Klienci”, a ich liczba to 1. W klasie klientów upewnij się, że ustawiłeś costPerUnitTime = 0 i costPerUnitDistance = 1, zakładając, że zwracasz swoją odległość metryczną w polu „odległość” zwróconym przez TravelMatrix.

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

Zobacz tutaj przykład uruchamiania solvera:

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

Sugeruję najnowszy artykuł Dyskryminacyjne grupowanie poprzez regularną maksymalizację informacji (i odnośniki w nim zawarte). W szczególności sekcja 2 mówi o równowadze klas i założeniu klastra.

Ostatnio sam tego potrzebowałem do niezbyt dużego zestawu danych. Moja odpowiedź, choć ma stosunkowo długi czas działania, z pewnością jest zbieżna z lokalnym optimum.

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)