Método da silhueta: diferenças entre revisões
nova página: {{Short description|Quality measure in cluster analysis}} '''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.<ref name="Rousseeuw 1987">{{Cite journal | doi = 10.1016/0377-0427(87)90125-7 | author = Peter J. Rousseeuw | author-link = Peter J. Rousseeuw | title = Silhouettes: a Graphical Aid to... Etiquetas: Expressão problemática Inserção de predefinição obsoleta Editor Visual: Trocado |
(Sem diferenças)
|
Revisão das 22h18min de 17 de novembro de 2023
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.[1] Foi proposta pelo estatístico belga Peter Rousseeuw in 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.
Definição
Assuma que os dados foram agrupados por qualquer técnica, como K-medoides or k-means, em k clusters.
Para o ponto de dados (ponto de dados i no cluster ), seja
a distância média entre i e todos os outros pontos de dados no mesmo cluster, onde é o número de pontos pertencentes ao cluster , e d(i,j) é a distância entre os pontos de dados i e j no cluster (dividimos por 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 como a média da distância de i para todos os pontos em (onde ).
Para cada ponto de dados , agora definimos
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
- , if
and
- , if
O que também pode ser escrito como:
Dado a definição acima fica claro que
Note que a(i) não é claramente definido para clusters com tamanho = 1, no qual caso definimo . Esta escolha é arbitrária, mas neutra no sentido de que está no ponto médio dos limites, -1 and 1.[1]
Para s(i) ser próximo de 1, requeremos . 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 wseria 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.[2]
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, [3] ou seja,
onde 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 , tornando essa avaliação muito mais custosa do que o agrupamento com k-means. Para um agrupamento com centros para cada cluster , podemos usar a seguinte Silhueta Simplificada para cada ponto em vez disso, que pode ser calculada usando apenas distâncias :
- and ,
o que tem o benefício adicional de que está sempre definido, então definimos de acordo a silhueta simplificada e o coeficiente de silhueta simplificado [4]
- .
Se os centros dos clusters são medoides (como no agrupamento k-medoids) em vez de médias aritméticas (como no agrupamento k-means), isso também é chamado de silhueta baseada em medoides ou silhueta de medoides.[5] or medoid silhouette.[6]
Se cada objeto é atribuído ao medoide mais próximo (como no agrupamento k-medoids), sabemos que , e portanto .[6]
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 [5] 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(N2), portanto, esse algoritmo precisa de O(N3ki) 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.[5] Ele precisa de O(N2k2i) de tempo.
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.[7]
Adotando melhorias recentes no algoritmo PAM, o FastMSC reduz o tempo de execução usando a silhueta de medoides para apenas O(N2i).[6]
See also
- Cluster analysis
- Davies–Bouldin index
- Calinski-Harabasz index
- Dunn index
- Determining the number of clusters in a data set
References
- ↑ a b Peter J. Rousseeuw (1987). «Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis». Computational and Applied Mathematics. 20: 53–65. doi:10.1016/0377-0427(87)90125-7
- ↑ R.C. de Amorim, C. Hennig (2015). «Recovering the number of clusters in data sets with noise features using feature rescaling factors». Information Sciences. 324: 126–145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039
- ↑ Leonard Kaufman; Peter J. Rousseeuw (1990). Finding groups in data : An introduction to cluster analysis. Hoboken, NJ: Wiley-Interscience. p. 87. ISBN 9780471878766. doi:10.1002/9780470316801
- ↑ Hruschka, E.R.; de Castro, L.N.; Campello, R.J.G.B. (2004). Evolutionary Algorithms for Clustering Gene-Expression Data. Fourth IEEE International Conference on Data Mining (ICDM'04). IEEE. pp. 403–406. doi:10.1109/ICDM.2004.10073
- ↑ a b c Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003). «A new partitioning around medoids algorithm». Journal of Statistical Computation and Simulation (em inglês). 73 (8): 575–584. ISSN 0094-9655. doi:10.1080/0094965031000136012
- ↑ a b c Lenssen, Lars; Schubert, Erich (2022). Clustering by Direct Optimization of the Medoid Silhouette. International Conference on Similarity Search and Applications (em inglês). pp. 190–204. arXiv:2209.12553. doi:10.1007/978-3-031-17849-8_15. Consultado em 20 de outubro de 2022
- ↑ Batool, Fatima; Hennig, Christian (2021). «Clustering with the Average Silhouette Width». Computational Statistics & Data Analysis (em inglês). 158. 107190 páginas. arXiv:1910.11339. doi:10.1016/j.csda.2021.107190