Przyjrzyjmy się szybko typom algorytmów klastrów i dowiesz się, kiedy warto wybrać każdy z nich.
Wybierając algorytm grupowania, rozważ, czy skaluje się on do zbioru danych. Zbiory danych w systemach uczących się mogą mieć miliony przykładów, ale nie wszystkie algorytmy grupowania skalują się skutecznie. Wiele algorytmów grupuje ze względu na podobieństwo wszystkich par przykładów. Oznacza to, że ich czas działania rośnie jako kwadrat liczby przykładów \(n\), co wskazuje na \(O(n^2)\) złożoność notacji. \(O(n^2)\) Algorytmy nie są praktyczne, gdy liczba przykładów jest miliony. Ten kurs skupia się na algorytmie k-średnia, który ma złożoność \(O(n)\), co oznacza, że skaluje się liniowo z \(n\).
Typy grupowań
Istnieje kilka sposobów na grupowanie. Pełną listę zawiera Kompleksowa ankieta na temat grupowania algorytmów Xu, D. i Tian, Y. Dane Ann. Naukowe (2015) 2: 165. Każde z nich najlepiej pasuje do konkretnego sposobu dystrybucji danych. Poniżej przedstawiamy krótką prezentację 4 typowych praktyk, które skupiają się na grupowaniu opartym na centroidach za pomocą k-średnich.
Klastry oparte na Centroidach
Klaster oparty na tropikach grupuje dane w klastry niehierarchiczne, w przeciwieństwie do grupowania hierarchicznego zdefiniowanego poniżej. Najczęściej używane są k-mesy. Algorytmy oparte na Centroid są skuteczne, ale wrażliwe na początkowe warunki i wartości odstające. Ten kurs skupia się na k-średnich, bo jest to wydajny, skuteczny i prosty algorytm grupowania.
Klastry oparte na gęstości
Klastry oparte na gęstości łączą obszary o wysokiej gęstości przykładowych w klastrach. Dzięki temu można łączyć dowolne kształty pod warunkiem, że są one połączone. Algorytmy mają trudności z danymi o różnych gęstościach i wysokich wymiarach. Co więcej, algorytmy te nie przypisują znacznych wartości do klastrów.
Klastry oparte na dystrybucji
Ta metoda grupowania zakłada, że dane składają się z rozkładów, takich jak rozkład Gaussa. Na rysunku 3 algorytm oparty na dystrybucji grupuje dane w 3 rozkłady Gaussa. Wraz ze wzrostem odległości od środka rozkładu rośnie prawdopodobieństwo, że punkt należy do rozkładu. Pasma wskazują, że prawdopodobieństwo zmniejszenia się prawdopodobieństwa jest mniejsze. Jeśli nie znasz typu dystrybucji danych, użyj innego algorytmu.
Klaster hierarchiczny
Klaster hierarchiczny tworzy drzewo klastrów. Klastry hierarchiczne nie są zaskakujące, ale dobrze nadają się do danych hierarchicznych, takich jak taksonomie. Zobacz przykład porównania 61 sekwencjonowanej Escherichia coli Oksany Lukjancenko, Trudy Wassenaar i Dave Ussery. Kolejną zaletą jest to, że możesz wybrać dowolną liczbę klastrów, wycinając drzewo na odpowiednim poziomie.