ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH


BÁO CÁO THU HOẠCH
MÔN KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
ĐỀ TÀI:
KỸ THUẬT GOM CỤM TRONG KHAI PHÁ DỮ LIỆU
Giáo viên hướng dẫn: Sinh viên thực hiện:
PGS. TS. ĐỖ PHÚC NGUYỄN NGỌC LÂM
MSSV: CH1101098
LỚP: CH-K6
TP.HCM 11-2012
Lời mở đầu
LỜI MỞ ĐẦU
Thế kỹ 21 là thế kỹ của sự bùm nổ thông tin và chúng ta đang sống trong thế giới đầy ấp
thông tin nhưng lại đói tri thức.
Sự bùng nổ thông tin đã dẫn tới một yêu cầu cấp thiết là cần có kỹ thuật mới, công nghệ
mới để biến thông tin thành những tri thức có ích nhằm phục vụ cho sự phát triển của
nhân loại. Nhờ đó, kỹ thuật khai phá dữ liệu trở thành lĩnh vực then chốt trong ngành
công nghệ thông tin và thuyền thông.
Gom cụm dữ liệu là một trong những phương pháp quan trọng trong quá trình khám phá
tri thức.
Gom cụm dữ liệu tự động là một bài toán phức tạp và được nhiều nhà khoa học nghiên
cứu, bước đầu họ đã đưa ra một số thuật toán như: K-means, k-medoids,… và đã đạt
được một số kết quả nhất định trong việc tìm kiếm, phân loại dữ liệu. Tuy nhiên, hầu hết
các thuật toán này yêu cầu phải xác định trước số cụm cần thực thi đặt biệt là thuật toán
k-means. Ngoài ra, các kỹ thuật này còn đòi hỏi phải chọn trước số điểm làm trọng tâm
với việc chọn ngẫu nhiên làm trọng tâm sẽ cho các kết quả khác nhau. Do đó, các kết quả
có thể không chính xác, với mức độ sai số có thể rất lớn.

liệu và kho dữ liệu. Qua đó giúp em có đầy đủ kiến thức để hoàn thành bài thu hoạch này.
Nhân đây em cũng xin gửi lời cảm ơn chân thành đến gia đình, bạn bè, đồng nghiệp đã
động viên tinh thần cho em trong suốt quá trình học tập của mình.
Sau cùng, em xin kính chúc quý Thầy Cô Khoa Học Máy Tính cùng PGS. TS. Đỗ Phúc
dồi dào sức khỏe để thực hiện sứ mệnh cao đẹp của mình là truyền đạt kiến thức cho thế
hệ mai sau.
Một lần nữa em xin chân thành cảm ơn !
TP. HCM, ngày 24 tháng 11 năm 2012
Sinh viên thực hiện
(ký và ghi rõ họ tên)
Nguyễn Ngọc Lâm
Nhận xét của giáo viên hướng dẫn
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẨN
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
………
……………………………………………………………………………………………………

Hình 4.4 Ma trận distance ……………………………………………………………… 46
Hình 4.5 Bảng thông báo ma trận distance không hợp lệ ……………………………… 47
Hình 4.6 Những ô không hợp lệ trong ma trận distance được tô màu đỏ ……………… 47
Hình 4.7 Ma trận distance hợp lệ ………………………………………………………. 47
Hình 4.8 Ma trận partition …………………………………………………………… 47
Hình 4.9 Bảng thông báo ma trận partition không hợp lệ …………………………… 48
Hình 4.10 Những ô không hợp lệ trong ma trận partition được tô màu đỏ…………… 48
Hình 4.11 Các cột không hợp lệ được tô màu xanh…………………………………….48
Hình 4.12 Bảng thông báo ma trận partition không hợp lệ do cột ……………………. 48
Hình 4.13 Các dòng không hợp lệ được tô màu xanh ………………………………… 48
Hình 4.14 Bảng thông báo ma trận partition không hợp lệ do hàng ………………… 49
Hình 4.15 Ma trận distance hợp lệ ……………………………………………………. 49
Hình 4.16 Kết quả của thuật toán gom cụm ………………………………………… 49
CH1101098 – Nguyễn Ngọc Lâm Trang 9
Chương 1 – Tổng quan về gom cụm dữ liệu
chương 1. TỔNG QUAN VỀ GOM CỤM DỮ LIỆU
ội dung chương 1 trình bày tổng quan các khái niệm cơ bản về lý thuyết gom
cụm dữ liệu, đồng thời giới thiệu các lĩnh vực đã ứng dụng thành công phương
pháp gom cụm vào thực tiễn.
1.1 Gom cụm dữ liệu là gì?
Gom cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các
cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn, từ đó cung cấp
thông tin, tri thức hữu ích cho việc ra quyết định.
Do đó, gom cụm dữ liệu là một quá trình phân chia tập dữ liệu ban đầu thành các cụm dữ
liệu sao cho các đối tượng trong cùng một cụm thì phải “tương tự” nhau và các đối tượng
trong các cụm khác nhau thì “phi tương tự” với nhau. Các cụm dữ liệu được xác định
bằng kinh nghiệm hoặc bằng một số phương pháp gom cụm tự động.
Sau khi xác định các đặc tính dữ liệu, người ta sử dụng các độ đo thích hợp để xác định
khoảng cách giữa các đối tượng hay các phép đo tương tự dữ liệu. Đây chính là các hàm
để đo sự giống nhau giữa các cặp đối tượng dữ liệu. Giá trị của các hàm tính độ đo tương

1.3 Thế nào là gom cụm tốt
Một phương pháp gom cụm tốt sẽ tạo ra các cụm có chất lượng cao nếu đạt được các
tính chất sau:
 Có độ tương tự cao trong từng cụm (intra-class).
 Có độ tương tự thấp giữa các cụm (inter-class).
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.
 Cài đặt độ đo tương tự.
1.4 Các yêu cầu của gom cụm dữ liệu
Một phương pháp gom cụm được đánh giá cao nếu đạt được các yêu cầu sau:
 Có khả năng phát hiện các mẫu ẩn.
 Có khả nặng làm việc hiệu quả với một lượng dữ liệu lớn.
 Có khả năng làm việc với nhiều loại dữ liệu khác nhau.
 Có khả năng khám phá ra các cụm có phân bố theo các hình dạng khác nhau.
 Có khả năng làm việc với nhiễu cũng như các mẫu cá biệt.
 Làm việc tốt trên CSDL có số chiều cao.
CH1101098 – Nguyễn Ngọc Lâm Trang 11
Chương 1 – Tổng quan về gom cụm dữ liệu
 Chấp nhận các ràng buộc do người dùng chỉ định.
 …
1.5 Một số phương pháp gom cụm dữ liệu.
Dựa trên cách tiếp cận và thuật toán sử dụng, người ta phân các thuật toán gom cụm
theo các phương pháp chính sau:
 Phương pháp gom cụm phân hoạch.
 phương pháp gom cụm phân cấp.
 phương pháp gom cụm dựa trên mật độ.
 phương pháp gom cụm dựa trên lưới.
 phương pháp gom cụm dựa trên mô hình.
 phương pháp gom cụm có dữ liệu ràng buộc.
 …

Dữ liệu biểu diễn gene có thể được gom cụm theo hai cách
 Cách thứ nhất: là nhóm các mẫu gene giống nhau
 Cách thứ hai: là nhóm các mẫu gene khác nhau trên các hồ sơ tương ứng
1.7.2 Gom cụm dữ liệu đối với hoạt động nghiên cứu thị trường
Trong lĩnh vực nghiên cứu thị trường, gom cụm dữ liệu được sử dụng để phân
đoạn thị trường và xác định mục tiêu thị trường. Trong phân đoạn thị trường, gom
cụm dữ liệu thường được dùng để phân chia thị trường thành những cụm mang những
đặc trưng riêng biệt giúp hổ trợ cho quá trình ra quyết định chiến lược trong kinh
doanh chẳng hạn như: tìm kiếm các nhóm khách hàng quan trọng, cũng như phân loại
khách hàng thành từng nhóm khách hàng để từ đó đưa ra chiến lược kinh doanh hợp
lý nhất.
1.7.3 Gom cụm dữ liệu phục vụ trong lĩnh vực y tế
Gom cụm dữ liệu còn được áp dụng trong lĩnh vực y tế bao gồm việc thúc đẩy và
duy trì sức khỏe, cải thiện hệ thống chăm sóc sức khỏe, công tác phòng chống bệnh
tật, xác định các nhóm đối tượng có thể được hưởng lợi từ các dịch vụ cụ thể, đồng
thời xác định các nhóm đối tượng có khả năng mắc các bệnh hiểm nghèo cao do lối
sống, đều kiện kinh tế và vùng địa lý.
1.7.4 Gom cụm dữ liệu đối với hoạt động phân đoạn ảnh
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. 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.7.5 Gom cụm dữ liệu trong phân tích dữ liệu không gian
Các vệ tinh nhân tạo trên các trạm không gian có nhiệm vụ quan sát, ghi nhận
thông tin và gửi một lượng lớn dữ liệu không gian xuống trái đất để phân tích và xử
lý. Gom cụm tự động có thể giúp chúng ta tự động nhận dạng và chiết xuất các đặc
tính quan trọng trong cơ sở dữ liệu không gian góp phần vào việc dự báo thời tiết,
động đất, núi lửa, sống thần…
1.7.6 Gom cụm dữ liệu trong lập quy hoạch đô thị
Trong lập quy hoạch đô thị, gom cụm dữ liệu giúp nhận dạng các nhóm nhà theo
kiến trúc và vị trí địa lý để lập quy hoạch đô thi một cách hợp lý nhất.

 x
i
, y
i
, z
i
với i = 1, 2, …, k là các đặc trưng hoặc các thuộc tính tương ứng của các
đối tượng x, y, z.
2.1.1 Phân loại các kiểu dữ liệu dựa trên kích thước miền
 Thuộc tính liên tục: nếu miền giá trị của nó là vô hạn, không đếm được.
 Thuộc tính rời rạc: nếu miền giá trị của nó là tập hữu hạn, đếm được.
 Lớp các thuộc tính nhị phân: là một thường hợp đặc biệt của thuộc tính rời rạc
do miền giá trị của nó gồm có hai phần tử để biểu diễn giá trị true/false.
2.1.2 Phân loại các kiểu dữ liệu dựa trên độ đo
 Thuộc tính định danh: đây là dạng thuộc tính khái quát hóa của thuộc tính nhị
phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn
hai phần tử. Nghĩa là nếu x và y là hai đối tượng trong không gian k chiều thì
có thể xác định là: x y hoặc x = y.
 Thuộc tính thứ tự: là thuộc tính định danh có thêm tính thứ tự nhưng chúng
không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì có thể xác định
là: x y hoặc x = y. hoặc x > y hoặc x < y.
 Thuộc tính khoảng: với thuộc tính khoảng, chúng ta có thể xác định được một
thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao
nhiêu. Nếu x
i
> y
i
thì ta nói rằng x cách y một khoảng bằng x
i
– y

 Loại tương tự cần thiết.
Lý tưởng, mọi độ đo khoảng cách phải thỏa một trong các đều kiện sau đây:
i. d(x,y) 0 (tính chất không âm).
ii. d(x,y) = 0 nếu x = y (tính chất điểm).
iii. d(x,y) = d(y,x) (tính chất đối xứng).
iv. d(x,y) d(x,z) + d(z,y) (tính chất bất đẳng thức tam giác).
Trong cơ sở dữ liệu có thể có nhiều kiểu thuộc tính khác nhau. Một điểm dữ liệu được
đặc trưng bằng nhiều thuộc tính có kiểu cơ sở. Để xây dựng được một độ đo tốt có thể áp
dụng cho dữ liệu tổng quát thì ta phải xây dựng được độ đo tốt cho các kiểu dữ liệu cơ sở.
Chương 2 – Các kiểu dữ liệu trong bài toán gom cụm & độ đo
Các kiểu dữ liệu cơ sở bao gồm: biến trị khoảng, biến nhị phân đối xứng, biến nhị phân
bất đối xứng, biến định danh, biến thứ tự, biến tỉ lệ, biến các kiểu dữ liệu hỗn hợp, biến
dữ liệu phức tạp…
2.4 Biến trị khoảng
Các biến trị khoảng là độ đo liên tục các đại lượng tuyến tính đơn giản như trọng
lượng, nhiệt độ, chiều cao, tuổi…các đơn vị đó ảnh hưởng rất nhiều đến kết quả gom
cụm. Do đó, tùy vào lĩnh vực ứng dụng và tiêu chí của phương pháp tiếp cận mà chuẩn
hóa dữ liệu.
Thay đổi đơn vị phép đo đã dùng có thể ảnh hưởng lớn đến kết quả gom cụm.
Ví dụ: thay đổi các đơn vị đo.
 từ meter sang inche cho chiều cao.
 kilogam tới pound cho trong lượng.
 …
Nhìn chung, biểu diễn một biến dưới dạng các đơn vị đo nhỏ hơn sẽ dẫn tới một cấu trúc
gom cụm rất khác biệt. Để tránh sự phụ thuộc vào việc chọn lựa đơn vị đo dữ liệu nên
được chuẩn hóa.
Để chuẩn hóa các phép đo, một lựa chọn đó là chuyển đổi các phép đo gốc sang các biến
không đơn vị và được biểu diễn như sau:
 Tính trung bình độ lệch tuyệt đối s
f

 Khoảng cách Manhanttan là khoảng cách khi q = 1
d(i,j) =
 Khoảng cách có trọng
d(i,j) =
Khoảng cách có trọng chính là sự cải tiến của khoảng cách Minkowski, trong đó có
tính đến đến ảnh hưởng của từng thuộc tính đến khoảng cách giữa hai đối tượng.
thuộc tính có trọng số w càng lớn thì ảnh hưởng càng nhiều đến khoảng cách d. Việc
chọn trọng số tùy thuộc vào ứng dụng và mục tiêu cụ thể.
2.5 Biến nhị phân đối xứng
Biến nhị phân là biến chỉ có hai trạng thái 0 hoặc 1, true hoặc false. Biến nhị phân là
đối xứng nếu cả hai trạng thái là tương đương (về mặt ý nghĩa của ứng dụng). có nghĩa là
không có xu hướng thiên vị trạng thái 1.
Bảng sự kiện (contingenecy table) cho biến nhị phân được áp dụng cho cả đối xứng và
bất đối xứng.
Đối tượng j
Đối tượng i
1 0 sum
1 a B a + b
0 c D c + d
sum a + c b + d p
Bảng 2.1 Bảng ngẫu nhiên cho các biến nhị phân
Trong đó:
 a là số các biến bằng 1 cho cả hai đối tượng i và j
 b là số các biến bằng 1 cho đối tượng i và bằng 0 cho đối tượng j
 c là số các biến bằng 0 cho đối tượng i và bằng 1 cho đối tượng j
 d là số các biến bằng 0 cho cả hai đối tượng i và j
 p = a + b + c + d là tổng số lượng của các biến
Xử lý các biến nhị phân cũng giống như các biến tỷ lệ khoảng cách có thể gây ảnh hưởng
đến kết quả gom cụm. Do đó, cần phải tính toán độ đo phi tương tự.
Chương 2 – Các kiểu dữ liệu trong bài toán gom cụm & độ đo

Mary F Y N P N P N
Jim M Y P N N N N
Bảng 2.2 Bảng hồ sơ bệnh nhân
Trong đó:
 Name, Geneder, Fever, Cough, Test-1, Test-2, Test-3, Test-4 là các thuộc tính.
 Y (Yes): triệu chứng rõ ràng.
 N (No): hoàn toàn không có triệu chứng.
 P (Part): triệu chứng không rõ ràng hoặc ít.
Geneder là thuộc tính nhị phân đối xứng còn các thuộc tính còn lại đều là thuộc tính nhị
phân bất đối xứng.
Ta mã hóa các giá trị Y và P bằng 1 và N được gán bằng 0. Ta tính khoảng cách giữa các
bệnh nhân bằng cách sử dụng hệ số Jaccard theo bảng giá trị đã được mã hóa sau đây:
Chương 2 – Các kiểu dữ liệu trong bài toán gom cụm & độ đo
Name
(tên)
Fever
(Sốt)
Cough
(Ho)
Test-1 Test-2 Test-3 Test-4
Jack 1 0 1 0 0 0
Mary 1 0 1 0 1 0
Jim 1 1 0 0 0 0
Bảng 2.3 Bảng hồ sơ bệnh nhân sau khi mã hóa
Tính d(Jack,Mary)
 Bảng ngẫu nhiên nhị phân cho đối tượng Jack và Mary
Mary
Jack 1 0 Sum
1 2 0 2
0 1 3 4

d(i,j) =
Trong đó:
 m là thuộc tính có giá trị trùng khớp giữa hai đối tượng i và j.
 p là tổng số thuộc tính.
 Phương pháp 2: đưa biến định danh về biến nhị phân bằng cách thay đổi trạng thái
định danh bằng một biến nhị phân mới.
2.8 Biến thứ tự
Biến có thứ tự là biến trên một tập giá trị có xác định quan hệ thứ tự trên đó. Các biến
có thứ tự rất hữu ích cho việc đánh giá chất lượng một cách chủ quan mà không thể đo
được bằng cách khách quan. Một biến có thứ tự liên tục giống như một tập dữ liệu liên
tục với một tỷ lệ chưa biết.
Ví dụ: sắp xếp quan hệ trong một môn thể thao đặc thù thường cần thiết hơn các giá trị
thực tế của một độ đo đặc thù. Các biến có thứ tự có thể cũng đạt được từ việc rời rạc hóa
các con số tỷ lệ khoảng cách bằng cách chia vào trong một số các lớp hữu hạn. Các giá trị
của một biến có thứ tự có thể được ánh xạ tới các hạng. Giả sử một biến có thứ tự f có M
f
trạng thái, thì các trạng thái được sắp xếp theo thứ tự 1, …, M
f
.
Giả sử f là một biến trong tập các biến có thứ tự mô tả n đối tượng thì độ đo cho biến có
thứ tự được xây dựng như sau:
 Giá trị của f cho đối tượng thứ i là x
if
và f có M
f
trạng thái đã được sắp xếp, miêu
tả bởi thứ tự 1, …, M
f
, Thay thế x
if

= 0.33
 Z
1f =
=

= 0.66
 Z
1f =
=

= 1
Ta có: Z
if
{0, 0.33, 0.66, 1}
 Tính độ phân biệt theo các phương pháp đã biết đối với các biến trị khoảng Z
if
Name
(tên)
Athletics
(Điền kinh)
Swimming
(Bơi lội)
tennis
(Quần vợt)
Jack Vàng Bạc -
Mary Bạc Đồng Đồng
Jim Đồng Vàng Bạc
Nadal - - Vàng
Bảng sau khi được chuẩn hóa theo Z
if

Chương 2 – Các kiểu dữ liệu trong bài toán gom cụm & độ đo
 Một phương pháp tốt hơn của tiền xử lý bằng cách chuyển sang dạng logarit y
if
=
log(x
if
) sau đó mới áp dụng trực tiếp phương pháp độ đo cho các biến trị khoảng
hoặc thứ tự.
 Xử lý x
if
như dữ liệu có thứ tự liên tục và xử lý các hạng của chúng như giá trị tỷ
lệ khoảng cách.
Nhận xét: hai phương pháp sau có hiệu quả nhất, mặc dù việc lựa chọn phương pháp còn
phụ thuộc vào từng loại ứng dụng cho trước.
2.10 Biến có kiểu hỗn hợp
Cơ sở dữ liệu thực tế là sự pha trộn giữa các kiểu biến. Nhìn chung, một cơ sở dữ liệu
có thể chứa tất cả sáu kiểu biến đã được trình bày ở phần trên. Do đó, cần có một phương
pháp để tính độ đo tương tự giữa các đối tượng của các kiểu dữ liệu hỗn hợp.
Một cách tiếp cận là nhóm mỗi loại biến với nhau, thực hiện các phép phân tích cụm
riêng biệt cho mỗi kiểu biến. Đều này là khả thi nếu như các phép phân tích này nhận
được kết quả thích hợp. Tuy nhiên, trong các ứng dụng thực tế thường không thể xảy ra
một phép phân tích cụm tách biệt cho mỗi kiểu biến sẽ sinh ra các kết quả thích hợp.
Một phương pháp tiếp cận tốt hơn là xử lý tất cả các kiểu biến với nhau, thực hiện một
phép gom cụm đơn và kỹ thuật này được đề xuất bởi Ducker et al vào năm 1965 sau đó
nó được mở rộng bởi Kaufman and Rousseeuw vào năm 1990. Phép gom cụm đơn kết
hợp các biến khác nhau vào trong một ma trận không tương đồng và mang tất cả các biến
có nghĩa lên trên một tỷ lệ chung trong [0, 1].
Giả sử kiểu dữ liệu chứa p biến kiểu dữ liệu hỗn hợp thì độ không tương đồng giữa hai
đối tượng i và j được định nghĩa như sau:
d(i,j) =

if
và z
if
= và xem
xét z
if
như tỷ lệ khoảng cách.
Chương 3 – Các phương pháp gom cụm & thuật toán
Chương 3 – Các phương pháp gom cụm & thuật toán
Chương 3. CÁC PHƯƠNG PHÁP GOM CỤM & THUẬT TOÁN