Metody odkrywania wiedzy: wykład 7
Grupowanie

Paweł Cichosz


Date: 2001/2002

Wykład dotyczy metod odkrywania wiedzy polegających na grupowaniu danych. Wynikiem grupowanie jest wyróżnienie w danych grup podobnych przykładów i wygenerowanie opisów tych grup, pozwalających na klasyfikowanie do nich dowolnych nowych przykładów.

Motywacja dla grupowania

Grupowanie jest rodzajem uczenia się bez nadzoru, w którym dane trenujące zawierają opisy przykładów w postaci wartości atrybutów, ale bez określonych kategorii pojęcia docelowego. Nazwaliśmy je wcześniej tworzeniem pojęć -- w odróżnieniu od uczenia się pojęć -- gdyż w tym przypadku zadanie systemu uczącego się obejmuje samodzielne wyznaczenie najbardziej odpowiednich kategorii przez związanie ich z pewnymi grupami przykładów trenujących, a następnie wyznaczenie hipotezy pozwalającej do tych kategorii klasyfikować dowolne nowe przykłady. Aby podkreślić możliwość klasyfikacji nowych przykładów, tak jak klasyfikuje się przykłady za pomocą pojęć, będziemy mówić o grupowaniu pojęciowym.

Mówienie w takiej sytuacji o odkrywaniu wiedzy może się wydawać problematyczne. Dlatego dyskusję metod grupowania poprzedzimy uzasadnieniem, że grupowanie faktycznie reprezentuje pewną wiedzę. Istotne dla tego uzasadnienia jest to, że podział na grupy i odpowiadające im kategorie nie jest arbitralny, lecz oparty na podobieństwie przykładów. Podobieństwo, jak zobaczymy, umożliwia wnioskowanie, a tam, gdzie jest możliwe wnioskowanie, mamy ponad wszelką wątpliwość do czynienia z wiedzą.

Grupowanie na podstawie podobieństwa

Na razie poprzestaniemy na nieformalnym rozumieniu podobieństwa przykładów: jest jasne, że za podobne uznalibyśmy takie przykłady, dla których identyczne lub podobne są wartości niektórych atrybutów. Dokładniej, dla atrybutów nominalnych jest sens mówić wyłącznie o identyczności, ale dla atrybutów porządkowych i ciągłych można mówić o podobieństwie w sensie odległości między wartościami.

Pod adresem dowolnych metod grupowania kierować będziemy postulat, aby każdy przykład był bardziej podobny do wszystkich przykładów zaliczonych do tej samej co on kategorii niż do któregokolwiek przykładu zaliczonego do innej kategorii, gdyż w przeciwnym przypadku przynależność przykładu do kategorii nie będzie o nim mówić nic dostatecznie pewnego, aby można było mówić o wyciąganiu wniosków. Oznacza to, po pierwsze, że w ramach każdej kategorii przykłady powinny być do siebie maksymalnie podobne, oraz, po drugie, że przykłady różnych kategorii powinny być maksymalnie zróżnicowane.

Wnioskowanie na podstawie podobieństwa

W przypadku uczenia się pojęć znaleziona na podstawie przykładów trenujących hipoteza może być następnie stosowana do klasyfikowania dowolnych przykładów. Właśnie ten proces klasyfikowania -- ustalania (prawdopodobnych) kategorii przykładów -- jest wnioskowaniem wykorzystującym wiedzę uzyskaną w trakcie uczenia się. Za jej pomocą z przesłanek, jakimi są wartości atrybutów przykładu, wywodzi się jego kategorię jako konkluzję. Z kolei w przypadku grupowania proces uczenia się powoduje wyznaczenie pewnego podziału zbioru trenującego na kategorie. Jeśli dodatkowo przyjmiemy, że ten podział jest indukcyjnie uogólniany, to można stosować go do całej dziedziny, czyli klasyfikować za jego pomocą również nowe przykłady. Ponieważ podział na kategorie jest oparty na podobieństwie, z faktu przynależności przykładu do kategorii można wyciągnąć wniosek o jego podobieństwie do innych przykładów tej samej kategorii. W pewnych sytuacjach może to być użyteczna informacja.

Możemy sobie wyobrazić, po pierwsze, że przykłady to dla nas coś więcej niż tylko wektory wartości atrybutów. W pewnych dziedzinach przykłady mogą mieć ponadto pewną znaczącą tożsamość, nie reprezentowaną przez opisujące je atrybuty, które opisują ich pewne cechy, ale nie w pełni je identyfikują. Wówczas fakt, że pewne dwa przykłady są podobne i należą do jednej kategorii, a inne dwa przykłady są niepodobne i należą do różnych kategorii, może dostarczać ważnej informacji, gdyż mówi o pewnych konkretnych obiektach z własną tożsamością.

Jest też inna możliwość, występująca wtedy, kiedy dla niektórych przykładów wartości niektórych atrybutów nie są znane. Dla takiego przykładu może być wyznaczona najbardziej odpowiednia kategoria na podstawie znanych wartości atrybutów, a następnie z jego przynależności do tej kategorii można wywnioskować prawdopodobne wartości pozostałych atrybutów. Widać stąd, że możliwe jest wnioskowanie na podstawie przynależności przykładów do określonych kategorii utworzonych przez proces grupowania, o ile odzwierciedlają one podobieństwo przykładów, a w związku z tym tworzone przez ten proces pojęcia można traktować jako wiedzę.

Od grupowania do pojęć

Aby wnioskowanie na podstawie wyników grupowania było możliwe, konieczny jest nie tylko odpowiedni podział przykładów trenujących na kategorie -- grupy utworzone według ich podobieństwa. Niezbędny jest również pewien opis każdej grupy, dzięki któremu możliwe będzie klasyfikowanie nowych przykładów. Ta obserwacja prowadzi do wyróżnienia dwóch podzadań w rozważanym przez nas zadaniu grupowania pojęciowego:

podział:
podzielenie przykładów trenujących na grupy, którym zostaną przypisane kategorie tworzonego pojęcia,
opis:
scharakteryzowanie każdej z wyróżnionych grup, czyli wygenerowanie hipotezy dla odpowiedniego pojęcia wielokrotnego, która będzie mogła być użyta do klasyfikowania nowych przykładów.

Hipotezy w grupowaniu

Przypomnijmy sobie, że w przypadku grupowania za hipotezę uznajemy funkcję $ h:X\mapsto C_h$, która odwzorowuje przykłady z dziedziny na związany z tą hipotezą zbiór kategorii $ C_h$. Utworzenie takiej hipotezy oznacza wyznaczenie zbioru kategorii przez podział danych trenujących na grupy oraz wyznaczenie opisu poszczególnych kategorii, dzięki któremu będzie można do tego zbioru kategorii klasyfikować dowolne przykłady.

Grupowanie dla atrybutów ciągłych

Inaczej niż dotąd dla innych metod odkrywania wiedzy, zaczniemy rozważania od założenia, że wszystkie uwzględnianie przy grupowaniu atrybuty są ciągłe. Wynika to z faktu, że pewne proste, klasyczne algorytmy grupowania przystosowane są do działania tylko z ciągłymi przestrzeniami atrybutów. Algorytmy te są oparte na liczbowych miarach odległości między przykładami, które w najbardziej naturalny sposób są określone dla atrybutów ciągłych.

Odległość

W zależności od właściwości dziedziny i konkretnego zastosowania właściwe mogą być różne miary odległości między przykładami, a ściślej między wektorami wartości atrybutów ciągłych. Tu poprzestaniemy na prostej metryce euklidesowej, zgodnie z którą dla dwóch przykładów $ x_1$ i $ x_2$ odległość określona jest następująco:

$\displaystyle \delta(x_1,x_2) = \sqrt{\sum_{i=1}^n(a_i(x_1)-a_i(x_2))^2}$. (1)

Można do niej dodatkowo wprowadzić współczynniki skalujące, przypisujące poszczególnym atrybutom różny wpływ na odległość:

$\displaystyle \delta(x_1,x_2) = \sqrt{\sum_{i=1}^n\alpha_i^2(a_i(x_1)-a_i(x_2))^2}$. (2)

Reprezentacja kategorii

W przypadku, gdy każda kategoria-grupa składa się z przykładów opisywanych przez wektory liczb rzeczywistych będących wartościami atrybutów ciągłych, naturalna jest reprezentacja kategorii również przez wektory liczb rzeczywistych:

$\displaystyle \mu^d = \langle \mu^d_1,\mu^d_2,\dots,\mu^d_n\rangle \in A_1\times A_2\times\dots\times A_n$. (3)

Przyjętą miarę odległości między przykładami można równie dobrze wykorzystać do mierzenia odległości między dowolnym przykładem $ x$ a wektorem $ \mu^d$ reprezentującym pewną kategorię $ d$, np. dla zwykłej metryki euklidesowej:

$\displaystyle \delta(x,d) = \sqrt{\sum_{i=1}^n(a_i(x)-\mu^d_i)^2}$, (4)

Naturalne wydaje się przyjęcie, że wektory reprezentujace poszczególne kategorie będą złożone z średnich wartości poszczególnych atrybutów dla przykładów zaliczonych do odpowiedniej grupy. Spełniający ten warunek wektor $ \mu^d$ nazywany jest wektorem centralnym lub środkowym (czasem krótko: centrum) kategorii $ d$.

W świetle powyższych ustaleń dowolna hipoteza $ h:X\mapsto C_h$ może być reprezentowana zbiór wektorów wartości atrybutów $ \mu^d$ dla każdej kategorii $ d\in C_h$. Dowolny przykład $ x$ można wówczas klasyfikować do najbliższej mu kategorii następująco:

$\displaystyle h(x) = \mathrm{arg}\min_{d\in C_h}\delta(x,d)$. (5)

Algorytm $ k$ środków

Prosty algorytm grupowania używający przedstawionej wyżej reprezentacji kategorii może polegać na losowym wybraniu ustalonej liczby przykładów i utworzeniu dla każdego z nich jednoelementowej grupy. Wówczas wektor wartości atrybutów każdego przykładu staje się początkowym wektorem środkowym grupy. Następnie przetwarzając kolejno wszystkie przykłady trenujące można dla każdego z nich znaleźć najbliższą grupę i dołączyć go do niej. Po zakończeniu tego procesu można wyznaczyć nowy wektor centralny każdej grupy przez obliczenie odpowiednich średnich, a następnie -- ponowić go, czyli znów dla każdego przykładu znaleźć najbliższą grupę, następnie ponownie zmodyfikować wektory środkowe itd., aż do uzyskania stabilizacji podziału na grupy, kiedy w kolejnych iteracjach żaden przykład nie zmienia swojej przynależności. Ta koncepcja realizowana jest przez algorytm $ k$ środków, opisany poniżej.


\begin{algorithmic}[1] \FUNCTION $\textit{grupuj-$k$-środków}(T, k)$\INPUTARGS\m... ...G_k$\ w kolejnych iteracjach}; \RET $\mu^1,\mu^2,\dots,\mu^k$. \end{algorithmic}

Przedstawiony algorytm po uzyskaniu zbieżności, czyli braku zmiany przynależności przykładów do grup, zwraca wektory centralne reprezentujące kategorie. Zgodnie z wcześniejszą dyskusją łącznie reprezentują one hipotezę grupowania $ h:X\mapsto\{1,2,\dots,k\}$.

Dynamiczne ustalanie liczby kategorii

Niedogodnością praktyczną algorytmu $ k$ środków jest konieczność ustalenia z góry parametru $ k$, liczby tworzonych kategorii, co może być niekiedy kłopotliwe. Można wskazać co najmniej trzy sposoby przezwyciężenia tej trudności:

Wielokrotne uruchamianie.

Rozwiązanie to jest zupełnie zadowalające, jeśli zwiększony nakład obliczeń nie jest problemem, pozostaje tylko ustalić kryterium, według którego będzie wybierane najlepsze grupowanie. Będzie o tym mowa dalej.

Grupowanie hierarchiczne.

Binarne grupowanie hierarchiczne wymaga w zamian określenia swego rodzaju kryterium stopu (podobnego do kryterium stopu w przypadku budowania drzewa decyzyjnego), dzięki któremu będzie można rozstrzygnąć, kiedy dzielenie grup na podgrupy ma być zatrzymane. To kryterium można jednak również sprowadzić do kryterium oceny jakości, porównującego jakość jednej ,,dużej'' grupy z dwiema mniejszymi, na które można ją podzielić.

Adaptacja liczby grup.

Realizacja adaptycyjnej zmiany liczby kategorii wymaga wprowadzenia do algorytmu, po zakończeniu etapu przypisywania przykładów trenujących do poszczególnych grup, weryfikacji polegającej na sprawdzeniu, czy

Zróżnicowanie grup można mierzyć za pomocą odchyleń standardowych wartości atrybutów -- jeśli np. średnie odchylenie standardowe przekracza ustalony parametr, uznajemy grupę za zbyt zróżnicowaną, co pociąga za sobą jej podział na dwie nowe grupy, dla których początkowe wektory centralne w najprostszy sposób można wyznaczyć wybierając dowolne (a najlepiej, możliwie maksymalnie różne od siebie) przykłady z dzielonej grupy. Z kolei podobieństwo między dwoma grupami można mierzyć odległością przykładów z tych grup, przy czym spotykane są co najmniej trzy koncepcje takiej oceny podobieństwa: Pierwszy wariant jest najprostszy do realizacji i zadowalający w większości przypadków. Grupy, które według przyjętego kryterium są zbyt podobne, można połączyć, i dla nowej grupy określić wektor środkowy w zwykły sposób przez obliczenie średnich wartości atrybutów wszystkich przykładów z obu łączonych grup.

Grupowanie dla atrybutów dyskretnych

Algorytm $ k$ średnich i jego zmodyfikowane wersje mogą być przystosowane w pewnym zakresie również do grupowania przykładów z atrybutami dyskretnymi, ale wymaga to innego określenia odległości między przykładami oraz zastąpienia operacji uśredniania przy wyznaczaniu wektorów środkowych operacją wybierania wartości najczęściej występującej. Oprócz tej możliwości znane są jednak bardziej wyrafiniwane algorytmy grupowania dla atrybutów dyskretnych, spośród których na uwagę zasługuje zwłaszcza algorytm COBWEB.

Każdy rodzaj indukcyjnego uczenia się można traktować jako przeszukiwanie przestrzeni hipotez w celu znalezienia hipotezy spełniającej pewne kryteria. Algorytm COBWEB szczególnie dobrze odpowiada takiemu spojrzeniu na uczenie się, jego działanie można bowiem postrzegać jako przeszukiwanie przestrzeni możliwych grupowań dla zbioru trenującego. Aby ten proces przeszukiwania dokładnie opisać, należy podać:

Dyskusję tych zagadnień rozpoczniemy od przedstawienia funkcji oceny, gdyż jej postać będzie miała wpływ na przyjętą reprezentację grupowania, od której z kolei zależą operatory i strategia ich stosowania.

Funkcja oceny grupowania

Funkcja oceny jakości grupowania stosowana w algorytmie COBWEB stara się mierzyć przydatność grupowania: jej wartość zależy od tego, mówiąc nieformalnie, z jakim prawdopodobieństwem na podstawie znajomości przynależności przykładu do grupy można ,,odgadywać'' wartości jego atrybutów. Wykorzystywane są w tym celu związane z każdą grupą oszacowania prawdopodobieństw wartości atrybutów.

Przyjmijmy, że ocenie podlega pewna hipoteza reprezentująca grupowanie $ h:X\mapsto C_h$, przy czym $ C_h$ jest zbiorem kategorii hipotezy $ h$. Załóżmy, że przykłady wybierane są z dziedziny $ X$ zgodnie z określonym na niej rozkładem prawdopodobieństwa $ \Omega$. Ponadto jak zwykle przyjmiemy, że na dziedzinie określone są atrybuty $ a_i:X\mapsto A_i$ dla $ i=1,2,\dots,n$, przy czym zgodnie z wcześniejszą zapowiedzią ograniczymy się do atrybutów dyskretnych.

Dla każdej kategorii $ d\in C_h$ interesować nas będzie zbiór prawdopodobieństw postaci $ \mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$ dla $ i=1,2,\dots,n$ i $ v\in A_i$, czyli prawdopodobieństwa tego, że atrybut $ a_i$ ma dla wybranego zgodnie z rozkładem $ \Omega$ przykładu $ x\in X$ wartość $ v$, jeśli wiadomo, że przykład ten został w grupowaniu zaliczony do kategorii $ d$. Według jednej z możliwych interpretacji prawdopodobieństwa tej postaci mogą reprezentować stopień podobieństwa przykładów w ramach kategorii $ d$. Nieformalne uzasadnienie takiej interpretacji jest następujące. Jeśli dla wszystkich lub znacznej części atrybutów prawdopodobieństwa $ \mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$ są duże dla jednej lub kilku wartości $ v$ oraz małe dla pozostałych wartości, to pozwala to, wiedząc, że przykład jest zaliczony do kategorii $ d$, z dużą dokładnością przewidywać wartości jego atrybutów. Inaczej mówiąc, im większe wartości osiągają te prawdopodobieństwa, tym bardziej podobne są przykłady zaliczone do tej samej kategorii. Z kolei podobieństwo przykładów w ramach kategorii pozwala, na podstawie przynależności przykładu do takiej kategorii, trafnie przewidywać jego wartości atrybutów.

Powyższe prawdopodobieństwa używane są w funkcji oceny algorytmu COBWEB w następujący sposób:

\begin{displaymath}\begin{split}\vartheta(h) ={}& \frac{1}{\vert C_h\vert}\sum_{... ... \mathrm{Pr}_{x\in\Omega}(a_i(x)=v)^2\Bigg]\text{.} \end{split}\end{displaymath} (6)

Jej interpretację ułatwia następujące rozumowanie. Rozważmy losowo wybrany przykład $ x$ zaliczony do kategorii $ d$ i załóżmy, że stoi przed nami zadanie odgadywania wartości poszczególnych atrybutów dla tego przykładu, na podstawie znajomości prawdopodobieństw $ \mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$ dla wszystkich $ i=1,2,\dots,n$ i $ v\in A_i$. Decyzje możemy podejmować na przykład drogą losowania, dla atrybutu $ a_i$ odgadując z prawdopodobieństwem $ p_i(v)$, że ma on wartość $ v$. Wówczas prawdopodobieństwo poprawnego odgadnięcia wartości $ a_i(x)$ wynosi oczywiście

$\displaystyle \sum_{v\in A_i}p_i(v)\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$, (7)

a suma

$\displaystyle \sum_{i=1}^n\sum_{v\in A_i} p_i(v)\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$ (8)

jest oczekiwaną liczbą ,,trafień'' przy odgadywaniu wartości wszystkich atrybutów. Jeśli przyjmiemy pewną szczególną probabilistyczną strategię zgadywania, nazywaną dopasowywaniem prawdopodobieństw, zgodnie z którą każdą wartość należy przewidywać z prawdopodobieństwem równym prawdopodobieństwu jej faktycznego wystąpienia, to otrzymujemy $ p_i(v)=\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$, co pozwala interpretować sumę

$\displaystyle \sum_i\sum_j\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)^2$ (9)

występującą we wzorze na funkcję oceny jako oczekiwaną liczbę wartości atrybutów, które mogą być poprawnie przewidziane dla dowolnego przykładu zaliczonego do kategorii $ d$ zgodnie z tą strategią. Z kolei suma

$\displaystyle \sum_{i=1}^n\sum_{v\in A_i}\mathrm{Pr}_{x\in\Omega}(a_i(x)=v)^2$ (10)

może być analogicznie interpretowana jaka liczba takich trafnie przewidywanych wartości atrybutów bez uwzględniania kategorii, do której został zaliczony przykład. Różnica określa więc wzrost oczekiwanych trafnych przewidywań wynikający ze znajomości grupowania. Całość jest mnożona przez normalizujący czynnik $ \frac{1}{\vert C_h\vert}$, który ma na celu skompensowanie wpływu liczby kategorii grupowania na ocenę jego właściwości predykcyjnych.

Reprezentacja grupowania

W systemie COBWEB tworzone jest zawsze grupowanie hierarchiczne. Oznacza to, że podział na grupy następuje na różnych poziomach szczegółowości. Na poziomie najbardziej ogólnym, który nazwiemy poziomem 0, można przyjąć, że wszystkie przykłady wchodzą w skład jedynej kategorii, która dzieli się następnie na poziomie $ 1$ na pewną liczbę podkategorii. Każda z nich ma dalej na poziomie $ 2$ swoje podkategorie i w ten sposób coraz bardziej szczegółowy podział może być kontynuowany; jego naturalny kres następuje, kiedy zostaną uzyskane kategorie obejmujące tylko jeden przykład trenujący, gdyż wówczas nie może być przeprowadzony dalszy podział. Dla każdej kategorii jej podkategorie są oczywiście parami rozłączne, a każdy przykład kategorii macierzystej należy do dokładnie jednej podkategorii potomnej.

Naturalną reprezentacją hierarchicznego grupowania jest drzewo, w którym węzły odpowiadają kategoriom. W związku z tym w węzłach są przechowywane służące do reprezentowania kategorii oszacowania rozkładów prawdopodobieństw. Węzły potomne odpowiadają podkategoriom kategorii, której odpowiada ich węzeł macierzysty. W korzeniu drzewa znajduje się węzeł odpowiadający kategorii poziomu 0, która zawiera wszystkie przykłady trenujące. Liśćmi drzewa są zazwyczaj węzły kategorii jednoelementowych, które nie mają węzłów potomnych, o ile nie zdecydujemy się zatrzymać podziału na podkategorie wcześniej, na przykład po osiągnięciu kategorii kilkuelementowych. Dla wygody będziemy mówić, że węzły drzewa zawierają przykłady lub że dodajemy przykłady do węzłów, mając na myśli kategorie związane z tymi węzłami. Jak zobaczymy, nie wiąże się z tym fizyczne przechowywanie ani kopiowanie przykładów.

Hierarchiczne grupowanie reprezentowane za pomocą drzewa nie jest oceniane jako całość, globalnie -- funkcja oceny jakości jest zawsze stosowana tylko lokalnie, do oceny podziału kategorii na podkategorie, w celu wyboru podziału o najlepszych właściwościach. Taki sposób oceniania dotyczy więc nie całego drzewa, ale jego poszczególnych węzłów, z których każdy oceniany jest ze względu na swoje węzły potomne, wyznaczające podział jego kategorii na podkategorie. Można więc przyjąć, że z każdym węzłem drzewa grupowania jest związana pewna hipoteza, opisująca podział kategorii odpowiadającej temu węzłowi na podkategorie. Ocenie podlega jakość takich hipotez.

Aby było możliwe stosowanie funkcji oceny, w węzłach muszą być przechowywane liczniki umożliwiające oszacowanie używanych do jej obliczania prawdopodobieństw: liczbę przykładów zaliczonych do kategorii związanej z węzłem oraz, dla każdego atrybutu, liczbę wystąpień wszystkich jego wartości. Prawdopodobieństwa mogą być szacowane z wykorzystaniem takich liczników w najprostszy sposób, za pomocą częstości. Ponieważ, jak wkrótce zobaczymy, algorytm działa w trybie inkrementacyjnym i przetwarza zawsze jeden przykład jednorazowo, liczniki w trakcie budowania drzewa grupowania uwzględniają tylko dotychczas przetworzone przykłady i są modyfikowane w trakcie przetwarzania kolejnych przykładów. Dodanie przykładu do węzła drzewa, które jest jedną z podstawowych operacji algorytmu COBWEB, polega wyłącznie na dokonaniu odpowiedniej modyfikacji liczników.

Operatory

Algorytm COBWEB przetwarzając kolejne przykłady trenujące może modyfikować drzewo grupowania stosując cztery następujące operatory:

Operatory mogą być stosowane do węzłów na różnych poziomach drzewa. Dokładniej, jeśli podczas przetwarzania przykładu na pewnym poziomie został on umieszczony w istniejącym lub nowo utworzonym węźle, to następnie, dla zachowania poprawności drzewa jako reprezentacji hierarchicznego grupowania, musi on zostać odpowiednio potraktowany na poziomie jego węzłów potomnych itd. Omawiając działanie poszczególnych operatorów założymy, że przykład został dodany do pewnego węzła i obecnie należy postanowić, co się z nim stanie na poziomie jego węzłów potomnych.

Umieszczenie przykładu w istniejącej kategorii

Umieszczenie nowego przykładu w istniejącej kategorii jest najprostszym i najbardziej naturalnym sposobem modyfikacji grupowania. Stosując ten operator należy oczywiście wybrać taką kategorię, dla której po dodaniu do niej nowego przykładu uzyskany podział będzie możliwie najlepszy. W tym celu przykład jest tymczasowo dodawany do każdego węzła potomnego, po czym obliczana jest wartość funkcji oceny dla uzyskanego w ten sposób podziału kategorii macierzystej na podkategorie. Przykład pozostawiany jest ostatecznie w węźle, dla którego otrzymano największą wartość tej funkcji. Jest on nazywany najlepszym pojemnikiem dla przykładu.

Utworzenie nowej kategorii

Umieszczenie przykładu w najlepszym dla niego pojemniku nie zawsze musi prowadzić do najlepszego grupowania, jakie da się uzyskać. Najprostszy alternatywny operator polega na utworzeniu nowej kategorii wyłącznie dla tego przykładu. Dokładniej, tworzony jest nowy liść potomny zawierający tylko przetwarzany przykład. Dzięki temu operatorowi liczba kategorii na każdym poziomie drzewa może się zwiększać.

Połączenie kategorii

Grupowania uzyskiwane za pomocą stosowania wyłącznie dwóch pierwszych operatorów mogą być w wielu przypadkach zupełnie satysfakcjonujące: każdy kolejny przykład jest albo umieszczany w tej spośród istniejących już kategorii, do której najlepiej pasuje, albo we własnej nowej jednoelementowej kategorii, jeśli nie pasuje dość dobrze do żadnej z nich. Wyniki uzyskiwane w ten sposób są jednak w zbyt dużym stopniu uzależnione od kolejności, w jakiej są podawane przykłady, a zależności takiej chcielibyśmy uniknąć. Jej osłabieniu służą operatory połączenia i podziału kategorii, które mogą niekiedy umożliwić uzyskanie lepszego grupowania niż wynikające z użycia któregoś z dwóch poprzednich operatorów.

Połączenie kategorii polega na wybraniu dwóch węzłów drzewa i zastąpieniu ich jednym węzłem, reprezentującym połączoną kategorię, do której następnie dodaje się przetwarzany aktualnie przykład. Operator połączenia powoduje zastąpienie tych dwóch węzłów jednym nowym węzłem, dla którego przechowywane w nim liczniki są równe sumie odpowiednich liczników z dwóch łączonych węzłów. Węzły te nie są jednak likwidowane, lecz stają się potomkami węzła powstałego z ich połączenia.

Chociaż ewentualne połączenie można w zasadzie rozważać dla dowolnych par węzłów, byłoby to dość kosztowne. W algorytmie COBWEB stosuje się w związku z tym heurystykę, zgodnie z którą podczas przetwarzania przykładu możliwość połączenia jest brana pod uwagę tylko dla dwóch węzłów, będących najlepszymi pojemnikami dla tego przykładu.

Podział kategorii

Podział kategorii jest operacją w przybliżeniu odwrotną do połączenia. Przybliżenie polega tu na tym, że o ile połączenie jest zawsze stosowane tylko dla wybranych dwóch węzłów, o tyle podział może prowadzić do zastąpienia jednej kategorii ich większą liczbą. Dokładniej, w wyniku podziału kategoria jest zastępowana przez wszystkie swoje podkategorie albo, inaczej mówiąc, węzeł jest zastępowany przez wszystkie swoje węzły potomne. Nie są przy tym potrzebne żadne obliczenia, a jedynie prosta manipulacja na strukturze drzewa. Po dokonaniu tego podziału przykład ten może być umieszczony w najlepszym pojemniku spośród uzyskanych w wyniku podziału węzłów, chociaż w algorytmie, który przedstawimy, jest stosowane nieco bardziej ogólne rozwiązanie.

Strategia sterowania

Podsumowaniem powyższej dyskusji jest konkretny zapis strategii, zgodnie z którą wybierane są przedstawione operatory. Efektem zastosowania każdego operatora jest umieszczenie przykładu w pewnej kategorii, istniejącej poprzednio, nowo utworzonej albo powstałej w wyniku połączenia lub podziału. Na pytanie, który z możliwych operatorów należy wybrać, odpowiedź jest dość naturalna: ten, który prowadzi do uzyskania najlepszego grupowania, czyli takiego, dla którego osiąga się największą wartość funkcji oceny.

Przy prezentacji operatorów zaznaczyliśmy, że ich działanie dotyczy zawsze pewnego ustalonego poziomu drzewa, na którym należy umieścić przetwarzany przykład w odpowiedniej kategorii. Sposób przemieszczania się w głąb drzewa jest przy tym zupełnie oczywisty. Na początku przykład zawsze musi być umieszczony w jedynej kategorii poziomu 0, której węzeł znajduje się w korzeniu drzewa. Potem następuje przejście na kolejne niższe poziomy; na każdym z nich w celu wyboru właściwego operatora jest rozpatrywany zbiór węzłów potomnych węzła, w którym przykład został umieszczony na poprzednim (wyższym) poziomie. Proces takiego schodzenia w głąb drzewa jest kontynuowany aż do umieszczenia przykładu w liściu lub utworzenia dla niego nowego liścia. W pierwszym przypadku jednak liść staje się węzłem o dwóch liściach potomnych, z których jeden jest kopią oryginalnego liścia (takiego, jaki był, zanim przykład został do niego dodany), a drugi zawiera ten przykład.

Najwygodniej jest sformułować naszkicowany tu sposób postępowania rekurencyjnie, tak jak naszkicowano to poniżej. Procedura cobweb otrzymuje dwa argumenty: przykład $ x$ i węzeł $ n$. Przedstawiony algorytm ma umieścić przykład $ x$ w węźle $ n$ i następnie w razie potrzeby wybrać odpowiedni operator na poziomie jego węzłów potomnych. Przed pierwszym wywołaniem procedury należy utworzyć drzewo złożone z jednego liścia, zawierającego pierwszy przykład. Następnie dla każdego kolejnego przykładu procedura powinna być wywoływana z pierwszym argumentem będącym węzłem znajdującym się w korzeniu drzewa.


\begin{algorithmic}[1] \FUNCTION $\textit{cobweb}(x,n)$\INPUTARGS\mbox{} \begin{... ...ęzła $n$\ i wywołaj $\textit{cobweb}(x,n)$; \ENDCHOOSE \ENDIF \end{algorithmic}

Jeśli węzeł $ n$, do którego ma być dodany przykład $ x$, jest liściem pozbawionym węzłów potomnych, to żaden z czterech standardowych operatorów systemu COBWEB nie może być zastosowany. W tej sytuacji liść zastępowany jest węzłem, którego dwoma potomkami stają się oryginalny liść $ n$ i nowy jednoelementowy liść utworzony dla przykładu $ x$. Gdy węzeł $ n$ ma węzły potomne, nowy przykład $ x$ jest do niego dodawany w zwykłym sensie, czyli zwiększane są odpowiednie liczniki przechowywane w tym węźle. Następnie musi zostać dokonany wybór właściwego operatora. W tym celu rozważany jest próbnie każdy z możliwych operatorów, a o ostatecznym wyborze decyduje wartość funkcji oceny.

Klasyfikacja przykładów

Wygenerowane drzewo reprezentujące grupowanie może być wykorzystywane do klasyfikowania przykładów w bardzo prosty sposób. Ponieważ klasyfikowanie polega na znalezieniu kategorii, do której przykład powinien być zaliczony, jednoznacznego kryterium podejmowania decyzji może nam dostarczyć ta sama funkcja oceny, która jest stosowana podczas konstruowania drzewa grupowania. Wyznaczenie kategorii dla przykładu jest niczym innym jak wyznaczeniem dla niego najlepszego pojemnika. Jeśli interesują nas kategorie pewnego poziomu $ l>0$, to, rozpoczynając od węzła znajdującego się w korzeniu drzewa (na poziomie 0), należy zstępować na kolejne niższe poziomy wzdłuż ścieżki wyznaczonej przez najlepsze pojemniki dla klasyfikowanego przykładu, aż do osiągnięcia pożądanego poziomu.

Zauważmy, że w opisany sposób mogą być również klasyfikowane przykłady, dla których nie wszystkie wartości atrybutów są znane. Wystarczy, dołączając na próbę taki przykład do różnych węzłów w poszukiwaniu najlepszego pojemnika, zwiększać liczniki, używane do szacowania prawdopodobieństw dla brakujących wartości atrybutów, o wielkości ułamkowe, określone na podstawie prawdopodobieństw dla tych wartości w kategorii nadrzędnej. Po znalezieniu w ten sposób właściwej kategorii dla przykładu z brakującymi wartościami atrybutów można wykorzystać związane z tą kategorią oszacowania prawdopodobieństw do wnioskowania o tych wartościach. Na podstawie znanych wartości atrybutów dowolnego przykładu można więc wyznaczyć rozkłady prawdopodobieństwa nieznanych wartości atrybutów dla tego przykładu.

Mieszane przestrzenie atrybutów

Zgodnie z sugestią podaną wcześniej, algorytm $ k$ środków lub jego zmodyfikowane wersje można zaadaptować również do atrybutów dyskretnych, co oczywiście oznacza, że istnieje także możliwość stosowania go w sytuacji, gdy część atrybutów jest ciągła, a część dyskretna. Jednak również algorytm COBWEB można w prosty sposób dostosować do używania atrybutów ciągłych, umożliwiając jego stosowanie do ciągłych i mieszanych przestrzeni atrybutów. Pomysł polega na tym, aby dla atrybutów ciągłych w węzłach szacować nie prawdopodobieństwa wartości atrybutów, lecz parametry funkcji gęstości, a przy obliczaniu funkcji oceny grupowania zamiast sum prawdopodobieństw postaci:

$\displaystyle \sum_{v\in A_i}\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,h(x)=d\big)$ (11)

i

$\displaystyle \sum_{v\in A_i}\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\big)$ (12)

używać odpowiednio całek z funkcji gęstości:

$\displaystyle \int_{v\in A_i}g^{i,d}_{\Omega}(v)dv$ (13)

i

$\displaystyle \int_{v\in A_i}g^i_{\Omega}(v)dv$, (14)

gdzie $ g^{i,d}_{\Omega}$ oznacza funkcję gęstości dla wartości atrybutu $ a_i$ w kategorii $ d$ i $ g^i_{\Omega}$ oznacza funkcję gęstości dla wartości atrybutu $ a_i$ bez względu na kategorię. Przyjmując, że wartości atrybutów ciągłych mają rozkład prawdopodobieństwa pewnego ustalonego typu (zazwyczaj normalnego) wystarczy do znanego wzoru na funkcję gęstości wstawić oszacowane parametry (wartość średnią i odchylenie standardowe), przechowywane w węzłach i modyfikowane przy dodawaniu przykładów.

Zagadnienia praktyczne

Wybór algorytmu

Preferencje wobec jednego z dwóch omówionych podejść do grupowania mogą zależeć od dziedziny zastosowania i oczekiwanych wyników. W wielu przypadkach proste podejście oparte na odległości, reprezentowane przez algorytm $ k$ środków lub jego zmodyfikowane wersje, może dać zadowalające efekty przy niższym nakładzie obliczeń. Warto z niego korzystać głównie wtedy, gdy wszystkie atrybuty są ciągłe, wystarcza nam grupowanie płaskie (niehierarchiczne) oraz można z góry ustalić pożądaną liczbę grup. Jeśli któryś z tych warunków nie jest spełniony, może to być przesłanka do sięgnięcia po algorytm COBWEB. Zwłaszcza występowanie atrybutów dyskretnych może być ważnym argumentem, gdyż stosowany w tym algorytmie opis kategorii w postaci oszacowań rozkładów prawdopodobieństw wartości atrybutu daje znacznie większe możliwości wnioskowania na podstawie zaklasyfikowania przykładu do kategorii.

Grupowanie bayesowskie

Dla atrybutów ciągłych metryka euklidesowa lub jej proste modyfikacje to zapewne najbardziej naturalne miary odległości między przykładami i kategoriami grupowania. W przypadku atrybutów dyskretnych można, jak sugerowane to było wyżej, dokonać jej odpowiedniej adaptacji: zamiast różnicy wartości atrrybutów ciągłych należałoby uwzględniać liczbę wartości pośrednich (zwiększoną o jeden) dla atrybutów porządkowych oraz 0 (jeśli jednakowe) i $ 1$ (jeśli różne) dla atrybutów nominalnych. Podobnie w wektorze środkowym kategorii zamiast średnich wartości dla atrybutów dyskretnych powinny się znaleźć raczej wartości najczęściej występujące. Jeśli jednak wszystkie lub większość atrybutów to atrybuty dyskretne, tak proste podejście może dostarczać zbyt mało informacji na temat grup i zbyt słabo zapewniać oczekiwane podobieństwo wewnątrz grup i zróżnicowanie między nimi.

Algorytm COBWEB może sugerować inną, probabilistyczną miarę odległości przykładu od kategorii, którą byłoby prawdopodobieństwo wartości atrybutów opisujących przykład przy założeniu przynależności do tej kategorii. Dla pewnego przykładu $ x_*$ możemy to prawdopodobieństwo zapisać jako:

$\displaystyle \mathrm{Pr}_{x\in\Omega}\big(a_1(x)=a_1(x_*),\dots,a_n(x)=a_n(x_*)\,\vert\, h(x)=d\big)$, (15)

co pozwala przy założeniu o niezależności wartości atrybutów względem kategorii na zapisanie miary odległości następująco:

$\displaystyle \delta(x_*,d) = \prod_{i=1}^n\mathrm{Pr}((a_i(x)=a_i(x_*)\,\vert\,h(x)=d)$, (16)

a więc identycznie, jak część wyrażenia, na podstawie którego wybiera kategorie naiwny klasyfikar bayesowski. Ściśle rzecz biorąc, tak zdefiniowana wielkość jest raczej miarą ,,bliskości'' niż odległości (tym większa, im przykład bardziej podobny do grupy). Właściwą odległość można by zdefiniować np. jako odwrotność, ale nie ma takiej potrzeby, gdyż wystarczy w algorytmie $ k$ środków zamienić minimalizację na maksymalizację.

Grupowanie na podstawie tak określonej odległości realizowane za pomocą algorytmu $ k$ środków lub pokrewnego można nazwać grupowaniem bayesowskim. Oczywiście reprezentacja kategorii musi zostać odpowiednio dostosowana: każda grupa powinna być opisana nie przez wektor wartości średnich czy środkowych, ale przez występujące w podanym wzorze na odległość prawdopodobieństwa, a ściślej przez liczniki wartości atrybutów pozwalające te prawdopodobieństwa szacować -- identycznie jak w algorytmie COBWEB. Również podobnie jak w tym algorytmie, można takie podejście rozszerzyć także na atrybuty ciągłe, używając funkcji gęstości zamiast prawdopodobieństw i obliczając dla atrybutów ciągłych wartość średnią i odchylenie standardowe.

Ocena jakości grupowania

Algorytm COBWEB ma swoją funkcję oceny grupowania, którą wykorzystuje przy budowaniu drzewa kategorii i którą można także wykorzystać po zakończeniu jego działania do oceny uzyskanych wyników -- np. porównując grupowania uzyskane w kilku niezależnych uruchomieniach, różniących się kolejnością przetwarzania przykładów. Jednak warto mieć także pewną niezależną od algorytmu, ,,obiektywną'' funkcję oceny, za pomocą której można by porównywać grupowania uzyskiwane za pomocą różnych algorytmów, także takich jak algorytm $ k$ środków i jego warianty, nie wyposażone w żadną wewnętrzną funkcję oceny. Jedno z podejść do takiej zobiektywizowanej oceny grupowania mówi, aby oprzeć ją na prawdopodobieństwie danych trenujących przy założeniu, że grupowanie opisuje rozkład prawdopodobieństwa, z jakim te dane są grupowane. W tym podejściu przyjmuje się, że każda grupa reprezentuje pewien rozkład prawdopodobieństwa, a dane są generowane przez ,,mieszanie'' tych rozkładów. Wówczas prawdopodobiństwo dowolnego przykładu $ x\in T$ przy danym grupowaniu $ h$ byłoby wyznaczone jako:

$\displaystyle \mathrm{Pr}(x\,\vert\,h) = \sum_{d\in C_h} \mathrm{Pr}(d)\mathrm{Pr}(x\,\vert\,d)$. (17)

W tym równaniu $ \mathrm{Pr}(d)$ jest w istocie użytym dla wygody skrótem dla prawdopodobieństwa, które wcześniej oznaczaliśmy przez $ \mathrm{Pr}_{x\in\Omega}\big(h(x)=d\big)$, a $ \mathrm{Pr}(x\,\vert\,d)$ należy interpretować jako prawdopodobieństwo uzyskania wartości atrybutów takich jak dla przykładu $ x$ przy wybieraniu przykładu z kategorii $ d$, co zmieniając $ x$ na $ x_*$ dla uniknięcia niejednoznaczności można zapisać w podany już wyżej sposób:

$\displaystyle \mathrm{Pr}_{x\in\Omega}\big(a_1(x)=a_1(x_*),\dots,a_n(x)=a_n(x_*)\,\vert\, h(x)=d\big)$ (18)

i obliczać na podstawie wzoru Bayesa, przyjmując zwykłe założenie o niezależności i ignorując niezależny od kategorii mianownik jako nieistotny czynnik skalujący. Jest to w istocie ta sama wielkość, która w poprzednim podrozdziale była proponowana jako probabilistyczna miara odległości przykładu od kategorii.

Wiedząc, jak obliczyć prawdopodobieństwo dla pojedynczego przykładu, prawdopodobieństwo dla całego zbioru trenującego $ T$ wyznaczymy jako iloczyn:

$\displaystyle \mathrm{Pr}(T\,\vert\,h) = \prod_{x\in T}\mathrm{Pr}(x\,\vert\,h)$. (19)

W praktyce ze względów obliczeniowych obliczalibyśmy raczej logarytm takiego prawdopodobieństwa, sumując logarytmy poszczególnych prawdopodobieństw zamiast je mnożyć. Uzyskana wartość pokazuje, jak bardzo dane trenujące ,,pasują'' do grupowania, co pozwala porównywać jakość różnych grupowań.

Wieloelementowe liście w algorytmie COBWEB

W praktyce wymóg tworzenia wyłącznie jednoelementowych liści w drzewie grupowania algorytmu COBWEB jest trudny do utrzymania. Jeśli kategorie są zawsze dzielone na podkategorie aż do osiągnięcia kategorii jednoelementowych, to liczba liści w drzewie grupowania zawsze będzie równa liczbie przetworzonych przykładów trenujących. Z każdym węzłem zaś, niezależnie od liczby zaliczonych do niego przykładów, wiąże się przechowywanie liczników niezbędnych do wyznaczenia rozkładów prawdopodobieństwa dla wszystkich wartości atrybutów lub odpowiednich parametrów funkcji gęstości. Jeśli rozmiar zbioru trenującego jest liczony w setkach tysięcy, a liczba atrybutów i ich wartości także nie jest mała, może to oznaczać nieakceptowalnie duże zapotrzebowanie na pamięć. Wówczas trzeba odstąpić od wymogu, aby liście reprezentowały zawsze kategorie jednoelementowe i dopuścić, że kategoria, do której zaliczono większą liczbę przykładów, nie ma podkategorii. Jednym z kryteriów podejmowania decyzji, czy dotychczasowy liść po dołączeniu kolejnego przykładu może dalej pozostać liściem, może być podobieństwo przykładów znajdujących się w odpowiedniej kategorii. Jeśli dla każdego lub prawie każdego atrybutu dyskretnego jedna wartość wyraźnie dominuje nad innymi, a wariancja wartości większości atrybutów ciągłych jest mała, można przyjąć, że kategoria jest wewnętrznie dostatecznie jednorodna, aby jej podział nie był konieczny. Mierzyć taką niejednorodność można za pomocą entropii. Inne rozwiązanie to nałożenie ograniczenia na minimalną wartość funkcji oceny grupowania, jakiej osiągnięcie jest konieczne, aby usprawiedliwić podział kategorii na podkategorie. Jeśli dla podwęzłów pewnego węzła wartość funkcji oceny byłaby niższa, należałoby uczynić ten węzeł wieloelementowym liściem.

Literatura

  1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdziały 6.3, 6.4).
  2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdziały ).

About this document ...

Metody odkrywania wiedzy: wykład 7
Grupowanie

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w7.tex

The translation was initiated by Pawel Cichosz on 2004-02-12

Pawel Cichosz 2004-02-12