Adatbányászat labor nagyfeladat

A Ward klaszterező algoritmus implementálása és elemzése

Készítette: Németh Bottyán és Takács Gábor


1. A feladat


Ward algoritmusa egy lentről építkező hierarchikus klaszterező eljárás. Az alulról építkezés azt jelenti, hogy kezdetben minden elem külön klaszter, ezután az algoritmus minden lépésben két klasztert egyesít egészen addig, amíg a klaszterek száma egy megadott értékre nem csökken. Ward módszere az egyesítések során a legkisebb négyzetes hibát próbálja meg minimalizálni (így csak vektortérben megadott pontok esetén alkalmazható). Az algoritmus minden lépésben azt a két klasztert egyesíti, amelyek a legkisebb négyzetes hibanövekedést okozzák. A módszer rendelkezik a négyzetes hibát minimalizáló eljárások minden hátrányával. Emellett nem skálázható, hiszen a távolságmátrixszal dolgozik, és végül nem garantált, hogy megtalálja a globális minimumot.


Nekünk konkrétan egy Ward klaszterező modullal kellett kibővítenünk Pilászy István és Förhécz András klaszterező keretrendszerét, utána konkrét példákon kellett kipróbálnunk az algoritmust, végül elemeznünk kellett a kapott eredményeket.


2. Naív implementáció


Első nekifutásra az ember valahogy így valósítja meg két klaszter egyesítését (pszeudokód):


doOneStep() {
    for (összes (ci, cj) klaszterpárra) {
        hiba = computeSquareError(ci, cj)
        hibanövekmény = hiba - ci.hiba - cj.hiba

        if (hibanövekmény < hibanövekmény_min) {
            hibanövekmény_min = hibanövekmény
            legjobb_pár = (ci, cj)
        }
    }

    join(legjobb_pár[1], legjobb_pár[2])
    klaszterszám--
}

Az egyesített klaszter négyzetes hibájának számítása naív módszerrel, 2 dimenziós pontok klaszterezése esetén (pszeudokód):


computeSquareError(Cluster ci, Cluster cj) {
    (avgX, avgY) = az egyesített kalszter középpontja
    négyzetes_hibaösszeg = 0

    while(ci.hasNextPoint()) {
        p = ci.nextPoint()
        négyzetes_hibaösszeg += (avgX - p.x)*(avgX - p.x)
        négyzetes_hibaösszeg += (avgY - p.y)*(avgY - p.y)
    }

    while(cj.hasNextPoint()){
        p = cj.nextPoint()
        négyzetes_hibaösszeg += (avgX - p.x)*(avgX - p.x)
        négyzetes_hibaösszeg += (avgY - p.y)*(avgY - p.y)
    }

    return négyzetes_hibaösszeg
}

3. Gyorsítás


A naív implementációval egy működő, de sajnos elég lassú algoritmust kaptunk. Nem tudtunk annyi ponttal tesztelni, mint amennyi Pilászy és Förhécz úr tesztjeiben szerepelt. Ezért megpróbáltunk valami gyorsítást kitalálni. A megoldást a Steiner formula alkalmazása jelentette.


Steiner formula:


Var[X] = E[X2] – E[X]2


Vagyis a valószínűségi változó szórásnégyzete kiszámítható a négyzet várható értékének és a várható érték négyzetének különbségeként.


Egy n pontú klaszter négyzetes hibája tulajdonképpen a klaszter szórásnégyzetének n-szerese. Ezért n-nel való szorzás után a Steiner formula a mi esetünkre is alkalmazható (E[X2] a pontok négyzetének átlaga és E[X]2 a középpont négyzete). Az pedig jelentősen gyorsít az algoritmuson, ha az egyesített klaszter négyzetes hibáját a Steiner formula segítségével számítjuk ki, mivel az egyesített kalszter E[X2] és E[X]2 értéke könnyen megkapható az egyesítendő klaszterek hasonló értékeiből (ha nyivántartjuk a klaszterek E[X2] és E[X]2 értékeit).


Megjegyzés: A klaszterezendő pontok több dimenziósak, így a Steiner formulát koordinátánként alkalmazzuk.


Másik megjegyzés: Ezzel a módszerrel természetesen csak konstansszoros lépésszámcsökkenés érhető el. Az aszimptotikus lépésszámigény a gyorsítás után is O(klaszterszám2).


Sebességnövekedés a naív módszerhez képest (mérési eredmények egy Athlon XP 1700-as processzorú, 256 Mb memóriával rendelkező gépen):



Tehát a naív módszerhez képesti sebességnövekedés kb. 10-szeres.


4. Teszteredmények


Az algoritmust a keretrendszerben megtalálható 7 db (2 dimenziós) tesztmintára próbáltuk ki. Zajmentes és a zajos esetet is vizsgáltunk. Az eredmények nagyjából megfelelnek a várakozásoknak: a négyzetes hibát minimalizáló algoritmus mindig nagyjából ellipszisekkel választotta szét a klasztereket. Ha az alakzatok klaszterszám darab ellipszissel szétválaszthatók voltak, akkor az algoritmus megfelelő eredményt adott. Ha az alakzatok nem voltak klaszterszám darab ellipszissel szétválaszthatók, akkor az algoritmus a bonyolultabb alakzatokat több részre vágta. A kis mértékű zajosítás nem nagyon befolyásolta az eredményt, az algoritmus jól tűrte az outlyer-eket.