CURE algoritme

CURE ( Clustering Using Representatives ) er en effektiv klyngeanalysealgoritme til store databaser .  Sammenlignet med k-means-metoden er algoritmen mere modstandsdygtig over for outliers og er i stand til at detektere klynger, der ikke har en sfærisk form og med en stor størrelsesspredning.

Ulemper ved traditionelle algoritmer

En populær k- betydningsalgoritme minimerer summen af ​​kvadratiske fejl :

Hvis der er stor forskel på størrelsen eller geometrien af ​​de forskellige klynger, kan den kvadratiske fejlmetode opdele store klynger for at minimere kvadratet af fejlen, hvilket ikke altid er korrekt. Også i tilfælde af hierarkiske klyngealgoritmer er dette problem til stede, da ingen af ​​afstandsmålene mellem klynger ( ) har en tendens til at fungere med forskellige former for klynger. Også køretiden er stor, hvis n er stor.

Problemet med BIRCH- algoritmen er, at når du genererer klynger efter trin 3, bruger algoritmen tyngdepunktet for klyngerne og tildeler hver information til klyngen med det nærmeste tyngdepunkt. At kun bruge tyngdepunkter til at omfordele punkter har et problem, hvis klyngerne ikke danner ensartede størrelser og former.

Klyngealgoritme CURE

For at undgå problemer med uensartede størrelser eller former for klynger, bruger CURE en hierarkisk klyngealgoritme , der foretager en afvejning mellem tyngdepunktet og alle ekstremer. I CURE-algoritmen vælges en konstant c klyngepunkter med en god fordeling, og disse punkter trækkes sammen med klyngens tyngdepunkt med en eller anden værdi. Punkterne efter kontraktion bruges som repræsentanter for klyngen. Klynger med det nærmeste par af repræsentanter kombineres ved hvert trin i CUREs hierarkiske klyngealgoritme. Dette gør det muligt for CURE-algoritmen at genkende klynger korrekt og gør den mindre følsom over for outliers.

Køretiden er O( n 2 log n ), hvilket gør den temmelig dyr, og rumkompleksiteten af ​​algoritmen er O( n ).

Algoritmen kan ikke anvendes direkte på en stor database på grund af den høje beregningsmæssige kompleksitet. Følgende forbedringer løser dette problem.

• Tilfældigt udvalg: Tilfældigt valg understøtter store datasæt. I det generelle tilfælde placeres tilfældigt valg i RAM . Tilfældig udvælgelse er et kompromis mellem nøjagtighed og effektivitet.
• Opdeling: Hovedideen er at opdele rummet af elementære begivenheder i p - dele. Hver del indeholder n/p -elementer. Den første passage klynger hver del, indtil det samlede antal klynger er reduceret til n/pq for en konstant . Den anden klyngepasning bringer antallet af klynger til n/q . Ved den anden gennemgang gemmes kun repræsentative punkter, da klyngesammenlægningsproceduren kun kræver klyngerepræsentanter, før den fusionerede klynges repræsentanter beregnes. Opdeling af input reducerer udførelsestiden.
• Markering af data på disk: Hvis der kun er angivet repræsentanter for k klynger, fordeles de resterende informationer også mellem klyngerne. For at gøre dette udvælges tilfældigt repræsenterende punkter for hver af de k klynger, og et stykke information tildeles den klynge, der indeholder den nærmeste repræsentant til punktet.

Pseudokode

CURE (antal point, k )

Input: Sæt af punkter S

Output : k klynger

• For hver klynge u (hvert punkt) gemmer u.mean og u.rep tyngdepunktet for klyngepunkterne og et sæt c klyngerepræsentanter (initielt c = 1, da hver klynge har én information). U.closest gemmer også den tætteste klynge på u.
• Alle inputpunkter indsættes i et k-dimensionelt træ T
• Behandl hvert inputpunkt som en separat klynge, beregn u.nærmest for hver u, og indsæt derefter hver klynge i heap Q. (klynger er arrangeret i rækkefølge efter stigende afstand fra u til u.nærmeste).
• Så længe størrelse (Q) > k
• Vi fjerner det øverste element af heapen Q(u) og slår det sammen med dets nærmeste klynge u.nærmeste(v), og beregner derefter nye repræsentanter for den fusionerede klynge w.
• Fjern u og v fra T og Q.
• For alle klynger x fra Q skal du opdatere x.nærmest og bestemme placeringen af ​​x i heapen
• indsæt w i Q
• gå til begyndelsen af ​​cyklussen

Tilgængelighed

• Open source pyclustering- biblioteket inkluderer en implementering af CURE-algoritmen i Python og C++.

Se også

• k-betyder metode
• BFR-algoritme

Noter

Litteratur

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