Algorytm PAM

Algorytm PAM (ang. Partitioning Around Medoids) – metoda grupowania danych opracowana przez Leonarda Kaufmana oraz Petera J. Rousseeuwa w 1987 r. PAM jest jednym z algorytmów stosowanym w analizie skupień (ang. data clustering), będącej elementem tzw. klasyfikacji bez nadzoru (ang. unsupervised learning).

PAM jest realizacją metody k-medoidowej, czyli takiej techniki grupowania, która dzieli zbiór danych zawierających $n$ obiektów na $k$ grup (skupień, ang. cluster) znanych a priori. Przydatnym narzędziem do oceny jakości grupowania jest sylwetka (ang. silhoutette). Oblicza się ją dla każdego obiektu podlegającego grupowaniu. Na jej podstawie można stwierdzić, czy obiekty zostały prawidłowo zgrupowane, czy też trafiły do złych klastrów.

Działanie tego algorytmu zbliżone jest do działania algorytmu centroidów, z tą różnicą, że centroidy zostają tu zastąpione przez medoidy, czyli najbardziej centralne obiekty ze zbioru danych reprezentujące daną grupę, dla których odległość od wszystkich pozostałych elementów wewnątrz danej grupy jest minimalna. Algorytm ten dąży do minimalizacji sumy odległości wszystkich elementów niebędących medoidami od najbliższych im medoidów.

Kolejną różnicą między algorytmem centroidów oraz metodą k-medoidową jest sposób definiowania dystansu między obserwacjami, bowiem algorytm PAM używa norm Manhattan zamiast odległości euklidesowej.

Zaletą tego algorytmu jest jego odporność na obserwacje odstające (ang. outliers) oraz szumy występujące w danych (ang. robustness). Główną wadą algorytmu PAM jest brak możliwości zastosowania tej metody dla dużych zbiorów danych (powyżej 65536 obserwacji).

Przebieg algorytmu PAM

Przebieg algorytmu PAM składa się z dwóch faz: fazy budowy (ang. build phase) oraz fazy zamiany (ang. swap phase).

Faza budowy

1. Podziel zbiór danych na $k$ skupień z przypisanymi $k$ medoidami

2. Oblicz macierz odległości pomiędzy medoidami oraz pozostałymi obserwacjami

3. Przypisz każdą z obserwacji (nie będącą medoidem) do najbardziej zbliżonego skupienia

Faza zamiany

4. Przy użyciu iteracji zastąp jeden z medoidów jednym z niemedoidów i sprawdź, czy odległości wszystkich elementów niebędących medoidami od najbliższych im medoidów są mniejsze

5. Jeśli nastąpiła przynajmniej jedna zamiana medoidów, przejdź do punktu 3. Jeśli nie, zakończ algorytm.

Przykładowe zastosowanie algorytmu PAM

W następującym przykładzie podzielono zbiór składający się z $n$ = 15 obiektów na $k$ = 2 grupy.

Wykres 1.1 – Rozkład danych

x1	7	8
x2	8	5
x3	7	3
x4	6	3
x5	2	4
x6	7	3
x7	1	2
x8	7	1
x9	4	4
x10	5	5
x11	4	2
x12	1	1
x13	5	4
x14	4	9
x15	9	2

Krok 1

Dwie obserwacje: x₆ = (7,3) i x₉ = (4,4) zostały wybrane jako centra grup – medoidy. Odległości obliczone przy użyciu normy Manhattańskiej, tzn. jako suma wartości bezwzględnych różnic współrzędnych punktów x_i oraz medoidów, prezentują się następująco:

Wykres 1.2 – Grupowanie. Krok 1

		Odległość od x6 = (7,3)	Odległość od x9 = (4,4)
x1	(7,8)	5	7
x2	(8,5)	3	5
x3	(7,3)	0	4
x4	(6,3)	1	3
x5	(2,4)	6	2
x6	(7,3)	0	4
x7	(1,2)	7	5
x8	(7,1)	2	6
x9	(4,4)	4	0
x10	(5,5)	4	2
x11	(4,2)	4	2
x12	(1,1)	8	6
x13	(5,4)	3	1
x14	(4,9)	9	5
x15	(9,2)	3	7
∑odległości		14	23

Punkty (7,8), (8,5), (7,3) (6,3), (7,1) i (9,2) przynależą do grupy 1, w której medoid to x₆ = (7,3) ponieważ są w mniejszej odległości od tego punktu, niż od drugiego medoidu x₉ = (4,4).

Krok 2

Następnie przy pomocy iteracji należy sprawdzić, czy lepszym medoidem nie jest inny punkt ze zbioru. Metoda obliczeń jest analogiczna do stosowanej w kroku 1.

		Odległość od x6 = (7,3)	Odległość od x13 = (5,4)
x2	(8,5)	3	4
x3	(7,3)	0	3
x4	(6,3)	1	2
x5	(2,4)	6	3
x6	(7,3)	0	3
x7	(1,2)	7	6
x8	(7,1)	2	5
x9	(4,4)	4	1
x10	(5,5)	4	1
x11	(4,2)	4	3
x12	(1,1)	8	7
x13	(5,4)	3	0
x14	(4,9)	9	6
x15	(9,2)	3	6
∑odległości		14	27

		Odległość od x2 = (8,5)	Odległość od x9 = (4,4)
x1	(7,8)	4	7
x2	(8,5)	0	5
x3	(7,3)	3	4
x4	(6,3)	4	3
x5	(2,4)	7	2
x6	(7,3)	3	4
x7	(1,2)	10	5
x8	(7,1)	5	6
x9	(4,4)	5	0
x10	(5,5)	3	2
x11	(4,2)	7	2
x12	(1,1)	11	6
x13	(5,4)	4	1
x14	(4,9)	8	5
x15	(9,2)	4	7
∑odległości		19	26

Algorytm PAM dąży do minimalizacji sumy odległości wszystkich elementów niebędących medoidami od najbliższych im medoidów. Punkty x₁₃ oraz x₂ okazują się być gorszymi medoidami, niż punkty x₆ i x_9, dla których suma odległości wszystkich elementów jest najmniejsza.

W celu oceny jakości grupowania należy zastosować narzędzie zwane sylwetką (ang. silhouette). Oblicza się ją dla każdego obiektu $i$ podlegającego grupowaniu. We wzorze $a(i)$ oznacza średnią odległość (niepodobieństwo ang. dissimilarity) od reszty obserwacji z tej samej grupy $c$ (ang. cluster). Im wartość $a(i)$ jest mniejsza, tym obserwacja $i$ jest bardziej podobna do danej grupy $c.$ Następnie wyznacza się odległość obserwacji $i$ do pozostałych grup punktów, jako średnią odległość obserwacji $i$ od wszystkich punktów z danej grupy $c.$ Najniższa średnia odległość obserwacji $i$ od każdej z grup $c,$ do której $i$ nie należy oznacza się jako $b(i).$ Sylwetkę $s(i)$ wyznacza się ze wzoru:

$s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}$

gdy $s(i)$ jest bliskie 1 oznacza to, że obserwacje zostały poprawnie zgrupowane, wartości $s(i)$ bliskie 0 i ujemne oznaczają duże niepodobieństwo.

Do ustalenia liczby skupień można wykorzystać analizę sylwetek podziału. Poprzez inkrementację liczby grup $c$ (począwszy od $k$ = 2) oblicza się wartość wskaźnika sylwetek i wybiera takie $k,$ dla którego średnia szerokość sylwetki (ang. average silhouette width) jest największa.

Posłużenie się sylwetką na powyższym zbiorze danych wykazało, że optymalna ilość skupień wynosi $k$ = 4.

Wykres 2.1 – Średnia szerokość sylwetki z dwoma i czterema grupami

A zatem medoidami w powyższym zbiorze $n$ = 15 obiektów pogrupowanych na $k$ = 4 skupień są obserwacje: x₆, x₇, x₉ i x₁₄. Poniżej przedstawiona jest analiza graficzna.

Wykres 2.2 – Poprawne grupowanie przy wykorzystaniu algorytmu PAM

Bibliografia

• L. Kaufman, P.J. Rousseeuw (1987), Clustering by means of Medoids, in Statistical Data Analysis Based on the Norm and Related Methods, edited by Y. Dodge, North-Holland, s. 405–416.
• A. Struyf, M. Hubert, P. Rousseeuw (1997), Clustering in an object-oriented environment, „Journal of Statistical Software”, 1(4), s. 1–30.
• Wykresy zostały opracowane w języku i środowisku R.