Universidad de Costa Rica
Maestría en Computación e Informática
Recuperación de la Información
Profesor: Msc. Edgar Casasola
Suffix Tree Clustering (STC)
Basado en el artículo:
“Web Document Clustering: A Feasibility Demostration”
Oscar Rivera Céspedes
Carné: A37523
Introducción
Los sistemas de RI convencionales:
• Retornan una larga lista de documentos
• No existe relación explícita de igualdad entre los documentos
• Los usuarios se ven forzados a recorrer esta lista
• Los resultados, por lo general, poseen baja precisión
• El usuario recorre un bajo porcentaje de la lista.
Estos factores impiden a los usuarios localizar la
információn que buscan.
Motivación
Desarrollar un algoritmo que permita agrupar los documentos
devueltos por un buscador, como respuesta a una consulta,
de manera que los elementos dentro de cada grupo sean
lo mas homogéneos posible y los grupos sean lo mas
heterogéneos posible entre ellos.
El algoritmo debe satisfacer los siguientes requisitos:
• Relevancia
• Fácil Navegación
• Permitir Traslapes
• Tolerancia para funcionar con trozos de documentos
• Velocidad
• Incrementabilidad
Trabajo previo sobre Clustering de Documentos
• Utilizado para mejorar la eficiencia de la búsqueda.
(proceso previo a la búsqueda).
• Los algoritmos tradicionales son lentos. O(n2) u O(n)
• Los criterios de parada del algortimo son arbitrarios.
• Son sensitivos al criterio de parada.
• Son sensitivos al ruido o valores atípicos.
• La mayoría no permiten que un elemento pertenezca a
mas de un grupo.
• No son incrementales.
• Tratan a los documentos como conjuntos de palabras
y no como una secuencia ordenada de palabras.
Suffix Tree Clustering un nuevo esquema
• Algoritmo de clustering con desempeño de tiempo lineal O(n)
• Identifica frases comunes a los documentos
• Trata a los documentos como frases o “strings”
• Incremental
• Utiliza un árbol de sufijos como estructura de datos base.
• Permite el traslape
• El algoritmo consta de 3 etapas:
1. Limpiar los documentos
2. Identificar los clusters base usando un árbol de sufijos
3. Combinar los clusters base en clusters
Paso 1. Limpiar los documentos
• Utilizar un algoritmo de stemming “liviano”
1. Borrar Prefijos
2. Borrar Sufijos
3. Cambiar plural a singular
• Marcar los límites de las oraciones
• Eliminar símbolos no relevantes (“tags”, números,
símbolos especiales).
• El texto original se mantiene inalterado para futuras refencias
o para mostrar posteriormente la fuente de los resultados.
Paso 2. Identificar los cluster base
• Consiste en crear un índice invertido para las frases
• Se puede hacer eficientemente con un árbol de sufijos
• Esta estructura se pueden construir en tiempo lineal, respecto
a la colección de documentos.
• Puede crearse incrementalmente conforme se leen los
documentos.
• Los documentos se tratan como frases pero en el sentido
de una secuencia ordenada de palabras y no como un
conjunto de palabras
Paso 2. Identificar los cluster base
Se debe crear un árbol de sufijos para los documentos
Se puede ver como un índice invertido
Características de un árbol de sufijos para un string S:
1. Tiene una raíz y es dirigido
2. Cada nodo interno tiene al menos 2 hijos
3. Cada arista se etiqueta con un “substring” no vació de S
4. La etiqueta de un nodo es la concatenación de las etiquetas
de las aristas que llevan a dicho nodo.
5. Para cada sufijo s de S, hay un nodo sufijo cuya etiqueta
es s.
Paso 2. Identificar los cluster base
Arbol de sufijos para el conjunto de “strings”:
• “cat ate cheese”
• “mouse ate cheese too”
• “cat ate mouse too”
Un cluster base es aquel que contiene dos o mas documentos
Paso 2. Identificar los cluster base
Calificación de los cluster base: (fórmula de ranking)
• A cada cluster base se le asigna una calificación
• Es una función del número de documentos que contiene
• La calificación s(B) del cluster base B con frase P es:
s(B) = |B| * f(|P|)
|B| = # de documentos en el cluster base B
|P| = # de palabras en P que no tienen calificación 0
f = función que penaliza a las frases de una sola palabra,
es lineal para frases de 2 a 6 palabras y constante
para frases mayores
Paso 3. Combinando los cluster base
Dados dos cluster base Bn y Bm, con tamaños | Bm| y | Bn|.
Sea | Bm Bn| el número de documentos comunes.
La similaridad entre Bn y Bm se define:
1 si:
| Bm Bn| / | Bm| > 0.5 y
| Bm Bn| / | Bn| > 0.5
0 en cualquier otro caso
Paso 3. Combinando los cluster base
1 si:
| Bm Bn| / | Bm| > 0.5 y
| Bm Bn| / | Bn| > 0.5
0 en cualquier otro caso
Experimentos
Contendientes de STC:
Ninguno es incremental y tratan los documentos como
conjuntos de palabras y no como una secuencia ordenada
de palabras
• GAHC (Group-Average Agglomerative Hierarchical Clustering)
• K-means
• Buckshot
• Fractionation
• Single pass
Experimentos
GAHC
• O(n2)
• Sensible al criterio de parada
• Sensible al ruido
• No permite traslapes
K-means
• Tiempo lineal, O(nkT). k = # clusters, T número de iteraciones
• No permite traslape de clusters
Single Pass
• Tiempo lineal, O(nk)
• Es el algoritmo incremental mas popular
• Tiende a producir clusters grandes
• Permite traslapes
Experimentos
Fractionation
• Rápido, de tiempo lineal
• Permite el traslape
• Es sensitivo al criterio de parada.
• Es sensitivo a valores atípicos
Buckshot
• Tiempo lineal
• No permite el traslape
• Los centroides se calculan tomando una muestra.
• Peligroso cuando se esta interesado en clusters pequeños
y estos no estan representados en la muestra.
Experimentos
Metodología
• Se definieron 10 consultas con sus tópicos y descripciones
• De los tópicos se tomaron las palabras claves para hacer
las búsquedas
• Se generaron 10 colecciones de 200 trozos (documentos)
cada una .
• Para cada trozo se bajo el documento completo.
• Manualmente se asigno una relevancia a todos los documentos.
• En promedio por cada colección había 40 documentos
relevantes (20 % del total de 200 documentos por consulta)
• Las consultas se realizaron en un meta buscador
(MetaCrawler.)
• Todos los algoritmos corrieron hasta producir 10 clusters.
Experimentos
Promedio de precisión
STC obtiene los mejores resultados porque:
• Usa frases (como una secuencia ordenada de palabras
y no como un conjunto de palabras) para identificar los clusters.
• Permite el traslape (cada documento fue colocado
en promedio en 2.1 clusters)
Experimentos
Promedio de precisión
• La utilización de frases y traslape son factores
vitales en el desempeño del algoritmo STC
Experimentos
Promedio de precisión. Algoritmos con
palabras simples y con frases
Promedio de precisión algoritmos con
traslape y sin traslape
• ¿Son la utilización de frases y traslape factores sensibles en los demás
Algoritmos o solo para STC?
• ¿Podría beneficiarse o empeorar el desempeño al adaptar los algoritmos
para que utilicen estas “mejoras”?
Experimentos
Promedio de precisión. Trozos vs Documentos completos
¿El desempeño es bueno a pesar de que no se utilice el documento
completo sino solamente trozos de él? Sí.
Factores que influyen:
• Los trozos que retornan los buscadores parecen ser significativos
y contienen acertadamente la mayoría de la información clave.
• Los trozos tienen menos “ruido” que los documentos completos
Experimentos
Tiempo de ejecución vs número de trozos
STC es bueno porque:
• Tiempo de ejecución lineal
• Es incremental (no necesita tener toda la colección para empezar
a procesarla)
Conclusiones
• Satisface los 6 requerimientos que debe cumplir el Cluster para Web
1. Relevancia
2. Traslape
3. Tolerancia a los trozos
4. Velocidad
5. Incrementabilidad
6. Fácil navegación
• Se demostró que es posible la utilización de cluster en la Web
• Utilizar los trozos que devuelven los buscadores es una alternativa
razonable y rápida
• Bajo la metodología utilizada STC sugiere ser un buen algoritmo
de clustering para Web
• El traslape y el uso de frases como una secuencia ordenada de
palabras son factores de mucho peso en STC no así en los
demás métodos.
Descargar

Presentación de PowerPoint