Algoritmos jerárquicos

Algoritmos jerárquicos Campo al que pertenece Reconocimiento de patrones

Los algoritmos de agrupamiento jerárquicos se utilizan para el agrupamiento de patrones de los cuales se desconoce la organización interna que tienen, es decir, no existe conocimiento acerca de la etiqueta de clase a la que pertenecen. Estos algoritmos trabajan uniendo o dividiendo en cada paso o iteración el par de grupos más semejante.

Cómo trabajan

Los algoritmos jerárquicos producen una secuencia anidada de particiones del conjunto de objetos, es decir, los grupos se organizan de forma jerárquica y cada grupo (cluster) puede verse como la unión de otros grupos (clusters), obteniendo así distintos niveles de jerarquía de grupos. Esta organización jerárquica es representada tradicionalmente por un árbol llamado dendrograma, el cual proporciona una taxonomía o índice jerárquico de la información procesada.

Clasificación

Estos algoritmos, atendiendo a la forma en que crean la jerarquía, se subdividen, a su vez, en divisivos o aglomerativos.

Algoritmos jerárquicos divisivos

Los algoritmos jerárquicos divisivos comienzan considerando el conjunto de objetos como un grupo y en cada iteración dividen un grupo en dos hasta que queden tantos grupos como objetos individuales existen en la colección o hasta que se cumpla un determinado criterio de parada.

Algoritmos jerárquicos aglomerativos

Por otra parte, los algoritmos jerárquicos aglomerativos basados en distancias comienzan considerando a cada objeto como grupos unitarios y en cada iteración se unen los dos grupos más cercanos hasta que se obtenga un único grupo o hasta que se cumpla un criterio de parada determinado. Los algoritmos jerárquicos aglomerativos se diferencian entre sí por la forma en que calculan la distancia entre los grupos. Dos de los principales representantes de este tipo de algoritmo son Single Link y CURE.

Criterios de parada

Los criterios de parada más empleados en las estrategias jerárquicas aglomerativas son: cuando se obtengan c grupos o cuando la distancia entre el par de grupos más cercanos sea mayor que un umbral dado.

Ejemplo de funcionamiento

En la imagen superior se representa un dendrograma en el cual se muestra cómo se realiza el proceso de agrupamiento de nueve objetos utilizando algoritmos aglomerativos, pues se parte de la idea de considerar a cada objeto como un grupo unitario y luego ir uniendo los grupos más semejantes hasta obtener un solo grupo.

Ver además

• Algoritmo de ordenamiento
• Algoritmo de búsqueda
• Algoritmo de Kruskal
• Algoritmo de Euclides
• Algoritmo de Prim
• Algoritmo de Boruvka
• Algoritmo de Gutmann
• Algoritmo criptográfico
• Algoritmo de Ordenamiento Burbuja
• Algoritmo de Ordenamiento Shell
• Algoritmo genético
• Algoritmo de ordenamiento por selección
• Algoritmo de árboles de decisión de Microsoft
• Algoritmo de Búsqueda Heurística A*
• Algoritmo asimétrico
• Algoritmos Avidos
• Algoritmos de clasificación no supervisada

Fuentes

Facultad de Matemática y Computación de la Universidad de Oriente.