Bài giảng Khai phá dữ liệu - Chương 5: Gom cụm

Chương 5 trang bị những kiện thức về gom cụm. Thông qua chương này người học sẽ tìm hiểu: Phân tích bằng gom cụm là gì? Đối tượng tương tự và không tương tự, các loại dữ liệu trong phân tích bằng gom cụm, một số phương pháp gom cụm. Mời 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 5: Gom cụm Chương 5: Gom cụm Phân tích bằng gom cụm Khái quát - Phân tích bằng gom cụm là gì? - Đối tượng tương tự và không tương tự - Các loại dữ liệu trong phân tích bằng gom cụm - Một số phương pháp gom cụm Chương 5: Gom cụm Phân tích bằng gom cụm là gì? Gom cụm: Gom các đối tượng dữ liệu: - Tương tự với một đối tượng khác trong cùng cụm - Không tương tự với các đối tượng trong các cụm khác Mục tiêu của gom cụm: Gom tập các đối tượng dữ liệu thành các nhóm Chương 5: Gom cụm Các ứng dụng của gom cụm - Tiếp thị: khám phá các nhóm khách hàng phân biệt trong CSDL mua hàng - Hoạch định thành phố: nhận dạng các nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý - Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm.... - Thương mại: nhận dạng sản phẩm hàng hóa, kinh doanh,.. Chương 5: Gom cụm Thế nào là gom cụm tốt - Một phương pháp phân cụm tốt sẽ tạo ra các cụm có chất lượng cao với: * Tương tự cao trong một lớp * Tương tự thấp giữa các lớp - Chất lượng của kết quả gom cụm phụ thuộc vào: * Độ đo tương tự được sử dụng * Phương pháp cài đặt độ đo tương tự Chương 5: Gom cụm Tương tự và bất tương tự giữa hai đối tượng? - Định nghĩa về tương tự và bất tương tự giữa các đối tượng phụ thuộc: * Loại dữ liệu khảo sát * Loại tương tự cần thiết - Tương tự/bất tương tự biểu diễn qua độ đo khoảng cách d(x,y) - Độ đo khoảng cách thỏa mãn các điều kiện: * d(x,y) ≥ 0 * d(x,y) =0 khi và chỉ khi x=y * d(x,y) = d(y,x) * d(x,z) ≤ d(x,y) + d(y,z) Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến khoảng tỷ lệ Các độ đo liên tục của các thang đo tuyến tính. Ví dụ: Trọng lượng, chiều cao, tuổi,...  Cần chuẩn hóc dữ liệu để tránh phụ thuộc đơn vị đo * Độ đo khoảng cách phổ biến cho biến tỷ lệ theo khoảng là độ đo khoảng cách Minkowski: d(i,j)= ( ???????????? − ???????????? ???? + ???????????? − ???????????? ???? + ⋯ + ???????????? − ???????????? ????) Trong đó: i=(xi1,xi2,...,xip) và j=(xj1,xj2,...,xjp) là các đối tượng dữ liệu p-chiều và q là số nguyên dương Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến khoảng tỷ lệ • Nếu q=1 thì độ đo khoảng cách là độ đo Manhatan: d(i,j)= ???????????? − ???????????? + ???????????? − ???????????? + ⋯ + ???????????? − ???????????? • Nếu q=2 thì độ đo khoảng cách là độ đo Euclidean: d(i,j)= ( ???????????? − ???????????? ???? + ???????????? − ???????????? ???? + ⋯ + ???????????? − ???????????? ????) Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân - Biến nhị phân chỉ có hai trạng thái là 0 và 1 Ví dụ: Giới tính - Bảng Contingency Table cho dữ liệu nhị phân Đối tượng j 1 0 sum Đối tượng i 1 a b a+b 0 c d c+d sum a+c b+d p Trong đó: a,b,c,d là số các thành phần tương ứng giữa 2 vector i và j Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân - Hệ số đối sánh đơn giản (Biến nhị phân là đối xứng) ????+???? d(i,j) = ????+????+????+???? - Hệ số Jaccard (Biến nhị phân bất đối xứng) ????+???? d(i,j) = ????+????+???? Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân Ví dụ: Cho các record bệnh nhân Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N  Ta có thể chuyển về dạng các vector nhị phân như sau: Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack 1 1 0 1 0 0 0 Mary 0 1 0 1 0 1 0 Jim 1 1 1 0 0 0 0 Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân Các vector nhị phân: Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack 1 1 0 1 0 0 0 Mary 0 1 0 1 0 1 0 Jim 1 1 1 0 0 0 0 Bảng Contingency Table cho hai đối tượng Jack và Mary  a=2, b=1, c=1, d=3 Đối tượng Mary  Hệ số Jaccard: 1 0 sum ????+???? Đối 1 2 1 a+b d(Jack,Mary)= =0.5 tượng ????+????+???? 0 1 3 c+d Tương tự: Jack sum a+c b+d p d(Jack,Jim)=0.5 d(Jim,Mary)=0.8 Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến định danh - Mở rộng biến nhị phân để biến có thể nhận nhiều hơn hai trạng thái Ví dụ: Màu sắc (đỏ, xanh, vàng, lục,....) - Phương pháp 1: Đối sánh đơn giản ????−???? d(i,j) = ???? Trong đó: - m: là số lần gi ...