Charakterystyka podejść do grupowania danych¶

Metody hierarchiczne¶

Wspólną cechą tych metod jest fakt, że w wyniku ich działania otrzymujemy całą hierarchię podziałów. Mając dany podział na ustalonym poziomie, uzyskany na kolejnym różni się w stosunku do niego tym, że dokładnie dwie grupy zostały połączone w jedną większą, lub dokładnie jedna grupa została rozdzielona na dwie mniejsze. Hierarchię podziałów, która spełnia na każdym poziomie przytoczoną własność, nazywamy podziałami zagnieżdżonymi. Zasadniczo, w zależności od sposobu konstrukcji zagnieżdżonych podziałów wyróżniamy dwa typy algorytmów hierarchicznych: aglomeracyjne i algorytmy podziału. W przypadku algorytmów aglomeracyjnych podział początkowy, stanowi \(N\) grup, z których każdą tworzy dokładnie jeden obiekt zboru uczącego. Kolejne podziały tworzone są poprzez połączenie dwóch grup w podziale otrzymanym w kroku poprzednim, w efekcie jako ostatni otrzymując podział, w którym cały zbiór uczący jest jedyną grupą. Każdy krok algorytmu polega na połączeniu dwóch grup do siebie najbardziej podobnych lub alternatywnie najmniej niepodobnych, zgodnie z przyjętą miarą podobieństwa. W przypadku algorytmów aglomeracyjnych mówimy, że hierarchia podziałów tworzona jest od dołu do góry. Natomiast hierarchiczne algorytmy podziału tworzą hierarchię w schemacie od góry do dołu, to znaczy rozpoczynając od grupy składającej się ze wszystkich obiektów zbioru uczącego, kończąc na podziale na N grup, w którym każdą grupę tworzy dokładnie jeden obiekt. W tym przypadku każdy krok polega na podzieleniu jednej z grup otrzymanego w kroku poprzednim podziału, na dwie mniejsze. Te metody są jednak znacznie rzadziej stosowane ze względu na większą niż aglomeracyjnych złożoność obliczeniową. Sposób określania podobieństwa międzygrupowego algorytmu hierarchicznego jest czynnikiem, który w decydujący sposób wpływa na rezultaty grupowania hierarchicznego i prowadzi w efekcie do różnych algorytmów [Jain1998]. Wśród najczęściej spotykanych metod określania miary podobieństwa międzygrupowego wyróżniamy:

1. Metoda najbliższego sąsiada (ang. single link algorithm )

   \[{{D}_{\min }}({{C}_{i}},{{C}_{j}})=\underset{x\in {{C}_{i}},y\in {{C}_{j}}}{\mathop{\rm min}}\,{{d}^{2}}\left( x,y \right)\]

2. Metoda najdalszego sąsiada (emph{ang. complete link algorithm})

   \[{{D}_{\max }}({{C}_{i}},{{C}_{j}})=\underset{x\in {{C}_{i}},y\in {{C}_{j}}}{\mathop{\rm max}}\,{{d}^{2}}\left( x,y \right)\]

3. Metoda średniej odległości międzygrupowej (ang. weighted pair group method average algorithm)

   \[{{D}_{avg}}({{C}_{i}},{{C}_{j}})=\frac{1}{{{n}_{i}}{{n}_{j}}}\sum\limits_{x\in {{C}_{i}}}{\sum\limits_{y\in {{C}_{j}}}{{{d}^{2}}\left( x,y \right)}}\text{, gdzie }{{n}_{i}}=\left| {{C}_{i}} \right|\]

4. Metoda odległość między środkami grup (ang. unweighted pair group method centroid algorithm)

   \[{{D}_{mean}}({{C}_{i}},{{C}_{j}})={{d}^{2}}\left( {{c}_{i}},{{c}_{j}} \right)\text{, gdzie }{{c}_{i}}=\frac{1}{{{n}_{i}}}\sum\limits_{x\in {{C}_{i}}}{x}\]

W przypadku powyższych miar podobieństwa międzygrupowego, za najbardziej podobne uważamy te grupy \({{C}_{i}},{{C}_{j}}\), które spełniają warunek:

Miara podobieństwa najbliższego sąsiada powoduje generowanie grup o wydłużonych kształtach, zaś miara najdalszego sąsiada grup o kształtach maksymalnie zwartych, eliptycznych. Pozostałe metody mają pośrednie własności, to znaczy o kształcie grup decydują kształty obszarów, w których występuje maksymalne zagęszczenie próbek. W ten sposób na wynik grupowania nie mają wpływu pojedyncze próbki znajdujące się między obszarami skupień, co jest wadą metody najbliższego sąsiada, a zarazem nie występuje tendencja do tworzenia za wszelką cenę grup o zwartych kształtach, jak w metodzie sąsiada najdalszego. Wynik działania algorytmu hierarchicznego przedstawiamy na ogół za pomocą tak zwanego dendrogramu, to znaczy drzewa binarnego, którego liśćmi są klasyfikowane wektory, a każdy węzeł reprezentuje grupę, do której należą wszystkie wektory (liście) do których prowadzi droga z tego węzła. Dodatkowo długość gałęzi może oznaczać wartość podobieństwa międzygrupowego, a odcinając dendrogram na \(i\)-tym poziomie, licząc od korzenia włącznie, otrzymujemy podział na \(i\) grup. Przy zadanej liczbie grup, algorytm hierarchiczny można zmodyfikować w ten sposób, by nie tworzył całej hierarchii podziałów, a zatrzymywał się w określonym miejscu. Algorytm grupowania hierarchicznego w schemacie aglomeracyjnym przebiega według poniższego schematu:

Wadą algorytmów hierarchicznych jest ich złożoność obliczeniowa, wynikająca z potrzeby przeliczania miar podobieństwa międzygrupowego na każdym poziomie, dlatego rozwój tych metod grupowania idzie w kierunku przyspieszenia ich działania, tak by przy ich pomocy można było analizować bardzo duże zbiory danych. Stosowane tutaj są na ogół metody fragmentaryzacji zbioru polegające na podziale zbioru na pewna liczbę równolicznych podzbiorów, tak aby grupowanie każdego z nich odbywało się wystarczająco szybko. Następnie w każdym podzbiorze przy pomocy algorytmu grupowania wybieramy zbiór reprezentantów, które to później ponownie poddawane są grupowaniu. Zgodnie z tą koncepcją pozostałe elementy zbioru przydzielamy do grup w oparciu o najmniejszą odległość od reprezentanta. Zamiast fragmentaryzacji stosujemy również próbkowanie zbioru, wybierając pewien jego losowy podzbiór bądź podzbiory.

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_classification
from scipy.cluster.hierarchy import fcluster
from sklearn.metrics import confusion_matrix
from numpy import array
import numpy as np

#Wygenerowanie zbioru danych na potrzeby klasyfikacji
mk_data=make_classification(n_samples=20, n_features=2, n_informative=2,
                         n_redundant=0, n_repeated=0, n_classes=3,
                         n_clusters_per_class=1, class_sep=2)
#dane uczące
data=mk_data[0]
#etykiety - na potrzeby wygenerowania macierzy konfuzji
labels=mk_data[1]

#macierz ilustrująca przebieg grupowania hierarchicznego
#single - miara najbliższego sąsiada dmin
#complete - miara najdalszego sasiada dmax
linkage_matrix = linkage(data, 'complete')
print 'Macierz grupowania hierarchicznego'
print linkage_matrix

#wykres ilustrujący dane w przestrzeni cech
plt.figure(1)
plt.title('Dane uczace')
plt.scatter(data[:,0],data[:,1], c=list(labels))
plt.show()

#Wygenerowanie dendrogramu
plt.figure(2)
plt.title("Dendrogram")
dendrogram(linkage_matrix)
plt.show()

#Odcięcie podziału na poziomie 3 grup
y = fcluster(linkage_matrix, 3, 'maxclust')
print 'Podział na trzy grupy'
print y

#Macierz konfuzji - porównanie uzyskanego podziału z etykietami
print confusion_matrix(labels,y-1)

Metody optymalizacji funkcji kryterialnej¶

Wspólną cechą algorytmów tej grupy jest poszukiwanie możliwie najlepszego podziału, minimalizując iteracyjnie pewną funkcję kryterialną. Funkcja kryterialna jest miernikiem jakości podziału zbioru, który pozwala spośród wszystkich możliwych wariantów podziału wybrać ten, który uznajemy za optymalny. Zwykle jest ona miarą dyspersji zbioru, na ogół ma postać sumy kwadratów odległości obiektów odpowiednich grup od prototypów je opisujących. Konstruowany podział zależy od przyjętej definicji podziału i w zależności od jej przyjęcia prowadzi do innego algorytmu grupowania. Pierwszą z możliwości jest przyjęcie definicji podziału twardego, która mówi o tym, że każdy obiekt musi należeć do dokładnie jednej grupy, ponadto żadna grupa nie może być pusta. Wynik działania algorytmu twardego grupowania, na \(K\) grup zwracany jest najczęściej w postaci tak zwanej macierzy podziału rozmiaru \(K\times N\), składającej się tylko z elementów równych 1 bądź 0, przy czym jedynka w \(i\)-tym wierszu i \(j\)-tej kolumnie oznacza, że obiekt \(x_j\) należy do klasy \(C_i\).

Algorytmy optymalizacji funkcji kryterialnej rozpoczynają swoje działanie od pewnego, na przykład losowego, podziału (to znaczy losowej macierzy podziału) i iteracyjnie zmierzają do podziału optymalnego, względem funkcji kryterialnej. W przypadku poszukiwania podziału twardego na ogół stosujemy funkcję kryterialną postaci:

gdzie symbolem \(d\left( {{x}_{j}},{{c}_{i}} \right)\) oznaczamy odległość obiektu \(x_j\) od grupy wyznaczonej przez prototyp \(c_i\), \(V\) jest zbiorem uczącym \(N\) elementowym, przez \(K\) oznaczamy liczbę grup w dokonywanym podziale, natomiast symbolem \(U\) oznaczamy macierz twardego podziału. Przyjęcie za miarę odległości między obiektem zbioru uczącego a prototypem grupy odległości euklidesowej, prowadzi do jednego z najbardziej popularnych algorytmów grupowania twardego opartego na minimalizacji powyższej funkcji, nazywanego algorytmem k-średnich (ang. k-means) [McQeen1967]. Algorytm przebiega według schematu zilustrowanego przez algorytm 18.

Algorytm inicjujemy macierzą twardego podziału, zatem pewnym podziałem początkowym. Każda iteracja polega na wyznaczaniu prototypów każdej grupy i przyporządkowaniu każdej próbki do grupy wyznaczonej przez najbliższy prototyp. W ten sposób uzyskujemy nowy podział. Powyższy algorytm jest wykonywany tak długo, dopóki macierz podziału ulega zmianom. Jest on zbieżny do lokalnego minimum funkcji kryterialnej, zalecane jest dlatego jego wielokrotne wykonanie z różnymi macierzami inicjalizacji. Z racji powolnej zbieżności często stosujemy kryterium stopu w postaci ustalenia maksymalnej liczby iteracji. Inicjalizacji algorytmu dokonywać możemy równoważnie za pomocą prototypów grup, gdyż zbiór prototypów determinuje podział zbioru. Istnieje wiele modyfikacji algorytmu \(k\)-średnich, przykładowo algorytm \(k\)-medoids, w którym prototypem grupy jest zawsze jeden z obiektów zbioru uczącego, na przykład położony najbliżej środka grupy. Wśród algorytmów tego typu, możemy wyróżnić algorytm PAM Istotą działania algorytmów twardego grupowania jest jednoznaczne przydzielenie każdego z obiektów do jednej grupy, co w niektórych przypadkach okazuje się istotnym ograniczeniem. Tego typu problemy rozwiązuje się przyjmując alternatywne definicje podziału zbioru na grupy. Przykładami takich definicji są podziały wyznaczone przez rozmytą i posybilistyczną macierz podziału. W pierwszym przypadku element \(u_{ij}\), czyli element rozmytej macierzy podziału, możemy odczytywać jako prawdopodobieństwo z jakim element \(x_j\) należy do grupy \(C_i\). W drugim przypadku wartość \(u_{ij}\) oznacza unormowany stopień podobieństwa wektora \(x_j\) należy do grupy \(C_i\). Rozmytą macierz podziału definiujemy poniżej.

W przypadku przyjęcia definicji podziału rozmytego zbioru dla algorytmów optymalizacji funkcji kryterialnej stosujemy najczęściej funkcję postaci:

gdzie \(U\) oznacza rozmytą macierz podziału, \(q\ge 1\) określa stopień rozmycia grup. Za wartość parametru \(q\) przyjmujemy na ogół 2. Przyjęcie wspomnianej funkcji i miary odległości

gdzie \(A\) jest dodatnio określoną macierzą symetryczną (może być jednostkowa - wtedy mamy odległość euklidesową) skutkuje jednym z najczęściej stosowanych algorytmów grupowania, znanym pod nazwą FCM (ang. Fuzzy C-Means) [Bezdek1981]. Schemat działania tej metody ilustruje algorytm 19.

Pokazano, że algorytm ten jest zbieżny do lokalnego minimum funkcji kryterialnej lub do punktu siodłowego. W związku z tym, algorytm jest zatrzymywany, gdy podział wyznaczony przez rozmytą macierz podziału się ustabilizuje, dlatego kryterium stopu algorytmu dotyczy odpowiedniej normy różnicy macierzy podziału w dwóch iteracjach i może być określone wzorem:

Omówione procedury grupowania podziałowego pozwalają na poprawną identyfikację grup, gdy mają one w przybliżeniu podobny kształt i rozmiar, prowadzą ponadto do utworzenia grup o zwartym eliptycznym kształcie, co bierze się z przyjętej miary odległości oraz z faktu, że grupa reprezentowana jest przez jeden prototyp (środek, medoid itp.). Znanych jest wiele modyfikacji i rozszerzeń algorytmu grupowania rozmytego FCM, na przykład algorytm Gustafssona Kessela [Gustafsson1979], o którym wspominamy ze względu na fakt, że zastosowana w nim dla każdej grupy osobno miara odległości obiektu od prototypu grupy pozwala na kreowanie grup o kształcie wydłużonym, na przykład liniowym, nie tylko w przybliżeniu eliptycznym. Ta miara odległości ważona jest macierzą kowariancji i-tej grupy i przedstawia się następująco:

W przypadku stosowania algorytmów rozmytych, w efekcie działania których nie otrzymujemy twardej macierzy podziału, jednoznacznie każdy obiekt zaklasyfikować można do grupy, w której prawdopodobieństwo jego klasyfikacji jest największe. W przypadku stosowania algorytmów rozmytych, proces w oparciu o który daną rozmytą macierz podziału przekształcamy w macierz podziału twardego, uzyskując jednoznaczny podział zbioru uczącego na grupy, nazywamy wyostrzaniem.

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from sklearn.cluster import KMeans
from sklearn import datasets
from sklearn.metrics import confusion_matrix

#wczytanie zbioru iris
iris = datasets.load_iris()
#macierz danych oraz znane etykiety klasowe
Data = iris.data
Classes = iris.target

#parametr algorytmu kMeans - podział na 3 grupy
kmeans=KMeans(n_clusters=3)

#uczenie algorytmu kMeans
kmeans.fit(Data)

#uzyskany podział
print 'Uzyskane etykiety podzialu dla zbioru iris:'
podzial=kmeans.labels_
print podzial

#ilustracja zbioru danych na wykresie 3d (trzy pierwsze atrybuty)
fig = plt.figure(1)
wykr = Axes3D(fig)
wykr.scatter(Data[:, 0], Data[:, 1], Data[:, 2], c=podzial.astype(np.float))
plt.show()

#Macierz konfuzji - porównanie uzyskanego podziału z etykietami
print confusion_matrix(podzial,Classes)

Algorytmy oparte na dopasowaniu modelu statystycznego¶

Metody grupowania bazujące na dopasowaniu modelu statystycznego zakładają, że zbiór obiektów uczących, a zatem również grupy, które możemy w tym zbiorze zidentyfikować, opisywane są przez pewien model statystyczny. Jest on najczęściej kombinacją rozkładów o znanej postaci parametrycznej. Zakładamy, że każdy obiekt zbioru uczącego jest elementem dokładnie jednej grupy, powiedzmy \(i\)-tej, rozkład elementów tej grupy opisany jest pewnym znanym rozkładem wyrażonym funkcją gęstości \(f\left( x|{{\theta }_{i}} \right)\), gdzie \({{\theta }_{i}}\) jest wektorem parametrów tego rozkładu. Oznaczając dodatkowo symbolem \(p_i\) prawdopodobieństwo wystąpienia elementu należącego do \(i\)-tej grupy, łączny rozkład wektorów zbioru uczącego \(V\) opisujemy funkcją gęstości postaci:

Składniki \(f\left( x|{{\theta }_{i}} \right)\) powyższego równania nazywamy komponentami modelu, natomiast wektor \(\Theta\) wektorem paramentów tego modelu. Na ogół przyjmujemy komponenty modelu w postaci wielowymiarowych rozkładów normalnych, natomiast wektor parametrów estymujemy metodą największej wiarygodności. W ogólnym przypadku, przy założeniu dowolnego rozkładu, nie zawsze funkcję wiarygodności można wyrazić w sposób jawny, dlatego stosujemy metody iteracyjne obliczania wartości oczekiwanych funkcji wiarygodności i jej maksymalizacji, w skrócie EM od angielskiego Expectation-Maximization. Algorytm EM rozpoczyna działanie od zainicjalizowania wektora parametrów modelu \(\Theta\), po którym następuje tak zwany etap \(E\), polegający na obliczeniu warunkowej wartości oczekiwanej logarytmu funkcji wiarygodności względem brakujących przynależności klasowych próbek. Kolejnym etapem jest etap \(M\), polegający na obliczeniu nowego wektora parametrów dla \(k\)-tej iteracji, maksymalizującego warunkową wartość oczekiwaną logarytmu funkcji wiarygodności. Etapy \(E\) oraz \(M\) są iteracyjnie powtarzane do osiągnięcia warunku stopu, którym jest na ogół pewien próg różnicy warunkowych wartości oczekiwanych logarytmu funkcji wiarygodności w sąsiednich iteracjach. Po osiągnięciu warunku stopu algorytm ostatecznie przydziela wektory zbioru uczącego do grup, dla której warunkowa wartość oczekiwana logarytmu funkcji wiarygodności jest największa spośród wszystkich opisywanych przez komponenty modelu.