Bài toán phân cụm và ứng dụng thực tế

Nói đến phân cụm, nếu tìm hiểu chúng ta sẽ hay gặp những bài toán phân loại khách hàng, phân đoan tị trường. Chúng hơi phức tại và khô khan. Tuy nhiên bản chất thì đúng là phân cụm. Để dễ tưởng tượng thì trong bài viết này ngoài 1 số điều mở đầu về phân cụm chúng ta sẽ tìm hiểu ý tưởng của thuật toán này qua bài toán thực tế đó là Tìm vị trí mở của hàng hợp lý.

Cùng bắt đầu nhé

Nội dung chính

Các tiêu chí để đáh giá chất lượng phân cụm tốt hay không

Chúng ta sẽ cần cân đối tất các các tiêu chí sau

+ Số cụm ít nhất

+ Các thành viên cụm có tính chất tương đồng nhất

+ Các cụm có thể được mô tả một cách rõ ràng

+ Các cụng khác nhau phải được phân biệt với nhau ở 1 hay 1 vài tiêu chí rõ nét

Các thuật toán phân cụm

Có 2 thuật toán phân cụm đó là phân cụm thứ bậc và không thứ bậc

Phân cụm thứ bậc

Có 2 hướng để phân cụm thứ bậc đó là tích tụ và phân chia. Ở đây mình sẽ nói đến phân cụm tích tụ.

+ Giả sử ban đầu có n quan sát (n điểm). Lần đầu tiên sẽ nhóm 2 điểm gần nhất thành 1 cụm. 1 cụm được đại diện bằng 1 tâm cụm, và sẽ dùng như 1 điểm tại bước tiếp theo. Như vậy lúc này coi như sẽ chỉ có n-1 điểm

+ Bước thứ 2 ta tiêp tục làm lặp lại, bước 3, 4,….. Chú ý rằng tâm mỗi cụm mới được tính là tâm của tất cả các điểm (dù là mới hay cũ trong cụm mới)

+ Như vậy sau n-1 bước ta sẽ thu được 1 cụm duy nhất. Cả quá trình sẽ được tóm tắt băng sơ đồ tích tụ dạng cành cây (Dendrogram). Sau này dựa vào đây ta có thể biết được nếu chia thành tất cả bao nhiêu cụm thì mỗi cụm gồm những phần tử nào. Đáp số cho cách phân cụm này là duy nhất.

Minh hoạ với bài toán phân cụm 8 điểm

Ta sẽ cần quyết định mở mây sửa hàng và đặt ở nhưng vị trí nào để khác hàng thuận tiện nhất

Bước 1: Nhóm các điểm 4+5

Bước 2: Nhóm các điểm 1+2

Bước 3: Nhóm các điểm 6+7

Bước 4: Nhóm các điểm 6+7 +8

Bước 5: Nhóm các điểm 4+5 +3

Bước 6: Nhóm các điểm 1+2 +3+4+5

Bước 7: Nhóm các điểm 1+2+3+4+5 và 6+7+8 vào 1 cụm. Lúc này tất cả các điểm đã ở cùng 1 cụm và thuật toán kết thúc.

Bây giờ nếu chia các điểm thành 2 cụm ta sẽ cắt theo đường màu xanh và được 2 cụm (1-2-3-4-5) và (6-7-8)

Nếu chia 3 cụm ta sẽ được các cụm là (1-2), (3-4-5) và (6-7-8)

Chia 4 cụm ta sẽ được các cụm là (1-2); (3); (4-5); (6-7-8)

Tương tự ta có thể chia cho đến khi 8 điểm về 8 cụm riêng biệt

Việc xác định khoảng cách để nhóm và tính tâm cụm cũng có nhiều phương pháp, xin phép không được đề cập tại đây

Phân cụm không thứ bậc (K-means)

Ý tưởng là ta sẽ quyết định trước số cụm (chính bằng K)

+ Ban đầu gán cho chúng 1 toạ độ bất kỳ.

+ Bước 1: Với n điểm ta tính khoảng cách đến k tâm cụm ấy. Khoảng cách đến tâm nào nhỏ nhất thì xếp nó vào cụm theo tâm ấy

+ Bước 2: Kết thúc bước này tính lại các tâm cụm theo các điểm nằm trong cụm

+ Tiếp theo ta lặp lại quy trình 2 bước trên đến khi tâm cụm và các phần tử trong mỗi cụm là không thay đổi nữa thì thuật toán kết thúc

Thuật toán vừa nêu sẽ được minh họa bằng bài toán rất thú vị bên dưới, cũng theo dõi tiếp nhé

Minh hoạ với bài toán mở của hàng Pizza

Phía dưới là vị trí của các khác hàng (đang minh hoạ trong không gian 2 chiều)

Bây giờ ta sẽ giải bài toán xem nên mở mấy cửa hàng để các khách hàng đến đó thuận tiện (gần nhất). và các cửa hàng đó sẽ đặt tại đâu

Bằng trực quan ta sẽ chia họ thành 3 cụm (tất nhiên viễc quyết định số cụm trên thực tế (với số lượng quan sát nhiều và trong không gian nhiều chiều hơn) thì không đơn giản như vậy nhé, và máy tính cũng sẽ không dùng trực quan như con người mà nó sẽ làm theo thuật toán được lập trình

Giả sử chia làm 3 nhóm (sẽ mở 3 của hàng)

Bước 1: Bắt đầu với 3 tâm cụm bất kỳ và chia nhóm cho chúng (sửa dụng 3 màu khác nhau)

3 tâm cụm ban đầu

Chia các điểm vào 3 cụm

Tính lại tâm cụm lần 1

Chia lại các điểm theo tâm cụm mới

Tiếp tực tính lại tâm các cụm lần 2

Chia lại các điểm

Tính lại tâm các cụm lần 3

Ok rồi. đến đây thì việc chia lại các điểm vào các nhóm sẽ không thay đổi kết quả nữa, và thuật toán kết thúc. Ta thu được các tâm cụm và thành viên các cụm.