k-means

• en büyük zorluğu k'yı seçmek. k'yı az seçersen farklı kümelere gelmesini istediğin nesneler aynı kümeye düşüyor. k'yı fazla seçersen de nesne uzayını parça pinçik ediyor. genel bir k belirleme algoritmasından bahsediyorum. nedir bunun yöntemi? cluster sayısı ve error'u minimize etmek üzerine kurulu bir şey olabilir gibi. ikisi arasında bir trade-off var, optimum değeri bulmak lazım.
• genelde elinize yeni bir data geldiginde yav bu data neymis bir gorelim gibisinden hizlica bir calistirilan ama genelde onun haricinde pek kullanilmayan bir metoddur.
  
  artilari:
  - hizli calisir. spectral clustering'mis yok efendim adjaceny matrix'in eigenvalue'larina bakmakmis, mean-shift'mis hepsinden cok daha hizlidir.
  - data uzerinden paralelleme yapilabilir, mapreduce'a uygundur. (mapper her adimda kullanilan datayi paylasicak, reducer da tum sonuclari alip centroidleri update edicek. her adim bir mapreduce seklinde)
  - cluster'larin centroidler etrafinda simetrik oldugunu varsayar. dataniz boyle ecis bucus, ince uzun kivir kivir clusterlardan olusuyorsa babayaro olursunuz. (bunu cozmek icin kernel k-means kullanabilirsiniz, o da kernel trick kullanrak uzaydaki metrigi euclidean'dan nonlinear bir yapiya cevirerek yapiliyor)
  
  eksileri:
  - k'yi elle vermen lazim. bu da gokten vahiy gelmedigi surece bi dolu k degeri icin calistirip sonuclari karsilastirmak demek oluyor.
  - son sonuclar initialization'a cok bagli. bastan guzel yerlere initialize etmezseniz babayi aliyorsunuz. onun icin hele bi de nerelere initialize edeceginizi bilmiyor gelisiguzel initialize ediyorsaniz bu bir ustteki birden fazla k degeri icin deneyip karar verme isini de yaparken her bir k degeri icin de bi 20-30 kere calistirip o k degeri icin ortalama (ya da o k degeri icin en iyi) performanslari karsilastirmak gerekiyor.
• bodoslamadan orta yerinden dalınırsa elbette anlaşılmaz. k-means, unsupervised, yani gözetimsiz bir kümeleme (bkz: clustering) yöntemidir. eldeki verinin k adet kümeden oluştuğunu varsayar ve oluşturulacak kümelere dahil olan noktaların, bu noktaların ortalaması şeklinde hesaplanan küme ortalamasına olan uzaklıklarının karelerinin toplamını (bkz: within cluster sum of squares) minimize etmeye çalışır.
  
  diğer detayların bir kısmından zaten bahsedilmiş
• kümelemenin iki amacı olan küme içi uzaklığın küçüklenmesi ve kümeler arası uzaklığın büyüklenmesinden sadece ilkine hizmet ettiği için sadece bunu ölçen gürbüzlük endekslerinde (robustness index) sonuçları görece iyi çıkabilir (veriye bağlı olarak değişir) ki bu endeks de en çok silhouette width endeksi olarak alınır. davies-bouldin, c, kendall's tau ve dunn's endekslerinde daha iyi sonuç vermeye meyilli başka bir algoritma için (bkz: self organizing map)
• en temel, görsel olarak anlaması kolay clustering algoritmasıdır. şöyle güzel bir görsel anlatımı vardır.
  
  temel olarak iki aşamadan oluşur, (i) rastgele (genellikle) k tane nokta seçersiniz, (ii) sonra o noktalara göre onların ortalamasına göre yeni centeroidlerinizi bulursunuz. mean centeroid noktası değişmeyene kadar tekrarlarsınız.
  
  k yı neye göre seçeceiğiniz de işin sırrı.
• bir veri içerisindeki noktaları kümelemek için kullanılan bir algoritmadır. aynı zamanda da oldukça hızlı çalışan bir algoritmadır. bu algoritmada sırasıyla şu basamaklar uygulanır rastegele "k" tane küme merkezi seç, herhangi bir değişim olmayana kadar tekrar tekrar veri içerisindeki noktaları kendisine en yakın kümeye bağla, küme merkezlerini güncelle. bu algoritma çok hızlı çalıştığı için birçok kez farklı noktalardan başlatılarak gürbüzlük (bkz: robustness)^* kazandırılabilir.
• bir kümeleme algoritmasi olup, cogunlukla az iterasyonda tatmin edici sonuclar elde edilmesini saglar. k tane sinif olusturulacagindan, bu k sayisinin belirlenmesi bir derttir. bunun icin silhouette coefficientüzerinden bir siniflandirmanin bu k sayisi icin ne kadar verimli olup olmadigini tespit etmemiz mümkündür.
  
  eger ki silhouette coefficient 0.25'den yüksekse, bir structure vardir, yok ise bir structure yok, diyerek bir siniflandirmanin verimini görebiliriz.
  silhouette coefficient icin: tik
  
  edit: imla
• kümeleme algoritması. kolay implement edilir. o(tkn) complexity sine sahip bu yüzden bir çok algoritmadan daha hızlı çalışır ( eğer seçilen k çok büyük değilse). başlangıç değerlerinin random verilmesi en büyük dezavantajlarından biridir bu yüzden kmeans++ gibi varyasyonları çıkmıştır. konveks olmayan şekilleri kümeleyemez. hadi ben kaçar.
• high dimension sakata getirir daha çok az boyutlu ve çok örnekli verilerde tercih edilir.
• az ömrümüzü yemedi ama her şeye rağmen başarılı bir kümeleme algoritmasıdır.