Naivni Bayesovi klasifikatori (NBC) jednostavni su, ali moćni algoritmi strojnog učenja. Oni se temelje na uvjetnoj vjerojatnosti i Bayesovom teoremu.
U ovom postu objašnjavam "trik" koji stoji iza NBC-a i dat ću vam primjer koji možemo koristiti za rješavanje problema s klasifikacijom.
U sljedećim odjeljcima govorit ću o matematici iza NBC-a. Slobodno preskočite te odjeljke i prijeđite na implementacijski dio ako vas matematika ne zanima.
U odjeljku za implementaciju pokazat ću vam jednostavan NBC algoritam. Tada ćemo ga koristiti za rješavanje problema s klasifikacijom. Zadatak će biti utvrditi je li određeni putnik na Titanicu preživio nesreću ili nije.
Uvjetna vjerojatnost
Prije nego što razgovaramo o samom algoritmu, razgovarajmo o jednostavnoj matematici koja stoji iza njega. Moramo razumjeti što je uvjetna vjerojatnost i kako možemo koristiti Bayesov teorem da bismo je izračunali.
Razmislite o poštenoj kocki sa šest strana. Kolika je vjerojatnost dobivanja šestice prilikom valjanja kockice? To je lako, 1/6 je. Imamo šest mogućih i jednako vjerojatnih ishoda, ali nas zanima samo jedan od njih. Dakle, 1/6 je.
Ali što će se dogoditi ako vam kažem da sam već izvaljao matricu i ishod je paran broj? Kolika je vjerojatnost da smo sada dobili šesticu?
Ovaj put su mogući ishodi samo tri, jer na matricu postoje samo tri parna broja. Još uvijek nas zanima samo jedan od tih ishoda, pa je sada vjerojatnost veća: 1/3. Koja je razlika između oba slučaja?
U prvom slučaju nismo imali prethodne informacije o ishodu. Stoga smo trebali razmotriti svaki pojedini mogući rezultat.
U drugom slučaju, rečeno nam je da je ishod paran broj, pa bismo prostor mogućih ishoda mogli svesti na samo tri parna broja koja se pojavljuju u redovnom šestostranom kalupu.
Općenito, pri izračunavanju vjerojatnosti događaja A, s obzirom na pojavu drugog događaja B, kažemo da izračunavamo uvjetnu vjerojatnost A datog B ili samo vjerojatnosti A datog B. Označavamo ga P(A|B).
Na primjer, vjerojatnost dobivanja šest obzirom da je broj smo dobili još: P(Six|Even) = 1/3. Ovdje smo sa Šest označili događaj dobivanja šestice, a s Even događajem dobivanja parnog broja.
Ali, kako izračunati uvjetne vjerojatnosti? Postoji li formula?
Kako izračunati uvjetne probe i Bayesov teorem
Sad ću vam dati nekoliko formula za izračunavanje uvjetnih problema. Obećavam da im neće biti teško, a važni su ako želite razumjeti uvide algoritama strojnog učenja o kojima ćemo kasnije razgovarati.
Vjerojatnost događaja A s obzirom na pojavu drugog događaja B može se izračunati na sljedeći način:
P(A|B) = P(A,B)/P(B) Gdje P(A,B)označava vjerojatnost istodobnog pojavljivanja A i B, a P(B)označava vjerojatnost B.
Primijetite da trebamo P(B) > 0jer nema smisla govoriti o vjerojatnosti A datog B ako pojava B nije moguća.
Također možemo izračunati vjerojatnost događaja A, s obzirom na pojavu više događaja B1, B2, ..., Bn:
P(A|B1,B2,...,Bn) = P(A,B1,B2,...,Bn)/P(B1,B2,...,Bn) Postoji još jedan način izračuna uvjetnih proba. Ovaj način je takozvani Bayesov teorem.
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) Primijetimo da izračunavamo vjerojatnost događaja A s obzirom na događaj B, obrnutim redoslijedom događaja.
Sada pretpostavljamo da se dogodio događaj A i želimo izračunati problem događaja B (ili događaji B1, B2, ..., Bn u drugom i općenitijem primjeru).
Važna činjenica koja se može izvesti iz ovog teorema je formula za izračunavanje P(B1,B2,...,Bn,A). To se naziva lančanim pravilom vjerojatnosti.
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) To je ružna formula, zar ne? Ali pod nekim uvjetima možemo zaobići i izbjeći ga.
Razgovarajmo o posljednjem konceptu koji moramo znati da bismo razumjeli algoritme.
Neovisnost
Posljednji koncept o kojem ćemo razgovarati je neovisnost. Kažemo da su događaji A i B neovisni ako
P(A|B) = P(A) To znači da na događaj događaja A ne utječe pojava događaja B. Izravna posljedica je ta P(A,B) = P(A)P(B).
Jednostavno rečeno, to znači da je proba istodobnog pojavljivanja i A i B jednaka umnošku probnih događaja događaja A i B koji se događaju odvojeno.
Ako su A i B neovisni, također vrijedi da:
P(A,B|C) = P(A|C)P(B|C) Sada smo spremni razgovarati o naivnim Bayesovim klasifikatorima!
Naivni Bayesovi klasifikatori
Pretpostavimo da imamo vektor X od n obilježja i želimo odrediti klasu tog vektora iz skupa k klasa y1, y2, ..., yk . Na primjer, ako želimo utvrditi hoće li danas padati kiša ili ne.
Imamo dvije moguće klase ( k = 2 ): kiša , ne kiša , a duljina vektora značajki može biti 3 ( n = 3 ).
Prva značajka može biti je li oblačno ili sunčano, druga značajka može biti visoka ili niska vlaga, a treća značajka je li temperatura visoka, srednja ili niska.
Dakle, to bi mogli biti mogući vektori značajki.
Naš je zadatak utvrditi hoće li kiša padati ili ne, s obzirom na vremenske značajke.
Nakon učenja o uvjetnim vjerojatnostima, čini se prirodnim pristupiti problemu pokušavajući izračunati vjerojatnost kiše s obzirom na značajke:
R = P(Rain | Cloudy, H_High, T_Low) NR = P(NotRain | Cloudy, H_High, T_Low) Ako R > NRodgovorimo da će kiša padati, inače kažemo da neće.
Općenito, ako imamo k klasa y1, y2, ..., yk i vektor od n značajki X = , želimo pronaći klasu yi koja maksimizira
P(yi | X1, X2, ..., Xn) = P(X1, X2,..., Xn, yi)/P(X1, X2, ..., Xn) Primijetite da je nazivnik konstantan i da ne ovisi o klasi yi . Dakle, možemo ga zanemariti i samo se usredotočiti na brojnik.
U prethodnom smo odjeljku vidjeli kako izračunati P(X1, X2,..., Xn, yi)rastavljajući ga u umnožak uvjetnih vjerojatnosti (ružna formula):
P(X1, X2,..., Xn, yi) = P(X1 | X2,..., Xn, yi)P(X2 | X3,..., Xn, yi)...P(Xn | yi)P(yi) Pod pretpostavkom da su sve značajke Xi neovisne i koristeći Bayesov teorem, uvjetnu vjerojatnost možemo izračunati na sljedeći način:
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) A mi se samo trebamo usredotočiti na brojnik.
Pronalaskom klase yi koja maksimizira prethodni izraz, klasificiramo ulazni vektor. Ali, kako možemo dobiti sve te vjerojatnosti?
Kako izračunati vjerojatnosti
Prilikom rješavanja ove vrste problema moramo imati niz prethodno klasificiranih primjera.
Na primjer, u problemu pogađanja hoće li padati kiša ili ne, trebamo imati nekoliko primjera vektora značajki i njihove klasifikacije koje bi se dobivale iz prošlih vremenskih prognoza.
Dakle, imali bismo otprilike ovako:
... -> Rain -> Not Rain -> Not Rain ... Pretpostavimo da moramo klasificirati novi vektor . Moramo izračunati:
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) Prethodni izraz dobivamo primjenom definicije uvjetne vjerojatnosti i lančanog pravila. Zapamtite da se moramo usredotočiti samo na brojnik kako bismo mogli ispustiti nazivnik.
Također moramo izračunati vjerojatnost za NotRain, ali to možemo učiniti na sličan način.
Možemo pronaći P(Rain) = # Rain/Total. To znači brojanje unosa u skupu podataka koji su klasificirani s Rain i dijeljenje tog broja s veličinom skupa podataka.
Za izračunavanje P(Cloudy | H_Low, T_Low, Rain)moramo izbrojati sve unose koji imaju značajke H_Low, T_Low i Cloudy . Te unose također treba klasificirati kao Rain. Zatim se taj broj podijeli s ukupnom količinom podataka. Na sličan način izračunavamo i ostale čimbenike formule.
Izračunavanje tih izračuna za svaku moguću klasu vrlo je skupo i sporo. Stoga moramo iznijeti pretpostavke o problemu koje pojednostavljuju izračune.
Naivni Bayesovi klasifikatori pretpostavljaju da su sve značajke neovisne jedna o drugoj. Tako možemo prepisati našu formulu primjenjujući Bayesov teorem i pretpostavljajući neovisnost između svakog para značajki:
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) Sada izračunavamo P(Cloudy | Rain)brojeći broj unosa koji su klasificirani kao Raini koji su bili 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.
In this article you read about conditional probabilities, independence, and Bayes's Theorem. Those are the Mathematical concepts behind Naive Bayes Classifiers.
After that, we saw a simple implementation of an NBC and solved the problem of determining whether a passenger on the Titanic survived the accident.
I hope you found this article useful. You can read about Computer Science related topics in my personal blog and by following me on Twitter.