Facultad de Ciencias Exactas
Universidad Nacional del Centro de la
Provincia de Buenos Aires (UNICEN)
Clasificación de Documentos Web
utilizando Marcadores Sociales
Tesis de Grado. Ingeniería de Sistemas
Nicolás A. Tourné
Directora: Dra. Daniela Godoy
Tandil, Argentina. 24 de Junio, 2011
Agenda
•
•
•
•
•
Introducción
Marcadores sociales en la Web
Recursos utilizados
Desarrollo de la investigación
Conclusiones
Agenda
•
•
•
•
•
Introducción
Marcadores sociales en la Web
Recursos utilizados
Desarrollo de la investigación
Conclusiones
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Introducción
Conclusiones
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Marco teórico
• Nuevo medio de comunicación: INTERNET.
• Surgimiento de data mining en los 90’s.
• A partir del rotundo crecimiento de la web, se comienza a
hablar de web mining.
• Las técnicas más utilizadas son clasificación y clustering.
PARADIGMA DE
APRENDIZAJE
EJEMPLOS
SISTEMA DE
APRENDIZAJE
CLASIFICADOR O
CATEGORIZADOR
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Contexto (1)
• Se llama web directory a un directorio organizado de
enlaces a otros sitios, estructurado con distintos niveles de
categorías.
• Se comienza a pensar en la “categorización automática”.
• Utilización de algoritmos de clasificación empleados en
otros dominios.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Contexto (2)
• El término Web 2.0: Colaboración e intercambio ágil de
información entre los usuarios.
• Surgimiento de los marcadores sociales.
• Beneficios en la categorización: A mayor información,
mejores predicciones.
delicious
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Propuesta
Evaluar si los marcadores sociales
son útiles para ser empleados en la
clasificación automática de
documentos web
Conclusiones
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Marcadores
sociales en la Web
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Las etiquetas (tags)
• Palabras claves asignadas a un recurso escogidas
libremente.
• No siguen regla formal de escritura.
• Significado “oculto”.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Tagging colaborativo
• Sistemas de clasificación colaborativa por medio de
etiquetas simples.
• Surgen de la participación de varios usuarios.
• Comúnmente se produce en entornos de software social.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Folcsonomía
• Significa clasificación gestionada por el pueblo.
• Se compone de anotaciones, cada una relacionada con tres
entidades (usuarios, tags y recursos) vinculados entre sí de
varias maneras.
• Varias deficiencias.
Usuario 1
Usuario 2
Tag 2
Tag 1
Tag 3
Tag 4
Recurso 1
Recurso 2
Recurso 3
Recurso 4
...
Recurso N
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
¿Qué son los marcadores sociales?
• Forma sencilla de almacenar, clasificar
y compartir enlaces en internet.
• Los usuarios guardan una lista de
recursos que consideran útiles.
• Los recursos son categorizados
mediante etiquetas o tags.
• Existe un gran número de servicios.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Recursos
utilizados
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Colección de datos CABS120k08
• Consiste en casi 120 mil URLs con metadatos adicionales
presentado en formato XML, basados en la intersección de:
500k random queries
Categorías
Tags
Anchors text
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Weka
• Software para aprendizaje automático y data mining
escrito en Java. Licencia GNU-GPL.
• Extensa colección de técnicas para pre-procesamiento de
datos.
• Herramientas de visualización y algoritmos para análisis de
datos y modelado predictivo.
• En la investigación se utilizaron los algoritmos Naive Bayes
y SMO.
• Formato de archivo plano ARFF.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Parser: CABS120k08 » ARFF
• Se ha construido en Java para convertir CABS120k08 a ARFF.
• Filtros aplicados a cada documento:
Reemplazar
código HTML
Documento
Eliminar
acentos
Eliminar
caracteres espec.
Aplicar
stemming
Eliminar
stop-words
Documento
filtrado
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Desarrollo de la
investigación
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resumen
• Procedimiento utilizado:
Generación
de datasets
CABS120k08.xml
Pre-procesam.
de c/ dataset
datasets
Clasificación
Optimizaciones
Análisis de
resultados
datasets
pre-procesados
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Generación de datasets
• Cada dataset está compuesto por los mismos 19.583
documentos, representados a partir de distintas fuentes de
información:
queries
queries +
anchor text
anchor text
queries +
tags
tags
anchor text +
queries +
tags
anchor text +
tags
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Análisis de resultados
• Primero, se decide cuál es el mejor clasificador:
- NaiveBayes
- SMO (PolyKernel)
- SMO (RBFKernel)
• Se utiliza la configuración por defecto para cada
clasificador: Percentage split (66%) y Cross-validation (10
folds).
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » NaiveBayes (1)
70%
57,92%
60,38%
60%
query
50%
anchortext
tags
40%
query+anchortext
30%
query+tags
anchortext+tags
20%
query+anchortext+tags
10%
0%
Percentage split, 66%
Cross-validation, 10 folds
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » NaiveBayes (2)
Precision
Recall
anchortext 51,8%
query 42,2%
tags 64,2%
anchortext 57,9%
+ tags
F-measure
query 46,7%
query+tags 60%
+anchortext
* Resultados empleando Percentage split (66%)
RAError
query 68,49%
anchortext 49,51%
+ tags
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » SMO (PolyKernel) (1)
64,34%
65,40%
70%
60%
query
50%
anchortext
tags
40%
query+anchortext
30%
query+tags
anchortext+tags
20%
query+anchortext+tags
10%
0%
Percentage split, 66%
Cross-validation, 10 folds
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » SMO (PolyKernel) (2)
Precision
Recall
query 45,8%
query 45,5%
tags 66,5%
tags 64,7%
F-measure
RAError
query 45,6%
query 96,66%
tags 65,6%
anchortext 94,89%
+ tags
* Resultados empleando Percentage split (66%)
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » SMO (RBFKernel) (1)
60%
49,67%
51,48%
50%
query
anchortext
40%
tags
30%
query+anchortext
query+tags
20%
anchortext+tags
query+anchortext+tags
10%
0%
Percentage split, 66%
Cross-validation, 10 folds
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Resultados » SMO (RBFKernel) (2)
Precision
Recall
anchortext 46,9%
anchortext 36,1%
tags 64,4%
query+tags 59,5%
+anchortext
F-measure
RAError
anchortext 40,8%
query 97,75%
query+tags 60,7%
+anchortext
query+tags 95,39%
+anchortext
* Resultados empleando Percentage split (66%)
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Selección del clasificador
• La performance de los clasificadores evaluados es la
siguiente:
SMO
(PolyKernel)
SMO
(RBFKernel)
NaiveBayes
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Elección del dataset ideal
• Pruebas realizadas con distintos % de entrenamiento.
anchortext+tags
85% inst. = 64,96%
70%
• Pocasquery
instancias de
entrenamiento,
pobres
anchortext
resultados
resultados clasificación
65%
60%
tags
55%
• Los tags
son el recurso
query+anchortext
de mayor
aporte a la clasif.
query+tags
50%
45%
anchortext+tags
• Las queries
perjudican la
query+anchortext+tags
clasificación
40%
35%
30%
25%
0%
20%
40%
60%
% instancias de entrenamiento
80%
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Optimizaciones
• Llevar a cabo una serie de cambios para lograr mejorar los
resultados de la clasificación.
• Se utiliza el categorizador SMO (PolyKernel) y Percentage
split como modo de entrenamiento.
• Se define un baseline.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#1 - Sin aplicar stemming (1)
• No se aplica stemming en la generación del dataset.
Reemplazar
código HTML
Documento
Eliminar
acentos
Eliminar
caracteres espec.
Aplicar
stemming
Eliminar
stop-words
Documento
filtrado
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#1 - Sin aplicar stemming (2)
baseline
85% inst. = 64,96%
resultados clasificación
70%
baseline
no stemming
65%
60%
55%
no stemming
85% inst. = 59,89%
50%
45%
0%
20%
40%
60%
% instancias de entrenamiento
80%
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#1 - Sin aplicar stemming (3)
• Existen casos como:
baseline = compute (53)
sin stemming = computer (28), compute (16),
computadora (8), computation (1)
Se descarta esta optimización
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#2 - Sinónimos (WordNet) (1)
• Encontrar sinónimos a cada término del dataset.
Reemplazar
código HTML
Documento
Eliminar
stop-words
Eliminar
acentos
Aplicar
stemming
Eliminar
caracteres espec.
Generar
sinónimos
Documento
filtrado
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#2 - Sinónimos (WordNet) (2)
baseline
85% inst. = 64,96%
resultados clasificación
70%
baseline
sinónimos
65%
60%
55%
sinónimos
90% inst. = 56,22%
50%
45%
0%
20%
40%
60%
% instancias de entrenamiento
80%
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#2 - Sinónimos (WordNet) (3)
• Si bien hubo casos donde los sinónimos fueron ventajosos
(ej. “globe” y “earth”), se incorporó demasiada información
para muchos otros términos.
computer = “computing machine”, “computing device”,
“data processor”, “electronic computer”
Se descarta esta optimización
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#3 - Spell-check (1)
• Corrección de los errores ortográficos encontrados.
Eliminar
stop-words
Reemplazar
código HTML
Documento
Aplicar
stemming
Eliminar
acentos
Eliminar
caracteres espec.
para cada
término
Aplicar
spell-check
Documento
filtrado
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#3 - Spell-check (2) » Tumba
spell-check Tumba
85% inst. = 70,12%
resultados clasificación
70%
baseline
spell-check Tumba
65%
baseline
85% inst. = 64,96%
60%
55%
50%
45%
0%
20%
40%
60%
% instancias de entrenamiento
80%
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#3 - Spell-check (3) » JaSpell
spell-check JaSpell
85% inst. = 71,25%
resultados clasificación
70%
baseline
spell-check JaSpell
65%
baseline
85% inst. = 64,96%
60%
55%
50%
45%
0%
20%
40%
60%
% instancias de entrenamiento
80%
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#3 - Spell-check (4) » Hunspell
spell-check Hunspell
85% inst. = 69,12%
resultados clasificación
70%
baseline
spell-check hunspell
65%
baseline
85% inst. = 64,96%
60%
55%
50%
45%
0%
20%
40%
60%
80%
% instancias de entrenamiento
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#3 - Spell-check (5)
• Los 3 spell-checkers mejoran los resultados del dataset
baseline.
Es JaSpell quien logra una pequeña diferencia con respecto
a sus pares.
Se acepta esta optimización
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#4 - Spell-check mejorado (1)
• La idea es mejorar el spell-check anterior. Evitar la pérdida
de términos cuando no existen sugerencias.
Reemplazar
código HTML
Documento
Eliminar
acentos
si
¿Abreviación?
términos
originales
Eliminar
caracteres espec.
para cada
término
incorrectos y
sin sugerencias
¿Traducción?
si
término
traducido
se descarta
el término
Aplicar
Spell-check
Aplicar
stemming
Eliminar
stop-words
Documento
filtrado
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#4 - Spell-check mejorado (2)
spell-check mejorado
85% inst. = 72,35%
resultados clasificación
70%
baseline
spell-check jaspell
65%
spell-check mejorado
60%
55%
50%
45%
0%
20%
40%
60%
80%
% instancias de entrenamiento
100%
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
#4 - Spell-check mejorado (3)
• Los resultados mejoran al spell-check anterior.
La mejora se debe a los nuevos términos presentes en el
dataset que antes eran descartados.
Se acepta esta optimización
(y reemplaza la anterior)
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Conclusiones
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Investigación (1)
Muchos investigadores coinciden que:
• Los tags proveen información adicional que no está
presente en los documentos mismos.
• Suponen que pueden ser útiles para la clasificación
automática de páginas web.
• Los tags son más diversos que los anchor-tags, pero
capturan información y significados desde distintos puntos
de vista.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Investigación (2)
Según esta investigación:
• Los tags efectivamente aportan valor a la clasificación
automática de documentos web.
• La fusión de tags y anchortexts resulta en la combinación
ideal para la generación del dataset.
• Según una clasificación individual para cada recurso:
1ro tags, 2do anchortext y 3ro queries.
Completar un poco más
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Extensiones
Existen diversas formas de mejorar los resultados:
• Filtrado de tags considerados subjetivos, resolver
problemas de sinonimia o polisemia.
• Utilizar las notas escritas por usuarios en Delicious.
• Considerar la “popularidad” de los documentos.
• Utilizar otros servicios donde se compartan links, como
Facebook o Twitter.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
Conclusiones
Trabajo futuro
• Muy relacionado con el campo de las búsquedas web. Por
ej. SafeSearch de Google.
• Personalización de búsquedas web: tags pueden ser útiles
para la desambiguación de palabras claves en una consulta.
• Sugerir categorías que expandan o refinen una búsqueda
web.
• Aplicación de categorización automática en ODP.
• En el área de marketing o publicidad.
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
¿Preguntas?
Conclusiones
Introducción
Marcadores sociales
Recursos utilizados
Desarrollo investigación
GRACIAS
Conclusiones
Descargar

Diapositiva 1