LỜI CẢM ƠN
Để hoàn thành được khóa luận này, trước hết em xin gửi lời cảm ơn
sâu sắc nhất tới PGS.TS Trịnh Đình Thắng, đã tận tình hướng dẫn, chỉ bảo,
định hướng, đóng góp những ý kiến quý báu trong suốt quá trình thực hiện.
Em xin chân thành cảm ơn các thầy, cô giáo trong khoa Công nghệ
thông tin, trường ĐH Sư Phạm Hà Nội 2 đã quan tâm dạy dỗ và giúp đỡ em
trong suốt bốn năm học vừa qua cũng như trong thời gian em làm bài khóa
luận này. Là sinh viên ngành Công nghệ thông tin, em rất tự hào về khoa
mình học, về thầy cô giáo của mình. Em xin kính chúc các thầy, các cô luôn
mạnh khỏe, hạnh phúc và thành công. Chúc khoa Công nghệ thông tin sẽ
ngày một khang trang, vững mạnh, góp phần to lớn trong sự nghiệp đào tạo
chuyên nghiệp của trường Đại học sư phạm Hà Nội 2.
Là sinh viên lần đầu nghiên cứu khoa học, chắc chắn đề tài của em
không tránh khỏi những thiếu sót, hạn chế. Vì vậy em rất mong sự đóng góp ý
kiến của các thầy cô giáo và các bạn để đề tài của em được hoàn thiện.
Cuối cùng, em xin cảm ơn tới đại gia đình của em, đã luôn luôn động
viên, khích lệ tinh thần và tạo điều kiện tốt nhất cho em hoàn thành khóa luận
này.
Hà Nội, tháng 05 năm 2013
Sinh viên
Vũ Thị Bích Phương

1


LỜI CAM ĐOAN
Tên em là: Vũ Thị Bích Phương
Sinh viên: K35 – CNTT, trường Đại học sư phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài “Nghiên cứu các kỹ thuật phân cụm dữ liệu và ứng dụng” là
kết quả tìm hiểu và nghiên cứu của riêng em, dưới sự hướng dẫn của

2.6 Các thuật toán phân cụm dữ liệu .........................................................28
2.6.1 Thuật toán phân cụm dữ liệu dựa vào phân cụm phân cấp ............ 28
2.6.2

Thuật toán phân cụm dữ liệu mờ ................................................ 33

2.6.3

Thuật toán phân cụm dữ liệu dựa vào cụm trung tâm ................ 35

2.6.4

Thuật toán phân cụm dữ liệu dựa vào lưới ................................. 38

2.6.5

Thuật toán phân cụm dữ liệu dựa vào mật độ ............................ 42

2.6.6

Thuật toán phân cụm dữ liệu dựa trên mẫu ................................ 48
3


CHƯƠNG 3:................................................... Error! Bookmark not defined.
ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU ..............................................50
3.1 Phân đoạn ảnh ....................................................................................50
3.1.1

Định nghĩa phân đoạn ảnh ......................................................... 51

thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm
phát triển một khuynh hướng kỹ thuật mới đó là kỹ thuật khám phá tri thức và
khai phá dữ liệu. Khám phá tri thức trong cơ sở dữ liệu có thể được coi như
quá trình tìm tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trong cơ sở
dữ liệu lớn.
Kỹ thuật khám phá tri thức và khai phá dữ liệu đã và đang được nghiên
cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại
Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được
nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây. Những vấn
đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu,
phần tử dị biệt, …
Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng
trong quá trình tìm hiểu tri thức. Phân cụm đặc biệt hiệu quả khi ta không biết
về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của cụm
mà ta chưa biết hoặc biết rất ít những thông tin đó. Phân cụm được coi như
5


một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các
thuật toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp
thị, sử dụng đất, bảo hiểm, hoạch định thành phố… Hiện nay, phân cụm dữ
liệu là một hướng được nghiên cứu rất nhiều trong Công nghệ thông tin.
Chính vì lý do đó mà em chọn đề tài “Nghiên cứu các kỹ thuật phân cụm dữ
liệu và ứng dụng” là hướng nghiên cứu cho bài khóa luận của mình.
2. Mục đích nghiên cứu
- Tìm hiểu qua về quá trình khám phá tri thức và khai phá dữ liệu.
- Tìm hiểu về phân cụm dữ liệu và các thuật toán trong phân cụm dữ
liệu.
- Trên nền tảng lý thuyết về khai phá dữ liệu và một số thuật toán phân
cụm dữ liệu tiến tới đi sâu vào tìm hiểu, phân tích, đánh giá một số

em bao gồm ba chương:
Chương 1: Tổng quan về khám phá tri thức và khai phá dữ liệu.
Chương 2: Phân cụm dữ liệu và các thuật toán trong phân cụm dữ liệu.
Chương 3: Ứng dụng của phân cụm dữ liệu.

7


DANH SÁCH CÁC HÌNH
Hình 1: Quá trình khám phá tri thức
Hình 2: Quá trình khai phá dữ liệu
Hình 3: Cây CF biểu diễn trong BIRCH
Hình 4: Cụm dữ liệu khai phá bởi thuật toán CURE
Hình 5: Các bước của thuật toán Chameleon
Hình 6: Các thiết lập để xác định danh giới các cụm ban đầu
Hình 7: Ví dụ hình dạng PCDL sau khi phân cụm bằng K-means
Hình 8: Mô hình cấu trúc dữ liệu lưới
Hình 9: Mô hình thuật toán STING
Hình 10: Hình dạng các cụm được khám phá bởi DBSCAN
Hình 11: Mật độ - đến được trực tiếp
Hình 12: Mật độ - đến được
Hình 13: Mật độ - liên thông
Hình 14: Cụm và nhiễu
Hình 15: Tính năng đại diện cho clustering
Hình 16: Ảnh thang đo xám gốc
Hình 17: Biểu đồ mức xám
Hình 18: Kết quả của việc tạo ngưỡng
Hình 19: Phân đoạn ảnh bằng phân cụm dữ liệu

8


2

CSDL

Database

Cơ sở dữ liệu

3

KDD

Knowledge Discovery in

Khám phá tri thức trong

Database

cơ sở dữ liệu

4

KPDL

Data mining

Khai phá dữ liệu

5

này ngày một cấp thiết và dẫn tới sự hình thành của một lĩnh vực mới – lĩnh
vực khai phá dữ liệu (Data mining) hay khám phá tri thức trong CSDL.
Khám phá tri thức trong CSDL có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong CSDL lớn.
Tuy mới ra đời nhưng khám phá tri thức và khai phá dữ liệu đã và đang
được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên
thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng
đang được nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây.
Những vấn đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân
cụm dữ liệu, phần tử dị biệt, …

11


1.2 Khám phá tri thức và quá trình khám phá tri thức
1.2.1 Khám phá tri thức
Khám phá hay phát hiện tri thức trong CSDL là một quy trình nhận biết
các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng
hợp, hợp thức, khả ích, và có thể hiểu được. Còn khai phá dữ liệu là một bước
trong quy trình khám phá tri thức gồm có các thuật toán khai thác dữ liệu
chuyên dùng dưới một số quy định về hiệu quả tính toán chấp nhận được để
tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói một cách khác, mục đích
của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các và/hoặc các mô
hình đang tồn tại trong các CSDL nhưng vẫn còn bị che khuất bởi hàng núi dữ
liệu.
1.2.2 Quá trình khám phá tri thức
Việc khám phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình
sau:

Hình 1: Quá trình khám phá tri thức

13


1.3 Khai phá dữ liệu
1.3.1 Khai phá dữ liệu
Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khám phá
tri thức. Về bản chất nó là giai đoạn duy nhất tìm ra được thông tin mới. Việc
khai phá dữ liệu còn được coi như là việc khai phá tri thức từ dữ liệu, trích lọc
tri thức, phân tích dữ liệu – mẫu, đào xới, nạo vét dữ liệu.
Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc
các thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các
CSDL hoặc các kho dữ liệu … Khai phá dữ liệu cũng còn được gọi là một
quá trình tìm kiếm, khám phá ở nhiều góc độ để tìm ra các mối tương quan,
các mối liên hệ dưới nhiều góc độ khác nhau nhằm tìm ra các mẫu hay các mô
hình tồn tại bên trong cơ sở dữ liệu đang bị che khuất. Để trích rút các mẫu,
mô hình tiềm ẩn có tính “tri thức” ta phải tìm và áp dụng các phương pháp, kỹ
thuật khai phá sao cho các kỹ thuật và phương pháp này phải phù hợp với tính
chất, đặc trưng của dữ liệu và mục đích sử dụng. Tuy khai phá dữ liệu chỉ là
một bước trong quá trình khám phá tri thức nhưng nó lại là bước tiên quyết,
quan trọng và ảnh hưởng đến toàn bộ quá trình.
Tóm lại, khai phá dữ liệu là một quá trình tìm kiếm thông tin “tri thức”
tiểm ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế, có thể nói rằng hai thuật ngữ
khám phá tri thức và khai phá dữ liệu là tương đương nếu nói ở khía cạnh
tổng quan, còn nếu xét ở góc độ chi tiết thì khai phá dữ liệu là một giai đoạn
có vai trò quan trọng trong quá trình khám phá tri thức.
1.3.2 Mục tiêu của khai phá dữ liệu
Qua những nội dung đã trình bày ở trên, ta có thể hiểu một cách sơ lược
rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang
tính dự báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục
đích chính như sau:

phải được sao cho nhiều bản (nếu được chiết xuất vào các tệp), quản lý
tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô
hình dữ liệu thay đổi), …
Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện
việc KPDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu
diễn dưới dạng luật kết hợp, cây quyết định, … tương ứng với ý nghĩa
của nó.
1.3.4 Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá
dữ liệu
Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp
cận chính sau:
1.3.4.1

Phân lớp và dự đoán

Hướng tiếp cận này làm nhiệm vụ đưa ra các dự đoán dựa vào các suy
diễn trên dữ liệu hiện thời. Kỹ thuật này gồm có: Phân lớp, hồi quy, … Là quá
trình xếp một đối tượng vào một trong những lớp đã biết trước (ví dụ: phân
lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ
liệu thời tiết …). Đối với hướng tiếp cận này thường sử dụng một số kỹ thuật
của máy như cây quyết định, mạng nơron nhân tạo, …
1.3.4.2

Phân cụm dữ liệu

Mục tiêu của phương pháp phân cụm dữ liệu là quá trình nhóm các
điểm dữ liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu
trong cùng một cụm có độ tương đồng lớn và những điểm không cùng một
cụm có sự tương đồng là rất nhỏ. Điểm mạnh của phân cụm dữ liệu là đưa ra
được những cấu trúc có ích hoặc những cụm có đối tượng tìm thấy trực tiếp từ

sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong
tương lai. Phương pháp hồi quy khác với phân lớp dữ liệu ở chỗ, hồi
quy dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu thì chỉ
dùng để dự đoán về các giá trị rời rạc.

17


1.3.5

Thách thức – khó khăn trong khám phá tri thức và khai phá dữ liệu
KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực

tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn. Một số các
thách thức và khó khăn cần được quan tâm:
Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước rất lớn,
trong thực tế, kích thước của các tập dữ liệu thường ở mức tera - byte (hàng
ngàn giga – byte) .
- Mức độ nhiễu cao hoặc dữ liệu bị thiếu.
- Số chiều lớn.
- Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không
còn phù hợp.
- Quan hệ giữa các trường phức tạp.
1.3.6

Ứng dụng của khai phá dữ liệu
Marketing: 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 hay dịch vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu

THUẬT TOÁN PHÂN CỤM DỮ LIỆU
2.1 Khái niệm về phân cụm dữ liệu
Phân cụm dữ liệu là một kỹ thuật phát triển mạnh mẽ trong nhiều năm
trở lại đây do các ứng dụng và lợi ích to lớn của nó đối với các lĩnh vực trong
thực tế. Ở một mức cơ bản nhất, người ta định nghĩa phân cụm dữ liệu như
sau:
Phân cụm dữ liệu là một kỹ thuật trong Data Mining 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 cho việc ra quyết định.
Một cụm các đối tượng dữ liệu có thể xem như một nhóm trong nhiều
ứng dụng, ví dụ: mô hình về phân cụm các trường dựa trên tiêu chuẩn về thu
nhập và số nợ. Cụm 1 là cụm những người thu nhập cao, số nợ nhiều, cụm 2
gồm những người thu nhập cao nhưng nợ ít. Cụm 3 gồm những đối tượng thu
nhập ít những nợ nhiều.

Hình 3: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ
20


Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ
liệu một cách tự động. Không giống như phân lớp, phân cụm không cần
những thông tin được xác định trước. Nói cách khác, phân cụm là phương
pháp học từ quan sát hay còn gọi là học không thầy trong trí tuệ nhân tạo.
Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta
quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết ít về các thông tin
đó.
Bài toán phân cụm là quá trình nhóm một cơ sở dữ liệu thành những
nhóm đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thức
tế. Không có một thuật toán phân cụm nào là tốt nhất và thích hợp cho tất cả
mọi ứng dụng mà với mỗi ứng dụng khác nhau người thì người ta phải lựa

những yêu cầu sau:
- Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo
kích thước của dữ liệu.
- Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu,
phức tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số,
kiểu nhị phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu
hỗn hợp.
- Thuật toán phải có khả năng xác định được những cụm với hình dáng
bất kỳ bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình
dạng lõm, hình cầu, hình que, …
- Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các
giá trị đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất
phức tạp để xác định các giá trị vào thích hợp đối với CSDL lớn.
- Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách
khác kết quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một
tập dữ liệu, khi đưa vào xử lý cho thuật toán PCDL với các thứ tự của
các đối tượng dữ liệu ở các lần thực hiện khác nhau thì không ảnh
hưởng lớn đến kết quả phân cụm).
22


- Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người
dùng.
- Thuật toán phải làm việc được với cơ sở dữ liệu đa chiều: Thuật toán
có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau.
- Thuật toán phải dễ hiểu, dễ cài đặt và khả thi: Người sử dụng có thể
chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng.
Nghĩa là, sự phân cụm có thể cần được giải thích ý nghĩa và ứng dụng
rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt mục tiêu rất quan
trọng có thể gây ảnh hưởng tới sự lựa chọn các phương pháp phân cụm.

Thuộc tính có thứ tự: Là thuộc tính định danh nhưng có thêm thứ tự
nhưng chúng không được định lượng. Nếu x, 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.
Thuộc tính khoảng: Để đo các giá trị theo xấp xỉ tuyến tính, với thuộc
tính khoảng có thể xác định 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 xi – yi tương ứng với thuộc tính
thứ i.
Thuộc tính nhị phân: Là thuộc tính có hai giá trị 0 và 1.
Thuộc tính tính tỷ lệ: Là thuộc tính khoảng nhưng được xác định một
cách tương đối so với điểm mốc.
Trong các thuộc tính trình bày ở trên, thuộc tính định danh và thuộc
tính có thứ tự gọi là thuộc tính hạng mục, còn thuộc tính khoảng cách và
thuộc tính tỷ lệ được gọi là thuộc tính số.
Đặc biệt, còn có dữ liệu không gian là loại dữ liệu có thuộc tính số khái
quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên
quan đến không gian chứa đựng các đối tượng (ví dụ: thông tin về hình học,
24


quan hệ metric, quan hệ hướng, …) Dữ liệu không gian có thể là liên tục hoặc
rời rạc.
- Dữ liệu không gian liên tục: Bao chứa một vùng không gian.
- Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều
chiều và cho phép xác định khoảng cách giữa các đối tượng dữ liệu
trong không gian.
2.5 Phép đo độ tương tự, phi tương tự
Khi các đặc tính của dữ liệu được xác định, người ta tìm cách thích hợp
để xác định “khoảng cách” giữa các đối tượng. Đây là các hàm để đo sự giống
nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để
tính độ “tương tự” hoặc tính độ “phi tương tự” giữa các đối tượng dữ liệu. Giá