EXTRAGEREA DE CUNOȘTINȚE DIN CLUSTERE DE DATE SPAȚIO -TEMPORALE Coordonator științific: Absolvent : Prof.dr.ing Alexandru Boicea Laura -Florina… [617136]

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA DE AUTOMATICĂ ȘI CALCULATOARE
DEPARTAMENTUL CALCULATOARE

PROIECT DE DISERTAȚIE

EXTRAGEREA DE CUNOȘTINȚE DIN CLUSTERE DE DATE
SPAȚIO -TEMPORALE

Coordonator științific: Absolvent: [anonimizat].dr.ing Alexandru Boicea Laura -Florina Popescu

BUCUREȘTI
Iunie 2018

TEMA PROIECTULUI

Rezumat: Extragerea cunoștințelor din date spațio -temporale necesită prelucrări complexe pe
volume mari de date, cum ar fi datele meteorologice. Algoritmii de grupare spațio -temporală trebuie
să țină cont de gruparea spațială și temporală a obiectelor în scopul de a extrage cunoștințe utile.
Algoritmii de clustering pentru date spațio -temporale sunt folosiți în aplicația pentru sistemele
informatice geografice. Tema își propune îmbunătățirea algoritmilor specifici, precum și tes tarea lor în
domenii de interes. Acea stă tema își propune testarea algoritmilor DBSCAN și K -Means pentru nașterea
speciilor din România. Aceasta clusterizare se face pe harta României , atât pentru algoritmul DBSCAN
cât și pentru algortimul K -Means. Se pot adăuga date noi pentru diferite spec ii , aceste date se adaugă
printr -un excel încărcat în aplicație pentru a le încărca în bazele de date.
Cuvinte cheie: date, spațio -temporale, cunoștințe, algoritmi de clustering

Cuprins

1. Introducere……………………………………………………………………… ………… ……………………………… ..1
2. Extragerea de date (Data Mining – DM)………………………………………………………… .………… ….3
2.1 Descoperirea de cunoștințe din baze de date………………………………………………… …..4
2.2 Metode clasice de data mining…………………………………………………………………………… .….5
2.3 Clasificarea tipurilor de data mining………………………………………………………………… ….….7
3. Cluster izarea ..…………………………………………………………………………………………… .………………… .9
3.1 Algoritmul K -MEANS …………………………………………………………………… .………………………..10
3.2 Algoritmul DBSCAN.……………………………………… .………………………………………………………12
4. Aplicație ………………………………………………………………… .……………………………………………………17
4.1 Structura datelor ……………………………………………… .…………………………………………………..17
4.2 Introducerea datelor ………………………………………………… .…………………………………………..18
4.3 Calcularea statisticilor ……………………………………………………… .……………………………………19
4.4 Afișarea hărții …………………… ……………………………………………… .…………………………………..21
4.5 Căutare informații …………………………………………………………… ..……………………………………25
4.6 Implementarea algoritmului DBSCAN ……………………………………………………………… ..……26
4.7 Implementarea algoritmului K -MEANS ……………………………………………………… .………….28
4.8 Comparație între algoritmul DBS CAN și K -MEANS ……………………………………… …………30
5. Concluzii………………………………………………………… ……………………………………………………………34
BIBLIOGRAFIE

1
CAPITOLUL 1. INTRODUCERE

Similar cu multe domenii de cercetare și aplicare, geografia s -a mutat dintr -o categorie de
date cu o calitate inferioară și cu un calcul sărac la o categorie cu un mediu bogat de date și un
calcul bogat. Domeniul de aplicare, de acoperire, precum și volumul de seturi de date georgrafice
digitale sunt în c reștere rapidă. Odată cu această creștere a dimensiunilro bazelor de date , cât și
în aplicațiile de baze de date din diferite domenii , vom putea examina extragerea automată a
cunoștințelor din bazele de date de mari dimensiuni. Mulți cercetători au consi derat acest
domeniu geografic unui semnificativ de investigat.[1]
Această lucrare de cercetare se referă la domeniul de exploatare a datelor geografice și
descoperirea de cunoștințe geografice într -un mediu bogat de date. Se vor înregistra multe
procese se mnificative în descoperirea de cunoștințe geografice (Geographic knowledge
discovery GKD) și tehnici noi pentru stocarea de date geografice (Geographic data warehousing
GDW) în extragerea de date spațiale și vizualizare geografică. În această secțiune se v or prezenta
și descoperirile de cunoștințe și extragerea datelor (DM). În descoperirea de cunoștințe din baza
de date (KDD) se vor evidenția obiectivele sale generale și relația sa cu domeniul statisticii și a
procesului științific general. Se vor prezenta etapele prelucrării KDD și extragerea datelor.
Descoperirea de cunoștințe din bazele de date (KDD) sau extragerea de date (DM) reprezintă
efortul de a întelege, a analiza și de a utiliza o cantitate imensă de date disponibile.
Procesul de descoperirea de cunoștințe din bazele de date (KDD) a fost conceput în anul
1989, pentru desemnarea unei zone de cercetare bazată pe metode de Data Mining (DM),
recunoașterea formelor și tehnici de baze de date în contextul bazelor de date de marimi mari.
Acest proces est e considerat unul însemnat de identificare a unor tipare de date valide, potențial
folositoare.
Clustering -ul este o abordare pentru a analiza date geografice temporale la un nivel mai
ridicat de abstractizare prin gruparea datelor conform similarității sa le în clustere semnificative.
Clusterul spațio -temporal este un proces de grupare a obiectelor pe baza similarității lor spațială
și temporală. Este relativ un subcâmp nou al extragerii de date,care a câștigat popularitate mare
în special în domeniul știin țelor informaționale geografice din cauza omniprezenței de toate
tipurile de dispozitive bazate pe locație sau mediu. Această poziție de înregistrare, de timp și/sau
de proprietăți de mediu ale unui obiect sau set de obiecte în timp real.[1]
Există un algo ritm al clusterului denumit DBSCAN (Density -based spatial clustering of
applications with noise). Acest algoritm este eficient pentru bazele de date spațiale de dimensiuni
mari. Se va efectua o evaluare experimentală a eficienței și eficacității DBSCAN fol osing datele
sintetice. Acest algoritm va fi proiectat pentru a descoperi clusterul și zgomotul de la o bază de
date spațială.

2
Ca o consecință,diferite tipuri și cantități mari de date spațio -temporale au devenit
disponibile și introduc noi provocări pentr u analiza datelor și necesită noi metode de descoperire
de cunoștințe.[1]
Proprietățile geografice și temporale sunt un aspect cheie al multor probleme de analiză
de date de afaceri, guvern și știință. Prin umare în analiza geografică temporală este trecer ea de
la dobândirea datelor corecte spre analiza pe scară largă a datelor disponibile.[1]
Mai multe forme diferite ale tipurilor de date spațio -temporale sunt disponibile în aplicații
reale. În timp ce toate au disponibilitatea unor tipuri de aspecte spați ale și temporale, amploarea
unor astfel de informații și modul în care acestea sunt legate pot combina mai multe tipuri diferite
de obiecte de date.[1]
Poate exista o clasificare în sensul unor tipuri de date , bazate pe două dimensiuni[1]:
 Dimensiunea tem porală – reprezintă în ce măsură este evoluția obiectului
capturat de date. În contexte mai puțin complexe, fiecare obiect poate
schimba starea ei, dar numai valoarea sa cea mai recentă este cunoscută,
rezultă că nu există niciun fel de cunoștințe despre i storia sa din trecut.
Exemplu : o actualizare instantanee a datelor[1]
 Dimensiunea spațială – descrie dacă obiectele considerate sunt asociate într –
o locație fixă.
Exemplu : informațiile colectate de senzorii fixați la sol sau se pot deplasa, iar
locația lor este dinamică și se poate schimba în timp.[1]

3
CAPITOLUL 2. EXTRAGEREA DE DATE ( DATA MINING )

Data mining reprezintă procesul de analiza a unor seturi de date, de dimensiuni foarte
mari, cu scopul de a descoperi tipare sau relații ascunse, o modalitate de a descoperi un nou
înțeles al datelor.
Termenul de proces în cadrul data mining poate fi clasificat în do uă categorii: extragerea
într-un mod descriptiv al datelor și extragerea într -un mod predictiv al datelor. În pasul de analiză
a datelor utilizatorii au o idee despre atributele care pot fi interesante pentru procesul de
extragere de cunoștințe.
Funcția pr incipală a DM este de a extrage modele de cunoștințe din date. Data mining
utilizează o varietate de algoritmi din statistică, recunoașterea formelor, clasificare, vizualizarea
datelor etc. Varietatea de algoritmi poate fi grupată în principalele component e ale data mining.
Numărul componentelor poate fi diferit în funcție de fiecare autor dar în principal sunt
următoarele:
o Modelul de alegere a datelor semnificative din baza de date – se reprezintă ca în orice
model informatic printr -o funcție într -un spați u unidimensional sau multidimensional,
care depinde de parametrii. Poate fi reprezentat fie ca o funcție de probabilitate, fie ca o
funcție liniară de parametrii etc. Obținerea modelului se realizează prin diferiți algoritmi,
cum ar fi cei de clasificare ș i clusterizare.[2][3]
o Criteriile de preferință – de preprocesare a datelor care sunt semnificative pentru
căutarea curentă, care pot fi de natură diferită, unele se pot baza pe ordonare, altele pe
interpolare sau pe aproximare, aceasta fiind cea mai bună s oluție.[2][3]
o Algoritmi de selecție – sunt algoritmii de determinare a rezultatelor dorite pe baza datelor
selectate, care conduc la selectarea a trei elemente importante care apar în data mining,
fiind următoarele: tiparul, care selectează din baza de modele,datele care se selectează
din b aza de date și constituie parametrii și criteriul de preferință care selectează din baza
de criterii.[2][3]
o Stabilirea abaterilor – constă în general în acei algoritmi de determinare a deviației și
stabilității. O categorie specifică de astfel de algoritmi sunt cei statistici, prin care se
stabilesc abaterile modelului față de ideal.[2][3]
Pentru că extragerea de date (Data Mining) este partea centrală a procesului de
descoperire de cunoștințe din bazele de date (KDD), termenii data mining și descoperirea d e
cunoștințe din baze de date au fost utilizați alternativ de mulți cercetători din domeniu.

4
2.1 DESCOPERIREA DE CUNOȘTINȚE DIN BAZE DE DATE
(KNOWLEDGE DISCOVERY IN DATABASES – KDD)

În cadrul Fig. 1. se consideră că extragerea cunoștințelor se realizea ză în următoarele
etape în procesul KDD:
a) Dezvoltarea și înțelegerea domeniului aplicației – această etapă include studierea
anterioară a cunoștințelor relevante și a scopului utilizatorului privind
descoperirea cunoștințelor. Definirea clară a obiectivelor ce vor fi urmărite în
concordanță cu scopul cercetării.[3]
b) Crearea și stabilirea unui set de date – această etapă constă în selectarea datelor
prin concentrarea pe un subset de variabile(atribute) sau eșantioane de date pe
care dorim să le interpretăm. Ac eastă etapă presupune interogarea datelor
existente, pentru selectarea subsetului dorit.[3]
c) Curățirea datelor și prelucrarea datelor – este un proces complex, specific
depozitelor de date. Se elimină datele eronate, datele duplicate, se reduc
dimensiunile, se stabilește modul de înlocuire a datelor care lipsesc ș.a. Tot în
această etapă se precizează modul în care vor fi manipulate câmpurile cu valori
lipsă.[3]
d) Aplicarea procedurilor de Data mining – această etapă fiind cea mai important al
procesului KDD. Se decide care dintre modelele și parametrii acesteia sunt
corespunzători situației date.[3]
e) Interpretarea și evaluarea rezultatelor din punctul de vedere al utilizatorului – este
o fază de decizie. Sunt vizualizate, validate și interpretate rezultatele ob ținute , în
cazul în care utilizatorul nu este mulțumit de rezultat , poate relua oricare dintre
fazele precedente.[3]
f) Utilizarea cunoștințelor descoperite – aceasta este ultima etapă al procesului KDD.
Această utilizare se realizează fie prin utilizarea c unoștințelor pentru susținerea
performanțelor sistemului , fie constă prin rapoarte simple adresate celor
interesați.[3]
KDD și Data Mining este un domeniu interdisciplinar care dezvoltă procese și algoritmi
pentru descoperirea cunoștințelor nestructurate, ce constau în categorii, concepte, relații și
tendințe.

5

Fig. 1. Etapele procesului KDD (Knowledge discovery in databases)

2.2 METODE CLASICE DE DATA MINING

Printre metodele clasice folosite pentru data mining se numără metodele statistice,
metodele care folosesc informații de clustering. Se presupun parcurgerea următoarelor etape
principale:
 Formalizarea datelor obținute din investigații necesare modelării procesului studiat
 Dezvoltarea matematică a modelului în scopul fundamentării predicțiilor fenomenului
studiat
 Confruntarea predicțiilor unui model matematic cu informațiile statistice
 Elaborarea concluziilor rezultate în urma unei analizei.
Metodele data mining pot fi împărțite după scopul funcțional în două categorii:
 metode descriptive – permit descrierea și explicarea fenomenelor
caracteristice sistemului studiat pe baza modelelor descoperite. DATE
DEPOZIT DE
DATE
DATE
PRELUCRATE
DATE
TRANSFORMA TEMODELCUNOȘTINȚE
Prelucrare

6
 metode predictive – sunt utilizate în realizarea de previziu ni referitoare la
sistemul studiat.
Printre metodele clasice ce le mai folosite se numără:
 Regresia – în cazul în care variabilele sunt numerice aceste metode sunt folosite
pentru a anticipa valoarea unui răspuns cu una sau mai multe variabile predictive.
Există diverse forme de regresie, precum lineară , multiplă, polinomială,
nonparametrică și robustă.[5]
 Modele lineare generalizate – aceste modele și modelele aditive generalizate
permit stabilirea unei relații între o variabilă de răspuns categoric și o s erie de
variabile predictive în același fel în care o variabilă de răspuns numeric folosește
regresia lineară.[5]
 Arborii de regresie – acești arbori sunt binari. Ei pot fi folosiți pentru clasificare și
predicție. Un arbore de regresie e asemănător unui a rbore de decizie, pentru că
testele se fac la nivelul nodurilor interne.[5]
 Analiza variabilității – tehnicile analizează datele experimentale pentru două sau
mai multe populații descrise de un răspuns numeric variabil și una sau mai multe
variabile catego riale.[4]
 Modele cu efect mixt – sunt folosite pentru analizarea datelor grupate. Aceste date
pot fi clasificate cu ajutorul a uneia sau a mai multor variabile de grupare.
 Analiza de factor – este folosită pentru determinarea de variabile care sunt
combina te pentru a genera un anumit factor.[4]
 Analiza discriminantă – este folosită pentru anticiparea unei variabile de răspuns
categorial. Această procedură încearcă să determine funcții discriminante care fac
deosebirea între grupurile definite de variabila d e răspuns. Această tehnică este
folosită în științele sociale.[4]
 Seriile de timp – sunt diverse tehnici de statistică utilizate pentru analizarea
datelor de tip serii de timp.[4]
În concluzie , tehnicile data mining permit descoperirea de segmente, cluste re, subgrupuri
care permit clasificarea și înțelegerea mai bună a coordonatelor fenomenului.

7
2.3 CLASIFICAREA TIPURILOR DE DATA MINING

Clasificarea unor sisteme data mining se realizează în funcție de criteriile stabilite astfel
încât să poată oferi fiecărui utilizator posibilitatea de a identifica cu ușurință și potrivit pentru
necesitățile unui sistem data mining. Principalele criterii de clasificare ale sistemului sunt :
o Criteriul în funcție de depozitul de date – acesta conține datele asupra căror a se
aplică procesul data mining. Acestea pot fi de două tipuri : modelul de date – este
construit depozitul de date, data warehouse, obiecturale, relațional -obiectual sau
heterogene[4]
o Tipul datelor manipulate – se deosebesc sistemele data mining , tempor ale,
secvențiale, text, multimedia, pentru fluxuri și secvențe de date și pentru Web[4]
o Criteriul în funcție de numărul de tehnici – reprezintă tehnici data mining integrate
pentru îndeplinirea funcțiilor, caz în care se deosebesc sistemele data mining
care[4]:
– Integrează o singură categorie de tehnici data mining care realizează
funcțiile pentru descoperirea unei singure categorii de modele de date. Exemplu:
tehnici pentru caracterizarea și discriminarea datelor.
– Integrează tehnici data mining multiple car e realizează funcțiile pentru
răspunderea așteptărilor diferiților utilizator și/sau descoperirea categoriilor variate
de modele de date necesare în diverse aplicații.
o Criteriul în funcție de nivelul de abstracție – se prelucrează datele, caz în care se
deosebesc sistemele data mining. Acestea asigură extragerea modelelor de date.
Se pot extrage pe un singur nivel de abstracție, corespunzător unui singur nivel de
detaliu specificat de utilizator. În acel nivel se obțin cunoștințe generalizate la un
nivel ri dicat de abstracție. Se mai pot extrage și pe mai multe nivele de abstracție,
corespunzătoare nivelelor de detaliu solicitate de utilizator, acestea fiind
sistemele data mining avansate.[4]
o Criteriul în funcție de frecvența de aplicare – dacă procesul data mining se
deosebește de sistemele data mining atunci datele sunt prelucrate astfel[4]:
– într-un mod regulat (frecvent) – este specific pentru extragerea modelelor
de date respectate de datele din setul de date selectat de utilizator pentru analiză.
Tehnicile data mining de tip caracterizare și discriminare,clasificare și
predicție,asociație și corelație prelucrează datele cu regularitate, respingând
excepțiile.
– într-un mod neregulat (aplicat la nevoie) – este specific pentru extrage rea
datelor aflate în afara modelelor de date respectate de date din setul de date selectat

8
de utilizator pentru analiză, acestea fiind considerate excepții. În cazul de față se
folosesc tehnicile data mining de analiză a excepțiilor.
o Criteriul în funcție de modul de interacțiune – nu interacționează cu utilizatorul
implicat pe durata procesului data mining (independente) sau interacționează cu
utilizatorul implicat pe durata procesului data mining(interactiv), această
interacțiune fiind bazată pe interogar e(Query).[4]
o Criteriul în funcție de metoda de analiză – este structurat în două părți. Prima parte
se referă la modelul de date în jurul căruia este construit depozitul de date care
conține datele asupra cărora se aplică procesul data mining. Poate fi pen tru baza
de date bidimensional sau pentru data warehouse multidimensional. A doua parte
se referă la forma de analiză a datelor asupra cărora se aplică procesul data
mining.[4]
o Criteriul în funcție de domeniul de aplicabilitate – sunt adaptate la domeniile de
activitate care utilizează forme avansate de analiză a datelor.[4]

9
CAPITOLUL 3. CLUSTERIZAREA

Scopul învățării nesupervizate (Unsupervised learning) este definit de necesitatea de
explorare a datelor pentru descoperirea unor strucuri esențiale. Utilizatorul explorează datele cu
scopul de a găsi strucuri noi, interesante și folositoare. Printre cele mai importante metode ale
învățării nesupervizate este clusterizarea, care organizează datele în grupuri similare numite
clustere, astfel încât instanțele dintr -un grup sunt similare dintr -o anumită perspectivă și total
diferite față de datele din celelalte grupuri.[6]
Această metodă statistică este folosită pentru a grupa date multidimensionale în grupe
(clustere) definite algoritmic. Această metodă este utilă pentru sumarizarea unor cantități mari
de informație, fiecare grupă reprezentând mai multe puncte având caracteristici similar e.
Clusterele distincte nu se suprapun(disjuncte).[6]
Clusterizarea reprezintă procesul de organizare a datelor dintr -o colecție nestructurată în
grupuri numite clustere ale căror membrii sunt similari într -un anumit fel.[6]
Calitatea diferitelor metode de clusterizare se diferențiază prin folosirea funcțiilor
obiectiv. Calitatea clusterizării se referă la omogenitatea în cadrul grupurilor și separabilitatea
între grupurile rezultate în urma procesului de clusterizare. Procesul de învățare nesupervizată
este unul ciclic.[6]
Similaritatea reprezintă metrica care reflectă potrivirea între două date, două șiruri text
sau caracteristici.[6]
Clusterizarea are nevoie de o funcție de similitiduine pentru a măsura cât de similiare sunt
două date.[6]

10

Fig. 2. Procesul de învățare nesupervizată

3.1 ALGORITMUL K -MEANS

K-means este o metodă de gruparea (clustering) observațiilor într -un anumit număr
de clustere disjuncte(nesuprapuse). Litera ”K” se referă la numărul de clustere specificat. Există
diverse măsuri de distanță pentru a determina care este observația care se anexează în fiecare
cluster. Algo ritmul are ca scop reducerea la minim măsura dintre centrul cluster -ului și observația
dată prin alăturarea iterativă, o obsevație a oricărui cluster și încetează când se realizează cea
mai mică măsură de distanță.[6]
K-means este cel mai utilizat și foar te simplu algoritm partițional și a devenit
exponentul unei întregi categorii de algoritmi. Caracteristicile principale ale algoritmului sunt :
simplicitatea implementării, scalabilitate, eficiență și viteza de convergență.[6]
Acest algoritm este un algori tm popular care ține datele în memoria centrală. Pe
acest algoritm se bazează alți algoritmi de clustering. Exemplu : BFR [6]
Algoritmul K -means pentru găsirea a ”K” clustere.[6] Date •Prelucrarea
Algoritm de
învățare
•Clusterizarea
Clustere
Evaluare
clustere•Evaluare &
Validare
Eficiență
& Eficacitate

11
1. Selectarea a K puncte ca fiind centroidele inițiale
2. Distribuirea tuturor punc telor câtre cel mai apropiat centroid
3. Recalcularea centroidului fiecărui cluster
4. Se repetă pasul 2 și 3 până când centroidele nu se mai schimbă.
Algoritmul K -means alege K centroizi de cluster și asignează punctele acestea alegând
centroidul cel mai apropi at de punctul respectiv. Pe măsură ce punctele sunt asignare la un
cluster, centroidul acestuia poate migra.[6]
Centroidul unui cluster este centrul de greutate al clusterului. El nu este de obicei
unul din punctele care formează clusterul ci un punct într e ele în spațiul euclidian respectiv.
Conceptul de centroid nu este valabil decât în cazul clusteringului în spații euclidiene.[6]

Fig. 3. Schema logică a algoritmului K -means nesupervizat

Algoritmul K -means are marele avantaj că este ușor de implementat și eficient, dar
are și câteva mari dezavantajuri. Primul dezavantaj constă în posibilitatea de a fi foarte lent din
moment ce în fiecare pas distanța dintre fiecare dată și fiecare cluster trebuie calculată, afectând
astfel timpul de execuție. O posibilă soluție este calcularea centroizilor în fiecare pas și
contorizarea datelor din fiecare cluster. Al doilea dezavantaj este că această metodă e foarte
sensibilă la numărul și inițializarea cl usterelor inițiale, algoritmul poate să furnizeze doar un optim
Inițializarea
parametrilor
Calcularea distanțelor
față de centroid și
reîmpărțirea punctelor
Recalcularea
centroidelor
Afișarea
rezultatelor
Da Nu Repetăm pașii

12
local. Pentru creșterea șansei determinării optimului global, algoritmul poate fi repetat cu centre
de clustere diferite.[7]
Pentru selectarea clusterelor inițiale s -au propus metodele: aleger ea punctului cel
mai îndepărtat de ultimul centroid ales, o clusterizare ierarhică suplimentară pentru fiecare
centroid sau selectarea manuală a valorilor de start. Ultimul dezavantaj constă în faptul că
algoritmul este vulnerabil la valorile extreme, marg inale.[7]

3.2 ALGORITMUL DBSCAN (DENSITY -BASED SPATIAL
CLUSTERING OF APPLICATIONS DATABASES WITH NOISE – DBSCAN)

În acest capitol se descrie algoritmul DBSCAN, un algoritm de clustering pe bază de
densitate, introdus în Ester în anul 1996, care poate fi utilizat pentru a identifica clustere de orice
formă în setul de date care conțin zgomot și valori.[8]
În figura 4 se pot identifica mai multe clustere, împreună cu mai multe puncte de zgomot,
din cauza diferențelor de densitatea a punctelor.[8]

Fig. 4. Tipuri de clustere
Algoritmul DBSCAN poate identifica cu succes clustere cu un volum mare de obiecte, doar
prin introducerea unui singur parametru.[8]
Caracteristicile acestui algoritm sunt[8]:
 Identificarea zgomotului și eliminarea acestuia
 Viteza de lucru mare, complexitatea algoritmului fiind aproape liniară
 Recunoașterea clusterelor cu forme arbitrare
În DBSCAN densitatea asociată cu un punct este obținut prin numărarea numărului de
puncte dintr -o regiune cu o rază specificată în jurul punctului . Punctele cu o densitate de peste
un prag specificat sunt construite ca grupuri (clustere). Printre algoritmii de grupare existente,

13
algoritmul DBSCAN are capacitatea de a descoperi diferite forme ale clusterului ca de exemplu
liniar, concav, oval etc. S pre deosebire de alți algoritmi de clustering, algoritmul DBSCAN nu cere
specificarea numărului de clustere și are capacitate de prelucrare a bazelor de date foarte mari.
Algoritmul DBSCAN poate grupa datele spațio -temporale în funcție de atributele sale non-
spațiale, temporale și spațiale. DBSCAN nu poate detecta unele puncte de zgomot atunci când
există clustere de diferite densități.[8]
DBSCAN este un algoritm de clusterizare bazat pe densitate, în care clusterele sunt regiuni
în care obiectele au dens itate mare, separate de regiuni de densitate mică.
Fig 5 . Core point , border point și outlier

Principiul de funcționare
Densitatea este estimată pentru fiecare obiect ( punct ) numărând toate punctele situate
la distanță 𝜀 în jurul acelui punct.

Fig 6 . Parametrul Eps ( 𝜀 )
Algoritmul DBSCAN clasifică punctele în trei categorii:
 Core points ( puncte de bază ) – poziționate în interiorul unui cluster. Un punct
este un core point dacă numărul de puncte din vecinătatea lui ( aflate la distanță

14
mai mica decât 𝜀 față de el ) este mai mare decât MinPts. MinPts reprezintă o
limită predefinită.
 Border points ( puncte de graniță ) – sunt puncte care nu sunt core points ( nu au
cel puțin MinPts puncte situate la distanță mai mică decât 𝜀 față de ele ) , dar sunt
în vecinătatea unui core point.
 Noise points ( puncte de zgomot ) – sunt punctele care nu sunt nici core points ,
nici border points.

Fig 7 . Pseudocod algoritm DBSCAN

Explicație : Cât timp există puncte neclasificate
1. Găseșt e vecinii punctului ( la distanță < 𝜀 față de el )
2. Dacă numărul de vecini este mai mare ca MinPts : pornește un nou cluster
din acel punct și se încearcă extinderea clusterului analizând regiunile lui
și etichetează punctele pe măsură ce sunt parcurse
End ( se sfârșește comanda while )
End ( se sfârșește comanda if )
În general , punctele de graniță ( border points ) au semnificativ mai puține puncte în
vecinătatea lor ( la distanța mai mică ca 𝜀 față de ele ) decât punctele de bază ( core points ).

15

Fig 8 . Algoritmul DBSCAN cu MinPts = 3

Directly density reachable reprezintă un punct p care este direct accesibil din q dacă p se
află în vecinătatea lui q și dacă q este core point. Density reachable – poți ajunge la el din core
point prin intermediul altui punct.

Fig 9 . Density reachable

16
Pentru a descoperi un cluster , algoritmul începe cu un punct arbitrar p și preia toate
punctele density – reachable din el ( vecinii și celelalte puncte în care pot să ajung din p utilizând
vecinii ) .

Fig 10 . Density reachable și directly density reachable
Dacă punctul p este core point ( punct de bază ) , creez un cluster.
Dacă punctul p este border point ( punc t de graniță ) , nu există nicio analizare a niciun
punct density reachable , următorul pas fiind analizarea altui punct. Deci dacă punctul p are mai
mult de MinPts vecini la distanță 𝜀 , atunci este core point deci pornesc un cluster din acel punct.
Veci nii lui îi introduc într -o coadă ( un array ) și sunt clasificați progresiv ( observ dacă există core
points sau border points ). Când s -a finalizat parcurgerea cozii ( coada este goală , toate punctele
din ea au fost clasificate ) , clusterul este complet , drept urmare se trece la analiza altui punct.
Dacă punctul aparține deja unui cluster , îl sărim și trecem la următorul punct.

Fig 11 . Pseudocod Algoritm DBSCAN

Definim o funcție DBSCAN cu 3 parametrii și anume D, 𝜀, MinPts.
Inițializăm ClusterLabel cu valoarea 1 și urmează 2 pași :
Pasul 1 : Pentru orice punct care aparține setului de date D rezultă etichetă ( punct ) =
UNCLASSIFIED

17
END ( se sfârșește pasul 1 )
Pasul 2 : Pentru orice punct p din setul de date D. Dacă etichetă ( punct ) =
UNCLASSIFIED . Dacă extindeCluster (D,punct,ClusterLabel, 𝜀 ,MinPts) = = true. ClusterLabel ++;
– se trece la clusterul următor.
END ( se sfârșește primul if)
END ( se sfârșește al doilea if )
END ( se sfârșește pasul 2 )

CAPITOLUL 4. APLICAȚIE

Aplicația de monitorizare a nașterilor pentru specii de animale oferă facilități pentru
clusterizarea evenimentelor corespunzătoare unei specii de interes în funcție de poziția
geografică, pentru salvarea a hărților generate, cu scopul menținerii unui istoric, oferind
posibilitatea de căutare a evenimentelor în funcție de localitate și posibilitatea de af ișare a
statisticilor.
Pentru că sunt analizate date spațiale (coordonate geografice), algoritmul de clusterizare
utilizat trebuie să proceseze corect clusterele indiferent de forma acestora. Algoritmul DBSCAN
se bazează pe densitatea obiectelor care compu n setul de date: în interiorul clusterelor,
densitatea obiectelor este mai mare decât în exteriorul acestora. De aceea, aplicația de
monitorizare a nașterilor pentru specii de animale implementează algoritmul DBSCAN.

4.1 STRUCTURA DATELOR
Informațiile sunt st ocate într-o bază de date MySQL. Fiecare specie este identificată
printr -un id unic și are asociată o denumire. Evidența speciilor este menținută în tabela specii .
Pentru fiecare specie este menținută o listă de evenimente (nașteri). Fiecare eveniment
are asoci ate data și locația geografică definită prin latitudine și longitudine. Pot exista mai multe
evenimente cu aceeași dată și locație geografică, fiecare înregistrare reprezentând o naștere în
zona respectivă.
Tabelul hărți_salvate conține informațiile corespunzătoare unei hărți clusterizate, fiecare
înregistrare fiind caracterizată de rază, id_cluster, latitudine, longitudine, nr_nașteri.

18

4.2 INTRODUCEREA DATELOR

Evenimentele corespunzătoare unei specii sunt importate din fișiere .xls utilizând
bibliot eca PHPExcel. Fișierele .xls trebuie să respecte următorul format: id_specie,
data_eveniment, latitudine, longitudine. Fiecare înregistrare definește o naștere care a avut loc
la data data_eveniment în locația definită prin coordonatele geografice specific ate. Fișierul .xls
trebuie să conțină un singur sheet.
Limitele fișierului .xls (utimul rând și ultima coloană) sunt extrase utilizând funcțiile oferite
de biblioteca PHPExcel: getHighestRow() și getHighestColumn().
Fiecare rând din fișierul cu evenimente este convertit într -un array PHP utilizând funcția
PHPExcel rangeToArray(). Informațiile din array sunt importate în tabela evenimente_specii .

Fig.12 – Citire fișier .xls evenimente

19
4.3 CALCULAREA STATISTICILOR

Pentru a oferi o vedere de ansamblu asupra nașterilor pe specii, la secțiunea Statistici
sunt afișate primele trei cele mai multe nașteri (indiferent de specie) și numărul total de nașteri
pentru fiecare specie introdusă în sistem.
Biblioteca Canvasjs ofer ă suport pentru crearea a 30 de tipuri de grafice diferite și pentru
afișarea acestora în mod responsive (adaptabil pentru display -uri de orice dimensiune) – printre
care bar și pie charts, utilizate în aplicație.
La încărcarea paginii ($(document).ready() ) este apelat, cu ajutorul AJAX
(Asynchronous JavaScript And XML), scriptul ajaxApp.php , care preia evenimentele din tabelul
evenimente_specii si calculează statisticile, care sunt trimise apoi ca răspuns către javascript
(success: function(response)). Pe baza acestui răspuns sunt construite datele de input pentru
API-ul Canvasjs: array -uri care conțin dicționare cu cheile y (valoarea numerică pentru o bară din
grafic) și label (legenda corespunzătoare barei din grafic). Porțiunea de cod client pentru
gene rarea stat isticilor este afișată în Fig. 13 .

20

Fig. 13 – Construcție și afișare grafice statisitici

Porțiunea de cod server -side pentru calculul statisticilor necesare graficului care afișează
cele mai mult e nașteri este afișată în Fig. 14 . Se observă că parametrii de interes (nr_nașteri,
nume_specie, latitudine, longitudine ) pentru fiecare grupă de evenimente sunt salvați în array -ul
$results_nașteri. Array -ul final este trimis în form at JSON către javascript (Fig. 15 ).

21

Fig. 14 – Calcul statistici – cod server -side

Fig. 15 – Rezultate finale in format JSON

4.4 AFIȘAREA HĂRȚII

Pentru afișarea hărții, poziționarea markerelor corespunzătoare evenimentelor
(nașterilor ) și implementarea că utării î n funcție de localitate sunt utilizate API -urile puse la
dispoziție de Google: Google Maps API si Google Maps Geocoding API.
În Fig. 1 6 este apelat API -ul Google Maps. Parametrul callb ack execută funcția initMap
după încărcarea API-ului.

Fig. 1 6 – Apelarea API -ului Google Maps

22

În funcție de parametrul doDbscan, initMap încarcă o hartă goală sau apelează scriptul
pentru clusterizare de pe server, pozitionând pe hartă markerele corespunzătoare nașterilor, în
culorile aferente (fiecare culoare repr ezintă un cluster).
Funcția initMap făr ă ajax este prezentată în Fig. 17 .

Fig. 17 – Funcția initMap

Id-ul speciei pentru care se dorește cluste rizarea nașterilor, raza (eps) ș i parametrul
doDbscan pot fi trimise către server fără a fi necesară reîncărcarea paginii, utilizând AJAX
(Asynchronous JavaScript And XML). În momentul declanșării unui eveniment (click pe butonul
Clusterizează ), javascript trimite un request către server, parsează răspunsul și updatează pagina
în conformitate cu acesta.
Biblioteca jQuery pune la dispoziție o modalitate simplă de execuție a ajax -urilor: funcția
$.ajax().
Request -ul transmis către server este de tip POST.
În Fig. 18 este afișată implementarea ajax -ului. URL -ul apelat est e ajaxApp.php : acest
script preia din baza de date evenimentele corespunzătoare speciei selectate (parametrul
id_specie, transmis prin cererea de tip POST) și apelează scriptul dbscan_simplu.php, care
clusterizează datele și returnează, pentru fiecare even iment identificat prin latitudine și
longitudine, culoarea clusterului din care evenimentul respectiv face parte.

23

Fig. 18 – Ajax în funcția initMap

Markerele sunt poziționate pe hartă în funcție de coordonatele returnate de scriptul PHP
de pe server și sunt colorate corespunzător cluste rului din care fac parte (Fig. 19 ). Variabila
responses este un array javascript care conține detaliile aferente fiecărui marker. Fiecare marker
este adăugat la un array pentru operațiile ulterioare.

Fig. 19 – Poziționare markere

24

Dicționarul statistici însumează nașterile din locațiile geografice care fac parte din același
cluster.
Pentru fiecare marker este creată o fereastră informativă. Fiecărui marker îi este asociat
un eveniment astfel încât, la execuția unui click pe markerul respectiv, este afișată fereastra
informativă corespunzătoare lui.

Fig. 20 Codul pentru afișarea ferestrei informative

25

Fig. 21 – Fereastră informativă

Utilizând API -ul Canvasjs, este afișat numărul total de nașteri corespunzător fiecărui
cluster, într -un grafic de tip bar -chart, fiecare bară păstrând culoarea clusterului respectiv.
Valorile și culorile specifice sunt preluate din dicționarul statistici – culorile fiind reprezentate de
cheile dicționarului.
Utilizato rul poate salva harta pentru a menține istoricul nașterilor de interes.
Datele aferente unei hărți sunt salvate în tabelul harti_salvate .

4.5 CĂUTARE INFORMAȚII

Pentru regăsirea informațiilor aferente unei specii pentru o locație geografică sunt
necesare se lectarea speciei de interes, introducerea localității de interes (ex.: București, Cluj,
Oradea) și a acoperirii î n km (Raza).
Utilizând API -ul Google Maps Geocoding API, pus la dispoziție de Google, locațiile sunt
translatate automat în coordonate geografice, îmbunătățind experiența utilizatorului.

26

Fig. 22 – Translatarea unei adrese în coordonate geografice

Cererea de translatare pentru locația $locatie (preluată în variabila globala $ _POST din
formular) este trimisă către API -ul Google Maps Geocoding prin curl. Modulul PHP pentru
transferul informațiilor prin curl, PHP/cURL, utilizează biblioteca libcurl, care oferă suport pentru
comunicația cu serverul prin diferite protocoale (http, ldap, https). Pașii implementați sunt:
inițializarea unei sesiuni de tip curl, setarea parametrilor sesiunii, interschimbarea informațiilor
client -server prin execuția sesiunii și închiderea sesiunii. Sesiunea este inițializată apelând
funcția curl_init() . Parametrii aferenți sesiunii sunt setați utilizând funcția curl_setopt() .
Rezultatele execuției sesiunii trebuie salvate într -o variabilă în loc să fie afișate direct pe ecran,
de aceea parametrul CUR LOPT_RETURNTRASFER este setat true .
Rezultatele primite de la server sunt în format JSON. Funcția json_decode() transformă
rezultatul într -un obiect PHP, din care sunt extrase latitudinea și longitudinea corespunzătoare
locației specificate de către utiliz ator.

4.6 IMPLEMENTAREA ALGORITMULUI DBSCAN

DBSCAN este un algoritm de clusterizare bazat pe densitate, formând clustere în regiunile
cu un număr mare de obiecte. Algoritmul primește ca parametri minPts, numărul minim de
vecini ai unui obiect pentru care acesta devine Core Point și distanța minimă eps, raza în jurul
unui obiect.

27
Densitatea unui obiect este calculată numărând obiectele aflate la distanță cel puțin eps
față de obiectul respectiv.
Rezultate le obținute depind de valorile parametrilor minPts și eps.
Algoritmul DBSCAN este rezistent la zgomote și nu depinde de forma sau dimensiunea
clusterelor, avantaje utile pentru clusterizarea în funcție de poziția geografică.
Clasa Point definește un eveni ment în funcție de latitudine (x), longitudine (y), id -ul
clusterului din care face parte (inițial -1 pentru toate evenimentele, acestea fiind la început
neclasificate), lista de vecini și numărul de nașteri pentru poziția geografică respectivă.
Un punct p oate fi etichetat prin asignarea uneia dintre valorile predefinite ( -1:
UNCLASSIFIED, -2: NOISE, 1: CORE_POINT, 0: NOT_CORE_POINT) la proprietatea cluster_id.

Fig. 23 – Definire obiecte

28
Fiecare punct este analizat – dacă îndeplinește condiția de densitate (are cel puțin
MinPts vecini aflați la o distanță cel puțin eps față de el) este creat un nou cluster pornind din
punctul respectiv. Toți vecinii săi sunt adăugați la cluster.
Clusterul este extins apoi cu ajutorul vecinilor: fiecare vecin al vecinilor punctului Core
Point este analizat: daca este etichetat ca UNCLASSIFIED sau NOISE, este adăugat la clusterul
current, dar și la lista de vecini ai punctului Core Point.

4.7 IMPLEMENTAREA ALGORITMULUI K -MEANS

K-Means este unul dintre cei mai simpli algoritmi de învățare nesupervizată
(“unsupervised learning”) care rezolvă problema clusterizării bine cunoscute. Procedura
urmărește o modalitate simplă și ușoară de a clasifica u n set de date dat printr -un anumit număr
de clustere.
Explicarea pseudocodului algoritmului K -means:
a. Alegem aleator k puncte în spațiul definit de obiectele din baza de date , ce urmează a fi
clusterizare. Acestea sunt centroizii inițiali. De obicei încercăm să îi plasăm cât se poate
de departe unul de altul
b. Asociem fiecare obiect din mulțimea de date celui mai apropiat centroid ( în sensul
distanței considerate ), obținând astfel un prim grupaj.
c. Se calculează centrele de greutate ale clusterelor obți nute, definind astfel noii centroizi.
d. Reluăm procedeul și astfel cei k centroizi își vor schimba locul, până ajung în poziția dorită.
Asemenea implementării algoritmului DBSCAN și implementarea algoritmului K -means
are funcția initMap în care id-ul speciei pentru care se dorește clusterizarea nașterilor si
parametrul doKmeans pot fi trimise către server fără a fi necesară reîncărcarea paginii, utilizând
AJAX . În momentul declanșării unui eveniment (click pe butonul Clusterizează ), javascript trimite
un requ est către server, parsează răspunsul și updatează pagina în conformitate cu acesta.
Biblioteca jQuery pune la dispoziție o modalitate simplă de execuție a ajax -urilor: funcția
$.ajax(). Request -ul transmis catre server este de tip POST. Și ca identificato ri de clustere am
folosit id -urile centroizilor din array -ul centroizi.

29
Fig. 24 – Funcția initMap algoritm K -Means

În Fig. 25 este afișată implementarea ajax -ului. URL -ul apelat este ajaxApp.php : acest
script preia din baza de date evenimentele corespunzătoare speciei selectate (parametrul
id_specie, transmis prin cererea de tip POST) și apelează scriptul clusterizare_kmeans.php și unde
filtrez valorile nule.

Fig. 25 Ajax în funcția initMap imp lementat în algoritmul K -Means
Avantajele algoritmului K -Means :
 simplu de implementat și utilizat
 eficient ca timp
Dezavantajele algoritmului K -Means :
 este sensibil la outlieri (valorile aberante) pentru ca utilizează media
obiectelor dintr -un cluster pentru determinarea centroidului

30
 funcționează bine doar pe clustere sferice – nu clusterizează bine clustere
de forme arbitrare
 este sensibil la alegerea centroizilor inițiali ( ei fiind aleși random )
 este un algoritm randomizat și pentru același set de date poate afișa
rezultate diferite ( în funcție de cum a ales centroizii inițiali )

4.8 COMPARAȚIE ÎNTRE ALGORITMUL DBSCAN ȘI
ALGORITMUL K-MEANS

Fig. 26 Rezultat clusterizare algortimul DBSCAN
Selectăm specia ca fiind oaie , alegem o data de început și o dată de final. Pentru
algoritmul DBSCAN este nevoie de a alege raza (eps ,km) ca în cazul fig. 26 raza este 150. Dupa
completarea tuturor câmpurilor apăsăm pe butonul Clusterizează pentru a se fo rma clusterele în

31
urma executării algoritmului pe harta României. În caz că dorim ca această hartă să fie salvată
apasăm butonul salvează rezultat clusterizare prezentată ca în figura 27.
Fig. 27 Salvarea rezultatului hărții în urma executării algoritmulu i DBSCAN
Observăm că pe hartă în urma executării s -au format două clustere.

32

Fig. 28 Rezultat ul clusterizării algoritmul ui K-Means

Selectăm specia ca fiind oaie la fel ca la algoritmul DBSCAN , alegem o data de început și
o dată de final. Pentru algoritmul K -Means este nevoie de a preciza numărul de clustere ca în
cazul fig. 28 numărul de clustere este 3. Dupa completarea tuturor câm purilor apăsăm pe butonul
Clusterizează pentru a se forma clusterele în urma executării algoritmului pe harta României.
Observăm că în urma executării pe hartă s -au format trei clustere.
În cazul ambilor algoritmi avem un formular de adăugare specii ce conține doar
denumirea speciei ca în modelul din figura 29 , iar în partea dreaptă a paginii este afișată li sta cu
toate speciile prezente di n baza de date.

33

Fig. 29 Formular pentru adăugare de specie nouă

În cazul ambilor algoritmi putem încărca un nou set de date pentru anumite specii. Pentru
a efectua acest lucru trebuie să încărcăm un set de date de tip excel ( .xls ) în aplicație ca în
modelul din figura 30.

Fig. 30 Adăugare de date pentru diferite specii

34
CAPITOLUL 5. CONCLUZII

Data mining oferă promisiunea unui ajutor important pentru descoperirea tiparelor
ascunse în date.
Construirea modelelor este doar un pas în descoperirea cunoștințelor. Este vital să se
colecteze și să se pregătească datele într -un mod corect, și să se confrunt e modelele cu realitatea.
Cel mai bun model este adesea găsit după construirea mai multor modele de diferite tipuri sau
prin aplicarea de diferite tehnologii sau algoritmi.
Clustering -ul este o metodă principală în multe domenii, inclusiv în extragerea dat elor și
descoperirea de cunoștințe și statistici. Acest studiu prezintă un algoritm de clustering bazat pe
densitate construit prin algoritmul DBSCAN.
Spre deosebire de K -means, DBSCAN nu cere utilizatorului să specifice numărul de
clustere care urmează s ă fie generate. Algoritmul DBSCAN poate găsi orice formă a clusterelor.
Clusterul nu trebuie să fie circular. Algoritmul DBSCAN poate identifica valorile aberante.

35

B I B L I O G R A F I E
[1] Harvey J. Miller & Jiawei Han, Geographic Data Mining and Knowledge Discovery , Second
Edition , 2009
[2] Arun K. Pujari Data mining techniques Universities Press, 2001
[3] Fayyad U, et al., From Data Mining to Knowledge Discovery in Databases, Ai Magazine, 1996
[4] Han, J. & Kamber, M. Data mining concepts and techniques (2nd ed.), edited by Morgan
Kaufmann, V. Harinarayan, A. Rajaraman, J.D.Ulman. San Francisco, 2006
[5] Mosteller, F. & Tukey, J. W. (1977) Data Analysis and Regression. Reading, MA: Addison –
Wesley
[6] Barbara, D. An introduction to cluster analy sis for data mining , 2000
[7] Ordonez, C. & Omiecinski, E. (2004). Efficient Disk -Based K -Means Clustering for Relational
Databases. IEEE Trans. on Knowl. and Data Eng., 16(8), 909 -921
[8] Derya Birant & Alp Kut, ST -DBSCAN: An algorithm for clustering spa tial-temporal data,
Department of Computer Engineering, Dokuz Eylul University, Turkey, 13 March 2006
[9] JB MacQueen (1967): "Unele metode de clasificare și analiză a observațiilor
multivariate, Proceedings of the 5th Berkeley Symposium on Statistical Mat hematics and
Probability"