Bu yazimda sizlere gelismis bir clustering(gruplama) teknigi olan DBSCAN algoritmasini anlatmaya calisacagim. “Density Based Spatial Clustering of Applications with Noise” soz grubunun bas harflerinden ismini almaktadir.Bu algoritmada diger clustering tekniklerinden farkli olarak “point density” kavrami ile veriler iliskilendirilir.Point density, verilerin agirlikli olarak toplandigi bolgelerdir. Aslinda bizim tum veri kumesine baktigimizda gozumuze carpan veri altkumeleri topluluklari olarak dusunebiliriz. Asagidaki figurde kolayca 3 adet cluster oldugunu gorebiliyoruz.
Clusterlari olusturmamizi saglayan veri yogunlugunun hizli olarak degistigi yerlerdir diyebiliriz.Ayrica bu ufak topluluklarin disinda kalan noktalar ise gurultu(noise) olarak adlandirilmaktadir ve herhangi bir clustera dahil degillerdir.(Yukaridaki figurun sag tarafinda beyaz olarak kalmis noktalar ornek olarak verilebilir)
Diger clustering algoritmalarinda oldugu gibi veriler arasinda “komsuluk iliskisini” belirleyecek, clusterlarin olusmasini saglayacak bir “uzaklik” metrigi verilmelidir. Yine bu noktada hangi tip uzaklik metriginin verildigi onem kazanmaktadir.
Simdi bir dbscan clustering yapan bir classimiz oldugunu varsayalim ve bu classdan bir nesne olusturalim. Olusturacagimiz nesnenin constructor’i muhtemelen su sekilde olacaktir:
public DBSCANAlgorithm(DataPoint[] points,
Distance distance,
double epsilon,
int minPoints)
points : Clustering yapmak istedigimiz data seti ifade eder.
distance : Hangi “uzaklik” metrigini kullanmak istedigimizi bu parametre ile geceriz
epsilon : Genellikle cok kucuk pozitif bir sayiyi ifade eden parametredir. Zaten bilimsel terminolojide de bu anlama gelir. Bu deger datapoint p’nin epsilon komsuluk degerinin belirlenmesi icin kullanilir. p noktasi epsilon degerinden kucuk ya da degerine esit uzakliktaki noktalar ile komsudur. Bu yuzden “epsilon komsulugu” seklinde yazdim.
minpoints : bir p noktasini bulundugu yeri yaricapi epsilon degerinde olan bir cember ile cevreleyelim. Eger minpoints degeri kadar nokta bu cemberin icerisine giriyorsa bu durumda bu noktasi cekirdek(core) noktalardan bir oluyor. Bir tanim daha : Eger bir nokta bir clustera ait fakat cekirdek noktalardan biri degilse bu durumda sinir(border) noktalardan biri olmaktadir.
Asagidaki figurde bu tanimlamalar dogrultusunda p noktasi core point q noktasi ise border point’tir.
Simdi bu algoritma ile ilgili onemli bir tanimlamadan bahsedecegim. Yukaridaki figurde gordugunuz p ve q noktalari uzerinden tanimlamalari yapacagim.q noktasi epsilon ve minpoints degerleri cercevesinde p noktasindan direkt olarak yogunluk anlaminda ulasilabilir(density-reachable) Cunku yogunluk anlaminda ulasilabilir olunabilmesi icin asagidaki sartlar aranmaktadir :
1-q epsilon anlaminda p’nin komsusu olmalidir
2-p ‘nin minpointsden daha fazla epsilon komsusu olmalidir.
Bu bilgiler isiginda p noktasi q noktasindan bu anlamda yogunluk anlaminda ulasilabilir degildir.
Algoritma Nasil Calisir
Algoritma su sekilde calismaktadir:
1-Rastgele uzerinden gecilmemis bir nokta secilir
2-Noktanin epsilon uzakligi icerisindeki komsulari bulunur
3-Eger komsu sayisi minpoints sayisina esit ya da buyuk ise bir cluster olusturulur; minpoint sayisindan kucuk ise bu nokta gurultu olarak isaretlenir.Fakat ileriki safhalarda gurultu olarak isaretlenen bu nokta baska bir noktanin olusturabilecegi clustera dahil edilebilir
4-Bir nokta bir clustera dahil edildi ise bu durumda tum epsilon komsulari da bu clustera dahil edilir. Tabiki bu eklenenler icin de gecerlidir. Bu islem eklenecek nokta kalmayana kadar devam ettirilir ve boylece clusterin tamami olusturulmus olur.
5-Yeni uzerinden gecilmemis bir nokta secilir ve dongu tekrarlanir
Pseudocode
DBSCAN(D, eps, MinPts)
C = 0
for each unvisited point P in dataset D
mark P as visited
N = regionQuery(P, eps)
if sizeof(N) < MinPts
mark P as NOISE
else
C = next cluster
expandCluster(P, N, C, eps, MinPts)
expandCluster(P, N, C, eps, MinPts)
add P to cluster C
for each point P' in N
if P' is not visited
mark P' as visited
N' = regionQuery(P', eps)
if sizeof(N') >= MinPts
N = N joined with N'
if P' is not yet member of any cluster
add P' to cluster C
Algoritmada goruldugu uzere epsilon ve minpoints parametrelerinin secimi cluster ciktisi sekillendirdigi icin onemlidir. Epsilon secimi icin asagidakilere dikkat edilebilir:
1-Data normalizasyonu. Ozellikle 2den daha fazla boyutlu datalar icin normalizasyon yapmak onemlidir.
2-Data setinin yapisi ile ilgili genel bilgi. Boylece noktalar arasi uzakligin bilinmesi epsilon saptamasi icin iyi bir ipucudur.
3-Bir noktanin ne kadar cok ozelliginin(attribute) oldugu.
Denemelerinizde size yardimci olabilecek bir ipucu: Diyelimki epsilon degerini 2 katina cikardiniz ve cluster yapisi kotuye gitti. Sonra 2 katina daha cikardiniz cok iyi bir sonuc elde ettiniz. Bu durumda ya dataniz cok boyutlu ve bu durumda gereksiz ozellikleri de hesaba katiyorsunuz ya da sectiginiz uzaklik metrigi data kumeniz icin uygun degil.
