Bár koránt sincs annyi módszer a sűrűség definiálására, mint a hasonlóságéra, de azért számos különböző eljárást találunk. Ebben a szakaszban azt a középpont-alapú (center-based) megközelítést tárgyaljuk, amelyen a DBSCAN is alapul. A sűrűség további definícióit a 9. fejezetben mutatjuk be.

A középpont-alapú megközelítésnél az adathalmaz egy adott pontjában a sűrűséget úgy becsüljük, hogy megszámoljuk a pont Eps sugarú környezetében található pontok számát. Ebbe magát a pontot is beleszámoljuk. Ezt a módszert szemlélteti grafikusan a 8.20. ábra. Az A pont Eps sugarú környezetében, A -val együtt, összesen 7 pont van.

A módszer implementációja egyszerű, de bármely pont sűrűsége a sugár függvénye lesz. Ha például a sugár elég nagy, akkor minden pontban m lesz a sűrűség, amely az összes pont száma az adathalmazban. Hasonlóképpen, ha a sugár túl kicsi, akkor minden pont sűrűsége 1 lesz. Alacsony dimenziós adatokhoz megfelelő sugár megválasztására a következő szakaszban, a DBSCAN tárgyalása során adunk stratégiát.

Pontok osztályozása középpont-alapú sűrűség alapján

A középpont-alapú sűrűségi megközelítés egy pontot aszerint osztályoz az elhelyezkedése alapján, hogy (1) egy sűrű terület belsejébe (belső pont), (2) egy sűrű terület szélére (határpont), vagy (3) egy ritka területre (zajos vagy háttér pont) esik. A 8.21. ábrán kétdimenziós pontok segítségével szemléltetjük grafikusan a belső, a határ-, valamint a zajos pontok fogalmát. Az alábbiakban pontosabb leírást adunk ezekről.

Belső (core) pontok:

Ezek a pontok a sűrűség-alapú klaszterek belső részében helyezkednek el. Egy pont belső pont, ha a távolságfüggvény és egy, a felhasználó által megadott Eps távolság paraméter által meghatározott környezetében található szomszédos pontok száma elér egy bizonyos MinPts küszöbértéket, mely szintén egy, a felhasználó által megadott paraméter. A 8.21. ábrán az A pont belső pont, amennyiben MinPts≤7 a jelölt Eps sugár esetén.

Határ (border) pontok:

Egy határpont nem belső pont, de egy belső pont környezetében van. A 8.21. ábrán B egy határpont. Egy határpont akár több belső pont szomszédja is lehet.

Zajos (noise) pontok:

Minden olyan pont zajos pont, amely nem belső vagy határpont. A 8.21. ábrán a C pont zajos pont.

Ha adott a belső, határ-, és zajos pontok fenti definíciója, akkor a DBSCAN algoritmus az alábbi kötetlen módon írható le. Bármely két belső pont ugyanabba a klaszterbe kerül, amennyiben elég közel -- egy Eps távolságon belül -- vannak egymáshoz. Hasonlóképpen, bármely határpontot, amely elég közel van egy belső ponthoz, a belső ponthoz tartozó klaszterhez rendeljük. (Az egyező távolságokból eredő problémákat fel kell oldani, ha a határpont közel van több, különböző klaszterekhez tartozó belső ponthoz.) A zajos pontokat figyelmen kívül hagyjuk. Az algoritmus formális leírását a 8.4. algoritmus adja meg. Ez az algoritmus azonos elvek alapján működik és ugyanazokat a klasztereket találja meg, mint az eredeti DBSCAN algoritmus, de megírásakor az egyszerűséget, és nem a hatékonyságot tartottuk szem előtt.

Idő- és tárbonyolultság

A DBSCAN algoritmus időbonyolultsága O(m× az Eps -sugarú környezetben található pontok megtalálásához szükséges idő ) , ahol m a pontok száma. Legrosszabb esetben ez O( m 2 ) . Alacsony dimenzióban azonban léteznek olyan adatszerkezetek, mint például a k -d fák, amelyek lehetővé teszik az összes pont kinyerését egy adott távolságon belül egy megadott ponthoz, és így az időbonyolultság akár is O(mlogm) lehet. A DBSCAN tárigénye még magas dimenziójú adatoknál is O(m) , mivel elég viszonylag kis számú adatot tárolni mindegyik pontra, nevezetesen a klasztercímkét és a pont besorolását mint belső, határ, vagy zajos pont.

A DBSCAN paramétereinek megválasztása

Természetesen kérdés, hogy hogyan határozzuk meg az Eps és a MinPts paraméterek értékeit. A legegyszerűbb megközelítés az, hogy megvizsgáljuk a pontok k -adik legközelebbi szomszédjától mért távolságának, amelyet k -távnak ( k -dist) hívunk, a viselkedését. A valamely klaszterbe tartozó pontok k -táv értéke kicsi lesz, feltéve, hogy k értéke nem nagyobb a klaszterek méreténél. Megjegyezzük, hogy a klaszterek sűrűsége és a pontok véletlen eloszlása miatt az értékek ugyan ingadozni fognak, de átlagosan nem lesz nagy ezen ingadozás terjedelme, amennyiben a klasztersűrűség nem különbözik gyökeresen. Az olyan klasztereken kívüli pontokra azonban, mint a zajos pontok, a k -táv értéke viszonylag nagy lesz. Ezért ha minden ponthoz kiszámítjuk a k -táv értéket egy adott k -ra, nagyság szerint sorba rendezzük őket, majd ábrázoljuk a sorba rendezett értékeket, akkor azt várjuk, hogy egy éles váltást látunk a k -táv értékekben, amely egy alkalmas Eps értéket szolgáltat. Amennyiben ezt a távolságot választjuk az Eps paraméter értékének és k értékét a MinPts paraméternek, akkor azokat a pontokat, amelyekhez tartozó k -táv értéke kisebb, mint Eps , belső pontoknak, a többi pontot pedig vagy zajos, vagy pedig határpontnak címkézzük.

A 8.22. ábra egy minta adathalmazt ábrázol, az adatokhoz tartozó k -táv értékek grafikonját pedig a 8.23. ábrán láthatjuk. A fentebb leírt módon meghatározott Eps értéke függ k értékétől, de nem változik jelentősen k értékével. Ha a k értéke túl kicsi, akkor még néhány, egymáshoz közel elhelyezkedő zajos pontot vagy kiugró értéket is hibásan klasztereknek címkézünk. Ha a k értéke túl nagy, akkor a kis klasztereket, melyeknek elemszáma kisebb, mint k , valószínűleg zajként címkézzük. Az eredeti DBSCAN algoritmus k=4 értéket használt, amely a legtöbb kétdimenziós adathalmaz esetében ésszerűnek tűnik.

Változó sűrűségű klaszterek

A DBSCAN módszer nehezen kezeli a nagymértékben változó sűrűségű klaszterek problémáját. Tekintsük a 8.24. ábrán látható, zajba ágyazott négy klasztert. A klaszterek és a zajos tartományok sűrűségét a szürke árnyalatainak mélysége jelöli (a sötétebb területek a sűrűbbek). A sűrűbb A és B klaszterek körüli zaj sűrűsége megegyezik a C és D klaszterek sűrűségével. Ha az Eps küszöbérték elég kicsi ahhoz, hogy a DBSCAN megtalálja a C és D klasztereket, akkor az A és B klaszter, valamint az őket körülvevő zaj egyetlen klasztert fognak alkotni. Ha az Eps küszöbérték elég nagy ahhoz, hogy a DBSCAN elkülönítse az A és B klasztereket, és a körülöttük található pontokat zajnak jelöli meg, akkor C és D , valamint körülöttük lévő pontok szintén zajnak lesznek megjelölve.

Példa

A DBSCAN használatát úgy szemléltetjük, hogy bemutatjuk a módszer segítségével megtalált klasztereket egy olyan viszonylag bonyolult szerkezetű kétdimenziós adathalmazon, mely a 8.22. ábrán látható. Ez az adathalmaz 3000 kétdimenziós pontot tartalmaz. Az Eps küszöbértéket ezekre az adatokra úgy kaptuk, hogy ábrázoltuk az adatpontok negyedik legközelebbi szomszédjaitól mért sorrendbe rendezett távolságokat (8.23. ábra) és leolvastuk azt az értéket, ahol éles növekedés látható. Az Eps=10 értéket választottuk, amelyet a görbe hajlatában mértünk. A választott paraméterek ( MinPts=4 és Eps=10 ) segítségével megtalált klasztereket a 8.25. (a) ábra mutatja. A belső, határ- illetve zajos pontokat a 8.25. (b) ábrán láthatjuk.

Mivel a DBSCAN egy klasztert sűrűség-alapon definiál, viszonylag ellenálló a zajjal szemben és kezelni képes tetszőleges alakú és méretű klasztereket. Így a DBSCAN képes olyan klaszterek megtalálására is, melyekre a K -közép módszer nem, ilyenek például a 8.22. ábrán láthatóak. Ahogy azt korábban említettük, a DBSCAN-nek problémája van azonban az erősen változó sűrűségű klaszterekkel. További nehézséget jelent a magas dimenzió a sűrűség definiálása miatt. Az ilyen kérdések megoldására a 9.4.8. szakaszban ismertetünk egy módszert. Végül a DBSCAN költséges lehet -- magas dimenziójú adatoknál rendszerint ez a helyzet --, amikor a legközelebbi szomszédok meghatározása az összes páronkénti közelség (távolság) kiszámítását igényli.