Extracting Semantic Annotations from Twitter

La extracción de información como detección de eventos y minería de opiniones en sitios de micro-blogging como Twitter han tomado gran interés.

Existe contenido semántico incluido en los mensajes publicados en este tipo de sitios, como ejemplo se menciona el siguiente tuit: “Just went to obamas speech in berlin. awesome”. Se pueden encontrar como entidades al presidente Obama, el discurso que pronunció y la ciudad de Berlin. Mientras tanto el sentimiento positivo expresado por la palabra “awesome” es una anotación semántica de la información. Extraer este tipo de información puede ayudar a conocer las respuestas a los eventos políticos.

Debido a las características de los mensajes en Twitter (abreviaciones, oraciones incompletas, emoticons, slangs, etc.) se vuelve una tarea más difícil el llevar a cabo el procesamiento lingüístico por lo que se requiere hacer una normalización previa.

El proceso se centra en herramientas y técnicas de procesamiento de lenguaje natural que incluyen: normalización del texto en los tuits, POS Tagging, reconocimiento de las entidades mencionadas, extracción y análisis de anotaciones y finalmente la transformación de la información en un formato de base de datos reusable.

Se debe tener en cuenta que es necesario contar con una forma de separar los datos de las opiniones, la información irrelevante, spam e información irrelevante de forma que puedan ser excluidas ya que no representan ningún aporte al contenido semántico.

Se forman parejas entre entidades y anotaciones para transferir la información a un formato semántico. Se emplea DBpedia como ontología.

El artículo no muestra mayor detalle en el sistema propuesto.

Narr, S., De Luca, E. W., & Albayrak, S. (2011). Extracting semantic annotations from twitter. Proceedings of the fourth workshop on Exploiting semantic annotations in information retrieval - ESAIR ’11 (p. 15). New York, New York, USA: ACM Press. doi:10.1145/2064713.2064723

Lexical Normalisation of Short Text Messages: Makn Sens a #twitter

Twitter es un espacio que contiene millones de mensajes de los cuales se puede buscar extraer información. Sin embargo, existen problemas en la forma en que la información es presentada, el texto puede contener errores, abreviaciones, emoticons, referencias, etc., esto puede impactar en el análisis de los mensajes.

Un ejemplo utilizado en el artículo es la palabra “Goood” que puede referirse a “Good” (bueno) o a “God” (Dios) dependiendo del contexto por lo que el aprendizaje supervisado puede tener dificultades.

El artículo se enfoca a trasladar las palabras OOV (Out Of Vocabulary) a su forma léxica tradicional en inglés. El sistema se limita al idioma inglés y a que cada token puede ser transformado a una sola palabra (smokin a smoking pero no imo a in my opinion). A este proceso lo denominan como normalización léxica.

Como primer paso, queda determinar la relevancia de crear un sistema de este tipo basados en la proporción de palabras OOV presentes. Para esto tomaron textos del NY Times, SMS (mensajes de texto de celular) y Twitter. Los resultados se presentan a continuación en la siguiente figura destacando cuestiones como que 15% de los mensajes en Twitter contienen 50% o más tokens OOV.

Para analizar el origen de los problemas léxicos tomaron 449 mensajes al azar y encontraron 254 instancias para normalización léxica. Las dividieron en lo mostrado en la siguiente figura:

Se crea un conjunto de confusión (Confusion Set) en el que se identifican los posibles candidatos a normalización. Se reducen las letras repetidas que tengan más de tres veces el mismo carácter a 3. Se calcula la distancia entre el candidato y las palabras en el diccionario con un Threshold determinado. Se lleva a cabo un proceso similar pero con el sonido de las palabras utilizando transcripción fonética. En la siguiente figura se muestran resultados de variar el Threshold.

Para determinar si una palabra esta mal formada (ill-formed) respecto a su conjunto de confusión, se utilizan las palabras adyacentes (2 palabras en cada lado) y mediante un SVM de un solo kernel se determina si lo es probando cada una de las combinaciones de las 3 palabras.

Para las palabras que quedan como candidatas a estar mal formadas se hace una selección de la palabra correcta según: lexical edit distance, phonemic edit distance, prefix substring, suffix substring y LCS (Longest Common Subsequence) para capturar la similitud morfo-fonética. Para inferir el contexto se emplea modelo del lenguaje y características basadas en la frecuencia de las dependencias.

Las pruebas se realizaron con dos objetivos: probar la identificación de palabras mal formadas y la selección de candidato. La evaluación de ambas pruebas se basó en la precisión a nivel de token, recall, y F-Score. Algunos datos observados muestran que mientras mayor sea el Threshold, de detección mayor será la precisión pero el recall caerá. Existen diferencias entre las dependencias encontradas en los diferentes conjuntos de prueba. Las siguientes imágenes muestran los resultados obtenidos:

 

En general encontraron ciertas semejanzas en los errores en los mensajes SMS y en Twitter. La mayoría de los errores son de tipo de variaciones morfo-fonéticas. El detector de palabras mal formadas no requiere anotaciones explícitas y las características basadas en dependencias resultaron ser útiles.

Han, B., & Baldwin, T. (2011). Lexical normalisation of short text messages: Makn sens a# twitter. HLT ’11 Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1 (pp. 368–378). Retrieved from http://ww2.cs.mu.oz.au/~hanb/acl2011-normalisation-slides.pdf

Named Entity Recognition in Tweets: An Experimental Study

Los mensajes en Twitter comprenden una compilación única de información que incluso puede ser más actual que la encontrada en noticias tradicionales debido a su facilidad de uso y la proliferación de los dispositivos móviles. Debido al volumen de mensajes, se piensa en utilizar técnicas como named-entity recognition, information extraction y text mining. Sin embargo, el desempeño de las herramientas de procesamiento de lenguaje natural suelen ser pobre debido a que fueron entrenadas en otro ambiente.

Identificar entidades en Twitter presenta dos problemas. El primero radica en que existe una gran cantidad de entidades (compañías, productos, películas, grupos musicales, etc.) y la mayoría de estos (exceptuando a Personas y Lugares) se presentan de forma relativamente infrecuente. El segundo problema se basa en la limitante de 140 caracteres que permite Twitter por lo que llega a ser difícil determinar el tipo de entidad sin un contexto adecuado.

Para solucionar los problemas, se propone un acercamiento distantemente supervisado que aplica LabeledLDA para tomar gran cantidad de información sin etiquetar en conjunto con diccionarios de datos obtenidos de Freebase y combinar la información del contexto de una entidad en sus menciones.

Se utiliza POS Tagging como una técnica de NLP. POS Tagging asigna cada palabra a su etiqueta más frecuente y asigna cada palabra OOV (Out Of Vocabulary) a la etiqueta POS más común. En el experimento tradicional de Brown corpus se obtuvo un 0.9 de precisión mientras que en los datos de Twitter obtiene solo un 0.76.

El principal motivo del impacto en la precisión se basa en que los mensajes de Twitter contienen más palabras OOV que texto gramatical. Muchas de las palabras OOV se obtienen de errores o variaciones en la ortografía.

Algunos ejemplos de casos que impactan el desempeño son el uso indebido de mayúsculas que no permiten diferenciar entre nombres propios y comunes, verbos y exclamaciones identificados como sustantivos, diferencias en vocabulario, diferencias entre la gramática de los mensajes de Twitter y la usada en el texto de noticias. Los tuits inician suelen iniciar con un verbo omitiendo o el sujeto.

Se anotó manualmente un conjunto de 800 tuits (16K tokens) con etiquetas del conjunto de Penn TreeBank para uso como información de entrenamiento dentro del dominio. Se agregaron etiquetas para fenómenos exclusivos de Twitter como retuits, @nombres_de_usuarios, #hashtags y URLs.

Para las palabras OOV y las variaciones léxicas, se aplicó clustering para agrupar a las palabras que son similares distributivamente. Se utilizó un clustering jerárquico con Jcluster en 52 millones de tuits. Los clusters formados frecuentemente resultan efectivos para capturar las variaciones léxicas como en el ejemplo que proveen para la palabra tomorrow mostrado en la siguiente figura:

T-POS (su sistema) emplea Conditional Random Fields debido a que pueden modelar fuertes dependencias entre POS tags adyacentes y también hacer uso de características altamente correlacionadas. La comparación entre T-POS y el hecho por Stanford se muestra en la siguiente figura:

Shallow Parsing (también denominado como chunking) es la acción de identificar frases no recursivas como frases de sustantivos, frases de verbos y frases preposicionales en el texto.

El uso de mayúsculas es una característica clave para la identificación de entidades. Sin embargo, en Twitter no se encuentra de manera confiable como si podría hallarse en otro tipo de textos. Existe una gran variedad de estilos desde los que no incluyen mayúsculas a los que escriben el texto completamente en mayúsculas. Se construyó un clasificador que toma en cuenta el contenido completo del mensaje y predice si el uso de mayúsculas en un tuit es informativo o no.

Los tuits individuales suelen no contener suficiente información para determinar a una entidad. Además existe el problema de contar con poca presencia, es decir, que no se mencione frecuentemente a una entidad de forma que puede que no se encuentre presente en el conjunto de entrenamiento o que no sea suficiente para su clasificación. Para disminuir el impacto de este problema, se utilizan grandes listas de entidades y sus tipos de una ontología de dominio abierto (Freebase) como fuente para supervisión a distancia.

Sin embargo, la simple búsqueda de entidades y su tipo no es suficiente debido a que existen entidades (35% en el caso de las pruebas) que se encuentran en varias categorías. Además 30% de las entidades mencionadas en Twitter no aparecen en absoluto en Freebase, esto puede ocurrir debido a que es una referencia muy nueva o porque se encuentra mal escrita o abreviada.

Para modelar las entidades sin etiquetar utilizaron LabeledLDA restringiendo a cada entidad a un conjunto de temas basados en los posibles temas arrojados por Freebase. LabeledLDA modela cada string de una entidad como una mezcla de tipos en lugar de un tipo escondido como lo hacen otros modelos anteriores. Esto ayuda a manejar entidades ambiguas que puedan referirse a varios temas.

En general el artículo se basa en la comparación experimental de los resultados de utilizar un POS Tagger propio entrenado con términos comunes en Twitter y otros que son comúnmente utilizados y entrenados con otro tipo de fuentes (textos de noticias principalmente). Se obtienen mejoras (reducen el error de clasificación) y se puede encontrar la herramienta en: https://github.com/aritter/

Ritter, A., Clark, S., & Etzioni, O. (2011). Named entity recognition in tweets: an experimental study. EMNLP ’11 Proceedings of the Conference on Empirical Methods in Natural Language Processing (pp. 1524–1534). Retrieved from http://dl.acm.org/citation.cfm?id=2145595

A Software System for Data Mining with Twitter

El artículo describe la arquitectura e implementación de un sistema para la colección y análisis de datos en Twitter. Se integran módulos para recolección de datos, almacenamiento espacial de datos fuera de línea, recolección de datos espaciales, búsqueda completa de texto, expansión de jerga (slang), mapeo de datos y exportación.

La siguiente figura muestra el diagrama de casos con las interacciones que se espera tenga el sistema con el usuario:

El módulo de recolección de datos se encuentra separado de la interfaz web. Se emplea la librería Twitter4J para conectarse al Streaming API y guarda los mensajes recibidos en una base de datos de SQLite. La siguiente figura muestra la arquitectura de la recolección de datos:

Los datos se hayan en una base de datos de SQLite originalmente sin datos espaciales. La información sobre localización (latitud y longitud) embebida en los mensajes debe ser representada en un formato espacial antes de poder llevar a cabo consultas tomándolo como parámetro. Se utilizan un par de sitios que contienen información sobre coordenadas dentro del Reino Unido.

Para usar la extensión geográfica GeoDjango se requiere de una base de datos espacial, en este caso se usa PostgreSQL con la extensión espacial PostGIS. Se utiliza un script para transformar cada mensaje almacenado en la base de SQLite a su equivalente espacial en PostgreSQL. La arquitectura de este módulo se muestra en la siguiente figura:

Una vez convertidos los datos a su equivalente espacial, GeoDjango se encarga de proveer un framework de alto nivel para obtener modelos geográficos basados en la localización. La siguiente figura muestra la arquitectura de esta parte:

La búsqueda de texto completo (full text search) se incorpora para ayudar al análisis textual, mejorar el tiempo de respuesta de los queries en grandes conjuntos de datos y para obtener una mayor cantidad de resultados.

Se incorpora el motor Apache SOLR basado en Lucene para el indexado de los documentos y su recuperación. El motor de búsqueda se integra al sistema usando el módulo HayStack.

Se introduce el sistema “slang expansion” para lidiar con las palabras y abreviaciones propias de Twitter. El proceso se basa en la integración de una “slang table” que contiene 5,000 palabras de este tipo y su equivalente al inglés formal. La siguiente figura muestra la arquitectura de todo este módulo:

El último módulo del sistema se encarga de la visualización y exportación de los datos y su arquitectura se encuentra en la siguiente figura:

La visualización de los datos (y en general el sistema) se basa en la información sobre el lugar en el que se producen los mensajes. Por ejemplo las siguientes imágenes muestran el conjunto de datos totales, los mensajes correspondientes al uso de alcohol y a referencias hacia fumar.

Bhat, F., & Oussalah, M. (2011). A software system for data mining with twitter. Cybernetic Intelligent Systems (CIS), 2011 IEEE 10th International Conference on (pp. 139–144). doi:10.1109/ CIS.2011.6169149

Building Earthquake Semantic Network by Mining Human Activity from Twitter

El objetivo del artículo se basa en poder presentar a las personas que se encuentran o encontraron en un siniestro una serie de patrones de acciones para llevar a cabo. Para empezar se define a una actividad como los siguientes cinco atributos: actor, acción, objeto, tiempo y lugar. Estos atributos deben encontrarse en los mensajes aunque algunas oraciones contienen una estructura más compleja además de anomalías como errores gramaticales y palabras inexistentes.

Debido a que se enfocan a las transiciones y causas entre las actividades, se etiquetan como Siguiente (Next) y Debido A (BecauseOf) respectivamente. La siguiente figura es un ejemplo de los atributos y relaciones entre actividades derivados de una oración de actividad.

Para extraer las actividades humanas de cada oración, se crea automáticamente su propio conjunto de aprendizaje (self-supervised learning) y utiliza CRF (linear-chain control random field) como modelo de aprendizaje.

La arquitectura general del sistema se compone de un Self-Supervised Learner (SEL) y un Extractor de Actividades. Primero, SEL utiliza 8 patrones básicos de sintaxis de japonés para seleccionar las oraciones analizables. Posteriormente se emplea un parser lingüístico profundo para extraer los atributos de la actividad y sus relaciones. Usando la acción y objeto extraídos como palabras clave, se utiliza el API de Google Blogs para recolectar nuevas oraciones de actividades que contengan atributos confiables. Después, SEL combina los resultados extraídos para crear su conjunto de entrenamiento de manera automática. Por último, utiliza CRF y un archivo de plantilla para crear un modelo de dichos datos de entrenamiento. El Extractor no despliega el parser lingüístico sino que se basa en el modelo obtenido para predecir atributos en cada oración obtenida de Twitter. La siguiente figura muestra el esquema general:

La red semántica del terremoto (ESN) se define como una inteligencia colectiva de actividades humanas que ocurren durante un terremoto. Se expresa mediante un grafo dirigido cuyos nodos son conceptos de atributos de actividades y los arcos son las relaciones entre los conceptos. La siguiente figura muestra un ejemplo:

Como en su trabajo anterior, decidieron utilizar N3 para la definición de la red semántica quedando de la siguiente manera:

El proceso de la creación de la red semántica inicia con la búsqueda en Twitter de las palabras clave (en este caso el hashtag #jishin) para obtener las oraciones de actividad. Posteriormente se extraen los atributos y se convierte a RDF/N3. El proceso se ilustra a continuación:

La elección de CRF se basó en la existencia de aprendizaje generativo representado comúnmente por modelo oculto de Markov (HMM) y el aprendizaje discriminativo donde se encuentra CRF, el modelo de máxima entropía de Markov (MEMM) y máquinas de soporte vectorial (SVM). Dado que en trabajos previos encontraron que CRF rebasa el desempeño de HMM y MEMM en la tarea de etiquetado secuencial (sequencial labeling task) decidieron comparar CRF con SVM. La siguiente figura muestra los resultados en los que se basaron para emplear CRF:

Las computadoras pueden recomendar un curso de acción a tomar basadas en patrones de otros encontrados dentro de la ESN. Por ejemplo si en una determinada hora, la mayoría de personas siguieron el conjunto { accion1, accion2 } para llegar al centro de evacuación A desde cierto punto. La computadora puede recomendar realizar dichas acciones para llegar al centro de evacuación para un usuario cercano al área inicial. El ejemplo se ilustra en la siguiente figura:

A diferencia de otros artículos mencionados, no se depende enteramente de una ontología previamente definida por lo que se puede aplicar a diversos siniestros y situaciones.

Nguyen, T.-M., Koshikawa, K., Kawamura, T., Tahara, Y., & Ohsuga, A. (2011). Building earthquake semantic network by mining human activity from Twitter. 2011 IEEE International Conference on Granular Computing, 496–501. doi:10.1109/GRC.2011.6122647

Building an Earthquake Evacuation Ontology from Twitter

En caso de un siniestro como el ocurrido en la región de Tohoku el 11 de marzo de 2011, hubo fallas en las comunicaciones tradicionales y las líneas de celulares debido entre otras cosas, a la saturación del sistema. Las redes sociales fueron entonces utilizadas como un medio para obtener información sobre baños, centros de evacuación, etc.

Debido a las características de Twitter, no solo el público en general sino también el Ministerio de Educación, Universidades y los gobiernos locales lo emplearon para poder difundir información durante aquel día.

Twitter contiene información textual, por lo tanto las búsquedas se llevan a cabo mediante una palabra o una frase. Existe el problema que consiste en que si una palabra no esta explícitamente escrita en el mensaje, no aparecerá en los resultados de la búsqueda.

Otro problema presentado radica en no tener conocimiento de un lugar. Se pone como ejemplo el haber llegado tras el incidente a Yokohama. Si se hace una búsqueda de Yokohama pueden aparecer mensajes como: “Para las personas que tengan dificultad para volver a sus casas, Pacifico Yokohama permanecerá abierto”, sin embargo, para personas que no conozcan el sitio, esta información resultará inútil. Las personas podrían llevar a cabo una búsqueda en Google acerca del lugar, pero esto se dificulta al encontrarse en medio de una emergencia.

Para que una computadora pueda proveer de toda la información necesaria, se plantea que primero esta debe entenderla. Para este motivo, se diseño una ontología que explícitamente define los atributos y las relaciones entre los conceptos.

Para proveer información adecuada de los centros de evacuación de cuerdo a la información proveniente de los usuarios, se requiere de información sobre los centros de evacuación, conocer la relación entre la información y un vocabulario para describir los conceptos. Un ejemplo del concepto de un centro de evacuación en la vida real se muestra en la siguiente figura:

Mientras tanto en la siguiente figura se muestran las clases y atributos de las ontologías planteadas a partir de la información del modelo:

Se procuraron los siguientes criterios para la creación de la ontología:

• Creación de un vocabulario
• Cooperación con ontologías existentes
• Conversión Japonés-Inglés

La ontología fue creada haciendo uso del RDF (Resource Description Framework), RDF Schema y OWL (estandarizado por W3C). En concreto se utilizó N3 (http://www.w3.org/TeamSubmission/n3/ ) y las siguientes figuras son ejemplos de una definición de clase y otra de atributos:

Un ejemplo de una ontología siguiendo los modelos definidos se muestra a continuación:

El proceso que se sigue para el uso de la ontología es llevar a cabo la búsqueda de los centros de evacuación en Twitter. Por ejemplo si se encuentra el siguiente mensaje: “School rooms and gymnasiums in Shinjuku Metropolitan High School have been opened. These have heating system, there are drinks and also TV information is provided”. Se extraerían el nombre del centro de evacuación (Shinjuku Metropolitan High School), los productos ofrecidos (bebidas, calentadores) y el tiempo en que se envió el mensaje. Después de obtener esta información, se obtienen datos complementarios como la dirección del sitio a través de Google Maps, la latitud y longitud del sitio a través de Geocoding y una traducción al inglés por medio de Google Translate. De esta forma, se complementan datos útiles que no se encontraban incorporados al mensaje original.

Las pruebas se llevaron a cabo con el fin de probar si la ontología es capaz de proveer información apropiada de acuerdo a la situación y si esta resulta flexible y escalable.

Usando SPARQL (Simple Protocol And RDF Query Language) se determinó si es posible ofrecer a los usuarios información adecuada basados en su localización y tiempo. El query mostrado como ejemplo obtiene información sobre centros de evacuación y los productos ofrecidos en Shinjuku entre las 18:00 horas de marzo 11 a las 9:00 horas de marzo 12. El ejemplo se muestra en la siguiente figura:

Los resultados de llevar a cabo la consulta anterior se muestran a continuación:

Se puede obtener información en base a consultas en tiempo real debido a la arquitectura del sistema (mostrada en la siguiente figura). Concluyeron que es posible brindar información útil sobre centros de evacuación.

Para mostrar la eficiencia de la ontología, se llevaron a cabo comparaciones con otro tipo de búsquedas (google, twitter) siguiendo los siguientes criterios:

1. Obtener información de todos los centros de evacuación con un parámetro designado.
2. Obtener información de todos los centros de evacuación que se encuentren abiertos de acuerdo a una dirección designada.
3. Obtener información de todos los centros de evacuación en Minato-ward, Tokio.
4. Obtener información de todos los centros de evacuación que se encuentren abiertos de acuerdo a un tiempo determinado.
5. Obtener información de todos los centros de evacuación que se encuentren abiertos en un rango de tiempo.
6. Obtener información de todos los centros de evacuación que se encuentren actualmente abiertos y que originalmente abrieron hace 15 minutos.
7. Obtener información de todos los centros de evacuación que estén abiertos basados en un parámetro designado.
8. Obtener información de todos los centros de evacuación capaces de ser usados en cooperación con una ontología externa de radiación.
9. Obtener información acerca de los productos ofrecidos por el centro de evacuación más cercano.

En general su búsqueda fue más rápida debido a que consideran que en una llevada a cabo de manera tradicional deberían seguir los siguientes pasos:

1. Buscar todos los nombres de lugares que aparecen en el mapa de acuerdo al parámetro determinado.
2. Buscar cada nombre encontrado en combinación con palabras clave como centro de evacuación.
3. Observar los resultados y obtener información sobre los centros de evacuación.

Se pueden combinar ontologías que tengan cierta similitud con los atributos que utilizan (por ejemplo ellos usaron 3 ontologías existentes para complementar la suya) y por lo tanto el sistema ofrece escalabilidad.

Como posible trabajo a futuro queda planteado la obtención automática de la ontología.

Iwanaga, I. S. M., Nguyen, T.-M., Kawamura, T., Nakagawa, H., Tahara, Y., & Ohsuga, A. (2011). Building an earthquake evacuation ontology from twitter. 2011 IEEE International Conference on Granular Computing, 306–311. doi:10.1109/GRC.2011.6122613

Anotaciones sobre API de Twitter

En general Twitter mantiene dos APIs generales (REST y Streaming) para acceder a su información y uno específico para búsquedas (SEARCH). Mientras que en general ambos permiten llevar a cabo búsquedas, filtros, ver perfiles, etc., pero se trabaja de una manera distinta.

REST API de Twitter permite hacer consultas a la red social (parece ser que es mediante HTTP Requests) y se inicia y termina una conexión cada que se lleva a cabo una petición. Se tiene un límite (me parece que es por hora) del número de peticiones que pueden ser llevadas a cabo. El proceso en general lo muestra la siguiente figura:

El Streaming API de Twitter mantiene una conexión abierta con el servidor. Las consultas HTTP se hacen de manera independiente. La ventaja que ofrece es el tener acceso a información en tiempo real y poder llevar a cabo parseo, filtros y otros procesos antes almacenar los resultados. La arquitectura general se muestra en la siguiente figura:

Por último el Search API se enfoca directamente a las búsquedas sobre el índice en tiempo real de tuits recientes. Sin embargo se tienen las siguientes limitaciones:

• No se busca en todos los tuits sino en el índice de mensajes recientes que incluye mensajes de entre 6 y 9 días de antigüedad.
• No se puede utilizar el API para buscar mensajes de más de una semana de antigüedad.
• Si el query es muy complejo arrojará un error.
• No se soporta autenticación, todos los queries son anónimos.
• Esta búsqueda se basa en relevancia y no completitud. Esto significa que algunos tuits pueden faltar. Si se requiere completitud se recomienda usar el Streaming API.
• No se puede usar el operador near, se debe usar la geo-localización.
• Los queries están limitados a 1,000 caracteres (incluyendo a operadores).
• Al realizar consultas basadas en geo-localización, solo se consideran 1,000 subregiones distintas al evaluar el query.
• Se tiene un límite en cuanto a complejidad y frecuencia en las consultas que se hacen.

Content-based prediction of temporal boundaries for events in Twitter

La popularidad y dinámica de Twitter, permiten que se puedan relatar eventos en tiempo real. Los mensajes normalmente son escritos por personas dentro de un evento o por personas que son afectadas directamente por el evento. Para eventos que pasan después de un tiempo (derrames de petróleo, huracanes, incendios, etc.) se puede analizar los datos de los mensajes para ver la progresión del evento, como avanzó geográficamente e identificar sus mayores sub-eventos.

El objetivo de este artículo es poder determinar cuando inicia un evento y cuando termina. Se segmenta este proceso en tres etapas: la concentración (buildup) del evento, el evento y los efectos y repercusiones posteriores al evento. El estudio va más enfocado al contenido de los mensajes que al volumen de los mismos.

Se recolectaron mensajes de varios temas (deportes, eventos climáticos, eventos sociales, etc.). Se trató a cada mensaje como una instancia de datos y se le etiquetó de manera manual si el mensaje correspondía a antes, durante o después del evento. Un ejemplo sobre el resultado del proceso se muestra en la siguiente figura y son mensajes correspondientes al SuperBowl XLV.

De igual forma se consideran los mensajes que no contienen información temporal. En lugar de ser descartados, se les asignan clases de forma que puedan ser identificados por el sistema. Un ejemplo de los datasets utilizados se muestra en la siguiente figura:

Para determinar los límites temporales de los eventos hacen uso de un SVM (Support Vector Machine) multi-clase para clasificar los datos del evento en tres grupos y se probaron distintos algoritmos para estimar los límites. La arquitectura general se muestra en la siguiente figura:

Se hace una limpieza de los mensajes eliminando elementos como URLs, símbolos de retuit (RT) y menciones a usuarios. Por otra parte, se aseguran de mantener los hashtags (palabras con un numeral # previo) debido a que es una característica valiosa y se puede usar para realizar consultas.

Debido al ruido presente en los mensajes, por ejemplo abreviaturas, faltas de ortografía, emoticons, etc., se requiere de un parser especializado para lidiar con el problema.

El identificar los tiempos en los que se encuentran conjugados los verbos ayuda a determinar en que grupo se debe clasificar un mensaje. El proceso para generar las características basadas en verbos se siguen los siguientes dos pasos:

1. Identificar verbos: Se anota a que instancia pertenece cada palabra (Part of Speech) utilizando el modelo left3words-wsj-0-18 del Stanford Log-linear POS Tagger. Este es un ejemplo del resultado de aplicarlo a una oración: the/DT doctor/NN is/VBZ examining/VBG the/DT effects/NNS that/WDT the/DT treatment/NN has/VBZ on/IN the/DT patient/NN ./.
2. Identificar la verb tag phrases: Se identifica cualquier secuencia de verbos en términos de sus frases de etiqueta. La siguiente figura muestra un ejemplo de las frases y etiquetas:

Se crearon oraciones gramáticamente correctas para poder comparar los verbos encontrados. Debido al ruido que se encuentra en los mensajes de Twitter y que el Stanford POS Tagger fue entrenado con estructuras gramaticales correctas, se debieron incluir más verb tag phrases.

Para los valores de C (compensación entre el error de entrenamiento y el margen), se calculó que 30,000 era un buen número de manera empírica al tratar con valores entre 1 y 100,000. Incrementar el valor de C significa incrementar la complejidad y poder manejar datasets más complejos.

La fidelidad del sistema se probó y se mostró que no influyen en gran medida las características obtenidas de los verbos. Sin embargo, se tiene en cuenta que esto puede ser ocasionado debido a como está entrenado el Stanford POS Tagger por lo que piensan utilizar un Tagger específico para Twitter en un trabajo a futuro. Los resultados se muestran en la siguiente figura:

El uso de una ventana deslizante mostró mejorías sobre la fidelidad de los resultados del sistema. El sistema mejoró sus resultados al incrementar su ventana hasta 20, después de ahí la mejoría por continuar incrementando el tamaño no fue tan drástica. Los resultados se pueden apreciar en la siguiente figura:

Siendo que se mantienen en orden cronológico los mensajes que se están procesando y al tener tres clases (antes, durante y después), la clasificación idealmente se debería llevar a cabo mediante dos cortes en el flujo de los mensajes. La comparación de los límites obtenidos mediante el algoritmo de Cuts y las cadenas ocultas de Markov (HMM) indican que para datos suavizados (smoothed) el desempeño del algoritmo de Cuts es mejor debido a que intenta minimizar el error pero para los casos en que los datos no se encuentran así, las HMM tienen un mejor desempeño ya que usan más factores para aprender. Los resultados se muestran en la siguiente figura:

Por otra parte, se mostró que es más sencillo identificar los límites de un evento bien definido como lo son los deportivos a diferencia de otros como un huracán (su duración comprende varios días afectando a diversas zonas) o la boda real (contiene varios sub-eventos como la alfombra roja, la llegada de la Reina, etc.) Debido a esto es difícil aun para los humanos decidir los límites que tienen los eventos. Esto se muestra en la siguiente figura:

Para evaluar la posible aplicación del sistema a un dominio en específico, se construyó un clasificador para deportes utilizando los 4 eventos del dataset (empleando 3 para el aprendizaje y uno de prueba). Los resultados de detección de los límites fueron bastante precisos y sobretodo al detectar el final del evento debido a la existencia de términos como ganar, perder, felicidades y otros que solo ocurren al finalizar el juego. Los resultados de comparar el clasificador específico del evento contra el del dominio se aprecian en la siguiente figura:

Por otra parte, la siguiente figura muestra la diferencia entre los límites reales y los especificados por el sistema en el caso del SuperBowl XLV:

En general el sistema asume que se cuenta con información suficiente que cubra los eventos y las situaciones previas y posteriores al mismo. Se comparan los resultados de utilizar clasificadores entrenados para el evento y otros para el dominio. Queda como trabajo a futuro crear clasificadores de multi-dominios.

Iyengar, A., Finin, T., & Joshi, A. (2011). Content-Based Prediction of Temporal Boundaries for Events in Twitter. 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third Internationall Conference on Social Computing (pp. 186–191). IEEE. doi:10.1109/PASSAT/SocialCom.2011.196

Breaking News Detection and Tracking in Twitter

Twitter es un medio que permite transmitir información en tan solo 140 caracteres. Los usuarios tienden a compartir eventos de relevancia para ellos, en este caso noticias, debido a la facilidad y alcance que se logra.

En si se separa la obtención de noticias recientes en dos partes: el aspecto de un solo mensaje y el aspecto de la línea de tiempo. Primero se tiene el aspecto de un solo mensaje. Un mensaje contiene dos elementos de relevancia: emociones y hechos. Las emociones distinguen a la entrega de la información por medio de Twitter de lo que haría un periodista profesional, aunque existan casos en que tradicionalmente se incluya en un medio profesional, este fenómeno tiende a aparecer más en Twitter. Las emociones se encuentran expresadas por símbolos (como el signo de exclamación) o por el uso de adjetivos.

Los hechos por su parte se encuentran en forma de texto, híper-texto, locación y fuente de información de quien envía el mensaje. La información basada en texto tiene gran relevancia ya que ayuda a responder los detalles de la noticia (¿qué?, ¿cuándo?, ¿cómo?, etc.). Se pueden establecer palabras clave que contribuyan a la noticia y normalmente son sustantivos y verbos significativos. Los sustantivos pueden incluir palabras encontradas en noticias convencionales, nombres de lugares famosos, personas y eventos. Los verbos significativos que se presentan como ejemplo son: quemar, chocar, bombardear, sobrevivir, rescatar, etc. Los usuarios tienden a preceder las palabras claves por una almohadilla o numeral (#) para agrupar los mensajes que se refieren al mismo tema. Los hechos basados en híper-texto proveen información de fuentes externas. Otros elementos comunes son la inclusión de mapas o imágenes para complementar la noticia.

Por su parte la línea del tiempo permite observar que los mensajes importantes o interesantes tienden a ser más retuiteados que otros. Se puede observar el desenvolvimiento de una historia por medio de una serie de mensajes. Un ejemplo se muestra en la siguiente figura:

El trabajo que se presenta deja de lado las emociones como trabajo a futuro y se concentra en un método para recolectar, agrupar, clasificar y seguir noticias actuales. Se divide el proceso en encontrar una historia y seguir el desarrollo de la historia. El proceso se muestra en la siguiente figura:

Para encontrar una historia se siguen los siguientes tres pasos:

1. Sampling: Mediante peticiones al Straming API de Twitter, se consultan términos relacionados con las noticias emergentes por ejemplo: #breakingnews, breaking news, etc.
2. Indexing: Se hace un indexado basado en el contenido de los mensajes utilizando el método de Apache Lucene.
3. Grouping: Los mensajes que son similares entre si son agrupados para formar la historia de una noticia. La medida de similitud se calcula mediante el TF-IDF. Para asegurar que un mensaje se encuentra relacionado a una noticia se compara con el mensaje original y con un número k (en este caso 10) de términos en el grupo.

Para el desarrollo de la historia, cada historia se ajusta según una clasificación adecuada por un periodo de tiempo. Se agregan fuentes externas, fotos y videos si son encontrados.

Se llega a la conclusión de que es necesario darle mayor relevancia a los nombres propios ya que en un espacio tan pequeño como los 140 caracteres que se permiten, seguramente contienen información relevante. Los resultados de los agrupamientos se muestran en la siguiente figura:

Se construyó un prototipo de la aplicación llamado HotStream. Se muestran las historias más relevantes de las últimas 24 horas y al dar clic en una noticia, se obtienen más detalles así como su desarrollo. La aplicación se muestra en la siguiente figura:

Phuvipadawat, S., & Murata, T. (2010). Breaking News Detection and Tracking in Twitter. 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, 120–123. doi:10.1109/WI-IAT.2010.205

Crawlers for Social Networks & Structural Analysis of Twitter

Debido al gran crecimiento que han tenido las redes sociales (Open Social Networks OSN), por ejemplo se menciona a Facebook con más de 800 millones de usuarios, es básicamente imposible tener una copia de la imagen de la estructura de cada red y que sea mantenida con información al día.

La primera razón que brindan como motivación para su investigación es el entendimiento de las características fundamentales de las redes sociales como leyes de potencias en grados de distribución o propiedades de mundos pequeños. Esta información les permitiría reflexionar sobre las similitudes y diferencias entre las redes de tipo OSN y también conocer información sobre ellas y la dinámica de sus comunidades.

La segunda motivación se concentra en la capacidad de crear modelos generativos para las OSNs tal que pequeñas redes representativas puedan ser simuladas para entender su dinámica y validar los análisis teóricos.

Para la construcción de los crawlers se tomaron en cuenta los siguientes puntos:

• Cobertura de nodo: El número de nodos visto como proporción del total de nodos presentes en la red social después de un número determinado de pasos del algoritmo.
• Capacidad de interpretación de las acciones de marcas por espías o fisgones de terceros: Es importante que las búsquedas de una marca en un proveedor de red social no pueda ser interpretado de tal forma que se pueda hacer una predicción de sus acciones.
• Uso de tokens de autenticación de la red social: Debido a la existencia de un límite de peticiones que pueden ser llevadas a cabo a los servidores, se trata de maximizar las peticiones que pueden llevar a cabo cada token autenticado.
• Facilidad de ser atrapado en un cluster local del que no sea fácil salir: Tener en cuenta que debido a la naturaleza de redes como Twitter, si no se cuenta con backtracking en el algoritmo, se puede quedar varado.
• Facilidad de paralelización: Se busca construir varios crawlers que trabajen de forma paralela para obtener la información requerida. Debe ser capaz de escalar hacia arriba como hacia abajo dependiendo de los recursos de procesamiento disponibles.

Por su parte, los algoritmos considerados para crear los crawlers fueron los siguientes:

• Random Walk: Se inicia en un nodo, explora todos sus vecinos y de manera aleatoria elige uno para continuar explorando. Puede quedarse atorado si un nodo solo tiene enlaces entrantes o tiene deshabilitada la exploración debido a las restricciones de seguridad. Aunque es fácil de implementar y paralelizable, es susceptible a visitar el mismo nodo varias veces cuando atraviesa la red.
• Random Walk with Backtrack: Para evitar quedar atascado, si no se encuentran enlaces para continuar se hace backtrack de un paso y se elige de nuevo un nodo al azar.
• Metropolis Hastings Random Walk (MHRW): Las caminatas aleatorias tienden a favorecer el visitar nodos de grados mayores. Se asegura un muestreo uniforme de la red.
• Breadth First Search (BFS): La búsqueda toma un nodo inicial y pone a todos sus vecinos en una cola de nodos visibles que todavía no son explorados. Después toma al primer nodo en la cola y lo explora, pone a todos sus vecinos que todavía no estén presentes en la cola y continúa el proceso. Es fácil de implementar pero requiere una gran cantidad de capacidad de almacenamiento para la cola. No es fácil de paralelizar al tener a todos los nodos compartiendo la misma cola.
• Randomized Search: Al igual que el anterior se toma un nodo inicial y se pone a sus vecinos en una lista. En lugar de tomar al primer nodo, se toma uno al azar de la lista. Se debe asegurar que los nodos que ya fueron visitados no sean incluidos de nuevo en la lista y solo entradas únicas existen en ella.
• Greedy: Se basa en el BFS pero la cola esta ordenada por el grado de enlaces salientes de cada nodo respecto al grafo explorado. A pesar de ser fácil de implementar y de paralelizar, se debe calcular el grado de enlaces salientes de manera constante.
• Lottery: Es similar al Greedy pero el nodo que será explorado se escoge de manera probabilística. Los nodos con mayor grado de enlaces salientes tienen mayor probabilidad. Al igual que Greedy, se necesitan calcular las probabilidades de manera constante.
• Hypothetical Greedy: Es similar al Greedy pero en lugar de basarse en el grado de enlaces salientes sobre el grafo explorado, se emplea el grafo entero. Se requiere un token extra de autenticación para llevarse a cabo.

La siguiente tabla muestra las características evaluadas en cada uno de los algoritmos:

Dentro de los resultados presentados encontraron algunos fenómenos como el hecho de que hacer el BFS como inferior al visitar los nodos como se muestra en la siguiente figura:

Al final decidieron quedarse con la implementación de Random Search para mantener bajos los requerimientos de procesamiento, optimizar el uso de tokens de autenticación y prever el espionaje de terceros.

La base de datos que contiene la información de descargada de Twitter o de cualquier otra red social se espera que crezca en gran dimensión. Otra consideración tomada en cuenta consiste en que la información esta limitada por lo que se puede obtener mediante los tokens de autenticación.

Para asegurar que no se repitan nodos que ya fueron procesados, siempre se lleva registro de ellos y van cambiando simplemente su lugar. En la siguiente figura se muestra la arquitectura general del proceso de la base de datos.

Se hacen algunas reflexiones dependiendo del número de seguidores como que los famosos tienen muchos más seguidores que su grupo de amigos. Otro caso parece ser el de los bots con pocos seguidores y que siguen a muchas personas. Esto se ve en la siguiente figura:

Otros resultados consisten en el número de usuarios por país y por zona horaria presentados a continuación:

En general el artículo se centra en las diferentes técnicas que evaluaron según sus criterios para llevar a cabo el descubrimiento de la estructura de una red social. Se menciona que al momento de la escritura, se tenían 5 millones de nodos, 950 millones de conexiones y 16 millones de perfiles capturados.

Saroop, A., & Karnik, A. (2011). Crawlers for social networks & structural analysis of Twitter. 2011 IEEE 5th International Conference on Internet Multimedia Systems Architecture and Application (pp. 1–8). IEEE. doi:10.1109/IMSAA.2011.6156368