Clasificación de Texto: medidas de rendimiento y desempeño

Voy a exponer en esta entrada algunos métodos comunes para evaluar un algoritmo de clasificación de textos.

Hay dos tipos de errores que pueden cometerse, como muchos saben: los falsos positivos (es decir aquellos textos que fueron etiquetados como de una clase dada y no lo son) y los falsos negativos, aquellos textos que no fueron etiquetados como pertenecientes a la clase y en verdad sí pertenecen.

Esta matriz gráfica lo anterior:

	Correcto	No correcto
Seleccionado	verdadero positivo	falso positivo
No seleccionado	verdadero negativo	falso negativo

Están marcados en rojos los casos de error.

Recuperación de información (information retrieval) y búsqueda en la Web: consultas de frases e índices posicionales

Hasta ahora hemos visto como recuperar documentos que contienen una o más palabras pero no como recuperar documentos que contienen una frase armada; si yo quisiera recuperar todos aquellos documentos en donde aparece la frase: "facultad de ingeniería", por ejemplo, lo único que podría hacer es recuperar los documentos que contienen las palabras "facultad", "de" e "ingeniería" ("de" podría obviarse porque es una stop word) y luego revisarlos exhaustivamente para encontrar la frase textual, ya que no me interesan los documentos que dicen cosas como: "Pedro estudió ingeniería en la facultad de Salta", estos no deberían ser devueltos.

Hay dos formas de solucionar este problema.

Recuperación de información (information retrieval) y búsqueda en la Web: consultas sobre Indices invertidos

En el post anterior vimos como crear un índice invertido, ahora voy a explicar como realizar una consulta sobre ese tipo de índice.

Supónganse que queremos obtener todos los documentos en donde aparecen las palabras: "Brutus" y "Cesar"

1. Obtenemos la lista de documentos en donde aparece la palabra "Brutus"
2. Obtenemos la lista de documentos en donde aparece la palabra "Cesar"
3. Realizamos una intersección de ambas listas mediante un algoritmo de merge

Recuperación de información (information retrieval) y búsqueda en la Web: Índices invertidos

Los índices invertidos son la estructura de datos más utilizada en los sistemas de recuperación de información, en particular en aquellos con grandes volúmenes de datos a manejar como los motores de búsqueda; hacen uso eficiente de la idea principal de la matriz de incidencias vista previamente.

Índice invertido:

• Para cada término t, tenemos que guardar todos los documentos que contienen t
• Identificar cada documento por un docId, que es un número incremental

Tendremos dos partes bien definidas: el diccionario y las listas de postings, que son básicamente una serie de listas, una por cada término, donde iremos insertando los docIds de los documentos. 

Recuperación de información (information retrieval) y búsqueda en la Web: Matrices de incidencia

Supongamos que mi colección de documentos no es ni más ni menos que las obras completas de William Shakespeare, y que la información que quiero conseguir es la siguiente:

   Todas las obras de Shakespeare que contengan las palabras: "Brutus" y "Cesar" pero no la palabra "Calpurnia".

    Una forma de solucionar este problema es hacer una búsqueda exhaustiva de todos los documentos, seleccionar primero aquellos que tienen las palabras "Brutus" y "Cesar" y luego eliminar de la lista los que también tienen la palabra "Calpurnia".  Con el comando grep de Linux se puede hacer en pocos pasos, pero: ¿es esta una buena solución?

Recuperación de información (information retrieval) y busqueda en la Web, introducción

la recuperación de información puede ser definida, según Chris Manning,  como la búsqueda de material (generalmente documentos) de naturaleza no estructurada (generalmente textos) que satisface una necesidad de información dentro de una colección muy grande elementos (generalmente almacenados en computadoras).

Por supuesto no siempre buscamos documentos de texto, a veces buscamos imágenes o música en grandes colecciones. El lugar más frecuente en donde se realiza esta recuperación de información suele ser la Web, pero no es el único escenario, otros posibles son:

• búsqueda de un email en nuestra bandeja de entrada
• búsqueda de un archivo en nuestra computadora
• búsquedas en la base de datos de conocimientos de una empresa
• búsqueda de información legal 

Clasificación de Texto: Naïve Bayes paso a paso

Hagamos un ejemplo, paso a paso para afianzar los conocimientos. 

Supongamos que tengo 4 documentos en mi corpus de entrenamiento, y dos clases: "C" y "U" que indican si un documento habla sobre Chile o sobre Uruguay respectivamente. Tengo ademas un quinto documento con el cual voy a probar mi clasificador:

Corpus	Documento	Palabras	Clase
Entrenamiento	1	Chileno Santiago Chileno	C
	2	Chileno Chileno Valparaiso	C
	3	Chileno Allende	C
	4	Montevideo Uruguay Chileno	U
Prueba	5	Chileno Chileno Chileno Montevideo Uruguay	?

Clasificación de Texto: entrenamiento de Naïve Bayes

Repasemos como entrenar el algoritmo de clasificación de texto automático: Naïve Bayes para obtener los parámetros necesarios:

El estimador de máxima verosimilitud para la probabilidad previa de la categoría "cj", perteneciente al conjunto de categorías C es:

^            
P(cj) = cant. docs (C=cj)
             cant. docs

El estimador de máxima verosimilitud para la probabilidad previa de la palabra palabra wi dada la clase cj es:

^            
P(wi | cj) = cantidad (wi | cj)       

∑ cantidad(w,cj)

                   w∈V

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.  :-)