Πώς λειτουργούν οι ταξινομητές Naive Bayes - με παραδείγματα κώδικα Python

Οι Naive Bayes Classifiers (NBC) είναι απλοί αλλά ισχυροί αλγόριθμοι μηχανικής μάθησης. Βασίζονται στην υπό όρους πιθανότητα και στο Θεώρημα του Bayes.

Σε αυτήν την ανάρτηση, εξηγώ το «κόλπο» πίσω από το NBC και θα σας δώσω ένα παράδειγμα που μπορούμε να χρησιμοποιήσουμε για να λύσουμε ένα πρόβλημα ταξινόμησης.

Στις επόμενες ενότητες, θα μιλήσω για τα μαθηματικά πίσω από το NBC. Μη διστάσετε να παραλείψετε αυτές τις ενότητες και να μεταβείτε στο μέρος υλοποίησης εάν δεν σας ενδιαφέρουν τα μαθηματικά.

Στην ενότητα υλοποίησης, θα σας δείξω έναν απλό αλγόριθμο NBC. Τότε θα το χρησιμοποιήσουμε για να λύσουμε ένα πρόβλημα ταξινόμησης. Ο στόχος θα είναι να καθοριστεί εάν ένας επιβάτης του Τιτανικού επέζησε του ατυχήματος ή όχι.

Υπό όρους πιθανότητα

Πριν μιλήσουμε για τον ίδιο τον αλγόριθμο, ας μιλήσουμε για τα απλά μαθηματικά πίσω από αυτόν. Πρέπει να καταλάβουμε ποια είναι η πιθανότητα υπό όρους και πώς μπορούμε να χρησιμοποιήσουμε το Θεώρημα του Bayes για να το υπολογίσουμε.

Σκεφτείτε μια δίκαιη μήτρα με έξι πλευρές. Ποια είναι η πιθανότητα να κερδίσετε έξι όταν ρίξετε τη μήτρα; Αυτό είναι εύκολο, είναι 1/6. Έχουμε έξι πιθανά και εξίσου πιθανά αποτελέσματα, αλλά μας ενδιαφέρει μόνο ένα από αυτά. Λοιπόν, το 1/6 είναι.

Αλλά τι θα συμβεί αν σας πω ότι έχω ήδη κυλήσει τη μήτρα και το αποτέλεσμα είναι ένας ζυγός αριθμός; Ποια είναι η πιθανότητα να έχουμε έξι τώρα;

Αυτή τη φορά, τα πιθανά αποτελέσματα είναι μόνο τρία, επειδή υπάρχουν μόνο τρεις ζυγοί αριθμοί στη μήτρα. Μας ενδιαφέρει ακόμα ένα από αυτά τα αποτελέσματα, οπότε τώρα η πιθανότητα είναι μεγαλύτερη: 1/3. Ποια είναι η διαφορά μεταξύ των δύο περιπτώσεων;

Στην πρώτη περίπτωση, δεν είχαμε προηγούμενες πληροφορίες σχετικά με το αποτέλεσμα. Επομένως, έπρεπε να εξετάσουμε κάθε πιθανό αποτέλεσμα.

Στη δεύτερη περίπτωση, μας είπαν ότι το αποτέλεσμα ήταν ένας ζυγός αριθμός, οπότε θα μπορούσαμε να μειώσουμε το χώρο των πιθανών αποτελεσμάτων μόνο στους τρεις ζυγούς αριθμούς που εμφανίζονται σε ένα κανονικό εξάπλευρο κύβος.

Σε γενικές γραμμές, κατά τον υπολογισμό της πιθανότητας ενός συμβάντος Α, δεδομένης της εμφάνισης ενός άλλου συμβάντος Β, λέμε ότι υπολογίζουμε την πιθανότητα υπό όρους του Α δεδομένου Β ή απλώς την πιθανότητα του δεδομένου Α. Το υποδηλώνουμε P(A|B).

Για παράδειγμα, η πιθανότητα του να πάρει ένα έξι, δεδομένου ότι ο αριθμός έχουμε είναι ακόμη: P(Six|Even) = 1/3. Εδώ εμείς, συμβολίζουμε με Έξι το γεγονός να πάρει ένα έξι και με το Ζυγό το γεγονός να πάρει έναν ζυγό αριθμό

Αλλά, πώς υπολογίζουμε τις πιθανότητες υπό όρους; Υπάρχει ένας τύπος;

Πώς να υπολογίσετε ανιχνευτές υπό όρους και το Θεώρημα του Bayes

Τώρα, θα σας δώσω μερικούς τύπους για τον υπολογισμό των υπό όρους ανιχνευτών. Υπόσχομαι ότι δεν θα είναι δύσκολο και είναι σημαντικό αν θέλετε να κατανοήσετε τις γνώσεις των αλγορίθμων Machine Learning για τις οποίες θα μιλήσουμε αργότερα.

Η πιθανότητα ενός συμβάντος Α δεδομένης της εμφάνισης ενός άλλου συμβάντος Β μπορεί να υπολογιστεί ως εξής:

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

Όπου P(A,B)υποδηλώνει την πιθανότητα εμφάνισης τόσο του Α όσο και του Β ταυτόχρονα, και P(B)υποδηλώνει την πιθανότητα του Β.

Παρατηρήστε ότι χρειαζόμαστε P(B) > 0γιατί δεν έχει νόημα να μιλάμε για την πιθανότητα του Α δεδομένου Β εάν η εμφάνιση του Β δεν είναι δυνατή.

Μπορούμε επίσης να υπολογίσουμε την πιθανότητα ενός συμβάντος Α, δεδομένης της εμφάνισης πολλαπλών συμβάντων B1, B2, ..., Bn:

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

Υπάρχει ένας άλλος τρόπος υπολογισμού ανιχνευτών υπό όρους. Αυτός ο τρόπος είναι το λεγόμενο Θεώρημα του Bayes.

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) 

Παρατηρήστε ότι υπολογίζουμε την πιθανότητα του συμβάντος Α δεδομένου του συμβάντος Β, αναστρέφοντας τη σειρά εμφάνισης των συμβάντων.

Τώρα υποθέτουμε ότι το συμβάν Α έχει συμβεί και θέλουμε να υπολογίσουμε την πιθανότητα του συμβάντος Β (ή συμβάντων Β1, Β2, ..., Bn στο δεύτερο και πιο γενικό παράδειγμα).

Ένα σημαντικό γεγονός που μπορεί να εξαχθεί από αυτό το Θεώρημα είναι ο τύπος υπολογισμού P(B1,B2,...,Bn,A). Αυτό ονομάζεται κανόνας αλυσίδας για πιθανότητες.

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) 

Αυτή είναι μια άσχημη φόρμουλα, έτσι δεν είναι; Αλλά κάτω από ορισμένες συνθήκες μπορούμε να κάνουμε μια λύση και να το αποφύγουμε.

Ας μιλήσουμε για την τελευταία ιδέα που πρέπει να γνωρίζουμε για να κατανοήσουμε τους αλγόριθμους.

Ανεξαρτησία

Η τελευταία ιδέα για την οποία θα μιλήσουμε είναι η ανεξαρτησία. Λέμε ότι τα γεγονότα Α και Β είναι ανεξάρτητα εάν

P(A|B) = P(A) 

Αυτό σημαίνει ότι η πιθανότητα του συμβάντος Α δεν επηρεάζεται από την εμφάνιση του συμβάντος Β. Άμεση συνέπεια είναι αυτό P(A,B) = P(A)P(B).

Στα απλά αγγλικά, αυτό σημαίνει ότι η πιθανότητα εμφάνισης αμφότερων των Α και Β ταυτόχρονα είναι ίδια με το προϊόν των ανιχνευτών των συμβάντων Α και Β που συμβαίνουν ξεχωριστά.

Εάν τα Α και Β είναι ανεξάρτητα, υποστηρίζει επίσης ότι:

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

Τώρα είμαστε έτοιμοι να μιλήσουμε για τους Naive Bayes Classifiers!

Naive Bayes Classifiers

Ας υποθέσουμε ότι έχουμε ένα διάνυσμα X των χαρακτηριστικών n και θέλουμε να προσδιορίσουμε την κλάση αυτού του διανύσματος από ένα σύνολο k τάξεων y1, y2, ..., yk . Για παράδειγμα, αν θέλουμε να καθορίσουμε αν θα βρέξει σήμερα ή όχι.

Έχουμε δύο πιθανές τάξεις ( k = 2 ): βροχή , όχι βροχή και το μήκος του διανύσματος των χαρακτηριστικών μπορεί να είναι 3 ( n = 3 ).

Το πρώτο χαρακτηριστικό μπορεί να είναι αν είναι θολό ή ηλιόλουστο, το δεύτερο χαρακτηριστικό μπορεί να είναι αν η υγρασία είναι υψηλή ή χαμηλή, και το τρίτο χαρακτηριστικό θα είναι αν η θερμοκρασία είναι υψηλή, μεσαία ή χαμηλή.

Έτσι, αυτά θα μπορούσαν να είναι πιθανά διανύσματα χαρακτηριστικών.

Our task is to determine whether it'll rain or not, given the weather features.

After learning about conditional probabilities, it seems natural to approach the problem by trying to calculate the prob of raining given the features:

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

If R > NR we answer that it'll rain, otherwise we say it won't.

In general, if we have k classes y1, y2, ..., yk, and a vector of n features X = , we want to find the class yi that maximizes

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

Notice that the denominator is constant and it does not depend on the class yi. So, we can ignore it and just focus on the numerator.

In a previous section, we saw how to calculate P(X1, X2,..., Xn, yi) by decomposing it in a product of conditional probabilities (the ugly formula):

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

Assuming all the features Xi are independent and using Bayes's Theorem, we can calculate the conditional probability as follows:

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) 

And we just need to focus on the numerator.

By finding the class yi that maximizes the previous expression, we are classifying the input vector. But, how can we get all those probabilities?

How to calculate the probabilities

When solving these kind of problems we need to have a set of previously classified examples.

For instance, in the problem of guessing whether it'll rain or not, we need to have several examples of feature vectors and their classifications that they would be obtained from past weather forecasts.

So, we would have something like this:

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

Suppose we need to classify a new vector . We need to calculate:

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) 

We get the previous expression by applying the definition of conditional probability and the chain rule. Remember we only need to focus on the numerator so we can drop the denominator.

We also need to calculate the prob for NotRain, but we can do this in a similar way.

We can find P(Rain) = # Rain/Total. That means counting the entries in the dataset that are classified with Rain and dividing that number by the size of the dataset.

To calculate P(Cloudy | H_Low, T_Low, Rain) we need to count all the entries that have the features H_Low, T_Low and Cloudy. Those entries also need to be classified as Rain. Then, that number is divided by the total amount of data. We calculate the rest of the factors of the formula in a similar fashion.

Making those computations for every possible class is very expensive and slow. So we need to make assumptions about the problem that simplify the calculations.

Naive Bayes Classifiers assume that all the features are independent from each other. So we can rewrite our formula applying Bayes's Theorem and assuming independence between every pair of features:

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) 

Now we calculate P(Cloudy | Rain) counting the number of entries that are classified as Rain and were 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.

Σε αυτό το άρθρο διαβάζετε σχετικά με τις πιθανότητες υπό όρους, την ανεξαρτησία και το θεώρημα του Bayes. Αυτές είναι οι μαθηματικές έννοιες πίσω από τους ταξινομητές Naive Bayes.

Μετά από αυτό, είδαμε μια απλή εφαρμογή ενός NBC και λύσαμε το πρόβλημα του να προσδιορίσουμε εάν ένας επιβάτης του Τιτανικού επέζησε του ατυχήματος.

Ελπίζω να βρείτε αυτό το άρθρο χρήσιμο. Μπορείτε να διαβάσετε σχετικά με θέματα που σχετίζονται με την Επιστήμη των Υπολογιστών στο προσωπικό μου blog και ακολουθώντας με στο Twitter.