Mục lục 2 MỞ ĐẦU Thuật toán EM (Expectation- Maximization) được nghiên cứu từ năm 1958 bởi Hartley và được nghiên cứu đầy đủ bởi Dempster, Laird và Rubin công bố năm 1977. Thuật toán EM được sử dụng để tìm ra kỳ vọng tối đa các thông số một mô hình thống kê trong trường hợp các phương trình không thể giải quyết trực tiếp được. Thông thường các mô hình liên quan đến các giá trị tiềm ẩn ngoài không biết các thông số và dữ liệu không quan sát được thông số. Có nghĩa là những giá trị bị thiếu hoặc không quan sát được mô hình bằng sự giả định của các điểm dữ liệu bổ sung. (Ví dụ: một mô hình kết hợp đơn giản có thể được mô tả bằng cách giả định rằng mỗi điểm dữ liệu quan sát được có một điểm tương ứng với dữ liệu không quan sát được, hoặc biến tiềm ẩn, xác định thành phần hỗn hợp cho mỗi điểm dữ liệu.) Việc tìm kiếm một giải pháp hợp lý là lấy các dẫn xuất của các hàm hợp (likehood function) đối với các giá trị không rõ tức là các thông số và các biến tiềm ẩn đồng thời giải quyết các phương trình. Trong một mô hình thống kê với các biến tiềm ẩn thường là không thể. Thay vào đó, kết quả thường là một tập hợp các chương trình đan xem vào đó là giải pháp cho các giá trị của biến tiềm ẩn và ngược lại . Thuật toán EM nhằm tìm ra sự ước lượng về khả năng lớp nhất của các tham số trong mô hình xác suất( các mô hình phụ thuộc vào các biến tiềm ẩn chưa được quan sát), nó được xem như là thuật toán dựa trên mô hình hoặc là mở rộng của thuật toán k-means. EM gán các đối tượng của cụm đã cho theo xác suất phân phối thành phần của đối tượng đó. Phân phối xác suất thường được sửa dụng là phân phối xác suất Gaussian với mục đích là khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là hàm logarit khả năng của đối tượng dữ liệu, đây là hàm tốt để mô hình xác suất cho các đối tượng dữ liệu. 3 CHƯƠNG 1: CÁC KIẾN THỨC CƠ SỞ 1.1 .Hàm logarit Cho a là một số dương khác 1 và b là một số dương, số thực α thỏa mãn aα = b được gọi là lôgarit cơ số a của b và kí hiệu loga(b). 1.2 .Công thức xác suất Xác suất là các số trong khoảng [0,1], được gán tương ứng với một biến cố mà khả năng xảy ra hoặc không xảy ra là ngẫu nhiên. Kí hiệu: P(Z) Công thức sử dụng: P(A|B)= P(A). P(B/A)/ P(B) 1.3 .Entropy thông tin Entropy thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu. 1.4 .Gom cụm dữ liệu Gom cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thường mà chúng ta vẫn làm và thực hiện hằng ngày ví dụ như phân loại học sinh khá, giỏi trong lớp, phân loại đất đai, phân loại tài sản, phân loại sách trong thư viện…. Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các lớp/cụm. Các đối tượng trong cùng một cụm tương tự với nhau hơn so với đối tượng ở các cụm khác. Mục tiêu: Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Quá trình gom cụm dữ liệu Các yêu cầu tiêu biểu về việc gom cụm dữ liệu