Nhận Xét Của Giáo Viên

ĐẠI HỌC QUỐC GIA
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN TP. HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT KHÓA 6
________ ________
BÀI THU HOẠCH
CHUYÊN ĐỀ: KHAI PHÁ DỮ LIỆU
Đề tài:
TÌM HIỂU VÀ CÀI ĐẶT ỨNG DỤNG
THUẬT TOÁN K_MEANS
GVHD: TS. Đỗ Phúc
SVTH: LÊ THỊ PHÚC KHOA – CH1101015
TP HCM, tháng 11 năm 2012
HVTH: CH1101015 _Lê Thị Phúc Khoa


 Bảo hiểm, tài chính: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch
vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài
chính (identifying frauds).
 WWW: Phân loại tài liệu (document classification); phân loại người dùng
web (clustering weblog);…
Các kỹ thuật phân cụm được phân loại như sau (xem hình)
GVHD: TS. Đỗ Phúc 4
HVTH: CH1101015 _Lê Thị Phúc Khoa
GVHD: TS. Đỗ Phúc 5
HVTH: CH1101015 _Lê Thị Phúc Khoa
II. Thuật toán K_means:
1. Giới thiệu thuật toán:
K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân
cụm. Tư tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng
(objects) đã cho vào K cụm (K là số các cụm được xác đinh trước, K nguyên
dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm nhóm
(centroid ) là nhỏ nhất.
d
i
x R
∈
Mục đích của thuật toán k_means là sinh ra k cụm dữ liệu {C1, C2, …., Ck}
từ một tập dữ liệu chứa n đối tượng trong không gian d chiều X = {x
i
| i = 1, 2, …,
N},
Hàm đo độ tương tự sử dụng khoảng cách Euclidean
E =
2
1

j j i j
i
c c
− ≤ −
for all i
*
= 1,… ,k}
Bước 3: Nhóm các đối tượng vào nhóm gần nhất
Bước 4: Cập nhật lại trọng tâm:
GVHD: TS. Đỗ Phúc 6
HVTH: CH1101015 _Lê Thị Phúc Khoa
( )
( 1)
( )
x
1
x
| |
t
j i
t
i j
t
S
i
c
S
+
∈
=

C
4 3
D
5 4
Bước 1. Khởi tạo tâm (centroid) cho 2 nhóm. Giả sử ta chọn A là tâm của nhóm thứ
nhất (tọa độ tâm nhóm thứ nhất c1(1,1)) và B là tâm của nhóm thứ 2 (tạo độ tâm
nhóm thứ hai c2 (2,1)).
GVHD: TS. Đỗ Phúc 8
HVTH: CH1101015 _Lê Thị Phúc Khoa
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)
Mỗi cột trong ma trận khoảng cách (D) là một đối tượng (cột thứ nhất tương ứng
với đối tượng A, cột thứ 2 tương ứng với đối tượng B,…). Hàng thứ nhất trong ma
trận khoảng cách biểu diễn khoảng cách giữa các đối tượng đến tâm của nhóm thứ
nhất (c1) và hàng thứ 2 trong ma trận khoảng cách biểu diễn khoảng cách của các
đối tượng đến tâm của nhóm thứ 2 (c2).
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:
GVHD: TS. Đỗ Phúc 9
HVTH: CH1101015 _Lê Thị Phúc Khoa
Bước 3. Nhóm các đối tượng vào nhóm gần nhất
Ta thấy rằng nhóm 1 sau vòng lặp thứ nhất gồm có 1 đối tượng A và nhóm 2 gồm
các đối tượng còn lại B,C,D.
Bước 4. Tính lại tọa độ các tâm cho các nhóm mới dựa vào tọa độ của các đối
tượng trong nhóm. Nhóm 1 chỉ có 1 đối tượng A nên tâm nhóm 1 vẫn không đổi,
c1(1,1). Tâm nhóm 2 được tính như sau:
Bước 5. Tính lại khoảng cách từ các đối tượng đến tâm mới
GVHD: TS. Đỗ Phúc 10
HVTH: CH1101015 _Lê Thị Phúc Khoa
Bước 6. Nhóm các đối tượng vào nhóm

• Luôn có ít nhất một điểm dữ liệu trong ột cụm dữ liệu.
• Các cụm không phân cấp và không bị chồng chéo dữ liệu lên nhau.
• Mọi thành viên của một cụm là gần với cụm đó hơn bất cứ một cụm nào
khác.
2. Khuyết điểm
• Không có khả năng tìm ra các cụm không lồi hoặc các cụm có hình dạng
phức tạp.
• Khó khăn trong việc xác định các trọng tâm cụm ban đầu:
- Chọn ngẫu nhiên các trung tâm cụm lúc khởi tạo
- Độ hội tụ của thuật toán phụ thuộc vào việc khởi tạo các
vector trung tâm cụm.
• Khó để chọn ra được số lượng cụm tối ưu ngay từ đầu, mà phải qua nhiều lần
thử để tìm ra được số lượng cụm tối ưu.
• Rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu.
• Không phải lúc nào mỗi đối tượng cũng chỉ thuộc về một cụm, chỉ phù hợp
với đường biên giữa các cụm rõ.
• Chi phí cho thực hiện vòng lặp tính toán khoảng cách lớn khi số cụm K và
dữ liệu phân cụm lớn.
VI. Các biến thể và cải tiến của K_means:
Các biến thể của k_means khác nhau ở:
- Chiến lược chọn k trọng tâm đầu tiên
- Phương pháp tính độ phân biệt.
- Phương pháp tính trọng tâm trong cụm.
Một số biếm thể tiêu biếu của k_means:
1. Thuật toán k-medoids:
GVHD: TS. Đỗ Phúc 13
HVTH: CH1101015 _Lê Thị Phúc Khoa
• Tương tự thuật toán K-mean
• Mỗi cụm được đại diện bởi một trong các đối tượng của cụm.
• Chọn đối tượng ở gần tâm cụm nhất làm đại diện cho cụm đó.

HVTH: CH1101015 _Lê Thị Phúc Khoa
Phần thông tin :
@relation <Tên dữ liệu><\n>.
@attribute object<\n> : tên loại đối tượng
@attribute<Tên thuộc tính><\n>
@data<\n> : bắt đầu phần dữ liệu
Phần dữ liệu:
<Tên loại đối tượng>,<Thuộc tính 1>,<Thuộc tính 2>,… , <Thuộc
tính n><\n>;
Ví dụ mẫu dữ liệu gom nhóm :
@relation drug
@attribute object
@attribute property1
@attribute property2
@data
A,1,1
B,2,1
C,4,3
D,5,4
Tài liệu tham khảo
[1]. “Giáo trình Khai Thác Dữ Liệu” TS. Đỗ Phúc, nxb Đại học quốc gia TP Hồ
Chí Minh.
GVHD: TS. Đỗ Phúc 16
HVTH: CH1101015 _Lê Thị Phúc Khoa
[2]. Slide bài giảng Khai phá dữ liệu, TS. Đỗ Phúc, trường Đại học Công nghệ
Thông tin, ĐHQG.HCM
[3].
[4].
….
GVHD: TS. Đỗ Phúc 17