Bài giảng Thuật toán K-Mean và ứng dụng - Trần Nam Khánh

Nội dung text: Bài giảng Thuật toán K-Mean và ứng dụng - Trần Nam Khánh

1. THUẬT TOÁN K-MEAN K - VÀ ỨNG DỤNG và Mean ứ ng dung ng 1 GVHD: CN.Trần Nam Khánh SV: Phạm Huyền Trang Lớp: K52CA
2. NỘI DUNG CHÍNH I. Phân cụm K - Mean và và Mean II. Thuật toán K-Mean 1. Khái quát về thuật toán ứ ng dung ng 2. Các bước của thuật toán 3. Ví dụ minh họa – Demo thuật toán 4. Đánh giá thuật toán 5. Tổng quát hóa và Các biến thể III. Ứng dụng của thuật toán K-Mean 2
3. I. PHÂN CỤM 1. Phân cụm là gì? ➢ Quá trình phân chia 1 tập dữ liệu ban đầu thành các cụm K - dữ liệu thỏa mãn: và Mean ➢ Các đối tượng trong 1 cụm “tương tự” nhau. ứ ng dung ng ➢ Các đối tượng khác cụm thì “không tương tự” nhau. ➢ Giải quyết vấn đề tìm kiếm, phát hiện các cụm, các mẫu dữ liệu trong 1 tập hợp ban đầu các dữ liệu không có nhãn. 3
4. I. PHÂN CỤM K - Mean và và Mean ứ ng dung ng Nếu X : 1 tập các điểm dữ liệu Ci : cụm thứ i X = C1   Ck Cngoại lai Ci  Cj =  4
5. I. PHÂN CỤM 2. Một số độ đo trong phân cụm  Minkowski K - n 1 và Mean p p (||xyii− || ) i=1 ứ ng dung ng  Euclidean – p = 2  Độ đo tương tự (gần nhau): cosin hai vectơ v.w cosµ = ||v ||.|| w || 5
6. I. PHÂN CỤM 3. Mục đích của phân cụm K - Mean và và Mean ➢ Xác định được bản chất của việc nhóm các đối tượng trong 1 tập dữ liệu không có nhãn. ứ ng dung ng ➢ Phân cụm không dựa trên 1 tiêu chuẩn chung nào, mà dựa vào tiêu chí mà người dùng cung cấp trong từng trường hợp. 6
7. I. PHÂN CỤM 5. Một số phương pháp phân cụm điển hình  Phân cụm phân hoạch K - Mean và và Mean  Phân cụm phân cấp ứ ng dung ng  Phân cụm dựa trên mật độ  Phân cụm dựa trên lưới  Phân cụm dựa trên mô hình  Phân cụm có ràng buộc 7
8. II.PHÂN CỤM PHÂN HOẠCH Phân 1 tập dữ liệu có n phần tử cho trước thành k tập con dữ liệu (k ≤ n), mỗi tập con biểu diễn 1 cụm. K - Các cụm hình thành trên cơ sở làm tối ưu giá trị hàm đo và Mean độ tương tự sao cho: ứ ng dung ng  Các đối tượng trong 1 cụm là tương tự.  Các đối tượng trong các cụm khác nhau là không tương tự nhau. Đặc điểm:  Mỗi đối tượng chỉ thuộc về 1 cụm.  Mỗi cụm có tối thiểu 1 đối tượng. Một số thuật toán điển hình : K-mean, PAM, CLARA, 8
9. II.2. Thuật toán K-Means Phát biểu bài toán: Input K - xR d và Mean ➢ Tập các đối tượng X = {xi| i = 1, 2, , N}, i ứ ➢ Số cụm: K dung ng Output ➢ Các cụm Ci ( i = 1 ÷ K) tách rời và hàm tiêu chuẩn E đạt giá trị tối thiểu. 9
10. II.1. KHÁI QUÁT VỀ THUẬT TOÁN ➢ Thuật toán hoạt động trên 1 tập vectơ d chiều, tập dữ liệu X gồm N phần tử: K - Mean và và Mean X = {xi | i = 1, 2, , N} ứ ng dung ng ➢ K-Mean lặp lại nhiều lần quá trình: ➢ Gán dữ liệu. ➢ Cập nhật lại vị trí trọng tâm. ➢ Quá trình lặp dừng lại khi trọng tâm hội tụ và mỗi đối tượng là 1 bộ phận của 1 cụm. 10
11. II.1. KHÁI QUÁT VỀ THUẬT TOÁN Hàm đo độ tương tự sử dụng khoảng cách Euclidean N K - 2 và Mean E =  (||xcij− || ) i= 1 xij C ứ ng dung ng trong đó cj là trọng tâm của cụm Cj Hàm trên không âm, giảm khi có 1 sự thay đổi trong 1 trong 2 bước: gán dữ liệu và định lại vị trí tâm. 11
12. II.2. CÁC BƯỚC CỦA THUẬT TOÁN Bước 1 - Khởi tạo Chọn K trọng tâm {ci} (i = 1÷K). Bước 2 - Tính toán khoảng cách ()t ()()tt S = {x:|| x− c || || x − c ||for all i*= 1, , k} i j j i j i* Bước 3 - Cập nhật lại trọng tâm 1 cx(t+ 1) = ij()t  ||S ()t i xSji Bước 4 – Điều kiện dừng Lặp lại các bước 2 và 3 cho tới khi không có sự thay đổi 12 trọng tâm của cụm.
13. II.2. CÁC BƯỚC CỦA THUẬT TOÁN Bắt đầu Số cụm K K - Mean và và Mean ứ Trọng tâm dung ng - Khoảng cách các Không có đối tượng + đối tượng đến các Kết thúc trọng tâm chuyển nhóm Nhóm các đối tượng vào các cụm 13
14. II.3 VÍ DỤ MINH HỌA Đối tượng Thuộc tính 1 (X) Thuộc tính 2 (Y) A 1 1 B 2 1 C 4 3 K - D 5 4 và Mean ứ ng dung ng 14
15. II.3 VÍ DỤ MINH HỌA Bước 1: Khởi tạo Chọn 2 trọng tâm ban đầu: c1(1,1) ≡ A và c2(2,1) ≡ B, thuộc 2 cụm 1 và 2 K - Mean và và Mean 4.5 ứ ng dung ng 4 3.5 3 2.5 2 1.5 1 0.5 0 15 0 2 4 6
16. II.3 VÍ DỤ MINH HỌA Bước 2: Tính toán khoảng cách (4− 1)22 + (3 − 1) ➢ d(C, c1) = K - = 13 và Mean (4− 2)22 + (3 − 1) d(C, c2) = ứ = 8 dung ng d(C, c1) > d(C, c2) C thuộc cụm 2 22 ➢ d(D, c1) = (5− 1) + (4 − 1) = 25 (5− 2)22 + (4 − 1) d(D, c2) = = 18 16 d(D,c1) > d(D, c2) D thuộc cụm 2
17. II.3 VÍ DỤ MINH HỌA Bước 3: Cập nhật lại vị trí trọng tâm ➢ Trọng tâm cụm 1 c1 ≡ A (1, 1) 2+ 4 + 5 1 + 3 + 4 ➢ Trọng tâm cụm 2 c2 (x,y) = (,) K 33 - Mean và và Mean ứ 4.5 dung ng 4 3.5 3 2.5 2 1.5 1 0.5 0 17 0 2 4 6
18. II.3 VÍ DỤ MINH HỌA Bước 4-1: Lặp lại bước 2 – Tính toán khoảng cách K - Mean và và Mean ➢ d(A, c1 ) = 0 d(C, c2 ) = 0.22 C thuộc cụm 2 ➢ d(D, c1 ) = 25 > d(D, c2 ) = 3.56 D thuộc cụm 2 18
19. II.3 VÍ DỤ MINH HỌA Bước 4-2: Lặp lại bước 3-Cập nhật trọng tâm c1 = (3/2, 1) và c2 = (9/2, 7/2) K - Mean và và Mean ứ ng dung ng 19
20. II.3 VÍ DỤ MINH HỌA Bước 4-3: Lặp lại bước 2 ➢ d(A, c1 ) = 0.25 d(D, c2 ) = 0.5 D thuộc cụm 2 20
21. II.3 VÍ DỤ MINH HỌA K - Mean và và Mean ứ ng dung ng 21
22. II.4 ĐÁNH GIÁ THUẬT TOÁN – ƯU ĐIỂM 1. Độ phức tạp: O( K N l ) với l: số lần lặp 2. Có khả năng mở rộng, có thể dễ dàng sửa đổi với K - những dữ liệu mới. và Mean 3. Bảo đảm hội tụ sau 1 số bước lặp hữu hạn. ứ ng dung ng 4. Luôn có K cụm dữ liệu 5. Luôn có ít nhất 1 điểm dữ liệu trong 1 cụm dữ liệu. 6. Các cụm không phân cấp và không bị chồng chéo dữ liệu lên nhau. 7. Mọi thành viên của 1 cụm là gần với chính cụm đó hơn bất cứ 1 cụm nào khác. 22
23. II.4 ĐÁNH GIÁ THUẬT TOÁN – NHƯỢC ĐIỂM 1. Không có khả năng tìm ra các cụm không lồi hoặc các cụm có hình dạng phức tạp. 2. Khó khăn trong việc xác định các trọng tâm cụm ban đầu K - - Chọn ngẫu nhiên các trung tâm cụm lúc khởi tạo và Mean - Độ hội tụ của thuật toán phụ thuộc vào việc khởi tạo ứ các vector trung tâm cụm dung ng 3. Khó để chọn ra được số lượng cụm tối ưu ngay từ đầu, mà phải qua nhiều lần thử để tìm ra được số lượng cụm tối ưu. 4. Rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. 5. Không phải lúc nào mỗi đối tượng cũng chỉ thuộc về 1 cụm, chỉ phù hợp với đường biên giữa các cụm rõ. 23
24. II.5 TổNG QUÁT HÓA VÀ CÁC BIếN THể B. Các biến thể K - 1. Thuật toán K-medoid: và Mean Tương tự thuật toán K-mean ứ ng dung ng Mỗi cụm được đại diện bởi một trong các đối tượng của cụm. Chọn đối tượng ở gần tâm cụm nhất làm đại diện cho cụm đó. K-medoid khắc phục được nhiễu, nhưng độ phức tạp lớn hơn. 24
25. II.5 TỔNG QUÁT HÓA VÀ CÁC BIẾN THỂ 2. Thuật toán Fuzzy c-mean (FCM): Chung chiến lược phân cụm với K-mean. N u K-mean là phân c m d li u c ng (1 đi m d K ế ụ ữ ệ ứ ể ữ - Mean và và Mean liệu chỉ thuộc về 1 cụm) thì FCM là phân cụm dữ liệu mờ (1 điểm dữ liệu có thể thuộc về nhiều hơn 1 ứ cụm với 1 xác suất nhất định). dung ng Thêm yếu tố quan hệ giữa các phần tử và các cụm dữ liệu thông qua các trọng số trong ma trận biểu biễn bậc của các thành viên với 1 cụm. FCM khắc phục được các cụm dữ liệu chồng nhau trên các tập dữ liệu có kích thước lớn hơn, nhiều chiều và nhiều nhiễu, song vẫn nhạy cảm với nhiễu và các phần tử ngoại lai. 25
26. III. ỨNG DỤNG CỦA THUẬT TOÁN Phân cụm tài liệu web. 1. Tìm kiếm và trích rút tài liệu K - Mean và và Mean 2. Tiền xử lý tài liệu: Quá trình tách từ và vecto hóa tài liệu: tìm kiếm và thay thế các từ bới chỉ số của từ đó ứ trong từ điển.Biểu diễn dữ liệu dưới dạng vectơ. dung ng 3. Áp dụng K-Mean Kết quả trả về là các cụm tài liệu và các trọng tâm tương ứng. Phân vùng ảnh 26
27. TÀI LIỆU THAM KHẢO ➢ Tài liệu chính: [WKQ08] Xindong Wu, Vipin Kumar, J. Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J. McLachlan, Angus Ng, Bing Liu, Philip K - S. Yu , Zhi-Hua Zhou, Michael Steinbach, David J. Hand, Dan Steinberg (2008). Top 10 và Mean algorithms in data mining, Knowl Inf Syst (2008) 14:1–37 ứ ➢ Pavel Berkhin (). Survey of Clustering Data Mining Techniques dung ng ➢ ➢ ➢ Slide KI2 – 7 Clustering Algorithms - Johan Everts ➢ ọc_không_có_giám_sát ➢ 27
28. K-Mean và ứng dung 28 THANK YOU FOR LISTENING