Algoritmo CURE - CURE algorithm

Parte di una serie su
Apprendimento automatico e data mining
I problemi Classificazione Raggruppamento Regressione Rilevamento anomalie Pulizia dei dati AutoML Regole dell'associazione Insegnamento rafforzativo Previsione strutturata Ingegneria delle caratteristiche Apprendimento delle funzionalità Apprendimento online Apprendimento semi-supervisionato Apprendimento non supervisionato Imparare a classificarsi Induzione grammaticale
Apprendimento supervisionato ( classificazione  • regressione ) Alberi decisionali Ensemble insaccamento potenziamento foresta casuale k -NN Regressione lineare Ingenuo Bayes Reti neurali artificiali Regressione logistica Perceptron Macchina vettoriale di pertinenza (RVM) Supporta la macchina vettoriale (SVM)
Raggruppamento BETULLA CURA gerarchico k -significa Aspettativa-massimizzazione (EM) DBSCAN OTTICA spostamento medio
Riduzione della dimensionalità Analisi fattoriale CCA ICA LDA NMF PCA PGD t-SNE
Previsione strutturata Modelli grafici Rete di Bayes Campo casuale condizionale Markov . nascosto
Rilevamento anomalie k -NN Fattore outlier locale
Rete neurale artificiale codificatore automatico Calcolo cognitivo Apprendimento profondo DeepDream Perceptron multistrato RNN LSTM GRUPPO ESN Macchina Boltzmann con restrizioni GAN SOM Rete neurale convoluzionale U-Net Trasformatore Spiking rete neurale Memtransistor RAM elettrochimica (ECRAM)
Insegnamento rafforzativo Q-learning SARSA Differenza temporale (TD)
Teoria Bias-varianza tradeoff Teoria dell'apprendimento computazionale Minimizzazione empirica del rischio Occam apprendimento Apprendimento PAC Apprendimento statistico teoria VC
Luoghi di apprendimento automatico NeurIPS ICML ML JMLR ArXiv:cs.LG
Articoli Correlati Glossario dell'intelligenza artificiale Elenco dei set di dati per la ricerca sull'apprendimento automatico Cenni sull'apprendimento automatico
v T e

CURE (Clustering Using REpresentatives) è un efficiente algoritmo di clustering di dati per database di grandi dimensioni . Rispetto al clustering K-means è più robusto rispetto ai valori anomali e in grado di identificare i cluster con forme non sferiche e variazioni dimensionali.

Svantaggi degli algoritmi tradizionali

Il popolare algoritmo di clustering K-means riduce al minimo il criterio della somma degli errori al quadrato :

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

Date le grandi differenze nelle dimensioni o nelle geometrie dei diversi cluster, il metodo dell'errore quadrato potrebbe dividere i cluster di grandi dimensioni per ridurre al minimo l'errore quadrato, che non è sempre corretto. Inoltre, con gli algoritmi di clustering gerarchico questi problemi esistono poiché nessuna delle misure di distanza tra i cluster ( ) tende a funzionare con diverse forme di cluster. Anche il tempo di esecuzione è alto quando n è grande. ${\displaystyle d_{min},d_{media}}$

Il problema con l' algoritmo BIRCH è che una volta generati i cluster dopo il passaggio 3, utilizza i centroidi dei cluster e assegna ciascun punto dati al cluster con il centroide più vicino. L'uso del solo centroide per ridistribuire i dati presenta problemi quando i cluster mancano di dimensioni e forme uniformi.

Algoritmo di clustering CURE

Per evitare i problemi con cluster di dimensioni o forma non uniformi, CURE utilizza un algoritmo di clustering gerarchico che adotta una via di mezzo tra il centroide basato e tutti i punti estremi. In CURE, viene scelto un numero costante c di punti ben dispersi di un cluster e vengono ridotti verso il centroide del cluster di una frazione α. I punti sparsi dopo il restringimento sono usati come rappresentanti del cluster. I cluster con la coppia di rappresentanti più vicina sono i cluster che vengono uniti in ogni fase dell'algoritmo di clustering gerarchico di CURE. Ciò consente a CURE di identificare correttamente i cluster e lo rende meno sensibile agli outlier.

Il tempo di esecuzione è O( n ² log n ), il che lo rende piuttosto costoso, e la complessità dello spazio è O( n ).

L'algoritmo non può essere applicato direttamente a database di grandi dimensioni a causa dell'elevata complessità di runtime. I miglioramenti soddisfano questo requisito.

• Campionamento casuale : il campionamento casuale supporta set di dati di grandi dimensioni. Generalmente il campione casuale si adatta alla memoria principale . Il campionamento casuale comporta un compromesso tra accuratezza ed efficienza.
• Partizionamento: l'idea di base è quella di partizionare lo spazio campione in p partizioni. Ogni partizione contiene n/p elementi. Il primo passaggio raggruppa parzialmente ogni partizione finché il numero finale di cluster si riduce a n/pq per alcune costanti q ≥ 1. Un secondo passaggio di clustering su n/q raggruppa parzialmente le partizioni. Per il secondo passaggio vengono memorizzati solo i punti rappresentativi poiché la procedura di fusione richiede solo punti rappresentativi dei cluster precedenti prima di calcolare i punti rappresentativi per il cluster unito. Il partizionamento dell'input riduce i tempi di esecuzione.
• Etichettatura dei dati su disco: dati solo i punti rappresentativi per k cluster, ai cluster vengono assegnati anche i punti dati rimanenti. Per questo viene scelta una frazione di punti rappresentativi selezionati casualmente per ciascuno dei k cluster e il punto dati viene assegnato al cluster contenente il punto rappresentativo più vicino ad esso.

Pseudocodice

CURE (n. punti, k )

Input : Un insieme di punti S

Output: k cluster

• Per ogni cluster u (ogni punto di input), in u.mean e u.rep memorizzare la media dei punti nel cluster e un insieme di c punti rappresentativi del cluster (inizialmente c = 1 poiché ogni cluster ha un punto dati) . Inoltre u.closest memorizza il cluster più vicino a te.
• Tutti i punti di input sono inseriti in un kd tree T
• Tratta ogni punto di input come cluster separato, calcola u.closest per ogni u e quindi inserisci ciascun cluster nell'heap Q. (i cluster sono disposti in ordine crescente di distanza tra u e u.closest).
• Mentre dimensione (Q) > k
• Rimuovere l'elemento superiore di Q (diciamo u) e unirlo con il suo cluster più vicino u.closest (diciamo v) e calcolare i nuovi punti rappresentativi per il cluster unito w.
• Rimuovi u e v da T e Q.
• Per tutti i cluster x in Q, aggiorna x.closest e riposiziona x
• inserisci w in Q
• ripetere

Disponibilità

• La libreria open source pyclustering include un'implementazione Python e C++ dell'algoritmo CURE.

Guarda anche

• k significa clustering
• Algoritmo BFR

Riferimenti

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURA: un algoritmo di clustering efficiente per grandi database" (PDF) . Sistemi Informativi . 26 (1): 35-58. doi : 10.1016/S0306-4379(01)00008-4 .
• Kogan, Jacob; Nicola, Carlo K.; Teboulle, M. (2006). Raggruppamento di dati multidimensionali: recenti progressi nel clustering . Springer. ISBN 978-3-540-28348-5.
• Teodoridi, Sergio; Koutroumbas, Konstantinos (2006). Riconoscimento del modello . stampa accademica. pp. 572-574. ISBN 978-0-12-369531-4.