ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Thị Thu Hằng

PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB
VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM

LUẬN VĂN THẠC SỸ

Hà Nội – 2007

TIEU LUAN MOI download :


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Thị Thu Hằng

PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB
VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM

Ngành: Cơng nghệ thơng tin.
Mã số: 1.01.10

LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS HÀ QUANG THỤY

Hà Nội - 2007

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

MỤC LỤC

DANH MỤC CHỮ VIẾT TẮT .................................................................... 6
DANH MỤC HÌNH VẼ, BẢNG BIỂU ........................................................ 7
U

MỞ ĐẦU....................................................................................................... 8
U

CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB ................. 11
1.1.

Khai phá dữ liệu Web.................................................................... 11

1.1.1.

Giới thiệu về Khai phá dữ liệu ............................................... 11

1.1.2.

Dữ liệu Web và nhu cầu khai thác thông tin .......................... 14

1.1.3.


Đặc điểm của dữ liệu Web ..................................................... 15

1.1.4.

Các hướng tiếp cận khai phá dữ liệu Web ............................. 16

1.1.5.

Nhu cầu phân cụm tài liệu Web ............................................. 17

1.2.

Mơ hình tìm kiếm thơng tin........................................................... 18

1.2.1.

Giới thiệu ................................................................................ 18

1.2.2.

Quy trình tìm kiếm thông tin trong hệ thống ......................... 19

1.2.3.

Ứng dụng phân cụm vào hệ thống tìm kiếm .......................... 23

1.3.

Kết luận chương 1 ......................................................................... 23


CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB ................................... 24
2.1.

Khái quát về các thuật toán phân cụm tài liệu .............................. 24

2.2.

Tiêu chuẩn đánh giá thuật toán phân cụm..................................... 27

2.3.

Các đặc tính của các thuật tốn phân cụm web............................. 29

2.3.1.

Mơ hình dữ liệu ...................................................................... 29

-3-

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

2.3.2.

Độ đo về sự tương tự .............................................................. 33

2.3.3.


Mơ hình phân cụm.................................................................. 35

2.4.

Một số kỹ thuật Phân cụm Web điển hình .................................... 36

2.4.1.

Phân cụm theo thứ bậc ........................................................... 36

2.4.2.

Phân cụm bằng cách phân mảnh ............................................ 40

2.5.

Các yêu cầu đối với các thuật tốn phân cụm Web ...................... 43

2.5.1.

Tách các thơng tin đặc trưng .................................................. 43

2.5.2.

Phân cụm chồng lặp................................................................ 44

2.5.3.

Hiệu suất ................................................................................. 44


2.5.4.

Khả năng khử nhiễu................................................................ 45

2.5.5.

Tính tăng................................................................................. 45

2.5.6.

Việc biểu diễn kết quả ............................................................ 45

2.6.

Bài toán tách từ tự động tiếng Việt ............................................... 46

2.6.1.

Một số khó khăn trong phân cụm trang Web tiếng Việt ........ 46

2.6.2.

Tiếng và Từ trong tiếng Việt .................................................. 48

2.6.3.

Phương pháp tách từ tự động tiếng Việt fnTBL..................... 48

2.6.4.


Phương pháp Longest Matching............................................. 53

2.6.5.

Kết hợp giữa fnTBL và Longest Matching ............................ 54

2.7.

Kết luận chương 2 ......................................................................... 54

CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT
TOÁN CÂY PHÂN CỤM TÀI LIỆU ........................................................ 55
U

3.1.

Giới thiệu về thuật toán phân cụm trang Web có tính tăng .......... 55

-4-

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

3.2.

Thuật tốn phân cụm cây hậu tố.................................................... 56


3.2.1.

Mơ tả....................................................................................... 56

3.2.2.

Thuật toán STC....................................................................... 57

3.3.

Thuật toán phân cụm sử dụng cây phân cụm tài liệu .................... 62

3.3.1.

Giới thiệu ................................................................................ 62

3.3.2.

Trích chọn đặc trưng và phân cụm tài liệu............................. 64

3.3.3.

Cây phân cụm tài liệu –DC Tree ............................................ 68

3.4.

Kết luận chương 3 ......................................................................... 73

CHƯƠNG 4 - PHẦN MỀM THỬ NGHIỆM VÀ KẾT QUẢ THỰC
NGHIỆM


75

4.1.

Giới thiệu....................................................................................... 75

4.2.

Thiết kế cơ sở dữ liệu .................................................................... 76

4.3.

Chương trình thử nghiệm .............................................................. 80

4.4.

Kết luận chương 4 ......................................................................... 84

TÀI LIỆU THAM KHÁO........................................................................... 86

-5-

TIEU LUAN MOI download :


Thank you for evaluating AnyBizSoft PDF Splitter.
A watermark is added at the end of each output PDF file.

To remove the watermark, you need to purchase the software from


/>
TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

DANH MỤC CHỮ VIẾT TẮT
AHC: Phân cụm tích tụ theo thứ bậc (Agglomerative Hierarchical
Clustering)
CSDL: Cơ sở dữ liệu
DF: Tần suất xuất hiện tài liệu (Document Frequency)
DC-tree: Cây phân cụm tài liệu (Document Clustering Tree)
fnTBL: Học dựa trên sự biến đổi (Fast Transformation-based
learning)
FCM: Fuzzy C-means
FCMdd: Fuzzy C-Medoids
IR: Mơ hình tìm kiếm thông tin (Information Retrieval)
IDF: Tần suất nghịch đảo tài liệu (inverse document frequency)
KDD: Khai phá tri thức (Knowledge Discovery in Databases)
STC: Phân cụm cây hậu tố (Suffix tree clustering)
TF: Tần suất xuất hiện (term frequency)

-6-

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.


DANH MỤC HÌNH VẼ, BẢNG BIỂU

Hình 1. Các bước trong KDD ..................................................................... 12
Hình 2. Mơ hình hệ thống tìm kiếm thơng tin ............................................ 20
Hình 3. Một ví dụ dendogram của phân cụm sử dụng phân cụm có thứ bậc
..................................................................................................................... 37
Hình 4. Quá trình học.................................................................................. 52
Hình 5. Giai đoạn xác định từ cho tài liệu mới........................................... 53
Hình 6. Cây hậu tố cho xâu BANANA...................................................... 57
Hình 7. Cây hậu tố của các chuỗi “cat ate cheese”, “mouse ate cheese too”,
“cat ate mouse too”. .................................................................................... 59
Hình 8. Đồ thị các cụm cơ sở của ví dụ trong Hình 7 và bảng 1................ 62
Hình 9. Ví dụ của một cây DC.................................................................... 69
Hình 10. Sơ đồ liên kết thực thể của chương trình thực nghiệm ................ 80
Hình 11. Màn hình hỗ trợ chức năng cập nhật chỉnh sửa Từ điển.............. 81
Hình 12. Màn hình chức năng hỗ trợ lấy dữ liệu từ Internet ...................... 82
Hình 13. Màn hình hỗ trợ chức năng Phân cụm với dữ liệu đã lấy về từ
Internet ........................................................................................................ 83
Hình 14. Màn hình chức năng hỗ trợ Tìm kiếm. ........................................ 84

-7-

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

MỞ ĐẦU
World Wide Web là một kho thông tin khổng lồ với tiềm năng được
coi là khơng có giới hạn. Khai phá Web là vấn đề nghiên cứu thời sự trong

thời gian gần đây, đã thu hút nhiều nhóm nhà khoa học trên thế giới tiến
hành nghiên cứu, đề xuất các mơ hình, phương pháp mới nhằm tạo ra các
cơng cụ hiệu quả hỗ trợ người dùng trong việc tổng hợp thơng tin và tìm
kiếm tri thức từ tập hợp các trang Web khổng lồ trên Internet.
Phân cụm tài liệu Web là một bài tốn điển hình trong khai phá
Web, nhằm phân hoạch tập văn bản thành các tập con có tính chất chung,
trong đó bài tốn phân cụm các trang Web là kết quả trả về từ máy tìm
kiếm là rất hữu dụng [4-6, 8-15, 18, 19, 22, 24]. Như đã biết, tập hợp các
trang Web đáp ứng một câu hỏi trả về từ máy tìm kiếm nói chung là rất lớn,
vì vậy, thuật tốn phân cụm văn bản ở đây cần có được một tính chất rất
quan trọng là tính "tăng" theo nghĩa thuật tốn phân cụm khơng phải thực
hiện chỉ trên toàn bộ tập dữ liệu mà có thể được thực hiện theo cách từ bộ
phận dữ liệu tới toàn bộ dữ liệu [4, 6, 11, 14, 15, 24]. Điều đó cho phép
thuật tốn tiến hành ngay trong giai đoạn máy tìm kiếm đưa các trang web
kết quả về.
Luận văn tập trung khảo sát các phương pháp phân cụm trong Web
có tính chất tăng và thực hiện một số thử nghiệm tích hợp các kết quả nghiên
cứu nói trên vào một phần mềm tải trang Web theo dạng máy tìm kiếm. Đồng
thời, luận văn triển khai một số bước đầu tiên trong việc áp dụng phân cụm
cho các trang Web tiếng Việt. Luận văn xây dựng một phần mềm thử
nghiệm và tiến hành các thử nghiệm phân cụm Web tiếng Việt.
Ngoài Phần Mở đầu, Phần Kết luận và các Phụ lục, nội dung luận
văn được chia thành 4 chương chính:

-8-

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.


Chương 1 – Khái quát về khai phá dữ liệu Web. Chương này
giới thiệu những nội dung cơ bản nhất, cung cấp một cái nhìn khái quát về
Khai phá dữ liệu Web. Đồng thời, luận văn cũng mô tả sơ bộ một hệ thống
thơng tin tìm kiếm và nhu cầu phân cụm áp dụng cho hệ thống này.
Chương 2 – Thuật tốn phân cụm Web. Chương này trình bày
một cách khái quát về các thuật toán phân cụm Web, những đặc trưng và
yêu cầu đối với các thuật toán phân cụm Web. Những yêu cầu và độ đo áp
dụng cho các thuật tốn phân cụm Web cũng được trình bày trong chương
này. Một số kiến thức cơ bản về tiếng Việt cũng được giới thiệu ở đây.
Chương 3 – Thuật toán phân cụm cây hậu tố và thuật toán cây
phân cụm tài liệu. Chương này đi sâu vào phân tích các thuật tốn phân
cụm Web có tính chất tăng. Luận văn tập trung vào hai thuật tốn phân
cụm Web có tính “tăng” là thuật tốn STC và thuật tốn phân cụm có sử
dụng cấu trúc cây DC (DC-tree).
Chương 4 – Phần mềm thử nghiệm và kết quả thực nghiệm.
Chương này trình bày kết quả thực nghiệm phân cụm Web theo phần mềm
thử nghiệm trên cơ sở thuật toán phân cụm DC-tree. Chương trình cài đặt
thử nghiệm được viết trên ngơn ngữ lập trình C# trên nền tảng .Net
Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ
liệu. Phần mềm đã hoạt động, cho kết quả phân cụm, tuy nhiên, do thời
gian hạn chế nên luận văn chưa tiến hành đánh giá kết quả phân cụm một
cách chính thống.
Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn
và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn.
Luận văn đã đạt một số kết quả khả quan bước đầu trong việc
nghiên cứu và triển khai các thuật toán phân cụm Web có tính chất tăng,

-9-


TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

tuy nhiên, luận văn khơng tránh khỏi những sai sót. Rất mong được sự
đóng góp ý kiến, nhận xét để tác giả có thể hồn thiện được kết quả nghiên
cứu.

- 10 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB
1.1. Khai phá dữ liệu Web
1.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ơ. 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 trong quá trình KDD. Quá trình KDD gồm một số bước
sau:
• Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu khơng cần thiết
• Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại

• Lựa chọn dữ liệu: Các dữ liệu có liên quan đến q trình phân
tích được lựa chọn từ cơ sở dữ liệu
• Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các
dạng phù hợp cho q trình xử lý
• Khai phá dữ liệu: Là một trong những bước quan trọng nhất,
trong đó sử dụng những phương pháp thông minh để lựa chọn ra
những mẫu dữ liệu.
• Ước lượng mẫu: Q trình đánh giá kết quả thơng qua một độ
đo nào đó
• Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan

cho người dùng.

- 11 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

Hình 1. Các bước trong KDD

Các hướng tiếp cận và các kỹ thuật trong khai phá dữ liệu
Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau:
• Mơ tả khái niệm (concept description): thiên về mơ tả, tổng
hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.
• Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ
ở dạng khá đơn giản. Ví dụ: “50% những người mua máy tính thì
cũng mua máy in”. Luật kết hợp được ứng dụng nhiều trong lĩnh
vực kính doanh, y học, tin-sinh, tài chính & thị trường chứng

khốn, .v.v.
• Phân lớp và dự đốn (classification & prediction): 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 vùng
địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng
một số kỹ thuật của machine learning như cây quyết định (decision

- 12 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

tree), mạng nơ ron nhân tạo (neural network), .v.v. Người ta cịn
gọi phân lớp là học có giám sát (học có thầy).
• Phân cụm (clustering): xếp các đối tượng theo từng cụm (số
lượng cũng như tên của cụm chưa được biết trước. 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 khốn vì nó có tính dự báo cao.
Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được
sự quan tâm của rất nhiều 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 [7,16]:
• Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis &
decision support)

• Điều trị y học (medical treatment)
• Text mining & Web mining
• Tin-sinh (bio-informatics)
• Tài chính và thị trường chứng khốn (finance & stock market)
• Bảo hiểm (insurance)
• Nhận dạng (pattern recognition)
• .v.v.

- 13 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin

Sự phát triển nhanh chóng của mạng Internet và Intranet đã 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).
Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng
như số lượng của các trang Web trên Internet thì vấn đề tìm kiếm thơng tin
đối với người sử dụng lại ngày càng khó khăn. Có thể nói nhu cầu tìm kiếm
thơng tin trên mơt cơ sở dữ liệu phi cấu trúc (bao gồm dữ liệu văn bản) đã
được phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy với
Internet, con người đã làm quen với các trang Web cùng với vô vàn các
thông tin. Trong những năm gần đây, Intrnet đã trở thành một trong những
kênh về khoa học, thông tin kinh tế, thương mại và quảng cáo. Một trong
những lý do cho sự phát triển này là giá cả thấp cần tiêu tốn khi công khai
một trang Web trên Internet. So sánh với những dịch vụ khác như mua bản
hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web "địi" chi phí

rẻ hơn rất nhiều mà lại được cập nhật nhanh chóng hơn tới hàng triệu người
dùng khắp mọi nơi trên thế giới. Có thể nói khơng gian Web như là cuốn từ
điển Bách khoa tồn thư. Thơng tin trên các trang Web đa dạng về mặt nội
dung cũng như hình thức. Có thể nói Internet như một xã hội ảo, nó bao
gồm các thơng tin về mọi mặt của đời sống kinh tế, xã hội được trình bày
dưới dạng văn bản, hình ảnh, âm thanh,...
Tuy nhiên cùng với sự đa dạng và số lượng lớn thông tin như vậy
đã nảy sinh vấn đề quá tải thông tin. Người ta khơng thể tìm tự kiếm địa chỉ
trang Web chứa thơng tin mà mình cần, do vậy địi hỏi cần phải có một
trình tiện ích quản lý nội dung 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

- 14 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

nay chúng ta đã làm quen với một số các tiện ích như vậy, đó là Yahoo,
Google, Alvista, ...
Mặt khác, giả sử chúng ta có các trang Web về các vấn đề Tin học,
Thể thao, Kinh tể-Xã hội và Xây dựng...Căn cứ vào nội dung của các tài
liệu mà khách hàng xem hoặc download về, sau khi phân lớp các yêu cầu
như thế của khách hàng, chúng ta sẽ biết được khách hàng 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à khách hàng quan tâm. Ngược
lai, về phía khách hàng, sau khi được phục vụ phù hợp yêu cầu, khách hàng
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 tố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 [25, 26].
Một cách trực quan có thể quan niệm khai phá Web là sự kết hợp
giữa Khai phá dữ liệu, Xử lý ngôn ngữ tự nhiên và Công nghệ Web:
Khai phá web = Khai phá dữ liệu + Xử lý ngôn ngữ tự nhiên +
World Wide Web.
1.1.3. Đặ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 bản truyền thống khác.

- 15 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

* Web là một nguồn tài ngun thơng tin có độ thay đổi cao
* Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng
* Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích
1.1.4. 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. 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 Text
(Textmining)
b. 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ự dộ 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.
2. Web Structure Mining
Khai phá dựa trên các siêu liên kết giữa các văn bản có liên quan.
3. Web Usage Mining
a. General Access Partern Tracking:

- 16 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

Phân tích các Web log để khám phá ra các mẫu truy cập của người
dùng trong trang Web.
b. Customize Usage Tracking:
Phân tích các mẫu truy cập của người dùng tại mỗi thời điểm để

biết xu hướng truy cập trang Web của từng đối tượng người dùng tại mỗi
thời điểm khác nhau
Luận văn này tập trung chủ yếu vào nội dung “khai phá phá nội
dung trang Web” và định hướng vào phân cụm tập trang web là kết quả tìm
kiếm của các máy tìm kiếm.
1.1.5. Nhu cầu phân cụm tài liệu Web

Một trong những bài toán quan trọng trong lĩnh vực khai phá Web
là bài toán phân cụm Web. Phân cụm Web - nói một cách khái quát - là
việc tự động sinh ra các "cụm" (lớp) tài liệu dựa vào sự tương tự của các tài
liệu. Các lớp tài liệu ở đây là chưa biết trước, người dùng có thể chỉ yêu
cầu số lượng các lớp cần phân loại, hệ thống sẽ đưa ra các tài liệu theo từng
tập hợp, từng cụm, mỗi tập hợp chứa các tài liệu tương tự nhau.
Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các
tài liệu được lấy từ Web. Có hai tình huống phân cụm tài liệu. Tình huống
thứ nhất là việc phân cụm trên tồn bộ một CSDL có sẵn gồm rất nhiều tài
liệu Web. Thuật tốn phân cụm cần tiến hành việc phân cụm tồn bộ tập dữ
liệu thuộc CSDL đó. Tình huống này thường được gọi là phân cụm khơng
trực tuyến (off-line). Tình huống thứ hai thường được áp dụng trên một tập
tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về theo một truy vấn
của người dùng. Trong trường hợp này, giải pháp phân cụm được tiến hành
kiểu phân cụm trực tuyến (on-line) theo nghĩa việc phân cụm tiến hành
theo từng bộ phận các tài liệu nhận được. Khi đó, thuật tốn phải có tính

- 17 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.


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 tốn phân
cụm.
Q 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 tố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
and sports 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.2. Mơ hình tìm kiếm thơng tin
1.2.1. Giới thiệu

Với sự phát triển nhanh chóng của cơng nghệ tin học, khối lượng
thơng tin lưu trữ trên máy tính ngày càng nhiều, vì vậy cần có các hệ thống
tìm kiếm thơng tin (IR: Information Retrieval) cho phép người dùng tìm
kiếm một cách chính xác và nhanh nhất các thơng tin mà họ cần trên kho
dữ liệu khổng lồ này, trong đó, Internet chính là một kho dữ liệu như thế.
Mục tiêu của hệ thống tìm kiếm là cung cấp cơng cụ để trả về cho người
dùng các tài liệu trong kho dữ liệu có liên quan tới câu truy vấn
[3,23,25,26]. Đó là nhu cầu chung của hầu hết các ngôn ngữ và tiếng Việt

- 18 -


TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

của chúng ta cũng phải là một ngoại lệ. Khác với các ngơn ngữ khác, tiếng
Việt có nhiều đặc điểm riêng biệt và rất khó xử lý bằng máy tính, nên các
đề tài liên quan đến các hệ thống tìm kiếm tiếng Việt cịn rất ít. Mà nhu cầu
tìm kiếm tài liệu trên kho tàng kiến thức của người Việt là rất lớn.
1.2.2. Quy trình tìm kiếm thơng tin trong hệ thống

Quy trình của một hệ thống tìm kiếm thơng tin như sau [3,23,26]:
• Người dùng muốn xem những tài liệu liên quan tới một chủ đề
nào đó.
• Người dùng cung cấp một mơ tả về chủ đề đó dưới dạng câu
truy vấn
• Từ câu truy vấn này hệ thống sẽ lọc ra những cụm từ chỉ mục
• Những cụm từ chỉ mục này sẽ được so khớp với những cụm từ
chỉ mục của các tài liệu đã được xử lý trước đó.
• Những tài liệu nào có mức độ liên quan cao nhất sẽ được trả
về cho người sử dụng.
Mục đích của hệ thống tìm kiếm thơng tin là tìm kiếm và hiển thị
cho người dùng một tập các thông tin thoả mãn nhu cầu của họ. Chúng ta
định nghĩa chính xác cho thơng tin cần thiết là “câu truy vấn” (query), và
các thông tin được chọn là “tài liệu” (documents). Mỗi cách tiếp cận trong
IR bao gồm hai thành phần chính (1) các kỹ thuật để biểu diễn thông tin
(câu truy vấn, tài liệu), và (2) phương pháp so sánh các cách biểu diễn này.
Mục đích là để tự động quy trình kiểm tra các tài liệu bằng cách tính tốn
độ tương quan giữa các câu truy vấn và tài liệu. Quy trình này được đánh

giá là thành cơng khi nó trả về các kết quả giống với các kết quả được con
người tạo ra khi so sánh câu truy vấn với các tài liệu.

- 19 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

Có một vấn đề thường xảy ra đối với hệ thống tìm kiếm là những từ
mà người dùng đưa ra trong câu truy vấn thường khác xa những từ trong
tập tài liệu chứa thơng tin mà họ tìm kiếm. Trường hợp như thế gọi là
“paraphrase problem” (vấn đề về diễn giải). Để giải quyết vấn đề này, hệ
thống đã tạo ra các hàm biểu diễn xử lý các câu truy vấn và các tài liệu một
cách khác nhau để đạt tới một độ tương thích nào đó.

Hình 2. Mơ hình hệ thống tìm kiếm thơng tin

Gọi miền xác định của hàm biểu diễn câu truy vấn q là Q, tập hợp
các câu truy vấn có thể có; và miền giá trị của nó là R, khơng gian thống
nhất biểu diễn thông tin. Gọi miền xác định của hàm biểu diễn tài liệu d là
D, tập hợp các tài liệu; và miền giá trị của nó là R2. Miền xác định của hàm
so sánh c là R × R và miền giá trị của nó là [0,1] là tập các số thực từ 0 đến
1. Trong một hệ thống tìm kiếm lí tưởng:

- 20 -

TIEU LUAN MOI download :



Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

c(q(query),d(doc)) = j(query,doc), ∀ query ∈ Q, ∀ doc ∈ D,
khi j: Q × D → [0,1] biểu diễn việc xử lý của người dùng giữa các mối
quan hệ của 2 thơng tin, được tính dựa trên một tiêu chuẩn nào đó(ví dụ: sự
giống nhau về nội dung hay sự giống nhau về kiểu,...). Hình 2 minh hoạ
mối quan hệ này.
Có hai kiểu hệ thống tìm kiếm: tìm kiếm dựa trên so khớp chính xác và
dựa trên sắp xếp. Mơ hình trên đây có thể mơ tả cả hai cách tiếp cận như
thế. Trong hệ thống tìm kiếm dựa trên so khớp chính xác, miền giá trị của c
được giới hạn hai lựa chọn là 0 và 1, và nó được chuyển sang nhị phân để
quyết định liệu 1 tài liệu có thoả biểu thức bool được xác định bởi câu truy
vấn hay không? Các hệ IR dựa trên sự so khớp chính xác thường cung cấp
các tài liệu khơng sắp xếp thoả mãn câu truy vấn của người sử dụng, hầu
hết các hệ thống tìm kiếm hiện nay đều dùng cách này. Cách hoạt động chi
tiết của hệ thống sẽ được mô tả ở phần sau.
Đối với hệ thống IR dựa trên sắp xếp, thì các tài liệu sẽ được sắp xếp
theo thứ tự giảm dần về mức độ liên quan. Có 3 loại hệ thống tìm kiếm dựa
trên sắp xếp: “ranked Boolean”, “probabilistic” và “similarity base”. Trong
3 cách này thì miền giá trị của c là [0, 1], tuy nhiên chúng khác nhau ở cách
tính “giá trị trạng thái tìm kiếm” (“retrieval status value”):
• Trong hệ thống dựa trên “ranked Boolean” giá trị này là mức độ mà
thông tin thoả mãn biểu thức Bool được chỉ ra bởi các thơng tin cịn lại.
• Trong hệ thống dựa trên “probabilistic”, khái niệm này hơi khác một
chút, giá trị này là xác suất mà thơng tin có liên quan đến một câu truy vấn.
Rất nhiều hệ thống tìm kiếm dựa trên xác suất được thiết kế để chấp nhận
câu truy vấn được diễn tả bằng ngôn ngữ tự nhiên hơn là một biểu thức
bool.


- 21 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

• Trong hệ thống tìm kiếm dựa trên sự giống nhau, giá trị trạng thái
tìm kiếm được tính bằng cách tính mức độ giống nhau của nội dung thơng
tin.
Trong các hệ thống tìm kiếm dựa trên sự so khớp chính xác, việc đánh
giá hệ thống chủ yếu dựa trên việc đánh giá mức độ liên quan. Giả sử j là
giá trị nhị phân và được cho trước. Nói cách khác, ta giả sử rằng các tài liệu
hoặc có hoặc khơng có liên quan đến câu truy vấn, và độ liên quan giữa tài
liệu và câu truy vấn do con người xác định là chính xác. Theo giả định này,
tính hiệu quả của các hệ thống tìm kiếm dựa trên so khớp chính xác được
đánh giá dựa trên hai đại lượng thống kê là “độ chính xác” ( precision) và
“độ hồi tưởng” (recall). Độ chính xác là tỷ lệ các tài liệu được chọn, các tài
liệu thực sự có liên quan đến các thông tin mà người dùng cần, độ hồi
tưởng là tỉ lệ tài liệu có liên quan được sắp xếp chính xác theo độ liên quan
bởi hệ thống tìm kiếm. Nói cách khác, độ chính xác bằng 1 trừ đi tỷ lệ cảnh
báo sai, trong khi đó độ hồi tưởng đo mức độ hồn chỉnh của việc tìm
kiếm. Về hai độ đo đánh giá này cũng sẽ được đề cập chi tiết trong phần
tiêu chuẩn đánh giá phân cụm cho thuật tốn phân cụm ở phía sau.
Việc đánh giá tính hiệu quả của hệ thống tìm kiếm dựa trên sắp xếp
là phức tạp hơn. Một cách tính độ hiệu quả phổ biến cho các hệ thống này
“độ chính xác trung bình”. Nó được tính bằng cách chọn 1 tập lớn hơn các
tài liệu ở đầu danh sách có giá trị hồi tưởng giữa 0 và 1. Phương pháp
thường được sử dụng là phương pháp tính dựa trên 5,7,11 điểm theo độ hồi
tưởng. Độ chính xác sau đó sẽ tính cho từng tập một. Quy trình sẽ được lặp

lại cho từng câu truy vấn, và tương ứng với mỗi độ chính xác trung bình sẽ
cho một độ hồi tưởng. Mỗi giá trị trung bình của những số này sau đó sẽ
được tính tốn và ghi nhận như một đặc trưng của hệ thống. Độ chính xác
trung bình càng lớn thì càng tốt, và việc so sánh chỉ thực sự có ý nghĩa khi

- 22 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

chúng ta sử dụng cùng một tập tài liệu và câu truy vấn. Tuy nhiên độ chính
xác trung bình cũng làm giảm đi mức độ thay đổi của các câu truy vấn có
các đặc tính khác nhau (ví dụ như số lượng tài liệu có liên quan khác nhau).
Hơn thế nữa, các tài liệu có liên quan thường tập trung ở đầu danh sách sắp
xếp nên thơng thường độ chính xác sẽ giảm mỗi khi tập tài liệu được mở
rộng để tăng độ hồi tưởng.
1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm

Như vậy, với việc phân tích nhu cầu phân cụm đối với các tài liệu
Web, khi ta xây dựng một hệ thống tìm kiếm thì đồng thời ta cũng sẽ tiến
hành tích hợp module phân cụm vào hệ thống này. Việc phân cụm văn bản
như một phương thức tổ chức các dữ liệu trả lại khác giúp người sử dụng
thay vì phải xem xét chọn lọc danh sách dài các văn bản theo thứ tự để tìm
kiếm các văn bản liên quan thì chỉ cần xem xét trong các lĩnh vực mà người
sử dụng quan tâm mà thơi. Như vậy hệ thống tìm kiếm sẽ trở nên hữu dụng
hơn cho người sử dụng.
1.3. Kết luận chương 1
Sự phát triển của Internet dẫn đến nhu cầu tìm kiếm, khai thác, tổ

chức, truy cập và duy trì thơng tin đối với người sử dụng thường xuyên
hơn. Những người sử dụng các máy tìm kiếm Web thường bị bắt buộc xem
xét chọn lọc thông qua một danh sách thứ tự dài của các mẩu thông tin văn
bản được trả trở lại bởi các máy tìm kiếm. Yêu cầu phân cụm tài liệu, cụ
thể hơn là tài liệu Web trở thành bài toán cho các nhà khoa học nghiên cứu
và giải quyết. Sau đây chúng ta sẽ nghiên cứu tiếp các vấn đề liên quan tới
bài toán phân cụm nêu trên.

- 23 -

TIEU LUAN MOI download :


Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.

CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB
2.1. Khái quát về các thuật tốn phân cụm tài liệu
Như đã trình bày ở chương 1, phân cụm tài liệu đã và đang được
nghiên cứu như là một cách cải tiến hiệu năng cho cách máy tìm kiếm bằng
cách phân cụm trước toàn bộ tập hợp. M. Steinbach và các đồng tác giả [4]
đã cung cấp một số nội dung khái quát về các thuật toán phân cụm tài liệu.
Theo các tác giả [4], rất nhiều thuật toán phân loại tài liệu đã xuất
hiện trong các tài liệu. Các thuật toán Agglomerative Hierarchical
Clustering (AHC – Phân cụm tích tụ có thứ bậc) được sử dụng thường
xuyên nhất. Những thuật toán này thường là chậm khi được áp dụng với
một tập lớn các tài liệu. Các phương thức liên kết đơn (Single-link) và
trung bình nhóm (group-average) thường có độ phức tạp thời gian khoảng
O(n2) trong khi liên kết đầy đủ thường mất khoảng O(n3).
Có nhiều điều kiện kết thúc cho các thuật tốn AHC được đưa ra,
nhưng chúng thường là được dựa trên các các quyết định cứng. Những

thuật toán này rất nhạy cảm với các điều kiện dừng – khi thuật toán trộn lỗi
nhiều phân cụm tốt, kết quả có thể là vô nghĩa đối với người dùng. Trong
lĩnh vực phân cụm web những kết quả của các câu truy vấn có thể là cực kỳ
nhiều (theo số lượng, độ dài, kiểu và độ quan hệ với tài liệu), việc nhạy
cảm với các điều kiện dừng rất dễ dẫn đến các kết quả nghèo nàn. Một
thuộc tính nữa của phân cụm Web đó là chúng ta thường xuyên nhận được
nhiều phần ko cần thiết. Đó là một kiểu nhiễu có thể gây giảm độ ảnh
hưởng của các tiêu chí ngừng thường được sử dụng hiện nay.
Các thuật tốn phân cụm có thời gian tuyến tính là các ứng cử viên
cho yêu cầu về tốc độ đối với các phân cụm online [11].

- 24 -

TIEU LUAN MOI download :