Bài giảng Khai phá dữ liệu - Bài 5: Gom cụm - Classification - Văn Thế Thành

11 Bài 5: Gom cụm (clustering) 2
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
Các phương pháp gom cụm chính
Các phương pháp phân hoạch
Các phương pháp phân cấp
Phân tích Outlier
Tóm tắt Phân tích bằng gom cụm 3
Gom cụm: gom các đối tượng dữ liệu o Tương tự với một đối tượng khác trong cùng cụm o Không tương tự với các đối tượng trong các cụm khác o Mục tiêu của gom cụm: để gom tập các đối tượng thành các nhóm Phân tích bằng gom cụm là gì ? 24 Các ứng dụng tiêu biểu của gom cụm
Một công cụ độc lập để xem xét phân bố dữ liệu
Làm bước tiền xử lý cho các thuật toán khác 5 Các ứng dụng của gom cụm
Tiếp thị: khám phá các nhóm khác 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ý. 6 Thế nào là gom cụm tốt
Một phương pháp tốt sẽ tạo ra các cụm có chất lượng cao với: o Tương tự cao cho trong lớp (intra-class) o Tương tự thấp giữa các lớp (inter-class)
Chất lượng của kết quả gom cụm phụ thuộc vào: o độ đo tương tự sử dụng o Cài đặt độ đo tương tự
Chất lượng của phương pháp gom cụm cũng được đo bởi khả năng phát hiện vài hay tất cả các mẫu bị che ( hidden patterns) 37 Các yêu cầu của gom cụm trong KPDL (1)
Có thể thay đổi quy mô (scalability)
Khả năng làm việc các loại thuộc tính khác nhau.
Khám phá các cụm có hình dáng bất kỳ
Các yêu cầu tối thiều cho tri thức lĩnh vực nhằm xác định các tham biến nhập 8 Các nhu cầu gom cụm trong KPDL (2)
Khả năng làm việc với nhiều và outliers
Không nhạy cảm với thư tự các bản ghi nhập vào
Có số chiều cao
Hợp tác với các ràng buộc do người dùng chỉ định
Có thể diễn dịch và khả dụng 9 Tương tự và bất tương tự giữa hai đối tượng (1)
Không có định nghĩa duy nhất về sự tương tự và bất tương tự giữa các đối tượng dữ liệu
Định nghĩa về tương tự và bất tượng tự giữa các đối tượng tùy thuộc vào o Loại dữ liệu khảo sát o Loại tương tự cần thiết 410 Sự tương tự và bất tương tự (2)
Tương tự /Bất tượng tự giữa đối tượng thường được biểu diễn qua độ đo khoảng cách d(x,y)
Lý tưởng, mọi độ đo khoảng cách phải là một và phải thỏa các điều kiện sau: ),(),(),( 4. ),(),( 3. iff 0),( 2. 0),( 1. zydyxdzxd xydyxd yxyxd yxd +≤ = == ≥ 11 Loại dữ liệu trong phân tích cụm
Các biến khoảng tỉ lệ
Biến nhị phân
Các biến định danh, thứ tự, tỉ lệ
Các biến có kiểu hổn hợp
Các kiểu dữ liệu phức tạp 12 Các biến trị khoảng (1)
Các độ đo liên tục của các thang đo tuyến tính, thô
Ví dụ: trọng lượng, chiều cao, tuổi
Đơn vị đo có thể ảnh hưởng đến phân tích cụm
Để tránh sự phụ thuộc vào đơn vị đo, cần chuẩn hoá dữ liệu 513 Các biến thang đo theo khoảng (2) Chuẩn hoá các độ đo : • Tính sai biệt tuyệt đối trung bình với và • Tính độ đo chuẩn (z-score) ,)...21 1 nffff xx(xn m +++= |)|...|||(|1 21 fnffffff mxmxmxns −++−+−= f fif if s mx z − = 14 Các biến thang đo khoảng (3)
Một nhóm các độ đo khoảng cách phổ biến cho biến tỉ lệ theo khoảng là khoảng cách Minkowski. với 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ố nguên dương q q pp qq jxixjxixjxixjid )||...|||(|),( 2211 −++−+−= 15 Các biến thang đo khoảng (4)
Nếu q = 1, độ đo khoảng cách là Manhattan
Nếu q = 2, độ đo khoảng cách là khoảng cách Euclidean ||...||||),( 2211 pp jxixjxixjxixjid −++−+−= )||...|||(|),( 22 22 2 11 pp jxixjxixjxixjid −++−+−= 616 Các biến nhị phân (1)
Biến nhị phân chỉ có hai trạng thái là 0 hay 1
Bảng contingency table cho dữ liệu nhị phân: pdbcasum dcdc baba sum ++ + + 0 1 01 Object i Object j 17 Các biến nhị phân (2)
Hệ số Jaccard coefficient (tương tự không bất biến, nếu biến nhị phân là bất đối xứng): dcba cb jid +++ + =),( cba cb jid ++ + =),( 18 Các biến nhị phân (3) Ví dụ: sự bất tương tự giữa các biến nhị phân: • Bảng record bệnh nhân
Tám thuộc tính trong đó o gender là thuộc tính đối xứng o Các thuộc tính còn lại là bất đối xứng nhị phân Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N 719 Các biến nhị phân (4)
Gọi các trị Y và P được gán trị 1, và trị N được gán trị 0
Tính khoảng cách giữa các bệnh nhân dựa vào các bất đối xứng dùng hệ số Jaccard: 75.0 211 21),( 67.0 111 11),( 33.0 102 10),( = ++ + = = ++ + = = ++ + = maryjimd jimjackd maryjackd 20 Các biến định danh (nominal variables)
Mở rộng biến nhị phân để biến có thể nhận nhiều hơn hai trạng thái chẳng hạn đỏ, vàng, xanh, lục
Phương pháp 1: đối sánh đơn giản o m: # lần đối sáng, p: tổng số biến
Phương pháp 2: dùng một số lượng lớn các biến nhị phân o Tạo biến nhị phân mới cho từng trang thái định danh của p mpjid −=),( 21 Các biến thứ tự
Các biến thứ tự có thể là liên tục hay rời rạc
Thứ tự của các trị là quan trọng, ví dụ hạng
Có thể xử lý như tỷ lệ khoảng
Thay thế x if bởi hạng của chúng o Ánh xạ phạm vi của từng biến vào đoạn [0, 1] bằng cách thay thế đối tượng thứ i trong biến thứ f bởi o Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo khoảng 1 1 − − = f if if M r z } ..., ,1 { fif Mr ∈ 822 Các biến tỉ lệ
Độ đo dương trên thang phi tuyến, xấp xỉ thang đo mũ
Ví dụ AeBt hay Ae-Bt
Các phương pháp:
xử lý chúng như các biến thang đo khoảng — không phải là lựa chọn tốt ! (why?)
áp dụng biến đổi logarithmic yif = log(xif)
xử lý chúng như dữ liệu thứ tự liên tục và xử lý chúng theo hạng như thang đo khoảng 23 Các biến có kiểu hỗn hợp (1)
CSDL Có thể chứa cả sáu loại biến
Có thể dùng công thức được gán trọng để kết hợp các hiệu quả: với )( 1 )()( 1),( f ij p f f ij f ij p f djid δ δ = = Σ Σ = 1 otherwise ;0or missing, is or if 0)( = == = δ (f) ij jfif jfif f ij xx xxδ 24 Các biến có kiểu hỗn hợp (2) Đóng góp của biến f vào khoảng cách d(i,j):
Nếu f là nhị phân hay định danh:
Nếu f dựa trên khoảng: dùng khoảng cách được chuẩn hoá
Nếu f là thứ tự hay tỉ số được tỉ lệ theo:
Tính hạng r if và o xử lý z if theo tỉ lệ khoảng 1 1 − − = f if M rzif 1 otherwise ; if 0 )()( === dd fijjfiffij xx 925 Các kiểu dữ liệu phức tạp
Tất cả các đối tượng được xem xét a trong KPDL là không quan hệ => Loại dữ liệu phức tạp o Ví dụ về loại dữ liệu như vậy là dữ liệu không gian, dữ liệu đa phương tiện, dữ liệu di truyền, dữ liệu văn bản, dữ liệu chuỗi thời gian, dữ liệu văn bản và dữ liệu được thu gom từ World-Wide Web
Các độ đo tương tự và bất tương tự thường hoàn toàn khác nhau ứng với các loại dữ liệu trên 26 Các phương pháp gom cụm (clustering) chính yếu
Các phương pháp dựa trên phân hoạch
Các phương pháp phân cấp
Các phương pháp dựa trên mật độ Grid-based methods
Các phương pháp dựa trên mô hình (gom cụm khái niệm, mạng neural ) 27 Các phương pháp phân hoạch
Phương pháp phân hoạch: tạo một phân hoạch của CSDL D chứa n đối tượng thành tập gồm k cụm sao cho: o Mỗi cụm chứa ít nhất là một đối tượng o Mỗi đối tượng thuộc về đúng một cụm
Cho k, tìm một phân hoạch có k cụm nhằm tối ưu tiểu chuẩn phân hoạch được chọn 10 28 Tiêu chuẩn suy đoán chất lượng phân hoạch
Tối ưu toàn cục: liệt kê theo lối vét cạn tất cả các phân hoạch
Các phương pháp: o k-means (MacQueen’67): mỗi cụm được đại diện bằng tâm của cụm (centroid) o k-medoids (Kaufman & Rousseeuw’87): mỗi cụm được đại diện bằng một trong các đối tượng của cụm (medoid) 29 Phương pháp gom cụm k- means(1)
Đầu vào của thuật toán: số k 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 30 Phương pháp gom cụm k- means(2) Thuật toán khác cũng gồm 4 bước : 1. Chọn bất kỳ k đối tượng làm các tâm (centroids) ban đầu 2. Gán hoặc gán lại từng đối tượng vào cụm với khoảng cách gần nhất 3. Cập nhật centroids 4. Quay về bước 2, dừng khi không còn phép gán mới 11 31 Ví dụ: phương pháp gom cụm k- means 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 32 Điểm mạnh của phương pháp gom cụm k-means
Scalable tương đối: trong khi xử lý các tập dữ liệu lớn
Hiệu suất tương đối: O(tkn), với n là số đối tượng, k là số cụm, và t là số lần lặp. Thông thường k, t << n.
Thường kết thúc ở điểm tối ưu cục bộ; có thể tìm được tối ưu toàn cục dùng các kỹ thuật như thuật toán di truyền 33 Điểm yếu của phương pháp gom cụm k-means
Có thể áp dụng chỉ khi xác định được trị trung bình của các đối tượng
Cần chỉ định trức k, số các cụm
Không thể xử lý dữ liệu chuỗi và outliers
Không phù hợp để khám phá các cụm với dạng khong lồi hay cụm có kích thước khác nhau. 12 34 Các biến đổi của phương pháp gom cụm k-means(1)
Vài biến thể của k-means khác nhau ở:
Chọn k centroids ban đầu o Tính toán sự bất tương tự o Các chiến lược tính centroids cụm
Xử lý dữ liệu phân nhóm: k-modes (Huang’98) o Thay trị trung bình của cluster bằng modes o Dùng các độ đo bất tương tự mới cho các đối tượng phân nhóm o Dùng phương pháo dựa trên tần số để cập nhật modes của các cụm
Một sự kết hợp giữa dữ liệu phân lớp và dữ liệu số : phương pháp k-prototype. 35 Phương pháp gom cụm K- medoids
Đầ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. Chọn bất kỳ k đối tượng làm medoids ban đầu (các đối tượng đại diện) 2. Gán từng đối tượng còn lại vào cụm có medoid gần nhất 3. Chọn nonmedoid và thay một trong các medoids bằng nó nếu nó cải thiện chất lượng cụm 4. Quay về bước 2, dừng khi không còn phép gán mới. 36 Phương pháp phân cấp
Phương pháp phân cấp: tạo phân cấp cụm, chứ không phải là một phân hoạch đơn thuần các đối tượng
Không cần dữ liệu nhập là số cụm k
Dùng ma trận làm tiêu chuẩn gom cụm
Có thể có điều kiện kết thúc (ví dụ số cụm) 13 37 Cây các cụm
Phân cấp cụm thường tạo cây các cụm hay còn được gọi là dendrogram o Các lá của cây biểu diễn các đối tượng riêng lẻ o Các nút trong của cây biểu diễn các cụm 38 Hai loại phương pháp tạo kiến trúc cụm (1) Hai loại kỹ thuật gom cụm phân lớp : • Gộp-agglomerative (từ dưới lên): o Đưa từng đối tượng vào cluster riêng của nó (a singleton) o Trộn ở mỗi bước hai cụm tương tự nhất cho đến khi chỉ còn một cụm hay thỏa điều kiện kết thúc o Phân chia -divisive (từ trên xuống): o Bắt đầu bằng một cụm lớn chứa tất cả đối tượng. o Phân chia cụm phân biệt nhất thành các cụm nhỏ hơn và xử lý cho đến khi co n cụm hay thỏa điều kiện kết thúc 39 Hai loại phương pháp tạo kiến trúc phân cấp cụm (2) Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 Gộp-agglomerative Phân chia- divisive 14 40 Các khoảng cách trong
Thường có 3 cách được dùng để định nghĩa khoảng cách giữa các cụm o Phương pháp liên kết đơn(làng giềng gần nhất): o Phương pháp liên kết hoàn toàn(láng giềng xa nhất ): o Phương pháp liên kết trung bình (trung bình cặp nhóm không có trọng ): { } ),( min),( , yxdjid ji CyCx ∈∈= { } ),( max),( , yxdjid ji CyCx ∈∈= { } ),( ),( , yxdavgjid ji CyCx ∈∈= 41 Sức mạnh của các phương pháp phân cấp
Khái niệm đơn giản
Lý thuyết tốt
Khi cụm được trộn/tácht, quyết định là vĩnh cửu => số các phưong án khác nhau cần được xem xét bị rút giảm 42 Điểm yếu của phương pháp phân cấp
Trộn/tách các cụm là vĩnh cửu => các quyết định sai là không thể khắc phục về sau
Các phương pháp phân chia là cần thời gian tính toán
Các phương pháp là không scalable cho các tập dữ liệu lớn 15 43 Phân tích Outlier (1)
Outliers o Là các đối tương bất tương tự với phần dữ liệu còn lại o Có thể gây ra việc đo đạc hay lỗi thực hiện, hay o Là kết quả của biến đổi dữ liệu kế thừa Rất nhiều thuật toán KTDL cố gắng o Giảm ảnh hưởng của outliers o Giảm outliers 44 Phân tích Outlier (2)
Cực tiểu hóa ảnh hưởng của outliers và/hay khử đi các the outliers có thể gây ra mất mát thông tin
Có thể quan tâm đến khai thác outlier mining
Các ứng dụng của khai thác outlier o Phát hiện phạm tội (Fraud detection) o Tiếp thị o Xử lý y khoa 45
Phân tích gom cụm các đôi tượng dựa trên sự tương tự
Phân tích gom cụm có phạm vi ứng dụng to lớn
Có thể tính độ đo tương tự cho nhiều loại dữ liệu khác nhau.
Việc lựa chọn độ đo tương tự tùy thuộc vào dữ liệu được dùng và loại tương tự cần tìm Tổng kết (1) 16 46
Có thể chia các thuật toán gom cụm thành các loại partitioning methods, o Các phương pháp phân cấp o Các phương pháp dựa trên mật độ, o Các phương pháp dựa trên lưới o Các phương pháp dựa trên mô hình
Có nhiều vấn đề nghiên cứu về phân tích gom cụm Tổng kết (2)