Képesnek lenni annak megkülönböztetésére, hogy van-e az adatokban nem-véletlen szerkezet, csupán a klaszterellenőrzés egyik fontos szempontja. Az alábbiakban a klaszterellenőrzés néhány fontos kérdését soroljuk fel.

Vegyük észre, hogy az 1., 2. és 3. pont nem használ fel semmiféle külső információt -- ezek felügyelet nélküli módszerek --, míg a 4. pont külső információkat igényel. Az 5. pont elvégezhető felügyelt vagy felügyelet nélkül módon is. A 3., 4. és 5. pontok tekintetében egy további különbséget tehetünk: a teljes klaszterezést vagy az egyes klasztereket szeretnénk értékelni?

Bár lehetséges különféle számszerű mértékek alkotása a klaszter érvényesség fent említett különböző szempontjainak mérésére, számos kihívás van. Először is, elég korlátozott lehet egy klaszter érvényességi mérték alkalmazhatósága. A klaszterezhetőség mértékeivel kapcsolatos legtöbb munka például két- vagy háromdimenziós térbeli adatokra irányult. Másodszor, bármiféle mérőszám értelmezéséhez egy keretrendszer szükséges. Ha a 10 értéket kapjuk egy azt értékelő mérték esetén, hogy milyen jól illeszkednek klasztercímkék külsőleg biztosított osztálycímkékre, akkor ez az érték jó, elfogadható vagy rossz illeszkedést jelent? Az illeszkedés jósága gyakran mérhető ezen érték statisztikai eloszlásának vizsgálata révén, azaz azáltal, hogy mennyire valószínű az, hogy az érték véletlenül fordul elő. Végül, ha túl bonyolult egy mérték alkalmazása vagy megértése, csak kevesen fogják használni.

Hagyományosan a következő három típusba sorolják azokat a kiértékelési mértékeket vagy indexeket, amelyeket a klaszter érvényesség különféle szempontjainak értékelésére alkalmaznak.

Felügyelet nélküli

Egy klaszterezési szerkezet jóságát méri külső információk felhasználása nélkül. Ennek egy példája az SSE. A klaszter érvényesség felügyelet nélküli mértékeit gyakran két további osztályra bontják: a klaszter kohézió (cluster cohesion) (tömörség, szorosság) mértékei, melyek azt határozzák meg, hogy milyen szorosan kapcsolódnak az objektumok egy klaszterben, valamint a klaszter elkülönülés (cluster separation) (izoláció) mértékei, melyek azt határozzák meg, hogy egy klaszter mennyire elhatárolható vagy jól elkülönülő a többi klasztertől. A felügyelet nélküli mértékeket gyakran belső indexeknek (internal indices) hívják, mivel csak olyan információkat használnak fel, amelyek az adathalmazban találhatóak.

Felügyelt

Annak fokát méri, hogy a klaszterező algoritmus által feltárt klaszterezési szerkezet mennyire illeszkedik valamilyen külső szerkezetre. A felügyelt indexek egy példája az entrópia, amely azt méri, hogy milyen jól illeszkednek a klasztercímkék külsőleg adott osztálycímkékre. A felügyelt mértékeket gyakran külső indexeknek (external indices) nevezik, mert olyan információkat használnak fel, amelyek nem az adathalmaz részét alkotják.

Relatív

ülönböző klaszterezéseket vagy klasztereket hasonlít össze. Egy relatív klaszter kiértékelési mérték egy olyan felügyelt vagy felügyelet nélküli kiértékelési mérték, amely összehasonlítási célra szolgál. A relatív mértékek tehát valójában nem a klaszter kiértékelési mértékek egy külön típusát képviselik, hanem inkább ilyen mértékek egy speciális felhasználást jelentik. Például két K -közép klaszterezést összehasonlíthatunk az SSE vagy az entrópia segítségével is.

A szakasz hátralevő részében a klaszter érvényesség konkrét részleteit adjuk meg. Először a felügyelet nélküli klaszter kiértékeléshez kapcsolódó témákat írunk le, (1) a klaszterek kohézióján és elkülönülésén alapuló mértékekkel és (2) két, a szomszédsági mátrixon alapuló módszerrel kezdve. Mivel ezek a módszerek csak felosztó klaszterező módszerek által létrehozott klaszterhalmazok esetén hasznosak, leírjuk a népszerű kofenetikus korrelációs együtthatót is, amely egy hierarchikus klaszterezés felügyelet nélküli kiértékelésére használható. A felügyelet nélküli kiértékelés tárgyalását a helyes klaszterszám meghatározásáról és a klaszterezhetőség kiértékeléséről szóló rövid fejtegetéssel zárjuk. Ezt követően a klaszter érvényesség felügyelt megközelítéseit tekintjük, mint például az entrópia, a tisztaság és a Jaccard-mérték. A szakaszt egy arról szóló rövid tárgyalással zárjuk, hogy miként értelmezhetőek a (felügyelt és felügyelet nélküli) érvényességi mértékek értékei.

A klaszter érvényesség sok belső mértéke, amelyeket a felosztó klaszterező sémákhoz használnak, épül a kohézió és elkülönülés fogalmára. Ebben a szakaszban a prototípus- és gráf-alapú klaszterező módszerek érvényességi mértékeit használjuk ezen fogalmak bizonyos mélységű vizsgálatára. Ennek során néhány érdekes összefüggést is látni fogunk a prototípus- és a gráf-alapú klaszterezés között.

Általánosan, K számú klaszter egy halmazának teljes érvényességét kifejezhetjük az egyes klaszterek érvényességének súlyozott összegeként:

teljes érvényesség= ∑ i=1 K w i  érvényesség( C i ). (8.8)

Az érvényesség függvény lehet kohézió, elkülönülés, vagy ezen mennyiségek valamilyen kombinációja. A súlyok a klaszter érvényességi mértéktől függően változnak. Néhány esetben a súlyok értéke egyszerűen 1 vagy a klaszterméret, míg más esetekben a súlyok egy bonyolultabb tulajdonságot tükröznek, mint például a kohézió négyzetgyöke. (Lásd a 8.6. táblázatot.) Ha az érvényességi függvény a kohézió, akkor a nagyobb értékek jobbak, ha az elkülönülés, akkor pedig a kisebbek.

A kohézió és elkülönülés gráf-alapú szemlélete

Gráf-alapú klaszterek esetén egy klaszter kohéziója definiálható a szomszédsági gráf azon éleihez tartozó súlyok összegeként, amelyek a klaszteren belül kötnek össze pontokat. (Lásd a 8.27. (a) ábrát.) (Emlékezzünk arra, hogy a szomszédsági gráf csúcsai adatobjektumok, minden adatobjektum-pár között egy él van, és minden élhez egy súly tartozik, amely az él által összekötött két adatobjektum közötti közelség.) Két klaszter közötti elkülönülés hasonlóan mérhető az egyik klaszter pontjaiból a másik klaszter pontjaiba vezető élek súlyainak összegeként. (Ezt a 8.27. (b) ábra szemlélteti.)

Egy gráf-alapú klaszter kohéziója és elkülönülése matematikailag a (8.9) és (8.10) egyenletek segítségével fejezhető ki. A közelség függvény lehet egy hasonlóság, egy különbözőség, vagy ezek egy egyszerű függvénye.

kohézió( C i )= ∑ x∈ C i y∈Ci közelség(x,y) (8.9)

elkülönülés( C i , C j )= ∑ x∈ C i y∈ C j közelség(x,y) (8.10)

A kohézió és elkülönülés prototípus-alapú nézete

A prototípus-alapú klaszterek esetén egy klaszter kohéziója a prototípushoz (középponthoz vagy medoidhoz) viszonyított közelségek összegeként definiálható. Két klaszter elkülönülése hasonlóan mérhető a két klaszter közelségével. A 8.28. ábra szemlélteti ezt, ahol a ``+'' szimbólum egy klaszter középpontját jelzi.

Egy prototípus-alapú klaszter kohézióját a (8.11) egyenlet adja meg, míg az elkülönülés két mértékét a (8.12) és a (8.13) egyenlet, ahol c i a C i klaszter prototípusa (középpontja), c pedig a teljes adathalmaz prototípusa (középpontja). Két elkülönülési mérték van, mivel -- mint ezt rövidesen látni fogjuk -- a klaszter prototípusok elkülönülése az abszolút prototípustól néha közvetlenül összefügg a klaszter prototípusok egymástól való elkülönülésével. Megjegyezzük, hogy (8.9) egyenlet a klaszter négyzetes hibaösszege (SSE), amennyiben közelségi függvénynek a négyzetes euklideszi távolságot választjuk.

kohézió( C i )= ∑ x∈ C i közelség(x, c i ) (8.11)

elkülönülés( C i , C j )=közelség( c i , c j ) (8.12)

elkülönülés( C i )=közelség( c i ,c) (8.13)

A kohézió és az elkülönülés teljes mértéke

A klaszter kohézió és elkülönülés előbbi definíciói a klaszter érvényesség egyszerű és jól meghatározott mértékeit adják, melyeket a klaszter érvényesség egy teljes mértékévé kombinálhatunk egy súlyozott összeg használata révén, ahogyan ezt a (8.8) egyenlet mutatja. El kell döntenünk azonban, hogy milyen súlyokat használjunk. Nem meglepő, hogy a használt súlyok széles tartományban változhatnak, bár tipikusan a klaszterméret valamilyen mérőszámai.

A 8.6. táblázat a kohézión és elkülönülésen alapuló érvényességi mértékekre ad példákat. Az ℐ 1 a kohézió egy olyan mértéke, amely a klaszter objektumainak páronkénti közelsége és a klaszterméret hányadosával van kifejezve. Az ℐ 2 pedig a kohézió egy olyan mértéke, mely a klaszter objektumainak a klaszter középpontjához vett közelségei összegén alapul. Az ℰ 1 az elkülönülés egy olyan mértéke, melyet úgy definiálunk, hogy a klaszterközéppont a teljes középponthoz vett közelségét megszorozzuk a klaszter objektumainak számával. A G 1 , mely egy kohézión és elkülönülésen is alapuló mérték, a klaszterbe tartozó összes objektum és a klaszteren kívüli összes objektum páronkénti közelségének összege -- a szomszédsági gráf éleihez tartozó súlyok összege, amely gráfot szét kell vágni, hogy a szóban forgó klaszter elkülönüljön az összes többitől -- a klaszteren belüli objektumok páronkénti közelségének összegével osztva.

Megjegyezzük, hogy bármely felügyelet nélküli klaszter érvényességi mérték potenciális célfüggvényként alkalmazható egy klaszterező algoritmushoz, és viszont. A CLUstering TOolkit (CLUTO) (lásd az irodalmi megjegyzéseket) a 8.6. táblázatban leírt klaszter kiértékelési mértékeket használja a klaszterező eljárás működtetéséhez, valamint néhány további mértéket is használ, amelyek itt nem kerülnek említésre. Egy olyan algoritmus segítségével hajtja ezt végre, amely hasonló a 8.2.2. szakaszban tárgyalt K -közép algoritmushoz. Egészen pontosan minden pontot ahhoz a klaszterhez rendel hozzá, amelyik a legjobb értéket szolgáltatja a klaszter kiértékelési függvényhez. Az ℐ 2 klaszter kiértékelési mérték a hagyományos K -közép módszernek felel meg, és jó SSE értékekkel rendelkező klasztereket állít elő. A többi mérték kevésbé jó klasztereket állít elő az SSE szempontjából, amelyek azonban optimálisabbak az adott klaszter érvényességi mérték szempontjából.

A prototípus-alapú kohézió és gráf-alapú kohézió közötti kapcsolat

Bár eltérőnek látszanak az egy klaszter kohéziójának és elkülönülésének mérésére szolgáló gráf-alapú és prototípus-alapú megközelítések, néhány közelségi mérték esetén ekvivalensek. Megmutatható például az SSE és euklideszi térbeli pontok esetén (lásd a (8.14) egyenletet), hogy egy klaszter pontjai közötti átlagos páronkénti távolság ekvivalens a klaszter SSE értékével. (Lásd a 27. feladatot az 585. oldalon.)

Klaszter SSE= ∑ x∈ C i d ( c i ,x) 2 = 1 2 m i ∑ x∈ C i ∑ y∈ C i d (x,y) 2 (8.14)

A prototípus-alapú elkülönülés két szemlélete

Amennyiben a közelséget euklideszi távolsággal mérjük, akkor a klaszterek közötti elkülönülés hagyományos mértéke a csoportok közötti négyzetösszeg (SSB -- between group sum of squares), amely egy c i klaszterközéppont négyzetes távolságainak az összege az összes adatpont c teljes átlagától. Az SSB-t az összes klaszterre összegezve kapjuk a teljes SSB-t, amelyet a (8.15) egyenlet ad meg, ahol c i az i -edik klaszter átlaga, c pedig a teljes átlag. Minél nagyobb egy klaszterezés esetén a teljes SSB, annál elkülönültebbek egymástól a klaszterek.

Teljes SSB= ∑ i=1 K m i d ( c i ,c) 2 (8.15)

Egyszerű megmutatni, hogy a teljes SSB közvetlenül összefügg a középpontok közötti páronkénti távolságokkal. Különösen akkor, ha a klaszterek egyenlő nagyságúak, azaz m i =m/K . Ekkor ez kapcsolat a (8.16) egyenlet által adott egyszerű formát ölti. (Lásd a 28. feladatot az 585. oldalon.) Ez a típusú ekvivalencia indokolja a prototípus elkülönülés definícióját a (8.12) és a (8.13) egyenleteket illetően.

Teljes SSB= 1 2K ∑ i=1 K ∑ j=1 K m K d ( c i , c j ) 2 (8.16)

A kohézió és elkülönülés közötti kapcsolat

Néhány esetben a kohézió és az elkülönülés között is erős kapcsolat van. Pontosabban, megmutatható, hogy a teljes SSE és a teljes SSB összege konstans, azaz egyenlő a teljes négyzetösszeggel (TSS -- total sum of squares), amely az egyes pontok az adatok teljes átlagtól vett távolságának négyzetösszege. Ennek az eredménynek az a fontossága, hogy a SSE (kohézió) minimalizálása ekvivalens az SSB (elkülönülés) maximalizálásával.

Ezen tény bizonyítását adjuk alább, mivel a megközelítés olyan módszereket is bemutat, amelyek alkalmazhatóak az utolsó két szakaszban meghatározott kapcsolatok igazolására is. A jelölés egyszerűsítésének érdekében feltesszük, hogy az adatok egydimenziósak, azaz d(x,y)= (x−y) 2 . Azt a tényt is felhasználjuk, hogy a ∑ i=1 K ∑ x∈ C i (x− c i )(c− c i ) keresztszorzat 0. (Lásd a 29. feladatot az 585. oldalon.)

TSS= ∑ i=1 K ∑ x∈ C i (x−c) 2

= ∑ i=1 K ∑ x∈ C i ((x− c i )−(c− c i )) 2

= ∑ i=1 K ∑ x∈ C i (x− c i ) 2 −2 ∑ i=1 K ∑ x∈ C i (x− c i )(c− c i )+ ∑ i=1 K ∑ x∈ C i (c− c i ) 2

= ∑ i=1 K ∑ x∈ C i (x− c i ) 2 + ∑ i=1 K ∑ x∈ C i (c− c i ) 2

= ∑ i=1 K ∑ x∈ C i (x− c i ) 2 + ∑ i=1 K | C i | (c− c i ) 2

=SSE+SSB

Egyéni klaszterek és objektumok kiértékelése

Eddig a kohézió és elkülönülés klaszterek egy csoportjának teljes kiértékeléséhez való felhasználására koncentráltunk. Ezen klaszter érvényességi mértékek közül számos használható egyéni klaszterek és objektumok kiértékelésére is. Rangsorolhatunk például klasztereket valamely klaszter érvényességi értékük, azaz a klaszter kohézió vagy elkülönülés szerint. Egy nagy kohéziójú klasztert jobbnak tekinthetünk, mint egy kisebb kohéziójút. Ez az információ gyakran felhasználható a klaszterezés minőségének javítására. Ha például egy klaszter nem erősen összetartozó, akkor esetleg több alklaszterre kívánjuk szétvágni. Ugyanakkor, ha két klaszter viszonylag összetartozó, akkor esetleg egyetlen klaszterbe kívánjuk összeolvasztani őket.

Egy klaszteren belüli objektumokat értékelhetünk a klaszter teljes kohéziójához vagy elkülönüléséhez való hozzájárulásuk szempontjából is. Azok az objektumok, melyek nagyobb mértékben járulnak a kohézióhoz és az elkülönüléshez, a klaszter ``belsejének'' közelében vannak. Azok az objektumok, melyekre ennek ellenkezője igaz, valószínűleg a klaszter ``szélének'' közelében vannak. A következő szakaszban egy olyan klaszter kiértékelési mértéket tekintünk, amely egy, a fenti meggondolásokra épülő megközelítést használ pontok, klaszterek és teljes klaszterhalmazok kiértékelésére.

A sziluett együttható

A népszerű sziluett együttható a kohéziót és elkülönülést kombinálja. A következő lépések magyarázzák el a sziluett együttható kiszámításának módját egy egyedi pontra, amely folyamat a következő három lépésből áll. Távolságokat használunk, de egy hasonló megközelítés használható hasonlóságokra.

A sziluett együttható értéke −1 és 1 között változhat. A negatív eset nemkívánatos, mivel ez egy olyan esetnek felel meg, amelyben a i , a klaszter pontjaitól vett átlagos távolság, nagyobb b i -nél, egy másik klaszter pontjaitól vett legkisebb átlagos távolságnál. Azt szeretnénk, hogy a sziluett együttható pozitív legyen ( a i ≤ b i ), a i pedig a lehető legközelebb legyen 0 -hoz, mivel az együttható akkor veszi fel maximális 1 értékét, ha a i =0 .

Egy klaszter átlagos sziluett együtthatóját kiszámíthatjuk úgy, hogy egyszerűen a klaszterhez tartozó pontok sziluett együtthatóinak átlagát vesszük. Egy klaszterezés teljes jóságának mértékét megkaphatjuk az összes pont sziluett együtthatója átlagának kiszámításával.

8.8. Példa

(Sziluett együttható) A 8.29. ábrán tíz klaszter pontjai sziluett együtthatóinak ábrázolása látható. A sötétebb árnyalatok kisebb sziluett együtthatókat jeleznek.

Ebben a szakaszban két olyan, a klaszter érvényesség értékelésére szolgáló felügyelet nélküli megközelítést vizsgálunk, amelyek a szomszédsági mátrixra épülnek. Az első egy valós és idealizált szomszédsági mátrixot hasonlít össze, míg a második vizualizációt használ.

Klaszter érvényesség mérése korreláción keresztül

Amennyiben adott egy adathalmaz hasonlósági mátrixa és adottak az adathalmaz egy klaszteranalíziséből származó klasztercímkék, akkor kiértékelhetjük a klaszterezés ``jóságát'' megvizsgálva a hasonlósági mátrix és annak egy, a klasztercímkéken alapuló ideális változata közötti korrelációt. (Kisebb változtatásokkal az alábbiak a szomszédsági mátrixokra is vonatkoznak, de az egyszerűség kedvéért csak a hasonlósági mátrixokat tárgyaljuk.) Pontosabban, ideális klaszter egy olyan, amely pontjainak 1 a hasonlósága minden klaszterbeli ponthoz, és 0 minden más klaszterbeli ponthoz. Ha tehát úgy rendezzük a hasonlósági mátrix sorait és oszlopait, hogy az ugyanahhoz az osztályhoz tartozó objektumok egymáshoz közel helyezkednek el, akkor az ideális hasonlósági mátrix blokkdiagonális (block diagonal) felépítésű. Más szóval, a hasonlóság nem nulla (azaz 1) a hasonlósági mátrix azon blokkjain belül, melyek elemei klaszteren belüli hasonlóságot jelentenek, máshol pedig 0. Az ideális hasonlósági mátrixot úgy hozzuk létre, hogy egy olyan mátrixot alkotunk, amely minden adatponthoz egy sort és egy oszlopot tartalmaz -- egy tényleges hasonlósági mátrixhoz hasonlóan --, és 1 értéket rendelünk egy elemhez akkor, ha a hozzá tartozó pontpár ugyanahhoz a klaszterhez tartozik. Az összes többi elem pedig 0 lesz.

Az ideális és a tényleges hasonlósági mátrix közötti magas korreláció azt jelzi, hogy az ugyanabba a klaszterbe tartozó pontok közel vannak egymáshoz, míg az alacsony korreláció ennek ellenkezőjét. (Mivel a tényleges és az ideális hasonlósági mátrix szimmetrikus, a korrelációt csak a mátrixok főátlója alatti vagy feletti n(n−1)/2 elem között számítjuk.) Következésképpen ez nem egy jó mérték sok sűrűség- vagy szomszédság-alapú klaszterhez, mivel ezek nem gömb alakúak és szorosan összefonódhatnak más klaszterekkel.

8.9. Példa

(Tényleges és ideális hasonlósági mátrixok korrelációja) A mérték szemléltetésére kiszámoltuk a tényleges és ideális hasonlósági mátrixok közötti korrelációt a 8.26. (c) ábrán látható (véletlen adatokból származó) és a 8.30. (a) ábrán látható (három jól elkülönülő) K -közép klaszterre. A korreláció értéke megfelelő sorrendben 0,5810 és 0,9235, amely azt az eredményekkel kapcsolatos elvárást tükrözi, miszerint a K -közép által a véletlenszerű adatokban talált klaszterek rosszabbak a jól elkülönülő klasztereket tartalmazó adatokban találtaknál.

Klaszterezés megítélése vizuálisan a hasonlósági mátrixa alapján

Az előző módszer egy általánosabb, minőségi megközelítést sugall klaszterek egy halmazának megítélésére: rendezzük a hasonlósági mátrixot a klasztercímkék szerint, majd ábrázoljuk. Elméletileg, ha jól elkülönülő klasztereink vannak, akkor a hasonlósági mátrix nagyjából blokkdiagonális kell hogy legyen. Ha nem ez a helyzet, akkor a hasonlósági mátrixban látható mintázatok klaszterek közötti összefüggéseket fedhetnek fel. Mindez ismét alkalmazható különbözőségi mátrixokra is, de az egyszerűség kedvéért csak a hasonlósági mátrixokat tárgyaljuk.

8.10. Példa

(A hasonlósági mátrix megjelenítése) Tekintsük a 8.30. (a) ábra pontjait, amelyek három, jól elkülönülő klasztert alkotnak. Ha a K -közép módszert használjuk a pontok három klaszterbe sorolására, akkor nem okoz gondot ezen klaszterek megtalálása, mivel jól elkülönülnek. Ezen klaszterek elkülönülését ábrázolja az átrendezett hasonlósági mátrix révén a 8.30. (b) ábra. (Az egységesség érdekében a távolságokat hasonlóságokká transzformáltuk az s=1−(d−mind)/(maxd−mind) formula segítségével.) A 8.31. ábra mutatja a DBSCAN, a K -közép és a teljes kapcsolás által a 8.26. ábrán látható véletlen adatokban talált klaszterek átrendezett hasonlósági mátrixát.

A 8.30. ábra jól elkülönülő klaszterei nagyon erős blokkdiagonális mintázatot mutatnak az átrendezett hasonlósági mátrixban. Gyenge blokkdiagonális mintázatok is vannak azonban (lásd a 8.31. ábrát) a véletlenszerű adatokban a K -közép, a DBSCAN és a teljes kapcsolás által talált klaszterezések átrendezett hasonlósági mátrixaiban. Ugyanúgy, ahogy az ember is képes alakzatokat találni a felhőkben, az adatbányászati algoritmusok is képesek klasztereket találni véletlenszerű adatokban. Míg szórakoztató mintázatokat keresni a felhőkben, értelmetlen és talán kellemetlen zajban klasztereket keresni.

Ez a módszer reménytelenül költségesnek tűnhet nagy adathalmazokra, mivel a szomszédsági mátrix kiszámítása O( m 2 ) időt vesz igénybe, ahol m az objektumok száma, de az eljárást még így is alkalmazni lehet mintavételezéssel. Mintát vehetünk minden klaszter adatpontjaiból, kiszámíthatjuk közöttük a hasonlóságot, majd ábrázolhatjuk az eredményt. Szükséges lehet a kis klaszterek túlmintavételezése és a nagy klaszterek alulmintavételezése, hogy az összes klaszter megfelelő reprezentációját kapjuk.

Az előző klaszter kiértékelési megközelítéseket a felosztó klaszterezésekhez szánják. Itt a kofenetikus korrelációt (cophenetic correlation) tárgyaljuk, amely egy népszerű mérték hierarchikus klaszterezések kiértékelésére. Két objektum közötti kofenetikus távolság (cophenetic distance) az a közelség, amelynél egy összevonó hierarchikus klaszterező módszer már az első alkalommal ugyanabba a klaszterbe sorolja a szóban forgó objektumokat. Ha például az agglomeratív hierarchikus klaszterezési folyamat egy bizonyos pontján egybeolvasztott két klaszter közötti legkisebb távolság 0,1 , akkor az egyik klaszter minden pontjának 0,1 a kofenetikus távolsága a másik klaszter pontjaira nézve. Egy kofenetikus távolságmátrix elemei az objektumpárok közötti kofenetikus távolságok. A kofenetikus távolságok különbözőek egy ponthalmaz minden hierarchikus klaszterezése esetén.

8.11. Példa

(Kofenetikus távolságmátrix) A 8.7. táblázat a 8.16. ábrán látható egyszerű kapcsolású klaszterezés kofenetikus távolságmátrixát tartalmazza. (Az ábrához tartozó adatok a 8.3. táblázatban adott 6 kétdimenziós pontból állnak.)

A kofenetikus korrelációs együttható (CPCC -- CoPhenetic Correlation Coefficient) a fenti mátrix és az eredeti különbözőségi mátrix elemei közötti korreláció, és egy standard mértéke annak, hogy milyen jól illeszkedik az adatokra egy (bizonyos típusú) hierarchikus klaszterezés. Ezen mérték leggyakoribb felhasználásainak egyike annak megállapítása, hogy mely típusú hierarchikus klaszterezés a legmegfelelőbb adott típusú adatokra.

8.12. Példa

(Kofenetikus korrelációs együttható) A CPCC értékeket a 8.16-8.19. ábrákon látható hierarchikus klaszterezésekre számítottuk ki. Az értékeket a 8.8. táblázatban tüntettük fel. Az egyszerű kapcsolású módszer által előállított hierarchikus klaszterezés látszólag kevésbé jól illeszkedik az adatokra, mint a teljes kapcsolás, a csoportátlag és a Ward módszer által előállított klaszterezések.

Különféle felügyelet nélküli klaszter kiértékelési mértékek használhatóak a klaszterek helyes vagy természetes számának hozzávetőleges meghatározására.

8.13. Példa

(A klaszterek száma) A 8.29. ábrán látható adathalmaz 10 természetes klasztert tartalmaz. A 8.32. ábrán az adathalmaz (kettéosztó) K -közép klaszterezésének SSE értéke látható a klaszterek számának függvényében, a 8.33. ábra pedig a sziluett együttható átlagos értékét mutatja, ugyancsak a klaszterszám függvényében. A SSE grafikonján egy jól látható hajlat, a sziluett együttható grafikonján pedig egy jól látható csúcs van, ha a klaszterek száma 10.

Megpróbálhatjuk tehát úgy meghatározni a klaszterek természetes számát az adathalmazban, hogy megkeressük azt a klaszterszámot, amelynél egy hajlat, csúcs vagy mélyedés van a kiértékelési mérték grafikonján, amikor azt a klaszterszám függvényében ábrázoljuk. Természetesen nem minden esetben működik jól egy ilyen megközelítés. A klaszterek összefonódottabbak vagy átfedőbbek lehetnek, mint a 8.29. ábrán láthatóak. Az adatok egymásba ágyazott klaszterekből is állhatnak. A 8.29. ábrán látható klaszterek valójában egy kissé egymásba ágyazottak, azaz 5 klaszterpár van, mivel a klaszterek felülről lefelé közelebb vannak egymáshoz, mint balról jobbra. Az SSE görbén ezt egy hajlat jelzi, de a sziluett együttható görbéje nem ilyen tiszta. Összességében elmondhatjuk, hogy bár óvatosnak kell lennünk, a leírt módszer betekintést nyújthat a klaszterek számáról az adatokban.

Az egyik nyilvánvaló mód annak meghatározására, hogy egy adathalmaz tartalmaz-e klasztereket, az, hogy megpróbáljuk klaszterezni. Azonban majdnem minden klaszterező algoritmus kötelességtudóan klasztereket fog találni, amikor adatokat kap. A probléma kezelésére megvizsgálhatjuk a létrejövő klasztereket, és csak akkor jelentjük ki, hogy az adathalmaz klasztereket tartalmaz, ha legalább néhány klaszter jó minőségű. Ez a megközelítés azonban figyelmen kívül hagyja azt a tényt, hogy az adatok klaszterei más típusúak is lehetnek, mint a klaszterező eljárás által keresettek. Ezt a további problémát kezelhetjük azáltal, hogy több algoritmust használunk és ismét kiértékeljük az eredményül kapott klasztereket. Ha a klaszterek egységesen rossz minőségűek, akkor az valóban azt jelezheti, hogy nincsenek is klaszterek az adatokban.

Vagylagosan, és erre összpontosítanak a klaszterezhetőség mértékei, klaszterezés nélkül is megpróbálhatjuk kiértékelni, hogy az adathalmazban vannak-e klaszterek. A leggyakoribb megközelítés, különösen az euklideszi térben lévő adatokra, az adatok térbeli véletlenszerűségére vonatkozó statisztikai próbák használata. Nagy kihívást jelent sajnos a helyes modell kiválasztása, a paraméterek becslése, és annak a hipotézisnek a statisztikai szignifikanciájának értékelése, hogy az adatok nem véletlenszerűek. Mindazonáltal számos megközelítést fejlesztettek ki, többségüket alacsony dimenziójú euklideszi térbeli pontokra.

8.14. Példa

(Hopkins statisztika) Ehhez a megközelítéshez p számú pontot generálunk, amelyek véletlenszerűen oszlanak el az adattérben, és szintén p pontot mintavételezünk a tényleges adatpontokból. Mindkét ponthalmaz pontjaira meghatározzuk az eredeti ponthalmazban található legközelebbi szomszédtól mért távolságokat. Jelölje u i a mesterségesen generált pontok legközelebbi szomszéd távolságait, w i pedig az eredeti adathalmazból származó mintapontok legközelebbi szomszéd távolságait. A H Hopkins statisztikát ekkor a (8.17) egyenlet definiálja:

H= ∑ i=1 p w i ∑ i=1 p u i + ∑ i=1 p w i . (8.17)

Ha a véletlenszerűen generált pontoknak és az adatokból vett mintapontoknak nagyjából ugyanazok a legközelebbi szomszéd távolságaik, akkor H értéke 0,5 -hez közeli lesz. A 0-hoz és 1-hez közeli H értékek azt jelzik, hogy az adatok erősen klaszterekbe tömörülnek, illetve hogy az adattérben szabályosan oszlanak el. Például a 8.26. ábra adataira 100 alkalommal p=20 esetén számítottunk ki a Hopkins statisztikát. H átlagos értéke 0,56 volt 0,03 szórással. Ugyanezt a kísérletet végeztük el fig:well_separated_sim. ábra jól elkülönülő pontjaira. Az átlagos H érték 0,95 volt 0,006 szórással.

Amikor az adatokról rendelkezésünkre áll külső információ, az tipikusan az adatobjektumokhoz tartozó külsőleg meghatározott osztálycímkék képében adott. Ilyen esetekben a szokásos eljárás az, hogy megmérjük a megfelelés fokát a klaszter- illetve az osztálycímkék között. De miért is fontos ez? Elvégre ha ismerjük az osztálycímkéket, akkor mi értelme van a klaszteranalízis elvégzésének? Egy ilyen analízis indítéka a klaszterező módszerek összevetése az ``alapigazsággal'', vagy annak megállapítása, hogy egy manuális osztályozási folyamat milyen mértékben automatizálható klaszteranalízis révén.

Két eltérő szemléletet mutatunk be. A módszerek első halmaza osztályozási mértékeket használ, mint az entrópia, a tisztaság és az F -mérték. Ezek a mérőszámok azt értékelik, hogy egy klaszter milyen mértékben tartalmaz egyetlen osztályból származó objektumokat. A módszerek második csoportja a bináris adatok hasonlósági mértékeihez kapcsolódik, mint például DataChapter. fejezetben látott Jaccard mérték. Ezek a megközelítések azt mérik, hogy milyen mértékben tartozik ugyanabba a klaszterbe két, ugyanabból az osztályból származó objektum, és fordítva. Kényelmi okokból a mértékek ezen két típusára osztályozás-orientált (classification-oriented) illetve hasonlóság-orientált (similarity-oriented) néven hivatkozunk.

A klaszterérvényesség osztályozás-orientált mértékei

Számos mérőszám létezik -- entrópia, tisztaság, pontosság, felidézés és az F -mérték -- amelyet széles körben használnak osztályozó modellek teljesítményének kiértékelésére. Osztályozás esetében azt mérjük, hogy az előrejelzett osztálycímkék milyen mértékben felelnek meg a valódi osztálycímkéknek. A fent említett mértékek esetében azonban semmilyen alapvető változás nem történik, ha klasztercímkéket használunk az előrejelzett osztálycímkék helyett. A következőkben röviden áttekinjük ezen mérőszámok definícióit, amelyeket a 4. fejezetben tárgyaltunk.

Entrópia: Azt méri, hogy az egyes klaszterek milyen mértékben állnak egyetlen osztály objektumaiból. Először minden klaszterre kiszámítjuk az adatok osztályeloszlását, azaz az i -edik klaszterre kiszámoljuk annak p ij valószínűségét, hogy az i -edik klaszter egy eleme a j -edik osztályba tartozik, ez p ij = m ij / m i , ahol m i az i -edik klaszter objektumainak száma, m ij pedig a j -edik osztály objektumainak száma az i -edik klaszterben. Ezt az osztályeloszlást felhasználva minden i -edik klaszter entrópiáját a szabványos formula segítségével számítjuk ki, azaz e i =− ∑ j=1 L p ij log 2 p ij , ahol L az osztályok száma. Egy klaszterhalmaz teljes entrópiáját az egyes klaszterek entrópiáinak a klaszterek méreteivel súlyozott összegeként kapjuk meg, azaz e= ∑ i=1 K m i m e i , ahol K a klaszterek száma, m pedig az adatpontok száma.

Tisztaság: Egy másik mérőszáma annak, hogy egy klaszter milyen mértékben tartalmaz egyetlen osztályból objektumokat. Az előző terminológia felhasználásával az i -edik klaszter tisztasága p i = max j p ij , egy klaszterezés teljes tisztasága pedig tisztaság= ∑ i=1 K m i m p i .

Precizitás:Egy klaszter azon hányada, amely egy adott osztály objektumaiból áll. Az i -edik klaszter precizitása a j -edik osztályra nézve precizitás(i,j)= p ij .

Felidézés:Annak mérőszáma, hogy egy klaszter milyen mértékben tartalmazza egy meghatározott osztály összes elemét. Az i -edik klaszter felidézése a j -edik osztályra nézve felidézés(i,j)= m ij / m j , ahol m j az objektumok száma a j -edik osztályban.

F-mérték: A pontosság és a felidézés egy kombinációja, amely annak mérőszáma, hogy egy klaszter milyen mértékben tartalmazza csak egy meghatározott osztály objektumait és ennek az osztálynak az összes elemét. Az i -edik klaszter F -mértéke a j -edik osztályra nézve F(i,j)=(2×precizitás(i,j)×felidézés(i,j))/(precizitás(i,j)+felidézés(i,j)) .

8.15. Példa

(Felügyelt kiértékelési mértékek) Egy példát mutatunk be ezen mérőszámok szemléltetésére. Nevezetesen a K -közép módszert használjuk a koszinusz hasonlósági mértékkel a Los Angeles Times 3204 újságcikkének klaszterezésére. Ezek a cikkek 6 különböző osztályból származnak: Szórakozás, Pénzügy, Külügy, Helyi hírek, Belföld és Sport. A 8.9. táblázatban foglaltuk össze a K -közép módszer eredményeit 6 klaszter keresése esetén. Az első oszlop a klasztert jelzi, míg a következő 6 oszlop együtt alkotja a tévesztési mátrixot, azaz ezek az oszlopok jelzik, hogy az egyes kategóriák dokumentumai hogyan oszlanak el a klaszterek között. Az utolsó két oszlop a klaszterek entrópiáját és tisztaságát tartalmazza.

Ideális esetben minden klaszter csak egyetlen osztályból származó dokumentumokat tartalmaz. A valóságban minden klaszter több osztályból tartalmaz dokumentumokat. Mindazonáltal sok klaszter tartalmaz dokumentumokat elsősorban egy osztályból. Különösen a 3. klaszter, amely főleg a Sport rovatból származó dokumentumokat tartalmaz, jó kivételesen, mind a tisztaság, mind az entrópia tekintetében. A többi klaszter tisztasága és entrópiája nem olyan jó, de általában nagymértékben javítható, ha az adatokat nagyobb számú klaszterre bontjuk.

A precizitás, felidézés és F -mérték minden klaszterre kiszámítható. Hogy egy konkrét példát adjunk, tekintsük a 8.9. táblázatból az 1. klasztert és a Helyi hírek osztályt. A precizitás 506/677=0,75 , a felidézés 506/943=0,26 , így az F -mérték 0,39 . A 3. klaszter és a Sport osztály F értéke ellenben 0,94 .

A klaszter érvényesség hasonlóság-központú mértékei

Az ebben a szakaszban tárgyalt mértékek mind azon a feltevésen alapulnak, hogy ugyanabban a klaszterben lévő bármely két objektum ugyanabba az osztályba kell hogy tartozzon, és fordítva. Erre a klaszter érvényességi szemléletre úgy is tekinthetünk, mint a következő két mátrix összehasonlítására: (1) a korábban tárgyalt ideális klaszter hasonlósági mátrix, amelynek ij -edik eleme 1 akkor, ha a két objektum, i és j , ugyanabban a klaszterben helyezkedik el, 0 egyébként, és (2) az ideális osztály hasonlósági mátrix, melyet az osztálycímkékre vonatkozóan definiálunk, és melynek ij -edik eleme 1 akkor, ha a két objektum, i és j , ugyanahhoz az osztályhoz tartozik, 0 egyébként. Mint korábban is, a két mátrix korrelációját vehetjük a klaszter érvényesség mértékének. Ezt a mértéket Γ statisztikának nevezik a klaszterezés érvényesítésének szakirodalmában.

8.16. Példa

(A klaszter- és osztálymátrix közötti korreláció) Az elképzelés konkrétabb bemutatására egy öt adatpontból ( p 1 , p 2 , p 3 , p 4 , p 5 ), két klaszterből ( C 1 ={ p 1 , p 2 , p 3 } és C 2 ={ p 4 , p 5 } ) valamint két osztályból ( L 1 ={ p 1 , p 2 } és L2={ p 3 , p 4 , p 5 } ) álló példát adunk. Az ideális klaszter és osztály hasonlósági mátrixot a 8.10. és 8.11. táblázat tartalmazza. A két mátrix elemei közötti korreláció értéke 0,359 .

Általánosabban bármely a 2.4.5. szakaszban látott bináris hasonlósági mértéket használhatjuk. (A két mátrixot bináris vektorokká alakíthatjuk például a sorokat egymás után illesztve.) Megismételjük annak a négy mennyiségnek a definícióját, melyeket ezen hasonlósági mértékek definiálására használtunk, úgy módosítjuk azonban a leíró szöveget, hogy illeszkedjen a jelenlegi környezetbe. Konkrétan az alábbi négy mennyiséget kell kiszámítanunk minden eltérő objektumpár esetén. (Ha m az objektumok száma, akkor m(m−1)/2 ilyen pár van.)

f 00 = azon objektumpárok száma, amely tagjai különböző osztályból és különböző klaszterből származnak

f 01 = azon objektumpárok száma, amely tagjai különböző osztályból és azonos klaszterből származnak

f 10 = azon objektumpárok száma, amely tagjai azonos osztályból és különböző klaszterből származnak

f 11 = azon objektumpárok száma, amely tagjai azonos osztályból és azonos klaszterből származnak

Az egyszerű egyezési együttható (simple matching coefficient), amelyet Rand statisztikának hívnak ebben a szövegkörnyezetben, és a Jaccard együttható a két leggyakrabban használt klaszter érvényességi mérték:

Rand statisztika= f 00 + f 11 f 00 + f 01 + f 10 + f 11 (8.18)

Jaccard együttható= f 11 f 01 + f 10 + f 11 (8.19)

8.17. Példa

(A Rand és a Jaccard mérték) Ezen képletek alapján könnyen kiszámíthatjuk a Rand statisztika és a Jaccard együttható értékét a 8.10. és 8.11. táblázatokon alapuló példára. Megjegyezve, hogy f 00 =4 , f 01 =2 , f 10 =2 és f 11 =2 , a Rand statisztika (2+4)/10=0,6 , a Jaccard együttható pedig 2/(2+2+2)=0,33 .

Megjegyezzük továbbá, hogy a négy mennyiség, f 00 , f 01 , f 10 és f 11 , határozza meg tab:cluster_contingency. táblázatban is látható kontingenciatáblázatot.

Korábban, az asszociációs elemzéssel összefüggésben -- lásd a 6.7.1.. szakaszt -- átfogó tárgyalást adtunk az olyan asszociációs mértékekről, melyeket az ilyen típusú kontingenciatáblázathoz használhatunk. (Hasonlítsuk össze a 8.12. és a 6.7. táblázatot.) Az említett mértékek alkalmazhatóak a klaszter érvényességre is.

Klaszter érvényesség hierarchikus klaszterezésekre

A szakaszban eddig csak a felosztó klaszterezésekre vonatkozó felügyelt klaszter érvényességi mértékeket tárgyaltuk. Egy hierarchikus klaszterezés felügyelt kiértékelése több különböző okból is nehezebb, beleértve azt a tényt, hogy gyakran nem áll rendelkezésre egy már létező hierarchikus szerkezet. A továbbiakban egy példát adunk egy olyan megközelítésre, amely egy hierarchikus klaszterezést (sima) osztálycímkéket figyelembe véve értékel, melyek nagyobb valószínűséggel állnak rendelkezésre, mint meglevő hierarchikus szerkezetek.

A megközelítés lényege annak kiértékelése, hogy egy hierarchikus klaszterezés tartalmaz-e minden osztályhoz legalább egy olyan klasztert, ami viszonylag tiszta és magában foglalja az osztály objektumainak többségét. Egy hierarchikus klaszterezés ezen célnak megfelelő kiértékeléséhez minden osztályra kiszámítjuk az F -mértéket, mégpedig a klaszterhierarchia minden egyes klaszterére. Minden osztályhoz a bármely klaszterre elért legnagyobb F -mértéket vesszük. Végül egy teljes F -mértéket számolunk a hierarchikus klaszterezésre, az osztályonkénti F -mértékek súlyozott átlagának meghatározásával, ahol az osztályok mérete szolgál a súlyok alapjául. A hierarchikus F -mértéket formálisan az alábbi módon definiáljuk:

F= ∑ j m j m max i F(i,j),

ahol a maximumot minden szint minden i -edik klaszterére vesszük, m j a j -edik osztálybeli objektumok száma, m pedig az összes objektum száma.

A klaszter érvényességi mértékeknek az a célja, hogy segítsék a kapott klaszterek jóságának mérését. Valóban, a jóság mértékeként jellemzően egyetlen számot adnak. Ezután azonban szembe kell néznünk a kapott szám szignifikanciájának értelmezésével, amely feladat még nehezebb lehet.

A klaszter érvényességi mértékek legkisebb és legnagyobb értéke sok esetben útmutatást adhat. A 0 tisztaság például definíció szerint rossz, míg az 1 tisztaság jó, legalábbis akkor, ha megbízunk az osztálycímkéinkben és azt szeretnénk, hogy a klaszterszerkezet az osztályszerkezetet tükrözze. Hasonlóképpen jó a 0 entrópia, csakúgy, mint a 0 SSE érték.

Néha azonban előfordulhat, hogy nincs legkisebb vagy legnagyobb érték, vagy hogy az adatok skálája hatással van az értelmezésre. Még ha ismerjük is a legkisebb és legnagyobb értékeket a nyilvánvaló magyarázatukkal együtt, a közbülső értékeket akkor is értelmezni kell. Néhány esetben egy abszolút normát használhatunk. Ha például hasznosítási céllal klaszterezünk, akkor lehet, hogy csak egy bizonyos mértékű hibát vagyunk hajlandóak tolerálni a pontok egy klaszterközépponttal történő közelítésénél.

Ha azonban nem ez a helyzet, akkor valami mást kell tennünk. Egy gyakori megközelítés az érvényességi mérték értékének statisztikai értelmezése. Nevezetesen azt próbáljuk megítélni, hogy mennyire valószínű az, hogy a megfigyelt érték véletlenül adódhatott. Az érték akkor jó, ha szokatlan, azaz ha valószínűtlen az, hogy a véletlennek köszönhető. Az indíték ezen megközelítés mögött az, hogy csak azok a klaszterek érdekesek számunkra, amelyek nem véletlenszerű szerkezetet mutatnak az adatokban, az ilyen felépítések pedig általában nagy (kicsi) klaszter érvényességi értékeket eredményeznek, legalábbis akkor, ha az érvényességi mértékeket úgy tervezték, hogy tükrözzék az erős klaszterszerkezet jelenlétét.

8.18. Példa

(A SSE szignifikanciája) Hogy bemutassuk azt, hogy mindez hogyan működik, egy példát adunk a K -közép módszer és az SSE segítségével. Tegyük fel, hogy meg szeretnénk mérni, hogy mennyire jók a 8.30. ábra jól elkülönülő klaszterei véletlenszerű adatokhoz képest. A három klaszter pontjainak tartományán sok, 100 véletlen pontból álló halmazt generálunk, minden adathalmazban három klasztert határozunk meg a K -közép módszerrel, majd eltároljuk a klaszterezések SSE értékeinek eloszlását. A SSE értékek eloszlását felhasználva meg tudjuk becsülni az eredeti klaszterek SSE értékének valószínűségét. A 8.24. ábrán 500 véletlenszerű futás SSE értékének hisztogramját látjuk. fig:sse_hist. ábrán látható legkisebb SSE érték 0,0173 . A 8.34. ábrán látható három klaszter SSE értéke 0,0050 . Így tehát óvatosan jelenthetjük ki, hogy 1%-nál kisebb az esély arra, hogy a véletlen műve egy olyan klaszterezés, mint ami a 8.30. ábrán látható.

Befejezésképpen azt hangsúlyozuk, hogy a klaszter kiértékelés -- akár felügyelt, akár felügyelet nélküli -- több egy numerikus klaszter érvényességi mérőszám előállításánál. Hacsak nincs az értéknek egy, a mérték definícióján alapuló természetes értelmezése, nekünk kell azt valamilyen módon értelmeznünk. Ha a klaszter kiértékelési mértékünket úgy definiáltuk, hogy a kisebb értékek erősebb klasztereket jeleznek, akkor statisztika segítségével dönthetjük el, hogy a kapott érték szokatlanul kicsi-e, feltéve, hogy ismerjük a kiértékelési mérték eloszlását. Bemutattunk egy példát arra, hogy hogyan találhatunk egy ilyen eloszlást, a témában azonban jelentősen több rejlik, az Olvasó az irodalmi megjegyzésekhez fordulhat további utalásokért.

Végezetül, még ha a kiértékelési mértéket relatív mérőszámként használtuk is, azaz két klaszterezés összehasonlítására, akkor is meg kell állapítani a két klaszterezésből származó mérőszámok közötti különbség szignifikanciáját. Bár az egyik érték majdnem minden esetben nagyobb a másiknál, nehéz lehet annak megállapítása, hogy az eltérés szignifikáns-e. Megjegyezzük, hogy ennek a szignifikanciának két szempontja van: hogy az eltérés statisztikailag szignifikáns-e (megismételhető-e), és hogy az eltérés nagyságrendje jelentéssel bír-e az alkalmazás szempontjából. Sokan nem tekintenének egy 0,1%-os eltérést szignifikánsnak, még ha az következetesen reprodukálható is.