Ok, să începem să vorbim despre DBSCAN.
Density-based spatial clustering of applications with noise (DBSCAN) este un algoritm bine cunoscut de grupare a datelor care este utilizat în mod obișnuit în data mining și machine learning.
Pe baza unui set de puncte (să ne gândim într-un spațiu bidimensional, așa cum este exemplificat în figură), DBSCAN grupează punctele care sunt apropiate unele de altele pe baza unei măsuri de distanță (de obicei, distanța euclidiană) și a unui număr minim de puncte. De asemenea, marchează ca fiind aberante punctele care se află în regiuni cu densitate scăzută.
Parametri:
Algoritmul DBSCAN necesită în principiu 2 parametri:
eps: specifică cât de apropiate trebuie să fie punctele între ele pentru a fi considerate ca făcând parte dintr-un cluster. Aceasta înseamnă că dacă distanța dintre două puncte este mai mică sau egală cu această valoare (eps), aceste puncte sunt considerate vecine.
minPoints: numărul minim de puncte pentru a forma o regiune densă. De exemplu, dacă stabilim parametrul minPoints ca fiind 5, atunci avem nevoie de cel puțin 5 puncte pentru a forma o regiune densă.
Stimarea parametrilor:
Stimarea parametrilor este o problemă pentru fiecare sarcină de extragere a datelor. Pentru a alege parametri buni, trebuie să înțelegem cum sunt utilizați și să avem cel puțin cunoștințe prealabile de bază despre setul de date care va fi utilizat.
eps: dacă valoarea eps aleasă este prea mică, o mare parte din date nu va fi grupată. Va fi considerată aberantă, deoarece nu satisface numărul de puncte pentru a crea o regiune densă. Pe de altă parte, dacă valoarea aleasă este prea mare, clusterele vor fuziona și majoritatea obiectelor vor fi în același cluster. Valoarea eps trebuie aleasă în funcție de distanța setului de date (putem folosi un grafic k-distanță pentru a o găsi), dar, în general, sunt de preferat valorile mici ale eps.
minPoints: Ca regulă generală, un minim minPoints poate fi derivat dintr-un număr de dimensiuni (D) din setul de date, ca minPoints ≥ D + 1. Valorile mai mari sunt, de obicei, mai bune pentru seturile de date cu zgomot și vor forma clustere mai semnificative. Valoarea minimă pentru minPoints trebuie să fie 3, dar cu cât setul de date este mai mare, cu atât mai mare este valoarea minPoints care trebuie aleasă.
Puteți găsi mai multe despre estimarea parametrilor aici.
De ce ar trebui să folosim DBSCAN?
Algoritmul DBSCAN ar trebui să fie folosit pentru a găsi asociații și structuri în date care sunt greu de găsit manual, dar care pot fi relevante și utile pentru a găsi tipare și a prezice tendințe.
Metodele de clusterizare sunt de obicei folosite în biologie, medicină, științe sociale, arheologie, marketing, recunoașterea caracterelor, sisteme de management și așa mai departe.
Să ne gândim la o utilizare practică a DBSCAN. Să presupunem că avem un comerț electronic și dorim să ne îmbunătățim vânzările prin recomandarea de produse relevante pentru clienții noștri. Nu știm exact ce caută clienții noștri, dar pe baza unui set de date putem prezice și recomanda un produs relevant pentru un anumit client. Putem aplica DBSCAN la setul nostru de date (pe baza bazei de date de comerț electronic) și putem găsi clustere pe baza produselor pe care le-au cumpărat utilizatorii. Cu ajutorul acestor clustere putem găsi similitudini între clienți, de exemplu, dacă clientul A a cumpărat 1 stilou, 1 carte și 1 foarfecă, iar clientul B a cumpărat 1 carte și 1 foarfecă, atunci îi putem recomanda clientului B 1 stilou. Acesta este doar un mic exemplu de utilizare a DBSCAN, dar poate fi folosit într-o mulțime de aplicații din mai multe domenii.
Cum îl putem implementa cu ușurință?
După cum am scris deja (sfat: nu credeți în tot ceea ce scriu), DBSCAN este un algoritm bine cunoscut, prin urmare, nu trebuie să vă faceți griji cu privire la implementarea sa. Puteți folosi una dintre bibliotecile/pachetele care pot fi găsite pe internet. Iată o listă de link-uri la care puteți găsi implementarea DBSCAN: Matlab, R, R, R, Python, Python.
Am dezvoltat și o aplicație (în portugheză) pentru a explica în mod didactic cum funcționează DBSCAN. Aplicația a fost scrisă în C++ și o puteți găsi pe Github.
.