GİRİŞ
Veri Madenciliği (VM) büyük boyutlardaki verilerden gelen bilgileri çekip çıkararak gizli kalmış bilgileri ve olanakları gerçek zamanlı uygulamalar için kullanılmasıdır. Veri Madenciliği veri analizi için çok çeşitli algoritmalara sahiptir. Bunlardan bazıları Kümeleme, Birliktelik, Sınıflamadır. (1)
Kümeleme, verinin benzer nesnelerden oluşturulmuş gruplara bölünmesidir. Kümeleme işleminde küme içindeki elemanların benzerliği fazla, kümeler arası benzerlik ise az olmalıdır (2,3). Bir kümeleme yönteminin kalitesi bu prensibi sağlaması ile doğru orantılıdır. Kümeleme yöntemi seçimi kullanılacak veri türüne ve uygulamanın amacına göre farklılık gösterir.
Bu çalışmada K-means ve K-Medoids kümeleme algoritmaları ile Iris veri seti kullanılarak analiz ve yorumlamalar yapılmıştır. Aynı zamanda bu iki algoritma bu veriler doğrultusunda karşılaştırılmıştır.
VERİ SETİ TANITIMI
Bu çalışmada örnek olarak kullanacağımız veri seti yapay öğrenme alanının en popüler veri setlerinden “Iris” veri seti.(4) Iris veri seti 3 Iris bitki türüne (Iris setosa, Iris virginica and Iris versicolor) ait, her bir türden 50 örnek olmak üzere toplam 150 örnek sayısına sahip bir veri setidir. Her bir örnek için 4 özellik tanımlanmıştır: taç yaprak uzunluğu (a1), taç yaprak genişliği(a2), çanak yaprak genişliği(a3), taç yaprak genişliğia(a4). Yani veri setimizde, her bir bitki örneği ayrı bir gözlemi ifade ederken; bitki tür ismi bağımlı değişken, bitkilerin ölçülen 4 temel özelliği ise bağımsız değişkenleri ifade eder. (5)
Çalışma için bu veri setini seçmemin amacı da kümeleme işlemi yaparken kullanacağım algoritmaların kümeleme sayılarını daha rahat karşılaştırabilmektir.
KULLANILAN ALGORİTMALARIN TANIMLARI
K-Means Kümeleme Algoritması
En eski kümeleme algoritmalarından olan k-means, 1967 yılında J.B. MacQueen tarafından geliştirilmiştir (MacQueen, 1967). K-Means aşamaları Şekil 1’de gösterilmiştir. En yaygın kullanılan gözetimsiz öğrenme yöntemlerinden birisi olan K-means’in atama mekanizması, her verinin sadece bir kümeye ait olabilmesine izin verir. Bu nedenle, keskin bir kümeleme algoritmasıdır. Merkez noktanın kümeyi temsil etmesi ana fikrine dayalı bir metottur (Han ve Kamber, 2001). Eşit büyüklükte küresel kümeleri bulmaya eğilimlidir.(6)
Şekil 1. K-Means algoritması aşamaları. (7)
K-means kümeleme yönteminin değerlendirilmesinde en yaygın olarak karesel hata kriteri SSE kullanılır. En düşük SSE değerine sahip kümeleme sonucu en iyi sonucu verir. Nesnelerin bulundukları kümenin merkez noktalarına olan uzaklıklarının karelerinin toplamı (1) nolu eşitlik ile hesaplanmaktadır (Pang-Ning vd., 2006).
Bu kriterleme sonucu, k tane kümenin olabildiğince yoğun ve birbirinden ayrı sonuçlanması hedeflenmeye çalışılır. Algoritma, karesel-hata fonksiyonunu azaltacak k parçayı belirlemeye gayret eder. K-means algoritması, algoritmaya kullanıcı tarafından verilen k parametresi ile n tane veriden oluşan veri setini k adet kümeye böler. Küme benzerliği kümedeki nesnelerin ortalama değeri ile ölçülür, bu da kümenin ağırlık merkezidir (Xu veWunsch, 2005). (6)
Avatajları:
Küme sayısı az ise büyük veri setlerinde hiyerarşik kümeleye göre daha hızlıdır.
Eğer veri seti özellikle küresel ise hiyerarşik kümelemeye göre daha sıkı kümeler oluşturur.
Dezavantajları:
Üretilen kümeler arasında kıyas yapmak zordur.
Sabitlenmiş küme sayısı, küme sayısının tahminini zorlaştırır.
Küresel olmayan veri setlerinde iyi çalışmaz.
Farklı başlangıç bölümlemeleri ile farklı sonuç kümeleri elde edilir.
Gürültülü veriye duyarlıdır. (2)
K-medoids Algoritmasının Yapısı
K-medoids algoritmasının temeli, verinin çeşitli yapısal özelliklerini temsil eden k tane temsilci nesneyi bulma esasına dayanır (Kaufman ve Rousseeuw, 1987). Temsilci nesne medoid olarak adlandırılır ve kümenin merkezine en yakın noktadır. Bir grup nesneyi k tane kümeye bölerken asıl amaç, birbirine çok benzeyen nesnelerin bir arada bulunduğu ve farklı kümelerdeki nesnelerin birbirinden benzersiz olduğu kümeleri bulmaktır. En yaygın kullanılan k-medoids algoritması, 1987 yılında Kaufman and Rousseeuw tarafından geliştirilmiştir (Kaufman ve Rousseeuw, 1990). Temsilci nesne, diğer nesnelere olan ortalama uzaklığı minimum yapan kümenin en merkezi nesnesidir. Bu nedenle, bu bölünme metodu her bir nesne ve onun referans noktası arasındaki benzersizliklerin toplamını küçültme mantığı esas alınarak uygulanır. Kümeleme literatüründe temsilci nesnelere çoğunlukla merkeztipler (centrotypes) denilmektedir. PAM (Partitioning Around Medoids) algoritmasında temsilci nesneler medoid olarak adlandırılmaktadır (Kaufman ve Rousseeuw, 1990). Amacın k tane nesneyi bulmak olmasından dolayı, k-medoids metodu olarak adlandırılmaktadır. k adet temsilci nesne tespit edildikten sonra her bir nesne en yakın olduğu temsilciye atanarak k tane küme oluşturulur. Sonraki adımlarda her bir temsilci nesne temsilci olmayan nesne ile değiştirilerek kümelemenin kalitesi yükseltilinceye kadar ötelenir. Bu kalite nesne ile ait olduğu kümenin temsilci nesnesi arasındaki ortalama benzersizlik maliyet fonksiyonu kullanılarak değerlendirilir.(6)
Avantajları:
Daha iyi ve kararlı kümeleme sonuçları verir.
Verilerin işleniş sırası ve ilk atamada ki merkez seçiminin kümeleme üzerinde etkisi yoktur.
Merkezi elemanların kümeyi temsil etmesinden dolayı gürültülü veriye karşı duyarlı değildir.
Dejavantajları:
Uygun küme sayısının belirlenmesi için birden fazla deneme yapmak gerekir. (2)
Şekil 2. K-Medoids algoritması aşamaları. (8)
ANALİZ SONUÇLARI
İki kümeleme algoritması için de k=2, k=3, k=4 ve k=5 değerleri kullanılarak kümeleme yapılmıştır. (Şekil 3)
Şekil 3. K-Means ve K-Medoids’in k değerlerine göre kümelenmeleri
K-Means algoritmasında her k değeri i çin hesaplanan SSE değerleri neticesinde k=3 değeri en uygun küme sayısı olarak saptanmıştır. (Şekil 4)
Şekil 4. K-Means algoritmasında SSE değeri ile optimum k değerinin saptanması.
SONUÇ
Şekil 3a ve Şekil 3b’de görüldüğü gibi k=2 değeri için iki algoritmanın da sonuçları aynıdır. Şekil 3c ve Şekil 3d’de de gözlemlendiği gibi k=3 değeri için de hemen hemen aynı sonuçları veren algoritmalar Şekil 3e, Şekil 3f, Şekil 3g, Şekil3h’de k=4 ve k=5 için tamamen farklı sonuçlar vermişlerdir. Özellikle K-Medoids algoritması aykırı değerlerde kümeleme sonuçlarında başarısız olmuştur. Büyük ve karmaşık veri setlerinde K-Means kullanımının verimlilik açısından daha mantıklı olduğu gözlemlenmiştir. Başka bir çalışmada da K-Means ve K-Medoids için aşağıdaki karşılaştırma tablosunda bulunan sonuçlar çıkmıştır. (Tablo 1)
Tablo 1. K-Means ve K-Medoids algoritmalarının karşılaştırması (9)
Özellikler | K-Means | K-Medoids |
Karmaşıklık | O ( i k n ) | O ( i k (n-k)2 ) |
Verimlilik | Nispeten iyi | Nispeten düşük |
İmplementasyon | Kolay | Karmaşık |
Aykırı değerlere hassasiyet | Evet | Hayır |
Konveks şekil zorunluluğu | Evet | Çok değil |
Küme sayısını (k) ön tanımlı olarak vermek | Zorunlu | Zorunlu |
Ön kısım (başlangıç) çalışma zamanı ve sonucu kötü etkiliyor mu? | Evet | Evet |
Optimum kullanım alanı | Ayrılmış Kümeler | Ayrılmış Kümeler ve küçük veri setleri |
REFERANSLAR
Dr. T. VELMURUGAN,”Efficiency of k-Means and K-Medoids Algorithms for Clustering Arbitrary Data Points”, International Journal of Computer Technology and Applications, 2012.
Han, J., Kamber, M., “Data Mining Concepts and Techniques”, Morgan Kaufmann Publishers Inc., 2001.
Fayyad, U.M., Piatesky-Shapiro, G., Smyth, P., Uthurusamy, R., “Advances in data mining and Knowledge Discovery.” AAAI Pres, USA, 1994.
https://archive.ics.uci.edu/ml/datasets/Iris
http://users.metu.edu.tr/e168244/classification.html
Meltem IŞIK, A. Yılmaz ÇAMURCU, “K-means, k-medoids ve bulanık c-means algoritmalarının uygulamalı olarak performanslarının tespiti”, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 2007/1
J. Han and M. Kamber. “Data Mining: Concepts and Techniques”, Morgan Kaufmann Publishers, August 2000.
Jiawei Han and Micheline Kamber, “Data Mining Techniques”, Morgan Kaufmann Publishers, 2000.
Shalini S. Sigh, N. C. Chauhan, "K-means v/s K-medoids: A Comparative Study", National Conference on Recent Trends in Engineering & Technology, 2011