Agrupamento difuso (fuzzy)

O agrupamento difuso (fuzzy clustering, também conhecido como agrupamento suave, soft clustering, ou soft k-means) é uma forma de agrupamento em que cada elemento pode pertencer a mais de um grupo (cluster).

Clustering ou análise de cluster envolve a atribuição de pontos de dados a grupos de forma que os itens no mesmo grupo sejam o mais semelhantes possível, enquanto os itens de grupos diferentes sejam o mais diferentes possível. Os grupos são identificados por meio de medidas de similaridade. Essas medidas de similaridade incluem distância, conectividade e intensidade. Diferentes medidas de similaridade podem ser escolhidas com base nos dados ou na aplicação.

Comparação com o agrupamento rígido

No agrupamento não-difuso (também conhecido como agrupamento rígido, ou hard clustering), os dados são divididos em grupos distintos, onde cada ponto de dados só pode pertencer a exatamente um grupo. No agrupamento fuzzy, os pontos de dados podem pertencer a vários clusters. Por exemplo, uma maçã pode ser vermelha ou verde (agrupamento rígido), mas uma maçã também pode ser vermelha E verde (agrupamento suave). Neste exemplo, a maçã pode ser vermelha até certo ponto, assim como verde até certo ponto. Em vez de a maçã ser verde [verde = 1] ou vermelha [vermelho = 0], como acontece no agrupamento rígido, a maçã pode pertencer ao cluster verde [verde = 0,5] e ao cluster vermelho [vermelho = 0,5] no agrupamento fuzzy. Esses valores são normalizados entre 0 e 1; no entanto, eles não representam probabilidades, portanto, a soma dos dois valores não precisa resultar em 1.

Associação

Os graus de associação são atribuídos a cada um dos pontos de dados (tags). Eles indicam o grau de pertencimento dos pontos de dados a cada cluster. Assim, os pontos que estão na borda do cluster, com um grau de associação menor, podem "estar no cluster" em um grau menor do que os pontos que estão no seu centro.

Agrupamento difuso C-means (Fuzzy C-means clustering)

Um dos algoritmos de agrupamento difuso mais utilizados é o Fuzzy C-means clustering (FCM).

Histórico

O algoritmo de agrupamento difuso C-means (fuzzy C-means clustering - FCM) foi desenvolvido por J.C Dunn em 1973 e aprimorado por J.C Bezdek em 1981.

Descrição geral

O algoritmo de agrupamento difuso C-means é muito parecido com o algoritmo de agrupamento k-means:

• Escolher o número de clusters
• Atribuir coeficientes aleatoriamente para cada ponto de dados para estar no cluster.
  • Calcular o centroide para cada cluster
  • Para cada ponto de dados calcular o coeficiente para que esteja nos clusters.

Centroide

Qualquer ponto x tem um conjunto de coeficientes que dão o grau do k-ésimo cluster w_k(x). Com o fuzzy c-means, o centroide de um cluster será a média de todos os pontos ponderados pelo grau de pertencimento ao cluster, ou matematicamente:

$c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}},$

Onde m é o hiperparâmetro que controla quão difuso será o cluster. Quanto maior for, mais difuso será o cluster no final.

Algoritmo

O algoritmo FCM tenta particionar uma coleção finita de $n$ elementos $X=\{\mathbf {x} _{1},...,\mathbf {x} _{n}\}$ em uma coleção de c clusters difusos, respeitando algum critério determinado.

Dado um conjunto finito de dados, o algoritimo retorna uma lista de $c$ centros de cluster $C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}$ e uma matriz de partição

$W=w_{i,j}\in [0,1],\;i=1,...,n,\;j=1,...,c$, onde cada elemento, $w_{ij}$ , diz o grau que o elemento $\mathbf {x} _{i}$ pertence ao cluster $\mathbf {c} _{j}$.

O FCM visa minimizar uma função objetiva:

${\underset {C}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\sum _{j=1}^{c}w_{ij}^{m}\left|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|^{2},$

onde:

$w_{ij}={\frac {1}{\sum _{k=1}^{c}\left({\frac {\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|}{\left\|\mathbf {x} _{i}-\mathbf {c} _{k}\right\|}}\right)^{\frac {2}{m-1}}}}.$