Luận văn Bộ công cụ tìm kiếm thông tin trên mạng

của các trang mong muốn khi Crawler dừng là K2/ T. + Thu hồi và dừng với ngưỡng: Giả sử rằng Crawler thăm K trang. Bây giờ chúng ta đưa ra một giá trị mục tiêu G về độ quan trọng và bát kỳ trang nào có mức độ quan trọng cao hơn G được xem là nống. Giả sử rằng tổng số các trang nóng là H. Hiệu suất Crawler, PST(C), là phần trăm của các trang nóng đã được thăm sau khi Crawler dừng. Nếu K<H thì một Crawler lý tưởng sẽ có hiệu suất 100%. Một Crawler ngẫu nhiên hoàn hảo khi thăm lại các trang sẽ mong đợi thăm(H/T).K trang nóng khi nó dừng. Vì thế hiệu suất của nó là(K.100)/T. Chỉ khi Crawler ngẫu nhiên thăm tất cả T trang thì hiệu suất mong đợi là 100%. * Ma trận thứ tự Một Crawler lưu trữ một hàng các giá trị URL mà nó đã tìm thấy trong suốt quá trình crawl, mà phải lừa chọn từ hàng này một giá trị URL được thăm tiếp theo. Ma trận thứ tự sẽ được Crawler sử dụng cho sự lựa chọn này, ví dụ nó chọn URL u sao cho giá trị thứ tự của nó là cao nhất trong số tất cả các URL trong hàng. Ma trận thứ tự có thể chỉ sử dụng các thông tin được tìm thấy bởi Crawler. Ma trận thứ tự nó có cùng nghĩa với ma trận đánh giá mức độ quan trọng. Chẳng hạn chúng ta đang tìm kiếm các trang có IB(P) cao, thì cũng tương tự như ta chọn chúng theo thứ tự của giá trị IB’(P) (ma trận PageRank). Ma trận vị trí có thể được sử dụng một cách trực tiếp để lựa chọn thứ tự, do URL của trang P cho ta ngay giá trị IL(P). Tuy nhiên, với các ma trận tương quan, nó khó hơn nhiều để đưa ra một ma trận thứ tự, khi chúng ta vẫn chưa tìm thấy P. 2.2 Lưu trữ Từ hình 3 cho chúng ta thấy kho lưu trữ các trang là một hệ thống lưu trữ mở rộng để quản lý tập hợp các trang Web. Kho lưu trữ sẽ thực hiện hai chức năng cơ bản. Thứ nhất nó cung cấp một giao diện để Crawler lưu trữ các trang. Thứ hai, nó phải cung cấp cách truy cập hiệu quả để các mô đun chỉ mục và mô đun phân tích tập hợp sử dụng cho việc tìm kiếm các trang. Một kho lưu trữ và quản lý một tập rất lớn các đối tượng dữ liệu, ở đây chính là các trang Web. Tuy nhiên một kho lưu trữ Web không phải cung cấp nhiều chức năng như các hệ thống File và các hệ thông cơ sở dữ liệu, nhưng thay vào đó như khả năng mở rộng vì nó phải phân tán kho lưu trữ trên một nhóm các máy tính và các đĩa để đối phó với kích thước của Web. Bên cạnh đó là việc tồn tại mô hình truy nhập kép, khi đó kho lưu trữ phải được hỗ trợ hai mô hình khác nhau có hiệu quả truy cập ngang nhau. Truy cập ngẫu nhiên sử dụng để thu hồi một trang Web cụ thể cho bởi một giá trị nhận dạng duy nhất của trang. Tuy cập theo luồng được sử dụng để thu hồi toàn bộ tập hợp, hoặc là một vài tập con quan trọng như một luồng các trang. Truy cập ngẫu nhiên được sử dụng bởi công cụ truy vấn để đưa ra các bản sao từ bộ đệm tới người sử dụng cuối. Truy cập theo luồng được sử dụng bởi các mô đun lập chỉ mục và mô đun phân tích tập hợp để xử lí và phân tích một số lượng lớn các trang. Do Web trao đổi rất nhanh nên kho lưu trữ cần được điều khiển với khả năng biến đổi cao. Khi nhận các phiên bản từ các trang Web từ Crawler, phần không gian bị chiếm gữi bởi phiên bản được phục hồi thông qua việc nén và tổ chức lại. Hơn nữa, phải tránh sự xung đột giữa việc xử lý cập nhật và các ứng dụng truy cập trang. Ngoài ra các trang quá hạn thì kho lưu trữ không được thông báo, vì thế kho lưu trữ phải có một kĩ sảo để dò xét các và rời các trang đã quá hạn. Để thiết kế kho lưu trữ Web phân tán sẽ có ba vấn đề chính tác động tới đặc thù và khả năng thực hiện của kho lưu trữ. 2.2.1.Sự phân tán trang theo các nút: Các trang có thể được phân bố tới các nút sử dụng một số chiến lược khác nhau. Ví dụ, với chiến lược phân tán đồng bộ, tất cả các nút được đối xử tương tự nhau. Một trang đã cho có thể được phân bố tới bất kỳ nút nào trong hệ thống không phụ thuộc vào giá trị nhận dạng của nó. Các nút sẽ lưu trữ các phần của tập hợp tương ứng với khả năng lưu trữ của nó. Ngược lại, với chiến lược phân bố băm, sự phân bố các trang tới các nút sẽ phụ thuộc vào giá trị nhận dạng của trang. Trong trường hợp này, giá trị nhận dạng trang sẽ được băm cho ta một giá trị nhận dạng nút và trang đó sẽ được phân bố tới nút tương ứng. 2.2.2.Các phương pháp tổ chức trang vật lý : Trong một nút đơn có 3 hoạt động có thể xảy ra là, thêm/chèn một trang, truy cập luồng trang tốc độ cao, truy cập trang ngẫu nhiên. Tổ chức trang vật lí tại mỗi nút là xác minh xem một nút hỗ trợ các hoạt động này tốt như thế nào. Có một vài sự lựa chọn cho việc tổ chức trang. Cho ví dụ tổ chức dựa trên việc băm sẽ coi mỗi đĩa như là một tập các bucket băm, mà mỗi phần tử đủ nhỏ để lấy đầy trong bộ nhớ. Các trang được phân bố trên các butkets băm phụ thuộc vào giá trị nhận dạng của nó. Do các trang thường xuyên được thêm vào nên tổ chức theo cấu trúc bản ghi sẽ thuận lợi. Trong trường hợp này toàn bộ đĩa được coi như là các bản ghi liên tiếp nhau và các trang thêm vào sẽ được nối vào cuối. Truy cập ngẫu nhiên được hỗ trợ bởi việc sử dụng bảng chỉ mục B- Tree để giá trị các ánh xạ nhận dạng các trang tới các vị trí vật lý trên đĩa, chúng ta cũng có thể đưa ra một cách tổ chức là sự kết hợp của băm và bản ghi, trong đó việc lưu trữ được chia thành các phần liên tiếp, các trang được băm thành các phần và mỗi phần được tổ chức giống như một File có cấu trúc bản ghi. Do đó mà mô hình bản ghi làm việc rất tốt ngoại trừ trường hợp đòi hỏi nhiều truy cập ngẫu nhiên. 2.2.3. Các chiến thuật cập nhật Việc thiết kế chiến thuật cập nhật cho một kho lưu trữ trang sẽ phụ thuộc vào các đặc thù của Crawler và Crawler có thể được xây dựng theo ít nhất là hai cách: a. Chế độ khối hoặc chế độ đồng đều : Crawler với chế độ khối được thực hiện một cách chu kỳ và cho phép thu hồi với lượng thời gian nào đó sau đó sẽ dừng lại. Khi đó các kho lưu trữ sẽ nhận sự cập nhật cho một số lượng nhất định cho một số ngày trong tháng. Ngược lại, một Crawler đồng đều (Steady) luôn luôn chạy và không dừng, liên tục cập nhật và cung cấp các trang mới tới kho lưu trữ. b. Thu hồi cục bộ hay toàn phần: Một Crawler chế độ khối có thể được định cấu hình để thực hiện một chiến lược thu hồi toàn phần tại mọi thời gian nó chạy hoặc chỉ thu hồi một số lượng cố định các trang hoặc các Site. Trong trường hợp đầu các trang từ đợt thu hồi mới thay thế hoàn toàn tập các trang cũ đang tồn tại trong kho. Trong trường hợp thứ hai, tập hợp mới được tạo ra bởi việc áp dụng sự cập nhật của Crawler cục bộ tập hợp đang tồn tại. Phụ thuộc vào kho lưu trữ này chúng ta có thể chọn lựa kiểu thực hiện hoặc là cập nhật tại chỗ hoặc là cập nhật có màn che (shadowing). Với kiểu cập nhật tại chỗ, thì các trang nhận được từ Crawler có thể được tích hợp một cách trực tiếp vào tập dữ liệu đang tồn tại, cũng có thể là thay đổi phiên bản cũ. với kiểu Shadowing thì các trang nhận được từ quá trình Crawler sẽ được lưu trữ một cách riêng biệt với tập đang tồn tại và được cập nhật cũng được thực hiện một bước riêng rẽ. như được chỉ ra trong hình 10, các nút đọc chứa đựng tập đang tồn tại và sử dụng để phục vụ tất cả các yêu cầu truy nhập theo luồng hay ngẫu nhiên. Các nút cập nhật lưu trữ các trang nhận được trong suốt quá trình crawl sau cùng. Đặc thù hấp dẫn của shadowing đó là sự tách biệt hoàn toàn giữa cập nhật và truy cập đọc. Một nút lưu trữ đơn không bao giờ phải đồng thời điều khiển việc thêm và tìm kiếm một trang. Điều này tránh được sự xung đột, nâng cao hiệu suất và thực hiện đơn giản hơn. Tuy nhiên, sẽ có một thời gian trễ từ khi có Crawler tìm thấy một trang và trang đó có hiệu lực cho việc truy cập, shadowing có thể làm giảm độ tươi của tập hợp. Kho lưu trữ Standford Webbase: Để minh họa tất cả các phần tử trong kho được kết hợp với nhau như thế nào, chúng ta sẽ được làm. Kho lưu trữ WebBase là một hệ thống lưu trữ file phân tán kết hợp với Stanford WebCawler. Kho lưu trữ hoạt động thông qua một nhóm các nút lưu trữ nối kết bởi một mạng truyền thông tốc độ cao. Kho lưu trữ sử dụng một máy quản lý nút để giám sát các nút lưu trữ cá nhân và tập hợp các thông tin trạng thái (ví dụ hư không gian trống, việc tải, việc phân đoạn, một số yêu cầu truy cập còn tồn tại). Quản lý nút sẽ sử dụng các thông tin này để điều khiển các hoạt động của kho lưu trữ và lập biểu việc cập nhật cùng với các yêu cầu truy cập trên mỗi nút. Nót ®äc Crawler nút quản lý LAN Indexer Analyst Nót cËp nhËt H×nh 10: KiÕn tróc kho l­u tr÷ Mỗi trang trong kho được phân bố một giá trị định danh duy nhất, nhận được từ một việc tính toán một Signature của URL kết hợp với trang đó. Tuy nhiên một giá trị URL có thể được diễn tả dưới nhiều dạng xâu văn bản khác nhau. Ví dụ http:// WWW.STANFORD.EDU:80/ và http:// www.stanford.edu:80/ diễn tả cùng một trang Web nhưng sẽ cho ta các giá trị Signature khác nhau. Để tránh vấn đề này, URL phải được chuẩn hóa và các giá trị định danh được tính toán như một signature của URL chuẩn này.Do Stanford Web Crawler là một crawler chế độ khối nên kho lưu trữ WebBase sử dụng kỹ thuật Shadowing. Nó có thể sử dụng các phương pháp khác để tổ chức trang và các chiến lược phân tán khác trên các nút đọc và các nút cập nhật. vì thế, các nút cập nhật có thể nâng cao hiệu suất thêm các trang còn các nút đọc nâng cao khả năng đọc. Như vậy: Kho lưu trữ trang là một nội dung quan trọng trong kiến trúc tìm kiếm Web. Nó phải hỗ trợ một cách hiệu quả các phép truy cập khác nhau đối với các mẫu của bộ công cụ truy vấn (truy cập ngẫu nhiên) và các mô đun lập chỉ mục (truy cập theo luồng). Nó cũng phải sử dụng một chiến thuật cập nhật phù hợp với các đặc thù của Crawler. Lập chỉ mục Các mô đun lập chỉ mục và mô đun phân tích tập hợp đã xây dựng lên đủ loại bảng lập chỉ mục trên tập hợp các trang. mô đun lập chỉ mục xây dựng hai bảng chỉ mục cơ bản: Đó là bảng chỉ mục văn bản(cho nội dung) và bảng chỉ mục cấu trúc (cho liên kết). Môđun phân tích tập hợp sử dụng hai bản chỉ mục cơ bản này cùng với các trang trong kho lưu trữ để xây dựng lên các bảng chỉ mục tiện ích khác. Sau đây, em trình bày một cách ngắn gọn từng loại bảng chỉ mục, chủ yếu là tập chung vào cấu trúc và phương pháp sử dụng chúng. * Lập chỉ mục văn bản: Mặc dù các kỹ thuật dựa trên các liên kết đã nâng cao chất lượng và độ chính xác của kết quả tìm kiếm, nhưng tìm kiếm dựa trên văn bản (chẳng hạn tìm kiếm các trang chứa đựng từ khóa) vẫn tiếp tục phương pháp chính để xác định các trang liên quan tới vấn đề đang được truy vấn. Bảng chỉ mục văn bản hỗ trợ cho việc tìm kiếm có thể được thực hiện sử dụng bất kỳ phương pháp truy cập truyền thống nào để tìm kiếm trên toàn tập tài liệu như các file Signature, các file Inverted hoặc các bảng chỉ mục Inverted. Bảng Inverted là cấu trúc truyền thống được lựa chọn cho Web. *Bảng chỉ mục tiện ích: số lượng kiểu bảng chỉ mục tiện ích được xây dựng bởi mô đun phân tích tập hợp phụ thuộc vào nét đặc trưng của công cụ truy vấn và các loại thông tin cần hỗ trợ cho quá trình sắp xếp. Cho ví dụ, một công cụ truy vấn cho phép tìm kiếm bị giới hạn trong một site hoặc là một miền cụ thể (chẳng hạn WWW.stanford.edu) sẽ có lợi nhuận từ một bảng chỉ mục site ánh xạ mỗi tên miền tới một danh sách các trang của miền đó. Tương tự, chúng ta có thể sử dụng các thông tin hàng xóm từ bảng chỉ mục liên kết để hỗ trợ cho thuật toán lặp trong việc tính toán và lưu trữ PageRank kết hợp với mỗi trang một cách dễ dàng. * Bảng chỉ mục liên kết: Muốn xây dựng một bảng chỉ mục liên kết thì các phần được thu hồi trên Web được mô hình hóa như một đồ thị với các cạnh và các nút. Mỗi nút trong đồ thị tương ứng với một trang Web, mỗi cạnh có hướng từ A đến B diễn tả liên kết siêu văn bản trong trang A trỏ tới trang B. Một bảng chỉ mục cho cấu trúc liên kết phải là một diễn tả mở rộng và hiệu quả của đồ thị này. Các thông tin cấu trúc phổ biến nhất được sử dụng trong tìm kiếm đó là các thông tin về hàng xóm. Chẳng hạn cho trang P, hãy tìm kiếm một tập các trang được P trỏ tới (liên kết đi ra) hoặc một tập các trang trỏ tới P(liên kết đi vào). Cấu trúc danh sách liền kề của đồ thị Web đầu tiên và của đồ thị Web đã được đảo có thể cung cấp phép truy cập tới các thông tin hàng xóm một cách có hiệu quả. Các thuộc tính cấu trúc khác của đồ thị Web có thể được đưa ra một cách dễ dàng từ những thông tin cơ bản lưu trữ trong danh sách liền kề. Cho ví dụ, khái niệm về các trang anh em thường được sử dụng làm cơ sở cho việc tìm kiếm các trang liên quan với trang đã cho. Thông tin anh em có thể được đưa ra một cách dễ dàng từ một cặp danh sách liền kề. Còn các đồ thị với hàng trăm hoặc hàng nghìn nút có thể được diễn tả một cách hiệu quả dưới bất kỳ dữ liệu được biết nào. Tuy nhiên làm công việc đó đối với đồ thị có vài triệu nút là một thách thức về công nghệ. Cấu trúc của bảng chỉ mục ngược Bảng chỉ mục ngược (Inverted) cho một tập các trang Web bao gồm một tập các danh sách Inverted được sắp xếp theo vị trí từ trong văn bản. Trong trường hợp đơn giản nhất, vị trí sẽ bao gồm giá trị nhận dạng trang và vị trí của từ trong trang. Tuy nhiên thuật toán tìm kiếm thường phải sử dụng những thông tin được thêm vào về từ trong trang Web. Chẳng hạn, từ xuất hiện dưới dạng chữ in đậm (gắn thẻ ), hoặc nằm trong phần đầu (gắn cờ hoặc ), hoặc các từ có thể được đánh trọng số hỗ trợ cho việc sắp xếp này. Để thực hiện được điều đó phải có một trường trọng tải được thêm vào tới các phần tử vị trí.Trường trọng tải mã hóa bất kỳ thông tin cần thiết nào cho mỗi từ. Với một từ chỉ mục w và vị trí tương ứng l lúc này ta có một cặp (w,l) và được gọi là posting cho từ w.Cộng với danh sách inverted, hầu hết các bảng chỉ mục cho văn bản đều duy trì một cuốn từ điển. Cuốn từ điển này liệt kê tất cả các từ xảy ra trong bảng chỉ mục cùng với sự thống kê của từ đó. 2.3.2 Một số thách thức: Khi xây dựng một bảng chỉ mục ngược bao gồm việc xử lý từng trang để trích ra các posting, sắp xếp các posting đầu tiên theo từ rồi sau đó theo vị trí và cuối cùng đưa ra các posting đã được sắp xếp như một tập hợp của các danh sách inverted trên đĩa. Đối với các tập hợp tĩnh và ít quan hệ như trong môi trường tìm kiếm thông tin truyền thống, thì thời gian xây dựng bảng chỉ mục là không quan trọng. Tuy nhiên, đối với tập dữ liệu Web rộng lớn, thì mô hình xây dựng bảng chỉ mục trở thành không thể quản lý và đòi hỏi nguồn tài nguyên quá lớn, thông thường mất nhiều ngày để hoàn thành. Thêm vào nữa, nội dung của trang Web thay đổi liên tục do đó việc thu hồi một cách tuần hoàn và xây dựng lại bảo chỉ mục là cần thiết để duy trì độ tươi. Việc xây dựng lại bảng chỉ mục là cần thiết bởi vì những kỹ thuật cập nhật tiên tiến nhất cũng trở nên nghèo nàn khi ta áp dụng nó với tập dữ liệu cực lớn và thay đổi liên tục như Web. Cuối cùng khuôn dạng lưu trữ của bảng chỉ mục Inverted phải được thiết kế một cách cẩn thận. Một bảng chỉ mục nén cải tiến khả năng truy vấn bằng việc cho phép từng phần của bảng chỉ mục có thể trở thành bộ đệm trong bộ nhớ. Do đó, phải có sự thỏa hiệp giữa hiệu suất này và tổng chi phí giải nén tại thời gian truy vấn. Để thu được sự cân bằng đã trử thành một thách thức lớn. Chia bảng chỉ mục Để xây dựng bảng chỉ mục ngược cho Web đòi hỏi một kiến trúc bảng chỉ mục phân tán và rộng lớn. Có hai chiến thuật cơ bản chỉ mục ngược dựa trên tập hợp các nút. Tổ chức dạng tập tin đảo (Inverted file ) cục bộ (IFL), mỗi nút tương ứng với một tập con các trang phân biệt trong tập hợp. Công việc tìm kiếm sẽ được quảng bá tới tất cả các nút, mỗi nút sẽ trả lại danh sách chứa đựng giá trị nhận dạng của các trang chứa đựng từ đang được tìm kiếm. Tổ chức dạng Inverted File toàn cục (IFG) sẽ chia theo các từ được lập chỉ mục, vì thế mỗi dịch vụ truy vấn sẽ chỉ lưu trữ các danh sách Inverted cho một tập các từ trong tập hợp. Ví dụ, trong một hệ thống có hai dịch vụ truy vấn A và B có thể lưu trữ các danh sách Inverted cho những từ bắt đầu với ký tự nằm trong phạm vi [a- q], còn B có thể lưu trữ các danh sách Inverted cho những từ còn lại. Vì thế, một yêu cầu truy vấn từ “process” sẽ chỉ đòi hỏi hệ phục vụ A. Trang Web Bé ph©n phèi Bé lËp chØ môc C¸c dÞch vô truy vÊn Bé Thèng kª B¶ng chØ môc Tr¹ng th¸i 2 Tr¹ng th¸i 1 D·y s¾p xÕp trung gian H×nh 11: M« h×nh lËp chØ môc Web Đặc thù quan trọng của chiến thuật IFL, như là khả năng phục hồi lỗi và giảm việc tải trên mạng, làm cho nó trở thành lý tưởng trong môi trường tìm kiếm Web. Các đánh giá về hiệu suất trong cũng chỉ ra rằng tổ chức IFL đã sử dụng nguồn tài nguyên một cách hiệu quả và cung cấp một truy vấn tốt trong hầu hết các trường hợp. Sắp xếp và phân tích liên kết Như được chỉ trong hình 3, công cụ truy vấn tập hợp các từ tìm kiếm từ người sử dụng và thu hồi các trang có nội dung liên quan. Có hai lý do chính giải thích tại sao các kỹ thuật thu hồi thông tin truyền thông không đủ hiệu quả cho việc sắp xếp các kết quả truy vấn. Đầu tiên là do Web quá lớn, với sự giao động về số lượng, chất lượng và kiểu loại thông tin được diễn tả trong mối trang Web. Vì vậy mà có rất nhiều trang chứa đựng các từ tìm kiếm nhưng chúng lại ít liên quan tâm thậm chí là không liên quan tới nội dung đang được tìm kiếm. Thứ hai, có rất nhiều trang Web không đủ để tự diễn tả nó muốn nói về vấn đề gì, do vậy nếu ta áp dụng kỹ thuật IR để kiểm tra nội dung của một trang thì sẽ không cho một câu trả lời tốt một ví dụ thông thường để minh họa cho vấn đề này là khi ta đánh từ tìm kiếm “search engines” các trang chủ của hầu hết bộ công cụ tìm kiếm chính đều không chứa đựng văn bản “search engines”. Hơn nữa các trang Web thường xuyên thêm vào các từ lừa dối vì thế chúng sẽ được sắp xếp cao hơn bởi bộ công cụ tìm kiếm (spaming). Do đó các kỹ thuật chỉ dựa trên nội dung của một trang Web sẽ đưa ra những quyết định lệch lạc. Cấu trúc của Web sẽ cho thấy các thông tin rất quan trọng, và nó có thể hỗ trợ trong việc lọc và sắp xếp các trang Web. Cụ thể là một liên kết từ trang A tới trang B cho ta biết trang B sinh ra từ trang A. Một vài thuật toán đã được đề xuất để khai thác cấu trúc liên kết này, không chỉ cho việc tìm kiếm từ khóa mà còn cho cả những công việc khác như vậy việc xây dựng kiến trúc Yahoo một cách tự động, hoặc nhận dạng nhóm truyền thống trên Web. Hiệu quả của thuật toán này cao hơn các thuật toán IR bởi chúng sử dụng nhiều thông tin hơn. Để đưa ra những thông tin lựa chọn cho một trang Web, sau đây em xin mô tả hai kỹ thuật dựa trên các cấu trúc liên kết – PageRanK và HITS. 2.4.1 Phương pháp PageRank Page và Brin đưa ra một mô hình sắp xếp tổng cục, được gọi là PageRank, để làm nổi bật khái niệm “quan trọng” của một trang. Chẳng hạn như trang chủ Yahoo có cảm giác là quan trọng hơn trang chủ của nhóm cơ sở dữ liệu Stanford. Sự khác biệt này được phản ánh trong số lượng các trang trỏ tới hai trang này, có nghĩa là có nhiều trang trỏ tới trang chủ Yahoo hơn trang chủ của nhóm cơ sở dữ liệu Stanford. Vì thế sự sắp xếp của trang A có thể định nghĩa như số lượng trang Web trỏ tới A, và có thể được sử dụng để sắp xếp các kết quả của truy vấn. PageRank mở rộng ý tưởng trên bởi việc đưa thêm vào khái niệm một trang được Yahoo trỏ tới sẽ quan trọng hơn một trang không biết nào đó trỏ tới. Do đó ta có định nghĩa của PageRank là đệ quy - độ quan trọng của một trang vừa phụ thuộc vừa ảnh hưởng tới độ quan trọng của trang khác. 1/ Tính PageRank đơn giản Định nghĩa về một PageRank đơn giản, và tham khảo các lĩnh vực tính toán của nó trước khi đưa ra một phép biến đổi thực tế. Định nghĩa các trang Web là 1,2,3,...,m. N(i) là số lượng liên kết đi ra từ trang i và B(i) là số lượng trang trỏ tới trang i. Chúng ta giả sử rằng các trang Web hình thành lên một đồ thị liên kết mạnh (mọi trang có thể đi tới từ bất kỳ một trang nào khác). Giá trị PageRank đơn giản của trang i được định nghĩa là r(i): Việc chia cho N(j) muốn nói rằng các trang trỏ tới trang i được phân bố giá trị sắp xếp của chúng một cách đồng đều tới tất cả các trang chúng trỏ tới. Theo ngôn ngữ đại số tuyến tính, ta có r = ATr, trong đó r là vector m´1 và các phần tử aij của ma trận A được cho bởi ai,j = 1/N(i) nếu trang i trỏ tới trang j và aij = 0 nếu ngược lại. Vì thế vector PageRank r là eigenvector của ma trận AT tương ứng với eigenvector 1. Vì đồ thị là liên kết mạnh nên có thể chỉ ra rằng 1 là eigenvector của AT và eigenvector r là duy nhất.(khi thực hiện chuẩn hóa là vector là không âm). * Mô hình lướt ngẫu nhiên Từ định nghĩa của PageRank đơn giản dẫn tới một sự diễn giải dựa trên các cuộc dạo chơi ngẫu nhiên thì được gọi là mô hình lướt ngẫu nhiên. Chúng ta hình dung ra một người đang lướt các trang Web bằng việc kích ngẫu nhiên vào các liên kết trên các trang được thăm. Việc lướt ngẫu nhiên này cũng tương tự như việc đi bộ trên một đồ thị liên kết cơ bản. Bài toán đi bộ trên đồ thị là một bài toán tổ hợp đã được nghiên cứu. Nó có thể được chỉ ra rằng vector PageRank r là tương đương với phân bố xác suất thống kê của việc đi bộ ngẫu nhiên. Vì thế, PageRanK của một trang tương ứng với tần số mà một người lướt ngẫu nhiên để thăm nó. * Các tính toán của PageRank Như đã trình bày ở mục trên, việc tính toán PageRank tương đương với việc tính toán eigenvector chính của ma trậ AT. một trong những phương pháp đơn giản nhất để tính toán eigenvector chính của ma trận đó là sử dụng các bước lặp lũy thừa. Trong một bước lặp lũy thừa, một vector ban đầu có giá trị tùy ý được nhân nhiều lần với một ma trận đã cho tới khi nó hội tụ về eigenvector chính. Bước lặp lũy thừa cho việc tính toán PageRank được cho như sau: s <- vector ngẫu nhiên bất kỳ r <- AT ´ s Nếu || r – s || < e thì kết thúc . r là vector PageRank 2 4 5 R2 = 0.142 3 R2 = 0.101 R2 = 0.154 1 R2 = 0.313 R2 = 0.290 Hình 12(b) PageRank với d = 0.8 4 . s < - r, goto 2 2 4 5 R2 = 0.286 3 R2 = 0.143 R2 = 0.286 1 R2 = 0.143 R2 = 0.143 Hình 12 (a ) PageRank đơn giản Hình 2.4.1(a) đã minh họa các giá trị PageRanK cho một đồ thị đơn giản. Nó thật dễ dàng để nhận ra rằng sự phân phối sắp xếp này thỏa mãn định nghĩa của PageRank. Chẳng hạn, nút 2 có giá trị sắp xếp là 0.286 và có hai liên kết đi ra. Một nửa giá trị sắp xếp (0.143) đi tới nút 1 và một nửa tới nút 3. Do nút 3 không có thêm một “liên kết tới” nào khác nữa nên giá trị sắp xếp của nó được nhận từ chính nút 2 và bằng 0.143. Nút 1 nhận 0.143 từ 2 và 0.143/2 từ 3 cộng với 0.143/2 từ nút 5 cho ta tổng là 0.286. để ý rằng nút 1 có thứ tự sắp xếp cao hơn bởi vì bất kỳ một người nào thăm nút 1 cũng sẽ phải thăm nút 2. Lưu ý rằng tổng giá trị sắp xếp của tất cả các nút bằng 1. 2/ Tính PageRank thực tế PageRank đơn giản chỉ được tính cho đồ thị liên kết mạnh. trong khi đó, môi trường Web không phải là một liên kết mạnh. Cụ thể là rank sinks và rank leaks. Bất kỳ nhóm các liên kết mạnh nằm trong đồ thị Web mà không có một liên kết nào đi ra từ chúng hình thành nên rank sink. Một trang đơn lẻ không có bất kỳ một liên kết đi ra nào hình thành nên rank leak. Mặc dù rank leak là trường hợp đặc biệt của rank sink nhưng rank leak sẽ gây ra một loại vấn đề khác. Trong trường hợp rank sink các nút không nằm trong sink nhận giá trị sắp xếp 0, nghĩa là chúng ta không thể phân biệt mức độ quan trọng của những nút như vậy. Ví dụ, giả sử trong hình 2.4.1(a) chúng ta rời liên kết 5-> 1, khi đó các nút 4 và 5 hình thành nên một sink. Một người lướt Web ngẫu nhiên khi thăm đồ thị này cuối cùng sẽ bị mắc kẹt trong các nút 4 và 5 vì thế các nút 1,2,3 sẽ có giá trị sắp xếp là 0 và các nút 4,5 có giá trị sắp xếp là 0.5. Còn một trong các trường hợp khác, bất kỳ một sắp xếp nào đi tới rank leak sẽ bị mất mãi mãi. Cho ví dụ, trong hình 2.4.1(a), nếu chúng ta rời nút 5(và tất cả các liên kết kết hợp với nó), nút 4 sẽ trở thành leak. leak này sẽ gây cho tất cả các giá trị cuối cùng đều bằng 0. Có nghĩa là một người lướt Web ngẫu nhiên cuối cùng sẽ đi tới nút 4 và không bao giờ trở lại nữa. Page và Brin đã gợi ý hai cách giải quyết vấn đề này. Thứ nhất là họ rời tất cả các nút leak có bậc ra bằng 0. Thứ hai để giải quyết vấn đề sink, họ đưa ra một hệ số phân rã d ( 0 < d <1)trong công thức PageRank. Ở định nghĩa đã được biến đổi này, chỉ có hệ số d của giá trị sắp xếp của một trang được phân bố giữa các nút nó trỏ tới. Giá trị sắp xếp còn lại được phân bố đồng đều cho tất cả các trang trên Web. Vì thế công thức PageRank có dạng Trong đó m là tổng số lượng các nút trong đồ thị. Chú ý rằng công thức PageRank đơn giản là trường hợp đặc biệt khi d =1. Trong mô hình lướt ngẫu nhiên, sự thay đổi có thể làm cho người lướt Web thỉnh thoảng sẽ gặp những điều tẻ nhạt và có thể nhảy đến một trang ngẫu nhiên trên Web (thay cho việc đi tới một liên kết ngẫu nhiên từ trang Web hiện thời). Hệ số phân rã d chỉ cho biết mức độ thường xuyên gặp điều phiền phức của người lướt Web như thế nào. Hình 12(b) chỉ ra mô hình PageRank đã được biến đổi ( với d = 0.8) cho đồ thị của hình 12(a) khi ta rời liên kết 5-> 1. Nút 4 và 5 có giá trị sắp xếp cao hơn các nút khác cho biết rằng những người lướt Web sẽ tập chung vào các nút 4 và 5. Tuy nhiên các nút khác có giá trị sắp xếp khác 0. 3/ Sử dụng PageRank cho tìm kiếm theo từ khóa Page và Brin diễn tả một bộ công cụ tìm kiếm được phát triển tại Stanford gọi là Google (Cái mà sau đó trở thành