PROFILPELAJAR.COM

O problema $k$ -medoids é um problema de agrupamento semelhante ao $k$ -means. O nome foi cunhado por Leonard Kaufman e Peter J. Rousseeuw no seu algoritmo PAM (Partitioning Around Medoids). ^[1] Ambos os algoritmos $k$ -means e $k$ -medoids são particionais (quebrando o conjunto de dados em grupos) e tentam minimizar a distância entre os pontos rotulados como pertencentes a um cluster e um ponto designado como o centro desse cluster. Em contraste com o algoritmo $k$ -means, $k$ -medoids escolhe pontos de dados reais como centros ( medoids ou exemplares) e, assim, permite maior interpretabilidade dos centros de cluster do que o $k$ -means, onde o centro de um cluster não é necessariamente um dos pontos de dados de entrada (é a média entre os pontos no cluster). Além disso, $k$ -medoides podem ser usados com medidas de dissimilaridade arbitrárias, enquanto $k$ -means geralmente requer distância euclidiana para soluções eficientes. Como $k$ -medoids minimiza uma soma de dissimilaridades aos pares em vez de uma soma de distâncias euclidianas ao quadrado, é mais robusto a ruído e outliers (anomalias) do que $k$ -means .

k-medoides é uma técnica clássica de particionamento para agrupamento de dados que divide o conjunto de dados de n objetos em k clusters, onde o número k de clusters, a priori, assume-se conhecer ( o que implica que o programador deve especificar k antes da execução de um algorítmos k-medoides). O quão bom é o valor de k pode ser obtido com métodos como o método silhouete

O medoide de um cluster é definido como o objeto no cluster cuja dissimilaridade média para todos os objetos no cluster é mínima, ou seja, é um ponto localizado mais centralmente no cluster.

Algoritmos

Em geral, o problema $k$ -medoids é NP-difícil de resolver exatamente. Como tal, existem muitas soluções heurísticas.

Particionamento em Medoides (PAM)

O PAM usa uma busca gulosa que pode não encontrar a solução ótima, mas é mais rápida que a busca exaustiva. Funciona da seguinte forma:

(CONSTRUIR) Inicializar: selecione avidamente $k$ dos $n$ pontos de dados como os medoids para minimizar o custo
Associe cada ponto de dados ao medoid mais próximo.
(SWAP) Enquanto o custo da configuração diminui:
1. Para cada medoid m, e para cada ponto de dados não medoid o :
  1. Considere a troca de $m$ e $o$ e calcule a mudança de custo
  2. Se a mudança de custo for a melhor atual, lembre-se desta combinação m e o
2. Faça a melhor troca de $m_{\text{best}}$ e $o_{\text{best}}$ , se diminui a função de custo. Caso contrário, o algoritmo termina.

A complexidade do tempo de execução do algoritmo PAM original por iteração de (3) é $O(k(n-k)^{2})$ , computando apenas a mudança no custo. Uma implementação ingênua recalculando toda a função de custo toda vez estará em $O(n^{2}k^{2})$ . Este tempo de execução pode ser ainda mais reduzido para $O(n^{2})$ , dividindo a mudança de custo em três partes de forma que os cálculos possam ser compartilhados ou evitados (FastPAM). O tempo de execução pode ser ainda mais reduzido executando swaps (FasterPAM), ^[2] momento em que uma inicialização aleatória se torna uma alternativa viável para BUILD.

Otimização alternada

Algoritmos diferentes do PAM também têm sido sugeridos na literatura, incluindo o seguinte método de iteração de Voronoi conhecido como heurística "Alternativa" na literatura, pois alterna entre duas etapas de otimização: ^[3] ^[4] ^[5]

Selecione medoids iniciais aleatoriamente
Iterar enquanto o custo diminui:
1. Em cada cluster, faça o ponto que minimiza a soma das distâncias dentro do cluster o medoid
2. Reatribua cada ponto ao cluster definido pelo medoid mais próximo determinado na etapa anterior

A iteração Voronoi k -means-style tende a produzir resultados piores e exibir "comportamento errático". ^[6] ^:957Como não permite reatribuir pontos a outros clusters durante a atualização, ele explora apenas um espaço de pesquisa menor. Pode-se mostrar que mesmo em casos simples esta heurística encontra soluções inferiores que os métodos baseados em swap podem resolver.

Agrupamento hierárquico

Várias variantes de agrupamento hierárquico com uma "ligação medoide" foram propostas. O critério de ligação Minimum Sum ^[7] usa diretamente o objetivo de medoids, mas a ligação Minimum Sum Growth mostrou produzir melhores resultados (semelhante a como Ward linkage usa o aumento no erro quadrado). Abordagens anteriores simplesmente usavam a distância dos medoids de cluster dos medoids anteriores como medida de ligação, ^[8] ^[9] mas que tende a resultar em soluções piores, pois a distância de dois medoids não garante que exista um bom medoid para a combinação . Essas abordagens têm uma complexidade de tempo de execução de $O(n^{3})$ , e quando o dendrograma é cortado em um determinado número de clusters k, os resultados normalmente serão piores do que os resultados encontrados pelo PAM. ^[7] Portanto, esses métodos são principalmente de interesse quando uma estrutura de árvore hierárquica é desejada.

Outros algoritmos

Outros algoritmos aproximados, como CLARA e CLARANS, trocam qualidade por tempo de execução. CLARA aplica PAM em várias subamostras, mantendo o melhor resultado. O CLARANS trabalha com todo o conjunto de dados, mas explora apenas um subconjunto das possíveis trocas de medoides e não medoides usando amostragem. BanditPAM usa o conceito de bandidos multi-armados para escolher trocas de candidatos em vez de amostragem uniforme como em CLARANS. ^[10]

Programas

ELKI inclui várias variantes de k -medoid, incluindo k -medoids de iteração de Voronoi, o algoritmo PAM original, melhorias de Reynolds e os algoritmos O(n²) FastPAM e FasterPAM, CLARA, CLARANS, FastCLARA e FastCLARANS.
Julia contém uma implementação k -medoid do algoritmo de estilo k-means (rápido, mas com qualidade de resultado muito pior) no pacote JuliaStats/Clustering.jl .
O KNIME inclui uma implementação k -medoid que suporta uma variedade de medidas eficientes de distância de matriz, bem como várias implementações k -means nativas (e integradas de terceiros)
Python contém FasterPAM e outras variantes no pacote " kmedoids ", implementações adicionais podem ser encontradas em muitos outros pacotes
R contém PAM no pacote " cluster ", incluindo as melhorias FasterPAM por meio das opções variant = "faster" e medoids = "random" . Também existe um pacote "fastkmedoids".
O RapidMiner tem um operador chamado KMedoids, mas não implementa nenhum dos algoritmos KMedoids acima. Em vez disso, é uma variante k-means, que substitui a média pelo ponto de dados mais próximo (que não é o medoid), que combina as desvantagens do k-means (limitado a dados coordenados) com o custo adicional de encontrar o ponto mais próximo ao meio.
Rust tem uma caixa " kmedoids " que também inclui a variante FasterPAM.
O MATLAB implementa PAM, CLARA e dois outros algoritmos para resolver o problema de agrupamento k -medoid.

Referências

↑ Kaufman, Leonard; Rousseeuw, Peter J. (8 de março de 1990), «Partitioning Around Medoids (Program PAM)», ISBN 978-0-470-31680-1, Hoboken, NJ, USA: John Wiley & Sons, Inc., Wiley Series in Probability and Statistics (em inglês): 68–125, doi:10.1002/9780470316801.ch2, consultado em 13 de junho de 2021
↑ Schubert, Erich; Rousseeuw, Peter J. (2021). «Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms». Information Systems (em inglês). 101. 101804 páginas. arXiv:2008.05171. doi:10.1016/j.is.2021.101804
↑ Maranzana, F. E. (1963). «On the location of supply points to minimize transportation costs». IBM Systems Journal. 2 (2): 129–135. doi:10.1147/sj.22.0129
↑ T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469.
↑ Park, Hae-Sang; Jun, Chi-Hyuck (2009). «A simple and fast algorithm for K-medoids clustering». Expert Systems with Applications (em inglês). 36 (2): 3336–3341. doi:10.1016/j.eswa.2008.01.039
↑ Teitz, Michael B.; Bart, Polly (1 de outubro de 1968). «Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph». Operations Research. 16 (5): 955–961. ISSN 0030-364X. doi:10.1287/opre.16.5.955
↑ ^a ^b Schubert, Erich (2021). HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations (PDF). LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany. pp. 191–204 – via CEUR-WS
↑ Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures. 2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS). pp. 400–403. doi:10.1109/SCIS-ISIS.2016.0091
↑ Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data (PDF). Graphics Interface. Graphics Interface (em inglês). doi:10.20380/gi2016.14. Consultado em 4 de novembro de 2022
↑ Tiwari, Mo; Zhang, Martin J.; Mayclin, James; Thrun, Sebastian; Piech, Chris; Shomorony, Ilan (2020). «BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits». Advances in Neural Information Processing Systems (em inglês). 33