Kümeleme Algoritmasını Çalıştır

Makine öğreniminde bazen milyonlarca örnek içerebilen veri kümeleriyle karşılaşırsınız. ML algoritmaları bu büyük veri kümelerine verimli bir şekilde ölçeklenmelidir. Ancak birçok küme algoritması, her nokta noktası arasındaki benzerliği hesaplamaları gerektiğinden ölçeklenmez. Bu, çalışma alanlarının puan sayısı noktasının karesi olarak \(O(n^2)\)olacağı anlamına gelir. Örneğin, bütünsel veya diferansiyel hiyerarşik kümeleme algoritmaları tüm nokta çiftlerini inceler ve sırasıyla \(O(n^2 log(n))\) ve \(O(n^2)\)karmaşıklık düzeyine sahiptir.

Bu kurs, \(O(nk)\)ölçeğiyle ölçeklendirildiği için k ortalamasına odaklanmaktadır. \(k\) Kümelerin sayısı<k class="ph-2-1"> kümelerin sayısını belirler. k-ortalaması, noktaların arasındaki küme sayısını en aza indirerek \(k\) kümelerde gruplandırır (aşağıda Şekil 1'de görüldüğü gibi). Bir kümenin merkez merkezi, kümedeki tüm noktaların ortalamasıdır.

Gösterildiği gibi, k ortalamaları dairesel olarak kabarık kümeleri bulur. Kavramsal olarak bu, k ortalamanın yaklaşık olarak bir dizi dairesel dağıtımdan oluşan veriler olarak etkin şekilde ele alındığı ve bu dağıtımlara karşılık gelen kümeleri bulmaya çalıştığı anlamına gelir. Gerçekte ise veriler aykırı değerler içerir ve bu tür bir modele uygun olmayabilir.

K-ortalamasını çalıştırmadan önce küme sayısını ( \(k\)) seçmeniz gerekir. İlk olarak \(k\)için bir tahminle başlayın. Daha sonra bu sayının nasıl hassaslaştırılacağını ele alacağız.

k-ortalama Kümeleme Algoritması

k-Ortalamaları, verileri \(k\) kümelerde kümelemek için aşağıdaki adımları uygular:

Şekil 1: İlk kullanıma hazırlama ile k anlamına gelir.

Birinci Adım

Algoritma rastgele bir şekilde her bir küme için bir merkezi değer seçer. Örneğimizde, 3/ \(k\) seçiyoruz. Bu nedenle algoritma rastgele bir şekilde 3 merkez yeri seçiyor.

Şekil 2: Başlangıç kümeleri.

İkinci Adım

Algoritma, başlangıç kümelerini almak için her noktayı \(k\) en yakın merkeze atar.

Şekil 3: Steridlerin hesaplanması.

Üçüncü Adım

Algoritma, her küme için kümedeki tüm noktaların ortalamasını alarak merkezi konumu yeniden hesaplar. Cidroidlerdeki değişiklikler, Şekil 3'te oklarla gösterilir. Cidroidler değişeceğinden algoritma, noktaları en yakın merkeze yeniden atar. 4. şekilde yeni atamanın ardından yeni kümeler gösterilir.

Şekil 4: Yeniden atamanın ardından küme sayısı.

Dördüncü Adım

Algoritma, noktaların küme değiştirme işlemi durdurulana kadar, merkezi nokta hesaplamasını ve noktaların atanmasını tekrarlar. Büyük veri kümelerini gruplandırırken başka ölçütleri kullanarak birleştirmeye ulaşmadan önce algoritmayı durdurursunuz.

Bu kurs için k ortalamasını anlamanız gerekmez. Ancak merak ediyorsanız matematiksel kanıtı aşağıda görebilirsiniz.

Matematiksel kanıt için artı simgesini tıklayın

\(k\) Kümelere \(n\) atanmış örnekler göz önüne alındığında, örneklerin merkez merkezlerine olan mesafelerinin toplamını en aza indirin. Burada:

• \(A_{nk} = 1\) Bir \(n\). örnek \(k\). kümeye atandığında ve 0 değerine ayarlanırsa 0
• \(\theta_k\) kümenin merkez noktası \(k\)

Aşağıdaki ifadeyi en aza indirmek istiyoruz: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ şuna tabidir: $$A_{nk} \in \{0,1\} \forall n,k$$ ve $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Küme merkezi odalarına göre ifadeyi en aza indirmek için \(\theta_k\) türevi \(\theta_k\) alın ve 0'a eşittir. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Pay, kümedeki tüm örnek merkez mesafelerinin toplamıdır. Payda, kümedeki örneklerin sayısıdır. Bu nedenle küme merkez\(\theta_k\) kümedeki örnek merkez noktasının ortalamasıdır. Bu da kanıtladı.

Cenroid konumları başlangıçta rastgele seçildiğinden k ortalamaları, arka arkaya yapılan çalıştırmalarda önemli ölçüde farklı sonuçlar döndürebilir. Bu sorunu çözmek için k-ortalamasını birden fazla kez çalıştırın ve en iyi kalite metriklerine sahip sonucu seçin. (Bu kursun ilerleyen bölümlerinde kalite metriklerini açıklayacağız.) Daha iyi başlangıç merkez konumları seçmek için k ortalamalarının gelişmiş bir sürümüne sahip olmanız gerekir.

Deneme: Stanford'daki bu k-ortalaması simülatörünü kullanarak k-ortalamalarını birden fazla kez çalıştırmayı deneyin ve farklı sonuçlar alıp almayacağınıza bakın.

Temel Terimler:

• merkezli