Ejemplo numérico de Agrupamiento K-medias

By Kardi Teknomo

Translated by Jaime Orjuela (Escuela Colombiana de Ingeniería)

<Previous | Next | Contents>

El proceso de agrupamiento k-medias es simple, Inicialmente se determina el número de grupos K y se asume el centroide o centro de esos grupos. Para determinar los centroides hay dos alternativas prácticas: la primera es tomar de forma aleatoria K objetos como centroides iniciales y la segunda es tomar los primeros K objetos en secuencia.

Luego el algoritmo ejecuta los siguientes tres pasos hasta que alcance el criterio de convergencia, es decir que los objetos no se muevan de grupo.

1. Se determina el o los centroides iniciales de acuerdo al número de cluster esperado.
2. Se determina la distancia de cada objeto con relación a los centroides
3. Se agrupan los objetos con base en la distancia mínima.

El ejemplo numérico mostrado a continuación es dado para entender una simple iteración. Puede descargar la implementación del ejemplo numérico en Matlab aquí . Otro ejemplo de agrupamiento k-medias usando Visual Basic está disponible aquí . El mismo ejemplo en MS Excel puede ser descargado al final de esta página.

Supóngase que se tienen cuatro tipos de medicina con dos atributos (peso e índice PH) como se muestra en la siguiente tabla:

Cada medicina puede ser representada como un punto en un espacio coordenado:

•  Valor inicial de los centroides: Sean C1 y C2 los centroides de los k-grupos. Si se eligen las medicinas A y B como los primeros centroides que quedan en los puntos (1,1) y (2,1).

•  Distancia de cada objeto a los centroides: Se calcula la distancia de cada objeto utilizando la distancia euclidiana , así por ejemplo la distancia entre la medicina C (4,3) y el primer centroide (1,1,) es , y su distancia con el segundo centroide (2,1) es . Resultando en la primera iteración la siguiente matriz de distancias:

•  Agrupación: Se asigna entonces cada objeto a cada grupo teniendo en cuenta el mínimo error de partición de cada elemento en cada grupo, entonces la medicina A se asigna al grupo 1 (con centroide en (1,1)) y las medicinas B, C y D al grupo 2 (con centroide en (2,1)).

•  Iteración 1, determinar centroides: Conociendo los miembros de los grupos, se vuelve a calcular el centroide de cada grupo y la matriz de distancias. Como el grupo 1 tiene sólo un miembro el centroide de ese grupo permanece en (1,1). El grupo 2 tiene ahora 3 miembros, por lo que el nuevo centroide es:

.

•  Iteración 1, Distancia de los objetos a los centroides: Nuevamente se calculan la distancia para todos los objetos con base en los nuevos centroides, similar al paso 2. Obteniendo las siguiente matriz de distancias:

•  Iteración 1, Agrupación de Objetos: Similar al paso 3, se asigna nuevamente cada objeto a cada grupo teniendo en cuenta el mínimo error de partición de cada elemento en cada grupo, entonces ahora las medicinas A y B quedan asignadas al grupo 1 (con centroide en 1,1) y las medicinas C y D al grupo 2 (con centroide en 11/3,8/3).

•  Iteración 2, determinación de Centroides: Repitiendo el paso 4, Se recalculan los centroides:

•  Iteración 2, Distancia de los objetos a los Centroides: Repitiendo el paso 2, Se recalcula la matriz de distancias:

•  Iteración 2, Agrupación de Objetos: Nuevamente se asignan los objetos en cada grupo basado el criterio de mínima distancia:

Los casos de entrada tendrán bajo esta nueva iteración la misma clasificación, concluyéndose que el cálculo de centroides se ha estabilizado, y no es necesario continuar iterando.

Ver más en: Datos multivariados (hasta n dimensiones) y otros tipos de distancia aquí

Nota:

Zlatan Aki Mur, un investigador AI independiente de Croacia ha contribuido con el Archivo de MS Excel basado este ejemplo. Usted puede descargar el ejemplo aquí

<Previous | Next | Contents>

These tutorial is copyrighted.

Preferable reference for this tutorial is

Teknomo, Kardi. K-Means Clustering Tutorials. http:\\people.revoledu.com\kardi\ tutorial\kMean\