Agac Yapili Verilerin Kumelenmesi


Dinler D., Tural M. K. , Özdemirel N. E.

38. Yöneylem Araştırması Endüstri Mühendisliği Ulusal Kongresi, Eskişehir, Türkiye, 26 - 29 Haziran 2018, ss.21

  • Basıldığı Şehir: Eskişehir
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.21

Özet

Geleneksel kumeleme yontemleri veri objelerinin noktasal
oldugunu varsaymaktadr. Fakat gelisen olcum teknikleri
ve daha detayl analizlere ihtiyac duyulmas sebebiyle
gunumuzde daha karmask veri kumeleri toplanmaktadr.
Bu calsmada, agrlkl veya agrlksz kenarl, koku olan
bir agac yapsna sahip veri objelerinin kumelenmesi
problemi ele alnmstr. Bu tarz agac yapl veri kumeleme
problemleri biyoloji, norobilim veya sosyal aglar gibi
bircok alanda karsmza ckmaktadr. Ele alnan problemin
cozumu icin kortalamalar (kmeans) tabanl bir
algoritma onerilmistir. Bu algoritma, kume merkezlerini
temsil eden agaclarla (centroid tree) baslayarak atama ve
merkez guncelleme asamalarn cozum yaknsayana kadar
tekrarlar. Atama asamasnda, her veri objesi Dugum
Kenar  Ortusmesi (DK O, Vertex Edge Overlap) olcutune
gore en benzer olan merkez agaca atanr. DKO olcutu
\fazla sayda ortak kenar ve dugume sahip iki agac
benzerdir" krini temel alr. Guncelleme asamasnda,
her merkez kendisine atanan veri objeleri goz onunde
bulundurularak guncellenir. Agaclarn agrlksz kenarl
oldugu durumda, verilen bir kumenin merkez agacn
bulmak icin dogrusal olmayan bir tamsayl programlama
formulasyonu onerilmistir. Bahsi gecen merkez agac,
kendisi ile o kumeye atanan agaclar arasndaki DKO
degerlerinin toplamn encoklayan agactr.  Onerilen
formulasyonun cozumu icin optimal sonucu bulan
sezgisel bir yontem kullanlmstr. Agaclarn agrlkl
kenarl oldugu durumda ise, kume merkezini bulmak
icin dogrusal olmayan bir programlama formulasyonu
onerilmis ve sezgisel bir yaklasmla cozulmustur. Fakat
bu sezgisel yaklasmn optimal sonucu bulacagnn
garantisi yoktur. Gelistirilen cozum yaklasmlar rassal
olarak uretilmis veri kumeleri kullanlarak geleneksel
algoritmalarla karslastrlmstr.