Cómo funcionan los clasificadores ingenuos de Bayes: con ejemplos de código de Python

Los clasificadores Naive Bayes (NBC) son algoritmos de aprendizaje automático simples pero potentes. Se basan en la probabilidad condicional y el teorema de Bayes.

En esta publicación, explico "el truco" detrás de NBC y les daré un ejemplo que podemos usar para resolver un problema de clasificación.

En las próximas secciones, hablaré sobre las matemáticas detrás de NBC. No dude en omitir esas secciones y pasar a la parte de implementación si no está interesado en las matemáticas.

En la sección de implementación, le mostraré un algoritmo NBC simple. Luego lo usaremos para resolver un problema de clasificación. La tarea será determinar si cierto pasajero del Titanic sobrevivió al accidente o no.

La probabilidad condicional

Antes de hablar sobre el algoritmo en sí, hablemos de las matemáticas simples detrás de él. Necesitamos entender qué es la probabilidad condicional y cómo podemos usar el teorema de Bayes para calcularla.

Piense en un dado justo con seis lados. ¿Cuál es la probabilidad de obtener un seis al lanzar el dado? Eso es fácil, es 1/6. Tenemos seis resultados posibles e igualmente probables, pero solo nos interesa uno de ellos. Entonces, 1/6 lo es.

Pero, ¿qué pasa si te digo que ya lancé el dado y el resultado es un número par? ¿Cuál es la probabilidad de que tengamos un seis ahora?

Esta vez, los posibles resultados son solo tres porque solo hay tres números pares en el dado. Todavía estamos interesados ​​en solo uno de esos resultados, por lo que ahora la probabilidad es mayor: 1/3. ¿Cuál es la diferencia entre ambos casos?

En el primer caso, no teníamos información previa sobre el resultado. Por lo tanto, teníamos que considerar todos los resultados posibles.

En el segundo caso, nos dijeron que el resultado era un número par, por lo que podíamos reducir el espacio de posibles resultados a solo los tres números pares que aparecen en un dado normal de seis caras.

En general, al calcular la probabilidad de un evento A, dada la ocurrencia de otro evento B, decimos que estamos calculando la probabilidad condicional de A dado B, o simplemente la probabilidad de A dado B. Lo denotamos P(A|B).

Por ejemplo, la probabilidad de obtener un máximo de seis, dado que el número que tenemos es par: P(Six|Even) = 1/3. Aquí, denotamos con Seis el evento de obtener un seis y con Even el evento de obtener un número par.

Pero, ¿cómo calculamos las probabilidades condicionales? ¿Existe una fórmula?

Cómo calcular problemas condicionales y el teorema de Bayes

Ahora, te daré un par de fórmulas para calcular problemas condicionales. Prometo que no serán difíciles y son importantes si desea comprender las ideas de los algoritmos de aprendizaje automático de los que hablaremos más adelante.

La probabilidad de un evento A dada la ocurrencia de otro evento B se puede calcular de la siguiente manera:

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

Donde P(A,B)denota la probabilidad de que A y B ocurran al mismo tiempo, y P(B)denota la probabilidad de que B.

Nótese que necesitamos P(B) > 0porque no tiene sentido hablar de la probabilidad de A dado B si la ocurrencia de B no es posible.

También podemos calcular la probabilidad de un evento A, dada la ocurrencia de múltiples eventos B1, B2, ..., Bn:

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

Hay otra forma de calcular problemas condicionales. De esta manera es el llamado Teorema de 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) 

Observe que estamos calculando la probabilidad del evento A dado el evento B, invirtiendo el orden de ocurrencia de los eventos.

Ahora suponemos que el evento A ha ocurrido y queremos calcular el problema del evento B (o eventos B1, B2, ..., Bn en el segundo y más general ejemplo).

Un dato importante que se puede derivar de este Teorema es la fórmula a calcular P(B1,B2,...,Bn,A). Eso se llama la regla de la cadena para las probabilidades.

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) 

Esa es una fórmula fea, ¿no? Pero bajo algunas condiciones podemos hacer una solución y evitarlo.

Hablemos del último concepto que necesitamos saber para entender los algoritmos.

Independencia

El último concepto del que vamos a hablar es el de independencia. Decimos que los eventos A y B son independientes si

P(A|B) = P(A) 

Eso significa que el problema del evento A no se ve afectado por la ocurrencia del evento B. Una consecuencia directa es eso P(A,B) = P(A)P(B).

En términos sencillos, esto significa que el problema de la ocurrencia de A y B al mismo tiempo es igual al producto de los problemas de los eventos A y B que ocurren por separado.

Si A y B son independientes, también se sostiene que:

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

¡Ahora estamos listos para hablar sobre los clasificadores Naive Bayes!

Clasificadores Bayes ingenuos

Supongamos que tenemos un vector X de n características y queremos determinar la clase de ese vector a partir de un conjunto de k clases y1, y2, ..., yk . Por ejemplo, si queremos determinar si lloverá hoy o no.

Tenemos dos clases posibles ( k = 2 ): lluvia , no lluvia , y la longitud del vector de características podría ser 3 ( n = 3 ).

La primera característica podría ser si está nublado o soleado, la segunda característica podría ser si la humedad es alta o baja, y la tercera característica sería si la temperatura es alta, media o baja.

Entonces, estos podrían ser posibles vectores de características.

Nuestra tarea es determinar si lloverá o no, dadas las características meteorológicas.

Después de conocer las probabilidades condicionales, parece natural abordar el problema tratando de calcular el problema de la lluvia dadas las características:

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

Si R > NRrespondemos que va a llover, de lo contrario, decimos que no.

En general, si tenemos k clases y1, y2, ..., yk , y un vector de n características X = , queremos encontrar la clase yi que maximiza

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

Observe que el denominador es constante y no depende de la clase yi . Entonces, podemos ignorarlo y enfocarnos en el numerador.

En una sección anterior, vimos cómo calcular P(X1, X2,..., Xn, yi)descomponiéndolo en un producto de probabilidades condicionales (la fórmula fea):

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

Suponiendo que todas las características Xi son independientes y usando el teorema de Bayes, podemos calcular la probabilidad condicional de la siguiente manera:

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) 

Y solo tenemos que centrarnos en el numerador.

Al encontrar la clase yi que maximiza la expresión anterior, estamos clasificando el vector de entrada. Pero, ¿cómo podemos obtener todas esas probabilidades?

Cómo calcular las probabilidades

Al resolver este tipo de problemas necesitamos tener un conjunto de ejemplos previamente clasificados.

Por ejemplo, en el problema de adivinar si lloverá o no, necesitamos tener varios ejemplos de vectores de características y sus clasificaciones que se obtendrían de pronósticos meteorológicos anteriores.

Entonces, tendríamos algo como esto:

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

Supongamos que necesitamos clasificar un nuevo vector . Necesitamos calcular:

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) 

Obtenemos la expresión anterior aplicando la definición de probabilidad condicional y la regla de la cadena. Recuerda que solo necesitamos enfocarnos en el numerador para que podamos eliminar el denominador.

También necesitamos calcular el problema NotRain, pero podemos hacerlo de manera similar.

Podemos encontrar P(Rain) = # Rain/Total. Eso significa contar las entradas en el conjunto de datos que se clasifican con Rain y dividir ese número por el tamaño del conjunto de datos.

Para calcular P(Cloudy | H_Low, T_Low, Rain), necesitamos contar todas las entradas que tienen las características H_Low, T_Low y Cloudy . Esas entradas también deben clasificarse como Rain. Luego, ese número se divide por la cantidad total de datos. Calculamos el resto de factores de la fórmula de forma similar.

Hacer esos cálculos para todas las clases posibles es muy costoso y lento. Por tanto, necesitamos hacer suposiciones sobre el problema que simplifiquen los cálculos.

Los clasificadores ingenuos de Bayes asumen que todas las características son independientes entre sí. Entonces podemos reescribir nuestra fórmula aplicando el teorema de Bayes y asumiendo independencia entre cada par de características:

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) 

Ahora calculamos P(Cloudy | Rain)contando el número de entradas que se clasifican como Rainy fueron Cloudy.

El algoritmo se llama Naive debido a esta suposición de independencia. Hay dependencias entre las funciones la mayor parte del tiempo. No podemos decir que en la vida real no haya dependencia entre la humedad y la temperatura, por ejemplo. Los clasificadores Naive Bayes también se llaman Independence Bayes o Simple Bayes.

La fórmula general sería:

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

Recuerda que puedes deshacerte del denominador. Solo calculamos el numerador y respondemos la clase que lo maximiza.

Ahora, implementemos nuestro NBC y usémoslo en un problema.

¡Codifiquemos!

Les mostraré una implementación de un NBC simple y luego lo veremos en la práctica.

El problema que vamos a resolver es determinar si un pasajero del Titanic sobrevivió o no, dadas algunas características como su género y su edad.

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.