Cách hoạt động của bộ phân loại Naive Bayes - với ví dụ về mã Python

Naive Bayes Classifier (NBC) là thuật toán Học máy đơn giản nhưng mạnh mẽ. Chúng dựa trên xác suất có điều kiện và Định lý Bayes.

Trong bài đăng này, tôi giải thích "thủ thuật" đằng sau NBC và tôi sẽ cung cấp cho bạn một ví dụ mà chúng tôi có thể sử dụng để giải quyết vấn đề phân loại.

Trong các phần tiếp theo, tôi sẽ nói về toán học đằng sau NBC. Vui lòng bỏ qua những phần đó và chuyển sang phần thực hiện nếu bạn không quan tâm đến toán học.

Trong phần triển khai, tôi sẽ chỉ cho bạn một thuật toán NBC đơn giản. Sau đó, chúng tôi sẽ sử dụng nó để giải quyết vấn đề phân loại. Nhiệm vụ sẽ là xác định xem một hành khách nào đó trên tàu Titanic có sống sót sau vụ tai nạn hay không.

Xác suất có điều kiện

Trước khi nói về bản thân thuật toán, hãy nói về phép toán đơn giản đằng sau nó. Chúng ta cần hiểu xác suất có điều kiện là gì và làm thế nào chúng ta có thể sử dụng Định lý Bayes để tính toán nó.

Hãy nghĩ về một cái chết công bằng với sáu mặt. Xác suất nhận được sáu khi lăn súc sắc là bao nhiêu? Thật dễ dàng, đó là 1/6. Chúng tôi có sáu kết quả có thể xảy ra và có khả năng như nhau nhưng chúng tôi chỉ quan tâm đến một trong số chúng. Vì vậy, 1/6 nó là.

Nhưng điều gì sẽ xảy ra nếu tôi nói với bạn rằng tôi đã lăn con lăn và kết quả là một số chẵn? Xác suất mà chúng tôi có sáu bây giờ là bao nhiêu?

Lần này, các kết quả có thể xảy ra chỉ là ba vì chỉ có ba số chẵn trên con súc sắc. Chúng tôi vẫn quan tâm đến một trong những kết quả đó, vì vậy bây giờ xác suất lớn hơn: 1/3. Sự khác biệt giữa cả hai trường hợp là gì?

Trong trường hợp đầu tiên, chúng tôi không có thông tin trước về kết quả. Vì vậy, chúng tôi cần phải xem xét mọi kết quả có thể có.

Trong trường hợp thứ hai, chúng tôi được thông báo rằng kết quả là một số chẵn, vì vậy chúng tôi có thể giảm không gian của các kết quả có thể xảy ra chỉ còn ba số chẵn xuất hiện trong một con xúc xắc sáu mặt thông thường.

Nói chung, khi tính xác suất của một sự kiện A, với sự xuất hiện của một sự kiện B khác, chúng ta nói rằng chúng ta đang tính xác suất có điều kiện của A cho B, hoặc chỉ xác suất của A cho B. Chúng ta ký hiệu nó P(A|B).

Ví dụ, xác suất nhận được một Sáu cho rằng số lượng chúng tôi đã có thậm chí còn: P(Six|Even) = 1/3. Ở đây chúng tôi, được biểu thị với Six sự kiện nhận được sáu và với sự kiện Even nhận được một số chẵn.

Nhưng, làm thế nào để chúng ta tính toán xác suất có điều kiện? Có một công thức?

Cách tính toán probs có điều kiện và Định lý Bayes

Bây giờ, tôi sẽ cung cấp cho bạn một vài công thức để tính toán các probs có điều kiện. Tôi hứa rằng chúng sẽ không khó và chúng rất quan trọng nếu bạn muốn hiểu những thông tin chi tiết về các thuật toán Học máy mà chúng ta sẽ đề cập ở phần sau.

Xác suất của một sự kiện A cho trước sự xuất hiện của một sự kiện B khác có thể được tính như sau:

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

Trong đó P(A,B)biểu thị xác suất của cả A và B xảy ra đồng thời và P(B)biểu thị xác suất của B.

Lưu ý rằng chúng ta cần P(B) > 0bởi vì không có ý nghĩa gì khi nói về xác suất của A cho B nếu sự xuất hiện của B là không thể.

Chúng ta cũng có thể tính xác suất của một sự kiện A, với sự xuất hiện của nhiều sự kiện B1, B2, ..., Bn:

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

Có một cách khác để tính toán probs có điều kiện. Cách này được gọi là Định lý 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) 

Lưu ý rằng chúng tôi đang tính xác suất của sự kiện A với sự kiện B, bằng cách đảo ngược thứ tự xuất hiện của các sự kiện.

Bây giờ chúng ta giả sử sự kiện A đã xảy ra và chúng ta muốn tính xác suất của sự kiện B (hoặc các sự kiện B1, B2, ..., Bn trong ví dụ thứ hai và tổng quát hơn).

Một thực tế quan trọng có thể rút ra từ Định lý này là công thức để tính toán P(B1,B2,...,Bn,A). Đó được gọi là quy tắc chuỗi cho các xác suất.

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) 

Đó là một công thức xấu xí, phải không? Nhưng trong một số điều kiện, chúng ta có thể giải quyết và tránh nó.

Hãy nói về khái niệm cuối cùng chúng ta cần biết để hiểu các thuật toán.

Sự độc lập

Khái niệm cuối cùng mà chúng ta sẽ nói đến là sự độc lập. Chúng tôi nói rằng các sự kiện A và B là độc lập nếu

P(A|B) = P(A) 

Điều đó có nghĩa là xác suất của sự kiện A không bị ảnh hưởng bởi sự xuất hiện của sự kiện B. Một hệ quả trực tiếp là điều đó P(A,B) = P(A)P(B).

Trong tiếng Anh đơn giản, điều này có nghĩa là xác suất xảy ra cả A và B cùng một lúc bằng tích của các mệnh đề của các sự kiện A và B xảy ra riêng biệt.

Nếu A và B độc lập, nó cũng cho rằng:

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

Bây giờ chúng ta đã sẵn sàng để nói về Bộ phân loại Naive Bayes!

Bộ phân loại Naive Bayes

Giả sử chúng ta có một vectơ X gồm n đặc trưng và chúng ta muốn xác định hạng của vectơ đó từ tập k lớp y1, y2, ..., yk . Ví dụ, nếu chúng ta muốn xác định xem hôm nay trời có mưa hay không.

Chúng ta có hai lớp khả dĩ ( k = 2 ): mưa , không mưa và độ dài của vectơ các đối tượng có thể là 3 ( n = 3 ).

Tính năng đầu tiên có thể là cho dù trời nhiều mây hay nắng, tính năng thứ hai có thể là độ ẩm cao hay thấp và tính năng thứ ba là nhiệt độ cao, trung bình hay thấp.

Vì vậy, đây có thể là các vectơ đặc trưng khả thi.

Nhiệm vụ của chúng tôi là xác định xem trời có mưa hay không, dựa trên các đặc điểm thời tiết.

Sau khi tìm hiểu về các xác suất có điều kiện, có vẻ tự nhiên khi tiếp cận vấn đề bằng cách cố gắng tính xác suất mưa với các tính năng:

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

Nếu R > NRchúng tôi trả lời rằng trời sẽ mưa, nếu không thì chúng tôi nói sẽ không.

Nói chung, nếu chúng ta có k lớp y1, y2, ..., yk và một vectơ của n đặc điểm X = , chúng ta muốn tìm lớp yi tối đa hóa

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

Chú ý rằng mẫu số là không đổi và nó không phụ thuộc vào hạng yi . Vì vậy, chúng ta có thể bỏ qua nó và chỉ tập trung vào tử số.

Trong phần trước, chúng ta đã biết cách tính toán P(X1, X2,..., Xn, yi)bằng cách phân tích nó trong tích các xác suất có điều kiện (công thức xấu xí):

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

Giả sử tất cả các đặc trưng Xi là độc lập và sử dụng Định lý Bayes, chúng ta có thể tính xác suất có điều kiện như sau:

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) 

Và chúng ta chỉ cần tập trung vào tử số.

Bằng cách tìm lớp yi tối đa hóa biểu thức trước đó, chúng tôi đang phân loại vectơ đầu vào. Nhưng, làm thế nào chúng ta có thể nhận được tất cả những xác suất đó?

Cách tính xác suất

Khi giải những bài toán này, chúng ta cần có một tập hợp các ví dụ đã được phân loại trước đó.

Ví dụ, trong bài toán đoán xem trời có mưa hay không, chúng ta cần có một số ví dụ về các vectơ đặc trưng và phân loại của chúng mà chúng sẽ thu được từ các dự báo thời tiết trước đây.

Vì vậy, chúng tôi sẽ có một cái gì đó như thế này:

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

Giả sử chúng ta cần phân loại một vector mới . Chúng ta cần tính toán:

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) 

Chúng ta có được biểu thức trước bằng cách áp dụng định nghĩa của xác suất có điều kiện và quy tắc chuỗi. Hãy nhớ rằng chúng ta chỉ cần tập trung vào tử số để có thể bỏ mẫu số.

Chúng ta cũng cần tính toán xác suất NotRain, nhưng chúng ta có thể làm điều này theo cách tương tự.

Chúng tôi có thể tìm thấy P(Rain) = # Rain/Total. Điều đó có nghĩa là đếm các mục nhập trong tập dữ liệu được phân loại với Rain và chia số đó cho kích thước của tập dữ liệu.

Để tính toán, P(Cloudy | H_Low, T_Low, Rain)chúng ta cần đếm tất cả các mục nhập có các tính năng H_Low, T_LowCloudy . Những mục này cũng cần được phân loại như Rain. Sau đó, số đó được chia cho tổng lượng dữ liệu. Chúng tôi tính toán các yếu tố còn lại của công thức theo cách tương tự.

Việc thực hiện các phép tính đó cho mọi lớp có thể rất tốn kém và chậm. Vì vậy chúng ta cần đưa ra các giả thiết về bài toán đơn giản hóa các phép tính.

Naive Bayes Classifier giả định rằng tất cả các tính năng là độc lập với nhau. Vì vậy, chúng ta có thể viết lại công thức của mình bằng cách áp dụng Định lý Bayes và giả định sự độc lập giữa mọi cặp đặc trưng:

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) 

Bây giờ chúng tôi tính toán P(Cloudy | Rain)đếm số mục nhập được phân loại là Rainvà đã từng 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.

Trong bài viết này, bạn đọc về xác suất có điều kiện, tính độc lập và Định lý Bayes. Đó là những khái niệm Toán học đằng sau Bộ phân loại Naive Bayes.

Sau đó, chúng tôi đã thấy một NBC triển khai đơn giản và giải quyết vấn đề xác định liệu một hành khách trên tàu Titanic có sống sót sau vụ tai nạn hay không.

Tôi hy vọng bạn thấy bài viết này hữu ích. Bạn có thể đọc về các chủ đề liên quan đến Khoa học Máy tính trong blog cá nhân của tôi và theo dõi tôi trên Twitter.