K-Means algoritması

Merhabalar bu yazımda Makine Öğrenme algoritmalarından popüler kümeleme algoritması K-means nedir ve Swift dili ile nasıl yazılır örneği vereceğim.

K-means algoritması bir kümeleme algoritmasıdır. Çoğu zaman Makine öğrenmede Sınıflama ve Kümeleme işlemleri karıştırılır. Bu farkı açıklayacak olursam. Kümeleme işleminde elimizde olan bir veri seti gruplara ayrılır ve tüm veriler düzlemde ayrıştırılır. Bir adet veri setimiz kümelenerek iki adet farklı veri seti kümesi oluşur. Ancak Sınıflama işleminde ise elimizde bulunan bir adet verinin hangi sınıfa ait olması gerektiğine elimizde bulunan train setinden sonra karar verilmesidir.

Yani Sınıflamada veri elma mı armut mu diye karar verirken Kümeleme işleminde ise veri armut grubunda mı yoksa elma grubunda mı diye karar veririz.

K-means algoritmasının önemli bir noktasıda öğrenmeden kümeleme işlemi yapmasıdır. Verinin Oluşan K merkezlere yakınlık derecesi bakılarak hangi kümede olduğu kararı verilir. Basit ve popüler bir algoritmadır.

Algoritmik olarak çalışma adımları aşağdaki gibidir.

1. Küme merkezlerinin belirlenmesi
2. Merkez dışındaki örneklerin mesafelerine göre sınıflandırılması
3. Yapılan sınıflandırmaya göre yeni merkezlerin belirlenmesi
4. Kararlı hale gelinene kadar 2. ve 3. adımların tekrarlanması

Piyasada bir çok kümeleme algoritmaları vardır. Bu algoritmalarda elimizdeki veri setine göre başarım olarak farklılık gösterirler. Diğer Makine Öğrenme algoritmalarında’da aynı olay söz konusudur. En önemlisi doğru modeli seçip problemimize uyarlamaktır.

Aşağıda Swift dili ile yazdığım K-Means örneğini inceleyebilirsiniz. Belirttiğiniz K adet kadar kümeleme işlemi yapacaktır. Mesafe fonksiyonu olarak Euclid uzaklığını kullandım.

func average(arr:[Int]) -> Double {
    
    return arr.reduce(0, +).toDouble() / arr.count.toDouble()
    
}

extension Int {
    func toDouble() -> Double {
        return Double(self)
    }
}

extension Double {
    func toInt() -> Int {
        return Int(self)
    }
}


let heightData:[Int] = [157,180,170,150,160,175,185,173,183,153,163,130]

func euclidianDistance(x1:Int,center:Int) -> Int {
    return Int(sqrt(pow(x1.toDouble() - center.toDouble(), 2)))
}


func kMeans(k:Int, data:[Int]) -> [[Int]] {
    
    var clusters:[[Int]] = [[Int]](repeating: [], count: k)
    var centroids:[Int] = [Int](repeating: 0, count: k)
    var oldCentroids:[Int] = [Int](repeating: 0, count: k)
    var distances:[Int] = [Int](repeating: 0, count: k)
    
    
    for c in 0..<k {
        centroids[c] = data[c]
    }

        
    loop: while true {
        
      clusters = [[Int]](repeating: [], count: k)
        
        for j in 0..<data.count {
            
           distances = []
            
            for z in 0..<k {
                
                distances.insert(euclidianDistance(x1: data[j], center: centroids[z]), at: z)

            }
            
            let indx = distances.index(of: distances.min()!)!
           
            clusters[indx].append(data[j])

        }
        
        for q in 0..<k {
            oldCentroids[q] = centroids[q]
            
            centroids[q] = average(arr: clusters[q]).toInt()
            
            if oldCentroids[q] == centroids[q] {
                break loop
            }
            
        }
        
    }
    
    return clusters
}


print(kMeans(k: 2, data: heightData))

Github link.