5. fejezet - Konkrét feladat: korrelációs klaszterezés

Tartalom

Cluster osztály
Gráf ábrázolása
Jelölt gráf ábrázolása mátrixszal
Egészek mátrixa
Bitek mátrixai
Feladatok
Gráf generálása
Mátrixsorozat generálása
Erdős-Rényi gráfgenerálás
Mátrixsorozat mentése
Barabási-Albert modell
Feladatok
Csoportosítás megadása
Klaszterek megadása
Számsorozat ábrázolás
Bitmátrixos ábrázolás
Kombinált ábrázolás
Futási eredmények kiírása
Eredmények kiírása
Célfüggvény értéke
Leíró statisztika
Segédosztályok
BitMatrix
Bitvektor
Solution
Main osztály
Konstansok

A korrelációs klaszterezés a gépi tanulás mellett előfordul a társadalom- és természettudományokban is. Az egyes egyedek kapcsolatáról, egymáshoz való hasonlatosságról van tudomásunk. Pontosabban adott egy G = (V,E) előjeles gráf, ahol az adott élhez rendel + jel jelzi, hogy az élhez tartozó csúcsoknak megfelelő egyedek hasonlóak, míg az élhez rendelt - jel az eltérést jelöli. A feladatunk, hogy az egymáshoz hasonló csúcsokat közös klaszterekbe szervezzük. A statisztikában és adatbányászatban elterjedt klaszterezésektől eltérően itt nem adott előzetesen, hogy hány klasztert kell alkotunk.

A valós életben emberekre vonatkoztatva a feladatot, a + és - jeleket értelmezhetjük úgy, mint a két ember szereti vagy gyűlöli egymást. Könnyen elképzelhetjük azt a helyzetet, amelyben egy főnök és egymással rivalizáló két beosztottja szerepel. A főnök szereti a beosztottjait, ahogy azok is a főnököt, ám a két beosztott gyűlöli egymást. A három ember öt lehetséges klaszterezéséről belátható, hogy egyik sem tökéletes, azaz egy klaszterbe kerül két egymást gyűlölő ember, vagy egymást szerető emberek külön klaszterbe kerülnek.

Ezek alapján feladatunk a következőképpen pontosítható: a V halmaznak adjuk meg azt a partícióját (osztályozását) melynél az ilyen konfliktusok száma a minimális legyen. Ennek megfelelően célfüggvényünk az olyan esetek száma, amikor + jellel jelölt él két végpontja külön partíciókban szerepel, vagy - jellel jelölt él két végpontja azonos partícióban található.

A feladat ezekkel a megkötésekkel NP teljes. Az összes lehetséges particionálás darabszámát a Bell számok adják meg. Az előbbi link segítségével elérhető a pontos megfogalmazás, ezért az alábbiakban csak néhány konkrét értéket sorolunk fel, ám ebből is látszik, hogy milyen gyorsan nő a függvény. A jegyzet írása idején maximum a 1030 állapotot tartalmazó feladatoknál merült fel, hogy az összes lehetséges állapotot egyesével végigvizsgálja egy számítógép. A korrelációs klaszterezés feladatánál a fizikusokat a több ezres csúcspontot tartalmazó gráfok érdeklik, így valóban szükségünk van megfelelő módszerekre, hogy elfogadható időn belül az optimálishoz közeli megoldást kapjunk ilyen elképzelhetetlenül nagy feladatok esetén is.

5.1. táblázat - Bell számok

nBn
01
11
22
35
415
552
10115 975
2051 724 158 235 372
1004,758539*10116
2006,247485*10276
5001,606073*10844
7509,453324*101370

Cluster osztály

Ahhoz, hogy a korábban ismertetett algoritmusokat alkalmazhassuk erre a problémára, a StateRC absztrakt osztályt a korrelációs klaszterezés feladatának megfelelően ki kell terjeszteni.

5.1. ábra - Cluster osztály

Cluster osztály

A Cluster osztály felhasznál további osztályokat. A további alfejezetek ezeket ismertetik. Hogy átlássuk ezek kapcsolatát, következzen egy áttekintő osztálydiagram:

5.2. ábra - Cluster osztály kapcsolata más osztályokkal

Cluster osztály kapcsolata más osztályokkal