BİLDİRİ DETAY

Ahmet KOCATÜRK, Bülent ALTUNKAYNAK
İKİLİ KÜMELEME ALGORİTMALARININ GÖRSEL AÇIDAN KARŞILAŞTIRMASI
 
Giriş: Büyük hacimli veri matrislerinde satır ve sütunların aynı anda kümelenmesi son yıllarda yaygın olarak çalışılmaktadır. Özellikle gen açıklama verilerinde gen örüntülerini bu şekilde ortaya çıkarmak hastalık teşhislerinde önem kazanmaktadır. Farklı gen açıklama verilerinin varlığı ve bu verilerin büyük hacimli veriler olması analiz işlemini oldukça zorlaştırmaktadır. Literatürde bu amaç için geliştirilmiş farklı ikili küme algoritmaları mevcuttur. Bunlardan bazıları Cheng ve Church (2000) tarafından önerilen CC algoritması, Prelic ve diğerleri (2006) tarafından önerilen Bimax algoritması, Lazzeroni ve Owen (2002) tarafından önerilen Plaid algoritması, Murali ve Kasif (2003) tarafından önerilen Quest ve Xmotif algoritmaları ve Kluger ve diğerleri (2003) tarafından önerilen Spectral algoritması örnek olarak verilebilir. Ancak ikili kümeleme algoritmalarının performanslarını karşılaştırmaya yönelik çalışmalar sınırlıdır. Amaç: Literatürde yaygın olarak kullanılan CC, Bimax, Plaid, Spectral, Quest ve Xmotif ikili kümeleme algoritmalarının adımlarını göstermek ve bu algoritmaların yapay veri kümeleri üzerinde farklı senaryolarda üretilen ikili kümeleri ısı grafikleri kullanılarak görsel açıdan karşılaştırmasını yapmaktır. Kapsam: Bu araştırmada, ortalaması 0 ve varyansı 1 olan normal dağılımdan rastgele üretilen 1000x1000 boyutlu yapay veri kümesinden iki farklı senaryoya göre ikili kümeler elde edilmiştir. İlk senaryoda, üretilen ikili kümelerde örtüşmenin olmadığı durum, ikinci senaryoda ise üretilen ikili kümelerde örtüşmenin olduğu durum ele alınmıştır. Her iki senaryoda da veri matrisi içerisinde farklı boyutlarda üç ikili küme oluşturulmuştur. Oluşturulan ikili kümeler 500x500 boyutlu, 300x300 boyutlu ve 200x200 boyutlu veri matrisleridir. CC, Bimax, Plaid, Spectral, Quest ve Xmotif ikili kümeleme algoritmaları ile elde edilen ısı grafikleri ile sonuçlar görsel açıdan yorumlanmıştır. Sınırlıklar: Çalışmadan elde edilen sonuçlar ikili kümelerde örtüşme durumunun olduğu ve olmadığı durumları içermektedir. Karşılaştırmalar sadece görsel açıdan yapılmıştır. Ayrıca üretilen veri kümesi normal dağılımdan elde edilerek sınırlandırılmıştır. Yöntem: Çalışmada kullanılacak yapay veri matrisi R Project v3.4.4 programıyla elde edilmiştir. Veri kümesi elde edilirken farklı parametrelere sahip normal dağılımlar kullanılarak 1000x1000 boyutlu bir başlangıç matrisini oluşturulmuştur. Oluşturulan başlangıç matrisi içerisine senaryolara uygun olacak şekilde farklı boyutlarda ikili küme yapıları yerleştirilmiştir. İkili kümeler veri kümesi içerisine yerleştirildikten sonra bir program parçasıyla satırlar kendi içlerinde ve sütunlar da kendi içlerinde rastgele yer değiştirerek ikili kümelerin kolayca belirlenemeyeceği karmaşık bir veri matrisi elde edilmiştir. Veri kümesinde hem satır hem de sütun kümelerinin eş zamanlı kümelenmesi için yaygın olarak kullanılan CC, Bimax, Plaid, Spectral, Quest ve Xmotif ikili kümeleme algoritmalarından elde edilen ikili kümeler ile başlangıç matrisindeki ikili kümeler görsel olarak karşılaştırılmıştır. Bulgular: 1000x1000 boyutlu yapay veri kümesi için yapılan analizler sonucunda ikili kümeler arasında örtüşmenin olduğu ve olmadığı senaryolarda CC, Bimax, Plaid, Quest ve Xmotif algoritmaları ile ikili kümeler elde edilmiştir. Her iki senaryo için de Spectral algoritmasından ikili küme elde edilememiştir. İkili kümeler arasında örtüşmenin olmadığı birinci senaryoda CC, Bimax, Plaid ve Quest algoritmalarından üç ikili küme, Xmotif algoritmasından ise iki ikili küme elde edilmiştir. Ancak algoritmaların elde ettiği ikili kümeler başlangıç matrisinde oluşturulan ikili küme boyutlarından farklılık göstermiştir. İkili kümeler arasında örtüşmenin olduğu ikinci senaryoda, CC, Bimax ve Quest algoritmalarından üç ikili küme, Plaid ve Xmotif algoritmalarından ise iki ikili küme elde edilmiştir. Başlangıç matrisinde oluşturulan ikili kümeler arasındaki örtüşmenin olduğu durum sadece Bimax algoritmasından elde edilen ikili kümeler arasında gerçekleşmiştir. Sonuç: Senaryo 1 için CC algoritması 400x500, 236x300 ve 141x200 boyutunda, Bimax algoritması 300x300, 200x200 ve 500x500 boyutunda, Plaid algoritması 285x500, 137x300 ve 88x200 boyutunda, Quest algoritması 272x300, 168x63 ve 56x196 boyutunda ve Xmotif algoritması 300x300 ve 500x500 boyutunda ikili küme matrisleri elde etmiştir. Gerçek duruma en yakın sonuçlar CC ve Bimax algoritmaları ile elde edilirken en uzak sonuçlar Quest ve Spectral algoritmalarında elde edilmiştir. Senaryo 2 için CC algoritması 405x400, 130x200 ve 127x199 boyutunda, Bimax algoritması 300x300, 500x500 ve 100x100 boyutunda, Plaid algoritması 192x500 ve 92x200 boyutunda, Quest algoritması 150x200, 150x150 ve 50x100 boyutunda ve Xmotif algoritması 500x500 ve 100x400 boyutunda ikili küme matrisleri elde etmiştir. Gerçek duruma en yakın sonuç Bimax algoritması ile elde edilirken en uzak sonuç Spectral algoritmasından elde edilmiştir. Genel olarak bu çalışmadaki senaryolar için, CC ve Bimax algoritmalarının daha iyi Spectral ve Quest algoritmalarının daha kötü sonuçlar verdiğini söylemek mümkündür.

Anahtar Kelimeler: İkili Küme, Algoritma, Isı Grafiği



 


Keywords: