Hvordan Naive Bayes-klassifikatorer fungerer - med eksempler på Python-kode

Naive Bayes Classifiers (NBC) er enkle, men kraftfulde maskinindlæringsalgoritmer. De er baseret på betinget sandsynlighed og Bayes sætning.

I dette indlæg forklarer jeg "tricket" bag NBC, og jeg giver dig et eksempel, som vi kan bruge til at løse et klassificeringsproblem.

I de næste sektioner vil jeg tale om matematikken bag NBC. Spring over disse sektioner og gå til implementeringsdelen, hvis du ikke er interesseret i matematikken.

I implementeringsafsnittet viser jeg dig en simpel NBC-algoritme. Så bruger vi det til at løse et klassificeringsproblem. Opgaven vil være at afgøre, om en bestemt passager på Titanic overlevede ulykken eller ej.

Betinget sandsynlighed

Før vi taler om algoritmen, lad os tale om den enkle matematik bag den. Vi er nødt til at forstå, hvad betinget sandsynlighed er, og hvordan kan vi bruge Bayes 'sætning til at beregne det.

Tænk på en retfærdig die med seks sider. Hvad er sandsynligheden for at få en seks, når du ruller matricen? Det er let, det er 1/6. Vi har seks mulige og lige så sandsynlige resultater, men vi er kun interesseret i et af dem. Så 1/6 er det.

Men hvad sker der, hvis jeg fortæller dig, at jeg allerede har rullet matricen, og resultatet er et lige antal? Hvad er sandsynligheden for, at vi har en seks nu?

Denne gang er de mulige resultater kun tre, fordi der kun er tre lige tal på matricen. Vi er stadig interesseret i kun et af disse resultater, så nu er sandsynligheden større: 1/3. Hvad er forskellen mellem begge sager?

I det første tilfælde havde vi ingen forudgående oplysninger om resultatet. Derfor var vi nødt til at overveje hvert eneste mulige resultat.

I det andet tilfælde fik vi at vide, at resultatet var et lige antal, så vi kunne reducere pladsen til mulige resultater til kun de tre lige tal, der vises i en regelmæssig seks-sidet terning.

Generelt siger vi, når vi beregner sandsynligheden for en begivenhed A, givet forekomsten af ​​en anden begivenhed B, at vi beregner den betingede sandsynlighed for A givet B eller bare sandsynligheden for A givet B. Vi betegner det P(A|B).

For eksempel, sandsynligheden for at få en seks givet, at antallet vi har fået endnu: P(Six|Even) = 1/3. Her betegnet vi med Six begivenheden for at få en seks og med Even begivenheden for at få et lige antal.

Men hvordan beregner vi betingede sandsynligheder? Er der en formel?

Sådan beregnes betingede probs og Bayes sætning

Nu giver jeg dig et par formler til beregning af betingede probs. Jeg lover, at de ikke bliver hårde, og de er vigtige, hvis du vil forstå indsigten i maskinindlæringsalgoritmerne, vi vil tale om senere.

Sandsynligheden for en begivenhed A givet forekomsten af ​​en anden begivenhed B kan beregnes som følger:

P(A|B) = P(A,B)/P(B) 

Hvor P(A,B)betegner sandsynligheden for, at både A og B forekommer på samme tid, og P(B)betegner sandsynligheden for B.

Bemærk, at vi har brug for, P(B) > 0fordi det ikke giver mening at tale om sandsynligheden for A givet B, hvis forekomsten af ​​B ikke er mulig.

Vi kan også beregne sandsynligheden for en begivenhed A, givet forekomsten af ​​flere begivenheder B1, B2, ..., Bn:

P(A|B1,B2,...,Bn) = P(A,B1,B2,...,Bn)/P(B1,B2,...,Bn) 

Der er en anden måde at beregne betingede probs på. Denne måde er den såkaldte Bayes's sætning.

P(A|B) = P(B|A)P(A)/P(B) P(A|B1,B2,...,Bn) = P(B1,B2,...,Bn|A)P(A)/P(B1,B2,...,Bn) 

Bemærk, at vi beregner sandsynligheden for begivenhed A givet begivenheden B ved at vende om rækkefølgen af ​​begivenhederne.

Nu antager vi, at begivenheden A er sket, og vi vil beregne sandsynligheden for begivenhed B (eller begivenheder B1, B2, ..., Bn i det andet og mere generelle eksempel).

En vigtig kendsgerning, der kan udledes af denne sætning, er formlen, der skal beregnes P(B1,B2,...,Bn,A). Det kaldes kædereglen for sandsynligheder.

P(B1,B2,...,Bn,A) = P(B1 | B2, B3, ..., Bn, A)P(B2,B3,...,Bn,A) = P(B1 | B2, B3, ..., Bn, A)P(B2 | B3, B4, ..., Bn, A)P(B3, B4, ..., Bn, A) = P(B1 | B2, B3, ..., Bn, A)P(B2 | B3, B4, ..., Bn, A)...P(Bn | A)P(A) 

Det er en grim formel, ikke? Men under nogle betingelser kan vi løse en løsning og undgå det.

Lad os tale om det sidste koncept, vi har brug for at forstå for at forstå algoritmerne.

Uafhængighed

Det sidste koncept, vi skal tale om, er uafhængighed. Vi siger, at begivenhederne A og B er uafhængige, hvis

P(A|B) = P(A) 

Det betyder, at sandsynligheden for begivenhed A ikke påvirkes af begivenheden B. En direkte konsekvens er, at P(A,B) = P(A)P(B).

På almindelig engelsk betyder dette, at sandsynligheden for forekomsten af ​​både A og B på samme tid er lig med produktet af sonderne for begivenhederne A og B, der forekommer separat.

Hvis A og B er uafhængige, fastslår det også, at:

P(A,B|C) = P(A|C)P(B|C) 

Nu er vi klar til at tale om Naive Bayes-klassifikatorer!

Naive Bayes klassifikatorer

Antag, at vi har en vektor X med n- funktioner, og vi vil bestemme klassen for denne vektor ud fra et sæt k- klasser y1, y2, ..., yk . For eksempel hvis vi vil afgøre, om det regner i dag eller ej.

Vi har to mulige klasser ( k = 2 ): regn , ikke regn , og længden af ​​vektoren af ​​funktioner kan være 3 ( n = 3 ).

Den første funktion kan være, om det er overskyet eller solrigt, det andet kan være, om luftfugtigheden er høj eller lav, og den tredje funktion er, om temperaturen er høj, medium eller lav.

Så disse kunne være mulige funktionsvektorer.

Vores opgave er at afgøre, om det regner eller ej i betragtning af vejrfunktionerne.

Efter at have lært om betingede sandsynligheder synes det naturligt at nærme sig problemet ved at prøve at beregne sandsynligheden for regn i betragtning af funktionerne:

R = P(Rain | Cloudy, H_High, T_Low) NR = P(NotRain | Cloudy, H_High, T_Low) 

Hvis R > NRvi svarer, at det regner, ellers siger vi, at det ikke vil.

Generelt, hvis vi har k- klasser y1, y2, ..., yk og en vektor af n har X = , vil vi finde den klasse yi, der maksimerer

P(yi | X1, X2, ..., Xn) = P(X1, X2,..., Xn, yi)/P(X1, X2, ..., Xn) 

Bemærk, at nævneren er konstant, og at den ikke afhænger af klassen yi . Så vi kan ignorere det og bare fokusere på tælleren.

I et tidligere afsnit så vi, hvordan man beregner P(X1, X2,..., Xn, yi)ved at nedbryde det i et produkt med betingede sandsynligheder (den grimme formel):

P(X1, X2,..., Xn, yi) = P(X1 | X2,..., Xn, yi)P(X2 | X3,..., Xn, yi)...P(Xn | yi)P(yi) 

Forudsat at alle funktionerne Xi er uafhængige og bruger Bayes's sætning, kan vi beregne den betingede sandsynlighed som følger:

P(yi | X1, X2,..., Xn) = P(X1, X2,..., Xn | yi)P(yi)/P(X1, X2, ..., Xn) = P(X1 | yi)P(X2 | yi)...P(Xn | yi)P(yi)/P(X1, X2, ..., Xn) 

Og vi skal bare fokusere på tælleren.

Ved at finde klassen yi, der maksimerer det forrige udtryk, klassificerer vi inputvektoren. Men hvordan kan vi få alle disse sandsynligheder?

Sådan beregnes sandsynlighederne

Når vi løser denne slags problemer, skal vi have et sæt tidligere klassificerede eksempler.

For eksempel i spørgsmålet om at gætte, om det regner eller ej, skal vi have flere eksempler på funktionsvektorer og deres klassifikationer for, at de ville fås fra tidligere vejrudsigter.

Så vi ville have noget som dette:

...  -> Rain  -> Not Rain  -> Not Rain ... 

Antag, at vi har brug for at klassificere en ny vektor . Vi skal beregne:

P(Rain | Cloudy, H_Low, T_Low) = P(Cloudy | H_Low, T_Low, Rain)P(H_Low | T_Low, Rain)P(T_Low | Rain)P(Rain)/P(Cloudy, H_Low, T_Low) 

Vi får det tidligere udtryk ved at anvende definitionen af ​​betinget sandsynlighed og kædereglen. Husk, at vi kun behøver at fokusere på tælleren, så vi kan droppe nævneren.

Vi skal også beregne sandsynligheden for NotRain, men vi kan gøre dette på en lignende måde.

Vi kan finde P(Rain) = # Rain/Total. Det betyder at tælle poster i datasættet, der er klassificeret med Rain, og dividere dette nummer med datasættets størrelse.

For at beregne skal P(Cloudy | H_Low, T_Low, Rain)vi tælle alle de poster, der har funktionerne H_Low, T_Low og Cloudy . Disse poster skal også klassificeres som Rain. Derefter divideres dette tal med den samlede mængde data. Vi beregner resten af ​​faktorerne i formlen på en lignende måde.

At foretage disse beregninger for hver mulig klasse er meget dyrt og langsomt. Så vi er nødt til at tage antagelser om problemet, der forenkler beregningerne.

Naive Bayes-klassifikatorer antager, at alle funktionerne er uafhængige af hinanden. Så vi kan omskrive vores formel, der anvender Bayes 'sætning og antage uafhængighed mellem hvert par funktioner:

P(Rain | Cloudy, H_Low, T_Low) = P(Cloudy | Rain)P(H_Low | Rain)P(T_Low | Rain)P(Rain)/P(Cloudy, H_Low, T_Low) 

Nu beregner vi at P(Cloudy | Rain)tælle antallet af poster, der er klassificeret som Rainog var Cloudy.

The algorithm is called Naive because of this independence assumption. There are dependencies between the features most of the time. We can't say that in real life there isn't a dependency between the humidity and the temperature, for example. Naive Bayes Classifiers are also called Independence Bayes, or Simple Bayes.

The general formula would be:

P(yi | X1, X2, ..., Xn) = P(X1 | yi)P(X2 | yi)...P(Xn | yi)P(yi)/P(X1, X2, ..., Xn) 

Remember you can get rid of the denominator. We only calculate the numerator and answer the class that maximizes it.

Now, let's implement our NBC and let's use it in a problem.

Let's code!

I will show you an implementation of a simple NBC and then we'll see it in practice.

The problem we are going to solve is determining whether a passenger on the Titanic survived or not, given some features like their gender and their age.

Here you can see the implementation of a very simple NBC:

class NaiveBayesClassifier: def __init__(self, X, y): ''' X and y denotes the features and the target labels respectively ''' self.X, self.y = X, y self.N = len(self.X) # Length of the training set self.dim = len(self.X[0]) # Dimension of the vector of features self.attrs = [[] for _ in range(self.dim)] # Here we'll store the columns of the training set self.output_dom = {} # Output classes with the number of ocurrences in the training set. In this case we have only 2 classes self.data = [] # To store every row [Xi, yi] for i in range(len(self.X)): for j in range(self.dim): # if we have never seen this value for this attr before, # then we add it to the attrs array in the corresponding position if not self.X[i][j] in self.attrs[j]: self.attrs[j].append(self.X[i][j]) # if we have never seen this output class before, # then we add it to the output_dom and count one occurrence for now if not self.y[i] in self.output_dom.keys(): self.output_dom[self.y[i]] = 1 # otherwise, we increment the occurrence of this output in the training set by 1 else: self.output_dom[self.y[i]] += 1 # store the row self.data.append([self.X[i], self.y[i]]) def classify(self, entry): solve = None # Final result max_arg = -1 # partial maximum for y in self.output_dom.keys(): prob = self.output_dom[y]/self.N # P(y) for i in range(self.dim): cases = [x for x in self.data if x[0][i] == entry[i] and x[1] == y] # all rows with Xi = xi n = len(cases) prob *= n/self.N # P *= P(Xi = xi) # if we have a greater prob for this output than the partial maximum... if prob > max_arg: max_arg = prob solve = y return solve 

Here, we assume every feature has a discrete domain. That means they take a value from a finite set of possible values.

The same happens with classes. Notice that we store some data in the __init__ method so we don't need to repeat some operations. The classification of a new entry is carried on in the classify method.

This is a simple example of an implementation. In real world applications you don't need (and is better if you don't make) your own implementation. For example, the sklearn library in Python contains several good implementations of NBC's.

Notice how easy it is to implement it!

Now, let's apply our new classifier to solve a problem. We have a dataset with the description of 887 passengers on the Titanic. We also can see whether a given passenger survived the tragedy or not.

So our task is to determine if another passenger that is not included in the training set made it or not.

In this example, I'll be using the pandas library to read and process the data. I don't use any other tool.

The data is stored in a file called titanic.csv, so the first step is to read the data and get an overview of it.

import pandas as pd data = pd.read_csv('titanic.csv') print(data.head()) 

The output is:

Survived Pclass Name \ 0 0 3 Mr. Owen Harris Braund 1 1 1 Mrs. John Bradley (Florence Briggs Thayer) Cum... 2 1 3 Miss. Laina Heikkinen 3 1 1 Mrs. Jacques Heath (Lily May Peel) Futrelle 4 0 3 Mr. William Henry Allen Sex Age Siblings/Spouses Aboard Parents/Children Aboard Fare 0 male 22.0 1 0 7.2500 1 female 38.0 1 0 71.2833 2 female 26.0 0 0 7.9250 3 female 35.0 1 0 53.1000 4 male 35.0 0 0 8.0500 

Notice we have the Name of each passenger. We won't use that feature for our classifier because it is not significant for our problem. We'll also get rid of the Fare feature because it is continuous and our features need to be discrete.

There are Naive Bayes Classifiers that support continuous features. For example, the Gaussian Naive Bayes Classifier.

y = list(map(lambda v: 'yes' if v == 1 else 'no', data['Survived'].values)) # target values as string # We won't use the 'Name' nor the 'Fare' field X = data[['Pclass', 'Sex', 'Age', 'Siblings/Spouses Aboard', 'Parents/Children Aboard']].values # features values 

Then, we need to separate our data set in a training set and a validation set. The later is used to validate how well our algorithm is doing.

print(len(y)) # >> 887 # We'll take 600 examples to train and the rest to the validation process y_train = y[:600] y_val = y[600:] X_train = X[:600] X_val = X[600:] 

We create our NBC with the training set and then classify every entry in the validation set.

We measure the accuracy of our algorithm by dividing the number of entries it correctly classified by the total number of entries in the validation set.

## Creating the Naive Bayes Classifier instance with the training data nbc = NaiveBayesClassifier(X_train, y_train) total_cases = len(y_val) # size of validation set # Well classified examples and bad classified examples good = 0 bad = 0 for i in range(total_cases): predict = nbc.classify(X_val[i]) # print(y_val[i] + ' --------------- ' + predict) if y_val[i] == predict: good += 1 else: bad += 1 print('TOTAL EXAMPLES:', total_cases) print('RIGHT:', good) print('WRONG:', bad) print('ACCURACY:', good/total_cases) 

The output:

TOTAL EXAMPLES: 287 RIGHT: 200 WRONG: 87 ACCURACY: 0.6968641114982579 

It's not great but it's something. We can get about a 10% accuracy improvement if we get rid of other features like Siblings/Spouses Aboard and Parents/Children Aboard.

You can see a notebook with the code and the dataset here

Conclusions

Today, we have neural networks and other complex and expensive ML algorithms all over the place.

NBCs are very simple algorithms that let us achieve good results in some classification problems without needing a lot of resources. They also scale very well, which means we can add a lot more features and the algorithm will still be fast and reliable.

Even in a case where NBCs were not a good fit for the problem we were trying to solve, they might be very useful as a baseline.

We could first try to solve the problem using an NBC with a few lines of code and little effort. Then we could try to achieve better results with more complex and expensive algorithms.

This process can save us a lot of time and gives us an immediate feedback about whether complex algorithms are really worth it for our task.

I denne artikel læser du om betingede sandsynligheder, uafhængighed og Bayes's sætning. Det er de matematiske begreber bag Naive Bayes Classifiers.

Derefter så vi en simpel implementering af en NBC og løste problemet med at afgøre, om en passager på Titanic overlevede ulykken.

Jeg håber, du fandt denne artikel nyttig. Du kan læse om datalogi-relaterede emner i min personlige blog og ved at følge mig på Twitter.