PDF de programación - Algoritmos de agrupamiento

Algoritmos de agrupamiento

D. Pascual 1, F. Pla 2, S. Sánchez 2

1. Departamento de Computación

Universidad de Oriente



Avda. Patricio Lumumba S/N. 90500 Santiago de Cuba, Cuba

[email protected]

2. Departamento de Lenguajes y Sistemas Informáticos

Universitat Jaume I

Avda. Sos Baynat S/N. 12071 Castellón, España

{pla, sanchez}@lsi.uji.es

Resumen


En el presente trabajo mostramos algunos de los resultados del estudio realizado
sobre diferentes técnicas de agrupamiento, las que se encuentran dentro del campo
de estudio del Reconocimiento de Patrones, haciendo hincapié en las técnicas
basadas en densidad. Mostramos el estudio comparativo de tres algoritmos
empleando bases de datos reales y artificiales.

Palabras clave: Algoritmos de agrupamiento, Algoritmos basados en densidad.


1 Introducción

Debido al desarrollo alcanzado con los microprocesadores se pueden manejar
grandes volúmenes de datos como puntos en espacios de una alta dimensionalidad,
éstos aparecen en varias esferas de la vida real, en bases de datos de corporaciones
financieras, telecomunicaciones, medicina, imágenes de satélite, etc., numerosas
son las aplicaciones en las que se requiere del manejo de bases de datos espaciales
con el objetivo de conocer acerca de la identificación de grupos, para descubrir
importantes distribuciones del espacio en estudio, lo cual puede ser resuelto con el
empleo de algún algoritmo de agrupamiento conveniente, por lo que el estudio,
aplicación y creación de nuevos algoritmos constituye un desafío importante en la
actualidad.

El Reconocimiento de Formas constituye un amplio conjunto de técnicas para el
tratamiento de datos entre las que se puede mencionar: la selección y extracción
de características, la clasificación de un objeto en un grupo dado y la división de
los datos en grupos (agrupamiento). Uno de los enfoques en el Reconocimiento
de Formas, en función del tipo de espacio de representación utilizado es el



Reconocimiento Estadístico de Formas que se apoya en la Teoría de Decisión,
éste asume que el espacio de representación tiene una estructura de espacio
vectorial y/o métrico y no se supone ninguna relación estructural entre las
distintas características. Dentro de este enfoque, se distingue entre
las
aproximaciones paramétrica y no paramétrica. En el primer caso, se asume un
conocimiento a priori sobre la forma funcional de las distribuciones de
probabilidad de cada clase sobre el espacio de representación, las cuales vendrán
determinadas por un conjunto finito y normalmente fijo de parámetros, las
fronteras de decisión estarán definidas por dichas distribuciones de clases. La
aproximación no paramétrica no supone ninguna forma de las distribuciones de
probabilidad sobre el espacio de representación, de modo que el único
conocimiento a priori será el correspondiente a la información inducida a partir
de un conjunto de muestras, las fronteras de decisión estarán determinadas por las
muestras del conjunto de entrenamiento. En este trabajo nos interesa el
Reconocimiento Estadístico de Formas no paramétrico, pero haremos una
pequeña alusión a la aproximación paramétrica con el estudio de las mixturas
finitas.

El problema del agrupamiento puede definirse como sigue: dados n puntos en un
espacio n-dimensional particionar los mismos en k grupos tales que los puntos
dentro de un grupo son más similares que cada uno a los de los otros grupos, dicha
similaridad se mide atendiendo a alguna función distancia (función de
disimilaridad) o alguna función de similaridad.

También es importante para el mejor funcionamiento de los algoritmos de
agrupamiento la detección de ruido para evitar la influencia negativa de éstos en la
formación de los grupos, así como la estimación del número correcto de grupos a
determinar.

Los métodos de agrupamiento no paramétricos pueden dividirse en tres grupos
fundamentales: jerárquicos [1-4], particionales [1] y basados en densidad [5-9]. En
el presente trabajo mostramos los resultados del estudio realizado acerca de los
algoritmos de agrupamiento existentes y con más detalles los basados en densidad
así como algunos experimentos realizados para comparar algunos de ellos. El
trabajo está estructurado de la siguiente forma: en la sección 2 se describen varios
algoritmos de agrupamiento, en la sección 3 se muestran algunos experimentos
realizados para comparar tres algoritmos y en la sección 4 las conclusiones.


2 Algoritmos de agrupamiento

El problema de formar grupos en un conjunto de datos es muy importante para el
conocimiento del comportamiento de una población de la cual solo se tiene una



___________________________________________________________________________________MÉTODOS INFORMÁTICOS AVANZADOS164 cantidad n de sus elementos. La solución de estos problemas se realiza mediante la
creación de algoritmos de agrupamiento.

Entre los métodos de agrupamiento paramétricos se encuentran las mixturas finitas,
éstas son una poderosa herramienta para modelar densidades de probabilidad de
conjuntos de datos univariados y multivariados, modelan observaciones las cuales
se asume que han sido producidas por un conjunto de fuentes aleatorias alternativas
e infieren los parámetros de estas fuentes para identificar qué fuente produjo cada
observación, lo que lleva a un agrupamiento del conjunto de observaciones.

Los métodos de agrupamiento no paramétricos pueden dividirse en tres grupos
fundamentales: jerárquicos, particionales y basados en densidad.

Los algoritmos jerárquicos son aquellos en los que se va particionando el conjunto
de datos por niveles, de modo tal que en cada nivel generalmente , se unen o se
dividen dos grupos del nivel anterior, según si es un algoritmo aglomerativo o
divisivo.

Los algoritmos particionales son los que realizan una división inicial de los datos
en grupos y luego mueven los objetos de un grupo a otro según se optimice alguna
función objetivo.

Los algoritmos basados en densidad enfocan el problema de la división de una base
de datos en grupos teniendo en cuenta la distribución de densidad de los puntos, de
modo tal que los grupos que se forman tienen una alta densidad de puntos en su
interior mientras que entre ellos aparecen zonas de baja densidad.


2.1 Mixturas finitas

Sea Y=[Y1, Y2, …, Yd]T una variable aleatoria d-dimensional con у=[y1, y2, …, yd]T
representando un resultado particular de Y. se dice que Y sigue una distribución de
mixtura finita con k componentes si su función de densidad de probabilidad se
puede escribir por:


k

m

yp
(

/

θ
m

)

(1)

yp
(

/

)
θ

=

∑

α
m
1
=


donde α1, α2, … αk son probabilidades mezclantes (probabilidades a priori ) que
nos indican el grado de importancia de cada uno de los k modos, cada Өm es el
vector de parámetros que define la m-ésima componente, Ө = {Ө1, …, Өk, α1, …,



___________________________________________________________________________________165MÉTODOS INFORMÁTICOS AVANZADOS αk} es el conjunto completo de parámetros necesarios para especificar la mixtura,
por supuesto las αm deben satisfacer:


αm ≥ 0 para todo m=1,…, k y

k

=∑
mα
1
=

m

1

(2).

log


La opción usual para obtener los estimados de los parámetros es el algoritmo
Expectation-Maximization (EM) [10], que produce una secuencia de estimados de
Ө aplicando alternativamente dos pasos (E-paso y M-paso) hasta obtener un
θYp
(
)
/
, siendo Y un conjunto de n muestras independientes
máximo local de:
e idénticamente distribuidas.

Este algoritmo tiene varias limitaciones: es un método local, por tanto es sensible a
la inicialización; puede converger a la frontera del espacio de parámetros donde la
verosimilitud es no acotada llevando a estimados sin sentido; si el número de
componentes es muy grande puede sobre-entrenar los datos pues estos son
incompletos y por tanto se puede obtener una forma más irregular de lo que
verdaderamente es, mientras que una mixtura con pocas componentes no es lo
suficientemente flexible para aproximar al verdadero modelo; la finalización
también es una limitación, pues llega un momento donde el proceso deja de
evolucionar por lo que se supone que alcanza la localización óptima pero esto no
nos asegura la verdadera distribución.

En el algoritmo que se describe en [10] se implementa el criterio de Mínima
longitud de un Mensaje usando una variante del EM, así reduce las limitaciones del
mismo, es robusto con respecto a la inicialización, elimina el problema de la
convergencia a la frontera del espacio de parámetros, comienza por un valor de k
grande kmax hasta otro menor kmin y obtiene buenos resultados debido a que
emplean la variante de considerar solamente las componentes de probabilidad no
cero para obtener los estimados de los parámetros. Se puede usar para cualquier
tipo de modelo de mixtura, en sus experimentos lo emplearon para mixturas de
gaussianas y a diferencia del EM este algoritmo lo que hace es minimizar la
función objetivo:

L

log(

yp
(

log

log

/

)
θ

,(
θ

y

)

+

)1

−



n
α
m
12

⎛
⎜
⎝

⎞
+⎟
⎠

k
nz
2

n
12

⎛
⎜
⎝

⎞
+⎟
⎠

(

Nk
nz
2

= ∑

N
2

m
:
α
m

>

0


donde N es la dimensión del parámetro Өm y knz el total de probabilidades no nulas.



___________________________________________________________________________________MÉTODOS INFORMÁTICOS AVANZADOS166 2.2