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

25

Że pewne punkty w , i chcę skupić punkty, aby:X={x1,...,xn}Rp

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

  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?

Nie Durrett
źródło
2
Czy określono również rozmiar klastra? Zatem, jak stwierdzono, problem wydaje mi się nierozwiązywalny. Rozważ następujący przypadek z : X = { - 1 , 0,99 , 1 , 1,01 } . Jeśli chcesz 2 klastry, otrzymasz albo różne rozmiary, albo nie „przestrzennie spójny”. A może chcesz coś w rodzaju „jak najbardziej spójnego przestrzennie” - minimalizując maksymalną odległość wewnątrz gromady? Innym rozwiązaniem byłoby dopuszczenie dowolnego dzielnika n jako rozmiaru klastra - ale zawsze istnieje trywialne rozwiązanie n klastrów o rozmiarze 1n=4,p=1X={-1,0,99,1,1.01}nn1.
Erik P.
1
Słuszna uwaga. Idealnie chciałbym coś, co jest „tak spójne przestrzennie, jak to możliwe”, przy jednoczesnym spełnieniu ograniczenia równości liczności. Ale chciałbym usłyszeć o wszelkich procedurach, które powodują tutaj inne kompromisy, ponieważ być może można je dostosować.
Nie Durrett,
Czy podział danych przez kwantyle wystarczyłby? Jeśli wartości nie są monotoniczne względem siebie, nie widzę, jak inaczej mogłyby być „przestrzennie spójne”.
celenius
4
Niedawno przeprowadzono badania dotyczące ograniczonego grupowania. Google google.com/search?q=constrained+k-means .
whuber
Tylko jeden niesprawdzony pomysł. W grupowaniu często stosuje się tak zwaną statystykę sylwetki. Pokazuje, jak dobrze obiekt jest klastrowany i jaki jest najlepszy inny sąsiedni klaster, do którego można go zapisać. Możesz więc zacząć od K-MEANS lub innej klasyfikacji z różnymi klastrami n . Następnie przenieś obiekty niezbyt dobrze sklasyfikowane (zgodnie ze statystyką) do ich najlepszych sąsiednich klastrów o mniejszym n, aż uzyskasz równe n . Spodziewam się iteracji: przenieś niektóre obiekty, ponownie oblicz statystyki, przenieś niektóre obiekty itp. To będzie proces kompromisowy.
ttnphns,

Odpowiedzi:

6

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ąć.

Jonas
źródło
4

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

Anony-Mus
źródło
2
Podobne podejście jest zawarte w ELKI jako samouczek oraz w module „rozszerzenia” samouczka: elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans
Erich Schubert
3

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

Logistyka otwartych drzwi
źródło
2

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)
Alexander Kain
źródło
1
Dzięki za ten wkład, @ user2341646. Czy miałbyś coś przeciwko dodaniu prezentacji wyjaśniającej, czym jest to rozwiązanie, jak działa i dlaczego jest rozwiązaniem?
gung - Przywróć Monikę
DOBRZE. Zasadniczo algorytm zaczyna się od losowych przydziałów członkostwa, ale w klastrze jest blisko członków G i ogólnie jest K klastrów. Definiujemy funkcję błędu, która mierzy średnie odległości między danymi w jednym klastrze, uśrednione dla wszystkich klastrów. Przeglądając systematycznie wszystkie pary danych, widzimy, czy wymiana członkostwa tych dwóch danych powoduje mniejszy błąd. Jeśli tak, aktualizujemy najmniejszy możliwy błąd, w przeciwnym razie cofamy zmianę członkostwa. Robimy to, dopóki nie pozostanie więcej ruchów dla jednego całego podania.
Alexander Kain