Tìm hiểu cơ bản về thuật toán K-means Clustering

Bài toán K-means Clustering

Ngày nay với sự phát triển một cách nhanh chóng của công nghệ đặc biệt là trí tuệ nhân tạo. Các từ khóa liên quan đến lĩnh vực này được truy xuất với các tuần số lớn và có vô vàn các câu hỏi trên các diễn đàn lớn nhỏ về lĩnh vực này. Và các thuật toán nền tảng để phát triển trong lĩnh vực này là mối quan tâm lớn. Ngày hôm nay, chúng ta đi tìm hiểu về thuật toán cơ bản nhất trong đó. Đối ứng với Linear Regression là một thuật toán cơ bản trong Supervised learning chúng ta cũng có K-means Clustering là một thuật toán cơ bản trong Unsupervised learning.

Trích dẫn vấn đề:

Chúng ta đều biết với mỗi cá thể người là có vô vàn sự khác biệt nhau về chiều cao, cân nặng, kích thước bàn chân, bàn tay, kích thước đầu,… Và đây là một vấn đề vô cùng khó khăn cho người cung cấp các sản phẩm thời trang để có thể đáp ứng quần áo phù hợp với từng cá thể. Khi mà với loại mũ lưỡi trai chúng ta có thể sử dụng đai thắt để điều chỉnh kích cỡ phù hợp, cũng như sử dụng dây lưng để có thể ôm phù hợp với cơ thể mình, hoặc cắt bớt độ dài quần để phù hợp với cơ thể. Nhưng vẫn còn số thứ khác phải tính đến như mũ bucket thì sao?? Hay những loại quần áo trang trí họa tiết mà không thể cắt bỏ? Người ta đã nghĩ đến việc phân vùng các nhóm người dựa trên tương quan về cân nặng, chiều cao để phân quần áo thành các nhóm mà nó phù hợp với một nhóm người thay vì vừa vặn với từng cá thể, cũng như tạo size giày dép dựa trên tương quan kích thước bàn chân. Và câu hỏi ban đầu được đưa về là “Làm sao để có thể phân chia một cách phù hợp nhất?”. Thì K-means Clustering là thuật toán phù hợp để giải quyết cho câu hỏi này.

Mô tả K-means Clustering:

Khác với bài toán được LinearRegression, các dữ liệu của chúng ta được phân bổ theo trục tọa độ có chiều bằng số các yếu tố tác động đến nó (ví dụ như quần áo được chia cân nặng, chiều cao thì nó tương tự như một điểm được biểu diễn trên trục tọa độ Oxy ). Chúng ta cần biết được là số lượng các phân nhóm (Cluster) sử dụng để chia dữ liệu thành các nhóm nhỏ hơn, giả sử là n. Khi đó một phần tử thuộc nhóm Ai khi phần tử đó có khoảng cách của phần tử đó đến điểm trung tâm của nhóm Ailuôn nhỏ hơn khoảng cách từ phần tử đó đến Ajvới ji. Và phân nhóm tối ưu nhất khi tổng khoảng cách các phần tử đến điểm trung tâm nhóm mình là nhỏ nhất.

Min{H=i=0n(||a-xi||22)}với xilà phần tử trung tâm của nhóm Ai và a là các phần tử tương ứng thuộc Ai.

Để giải được bài toán trên người ta có thể sử dụng hai phương pháp:

  • Cố định điểm trung tâm để đi tìm các điểm xung quanh nó.

Khi đó, chúng ta sẽ sử dụng các điểm trung tâm cho trước để tìm các điểm xung quanh từ đó chúng ta tìm được giá trị của biểu thức H ứng với mỗi bộ điểm trung tâm và tìm được ra bộ trung tâm nào làm cho biểu thức H nhỏ nhất.

  • Cố định các nhóm và đi tìm các điểm trung tâm.

Khi đó, chúng ta cũng tương tự tìm được bộ điểm trung tâm ứng với mỗi nhóm và tiếp tục biểu thức H ứng với mỗi các phân nhóm đó và đi tìm H nhỏ nhất, qua đó tìm được các điểm trung tâm và các phân nhóm tương ứng.

Hay chúng ta có thể mô tả nó một cách toán học hơn như sau:

Giả sử có N điểm dữ liệu là X = [x1,x2,…,xN] RdNvà chúng ta phải phân nhóm các điểm dữ liệu trên vào K nhóm (K < N). Khi đó với mỗi nhóm chúng ta sẽ có miRd1là điểm trung tâm nhóm thứ i (1 <= i <= K), và label của mỗi điểm dữ liệu. Label của xi ở đây yi= {yi1,yi2,…,yiK} và nếu xi thuộc nhóm j thì yij=1 và yin= 0 với nj, 1j,nK. Hay yij{0,1}, j=1Kyij=1.

Giả sử mk là trung tâm của mỗi cluster và dự đoán các điểm thuộc vào phân nhóm này bởi mk. Khi đó xi thuộc phân nhóm j thì sẽ có sai số (hay có thể hiểu là khoảng cách tương ứng với các giải trên) là : (xi- mj) và bài toán sẽ là đi tìm giá trị nhỏ nhất của ||xi-mj||22 mà label thể hiện rõ rằng xi thuộc phân nhóm nào nên ta có thể tổng quá thành:

n=1Kyin||xi-mj||22(1) khi đó sai số cho toàn bộ dữ liệu này là H = i=1Nn=1Kyin||xi-mj||22. Chúng ta không thể loại bỏ x để cho biểu thức H giảm giá trị vậy nên chúng ta phải tìm bộ Y,M sao cho H nhỏ nhất với X cho trước.

Khi đó ta lại trở về hai cách giải quyết trên. Và với việc cố định M ta làm như một phương thức vét cạn các cặp số và tìm H sao cho H nhỏ nhất.

Còn với cố định Y ta sẽ luôn tìm được M sao cho khoảng cách các điểm đến cùng nhóm nhỏ nhất,bằng việc tính đạo hàm biểu thức 1 theo mjvà giải ta có thể thấy mj chính là giả trị trung bình của các phần tử thành phần (Bạn có thể dễ dàng nhận thấy trên Oxy hoặc 1 chút khó khăn hơn trên Oxyz).

Do em chưa tìm hiểu rõ cách thể hiện công thức toán học trên trang nên gặp phải một số lỗi hiển thị ạ! Link em để dưới đây sẽ biểu thị các công thức toán học một cách rõ ràng hơn ! ^^
https://docs.google.com/document/d/1wGJ9kF06r3AH8McYzC91li45KcrI9hnu6LeMlTiceU4/edit?usp=sharing

5 Likes

Em thấy trích dẫn vấn đề dễ hiểu, chỉ có vấn đề là công thức toán gây khó khăn cho người đọc mặc dù có link ở cuối cùng.

1 Like

Đồng quan điểm với Charlie, công thức toán học khá khó để theo dõi, hơn nữa kiểu đi thẳng vào vấn đề quá làm những người chưa tìm hiểu về phần này sẽ bị khó hiểu.

1 Like

Thế nên mới có mô tả một cách thuần toán hoặc một cách có lời mà :<