[ad_1]
Mục lục
1. Giới thiệu
2. Thuật toán K-Means có tác dụng gì?
3. Triển khai bằng Python
4. Đánh giá và giải thích
5. Kết luận và các bước tiếp theo
Hầu hết các thuật toán học máy được sử dụng rộng rãi, chẳng hạn như Hồi quy tuyến tính, Hồi quy logistic, Cây quyết định và các thuật toán khác đều hữu ích để đưa ra dự đoán từ dữ liệu được gắn nhãn, nghĩa là mỗi đầu vào bao gồm các giá trị đặc trưng có giá trị nhãn được liên kết. Đó là những gì được gọi là Học tập có giám sát.
Tuy nhiên, chúng ta thường phải xử lý những tập dữ liệu lớn không có nhãn liên quan. Hãy tưởng tượng một doanh nghiệp cần hiểu các nhóm khách hàng khác nhau dựa trên hành vi mua hàng, nhân khẩu học, địa chỉ và các thông tin khác để có thể cung cấp dịch vụ, sản phẩm và chương trình khuyến mãi tốt hơn.
Những loại vấn đề này có thể được giải quyết bằng cách sử dụng Học không giám sát kỹ thuật. Thuật toán Ok-Means là thuật toán học không giám sát được sử dụng rộng rãi trong Machine Studying. Cách tiếp cận đơn giản và tinh tế của nó giúp có thể tách tập dữ liệu thành số Ok cụm riêng biệt mong muốn, do đó cho phép người ta tìm hiểu các mẫu từ dữ liệu chưa được gắn nhãn.
Như đã nói trước đó, thuật toán Ok-Means tìm cách phân vùng các điểm dữ liệu thành một số cụm nhất định. Các điểm trong mỗi cụm là tương tự nhau, trong khi các điểm ở các cụm khác nhau có sự khác biệt đáng kể.
Nói như vậy, một câu hỏi được đặt ra: làm thế nào để chúng ta xác định sự tương đồng hay khác biệt? Trong phân cụm Ok-Means, khoảng cách Euclide là thước đo phổ biến nhất để đo lường độ tương tự.
Trong hình bên dưới, chúng ta có thể thấy rõ 3 nhóm khác nhau. Do đó, chúng ta có thể xác định tâm của mỗi nhóm và mỗi điểm sẽ được liên kết với tâm gần nhất.
Bằng cách làm điều đó, nói về mặt toán học, ý tưởng là giảm thiểu phương sai trong cụmphép đo độ tương tự giữa mỗi điểm và tâm gần nhất của nó.
Việc thực hiện tác vụ trong ví dụ trên rất đơn giản vì dữ liệu là hai chiều và các nhóm được phân biệt rõ ràng. Tuy nhiên, khi số chiều tăng lên và các giá trị khác nhau của Ok được xem xét, chúng ta cần một thuật toán để xử lý độ phức tạp.
Bước 1: Chọn tâm ban đầu (ngẫu nhiên)
Chúng ta cần tạo ra thuật toán với các vectơ trung tâm ban đầu có thể được chọn ngẫu nhiên từ dữ liệu hoặc tạo ra các vectơ ngẫu nhiên có cùng kích thước với dữ liệu gốc. Xem những viên kim cương trắng trong hình ảnh dưới đây.
Bước 2: Tìm khoảng cách từ mỗi điểm đến tâm
Bây giờ, chúng ta sẽ tính khoảng cách của từng điểm dữ liệu đến tâm Ok. Sau đó chúng ta liên kết mỗi điểm với tâm gần điểm đó nhất.
Cho một tập dữ liệu với N mục và M Đặc điểm, khoảng cách đến các trung tâm c có thể được cho bởi phương trình sau:
Ở đâu:
ok thay đổi từ 1 đến Ok;
D là khoảng cách từ điểm n tới ok trung tâm;
x là vectơ điểm;
c là vectơ trung tâm
Do đó, với mỗi điểm dữ liệu N chúng ta sẽ có Ok khoảng cách, sau đó chúng ta phải gắn nhãn vectơ vào tâm với khoảng cách nhỏ nhất:
Ở đâu D là một vectơ với Ok khoảng cách.
Bước 3: Tìm Ok centroid và lặp lại
Đối với mỗi Ok cụm, tính toán lại trọng tâm. Trọng tâm mới là giá trị trung bình của tất cả các điểm dữ liệu được gán cho cụm đó. Sau đó cập nhật vị trí của trọng tâm theo giá trị mới được tính toán.
Kiểm tra xem trọng tâm có thay đổi đáng kể so với lần lặp trước hay không. Điều này có thể được thực hiện bằng cách so sánh vị trí của các tâm trong lần lặp hiện tại với vị trí của các tâm trong lần lặp cuối cùng.
Nếu trọng tâm thay đổi đáng kể, hãy quay lại Bước 2. Nếu không, thuật toán đã hội tụ và quá trình dừng lại. Xem hình ảnh dưới đây.
Bây giờ chúng ta đã biết các khái niệm cơ bản của thuật toán Ok-Means, đã đến lúc triển khai lớp Python. Các gói được sử dụng là Numpy để tính toán toán học, Matplotlib để trực quan hóa và gói Make_blobs từ Sklearn cho dữ liệu mô phỏng.
# import required packages
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
Lớp sẽ có các phương thức sau:
Phương thức xây dựng để khởi tạo các tham số cơ bản của thuật toán: giá trị ok của cụm, số lần lặp tối đa max_iter, và sự khoan dung tol giá trị để làm gián đoạn việc tối ưu hóa khi không có sự cải thiện đáng kể.
Các phương pháp này nhằm mục đích hỗ trợ quá trình tối ưu hóa trong quá trình huấn luyện, chẳng hạn như tính toán khoảng cách Euclide, chọn ngẫu nhiên trọng tâm ban đầu, gán trọng tâm gần nhất cho mỗi điểm, cập nhật giá trị của trọng tâm và xác minh xem tối ưu hóa có hội tụ hay không.
Như đã đề cập trước đó, thuật toán Ok-Means là một kỹ thuật học không giám sát, nghĩa là nó không yêu cầu dữ liệu được dán nhãn trong quá trình đào tạo. Theo cách đó, cần có một phương pháp duy nhất để khớp dữ liệu và dự đoán mỗi điểm dữ liệu thuộc về cụm nào.
Một phương pháp đánh giá chất lượng tối ưu hóa bằng cách tính toán tổng sai số bình phương của việc tối ưu hóa. Điều đó sẽ được khám phá trong phần tiếp theo.
Đây là mã đầy đủ:
class Kmeans:# assemble technique for hyperparameter initialization
def __init__(self, ok=3, max_iter=100, tol=1e-06):
self.ok = ok
self.max_iter = max_iter
self.tol = tol
# randomly picks the preliminary centroids from the enter information
def pick_centers(self, X):
centers_idxs = np.random.alternative(self.n_samples, self.ok)
return X(centers_idxs)
# finds the closest centroid for every information level
def get_closest_centroid(self, x, centroids):
distances = (euclidean_distance(x, centroid) for centroid in centroids)
return np.argmin(distances)
# creates an inventory with lists containing the idxs of every cluster
def create_clusters(self, centroids, X):
clusters = (() for _ in vary(self.ok))
labels = np.empty(self.n_samples)
for i, x in enumerate(X):
centroid_idx = self.get_closest_centroid(x, centroids)
clusters(centroid_idx).append(i)
labels(i) = centroid_idx
return clusters, labels
# calculates the centroids for every cluster utilizing the imply worth
def compute_centroids(self, clusters, X):
centroids = np.empty((self.ok, self.n_features))
for i, cluster in enumerate(clusters):
centroids(i) = np.imply(X(cluster), axis=0)
return centroids
# helper operate to confirm if the centroids modified considerably
def is_converged(self, old_centroids, new_centroids):
distances = (euclidean_distance(old_centroids(i), new_centroids(i)) for i in vary(self.ok))
return (sum(distances) < self.tol)
# technique to coach the info, discover the optimized centroids and label every information level in accordance with its cluster
def fit_predict(self, X):
self.n_samples, self.n_features = X.form
self.centroids = self.pick_centers(X)
for i in vary(self.max_iter):
self.clusters, self.labels = self.create_clusters(self.centroids, X)
new_centroids = self.compute_centroids(self.clusters, X)
if self.is_converged(self.centroids, new_centroids):
break
self.centroids = new_centroids
# technique for evaluating the intracluster variance of the optimization
def clustering_errors(self, X):
cluster_values = (X(cluster) for cluster in self.clusters)
squared_distances = ()
# calculation of complete squared Euclidean distance
for i, cluster_array in enumerate(cluster_values):
squared_distances.append(np.sum((cluster_array - self.centroids(i))**2))
total_error = np.sum(squared_distances)
return total_error
Bây giờ chúng ta sẽ sử dụng lớp Ok-Means để thực hiện phân cụm dữ liệu mô phỏng. Để làm điều đó, nó sẽ được sử dụng make_blobs gói từ thư viện Sklearn. Dữ liệu bao gồm 500 điểm hai chiều với 4 tâm cố định.
# create simulated information for examples
X, _ = make_blobs(n_samples=500, n_features=2, facilities=4,
shuffle=False, random_state=0)
Sau khi thực hiện đào tạo bằng bốn cụm, chúng tôi đạt được kết quả sau.
mannequin = Kmeans(ok=4)
mannequin.fit_predict(X)
labels = mannequin.labels
centroids =mannequin.centroids
plot_clusters(X, labels, centroids)
Trong trường hợp đó, thuật toán có khả năng tính toán các cụm thành công với 18 lần lặp. Tuy nhiên, chúng ta phải nhớ rằng chúng ta đã biết số cụm tối ưu từ dữ liệu mô phỏng. Trong các ứng dụng thực tế, chúng ta thường không biết giá trị đó.
Như đã nói trước đó, thuật toán Ok-Means nhằm mục đích tạo ra phương sai trong cụm càng nhỏ càng tốt. Số liệu được sử dụng để tính toán phương sai đó là tổng khoảng cách Euclide bình phương được cho bởi:
Ở đâu:
p là số điểm dữ liệu trong một cụm;
c_i là vectơ trọng tâm của cụm;
Ok là số cụm.
Nói cách khác, công thức trên cộng khoảng cách của các điểm dữ liệu đến trọng tâm gần nhất. Sai số giảm khi số Ok tăng.
Trong trường hợp cực đoan Ok =N, bạn có một cụm cho mỗi điểm dữ liệu và lỗi này sẽ bằng 0.
Willmott, Paul (2019).
Nếu chúng ta vẽ lỗi theo số cụm và nhìn vào vị trí “uốn cong” của biểu đồ, chúng ta sẽ có thể tìm thấy số cụm tối ưu.
Như chúng ta có thể thấy, đồ thị có “hình khuỷu tay” và nó uốn cong ở Ok = 4, nghĩa là đối với các giá trị Ok lớn hơn, mức giảm tổng sai số sẽ ít đáng kể hơn.
Trong bài viết này, chúng tôi đã đề cập đến các khái niệm cơ bản đằng sau thuật toán Ok-Means, cách sử dụng và ứng dụng của nó. Ngoài ra, bằng cách sử dụng các khái niệm này, chúng tôi có thể triển khai ngay từ đầu một lớp Python để thực hiện phân cụm dữ liệu mô phỏng và cách tìm giá trị tối ưu cho Ok bằng cách sử dụng sơ đồ phân lớp.
Tuy nhiên, vì chúng ta đang xử lý một kỹ thuật không giám sát nên cần có một bước bổ sung. Thuật toán có thể gán nhãn thành công cho các cụm, nhưng ý nghĩa của mỗi nhãn là nhiệm vụ mà nhà khoa học dữ liệu hoặc kỹ sư máy học sẽ phải thực hiện bằng cách phân tích dữ liệu của từng cụm.
Ngoài ra, tôi sẽ để lại một số điểm để khám phá thêm:
- Dữ liệu mô phỏng của chúng tôi sử dụng các điểm hai chiều. Hãy thử sử dụng thuật toán cho các tập dữ liệu khác và tìm giá trị tối ưu cho Ok.
- Có các thuật toán học không giám sát khác được sử dụng rộng rãi như Phân cụm theo cấp bậc.
- Tùy thuộc vào phạm vi của vấn đề, có thể cần phải sử dụng các phép đo lỗi khác như khoảng cách Manhattan và độ tương tự cosine. Hãy cố gắng điều tra chúng.
Mã hoàn chỉnh có sẵn đây:
[ad_2]
Source link