Sok összevonó hierarchikus klaszterező módszer egyetlen megközelítés változata: az egyedi pontokkal mint klaszterekkel indulva egymás után vonjuk össze a legközelebbi klasztereket egészen addig, amíg egyetlen klaszter nem marad. Ezt az algoritmust írja le formálisan a 8.3. algoritmus.

A klaszterek közötti közelség definiálása

A 8.3. algoritmus legfontosabb lépése a klaszterek közötti közelség kiszámítása. A különböző hierarchikus klaszterező eljárások között fennálló különbséget éppen a klaszterek közötti közelség definíciója okozza. Klaszterek közelségét jellemzően a fejünkben lévő klaszterek konkrét típusa alapján definiáljuk -- lásd a 8.1.3. szakaszt. Például sok hierarchikus klaszterező módszer, mint a MIN, a MAX és a csoportátlag (group average) módszer, származik a klaszterek gráfalapú megjelenítéséből. A MIN módszer két klaszter közötti közelség alatt a különböző klaszterekben található legközelebbi pontpár távolságát érti, vagy a gráfok nyelvén fogalmazva, két csúcs közötti legrövidebb élt csúcsok különböző részhalmazaiban. Ez a 8.2. (c) ábrán látható szomszédság-alapú klasztereket szolgáltatja. Alternatív módon, a MAX módszer közelségnek a különböző klaszterekben található legtávolabbi két pont között mért távolságot veszi, vagy a gráfok nyelvén, két csúcs közötti leghosszabb élt csúcsok különböző részhalmazaiban. (Ha a közelségek valójában távolságok, akkor a MIN és a MAX elnevezések rövidek és sokatmondóak. Hasonlóságok esetén azonban, ahol a nagyobb érték közelebbi pontokat takar, az elnevezések fordítottnak tűnnek. Ezen okból előnyben részesítjük a tárgyalt módszerek alternatív neveit, az egyszerű kapcsolás (single link), és a teljes kapcsolás (complete link) elnevezéseket.) Egy másik gráfalapú megközelítés a csoportátlag módszer, amely a klaszter-közelségeket a különböző klaszterekből vett összes pontpár távolságának átlagaként (átlagos élhosszként) definiálja. A 8.14. ábra szemlélteti ezt a három megközelítést.

Amennyiben ehelyett a prototípus-alapú szemlélettel élünk, amelynél minden klasztert a középpontja jellemez, a klaszter-közelség más definíciói tűnnek természetesebbnek. Középpontok használata során a közelség alatt gyakran a középpontok közötti közelséget értjük. Egy alternatív módszer, Ward módszere, szintén azt feltételezi, hogy a klasztereket a középpontjaikkal jellemezzük, azonban két klaszter közelségét az összeolvasztásukból származó, a teljes négyzetes hibában fellépő növekménnyel méri. A K -közép módszerhez hasonlóan, Ward módszere is a pontoknak a klaszter-középpontjaiktól vett négyzetes távolságaik összegét minimalizálja.

Idő- és tárbonyolultság

A bemutatott összevonó hierarchikus klaszterező eljárás közelségi mátrixot használ. A mátrix tárolásához -- feltételezve, hogy az szimmetrikus -- 1 2 m 2 közelséget kell tárolnunk, ahol m az adatpontok száma. A klaszterek követéséhez a klaszterek számával arányos méretű tárhelyre van szükség, amely m−1 az egy elemű klasztereket nem számolva. Így a teljes tárbonyolultság O( m 2 ) .

A tárgyalt összevonó klaszterező algoritmus időbonyolultságának elemzése szintén egyszerű. A közelségi mátrix számítása O( m 2 ) időt igényel. Ezután m−1 , a harmadik és negyedik lépést magában foglaló iteráció történik, hiszen kezdetben m klaszterünk van, és minden iterációs lépés során két klasztert vonunk össze. Feltételezve, hogy a közelségi mátrixban a keresés lineáris, a 3. lépés i. iterációjának időigénye O( (m−i+1) 2 ) , amely arányos a már meglévő klaszterek számának négyzetével. A 4. lépés, a klaszterösszevonás utáni közelségi mátrix számítása, csak O(m−i+1) időigényű. (Egy klaszterösszevonás csak O(m−i+1) közelséget érint a mátrixban.) Módosítás nélkül ez O( m 3 ) időbonyolultságot jelentene. Amennyiben a klaszterek közötti távolságokat egy rendezett listában (vagy kupacban) tároljuk, a keresési időt O(m−i+1) -ig csökkenthetjük. Mivel azonban az adatok rendezett listában vagy kupacban tárolása további bonyolultsággal jár, így a 8.3. algoritmuson alapuló hierarchikus klaszterezés teljes időbonyolultsága O( m 2 logm) lesz.

A hierarchikus klaszterezés idő- és tárbonyolultsága erősen korlátozza a feldolgozható adathalmaz méretét. A klaszterező algoritmusok, köztük a hierarchikus klaszterező eljárások skálázhatósági kérdéseivel a 9.5. szakaszban foglalkozunk.

Mintaadatok

A különböző hierarchikus klaszterező algoritmusok viselkedésének szemléltetésére egy minta adathalmazt használunk, amely 6 kétdimenziós pontot tartalmaz. Az adatpontokat a 8.15. ábrán láthatjuk. Az x és y koordinátákat a 8.3. táblázat, a pontok közötti euklideszi távolságokat pedig a 8.4. táblázat tartalmazza.

Egyszerű kapcsolás vagy MIN módszer

A hierarchikus módszer egyszerű kapcsolású vagy másnéven MIN változata két klaszter közelségét úgy definiálja, mint a két különböző klaszterben elhelyezkedő tetszőleges két pont közötti legkisebb távolság (legnagyobb hasonlóság). Gráfelméleti terminológiát használva, ha kezdetben minden pontot különálló klaszternek tekintünk, és egyesével éleket veszünk fel a pontok között, a legrövidebb éllel kezdve, akkor ezek az élek a pontokat klaszterekbe fogják össze. Az egyszerű kapcsolású módszer nem-elliptikus klaszterek felismerésére alkalmas, azonban érzékeny a zajra és a kiugró értékekre.

8.4. Példa.

(Egyszerű kapcsolás) A 8.16. ábra a mintaadatállományunk 6 pontján végrehajtott egyszerű kapcsolású módszer eredményét mutatja. A 8.16. (a) ábrán a beágyazott klasztereket egymásba ágyazott ellipszisek sorozataként ábrázoljuk, ahol a feltüntetett számok a klaszterek létrehozásának sorrendjét jelölik. A 8.16. (b) ábra ugyanezt ábrázolja dendrogram formájában. Az a magasság, ahol a klaszterek összekapcsolódnak, a klaszterek közötti távolságot reprezentálja a dendrogramon. A 8.4. táblázatból kiolvashatjuk például, hogy a 3-as és a 6-os pont közötti távolság 0,11, és ez az a magasság, amelyen egy klaszterbe kapcsolódnak össze a dendrogramon. Egy másik példa a {3,6} és a {2,5} klaszterek közötti távolság, amely az alábbi módon adódik:

d({3,6},{2,5})=min(d(3,2),d(6,2),d(3,5),d(6,5))

=min(0,15;0,25;0,28;0,39)

=0,15.

Teljes kapcsolás vagy MAX vagy CLIQUE módszer

A hierarchikus klaszterezés teljes kapcsolású vagy MAX változatában két klaszter közelségét a két különböző klaszterbeli két tetszőleges pont közötti távolság maximumával (hasonlóság minimumával) definiáljuk. Gráfelméleti terminológiát használva, ha kiinduláskor a pontokra úgy tekintünk, mint egyelemű klaszterekre, és egyesével éleket veszünk fel a pontok között, a legrövidebb éllel kezdve, akkor pontok egy csoportja addig nem alkot klasztert, amíg a csoport minden pontja teljesen össze nincs kapcsolva, azaz amíg klikket (clique) nem alkotnak. A teljes kapcsolás kevésbé érzékeny a zajra és a kiugró értékekre, azonban a nagyméretű klasztereket több részre bonthatja, valamint a gömb alakú klasztereket részesíti előnyben.

8.5. Példa.

(Teljes kapcsolás) A 8.17. ábrán a 6 pont mintaadatállományán végrehajtott MAX módszer eredményét láthatjuk. Ahogyan az egyszerű kapcsolás esetében is, az első lépésben a 3-as és a 6-os pontot kapcsoljuk össze. Azonban a {3,6} pontcsoportot a {2,5} vagy az {1} helyett a {4} -gyel kapcsoljuk össze mert

d({3,6},{4})=max(d(3,4),d(6,4))

=max(0,15;0,22)

=0,22,

d({3,6},{2,5})=max(d(3,2),d(6,2),d(3,5),d(6,5))

=max(0,15;0,25;0,28;0,39)

=0,39,

d({3,6},{1})=max(d(3,1),d(6,1))

=max(0,22;0,23)

=0,23.

Csoportátlag

A hierarchikus klaszterezés csoportátlag változatában két klaszter viszonyát úgy határozzuk meg, hogy a különböző klaszterek összes pontpárja közötti páronkénti közelség (távolság) átlagát vesszük. Ez egy köztes megoldást eredményez az egyszerű és a teljes kapcsolású módszer között. Így a csoportátlag módszer az m i és m j méretű C i és C j klaszterek közelségét ( közelség( C i , C j ) ) az alábbi képlettel határozza meg:

közelség( C i , C j )= ∑ x∈ C i y∈ C j közelség(x,y) m i * m j . (8.6)

8.6. Példa

(Csoportátlag) A 8.18. ábra a 6 pont mintaadatállományára alkalmazott csoportátlag módszer eredményét mutatja. A módszer szemléltetése érdekében bemutatjuk néhány klaszter közötti távolság kiszámítását:

d({3,6,4},{1})=(0,22+0,37+0,23)/(3*1)

=0,28

d({2,5},{1})=(0,2357+0,3421)/(2*1)

=0,2889

d({3,6,4},{2,5})=(0,15+0,28+0,25+0,39+0,20+0,29)/(3*2)

=0,26

Mivel a d({3,6,4},{2,5}) távolság kisebb, mint a d({3,6,4},{1}) és a d({2,5},{1}) , ezért a {3,6,4} és a {2,5} klasztert vonjuk össze a negyedik lépésben.

Ward módszere és a centroid módszerek

A Ward módszer esetén két klaszter közelségét a klaszter-összevonásból származó négyzetes hiba növekményeként definiáljuk. Így ez a módszer ugyanazt a célfüggvényt használja, mint a K -közép módszer. Bár az említett tulajdonságok azt sugallják, hogy a Ward módszer eltér a többi hierarchikus módszertől, azonban matematikailag megmutatható, hogy ha két pont viszonyát a köztük lévő távolság négyzetével adjuk meg, a módszer a csoportátlag módszerhez hasonló.

8.7. Példa

(Ward módszer) A 8.19 a 6 pont mintaadatállományán alkalmazott Ward módszer végeredményét mutatja be. A létrejött klaszterezés különbözik az egyszerű kapcsolás, a teljes kapcsolás, illetve a csoportátlag módszerek végeredményétől.

A centroid (középpont-alapú) módszerek két klaszter viszonyát a klaszterközéppontok közötti távolság kiszámításával határozzák meg. Ezek a módszerek hasonlónak tűnhetnek a K -közép módszerhez, azonban -- ahogy azt már korábban megjegyeztük -- Ward módszere a helyes hierarchikus megfelelő.

A centroid módszernek van egy -- gyakran rossznak titulált -- tulajdonsága, amely a többi általunk tárgyalt hierarchikus módszerre nem jellemző: az inverzió lehetősége. Magyarul előfordulhat, hogy az éppen egyesített két klaszter hasonlóbb (közelebb van egymáshoz), mint az előző lépésben egyesített klaszterpár. A többi módszerben az összevonásra kijelölt klaszterek között a távolság monoton nő (vagy legrosszabb esetben nem változik) ahogy az egyelemű klaszterektől eljutunk a végső, az összes pontot tartalmazó klaszterig.

A szakaszban tárgyalt bármely klaszterviszonyra tekinthetünk úgy is, mint a Lance-Williams formula (melyet a (8.7) egyenletben mutatunk be) különböző paramétereinek megválasztására a Q és R klaszterek közötti viszony leírásához, ahol az R klaszter az A és B klaszter egyesítéséből jött létre. Ebben az egyenletben a p(⋅,⋅) a viszonyfüggvény, az m A , m B és m Q pedig a pontok száma az A , B és Q klaszterekben. Más szóval, az A és B klaszterek egyesítése után létrejövő R , és a már meglévő Q klaszter közötti viszony nem más, mint a Q és az eredeti A és B klaszterek közötti viszonyok lineáris függvénye. A 8.5. táblázat ezen együtthatók értékeit mutatja a tárgyalt módszerek esetén.

p(R,Q)= α A  p(A,Q)+ α B  p(B,Q)+β p(A,B)+γ |p(A,Q)−p(B,Q)| (8.7)

Azok a hierarchikus módszerek, amelyek leírhatóak a Lance-Williams formulával, nem követelik meg az eredeti adatpontok megtartását. Ehelyett minden klaszterezés során a viszonymátrixot (proximity matrix) frissítjük. Bár egy általános formula csábító, főleg implementációs szemszögből, azonban a különböző módszereket egyszerűbb megérteni, ha közvetlenül a klaszterek a módszerek által használt viszonyának definícióit tekintjük.

A globális célfüggvény hiánya

Korábban említettük, hogy az összevonó hierarchikus klaszterezésre nem tekinthetünk úgy, mint egy globális célfüggvény optimalizálási feladatra. Ezek a módszerek inkább különböző feltételeket alkalmaznak, hogy lokálisan döntsék el minden lépésben, mely klasztereket egyesítsék (vagy vágják szét a felosztó megközelítésben). Ez a szemlélet olyan klaszterező algoritmusokat helyez előtérbe, amelyek kerülik a nehéz kombinatorikus optimalizációs problémákat. (Megmutatható, hogy az általános klaszterezési probléma egy olyan célfüggvényre, mint például ``az SSE minimalizálása'' megvalósíthatatlan számításigényű.) Az ilyen szemléletmódoknak továbbá nincs problémájuk a lokális minimummal és nem jelent nehézséget a kezdőpontok megválasztása sem. Természetesen a O( m 2 logm) idő-, és a O( m 2 ) tárbonyolultság sok esetben korlátozó tényező.

Különböző méretű klaszterek kezelésének képessége

Az összevonó hierarchikus klaszterezés egy eddig még nem tárgyalt szempontja, hogy hogyan kezelhetőek a relatív méretek a klaszterek összevonásakor. (Ez a leírás csak azokra a klaszterviszony-típusokra alkalmazható, amelyek összegzést használnak, mint például a centroid, a Ward és a csoportátlag módszerek.) Két megközelítés létezik: a súlyozott (weighted), amely minden klasztert ugyanúgy kezel, valamint a súlyozás nélküli (unweighted), amely figyelembe veszi a klaszterekben található pontok számát. Fontos megjegyezni, hogy a súlyozott illetve súlyozás nélküli kifejezés az adatpontokra vonatkozik, és nem a klaszterekre. Más szóval, abban az esetben, ha a különböző méretű klasztereket egyenlően kezeljük, akkor a különböző klaszterek pontjai eltérő súlyt kapnak, míg a klaszterek méretének figyelembe vétele különböző klaszterekbeli pontokhoz is azonos súlyt rendel.

A jelenséget a 8.3.2. szakaszban leírt csoportátlag módszer segítségével szemléltetjük, amely egy súlyozás nélküli változata a csoportátlag módszernek. A klaszterező szakirodalomban a módszer teljes neve súlyozás nélküli pár csoport módszer számtani átlaggal (UPGMA -- Unweighted Pair Group Method using Arithmetic averages). A 8.5. táblázatban, amely megadja a formulát a klaszterek hasonlóságának frissítésére, az UPGMA együtthatói függenek mindegyik összevont klaszter méretétől: α A = m A m A + m B , α B = m B m A + m B ,β=0,γ=0 . A csoportátlag módszer súlyozott változatában (mely WPGMA-ként ismert) az együtthatók viszont konstansok: α A =1/2, α B =1/2,β=0,γ=0 . Általában elmondható, hogy a súlyozás nélküli megközelítések élveznek előnyt, kivéve ha okunk van feltételezni, hogy a pontokat súlyoznunk kell, például a különböző csoportból származó objektumokból eltérő módon vettünk mintát.

Az összevonások véglegesek

Az összevonó hierarchikus klaszterező algoritmusok hajlamosak jó lokális döntéseket hozni két klaszter egyesítéséről, mivel az összes pont páronkénti hasonlóságával kapcsolatos információt fel tudják használni. Amint azonban egy döntés megtörtént két klaszter összevonásáról, akkor azt később már nem lehet visszavonni. Ez a megközelítés megakadályozza, hogy egy lokális optimalizációs feltétel végül globális legyen. Például, bár a K -közép módszerben is alkalmazott ``négyzetes hiba minimalizálási'' kritériumot használjuk Ward módszerében annak eldöntésére, hogy mely klasztereket vonjunk össze, az egyes szintek klaszterei nem lesznek a teljes SSE lokális minimumhelyei. Valójában a klaszterek még csak nem is stabilak abban az értelemben, hogy egy pont közelebb lehet egy másik klaszter középpontjához, mint a sajátjához. Ennek ellenére a Ward módszert gyakran használják a K -közép módszer robusztus inicializálására észrevéve azt, hogy kapcsolat van a ``négyzetes hibát minimalizáló'' lokális és globális célfüggvény között.

Létezik néhány módszer, amely megpróbálja az összevonások véglegességéből eredő korlátokat felszámolni. Az egyik megközelítés a probléma orvoslására, a hierarchikus klaszterezés során létrejövő fa ágainak mozgatásával javítani a globális célfüggvényen. Egy másik megközelítés egy particionáló klaszterező módszert, például K -közép módszert, alkalmaz, hogy sok kis elemszámú klasztert állítson elő, majd ezeket a klasztereket használja a hierarchikus klaszterezés kiinduló klasztereiként.

Az egyes speciális összevonó hierarchikus klaszterező algoritmusok előnyeit és hátrányait már fentebb leírtuk. Általánosabban az ilyen típusú algoritmusokat jellemzően a háttérben lévő alkalmazás miatt használnak, ha például egy taxonómia létrehozásához hierarchiára van szükségünk. Ismertek továbbá olyan tanulmányok, amelyek azt állítják, hogy ezek az algoritmusok jobb minőségű klasztereket állítanak elő. Az összevonó hierarchikus klaszterező algoritmusok azonban számítás- és tárigényesek. Az eljárás azon tulajdonsága, hogy az összevonások visszavonhatatlanok, problémát okozhat olyan zajos, magas-dimenziójú adatok esetén, mint például a dokumentum adatok. Viszont az említett két probléma kezelhető bizonyos mértékig, ha először egy másik módszerrel, mint például a K -közép, részben klaszterezzük az adatokat.