Agrupamiento de FLAME

Tipo de algoritmo para agrupamiento de datos

El agrupamiento difuso por aproximación local de membresías (FLAME) es un algoritmo de agrupamiento de datos que define los clústeres en las partes densas de un conjunto de datos y realiza la asignación de clústeres únicamente en función de las relaciones de vecindad entre los objetos. La característica clave de este algoritmo es que las relaciones de vecindad entre los objetos vecinos en el espacio de características se utilizan para restringir las membresías de los objetos vecinos en el espacio de membresía difusa.

Descripción del algoritmo FLAME

El algoritmo FLAME se divide principalmente en tres pasos:

1. Extracción de la información de la estructura del conjunto de datos:
   1. Construya un gráfico de vecindad para conectar cada objeto con sus K vecinos más cercanos (KNN);
   2. Estimar una densidad para cada objeto en función de su proximidad a su KNN;
   3. Los objetos se clasifican en 3 tipos:
      1. Objeto de soporte de clúster (CSO): objeto con densidad mayor que todos sus vecinos;
      2. Valores atípicos del clúster: objeto con una densidad menor que la de todos sus vecinos y menor que un umbral predefinido;
      3. el resto.
2. Aproximación local/de barrio de membresías difusas :
   1. Inicialización de membresía difusa:
      1. A cada OSC se le asigna una membresía fija y completa para representar a un clúster;
      2. A todos los valores atípicos se les asigna una membresía fija y completa al grupo de valores atípicos;
      3. El resto se asigna con membresías iguales a todos los clústeres y al grupo de valores atípicos;
   2. Luego, las membresías difusas de todos los objetos de tipo 3 se actualizan mediante un procedimiento iterativo convergente llamado Aproximación local/de vecindad de membresías difusas , en el que la membresía difusa de cada objeto se actualiza mediante una combinación lineal de las membresías difusas de sus vecinos más cercanos.
3. Construcción de clústeres a partir de membresías difusas de dos maneras posibles:
   1. Asignación de objetos a clúster uno a uno, para asignar cada objeto al clúster en el que tiene la membresía más alta;
   2. Asignación de uno a varios grupos de objetos, para asignar cada objeto al grupo en el que tiene una membresía mayor que un umbral.

El problema de optimización en FLAME

La aproximación local/vecinal de membresías difusas es un procedimiento para minimizar el error de aproximación local/vecinal (LAE/NAE) definido de la siguiente manera:

${\displaystyle E(\{{\boldsymbol {p}}\})=\sum _{{\boldsymbol {x}}\in {\boldsymbol {X}}}{\bigg \|}{\boldsymbol {p(x)}}-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{\boldsymbol {p(y)}}{\bigg \|}^{2}}$

donde es el conjunto de todos los objetos de tipo 3, es el vector de pertenencia difusa del objeto , es el conjunto de vecinos más cercanos de , y con son los coeficientes que reflejan las proximidades relativas de los vecinos más cercanos. ${\displaystyle {\boldsymbol {X}}}$ ${\displaystyle {\boldsymbol {p(x)}}}$ ${\displaystyle {\boldsymbol {x}}}$ ${\displaystyle {\mathcal {N}}(x)}$ ${\displaystyle {\boldsymbol {x}}}$ ${\displaystyle w_{\boldsymbol {xy}}}$ ${\displaystyle \sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}=1}$

La NAE se puede minimizar resolviendo las siguientes ecuaciones lineales con solución única que es el mínimo global único de NAE con valor cero:

${\displaystyle p_{k}({\boldsymbol {x}})-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}p_{k}({\boldsymbol {y}})=0,\quad \forall {{\boldsymbol {x}}\in {\boldsymbol {X}}},\quad k=1,...,M}$

donde es el número de OSC más uno (para el grupo de valores atípicos). Se puede utilizar el siguiente procedimiento iterativo para resolver estas ecuaciones lineales: ${\displaystyle M}$

${\displaystyle {{\boldsymbol {p}}^{t+1}({\boldsymbol {x}})}=\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{{\boldsymbol {p}}^{t}({\boldsymbol {y}})}}$

Una ilustración sencilla de un conjunto de datos de prueba de dos dimensiones

Véase también

• Agrupamiento de datos
• Agrupamiento difuso

Enlaces externos

• BMC Bioinformatics (2007): FLAME, un nuevo método de agrupamiento difuso para el análisis de datos de microarrays de ADN
• Códigos fuente de FLAME en C publicados bajo licencia similar a FreeBSD en GoogleCode