Phân cụm K-Means là gì?

K-nghĩa là phân cụm là một học tập 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, phân cụm K-means có thể được sử dụng rộng rãi nhất nhờ sức mạnh và tính đơn giản của nó. Phân cụm K-mean hoạt động chính xác như thế nào?

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

Xác định phân cụm

Trước khi chúng tôi kiểm tra các thuật toán chính xác được sử dụng để thực hiện phân cụm theo phương tiện K, chúng ta hãy dành một ít thời gian để xác định phân cụm nói chung.

Các cụm chỉ là các nhóm mục và phân cụm chỉ là đặt các mục vào các nhóm đó. Theo nghĩa khoa học dữ liệu, thuật toán phân cụm nhằm làm hai việc:

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

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

Phân cụm K-Means

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

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

• Đặt tất cả các trường hợp vào các tập hợp con, trong đó số lượng tập hợp con bằng K.
• Tìm điểm trung bình/trọng tâm của các phân vùng cụm mới được tạo.
• Dựa trên các trọng tâm này, hãy gán từng điểm cho một cụm cụ thể.
• Tính khoảng cách từ mọi điểm đến trọng tâm và gán điểm cho các cụm có khoảng cách từ trọng tâm là nhỏ nhất.
• Sau khi các điểm đã được gán cho các cụm, hãy tìm trọng tâm 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 huấn luyện kết thúc.

Trong giai đoạn đầu, trọng tâm được đặt ở đâu đó giữa các điểm dữ liệu.
Ảnh: Weston.pace qua wikimedia commons, Giấy phép Tài liệu Miễn phí GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Ngoài ra, sau khi các trọng tâm đã được đặt, chúng ta có thể hình dung về phân cụm K-means như hoán đổi qua lại giữa hai giai đoạn khác nhau: ghi nhãn điểm dữ liệu và cập nhật trọng tâm.

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

Trong giai đoạn ghi nhãn điểm dữ liệu, mọi điểm dữ liệu được gán một nhãn đặt nó trong cụm thuộc về trọng tâm gần nhất. Trọng tâm gần nhất thường được xác định bằng cách sử dụng khoảng cách Euclide bình phương, mặc dù các số liệu khoảng cách khác như khoảng cách Manhattan, Cosine và khoảng cách 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 phân cụm.

Trong bước thứ ba, trọng tâm được di chuyển đến mức trung bình của tất cả các điểm dữ liệu. Các lớp sau đó được chỉ định 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 bước cập nhật trọng tâm, trọng tâm được tính 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 có trong một cụm.

Cách chọn giá trị phù hợp cho “K”

Xem xét rằng phân cụm K-nghĩa là một thuật toán không được giám sát và số lượng lớp không được biết trước, làm cách nào để bạn quyết định số lượng lớp thích hợp/giá trị phù hợp cho K?

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

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

Phân cụm K-Means theo đợt nhỏ

Khi bộ dữ liệu lớn hơn, thời gian tính toán cũng tăng theo. Phân cụm K-means 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 điều chỉnh đối với phân cụm K-mean đã được thực hiện để cho phép giảm chi phí không gian và thời gian của thuật toán.

Mini-Batch K-có nghĩa là phân cụm là một biến thể trên phân cụm K-means trong đó kích thước của tập dữ liệu đang được xem xét được giới hạn. Phân cụm K-mean bình thường hoạt động trên toàn bộ tập dữ liệu/đợt cùng một lúc, trong khi phân cụm K-mean theo lô nhỏ chia tập dữ liệu thành các tập con. Các lô nhỏ được lấy mẫu ngẫu nhiên từ toàn bộ tập dữ liệu và đối với mỗi lần lặp 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 trọng tâm.

Trong phân cụm K-Means theo lô nhỏ, các cụm được cập nhật với sự kết hợp của các giá trị lô nhỏ và tốc độ học. Tỷ lệ học tập giảm dần qua các lần lặp lại và tỷ lệ này 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 quả của việc giảm tốc độ học tập là tác động của dữ liệu mới bị giảm và đạt được sự hội tụ khi sau một vài lần lặp lại, không có thay đổi nào trong các cụm.

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

Các ứng dụng của K-Means Clustering

K-mean phân cụm có thể được sử dụng một cách an toàn trong mọi tình huống mà các điểm dữ liệu có thể được phân đoạn 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 phân cụm K-mean.

K-mean phân cụm có thể được áp dụng để 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ẻ, cách 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 là bot hay không phải bot dựa trên các mẫu hoạt động như bài đăng và nhận xét. Phân cụm K-means cũng có thể được sử dụng để đưa mọi người vào các nhóm dựa trên mức độ quan tâm khi theo dõi sức khỏe của họ, dựa trên các đặc điểm như bệnh đi kèm, tuổi tác, tiền sử bệnh nhân, v.v.

K-nghĩa là phân cụm cũng có thể được sử dụng cho các nhiệm vụ kết thúc mở hơn như tạo hệ thống đề xuất. 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 kiểu xem và nội dung tương tự được đề xuất. Phân cụm K-means có thể được sử dụng cho các nhiệm vụ phát hiện bất thường, làm nổi bật các trường hợp gian lận tiềm ẩn hoặc các mặt hàng bị lỗi.