A blog about data, information and IT, by Mario Alberich

Mar 03
2008

Clustering en recursos corporativos y generalistas


Colecciones y algoritmos

la colección corporativa generada por unos pocos usuarios (denominado Labbies), y una selección de recursos etiquetados en del.icio.us, que se tomará como muestra de colección externa.

Se quiere analizar dos algoritmos que en último término deberían permitir la selección de etiquetas para facilitar la navegación por los recursos.

Los dos algoritmos utilizados se denominan tag co-ocurrence divisive clustering y betweenness centrality clustering.

En el primer caso se puede entender la co-ocurrencia como una correlación que hay entre dos tags (cuanto más coinciden en el etiquetado de recursos, más correlacionados están). Este algoritmo tiene efectos sobre entornos temáticamente relacionados, y no entra a fondo en la estructura general de la colección.

Al aplicar el algoritmo de la coocurrencia, las correlaciones inferiores a un determinado umbral (un valor mínimo) quedan descartadas por ser muy débiles. Tras este proceso de selección de relaciones, ya se puede visualizar la relación entre etiquetas, e identificar los subgrupos (clusters).

En el segundo caso se aplica un algoritmo que analiza el conjunto de caminos entre nodos. Dentro de estos caminos se seleccionan los arcos que forman parte de un mayor número de rutas más cortas, lo que implícitamente supone que son los más bien vinculados del conjunto. Computacionalmente, este segundo algoritmo es mucho más costoso, aunque existen métodos para la reducción de esta complejidad. A diferencia del algoritmo de coocurrencia, en este caso se prima más la visión de conjunto.

Seleccionando un tema de interés (en este caso, el uso del tag dspace) se recogen los datos de ambas fuentes. En el caso de del.icio.us se crea un subconjunto de datos fruto de un proceso de limpieza que consiste en tareas de homonimia/sinonimia y la eliminación de tags inherentemente ruidosos


Resultados para Labbies

Aplicando el algoritmo de co-ocurrencia se comprueba que el algoritmo prioriza la detección de tags relacionados o similares. Por lo tanto la "similitud" es el factor clave.

Por otro lado se identifica un conjunto de tags no afiliados completamente a un cluster, sino que más bien están a medio camino entre dos clusters diferentes. Estos tags normalmente se identifican con términos genéricos o ambiguos.

En el caso del algoritmo betweenness centrality se verifica que hay un grado menor de disgregación (menos clusters) pero también mayor homogeneidad de tamaño entre ellos.

No se puede determinar si hay uno de los dos algoritmos que sea más potente que el otro de cara a aumentar la recuperación de información en este entorno corporativo.


Resultados con del.icio.us

Al disponer de un número mayor de datos, el proceso de cálculo y visualización de los clusters de del.icio.us fue más largo y complejo.

Además de eso, se produce una generalización en la temática de cada cluster, incluyendo relaciones que semánticamente están alejadas.


Coocurrencia en del.icio.us

El resultado de aplicar este algoritmo es que se generan grandes clusters, que además presentan relaciones débiles. Esto viene dado por un efecto de "coche escoba": los ítems raros se acaban afiliando a una gran masa que acaba formando un cluster principal.

Para evitar este efecto, y con la ayuda de técnicas de visualización se aplica un umbral de co-ocurrencia de 0,142, que genera una agrupación mejorada, aunque conlleva el sacrificio de una gran cantidad de tags.

Este coeficiente demostró ser diferente para cada conjunto de datos (Labbies, del.icio.us y del.icio.us limpiado), lo que implica una mayor generalización.


Betweenness centrality en del.icio.us

En el caso de este algoritmo se generó un gran cluster que no se pudo desmembrar ni siquiera con técnicas de filtrado.

La principal consecuencia es que es mucho más complejo producir cluster de un tamaño adecuado para ser visualizables y favorecer a la navegación por tags como medio para la recuperación de información. Por lo tanto el algoritmo de betweenness centrality no es la mejor opción para descuartizar colecciones de etiquetas.


Enfoque futuro

El principal problema de la aplicación de algoritmos de clustering es que se generan grandes subgrupos. Esto representa un problema para la navegación del usuario. Por lo tanto, es interesante profundizar en las técnicas de división de estos macro-clusters. Conseguirlo permitiría una navegación más sencilla y una interficie menos cargada de información.

No lo apuntan los autores, pero quizá exista la posibilidad de aplicar iterativamente ambos algoritmos: betweenness a alto nivel y coocurrencia en clusters grandes). Quizá con una mínima heurística se podría llegar más al fondo de la cuestión.

Otro aspecto interesante al que se apunta es a la definición de jerarquías de clusters, lo que permitiría un primer nivel de macro-navegación (en forma de áreas temáticas generales), y luego profundizar en clusters temáticamente más delimitados.

Más allá del contenido del artículo, lo más interesante de este tipo de estudios es comprobar hasta qué punto afecta la selección de uno u otro algoritmo para la organización de la información (y en este caso a su recuperación). Como ejemplo aplicado a las colecciones de recursos, creo que es muy pedagógico.

Tags

gestión documental 10     Recuperación información 11     Linux 7     Usabilidad 5     open source 3     Tagging 12     lógica borrosa 2     fuentes de información 12     Google 6     off-topic 6     spam 2     grafos 6     Web social 11     modelización 12     Productividad 11     buscadores 2     utilidades 17     Profesionales 9     SEO 5     estándares 3     veracidad 3     relevancia 2     lingüística 2     PLN 2     lenguajes documentales 2     apis-mashups 3     reseñas 7     Flash 7     Gráficos estadísticos 13     Publicidad 3     Innovación 5     muestreo estadístico 9     PHP 14     internet 2     testeo 12     desarrollo 3     visualizacion 36     javascript 16     datos abiertos 9     elecciones 2     simulación 5     html5 7     phing 9     ssh 2     seguridad 3     indicadores 2     demografía 3     media 2     algoritmos 7     shell 4     mysql 2     backup 2     big data 6     twitter 2     d3js 11     revealjs 2     metodología 6     data-journalism 6     smartcities 2     NYT 2     privacidad 3     benchmarking 4     recopilaciones 21     magento 5     formacion 2     github 2     HHVM 3     psicología 2     angularjs 3     grep 2     nodejs 5     promises 2     mapreduce 3     crossfilter 2     exploración de datos 2     machine learning 2    

© 2007 and beyond Mario Alberich, licensed under CC-BY-SA unless stated otherwise.