Algoritmos de agrupamiento star
| ||||
Sumario
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.
Religion
Bueno,ellos no tienen ninguna religion a no ser a de los Friki,son dos jovenes que les gusta la moda de los friki y de los reparteros,despues de eso ya no tienen mas ninguna religion,son dos chicos que se denominan a si mismos como creyentes de Dios pero a su manera..
Ultimos Discos
Su ultimo disco salido al aire en el 2015 fue el de (La H y la T)estos fueron sus 5 discos actual mente que tienen.. 1-Mucho mas Problema 2-Mienteme 3-La H y la T 4-Estoy para ti 5-Te ves vien Muchos piensan que son unos chicos extrobertidos,pero no es asi,el 8 de uctubre del 2015 su consierto fue en Guaimaro la cansiones mas solisitadas fueron,Usted me Engaño,Yo soy tu Maestro,Como Podre,Saca Sacude y Me tienes que olvidar
Gustos
Armando Serrano Reyes,dice que sus gustos son muchos y resumio brebemente sus gustos,le gusta mucho salir de fiesta con sus amigos y amigas,le gusta mucho darle lujos a su novia,le encanta el futbol y es fans al FC Barcelona,le encanta ayudarle a su madre en lo que pueda a pesar de que este lojos de ella...
Helkis Cisnero Reyes,es un poco mas serio,es fan al FC Barcelona,no le gusta mucho salir a las fiestas le gusta escuchar musica de reparteros al igual que su primo,le gusta darle consejos a su primo sobre las mujeres,dice que el es un chico un poco serio pero que tiene sentido del umor tambien..
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.
