Quán tính

Thuộc phần Học không giám sát trong hành trình Machine Learning của Coddy. Bài học 6 trên 51.

Chương này nói về cách chọn k. Kết thúc chương, bạn sẽ chọn k cho các chuyến giao hàng của một tiệm bánh và phân vùng:

Bản đồ các điểm giao hàng trong thành phố, hướng đông theo km trên trục ngang và hướng bắc theo mét trên trục dọc, chia thành ba vùng có lần lượt 45, 40 và 25 điểm giao hàng, mỗi vùng có một ngôi sao màu đen ở giữa

Trước tiên, hãy xét điểm số. Inertia cộng bình phương khoảng cách từ mỗi điểm đến tâm của nhóm chứa điểm đó: giá trị nhỏ khi các điểm nằm sát tâm nhóm.

36 quả táo được chia thành ba nhóm, mỗi quả nối với tâm hình ngôi sao màu đen của nhóm bằng một đoạn thẳng màu xám mảnh. Inertia bình phương độ dài của từng đoạn thẳng rồi cộng tất cả lại

KMeans lưu giá trị này trong inertia_. Với 180 quả táo:

for k in [1, 2, 3, 4]:
    km = KMeans(n_clusters=k, n_init=10, random_state=0)
    km.fit(X)
    print(k, round(km.inertia_))

Kết quả in ra là:

Nhiều tâm hơn, các nhánh ngắn hơn: quán tính luôn giảm khi k tăng. Khi mỗi điểm có một tâm riêng, quán tính bằng 0, nên nhỏ nhất không phải là tốt nhất.

Thử thách

Dễ

Một xưởng gốm đóng bình vào các hộp có một vài kích cỡ. Mỗi chiếc bình được xếp vào kích cỡ gần nhất; inertia đo mức độ không vừa khít. Chương trình đọc budget, mức độ không vừa khít tối đa mà xưởng gốm chấp nhận.

Thử k = 1, 2, 3, cứ thế tiếp tục: huấn luyện KMeans trên vases và in inertia của từng k sau khi làm tròn.
Dừng ở k đầu tiên có inertia nằm trong ngân sách, rồi in k đó.

Với một xưởng gốm khác:

k = 1, inertia 15120
k = 2, inertia 4811
k = 3, inertia 1290
Box sizes needed: 3

Tự làm thử

import numpy as np
from sklearn.cluster import KMeans

# Đừng thay đổi các dòng bên dưới
rng = np.random.default_rng(8)
# Bốn loại bình: chiều cao và chiều rộng điển hình tính bằng cm, cùng số lượng mỗi loại
kinds = [(15, 8, 25), (38, 13, 25), (22, 22, 20), (58, 26, 10)]
parts = []
for h, w, n in kinds:
    parts.append(np.column_stack([rng.normal(h, 2.5, n), rng.normal(w, 2, n)]))
# 80 chiếc bình, mỗi hàng là một chiếc: chiều cao và chiều rộng tính bằng cm
vases = np.round(np.concatenate(parts), 1)

# Mức sai lệch tối đa mà xưởng gốm chấp nhận, tính theo inertia
budget = int(input())

# Viết code của bạn bên dưới