Chương 5: Gom cụm

Phân tích bằng gom cụm Chương 5: 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 Phân tích bằng gom cụm là gì? Chương 5: Gom cụm 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 Các ứng dụng của gom cụm Chương 5: 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,.. Thế nào là gom cụm tốt Chương 5: Gom cụm - 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ự Tương tự và bất tương tự giữa hai đối tượng? Chương 5: Gom cụm - Đị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) Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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 Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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)= ( 𝒙𝒊𝟏 − 𝒙𝒋𝟏 𝟐 + 𝒙𝒊𝟐 − 𝒙𝒋𝟐 𝟐 + ⋯ + 𝒙𝒊𝒑 − 𝒙𝒋𝒑 𝟐) Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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 Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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) = 𝒃+𝒄 𝒂+𝒃+𝒄 Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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 Một số loại dữ liệu trong phân tích cụm Chương 5: Gom cụm Các biến nhị phân Các vector nhị phân: Bảng Contingency Table cho hai đối tượng Jack và Mary Đối tượng Mary 1 0 sum Đối tượng Jack 1 2 1 a+b 0 1 3 c+d sum a+c b+d p  a=2, b=1, c=1, d=3  Hệ số Jaccard: d(Jack,Mary)= 𝟏+𝟏 𝟐+𝟏+𝟏 =0.5 Tương tự: d(Jack,Jim)=0.5 d(Jim,Mary)=0.8 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 Một số loại dữ liệu trong phân tích cụm Chương 5: Gom 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 Một số phương pháp gom cụm Chương 5: 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 Bắt đầu K=? Chọn K tâm Khoảng cách các đối tượng đến tâm Nhóm các đối tượng vào cụm gần nhất Xác định lại tâm cho các cụm Thay đổi cụm của các đối tượng Thuật toán K-Means thực hiện qua các bước chính sau: 1.Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại diện bằng các tâm của cụm. 2.Tính khoảng cách giữa các đối tượng (objects) đến K tâm (Euclidean) 3.Nhóm các đối tượng vào nhóm gần nhất 4.Xác định lại tâm mới cho các nhóm 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 A 1 1 B 2 1 C 4 3 D 5 4 Bước 1: Khởi tạo tâm cho 2 cụm. Giả sử A là tâm cụm 1 - c1(1,1) và B là tâm cụm 2 - c2 (2,1) 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0 (Y ) (X) 0 1 2 3 4 5 6 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: c2 = ( 𝟐+𝟒+𝟓 𝟑 , 𝟏+𝟑+𝟒 𝟑 ) = ( 𝟏𝟏 𝟑 , 𝟖 𝟑 ) = (𝟑. 𝟔𝟔, 𝟐. 𝟔𝟔) 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0 (Y ) (X) 0 1 2 3 4 5 6 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 c2=( 𝟏𝟏 𝟑 , 𝟖 𝟑 ) – group 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: c1 = ( 𝟏+𝟐 𝟐 , 𝟏+𝟏 𝟐 ) = ( 𝟑 𝟐 ,1)  Tâm cụm 2 được tính như sau: c2 = ( 𝟒+𝟓 𝟐 , 𝟑+𝟒 𝟐 ) = ( 𝟗 𝟐 , 𝟕 𝟐 ) 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0 (Y ) (X) 0 1 2 3 4 5 6 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 𝑿 = 𝟏 𝟐 𝟒 𝟓 𝒀 = 𝟏 𝟏 𝟑 𝟒 𝑫𝟐 = 𝑿 = 𝟎. 𝟓 𝟎. 𝟓 𝟑. 𝟐 𝟒. 𝟔𝟏 𝒀 = 𝟒. 𝟑 𝟑. 𝟓𝟒 𝟎. 𝟕𝟏 𝟎. 𝟕𝟏 c1=( 𝟑 𝟐 ,1) – group 1 c2=( 𝟗 𝟐 , 𝟕 𝟐 ) – group 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 Một số phương pháp gom cụm Chương 5: 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) 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 2. Xem mỗi đối tượng là một cluster (chẳng hạn, nếu ta có 4 đối tượng, ban đầu chúng ta sẽ có 4 clusters) 3. Lặp lại 2 bước sau cho đến khi số cluster bằng 1 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 Bắt đầu Chuyển đổi các đặc trưng Xác định cluster Số cluster=1? Gộp 2 cluster Cập nhật ma trận Sai 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). 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 = min (dij), i∈A,j∈B 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). 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 = avg (dij), i∈A,j∈B dAB = |cA – cB| Chương 5: Gom cụm 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 A 1 1 B 1.5 1.5 C 5 5 D 3 4 E 4 4 F 3 3.5 Thuật toán AHC Bước 1: Chuyển sang ma trận khoảng cách A B C D E F 1 1.5 5 3 4 3 X1 1 1.5 5 4 4 3.5 X2 6 5 4 3 2 1 0 (X2) (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 (A,B) 0 4.95 2.5 3.54 C 4.95 0 2.24 1.41 (D,F) 2.5 2.24 0 1 E 3.54 1.41 1 0  Khoảng cách từ (D,F) đến E là khoảng cách nhỏ nhất (1) 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) (A,B) 0 4.95 2.5 C 4.95 0 1.41 ((D,F),E) 2.5 1.41 0  Khoảng cách từ ((D,F),E) đến C là khoảng cách nhỏ nhất (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:  Nhóm 2 clusters còn lại (A,B) và (((D, F), E), C) (A,B) (((D,F),E),C) (A,B) 0 2.5 (((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 Quá trình phân cụm D F E C A B 2.5 2.0 1.5 1.0 0.5 Thứ tự phân cụm 0 1 2 3 4 5 6 5 4 3 2 1 6 A B C D F E