Algoritmus CURE

CURE ( Clustering Using Representatives ) je účinný algoritmus shlukové analýzy pro velké databáze .  Algoritmus je ve srovnání s metodou k-means odolnější vůči odlehlým hodnotám a je schopen detekovat shluky, které nemají kulový tvar as velkým rozptylem velikosti.

Nevýhody tradičních algoritmů

Populární algoritmus k-means minimalizuje součet čtvercových chyb :

Pokud existuje velký rozdíl ve velikosti nebo geometrii různých shluků, metoda kvadratické chyby může rozdělit velké shluky, aby se minimalizovala druhá mocnina chyby, což není vždy správné. Také v případě hierarchických shlukovacích algoritmů je tento problém přítomen, protože žádný z měřítek vzdálenosti mezi shluky ( ) nemá tendenci pracovat s různými formami shluků. Také doba běhu je velká, pokud je n velké.

Problém s algoritmem BIRCH je v tom, že při generování shluků po kroku 3 používá algoritmus těžiště shluků a přiřazuje každou informaci shluku s nejbližším těžištěm. Použití pouze těžišť k přerozdělení bodů má problém, pokud shluky netvoří jednotné velikosti a tvary.

Shlukovací algoritmus CURE

Aby se předešlo problémům s nejednotnými velikostmi nebo tvary shluků, používá CURE hierarchický shlukovací algoritmus , který vytváří kompromis mezi těžištěm a všemi extrémy. V algoritmu CURE jsou vybrány konstantní body shluku c s dobrým rozložením a tyto body jsou staženy do těžiště shluku o nějakou hodnotu. Body po kontrakci se používají jako zástupci shluku. Shluky s nejbližší dvojicí zástupců jsou kombinovány v každém kroku hierarchického shlukovacího algoritmu CURE. To umožňuje algoritmu CURE správně rozpoznat shluky a činí jej méně citlivým na odlehlé hodnoty.

Doba běhu je O( n 2 log n ), což jej činí poměrně drahým, a prostorová složitost algoritmu je O( n ).

Algoritmus nelze použít přímo na velkou databázi z důvodu vysoké výpočetní náročnosti. Následující vylepšení řeší tento problém.

• Náhodný výběr: Náhodný výběr podporuje velké datové sady. V obecném případě je náhodný výběr umístěn do paměti RAM . Náhodný výběr je kompromisem mezi přesností a účinností.
• Rozdělení: Hlavní myšlenkou je rozdělit prostor elementárních událostí na p části. Každá část obsahuje n/p prvků. První průchod shlukuje každou část, dokud se celkový počet shluků nesníží na n/pq pro nějakou konstantu . Druhý průchod shlukování zvýší počet shluků na n/q . Při druhém průchodu se ukládají pouze reprezentativní body, protože procedura slučování shluků vyžaduje před výpočtem zástupců sloučeného shluku pouze zástupce shluků. Rozdělení vstupu zkracuje dobu provádění.
• Označení dat na disku: Pokud jsou uvedeni pouze zástupci k shluků, zbývající informace se také rozdělí mezi shluky. K tomu se pro každý z k shluků vyberou náhodně reprezentující body a shluku obsahujícímu nejbližšího zástupce bodu je přiřazena informace.

Pseudokód

CURE (počet bodů, k )

Vstup: Sada bodů S

Výstup: k clusterů

• Pro každý shluk u (každý bod), u.mean a u.rep ukládají těžiště bodů shluku a množinu zástupců shluku c (zpočátku c = 1, protože každý shluk má jednu informaci). U.closest také ukládá nejbližší cluster k u.
• Všechny vstupní body jsou vloženy do k-rozměrného stromu T
• Zacházejte s každým vstupním bodem jako se samostatným shlukem, vypočítejte u.nejbližší pro každé u a poté vložte každý shluk do haldy Q. (shluky jsou uspořádány podle rostoucí vzdálenosti od u k u.nejbližší).
• Pokud velikost (Q) > k
• Odstraníme horní prvek haldy Q(u) a sloučíme jej s jeho nejbližším shlukem u.closest(v), poté vypočítáme nové zástupce pro sloučený shluk w.
• Odeberte u a v z T a Q.
• Pro všechny clustery x z Q aktualizujte x.closest a určete umístění x v haldě
• vložte w do Q
• přejděte na začátek cyklu

Dostupnost

• Knihovna pyclustering s otevřeným zdrojovým kódem obsahuje implementaci algoritmu CURE v Pythonu a C++.

Viz také

• metoda k-means
• Algoritmus BFR

Poznámky

Literatura

• Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: Efektivní shlukovací algoritmus pro velké databáze  // Informační systémy. - 1998. - T. 26 , no. 1 . — s. 35–58 . - doi : 10.1016/S0306-4379(01)00008-4 .
• Jacob Kogan, Charles K. Nicholas, Teboulle M. Seskupování vícerozměrných dat: nedávné pokroky v shlukování. - Springer, 2006. - ISBN 978-3-540-28348-5 .
• Sergios Theodoridis, Konstantinos Koutroumbas. Rozpoznávání vzorů . - Academic Press, 2006. - S. 572-574. — ISBN 978-0-12-369531-4 .