lunes, 24 de octubre de 2011

09.- Sistemas de clustering

Los sistemas de clustering son aquellos sistemas de recuperación que emplean algoritmos de agrupación de contenidos, por ello el proceso también puede adoptar otras denominaciones como categorización de los documentos de la colección. 
El concepto de clasificación de documentos refiere al problema de encontrar para cada documento la clase a la que pertenece, asumiendo que las clases están predefinidas y que se tienen documentos preclasificados para utilizar como ejemplos. En la presente tesis, se estudia la categorización o agrupamiento de documentos, entendiéndose por esto el proceso de encontrar grupos dentro de una colección de documentos basándose en las similitudes existentes entre ellos, sin un conocimiento a priori de sus características. (GOLDENBERG, D. 2007)
Algunos de los algoritmos empleados para efectuar los procesos de agrupación son: 
  • Categorización por objeto. El objetivo es encontrar agrupaciones entre todos los documentos que conforman la colección. Esto significa que un porcentaje de términos relevantes de un grupo de documentos deberá estar presente en todos y cada uno de ellos.
  • Representación vectorial. Cada documento de la colección se representa mediante vectores, quedando caracterizado por la frecuencia de aparición de los términos más relevantes y representativos. De esta forma se pueden comparar los vectores y agrupar los documentos en función de su similaridad.
    • Cálculo del Centroide. A partir de un grupo de documentos representados vectorialmente, se define el centroide que es el promedio de los vectores que componen el grupo. 
    • Reducción de términos a su raíz.
    • Eliminación de palabras vacías.
    • Eliminación de términos con bajo poder discriminatorio.
    • Eliminación de HAPAX.
  • Similaridad documental. Consiste en medir la distancia entre los vectores de cada documento para los que existen los algoritmos de:
    • Coeficiente del coseno. Cálculo del ángulo alfa. La semejanza entre los documentos se calcula como el producto vectorial entre ellos.
    • Otros: Jaccard, Distancia Euclideana, Coeficiente de Dice, Sorensen, Hamming, Tversky.
  • Métodos Jerárquicos. Emplean algoritmos que permiten caracterizar los documentos de la colección con una estructura arbórea denominada dendograma, quedando definidos los grupos con cada vértice del árbol representado. A partir de la raíz del árbol (conformada por un único grupo que contiene todos los documentos), la división por grupos se produce cuando se analiza en el documentoA qué otro documento tiene mayor presencia sus términos.
  • Métodos Particionales. En vez de trabajar a varios niveles para crear una estructura arbórea como en el caso anterior, se trabaja a un sólo nivel. Esto implica que el patrón de agrupación viene dado de antemano. Este factor establece las divisiones o partes con las que se calcula la similitud de los documentos.
  • Mapas auto-organizados. También denominado sistema de redes neuronales.
Bibliografía

Un ejemplo de Clustering: Carrot2
Carrot2 es un sistema de recuperación basado en técnicas de agrupación de documentos y contenidos web, sin requerir de bases de conocimiento externas como taxonomías o contenido preclasificado. Uno de sus algoritmos de agrupación es el correspondiente al método jerárquico, con los que es capaz de agrupar los contenidos de los motores de búsqueda Google o Bing. No obstante también puede emplearse para la recuperación de documentación dentro de un equipo cliente, siempre que disponga de una instalación previa "Google Desktop".

Para trabajar con Carrot2, se puede cargar su versión online desde el navegador web en la siguiente dirección: http://search.carrot2.org/stable/search. No obstante a efectos de probar todas sus posibilidades se recomienda la descarga de su versión carrot2-workbench-win32. Una vez descargado, descomprimir y ejecutar el archivo carrot2-workbench.exe.
  • Opciones de búsqueda.
    • Fuente. Se puede especificar qué base de conocimiento se desea utilizar para efectuar la búsqueda.
    • Algoritmo. Se permite la elección del algoritmo de agrupación de Carrot2. Por defecto se emplea Lingo, pero puede utilizarse K-mean, STC ó emplear los métodos habituales de agrupación por URL y fuente.
  • Páginas de resultados.
    • Clusters. Muestra un listado de todos los grupos identificados.
    • Documentos. Presenta un listado con los resultados más pertinentes de cada grupo.
  • Visualización.
    • Esquema relacional Aduna. (Aduna cluster map visualization). Muestra las relaciones entre unos grupos y otros.
    • Diagrama circular de grupos. (Circles visualization). Muestra una visión de los principales temas agrupados.
    • Mapa de superficie por grupos. (FoamTree visualization). Muestra un mapa de áreas con los grupos más pertinentes con colores cálidos en el margen superior de la imagen y los grupos menos relevantes en el margen inferior destacados con colores fríos. En la base del dibujo aparece el grupo desconectado "Other Topics".
  • Edición y configuración de atributos de consulta.
    • Grupos - Clusters
      • Cluster count base: Número que establece el factor base para la creación de grupos. Cuanto mayor sea el número mayor será el número de grupos que generará. No existe equiparación entre este número y el número de grupos, significa que a partir del factor base se creará un número proporcional de grupos.
      • Size-score sorting ratio: Establece el equilibrio entre la puntuación de los grupos y el tamaño según cantidad de documentos. Si toma valor 0 el algoritmo ordenará según tamaño. Si toma el valor 1 los resultados se ordenarán en función de un ranking de puntuaciones. Un valor intermedio tendrá en cuenta ambos factores.
    • Filtrado de etiquetas. Efectúa un proceso de reducción de los términos, eliminación de palabras vacías, números, términos interrogativos, para efectuar posteriores procesos de indexación más eficaces.
    • Etiquetas
      • Cluster label assignment method
        • Método único. Asigna etiquetas únicas para cada vector en cada grupo o cluster. De esta forma evita duplicaciones de grupos. Por este motivo, al requerir contrastar todos los vectores de todos los documentos entre sí, puede resultar un método lento pero más exhaustivo.
        • Método simple. Asigna etiquetas en todos los vectores de cada grupo contrastándolos mediante similaridad documental, obteniendo grupos duplicados y no duplicados. En tal caso finalmente se eliminan aquellos grupos con etiquetas duplicadas, quedando un resultado más reducido. Se trata de un método rápido, pero menos exhaustivo. 
      • Cluster merging threshold. Es el porcentaje de coincidencia entre los documentos de dos cluster para que se fusionen en uno. Si se utilizan valores bajos, significa que los grupos tendrán un mayor nivel de coincidencia, con un corpus muy parecido. Cuando mayor es el valor, más riesgos de que el grupo sea más heterogeneo.
      • Phrase label boost. Es el peso o puntuación específica que se otorga a varios términos cuando aparecen junto con otro. De esta forma se establecen relaciones de palabras o frases que siempre se recuperan juntas. Cuanto mayor sea el valor, mayor será la capacidad discriminatoria de las frases.
      • Phrase length penalty start. Número de palabras máximo antes de ser infraponderada la frase o grupo de palabras. 
      • Phrase length penalty stop. Si la frase supera el número máximo de palabras será eliminada.
      • Title word boost. Determina el peso que otorga a las palabras clave que coincidan con la consulta en el campo título.
    • Modelo de matriz
      • Factorization method. Es el método de factorización de la matriz de documentos.
        • Partial singular. Factoriza en función del número máximo de vectores K.
        • Factorization ED. Tiene en cuenta todos los factores de configuración de etiquetas, filtrado y clusters.
      • Factorization quality. Es el número de iteraciones del proceso de factorización.
      • Maximum matrix size. Determina el número máximo de elementos de cada matriz de cada documento
      • Maximum word document frequency. Determina la frecuencia máxima de las palabras en cada documento. Si la frecuencia supera a la especificada, la palabra será eliminada. El valor por defecto es 0,90 que indica 90%.
      • Term weighting. Determina el método para calcular el peso de las palabras del documento. Logaritmo de TF-IDF, Función lineal de TF-IDF o sólamente Factor TF.
    • Grupos multilingües
      • Default clustering language. Idioma por defecto para efectuar el proceso de agrupación.
      • Language aggregation strategy. Define la estrategia de agregación idiomática. Se puede establecer que efectúe un tratamiento de cluster para todos los idiomas, por idioma mayoritario ó creando grupos para cada idioma.
    • Extracción de frases
      • Phrase Document Frequency threshold. Umbral de la frecuencia de aparición de frases en documentos. Las frases con una frecuencia de aparición menor a la indicada serán ignoradas.
      • Truncated label threshold. Umbral de truncamiento en etiquetas. Valores bajos determinan grupos más grandes, ya que el factor de truncamiento de términos es más alto.
    • Preprocesamiento
      • Exact phrase assignment. Determina que los contenidos disponibles en cada agrupación coincidan con la consulta efectuada de forma exacta.
      • Merge lexical resources. Combina todas las palabras de todos los idiomas para formar parte del mismo lexicón de recuperación.
      • Minimun cluster resources. Define el número mínimo de documentos por grupo.
      • Reload lexical resources. Recarga todo el lexicón en cada consulta.
      • Word Document Frequency threshold. Umbral de frecuencia de los términos del documento, determina que cualquier término con un número de ocurrencias menor al especificado sea ignorado.

No hay comentarios:

Publicar un comentario

Nota: solo los miembros de este blog pueden publicar comentarios.