9 Klasyfikatory bayesowskie

Całą gamę klasyfikatorów opartych na twierdzeniu Bayesa nazywać będziemy bayesowskimi. \[\begin{equation}\label{bayes} P(A|B)=\frac{P(A)P(B|A)}{P(B)}, \end{equation}\] gdzie \(P(B)>0\).

Bayesowskie reguły podejmowania decyzji dały podstawy takich metod jak:

  • liniowa analiza dyskryminacyjna;
  • kwadratowa analiza dyskryminacyjna;

W ustaleniu klasyfikatora bayesowskiego będzie nam przyświecała cały czas ta sama reguła: jeśli znam wartości cech charakteryzujących badane obiekty oraz klasy do których należą (w próbie uczącej), to na ich podstawie mogę wyznaczyć miary prawdopodobieństw a posteriori, które pomogą mi w ustaleniu klasy do której należy nowy testowy element.

W dalszej części będziemy przyjmowali następujące oznaczenia:

  • \(T\) - zbiór danych uczących (treningowych),
  • \(T^j\) - zbiór danych uczących dla których przyjęliśmy decyzję o przynależności do \(j\)-tej klasy,
  • \(T^j_{a_i=v}\) - zbiór danych uczących o wartości atrybutu \(a_i\) równej \(v\) i klasy \(j\)-tej,
  • \(\mathbb{H}\) - przestrzeń hipotez,
  • \(P(h|a_1=v_1, a_2=v_2,\ldots,a_p=v_p)\) - prawdopodobieństwo a posteriori, że prawdziwa jest hipoteza \(h\in \mathbb{H}\), jeśli znamy atrybuty obiektu,
  • \(P(h)\) - prawdopodobieństwo a priori zajścia hipotezy \(h\in \mathbb{H}\),
  • \(c\) - prawdziwy stan obiektu.

9.1 Klasyfikator maximum a posteriori (MAP)

Na podstawie wiedzy o atrybutach obiektu \(x\) podejmujemy decyzję o klasyfikacji tego obiektu zgodnie z hipotezą \(h_{MAP}\in \mathbb{H}\), która przyjmuje postać \[\begin{align}\label{MAP} h_{MAP}=&\operatorname{arg}\max_{h\in \mathbb{H}}P(h|a_1=v_1, a_2=v_2,\ldots,a_p=v_p)\\ =& \operatorname{arg}\max_{h\in \mathbb{H}}P(a_1=v_1, a_2=v_2,\ldots,a_p=v_p|h)\cdot P(h), \end{align}\] gdzie ostatnia równość wynika z twierdzenia Bayesa oraz faktu, że dla konkretnego obiektu \(x\) wielkości atrybutów nie zależą od postawionej hipotezy.

9.2 Klasyfikator największej wiarogodności (ML)

Na podstawie wiedzy o atrybutach obiektu \(x\) podejmujemy decyzję o klasyfikacji tego obiektu zgodnie z hipotezą \(h_{ML}\in \mathbb{H}\), która przyjmuje postać \[\begin{equation}\label{ML} h_{ML}=\operatorname{arg}\max_{h\in \mathbb{H}}P(a_1=v_1, a_2=v_2,\ldots,a_p=v_p|h). \end{equation}\]

Uwaga. Obie wspomniane metody wymagają znajomości prawdopodobieństwa \(P(a_1=v_1,a_2=v_2,\ldots,a_p=v_p|h)\), ale różnią się podejściem do wiedzy o prawdopodobieństwach a priori. W metodzie MAP brana pod uwagę jest wiedza o prawdopodobieństwie przynależności do poszczególnych klas, a w ML nie. Dla klasyfikacji, w których prawdopodobieństwa przynależności do klas są takie same, klasyfikatory MAP i ML są równoważne.

9.3 Naiwny klasyfikator Bayesa (NB)18

Największy problem w wyznaczeniu klasyfikatorów MAP i ML stanowi wyznaczenie rozkładu łącznego \(P(a_1=v_1, a_2=v_2,\ldots,a_p=v_p|h)\). W naiwnym klasyfikatorze Bayesa zakłada się niezależność warunkową poszczególnych atrybutów względem klasy do której ma należeń wg hipotezy obiekt. Założenie to często nie jest spełnione i stąd nazwa przymiotnik “naiwny”.

Definicja naiwnego klasyfikatora bayesowskiego różni się od klasyfikatora MAP tylko podejściem do prawdopodobieństwa a posteriori. \[\begin{equation}\label{naiwny_bayes} h_{NB}=\operatorname{arg}\max_{h_j\in \mathbb{H}}P(h_j)\prod_{i=1}^{p}P(a_i=v_i|h_j), \end{equation}\] gdzie \(h_j\) oznacza hipotezę (decyzję), że badany obiekt należy do \(j\)-tej klasy.

Oczywiście zarówno prawdopodobieństwo a priori jak i a posteriori są wyznaczane na podstawie próby, i tak prawdopodobieństwo a priori wynosi \[\begin{equation}\label{apriori} P(h_j)=P_T(h_j)=\frac{|T^j|}{|T|}, \end{equation}\] gdzie \(|A|\) oznacza moc zbioru \(A\).

Natomiast prawdopodobieństwo a posteriori dla \(i\)-tego atrybutu wynosi \[\begin{equation}\label{aposteriori} P(a_i=v_i|h_j)=P_{T^j}(a_i=v_i)=\frac{|T^j_{a_i=v_i}|}{|T^j|}. \end{equation}\] Na mocy powyższego możemy zauważyć, że jeżeli założenie o warunkowej niezależności jest spełnione, to klasyfikatory NB i MAP są równoważne.

Chcąc przypisać klasę nowemu obiektowi powstaje problem praktyczny, polegający na tym, że dla pewnych konfiguracji atrybutów nie ma odpowiedników w nauczonym modelu. Powodem takiego stanu rzeczy jest fakt, że takie kombinacje nie wystąpiły w próbie uczącej.

Istnieją dwa sposoby predykcji w takiej sytuacji:

  1. \[\begin{equation}\label{pred1} P(a_i=v_i|h_j)= \begin{cases} \frac{|T^j_{a_i=v_i}|}{|T^j|}, & T^j_{a_i=v_i}\neq \emptyset\\ \epsilon, & \text{w przeciwnym przypadku.} \end{cases} \end{equation}\] W tym przypadku przyjmuje się, że \(\epsilon \ll 1/|T_j|\).
  2. Drugi sposób wykorzystuje estymację z poprawką \[\begin{equation}\label{pred2} P(a_i=v_i|h_j)=\frac{|T^j_{a_i=v_i}|+mp}{|T^j|+mp}, \end{equation}\] gdzie \(p\) oznacza prawdopodobieństwo a priori przyjęcia przez atrybut \(a\) wartości \(v\) (najczęściej \(p=1/|A|\), \(A\) - zbiór wszystkich możliwych wartości atrybutu \(a\)), \(m\) - waga (najczęściej \(m=|A|\)).

W przypadku gdy atrybuty są mierzone na skali ciągłej najczęściej stosuje się dyskretyzację ich do zmiennych ze skali przedziałowej. Inna metoda stosowana w przypadku ciągłych atrybutów, to użycie gęstości \(g_i^j\) o rozkładzie normalnym w miejsce \(P(a_i=v_i|h_j)\). Przy czym do obliczenia parametrów rozkładu stosujemy wzory \[\begin{equation}\label{sred} m_i^j=\frac{1}{|T^j|}\sum_{x\in T^j}a_i(x), \end{equation}\] oraz \[\begin{equation}\label{odch} (s_i^j)^2=\frac{1}{|T^j|-1}\sum_{x\in T^j}(a_i(x)-m_i^j)^2. \end{equation}\]

Obsługa braków danych przez naiwny klasyfikator Bayesa jest dość prosta i opiera się na liczeniu prawdopodobieństw a posteriori wyłącznie dla obiektów, których wartości atrybutów są znane. Dlatego prawdopodobieństwa warunkowe liczy się wg wzoru \[\begin{equation}\label{pr_war} P(a_i=v_i|h_j)=\frac{|T^j_{a_i=v_i}|}{|T^j|-|T^j_{a_i=NA}|}. \end{equation}\] Jeśli brakujące dane nie niosą w sobie istotnych informacji dotyczących klasyfikacji obiektów, to naiwny klasyfikator Bayesa będzie działał poprawnie.

Naiwny klasyfikator Bayesa jest implementowany w pakietach e1071 (Meyer et al. 2019) i klaR (Weihs et al. 2005).

Przykład 9.1 Przeprowadzimy klasyfikację dla zbioru Titanic. W przypadku funkcji z pakietu e1071 nie potrzeba zamieniać tabeli na przypadki. W pakiecie klaR istnieje inna funkcja budująca klasyfikator Bayesa NaiveBayes, ale w tym przypadku jeśli zbiór jest w formie tabeli, to należy go zamienić na ramkę danych z oddzielnymi przypadkami.

library(e1071)
Titanic
## , , Age = Child, Survived = No
## 
##       Sex
## Class  Male Female
##   1st     0      0
##   2nd     0      0
##   3rd    35     17
##   Crew    0      0
## 
## , , Age = Adult, Survived = No
## 
##       Sex
## Class  Male Female
##   1st   118      4
##   2nd   154     13
##   3rd   387     89
##   Crew  670      3
## 
## , , Age = Child, Survived = Yes
## 
##       Sex
## Class  Male Female
##   1st     5      1
##   2nd    11     13
##   3rd    13     14
##   Crew    0      0
## 
## , , Age = Adult, Survived = Yes
## 
##       Sex
## Class  Male Female
##   1st    57    140
##   2nd    14     80
##   3rd    75     76
##   Crew  192     20
nb <- naiveBayes(Survived ~ ., data = Titanic)
nb$apriori
## Survived
##   No  Yes 
## 1490  711

Poniższe tabele zawierają warunkowe prawdopodobieństwa przynależności do poszczególnych klas.

nb$tables
## $Class
##         Class
## Survived        1st        2nd        3rd       Crew
##      No  0.08187919 0.11208054 0.35436242 0.45167785
##      Yes 0.28551336 0.16596343 0.25035162 0.29817159
## 
## $Sex
##         Sex
## Survived       Male     Female
##      No  0.91543624 0.08456376
##      Yes 0.51617440 0.48382560
## 
## $Age
##         Age
## Survived      Child      Adult
##      No  0.03489933 0.96510067
##      Yes 0.08016878 0.91983122
dane <- as.data.frame(Titanic)
pred <- predict(nb, dane)
pred
##  [1] Yes No  No  No  Yes Yes Yes Yes No  No  No  No  Yes Yes Yes Yes Yes No  No 
## [20] No  Yes Yes Yes Yes No  No  No  No  Yes Yes Yes Yes
## Levels: No Yes
tab <- table(pred, dane$Survived)
tab
##      
## pred  No Yes
##   No   7   7
##   Yes  9   9
sum(diag(prop.table(tab)))
## [1] 0.5

Naiwny klasyfikator spisał się bardzo słabo, ponieważ klasyfikacja na poziomie 0.5 jest taka jak przy rzucie monetą.

Przykład 9.2 Przeprowadzimy klasyfikację gatunków irysów na podstawie szerokości i długości kielicha i płatka.

library(klaR)
set.seed(2019)
uczaca <- sample(1:nrow(iris), 2*nrow(iris)/3)
pr.ucz <- iris[uczaca,]
pr.test <- iris[-uczaca,]
nb2 <- NaiveBayes(Species~., data = pr.ucz)
nb2$apriori
## grouping
##     setosa versicolor  virginica 
##       0.35       0.32       0.33

Prawdopodobieństwa a priori zostały oszacowane na podstawie próby uczącej. Poniższe tabele zawierają średnie i odchylenia standardowe zmiennych w poszczególnych klasach.

nb2$tables
## $Sepal.Length
##                [,1]      [,2]
## setosa     4.982857 0.3485143
## versicolor 6.003125 0.5462390
## virginica  6.463636 0.5808497
## 
## $Sepal.Width
##                [,1]      [,2]
## setosa     3.408571 0.3616721
## versicolor 2.750000 0.3537814
## virginica  2.960606 0.2838787
## 
## $Petal.Length
##                [,1]      [,2]
## setosa     1.480000 0.1875539
## versicolor 4.275000 0.4852668
## virginica  5.460606 0.5225774
## 
## $Petal.Width
##                 [,1]      [,2]
## setosa     0.2657143 0.1109925
## versicolor 1.3437500 0.2198790
## virginica  2.0151515 0.3123712
pred <- predict(nb2, newdata = pr.test)
tab <- table(pred$class, pr.test$Species)
tab
##             
##              setosa versicolor virginica
##   setosa         15          0         0
##   versicolor      0         17         0
##   virginica       0          1        17
sum(diag(prop.table(tab)))
## [1] 0.98

Klasyfikacja na podstawie modelu jest bardzo dobra (98%).

9.4 Zalety i wady

  • Zalety:
    • prostota konstrukcji i prosty algorytm;
    • jeśli jest spełnione założenie warunkowej niezależności, to ten klasyfikator działa szybciej i czasem lepiej niż inne metody klasyfikacji;
    • nie potrzebuje dużych zbiorów danych do estymacji parametrów;
  • Wady:
    • często nie spełnione założenie o warunkowej niezależności powoduje obciążenie wyników;
    • brak możliwości wprowadzania interakcji efektów kilku zmiennych;
    • potrzebuje założenia normalności warunkowych gęstości w przypadku ciągłych atrybutów;
    • często istnieją lepsze klasyfikatory.

Bibliografia

Meyer, David, Evgenia Dimitriadou, Kurt Hornik, Andreas Weingessel, and Friedrich Leisch. 2019. E1071: Misc Functions of the Department of Statistics, Probability Theory Group (Formerly: E1071), TU Wien. https://CRAN.R-project.org/package=e1071.
Weihs, Claus, Uwe Ligges, Karsten Luebke, and Nils Raabe. 2005. “klaR Analyzing German Business Cycles.” In Data Analysis and Decision Support, edited by D. Baier, R. Decker, and L. Schmidt-Thieme, 335–43. Berlin: Springer-Verlag.

  1. ang. Naive Bayes Classifier↩︎