ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
   BÀI THU HOẠCH
Môn học
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU

Đề tài
TÌM HIỂU THUẬT TOÁN GOM CỤM K-MEAN
VÀ CÀI ĐẶT CHƯƠNG TRÌNH MINH HỌA

Giảng viên hướng dẫn : PGS.TS Đỗ Phúc
Học viên thực hiện : Bùi Thị Hoàng Anh
Mã số : CH1101065
Lớp : Cao học – CNTT K6
HCM, 11/2012



1.2 Khai phá dữ liệu và các khái niệm liên quan

3

1.2.1 Khái niệm khai phá dữ liệu

3

1.2.2 Các hướng tiếp cận trong khai phá dữ liệu

3

1.2.2 Các lĩnh vực ứng dụng

4

Chương 2: PHÂN CỤM DỮ LIỆU VÀ THUẬT TOÁN K-MEANS

5

2.1 Khái quát gom cụm dữ liệu

5

2.1.1 Khái niệm

5

2.1.2 Chuẩn hóa các độ đo


3.1 Chương trình thử nghiệm thuật toán K-Means

15

3.2 Chương trình ứng dụng thuật toán K-Means trong bài toán
phân đoạn ảnh

16

KẾT LUẬN

20

TÀI LIỆU THAM KHẢO

21

PHỤ LỤC

22

1

LỜI NÓI ĐẦU

Trong vài thập niên gần đây, công nghệ thông tin được ứng dụng
rộng rãi trong nhiều lĩnh vực: tài chính, sản xuất, kinh doanh, truyền thông,
y tế, Sự phát triển không ngừng của ngành công nghệ thông tin và các
lĩnh vực liên quan dẫn đến hệ quả là khối lượng thông tin lưu trữ ngày

tri thức trong cơ sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được các
tri thức chính là kỹ thuật khai phá dữ liệu.
Quá trình phát hiện tri thức gồm một số bước sau:
- Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết
- Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại
- Lựa chọn dữ liệu: Các dữ liệu có liên quan đến quá trình phân
tích được lựa chọn từ cơ sở dữ liệu
- Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng
phù hợp cho quá trình xử lý
- Khai phá dữ liệu: Là một trong những bước quan trọng nhất,
trong đó sử dụng những phương pháp thông minh để lựa chọn ra
những mẫu dữ liệu.
- Ước lượng mẫu: Quá trình đánh giá kết quả thông qua một độ đo
nào đó
- Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan cho
người dùng.
3

1.2 Khai phá dữ liệu và các khái niệm liên quan
1.2.1 Khái niệm khai phá dữ liệu
Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay
khám phá tri thức từ một lượng lớn dữ liệu. Thuật ngữ Data Mining ám chỉ
việc tìm một tập nhỏ có giá trị từ một lượng lớn các dữ liệu thô. Khai phá
dữ liệu chỉ là một bước trong quá trình phát hiện tri thức.
1.2.2 Các hướng tiếp cận trong khai phá dữ liệu
Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau:
 Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp
và tóm tắt khái niệm.
Ví dụ: tóm tắt văn bản.
 Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở

 Tài chính và thị trường chứng khoán (finance & stock market)
 Bảo hiểm (insurance): 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
 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
 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ý

5

Chương 2: GOM CỤM DỮ LIỆU
VÀ THUẬT TOÁN K-MEANS
2.1 Khái quát gom cụm dữ liệu
2.1.1 Khái niệm
Gom cụm là quá trình phân chia một tập dữ liệu ban đầu thành các
cụm dữ liệu thỏa mãn:
a. Các đối tượng trong một cụm “tương tự” nhau.
b. Các đối tượng khác cụm thì “không tương tự” nhau.
Mục đích của gom cụm là xác định được bản chất của việc nhóm các
đối tượng trong một tập dữ liệu không có nhãn. Gom cụm không dựa trên
một tiêu chuẩn chung nào, mà dựa vào tiêu chí do người dùng cung cấp
trong từng trường hợp.
 Thế nào là một 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:
- Tương tự cao cho trong lớp (intra-class)
- 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 tương tự sử dụng

2.1.2 Chuẩn hóa các độ đo
 Tính sai biệt tuyệt đối trung bình

với và
 Tính độ đo chuẩn (z-score)  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.

),(),(),( 4.
),(),( 3.
iff 0),( 2.
0),( 1.
zydyxdzxd
xydyxd
yxyxd
yxd




|)| |||(|
1
21 fnffffff
mxmxmx
n
s 
,)
21

2211

7 với i = (x
i1
, x
i2
, …, x
ip
) và j = (x
j1
, x
j2
, …, x
jp
) là các đối tượng
dữ liệu p-chiều và q là số nguyên dương.
 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 2.1.3 Một số ứng dụng của gom cụm dữ liệu
Kỹ thuật gom cụm có thể áp dụng trong rất nhiều lĩnh vực như:
 Thương mại: Xác định các nhóm khách hàng (khách hàng tiềm
năng, khách hàng giá trị, phân loại và dự đoán hành vi khách
hàng, ) sử dụng sản phẩm của công ty để có chiến lược kinh
doanh hiệu quả hơn.

i
x
j
x
i
x
j
i
d







)|| |||(|),(
22
22
2
11 pp j
x
i
x
j
x
i
x
j
x

liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng
trong không gian cùng với các quan hệ, các thuộc tính, các hoạt
động của chúng.
9

Một số thuật toán PCDL dựa trên cấu trúc lưới điển hình là:
STING, WAVECluster, CLIQUE,…
2.2 Gom cụm phân hoạch
Gom cụm phân hoạch là phân một tập dữ liệu có n phần tử cho trước
thành k tập con dữ liệu (k ≤ n), mỗi tập con biểu diễn một cụm.
Các cụm hình thành trên cơ sở làm tối ưu giá trị hàm đo độ tương tự
sao cho:
i) Các đối tượng trong một cụm là tương tự.
ii) Các đối tượng trong các cụm khác nhau là không tương tự nhau.
Đặc điểm:
- Mỗi đối tượng chỉ thuộc về một cụm.
- Mỗi cụm có tối thiểu một đối tượng.
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.
Một số thuật toán điển hình:
- K-mean

(MacQueen’67): mỗi cụm được đại diện bằng tâm
của cụm.
- 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.
2.3 Thuật toán k-means
Thuật toán k-means là thuật toán gom cụm lặp đơn giản. Nó phân
mảnh tập dữ liệu cho trước thành k cụm, giá trị k do người dùng xác định.
Thuật toán dễ thực hiện, thi hành nhanh, dễ thích nghi và phổ biến trong
thực tế. Đây là một trong những thuật toán kinh điển trong khai thác dữ

d(X1,V1) = sqrt(sqr(1 - 1) + sqr(1 - 1)) = 0.0
d(X1,V2) = sqrt(sqr(1 - 2) + sqr(1 - 1)) = 1.0
+ Do d(X1,V1) < d(X1,V2) nên X1 thuộc cụm C1
d(X2,V1) = sqrt(sqr(2 - 1) + sqr(1 - 1)) = 1.0
d(X2,V2) = sqrt(sqr(2 - 2) + sqr(1 - 1)) = 0.0
11

+ Do d(X2,V2) < d(X2,V1) nên X2 thuộc cụm C2
d(X3,V1) = sqrt(sqr(4 - 1) + sqr(3 - 1)) = 3.61
d(X3,V2) = sqrt(sqr(4 - 2) + sqr(3 - 1)) = 2.83
+ Do d(X3,V2) < d(X3,V1) nên X3 thuộc cụm C2
d(X4,V1) = sqrt(sqr(5 - 1) + sqr(4 - 1)) = 5.0
d(X4,V2) = sqrt(sqr(5 - 2) + sqr(4 - 1)) = 4.24
+ Do d(X4,V2) < d(X4,V1) nên X4 thuộc cụm C2
Tăng n lên 1, ta có ma trận:
U1 X1 X2 X3 X4
C1 1 0 0 0
C2 0 1 1 1

Lặp lại bước 2 đối với U1: Tìm các vector trọng tâm.
* Gọi V1 là vector trọng tâm của cụm C1
V11 = (m11*X11 + m12*X21 + m13*X31 + m14*X41) /
(m11+m12+m13+m14)
= (1*1 + 0*2 + 0*4 + 0*5)/(1+0+0+0) = 1/1 = 1.0
V12 = (m11*X12 + m12*X22 + m13*X32 + m14*X42) /
(m11+m12+m13+m14)
= (1*1 + 0*1 + 0*3 + 0*4)/(1+0+0+0) = 1/1 = 1.0
Vậy V1 = (1.0, 1.0)
* Gọi V2 là vector trọng tâm của cụm C2
V21 = (m21*X11 + m22*X21 + m23*X31 + m24*X41) /

= (1*1 + 1*2 + 0*4 + 0*5)/(1+1+0+0) = 3/2 = 1.5
V12 = (m11*X12 + m12*X22 + m13*X32 + m14*X42) /
(m11+m12+m13+m14)
= (1*1 + 1*1 + 0*3 + 0*4)/(1+1+0+0) = 2/2 = 1.0
Vậy V1 = (1.5, 1.0)
* Gọi V2 là vector trọng tâm của cụm C2
V21 = (m21*X11 + m22*X21 + m23*X31 + m24*X41) /
(m21+m22+m23+m24)
= (0*1 + 0*2 + 1*4 + 1*5)/(0+0+1+1) = 9/2 = 4.5
13

V22 = (m21*X12 + m22*X22 + m23*X32 + m24*X42) /
(m21+m22+m23+m24)
= (0*1 + 0*1 + 1*3 + 1*4)/(0+0+1+1) = 7/2 = 3.5
Vậy V2 = (4.5, 3.5)
Bước 3: Tính khoảng cách các điểm Xi so với các vector trọng tâm.
d(X1,V1) = sqrt(sqr(1 - 1.5) + sqr(1 - 1.0)) = 0.5
d(X1,V2) = sqrt(sqr(1 - 4.5) + sqr(1 - 3.5)) = 4.3
+ Do d(X1,V1) < d(X1,V2) nên X1 thuộc cụm C1
d(X2,V1) = sqrt(sqr(2 - 1.5) + sqr(1 - 1.0)) = 0.5
d(X2,V2) = sqrt(sqr(2 - 4.5) + sqr(1 - 3.5)) = 3.54
+ Do d(X2,V1) < d(X2,V2) nên X2 thuộc cụm C1
d(X3,V1) = sqrt(sqr(4 - 1.5) + sqr(3 - 1.0)) = 3.2
d(X3,V2) = sqrt(sqr(4 - 4.5) + sqr(3 - 3.5)) = 0.71
+ Do d(X3,V2) < d(X3,V1) nên X3 thuộc cụm C2
d(X4,V1) = sqrt(sqr(5 - 1.5) + sqr(4 - 1.0)) = 4.61
d(X4,V2) = sqrt(sqr(5 - 4.5) + sqr(4 - 3.5)) = 0.71
+ Do d(X4,V2) < d(X4,V1) nên X4 thuộc cụm C2
Tăng n lên 1, ta có ma trận:
U3 X1 X2 X3 X4

3. Áp dụng K-Mean
Kết quả trả về là các cụm tài liệu và các trọng tâm tương ứng.
 Phân vùng ảnh
15

Chương 3: CÀI ĐẶT THỬ NGHIỆM THUẬT TOÁN K-
MEANS

3.1 Chương trình thử nghiệm thuật toán K-Means
3.1.1 Giới thiệu
- Chương trình demo thuật toán K-Means được thiết kế trên nền
ngôn ngữ lập trình Visual Basic. Các chức năng chính của
chương trình bao gồm:
- Nhập số liệu đầu vào:
 Số cụm k
 Tọa độ các điểm
 Tọa độ vector trọng tâm ban đầu (nếu có)
 Ma trận phân hoạch ban đầu (nếu có)
- Thực thi thuật toán K-Means
- Hiển thị kết quả:
 Chi tiết các bước thực hiện thuật toán từ lúc bắt đầu đến
khi kết thúc
3.1.2 Phụ lục giao diện của chương trình

16

3.1.3 Hướng dẫn sử dụng
- Bước 1: Nhập số cụm và số điểm vào các ô nhập tương ứng.
- Bước 2: Nhập tọa độ các điểm vào các ô nhập tọa độ điểm
- Bước 3 (không bắt buộc): Nếu bài toán có cho trước vector trọng

Trong khoảng 30 năm trở lại đây đã có rất nhiều các thuật toán được
đề xuất để giải quyết bài toán phân đoạn ảnh. Các thuật toán hầu hết đều
dựa vào hai thuộc tính quan trọng của mỗi điểm ảnh so với các điểm lân
cận của nó, đó là: sự khác (dissimilarity) và giống nhau (similarity). Các
phương pháp dựa trên sự giống nhau của các điểm ảnh được gọi là phương
pháp miền (region-based methods), còn các phương pháp dựa trên sự khác
nhau của các điểm ảnh được gọi là các phương pháp biên (boundary-based
methods).
Trong phạm vi bài thu hoạch này em xin phép được trình bày thuật
toán K-means để giải quyết bài toán phân đoạn ảnh như sau:
 Input:
 Ảnh có kích thước m*n.
 Số cụm (k) muốn phân đoạn.
 Output:
 Ảnh được phân thành k đoạn có màu sắc tương đồng
nhau.
3.2.2 Giới thiệu chương trình
- Chương trình này trình bày kết quả thực nghiệm gom cụm hình
ảnh theo màu sắc trên cơ sở thuật toán gom cụm K-Means.
Chương trình cài đặt được viết trên ngôn ngữ lập trình C# trên
nền tảng .Net Framework của Microsoft. Chương trình đã thực
thi được và cho kết quả gom cụm theo màu sắc của hình ảnh đưa
vào. Tuy nhiên, do thời gian hạn chế nên chương trình chỉ dừng
lại ở mức độ gom cụm hình ảnh theo màu sắc. Các chức năng
chính của chương trình bao gồm:
18

- Nhập số liệu đầu vào:
 Số cụm k
 Chọn ảnh cần phân đoạn

thuật toán gom cụm khác như: k-modes, k-prototype, Đặc biệt "Chương
trình demo ứng dụng thuật toán K-Means trong phân đoạn ảnh" có thể
được phát triển thành phần mềm xử lý ảnh chụp từ máy CT phục vụ cho
công tác chẩn đoán bệnh trong y học. 21

TÀI LIỆU THAM KHẢO 1. TS. Đỗ Phúc, Giáo trình khai thác dữ liệu, Nhà xuất bản Đại Học
Quốc Gia TP.HCM, 2006
2. TS. Đỗ Phúc, Bài giảng Môn học Khai Phá Dữ Liệu, Trường Đại Học
Công Nghệ Thông Tin, 2007
3. http://www.google.com.vn/url?sa=t&rct=j&q=&esrc=s&source=web
&cd=1&ved=0CC4QFjAA&url=http%3A%2F%2Ffit.hcmup.edu.vn
%2F~haits%2FXu%2520Ly%2520Anh%2FPhan%2520doan%2520a
nh.doc&ei=PyivUKWpN8PpiAeQ0IDQAg&usg=AFQjCNG9xDWo
wKHDvPM0YpWEiU7TnhWHcw&sig2=Vtk0lDYicUPuBZQZOtny
GA

22

PHỤ LỤC

Phụ lục 1: Source code chương trình demo thuật toán k_means
Option Explicit
Dim Bound() As Currency


Private Sub chkBietTrongTam_Click()
Dim i As Byte

23

If Trim(txtSoCum.Text) = "" Then Exit Sub
Call Hide_Vector
If chkBietTrongTam.Value <> 0 Then
For i = 0 To Val(txtSoCum.Text) - 1
V1(i).Visible = True
lblV1(i).Visible = True
lblV2(i).Visible = True
txtV1(i).Visible = True
txtV2(i).Visible = True
Next i
End If
End Sub

Private Sub Hide_Vector()
Dim i As Byte

For i = 0 To 9
V1(i).Visible = False
lblV1(i).Visible = False
lblV2(i).Visible = False
txtV1(i).Visible = False
txtV2(i).Visible = False
txtV1(i).Text = ""
txtV2(i).Text = ""
Next i