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:

1. Pode ser a distância entre os pontos mais distantes dentro de um cluster.
2. Pode ser a média de todas as distâncias entre pares de pontos de dados dentro do cluster.
3. 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:

1. A distância mínima entre dois objetos pertencentes a clusters distintos (Single-linkage clustering).
2. A distância máxima entre qualquer ponto de dados no primeiro cluster e qualquer ponto de dados no segundo cluster (Complete-linkage clustering)
3. A distância média entre todos os objetos pertencentes a dois clusters distintos (Average linkage distance)
4. A distância entre o centróide de dois clusters distintos (Centroid linkage distance)

Definição

Um gráfico mostrando as pontuações de silhueta de três tipos de animais do conjunto de dados do Zoológico conforme renderizado pela suíte de mineração de dados Orange. Na parte inferior do gráfico, a silhueta identifica golfinhos e marsuínos como outliers no grupo de mamíferos.

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:

1. Escolha medoides iniciais usando PAM.
2. Calcule a silhueta média dessa solução inicial.
3. Para cada par de um medoide m e um não medoide x
   1. Troque m e x
   2. Calcule a silhueta média da solução resultante
   3. Lembre-se da melhor troca
   4. Desfaça a troca de m e x para a próxima iteração.
4. 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²), portanto, esse algoritmo precisa de O(N³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²k²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²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)

Ver também

• Clustering
• Davies–Bouldin index
• Dunn index

Ligações externas

• «Agglomerative Hierarchical Clustering». Consultado em 19 de dezembro de 2022  (em inglês)
• «Dunn index and DB index – Cluster Validity indices». Consultado em 23 de dezembro de 2022  (em inglês)
• «What are some challenges and limitations of cluster analysis using Davies-Bouldin index?». Consultado em 23 de dezembro de 2022  (em inglês)