Algoritme Pengelompokan - Algoritme Pergeseran Rata-rata

Pengantar Algoritma Mean-Shift

Seperti yang dibahas sebelumnya, ini adalah algoritma pengelompokan hebat lainnya yang digunakan dalam pembelajaran tanpa pengawasan. Tidak seperti pengelompokan K-means, ia tidak membuat asumsi apa pun; karenanya ini adalah algoritma non-parametrik.

Algoritma mean-shift pada dasarnya menetapkan titik data ke cluster secara iteratif dengan menggeser titik ke arah kepadatan titik data tertinggi yaitu cluster centroid.

Perbedaan antara algoritma K-Means dan Mean-Shift adalah nantinya seseorang tidak perlu menentukan jumlah cluster terlebih dahulu karena jumlah cluster akan ditentukan oleh data algoritma wrt.

Cara Kerja Algoritma Mean-Shift

Kita dapat memahami cara kerja algoritma pengelompokan Mean-Shift dengan bantuan langkah-langkah berikut -

Step 1 - Pertama, mulailah dengan titik data yang ditetapkan ke klusternya sendiri.
Step 2 - Selanjutnya, algoritma ini akan menghitung sentroid.
Step 3 - Pada langkah ini, lokasi sentroid baru akan diperbarui.
Step 4 - Sekarang, proses akan diulangi dan dipindahkan ke wilayah dengan kepadatan yang lebih tinggi.
Step 5 - Akhirnya, itu akan dihentikan setelah sentroid mencapai posisi di mana ia tidak dapat bergerak lebih jauh.

Implementasi dengan Python

Ini adalah contoh sederhana untuk memahami cara kerja algoritma Mean-Shift. Dalam contoh ini, pertama-tama kita akan menghasilkan dataset 2D yang berisi 4 blob berbeda dan setelah itu akan menerapkan algoritma Mean-Shift untuk melihat hasilnya.

%matplotlib inline
import numpy as np
from sklearn.cluster import MeanShift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets.samples_generator import make_blobs
centers = [[3,3,3],[4,5,5],[3,10,10]]
X, _ = make_blobs(n_samples = 700, centers = centers, cluster_std = 0.5)
plt.scatter(X[:,0],X[:,1])
plt.show()

ms = MeanShift()
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_
print(cluster_centers)
n_clusters_ = len(np.unique(labels))
print("Estimated clusters:", n_clusters_)
colors = 10*['r.','g.','b.','c.','k.','y.','m.']
for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize = 3)
plt.scatter(cluster_centers[:,0],cluster_centers[:,1],
    marker=".",color='k', s=20, linewidths = 5, zorder=10)
plt.show()

Keluaran

[[ 2.98462798 9.9733794 10.02629344]
[ 3.94758484 4.99122771 4.99349433]
[ 3.00788996 3.03851268 2.99183033]]
Estimated clusters: 3

Keuntungan dan kerugian

Keuntungan

Berikut ini adalah beberapa keuntungan dari algoritma pengelompokan Mean-Shift -

Tidak perlu membuat asumsi model seperti dalam campuran K-means atau Gaussian.
Ia juga dapat memodelkan cluster kompleks yang memiliki bentuk nonconvex.
Ini hanya membutuhkan satu parameter bernama bandwidth yang secara otomatis menentukan jumlah cluster.
Tidak ada masalah minimum lokal seperti di K-means.
Tidak ada masalah yang dihasilkan dari pencilan.

Kekurangan

Berikut ini adalah beberapa kelemahan dari algoritma pengelompokan Mean-Shift -

Algoritme pergeseran rata-rata tidak berfungsi dengan baik dalam kasus dimensi tinggi, di mana jumlah cluster berubah secara tiba-tiba.

Kami tidak memiliki kendali langsung atas jumlah cluster, tetapi dalam beberapa aplikasi, kami memerlukan jumlah cluster tertentu.
Itu tidak dapat membedakan antara mode yang bermakna dan tidak berarti.