Método da silhueta

Predefinição:Short description 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 Predefinição:Math clusters.

Para o ponto de dados $i\in C_I$ (ponto de dados Predefinição:Math no cluster $C_I$), seja

$a(i)=\frac{1}{|C_I|-1}\sum _{j\in C_I,i\ne j}d(i,j)$

a distância média entre Predefinição:Math e todos os outros pontos de dados no mesmo cluster, onde $|C_I|$ é o número de pontos pertencentes ao cluster $C_I$, e Predefinição:Math é a distância entre os pontos de dados Predefinição:Math e Predefinição:Math no cluster $C_I$ (dividimos por $|C_I|-1$ porque não incluímos a distância Predefinição:Math na soma). Podemos interpretar Predefinição:Math como uma medida de quão bem Predefinição:Math está atribuído ao seu cluster (quanto menor o valor, melhor a atribuição).

Definimos então a dissimilaridade média do ponto Predefinição:Math para algum cluster $C_J$ como a média da distância de Predefinição:Math para todos os pontos em $C_J$ (onde $C_J\ne C_I$).

Para cada ponto de dados $i\in C_I$, agora definimos

$b(i)=\underset{J\ne I}{\min }\frac{1}{|C_J|}\sum _{j\in C_J}d(i,j)$

ara ser a menor média de distância de Predefinição:Math para todos os pontos em qualquer outro cluster (ou seja, em qualquer cluster do qual Predefinição:Math não é membro). O cluster com essa menor média de dissimilaridade é dito ser o "cluster vizinho" de Predefinição:Math porque é o próximo melhor ajuste para o ponto Predefinição:Math.

Agora definimos uma silhueta (valor) de um ponto de dados Predefinição:Math

$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{array}{cc}1-a(i)/b(i),& \text{se }a(i)<b(i)\\ 0,& \text{se }a(i)=b(i)\\ b(i)/a(i)-1,& \text{se }a(i)>b(i)\end{array}$

Dado a definição acima fica claro que

$-1\le s(i)\le 1$

Note que Predefinição:Math 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 Predefinição:Math ser próximo de 1, requeremos $a(i)\ll b(i)$. Como Predefinição:Math é uma medida de quão dissimilar Predefinição:Math é do seu próprio cluster, um valor pequeno significa que está bem ajustado. Além disso, um grande Predefinição:Math implica que Predefinição:Math está mal ajustado ao seu cluster vizinho. Assim, um Predefinição:Math próximo de 1 significa que os dados estão apropriadamente agrupados. Se Predefinição:Math está próximo de -1, então pela mesma lógica vemos que Predefinição:Math seria mais apropriado se estivesse agrupado em seu cluster vizinho. Um Predefinição:Math próximo de zero significa que o dado está na fronteira de dois clusters naturais.

A média de Predefinição:Math 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 Predefinição:Math 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 Predefinição:Math é 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 Predefinição:Math sobre todos os dados do conjunto de dados inteiro, ou seja,

$SC=\underset{k}{\max }\tilde{s}\left(k\right),$

onde $\tilde{s}\left(k\right)$ representa a média Predefinição:Math sobre todos os dados do conjunto de dados inteiro para um número específico de clusters Predefinição:Math.

Silhueta simplificada e silhueta de medoides

Calcular o coeficiente de silhueta requer todas as distâncias entre pares $𝒪(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 $𝒪(Nk)$:

$a^{\prime }(i)=d(i,{\mu }_{C_I})$ e $b^{\prime }(i)=\underset{C_J\ne C_I}{\min }d(i,{\mu }_{C_J})$,

o que tem o benefício adicional de que $a^{\prime }(i)$ está sempre definido, então definimos de acordo a silhueta simplificada e o coeficiente de silhueta simplificado

$s^{\prime }(i)=\frac{b^{\prime }(i)-a^{\prime }(i)}{\max \{a^{\prime }(i),b^{\prime }(i)\}}$

$S{C}^{\prime }=\underset{k}{\max }\frac{1}{N}\sum _i{s}^{\prime }\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^{\prime }(i)\le b^{\prime }(i)$, e portanto $s^{\prime }(i)=\frac{b^{\prime }(i)-a^{\prime }(i)}{b^{\prime }(i)}=1-\frac{a^{\prime }(i)}{b^{\prime }(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 Predefinição:Math e um não medoide Predefinição:Math
   1. Troque Predefinição:Math e Predefinição:Math
   2. Calcule a silhueta média da solução resultante
   3. Lembre-se da melhor troca
   4. Desfaça a troca de Predefinição:Math e Predefinição:Math 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 Predefinição:Math pares, e envolve calcular a silhueta em Predefinição:Math, portanto, esse algoritmo precisa de Predefinição:Math tempo, onde Predefinição:Math é 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 Predefinição:Math 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 Predefinição:Math.

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

• Predefinição:Cite web Predefinição:En
• Predefinição:Cite web Predefinição:En
• Predefinição:Cite web Predefinição:En