k-oznacza pusty klaster

Question

Próbuję wprowadzić k-means jako zadanie domowe. W moim arkuszu ćwiczeń podaję następującą uwagę dotyczącą pustych ośrodków:

Podczas iteracji, jeśli którykolwiek z centrów klastra nie ma powiązanych z nim punktów danych, należy zastąpić go losowym punktem danych.

Trochę to mnie denerwuje, po pierwsze Wikipedia lub inne źródła, które czytam, w ogóle o tym nie wspominają. W dalszej części przeczytałem o problemie z "wyborem dobrego k dla danych" - jak mój algorytm powinien się zbiegać, gdy zacznę ustawiać nowe centra dla klastra, które były puste.

Jeśli zignoruję puste klastry, zbiegam się po 30-40 iteracjach. Czy błędem jest ignorowanie pustych klastrów?

Answer 1

Nie należy ignorować pustych klastrów, ale zastąpić go. k-znaczy to algorytm, który może zapewnić tylko lokalne minimum, a puste klastry to lokalne minimum, którego nie chcesz. Twój program będzie się zbiegał, nawet jeśli zamienisz punkt na losowy. Pamiętaj, że na początku algorytmu losowo wybierasz początkowe punkty K. jeśli może się zbiegać, dlaczego K-1 nie może zbiegać się z jednym punktem losowym? potrzebnych jest tylko kilka kolejnych iteracji.

Answer 2

"Wybór dobrych k dla danych" odnosi się do problemu wyboru odpowiedniej liczby klastrów. Ponieważ algorytm k-średnich działa z określoną z góry liczbą centrów klastra, ich liczba musi zostać wybrana na początku. Wybór niewłaściwej liczby może utrudnić podział punktów danych na klastry, a klastry mogą stać się małe i pozbawione znaczenia.

Nie mogę udzielić odpowiedzi na pytanie, czy ignorowanie pustych klastrów jest złym pomysłem. Jeśli to zrobisz, możesz otrzymać mniejszą liczbę klastrów niż zdefiniowano na początku. W ten sposób ludzie, którzy oczekują k-średnich, będą pracować w określony sposób, ale niekoniecznie jest to zły pomysł.

Po zmianie lokalizacji pustych centrów klastra algorytm prawdopodobnie się zbiegnie, jeśli zdarzy się to w ograniczonej liczbie razy. Jeśli jednak musisz się zbyt często przenosić, może się zdarzyć, że Twój algorytm się nie zakończy.

Answer 3

Zobacz przykład tego, jak puste klastry mogą się zdarzyć: http://www.ceng.metu.edu.tr/~tcan/ceng465_f1314/Schedule/KMeansEmpty.html Oznacza to po prostu 1) przypadkowe drżenie w sile lub 2) liczbę klastrów k jest błędna. Powinieneś powtórzyć kilka różnych wartości k i wybrać najlepsze. Jeśli podczas iteracji powinieneś spotkać się z pustym klastrem, umieść losowy punkt danych w tym klastrze i kontynuuj. Mam nadzieję, że pomogło ci to w twoim zadaniu domowym w ubiegłym roku.

Answer 4

Obsługa pustych klastrów nie jest częścią algorytmu k-średnich, ale może skutkować lepszą jakością klastrów. Mówiąc o konwergencji, nigdy nie jest to dokładnie, ale tylko heurystycznie gwarantowane, a zatem kryterium konwergencji jest rozszerzane przez uwzględnienie maksymalnej liczby iteracji.

Jeśli chodzi o strategię radzenia sobie z tym problemem, powiedziałbym, że przypadkowe przypisanie niektórych danych do niego nie jest zbyt sprytne, ponieważ możemy mieć wpływ na jakość klastra, ponieważ odległość do aktualnie przypisanego centrum jest duża lub mała. Hierarchiczna dla tego przypadku będzie wybranie najdalszego punktu z największej gromady i przesunięcie pustej gromady, a następnie robienie tego, dopóki nie będzie pustych klastrów.