Free Press

Zadanie obejmujące uczenie maszynowe może nie być liniowe, ale ma kilka dobrze znanych kroków:

• Zdefiniowanie problemu.
• Przygotowanie danych.
• Uczenie modelu bazowego.
• Poprawa modelu bazowego poprzez oceny ilościowe i jakościowe.
• Prezentacja modelu.

Dobrym sposobem na pogodzenie się z nowym problemem jest praca poprzez identyfikację i zdefiniowanie problemu w najlepszy możliwy sposób oraz nauczenie się modelu, który przechwytuje znaczące informacje z danych. Chociaż problemy w rozpoznawaniu wzorców i uczeniu maszynowym mogą być różnego rodzaju, można je ogólnie sklasyfikować w trzech kategoriach:

• Uczenie pod nadzorem:
  Systemowi przedstawiane są przykładowe dane wejściowe i ich pożądane wyjścia, podane przez „nauczyciela”, a celem jest nauczenie się ogólnej reguły, która mapuje dane wejściowe na dane wyjściowe.
• Uczenie bez nadzoru:
  Algorytmowi uczącemu nie są podawane żadne etykiety, pozostawiając go samemu sobie w celu znalezienia struktury w danych wejściowych. Uczenie bez nadzoru może być celem samym w sobie (odkrywanie ukrytych wzorców w danych) lub środkiem do celu (uczenie cech).
• Uczenie przez wzmocnienie:
  System wchodzi w interakcję z dynamicznym środowiskiem, w którym musi wykonać określony cel (np. prowadzenie pojazdu lub gra z przeciwnikiem). System otrzymuje informacje zwrotne w postaci nagród i kar, gdy porusza się w przestrzeni problemowej.

Pomiędzy uczeniem nadzorowanym i nienadzorowanym znajduje się uczenie półnadzorowane, w którym nauczyciel przekazuje niekompletny sygnał treningowy: zbiór treningowy, w którym brakuje niektórych (często wielu) docelowych danych wyjściowych. W tym wpisie skupimy się na uczeniu nienadzorowanym i grupowaniu danych.

Uczenie nienadzorowane

W niektórych problemach rozpoznawania wzorców, dane szkoleniowe składają się z zestawu wektorów wejściowych x bez odpowiadających im wartości docelowych. Celem w takich problemach uczenia nienadzorowanego może być odkrycie grup podobnych przykładów w obrębie danych, gdzie nazywa się to grupowaniem, lub określenie, jak dane są rozmieszczone w przestrzeni, znane jako estymacja gęstości. Mówiąc prościej, dla n-próbkowanej przestrzeni x1 do xn, prawdziwe etykiety klas nie są dostarczane dla każdej próbki, stąd znane jako uczenie bez nauczyciela.

Problemy z uczeniem nienadzorowanym:

• Uczenie nienadzorowane jest trudniejsze w porównaniu do zadań uczenia nadzorowanego…
• Skąd wiemy, czy wyniki są znaczące, skoro nie są dostępne etykiety odpowiedzi?
• Pozwolić ekspertowi spojrzeć na wyniki (ewaluacja zewnętrzna)
• Zdefiniować funkcję celu na klasteryzację (ewaluacja wewnętrzna)

Dlaczego uczenie nienadzorowane jest potrzebne pomimo tych problemów?

• Anotowanie dużych zbiorów danych jest bardzo kosztowne i dlatego możemy ręcznie etykietować tylko kilka przykładów. Przykład: Speech Recognition
• Mogą wystąpić przypadki, w których nie wiemy na ile/jakie klasy podzielone są dane. Przykład: Data Mining
• Możemy chcieć użyć klastrowania, aby uzyskać pewien wgląd w strukturę danych przed zaprojektowaniem klasyfikatora.

Uczenie nienadzorowane można dalej podzielić na dwie kategorie:

• Parametric Unsupervised Learning
  W tym przypadku zakładamy parametryczny rozkład danych. Zakłada on, że przykładowe dane pochodzą z populacji, która podąża za rozkładem prawdopodobieństwa opartym na ustalonym zestawie parametrów. Teoretycznie, w normalnej rodzinie rozkładów, wszyscy członkowie mają ten sam kształt i są sparametryzowani przez średnią i odchylenie standardowe. Oznacza to, że jeśli znamy średnią i odchylenie standardowe, oraz że rozkład jest normalny, znamy prawdopodobieństwo każdej przyszłej obserwacji. Parametric Unsupervised Learning polega na konstrukcji Gaussian Mixture Models i wykorzystaniu algorytmu Expectation-Maximization do przewidywania klasy danej próbki. Ten przypadek jest znacznie trudniejszy niż standardowe uczenie nadzorowane, ponieważ nie ma dostępnych etykiet odpowiedzi, a tym samym nie ma poprawnej miary dokładności dostępnej do sprawdzenia wyniku.
• Nieparametryczne uczenie nienadzorowane
  W nieparametrycznej wersji uczenia nienadzorowanego, dane są pogrupowane w klastry, gdzie każdy klaster (miejmy nadzieję) mówi coś o kategoriach i klasach obecnych w danych. Metoda ta jest powszechnie używana do modelowania i analizy danych z małymi rozmiarami próbek. W przeciwieństwie do modeli parametrycznych, modele nieparametryczne nie wymagają od modelera przyjęcia żadnych założeń dotyczących rozkładu populacji, i dlatego są czasami nazywane metodą bezrozkładową.

Co to jest klastrowanie?

Klastrowanie może być uważane za najważniejszy problem uczenia nienadzorowanego; tak, jak każdy inny problem tego rodzaju, zajmuje się znalezieniem struktury w zbiorze nieoznakowanych danych. Luźną definicją klastrowania może być „proces organizowania obiektów w grupy, których członkowie są do siebie w jakiś sposób podobni”. Klaster jest więc zbiorem obiektów, które są „podobne” między sobą i są „niepodobne” do obiektów należących do innych klastrów.

Klastrowanie oparte na odległości.

Dając zbiór punktów, z pojęciem odległości między punktami, grupuje punkty w pewną liczbę klastrów, takich, że

• odległości wewnętrzne (wewnątrz klastra) powinny być małe i.członkowie klastrów są blisko/podobni do siebie.
• zewnętrzne (wewnątrzklastrowe) odległości powinny być duże, tj. członkowie różnych klastrów są niepodobni do siebie.

Cele klastrowania

Celem klastrowania jest określenie wewnętrznego grupowania w zbiorze nieoznakowanych danych. Ale jak zdecydować, co stanowi dobrą klasteryzację? Można pokazać, że nie ma absolutnego „najlepszego” kryterium, które byłoby niezależne od ostatecznego celu klasteryzacji. W związku z tym, to użytkownik powinien dostarczyć to kryterium, w taki sposób, aby wynik klasteryzacji odpowiadał jego potrzebom.

W powyższym obrazie, skąd wiemy, jakie jest najlepsze rozwiązanie klasteryzacji?

Aby znaleźć konkretne rozwiązanie klasteryzacji, musimy zdefiniować miary podobieństwa dla klastrów.

Miary bliskości

Dla klasteryzacji, musimy zdefiniować miarę bliskości dla dwóch punktów danych. Bliskość oznacza jak podobne/niepodobne są próbki w stosunku do siebie.

• Miara podobieństwa S(xi,xk): duża jeśli xi,xk są podobne
• Miara niepodobieństwa(lub odległości) D(xi,xk): mała, jeśli xi,xk są podobne

Istnieją różne miary podobieństwa, które mogą być użyte.

• Wektory: Cosine Distance

• Zestawy: Odległość Jaccard

• Punkty: Euclidean Distance
  q=2

„Dobra” miara bliskości jest BARDZO zależna od aplikacji. Skupiska powinny być niezmienne przy przekształceniach „naturalnych” dla danego problemu. Podczas klasteryzacji nie zaleca się również normalizacji danych, które są pobierane z wielu rozkładów.

Algorytmy klasteryzacji

Algorytmy klasteryzacji można sklasyfikować jako wymienione poniżej:

• Klastrowanie wyłączne
• Klastrowanie nakładające się
• Klastrowanie hierarchiczne
• Klastrowanie probabilistyczne

W pierwszym przypadku dane są grupowane w sposób wyłączny, tak że jeśli dany punkt danych należy do określonego klastra, to nie mógłby znaleźć się w innym klastrze. Prosty przykład tego jest pokazany na poniższym rysunku, gdzie oddzielenie punktów jest osiągnięte przez linię prostą na dwuwymiarowej płaszczyźnie.

Przeciwnie, drugi typ, klasteryzacja nakładająca się, używa zbiorów rozmytych do grupowania danych, tak że każdy punkt może należeć do dwóch lub więcej klastrów o różnych stopniach przynależności. W tym przypadku dane będą powiązane z odpowiednią wartością przynależności.

Hierarchiczny algorytm klasteryzacji opiera się na unii pomiędzy dwoma najbliższymi klastrami. Warunek początkowy jest realizowany poprzez ustawienie każdego punktu danych jako klastra. Po kilku iteracjach dochodzi do poszukiwanych klastrów końcowych.

Wreszcie ostatni rodzaj klasteryzacji wykorzystuje podejście całkowicie probabilistyczne.

W tym blogu porozmawiamy o czterech najczęściej używanych algorytmach klasteryzacji:

• K-means
• Fuzzy K-means
• Klasteryzacja hierarchiczna
• Mieszanka Gaussianów

Każdy z tych algorytmów należy do jednego z typów klasteryzacji wymienionych powyżej. Podczas gdy, K-means jest wyłącznym algorytmem grupowania, Fuzzy K-means jest nakładającym się algorytmem grupowania, Hierarchiczne grupowanie jest oczywiste i wreszcie Mieszanina Gaussianów jest probabilistycznym algorytmem grupowania. Omówimy każdą z metod klasteryzacji w kolejnych akapitach.

K-Means Clustering

K-means jest jednym z najprostszych algorytmów uczenia nienadzorowanego, który rozwiązuje dobrze znany problem klasteryzacji. Procedura ta polega na prostym i łatwym sposobie klasyfikacji danego zbioru danych poprzez pewną liczbę klastrów (zakładamy k klastrów) ustaloną a priori. Główną ideą jest zdefiniowanie k centroidów, po jednym dla każdego klastra. Centroidy te powinny być rozmieszczone w przemyślany sposób, ponieważ różne ich położenie powoduje różne wyniki. Dlatego lepszym wyborem jest umieszczenie ich jak najdalej od siebie. Następnym krokiem jest wzięcie każdego punktu należącego do danego zbioru danych i powiązanie go z najbliższym centroidem. Gdy żaden punkt nie jest oczekujący, pierwszy krok jest zakończony i następuje wczesne grupowanie. W tym momencie musimy ponownie obliczyć k nowych centroidów jako barycentra skupień powstałych w poprzednim kroku. Po uzyskaniu tych k nowych centroidów, należy wykonać nowe wiązanie pomiędzy tymi samymi punktami zbioru danych a najbliższym nowym centroidem. Powstaje w ten sposób pętla. W wyniku tej pętli możemy zauważyć, że k centroidów zmienia swoje położenie krok po kroku, aż do momentu, gdy nie będzie już żadnych zmian. Innymi słowy centroidy nie poruszają się już więcej.

Wreszcie, algorytm ten ma na celu minimalizację funkcji celu, w tym przypadku funkcji błędu kwadratowego. Funkcja celu

gdzie

jest wybraną miarą odległości między punktem danych xi a centrum klastra cj, jest wskaźnikiem odległości n punktów danych od ich odpowiednich centrów klastra.

Algorytm składa się z następujących kroków:

• Pozwól X = {x1,x2,x3,……..,xn} być zbiorem punktów danych, a V = {v1,v2,…….,vc} być zbiorem centrów.
• Losowo wybierz 'c’ centrów klastrów.
• Oblicz odległość między każdym punktem danych a centrami klastrów.
• Przypisać punkt danych do centrum klastra, którego odległość od centrum klastra jest minimalna spośród wszystkich centrów klastrów.
• Obliczyć nowe centrum klastra przy użyciu:

gdzie, 'ci’ reprezentuje liczbę punktów danych w i-tym klastrze.

• Oblicz ponownie odległość pomiędzy każdym punktem danych a nowo otrzymanymi centrami skupień.
• Jeżeli żaden punkt danych nie został ponownie przypisany to zatrzymaj się, w przeciwnym razie powtórz od kroku 3).

Chociaż można udowodnić, że procedura zawsze się zakończy, algorytm k-średnich niekoniecznie znajduje najbardziej optymalną konfigurację, odpowiadającą globalnemu minimum funkcji celu. Algorytm jest również istotnie wrażliwy na początkowe, losowo wybrane centra skupień. Algorytm k-średnich może być uruchamiany wielokrotnie w celu zmniejszenia tego efektu.

K-średnich jest prostym algorytmem, który został zaadaptowany do wielu dziedzin problemowych. Jak zobaczymy, jest on dobrym kandydatem do rozszerzenia do pracy z rozmytymi wektorami cech.

Procedura k-średnich może być postrzegana jako zachłanny algorytm podziału n próbek na k skupień tak, aby zminimalizować sumę kwadratów odległości do centrów skupień. Ma ona jednak pewne słabości:

• Nie określono sposobu inicjalizacji środków. Jednym z popularnych sposobów rozpoczęcia jest losowy wybór k próbek.
• Może się zdarzyć, że zbiór próbek najbliższych mi jest pusty, więc mi nie może być aktualizowane. Jest to problem, z którym należy sobie poradzić podczas implementacji, ale zazwyczaj jest ignorowany.
• Wyniki zależą od wartości k i nie ma optymalnego sposobu na opisanie najlepszego „k”.

Ten ostatni problem jest szczególnie kłopotliwy, ponieważ często nie mamy sposobu, aby wiedzieć, ile klastrów istnieje. W przykładzie pokazanym powyżej, ten sam algorytm zastosowany do tych samych danych daje następujące 3-means clustering. Czy jest ono lepsze czy gorsze niż grupowanie 2-średnich?

Niestety nie istnieje ogólne teoretyczne rozwiązanie pozwalające znaleźć optymalną liczbę klastrów dla dowolnego zbioru danych. Prostym podejściem jest porównanie wyników wielu przebiegów z różnymi klasami k i wybranie najlepszego według danego kryterium, ale musimy być ostrożni, ponieważ zwiększenie k skutkuje mniejszymi wartościami funkcji błędu z definicji, ale również zwiększa ryzyko przepasowania.

Fuzzy K-Means Clustering

W klasteryzacji rozmytej, każdy punkt ma prawdopodobieństwo przynależności do każdego klastra, a nie całkowitej przynależności do tylko jednego klastra, jak to ma miejsce w tradycyjnym k-średnich. Fuzzy k-means specjalnie próbuje poradzić sobie z problemem, w którym punkty są nieco pomiędzy centrami lub w inny sposób niejednoznaczne poprzez zastąpienie odległości prawdopodobieństwem, które oczywiście może być jakąś funkcją odległości, taką jak posiadanie prawdopodobieństwa względem odwrotności odległości. Fuzzy k-means używa ważonego centroidu opartego na tych prawdopodobieństwach. Procesy inicjalizacji, iteracji i zakończenia są takie same jak te używane w k-średnich. Wynikowe klastry są najlepiej analizowane jako rozkłady probabilistyczne, a nie twarde przypisanie etykiet. Należy zdać sobie sprawę, że k-średnich jest specjalnym przypadkiem rozmytych k-średnich, gdy używana funkcja prawdopodobieństwa jest po prostu 1, jeśli punkt danych jest najbliższy centroidowi i 0 w przeciwnym razie.

Algorytm rozmytych k-średnich jest następujący:

• Załóż stałą liczbę klastrów K.
• Inicjalizacja: Losowo inicjalizuj k-średnich μk związanych z klastrami i oblicz prawdopodobieństwo, że każdy punkt danych Xi jest członkiem danego klastra K,
  P(PointXiHasLabelK|Xi,K).
• Iteracja: Przelicz centroid klastra jako centroid ważony biorąc pod uwagę prawdopodobieństwa przynależności wszystkich punktów danych Xi :

• Zakończenie: Iteruj aż do zbieżności lub do osiągnięcia określonej przez użytkownika liczby iteracji (iteracja może zostać uwięziona na pewnych lokalnych maksimach lub minimach)

Dla lepszego zrozumienia możemy rozważyć ten prosty jednowymiarowy przykład. Biorąc pod uwagę pewien zbiór danych, załóżmy, że reprezentujemy go jako rozłożony na osi. Pokazuje to poniższy rysunek:

Patrząc na rysunek, możemy zidentyfikować dwa skupiska w pobliżu dwóch skupisk danych. Będziemy się do nich odwoływać używając 'A’ i 'B’. W pierwszym podejściu przedstawionym w tym tutorialu – algorytmie k-średnich – przypisaliśmy każdy punkt danych do określonego centroidu; dlatego też funkcja przynależności wyglądała następująco:

W podejściu Fuzzy k-średnich ten sam punkt danych nie należy wyłącznie do dobrze zdefiniowanego klastra, ale może być umieszczony w sposób pośredni. W tym przypadku funkcja przynależności podąża gładszą linią, aby wskazać, że każdy punkt danych może należeć do kilku klastrów z różnym zakresem przynależności.

Na rysunku powyżej punkt danych pokazany jako zaznaczony na czerwono należy raczej do klastra B niż do klastra A. Wartość 0.2 'm’ wskazuje stopień przynależności do A dla takiego punktu danych.

Hierarchiczne algorytmy grupowania

Dając zestaw N elementów do zgrupowania i N*N macierzy odległości (lub podobieństwa), podstawowy proces hierarchicznego grupowania jest następujący:

• Zacznij od przypisania każdego elementu do klastra, więc jeśli masz N elementów, masz teraz N klastrów, każdy zawierający tylko jeden element. Niech odległości (podobieństwa) między klastrami są takie same jak odległości (podobieństwa) między elementami, które zawierają.
• Znajdź najbliższą (najbardziej podobną) parę klastrów i połącz je w jeden klaster, tak że teraz masz jeden klaster mniej.
• Oblicz odległości (podobieństwa) między nowym klastrem a każdym ze starych klastrów.
• Powtarzaj kroki 2 i 3, aż wszystkie elementy zostaną zgrupowane w pojedynczym klastrze o rozmiarze N.

Clustering as a Mixture of Gaussians

Istnieje jeszcze jeden sposób radzenia sobie z problemami klasteryzacji: podejście oparte na modelu, które polega na użyciu pewnych modeli dla klastrów i próbie optymalizacji dopasowania między danymi a modelem.

W praktyce, każdy klaster może być matematycznie reprezentowany przez rozkład parametryczny, taki jak gaussowski. Cały zbiór danych jest więc modelowany przez mieszaninę tych rozkładów.
Model mieszaniny o wysokim prawdopodobieństwie ma następujące cechy:

• rozkłady składowe mają wysokie „szczyty” (dane w jednym klastrze są ścisłe);
• model mieszaniny dobrze „pokrywa” dane (dominujące wzorce w danych są uchwycone przez rozkłady składowe).

Główne zalety grupowania opartego na modelu:

• dostępne są dobrze zbadane techniki wnioskowania statystycznego;
• elastyczność w wyborze rozkładu składowego;
• uzyskanie estymacji gęstości dla każdego klastra;
• dostępna jest „miękka” klasyfikacja.

Mieszanina Gaussianów
Najpowszechniej stosowana metoda klasteryzacji tego typu opiera się na uczeniu mieszaniny Gaussianów:

Model mieszaninowy to mieszanina k rozkładów składowych, które wspólnie tworzą rozkład mieszaniny f(x):

Przypis αk reprezentuje wkład k-tej składowej w konstruowanie f(x). W praktyce często stosuje się rozkłady parametryczne (np. gaussowskie), ponieważ wykonano wiele pracy, aby zrozumieć ich zachowanie. Jeśli zastąpisz każdą fk(x) gaussianem, otrzymasz coś, co jest znane jako gaussian mixture models (GMM).

Algorytm EM

Expectation-Maximization zakłada, że twoje dane składają się z wielu rozkładów normalnych (zauważ, że jest to bardzo silne założenie, w szczególności, gdy ustalisz liczbę klastrów!). Alternatywnie rzecz ujmując, EM jest algorytmem maksymalizacji funkcji prawdopodobieństwa, gdy niektóre ze zmiennych w twoim modelu są nieobserwowalne (tj. gdy masz zmienne ukryte).
Możesz uczciwie zapytać, jeśli po prostu próbujemy zmaksymalizować funkcję, dlaczego nie możemy po prostu użyć istniejącej maszynerii do maksymalizacji funkcji. Dobrze, jeśli próbujesz maksymalizować to przez branie pochodnych i ustawianie ich na zero, znajdujesz, że w wielu przypadkach warunki pierwszego rzędu nie mają rozwiązania. Jest to problem typu „kura i jajko”, ponieważ aby rozwiązać problem parametrów modelu, musisz znać rozkład twoich nieobserwowanych danych; ale rozkład twoich nieobserwowanych danych jest funkcją parametrów modelu.

Algorytm Expectation-Maximization próbuje obejść ten problem poprzez iteracyjne zgadywanie rozkładu dla nieobserwowanych danych, a następnie estymację parametrów modelu poprzez maksymalizację czegoś, co jest dolnym ograniczeniem rzeczywistej funkcji prawdopodobieństwa, i powtarzanie aż do zbieżności:

Algorytm Expectation-Maximization

• Start z zgadywaniem wartości parametrów modelu
• Krok E: Dla każdego punktu danych, który ma brakujące wartości, użyj równania modelu, aby rozwiązać rozkład brakujących danych, biorąc pod uwagę twoje aktualne przypuszczenia dotyczące parametrów modelu i biorąc pod uwagę obserwowane dane (zauważ, że rozwiązujesz rozkład dla każdej brakującej wartości, a nie dla wartości oczekiwanej). Teraz, gdy mamy już rozkład dla każdej brakującej wartości, możemy obliczyć oczekiwanie funkcji prawdopodobieństwa w odniesieniu do nieobserwowanych zmiennych. Jeśli nasze przypuszczenia co do parametrów modelu były poprawne, to oczekiwane prawdopodobieństwo będzie rzeczywistym prawdopodobieństwem naszych obserwowanych danych; jeśli parametry nie były poprawne, to będzie to tylko dolna granica.
• Krok M: Teraz, gdy mamy oczekiwaną funkcję prawdopodobieństwa, w której nie ma zmiennych nieobserwowanych, zmaksymalizuj tę funkcję tak, jak w przypadku w pełni obserwowanym, aby uzyskać nowe oszacowanie parametrów modelu.
• Powtarzaj aż do zbieżności.

Problemy związane z grupowaniem

Istnieje wiele problemów związanych z grupowaniem. Wśród nich:

• radzenie sobie z dużą liczbą wymiarów i dużą liczbą elementów danych może być problematyczne ze względu na złożoność czasową;
• skuteczność metody zależy od definicji „odległości” (dla grupowania opartego na odległości). Jeśli oczywista miara odległości nie istnieje, musimy ją „zdefiniować”, co nie zawsze jest łatwe, zwłaszcza w przestrzeniach wielowymiarowych;
• wynik działania algorytmu grupowania (który w wielu przypadkach może być arbitralny) może być interpretowany na różne sposoby.

Możliwe zastosowania

Algorytmy klasteryzacji mogą być stosowane w wielu dziedzinach, na przykład:

• Marketing: znajdowanie grup klientów o podobnych zachowaniach biorąc pod uwagę dużą bazę danych o klientach zawierającą ich właściwości i dotychczasowe rekordy zakupowe;
• Biologia: klasyfikacja roślin i zwierząt biorąc pod uwagę ich cechy;
• Ubezpieczenia: identyfikacja grup posiadaczy polis ubezpieczenia komunikacyjnego o wysokim średnim koszcie roszczenia; identyfikacja oszustw;
• Badania nad trzęsieniami ziemi: grupowanie obserwowanych epicentrów trzęsień ziemi w celu identyfikacji stref niebezpiecznych;
• World Wide Web: klasyfikacja dokumentów; grupowanie danych z blogów internetowych w celu odkrycia grup o podobnych wzorcach dostępu.