Kmeans ve Kmedoids Kümeleme
Bu yazımda sizlere Veri Madenciliği’nin Kümeleme (Clustering) alt başlığının iki üyesi olan K-means ve K-medoids’ten bahsetmeye çalışacağım.
Öğrenme Çeşitleri
Gözetimli öğrenme, sonuçları bilinen veri seti ile modelin oluşturulması ve oluşan modele sonuçları bilinmeyen veri seti verildiğinde, sonuçların tahmin edilmesidir. Örneğin, çalışmada hasta kişiler tahmin edilecekse hasta olan ve olmayan kişilerin bilgisi ile model oluşturulur. Daha sonra modele x kişisinin bilgileri verildiğin x kişisinin hasta olup olmadığı tahmin edilir.
Gözetimsiz öğrenme, sonuçları hakkında bilgi sahibi olunmayan veri setinin tahminidir. Örneğin, elimizde hasta olan ve hasta olmayan kişilere ait bilgileri var fakat kimin hasta olduğunu bilmiyoruz. Bu sefer elimizde olan bilgilere göre kişileri iki gruba ayırıyoruz.
Kümeleme
Kümeleme yöntemi, veriyi gruplara veya kümelere ayıran gözetimsiz öğrenme çeşididir. Veri, grup içindeki elemanların kendi içindeki benzerliği ve grupların birbirine benzememesi kıstası ile birbirinden ayrılır. Kümeleme de esas nokta sınıflar arasındaki benzerliğin minimum, sınıfın kendi içindeki benzerliği maksimum olmasını sağlamaktır. Bu benzerlik uzaydaki veri elemanlarının uzaklık fonksiyonlarına göre birbirlerine olan yakınlığı bazında hesaplanır. Kümeleme bu özelliği ile otomatik sınıflandırma olarak da adlandırılır.
Kümeleme, iş zekası, görüntü örüntü tanıma, web arama, biyoloji ve güvenlik alanlarında yaygın olarak kullanılır. Örneğin, görüntü tanımada el yazısı karakterlerini bulmak için veri kümelere ayrılır.
Kümeleme, bazı uygulamalarda veriyi benzerliğe göre gruplara ayırmasından dolayı aynı zamanda veri segmentasyonu(data segmentation) olarak adlandırılır. Ayrıca ayrılan gruplara benzemeyen veri elemanları ortaya çıktığı için uç değer bulma(outlier detection) uygulamalarında da kullanılır.
Veri madenciliğinde kümelemenin sağlıklı yapılabilmesi için, verinin ölçeklenebilir olmalıdır. Ayrıca kümeleme, veri tipinden bağımsız olarak çalışabilmeli, gürültülü veri ile uğraşabilmeli, girdi sayısının değişkenliğine karşı hassasiyetinin olmaması ve çok elemanlı/boyutlu veri ile çalışabilmelidir.
Kümeleme yöntemleri, bölümleme, hiyerarşik, yoğunluk tabanlı ve ızgara tabanlı olmak üzere dört şekilde uygulanır. Bölümleme metodu, K-means ve K-medoids yöntemlerinden oluşmaktadır.
K-means
Küme merkezi(centroid) tabanlı bir tekniktir. Bölümleme, D elemanı k kümeye ayırır. Oluşan kümelere C dersek, C 1 den C k’ya k küme adet oluşur ve her küme D nin altkümesi C i ⊂ D iken kümeler arasında (1 ≤ i, j ≤ k) benzerlik C i ∩ C j = ∅ yoktur.
Algoritma, n elemanı k tane kümeye ayırma işlemi ile başlar. K centroid belirlendikten sonra elemanların k centroid lere olan uzaklıkları hesaplanır ve k centroid en yakın noktalar bir kümeyi oluşturur. Küme elemanlarının ortalaması alınır ve centroid ler tekrar belirlenir. Eğer centroid değişmişse noktaların merkeze olan uzaklıklarına göre hangi centroide ait oldukları bulunur ve bu işlem küme merkezleri (centroid) stabil hale gelene kadar devam eder.
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.
K-medoids
Nesne temelli bir tekniktir. K belirlendikten sonra k tane centroid belirlenir. Elemanların centroide uzaklığına göre hangi centroide ait oldukları bulunur. Centroid ler stabil duruma gelene kadar noktaların centroidlere olan uzaklıkları hesaplanır ve yeni cetroidler belirlenir.
İki algoritma arasındaki temel fark merkezin (centroid) belirlenmesidir. Kmeans’te noktaların ortalaması alınırken, K-medoids’te noktaların centroide olan uzaklıkları hesaplanır.
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.
K-means ve K-medoids Kıyaslaması
K-means
- Küme, küme merkezi ile temsil edilir.
- Gürültülü veriye karşı duyarlıdır.
- Büyük veride daha güvenilirdir.
K-medoids
- Küme, kümede ki herhangi bir eleman ile temsil edilir.
- Gürültülü veriden etkilenmez.
- Küçük veride daha güvenilirdir.
Cluster sayısını belirlenmesi için çeşitli yöntemler
- Deneysel yöntem: Veri setindeki nokta sayısı n ise cluster sayısı √n/2
- Elbow Yöntemi: Cluster sayısı başlangıç olarak 1 alınır ve varyans hesaplanır. Varyans değeri sabitlenene kadar cluster sayısı artırılmaya devam edilir.
- Silhouette Coefficient: Bu değer ile kümelerin birbirinden ne kadar farklı olduğunu bulmuş oluruz. +1 ile -1 arasında oluşan değer +1’e ne kadar yakın olursa cluster sayısının o kadar iyi olduğunu teyit ederiz. Kümelerin kendi içlerindeki ve kümelerin kendi aralarındaki ortalama uzaklık arasında oluşturulan denklem ile bu değer bulunur.
Spark ile K-means örneği: (scala dili ile)
import org.apache.spark.{SparkContext, SparkConf}
import org.apache.spark.mllib.clustering.{KMeansModel, KMeans}
import org.apache.spark.mllib.linalg.Vectors
object Kmeans {
def main(args: Array[String]) {
if (args.length < 4) {
println("usage: input output numClusters maxIterations")
System.exit(0)
}
val conf = new SparkConf
conf.setAppName("Spark KMeans Example").setMaster("local")
val context = new SparkContext(conf)
val input = args(0)
val output = args(1)
val K = args(2).toInt
val maxIteration = args(3).toInt
val runs = calculateRuns(args)
val data = context.textFile(input).map {
line => Vectors.dense(line.split(',').map(_.toDouble))
}.cache()
val clusters: KMeansModel = KMeans.train(data, K, maxIteration, runs)
println("cluster centers: " + clusters.clusterCenters.mkString(","))
val vectorsAndClusterIdx = data.map{ point =>
val prediction = clusters.predict(point)
(point.toString, prediction)
}
vectorsAndClusterIdx.saveAsTextFile(output)
context.stop()
}
def calculateRuns(args: Array[String]): Int = {
if (args.length > 4) args(4).toInt
else 1
}
}
Girdi:
818.21,809.83 8.37,850.78 680.43,698.76 913.88,173.43 579.87,135.51 204.13,800.01 700.44,758.47 657.36,745.11 290.3,109.27 246.64,885.54
Çıktı:
([818.21,809.83],1) ([8.37,850.78],2) ([680.43,698.76],1) ([913.88,173.43],0) ([579.87,135.51],0) ([204.13,800.01],2) ([700.44,758.47],1) ([657.36,745.11],1) ([290.3,109.27],0) ([246.64,885.54],2)
Kaynaklar
Data Mining Concepts and Techniques Third Edition
Jiawei Han
Micheline Kamber
Jian Pei
Veri analizinde yeni alışkanlıklar Hive İç İçe Sorgu Kullanımı