zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

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

Chia sẻ: Kệ Tui | Ngày: | Loại File: PDF | Số trang:35

Báo xấu

121
lượt xem 10
download

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

Chương 5 trang bị những kiện thức về gom cụm. Thông qua chương này người học sẽ tìm hiểu: 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, một số phương pháp gom cụm. Mời 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 - Chương 5: Gom cụm

Chương 5: Gom cụm Phân tích bằng gom cụm Khái quát - 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 - Một số phương pháp gom cụm
Chương 5: Gom cụm Phân tích bằng gom cụm là gì? Gom cụm: Gom các đối tượng dữ liệu: - Tương tự với một đối tượng khác trong cùng cụm - Không tương tự với các đối tượng trong các cụm khác Mục tiêu của gom cụm: Gom tập các đối tượng dữ liệu thành các nhóm
Chương 5: Gom cụm Các ứ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 - 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ý - Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm.... - Thương mại: nhận dạng sản phẩm hàng hóa, kinh doanh,..
Chương 5: Gom cụm Thế nào là gom cụm tốt - Một phương pháp phân cụm tốt sẽ tạo ra các cụm có chất lượng cao với: * Tương tự cao trong một lớp * Tương tự thấp giữa các lớp - Chất lượng của kết quả gom cụm phụ thuộc vào: * Độ đo tương tự được sử dụng * Phương pháp cài đặt độ đo tương tự
Chương 5: Gom cụm Tương tự và bất tương tự giữa hai đối tượng? - Định nghĩa về tương tự và bất tương tự giữa các đối tượng phụ thuộc: * Loại dữ liệu khảo sát * Loại tương tự cần thiết - Tương tự/bất tương tự biểu diễn qua độ đo khoảng cách d(x,y) - Độ đo khoảng cách thỏa mãn các điều kiện: * d(x,y) ≥ 0 * d(x,y) =0 khi và chỉ khi x=y * d(x,y) = d(y,x) * d(x,z) ≤ d(x,y) + d(y,z)
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến khoảng tỷ lệ Các độ đo liên tục của các thang đo tuyến tính. Ví dụ: Trọng lượng, chiều cao, tuổi,...  Cần chuẩn hóc dữ liệu để tránh phụ thuộc đơn vị đo * Độ đo khoảng cách phổ biến cho biến tỷ lệ theo khoảng là độ đo khoảng cách Minkowski: d(i,j)= ( 𝒙𝒊𝟏 − 𝒙𝒋𝟏 𝒒 + 𝒙𝒊𝟐 − 𝒙𝒋𝟐 𝒒 + ⋯ + 𝒙𝒊𝒑 − 𝒙𝒋𝒑 𝒒) Trong đó: 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ố nguyên dương
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến khoảng tỷ lệ • Nếu q=1 thì độ đo khoảng cách là độ đo Manhatan: d(i,j)= 𝒙𝒊𝟏 − 𝒙𝒋𝟏 + 𝒙𝒊𝟐 − 𝒙𝒋𝟐 + ⋯ + 𝒙𝒊𝒑 − 𝒙𝒋𝒑 • Nếu q=2 thì độ đo khoảng cách là độ đo Euclidean: d(i,j)= ( 𝒙𝒊𝟏 − 𝒙𝒋𝟏 𝟐 + 𝒙𝒊𝟐 − 𝒙𝒋𝟐 𝟐 + ⋯ + 𝒙𝒊𝒑 − 𝒙𝒋𝒑 𝟐)
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân - Biến nhị phân chỉ có hai trạng thái là 0 và 1 Ví dụ: Giới tính - Bảng Contingency Table cho dữ liệu nhị phân Đối tượng j 1 0 sum Đối tượng i 1 a b a+b 0 c d c+d sum a+c b+d p Trong đó: a,b,c,d là số các thành phần tương ứng giữa 2 vector i và j
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân - Hệ số đối sánh đơn giản (Biến nhị phân là đối xứng) 𝒃+𝒄 d(i,j) = 𝒂+𝒃+𝒄+𝒅 - Hệ số Jaccard (Biến nhị phân bất đối xứng) 𝒃+𝒄 d(i,j) = 𝒂+𝒃+𝒄
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân Ví dụ: Cho các record bệnh nhân Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N  Ta có thể chuyển về dạng các vector nhị phân như sau: Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack 1 1 0 1 0 0 0 Mary 0 1 0 1 0 1 0 Jim 1 1 1 0 0 0 0
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến nhị phân Các vector nhị phân: Name Gender Test1 Test2 Test3 Test4 Test5 Test6 Jack 1 1 0 1 0 0 0 Mary 0 1 0 1 0 1 0 Jim 1 1 1 0 0 0 0 Bảng Contingency Table cho hai đối tượng Jack và Mary  a=2, b=1, c=1, d=3 Đối tượng Mary  Hệ số Jaccard: 1 0 sum 𝟏+𝟏 Đối 1 2 1 a+b d(Jack,Mary)= =0.5 tượng 𝟐+𝟏+𝟏 0 1 3 c+d Tương tự: Jack sum a+c b+d p d(Jack,Jim)=0.5 d(Jim,Mary)=0.8
Chương 5: Gom cụm Một số loại dữ liệu trong phân tích cụm Các biến định danh - Mở rộng biến nhị phân để biến có thể nhận nhiều hơn hai trạng thái Ví dụ: Màu sắc (đỏ, xanh, vàng, lục,....) - Phương pháp 1: Đối sánh đơn giản 𝒑−𝒎 d(i,j) = 𝒑 Trong đó: - m: là số lần giống nhau khi so sánh - p: Tổng số biến - Phương pháp 2: Dùng một số lượng các biến nhị phân. Tạo biến nhị phân mới cho từng trạng thái định danh
Chương 5: Gom cụm Một số phương pháp gom cụm Phương pháp phân hoạch Tạo phân hoạch CSDL D có n đối tượng thành tập có k cụm sao cho: - Mỗi cụm chứa ít nhất một đối tượng - Mỗi đối tượng thuộc về một cụm duy nhất - Một số phương pháp: * K-Means (MacQueen’67): Mỗi cụm được đại diện bởi trọng tâm (centroid) của cụm. * K-Medoids (Kaufman & Rousessuw’87): Mỗi cụm được đại diện bằng một trong các đối tượng của cụm
Chương 5: Gom cụm Thuật toán K-Means Thuật toán K-Means thực hiện Bắt đầu qua các bước chính sau: 1.Chọn ngẫu nhiên K tâm K=? (centroid) cho K cụm (cluster). Mỗi cụm được đại diện bằng các Chọn K tâm tâm của cụm. Thay đổi 2.Tính khoảng cách giữa các đối Khoảng cách cụm của các tượng (objects) đến K tâm các đối tượng đối tượng (Euclidean) đến tâm 3.Nhóm các đối tượng vào nhóm gần nhất Nhóm các đối Xác định lại tâm 4.Xác định lại tâm mới cho các tượng vào cụm cho các cụm nhóm gần nhất 5.Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng
Chương 5: Gom cụm Thuật toán K-Means Ví dụ: Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại được biểu diễn bởi 2 đặc trưng X và Y như sau. Mục đích của ta là nhóm các thuốc đã cho vào 2 nhóm (K=2) dựa vào các đặc trưng của chúng. Đối tượng X Y Bước 1: Khởi tạo tâm cho 2 cụm. Giả sử A là tâm A 1 1 cụm 1 - c1(1,1) và B là tâm cụm 2 - c2 (2,1) B 2 1 4.5 C 4 3 4 D 5 4 3.5 3 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X)
Chương 5: Gom cụm Thuật toán K-Means Bước 2: Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách Euclidean) – D0 A B C D 𝑿= 𝟏 𝟐 𝟒 𝟓 𝒀= 𝟏 𝟏 𝟑 𝟒 𝑿=𝟎 𝟏 𝟑. 𝟔𝟏 𝟓 c1=(1,1) – group 1 𝑫𝟎 = 𝒀= 𝟏 𝟏 𝟐. 𝟖𝟑 𝟒. 𝟐𝟒 c2=(2,1) – group 2 - Mỗi cột trong ma trận D là một đối tượng - Mỗi hàng là khoảng cách của mỗi đối tượng đến các tâm (được tính bởi Euclidean: d(i,j)= ( 𝒙𝒊𝟏 − 𝒙𝒋𝟏 𝟐 + 𝒙𝒊𝟐 − 𝒙𝒋𝟐 𝟐 + ⋯ + 𝒙𝒊𝒑 − 𝒙𝒋𝒑 𝟐) Ví dụ: Khoảng cách từ loại thuốc C=(4,3) đến tâm c1(1,1) là 3.61 và đến tâm c2(2,1) là 2.83 được tính như sau: d(C,c1) = 𝟒−𝟏 𝟐 + 𝟑−𝟏 𝟐 = 3.61 d(C,c2) = 𝟒−𝟐 𝟐 + 𝟑−𝟏 𝟐 = 2.83
Chương 5: Gom cụm Thuật toán K-Means Bước 3: Nhóm các đối tượng vào nhóm gần nhất– G0 A B C D 𝟏 𝟎 𝟎 𝟎 – group 1 𝑮𝟎 = 𝟎 𝟏 𝟏 𝟏 – group 2  Cụm 1 sau vòng lặp thứ nhất gồm có 1 đối tượng A  Cụm 2 gồm các đối tượng còn lại B,C,D.
Chương 5: Gom cụm Thuật toán K-Means Bước 4: Tính lại tọa độ các tâm cho các cụm mới dựa vào tọa độ của các đối tượng trong cụm.  Cụm 1 chỉ có 1 đối tượng A nên tâm cụm 1 vẫn không đổi c1=(1,1).  Tâm cụm 2 được tính như sau: 𝟐+𝟒+𝟓 𝟏+𝟑+𝟒 c2 = ( , ) 4.5 𝟑 𝟑 4 𝟏𝟏 𝟖 =( , ) 3.5 𝟑 𝟑 3 = (𝟑. 𝟔𝟔, 𝟐. 𝟔𝟔) 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X)
Chương 5: Gom cụm Thuật toán K-Means Bước 5: Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách Euclidean) – D1 A B C D 𝑿= 𝟏 𝟐 𝟒 𝟓 𝒀= 𝟏 𝟏 𝟑 𝟒 𝑿= 𝟎 𝟏 𝟑. 𝟔𝟏 𝟓 c1=(1,1) – group 1 𝑫𝟏 = 𝒀 = 𝟑. 𝟏𝟒 𝟐. 𝟑𝟔 𝟎. 𝟒𝟕 𝟏. 𝟖𝟗 𝟏𝟏 𝟖 c2=( , ) – group 2 𝟑 𝟑 Bước 6: Nhóm các đối tượng vào nhóm gần nhất– G1 A B C D 𝟏 𝟏 𝟎 𝟎 – group 1 𝑮𝟏 = 𝟎 𝟎 𝟏 𝟏 – group 2  Cụm 1 sau vòng lặp thứ hai gồm có 2 đối tượng A,B  Cụm 2 gồm các đối tượng còn lại C,D.
Chương 5: Gom cụm Thuật toán K-Means Bước 7: Tính lại tâm cho nhóm mới: 𝟏+𝟐 𝟏+𝟏 𝟑  Tâm cụm 1 được tính như sau: c1 = ( , ) = ( ,1) 𝟐 𝟐 𝟐 𝟒+𝟓 𝟑+𝟒 𝟗 𝟕  Tâm cụm 2 được tính như sau: c2 = ( , )=( , ) 𝟐 𝟐 𝟐 𝟐 4.5 4 3.5 3 2.5 (Y) 2 1.5 1 0.5 0 0 1 2 3 4 5 6 (X)

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.