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

Chương 5: Gom cụm dữ liệu 1 Nội dung  Tổng quan về gom cụm dữ liệu  Gom cụm dữ liệu bằng phân hoạch  Gom cụm dữ liệu bằng phân cấp  Gom cụm dữ liệu dựa trên mật độ  Gom cụm dữ liệu dựa trên mô hình  Các phương pháp gom cụm dữ liệu khác  Đánh giá chất lượng gom cụm  Tóm tắt 2 Tình huống 1 – Outlier detection 3 Người đang sử dụng thẻ ID = 1234 thật sự là chủ nhân của thẻ hay là một tên trộm? Tình huống 2 - Làm sạch dữ liệu  Nhận diện phần tử biên (outliers) và giảm thiểu nhiễu (noisy data) - Giải pháp giảm thiểu nhiễu  Phân tích cụm (cluster analysis) 4 Tình huống 3 5 Tình huống 3 6 Tình huống 3 7 Tình huống 3 8 Tình huống 3 9 Tình huống 3 10 Tình huống 3 11 Tình huống 4 12 Gom cụm ảnh Tình huống 13 Gom cụm Tình huống  Hỗ trợ giai đoạn tiền xử lý dữ liệu (data preprocessing)  Mô tả sự phân bố dữ liệu/đối tượng (data distribution)  Nhận dạng mẫu (pattern recognition)  Phân tích dữ liệu không gian (spatial data analysis)  Xử lý ảnh (image processing)  Phân mảnh thị trường (market segmentation)  Gom cụm tài liệu ((WWW) document clustering)  14 Tổng quan về gom cụm dữ liệu  Gom cụm - Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các lớp/cụm - Các đối tượng trong cùng một cụm tương tự với nhau hơn so với đối tượng ở các cụm khác.  Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2  Obj1 tương tự Obj2 hơn so với tương tự Obj3. 15 Gom cụm Tổng quan về gom cụm dữ liệu  Gom cụm - Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các lớp/cụm - Các đối tượng trong cùng một cụm tương tự với nhau hơn so với đối tượng ở các cụm khác.  Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2  Obj1 tương tự Obj2 hơn so với tương tự Obj3. 16 Inter-cluster distances are maximized. Intra-cluster distances are minimized. Tổng quan về gom cụm dữ liệu  Gom cụm - Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các lớp/cụm - Các đối tượng trong cùng một cụm tương tự với nhau hơn so với đối tượng ở các cụm khác.  Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2  Obj1 tương tự Obj2 hơn so với tương tự Obj3. 17 Inter-cluster distances are maximized. Intra-cluster distances are minimized. High intra- cluster/class similarity Low inter- cluster/class similarity Tổng quan về gom cụm dữ liệu  Có thể dùng ma trận dữ liệu để mô hình hóa bài toán gom cụm. Ma trận biểu diễn không gian dữ liệu gồm n đối tượng theo p biến/thuộc tính Ma trận dữ liệu (data matrix)                   npx...nfx...n1x ............... ipx...ifx...i1x ............... 1px...1fx...11x 18 -n đối tượng (objects) -p biến/thuộc tính (variables/attributes) Tổng quan về gom cụm dữ liệu  Để biểu diễn khoảng cách giữa hai điểm (đối tượng) trong không gian dữ liệu gồm n đối tượng theo p thuộc tính ta dùng ma trận phân biệt  Ma trận phân biệt (dissimilarity matrix)                 0...)2,()1,( ::: )2,3() ...ndnd 0dd(3,1 0d(2,1) 0 19 d(i, j) là khoảng cách giữa đối tượng i và j; thể hiện sự khác biệt giữa đối tượng i và j; được tính tuỳ thuộc vào kiểu của các biến/thuộc tính. Độ đo khoảng cách  Để đánh giá độ tương tự giữa các điểm dữ liệu cần có một độ đo khoảng cách được định nghĩa trong không gian dữ liệu đang xét.  Không có một độ đo nào có thể dùng chung cho mọi trường hợp.  Tùy theo mục tiêu khảo sát và bản chất dữ liệu người dùng phải chọn độ đo khoảng cách phù hợp với ứng dụng đang triển khai. 20 Độ đo khoảng cách 21 d(i, j) là khoảng cách giữa đối tượng i và j; thể hiện sự khác biệt giữa đối tượng i và j; được tính tuỳ thuộc vào kiểu của các biến/thuộc tính. d(i,j)  0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j)  d(i,k) + d(k,j) Vấn đề kiểu dữ liệu/đối tượng được gom cụm  Interval-scaled variables/attributes (trị khoảng) Binary variables/attributes (nhị phân) Categorical variables/attributes Ordinal variables/attributes (thứ tự) Nominal variables/atrribute (định danh) Ratio-scaled variables/attributes (tỉ lệ khoảng) Variables/attributes of mixed types 22 Độ đo khoảng cách Biến trị khoảng 23  Các biến trị khoảng là độ đo liên tục của các đại lượng tuyến tính đơn giản như trọng lượng, chiều cao, nhiệt độ, tuổi  Các đơn vị đó ảnh hưởng rất nhiều đến kết quả gom cụm. Do đó tùy vào lĩnh vực ứng dụng và tiêu chí của phương pháp tiếp cận mà chuẩn hóa dữ liệu. Biến trị khoảng 24  Phương pháp chuẩn hóa các độ đo - Tính sai số tuyệt đối trung bình: - Trong đó: - Tính độ đo chuẩn (z-score) |)|...|||(|1 21 fnffffff mxmxmxns  .)... 21 1 nffff xx(xn m  f fif if s mx z   Biến trị khoảng 25 Các độ đo thông dụng cho biến trị khoảng  Độ đo khoảng cách Minkowski  Độ đo khoảng cách Manhattan  Độ đo khoảng cách Euclidean q q pp qq j x i x j x i x j x i xjid )||...|||(|),( 2211  ||...||||),( 2211 pp j x i x j x i x j x i xjid  )||...|||(|),( 22 22 2 11 pp j x i x j x i x j x i xjid  Biến nhị phân 26  Biến nhị phân là biến chỉ có 2 trạng thái 0 hoặc 1.  Biến nhị phân là đối xứng nếu cả hai trạng thái là tương đương (về mặt ý nghĩa của ứng dụng). Có nghĩa là không có xu hướng thiên vị trạng thái 1.  Biến nhị phân là bất đối xứng nếu có một trạng thái có ý nghĩa quan trọng hơn (thường được mã là 1). Lúc này thường có xu hướng thiên vị trạng thái ưu tiên đó  Độ tương tự dựa trên biến nhị phân đối xứng thì được gọi là tương tự bất biến Biến nhị phân 27  Hệ số so trùng. dcba cb jid  ),( pdbcasum dcdc baba sum    0 1 01 cba cb jid  ),( Object i Object j (= a + b + c + d) Hệ số so trùng đơn giản (nếu symmetric): Hệ số so trùng Jaccard (nếu asymmetric): Biến nhị phân 28  Hệ số so trùng.  Ví dụ - Giới tính: thuộc tính nhị phân đối xứng - Các thuộc tính còn lại: nhị phân phi đối xứng - Cho giá trị Y và P là 1, và giá trị N là 0: Biến định danh 29  Biến định danh là biến có thể nhận nhiều hơn 2 trạng thái.  Ví dụ biến màu sắc có thể nhận “đỏ, vàng, xanh, lục”  Có 2 phương pháp để xác định khoảng cách theo biến định danh:  Phương pháp 1: Đối sánh đơn giản - m: số thuộc tính có giá trị trùng khớp giữa 2 đối tượng i và j , p: tổng số thuộc tính.  Phương pháp 2: đưa biến định danh về biến nhị phân bằng cách thay mỗi trạng thái định danh bằng một biến nhị phân mới.  Ví dụ biến màu sắc (đỏ, vàng, xanh, lục) có thể chuyển thành 4 biến nhị phân đỏ (có/không), vàng(có/không), xanh(có/không), lục(có/không) p mpjid ),( Biến thứ tự 30  Biến thứ tự là biến trên một tập giá trị có xác định quan hệ thứ tự trên đó, ví dụ hạng xếp loại huy chương vàng, bạc, đồng.  Biến thứ tự có thể rời rạc hoặc liên tục.  Độ đo cho biến thứ tự được xây dựng như sau:  Giả sử ta có biến thứ tự xif : - Thay xif bằng hạng của nó - Ánh xạ phạm vi biến vào [0, 1] khi thay thế đối tượng i thành biến f : - Tính toán độ phân biệt sử dụng phương pháp với biến cỡ-khoảng Zif },...,1{ fif Mr  1 1    f if if M r z Biến thứ tự 31  Ví dụ: biến thứ tự huy chương (vàng, bạc, đồng, không) 1. Thay thế xif bằng hạng của nó rif Є {1,2,3,4} 2. Ánh xạ phạm vi biến vào [0, 1] khi thay thế đối tượng i thành biến f bởi Ta có Z if ={0, 0.33, 0.66, 1} 3. Tính toán độ phân biệt sử dụng phương pháp với biến cỡ- khoảng Zif 1 1    f if if M r z Tên Điền kinh Bơi lội Xe đạp Sơn Vàng Bạc Bạc Ngọc Bạc - Đồng Dung - Vàng - Biến thứ tự 32  Bảng sau khi được chuẩn hóa (các phần tử là các Zif):  Chọn khoảng cách Euclide ta có d(Sơn, Ngọc) = 0.81 d(Ngọc, Dũng) =1.23 Tên Điền kinh Bơi lội Xe đạp Sơn 0 0.33 0.33 Ngọc 0.33 1 0.66 Dung 1 0 1 ))66.033.0(|133.0()33.00( 2 2)2   ))166.0(|01()133.0( 2 2)2   Biến tỉ lệ theo khoảng 33  Biến tỉ lệ khoảng là độ đo dương trên các tỉ lệ phi tuyến. Ví dụ: các đại lượng biểu diễn theo hàm mũ chẳng hạn AeBt .  Trong đa số trường hợp thì không thể áp dụng trực tiếp phương pháp độ đo cho các biến trị khoảng cho loại biến này vì có thể gây sai số lớn.  Phương pháp tốt hơn là tiền xử lý bằng cách chuyển sang logarit yif=log(xif) sau đó mới áp dụng trực tiếp phương pháp độ đo cho các biến trị khoảng hoặc thứ tự  CSDL có thể chứa cả 6 loại biến đơn nêu trên. Ta có thể dùng công thức được gán trọng để kết hợp các hiệu quả của các biến thành phần )( 1 )()( 1),( f ij p f f ij f ij p f d jid        34 Biến có kiểu hỗn hợp - f là nhị phân hay định danh: dij (f) = 0 nếu xif = xjf , hoặc dij (f) = 1 ngược lại - f là số: sử dụng khoảng cách đã chuẩn hóa - f là thứ bậc  Tính toán hạng rif và  Cho zif như cỡ-khoảng 1 1    f if M rz if Độ tương tự Cosine  Đối tượng vector (vector objects)  Đối tượng i và j được biểu diễn tương ứng bởi vector x và y.  Độ tương tự (similarity) giữa i và j được tính bởi độ đo cosine: 35 x = (x1, , xp) y = (y1, , yp) s(x, y) = (x1*y1 + + xp*yp)/((x12 + + xp2)1/2*(y12+ + yp2)1/2) Độ tương tự Cosine  Ví dụ: Một tài liệu có thể được trình bày bằng hàng nghìn thuộc tính, mỗi ghi nhận tần số của các phần tử (như từ khóa, n-gram) hoặc cụm từ  Tìm độ tương tự giữa hai tài liệu 1 và 2. d1 = (5, 0, 3, 0, 2, 0, 0, 2, 0, 0) d2 = (3, 0, 2, 0, 1, 1, 0, 1, 0, 1) d1d2 = 5*3+0*0+3*2+0*0+2*1+0*1+0*1+2*1+0*0+0*1 = 25 ||d1||= (5*5+0*0+3*3+0*0+2*2+0*0+0*0+2*2+0*0+0*0) 0.5=(42)0.5 = 6.481 ||d2||= (3*3+0*0+2*2+0*0+1*1+1*1+0*0+1*1+0*0+1*1) 0.5=(17)0.5 = 4.12 cos(d1, d2 ) = 0.94 36 Tổng quan về gom cụm dữ liệu 37  Quá trình gom cụm dữ liệu R. Xu, D. Wunsch II. Survey of Clustering Algorithms. IEEE Transactions on Neural Networks, 16(3), May 2005, pp. 645-678. Tổng quan về gom cụm dữ liệu  Mỗi cụm nên có bao nhiêu phần tử?  Các phân tử nên được gom vào bao nhiêu cụm?  Bao nhiêu cụm nên được tạo ra? 38 Bao nhiêu cụm? 4 cụm? 2 cụm? 6 cụm? Tổng quan về gom cụm dữ liệu  Các yêu cầu tiêu biểu về việc gom cụm dữ liệu - Khả năng co giãn về tập dữ liệu (scalability) - Khả năng xử lý nhiều kiểu thuộc tính khác nhau (different types of attributes) - Khả năng khám phá các cụm với hình dạng tùy ý (clusters with arbitrary shape) - Tối thiểu hóa yêu cầu về tri thức miền trong việc xác định các thông số nhập (domain knowledge for input parameters) - Khả năng xử lý dữ liệu có nhiễu (noisy data) 39 Tổng quan về gom cụm dữ liệu  Các yêu cầu tiêu biểu về việc gom cụm dữ liệu - Khả năng gom cụm tăng dần và độc lập với thứ tự của dữ liệu nhập (incremental clustering and insensitivity to the order of input records) - Khả năng xử lý dữ liệu đa chiều (high dimensionality) - Khả năng gom cụm dựa trên ràng buộc (constraint- based clustering) - Khả diễn và khả dụng (interpretability and usability) 40 Tổng quan về gom cụm dữ liệu  Phân loại các phương pháp gom cụm dữ liệu tiêu biểu - Phân hoạch (partitioning): các phân hoạch được tạo ra và đánh giá theo một tiêu chí nào đó. - Phân cấp (hierarchical): phân rã tập dữ liệu/đối tượng có thứ tự phân cấp theo một tiêu chí nào đó. - Dựa trên mật độ (density-based): dựa trên connectivity and density functions. - Dựa trên lưới (grid-based): dựa trên a multiple-level granularity structure. - Dựa trên mô hình (model-based): một mô hình giả thuyết được đưa ra cho mỗi cụm; sau đó hiệu chỉnh các thông số để mô hình phù hợp với cụm dữ liệu/đối tượng nhất. - 41 Tổng quan về gom cụm dữ liệu  Phân loại các phương pháp gom cụm dữ liệu tiêu biểu 42 Original Points Partitioning Tổng quan về gom cụm dữ liệu  Phân loại các phương pháp gom cụm dữ liệu tiêu biểu 43 p4 p1 p3 p2 p4p1 p2 p3 Hierarchical Original Points p4 p1 p3 p 2 Gom cụm dữ liệu bằng phân hoạch  Cho tập dữ liệu D, n đối tượng, và K là số lượng các cụm được hình thành.  Thuật toán phân hoạch tổ chức các đối tượng vào phân vùng k (k<=n), trong đó mỗi phân vùng đại diện cho 1 cụm.  Các cụm được hình thành cần tối ưu tiêu chuẩn phân hoạch đối tượng, ví dụ như các đối tượng cùng cụm thì tương tự hơn so với các đối tượng ở cụm khác về mặt thuộc tính tập dữ liệu, độ đo bình phương sai SSE nhỏ nhất 44 Gom cụm dữ liệu bằng phân hoạch  Trong phần này chúng ta học các phương pháp phân hoạch phổ biến: - K-mean - K-medoids  Chúng ta cũng học các biến thể khác nhau của các phương pháp phân hoạch cổ điển và cách thức mở rộng để quản lý một tập dữ liệu lớn 45 Gom cụm dữ liệu bằng phân hoạch  Công thức tính bình phương sai (Sum of Squared Error - SSE) ( within cluster variation)  Trong đó E là tổng số các lỗi bình phương của tất cả các đối tượng trong tập dữ liệu, p là điểm trong không gian hiển thị đối tượng cho trước, ci là trọng tâm của nhóm Ci (cả p và ci là đa chiều) 46 Thuật toán K-mean  Giải thuật k-means 47 Gom cụm dữ liệu bằng phân hoạch  Bước 1: Chọn ngẫn nhiên k đối tượng như là trọng tâm của nhóm  Bước 2: Gán từng đối tượng còn lại vào nhóm có trung tâm nhóm gần nó nhất (dựa vào khoảng cách Euclide giữa đối tượng cần gán và trọng tâm của nhóm)  Bước 3: - Tính lại giá trị trọng tâm của từng nhóm - Di chuyển trọng tâm nhóm về bằng với giá trị trung bình mới của nhóm  Bước 4: - Nếu các trọng tâm nhóm không thay đổi thì dừng, ngược lại, quay lại bước 2 48 Gom cụm dữ liệu bằng phân hoạch 49 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Arbitrarily choose K object as initial cluster center Assign each objects to most similar center Update the cluster means Update the cluster means reassign reassign Gom cụm dữ liệu bằng phân hoạch  Ví dụ: k=2 (chia tập các đối tượng sau thành 2 nhóm) 50 Bước 1: Chọn ngẫu nhiên 2 trọng tâm là: m1=(1.0,1.0) và m2=(5.0,7.0). Gom cụm dữ liệu bằng phân hoạch Bước 2:  Chúng ta có 2 nhóm: {1,2,3} and {4,5,6,7}.  Trọng tâm mới là: Gom cụm dữ liệu bằng phân hoạch Bước 3:  Tính khoảng cách Euclide từ các đối tượng ở bảng trên đến trọng tâm mới ở bước 2.  Vì vậy, 2 nhóm mới là: {1,2} and {3,4,5,6,7}  Trọng tâm mới là: m1=(1.25,1.5) and m2 = (3.9,5.1) Gom cụm dữ liệu bằng phân hoạch  Bước 4 : Các nhóm mới là: {1,2} và {3,4,5,6,7}  Không có sự thay đổi các đối tượng trong nhóm, thuật toán dừng  Kết quả: gom thành 2 nhóm sau: {1,2} và {3,4,5,6,7}. Gom cụm dữ liệu bằng phân hoạch Kết quả Gom cụm dữ liệu bằng phân hoạch Gom cụm dữ liệu bằng phân hoạch Step 1 Step 2 Với K=3 Kết quả Gom cụm dữ liệu bằng phân hoạch Gom cụm dữ liệu bằng phân hoạch  Đặc điểm của giải thuật k-means: - Kết quả của giải thuật phụ thuộc vào việc khởi tạo ngẫu nhiên các trung tâm của cụm. - Trong thực tế, để đạt được kết quả tốt, thường thực thi thuật toán k-mean nhiều lần với trọng tâm khởi tạo của các cụm khác nhau. - Mỗi cụm được đặc trưng hóa bởi trung tâm của cụm (i.e. đối tượng trung bình (mean)).  Không thể xác định được đối tượng trung bình???  Số cụm k nên là bao nhiêu? - Độ phức tạp của giải thuật k-mean là O(nkt), n: tổng số đối tượng, k: số cụm, t: số lần lặp. Thông thường k<<n và t<<n, vì vậy, phương pháp này có khả năng mở rộng, tương đối hiệu quả trong việc xử lý tập dữ liệu lớn. 58 Gom cụm dữ liệu bằng phân hoạch  Đặc điểm của giải thuật k-means - Ảnh hưởng bởi nhiễu (các phần tử kì dị/biên) - Không phù hợp cho việc khai phá ra các cụm có dạng không lồi (nonconvex) hay các cụm có kích thước rất khác nhau - Chỉ áp dụng khi giá trị trung bình của đối tượng được định nghĩa, không áp dụng cho các thuộc tính là nominal  k-mode là biến thể của k-mean - Nominal means “relating to names.” The values of a nominal attribute are symbols or names of things. 59 Gom cụm dữ liệu bằng phân hoạch  Ví dụ: các hạn chế của k-mean - Giả sử có 6 điểm trong không gian 1-D có giá trị sau: 1, 2, 3, 8, 9, 10 và 25. - Về mặt trực quan, ta có 2 cụm {1, 2,3} và {8, 9,10} và 25 thì tách biệt ra khỏi 2 nhóm trên do 25 là phần tử nhiễu. - k-mean phân cụm như thế nào nếu k=2? 60 Gom cụm dữ liệu bằng phân hoạch  Ví dụ: các hạn chế của k-mean - Nếu phân thành 2 cụm {1, 2, 3} và {8, 9,10, 25} - within-cluster variation= - Nếu phân thành 2 cụm {1, 2, 3, 8} và {9, 10, 25} - within-cluster variation= 61 Gom cụm dữ liệu bằng phân hoạch  Ví dụ: các hạn chế của k-mean - Cách chia sau có within-cluster variation nhỏ nhất, vì vậy k-mean gán 8 vào cụm khác với cụm chứa 9,10 bởi vì có giá trị nhiễu là 25, hơn nữa, trọng tâm của nhóm 2 là 14.76 về bản chất khác xa với các đối tượng trong cụm cần bổ sung vào thuật toán k-mean để giải quyết vấn đề trên Thuật toán k-medoids 62 Gom cụm dữ liệu bằng phân hoạch 63 Gom cụm dữ liệu bằng phân hoạch  Bước 1: Chọn ngẫn nhiên k đối tượng như là trọng tâm của nhóm  Bước 2: Gán từng đối tượng còn lại vào nhóm có trọng tâm cụm gần nó nhất  Bước 3: Chọn một đối tượng bất kỳ, hoán đổi nó với trọng tâm của nhóm, nếu chất lượng của nhóm tăng lên thì quay lại bước 2, ngược lại tiếp tục thực hiện bước 3 cho đến khi không còn có thay đổi. 64 Gom cụm dữ liệu bằng phân hoạch 65 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Arbitrary choose k object as initial medoids 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Assign each remainin g object to nearest medoids Randomly select a nonmedoid object,Oramdom Compute total cost of swapping 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 26 Swapping O and Oramdom If quality is improved. Do loop Until no change 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Gom cụm dữ liệu bằng phân hoạch  Đặc điểm của giải thuật PAM (k-medoids) - Mỗi cụm được đại diện bởi phần tử chính giữa cụm (centroid).  Giảm thiểu sự ảnh hưởng của nhiễu (phần tử biên/kì dị/cực trị).  Số cụm k cần được xác định trước. - Độ phức tạp cho mỗi vòng lặp O(k(n-k)2)  Giải thuật bị ảnh hưởng bởi kích thước tập dữ liệu. 66 Gom cụm dữ liệu bằng phân hoạch  Đặc điểm của giải thuật PAM (k-medoids) - Hiệu quả với tập dữ liệu nhỏ nhưng không co dãn tốt với tập dữ liệu lớn  Phương pháp lấy mẫu:  CLARA(Clustering LARge Applications)  CLARAN (Clustering LARge Application based upon) 67 Gom cụm dữ liệu bằng phân cấp  Gom cụm dữ liệu bằng phân cấp (hierarchical clustering): nhóm các đối tượng vào cây phân cấp của các cụm - Agglomerative: bottom-up (trộn các cụm) - Divisive: top-down (phân tách các cụm) Không yêu cầu thông số nhập k (số cụm) Yêu cầu điều kiện dừng Không thể quay lui ở mỗi bước trộn/phân tách 68 Gom cụm dữ liệu bằng phân cấp 69 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 Single-linkage Complete-linkage Tiêu chí trộn các cụm: single-linkage và complete-linkage Gom cụm dữ liệu bằng phân cấp 70 Min distance Average distance Max distance Single-Link Method / Nearest Neighbor Complete-Link / Furthest Neighbor Their Centroids. Average of all cross-cluster pairs. Gom cụm dữ liệu bằng phân cấp  An agglomerative hierarchical clustering method: AGNES (Agglomerative NESting)  bottom-up  A divisive hierarchical clustering method: DIANA (Divisive ANAlysis)  top-down 71 Gom cụm dữ liệu bằng phân cấp  An agglomerative hierarchical clustering method: AGNES (Agglomerative NESting)  bottom-up - Khởi đầu, mỗi đối tượng tạo thành một cụm. - Các cụm sau đó được trộn lại theo một tiêu chí nào đó.  Cách tiếp cận single-linkage: cụm C1 và C2 được trộn lại nếu khoảng cách giữa 2 đối tượng từ C1 và C2 là ngắn nhất. - Quá trình trộn các cụm được lặp lại đến khi tất cả các đối tượng tạo thành một cụm duy nhất. 72 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Gom cụm dữ liệu bằng phân cấp  A divisive hierarchical clustering method: DIANA (Divisive ANAlysis) - Khởi đầu, tất cả các đối tượng tạo thành một cụm duy nhất. - Một cụm được phân tách theo một tiêu chí nào đó đến khi mỗi cụm chỉ có một đối tượng.  Khoảng cách lớn nhất giữa các đối tượng cận nhau nhất. 73 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Gom cụm dữ liệu bằng phân cấp  Quá trình gom cụm bằng phân cấp được biểu diễn bởi cấu trúc cây (dendrogram). 74 Gom cụm dữ liệu bằng phân cấp  Quá trình gom cụm bằng phân cấp được biểu diễn bởi cấu trúc cây (dendrogram). 75 0.5 3 cụm có độ tương tự kết hợp nhỏ nhất 0.5 Gom cụm dữ liệu bằng phân cấp  Các độ đo dùng đo khoảng cách giữa các cụm Ci và Cj 76 p, p’: các đối tượng |p-p’|: khoảng cách giữa p và p’ mi, mj: đối tượng trung bình của Ci, Cj, tương ứng ni, nj: số lượng đối tượng của Ci, Cj, tương ứng Gom cụm dữ liệu bằng phân cấp  Single-Link Method b a 4 53 652 c b a dcb Distance Matrix 4 53, c ba dc 4 53 652 c b a dcb 4,, cba d (1) (2) (3) a,b,c c c d a,b d d a,b,c,d Euclidean Distance Gom cụm dữ liệu bằng phân cấp  Complete-Link Method b a 4 53 652 c b a dcb Distance Matrix Euclidean Distance 4 65, c ba dc 4 53 652 c b a dcb 6, , ba dc (1) (2) (3) a,b c c d a,b d c,d a,b,c,d Gom cụm dữ liệu bằng phân cấp  Single-Link và Complete-Link a b c d a b c d 2 4 6 0 Single-Link Complete-Link Gom cụm dữ liệu bằng phân cấp Ví dụ : Gom cụm phân cấp sử dụng phương pháp single-linkage để gom cụm các thành phố trên bản đồ dựa vào ma trận khoảng cách bên dưới Gom cụm dữ liệu bằng phân cấp  Khoảng cách giữa thành phố MI và TO là gần nhất: 138, 2 thành phố này gộp lại thành 1 cụm "MI/TO". (m=1)  Chúng ta tính khoảng cách từ đối tượng kép này đến tất cả các đối tượng còn lại.  Trong phương pháp single-link, khoảng cách từ đối tượng kép đến các đối tượng còn lại là khoảng cách gần nhất từ thành viên của đội tượng kép đến đối tượng bên ngoài.  Vì vậy khoảng cách từ “MI/TO” đến RM là 564 tức là khoảng cách từ MI đến RM, Gom cụm dữ liệu bằng phân cấp Input Distance Matrix L=0 for all clusters Gom cụm dữ liệu bằng phân cấp min d(i,j) = d(NA,RM) = 219 => merge NA and RM into a new cluster called NA/RM L(NA/RM) = 219 m = 2 BA FI MI/TO NA/RM BA 0 662 877 255 FI 662 0 295 268 MI/TO 877 295 0 564 NA/RM 255 268 564 0 Gom cụm dữ liệu bằng phân cấp min d(i,j) = d(BA,NA/RM) = 255 => merge BA and NA/RM into a new cluster called BA/NA/RM L(BA/NA/RM) = 255 m = 3 BA/NA/RM FI MI/TO BA/NA/RM 0 268 564 FI 268 0 295 MI/TO 564 295 0 Gom cụm dữ liệu bằng phân cấp min d(i,j) = d(BA/NA/RM,FI) = 268 => merge BA/NA/RM and FI into a new cluster called BA/FI/NA/RM L(BA/FI/NA/RM) = 268 m = 4 BA/FI/NA/RM MI/TO BA/FI/NA/RM 0 295 MI/TO 295 0 Gom cụm dữ liệu bằng phân cấp  Cuối cùng, quá trình gom cụm cho ra kết quả như hình sau: BA/FI/NA/RM MI/TO BA/FI/NA/RM 0 295 MI/TO 295 0 Gom cụm dữ liệu bằng phân cấp  Một số giải thuật gom cụm dữ liệu bằng phân cấp - BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies): phân hoạch các đối tượng dùng cấu trúc cây theo độ co giãn của phân giải (scale of resolution) - ROCK (Robust Clustering using linKs): gom cụm dành cho các thuộc tính rời rạc (categorical/discrete attributes), trộn các cụm dựa vào sự kết nối lẫn nhau giữa các cụm - Chameleon: mô hình động để xác định sự tương tự giữa các cặp cụm 87 Gom cụm dữ liệu bằng phân cấp  Một số vấn đề với gom cụm dữ liệu bằng phân cấp - Chọn điểm trộn/phân tách phù hợp - Khả năng co giãn (scalability)  Mỗi quyết định trộn/phân tách yêu cầu kiểm tra/đánh giá nhiều đối tượng/cụm. Tích hợp gom cụm dữ liệu bằng phân cấp với các kỹ thuật gom cụm khác Gom cụm nhiều giai đoạn (multiple-phase clustering) 88 Gom cụm dữ liệu dựa trên mật độ  Phương pháp phân hoạch và phân cấp được thiết kế để tìm các cụm có hình dạng hình cầu, khó tìm các cụm có hình dạng bất kỳ ví dụ như hình chữ S hay hình bầu dục như hình bên dưới đây 89 Gom cụm dữ liệu dựa trên mật độ  Gom cụm dữ liệu dựa trên mật độ - Mỗi cụm là một vùng dày đặc (dense region) gồm các đối tượng.  Các đối tượng trong vùng thưa hơn được xem là nhiễu. - Mỗi cụm có dạng tùy ý.  Giải thuật - DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - OPTICS (Ordering Points To Identify the Clustering Structure) - DENCLUE (DENsity-based CLUstEring) 90 Gom cụm dữ liệu dựa trên mật độ  DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - Phân tích các điểm kết nối nhau dựa vào mật độ  OPTICS (Ordering Points To Identify the Clustering Structure) - Tạo ra thứ tự các điểm dữ liệu tùy vào cấu trúc gom cụm dựa vào mật độ của tập dữ liệu  DENCLUE (DENsity-based CLUstEring) - Gom cụm dựa vào các hàm phân bố mật độ 91 Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ - ε: bán kính của vùng láng giềng của một đối tượng, gọi là ε-neighborhood. - MinPts: số lượng đối tượng ít nhất được yêu cầu trong ε-neighborhood của một đối tượng.  Nếu đối tượng có ε-neighborhood với MinPts thì đối tượng này được gọi là đối tượng lõi (core object). 92 q p ε ε p: core object (MinPts = 3) q: không là core object Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ - Directly density-reachable (khả năng đạt được trực tiếp): q có thể đạt được trực tiếp từ p nếu q trong vùng láng giềng ε-neighborhood của p và p phải là core object. 93 q p ε ε p: directly density-reachable đối với q? q: directly density-reachable đối với p? p: directly density-reachable đối với q? X q: directly density-reachable đối với p?  Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ - Density-reachable (khả năng đạt được):  Cho trước tập đối tượng D, ε và MinPts  q density-reachable từ p nếu  chuỗi các đối tượng p1, ..., pn  D với p1 = p và pn = q sao cho pi+1 directly density-reachable từ pi theo các thông số ε và MinPts, 1 ≤ i ≤ n.  Bao đóng truyền (transitive closure) của directly density- reachable  Quan hệ bất đối xứng (asymmetric relation) 94 q p p2 MinPts = 5 Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ - Density-connected (nối kết dựa trên mật độ):  Cho trước tập các đối tượng D, ε và MinPts  p, q  D  q density-connected với p nếu  o  D sao cho cả q và p đều density-reachable từ o theo các thông số ε và MinPts.  Quan hệ đối xứng 95 p q o p q o Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ 96 MinPts = 3 Gom cụm dữ liệu dựa trên mật độ  Các khái niệm dùng trong gom cụm dữ liệu dựa trên mật độ - Cụm dựa trên mật độ (density based cluster): tập tất cả các đối tượng được nối kết với nhau dựa trên mật độ.  Đối tượng thuộc về cụm có thể là core object.  Nếu đối tượng đó không là core object thì gọi là đối tượng ranh giới (border object).  Đối tượng không thuộc về cụm nào được xem là nhiễu (noise/outlier). 97 Core Border Outlier ε = 1cm MinPts = 5 Gom cụm dữ liệu dựa trên mật độ  DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - Input: tập đối tượng D, ε, MinPts - Output: density-based clusters (và noise/outliers) - Giải thuật  1. Xác định ε–neighborhood của mỗi đối tượng p  D.  2. If p là core object, tạo được một cluster.  3. Từ bất kì core object p, tìm tất cả các đối tượng density-reachable và đưa các đối tượng này (hoặc các cluster) vào cùng cluster ứng với p.  3.1. Các cluster đạt được (density-reachable cluster) có thể được trộn lại với nhau.  3.2. Dừng khi không có đối tượng mới nào được thêm vào. 98 Gom cụm dữ liệu dựa trên mật độ 99 MinPts = 4  C1   C1 Gom cụm dữ liệu dựa trên mật độ  DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - Đặc điểm ???  Các cụm có dạng và kích thước khác nhau.  Không có giả định về phân bố của các đối tượng dữ liệu  Không yêu cầu về số cụm  Không phụ thuộc vào cách khởi động (initialization)  Xử lý nhiễu (noise) và các phần tử biên (outliers)  Yêu cầu trị cho thông số nhập  Yêu cầu định nghĩa của mật độ (density)  ε và MinPts  Độ phức tạp  O(nlogn)  O(n2) 100 Gom cụm dữ liệu dựa trên mô hình  Tối ưu hóa sự phù hợp giữa dữ liệu và mô hình toán nào đó - Giả định về quá trình tạo dữ liệu  Dữ liệu được tạo ra với nhiều sự phân bố xác suất khác nhau.  Các phương pháp - Tiếp cận thống kê  Mở rộng của giải thuật gom cụm dựa trên phân hoạch k- means: Expectation-Maximization (EM) - Tiếp cận học máy: gom cụm ý niệm (conceptual clustering) - Tiếp cận mạng neural: Self-Organizing Feature Map (SOM) 101 Gom cụm dữ liệu dựa trên mô hình  Gom cụm Expectation-Maximization (EM) - Giải thuật tinh chỉnh lặp để gán các đối tượng vào các cụm (bước kỳ vọng) và ước lượng trị thông số (bước cực đại hoá).  Gom cụm ý niệm (conceptual clustering) - Tạo ra cách phân lớp các đối tượng chưa được gán nhãn dựa vào các mô tả đặc trưng cho mỗi nhóm đối tượng ứng với mỗi khái niệm (concept).  Gom cụm với mạng neural - Biểu diễn mỗi cụm là một ví dụ tiêu biểu (exemplar). - Exemplar đóng vai trò của một prototype của cụm. - Các đối tượng mới được phân bố vào một cụm nếu tương tự với exemplar của cụm đó nhất dựa trên độ đo khoảng cách. 102 Gom cụm dữ liệu dựa trên mô hình 103 Gom cụm dữ liệu dựa trên mô hình  Giải thuật Expectation-Maximization (EM) - Gán một đối tượng vào một cụm nếu tương tự trung tâm (mean) của cụm đó nhất  Dựa vào trọng số (weight) của đối tượng đối với mỗi cụm  Xác suất thành viên (probability of membership)  Không có ranh giới giữa các cụm  Trung tâm của mỗi cụm được tính dựa vào các độ đo có trọng số (weighted measures). - Hội tụ nhanh nhưng có thể tối ưu cục bộ 104 Gom cụm dữ liệu dựa trên mô hình  Giải thuật Expectation-Maximization (EM) - Input: tập n đối tượng, K (số cụm) - Output: trị tối ưu cho các thông số của mô hình - Giải thuật:  1. Khởi trị  1.1. Chọn ngẫu nhiên K đối tượng làm trung tâm của K cụm  1.2. Ước lượng trị ban đầu cho các thông số (nếu cần)  2. Lặp tinh chỉnh các thông số (cụm):  2.1. Bước kỳ vọng (expectation step): gán mỗi đối tượng xi đến cụm Ck với xác suất P(xi  Ck) với k=1..K  2.2. Bước cực đại hóa (maximization step): ước lượng trị các thông số  2.3. Dừng khi thỏa điều kiện định trước. 105 Gom cụm dữ liệu dựa trên mô hình  Giải thuật Expectation-Maximization (EM) - Giải thuật:  1. Khởi trị  2. Lặp tinh chỉnh các thông số (cụm):  2.1. Bước kỳ vọng (expectation step): gán mỗi đối tượng xi đến cụm Ck với xác suất P(xi  Ck)  2.2. Bước cực đại hóa (maximization step): ước lượng trị các thông số 106 (mk là trung tâm của cụm Ck, j = 1..K, k = 1..K) Các phương pháp gom cụm dữ liệu khác  Gom cụm cứng (hard clustering) - Mỗi đối tượng chỉ thuộc về một cụm. - Mức thành viên (degree of membership) của mỗi đối tượng với một cụm hoặc là 0 hoặc là 1. - Ranh giới (boundary) giữa các cụm rõ ràng.  Gom cụm mờ (fuzzy clustering) - Mỗi đối tượng thuộc về nhiều hơn một cụm với mức thành viên nào đó từ 0 đến 1. - Ranh giới giữa các cụm không rõ ràng (mờ - vague/fuzzy). 107 100 150 200 250 300 500 1000 1500 2000 2500 3000 3500 Top speed [km/h] W e ig h t [k g ] Sports cars Medium market cars Lorries Đánh giá chất lượng gom cụm  Các phương pháp đánh giá việc gom cụm dữ liệu - Đánh giá ngoại (external validation)  Đánh giá kết quả gom cụm dựa vào cấu trúc được chỉ định trước cho tập dữ liệu - Đánh giá nội (internal validation)  Đánh giá kết quả gom cụm theo số lượng các vector của chính tập dữ liệu (ma trận gần – proximity matrix) - Đánh giá tương đối (relative validation)  Đánh giá kết quả gom cụm bằng việc so sánh các kết quả gom cụm khác ứng với các bộ trị thông số khác nhau  Tiêu chí cho việc đánh giá và chọn kết quả gom cụm tối ưu - Độ nén (compactness): các đối tượng trong cụm nên gần nhau. - Độ phân tách (separation): các cụm nên xa nhau. 108  Các phương pháp đánh giá việc gom cụm dữ liệu - Đánh giá ngoại (external validation)  Độ đo: Rand statistic, Jaccard coefficient, Folkes and Mallows index, - Đánh giá nội (internal validation)  Độ đo: Hubert ’ s  statistic, Silhouette index, Dunn’s index, - Đánh giá tương đối (relative validation) 109 Đánh giá chất lượng gom cụm  Các phương pháp đánh giá việc gom cụm dữ liệu - Các độ đo đánh giá ngoại (external validation measures – contingency matrix) 110 J. Wu and et al. Adapting the Right Measures for K-means Clustering. KDD’09, Paris, France, July 2009. Đánh giá chất lượng gom cụm  Đánh giá kết quả gom cụm 111 Contingency matrix -Partition P: kết quả gom cụm trên n đối tượng -Partition C: các cụm thật sự của n đối tượng -nij = |PiCj|: số đối tượng trong Pi từ Cj Đánh giá chất lượng gom cụm  Đánh giá kết quả gom cụm 112 Kết quả gom cụm theo phương án I và II -Partition P: kết quả gom cụm trên n (=66) đối tượng -Partition C: các cụm thật sự của n (=66) đối tượng -nij = |PiCj|: số đối tượng trong Pi từ Cj Đánh giá chất lượng gom cụm  Đánh giá kết quả gom cụm - Entropy (trị nhỏ khi chất lượng gom cụm tốt) ??? ) 24 0 log 24 0 24 12 log 24 12 24 12 log 24 12 ( 66 24 ) 23 12 log 23 12 23 3 log 23 3 23 8 log 23 8 ( 66 23 ) 19 12 log 19 12 19 4 log 19 4 19 3 log 19 3 ( 66 19 )log( )log()(           i i ij j i iji i i ij j i ij i n n n n n n p p p p pIEntropy ??? ) 24 0 log 24 0 24 12 log 24 12 24 12 log 24 12 ( 66 24 ) 23 12 log 23 12 23 0 log 23 0 23 11 log 23 11 ( 66 23 ) 19 12 log 19 12 19 7 log 19 7 19 0 log 19 0 ( 66 19 )log( )log()(           i i ij j i iji i i ij j i ij i n n n n n n p p p p pIIEntropy 113  Gom cụm theo phương án I hay phương án II tốt??? Đánh giá chất lượng gom cụm Tóm tắt  Gom cụm nhóm các đối tượng vào các cụm dựa trên sự tương tự giữa các đối tượng.  Độ đo đo sự tương tự tùy thuộc vào kiểu dữ liệu/đối tượng cụ thể.  Các giải thuật gom cụm được phân loại thành: nhóm phân hoạch, nhóm phân cấp, nhóm dựa trên mật độ, nhóm dựa trên lưới, nhóm dựa trên mô hình, 114 Tóm tắt 115 R. Xu, D. Wunsch II. Survey of Clustering Algorithms. IEEE Transactions on Neural Networks, 16(3), May 2005, pp. 645-678.