ĐẠ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Ỹ NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS HÀ QUANG THỤY
Hà Nội - 2007
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 3 -
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
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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 5 -
3.2. Thuật toá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
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
/>
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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 8 -
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 toá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 toá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 toán phân cụm văn bản ở đây cần có được một tính chất rất
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,
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 10 -
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ể hoàn thiện được kết quả nghiên
cứu.
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 11 -
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ỉ
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
khoán, .v.v.
• Phân lớp và dự đoá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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 13 -
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 khoá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
điển Bách khoa toà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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 15 -
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 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 [25, 26].
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:
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 17 -
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 toàn bộ một CSDL có sẵn gồm rất nhiều tài
liệu Web. Thuật toán phân cụm cần tiến hành việc phân cụm toàn bộ tập dữ
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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 19 -
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
- 21 -
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.
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 toá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
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 23 -
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
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 toá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].
Copyright: Tài liệu đại học ©