Zbiory danych systemów uczących się mogą zawierać miliony ale nie wszystkie algorytmy grupowania skalują się skutecznie. Wiele grupowania algorytmy obliczają podobieństwo wszystkich par przykładów, które oznacza, że czas działania wydłuża się do kwadratu liczby przykładów \(n\), opisane jako \(O(n^2)\) w notacji złożoności. \(O(n^2)\) Algorytmy nie są praktyczny w przypadku zbiorów danych z milionami przykładów.
Algorytm k-średni zawiera funkcję złożoność \(O(n)\), co oznacza, że algorytm skaluje się liniowo wraz z \(n\). Ten algorytm będzie głównym tematem tego kursu.
Typy grupowania
Pełną listę różnych metod grupowania znajdziesz w artykule Wszechstronna analiza algorytmów grupowania Xu, D. & Tian, Y. Anna. Dane. Nauka (2015) 2: 165. Każda z tych metod sprawdzi się najlepiej, zgodnie z konkretną dystrybucją danych. W tym kursie omówiono pokrótce cztery często spotykane podejść do problemu.
Grupowanie według Centroid
centroid klastra to średnia arytmetyczna wszystkich punktów w klastra. Grupowanie w oparciu o centroidy powoduje uporządkowanie danych w niehierarchiczny sposób. klastrów. Algorytmy grupowania oparte na Centroid są wydajne, ale wrażliwe warunki początkowe i wartości odstające. Spośród nich k-średnie są największą powszechnie stosowane. Wymaga określenia przez użytkownika liczby centroidów, k dobrze działa z klastrami o mniej więcej takiej samej wielkości.
Grupowanie na podstawie gęstości
Grupowanie na podstawie gęstości łączy sąsiadujące obszary o dużej gęstości przykładów klastrów. Umożliwia to wykrywanie dowolnej liczby klastrów o dowolnym kształcie. Wyniki odstające nie są przypisywane do klastrów. Algorytmy te mają trudności z klastry o różnej gęstości i dużych wymiarach,
Grupowanie oparte na dystrybucji
Takie podejście do grupowania zakłada, że dane składają się z prawdopodobnych dystrybucji, takich jak Rozkłady Gaussa. W Rys. 3: algorytm rozkładu oparty na rozkładzie danych łączy dane w trzy postacie rozkładu Gaussa rozkłady. Wraz ze wzrostem odległości od centrum rozkładu prawdopodobieństwo, że punkt należy do rozkładu, maleje. Koncerty zespołów zmniejsza się prawdopodobieństwo. Gdy nie czujesz się komfortowo przy założeniu, zgodnie z rozkładem danych, należy użyć innego algorytmu.
Grupowanie hierarchiczne
Grupowanie hierarchiczne tworzy drzewo klastrów. Grupowanie hierarchiczne, ale nie jest zaskoczeniem, że dobrze sprawdza się w przypadku danych hierarchicznych, takich jak taksonomie. Zobacz Porównanie 61 sekwencjonowanych genomów Escherichia coli autorzy: Oksana Lukjancenko, Trudy Wassenaar Dave Ussery'ego. Możesz wybrać dowolną liczbę klastrów, przycinając drzewo na odpowiednim poziomie.
