Clustering — Kumeleme
Clustering nedir?
Kümeleme ya da kümeleme analizi bir unsupervised learning (denetimsiz öğrenme) problemidir. Verilerdeki doğal olarak oluşan gruplanmayı keşfetmeyi amaçlar. Supervised learning algoritmalarının aksine, yalnızca girdileri kullanarak, grup ve kümeleri tespit eder. Supervised learning ve unsupervised learning arasındaki farkları hatırlamak için burayı ziyaret edebilirsiniz.
Kümeleme algoritmaları genellikle datada bulunan benzerlikleri analiz etmek maksadıyla kullanılır. Birden fazla kümeleme algoritması bulunmaktadır. Ve tüm durumlar için mükemmel çalışan bir algoritma maalesef ki bulunmamaktadır. Bunun yerine, farklı algoritmaları, farklı datalarda kullanmak daha sağlıklı olacaktır.
Kümeleme algoritmaları, etiketsiz verilerde, tahmin edilecek bir sınıf olmadığında kullanılır. Kümeleme, genellikle datanın featurelarının uzayda bir topluluk oluşturması ve bu topluluğun diğer topluluklardan ayrık olması esasına dayanır.
Kümeleme, pattern discovery (model keşfi) veya knowledge discovery (bilgi keşfi) olarak adlandırılan problem alanı hakkında daha fazla bilgi edinmek için bir veri analizi etkinliği olarak yardımcı olabilir.
Örnek olarak :
- Yapılan alışveriş çeşitlerine göre müşterilerin kümelenmesi
- Normal data ile outlierların ayırt edilmesi
- Normal haberlerin kümelenerek, fake haberlerin tespit edilmesi
- Gelen mailler arasından spam olanların ayırt edilmesi
gibi durumlardır.
Kümeleme algoritmalarının performansını ölçecek bazı metrikler bulunmasına rağmen, bu değerlendirmeleri yapmak uzmanlık bilgisi gerektirmektedir.
K-means Clustering
Kmeans kümeleme algoritması, en çok kullanılan kümeleme algoritması olabilir. Her küme içindeki varyansı en aza indirecek kümelere örneklemleri atamayı içerir.
Verilen datasette bulunan örneklemleri, modelde tanımlanan k kadar kümeye bölmeyi hedefler. Kümelere bölme işleminde amaç, aynı kümede bulunan örneklemlerin benzerliklerinin maksimum olması, kümeler arası benzerliğin minimum olması esasına dayanır.
K-means kümeleme algoritması, uygulaması kolay olması sebebiyle sık kullanılan bir algoritmadır. Büyük ölçekli verileri hızlı ve etkin şekilde kümeleyebilir. Modelde bulunan “K” parametresi, datasette bulunacak küme sayısını ifade eder. Kmeans algoritması, her verinin ait olduğu kümeye olan uzaklıkları toplamını küçültmektedir. Kmeans algoritması karesel hatayı en küçük yapacak olan K adet kümeyi tespit etmeye çalışmaktadır.
Kmeans algoritmasının çalışma prensibi ise şu şekildedir. Öncelikle her kümenin merkez noktasını veya ortalamasını temsil etmek üzere K adet nesne rastgele seçilir. Kalan diğer nesneler, kümelerin ortalama değerlerine olan uzaklıkları dikkate alınarak en benzer oldukları kümelere dahil edilir. Daha sonra, her bir kümenin ortalama değeri hesaplanarak yeni küme merkezleri belirlenir ve tekrar nesnelerin merkeze uzaklıkları incelenir. Herhangi bir değişim olmayıncaya kadar algoritma tekrarlamaya devam eder. Burada bulunan scriptte her adımda kümelerin ve küme merkezlerinin nasıl yer değiştirdiği çok net bir şekilde görülmektedir.
Algoritma temel olarak 4 aşamadan oluşur:
- Küme merkezlerinin belirlenmesi (random olarak)
- Merkez dışındaki verilerin mesafelerine göre kümelendirilmesi
- Yapılan kümelendirmeye göre yeni merkezlerin belirlenmesi (veya eski merkezlerin yeni merkeze kaydırılması)
- Kararlı hale (stable state) gelinene kadar 2. ve 3. adımların tekrarlanması.
Burada görüldüğü üzere en temel sorun, küme sayısının tespit edilmesi olacaktır. Bunun için nasıl bir yol haritası izlenebilir?
Elbow Metodu
Elbow Metodu : Unsupervised learning algoritmalarında kümeleme problemleri için en optimal küme sayısını belirlemede kullanılan metoddur.
Bu metodda temel amaç, küme sayısının bilinmediği veya tahmin edilemediği durumda, 1'den başlayarak, yüksek sayılardaki küme sayılarına kadar tüm kümeleme bozulma/ataletini tespit edip, bu bozulma/ataletin minimize olduğu yerde, dirsek durumunun oluştuğu yerdeki numaranın, küme sayısı olarak alınması esasına dayanır.
Yukarıdaki grafikte görüldüğü üzere, inertia değerinin, 3'ten sonra (X ekseni — küme sayısını simgeler) değişime pek uğramadığı, 3 sayısının olduğu yerde bir dirsek şekli aldığı görülmektedir. Dolayısıyla böyle bir dataset için k=3 alınarak KMeans algoritmasının uygulanması uygun olacaktır.
K-Means algoritmasının avantajları ve dezavantajları nelerdir?
K-Means algoritmasının avantajları:
- Uygulaması kolaydır.
- Diğer kümeleme algoritmalarına göre hesaplama yönünden efektif algoritmadır.
- Sonuçların yorumlanması kolaydır.
- Hiyerarşik algoritmaların aksine zaman kompleksity (time complexity) yönünden avantajlıdır.
K-Means algoritmasının dezavantajları:
- Küme sayısını önceden tahmin etmek zor olabilir.
- Başlangıç değerleri sonuç üzerinde çok etkilidir.
- Outlierlara karşı hassastır.
Agglomerative Clustering
Hiyerarşik Kümeleme nedir?
Agglomerative kümeleme, hiyerarşik kümeleme algoritmasının en ünlü algoritmasıdır. Öncelikle isterseniz hiyerarşik kümelemeden bahsedelim biraz.
Mesela hayvanlar alemini inceliyoruz. Hayvanları alt kümelere ayıralım. Kediler, köpekler, balıklar, kuşlar vs. Tabii ki bu alt kümeleri de alt kümelere bölebiliriz. Mesela kediler kümesini, Scottish, British, Van kedisi vs gibi alt dallara ayırabiliriz. Aynı şekilde köpek, balık, kuşlar içinde alt kümeler yapılabilir. Bu alt kümelerde alt kümelere ayrılarak daha da dallanıp budaklanabilir. İşte görüldüğü üzere burada bir hiyerarşi söz konusudur.
Hiyerarşik kümeleme iki farklı algoritma ile çalışabilir. Agglomerative kümeleme ve Divisive kümeleme.
Agglomerative kümeleme nedir?
Agglomerative kümeleme de temel mantık olarak, N elemanlı bir datasetten N adet küme oluşturur. Daha sonra birbirine en benzeyen iki küme birleştirilir ve bir büyük küme meydana getirilir. Bu işlem tüm datasete uygulanır. Yani en alt elemandan başlanarak en yukarı kadar kümeleme hedeflenir.
Agglomerative kümelemenin tersi ise DIANA (Divisive Analysis)’dir ve bütün datasetten parçalara ayrılarak kümelerin bulunması hedeflenir.
Yukarıdaki şekilde, Agglomerative kümeleme ve DIANA’ya ait diyagram gösterilmiştir.
Dendogram nedir?
Dendogram, hiyerarşik kümelemede, birbirine benzeyen örneklemleri birleştirerek, bir ağaç yapısında, tek küme kalana kadar yapılan işlemler bütünüdür.
Dendogram yardımı ile hiyerarşik kümedeki küme sayısını tespit edebiliriz. Bir örnek ile öğrendiklerimizi somut hale getirelim.
Bir sentetik dataset oluşturalım ve kümeleme işlemini yapmaya başlayalım.
from sklearn import datasets
import matplotlib.pyplot as plt
import numpy as np
import pandas as pdX, y = datasets.make_blobs(n_samples=100, n_features=8, centers=5, center_box=(-40, 40)) # we have 8 features hereplt.scatter(X[:,0], X[:,1], c=y)
Yukarıda 8 feature’a sahip, 5 küme merkezi olan sentetik dataset ürettim. Şimdi bu görüntünün grafiğini inceleyelim.
Şimdi hemen bir scaling işlemi yapalım ve boyut indirgeyelim. (Boyut indirgemeye ait detaylar için burayı ziyaret ediniz. Scaling işlemlerine ait detaylar için burayı ziyaret ediniz.)
# scaling işlemi
from sklearn. preprocessing import StandardScaler, normalize
sc = StandardScaler()
X_scaled = sc.fit_transform(X)
X_normalized = normalize(X_scaled)# boyut indirgeme
# because we have 8 features, its too much. Lets reduce dimensionsfrom sklearn. decomposition import PCA
pca = PCA(n_components=3)
X_norm = pca.fit_transform(X_normalized)
X_norm = pd.DataFrame(X_norm)
X_norm.columns = ['P1', 'P2', 'P3']# şimdi artık dendogram grafiğimi çizdirebilirim.import scipy.cluster.hierarchy as hc
plt.figure(figsize =(8, 8))
plt.title('Visualising the data')
dendrogram = hc.dendrogram((hc.linkage(X_norm, method ='ward')))
Şimdi dendogram grafiğini yorumlayarak, datasette kaç küme olduğunu tespit edelim. Dendogram grafiğinde, en uzun bacakların olduğu yerden çizgi çizilerek, oradaki bacak sayısı kadar küme olduğu farz ve kabul edilir. Evet açıklama çok sağlıklı olmadı, farklı bir dille tekrar edelim. Dendrogramda düğümler arasındaki en büyük dikey farkı bulun ve ortasından yatay bir çizgi geçin. Onu kesen dikey çizgilerin sayısı, optimal küme sayısıdır. Şimdi bir görselle ne demek istediğimi anlatayım.
Grafikte çizdiğimi kırmızı hattı dikkate alalım. Turuncu ve mavi düğümlere tek tek baktığımızda, her bir bacak son derece uzun dikey farklar oluşturmuştur.
Burada görseli biraz daha canlandırmak istedim. Yani anlaşılmama durumuna istinaden, 1,2,3,4 ve 5 numaralı düğümlerin birbirine mesafelerine bakalım. 1–2 arasındaki mesafe, 2–3 arasındaki mesafe ve 3–4 arasındaki mesafeler dikkate alındığında, 4–5 arasındaki mesafenin en uzun olduğu görülmektedir. Dolayısıyla, 4–5 arasındaki düğümlerden çizdiğim kırmızı çizginin üzerinden geçen bacak sayısı 5 olarak görülmektedir. Yani bu dendogram grafiğindeki ideal küme sayısını 5 olarak tespit ediyorum.
Şimdi konuyu daha fazla uzatmadan, Agglomerative kümeleme algoritması ile 5 küme sayısında elde ettiğim şekli inceleyelim.
from sklearn.cluster import AgglomerativeClusteringagg = AgglomerativeClustering(n_clusters=5)
#Lets assume that we have 5 clustersplt.figure(figsize =(8, 8))
plt.scatter(X_norm[‘P1’], X_norm[‘P2’], c = agg.fit_predict(X_norm), cmap =’rainbow’)
plt.title(“Agglomerative Clusters — Scatter Plot”, fontsize=18)
plt.show()
Evet görüldüğü üzere, dendogramda bulduğumuz 5 küme sayısını Agglomerative kümeleme ile tahminlediğimizde, yukarıdaki görselde güzel bir tahminleme yaptığımızı görüyoruz.
Buraya kadar Agglomerative kümelemenin başarılarından bahsettik ancak tabii ki her datasette başarılı olmasını beklemek yanlış olur.
Son olarak, hiyerarşik kümeleme ile öğrendiklerimizi özetleyelim.
- Hiyerarşik kümeleme, hiyerarşik sıralamaya dayalı kümeleri oluşturmak için kullanılan denetimsiz bir öğrenme algoritmasıdır.
- İki farklı tür hiyerarşik kümeleme algoritması vardır — Agglomerative kümeleme ve Divisive kümeleme. Dendogram grafik yardımı ile ideal küme sayısı belirlenebilir.
- Agglomerative hiyerarşik kümelemede, kümeleme tek tek noktalardan başlar ve kümeler, bir küme — kök küme kalana kadar yukarı doğru oluşturulur. Aşağıdan yukarıya hiyerarşik kümeleme olarak da adlandırılır.
- Division hiyerarşik kümelemede kümeleme yukarıdan başlar, örneğin tüm veriler tek bir küme olarak alınır. Kök küme iki kümeye bölünür ve her ikisi de ikiye bölünür ve bu, bireysel noktalara sahip kümeler oluşana kadar yinelemeli olarak devam eder. Yukarıdan aşağıya hiyerarşik kümeleme olarak da adlandırılır.
Agglomerative kümeleme ve detayları için buradaki linkten notebooka erişebilirsiniz.
Hiyerarşik algoritmaların avantajları ve dezavantajları nelerdir?
Hiyerarşik algoritmaların avantajları:
- Uygulaması kolaydır.
- Küme sayısını önceden belirtme ihtiyacı yoktur. (dendogram ile bulunabilir)
- Bir hiyerarşik yapıya göre karar verdiğinden küme sayısı kolaylıkla seçilebilir.
Hiyerarşik algoritmaların dezavantajları:
- Bazı datasetlerde çok iyi sonuçlar verebilir.
- Önceki adımı geri almak mümkün değildir: örnekler bir kümeye atandıktan sonra artık hareket ettirilemezler.
- Zaman karmaşıklığı: büyük veri kümeleri için uygun değildir.
- Outlierlara karşı hassastır.
Şimdi isterseniz son olarak DBSCAN üzerinde biraz sohbet edelim ve kümeleme çalışmamızı sonlandıralım.
DBSCAN nedir?
DBSCAN — Density-Based Spatial Clustering of Applications with Noise.
DBSCAN algoritması, yüksek yoğunluklu çekirdek örnekleri bulur ve bunlardan kümeleri genişletir. Benzer yoğunlukta kümeler içeren veriler için iyidir.
Şimdi kümelemenin temel mantığını aklımıza getirdiğimizde, kümeler kendi içinde bir topluluk oluşturacaktır ve kümeler arasında bir nebze boşluk (mesafe) olması beklenmektedir. İşte burada, DBSCAN algoritması, KMeans algoritmasının aksine, yoğunluk olarak kümeleri değerlendirmektedir. Bu sayede, DBSCAN algoritması herhangi bir şekilde (iç içe kümeler veya ay şeklinde ayrılmış datasetler vs.) ayrılmış kümeleri tespit etme konusunda başarılı sonuçlar vermektedir.
Dolayısıyla kümeler birbirine yakın (herhangi bir mesafe ölçütü olabilir. Mesafe ölçütleri hakkında detaylı bilgi için burayı ziyaret ediniz) mesafelerde olmalıdır. DBSCAN algoritması, yoğunluk tespiti yapmak maksadıyla min_samples ve eps parametrelerini kullanır. eps parametresi örneklemler arasındaki maksimum mesafeyi tanımlarken, min_samples parametresi, noktanın, çekirdek nokta olarak varsayılması için bulunması gereken örneklem sayısı olarak tanımlanır. Bu iki parametre ile yoğunluk hakkında fikir sahibi olmak hedeflenmektedir.
Yani kümemdeki nokta, min_samples sayısı ile küme çekirdeği olarak temsil edilmektedir. Yine bulunan komşulara aynı işlemler uygulanarak yeni komşular tespit edilmektedir. Sezgisel olarak, bu örnekler bir kümenin sınırlarındadır.
Herhangi bir çekirdek örnek, tanım gereği bir kümenin parçasıdır. Çekirdek örnek olmayan ve herhangi bir çekirdek örnekten en az eps uzaklıkta olan herhangi bir örnek, algoritma tarafından aykırı değer olarak kabul edilir.
min_samples parametresi öncelikle algoritmanın gürültüye karşı ne kadar toleranslı olduğunu kontrol ederken (gürültülü ve büyük veri setlerinde bu parametrenin arttırılması istenebilir), eps parametresinin veri seti ve mesafe fonksiyonu için uygun şekilde seçilmesi çok önemlidir ve genellikle varsayılan değerde bırakılamaz. Noktaların yerel komşularını kontrol eder. Çok küçük seçildiğinde, çoğu veri kümelenmez (ve “gürültü” için -1 olarak etiketlenir). Çok büyük seçildiğinde, yakın kümelerin tek bir kümede birleştirilmesine ve sonunda tüm veri kümesinin tek bir küme olarak döndürülmesine neden olur.
Şu ana kadar soyut olarak konuştuğumuz konuyu bir tablo ile somut hale getirelim.
Yukarıda görülen kümelenmiş datasette toplam 3 adet küme tespit edilmektedir. Siyah olarak tespit edilen noktalar ise outlier olarak değerlendirilmektedir. Şekil dikkatli incelendiğinde merkez konumda olan örneklemlerin büyük, sınır durumunda olan örneklemlerin küçük olarak işaretlendiğini görüyoruz. İşte min_samples sayısı kadar komşusu olan noktalar core sample (çekirdek örneklem) olarak tanımlanmaktadır. min_samples kadar komşusu olmayan noktalar ise çekirdek olmayan kümenin sınır uçlarında bulunan örneklem olarak tanımlanmaktadır. Noktalar arasındaki mesafe ise eps parametresi ile ölçülür. eps değeri arttırılır ise, küme merkezlerine yakın olan siyah noktalardan bazıları, küme merkezlerine dahil edilebilir. Veya eps değeri küçük seçilirse, küme içerisinde tespit edilen bazı noktalar, outlier durumuna düşebilir.
DBSCAN algoritması deterministiktir, aynı veriler aynı sırada verildiğinde her zaman aynı kümeleri oluşturur. Ancak, veriler farklı bir sırada sağlandığında sonuçlar farklılık gösterebilir.
İlk olarak, çekirdek örnekler her zaman aynı kümelere atanacak olsa da, bu kümelerin etiketleri, verilerde bu örneklerin karşılaşıldığı sıraya bağlı olacaktır.
İkincisi ve daha da önemlisi, çekirdek olmayan örneklerin atandığı kümeler, veri sırasına bağlı olarak farklılık gösterebilir. Bu, çekirdek olmayan bir örneklemin farklı kümelerdeki iki çekirdek örnekleme eps’den daha düşük bir mesafeye sahip olması durumunda gerçekleşir. Normalde kümelerin birnirine eps’den daha uzak mesafelerde olması beklenir, yoksa aynı kümede olurlardı. Çekirdek olmayan örnek, verilerden geçişte ilk oluşturulan kümeye atanır ve bu nedenle sonuçlar, veri sıralamasına bağlı olacaktır. (Yani sıralama değiştiğinde eps mesafede olan çekirdek olmayan bir örneklem, veri sırası değiştiğinde eps mesafesinde olan farklı bir kümeye ait olma ihtimali olabilir.)
Peki, bu kadar teorik ve sıkıcı bilginin ardından bir uygulama ile DBSCAN konusunu taçlandıralım isterseniz.
import numpy as np
import matplotlib.pyplot as plt
from sklearn import cluster, datasets, pipeline, preprocessing
from ipywidgets import interactX, y = datasets.make_blobs(random_state=42)m = cluster.DBSCAN()
clusters = m.fit_predict(X)
plt.scatter(*X[clusters!=-1].T, c=clusters[clusters!=-1])
plt.scatter(*X[clusters==-1].T, color='red')
Evet default parametreler ile oluşturduğumuz DBSCAN algoritmasına ait tahminler aşağıda gösterilmiştir.
Görüldüğü üzere, default değerler, modelde ekseriyetle outlier tespit etmiştir. Yani yazının içeriğinde de belirttiğim gibi, default değerlerden ziyade net bir ifade vermek daha sağlıklı olabilecektir. Şimdi eps = 1 değeri ile modelin tahmini inceleyelim.
m = cluster.DBSCAN(eps=1.0)
clusters = m.fit_predict(X)
plt.scatter(*X[clusters!=-1].T, c=clusters[clusters!=-1])
plt.scatter(*X[clusters==-1].T, color=’red’)
Evet, görüldüğü üzere model tahminleme konusunda daha başarılı sonuçlar üretmektedir. Datasetteki örneklemlere ait küme tahminlemesi yapmak maksatıyla fit_predict metodunu kullanıyoruz. fit_predict metodunda, tahmin olarak küme numaraları verilmektedir. Arada -1 olarak tahminlenen örneklemlerde bulunmaktadır. -1 olarak tahminlenen örneklemler, outlier değerleri temsil etmektedir.
m = cluster.DBSCAN(eps=1.0)X = preprocessing.StandardScaler().fit_transform(X)clusters = m.fit_predict(X)
plt.scatter(*X[clusters!=-1].T, c=clusters[clusters!=-1])
plt.scatter(*X[clusters==-1].T, color=’red’)
Şimdi aynı değerlere sahip dataseti scale işlemi uygulayıp sonucunu görelim.
Görüldüğü üzere scale işlemi öncesinde outlier olarak tespit edilen örneklemler de, scale işleminden sonra kümelere dahil edilmiş oldu. Bu kapsamda şu yorumu yapabiliriz. Mesafe konusu gündeme geldiği DBSCAN algoritmasında da scale işlemi yapmak önem arz etmektedir.
Son olarak yaptığım işlemleri bir boru vasıtasıyla göze daha hoş gelen bir şekilde sergileyip bu konuyu kapatıyorum. DBSCAN algoritmasına ait notebook burada bulunmaktadır.
p = pipeline.Pipeline([(‘1’, preprocessing.StandardScaler()),
(‘2’, cluster.DBSCAN())])clusters = p.fit_predict(X)plt.scatter(*X[clusters!=-1].T, c=clusters[clusters!=-1])
plt.scatter(*X[clusters==-1].T, color=’red’)
DBSCAN algoritmasının avantajları ve dezavantajları nelerdir?
DBSCAN algoritmasının avantajları:
- DBSCAN, küme sayısının önceden belirtilmesini gerektirmez.
- DBSCAN, rastgele şekillendirilmiş kümelerle iyi performans gösterir.
- DBSCAN’ın bir gürültü kavramı vardır ve aykırı değerlere karşı dayanıklıdır.
DBSCAN algoritmasının dezavantajları:
- DBSCAN, yoğunluklarında büyük farklılıklar olan veri kümelerini iyi bir şekilde kümeleyemez
- Veriler iyi anlaşılmadıysa anlamlı bir eps değeri seçmek zor olabilir.
- DBSCAN tamamen deterministik değildir. Bunun nedeni, algoritmanın rastgele bir nokta ile başlamasıdır. Bu nedenle, birden fazla kümeden ulaşılabilen sınır noktaları, herhangi bir kümenin parçası olabilir.
Kümeleme konusuna genel olarak değinmiş olduk. Kümeleme konusunu etiketsiz dataya uygulamakla beraber, sınıflandırma problemlerinde, örneklemlerin kümelerini belirleyip, ekstra bir feature olarak da uygulayabiliriz. Bu durumda başarı skorumunuzun artmasını hedefleyebiliriz.
Sabrınız için teşekkürler, umarım faydalı olmuştur…
Referances :
