K-Means Clustering Là Gì?

K-means clustering là một thuật toán học không giám sát, và trong số tất cả các thuật toán học không giám sát, K-means clustering có thể là thuật toán được sử dụng rộng rãi nhất, nhờ vào sức mạnh và sự đơn giản của nó. Vậy K-means clustering hoạt động như thế nào?

Câu trả lời ngắn gọn là K-means clustering hoạt động bằng cách tạo một điểm tham chiếu (centroid) cho một số lớp mong muốn, và sau đó gán dữ liệu vào các cụm lớp dựa trên điểm tham chiếu nào gần nhất. Mặc dù đó là một định nghĩa nhanh chóng cho K-means clustering, nhưng hãy dành một chút thời gian để tìm hiểu sâu hơn về K-means clustering và hiểu rõ hơn về cách nó hoạt động.

Định Nghĩa Cụm

Trước khi chúng ta xem xét các thuật toán chính xác được sử dụng để thực hiện K-means clustering, hãy dành một chút thời gian để định nghĩa cụm nói chung.

Cụm chỉ là các nhóm mục, và cụm là việc đặt mục vào các nhóm đó. Trong lĩnh vực khoa học dữ liệu, các thuật toán cụm nhằm thực hiện hai việc:

• Đảm bảo tất cả các điểm dữ liệu trong một cụm đều giống nhau càng nhiều càng tốt.
• Đảm bảo tất cả các điểm dữ liệu trong các cụm khác nhau đều khác nhau càng nhiều càng tốt.

Các thuật toán cụm nhóm các mục lại với nhau dựa trên một số tiêu chí về sự tương tự. Điều này thường được thực hiện bằng cách tìm “centroid” của các nhóm khác nhau trong tập dữ liệu, mặc dù không phải lúc nào cũng như vậy. Có nhiều loại thuật toán cụm khác nhau, nhưng mục tiêu của tất cả các thuật toán cụm là giống nhau, đó là xác định các nhóm nội tại trong một tập dữ liệu.

K-Means Clustering

K-Means Clustering là một trong những thuật toán cụm lâu đời nhất và được sử dụng rộng rãi nhất, và nó hoạt động dựa trên vector quantization. Có một điểm trong không gian được chọn làm điểm gốc, và sau đó các vector được vẽ từ điểm gốc đến tất cả các điểm dữ liệu trong tập dữ liệu.

Nói chung, K-means clustering có thể được chia thành năm bước khác nhau:

• Đặt tất cả các thể hiện vào các tập con, nơi số lượng tập con bằng với K.
• Tìm điểm trung bình / centroid của các phân vùng cụm mới tạo.
• Dựa trên các centroid này, gán mỗi điểm vào một cụm cụ thể.
• Tính toán khoảng cách từ mỗi điểm đến các centroid, và gán điểm vào các cụm nơi khoảng cách từ centroid là tối thiểu.
• Sau khi các điểm đã được gán vào các cụm, tìm centroid mới của các cụm.

Các bước trên được lặp lại cho đến khi quá trình đào tạo hoàn thành.

Trong giai đoạn ban đầu, các centroid được đặt ở một nơi nào đó trong các điểm dữ liệu.
Ảnh: Weston.pace qua wikimedia commons, Giấy phép Tài liệu Tự do GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Ngược lại, sau khi các centroid đã được đặt, chúng ta có thể coi K-means clustering như việc luân phiên giữa hai giai đoạn khác nhau: gán nhãn cho các điểm dữ liệu và cập nhật centroid.

Trong bước thứ hai, một metric khoảng cách như khoảng cách Euclidean được sử dụng để tính toán centroid nào mà một điểm nhất định gần nhất, và sau đó các điểm được gán vào lớp của centroid đó. Ảnh: Weston.pace qua Wikimedia Commons, Giấy phép Tài liệu Tự do GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Trong giai đoạn gán nhãn cho các điểm dữ liệu, mỗi điểm dữ liệu được gán một nhãn đặt nó vào cụm thuộc về centroid gần nhất. Centroid gần nhất thường được xác định bằng khoảng cách Euclidean bình phương, mặc dù các metric khoảng cách khác như khoảng cách Manhattan, Cosine và Jaccard có thể được sử dụng tùy thuộc vào loại dữ liệu được đưa vào thuật toán cụm.

Trong bước thứ ba, centroid được di chuyển đến trung bình của tất cả các điểm dữ liệu. Các lớp sau đó được gán lại. Ảnh: Weston.pace qua Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Trong giai đoạn cập nhật centroid, centroid được tính toán bằng cách tìm khoảng cách trung bình giữa tất cả các điểm dữ liệu hiện tại trong một cụm.

Làm Thế Nào Để Chọn Giá Trị Đúng Cho “K”

Vì K-means clustering là một thuật toán không giám sát và số lượng lớp không được biết trước, làm thế nào để quyết định số lượng lớp phù hợp / giá trị đúng cho K?

Một kỹ thuật để chọn giá trị K phù hợp là gọi là “phương pháp khuỷu”. Phương pháp khuỷu bao gồm chạy thuật toán K-means clustering cho một loạt các giá trị K khác nhau và sử dụng một metric độ chính xác, thường là Tổng Squared Error, để xác định giá trị K nào cho kết quả tốt nhất. Tổng Squared Error được xác định bằng cách tính toán khoảng cách trung bình giữa centroid của một cụm và các điểm dữ liệu trong cụm đó.

Thuật ngữ “phương pháp khuỷu” xuất phát từ thực tế rằng khi bạn vẽ SSE với các giá trị K khác nhau, đồ thị kết quả thường có hình dạng “khuỷu”, nơi SSE giảm nhanh trong vài giá trị K đầu tiên, nhưng sau đó trở nên bằng phẳng. Trong trường hợp như vậy, giá trị K nằm ở khuỷu là giá trị tốt nhất cho K, vì có sự giảm dần nhanh chóng sau giá trị này.

Mini-Batch K-Means Clustering

Khi các tập dữ liệu trở nên lớn hơn, thời gian tính toán cũng tăng lên. K-means clustering cơ bản có thể mất nhiều thời gian để hoàn thành khi chạy trên các tập dữ liệu lớn, và do đó, các biến thể của K-means clustering đã được tạo ra để giảm chi phí không gian và thời gian của thuật toán.

Mini-Batch K-means clustering là một biến thể của K-means clustering nơi kích thước của tập dữ liệu được xem xét là bị giới hạn. K-means clustering thông thường hoạt động trên toàn bộ tập dữ liệu / batch tại một thời điểm, trong khi Mini-batch K-means clustering chia tập dữ liệu thành các tập con. Các mini-batch được lấy mẫu ngẫu nhiên từ toàn bộ tập dữ liệu và cho mỗi lần lặp lại mới, một mẫu ngẫu nhiên mới được chọn và sử dụng để cập nhật vị trí của các centroid.

Trong Mini-Batch K-Means clustering, các cụm được cập nhật với sự kết hợp của các giá trị mini-batch và tốc độ học. Tốc độ học giảm dần theo các lần lặp lại, và nó là nghịch đảo của số lượng điểm dữ liệu được đặt trong một cụm cụ thể. Hiệu ứng của việc giảm tốc độ học là tác động của dữ liệu mới bị giảm và sự hội tụ được đạt được khi, sau một số lần lặp lại, không có thay đổi trong các cụm.

Kết quả của các nghiên cứu về hiệu quả của Mini-batch K-means clustering cho thấy nó có thể giảm thành công thời gian tính toán với một sự đánh đổi nhỏ về chất lượng cụm.

Ứng Dụng Của K-Means Clustering

K-means clustering có thể được sử dụng an toàn trong bất kỳ tình huống nào mà các điểm dữ liệu có thể được phân chia thành các nhóm / lớp riêng biệt. Dưới đây là một số ví dụ về các trường hợp sử dụng phổ biến cho K-mean clustering.

K-means clustering có thể được áp dụng cho phân loại tài liệu, nhóm các tài liệu dựa trên các tính năng như chủ đề, thẻ, sử dụng từ, siêu dữ liệu và các tính năng tài liệu khác. Nó cũng có thể được sử dụng để phân loại người dùng thành bot hoặc không phải bot dựa trên các mẫu hoạt động như bài đăng và bình luận. K-means clustering cũng có thể được sử dụng để nhóm người vào các nhóm dựa trên mức độ lo lắng khi theo dõi sức khỏe của họ, dựa trên các tính năng như bệnh đồng thời, tuổi, lịch sử bệnh nhân, v.v.

K-means clustering cũng có thể được sử dụng cho các nhiệm vụ mở hơn như tạo hệ thống khuyến nghị. Người dùng của một hệ thống như Netflix có thể được nhóm lại với nhau dựa trên mẫu xem và khuyến nghị nội dung tương tự. K-means clustering có thể được sử dụng cho các nhiệm vụ phát hiện bất thường, nhấn mạnh các trường hợp có thể là gian lận hoặc các mục bị lỗi.