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é
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.
Quyết định số cụm
Cùng với bài toán trên, nếu chia thành các cụm khác nhau ta sẽ thu được các kết quả khác nhau.
Vậy chọn số cụm sao cho hợp lý
Quyết định số cụm băng sơ đồ khuỷ tay
Bước 1: Ghi lại khoảng cách giữ 2 điểm xa nhất trong 1 cụm ở mỗi trường hợp phân cụm
Bước 2: Săp xếp chúng lên một đồ thị
Tại điểm mà khoảng cách này không còn giảm đáng kể (Các điểm trong 1 cụm đã khá tương đồng ) thì đó có thể là gợi ý về số cụm tốt nhất
Minh hoạ trong bài viết sử dụng từ Video của Luis Serrano tại đường dẫn: https://www.youtube.com/watch?v=QXOkPvFM6NU&ab_channel=LuisSerrano