Mục lục nội dung
Giới thiệu về K-Means
K-means là một thuật toán phân cụm đơn thuần thuộc loại học không giám sát ( tức là tài liệu không có nhãn ) và được sử dụng để xử lý bài toán phân cụm. Ý tưởng của thuật toán phân cụm k-means là phân loại 1 bộ tài liệu thành những cụm khác nhau. Trong đó số lượng cụm được cho trước là k. Công việc phân cụm được xác lập dựa trên nguyên tắc : Các điểm tài liệu trong cùng 1 cụm thì phải có cùng 1 số đặc thù nhất định. Tức là giữa những điểm trong cùng 1 cụm phải có sự tương quan lẫn nhau. Đối với máy tính thì những điểm trong 1 cụm đó sẽ là những điểm tài liệu gần nhau .
Thuật toán phân cụm k-means thường được sử dụng trong những ứng dụng cỗ máy tìm kiếm, phân đoạn người mua, thống kê tài liệu, …
Thuật toán k-means là gì?
Thuật toán phân cụm k-means là một phương pháp được sử dụng trong phân tích tính chất cụm của dữ liệu. Nó đặc biệt được sử dụng nhiều trong khai phá dữ liệu và thống kê. Nó phân vùng dữ liệu thành k cụm khác nhau. Giải thuật này giúp chúng ta xác định được dữ liệu của chúng ta nó thực sử thuộc về nhóm nào.
Bạn đang đọc: Thuật toán phân cụm K-means có demo code Python
Để những bạn dễ tưởng tượng ứng dụng của thuật toán. Chúng ta hãy quan sát một ví dụ trong thực tiễn như sau :
Trong những quy mô kinh doanh thương mại, doanh nghiệp sẽ chia nhỏ tệp người mua ra thành những nhóm đối tượng người tiêu dùng khác nhau để hoàn toàn có thể vận dụng những kế hoạch kinh doanh thương mại đơn cử cho từng nhóm đối tượng người dùng. Điều này giúp cho người mua được tiếp cận với những loại sản phẩm thật sự tương thích với bản thân họ. Sự tương thích đó sẽ kéo doanh thu của tất cả chúng ta tăng lên. Vấn đề đặt ra là làm thế nào hoàn toàn có thể chia nhỏ tệp người mua đó ra khi mà số lượng hóa đơn là rất lớn và tất cả chúng ta không hề ngồi để nghiên cứu và phân tích từng vị khách .
Và tiềm năng của những thuật toán phân cụm là từ tập dữ liệu khổng lồ đó. Làm sao tất cả chúng ta biết có những nhóm tài liệu đặc trưng nào trong đó ? Từng tài liệu trong đó thuộc vào nhóm nào ? Đó là cái mà thuật toán phân cụm của tất cả chúng ta cần đi tìm câu vấn đáp .
Có thể bạn chăm sóc : Tensorflow tutorial
Thực hành với K-Means
Đây là một ví dụ đơn thuần về thuật toán phân cụm k-means trên khoảng trống 2 chiều. Code ví dụ được viết bằng ngôn từ python. Sẽ có nhiều hình ảnh để những bạn hiểu được từng bước của thuật toán này .
Bài toán: Có 1 tập hợp các điểm trên không gian tọa độ Oxy. Mỗi điểm sẽ có tọa độ (x, y) xác định. Bài toán cần giải quyết là chia các điểm này thành K cụm khác nhau phân biệt.
Triển khai code
Đầu tiên, hãy import những thư viện thiết yếu
| 01234 | importnumpyasnp# thư viện đo lường và thống kê toán học importmatplotlib.pyplotasplt# visualize data sử dụng đồ thị fromscipy.spatial.distanceimportcdist# Hỗ trợ tính khoảng cách |
Tôi sẽ khởi tạo ngẫu nhiên các điểm dữ liệu. Tuy nhiên, để thể hiện tính chất cụm của dữ liệu, ta sẽ khởi tạo các mẫu dữ liệu này xung quanh 3 tâm cụm (2, 2), (9, 2) và (4,9).
Ứng với mỗi tâm cụm, ta sẽ khởi tạo 500 điểm dữ liệu xung quanh nó. Ở đây lần lượt là X0, X1, X2.
| 0123456789 | means=[[2,2],[9,2],[4,9]] cov=[[2,0],[0,2]] n_samples=500 n_cluster=3 X0=np.random.multivariate_normal(means[0],cov,n_samples) X1=np.random.multivariate_normal(means[1],cov,n_samples) X2=np.random.multivariate_normal(means[2],cov,n_samples) X=np.concatenate((X0,X1,X2),axis=0) |
Để đơn giản, tôi sẽ chỉ định số tâm cụm cho bài toán này là n_cluster = 3 luôn – chính là K đó ạ. Đúng với số cụm chúng ta vừa khởi tạo. Bạn có thể thử và xem với các giá trị n_cluster khác nhau để xem sự thay đổi.
Bạn hoàn toàn có thể xem phân bổ của tài liệu mà tất cả chúng ta vừa tạo ra như sau :
| 0123456 | plt.xlabel(‘ x ‘) plt.ylabel(‘ y ‘) plt.plot(X[:,0],X[:,1],’ bo ‘,markersize=5) plt.plot() plt.show() |
Như vậy, nếu thuật toán phân cụm k-means hoạt động tốt, nó sẽ phải học ra 3 tâm cụm có tọa độ sát với 3 tâm cụm (2, 2), (9, 2) và (4,9). Và ban đầu tọa độ của các tâm này sẽ được lấy ngẫu nhiên.
Bây giờ, chúng ta hãy viết hàm khởi tạo n_cluster tâm cụm
| 012345 | defkmeans_init_centers(X,n_cluster): # random k index beetween 0 and shape ( X ) without duplicate index . # Then return X [ index ] as cluster returnX[np.random.choice(X.shape[0],n_cluster,replace=False)] |
Ở đây, tôi khởi tạo n_cluster tâm cụm bằng cách lấy ngẫu nhiên n_cluster điểm dữ liệu của tập dữ liệu. Bạn có thể lấy tọa độ nào đó không thuộc vào tệp dữ liệu. Nhưng hãy lưu ý đến: “Việc khởi tạo vị trí của k tâm cụm cũng rất quan trọng” tôi đã nói ở trên.
Xác định các tâm cụm
| 012345 | defkmeans_predict_labels(X,centers): D=cdist(X,centers) # return index of the closest center returnnp.argmin(D,axis=1) |
Với mỗi điểm dữ liệu trong tập dữ liệu, tâm cụm của nó sẽ là 1 trong số n_cluster tâm cụm gần với nó nhất. Việc tính toán khoảng cách giữa 2 điểm trong bài này sử dụng Euclidean distance. Công thức này bạn vẫn thường sử dụng để tính khoảng cách giữa hai điểm khi biết tọa độ hồi cấp 3. Ngoài ra còn có rất nhiều công thức tính khoảng cách khác nữa.
Cập nhật lại vị trí của các tâm cụm
| 0123456789 | defkmeans_update_centers(X,labels,n_cluster): centers=np.zeros((n_cluster,X.shape[1])) forkinrange(n_cluster): # collect all points assigned to the k-th cluster Xk=X[labels==k,:] # take average centers[k,:]=np.mean(Xk,axis=0) returncenters |
Việc thống kê giám sát lại tọa độ của mỗi tâm cụm được triển khai đơn thuần bằng cách lấy trung bình cộng tọa độ của tổng thể những điểm tài liệu của cụm. Sau khi đo lường và thống kê xong, vị trí mới của tâm cụm sẽ nằm chính giữa cụm của nó .
Kiểm tra tính hội tụ
| 012345 | defkmeans_has_converged(centers,new_centers): # return True if two sets of centers are the same return(set([tuple(a)foraincenters])== set([tuple(a)forainnew_centers])) |
Nếu việc update lại vị trí của những tâm cụm không có biến hóa gì thì có nghĩa là tất cả chúng ta đã hoàn toàn có thể dừng và đưa ra hiệu quả. Nghĩa là tọa độ cũ và tọa độ sau khi update của những tâm cụm là như nhau. Trong trường hợp này, nếu bạn có liên tục chạy nữa thì cũng sẽ không biến hóa gì .
Để những bạn hoàn toàn có thể thấy rõ cách hoạt động giải trí của thuật toán, hãy bổ trợ thêm hàm visualize này
| 01234567891011121314151617 | # Hàm này dùng để vẽ tài liệu lên đồ thị # Random color chỉ thao tác với k < = 4 # Nếu bạn biến hóa k > 4, hãy sửa lại phần random color nhé # Chỉ sử dụng trong bài toán này thôi nhé . defkmeans_visualize ( X,centers,labels,n_cluster,title): plt.xlabel(‘ x ‘)# label trục x plt.ylabel(‘ y ‘)# label trục y plt.title(title)# title của đồ thị plt_colors=[‘ b ‘,’ g ‘,’ r ‘,’ c ‘,’ m ‘,’ y ‘,’ k ‘,’ w ‘]# list những màu tương hỗ foriinrange(n_cluster): data=X[labels==i]# lấy tài liệu của cụm i plt.plot(data[:,0],data[:,1],plt_colors[i]+’ ^ ‘,markersize=4,label=’ cluster_ ‘+str(i))# Vẽ cụm i lên đồ thị plt.plot(centers[i][0],centers[i][1],plt_colors[i+4]+’ o ‘,markersize=10,label=’ center_ ‘+str(i))# Vẽ tâm cụm i lên đồ thị plt.legend()# Hiện bảng chú thích plt.show() |
Sau mỗi lần cập nhật tâm cho từng điểm tài liệu, hoặc update lại tọa độ của những tâm. Hãy gọi hàm này để xem sự biến hóa của vị trí tâm và tâm của những điểm tài liệu. Kết quả sẽ được vẽ lên đồ thị để bạn dễ quan sát .
Toàn bộ thuật toán k-means
| 0123456789101112131415 | defkmeans(init_centes,init_labels,X,n_cluster): centers=init_centes labels=init_labels times=0 whileTrue: labels=kmeans_predict_labels(X,centers) kmeans_visualize(X,centers,labels,n_cluster,’ Assigned label for data at time = ‘+str(times+1)) new_centers=kmeans_update_centers(X,labels,n_cluster) ifkmeans_has_converged(centers,new_centers): break centers=new_centers kmeans_visualize(X,centers,labels,n_cluster,’ Update center possition at time = ‘+str(times+1)) times+=1 return(centers,labels,times) |
Bạn đầu, tất cả chúng ta sẽ khởi tọa độ cho những tâm cụm. Khởi tạo toàn bộ những điểm tài liệu thuộc cụm 0 ( tùy chọn ) .
Lặp lại việc tìm tâm cụm cho những điểm tài liệu, update tọa độ tâm cụm cho tới khi tọa độ của những tâm cụm không còn biến hóa nữa .
Do bài toán này khá đơn thuần, nên việc giải chỉ mất vài lần lặp .
Chúng ta sẽ gọi hàm kmeans_visualize sau mỗi lần gán lại tâm cụm cho từng điểm dữ liệu hoặc tính toán lại tọa độ các tâm cụm.
Bây giờ, việc ta cần làm là khởi tạo tọa độ tâm các cụm. Và sau đó gọi hàm kmeans phía trên để thực thi.
| 012345678 | init_centers=kmeans_init_centers(X,n_cluster) print(init_centers)# In ra tọa độ khởi tạo khởi đầu của những tâm cụm init_labels=np.zeros(X.shape[0]) kmeans_visualize(X,init_centers,init_labels,n_cluster,’ Init centers in the first run. Assigned all data as cluster 0 ‘) centers,labels,times=kmeans(init_centers,init_labels,X,n_cluster) print(‘ Done ! Kmeans has converged after ‘,times,’ times ‘) |
Bạn hoàn toàn có thể xem sự biến hóa ở những lần chạy như sau :
Đây là tọa độ tâm những cụm khởi tạo ngẫu nhiên
| 01234 | [[4.637958258.18623907] [-0.302160263.63816318] [4.531411391.41293449]] |
Quá trình chạy được biểu lộ lần lượt theo đồ thị dưới đây :
Sau khi chạy xong thuật toán k-means. Chúng ta hãy thử in gia tọa độ của những tâm cụm :
| 0123456 | print(centers) >> [[4.034578958.99262915] [1.967288051.9546642] [8.816883071.9386987]] |
Kết quả cho ra tọa độ của 3 tâm cụm khá sát vớt các tâm mà chúng ta khởi tạo là (2, 2), (9, 2) và (4,9). Điều đó cho thấy k-means đã làm rất tốt trong bài toán này.
Các bạn có thể thử thay đổi các giá trị k khác nhau để xem sự thay đổi. Bạn cũng có thể sử đổi theo ý mình để hiểu cả ý tưởng của thuật toán lẫn triển khai code.
Xem thêm: Viber
Bạn đọc thực nghiệm
Source code thuật toán K-Measn trình diễn trong bài viết này được lưu tại Github, bạn đọc hoàn toàn có thể nhấp vào link dưới đây để thực hành thực tế trực tiếp nhé !
Hãy để lại vướng mắc của bạn xuống mục phản hồi. Tôi sẽ vấn đáp những bạn sớm nhất hoàn toàn có thể !
Source: https://mindovermetal.org
Category: Ứng dụng hay
