centro nacional de investigaciÓn y … rosy ilda... · rosy ilda basave torres director de tesis...
Post on 22-Sep-2018
219 Views
Preview:
TRANSCRIPT
S.E.P. S.E.S. D.G.E.S.T.
CENTRO NACIONAL DE INVESTIGACIÓN
Y DESARROLLO TECNOLÓGICO
cenidet
MEJORAMIENTO DE LA EFICIENCIA Y EFICACIA DEL ALGORI TMO DE AGRUPAMIENTO K-MEANS MEDIANTE UNA NUEVA CONDICIÓN D E
CONVERGENCIA
T E S I S QUE PARA OBTENER EL GRADO DE: MAESTRO EN CIENCIAS EN CIENCIAS DE LA COMPUTACION
PRESENTA ROSY ILDA BASAVE TORRES
DIRECTOR DE TESIS DR. JOAQUÍN PÉREZ ORTEGA
CODIRECTOR DE TESIS
DR. VÍCTOR JESÚS SOSA SOSA
CUERNAVACA, MORELOS AGOSTO 2005
DEDICATORIA
Dedico esta tesis especialmente a mi Chenda (Roselena Arroyo Basave) por el
enorme amor que nos une sólidamente.
A mis padres Sr. Carlos Basave Guadarrama y Sra. Imelda Torres Torres por su
apoyo y amor incondicional durante toda mi vida.
A mis hermanos José, Raful, Teresa, Dora Luz, Maria Elena, Maria Isabel, Antonio
y Eliud por el amor tan grande que siempre me han demostrado.
A Edwin Beutelspacher Santiago por ser un enorme apoyo al final de este camino.
A mis tíos Guadalupe Banderas Torres y Roberto Banderas Torres, por su apoyo
moral y sus constantes esfuerzos de conservar sólidos los lazos familiares.
ii
RECONOCIMIENTOS
Mi profundo agradecimiento a los miembros del comité tutorial de esta tesis:
Dr. Rodolfo A. Pazos Rangel, Dr. Guillermo Rodríguez Ortiz, Dr. Joaquín Pérez
Ortega, Dr. Mario Guillen Rodríguez, y Dr. Víctor Jesús Sosa Sosa.
En especial, mi sincero aprecio al Dr. Joaquín Pérez Ortega y Dr. Víctor Jesús
Sosa Sosa por haber dirigido esta tesis por sus valiosas sugerencias, críticas y
tiempo dedicado.
Al Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET) por la
oportunidad de realizar mis estudios de maestría.
Al Consejo del Sistema Nacional de Educación Tecnológica (CoSNET) por
brindarme el apoyo económico durante los estudios de maestría.
Estoy en deuda con el Instituto Tecnológico de Ciudad Madero (ITCM) que
proporcionó las facilidades necesarias para esta investigación.
A la Dra. Laura Cruz Reyes y el Dr. Héctor Joaquín Fraire Huacuja por su gran
apoyado y amistad.
Finalmente, doy gracias a mis compañeros del (CENIDET) y (ITCM) por su ayuda,
soporte moral y amistad. Para ellos mi estimación.
iii
RESUMEN
En esta tesis se propone un mejoramiento al algoritmo K-means estándar. Se han
realizado numerosos mejoramientos al algoritmo, la mayoría relacionados con los
valores de los parámetros iniciales, en contraste, en este trabajo se hace una
aportación a la condición de convergencia.
Se implementó computacionalmente el algoritmo K-means estándar y un
generador de casos de pruebas. Para validar la implementación del algoritmo
K-means estándar se realizaron pruebas con datos sintéticos generados en esta
tesis. Los resultados fueron contrastados con los resultados de los algoritmos
K-means que proporciona el paquete comercial SPSS y la herramienta Weka, los
cuales llegaron a la misma agrupación.
Con el propósito de estudiar el algoritmo K-means estándar se le introdujo
código para darle seguimiento al algoritmo al tiempo de ejecución, se realizó una
experimentación con la base de datos Diabetes y se observó que el algoritmo
estándar no convergía en el óptimo local hasta en un 96% de las corridas, lo cual
mostró una posibilidad de mejorar el algoritmo en la condición de convergencia. La
nueva condición propuesta en esta tesis, consiste en parar el algoritmo cuando se
encuentra un mínimo local o bien cuando ya no hay intercambios de elementos
entre los grupos.
Para probar la mejoría del algoritmo se resolvieron seis bases de datos
reales de aprendizaje máquina y una base de datos del problema Bin-packing
usada y generada en la tesis doctoral [Cruz 2004]. Los resultados se contrastaron
con SPSS, Weka y el algoritmo K-means estándar. En todos los casos evaluados
el algoritmo propuesto obtuvo resultados mejores o iguales. El algoritmo
propuesto obtuvo una mejoría en eficiencia hasta de un 82 % y en eficacia hasta
de un 33%
iv
TABLA DE CONTENIDO
Página
LISTAS DE FIGURAS........................................................................................
LISTAS DE TABLAS..........................................................................................
vii
viii
Capítulo
1 INTRODUCCIÓN………………………………………………………………… 1
1.1 MOTIVACIONES...................................................................................
1.2 DESCRIPCIÓN DEL PROBLEMA DE INVESTIGACIÓN……..............
1.3 OBJETIVO DE LA TESIS......................................................................
1.4 CONTEXTO DE LA INVESTIGACIÓN..................................................
1.5 TRABAJOS RELACIONADOS…………..………………………………..
1.5.1 [Su 2004]…………………………………..…………………………..
1.5.2 [Likas 2003]……………………………………………………………
1.5.3 [Hamerly 2002]………………………………………………………..
1.5.4 [Su 2001]………………………………………………………………
1.5.5 [Pelleg 2000]…………………………………………………………..
1.6 OTROS TRABAJOS………………………………………………………..
1.6.1 [Ordonez 2004]……………………………………………………….
1.6.2 [Kanungo 2002]……………………………………………………….
1.7 ANÁLISIS COMPARATIVOS……………………………………………...
1.8 ORGANIZACIÓN DEL DOCUMENTO……………………..…………….
2
2
2
2
3
3
4
4
5
5
5
5
6
6
7
2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN.………..…………………….. 8
2.1 K-MEANS ESTÁNDAR..........................................................................
2.1.1 Definiciones y notación…………………………............................
2.2 ALGORITMO K-MEANS ESTÁNDAR....................................................
2.2.1 Parámetros del algoritmo…..……………………………………….
2.2.2 Pasos del algoritmo.....................................................................
2.2.3 Características del algoritmo K-means estándar…………………
2.3 IMPLEMENTACIÓN Y ANÁLISIS EL ALGORITMO K-MEANS
ESTÁNDAR………………………………………………………………….
9
9
12
12
12
12
15
v
2.3.1 Implementación del algoritmo K-means estándar………………...
2.3.2 Software comercial SPSS……………………………………………
2.3.3 Herramienta Weka……………………………………………………
2.3.4 Resultados experimentales del algoritmo implementado.............
2.3.4.1 Validación experimental de la implementación del
K-means estándar…………………………………………………
2.3.4.2 Experimentación con una base de datos…………………..
16
16
17
17
17
20
3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS................... 22
3.1 ANÁLISIS DETALLADO DEL ALGORITMO K-MEANS
ESTÁNDAR...........................................................................................
3.1.1 Análisis del comportamiento para una corrida............................
3.1.2 Búsqueda de patrones en el comportamiento del algoritmo
K-means estándar con la base de datos
Diabetes......................................................................................
3.1.3 Comportamiento del algoritmo K-means estándar con siete
bases de datos …………………….....……………………………..
3.2 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
ESTÁNDAR…………………………………………………………………..
3.3 ALGORITMO DEL ALGORITMO K-MEANS MEJORADO……………..
23
23
24
28
29
30
4 RESULTADOS EXPERIMENTALES……………......................................... 32
4.1 DESCRIPCIÓN DE LAS BASES DE DATOS QUE SE USARON EN
LA EXPERIMENTACIÓN…………………………………………………..
4.1.1 Base de datos Bin-packing..........................................................
4.1.2 Base de datos Vehicle.................................................................
4.1.3 Base de datos Glass…….………………………………................
4.1.4 Base de datos Diabetes…………………………………………….
4.1.5 Base de datos Heart………………………………………..............
4.1.6 Base de datos Wine…………………………………………………
4.1.7 Base de datos Liver…………………………………………………
4.2 RESULTADOS EXPERIMENTALES.....................................................
4.2.1 Resultados de eficiencia ……..…………………...………………..
33
33
33
33
33
34
34
34
35
35
vi
4.2.1.1 Resultados para Bin-packing…..……………………………
4.2.1.2 Resultados para Vehicle……………………………………..
4.2.1.3 Resultados para Glass……………………………………….
4.2.1.4 Resultados para Diabetes……………………………………
4.2.1.5 Resultados para Heart. …………………............................
4.2.1.6 Resultados para Wine…..……………………………………
4.2.1.7 Resultados para Liver………...……………………………...
4.2.2 Análisis comparativo de eficiencia…………………………………
4.2.3 Resultados de eficacia………………………………………………
4.2.3.1 Resultados para Bin-packing……..…………………………
4.2.3.2 Resultados para Vehicle………………..……………………
4.2.3.3 Resultados para Glass……...………………………………..
4.2.3.4 Resultados para Diabetes……..…………………………….
4.2.3.5 Resultados para Heart…………..…………………..............
4.2.3.6 Resultados para Wine………..………………………………
4.2.3.7 Resultados para Liver…………………………...…………...
4.2.4 Análisis comparativo de la eficacia………………………………..
36
36
36
37
37
38
38
38
40
40
40
41
41
41
42
42
42
5 CONCLUSIONES Y TRABAJOS FUTUROS.............................................. 45
5.1 Conclusiones.........................................................................................
5.2 Trabajos Futuros....................................................................................
45
47
REFERENCIAS.................................................................................................. 48
Anexo A. Agrupamiento……………………………………………………............. 51
vii
LISTA DE FIGURAS 2.1 Pseudocódigo del algoritmo K-means estándar…………………..………... 14
2.2 Primera iteración de K-means estándar…………………………….……….. 18
2.3 Segunda iteración de K-means estándar……………………...…………….. 19
3.1 K-means pasa por un mínimo local y pierde su valor óptimo...….. ………. 25
3.2 K-means converge en un mínimo local……………………………..……….. 26
3.3 Pseudocódigo del algoritmo K-means mejorado…………………..……….. 31
A.1 Pseudocódigo del generador de bases de datos sintéticas……………….. 53
A.2 Calculando el primer grupo…………………………………………..……….. 55
A.3 Se genera una copia espejo en una dimensión…………………………….. 55
A.4 Copia los objetos para la segunda dimensión……………………..……….. 56
A.5 Grupos sintéticos generados………………………………………………….. 56
viii
LISTA DE TABLAS 1.1 Trabajos relacionados………………………………………………...…….. 7
2.1 Términos y notación…………………………………………………...…….. 10
2.2 Comprobación de la implementación del algoritmo K-means…….…….. 19
2.3 Corridas K-means estándar con la base de datos Bin-packing…..…….. 21
2.4 Resultados de la comparación K-means estándar usando Bin-packing 22
3.1 Salida de un mínimo y convergencia en una calidad menor con
Diabetes………………………………………………………………...……..
24
3.2 Experimentación de K-means estándar con Diabetes..………….. .……. 27
3.3 Porcentaje de corridas que no paran en un óptimo local………….…….. 29
4.1 Detalle de las bases de datos usadas para experimentación…….…….. 34
4.2 Resultados experimentales en eficiencia para Bin-packing……….……. 36
4.3 Resultados experimentales en eficiencia para Vehicle……….…...…….. 36
4.4 Resultados experimentales en eficiencia para Glass………….......……. 37
4.5 Resultados experimentales en eficiencia para Diabetes…………..……. 37
4.6 Resultados experimentales en eficiencia para Heart……………....……. 37
4.7 Resultados experimentales en eficiencia para Wine……………….……. 38
4.8 Resultados experimentales en eficiencia para Liver…………..…...……. 38
4.9 Análisis comparativo en eficiencia…………………………………...…….. 39
4.10 Resultados experimentales en eficacia para Bin-packing………....……. 40
4.11 Resultados experimentales en eficacia para Vehicle……………...…….. 41
4.12 Resultados experimentales en eficacia para Glass………………..…….. 41
4.13 Resultados experimentales en eficacia para Diabetes…………….……. 41
4.14 Resultados experimentales en eficacia para Heart…………….…..……. 42
4.15 Resultados experimentales en eficacia para Wine…...…………....……. 42
4.16 Resultados experimentales en eficacia para Liver………………....……. 42
4.17 Análisis comparativo en eficacia……………………..……………….……. 44
A.1 Notación y definiciones………………………………………………..…….. 52
A.2 Valores de entrada al generador de casos de pruebas…………....……. 54
1
Capítulo 1
INTRODUCCIÓN
En este trabajo se aborda el problema de agrupamiento de objetos con base a sus
atributos, el cual ha sido ampliamente estudiado debido a su aplicación en áreas
como: aprendizaje máquina [MacQueen 1967], minería de datos, descubrimiento
del conocimiento, comprensión de datos, reconocimiento de patrones y
clasificación de patrones [Witten 1999, Mehmed 2003, Jain 1999]. El objetivo del
agrupamiento es particionar un conjunto de objetos que tienen asociados vectores
multidimencionales de atributos, en grupos homogéneos, tales que los patrones
dentro de cada grupo sean similares entre sí [Berkhin 2002, Jain 1999, Halkidi
2001].
En las secciones de este capítulo se presenta un panorama general de la
tesis, el cual se inicia con la descripción de los motivos que llevaron a esta
investigación y se continúa con la definición del problema de investigación. En
seguida se explican los objetivos que se plantearon alcanzar. Se explica también
el contexto en el que se desarrolló este trabajo, se abordan los principales trabajos
relacionados a esta tesis, y finalmente se termina dando una descripción del
contenido de cada capítulo.
Capítulo 1 INTRODUCCIÓN
2
1.1 MOTIVACIONES
El agrupamiento de datos es la tarea de encontrar agrupamientos naturales en los
datos. Ésta es una tarea importante en varias áreas del conocimiento, tales como:
aprendizaje máquina, minería de datos, estadística y reconocimiento de patrones.
Típicamente en agrupamiento no hay una solución perfecta para el problema, pero
los algoritmos persiguen minimizar una función objetivo. Entre varios algoritmos de
agrupamiento K-means es uno de los más usados.
1.2 DESCRIPCIÓN DEL PROBLEMA DE INVESTIGACIÓN
En este trabajo se plantea el problema del mejoramiento la eficiencia y eficacia del
algoritmo de agrupamiento K-means.
1.3 OBJETIVO DE LA TESIS
El objetivo principal de esta investigación es estudiar a detalle el algoritmo de
agrupamiento K-means con el propósito de mejoría en su eficiencia y eficacia, ya
que es un algoritmo de propósito general, ampliamente usado en áreas como:
aprendizaje máquina, estadística, minería de datos y reconocimiento de patrones.
1.4 CONTEXTO DE LA INVESTIGACIÓN
En el Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET), se
han venido desarrollando trabajos en el área de diseño de la distribución de bases
de datos, y debido a su complejidad se presentó la necesidad de utilizar métodos
heurísticos para su solución.
En la tesis doctoral “Caracterización de algoritmos heurísticos aplicados al
diseño de bases de datos distribuidas” [Cruz 2004], se abordó el problema de
selección de algoritmos proponiendo una metodología basada en el aprendizaje
automático y la estadística, que permite identificar características críticas y sus
Capítulo 1 INTRODUCCIÓN
3
interrelaciones, lo cual posibilita que para cada algoritmo se determine un patrón
de agrupamiento de los casos que ha resuelto mejor. Para un nuevo caso se
determina a qué patrón de agrupamiento es más afín y se selecciona el algoritmo.
La metodología aborda el problema de agrupamiento para el problema de
distribución de objetos en contenedores (Bin-packing) y usa el algoritmo K-means.
Fraire, en su tesis doctoral “Una metodología para el diseño de la
fragmentación y ubicación en grandes bases de datos distribuidas” [Fraire 2005],
aborda el problema de la automatización del diseño lógico de una base de datos
distribuida. Él propone un nuevo enfoque de solución que considera que el
desempeño del proceso de automatización es un requisito crítico de la solución
práctica del problema. Este enfoque consiste en seleccionar, para un ejemplar
dado, una transformación de compresión. La hipótesis que sustenta es que, se
puede comprimir el ejemplar dado y usar la ejemplar resultante para obtener una
solución de buena calidad del ejemplar original. Para realizar esta transformación
se usaron técnicas de agrupamiento; es decir, cuando un ejemplar del diseño de la
distribución tiene operaciones repetidas, es posible transformarla en una con
menos operaciones.
En los dos trabajos anteriores se usaron técnicas de agrupamiento, como
parte de la solución de un problema más general. También se hizo evidente que
una contribución al problema de agrupamiento podría incidir en el mejoramiento de
los métodos de solución de los trabajos anteriores.
1.5 TRABAJOS RELACIONADOS
En la siguiente sección se describen los trabajos relacionados más relevantes:
1.5.1 [Su 2004] “A Deterministic Method for Initializing K-means Clustering”. En
este trabajo proponen un método para inicializar los parámetros del algoritmo
K-means, en particular los centroides iniciales. Dicho método es jerárquico
divisible determinista y se denomina PCA-part. Se reportan resultados
Capítulo 1 INTRODUCCIÓN
4
experimentales en donde el algoritmo obtiene calidad de solución equivalente a
haber corrido el algoritmo K-means estándar cientos de veces.
1.5.2 [Likas 2003] “The Global K-means Clustering Algorithm”. La idea principal
subyacente en este trabajo es qué se puede calcular el agrupamiento para k
grupos de manera incremental. El algoritmo inicia con k = 1 y obtiene su centroide
C1 el cual quedará fijo. El siguiente centroide se obtiene calculando de manera
exhaustiva el error al cuadrado del nuevo centroide en cada una de las posiciones
de los objetos de la base de datos, esto es, se prueba el nuevo centroide en cada
una de las posiciones de los objetos y se selecciona como nuevo centroide aquella
posición en la que se obtuvo el menor error al cuadrado.
1.5.3 [Hamerly 2002] “Alternatives to the K-means Algorithm that Find Better
Clustering”. En este trabajo se investiga el comportamiento de los siguientes
algoritmos: K-means, Gaussian Expectation-Maximization, Fuzzy K-means y dos
variantes de K-harmonic Means. Se desarrollaron un conjunto de pruebas
experimentales con bases de datos sintéticas, las cuales mostraron que con baja
dimensionalidad dichos algoritmos tienen un comportamiento muy diferente. Con
base en los resultados se encontró que el algoritmo K-harmonic Means tiene un
desempeño superior. En base al comportamiento de los algoritmos, los autores
proponen dos nuevos algoritmos híbridos a los que denominan H1 y H2.
H1 usa la membresía dura de K-means, es decir, cada objeto pertenece al
centroide más cercano. Usa la función de peso del algoritmo K-harmonic Means,
esto es, da más peso a aquellos puntos que están más alejados del centroide. El
híbrido H2 usa la función de membresía suave del K-harmonic Means y la función
de peso constante de K-means.
Las variantes híbridas no muestran una superioridad sobre K-harmonic
means en bases de datos de baja dimensionalidad. Finalmente de manera general
los autores sugieren que para bases de datos de mediana y alta dimensionalidad
se use Fuzzy K-means, H2 y K-harmonic Means.
Capítulo 1 INTRODUCCIÓN
5
1.5.4 [Su 2001] “A Modified Version of the K-Means Algorithm with a Distance
Based on Cluster Symmetry”. En este trabajo se propone un nuevo algoritmo que
es una variante del K-means. En particular se propone una nueva medida de
distancia basada en simetría. El algoritmo fue probado con varias bases de datos
que contenían figuras geométricas y rostros humanos con resultados alentadores.
Una desventaja importante del algoritmo es que incrementa la complejidad
computacional.
1.5.5 [Pelleg 2000] “X-means: Extending K-means with Efficient Estimation of the
Number of Clusters”. En este trabajo se extiende y se hace un mejoramiento del
algoritmo K-means, en particular el algoritmo obtiene de manera automatizada el
mejor número de grupos; es decir, se define de manera automatizada el valor de
k. Resultados experimentales sobre bases de datos reales y sintéticas muestran
que el algoritmo es más eficiente para obtener el valor de k comparado con
ejecutar un gran número de veces el algoritmo K-means estándar con diferentes
valores de k.
1.6 OTROS TRABAJOS
En esta sección se muestran otros dos trabajos que están marginalmente
relacionados con esta tesis. La aportación principal está relacionada con la
implementación computacional del algoritmo y no tanto con el algoritmo en sí.
1.6.1 [Ordonez 2004] “Programming the k-means Clustering Algorithm in SQL”.
En este trabajo se muestra que es factible implementar el algoritmo K-means
estándar en el lenguaje SQL estándar. En el lenguaje SQL estándar se muestra la
definición de tablas índices y consultas necesarias para la implementación del
algoritmo. Se implementan dos algoritmos: uno es el algoritmo K-means estándar
y el otro es un algoritmo propuesto al que denominan K-means optimizado. El
algoritmo optimizado emplea funciones estadísticas y almacena el modelo de
agrupamiento en una tabla. Resultados experimentales con grandes bases de
Capítulo 1 INTRODUCCIÓN
6
datos mostraron que el algoritmo K-means estándar tiene problemas de
escalabilidad; sin embargo, el algoritmo K-means optimizado mostró una
escalabilidad lineal y mayor eficiencia.
1.6.2 [Kanungo 2002] “An Efficient k-Means Clustering Algorithm: Analysis and
Implementation”. En este trabajo se hace una implementación eficiente de una
variante de K-means denominada algoritmo Lloyd’s. Éste define el conjunto de
puntos vecinos a un centroide Ci, cambia el centroide a la posición de cada punto
evaluando el criterio de convergencia, y selecciona el punto donde se obtuvo el
menor valor del criterio de convergencia para ser el nuevo centroide. Parte de la
eficiencia de la implementación se debe al uso de una estructura de datos kd-tree.
1.7 ANÁLISIS COMPARATIVO
Al algoritmo K-means estándar se le han hecho mejoramientos en varios aspectos
asociados con cada uno de los pasos del algoritmo. De manera general el
algoritmo consta de cuatro pasos:
1) Inicialización.
2) Clasificación.
3) Cálculo de centroides.
4) Condición de convergencia.
En cuanto a mejoramientos en los cuatro pasos, tal vez, el que ha recibido
más atención es el de inicialización; en este sentido se pueden mencionar los
trabajos [Su 2004], [Likas 2003] y [Pelleg 2000]. Con relación al paso dos del
algoritmo, se han definido varias medidas de afinidad de los elementos de los
grupos; en este sentido podemos mencionar las aportaciones de [Su 2001] y
[Hamerly 2002]. En relación a los pasos tres y cuatro del algoritmo y de acuerdo a
la literatura especializada, no se reportan trabajos de mejoría al algoritmo.
Capítulo 1 INTRODUCCIÓN
7
En la Tabla 1.1, la primera columna muestra la referencia del trabajo, la
segunda, tercera y cuarta muestran respectivamente la inicialización, clasificación
y condición de convergencia del algoritmo.
Tabla 1.1 Trabajos relacionados.
Proyecto Inicialización Clasificación Condición de
convergencia
[Su 2001] �
[Hamerly 2002] �
[Likas 2003] �
[Pelleg 2000] �
[Su 2004] �
K-means mejorado �
Como podemos observar la mayoría de los trabajos se centran en la
inicialización y la clasificación.
1.8 ORGANIZACIÓN DEL DOCUMENTO
La tesis está organizada de la siguiente manera:
En el capítulo 2 se aborda el algoritmo K-means estándar, y se expone la
implementación computacional y análisis del algoritmo K-means estándar. En el
capítulo 3 se presenta un análisis detallado del algoritmo K-means y finalmente se
presenta el mejoramiento propuesto al algoritmo K-means. En el capítulo 4 se
describen las bases de datos que se usaron en la experimentación y se muestran
los resultados experimentales. Finalmente en el capítulo 5 se presentan las
conclusiones a las que se llegaron durante el desarrollo de esta investigación y
sugerencias de trabajos futuros.
8
Capítulo 2
K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
El agrupamiento se puede ver como un problema de optimización, de naturaleza
combinatoria, lo cual justifica el uso de algoritmos heurísticos para resolver casos
de tamaño grande. Dichos algoritmos no garantizan obtener el óptimo global, sin
embargo, han mostrado obtener buenos resultados. K-means es uno de estos de
algoritmos, y tal vez es uno de los más usados debido a que es relativamente
sencilla la implementación del algoritmo estándar.
Este capítulo está organizado de la siguiente manera: en la sección 2.1 se
presenta el algoritmo K-means estándar y en la 2.2 se presentan la
implementación y análisis del algoritmo K-means estándar.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
9
2.1 K-MEANS ESTÁNDAR
El algoritmo de agrupamiento K-means es uno de los algoritmos de agrupamiento
más usado por su simplicidad computacional y eficiencia. Este algoritmo ha sido
usado en varias áreas del conocimiento [Pham 2004, Fraire 2005, Cruz 2004],
siendo algunas de ellas las siguientes:
a) Diseño de bases de datos distribuidas.
b) Aprendizaje máquina.
c) Reconocimiento de patrones.
d) Compresión y segmentación de imágenes.
e) Minería de datos.
f) Minería Web.
g) En los negocios para descubrir grupos significativos dentro de bases de
datos, por ejemplo, con base a parámetros de compras.
h) En biología para definir taxonomías, caracterizar genes con funcionalidad
similar y aumentar la división dentro de estructuras inherentes en la
población.
i) Agrupamiento de partes mecanizadas dentro de familias en diseño de
sistemas de manufactura de celulares.
2.1.1 Definiciones y notación
Debido a que K-means es usado en varios tipos de aplicaciones, es común que
dependiendo de la aplicación se le den diferentes nombres a los elementos del
algoritmo. En esta sección se describirá para cada elemento su función, y se
mencionará el nombre con el que será referenciado en este documento, y además
se mencionarán algunos nombres con los cuales también son referenciados en la
literatura especializada.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
10
En la Tabla 2.1 muestra los términos y notación que serán usados en las
siguientes partes de este documento.
Tabla 2.1. Términos y notación.
D Es el número de dimensiones de un espacio. El
elemento que define cada una de las dimensiones
en este documento será referenciado como
dimensión . Algunos nombres con que es
referenciado en la literatura son: atributo, variable,
característica, componente y campo.
N Es el número de objetos en un espacio.
K Es el número de regiones en que se divide un
espacio, cada región debe contener al menos un
objeto. En este documento la región será
referenciada como grupo , otros nombres con que
es referenciado en la literatura son clase y
partición.
nj Es el número de objetos del grupo j.
X = {X1, …, Xn} Es un conjunto n objetos en un espacio de d
dimensiones. En este documento será referenciado
como base de datos . Algunos nombres con que es
referenciado en la literatura son: matriz de objetos,
matriz de características, matriz de patrones,
matriz de componentes, matriz de atributos, base
de datos, conjunto de datos y datos de
entrenamiento.
Xn = (xn1, …, xnd) Es el n-ésimo objeto en X. Tiene estructura de
vector con d elementos. Un elemento xnd contiene
el valor de la coordenada del objeto Xn en la
dimensión d. En este documento será referenciado
como objeto . Algunos nombres con que es
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
11
referenciado en la literatura son: vector de
características, observación, punto de dato, patrón,
ejemplar, caso, registro, transacción, tupla y
elementos.
W = {W1, …, Wk} Es un conjunto de k grupos, donde cada k grupo
contiene los objetos ubicados en la región k.
{ }= 1, ...,kk k knW W W Es el k-ésimo grupo en W. Contiene nk objetos Wkj.
Wkj =(wkj1, …, wkjd) Es el j-ésimo objeto del grupo k, tiene estructura de
vector con d componentes.
C = {C1, …, Ck} Es un conjunto de los centros geométricos o
centroides asociados a cada una de las k regiones
o grupos.
Ck = (ck1, …, ckd) Es el k-ésimo centroide en C. Cada elemento ckd
contiene el valor medio del grupo Wk en la
dimensión d.
d(Xj, Ck)= ∑2
=1
(X - )d
jl kll
c Función de error al cuadrado. La función es un
índice de similaridad que cuantifica la distancia
entre un objeto Xj del conjunto de datos X y el
centroide Ck del grupo k.
( ), =∑2
=1
( - )d
kj k kjl kll
d w cW C Función de error al cuadrado. La función es un
índice de similaridad que cuantifica la distancia
entre un objeto Wkj de un k grupo y el centroide Ck
del grupo k.
∑( ) = , )kn
k k kj kj=1
g W , dC W C( Función de error al cuadrado de un k grupo. Es un
índice de similaridad de los objetos del grupo k.
∑( ) = )k
i ii=1
h , g W ,(W C C Función de error al cuadrado de todos los k grupos.
Esta función es un índice de calidad de
agrupamiento.
aleatorio ( X ) Función que retorna un objeto aleatorio Xj del
conjunto de objetos X.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
12
2.2 ALGORITMO K-MEANS ESTÁNDAR
El propósito de esta sección es describir el algoritmo K-means estándar.
2.2.1 Parámetros del algoritmo
Parámetros de entrada para el algoritmo K-means:
a) Una base de datos X. Es el conjunto de objetos sobre los cuales trabajará
el algoritmo.
b) El número de grupos k. Es el número de grupos que formará el algoritmo.
Parámetros de salida para el algoritmo K-means:
a) Un conjunto de k grupos formados W.
2.2.2 Pasos del algoritmo
De acuerdo a la literatura especializada [Su 2004, Su 2001, Pham 2004, Ordonez
2004, Kanungo 2000] se identifican cuatro pasos del algoritmo, los cuales se
describen a continuación:
Paso 1. Inicialización. Este paso consta de dos partes, en la primera parte
se identifica la base de datos X sobre la cual trabajará el algoritmo. En la segunda
se define para cada uno de los grupos un objeto que será usado como referencia
en la selección de los objetos que pertenecerán a cada uno de los grupos.
Usualmente a estas referencias se les llama centroides iniciales C. Dichos puntos
de referencia pueden ser generados de manera aleatoria para cada grupo o bien
pueden ser obtenidos en base a cálculos. En el algoritmo K-means estándar
estos puntos se obtienen de manera aleatoria, como se muestra en el
pseudocódigo de la Figura 2.1 de la línea 1 a la 3.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
13
Paso 2. Clasificación. En este paso se determina para cada objeto Xi el
grupo Wi cuyo centroide Ci está más cercano o más afín al objeto Xi. Usualmente
la medida de distancia o afinidad se determina con la función de error al cuadrado
entre el objeto Xj y el centroide Ci de cada grupo Wi. Otras medidas de afinidad
pueden ser también las distancias Euclidiana, Manhattan y Minkowski por
mencionar algunas. En el algoritmo K-means estándar este paso se muestra en la
Figura 2.1 entre las líneas 8 y 18.
Paso 3. Cálculo de los centroides. El centroide Ci de un grupo Wi es un
vector cuyos elementos contienen los valores medios del grupo Wj en cada una de
las dimensiones d. En el algoritmo K-means estándar este paso se realiza en la
Figura 2.1 entre las líneas 20 y 28, donde nk es igual al número de elementos del
conjunto Wj.
Paso 4. Verificación de convergencia. En este paso se verifica si se ha
cumplido una o varias condiciones que indique que el algoritmo debe parar. A esta
condición se le ha llamado criterio de paro, condición de convergencia y condición
de paro, nosotros le llamaremos condición de convergencia . Las condiciones de
convergencia más usadas son las siguientes:
a) El número de iteraciones.
b) Cuando los centroides obtenidos en dos iteraciones sucesivas no cambian
su valor. Esta es la condición de convergencia del algoritmo K-means
estándar, y su pseudocódigo se muestra en la figura 2.1 en la línea 29.
c) Cuando la diferencia entre los centroides de dos iteraciones sucesivas no
supera cierto umbral.
d) Cuando no hay transferencia de objetos entre grupos en dos iteraciones
sucesivas.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
14
Algoritmo K-means_estándar( X, k, W )
Entrada X, k
Salida W
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Para ( m ← 1 hasta k ) hacer
Cm ← aleatorio ( X );
Fin Para ;
Repite
Para ( i ← 1 hasta k ) hacer
Wi ← Ø;
Fin Para ;
Para ( j ← 1 hasta n ) hacer
m ← 0;
min ← + ∞;
Para ( i ← 1 hasta k ) hacer
Si (d( Xj, Ci ) < min ) hacer
min ← d( Xj, Ci );
m ← i;
Fin Si ;
Fin Para ;
Wm ← Wm U { Xj };
Fin Para ;
C’ ← C;
Para ( i ← 1 hasta k ) hacer
Para ( l ← 1 hasta d ) hacer
media ← 0;
Para ( j ← 1 hasta ni ) hacer
media ← media + wijl;
Fin Para ;
Cil ← ( media / ni );
Fin Para ;
Fin Para ;
Hasta ( C’ = C);
Regresa ( W );
Figura 2.1. Pseudocódigo del algoritmo K-means estándar.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
15
2.2.3 Características del algoritmo K-means estánda r
Las principales características del algoritmo son las siguientes [Su 2004, Kanungo
2002, Hamerly 2002]:
a) El algoritmo está clasificado como un algoritmo glotón.
b) Es un método heurístico y, como tal, no garantiza el óptimo global.
c) Puede quedar atrapado en óptimos locales.
d) Un factor que incide directamente en el costo computacional del algoritmo
K-means es el número de iteraciones que requiere efectuar, ya que por
cada iteración calcula para cada uno de los objetos de la base de datos la
distancia a los centroides de los grupos.
Se han identificado las siguientes ventajas para el algoritmo:
a) Algoritmo sencillo con cálculos simples.
b) Funciona bien para grupos con geometría globular.
Como desventajas se pueden mencionar las siguientes:
a) Es necesario saber el número de k grupos.
b) La agrupación final depende de los centroides iniciales.
c) No garantiza una convergencia en el óptimo global.
d) En el caso de ejemplares grandes de problemas, puede requerir un gran
número de iteraciones para convergir.
e) Se usa sólo con datos numéricos.
f) No funciona bien si hay ruido.
g) No es adecuado para grupos con geometría no globular.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
16
2.3 IMPLEMENTACIÓN Y ANÁLISIS DEL ALGORITMO K-MEANS ESTÁNDAR
Para los fines de análisis se implementó computacionalmente el algoritmo
K-means estándar sin límites de dimensión, número de grupos y número de
objetos, teniendo como restricción únicamente la capacidad de la máquina. Las
métricas usadas para medir la eficiencia y eficacia son el número de iteraciones y
el error al cuadrado respectivamente.
2.3.1 Implementación del algoritmo K-means estándar
Se implementó computacionalmente el algoritmo K-means estándar, y se le
introdujo código al programa para que en cada iteración mostrara el error al
cuadrado g(Wk, Ck) y la suma del error al cuadrado de cada grupo h(W, C), esto
con la finalidad de monitorear la eficacia del agrupamiento en cada iteración. El
algoritmo estándar de K-means fue implementado en el lenguaje C++ Builder, y
las pruebas se realizaron en una computadora Pentium 4 a 2.4 GHz con 512 MB
de memoria RAM. El pseudocódigo del algoritmo se muestra en la Figura 2.1.
2.3.2 Software comercial SPSS
SPSS es una herramienta comercial usada en negocios e investigación, la cual
incluye módulos para la identificación de grupos, medidas de similaridad y
clasificación entre otras. Dentro del módulo clasificación tiene una implementación
del algoritmo K-means [SPSS]. Este algoritmo K-means realiza un
preprocesamiento de los datos y obtiene sus centroides iniciales de manera que
siempre son los mismos, posteriormente realiza la clasificación y el cálculo de
centroides, y finalmente proporciona dos condiciones de convergencia: cuando
llega a un número de iteraciones y cuando la diferencia entre los centroides de dos
iteraciones sucesivas no supera cierto umbral.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
17
2.3.3 Herramienta Weka
Weka es una colección de algoritmos para tareas de aprendizaje máquina y
minería de datos. Weka es una biblioteca de Java y su código es abierto bajo
GNU. Entre los algoritmos de agrupamiento que contiene Weka se encuentra
K-means [Witten 1999]. Este algoritmo K-means realiza un preprocesamiento de
los datos y obtiene sus centroides iniciales de manera que siempre son los
mismos, posteriormente realiza la clasificación y el cálculo de centroides, y
finalmente converge cuando los centroides obtenidos en dos iteraciones sucesivas
no cambian su valor.
2.3.4 Resultados experimentales del algoritmo imple mentado
Con el propósito de validar experimentalmente la implementación del algoritmo
K-means estándar, se diseñaron dos experimentos: uno con una base de datos
generada artificialmente para la cual se conocía el número de grupos y sus
centroides óptimos, y otra base de datos sintética asociada con el problema de
Bin-packing. Los resultados de ambos experimentos se contrastaron con el
resultado del paquete comercial SPSS y la biblioteca Weka de Java. En las
siguientes secciones se muestran a detalle dichos experimentos.
2.3.4.1 Validación experimental de la implementació n del K-means estándar
Objetivo
Comprobar la correcta implementación computacional de K-means estándar y
contrastar los resultados con SPSS y Weka.
Procedimiento
Para esta experimentación se usó como datos de entrada una base de datos
sintética generada por el generador de bases de datos sintéticas implementado en
esta tesis. De esta base de datos se conoce el error al cuadrado h(W, C)= 77.46
de la agrupación óptima. La base de datos consta de 40 objetos, dos grupos y dos
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
18
dimensiones. El siguiente paso es ejecutar cada uno de los algoritmos de
agrupamiento, obtener el error al cuadrado h(W, C) de los grupos generados por
cada algoritmo, y comprobar su igualdad.
Se presenta en detalle el procedimiento que llevó a cabo el algoritmo
K-means estándar al ser ejecutado. Primero se calcularon los centroides iniciales
C1 = (2.99, 2.42) y C2 = (-2.68, -0.09) de forma aleatoria, posteriormente repartió
los objetos usando como medida de similaridad la función error al cuadrado
d(Xj, Ck) y obteniendo el agrupamiento mostrado en la Figura 2.2. En el siguiente
paso se recalcularon los centroides C1 = (3, 2) y C2 = (-4, 2), y nuevamente se
repartieron los objetos obteniendo el agrupamiento mostrado en la Figura 3.3.
Posteriormente se recalcularon los centroides y se contrastaron con los centroides
obtenidos en la iteración anterior, y como éstos fueron iguales el algoritmo
convergió en la segunda iteración.
Iteración 1
-2
-1
0
1
2
3
4
5
6
-8 -6 -4 -2 0 2 4 6
Grupo1 Z1 Grupo2 Z2
Figura 2.2. Primera iteración de K-means estándar.
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
19
Iteración2
-2
-1
0
1
2
3
4
5
6
-8 -6 -4 -2 0 2 4 6
Grupo Z1 Grupo2 Z2
Figura 2.3. Segunda iteración de K-means estándar.
Resultados
En la Tabla 2.2 se muestran los resultados obtenidos por cada algoritmo durante
esta experimentación. En la primera columna se muestra el Error al cuadrado
h(W, C) de K-means estándar; en la segunda columna se muestra el número de
iteración en la que converge K-means estándar, en la tercera columna se muestra
el error al cuadrado h(W, C) de SPSS, en la cuarta columna se muestra el número
de iteración en la que converge SPSS, en la quinta columna se muestra el error al
cuadrado h(W, C) de Weka, y en la sexta columna se muestra el número de
iteración en la que converge Weka.
Tabla 2.2. Comprobación de la implementación del algoritmo K-means.
K-means estándar SPSS Weka
Error al
cuadrado
h(W, C)
Iteración Error al
cuadrado
h(W, C)
Iteración Error al
cuadrado
h(W, C)
Iteración
77.46 2 77.46 2 77.46 4
Análisis de resultados
De acuerdo con los resultados obtenidos en la Tabla 2.1, todos los algoritmos
convergen en la misma agrupación, donde sus errores al cuadrado h(W, C) son
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
20
iguales al conocido con antelación. Por lo tanto, podemos concluir que el algoritmo
K-means estándar está perfectamente implementado computacionalmente. Por
otra parte analizando el número de iteraciones, podemos observar que K-means
estándar y SPSS convergieron en el mismo número de iteraciones y Weka en un
número mayor.
2.3.4.2 Experimentación con una base de datos
Objetivo
Conocer el error al cuadrado h(W, C) y la iteración promedio en la que convergen
cada uno de los algoritmos.
Procedimiento
A cada algoritmo se le dio como datos de entraba la base de datos Bin-packing
descrita en la sección 4.1.1. Para el algoritmo K-means estándar se hicieron 30
corridas, ya que este algoritmo obtiene los centroides iniciales de manera
aleatoria, siendo cada uno de éstos un objeto de la base de datos. Para SPSS y
Weka se realizó sólo una corrida, ya que estos algoritmos hacen un
preprocesamiento de los datos y sus centroides iniciales siempre son los mismos.
Para comparar la calidad de los algoritmos se usó la función error al cuadrado
h(W, C). Cabe mencionar que, entre menor sea este error, mayor es la eficacia del
agrupamiento.
Resultados
En la Tabla 2.3 se muestran los resultados en eficacia y eficiencia
correspondientes al punto de convergencia de cada una de las 30 corridas. En la
primera columna se muestra el número de corrida; en la segunda, el número de
iteración; y en la tercera columna se muestra el error al cuadrado h(W, C) para
cada corrida.
En la Tabla 2.4, en el primer renglón se muestra el número de iteraciones
en el que converge cada algoritmo, y en el último renglón se muestra el error al
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
21
cuadrado h(W, C) de los algoritmos de agrupamiento k-means estándar, SPSS y
Weka.
Tabla 2.3 Corridas K-means estándar con la base de datos Bin-packing.
No. Corrida Iteración Error al cuadrado h(W, C)
1 19 580.27
2 27 580.32
3 23 580.32
4 22 580.27
5 32 580.27
6 23 580.32
7 35 580.27
8 32 580.27
9 16 580.33
10 26 580.27
11 31 580.32
12 39 580.32
13 28 580.27
14 17 580.27
15 18 580.29
16 22 580.27
17 18 580.27
18 15 580.27
19 34 580.27
20 25 580.27
21 31 580.27
22 21 580.32
23 18 580.27
24 17 580.32
25 16 580.33
26 25 580.27
27 23 580.27
28 26 580.27
29 11 580.32
30 14 580.33
Capítulo 2 K-MEANS ESTÁNDAR E IMPLEMENTACIÓN
22
Tabla 2.4 Resultados de la comparación K-means estándar usando Bin-packing.
k-means estándar
promedio
SPSS Weka
Iteración 23 31 21
Error al cuadrado h(W, C) 580.29 580.27 669.30
Análisis de resultados
En promedio de iteraciones y calidad, K-means estándar converge en 23
iteraciones con un error al cuadrado h(W, C) de 580.29, SPSS converge en 31
iteraciones y un error al cuadrado h(W, C) de 580.27, y Weka converge en la
iteración 21 y con un error al cuadrado h(W, C) de 669.30, ver Tabla 2.4.
22
Capítulo 3
MEJORAMIENTO PROPUESTO AL ALGORITMO
K-MEANS
En este capítulo se presenta una técnica para mejorar la eficiencia y eficacia del
algoritmo K-means estándar mediante una nueva condición de convergencia.
Durante experimentos realizados con una base de datos, observamos que el
algoritmo K-means estándar no convergía en el óptimo local en un 96% de las
pruebas realizadas, ya que el algoritmo entraba a un mínimo local y salía de él
convergiendo con un error mayor, lo cual mostró una posibilidad de hacer una
mejoría al algoritmo.
En este capítulo se presenta una técnica para mejorar el algoritmo K-means
y está organizado como sigue: En la sección 3.1 se describe el análisis del
algoritmo K-means estándar, y en la sección 3.2 se presenta la técnica para
mejorar el algoritmo.
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
23
3.1 ANÁLISIS DETALLADO DEL ALGORITMO K-MEANS ESTÁND AR
Con la finalidad de hacer una mejoría al algoritmo K-means, se analizó
detalladamente cada una de las corridas de K-means estándar en cada una de las
iteraciones, comparando el error al cuadrado h(W, C) de cada una de las corridas
en cada una de las iteraciones.
3.1.1 Análisis del comportamiento para una corrida
Objetivo
Realizar un análisis detallado del algoritmo K-means estándar con la finalidad de
encontrar una posible mejoría.
Procedimiento
Analizar el comportamiento del error al cuadrado h(W, C) de cada una de las
iteraciones con la base de datos Diabetes descrita en la sección 4.1.4.
Resultados
En la Tabla 3.1 se muestran detalles de la corrida del algoritmo. En la primera
columna se muestra el número de iteración, en la dos y tres respectivamente se
muestra el error al cuadrado g(Wk, Ck) de cada grupo. Finalmente la columna
cuatro muestra el error al cuadrado h(W, C) de la agrupación.
Análisis de resultados
Al analizar los resultados tabulares del error al cuadrado de cada iteración, se
observó que el algoritmo pasaba por un óptimo local y, sin embargo, continuaba
realizando iteraciones incrementando el error al cuadrado h(W, C).
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
24
Tabla 3.1 Salida de un mínimo y convergencia en una calidad menor con
Diabetes.
No. Iteración Error al cuadrado g(Wk,
Ck) del grupo 1
Error al cuadrado g(Wk,
Ck) del grupo 2 Error al cuadrado h(W, C)
1 26891 29712 56603
2 24755 23053 47808
3 28106 205972 48703
4 30447 19202 49649
5 31710 18688 50399
6 32584 18225 50809
7 33447 17649 51097
8 33980 17414 51395
9 34392 17175 51568
10 34660 17047 51708
11 34917 16879 51797
12 35064 16823 51887
13 35195 16739 51935
14 35434 16544 51979
15 35464 16607 52072
3.1.2 Búsqueda de patrones en el comportamiento del algoritmo K-means
estándar con la base de datos Diabetes
En el experimento de la sección 3.1.1 nos dimos cuenta de que el algoritmo no
convergía en el óptimo local y continuaba realizando iteraciones perdiendo calidad
y consumiendo recursos.
Objetivo
Buscar patrones de comportamiento durante cada iteración del algoritmo basados
en el error al cuadrado h(W, C), y comprobar si el patrón encontrado en la sección
3.1.1 se repite.
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
25
Procedimiento
Se realizaron 30 corridas del algoritmo K-means estándar usando la base de datos
Diabetes descrita en la sección 4.1.4, obteniendo el error al cuadrado h(W, C) de
cada una de las iteraciones.
Resultados
Durante la experimentación se obtuvo una secuencia de la corrida por iteración
igual que la presentada en la Tabla 3.1 y se observaron dos patrones:
a) Patrón donde el algoritmo pasa por un óptimo local y degrada su valor
convergiendo en una calidad menor ver Figura 3.1.
b) Patrón donde el algoritmo converge en el óptimo local ver Figura.3.2.
Como se puede apreciar en la Figura 3.1, en la iteración número dos se
encuentra un valor mínimo del error cuadrado h(W, C); sin embargo, el algoritmo
K-means estándar converge en un valor final del error cuadrado h(W, C) y en una
iteración posterior.
Figura 3.1. K-means pasa por un mínimo local y pierde su valor óptimo.
Por otra parte, en varios de los experimentos se observó que el algoritmo
convergía en un óptimo local como se muestra en la Figura 3.2. En estos casos el
No. Iteración
15.5E+8 15.0E+8 14.5E+8 14.0E+8
13.5E+8 13.0E+8
12.5E+8 12.0E+8
1 2 3 4 6 5 7 8 9 10 11 12 13 14
Valor inicial Valor de
convergencia
Óptimo local
Err
or a
l cua
drad
o h(
W, C
)
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
26
error cuadrado h(W, C) seguía un patrón de decremento con cada nueva
iteración.
Figura 3.2. K-means converge en un mínimo local.
En la Tabla 3.2 se muestran en forma sombreada las corridas que
presentan el patrón donde pasa por un mínimo y converge en un error al cuadrado
h(W, C) mayor. En las filas no sombreadas se presenta el patrón donde converge
en un mínimo. En la columna uno se muestra el número de la corrida, en la dos y
tres se muestra respectivamente el número de iteraciones y el error al cuadrado
h(W, C) en el cual converge el algoritmo K-means estándar. En las columnas
cuatro y cinco se muestran respectivamente el número de iteración y el error al
cuadrado h(W, C) cuando se encuentra el óptimo local.
Análisis de resultados
En el 96% de las corridas se repetía el comportamiento del algoritmo donde no
paraba en el óptimo local y en el 4% de los casos el algoritmo sí convergía en el
óptimo local.
Err
or a
l cua
drad
o h(
W,C
)
No. Iteración
40E+8
30E+8
20E+8
10E+8
1
2
3
4
6
5
7
8
9
10
Valor inicial
Óptimo local
Valor de convergencia
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
27
Tabla 3.2 Experimentación de K-means estándar con Diabetes.
Corrida
K-means estándar Óptimo local
Iteración Error al cuadrado W Iteración Error al cuadrado W
1 17 52072 4 47744
2 14 52072 2 48966
3 13 52072 3 50235
4 16 52072 3 47830
5 15 52072 3 48785
6 14 52072 3 48282
7 14 52072 2 48775
8 15 52072 3 48149
9 15 52072 3 47815
10 15 52072 2 47826
11 14 52072 2 48284
12 14 52072 2 48228
13 16 52072 3 48099
14 16 52072 3 47965
15 15 52072 2 47863
16 15 52072 3 48089
17 14 52072 2 48289
18 13 52072 2 49221
19 15 52072 2 47954
20 15 52072 2 47808
21 16 52072 3 47805
22 16 52072 3 47780
23 10 52072 10 52072
24 13 52072 2 49363
25 15 52072 2 48130
26 14 52072 2 48212
27 15 52072 3 48051
28 16 52072 3 47918
29 14 52072 2 48634
30 16 52072 3 47810
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
28
3.1.3 Comportamiento del algoritmo K-means estándar con siete bases de
datos
Objetivo
Realizar por cada corrida un análisis de cada iteración de las siete bases de datos
mostradas en la Tabla 4.1 usando el algoritmo K-means estándar, con el objetivo
de detectar el número de corridas donde pasa por un mínimo y pierde su valor
convergiendo en un error al cuadrado h(W, C) mayor y en consecuencia menor
eficacia.
Procedimiento
Se realizaron 30 corridas del algoritmo K-means estándar para cada una de las
bases de datos de la Tabla 4.1.
Resultados
Se obtuvieron 30 corridas de cada una de las bases de datos, donde para cada
corrida se registró el error cuadrado h(W, C) de cada una de las iteraciones
realizadas por el algoritmo.
Análisis de resultados
Durante esta experimentación se observó que el algoritmo no convergía en un
óptimo local como se muestra en la Figura 3.1. En estos casos se llegaba a un
mínimo local y el algoritmo continuaba haciendo operaciones incrementando su
error cuadrado h(W, C) y, por consiguiente, decrementando su eficacia. Los
resultados obtenidos en esta experimentación son resumidos en la Tabla 3.3.
En la Tabla 3.3 se muestra el porcentaje de las corridas en las cuales se
observo el patrón de la Figura 3.1 para cada base de datos. En la primera columna
se muestra el nombre de la base de datos; y en la segunda y tercera columnas
respectivamente, el número de corridas y el porcentaje de corridas en las cuales
ocurre el patrón de la Figura 3.1. De las bases de datos analizadas, Diabetes fue
en la que más corridas se encontró este patrón (96%). Después sigue Bin-Packing
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
29
con un 77%, Liver con 70%, Vehicle con 50%, Wine con 43%, Heart con 33% y
Glass fue la que en menos corridas se observó este patrón (20%).
Tabla 3.3. Porcentaje de corridas que no paran en un óptimo local.
Base de
datos
Número de iteraciones con el
patrón de la Figura 3.1
% de corridas que no paran
en un óptimo local
Diabetes 29 96
Bin-packing 23 77
Liver 21 70
Vehicle 15 50
Wine 13 43
Heart 10 33
Glass 6 20
Con base en los resultado anteriores, se determinó que sería de utilidad el
definir una nueva condición de convergencia, para mejorar desempeño del
algoritmo en aquellos casos en los cuales el algoritmo no para en el óptimo local.
Una mejoría de este tipo puede proporcionar dos beneficios: una reducción en el
número de iteraciones y una mejoría en la calidad.
3.2 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS EST ÁNDAR
Tradicionalmente se ha considerado que el algoritmo K-means es un algoritmo
goloso; es decir, que puede quedar atrapado en un óptimo local; sin embargo,
analizando las condiciones de convergencia y la experimentación realizada, se
observó que no existe un criterio de convergencia asociado al valor de la función
del error al cuadrado h(W, C), siendo ésta la razón por la cual el algoritmo
estándar no puede garantizar una convergencia a un óptimo local (ver Figura. 3.3).
En este sentido, la principal aportación de este trabajo consiste en asociar un
criterio de convergencia con los valores de la función error al cuadrado h(W, C), de
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
30
manera que sea posible que el algoritmo pare cuando se identifique un óptimo
local. La nueva condición de convergencia está compuesta de dos condiciones:
a) Cuando en dos iteraciones sucesivas el valor del error al cuadrado h(W, C)
de la última iteración es mayor que el valor del error al cuadrado h(W, C) de
la iteración anterior.
b) Cuando los centroides en dos iteraciones sucesivas no cambian.
3.3 ALGORITMO DEL ALGORITMO K-MEANS MEJORADO
En la siguiente figura se muestra el pseudocodigo del algoritmo K-means
mejorado, donde la condición de convergencia propuesta se encuentra en la línea
32 de la Figura 3.3.
Algoritmo K-means_mejorado( X, k, W )
Entrada X, k
Salida W
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Para ( m ← 1 hasta k ) hacer
Cm ← aleatorio ( X );
Fin Para ;
z ← + ∞;
Repetir
z' ← z;
Para ( i ← 1 hasta k ) hacer
Wi ← Ø;
Fin Para ;
Para ( j ← 1 hasta n ) hacer
min ← + ∞;
Para ( i ← 1 hata k ) hacer
Si (d( Xj, Ci ) < min ) hacer
min ← d( Xj, Ci );
Capítulo 3 MEJORAMIENTO PROPUESTO AL ALGORITMO K-MEANS
31
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
m ← i;
Fin Si ;
Fin Para ;
Wm ← Wm U { Xj };
Fin Para ;
C’ ← C;
Para ( i ← 1 hasta k ) hacer
Para ( l ← 1 hasta d ) hacer
media ← 0;
Para ( j ← 1 hasta nk ) Hacer
media ← media + wijl;
Fin Para ;
Cil ← ( media / nk );
Fin Para ;
Fin Para ;
z ← h( W, C );
Hasta ( ( C’ = C ) o ( z’ < z ) );
Regresa ( W );
Figura 3.3 Pseudocódigo del algoritmo K-means mejorado.
32
Capítulo 4
RESULTADOS EXPERIMENTALES
En este capítulo se describe la experimentación realizada para validar el nuevo
criterio de convergencia del algoritmo K-means mejorado en este trabajo. El
algoritmo K-means mejorado se contrasta con los algoritmos: K-means estándar,
el paquete comercial SPSS y la herramienta Weka de Java.
En este capítulo se muestra la experimentación realizada para validar el
algoritmo K-means mejorado en el capítulo 3. En particular se muestran los
experimentos realizados con seis bases de datos reales y una base de datos del
problema Bin-packing. En la sección 4.1 se describen las bases de datos que se
usaron en la experimentación, en la sección 4.2 se muestra la experimentación
realizada y el análisis de los resultados.
Capítulo 4 RESULTADOS EXPERIMENTALES
33
4.1 DESCRIPCIÓN DE LAS BASES DE DATOS QUE SE USARON EN LA
EXPERIMENTACIÓN
Para realizar la experimentación se usaron seis bases de datos reales del
repositorio aprendizaje máquina [Hettich 1998] y una base de datos de
Bin-packing obtenida de la tesis doctoral [CRUZ 2004].
4.1.1 Base de datos Bin-packing
Bin-packing es una base de datos sintética, la cual contiene un conjunto de 2,430
objetos aleatorios con cuatro grupos y cinco dimensiones.
4.1.2 Base de datos Vehicle
La base de datos Vehicle se usa para clasificar una silueta dada que pertenece a
uno de cuatro tipos de vehículos, usando un conjunto de rangos extraídos de la
silueta. El vehículo puede verse desde muchos ángulos diferentes. Vehicle
contiene 846 objetos, cuatro grupos y 18 dimensiones.
4.1.3 Base de datos Glass
La base de datos Glass se usa para la clasificación de tipos de cristales. El acopio
de estos datos fue motivado por la investigación de criminología. Glass contiene
214 objetos, siete grupos y nueve dimensiones.
4.1.4 Base de datos Diabetes
La base de datos Diabetes contiene el diagnóstico de pacientes de diabetes según
la Organización Mundial de Salud. Diabetes contiene 768 objetos, dos grupos y
ocho dimensiones.
Capítulo 4 RESULTADOS EXPERIMENTALES
34
4.1.5 Base de datos Heart
Esta base de datos contiene el diagnóstico de enfermedades del corazón. Heart
contiene 270 objetos, dos grupos y 13 dimensiones.
4.1.6 Base de datos Wine
Estos datos son los resultados de un análisis químico de cepas cultivadas en una
región de Italia y derivó de tres cultivos diferentes. El análisis determinó las
cantidades de 13 componentes encontrados en cada uno de los tres tipos de
vinos. Wine contiene 178 objetos, tres grupos y 13 dimensiones.
4.1.7 Base de datos Liver
Estos datos son resultado de una investigación médica de pacientes que pueden
ser sensibles a desórdenes del hígado, los cuales podrían originarse por el
consumo excesivo de alcohol. Liver contiene 345 objetos, dos grupos y 6
dimensiones.
Tabla 4.1. Detalle de las bases de datos usadas para experimentación.
Base de datos Número de
grupos
Número de
dimensiones
Número de
objetos
Bin-Packing 4 5 2430
Vehicle 4 18 846
Glass 7 9 214
Diabetes 2 8 768
Heart 2 13 270
Wine 3 13 178
Liver 2 6 345
Capítulo 4 RESULTADOS EXPERIMENTALES
35
En la Tabla 4.1 se muestran los atributos generales de las bases de datos. En la
primera columna se encuentran los nombres de las bases de datos; en la
segunda, el número de grupos; en la tercera, el número de dimensiones; y en la
cuarta, el número de objetos.
4.2 RESULTADOS EXPERIMENTALES
Con la finalidad de comprobar la eficiencia y eficacia del algoritmo K-means
mejorado, se realizaron dos experimentos: uno para comprobar la eficiencia
usando como métrica el número de iteraciones y otro para comprobar la eficiencia
usando como métrica la suma del error al cuadrado h(W, C) de los grupos.
Objetivo
El objetivo es comparar la eficiencia y eficacia del algoritmo K-means mejorado
con K-means estándar, SPSS y Weka.
Procedimiento
Se usaron las siete bases de datos mencionadas en la Tabla 4.1, y cada una se
procesó usando Weka, SPSS, K-means estándar y K-means mejorado. Las bases
de datos se procesaron una vez con Weka y con SPSS, debido a que estas
herramientas hacen un preprocesamiento de los datos y definen unos centroides
iniciales, los cuales no varían para cada corrida. Para el caso K-means estándar y
K-means mejorado, se efectuaron 30 corridas generando al azar los centroides
iniciales para cada corrida.
4.2.1 Resultados de eficiencia
Se obtuvo el número de iteraciones en el que convergió cada algoritmo con las
bases de datos. Los resultados son expresados en una tabla comparativa para
cada una de las bases de datos, la cual expresa el número de iteración en que
converge cada algoritmo. Para los algoritmos K-means estándar y K-means
mejorado, se muestran la iteración mínima, promedio y máxima en la columna dos
Capítulo 4 RESULTADOS EXPERIMENTALES
36
y tres respectivamente; y en la columna cuatro y cinco, el número de iteración en
la que converge SPSS y Weka respectivamente.
4.2.1.1 Resultados para Bin-packing. En la Tabla 4.2 se ve que en promedio el
algoritmo mejorado converge en 17 iteraciones, siendo éste el más rápido;
después Weka, en 21; K-means estándar, en 25; y por último SPSS, en 31
iteraciones.
Tabla 4.2 Resultados experimentales en eficiencia para Bin-packing.
Bin-packing
K-means mejorado K-means estándar SPSS Weka
Mínimo 10 11
31
21
Promedio 17 23
Máximo 36 39
4.2.1.2 Resultados para Vehicle. En la Tabla 4.3 se ve que en promedio el
algoritmo mejorado converge en la misma iteración que Weka con 10 iteraciones,
después le sigue K-means estándar con 13 iteraciones y por último SPSS con 19
iteraciones.
Tabla 4.3 Resultados experimentales en eficiencia para Vehicle.
Vehicle
K-means mejorado K-means estándar SPSS Weka
Mínimo 2 2
19
10
Promedio 10 13
Máximo 26 26
4.2.1.3 Resultados para Glass. En la Tabla 4.4 se ve que en promedio el
algoritmo mejorado converge en el menor número de iteraciones, en la 8; después
le sigue K-means estándar y SPSS con 9 iteraciones y finalmente Weka con 14
iteraciones.
Capítulo 4 RESULTADOS EXPERIMENTALES
37
Tabla 4.4 Resultados experimentales en eficiencia para Glass.
Glass
K-means mejorado K-means estándar SPSS Weka
Mínimo 4 4
9
14
Promedio 8 9
Máximo 18 18
4.2.1.4 Resultados para Diabetes. En la Tabla 4.5 se ve que en promedio el
algoritmo mejorado converge mucho más rápido, en 3 iteraciones; después le
sigue Weka con 9, K-means estándar con 15 y finalmente SPSS con 17
iteraciones.
Tabla 4.5 Resultados experimentales en eficiencia para Diabetes.
Diabetes
K-means mejorado K-means estándar SPSS Weka
Mínimo 2 10
17
9
Promedio 3 15
Máximo 10 17
4.2.1.5 Resultados para Heart. En la Tabla 4.6 se ve que Weka es el que obtuvo
mejores resultados terminando en 6 iteraciones, después le sigue el algoritmo
K-means mejorado con 7, K-means estándar con 10 y finalmente SPSS con 13
iteraciones.
Tabla 4.6 Resultados experimentales en eficiencia para Heart.
Heart
K-means mejorado K-means estándar SPSS Weka
Mínimo 2 2
13
6
Promedio 7 10
Máximo 14 14
Capítulo 4 RESULTADOS EXPERIMENTALES
38
4.2.1.6 Resultados para Wine. En la Tabla 4.7 se ve que en promedio el
algoritmo mejorado converge más rápido, con 5 iteraciones; después le sigue
K-means estándar con 6 y finalmente SPSS y Weka con 8 iteraciones.
Tabla 4.7 Resultados experimentales en eficiencia para Wine.
Wine
K-means mejorado K-means estándar SPSS Weka
Mínimo 2 2
8
8
Promedio 5 6
Máximo 13 13
4.2.1.7 Resultados para Liver. En la Tabla 4.8 se ve que en promedio el
algoritmo mejorado converge más rápido, en 4 iteraciones; después le sigue SPSS
con 6, Weka con 7 y finalmente el algoritmo K-means estándar con 9 iteraciones.
Tabla 4.8 Resultados experimentales en eficiencia para Liver.
Liver
K-means mejorado K-means estándar SPSS Weka
Mínimo 2 3
6
7
Promedio 4 9
Máximo 8 14
4.2.2 Análisis comparativo de eficiencia
En esta sección se realiza un análisis comparativo del número de iteraciones en el
que convergen los algoritmos con las bases de datos que se están manejando. En
particular se contrastan los resultados obtenidos por el algoritmo K-means
mejorado contra los resultados obtenidos por los demás algoritmos en porcentaje.
En la Tabla 4.9 se muestra dicho análisis comparativo. En la primera
columna se muestra el nombre de la base de datos; en la segunda y tercera, la
Capítulo 4 RESULTADOS EXPERIMENTALES
39
iteración promedio en que converge el algoritmo K-means mejorado y K-means
estándar respectivamente. En la cuarta columna se muestra la superioridad del
algoritmo K-means mejorado en porcentaje. En la columna cinco se indica el
número de iteración en la que converge el paquete comercial SPSS; y en la sexta,
el porcentaje de mejoría del algoritmo K-means mejorado. En la columna siete se
muestra la iteración en la que converge Weka; y en la octava columna, la
superioridad del algoritmo K-means mejorado en porcentaje.
Tabla 4.9 Análisis comparativo en eficiencia.
Base de
datos
K-means
mejorado
K-means
estándar SPSS WEKA
Iteración
promedio
Iteración
promedio % Iteración % Iteración %
Bin-packing 17 23 26.09 31 45.16 21 19.05
Vehicle 10 13 23.08 19 47.37 10 0.00
Glass 8 8 0.00 9 11.11 14 42.86
Diabetes 3 14 78.57 17 82.35 9 66.70
Heart 7 10 30.00 13 46.15 6 -16.67
Wine 5 6 16.67 8 37.50 8 37.50
Liver 4 9 55.56 6 33.33 7 42.86
Como se observa en la Tabla 4.9, en el mejor de los casos el algoritmo
mejorado vs. K-means estándar ganó con 78% en la base de datos Bin-packing, el
algoritmo mejorado vs. SPSS ganó con 82% en la base de datos Diabetes y el
algoritmo mejorado vs. Weka ganó con 66% en la base de datos Diabetes. En el
peor de los casos el algoritmo mejorado vs. K-means estándar obtuvo el mismo
resultado con la base de datos Glass, el algoritmo mejorado vs. SPSS ganó con
11% en la base de datos Glass y el algoritmo mejorado vs. Weka perdió con 16%
en la base de datos Heart.
Capítulo 4 RESULTADOS EXPERIMENTALES
40
4.2.3 Resultados de eficacia
Se obtuvo el error al cuadrado h(W, C) en el cual convergió cada algoritmo para
cada una de las bases de datos. Los resultados son expresados en una tabla
comparativa para cada una de las bases de datos. En dicha tabla se indica el error
al cuadrado h(W, C) con el que convergió cada algoritmo. Además, en la tabla se
indica el error al cuadrado h(W, C) mínimo, promedio y máximo para los
algoritmos K-means estándar y mejorado en las columnas dos y tres
respectivamente. Es conveniente mencionar que estos resultados se obtuvieron
con un conjunto de 30 corridas. Finalmente, en las columnas cuatro y cinco se
indica el error al cuadrado h(W, C) con el que convergion SPSS y Weka
respectivamente.
4.2.3.1 Resultados para Bin-packing. La Tabla 4.10 muestra que K-means
mejorado en promedio es mejor que K-means estándar, SPSS y Weka.
Tabla 4.10 Resultados experimentales en eficacia para Bin-packing.
Bin-packing
K-means mejorado K-means estándar SPSS Weka
Mínimo 579.96 580.27
580.27
669.30
Promedio 580.17 580.29
Máximo 580.33 580.33
4.2.3.2 Resultados para Vehicle. En la Tabla 4.11, se ve que K-means mejorado
en promedio es mejor que K-means estándar, SPSS y Weka.
Capítulo 4 RESULTADOS EXPERIMENTALES
41
Tabla 4.11 Resultados experimentales en eficacia para Vehicle.
Vehicle
K-means mejorado K-means estándar SPSS Weka
Mínimo 45105.17 45144.24
50001.83
55949.20
Promedio 46989.71 47122.65
Máximo 56915.15 56915.15
4.2.3.3 Resultados para Glass. En la Tabla 4.12, se ve que K-means mejorado
en promedio es mejor que el promedio de K-means estándar, SPSS y Weka.
Tabla 4.12 Resultados experimentales en eficacia para Glass.
Glass
K-means mejorado K-means estándar SPSS Weka
Mínimo 203.37 203.37
211.50
235.82
Promedio 210.54 210.58
Máximo 223.80 223.78
4.2.3.4 Resultados para Diabetes. En la Tabla 4.13, se ve que K-means
mejorado en promedio es mejor que el promedio de K-means estándar, SPSS y
Weka.
Tabla 4.13 Resultados experimentales en eficacia para Diabetes.
Diabetes
K-means mejorado K-means estándar SPSS Weka
Mínimo 47744.54 52072.20
52072.24
73193.07
Promedio 48399.88 52072.20
Máximo 52072.20 52072.20
4.2.3.5 Resultados para Heart. En la Tabla 4.14, se ve que K-means mejorado
en promedio es mejor que el promedio de K-means estándar, SPSS y Weka.
Capítulo 4 RESULTADOS EXPERIMENTALES
42
Tabla 4.14 Resultados experimentales en eficacia para Heart.
Heart
K-means mejorado K-means estándar SPSS Weka
Mínimo 10680.87 10695.79
10700.83
13692.84
Promedio 10692.55 10698.47
Máximo 10700.83 10700.83
4.2.3.6 Resultados para Wine. En la Tabla 4.15, se ve que K-means mejorado
en promedio es mejor que el promedio de K-means estándar, SPSS y Weka.
Tabla 4.15 Resultados experimentales en eficacia para Wine.
Wine
K-means mejorado K-means estándar SPSS Weka
Mínimo 16384.57 16529.84
18436.95
24590.53
Promedio 17776.31 17812.16
Máximo 24905.08 24905.08
4.2.3.7 Resultados para Liver. En la Tabla 4.16, se ve que K-means mejorado
en promedio es mejor que el promedio de K-means estándar, SPSS y Weka.
Tabla 4.16 Resultados experimentales en eficacia para Liver.
Liver
K-means mejorado K-means estándar SPSS Weka
Mínimo 9865.34 10212.54
10231.43
10921.56
Promedio 9961.43 10212.54
Máximo 10231.43 10212.54
4.2.4 Análisis comparativo de la eficacia
En esta sección se realiza un análisis comparativo del error al cuadrado h(W, C)
en la que convergen los algoritmos con las bases de datos que se están
Capítulo 4 RESULTADOS EXPERIMENTALES
43
manejando. En particular se contrastan los resultados obtenidos por el algoritmo
K-means mejorado contra los resultados obtenidos por los demás algoritmos en
porcentaje.
En la Tabla 4.17 se muestra dicho análisis comparativo. En la primera
columna se muestra el nombre de la base de datos; en la segunda y tercera, el
error al cuadrado h(W, C) promedio en que converge el algoritmo K-means
mejorado y K-means estándar respectivamente. En la cuarta columna se muestra
la superioridad del algoritmo K-means mejorado en porcentaje. En la columna
cinco se indica el error al cuadrado h(W, C) con el que converge el paquete
comercial SPSS; y en la sexta, el porcentaje en el que es mejor el algoritmo
K-means mejorado. En la columna siete se muestra el error al cuadrado h(W, C)
con el que converge Weka; y en la octava columna, la superioridad del algoritmo
K-means mejorado en porcentaje.
Como se observa en la Tabla 4.17, en el mejor de los casos el algoritmo
mejorado vs. K-means estándar ganó con 7% en la base de datos Diabetes, el
algoritmo mejorado vs. SPSS ganó con 7% en la base de datos Diabetes y el
algoritmo mejorado vs. Weka ganó con 33% en la base de datos Diabetes. En el
peor de los casos el algoritmo mejorado vs. K-means estándar obtuvo 0.02% en la
base de datos Bin-packing, el algoritmo mejorado vs. SPSS ganó con 0.02% en la
base de datos Bin-packing y el algoritmo mejorado vs. Weka ganó con 8.79% en la
base de datos Liver.
Capítulo 4 RESULTADOS EXPERIMENTALES
44
Tabla 4.17 Análisis comparativo en eficacia.
Base de
datos
K-means
mejorado
K-means
estándar SPSS WEKA
Error al
cuadrado
h(W, C)
promedio
Error al
cuadrado
h(W, C)
promedio
%
Error al
cuadrado
h(W, C)
%
Error al
cuadrado
h(W, C)
%
Bin-packing 580.17 580.29 0.02 580.27 0.02 669.30 13.32
Vehicle 46989.72 47122.65 0.28 50001.83 6.02 55949.21 16.01
Glass 210.54 210.58 0.02 211.51 0.46 235.82 10.72
Diabetes 48399.88 52072.20 7.05 52072.24 7.05 73193.07 33.87
Heart 10692.66 10698.48 0.05 10700.84 0.08 13692.85 21.91
Wine 17776.32 17812.16 0.20 18436.95 3.58 24590.54 27.71
Liver 9961.43 10212.55 2.46 10231.44 2.64 10921.56 8.79
45
Capítulo 5
CONCLUSIONES Y TRABAJOS FUTUROS
En este capítulo se presentan las aportaciones de esta investigación, y se
sugieren direcciones para trabajos futuros.
5.1 CONCLUSIONES
Un buen número de mejoras del algoritmo K-means han estado enfocadas a la
inicialización del algoritmo [Su 2004, Pelleg 2000, Likas 2003]; sin embargo, uno
de los factores que más inciden en el costo computacional es el número de
iteraciones que se realizan para que el algoritmo converja.
En este trabajo, se muestra que es factible mejorar el algoritmo K-means
estándar mediante un nuevo criterio de convergencia. Durante el monitoreo de una
implementación del algoritmo estándar, y en particular observando el valor del
error cuadrado para cada iteración, se observó que el algoritmo no paraba en un
óptimo local; es decir, a pesar de haber obtenido un mínimo local, el algoritmo
continuaba realizando iteraciones. Este patrón de comportamiento en el algoritmo
se repitió en aproximadamente el 96% de los casos en que se corrió con la base
de datos Diabetes.
Capítulo 5 CONCLUSIONES Y TRABAJOS FUTUROS
46
Un análisis detallado del algoritmo nos permitió identificar que el algoritmo
no paraba debido a que su condición de convergencia no incorporaba el error al
cuadrado.
En contraste, en este trabajo se aporta una nueva condición de
convergencia que incorpora el error al cuadrado, lo cual permite garantizar que el
algoritmo pare en óptimos locales, reduciendo el número de iteraciones y
mejorando la calidad en la solución.
Para validar la mejora propuesta se usó un conjunto de bases datos reales
obtenidas del repositorio de aprendizaje máquina [Hettich 1998], las cuales se
procesaron con el algoritmo K-means mejorado, K-means estándar, la librería
Weka de Java y el paquete comercial SPSS. Los resultados experimentales fueron
alentadores; por ejemplo, en la base de datos Diabetes la solución se obtuvo en 3
iteraciones con el algoritmo mejorado, mientras que con K-means estándar se
obtuvo en 15; con SPSS, en 17; y con Weka, en 9. Con relación a la calidad el
algoritmo mejorado fue superior en 7.05% con respecto al K-means estándar,
7.05% con respecto a SPSS y 33.87% mejor que Weka.
Finalmente consideramos que la mejora propuesta puede ser incorporada
en algunas otras variantes del algoritmo K-means contribuyendo a mejorar su
desempeño.
Capítulo 5 CONCLUSIONES Y TRABAJOS FUTUROS
47
5.2 TRABAJOS FUTUROS
En el desarrollo de este trabajo de tesis surgieron varias propuestas de trabajos
futuros:
� Implementación optimizada del algoritmo K-means con la condición de
convergencia propuesta en esta tesis, ya que en ésta tesis se implementó
con propósito de estudio; es decir, se introdujo código con la finalidad de
monitorear su comportamiento.
� Incorporación de la condición de convergencia propuesta en esta tesis en
otras variantes del algoritmo K-means.
48
REFERENCIAS
[Berkhin 2002] Berkhin, P.: Survey of Clustering Data Mining Techniques. In
Accrue . San Jose, CA. (2002)
[Cruz 2004] Cruz, L.: Clasificación de Algoritmos Heurísticos para la Solución de
Problemas de Bin Packing. Tesis doctoral. Centro Nacional de Investigación y
Desarrollo Tecnológico (CENIDET) Cuernavaca, México (2004)
[Fraire 2005] Fraire, H.: Una Metodología para el Diseño de la Fragmentación y
Ubicación en Grandes Bases de Datos Distribuidas. Tesis doctoral. Centro
Nacional de Investigación y Desarrollo Tecnológico (CENIDET) Cuernavaca,
México (2005)
[Halkidi 2001] Halkidi, M., Batistakis, Y., Vazirgiannis, Michalis.: On Clustering
Validation Techniques. In Journal of Intelligent Information Systems. Publishers
Kluwer Academic. (2001) 107-145
[Hamerly 2002] Hamerly, G., Elkan, C.: Alternatives to the K-means Algorithm that
Find Better Clusterings. In Proceedings of the Eleventh International Conference
on Information and Knowledge Management. ACM Press. New York (2002) 600-
607
[Hettich 1998] Hettich, S., Blake, C.L., Merz, C.J: UCI Repository of Machine
Learning Databases. Department of Information and Computer Science,
University of California. Irvine, CA (1998)
http://www.ics.uci.edu/~mlearn/MLRepository.html.
[Jain 1999] Jain, A.K, Murty, M.N., Flynn, P.J.: Data Clustering: A Review. ACM
Computing Survey. Vol. 31, No. 3 (1999) 264-323
49
[Kanungo 2000] Kanungo, T., Mount, D M., Netanyahu, N S., Piatko, C.: The
Analysis of a Simple K-means Clustering Algorithm. Proceedings or the
Sixteenth Annual Symposium on Computational Geometry, ACM Press, New
York, 2000, 100-109
[Kanungo 2002] Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D.,
Silverman, R., Wu, A.Y.: An Efficient K-means Clustering Algorithm: Analysis
and Implementation. Pattern Analysis and Machine Intelligence, IEEE
Transactions on Pattern Analysis and Machine Intelligence. Vol. 24, No. 7 (2002)
881-892
[Likas 2003] Likas, A., Vlassis, N., Verbeek, J.J.: The Global K-means Clustering
Algorithm. Pattern Recognition. The Journal of the Pattern Recognition Society.
Vol. 36, No. 2 (2003) 451-461
[MacQueen 1967] MacQueen, J.: Some Methods for Classification and Analysis of
Multivariate Observations. In Proceedings Fifth Berkeley Symposium
Mathematics Statistics and Probability. Vol. 1. Berkeley, CA (1967) 281-297
[Mehmed 2003] Mehmed, K.: Data Mining: Concepts, Models, Methods, and
Algorithms. John Wiley & Sons Inc. (2003)
[Ordonez 2004] Ordonez, C.: Programming the K-means Clustering Algorithm in
SQL. Proceedings or the 2004 ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining., 2004, 823-828
[Pelleg 2000] Pelleg, D., Moore, A.: X-means: Extending K-means with Efficient
Estimation of the Number of Clusters. In Proceedings 17 th. International
Conference on Machine Learning. Morgan Kaufmann Publishers. San Francisco,
CA (2000) 727-734
50
[Pham 2004] Pham, D T., Nguyen, C D.: An Incremental K-means Algorithm. In
Journals ProQuest Science. Proceedings of the Institution of Mechanical
Engineers., 2004, Vol. 218, Part. C7, 783-795
[SPSS] SPSS Inc. SPSS Ver. 10.0. On product Information. Chicago, Illinois.
[Su 2001] Su, M.C., Chou, C.H.: A Modified Version of the K-Means Algorithm with
a Distance Based on Cluster Symmetry. Pattern Analysis and Machine
Intelligence, IEEE Transactions on Pattern Analysis and Machine Intelligence.
Vol. 23, No. 6 (2001) 674-680
[Su 2004] Su, T., Dy, J.: A Deterministic Method for Initializing K-means Clustering.
Proceeding of the 16th IEEE International Conference on Tools with Artificial
Intelligence (ICTAI 2004), 2004, 784-786
[Witten 1999] Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning
Tools and Techniques with Java Implementations. Morgan Kaufmann
Publishers. San Diego, CA (1999)
51
Anexo A
GENERADOR DE BASES DE DATOS SINTÉTICAS
A.1 Implementación del generador de bases de datos sintéticas
Con la finalidad de validar el algoritmo K-means implementado, fue necesario
saber con antelación la agrupación óptima para poder comparar el agrupamiento
generado por dicho algoritmo. Para esto se desarrolló un módulo generador de
bases de datos sintéticas. Cabe hacer notar que en la literatura especializada no
se menciona este tipo de herramientas.
La base de datos sintética que se produce, tiene la propiedad de simetría
entre los elementos de un grupo con respecto a los hiperplanos que cortan el
centroide de cada grupo. Debido a que uno de los datos de entrada es el conjunto
de centroides, es posible obtener los agrupamientos óptimos. En la Tabla A.1 y
Tabla 2.1 se muestran las definiciones y notación usada en el pseudocódigo.
Anexo A
52
Tabla A.1 Notación y definiciones.
d(Xij, Ci)=
∑2
=1
( - )d
ijl ill
x c
Función de error al cuadrado. La función es un
índice de similaridad que cuantifica la distancia entre
un objeto Xij del conjunto de datos Xi y el centroide Ci
del grupo k.
rk Es el radio de un círculo imaginario dentro del cual
estarán los objetos generados aleatoriamente para el
k-ésimo grupo.
nk = (2d) (mk) Con esta función se calcula el número de objetos.
mk Es el número de objetos semilla.
D Es el número de dimensiones para todos los
objetos.
Na Es un número real generado aleatoriamente dentro
del intervalo [0,1].
si Es la cardinalidad del grupo Wk.
Los parámetros de entrada para el generador de bases de datos sintéticas
son: k, Ck, rk, mk, d.
Los parámetros de salida para el generador de bases de datos sintéticas
son: la base de datos X, el conjunto de grupos W y la suma del error al cuadrado
de cada grupo Wk.
A.2 Algoritmo del generador de casos
Paso 1. Genera mk objetos semilla. En este paso se generan de forma aleatoria
mk objetos dentro de un cuadrado imaginario cuya esquina superior derecha es el
objeto centroide Ck. Tomando en cuenta que el algoritmo K-means descubre
figuras globulares, se agregó una condición que elimina los objetos Xij cuya
distancia con respecto al centroide Ck se encuentra fuera del radio rk. Este
Anexo A
53
procedimiento se encuentra entre las líneas 1 a la 13 del pseudocódigo de la
Figura A.1.
ALGORITMO Generador( X, k, rk, mk, d, Ck )
ENTRADA k, rk, mk, d, Ck
SALIDA X
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Para ( i ← 1 hasta k ) hacer
Wi ← Ø;
Para ( j ← 1 hasta mk) hacer
Para (l← 1 hasta d ) hacer
xijl ← ( cil - ri ) + ( Na - ri ) ;
Fin Para ;
Si (d( Xij, Ci ) <= r2i ) hacer
Wi ← Wi U { Xij };
De lo contrario hacer
j ← j – 1;
Fin Si ;
Fin Para ;
Fin Para ;
Para ( i ← 1 hasta k ) hacer
Para ( l ← 1 hasta d ) hacer
Para ( j ← 1 hasta si ) hacer
Para ( h ← 1 hasta d ) hacer
Si ( h = l ) hacer
x’’h ← ( cih - xijh ) + cih;
De lo contrario hacer
x’’h ← xijh;
Fin Si ;
Fin Para ;
Wi ← Wi U { X’ };
Fin Para ;
Fin Para ;
Fin Para ;
Para ( i ← 1 hasta k ) hacer
X ← X U Wi ;
Fin Para ;
Regresa ( X );
Figura A.1 Pseudocódigo del generador de bases de datos sintéticas.
Anexo A
54
Paso 2. Genera k grupos con nk elementos. Con la finalidad de conocer
la agrupación óptima, este paso realiza una copia espejo en cada una de las
dimensiones y finalmente integra los k grupos dentro de la base de datos X. Este
procedimiento se encuentra entre las líneas 14 a la 31.
A.3 Generación de datos sintéticos con el generador de bases de datos.
En esta sección se muestra el procedimiento para generar una base de datos
sintética con el generador implementado. Los valores de entrada se muestran en
la Tabla A.2. En la primera columna se muestra el parámetro; y en la segunda
columna, el valor del mismo.
Tabla A.2 Valores de entrada al generador de casos de pruebas.
Parámetr
o
Valor
k 2
C1 (-4, 2)
C2 (3, 2)
r1 3
r2 3
m1 5
m2 5
d 2
Paso 1. Genera mk objetos semilla. En este paso se generan m1 objetos
dentro de un radio 1r . En la Figura A.2 se muestran gráficamente los objetos
generados. De la misma forma se generan m2 objetos.
Anexo A
55
-1
-0,5
0
0,5
1
1,5
2
2,5
0
Centroide Puntos aleatorios
Figura A.2. Calculando el primer grupo.
Paso 2. Genera k grupos con nk elementos. En este paso se copian los
objetos para cada una de las dimensiones. En la Figura A.3 se muestra cómo el
algoritmo genera una copia en la primera dimensión, y en la Figura A.4 se muestra
cómo el algoritmo copia los objetos para la siguiente dimensión. Finalmente
integra los grupos generados como se muestra en a Figura A.5.
-1
-0,5
0
0,5
1
1,5
2
2,5
-6 -4 -2 0
Centroide Puntos aleatorios Copia en x
Figura A.3 Se genera una copia espejo en una dimensión.
Anexo A
56
-2
-1
0
1
2
3
4
5
6
-6 -4 -2 0
Centroide Puntos aleatorios Copia en x Copia en y
Figura A.4 Copia los objetos para la segunda dimensión.
-2
-1
0
1
2
3
4
5
6
-8 -6 -4 -2 0 2 4 6
Centroide 1 Grupo1 Centroide 2 Grupo 2
Figura A.5 Grupos sintéticos generados.
top related