Fuzzy K Means

Mariano Rivera

Abril 2017

A diferencia de K-Means, en cada iteración se asigna una membrecía (no se asigna exclusivamente un dato a cada clase)

El grado membrecía es el que dá el nombre de Fuzzy (o difuso)

Puede interpretarse como la probabilidad de que una clase sea la correcta para un dato.

Sinónimos:
Membrecía = Pretenecia = Similitud

Sean

• $x = \{x_i\}_{i=1,2,\ldots,M}$ con $x_i \in\mathbb{R}^n$ son los datos,
• $m = \{m_k\}_{k=1,2,\ldots,K}$ con $m_k \in\mathbb{R}^n$ los centroides (representantes o medias) para los $K$ clusters
• $p = \{p_{ik}\}_{i=1,2,\ldots,M; \, k=1,2,\ldots,K}$; tal que $p_{ik}$ se interpreta como la pertenecia del dato $x_i$ al cluster cuyo representante es $m_k$ (i-ésimo dato and k-ésimo cluster)
• $\| \cdot \|^2$ es la norma Euclideana al cuadrado.

Función Objetivo de Fuzzy K-Means

Luego,el clustring por Fuzzy K-Means se obtiene de minimizar

(1)
$\underset{m,\,p}{\arg\min} \frac{1}{2} \sum_k \sum_i \| x_i- m_k \|^2 p_{ik}^\mu \\ \;\;\;\;\;\; \text{s.t.} \;\;\; \sum_k p_{ik} =1 \\ \;\;\;\;\;\;\;\;\;\;\;\; p_{ik} \ge 0$

donde $\mu \in (1, \infty)$ es un parámetro del algoritmo.

Lagrangiano

El Lagrangiano del problema (1) esta dado por

(2)
$\mathcal{L} (m,p, \lambda,s) = \frac{1}{2}\sum_k \sum_i \| x_i- m_k \|^2 p_{ik}^\mu - \sum_i \lambda_i \left( \sum_k p_{ik} -1 \right) -\sum_k\sum_i s_{ik} p_{ik}$

donde $\lambda <> 0$ y $s\ge 0$ son los multiplicadores de Lagrange de las restricciones de igualdad y nonegatividad, respectivamente.

definimos

(3)
$d_{ik} \overset{def}{=} \| x_i- m_k \|^2$

Condiciones KKTs

(4)
$\frac{\partial \mathcal{L}}{\partial m_k} = 0 \rightarrow \sum_i ( m_k - x_i) p_{ik}^\mu =0 \rightarrow m_k = \frac{\sum_i x_i \, p^{\mu}_{ik}}{ \sum_i p^{\mu}_{ik}}$

(5)
$\frac{\partial \mathcal{L}}{\partial p_{ik}} = 0 \rightarrow \frac{\mu}{2} d_{ik} p_{ik}^{\mu-1} - \lambda_i - s_{ik} =0$

(6)
$\sum_k p_{ik} -1 =0$

(7)
$p_{ik}s_{ik} = 0$

(8)
$p_{ik},s_{ik} \ge 0$

Tomando (5):

(9)
$p_{ik}^{\mu-1} = \frac{2}{\mu} \frac{ \lambda_i + s_{ik}}{d_{ik}}$

Ahora, haremos una “apuesta”, asumiremos que el valor óptimo del multiplicador de Lagrange de la nonegatividad será $s_{ik} =0$. Luego, por (7) y (8) debemos obtener una fórmula para la membrecia que satisfaga estrictamente $p_{ik} >0$. Si la suposición no es correcta, la fórmula que obtengamos para $p_{ik}$ no garantizará que ésta sea estrictamente positiva.

Entonces, asumiendo que $s_{ik}^\ast =0$, (9) se reduce a:

$p_{ik}^{\mu-1} = \frac{2}{\mu} \frac{ \lambda_i}{d_{ik}}$
y tenemos que

(10)
$p_{ik} = \left[ \frac{2}{\mu} \frac{ \lambda_i}{d_{ik}}\right]^{\frac{1}{\mu-1}}$

Sumando sobre $k$ y aplicando (6):

(11)
$\sum_k \left[ \frac{2}{\mu} \frac{ \lambda_i}{d_{ik}}\right]^{\frac{1}{\mu-1}} =1 \\ \lambda_i^{\frac{1}{\mu-1}} \sum_k \left[ \frac{2}{\mu \, d_{ik}}\right]^{\frac{1}{\mu-1}} =1$
y tenemos que

(12)
$\lambda_i = \left[ \frac{1}{ \sum_k \left[ \frac{2}{\mu \, d_{ik}}\right]^{\frac{1}{\mu-1}}} \right]^{\mu-1}$

Es posible notar que $\lambda_i >0$, y sustituyendo en (9) tendremos $p_{ik} >0$. Luego, fué correcto suponer $s_{ik}=0$.

Procedamos a hacer la sustitución de (12) en (9):

(13)
$p_{ik} = \left[ \frac{2}{\mu} \frac{1}{d_{ik}}\right]^{\frac{1}{\mu-1}} \left[ \frac{1}{ \sum_{q} \left[ \frac{2}{\mu} \frac{1}{d_{iq}}\right]^{\frac{1}{\mu-1}}} \right]$

Un caso particularmente interesante ocurre para $\mu =2$:

(14)
$p_{ik} = \frac{ \frac{1}{d_{ik}} }{ \sum_{q} \frac{1}{d_{iq}} }$

Algoritmo de Solución Fuzzy K-Means

La estrategia de solución consiste en

---

Inicializar para los centroides $m$. Entonces

Iterar hasta $\| m^{(t)} -m^{(t-1)} \| \le \tau$ (donde $\tau$ es un umbral propuesto):

1. Calcular el cuadrado de las distancias Eicideanas: $d_{ik}$ con (3).
2. Calcular $p_{ik}$ usando (13).
3. Actualizar los centroides $m_k$ usando (4).

Terminar con la asignación de clases $c_{i} = \underset{k}{\arg\,\max} \; p_{ik}$.

---

Ejercicios.

Derive las versiones del algoritmo para:

a) Usar $\| x_i- m_k \|_{A_k} = (x_i- m_k)^\top A_k (x_i- m_k)$ la norma inducida por la matrix de pesos simétrica positiva definida $A \in\mathbb{R}^{m \times m}$. Con $A_k= \Sigma^{-1}_k$ la matriz de covarianza que puede ser recalculada:

$\Sigma_k = \frac{1}{m-1} \sum_i (x_{i}-m_{k})^\top (x_{i}-m_{k}) p^\mu_{ik}$

b) Para el caso límite ${\mu \rightarrow 1}$.

K-Medoides

Un variante de Fuzzy K-Medias (FKM) es K-Medoides.

K-Medoides consiste en generalizar el método para datos en espacios donde la distancia Eclideana no esta definida; pero si tenemos definida una disimilaridad.

Dado que no se tienen definida la distancia Euclideana, no es posible calcular una media.

El método selecciona la medoide, que es el dato con la menor suma de disimilaridades a los miembros de la misma clase (similarmente a como se motiva K-Medias).

El algorithmo de K-Medoides esta dado por

---

Inicializar aleatoriamente las medoides $m$ usando $k$ datos.

Iterar hasta $\{ m^{(t)} \} \setminus \{m^{(t-1)} \} = \emptyset$:

1. Calcular las disimilaridades $d_{ik}$.
2. Calcular $c_{i} = \underset{k}{\arg\,\min} \; d_{ik}$.
3. Actualizar las medoides, para la clase k:
   $i^* = \underset{i}{\arg\,\min} \; \left\{ \sum_{ j : c_i, c_j = k} d_{ij} \right\}$
   Luego $m_k=x_{i^*}$

Terminar con la asignación de clases $c_{i}$.

---