BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

TRẦN THỊ GEN NI

Nghiªn cøu ph©n côm
d÷ liÖu web vµ øng dông

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Huế, 2015


MỤC LỤC
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục các bảng
Danh mục các hình
MỞ ĐẦU .......................................................................................................... 1
Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU.................................. 4
1.1. Giới thiệu về Khai phá dữ liệu ................................................................... 4
1.1.1. Các chức năng chính của khai phá dữ liệu .............................................. 5
1.1.2. Các phương pháp khai phá dữ liệu.......................................................... 6
1.1.3. Ứng dụng của khai phá dữ liệu ............................................................... 7
1.2. Khai phá dữ liệu web ................................................................................. 7
1.2.1. Dữ liệu Web và nhu cầu khai thác thông tin ........................................... 7

2.7.1. Phân cụm theo thứ bậc .......................................................................... 46
2.7.2. Phân cụm bằng cách phân mảnh ........................................................... 49
2.8. Kết luận chương 2 .................................................................................... 51


Chương 3. ỨNG DỤNG VỀ PHÂN CỤM DỮ LIỆU WEB ...................... 52
3.1. Môi trường thực nghiệm: ......................................................................... 52
3.2. Công cụ thực nghiệm: .............................................................................. 52
3.3. Chuẩn bị dữ liệu ....................................................................................... 53
3.4. Quá trình thực nghiệm.............................................................................. 53
3.5. Thiết kế cơ sở dữ liệu ............................................................................... 54
3.6. Chương trình thử nghiệm ......................................................................... 56
3.7. Kết luận chương 3 .................................................................................... 58
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...................................................... 59
TÀI LIỆU THAM KHẢO ............................................................................... 61
PHỤ LỤC


DANH MỤC CÁC BẢNG
Số hiệu bảng

Tên bảng

Trang

1.1

Thống kê các tần số xuất hiện cao

14


hình vẽ

Trang

1.1

Các bước trong Data Mining & KDD

5

1.2

Phân loại dữ liệu Web

9

1.3

Lược đồ thống kê tần số của từ theo Định luật Zipf

16

2.1

Mô phỏng sự PCDL

23

2.2


Single Link

34

2.8

Complete Link

34

2.9

Các bước cơ bản của AGNES

35

2.10

Ví dụ các bước cơ bản của thuật toán AGNES

36

2.11

Các bước cơ bản của DIANA

37

3.1

tăng lên.
Cùng với sự tiến bộ vượt bậc của công nghệ thông tin là sự phát triển
mạnh mẽ của mạng thông tin toàn cầu, nguồn dữ liệu web trở thành kho dữ liệu
khổng lồ. Do đó, việc nghiên cứu các mô hình dữ liệu mới và áp dụng các
phương pháp để tìm kiếm nhanh chóng tài nguyên web là một xu thế tất yếu.
Với số lượng thông tin đồ sộ như vậy, một yêu cầu lớn đặt ra với chúng
ta là làm sao tổ chức và tìm kiếm thông tin một cách hiệu quả nhất. Phân loại
thông tin là một giải pháp hợp lý cho yêu cầu trên. Nhưng một thực tế là khối
lượng thông tin quá lớn, việc phân loại thủ công là điều không tưởng. Hướng
giải quyết là một chương trình máy tính tự động phân loại các thông tin trên.
Do đó, việc nghiên cứu các mô hình dữ liệu mới và áp dụng các phương
pháp khai phá dữ liệu trong khai phá tài nguyên Web là một xu thế tất yếu vừa
có ý nghĩa khoa học vừa mang ý nghĩa thực tiễn cao.
Ngày nay, nhờ sự cải tiến không ngừng của các công cụ tìm kiếm về cả
chức năng tìm kiếm lẫn giao diện đã giúp cho người sử dụng dễ dàng hơn trong
việc tìm kiếm thông tin trên web. Tuy nhiên, người sử dụng thường vẫn phải
duyệt qua hàng trăm, thậm chí hàng ngàn trang Web mới có thể tìm kiếm được


2

thứ mà họ cần. Nhằm giải quyết vấn đề này, ta có thể nhóm các kết quả tìm
kiếm thành các nhóm theo từng chủ đề, khi đó người dùng có thể bỏ qua các
nhóm mà họ không quan tâm để tìm đến nhóm chủ đề quan tâm. Điều này sẽ
giúp cho người dùng thực hiện công việc tìm kiếm một cách hiệu quả hơn.
Đặc biệt trong vấn đề giải quyết văn bản. Văn bản có rất nhiều loại, khi
muốn tìm kiếm bất kỳ văn bản nào trên web nếu làm bằng thủ công cũng rất khó
khăn và mất nhiều thời gian. Với số lượng văn bản đồ sộ như thế cần có một giải
pháp để tìm kiếm văn bản được nhanh hơn. Vì thế việc ứng dụng phân cụm dữ
liệu để tìm kiếm văn bản theo chủ đề là một vấn đề rất cần thiết.

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Giới thiệu về Khai phá dữ liệu
Khái niệm Khai phá dữ liệu (Data Mining)
Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay khám
phá tri thức từ một lượng lớn dữ liệu. Thuật ngữ Data Mining ám chỉ việc tìm
một tập nhỏ có giá trị từ một lượng lớn các dữ liệu thô. Hai khái niệm KPDL và
KDD được các nhà khoa học trên hai lĩnh vực xem là tương đương với nhau.
Tuy nhiên, nếu phân chia một cách chi tiết vẫn có sự phân biệt giữa khái niệm
"Khai phá dữ liệu" với khái niệm "Phát hiện tri thức" (Knowledge Discovery in
Databases - KDD) mà theo đó, khai phá dữ liệu chỉ là một bước chính trong quá
trình KDD.
Định nghĩa 1.1: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử
dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong
một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm
ẩn trong tập dữ liệu đó. [1]
Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD
(Knowleadge Discovery in Database) và KDD được xem như 7 quá trình khác
nhau theo thứ tự sau:
1. Làm sạch dữ liệu (data cleaning & preprocessings): Loại bỏ nhiễu và
các dữ liệu không cần thiết.
2. Tích hợp dữ liệu (data integration): quá trình hợp nhất dữ liệu thành
những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền
xử lý (data cleaning & preprocessing).
3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ
liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá


trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không
đầy đủ (incomplete data), .v.v.
4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù

được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng
một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các
cụm khác nhau là nhỏ nhất. Người ta còn gọi phân cụm là học không
giám sát (học không thầy).
 Khai phá chuỗi (sequential/temporal patterns): 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.
1.1.2. Các phương pháp khai phá dữ liệu
Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường
sử dụng các phương pháp sau cho khai phá dữ liệu:
 Luật kết hợp (association rules)
 Phân lớp (Classfication)
 Hồi qui (Regression)


 Trực quan hóa (Visualiztion)
 Phân cụm (Clustering)
 Tổng hợp (Summarization)
 Mô hình ràng buộc (Dependency modeling)
 Biểu diễn mô hình (Model Evaluation)
 Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
 Phương pháp tìm kiếm (Search Method)
Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó
có ba phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết
hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.
1.1.3. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu thu hút được rất nhiều sự quan tâm của các nhà nghiên
cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể liệt
kê ra đây một số ứng dụng điển hình:

của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung
giống với yêu cầu của người tìm kiếm. Các tiện ích này quản lý dữ liệu trang
Web như các đối tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một số
các tiện ích như vậy, đó là Yahoo, Google, Alvista,...
Nhờ sự cải tiến không ngừng của các công cụ tìm kiếm về cả chức năng
tìm kiếm lẫn giao diện đã giúp cho người sử dụng dễ dàng hơn trong việc tìm
kiếm thông tin trên web. Tuy nhiên vấn đề phân cụm tài liệu Web và chọn chủ
đề thích hợp để nó có thể mô tả được nội dung của các trang là một vấn đề
không đơn giản.
Đặc biệt trong vấn đề giải quyết văn bản. Văn bản có rất nhiều loại, khi
muốn tìm kiếm bất kỳ văn bản nào trên web nếu làm bằng thủ công cũng rất khó
khăn và mất nhiều thời gian. Với số lượng văn bản đồ sộ như thế cần có một giải
pháp để tìm kiếm văn bản được nhanh hơn. Vì thế việc ứng dụng phân cụm dữ
liệu để tìm kiếm văn bản theo chủ đề là một vấn đề rất cần thiết.


Mặt khác, căn cứ vào nội dung của các tài liệu mà người dùng xem và tải
về, sau khi phân lớp các yêu cầu như thế của người dùng, chúng ta sẽ biết được
họ hay tập trung vào nội dung gì trên trang Web của chúng ta, mà từ đó chúng ta
sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà họ quan tâm. Ngược lai, về
phía người dùng, sau khi được phục vụ phù hợp yêu cầu, họ sẽ hướng sự quan
tâm tới hệ thống của chúng ta hơn. Từ những nhu cầu thực tế trên, phân lớp và
tìm kiếm trang Web vẫn là bài toán thời sự và cần được phát triển nghiên cứu.
Như vậy, chúng ta có thể hiểu rằng khai phá Web như 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.
1.2.2. Đặc điểm của dữ liệu Web
* Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ
Khai phá dữ liệu.
* Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn


Các đối tượng của khai phá Web bao gồm: Server logs, Web pages, Web
hyperlink structures, dữ liệu thị trường trực tuyến và các thông tin khác.
Web logs: Khi người dùng duyệt Web, dịch vụ sẽ phân ra 3 loại dữ liệu
đăng nhập: sever logs, error logs và cookie logs. Thông qua việc phân tích các
tài liệu đăng nhập này ta có thể khám phá ra những 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 structure: 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 rất 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 website 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.
1.3. Các hướng tiếp cận khai phá dữ liệu web
Như đã phân tích về đặc điểm và nội dung các siêu văn bản ở trên, từ đó
khai phá dữ liệu Web cũng sẽ tập trung vào các thành phần có trong trang Web.
Đó chính là:
1. Khai phá nội dung trang Web (Web Content mining)
Khai phá nội dung trang Web gồm hai phần:
a. Nội dung trang web (Web Page Content)
Nghĩa là sẽ sử dụng chỉ các từ trong văn bản mà không tính đến các liên
kết giữa các văn bản. Đây chính là khai phá dữ liệu văn bản(Textmining).
b. Tìm kiếm kết quả (Search Result)
Tìm kiếm theo kết quả. Trong các máy tìm kiếm, sau khi đã tìm ra những
trang Web thoả mãn yêu cầu người dùng, còn một công việc không kém phần
quan trọng, đó là phải sắp xếp kết quả theo thứ tự độ gần nhau với nội dung cần
tìm kiếm. Đây cũng chính là khai phá nội dung trang Web.



liệu nhận được. Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân
cụm ngay khi chưa có đủ tài liệu và phân cụm tiếp theo không cần phải tiến
hành với dữ liệu đã được phân cụm trước đó. Do tập tài liệu trên Web là vô cùng
lớn cho nên cách phân cụm trực tuyến là thích hợp hơn và phải đòi hỏi tính "gia
tăng" của thuật toán phân cụm.
Quá trình xử lý truy vấn và kết quả phân hạng được phản hồi từ các máy
tìm kiếm phụ thuộc vào việc tính toán độ tương tự giữa truy vấn và các tài liệu.
Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhưng nó
thường quá ngắn và dễ xảy ra sự nhập nhằng. Như đã biết, trung bình các truy
vấn trên Web chỉ gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn,
truy vấn star dẫn đến sự nhập nhằng rất cao, các tài liệu lấy được liên quan đến
astronomy, plants, animals, popular media ndsports figures… Độ tương tự giữa
các tài liệu của một truy từ đơn như vậy là có sự khác nhau rất lớn. Vì lẽ đó, nếu
máy tìm kiếm phân cụm các kết quả theo từng chủ đề thì người dùng có thể
nhanh chóng hiểu kết quả truy vấn hoặc tìm vào một chủ đề xác định.
1.5. Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web
1.5.1. Dữ liệu văn bản
Trong các loại dữ liệu hiện nay thì văn bản là loại dữ liệu phổ biến nhất và
nó có mặt khắp mọi nơi, đặc biệt là đối với dữ liệu trên Web. Do vậy, các bài
toán xử lý văn bản đã được đặt ra từ rất sớm và hiện nay nó vẫn là vấn đề rất
được nhiều nhà nghiên cứu quan tâm, một trong những bài toán đó là tìm kiếm
và trích dẫn văn bản, biểu diễn và phân loại văn bản,…
CSDL văn bản có thể chia làm 2 loại chính:
+ Dạng không có cấu trúc: Đây là những tài liệu văn bản thông thường mà
ta đọc thường ngày trên các sách, báo, internet,… đây là dạng dữ liệu của ngôn
ngữ tự nhiên của con người và nó không theo một khuôn mẫu định sẵn nào cả.


+ Dạng nửa cấu trúc: Đây là những văn bản được tổ chức dưới dạng cấu

105 đối với các tập văn bản nhỏ. Vấn đề đặt ra là làm sao để giảm số chiều của
vector mà vẫn đảm bảo việc xử lý văn bản đúng và chính xác, đặc biệt là trong
môi trường www, ta sẽ xem xét đến một số phương pháp để giảm số chiều của
vector.
1.5.2.1. Loại bỏ từ dừng
Trước hết ta thấy trong ngôn ngữ tự nhiên có nhiều từ chỉ dùng để biểu
diễn cấu trúc câu chứ không biểu đạt nội dung của nó. Như các giới từ, từ nối, ...
những từ như vậy xuất hiện nhiều trong các văn bản mà không liên quan gì tới
chủ đề hoặc nội dung của văn bản. Do đó, ta có thể loại bỏ những từ đó để giảm
số chiều của vector biểu diễn văn bản, những từ như vậy được gọi là những từ
dừng.
Sau đây là ví dụ về tần số xuất hiện cao của một số từ (tiếng Anh) trong
336.310 tài liệu gồm tổng cộng 125.720.891 từ, 508.209 từ riêng biệt.
Bảng 1.1. Thống kê các tần số xuất hiện cao
Frequent Word

Number of Occurrences

Percentage of Total

The
of
to
and
in
is
for
The
that
Said

từ xuất hiện một hoặc hai lần (tần số xuất hiện nhỏ) thì ảnh hưởng rất bé đến các
văn bản.
Tiền đề cho việc lý luận để loại bỏ những từ có tần suất nhỏ được đưa ra
bởi Zipf năm 1949. Zipf phát biểu dưới dạng một quan sát nhưng ngay trong
thời điểm đó, quan sát đó đã được gọi là định luật Zipf, mặc dù nó thực sự
không phải là một định luật mà đúng hơn đó là một hiện tượng xấp xỉ toán học.
Để mô tả định luật Zipf, ta gọi tổng số tần số xuất hiện của từ t trong tài
liệu D là ft. Sau đó sắp xếp tất cả các từ trong tập hợp theo chiều giảm dần của
tần số xuất hiện f và gọi thứ hạng của mỗi từ t là rt.
Định luật Zipf được phát biểu dưới dạng công thức như sau:
rt.ft  K (với K là một hằng số)
Trong tiếng Anh, người ta thấy rằng hằng số K  N/10 trong đó N là số
các từ trong văn bản. Ta có thể viết lại định luật Zipf như sau: rt  K/ ft
Giả sử từ ti được sắp xếp ở vị trí thấp nhất với tần số xuất hiện là b nào
đấy và từ tj cũng được sắp ở vị trí thấp kế tiếp với một tần số xuất hiện là
b+1. Ta có thể thu được thứ hạng xấp xỉ của các từ này là rti  K/b và
rtj  K/(b+1), trừ 2 biểu thức này cho nhau ta xấp xỉ đối với các từ riêng biệt
có tần số xuất hiện là b.
rti- rtj  K/b-K/(b+1)
Ta xấp xỉ giá trị của từ trong tập hợp có thứ hạng cao nhất. Một cách tổng
quát, một từ chỉ xuất hiện một lần trong tập hợp, ta có rmax=K.


Xét phân bố của các từ duy nhất xuất hiện b lần trong tập hợp, chia 2 vế
cho nhau ta được K/b. Do đó, định luật Zipf cho ta thấy sự phân bố đáng chú ý
của các từ riêng biệt trong 1 tập hợp được hình thành bởi các từ xuất hiện ít nhất
trong tập hợp.
Năm 1958 Luhn đề xuất những từ “phổ biến” và “hiếm” và không cần
thiết cho quá trình xử lý như sau.


các công thức sau:
- Wij=tfij
- Wij= 1+log(tfij)
- Wij=

tf ij

Với mô hình này, trọng số Wij đồng biến với số lần xuất hiện của thuật
ngữ ti trong tài liệu dj. Khi số lần xuất hiện thuật ngữ ti trong tài liệu dj càng lớn
thì có nghĩa là dj càng phụ thuộc nhiều vào thuật ngữ ti, nói cách khác thuật ngữ
ti mang nhiều thông tin hơn trong tài liệu dj.


1.5.3.2.2. Phương pháp dựa trên tần số văn bản nghịch đảo
Trong mô hình dựa trên tần số văn bản nghịch đảo (IDF-Inverse
Document Frequency) giá trị trọng số của từ được tính bằng công thức sau:

Trong đó, n là tổng số văn bản trong CSDL, hi là số văn bản chứa thuật
ngữ ti.
Trọng số wij trong công thức trên được tính dựa vào độ quan trọng của
thuật ngữ ti trong tài liệu dj. Nếu ti xuất hiện càng ít trong các văn bản thì nó
càng quan trọng, do đó nếu ti xuất hiện trong dj thì trọng số của nó càng lớn,
nghĩa là nó càng quan trọng để phân biệt dj với các tài liệu khác và lượng thông
tin của nó càng lớn.
1.5.3.2.3. Mô hình kết hợp TF-IDF
Trong mô hình TF-IDF, mỗi tài liệu dj được xét đến thể hiện bằng một
đặc trưng của (t1, t2,.., tn) với ti là một từ/cụm từ trong dj. Thứ tự của ti dựa trên
trọng số của mỗi từ. Các tham số có thể được thêm vào để tối ưu hóa quá trình
thực hiện nhóm. Như vậy, thành phần trọng số được xác định bởi công thức sau,
nó kết hợp giá trị trọng số tf và giá trị trọng số idf.


i 1

m

x
i 1

2

i

m

2

i 1

i

y

m

Jaccard: Sim( X , Y ) 

(x . y )
m

x

i 1

2

2

m

i

i 1

  y   ( xi . y )

m

Cosine: sim ( X , Y ) 

i

i