Mostrar código-fonte de 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 [[Clustering|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. <ref>{{Citar web |url=http://reference.wolfram.com/applications/fuzzylogic/Manual/12.html |titulo=Fuzzy Clustering |acessodata=2016-04-26 |website=reference.wolfram.com}}</ref>

== 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<ref>{{Cite journal|last=Dunn|first=J. C.|date=1973-01-01|title=A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters|journal=Journal of Cybernetics|volume=3|issue=3|pages=32–57|doi=10.1080/01969727308546046|issn=0022-0280}}</ref> e aprimorado por J.C Bezdek em 1981.<ref>Bezdek, James C. (1981). ''Pattern Recognition with Fuzzy Objective Function Algorithms''. {{ISBN|0-306-40671-3}}.</ref>

=== Descrição geral ===
O algoritmo de agrupamento difuso C-means é muito parecido com o algoritmo de [[k-means|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''<sub>''k''</sub>(''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: 

<math> c_k =  {{\sum_x {w_k(x)} ^ {m} x} \over {\sum_x {w_k(x)} ^ {m}}},
</math>

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 <math>n</math> elementos <math>X=\{ \mathbf{x}_1, . . . ,\mathbf{x}_n \}</math> 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 <math>c</math> centros de cluster <math>C = \{ \mathbf{c}_1, . . . , \mathbf{c}_c \}</math> e uma matriz de partição 

<math>W = w_{i,j} \in[0,1],\; i = 1, . . . , n, \; j = 1, . . . , c</math>, 
onde cada elemento, <math>w_{ij}</math> , diz o grau que o elemento <math>\mathbf{x}_i</math> pertence ao cluster <math>\mathbf{c}_j</math>.

O FCM visa minimizar uma função objetiva:

:<math>\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, </math>

onde:

:<math>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}}}.</math>


{{Referências}}
[[Categoria:Algoritmos de análise de cluster]]