Thuật toán EM (Kỳ vọng-Tối đa hóa) là một thuật toán sàng lọc lặp lại nổi tiếng có thể được sử dụng để khám phá các ước tính tham số. Nó có thể được coi là một phần mở rộng của mô hình k-mean, tạo ra một đối tượng cho cụm mà nó tương tự nhất, tùy thuộc vào ý nghĩa của cụm.
EM tạo từng đối tượng thành một cụm theo trọng số xác định xác suất thành viên. Nói cách khác, không có ranh giới nghiêm ngặt giữa các cụm. Do đó, các phương tiện mới được đánh giá dựa trên các thước đo có trọng số.
EM bắt đầu với một ước tính ban đầu hoặc "phỏng đoán" các tham số của mô hình kết hợp (được định nghĩa chung là vectơ tham số). Nó có thể thay đổi điểm theo các đối tượng lặp đi lặp lại trái ngược với mật độ hỗn hợp do vectơ tham số tạo ra. Các đối tượng thay đổi vị trí được sử dụng để khôi phục các ước tính tham số. Mỗi đối tượng đã tạo ra một xác suất mà nó có thể sở hữu một tập hợp các giá trị thuộc tính cụ thể cho rằng nó là một thành viên của một cụm nhất định. Thuật toán được biểu diễn như sau -
-
Nó có thể được sử dụng để phỏng đoán ban đầu của vectơ tham số - Điều này bao gồm việc chọn ngẫu nhiên k đối tượng để xác định các phương tiện hoặc trung tâm của cụm (như trong phân vùng k-mean) và đưa ra các phỏng đoán cho các tham số mới.
-
Nó có thể tinh chỉnh lặp lại các tham số (hoặc các cụm) tùy thuộc vào hai bước sau -
-
(a) Bước kỳ vọng - Nó có thể tạo từng đối tượng xi để phân cụm ck với xác suất
$$ P (x_ {i} \ epsilon C_ {k}) =p (C_ {k} | x_ {i}) =\ frac {p (C_ {k}) p (x_ {i} | C_ {k} )} {p (x_ {i})} $$
trong đó p (x i | C k ) =N (m k , E k (x i )) tuân theo phân phối chuẩn (tức là Gaussian) xung quanh giá trị trung bình, m k , với sự mong đợi, E k . Nói cách khác, bước này tính xác suất thành viên cụm của đối tượng x i , cho mỗi cụm. Các xác suất này là tư cách thành viên cụm “dự kiến” cho đối tượng x i .
-
(b) Bước tối đa hóa - Nó có thể cần các ước lượng xác suất từ trên để điều chỉnh lại (hoặc tinh chỉnh) các thông số mô hình. Ví dụ:
$$ m_ {k} =\ frac {1} {n} \ sum_ {i =1} ^ {n} \ frac {x_ {i} P (x_ {i} \ epsilon C_ {k})} {\ sum_ {j} P (x_ {i} \ epsilon C_ {j})} $$
Giai đoạn này là "tối đa hóa" khả năng phân bổ được cung cấp dữ liệu.
Thuật toán EM rất đơn giản và dễ hiểu để thực thi. Nó hội tụ nhanh chóng nhưng không thể đạt tới optima toàn cầu. Sự hội tụ được đảm bảo cho các dạng hàm tối ưu hóa cụ thể. Độ phức tạp tính toán là tuyến tính theo d (số lượng đặc tính đầu vào), n (số lượng mục) và t (số lượng dự phòng). Chúng thường được sử dụng trong cộng đồng thống kê.
Trong công nghiệp, AutoClass là một kỹ thuật phân nhóm Bayes nổi tiếng sử dụng việc sửa đổi thuật toán EM. Việc phân cụm tốt nhất tối đa hóa khả năng dự đoán các thuộc tính của một đối tượng với cụm chính xác của đối tượng. AutoClasscan cũng ước tính số lượng các cụm. Nó đã được sử dụng trong nhiều lĩnh vực khác nhau và có thể tìm thấy một lớp sao mới tùy thuộc vào dữ liệu thiên văn học hồng ngoại.