Klastrowanie (k-średnie lub w inny sposób) z ograniczeniem minimalnego rozmiaru klastra

14

Muszę grupować jednostki w klastrów, aby zminimalizować sumę kwadratów wewnątrz grupy (WSS), ale muszę upewnić się, że każda z klastrów zawiera co najmniej jednostek. Masz pojęcie, czy którakolwiek z funkcji klastrowania R pozwala na grupowanie w klastrów z zastrzeżeniem ograniczenia minimalnego rozmiaru klastra? Kmeans () nie wydaje się oferować opcji ograniczenia rozmiaru.kmk

r clustering Cyrus S.
źródło

Odpowiedzi:

5

Użyj klastrowania EM

W klastrowaniu EM algorytm iteracyjnie udoskonala początkowy model klastra w celu dopasowania do danych i określa prawdopodobieństwo istnienia punktu danych w klastrze. Algorytm kończy proces, gdy model probabilistyczny pasuje do danych. Funkcja zastosowana do określenia dopasowania to logarytmiczne prawdopodobieństwo danych dla danego modelu.

Jeśli podczas procesu generowane są puste klastry lub jeśli członkostwo jednego lub więcej klastrów spadnie poniżej określonego progu, klastry o niskiej populacji są ponownie wysiewane w nowych punktach i algorytm EM jest uruchamiany ponownie.

mariana bardziej miękka
źródło
Dzięki, Marianna. Wolałbym rozwiązanie, które w mniejszym stopniu opiera się na (zazwyczaj nieuzasadnionych) modelach parametrycznych, ale na pewno je przeanalizuje.
Cyrus S,
4

Ten problem rozwiązano w tym dokumencie:

Bradley, PS, KP Bennett i Ayhan Demiriz. „Ograniczone k-oznacza grupowanie”. Microsoft Research, Redmond (2000) : 1-8.

Mam implementację algorytmu w Pythonie.

Behrouz Babaki
źródło
To jest idealne, dzięki! Użyłem rPythonpakietu w R do stworzenia interfejsu do tej implementacji, do którego uzyskałem dostęp ze skryptu R.
Michael Ohlrogge
@MichaelOhlrogge, czy masz gdzieś przykład (github?) Na interfejsie, który napisałeś, aby wywołać pakiet Pythona z R? Dzięki!
Matifou
Przepraszam, rozejrzałem się po starym kodzie, ale nie mogłem go już znaleźć.
Michael Ohlrogge
3

Myślę, że byłoby to po prostu kwestią uruchomienia k środków jako części pętli if z testem dla wielkości klastra, tj. Liczyć n w klastrze k - pamiętaj również, że k oznacza da inne wyniki dla każdego uruchomienia na tych samych danych, więc i tak powinieneś uruchomić go jako część pętli, aby wyodrębnić „najlepszy” wynik


źródło
1
Dzięki, Alex. Widzę jednak problem: co jeśli wygenerowane rozwiązania nigdy nie spełnią ograniczenia? Może się to zdarzyć, jeśli k oznacza, że ​​będą działać bez ograniczenia wielkości klastra. Chciałbym rozwiązania, które pozwala tego uniknąć. (Charakter aplikacji jest taki, że naprawdę muszę upewnić się, że klastry mają minimalny rozmiar.)
Cyrus S
1

Jak duży jest twój zestaw danych? Być może możesz spróbować uruchomić hierarchiczne klastrowanie, a następnie zdecydować, które klastry zachowają na podstawie twojego dendrogramu.

Jeśli Twój zestaw danych jest ogromny, możesz także połączyć obie metody klastrowania: początkową niehierarchiczną, a następnie hierarchiczną, korzystając z grup z analizy niehierarchicznej. Przykład takiego podejścia można znaleźć w Martínez-Pastor i in. (2005)

Manuel Ramón
źródło
Dzięki, Manuel. To właściwie brzmi bardzo intrygująco. Muszę pomyśleć o tym, czy hierarchiczne partycjonowanie narzuciłoby pewne ograniczenia, które uniemożliwiłyby algorytmowi osiągnięcie optymalnego partycjonowania klastra bezpośrednio pod ograniczeniem wielkości. Ale intuicyjnie widzę, że to może zadziałać.
Cyrus S,
0

Można to osiągnąć, modyfikując krok przypisania klastra (E w EM) przez sformułowanie go jako problemu optymalizacji sieci liniowej o minimalnym przepływie kosztów (MCF).

Napisałem pakiet Pythona, który korzysta z SimpleMinCostFlow narzędzia Google Operations Research, które jest szybką implementacją C ++. Ma standardowy interfejs API scikit-lean.

joshlk
źródło