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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

47
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Khai phá dữ liệu - Bài 5: Gom cụm (clustering)" trình bày các nội dung: 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, phương pháp phân hoạch,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai phá dữ liệu: Bài 5 - Văn Thế Thành

Bài 5: Gom cụm (clustering) 1 Phân tích bằng gom cụm Phân tích bằng gom cụm là gì ? Đối tượ tượng tương tự và không tương tự Các loạ loại dữ liệ liệu trong phân tích bằng gom cụm Các phương phá pháp gom cụm chí chính Các phương phá pháp phân hoạ hoạch Các phương phá pháp phân cấp Phân tích Outlier Tóm tắt 2 Phân tích bằng gom cụm là gì ? 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 3 1
Các ứng dụ dụng tiêu biể biểu củ của gom cụm Một công cụ cụ độ độc lậ lập để để xem xé xét phân bố bố dữ liệ liệu Làm bướ bước tiề tiền xử xử lý cho cá các thuậ thuật toá toán khá khác 4 Các ứng dụng của gom cụm Tiế thị: khám phá các nhóm khác hàng Tiếp thị 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 hiểm: nhận dạng các nhóm công ty có Bảo hiể chính sách bảo hiểm mô tô với chi phí đền bù trung bình cao Hoạ Hoạch định thà phố: nhận dạng các thành phố nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý. 5 Thế 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 intra--class) o Tương tự thấp giữa các lớp (inter 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) 6 2
Các yêu cầu của gom cụm trong KPDL (1) Có thể thể thay đổi quy mô (scalability) Khả Khả năng làm việ việc các loạ loại thuộ thuộc tính khá khác nhau. nhau. Khá Khám phá phá các cụm có hình dáng bất kỳ Các yêu cầu tối thiề thiều cho tri thứ thức lĩnh vực nhằ nhằm xác định các tham biế biến nhậ nhập 7 Các nhu cầu gom cụm trong KPDL (2) Khả Khả năng làm việ việc với nhiề nhiều và outliers Không nhạ nhạy cảm với thư tự các bản ghi nhậ nhập vào Có số chiề chiều cao Hợp tác với các ràng buộ buộc do ngườ người dùng chỉ chỉ định Có thể thể diễ diễn dịch và khả khả dụng 8 Tương tự và bất tương tự giữ tượng (1) giữa hai đối tượ 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 9 3
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: 1. d ( x, y ) ≥ 0 2. d ( x , y ) = 0 iff x = y 3. d ( x, y ) = d ( y, x ) 4. d ( x, z ) ≤ d ( x, y ) + d ( y , z ) 10 Loạ Loại dữ liệ liệu trong phân tích cụm Các biế biến khoả khoảng tỉ lệ Biế Biến nhị nhị phân Các biế biến định danh, danh, thứ thứ tự, tỉ lệ Các biế biến có kiể kiểu hổn hợp Các kiể kiểu dữ liệ liệu phứ phức tạp 11 Các biế biến trị trị khoả khoảng (1) Các độ đo liên tục của các thang đo tuyế tuyến tính, 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 12 4
Các biế khoảng (2) biến thang đo theo khoả Chuẩn hoá các độ đo : • Tính sai biệt tuyệt đối trung bình s f = 1n (| x1 f − m f | + | x2 f − m f | +...+ | xnf − m f |) với m f = 1n (x1 f + x2 f + ... + xnf ), và • Tính độ đo chuẩn (z-score) score) xif − m f zif = sf 13 Các biế biến thang đo o khoả 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. Minkowski. d(i, j) = q (| x − x |q +| x − x |q +...+| x − x |q ) i1 j1 i2 j 2 ip jp với i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là các đối tượ tượng dữ liệliệu p-chiều và q là số nguên dương 14 Các biế biến thang đo khoả khoảng (4) Nếu q = 1, độ đo khoả khoảng cách là Manhattan d (i , j ) =| x − x | + | x − x | + ...+ | x − x | i1 j1 i2 j2 ip jp Nếu q = 2, độ đo khoả khoảng cách là khoả khoảng cách Euclidean d(i, j) = (| x − x |2 +| x − x |2 +...+| x − x |2 ) i1 j1 i2 j2 ip jp 15 5
Các biế biến nhị 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: Object j 1 0 sum 1 a b a +b Object i 0 c d c+ d sum a + c b + d p 16 Các biế biến nhị 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): d (i, j) = b+c a +b+c + d d (i , j ) = b+c a+b+c 17 Các biế biến nhị nhị phân (3) Ví dụ: sự bất tương tự giữa các biến nhị phân: Name• Bảng record Gender Fever Coughbệnh Test-1 nhân 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 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 18 6
Các biế biến nhị 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: 0 +1 d ( jack , mary ) = = 0.33 2 + 0 +1 1+1 d ( jack , jim ) = = 0.67 1 +1 +1 1+ 2 d ( jim , mary ) = = 0.75 1+1+ 2 19 Các biế 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ả giản o m: # lần đối sáng,, p: tổng số biế biến d ( i , j ) = p −p m Phương pháp 2: dùng một số lượ lượng lớn các biế biến nhị nhị phân o Tạo biến nhị phân mới cho từng trang thái định danh của 20 Các biế biến thứ 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ế xif 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 rif ∈ { 1, ..., M f } o Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo khoảng r if − 1 z if = M f − 1 21 7
Các biế biến tỉ lệ Độ đo dương trên thang phi tuyế tuyến, xấp xỉ thang đo mũ Ví dụ AeBt hay Ae-Bt Các phương phá 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) 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 22 Các biế biến có kiể 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ả: Σ pf = 1δ ij( f ) d ij( f ) d (i , j ) = Σ pf = 1δ ij( f ) với δ = ( f ) ij 0 if x if or x jf is missing, or x if = x jf = 0 ; = 1 (f) otherwise δ ij 23 Các biế biến có kiể kiểu hỗn hợp (2) Đóng góp của biế biến f vào khoả khoảng cách d(i,j):: Nếu f là nhị phân hay định danh: = 0 if x if = x jf ; otherwise =1 ( f ) ( f ) d ij d ij 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 rif và zif r −1 xử lý zif theo tỉ lệ khoảng = if o M −1 f 24 8
Các kiể kiểu dữ liệ liệu phứ 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 25 Các phương phá pháp gom cụm (clustering) chí 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á pháp dựa trên mật độ Grid- Grid-based methods Các phương phá pháp dựa trên mô hình (gom cụm khái niệm, mạng neural ) 26 Các phương phá pháp phân hoạ hoạch Phương phápháp phân hoạ hoạch: 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 27 9
Tiêu chuẩ chuẩn suy đoá đoán chấ chất lượ lượng phân hoạ hoạch Tối ưu toà 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á pháp: o k-means (MacQueen’67): mỗi cụm được đại diện bằng tâm của cụm (centroid centroid) o k-medoids (Kaufman & Rousseeuw’87): mỗi cụm được đại diện bằng một trong các medoid) đối tượng của cụm (medoid 28 Phương phá pháp gom cụm k- means(1) Đầu vào của thuậ toán: số k cụm k, và CSDL thuật toá có n đối tượng Thuậ Thuật toá bước: toán gồm 4 bướ 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 29 Phương phá pháp gom cụm k- means(2) Thuật toá toán khá khác cũng gồm 4 bướ 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 30 10
Ví dụ: phương pháp gom cụm k- means 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 31 Điể Điểm mạnh của phương phá pháp gom cụm k-means Scalable tương đối: trong khi xử lý các tập dữ liệ liệu lớn Hiệ Hiệu suấ 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
Các biế biến đổi của phương phá pháp gom cụm k-means(1) Vài biế biến thể 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. 34 Phương phá pháp gom cụm K- medoids Đầu vào của thuậ thuật toá toán: số cụm k và CSDL có n đối tượng Thuật toá toán gồm 4 bướ 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. 35 Phương Phương phá 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ậ trận làm tiêu chuẩn gom cụm Có thể thể có điề điều kiệ kiện kết thú thúc (ví dụ số cụm) 36 12
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 37 Hai loạ loại phương phá pháp tạo kiế kiến trú trúc cụm (1) Hai loạ loại kỹ kỹ thuậ thuật gom cụcụm phân lớ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 38 Hai loạ loại phương phá pháp tạ tạo kiế kiến trú trúc phân cấ cấp cụ cụm (2) Step 0 Step 1 Step 2 Step 3 Step 4 Gộp-agglomerative a ab b abcde c cde d de e Phân chia- chia- divisive Step 4 Step 3 Step 2 Step 1 Step 0 39 13
Các khoả 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á pháp liên kết đơn(làng đơn giềng gần nhất): d (i, j) = minx∈C , y∈C { d ( x, y ) } i j o Phương phá pháp liên kết hoà hoàn toà toàn(láng giềng xa nhất ): d (i, j ) = max x∈C , y∈C { d ( x, y ) } i j o pháp liên kết trung bình (trung bình Phương phá cặp nhóm không có trọng ): d (i, j ) = avg x∈Ci , y∈Cj { d ( x, y ) } 40 Sức mạnh của các phương phá pháp phân cấp Khá Khái niệ niệm đơn giả giản Lý thuyế thuyết tốt Khi cụm đượđược trộ trộn/tácht, quyết định là vĩnh cửu => số các phưong án khá khác nhau cần đượ được xem xét bị rút giả giảm 41 Điể Điểm yếu của phương phá pháp phân cấp Trộ Trộn/tá n/tách các cụm là vĩnh cửu => các quyế quyết định sai là không thể thể khắ khắc phụ phục về sau Các phương phá pháp phân chia là cần thờ thời gian tính toá toán Các phương phá pháp là không scalable cho các tập dữ liệ liệu lớn 42 14
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 43 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á thác outlier o Phát hiện phạm tội (Fraud detection) o Tiếp thị o Xử lý y khoa 44 Tổng kết (1) Phân Phân tích gom cụm các đôi tượtượng dựa trên sự tương tự Phân Phân tích gom cụm có phạphạm vi ứng dụng to lớn Có thể thể tính độ đo tương tự cho nhiề nhiều loạ loại dữ liệ liệu khá khác nhau. nhau. Việ Việc lựa chọ chọn độ đo tương tự tùy thuộ thuộc vào dữ liệ liệu đượ được dùng và loạ loại tương tự cần tìm 45 15
Tổng kết (2) Có thể thể chia các thuậ thuật toá toán gom cụm thà thành các loạ loại partitioning methods, o Các phương phá pháp phân cấp o Các phương phá pháp dựa trên mật độ, o Các phương phá pháp dựa trên lướ lưới o Các phương phá pháp dựa trên mô hình Có nhiề nhiều vấn đề nghiên cứu về phân tích gom cụm 46 16