Bài giảng Khai phá dữ liệu (Datamining) - Chương 5: Gom cụm (Clustering) - Phan Mạnh Thường

Chương 5 Gom cụm (Clustering) Nội dung 1 Giới thiệu 2 Các độ đo khoảng cách 3 Phương pháp K-means 4 Bài tập lý thuyết Chương 5 Gom cụm Giới thiệu . Sự bùng nổ thông tin hiện nay do tác động của các siêu phương tiện và WWW . Các hệ thống truy vấn thông tin dựa trên việc phân nhóm, gom cụm (clustering) ra đời để làm tăng tốc độ tìm kiếm thông tin. . Do sự biến động thường xuyên của thông tin nên các thuật toán clustering đang tồn tại không thể duy trì tốt các nhóm, cụm (cluster) trong một môi trường như thế . Vấn đề đặt ra là làm thế nào để cập nhật các cluster trong hệ thống mỗi khi thông tin được cập nhật thay vì phải thường xuyên clustering lại toàn bộ dữ liệu? 7/12/2014 www.lhu.edu.vn Chương 5 Gom cụm Giới thiệu . Gom cụm (clustering) là quá trình nhóm tập đối tượng thành các cụm (cluster) có các đối tượng giống nhau. . Cho CSDL D={t1,t2,,tn} và số nguyên k, gom cụm là bài toán xác định ánh xạ f : Dg{1,,k} sao cho mỗi ti được gán vào một cụm (lớp) Kj, 1 <= j <= k . . Không giống bài toán phân lớp, các cụm không được biết trước. 7/12/2014 www.lhu.edu.vn Chương 5 Gom cụm Ví dụ gom cụm các ngôi nhà Dựa trênDựa khoảng trên kích cách thước điạ lý 4 Chương 5 Gom cụm Giới thiệu Cách biểu diễn các cụm . Phân chia bằng các đường ranh giới . Các khối cầu . Theo xác suất . Hình cây 1 2 3 . I1 0.5 0.2 0.3 I2 In 5 Chương 5 Gom cụm Tiêu chuẩn gom cụm . Phương pháp gom cụm tốt là phương pháp sẽ tạo các cụm có chất lượng : . Sự giống nhau giữa đối tượng trong cùng một cụm cao. . Giữa các cụm thì sự giống nhau thấp. . Chất lượng của kết quả gom cụm dựa trên 2 yếu tố . Độ đo sự giống nhau dùng trong phương pháp gom cụm và . Sự thi hành nó. . Chất lượng của phương pháp gom cụm còn được đo bằng khả năng phát hiện một số hay tất cả các mẫu bị ẩn, bị dấu. 6 Chương 5 Gom cụm Ứ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 . Sử dụng đất: nhận dạng các vùng đất sử dụng giống nhau khi khảo sát CSDL quả đất . Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với chi phí đền bù trung bình cao . 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ý. . Dự báo động đất: dựa trên các kết quả gom cụm các vết đứt gãy của địa tầng . 7 Chương 5 Gom cụm Độ đo khoảng cách . Độ đo khoảng cách thường dùng để xác định sự khác nhau hay giống nhau giữa hai đối tượng. . Khoảng cách Minkowski : q q q d(i,j)q (|x x | |x x | ...|x x | ) i1 j1 i2 j2 ip jp với i =(xi1, xi2, , xip) và j =(xj1, xj2, , xjp): hai đối tượng p-chiều và q là số nguyên dương . Nếu q=1, d là khoảng cách Manhattan : d(i, j)|x x ||x x |...|x x | i1 j1 i2 j2 ip jp 8 Chương 5 Gom cụm Độ đo khoảng cách . Nếu q=2, d là khoảng cách Euclid : d(i, j) (|x x |2 |x x |2 ...|x x |2) i1 j1 i2 j2 ip jp . Tính chất của độ đo khoảng cách  d(i,j)  0  d(i,i) = 0  d(i,j) = d(j,i)  d(i,j)  d(i,k) + d(k,j) 9 Chương 5 Gom cụm Thuật toán gom cụm K-Means . Không gian dữ liệu có n điểm (đối tượng) . Đã có độ đo khoảng cách giữa các điểm . k là số cụm cần phân hoạch . 1 <= k <= n Chương 5 Gom cụm Thuật toán gom cụm K-Means (1) 1. Chọn ngẫu nhiên k điểm làm trọng tâm ban đầu của k cụm 2. Gán (hoặc gán lại) từng điểm vào cụm có trọng tâm gần điểm đang xét nhất . Nếu không có phép gán lại nào thì dừng. • Vì không có phép gán lại nào có nghĩa là các cụm đã ổn định và thuật toán không thể cải thiện làm giảm độ phân biệt hơn được nữa. 3. Tính lại trọng tâm cho từng cụm 4. Quay lại bước 2 Chương 5 Gom cụm Thuật toán gom cụm K-Means (2) . Đầu vào của thuật toán: số cụm k, và CSDL có n đối tượng . Thuật toán gồm 4 bước: 1. Phân hoạch đối tượng thành k tập con/cụm khác rỗng 2. Tính các điểm hạt giống làm centroid (trung bình của các đối tượng của cụm) cho từng cụm trong cụm hiện hành 3. Gán từng đối tượng vào cụm có centroid gần nhất 4. Quay về bước 2, chất dứt khi không còn phép gán mới Chương 5 Gom cụm Thuật toán gom cụm K-Means Chương 5 Gom cụm Thuật toán gom cụm K-Means . Dữ liệu Order ID Total Order ID Total minh hoạ 10248 440.00 10263 1873.80 10249 1863.40 10264 695.62 10250 1552.60 10265 1176.00 10251 654.06 10266 346.56 10252 3597.90 10267 3536.60 10253 1444.80 10268 1101.20 10254 556.62 10269 642.20 10255 2490.50 10270 1376.00 10256 517.80 10271 48.00 10257 1119.90 10272 1456.00 10258 1614.88 10273 2037.28 10259 100.80 10274 538.60 10260 1504.65 10275 291.84 10261 448.00 10276 420.00 10262 584.00 10277 1200.80 Chương 5 Gom cụm Cluster Order ID Total ($) Mean Distance To M1 Distance To M2 Distance To M3 C1 10252 3597.90 3208.33 389.57 2111.65 3149.04 C1 10267 3536.60 328.27 2050.35 3087.74 . Kết quả chạy C1 10255 2490.50 717.83 1004.25 2041.64 C2 10273 2037.28 1486.25 1171.05 551.03 1588.42 thử nghiệm C2 10263 1873.80 1334.53 387.55 1424.94 C2 10249 1863.40 1344.93 377.15 1414.54 C2 10258 1614.88 1593.45 128.63 1166.02 k-means C2 10250 1552.60 1655.73 66.35 1103.74 C2 10260 1504.65 1703.68 18.40 1055.79 C2 10272 1456.00 1752.33 30.25 1007.14 C2 10253 1444.80 1763.53 41.45 995.94 C2 10270 1376.00 1832.33 110.25 927.14 C2 10277 1200.80 2007.53 285.45 751.94 C2 10265 1176.00 2032.33 310.25 727.14 C2 10257 1119.90 2088.43 366.35 671.04 C2 10268 1101.20 2107.13 385.05 652.34 C3 10264 695.62 448.86 2512.71 790.63 246.76 C3 10251 654.06 2554.27 832.19 205.20 C3 10269 642.20 2566.13 844.05 193.34 C3 10262 584.00 2624.33 902.25 135.14 C3 10254 556.62 2651.71 929.63 107.76 C3 10274 538.60 2669.73 947.65 89.74 C3 10256 517.80 2690.53 968.45 68.94 C3 10261 448.00 2760.33 1038.25 0.86 C3 10248 440.00 2768.33 1046.25 8.86 C3 10276 420.00 2788.33 1066.25 28.86 C3 10266 346.56 2861.77 1139.69 102.30 C3 10275 291.84 2916.49 1194.41 157.02 C3 10259 100.80 3107.53 1385.45 348.06 C3 10271 48.00 3160.33 1438.25 400.86 Chương 5 Gom cụm Ví dụ về K-Means Cho dữ liệu 1 chiều sau và k = 2 : {2,4,10,12,3,20,30,11,25} Gán ngẫu nhiên : m1=3, m2=4 K1={2,3}, K2={4,10,12,20,30,11,25}, m1=2.5, m2=16 K1={2,3,4},K2={10,12,20,30,11,25}, m1=3, m2=18 K1={2,3,4,10},K2={12,20,30,11,25}, m1=4.75, m2=19.6 K1={2,3,4,10,11,12},K2={20,30,25}, m1=7, m2=25 Dừng khi trung tâm cụm không thay đổi Chương 5 Gom cụm Vấn đề chọn số cụm k x x xx x Nếu k quá nhỏ, x x Khoảng cách x x x x x đến x x x x x x x x x x x x trung tâm xa x x x x x x x x x x x x x x x x x 17 Chương 5 Gom cụm Vấn đề chọn số cụm k x x Nếu k vừa đúng, xx x x x Khoảng cách đủ x x x x x ngắn x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 18 Chương 5 Gom cụm Vấn đề chọn số cụm k x x xx x Nếu k quá lớn; x x Khoảng cách x x x x x trung bình cải x x x x x x x x x x x x thiện ít x x x x x x x x x x x x x x x x x 19 Chương 5 Gom cụm Ví dụ về K-Means . Ví dụ 1: Cho tập điểm x1={1,3} ={x11,x12}; x2={1.5 , 3.2 }={x21,x22} x3 ={1.3 ,2.8}={x31,x32}; x4={3, 1}={x41,x42} Dùng K-Mean để gom nhóm (K=2) . Ví dụ 2: Cho tập điểm X1(4,1) ; X2(5,1) ; X3(5,2) ; X4(1,4) ; X5(1,5) ; X6(2,4) ; X7(2,5) Dùng K-Mean để gom nhóm (K=2) Chương 5 Gom cụm Ưu điểm của K-means . Tương đối nhanh . Độ phức tạp của thuật toán là O(tkn) • n: số điểm trong không gian dữ liệu • k: số cụm cần phân hoạch • t: số lần lặp (t << n) . K-Means phù hợp với các cụm có dạng hình cầu Chương 5 Gom cụm Nhược điểm của K-means . Không đảm bảo đạt được tối ưu toàn cục . kết quả đầu ra phụ thuộc vào việc chọn k điểm khởi đầu . Cần phải xác định trước số cụm k . Khó xác định số cụm thực sự mà không gian dữ liệu có thể có . Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng cụm không lồi . Không thể xử lý nhiễu và biệt lệ . Chỉ có thể áp dụng khi tính được trọng tâm