Как работят наивните класификатори на Bayes - с примери за Python Code

Наивните класификатори на Bayes (NBC) са прости, но мощни алгоритми за машинно обучение. Те се основават на условна вероятност и теоремата на Байес.

В този пост обяснявам „трика“ зад NBC и ще ви дам пример, който можем да използваме за решаване на проблем с класификацията.

В следващите раздели ще говоря за математиката зад NBC. Чувствайте се свободни да пропуснете тези раздели и да преминете към частта за внедряване, ако не се интересувате от математиката.

В раздела за внедряване ще ви покажа прост NBC алгоритъм. След това ще го използваме за решаване на проблем с класификацията. Задачата ще бъде да се определи дали определен пътник на Титаник е оцелял при инцидента или не.

Условна вероятност

Преди да говорим за самия алгоритъм, нека поговорим за простата математика зад него. Трябва да разберем какво е условна вероятност и как можем да използваме теоремата на Байес, за да я изчислим.

Помислете за справедлива матрица с шест страни. Каква е вероятността да получите шестица, когато валяте матрицата? Това е лесно, това е 1/6. Имаме шест възможни и еднакво вероятни резултати, но се интересуваме само от един от тях. И така, 1/6 е.

Но какво ще стане, ако ви кажа, че вече съм хвърлил матрицата и резултатът е четно число? Каква е вероятността да имаме шестица сега?

Този път възможните резултати са само три, защото на матрицата има само три четни числа. Все още се интересуваме само от един от тези резултати, така че сега вероятността е по-голяма: 1/3. Каква е разликата между двата случая?

В първия случай нямахме предварителна информация за резултата. По този начин трябваше да разгледаме всеки един възможен резултат.

Във втория случай ни беше казано, че резултатът е четно число, така че бихме могли да намалим пространството на възможните резултати до трите четни числа, които се появяват при обикновена шестстранна матрица.

Като цяло, когато се изчислява вероятността за събитие А, като се има предвид появата на друго събитие B, ние казваме, че изчисляваме условната вероятност за A дадено B или просто вероятността за A дадено B. Ние го обозначаваме P(A|B).

Например, вероятността за получаване на шест предвид, че броят ние имаме дори е: P(Six|Even) = 1/3. Тук ние, означени с шест събитие за получаване на шестица и с четно събитие за получаване на четно число.

Но как да изчислим условните вероятности? Има ли формула?

Как да изчислим условни проблеми и теоремата на Байес

Сега ще ви дам няколко формули за изчисляване на условни проблеми. Обещавам, че няма да са трудни и са важни, ако искате да разберете прозренията на алгоритмите за машинно обучение, за които ще говорим по-късно.

Вероятността за събитие A при възникване на друго събитие B може да бъде изчислена по следния начин:

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

Където P(A,B)означава вероятността едновременно да се появят както A, така и B, и P(B)означава вероятността за B.

Забележете, че имаме нужда, P(B) > 0защото няма смисъл да говорим за вероятността за A даден B, ако появата на B не е възможна.

Също така можем да изчислим вероятността за събитие A, като се има предвид появата на множество събития B1, B2, ..., Bn:

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

Има и друг начин за изчисляване на условни проблеми. По този начин е така наречената теорема на Байес.

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) 

Забележете, че ние изчисляваме вероятността от събитие A при събитие B, като обръщаме реда на възникване на събитията.

Сега предполагаме, че събитието А е настъпило и искаме да изчислим проблема на събитие Б (или събития В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) 

Това е грозна формула, нали? Но при някои условия можем да направим заобиколно решение и да го избегнем.

Нека да поговорим за последната концепция, която трябва да знаем, за да разберем алгоритмите.

Независимост

Последната концепция, за която ще говорим, е независимостта. Казваме, че събитията A и B са независими, ако

P(A|B) = P(A) 

Това означава, че проблемът на събитие А не се влияе от настъпването на събитие Б. Пряко следствие е това P(A,B) = P(A)P(B).

На обикновен английски това означава, че изпитанието на появата едновременно на A и B е равно на произведението на пробите на събития A и B, случващи се поотделно.

Ако A и B са независими, той също така счита, че:

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

Сега сме готови да поговорим за класификаторите на Naive Bayes!

Класификатори на наивните Байес

Да предположим, че имаме вектор X от n характеристики и искаме да определим класа на този вектор от набор от k класове y1, y2, ..., yk . Например, ако искаме да определим дали ще вали днес или не.

Имаме два възможни класа ( k = 2 ): дъжд , не дъжд и дължината на вектора на характеристиките може да бъде 3 ( n = 3 ).

Първата характеристика може да бъде дали е облачно или слънчево, втората характеристика може да бъде дали влажността е висока или ниска, а третата характеристика би била дали температурата е висока, средна или ниска.

Така че, това може да са възможни вектори на функции.

Нашата задача е да определим дали ще вали или не, предвид характеристиките на времето.

След като научихме за условни вероятности, изглежда естествено да подходим към проблема, като се опитаме да изчислим вероятността от дъжд, като се имат предвид характеристиките:

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

Ако R > NRотговорим, че ще вали, в противен случай казваме, че няма.

Като цяло, ако имаме k класове y1, y2, ..., yk и вектор от n функции X = , ние искаме да намерим класа yi, който максимизира

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

Забележете, че знаменателят е постоянен и не зависи от класа yi . Така че, можем да го игнорираме и просто да се съсредоточим върху числителя.

В предишен раздел видяхме как да изчислим, P(X1, X2,..., Xn, yi)като го разложим в продукт на условни вероятности (грозната формула):

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

Ако приемем, че всички характеристики Xi са независими и използвайки теоремата на Байес, можем да изчислим условната вероятност, както следва:

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) 

И просто трябва да се съсредоточим върху числителя.

Като намираме класа yi, който максимизира предишния израз, ние класифицираме входния вектор. Но как можем да получим всички тези вероятности?

Как да изчислим вероятностите

При решаването на този вид проблеми трябва да имаме набор от предварително класифицирани примери.

Например, при проблема с отгатването дали ще вали или не, трябва да имаме няколко примера за вектори на характеристики и техните класификации, които биха били получени от минали прогнози за времето.

И така, щяхме да имаме нещо подобно:

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

Да предположим, че трябва да класифицираме нов вектор . Трябва да изчислим:

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) 

Получаваме предишния израз, като прилагаме определението за условна вероятност и правилото на веригата. Не забравяйте, че трябва да се съсредоточим само върху числителя, за да можем да пуснем знаменателя.

Ние също трябва да изчислим вероятността за NotRain, но можем да направим това по подобен начин.

Можем да намерим P(Rain) = # Rain/Total. Това означава преброяване на записите в набора от данни, които са класифицирани с Rain и разделяне на това число на размера на набора от данни.

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.

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.