Denetimsiz öğrenim adından da anlayacağınız üzere denetim olmayan bir türdür. Denetimsiz öğrenim denetimli öğretime kıyasla daha karmaşık işleri gerçekleştirebiliriz. Sebebi ise makinenin sistemi değil veriden öğrenmesidir.
Kümeleme (clustering)
Kümeleme, verilerde, küme olarak isimlendirilen benzerlik gruplarını bulmaya yarayan tekniktir.
Kümeleme, benzer verileri aynı farklı verileri ayrık kümelere ayırma görevi üstlenir.
Verilerin hangi gruplara atanacağına dair bir ön bilgi olmadığı için kümeleme bir denetimsiz (unsupervised) teknik olarak isimlendirilir.
Tarihsel nedenlerle kümeleme denetimsiz öğrenimle aynı anlama gelir.
Bununla birlikte, denetimsiz öğrenim kümeleme haricinde birliktelik kuralları madenciliğini de kapsar.
Kümeleme ne için yapılır?
Gerçek hayattan iki örnek:
Örnek 1: benzer boyutlara sahip T-shirtler «küçük», «orta» ve «büyük» şeklinde kümelere ayrılır.
Her bedene uygun tasarım çok pahalı olacağı için yapılır.
Herkesi tek bedene uydurmak mümkün değildir.
Örnek 2: Pazarlamada müşteriler benzer özelliklerine göre bölümlere ayrılır.
Hedefli reklamcılık için buna ihtiyaç vardır.
Örnek 3: verilen bir dizi metni içeriklerine göre gruplamak için,
Böylece bir konu hiyerarşisi oluşturulabilir
Kümeleme, veri madenciliğinde en sık kullanılan tekniklerden biridir.
Uzun bir geçmişi vardır ve tıp, psikoloji, botanik, sosyoloji, biyoloji, arkeoloji, pazarlama, sigorta, kütüphaneler gibi hemen hemen her alanda kullanılmaktadır.
Son yıllarda çevrimiçi dokümanların artması nedeniyle metin kümeleme (text clustering) daha önemli hale gelmiştir.
Kümelemenin Türleri
Bir kümeleme algoritması
Bölümlemeli (Partitional) kümeleme
Hiyerarşik (Hierarchical) kümeleme olarak iki türden birinde olabilir.
Bir uzaklık (benzerlik veya benzemezlik) fonksiyonu
Kümeleme kalitesi
Kümeler arası uzaklık Þ maximized
Küme için uzaklık Þ minimized
Bir kümeleme sonucunun kalitesi, algoritmaya, mesafe fonksiyonuna ve uygulamaya bağlıdır.
K-means kümeleme
K-means bölümlemeli bir kümeleme algoritmasıdır
Veri noktaları veya örnekler kümesi D olmak üzere
{x1, x2, …, xn},
burada xi = (xi1, xi2, …, xir) X U Rr uzayında, r adet özelliği olan reel değerli bir vektördür. R değeri vektörün boyutunu verir.
K-means algoritması sunulan veriyi K kümeye ayırır
Her kümenin adı centroid olan bir küme merkezi bulunur.
k değeri kullanıcı tarafından ayarlanır
K-means algoritması
K-means algoritması aşağıdaki şekilde çalışır:
1) Random olarak k veri noktası (çekirdek) başlangıç centroid değeri olarak seçilir, centroid değerleri küme merkezlerini sunar
2) Her veri noktası kendisine en yakın centroid değerine göre bir kümeye atanır
3) Bütün verilerin kümelelere atanması bittikten sonra kümelerin kendisine ait elemanlar yardımıyla yeni centroid değerleri elde edilir.
4) kümeler stabil hale gelene kadar (kümeden kümeye geçen eleman kalmayana kadar) 2. adıma dön ve işlemleri yinele
A disk version of k-means
K-means disk üzerindeki veriler ile uygulanabilir
Her bir iterasyonda veri bir kez taranır.
Centroidler artırımlı olarak hesaplanabilir
Ana belleğe sığmayan büyük veri kümelerini kümelemek için kullanılabilir
Yineleme sayısı kontrol edilmelidir
Pratikte, limitli bir küme (< 50).
En iyi yöntem değildir, BIRCH gibi daha ölçeklenebilir yöntemler vardır.
K-means algoritmasının güçlü yönleri
Güçlü yönler:
Sade: geliştirmek için anlaşılması kolaydır
Verimli: zaman karmaşıklığı: O(tkn),
burada; n veri noktalarının adedi,
k kümelerin adedi ve
t iterasyonların adedidir
Hem k hem de t küçük olduğu için. K-means doğrusal bir algoritma olarak kabul edilir.
K-means en popüler kümeleme algoritmasıdır.
Unutmayın: SSE kullanılırsa yerel bir optimumda sona erer. Karmaşıklık nedeniyle küresel optimumun bulunması zor.
K-means zayıf yönleri
Algoritma, yalnızca ortalamanın alınabileceği veri türleri için uygundur.
Kategorik veriler için k-mode yöntemi kullanılır, centroid olarak en sık tekrar eden değerler kullanılır.
K değerini belirlemeye ihtiyaç duyar.
Algoritma taşmalara karşı duyarlıdır
Aykırı değerler, diğer veri noktalarından çok uzak olan veri noktalarıdır.
Aykırı değerler, veri kaydındaki hatalar veya çok farklı değerlere sahip bazı özel veri noktaları olabilir.
K-means özeti
Zayıflıklara rağmen, k-means basitliği, verimliliği ve kullanımı nedeniyle hala en popüler algoritmadır.
Diğer kümeleme algoritmalarının kendilerine özgü zayıflıkları vardır.
Diğer kümeleme algoritmalarının genel olarak daha iyi performans gösterdiğine dair net bir kanıt yok
bazı özel veri türleri veya uygulamalar için daha uygun olsalar da.
Farklı kümeleme algoritmalarını karşılaştırmak zor bir iştir. Doğru kümeleri kimse bilmiyor!
Kümeleri sunmak için farklı yollar
Kümeyi temsil etmek için her kümenin ağırlık merkezini kullanın.
Yarıçapı ve her boyuttaki yayılmasını belirleme için standart sapmasını hesaplayın
Ağırlık merkezi gösterimi, kümeler hiper-küresel şekildeyse tek başına iyi çalışır.
Kümeler uzamışsa veya başka şekillerde ise ağırlık merkezi yeterli değildir.
Sınıflandırma modeli kullanımı
Bir kümedeki bütün veri noktaları sınıf etiketi ile uyumlu kümede yer alır.
Bir sınıflandırma modeli bulmak için veriler üzerinde denetimli bir öğrenme algoritması çalıştırın.
Kümeyi temsil etmek için sık (frequent) değerler kullanın
Bu yöntem esas olarak kategorik verilerin kümelenmesi içindir (örneğin, k-mode kümeleme).
Kümeyi temsil etmek için her kümedeki küçük bir sık sözcük kümesinin seçildiği metin kümelemede kullanılan ana yöntem.
Keyfi şekillerin kümeleri
Hiper eliptik ve hiper küresel kümelerin, ağırlık merkezlerini yaymalarla birlikte kullanarak temsil etmesi genellikle kolaydır.
Düzensiz şekilli kümelerin temsil edilmesi zordur.
Bazı uygulamalarda kullanışlı olmayabilirler.
Ağırlık merkezlerinin kullanılması genel olarak uygun değildir (üstteki şekil)
K-means kümeler, örneğin 2 boyutlu T-shirtler yapmak için daha kullanışlı olabilir (alt şekil).
Hiyerarşik kümeleme
Dendrogram olarak da adlandırılan bir ağaç yardımıyla iç içe geçmiş bir dizi küme üretilir.
Hiyerarşik kümeleme türleri
Aglomeratif (aşağıdan yukarıya) kümeleme : En alt seviyede her bir nokta için bir dendrogramı (ağaç) oluşturur ve tüm veri noktaları tek bir kümede (yani kök küme) birleştirilene kadar devam eder.
Divisive (yukarıdan aşağıya) kümeleme: bütün veri noktalarının tek bir kümede yer almasıyla başlar ve adım adım alt kümeler oluşturularak bireysel noktalara kadar bölünür.
Aglomeratif (birleştirmeli) kümeleme
Ayrılıkçı (divisive) yöntemlerden daha popülerdir.
Başlangıçta her bir veri noktası bir küme formundadır (düğüm olarak da isimlendirilir).
Düğüm/küme birleştirmeleri en yakın mesafeye göre yapılır.
Birleştirme devam eder
Bütün düğümler tek bir kümeye ait olana kadar işlem devam eder
İki kümenin mesafesinin ölçümü
İki kümenin mesafe ölçümü için birkaç yöntem vardır.
Algoritmanın farklı varyasyonlarıyla sonuçlanır.
Single link
Complete link
Average link
Centroids
…
Single link yöntemi
İki küme arasındaki mesafe, iki kümedeki en yakın iki veri noktası arasındaki mesafedir, her kümeden bir veri noktası.
Keyfi şekilli kümeler bulabilir, ancak gürültülü noktalardan istenmeyen “zincir etkisine” neden olabilir.
Complete link yöntemi
İki küme arasındaki mesafe, iki kümedeki en uzaktaki iki veri noktasının mesafesidir.
Aykırı değerler uzakta olduğu için aykırı değerlere karşı hassastır.
Average link ve centroid yöntemleri
Average link:
tam bağlantılı kümelemenin aykırı değerlere duyarlılığı ve tek bağlantılı kümelemenin, kompakt, küresel nesneler olarak sezgisel küme kavramına karşılık gelmeyen uzun zincirler oluşturma eğilimi arasında bir uzlaşma sağlar
Bu yöntemde, iki küme arasındaki mesafe, iki kümedeki veri noktaları arasındaki tüm çiftler arası mesafelerin ortalama mesafesidir.
Centroid method: Bu yöntemde, iki küme arasındaki mesafe, ağırlık merkezleri arasındaki mesafedir.
Karmaşıklık
N, veri noktalarının sayısı olmak üzere algoritmaların karmaşıklığı en az O(n2) mertebesindedir.
Single link O(n2) zamanında yerine getirilir.
Complete ve average link O(n2logn) zamanında yerine getirilir.
Karmaşıklık nedeniyle büyük boyutlu veri setlerinde;