Cómo estimar la similitud entre documentos con Python

Cómo estimar la similitud entre documentos con Python

English version

¿Melania Trump plagió el discurso de Michelle Obama?

En el año 2016, durante la convención del partido republicano, Melania Trump dio un discurso apoyando la campaña de su esposo Donald; tan pronto como terminó la convención, usuarios de Twitter notaron similitudes en algunas lineas del discurso de la señora Trump y otro pronunciado por Michelle Obama ocho años antes en la convención del partido demócrata. La crítica sobre los Trump no se hizo esperar y el equipo de campaña llevó a cabo su labor de defensa con el argumento de que el discurso era un reflejo de experiencias de la vida real de Melania.

image

¿Cómo fue que los usuarios de Twitter notaron las semejanzas? Por un lado, algunas lineas eran exactamente iguales, por otro, como lo dijo un articulo de Usa Today:

It’s not entirely a verbatim match, but the two sections bear considerable similarity in wording, construction and themes.

Si quisieras automatizar el proceso de detección de similitudes ¿qué enfoque tomarías? Una posible solución sería comparar ambos textos, palabra por palabra, sin embargo esto no escalaría de manera eficiente; considera la complejidad de comparar todas las posibles frases compuestas por palabras consecutivas de un documento contra otro. Afortunadamente NLP nos da una solución elegante.

¿Cómo lo logramos?

Hay una técnica de NLP llamada similitud de textos, que se encarga del problema descrito: ¿Cómo comparar textos de una manera eficiente? Para lograr esto, es necesario transformar los documentos en un representación común y definir una métrica para compararlos.

En las secciones siguientes encontraras: los conceptos matemáticos detrás del proceso, el código explicado en detalle para que lo puedas reusar y finalmente la respuesta a la pregunta inicial: ¿Melania cometió plagio o no?

Conceptos de similitud de textos

TF-IDF

El texto es convertido en un vector. Las palabras se denominan features. Cada posición del vector representa un feature y el valor de la posición en el vector depende del método usado. Una forma de calcularlo, es contar cuantas veces la palabra aparece en el texto, dividirlo por el total de palabras únicas del documento y asignar este valor en el vector para el feature, esto es llamado Term Frequency o TF.

Screen Shot 2020-08-09 at 5.23.37 PM
Term frequency, siendo t una palabra, nt,d el número de veces que la palabra aparece en el documento. El denominador es el número total de palabras en el documento.

Term frequency por si solo da relevancia a palabras comunes en el documento, pero que no son necesariamente importantes, pueden ser stopwords, Las stopwords son palabras que no añaden valor al texto, como artículos, pronombres o preposiciones: yo, tu, el, la, a, ante, de, desde, etc.

Para saber si una palabra es importante en un documento, Inverse document frequency o IDF es usado, IDF encuentra la importancia en el documento contando cuantos documentos ademas del actual, contienen la palabra.

Screen Shot 2020-08-09 at 5.23.53 PM
Inverse document frequency.

En IDF, N representa el número de documentos en el corpus, mientras que dfrepresenta el número de documentos que contienen a una palabra t. Si todos los documentos en el corpus contienen la palabra t, entonces N/dft será igual a 1, y log(1) = 0, lo que significa que la palabra no es representativa, pues haciendo énfasis nuevamente, aparece en todos los documentos.

Term frequency–inverse document frequency o TF-IDF combina las dos métricas anteriores: si una palabra aparece en un documento, pero también aparece en los demás documentos del corpus, significa que no es representativa y TF-IDF le da un valor bajo. Por el contrario, si la palabra aparece muchas veces en un documento y solo aparece en ese documento, TF-IDF le da un valor alto.

Screen Shot 2020-08-09 at 5.24.30 PM
Term frequency–inverse document frequency.

Los valores de TF-IDF son calculados para cada palabra y dichos valores son asignados a las palabras del vector.

Similitud de coseno

Si se tienen los textos en representación vectorial ¿cómo se pueden comparar?

Primero, veamos un ejemplo de la conversión de texto a vector en Python:

from sklearn.feature_extraction.text import TfidfVectorizer

phrase_one = 'This is Sparta'
phrase_two = 'This is New York'
vectorizer = TfidfVectorizer ()
X = vectorizer.fit_transform([phrase_one,phrase_two])

vectorizer.get_feature_names()
['is', 'new', 'sparta', 'this', 'york']
X.toarray()
array([[0.50154891, 0.        , 0.70490949, 0.50154891, 0.        ],
       [0.40993715, 0.57615236, 0.        , 0.40993715, 0.57615236]])

Este código muestra dos textos, “This is Sparta” y “This is New York“. El vocabulario está compuesto por cinco palabras: “This“, “is“, “Sparta“, “New” y “York“.

La linea vectorizer.get_feature_names() muestra el vocabulario. La linea X.toarray() muestra ambos textos como vectores con el valor asignado por TF-IDF para cada palabra. Se puede ver como, para el primer vector, la segunda y quinta posición tienen un valor de cero. Estas posiciones corresponden a las palabras: new” y “york” las cuales no aparecen en el primer texto. De la misma forma, la tercer posición del segundo vector es también cero, esta posición corresponde a la palabra sparta“, la cual no aparece en el segundo texto.

¿Y cómo comparamos los vectores? Usando el producto punto es posible encontrar el ángulo entre dos vectores, este es el concepto conocido como similitud de coseno. Teniendo dos vectores y calculando el ángulo entre ellos, es posible medir que tan cerca están estos, por lo tanto, permite determinar que tan parecidos son dos textos. Un ángulo de cero significa que los textos son exactamente iguales. Si recuerdas tus clases de secundaria, el coseno de cero es 1.

Scalar-product.svg
El coseno del ángulo entre dos vectores da la medida de similitud.

Encontrando la similitud entre textos con Python

Primero, se cargan los paquetes de NLTK y Sklearn, se define una lista con los símbolos de puntuación y las stopwords, para que sean retiradas del texto.

from string import punctuation
from nltk.corpus import stopwords
from sklearn.metrics.pairwise import cosine_similarity
from sklearn.feature_extraction.text import TfidfVectorizer

language_stopwords = stopwords.words('english')
non_words = list(punctuation)

Se definen tres funciones, una para remover las stopwords, otra para remover los símbolos de puntuación y otra que recibe la ruta de un archivo de texto como parámetro, lee el archivo, transforma el texto a minúscula y llama las otras dos funciones para tener el texto preprocesado.

def remove_stop_words(dirty_text):
    cleaned_text = ''
    for word in dirty_text.split():
        if word in language_stopwords or word in non_words:
            continue
        else:
            cleaned_text += word + ' '
    return cleaned_text

def remove_punctuation(dirty_string):
    for word in non_words:
        dirty_string = dirty_string.replace(word, '')
    return dirty_string

def process_file(file_name):
    file_content = open(file_name, "r").read()
    # All to lower case
    file_content = file_content.lower()
    # Remove punctuation and spanish stopwords
    file_content = remove_punctuation(file_content)
    file_content = remove_stop_words(file_content)
    return file_content

Se llama la función process_file para cargar los archivos a analizar, en este ejemplo, estoy usando el contenido de tres posts anteriores de mi blog.

nlp_article = process_file("nlp.txt")
sentiment_analysis_article = process_file("sentiment_analysis.txt")
java_certification_article = process_file("java_cert.txt")

Una vez que se tiene el texto preprocesado, se usa TF-IDF y se aplica la similitud de coseno.

#TF-IDF
vectorizer = TfidfVectorizer ()
X = vectorizer.fit_transform([nlp_article,sentiment_analysis_article,java_certification_article])
similarity_matrix = cosine_similarity(X,X)

La salida es la siguiente matriz de similitud:

[[1.         0.217227   0.05744137]
 [0.217227   1.         0.04773379]
 [0.05744137 0.04773379 1.        ]]

Observa la diagonal de unos en la matriz, cada uno representa la similitud de un documento consigo mismo, el valor 0.217227 es la similitud entre los posts de NLP y análisis de sentimientos. El valor de 0.05744137 es la similitud entre el post de NLP y el de certificación de Java. Finalmente el valor de 0.04773379 representa la similitud entre los posts de análisis de sentimientos y el de la certificación de Java. Ya que el de NLP y el de análisis de sentimientos tratan temas en común, su medida de similitud es mas grande que la que tiene cada uno con la de la certificación de Java. 

Similitud entre el discurso de Melania Trump y el de Michelle Obama

Los textos de los discursos se pueden encontrar en este artículo, usando el mismo proceso se calcula la siguiente matriz de similitud:

[[1.         0.29814417]
 [0.29814417 1.        ]]

Si te saltaste la explicación técnica hasta este punto buscando el resultado, te daré un resumen: usando una técnica de NLP estimé la similitud de dos posts de este blog que tienen temas en común y fueron escritos por mi. Luego, usando el mismo método, estimé la similitud entre el discurso de Melania y Michelle.

Ahora, apliquemos algo de análisis. Al calcular la similitud entre dos posts escritos por un mismo autor (yo) que tratan sobre temas relacionados (NLP y análisis de sentimientos), el resultado fue de 0.217227. La similitud entre los discursos de Melania y Michelle fue de 0.29814417. Lo anterior, quiere decir, que dos discursos escritos por personas diferentes pertenecientes a corrientes políticas opuestas, son mas parecidos que mis dos posts. Te dejo la conclusión final a ti. El código completo y los archivos puedes encontrarlos en mi repo de Github.

¡Buena suerte con tu análisis!

NLP, inteligencia artificial aplicada al lenguaje humano

NLP, inteligencia artificial aplicada al lenguaje humano

English version

Vivimos en años de avance tecnológico, años de automatización; donde tareas humanas están siendo llevadas a cabo por maquinas o soportadas por ellas. Con estos avances, muchos términos han ganado popularidad: Big Data, machine learning, inteligencia artificial, deep learning, redes neuronales entre otros. Estos términos son populares, porque mas allá de ser una moda, han demostrado su aplicación en problemas reales. Hoy quiero traer un nuevo término Procesamiento del Lenguaje Natural o NLP por sus siglas en ingles.

¿Qué es NLP?

NLP es un área de la computación que busca analizar, modelar y entender el lenguaje humano, una tarea bastante difícil si lo pensamos un momento. ¿Has considerado como nuestro cerebro interpreta el lenguaje? ¿Como somos capaces de comunicarnos? Si tuviéramos claro este punto, ¿como podríamos llevar este conocimiento tácito a reglas explícitas que pudieran ser programadas en una máquina? Lo que antes parecía solo ciencia ficción ahora nos rodea todos los días y veremos por que.

Si has pronunciado las palabras “Hola Siri” ya has visto los beneficios de NLP de primera mano; claro está, puede que prefieras otra marca como Android, Microsoft, Amazon; indistintamente de si te diriges al asistente de Google, Alexa o Cortana, estas dando instrucciones que son interpretadas por una máquina. ¿Como funciona entonces NLP? Para entender esto, debemos entender como se estructura el lenguaje humano.

De vuelta al colegio

El lenguaje es como un conjunto enorme de piezas que podemos combinar para crear estructuras hermosas y gigantes. Para lograr estas estructuras, combinamos las piezas mas pequeñas para crear bloques de un tamaño un poco mayor. La combinación de piezas sigue ciertas reglas, y dichas reglas dependen de si estamos trabajando con las piezas mas pequeñas o con las que hemos construido a partir de estas. Las piezas mas pequeñas son denominadas fonemas, que en la práctica son las letras del alfabeto (A-Z). Las letras por si solas no logran tener un significado, así que comenzamos a combinarlas.

Los siguientes bloques se denominan morfemas, estos son la combinación minima de fonemas que logra tener un significado, de manera común las denominamos palabras, sin embargo, no todos los morfemas se consideran palabras, tal es el caso de prefijos (aero, anti, macro, infra) y sufijos (arquía, ito, ita, filia).

NLP
Composición de morfemas para construir uno nuevo. Los prefijos y sufijos no son palabras pero si morfemas.

Los lexemas son variaciones de los morfemas que comparten un significado común y en general, una raíz común; por ejemplo “encontrar”, “encontrando”, “encontrado”, “encontraste” comparten la raíz “encontrar”. Este concepto es particularmente importante en fases de NLP, dado que el texto a analizar suele tener distintos lexemas que confluyen al mismo significado y construyen el mismo contexto. El proceso de extraer la raíz común de los lexemas (o lemma) es llamado lematización, trabajar con la raíz de los lexemas permite resumir el texto y facilita el análisis.

Al combinar lexemas y morfemas, se obtienen frases y oraciones; existen ciertas reglas para estas combinaciones, pues no escribimos de manera aleatoria. Un ejemplo común de una oración bien formada suele tener un sustantivo, un verbo y proposiciones que los unen como en: “Javier toca la guitarra en las noches”. El conjunto de leyes que rigen el orden de las palabras es denominado sintaxis.

A partir de la combinación de frases y oraciones, nacen las grandes creaciones que amamos: libros, poemas, canciones, etc. En este nivel existe un contexto y la estructura refleja un significado. Este contexto es el que queremos que sea procesado y entendido por las maquinas.

¿Qué se está haciendo en NLP?

El área mas popular de investigación es clasificación de texto, el objetivo de esta área es asignar una o mas etiquetas a un texto. Un uso común es la detección de spam, usado por compañías como Gmail o Outlook. Otro caso de uso está en el soporte de servicio al cliente; estos equipos deben procesar miles de peticiones/reclamos, no es una tarea eficiente a gran escala, dada la necesidad de interacción humana, además, muchos de los reclamos suelen tener información que no es de valor (solo reflejan insatisfacción pero no el porqué); la clasificación de texto ayuda a filtrar la información que puede llevar a accionables. El proceso para aplicar clasificación de texto es similar al del entrenamiento de un modelo de machine learning, se inicia con un conjunto de datos (texto para el caso puntual), se asignan las etiquetas a cada una de las muestras, se divide el conjunto en entrenamiento y pruebas, se elige un algoritmo de entrenamiento apropiado para el problema y finalmente se entrena el modelo. Luego de la validación del modelo, se usa para clasificar los nuevos datos.

NLP (1)
Proceso para obtener un modelo de clasificación de texto.

Inicié la definición de NLP dando el ejemplo de Siri, Google assitant, Cortana y Alexa, estos hacen parte del área de agentes conversacionales. En general todas las areas de NLP, tienen en común la extracción de información, el objetivo de esta última es identificar las entidades mencionadas en el texto. Por ejemplo, en una frase como: “El presidente fue al congreso en Bogotá para defenderse de los cargos de corrupción”, para entender el significado, un algoritmo necesitaría extraer palabras como: “presidente”, “congreso”, “Bogotá” y “corrupción”, estas palabras son conocidas como entidades; pueden identificarse fácilmente ya que suelen tomar la forma de sustantivos. Del texto que se encuentra entre las entidades es posible extraer las relaciones: “El presidente fue al congreso”; entidades y relaciones forman un contexto. Un agente conversacional usa el contexto para responder a consultas del usuario, la interpretación de consultas involucra otra área de NLP, information retrieval; ademas de interpretar la consulta, busca dentro de documentos la/s solución/es mas cercana/s a dicha consulta; information retrieval es por supuesto usado en motores de búsqueda. Los agentes conversacionales se apalancan de las áreas mencionadas para dar solución a las peticiones de los usuarios.

A medida que se vuelve mas común la aplicación de NLP, nuevos casos de uso surgen: detección de eventos de calendario en correo electrónico, detección de plagio, reconocimiento de voz, corrección de ortografía, análisis de sentimientos, traducciones; la lista crece a medida que la investigación avanza.

¿Como trabajar con NLP?

Hay tres enfoques para trabajar con NLP, el primero es el uso de heuristicas. Con las heuristicas, las reglas para entender el lenguaje son creadas a mano; el enfoque es de utilidad para MVP’s de aplicaciones, pero es sensible al cambio de contexto (es decir los usuarios dejan de hablar como lo hacían cuando se crearon las reglas) y sufren de perdida de exactitud cuando la aplicación escala. Para trabajar con heuristicas se requiere de expertos en el dominio del problema, esto puede ser una desventaja si lo vemos como una dependencia mas del sistema; para compensar la ausencia del experto, o como una heuristica adicional, se suelen usar bases de conocimiento, diccionarios y tesauros disponibles en la web, estos recursos son mantenidos por la comunidad (en algunos casos) y de acceso libre. Una herramienta común para el análisis en este enfoque son las expresiones regulares, por ejemplo, la siguiente expresión podría usarse para extraer nombres de usuarios al analizar posts en redes sociales:

"@.*"

Un enfoque popular en NLP es el de machine learning; teniendo conjuntos de datos de texto, se entrena un modelo en la tarea deseada; las técnicas mas comunes son: naïve Bayes, support vector machines y conditional random fields. Los conditional random fields o CRF han ganado popularidad superando a los modelos de cadenas de Markov, al dar relevancia al orden de aparición de las palabras y el contexto que forman. CRF ha sido usado de manera exitosa en la extracción de entidades.

Finalmente, deep learning con el uso de redes neuronales es el tercer enfoque, aprovechando la habilidad de las redes neuronales para trabajar con datos sin estructura aparente.

¿Donde puedo iniciar?

Personalmente he trabajado con heuristicas y machine learning, el lenguaje de programación que recomiendo es Python, dada la versatilidad de trabajar con orientación a objetos, programación funcional y estructurada, ademas cuenta con un gran ecosistema para trabajar en ciencia de datos. Las herramientas que seguramente necesitaras son:

  • Pandas: Tu mejor amigo manipulando datos. Con pandas es bastante fácil cargar archivos csv y json, con los que seguro tendrás que interactuar, y trabajar con los datos en una estructura de matriz. Permite hacer búsquedas sobre la matriz, transformación, reducción de dimensionalidad, transformación de valores y filtrado entre otras. https://pandas.pydata.org/
  • Numpy: Es la herramienta para trabajar con algebra y estructuras de datos de n dimensiones. A medida que avances en el análisis de texto, veras la necesidad de convertir palabras y documentos en vectores, este paquete facilita el trabajo con estas estructuras. https://numpy.org/
  • Sklearn: La librería para trabajar con machine learning, tiene una gran cantidad de algoritmos de clasificación, métodos de cluster para aprendizaje no supervisado, preprocesamiento de datos, generación aleatoria de archivos de entrenamiento y pruebas así como funciones de evaluación entre otras cosas. Dominar esta herramienta es la base no solo para NLP sino para los temas que se relacionen con machine learning. https://scikit-learn.org/stable/
  • NTLK: Finalmente, el paquete ad hoc package para NLP, provee: clasificación, tokenización, lematización, parseo, diccionarios de stop words y en general un completo set de herramientas para análisis de lenguaje. https://www.nltk.org/

Para leer mas del tema te recomiendo:

Feliz investigación!