Thuật toán phân cụm - Thuật toán dịch chuyển trung bình

Giới thiệu về thuật toán Mean-Shift

Như đã thảo luận trước đó, nó là một thuật toán phân cụm mạnh mẽ khác được sử dụng trong học tập không giám sát. Không giống như K-mean clustering, nó không đưa ra bất kỳ giả định nào; do đó nó là một thuật toán không tham số.

Thuật toán Mean-shift về cơ bản chỉ định lặp đi lặp lại các điểm dữ liệu cho các cụm bằng cách dịch chuyển các điểm về phía mật độ điểm dữ liệu cao nhất tức là trung tâm cụm.

Sự khác biệt giữa thuật toán K-Means và Mean-Shift là sau này người ta không cần chỉ định trước số lượng cụm vì số lượng cụm sẽ được xác định bởi dữ liệu wrt của thuật toán.

Hoạt động của thuật toán Mean-Shift

Chúng ta có thể hiểu hoạt động của thuật toán phân cụm Mean-Shift với sự trợ giúp của các bước sau:

Step 1 - Đầu tiên, hãy bắt đầu với các điểm dữ liệu được gán cho một cụm của riêng chúng.
Step 2 - Tiếp theo, thuật toán này sẽ tính toán các centroid.
Step 3 - Trong bước này, vị trí của các trung tâm mới sẽ được cập nhật.
Step 4 - Bây giờ, quy trình sẽ được lặp lại và chuyển đến vùng mật độ cao hơn.
Step 5 - Cuối cùng, nó sẽ bị dừng lại khi các trọng tâm đến vị trí mà nó không thể di chuyển xa hơn.

Triển khai bằng Python

Đó là một ví dụ đơn giản để hiểu cách hoạt động của thuật toán Mean-Shift. Trong ví dụ này, trước tiên chúng ta sẽ tạo tập dữ liệu 2D chứa 4 đốm màu khác nhau và sau đó sẽ áp dụng thuật toán Mean-Shift để xem kết quả.

%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()

Đầu ra

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

Ưu điểm và nhược điểm

Ưu điểm

Sau đây là một số ưu điểm của thuật toán phân cụm Mean-Shift:

Nó không cần đưa ra bất kỳ giả định mô hình nào giống như trong hỗn hợp K-mean hoặc Gaussian.
Nó cũng có thể mô hình hóa các cụm phức tạp có hình dạng không lồi.
Nó chỉ cần một tham số có tên là băng thông sẽ tự động xác định số lượng cụm.
Không có vấn đề về cực tiểu cục bộ như trong K-means.
Không có vấn đề gì được tạo ra từ các ngoại lệ.

Nhược điểm

Sau đây là một số nhược điểm của thuật toán phân cụm Mean-Shift:

Thuật toán dịch chuyển trung bình không hoạt động tốt trong trường hợp thứ nguyên cao, trong đó số lượng cụm thay đổi đột ngột.

Chúng tôi không có bất kỳ kiểm soát trực tiếp nào về số lượng cụm nhưng trong một số ứng dụng, chúng tôi cần một số lượng cụ thể của cụm.
Nó không thể phân biệt giữa các chế độ có ý nghĩa và vô nghĩa.