Algoritmos de agrupamiento star

Algoritmos de agrupamiento star Concepto: “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.

Técnicas 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. A continuación se realiza una descripción de los algoritmos que componen a dichas técnicas, especificando sus principales características, definiciones, bondades y deficiencias que presentan cada uno de ellos. Para lo mismo se necesitan tener conocimientos de los siguientes conceptos:

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 Extended Star

El algoritmo Extended Star, en español Estrella Extendida, fue desarrollado por Reynaldo J. Gil García, para dar solución a las deficiencias del algoritmo Star. Dicho algoritmo presenta las mismas características de su antecesor, pero realizando una nueva definición del vértice centro, el cual obtiene un conjunto diferente de estos y por lo tanto, un conjunto diferente de grupos. Este algoritmo plantea que, para ser vértice centro v debe tener un vecino o adyacente v´ el cual cumple con lo siguiente:

• v´ no tiene vértices centros adyacentes
• Si se considera a v´´ como el vértice centro de mayor grado que es adyacente a v´, entonces se cumple que v´´ tiene un grado mayor al de v.

Este algoritmo para determinar el conjunto de vértices que definen el agrupamiento además de utilizar el grado de los vértices trabaja con el grado complemento de los mismos. El grado complemento de un vértice v es la cantidad de adyacentes que tiene v que no pertenecen a ninguno de los grupos formados a partir de los vértices anteriormente incluidos en el conjunto. Sin embargo, el algoritmo Extended Star presenta deficiencias, y es que se pueden obtener grupos redundantes, esto se debe a que este algoritmo permite que más de un vértice que cumpla con las condiciones para ser centro sea considerado como tal.

Algoritmo Generalized Star

Propuesto por Ariel Pérez Suárez y José E. Medina, donde, manteniendo el planteamiento de Javed Aslam de que, el cubrimiento del grafo Gβ a través de sub-grafos en forma de estrella: permite obtener grupos con una semejanza relativamente alta entre los documentos que lo componen. Desarrollaron un nuevo concepto de sub-grafo en forma de estrella, posibilitando a este algoritmo a partir del cubrimiento del grafo con la nueva definición de sub -grafo, construir un conjunto de grupos que pueden ser solapados. Star, para la definición del sub-grafo utiliza solamente el grado de los vértices, mientras que el algoritmo Generalized Star define un grupo de conjuntos para cada uno de los vértices del grafo, el cual apoyado en estos define el sub-grafo en forma de estrella generalizada (EG), además de una heurística que define como sería el agrupamiento que se obtenga Los conjuntos de Satélites Débiles (SD) y Satélites Potenciales (SP) de un vértice v, se definen por las siguientes expresiones:
v.SD={ s v. Ady|| v. Ady | ≥ | s. Ady|}.
v.SP={ s v. Ady|| v. SD | ≥ | s. SD |}.
El grado SD y SP de un vértice v, se define como la cardinalidad de los conjuntos de satélites débiles y potenciales de v respectivamente. Teniendo en cuenta las definiciones anteriores, un sub-grafo en forma de estrella generalizada (sub-grafo EG) se define como un sub-grafo de m + 1 vértices, en el cual existe un vértice c denominado “centro" y m vértices llamados “satélites", cumpliéndose que existe una arista entre cada satélite y el centro satisface la siguiente expresión:
Para toda s que pertenezca a c.SP/c.SP/ >=/s.SP
El algoritmo Generalized Star posee algunas ventajas sobre sus predecesores, dando solución a algunas deficiencias del los mismos, no produce grupos ilógicos ni grupos redundantes. Pero también es importante tener en cuenta las deficiencias de este algoritmo. La primera de ellas es que elimina grupos densos previamente encontrados, lo cual puede afectar la calidad del agrupamiento realizado. Otra deficiencia está relacionada con el consumo de memoria por este algoritmo, y es que el mismo necesita calcular varios conjuntos para cada vértice, siendo estos los adyacentes, satélites débiles y satélites potentes, los cuales tiene que mantenerse almacenados en memoria hasta el final del algoritmo, pudiendo llegar a ser ineficiente con grandes colecciones de documentos.

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.

Conclusiones

Mediante el algoritmo Extended Star se logra la agrupación de los documentos de acuerdo a su similitud.

Fuentes

ASLAM, J. A.; PELEKHOV, E., et al. The Star Clustering Algorithm for Information Organization. 2006.