R İLE HİYERARŞİK KÜMELEME ANALİZİ (HCL)

tarihinde yayınlandıGenel içinde yayınlandı
Facebooktwittergoogle_plusredditpinterestlinkedinmail

Doç. Dr. Kutlu MERİH

EğitimsizMakine Öğrenmesinde kümelene tekniği uygulamak istediğimizde kullanabieceğimiz iki standart yaklaşım vardır:
  • 1-Partisyon Teknikleri (k-means, PAM, CLARA gibi)
  • 2- Hiyerarşik Kümeleme.
Partisyon tekniklerini önceki çalışmamızda özetlemiş, hiyerarşik yöntemleri ayrıca inceleyeceğimizi vurgulamıştık. burada temel hiyerarşik kümeleme tekniklerini özetleyecek bunları R ile nasıl uygulayabileceğimizi ve görselleştirebileceğimizi araştıracağız.
Hiyerarşik kümeleme k-means tekniğinin benzer fakat alternatifi olup verisetlerindeki özgün grupları belirlemek için kullanılır. Burada grup sayısının k-means tekniğinde olduğu gibi önceden belirlenmesi gerekmez. Uygulama sonucunda gözlemler agaç tipi bir yapı içinde sergilenir buna DENDOGRAM denmektedir. Algoritma gözlemler arasında kümeleme kriteri olarak ikili bir mesafe uzaklık (distance) matrisi kullanmaktadır.

### Gerekli R Paketleri

library(cluster) #  PAM and CLARA hesaplamak için
library(factoextra) # Kümeleri görsel olarak grafiklemek için

 

Hiyerarşik Kümeleme Algoritmaları

Hiyerarşik kümeleme iki temel yapıda algoritma ile gerçekleştirilir; Agglomerative (Yığıştırma) ve Divisive (Bölüştürme)
  1. Agglomerative kümeleme : Kısaca AGNES (Agglomerative Nesting) olarak da adlandırlır. Tabandan yukarıya doğru çalışır. Burada her gözlem tek elemanlı bir küme (leaf-yaprak) olarak düşünülür. Sonra algoritmanın her adımında her küme kendine en çok benzeyen diğer küme ile daha büyük bir küme olarak birleştirilir. Bu süreç bütün elemanlar tek bir büyük küme (root-kök) oluncaya kadar sürdürülür. Sonuç bir dendogram (ağaç diyagramı) olarak grafiklenir.
  1. Divisive hiyrarşik kümeleme: Kısaca DIANA (Divise Analysis) olarak da bilinir ve tepeden-aşağı şekilde uygulanır. Bir anlamda AGNES in ters uygulamasıdır. Algoritma bütünü gözlemlerin tek bir küme olduğu root ile başlar ve her adımda en heterojen küme ikiye bölünür. Bu süreç bütün gözlemler uygun kümelerine yerleşinceye kadar sürdürülür.
Buradan  agglomerative kümelemenin küçük kümeleri belirlemede divisive hiyerarşik kümelemenin ise büyük kümeleri belirlemede iyi olduğu sonucunu çıkarabiliriz.
Kümeleri bütünleştirmek veya bölmek uygun bir benzersizlik (dissimilarity) metriğine göre geçekleştirilmektedir. R yazılımında Öklit metriği (herkesin bildiği) uygun bir benzersizlik metriği olarak default olarak kullanılmaktadır. İki eleman arasındaki Öklit metriğinin kolyaca hesaplanabileceği açık. Yukarda iki küme arasındaki benzersizlik metriğinden (dissimilarity metric) söz ettik. Bunu nasıl hesaplayacağız?

Kümeleme Metodları

Küme ayrıştırma ile ilgili geliştirilen bazı yöntemler (methods) söz konusudur. R paketleri bunların hemen hepsinden yararlanır. En genel yöntemler:
  • Maximum veya complete linkage kümeleme: Küme 1 ve Küme2 elemanları arasındaki bütün uzaklıkları hesaplar ve bunların en büyüğünü iki küme arasında uzaklık olarak kabul eder. Giderek daha sıkı kümelerin oluşmasını sağlar.
  • Minimum veya single linkage kümeleme: Küme 1 ve Küme2 elemanları arasındaki bütün uzaklıkları hesaplar ve bunların en küçüğünü iki küme arasında uzaklık olarak kabul eder. Giderek daha gevşek kümelerin oluşmasını sağlar.
  • Mean veya average linkage clustering: Küme 1 ve Küme2 elemanları arasındaki bütün uzaklıkları hesaplar ve bunların ortalamasını iki küme arasında uzaklık olarak kabul eder.
  • Centroid linkage kümeleme: Küme 1 centroid (p elemanlı ortalama vektor) ve Küme2 centroid arasındaki bütün uzaklıkları hesaplar
  • Ward minimum varyans yöntemi: Toplam küme içi varyansı minimize eder. Her adımda kümeler-arası mesafe minimum olan kümeler birleştirilir.
Complete linkage and Ward yöntemi genel olarak tercih edilir.

Hierarşik Kümeleme ve Korelasyon Tabanlı Uzaklık

Hiyerarşik kümelede ve R yazılımında farklı yöntem ve fonksiyonlar default olarak Öklit uzaklık metriği kullanırlar. Bu uygulamalarda korelasyon tabanlı metrikler kullanmak da mümkündür. Bunun için cor() fonksiyonu ile “pearson” “spearman” veya “kendall” opsiyonlu ikili korelasyonlar matrisi hesaplanır. Sonra bu korealasyon matrisi basit bir formül ile uzaklık matrisine dönüştürülür ve bununla kümeleme gerçekleştirilir.
res.cor <- cor(t(df), method = “pearson”)
d.cor <- as.dist(1 – res.cor)
plot(hclust(d.cor, method = “ward.D2”), cex = 0.6)

Ne tür bir uzaklık metriği seçilmeli?

Hiyerarşik kümelemede uzaklık metriği seçimi çok önemlidir. Çünkü bunun sonuç dendogramı üzerinde yoğun bir etkisi vardır. Genelde tercih edilen Öklit metriğidir fakat verinin yapısına ve ulaşılmak istenen sonuçlara göre korelasyon metriği de seçilebilir. Korelasyon metriği Öklit metriğine göre uzak sayılan verileri yakın olarak görebilir. Eğer gözlem kümelerini montanlarından bağımsız olarak gerçekleştirmek istiyorsak korelasyon metriği daha uygun bir seçim olabilir. Bu özellikle montandan bağımsız tercih yansıtan verisetleri için geçerlidir.

Hiyerarşik Kümeleme için R Paket-Fonksiyonları

R yazılımında hiyerarşik kümeleme yapılabilecek çeşitli paketler ve çeşitli fonksiyonlar bulunur. Bunların performansı farkedebilir. Deneyim en iyi seçimi sağlayacaktır. En çok kullanılanlar:
  • Agglomerative hiyerarşik kümeleme için
hclust() [base/stats paketinde] ve agnes() [cluster paketinde]
  • divisive HC için diana() [cluster paketinde]

hclust() function

Basit format:
hclust(d, method = “complete”)
help(hclust) ile;
d: dist() funksiyonu ile oluşturulmuş bir benzemezlik matrisi.
method: The agglomeration method to be used. Allowed values is one of “ward.D”, “ward.D2”, “single”, “complete”, “average”, “mcquitty”, “median” ve “centroid”.
Gözlemler arası Öklit uzaklık metriğini hesaplamak için dist() fonksiyonu kullanılır. Bundan sonra gözlemler Ward metodu ile kümelenir. Yardım formu başka metodların da (toplam 8 adet) tercih edilebileceğini gösteriyor.

agnes() ve diana() fonksiyonları

# AGglomerative NESting (Hierarchical Clustering)
agnes(x, metric = “euclidean”, stand = FALSE, method = “average”)
Fonksiyon agnes() “agnes” sınıfı bir object oluşturur: Bunda print(), summary(), plot(), pltree(), as.dendrogram(), as.hclus() cutree() metot fonksiyonları bulunur.

R ile Hiyerarşik Kümeleme Uygulamaları

Şimdi bu anlattıklarımızın R de nasıl gerçekleştiğine bakalım.Demo verisetimiz yine R/datasets  mtcars veriseti olacak.
# Load the data set
data(“mtcars”)
# Verisetinde olabilecek NA değerlerini ayıklayalım
df <- na.omit(mtcars) # bu verisetinde NA yok ama kritik bir adım olarak atlanmamalı
# Verisetinin ik 3 satırını görelim
head(df, n = 3)
# Hiyerarşik kümeleme öncesi bazı betimsel istatikleri hesaplayalım:
# Hiyerarşik kümeleme öncesi bazı betimsel istatikleri hesaplayalım:
stats <- function(dataset) {
ds<-dataset
dx<-data.frame(
Min = apply(ds, 2, min),            # minimum
Med = apply(ds, 2, median),   # median
Mean = apply(ds, 2, mean),     # mean
SD = apply(ds, 2, sd),                 # Standard deviation
Max = apply(ds, 2, max)           # Maximum
)
dx <- round(dx, 1)
return(dx)
}
print(stats(df))
#Burada değişkenlerin ortalama ve standart sapmalarının oldukça farklı olabildiğini görüyoruz. Bu durmda verisetini standardize etmek sağlıklı bir yaklaşım olacaktır. R/base scale() fonksiyonu verisetini istatistik standart skora dönüştürür. Bu kümelemenin bir değişken tarafından domine edilmesini engeller.
df <- scale(df)
head(df)
par(ask=TRUE) # ardışık grafikleri tıklamak için
# Dissimilarity matrisi
d <- dist(df, method = “euclidean”)
# Ward’s metodu ile HCL
res.hc <- hclust(d, method = “ward.D2” )
# Ağacı grafikle
plot(res.hc, cex = 0.6, hang = -1)
library(“cluster”)
# Compute agnes()
res.agnes <- agnes(df, method = “ward”)
# Agglomerative coefficient
res.agnes$ac
# Plot the tree using pltree()
pltree(res.agnes, cex = 0.6, hang = -1,
       main = “Dendrogram of agnes”)
# AGNES dendrogramı plot.hclust() ve plot.dendrogram() fonksiyonları kullanılarak da grafiklenebilir
# plot.hclust()
plot(as.hclust(res.agnes), cex = 0.6, hang = -1)
# plot.dendrogram()
plot(as.dendrogram(res.agnes), cex = 0.6, horiz = TRUE)
# Compute diana()
res.diana <- diana(df)
# Plot the tree
pltree(res.diana, cex = 0.6, hang = -1,
       main = “Dendrogram of diana”)
# Divise coefficient; amount of clustering structure found
res.diana$dc
# DIANA dendogram grafiği için plot.hclust() ve plot.dendrogram()
fonksiyonları da kullanılabilir
# plot.hclust()
plot(as.hclust(res.diana), cex = 0.6, hang = -1)
# plot.dendrogram()
plot(as.dendrogram(res.diana), cex = 0.6, horiz = TRUE)

 
 

Dendogram ın Yorumlanması

Düşey formdaki bir dendogram başaşağı bir ağaç şeklindedir. En altta yapraklar olarak veriseti elemanları bulunur. Ağaçta yukarıya doğru çıkıldıkça birbirine benzer olan gözlemler dallar halinde birleşmeye başlarlar. Bunlar da daha üst düzeylerde birleşirler. Düşey eksende gözlenen birleşim yüksekliği elemanların benzemezliğinin göstergesidir. Daha uzun bir dal daha az benzeyen elemana karşı gelir. Birleşmiş iki elemanın ne kadar benzer veya benzemez olduğu sadece dal yüksekliğinden anlaşılır. Yatay eksendeki pozisyonlar benzerliği yansıtmazlar. Alt grupları belirlemek için dendogram belirli bir yüksekliten kesilebilir.

Dendogramı farklı gruplara bölmek

Dendogramı kesme yüksekliği elde edilecek küme sayısını belirler. Bu işlem k-means algoritmasında k sayısının rolünü oynar fakat önceden belirlenmesi gerekmez. Her gözlemin ait olduğu küme sayısı cutree() fonksiyonu ile verilen bir vektör ile belirlenir.
par(ask=TRUE)
# Cut tree into 2 groups
grp <- cutree(res.hc, k = 2)
# Her kümedeki eleman sayısı
table(grp)
# Küme 1 deki elemanların isimleri
rownames(df)[grp == 1]
#Dendogramı iki küme etrafında border ile grafiklemek. Her küme için farklı renk
plot(res.hc, cex = 0.6)
rect.hclust(res.hc, k = 2, border = 2:5)
#cutree() fonksiyonu agnes() ve diana() ile yaratılmış ağaçları da bölmek için kullanılabilir.
# Ağaç agnes() 2 gruba dağıt
cutree(as.hclust(res.agnes), k = 2)
# Ağaç diana() 2 gruba dağıt
cutree(as.hclust(res.diana), k = 2)
 
# Dendogram fviz_cluster() [factoextra paketinde] fonksiyonu ile saçılım grafiğine de dönüştürülebilir. Burada gözlemler PCA sonuçları kullanılarak kümelere dağılacaktır. Her küme etrafına bir çerçeve çizilir.
library(factoextra)
tma<-theme_igray()
fviz_cluster(list(data = df, cluster = grp))+tma
 

 

Facebooktwittergoogle_plusredditpinterestlinkedinmail