Kümeleme

“Ne kadar başarılı olursanız olun, öğrenimlerinizi daima başkalarıyla paylaşın.” Michael Jorden

Herkese merhaba,

Bugün kümele konusuna değineceğim.Kümeleme hem veri madenciliği hemde veri bilimi alanları için oldukça önemlidir.Yanlışlarım olursa şimdiden affınıza sığınıyorum.

Kümeleme birbirlerine benzeyen veri parçalarını ayırma işlemidir ve kümeleme yöntemlerinin çoğu veri arasındaki uzaklıkları kullanır.

Örneğin Öklid, Manhattan ve Minkowski uzaklık bağıntıları kümeleme işlemlerinde alt işlem olarak kullanılmaktadır. Kümeleme yöntemleri arasında akla ilk en yakın komşu algoritması ve en uzak komşu algoritması gelmektedir;bunlar hiyeraşik kümeleme yöntemleri olarak bilinir. Hiyeraşik olmayan kümeleme yöntemleri arasında k-ortalamalar yöntemi sayılabilir.

Kümeleme Çözümlemesi

Kümeleme Çözümlemesi, verilerin birbirleriyle benzer alt kümelere ayırma işlemidir. Çok sayıda kümeleme yöntemi kullanılmaktadır. Bu yöntemler değişkenler arasındaki benzerliklerden ya da farklılıklardan yararlanarak kümeyi alt kümelere ayırmakta kullanılmaktadır.

Kümeleme çözümleri istatistikte başvurulan yöntemlerdir. Aslında kümeleme çözümleri birbirine benzeyen gözlem değerlerinin ayrılarak sınıflandırılmasını sağlayan çok değişkenli çözümleme yöntemleri olarak karşımıza çıkmaktadır.

Kümeleme çözümleri pazarlama faaliyetlerinde sıkça kullanılır. Örneğin bir mamulden farklı beklentilerine göre müşterileri kümelere ayrılabilir. Bunun dışında belirli ürünleri kullanıcıların davranış biçimine göre gruplandırmak söz konusu olabilir. Böylece çözümleme ile elde edilen sonuçlara bakılarak pazarlama stratejisi belirlenebilir.

Uzaklık Ölçüleri

Kümeleme yöntemlerinin çoğu gözlem değerleri arasındaki uzaklıkların hesaplanması esasına dayanmaktadır.O nedenle iki nokta arasındaki uzaklığı hesaplayan bağıntılara gereksinim vardır.

Çeşitli değişkenlerden oluşan gözlem değerlerini bir X matrisi biçiminde gösterebiliriz.Örneğin üç değişken 5 gözlemden oluşan matris aşağıdaki gibi ifade edilebilir.

(X11,x12,x13) >1.gözlem noktasının konumu

(X21,x22,x23)=>2.gözlem noktasının konumu

Bu iki nokta arasındaki uzaklık d(1,2) şeklinde ifade edilir.

X matrisinin her bir satırının diğerine olan uzaklığı d(i,j) olarak ifade edilecek olursa, simetrik D uzaklıklar matrisi şu şekilde yazılabilir:

Yukarıdaki matrisin üst kısmı alt kısmının simetriği olduğundan ayrıca yazılmamıştır.Bu durumda d(i,j)=d(j,i) olduğu kabul edilir.

Kümeleme çözümlemelerinde birçok uzaklık bağıntısı kullanılabilmektedir.Bu bölümde Öklit,Manhattan ve Minkowski uzaklıklarına değineceğiz.

1-ÖKLİT UZAKLIĞI

Uygulamalarda en çok kullanılan uzaklık ölçüsü Öklid uzaklık bağıntısı adıyla bilinmektedir.

Bu uzaklık iki boyutlu uzayda Pisagor teoreminin bir uygulaması olarak karşımıza çıkmaktadır.

A ve B noktası arasındaki Öklit uzaklığı aşağıdaki gibidir:

Bu bağıntı genelleştirilecek olursa i ve j noktaları için şu şekilde bir bağıntıya ulaşılır:

2- MANHATTAN UZAKLIĞI

Manhattan uzaklığı, gözlemler arasındaki mutlak uzaklıkların toplamı alınarak hesaplanır

3 – MİNKOWSKİ UZAKLIĞI

P sayıda değişken göz önüne alınarak gözlem değerleri arasındaki uzaklığın hesaplanması söz konusu ise Minkowski uzaklık bağıntısı kullanılabilir.

Burada m=2 yazılarak Öklid uzaklık bağıntısı elde edilebilir.

Örnek

A,B ve C gibi üç değişkenden oluşan aşağıdaki gözlemleri göz önüne alalım.Bu gözlem noktalarının her birinin birbirine olan uzaklığını farklı uzaklık ölçüleriyle elde etmek istiyoruz.

Öklid Uzaklığı: Burada yer alan üç değişken için, i ve j gözlem noktaları ve p=3 olmak üzere Öklit uzaklık bağıntısını şu şekilde tanımlayabiliriz:

İkinci gözlem ile birinci gözlem arasındaki uzaklık şu şekilde hesaplanır:

Üçüncü gözlem ile ikinci gözlem arasındaki uzaklık şu şekilde hesaplanır:

Her bir gözlem arasındaki Öklit uzaklıkları hesaplandığında aşağıdaki sonuçlar elde edilir:

Manhattan Uzaklığı:Örnekteki veriler kullanılarak 3 değişken için Manhattan uzaklığı aşağıdaki gibi hesaplanır:

İkinci gözlem ile birinci gözlem arasındaki Manhattan uzaklığı aşağıdaki gibidir:

Üçüncü gözlem ile ikinci gözlem arasındaki Manhattan uzaklığı aşağıdaki gibidir:

Tüm gözlemlerin birbirlerine olan uzaklıkları hesaplandığında aşağıdaki sonuçlar elde edilir:

Minkowski Uzaklığı:Örnekteki veriler kullanılarak 3 değişken için Minkowski uzaklığı aşağıdaki gibi hesaplanır:

Bu bağıntıdan yararlanarak m=3 varsayımı altında ikinci gözlem ile birinci gözlem arasındaki Minkowski uzaklığı şu şekilde hesaplanır:

Bu bağıntıdan yararlanarak m=3 varsayımı altında üçüncü gözlem ile ikinci gözlem arasındaki Minkowski uzaklığı:

Tüm gözlem arasındaki uzaklıklar hesaplandığında aşağıdaki sonuçlar elde edilir:

Hiyerarşik Kümeleme

Kümelerin bir ana küme olarak ele alınması ve sonra aşamalı olarak içerdiği alt kümelere ayrılması veya ayrı ayrı ele alınan kümelerin aşamalı olarak bir küme biçiminde birleştirilmesi esasına dayanır.

1.Birleştirici Hiyerarşik Yöntemler,

Ayrı ayrı ele alınan kümelerin aşamalı olarak birleştirilmesini sağlayan yöntemlerdir.

Bu yöntemlerden aşağıda belirtilenleri ele alarak inceleyeceğiz:

A) En yakın komşu algoritması

B) En uzak komşu algoritması

A) En Yakın Komşu Algoritması

En yakın komşu yöntemine “tek bağlantı kümeleme yöntemi ” adı da verilmektedir. Başlangıçta tüm gözlem değerleri birer küme olarak değerlendirilir.Adım adım bu kümeler birleştirilerek yeni kümeler elde edilir.

Bu yöntemde öncelikle komşular arasındaki uzaklıklar belirlenir.i ve j gözlem noktaları arasındaki uzaklıkların hesaplanmasında öklit bağıntısı kullanılabilir.

Uzaklıklar göz önüne alınarak Min d(i,j ) seçilir.Söz konusu uzaklıkla ilgili satırlar

birleştirilerek yeni bir küme elde edilir.Bu duruma göre uzaklıkların yeniden

hesaplanması gerekir. Birden fazla gözlem değerine sahip olan iki küme arasındaki uzaklığın belirlenmesi gerektiğinde farklı bir yol izlenir.İki kümenin içerdiği gözlemler arasında “birbirine en yakın olanların uzaklığı” iki kümenin birbirine olan uzaklığı olarak ifade edilir.

En yakın komşu algoritmasında iki kümenin birbirine ne yakın gözlemleri arasındaki uzaklık iki kümenin birbirine olan uzaklığı olarak değerlendirilir.

ÖRNEK

Aşağıdaki tabloda verilen 5 adet gözlemi göz önüne alalım.Bu veriler üzerinde en yakın komşu algoritmasını kullanarak kümeleme işlemlerini yapmak istiyoruz.

ADIM 1 :Öncelikle uzaklık tablosunun (matrisinin) hesaplanması gerekiyor. Bunun için Öklit uzantı ölçüsünü kullanalım.

Bu formül yardımıyla aşağıdaki hesaplamalar yapılır daha sonra gözlemlere ilişkin uzaklıklar matrisi çıkartılır.

ADIM 2: Uzaklıklar tablosunda Min d(i,j) hücresinin belirlenmesi gerekiyor.Tablo incelendiğinde Min d(i,j)=1.41 olduğu görülür.O halde bu değerin ilgili olduğu 1 ve 3 numaralı gözlemler ele alınır.Bu iki değer birleştirilerek (1,3) kümesi elde edilir.Şimdi elde edilen bu kümeye göre uzaklıklar matrisini yeniden gözden geçirelim.Bu amaçla (1,3) kümesi ile 2,4 ve 5 numaralı gözlemler arasındaki uzaklıkları belirleyelim.

Bu durumda uzaklıklar tablosu aşağıdaki gibi olur:

ADIM 4: Uzaklıklar tablosu incelendiğinde Min d(i,j)=2.83 olduğu görülür.O halde bu uzaklık ile ilgili 2 gözlemi ile (1,3) kümesi birleştirilecektir.Elde edilen (1,2,3) kümesi ile (4,5) kümesi arasındaki uzaklığı belirlemek için kümeler içindeki her bir değeri eşliyoruz ve aralarında en küçük olanı belirliyoruz.

ADIM 5: Elde edilen son iki küme birleştirilerek sonuç küme elde edilir.Bu küme (1,2,3,4,5) gözlemlerinden oluşan kümedir.Uzaklık düzeyi göz önüne alınarak kümeler şu şekilde belirlenmiştir:

HİYERARŞİK OLMAYAN KÜMELEME

K-Ortalamalar Yöntemi

Bu yöntemde daha başlangıçta belli sayıdaki küme için toplam ortalama hatayı minimize etmek amaçlanır. N boyutlu uzayda N örnekli kümelerin verildiğini varsayalım.Bu uzay { C1,C2,…..,Ck} biçiminde K kümeye ayrılsın.

O zaman ∑nk= N (k=1,2,…,k))olmak üzere Ck kümesinin ortalama vektörü Mk şu şekilde hesaplanır.

Burada Xk değeri Ck kümesine ait i. örnektir. Ck kümesi için kare-hata, her bir Ck değeri ile onun merkezi arasındaki Öklit uzaklıkların toplamıdır.Bu hataya “küme içi değişme” adı da verilir.Küme içi değişmeler şu şekilde hesaplanır:

K kümesini içeren bütün kümeler uzayı için kare-hata,küme içindeki değişmelerin toplamıdır.O halde söz konusu kare-hata değeri şu şekilde hesaplanır.

Kare-hata kümeleme yönteminin amacı, verilen K değeri için Ek2 değerini minimize eden K kümelerini bulmaktır.O halde k-ortalama algoritmasında Ek2 değerinin bir önceki iterasyona göre azalması gerekir.

Algoritma

K-ortalama algoritmasına başlamadan önce k küme sayısının belirlenmesi gerekir. Söz konusu k değeri belirlendikten sonra her bir kümeye gözlem değerleri atanır ve böylece {C1,C2,….,Ck} kümeleri belirlenmiş olur.Ardından aşağıdaki işlemler gerçekleştirilir:

a) Her bir kümenin merkezi belirlenir.Bu merkezler M1,M2,..,Mk biçimindedir.

b) e1, e2,…,ek küme içi değişmeler hesaplanır.Bu değişmelerin toplamı olan Ek2 değeri bulunur.

c) Mk merkez değerleri ile gözlem değerleri arasındaki uzaklıklar hesaplanır.Bu gözlem değeri hangi merkeze yakın ise, o merkez ile ilgili küme içine dahil edilir.

d) Yukarıdaki b ve c adımları, kümelerde herhangi bir değişiklik olmayıncaya dek sürdürülür.

ÖRNEK:Aşağıdaki gözlem değerlerini göz önüne alalım.Bu gözlem değerlerine k-ortalamalar yöntemini uygulayarak kümelemek istiyoruz.

Kümelerin sayısına başlangıçta k=2 biçiminde karar veriyoruz.Başlangıçta tesadüfi olarak aşağıdaki iki kümeyi belirliyoruz.

C1={X1,X2,X4}

C2={X3,X5}

Bu kümeleri de içeren gözlem değerlerini aşağıdaki tablo üzerinde topluca gösteriyoruz.

ADIM 1:

a) İki kümenin merkezleri şu şekilde hesaplanır:

b) Küme içi değişmeler şu şekilde hesaplanır:

Toplam kare hata aşağıdaki gibi hesaplanır:

c) Gözlemlerin M1 ve M2 merkezlerinden olan uzaklıkların minimum olması istendiğinden aşağıdaki hesaplamalar yapılır: Öklid formülü kullanılarak söz konusu mesafeler hesaplanır. Örneğin (M1,X1)noktaları arasındaki uzaklık M1={6.67,4.00} ve X1={4,2} olduğuna göre şu şekilde hesaplanır: