Adatelemzés és adatbányászat MSc

Adatelemzés és adatbányászat MSc 12. téma

Klaszterezési módszerek

Dr. Kovács László ME GEIAL

Klaszterezés célja Adott az objektumok, tulajdonságaik együttese. Az objektumok között hasonlóságot és különbözőséget fedezhetünk fel. A klaszterezés célja, hogy az objektumok halmazán hasonlósági objektumcsoportokat hozzunk létre: - egymáshoz hasonló elemek egy csoportba kerülnek - egymástól különböző elemek különböző csoportba kerülnek. A feladat nehézségei: - objektumok reprezentálása - a hasonlóság mérésére különböző módszerek léteznek - klaszterhatárok kialakítása nem egyértelmű - nincs egyértelmű mérőszám a csoportképzés jóságának mérésére - nagy méretű feladatok kezelésének hatékonysága alacsony


1

Klaszterezés célja Klaszterezés alkalmazási területei - vásárlók csoportosítása, tipikus viselkedési minták kialakítása - újlenyomatok rendszerbe szervezése - csalások felismerése - biometrikus adatok alapján történő azonosítás - kártyahasználat ellenőrzése - biológia, génkutatás - képfeldolgozás, képek szegmensekre bontása - földrajzi területek csoportosítása


Klaszterezés célja A klaszterezési módszerrel szembeni elvárások: - skálázhatóság, nagy méretű problémák kezelése - különböző típusú attributumok kezelése - bemenő paraméterek megadása minél kevesebb előismeretet feltételezzen - tetszőleges alakú klaszterek felismerése - zajos adatok kezelése - megszorítások figyelembe vételének támogatása - értelmezhetőség, felhasználhatóság - távolság egység invariencia - klaszter konzisztencia őrzés (Kleinberg)


2

Klaszterezési módszerek - Particonáló módszerek - K-átlag - SOM NN - Hierarchikus módszerek - HAC - DAC - Sűrűség alapú módszerek - DBSCAN - Rács alapú módszerek - STING - Modell alapú módszerek - Gauss Dr. Kovács László ME GEIAL

Klaszterezési módszerek A klaszterek távolságának mérése:

1. A két legközelebbi pont távolsága

2. A két legtávolabbi pont távolsága

3. Pontok átlagos távolsága


3

Klaszterezés ábrázolása Dendogram A hasonló objektumok szomszédok lesznek, a hasonlóság a közös pont szintjének és az alappontok szintjei közötti különbséggel mérhető. A szintek különbségével vizualizálható az eltérés mértéke


Klaszterezés ábrázolása A dendogram alkalmas arra, hogy az egyedi zajokat, kívülálló elemeket is feltárja. A térbeli elrendezés többet mutat, a dendogram kétdimenziós térben ábrázolja csak a viszonyokat.


4

HAC algoritmus HAC: hierarchikus agglomerativ klasztererzés Minden lépésben két közeli klasztert von össze egybe A leállás feltételei: - min. klaszterszám - maximális összevonási távolság Algoritmus: - minden elem egy önálló klaszter - a két legközelebbi klaszter meghatározása - a két legközelebbi klaszter összevonása egybe - a fenti eljárás folytatása, amíg a leállási feltétel ezt megengedi Fő költségelem: az összevonandó klaszterpár meghatározása monoton nő a távolság Dr. Kovács László ME GEIAL

HDC algoritmus HDC: hierarchikus szétbontó klasztererzés Minden lépésben egy klasztert két részre választ szét A leállás feltételei: - max. klaszterszám - elemi klaszterek jöttek létre Algoritmus: - minden elem egyetlen klaszterben tárolódik - azon klaszter meghatározása, amelyen belül a legnagyobb a belső válaszvonal - a kiválasztott klaszter szétválasztása - a fenti eljárás folytatása, amíg a leállási feltétel ezt megengedi Fő költségelem: a hasítandó klaszterpár meghatározása Dr. Kovács László ME GEIAL

5

Hierarchikus algoritmusok HAC klaszterezés teljes menetét jól mutatja a dendogram


Hierarchikus algoritmusok Egyszerűen követhető algoritmus Szemléletes, értelmezhető Nagy költségű alap:

Célfüggvény:

O( N 3 )

∑ ∑

c ( x1 ) = c ( x2 ) c ( x1 ) ≠ c ( x 2 )

d ( x1 , x2 ) d ( x1 , x2 )

→ min

Triviális szélső eset: klaszterszám = N Távolságok eloszlásával függ össze a jóság, relatív


6

BIRCH algoritmusok Hierarchikus algoritmus Kiegyensúlyozott hierarchiát alkot (B+ fára hasonlít) Egy elem bejegyzése: CF-node: (N, L, D) N: gyerekek 0.-momentuma, darabszáma L: gyerekek összege, 1. momentuma D: gyerekek négyzetösszege, 2. momentuma CF-fa csomópont: CF-node bejegyzések listája, minden bejegyzés mögött egy gyerek fa-csomópont Fa feléptés menete: - az elemek levitele a levélig - a levélben klaszterek képzése - ha klaszterek mérete nagyobb lenne egy küszöbnél, akkor a levelet fel kell osztani és a szülőkbe delegálni a leíró CF-node-ot Egy klaszternek Dr. Kovács László ME GEIAL

megadott méreten, kiterjedésen belül kell maradnia

BIRCH algoritmusok A belső CF-node-ok gyerek elemekre, a levél CF-node-ok adatbucketekre mutatnak

A keresésnél a klaszterek távolságán alapul az irány kijelölése: a legközelebbi CF-node felé megy tovább Minden klaszterhez tartozik maximális lefedési sugár Igen hatékony algoritmus


7

BIRCH algoritmusok


Particionáló módszerek, K-means K-means algoritmus Az elemeket közvetlenül a klaszterhez rendeljük hozzá A hozzárendelés iteratív közelítésen alapszik. Előre adott az igényelt klaszterek darabszáma (K) Algoritmus: 1. induláskor felveszünk K darab középpontot, mint klaszter középpontot 2. minden elemet hozzárendeljük a legközelebbi középponthoz 3. a kapott csoportokra kiszámítjuk az elemei átlagát 4. a klaszter középpontot az új átlagba visszük át 5. ha egyik klaszterközéppont sem mozog már, leáll az algoritmus

Egyes változatokban a közép helyett a k-medián módszert alkalmazzák Dr. Kovács László ME GEIAL

8

K-means Az induló állapot kiválasztása véletlenszerű Mind a K darabszám ,mind a pozíció tetszőleges

A középpontok vándorolnak az optimális hely felé Konvergencia figyelhető meg


K-means A konvergencia háttere Az elrendezés jóságának mérőszáma a klaszteren belüli elemek egymástól való távolságnégyzeteinek összege

Ezzel arányos a középponttól mért távolságok összege

A módszer minden lépésében csökken ezen utóbbi függvény értéke Dr. Kovács László ME GEIAL

9

K-means CLARA: A k-means algoritmus adaptálása nagy adathalmazra A módszer a teljes adatbázis helyett annak csak agy reprezentatív mintájával dolgozik A középpontok helyét a mintákból számolja ki.

K-means értékelése: - problematikus a kvalitatív változók kezelése (kategória értékek), mert nem lehet közép értéket számtani - nem tudja kezelni a zajokat - O(tkn) költségű K . Középpontszám, N elemszám, t: iterációszám


SOM NN Célja: a magasabb dimenziószámú térben lévő objektumokhoz egy egy vagy kétdimenziós klasztertérképet készíteni. Neurális hálót alkalmaz Elemei: objektumok tere: objektumok és bázis elemek reprezentációs tér: rácselemek minden rácselem kapcsolt egy báziselemhez


10

SOM NN Tanulás menete: 1. a báziselemek véletlen eloszlással indulnak 2. Az objektumokat egyesével adjuk be az objektum térbe 3. minden új objektumnál megkeressük a hozzá legközelebb álló báziselemet 4. A nyerő báziselemet és annak rácsbeli szomszédaihoz tartozó báziselemeket elmozgatjuk az új objektum irányába 5. Az összes objektum feldolgozása után beállnak báziselemek 6. A kapcsolt báziselemek távolság viszonyait átvezetjük a a rácspontok közötti távolság viszonyokra


SOM NN


11

Sűrűség alapú módszerek-DENCLUE A klaszter kialakításánál a pontok elhelyezkedési sűrűségét vizsgálják: a sűrűn belakott területek lesznek a klaszterek. Előnye: - tetszőleges alakzat - zajok kezelése - domain független Hátránya: - időigényes, költséges


Sűrűség alapú módszerek-DENCLUE Alap módszer: 1. A térre rácshálót húzunk 2. A objektumokra sűrűségi távhatási függvényt helyezünk fel, ahol az objektum a függvény centruma 3. Kiszámoljuk a rácsháló minden pontjára az eredő sűrűséget 4. Ahol az eredő nagyobb, mint egy küszöb, sűrű pont lesz 5. Az összefüggő sűrű pontok alkotnak egy klasztert


trapezoid távhatási függvény

12

Sűrűség alapú módszerek: DBSCAN Csak az objektumok halmazát vizsgálja, nincs külön rácsháló Mag elem: azon objektum, melynek egy megadott határsugarú környezetében megadott darabszámnál nagyobb másik objektum található. Határ elem: azon objektum, mely nem mag elem. Közvetlen kapcsolt elemek: egyik a másik határsugarú környezetében van. Közvetett kapcsolt elemek: közvetlen kapcsolatok láncán keresztül köthetők össze Klaszter: kapcsolt mag elemekből és a magokból közvetlenül elérhető objektumok

Outlier Border Core Dr. Kovács László ME GEIAL

Eps = 1cm MinPts = 5

Sűrűség alapú módszerek: DBSCAN A módszer algortimusa – Tetszőleges p objektum kiválasztása – A p –ből elérhető, kapcsolt elemek kigyüjtése. – Ha p magelem, akkor klasztert kaptunk – Ha p határelem, akkor p elvetése a kapcsolt elemeivel együtt – Az adatbázis összes elemének feldolgozása a fenti módon


13

Rács alapú módszerek Az objektumok terét téglalapokra bontja fel A téglalapok tartalmazási hierarchiát alkotnak A szülő, tartalmazó téglalapban a gyerekekre vonatkozó aggregált értékek tárolódnak - min - max - avg - stdev Az eredő szint jelzőiből lehet következtetni a gyerekek állapotaira A lekérdezés ezen aggregált jellemzőkön alapul A lekérdezés hierarchikus végrehajtású A lekérdezés ellenőrzi az adott szint aktuális téglalapjait Dr. Kovács László ME GEIAL

Rács alapú módszerek A lekérdezés csak azon téglalapoknál megy tovább, ahol a feltétel teljesül A kiválasztott elemek gyerekeit dolgozza fel a módszer rekurzívan

A lekérdezések hatékonyságjavítását szolgálja Dr. Kovács László ME GEIAL

14

Modell alapú módszerek


Modell alapú módszerek Algoritmus lépései: 1. Klaszterdarabszám meghatározása 2. A gyes klasztereket leíró paraméterek inicializálása 3. A paraméterek alapján a klaszterek valószínűségi eloszlásainak meghatározása 4. A mért és számított eloszlások összevetése alapján ez eloszlások paramétereinek aktualizálása Az eltérés minimalizálása a cél 5. A fenti ciklus ismétlése, amíg jelentős az eltérés Dr. Kovács László ME GEIAL

15

Modell alapú módszerek

Modell alapú megközeltés előnye:


- általános, probléma terület független - O(tkn) hatékonyság - általánosítható különböző eloszlások felé

Módszerek összevetése


16

Módszerek összevetése


17

Adatelemzés és adatbányászat MSc

Recommend Documents