Khóa luận Bài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ HTML và đồ thị web

MỤC LỤC

TÓM TẮT NỘI DUNG i

MỤC LỤC ii

Bảng các kí hiệu và chữ viết tắt iv

Danh mục hình vẽ v

Danh mục các bảng biểu vi

MỞ ĐẦU 1

Chương 1. Giới thiệu bài toán trích xuất từ khoá cho trang web 3

1.1. Đặt vấn đề 3

1.2. Khái niệm và các đặc trưng của từ khóa 4

1.3. Đánh giá các từ khóa 5

1.4. Thách thức của bài toán sinh từ khóa cho trang web 5

1.4.1. Đối với các trang có nội dung tập trung 6

1.4.2. Đối với các trang có nội dung tổng hợp 6

1.4.3. Các vấn đề khác 6

1.5. Ứng dụng của từ khóa trong các lĩnh vực 7

1.5.1. Vai trò từ khóa trong máy tìm kiếm 7

1.5.1.1. Quảng cáo trên máy tìm kiếm 7

1.5.1.2. Hoạt động quảng bá web trong máy tìm kiếm 9

1.5.3. Vai trò từ khóa trong các trang web tổng hợp thông tin 10

1.6. Tổng kết chương 12

Chương 2. Các công trình liên quan 13

2.1. Các phương pháp trích xuất từ khóa cho văn bản 13

2.1.1. Phương pháp tần số từ 13

2.1.2. Phương pháp sử dụng các thông tin khác trong văn bản 14

2.1.3. Phương pháp sử dụng học máy 15

2.1.3.1. Trích xuất từ khóa sử dụng phân lớp Naïve Bayes 16

2.1.3.2. Trích xuất từ khóa sử dụng lexical chain (chuỗi từ vựng) và phân lớp 16

2.2. Các phương pháp trích xuất từ khóa cho trang web 17

2.2.1. Tần số từ 17

2.2.2. Kĩ thuật khai phá log 17

2.2.3. Kĩ thuật áp dụng máy tìm kiếm và độ tương đồng từ 18

2.3. Gán từ khóa trong văn bản, web (keyword assignment) 19

2.4 Tổng kết chương 19

Chương 3. Hướng giải quyết và đề xuất mô hình bài toán 20

3.1. Hướng giải quyết 20

3.1.1. Sử dụng độ quan trọng của các thẻ trong HTML 20

3.1.2. Sử dụng đồ thị web 23

3.1.2.1. Định nghĩa đồ thị Web 23

3.1.2.2 Nội dung của phương pháp 24

3.1.3. Sử dụng query log 26

3.1.4. Sử dụng từ điển hỗ trợ 27

3.2. Đề xuất mô hình bài toán 27

3.2.1. Mô hình toàn hệ thống 27

3.2.2. Mô đun Crawler 28

3.2.3. Mô đun sinh từ khóa 29

3.2.3.1. Mô đun sử dụng trọng số thẻ HTML 30

3.2.3.2. Mô đun sử dụng đồ thị web 32

3.2.3.3. Các phương pháp hỗ trợ 33

3.2.3.4. Mô đun tổng hợp 35

3.3. Tổng kết chương 35

Chương 4. Thực nghiệm và đánh giá 36

4.1. Giới thiệu bài toán thực nghiệm 36

4.2. Môi trường, dữ liệu 36

4.1.1. Môi trường phần cứng 36

4.1.2. Mô tả chương trình 36

4.1.3. Công cụ phần mềm 37

4.1.4. Dữ liệu thử nghiệm 38

4.3. Kết quả thực nghiệm 40

4.4. Đánh giá kết quả thực nghiệm 43

Kết luận 46

Hướng phát triển tiếp theo 47

Tài liệu tham khảo. 48

 

 

doc59 trang | Chia sẻ: netpro | Lượt xem: 2105 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu Khóa luận Bài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ HTML và đồ thị web, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
tài liệu (tf) và phân phối của từ ở trong corpus (idf - inverted document)[34] idf(keyword) = Trong đó : NUMDOC: số tài liệu trong tập corpus NUMDOC(keyword) : chính là số tài liệu mà có từ keyword xuất hiện. Nếu tf(keyword) x idf(keyword) vượt một ngưỡng xác định, các cụm từ khóa được tìm thấy và được gán trọng số. Những từ nào có trọng số cao thì được chọn. Đối với trang web, có thể áp dụng phương pháp này bằng cách từ địa chỉ trang web cần lấy từ khóa. Lần theo các liên kết trong trang hạt giống này (seed page) để lấy về các trang web khác và phải thuộc cùng domain[25]. Tập các trang web này tạo nên một tập corpus. Việc tính toán từ khóa cho mỗi tài liệu web sẽ được tính theo công thức trên dựa vào những đoạn text hiển thị trích ra từ các trang web đó. Tuy nhiên, do trang web có nhiều những từ được hiển thị trong một trang không có ý nghĩa như : thực đơn, quảng cáo... nhưng lại xuất hiện nhiều lần ở các trang. Vì vậy, các từ xuất hiện trong các mục này lại có tần số xuất hiện cao, và thường vào các từ khóa. 2.1.2. Phương pháp sử dụng các thông tin khác trong văn bản Phương pháp tìm từ khóa dựa vào trích xuất các phần quan trọng của các phần trong văn bản có phần tương tự như phương pháp tóm tắt của Edmundson [12], dựa vào phương pháp lấy phần quan trọng của văn bản: là các cụm từ gợi ý, từ khóa, tiêu đề của văn bản, ví trị của câu trong văn bản. Phương pháp tìm từ khóa cũng sẽ dùng các đặc điểm của văn bản để tìm ra những từ khóa. Dưới đây là cơ sở của phương pháp: Cụm từ gợi ý trong văn bản Thông thường các cụm từ gợi ý là liên quan hoặc không liên quan tới các câu quan trọng. Ví dụ với các từ “Trong bài báo này”, “Tóm lại”... thường là phần quan trọng của văn bản. Hoặc những cụm từ khác như “ví dụ” chỉ ra phần không quan trọng của văn bản. Tiêu đề của văn bản Người viết khi viết về văn bản của mình thì phải luôn chú trọng đến nội dung, cũng như cách thể hiện tiêu đề sao cho người đọc chỉ cần nhìn qua vào tiêu đề có thể hiểu được nội dung của toàn bộ văn bản. Vì vậy, tiêu đề là có độ quan trọng rất cao trong văn bản. Đã có các bài báo nghiên cứu tóm tắt văn bản dựa vào độ tương đồng câu dùng câu tiêu đề làm câu mẫu để các câu khác so sánh [1]. Có thể áp dụng phương pháp này trong văn bản web mà đặc biệt là phần văn bản trong thẻ của nguồn HTML của trang web. Việc bám sát vào các câu của tiêu đề văn bản sẽ cho việc tìm nội dung của văn bản, hay trang web sẽ trở nên chính xác hơn. Các câu tiêu đề có thể được coi như là phần tóm tắt ngắn gọn của văn bản, các từ có nghĩa tương tự, hay những từ lặp lại nhiều trong văn bản trùng với các từ trong tiêu đề thì đều quan trọng. Vị trí của các từ khóa trong văn bản Thông thường những từ mà được xuất hiện trong những đoạn đầu tiên trong văn bản thường có độ quan trọng cao hơn các từ mà đứng giữa hay cuối. Do vậy, có thể chọn các từ khóa mà sao cho nó xuất hiện nhiều ở phần mở đầu, nhất là đối với những bài viết dài. Tuy nhiên, một số bài lại có cấu trúc dạng: phần giới thiệu, phần chính, tóm lại. Các từ ở phần giới thiệu và phần tóm lại nếu xuất hiện nhiều trong văn bản đều khá quan trọng Tần số từ trong văn bản Các từ xuất hiện thường xuyên trong văn bản có xu hướng chỉ ra chủ đề của văn bản đó. Mức độ quan trọng của các từ, cụm từ tính toán trên cơ sở tần số xuất hiện của chúng trong văn bản. Điểm khác của kĩ thuật tần số này so với tần số bên trên là : tần số từ bên trên xét về một tập các bài, hoặc tập các đoạn văn khác nhau. Còn đây chỉ là áp dụng trong nội tại của một văn bản. Một mục từ, cụm từ xuất hiện trong văn bản nhiều hơn một ngưỡng nào đó thì được coi là từ quan trọng. Từ những cơ sở trên ta có thể tính được trọng số của một từ khóa bằng tổ hợp tuyến tính các trọng số nhận được từ các phương pháp trích rút ở trên: weight(K) = Các tham số sẽ được điều chỉnh phù hợp bằng cách thử nghiệm với các dữ liệu khác nhau. 2.1.3. Phương pháp sử dụng học máy KEA [19] và GenEX [9] là hai trình ứng dụng đưa ra một số giải pháp về bài toán trích xuất từ khóa (keyword extraction)[28]. Trong khi GenEX dùng giải thuật di truyền thì KEA dùng luật quyết định dựa trên phân lớp Naive Bayes (Naïve Bayes decision rule) trên 2 thuộc tính đó là TFxIDF và khoảng cách của từ đến đoạn đầu của văn bản. Một phương pháp khác áp dụng dựa trên chuỗi từ vựng (lexical chain), áp dụng từ điển WordNet và bài toán phân lớp để giải quyết bài toán sinh từ khóa này. 2.1.3.1. Trích xuất từ khóa sử dụng phân lớp Naïve Bayes Trong bài báo [28]Yasin Uzun sử dụng phân lớp Naïve Bayes để áp dụng vào bài toán này. Ông cho rằng bài toán này có thể coi là một vấn đề trong học máy. Có các từ ở trong văn bản và mục đích là nhận ra một từ có phải thuộc lớp từ khóa( keywords) hay là một từ thông thường(ordinary words). Như các mô hình học máy khác, mô hình này cũng sử dụng tập huấn luyện để học cách sao để nhận ra một từ là từ khóa hay không. Dựa vào những thông tin đã nhận được từ quá trình học để nhận biết, tìm ra các từ khóa từ những văn bản mới đưa vào. Naïve Bayes dựa trên xác suất của các từ để quyết định xem từ đó có thỏa mãn ngưỡng là một từ khóa không. Trước hết, văn bản cần được được tách ra thành các token sử dụng các kí hiệu như: dấu cách, xuống dòng, tab, dấu chấm, phẩy,... Những chữ không là alpha-beta bị loại bỏ. Tính chỉ số TFxIDF cho các token. Do sử dụng IDF nên các tập dữ liệu phải trong cùng một chủ đề. Để xây dựng được một mô hình phân lớp để nhận biết được đâu là từ khóa. Tác giả đã sử dụng các thuộc tính gồm: tần số xuất hiện, vị trí của từ trong văn bản. 2.1.3.2. Trích xuất từ khóa sử dụng lexical chain (chuỗi từ vựng) và phân lớp Trong bài báo năm 2007 [11] Gonenc Ercan, Ilyas Cicekli đã trình bày cách tiếp cận bài toán theo hướng sử dụng từ điển ngữ nghĩa WordNet [38] kết hợp phân lớp cây quyết định để có thể nhận dạng chính xác từ khóa. Phương pháp này có sử dụng các quan hệ ngữ nghĩa nhằm nâng cao chất lượng các từ khóa liên quan. Trích xuất Chuỗi từ vựng là việc đưa ra các quan hệ ngữ nghĩa của câu, văn bản đưa vào. Trong một câu, chuỗi từ vựng sẽ chỉ ra được đâu là động từ, danh từ, trạng từ và các quan hệ đồng nghĩa, trái nghĩa, là (is a), có (has a)...Công việc khó khăn nhất đó chính là xây dựng được một chuỗi từ vựng của văn bản dựa vào từ điển WordNet. WordNet được chọn vì từ điển tiếng Anh này có đầy đủ các thông tin về các từ trong tiếng Anh như: danh từ, các từ đồng nghĩa, trái nghĩa..... Với các quan hệ ngữ nghĩa này, tác giả xây dựng mô hình để sinh ra chuỗi từ vựng (lexical chain) toàn bộ văn bản tạo thành một chuỗi từ vựng có cấu tạo giống với WordNet. Nhiều câu phức tạp sẽ sinh ra trường hợp nhầm ngữ nghĩa. Sau khi có được các chuỗi ngữ nghĩa của văn bản cần sinh từ khóa. Tác giả chọn thuật toán cây quyết định C4.5 với các thuộc tính là : vị trí xuất hiện đầu tiên, tần số xuất hiện, vị trí xuất hiện cuối cùng, và một thuộc tính lấy từ chuỗi từ vựng đã sinh ra từ văn bản. Bài báo cũng đề xuất ra các trọng số cụ thể cho các quan hệ như đồng nghĩa :10; quan hệ is a: 7. quan hệ has a: 4. 2.2. Các phương pháp trích xuất từ khóa cho trang web 2.2.1. Tần số từ Phương pháp tần số từ trong văn bản có thể được áp dụng trên các trang web. Việc lấy ra nội dung của văn bản trong các trang web là đơn giản. Và phương pháp phân tích nội dung này, thống kê tần số xuất hiện của các từ, cụm từ áp dụng kĩ thuật n-gram. Một ví dụ về trích từ khoá cho trang web phục vụ hoạt động của SEO của Andy Hoskison, LLC trong Hình 5 áp dụng kĩ thuật tìm các từ khoá đơn và cụm từ khoá bằng phương pháp xét tần số xuất hiện của các từ trong văn bản hiển thị web. Phương pháp tìm từ khóa trang web này chỉ dừng lại ở việc tìm từ khóa đơn và kép, tính tần số của nó trên chính trang đó, cho nên nhiều trang web cho không chính xác. Hình 5. Hình minh họa kết quả sinh từ khóa của trang web 2.2.2. Kĩ thuật khai phá log Các máy tìm kiếm sử dụng kĩ thuật khai phá log để có thể tìm ra những từ khoá khác nhau cho trang web[31] . Đó là một lợi điểm của các máy tìm kiếm. Những hoạt động trước của người dùng được ghi lại sẽ cho ta hiểu cách nghĩ của người dùng đối với các trang web. Họ cố gắng tìm ra mối quan hệ giữa các từ khóa đã được người dùng tìm dựa vào một tập các từ khoá ban đầu. Google’s Adword Tool [31] là một ví dụ về việc dùng log để đưa ra những từ khóa gợi ý, với đầu vào là từ khoá ban đầu. Yahoo’s Keyword Selection Tool [32] cũng tương tự khi sử dụng tần số xuất hiện của những từ khoá liên quan tới từ khoá của người dùng yêu cầu. Một phương pháp mới hơn được Bart đễ xuất dựa trên việc lọc liên hợp (collaborative filtering) sử dụng mối quan hệ của query và các url click vào trong log [16]. Tuy nhiên những từ khóa gợi ý sẽ là những từ khóa xuất hiện nhiều trong log, thường có độ phổ biến cao và quan trọng do đó từ khóa này sẽ có giá cao. 2.2.3. Kĩ thuật áp dụng máy tìm kiếm và độ tương đồng từ Bài báo [25][17] sử dụng chính máy tìm kiếm, cùng độ tương đồng từ để áp dụng cho bài toán tìm từ khóa cho trang web. Phương pháp đã được dùng trong thương mại đó là việc áp dụng dựa vào tìm kiếm lân cận (proximity search) để sinh từ khóa. Proximity Search là cách dựa vào máy tìm kiếm, với một query đầu vào gọi là từ khoá hạt giống (seed keyword) và tìm ra được những từ khoá từ những trang liên quan trả về từ máy tìm kiếm. Kĩ thuật này nhằm tìm từ khóa cho một trang chủ, portal. Quy trình của phương pháp này có thể được miêu tả như sau: Bước 1: Tải về toàn bộ các trang thuộc cùng domain với trang này(có thể phải giới hạn số trang lấy về) Bước 2: Trích xuất các từ khóa cho các trang web này dựa vào độ đo (tf x idf). Lưu trữ dưới dạng một tập từ điển ban đầu (lấy trong các ngưỡng xác định, loại bỏ từ dừng...) Bước 3: Với mỗi từ khóa trong bộ từ điển từ khóa, tìm kiếm những trang web liên quan nhờ các máy tìm kiếm. Chỉ lấy các trang đầu trả về của máy tìm kiếm. Bước 4: Tải các trang trong kết quả máy tìm kiếm trả về, sinh từ khóa cho các trang web này dựa vào tần số xuất hiện của từ, so sánh độ tương đồng ngữ nghĩa của từ tìm kiếm và các từ khóa này. Nếu thỏa mãn các ngưỡng về độ tương đồng, tần số xuất hiện thì thêm vào từ điển những từ khóa này. Bước 5: Thống kê lại các từ khóa nhờ vào tần số xuất hiện trong từ điển. Kết quả của phương pháp này khá là hiệu quả và tốt, nhưng chi phí cho nó là rất nhiều, và nó phù hợp cho các trang mà độ nhiễu trong các trang khác nhau là không quá lớn. Việc so sánh ngữ nghĩa của các từ khóa tốt là thành công cho phương pháp này. 2.3. Gán từ khóa trong văn bản, web (keyword assignment) Các phương pháp nêu trên là các phương pháp dùng để trích xuất từ khóa (keyword extraction) [29][9][28]. Trong khi đó có một phương pháp cũng đã được sử dụng nhiều trong trang web, và cả văn bản đó là phương pháp gán từ khóa. Việc gán từ khóa chỉ là việc khớp các từ trong văn bản, web với các từ thuộc bộ từ điển có sẵn. Từ những trang cần sinh từ khóa, ta lấy ra những đoạn text trong trang web đó. Dùng các kĩ thuật tách từ, n-gram để khớp các từ khóa với các từ trong bộ từ điển có sẵn. Giải pháp này được áp dụng nhiều trong các trang báo điện tử, các bản tóm tắt, để có thể khớp một cách chính xác nhất. Các từ được khớp chính là các từ trong từ điển nên chúng sẽ không bị sai về mặt ngữ pháp, hay lộn xộn về mặt từ vựng. 2.4 Tổng kết chương Chương này đã giới thiệu những phương pháp cơ bản để giải quyết bài toán trích xuất từ khóa trong văn bản cũng như đối với Web. Các phương pháp này hiệu quả đối với một số miền, và có thể áp dụng trong nhiều bài toán khác nữa. Trong chương tiếp, tôi xin trình bày về hướng giải quyết bài toán sinh từ khóa trên các trang web, xây dựng mô hình. Chương 3. Hướng giải quyết và đề xuất mô hình bài toán 3.1. Hướng giải quyết Như đã đề cập ở chương II, nhiều phương pháp đã được áp dụng trên thực tế và có kết quả tốt như : sử dụng log, độ tương đồng từ. Tuy nhiên, các phương pháp này chỉ hiệu quả với các trang Web tiếng Anh. Các máy tìm kiếm có lợi thế khi họ lưu trữ được những bộ log rất lớn, ghi lại các giao dịch của người dùng trong nhiều năm. Vì vậy, việc tìm kiếm trong log sẽ rất hữu hiệu cho các doanh nghiệp tìm ra các từ khóa hướng người sử dụng. Còn các phương pháp áp dụng học máy, thì giá phải trả là họ phải có tập huấn luyện, thời gian chạy khá lâu. Kết quả tốt thì tập dữ liệu huấn luyện phải tốt. Các phương pháp sử dụng tần số đơn thuần thể hiện không hiệu quả do chỉ xét tần số mà chưa tính đến độ quan trọng trong văn bản Web. Một thách thức khác đặt ra với tiếng Việt chính là việc tách các cụm từ. Không những chỉ có văn bản thông thường được hiển thị, web còn chứa đựng trong nó nhiều các đặc trưng khác mà rất quan trọng cho bài toán sinh từ khóa. Dưới đây là hai hướng tiếp cận chính của tôi trong khóa luận đó là: sử dụng độ quan trọng của các thẻ trong HTML và đồ thị web. Hai hướng này là chủ đạo có thể áp dụng với các loại trang web tiếng Việt và tiếng Anh. Tuy nhiên, phương pháp đồ thị web do phải xử lý nhiều nên phù hợp hơn với các trang chủ, các web portal. Bên cạnh hai phương pháp trên, tôi còn ứng dụng thêm hai phương pháp đó là : query log, và từ điển (bài toán gán từ khóa). Do log chỉ giới hạn một số trang và với ngôn ngữ xác đinh, nên nó chỉ là thành phần hỗ trợ nhằm nâng cao kết quả cho các trang web trong log. Còn bài toán gán từ khóa là các từ trong từ điển tiếng Việt, thì nó chỉ phù hợp cho việc gán từ khóa cho các văn bản ngắn, các đoạn tóm tắt bằng tiếng Việt. Sau đây tôi xin trình bày các phương pháp đã đề cập ở trên. 3.1.1. Sử dụng độ quan trọng của các thẻ trong HTML Theo Wikipedia [3] HTML (tên Tiếng Anh viết tắt của HyperText Markup Language hay “ngôn ngữ đánh dấu siêu văn bản”) là một ngôn ngữ đánh dấu được thiết kế nhằm mục đích hiển thị các thông tin khác nhau lên trên trình duyệt. Với ngôn ngữ HTML, chúng ta có thể biểu diễn trang web một cách sinh động, tùy thích với nhiều màu sắc, điểm nhấn, cấu trúc khác nhau. HTML bây giờ đã trở thành chuẩn của tổ chức World Wide Wed Consortium (W3C) duy trì, và được mọi trình duyệt phải thiết kế theo. Các file HTML có chứa các thẻ đánh dấu, nghĩa là các chỉ thị cho chương trình về cách hiển thị hay xử lý văn bản ở dạng thuần túy. Ngôn ngữ HTML có rất nhiều các thẻ khác nhau, chi tiết có thể xem tại W3C. Ví dụ: Khi một người muốn nhấn mạnh một điều gì đó trong bài viết của mình họ thường tô đậm chữ với thẻ hoặc dùng các thẻ ,... để có thể phân biệt được với các chữ khác. Hay các thẻ như trong văn bản web có chứa tiêu đề của trang web đó. Nhờ những đặc điểm sẵn có là HTML trong văn bản web, tôi đã đề xuất phương án áp dụng độ quan trọng của các từ trong các thẻ khác nhau trong văn bản HTML để phục vụ cho bài toán sinh từ khóa. Trước hết, áp dụng phương pháp này vào bài toán trích xuất từ khóa là việc lấy nội dung nội tại của trang web về để xử lý - hay văn bản HTML của chính trang cần trích xuất. Như đã nhắc về các công trình liên quan tại chương II [25][13], tần số từ (TF) là một trong những phương pháp có thể áp dụng không những trong văn bản , mà còn trong cả web. Phương pháp của tôi đề xuất không tính trực tiếp tần số xuất hiện của các từ khóa trong văn bản web, nhưng cũng gián tiếp tính tần số của chúng nhưng theo độ quan trọng khác nhau của mỗi loại thẻ HTML quan tâm. Một chú ý, ở phương pháp này không dùng IDF do chỉ xét trên chính một trang. Mỗi trang web hiển thị lên trình duyệt được nhờ vào các thẻ HTML. Cho nên, với người soản thảo web, họ sẽ chủ động đặt những từ, câu quan trọng trong các thẻ HTML có độ quan trọng cao. Nhiệm vụ đặt ra là làm sao biết trong HTML thẻ nào là quan trọng, và thẻ nào quan trọng hơn thẻ nào, thẻ nào không quan trọng. Trong dự án tạo phần abstract (tóm tắt) cho văn bản của ứng dụng TextNet [7][6], qua nhiều thực nghiệm, nhóm các nhà nghiên cứu đã đưa ra được trọng số của các thẻ trong HTML dưới Bảng 1 sau: Bảng 1. Bảng trọng số các thẻ HTML trongTextNet TAG HTML WEIGHT A 1 B 2 BLOCKQUOTE -1 CENTER 3 CODE -1 EM 1 H1 10 H2 9 H3 8 H4 7 KBD -1 PRE -1 SAMP -1 STRONG 2 SUB -1 SUP -1 TITLE 15 U 1 Và tôi cũng áp dụng trọng số của các thẻ này trong quá trình thực nghiệm. Như thấy trong bảng, thẻ có trọng số cao nhất, một số thẻ dạng hay không quan trọng mà còn làm giảm đi ý nghĩa của từ thể hiện trong nó. Tuy nhiên, đối với bài toán sinh từ khóa không những chỉ xét những thẻ đó, mà còn cần xét những thẻ khác nữa và tôi đưa thêm vào một số thẻ khác trong Bảng 2 : Bảng 2. Bảng các thẻ HTML quan trọng khác TAG HTML WEIGHT P 1 DIV 1 META(name = ‘Keywords’) 17 META(name = ‘descriptions’) 10 Qua quá trình thực nghiệm, các trọng số của các thẻ này được điều chỉnh cho phù hợp sao cho kết quả đầu ra là tốt nhất. Những thông tin nằm trong các thẻ khác nhau thì có độ quan trọng khác nhau. Một câu, cụm từ, hay từ có thể nằm đan xen trong nhiều thẻ khác nhau. Vì vậy, trọng số toàn cục của câu, từ này sẽ là tổng số các trọng số mà nó thuộc vào các thẻ. Các từ hay câu thuộc vào những thẻ nào thì nó sẽ nhận tổng của các trọng số của các thẻ đó. Vì vậy, việc tính tần số vẫn tồn tại ngầm trong trọng số toàn cục. Ví dụ như một văn bản HTML dạng TIT P T B TIT Trong văn bản trên các từ “TIT” sẽ nhận các trọng số của thẻ và thẻ , do chúng đều nằm trong các thẻ này. Và trọng số của “TIT” = trọng số + trọng số + trọng số . Tương tự, trọng số của “T” được tính = trọng số + trọng số + trọng số. Gọi : T= {tập các thẻ của HTML mà ta quan tâm} W = {trọng số các thẻ HTML} W(i) = trọng số của thẻ thứ i thuộc T. Trọng số từ “A”=(với từ “A” xuất hiện trong “thông tin quan tâm” của thẻ i ) “Thông tin quan tâm” của thẻ i là những phần văn bản nằm trong phần mở thẻ và đóng thẻ hay những thuộc tính của thẻ. 3.1.2. Sử dụng đồ thị web 3.1.2.1. Định nghĩa đồ thị Web Các trang web ngoài các đặc trưng về sự hiển thị trên trình duyệt qua ngôn ngữ HTML mà chúng còn có sự liên kết, kết nối đến nhau. Chính những liên kết này tạo nên đồ thị web. Đồ thị Web là một đồ thị có hướng gồm các đỉnh là các trang web (các trang tĩnh), và có cung nối từ trang A đến trang B nếu từ trang A có liên kết đến trang B. Liên kết trong trang web được thể hiện qua thẻ của HTML(Hình 6). Thuộc tính href= “B” của thẻ có giá trị B chính là địa chỉ của trang B. Chính vì các trang web trên Internet hiện nay là rất lớn, và có rất nhiều liên kết, nên việc tạo được một đồ thị web cho liên quan đến các trang lớn đòi hỏi nhiều thời gian và phức tạp. Hình 6. Mô tả đồ thị web A C B D Mạng của các liên kết trong đồ thị web đã làm cho nâng cao, cải thiện việc tìm kiếm trên mạng [21][14][15][10] và làm cho việc phân lớp chính xác hơn [22] và đánh giá được các trang mới nhất trên cộng đồng mạng [23]. Hơn thế nữa các liên kết này còn là một nguồn thông tin cung cấp dồi dào phục vụ cho các ngành khoa học xã hội. Và bên cạnh đó, nó còn giúp đánh giá được các đường đi tồn tại trong đồ thị web này nhằm phục vụ việc gợi ý cho người dùng. Đồ thị web có rất nhiều ứng dụng trong việc khai phá web, là cơ sở để các máy tìm kiếm đánh hạng trang (thuật toán HITS), phân tích hành vi người dùng, hỗ trợ bài toán crawling... 3.1.2.2. Nội dung của phương pháp Trong các trang web có các liên kết đến các trang web khác, và có nhiều trang khác có link liên kết đến các trang này. Trong các trang web, liên kết được thể hiện qua thẻ . Trang A có các liên kết đến tập các trang khác và trong một số trường hợp tập các trang này liên quan đến trang A, nhưng nhiều trường hợp tập các trang lại không liên quan nhiều đến trang A đó. Đặc biệt đối với các trang chủ, trang tổng hợp thì có rất nhiều liên kết tới không liên quan. Trong khi đó, một phần nội dung của những trang trỏ đến trang A lại liên quan đến trang A. Những người soạn thảo web khi tạo liên kết đến một trang nào, họ luôn dùng một vài từ đặc trưng đến trang web họ muốn trỏ tới, rồi đặt thẻ liên kết đến trang đó. Vì vậy, chính những phần hiển thị (của phần liên kết trỏ tới các trang) trên trình duyệt nói lên phần nào suy nghĩ của người khác về trang đang được hướng tới. Trong liên kết web của trang THPT-NTT (Hình 7), ta thấy được cách đặt phần hiển thị cho một số trang báo nổi tiếng. Giả dụ ở đây, nếu ta muốn sinh từ khóa cho trang dân trí , dựa vào phần hiển thị là “Đọc báo trực tuyến Dân Trí” ta có thể trích xuất ra các từ khóa như : đọc báo, trực tuyến, dân trí.... Nếu phân tích nhiều trang khác trỏ đến trang dân trí này thì kết quả sẽ cho cao hơn. Hình 7. Phần hiển thị của các liên kết đến các trang cần trích xuất từ khóa Trong khóa luận này, tôi áp dụng các liên kết trỏ đến các trang cần sinh từ khóa. Vậy làm sao để có thể tìm được một trang có liên kết đến trang ta muốn sinh từ khóa? Những trang có liên kết đi thì dễ dàng tìm thấy khi chỉ phải phân tích nội dung của chính văn bản HTML và nhận dạng các thẻ . Để tìm được các link liên kết đến trang cần sinh từ khóa, tôi sử dụng công cụ máy tìm kiếm như google, yahoo, altavista để tìm ra các link trỏ đến trang web mà ta đang muốn có từ khóa. Câu truy vấn trong các máy tìm kiếm để tìm ra tập các trang trỏ đến một trang có dạng “link:A”. Với câu truy vấn này các máy tìm kiếm sẽ trả về tập các trang web có liên kết trỏ đến trang “A” này. Hình 8, là tập các trang web trả về từ máy tìm kiếm google có liên kết đến trang Hình 8. Kết quả trả về của máy tìm kiếm Google có liên kết trỏ tới trang vnexpress Qua việc xử lý kết quả trả về qua các máy tìm kiếm, chúng ta kết nối, tải các trang liên quan này về rồi phân tích cấu trúc của các trang web này. Dựa vào thẻ (anchor text) tìm những liên kết có địa chỉ giống như trang ta muốn sinh từ khóa. Từ đó lọc ra các phần hiển thị của thẻ đó, xử lý chúng để tìm ra từ khóa. Do kết quả của các máy tìm kiếm trả về có những trang với tập kết quả rất lớn, nên có thể dùng số lượng các từ khóa để giới hạn việc tải các trang web về. Việc sử dụng máy tìm kiếm làm công cụ trung gian không những giúp tìm các trang có liên kết đến trang ta cần sinh từ khóa, mà còn giảm đi lượng lớn các trang không đúng, thiếu tin cậy nhờ vào thứ hạng của máy tìm kiếm. Tuy nhiên phương pháp này sẽ có tác dụng đối với các trang có liên kết đến. Đối với các trang không nổi tiếng, hay không có link đến thì sẽ không tìm được các trang liên quan, và không có kết quả. 3.1.3. Sử dụng query log Các máy tìm kiếm hàng ngày phải trả lời yêu cầu của người dùng rất nhiều. Và những thông tin của người dùng cũng rất hữu hiệu cho việc tìm từ khóa cho các trang web. Đối với các người quản trị web thì họ có thể tự tìm được những từ khóa cho trang web của mình. Nhưng đôi khi chính họ cũng không thể biết được những suy nghĩ mà người dùng nghĩ tới trang web của mình như thế nào. Chính vì vậy, những nhận xét của số đông người dùng sẽ là một phương pháp hữu hiệu để sinh từ khóa một cách đại trà nhất theo cách hiểu của người dùng. Như đã đề cập ở chương I, các máy tìm kiếm có một lợi thế khi họ ghi lại quá trình sử dụng của người dùng để có thể hướng đến chủ đề người dùng quan tâm, hay cách nghĩ của họ về các trang web. Trong các máy tìm kiếm có các bộ log ghi lại toàn bộ thông tin truy cập, tra cứu của người dùng khi dùng. File này được lưu lại có các trường như: ngày tháng, phiên giao dịch, query truy vấn, url được click, browser...Dưới đây là ví dụ một phần của log của máy tìm kiếm MSN [39]( dung lượng ~ 1.3Gb) mà tôi cũng dùng làm thực nghiệm( Bảng 3): Bảng 3. Ví dụ về các trường trong querylog của MSN Time Query QueryID SessionID URL Result count 1 2006-05-01 00:00:03 us geography f6f710aa27014dac 1cb8398abb354112 20 2 2006-05-01 00:00:04 msn groups ba6d190cc4cd4fd3 136fd5e571d24886 10 3 2006-05-01 00:00:05 internal drive a0f7737bb44c46d5 0ff87b8bdbac406d 12 Hàng ngày số người tìm kiếm trên các máy tìm kiếm là rất nhiều, cho nên các file lưu trữ này thường rất lớn. Chúng ta quan tâm đến 2 trường query và url được click vào để giải quyết bài toán trích xuất từ khóa. Khi đưa trang web cần sinh từ khóa vào, nhiệm vụ đặt ra cần tìm các query mà đã dùng máy tìm kiếm rồi truy nhập vào trang này. Các từ khóa sinh ra sẽ dựa vào tần số xuất hiện của các từ trong query. Vì đã qua bước xử lý của máy tìm kiếm, nên kết quả thường có kết quả khá chính xác. Tuy nhiên, những kết quả trả về của số đông cho nên giá của các từ khóa trên máy tìm kiếm thường đắt. 3.1.4. Sử dụng từ điển hỗ trợ Đối với những trang tin tức, hay báo chí là những bài viết về một chủ đề. Chúng ta có thể áp dụng phương pháp gán từ khóa cho văn bản này bằng cách so khớp các từ trong văn bản với những từ hiện có trong từ điển. Sự phong phú, chính xác của từ điển cũng dẫn đến sự chính xác, đa dạng trong cách sinh từ khóa. Các từ khóa này sinh ra do đã qua từ điển nên chúng có ý nghĩa rõ ràng, rành mạch. Tuy nhiên, phương pháp này sẽ tốn nhiều thời gian nếu từ điển là lớn, và văn bản áp dụng dài. Nó đặc biệt hữu ích với các trang có các phần tóm tắt, và nhiệm vụ chỉ là sinh từ khóa cho một đoạn văn tóm tắt. Trang báo điện tử báo mới là một trong những trang web đã có phần sinh từ khóa này trong các tóm tắt văn bản [29][9][28]. 3.2. Đề xuất mô hình bài toán Internet tập các trang web Mô đun Crawler1

Các file đính kèm theo tài liệu này:

  • docBài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ html và đồ thị web.doc