Zastosowanie naiwnego klasyfikatora Bayes'a do klasyfikowania dokumentów tekstowych

Naiwny klasyfikator Bayes'a

Naiwny klasyfikator Bayes'a jest jedną z metod uczenia maszynowego, stosowaną do rozwiązywania problemu sortowania klas decyzyjnych. Zadaniem klasyfikatora Bayes'a jest przyporządkowanie nowego przypadku do jednej z klas, przy czym ich zbiór musi być skończony i zdefiniowany a priori.

Każdy przykład uczący opisany jest przy pomocy zbioru atrybutów warunkowych {A_i} i jednego atrybutu decyzyjnego D. W odróżnieniu od wielu innych technik uczenia maszynowego, tutaj nie zakłada się, że każdy przykład opisany jest przy pomocy takiego samego zbioru atrybutów warunkowych (z drugiej jednak strony, aby zachować spójność z innymi podejściami, można przyjąć interpretację, że zbiór atrybutów warunkowych jest stały dla wszystkich przykładów, natomiast poszczególne przykłady mogą zawierać wartości brakujące, które nie są brane pod uwagę zarówno podczas uczenia, jak i podczas klasyfikacji).

W myśl teorii Bayes'a, najbardziej prawdopodobną klasą, do której należy przypisać nowy obiekt, opisany wartościami n-atrybutów warunkowych A_j1 = v_j1, A_j2 = v_j2 … A_jn = v_jn (lub w skrócie <v_j1, v_j2 … v_jn>), jest klasa d_i, która maksymalizuje prawdopodobieństwo warunkowe P(d_i | v_j1, v_j2 … v_jn). Klasa ta oznaczona jest jako d_MAP (maximum a posterori).

  (1)

We wzorze (1) przez V_D oznaczono dziedzinę atrybutu decyzyjnego (czyli zbiór klas decyzyjnych). W ostatniej linii (1) usunięto mianownik – prawdopodobieństwo P(v_j1, v_j2 … v_jn) ma wartość stałą, niezależną od klasy decyzyjnej d_i, więc nie ma ono wpływu na wybór klasy d_MAP.

Prawdopodobieństwo P(d_i) można oszacować w prosty sposób (i niezależnie od wielkości zbioru uczącego) jako stosunek liczby przykładów uczących należących do klasy d_i do liczby wszystkich przykładów uczących. Oszacowanie prawdopodobieństwa P(v_j1, v_j2 … v_jn | d_i) w analogiczny sposób (tzn. jako stosunek liczby przykładów uczących opisanych wartościami atrybutów warunkowych <v_j1, v_j2 … v_jn > i należących do klasy d_i do liczby wszystkich przykładów uczących z klasy d_i) jest dopuszczalne jedynie dla bardzo dużych zbiorów przykładów uczących.

Aby umożliwić łatwe oszacowanie prawdopodobieństwa P(v_j1, v_j2 … v_jn | d_i), w naiwnym klasyfikatorze Bayes'a wprowadzono założenie o warunkowej niezależności wartości atrybutów przy ustalonej klasie decyzyjnej. Po przyjęciu takiego założenia, prawdopodobieństwo to można zapisać jako:

Natomiast prawdopodobieństwo P(v_jk | d_i) można oszacować jako stosunek liczby przykładów uczących z klasy d_i, dla których wartość atrybutu A_jk równa jest v_jk, do liczby wszystkich przykładów uczących z klasy d_i.

Po uwzględnieniu wspomnianego wyżej założenia, do klasyfikacji nowego przykładu wybrana zostaje klasa d_NB (Naïve Bayes).

Warto tutaj zaznaczyć, że etap estymacji prawdopodobieństw odpowiada etapowi uczenia się (czyli etapowi budowy klasyfikatora, np. generowaniu drzew decyzyjnych lub indukcji reguł) w innych metodach uczenia maszynowego.

Oszacowywanie prawdopodobieństwa

Przy oszacowywaniu prawdopodobieństwa, np. P(v_jk | d_i), może się okazać, że otrzymana estymata jest zbyt mała w porównaniu do rzeczywistego prawdopodobieństwa. Ma to miejsce szczególne wtedy, gdy licznik ułamka w estymacie jest bardzo mały (spośród n wszystkich przypadków, tylko n₊ ma rozważaną wartość atrybutu v_jk w klasie d_i). Aby rozwiązać ten problem wprowadzono m-estymatę prawdopodobieństwa:

w której p jest wstępną estymatą szacowanego prawdopodobieństwa, a m jest stałą zwaną rozmiarem równoważnej próbki (equivalent sample size). Taka nazwa stałej wynika z interpretacji, w której m-estymata potraktowana jest jako uzupełnienie zbioru uczącego m dodatkowymi przykładami.

W przypadku oszacowywania prawdopodobieństwa wystąpienia wartości atrybutu, jeżeli brak jest innych informacji, zazwyczaj przyjmuje się p równe 1/k, gdzie k jest liczbą możliwych wartości rozważanego atrybutu.

Szczególnym przypadkiem m-estymaty jest wykorzystywana w wielu zastosowaniach estymata Laplace'a (zob. np. tu albo tu (str. 18/20)).

Klasyfikacja dokumentów tekstowych

Naiwny klasyfikator Bayes'a jest jedną z najbardziej efektywnych metod uczenia maszynowego służącą do klasyfikacji dokumentów tekstowych. W praktyce stosowany jest najczęściej do filtrowania dokumentów (np. w przeszukiwarkach internetowych).

Każdy dokument tekstowy opisany jest przy pomocy zbioru atrybutów warunkowych {A_i}. Atrybut A_i oznacza i-tą pozycję słowa w dokumencie (np. przy założeniu, że ten akapit stanowi oddzielny dokument, atrybut A₁ oznacza pierwszy wyraz w akapicie, a jego wartość wynosi 'każdy'). Należy zauważyć, że liczba atrybutów warunkowych (oznaczająca długością tekstu) może być zmienna.

Każdy przykład (dokument) uczący opisany jest również przy pomocy wartości atrybutu decyzyjnego. Zbiór klas decyzyjnych jest zależny od zastosowania – może on zawierać określenia tematyki, której poświęcone są teksty (np. komputery, samochody …) lub oceny tekstu (np. interesujący, nudny …).

Nowy dokument, zawierający n słów, z których pierwsze – A₁ to w_A1, drugie A₂ = w_A2, … ostatnie A_n = w_An, przyporządkowywany jest do klasy d_NB, wyznaczonej jako:

Warto zauważyć, że w przypadku dokumentów tekstowych nie jest spełnione założenie o warunkowej niezależności wartości atrybutów warunkowych (słowa tworzą zwroty, w których na podstawie jednego słowa można przewidzieć następne – np. zwrot 'przede wszystkim'), jednak w praktyce nie obniża to zbytnio skuteczności klasyfikatora.

Ponieważ zbiór atrybutów warunkowych oraz zbiór możliwych wartości dla każdego z atrybutów (czyli zbiór możliwych słów) są zazwyczaj bardzo duże, oszacowanie prawdopodobieństw P(w_Aj | d_i) może być bardzo trudne, dlatego przyjęto upraszczające założenie, że prawdopodobieństwo wystąpienia słowa jest niezależne od jego pozycji w tekście, tzn. jeżeli w_Ai = w^k i w_Aj = w^k (gdzie w^k oznacza k-te słowo w słowniku DICT, utworzonym ze słów występujących w tekstach uczących), to P(w_Ai | d_i) = P(w_Aj | d_i) = P(w^k | d_i). Dzięki takiemu założeniu znacząco maleje liczba estymat prawdopodobieństwa, jakie trzeba wyznaczyć podczas uczenia.

Przy wyznaczaniu estymat P(w^k | d_i) stosuje się następującą m-estymatę:

w której n oznacza całkowitą liczbę słów w tekstach uczących należących do klasy d_i, n_k – liczbę wystąpień słowa w^k w tekstach z klasy d_i, a |DICT| – rozmiar słownika, czyli liczbę rozróżnialnych słów występujących we wszystkich tekstach uczących.

Algorytm uczący i testujący przedstawione są poniżej. Warto zwrócić uwagę, że podczas klasyfikacji nie są pod uwagę słowa z klasyfikowanego dokumentu, które nie występują w słowniku DICT – klasyfikacja dokonywana jest jedynie na podstawie zbioru positions.

Algorytm uczący i testujący

LearnNaiveBayes(examples, V_D)

examples – set of learning documents

V_D – set of decision classes

begin

DICT := set of all distinct words occuring in any text document from examples

for each d_i in V_D do begin

docs_i := subset of documents from examples that belong to class d_i

P(d_i) := |docs_i| / |examples|

text_i := single document created by concatenating all members of docs_i

n := total number of words in text_i

for each word w^k in DICT do begin

n_k := number of times word w^k occurs in text_i

P(w^k | d_i) := (n_k + 1) / (n + |DICT|)

end

end

end

ClassifyNaiveBayes(doc)

doc – document to be classified

begin

positions := set of indexes (for each word in doc find its index in DICT)

${\text{d}}_{\text{NB}}:=\mathrm{\text{arg}}\text{ma}{\text{x}}_{{\text{d}}_{\text{i}}\in {\text{V}}_{\text{D}}}\text{P}\left({\text{d}}_{\text{i}}\right)\prod _{\text{j}\in \text{positions}}\text{P}\left({\text{w}}^{\text{j}}\right|{\text{d}}_{\text{i}})$

return d_NB

end