Algoritmos de agrupamiento star
| ||||
Algoritmo de agrupamiento Star. Están compuestas por un conjunto de algoritmos basados en grafos, los cuales se identifican por la creación de sub-grafos en forma de estrella. Mediante el se logra la agrupación de los documentos de acuerdo a su similitud.
Sumario
Técnicas de agrupamiento Star
Función de semejanza
Se denomina función de semejanza w a una función que asocia a cada par de objetos de un universo de objetos U= { 01,…, 0n } una magnitud que evalúa su semejanza o parecido.
Grafo de semejanza
Se llama grafo de semejanzas G = (V, E, w), al grafo completo donde los vértices (V) son los objetos a agrupar y las aristas se etiquetan con las semejanzas entre los objetos (E), calculada por una función de semejanza (w).
Objeto β-semejantes
Dos objetos cuya semejanza es mayor o igual que un cierto umbral β (definido por el usuario) se denominan β-semejantes. Si un objeto no es β-semejante con ningún otro objeto se denomina β-aislado.
Grafo de β-semejanza
Un grafo de β-semejanza se denota Gβ = ( V,Eβ ), el cual es un sub-grafo del grafo de semejanzas, donde se eliminan las aristas con peso menor que β, donde solamente quedan conectados los objetos semejantes.
Algoritmo Star
Desarrollado por Javed Aslam, el cual se basa en la construcción de un grafo de semejanza Gβ cuyos vértices representan a los documentos. De este grafo se obtienen los documentos estrellas o centros de clústeres que son los vértices del grafo que tengan mayor cantidad de aristas y el resto de los vértices son considerados satélites de estas estrellas.
Un sub-grafo en forma de estrella, es un sub-grafo de m + 1 vértices, en el cual existe un vértice llamado “centro", m vértices denominados “satélites" y se cumple que:
- El centro tiene un grado mayor o igual que el resto de los vértices del sub-grafo.
- Existe una arista del centro a cada uno de los satélites.
El problema de encontrar los sub-grafos en forma de estrella se reduce al problema de determinar el conjunto X de vértices centro. Este algoritmo presenta dos deficiencias significativas, siendo la primera de estas que el resultado de la agrupación está en dependencia del orden en que se realice el análisis de los vértices del grafo.
Y como segunda deficiencia es que independientemente del orden en que se realice el análisis de los vértices, se obtienen grupos “ilógicos”. Un grupo g1 se considera ilógico si cumple las siguientes condiciones:
- Existe un elemento e que pertenece a gi que es más denso que el vértice centro c que define a gi.
- El elemento e puede agrupar, si se considera como centro, a los vértices que son agrupados solo por el centro c.
Estas condiciones vienen dadas debido a que el algoritmo Star no permite que dos vértices adyacentes sean centros.
Algoritmo CStar
El algoritmo CStar introduce una nueva definición de sub -grafo, el cual es nombrado “sub-grafo en forma de estrella condensada”. Con este algoritmo se obtienen grupos que pueden tener traslape, manteniendo los puntos fuertes de sus predecesores y trabajando sobre las deficiencias anteriores.
La idea principal del algoritmo CStar es determinar un criterio que establezca cuándo un sub-grafo del tipo estrella condensada (EC) es más denso que otro y partiendo de éste, realizar un cubrimiento del grafo de β-semejanza utilizando los sub-grafos EC más densos y posteriormente aplicar un proceso de filtrado que reduzca la cantidad de éstos. Un problema que presenta este algoritmo es que puede obtener diferentes agrupamientos cuando se ejecutan sobre una misma colección, debido esto a que existe una dependencia del orden de análisis de los documentos entre otras características de este algoritmo.
Algoritmo CStar+
Se describe como una variante de su antecesor CStar. Este algoritmo utiliza sub-grafos EC para realizar un cubrimiento sobre las componentes conexas del grafo de β -semejanza. Transformando el problema de determinar un agrupamiento de Gβ usando sub-grafos EC en el problema de realizar un cubrimiento utilizando sub-grafos EC de cada componente conexa.
Es importante tener en cuenta que aunque obtener un cubrimiento de estas componentes a través de sub-grafos EC reduce el encadenamiento, también podría afectar la calidad del agrupamiento si dicha componente tiene un alto grado de conexión entre sus vértices, pues se estaría dividiendo en sub-grupos un grupo que ya es altamente cohesionado.
Este algoritmo también presenta el problema de su antecesor de que, se pueden obtener diferentes agrupamiento si se aplican en una misma colección de documentos.
Fuentes
- ASLAM, J. A.; PELEKHOV, E., et al. The Star Clustering Algorithm for Information Organization. 2006.
