Thuật toán Phân cụm K-Means từ Gốc theo Phương pháp Lloyd
K-Means là thuật toán phân nhóm khách hàng, nén ảnh và phân đoạn dữ liệu phổ biến nhất. Hiểu cơ chế hội tụ của nó giúp kỹ sư chọn số cụm K tối ưu (Elbow Method).
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: numpy-broadcasting-matrix-norm.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu thuật toán phân cụm không giám sát K-Means lặp 2 bước của Lloyd:
- Bước 1 (Gán nhãn - Expectation): Gán mỗi điểm dữ liệu về tâm cụm (centroid) gần nhất theo khoảng cách Euclidean.
- Bước 2 (Cập nhật tâm - Maximization): Tính lại tọa độ tâm cụm bằng trung bình cộng các điểm thuộc cụm đó.
- Đo lường hàm mục tiêu quán tính (Inertia / WCSS - Within-Cluster Sum of Squares): ∑i=1N |xi - μci|2.
- Xử lý trường hợp biên: Cụm bị rỗng (empty cluster) bằng cách tái khởi tạo tâm cụm tại điểm dữ liệu xa nhất.
Mô tả bài toán
K-Means là thuật toán phân nhóm khách hàng, nén ảnh và phân đoạn dữ liệu phổ biến nhất. Hiểu cơ chế hội tụ của nó giúp kỹ sư chọn số cụm K tối ưu (Elbow Method).
Yêu cầu
Viết hàm kmeans_lloyd(X: np.ndarray, k: int, max_iters: int = 100, tol: float = 1e-4, seed: int = 42) -> dict[str, Any]:
- Khởi tạo tâm cụm: Dùng
np.random.RandomState(seed), chọn ngẫu nhiên k mẫu từ X làm k tâm cụm ban đầu. - Vòng lặp tối đa
max_iters: - Tính khoảng cách Euclidean từ mỗi điểm tới k tâm cụm bằng broadcasting: Dik = |xi - μk|.
- Gán nhãn cụm: labelsi = argmink Dik.
- Cập nhật tâm mới: Trung bình của các điểm cùng nhãn. Nếu một cụm không có điểm nào, gán tâm đó là điểm dữ liệu có khoảng cách xa nhất tới các tâm hiện tại.
- Kiểm tra hội tụ: Nếu độ dịch chuyển lớn nhất của các tâm max |μnew - μold| < tol, dừng vòng lặp sớm.
- Tính 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ó.
- Trả về dictionary:
{"centroids": np.ndarray, "labels": np.ndarray, "inertia": float, "n_iters": int}.
import numpy as np
from typing import Any
def kmeans_lloyd(X: np.ndarray, k: int, max_iters: int = 100, tol: float = 1e-4, seed: int = 42) -> dict[str, Any]:
passInput
- Hàm
kmeans_lloyd(X,k,max_iters,tol,seed): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Output
- Hàm
kmeans_lloyd: Trả về kết quả kiểudict[str, Any]theo đúng đặc tả kỹ thuật và kích thước quy định.
Ràng buộc
- Thời gian chạy tối đa: 3000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
X = np.array([[0.0, 0.0], [0.1, 0.0], [-0.1, 0.0], [10.0, 10.0], [10.1, 10.0], [9.9, 10.0]])
kmeans_lloyd(X, k=2, seed=42)Output
{
'centroids': [[ 0., 0.],
[10., 10.]],
'labels': [0, 0, 0, 1, 1, 1],
'inertia': 0.04,
'n_iters': 3
}Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Ví dụ 2
Input
X = np.random.randn(50, 3)
res1 = kmeans_lloyd(X, k=3, seed=123)
res2 = kmeans_lloyd(X, k=3, seed=123)Output
{
'centroids': [[ 1.6674, 0.1597, -0.0449],
[-0.3183, -0.8548, -0.1295],
[-0.1147, 1.0714, 0.1891]],
'labels': [1, 1, 2, 1, 2, 1, 2, 1, 1, 0, 0, 2, 2, 1, 0, 0, 2, 2, 1, 0, 2, 2, 1, 2, 1,
2, 1, 2, 1, 1, 2, 0, 2, 0, 2, 2, 0, 2, 2, 0, 2, 1, 0, 1, 2, 2, 0, 2, 1, 1],
'inertia': 97.639534,
'n_iters': 4
}Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.