Thuật toán phân cụm - Thuật toán K-mean
Giới thiệu về thuật toán K-Means
Thuật toán phân cụm K-mean tính toán các centroid và lặp lại cho đến khi chúng tôi tìm thấy centroid tối ưu. Nó giả định rằng số lượng các cụm đã được biết trước. Nó còn được gọi làflat clusteringthuật toán. Số lượng các cụm được xác định từ dữ liệu bằng thuật toán được biểu thị bằng 'K' trong K-mean.
Trong thuật toán này, các điểm dữ liệu được gán cho một cụm sao cho tổng khoảng cách bình phương giữa các điểm dữ liệu và centroid sẽ là nhỏ nhất. Cần phải hiểu rằng ít biến động hơn trong các cụm sẽ dẫn đến nhiều điểm dữ liệu giống nhau hơn trong cùng một cụm.
Hoạt động của thuật toán K-Means
Chúng ta có thể hiểu hoạt động của thuật toán phân cụm K-Means với sự trợ giúp của các bước sau:
Step 1 - Đầu tiên, chúng ta cần xác định số lượng cụm, K, cần được tạo ra bởi thuật toán này.
Step 2- Tiếp theo, chọn ngẫu nhiên K điểm dữ liệu và gán mỗi điểm dữ liệu vào một cụm. Nói cách đơn giản, hãy phân loại dữ liệu dựa trên số điểm dữ liệu.
Step 3 - Bây giờ nó sẽ tính toán các trung tâm cụm.
Step 4 - Tiếp theo, tiếp tục lặp lại các bước sau cho đến khi chúng ta tìm thấy centroid tối ưu, đó là việc gán các điểm dữ liệu cho các cụm không thay đổi nữa -
4.1 - Đầu tiên, tổng bình phương khoảng cách giữa các điểm dữ liệu và trung tâm sẽ được tính toán.
4.2 - Bây giờ, chúng ta phải gán mỗi điểm dữ liệu cho cụm gần hơn cụm khác (centroid).
4.3 - Cuối cùng, tính toán trọng tâm cho các cụm bằng cách lấy giá trị trung bình của tất cả các điểm dữ liệu của cụm đó.
K-mean theo sau Expectation-Maximizationcách tiếp cận để giải quyết vấn đề. Bước Kỳ vọng được sử dụng để gán các điểm dữ liệu cho cụm gần nhất và bước Tối đa hóa được sử dụng để tính toán trung tâm của mỗi cụm.
Trong khi làm việc với thuật toán K-mean, chúng ta cần lưu ý những điều sau:
Trong khi làm việc với các thuật toán phân cụm bao gồm K-Means, bạn nên chuẩn hóa dữ liệu vì các thuật toán như vậy sử dụng phép đo dựa trên khoảng cách để xác định sự giống nhau giữa các điểm dữ liệu.
Do tính chất lặp đi lặp lại của K-Means và sự khởi tạo ngẫu nhiên của các trung tâm, K-Means có thể gắn bó với mức tối ưu cục bộ và có thể không hội tụ với mức tối ưu toàn cục. Đó là lý do tại sao nó được khuyến khích sử dụng các khởi tạo khác nhau của centroid.
Triển khai bằng Python
Hai ví dụ sau đây về việc triển khai thuật toán phân cụm K-Means sẽ giúp chúng ta hiểu rõ hơn về nó -
ví dụ 1
Đó là một ví dụ đơn giản để hiểu cách hoạt động của k-mean. 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 k-mean để xem kết quả.
Đầu tiên, chúng tôi sẽ bắt đầu bằng cách nhập các gói cần thiết -
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeansĐoạn mã sau sẽ tạo 2D, chứa bốn đốm màu -
from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=400, centers=4, cluster_std=0.60, random_state=0)Tiếp theo, đoạn mã sau sẽ giúp chúng ta hình dung tập dữ liệu:
plt.scatter(X[:, 0], X[:, 1], s=20);
plt.show()
Tiếp theo, tạo một đối tượng của KMeans cùng với việc cung cấp số lượng cụm, đào tạo mô hình và thực hiện dự đoán như sau:
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)Bây giờ, với sự trợ giúp của đoạn mã sau, chúng ta có thể vẽ và hình dung các trung tâm của cụm được chọn bởi trình ước lượng Python k-mean -
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=20, cmap='summer')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='blue', s=100, alpha=0.9);
plt.show()
Ví dụ 2
Chúng ta hãy chuyển sang một ví dụ khác, trong đó chúng ta sẽ áp dụng phân cụm K-mean trên tập dữ liệu các chữ số đơn giản. K-means sẽ cố gắng xác định các chữ số tương tự mà không cần sử dụng thông tin nhãn gốc.
Đầu tiên, chúng tôi sẽ bắt đầu bằng cách nhập các gói cần thiết -
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeansTiếp theo, tải tập dữ liệu chữ số từ sklearn và tạo một đối tượng của nó. Chúng ta cũng có thể tìm số hàng và số cột trong tập dữ liệu này như sau:
from sklearn.datasets import load_digits
digits = load_digits()
digits.data.shapeĐầu ra
(1797, 64)Kết quả trên cho thấy tập dữ liệu này có 1797 mẫu với 64 tính năng.
Chúng ta có thể thực hiện phân cụm như đã làm trong Ví dụ 1 ở trên -
kmeans = KMeans(n_clusters=10, random_state=0)
clusters = kmeans.fit_predict(digits.data)
kmeans.cluster_centers_.shapeĐầu ra
(10, 64)Kết quả trên cho thấy K-mean đã tạo ra 10 cụm với 64 tính năng.
fig, ax = plt.subplots(2, 5, figsize=(8, 3))
centers = kmeans.cluster_centers_.reshape(10, 8, 8)
for axi, center in zip(ax.flat, centers):
axi.set(xticks=[], yticks=[])
axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)Đầu ra
Như đầu ra, chúng ta sẽ nhận được hình ảnh sau đây cho thấy các trung tâm cụm được học bằng k-means.
Các dòng mã sau sẽ khớp các nhãn cụm đã học với các nhãn thực được tìm thấy trong chúng -
from scipy.stats import mode
labels = np.zeros_like(clusters)
for i in range(10):
mask = (clusters == i)
labels[mask] = mode(digits.target[mask])[0]Tiếp theo, chúng ta có thể kiểm tra độ chính xác như sau:
from sklearn.metrics import accuracy_score
accuracy_score(digits.target, labels)Đầu ra
0.7935447968836951Kết quả trên cho thấy độ chính xác là khoảng 80%.
Ư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 K-Means:
Nó rất dễ hiểu và dễ thực hiện.
Nếu chúng ta có số lượng biến lớn thì K-mean sẽ nhanh hơn so với phân cụm phân cấp.
Khi tính toán lại các centroid, một thể hiện có thể thay đổi cụm.
Các cụm chặt chẽ hơn được hình thành với K-means so với phân cụm theo thứ bậc.
Nhược điểm
Sau đây là một số nhược điểm của thuật toán phân cụm K-Means:
Có một chút khó khăn để dự đoán số lượng cụm tức là giá trị của k.
Đầu ra bị tác động mạnh bởi các đầu vào ban đầu như số cụm (giá trị của k).
Thứ tự của dữ liệu sẽ có tác động mạnh mẽ đến kết quả cuối cùng.
Nó rất nhạy cảm với việc thay đổi tỷ lệ. Nếu chúng tôi bán lại dữ liệu của mình bằng phương pháp chuẩn hóa hoặc chuẩn hóa, thì đầu ra sẽ hoàn toàn thay đổi. Đầu ra cuối cùng.
Sẽ không tốt khi thực hiện công việc phân cụm nếu các cụm có dạng hình học phức tạp.
Các ứng dụng của K-Means Clustering Algorithm
Các mục tiêu chính của phân tích cụm là -
Để có được trực giác có ý nghĩa từ dữ liệu chúng tôi đang làm việc.
Cluster-then-dự đoán nơi các mô hình khác nhau sẽ được xây dựng cho các nhóm con khác nhau.
Để hoàn thành các mục tiêu đề cập ở trên, K-means clustering đang hoạt động đủ tốt. Nó có thể được sử dụng trong các ứng dụng sau:
Phân khúc thị trường
Phân cụm tài liệu
Phân đoạn hình ảnh
Nén hình ảnh
Phân khúc khách hàng
Phân tích xu hướng trên dữ liệu động