Feladatok

1. Elemezze, hogy ritka adatokra miért adhat pontosabb képet az objektumokról az, ha csak a nem nulla értékek jelenlétét tekintjük, mintha az értékek tényleges nagyságát is figyelembe vennénk. Mikor lehet nemkívánatos egy ilyen megközelítés?

2. Írja le a K -közép módszer időbonyolultságának változását a megtalált klaszterek számának növekedése esetén.

3. Tekintsünk egy dokumentumhalmazt. Tegyük fel, hogy minden dokumentumot normalizáltunk, hogy egységnyi hosszúságúak legyenek. Mi az ``alakja'' annak a klaszternek, ami azokból a dokumentumokból áll, amiknek a koszinusz hasonlósága egy középponthoz nagyobb, mint egy megadott konstans? Más szavakkal, cos(d,c)δ , ahol 0δ1 .

4. Elemezze annak az előnyeit és hátrányait, ha a klaszterezést optimalizálási problémának tekintjük. Más tényezők mellett vizsgálja a hatékonyságot, nemdeterminisztikusságot, és hogy vajon az optimalizálás-alapú megközelítés meg tudja-e ragadni az összes érdeklődésre számot tartó klaszterezési típust.

5. Mi a fuzzy c -közép idő- és tárbonyolultsága? És a SOM-nak? Hogyan viszonyulnak ezek a bonyolultságok a K -középéhez?

6. A hagyományos K -középnek számos korlátja van, mint például az érzékenység a kiugró értékekre, valamint a különböző méretű, alakú és sűrűségű, vagy a nem gömb alakú klaszterek kezelésének a nehézsége. Vizsgálja meg a fuzzy c -közép képességét ezen szituációk kezelésére.

7. Az ebben a könyvben bemutatott fuzzy c -közép algoritmusnál tetszőleges pontra 1-et kapunk, ha az összes klaszterre összegezzük a tagsági súlyát. Ehelyett csak azt is megkövetelhettük volna, hogy egy pont tagságának foka tetszőleges klaszterre 0 és 1 közötti legyen. Melyek egy ilyen megközelítés előnyei és hátrányai?

8. Fejtse ki a likelihood és a valószínűség közötti különbséget.

9. A (9.12) képlet a likelihood értékét adja meg egy Gauss eloszlásból származó ponthalmazra a μ várható érték és a σ szórás függvényében. Mutassa meg matematikailag, hogy μ és σ maximum likelihood becslése a mintaátlag és a minta szórása.

10. Egy mintát veszünk a felnőttek közül és megmérjük a magasságukat. Ha felvesszük az egyes személyek nemét, akkor külön-külön ki tudjuk számolni a férfiak és a nők magasságának átlagát és varianciáját. Tegyük fel azonban, hogy ezt az információt nem tároltuk. Lehetséges volna mégis megkapni ezt az információt? Magyarázza meg, hogy miért.

11. Hasonlítsa össze a tagsági súlyokat és valószínűségeket a 9.1. és a 9.4. ábrán, amelyeket a fuzzy és az EM klaszterezés alkalmazásával kaptunk ugyanazokra az adatpontokra. Milyen különbségeket lehet észrevenni, és hogyan lehet ezeket a eltéréseket magyarázni?

12. A 9.28. ábra egy kétdimenziós ponthalmaz két klaszterből álló klaszterezését mutatja. A bal oldali klaszter, amelynek pontjait csillagok jelölik, valamelyest diffúz, míg a jobb oldali klaszter, amelynek pontjait körök jelölik, kompakt. A kompakt klasztertől jobbra egy (nyíllal jelölt) pont található, amely a diffúz klaszterhez tartozik, annak ellenére, hogy a középpontja távolabb van tőle, mint a kompakt klaszteré. Magyarázza el, miért lehetséges ez az EM klaszterezésnél, és miért nem a K -közép klaszterezésnél.

9.28. ábra - Adatok 1l. feladathoz. Két különböző sűrűségű klasztert tartalmazó kétdimenziós ponthalmaz EM klaszterezése.

Adatok 1l. feladathoz. Két különböző sűrűségű klasztert tartalmazó kétdimenziós ponthalmaz EM klaszterezése.

13. Mutassa meg, hogy a 9.4.2. szakasz MST klaszterező módszere ugyanazokat a klasztereket állítja elő, mint az egyszerű kapcsolás. A komplikációk és speciális esetek elkerülése végett tegyük fel, hogy az összes páronkénti hasonlóság különböző.

14. A szomszédsági mátrix ritkításának egy lehetséges módja a következő: minden egyes objektumra (a mátrix soraira) minden érték legyen 0, kivéve azokat, amelyek az objektumok k -legközelebbi szomszédjaihoz tartoznak. Viszont ez a ritkított szomszédsági mátrix tipikusan nem szimmetrikus.

  1. Ha az a objektum a b objektum k -legközelebbi szomszédja között van, akkor miért nem garantált az, hogy b is az a k -legközelebbi szomszédja között legyen?

  2. Javasoljon legalább két olyan megközelítést, amelyeket a ritkított szomszédsági mátrix szimmetrizálására lehetne használni.

15. Adjon egy példát olyan klaszterhalmazra, ahol a klaszterek közelségén alapuló egyesítés természetesebb klaszterhalmazhoz vezet, mint a klaszterek kapcsolatának erősségén (interconnectedness) alapuló egyesítés.

16. A 9.4. táblázat négy pont két legközelebbi szomszédait adja meg.

9.4. táblázat - Négy pont két legközelebbi szomszédai

Pont

Első szomszéd

Második szomszéd

1

4

3

2

3

4

3

4

2

4

3

1


Minden egyes pontpár között számolja ki az SNN hasonlóságot, felhasználva a 9.10. algoritmusban szereplő definíciót.

17. Az SNN hasonlóság a 9.10. algoritmussal megadott definíciójában az SNN távolság kiszámítása nem veszi figyelembe a közös szomszédok pozícióját a két legközelebbi szomszéd listán. Más szavakkal, kívánatos lehet nagyobb hasonlóságot adni két olyan pontnak, amelyeknek ugyanazok a legközelebbi szomszédai ugyanabban vagy majdnem ugyanabban a sorrendben.

  1. Írja le, hogyan lehetne úgy módosítani az SNN hasonlóság definícióját, hogy nagyobb hasonlóságot kapjanak azok a pontok, amelyek közös szomszédai nagyjából hasonló sorrendben szerepelnek.

  2. Vizsgálja meg egy ilyen módosítás előnyeit és hátrányait.

18. Nevezzen meg egy szituációt, amelyben nem akarnánk SNN hasonlóságon vagy sűrűségen alapuló klaszterezést alkalmazni.

19. A rács-alapú klaszterező eljárások abban különböznek a többi klaszterező módszertől, hogy a teret osztják fel a ponthalmaz helyett.

  1. Hogyan befolyásolja ez a tény az ilyen eljárásoknál keletkező klaszterek leírását és a megtalálható klaszterek típusát?

  2. Milyen fajta klaszter található meg rács-alapú klaszterezéssel, ami nem található meg más típusú klaszterezési módszerekkel? (Útmutatás: lásd a 20. feladatot a 8. fejezetben az 584. oldalon.)

20. A CLIQUE-ben a klaszter-sűrűség meghatározásához használt küszöbérték konstans marad még akkor is, ha a dimenziószám nő. Ez egy potenciális probléma, mert a sűrűség csökken, ahogy a dimenziószám nő. Azaz ahhoz, hogy magasabb dimenzióban is megtaláljuk a klasztereket, a küszöbértéket olyan szintre kell beállítani, ami jó eséllyel egyesíti az alacsonyabb dimenziós klasztereket. Gondolja meg, hogy ezt valódi problémának érzi-e, és ha igen, hogyan módosítaná a CLIQUE algoritmust, hogy kezelje ezt a problémát.

21. Ha adott egy ponthalmaz az euklideszi térben, amelyet a K -közép algoritmussal klaszterezünk az euklideszi távolságot használva, akkor a háromszög-egyenlőtlenséget használhatjuk a hozzárendelési lépésnél ahhoz, hogy elkerüljük az összes pont távolságának kiszámítását az összes klaszter középponttól. Adjon általános elemzést arról, hogy ez miként tud működni.

22. Ahelyett, hogy a CURE-hoz kiszámolt képletet használnánk -- lásd a (9.19) képletet -- futtathatnánk egy Monte Carlo szimulációt, hogy közvetlenül megbecsüljük annak a valószínűségét, hogy egy s elemű minta egy klaszterből származó pontok legalább egy adott részarányát tartalmazza. Monte Carlo szimuláció alkalmazásával számolja ki annak a valószínűségét, hogy egy s elemű minta egy 100 elemű klaszter elemeinek 50%-át tartalmazza, ahol a pontok teljes száma 1000, és ahol s a 100, 200, vagy 500 értéket veheti fel.