Giải thuật LPageRank - Algorythm LPageRank

Thứ tư , 31/05/2017, 02:48 GMT+7
     

Bài trước chúng ta đã đi qua vấn đề:

                                                               Bài 1: Xây dựng Ontology

 

Giải thuật  LpageRank.

Giải thuật LPageRank được tác giả Qing Cui và Alex Dekhtyar giới thiệu vào năm 2005 với hướng nghiên cứu sử dụng web log để giảm bớt chi phí thu thập liên kết và cải tiến việc đánh giá mức độ truy cập lên trang trong việc tính toán trọng số của trang web. Nhìn một cách tổng quan, thì LPageRank là PageRank được tính toán dựa trên đồ thị xác suất của trang web được xây dựng từ các mẫu truy cập trong nhật ký sử dụng web của người dùng.

-     Tập tin log ghi lại sự truy cập của người dùng trên một web site. Do đó, nếu như ta lấy thông tin toàn bộ tập tin web log được ghi nhận một cách đầy đủ và giả sử rằng tất cả các liên kết (link) trên trang web đều được truy cập ta có thể mô hình hóa lại được chuỗi truy cập của người dùng và từ đó hình thành nên liên kết cấu trúc của toàn bộ trang web. Không chỉ có thế, tập tin web log còn cung cấp thêm thông tin về việc người dùng quan tâm như thế nào đến một liên kết. Đó là một trong những thông tin rất quan trọng cho việc đánh giá khả năng truy cập trang web.

-     Đồ thị xác suất là đồ thị được xây dựng từ tập tất cả các liên kết cấu trúc của tập tất cả các trang web trong web site. Mỗi liên kết từ một trang này đến một trang khác tượng trưng cho một cung trong đồ thị. Tần số liên kết giữa các trang với nhau tương ứng với tần số truy cập giữa chúng của người dùng và cũng được xem là trọng số của cung trong đồ thị. Do đó, đồ thị thể hiện khả năng truy cập từ một trang đến các trang khác thông qua trọng số của cung kết nối. Đồ thị xác suất được xây dựng dựa trên kết quả phân tích thông tin web log.

Giải thuật xây dựng đồ thị xác suất.

Mỗi mẫu truy cập của web log mô tả một cung liên kết từ trang một trang này đến một trang khác trong web site. Xét một phiên truy cập của người dùng, ta sẽ có được một chuỗi truy cập từ một trang lần lượt đến một hay nhiều trang khác. Ta sẽ tiến hành mô hình hóa toàn bộ lịch sử truy cập người dùng thành đồ thị xác suất như sau. Với mỗi cung của đồ thị (B,A) tương ứng với một mẫu truy cập từ B liên kết đến A trong một phiên truy cập (session), ta tăng trọng số của cung (B,A) lên 1 nếu trong một phiên truy cập có liên kết từ B đến A. Sau khi duyệt tất cả các session ta sẽ có một đồ thị có trọng số thể hiện mối liên kết giữa các liên kết (link). Sau cùng, ta tiến hành chuẩn hóa trọng số các cung trong đồ thị với bằng cách chia trọng số của cung cho tổng trọng số các cung ra cho mỗi nút trong đồ thị. Trong quá trình này, ta xây dựng một ma trận vuông A có kích thước mxm với m là số URL trong toàn bộ các session thu thập được. Mỗi giá trị trong ma trận vuông A[i,j] ứng với cung (i,j), giá trị của nó được tăng lên sau mỗi liên kết từ i đến j được duyệt qua. Cuối cùng, ta chuẩn hóa ma trận A để thu được ma trận đồ thị xác suất.

 

Giải thuật xây dựng đồ thị xác suất

Giải thuật LPageRank được cải tiến từ giải thuật PageRank với web log.

 

Giả sử G=(W,E,P) là đồ thị xác suất cho tập các trang web của site là W. Sau đó tính LPageRank(LPR) của trang web như sau:

Với cách cải tiến này, giá trị LPageRank cho mỗi trang sẽ được tính toán phụ thuộc vào việc người dùng truy cập lên trang web đó nhiều hay ít. Nói cách khác, giá trị này phụ thuộc vào mức độ quan tâm của người dùng đối với trang web. Giải thuật LPageRank đã tối ưu hơn cách thực hiện máy móc của PageRank khi không quan tâm đến hành vi sử dụng web của người dùng của giải thuật PageRank. Đây là sự khác nhau cơ bản mà LPageRank đã sử dụng để tối ưu cho công cụ tìm kiếm.

Ứng dụng giải thuật TF-IDF kết hợp cùng với thuật giải LPageRank trong công cụ tìm kiếm.

Sử dụng giải thuật TF-IDF cho việc đánh trọng số câu truy vấn.

Định nghĩa trọng số TF-IDF.

Trọng số TF-IDF (Term Frequency-Inverse Document Frequency) là trọng số thường được sử dụng trong tìm kiếm thông tin và khai thác dữ liệu văn bản. Trọng số này là một độ đo tĩnh được sử dụng để đánh giá mức độ quan trọng của một từ (token) đối với một tài liệu và một từ trong tài liệu với tập các tài liệu. Độ quan trọng này được tăng lên tương ứng với số lần xuất hiện của từ trong tài liệu. TF (Term Frequency) trong một tài liệu là tần số xuất hiện của một từ khóa (term) đã cho trong một tài liệu. Và IDF (Inverse Document Frequency) là độ đo nghịch đảo của một từ khóa trong tất cả các tài liệu có trong kho tìm kiếm có chứa từ khóa.

Trong mô hình tìm kiếm này, một tài liệu là một vectơ thực d trong Rk (trọng số thực), di được xác định dựa trên một hàm tính toán TF-IDF. Cũng tương tự như một tài liệu, ta xem một câu truy vấn cũng là một vectơ thực q trong Rk trong đó qi là trọng số của ti trong q. Hàm tính độ liên quan là f(d,q)= sim(d,q) trong đó sim(d,q) là mức độ giống nhau giữa d và q.

Từ đó, định nghĩa giống nhau giữa một vectơ tài liệu và một vectơ truy vấn như sau:

Phương thức này sẽ gán một lượng đáng kể cho các từ khóa xuất hiện trong tài liệu nhưng không xuất hiện trong câu truy vấn. Vectơ truy vấn thường thưa thớt hơn nhiều so với vectơ tài liệu, vì vậy một phương thức tốt hơn nên loại bỏ hiệu ứng của các từ khóa không xuất hiện trong câu truy vấn.

Phương thức đo sự giống nhau cosin dựa trên quan sát ở trên, là phương thức thông dụng để đo sự giống nhau giữa một vectơ tài liệu và một vectơ truy vấn

Chú ý là, nếu góc giữa hai vectơ nhỏ thì cosin gần tới 1, là giá trị lớn nhất của sự giống nhau. Nếu hai vectơ gần như vuông góc thì cosin gần tới 0 nghĩa là sự giống nhau nhỏ nhất.

TF-IDF là phương pháp thông dụng để “cân nặng” (đánh giá) các từ khóa (term) trong một tài liệu. Ý tưởng cơ bản của phương pháp này là xem xét tính phổ biến của một từ khóa trong một tài liệu khi so sánh với tính phổ biến của thuật ngữ đó trong các tài liệu khác.

Giải thuật tính TF-IDF cho một tài liệu.

Định nghĩa chính qui của TF-IDF được định nghĩa như sau: Gọi n(d,ti) là tần số xuất hiện của ti trong d và N=là tổng số thuật ngữ trong d. Di chỉ số tài liệu chứa ti và D là tổng số tài liệu có trong tập hợp. Tần số thuật ngữ (term frequency) TF (d, ti) là tần số xuất hiện của ti trong d.

Có vài cách tính tần số thuật ngữ: hai cách thông dụng nhất là chia số lần xuất hiện của thuật ngữ trong tài liệu cho hoặc là tổng số thuật ngữ có trong tài liệu hoặc là số lần xuất hiện của thuật ngữ xuất hiện nhiều nhất trong tài liệu:

               TF(d, ti) = n(d, ti)/N

Hoặc

            TF(d, ti) = n(d, ti)/max(n(d, ti))

Trong bất kì trường hợp nào thuật ngữ xuất hiện nhiều hơn sẽ có điểm TF cao hơn (cao nhất là 1) và thuật ngữ ít xuất hiện sẽ có điểm TF gần bằng 0.

Ngược lại, IDF(ti) (Inverse Document Frequency) là tần số nghịch đảo của ti trong tất cảc các tài liệu có trong tập hợp và số tài liệu trong tập hợp có chứa ti.

               IDF(ti) = log(D/Di)  

Thuật ngữ thường xuyên xuất hiện trong tài liệu như là “the” vì vậy sẽ có IDF gần bằng 0 và thuật ngữ hiếm gặp sẽ có IDF gần bằng 1. Trọng số TF-IDF được tính bằng cách nhân tổ hợp điểm TF và IDF

               TF-IDF(d, ti) =TF(d,ti) x IDF(ti)

Qua công thức trên, ta có thể thấy rằng TF-IDF sẽ cho điểm một thuật ngữ cao hơn nếu nó xuất hiện thường xuyên trong một tài liệu và không xuất hiện thường xuyên trong các tài liệu khác.

Giải thuật TF-IDF.

Cho tập từ khóa t{t0,…tn} trong tập tài liệu D{D0,…DN}.

Tính TF-IDF(Di,ti).

B1:           Duyệt từng tài liệu Dj trong tập tài liệu D.

B2:           Duyệt từng từ khóa ti trong tập từ khóa t trong từng tài liệu Dj.

                 Nếu ti xuất hiện

                 count_ti =count_ti + 1.

B3:           Tính TF(Dj,ti)=count_ti/N //N tổng số từ trong tài liệu Dj.

Hoặc TF(Dj,ti)=count_ti/Max_count_term //Max_count_term số lần xuất //hiện của từ khóa xuất hiện nhiều nhất trong Dj

B4:           Duyệt hết một tài liệu Dj, nếu count_ti>0 thì count_di=count_di+1.

B5:           Duyệt từng từ khóa ti.

Tính IDF(ti)=log(N/count_di) //số tài liệu trong D chia cho tổng số tài liệu chứa ti.

B6:           Duyệt từng tài liệu liệu Dj trong tập tài liệu D.

                 Duyệt từng từ khóa ti trong tập từ khóa t trong từng tài liệu Dj.

Tính TF-IDF(Di,ti)= TF(Dj,ti)*IDF(ti).

Mô hình không gian vectơ, thường xuyên sử dụng TF-IDF để đánh giá các thuật ngữ và hàm cosin là hàm đo mức độ giống nhau, thể hiện là một phương thức tính độ liên quan giữa một tài liệu và một câu truy vấn tin cậy hơn. Song, phương pháp này có một nhược điểm là đánh giá các thuật ngữ độc lập với nhau, mà trong thực tế các thuật ngữ có liên quan với nhau và hiểu được điều này có thể dẫn đến việc tính độ liên quan tốt hơn.

Ứng dụng giải thuật TF-IDF trong công cụ tìm kiếm.

Độ đo TF-IDF là một trong những độ đo được sử dụng khá nhiều trong các công cụ tìm kiếm thông tin. Độ đo TF-IDF được ứng dụng cho việc xử lý truy vấn của người dùng trong tìm kiếm cục bộ trên web site.

Quá trình xử lý câu truy vấn và tìm kiếm trên trang web không giống với những tài liệu thông thường vì trang web có một số đặc thù riêng biệt khác với các dạng tài liệu phẳng khác. Do đó, khi tiến hành thực nghiệm cần tiến hành một số bước tiền xử lý trước khi áp dụng giải thuật TF-IDF.

Công cụ tìm kiếm thông tin cục bộ trên web site được ứng dụng giải thuật TF-IDF cho xử lý trực tuyến câu truy vấn của người dùng và tài liệu tìm kiếm. Sau khi xử lý, giải thuật LPageRank sẽ được áp dụng để tối ưu trọng số của tài liệu.

Ngoài ra, trong mô hình này, cơ chế gom nhóm phiên truy cập của người dùng được sử dụng để gom các kết quả tìm kiếm vào nhóm các mẫu truy cập nhiều nhất và được người dùng quan tâm nhất nhằm hướng kết quả tìm kiếm gần với mục tiêu sử dụng của người dùng. 

Algorythm LPageRank
LPageRank Algorythm LPageRank thuat toan xep hang giai thuat google