Phân cụm K-means

Đặt vấn đề

Bạn được giao một tệp mười nghìn dòng, mỗi dòng là một khách hàng siêu thị kèm hai con số: số lần ghé mua trong năm và tổng tiền đã chi. Không cột nào nói khách này thuộc nhóm nào. Sếp hỏi một câu rất mở: khách hàng của ta chia thành mấy kiểu.

Đây không phải bài toán dự đoán, vì không ai đưa cho bạn đáp án đúng để so. Nếu chấm mười nghìn điểm ấy lên mặt phẳng, mắt bạn sẽ thấy vài đám tụ lại. Việc của thuật toán phân cụm là làm chính xác cái mà mắt bạn vừa làm, nhưng làm được cả khi dữ liệu có hai mươi chiều, tức là khi không thể vẽ ra để nhìn. Không có nhãn thì cũng không có đúng sai tuyệt đối, nên ta phải tự đặt ra một tiêu chí nội tại về thế nào là cách chia tốt rồi tối ưu chính tiêu chí đó.

Thử ngay: chạy K-means từng bước

K-means là thuật toán phân cụm phổ biến nhất: chọn trước số cụm K, đặt K điểm đại diện gọi là tâm cụm, rồi lặp hai việc, gán mỗi điểm về tâm gần nhất và dời mỗi tâm về giữa những điểm nó vừa nhận. Bấm nút để chạy K-means từng bước trên một tập điểm mẫu. Ba tâm cụm bắt đầu ở vị trí lệch, và bạn sẽ thấy chúng dịch dần về giữa ba đám điểm sau vài vòng. Xem hết một lượt rồi, bạn hãy đổi số cụm K, bấm khởi tạo lại tâm, hoặc bấm thẳng vào khung để thêm và bớt điểm, sau đó chạy lại: đó là cách nhanh nhất để thấy chọn sai K hoặc khởi tạo xui thì cụm xấu đi thế nào.

K-means chạy từng bướcVòng 0

Số cụm K23 (mặc định)45

Tâm khởi tạo

số điểm: 15độ chặt cụm: chưa gán

Ba tâm cụm đặt ở vị trí ban đầu. Bấm để gán mỗi điểm vào tâm gần nhất.

Bấm vào khung để thêm điểm, bấm trúng một điểm để xoá nó. Đổi K hoặc tâm khởi tạo rồi chạy lại: độ chặt cụm càng nhỏ thì cách chia càng gọn, nhưng K càng lớn thì con số này luôn giảm, nên đừng chỉ nhìn nó mà chọn K.

Ý tưởng cốt lõi

Cho đến giờ ta chủ yếu nói về học có giám sát: máy nhận đầu vào và một nhãn đúng đi kèm, rồi học cách dự đoán nhãn cho dữ liệu mới. Nhưng nhãn không phải lúc nào cũng có. Dán nhãn rất tốn kém, ví dụ để dán nhãn một triệu ảnh y học cần hàng nghìn giờ làm việc của bác sĩ.

Trong nhiều bài toán, câu hỏi không phải là "điểm này thuộc nhóm A hay nhóm B", mà là một câu hỏi mở hơn: "dữ liệu của tôi có cấu trúc nội tại gì". Đó chính là địa hạt của học không giám sát, và phân cụm là đại diện tiêu biểu nhất.

Phân cụm nghĩa là chia một tập điểm dữ liệu không có nhãn thành các nhóm gọi là cụm, sao cho:

• Các điểm trong cùng một cụm thì giống nhau, gần nhau.
• Các điểm ở những cụm khác nhau thì khác biệt, xa nhau.

Một ví dụ kinh điển là phân khúc khách hàng. Bạn có dữ liệu hành vi mua sắm của hàng nghìn khách hàng, mỗi khách được mô tả bằng nhiều con số như số lần mua, số tiền chi, danh mục yêu thích. Không ai gán sẵn nhãn "khách nhóm 1, khách nhóm 2". Máy phải tự khám phá xem khách hàng tự nhiên chia thành mấy nhóm và mỗi nhóm có đặc điểm gì.

K-means là thuật toán phân cụm nổi tiếng và đơn giản nhất. Tư tưởng của nó dựa trên khái niệm tâm cụm, là một điểm đại diện cho trung tâm của mỗi cụm. Ta chọn trước số cụm cần tìm, gọi là K, rồi để thuật toán tự sắp xếp các điểm quanh K cái tâm đó.

Khoảng cách giữa hai điểm

Để nói hai điểm "gần nhau" ta cần một thước đo khoảng cách. Thước đo phổ biến nhất là khoảng cách Euclid, tức khoảng cách thẳng theo đường chim bay. Với hai điểm trong mặt phẳng hai chiều có tọa độ (x1, y1) và (x2, y2), bình phương khoảng cách giữa chúng được tính bằng:

khoang_cach = (x1 - x2)**2 + (y1 - y2)**2

Ở đây ta thường làm việc với bình phương khoảng cách để khỏi phải lấy căn bậc hai. Việc bỏ căn không làm thay đổi thứ tự gần xa giữa các điểm, nên khi chỉ cần tìm tâm gần nhất thì so sánh bình phương khoảng cách là đủ và lại nhanh hơn.

Thuật toán K-means theo từng bước

K-means hoạt động như một vòng lặp gồm hai bước luân phiên nhau cho đến khi mọi thứ ổn định.

Bước 0, khởi tạo. Chọn K điểm làm tâm cụm ban đầu. Cách đơn giản nhất là lấy ngẫu nhiên K điểm trong dữ liệu.

Bước 1, gán điểm. Với mỗi điểm dữ liệu, tính khoảng cách từ nó tới tất cả K tâm, rồi gán điểm đó vào cụm có tâm gần nhất. Bước này được gọi là bước gán.

Bước 2, cập nhật tâm. Sau khi mọi điểm đã được gán, tính lại vị trí từng tâm bằng cách lấy trung bình tọa độ của tất cả các điểm thuộc cụm đó. Tâm mới chính là điểm chính giữa của cụm. Bước này gọi là bước cập nhật.

Bước 3, kiểm tra dừng. Quay lại bước 1 và lặp tiếp. Khi các tâm gần như không còn di chuyển nữa, hoặc không có điểm nào đổi cụm so với vòng trước, thuật toán dừng lại.

Trực giác của vòng lặp này khá đẹp. Bước gán kéo mỗi điểm về với tâm gần nó nhất. Bước cập nhật lại kéo mỗi tâm về đúng giữa đám điểm đang theo nó. Hai lực kéo qua lại này dần dần làm các cụm gọn lại và các tâm ổn định.

Chạy tay một vòng K-means

Lấy bốn điểm trên một trục số cho gọn: 1, 2, 8, 9. Đặt K = 2 và khởi tạo hai tâm ở vị trí xấu: t1 = 1 và t2 = 2.

Vòng 1, bước gán. Điểm 1 vào cụm 1. Điểm 2 vào cụm 2. Điểm 8 cách t1 là 7 và cách t2 là 6 nên vào cụm 2. Điểm 9 cũng vào cụm 2. Bước cập nhật: tâm cụm 1 vẫn là 1, tâm cụm 2 là trung bình của {2, 8, 9}, tức 19/3 xấp xỉ 6.33.

Vòng 2, bước gán. Điểm 2 giờ cách t1 là 1 nhưng cách t2 tới 4.33, nên nó nhảy sang cụm 1. Cụm 1 thành {1, 2}, cụm 2 thành {8, 9}. Bước cập nhật cho tâm 1.5 và 8.5.

Vòng 3: không điểm nào đổi cụm nữa, thuật toán dừng, inertia cuối bằng 1.0. Dù khởi tạo lệch hẳn, hai lực kéo qua lại vẫn tự chỉnh về lời giải hợp lý sau vài vòng, và nó dừng vì cách gán lặp lại chính nó chứ không phải vì ta ép nó dừng.

Hàm mục tiêu: tổng bình phương khoảng cách

K-means không chạy lung tung mà thực ra đang tối ưu hóa một đại lượng cụ thể. Đại lượng đó là tổng bình phương khoảng cách từ mỗi điểm tới tâm cụm của nó. Người ta gọi nó là inertia, hay tổng bình phương trong cụm.

Bằng lời, ta cộng dồn: với mỗi cụm, lấy từng điểm trong cụm, tính bình phương khoảng cách từ điểm đó tới tâm cụm, rồi cộng tất cả lại qua mọi điểm và mọi cụm. Con số tổng này càng nhỏ thì các cụm càng chặt, vì điểm nằm sát tâm của mình.

Điều thú vị là cả hai bước của K-means đều không bao giờ làm tăng inertia.

• Bước gán đưa mỗi điểm về tâm gần nhất, tức là chọn lựa chọn nhỏ nhất, nên tổng khoảng cách không thể tăng.
• Bước cập nhật đặt tâm vào trung bình cụm. Có thể chứng minh rằng trung bình cộng chính là điểm làm tổng bình phương khoảng cách trong cụm nhỏ nhất, nên bước này cũng không làm inertia tăng.

Vì inertia luôn không âm và mỗi vòng lặp đều khiến nó giảm hoặc giữ nguyên, thuật toán chắc chắn hội tụ sau hữu hạn bước. Lập luận chặt hơn: số cách gán n điểm vào K cụm là hữu hạn, mà mỗi vòng inertia không tăng, nên không thể giảm mãi và cũng không thể quay vòng qua các trạng thái cũ. Tuy nhiên cần lưu ý nó chỉ hội tụ về một cực tiểu địa phương, không nhất thiết là lời giải tốt nhất tuyệt đối. Khởi tạo khác nhau có thể dẫn tới kết quả cụm khác nhau, nên trong thực tế người ta thường chạy K-means nhiều lần với khởi tạo khác nhau rồi giữ lần có inertia nhỏ nhất.

Cách chọn số cụm K

K-means buộc ta phải biết trước số cụm K, nhưng đời thực thường không cho ta biết con số đó. Một cách phổ biến để dò K là phương pháp khuỷu tay, tiếng Anh là elbow method.

Ý tưởng như sau. Ta chạy K-means lần lượt với K = 1, 2, 3, ... cho tới một giá trị tối đa. Với mỗi K ta ghi lại inertia thu được, rồi vẽ đồ thị inertia theo K. Khi K còn nhỏ, tăng K thêm một đơn vị làm inertia giảm rất mạnh. Khi K đã đủ lớn, tăng thêm gần như không giúp inertia giảm thêm bao nhiêu. Điểm gãy của đường cong, trông giống khuỷu tay, chính là giá trị K hợp lý để chọn.

Phương pháp khuỷu tay đơn giản nhưng không phải lúc nào cũng rõ ràng, vì có những đường cong rất mượt không lộ ra khuỷu tay nào. Khi đó người ta dùng thêm các thước đo chất lượng cụm khác như hệ số silhouette để chọn K một cách khách quan hơn.

Một điều bắt buộc phải hiểu: inertia luôn giảm khi K tăng, và bằng đúng 0 khi K bằng số điểm dữ liệu, vì khi ấy mỗi điểm là tâm của chính nó. Cho nên không bao giờ được chọn K bằng cách lấy K có inertia nhỏ nhất. Khuỷu tay tìm điểm mà thêm một cụm nữa không còn đáng, chứ không tìm giá trị nhỏ nhất.

Hệ số bóng (silhouette)

Hệ số bóng chấm điểm từng điểm dữ liệu bằng cách so hai đại lượng. Gọi a là khoảng cách trung bình từ điểm đó tới các điểm khác trong cùng cụm, b là khoảng cách trung bình tới các điểm của cụm gần nhất mà nó không thuộc về. Hệ số bóng là hiệu b - a chia cho số lớn hơn trong hai số a và b.

Gần 1 nghĩa là điểm nằm sâu trong cụm của mình. Gần 0 nghĩa là nó nằm ngay ranh giới. Âm nghĩa là nó còn gần cụm hàng xóm hơn cụm của chính nó, nhiều khả năng bị gán nhầm. Trung bình hệ số bóng không đơn điệu theo K nên nó có cực đại thật sự, dùng để chọn K khách quan hơn khuỷu tay. Dù vậy không thước đo nào thay được kiến thức lĩnh vực: nếu marketing chỉ chăm sóc nổi bốn nhóm khách, K bằng 4 là câu trả lời đúng.

Khởi tạo và K-means++

Giả sử dữ liệu có ba đám tách bạch, nhưng khởi tạo ngẫu nhiên cho hai tâm rơi vào cùng một đám, còn đám thứ ba không có tâm nào gần. Bước gán sẽ chẻ đôi đám thứ nhất thành hai cụm giả, đồng thời nhét hai đám còn lại vào chung một cụm. Từ trạng thái ấy, không bước đơn lẻ nào kéo được một tâm băng qua khoảng trống về đám bị bỏ rơi: thuật toán vẫn báo đã hội tụ, nhưng cách chia sai hẳn cấu trúc thật.

Cách chữa thứ nhất là chạy lại nhiều lần rồi giữ lần cho inertia nhỏ nhất. Cách thứ hai là K-means++: chọn tâm đầu ngẫu nhiên, rồi chọn từng tâm tiếp theo với xác suất tỉ lệ thuận với bình phương khoảng cách từ điểm đó tới tâm gần nhất đã chọn. Điểm nào nằm xa mọi tâm hiện có thì càng dễ được chọn, nhờ vậy các tâm khởi tạo rải đều. K-means++ thường cho inertia cuối thấp hơn và hội tụ sau ít vòng hơn, nên nó là mặc định trong các thư viện thông dụng.

Thang đo đặc trưng ảnh hưởng thế nào

Đây là cái bẫy im lặng: chương trình vẫn chạy, vẫn ra kết quả, chỉ có điều kết quả vô nghĩa. Xét dữ liệu khách hàng với số lần mua trong năm (từ 1 tới 50) và tổng chi tiêu tính bằng đồng (tới vài chục triệu). Chênh lệch số lần mua tối đa là 49, bình phương lên khoảng 2400, trong khi chênh lệch tiền bình phương lên là con số khổng lồ. Kết quả: K-means gần như chỉ phân cụm theo tiền, còn số lần mua bị vô hiệu hóa. Cách chữa là chuẩn hóa mọi đặc trưng về cùng thang đo trước khi phân cụm.

Khi nào K-means hỏng

Mọi kiểu hỏng của K-means đều truy về cùng một gốc: nó giả định mỗi cụm là một quả cầu quây quanh một tâm, các quả cầu cỡ gần bằng nhau.

Cụm dài thuôn. Nếu hai cụm thật là hai dải song song kéo dài, một điểm ở đầu xa của dải này có thể nằm gần tâm dải kia hơn tâm của chính mình, nên K-means cắt ngang hai dải dù mắt người thấy cấu trúc rõ mồn một.

Cụm lồng nhau. Kinh điển nhất là hai vòng tròn đồng tâm. Cả hai có chung tâm hình học nên khái niệm tâm cụm mất ý nghĩa phân biệt, và K-means sẽ chia đôi bức tranh bằng một đường thẳng cắt ngang cả hai vòng.

Cụm chênh lệch mật độ. Vì bước cập nhật lấy trung bình, một cụm rất đông và trải rộng sẽ hút tâm về phía nó, lấn sang lãnh thổ cụm nhỏ bên cạnh. Với các tình huống trên, hoặc ta biến đổi dữ liệu sang không gian khác để cụm tròn hơn, hoặc đổi sang phân cụm theo mật độ, phân cụm phân cấp, hoặc mô hình hỗn hợp Gauss.

Ứng dụng thực tế

Ngoài phân khúc khách hàng, K-means còn dùng để nén ảnh theo bảng màu: coi mỗi điểm ảnh là một điểm trong không gian ba chiều đỏ, xanh lá, xanh dương, chạy K-means với K bằng 16 rồi thay mỗi điểm ảnh bằng màu tâm cụm gần nhất. Nó cũng dùng để gom nhóm văn bản phát hiện chủ đề, và để phát hiện bất thường sơ bộ vì điểm nằm xa tâm cụm bất thường là ứng viên đáng ngờ.

Hạn chế của K-means

K-means rất nhanh và đơn giản, nhưng nó không phải là chìa khóa vạn năng. Cần ghi nhớ vài hạn chế quan trọng.

• Phải biết trước số cụm K, trong khi nhiều bài toán không cho ta biết.
• Nó ngầm giả định các cụm có dạng tròn, kích thước gần bằng nhau. Khi cụm có dạng dài thuôn, mật độ khác nhau, hay hình dạng cong phức tạp, K-means dễ chia sai.
• Nó nhạy với điểm ngoại lai. Một vài điểm lạc loài quá xa có thể kéo lệch tâm cụm vì tâm được tính bằng trung bình.
• Kết quả phụ thuộc vào khởi tạo. Một lần chạy có thể rơi vào cực tiểu địa phương tệ, nên cần chạy nhiều lần.
• Nó phụ thuộc nhiều vào tiền xử lý. Nếu các đặc trưng có thang đo khác nhau quá lớn, đặc trưng số lớn sẽ áp đảo khoảng cách. Vì vậy thường phải chuẩn hóa dữ liệu trước.

Khi dữ liệu có hình dạng kỳ lạ hoặc nhiều nhiễu, người ta chuyển sang các thuật toán khác như phân cụm theo mật độ, nhưng đó là câu chuyện cho một bài học khác.

Hiểu nhầm thường gặp

• Tưởng K-means tìm ra cách chia tốt nhất. Nó chỉ hội tụ về một cực tiểu địa phương của inertia. Đổi khởi tạo là đổi kết quả, nên phải chạy nhiều lần hoặc dùng K-means++.
• Tưởng inertia nhỏ hơn thì phân cụm tốt hơn, kể cả khi K khác nhau. Inertia luôn giảm khi K tăng, tới 0 khi mỗi điểm là một cụm. So sánh inertia chỉ có nghĩa giữa các lần chạy cùng K.
• Tưởng các cụm tìm ra là nhóm có thật trong tự nhiên. K-means luôn trả về đúng K cụm, kể cả khi dữ liệu vốn không có cấu trúc nhóm nào. Chia được không có nghĩa là đáng chia.
• Nhầm tâm cụm với một điểm dữ liệu thật. Tâm là trung bình cộng, thường không trùng điểm nào trong dữ liệu. Muốn tâm là điểm thật thì phải dùng K-medoids.

Mã nguồn Python

Đoạn mã dưới đây tự cài đặt K-means trên vài điểm hai chiều, chỉ dùng list thuần Python, không cần thư viện ngoài. Chương trình in ra vị trí các tâm cụm và inertia sau mỗi vòng lặp, kèm điều kiện dừng khi tâm không còn đổi.

# K-means tu cai dat tren cac diem 2 chieu, chi dung list thuan

# Du lieu: moi diem la mot cap (x, y)
diem = [
    (1.0, 1.0), (1.5, 2.0), (1.0, 0.5),
    (8.0, 8.0), (9.0, 8.5), (8.5, 9.0),
    (4.0, 5.0), (5.0, 4.5), (4.5, 5.5),
]

K = 3                     # so cum can tim
so_vong = 5               # so vong lap toi da

# Khoi tao tam ban dau bang K diem dau tien (don gian, de tai lap)
tam = [diem[0], diem[3], diem[6]]


def binh_phuong_khoang_cach(a, b):
    # tra ve binh phuong khoang cach Euclid giua hai diem 2 chieu
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


def tam_gan_nhat(p, danh_sach_tam):
    # tra ve chi so cua tam gan diem p nhat
    chi_so_tot = 0
    kc_nho_nhat = binh_phuong_khoang_cach(p, danh_sach_tam[0])
    for k in range(1, len(danh_sach_tam)):
        kc = binh_phuong_khoang_cach(p, danh_sach_tam[k])
        if kc < kc_nho_nhat:
            kc_nho_nhat = kc
            chi_so_tot = k
    return chi_so_tot


def tinh_inertia(diem, nhan, tam):
    # tong binh phuong khoang cach tu moi diem toi tam cum cua no
    tong = 0.0
    for i in range(len(diem)):
        tong += binh_phuong_khoang_cach(diem[i], tam[nhan[i]])
    return tong


for vong in range(so_vong):
    # Buoc 1: gan moi diem vao cum co tam gan nhat
    nhan = []
    for p in diem:
        nhan.append(tam_gan_nhat(p, tam))

    # Buoc 2: cap nhat tam = trung binh cac diem trong cum
    tam_moi = []
    for k in range(K):
        tong_x = 0.0
        tong_y = 0.0
        dem = 0
        for i in range(len(diem)):
            if nhan[i] == k:
                tong_x += diem[i][0]
                tong_y += diem[i][1]
                dem += 1
        if dem > 0:
            tam_moi.append((tong_x / dem, tong_y / dem))
        else:
            tam_moi.append(tam[k])   # cum rong thi giu nguyen tam cu

    # In tam va inertia cua vong nay
    inertia = tinh_inertia(diem, nhan, tam_moi)
    print("Vong", vong + 1, "tam:", tam_moi)
    print("        inertia =", round(inertia, 3))

    # Kiem tra dung: neu tam khong doi thi thoi
    if tam_moi == tam:
        print("Da hoi tu, dung lai.")
        break
    tam = tam_moi

Chạy đoạn mã trên, kết quả in ra đúng như sau:

Vong 1 tam: [(1.1666666666666667, 1.1666666666666667), (8.5, 8.5), (4.5, 5.0)]
        inertia = 3.333
Vong 2 tam: [(1.1666666666666667, 1.1666666666666667), (8.5, 8.5), (4.5, 5.0)]
        inertia = 3.333
Da hoi tu, dung lai.

Ba tâm rơi đúng vào ba cụm tự nhiên của dữ liệu, một cụm ở góc dưới trái, một cụm ở góc trên phải và một cụm ở giữa. Đừng vội thất vọng vì inertia không giảm: chính vì tam = [diem[0], diem[3], diem[6]] lấy mỗi điểm từ một cụm khác nhau nên bước gán ở vòng 1 đã chia đúng ngay, không vòng nào sau đó còn gì để sửa. Vòng 2 lặp lại y hệt vòng 1, tâm không đổi nên thuật toán dừng. Đây là minh họa sống cho điều mục khởi tạo đã nói: khởi tạo tốt thì K-means hội tụ gần như tức thì. Muốn thấy inertia thật sự giảm qua nhiều vòng, hãy làm bài tập 2 dưới đây, đổi tâm khởi tạo thành ba điểm nằm sát nhau trong cùng một cụm.

Bài tập thực hành

Bài 1. Thêm dòng in ra danh sách nhãn cụm của từng điểm sau mỗi vòng lặp, để quan sát xem điểm nào đổi cụm và ở vòng nào thì không còn điểm nào đổi cụm nữa.

Gợi ý

Bạn đã có biến nhan chứa chỉ số cụm của mỗi điểm. Chỉ cần thêm một dòng print(" nhan:", nhan) ngay sau khi tính xong nhan trong vòng lặp. Khi nhan của hai vòng liên tiếp giống hệt nhau thì thuật toán thực chất đã hội tụ.

Bài 2. Thay tâm khởi tạo bằng ba điểm khác trong dữ liệu, ví dụ ba điểm đầu tiên diem[0], diem[1], diem[2]. Chạy lại và so sánh tâm cuối cùng cùng inertia cuối với lần khởi tạo ban đầu. Khởi tạo có làm thay đổi kết quả không.

Gợi ý

Đổi dòng tam = [diem[0], diem[3], diem[6]] thành tổ hợp điểm khác. Vì cả ba điểm đầu nằm sát nhau trong cùng một vùng, khởi tạo này thường cho cực tiểu địa phương tệ hơn, inertia cuối lớn hơn. Đây là minh chứng trực quan cho việc K-means phụ thuộc vào khởi tạo và vì sao nên chạy nhiều lần.

Bài 3. Viết một hàm thử lần lượt K = 1, 2, 3, 4 rồi in ra inertia cuối ứng với mỗi K. Quan sát inertia giảm thế nào khi K tăng và thử nhận ra khuỷu tay.

Gợi ý

Bọc toàn bộ vòng lặp K-means vào một hàm nhận tham số K và trả về inertia cuối cùng. Cách khởi tạo ở đây quyết định kết quả, nên đừng chỉ lấy K điểm đầu danh sách: làm vậy với K bằng 2 và K bằng 3 bạn sẽ rơi vào cùng một cực tiểu địa phương tệ và khuỷu tay không hiện ra. Hãy làm đúng điều mục khởi tạo đã khuyên, tức với mỗi K thì thử nhiều bộ tâm khởi tạo khác nhau rồi chỉ giữ lại inertia nhỏ nhất. Dữ liệu chỉ có 9 điểm nên bạn duyệt được hết mọi tổ hợp K điểm bằng itertools.combinations(diem, K). Khi đó kết quả là K=1: 164.944, K=2: 42.042, K=3: 3.333, K=4: 2.125. Inertia giảm rất mạnh từ K bằng 1 tới K bằng 3, rồi từ K bằng 3 sang K bằng 4 gần như không giảm thêm bao nhiêu, đó chính là dấu hiệu khuỷu tay ở K bằng 3, khớp với ba cụm tự nhiên trong dữ liệu.

Tự kiểm tra

Câu 1. Trong K-means, bước cập nhật đặt mỗi tâm cụm vào đâu, và vì sao lựa chọn đó không làm tăng inertia.

Đáp án

Bước cập nhật đặt tâm vào trung bình tọa độ của tất cả các điểm thuộc cụm, tức điểm chính giữa của cụm. Trung bình cộng chính là điểm làm tổng bình phương khoảng cách tới các điểm trong cụm nhỏ nhất, nên thay tâm cũ bằng trung bình chỉ có thể làm inertia giảm hoặc giữ nguyên, không bao giờ tăng.

Câu 2. Vì sao K-means thường thất bại khi các cụm có dạng dài thuôn hoặc hình cong, dù dữ liệu rõ ràng có cấu trúc nhóm.

Đáp án

K-means gán điểm theo khoảng cách Euclid tới tâm, nên nó ngầm coi mỗi cụm là một vùng tròn quây quanh một điểm trung tâm. Với cụm dài thuôn hay cong, một điểm ở đầu cụm này có thể gần tâm cụm khác hơn tâm cụm của chính nó, khiến thuật toán chia ranh giới sai. Khi đó cần các phương pháp dựa trên mật độ hoặc hình dạng thay vì dựa trên khoảng cách tới tâm.

Câu 3. Một bạn chọn K bằng cách chạy K-means với K từ 1 tới 50 rồi lấy K cho inertia nhỏ nhất. Sai lầm ở đâu, và nên làm gì thay thế.

Đáp án

Inertia luôn giảm khi K tăng, và bằng đúng 0 khi K bằng số điểm dữ liệu vì mỗi điểm trở thành tâm của chính nó. Tiêu chí "lấy K cho inertia nhỏ nhất" vì thế luôn dẫn tới K lớn nhất được thử, một đáp án vô nghĩa. Thay vào đó nên dùng phương pháp khuỷu tay, hoặc dùng trung bình hệ số bóng vốn không đơn điệu theo K nên có cực đại thật sự, và luôn đối chiếu với ràng buộc nghiệp vụ.

Câu hỏi tự kiểm

Kiểm tra nhanh: phân cụm K-means0/4 đúngchưa trả lời

1. 1K-means hội tụ về đâu, và điều đó phụ thuộc gì?
2. 2Vì sao không được chọn số cụm K bằng cách lấy K cho inertia nhỏ nhất?
3. 3K-means thường chia sai khi gặp hai vòng tròn đồng tâm hoặc cụm dài thuôn. Gốc rễ là do đâu?
4. 4Dữ liệu có số lần mua (1 tới 50) và tổng chi tiêu (tới vài chục triệu đồng). Nếu không xử lý gì, K-means sẽ ra sao?

Tóm tắt

K-means nhận dữ liệu không nhãn và tự tìm cấu trúc nhóm. Vì không có nhãn đúng để so, ta tự đặt tiêu chí là inertia, tổng bình phương khoảng cách từ mỗi điểm tới tâm cụm của nó. Thuật toán lặp hai bước, gán điểm về tâm gần nhất rồi dời tâm về trung bình cụm. Không bước nào làm inertia tăng và số cách gán là hữu hạn, nên nó chắc chắn dừng, nhưng chỉ dừng ở một cực tiểu địa phương.

Ba quyết định của người dùng ảnh hưởng tới kết quả nhiều hơn bản thân thuật toán: chọn K, chuẩn hóa đặc trưng, và hiểu giả định. K-means coi cụm là những quả cầu cỡ tương đương nên nó hỏng trước cụm dài thuôn, cụm lồng nhau, cụm chênh mật độ và trước ngoại lai.

Ghi nhớ

K-means lặp hai bước: gán mỗi điểm vào tâm gần nhất, rồi dời tâm về trung bình của cụm. Nó tối thiểu hóa inertia, tức tổng bình phương khoảng cách từ điểm tới tâm cụm của mình. Mỗi vòng inertia không bao giờ tăng nên thuật toán hội tụ, nhưng chỉ về cực tiểu địa phương. Số cụm K phải chọn trước, thường dò bằng phương pháp khuỷu tay. K-means nhanh và đơn giản nhưng giả định cụm tròn đều, nhạy với ngoại lai và phụ thuộc khởi tạo cùng cách chuẩn hóa dữ liệu.