Đồ Án Xây dựng hệ thống Focused Crawler

PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP

1. Thông tin về sinh viên
Họ và tên sinh viêndata:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=" class="mceSmilieSprite mceSmilie8" alt="" title="Big Grin ">ương Minh Sơn
Điện thoại liên lạc :0976738243 Email: <a class="__cf_email__" href="http://www.cloudflare.com/email-protection" data-cfemail="cfbca0a1aba2fef78fb6aea7a0a0e1aca0a2">[email protected]<script type="text/javascript">
(function(){try{var s,a,i,j,r,c,l,b=document.getElementsByTagName("script");l=b[b.length-1].previousSibling;a=l.getAttribute(data-cfemail);if(a){s=;r=parseInt(a.substr(0,2),16);for(j=2;a.length-j;j+=2){c=parseInt(a.substr(j,2),16)^r;s+=String.fromCharCode(c);}s=document.createTextNode(s);l.parentNode.replaceChild(s,l);}}catch(e){}})();

Lớp: HTTT_B , K49 Hệ đào tạo: kỹ sư chính quy
Đồ án tốt nghiệp được thực hiện tại: Bộ môn các hệ thống thông tin
Thời gian làm ĐATN: Từ ngày 23/ 02 /2009 đến 10 / 06 /2009

[B]2. Mục đích nội dung của ĐATN
ã Xây dựng hệ thống Focused Crawler.[/B]

[B]3. Các nhiệm vụ cụ thể của ĐATN [/B]
ã Tìm hiểu kiến trúc tổng thể hệ thống Search Engine, Vertical Search Engine, Crawler, Focused Crawler.
ã Tìm hiểu các phương pháp xây dựng hệ thống Focused Crawler
ã Phân tích ,thiết kế cài đặt một hoặc hai phương pháp xây dựng hệ thống và đánh giá kết quả




[B]4. Lời cam đoan của sinh viên:[/B]
Tôi – Dương Minh Sơn- cam kết ĐATN là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn của PGS.TS.Trần Đình Khang
Các kết quả nêu trong ĐATN là trung thực, không phải là sao chép toàn văn của bất kỳ công trình nào khác.

[B] Hà Nội, ngày 25 tháng 5 năm 2009
Tác giả ĐATN[/B]


Dương Minh Sơn



[B]TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP[/B]

Vertical Search Engine là một hệ thống Search Engine thực hiện việc tìm kiếm trên một miền lĩnh vực hẹp. Thành phần trung tâm của nó là Focused Crawler. Nhiệm vụ của nó là tiến hành thu thập các tài liệu trên internet liên quan hoặc thuộc về một miền lĩnh vực nào đó. Đồ án tốt nghiệp gồm năm chương.

Chương một, trình bày một cách tổng thể về các hệ thống Search Engine, Vertical Search Engine, Crawler, Focused Crawler. Giúp ta hiểu về nguyên lý hoạt động ,các thành phần của các hệ thống trên.

Vấn đề mấu chốt của Focused Crawler là với một tài liệu d, một lĩnh vực t, hãy ước lượng giá trị hàm liên quan giữa d và t : R(d,t) . Để làm được điều này ,trước hết ta cần một mô hình để biểu diễn tài liệu và lĩnh vực. Chương hai, trình bày về mô hình không gian vector ,mô hình hay sử dụng nhất hiện nay. Ngoài ra hệ thống Focused Crawler cũng như các hệ thống Crawler khác được xây dựng trên cơ sở các giải thuật Crawling. Phần tiếp theo của chương hai trình bày các giải thuật Crawling nổi tiếng nhất. Phần cuối cùng của chương này giới thiệu về thư viện mã nguồn mở Nutch mà ta sẽ sử dụng để cài đặt hệ thống.

Trên cơ sở mô hình không gian vector, chương ba, trình bày hai phương pháp ước lượng giá trị hàm R(d,t) dựa trên hàm tương tự (Similarity Function) và phân loại Bayes (Bayes Classification). Đánh giá độ phức tạp tính toán, các vấn đề lưu trữ và cài đặt hai phương pháp trên.

Chương bốn, nói tới việc phân tích ,thiết kế hệ thống Focused Crawler theo hướng cấu trúc.

Chương năm, trình bày tổng quan các phương pháp đánh giá một hệ thống Focused Crawler và đánh giá hệ thống vừa cài đặt. Trong chương này chúng ta cũng đưa ra những kết luận cuối cùng về bài toán mà đồ án giải quyết cũng như định hướng phát triển.



[B]ABSTRACT OF THESIS[/B]
Vertical Search Engine is a Search Engine which you can search for information about a particular topic. The main component of Vertical Search Engine is Focused Crawler. Focused Crawler is a robot, working in the Internet that retrieves the documents belonging to the topic.

Chapter one will present the architecture, principle of Search Engines, Vertical Search Engines, Crawlers, Focused Crawlers.

The most important problem in developing a Focused Crawler is estimates the value of a function: R(d,t) where d is a document and t is a topic. We need a model to present documents and topics. So, chapter two will introduce the Vector Space Model, a famous model in Information Retrieval. In this chapter, we also discuss about crawling algorithm. The last item in this chapter is about Nutch, a java open source library for developing Search Engine.

By using Vector Space Model, chapter three will present two methods to estimates R(d,t). The first method is based on Similarity Function and the second method is based on Bayes Classification .We will also discuss about the complexity, implementation problem of the two methods.

In chapter four, we will anaylize and design the system including functions, data structure.

The last chapter will present the evaluation method to evaluate a Focused Crawler. We will evaluate the system which we implemented. This chapter will also make conclusions of the problem we are solving and its development in future.



[B]Mục lục

Mục lục 4
Lời nói đầu 6
Chương 1.Giới thiệu 8[/B]
1.1. Hệ thống tìm kiếm tổng quát 8
1.1.1. Giới thiệu 8
1.1.2. Nguyên lý và kiến trúc của các hệ thống tìm kiếm 9
1.1.3. Thành phần Crawler 13
1.1.4. Các vấn đề khó khăn nhất khi xây dựng hệ thống tìm kiếm 15
1.2. Hệ thống tìm kiếm theo chiều sâu 15
1.2.1. Tại sao phải xây dựng hệ thống tìm kiếm theo chiều sâu 15
1.2.2. Nguyên lý và kiến trúc các hệ thống tìm kiếm theo chiều sâu. 17
1.2.3. Thành phần Focused Crawler 17
[B]Chương 2: Cơ sở lý thuyết 20[/B]
2.1. Các bước xử lý ngôn ngữ thông thường trong khi tìm kiếm 20
2.1.1. Loại bỏ các từ dừng (Stop Word) 20
2.1.2. Đưa một từ trở về từ gốc (Stemming) 20
2.2. Mô hình không gian vector 21
2.2.1. Mô hình không gian vector 21
2.2.2.Ứng dụng mô hình không gian vector trong các hệ thống tìm kiếm 24
2.3. Các giải thuật Crawling 29
2.3.1. Giới thiệu 29
2.3.2. Các độ đo 31
2.3.3. Các giải thuật Crawling 33
2.3.4.Đánh giá các giải thuật Crawling 37
2.4. Thư viện mã nguồn mở Nutch 38
2.4.1. Giới thiệu Nutch 38
2.4.2. Kiến trúc của một hê thống tìm kiếm dựa Nutch 39
[B]Chương 3: Xây dựng hệ thống Focused Crawler 46[/B]
3.1.Hướng tiếp cận thứ nhất 46
3.2. Hướng tiếp cận thứ hai 47
3.2.1. Xây dựng Focused Crawler dựa trên hàm tương tự 47
3.2.2. Xây dựng Focused Crawler dựa trên định lý Bayes 53
[B]Chương 4: Phân tích thiết kế hệ thống Focused Crawler 59[/B]
4.1. Phân tích hệ thống 60
4.1.1. Phân tích hệ thống về mặt chức năng 60
4.1.2. Phân tích hệ thống về mặt dữ liệu 66
4.2. Thiết kế hệ thống 68
4.2.1. Thiết kế dữ liệu 68
4.2.2. Thiết kế chương trình 73
[B]Chương 5: Đánh giá kết quả 76[/B]
5.1. Các phương pháp đánh giá hệ thống Focused Crawler 76
5.1.1. Đánh giá giải thuật Crawling 77
5.1.2. Đánh giá việc phân loại tài liệu 79
5.2. Đánh giá hệ thống đã xây dựng được 82
5.2.1. Đánh giá giải thuật Crawling sử dụng 82
5.2.2. Đánh giá giải thuật phân loại tài liệu 84
5.3. Kết luận 89
Phụ lục 1: Danh mục các hình vẽ trong tài liệu 91
Phụ lục 2 : Danh sách các bảng trong tài liệu 92
Phụ lục 3: Danh sách các thuật ngữ tiếng Anh 93
Phụ lục 4: Một số website tìm kiếm theo chiều sâu hiện nay 94
Tài liệu tham khảo 95

[B]Lời nói đầu[/B]

Thông tin ngày càng có vai trò quan trọng trong cuộc sống. Đến đầu thế kỷ 21 đã xuất hiện nền kinh tế tri thức coi tri thức, thông tin là đầu vào của nhiều công đoạn sản xuất. Xuất hiện một bộ phận những người lao động tạo ra giá trị bằng cách phổ biến thông tin. Đối với nhiều quốc gia, tổ chức, cá nhân, thông tin thực sự là một tài nguyên.

Từ những năm 60 của thế kỷ trước vấn đề khai thác và sử dụng thông tin hiệu quả đã được đặt ra, và lúc này khi mạng Internet trở nên phổ biến trên toàn cầu nó càng trở nên bức thiết hơn. Trong khai thác và sử dụng thông tin thì tìm kiếm thông tin là công đoạn quan trọng nhất.Vì vậy một cách tất yếu con người cần có một hệ thống tìm kiếm thông tin hiệu quả ,và cũng tất nhiên nó phải làm việc tốt trên môi trường Internet.Các công cụ như vậy được gọi là Search Engine.Đến giữa những năm 90 đã xuất hiện những hệ thống tìm kiếm đầu tiên Aliweb, sau đó là hàng lọat tên tuổi lớn Altavista (1995) ; Google (1998) ; Yahoo! Search (2004) ; MSN Search (2005)

Trong đồ án này em mong muốn tiếp cận và xây dựng thử nghiệm một hệ thống thu thập thông tin tập trung (Focused Crawler),hạt nhân của một hệ thống tìm kiếm theo chiều sâu (Vertical Search Engine).

Báo cáo bao gồm 5 phần :
ã Chương 1: Giới thiêu: đề cập sự cần thiết và lí do ra đời của hệ thống,các khái niệm liên quan, các hệ thống đang tồn tại.
ã Chương 2: Cơ sở lý thuyết: đề cập phương pháp luận ,các mục kiến thức liên quan để xây dựng hệ thống
ã Chương 3: Các phương pháp xây dựng hệ thống Focused Crawler: trình bày hai phương pháp cơ bản xây dựng hệ thống dựa trên mô hình không gian vector
ã Chương 4: Phân tích , thiết kế hệ thống: trình bày việc phân tích ,thiết kế hệ thống theo hướng cấu trúc.
ã Chương 5: Kết luận: trình bày các phương pháp đánh giá hệ thống Focused Crawler, rồi sử dụng để đánh giá kết quả thu được

Do thời gian và kiến thức cũng như kinh nghiệm hạn chế, nên đồ án không tránh khỏi thiếu sót .Kính mong được thầy cô góp ý, hướng dẫn thêm cho em hoàn thiện đồ án hơn.
Đồ án được hoàn thành dưới sự chỉ bảo và hướng dẫn tận tình của PGS.TS.Trần Đình Khang. Với tư duy khoa học nhạy bén, và kinh nghiệm phong phú , thầy đã góp nhiều ý kiến quý báu để chúng em lựa chọn những hướng tiếp cận và giải pháp phù hợp nhất.

Em cũng xin gửi lời cảm ơn tới các anh chị tại phòng nghiên cứu công ty cổ phần A.N.Lab và đặc biệt là cá nhân anh Đinh Khắc Dũng ,trưởng phòng, đã tạo điều kiện để em thực tập tốt nghiệp ,cài đặt ,và chạy thử hệ thống trên môi trường của công ty.