Análisis de contenidos generados por usuarios mediante la integración de información estructurada y no estructurada

Departamento de Lenguajes y Sistemas Informáticos Escuela Técnica Superior de Ingeniería Ingeniería Universidad de Sevilla Análisis de Contenidos Generados por Usuarios mediante la Integración de Información Estructurada y No Estructurada Juan Manuel Cotelo Moya Dirigida por Prof. Dr. José A. Troyano y por Prof. Dr. Fermín L. Cruz Universidad de Sevilla Sevilla, Junio 2015 Índice general 1. Introducción 1 1.1. Motivación y contexto . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Hipótesis ............................... 3 1.3. Resumen de la propuesta . . . . . . . . . . . . . . . . . . . . . . 5 1.4. Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Recuperación temática de tweets 7 2.1. Introducción.............................. 7 2.2. Trabajos relacionados . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Recuperación de información basada en preferencias de usuarios............................ 9 2.2.2. Métodos con pseudo-relevance feedback ........... 11 2.3. Definición de la tarea . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4. Métodopropuesto .......................... 14 2.4.1. Construcción del grafo . . . . . . . . . . . . . . . . . . . . 15 2.4.2. Análisis del grafo . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.3. Descripción del método . . . . . . . . . . . . . . . . . . . 18 2.5. Experimentación ........................... 20 2.5.1. Entorno experimental . . . . . . . . . . . . . . . . . . . . 22 2.5.2. Muestreo y etiquetado . . . . . . . . . . . . . . . . . . . . 22 2.5.3. Evaluación .......................... 23 2.6. Análisis de los resultados . . . . . . . . . . . . . . . . . . . . . . 24 2.6.1. Tamaño del conjunto de palabras clave . . . . . . . . . . . 24 2.6.2. Filtrando usuarios inherentemente ruidosos . . . . . . . . 26 2.7. Conclusiones y trabajo futuro . . . . . . . . . . . . . . . . . . . . 28 3. Normalización de tweets 29 3.1. Introducción.............................. 29 3.2. Trabajos relacionados . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.1. Transductores de estados finitos . . . . . . . . . . . . . . 32 3.2.2. Enfoques de carácter estrictamente léxico . . . . . . . . . 33 3.2.3. Sistemas modulares y multicomponente . . . . . . . . . . 35 3.3. Caracterización del problema . . . . . . . . . . . . . . . . . . . . 36 3.4. Arquitectura del sistema propuesto . . . . . . . . . . . . . . . . . 39 3.4.1. Preprocessado y detección . . . . . . . . . . . . . . . . . . 40 3.4.2. Generación de candidatos . . . . . . . . . . . . . . . . . . 41 3.4.3. Selección del candidato y resumen del proceso completo . 44 3.5. Recursos utilizados . . . . . . . . . . . . . . . . . . . . . . . . . . 44 iii 3.6. Evaluación del sistema . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6.1. Medidas de rendimiento . . . . . . . . . . . . . . . . . . . 47 3.6.2. Evaluación del sistema respecto a los módulos . . . . . . . 48 3.6.3. Rendimiento del sistema respecto a los fenómenos de error 50 3.6.4. Capacidad de adaptación del sistema . . . . . . . . . . . . 51 3.6.5. Ajustando la etapa de selección de candidatos . . . . . . . 52 3.7. Conclusiones y trabajo futuro . . . . . . . . . . . . . . . . . . . . 55 4. Combinación de información textual y estructural aplicada a la categorización automática de tweets 59 4.1. Introducción.............................. 59 4.2. Trabajos relacionados . . . . . . . . . . . . . . . . . . . . . . . . 61 4.2.1. Clasificación de polaridad en política . . . . . . . . . . . . 61 4.2.2. Clasificación de polaridad mediante propagación de etiquetas............................. 62 4.2.3. Categorización mas allá de la polaridad . . . . . . . . . . 63 4.3. Definición de la tarea . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.4. Extracción de conocimiento a partir del contenido textual . . . . 67 4.4.1. Modelo Bag-of-Words estándar . . . . . . . . . . . . . . . 68 4.4.2. Modelo BoW con selección automática de características . 69 4.5. Extracción de conocimiento a partir del contenido estructural . . 71 4.6. Estrategias de combinación de características . . . . . . . . . . . 73 4.6.1. Combinación directa . . . . . . . . . . . . . . . . . . . . . 74 4.6.2. Stacked Generalization . . . . . . . . . . . . . . . . . . . . 74 4.6.3. Multiple Pipeline Stacked Generalization . . . . . . . . . 75 4.7. Conclusiones y trabajo futuro . . . . . . . . . . . . . . . . . . . . 76 5. Detección de comunidades de interés mediante Spectral Biclustering 79 5.1. Introducción.............................. 80 5.2. Trabajos relacionados . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2.1. Métodos basados en análisis de enlaces . . . . . . . . . . . 81 5.2.2. Clustering de comunidades basado en significancia estadística............................. 82 5.2.3. Modelos generativos . . . . . . . . . . . . . . . . . . . . . 84 5.3. Definición de la tarea . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.4. Detección de comunidades usando Spectral Biclustering . . . . . 88 5.4.1. Creación del grafo bipartito . . . . . . . . . . . . . . . . . 89 5.4.2. El Método Louvain: un baseline exigente . . . . . . . . . . 90 5.4.3. La aproximación propuesta basada en biclustering . . . . 92 5.5. Evaluación de las aproximaciones . . . . . . . . . . . . . . . . . . 94 5.5.1. Coeficiente Silhouette . . . . . . . . . . . . . . . . . . . . 95 5.5.2. Evaluación extrínseca . . . . . . . . . . . . . . . . . . . . 97 5.5.3. Análisis cualitativo de usuarios políticamente relevantes . 98 5.6. Conclusiones y trabajo futuro . . . . . . . . . . . . . . . . . . . . 99 6. Conclusiones 101 Índice de figuras 2.1. Esquema del método presentado en Golbeck and Hansen (2011) . 10 2.2. Esquema general de un método con pseudo-relevance feedback . . 11 2.3. Recuperación temática de tweets . . . . . . . . . . . . . . . . . . 14 2.4. Grafo de elementos y relaciones posibles en un tweet . . . . . . . 15 2.5. Ejemplo de multiples relaciones en un solo tweet . . . . . . . . . 16 2.6. Muestra de interacción de usuarios en Twitter relacionada con Ferrari................................. 17 2.7. Proceso de construcción del grafo paso a paso del ejemplo provisto 19 2.8. Método propuesto para resolver la tarea de recuperación temática detweets ............................... 20 2.9. Precisión del dataset respecto al tamaño máximo del conjunto de términos (k).............................. 25 2.10. Cobertura de dataset o Dataset recall respecto al tamaño máximo del conjunto de términos (k)..................... 25 2.11. Precisión y dataset recall respecto a diferentes valores k, mostrando una curva de frontera de Pareto. .............. 26 2.12. Grafo de relevancia correspondiente al partido entre España y Portugal durante el evento Euro2012. . . . . . . . . . . . . . . . . 27 3.1. Ejemplo de un FST de pronunciación sobre las palabras inglesas data ydew .............................. 32 3.2. Funcionamiento del sistema de normalización propuesto en Porta andSancho(2013) .......................... 33 3.3. Funcionamiento del sistema de normalización propuesto en Gamalloetal.(2013b).......................... 35 3.4. Funcionamiento del sistema de normalización propuesto en Ageno etal.(2013).............................. 37 3.5. Distribución de términos detectados en el dataset . . . . . . . . . 38 3.6. Arquitectura del sistema con sus diferentes etapas de procesado . 41 3.7. Rendimiento del sistema con diferentes módulos activados . . . . 49 3.8. Rendimiento del sistema completo respecto a diferentes fenómenosdeerror.............................. 51 3.9. Distribución de la posición de ranking del candidato correcto . . 53 3.10. Inclusión de la etapa de clasificación a posteriori a la etapa de selección del sistema propuesto . . . . . . . . . . . . . . . . . . . 54 3.11. Rendimiento del sistema con una etapa de clasificación a posteriori 55 4.1. Arquitectura y funcionamiento del sistema de propagación de etiquetas descrito en Speriosu et al. (2011) . . . . . . . . . . . . . . 63 v 4.2. Esquema de funcionamiento general del sistema de clasificación automática descrito en Mohammad et al. (2014) . . . . . . . . . 64 4.3. Esquema del proceso de extracción de conocimiento a partir del contenidoestructural......................... 72 5.1. Esquema de evaluación al incluir el vértice ial subgrafo Cen el modelonulo.............................. 83 5.2. Funcionamiento del método iterativo de detección de comunidadesOSLOM.............................. 84 5.3. Representación gráfica del modelo TUCM . . . . . . . . . . . . . 85 5.4. Grafo de amistad directa generado a partir de la colección de tweetsobtenida............................ 87 5.5. Esquema general del proceso de detección de comunidades. . . . 88 5.6. Grafo bipartito construido a partir del grafo de amistad directa. . 90 5.7. Matriz de amistad sin estructura obtenida del grafo bipartito. . . 93 5.8. Matriz de amistad reordenada después de aplicar Spectral Biclustering.................................. 94 5.9. Grafo de similaridad de los creadores de contenidos extraído de la aproximación de Spectral Biclustering . . . . . . . . . . . . . . 95 5.10. Distribución de los coeficientes Silhouette . . . . . . . . . . . . . 96 Índice de cuadros 2.1. Desglose de la interacción de usuarios perteneciente a la figura 2.6 18 2.2. Precisión calculada y valores de consenso . . . . . . . . . . . . . 23 2.3. Comparativa de rendimiento entre métodos . . . . . . . . . . . . 24 2.4. Comparativa de resultados de rendimiento del método incluyendo el filtrado de usuarios ruidosos . . . . . . . . . . . . . . . . . . . 27 3.1. Distribución de términos detectados en el dataset . . . . . . . . . 38 3.2. Caracterización de los fenómenos de error encontrados en el dataset 40 3.3. Extracto de las reglas de transformación usadas en el sistema . . 43 3.4. Ejemplos de salida del sistema propuesto . . . . . . . . . . . . . . 45 3.5. Léxicos usados por el sistema propuesto . . . . . . . . . . . . . . 46 3.6. Rendimiento del sistema con diferentes módulos activados incrementalmente ............................. 49 3.7. Contribución de los módulos a la generación del candidato correcto respecto a cada fenómeno de error . . . . . . . . . . . . . . 50 3.8. Rendimiento del sistema completo respecto a diferentes fenómenosdeerror.............................. 50 3.9. Rendimiento del sistema sobre el dataset de evaluación del aborto. 52 3.10. Rendimiento maximal teórico para un proceso de candidato de selecciónperfecto........................... 53 3.11. Comparativa de rendimiento incluyendo la extensión propuesta . 55 4.1. Distribución de la opinión política dentro del dataset. . . . . . . 67 4.2. Exactitud con validación cruzada del modelo Bag-of-Words tradicional................................. 68 4.3. Exactitud con validación cruzada del modelo BoW con selección automática de características (AFS). . . . . . . . . . . . . . . . . 71 4.4. Exactitud con validación cruzada de las aproximaciones basadas entopologíadered.......................... 73 4.5. Exactitud con validación cruzada de la combinación directa de características............................. 74 4.6. Exactitud con validación cruzada del método Stacked Generalization ................................. 75 4.7. Exactitud con validación cruzada de la variante propuesta Multiple Pipeline Stacked Generalization . . . . . . . . . . . . . . . . 76 5.1. Exactitud con validación cruzada para diferentes modelos de características.............................. 97 5.2. Valores de afinidad de los 10 usuarios con mayor relevancia política 99 vii Agradecimientos En una primera instancia, deseo expresar mi más profundo agradecimiento a José, no sólo desde la perspectiva del gran trabajo como director de esta tesis, sino también por el apoyo moral y comprensión que me ha proporcionado durante todo el trayecto, y en especial, en los momentos más duros cuando todo parecía negro. A Fermín le agradezco todo el esfuerzo de codirección de esta tesis, siendo su paciencia y gran capacidad de análisis del detalle una habilidad inestimable respecto a la revisión tanto de los artículos como del borrador de esta memoria de tesis. Quiero agradecer a los compañeros Javier, Fernando y Carlos por su participación en los trabajos realizados durante el transcurso de la investigación doctoral. También agradezco a Marc y a Tomás toda la compañía ofrecida, pues ellos han conseguido que trabajar en aquél despacho se hiciera mucho más llevadero. Desde un punto de vista personal, agradezco enormemente la comprensión de mis amigos y compañeros, recalcando el apoyo y compañía ofrecido día a día durante todos estos años por parte de Mar, Sergio, Manu, Dani, Sonia, Ashur y Karim, los cuales me han proporcionado energía y motivación hasta en los peores momentos. También doy las gracias a mis compañeros del ámbito musical, sobre todo a Enrique y Alejandro, pues las incursiones realizadas en este ámbito han sido un soplo de aire fresco imprescindible para seguir adelante. Finalmente, en el plano familiar, agradezco todo el apoyo proporcionado por mis padres, Juan Manuel y Charo, y mi hermana, María, pues ellos me han instado a seguir adelante en todo momento. ix 4CAPÍTULO 1. INTRODUCCIÓN Los documentos suelen contener un gran contenido de opinión personal respecto al tema tratado, siendo principalmente motivados por un hecho polémico de reciente actividad. Existe un gran componente estructural en los mensajes con opinión y, con frecuencia, son respuestas a otros mensajes provistos por usuarios de mayor relevancia dentro de esa red. Los usuarios tienden a generar comunidades implícitas respecto a cada temática estudiada, agrupándose de forma orgánica sin necesidad de contacto directo; se agrupan compartiendo ideas e intereses comunes de forma indirecta. Dado que los usuarios, mensajes y sus relaciones forman parte fundamental de una red social, el análisis de los mismos no puede realizarse por separado. Gran parte de la significancia de los mensajes se pierde si no se considera el contexto de la red en el que se realiza. A la vista de las consideraciones expuestas, se comprende que no es una buena idea la de separar los mensajes del resto de entidades existentes en la red social. Cabe esperar que establecer algún tipo de mecanismo para detectar las comunidades sea un factor importante a la hora de analizar los mensajes; la respuesta de los usuarios respecto a un tema de opinión puede verse influida por las ideas de la comunidad a la que el usuario pertenece. Es necesario abordar dicho descubrimiento de comunidades mas allá del clustering tradicional, utilizando la información estructural de la red social. Sustentando la hipótesis 3, la clasificación de los mensajes de una red social respecto a una temática en cuestión se ve enormemente influida por la naturaleza del usuario dentro de esta red social. No sólo es importante el contenido del mensaje, sino el contexto de la red en el que se hace y a que grupos se refiere. Por ello, la idea de incorporar dicha información estructural como factor relevante, es bastante intuitiva, siendo importante elaborar un esquema de combinación y representación para combinar ambos tipos de información a la hora de diseñar un sistema clasificador. En otro orden e independientemente de las hipótesis presentadas, los mensajes provenientes de las redes sociales también tienen una interesante contrapartida de carácter transversal respecto a su información textual no estructurada. Estos mensajes suelen presentar, en muchas ocasiones, problemas de calidad respecto a la redacción del texto en cuestión. Tanto el auge de los dispositivos móviles como la relación que estos dispositivos tienen con las redes sociales, resultan en textos escritos a la carrera y en cualquier situación, primando la velocidad sobre la redacción del texto. Si se quiere cierto tipo de garantía a la hora de aplicar técnicas de PLN sobre estos textos, es necesario realizar algún tipo de tratamiento previo más allá del preprocesado tradicional. En esta tesis, también se ha abordado una tarea de esta naturaleza consistente en la normalización de tweets, cuyo objetivo consiste en restaurar los textos a nivel léxico para conseguir una redacción de mayor calidad y mejorando potencialmente cualquier tarea posterior sobre los textos restaurados. 1.3. RESUMEN DE LA PROPUESTA 5 1.3. Resumen de la propuesta En esta tesis se proponen una serie de técnicas y métodos para validar las diferentes hipótesis y situaciones planteadas, abordando la problemática de las tareas descritas dentro del contexto de las redes sociales. Cada problemática o tarea es tratada de forma individual, proporcionando una formalización para la misma, caracterizando los fenómenos más relevantes, proponiendo uno o varios métodos para abordarla, realizando una evaluación sobre ellos y explorando los resultados de forma consecuente. En líneas generales, las aportaciones expuestas en esta memoria de tesis son las siguientes: 1. Se aborda el problema de la recuperación de información en Twitter, paso inicial para generar cualquier dataset para cualquier otra tarea. Se propone un método dinámico y adaptativo para generar consultas que son consumibles por su sistema, utilizando una representación de grafo para calcular la relevancia de los términos en función de los tweets recogidos. Esta aportación ha sido plasmada y publicada en los artículos Cotelo et al. (2012) y Cotelo et al. (2014). 2. Se analizan los principales fenómenos de error en la redacción de los mensajes recuperados y se propone un sistema de normalización léxica altamente modular, cuya filosofía es que cada módulo realice un análisis independiente y se elija la mejor corrección. Esta aportación ha sido plasmada y publicada en los artículos Cotelo et al. (2013) y Cotelo et al. (2015a). 3. Se propone un esquema de integración para combinar modelos de características provenientes de información estructurada y no estructurada, el cual mejora significativamente la tarea de clasificación de mensajes. Esta aportación ha sido plasmada en el artículo Cotelo et al. (2015b) que está bajo revisión en el momento de la redacción de esta memoria. 4. Se explora la caracterización de grupos de usuarios dentro de un contexto específico, proporcionando un novedoso método para el descubrimiento de usuarios basado en biclustering. Esta aportación ha sido plasmada en el artículo Cotelo et al. (2015d) que está bajo revisión en el momento de la redacción de esta memoria. Además de lo expuesto, la obra Cotelo et al. (2015c) plasma el análisis conjunto de las tareas de recuperación de información y clasificación de opinión respecto al contexto político español de la red social Twitter durante un periodo determinado, detallando como se han relacionado ambos procesos y los resultados obtenidos. 1.4. Estructura de la tesis La estructura de esta memoria de tesis es como sigue. En el capítulo Recuperación temática de tweets (2) se aborda la problemática de la extracción de datasets significativos de la red Twitter, observando que la API que Twitter ofrece es insuficiente para afrontar el carácter temporal y espontáneo de la red y proponiendo un método de generación de consultas dinámicas que evolucionan 6CAPÍTULO 1. INTRODUCCIÓN y se adaptan a los temas que toman más protagonismo dentro de una temática especificada. En el capítulo 3 (Normalización de tweets) se analizan y caracterizan los diferentes fenómenos de error asociados a la escritura textual de los tweets, siendo éstos frecuentemente escritos desde dispositivos móviles, sin redacción ni reflexión antes de la publicación del mensaje. A partir de la caracterización de los errores, se propone un sistema para normalizar léxicamente estos tweets, siendo éste de naturaleza extensible y modular, fácil de ampliar requiriendo poco esfuerzo manual tanto para configurarlo inicialmente como para adaptarlo a otros contextos. En el capítulo 4 (Combinación de información textual y estructural aplicada a la categorización automática de tweets) se introduce al lector al análisis de afinidades políticas en Twitter, proponiendo una tarea de clasificación múltiple para determinar la postura de los mensajes respecto al panorama político español. Para determinar las posturas de los mensajes, se proponen dos grandes aproximaciones para la clasificación: basada en contenido y basada en estructura. Finalmente, se propone un esquema de integración de ambos tipos de modelos usando diferentes técnicas. En el capítulo 5 (Detección de comunidades de interés mediante Spectral Biclustering) se explora otra faceta del análisis del contexto político en Twitter, solo que ésta vez con un enfoque menos individual, intentando caracterizar colectivos de usuarios en función de intereses comunes mediante la detección de comunidades implícitas sobre una temática en particular (siendo en este caso, el panorama político español). La principal contribución consiste en una novedosa aproximación basada en biclustering, motivada por el bajo rendimiento obtenido con las técnicas de clustering tradicional. Adicionalmente, se incluye un análisis empírico de las comunidades obtenidas sobre una selección de usuarios no famosos ni oficiales con mayor relevancia obtenidas mediante el método explicado. Finalmente, en el capítulo 6 (Conclusiones) se realiza un resumen de las aportaciones y se describen las conclusiones más relevantes extraídas de la experimentación y los resultados de investigación. En lugar de existir un capítulo que aborda el estado del arte de forma monolítica, se ha tratado el estado del arte relacionado a cada capítulo individualmente, incluyéndose éste en una sección dentro de cada capítulo llamada Trabajos Relacionados. Cada una de esta secciones analiza el estado del arte de la tarea abordada en el capítulo, dedicando apartados específicos a diversos enfoques y trabajos de especial interés. Capítulo 2 Recuperación temática de tweets 2.1. Introducción Recientemente, Twitter ha recibido mas atención por parte de la comunidad científica debido, en gran parte, a factores como su alto potencial como recurso para tareas tales como el análisis de opinión o el seguimiento de temas “candentes” o de moda en tiempo real y su relativo éxito relacionado al reciente uso generalizado de los smartphones. Sin embargo, Twitter es una enorme red social en la cual buscar y recuperar mensajes, llamados tweets, que traten específicamente un tema o contexto no es una tarea nada fácil. Aunque Twitter proporciona una interfaz basada en palabras claves muy similar a la que proporcionan los modernos motores de búsqueda a los que estamos acostumbrados, esta interfaz es bastante limitada respecto a su utilidad y alcance, siendo más una simple herramienta de búsqueda para el usuario común que un punto de entrada para un proceso serio de extracción de datos. Mas aún, idear un conjunto de palabras clave que sea realmente efectivo es una tarea difícil por sí misma debido a dos factores fundamentales: la dificultad de establecer de antemano un conjunto de palabras clave adecuado para representar el tema en cuestión, y la muy cambiante naturaleza de la red, pues Twitter sufre de constantes interacciones y cambios en tiempo real. Antes de intentar analizar cualquier tipo de información específica a un tema que haya sido obtenida de Twitter, el proceso de recuperación de datos debe ser abordado de forma muy sistemática, con vistas a asegurar un buen grado de calidad y significancia en los datos extraídos. Esta idea es la principal motivación para abordar una tarea que no había sido previamente definida: dado un tema, obtener todos los tweets relacionados con ese tema durante una ventana de tiempo bien definida. Una formalización de esta tarea es necesaria para poder identificar correctamente sus principales problemas, siendo así mucho más fácil idear un método sistemático para abordar esta nueva tarea. Por ello, en este capítulo se establece una formalización para esta tarea y se presenta un método general para abordarla, aprovechando la estructura de grafo subyacente de Twitter. 7 8CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS Como se observa en la sección 2.2, la ausencia de aproximaciones que aborden de una forma general y sistemática el proceso de la recuperación de datos en Twitter, asegurando un alto grado de calidad y significancia en los datos obtenidos, es una de las motivaciones más importantes del esfuerzo que hay detrás de este capítulo. Las contribuciones de este capítulo se resumen a continuación: Se introduce el problema de la recuperación de tweets altamente relacionados con un tema específico, haciendo hincapié en las peculiaridades que deben tenerse en cuenta al tratar con información proveniente de Twitter. Se propone un método general para abordar dicha tarea, el cual se aprovecha de la estructura de red subyacente de Twitter. Se realiza un proceso de experimentación y evaluación en el cual se compara el método propuesto con otras aproximaciones típicas. Se realiza un análisis sobre los datos obtenidos, discutiendo algunos factores interesantes respecto al propio método propuesto y sugiriendo ciertas directrices para optimizar más aún el método. Este capítulo se organiza de la siguiente manera. En la sección 2.2 (Trabajos relacionados) se realiza una revisión del estado del arte actual relacionado con la temática del capítulo y se analizan algunos trabajos de mayor interés. En la sección 2.3 (Definición de la tarea) se introduce el problema y se propone una formalización de la tarea en sí. En la sección 2.4 (Método propuesto), se describe el método previamente mencionado para abordar la tarea. En la sección 2.5 (Experimentación) se describe el proceso de experimentación y se muestra una comparativa entre el método propuesto y las aproximaciones que típicamente se usan en las obras mencionadas. En la sección 2.6 (Análisis de los resultados), se realiza un análisis detallado sobre los datos recogidos por el método y se discuten algunas consideraciones importantes a tener en cuenta. Finalmente, en la sección 2.7 (Conclusiones y trabajo futuro) se exponen las conclusiones de este capítulo. 2.2. Trabajos relacionados La mayoría de los trabajos de investigación que usan datos provenientes de Twitter simplemente confían en usar la herramienta básica de consulta y, dependiendo del problema abordado, esto puede resultar en una pérdida significativa de datos y/o incurrir en un inesperado aumento del ruido en los datos recuperados. Esta situación se debe principalmente a que la correcta recuperación y tratamiento de los datos no es su preocupación principal y la mayoría de los trabajos simplemente confeccionan listas de términos de forma artesanal que usan para construir las consultas que van a ser usadas en la herramienta de búsqueda básica. Trabajos como Tumasjan et al. (2010); Gayo-Avello et al. (2011); Hong and Nadler (2011); Pennacchiotti and Popescu (2011); Congosto et al. (2011); Agarwal et al. (2011); Davidov et al. (2010a,b); Go et al. (2009); Jiang et al. (2011); Kim et al. (2009); Pak and Paroubek (2010); Silva et al. (2011); Tan et al. (2011) sólo hacen uso de este tipo de listas acorde a sus necesidades específicas, normalmente seleccionando usuarios y hashtags (etiquetas) que, mediante 2.2. TRABAJOS RELACIONADOS 9 algún criterio ad-hoc, guardan cierta relación con el tema abordado en cuestión. Este tipo de solución es demasiado específica y la cobertura de datos suele ser insuficiente para la tarea abordada. Un esfuerzo que es digno de mención, que proviene de la comunidad científica dedicada al Information Retrieval(IR), es la edición del 2012 del TREC Microblog track (Soboroff et al., 2012). La línea presentada comparte ciertas similaridades con el objetivo principal presentado en este capítulo pero su foco es claramente distinto; la principal tarea de búsqueda presentada es la Real-time Adhoc Task, consistente en obtener la más reciente aunque relevante información a partir de una consulta dada. De ahí que el objetivo es responder a una consulta específica teniendo en cuenta el tiempo de la consulta, devolviendo tweets relevantes ordenados de más a menos reciente. Por motivos técnicos, en lugar de usar la propia red Twitter, esas búsquedas se realizan sobre un corpus ya previamente generado y diseñado por el organismo americano NIST (National Institute of Standards and Technology). 2.2.1. Recuperación de información basada en preferencias de usuarios En la obra Golbeck and Hansen (2011) se presenta la idea de la recuperación de tweets personalizada mediante la creación de filtros en base a las preferencias de usuario, todo ello dentro del contexto político. Para ello, presenta una metodología completamente ad-hoc que estima el sesgo político de la audiencia de los medios de comunicación más relevantes, usando dichos valores estimados para la creación de filtros de tweets, mejorar la experiencia del usuario y, en resumen, abordar la recuperación de tweets desde un punto de vista distinto e interesante. Los autores estiman la preferencia política de las audiencias de los diferentes medios de comunicación usando información disponible de los informes oficiales de valoración política de los congresistas y utilizando a los usuarios seguidores de esos congresistas y consumidores de los medios de comunicación como enlace. El método que proponen para determinar la preferencia política de la audiencia de los medios se basa en tres pasos: 1. Se establecen las puntuaciones base a priori sobre el conjunto de usuarios del grupo semilla, siendo en el caso específico explorado por los autores, los congresistas de los estados unidos. Usando el informe oficial de la asociación Americans for Democratic Action (ADA) referente al año 2009 (for Democratic Action, 2009), se asigna a cada congresista cun valor pc∈[0,1] indicando cómo de liberal es ese congresista, siendo 0un congresista muy conservador y 1un congresista muy liberal. El uso de esta medida específica se debe a que ésta es una medida muy aceptada para valorar la posición política. 2. Se calculan los valores de preferencia política a los usuarios seguidores de los congresistas, usando para ello los valores de los congresistas anteriormente calculados. Los autores parten de la suposición que, de media, la preferencia política de un seguidor cualquiera es reflejada por los valores ideológicos de aquellos congresistas a los que siguen. Por ello, establecen que para cada seguidor f, el valor de preferencia política inferido pfconsiste en la media aritmética de los valores de pertenencia asignados a los 10 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS congresistas que el usuario fsigue, quedando que si Cfes el conjunto de congresistas a los que fsigue, pf=Pc∈Cfpc |Cf|. Los valores de pftambién se encuentran en el intervalo [0,1] y tienen un significado análogo a pc. 3. Calcular los valores de preferencia política sobre el conjunto de cuentas de usuario objeto de la investigación, usando para ello los valores de los usuarios seguidores calculados anteriormente. De manera análoga al paso anterior, se calculan los valores de los medios de comunicación, siendo el valor pmdel medio de comunicación mcomo la media aritmética de los valores de preferencia de los usuarios seguidores de los congresistas que siguen al medio mespecíficamente. Sin embargo, la representación política está demasiado sesgada debido a que la distribución de seguidores está muy desequilibrada; aunque la representación política de la cámara era principalmente Demócrata, los congresistas republicanos tenían un número desproporcionado de seguidores, dejando a la otra clase política claramente poco representada. Cualquier cálculo directo induciría incorrectamente a que la mayoría de los medios serían mucho mas conservadores de lo que realmente son. Para solventar esta situación, los autores proponen un esquema de muestreo con validación cruzada, donde las clases están equilibradas respecto a los resultados de las elecciones del congreso1, usando k= 10 folds y ponderando el resultado final sobre todos los folds muestreados. La figura 2.1 consiste en un esquema del proceso descrito, mostrando el carácter secuencial del método y los elementos que intervienen. Figura 2.1: Esquema del método presentado en Golbeck and Hansen (2011) Uno de los resultados interesantes que obtienen los autores mediante el método propuesto es que la distribución de valores de preferencia de los usuarios en el contexto político es claramente bimodal, argumentando que una de las razones principales radica en que los datos originales de los que parten también exigen bimodalidad. Esto contrasta con otros estudios que aseguran que la distribución de la opinión política es exhibe cierta normalidad, siendo la mayoría de la población 1vigentes respecto al momento de la escritura del artículo 2.2. TRABAJOS RELACIONADOS 11 moderada. Otro factor importante a tener en cuenta se debe a que los usuarios que suelen seguir a los congresistas son usuarios políticamente conscientes y activos, características que conllevan a una serie de ideologías mas radicales, desmarcándose claramente de los sectores mas moderados. Este método utiliza, aunque muy limitadamente, la topología de red del contexto político que exploran, consiguiendo un modelo básico para caracterizar al grupo objetivo mediante los propios usuarios, partiendo de un conocimiento base previo. Este modelo tiene utilidad dentro de la recuperación de información pues permite realizar un ajuste o filtrado sobre un conjunto obtenido previamente, mejorando la calidad y el enfoque del subconjunto resultante. Incluso se puede ajustar para personalización o análisis de sesgo. Sin embargo, este método no es general ni dinámico, requiere de cierto tipo de información base inicial que no siempre se puede disponer y no tiene en cuenta los contenidos de los usuarios ni cómo éstos reaccionarían a eventos imprevistos, pues sólo tiene en cuenta la topología estática en un momento determinado del tiempo. 2.2.2. Métodos con pseudo-relevance feedback Relevance feedback es una característica que exhiben algunos métodos de IR, basada en la idea de utilizar los resultados relevantes de una consulta inicialmente dada para realizar otra consulta (o refinar una existente), descartando los no relevantes en el proceso. Existen tres tipos principales de relevance feedback: explícito, implícito y “pseudo” o ciego. Tanto el explícito como el implícito requieren de intervención humana, mientras que el “pseudo” es completamente automático. En nuestro caso, los únicos métodos que interesan son aquellos con pseudorelevance feedback o “ciegos”, dado que el carácter iterativo y de refinamiento se asemeja, en términos muy generales, al método dinámico adaptativo que se propone. Figura 2.2: Esquema general de un método con pseudo-relevance feedback Aunque los detalles explícitos dependen del método en cuestión, el proceso general consiste en un análisis automático local de los datos y las consultas. 12 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS En términos generales, el sistema parte de un conjunto definido de documentos, los analiza, elige los mejores y utiliza esa información para refinar la consulta. La figura 2.2 muestra un esquema general de un proceso iterativo con pseudorelevance feedback. Estos métodos suelen funcionar bastante bien y, mediante la expansión de consultas, pueden mejorar la cobertura de las consultas realizadas inicialmente y mejorar el rendimiento global. No obstante, este efecto se basa enormemente en la calidad del análisis y la selección, y cualquier procedimiento de este tipo puede derivar en resultados erróneos y/o no deseados si el proceso no es controlado correctamente. Sin embargo, nuestro método difiere en puntos bastante esenciales; todo el proceso de análisis y refinamiento se basa en un análisis topológico de los elementos estructurales de los mensajes, como se explica en la sección 2.4. Puede encontrarse mas información sobre modelos con “pseudo-relevance feedback” o efectos similares en obras como Lee et al. (2008), Tao and Zhai (2006), Cao et al. (2008) y Lavrenko and Croft (2001). 2.3. Definición de la tarea El objetivo final de la tarea tratada en este capítulo consiste en la recuperación de todos los mensajes de los usuarios en Twitter (llamados tweets) relacionados con un tema específico y que han sido enviados durante una ventana de tiempo en concreto. Para entender la complejidad esta tarea, hay que aclarar tres conceptos importantes que la definen: Twitter, tema y tiempo. En Twitter, los tweets poseen ciertas características especiales a considerar. En primer lugar, existe una restricción estricta respecto a la longitud de los tweets, siendo 140 caracteres este límite superior, cosa que no es del todo inusual pues la brevedad de los mensajes es una parte fundamental en cualquier red de micro-blogging. Como contrapartida, restricciones de longitud muy frecuentemente conllevan fenómenos como palabras acortadas, abundancia de acrónimos y técnicas similares para poder lidiar con este límite impuesto, resultando en una pérdida de calidad general respecto a la redacción del texto. Incluso herramientas acortadoras de URL se han convertido en una necesidad cuando se desea incluir hipervínculos en el tweet. En segundo lugar, los tweets sólo pueden contener lo que se denomina texto plano, lo que significa que el contenido no posee formato de ningún tipo. Twitter proporciona adicionalmente un par de constructos especiales (también representados en texto plano) para especificar interrelaciones entre usuarios. Uno de ellos, es la mención directa a otros usuarios en un tweet usando el carácter ’@’ como prefijo al nombre del usuario mencionado en cuestión. El otro tipo de constructo son los denominados comúnmente “hashtags”, los cuales son palabras o inclusos expresiones (palabras concatenadas sin usar espacios) prefijadas por el carácter ’#’. Se usan principalmente para marcar el mensaje y participar en una especie de discusión ad-hoc sin mecanismo de moderación sobre un tema bastante específico, funcionando como etiquetas de metadatos sin administración por parte de la plataforma. Más aún, estos hashtags son promocionados por usuarios individuales y algunas veces actúan como “señales” o indicadores, pudiéndose vagamente relacionar entre sí tweets que hayan usado hashtag, estableciéndose así un criterio de agrupación. 2.3. DEFINICIÓN DE LA TAREA 13 En tercer lugar, Twitter sólo ofrece el uso de consultas directas para poder obtener los mensajes de su plataforma. Las consultas deben estar formadas por palabras claves (ya sean palabras, hashtags o nombres de usuario) y su composición es bastante simple, asemejándose mucho a las interfaces ofrecidas por los típicos motores de búsqueda web. Aunque simple e intuitivo, este tipo de interfaz restringe drásticamente y dificulta el diseño de aproximaciones para resolver la tarea de la recuperación temática de tweets. El concepto de tema es sencillo de entender de forma intuitiva pero es difícil establecer una definición exacta. En términos generales, podríamos definir un tema como el sujeto u objecto principal de una discusión entre usuarios. Asimismo, la realización del tema deseado podría ser difícil por sí misma, encontrando dificultades en la “transformación” del concepto abstracto a algo que puede ser consumido por sistemas de información. Con respecto al concepto de la temporalidad, otra cosa a tener muy en cuenta es el dinamismo temporal de la propia red. Twitter es una red social que exhibe constantes cambios en tiempo real y su comunidad reacciona muy rápidamente a cualquier evento, creando nuevas tendencias, temas y hashtags constantemente. Esto dificulta considerablemente el seguimiento de temas a lo largo de un periodo de tiempo. Todos estos factores convierten la recuperación temática de tweets en una tarea nada trivial pero muy interesante: generar consultas que aseguren la recuperación de tweets de alta significancia a lo largo del tiempo. Una vez expuesta esta explicación intuitiva de la tarea, se propone una formalización de la misma (Definición 2.1) que servirá como apoyo para el resto de este capítulo. Definición 2.1 Dadas las siguientes disposiciones: Sea Tel conjunto de todos los tweets existentes en Twitter. Dado que T crece continuamente en el tiempo, se denota como Ttal conjunto de todos los tweets existentes en el instante t. Sea Qel conjunto de todas las consultas que se pueden hacer sobre T. Cada consulta q⊆Qes un conjunto específico de palabras clave cuya ejecución en el instante tdevuelve Tt q⊆Ttque es el conjunto de tweets en Ttque contienen al menos una de las palabras claves de q. Sea Tt tema ⊆Ttel conjunto de todos los tweets existentes en Twitter en el instante tque guardan relación sobre un tema específico. Sea Qt tema ⊆Qtal que Qt tema =qi:Tt qi⊇Tt tema. Dado un instante t, la tarea de recuperación temática de tweets consiste en: 1. Caracterizar un qi∈Qt topic, preferiblemente con un |Tt qi|pequeño, que limite el número de tweets recuperados que no guarden relación con el tema en cuestión. 2. Seleccionar los tweets del resultante Tt qique pertenezcan a Tt topic, eliminando los tweets que no están relacionados con el tema en cuestión. Esta formalización realiza una división natural de la tarea en dos subtareas, cada una relacionada con los puntos (1) y (2) de la definición 2.1 respectivamente: generación de consultas yfiltrado. Aunque ambas tareas están claramente 20 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS Figura 2.8: Método propuesto para resolver la tarea de recuperación temática de tweets ventana de 60 minutos es una elección muy adecuada. Al no tener iteración anterior, la primera iteración del método carece de tweets previamente capturados, necesitando algún tipo parámetro inicial. En este caso, se usa un conjunto semilla de palabras clave, siendo lo más apropiado que este conjunto semilla represente el conjunto central del tema seleccionado de forma adecuada. Después de realizar el paso de construcción del grafo con los datos de la iteración anterior, se usa PageRank para confeccionar un ranking de relevancia sobre los nodos del grafo, el cual se va a utilizar como lista tentativa de candidatos. El proceso de selección de candidatos se realiza simplemente eligiendo los mejores nodos y descartando el resto, estableciendo algún punto como umbral en la lista, cuyo valor se determina de antemano. Para este caso, se determina que el punto de corte es un parámetro entero k, representando el tamaño máximo del conjunto de elementos seleccionados, fijo de antemano al inicio del método. Finalmente, generar la consulta consumible por Twitter es un paso bastante directo. Los elementos seleccionados por la etapa anterior son usados como palabras clave y todos son concatenados usando el típico operador or. En esencia, usamos los mismos elementos estructurales propios de Twitter (usuarios y hashtags) para la construcción de las consultas pero teniendo en cuenta la topología de red subyacente y la naturaleza cambiante de Twitter. Como ya se ha comentado previamente en el apartado 2.2.2, el método propuesto guarda cierta semejanza con los métodos que poseen o se basan en el efecto pseudo-relevance feedback usado en IR y a nivel muy esencial tienen elementos en común. Sin embargo, nuestro método difiere muy significativamente del modelo pseudo-relevance feedback en varios puntos clave: construcción de grafo y análisis topológico en lugar de usar un modelo vector space, tener en cuenta los elementos estructurales en lugar de sólo el contenido y la realización de las consultas usando esos elementos estructurales. 2.5. Experimentación Para poder probar el rendimiento del método propuesto en este capítulo, se ha aplicado sobre un tema en concreto, realizado un análisis sobre el conjunto 2.5. EXPERIMENTACIÓN 21 ALGORITMO 1: Método propuesto Data: Términos semillla s, ventana de análisis w, tiempo de iteración i 1begin 2Terminos ← {s} 3T← ∅ 4repeat 5T←T∪AplicarConsultaTwitter(Terminos,i) 6G←CrearGrafoVacío() 7Tw←tweets de Tobtenidos en las últimas witeraciones 8foreach tweet t∈Twtales que el término saparece en tdo 9user ←usuario que escribió t 10 tags ←hashtags que aparecen en t 11 mentions ←menciones de usuario que aparecen en t 12 if user /∈Gthen 13 actualiza Gcon un nodo que represente a user 14 foreach tag ∈tags do 15 if tag /∈Gthen 16 actualiza Gcon un nodo que represente tag 17 if arco dirigido a= (user, tag)/∈Gthen 18 añadir a Gel arco dirigido a 19 incrementa el peso del arco existente a= (user, tag) 20 foreach mentioned_user ∈mentions do 21 if mentioned_user /∈Gthen 22 actualiza Gcon un nodo que represente a mentioned_user 23 if arco dirigido a= (user, mentioned_user)/∈Gthen 24 añadir a Gel arco dirigido a 25 incrementa el peso del arco existente a= (user, mentioned_user) 26 foreach tag1, tag2∈tags tales que tag16=tag2do 27 if arco no dirigido a= (tag1, tag2)/∈Gthen 28 añadir a Gel arco no dirigido a 29 incrementa el peso del arco existente a= (tag1, tag2) 30 R←PageRank(G) 31 Terminos ←primeros ntérminos de R 32 until fin de la sesión de recuperación de tweets 22 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS de datos obtenido y generado una comparativa con otras aproximaciones más simples y con diferentes parámetros de configuración. 2.5.1. Entorno experimental El tema seleccionado para la recolección de datos fue el evento Campeonato Europeo de Fútbol de la UEFA 2012, coloquialmente llamado Eurocopa 2012 oEuro2012. Este evento es una competición deportiva muy importante en el continente europeo y muy seguida por todos los medios de comunicación, especialmente por los medios de deporte. El evento fue abordado desde la perspectiva española, siendo solo de interés los tweets en Español. El término central usado como semilla para el método fue el famoso hashtag #vamosespaña. Este hashtag era bien recibido en la comunidad española, siendo un término muy común para animar a la selección española de fútbol que participaba en el evento. La recolección de tweets se hizo durante la duración de todo el evento, que duró desde el 6 de junio del 2012 al 3 de julio del 2012. Para ello se usaron tres métodos diferentes en paralelo, que se describen a continuación: Palabra clave central: Usar la palabra clave central elegida, siendo en este caso el término #vamosespaña, como único término de consulta durante todo el evento. Esta aproximación simplista es usada como baseline comparativo respecto al resto de métodos durante el análisis experimental. Lista estática ad-hoc de palabras claves: Está aproximación consiste en hacer uso de una colección de palabras clave elegidas por un experto (siendo estas usualmente hashtags) como consulta estática a lo largo de todo el evento. Para probar este método, se ha elegido el siguiente conjunto de palabras clave: #vamosespaña,#nohaydossintres,#eurocopa, #eurocopa2012,#laroja. Estos términos fueron elegidos por su alta relevancia y muy baja ambigüedad respecto al evento. Método dinámico propuesto: Se usa como semilla inicial para el método la palabra clave central #vamosespaña, variando el tamaño máximo de palabras claves inferidas hasta un valor de k= 20. 2.5.2. Muestreo y etiquetado Evaluar completamente un dataset de estas características sería una tarea titánica, pues requeriría de revisar manualmente del orden de cientos de miles o incluso millones de tweets; el dataset del caso partícular tratado en este capítulo está compuesto por unos 3 millones de tweets. En su lugar se escoge una muestra aleatoria significativa que, acorde al teorema central del límite, estableciendo un nivel de significancia estadística α= 0,05 y una cota superior de error del 1 %, consta de 10000 mensajes aunque solo se requieren estrictamente 9604 mensajes. Esta muestra permite inferir con precisión las propiedades del dataset original y es usada durante todo el proceso de evaluación en lugar del dataset original. Para poder estimar la precisión, tres revisores etiquetaron manualmente cada mensaje si era relevante o no, muy similar a un proceso de clasificación binaria. La tabla 2.2 muestra los datos de precisión acorde a cada revisor y el índice de 2.5. EXPERIMENTACIÓN 23 consenso entre revisores. Los valores de consenso y el estimador κ(Fleiss, 1971) indican que la tarea de etiquetado está bien definida y que las anotaciones hechas por los revisores son lo suficientemente fiables para usar la media armónica de los valores de precisión obtenidos individualmente como medida de precisión para posteriores usos en este proceso de evaluación. Medida Revisor 1 Revisor 2 Revisor 3 Precision 0.8882 0.8292 0.8715 Consenso con Revisor 1 1.0 0.9290 0.9651 Consenso con Revisor 2 0.9290 1.0 0.9375 Consenso con Revisor 3 0.9651 0.9375 1.0 Consenso completo 0.9158 Estimador κ0.7627 Cuadro 2.2: Precisión calculada y valores de consenso 2.5.3. Evaluación Mediante la muestra anotada, se puede estimar la precisión (proporción de los tweets recuperados que son relevantes) con un error inferior al 1 %, siendo esta debidamente calculada e incluida en este estudio. Sin embargo, el cómputo de la cobertura, llamada recall en la literatura, presenta grandes dificultades en este estudio. Para explicar por qué el cálculo exacto de la cobertura no es factible, es necesario entender en que consiste exactamente: mide cuantos documentos relevantes han sido en comparación al total de documentos relevantes que existen. En este caso, significaría que se debería saber el número exacto de tweets existentes en todo Twitter que están relacionados con el tema seleccionado, cosa que no es para nada factible. Mas aún, el muestreo no es una técnica viable para obtener una estimación correcta sobre el número de tweets existentes relacionados con la temática. Aunque Twitter proporciona un flujo muestral con una distribución pseudoaleatoria de mensajes, es extremadamente raro que algún mensaje del tema en cuestión aparezca en ese flujo, dado que cualquier temática a elegir es insignificante en comparación con el total de temáticas que pueden darse en toda la red Twitter en un momento determinado. Si consideramos el tamaño máximo evaluado para el conjunto de palabras clave en este entorno experimental (k= 20), el dataset resultante posee alrededor de 3 millones de mensajes y en Twitter se generan mil millones de mensajes semanales de media, dejando muy poco margen para obtener una muestra significativa de mensajes relevantes totales. Por ello, se consideró dejar de lado el uso la métrica recall exacta para el proceso de evaluación y su uso para cualquier otra medida. En su lugar, se ha definido una medida alternativa llamada cobertura de dataset odataset recall, la cual es similar a la medida de recall pero a nivel de dataset, solo teniendo en cuenta todo los tweets relevante obtenidos como estimación de los todos los tweets relevantes existentes. Esta alternativa permite medir la capacidad de cobertura del método respecto a diferentes parámetros. 24 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS Al igual que con la medida de precisión, esta medida produce cualquier valor x∈R:x∈[0,1]. La tabla 2.3 muestra una comparativa de los resultados de rendimiento del método propuesto respecto al baseline y el método de lista estática adhoc usado en la mayoría de las aplicaciones. Como se ha mencionado antes, los términos propuestos para el método de lista estática fueron aquellos que tuvieron alta relevancia dentro de la comunidad española respecto al even- to (#vamosespaña,#eurocopa,#eurocopa2012,#laroja), mientras que para el método dinámico propuesto, se muestran valores de rendimiento para los parámetros k= 10 yk= 20. Método Precisión Dataset Recall Baseline (sólo el término central) 0,9726 0,1504 Lista estática seleccionada 0,9721 0,2698 Método dinámico con k= 10 0,9274 0,8034 Método dinámico con k= 20 0,8713 1,0000 Cuadro 2.3: Comparativa de rendimiento entre métodos En líneas generales, se observa que nuestro método obtiene un mayor volumen de datos a expensas de un ligero descenso en la precisión aunque elegir correctamente el parámetro kno es trivial y depende mucho del problema en cuestión. Esta pérdida de precisión se debe en parte a la inclusión no deseada de usuarios con un alto número de seguidores, cuyos mensajes tienen un gran impacto en la red social pero son altamente “ruidosos”, debido a que suelen escribir sobre una gran variedad mensajes de temática muy variada y son usuarios muy mencionados 3. 2.6. Análisis de los resultados Una manera de analizar efectivamente el rendimiento del método consiste en la observación de su comportamiento respecto al tamaño del conjunto de palabras claves dinámicamente generado, reflejando el grado de bondad de las consultas generadas y que efectos tienen sobre el dataset. 2.6.1. Tamaño del conjunto de palabras clave La figura 2.9 muestra el comportamiento de la precisión del dataset respecto a diferentes valores de tamaño máximo del conjunto de términos (k) y es fácil de observar que la pérdida de precisión está claramente asociada al incremen- to del tamaño máximo del conjunto de términos. Este comportamiento no es inesperado, pues el método intenta aumentar el volumen del conjunto de datos mediante la introducción de nuevos términos, siendo esta una forma usual de introducir ruido en el dataset. Sin embargo, esta pérdida de precisión es relativamente baja, siendo muy estable para determinados intervalos del parámetro k. 3Cuando se hace una consulta a Twitter que contiene un nombre de usuario, se obtienen tanto los tweets escritos por ese usuario como los que los tweets que hacen mención a este. 2.6. ANÁLISIS DE LOS RESULTADOS 25 Figura 2.9: Precisión del dataset respecto al tamaño máximo del conjunto de términos (k) Figura 2.10: Cobertura de dataset o Dataset recall respecto al tamaño máximo del conjunto de términos (k) Como se ha mencionado anteriormente, el cómputo de la medida recall no es factible, habiendo utilizado la cobertura de dataset o dataset recall en su lugar. Aunque no es un substituto real de la medida original, el uso de esta medida alternativa se considera como muy apropiado, debido a que el foco principal del método es el de incrementar el volumen de datos obtenidos sin incurrir una alta pérdida en la precisión. La figura 2.10 muestra el comportamiento de la medida alternativa dataset recall respecto a diferentes valores del parámetro k. Un método mejor para identificar el “mejor” valor de kconsiste en ordenar ambas métricas en conjunto, similar a una figura de frontera de Pareto, siendo 26 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS Figura 2.11: Precisión y dataset recall respecto a diferentes valores k, mostrando una curva de frontera de Pareto. la figura 2.11 un claro ejemplo de este tipo de combinación. En ella se muestra una curva de eficiencia paramétrica, siendo cada punto de la curva la precisión y el dataset recall para cada valor de k, observándose que la curva exhibe un buen compromiso entre precisión y volumen de datos para un valor de k= 8. Ese punto en concreto (k= 8) consigue una precisión del 93,43 % y una cobertura de dataset del 74,78 %, resultando en un incremento de volumen de 5,32 veces respecto al baseline con sólo un descenso en la precisión del 3,5 %. A partir de este punto, la curva empieza a caer considerablemente, por lo que puede no ser conveniente incrementar el valor de k. Por supuesto, esta conclusión no es aplicable a todos los casos: el valor de kóptimo depende de la naturaleza de la temática elegida y de las necesidades de la aplicación en concreto. 2.6.2. Filtrando usuarios inherentemente ruidosos Como se ha mencionado con anterioridad, algunos de los usuarios incluidos contribuyen enormemente a la pérdida de precisión observada, induciendo una considerable cantidad de ruido. Estos usuarios son, con frecuencia, personas muy famosas y existen dos buenos ejemplos en nuestro dataset: El piloto español de Fórmula Uno Fernando Alonso (@alo_oficial) y el cantante y compositor español Alejandro Sanz (@alejandrosanz). Estos usuarios fueron inicialmente seleccionados por el método porque explícitamente animaron a la selección española de fútbol, pero han permanecido en la topología debido a su alta relevancía dentro de Twitter. Alrededor del 44,62 % de los mensajes obtenidos relacionados con @alejandrosanz guardan relación con el tema explorado, siendo el resto una considerable cantidad de ruido. El caso de los mensajes relacionados con el usuario @alo_oficial es significativamente peor, pues solo el 15,80 % de los mensajes son relevantes, siendo la mayoría de sus mensajes una fuente de ruido. Si filtramos sólo estos dos usuarios ruidosos del dataset, podríamos obtener un aumento en la precisión muy significativo a expensas de una ligera pérdida 2.6. ANÁLISIS DE LOS RESULTADOS 27 de volumen. En efecto, filtrando estos usuarios ruidosos, el método propuesto es capaz de incrementar la precisión por encima del 91 % para k= 20 y por encima del 96 % usando el propuesto k= 8. La tabla 2.6.2 contiene una comparativa mostrando las diferencias de rendimiento entre la versión del método con y sin filtrado adicional. Método Precisión D. Recall Prec. diff D. Recall diff k= 8 0,9343 0,7478 - - k= 10 0,9274 0,8034 - - k= 20 0,8714 1,0000 - - k= 8 c/filtrado 0,9604 0,8298 +2,61 % −1,74 % k= 10 c/filtrado 0,9521 0,8609 +2,48 % −1,77 % k= 20 c/filtrado 0,9185 0,9488 +4,72 % −1,88 % Cuadro 2.4: Comparativa de resultados de rendimiento del método incluyendo el filtrado de usuarios ruidosos Figura 2.12: Grafo de relevancia correspondiente al partido entre España y Portugal durante el evento Euro2012. 28 CAPÍTULO 2. RECUPERACIÓN TEMÁTICA DE TWEETS La figura 2.12 muestra el grafo de relevancia correspondiente al partido entre España y Portugal durante el evento Euro2012, siendo visualmente sencillo detectar las entidades mas relevantes en el grafo y el grado de inteconexión existente. Debido a que el término central usado (#vamosespaña) es demasiado relevante y está extremadamente conectado con el resto de elementos, por motivos de claridad, se ha omitido del grafo. Se observa que el usuario @alejandrosanz está presente en el grafo como elemento relevante aunque exhibe el comportamiento de un “exterior hub” o “núcleo periférico”; posee una gran comunidad pero está sufre de una vaga conexión con el resto de elementos del grafo, indicando una baja relación con el resto de términos y de la temática en general. Esto se correlaciona con el ruido previamente asociado a este usuario y es bastante intuitivo que eliminar este tipo de “núcleos periféricos” del grafo es una buena aproximación para una etapa de filtrado. 2.7. Conclusiones y trabajo futuro En este capítulo, se ha provisto de una formalización para una tarea, hasta el momento no muy bien definida, que es de importancia para hoy en día: la tarea de la recuperación temática de tweets. A partir de esta definición, se idea y propone un método general que aborda la tarea, haciendo hincapié en el análisis estructural del grafo subyacente, apostando por una aproximación topológica en lugar de una puramente textual. La evaluación muestra la efectividad del método propuesto, observando que al elegir un buen punto de eficiencia paramétrica (k= 8 en este caso) se obtiene un aumento considerable en el volumen del dataset recuperado sin incurrir en mucho ruido; se obtiene un dataset 5,32 veces mas grande con una pérdida de precisión del 3,5 %. Además, se explora la idea de filtrar usuarios ruidosos a posteriori y se observa que, simplemente al eliminar dos usuarios particularmente famosos y ruidosos, se obtiene un incremento considerable en la precisión. Como trabajo futuro, una línea de mejora interesante sería la consideración del uso de otros tipos de relaciones adicionales para la fase de construcción del grafo. Otra línea de mejora sería la de idear ciertas modificaciones sobre el algoritmo de relevancia PageRank que pueden ser útiles para el cálculo de relevancia dentro de este contexto. Otra vía de trabajo sería la de abordar la subtarea de filtrado de forma explícita, probablemente realizando análisis sobre el contenido como complemento al análisis estructural actual, aunque el proceso de analizar el texto de un tweet es una tarea por sí misma. Capítulo 3 Normalización de tweets Como ya sabemos, Twitter es una red social de éxito generalizado, donde millones de personas expresan ideas continuamente sobre cualquier tema, siendo una gran fuente de información. Sin embargo, la mayoría de los tweets suelen estar redactados con prisa, sin revisión y con un alto grado de abreviación, convirtiéndolos en textos nada apropiados para el procesamiento de lenguaje natural tradicional. En este capítulo se aborda este fenómeno de forma directa, generando una caracterización de los problemas textuales encontrados y proponiendo un sistema para mejorar la calidad textual de estos tweets. Este sistema propuesto es de naturaleza extensible y modular, siendo fácil de ampliar y requiriendo poco esfuerzo manual tanto para configurarlo inicialmente como para adaptarlo a otros contextos. 3.1. Introducción Uno de los desafíos mas importantes que afrontamos hoy en día consiste en determinar cómo procesar y analizar la enorme cantidad de información que se puede extraer de Internet, especialmente de sitios que son redes sociales como Twitter, donde millones de personas expresan ideas y opiniones diariamente sobre una enorme variedad de temas distintos. Los textos escritos en Twitter, se caracterizan por tener una corta longitud (140 caracteres como máximo), siendo textos muy pequeños en comparación con el tamaño de los textos en géneros más tradicionales. Además, la mayor parte de estos tweets se escriben desde dispositivos móviles tales como smartphones o tablets, siendo escritos con prisa (incluso ciertos usuarios escriben casi en tiempo real, como si se tratara de un sistema de mensajería instanánea) y sin ningún tipo de revisión antes del envío, claramente favoreciendo la velocidad a expensas de la calidad y exactitud de la redacción. Consecuentemente, los usuarios de este tipo de redes han desarrollado una nueva forma de expresión que incluye el uso generalizado de abreviaturas similares a las usadas en los SMS, variantes léxicas, repetición o ausencia intencional de caracteres y uso de emoticonos, amén de otras técnicas. Pero los fenómenos mencionados anteriormente provocan una serie de dificultades inherentes al procesado de estos textos usando análisis NLP tradicional. 29 36 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS Módulos de expresiones regulares: Estos módulos son colecciones independientes de expresiones regulares que se encargan de proponer candidatos de corrección a patrones muy recurrentes como emoticonos, algunas onomatopeyas, ciertas abreviaturas y/o errores muy frecuentes. Cada uno de estos módulos propone una única solución para cada caso. Módulos unipalabra: Cada módulo perteneciente a esta clase usa un recurso léxico propio de palabras simples y un conjunto de medidas de distancias de edicion con el fin de encontrar candidatos similares al token OOV. Las distancias usadas son la distancia de edición tradicional, de similitud fonológica y de distancia física en un teclado. Módulos multipalabra: Estos módulos parten de la información proporcionada por el resto de módulos y toman una decisión basada en el contexto de la OOV. En concreto, los autores utilizan tres módulos: un módulo con un diccionario multipalabra, un módulo con un etiquetador POS y un módulo que analiza las palabras concatenadas. Estos módulos actúan secuencialmente, cada uno utilizando información adicional para complementar, filtrar o descartar candidatos propuestos por el resto de módulos. Los autores han utilizado FreeLing como framework para implementar los módulos y como herramienta de preprocesado y tokenizado. Además, utilizan el toolkit FOMA (Hulden, 2009) para realizar búsquedas aproximadas eficientes sobre los diferentes recursos utilizados por cada módulo. Cada módulo posee un conjunto de recursos léxicos específico. Los módulos de expresiones regulares utilizan un lista de acrónimos conocidos y abreviaturas comunmente usadas en tweets, una lista de emoticonos y una lista de onomatopeyas extraidas del DRAE. Los módulos unipalabra utilizan un diccionario propio del lenguaje español, un diccionario propio del lenguaje inglés, un diccionario de variantes morfológicas generadas a partir del diccionario español, una lista de nombres propios que incluye algunos diminutivos y un diccionario de entidades unipalabra tales como localizaciones, organizaciones, personas, canales de televisión, programas, productos y otros medios de comunicación. Para los módulos multipalabra, sólo se ha generado un diccionario de entidades multipalabra, el cual es de naturaleza similar al diccionario de entidades unipalabra pero con la diferencia que los términos de las entidades son exclusivamente multipalabra. El método de normalización propuesto consiste en obtener una primera tanda de candidatos mediante los módulos de expresiones regulares y unipalabra, refinar dicha tanda con los módulos multipalabra y aplicar un esquema de votación simple para seleccionar el mejor candidato. La figura 3.4 muestra a la arquitectura general del sistema de normalización propuesto y su funcionamien- to. 3.3. Caracterización del problema Para caracterizar el problema y evaluar el sistema de normalización propuesto en este capítulo se ha utilizado un dataset compuesto por 3.1 millones de 3.3. CARACTERIZACIÓN DEL PROBLEMA 37 Figura 3.4: Funcionamiento del sistema de normalización propuesto en Ageno et al. (2013) tweets escritos en español que están altamente relacionados con el Campeonato Europeo de Fútbol de la UEFA 2012, coloquialmente llamado Eurocopa 2012 o Euro2012. El dataset ha sido generado usando el proceso dinámico de recuperación de tweets descrito inicialmente en la obra Cotelo et al. (2014) y revisado en el capítulo 2. Este dataset es muy útil debido a que contiene una gran cantidad de tweets en español que exhiben los típicos problemas de calidad y redacción que hemos mencionado anteriormente. Como dato adicional, este dataset ya había sido recolectado y analizado para la evaluación del método de recuperación descrito en el capítulo 2, por lo que no había necesidad de realizar otro proceso de recuperación si los datos pueden ser reutilizados con otro fin. Como paso inicial al esfuerzo realizado en este capítulo, se ha llevado a cabo un análisis sobre la distribución de términos de nuestro dataset, utilizando varios vocabularios como fuente de conocimiento existente para la determinación de términos válidos. La tabla 3.1 y la figura 3.5 representan los resultados de dicho análisis, mostrando que sólo 68,76 % de los términos encontrados fueron reconocidos dentro del vocabulario común del lenguaje español, denominando esta proporción como Language IV (In-Vocabulary o dentro del vocabulario del Lenguaje). Una parte significativa de los términos no pertenecientes al vocabulario del lenguaje español fueron OOV mientras que el resto de términos detectados pertenecían a un vocabulario de propósito especifico (Specific IV ) o algo distinto a lo que comúnmente consideramos una palabra (fechas, hashtags, menciones, numerales, etc). Antes de realizar ningún proceso de normalización, se procedió a realizar una caracterización de los fenómenos de errores existentes causantes de los términos OOV. Como no es viable realizar este tipo de caracterización sobre los 3.1 millones del dataset original, se obtuvo una muestra estadísticamente significativa del dataset (α= 0,05, error = 1 %) compuesta por tweets que tuvieran al menos un término OOV. Cada uno de estos tweets fue analizado manualmente, siendo 38 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS Tipo Detección Descripción Language IV 68,76 % Términos validos encontrados en el vocabulario común del lenguaje español Rest 31,24 % Términos no encontrados en el vocabulario común del lenguaje español OOV 28,82 % Términos no encontrados en ningún otro recurso Specific IV 15,82 % Términos validos encontrados en algún recurso de propósito específico (género, dominio, etc. . . ) REGEX 53,33 % Términos válidos reconocidos mediante expresiones regulares (menciones, hashtags, fechas, etc. ..) Cuadro 3.1: Distribución de términos detectados en el dataset Figura 3.5: Distribución de términos detectados en el dataset cada término OOV etiquetado indicando el fenómeno de error asociado y su forma correcta. Se dieron algunos casos de fenómenos múltiples en una misma OOV. Esta muestra manualmente anotada se usa como dataset de evaluación durante todo el proceso de experimentación. La caracterización de los diferentes fenómenos de error da lugar a las siguientes categorías: Errores comunes de ortografía (ORT): segmentación de palabras incorrecta, ausencia o mal uso de acentuación, uso incorrecto de las mayúsculas y faltas de ortografía más comunes. 3.4. ARQUITECTURA DEL SISTEMA PROPUESTO 39 Lenguaje móvil (TXT): acrónimos adhoc, abreviaturas, omisión de letras, omisión de elementos morfosintácticos, uso de logogramas y pictogramas. Confusión homofónica (HOMO): cambios fonológicos comunes y otras variantes de escritura de origen fonológico. Onomatopeyas no identificadas (ONO): onomatopeyas muy poco frecuentes o variantes de onomatopeyas que no son fácilmente reconocibles. Repetición de caracteres (REP): repetición innecesaria de caracteres, utilizada normalmente para enfatizar. Arte ASCII (ASC): Uso especial y creativo de los caracteres disponibles para reflejar situaciones, emociones, estados de ánimo o para expresar cualquier otro tipo de comunicación no verbal e incluso con fines puramente estéticos. Flexiones y variantes libres: Variantes de escritura aceptadas normalmente vinculadas a una región o colectivo específico. No es un fenómeno de error en el sentido estricto de la palabra, pero a efectos del proceso de detección, son considerados a priori como términos OOV. Términos foráneos (FT): Términos de origen extranjero, provenientes de otros idiomas, que no tienen por qué ser aceptados en el contexto del lenguaje español. La tabla 3.2 ilustra esta caracterización y proporciona varios ejemplos para cada fenómeno. Se observa que la mayoría de los errores que se pueden encontrar encajan en alguna de las grandes categorías de error descritas anteriormente, estando claramente relacionados con el estilo de escritura rápido e informal asociado a Twitter, comúnmente propiciado por la escritura usando un dispositivo móvil. 3.4. Arquitectura del sistema propuesto Las obras de normalización existentes están mayormente diseñadas para abordar un caso en concreto, siendo muy costoso adaptarlas para otro dominio o lenguaje. La aproximación que se propone y evalúa en este capítulo toma un camino diferente: un sistema que está específicamente enfocado en ser flexible, modular, tolerante ante problemas difíciles y con poca carga de trabajo manual, comparado con aproximaciones más tradicionales. En términos generales, todos los módulos del sistema hacen uso de uno o más elementos generales que componen el sistema: Recursos y fuentes de conocimiento: léxicos, corpus y cualquier otro tipo de recurso lingüístico, incluyendo recursos que contienen conocimien- to específico sobre el medio usado o el dominio abordado. Los recursos utilizados por el sistema se describen en la sección 3.5. Reglas: reglas para el manejo automático de fenómenos comúnmente encontrados en Twitter, como repetición excesiva de caracteres, acrónimos o errores de carácter homofónico. 40 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS Fenómeno Prop. Ejemplos Errores comunes de ortografía 27,51 % sacalo →sácalo, trapirar →transpirar, . . . Lenguaje móvil 07,92 % x2 →por dos, q →que, aro →claro, . . . Confusión homofónica 08,52 % kasa →casa, caxo →cacho, . . . Onomatopeyas no identificadas 05,96 % jajajajjajja →ja, jum →um, . . . Repetición de caracteres 15,25 % siiiiiiiii →si, quiiiiieeeeroooo →quiero, . . . Arte ASCII 13,80 % « ¤ oO._.Oo . . . Variantes libres 06,90 % gatino, besote, bonico, . . . Otros errores 06,73 % htt, asdfasdfasdf, . . . Términos foráneos 04,00 % flow, ftw, great, lol, . . . Fenómeno múltiple 03,41 % diass →días, artooo →rato, . . . Cuadro 3.2: Caracterización de los fenómenos de error encontrados en el dataset Análisis léxico: la distancia léxica tradicional permite a los analizadores abordar errores ortográficos comunes. El sistema analiza cada término a nivel léxico, determinando si son términos OOV o no, utilizando los recursos y técnicas disponibles. Si el sistema determina que el término en cuestión es OOV, éste genera un conjunto de candidatos de corrección y finalmente selecciona el mejor candidato de corrección para cada caso. La figura 3.6 muestra los componentes, cómo se interconectan y el flujo de procesado del sistema. Conceptualmente hablando, el sistema se divide en diferentes etapas: preprocesado,detección,generación de candidatos yselección de candidatos. Las etapas son abordadas en detalle a lo largo los apartados que vienen a continuación. 3.4.1. Preprocessado y detección Como ocurre en la mayoría de los sistemas de procesado existentes en el campo del NLP, el primer paso del sistema propuesto consiste en realizar un preprocesado sobre los textos en bruto. El módulo de preprocesado se encarga de realizar el tratamiento inicial típico en todo análisis léxico, generando un flujo de tokens para cada tweet, teniendo en cuenta términos especiales como constructos de Twitter (hashtags y nombres de usuario), numerales, fechas, elementos URL, emoticonos y algunos tipos de ordinales. El correcto tratamiento de estos elementos especiales es fundamental para que cualquier sistema de este tipo funcione correctamente. Además de lo descrito anteriormente, el módulo de preprocesado también se encarga de las tareas de tratamiento y limpieza relacionadas con la codificación de caracteres, corrigiendo caracteres mal codificados, descartando elementos 3.4. ARQUITECTURA DEL SISTEMA PROPUESTO 41 Figura 3.6: Arquitectura del sistema con sus diferentes etapas de procesado Unicode no estándar y normalizando todos los caracteres a una misma forma canónica. De lo contrario, el resto de las etapas tendrían problemas al realizar los correspondientes análisis a nivel de carácter. La siguiente etapa consiste en detectar, a grosso modo, la naturaleza de cada token resultante. El módulo de detección intenta determinar si un token es un término OOV o no, comprobando si pertenece a algún recurso externo (o fuente de conocimiento equivalente) o si se asemeja a construcciones conocidas como nombres de usuario, hashtags, fechas, numerales, direcciones URL, etc. Como recursos externos para la detección se usan un conjunto de léxicos, vocabularios y otro tipo de recursos textuales (ver sección 3.5, cada uno proporcionando formas conocidas y aceptadas en el lenguaje español y Twitter, incluyendo emoticonos, locuciones, variantes y coloqualismos. Para la detección de construcciones especiales, se usa una aproximación basada en reglas y expresiones regulares. Después de esta etapa de detección, cada token detectado como término OOV es llevado a la siguiente etapa de la cadena de procesado mientras que el resto simplemente se marcan con la naturaleza detectada en cuestión y son enviados al final de la cadena. 3.4.2. Generación de candidatos Después de que un token sea marcado como OOV, se envía al siguiente módulo de la cadena de procesado: el módulo generador de candidatos. Este módulo controla la etapa de generación de candidatos y está enlazado a varios 42 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS módulos analizadores que son los que realmente realizan el grueso del trabajo de la generación de candidatos. Dado un token detectado como OOV, el módulo de generación de candidatos ordena a cada analizador a realizar proceso de suposición del error, dando cada módulo su respuesta en forma de candidatos propuestos para corregir dicho token. El proceso subyacente específico varía dependiendo del analizador, cada uno especializándose en algún fenómeno de error en particular y haciendo uso de cualquier tipo de recurso externo para realizar esta labor. Cada módulo analizador provee algún tipo de mecanismo para generar puntuaciones básicas sobre los candidatos, indicando el grado de confianza otorgado por el analizador para cada corrección propuesta. La arquitectura modular permite tener un número arbitrario de analizadores distintos, otorgando total flexibilidad a la hora de diseñar el sistema en cuestión para cualquier contexto. Para esta obra en cuestión, se han implementado los siguientes módulos analizadores: El módulo Edit distance (distancia de edición) tiene un funcionamiento muy similar al esquema de sugerencias basado en distancias de edición, una técnica muy utilizada en la mayoría de los correctores ortográficos, aunque una de las mayores diferencias es que está diseñado para tener en cuenta múltiples léxicos y vocabularios en lugar de uno solo. Este módulo es el más general del sistema, abordando los fenómenos de error más comunes, siendo el analizador que trata los errores ortográficos comunes (ORT) mucho mejor que ningún otro módulo implementado. La distancia entre cadenas de caracteres utilizada es la distancia Damerau-Levenshtein (Damerau, 1964; Levenshtein, 1966) la cual, dadas dos cadenas cualesquiera, expresa el número de operaciones léxicas de caracteres (inserción, eliminación, substitución o transposición adyacente) que transformaría una cadena en la otra. Por ejemplo, la distancia Damerau-Levenshtein entre las palabras puerta yperro es 3: una operación de eliminación y dos operaciones de substitución. Para la implementación del módulo se basa en el uso varios léxicos y autómatas de Levenshtein autómata (Schulz and Mihov, 2002). Los valores de confianza asignados a los candidatos generados se encuentran en el intervalo [1,3], siendo el valor de confianza inversamente proporcional a la distancia entre el candidato propuesto y el OOV; la idea es que un candidato es menos probable cuanto más mayor es su distancia respecto al OOV. El módulo analizador Tranformation rules (reglas de transformación) contiene una colección de reglas creadas manualmente por un experto. Estas reglas tienen como objetivo inyectar directamente conocimiento “humano experto” al sistema y cada una representa un tipo de error “bien definido”. Usando estas reglas, el módulo genera un conjunto de candidatos mediante la aplicación de reglas cuyo patrón coincide con el token OOV, realizando una transformación léxica sobre el token original de acuerdo a cada regla coincidente y generando de esta forma un candidato de corrección. Es técnicamente posible generar más de un candidato debido a múltiples coincidencias de patrón, pero la cantidad de casos normalmente se limita a unos pocos. Estas reglas están diseñadas para abordar fenómenos que el módulo de distancia de edición no es capaz de tratar correctamente tales como la Repetición de caracteres o el Lenguaje móvil. El proceso de creación de reglas se describe en profundidad en la sección 3.5 y la tabla 3.3 muestra algunos ejemplos de regla, usando el lenguaje de expresiones 3.4. ARQUITECTURA DEL SISTEMA PROPUESTO 43 regulares de Python1. Este módulo siempre asigna un valor máximo de confianza 3para los candidatos generados. Patrón Tr. Léxica Ejemplos Fenómeno ˆ[ck]n$ con kn →con Lenguaje Móvil cn →con x([aeiouáéíóú]) ch\1xaval →chaval Lenguaje Móvil coxe →coche ((\w)(\w))\1+(\2|\3)? \g<1> sisisisi →si Repetición caracteres nonono →no ˆt[qk]m+$ te quiero mucho tkm →te quiero mucho Lenguaje Móvil tqm →te quiero mucho Cuadro 3.3: Extracto de las reglas de transformación usadas en el sistema El módulo de detección Foreign language (lenguaje foráneo) es el encargado de identificar si el token OOV en cuestión pertenece a un lenguaje distinto del español y si el módulo detecta que ese token pertenece a otro lenguaje, se marca dicho token como termino foráneo. Merece la pena recalcar que el módulo no propone ningún tipo de candidato de corrección; términos que pertenecen a otros lenguajes deben ser marcados como tales pero no corregidos. El analizador utiliza un módulo de detección de lenguaje basado en trigramas implementado en Python 3 (Phi-Long, 2012) como motor de detección subyacente. Los valores de confianza asignados a los candidatos generados se hayan comprendidos en el intervalo [1,3] y el valor es directamente proporcional al valor de confianza proporcionado por el estimador del motor de detección subyacente. El módulo de detección de ASCII Art (arte ASCII) intenta identificar si un token OOV es algun tipo de arte ASCII, un emoticono no registrado o una variante de uno ya conocido. Funciona mediante la mezcla de varias expresiones regulares cuidadosamente generadas y una lista de emoticonos comunes. Este módulo se comporta de forma similar al módulo de detección de lenguaje foráneo en el sentido que sólo marca los tokens. Este módulo siempre asigna el valor máximo de confianza 3para los candidatos generados. Después de que los candidatos sean propuestos por los analizadores, el módulo de generación de candidatos realiza un paso de filtrado y validación, con la intención de eliminar candidatos incorrectos y/o duplicados, todo ello acorde a un conjunto de reglas de validación y recursos lingüísticos. Recapitulando, la etapa de generación de candidatos funciona de la siguiente manera: 1. Dado un token OOV, el módulo encargado del proceso general de generación de candidatos envía dicho token a los módulos analizadores. 2. Cada módulo analizador puede o no proponer uno o más candidatos como posibles correcciones para dicho token OOV. 3. El módulo del proceso general de generación de candidatos filtra y valida los candidatos propuestos por los módulos analizadores. 1Ver la documentación oficial The Python 3 Standard Library, módulo re, accesible desde https://docs.python.org/3/library/re.html 44 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS 4. El conjunto de candidatos resultante es enviado a la siguiente etapa de la cadena de procesado. 3.4.3. Selección del candidato y resumen del proceso completo Esta es la etapa final de la cadena de procesado donde, para cada token OOV, se elige la mejor corrección posible entre los candidatos propuestos. Para poder elegir el mejor candidato, se asigna un valor numérico a cada usando el módulo Candidate Scorer (puntuador de candidatos), generando puntuaciones mediante la normalización de los valores de confianza asignados a los candidatos. Después de esto, el módulo Candidate Selector (selector de candidatos) ordena la lista de candidatos por puntuación y elige el mejor, utilizando varios criterios en cascada para resolver empates: 1. Puntuación: Se elige el candidato con la mejor puntuación y en caso de empate se recurre al siguiente criterio. 2. Frecuencia dentro del corpus: Se elige el candidato cuya frecuencia de aparición dentro del corpus generado a partir del dataset. La mayoría de casos se resuelven en este criterio, pero si existen uno o mas candidatos con la misma frecuencia de aparición, se recurre al último criterio. 3. Frecuencia del fenómeno de errro asociado: Se elige el candidato cuyo fenómeno de error asociado sea el más frecuente. En el muy raro caso de que dos términos distintos de igual puntuación, tengan misma frecuencia dentro del corpus y resuelvan el mismo fenómeno, se escoge uno cualquiera. El flujo de trabajo del sistema completo puede ser resumido tal y como sigue: el sistema genera un flujo de tokens a partir de un tweet usando el módulo de preprocesado. Para cada token, se determina si es un token OOV o no usando el módulo de detección. Si el token es un token IV, no se realiza procesamiento posterior alguno debido a que ya se considera una forma válida. De lo contrario, si el token es un token OOV, el modulo de generación de candidatos crea una lista tentativa de candidatos mediante el uso de los analizadores previamente descritos. Como paso final, el módulo selector de candidatos elige el mejor candidato para la corrección del token usando las puntuaciones que le proporciona el módulo puntuador de candidatos. La tabla 3.4 muestra algunos ejemplos de salida del sistema, mostrando la corrección final propuesta por el sistema para cada uno de los tweets de entrada de ejemplo. Por motivos de claridad, sólo se muestra el texto final resultante, omitiendo toda información respecto a los tokens y a los candidatos. 3.5. Recursos utilizados Tal y como se ha mencionado anteriormente, para realizar el proceso de evaluación del sistema propuesto se ha considerado el evento Euro2012 como escenario de normalización. A lo largo de esta sección se describen el proceso y el coste de generación para cada uno de los recursos utilizados por el sistema para abordar el evento en cuestión. 3.5. RECURSOS UTILIZADOS 45 Tweet original Corrección propuesta RT @axestrella7: fds estupendo: Partidzo d España con mi amr. tqmmmmmm :) RT @axestrella7: Fin de semana estupendo: partidazo de España con mi amor. Te quiero mucho :) iiiiiiiker iiiiiker iiiiiiiker!!!! q crack *.* #VamosEspaña Íker Íker Íker! Qué crack *.* #VamosEspaña @SergioRamos ers un crack menudopenalty mas bien tirado demostrando q lo de la otra vez solo fue mala suerte @SergioRamos eres un crack menudo penalty mas bien tirado demostrando que lo de la otra vez sólo fue mala suerte Cuadro 3.4: Ejemplos de salida del sistema propuesto Previo al proceso de generación de recursos, se realizó un análisis sobre los textos para determinar el vocabulario utilizado en los mismos. Los resultados obtenidos inducen a la idea de que el vocabulario total puede dividirse en diferentes categorías conceptuales independientes entre sí y cada una de ellas dedicada a abordar un aspecto diferente del léxico usado en los textos. Los resultados llevan a identificar tres grandes categorías conceptuales: Language (lenguaje), Genre (género) and Domain (dominio). Los términos que pertenecen a la categoría Language (Lang de forma abreviada) son aquellos que pertenecen, en un sentido general y amplio, al lenguaje español, no siendo asociados a ningún contexto específico, medio de comunicaciones o dominio en particular. Las formas aceptadas que son usadas con mas frecuencia caen dentro de esta categoría. La categoría Genre está compuesta por términos cuyo uso está típicamente confinado al contexto de Twitter e Internet, siendo normalmente terminología específica o expresiones muy utilizadas por los usuarios de estos medios. La categoría Domain está compuesta por elementos comunes del domino en cuestión: entidades, términos futbolísticos y otros términos referentes al evento Euro2012 tales como nombres de jugadores, equipos o estadios donde se celebran los partidos. Como resultado directo de esta categorización conceptual, se han generado y utilizado varios léxicos especializados para las diferentes etapas de detección y análisis en el sistema propuesto. Teniendo en cuenta las categorías observadas, cada léxico se genera independientemente del resto y enfocándose en cubrir un aspecto específico, mejorando la flexibilidad y la facilidad de adaptación a otros contextos distintos que difieran en género y/o dominio. Todos estos recursos léxicos se componen de texto sin formato y cada línea es una entrada distinta. Acorde con los experimentos realizados, el sistema puede ser configurado desde cero para un nuevo escenario (combinación de lenguaje, género y dominio) mediante la inversión de aproximadamente 20 horas de esfuerzo manual. Una vez que este trabajo inicial se ha realizado, adaptar el sistema para otro domino distinto (cualquier dominio no relacionado con fútbol y el evento Euro2012) sólo requiere de generar el nuevo recurso del dominio en cuestión. La cantidad específica de tiempo requerida para generar este nuevo domino es muy dependiente del domino en cuestión. En algunos casos, como cabe esperar, este esfuerzo puede reducirse si se adaptan recursos ya existentes o si se hace uso de procedimientos automáticos para acelerar la tarea de construc- 52 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS yoritarios se posicionaron activamente respecto a la propuesta. El proceso de generación del dataset del aborto fue el mismo que el usado en para el dataset Euro2012: el método de recuperación dinámica descrito en Cotelo et al. (2014). Dado que el lenguaje y la plataforma permanecen siendo iguales, normalizar los tweets de este dataset sólo requirió de la generación de un nuevo recurso de dominio (Domain), reutilizando directamente los recursos y parámetros del experimento sobre el dataset Euro2012. Este nuevo recurso de dominio contiene los nombre de los políticos y ministros relevantes, términos específicos sobre el tema del aborto y otros términos directamente relacionados con el sistema legislativo español. Componer este recurso sólo costó una hora de esfuerzo manual, siendo un coste de adaptación muy bajo. Se procedió de manera muy similar a la hora de generar el dataset de evaluación: se obtuvo una muestra estadísticamente significativa del dataset aborto (α= 0,05, error = 1 %), cuyos tweets pertenecientes a la muestra debían tener al menos un término identificado como OOV. Este dataset de evaluación fue anotado manualmente de la misma forma que para el experimento Euro2012. Fenómeno Selection Precision Candidate Coverage Total Accuracy ASC 76,67 % 100,00 % 76,67 % HOMO 95,45 % 95,65 % 91,30 % ORT 87,50 % 87,13 % 76,24 % REP 100,00 % 100,00 % 100,00 % TXT 96,63 % 94,98 % 86,96 % Total 94,40 % 91,81 % 82,71 % Cuadro 3.9: Rendimiento del sistema sobre el dataset de evaluación del aborto. La tabla 3.9 muestra el rendimiento obtenido por el sistema (incluyendo un desglose por fenómeno) al configurarse para abordar un nuevo dominio. El rendimiento global obtenido por el sistema se encuentra dentro del mismo rango de valores obtenido por el experimento anterior, sólo existiendo una ligera mejora de rendimiento (+1,88 %) respecto al otro experimento. Esta diferencia puede ser atribuida a que la calidad de los tweets en el dataset aborto es mayor y que los fenómenos de error encontrados son ligeramente más fáciles de resolver. Se concluye que con un mínimo esfuerzo manual adicional (alrededor de 1 hora) para generar el recurso adicional, el sistema propuesto se adapta muy satisfactoriamente al nuevo dominio. 3.6.5. Ajustando la etapa de selección de candidatos En este apartado se realiza un análisis sobre la etapa de selección de candidatos de la cadena de procesado, el cual sienta la bases para una modificación de la actual etapa de selección. Esta modificación consiste en la inclusión de una sub-etapa de clasificación a posteriori que permite un refinado aún mayor de la etapa de selección de candidatos. Este refinamiento conlleva a un significante número de mejoras de rendimiento. La etapa de selección de candidatos, como se ha visto previamente en la 3.6. EVALUACIÓN DEL SISTEMA 53 sección 3.4, es directa y sencilla: consiste en generar un ranking sobre los candidatos usando los valores de confianza provistos por los módulos analizadores y seleccionar el candidato que mejor puntuación obtenga. El objetivo final de este paso es la correcta elección del candidato, siendo este la corrección correcta para el término OOV dado. Figura 3.9: Distribución de la posición de ranking del candidato correcto El rendimiento general de la etapa de selección de candidatos se estima mediante la medida Selection Precision definida con anterioridad en la sección de evaluación. Teniendo en cuenta la actual etapa de selección de candidatos, la medida simplemente cuenta el número de candidatos correctos que han sido colocados como primeros dentro del ranking. La figura 3.9 muestra la distribución de las posiciones donde el candidato correcto ha sido colocado dentro del ranking por el módulo de selección de candidatos. Es fácil observar que ésta distribución se asemeja a una distribución ley de potencias opower-law: la mayoría de los candidatos correctos se encuentran entre las primeras posiciones del ranking seguidos de una cola larga. Como consecuencia de este tipo de distribuciones, teniendo en cuenta sólo los primeros n= 5 posiciones del ranking, más del 95 % de los candidatos correctos son cubiertos. Candidatos considerados Cota superior Selection Precision Cota superior Accuracy Posición p∈[1,3] 93,60 % 85,78 % Posición p∈[1,5] 95,28 % 87,33 % Todos 100,00 % 91,65 % Cuadro 3.10: Rendimiento maximal teórico para un proceso de candidato de selección perfecto 54 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS La tabla 3.10 muestra los valores maximales de rendimiento teóricamente alcanzables si el proceso de selección de candidatos fuera totalmente perfecto. Observando los valores, se infiere que al incluir un hipotético proceso que genere un reranking preciso sobre las primeras posiciones del ranking original, se aumentaría el rendimiento total del sistema. Figura 3.10: Inclusión de la etapa de clasificación a posteriori a la etapa de selección del sistema propuesto Teniendo en cuenta estos resultados, se propone una variante del proceso de selección de candidatos original que consiste en incluir un proceso auxiliar basado en clasificadores. Esta extensión ajusta y afina el proceso de selección, sugiriendo rerankings de los primeros nelementos del ranking basado en puntuaciones original. La figura 3.10 muestra cómo la extensión se incluiría dentro del proceso de selección original, modificando la arquitectura del sistema. Para el proceso clasificador de la extension, se ha elegido un clasificador Random Forest. Este clasificador consiste en un meta-estimador que entrena independientemente un número finito de árboles de decisión sobre subconjuntos de los datos de entrenamiento, suavizando los resultados, mejorando la capacidad predictiva y reduciendo el sobreajuste. Esta etapa de clasificación a posteriori intenta maximizar el rendimiento del proceso de selección de candidatos del sistema, aumentando los resultados de la medida Selection Precision. Si nos basamos en los datos experimentales discutidos anteriormente, se observa que es más que adecuado el considerar sólo los n= 5 primeros candidatos para este proceso. La tabla 3.11 y la figura 3.11 muestran el rendimiento del sistema con la extensión propuesta. Se ha utilizado un esquema de validación cruzada con k= 10 durante el proceso de evaluación del clasificador para evitar el sobreajuste. Al introducir esta extensión en la etapa de selección, se observa un incremento significativo en el rendimiento total del sistema, debido a que esta extensión 3.7. CONCLUSIONES Y TRABAJO FUTURO 55 Figura 3.11: Rendimiento del sistema con una etapa de clasificación a posteriori Módulos activos Candidate Coverage Selection Precision Accuracy Lang, GD, Transformation Rules (TR) 70,48 % 90,13 % 63,52 % Todos (Full system) 91,65 % 88,20 % 80,83 % Todos + Clasificador 91,65 % 89,21 % 81,76 % Todos + Clasificador + Reducción Características 91,65 %90,39 %82,84 % Cuadro 3.11: Comparativa de rendimiento incluyendo la extensión propuesta realmente refina el ranking propuesto inicialmente por el módulo. Si se realiza un proceso automático de reducción de características, el sistema consigue un incremento de rendimiento en la selección de candidato del 88,20 % al 90,39 %, que resulta en una mejora total del sistema pasando del 80,83 % al 82,84 %. Esta mejora es bastante significativa; es muy difícil superar la barrera del 90 % en la medida de Selection Precision debido a la dificultad de la tarea en sí a estos niveles de rendimiento. 3.7. Conclusiones y trabajo futuro A lo largo de este capítulo se ha presentado una novedosa aproximación modular basada en recursos para abordar la tarea de la normalización léxica de tweets. La principal idea detrás de esta aproximación consiste en que el sistema diseñado en cuestión se comporte como un “grupo de expertos”, logrando un sistema más tolerante con los errores difíciles y más sencillo de ampliar que las aproximaciones encontradas comúnmente en la literatura, las cuales recurren a sólo una técnica específica para resolver el problema. 56 CAPÍTULO 3. NORMALIZACIÓN DE TWEETS El sistema propuesto en cuestión posee una arquitectura extensible compuesta por módulos independientes, cada uno de ellos enfocado a una tarea específica o un fenómeno de error en concreto. Esta capacidad de especialización permite rebajar lo costes para hacer cualquier módulo a la vez que se incrementa la eficacia del sistema. Además, expandir el sistema para abordar otros fenómenos de error distintos sólo requiere la adición de módulos específicamente construidos para resolver dicho fenómeno. Esta combinación de arquitectura modular y de recursos de carácter ligero hace que esta aproximación sea muy fácil de adaptar a otros dominios, géneros u otros escenarios a muy bajo coste de implementación adicional. Una vez que el sistema está implementado para algún lenguaje en concreto, los costes de adaptación son muy reducidos; en nuestro caso, una vez creado los recursos de lenguaje, sólo costó 4 horas de trabajo manual generar los recursos para que abordara el género y el dominio en cuestión. Se ha mostrado que al aumentar el número de módulos de análisis especializados en el sistema, este experimenta un incremento global sobre el rendimiento a expensas de introducir algo de ruido, causando que la etapa de selección de candidatos sea ligeramente más difícil. Para paliar este efecto, se propone una mejora sobre la etapa de selección de candidatos original consistente en la introducción de un clasificador automático para realizar un ajuste sobre los rankings obtenidos. Los resultados muestran que el uso de este proceso de clasificación a posteriori incrementa significativamente el rendimiento del sistema debido a un aumento de la precisión en la etapa de selección. Considerando la mejora mencionada, el rendimiento total del sistema es bastante significativo: obtiene más de del 82 % de accuracy comparado con el 31 % obtenido por el baseline. El sistema propuesto también posee ciertas desventajas. Tal y como se ha mencionado previamente, aumentar el número de módulos que participan en el sistema “pseudo-democratico” de generación de candidatos conlleva un aumento de ruido y dificulta el proceso de decisión. Aunque este ruido inducido es inherente a este tipo de esquema de funcionamiento e impone una vaga cota superior sobre el rendimiento del sistema, los módulos pueden ser diseñados para reducir el solapamiento en la medida de lo posible, generando menos ruido y causando una menor confusión. Como en toda aproximación léxica, un factor importante a tener en cuenta es el correcto diseño e implementación de la etapa de preprocesado. El procesado, tokenización y detección de OOV son actividades vitales que deben hacerse lo mejor posible para el correcto funcionamiento del sistema; todo el resto del sistema depende de la fase de preprocesado y detección. El sistema puede ser mejorado en varias direcciones. Actualmente se utilizan expresiones regulares para tokenizar y tratar los textos de los tweets. Incluir un módulo segmentador en la etapa de preprocesado resultaría en una mejor tokenización y, por ende, en una posible mejora del sistema. Cada token OOV se aborda y analiza a nivel léxico de forma independiente, no teniendo en cuenta el resto del tweet. Tanto la generación y la selección de candidatos podría beneficiarse mucho si dispusieran de cierta información contextual, permitiendo el descarte automático de candidatos que no serían factibles debido a restricciones de carácter morfosintáctico. Otra dirección de investigación interesante consiste en mejorar el sistema de puntuación de candidatos y utilizar mejores métodos de selección. En lugar de 3.7. CONCLUSIONES Y TRABAJO FUTURO 57 usar heurísticas ad-hoc para generar valores de confianza, los módulos podrían hacer uso de métodos de aprendizaje automático para establecer estos valores de confianza, haciendo que la etapa de selección sea más precisa y sencilla. Capítulo 4 Combinación de información textual y estructural aplicada a la categorización automática de tweets En este capítulo se explora la tarea de categorización de tweets, abordando específicamente la determinación de la opinión política de los usuarios dentro de su contexto político. Para ello, en lugar de confiar únicamente en el análisis del contenido textual de los tweets, tal y como lo hacen la mayoría de trabajos existentes, se extrae conocimiento complementario de la topología de la red social y se realiza un análisis de la información estructural provista por las relaciones entre tweets y usuarios. A lo largo del capítulo se realiza una discusión sobre el análisis de ambos tipos de contenido (textual y estructural), aplicando diferentes aproximaciones para obtener diferentes modelos y realizando una evaluación sobre ellos. También se discute la idea de integrar información de ambos aspectos de los tweets, combinando modelos provenientes de diferentes tipos de conocimiento mediante varios métodos. Después de la evaluación de estos métodos de combinación, en la cual se obtienen buenos resultados, se realiza una discusión sobre las principales ventajas e inconvenientes a tener en cuenta. 4.1. Introducción Categorizar mensajes de Twitter es una tarea interesante y valiosa. Como ya hemos comentado, en este capítulo se aborda la categorización de tweets, enfocada específicamente a la determinación de la opinión política de los tweets escritos dentro de un contexto político en particular. Una colección de tweets no solo contiene información textual, sino que también ofrece cierta información estructural debido a la relaciones existentes entre mensajes y usuarios, formando una red implícita. A lo largo de este capítulo se discute el análisis de ambos tipos de contenido, se aplican diferentes propuestas a cada tipo de contenido para generar modelos 59 60 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS de características y se proponen varios métodos para combinar con éxito modelos de características provenientes de diferentes tipos de información en el proceso de clasificación. En esta memoria de tesis se explora la tarea de categorización de tweets, la abordando determinación de la opinión política, específicamente dentro del contexto político español. Extraer conocimiento del contenido estructural de los tweet y generar un modelo de características válido no ha resultado trivial. En este caso, requirió de la generación de una representación basada en grafos e inferir las comunidades emergentes dentro de él para generar un modelo de características los suficientemente expresivo. La combinación de modelos extraídos provenientes de diferentes tipos de conocimiento (en este caso, modelos textuales con modelos estructurales) resultó ser bastante satisfactorio, obteniendo buenos resultados pero entrañando una serie de dificultades debido a que dichos modelos eran de naturaleza diferente. Para ello, se desarrolló una estrategia de combinación de Ensemble Learning que se llama Multiple Pipeline Stacked Generalization, diseñada específicamente para aprovecharse de la mezcla de modelos diferentes. Este capítulo está estructurado de la siguiente manera: En la sección 4.2 (Trabajos relacionados) se realiza una revisión del estado del arte actual relacionado con la temática del capítulo y se analizan algunos trabajos de mayor interés. En la sección 4.3 (Definición de la tarea), se define específicamente la tarea abordada en este trabajo y se realiza una caracterización del dataset en cuestión, describiéndose como se ha generado y las peculiaridades que posee. En la sección 4.4 (Extracción de conocimiento a partir del contenido textual), se aborda la extracción de conocimiento del contenido textual explícito de los tweets, estudiando la aplicación de modelos tales como el Bag-of-Words (BoW) y su problemática, proponiendo un proceso de selección automática de características para una mejora en el rendimiento ofrecido por este modelo. En la sección 4.5 (Extracción de conocimiento a partir del contenido estructural) se diserta sobre cómo extraer conocimiento útil sobre el información estructural de los tweets, explotando características topológicas de la subyacente red formada por los usuarios y los mensajes. Para ello, se realiza una aproximación de carácter topológico consistente en generar un grafo de amistad bipartito basado en la identificación de dos grandes tipos de usuarios (creadores de contenidos and consumidores de contenido). Tomando este grafo bipartito como base, se proponen dos modelos de características de comunidad diferentes, basados en el Louvain Method y la técnica Spectral Biclustering respectivamente. En la sección 4.6 (Estrategias de combinación de características), se combinan modelos tanto estructurales como textuales de tres formas distintas: mediante la combinación directa, usando la técnica Stacking Generalization y mediante una variación propia de esta técnica que se ha denominado Multiple Pipeline Stacked Generalization. Finalmente, en la sección 4.7 (Conclusiones y trabajo futuro), se resumen los esfuerzos realizados en este capítulo, se revisan los puntos principales del trabajo y se diserta sobre la importancia de la combinación de contenidos tanto textuales como estructurales para la categorización automática de tweets. 4.2. TRABAJOS RELACIONADOS 61 4.2. Trabajos relacionados Existen varios trabajos que tratan con la clasificación de tweets, especialmente dentro del área de Sentiment Analisys, tratando de determinar opiniones en el contenido subjetivo de muchos de los tweets. La mayoría de estos trabajos encaran la clasificación de polaridad, decidiendo si un tweet expresa una actitud u opinión positiva, negativa o neutral respecto a un tema en cuestión. Por ejemplo, en Babour and Khan (2014), la clasificación de polaridad se realiza mediante el uso de léxicones de polaridad (recursos que consisten en listas de palabras positivas y negativas) y posteriormente ajustando la polaridades obtenidas teniendo el cuenta el contexto semántico en que dichas palabras aparecen. En Al-Osaimi and Badruddin (2014), la falta de léxicones de polaridad del lenguaje árabe es paliada mediante el uso de emoticonos que aparecen en los tweets, construyendo un clasificador de polaridad usando estos emoticonos. Dicha idea se extrae directamente de la obra Pak and Paroubek (2010), donde la misma técnica es aplicada a un corpus de tweets pero escritos en inglés. En otros trabajos como Xie et al. (2014), los autores diseñan un sistema para generar resúmenes automáticos de las opiniones de un usuario de Twitter mediante la integración de varias opiniones, tanto negativas como positivas, expresadas por los usuarios respecto a diferentes temas. En todos estos trabajos, la clasificación del tweet es realizada únicamente en su contenido textual: la información estructural inherente a Twitter no es usada en ningún caso, como pudiera ser la relación o similitud entre tweets de diferentes usuarios o el uso común de etiquetas. 4.2.1. Clasificación de polaridad en política Varios autores han estado interesados en el estudio del comportamiento de los usuarios de Twitter en relación con el dominio de la política. En la obra Small (2011), se realiza un análisis sobre los hashtags usados dentro del contexto de la política canadiense, intentando distinguir los diferentes objetivos para los cuales dichos hastags son usados en este contexto. En Park (2013), se realizó un estudio sobre los diferentes tipos de usuarios existentes en Twitter, con el fin de caracterizar los, así llamados, líderes de opinión; estos líderes son bastante activos y tienden a buscar información, movilizar colectivos y expresar opiniones públicamente, ejerciendo una gran influencia dentro de la tendencia política de sus seguidores (idea que aplicaremos en nuestro trabajo, ver sección 4.5). En el trabajo Tumasjan et al. (2010), se usó el recurso LIWC2007 (Linguistic Inquiry and Word Count; Pennebaker Kahn et al. (2007)) para determinar características emocionales y cognitivas de los tweets en relación a las elecciones federales al parlamento nacional alemán en 2009. Los autores concluyen que existe una alta correlación entre los resultados obtenidos y métricas estadísticas poblacionales tales como concentración y participación. Incluso el mero número de tweets que mencionan a un candidato es un buen estimador de los resultados electorales. Los autores de la obra Barclay (2014) también intentan medir si existe alguna correlación entre la actividad en redes sociales (Twitter y Facebook) y los resultados de las elecciones presidenciales de los EEUU del 2012. Los autores realizaron manualmente una clasificación de polaridad de los ciudadanos sobre 68 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS 4.4.1. Modelo Bag-of-Words estándar El primer modelo de características propuesto en este paper es el conocido modelo Bag-of-Words (BoW). Este modelo simplifica cada documento representándolo como una bolsa o multiconjunto de las palabras que lo componen, ignorando cualquier regla gramatical u ordenación de las palabras pero teniendo en cuenta la multiplicidad de las palabras dentro del documento. Cuando los documentos de este modelo se representa vectorialmente, se asemeja a una representación de histograma. A pesar de su simplicidad, este modelo de características es ampliamente usado en diferentes aplicaciones las cuales requieren de un vector de características para entrenar clasificadores y los resultados obtenidos suelen ser adecuados. En el caso particular que se aborda, se considera que este modelo es aceptable debido a que la naturaleza del contenido textual de los tweets es breve y de muy baja complejidad gramatical. Se ha evaluado el rendimiento del modelo sin variante alguna como una primera aproximación a la tarea, incluyendo varios dummy baselines por motivos puramente comparativos. Estos dummy baselines no son modelos propiamente dichos, sino estrategias extremadamente simplistas de clasificación que intentan comprobar la sensatez de los resultados obtenidos. En este caso, se han implementado el estimadores aleatorios (tanto uniforme como estratificado) y el estimador que clasifica siempre como la clase mas frecuente. La tabla 4.2 muestra los valores de rendimiento de la métrica accuracy (exactitud completa) con validación cruzada respecto a las dos versiones de la tarea propuesta, usando para ello un clasificador Support Vector Machine (SVM) con búsqueda de hiperparámetros. Todo el proceso de validación cruzada se ha realizado estratificadamente con k= 10 folds o pliegues, preservando la proporción de clases en todos los pliegues y minimizando la posible asimetría de clases. Modelo de Características Problema Completo Problema Reducido Dummy Aleatorio uniforme 12,73 % 34,86 % Dummy Aleatorio estratificado 31,32 % 36,37 % Dummy Clase mas frecuente 46,13 % 51,24 % Bag-of-Words 61,97 % 68,36 % Cuadro 4.2: Exactitud con validación cruzada del modelo Bag-of-Words tradicional. A pesar de que el rendimiento del modelo BoW es bastante superior a los baselines presentados, los resultados no son demasiado buenos. El modelo BoW supera al estimador Dummy Clase mas frecuente en ≈+15 % para el problema completo y en ≈+17 % para el problema reducido, consiguiendo un éxito moderado (entre el 61 % y el 69 % de exactitud). 4.4. EXTRACCIÓN DE CONOCIMIENTO A PARTIR DEL CONTENIDO TEXTUAL 69 4.4.2. Modelo BoW con selección automática de características Una manera muy popular para mejorar el modelo BoW consiste en aplicar un esquema de ponderación TF-IDF a los documentos en formato vectorial, otorgando mayor relevancia a ciertas palabras y mejorando el rendimiento general del modelo. Debido a la naturaleza del contenido textual de los tweets, al aplicar el esquema de ponderación TF-IDF sólo se obtiene una moderada mejora de los resultados (obteniendo un 70,42 % en la tarea completa y un 77,45 % en la tarea reducida). Sin embargo, al probar otras técnicas para mejorar el modelo BoW se ha observado que el margen de mejora es mucho mayor que el ofrecido por el esquema TF-IDF. Esto se debe a que la coocurrencia a nivel de palabra dentro de los tweets es muy baja y la longitud de los tweets es demasiado pequeña en comparación al número de documentos existentes en el dataset. Cualquier sistema de ponderación basado en la distribución de palabras de los documentos esta sometida a esta limitación (siendo TF-IDF un ejemplo de este tipo de esquemas). Un análisis superficial sobre los datos vectoriales del modelo BoW revelan un problema importante que está asociado al contenido textual. La dimensionalidad proporcionada por el modelo BoW es demasiado elevada (≈3kcaracterísticas) mientras que el número de palabras/tweet es del orden de 10,41. Esto hace que la matriz de datos obtenida sea extremadamente dispersa, obteniendo una densidad de valores no nulos del ≈3.34 ×10−3y los clasificadores tengan muchas dificultades a la hora de entrenarse y, por consiguiente, obtienen un rendimiento pobre. Para paliar esta situación, se aplica un proceso de reducción de dimensionalidad sobre el modelo BoW. En términos generales, existen dos grandes familias de técnicas para abordar dicha reducción de dimensionalidad: basadas en dataset transformation y basadas en feature selection. Las basadas en Dataset transformation (Transformación del dataset) intentan reducir la dimensionalidad del modelo mediante transformaciones sobre el conjunto de datos, combinando dimensiones para lograr un menor número de ellas. Estas técnicas reducen el problema a uno de factorización matricial (PCA, Kernel PCA,SVD oNNMF) o realizan un proceso de Manifold Learning (LLE, LTSA,IsoMap,Spectral Embedding or MDS). Aproximaciones basadas en problemas de factorización matricial intentan explicar la máxima varianza posible utilizando el menor número de componentes independientes aunque tienden a ignorar cualquier otra información que no se puede observar mediante la covarianza. Este tipo de aproximaciones son muy útiles si el dataset puede interpretarse de forma efectiva como la mezcla de señales interdependientes o si existen conjuntos de características con una alta correlación y se pueden transformar en dimensiones independientes. Estas aproximaciones consiguieron resultados moderadamente satisfactorios, superando a la mejora obtenida mediante TF-IDF en el caso de la factorización mediante NNMF (obteniendo un 72,42 % en la tarea completa y un 78,91 % en la tarea reducida). Sin embargo, como veremos más adelante, las técnicas basadas en feature selection proporcionaron un rendimiento mucho mayor. Por otro lado, las aproximaciones basadas en Manifold Learning (o inferencia de variedades) realizan una reducción no lineal sobre el conjunto de datos, 70 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS basándose en que la dimensionalidad existente en el dataset es artificialmente alta. Cada técnica en particular funciona de forma diferente, pero la idea principal radica en construir una representación de baja dimensionalidad usando una función de coste encargada de que los datos transformados retengan parte de las propiedades locales observada de los datos originales de mayor dimensionalidad. Este tipo de técnicas son útiles cuando se observa que los datos poseen una estructura claramente no lineal y que existe cierto grado de relación (no necesariamente lineal) entre las diferentes dimensiones. Ahora bien, las aproximaciones basadas en inferencia de variedades no funcionaron correctamente sobre el modelo BoW; la mayoría de las aproximaciones obtuvieron resultados significativamente peores. Los mejores resultados se obtuvieron al aplicar IsoMap, consiguiendo un 57,45 % en la tarea completa y un 64,20 % en la tarea reducida. Estos resultados son claramente inferiores a los obtenidos mediante el modelo BoW sin transformar o modificar. Aunque las técnicas de transformación del dataset suelen funcionar bastante bien y mejorar el rendimiento general, no todas obtuvieron resultados satisfactorios. Aunque en el caso de las técnicas de factorización matricial, se obtuvieron rendimientos superiores al modelo BoW, los resultados obtenidos fueron significativamente inferiores en comparación a los obtenidos mediante las técnicas basdas en Feature Selection. Las técnicas basadas en Feature Selection (Selección de características) tienen una filosofía distinta, pues se basan en la suposición general de que los datos contienen características (dimensiones) que son redundantes o irrelevantes, provocando un claro perjuicio al proceso de clasificación. Estas técnicas encajan mejor con el modelo BoW pues, como hemos mencionado anteriormente, el alto grado de dispersión de los datos y el hecho de que muchas palabras no tienen por qué ser relevantes para la tarea hacen que muchas características no sean informativas. Existen una gran cantidad de técnicas de selección de características, aunque la mayoría recurren a la búsqueda en los espacios de características,métricas de filtrado ométodos embebidos. Para el caso explorado en este capítulo, se comprobó que los métodos embebidos funcionaron mucho mejor que el resto, siendo dignos de mención los métodos basados Norma L1 y las técnicas basadas en Árboles de Decisión. La selección de características basada en Norma L1 utilizan modelos lineales normalizados al espacio L1, dando lugar a soluciones dispersas con muchos coeficientes nulos. El proceso de selección consiste en elegir características con el mayor número de coeficientes no nulos. Sin embargo, los modelos lineales dependen mucho de los parámetros de regularización (parámetros que regulan la dispersión de los resultados) y no existe una regla o criterio general para elegir los mejores parámetros de regularización, haciendo que el proceso de selección de características sea muy sensible a la parametrización. Los árboles de decisión pueden calcular valores de importancia sobre las características (mediante el cómputo de la entropía o la impureza Gini), siendo estos valores de importancia muy útiles a la hora de descartar características irrelevantes. Bosques de árboles de decisión con un alto número de estimadores tienden a recuperar con mucho éxito el conjunto de características significativas y no exhiben los mismos problemas de parametrización que los métodos basados en la Norma L1, siendo muy estables a la hora de su uso. Finalmente, se definió un proceso de selección automática de característi- 4.5. EXTRACCIÓN DE CONOCIMIENTO A PARTIR DEL CONTENIDO ESTRUCTURAL 71 cas para transformar el modelo BoW, haciendo uso de un Bosque de árboles extremadamente aleatorizados con un gran número de estimadores. Este tipo de bosque es similar al Bosque de árboles aleatorizados tradicional pero difiere en la manera de elegir los umbrales para cada subconjunto de datos aleatorios: los umbrales se eligen al azar dentro del conjunto de características candidatas y se eligen los mejores en lugar de simplemente buscar las características mas discriminativas. Esta variación permite reducir aún mas la varianza del modelo interno. Modelo de Características Problema Completo Problema Reducido Dummy Clase mas frecuente 46,13 % 51,24 % Bag-of-Words 61,97 % 68,36 % BoW-AFS 77,37 % 88,38 % Cuadro 4.3: Exactitud con validación cruzada del modelo BoW con selección automática de características (AFS). La tabla 4.3 muestra los valores de la métrica accuracy cuando se aplica la selección automática de características (AFS) al modelo BoW original justo antes de ser usado para entrenar el clasificador SVM. Con este paso de selección automática de características, el modelo BoW experimenta una enorme mejora de rendimiento (≈desde un +15 % hasta un +20 % respecto al modelo BoW simple) en ambas versiones del problema, llegando hasta un 88 % de exactitud en la versión reducida del problema. Se observa que con este paso de selección de características, el modelo BoW consigue un buen rendimiento y es apropiado como modelo de características para la clasificación de tweets a partir de contenido textual. 4.5. Extracción de conocimiento a partir del contenido estructural La naturaleza estructural de los tweets es una fuente de conocimiento muy interesante y relevante, aunque este aspecto de los tweets es, con frecuencia, pasado por alto. Además, extraer conocimiento a partir de la información estructural encontrada en una colección de tweets es un proceso para nada trivial. A pesar del hecho de que existen constructos especiales dentro de los tweets que establecen algunas relaciones entre elementos, tales como las menciones de usuario o el uso explícito de hashtags, la red subyacente es muy rica y comple- ja, requiriendo de esfuerzo adicional y métodos específicos para abordar dicha complejidad. Para realizar la extracción de dicho conocimiento, se opta por extraer la información topológica de la red subyacente, usando para ello todo un proceso de transformación que parte de la colección de tweets original para generar una representación de grafo bipartito, en la cual los nodos son los usuarios de la red y las aristas sus relaciones de amistad directas. La figura 4.3 muestra, de forma esquemática, las diferentes etapas del proceso. Se parte de la colección de tweets, se genera un grafo de amistad, de éste 72 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS Figura 4.3: Esquema del proceso de extracción de conocimiento a partir del contenido estructural un grafo bipartito y, finalmente, una representación espectral de mayor utilidad que depende de la técnica utilizada en cuestión. Todo el proceso de generación hasta el punto del grafo bipartito se encuentra detallado en la sección 5.4.1. Dicho esto, se abordará el análisis de la información estructural extraída mediante dos aproximaciones diferentes pero claramente orientadas a interpretar la información topológica extraíble de una colección de tweets: una aproximación de granularidad gruesa basada en la aplicación de la bien conocida técnica Louvain method (Blondel et al., 2008) y otra aproximación de mayor poder expresivo basada en la aplicación de la técnica Spectral Biclustering (Kluger et al., 2003). La primera aproximación de carácter topológico consiste en generar un modelo de características mediante el modelo de comunidades extraído por el Método Louvain. En líneas generales, se genera un grafo de similaridad y de él se obtiene un modelo de comunidades mediante la aplicación de este método. El proceso de generación del modelo de comunidades mediante el método Louvain se encuentra detallado en la sección 5.4.2, explicando cómo se genera el grafo de similaridad, qué métrica se ha usado y qué criterios se han utilizado para el proceso del grafo bipartito. Usando este modelo de comunidad, se ha generado un modelo de características en el cual cada usuario se representa mediante un vector de afinidad sobre las comunidades resultantes. Para cada usuario que aparece en el dataset, se calcula la proporción de relaciones de amistad respecto a cada comunidad, obteniendo un vector cuya suma de valores es 1. En la tabla 4.4 se muestra la exactitud de esta aproximación topológica, además de los valores de exactitud para las demás aproximaciones. Se observa un ligero incremento en el rendimiento al aplicar una etapa de selección automática de características pero es muy difícil mejorar más este modelo con este tipo de técnicas debido al bajo número de características que son usadas. Es muy interesante que una aproximación estructural de este tipo adquiera este poder predictivo, considerando que este modelo ignora por completo lo que los usuarios expresan en sus tweets, realizando predicciones simplemente mediante la estructura de red. Análogamente al caso anterior, la segunda aproximación de carácter topológico consiste en generar un modelo de características mediante el modelo de 4.6. ESTRATEGIAS DE COMBINACIÓN DE CARACTERÍSTICAS 73 comunidades extraído por el Spectral Biclustering. Esta aproximación intenta paliar las deficiencias existentes en el modelo anterior, clasificando todos los nodos del grafo bipartito en conjunto, en lugar de hacerlo en diferido mediante un grafo de similaridad. A grandes rasgos, la técnica consiste en generar una representación matricial del grafo bipartito, calcular los biclusters (comunidades de nodos creadores y consumidores de contenido; ver apartado 5.4.3) y generar un modelo de características a partir de estos biclusters usando una métrica de relevancia intracluster. Para cada creador de contenido iy su bicluster más representativo bi, se calcula su peso intra-bicluster wi=Pj∈biMi,j |j∈bi|, siendo éste la proporción de seguidores directos dentro del mismo bicluster asignado al creador de contenido i. Estos pesos representan la relevancia de los distintos creadores de contenido dentro de la comunidad representada por su bicluster. Una vez generado el modelo con los pesos, para cada usuario que aparece en el dataset, se genera un modelo de características similar al usado en la aproximación anterior pero con una excepción: la medida de pertenencia a cada comunidad (bicluster) se hace mediante la suma de los pesos intra-cluster de los generadores de contenido que pertenecen a ese bicluster. Modelo de Características Problema Completo Problema Reducido Bag-of-Words 61,97 % 68,36 % Afinidad Comunidades 50,07 % 56,04 % Afinidad Comunidades-AFS 50,28 % 56,51 % Relevancia Biclustering 59,97 % 68,75 % Relevancia Biclustering-AFS 61,11 % 69,60 % Cuadro 4.4: Exactitud con validación cruzada de las aproximaciones basadas en topología de red En la tabla 4.4 se muestran los resultados obtenidos por este modelo de características usando el algoritmo de Spectral Biclustering para obtener las comunidades y la relevancia de los miembros dentro de esas comunidades. Esta aproximación funciona sustancialmente mejor que la aproximación estructural previa y obtiene resultados similar al modelo BoW, mostrando que la estructura de red subyacente es, por sí misma, muy útil. Merece la pena destacar que la etapa de selección automática de características también mejora ligeramente los resultados aunque al poseer un número reducido de características, el rendimien- to no puede mejorar mucho más, situación que comparte con la aproximación topológica anterior. 4.6. Estrategias de combinación de características En las secciones anteriores se han mostrado cómo se ha extraído conocimiento tanto del contenido estructural como del contenido textual de un tweet, 74 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS abordándose cada tipo de contenido de forma independiente y consiguiendo diferentes resultados. En esta sección se evalúa la idea de mezclar los mejores modelos de características provenientes de diferentes tipos de conocimiento, explorando varias formas de combinar dichos modelos para mejorar aún mas los resultados. 4.6.1. Combinación directa La primera estrategia probada consistió en la combinación directa de ambos modelos de características en un modelo de mayor tamaño. La operación de combinación utilizada fue simplemente la concatenación directa de ambos modelos resultando en otro modelo vectorial de características. Además, se ha aplicado una etapa de selección de características de dos formas: a priori, combinando modelos ya previamente reducidos, y a posteriori, reduciendo el conjunto de características final después de combinar ambos modelos originales. Modelo de Características Problema Completo Problema Reducido BoW-AFS 77,37 % 88,38 % Biclustering-AFS 61,11 % 69,60 % Combinación 64,79 % 71,98 % Combinación-AFS a posteriori 75,24 % 86,68 % Combinación-AFS a priori 77,40 % 89,07 % Cuadro 4.5: Exactitud con validación cruzada de la combinación directa de características La tabla 4.5 muestra los valores de rendimiento obtenidos por las diferentes versiones de combinación directa. Esta estrategia de combinación tiene dificultades para obtener mejores resultados en la mayoría de las variantes, siendo la variante con modelos pre-reducidos la única que obtiene resultados realmente significativos. En el problema reducido, el resultado obtenido por esta variante es superior y en la versión completa, el resultado es similar al mejor modelo individual. Se observa que los clasificadores suelen tener dificultades a la hora de abordar el modelo generado mediante concatenación directa. Los modelos de características incluidos representan diferentes tipos de conocimiento que confunden a los clasificadores pues estos modelos pueden presentar discrepancias al mismo nivel y estar en desacuerdo respecto a las clases inferidas. 4.6.2. Stacked Generalization El método de combinación directa usado en el apartado anterior no obtuvo muy buenos resultados y está claro que se necesitó de otros esquemas de combinación que fueran capaces de manejar datos de diferente naturaleza. Los métodos de Ensemble learning usan múltiples algoritmos de aprendizaje para obtener mejor rendimiento predictivo. Aunque existen varios de estos métodos que usan el mismo modelo de características y/o algoritmos, los métodos de Ensemble learning tienden a obtener muchos mejores resultados si existe 4.6. ESTRATEGIAS DE COMBINACIÓN DE CARACTERÍSTICAS 75 una diversidad significativa entre los modelos. Muchos métodos de Ensemble learning tienden a promocionar tal diversidad entre los modelos que combinan, pero los métodos que son interesante para este caso en cuestión son aquellos que permiten la combinación de diferentes modelos y algoritmos. El método Stacked generalization oStacking (Wolpert, 1992; Breiman, 1996) implica entrenar un meta-clasificador sobre las salidas o predicciones de varios otros clasificadores. La idea en cuestión radica en que el meta-clasificador aprende cómo de bien cada uno de los clasificadores son capaces de aprender los datos de entrenamiento. Modelo de Características Problema Completo Problema Reducido Combinación 64,79 % 71,98 % Combinación-AFS a priori 77,40 % 89,07 % Stacked Generalization 79,99 % 89,22 % Cuadro 4.6: Exactitud con validación cruzada del método Stacked Generalization La tabla 4.6 muestra la exactitud obtenida por el método de Stacked Generalization, mostrando que este método funciona significativamente mejor que estrategia de combinación directa utilizada en el apartado anterior. Experimentalmente, se determinó que el método funcionaba mejor cuando se combinaban el modelo BoW con AFS y el modelo de Spectral Biclustering sin AFS. 4.6.3. Multiple Pipeline Stacked Generalization En la sección anterior se observa que la técnica de Stacking es capaz de combinar con éxito modelos de características generados de fuentes muy diferentes. Sin embargo, los clasificadores individuales usados en la técnica exhiben los mismos problemas de aprendizaje que en la combinación directa, pues dichos clasificadores usan todo el modelo de características completo de forma muy similar a la combinación directa. Aunque el meta-clasificador hace lo posible para mitigar esta situación y logra cierto éxito en ello, se ha ideado una variación sobre la técnica de Stacking que intenta abordar específicamente esta problemática. El método en cuestión es llamado Multiple Pipeline Stacked Generalzation y es similar al Stacking tradicional pero es capaz de procesar cada modelo de características original en pipelines (flujos de procesado) independiente, en lugar de usar el conjunto de características completo en cada clasificador. Cada modelo de características es procesado de forma separada en cada pipeline, teniendo cada uno de ellos su propio conjunto de clasificadores individuales con sus parámetros, permitiendo potencialmente un mejor ajuste a cada modelo. Un resultado directo de este procesamiento independiente es que el modelo de nivel 1es significativamente mayor. Siendo Nclases, Mmodelos y Kmclasificadores por modelo de características m, el modelo de nivel 1tendrá |N| × Pi∈M|Ki|características, a diferencia del modelo de nivel 1de la técnica Stacking tradicional que tiene |N| × |K|características (|K|clasificadores independientes). El resto del proceso (etapa de aprendizaje en el meta-clasificador 76 CAPÍTULO 4. COMBINACIÓN DE INFORMACIÓN TEXTUAL Y ESTRUCTURAL APLICADA A LA CATEGORIZACIÓN AUTOMÁTICA DE TWEETS y evaluación) es idéntico al modelo tradicional. Cada pipeline de trabajo fue configurado usando los mejores clasificadores previamente probados en cada modelo de características por separado, teniendo en cuenta también las diferentes versiones del problema. Para la versión completa del problema, se observó experimentalmente que la combinación de SVM-C, Random Forests, Logistic Regression y Multinomial Naive Bayes funcionó bien para ambos modelos de características originales. Sin embargo, en la versión reducida del problema, la mejor combinación encontrada fue SVM-C, Random Forest y Logistic Regression para el modelo BoW, mientras que para el modelo de Spectral Biclsutering fue la combinación de SVM-C y Random Forest. Modelo de Características Problema Completo Problema Reducido Combinación-AFS a priori 77,35 % 89,07 % Stacked Generalization 79,99 % 89,22 % Multiple Pipeline Stacked Generalization 82,36 % 91,22 % Cuadro 4.7: Exactitud con validación cruzada de la variante propuesta Multiple Pipeline Stacked Generalization La tabla 4.7 muestra la exactitud de la variante propuesta Multiple Pipeline Stacked Generalization con los mismos modelos usados durante la evaluación de Stacked Generalization. Se observa que la variación propuesta obtiene un rendimiento significativamente mejor en ambas versiones del problema, siendo una manera mucho mas efectiva de combinar ambos modelos de características. 4.7. Conclusiones y trabajo futuro A lo largo de este capítulo, se ha propuesto una aproximación a la tarea de categorización de tweets dentro del contexto político, basada en la idea de combinar nos fuentes de conocimiento diferentes: el contenido textual de los tweets y la información estructural que la red social subyacente ofrece. Este enfoque difiere del tradicional enfoque sobre el contenido textual que se puede encontrar con frecuencia en la literatura actual. Partiendo de una colección de tweets generados usando el método de recuperación dinámica explicado en Cotelo et al. (2014) y expandido en el capítulo 2, se ha generado un dataset compuesto por 3000 tweets escritos en español que hacen referencia directa al gobierno actual (referente al periodo de la recolección del dataset) o su oposición, clasificando dichos tweets en opiniones Positiva, Negativa o Neutra respecto a cada partido, generando un total de nueve clases. La distribución de estas nueve clases de clasificación es bastante desequilibrada, por lo que se evalúa en paralelo una versión “reducida” del problema, en la cual simplemente se consideran las tres categorías mas frecuentes. Después de preprocesar y tokenizar los tweets, se ha generado un modelo de características basado en el bastante establecido modelo Bag-of-Words. A pesar de su simplicidad, obtiene un éxito moderado y supera a todos los baselines propuestos. Se observó que la aplicación de un esquema de ponderado TFIDF no mejora los resultados. Después de un análisis superficial, se observó 4.7. CONCLUSIONES Y TRABAJO FUTURO 77 que este modelo sufría problemas de dimensionalidad, por lo que se le aplicó una etapa de selección de características basada en el uso de Bosque de árboles extremadamente aleatorizados. Con esta reducción de características, el modelo BoW experimenta un considerable aumento en el rendimiento, convirtiendo este modelo inicial en uno ligeramente apropiado para la clasificación de tweets a través de información textual. El análisis de la información estructural posee un enfoque distinto al ser dicha información de muy distinta naturaleza. A partir de la idea de que los usuarios forman comunidades implícitas cuyos miembros tienden a compartir intereses comunes sin la necesidad de contacto directo, se ha ideado una estrategia basada en grafos para caracterizar dichos usuarios mediante el descubrimiento de estas comunidades implícitas. Se construye un grafo de amistad bipartito que es usado como base para la generación de dos modelos de características estructurales diferentes. Uno de los modelos estructurales se genera a partir de las comunidades detectadas usando el Louvain method sobre un grafo de similaridad construido a partir del grafo de amistad y usando la medida Dice como medida de similaridad. EL otro modelo se construye mediante la aplicación de la técnica Spectral Biclustering sobre la matriz de amistad transformada y calculando un modelo de comunidades difuso y mas complejo. Aunque ambas aproximaciones estructurales son interesantes, el modelo de características basado en la técnica de Spectral Biclustering es claramente superior; obtiene resultados similares al modelo BoW mientras que los valores de rendimiento obtenido a través de la estrategia basada en el Louvain method son claramente inferiores. Después de extraer conocimiento, se discute la idea de mezclar los mejores modelos de características extraídos de ambos tipos de contenido. Para mezclar estos modelos de características, se ha recurrido a métodos de combinación que, de alguna forma, son capaces de tratar con modelos de características provenientes de diferentes tipos de conocimiento. Se han probado tres esquemas de combinación diferentes: combinación directa, Stacked Generalization y una variante propia de Stacked Generalization llamada Multiple Pipeline Stacked Generalzation. Los resultados muestran que la variación propuesta funciona significativamente mejor que cualquier otro modelo de características independiente y esquema de combinación, siendo esta variación bastante efectiva a la hora de combinar modelos de características de diferentes tipos de contenido. Se puede concluir que mezclar tanto conocimiento textual como estructural es una buena aproximación para determinar la orientación política de los tweets. Extraer conocimiento y generar buenos modelos de características es mucho más difícil para el contenido estructural que para el contenido textual, y hacer uso de ambos modelos de características resultó ser nada trivial, pues la combinación directa de los modelos no se comportaba de manera correcta debido a que los modelos eran de diferente naturaleza. Mas aún, se debe tener un cuidado especial a la hora de combinar modelos de ambos tipos de contenido. La aproximación mixta propuesta trata estos problemas cuidadosamente y ha demostrado ser efectiva y significativa. 84 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING Figura 5.2: Funcionamiento del método iterativo de detección de comunidades OSLOM bilidad de observar, al menos, |C|elementos de L1en una lista cualquiera de tamaño |L2|. Las aristas cuya medida de similaridad se inferior a un valor umbral especirficado son descartadas. Después, se aplica el método OSLOM sobre el grafo de similaridad, obteniendo un clustering sobre las listas de usuarios, cada conjunto de listas de usuario siendo un tema de interés en potencia. Los autores realizan una batería de pruebas con redes tanto artificiales como reales, y aunque los resultados son bastante buenos en términos generales, el tiempo de computación del método es muy alto, creciendo prohibitivamente respecto al número de vértices a considerar para incluir o eliminar de un cluster. Este método no es, por sí solo, factible para redes grandes. Los autores exploran el usar el método OSLOM como refinamiento de una partición anterior, logrando así solventar parcialmente este problema para usar el método en redes grandes. Es obvio que el resultado final está bastante condicionado por la técnica inicial usada y en la experimentación mostrada, usan como punto de partida las particiones generadas por el método Louvain (Blondel et al., 2008). Como nota final, los propios autores mencionan que necesitan otro método para seleccionar los vertices en el proceso de análisis individual de clusters. 5.2.3. Modelos generativos La mayoría de las aproximaciones para la detección de comunidades se basan en aplicar alguna técnica de análisis de redes para generar un clustering, ya sea mediante clustering aglomerativo, particionado de corte mínimo, medidas de centralidad y métodos similares. Estos métodos, aunque consiguen buenos resultados en muchos casos, suelen realizar un particionado directo de las comunidades de usuarios y no tratan todos los enlaces de la red por igual, no haciendo distinción entre los tipos de 5.2. TRABAJOS RELACIONADOS 85 relaciones o diferentes interacciones en una red social. Esta situación es una de las principales motivaciones que tienen los autores de la obra Sachan et al. (2012), en la cual implementan un modelo bayesiano generativo llamado TUCM (Topic User Community Model), cuyo objeto es el de descubrir comunidades de usuarios latentes. Este modelo, que consiste en una variación del bien conocido modelo generativo usado para descubrir diferentes temáticas en un conjunto de textos escritos Latent Dirichlet Allocation (LDA) (Blei et al., 2002), parte de la suposición de que los usuarios que interactúan más frecuentemente entre sí tienden a pertenecer algún tipo de comunidad latente común aunque no sea explícita. Es más, el modelo intenta describir de forma conjunta a los usuarios y los temas explorados mediante los mensajes y sus diferentes tipos, permitiendo que un usuario pueda pertenecer a varias comunidades y estar interesado en diferentes temas, aunque no se determinan grados de pertenencia o interés respecto a las comunidades y los temas, respectivamente. La idea base radica en representar a los usuarios mediante las interacciones de dichos usuarios dentro de la red social, determinando que la distribución de interacciones de un usuario se representa como una mezcla aleatoria de las variables latentes de las comunidades. De forma general, el mensaje de un usuario viene determinado por dos elementos: la comunidad y la temática. Dado un usuario, la temática de la que quiere hablar y la comunidad asociada a la temática, la comunidad determina el tipo de interacción (tweet simple, retweet o respuesta) y la temática determina el conjunto de palabras usadas en ese mensaje. Figura 5.3: Representación gráfica del modelo TUCM La figura 5.3 muestra el proceso generativo completo incluyendo las variables latentes y parámetros. Es interesante destacar que, dado que el cómputo de las probabilidades exactas de las distribuciones posteriores sobre el conjunto completo de hiperparámetros es un problema intratable, los autores utilizando 86 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING inferencia aproximada usando un método basado en Gibbs sampling. La descripción completa del proceso generativo específico se encuentra en la obra original Sachan et al. (2012), pues describir cómo funciona un proceso bayesiano completo queda fuera del alcance de esta memoria de tesis. En la obra se determina que los resultados obtenidos por el modelo TUCM eran apropiados para abordar una red con capacidades de broadcast como Twitter y el rendimiento computacional de TUCM respecto a otros modelos similares es superior debido a que TUCM escala mucho mejor. Sin embargo, el modelo TUCM requiere de cierta parametrización muy dependiente del contexto, pues como en LDA, hay que establecer el número de comunidades y temas a priori. Esto implica que cada modelo generado no sólo es extremadamente dependiente de los datos sino de la interpretación del responsable del experimento, requiriendo de un buen juicio a la hora de determinar estos parámetros para poder obtener un rendimiento apropiado. 5.3. Definición de la tarea Una fuente de conocimiento interesante aparece una vez que se consideran los usuarios como elementos estructurales de una red en lugar de individuales de una red social. Estos usuarios establecen relaciones entre ellos, tanto explícitas como implícitas, dando lugar a la creación orgánica e implícita de grupos usuarios en las cuales los miembros del grupo comparten intereses comunes a pesar de que la mayoría de los usuarios del grupo no se conocen directamente o tienen algún tipo de contacto directo. A raíz de esta observación, podemos definir como comunidad a un grupo de usuarios cuyos miembros comparten intereses comúnes respecto a una temática, con independencia a la interacción directa entre sus miembros o el reconocimiento expreso de pertenencia a la comunidad por parte de los mismos. Detectar comunidades de usuarios dentro de una red dada es una tarea muy amplia. En este capítulo se aborda la tarea de detectar tales comunidades de usuarios dentro de la red Twitter, pero en lugar de extraer comunidades genéricas a gran escala, la detección se centra en detectar comunidades subyacentes respecto a un tema específico. Estas comunidades de granularidad fina son muy interesantes porque son capaces de revelar posturas respecto al tema abordado en cuestión y ayudan a identificar qué usuarios apoyan tales posturas. Para esta obra en cuestión, se analiza la situación política española mediante la detección de comunidades de usuarios españoles cuyos mensajes guarden relación con el contexto político español. Sin embargo, no nos es factible recuperar y analizar la red compuesta por el conjunto completo de usuarios españoles debido a restricciones de carácter técnico; el tamaño de la red sería enorme y Twitter limita la cantidad total de información recuperada. Por lo tanto, se opta por analizar una muestra de los tweets pertinentes usando un método de generación de consultas que proporciona una cobertura mayor en comparación a hacer consultas simples sobre el sistema que proporciona Twitter. Se construye una colección de tweets escritos en español durante la presentación del borrador final de las enmiendas a realizar sobre la ley que regula el aborto en España, conocida coloquialmente como Ley del Aborto. El periodo de la presentación en cuestión está comprendido entre el 20 de diciembre del 2013 y el 23 de diciembre del 2013. La reforma propuesta causó un gran impacto sobre 5.3. DEFINICIÓN DE LA TAREA 87 la población española y todos los partidos políticos mayoritarios se posicionaron de forma activa respecto a esta cuestión. El método en cuestión usado para recuperar estos tweets es método de recuperación dinámica explicado en Cotelo et al. (2014) y en el capítulo 2. Como ya se ha mencionado anteriormente, este método garantiza un alto volumen de tweets, introduce poco ruido y es capaz de reaccionar ante eventos imprevistos relacionados con la temática durante el periodo de recuperación de datos. Al igual que en otros países, y como se menciona en el capítulo 4, la situación política española se encontraba claramente dominada por un puñado de fuerzas políticas, en particular por dos partidos políticos mayoritarios: el conservador, liberal y cristiano demócrata Partido Popular (PP) y el social demócrata Partido Socialista Obrero Español (PSOE). Desde la transición española a la democracia, estos partidos son los únicos que han tomado gobierno en el país y se han seleccionado términos relacionados a esos partidos como conjunto semilla para el método de recuperación. Se han recuperado un total de 20251 tweets que involucran de forma directa a más de 180kusuarios. A partir de esta colección de tweets, se extraen los usuarios que aparecen directamente en el contenido de cualquier tweet, ya sea el autor o cualquier otro usuario mencionado en el tweet. En complemento a los usuarios que aparecen, se recopilan las listas de amigos directos (aquellos a quien siguen), obteniendo de forma efectiva sus vecinos más inmediatos. Partiendo de la lista conjunta de usuarios (autores y mencionados) y sus respectivos amigos, se compone un grafo de amistad directa con miles de nodos (usuarios) y millones de aristas (relaciones de amistad directa). Figura 5.4: Grafo de amistad directa generado a partir de la colección de tweets obtenida 88 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING En la figura 5.4 se muestra el grafo de amistad resultante, el cual contiene más de 500kusuarios y más de 1,1Mrelaciones de amistad. Por motivos de claridad, los nodos son visualmente escalados y coloreados por su grado de entrada (número de relaciones de amistad entrantes). Este grafo de amistad alberga usuarios que son de naturaleza muy variada; la mayoría de los usuarios son cuentas oficiales de medios de comunicación, gente políticamente activa, miembros oficiales de partidos políticos y gente corriente sin relación aparente con las organizaciones políticas, cubriendo la mayoría de los actores de contexto sociopolítico. Este grafo de amistad de carácter político es una buena fuente de partida para la detección de comunidades de interés en Twitter respecto a la situación política española y por ello, es usado como base para el resto del trabajo presentado en este capítulo. 5.4. Detección de comunidades usando Spectral Biclustering Identificar la estructura de comunidad subyacente que existe en una red de usuarios puede ser una tarea difícil y computacionalmente costosa. En esta sección se propone una aproximación basada en biclustering para detectar las comunidades de interés dentro de Twitter respecto a una temática específica. Figura 5.5: Esquema general del proceso de detección de comunidades. La figura 5.5 consiste en un esquema general sobre el proceso utilizado para la detección de comunidades, consistente en varios pasos: creación del un grafo de amistad directa a partir de los tweets, transformación del grafo de amistad a un grafo bipartito y aplicación de una técnica de detección de comunidades usando como recurso base dicho grafo bipartito. En primer lugar, se detalla el proceso de construcción del grafo bipartito que va a ser utilizado como fuente de conocimiento para las aproximaciones presentadas en esta sección. Este grafo bipartito expresa una ordenación topológica sobre los usuarios de gran interés y utilidad, y se construye a partir del grafo de amistad mencionado en la sección 5.3. En segundo lugar, antes de entrar en detalle sobre la aproximación propuesta basada en biclustering, se describe una aproximación bastante más convencional que es incluida y usada como punto de comparación exigente y de relevancia. Esta aproximación consiste en modelar la tarea en cuestión como un problema de Maximización de la Modularidad y aplicar el conocido Método Louvain 5.4. DETECCIÓN DE COMUNIDADES USANDO SPECTRAL BICLUSTERING 89 (Blondel et al., 2008). La inclusión de esta aproximación específica radica en que las técnicas de maximización de la modularidad son apropiadas para la detección y descubrimiento de comunidades a gran escala, siendo el Método Louvain indicado por su eficiencia para abordar redes de gran tamaño. En tercer lugar, se detalla la novedosa aproximación basada en biclustering para la extracción de la estructura de comunidad a partir del grafo de amistad mencionado anteriormente. La idea radica en modelar el proceso de detección de comunidades como una tarea de biclustering y hacer uso del algoritmo Spectral Biclustering (Kluger et al., 2003) para calcular los correspondientes biclusters, los cuales serán usados para componer las comunidades. 5.4.1. Creación del grafo bipartito Para lograr detectar comunidades implícitas y poder caracterizar a los usuarios a través de dichas comunidades, se ha desarrollado una aproximación basada en grafos. Esta aproximación se basa en la idea de que se puede establecer y calcular algún tipo de medida de similaridad entre los usuarios si se analizan sus relaciones de amistad, siendo este análisis la base para identificar las comunidades de usuarios que comparten intereses comunes. El primer paso consiste en la construcción de un grafo dirigido de amistad directa utilizando todos los usuarios que aparecen en la colección de tweets y sus respectivos amigos (usuarios a los cuales ellos siguen de forma directa). Este grafo resultante puede llegar a ser enorme y muy difícil de tratar computacionalmente hablando. El grafo de amistad utilizado a lo largo de este capítulo es el que se menciona al final de la sección 5.3. Sin embargo, muchos de los nodos (usuarios) sólo tienen una arista entrante y ninguna saliente, por lo que no aportan mucho al grafo en sí y se consideran nodos irrelevantes. Por lo tanto, este grafo de amistad en bruto es podado, eliminando nodos irrelevantes que posean un bajo número de aristas entrantes y ninguno saliente. En lugar de establecer el umbral manualmente, se ha elegido el valor correspondiente al percentil q= 95 sobre la distibución del número de aristas entrantes, determinando el grado de aristas entrantes para nodos sin aristas salientes debe encontrarse dentro del 5 % superior de la distribución. Este grafo de amistad podado posee dos tipos de usuarios: usuarios originales que son autores de algún tweet en el dataset original y los nuevos usuarios detectados a través de las relaciones de amistad existentes en la red. Después de un análisis superficial, se detecta que la mayoría de los usuarios originales son principalmente consumidores de contenido mientras que los nuevos usuarios detectados son, principalmente, generadores de contenido. Los nodos denominados generadores de contenido son elementos cuya función principal en la red es la de generar contenido potencialmente relevante y siendo, con frecuencia, fuentes de opinión politica . Estos usuarios corresponden normalmente a cuentas de medios de comunicación relevantes, usuarios políticamente activos y cuentas oficiales de los partidos políticos; estos usuarios suelen tener un gran número de seguidores, aunque no es una condición necesaria. Los consumidores de contenido forman el resto de los nodos de la red y estos usuarios “consumen” los contenidos ofrecidos por los generadores de contenido, recibiendo dicho contenido porque los consumidores siguen a dichos generadores. Es interesante ver que estos roles no son mutuamente excluyentes. A partir del grafo de amistad, se construye un grafo bipartito que exprese este 90 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING comportamiento de creadores y consumidores, teniendo en cuenta que algunos nodos pueden, potencialmente, tener ambos roles y poseer tanto aristas entrantes como salientes. Estos nodos que exhiben los dos roles son transformados a dos nodos distintos, cada uno de ellos teniendo solo aristas entrantes (creador de contenido) o aristas salientes (consumidor de contenido). Cualquier nodo que se encuentre aislado después del proceso de podado o del proceso de transformación a grafo bipartito, es descartado y eliminado del grafo. Figura 5.6: Grafo bipartito construido a partir del grafo de amistad directa. La figura 5.6 muestra el grafo bipartito resultante donde los nodos son coloreados por grado de entrada y distribuidos por su clase bipartita (los consumidores de contenido se distribuyen hacia a la derecha mientras que los creadores de contenido son distribuidos a la izquierda). 5.4.2. El Método Louvain: un baseline exigente La Modularidad (Newman and Girvan, 2004; Newman, 2006) es una función de recompensa o beneficio1diseñada para medir la calidad de una división de la red en comunidades en concreto. Una partición de la red con un alto grado de modularidad exhibe una red de interconexiones intra-comunidad muy densa y poca densidad de conexiones extra-comunitarias. En esencia, cualquier método de partición basado en modularidad intenta encontrar una partición de la red en comunidades que maximicen la función de modularidad a nivel global. No obstante, realizar una búsqueda de fuerza bruta sobre el espacio de todas las particiones posibles de una red es intratable para la mayoría de los casos excepto los más triviales, debido a que el espacio de búsqueda crece exponencialmente con el tamaño de la red; se trata de un problema NP-duro. Por lo tanto, 1Una función de recompensa puede verse como una función objetivo a maximizar en lugar de minimizar, como en una función de coste o pérdida 5.4. DETECCIÓN DE COMUNIDADES USANDO SPECTRAL BICLUSTERING 91 la mayoría de los algoritmos recurren a métodos de optimización aproximada para buscar una partición, haciendo uso de algoritmos como los algoritmos voraces, métodos quasi-Newton o métodos de optimización espectral, consiguiendo soluciones aproximadas al problema de maximización de la modularidad con diferentes grados de velocidad y precisión. Para este trabajo en concreto, se usa el popular Método Louvain (Blondel et al., 2008) para aproximar la función de modularidad. Este método iterativo optimiza la modularidad de las comunidades localmente hasta que no se consigue mejorar la modularidad global mediante perturbaciones del estado de la partición actual. Este método suele ser mejor que otros métodos en términos de tiempo de computación, lo cual permite el análisis de redes de gran tamaño en un tiempo razonable y consigue modelos muy precisos a la hora de abordar comunidades ad-hoc con una estructura de comunidades conocida. El siguiente paso consiste en generar una matriz de similaridad sobre los nodos creadores de contenidos a partir de la información del grafo bipartito. La idea radica en que dos nodos creadores de contenido son similares si tienen consumidores de contenido en común. Se ha elegido la medida Dice como una medida de similaridad apropiada para comparar nodos creadores mediante sus conjuntos de consumidores. Usando esta medida, se construye un grafo ponderado de similaridad entre los nodos creadores de contenido cuyo peso de las aristas es igual a la coeficiente Dice entre los conjuntos de nodos consumidores de contenido que siguen a dichos nodos creadores. Como detalle técnico, cualquier grafo de similaridad construido de esta forma es un grafo completo, significando que el grafo tiene n(n−1) 2aristas, no mostrando de forma evidente alguna característica de carácter topológico y la mayoría de los algoritmos de detección de comunidades pueden tener dificultades cuando son aplicados a los grafos completos. Mas aún, la mayoría de las aristas tendrán pesos nulos o valores muy cercanos a cero, indicando que los esos nodos poseen casi ninguna similaridad. Por ello, este grafo de similaridad ha sido procesado para revelar algún tipo de estructura oculta. Cualquier arista que represente un valor de similaridad bajo se considera como no informativa, así que se eliminan todas las aristas con un peso menor a cierto valor umbral especificado. Para este caso en concreto, se determinó que pesos inferiores a 0,35 indicaban una similaridad muy baja entre nodos creadores de contenido. Este umbral es considerado como apropiado pero no demasiado estricto, pues los valores de similaridad, al haber sido compuatados mediante la medida Dice, se encuentran en el rango de valores comprendido en el intervalo [0,1]. Al procesar este grafo de similaridad de la forma anteriormente descrita, el grafo resultante puede no seguir siendo un grafo conexo y las diferentes componentes conexas deben ser inspeccionadas individualmente aunque, en la mayoría de los casos, la componente conexa con el mayor número de nodos es la única relevante. Después de seleccionar las componentes conexas y elegir las relevantes, se ha aplicado el conocido método de detección de comunidades Louvain method (Blondel et al., 2008) al grafo de similaridad, asignando a cada nodo creador de contenido una comunidad en concreto. A los nodos consumidores de contenido se les asigna la comunidad en función de la proporción de relaciones de amistad respecto a cada comunidad de nodos creadores de contenidos. El método Louvain obtiene mejores resultados (tanto en tiempo como en 92 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING valor de categorías) respecto a métodos similares como los que se describen en las obras Clauset et al. (2004) y Wakita and Tsurumi (2007). En la obra Rotta and Noack (2011) se mejora el método Louvain con un proceso de refinamiento multinivel pero tiene como contrapartida que es significativamente más lento, restringiendo el tamaño de las redes a analizar. A pesar de todo lo expuesto, cualquier aproximación basada en la modularidad, sufre lo que se denomina límite de resolución y suelen dar resultados insatisfactorios cuando se quiere encontrar comunidades por debajo de cierta escala, dependiendo del tamaño total de la red. Por ello, estos métodos son precisos a la hora de detectar comunidades a gran escala (respecto a la red en concreto) pero no son apropiados para recuperar comunidades a menor escala. Dado que el enfoque de este trabajo consiste en la obtención de comunidades a gran escala de usuarios políticamente sesgados extraídos de una red de gran tamaño, se considera que el método Louvain es bastante apropiado para la obtención de este tipo de comunidades dentro de esta tesis. Merece la pena mencionar que esta aproximación (como muchas otras aproximaciones existentes) no considera que exista cierto solapamiento en las comunidades, mientras que realmente, muchos usuarios son capaces de exhibir rasgos políticos de diversas comunidades. 5.4.3. La aproximación propuesta basada en biclustering Aunque el Método Louvain, como se ha mencionado anteriormente, es bastante apropiado para revelar comunidades a gran escala dentro de redes de usuarios, se percibe que este método está más o menos limitado; es insuficiente para descubrir el conocimiento estructural subyacente. La mayor desventaja presentada por la aproximación anterior es que todo el análisis de comunidades se realiza en “diferido”, desacoplando de forma moderada los consumidores de contenido de los creadores de contenido en lugar de analizarlos de forma conjunta. Por ello, en este apartado, se propone una aproximación diferente para revelar la estructura de comunidades subyacente, abordando el análisis conjunto de ambos tipos de nodo mediante el modelado de la tarea como un problema de biclustering, una manera novedosa de abordar esta tarea si recurrimos a la literatura actual. El proceso de Biclustering, también llamado Co-clustering oclustering bimodal, es un proceso de minería de datos diseñado para realizar un clustering (o agrupamiento) simultaneo de filas y columnas de una matriz dada (Hartigan, 1972; Mirkin, 1998). Un bicluster es un subconjunto de la matriz original cuyas filas presentan un comportamiento similar respecto a sus columnas y viceversa. Sin embargo, la definición exacta de “comportamiento similar” depende del algoritmo de biclustering utilizado. Como requisito para aplicar cualquier técnica de biclustering sobre la tarea abordada en este capítulo, es necesario transformar la representación basada en grafo de los usuarios de la red a una representación matricial tradicional. A partir del grafo bipartito reducido mencionado en el apartado 5.4.1, se genera una matriz de amistad Mdonde Mi,j = 1 si y solo sí, el creador ies seguido por el consumidor j(o lo que es lo mismo, jtiene una relación de amistad directa con i). Esta matriz está lista para ser usada como entrada para cualquier técnica de biclustering y tiene el beneficio de que cualquier bicluster extraído 5.4. DETECCIÓN DE COMUNIDADES USANDO SPECTRAL BICLUSTERING 93 Figura 5.7: Matriz de amistad sin estructura obtenida del grafo bipartito. del proceso representa una comunidad entre usuarios (tanto creadores como consumidores) que exhiben comportamiento similar. La figura 5.7 muestra la matriz de amistad resultante lista para ser utilizada como entrada para cualquier técnica de biclustering. A priori, no se observa ningún patron o estructura en la matriz, pero tras aplicar la técnica de biclustering aparecerá dicha estructura subyacente, tal y como se observa en la figura 5.8. Existe una variedad de técnicas de biclustering, cada una de ellas con sus peculiaridades y su fundamento subyacente, pero describirlas a todas ellas queda fuera del alcance de esta tesis. El estudio Madeira and Oliveira (2004) es una buena fuente para el que esté interesado en saber más sobre técnicas de biclustering. Para el problema concreto abordado en esta tesis, se ha elegido el algoritmo Spectral Biclustering (Kluger et al., 2003) porque es capaz de generar un modelo de comunidades difuso que permite diferentes grados de pertenencia a diferentes biclusters en lugar de un típico modelo inyectivo. La técnica Spectral Biclustering se basa en la idea de que la matriz de datos posee una estructura tipo tablero de ajedrez oculta y las nfilas y mcolumnas pueden ser particionadas en n×mbiclusters. Cada fila pertenecerá a m biclsuters y cada columna a nbiclusters con diferentes grados de pertenencia. El algoritmo termina usando estos m×nbiclusters para calcular el bicluster más representativo para cada elemento fila y cada elemento columna. La figura 5.8 muestra una matriz de amistad cuyas filas y columnas han sido reordenadas después de aplicar el algoritmo de Spectral Biclustering. Tanto filas como columnas se han agrupado acorde a su bicluster más representativo y se han dibujado las líneas divisorias entre biclusters por motivos de claridad. En la figura se observa que la varianza en los datos dentro de cada bicluster es baja, indicando una alta correlación entre los creadores de contenido y los consumidores dentro de cada bicluster. La figura 5.9 muestra un grafo de similaridad de los nodos creadores de contenido extraidos del modelo generado a partir del grafo biparito y la aproximación de biclustering explicada en esta sección. Los nodos han sido escalados respecto al número de seguidores directos en el grafo bipartito y coloreados en función del bicluster más representativo al que pertenecen. La relevancia intra-cluster se 100 CAPÍTULO 5. DETECCIÓN DE COMUNIDADES DE INTERÉS MEDIANTE SPECTRAL BICLUSTERING colección de tweets, se ha generado una muy útil representación de la red de usuarios consistente en un grafo de amistad directo, cuyos usuarios han sido extraídos directa e indirectamente de la colección de datos recuperado. Este grafo de amistad directa sirve como base para la mayoría del análisis y proceso de evaluación. Para poder probar la propuesta de forma efectiva, se ha implementado otro método basado en la maximización de la modularidad como baseline exigente. Este tipo de aproximaciones obtienen buenos resultados a la hora de detectar comunidades a gran escala y sus requisitos computacionales son relativamente bajos, haciéndolos apropiados para el análisis de grafos de gran tamaño. De las técnicas de maximización de la modularidad disponibles, se ha optado por el conocido Método Louvain pues obtiene buenos resultados mientras que sus requisitos computacionales son mucho menores en comparación a otras técnicas. A través de métodos de evaluación tanto intrínsecos como extrínsecos, se observa que el modelo de comunidades generado por la aproximación basada en Spectral Biclustering es muy superior al generado por el baseline propuesto. No sólo funciona mejor, sino que proporciona mejores modelos que permiten comunidades solapadas, pertenencia difusa a comunidades, comunidades más pequeñas y proporciona información adicional sobre la relevancia intra-cluster de los miembros de una comunidad. A pesar de que la técnica de biclustering elegida es ligeramente más lenta que el Método Louvain, sus requisitos de memoria son similares y los resultados obtenidos son mucho mejores. Además de los métodos de evaluación propuestos, se realiza un análisis cualitativo de los usuarios políticamente relevantes mediante el uso del modelo de comunidades provisto por la aproximación de biclustering. Usando la información de relevancia intra-cluster del modelo, se pudo observar que el método era capaz de identificar y correctamente agrupar usuarios ordinarios que comparten la misma ideología política a pesar de que esos usuarios no han interactuado entre ellos y no profesan públicamente ningún tipo de afiliación política. Finalmente, se concluye que la propuesta se comporta con éxito, siendo capaz de abordar grandes redes que suelen ser abordadas por aproximaciones tradicionales de maximización de la modularidad mientras que obtiene mejores resultados y proporciona un modelo mucho más rico. Capítulo 6 Conclusiones Como se ha mencionado a lo largo de esta memoria de tesis, las redes sociales son un elemento que ha pasado de ser un simple servicio a formar parte fundamental de la vida de las personas, experimentando un enorme auge en los últimos años. La facilidad de creación de contenido por parte de los usuarios, la sencillez con la que éste es compartido de forma efectiva, la inmediatez de las plataformas y la simbiosis con los dispositivos móviles de nueva generación (smartphones), han introducido cambios muy importantes sobre cómo las personas interactúan entre sí. Este éxito generalizado por parte de las redes sociales mayoritarias, donde millones de personas opinan, comentan y comparten a diario ideas sobre cualquier tema, hace que las redes sociales sea un objetivo como fuente potencial de información a analizar. Dado que los mensajes generados por los usuarios, y en general contenidos de cualquier tipo, rara vez son objetivos, hace que la información potencial a extraer haya atraído la atención de un diversos sectores como un elemento lucrativo. Además de enfoques más obvios como campañas de marketing, análisis de la opinión pública, análisis de marcas o análisis de perfiles de usuarios, las empresas participan activamente dentro de estas redes, no sólo como elemento dinamizador, sino además como soporte técnico y atención al cliente. Sin embargo, la información que se puede encontrar en este tipo de redes difiere bastante en lo que respecta a los tipos de información que se encuentran tradicionalmente en la mayoría de contextos, requiriendo de un enfoque holístico a la hora de analizar los contenidos de las redes sociales; es necesario explorar tanto el análisis del contenido en sí como el papel que éste o su autor desempeña dentro de la red. En esta memoria de tesis, se recoge el proceso investigador realizado para enfrentarse a las diferentes facetas del análisis de mensajes en redes sociales, todo ello bajo el enfoque holísitco de integrar tanto el aspecto estructural de los contenidos y los usuarios como el contenido no estructurado de los mensajes. En primer lugar, se aborda la tarea de recuperación de los datos respecto a una temática, pues es imperativo generar datasets que estén los suficientemente enfocados a una temática dado que la variedad existente en las redes es prácticamente infinita. Un aspecto a tener en cuenta, que es independiente a la temática elegida, es que los mensajes suelen ser mal redactados y de baja calidad, por lo que una 101 102 CAPÍTULO 6. CONCLUSIONES de las tareas abordadas es la de normalizar, a nivel léxico, los mensajes. Esta normalización busca paliar la baja calidad que pueda existir en los mensajes, intentando restaurar sus contenidos para que sea más efectivo analizarlos. La clasificación de mensajes respecto a la opinión que contienen es otra de las tareas abordada que, además de ser interesante, tiene implicaciones adicionales a nivel socio-político muy relevantes. Siguiendo el tema central de la tesis, se aborda la tarea extrayendo modelos de ambos aspectos (estructurado y no estructurado) de los mensajes e integrándolos de forma efectiva usando un esquema de combinación diseñado para ello. Muy interrelacionado con la tarea anterior, se ha tratado la detección de comunidades implícitas de usuarios respecto a una temática en concreto. Revelar este tipo de comunidades de interés contrasta respecto al enfoque pormenorizado de la tarea de clasificación, pues la naturaleza de ésta es a mucha mayor escala. Ahora bien, a la hora de caracterizar los colectivos de usuarios respecto a intereses comunes, hay que tener en cuenta que muchos de esos usuarios no se conocen ni interactúan de ninguna forma entre sí, resultando en un enfoque muy interesante respecto a muchas tareas de análisis. Teniendo en cuenta lo expuesto anteriormente, las principales aportaciones contenidas en esta memoria de tesis son las siguientes: 1. El diseño de un método dinámico de recuperación de información respecto a una temática concreta sobre redes sociales, apropiada sobre una red social (Twitter) que presenta un comportamiento muy dinámico, pero que no ofrece herramientas lo suficientemente apropiadas para esta tarea. 2. Una caracterización de los fenómenos de error y peculiaridades encontrados en los mensajes recuperados de las redes sociales, principalmente de redacción pobre y escritos desde un dispositivo móvil. 3. Un sistema de normalización léxica altamente modular para restaurar la calidad de los mensajes recuperados. Este sistema combina diferentes componentes de normalización, es fácilmente extensible, su coste de implantación es bajo y tanto los recursos como los componentes son reutilizables. 4. Una metodología para categorizar mensajes de opinión de las redes sociales dentro del contexto específico, explorando aproximaciones basadas tanto en información estructurada como no estructurada y proponiendo un esquema de integración basado en Stacking para combinar modelos de características de diferente naturaleza. 5. Un método para resolver la tarea de descubrimiento y caracterización de las comunidades implícitas y ad-hoc de usuarios dentro de un contexto específico, usando un enfoque combinado de representación de grafo y Spectral Biclustering. Las diferentes aportaciones han sido un resultado directo del diseño e implementación de los experimentos detallados en esta memoria de tesis, los cuales han logrado validar las hipótesis iniciales presentadas en la sección 1.2. Aunque conclusiones de forma detallada e individual respecto a cada experimentos, han sido presentadas en sus respectivos capítulos, podemos destacar algunas de las conclusiones principales extraídas de los resultados obtenidos: 103 1. En la tarea de recuperación de mensajes, el análisis del grafo de términos subyacente construido a partir de la información estructurada existente en los mensajes es una técnica mucho mas versátil y proporciona mucha mas cobertura que usar simplemente una consulta estática de términos. Además, usando sólo un conjunto de términos semilla significativo y acotado, se consigue una recuperación de mensajes de gran volumen centrada en un tema representado por ese conjunto semilla, con poco ruido introducido y que responde a eventos inesperados en el tiempo. 2. Respecto a la normalización de mensajes ruidosos, se comprueba que, tendiendo en cuenta los fenómenos de error observados, la idea de utilizar componentes independientes que funcionan como “grupo de expertos” es una forma muy efectiva para abordar dichos mensajes ruidosos. Además, como resultado adicional de esta idea, la arquitectura modular resultante exhibe un alto grado de especialización en sus componentes, siendo esta especialización beneficiosa en términos de coste, extensibilidad y adaptación a otros dominios 3. La elaboración de un esquema de integración de modelos de características extraídos de información tanto estructurada como no estructurada es fundamental para la tarea de clasificación de opinión de mensajes generados por los usuarios. Usar sólo información no estructurada es ineficaz, ya que los textos de los mensajes carecen de la cantidad de contenido necesaria para las técnicas de PLN comunes. 4. La detección de comunidades de usuarios de interés en las redes sociales requiere de técnicas diferentes a las de clustering tradicional, pero con una representación de grafo usando la información estructurada de los mensajes y la técnica de Spectral Biclustering, se consiguen unos resultados muy satisfactorios; las comunidades comunidades de usuarios obtenidas a través de este procedimiento son muy acertadas, probando que la aproximación topológica mostrada es viable en grandes grafos y obtiene resultados muy fidedignos. A partir del desarrollo de la investigación expuesta en esta memoria de tesis, se han generado varios trabajos en forma de artículos de investigación. Los resultados publicados relacionados con la tarea de recuperación de información se encuentran en los trabajos Cotelo et al. (2012) y Cotelo et al. (2014), mientras que los resultados relacionados con la tarea de normalización se encuentran en los trabajos Cotelo et al. (2013) y Cotelo et al. (2015a). También se ha publicado el trabajo Cotelo et al. (2015c), el cual combina resultados provenientes de la recuperación de información y la clasificación de opinión en el contexto político español. Los resultados referentes a las tarea de clasificación de opinión y detección de comunidades se encuentran en las obras en proceso de revisión Cotelo et al. (2015b) y Cotelo et al. (2015d) respectivamente. Bibliografía Agarwal, A., Xie, B., Vovsha, I., Rambow, O., and Passonneau, R. (2011). Sentiment analysis of twitter data. In Proceedings of the Workshop on Languages in Social Media, pages 30–38. Association for Computational Linguistics. Ageno, A., Comas, P. R., Padró, L., and Turmo, J. (2013). The talp-upc approach to tweet-norm 2013. In Proceedings of the tweet normalization workshop at SEPLN 2013. Sociedad Española para el Procesamiento del Lenguaje Natural. Al-Osaimi, S. and Badruddin, K. M. (2014). Role of emotion icons in sentiment classification of arabic tweets. In Proceedings of the 6th International Conference on Management of Emergent Digital EcoSystems, pages 167–171. ACM. Babour, A. and Khan, J. I. (2014). Tweet sentiment analytics with context sensitive tone-word lexicon. In Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2014 IEEE/WIC/ACM International Joint Conferences on, volume 1, pages 392–399. IEEE. Barclay, F. P. (2014). Political opinion expressed in social media and election outcomes-us presidential elections2012. Journal on Media & Communications (JMC), 1(2). Berstel, J. and Boasson, L. (1979). Transductions and context-free languages. Ed. Teubner, pages 1–278. Berstel, J. and Reutenauer, C. (1988). Rational series and their languages, volume 12. Springer-Verlag Berlin. Blei, D. M., Ng, A. Y., and Jordan, M. I. (2002). Latent dirichlet allocation. Journal of Machine Learning Research, 3:2003. Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008. Breiman, L. (1996). Stacked regressions. Machine Learning, 24(1):49–64. Cao, G., Nie, J.-Y., Gao, J., and Robertson, S. (2008). Selecting good expansion terms for pseudo-relevance feedback. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’08, pages 243–250, New York, NY, USA. ACM. 105 Chen, Y., Amiri, H., Li, Z., and Chua, T.-S. (2013). Emerging topic detection for organizations from microblogs. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval, pages 43–52. ACM. Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Phys. Rev. E, 70:066111. Congosto, M. L., Fernández, M., and Egido, E. M. (2011). Twitter y política: Información, opinión y ¿predicción? Cuadernos de Comunicación Evoca, 4. Costa-Jussa, M. R. and Banchs, R. E. (2013). Automatic normalization of short texts by combining statistical and rule-based techniques. Language resources and evaluation, 47(1):179–193. Cotelo, J., Cruz, F., Troyano, J., and Ortega, F. (2015a). A modular approach for lexical normalization applied to spanish tweets. Expert Systems with Applications, 42(10):4743 – 4754. Cotelo, J. M., Cruz, F. L., Enríquez, F., and Troyano, J. A. (2015b). Tweet categorization by combining content and structural knowledge. Submitted to Information Fusion (INFFUS); Under Review. Cotelo, J. M., Cruz, F. L., and Troyano, J. A. (2013). Resource-based lexical approach to tweet-norm task. In Tweet-Norm@ SEPLN, pages 20–24. Cotelo, J. M., Cruz, F. L., and Troyano, J. A. (2014). Dynamic topic-related tweet retrieval. Journal of the Association for Information Science and Technology, 65(3):513–523. Cotelo, J. M., Cruz Mata, F., and Troyano Jiménez, J. A. (2012). Generación adaptativa de consultas para la recuperación temática de tweets. Cotelo, J. M., Cruz Mata, F., and Troyano Jiménez, J. A. (2015c). Explorando twitter mediante la integración de información estructurada y no estructurada. Procesamiento del Lenguaje Natural, (55). Cotelo, J. M., Ortega, F. J., Troyano, J. A., and Vallejo, C. G. (2015d). Detecting communities of interest in twitter using spectral biclustering over friend relationships. Submitted to Knowledge and Information Systems (KAIS); Under Review. Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3):171–176. Davidov, D., Tsur, O., and Rappoport, A. (2010a). Enhanced sentiment learning using twitter hashtags and smileys. In Proceedings of the 23rd International Conference on Computational Linguistics: Posters, COLING ’10, pages 241– 249, Stroudsburg, PA, USA. Association for Computational Linguistics. Davidov, D., Tsur, O., and Rappoport, A. (2010b). Semi-supervised recognition of sarcastic sentences in twitter and amazon. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, CoNLL ’10, pages 107–116, Stroudsburg, PA, USA. Association for Computational Linguistics. Derényi, I., Palla, G., and Vicsek, T. (2005). Clique percolation in random networks. Physical Review Letters, 94(16):160202. Eisenstein, J. (2013). What to do about bad language on the internet. In Proceedings of NAACL-HLT, pages 359–369. Fernández, J., Gutiérrez, Y., Gómez, J. M., and Martínez-Barco, P. (2014). Gplsi: Supervised sentiment analysis in twitter using skipgrams. SemEval 2014, pages 294–298. Fleiss, J. L. (1971). Measuring nominal scale agreement among many raters. Psychological bulletin, 76(5):378. for Democratic Action, A. (2009). Annual voting records. Gamallo, P., García, M., Muñoz, M., and del Río, I. (2013a). Learning verb inflection using cilenis conjugators. THE EUROCALL REVIEW, 21(1):12– 19. Gamallo, P., García, M., and Pichel, J. R. (2013b). A method to lexical normalisation of tweets. In Proceedings of the tweet normalization workshop at SEPLN 2013. Sociedad Española para el Procesamiento del Lenguaje Natural. Gayo-Avello, D., Metaxas, P. T., and Mustafaraj, E. (2011). Limits of electoral predictions using twitter. In Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media. Gibson, D., Kleinberg, J., and Raghavan, P. (1998). Inferring Web communities from link topology. In Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space—structure in hypermedia systems links, objects, time and space—structure in hypermedia systems - HYPERTEXT ’98, pages 225–234, New York, New York, USA. ACM Press. Gimpel, K., Schneider, N., O’Connor, B., Das, D., Mills, D., Eisenstein, J., Heilman, M., Yogatama, D., Flanigan, J., and Smith, N. A. (2011). Part-of-speech tagging for twitter: Annotation, features, and experiments. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers-Volume 2, pages 42–47. Association for Computational Linguistics. Go, A., Bhayani, R., and Huang, L. (2009). Twitter sentiment classification using distant supervision. In Processing. Golbeck, J. and Hansen, D. (2011). Computing political preference among twitter followers. In Proceedings of the 2011 annual conference on Human factors in computing systems, CHI ’11, pages 1105–1108, New York, NY, USA. ACM. Greene, D., O’Callaghan, D., and Cunningham, P. (2012). Identifying Topical Twitter Communities via User List Aggregation. Han, B. and Baldwin, T. (2011). Lexical normalisation of short text messages: Makn sens a# twitter. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies- Volume 1, pages 368–378. Association for Computational Linguistics. Han, B., Cook, P., and Baldwin, T. (2012). Automatically constructing a normalisation dictionary for microblogs. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 421–432. Association for Computational Linguistics. Han, B., Cook, P., and Baldwin, T. (2013). Lexical normalization for social media text. ACM Trans. Intell. Syst. Technol., 4(1):5:1–5:27. Han, B., Cook, P., and Baldwin, T. (2014). Text-based twitter user geolocation prediction. Journal of Artificial Intelligence Research, pages 451–500. Hartigan, J. A. (1972). Direct clustering of a data matrix. Journal of the american statistical association, 67(337):123–129. Hong, S. and Nadler, D. (2011). Does the early bird move the polls?: the use of the social media tool ’twitter’ by u.s. politicians and its impact on public opinion. In Proceedings of the 12th Annual International Digital Government Research Conference: Digital Government Innovation in Challenging Times, dg.o ’11, pages 182–186, New York, NY, USA. ACM. Hulden, M. (2009). Foma: a finite-state compiler and library. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics: Demonstrations Session, pages 29–32. Association for Computational Linguistics. Jabeen, S., Shah, S., and Latif, A. (2013). Named entity recognition and normalization in tweets towards text summarization. In Digital Information Management (ICDIM), 2013 Eighth International Conference on, pages 223–227. IEEE. Jiang, L., Yu, M., Zhou, M., Liu, X., and Zhao, T. (2011). Target-dependent twitter sentiment classification. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, HLT ’11, pages 151–160, Stroudsburg, PA, USA. Association for Computational Linguistics. Kahn, J. H., Tobin, R. M., Massey, A. E., and Anderson, J. A. (2007). Measuring emotional expression with the linguistic inquiry and word count. The American journal of psychology, pages 263–286. Kim, E., Gilbert, S., Edwards, M. J., and Graeff, E. (2009). Detecting sadness in 140 characters: Sentiment analysis of mourning michael jackson on twitter. Web Ecology, 3. Kleinberg, J. M. (1999). Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 46:668–677. Kluger, Y., Basri, R., Chang, J. T., and Gerstein, M. (2003). Spectral biclustering of microarray cancer data: Co-clustering genes and conditions. Genome Research, 13:703–716. Kontopoulos, E., Berberidis, C., Dergiades, T., and Bassiliades, N. (2013). Ontology-based sentiment analysis of twitter posts. Expert systems with applications, 40(10):4065–4074. Lancichinetti, A., Radicchi, F., Ramasco, J. J., and Fortunato, S. (2010). Finding statistically significant communities in networks. PLoS ONE, page 24. Lau, J. H., Collier, N., and Baldwin, T. (2012). On-line trend analysis with topic models:\# twitter trends detection topic model online. In COLING, pages 1519–1534. Citeseer. Lavrenko, V. and Croft, W. B. (2001). Relevance based language models. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’01, pages 120–127, New York, NY, USA. ACM. Lee, K. S., Croft, W. B., and Allan, J. (2008). A cluster-based resampling method for pseudo-relevance feedback. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’08, pages 235–242, New York, NY, USA. ACM. Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, volume 10, pages 707–710. Lim, K. H. and Datta, A. (2012a). Finding twitter communities with common interests using following links of celebrities. In Proceedings of the 3rd international workshop on Modeling social media - MSM ’12, page 25, New York, New York, USA. ACM Press. Lim, K. H. and Datta, A. (2012b). Tweets Beget Propinquity: Detecting Highly Interactive Communities on Twitter Using Tweeting Links. In 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, pages 214–221. Ieee. Madeira, S. and Oliveira, A. (2004). Biclustering algorithms for biological data analysis: a survey. Computational Biology and Bioinformatics, IEEE/ACM Transactions on, 1(1):24–45. Mirkin, B. (1998). Mathematical classification and clustering: From how to what and why. Springer. Mohammad, S. M. and Turney, P. D. (2010). Emotions evoked by common words and phrases: Using mechanical turk to create an emotion lexicon. In Proceedings of the NAACL HLT 2010 Workshop on Computational Approaches to Analysis and Generation of Emotion in Text, pages 26–34. Association for Computational Linguistics. Mohammad, S. M., Zhu, X., Kiritchenko, S., and Martin, J. (2014). Sentiment, emotion, purpose, and style in electoral tweets. Information Processing & Management. Mohri, M. (2009). Weighted automata algorithms. In Handbook of weighted automata, pages 213–254. Springer. Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random structures & algorithms, 6(2-3):161–180.