Giới thiệu EM
EM (Expectation-Maximization) là thuật toán tinh chỉnh lặp (iterative refinement) nổi tiếng để ước lượng tham số. Coi như mở rộng của mô hình k-means, gán đối tượng cho cụm gần nhất dựa trên trung bình cụm.
EM gán mỗi đối tượng cho cụm theo trọng số xác suất thành viên (probability of membership). Không có ranh giới cứng giữa cụm. Trung bình mới được tính dựa trên các đo lường có trọng số.
Quy trình EM
- Bước 1 - Khởi tạo: Đặt ước lượng ban đầu ("đoán") vector tham số mô hình hỗn hợp. Chọn ngẫu nhiên k đối tượng làm trung bình/tâm cụm (như k-means), đoán các tham số khác.
- Bước 2 - Lặp lại tinh chỉnh tham số/cụm qua 2 bước:
- (a) Bước Expectation (E-step): Gán mỗi đối tượng xᵢ cho cụm cₖ với xác suất:
P(xᵢ ∈ Cₖ) = p(Cₖ|xᵢ) = p(Cₖ)p(xᵢ|Cₖ) / p(xᵢ)
trong đó p(xᵢ|Cₖ) = N(mₖ, Eₖ(xᵢ)) tuân theo phân phối chuẩn (Gaussian) quanh mean mₖ, với kỳ vọng E₋. Tính xác suất thành viên cụm của xᵢ cho từng cụm → "expected" cluster memberships. - (b) Bước Maximization (M-step): Dùng ước lượng xác suất trên để ước lượng lại (tinh chỉnh) tham số mô hình. Ví dụ:
mₖ = (1/n) Σᵢ [ xᵢ P(xᵢ ∈ Cₖ) / Σⱼ P(xᵢ ∈ Cⱼ) ]
Đây là bước "maximization" của likelihood phân bổ cho trước dữ liệu.
- (a) Bước Expectation (E-step): Gán mỗi đối tượng xᵢ cho cụm cₖ với xác suất:
Đặc điểm
- Đơn giản, dễ triển khai.
- Hội tụ nhanh nhưng không đảm bảo tối ưu toàn cục (global optima). <
- Hội tụ đảm bảo cho dạng hàm tối ưu cụ thể.
- Độ phức tạp tính toán tuyến tính theo d (số đặc trưng đầu vào), n (số mục), t (số lặp).
AutoClass - Ứng dụng thực tế
Trong công nghiệp, AutoClass là kỹ thuật Bayesian clustering nổi tiếng dùng biến thể EM. Phân cụm tốt nhất tối đa hóa khả năng dự đoán thuộc tính đối tượng cho trước cụm chính xác của đối tượng. AutoClass cũng ước lượng số cụm. Đã dùng nhiều lĩnh vực, phát hiện lớp sao mới dựa trên dữ liệu thiên văn học hồng ngoại.