Búsqueda de Frases Clave en una Red Social de Microblogging usando

Técnicas de Emparejamiento Semántico

Alumno: Erwin Salas Coz

Taller de Tesis en Ingeniería de Sistemas 2

1UNIVERSIDAD NACIONAL DE INGENIERIA

Lima-Perú2009

Escuela Académica Profesional de Ingeniería de Sistemas

Profesor: Mg. Samuel Oporto Díaz

Código: 20050053ECorreo electrónico : esalascoz@gmail.com

UNIVERSIDAD NACIONAL DE INGENIERÍA

FACULTAD DE INGENIERÍA INDUSTRIAL Y DE SISTEMAS

• La popularizaci´on de las redes sociales en internet ha hecho que las empresas que tienen como plaza (medio de publicidad en el argot del m´arketing) el internet est´en interesados en su potencialidad para realizar campa˜nas de publicidad m´as acorde al perfil del consumidor de tal forma que sea m´as relevante y pueda m´as efectivamente satisfacer las necesidades del cliente. Estas redes sociales se las puede clasificar como los blogs, microblogging y los servicios de red social. Como ejemplos tenemos a Blogger, Twitter y Facebook respectivamente. Tomaremos con atenci´on a los de la clase microblogging los cuales funcionan de la siguiente manera:

• Disponemos de una p´agina web o cliente1 el cual brinda el servicio de microblogging.

• Si el usuario no tiene una cuenta se la crea, sino accede a su cuenta.• El usuario escribe en un texto de no m´as de 140 caracteres (motivo de su ´exito)• en cual escribe acerca de su que hacer, opiniones, ideas, pensamientos,• temas relacionados a actividades sociales que desea compartir con otros.

Introducción

• Entre las actividades realizadas al hacer una campa˜na de publicidad en internet tenemos:

• Definir los objetivos de la campa˜na en internet.• Identificar la fase en la que se encuentra el cliente potencial en

la internet.• Identificar keywords y keyphrase relevantes al negocio.• Anunciar en motores de b´usqueda (search engine).• Anunciar en en redes sociales con banners, textos e im´agenes.• Monitorear el desempe˜no de cada medio de publicidad.• Realizar los cambios necesarios para cumplir con los objetivos

planteados.

Muchos problemas de bioinformática se puede representar como hallar las ocurrencias de un string en otro.

S1

S2

EL PROBLEMA SE ACRECIENTA AÚN MÁS CUANDO SE BUSCA REPTICIÓN APROXIMADA!

Repetición Repetición Repetición

CAMINO

CAMINOS

PISTAS

PISTA

CAMINO

CARRETERA

LISTA

ENTRE PALABRAS SIMILARES EXITE UN ALTO NIVEL DE MISMO SIGNIFICADO SEMANTICO

Navegador

“iPhone en Perú”Search

TWITTERTWITTERBuscador

Procesos-Indexar-Rankear-Evaluar-Elegir-Mostar

¿De qué manera decir, este es mejor que el otro?

Planteamiento del problema

• El buscador semántico ¿cómo definir el nivel de similitud ontológico mediante técnicas de emparejamiento semántico?.

OBJETIVOS

• Objetivo de la Investigacion• Objetivo superior• Definir un criterio de similitud ontológica mediante

tecnicas terminologicas aplicable a un buscador web.• Objetivo principal• Identificar cu´al algoritmo es el que logra la mejor

distancia de Hamming y Levenshtein adem´as de la mejor eficiencia O() en el tiempo y espacio de ejecuci´on para las secuencias mitocondriales asi como desarroollar una medidad de similitud entre ontolog´ıas basada en la distancia entre cadenas orientadas a un buscador web.

• Objetivos espec´ıficos• Los objetivos espec´ıficos son los siguientes:• 1. Investigar sobre algoritmos m´as comunmente usados en

la web sem´antica.• 2. Desarrollar y explicar los algoritmos de Needleman-

Wunsch y Weiner.• 3. Mostrar ejemplos de los algoritmos.• 4. Recopilar las actualizaciones de acuerdo a un tema en

Twiiter.• 5. Desarrollar una medida de similitud de las preguntas al

buscador y resultados basado en el algoritmo de Needleman-Wunsch.

• 6. Investigar la bibliografia correpondiente para la implementaci´on de los algoritmos.

• 7. Desarrollar los algoritmos a comparar en C++ para su evaluaci´on y an´alisis.• 8. Ejecutar los algoritmos usando las base de datos recopilada.• 9. Recopilar la informaci´on estad´ıstica de cada producto obtenido de los

algoritmos.• 10. Medir las distancias de Hamming y Levenshtein de los alineamientos

obtenidos.• 11. Comparar los resultados obtenidos entre los dos algoritmos.• 12. Identificar cual es el que tiene el mejor desempe˜no seg´un los plantemientos• fijados.• 13. Medir el nivel de acertaci´on de las b´usquedas realizadas en base al buscador• sem´antico, es decir la revisi´on de los resultados.

Justificación• Cada vez es m´as imperante tener m´etodos para obtener informaci´on de

mayor relevancia (o entrando a otros campos producir conocimiento) u ordenada de las cada vez m´as grandes cantidades de informaci´on vertida en la internet por los usuarios.

• El conocimiento por parte de las empresas consultoras de m´arketing de las opiones de las personas en las redes sociales es de vital importancia para el ´éxito de las campa˜nas que realizan, siendo la inversi´on en m´arketing online cada vez m´as importante en el mundo de la publicidad.

Base de Datos

• Fuente de Datos• La fuente de datos ser´a recopilado mediante las APIs de

Twitter usando los comandos proporcionados por la misma. Estos datos est´an disponibles de los ´ultimos 7 d´ıas que por lo tanto para tener una mayor cantidad de datos ha de realizarse un almacenamiento semanal. Para su obtenci´on se har´a un parser al codigo obtenido por la API de Twitter. La direcci´on URL en donde se ecuentran los formatos, sintaxis y detalles de la API de Twitter es http : ==apiwiki:twitter:com.

• Estructura de los datos• Los datos al ser texto ser´an almacenados en una base de datos

en campos de tipo text.

• Descripción de los datos• Los datos son b´asicamente texto ASCII y son

de a lo m´as 140 caracteres lo• cual facilita en cierta medida el trabajo del

buscador. Son obtenidos mediante el• comando search en formato JSON, RSS y

Atom.

METODO DE SOLUCION

Preprocesamiento

• Obtenci´on de los tweets de la API: Para proceder con esto usaremos el siguiente comando proporcionado por la API de Twitter http : ==search:twitter:com=search:format Definimos el comando y caracter´ısticas m´as resaltantes de la API search de Twitter.

• URL: http : ==search:twitter:com=search:format• Formats: json, atom• HTTP Method: GET• Requiere autenticaci´on : false• L´ımite de llamadas a la API a la vez : 1 call per request• Los resultados son obtenidos en este formato en JSON:

Explicación, dise ño eimplementación de los algoritmos de

Needleman-Wunsch y WeinerNeedleman-Wunsch

• Weiner

Evaluaci´on afinada de similitud

• F´ormula Matem´atica de afinamientoSim (s1; s2) = Comm(s1; s2) - Diff (s1; s2) +Winkler (s1; s2)

• Sim (s1; s2) = Comm(s1; s2) - Diff (s1; s2)

Conclusiones

• 8.1. Conclusiones• 1. El m´etodo de soluci´on ha sido desarrollado parcialemente,

debido que para completar la ´ultima fase del modelo soluci´on es necesario realizar experimentos y obtener un par´ametro Q adecuado en base a estad´ısticas.

• 2. El uso de las f´ormulas desarrolladas en Giorgos [3] fueron ´utiles para modificarlos de acuerdo a las caracter´ısticas propias del trabajo, como eliminar la funci´on de mejoramiento que tiene otros fines para palabras muy largas, en este caso no pasan de los 140 caracteres.

• 3. El desarrollo del m´etodo soluci´on esta planteado adecuadamente para poder ser codificada y evaluada.

• 8.2. Contribuciones• Aplicaci´on de algoritmos bioinform´aticos al marketing on line para

encontrar palabras clave en la red social exitosa Twitter con millones de usuarios activos y miles de aportos por segundo, adem´as por usar m´etodos matem´aticos rigurosos para evaluar.

• 8.3. Trabajos Futuros• Puede complementarse con retroalimentaci´on para determinar si se

obtiene una palabra clave, es decir por los resultados obtenidos en cada ejecuci´on del modelo soluci´on se puede afinarse a´un m´as. Otro trabajo que puede realizarse es desarrollarlo on line, para el uso de los usarios interesados en saber las frases claves que resaltan en Twitter, actualemente se dispone de los denominados ’trendingtopic’ pero son s´olo palabras mas no frases.

GRACIAS