Algoritmo CURE - CURE algorithm

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

CURE (Clustering Using REpresentatives) é um algoritmo de agrupamento de dados eficiente para grandes bancos de dados . Em comparação com o agrupamento K-means , é mais robusto para outliers e capaz de identificar clusters com formas não esféricas e variações de tamanho.

Desvantagens dos algoritmos tradicionais

O popular algoritmo de agrupamento K-means minimiza a soma do critério de erros quadrados :

${\ displaystyle E = \ sum _ {i = 1} ^ {k} \ sum _ {p \ in C_ {i}} (p-m_ {i}) ^ {2},}$

Dadas as grandes diferenças em tamanhos ou geometrias de diferentes clusters, o método do erro quadrado poderia dividir os grandes clusters para minimizar o erro quadrado, o que nem sempre é correto. Além disso, com algoritmos de agrupamento hierárquico, esses problemas existem, pois nenhuma das medidas de distância entre os clusters ( ) tende a funcionar com diferentes formatos de cluster. Além disso, o tempo de execução é alto quando n é grande. ${\ displaystyle d_ {min}, d_ {mean}}$

O problema com o algoritmo BIRCH é que, uma vez que os clusters são gerados após a etapa 3, ele usa os centróides dos clusters e atribui cada ponto de dados ao cluster com o centróide mais próximo. Usar apenas o centróide para redistribuir os dados tem problemas quando os clusters não têm tamanhos e formas uniformes.

Algoritmo de agrupamento CURE

Para evitar os problemas com clusters de tamanhos ou formatos não uniformes, o CURE emprega um algoritmo de agrupamento hierárquico que adota um meio-termo entre o centróide baseado e todos os pontos extremos. No CURE, um número constante c de pontos bem dispersos de um cluster são escolhidos e eles são reduzidos em direção ao centroide do cluster por uma fração α. Os pontos espalhados após a redução são usados ​​como representantes do cluster. Os clusters com o par mais próximo de representantes são os clusters que são mesclados em cada etapa do algoritmo de clustering hierárquico do CURE. Isso permite que o CURE identifique corretamente os clusters e o torna menos sensível a outliers.

O tempo de execução é O ( n ² log n ), o que o torna bastante caro, e a complexidade do espaço é O ( n ).

O algoritmo não pode ser aplicado diretamente a grandes bancos de dados devido à alta complexidade do tempo de execução. Os aprimoramentos atendem a esse requisito.

• Amostragem aleatória : a amostragem aleatória oferece suporte a grandes conjuntos de dados. Geralmente, a amostra aleatória cabe na memória principal . A amostragem aleatória envolve uma troca entre precisão e eficiência.
• Particionamento: A ideia básica é particionar o espaço de amostra em p partições. Cada partição contém n / p elementos. A primeira passagem agrupa parcialmente cada partição até que o número final de clusters seja reduzido a n / pq para alguma constante q ≥ 1. Uma segunda passagem de agrupamento em n / q agrupa parcialmente partições. Para a segunda passagem, apenas os pontos representativos são armazenados, pois o procedimento de mesclagem requer apenas pontos representativos de clusters anteriores antes de computar os pontos representativos para o cluster mesclado. O particionamento da entrada reduz os tempos de execução.
• Rotulando dados no disco: dados apenas pontos representativos para k clusters, os pontos de dados restantes também são atribuídos aos clusters. Para isso, uma fração de pontos representativos selecionados aleatoriamente para cada um dos k clusters é escolhida e o ponto de dados é atribuído ao cluster que contém o ponto representativo mais próximo a ele.

Pseudo-código

CURA (nº de pontos, k )

Entrada: Um conjunto de pontos S

Resultado: k clusters

• Para cada cluster u (cada ponto de entrada), em u.mean e u.rep armazene a média dos pontos no cluster e um conjunto de c pontos representativos do cluster (inicialmente c = 1, pois cada cluster tem um ponto de dados) . Também u.closest armazena o cluster mais próximo de u.
• Todos os pontos de entrada são inseridos em uma árvore kd T
• Trate cada ponto de entrada como um cluster separado, calcule u.closest para cada u e, em seguida, insira cada cluster no heap Q. (os clusters são organizados em ordem crescente de distâncias entre u e u.closest).
• Enquanto tamanho (Q)> k
• Remova o elemento superior de Q (digamos u) e mescle-o com seu cluster mais próximo u.mais próximo (digamos v) e calcule os novos pontos representativos para o cluster mesclado w.
• Remova uev de T e Q.
• Para todos os clusters x em Q, atualize x.closest e realoque x
• insira w em Q
• repetir

Disponibilidade

• A biblioteca de código aberto pyclustering inclui uma implementação Python e C ++ do algoritmo CURE.

Veja também

• agrupamento k-means
• Algoritmo BFR

Referências

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: An Efficient Clustering Algorithm for Large Databases" (PDF) . Sistemas de informação . 26 (1): 35–58. doi : 10.1016 / S0306-4379 (01) 00008-4 .
• Kogan, Jacob; Nicholas, Charles K .; Teboulle, M. (2006). Agrupando dados multidimensionais: avanços recentes no agrupamento . Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Reconhecimento de padrões . Academic Press. pp. 572–574. ISBN 978-0-12-369531-4.