Kümeleme Algoritmaları: Baştan Son Teknolojiye

Veri Bilimcisi olmak için kötü bir zaman değil. Sohbeti “Büyük Veri”ye çevirirseniz ciddi insanlar ilginizi çekebilir ve “Yapay Zeka” ve “Makine Öğrenimi”nden bahsettiğinizde parti kalabalığının geri kalanının ilgisini çekecektir. Google bile senin kötü olmadığını ve daha da iyiye gittiğini düşünüyor. Veri bilimcilerinin sihirbazlıklarını yapmalarına yardımcı olan birçok 'akıllı' algoritma vardır. Her şey karmaşık görünebilir, ancak algoritmaları biraz anlar ve düzenlersek, ihtiyacımız olanı bulmak ve uygulamak o kadar da zor değildir.

Veri madenciliği veya makine öğrenimi ile ilgili kurslar, hem basit hem de kullanışlı olduğu için genellikle kümeleme ile başlar. Tanımlamak istediğimiz verilerin etiketlenmediği, biraz daha geniş Denetimsiz Öğrenme alanının önemli bir parçasıdır. Çoğu durumda bu, kullanıcının bize beklenen çıktının ne olduğu konusunda fazla bilgi vermediği yerdir. Algoritma yalnızca verilere sahiptir ve elinden gelenin en iyisini yapmalıdır. Bizim durumumuzda, kümeleme - verileri benzer veri noktalarını içeren gruplara (kümelere) ayırırken, gruplar arasındaki farklılık mümkün olduğunca yüksek olmalıdır. Veri noktaları, müşterilerimiz gibi her şeyi temsil edebilir. Örneğin, benzer kullanıcıları gruplamak ve ardından her kümede farklı pazarlama kampanyaları yürütmek istiyorsak, kümeleme yararlı olabilir.

K-Ortalamalar Kümeleme

Gerekli tanıtımdan sonra Veri Madenciliği kursları her zaman K-Means ile devam eder; etkili, yaygın olarak kullanılan, çok yönlü bir kümeleme algoritması. Gerçekte çalıştırmadan önce, veri noktaları arasında bir mesafe fonksiyonu tanımlamalıyız (örneğin, uzayda noktaları kümelemek istiyorsak Öklid mesafesi) ve istediğimiz küme sayısını (k) ayarlamalıyız.

Algoritma, başlangıç ​​merkezleri (kümelerin 'merkezleri') olarak k nokta seçilerek başlar. Herhangi bir rastgele k nokta seçebiliriz veya başka bir yaklaşım kullanabiliriz, ancak rastgele noktaları seçmek iyi bir başlangıçtır. Ardından, iki adımı yinelemeli olarak tekrarlıyoruz:

1. Atama adımı: Veri kümemizdeki m noktanın her biri, en yakın k ağırlık merkezi tarafından temsil edilen bir kümeye atanır. Her nokta için, her bir merkeze olan mesafeleri hesaplıyoruz ve basitçe en uzak olanı seçiyoruz.

2. Güncelleme adımı: Her küme için kümedeki tüm noktaların ortalaması olarak yeni bir merkez noktası hesaplanır. Önceki adımdan, bir kümeye atanmış bir dizi noktamız var. Şimdi, bu tür her küme için, kümenin yeni bir ağırlık merkezini bildirdiğimizin bir ortalamasını hesaplıyoruz.

Her yinelemeden sonra, merkezler yavaşça hareket eder ve her noktadan atanan merkeze olan toplam mesafe giderek azalır. İki adım, yakınsama kadar, yani küme atamasında daha fazla değişiklik kalmayana kadar değiştirilir. Bir dizi yinelemeden sonra, her bir merkeze aynı puan kümesi atanacak ve bu nedenle tekrar aynı merkezlere yol açacaktır. K-Means'in yerel bir optimuma yakınsaması garanti edilir. Ancak, bunun mutlaka en iyi genel çözüm (küresel optimum) olması gerekmez.

Nihai kümeleme sonucu, ilk ağırlık merkezlerinin seçimine bağlı olabilir, bu nedenle bu problem üzerinde çokça düşünülmüştür. Basit bir çözüm, K-Means'i rastgele başlangıç ​​atamalarıyla birkaç kez çalıştırmaktır. Daha sonra, her noktadan kümesine olan mesafelerin minimum toplamı olan birini alarak en iyi sonucu seçebiliriz - ilk etapta en aza indirmeye çalıştığımız hata değeri.

Başlangıç ​​noktalarının seçilmesine yönelik diğer yaklaşımlar, uzak noktaların seçilmesine dayanabilir. Bu daha iyi sonuçlara yol açabilir, ancak aykırı değerlerle ilgili bir sorunumuz olabilir, yalnızca "kapalı" olan ve yalnızca bazı hatalar olabilen bu nadir tek başına noktalar. Herhangi bir anlamlı kümeden uzak oldukları için, bu tür her nokta kendi 'kümesi' haline gelebilir. İyi bir denge K-Means++ varyantıdır [Arthur ve Vassilvitskii, 2007], başlatma işlemi yine de rastgele noktalar seçecektir, ancak olasılıkla önceden atanan merkezlerden uzaklığın karesiyle orantılıdır. Daha uzaktaki noktaların başlangıç ​​ağırlık merkezi olarak seçilme olasılığı daha yüksektir. Sonuç olarak, bir nokta grubu varsa, olasılıkları arttıkça gruptan bir noktanın seçilme olasılığı da artar ve bahsettiğimiz aykırı değer sorununu çözer.

K-Means++ ayrıca Python'un Scikit-learn K-Means uygulaması için varsayılan başlatmadır. Python kullanıyorsanız, tercih ettiğiniz kitaplık bu olabilir. Java için Weka kütüphanesi iyi bir başlangıç ​​olabilir:

Java (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-öğren)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

Yukarıdaki Python örneğinde, üç farklı iris türü için çiçek yaprağı ve çanak yaprağı boyutlarını içeren standart bir örnek veri kümesi 'İris' kullandık. Bunları üç kümeye ayırdık ve mükemmel bir şekilde eşleştiklerini görmek için elde edilen kümeleri gerçek türlerle (hedef) karşılaştırdık.

Bu durumda, üç farklı küme (tür) olduğunu biliyorduk ve K-Ortalamalar hangilerinin bir arada olduğunu doğru bir şekilde tanıdı. Ancak, genel olarak iyi sayıda k kümesini nasıl seçeriz? Bu tür sorular Makine Öğreniminde oldukça yaygındır. Daha fazla küme talep edersek, bunlar daha küçük olacak ve bu nedenle toplam hata (noktalardan atanan kümelere olan toplam mesafeler) daha küçük olacaktır. Yani, sadece daha büyük bir k ayarlamak iyi bir fikir mi? k = m ile bitirebiliriz, yani her nokta kendi ağırlık merkezidir ve her kümenin sadece bir noktası vardır. Evet, toplam hata 0'dır, ancak verilerimizin daha basit bir tanımını alamadık ve ortaya çıkabilecek bazı yeni noktaları kapsayacak kadar genel değil. Buna aşırı takma denir ve biz bunu istemiyoruz.

Bu sorunla başa çıkmanın bir yolu, daha fazla sayıda küme için bir miktar ceza eklemektir. Yani, şimdi sadece hatayı değil, aynı zamanda hata + cezayı da en aza indirmeye çalışıyoruz. Küme sayısını artırdıkça hata sadece sıfıra yakınsar, ancak ceza artacaktır. Bazı noktalarda, başka bir küme eklemekten elde edilen kazanç, uygulanan cezadan daha az olacak ve en uygun sonucu alacağız. Bu amaçla Bayesian Information Criterion (BIC) kullanan bir çözüme X-Means denir [Pelleg ve Moore, 2000].

Düzgün tanımlamamız gereken bir diğer şey de uzaklık fonksiyonudur. Bazen bu basit bir görevdir, verilerin doğası göz önüne alındığında mantıklı bir görevdir. Uzaydaki noktalar için Öklid mesafesi bariz bir çözümdür, ancak farklı 'birimlerin' özellikleri, ayrık değişkenler vb. için zor olabilir. Bu, çok fazla alan bilgisi gerektirebilir. Veya yardım için Machine Learning'i arayabiliriz. Aslında mesafe fonksiyonunu öğrenmeye çalışabiliriz. Nasıl gruplanması gerektiğini bildiğimiz bir eğitim noktamız varsa (yani kümeleriyle etiketlenmiş noktalar), iyi bir işlev bulmak için denetimli öğrenme tekniklerini kullanabilir ve ardından henüz kümelenmemiş hedef kümemize uygulayabiliriz. .

K-Ortalamalarda kullanılan yöntem, birbirini izleyen iki adımıyla Beklenti-Maksimizasyon (EM) yöntemine benzer. Aslında EM'nin çok basit bir versiyonu sayılabilir. Bununla birlikte, aynı prensiplerden bazılarını paylaşmasına rağmen, daha ayrıntılı EM kümeleme algoritması ile karıştırılmamalıdır.

EM Kümeleme

Böylece, K-Ortalamalar kümeleme ile her nokta yalnızca tek bir kümeye atanır ve bir küme yalnızca kendi ağırlık merkezi tarafından tanımlanır. Üst üste binen veya dairesel olmayan kümelerle ilgili sorunlarımız olabileceğinden, bu çok esnek değildir. EM Kümeleme ile artık bir adım daha ileri gidebilir ve her kümeyi kendi ağırlık merkezi (ortalama), kovaryans (böylece eliptik kümelere sahip olabiliriz) ve ağırlık (kümenin boyutu) ile tanımlayabiliriz. Bir noktanın bir kümeye ait olma olasılığı artık çok değişkenli bir Gauss olasılık dağılımı ile verilmektedir (çok değişkenli - birden çok değişkene bağlı olarak). Bu aynı zamanda bir noktanın Gauss 'çanı' altında olma olasılığını, yani bir noktanın bir kümeye ait olma olasılığını hesaplayabileceğimiz anlamına gelir.

Şimdi, her nokta için, mevcut kümelerin her birine ait olma olasılıklarını hesaplayarak EM prosedürüne başlıyoruz (ki bunlar da başlangıçta rastgele oluşturulabilir). Bu, E-adımıdır. Bir küme bir nokta için gerçekten iyi bir adaysa, bire yakın bir olasılığa sahip olacaktır. Bununla birlikte, iki veya daha fazla küme kabul edilebilir adaylar olabilir, bu nedenle nokta, kümeler üzerinde bir olasılık dağılımına sahiptir. Algoritmanın tek bir kümeye ait olmayan noktaların bu özelliğine “yumuşak kümeleme” denir.

M adımı şimdi, önceki küme kümesine noktaların atamalarını kullanarak her kümenin parametrelerini yeniden hesaplar. Bir kümenin yeni ortalamasını, kovaryansını ve ağırlığını hesaplamak için, her nokta verisi, önceki adımda hesaplandığı gibi, kümeye ait olma olasılığına göre ağırlıklandırılır.

Bu iki adımı değiştirmek, yakınsayana kadar toplam log olasılığını artıracaktır. Yine maksimum yerel olabilir, bu nedenle daha iyi kümeler elde etmek için algoritmayı birkaç kez çalıştırabiliriz.

Şimdi her nokta için tek bir küme belirlemek istiyorsak, basitçe en olası olanı seçebiliriz. Bir olasılık modeline sahip olarak, onu benzer veriler oluşturmak, yani gözlemlediğimiz verilere benzer daha fazla nokta örneklemek için de kullanabiliriz.

Yakınlık Yayılımı

Affinity Propagation (AP), Frey ve Dueck tarafından 2007'de yayınlandı ve basitliği, genel uygulanabilirliği ve performansı nedeniyle giderek daha popüler hale geliyor. Durumunu son teknolojiden fiili standarda değiştiriyor.

K-Means ve benzer algoritmaların ana dezavantajları, küme sayısını ve ilk nokta kümesini seçmek zorunda olmalarıdır. Yakınlık Yayılımı bunun yerine, veri noktası çiftleri arasındaki benzerliğin girdi ölçülerini alır ve aynı anda tüm veri noktalarını potansiyel örnekler olarak kabul eder. Gerçek değerli mesajlar, yüksek kaliteli bir dizi örnek ve karşılık gelen kümeler kademeli olarak ortaya çıkana kadar veri noktaları arasında değiş tokuş edilir.

Bir girdi olarak, algoritma iki veri seti sağlamamızı gerektirir:

1. Bir noktanın başka birinin örneği olmaya ne kadar uygun olduğunu gösteren veri noktaları arasındaki benzerlikler. Aynı kümeye ait olamayacakları gibi iki nokta arasında benzerlik yoksa, uygulamaya bağlı olarak bu benzerlik atlanabilir veya -Infinity olarak ayarlanabilir.

2. Her bir veri noktasının örnek olmaya uygunluğunu temsil eden tercihler. Bu rol için hangi noktaların tercih edilebileceğine dair bazı ön bilgilere sahip olabiliriz ve böylece onu tercihler yoluyla temsil edebiliriz.

Hem benzerlikler hem de tercihler genellikle tek bir matris aracılığıyla temsil edilir, burada ana köşegendeki değerler tercihleri ​​temsil eder. Matris gösterimi, yoğun veri kümeleri için iyidir. Noktalar arasındaki bağlantıların seyrek olduğu durumlarda, nxn matrisinin tamamını bellekte saklamamak, bunun yerine bağlantılı noktalara benzerliklerin bir listesini tutmak daha pratiktir. Sahnenin arkasında, 'noktalar arasında mesaj alışverişi' matrisleri manipüle etmekle aynı şeydir ve bu sadece bir bakış açısı ve uygulama meselesidir.

Algoritma daha sonra yakınsayana kadar bir dizi yinelemeden geçer. Her yinelemenin iki mesaj iletme adımı vardır:

1. Sorumlulukların hesaplanması: Sorumluluk r(i, k), i noktası için diğer potansiyel örnekleri hesaba katarak, k noktasının i noktası için örnek teşkil etmesi için ne kadar uygun olduğuna dair birikmiş kanıtları yansıtır. Sorumluluk, i veri noktasından k aday örnek noktasına gönderilir.

2. Kullanılabilirliklerin hesaplanması: Kullanılabilirlik a(i, k), k noktasının örnek olması gereken diğer noktalardan gelen desteği dikkate alarak, i noktasının k noktasını örnek olarak seçmesinin ne kadar uygun olacağına dair birikmiş kanıtları yansıtır. Kullanılabilirlik, aday örnek noktası k'den i noktasına gönderilir.

Algoritma, sorumlulukları hesaplamak için önceki yinelemede hesaplanan orijinal benzerlikleri ve kullanılabilirlikleri kullanır (başlangıçta tüm kullanılabilirlikler sıfıra ayarlanır). Sorumluluklar, örnek olarak i noktası ve k noktası arasındaki girdi benzerliğine, eksi i noktası ve diğer aday örnekler arasındaki benzerlik ve kullanılabilirlik toplamının en büyüğüne ayarlanır. Bir noktanın bir örnek için ne kadar uygun olduğunu hesaplamanın arkasındaki mantık, ilk a priori tercih daha yüksekse daha fazla tercih edilmesidir, ancak kendisini iyi bir aday olarak gören benzer bir nokta olduğunda sorumluluk azalır, bu nedenle ' rekabet 'biri bazı yinelemelerde karar verilene kadar.

O halde, müsaitliklerin hesaplanması, hesaplanan sorumlulukları, her adayın iyi bir örnek oluşturup oluşturmayacağının kanıtı olarak kullanır. Kullanılabilirlik a(i, k), öz sorumluluk r(k, k) artı aday k örneğinin diğer noktalardan aldığı pozitif sorumlulukların toplamına ayarlanır.

Son olarak, değerlerdeki değişiklikler bir eşiğin altına düştüğünde veya maksimum yineleme sayısına ulaşıldığında olduğu gibi, prosedürü sonlandırmak için farklı durdurma kriterlerine sahip olabiliriz. Yakınlık Yayılımı prosedürü boyunca herhangi bir noktada, Sorumluluk (r) ve Kullanılabilirlik (a) matrislerini toplamak bize ihtiyacımız olan kümeleme bilgisini verir: i noktası için, maksimum r(i, k) + a(i, k) olan k, noktayı temsil eder. ben örnek. Veya sadece örnek kümesine ihtiyacımız varsa, ana köşegeni tarayabiliriz. r(i, i) + a(i, i) > 0 ise, i noktası bir örnektir.

K-Means ve benzer algoritmalarla küme sayısına karar vermenin zor olabileceğini gördük. AP ile, bunu açıkça belirtmek zorunda değiliz, ancak optimal bulabileceğimizden daha fazla veya daha az küme elde edersek yine de biraz ayarlamaya ihtiyacı olabilir. Neyse ki, sadece tercihleri ​​ayarlayarak küme sayısını azaltabilir veya artırabiliriz. Tercihleri ​​daha yüksek bir değere ayarlamak daha fazla kümeye yol açacaktır, çünkü her nokta bir örnek olmaya uygunluğundan 'daha kesin'dir ve bu nedenle 'yenilmesi' ve başka bir noktanın 'hakimiyeti' altına dahil edilmesi daha zordur. Tersine, daha düşük tercihler ayarlamak daha az kümeye sahip olmanıza neden olur; sanki "hayır hayır lütfen sen daha iyi bir örneksin, ben senin kümene katılacağım" der gibi. Genel bir kural olarak, tüm tercihleri ​​orta ila çok sayıda küme için ortanca benzerliğe veya orta sayıda küme için en düşük benzerliğe ayarlayabiliriz. Ancak, ihtiyaçlarımıza tam olarak uyan sonucu elde etmek için ayar tercihleri ​​ile birkaç çalışma gerekebilir.

Hiyerarşik Yakınlık Yayılımı, veri kümesini birkaç alt kümeye bölerek, bunları ayrı ayrı kümeleyerek ve ardından ikinci kümeleme düzeyini gerçekleştirerek ikinci dereceden karmaşıklıkla ilgilenen algoritmanın bir varyantı olarak da bahsetmeye değer.

Sonunda…

Her birinin sahip oldukları veri türü, zaman karmaşıklığı, zayıf yönleri vb. ile ilgili artıları ve eksileri olan çok çeşitli kümeleme algoritmaları vardır. Daha fazla algoritmadan bahsetmek gerekirse, örneğin Hiyerarşik Aglomeratif Kümeleme (veya Bağlantı Kümelemesi) vardır, dairesel (veya hiper-küresel) kümelere sahip olmadığımız ve küme sayısını önceden bilmediğimiz durumlar için iyidir. Her noktanın ayrı bir küme olmasıyla başlar ve her şey tek bir büyük kümede olana kadar her adımda en yakın iki kümeyi birleştirerek çalışır.

Hiyerarşik Aglomeratif Kümeleme ile dendrogramı (ağaç diyagramı) uygun bulduğumuz yerde yatay olarak keserek daha sonra kolayca küme sayısına karar verebiliriz. Aynı zamanda tekrarlanabilirdir (aynı veri kümesi için her zaman aynı yanıtı verir), ancak aynı zamanda daha karmaşıktır (ikinci dereceden).

O halde DBSCAN (Yoğunluk Tabanlı Mekansal Kümelenme ile Uygulamaların Gürültüsü) de bahsetmeye değer bir algoritmadır. Birbirine çok yakın olan noktaları gruplandırır, kümeleri yakındaki noktaların olduğu herhangi bir yöne doğru genişletir, böylece farklı küme şekilleri ile ilgilenir.

Bu algoritmalar kendilerine ait bir makaleyi hak ediyor ve onları daha sonra ayrı bir gönderide keşfedebiliriz.

Bir algoritmanın veya diğerinin ne zaman kullanılacağını bilmek biraz deneme yanılma deneyimi gerektirir. Neyse ki, farklı programlama dillerinde bir dizi uygulamamız var, bu yüzden onları denemek sadece biraz oynamak için istekli olmayı gerektiriyor.