Како раде наивни Баиесови класификатори - на примерима Питхон кода

Наивни Баиесови класификатори (НБЦ) су једноставни, али моћни алгоритми машинског учења. Заснивају се на условној вероватноћи и Баиесовој теореми.

У овом посту објашњавам „трик“ који стоји иза НБЦ-а и даћу вам пример који можемо користити за решавање проблема класификације.

У следећим одељцима говорићу о математици иза НБЦ-а. Слободно прескочите те одељке и идите на део за примену ако вас математика не занима.

У одељку за примену показаћу вам једноставан НБЦ алгоритам. Тада ћемо га користити за решавање проблема класификације. Задатак ће бити да утврди да ли је одређени путник на Титанику преживео несрећу или није.

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

Пре него што разговарамо о самом алгоритму, хајде да разговарамо о једноставној математици која стоји иза њега. Морамо да разумемо шта је условна вероватноћа и како можемо да користимо Баиесову теорему да бисмо је израчунали.

Размислите о поштеној коцки са шест страна. Колика је вероватноћа да добијете шестицу при ваљању коцкице? То је лако, 1/6 је. Имамо шест могућих и једнако вероватних исхода, али нас занима само један од њих. Дакле, 1/6 је.

Али шта ће се догодити ако вам кажем да сам већ изваљао коцку и исход је паран број? Колика је вероватноћа да смо сада добили шестицу?

Овога пута су могући исходи само три, јер на матрицу постоје само три парна броја. Још увек нас занима само један од тих исхода, па је сада вероватноћа већа: 1/3. Која је разлика између оба случаја?

У првом случају нисмо имали претходне информације о исходу. Стога смо морали да размотримо сваки могући резултат.

У другом случају, речено нам је да је исход паран број, па бисмо могли смањити простор могућих исхода на само три парна броја која се појављују у редовном шестостраном калупу.

Генерално, приликом израчунавања вероватноће догађаја А, с обзиром на појаву другог догађаја Б, кажемо да рачунамо условну вероватноћу А датог Б или само вероватноће А датог Б. Означавамо га P(A|B).

На пример, вероватноћа добијања шест обзиром да је број имамо још: P(Six|Even) = 1/3. Овде смо са Шест означили догађај добијања шестице, а са Евен догађајем добијања парног броја.

Али, како израчунавамо условне вероватноће? Да ли постоји формула?

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

Сад ћу вам дати неколико формула за израчунавање условних проблема. Обећавам да неће бити тешки и важни су ако желите да разумете увиде алгоритама машинског учења о којима ћемо касније разговарати.

Вероватноћа догађаја А с обзиром на појаву другог догађаја Б може се израчунати на следећи начин:

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

Где P(A,B)означава вероватноћу да се А и Б јављају истовремено, а P(B)означава вероватноћу Б.

Приметите да нам је потребно P(B) > 0јер нема смисла говорити о вероватноћи датог Б ако појава Б није могућа.

Такође можемо израчунати вероватноћу догађаја А, с обзиром на појаву више догађаја Б1, Б2, ..., Бн:

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) 

Приметите да израчунавамо вероватноћу догађаја А с обзиром на догађај Б, инвертујући редослед појављивања догађаја.

Сада претпостављамо да се догодио догађај А и желимо да израчунамо проба догађаја Б (или догађаја Б1, Б2, ..., Бн у другом и општијем примеру).

Важна чињеница која се може извести из ове теореме је формула за израчунавање 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) 

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

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

Претпоставимо да имамо вектор Кс од н обележја и желимо да одредимо класу тог вектора из скупа к класа и1, и2, ..., ик . На пример, ако желимо да утврдимо да ли ће данас падати киша или не.

Имамо две могуће класе ( к = 2 ): киша , не киша , а дужина вектора обележја може бити 3 ( н = 3 ).

Прва карактеристика може бити да ли је облачно или сунчано, друга карактеристика може бити висока или ниска влажност, а трећа карактеристика да ли је температура висока, средња или ниска.

Дакле, ово би могли бити могући вектори карактеристика.

Наш задатак је да утврдимо да ли ће киша падати или не, с обзиром на временске карактеристике.

Након сазнања о условним вероватноћама, чини се природним приступити проблему покушавајући израчунати вероватноћу кише с обзиром на особине:

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

Ако R > NRодговоримо да ће киша падати, у супротном кажемо да неће.

Генерално, ако имамо к класа и1, и2, ..., ик и вектор од н карактеристика Кс = , желимо да пронађемо класу ии која максимизира

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

Приметите да је називник константан и да не зависи од класе ии . Дакле, можемо то занемарити и само се усредсредити на бројилац.

У претходном одељку видели смо како израчунати 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) 

Под претпоставком да су све карактеристике Кси независне и користећи Баиесову теорему, можемо израчунати условну вероватноћу на следећи начин:

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) 

И само се морамо усредсредити на бројилац.

Проналажењем класе ии која максимизира претходни израз, класификујемо улазни вектор. Али, како можемо добити све те вероватноће?

Како израчунати вероватноће

При решавању ове врсте проблема морамо имати скуп претходно класификованих примера.

На пример, у проблему погађања да ли ће падати киша или не, морамо да имамо неколико примера вектора карактеристика и њихове класификације које би добили из прошлих временских прогноза.

Дакле, имали бисмо отприлике овако:

...  -> 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. То значи да се преброје уноси у скупу података који су класификовани са Раин и поделити тај број са величином скупа података.

Да би се израчунао P(Cloudy | H_Low, T_Low, Rain)треба да се наброје све ставке које имају карактеристике Х_Лов, Т_Лов и облачно . Те уносе такође треба класификовати као Rain. Затим се тај број дели укупном количином података. На сличан начин израчунавамо и остале факторе формуле.

Израчунавање тих израчуна за сваку могућу класу је врло скупо и споро. Зато морамо да претпоставимо о проблему који поједностављује прорачуне.

Наивни Баиесови класификатори претпостављају да су све карактеристике независне једна од друге. Тако можемо преписати нашу формулу примењујући Баиесову теорему и претпостављајући неовисност између сваког пара обележја:

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) 

Сада израчунавамо P(Cloudy | Rain)бројећи број уноса који су класификовани као Rainи који су били 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.

У овом чланку читате о условним вероватноћама, независности и Баиесовој теореми. То су математички концепти који стоје иза Наивних Баиесових класификатора.

Након тога, видели смо једноставну примену НБЦ-а и решили проблем утврђивања да ли је путник на Титанику преживео несрећу.

Надам се да вам је овај чланак био користан. О темама везаним за рачунарске науке можете читати на мом личном блогу и пратећи ме на Твиттер-у.