Fuzzy clustering

El agrupamiento difuso (en inglés, fuzzy clustering) es una clase de algoritmos de agrupamiento donde cada elemento tiene un grado de pertenencia difuso a los grupos.

Este tipo de algoritmos surge de la necesidad de resolver una deficiencia del agrupamiento exclusivo, que considera que cada elemento se puede agrupar inequívocamente con los elementos de su cluster y que, por lo tanto, no se asemeja al resto de los elementos. Tras la introducción de la lógica difusa por Zadeh en 1965 surgió una solución para este problema, caracterizando la similitud de cada elemento a cada uno de los grupos. ​ Esto se logra representando la similitud entre un elemento y un grupo por una función, llamada función de pertenencia, que toma valores entre cero y uno. Los valores cercanos a uno indican una mayor similitud, mientras que los cercanos a cero indican una menor similitud. Por lo tanto, el problema del agrupamiento difuso se reduce a encontrar una caracterización de este tipo que sea óptima.

Los algoritmos de agrupamiento difuso se han aplicado ampliamente en diferentes áreas como el procesamiento de imágenes, sistemas de ingeniería, estimación de parámetros, entre otras. ​

Partición difusa

Una partición difusa es una partición que caracteriza la participación de cada muestra en todos los grupos utilizando funciones de pertenencia que toman valores entre cero y uno. Además, cumplen que para cada muestra la suma de sus participaciones en cada grupo es uno. De esta forma, es posible traducir el problema del agrupamiento difuso en encontrar una partición difusa óptima. A continuación se encuentra una definición más formal de este concepto.

Sea X = (x₁,...,x_n) un subconjunto de un espacio euclidiano de dimensión s y c un entero positivo mayor que uno. Una partición difusa de X en c grupos es una tupla de c funciones de pertenencia $\mu =(\mu _{1},\ldots ,\mu _{c})$ que cumplen que:

1. $0\leq \mu _{i}(x)\leq 1,\forall i=1,\ldots ,c$
2. $0<\sum \limits _{j=1}^{n}\mu _{i}(x_{j})<1,\forall i$
3. $\sum \limits _{i=1}^{c}\mu _{i}(x_{j})=1,\forall j$

Las particiones difusas se representan como una matriz asociando cada fila a uno de los c grupos y cada columna a uno de los elementos de X, de forma tal que el valor en la fila i y la columna j indique la pertenencia del elemento j al grupo i. Más formalmente, el conjunto de las particiones difusas se puede definir como:

$M_{fc}=\{U\in \Re ^{c\times n}|U=[u_{ij}];u_{ij}\in [0,1]\forall i,j;\sum \limits _{i=1}^{c}u_{ij}=1\forall j;\sum \limits _{j=1}^{n}u_{ij}>0\forall i\}$

Algoritmos Fuzzy c-Means

Los algoritmos Fuzzy c-Means son algunos de los principales algoritmos utilizados en el agrupamiento difuso y pertenecen a una clase de algoritmos basados en funciones objetivo.​ Estos algoritmos definen un criterio de agrupamiento en la forma de una función objetivo que depende de la partición difusa. El procedimiento, en sentido general, consiste en minimizar iterativamente esta función hasta obtener una partición difusa óptima.

Se han propuesto varios criterios de agrupamiento para obtener la partición difusa óptima para X, pero el más popular hasta el momento está asociado con la función de error mínimo cuadrático:​

$J_{m}(U,v)=\sum \limits _{k=1}^{n}\sum \limits _{i=1}^{c}(u_{ik})^{m}d_{ik}^{2}$

El valor $d_{ik}^{2}$ indica la distancia cuadrada entre los elementos de X y los centros de los grupos y puede calcularse utilizando la siguiente fórmula:

$d_{ik}^{2}=||x_{k}-v_{i}||_{A}^{2}=(x_{k}-v_{i})^{T}A(x_{k}-v_{i})$

donde:

• $X=(x_{1},x_{2},\ldots ,x_{n})\subset \Re ^{s}$ son los datos,
• $v_{i}=(v_{i1},v_{i2},\ldots ,v_{ic})$ es el vector centro del grupo i,
• || ||_A es la norma inducida por A
• A es una matriz definida positiva de pesos de dimensiones $(n\times n)$.

En particular, si A es la matriz identidad, $d_{ik}^{2}$ es el cuadrado de la distancia euclidiana.

El peso asociado a cada distancia cuadrada, $(u_{ik})^{m}$, es la m-ésima potencia del grado de pertenencia del k-ésimo dato al grupo i. Cuando $m\rightarrow 1$ la partición óptima es cada vez más cercana a una partición exclusiva, mientras que cuando $m\rightarrow \infty$ la partición óptima se aproxima a la matriz con todos sus valores iguales a (1/c). Los valores de m que normalmente se utilizan son valores en el intervalo [1,30]. Cada selección de un valor particular de m marca un algoritmo Fuzzy c-Means específico.​

Teniendo esto en cuenta, el procedimiento general de los algoritmos Fuzzy c-Means puede formalizarse en los siguientes pasos:

1. Fijar c, m, A y ||k||_A. Elegir una matriz inicial $U^{(0)}\in M_{fc}$.
2. Calcular los centros de los grupos con la fórmula $v_{i}={\frac {\sum \limits _{k=1}^{n}(u_{ik})^{m}x_{k}}{\sum \limits _{k=1}^{n}(u_{ik})^{m}}};1\leq i\leq c$.
3. Actualizar la matriz de partición difusa U = [u_ik] con $u_{ik}=(\sum \limits _{j=1}^{c}({\frac {d_{ik}}{d_{jk}}})^{\frac {2}{m-1}})^{-1};1\leq k\leq n;1\leq i\leq c$.
4. Si se alcanzó el criterio de parada, terminar. En caso contrario, regresar al paso 2.

Algunos de los criterios de parada más utilizados son:​

• Un número máximo de iteraciones
• Que la variación en la matriz U sea muy pequeña:

$||U^{k+1}-U^{k}||<\epsilon$.

Algoritmos Possibilistic c-Means

Los algoritmos Possibilistic c-Means aparecen con el objetivo de resolver el mal comportamiento de los algoritmos Fuzzy c-Means al ser utilizados en conjuntos de datos con mucho ruido. ​ Estos algoritmos se caracterizan por interpretar los valores u_ij como grados de compatibilidad con los grupos, en lugar de probabilidades de pertenencia. Para ello, se relaja la restricción de las particiones difusas que obliga a que la suma de los grados de pertenencia de un elemento hacia todos los grupos sea uno, exigiendo solamente que al menos uno de los grados de pertenencia sea positivo.

Por lo tanto, las restricciones en la definición de partición difusa podrían reescribirse como:

1. $0\leq \mu _{i}(x)\leq 1,\forall i=1,\ldots ,c$
2. $0<\sum \limits _{j=1}^{n}\mu _{i}(x_{j})<1,\forall i$
3. $\max \limits _{i}\mu _{i}(x_{j})=1,\forall j$

Una de las funciones objetivos más utilizadas por estos algoritmos es la siguiente:​

$J_{m}(U,v,\eta )=\sum \limits _{k=1}^{n}\sum \limits _{i=1}^{c}(u_{ik})^{m}d_{ik}^{2}+\sum \limits _{i=1}^{c}\eta _{i}\sum \limits _{k=1}^{n}(1-u_{ik})^{m}$

Esta es la misma función objetivo de los algoritmos Fuzzy c-Means con un término añadido que impide que la partición obtenida sea la solución trivial donde todos los valores de pertenencia sean iguales a cero. El vector $\eta =(\eta _{1},\eta _{2},\ldots ,\eta _{c})$ es un vector de valores positivos, donde sus valores $\eta _{i}$ denotan la distancia desde el centro del grupo i a la que el grado de pertenencia de un elemento es 0.5. Estos valores determinan el tamaño y forma de sus grupo correspondiente y generalmente se calculan utilizando la siguiente fórmula:​

$\eta _{i}=K{\frac {\sum \limits _{j=1}^{n}u_{ij}^{m}d_{ij}^{2}}{\sum \limits _{j=1}^{n}u_{ij}^{m}}}$

donde K es normalmente uno.

El procedimiento general para estos algoritmos es:

1. Fijar c, m, A y ||k||_A. Elegir una matriz inicial $U^{(0)}\in M_{fc}$. Estimar los valores de $\eta$.
2. Calcular los centros de los grupos con la fórmula $v_{i}={\frac {\sum \limits _{k=1}^{n}(u_{ik})^{m}x_{k}}{\sum \limits _{k=1}^{n}(u_{ik})^{m}}};1\leq i\leq c$.
3. Actualizar la matriz de partición difusa U = [u_ik] con $u_{ik}=(1+({\frac {d_{ik}^{2}}{\eta _{i}}})^{\frac {1}{m-1}})^{-1};1\leq k\leq n;1\leq i\leq c$.
4. Si se alcanzó el criterio de parada, terminar. En caso contrario, regresar al paso 2.

Los criterios de parada utilizados por estos algoritmos son similares a los utilizados por los algoritmos Fuzzy c-Means.

Puede consultar también

• K-means
• Clustering

Referencias

• Datos: Q5511111