Bài giảng Khai phá dữ liệu: Chương 6 - Trường ĐH Phan Thiết

Bài giảng Khai phá dữ liệu: Chương 6 Phân cụm dữ liệu, cung cấp cho người học những kiến thức như: Giới thiệu bài toán phân cụm; Một số độ đo cơ bản cho phân cụm; Phân cụm K-mean gán cứng; Phân cụm phân cấp; Biểu diễn cụm và gán nhãn; Đánh giá phân cụm. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá dữ liệu: Chương 6 - Trường ĐH Phan Thiết Chương 6 Phân cụm dữ liệuKHAI PHÁ DỮ LIỆU Nội dung1. Giới thiệu bài toán phân cụm2. Một số độ đo cơ bản cho phân cụm3. Phân cụm K-mean gán cứng4. Phân cụm phân cấp5. Biểu diễn cụm và gán nhãn6. Đánh giá phân cụm DW DM 348 1. Giới thiệu bài toán phân cụm Bài toán  Tập dữ liệu D = {di}  Phân các dữ liệu thuộc D thành các cụm  Các dữ liệu trong một cụm: “tương tự” nhau (gần nhau)  Dữ liệu hai cụm: “không tương tự” nhau (xa nhau)  Đo “tương tự” (gần) nhau ?  Tiên đề phân cụm: Nếu người dùng lựa chọn một đối tượng d thì họ cũng lựa chọn các đối tượng cùng cụm với d  Khai thác “cách chọn lựa” của người dùng  Đưa ra một số độ đo “tương tự” theo biểu diễn dữ liệu Một số nội dung liên quan  Xây dựng độ đo tương tự  Khai thác thông tin bổ sung  Số lượng cụm cho trước, số lượng cụm không cho trước DW DM 349 Sơ bộ tiếp cận phân cụm Phân cụm mô hình và phân cụm phân vùng  Mô hình: Kết quả là mô hình biểu diễn các cụm dữ liệu  Vùng: Danh sách cụm và vùng dữ liệu thuộc cụm Phân cụm đơn định và phân cụm xác suất  Đơn định: Mỗi dữ liệu thuộc duy nhất một cụm  Xác suất: Danh sách cụm và xác suất một dữ liệu thuộc vào các cụm Phân cụm phẳng và phân cụm phân cấp  Phẳng: Các cụm dữ liệu không giao nhau  Phân cấp: Các cụm dữ liệu có quan hệ phân cấp cha- con Phân cụm theo lô và phân cụm tăng  Lô: Tại thời điểm phân cụm, toàn bộ dữ liệu đã có  Tăng: Dữ liệu tiếp tục được bổ sung trong quá trình phân DW cụm DM 350 Các phương pháp phân cụm Các phương pháp phổ biến  Phân vùng, phân cấp, dựa theo mật độ, dựa theo lưới, dựa theo mô hình, và phân cụm mờ Phân cụm phân vùng (phân cụm phẳng)  Xây dựng từng bước phân hoạch các cụm và đánh giá chúng theo các tiêu chí tương ứng  Tiếp cận: từ dưới lên (gộp dần), từ trên xuống (chia dần)  Độ đo tương tự / khoảng cách  K-mean, k-mediod, CLARANS, …  Hạn chế: Không điều chỉnh được lỗi Phân cụm phân cấp  Xây dựng hợp (tách) dần các cụm tạo cấu trúc phân cấp và đánh giá theo các tiêu chí tương ứng  Độ đo tương tự / khoảng cách  HAC: Hierarchical agglomerative clustering DW  CHAMELEON, BIRRCH và CURE, … DM 351 Các phương pháp phân cụm Phân cụm dựa theo mật độ  Hàm mật độ: Tìm các phần tử chính tại nơi có mật độ cao  Hàm liên kết: Xác định cụm là lân cận phần tử chính  DBSCAN, OPTICS… Phân cụm dựa theo lưới  Sử dụng lưới các ô cùng cỡ: tuy nhiên cụm là các “ô” phân cấp  Tạo phân cấp ô lưới theo một số tiêu chí: số lượng đối tượng trong ô  STING, CLIQUE, WaweCluster… Phân cụm dựa theo mô hình  Giải thiết: Tồn tại một số mô hình dữ liệu cho phân cụm  Xác định mô hình tốt nhất phù hợp với dữ liệu  MCLUST… Phân cụm mờ  Giả thiết: không có phân cụm “cứng” cho dữ liệu và đối tượng có thể thuộc một số cụm DW  Sử dụng hàm mờ từ các đối tượng tới các cụm DM  FCM (Fuzzy CMEANS),… 352 2. Một số độ đo cơ bản Độ đo tương đồng  Biểu diễn: vector n chiều  Giá trị nhị phân: Ma trận kề, độ đo Jaccard  Giá trị rời rạc [0,m]: Chuyển m giá trị thành nhị phân, độ đo Jaccard  Giá trị thực : độ đo cosin hai vector Độ đo khác biệt  Đối ngẫu độ đo tương đồng  Thuộc tính nhị phân: đối cứng, không đối xứng  Giá trị rời rạc: hoặc tương tự trên hoặc dạng đơn giản (q thuộc tính giống nhau)  Giá trị thực: Khoảng cách Manhattan, Euclide, Mincowski  Tính xác định dương, tính đối DW xứng, tính bất đẳng thức tam giác DM 353 Một số độ đo cơ bản Ví dụ về độ khác biệt  CSDL xét nghiệm bệnh nhân  Quy về giá trị nhị phân: M/F, Y/N, N/P  Lập ma trận khác biệt cho từng cặp đối tượng.  Ví dụ, cặp (Nam, Vân): a=2, b=1, c=1, d=3 D(Nam, Vân) =(1+1)/(2+1+1)=0.5 DW DM 354 3. Phân cụm K-mean gán cứng Một số lưu ý  Điều kiện dừng  Sau bước 2 không có sự thay đổi cụm  Điều kiện dừng cưỡng bức  Khống chế số lần lặp  Giá trị mục tiêu đủ nhỏ DW  Vấn đề chọn tập đại diện ban đầu ở bước Khởi động DM  Có thể dùng độ đo khoảng cách thay cho độ đo tương tự 355 a. Thuât toán K-mean gán cứng Một số lưu ý (tiếp) và ví dụ  Trong bước 2: các trọng tâm có thể không thuộc S  Thực tế: số lần lặp  50  Thi hành k-mean với dữ liệu trên đĩa  Toàn bộ dữ liệu quá lớn: không thể ở bộ nhớ trong  Với mỗi vòng lặp: duyệt CSDL trên đĩa 1 lần  Tính được độ tương tự của ...