Gom cụm (Clustering)

Gom cụm (Clustering) Chương 5 Bài tập lý thuyết4 Giới thiệu1 Các độ đo khoảng cách2 Phương pháp K-means3 Nội dung 3/11/2010 www.lhu.edu.vn Chương 5 Gom cụm  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? Giới thiệu 3/11/2010 www.lhu.edu.vn Chương 5 Gom cụm  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. Giới thiệu 4 Dựa trên kích thướcDựa trên khoảng cách điạ lý Ví dụ gom cụm các ngôi nhà Chương 5 Gom cụm 5Cá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 I2 … In 0.5 0.2 0.3 Giới thiệu Chương 5 Gom cụm 6  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. Tiêu chuẩn gom cụm Chương 5 Gom cụm 7  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  … Ứng dụng của gom cụm Chương 5 Gom cụm 8  Độ đ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 pp qq jxixjxixjxixjid )||...|||(|),( 2211  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 : ||...||||),( 2211 pp jxixjxixjxixjid  Độ đo khoảng cách Chương 5 Gom cụm 9 Nếu q=2, d là khoảng cách Euclid : )||...|||(|),( 22 22 2 11 pp jxixjxixjxixjid   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) Độ đo khoảng cách Chương 5 Gom cụm  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 Thuật toán gom cụm K-Means Chương 5 Gom cụm 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 Thuật toán gom cụm K-Means (1) Chương 5 Gom cụm  Đầ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 Thuật toán gom cụm K-Means (2) Chương 5 Gom cụm Thuật toán gom cụm K-Means Chương 5 Gom cụm Order ID Total 10248 440.00 10249 1863.40 10250 1552.60 10251 654.06 10252 3597.90 10253 1444.80 10254 556.62 10255 2490.50 10256 517.80 10257 1119.90 10258 1614.88 10259 100.80 10260 1504.65 10261 448.00 10262 584.00 Order ID Total 10263 1873.80 10264 695.62 10265 1176.00 10266 346.56 10267 3536.60 10268 1101.20 10269 642.20 10270 1376.00 10271 48.00 10272 1456.00 10273 2037.28 10274 538.60 10275 291.84 10276 420.00 10277 1200.80  Dữ liệu minh hoạ Thuật toán gom cụm K-Means Chương 5 Gom cụm  Kết quả chạy thử nghiệm k-means 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 C1 10255 2490.50 717.83 1004.25 2041.64 C2 10273 2037.28 1486.25 1171.05 551.03 1588.42 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 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 17 x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x x x x Nếu k quá nhỏ, Khoảng cách đến trung tâm xa Vấn đề chọn số cụm k Chương 5 Gom cụm 18 x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x x x x Nếu k vừa đúng, Khoảng cách đủ ngắn Vấn đề chọn số cụm k Chương 5 Gom cụm 19 x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x x x x Nếu k quá lớn; Khoảng cách trung bình cải thiện ít Vấn đề chọn số cụm k 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  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 Ưu điểm của K-means Chương 5 Gom cụm  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 Nhược điểm của K-means Chương 5 Gom cụm