Xây dựng clustering model sử dụng giải thuật K-means với thư viện scikit-learn

Hôm nay, chúng ta cùng nhau xây dựng một chương trình ứng dụng giải thuật K-means với sự giúp đỡ của thư viện scikit learn nhé.

1. Khái quát về K-means và thư viện scikit-learn

Về giải thuật K-means, trên stories cũng có bài viết về giải thuật này rồi, mọi người có thể tham khảo TẠI ĐÂY. Nói qua một chút về K-means, đây là một giải thuật học không có giám sát với mục tiêu là phân các ví dụ về k cụm, sao cho cực tiểu hóa khoảng cách giữa các ví dụ trong một cụm và cực đại hóa khoảng cách giữa các cụm với nhau. Đây là một giải thuật quan trong trong lớp các giải thuật học không giám sát, ý tưởng chung của nó là xuất phát từ tâm cụm khởi đầu, tiến hành phân các ví dụ vào cụm mà có tâm cụm gần nó nhất, sau đó điều chỉnh lại tâm cụm, rồi lại phân lại các ví dụ vào các cụm, rồi lại điều chỉnh tâm cụm…, cứ như vậy cho đến khi thuật toán hội tụ.
Còn thư viện scikit learn là một thư viện vô cùng hữu ích cho những ai làm về Machine Learning và Data Science, nó được implement bằng Python, cung cấp các modules biểu diễn các models ứng với từng giải thuật. Scikit learn phủ khắp các giải thuật học máy từ học có giám sát (linear regression, logistic regression, SVM…), học không có giám sát (K-means, DBSCAN…), đến cả các giải thuật về xử lý, nén, biến đổi chiều dữ liệu… và các class phụ trợ cho việc xây dựng pipeline cho hệ thống, lựa chọn siêu tham số (hyperparameters) phù hợp… Nếu bạn muốn tìm hiểu thêm về thư viện này thì có thể tìm đọc cuốn “Hands on Machine learning with Scikit Learn, Keras and TensorFlow” với giới thiệu sơ lược về các thuật toán và kèm theo đó là hướng dẫn cách sử dụng các class tương ứng.

2. Xây dựng chương trình với thư viện scikit-learn

Bây giờ chúng ta cùng chuyển sang phần chính: implement một chương trình ứng dụng giải thuật K-means với scikit-learn.

2.1. Tạo bộ dữ liệu

Trước hết ta cùng tạo bộ dữ liệu cho bài toán nhé, scikit learn có module make_blobs giúp chúng ta random các điểm trong không gian và sử dụng nó như các ví dụ cho quá trình train hệ thống.
image
Bộ dữ liệu của chúng ta sẽ gồm 200 ví dụ, mỗi ví dụ gồm 2 thuộc tính để có thể dễ dàng quan sát trên mặt phẳng. Dữ liệu sẽ được random “có chủ đích” để làm sao cho các ví dụ sẽ xoay quanh 4 điểm centers.
Cùng visualize dữ liệu mà ta có để quan sát sự phân bố của các điểm trong không gian.


Dễ dàng quan sát bằng mắt thường là dữ liệu trên có thể chia vào 4 cụm khác nhau, tuy nhiên trong thực thế thì real data sẽ khó có sự phân bố rõ ràng như thế này, đặc biệt là ở đây ví dụ chỉ có 2 features nên có thể trải được trên mặt phẳng, ngoài đời thì các ví dụ có thể có rất nhiều features nên chúng ta rất khó có thể hình dung được sự phân bổ của chúng trong không gian, đó là lý do tại sao chúng ta cần đến K-means.

2.2. Sử dụng class Kmeans để dựng clustering model

Bây giờ cùng dùng class Kmeans của scikit learn để tiến hành phân cụm các ví dụ này nhé.
image
Tham số n_clusters xác định giá trị k, tức số cụm chúng ta muốn phân. Do ở đây quan sát bằng mắt cũng có thể thấy được dữ liệu phân thành 4 vùng nên chúng ta sẽ đặt luôn bằng 4. Còn khi không thể quan sát được rõ, hay không thể xác định được k từ trước, ta cần có kỹ thuật để xác định giá trị k sao cho tối đa hóa hiệu quả phân cụm, cụ thể sẽ trình bày ở sau nhé!
Chúng ta có thể lấy ra các vị trí tâm của mỗi cụm thông qua attribute cluster_centers_
image
Kết quả vị trí của 4 tâm cụm:
image
Cùng quan sát kết quả so sánh giữa cụm ban đầu sinh bởi module make_blobs và cụm được phân bởi hệ thống với giải thuật Kmeans:
image
Kết quả:
image
Khá tương đồng phải không?

2.3. Lựa chọn số cụm phù hợp

Vấn đề của K-means là chúng ta phải xác định trước giá trị tham số k, ở trường hợp này do dataset của chúng ta có thể visualize được và phân bố cũng khá rõ ràng nên chúng ta có thể dễ dàng xác định được k=4.Vậy trong trường hợp không thể rõ ràng xác định trước giá trị k thì chúng ta phải làm như thế nào?
image
Hình trên cho ta thấy một ví dụ minh họa việc lựa chọn sai giá trị k có thể ảnh hưởng tới hiệu quả phân cụm của thuật toán. Rõ ràng ta thấy số cụm bằng 5 sẽ là lý tưởng, k=3 (quá nhỏ) hoặc k=8 (quá lớn) đều dẫn tới kết quả phân cụm không được “đẹp”.
Chúng ta có thể đưa ra một thông số đánh giá hiệu năng của việc phân cụm và lựa chọn giá trị k để cực đại hóa độ đo này. Cụ thể chúng ta sử dụng silhouette score. Với mỗi ví dụ, giá trị silhouette score của nó được tính như sau:
silhouette score = (b-a)/max(a,b)
Trong đó:

  • a là khoảng cách trung bình tới các ví dụ khác ở trong cùng một cụm
  • b là khoảng cách trung bình tới các ví dụ trong cụm gần nhất
    Giá trị silhouette score nằm trong khoảng từ -1 đến 1
  • silhouette score nằm gần 1 nghĩa là ví dụ đang được phân cụm chính xác, xa các cụm khác
  • silhouette score gần 0 nghĩa là ví dụ đang nằm gần đường bao của cụm
  • silhouette score gần -1 nghĩa là ví dụ đang bị phân sai cụm
    Chúng ta có thể lấy giá trị silhouette score thông qua hàm silhouette_score() của thư viện scikit-learn:
    image
    Kết quả:
    image
    Bây giờ hãy thử với các giá trị k khác nhau để chọn ra giá trị k ứng với silhouette score cao nhất nhé:
    image
    Kết quả hiển thị trên đồ thị:

    Như bạn thấy đấy, ta sẽ chọn k=4 ứng với tập dataset của chúng ta để thu được giá trị silhouette score tốt nhất.

2.4. Khởi tạo tâm cụm

Có một điều chú ý là hiệu quả của việc phân cụm phụ thuộc rất nhiều vào việc khời tạo giá trị tâm cụm ban đầu. Các tâm cụm ban đầu khác nhau sẽ có thể dẫn tới đưa ra các cụm khác nhau.
image
Hoặc lựa chọn random một tâm cụm ban đầu khác ta thu được kết quả khác hẳn
image
Một giải pháp là thực hiện nhiều lần K-means với các tâm cụm ban đầu khác nhau và lựa chọn model có hiệu quả phân cụm tốt nhất.
image
Chúng ta set tham số init bằng ‘random’ để model thực hiện lựa chọn tâm cụm khởi đầu một cách hoàn toàn ngẫu nhiên, tham số n_init cho biết model thực hiện 10 lần train với bộ tâm cụm khởi đầu khác nhau để lựa chọn model cho hiệu quả phân loại tốt nhất
Có một cách khác lựa chọn các tâm cụm mà không cần thực hiện train nhiều lần, cụ thể tâm cụm thứ i sẽ được lựa chọn sao cho cực đại hóa khoảng cách từ nó đến tâm cụm gần nó nhất trong số i-1 tâm cụm đã được chọn trước đó. Cách này được module Kmeans sử dụng như mặc định.
image
Một chú ý khi sử dụng K-means đó là K-means không phù hợp cho các cụm không có dạng hình cầu, dạng lồi, bởi lúc này giải thuật sẽ xuất ra các cụm rất tệ:
image
Nên trước khi lựa chọn giải thuật, tốt nhất hãy visualize date lên để quan sát sự phân bố của các ví dụ từ đó quyết định hướng đi phù hợp nhé!

2 Likes

Huhu nhiều kiến thức chị ko hiểu, nhưng chị thích cách em giải thích vấn đề và viết. Rõ ràng và kết nối.

Một số đoạn về code em sử dụng markdown, vừa đẹp vừa có thể copy paste được nhé
from sklearn.cluster import KMeans
kmeans = Kmeans(n_clusters = 4, init = 'random', n_init = 10)
y_pred = kmeans.fit_predict(x)