DBSCAN: Kaj je to? Kdaj ga uporabiti? Kako ga uporabljati

DBSCAN (Prostorsko gruščanje aplikacij s hrupom na osnovi gostote) je priljubljena nenadzorovana metoda učenja, uporabljena pri algoritmih gradnje modelov in strojnega učenja. Preden gremo dalje, moramo določiti, kaj je "nenadzorovan" način učenja. Nenadzorovane metode učenja so, kadar ni jasnega cilja ali rezultata, ki ga želimo najti. Namesto tega podatke združujemo na podlagi podobnosti opazovanj. Za lažjo razjasnitev vzemimo Netflix za primer. Na podlagi prejšnjih oddaj, ki ste jih gledali v preteklosti, bo Netflix priporočal oddaje, ki si jih boste ogledali v nadaljevanju. Vsakdo, ki je kdaj gledal ali bil na Netflixu, je spodaj videl zaslon s priporočili (ja, ta slika je posneta neposredno iz mojega računa Netflix in če še nikoli niste gledali Shameless, predlagam, da se prijavite na ta ASAP).

Ker sem gledal "Brez sramu", Netflix priporoča več drugih podobnih oddaj. Toda od kod Netflix zbira ta priporočila? Glede na to, da poskuša napovedati prihodnost s tistim oddajem, ki ga bom gledal naprej, Netflix napovedi ali priporočila ne more utemeljiti na (nobenega jasnega dokončnega cilja). Namesto tega Netflix pregleduje druge uporabnike, ki so si v preteklosti ogledali tudi 'Shameless', in vidi, kaj so ti uporabniki videli poleg 'Shameless'. S tem Netflix združuje svoje uporabnike na podlagi podobnosti interesov. Prav to deluje nenadzorovano učenje. Preprosto združevanje opazovanj na podlagi podobnosti in upanje na točne sklepe na podlagi grozdov.

Nazaj na DBSCAN. DBSCAN je metoda grozdenja, ki se uporablja pri strojnem učenju za ločevanje skupin visoke gostote od grozdov nizke gostote. Glede na to, da je DBSCAN algoritem združevanja, ki temelji na gostoti, odlično opravi iskanje območij v podatkih, ki imajo visoko gostoto opazovanj, v primerjavi s področji podatkov, ki niso zelo gosti z opazovanji. DBSCAN lahko razvrsti podatke tudi v grozde različnih oblik, kar je še ena močna prednost. DBSCAN deluje kot tak:

  • Nabor podatkov razdeli na n dimenzij
  • Za vsako točko v naboru podatkov DBSCAN oblikuje n dimenzionalno obliko okoli te podatkovne točke in nato šteje, koliko podatkovnih točk spada pod to obliko.
  • DBSCAN šteje to obliko kot grozd. DBSCAN iterativno širi gručo tako, da gre skozi vsako posamezno točko znotraj grozda in šteje število drugih podatkovnih točk v bližini. Za primer si oglejte spodnjo grafiko:

Ko gremo korak po korak skozi zgoraj omenjeni postopek, bo DBSCAN začel z deljenjem podatkov na n dimenzij. Ko DBSCAN to stori, se bo začel naključno (v tem primeru predpostavimo, da je bila ena od rdečih točk) in šteje, koliko drugih točk je v bližini. DBSCAN bo nadaljeval ta postopek, dokler ni v bližini nobenih drugih podatkovnih točk, nato pa bo iskal drugo gručo.

Kot ste morda opazili na sliki, je nekaj parametrov in specifikacij, ki jih moramo dati DBSCAN, preden bo opravil svoje delo. Dva parametra, ki ju moramo določiti, sta kot taka:

Kakšno je najmanjše število podatkovnih točk, potrebnih za določitev posamezne skupine?
Kako daleč je lahko ena točka od naslednje točke znotraj istega grozda?

Glede na grafiko je epsilon polmer, ki je dan za preizkus razdalje med podatkovnimi točkami. Če točka pade znotraj epsilonske razdalje druge točke, bosta ti dve točki v istem razredu.

Poleg tega je v tem primeru minimalno število potrebnih točk določeno na 4. Ko gre skozi vsako podatkovno točko, dokler DBSCAN najde 4 točke znotraj epsilonske razdalje med seboj, nastane grozd.

POMEMBNO: Da se lahko točka šteje za "jedro", mora vsebovati najmanjše število točk znotraj epsilonske razdalje. Ergo, vizualizacija ima pravzaprav samo dve točki. Tu si oglejte dokumentacijo in še posebej preglejte parameter min_samples.

Opazili boste tudi, da modra točka na sliki ni v nobeni skupini. DBSCAN NIČNO ne razvršča v vsako podatkovno točko in je zato izjemen pri ravnanju z zunanjimi podatki v naboru podatkov. Oglejmo si spodnjo grafiko:

Na levi sliki je prikazana bolj tradicionalna metoda združevanja, ki ne upošteva večdimenzionalnosti. Medtem ko prava slika prikazuje, kako DBSCAN lahko podatke razdeli v različne oblike in dimenzije, da bi našel podobne grozde.

Na levi sliki je prikazana bolj tradicionalna metoda združevanja, kot je K-Means, ki ne upošteva večdimenzionalnosti. Medtem ko prava slika prikazuje, kako DBSCAN lahko podatke razdeli v različne oblike in dimenzije, da bi našel podobne grozde. Na desni sliki opazimo tudi, da točke vzdolž zunanjega roba nabora podatkov niso razvrščene, kar kaže na to, da so med podatki zunaj njega.

Prednosti DBSCAN:

  • Odličen je pri ločevanju grozdov visoke gostote v primerjavi z grozdi nizke gostote znotraj določenega nabora podatkov.
  • Odličen je za ravnanje z zunanjimi osebami znotraj nabora podatkov.

Slabosti DBSCAN:

  • Ne deluje dobro, če se ukvarjamo s skupinami različnih gostot. Medtem ko je DBSCAN odličen pri ločevanju grozdov visoke gostote od grozdov nizke gostote, se DBSCAN bori z grozdi podobne gostote.
  • Bori se s podatki visoke dimenzije. Vem, v tem celotnem članku sem navedel, kako je DBSCAN odličen pri pretvorbi podatkov v različne dimenzije in oblike. DBSCAN pa lahko gre samo tako daleč, če poda podatke s preveč dimenzijami, DBSCAN trpi

Spodaj sem vključil, kako implementirati DBSCAN v Python, v katerem nato razložim metrike in ocenim vaš model DBSCAN

Izvedba DBSCAN v Pythonu

1. Dodeljevanje podatkov kot naše X vrednosti
Ne pozabite, da ker je to nenadzorovano učenje, nimamo nobenih jasnih vrednosti y.
2. Takoj začnemo uporabljati naš model DBSCAN. V spodnji kodi je epsilon = 3 in min_samples najmanjše število točk, potrebnih za sestavljanje skupine.
3. Shranjevanje nalepk, ki jih je oblikoval DBSCAN
4. Določanje, katere točke tvorijo naše "ključne točke"
5. Izračun števila grozdov
6. Izračunavanje ocene silhuete

Meritve za merjenje uspešnosti DBSCAN:

Ocena silhuete: Rezultat silhuete se izračuna z uporabo povprečne razdalje med točkami znotraj točk in povprečne razdalje najbližjega grozda. Na primer, grozd z veliko podatkovnimi točkami zelo blizu drug drugega (velika gostota) IN je daleč stran od naslednjega najbližjega grozda (kar kaže na to, da je grozd zelo edinstven v primerjavi z naslednjim najbližjim), bo imel močan rezultat silhuete . Rezultat silhuete se giblje med -1 in 1, pri čemer je -1 najslabši možni rezultat, 1 pa najboljši rezultat. Rezultati silhuete 0 kažejo, da se grozdi prekrivajo.

Inercija: Inercija meri notranjo gručo vsoto kvadratov (vsota kvadratov je vsota vseh ostankov). Inercija se uporablja za merjenje, kako so povezani grozdi med seboj, nižji je rezultat inercije, tem bolje. VEDNO je pomembno opozoriti, da se vztrajnost močno opira na domnevo, da so grozdi izbočeni (sferične oblike). DBSCAN ni nujno, da podatke razdeli na sferične grozde, zato vztrajnost ni dobra meritev, ki bi jo lahko uporabili za ocenjevanje modelov DBSCAN (zato v zgornji kodi nisem vključil inercije). Inercija se pogosteje uporablja pri drugih metodah grozdenja, kot je na primer združevanje s sredstvi K.

Drugi viri:

Blog Naftali Harris je ogromen dodaten vir za več informacij