i

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
=================== Nguyễn Thị Huế NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU
VÀ ỨNG DỤNG

LUẬN VĂN THẠC SỸ Nguyễn Thị Huế

iii

LỜI CAM ĐOAN

Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm
hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận
văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo
đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày
hoàn chỉnh trong bất cứ tài liệu nào. Hà Nội, ngày 10 tháng 04 năm 2011

Học viên
Nguyễn Thị Huế

iv

Chương 3: ỨNG DỤNG 58
KẾT LUẬN 65
TÀI LIỆU THAM KHẢO 66
PHỤ LỤC 68
v

DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT

Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh
Cơ sở dữ liệu CSDL DataBase
Khai phá tri thức trong cơ sở dữ liệu

KDD Knowledge Discovery in
Databases
Khai phá dữ liệu KPDL Data Mining
Phân cụm dữ liệu PCDL Data Clustering
Khai phá tri thức KPTT Knowledge Discovery
vi

DANH MỤC HÌNH VẼ

Hình 1.2: Quá trình khai phá tri thức 4
Hình 1.3: Qúa trình khai phá dữ liệu 7
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ 15
Hình 2.2: Khoảng cách Euclidean 24
Hình 2.3: Bảng tham số 26
Hình 2.4: Ví dụ quá trình phân hoạch với k=3 30
Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means 32
Hình 2.7: Các chiến lược phân cụm phân cấp 37
Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. 39

lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các
phương pháp quản trị và khai 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
khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining). Khai 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 trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)[5]
Kỹ thuật khai 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 kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning
from obversation) hay còn gọi là học không thầy (unupervised learning or
automatic classfication) trong trí tuệ nhân tạo. 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à chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như
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 Tin học. 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
chính cho luận văn của mình.
2 Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong

nhanh chóng. Trong những CSDL đó tiềm ẩn nhiều rất nhiều tri thức mà con người
chưa khám phá ra được. Đứng trước núi dữ liệu khổng lồ thu thập được, việc khám
phá tri thức và thông tin trở nên rất khó khăn. Chính vì lý do đó nhu cầu tìm kiếm
tri thức trong khối CSDL đã nảy sinh, nhu cầu 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 khai
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD).
Khai 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 trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)
Tuy mới ra đời nhưng khai 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,…
1.2. Khai phá tri thức và quá trình khai phá tri thức
1.2.1. Khai phá tri thức
Khai phá hay phát hiện tri thức trong các cơ sở dữ liệu 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 khám phá dữ liệu là một bước trong qui
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ố qui đị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
4 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 mẫu và/hoặc các mô hình đang tồn tại trong các cơ
sở dữ liệu nhưng 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 khai phá tri thức
Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình

ngày càng hoàn thiện hơn.
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 KPTT. 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 (knowlegde mining from
databases), trích lọc tri thức (knowlegde extraction), phân tích dữ liệu - mẫu (data-
partent analysis), khảo cứu dữ liệu (data archaeology), đào xới, nạo vét dữ liệu
(data dredging).
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 coi 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à
6 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 ở mộ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 [3][4][9].
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ự

 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 PKDL để 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 (classification), hồi quy
(regression) 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ỹ
8 thuật của học máy như cây quyết định (decision tree), mạng nơron nhân tạo (neural
network),
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ác đối tượng tìm thấy trực tiếp từ dữ liệu mà không cần bất kì một
tri thức cơ sở nào. Giống như cách tiếp cận học máy, phân cụm dữ liệu được hiểu
như là phương pháp “học không có thầy” (unsupervised learning). Không giống
như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các
mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng
quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ
(learning by example). Trong phương pháp này sẽ không thể biết kết quả các cụm

những luật về sự kết hợp giữa một hoặc nhiều thuộc tính đối với một hoặc nhiều
thuộc tính khác. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh
doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng
khoán,
Khái niệm về luật kết hợp được phát biểu diễn như sau: một luật có dạng X
Y (c%) với X và Y là tập các thuộc tính với độ tin cậy là c% được coi là luật kết
hợp nếu có ít nhất c% đối tượng trong cơ sở dữ liệu đang xét thoả mãn: nếu điều
kiện X được thoả mãn thì điều kiện Y cũng thoả mãn.
Ví dụ, luật sau là luật kết hợp: is_a(x, school)  close (x, park) (80%). Luật
trên thể hiện là: 80% trường học gần với công viên.
Như vậy, có rất nhiều kiểu thuộc tính có thể tạo thành những luật kết hợp.
Điều này khiến cho trong nhiều trường hợp số luật kết hợp tìm được vượt quá nhu
cầu. Để hạn chế số luật kết hợp tìm được, người ta sử dụng khái niệm hỗ trợ tối
thiểu  (minimum support) và độ tin cậy tối thiểu  (minimum confidence). Hai
tham số sẽ giúp loại bớt các luật tìm thấy và chỉ để lại những luật thực sự có ích cho
người sử dụng:
1. Hỗ trợ tối thiểu
10 Trong cơ sở dữ liệu lớn, có thể có rất nhiều luật giữa các đối tượng nhưng
phần lớn các luật đó chỉ có thể áp dụng vào một số nhỏ các đối tượng hoặc độ tin
cậy của luật là rất thấp. Chính vì thế mà phần lớn các luật không có ích với người sử
dụng. Ví dụ, người sử dụng có thể không quan tâm nhiều tới mối quan hệ giữa nhà
ở và trường học nếu luật đó chỉ áp dụng cho 5% số nhà ở trong khi người ta muốn ít
nhất luật đó cũng phải được áp dụng cho trên 50% các ngôi nhà. Do đó chúng ta có
thể lọc bỏ những luật kết hợp mà chỉ có thể áp dụng cho % đối tượng trong cơ sở
dữ liệu.
2. Độ tin cậy tối thiểu
Nếu một luật được đưa ra với mức độ tin cậy (độ tin cậy là tỉ lệ số đối tượng

- Mô hình mạng là gì?
- Mạng cần bao nhiêu nút?
- Số lớp ẩn sử dụng cho mạng là như thế nào?
- Khi nào thì việc học dừng?
Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu
trước khi đưa vào mạng Neural để mạng có thể hiểu được.
Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia
đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạng
có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học.
1.3.4.7. Khai phá dữ liệu sử dụng thuật giải di truyền
Đây là phương pháp không chỉ thực hiện phát hiện tri thức mà còn phục vụ
rất nhiều bài toán khác. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc
tự nhiên. Người ta mô phỏng tập dữ liệu ban đầu bằng ký tự nhị phân và gọi là
những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến nhằm biến đổi quần
thể gene ban đầu và loại đi một số gene, làm cho số lượng gene trong quần thể là
không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi
ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho lời giải tối ưu toàn cục
(khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn chế lời giải với
một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể.
Nói theo nghĩa rộng, giải thuật di truyền mô phỏng lại hệ thống tiến hoá
trong tự nhiên, chính xác hơn là giải thuật chỉ ra tập các cá thể được hình thành,
được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để
lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ.
12 Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi
trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng
Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá là cần
thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất.

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
Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực, điển hình:
 Thông tin thương mại:
o Phân tích dữ liệu tiếp thị và bán hàng và thị trường;
o Phân tích vốn đầu tư;
o Quyết định cho vay vốn;
o Phát hiện gian lận;
o v.v
 Thông tin sản xuất:
o Điều khiển và lập lịch;
o Hệ thống quản lý;
o Quản trị mạng;
o Phân tích kết quả thí nghiệm;
o V.v
 Thông tin khoa học:
o Dự báo thời tiết;
o CSDL sinh học;
14
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 (learning from obversation) hay còn gọi là học không thầy
(unsupervised learning or automatic classfication) 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 rất ít về các thông tin đó.
Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài toán
phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được áp dụng
16 vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh doanh…Sự
đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế
cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những thuật toán phân
cụm khác nhau.
Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ tương
đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong dữ liệu
không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí không gian
giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu được gọi là
tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ.
Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là bằng
nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm không tương
đồng, hàm dựa trên những thuộc tính không gian của các đối tượng dữ liệu như: toạ
độ của các đối tượng, độ cao của các đối tượng… Trong nhiều trường hợp thì hàm
không tương đồng được xem như là hàm khoảng cách không gian giữa các đối
tượng như hàm khoảng cách Euclid, hàm khoảng cách Manhattan, hàm khoảng cách
Minkowski…
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 thì người sử dụng phải lựa chọn ra một thuật toán phân

trong những thách thức lớn trong lĩnh vực KPDL.
Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu vì những
ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc
biệt của chúng. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và có dữ liệu
nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn những yêu cầu
sau:[4][14]:
 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
18  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 các 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ự vào 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 )
 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 chứa nhiều lớp đối tượng dữ
liệu phức tạp và có tính chất khác nhau.
 Thuật toán phải thích nghi với 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ố khác chiều nhau.

f p
i if ip
n nf np
x x x
x x x
x x x
 
 
 
 
 
 
 
 

Ma trận phi tương tự (Dissimilarity matrix, object-by-object structure): là
mảng n hàng, n cột. Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối
tượng i và đối tượng j, d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai
đối tượng i và j là khá "gần" nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác
nhau. Do d(i,j) = d(j,i) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau:
0
(2,1) 0
(3,1) (3,2) 0

( ,1) ( ,2) 0
d
d d
d n d n
 
 