Download Recuperación de Información Lematización

Universidad de Costa Rica
Exposición: Clustering
Juan de Dios Murillo Morera
A37520
Miércoles 9 de Junio, 2004
Agenda









Motivación
Qué es clustering ?
Modelo
Conceptos importantes
Ejemplo
Algunos algoritmos utilizados
El algoritmo de árbol de sufijos(STC)
Resultados y evaluaciones de algoritmos de
clustering
Conclusiones
Motivación
Problema: La baja precisión del Web search engine hace dificil
para el usuario la tarea de localizar rapidamente la información
esperada
Solución:
Web Document Clustering
Qué es Clustering ?


Es un método alternativo que permite organizar los resultados
obtenidos a través de grupos de documentos(cluster base)
tomando en cuenta algún tópico en especial.
Según el artículo es una técnica para presentar los documentos
despúes de haberlos recuperado en grupos pequeños que
están relacionados por un tema en especial.
Modelo
clusters
Clustering
Engine
User
query
Search
Engine
Requerimientos principales




Relevance: método que produce clusters que
agrupan los documentos relevantes separandolos de
los irrelevantes.
Browsable Summaries: Cuando el usuario necesita
determinar si los contenidos de un cluster son de
interés
Overlap: Es importante por que se asigna un
documento a más de un cluster.
Snippets : Lista de documentos ordenadas por
orden de relevancia, relativamente pequeños.
Ejemplo # 1
Compartir frases en
un clustering es una
forma de resumir su
contenido.

Algunos algoritmos utilizados
Single-Pass: es el más popular de los algoritmos
incrementales, sin embargo tiene tendencia a producir
clusters largos.
 K-means: permite aplicar overlapping y es una
aproximación de GAHC.
 Buckshot y Fractionation : son más rápido que los
dos primeros
 STC: árbol de sufijos, a diferencia de los anteriores
tratan a los documentos como una secuencia ordenada
de palabras.

Suffix Tree Clustering (STC)
Es un algoritmo de cluster de tiempo lineal, que está basado en el
árbol de sufijos y el cual con eficiencia identifica el conjunto de
documentos que comparten frases comunes.
 El STC trata los documentos como un conjunto de strings y hace
uso de información próxima entre palabras.
 Resume el contenido de los clusters para los usuarios
 Es bastante rápido por que trabaja con un conjunto pequeño de
documentos en forma incremental e independiente.

Procedimiento de operación
1.
2.
3.
Pasos:
“Limpiar” los documentos
Identificar los clusters base
Combinar los clusters base
“Limpiar” los documentos
La cadena de texto que representa cada documentos es
transformado haciendo uso de un algoritmo de stemming.
 Se eliminan los prefijos y sufijos.
 Se pasa de plural a singular.
 Se eliminan los tags así como signos de puntuación.

Identificar los clusters base
Está compuesto de una raíz que direcciona el árbol
 Cada nodo interno tiene dos hijos.
 Cada línea entre nodos está etiquetada con un sub-string del
string(S).
 Ninguna de las aristas fuera del mismo nodo pueden tener las
etiquetas que comiencen con la misma palabra.
 Puede verse como la creación de un índice invertido.

Identificar los clusters
clusters base
base(cont)
Combinar los clusters base


Los documentos pueden compartir más de una frase.
Los documentos de distintas bases pueden aplicar overlap.
Phrase: cat ate
Documents: 1,3
Phrase: mouse
Documents: 2,3
a
d
Phrase: cheese
Documents: 1,2
c
b
e
Phrase: too
Documents: 2,3
Phrase: ate
Documents: 1,2,3
Clustering de clustering bases
f
Phrase: ate cheese
Documents: 1,2
Diagrama del árbol de sufijos
Dadas las siguientes cadenas
 Cadena1:
 Cadena2:
“mouse ate cheese too”.
 Cadena3:
“cat ate mouse too”.
cat
ate
a
cheese
1,1
Objetivo: Agrupar documentos que
“cat ate cheese”.
compartan temas comunes
ate
cheese
b
c
3,1
1,2
too
3,2
too
2,2
too
d
1,3
mouse
too
cheese
f
mouse
too
mouse
2,3
e
2,4
ate
cheese
too
too
2,1
3,3
3,4
Experimento # 1



Uso de frases para identificar los clusters.
Los clusters usan overlapping
72 % de los documentos fueron puestos en más de un cluster.
Se trabajaron 10 colecciones de documentos de 200 documentos.
STC
0.40
average precison

GAHC
Fractionation
Buckshot
0.30
K-means
Single-Pass
0.20
0.10
original list
0.00
algorithm
Experimento # 2
Las frases son claves para identificar los clusters así
como también el overlap.
STC
0.40
average precision

0.30
STC-nophrases
STC-nooverlap
0.20
0.10
0.00
algorithm
Experimento # 3

El uso de frases son claves en STC y el de palabras en el de GAHC.
La diferencia de K-Means entre el uso de frases y no uso de las
mismas es más pequeño en relación con el de STC.
0.5
single words
phrases
0.4
average precision

GAHC
K-Means
0.3
0.2
0.1
0
algorithm
STC
Experimento # 4
El impacto de K-Means y Buckshot en relación a overlap es
considerablemente pequeño.
0.4
no overlap
overlap allowed
Buckshot
average precision

0.3
K-Means
0.2
0.1
0
algorithm
STC
Experimento # 4 (cont)
Si los documentos aparecen en múltiples clusters:
1-) Es ventajoso si el doc es relevante.
2-) Es desventajoso si el documento es irrelevante.

Avg. num of clusters:
Relevant document.
Avg. num of clusters:
Irrelevant document
Ratio of the above
K-Means
1.40
Buckshot
1.40
STC
2.60
1.55
1.35
1.90
0.90
1.04
1.37
Propuesta de artículo de
investigación

Implementar un algoritmo de los
descritos y hacer un análisis de
resultados en términos de tiempo,
precisión, agrupamiento de documentos
etc.
Conclusiones




El clustering es un método de recuparar la información a través
del agrupamiento de documentos en base a temas específicos.
Una secuencia ordenada de palabras es mucho más
significativas que simples palabras claves.
El uso del custering facilitaría al usuario localizar rapidamente la
información esperada.
El STC es mucho más rápido que el uso tradicional de
clustering.
Gracias!!!