ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
MỘT SỐ PHƯƠNG PHÁP GOM CỤM DỮ LIỆU -
THUẬT TOÁN K-MEANS
Giảng viên hướng dẫn : PGS.TS Đỗ Phúc
Học viên thực hiện : Nguyễn Thị Ngọc Diễm
MSHV : CH1101075
Lớp : Cao học khóa 6
Tp Hồ Chí Minh, tháng 11 năm 2012
Mục lục
Chương 1: TỔNG QUAN VỀ GOM CỤM DỮ LIỆU
1.1 Định nghĩa gom cụm
1.1.1. Định nghĩa
- Gom cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp
các phương pháp Unsupervised Learning trong Machine Learning. Có rất
nhiều định nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể
hiểu gom cụm là các qui trình tìm cách nhóm các đối tượng đã cho vào các
cụm, sao cho các đối tượng trong cùng một cụm tương tự nhau và các đối
tượng khác cụm thì không tương tự nhau.
1.1.2. Mục tiêu
- Mục đích của gom cụm là tìm ra bản chất bên trong các nhóm của dữ liệu.
Các thuật toán gom cụm đều sinh ra các cụm. Tuy nhiên, không có tiêu chí
nào là được xem là tốt nhất để đánh hiệu của của phân tích gom cụm, điều
này phụ thuộc vào mục đích của gom cụm như: giảm kích thước dữ liệu,
khám phá thông tin hữu ích, phát hiện giá trị ngoại lai.
1.1.3. Ứng dụng
- Gom cụm dữ liệu là một công cụ thiết yếu của khai phá dữ liệu, khai phá dữ
liệu là quá trình khám phá và phân tích một khối lượng lớn dữ liệu để lấy
được các thông tin hữu ích. Gom cụm dữ liệu cũng là một vấn đề cơ bản
trong nhận dạng mẫu (pattern recognition).

- Phân đoạn ảnh là việc phân tích mức xám hay màu của ảnh thành các lát
đồng nhất (Comaniciu and Meer, 2002). Trong phân đoạn ảnh, gom cụm dữ
liệu thường được sử dụng để phát hiện biên của đối tượng trong ảnh.
1.1.3.Sinh học
- Phận nhóm động vật và thực vật dựa vào các thuộc tính của chúng.
1.1.4.Trong y tế sức khỏe tâm lý
- Phân cụm dữ liệu áp dụng trong nhiều lĩnh vực sức khỏe tâm lý, bao gồm
cả việc thúc đẩy và duy trì sức khỏe, cải thiện cho hệ thống chăm sóc sức
khỏe, và công tác phòng chống bệnh tật và người khuyết tật (Clatworthy et
al., 2005). Trong sự phát triển hệ thống chăm sóc sức khỏe, phân cụm dữ
liệu được sử dụng để xác định các nhóm của người dân mà có thể được
hưởng lợi từ các dịch vụ cụ thể (Hodges và Wotring, 2000). Trong thúc đẩy
4
y tế, nhóm phân tích được sử dụng để lựa chọn nhắm mục tiêu vào nhóm sẽ
có khả năng đem lại lợi ích cho sức khỏe cụ thể từ các chiến dịch quảng bá
và tạo điều kiện thuận lợi cho sự phát triển của quảng cáo. Ngoài ra, gom
cụm dữ liệu được sử dụng để xác định các nhóm dân cư bị rủi ro do phát
triển y tế và các điều kiện những người có nguy cơ nghèo.
1.1.5.Insurance, Finance
- 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 của khách hàng, phát hiện gian lận tài chính.
1.1.6.Phân cụm Web
- Là phân cụm trên tập các tài liệu được lấy từ Web. Có hai tình huống phân
cụm tài liệu. Tình huống thứ nhất là việc phân cụm trên toàn bộ một CSDL
có sẵn gồm rất nhiều tài liệu Web. Tình huống thứ hai thường được áp
dụng trên một tập tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về
theo một truy vấn của người dung.
1.2 Các loại dữ liệu trong gom cụm
- Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các
đặc tính hay còn gọi là thuộc tính ( Khái niệm “các kiểu dữ liệu” và “các

- Một thành phần quan trọng trong thuật toán phân cụm là phép đo khoảng
cách giữa hai điểm dữ liệu. Nếu thành phần của vectơ thể hiện dữ liệu
thuộc trong cùng một đơn vị giống nhau thì nó tồn tại khoảng cách
Euclidean có thể xác định được nhóm dữ liệu tương tự. Tuy nhiên, không
phải lúc nào khoảng cách Euclidean cũng cho kết quả chính xác.
- Tuy nhiên chú ý rằng đây không phải vấn đề đồ thị: vấn đề phát sinh từ
công thức toán học được sử dụng để kết hợp khoảng cách giữa các thành
phần đơn đặc tính dữ liệu vectơ vào trong một độ đo khoảng duy nhất mà
có thể được sử dụng cho mục đích gom cụm: các công thức khác nhau dẫn
tới những cụm khác nhau.
- Các thuật toán cần có các phép đo khoảng cách hoặc độ tương tự giữa hai
đối tượng để thực hiện gom cụm. Kiến thức miền phải được sử dụng để để
trình bày rõ ràng phép đo khoảng thích hợp cho mỗi ứng dụng. Hiện nay,
phép đo có nhiều mức độ khác nhau tùy theo từng trường hợp.
- Khoảng cách Minkowski được định nghĩa như sau:
Trong đó x, y là hai đối tượng với n là số lượng thuộc tính, và là kích
thước của dữ liệu.
- Khoảng cách Euclidean:
Là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q=2.
- Khoảng cách Manhattan:
Là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q=1.
7
- Khoảng cách Chebychev:
Trong trường hợp q = ∞, hữu ích để định nghĩa các đối tượng phi tương tự
nếu chúng khác nhau chỉ trong một kích thước biến đổi.
- Tính chất của distance(i,j):
o distance (i,j) >= 0
o distance (i,i) = 0
o distance (i,j) = distance (j,i)
o distance (i,j) <= distance (i,h) + distance (h,j)

nghĩa với một biến nhị phân mới từ mỗi biến danh nghĩa, bằng việc nhóm
các nhãn danh nghĩa thành hai lớp, một nhãn là 1, nhãn khác là 0. Xây dựng
và xem xét bảng ngẫu nhiên các sự kiện có thể xảy ra và định nghĩa các
thuộc tính của đối tượng i, j bằng các biến số nhị phân 0 và 1. Ví dụ ta có
bảng tham số sau:
j
1 0
i
1 a b a+b
0 c d c+d
a+c b+d p=a+b+c+d
Trong đó:
o a là tổng số các thuộc tính có giá trị 1 trong hai đối tượng i, j
o b là tổng số các thuộc tính có giá trị 1 trong i và giá trị 0 trong j
o c là tổng số các thuộc tính có giá trị 0 trong i và giá trị 1 trong jx
o d là tổng số các thuộc tính có giá trị 0trong hai đối tượng i, j
o p là tổng tất cả các thuộc tính của hai đối tượng i, j
- Giá trị đối xứng: Một thuộc tính nhị phân là đối xứng nếu kết quả là cả hai
đều quan trọng.
- Giá trị bất đối xứng: Một thuộc tính nhị phân là không đối xứng nếu các kết
quả của các trạng thái không quan trọng.
- Các phép đo độ tương tự của các trường hợp với dữ liệu thuộc tính nhị phân
được thực hiện bằng các cách sau:
o Hệ số đối sánh đơn giản: . cả hai đối tượng có vai trò như nhau,
nghĩa là chúng đối xứng và có cùng trọng số.
9
o Hệ số Jaccard (không đối xứng): . Tham số này loại bỏ các đối sánh
0-0.
Ví dụ:
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4

phép biến đổi sau cho mỗi thuộc tính:
Trong đó là cấp bậc của đối tượng thứ i trong biến thứ tự thứ
o Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối
với các giá trị , đây cũng chính là độ phi tương tự của thuộc tính có
thứ tự.
1.2.5. Biến định danh
- Dạng biến định danh là mở rộng của biến nhị phân nhưng có thể có nhiều
hơn 2 trạng thái. Ví dụ: Color là một thuộc tính có 4 giá trị: yellow, green,
red, blue.
- Giả sử ta gọi M là số lượng các giá trị của thuộc tính. Độ đo phi tương tự
giữa hai đối tượng i và j được định nghĩa như sau:
Trong đó:
o m là số thuộc tính đối sánh tương ứng trùng nhau
o p là tổng số các thuộc tính
- Biến định danh có thể mã hóa thành biến nhị phân bất đối xứng cho mỗi
giá trị M. Mỗi record được cho bởi một số liệu, thuộc tính giá trị nhị phân
đại diện cho giá trị đó được thiết lập để 1, trong khi các giá trị nhị phân còn
lại được thiết lập là 0.

1.2.6. Biến có kiểu hỗn hợp
- Cơ sở dữ liệu có thể chứa cả sáu loại biến
11
Yellow Green Red Blue
Record 1 0 0 1 0
Record 2 0 1 0 0
Record 3 1 0 0 0
- Có thể dùng công thức được gán trọng để kết hợp các hiệu quả:
Trong đó:
o
o Đóng góp của biến f vào khoảng cách :

Đầu vào: Số cụm k và CSDL D gồm n đối tượng.
Đầu ra: tập các cụm.
là tập các đối tượng đại diện của k cụm ở lần phân hoạch thứ i.
Partition(D, k);
1. Chọn ngẫu nhiên k tâm bất kỳ . Đặt i= 0.
2. Với mỗi điểm dữ liệu thì tìm đối tượng đại diện gần nhất và đưa
p vào cụm đó.
3. Tính lại đối tượng đại diện của các cụm

dựa vào các điểm dữ
liệu thuộc cụm.
4. Nếu thì dừng lại. Trong trường hợp ngược lại i= i+1 và quay lại
2.
- Với phương pháp này, số cụm được thiết lập là đặc trưng được lựa chọn
trước. Phương pháp phân hoạch thích hợp với bài toán tìm các cụm trong
không gian 2D. Ngoài ra, phương pháp xem xét đến khoảng cách cơ bản
giữa các điểm dữ liệu để xác định chúng có quan hệ gần nhau, hoặc không
gần nhau hay không có quan hệ.
- Nhược điểm của phương pháp này là đòi hỏi phải đưa vào tham số k và
không xử lý trên bộ dữ liệu thuộc cụm có hình dạng phức tạp hoặc mật độ
phân bố dày đặc. Ngoài ra, nếu cơ sở dữ liệu có nhiễu hoặc có đối tượng dữ
liệu quá xa tâm (outline) thì phương pháp gom cụm phân hoạch cùng không
áp dụng được vì trong các trường hợp đó, các đối tượng dữ liệu nhiễu hoặc
các đối tượng dữ liệu xa tâm (outline) sẽ làm tâm của cụm bị lệch đi. Do
đó, không đưa ra được các cụm chính xác. Thêm vào đó, thuật toán có độ
phức tạp tính toán lớn khi cần xác định kết quả tối ưu.
- Các thuật toán trong phương pháp phân hoạch: K-MEANS, PAM
(Partitioning Around Medoids), CLARA (Clustering LARge Application),
CLARANS (Clustering Large Applications based upon RANdomized
Search).

- Phương pháp này gồm có các thuật toán: AGNES (Agglomerative NEsting)
và DIANA (DIvisia ANAlysic), CURE (Clustering Using Representatives),
BIRCH (Balance Iterative Reducing and Clustering using Hierarchies),
CHAMELEON.
2.3 Phương pháp gom cụm dữ liệu mờ
- Trong cuộc sống, chúng ta đã gặp rất nhiều ứng dụng của bài toán gom
cụm. Chẳng hạn như trong ngành bưu điện, hàng ngày bưu điện phải phân
loại thư theo mã nước, trong mã nước lại phân loại theo mã tỉnh/thành phố,
sau đó khi thư về đến bưu điện tỉnh thì bưu điện tỉnh lại phải phân loại thư
theo quận/huyện để gửi đi, đến bưu điện quận/huyện lại phân loại thư theo
xã/phường để gửi thư. Đó chính là một ứng dụng của bài toán gom cụm rõ.
Vậy bài toán gom cụm rõ là gì?
- Ta có thể định nghĩa bài toán gom cụm rõ như sau: Cho tập dữ liệu mẫu X,
ta kiểm tra các điểm dữ liệu xem nó giống với đặc điểm của nhóm nào nhất
thì ta gán điểm dữ liệu đó vào trong nhóm đó. Nhưng trong thực tế không
phải lúc nào bài toán gom cụm rõ cũng áp dụng được. Chẳng hạn, ta có
phép phân loại sau: Những người đi xe máy xịn thì thuộc nhóm người giàu,
những người đi xe máy thường thuộc nhóm người bình dân. Vậy người
nghèo mà đi xe máy xịn thì chúng ta xếp người đó vào nhóm nào? Vì vậy,
chúng ta cần đưa vào khái niệm bài toán gom cụm mờ.
Trong các phương pháp gom cụm đã giới thiệu trong chương trước, mỗi
phương pháp gom cụm phân hoạch một tập dữ liệu ban đầu thành các cụm
dữ liệu có tính tự nhiên và mỗi đối tượng dữ liệu chỉ thuộc về một cụm dữ
liệu, phương pháp này chỉ phù hợp với việc khám phá ra các cụm có mật độ
cao và rời nhau, với đường biên giữa các cụm được xác định tốt. Tuy nhiên,
15
trong thực tế, đường biên giữa các cụm có thể mờ, các cụm có thể chồng
lên nhau, nghĩa là một số các đối tượng dữ liệu thuộc về nhiều các cụm
khác nhau, do đó mô hình này không mô tả được dữ liệu thực. Vì vậy
người ta đã áp dụng lý thuyết về tập mờ trong gom cụm dữ liệu để giải

QUEst).
2.5 Phương pháp dựa trên mật độ
- Phương pháp dựa trên mật độ gom cụm các đối tượng dữ liệu dựa trên mối
quan hệ của các đối tượng dữ liệu với các điểm lân cận của các điểm dữ
liệu đó. Gom cụmdựa trên mật độ (có điều kiện cụm cục bộ) giống như các
điểm có khả năng liên kết theo mật độ (density-connected). Một cụm được
mở rộng theo hướng bất kỳ mà mật độ dẫn theo, do đó phương pháp này có
khả năng tìm ra các cụm có hình dạng phức tạp. Mặc dù chỉ duyệt tập dữ
liệu một lần nhưng phương pháp này có khả năng loại bỏ phần tử nhiễu và
phần tử ngoại lai. Phương pháp này phù hợp với các đối tượng có trường
dữ liệu kiểu số, dữ liệu thuộc tính chỉ là thuộc tính mô tả thêm cho các đối
tượng không gian.
Phương pháp này có thể tiếp cận theo 2 hướng chính: liên kết dựa trên mật
độ và hàm mật độ.
- Các thuật toán thuộc phương pháp này bao gồm DBSCAN (Density Based
Spatial Clustering of Application with Noise), OPTICS (Ordering Points to
Identify the Clustering Structure), DENCLUE (Density-based
CLUstEring), DBCLASD (Distribution Based Clustering of Large Spatial
Databased).
2.6 Phương pháp dựa trên mô hình
- Phương này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình
sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến
lược gom cụm phân hoạch hoặc gom cụm phân cấp, dựa trên cấu trúc hoặc
mô hình mà chúng giả định về tập dữ liệu và cách chúng hiệu chỉnh các mô
hình này để nhận dạng ra các phân hoạch. Phương pháp gom cụm dựa trên
mô hình cố gắng khớp giữa các dữ liệu với mô hình toán học, nó dựa trên
giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản.
Các thuật toán gom cụm dựa trên mô hình có hai cách tiếp cận chính: mô
hình thống kê và mạng nơron. Phương pháp này gần giống với phương
pháp gom cụm dựa trên mật độ, vì chúng phát triển các cụm riêng biệt

trong lĩnh vực thống kê năm 1967, mục đích của tuật toán K-MEANS
19
là sinh ra k cụm dữ liệu {C
1
, C
2
, …, C
k
} từ một tập dữ liệu ban đầu
gồm n đối tượng trong không gian d chiều X
i
= (x
i1
, x
i2
, …, x
id
),
),1( ni
=
, sao cho hàm tiêu chuẩn:
∑∑
= ∈
−=
k
i Cx
i
i
mxDE
1

Bước 2: Tính khoảng cách
Đối với mỗi đối tượng X
i
(1 ≤ i ≤ n), tính khoảng cách của nó
tới mỗi trọng tâm m
j
với j=1,…,k, sau đó tìm trọng tâm gần
nhất đối với mỗi đối tượng.
20
Bước 3: Cập nhật lại trong tâm
Đối với mỗi j=1,…,k, cập nhật trọng tâm cụm m
j
bằng cách
xác định trung bình cộng của các vector đối tượng dữ liệu.
Bước 4: Điều kiện dừng
Lặp lại bước 2 và bước b cho đến khi các trọng tâm của cụm
không thay đổi.
- Thuật toán K-MEANS được chứng minh là hội tụ và có độ phức tạp
tính toán là: O((n.k.d).
τ
.
Τ
flop
). Trong đó, n là số đối tượng dữ liệu, k là
số cụm dữ liệu, d là số chiều của vector đối tượng dữ liệu,
τ
là số vòng
lặp,
Τ
flop

số
lượng điểm vào textbox như hình
dưới. Ví dụ ta nhập vào 60 điểm, sau đó nhấn button Generation để
phát
sinh
60
điểm được biểu diễn bằng chấm tròn
đỏ như hình vẽ:
22
-
- Chọn
số
lượng
trọng tâm bằng cách click chuột trực
tiếp vào hình. Ví dụ bên dưới ta click vào 3 vị trí có dấu hình vuông màu
vàng.
- Ta có kết quả như hình dưới
- Các button First, Pre, Next, Last để hiển
thị kết quả gom cụm ở những lần khác. Ví dụ Thuật toán kmeans cho ví dụ
này chạy tổng cộng 3 bước, và hình sau thể hiện sự gom cụm ở bước thứ 2
và thứ 1 của thuật toán.
23
- Một ví dụ khác cho việc gom cụm 80 điểm ngẫu nhiêu với k=6.
24
Chương 4: KẾT LUẬN
Tiểu luận trình bày tổng quan, lý thuyết về gom cụm dữ liệu, mục tiêu cũng như
ứng dụng của gom cụm vào thực tiễn. Tiếp đó trình bày các kiểu dữ liệu dùng
trong gom cụm bao gồm: các biến trị khoảng, biến nhị phânm biến thứ tự, biến
định danh, biến tỷ lệ và biến hỗn hợp. Tiểu luận còn giới thiệu tổng quát các
phương pháp được dùng trong phân cụm dữ liệu gồm 6 phương pháp là: Phương