Clasificación de Texto: Naïve Bayes

En mi post anterior introduje el tópico de la clasificación de textos y mencioné que había métodos de clasificación automática. Repasemos qué era la clasificación de textos.
   Imaginen que tengo una critica cinematográfica y quiero saber si es buena o mala. O tengo una novela y quiero saber si es de ciencia-ficción o de misterio. O quizás una publicación científica y quiero saber si es sobre medicina o ingeniería. Estos son todos problemas de clasificación de texto.

   Un enfoque posible para la resolución de este problema es encararlo por el lado estadístico, entonces diría que tengo n documentos, y x clases posibles, mi pregunta pasa a ser entonces: ¿cuál es la probabilidad de que el documento d pertenezca a la clase c?

   Parafraseado como probabilidad condicional: dado el documento d, ¿cuál es la probabilidad de que pertenezca a c?  = P(c | d)
    Y por el teorema de Bayes puedo  plantear lo siguiente:

P(c | d) = P(d | c) P(c)
                     P(d)

Y con un poco de ingenio puedo resolver este calculo.  :-)



Antes de continuar me gustaría hacer un pequeño repaso de la regla de Bayes y explicarla mejor con un ejemplo de Probabilidad y Estadística:

La regla de Bayes es un caso especial de probabilidad condicional, se aplica cuando se desea calcular la probabilidad condicional de un evento A dado otro evento B ya ocurrido.

Ejemplo: Tengo 23 naipes distribuidos de la siguiente forma: 2 Oros, 3 Bastos, 9 Copas y 9 Espadas. A su vez, sé que tengo los 4 reyes entre ellos.

  ¿Cúal es la probabilidad de que habiendo sacado un Basto este sea un rey?

  evento A: Sacar un rey
  evento B: Sacar un Basto

   P(A | B) = P(B | A) P(A)
                           P(B)

P(A) = 4/23, P(B)= 3/23  y P(B | A) = 1/4 =>  P (A | B ) =  ((1/4) * (4/23))/ (3/23) = 1/3

Este ejemplo es obvio y a simple vista nos damos cuenta del resultado sin tener que hacer ninguna cuenta pero sirve para repasar la regla de Bayes.

Naïve Bayes:

Para este método un documento es una bolsa de palabras, no le importa el orden ni aspectos estéticos. Supongan el siguiente documento:

Una comedia entretenida que nos muestra la pasión por la música, la amistad, el amor y los conflictos en las relaciones humanas. Un guión sin desperdicio, una dirección con profesionalismo y actuaciones memorables. Muy recomendable para ver en familia.

Podría tomar todas las palabras o bien solo algunas que me interesen.

||

\/

xxx comedia entretenida xxx xxx xxxxxxx xx xxxxx xxx xx xxxx, xx xxxxx, xx xxxx x  xxx amor xx xxx xxxxxxxx xxxxxxxx xx xxxx xxx xxxxxxxxx, xxxx xxxxxxx xxx  profesionalismo x xxxxxxxxxx memorables xxxx recomendable xxxx xxx xx xxxxxxx

                              Luego cuento las veces que aparecen esas palabras:

||

\/ 

amor	1
recomendable	2
comercial	2
memorables	1
...	...

Así es como este método representa a un documento: como un vector de palabras, indicando la cantidad de veces que estas aparecen.

Entonces, suponiendo que tengo varias clases posibles: ¿Cuál es la probabilidad que tiene un documento de pertenecer a una clase c dada?

cmap =  argmax P(c | d) para c ∈ C, (el conjunto de todas las clases).

cmap significa la clase más probable y "argmax" indica que esta será la que devuelva
         el mayor  valor de todos las P (c|d) calculadas.

por Bayes:   cmap =  argmax P(d | c) P(c)  , c ∈ C
                                                  P(d)

como P(d) es constante, lo podemos eliminar de la ecuación:

 cmap =  argmax P(d | c) P(c)  , c ∈ C

Ahora bien, ¿qué es P(c) y qué es P(d|c)?

P(c) es la probabilidad que tiene la clase de aparecer en una cantidad dada de documentos.

P(d|c) es la probabilidad de que dada una clase c, d sea un documento de ella. Esto es un poco más difícil de identificar, así que para poder calcularlo vamos a representar al documento como una serie de características: x1,x2,x3,....xn: estas características como adelantamos van a estar representadas por las palabras que aparecen en el documento. Vamos a asumir dos supuestos muy importantes:

• que no importa el orden de las palabras
• que las probabilidades de cada característica dada una clase c: P(x i|c j) son independientes entre sí

Ambos supuestos son falsos, sin embargo nos permiten simplificar mucho los cálculos y obtener igualmente resultados muy buenos.

Ahora tenemos que P(d|c) = P(x1,x2,x3,....xn | c) y

P(x1,x2,x3,....xn | c) = P(x1|c) * P(x2|c) *  P(x3|c) * ....* P(xn | c)                (* multiplicación)

Entonces P(d|c) es la multiplicación de cada una de las probabilidades que tiene cada palabra de pertenecer a la clase c dada y nos queda la siguiente formula:

 cmap =  argmax P(cj) ∏ P(xi | cj)
                  cj ∈ C        i ∈ Posiciones

Algorítmicamente: (para calcular la categoría de un documento)

1. tomo la primera de las clases candidatas
2. recorro el texto palabra por palabra (o solo uso las palabras que me interesan)
3. para cada palabra tomo su probabilidad de pertenecer a la clase anterior (ejemplo: la probabilidad de que la palabra: decepcionante pertenezca a la clase: Buenas) 
4. multiplico las probabilidades de todas las palabras y la probabilidad de la categoría
5. repito para la siguiente categoría
6. escojo la c más alta. 

NOTA: si bien hablo de probabilidad, recordar que se eliminó el denominador de la ecuación de Bayes por lo que no es estrictamente una probabilidad (no está normalizada.)

Bien, si me han seguido hasta acá (eso espero) tendrán en claro como aplicar este algoritmo de clasificación pero no saben aún como obtener los valores: p(c) y p(wi|c).

p(c) = cantidad de documentos de clase c
            cantidad de documentos totales

p(wi|c) = cantidad de veces que aparece wi en documentos en la clase c
                   cantidad de palabras que aparecen en los documentos de la clase c

    Estos valores en verdad no los podemos obtener, porque son valores absolutos, las probabilidades varían cada vez que alguien crea un nuevo documento y si supiésemos de antemano su clase no necesitaríamos este algoritmo.

Lo que vamos a hacer es usar valores parecidos, próximos, los cuales calcularemos usando un conjunto de datos de entrenamiento. Este conjunto de datos consistirá en una serie de documentos similares a los que nos interesan previamente clasificados.
Indicamos con un ^ a los valores similares y llamemos T al conjunto de prueba.


^p(c) = cantidad de documentos de clase c en T
            cantidad de documentos en T

^p(wi|c) = cantidad de veces que aparece wi en documentos de T de la clase c
                 cantidad de palabras que aparecen en los documentos de T de la clase c

                                                                     
Consejo: para optimizar el calculo de ^p(wi|c) se puede crear un solo documento concatenando todos los documentos de una clase c dada, y después simplemente tomamos la frecuencia de wi en dicho documento.

   Hasta acá todo muy bien, pero existe un problema al utilizar estos valores similares en lugar de los verdaderos. Voy a explicar este problema y como solucionarlo en el próximo post.