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 Jack Tương tự: 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ống nhau khi so sánh - p: Tổng số biến - Phương pháp 2: Dùng một số lượng các biến nhị phân. Tạo biến nhị phân mới cho từng trạng thái định danh Chương 5: Gom cụm Một số phương pháp gom cụm Phương pháp phân hoạch Tạo phân hoạch CSDL D có n đối tượng thành tập có k cụm sao cho: - Mỗi cụm chứa ít nhất một đối tượng - Mỗi đối tượng thuộc về một cụm duy nhất - Một số phương pháp: * K-Means (MacQueen’67): Mỗi cụm được đại diện bởi trọng tâm (centroid) của cụm. * K-Medoids (Kaufman & Rousessuw’87): Mỗi cụm được đại diện bằng một trong các đối tượng của cụm Chương 5: Gom cụm Thuật toán K-Means Thuật toán K-Means thực hiện Bắt đầu qua các bước chính sau: 1.Chọn ngẫu nhiên K tâm K=? (centroid) cho K cụm (cluster). Mỗi cụm được đại diện bằng các Chọn K tâm tâm của cụm. Thay đổi 2.Tính khoảng cách giữa các đối Khoảng cách cụm của các tượng (objects) đến K tâm các đối tượng đối tượng (Euclidean) đến tâm 3.Nhóm các đối tượng vào nhóm gần nhất Nhóm các đối Xác định lại tâm 4.Xác định lại tâm mới cho các tượng vào cụm cho các cụm nhóm gần nhất 5.Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng Chương 5: Gom cụm Thuật toán K-Means Ví dụ: Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại được biểu diễn bởi 2 đặc trưng X và Y như sau. Mục đích của ta là nhóm các thuốc đã cho vào 2 nhóm (K=2) dựa vào các đặc trưng của chúng. Đối tượng X Y Bước 1: Khởi tạo tâm cho 2 cụm. Giả sử A là tâm A 1 1 cụm 1 - c1(1,1) và B là tâm cụm 2 - c2 (2,1) B 2 1 C 4 3 4.5 4 D 5 4 3.5 3 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X) Chương 5: Gom cụm Thuật toán K-Means Bước 2: Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách Euclidean) – D0 A B C D 푿 = ퟏ ퟐ ퟒ ퟓ 풀 = ퟏ ퟏ ퟑ ퟒ 푿 = ퟎ ퟏ ퟑ. ퟔퟏ ퟓ c1=(1,1) – group 1 푫ퟎ = 풀 = ퟏ ퟏ ퟐ. ퟖퟑ ퟒ. ퟐퟒ c2=(2,1) – group 2 - Mỗi cột trong ma trận D là một đối tượng - Mỗi hàng là khoảng cách của mỗi đối tượng đến các tâm (được tính bởi Euclidean: ퟐ ퟐ ퟐ d(i,j)= ( 풙풊ퟏ − 풙풋ퟏ + 풙풊ퟐ − 풙풋ퟐ + ⋯ + 풙풊풑 − 풙풋풑 ) Ví dụ: Khoảng cách từ loại thuốc C=(4,3) đến tâm c1(1,1) là 3.61 và đến tâm c2(2,1) là 2.83 được tính như sau: ퟐ ퟐ d(C,c1) = ퟒ − ퟏ + ퟑ − ퟏ = 3.61 ퟐ ퟐ d(C,c2) = ퟒ − ퟐ + ퟑ − ퟏ = 2.83 Chương 5: Gom cụm Thuật toán K-Means Bước 3: Nhóm các đối tượng vào nhóm gần nhất– G0 A B C D ퟏ ퟎ ퟎ ퟎ – group 1 푮 = ퟎ ퟎ ퟏ ퟏ ퟏ – group 2  Cụm 1 sau vòng lặp thứ nhất gồm có 1 đối tượng A  Cụm 2 gồm các đối tượng còn lại B,C,D. Chương 5: Gom cụm Thuật toán K-Means Bước 4: Tính lại tọa độ các tâm cho các cụm mới dựa vào tọa độ của các đối tượng trong cụm.  Cụm 1 chỉ có 1 đối tượng A nên tâm cụm 1 vẫn không đổi c1=(1,1).  Tâm cụm 2 được tính như sau: ퟐ+ퟒ+ퟓ ퟏ+ퟑ+ퟒ c = ( , ) 2 ퟑ ퟑ 4.5 ퟏퟏ ퟖ 4 = ( , ) 3.5 ퟑ ퟑ 3 = (ퟑ. ퟔퟔ, ퟐ. ퟔퟔ) 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X) Chương 5: Gom cụm Thuật toán K-Means Bước 5: Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách Euclidean) – D1 A B C D 푿 = ퟏ ퟐ ퟒ ퟓ 풀 = ퟏ ퟏ ퟑ ퟒ 푿 = ퟎ ퟏ ퟑ. ퟔퟏ ퟓ c1=(1,1) – group 1 푫 = ퟏ 풀 = ퟑ. ퟏퟒ ퟐ. ퟑퟔ ퟎ. ퟒퟕ ퟏ. ퟖퟗ ퟏퟏ ퟖ c =( , ) – group 2 2 ퟑ ퟑ Bước 6: Nhóm các đối tượng vào nhóm gần nhất– G1 A B C D ퟏ ퟏ ퟎ ퟎ – group 1 푮 = ퟏ ퟎ ퟎ ퟏ ퟏ – group 2  Cụm 1 sau vòng lặp thứ hai gồm có 2 đối tượng A,B  Cụm 2 gồm các đối tượng còn lại C,D. Chương 5: Gom cụm Thuật toán K-Means Bước 7: Tính lại tâm cho nhóm mới: ퟏ+ퟐ ퟏ+ퟏ ퟑ  Tâm cụm 1 được tính như sau: c = ( , ) = ( ,1) 1 ퟐ ퟐ ퟐ ퟒ+ퟓ ퟑ+ퟒ ퟗ ퟕ  Tâm cụm 2 được tính như sau: c = ( , ) = ( , ) 2 ퟐ ퟐ ퟐ ퟐ 4.5 4 3.5 3 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X) Chương 5: Gom cụm Thuật toán K-Means Bước 8: Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách Euclidean) – D2 A B C D 푿 = ퟏ ퟐ ퟒ ퟓ 풀 = ퟏ ퟏ ퟑ ퟒ ퟑ c =( 1) – group 1 푿 = ퟎ. ퟓ ퟎ. ퟓ ퟑ. ퟐ ퟒ. ퟔퟏ 1 , 푫 = ퟐ ퟐ 풀 = ퟒ. ퟑ ퟑ. ퟓퟒ ퟎ. ퟕퟏ ퟎ. ퟕퟏ ퟗ ퟕ c =( , ) – group 2 2 ퟐ ퟐ Bước 9: Nhóm các đối tượng vào nhóm gần nhất– G2 A B C D ퟏ ퟏ ퟎ ퟎ – group 1 푮 = ퟐ ퟎ ퟎ ퟏ ퟏ – group 2  G2 = G1  Không có sự thay đổi cụm nào của các đối tượng  Dừng Chương 5: Gom cụm Thuật toán K-Means  Với 4 loại thuốc A,B,C,D, mỗi loại được biểu diễn bởi 2 đặc trưng X và Y, ta nhóm các thuốc đã cho vào 2 cụm (K=2) dựa vào các đặc trưng của chúng như sau: Đối tượng X Y Cụm A 1 1 1 B 2 1 1 C 4 3 2 D 5 4 2 Chương 5: Gom cụm Một số phương pháp gom cụm Phương pháp phân cấp - Tạo các cụm được phân cấp. - Không cần số các cụm K ban đầu ở đầu vào - Thường biểu diễn dưới dạng cây các cụm, gọi là dendrogam, trong đó: • Các lá của cây biểu diễn từng đối tượng • Các nút biểu diễn cho các cụm Chương 5: Gom cụm Thuật toán AHC ( Aggloerative Hierarchical Clustering – Phân nhóm theo thứ bậc) Bắt đầu 1. Chuyển đổi các đặc trưng (thuộc tính - Features) của đối tượng (objects) vào ma trận khoảng cách Chuyển đổi các đặc trưng 2. Xem mỗi đối tượng là một cluster Xác định cluster (chẳng hạn, nếu ta có 4 đối tượng, ban đầu chúng ta sẽ có 4 clusters) Số cluster=1? 3. Lặp lại 2 bước sau cho đến khi số Sai cluster bằng 1 Gộp 2 cluster a. Gộp (liên kết) 2 cluster gần nhất b. Cập nhật ma trận khoảng cách Cập nhật ma trận Chương 5: Gom cụm Thuật toán AHC Tính liên kết giữa các đối tượng -Compute Linkages Between Objects 1. Single Linkage: Khoảng cách giữa 2 clusters được tính là khoảng cách giữa 2 đối tượng gần nhau nhất trong 2 clusters đó (minimum distance). dAB = min (dij), i∈A,j∈B 2. Complete Linkage: Khoảng cách giữa 2 clusters được tính là khoảng cách giữa 2 đối tượng xa nhau nhất trong 2 clusters đó (maximum distance). dAB = max (dij), i∈A,j∈B Chương 5: Gom cụm Thuật toán AHC Tính liên kết giữa các đối tượng -Compute Linkages Between Objects 3. Average Group: Khoảng cách giữa 2 clusters được tính là khoảng cách trung bình giữa các đối tượng trong 2 clusters đó (average distance). dAB = avg (dij), i∈A,j∈B 4. Centroid distance : Khoảng cách giữa 2 clusters được tính là khoảng cách của 2 tâm của 2 clusters đó (Centroid distance). dAB = |cA – cB| Chương 5: Gom cụm Thuật toán AHC Ví dụ: Giả sử có 6 đối tượng cần phân cụm A,B,C,D,E,F, mỗi đối tượng có 2 thuộc tính X1 và X2 như sau: Đối tượng X1 X2 Bước 1: Chuyển sang ma trận khoảng cách A 1 1 A B C D E F B 1.5 1.5 1 1.5 5 3 4 3 X1 C 5 5 1 1.5 5 4 4 3.5 X2 D 3 4 E 4 4 (X2) 6 F 3 3.5 5 4 3 2 1 0 (X1) 0 1 2 3 4 5 6 Chương 5: Gom cụm Thuật toán AHC Bước 2: Sử dụng Euclidean tính khoảng cách của tất cả các đối tượng  Ma trận khoảng cách: A B C D E F A 0 0.71 5.66 3.61 4.24 3.2 B 0.71 0 4.95 2.92 3.54 2.5 C 5.66 4.95 0 2.24 1.41 2.5 D 3.61 2.92 2.24 0 1 0.5 E 4.24 3.54 1.41 1 0 1.12 F 3.2 2.5 2.5 0.5 1.12 0 Chọn cách gộp các cluster bằng Single Linkage  Khoảng cách từ D đến F là khoảng cách nhỏ nhất (0.5)  Nhóm cụm D và F vào 1 cluster (D,F). Chương 5: Gom cụm Thuật toán AHC Bước 3: Chọn cách gộp các cluster bằng Single Linkage  Khoảng cách từ D đến F là khoảng cách nhỏ nhất (0.5)  Nhóm cụm D và F vào 1 cluster (D,F).  Ma trận khoảng cách: A B C (D,F) E A 0 0.71 5.66 ? 4.24 B 0.71 0 4.95 ? 3.54 C 5.66 4.95 0 ? 1.41 (D,F) ? ? ? 0 ? E 4.24 3.54 1.41 ? 0 Chương 5: Gom cụm Thuật toán AHC Bước 3: Tính lại khoảng cách từ cluster (D,F) đến các clusters khác - Khoảng cách từ cluster (D, F) và cluster A d(D,F)A = min(dDA,dFA) = min(3.61,3.2)=3.2 - Tương tự ta có: d(D,F)B = 2.5, d(D,F)C = 2.24, d(D,F)E = 1  Cập nhật ma trận khoảng cách: A B C (D,F) E A 0 0.71 5.66 3.2 4.24 B 0.71 0 4.95 2.5 3.54 C 5.66 4.95 0 2.24 1.41 (D,F) 3.2 2.5 2.24 0 1 E 4.24 3.54 1.41 1 0  Khoảng cách từ A đến B là khoảng cách nhỏ nhất (0.71) Chương 5: Gom cụm Thuật toán AHC Bước 4: Chọn cách gộp các cluster bằng Single Linkage  Khoảng cách từ A đến B là khoảng cách nhỏ nhất (0.71)  Nhóm cụm A và B vào 1 cluster (A,B).  Ma trận khoảng cách: (A,B) C (D,F) E (A,B) 0 ? ? ? C ? 0 2.24 1.41 (D,F) ? 2.24 0 1 E ? 1.41 1 0 Chương 5: Gom cụm Thuật toán AHC Bước 5: Tính lại khoảng cách giữa các clusters - Khoảng cách giữa cluster (A, B) và cluster C: d(A,B)C = min(dAC,dBC) = min(5.66,4.95)=4.95 - Khoảng cách giữa cluster (A, B) và cluster (D,F): d(A,B)DF = min(dAD,dAF,dBD,dBF) = min(3.61,2.92,3.2,2.5)=2.5 - Khoảng cách giữa cluster (A, B) và cluster E: d(A,B)E = min(dAE,dBE) = min(4.24,3.54)=3.54  Cập nhật ma trận khoảng cách: (A,B) C (D,F) E  Khoảng cách từ (D,F) (A,B) 0 4.95 2.5 3.54 đến E là khoảng cách C 4.95 0 2.24 1.41 nhỏ nhất (1) (D,F) 2.5 2.24 0 1 E 3.54 1.41 1 0 Chương 5: Gom cụm Thuật toán AHC Bước 6: Chọn cách gộp các cluster bằng Single Linkage  Khoảng cách từ (D,F) đến E là khoảng cách nhỏ nhất (1)  Nhóm cụm (D,F) vào cluster (E).  Ma trận khoảng cách: (A,B) C ((D,F),E) (A,B) 0 4.95 ? C 4.95 0 ? ((D,F),E) ? ? 0 Bước 7: Tính lại khoảng cách giữa các clusters  d((D,F),E)(A,B) = 2.5, d((D,F),E)C = 1.41  Cập nhật ma trận khoảng cách: (A,B) C ((D,F),E)  Khoảng cách từ (A,B) 0 4.95 2.5 ((D,F),E) đến C là C 4.95 0 1.41 khoảng cách nhỏ nhất ((D,F),E) 2.5 1.41 0 (1.41) Chương 5: Gom cụm Thuật toán AHC Bước 8: Chọn cách gộp các cluster bằng Single Linkage  Khoảng cách từ ((D,F),E) đến C là khoảng cách nhỏ nhất (1.41)  Nhóm cụm ((D,F),E) vào cluster (C).  Ma trận khoảng cách: (A,B) (((D,F),E),C) (A,B) 0 ? (((D,F),E),C) ? 0 Bước 9: Tính lại khoảng cách giữa các clusters  d(((D,F),E),C)(A,B) = 2.5  Cập nhật ma trận khoảng cách: (A,B) (((D,F),E),C)  Nhóm 2 clusters còn lại (A,B) (A,B) 0 2.5 và (((D, F), E), C) (((D,F),E),C) 2.5 0 Chương 5: Gom cụm Thuật toán AHC Bước 10: Chọn cách gộp các cluster bằng Single Linkage  Nhóm 2 clusters còn lại (A,B) và (((D, F), E), C)  Được 1 cluster duy nhất gồm toàn bộ 6 đối tượng ((((D,F),E),C),(A,B))  Kết thúc thuật toán AHC 2.5 6 2.0 5 C 4 1.5 D E 3 F 1.0 2 0.5 1 B A D F E C A B 0 1 2 3 4 5 6 Quá trình phân cụm Thứ tự phân cụm