# Método da silhueta

Silhueta refere-se a um método de interpretação e validação da consistência dentro de agrupamentos de dados. A técnica fornece uma representação gráfica concisa de quão bem cada objeto foi classificado. Foi proposta pelo estatístico belga Peter Rousseeuw em 1987.
O valor da silhueta é uma medida de quão similar um objeto é ao seu próprio cluster (coesão) em comparação com outros clusters (separação). A silhueta varia de -1 a +1, onde um valor alto indica que o objeto está bem ajustado ao seu próprio cluster e mal ajustado aos clusters vizinhos. Se a maioria dos objetos tem um valor alto, então a configuração de agrupamento é apropriada. Se muitos pontos têm um valor baixo ou negativo, então a configuração de agrupamento pode ter muitos ou poucos clusters.
A silhueta pode ser calculada com qualquer métrica de distância, como a distância euclidiana ou a geometria do táxi (distância de Manhattan).

## Preliminares

Dois conceitos importantes para realizar o cálculo do método são:

#### Distância intracluster

Essa métrica avalia quão similares são os pontos dentro de um cluster em comparação com outros clusters, isso é, expressa o quão coesão ou disperso é cluster. O diâmetro é uma maneira comum de representar a distância intracluster, sendo definido como a maior distância entre dois pontos dentro do mesmo cluster.
Existem muitas maneiras de defini-la:
* Pode ser a distância entre os pontos mais distantes dentro de um cluster.
* Pode ser a média de todas as distâncias entre pares de pontos de dados dentro do cluster.
* Pode ser a distância de cada ponto de dados do centroide do cluster.

#### Distância intercluster

Essa métrica avalia quão separados ou distintos são os clusters uns dos outros, isso é, refere-se à medida de distância ou dissimilaridade entre dois clusters distintos.
Existem muitas maneiras de defini-la:
* A distância mínima entre dois objetos pertencentes a clusters distintos (Single-linkage clustering).
* A distância máxima entre qualquer ponto de dados no primeiro cluster e qualquer ponto de dados no segundo cluster (Complete-linkage clustering)
* A distância média entre todos os objetos pertencentes a dois clusters distintos (Average linkage distance)
* A distância entre o centróide de dois clusters distintos (Centroid linkage distance)

## Definição

Assuma que os dados foram agrupados por qualquer técnica, como K-medoides ou k-means, em k clusters.
Para o ponto de dados $i\in C_{I}$ (ponto de dados i no cluster $C_{I}$), seja
    $a(i)={\frac {1}{|C_{I}|-1}}\sum _{j\in C_{I},i\neq j}d(i,j)$
a distância média entre i e todos os outros pontos de dados no mesmo cluster, onde $|C_{I}|$ é o número de pontos pertencentes ao cluster $C_{I}$, e d(i,j) é a distância entre os pontos de dados i e j no cluster $C_{I}$ (dividimos por $|C_{I}|-1$ porque não incluímos a distância d(i,i) na soma). Podemos interpretar a(i) como uma medida de quão bem i está atribuído ao seu cluster (quanto menor o valor, melhor a atribuição).
Definimos então a dissimilaridade média do ponto i para algum cluster $C_{J}$ como a média da distância de i para todos os pontos em $C_{J}$ (onde $C_{J}\neq C_{I}$).
Para cada ponto de dados $i\in C_{I}$, agora definimos
    $b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\sum _{j\in C_{J}}d(i,j)$
ara ser a menor média de distância de i para todos os pontos em qualquer outro cluster (ou seja, em qualquer cluster do qual i não é membro). O cluster com essa menor média de dissimilaridade é dito ser o "cluster vizinho" de i porque é o próximo melhor ajuste para o ponto i.
Agora definimos uma silhueta (valor) de um ponto de dados i
    $s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}$, se $|C_{I}|>1$
e
    $s(i)=0$, se $|C_{I}|=1$
O que também pode ser escrito como:
    $s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{se }}a(i)<b(i)\\0,&{\mbox{se }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{se }}a(i)>b(i)\\\end{cases}}$
Dado a definição acima fica claro que
    $-1\leq s(i)\leq 1$
Note que a(i) não é claramente definido para clusters com tamanho = 1, no qual caso definimos $s(i)=0$. Esta escolha é arbitrária, mas neutra no sentido de que está no ponto médio dos limites, -1 e 1.
Para s(i) ser próximo de 1, requeremos $a(i)\ll b(i)$. Como a(i) é uma medida de quão dissimilar i é do seu próprio cluster, um valor pequeno significa que está bem ajustado. Além disso, um grande b(i) implica que i está mal ajustado ao seu cluster vizinho. Assim, um s(i) próximo de 1 significa que os dados estão apropriadamente agrupados. Se s(i) está próximo de -1, então pela mesma lógica vemos que i seria mais apropriado se estivesse agrupado em seu cluster vizinho. Um s(i) próximo de zero significa que o dado está na fronteira de dois clusters naturais.
A média de s(i) sobre todos os pontos de um cluster é uma medida de quão agrupados estão todos os pontos no cluster. Assim, a média de s(i) sobre todos os dados do conjunto de dados inteiro é uma medida de quão apropriadamente os dados foram agrupados. Se houver muitos ou poucos clusters, como pode ocorrer quando uma escolha pobre de k é usada no algoritmo de agrupamento (por exemplo, k-means), alguns dos clusters exibirão tipicamente silhuetas muito mais estreitas do que o resto. Assim, gráficos de silhueta e médias podem ser usados para determinar o número natural de clusters dentro de um conjunto de dados. Pode-se também aumentar a probabilidade de a silhueta ser maximizada no número correto de clusters reescalando os dados usando pesos de características que são específicos do cluster.
Kaufman e outros introduziram o termo coeficiente de silhueta para o valor máximo da média de s(i) sobre todos os dados do conjunto de dados inteiro, ou seja,
    $SC=\max _{k}{\tilde {s}}\left(k\right),$
onde ${\tilde {s}}\left(k\right)$ representa a média s(i) sobre todos os dados do conjunto de dados inteiro para um número específico de clusters k.

## Silhueta simplificada e silhueta de medoides

Calcular o coeficiente de silhueta requer todas as distâncias entre pares ${\mathcal {O}}(N^{2})$, tornando essa avaliação muito mais custosa do que o agrupamento com k-means. Para um agrupamento com centros $\mu _{C_{I}}$ para cada cluster $C_{I}$, podemos usar a seguinte silhueta simplificada para cada ponto $i\in C_{I}$ em vez disso, que pode ser calculada usando apenas distâncias ${\mathcal {O}}(Nk)$:
    $a'(i)=d(i,\mu _{C_{I}})$ e $b'(i)=\min _{C_{J}\neq C_{I}}d(i,\mu _{C_{J}})$,
o que tem o benefício adicional de que $a'(i)$ está sempre definido, então definimos de acordo a silhueta simplificada e o coeficiente de silhueta simplificado
    $s'(i)={\frac {b'(i)-a'(i)}{\max\{a'(i),b'(i)\}}}$
    $SC'=\max _{k}{\frac {1}{N}}\sum _{i}s'\left(i\right)$.
Se os centros dos clusters são medoides (como no agrupamento k-medoids) em vez de médias aritméticas (como no agrupamento com k-means), isso também é chamado de silhueta baseada em medoides ou silhueta de medoides.
Se cada objeto é atribuído ao medoide mais próximo (como no agrupamento k-medoids), sabemos que $a'(i)\leq b'(i)$, e portanto $s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}$.

## Agrupamento por silhueta

Em vez de usar a silhueta média para avaliar um agrupamento obtido de, por exemplo, k-medoids ou k-means, podemos tentar encontrar diretamente uma solução que maximize a Silhueta. Não temos uma solução de forma fechada para maximizar isso, mas geralmente será melhor atribuir pontos ao cluster mais próximo, como feito por esses métodos. Van der Laan e outros propuseram adaptar o algoritmo padrão para k-medoides, PAM, para esse propósito e chamam esse algoritmo de PAMSIL:
* Escolha medoides iniciais usando PAM.
* Calcule a silhueta média dessa solução inicial.
* Para cada par de um medoide m e um não medoide x
** Troque m e x
** Calcule a silhueta média da solução resultante
** Lembre-se da melhor troca
** Desfaça a troca de m e x para a próxima iteração.
* Realize a melhor troca e retorne ao passo 3, caso contrário, pare se nenhuma melhoria for encontrada.
O loop no passo 3 é executado para O(Nk) pares, e envolve calcular a silhueta em O(N$^2$), portanto, esse algoritmo precisa de O(N$^3$ki) tempo, onde i é o número de iterações.
Como essa é uma operação bastante cara, os autores propõem usar também a silhueta baseada em medoides, e chamam o algoritmo resultante de PAMMEDSIL. Ele precisa de O(N$^2$k$^2$i) de tempo.
Já Batool e outros propõem um algoritmo semelhante sob o nome OSil, e propõem uma estratégia de amostragem semelhante à CLARA para conjuntos de dados maiores, que resolve o problema apenas para uma subamostra.
Adotando melhorias recentes no algoritmo PAM, o FastMSC reduz o tempo de execução usando a silhueta de medoides para apenas O(N$^2$i).

## Implementações

* No Python, a implementação pode ser encontrada na biblioteca scikit-learn, dentro do pacote 'sklearn.base', mais especificamente no módulo 'sklearn.metrics.silhouette_score', que pode ser encontrado com mais detalhes aqui.
* Abaixo um exemplo desse módulo:
from sklearn import metrics
from sklearn.metrics import pairwise_distances
from sklearn import datasets
import numpy as np
from sklearn.cluster import KMeans
X, y = datasets.load_iris(return_X_y=True)
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.silhouette_score(X, labels, metric='euclidean')
* No R também existe uma implementação já criada. Ela pode ser encontrada importando o pacote 'bios2mds', para mais detalhes a documentação se encontra aqui.
* Abaixo, um exemplo do método:
library(clusterSim)
data(gpcr)
active <- gpcr$dif$sapiens.sapiens
mds <- mmds(active)
sil.score1 <- sil.score(mds$coord, nb.clus = c(2:10), nb.run = 100, iter.max = 100)
barplot(sil.score1)