Implementare Python

Prof. Tăbîrcă Angelica-Ioana, informatică și TIC, Liceul Teoretic „Ion Heliade Rădulescu” Târgoviște

Prof. Tăbîrcă Nicolae-Radu, informatică și TIC, Liceul Teoretic „Ion Heliade Rădulescu” Târgoviște

Contextul și importanța algoritmului DBSCAN

În cadrul domeniului clusterizării datelor, algoritmul DBSCAN (Density-Based Spatial Clustering of Applications with Noise) reprezintă o metodă de clusterizare bazată pe densitate. Acest algoritm se bazează pe ideea că obiectele din aceeași regiune densă a spațiului de date ar trebui să fie grupate împreună, în timp ce regiunile rare sau punctele izolate sunt considerate zgomot și nu sunt incluse în niciun cluster.

Schubert et al. (2017) au realizat o revizuire a algoritmului DBSCAN, subliniind importanța continuă a utilizării sale și oferind argumente pentru alegerea sa în anumite situații de clusterizare [1]. Importanța algoritmului DBSCAN constă în capacitatea sa de a identifica clusterii de forme și dimensiuni arbitrar complexe, precum și capacitatea sa de a gestiona eficient datele care pot conține zgomot sau puncte izolate. Algoritmul DBSCAN a devenit o metodă populară și eficientă în analiza datelor și în diverse domenii de aplicare, cum ar fi recunoașterea de tipare, analiza de imagini, analiza socială, analiza traficului rutier, și multe altele.

Unul dintre scopurile cercetării este de a explora și de a analiza algoritmul DBSCAN în detaliu, în vederea înțelegerii sale teoretice și practice.

Principiile clusterizării bazate pe densitate

Clusterizarea bazată pe densitate este o abordare în care clusterii sunt definiți ca regiuni dense de puncte de date separate de regiuni rar populate. Principalele principii ale clusterizării bazate pe densitate sunt [2]:

• Nucleu (core): Este un punct de date înconjurat de un număr minim de puncte vecine, care indică o regiune densă a clusterului.
• Directly reachable points: Acestea sunt punctele de date situate în interiorul sau în apropierea regiunii dense și sunt considerate parte a clusterului.
• Reachability points: Acestea sunt punctele de date situate în afara regiunii dense, dar pot fi conectate prin intermediul punctelor Directly reachable points și sunt considerate parte a clusterului.
• Puncte de zgomot (noise points): Acestea sunt punctele de date care nu pot fi atinse nici direct, nici indirect de nicio regiune densă și nu sunt considerate parte a clusterului.

Principiul de funcționare al algoritmului DBSCAN Algoritmul DBSCAN

(Density-Based Spatial Clustering of Applications with Noise) utilizează principiile clusterizării bazate pe densitate pentru a identifica clusterii într-un set de date. Principalele etape ale algoritmului sunt [1]:

• Inițializarea: Se selectează un punct de date nedescoperit aleator și se verifică vecinătatea sa pentru a determina dacă este un nucleu sau un punct de zgomot.
• Expandarea clusterului: Dacă un punct este un nucleu, se identifică toate punctele direct atingătoare și se extinde clusterul prin adăugarea acestor puncte și a punctelor Reachability points în mod recursiv.
• Formarea clusterului: Cluster-ul se formează prin adăugarea continuă a punctelor Directly reachable points și a punctelor Reachability points.
• Identificarea punctelor de zgomot: Punctele care nu pot fi atinse nici direct, nici indirect de nicio regiune densă sunt considerate puncte de zgomot și nu sunt atribuite niciunui cluster.

Algoritmul DBSCAN este robust la forme și dimensiuni variate ale clusterilor și poate detecta clusteri de orice formă. De asemenea, poate identifica punctele de zgomot și nu necesită specificarea numărului de clusteri în avans.

Descrierea algoritmului DBSCAN

Algoritmul DBSCAN (Density-Based Spatial Clustering of Applications with Noise) este un algoritm de clusterizare bazat pe densitate. Acesta se bazează pe ideea că un cluster într-un set de date este o regiune de densitate ridicată, separată de regiuni de densitate scăzută prin zone de zgomot.

Principiul de bază al algoritmului DBSCAN constă în identificarea punctelor de date „core” (nuclee) și a punctelor de date „border”. Un punct „core” este un punct de date care are cel puțin un număr minim predefinit de vecini într-o anumită rază predefinită. Un punct „border” este un punct de date care are mai puțini vecini decât numărul minim, dar se află în raza unui punct „core”. Punctele care nu sunt nici „core” nici „border” sunt considerate puncte de zgomot și nu sunt atribuite niciunui cluster [3].

Procesul de clusterizare în algoritmul DBSCAN începe prin alegerea unui punct de date nevizitat și verificarea dacă acesta este un punct „core”. Dacă este, se formează un nou cluster și se adaugă toate punctele din vecinătatea sa care satisfac condițiile de „core” sau „border”. Acest proces continuă recursiv până când nu mai există puncte nevizitate care să fie „core” sau să fie în vecinătatea punctelor „core”.

Parametrii algoritmului și impactul lor asupra rezultatelor

Algoritmul DBSCAN are doi parametri principali: raza (epsilon) și numărul minim de vecini (MinPts). Acești parametri influențează rezultatele clusterizării și trebuie aleși cu grijă în funcție de caracteristicile setului de date.

Raza (epsilon) determină distanța maximă până la care un punct poate fi considerat vecin cu alt punct. O valoare mare a razei va duce la formarea de clusteri mai mari și la absorbirea unor clusteri mai mici într-unul mai mare. Pe de altă parte, o valoare mică a razei poate duce la formarea de clusteri separați care ar putea fi parte din același cluster.

Numărul minim de vecini (MinPts) specifică numărul minim de vecini pe care un punct trebuie să îi aibă în raza specificată pentru a fi considerat „core”. Aceasta controlează densitatea necesară pentru a forma un cluster. Un MinPts mai mare va duce la formarea de clusteri mai restrânși și va ignora punctele de zgomot, în timp ce un MinPts mai mic va permite formarea de clusteri mai mari și poate include puncte de zgomot în clusteri [1].

Măsuri de evaluare a calității clusterizării

Pentru a evalua performanța clusterizării realizate de algoritmul DBSCAN, există mai multe măsuri și metode disponibile. Două dintre cele mai comune exemple sunt:

• Indicele Silhouette

Indicele Silhouette este o măsură a calității clusterizării, care ia în considerare gradul de similaritate între obiectele din același cluster și gradul de diferență între obiectele din clusterul respectiv și ceilalți clusteri. Valoarea indicelui Silhouette variază între -1 și 1, unde o valoare mai mare indică o clusterizare mai bună [4].

• Validarea externă

Validarea externă implică compararea rezultatelor algoritmului DBSCAN cu un set de date de referință, care conține etichetele reale ale obiectelor. Acesta poate implica utilizarea unor măsuri precum precizia, acuratețea sau măsuri specifice cum ar fi Rand Index sau Fowlkes-Mallows Index. Validarea externă oferă o perspectivă asupra cât de bine se potrivește clusterizarea algoritmului DBSCAN cu datele de referință [4].

Compararea performanței DBSCAN cu alți algoritmi de clusterizare

Pentru a compara performanța algoritmului DBSCAN cu alți algoritmi de clusterizare, se pot utiliza măsuri de evaluare precum cele menționate anterior sau se pot realiza experimente comparative pe diverse seturi de date. Alți algoritmi de clusterizare populari, care pot fi luați în considerare în comparație cu DBSCAN, sunt K-Means, Hierarchical Clustering sau Mean Shift.

Avantajele și limitările algoritmului DBSCAN [5] [6]

Avantajele algoritmului DBSCAN:

• Capacitatea de a identifica clusteri de forme și dimensiuni arbitrare: DBSCAN poate detecta clusteri de forme complexe și poate gestiona seturi de date în care clusterii pot fi de dimensiuni și densități variate. Nu necesită să se specifice forma sau dimensiunea clusterilor în prealabil.
• Capacitatea de a identifica puncte de zgomot: Algoritmul poate identifica și clasifica punctele de date care nu aparțin niciunui cluster ca puncte de zgomot. Acest lucru este util în identificarea și eliminarea datelor nerelevante sau anomalii din seturile de date.
• Rezistența la valori atipice: DBSCAN este rezistent la prezența valorilor atipice în setul de date. Datorită utilizării densității drept criteriu de formare a clusterilor, punctele atipice sau izolate nu vor fi incluse într-un cluster, ci vor fi tratate ca puncte de zgomot.
• Scalabilitate: Algoritmul DBSCAN poate fi eficient implementat și aplicat pe seturi de date mari. Performanța sa nu scade semnificativ odată cu creșterea dimensiunii setului de date.

Limitările algoritmului DBSCAN:

• Sensibilitate la parametri: Algoritmul DBSCAN necesită specificarea a doi parametri cheie: raza de vecinătate și numărul minim de puncte pentru a forma un cluster. Alegerea incorectă a acestor parametri poate duce la rezultate inadecvate. Adesea, este necesară o analiză și ajustare manuală a parametrilor pentru a obține rezultate optime.
• Sensibilitate la densitatea datelor: DBSCAN poate avea dificultăți în identificarea clusterilor în seturile de date cu densități inegale. Dacă există variații semnificative ale densității în setul de date, pot apărea dificultăți în detectarea clusterilor cu densități scăzute sau în separarea clusterilor densi de punctele de zgomot.
• Necesitatea de a alege o metrică adecvată: Algoritmul DBSCAN se bazează pe măsurarea distanței sau similarității între puncte. Alegerea unei metrici adecvate pentru setul de date și domeniul specific poate influența rezultatele algoritmului.
• Necesitatea de a preprocesa datele: Înainte de aplicarea algoritmului DBSCAN, este adesea necesară o etapă de preprocesare a datelor, cum ar fi normalizarea sau scalarea, pentru a asigura coerența valorilor și pentru a evita influența disproporționată a anumitor caracteristici asupra rezultatelor clusterizării.

Rezultate

Setul de date și prelucrarea acestuia

Setul de date utilizat în acest studiu provine de la Institutul Național al Diabetului și al Bolilor Digestive și Renale, care face parte din Institutul Național de Sănătate al Statelor Unite. Acesta este disponibil pe platforma Kaggle la următoarea adresă: https://www.kaggle.com/datasets/mathchi/diabetes-data-set .

Acest set de date este alcătuit din măsurători privind diabetul pentru pacientele de gen feminin, în vârstă de cel puțin 21 de ani, de origine indiană. Scopul studiului este de a analiza gruparea acestor paciente utilizând algoritmi de clusterizare, în funcție de indicatorii specifici diabetului. Setul de date conține următoarele variabile:

1. ID: id-ul unic al fiecărei paciente;
2. Pregnancies: Numărul de sarcini;
3. Glucose: Concentrația de glucoză plasmatică la 2 ore în cadrul unui test de toleranță la glucoză orală;
4. BloodPressure: Tensiunea arterială diastolică (mm Hg);
5. SkinThickness: Grosimea pliului cutanat al tricepsului (mm);
6. Insulin: Insulină serică la 2 ore (mu U/ml);
7. BMI: Indicele de masă corporală (greutate în kg/(înălțime în m)^2);
8. DiabetesPedigreeFunction: Funcția pedigree pentru diabet;
9. Age: vârsta în ani.

Înainte de a aplica algoritmii de clusterizare, setul de date a fost prelucrat pentru a asigura calitatea și consistența acestuia. Acest proces de prelucrare a implicat următorii pași:

• Curățarea datelor: Identificarea și eliminarea eventualelor erori sau anomalii, precum valorile lipsă sau incorecte.
• Transformarea datelor: Conversia datelor într-un format adecvat pentru aplicarea algoritmilor de clusterizare, cum ar fi normalizarea sau scalarea variabilelor.
• Reducerea dimensiunilor: Selecționarea celor mai relevante variabile pentru analiza clusterizării, eliminând variabilele redundante sau coliniare, prin tehnici precum analiza componentelor principale (PCA) sau selecția univariată a caracteristicilor.

După prelucrarea și pregătirea setului de date, acesta a fost folosit pentru aplicarea și evaluarea algoritmului de clusterizare DBSCAN. Algoritmul a fost implementat în limbajul de programare Python, folosindu-se biblioteci și pachete software specifice, cum ar fi scikit-learn și NumPy.

Rezultatele obținute prin DBSCAN în Python

Analiza clusterilor prin histograme

Prezentarea clusterilor

Figură 1. Cod sursă 1 – algoritm Python DBSCAN

Figură 2. Cod sursă 2 – algoritm Python DBSCAN

Vârsta – pacienții care au vârsta cea mai mică se situează în clusterul 1.

Figură 3. Histogramă DBSCAN (id = vârstă)

Presiunea arterială – pacienții care au presiunea arterială cea mai mare se situează în clusterul 1.

Figură 4. Histogramă DBSCAN (id = presiune arterială)

Indicele de masă corporală – pacienții care au indicele de masă corporală cel mai mare se situează în clusterul 1.

Figură 5. Histogramă DBSCAN (id = indice de masă corporală)

Probabilitatea de diabet pe baza antecedentelor familiale – pacienții care au probabilitatea de diabet cea mai mare se situează în clusterul 1.

Figură 6. Histogramă DBSCAN (id = pb. de diabet pe baza antecedentelor familiale)

Cantitatea de glucoză – pacienții care au cantitatea de glucoză cea mai mare se situează în  clusterul 1.

Figură 7. Histogramă DBSCAN (id = cantitatea de glucoză)

Insulină – pacienții care au insulina cea mai mică se situează în clusterul 1.

Figură 8. Histogramă DBSCAN (id = insulină)

Numărul de nașteri – pacienții care au numărul de nașteri cel mai mare se situează în clusterul 1.

Figură 9. Histogramă DBSCAN (id = nr. de nașteri)

Grosimea pielii – pacienții care au grosimea pielii cea mai mare se situează în clusterul 1.

Figură 10. Histogramă DBSCAN (id = grosimea pielii)

Graficul partiției evidențiază formarea a nouă clusteri, dintre care doar c1 având datele ușor mai grupate.

Figură 11. Graficul partiției DBSCAN

În concluzie, DBSCAN (Implementare Python): Aplicarea algoritmului DBSCAN a condus la formarea a nouă clusteri, dintre care doar c1 având datele ușor mai grupate. De exemplu, pacienții care au vârsta cea mai mică, presiunea arterială cea mai mare, indicele de masă corporală cel mai mare, probabilitatea de diabet cea mai mare, cantitatea de glucoză cea mai mare, insulina cea mai mică, numărul de nașteri cel mai mare, și grosimea pielii cea mai mare se situează în clusterul 1.

Referințe bibliografice

[1]: https://dl.acm.org/doi/10.1145/3068335

Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), 19

[2]: http://www.cs.ubbcluj.ro/~lauras/test/docs/school/MIRPR/lectures/05_ML.pdf

[3]: https://towardsdatascience.com/dbscan-make-density-based-clusters-by-hand-2689dc335120

[4]: https://link.springer.com/article/10.1007/BF01908075

Rousseeuw, P.J. (1987). Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis.

[5]: https://dl.acm.org/doi/10.5555/3001460.3001507

Ester, M., Kriegel, H.P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96).

[6]: https://ieeexplore.ieee.org/document/914876

Jin, W., Tung, A.K.H., Han, J., & Wang, W. (2001). Mining Top-k Covering Rule Groups for Gene Expression Data. In Proceedings of the 17th International Conference on Data Engineering (ICDE 2001).