Kümeleme Tabanlı Segmentasyon — KMeans Uygulaması
Bölütleme (Segmentasyon), homojen bir küme içerisinde aynı karakteristiğe sahip alanların diğer kümelerden ayrılması, belirgin bir hale getirilmesi işlemidir. (Şengür, Türkoğlu, & İnce, 2005)
Bölütleme işlemi için ise genellikle kümeleme algoritmaları kullanılır. Kümeleme işlemi ötelemeli bir yöntem olup zaman almaktadır. Gerçek zamanlı çalışmalarda bölütlemenin hızlı yapılabilmesi için kümeleme algoritmalarının da hızlı olması ya da bölütlenen verinin azaltılması gerekmektedir. (Şişeci, Metlek, & Çetişli, 2014)
Kümeleme Algoritmaları
Kümeleme analizi ilk kez 1939 yılında kullanılmış ve 1960’lı yıllardan sonra kullanımı yaygınlaşmıştır. (Anderberg, 1973) Kümeleme analizinin asıl amacı, gruplanmamış verileri benzerliklerine göre gruplandırmak ve buna göre yorumlanabilmesini ve dolasıyla sayısal görüntü işlemedede imge bölütlemelesinin sağlamaktır. (Romesbourg, 1984)
Kümeleme Algoritmalarının Sınıflandırılması
Kümeleme algoritmaları temelde özel (exclusive) , örtüşen (overlapping), hiyerarşik, olasıklık ve yapay sinir ağları bazlı olarak ana sınıflara ayrılabilir. (Dubey, Vijay, & Pratibha, 2018)
Özel (Exclusive)
K-Means
Özel algoritmalardan en eski ve öne çıkan K — Means (K — Ortalamalar) ilk olarak 1967 yılında ortaya atılan bu algoritma, sürekli olarak kümelerin yenilendiği ve en uygun çözüme ulaşana kadar devam eden döngüsel bir algoritmadır. (Kalaycı, 2006) K-ortalama algoritmasının genel mantığı n tane veri nesnesinden oluşan bir veri kümesini, araştırmacının ön bilgisine ve tecrübesine dayanarak belirlenen k tane kümeye bölümlemektir. Amaç, gerçekleştirilen bölümleme işlemi sonunda elde edilen kümelerin küme içi benzerliklerini maksimum ve farklı kümeler arası benzerliklerin minimum olmasını sağlamaktır. (Kalaycı, 2006)
Küme benzerliği, kümenin ağırlık merkezi olarak kabul edilen bir nesne (sentroid) ile kümedeki diğer nesneler arasındaki uzaklıkların ortalama değeri ile ölçülmektedir. (Oğuz, 2017)
Adım adım K-Means yöntemi adımlarını maddelendirilmiş hali şu şekildedir:
- Nesneleri al, küme sayısını belirle ve başlangıç kitle merkezlerini (centroid) belirle.
- Her nesneyi en uygun gruba ata ve her atama işleminden sonra atama yapılan k kitle merkezini hesapla.
- Yeni oluşan grubu geçmişteki grup ile kıyasla. Grupta değişim yok ise algoritmayı bitir, aksi takdirde bir önceki adıma geri dön.
Bu yöntemin temel atama mekanizması, her bir verinin sadece bir kümeye ait olmasına izin vermekteidir. Bu nedenle bu kesin — hard bir kümeleme yöntemidir. Eğer bir verinin birden fazla kümeye ait olabilme durumu olursa bu fuzzy ya da soft k-means yöntemi olarak adlandırılmaktadır ve örtüşen bir yaklaşım olarak da değerlendirilebilir. (Oğuz, 2017)
Örtüşen (Overlapping)
Bulanık C-Means
Bulanık C-Means (BCO), bulanık kümeleme tekniklerinden en iyi bilinen ve yaygın olarak kullanılan ötelemeli bir algoritmadır. (Şişeci, Metlek, & Çetişli, 2014) Bu algoritma amaç fonksiyonunu küçültmeyi hedefler ve nesnelerin iki veya daha fazla kümeye ait olabilmesine izin verir. Bulanık mantık prensibi gereği her veri, kümelerin her birine [0–1] arasında değişen birer üyelik değeri ile aittir. Nesne hangi küme merkezine yakın ise o kümeye ait olma üyeliği diğer kümelere ait olma üyeliğinden daha büyük olacaktır. Amaç fonksiyonun belli bir değere yakınsamasıyla kümeleme işlemi tamamlanır. (Şişeci, Metlek, & Çetişli, 2014)
Hiyerarşik
Hiyerarşik kümeleme teknikleri, kümeleri peş peşe birleştirme sürecidir ve bir grup, diğeri ile bir kez birleştirildikten sonra, daha sonraki adımlarda kesinlikle ayrılamaz. (Kırmızıbiber & Gökgöz, 2019)
Gruplayıcı ve bölücü olmak üzere iki yöntem mevcuttur. Gruplayıcı hiyerarşik yöntemde her birim veya her gözlem başlangıçta bir küme olarak kabul edilir. Daha sonra en yakın iki küme (veya gözlem) yeni bir kümede toplanarak birleştirilir. Böylece her adımda küme sayısı bir azaltılır. Bölücü hiyerarşik yöntemde ise süreç gruplayıcı hiyerarşik yöntemin tam tersidir. Bu yöntemde tüm gözlemlerden oluşan büyük bir küme ile işe başlanır. Benzer olmayan gözlemler ayıklanarak daha küçük kümeler oluşturulur. Her gözlem tek başına küme oluşturana kadar işleme devam edilir. (Kırmızıbiber & Gökgöz, 2019)
Olasılıklı
Gaus Karışımı
Gauss karışım modeli, imgeyi birbirinden bağımsız birden fazla Gauss dağılımının karışımıyla tanımlayan bir modeldir. (Herkiloğlu, 2005) Gauss dağılımı ile örnek üreten birden fazla bağımsız kaynaktan üretildiği varsayılıp, bu kaynaklara ait Gauss parametrelerinin, karışımın olasılık yoğunluk işlevini en çoklayacak şekilde optimizasyonudur. Böylece, verisetinin tek dağılımdan üretildiğinin varsayılıp modelleme yapan algoritmaların çıkmaza girdiği yerlerde bile Gauss karışımı başarılıdır. (Herkiloğlu, 2005)
Yapay Sinir Ağları
Yapay sinir ağları (YSA) sınıflandırma, kümeleme ve özellik çıkartımı gibi desen tanıma problemleri için özellikle uygundur ve yaygın olarak kullanılmaktadır. (Demirhan & Güler, 2010) YSA’lar kendi kendilerine öğrenebilmeleri, hata toleransları ve en uygunu arama yeteneklerinden dolayı her geçen gün daha fazla ilgi çekmektedirler. YSA’lar paralel çalışan, lineer olmayan ve biyolojik sinir ağlarına benzer bir desende düzenlenmiş çok sayıda hesap elemanından oluşurlar. Tepkilerini bulundukları ortama göre değiştirirler, deneyimlerden öğrenirler ve daha önceki örneklerden yenilerine genelleme yaparlar. (Demirhan & Güler, 2010)
Avantajları & Dezavantajları
Aşağıdaki tablo ile genel bir özet çıkarabilmek mümkündür (Dubey, Vijay, & Pratibha, 2018):
Problemin gösteriminin zor olması nedeniyle ayrık veri yatkınlığı, Yavaş yakınsama oranı nedeniyle uzun olması
K-Means literatürde yer alan klasik ama hızı ve iyi ayrılmış verilerde etkili yönüyle efektif bir yöntem olarak değerlendirilebilir. Bulanık C-Means iç içe geçmiş verilerde daha etkili olduğu için nihayetinde K-Means’ten nispeten daha iyi sonuçlar verebilmektedir. Eğer küme sayısını belirlemek için bir öngörü sahibi olunamıyorsa hiyerarşik tercih edilebilir. Gauss Karışımı doğal gerçek veri setlerinde , tek dağılım davranışı göstermeyen verilerde en başarılı sonuçları verebiliyor. Yapay sinir ağları belirli bir eğitilmiş modele dayandığı için iyi ayrılmış verilerde daha net cevaplar verebiliyor; ayrıca imgenin bütününü değerlendirebildiği için gürültülü imgelerde de başarılı sonuçlar veriyor ancak başarılı sonuca ulaşması yavaş yakınsama oranı nedeniyle uzun sürebilmektedir.
K-Means Yönteminin Uygulanması
Arayüzler
İkili kümeden başlayarak adım adım küme sayısı arttırılarak sonuçlar arasında karşılaştırma arayüzler arasından yapılabilmektedir.
Küme sayısı arttırıldıkça görüntü aslına daha fazla yakınsamakta ve aradaki fark azalmaktadır. Olası kötü rassal seçimlerin önüne geçmek adına iterasyon arttırılarak algoritma çalıştıralabilir ancak bu da yavaşlamaya neden olacaktır.
Kod
Algoritmayı çalıştıran ve hesabı yapan sınıf ve fonksiyonlar şu şekilde belirtilebilir:
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Text;
namespace KMeans
{
class KMeans
{
Bitmap mainBitmap;
GVector[,] inputGVector;
public Bitmap output;
private int cluster;
public KMeans(Bitmap inputB,int inputCluster)
{
this.mainBitmap = inputB;
this.inputGVector = ConvertToGVector(inputB);
this.cluster = inputCluster;
}
public GVector[,] ConvertToGVector(Bitmap input)
{
Bitmap bt = (Bitmap)input.Clone();
GVector[,] result = new GVector[bt.Width, bt.Height];
for (int y = 0; y < bt.Height; y++)
{
for (int x = 0; x < bt.Width; x++)
{
Color c = bt.GetPixel(x, y);
result[x, y] = new GVector(c.R, c.G, c.B,x,y);
}
}
return result;
}
public Bitmap CalculateKmeans(int ClusterCount, GVector[,] input, int iterations)
{
int length = input.GetLength(0);
int height = input.GetLength(1);
Random randomizer = new Random();
List<GVector> centroides = new List<GVector>(ClusterCount);
List<List<GVector>> clusters = new List<List<GVector>>(ClusterCount);
for (int i = 0; i < ClusterCount; i++)
{
GVector centroid = input[randomizer.Next(0, length), randomizer.Next(0, height)];
List<GVector> cluster = new List<GVector>();
cluster.Add(centroid);
clusters.Add(cluster);
centroides.Add(centroid);
}
int count = 0;
while (count < iterations)
{
for (int x = 0; x < input.GetLength(0); x++)
{
for (int y = 0; y < input.GetLength(1); y++)
{
GVector currentVector = input[x, y];
double min_distance = Double.PositiveInfinity;
GVector closest_centroid = centroides[0];
foreach (GVector centroid in centroides)
{
double distance = currentVector.Distance(centroid);
if (Math.Pow(distance, 2) < min_distance)
{
min_distance = Math.Pow(distance, 2);
closest_centroid = centroid;
}
}
List<GVector> to_assign = clusters[0];
foreach (List<GVector> cluster_list in clusters)
{
if (cluster_list[0].r == closest_centroid.r && cluster_list[0].g == closest_centroid.g && cluster_list[0].b == closest_centroid.b)
{
to_assign = cluster_list;
break;
}
}
to_assign.Add(currentVector);
int current_length = to_assign.Count;
GVector current_centroid = to_assign[0];
GVector new_centroid = new GVector(0, 0, 0);
foreach (GVector vector in to_assign)
{
new_centroid = new_centroid.Sum(vector);
}
new_centroid = new GVector(new_centroid.r / current_length, new_centroid.g / current_length, new_centroid.b / current_length);
to_assign.RemoveAt(0);
to_assign.Insert(0, new_centroid);
for (int i = 0; i < centroides.Count; i++)
{
if (centroides[i].r == current_centroid.r && centroides[i].g == current_centroid.g && current_centroid.b == centroides[i].b)
{
centroides[i] = new_centroid;
break;
}
}
}
}
count++;
}
foreach (List<GVector> cluster_list in clusters)
{
GVector current_centroid = cluster_list[0];
for (int i = 1; i < cluster_list.Count; i++)
{
cluster_list[i].r = current_centroid.r;
cluster_list[i].g = current_centroid.g;
cluster_list[i].b = current_centroid.b;
}
}
Bitmap output = (Bitmap)this.mainBitmap.Clone();
foreach (List<GVector> cluster_list in clusters)
{
for (int i = 0; i < cluster_list.Count; i++)
{
GVector current_vector = cluster_list[i];
output.SetPixel(current_vector.x, current_vector.y,Color.FromArgb((int)current_vector.r, (int)current_vector.g, (int)current_vector.b));
//output[current_vector.x, current_vector.y] = Color.FromArgb((int)current_vector.r, (int)current_vector.g, (int)current_vector.b);
}
}
return output;
}
private void ApplyKMeans(int iteration)
{
this.output = CalculateKmeans(this.cluster, this.inputGVector, iteration);
}
public void Run(int iteration)
{
this.ApplyKMeans(iteration);
}
}
}
Kaynaklar
Anderberg, M. (1973). Cluster Analysis for Applications. Academic Press.
Demirhan, A., & Güler, İ. (2010). ÖZÖRGÜTLEMELİ HARİTA AĞLARI VE GRİ DÜZEY EŞ OLUŞUM MATRİSLERİ İLE GÖRÜNTÜ BÖLÜTLEME. Gazi Üniv. Müh. Mim. Fak. Der., 285–291.
Dubey, S. K., Vijay, S., & Pratibha. (2018). A Review of Image Segmentation using Clustering Methods. International Journal of Applied Engineering Research, 2484–2489.
Herkiloğlu, K. (2005). GAUSS KARIŞIM MODELLERİ KULLANILARAK SES İMZALARININ SINIFLANDIRILMASI. Yüksek Lisans Tezi.
Kalaycı, Ş. (2006). SPSS uygulamalı çok değişkenli istatistik teknikleri, Asil Yayın Dağıtım Evi, Ankara, TR, 426ss.
Kırmızıbiber, A., & Gökgöz, T. (2019). Hiyerarşik ve K-Ortalamalar Yöntemleriyle Grid Noktalarının Kümelenmesi. 17. Türkiye Harita Bilimsel ve Teknik Kurultayı, .
Oğuz, T. (2017). Metin Analitiği Ders Notları. Retrieved from ttps://acikders.ankara.edu.tr/pluginfile.php/171125/mod_resource/content/1/6%20Kümeleme.pdf
Romesbourg, C. (1984). Cluster Analysis for Researchers. Belmont: Lifetime Learning Publications.
Şengür, A., Türkoğlu, İ., & İnce, M. (2005). İki boyutlu entropi ile görüntü eşikleme uygulamaları. 275–278. Kayseri: IEEE 13. Sinyal İşleme ve İletişim Uygulamaları Kurultayı.
Şişeci, M., Metlek, S., & Çetişli, B. (2014). Alt-Bloklar Tekniği Ve Kümeleme Yöntemleri İle Görüntü Bölütlemenin Hızlandırılması. Journal of the Faculty of Engineering and Architecture of Gazi University, 655–664.
