Luận văn tốt nghiệp: Giải pháp tính hạng trang khai thác cấu trúc Block của web và áp dụng vào máy tìm kiếm

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

95
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ngày nay, với những tác động to lớn và mạnh mẽ của mạng Internet tới đời sống kinh tế, chính trị và văn hóa của con người, lĩnh vực khai phá dữ liệu Web đã và đang trở thành lĩnh vực nghiên cứu thời sự, thu hút được sự quan tâm của rất nhiều nhà nghiên cứu. Khai phá dữ liệu Web là điểm hội tụ của rất nhiều lĩnh vực nghiên cứu như: cơ sở dữ liệu, truy xuất thông tin (information retrival), trí tuệ nhân tạo, nó còn là một lĩnh vực nhỏ trong học máy (machine learning)...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn tốt nghiệp: Giải pháp tính hạng trang khai thác cấu trúc Block của web và áp dụng vào máy tìm kiếm

Luận văn tốt nghiệp Giải pháp tính hạng trang khai thác cấu trúc Block của web và áp dụng vào máy tìm kiếm
Mở đầ u Ngày nay, với những tác động to lớn và mạnh mẽ của mạng Internet tới đời sống kinh tế, chính trị và văn hóa của con người, lĩnh vực khai phá dữ liệu Web đã và đang trở thành lĩnh vực nghiên cứu thời sự, thu hút được sự quan tâm của rất nhiều nhà nghiên cứu. Khai phá dữ liệu Web là điểm hội tụ của rất nhiều lĩnh vực nghiên cứu như: cơ sở dữ liệu, truy xuất thông tin (information retrival), trí tuệ nhân tạo, nó còn là một lĩnh vực nhỏ trong học máy (machine learning) và xử lý ngôn ngữ tự nhiên. Một trong những lĩnh vực nghiên cứu đang rất được quan tâm hiện nay trong khai phá Web là việc xây dựng các công cụ tìm kiếm trên Web. Bởi trong bối cảnh xã hội thông tin ngày nay, nhu cầu nhận được các thông tin một cách nhanh chóng, chính xác đang ngày càng trở nên cấp thiết. Để tìm ra được các thông tin có ích đối với mỗi người dùng, đặc biệt là với những người dùng thiếu kinh nghiệm hoàn toàn không phải là việc đơn giản. Với một công cụ tìm kiếm, khả năng người dùng có thể duyệt Web và định vị được các trang Web mình quan tâm đã trở nên dễ dàng hơn nhiều. Tuy nhiên hiện nay, do sự phát triển và thay đổi với tốc độ quá nhanh của Internet, các công cụ tìm kiếm đang phải đối mặt với những bài toán nan giải về tốc độ. Trong đó có bài toán về tốc độ tính toán hạng cho các trang Web, thực thi nhiệm vụ tính toán độ “quan trọng” cho các trang thông tin kết quả tìm được so với yêu cầu tìm kiếm của người dùng. Vì kích thước của World Wide Web là vô cùng lớn, lên tới hàng tỉ trang web, không những thế các trang Web này không ở trạng thái tĩnh mà luôn luôn thay đổi. Do đó tính hiệu quả về thời gian càng trở nên quan trọng. Nếu phép tính PageRank cho tập các trang web trong cơ sở dữ liệu không đủ nhanh, hệ thống tìm kiếm sẽ không cung cấp được chất lượng tìm kiếm tốt cho người dùng. Ý thức đây là một lĩnh vực nghiên cứu có nhiều triển vọng, chúng tôi đã chọn hướng nghiên cứu “Giải pháp tính hạng trang khai thác cấu trúc Block của Web và áp dụng vào máy tìm kiếm” cho đề tài khóa luận tốt nghiệp của mình. Khóa luận tập trung nghiên cứu bài toán tính hạng trang web (PageRank) trong các máy tìm kiếm: cấu trúc, thuật toán cũng như các tiêu chuẩn đánh giá quá trình này. Chúng tôi cũng đã áp dụng các lý thuyết trên để đi sâu phân tích mã nguồn, tìm hiểu cơ chế thực thi quá trình tính PageRank trong máy tìm kiếm Vinahoo, một máy tìm kiếm tiếng Việt mã nguồn mở với nhiều tính năng ưu việt. Từ việc nghiên cứu này, chúng tôi đã đề xuất một giải pháp áp dụng khái niệm thành phần liên thông trong ma trận liên kết Web trong Vinahoo, đồng thời thực hiện việc cài đặt thử nghiệm trên mã nguồn của máy tìm kiếm này. Nội dung của khóa luận được tổ chức thành bốn chương với nội dung được giới thiệu như dưới đây. 1
Chương 1 với tên gọi “Tổng quan về khai phá dữ liệu web và máy tìm kiếm” trình bày về những nội dung nghiên cứu cơ bản của khai phá web, những thuận lợi và khó khăn trong lĩnh vực này. Phần cuối của chương này trình bày các thành phần cơ bản của một máy tìm kiếm. “Một số thuật toán tính hạng trang điển hình” là tiêu đề của chương 2. Phần đầu chương này giới thiệu tổng quan về bài toán xêp hạng trang Web trong máy tìm kiếm và thuật toán tính PageRank cơ bản. Việc phân tích nhu cầu tăng tốc độ tính toán PageRank trong máy tìm kiếm, một số thuật toán cải tiến từ phương pháp PageRank cùng với đánh giá được trình bày trong phần cuối của chương. Chương 3 với tên gọi “Thuật toán sử dụng cấu trúc Block theo thành phần liên thông” tập trung nghiên cứu về giải pháp khai thác cấu trúc Web. Chương này giới thiệu khái niệm, một số vấn đề về lý thuyết, chứng minh và đánh giá thuật toán CCP sử dụng cấu trúc này. Chương 4 với tiêu đề “Giải pháp tính hạng trang cải tiến cho máy tìm kiếm Vinahoo” giới thiệu thành phần tính PageRank trong module đánh chỉ số của Vinahoo, các cải tiến, cài đặt và đánh giá kết quả thực nghiệm. 2
Chương 1. Tổng quan về khai phá dữ liệu Web và máy tìm kiếm 1.1. Khai phá dữ l iệ u Web 1.1.1. Tổng quan về khai phá dữ liệu Web Ngày nay, 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). 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à chi phí thấp để duy trì một trang Web trên Internet. So sánh với những dịch vụ khác như đăng tin hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web "đòi" rẻ hơn rất nhiều và 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 Internet như là cuốn từ điển Bách khoa toàn thư với nội dung và hình thức đa dạng. Nó 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 ... WWW Tri thức Hình 1. Khai phá Web, công việc không dễ dàng Tuy nhiên, Internet là một môi trường đa phương tiện động bao gồm sự kết hợp của các cơ sở dữ liệu không đồng nhất, các chương trình và các giao tiếp người dùng. Rõ ràng, khai phá dữ liệu text chỉ là một lĩnh vực nhỏ trong môi trường này. Khai phá dữ liệu trên Internet, hay thường được gọi là khai phá web ngoài việc cần khai phá được nội dung các trang văn bản, còn phải khai thác được các nguồn lực nói trên cũng như mối quan hệ giữa chúng. Khai phá Web, sự giao thoa giữa khai phá dữ liệu và Word-Wide-Web, đang phát triển mạnh mẽ và bao gồm rất nhiều lĩnh vực nghiên cứu như cơ sở dữ liệu, trí tuệ nhân tạo, truy xuất thông tin (information retrival) và nhiều lĩnh vực khác. Các công nghệ Agent-base, truy xuất thông tin dựa trên khái niệm (concept-based), truy xuất thông tin sử dụng case-base reasoning và 3
tính hạng văn bản dựa trên các đặc trưng (features) siêu liên kết... thường được xem là các lĩnh vực nhỏ trong khai phá web. Khai phá Web vẫn chưa được định nghĩa một cách rõ ràng và các chủ đề trong đó vẫn tiếp tục được mở rộng. Tuy vậy, chúng ta có thể hiểu khai phá web như việc: trích 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[9]. Hình 2 thể hiện một sự phân loại các lĩnh vực nghiên cứu quen thuộc trong khai phá Web. Người ta thường phân khai phá web thành 3 lĩnh vực chính: khai phá nội dung web (web content mining), khai phá cấu trúc web (web structure mining) và khai phá sử dụng web (web usage mining). KHAI PHÁ DỮ LIỆU WEB Khai phá nội Khai phá cấu Khai phá sử dung Web trúc Web dụng Web Tối ưu kết Khai phá các Phân tích các xu Khai phá nội quả trả về mẫu truy cập hướng cá nhân dung trang Web Hình 2: Các nội dung trong khai phá Web 1.1.2. Các lĩnh vực của khai phá dữ liệu Web 1.1.2.1 Khai phá nội dung Web Phần lớn các tri thức của World-Wide Web được chứa trong nội dung văn bản. Khai phá nội dung web (web content mining) là các quá trình xử lý để lấy ra các tri thức từ nội dung các trang văn bản hoặc mô tả của chúng. Có hai chiến lược khai phá nội dung web: một là khai phá trực tiếp nội dung của trang web, và một là nâng cao khả năng tìm kiếm nội dung của các công cụ khác như máy tìm kiếm. - Khai phá nội dung trang web(Web Page summarization): liên quan tới việc truy xuất các thông tin từ các văn bản có cấu trúc, văn bản siêu liên kết, hay các văn bản bán cấu trúc. Lĩnh vực này liên quan chủ yếu tới việc khai phá bản thân nội dung các văn bản. 4
- Tối ưu kết quả trả về (search engine result summarization): Tìm kiếm trong 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, chọn lọc kết quả theo mức độ hợp lệ với yêu cầu người dùng. Quá trình này thường sử dụng các thông tin như tiêu đề trang, URL, content-type, các liên kết trong trang web... để tiến hành phân lớp và đưa ra tập con các kết quả tốt nhất cho người dùng. 1.1.2.2. Khai phá cấu trúc web Nhờ vào các kết nối giữa các văn bản siêu liên kết, World-Wide Web có thể chứa đựng nhiều thông tin hơn là chỉ các thông tin ở bên trong văn bản. Ví dụ, các liên kết trỏ tới một trang web chỉ ra mức độ quan trọng của trang web đó, trong khi các liên kết đi ra từ một trang web thể hiện các trang có liên quan tới chủ đề đề cập trong trang hiện tại. Và nội dung của khai phá cấu trúc Web (web structure mining) là các quá trình xử lý nhằm rút ra các tri thức từ cách tổ chức và liên kết giữa các tham chiếu của các trang web. 1.1.2.3 Khai phá sử dụng web Khai phá sử dụng web (web usage mining) hay khai phá hồ sơ web (web log mining) là việc xử lý để lấy ra các thông tin hữu ích trong các hồ sơ truy cập Web. Thông thường các web server thường ghi lại và tích lũy các dữ liệu về các tương tác của người dùng mỗi khi nó nhận được một yêu cầu truy cập. Việc phân tích các hồ sơ truy cập web của các web site khác nhau sẽ dự đoán các tương tác của người dùng khi họ tương tác với Web cũng như tìm hiểu cấu trúc của Web, từ đó cải thiện các thiết kế của các hệ thống liên quan. Có hai xu hướng chính trong khai phá sử dụng web là General Access Pattern Tracking và Customizied Usage tracking. - Phân tích các mẫu truy cập (General Access Pattern tracking): phân tích các hồ sơ web để biết được các mẫu và các xu hướng truy cập. Các phân tích này có thể giúp cấu trúc lại các site trong các phân nhóm hiệu quả hơn, hay xác định các vị trí quảng cáo hiệu quả nhất, cũng như gắn các quảng cáo sản phẩm nhất định cho những người dùng nhất định để đạt được hiệu quả cao nhất... - Phân tích các xu hướng cá nhân (Cusomized Usage tracking): Mục đích là để chuyên biệt hóa các web site cho các lớp đối tượng người dùng. Các thông tin được hiển thị, độ sâu của cấu trúc site và định dạng của các tài nguyên, tất cả đều có thể chuyên biệt hóa một cách tự động cho mỗi người dùng theo thời gian dựa trên các mẫu truy cập của họ. 5
1.1.3. Khó khăn của khai phá Web World Wide Web là một hệ thống rất lớn phân bố rộng khắp, cung cấp thông tin trên mọi lĩnh vực khoa học, xã hội, thương mại, văn hóa,... Web là một nguồn tài nguyên giàu có cho Khai phá dữ liệu. Những quan sát sau đây cho thấy Web đã đưa ra những thách thức lớn cho công nghệ Khai phá dữ liệu [6]. 1.1.3.1. Web quá lớn để tổ chức thành kho dữ liệu phục vụ Dataming Các CSDL truyền thống thì có kích thước không lớn lắm và thường được lưu trữ tập trung, trong khi đó kích thước Web rất lớn, tới hàng terabytes và thay đổi liên tục, không những thế còn phân tán trên rất nhiều máy tính khắp nơi trên thế giới. Một vài nghiên cứu về kích thước của Web[6] đã đưa ra các số liệu như sau: Hiện nay trên Internet có khoảng hơn một tỷ các trang Web được cung cấp cho người sử dụng. Kích thước trung bình của mỗi trang là 5-10KB thì tổng kích thước của WWW ít nhất là 10 terabyte. Còn tỷ lệ tăng của các trang Web thì thật sự gây ấn tượng. Hai năm gần đây số các trang Web tăng gấp đôi và còng tiếp tục tăng trong hai năm tới. Nhiều tổ chức và xã hội đặt hầu hết những thông tin công cộng của họ lên Web. Như vậy việc xây dựng một kho dữ liệu (datawarehouse) để lưu trữ, sao chép hay tích hợp các dữ liệu trên Web là gần như không thể. 1.1.3.2. Độ 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 Các dữ liệu trong các CSDL truyền thống thì thường là loại dữ liệu đồng nhất (về ngôn ngữ, định dạng,…), còn dữ liệu Web thì hoàn toàn không đồng nhất. Dữ liệu Web bao gồm rất nhiều loại ngôn ngữ khác nhau (cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập trình), nhiều loại định dạng khác nhau (text, HTML, PDF, hình ảnh, âm thanh,…), nhiều loại từ vựng khác nhau (địa chỉ email, các liên kết, các mã nén (zipcode), số điện thoại...). Nói cách khác, các trang Web thiếu một cấu trúc thống nhất. Chúng được coi như một thư viện kỹ thuật số rộng lớn, tuy nhiên số lượng khổng lồ các tài liệu trong thư viện thì không được sắp xếp theo một tiêu chuẩn đặc biệt nào, không theo phạm trù nào,... Điều này là một thử thách rất lớn cho việc tìm kiếm thông tin cần thiết trong một thư viện như thế. 1.1.3.3. Web là một nguồn tài nguyên thông tin có độ thay đổi cao Web không chỉ có thay đổi về độ lớn mà thông tin trong chính các trang Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu [6] hơn 500.000 trang Web 6
trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì 50% các trang trong tên miền đó biến mất, nghĩa là địa chỉ URL của nó không còn tồn tại nữa. Tin tức, thị trường chứng khoán, các công ty quản cáo và trung tâm phục vụ Web thường xuyên cập nhật trang Web của họ. Thêm vào đó sự kết nối thông tin và sự truy cập bản ghi cũng được cập nhật. 1.1.3.4. Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng Internet hiện nay nối với khoảng 50 triệu trạm làm việc [6], và cộng đồng người dùng vẫn đang nhanh chóng lan rộng. Mỗi người dùng có một kiến thức, mối quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng không có kiến thức tốt về cấu trúc mạng thông tin, hoặc không có ý thức cho những tìm kiếm, rất dễ bị "lạc" khi trong khối dữ liệu khổng lồ của mạng hoặc sẽ chán khi tìm kiếm mà chỉ nhận những mảng thông tin không mấy hữu ích. 1.1.3.5. Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích Theo thống kê [6], 99% của thông tin Web là vô ích với 99% người dùng Web. Trong khi những phần Web không được quan tâm lại bị búi vào kết quả nhận được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào để nhận được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng? Như vậy chúng ta có thể thấy các điểm khác nhau giữa việc tìm kiếm trong một CSDL truyền thống với vviệc tìm kiếm trên Internet. Những thách thức trên đã đẩy mạnh việc nghiên cứu khai phá và sử dụng tài nguyên trên Internet. 1.1.4. Thuận lợi của khai phá Web Bên cạnh những thử thách trên, khai phá Web cũng có những thuận lợi: 1. Web bao gồm không chỉ có các trang mà còn có cả các liên kết trỏ từ trang này tới trang khác. Khi một tác giả tạo một liên kết từ trang của ông ta tới một trang A có nghĩa là A là trang có hữu ích với vấn đề đang bàn luận. Nếu một trang càng nhiều liên kết từ trang khác trỏ đến chứng tỏ trang đó quan trọng. Vì vậy các thông tin liên kết trang sẽ cung cấp một lượng thông tin giàu có về mối liên quan, chất lượng, và cấu trúc của nội dung trang Web, và vì thế là một nguồn tài nguyên lớn cho khai phá Web. 2. Một máy chủ Web thường đăng ký một bản ghi đầu vào (Weblog entry) cho mọi lần truy cập trang Web. Nó bao gồm địa chỉ URL, địa chỉ IP, timestamp. Dữ liệu Weblog cung cấp lượng thông tin giàu có về những trang Web động. Thực hiện phân 7
tích các hồ sơ truy cập này ta có thể rút ra những thống kê về xu hướng truy cập Web, cấu trúc Web và nhiều thông tin hữu ích khác. 1.2. Tổ ng quan về máy tìm kiế m 1.2.1. Nhu cầu Như đã đề cập ở phần trên, Internet là một kho thông tin khổng lồ và phức tạp. 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. 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. 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. Đối với mỗi người dùng chỉ một phần rất nhỏ thông tin là có ích, chẳng hạn có người chỉ quan tâm đến trang Thể thao, Văn hóa mà không mấy khi quan tâm đến Kinh tế. 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. Định nghĩa [14]:Máy tìm kiếm (search engine) là một hệ thống được xây dựng nhằm tiếp nhận các yêu cầu tìm kiếm của người dùng (thường là một tập các từ khóa), sau đó phân tích yêu cầu này và tìm kiếm thông tin trong cơ sở dữ liệu được tải xuống từ Web và đưa ra kết quả là các trang web có liên quan cho người dùng. Cụ thể, người dùng gửi một truy vấn, dạng đơn giản nhất là một danh sách các từ khóa, và máy tìm kiếm sẽ làm việc để trả lại một danh sách các trang Web có liên quan hoặc có chứa các từ khóa đó. Phức tạp hơn, thì truy vấn là cả một văn bản hoặc một đoạn văn bản hoặc nội dung tóm tắt của văn bản. Một số máy tìm kiếm điển hình hiện nay: Yahoo, Google, Alvista, ASPSeek... 1.2.2. Cấu trúc cơ bản và hoạt động của một máy tìm kiếm Một máy tìm kiếm có thể được xem như là một ví dụ của hệ thống truy xuất thông tin Information Retrival (IR)[14]. Một hệ thống truy xuất thông tin IR thường tập trung vào việc cải thiện hiệu quả thông tin được lấy ra bằng cách sử dụng việc đánh chỉ số dựa trên các từ khóa (term-base indexing)[11] và kỹ thuật tổ chức lại các câu truy vấn (query refomulation technique)[12]. Quá trình xử lý các văn bản dựa trên từ khóa ban đầu trích ra các từ khóa trong văn bản sử dụng một từ điển được xây dựng 8
trước, một tập các từ dừng, và các qui tắc (stemming rule)[14] chuyển các hình thái của từ về dạng từ gốc. Sau khi các từ khóa đã được lấy ra, các hệ thống thường sử dụng phương pháp TF-IDF (hoặc biến thể của nó) để xác định mức độ quan trọng của các từ khóa. Do đó, một văn bản có thể được biểu diễn bởi một tập các từ khóa và độ quan trọng của chúng. Mức độ tương tự đo được giữa một câu truy vấn và một văn bản chính bằng tích vô hướng giữa hai vector các từ khóa tương ứng. Để thể hiện mức độ hợp lệ của các văn bản và câu truy vấn, các văn bản được lấy ra được biểu diễn dưới dạng một danh sách được xếp hạng dựa trên độ đo mức độ tương tự giữa chúng và câu truy vấn. Hình 3 miêu tả cấu trúc cơ bản của một máy tìm kiếm. Mặc dù trong thực tế, mỗi máy tìm kiếm có cách thực thi riêng, nhưng về cơ bản vẫn dựa trên cơ chế hoạt động như được mô tả. Kho trang web Bé t×m duyÖt Hình 3: Mô hình cấu trúc của một máy tìm kiếm - Module dò tìm (crawler): là các chương trình có chức năng cung cấp dữ liệu cho các máy tìm kiếm hoạt động. Module này thực hiện công việc duyệt Web, nó đi theo các liên kết trên các trên Web để thu thập nội dung các trang Web. Các chương trình dò tìm được cung cấp các địa chỉ URL xuất phát, đọc các trang web tương ứng, phân tích và tìm ra các URL có trong các trang web đó. Sau đó bộ tìm duyệt cung cấp các địa chỉ URL kết quả cho bộ điều khiển dò tìm (crawl control). Bộ điều khiển này sẽ quyết định xem URL nào sẽ được duyệt tiếp theo và gửi lại kết quả cho bộ dò tìm. 9
Các bộ dò tìm sau khi tải các trang web sẽ lưu kết quả vào kho trang web (page repository). Quá trình này lặp lại cho tới khi đạt tới điều kiện kết thúc. - Module đánh chỉ mục (indexing): module này có nhiệm vụ duyệt nội dung các trang web đã được tải về, đánh chỉ mục cho các trang này bằng cách ghi lại địa chỉ URL của các trang web có chứa các từ trong cơ sở dữ liệu. Kết quả sinh ra một bảng chỉ mục rất lớn. Nhờ có bảng chỉ mục này, máy tìm kiếm cung cấp tất cả các địa chỉ URL của các trang web theo các truy vấn bằng từ khóa của người dùng. Thông thường bộ tạo chỉ mục tạo ra chỉ mục nội dung và chỉ mục cấu trúc (structure index). Chỉ mục nội dung chứa thông tin về các từ xuất hiện trong các trang web. Chỉ mục cấu trúc thể hiện mối liên kết giữa các trang web, tận dụng được đặc tính quan trọng của dữ liệu web là các liên kết. Nó là một dạng đồ thị gồm các nút và các cung, mỗi nút trong đồ thị tương ứng với một trang web, mỗi cung nối từ nút A tới nút B tương ứng là siêu liên kết từ trang web A đến trang web B. - Module phân tích tập (Collection Analysis Module) hoạt động dựa vào thuộc tính module truy vấn. Ví dụ nếu bộ truy vấn chỉ đòi hỏi việc tìm kiếm hạn chế trong một số website đặc biệt, hoặc giới hạn trong một tên miền thì công việc sẽ nhanh và hiệu quả hơn. Module này sử dụng thông tin từ hai loại chỉ mục cơ bản (chỉ mục nội dung và chỉ mục cấu trúc) do module đánh chỉ số cung cấp cùng với thông tin các từ khóa trong trang web và các thông tin tính hạng để tạo ra các chỉ mục tiện ích. - Module truy vấn (query engine): module này chịu trách nhiệm nhận các yêu cầu tìm kiếm của người sử dụng. Module này thường xuyên truy vấn cơ sở dữ liệu đặc biệt là các bảng chỉ mục để trả về danh sách các tài liệu thỏa mãn một yêu cầu của người dùng. Do số lượng các trang web là rất lớn, và thông thường người dùng chỉ đưa vào một vài từ khóa trong câu truy vấn nên tập kết quả thường rất lớn. Vì vậy bộ xếp hạng (ranking) có nhiệm vụ sắp xếp các tài liệu này theo mức độ hợp lệ với yêu cầu tìm kiếm và hiển thị kết quả cho người sử dụng. Khi muốn tìm kiếm các trang web về một vấn đề nào đó, người sử dụng đưa vào một số từ khóa liên quan để tìm kiếm. Module truy vấn dựa theo các từ khóa này để tìm kiếm trong bảng chỉ mục nội dung địa chỉ các url có chứa từ khóa này. Sau đó, module truy vấn sẽ chuyển các trang web cho module xếp hạng để sắp xếp các kết quả theo mức độ giảm dần của tính hợp lệ giữa trang web và câu truy vấn rồi hiển thị kết quả cho người sử dụng. 10
Chương 2. Một số thuật toán tính hạng trang điển hình 2 .1. Bài toán x ế p hạ ng trang Web trong máy tìm ki ế m Trong chương này, phần đầu chúng tôi sẽ giới thiệu tổng quan về bài toán xếp hạng trang Web trong các máy tìm kiếm, phần sau, chúng tôi sẽ tập trung phân tích nội dung các thuật toán PageRank, Modified Adaptive PageRank và Topic-sensitive PageRank ứng dụng trong bài toán tính hạng cho các trang Web. 2.1.1. Nhu cầu Ngày nay, người sử dụng có thể tìm kiếm thông tin đa dạng về mọi mặt của xã hội loài người trên Internet. Tuy nhiên, do lượng thông tin trên Internet là khổng lồ, đang từng ngày từng giờ tăng trưởng với tốc độ cao, cho nên việc giải bài toán tìm và cung cấp thông tin được người dùng thực sự quan tâm trong thời gian cho phép đã trở thành công việc hết sức cấp thiết. Công nghệ xây dựng công cụ tìm tin trên Internet (điển hình là máy tìm kiếm - search engine) cần không ngừng được cải tiến nhằm bảo đảm thoả mãn yêu cầu người dùng cả theo khía cạnh thời gian tìm kiếm nhanh lẫn tính sự phù hợp cao giữa các trang thông tin kết quả tìm được với yêu cầu tìm kiếm của người dùng. Khi người dùng nhập vào một nhóm từ khóa tìm kiếm, máy tìm kiếm sẽ thực hiện nhiệm vụ tìm kiếm và trả lại một số trang Web theo yêu cầu người dùng. Nhưng số các trang Web liên quan đến từ khóa tìm kiếm có thể lên tời hàng vạn trang, trong khi người dùng chỉ quan tâm đến một số ít trang trong đó, vậy việc tìm ra các trang đáp ứng nhiều nhất yêu cầu người dùng để đưa lên đầu là cần thiết. Đó chính là công việc tính hạng của máy tìm kiếm - sắp xếp các trang kết quả theo thứ tự giảm dần của độ quan trọng. Cần thiết phải xác định phép đo về "độ phù hợp" của một trang Web tìm được với yêu cầu người dùng [1,10]. Liên quan tới việc xác định phép đo như vậy, người ta quan tâm tới hai hướng giải quyết.. Hướng thứ nhất sử dụng độ quan trọng (được xác định qua một đại lượng được gọi là hạng trang - page rank) của trang Web làm độ phù hợp với yêu cầu người dùng. Hầu hết các nghiên cứu đều thừa nhận một giả thiết là nếu một trang Web mà có nhiều trang Web khác hướng (link) tới thì trang Web đó là trang Web quan trọng. Trong trường hợp này, hạng trang được tính toán chỉ dựa trên mối liên kết giữa các trang Web với nhau. Hầu hết các máy tìm kiếm sử dụng hạng trang làm độ phù hợp của kết quả tìm kiếm với các thuật toán điển hình là PageRank, 11
Modified Adaptive PageRank [10]. Hướng thứ hai coi độ phù hợp của trang Web với câu hỏi của người dùng không chỉ dựa trên giá trị hạng trang Web như trên mà còn phải tính đến mối liên quan giữa nội dung trang Web đó với nội dung câu hỏi theo yêu cầu của người dùng mà thuật toán điển hình là Topic-sensitive PageRank [15,16]. Một số nghiên cứu khai thác khía cạnh nội dung của trang Web đối với độ phù hợp của trang Web tìm kiếm với câu hỏi người dùng cũng được đề cập trong một số công trình [4,7]. 2.1.2. Độ quan trọng của trang web Một số phương pháp được sử dụng để đo độ quan trọng của các trang web. a. Các từ khóa trong văn bản: Một trang web được coi là hợp lệ nếu nó có chứa một số hoặc tất cả các từ khóa trong câu truy vấn. Ngoài ra, tần số xuất hiện của từ khóa trong trang cũng được xem xét. b. Mức độ tương tự với câu truy vấn: một người dùng có thể chỉ định một thông tin cần tìm bởi một câu truy vấn ngắn hay bằng các cụm từ dài hơn. Mức độ tương tự giữa các mô tả ngắn hay dài của người dùng với nội dung mỗi trang web được tải về có thể sử dụng để xác định tính hợp lệ của trang web đó. c. Mức độ tương tự với trang hạt nhân: Các trang tương ứng với các URL hạt nhân được sử dụng để đo mức độ hợp lệ của mỗi trang được tải. Các trang hạt nhân được kết hợp với nhau thành một văn bản lớn duy nhất và mức độ gần nhau của văn bản này với các trang web đang được duyệt được sử dụng làm điểm số của trang đó. d. Điểm số phân lớp: một bộ phân lớp có thể được huấn luyện để xác định các trang phù hợp với thông tin hoặc nhiệm vụ cần làm. Việc huấn luyện được tiến hành sử dụng các trang hạt nhân (hoặc các trang web hợp lệ được chỉ định trước) như là các ví dụ dương. Các bộ phân lớp được huấn luyện sau đó sẽ gán các điểm số nhị phân (0,1) hoặc liên tiếp cho các trang web được duyệt dựa trên các ví dụ huấn luyện. e. Đánh giá độ quan trọng dựa trên liên kết: Một crawler có thể sử dụng các thuật toán như PageRank hoặc HITS, để cung cấp một sự đánh giá độ quan trọng của mỗi trang web được duyệt. Hoặc đơn giản hơn là chỉ sử dụng số lượng các liên kết tới trang web đó để xác định thông tin này. 12
2.2. Thuậ t toán PageRank c ơ bản Trong [8], Page và Brin đã đưa ra một phương pháp nhằm giúp cho công việc tính toán hạng trang. Phương pháp này dựa trên ý tưởng rằng: nếu có liên kết (links) từ trang A đến trang B thì độ quan trọng của trang A cũng ảnh hưởng đến độ quan trọng của trang B. Điều này ta cũng có thể thấy được một cách trực quan rằng, nếu trang Web bất kì được link đến bởi trang Yahoo! chắc chắn sẽ quan trọng hơn nếu nó được link bởi một trang Web vô danh nào đó. Giả sử ta có một tập hợp các trang Web với các liên kết giữa chúng, khi đó ta coi tập hợp các trang Web như là một đồ thị với các đỉnh là các trang Web và các cạnh là các liên kết giữa chúng. 2.2.1. PageRank thô Trước tiên ta sẽ giới thiệu một định nghĩa về PageRank đơn giản thể hiện độ quan trọng của mỗi trang Web dựa vào các liên kết, trước khi tìm hiểu một phương pháp được áp dụng trong thực tế. Giả sử rằng các trang Web tạo thành một đồ thị liên thông, nghĩa là từ một trang bất kì có thể có đường liên kết tới một trang Web khác trong đồ thị đó. Công việc tính PageRank được tiến hành như sau: Ta đánh số các trang Web có được từ 1, 2,…,m. Gọi N(i) là số liên kết ra ngoài của trang thứ i. Gọi B(i) là số các trang Web có liên kết đến trang i. Khi đó giá trị PageRank r(i) ứng với trang i được tính như sau ∑ r ( j) r (i ) = N ( j) j∈B ( i ) Nếu gọi r = [r(1),r(2), ... , r(n)] là vector PageRank, trong đó các thành phần là các hạng tương ứng của các trang Web, ta viết lại các phương trình này dưới dạng ma trận r = ATr trong đó: A là ma trận kích thước n x n trong đó các phần tử 13
1 aij = nếu có liên kết từ i đến j N j aij = 0 nếu ngược lại Như vậy ta có thể thấy vectơ PageRank r chính là vectơ riêng của ma trận AT Như ta đã thấy ỏ trên, việc tính toán mức độ quan trọng hay hạng trang theo phương pháp PageRank có thể được thực hiện thông qua việc phân tích các liên kết tới trang Web đó. Nếu nó có những liên kết quan trọng trỏ tới thì rất có thể trang đó là trang quan trọng. Tuy nhiên việc tính toán hạng trang lại phụ thuộc vào việc biết được hạng của các trang Web có liên kết tới nó, và như vậy muốn tính hạng trang này ta phải biết được hạng của trang liên kết tới nó, điều này có thể gây ra việc lặp vô hạn rất tốn kém. Khắc phục bằng cách đưa về các vectơ hạng, ta có thể tính toán được các hạng trang thông qua việc tính toán vectơ riêng của ma trận AT. Trong đại số tuyến tính có khá nhiều các phương pháp có thể tính được vectơ riêng của ma trận tuy nhiên có một phương pháp khá tiện và có thể được áp dụng vào việc tính toán vectơ PageRank là phương pháp lặp. Các công việc tính toán sẽ được làm như sau: 1. s vector bất kì AT s 2. r 3. nếu ||r-s||
2.2.2. PageRank trong thực tế Trong thực tế, không phải lúc nào chúng ta cũng gặp trường hợp các trang Web lập thành một đồ thị liên thông. Trên WWW có rất nhiều các trang Web mà chúng không hề có trang nào liên kết tới (Web leak) hay không liên kết tới trang Web nào khác (Web sink). Đối với những trang không có liên kết tới trang khác, như ví dụ ở hình vẽ 3, cụm (4,5) là Websink, người dùng khi đi đến nút (4,5) sẽ bị tắc, khi đó các trang Web sẽ có hạng r1=r2=r3=0, r4=r5=0.5, còn nếu bỏ nút 5 cùng các liên kết thì trang 4 là Web leak, dẫn đến hạng của mọi trang dẫn đến 4 đều = 0. Điều này không phù hợp thực tế, vì bất kì trang Web nào ra đời cũng đều có tính quan trọng của nó, cho dù trang đó của một cá nhân thì nó cũng quan trọng với riêng người đó. Do vậy cần phải sửa đổi công thức PageRank bằng cách thêm vào một hệ số hãm d, công thức PageRank được sửa đổi có dạng như sau: ∑ r ( j) r (i ) = d * N ( j ) + (1 − d ) / n Bi j∈ Việc thêm “ hệ số hãm “ d ( thường được chọn d=0.85 ) có ý nghĩa như sau: bổ sung thêm giá trị PageRank vào cho các trang không có link ra ngoài. Ta cũng nhận thấy khi d=1 thì công thức sẽ quay lại trường hợp PageRank thô. Page và Brin [8] cũng đã chỉ ra rằng các giá trị này có thể hội tụ khá nhanh, trong vòng khoảng 100 vòng lặp chúng ta có thể nhận được kết quả với sai số không lớn lắm. 1 2 3 5 4 Hình 4: Một ví dụ liên kết Web 15
2.3. Mộ t s ố thu ậ t toán khác Phần này chúng tôi xin đề cập tới vấn đề liên quan tới hiệu năng tính toán của thuật toán PageRank bao gồm khả năng tăng tốc độ tính toán và một trong các phương pháp tăng tốc độ tính toán hiện nay là Modified Adaptive PageRank. 2.3.1. Nhu cầu tăng tốc độ tính toán PageRank PageRank là một trong những phương pháp thịnh hành nhất và có hiệu quả nhất trong công việc tìm kiếm các thông tin trên Internet. Như chúng ta đã xem xét ở trên, PageRank sẽ tìm cách đánh giá hạng các trang thông qua các liên kết giữa các trang Web. Việc đánh giá này có thể được thực hiện thông qua việc tính toán vectơ riêng của ma trận kề biểu diễn cho các trang Web. Nhưng với kích cỡ khổng lồ của mình, WWW có thể làm cho công việc tính toán này tốn rất nhiều ngày. Cần phải tăng được tốc độ tính toán này lên vì hai lí do: - Cần có được kết quả sớm để đưa được những thông tin sang các bộ phận khác trong cùng máy tìm kiếm, việc tính toán nhanh vectơ PageRank có thể giúp giảm thiểu thời gian chết của những bộ phận đó. - Hiện nay, các phương pháp nghiên cứu mới đều tập trung vào việc đánh giá dựa trên những tiêu chí do cả người dùng quan tâm, do vậy cần phải tính toán nhiều vectơ PageRank, mỗi vectơ hướng tới một tiêu đề khác nhau. Việc tính toán nhiều vectơ này cũng đòi hỏi mỗi vectơ thành phần được tính toán nhanh chóng. Việc tăng cường tốc độ tính toán có thể vấp phải nhiều khó khăn kích thước của WWW. Vì vậy trong [11], đã giới thiệu một cách để giúp đỡ cho quá trình tính toán được nhanh hơn. Phương pháp này xuất phát từ ý tưởng sau: khi cài đặt chương trình và chạy, độ quan trọng các trang Web có tốc độ hội tụ không giống nhau, có những trang Web độ quan trọng hội tụ nhanh có trang lại có độ hội tụ chậm. Vậy chúng ta có thể tận dụng những trang hội tụ trước và kết quả độ quan trọng của những trang đã hội tụ đó có thể không cần phải tính nữa. Như vậy ta có thể giảm được những tính toán dư thừa và làm tăng được hiệu suất tính toán của hệ thống. Phương pháp này là một cải tiến của phương pháp PageRank. 16
2.3.2. Thuật toán Modified Adaptive PageRank 2.3.2.1. Thuật toán Adaptive PageRank Giả sử việc tính toán vectơ PageRank của chúng ta đã được thực hiện đến vòng lặp thứ k. Ta cần tính toán x(k+1) = Ax(k), (*) Gọi C là tập hợp các trang Web đã hội tụ đến mức e nào đó và N là tập hợp các trang Web chưa hội tụ. Khi đó ta chia ma trận A ra làm hai ma trận con, AN cỡ mxn là ma trận kề đại diện cho những liên kết của m trang chưa hội tụ, còn AC cỡ (n-m)xn là ma trận kề đại diện cho những liên kết của (n-m) trang đã hội tụ. Tương tự, ta cũng chia vectơ x(k) ra thành 2 vectơ (k ) x tương ứng với những N thành phần của x(k) đã hội tụ còn tương ứng với những thành phần của x(k) chưa (k ) x C hội tụ. Vậy ta có thể viết lại ma trận A và x(k) dưới dạng như sau : ⎛ (k ) ⎞ xN ⎛ AN ⎞ = ⎜ (k ) ⎟ =⎜ ⎟ (k ) x A và ⎜ ⎟ ⎜ ⎟ ⎝ AC ⎠ ⎝ xC ⎠ Ta có thể viết lại phương trình (*) như sau: ⎛ ( k +1) ⎞ ⎛ ⎛ (k ) ⎞ ⎜ x N ⎟ = ⎜ AN ⎞ • ⎜ x N ⎟ ⎟ ⎜ ( k +1) ⎟ ⎜ ⎟ ⎜ (k ) ⎟ ⎝ xC ⎠ ⎝ AC ⎠ ⎝ xC ⎠ ( k +1) (k ) x x Do những thành phần của đã hội tụ do vậy ta không cần tính nữa và C C (k ) Ax như vậy việc tính toán sẽ được giảm đi do không phải tính toán nữa mà chỉ C cần thực hiện xN(k+1)= ANx(k) 2.3.2.2. Thuật toán Modified Adaptive PageRank Trong thuật toán Adaptive PageRank tốc độ tính toán được tăng nhanh lên do ta đã giảm đi được những tính toán dư thừa bằng cách không tính những giá trị đã hội tụ. Trong phần này ta sẽ nghiên cứu sâu hơn về cách giảm đi những tính toán dư thừa. Chúng ta có thể viết ma trận A một cách rõ ràng hơn như sau ⎛ ANN ANC ⎞ =⎜ ⎟ A ⎜ ⎟ ⎝ ACN ACC ⎠ 17
Với ANN là ma trận kề đại diện cho những liên kết của các trang chưa hội tụ tới những trang chưa hội tụ, ACN là ma trận kề đại diện cho những liên kết của các trang đã hội tụ tới những trang chưa hội tụ và tương tự cho các phần khác ANC,ACC.Vì xC và ANCxC không thay đổi sau vòng lặp thứ k vì chúng đã hội tu, nên phương trình (*) có thể được viết lại : ( k +1) (k ) (k ) x Ax Ax = + NN CN N N C Ma trận A đã được chia nhỏ ra do vậy công việc tính toán có thể được giảm đi một cách đáng kể. Những kết quả thực nghiệm trong [11] cho thấy tốc độ tính toán có thể được cải thiện khoảng 30%. Theo [11], việc giảm những tính toán của phương pháp PageRank giúp chúng ta có thể tính toán nhanh hơn tuy nhiên đây chưa phải là đích đến cuối cùng cần đạt được. 2.3.3. Topic-sensitive PageRank PageRank là phương pháp tìm kiếm hiện đang được áp dụng trên máy tìm kiếm Google. Tuy nhiên phương pháp này chỉ quan tâm đến các liên kết mà không quan tâm đến nội dung của trang Web có chứa liên kết đó, do vậy có thể dẫn tới những sai lạc trong thông tin tìm kiếm được. Yêu cầu đặt ra là cần phải đưa ra một phương pháp có tốc độ nhanh như phương pháp PageRank và lại có quan tâm đến nội dung của trang Web thông qua "chủ đề" của nó. Hơn nữa, nếu khai thác được mối quan tâm của người dùng đối với các trang Web trong việc tính độ phù hợp của trang Web với câu hỏi người dùng thì việc đó càng có ý nghĩa. Taher H. Haveliwala [15,16] đề xuất phương pháp mới nhằm đáp ứng yêu cầu trên, đó là phương pháp PageRank theo chủ đề (Topic sensitive PageRank). Các tác giả sử dụng khái niệm "phạm vi ngữ cảnh" để biểu thị mối quan tâm của người dùng. Trong [4], thuật toán tìm kiếm trang Web có nội dung tương tự cho một cách tiếp cận khác khi đề cập tới xem xét khía cạnh nội dung trang Web trong bài toán tìm kiếm. Thuật toán gồm hai bước được mô tả sơ bộ như dưới đây. Tại bước đầu tiên, các trang Web trong cơ sở dữ liệu được phân thành các lớp theo các chủ đề c1,c2,...,cn ; gọi Tj là tập hợp những trang Web theo chủ đề cj. Mỗi lớp 18
tương ứng với một vector PageRank của chủ đề mà mỗi thành phần là giá trị PageRank của mỗi trang trong lớp. Vector PageRank của chủ đề được tính như bình thường tuy nhiên thay vì sử r uu r dụng v = [1 / N ] thuật toán sử dụng vector v = vj trong đó → n×1 ⎧ 1|T | ⎪ i ∈Tj v ji = ⎨ j i ∉T j (1) ⎪0 ⎩ → Gọi D j là vector các từ khoá, gồm tất cả các từ khoá trong các tài liệu của các chủ đề; Djt là số lần xuất hiện của từ khoá t trong tất cả các tài liệu của chủ đề cj. Bước thứ hai được thực hiện trong thời gian hỏi-đáp. Giả sử có truy vấn q, gọi q’ là phạm vi ngữ cảnh của q. Mô tả sơ bộ khái niệm phạm vi ngữ cảnh như sau. Với truy vấn thông thường (từ hộp thoại) thì q’ chính là q. Trường hợp truy vấn q được đặt bằng cách tô sáng từ khoá q trong trang Web u thì q’ sẽ chứa các từ khoá trong u bao gồm cả q. Sau đó tính xác suất để q’ thuộc về các chủ đề khác nhau. Sử dụng thuật toán phân lớp Bayes với (i) Tập huấn luyện gồm những trang được liệt kê trong các chủ đề; (ii) Đầu vào là câu truy vấn hoặc phạm vi ngữ cảnh của câu truy vấn; (iii) Đầu ra là xác suất để đầu vào thuộc mỗi chủ đề. q' Dưới đây là một số công thức của một số giá trị xác suất nói trên. Gọi l à từ i khoá thứ i trong ngữ cảnh q’. Với mỗi cj, xác suất để q’ ∈ cj là: P(c ) . P(q' c ) (2) P(c ) .∏ P(q' c ) j P(c q') j = ≈ j P(q') j j i i → Trong đó P ( qi' | c j ) được tính từ vector các từ khoá D j được xác định tại bước 1. Giá trị P(cj) được xác định hoặc là các giá trị bằng nhau cho mọi chủ đề (các chủ đề đồng khả năng) hoặc tính toán thống kê qua tham chiếu tới các trang Web thuộc mỗi chủ đề của tập hợp người dùng. → Theo [15,16], với ký hiệu rankjd là hạng của văn bản d cho bởi vector PR(d, v j ) - vector PageRank của chủ đề cj thì độ quan trọng sqd dựa theo câu truy vấn được tính toán như sau: s = ∑P(c q') .rank (3) qd jd j j 19