Naiwny klasyfikator Bayesa - Naive Bayes classifier

W statystykach , naiwne klasyfikatory bayesowskie są rodziną prostych „ probabilistycznych klasyfikatorów ” w oparciu o zastosowanie Twierdzenie Bayesa z silnymi (naiwne) niepodległościowych założeń między funkcjami (patrz Bayesa klasyfikatora ). Są to jedne z najprostszych modeli sieci bayesowskich , ale w połączeniu z szacowaniem gęstości jądra mogą osiągnąć wyższe poziomy dokładności.

Naiwne klasyfikatory Bayesa są wysoce skalowalne, wymagają szeregu parametrów liniowych w stosunku do liczby zmiennych (cech/predyktorów) w problemie z uczeniem. Trening maksymalnego prawdopodobieństwa można przeprowadzić, oceniając wyrażenie w formie zamkniętej , które zajmuje czas liniowy , a nie przez drogie przybliżenie iteracyjne, które jest stosowane w przypadku wielu innych typów klasyfikatorów.

W statystyce i literaturze informatycznej naiwne modele Bayesa są znane pod różnymi nazwami, w tym prosty Bayes i niezależność Bayes . Wszystkie te nazwy odwołują się do użycia twierdzenia Bayesa w regule decyzyjnej klasyfikatora, ale naiwny Bayes nie jest (koniecznie) metodą bayesowską .

Wstęp

Naive Bayes to prosta technika konstruowania klasyfikatorów: modeli, które przypisują etykiety klas do instancji problemów, reprezentowanych jako wektory wartości cech , gdzie etykiety klas są rysowane z pewnego skończonego zbioru. Nie istnieje jeden algorytm do uczenia takich klasyfikatorów, ale rodzina algorytmów oparta na wspólnej zasadzie: wszystkie naiwne klasyfikatory Bayesa zakładają, że wartość danej cechy jest niezależna od wartości jakiejkolwiek innej cechy, biorąc pod uwagę zmienną klasy. Na przykład za jabłko można uznać owoc, jeśli jest czerwony, okrągły i ma około 10 cm średnicy. Naiwny klasyfikator Bayesa uważa, że ​​każda z tych cech przyczynia się niezależnie do prawdopodobieństwa, że ​​ten owoc jest jabłkiem, niezależnie od wszelkich możliwych korelacji między cechami koloru, okrągłości i średnicy.

W przypadku niektórych typów modeli prawdopodobieństwa naiwne klasyfikatory Bayesa można bardzo wydajnie trenować w nadzorowanym środowisku uczenia się . W wielu praktycznych zastosowaniach estymacja parametrów dla naiwnych modeli Bayesa wykorzystuje metodę największej wiarygodności ; innymi słowy, można pracować z naiwnym modelem Bayesa bez akceptowania prawdopodobieństwa bayesowskiego lub przy użyciu jakichkolwiek metod bayesowskich.

Pomimo naiwnego projektu i pozornie uproszczonych założeń, naiwne klasyfikatory Bayesa sprawdzają się całkiem dobrze w wielu złożonych sytuacjach rzeczywistych. W 2004 r. analiza problemu klasyfikacji bayesowskiej wykazała, że ​​istnieją solidne teoretyczne powody dla pozornie nieprawdopodobnej skuteczności naiwnych klasyfikatorów Bayesa. Mimo to kompleksowe porównanie z innymi algorytmami klasyfikacji w 2006 r. wykazało, że klasyfikację Bayesa przewyższają inne podejścia, takie jak drzewa wzmocnione lub lasy losowe .

Zaletą naiwnego Bayesa jest to, że wymaga tylko niewielkiej liczby danych uczących, aby oszacować parametry niezbędne do klasyfikacji.

Model probabilistyczny

Abstrakcyjnie, naiwny model Bayesa jest warunkowym modelem prawdopodobieństwa : biorąc pod uwagę klasyfikowaną instancję problemu, reprezentowaną przez wektor reprezentujący pewne n cech (zmienne niezależne), przypisuje tej instancji prawdopodobieństwa

dla każdego z K możliwych wyników lub klas .

Problem z powyższym sformułowaniem polega na tym, że jeśli liczba cech n jest duża lub jeśli cecha może przyjmować dużą liczbę wartości, to oparcie takiego modelu na tablicach prawdopodobieństwa jest niewykonalne. W związku z tym model musi zostać przeformułowany, aby był bardziej wykonalny. Korzystając z twierdzenia Bayesa , prawdopodobieństwo warunkowe można rozłożyć jako

W prostym języku angielskim, używając terminologii prawdopodobieństwa bayesowskiego , powyższe równanie można zapisać jako

W praktyce interesuje się tylko licznikiem tego ułamka, ponieważ mianownik nie jest zależny i podane są wartości cech , dzięki czemu mianownik jest praktycznie stały. Licznik jest równoważny wspólnemu modelowi prawdopodobieństwa

które można przepisać w następujący sposób, stosując zasadę łańcucha dla powtarzających się zastosowań definicji prawdopodobieństwa warunkowego :

Teraz w grę wchodzą „naiwne” założenia warunkowej niezależności : załóżmy, że wszystkie cechy w są wzajemnie niezależne , uwarunkowane kategorią . Zgodnie z tym założeniem

.

Zatem wspólny model można wyrazić jako

gdzie oznacza proporcjonalność .

Oznacza to, że przy powyższych założeniach niezależności rozkład warunkowy nad zmienną klasową wynosi:

gdzie dowodem jest współczynnik skalujący zależny tylko od , czyli stała, jeśli znane są wartości zmiennych cech.

Konstruowanie klasyfikatora z modelu prawdopodobieństwa

Dotychczasowa dyskusja wyprowadziła niezależny model cech, czyli naiwny model prawdopodobieństwa Bayesa . Naiwny klasyfikator Bayesa łączy ten model z regułą decyzyjną . Jedną z powszechnych zasad jest wybranie najbardziej prawdopodobnej hipotezy; jest to znane jako reguła decyzyjna maksimum a posteriori lub MAP . Odpowiedni klasyfikator, klasyfikator Bayesa , to funkcja, która przypisuje etykietę klasy dla niektórych k w następujący sposób:

Estymacja parametrów i modele zdarzeń

Klasa wcześniejszej może być obliczany przy założeniu klas prawdopodobnych ( to znaczy , ) lub obliczenia szacunkowej wartości prawdopodobieństwa klasy ze zbioru treningowego ( to znaczy , <przed dla danej klasy> = <liczba próbek w klasie> / <całkowitej liczba próbek>). Aby oszacować parametry rozkładu cechy, należy założyć rozkład lub wygenerować modele nieparametryczne dla cech ze zbioru uczącego.

Założenia dotyczące rozkładów cech nazywane są „modelem zdarzeń” naiwnego klasyfikatora Bayesa. W przypadku funkcji dyskretnych, takich jak te spotykane w klasyfikacji dokumentów (w tym filtrowanie spamu), popularne są dystrybucje wielomianowe i Bernoulliego . Te założenia prowadzą do dwóch odrębnych modeli, które często są mylone.

Gaussowski naiwny Bayes

W przypadku danych ciągłych typowym założeniem jest to, że wartości ciągłe skojarzone z każdą klasą są rozłożone zgodnie z rozkładem normalnym (lub gaussowskim). Załóżmy na przykład, że dane uczące zawierają atrybut ciągły, . Dane są najpierw podzielone według klasy, a następnie średnią i wariancję z obliczany jest w każdej klasie. Niech będzie średnią wartości skojarzonych z klasą C k i niech będzie skorygowaną przez Bessela wariancją wartości skojarzonych z klasą C k . Załóżmy, że ktoś zebrał jakąś wartość obserwacyjną . Następnie prawdopodobieństwo gęstość od danej klasy , może być obliczana poprzez podłączenie do równania dla rozkładu normalnego parametryzowane i . To znaczy,

Inną powszechną techniką obsługi wartości ciągłych jest użycie binningu do dyskretyzacji wartości cech, aby uzyskać nowy zestaw cech rozłożonych przez Bernoulliego; część literatury faktycznie sugeruje, że jest to konieczne, aby zastosować naiwny Bayes, ale tak nie jest, a dyskretyzacja może odrzucić dyskryminującą informację .

Czasami rozkład gęstości krańcowych warunkowanych klasami jest daleki od normalnego. W takich przypadkach oszacowanie gęstości jądra można wykorzystać do bardziej realistycznego oszacowania gęstości brzegowych każdej klasy. Ta metoda, wprowadzona przez Johna i Langleya, może znacznie zwiększyć dokładność klasyfikatora.

Wielomianowy naiwny Bayes

W modelu zdarzenia wielomianowego próbki (wektory cech) reprezentują częstości, z jakimi pewne zdarzenia zostały wygenerowane przez wielomian, gdzie jest prawdopodobieństwo wystąpienia zdarzenia i (lub K takich wielomianów w przypadku wielomianowym). Wektor cech jest wtedy histogramem , zliczającym, ile razy zdarzenie i zostało zaobserwowane w danym przypadku. Jest to model zdarzeń zwykle używany do klasyfikacji dokumentów, w którym zdarzenia reprezentują wystąpienie słowa w pojedynczym dokumencie (patrz założenie worka słów ). Prawdopodobieństwo zaobserwowania histogramu x jest podane przez

Wielomianowy naiwny klasyfikator Bayesa staje się klasyfikatorem liniowym, gdy jest wyrażony w przestrzeni logarytmicznej:

gdzie i .

Jeżeli dana klasa i wartość cechy nigdy nie występują razem w danych uczących, to oszacowanie prawdopodobieństwa opartego na częstotliwości będzie wynosić zero, ponieważ oszacowanie prawdopodobieństwa jest wprost proporcjonalne do liczby wystąpień wartości cechy. Jest to problematyczne, ponieważ wymaże wszystkie informacje z innych prawdopodobieństw, gdy zostaną pomnożone. Dlatego często pożądane jest włączenie poprawki dla małej próbki, zwanej pseudocount , we wszystkich estymacjach prawdopodobieństwa, tak aby żadne prawdopodobieństwo nie było ustawione na dokładnie zero. Ten sposób uregulowania naiwnego Bayesa nazywa się wygładzaniem Laplace'a, gdy pseudoliczba wynosi jeden, i wygładzaniem Lidstone'a w ogólnym przypadku.

Rennie i in. omówić problemy z założeniem wielomianowym w kontekście klasyfikacji dokumentów i możliwe sposoby ich złagodzenia, w tym użycie wag tf–idf zamiast surowych częstości terminów i normalizacji długości dokumentu, w celu uzyskania naiwnego klasyfikatora Bayesa, który jest konkurencyjny z wektorem nośnym maszyny .

Bernoulli naiwny Bayes

W wielowymiarowym modelu zdarzeń Bernoulliego cechy są niezależnymi wartościami boolowskimi (zmiennymi binarnymi) opisującymi dane wejściowe. Podobnie jak model wielomianowy, model ten jest popularny w zadaniach klasyfikacji dokumentów, w których używane są binarne cechy występowania terminów, a nie częstotliwości terminów. Jeśli jest wartością logiczną wyrażającą wystąpienie lub nieobecność i -tego terminu w słowniku, to prawdopodobieństwo, że dokument ma daną klasę, wyraża się wzorem

gdzie jest prawdopodobieństwo wygenerowania terminu przez klasę . Ten model zdarzeń jest szczególnie popularny przy klasyfikowaniu krótkich tekstów. Ma tę zaletę, że jawnie modeluje brak terminów. Należy zauważyć, że naiwny klasyfikator Bayesa z modelem zdarzeń Bernoulliego nie jest tym samym, co wielomianowy klasyfikator NB z liczbą częstotliwości skróconą do jednego.

Półnadzorowana estymacja parametrów

Biorąc pod uwagę sposób uczenia naiwnego klasyfikatora Bayesa na podstawie danych oznaczonych, możliwe jest skonstruowanie częściowo nadzorowanego algorytmu uczenia, który może uczyć się na podstawie kombinacji danych oznaczonych i nieoznakowanych, uruchamiając algorytm uczenia nadzorowanego w pętli:

Mając zbiór oznaczonych próbek L i nieoznakowanych próbek U , zacznij od uczenia naiwnego klasyfikatora Bayesa na L .
Do czasu zbieżności wykonaj:
Przewiduj prawdopodobieństwa klas dla wszystkich przykładów x in .
Ponownie naucz model na podstawie prawdopodobieństw (nie etykiet) przewidzianych w poprzednim kroku.

Zbieżność wyznacza się na podstawie poprawy wiarogodności modelu , gdzie oznacza parametry naiwnego modelu Bayesa.

Ten algorytm uczący wystąpienie bardziej ogólnego algorytmu maksymalizacji oczekiwanie (EM): etap przewidywania w pętli jest E -step EM, a ponowne szkolenia naiwnych Bayesa jest M -step. Algorytm jest formalnie uzasadniony założeniem, że dane generowane są przez model mieszaniny , a składowe tego modelu mieszaniny są dokładnie klasami problemu klasyfikacyjnego.

Dyskusja

Pomimo tego, że dalekosiężne założenia niezależności są często niedokładne, naiwny klasyfikator Bayesa ma kilka właściwości, które czynią go zaskakująco użytecznym w praktyce. W szczególności rozdzielenie rozkładów cech warunkowych klasy oznacza, że ​​każdy rozkład może być niezależnie estymowany jako rozkład jednowymiarowy. Pomaga to złagodzić problemy wynikające z przekleństwa wymiarowości , takie jak zapotrzebowanie na zestawy danych, które skalują się wykładniczo wraz z liczbą funkcji. Chociaż naiwny Bayes często nie daje dobrego oszacowania dla poprawnych prawdopodobieństw klas, może to nie być wymagane dla wielu aplikacji. Na przykład naiwny klasyfikator Bayesa dokona prawidłowej klasyfikacji reguły decyzji MAP, o ile właściwa klasa jest bardziej prawdopodobna niż jakakolwiek inna klasa. Dzieje się tak niezależnie od tego, czy oszacowanie prawdopodobieństwa jest nieznacznie, czy nawet rażąco niedokładne. W ten sposób ogólny klasyfikator może być wystarczająco solidny, aby zignorować poważne braki w swoim podstawowym modelu prawdopodobieństwa naiwnego. Inne przyczyny obserwowanego sukcesu naiwnego klasyfikatora Bayesa omówiono w cytowanej poniżej literaturze.

Związek z regresją logistyczną

W przypadku wejść dyskretnych (wskaźnik lub cechy częstotliwości dla zdarzeń dyskretnych), naiwne klasyfikatory Bayesa tworzą parę generatywno-dyskryminacyjną z ( wielomianowymi ) klasyfikatorami regresji logistycznej : każdy naiwny klasyfikator Bayesa można uznać za sposób dopasowania modelu prawdopodobieństwa, który optymalizuje wspólne wiarogodność , podczas gdy regresja logistyczna dopasowuje ten sam model prawdopodobieństwa w celu optymalizacji warunkowego .

Związek między nimi może być postrzegane przez obserwację, że funkcja decyzji dla naiwnych Bayesa (w przypadku binarnym) może być zapisane jako „klasę przewidzieć , czy kursy z wykraczają poza ”. Wyrażenie tego w przestrzeni dziennika daje:

Lewa strona tego równania to log-odds lub logit , wielkość przewidywana przez model liniowy, który leży u podstaw regresji logistycznej. Ponieważ naiwny model Bayesa jest również modelem liniowym dla dwóch „dyskretnych” modeli zdarzeń, można go przeparametryzować jako funkcję liniową . Uzyskanie prawdopodobieństw jest wtedy kwestią zastosowania funkcji logistycznej do , lub w przypadku wieloklasowym do funkcji softmax .

Klasyfikatory dyskryminacyjne mają mniejszy błąd asymptotyczny niż klasyfikatory generatywne; jednak badania przeprowadzone przez Ng i Jordana wykazały, że w niektórych praktycznych przypadkach naiwny Bayes może przewyższać regresję logistyczną, ponieważ szybciej osiąga swój błąd asymptotyczny.

Przykłady

Klasyfikacja osób

Problem: na podstawie zmierzonych cech ustal, czy dana osoba jest mężczyzną czy kobietą. Funkcje obejmują wzrost, wagę i rozmiar stopy.

Szkolenie

Przykładowy zestaw szkoleń poniżej.

Osoba wzrost (w stopach) Waga w funtach) rozmiar stopy (cale)
mężczyzna 6 180 12
mężczyzna 5.92 (5'11") 190 11
mężczyzna 5.58 (5'7") 170 12
mężczyzna 5.92 (5'11") 165 10
Płeć żeńska 5 100 6
Płeć żeńska 5,5 (5'6") 150 8
Płeć żeńska 5,42 (5'5") 130 7
Płeć żeńska 5,75 (5'9") 150 9

Klasyfikator utworzony ze zbioru uczącego przy założeniu rozkładu Gaussa to (podane wariancje są nieobciążonymi wariancjami próbki ):

Osoba średnia (wzrost) wariancja (wysokość) średnia (waga) wariancja (waga) średnia (rozmiar stopy) wariancja (rozmiar stopy)
mężczyzna 5,855 3,5033 × 10 -2 176,25 1,2292 × 10 2 11.25 9,1667 x 10 -1
Płeć żeńska 5.4175 9,7225 x 10 -2 132,5 5,5833 × 10 2 7,5 1,6667

Poniższy przykład zakłada równoprawdopodobne klasy, tak że P(mężczyzna)= P(kobieta) = 0.5. Ten uprzedni rozkład prawdopodobieństwa może być oparty na wcześniejszej wiedzy o częstościach w większej populacji lub w zbiorze uczącym.

Testowanie

Poniżej znajduje się próbka, którą należy sklasyfikować jako mężczyznę lub kobietę.

Osoba wzrost (w stopach) Waga w funtach) rozmiar stopy (cale)
próbka 6 130 8

Aby sklasyfikować próbkę, należy określić, który tył jest większy, męski czy żeński. Za klasyfikację jako samca a posteriori podaje się wzorem

Za klasyfikację jako kobietę a posteriori podaje się wzorem

Dowód (nazywany również stałą normalizującą) można obliczyć:

Jednak biorąc pod uwagę próbkę, dowód jest stały, a zatem skaluje oba a posteriori w równym stopniu. Dlatego nie ma to wpływu na klasyfikację i można je zignorować. Można teraz wyznaczyć rozkład prawdopodobieństwa dla płci próbki:

,

gdzie i są parametrami rozkładu normalnego, które zostały wcześniej określone ze zbioru uczącego. Zauważ, że wartość większa niż 1 jest tutaj OK – jest to gęstość prawdopodobieństwa, a nie prawdopodobieństwo, ponieważ wysokość jest zmienną ciągłą.

Ponieważ licznik tylny jest większy w przypadku kobiet, przewiduje się, że próbka jest płci żeńskiej.

Klasyfikacja dokumentów

Oto praktyczny przykład naiwnej klasyfikacji bayesowskiej do problemu klasyfikacji dokumentów . Rozważ problem klasyfikacji dokumentów według ich zawartości, na przykład do spamu i niespamowych wiadomości e-mail . Wyobraź sobie, że dokumenty są wyciągane z wielu klas dokumentów, które można zamodelować jako zbiory słów, w których (niezależne) prawdopodobieństwo wystąpienia i-tego słowa danego dokumentu w dokumencie z klasy C można zapisać jako

(W przypadku tego traktowania, rzeczy są jeszcze bardziej uproszczone poprzez założenie, że słowa są losowo rozmieszczone w dokumencie - to znaczy słowa nie są zależne od długości dokumentu, pozycji w dokumencie w stosunku do innych słów lub innego kontekstu dokumentu. )

Wtedy prawdopodobieństwo, że dany dokument D zawiera wszystkie słowa należące do klasy C , wynosi

Pytanie, na które należy odpowiedzieć, brzmi: „jakie jest prawdopodobieństwo, że dany dokument D należy do danej klasy C ?” Innymi słowy, czym jest ?

Teraz z definicji

oraz

Twierdzenie Bayesa przekształca je w zestawienie prawdopodobieństwa w kategoriach prawdopodobieństwa .

Załóżmy, na chwilę, że istnieją tylko dwie wzajemnie wykluczające się zajęcia, S i ¬ S (np spam i nie spam), tak, że każdy element (e-mail) jest w jednej lub drugiej strony;

oraz

Korzystając z powyższego wyniku bayesowskiego można napisać:

Dzielenie jednego przez drugiego daje:

Które mogą być refaktoryzowane jako:

Zatem stosunek prawdopodobieństwa P ( S | D ) / P (Ź S | D ) może być wyrażona w kategoriach szeregu ilorazów wiarogodności . Rzeczywiste prawdopodobieństwo p( S | D ) można łatwo obliczyć z log (p( S | D ) / p(¬ S | D )) na podstawie obserwacji, że p( S | D ) + p(¬ S | D ) = 1.

Biorąc logarytm tych wszystkich stosunkach, otrzymuje się:

(Ta technika „ logarytmicznych współczynników wiarygodności ” jest powszechną techniką w statystyce. W przypadku dwóch wzajemnie wykluczających się alternatyw (takich jak ten przykład) konwersja współczynnika logarytmicznego wiarygodności na prawdopodobieństwo przyjmuje postać krzywej sigmoidalnej : zobacz logit po szczegóły.)

Wreszcie dokument można sklasyfikować w następujący sposób. Jest to spam if (tj. ), w przeciwnym razie nie jest spamem.

Zobacz też

Bibliografia

Dalsza lektura

Linki zewnętrzne

Oprogramowanie