K-medoides

O problema Predefinição:Math -medoids é um problema de agrupamento semelhante ao [[K-means|Predefinição:Math -means]]. O nome foi cunhado por Leonard Kaufman e Peter J. Rousseeuw no seu algoritmo PAM (Partitioning Around Medoids). Ambos os algoritmos Predefinição:Math -means e Predefinição:Math -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 Predefinição:Math -means, Predefinição:Math -medoids escolhe pontos de dados reais como centros ( medoids ou exemplares) e, assim, permite maior interpretabilidade dos centros de cluster do que o Predefinição:Math -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, Predefinição:Math -medoides podem ser usados com medidas de dissimilaridade arbitrárias, enquanto Predefinição:Math -means geralmente requer distância euclidiana para soluções eficientes. Como Predefinição:Math -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|Predefinição:Math -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

PAM escolhendo medoids iniciais, então iterando para convergência para k=3 clusters, visualizados com ELKI .

Em geral, o problema Predefinição:Math -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:

1. (CONSTRUIR) Inicializar: selecione avidamente Predefinição:Mvar dos Predefinição:Mvar pontos de dados como os medoids para minimizar o custo
2. Associe cada ponto de dados ao medoid mais próximo.
3. (SWAP) Enquanto o custo da configuração diminui:
   1. Para cada medoid Predefinição:Mvar, e para cada ponto de dados não medoid Predefinição:Mvar :
      1. Considere a troca de Predefinição:Mvar e Predefinição:Mvar 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), 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:

1. Selecione medoids iniciais aleatoriamente
2. 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". Predefinição:RpComo 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 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, 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. 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.

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.