CURE-algoritm

CURE ( Clustering Using Representatives ) är en effektiv klusteranalysalgoritm för stora databaser .  Jämfört med k-means-metoden är algoritmen mer motståndskraftig mot extremvärden och kan detektera kluster som inte har en sfärisk form och med stor storleksspridning.

Nackdelar med traditionella algoritmer

En populär k-medelalgoritm minimerar summan av kvadratiska fel :

Om det finns en stor skillnad i storleken eller geometrin hos de olika klustren, kan den kvadratiska felmetoden dela upp stora kluster för att minimera kvadraten på felet, vilket inte alltid är korrekt. Även i fallet med hierarkiska klustringsalgoritmer finns detta problem, eftersom inget av avståndsmåtten mellan kluster ( ) tenderar att fungera med olika former av kluster. Dessutom är körtiden stor om n är stor.

Problemet med BIRCH- algoritmen är att när kluster genereras efter steg 3 använder algoritmen klustrens tyngdpunkt och tilldelar varje information till klustret med närmaste tyngdpunkt. Att endast använda tyngdpunkter för att omfördela punkter har ett problem om klustren inte bildar enhetliga storlekar och former.

Klustringsalgoritm CURE

För att undvika problem med olikformiga storlekar eller former av kluster, använder CURE en hierarkisk klusteralgoritm som gör en avvägning mellan tyngdpunkten och alla ytterligheter. I CURE-algoritmen väljs en konstant c -klusterpunkter med god fördelning och dessa punkter dras samman med klustrets tyngdpunkt med något värde. Punkterna efter kontraktion används som representanter för klustret. Kluster med det närmaste paret av representanter kombineras vid varje steg i CUREs hierarkiska klustringsalgoritm. Detta gör det möjligt för CURE-algoritmen att korrekt känna igen kluster och gör den mindre känslig för extremvärden.

Körtiden är O( n 2 log n ), vilket gör den ganska dyr, och rymdkomplexiteten för algoritmen är O( n ).

Algoritmen kan inte appliceras direkt på en stor databas på grund av den höga beräkningskomplexiteten. Följande förbättringar löser detta problem.

• Slumpmässigt urval: Slumpmässigt urval stöder stora datamängder. I det allmänna fallet placeras slumpmässigt urval i RAM . Slumpmässigt urval är en kompromiss mellan noggrannhet och effektivitet.
• Partitionering: Huvudidén är att dela upp utrymmet för elementära händelser i p- delar. Varje del innehåller n/p- element. Det första passet kluster varje del tills det totala antalet kluster reduceras till n/pq för någon konstant . Det andra klustringspasset bringar antalet kluster till n/q . Vid det andra passet lagras endast representativa punkter, eftersom klustersammanfogningsproceduren endast kräver klusterrepresentanter innan representanterna för det sammanslagna klustret beräknas. Att dela ingången minskar exekveringstiden.
• Märkning av data på disk: Om endast representanter för k kluster anges, fördelas även återstående information mellan klustren. För att göra detta väljs slumpmässigt representerande punkter för vart och ett av de k klustren, och en bit information tilldelas klustret som innehåller den närmaste representanten till punkten.

Pseudokod

CURE (antal punkter, k )

Ingång: Uppsättning punkter S

Utgång: k kluster

• För varje kluster u (varje punkt), lagrar u.mean och u.rep tyngdpunkten för klusterpunkterna och en uppsättning c klusterrepresentanter (initialt c = 1, eftersom varje kluster har en bit information). Dessutom lagrar u.closest det närmaste klustret till u.
• Alla inmatningspunkter infogas i ett k-dimensionellt träd T
• Behandla varje ingångspunkt som ett separat kluster, beräkna u.närmast för varje u, och infoga sedan varje kluster i heap Q. (klustren är ordnade efter ökande avstånd från u till u.närmast).
• Så länge storlek (Q) > k
• Vi tar bort det översta elementet i högen Q(u) och slår samman det med dess närmaste kluster u.closest(v), och beräknar sedan nya representanter för det sammanslagna klustret w.
• Ta bort u och v från T och Q.
• För alla kluster x från Q, uppdatera x.närmast och bestäm platsen för x i högen
• infoga w i Q
• gå till början av cykeln

Tillgänglighet

• Biblioteket med öppen källkod för pyclustering inkluderar en implementering av CURE-algoritmen i Python och C++.

Se även

• k-betyder metod
• BFR-algoritm

Anteckningar

Litteratur

• Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: En effektiv klustringsalgoritm för stora databaser  // Informationssystem. - 1998. - T. 26 , nr. 1 . — s. 35–58 . - doi : 10.1016/S0306-4379(01)00008-4 .
• Jacob Kogan, Charles K. Nicholas, Teboulle M. Gruppering av multidimensionella data: senaste framsteg inom klustring. - Springer, 2006. - ISBN 978-3-540-28348-5 .
• Sergios Theodoridis, Konstantinos Koutroumbas. Mönsterigenkänning . - Academic Press, 2006. - S. 572-574. — ISBN 978-0-12-369531-4 .