1. Tekintsünk egy 2 20 adatvektort tartalmazó adathalmazt, melynek minden vektora 32 elemű, és minden elem egy 4 bájtos érték. Tegyük fel, hogy tömörítésre alkalmaztunk vektor kvantálást, és hogy 2 16 prototípus vektort használtunk. Hány bájtnyi tárterületet foglal az adathalmaz a tömörítés előtt és után, mekkora továbbá a tömörítési arány?

2. Keressen meg minden jól elkülönülő klasztert 6. ábrán látható ponthalmazban.

3. Sok felosztó klaszterező algoritmus, mely automatikusan határozza meg a klaszterek számát, azt állítja, hogy ez előnyt jelent. Soroljon fel két olyan helyzetet, amelyekben hamis ez az állítás.

4. Ha adott K egyenlő nagyságú klaszter, akkor 1/K annak valószínűsége, hogy egy véletlenszerűen kiválasztott kiindulási középpont egy adott klaszterbe tartozzon, viszont sokkal kisebb annak valószínűsége, hogy minden klaszter pontosan egy kiindulási középpontot tartalmazzon. (Világos kell legyen, hogy a K -közép módszer számára egy jó kiinduló helyzet az, ha minden klaszterben található egy kezdő középpont.) Általánosan, ha K klaszter van és minden klaszter n pontot tartalmaz, akkor (8.15) képlet adja meg annak p valószínűségét, hogy egy K elemű mintába minden klaszterből kiválasztásra kerül egy középpont. (Visszatevéses mintavételt feltételezve.) A formulából kiszámíthatjuk például azt, hogy 4!/ 4 4 =0,0938 annak az esélye, hogy 4 klaszter mindegyikébe egy kezdő középpont esik.

p= annak száma, hogy hányféle módon választható ki minden klaszterből egy középpont annak száma, hogy hányféle módon választható ki K középpont = K! n K (Kn) K = K! K K (8.20)

5. Azonosítsa a klasztereket a 8.36. ábrán a középpont, szomszédság- és sűrűség-alapú definíciók segítségével. Minden esetben adja meg a klaszterek számát is, valamint adjon rövid indoklást. Megjegyezzük, hogy a sötétség vagy pontok száma a sűrűséget jelzi. Amennyiben ez segít, tételezze fel, hogy a középpont-alapú definíció a K -közép módszert, a szomszédság-alapú az egyszerű kapcsolást, a sűrűség-alapú pedig a DBSCAN algoritmust jelenti.

6. Az alábbi kétdimenziós ponthalmazok esetén (1) vázolja fel, hogy hogyan vágná szét őket megadott számú klaszterré a K -közép módszer, és (2) megközelítőleg mutassa meg, hogy hol lennének az eredményül kapott középpontok. Tételezzük fel, hogy a négyzetes hiba célfüggvényt használjuk. Ha úgy véli, hogy egynél több lehetséges megoldás van, akkor minden egyes megoldáshoz tüntesse fel, hogy az lokális vagy globális minimum. Megjegyezzük, hogy a 8.37. ábra minden diagramjának felirata megfelel ezen kérdés vonatkozó részének, például a 8.37. (a) ábra az (a) részhez tartozik.

7. Tegyük fel egy adathalmazról, hogy

Az alábbiak közül melyik kell, hogy teljesüljön az adathalmazra a négyzetes hiba K klaszter keresése esetén történő minimalizálásához?

Megjegyzés: Ne vonják el a figyelmét rendkívüli esetek, és a sűrűségen kívül ne vegyen figyelembe más tényezőt. Ha úgy érzi azonban, hogy a helyes válasz különbözik a fentebb felsoroltaktól, akkor indokolja válaszát.

8. Tekintsük egy olyan objektumokból álló klaszter átlagát, amelyek egy bináris tranzakciós adathalmazból származnak. Melyek az átlag koordinátáinak legkisebb és legnagyobb értékei? Mi a klaszterátlag koordinátáinak értelmezése? Mely koordináták jellemzik legpontosabban a klaszter objektumait?

9. Adjon egy példát olyan adathalmazra, amely három természetes klasztert tartalmaz, és amelyre a K -közép módszer (majdnem minden esetben) jó eséllyel a helyes klasztereket találná meg, a kettéosztó K -közép módszer azonban nem.

10. A koszinusz mérték lenne-e a megfelelő hasonlóság mérték idősor adatok K -közép módszerrel történő klaszterezéséhez? Miért, vagy miért nem? Ha nem, akkor mely hasonlósági mérték lenne megfelelőbb?

11. A teljes SSE a különböző attribútumokhoz tartozó SSE értékek összege. Mit jelent az, ha az egyik változóhoz tartozó SSE minden klaszter esetén kicsi? Ha csak egy klaszter esetében kicsi? Ha nagy minden klaszter esetén? Ha csak egy klaszternél nagy? Hogyan tudná a klaszterezés javítására felhasználni a változónkénti SSE információkat?

12. A vezér algoritmus (leader algorithm, Hartigan [5008]) minden klasztert egy pont segítségével ábrázol, melyet vezérnek (leader) nevezünk, és minden pontot a hozzá legközelebbi vezérnek megfelelő klaszterhez rendel hozzá, hacsak nem nagyobb a vezértől mért távolság egy, a felhasználó által megadott küszöbértéknél. Ebben az esetben a pont egy új klaszter vezére lesz.

13. A sík egy K elemű ponthalmazának Voronoi diagramja a sík összes pontjának egy K számú területre történő olyan felosztása, ahol a sík minden pontját az adott K pont közül a hozzá legközelebbihez rendeljük hozzá. (Lásd 9. ábrát.) Mi a kapcsolat a Voronoi diagram és a K -közép módszer klaszterei között? Mit mondanak a Voronoi diagramok a K -közép klaszterek lehetséges alakjáról?

14. Adott egy 100 rekordból álló adathalmaz, feladatunk pedig az adatok klaszterezése. K -közép módszert használunk az adatok klaszterezésére, de az algoritmus csak egy nem üres klasztert ad vissza minden K értékre, ahol 1≤K≤100 . Ezután a K -közép algoritmus egy növekményes változatát alkalmazzuk, de pontosan ugyanezt az eredményt kapjuk. Hogyan lehetséges ez? Hogyan kezelne az egyszerű kapcsolás vagy a DBSCAN ilyen adatokat?

15. A hagyományos hierarchikus klaszterező eljárások minden lépésben két klasztert olvasztanak össze. Valószínűnek tűnik-e, hogy egy ilyen megközelítés pontosan tükrözi adatpontok egy halmazának (egymásba ágyazott) klaszterszerkezetét? Ha nem, akkor fejtse ki, hogy milyen utófeldolgozást végezhetne az adatokon, hogy pontosabb képet kapjon a klaszterszerkezetről.

16. Használja a 8.13. táblázat hasonlósági mátrixát egyszerű kapcsolású és teljes kapcsolású hierarchikus klaszterezés végrehajtására. Ábrázolja az eredményt egy dendrogram rajzolásával. A dendrogram egyértelműen kell hogy mutassa a pontok összevonásának sorrendjét.

17. A hierarchikus klaszterezést néha úgy használják K≥1 számú klaszter létrehozására, hogy a dendrogram K -adik szintjén lévő klasztereket veszik. (A gyökér az 1. szinten helyezkedik el.) Megvizsgálva az ilyen módon létrehozott klasztereket értékelhetjük a hierarchikus klaszterezés különböző típusú adatokon és klasztereken történő viselkedését, valamint összehasonlíthatjuk a hierarchikus megközelítéseket a K -közép módszerrel is.

Adott egydimenziós pontok következő halmaza: {6,12,18,24,30,42,48} .

18. Tegyük fel, hogy K klasztert találunk a Ward módszerrel, a kettéosztó K -közép módszerrel és a hagyományos K -közép módszerrel. Ezen megoldások közül melyik képvisel lokális vagy globális minimumot? Magyarázza meg, hogy miért.

19. A hierarchikus klaszterező algoritmusok O( m 2 log(m)) időigényűek, ebből kifolyólag nem praktikus a nagyobb adathalmazokon történő közvetlen használatuk. A szükséges idő csökkentésének egyik módszere az adathalmaz mintavételezése. Ha például K klasztert szeretnénk létrehozni és m pontot mintavételeztünk m számú pontból, akkor egy hierarchikus klaszterező algoritmus nagyjából O(m) idő alatt állít elő egy hierarchikus klaszterezést. Úgy nyerhetünk ki K klasztert ebből a hierarchikus klaszterezésből, hogy a dendrogram K -adik szintjén lévő klasztereket vesszük. A fennmaradó pontokat ezután több stratégia segítségével lineáris időben sorolhatjuk klaszterekbe. Hogy egy konkrét példát adjunk, kiszámíthatjuk a K klaszter középpontjait, majd az m− m fennmaradó pont mindegyikét a legközelebbi középponthoz tartozó klaszterhez rendelhetjük hozzá.

Minden, a következőkben felsorolt adat- és klasztertípus esetén vitassa meg röviden, hogy (1) okoz-e a mintavétel problémákat a fenti megközelítésnél, és hogy (2) melyek ezek a problémák. Tegyük fel, hogy a mintavételezési módszer véletlenszerűen választ pontokat az összesen m pontból, és hogy az adatok vagy klaszterek minden nem említett jellemzője a lehető legoptimálisabb. Más szóval, csak a megadott jellemzőkből adódó hibákra összpontosítson. Tegyük fel végül, hogy K sokkal kisebb, mint m .

20. Tekintsük a 8.39. ábrán látható négy arcot. A sötétség vagy a pontok száma ismét a sűrűséget jelzi. A vonalak csupán területeket különítenek el, nem pedig pontokat ábrázolnak.

21. Számítsa ki az entrópiát és a tisztaságot a 8.14. táblázatban látható tévesztési mátrixra.

22. Adott két, 100 olyan pontból álló halmaz, amelyek az egységnégyzeten belül helyezkednek el. Az egyik adathalmaz olyan módon elrendezett, hogy a pontok egymástól egyenlő távolságra helyezkednek el. A másik adathalmazt az egységnégyzeten egyenletes eloszlásból generáljuk.

23. A 24.. feladat adatait felhasználva számítsa ki a sziluett együttható értékét minden egyes pontra, mindkét klaszterre és a teljes klaszterezésre.

24. Adott a 8.15 és a 8.16. táblázatban látható klasztercímke halmaz és hasonlósági mátrix. Számítsa ki a hasonlósági mátrix és az ideális hasonlósági mátrix közötti korrelációt. (Az ideális hasonlósági mátrix ij -edik eleme 1, ha a megfelelő két objektum ugyanabba a klaszterbe tartozik, 0 egyébként.)

25. Számítsa ki a hierarchikus F -mértéket 11. ábrán látható nyolc objektumra ( p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 ) és hierarchikus klaszterezésre. Az A osztály a p1 , p2 és p3 pontokat tartalmazza, míg a p4 , p5 , p6 , p7 és p8 a B osztályhoz tartozik.

26. Számítsa ki a kofenetikus korrelációs együtthatót a 16. feladat hierarchikus klaszterezéseire. (A hasonlóságokat különbözőségekké kell alakítania.)

27. Bizonyítsa be (8.14) egyenletet.

28. Bizonyítsa be (8.16) egyenletet.

29. Bizonyítsa be, hogy ∑ i=1 K ∑ x∈ C i (x− m i )(m− m i )=0 . Ezt a tényt használtuk fel a 8.5.2. szakaszban annak bizonyításánál, hogy TSS = SSE + SSB.

30. Dokumentumok klasztereit összegezhetjük úgy, hogy megkeressük a legmagasabb rangú kifejezéseket (szavakat) a klaszter dokumentumaiban, azaz a k leggyakoribb kifejezést véve, ahol k egy konstans, például 10, vagy az összes olyan kifejezést véve, melyek egy adott küszöbértéknél gyakrabban fordulnak elő. Tegyük fel, hogy a K -közép módszert használjuk arra, hogy egy dokumentum adathalmazban megkeressük a dokumentumok és szavak klasztereit is.

32. Egy adathalmaz ábrázolható objektum-csúcsok egy és attribútum-csúcsok egy halmazaként, ahol minden objektum és minden attribútum között egy él van, és ahol egy él súlya az adott attribútum az objektumhoz tartozó értéke. Ritka adatok esetén elhagyunk egy élt, ha az érték 0. A páros klaszterezés (bipartite clustering) ezt a gráfot próbálja diszjunkt klaszterekre osztani, ahol minden egyes klaszter objektum- és attribútum-csúcsokból áll. A cél az objektum- és attribútum-csúcsok közötti élek súlyainak maximalizálása egy klaszteren belül, és egyidejűleg a különböző klaszterekhez tartozó objektum- és attribútum-csúcsok közötti élek súlyainak minimalizálása. Ezt a típusú klaszterezést együttes klaszterezésnek (co-clustering) is nevezik, mivel az objektumok és az attribútumok klaszterezése egyidejűleg történik.

33. Párosítsa össze a 8.41. ábrán látható és a klasztercímkék szerint rendezett hasonlósági mátrixokat az ábra ponthalmazaival. A klasztereket eltérő színezés és szimbólumok különböztetik meg, valamint minden ponthalmaz 100 pontot és 3 klasztert tartalmaz. A 2-es ponthalmazban 3 nagyon szoros, azonos méretű klaszter van.