i

MỤC LỤC
MỤC LỤC.........................................................................................................i
CÁC CỤM TỪ VIẾT TẮT............................................................................iii
DANH MỤC CÁC HÌNH VẼ........................................................................iv
LỜI NÓI ĐẦU..................................................................................................1
CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU..............................3
1.1. Khai phá dữ liệu và phát hiện tri thức................................................3
1.1.1. Khai phá dữ liệu ...............................................................................3
1.1.2. Quá trình khám phá tri thức..............................................................4
1.1.3. Khai phá dữ liệu và các lĩnh vực liên quan......................................5
1.1.4. Các phương pháp áp dụng trong Khai phá dữ liệu...........................6
1.1.5. Những chức năng chính của KPDL..................................................7
1.1.6. Các ứng dụng của Khai phá dữ liệu .................................................9
1.2. Phương pháp phân cụm trong Khai phá dữ liệu.............................10
1.2.1. Khái quát về phân cụm dữ liệu .....................................................10
1.2.2. Ứng dụng của phân cụm dữ liệu.....................................................13
1.2.3. Các yêu cầu đối với phương pháp phân cụm dữ liệu.....................14
1.3. Khai phá Web......................................................................................15
1.3.1. Khai phá Web ...............................................................................15
1.3.2. Khái niệm khai phá Web................................................................16
1.3.3. Đặc trưng của khai phá Web..........................................................17
1.3.4. Các đối tượng khai phá Web..........................................................18
Tổng kết chương 1.....................................................................................18
CHƯƠNG II. MỘT SỐ PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU.........20
2.1. Phân cụm phân hoạch:......................................................................21
2.1.1. Thuật toán K-means........................................................................21
2.1.2. Thuật toán K-medoids....................................................................24
2.2. Phân cụm phân cấp.............................................................................26
2.2.1. Thuật toán BIRCH .........................................................................27

3.3.2. Khai phá và quản lý cộng đồng Web..............................................61
3.4. Áp dụng thuật toán phân cụm dữ liệu trong tìm kiếm và phân cụm
tài liệu Web.................................................................................................65
3.4.1. Hướng tiếp cận bằng phương pháp phân cụm dữ liệu....................66
3.4.2. Quá trình tìm kiếm và phân cụm tài liệu........................................67
Tổng kết chương 3......................................................................................74
KẾT LUẬN ...................................................................................................74
TÀI LIỆU THAM KHẢO.............................................................................77


iii

CÁC CỤM TỪ VIẾT TẮT
STT
1

Viết tắt
CSDL

2

KDD

3
4

KPDL
PCDL

Cụm từ tiếng Anh

31
Hình 3.1. Phân loại khai phá Web
50
Hình 3.2. Quan hệ trực tiếp giữa 2 trang Web
60
Hình 3.3. Độ tương đồng trích dẫn


v

60
Hình 3.4. Độ tương tự chỉ mục
60
Hình 3.5. Đồ thị phân đôi của Hup và Authority
62
Hình 3.6. Sự kết hợp giữa Hup và Authority
63
Hình 3.7. Các bước phân cụm kết quả tìm kiếm trên Web
67


1

LỜI NÓI ĐẦU
Khai phá dữ liệu là lĩnh vực được quan tâm nhiều trong thời gian gần
đây, xuất phát từ sự bùng nổ về thông tin, sự phát triển nhanh chóng của khoa
học kỹ thuật. Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên khổng lồ
và đồ sộ. Vấn đề đặt ra cần có những công cụ, phương pháp để khai thác các
nguồn tri thức đó ngày càng trở nên cấp thiết cho nghành khoa học công nghệ
thông tin trên toàn thế giới.

3

CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khai phá dữ liệu và phát hiện tri thức
1.1.1. Khai phá dữ liệu
Trong những thập kỷ gần đây, sự phát triển rộng khắp của các cơ sở dữ
liệu đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này người ta
bắt đầu đề cập đến việc khủng hoảng trong quá trình phân tích dữ liệu tác
nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao trong tổ
chức chính phủ, tài chính, thương mại, khoa học…
Đúng như John Naisbett cảnh báo “Chúng ta đang chìm ngập trong dữ
liệu mà vẫn đói trí thức”. Lượng dữ liệu khổng lồ thực sự là nguồn tài nguyên
có nhiều giá trị bởi thông tin là yếu tố then chốt phục vụ cho mọi hoạt động
quản lý, kinh doanh, phát triển sản xuất và dịch vụ,.. nó giúp người điều hành
và quản lý có những hiểu biết về môi trường và tiến trình hoạt động trong các
lĩnh vực kinh doanh từ đó sẽ quyết định tác động đến quá trình hoạt động như
thế nào để đạt được các mục tiêu một cách hiệu quả và bền vững.
KPDL là một lĩnh vực được nghiên cứu, nhằm tự động khai thác thông
tin, tri thức hữu ích, tiềm ẩn từ những cơ sở dữ liệu lớn từ đó làm thúc đẩy
khả năng sản xuất, kinh doanh, cạnh tranh trong xã hội hiện nay. Các kết quả
nghiên cứu khoa học và những ứng dụng thành công trong KDD cho thấy
KPDL là một lĩnh vực phát triển bền vững, mang lại lợi ích và có nhiều triển
vọng, đồng thời có ưu thế hơn hẵn so với các công cụ tìm kiếm dữ liệu truyền
thống. Hiện nay, KPDL đã ứng dụng ngày càng rộng rãi trong các lĩnh vực
như thương mại, tài chính, y học, viễn thông, tin – sinh,.. Các phương pháp
được áp dụng trong lĩnh vực KPDL phần lớn được thừa kế từ CSDL, học
máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê và tính toán nâng
cao...



vào phân khoảng...), Sau bước này dữ liệu sẽ được nhất quán, đầy đủ, được
rút gọn và được rời rạc hoá.


5

Biến đổi dữ liệu: Đây là bước chuẩn hoá và làm mịn dữ liệu về dạng
thuận lợi nhất nhằm phục vụ quá trình khai phá ở bước sau.
Khai phá dữ liệu: Đây là bước áp dụng các phương pháp phân tích
(như các phương pháp của học máy) nhằm để khai thác dữ liệu, trích chọn
những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem
là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ
trong dữ liệu đã khám phá ở bước trên được biến đổi và biểu diễn ở một dạng
gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật… Đồng thời bước
này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất
định.
1.1.3. Khai phá dữ liệu và các lĩnh vực liên quan
KPDL là một lĩnh vực liên quan tới thống kê, học máy, CSDL, thuật
toán, tính toán song song, thu nhận tri thức từ hệ chuyên gia và dữ liệu trừu
tượng. Đặc trưng của hệ thống khám phá tri thức là nhờ vào các phương pháp,
thuật toán từ những lĩnh vực khác nhau để KPDL.
Lĩnh vực học máy và nhận dạng mẫu trong KDD nghiên cứu các lý
thuyết và thuật toán của hệ thống để trích ra các mẫu và mô hình từ dữ liệu
lớn. KDD tập trung vào việc mở rộng các lý thuyết và thuật toán cho các vấn
đề tìm ra các mẫu đặc biệt (hữu ích hoặc có thể rút ra tri thức quan trọng)
trong CSDL lớn.
Ngoài ra, KDD có nhiều điểm chung với thống kê, đặc biệt là phân tích
dữ liệu thăm dò (Exploratory Data Analysis - EDA). Hệ thống KDD thường
gắn những thủ tục thống kê cho mô hình dữ liệu và tiến trình nhiễu trong

hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin – sinh, tài
chính và thị trường chứng khoán.,..


7

Phân tích chuỗi theo thời gian: Tương tự như khai phá luật kết hợp
nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng
dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính
dự báo cao.
Phân cụm: Xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân
cụm còn được gọi là học không có giám sát.
Mô tả tóm tắt khái niệm: Thiên về mô tả tổng hợp và tóm tắt khái niệm,
ví dụ như tóm tắt văn bản..
Do KPDL được ứng dụng rộng rãi nên có thể làm việc với rất nhiều
kiểu dữ liệu khác nhau. Sau đây là một dạng dữ liệu điển hình: Dữ liệu quan
hệ, dữ liệu đa chiều, dữ liệu dạng giao dịch, dữ liệu quan hệ - hướng đối
tượng, dữ liệu không gian và thời gian, dữ liệu chuỗi thời gian, dữ liệu đa
phương tiện, dữ liệu văn bản và Web,...
1.1.5. Những chức năng chính của KPDL
Hai mục tiêu chính của KPDL là mô tả và dự báo. Dự báo là dùng một
số biến hoặc trường trong CSDL để dự đoán ra các giá trị chưa biết hoặc sẽ có
các biến quan trọng khác. Việc mô tả tập trung vào tìm kiếm các mẫu mà con
người có thể hiểu được để mô tả dữ liệu. Trong lĩnh vực KDD, mô tả được
quan tâm nhiều hơn dự báo, nó ngược với các ứng dụng học máy và nhận
dạng mẫu mà trong đó việc dự báo thường là mục tiêu chính. Trên cơ sở mục
tiêu chính của KPDL, các nhiệm vụ chính của KDD gồm:
Mô tả lớp và khái niệm: Dữ liệu có thể được kết hợp trong lớp và khái
niệm. Thí dụ, trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng
bao gồm máy tính, máy in… và khái niệm khách hàng bao gồm khách hàng

tích các đối tượng dữ liệu khi chưa biết nhãn của lớp. Nhìn chung, nhãn của
lớp không tồn tại trong suốt quá trình huấn luyện dữ liệu, phân cụm có thể
được sử dụng để đưa ra nhãn của lớp. Sự phân cụm được thực hiện để nhóm
các đối tượng dữ liệu theo nguyên tắc: Các đối tượng trong cùng một nhóm


9

thì giống nhau hơn các đối tượng trong các nhóm khác nhau. Mỗi cụm được
tạo thành có thể được xem như một lớp các đối tượng mà các luật được lấy ra
từ đó. Dạng của cụm được hình thành theo một cấu trúc phân cấp của các lớp
mà mỗi lớp là một nhóm các sự kiện tương tự nhau.
Phân tích các đối tượng ngoài cuộc: Một CSDL có thể chứa các đối
tượng không tuân theo mô hình dữ liệu. Các đối tượng như vậy gọi là đối
tượng ngoài cuộc. Hầu hết các phương pháp KPDL đều coi các đối tượng
ngoài cuộc là nhiễu và loại bỏ chúng. Sự phân tích dữ liệu ngoài cuộc được
coi như là sự khai phá các đối tượng ngoài cuộc. Một số phương pháp được
sử dụng để phát hiện đối tượng ngoài cuộc: Sử dụng các test mang tính thống
kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất cho dữ liệu,
dùng các độ đo khoảng cách mà theo đó các đối tượng có một khoảng cách
đáng kể đến cụm bất kỳ khác được coi là đối tượng ngoài cuộc, dùng các
phương pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc
trưng chính của các nhóm đối tượng.
Phân tích sự tiến hóa: Phân tích sự tiến hóa thực hiện việc mô tả và mô
hình hóa các quy luật hay khuynh hướng của những đối tượng mà hành vi của
chúng thay đổi theo thời gian, phân tích sự tiến hóa có thể bao gồm cả đặc
trưng hóa, phân biệt, tìm luật kết hợp, phân lớp hay PCDL liên quan đến thời
gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên độ tương tự.
1.1.6. Các ứng dụng của Khai phá dữ liệu
KPDL được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác

phân cụm ta không hề biết trước tính chất của các cụm và thường dựa vào mối
quan hệ của các đối tượng để tìm ra sự giống nhau giữa các đối tượng dựa vào
một độ đo nào đó đặc trưng cho mỗi cụm.
Việc phân cụm không thực hiện độc lập mà thường sử dụng kết hợp với
các phương pháp khác. Một cách phân cụm được đưa ra cũng phải có một
phương pháp áp dụng trên các lớp đó để đưa ra được ý nghĩa của cụm đó.


11

Ta có thể khái quát hóa khái niệm PCDL như sau [6][10]:
"PCDL là một phương pháp 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, quan tâm trong tập dữ liệu
lớn, từ đó cung cấp thông tin, tri thức hữu ích cho người sử dụng".
Hiện nay có rất nhiều vấn đề nghiên cứu về phân cụm trong các lĩnh
vực khác nhau như: KPDL, thống kê, học máy, công nghệ dữ liệu không
gian, sinh học... Do kích thước của các cơ sở dữ liệu tăng lên rất nhanh nên
phân cụm là vấn đề đã và đang thu hút nhiều sự quan tâm của các nhà khoa
học trên thế giới.
Trong lĩnh vực thống kê, phân cụm đã được nghiên cứu và phát triển
trong nhiều năm, các vấn đề tập trung chủ yếu vào phân tích các lớp dựa vào
khoảng cách. Các công cụ phân tích lớp dựa trên một số các phương pháp như kmeans, k-medoids đã được ứng dụng trong nhiều hệ thống phần mềm phân tích
thống kê như: S-Plus, SPSS, SAS...
Trong học máy, PCDL được xem là vấn đề học không có giám sát, vì
nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chưa biết
trước các thông tin về cụm hay các thông tin về tập ví dụ huấn luyện. Trong
nhiều trường hợp, khi phân lớp (Classification) được xem vấn đề học có giám
sát thì PCDL là một bước trong phân lớp dữ liệu, trong đó PCDL sẽ khởi tạo
các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu.
Trong lĩnh vực khai thác dữ liệu, các vấn đề nghiên cứu trong phân

- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo.
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm.
Theo các nghiên cứu thì đến nay chưa có một phương pháp phân cụm
tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu.
Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc các
cụm dữ liệu khác nhau, với mỗi cách thức biểu diễn khác nhau sẽ có một thuật
toán phân cụm phù hợp. PCDL đang là một vấn đề mở và khó vì người ta phải đi


13

giải quyết nhiều vấn đề cơ bản như đã đề cập ở trên một cách trọn vẹn và phù
hợp với nhiều dạng dữ liệu khác nhau. Đặc biệt đối với dự liệu hỗn hợp, đang
ngày càng phát triển không ngừng trong hệ quản trị dữ liệu, đây cũng thách thức
lớn của lĩnh vực KPDL trong những thập kỷ tiếp theo và đặc biệt là trong lĩnh
vực KPDL Web.
1.2.2. Ứng dụng của phân cụm dữ liệu
PCDL là một trong những công cụ chính của KPDL, các phương pháp
PCDL đã được áp dụng cho một số ứng dụng điển hình trong các lĩnh vực như
sau [6][10]:
Thương mại: PCDL có thể giúp các thương nhân khám phá ra các
nhóm khách hàng quan trọng có đặc trưng tương đồng nhau và đặc tả họ từ
các mẫu mua bán trong CSDL khách hàng.
Sinh học: PCDL được sử dụng để xác định các loại sinh vật, phân loại các
gen với chức năng tương đồng và thu được cấu trúc trong các mẫu.
Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như dữ
liệu thu được từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống
thông tin địa lý (GIS),… làm cho người dùng rất khó để kiểm ta dữ liệu không
gian một cách chi tiết. PCDL có thể trợ giúp người dùng tự động phân tích và xử
lý các dữ liệu không gian như nhận dạng và chiết xuất các đặc tính hoặc các mẫu

phân cụm dữ liệu phải có khả năng khám phá ra những cụm dữ liệu có các hình
thù khác nhau.
Tối thiểu lượng tri thức cần cho tham số đầu vào: Do các giá trị đầu vào
của các thuật toán có ảnh hưởng rất lớn đến độ phức tạp, tốc độ của thuật toán.
Do đó cần xác định các giá trị đầu vào của các thuật toán một cách tối ưu đặc
biệt là đối với những CSDL lớn.
Ít nhạy cảm đối với thứ tự của dữ liệu vào: Cùng một tập dữ liệu khi đưa
vào xử lý bằng các thuật toán PCDL, 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 không ảnh hưởng đến kết quả phân cụm dữ liệu.


15

Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm
trong KPDL đều có chứa các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác được
gọi chung là dữ liệu nhiễu. Bởi vậy các thuật toán phân cụm dữ liệu không
những có hiệu quả với các dữ liệu nhiễu mà còn tránh dẫn đến chất lượng phân
cụm thấp do nhạy cảm với dữ liệu nhiễu.
Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng có hiệu
quả đối với các dữ liệu đa chiều.
Dễ hiểu, dễ cài đặt và khả thi: Đây là yêu cầu đồng thời là tiêu chí để đánh
giá hiệu quả của các thuật toán PCDL.
1.3. Khai phá Web
1.3.1. Khai phá Web
Với sự phát triển nhanh chóng của mạng Interner đã sinh ra một khối
lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Vì vậy khai phá
dữ liệu Web đang từng bước trở nên quan trọng trong lĩnh vực KPDL, với
tham vọng lấy được những tri thức mới từ việc tìm kiếm, phân tích, tổng hợp.
Những tri thức đó có thể giúp ta xây dựng nên những Web site hiệu quả để
phục vụ con người được tốt hơn.

dịch vụ và cấu trúc Web. Hay nói cách khác khai phá Web là việc trích chọn
ra các thành phần được quan tâm hay được đánh giá là có ích cùng các thông
tin tiềm năng từ các tài nguyên hoặc các hoặt động liên quan tới World Wide
Web, nó có thể giúp con người rút ra những tri thức mới, cải tiến việc thiết kế
các Web site và phát triển thương mại điện tử tốt hơn. Quá trình khai phá
Web có thể chia thành các giai đoạn như sau:
1. Tìm kiếm nguồn tài nguyên: Thực hiện việc tìm kiếm và lấy các tài
liệu Web phục vụ cho việc KPDL.
2. Lựa chọn và tiền xử lý dữ liệu: Lựa chọn và tiền xử lý tự động các
loại thông tin từ nguồn tài nguyên Web đã lấy về.


17

3. Tổng hợp: Tự động khám phá các mẫu chung từ các Web site riêng
lẻ cũng như nhiều Web site liên kết với nhau.
4. Phân tích: Đánh giá, giải thích, biểu diễn các mẫu khai phá được.
1.3.3. Đặc trưng của khai phá Web
Từ những năm 2000 trở lại đây tốc độ phát triển nhanh chóng của mạng
Internet đã sinh ra một khối lượng khổng lồ các dữ liệu Web (dữ liệu dạng
siêu văn bản). Một số đặc trưng sau đây cho thấy những thách thức và thuận
lợi của quá trình khai phá Web.
* Web quá lớn để tổ chức thành kho dữ liệu:
Các CSDL truyền thống có kích thước không lớn lắm, thường được lưu
trữ tập trung, trong khi đó kích thước của Web là rất lớn, tới hàng terabytes và
thay đổi liên tục, không những thế dữ liệu Web còn được phân tán ở rất nhiều
máy tính khắp nơi trên thế giới. Theo tài liệu thống kê năm 2009 cho thấy có
gần 236 triệu Website trên Internet [4].
* Độ phức tạp của các trang Web là rất lớn
Dữ liệu trong CSDL truyền thống thường đồng nhất về ngôn ngữ còn dữ

các tài liệu đăng nhập này có thể khám phá ra các thông tin truy cập.
Web pages: Hầu hết các phương pháp KPDL Web được sử dụng trong
Web pages là theo chuẩn HTML.
Web hyperlink structures: Các trang Web được liên kết với nhau bằng
các siêu liên kết, điều này rất quan trọng để khai phá thông tin. Do các siêu
liên kết Web là nguồn tài nguyên xác thực.
Dữ liệu thị trường trực tuyến: Như lưu trữ thông tin thương mại điện tử
trong các site thương mại điện tử.
Các thông tin khác: Chủ yếu bao gồm các đăng ký người dùng, nó có
thể giúp cho việc khai phá tốt hơn.
Tổng kết chương 1
Trong chương này trình bày những kiến thức cơ bản về khai phá dữ liệu,


19

khám phá tri thức, phân cụm trong khai phá dữ liệu và các khái niệm liên quan
đến phân cụm dữ liệu, ứng dụng của phân cụm dữ liệu và các yêu cầu đối với
phương pháp phân cụm dữ liệu.
Ngoài ra trong chương này còn đề cập đến một lĩnh vực cụ thể của KPDL
đó là khai phá Web. Trong phạm vi chương 1 chỉ đề cập đến khái niệm, các đặc
trưng và một số kiểu dữ liệu Web.


20

CHƯƠNG II. MỘT SỐ PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU
Các phương pháp áp dụng để giải quyết vấn đề PCDL đều hướng tới hai
mục tiêu chung: Chất lượng của các cụm khám phá được và tốc độ thực hiện
của thuật toán. Hiện nay, các kỹ phân cụm dữ liệu có thể phân loại theo các

toán phân
cụm dữ
liệu mờ

Thuật toán
K-means

Thuật toán
BIRCH

Thuật toán
DBSCAN

Thuật toán
STING

Thuật toán
EM

Thuật toán
FCM

Thuật toán
K-medoid

Thuật toán
CURE

Thuật toán
OPTICS