Zbiory danych uczenia maszynowego mogą zawierać miliony przykładów, ale nie wszystkie algorytmy grupowania skalują się efektywnie. Wiele algorytmów klastrowania oblicza podobieństwo między wszystkimi parami przykładów, co oznacza, że ich czas działania zwiększa się proporcjonalnie do kwadratu liczby przykładów \(n\), co oznacza, że w notacji złożoności \(O(n^2)\) , algorytmy \(O(n^2)\) nie są praktyczne w przypadku zbiorów danych zawierających miliony przykładów.
Algorytm k-średnich ma złożoność \(O(n)\), co oznacza, że algorytm skaluje się liniowo z \(n\). Ten algorytm będzie tematem tego kursu.
Typy grupowania
Pełną listę różnych podejść do grupowania znajdziesz w artykule A Comprehensive Survey of Clustering Algorithms (Xu, D. i Tian, Y. Ann. Data. Sci. (2015) 2: 165. Każde z tych podejść najlepiej nadaje się do konkretnego rozkładu danych. W tym szkoleniu omówiono pokrótce 4 popularne podejścia.
Utworzenie klastrów na podstawie centroidów
Środek geometryczny klastra to średnia arytmetyczna wszystkich punktów w klastrze. Klasteryzacja na podstawie centroidów porządkuje dane w niehierarchiczne klastry. Algorytmy zgrupowania opartego na środku ciężkości są wydajne, ale wrażliwe na początkowe warunki i wartości odstające od reszty. Spośród nich najczęściej stosowana jest metoda k-średnich. Wymaga od użytkowników określenia liczby centroidów k i dobrze działa z klastrami o zbliżonej wielkości.
Grupowanie na podstawie gęstości
Gromadzenie oparte na gęstości łączy ze sobą ciągłe obszary o dużej gęstości przykładów w klastry. Umożliwia to wykrywanie dowolnej liczby klastrów o dowolnym kształcie. Wartości odstające nie są przypisywane do klastrów. Te algorytmy mają trudności z grupami o różnej gęstości i danymi o dużej liczbie wymiarów.
Grupowanie na podstawie rozkładu
To podejście do zgrupowania zakłada, że dane składają się z rozkładów prawdopodobieństwa, takich jak rozkłady normalne. Na rysunku 3 algorytm oparty na rozkładzie grupował dane w 3 rozkłady normalne Gaussa. Wraz ze wzrostem odległości od środka rozkładu maleje prawdopodobieństwo, że dany punkt należy do rozkładu. Paski wskazują na spadek prawdopodobieństwa. Jeśli nie masz pewności co do konkretnego rozkładu danych, użyj innego algorytmu.
Grupowanie hierarchiczne
Klasterowanie hierarchiczne tworzy drzewo klastrów. Grupowanie hierarchiczne jest dobrze dopasowane do danych hierarchicznych, takich jak taksonomia. Przykładem jest artykuł Comparison of 61 Sequenced Escherichia coli Genomes autorstwa Oksany Lukjancenko, Trudy Wassenaar i Dave’a Ussery’ego. Możesz wybrać dowolną liczbę klastrów, przecinając drzewo na odpowiednim poziomie.
