Paylaşım , Takip İçin
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;
- Örnekleme veya
- BIRCH gibi ölçeklenebilir yöntemler kullanılır.
Bir öneki makine öğrenimi dersi için tıklayınız — Olasılık ve Bayes
Paylaşım , Takip İçin