Numerical Cruncher

Clustering

Algoritmo basado en la matriz de similaridad

El principal inconveniente de la mayor parte de los algoritmos heurísticos es su dependencia del orden en que se le presentan los patrones. Los métodos basados en grafos, igual que los algoritmos GRASP, intentan evitar este hecho pero su coste computacional los hace inaplicables en muchas ocasiones.

La matriz de similaridad

La matriz de similaridad se emplea para mostrar el grado de similaridad entre un conjunto de patrones. Se construye una matriz S simétrica de tamaño NxN, siendo N el número de patrones del conjunto de entrenamiento. S[i,j] toma el valor 1 si la distancia entre los patrones i y j queda por debajo de un umbral preestablecido . En caso contrario, S[i,j] vale 0. Por lo tanto, con un bit por celda podemos almacenar la matriz de similaridad.

Agrupamiento basado en la matriz de similaridad

Mientras queden patrones en la matriz de similaridad S

1. Seleccionar la fila i de la matriz de similaridad S que contenga más unos. Si hay varias, escoger una al azar.
   
2. Crear un agrupamiento con los patrones j tales que S[i,j] = 1
   
3. Añadir al agrupamiento todos aquellos patrones k tales que S[j,k] = 1, siendo j un patrón incluido en el nuevo agrupamiento hasta que no se puedan añadir más patrones a dicho agrupamiento.
   
4. Reducir la matriz de similaridad: Eliminar de S todas las filas y columnas correspondientes a patrones incluidos en el agrupamiento recién creado.