FOREL család algoritmusai

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 14-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A FOREL (Formal Element) egy klaszterező algoritmus , amely azon az elgondoláson alapul, hogy az objektumokat a legnagyobb koncentrációjú területeken egy klaszterbe vonják össze.

A klaszterezés célja

Osszuk fel a mintát olyan (korábban ismeretlen) számú taxonra , hogy a klaszterobjektumok és a klaszterközpontok közötti távolságok összege minden klaszter esetében minimális legyen. Azaz az a feladatunk, hogy egymáshoz minél közelebb eső objektumcsoportokat azonosítsunk, amelyek a hasonlósági hipotézis értelmében klasztereinket alkotják majd.

Az algoritmus által minimalizált minőségi funkcionális

F=\sum _{{j=1}}^{k}\sum _{{x\in K_{j}}}\rho (x,W_{j}),

ahol az első összegzés az összes mintaklaszterre vonatkozik, a második összegzés az aktuális klaszterhez tartozó összes objektumra vonatkozik, és az aktuális klaszter középpontja , és az objektumok közötti távolság . $x$ $K_{j}$ $W_j$ $\rho (x,y)$

A munkavégzés feltételei

A tömörségi hipotézis teljesülése , amely feltételezi, hogy az egymáshoz közel álló objektumok nagy valószínűséggel ugyanabba a klaszterbe (taxonba) tartoznak.
Klaszteres objektumok lineáris vagy metrikus terének jelenléte.

Bemeneti adatok

Csoportosított mintavétel

Meghatározható az objektumok jellemző leírásával – egy lineáris térrel vagy az objektumok közötti páronkénti távolságok mátrixával.
Megjegyzés: a valós feladatokban gyakran lehetetlen vagy értelmetlen az összes adat tárolása, ezért a szükséges adatok a klaszterezés során gyűjtésre kerülnek

Az R paraméter a helyi koncentrációk keresési sugara

Beállítható mind a priori megfontolásokból (a klaszter átmérőjének ismerete), mind a csúszó vezérléssel.

A módosítások során bevezethető a k paraméter — a klaszterek száma.

Impresszum

Csoportosulás egy korábban ismeretlen számú taxonba.

Hogyan működik

Minden lépésben véletlenszerűen kiválasztunk egy tárgyat a mintából, felfújunk egy R sugarú gömböt köré, kiválasztjuk a gömbön belüli súlypontot, és az új gömb középpontjává tesszük. Azaz minden lépésnél a mintatárgyak lokális koncentrációja irányába mozgatjuk a gömböt, azaz igyekszünk minél több mintatárgyat rögzíteni egy fix sugarú gömbbel. Miután a gömb középpontja stabilizálódott, a gömbön belüli összes tárgyat ezzel a középponttal csoportosítottként jelöljük meg, és kidobjuk a mintából. Ezt a folyamatot addig ismételjük, amíg a teljes minta csoportosul.

Algoritmus

A kijelölésből véletlenszerűen kiválasztjuk az aktuális objektumot;
Megjelöljük az aktuálistól R-nél kisebb távolságra lévő mintaobjektumokat;
Kiszámoljuk a súlypontjukat, megjelöljük ezt a középpontot új aktuális objektumként;
Ismételje meg a 2-3. lépéseket, amíg az új aktuális objektum meg nem egyezik a régivel;
Az aktuális objektum körüli R sugarú gömbön belüli objektumokat fürtözöttnek jelöljük, kidobjuk a kijelölésből;
Ismételje meg az 1–5. lépéseket, amíg a teljes minta csoportosul.

Az algoritmus pszeudokódja C - szerű nyelven:

# define R 30 // helyi fürtözés keresési szélessége - a clusterization_not_finished () algoritmus bemeneti paramétere ; // az összes objektum fürtözött get_random_object (); // egy tetszőleges, nem fürtözött objektumot ad vissza get_neighbour_objects ( type * object ); // olyan objektumok tömbjét adja vissza , amelyek <= R helyen találhatók az aktuális_objektumok_centrumból ( típus * mass_of_objects ) ; // visszaadja a megadott objektumok súlypontját delete_objects ( type * mass_of_objects ); // eltávolítja a megadott objektumokat a kijelölésből ( már csoportosítottuk őket ) , míg ( clusterisation_not_finished ()) { current_object = get_random_object ( ); szomszéd_objektumok = get_neighbour_objects ( jelenlegi_objektum ); center_object = objektumok_középpontja ( szomszéd_objektumok ); while ( center_object ! = aktuális_objektum ) // amíg a súlypont stabilizálódik { aktuális_objektum = center_object ; _ szomszéd_objektumok = get_neighbour_objects ( jelenlegi_objektum ); center_object = objektumok_középpontja ( szomszéd_objektumok ); } delete_objects ( szomszéd_objektumok ); }

Súlypont heurisztika

Lineáris térben a tömegközéppont;
A metrikus térben egy objektum, amelynek távolságainak összege minimális, a gömbön belüli összes között;
Olyan objektum, amely egy R sugarú gömbön belül tartalmazza a maximális számú egyéb objektumot a teljes kijelölésből (lassú);
Az az objektum, amely a maximális számú objektumot tartalmazza egy kis sugarú gömbön belül (az R sugarú gömbből).

Észrevételek

Az algoritmus véges számú lépésben való konvergenciája bizonyított;
A lineáris térben a súlypont tetszőleges térbeli pont lehet, a metrikus térben csak a minta tárgya;
Minél kisebb R, annál több taxon (klaszter);
Lineáris térben a középpont keresése O(n) időben, O(n²) metrikus térben történik;
Az algoritmus a legjobb eredményeket a tömörségi feltételek megfelelő teljesítése mellett éri el a mintákon;
Ismétlődő iterációknál lehetőség van az R paraméter csökkentésére, a leggyorsabb konvergencia érdekében;
A klaszterezés nagymértékben függ a kezdeti közelítéstől (az objektum kiválasztása az első lépésben);
Javasoljuk az algoritmus újbóli futtatását, hogy kiküszöböljük a „rossz” klaszterezés helyzetét, amely a kezdeti objektumok sikertelen kiválasztása miatt következett be.

Előnyök

A minőségi funkcionális minimalizálás pontossága (az R paraméter sikeres kiválasztásával);
Klaszteres vizualizáció megjelenítése;
Az algoritmus konvergenciája;
A klaszterek középpontjain végzett műveletek lehetősége - ezek az algoritmus során ismertek;
Képes kiszámítani a közepes minőségű funkcionálisokat, például a helyi koncentrációk láncolatának hosszát;
Hasonlósági és tömörségi hipotézisek tesztelésének lehetősége az algoritmus működése során.

Hátrányok

Viszonylag alacsony teljesítmény (megoldott a gömbön belüli 1 objektum hozzáadásakor a középpont keresésének újraszámítási funkciójának bevezetése);
Az algoritmus rossz alkalmazhatósága a minta klaszterekre való rossz szétválasztásával;
Az algoritmus instabilitása (a kezdeti objektum kiválasztásától való függés);
Tetszőleges szám szerinti felosztás klaszterekre;
A klaszterek szélességére (átmérőjére) vonatkozó előzetes ismeretek szükségessége.

Kiegészítők

Miután az algoritmus dolgozott a kész klaszterezésen, végrehajthat néhány műveletet:

A leginkább reprezentatív (reprezentatív) objektumok kiválasztása az egyes klaszterekből. Kiválaszthatja a klaszterek középpontjait, minden klaszterből több objektumot is kiválaszthat, figyelembe véve a minta szükséges reprezentativitásának előzetes ismereteit. Így a kész klaszterezés szerint lehetőségünk van a legreprezentatívabb minta felépítésére;
Klaszterezés (többszintűség) újraszámítása KNI módszerrel.

Hatókör

Klaszterezési problémák megoldása;
Minta rangsorolásának problémáinak megoldása.

Lásd még

klaszteranalízis

Irodalom

Vorontsov K. V. Előadások a klaszterezésről és a többdimenziós skálázási algoritmusokról , Moszkvai Állami Egyetem, 2007
Zagoruiko N. G., Yolkina V. N., Lbov G. S. Algorithms for detecting empirikus minták. - Novoszibirszk: Nauka, 1985. - 999 p.
Zagoruiko NG Alkalmazott adat- és tudáselemzési módszerek. - Novoszibirszk: IM SO RAN, 1999. - 270 p. - ISBN 5-86134-060-9 .