Naiwny klasyfikator bayesowski

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Naiwny klasyfikator bayesowski – prosty klasyfikator probabilistyczny. Naiwne klasyfikatory bayesowskie są oparte na założeniu o wzajemnej niezależności predyktorów (zmiennych niezależnych). Często nie mają one żadnego związku z rzeczywistością i właśnie z tego powodu nazywa się je naiwnymi. Bardziej opisowe jest określenie – „model cech niezależnych”. Ponadto model prawdopodobieństwa można wyprowadzić korzystając z twierdzenia Bayesa.

W zależności od rodzaju dokładności modelu prawdopodobieństwa, naiwne klasyfikatory bayesowskie można skutecznie „uczyć” w trybie uczenia z nadzorem. W wielu praktycznych aplikacjach, estymacja parametru dla naiwnych modeli Bayesa używa metody maksymalnego prawdopodobieństwa a posteriori; inaczej mówiąc, można pracować z naiwnym modelem Bayesa bez wierzenia w twierdzenie Bayesa albo używania jakichś metod Bayesa.

Pomimo ich naiwnego projektowania i bardzo uproszczonych założeń, w wielu rzeczywistych sytuacjach naiwne klasyfikatory Bayesa często pracują dużo lepiej, niż można było tego oczekiwać.

Naiwny model probabilistyczny Bayesa[edytuj | edytuj kod]

Model prawdopodobieństwa dla klasyfikatora jest modelem warunkowym

p(C \vert F_1,\dots,F_n)\,

przez zmienną zależną klasy C z niewielu rezultatów albo „klas”, zależnych od kilku opisujących zmiennych F_1 do F_n. Problem pojawia się, gdy liczba cech n jest duża lub gdy cecha może przyjmować dużą liczbę wartości. Wtedy opieranie się na modelu tablic prawdopodobieństw jest niewykonalne. Dlatego też inaczej formułuje się taki model, by był bardziej przystępny.

Korzystając z twierdzenia Bayesa:

p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)} \,

W praktyce interesujący jest tylko licznik ułamka, bo mianownik nie zależy od C i wartości cechy F_i sa dane. Mianownik jest więc stały.

Licznik ułamka jest równoważny do łącznego modelu prawdopodobieństwa

p(C, F_1, \dots, F_n)\,

który można zapisać, wykorzystując prawdopodobieństwo warunkowe

p(C, F_1, \dots, F_n)\,
= p(C) \ p(F_1,\dots,F_n\vert C)
= p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1)
= p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2)
= p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3)

i tak dalej. Włącza się teraz „naiwną” warunkową zależność. Zakładając, że każda cecha F_i jest warunkowo niezależna od każdej innej cechy

F_j dla j\neq i

Oznacza to

p(F_i \vert C, F_j) = p(F_i \vert C)\,

więc model można wyrazić jako

p(C, F_1, \dots, F_n) = p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots\,
= p(C) \prod_{i=1}^n p(F_i \vert C)\,

Oznacza to, że pod powyższymi niezależnymi założeniami, warunkowe rozmieszczenie nad klasą zmiennych C można zapisać

p(C \vert F_1,\dots,F_n) = \frac{1}{Z}  p(C) \prod_{i=1}^n p(F_i \vert C)

gdzie Z jest współczynnikiem skalowania zależnym wyłącznie od F_1,\dots,F_n.

Modele tej formy są łatwiejsze do zrealizowania, gdy rozłoży się je na czynniki zwane klasą „prior” p(C) i niezależny rozkład prawdopodobieństwa p(F_i\vert C). Jeśli są klasy k i jeśli model dla p(F_i) może być wyrażony przez parametr r, wtedy odpowiadający naiwny model Bayesa ma (k − 1) + n r k parametrów. W praktyce często k=2 (klasyfikacja binarna) i r=1 (zmienna Bernouliego jako cecha), wtedy całkowita liczba parametrów naiwnego modelu Bayesa to 2n+1, gdzie n jest liczbą binarnych użytych cech.

Estymacja parametru[edytuj | edytuj kod]

W przypadku uczenia z nadzorem, chcemy ocenić parametry probabilistycznego modelu. Z powodu założenia niezależnych cech, wystarczy ocenić klasę poprzednią i zależną cechę modelu niezależnie, wykorzystując metodę maksimum prawdopodobieństwa a posteriori (MAP), wnioskowanie Bayesa lub inną parametryczną procedurę estymacji.

Konstrukcja klasyfikatora z modelu probabilistycznego[edytuj | edytuj kod]

Dotychczasowe omówienie problemu wyprowadziło model niezależnych cech, które są naiwnym probabilistycznym modelem Bayesa. Naiwny klasyfikator bayesowski łączy ten model z regułą decyzyjną. Jedna, ogólna reguła ma wydobyć hipotezę najbardziej prawdopodobną. Odpowiadający klasyfikator jest funkcją \mathrm{classify}, zdefiniowaną

\mathrm{classify}(f_1,\dots,f_n) = \mathop{\mathrm{argmax}}_c \ p(C=c) \prod_{i=1}^n p(F_i=f_i\vert C=c)

Omówienie[edytuj | edytuj kod]

Naiwny klasyfikator bayesowski ma wiele własności, które okazują się zaskakująco przydatne w praktyce, pomimo faktu, że założenia niezależności często są naruszone. Jak wszystkie probabilistyczne klasyfikatory, wykorzystujące regułą decyzyjną MAP, klasyfikacja jest tak długo poprawna, jak długo poprawna klasa jest bardziej prawdopodobna od innych (prawdopodobieństwa poszczególnych klas nie muszą być oceniane zbyt dokładnie). Inaczej mówiąc, klasyfikator jest wystarczająco mocny, by zignorować poważne niedociągnięcia naiwnego probabilistycznego modelu.

Przykład – klasyfikacja dokumentu[edytuj | edytuj kod]

Przedstawiony zostawnie tu problem klasyfikacji dokumentów metodą naiwnego klasyfikatora Bayesa. Rozważać będziemy klasyfikację poczty email pod względem zawartości i oceniać czy poszczególne wiadomości są chcianą pocztą czy też spamem. Wyobraźmy sobie, że dokumenty są przypisane do pewnej liczby klas dokumentów, które mogą być modelowane jako komplety słów, gdzie (niezależne) prawdopodobieństwo, że i-te słowo danego dokumentu zdarza się w dokumencie klasy C zapisujemy, jako

p(w_i \vert C)\,

Zakładamy, że prawdopodobieństwo wystąpienia słowa w dokumencie jest niezależne od długości dokumentu lub też, że wszystkie dokumenty mają tę samą długość.

Wtedy prawdopodobieństwo danego dokumentu D, klasy C

p(D\vert C)=\prod_i p(w_i \vert C)\,

Pytanie, na które chcemy odpowiedzieć to: „jakie jest prawdopodobieństwo, że dany dokument D należy do danej klasy C?”

Korzystając z definicji

p(D\vert C)={p(D\cap C)\over p(C)}

i

p(C\vert D)={p(D\cap C)\over p(D)}
p(C\vert D)={p(C)\over p(D)}\,p(D\vert C)

przyjmijmy założenie, że są tylko dwie klasy: S i ¬S (w naszym przykładzie: spam i nie-spam).

p(D\vert S)=\prod_i p(w_i \vert S)\,

i

p(D\vert\neg S)=\prod_i p(w_i\vert\neg S)\,

Korzystając z bayesianu, powyższy rezultat zapisać możemy jako

p(S\vert D)={p(S)\over p(D)}\,\prod_i p(w_i \vert S)
p(\neg S\vert D)={p(\neg S)\over p(D)}\,\prod_i p(w_i \vert\neg S)

Dzieląc jeden przez drugi otrzymujemy:

{p(S\vert D)\over p(\neg S\vert D)}={p(S)\,\prod_i p(w_i \vert S)\over p(\neg S)\,\prod_i p(w_i \vert\neg S)}

Możemy to przekształcić do postaci:

{p(S)\over p(\neg S)}\,\prod_i {p(w_i \vert S)\over p(w_i \vert\neg S)}

W ten sposób, prawdopodobieństwo stosunku p(S | D) / p(¬S | D) może być wyrażone jako stosunek prawdopodobieństw. Bieżące prawdopodobieństwo p(S | D) można obliczyć jako log (p(S | D) / p(¬S | D)), korzystając z własności, że p(S | D) + p(¬S | D) = 1.

Otrzymujemy więc:

\ln{p(S\vert D)\over p(\neg S\vert D)}=\ln{p(S)\over p(\neg S)}+\sum_i \ln{p(w_i\vert S)\over p(w_i\vert\neg S)}

W końcu możemy sklasyfikować dany dokument. Jest to spam, jeśli

\ln{p(S\vert D)\over p(\neg S\vert D)} > 0

W innym wypadku dokument spamem nie jest.

Linki zewnętrzne[edytuj | edytuj kod]

  1. Naiwny klasyfikator Bayesa. Internetowy Podręcznik Statystyki. [dostęp 2011-07-13].