CURE -algoritme - CURE algorithm

Del af en serie om
Maskinlæring og data mining
Problemer Klassifikation Klynger Regression Anomali detektion Datarensning AutoML Foreningsregler Forstærkningslæring Struktureret forudsigelse Feature engineering Feature læring Online læring Semi-superviseret læring Uovervåget læring Lær at rangere Grammatisk induktion
Overvåget læring ( klassificering  • regression ) Beslutningstræer Ensembler Sække Boosting Tilfældig skov k -NN Lineær regression Naive Bayes Kunstige neurale netværk Logistisk regression Perceptron Relevans vektor maskine (RVM) Support vektor maskine (SVM)
Klynger BIRK HELBREDE Hierarkisk k -betyder Forventning – maksimering (EM) DBSCAN OPTIK Gennemsnitligt skift
Dimensionalitetsreduktion Faktoranalyse CCA ICA LDA NMF PCA PGD t-SNE
Struktureret forudsigelse Grafiske modeller Bayes net Betinget tilfældigt felt Skjult Markov
Anomali detektion k -NN Lokal outlier -faktor
Kunstigt neuralt netværk Autoencoder Kognitiv computing Dyb læring DeepDream Flerlags perceptron RNN LSTM GRU ESN Begrænset Boltzmann -maskine GAN SOM Konvolutionelt neuralt netværk U-Net Transformer Spiking neuralt netværk Memtransistor Elektrokemisk RAM (ECRAM)
Forstærkningslæring Q-læring SARSA Midlertidig forskel (TD)
Teori Bias -varians -afvejning Computational learning teori Empirisk risikominimering Occam læring PAC læring Statistisk læring VC teori
Maskinlæringssteder NeurIPS ICML ML JMLR ArXiv: cs.LG
Relaterede artikler Ordliste over kunstig intelligens Liste over datasæt til maskinlæringsforskning Oversigt over maskinlæring
v t e

CURE (Clustering Using REpresentatives) er en effektiv dataklynge -algoritme til store databaser . Sammenlignet med K-betyder-klynger er den mere robust over for ekstreme og i stand til at identificere klynger med ikke-sfæriske former og størrelsesforskelle.

Ulemper ved traditionelle algoritmer

Den populære K-middel-klynge- algoritme minimerer summen af ​​kvadratiske fejlkriterier:

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

I betragtning af store forskelle i størrelser eller geometrier af forskellige klynger, kan kvadratfejlmetoden opdele de store klynger for at minimere kvadratfejlen, hvilket ikke altid er korrekt. Også med hierarkiske klynge -algoritmer eksisterer disse problemer, da ingen af ​​afstandsmålene mellem klynger ( ) har tendens til at arbejde med forskellige klyngeformer. Også køretid er høj, når n er stor. ${\ displaystyle d_ {min}, d_ {mean}}$

Problemet med BIRCH -algoritmen er, at når klyngerne er genereret efter trin 3, bruger den centroider i klyngerne og tildeler hvert datapunkt til klyngen med den nærmeste centroid. Kun at bruge centroid til at omfordele dataene har problemer, når klynger mangler ensartede størrelser og former.

CURE -klynge -algoritme

For at undgå problemerne med ikke-ensartede størrelser eller formede klynger anvender CURE en hierarkisk klynge- algoritme, der vedtager en mellemvej mellem centroid-baserede og alle punktekstremer. I CURE vælges et konstant antal c af godt spredte punkter i en klynge, og de krympes mod klyngens midterkreds med en brøkdel α. De spredte punkter efter krympning bruges som repræsentanter for klyngen. Klyngerne med det nærmeste par repræsentanter er de klynger, der flettes på hvert trin i CUREs hierarkiske klynge -algoritme. Dette gør CURE i stand til korrekt at identificere klyngerne og gør det mindre følsomt over for ekstremiteter.

Driftstiden er O ( n ² log n ), hvilket gør den temmelig dyr, og rumkompleksiteten er O ( n ).

Algoritmen kan ikke direkte anvendes på store databaser på grund af den høje runtime -kompleksitet. Forbedringer opfylder dette krav.

• Tilfældig prøveudtagning: tilfældig stikprøve understøtter store datasæt. Generelt passer stikprøven i hovedhukommelsen . Den stikprøveudtagning indebærer en afvejning mellem nøjagtighed og effektivitet.
• Partitionering: Den grundlæggende idé er at opdele prøveområdet i p -partitioner. Hver partition indeholder n/p -elementer. Den første passage klynger delvist hver partition, indtil det endelige antal klynger reduceres til n/pq for nogle konstante q ≥ 1. En anden klyngegang på n/q delvist klynge -partitioner. For den anden gennemgang lagres kun de repræsentative punkter, da fletningsproceduren kun kræver repræsentative punkter i tidligere klynger, før de beregner de repræsentative punkter for den fusionerede klynge. Partitionering af input reducerer udførelsestiden.
• Mærkning af data på disk: Gives kun repræsentative punkter for k -klynger, tildeles de resterende datapunkter også til klyngerne. Til dette vælges en brøkdel af tilfældigt udvalgte repræsentative punkter for hver af k -klyngerne, og datapunkt tildeles klyngen, der indeholder det repræsentative punkt, der er tættest på det.

Pseudokode

CURE (antal point, k )

Input: Et sæt punkter S

Output: k klynger

• For hver klynge u (hver indgang point), i u.mean og u.rep gemme middelværdien af de punkter i klyngen og et sæt af c repræsentative punkter i klyngen (oprindeligt c = 1, da hver klynge har et datapunkt) . Også u.nærmeste gemmer klyngen tættest på u.
• Alle inputpunkter indsættes i et kd -træ T
• Behandl hvert inputpunkt som en separat klynge, beregn u.næreste for hver u, og indsæt derefter hver klynge i bunken Q. (klynger er arrangeret i stigende rækkefølge af afstande mellem u og u.nærmeste).
• Mens størrelse (Q)> k
• Fjern det øverste element i Q (sig u), og flet det med sin nærmeste klynge u.nærmeste (siger v) og beregne de nye repræsentative punkter for den fusionerede klynge w.
• Fjern u og v fra T og Q.
• For alle klynger x i Q skal du opdatere x.nærmeste og flytte x
• indsæt w i Q
• gentage

Tilgængelighed

• pyclustering open source -bibliotek inkluderer en Python og C ++ implementering af CURE -algoritme.

Se også

• k-betyder klynge
• BFR algoritme

Referencer

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: En effektiv klynge -algoritme til store databaser" (PDF) . Informationssystemer . 26 (1): 35–58. doi : 10.1016/S0306-4379 (01) 00008-4 .
• Kogan, Jacob; Nicholas, Charles K .; Teboulle, M. (2006). Gruppering af flerdimensionale data: nylige fremskridt inden for klynger . Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Mønstergenkendelse . Academic Press. s. 572–574. ISBN 978-0-12-369531-4.