1 WEDT Klasyfikacja i grupowanie dokumentówWykład 6 Piotr Gawrysiak 2006

2 Grupowanie (clustering)

3 Klasyfikacja (categorization)Klasa A Klasa B Klasa C

4 PR – precision, R – recall, A – accuracy, FO – falloutOcena efektywności algorytmów kategoryzacji kategoryzacja jest problemem zbliżonym do wyszukiwania informacji (IR) DB dr ds dr – dokumenty relewantne ds – dokumenty uznane przez system za relewantne DB – baza dokumentów PR – precision, R – recall, A – accuracy, FO – fallout

5 Kategoryzacja binarnaWartość wskaźnika dokładności określa prawdopodobieństwo dokonania poprawnej klasyfikacji, dla losowo wybranego dokumentu ze zbioru D. Wartość wskaźnika precyzji określa prawdopodobieństwo, iż losowy dokument wybrany z dokumentów uznanych za relewantne, jest rzeczywiście dokumentem relewantnym. Zupełność odpowiada prawdopodobieństwu tego, iż dokument faktycznie relewantny, zostanie za taki uznany przez system. Zaszumienie określa z kolei prawdopodobieństwo niepoprawnego uznania za relewantny dokumentu, który faktycznie relewantny nie jest. Tablica kontyngencji R0 – nierelewantne R1 – relewantne F – empiryczna G - estymowana

6 Rozszerzenie dla wielu klasM={M1, M2,...,Ml} Mk Makro-uśrednianie Mikro-uśrednianie PR={PR1, PR2, ..., PRl}

7 Przykład oceny Wyniki działania czterech systemów kategoryzacji:Ocena systemów według przedstawionych wskaźników:

8 Reprezentacje dokumentóww istocie są niemal tożsame z modelami języka Zliczanie słów reprezentacje unigramowe (bag-of-words) binarne częstościowe reprezentacja n-gramowe reprezentacje mieszane (Katz backoff style) reprezentacje pozycyjne Zliczanie sekwencji słów Rozkłady prawdopodobieństwa wyst. słów

9 Reprezentacje unigramoweNiech dany będzie dokument D=(w1, w2, ..., z1, ..., wn, zm). Unigramową reprezentacją binarną dokumentu D nazywamy wektor R taki, że: Niech dany będzie dokument D=(w1, w2, ..., z1, ..., wn, zm). Unigramową reprezentacją częstościową dokumentu D nazywamy wektor R taki, że:

10 Reprezentacje bazujące na modelu Markowan-gramowe mieszane „I would like to make phone...” Niech dany będzie dokument D=(w1, w2, ..., z1, ..., wo, zm). Reprezentacją n-gramową dokumentu D nazywamy macierz M taką, że: 1) kolejne wiersze x macierzy odpowiadają kolejnym wariacjom rx obejmującym n-1 słów ze słownika V 2) kolejne kolumny y macierzy odpowiadają kolejnym słowom vy ze słownika V 3) elementy macierzy przyjmują wartości:

11 Budowanie reprezentacji n-gramowejPrzykład – bigram dla tekstu: Twas brillig, and the slithy toves Did gyre and gimble in the wabe

12 Reprezentacja pozycyjna

13 Budowanie reprezentacji pozycyjnejNiech dany będzie dokument D=(w1, w2, ..., z1, ..., wn, zm). Reprezentacją pozycyjną dokumentu D nazywamy dwójkę (F, S) gdzie F jest zbiorem funkcji gęstości rozkładu słów fVi o następujących własnościach: 1) dziedziną funkcji fVi jest zbiór {1...n} 2) wartości funkcji fVi określone są następująco: 2r Wystąpienia słów f(k)=2 (przed norm.) k

14 Przykłady funkcji gęstości

15 Przetwarzanie reprezentacji dokumentówPowiększanie rozmiaru reprezentacji Różne metody wygładzania Ograniczanie rozmiaru reprezentacji Funkcje istotności atrybutów Wybór atrybutów Przekształcanie przestrzeni atrybutów

16 Po co ograniczać rozmiar reprezentacji?Prawo Zipfa „Hapax legomena”

17 Ograniczanie wielkości reprezentacji„Uniwersalne” funkcje istotności atrybutów Funkcje istotności atrybutów – rodzina TF/IDF term frequency tfi,j – określa częstość wystąpień atrybutu wi w dokumencie dj document frequency dfi – określa liczbę dokumentów w których występuje atrybut wi N – określa liczbę wszystkich dokumentów w systemie Atrybut w jednym dokumencie Atrybut we wszystkich dokumentach Funkcje istotności atrybutów - analiza funkcji gęstości Np. wartość takiej funkcji równa 0 oznacza całkowicie równomierny rozkład wystąpień słowa, zaś dla maksymalnej koncentracji (tj. dla pojedynczego wystąpienia słowa w dokumencie) wartość równa jest 1.

18 Korelacja atrybut-klasaTesty statystyczne mogą być zastosowane A A A C C A B C B C B Klasa 1 i A – istotny Klasa 2 i B – istotny C – nieistotny dla separacji klas

19 Funkcje istotności atrybutów – Information GainInformation Gain określa, które atrybuty są tymi, które w najlepszy sposób różnicują klasy ze zbioru trenującego

20 Przekształcanie przestrzeni atrybutówGrupowanie atrybutów Przekształcanie przestrzeni atrybutów Grupowanie wg zależności atrybut-klasa Grupowanie semantyczne Bezpośrednia analiza macierzy reprezentacji (SVD) Grupowanie wg podobieństwa funkcji gęstości

21 Kategoryzacja dokumentów o bogatej strukturzeAtrybuty nie muszą być wyłącznie częstościami słów/sekwencji słów XEROX Web Categorisation topologia metadane podobieństwo tekstów (klasyczny model dokumentów) częstość odwiedzin Przykład: Tekst Elementy medialne (obraz, dźwięk itp.) Osadzone aplikacje Kroje pisma Hiperpołączenia z innymi dokumentami Układ stron i paginacja Node Type Size Number Number Depth Similari Freq. Entry Precision Inlinks Outlinks of ty to Point Children Children Index Source Index Reference Destination Head Org. Home Page Personal Home >1k&<3k Content

22 Kategoryzacja oparta o formatowanie dokumentów

23 Przykład Słownik bunga-unga bunga unga 1 Unga Bunga Unigram binarnyBunga bunga bunga Unga unga unga Bunga unga bunga 1 2 Unga Bunga Unigram częstościowy

24 Przestrzeń Unga Bunga 1 2 Bunga unga bunga

25 Tree clustering Łączymy obiekty w coraz to większe grupyKryterium łączenia – miara podobieństwa lub odległość Wynik - drzewo Odległość Obiekty wyjściowe

26 Grupowanie (hierarchiczne)Unga Bunga 1 2 Potrzebne miary odległości

27 Miary odległości Euclidean distance distance(x,y) = {i (xi - yi)2 }½Squared Euclidean distance distance(x,y) = i (xi - yi)2 City-block distance distance(x,y) =  i |xi - yi| Chebychev distance distance(x,y) = Maximum|xi - yi| Power distance distance(x,y) = (i |xi - yi|p)1/r Percent disagreement distance(x,y) = (Number of xi  yi)/ i

28 Pierwszy etap Unga 2 1 Bunga 1 2

29 Reguły łączenia Single linkage (nearest neighbour)Complete linkage (furthest neighbour) Unweighted pair-group average - UPGMA Weighted pair-group average - WPGMA Unweighted pair-group centroid - UPGMC Weighted pair-group centroid - WPGMC

30 Drugi etap Unga Bunga 1 2

31 Kategoryzacja Unga Bunga 1 2 Unga > 0 Unga  0 Bunga < 21 2 Bunga < 2 Bunga  2 Bunga  0 Bunga > 0 Unga  1 Unga > 1

32 Kategoryzacja nowego dokumentuUnga > 0 Unga  0 Bunga < 2 Bunga  2 Bunga  0 Bunga > 0 Unga  1 Unga > 1 Bunga unga bunga Bunga unga bunga

33 Zastosowania Klasyczne Analiza wiadomości email (spam, routing etc.)Event tracking Internet related Web Content Mining Focused crawling, assisted browsing …