20. tétel - Klaszterezés

Mit értünk klaszterezési feladatok alatt? Mutassa be a K-means algoritmust! Ismertesse a DBSCAN algoritmus alapfogalmait és alapvető lépéseit! Mi a különbség az egyes módszerek között?

Klaszterezési feladatok

1. A klaszterezés közeli adatokból csoportokat (klasztereket) alakít ki.
2. Az egymástól távoli elemek különböző klaszterekbe kerülnek.
3. Gyakran a csoportok elhelyezkedése és száma előre nem ismert

flowchart TB
K[Klaszterezés]-->H[Hierarchikus] & NH[Nem hierarchikus]
H --> O["`**Összevonó**
*(kezdetben minden elem külön klaszter, majd ezeket összevonogatja nagyobb klaszterekké)*`"]
H --> F["`**Felosztó**
*(kezdetben az összes elem egy klaszterben van, és ezt bontogatja kisebb klaszterekre)*`"]
O --> DS[DBSCAN]
NH --> KM["K-means"]

K-közép (K-means) algoritmus

1. Nem hierarchikus
2. \(N\) darab centroidot tárol (\(C_1\), \(C_2\), ... \(C_n\))
3. Minden pont abba klaszterbe (\(K_1\), \(K_2\), ... \(K_n\)) tartozik, amelynek a centroidjához legközelebb van
4. Úgy mozgatja a centroidokat, hogy minél inkább egymástól elkülönülő klaszterek jöjjenek létre

Alapvető lépések

1. Inicializálás, kezdő centroidok (klaszterek ”középpontjának”) megadása
   • tipikusan véletlenszerűen
2. Elemek besorolása a klaszterekbe a távolsági adatok alapján
   • minden elem a hozzá legközelebbi centroid klaszterébe kerül.
3. Ez alapján klaszterek középpontjának módosítása -minden centroid új pozíciója a hozzá tartozó elemek pozícióinak átlaga lesz
4. Ha változtak a középpontok, akkor megismételjük a műveletet.
5. Ha nem változtak a középpontok, kilép az eljárás

flowchart TB
I["Inicializálás (véletlen kezdőpontok felvétele)"]
BES[Elemek besorolása a klaszterekbe a távolságok alapján]
KP["Centroidok módosítása (a klaszterbe tartozó elemek pozíciójának átlagolásával)"]
V{Változtak a centroidok?}--"igen"-->BES
I-->BES-->KP-->V--"nem"-->K[Kilépés]

Megvalósítás

• \(C'\) halmaz mindig az előző iteráció elemeit tárolja
  • ide hozzuk létre a kezdő centroidokat is
• Az új centroidokat mindig a \(C\) halmazba hozzuk létre
• \(K\) halmazok tárolják a klaszterek elemeit
  • ezeket mindig újra létrehozzuk
• A függvény visszatérési értéke a klaszterek halmaza

Értékelés

• Előny: Egyszerű, gyors
• Hátrány: előre meg kell adni a klaszterek számát, amit sokszor nem tudunk
  • Kiegészítési lehetőség: ha ezt nem tudjuk, az algoritmust le lehet futtatni egymás után többféle K értékkel
• Gyakorlati probléma: képszegmentálás

DBSCAN

• Sűrűség-alapú klaszterezési eljárás
• Hierarchikus, öszevonó jellegű módszer

Bemenetei

Fogalmak

1. Belső pont: olyan pont, amitől a legfeljebb \(\epsilon\) távolságra lévő elemek száma legalább \(minPts\)
2. Közvetlenül sűrű elérhetőség: ha egy belső ponttól egy \(q\) pont távolsága legfeljebb \(\epsilon\), akkor \(q\) közvetlenül sűrűn elérhető
3. Sűrű elérhetőség: ha egy belső pontból át tudunk "lépkedni" \(q\)-ig úgy, hogy a köztes pontok mindig közvetlenül sűrűn elérhetőek az előző pontból, akkor \(q\) sűrűn elérhető
   • tehát a közvetlen sűrű elérhetőség tranzitív lezártja
4. Kivülállók: azok a pontok, amelyek nem elérhetőek a többi pontból

Alapvető lépések

1. Vegyük azokat a pontokat, amelyeknek az \(\epsilon\) környezetében legalább \(minPts\) darab másik pont található.
2. Ezeket a belső pontokat és az \(\epsilon\) környezetben lévő pontokat tekinthetjük egy klaszter kiinduló halmazának.
3. Amennyiben vannak a térben olyan pontok, amelyek még nem részei ennek a halmaznak, viszont annak valamelyik belső pontjától \(\epsilon\) távolságon belül vannak, akkor ezekkel egészítsük ki a halmazt.
4. Amennyiben már nem találunk ilyen pontot, megkaptuk a kezdőpontból elérhető legnagyobb klasztert.
5. Végezzük el a műveletet a többi belső pontra.

A klaszterek átfedhetik egymást.

• Tipikusan az egy klaszter különböző pontjaiból induló keresések átfedő eredményeket adnak.
• Ezért menet közben csak olyan kezdőpontokat választunk, illetve olyan elemekkel bővítünk, amelyek még nem lettek feldolgozva.

K-means és DBSCAN különbségei