Analiza datelor prin clustering pe bază de densitate în mineritul datelor

În clusteringul bazată pe densitate, clusterele sunt definite ca zone cu o densitate mai mare decât restul setului de date. Obiectele din aceste zone împrăștiate – care sunt necesare pentru a separa clusterele – sunt de obicei considerate a fi puncte de zgomot și de frontieră.

Cea mai populară metodă de clustering bazat pe densitate este DBSCAN. Spre deosebire de multe metode mai noi, prezintă un model de cluster bine definit numit „densitate-accesibilitate”. Similar clusteringului bazat pe conexiuni, se bazează pe puncte de conectare în anumite praguri de distanță. Cu toate acestea, conectează numai puncte care îndeplinesc un criteriu de densitate, în varianta originală definită ca un număr minim de alte obiecte în această rază. Un cluster este format din toate obiectele conectate prin densitate (care pot forma un cluster de formă arbitrară, spre deosebire de multe alte metode) plus toate obiectele care se află în raza acestor obiecte. O altă proprietate interesantă a DBSCAN este că complexitatea sa este destul de scăzută – necesită un număr liniar de interogări de interval în baza de date – și că va descoperi în esență aceleași rezultate (este determinist pentru punctele de bază și de zgomot, dar nu pentru punctele de graniță) în fiecare rulare, prin urmare nu este nevoie să o rulați de mai multe ori. OPTICS este o generalizare a DB-SCAN care înlătură necesitatea de a alege o valoare adecvată pentru parametrii de interval s și produce un rezultat ierarhic legat de cel al clusteringului de legături. DeLi-Clu, Density-Link-Clustering, combină ideile din clustering cu o singură legătură și OPTICS, eliminând complet parametrul s și oferind îmbunătățiri ale performanței față de OPTICS prin utilizarea unui index de arbore R.

Dezavantajul cheie al DBSCAN și OPTICS este că se așteaptă la un fel de scădere a densității pentru a detecta granițele clusterului. Mai mult, nu pot detecta structurile intrinseci ale clusterelor care sunt predominante în majoritatea datelor din viața reală. O variantă a DBSCAN, EnDBSCAN, detectează eficient astfel de structuri. Pe seturile de date cu, de exemplu, distribuții gaussiene suprapuse – un caz de utilizare obișnuit în datele artificiale – granițele clusterului produse de acești algoritmi vor părea adesea arbitrare, pentru că densitatea clusterului scade continuu. Pe un set de date format din amestecuri de gaussieni, acești algoritmi sunt aproape întotdeauna depășiți de metode precum gruparea EM, care sunt capabile să modeleze cu precizie acest tip de date.

Mean-shift este o abordare de clustering în care fiecare obiect este mutat în zona cea mai densă din vecinătatea sa, pe baza estimării densității nucleului. În cele din urmă, obiectele converg către maximele locale de densitate. Similar cu clusteringul k-means, acești „atractori de densitate” pot servi ca reprezentanți pentru setul de date, dar deplasarea medie poate detecta clustere de formă arbitrară similare cu DBSCAN. Datorită procedurii iterative costisitoare și estimării densității, deplasarea medie este de obicei mai lentă decât DBSCAN sau k-Means.

Exemple de grupare bazate pe densitate:

(Clustering bazat pe densitate cu DBSCAN.)

(DBSCAN presupune clustere de densitate similară și poate avea probleme la separarea clusterelor din apropiere)

(OPTICS este o variantă DBSCAN care gestionează mult mai bine diferite densități)

Sursa: Drew Bentley, Business Intelligence and Analytics. © 2017 Library Press, Licență CC BY-SA 4.0. Traducere și adaptare: Nicolae Sfetcu