Giáo trình Khai phá dữ liệu web

Nội dung text: Giáo trình Khai phá dữ liệu web

1. Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU WEB 1.1. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU (DATAMING) VÀ KDD 1.1.1. Tại sao lại cần khai phá dữ liệu (datamining) Khoảng hơn một thập kỷ trở lại đây, lượng thông tin được lưu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng lượng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Nói một cách hình ảnh là chúng ta đang “ngập” trong dữ liệu nhưng lại “đói” tri thức. Câu hỏi đặt ra là liệu chúng ta có thể khai thác được gì từ những “núi” dữ liệu tưởng chừng như “bỏ đi” ấy không ? “Necessity is the mother of invention” - Data Mining ra đời như một hướng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên []. Khá nhiều định nghĩa về Data Mining và sẽ được đề cập ở phần sau, tuy nhiên có thể tạm hiểu rằng Data Mining như là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó. 1.1.2. Khai phá dữ liệu là gì? Khai phá dữ liệu (datamining) được định nghĩa như là một quá trình chắt lọc hay khai phá tri thức từ một lượng lớn dữ liệu. Một ví dụ hay được sử dụng là là việc khai thác vàng từ đá và cát, Dataming được ví như công việc "Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trước. Thuật ngữ Dataming ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ Datamining như Knowledge Mining (khai phá tri thức), knowledge extraction(chắt lọc tri thức), data/patern analysis(phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging(nạo vét dữ liệu), Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowleadge Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự sau:s
2. 1. Làm sạch dữ liệu (data cleaning & preprocessing)s: Loại bỏ nhiễu và các dữ liệu không cần thiết. 2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xử lý (data cleaning & preprocessing). 3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không đầy đủ (incomplete data), .v.v. 4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý 5. Khai phá dữ liệu(data mining): Là một trong các bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu. 6. Ước lượng mẫu (knowledge evaluation): Quá trình đánh giá các kết quả tìm được thông qua các độ đo nào đó. 7. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng. Hình 1 - Các bước trong Data Mining & KDD
3. 1.1.3. Các chức năng chính của khai phá dữ liệu Data Mining được chia nhỏ thành một số hướng chính như sau: • Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. • Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v. • Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Người ta còn gọi phân lớp là học có giám sát (học có thầy). • Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Người ta còn gọi phân cụm là học không giám sát (học không thầy). • Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. 1.1.4. Ứng dụng của khai phá dữ liệu Data Mining tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể liệt kê ra đây một số ứng dụng điển hình: • Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support) • Điều trị y học (medical treatment) • Text mining & Web mining • Tin-sinh (bio-informatics) • Tài chính và thị trường chứng khoán (finance & stock market)
4. • Bảo hiểm (insurance) • Nhận dạng (pattern recognition) • .v.v. 1.2. CƠ SỞ SỮ LIỆU HYPERTEXT VÀ FULLTEXT 1.2.1. Cơ sở dữ liệu FullText Dữ liệu dạng FullText là một dạng dữ liệu phi cấu trúc với thông tin chỉ gồm các tại liệu dạng Text. Mỗi tài liệu chứa thông tin về một vấn đề nào đó thể hiện qua nội dung của tất cả các từ cấu thành tài liệu đó. Ý nghĩa của mỗi từ trong tài liệu khkông cố định mà tuỳ thuộc vào từng ngữ cảnh khác nhau sẽ mang ý nghĩa khác nhau. Các từ trong tài liệu được liên kết với nhau theo một ngôn ngữ nào đó. Trong các dữ liệu hiện nay thì văn bản là một trong những dữ liệu phổ biến nhất, nó có mặt ở khắp mọi nơi và chúng ta thường xuyên bắt gặp do đó các bài toán về xử lý văn bản đã được đặt ra khá lâu và hiện nay vẫn là một trong những vấn đề trong khai phá dữ liệu Text, trong đó có những bài toán đáng chú ý như tìm kiếm văn bản, phân loại văn bản, phân cụm văn bản hoặc dẫn đường văn bản CSDL full_text là một dạng CSDL phi cấu trúc mà dữ liệu bao gồm các tài liệu và thuộc tính của tài liệu. Cơ sở dữ liệu Full_Text thường được tổ chức như môt tổ hợp của hai thành phần: Một CSDL có cấu trúc thông thường (chứa đặc điểm của các tài liệu) và các tài liệu CSDL Full-Text CSDL có cấu trúc chứa đặc điểm Các tài liệu của các tài liệu Nội dung cuả tài liệu được lưu trữ gián tiếp trong CSDL theo nghĩa hệ thống chỉ quản lý địa chỉ lưu trữ nội dung. Cơ sở dữ liệu dạng Text có thể chia làm hai loại sau: Dạng không có cấu trúc (unstructured): Những văn bản thông thường mà chúng ta thường đọc hàng ngày được thể hiện dưới dạng tự nhiên của con người và nó
5. không có một cấu trúc định dạng nào. VD: Tập hợp sách, Tạp chí, Bài viết được quản lý trong một mạng thư viện điện tử. Dạng nửa cấu trúc (semi-structured): Những văn bản được tổ chức dưới dạng cấu trúc không chặt chẽ như bản ghi các ký hiệu đánh dấu văn bản và vẫn thể hiện được nội dung chính của văn bản, ví dụ như các dạnh HTML, email, Tuy nhiên việc phân làm hai loại cũng không thật rõ ràng, trong các hệ phần mềm, người ta thường phải sử dụng các phần kết hợp lại để thành một hệ như trong cá hệ tìm tin (Search Engine), hoặc trong bài toán tìm kiếm văn bản (Text Retrieval), một trong những lĩnh vực qua tâm nhất hiện nay. Chẳng hạn trong hệ tìm kiếm như Yahoo, Altavista, Google đều tổ chức dữ liệu theo các nhóm và thư mục, mỗi nhóm lại có thể có nhiều nhóm con nằm trong đó. Hệ Altavista còn tích hợp thêm chương trình dịch tự động có thể dịch chuyển đổi sang nhiều thứ tiếng khác nhau và cho kết quả khá tốt. 1.2.2. Cơ sở dữ liệu HyperText Theo từ điển của Đại học Oxford (Oxford English Dictionary Additions Series) thì Hypertext được định nghĩa như sau: Đó là loại Text không phải đọc theo dạng liên tục đơn, nó có thể được đọc theo các thứ tự khác nhau, đặc biệt là Text và ảnh đồ họa (Graphic) là các dạng có mối liên kết với nhau theo cách mà người đọc có thể không cần đọc một cách liên tục. Ví dụ khi đọc một cuốn sách người đọc không phải đọc lần lượt từng trang từ đầu đến cuối mà có thể nhảy cóc đến các đoạn sau để tham khảo về các vấn đề họ quan tâm. Như vậy văn bản HyperText bao gồm dạng chữ viết không liên tục, chúng được phân nhánh và cho phép người đọc có thể chọn cách đọc theo ý muốn của mình. Hiểu theo nghĩa thông thường thì HyperText là một tập các trang chữ viết được kết nối với nhau bởi các liên kết và cho phép người đọc có thể đọc theo các cách khác nhau. Như ta đã làm quen nhiều với các trang định dạng HTML, trong các trang có những liên kết trỏ tới từng phần khác nhau của trang đó hoặc trỏ tới trang khác, và người đọc sẽ đọc văn bản dựa vào những liên kết đó. Bên cạnh đó, HyperText cũng là một dạng văn bản Text đặc biệt nên cũng có thể bao gồm các chữ viết liên tục (là dạng phổ biến nhất của chữ viết). Do không bị hạn chế bởi tính liên tục trong HyperText, chúng ta có thể tạo ra các dạng trình bày mới, do đó tài liệu sẽ phản ánh tốt hơn nội dung muốn diễn đạt. Hơn nữa người đọc có thể chọn cho mình một cách đọc phù hợp chẳng hạn như đi sâu vào một vấn đề mà họ
6. quan tâm. Sáng kiến tạo ra một tậpc cá văn bản cùng với các con trỏ trỏ tới các văn bản khác để liên kết một tập các văn bản có mối quan hệ voiứ nhau với nhau là một cách thực sự hay và rất hữu ích để tổ chức thông tin. Với người viết, cách này cho phép họ có thể thoải mái loại bỏ những băn khoăn về thứ tự trình bày, mà có thể tổ chức vấn đề thành những phần nhỏ, rồi sử dụng kết nối để chỉ ra mối liên hệ giữa các phần nhỏ đó với nhau. Với người đọc cách này cho phép họ có thể đi tắt trên mạng thông tin và quyết định phần thông tin nào có liên quan đến vấn đề mà họ quan tâm để tiêp tục tìm hiểu. So sánh với cách đọc tuyến tính, tức là đọc lần lượt thì HyperText đã cung cấp cho chúng ta một giao diện để có thể tiếp xúc với nội dung thông tin hiệu quả hơn rất nhiều. Theo khía cạnh của các thuật toán học máy thì HyperText đã cung cấp cho chúng ta cơ hội nhìn ra ngoài phạm vi một tài liệu để phân lớp nó, nghĩa là có tính cả đến các tài liệu có liên kết với nó. Tất nhiên không phải tất cả các tài liệu có liên kết đến nó đều có ích cho việc phân lớp, đặc biệt là khi các siêu liên kết có thể chỉ đến rất nhiều loại các tài liệu khác nhau. Nhưng chắc chắn vẫn còn tồni tại tiềm năng mà con người cần tiếp tục nghiên cứu về việc sử dụng các tài liệu liên kết đến một trang để nâng cao độ chính xác phân lớp trang đó. Có hai khái niệm về HyperText mà chúng ta cần quan tâm: Hypertext Document (Tài liệu siêu văn bản): Là một tài liệu văn bản đơn trong hệ thống siêu văn bản. Nếu tưởng tượng hệ thống siêu văn bản là một đồ thị, thì các tài liệu tương ứng với các nút. Hypertext Link (Liên kết siêu văn bản): Là một tham chiếu để nối một tài liệu HyperText này với một tài liệu HyperText khác. Các siêu liên kết đóng vai trò như những đường nối trong đồ thị nói trên. HyperText là loại dữ liệu phổ biến hiện nay, và cũng là loại dữ liệu có nhu cầu tìm kiếm và phân lớp rấ lớn. Nó là dữ liệu phổ biến trên mạng thông tin Internet CSDL HyperText với văn bản dạng “nửa cấu trúc” do xuất hiện thêm các “thẻ “: Thẻ cấu trúc (tiêu đề, mở đầu, nội dung), thẻ nhấn trình bày chữ (đậm, nghiêng, ). Nhờ các thẻ này mà chúng ta có thêm một tiêu chuẩn (so với tài liệu fulltext) để có thể tìm kiếm và phân lớp chúng. Dựa vào các thẻ đã quy định trước chúng ta có thể phân thành các độ ưu tiên khác nhaucho các từ khóa nếu chúng xuất hiện ở những vị trí khác nhau. Ví dụ khi tìm kiếm các tài liệu có nội dung liên quan đến “people “ thì chúng ta đưa từ khóa tìm kiếm là “people”, và các tài liệu có từ khóa “poeple” đứng ở tiêu đề thì sẽ gần với yêu cầu tìm kiếm hơn.
7. Một sơ đồ minh hoạ Hypertext Document như là các nút và các Hypertext Link như là các liên kết giữa chúng So s¸nh ®Æc ®iÓm cña d÷ liÖu Fulltext vµ d÷ liÖu trang web Mặc dù trang Web là một dang đặc biệt của dữ liệu FullText, nhưng có nhiều điểm khác nhau giữa hai loại dữ liệu này. Một số nhận xét sau đây cho thấy sự khác nhau giữa dữ liệu Web và FullText. Sự khác nhau về đặc điểm là nguyên nhân chính dẫn đến sự khác nhau trong khai phá hai loại dữ liệu này (phân lớp, tìm kiếm, ).
8. Một số đối sánh dưới đây về đặc điểm giữa dữ liệu Fulltext với dữ liệu trang đã được trình bày trong [2]. STT Trang web Văn bản thông thường (Fulltext) 1 Là dạng văn bản “nửa cấu trúc”. Văn bản thường là dạng văn bản “phi Trong nội dung có phần tiêu đề và cấu trúc”. Trong nội dung của nó có các thẻ nhấn mạnh ý nghĩa của không có một tiêu chuẩn nào cho ta từ hoặc cụm từ dựa vào đó để đánh giá 2 Nội dung của các trang Web Nội dung của các văn bản thông thường đườn mô tả ngắn gọn, cô thường thường rất chi tiết và đầy đủ đọng, có các siêu liên kết chỉ ra cho người đọc đến những nơi khác có nội dung liên quan 3 Trong nội dung các trang Web có Các trng văn bản thông thường không chứa các siêu liên kết cho phép liên kết được đến nội dung của các liên kết các trang có nội dung liên trang khác với nhau 1.3. KHAI PHÁ DỮ LIỆU VĂN BẢN (TEXTMINING) VÀ KHAI PHÁ DỮ LIỆU WEB (WEBMINING) Như đã đề cập ở trên, TextMining (Khai phá dữ liệu văn bản) và WebMining (Khai phá dữ liệu Web) là một trong những ứng dụng quan trọng của Datamining. Trong phần này ta sẽ đi sâu hơn vào bài toán này. 1.3.1. Các bài toán trong khai phá dữ liệu văn bản 1. Tìm kiếm văn bản a. Nội dung Tìm kiếm văn bản là quá trình tìm kiếm văn bản theo yêu cầu của người dùng. Các yêu cầu được thể hiện dưới dạng các câu hỏi (query), dạng câu hỏi đơn giản nhất là các từ khóa. Có thể hình dung hệ tìm kiếm văn bản sắp xếp văn bản thành hai lớp: Một lớp cho ra những các văn bản thỏa mãn với câu hỏi đưa ra và một lớp không hiển thị những văn bản không được thỏa mãn. Các hệ thống thực tế hiện nay không hiển thị
9. như vậy mà đưa ra các danh sách văn bản theo độ quan trọng của văn bản tuỳ theo các câu hỏi đưa vào, ví dụ điển hình là các máy tìm tin như Google, Altavista, b. Quá trình Quá trình tìm tin được chia thành bốn quá trình chính : Đánh chỉ số (indexing): Các văn bản ở dạng thô cần được chuyển sang một dạng biểu diễn nào đó để xử lý. Quá trình này còn được gọi là quá trình biểu diễn văn bản, dạng biểu diễn phải có cấu trúc và dẽ dàng khi xử lý. Định dạng câu hỏi: Người dùng phải mô tả những yêu cầu về lấy thông tin cần thiết dưới dạng câu hỏi. Các câu hỏi này phải được biểu diễn dưới dạng phổ biến cho các hệ tìm kiếm như nhập vào các từ khóa cần tìm. Ngoài ra còn có các phương pháp định dạng câu hỏi dưới dạng ngôn ngữ tự nhiên hoặc dưới dạng các ví dụ, đối với các dạngnày thì cần có các kỹ thuật xử lý phức tạp hơn. Trong các hệ tìm tin hiện nay thì đại đa số là dùng câu hỏi dưới dạng các từ khóa. So sánh: Hệ thống phải có sự so sánh rõ ràng và hoàn toàn câu hỏi các câu hỏi của người dùng với các văn bản đượcl ưu trữ trong CSDL. Cuối cùng hệ đưa ra một quyết định phân loại các văn bản có độ liên quan gầnvới câu hỏi đưa vào và thứ tự của nó. Hệ sẽ hiển thị toàn bộ văn bản hoặc chỉ một phần văn bản. Phản hồi: Nhiều khi kết quả được trả về ban đầu không thỏa mãn yêu cầu của người dùng, do đó cần phải có qua trình phản hồi để người dùng có thểt hay đổi lại hoặc nhập mới các yêu cầu của mình. Mặt khác, người dùng có thể tương tác với các hệ về các văn bản thỏa mãn yêu cầu của mình và hệ có chức năng cập nhậu các văn bản đó. Quá trình này được gọi là quá trình phản hồi liên quan (Relevance feeback). Các công cụ tìm kiếm hiện nay chủ yếu tập trung nhiều vào ba quá trình đầu, còn phần lớn chưa có quá trình phản hồi hay xử lý tương tác người dùng và máy. Quá trình phản hồi hiện nay đang được nghiên cứu rộng rãi và riêng trong quá trình tương tác giao diện người máy đã xuất hiện hướng nghiên cứu là interface agent. 2. Phân lớp văn bản(Text Categoization) a. Nội dung Phân lớp văn bản được xem như là quá trình gán các văn bản vào một hay nhiều văn bản đã xác định từ trước. Người ta có thể phân lớp các văn bản mộtc ách thủ công, tức là đọc từng văn bản một và gán nó vào một lớp nào đó. Cách này sẽ tốn rất nhiều thời gian và công sức đối với nhiều văn bản và do đó không khả thi. Do vậy mà
10. phải có các phương pháp phân lớp tự động. Để phân lớp tự động người ta sử dụng các phương pháp học máy trong trí tuệ nhân tạo (Cây quyết định, Bayes, k người láng giềng gần nhất) Một trong những ứng dụng quan trọng nhất của phân lớp văn bản là trong tìm kiếm văn bản. Từ một tập dữ liệu đã phân lớp các văn bản sẽ được đánh chỉ số đô ívới từng lớp tương ứng. Người dùng có thể xác định chủ đề hoặc phân lớp văn bản mà mình mong muốn tìm kiếm thông qua các câu hỏi. Một ứng dụng khác của phân lớp văn bản là trong lĩnh vực tìm hiểu văn bản. Phân lớp văn bản có thể được sử dụng để lọc các văn bản hoặc một phần các văn bản chứa dữ liệu cần tìm mà không làm mất đi tính phức tạp của ngôn ngữ tự nhiên. Trong phân lớp văn bản, một lớp có thể được gán giá trị đúng sai (True hay False hoặc văn bản thuộc hay không thuộc lớp) hoặc được tính theo mức độ phụ thuộc (văn bản có môt mức độ phụ thuộc vào lớp). Trong trương hợp có nhiều lớp thì phân loại đúng sai sẽ là việc xem một văn bản có thuộc vào một lớp duy nhất nào đó hay không b. Quá trình Quá trình phân lớp văn bản. tuân theo các bước sau: Đánh chỉ số (Indexing): Quá trình đánh chỉ số văn bản cũng giống như trong quá trình đánh chỉ số của tìm kiếm văn bản. Trong phần này thì tốc độ đánh chỉ số đóng vai trò quan trọng vì một số các văn bản mới có thể cần đươc xử lý trong thời gían thực Xác định độ phân lớp: Cũng giống như trong tìm kiếm văn bản, phân lớp văn bản yêu cầu quá trình diễn tả việc xác định văn bản đó thuộc lớp nào đó như thế nào, dựa trên cấu trúc biểu diễn của nó. Đối với hệ phân lớp văn bản, chúng ta gọi quá trình này là bộ phân lớp (Categorization hoặc classifier). Nó đóng vai trò như những câu hỏi trong hệ tìm kiếm. Nhưng trong khi những câu hỏi mang tính nhất thời, thì bộ phân loại được sử dụng một cách ổn định và lâu dài cho quá trình phân loại. So sánh: Trong hầu hết các bộ phân loại, mỗi văn bản đều được yêu cầu gán đúng sai vào một lớp nào đó. Sự khác nhau lớn nhất đối với quá trình so sánh trong hệ tìm kiếm văn bản là mỗi văn bản chỉ được so sánh với một số lượng các lớp một lần và việcc họn quyết đnịh phù hợp còn phụ thuộc vào mối quan hệ giữa các lớp văn bản.
11. Phản hồi (Hay thích nghi): Quá trình phản hồi đóng vai trò trong hệ phân lớp văn bản. Thứ nhất là khi phân loại thì phải có môt số lượng lớn các văn bản đã được xếp loại bằng tay trước đó, các văn bản này được sử dụng làm mẫu huấn luyện để hỗ trợ xây dựng bộ phân loại. Thứ hai là đối với việc phân loại văn bản này không dễ dàng thay đổi các yêu cầu như trong quá trình phản hồi của tìm kiếm văn bản , người dùng có thể thông tin cho người bảo trì hệ thống về việc xóa bỏ, thêm vào hoặc thay đổi các phân lớp văn bản nào đó mà mình yêu cầu. 3. Một số bài toán khác Ngoài hai bài toán kể trên, còn có các bài toán sau: Tóm tắt văn bản Phân cụm văn bản Phân cụm các từ mục Phân lớp các từ mục Đánh chỉ mục các từ tiềm năng Dẫn đường văn bản Trong các bài toán xử lý vănbản đã nêu ở trên, chúng tra thấy vai trò của biểu diễn văn bản rất lớn, đặc biệt trong các bàit oán tìm kiếm, phân lớp, phân cụm, dẫn đường 1.3.2. Khai phá dữ liệu Web a. Nhu cầu 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). Cùng với sự thay đổi và phát triển hàng ngaỳ 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ôn g tin đối với người sử dụng lại ngày càng khó khăn. Có thể nói nhu cầu tìm kiếm thông tin trên môt CSDL phi cấu trúc đã được phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy với Internet con người đã làm quen với các trang Web cùng với vô vàn các thông tin. 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à sự thấp về giá cả tiêu tốn khi công khai một trang Web trên Internet. So sánh với những dịch vụ khác như mua bản 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
12. 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 trang Web như là cuốn từ điển Bách khoa toàn thư. 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. Có thể nói Internet 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, 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. 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. Các tiện ích này quản lý dữ liệu như các đối tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy đó là: Yahoo, goolel, Alvista, Mặt khác, giả sử chúng ta có các trang Web về các vấn đề Tin học, Thể thao, Kinh tể-Xã hội và xây dựng Căn cứ vào nội dung của các tài liệu mà khách hàng xem hoặc download về, sau khi phân lớp chúng ta sẽ biết khách hàng hay tập trung vào nội dung gì trên trang Web của chúng ta, từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm và ngược lại. Còn về phía khách hàng sau khi phân tích chúng ta cũng biết được khách hàng hay tập trung về vấn đề gì, để từ đó có thể đưa ra những hỗ trợ thêm cho khách hàng đó. Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài toán hay và cần phát triển nghiên cứu hiện nay. b. Khó khăn Hệ thống phục vụ World Wide Web như là một hệ thống trung tâm rất lớn phân bố rộng 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 sự thách thức lớn cho công nghệ Khai phá dữ liệu 1. Web dường như quá lớn để tổ chức thành một 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ữ ở một nơi, , 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 đã đư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.,
13. giả sử kích thước trung bình của mỗi trang là 5-10Kb thì tổng kích thước của nó ít nhất là khoảng 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ể 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. Ví dụ về ngôn ngữ 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 (links), các mã nén (zipcode), số điện thoại) Nói cách khá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 con số khổng lồ các tài liệu trong thư viện thì không được sắp xếp tuân theo một tiêu chuẩn đặc biệt nào, không theo phạm trù, tiêu đề, tác giả, số trang hay nội dung, Đ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ế. 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 , hơn 500.000 trang Web 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ọ.s 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 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 trạm làm việc, 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 đang "mò
14. mẫm"trong "bóng tối" 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 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ê, 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 c. Thuận lợi Bên cạnh những thử thách trên, còn một số lợi thế của trang Web cung cấp cho công việc khai phá Web. 1. Web bao gồm không chỉ có các trang mà còn có cả các hyperlink trỏ từ trang này tới trang khác. Khi một tác giả tạo một hyperlink 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 trang A càng nhiều Hyperlink từ trang khác trỏ đến chứng tỏ trang A quan trọng. Vì vậy số lượng lớn 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. Với những thông tin về địa chỉ URL, địa chỉ IP, một cách hiển thị đa chiều có thể được cấu trúc nên dựa trên CSDL Weblog. Thực hiện phân tích OLAP đa chiều có thể đưa ra N người dùng cao nhất, N trang Web truy cập nhiều nhất, và khoảng thời gian nhiều người truy cập nhất, xu hướng truy cập Web d. Các nội dung trong Webmining Như đã phân tích về đặc điểm và nội dung các văn bản HyperText ở trên, từ đó khai phá dữ liệu Web cũng sẽ tập trung vào các thành phần có trong trang Web. Đó chính là: 1. Khai phá nội dung trang Web (Web Content mining)
15. Khai phá nội dung trang Web gồm hai phần: a. Web Page Content Nghĩa là sẽ sử dụng chỉ các từ trong văn bản mà không tính đến các liên kết giữa các văn bản. Đây chính là khai phá dữ liệu Text (Textmining) b.Search Result Tìm kiếm theo 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 kết quả theo thứ tự dộ gần nhau với nội dung cần tìm kiếm. Đây cũng chính là khai phá nội dung trang Web. 2. Web Structure Mining Khai phá dựa trên các siêu liên kết giữa các văn bản có liên quan. 3. Web Usage Mining a. General Access Partern Tracking: Phân tích các Web log để khám phá ra các mẫu truy cập của người dùng trong trang Web. b. Customize Usage Tracking: Phân tích các mẫu truy cập của người dùng tại mỗi thời điểm để biết xu hướng truy cập trang Web của từng đối tượng người dùng tại mỗi thời điểm khác nhau Web Mining Web Web Web Content Structure Usage Web Page Search General Access Customized Content Result Pattern Usage Các nội dung trong khai phá Web
16. Chương 2. MÁY TÌM KIẾM 2.1. NHU CẦU Như đã đề cập ở phần trên. Internet 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, 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. Đố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. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy đó là: Yahoo, Google, Alvista, M¸y t×m kiÕm lµ c¸c hÖ thèng ®−îc x©y dùng cã kh¶ n¨ng 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õ kho¸), sau ®ã ph©n tÝch vµ t×m kiÕm trong c¬ së d÷ liÖu ®· cã s½n vµ ®−a ra c¸c kÕt qu¶ lµ c¸c trang web cho ng−êi sö 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. 2.2. CẤU TRÚC VÀ CƠ CHẾ HOẠT ĐỘNG 2.2.1. Tổng quan về các hệ tìm kiếm hiện nay Bằng một ví dụ cụ thể, ta xem xét hệ tìm kiếm Google Trong phần này ta đưa ra cái nhìn tổng quan về cách làm việc của một hệ tìm kiếm Google. Phần sau sẽ thảo luận về ứng dụng chính (Crawling, indexing, searching) và cấu trúc dữ liệu mà phần này chưa kịp đề cập. Phần lớn Google được thiết kế bằng C, C++ và chạy tốt trên Solaris hay Linux. Trong Google, Web crawling(download các trang Web) được thực hiện bởi một vài Webcrawler phân tán. Có một máy chủ URL gửi danh sách các URL mà đã được đính kèm tới crawler. Những trang Web được đính kèm đó đựơc gửi tới máy chủ lưu trữ. Máy chủ lưu trữ sẽ nén và lưu trữ các trang vào Repository (Nơi lưu trữ). Mọi trang Web đều có một chỉ số ID kèm theo gọi là DocID. Chức năng
17. Index được được thực hiện bởi Indexer và Sorter. Indexer thực hiện các chức năng sau: Đọc từ Repository , giải nén tài liệu và phân tích chúng. Mỗi tài liệu được được chuyển thành một tập hợp các từ xuất hiện gọi là Hits. Hits ghi các từ, vị trí các từ, xấp xỉ của phông chữ, sự viết hoa thường. Indexer phân bố những Hits thành các bộ gọi là "Barrels". Indexer thực hiện một chức năng quan trọng khác, đó là nó phân tích tất cả những hyperlink trên tất cả các trang và lưu trữ những thông tin quan trọng về chúng vào một file nguồn. File H×nh 2.3_M« h×nh kiÕn tróc cña m¸y t×m kiÕm Google này chứa một lượng đủ lớn các thông tin để xác định mỗi liên kết trỏ từ và trỏ tới trang nào, cùng nội dung của liên kết. Như vậy, Crawler có nhiệm vụ down các trang web về lưu trữ vào respository Indexer đọc từ respository giải nén các tài liệu và phân tích, mã hóa thành Hits, sắp xếp thành "Barrels". Phân tích tất cả các hyperlink lưu trữ vào một file 2.2.2. Cấu trúc của các hệ tìm kiếm Các máy tìm kiếm hiện nay thường được tổ chức thành ba Modul sau: Modul đánh chỉ mục (indexing): Dò tìm các trang Web trên Internet, phân tích chúng rồi lưu vào CSDL. Modul tìm kiếm (searching): Truy xuất các CSDL để trả về danh sách các tài liệu thỏa mãn một yêu cầu người dùng (dưới dạng truy vấn là một tập các từ khóa). Modul giao diện người máy: Lấy kểt quả từ modul tìm kiếm. Sau đây ta đi sâu vào chi tiết của từng modul và nhiệm vụ của chúng
18. a. Modul đánh chỉ mục (Indexing) Modul đánh chỉ mục thực hiện các nhiệm vụ sau 1. Phân tích cú pháp văn bản và đánh chỉ mục toàn bộ các từ khoá trong văn bản (số lần xuất hiện, vị trí xuất hiện) 2. Lập đồ thị liên kết giữa các siêu văn bản (liên kết xuôi và liên kết ngược). 3. Tính toán độ quan trọng – PageRank của tất cả các văn bản dựa vào cấu trúc liên kết siêu văn bản (GoogleTM). Sau đây, ta xem xét chi tiết từng nhiệm vụ a.1. Bộ dò trên Web theo các hyperlink (Web Crawler) Crawler (s): Hầu hết các máy tìm kiếm hoạt động dựa trên các chương trình có tên là Crawler, chương trình này cung cấp dữ liệu (là các trang Web) cho máy tìm kiếm hoạt động. Crawler là các chương trình nhỏ của các máy tìm kiếm làm công việc duyệt Web. Công việc của nó cũng tương tự như công việc của con người truy cập Web dựa vàomối liên kết để đi đến các trang Web khác nhau. Các Crawler được cung cấp các địa chỉ URL ban đầu và sẽ phân tích các liên kết có trong các trang đó và đưa các thông tin về cho bộ phận điều khiển crawler (Crawler control). Bộ phận điều khiển này sẽ quyết định xem liên kết nào sẽ được đi thăm tiếp theo và gửi lại kết quả đó cho Crawler (trong một vài máy tìm kiếm chức năng này của bộ phận điều khiển crawler có thể được crawler thực hiện luôn). Các Crawler cũng chuyển luôn các trang đã tìm thấy đó vào kho chứa các trang (Page Repository), tiếp tục đi thăm các trang Web khác trên Internet cho đến khi các nguồn chứa cạn kiệt. Vậy modul Crawler truy lục các trang lấy từ Mạng, download xuống sau đó các trang đựợc đánh chỉ mục bởi Môdul đánh chỉ mục, sau đó đẩy vào CSDL. Quá trình này cứ lặp đi lặp lại cho đến khi Crawler có quyết định dừng. Để bộ điều khiển quyết định được trang Web nào được đi thăm tiếp theo Một máy tìm kiếm tiêu chuẩn cần xem xét hai vấn đề chính trong modul crawler: - Số các trang Web là rất lớn, nên Crawler không thể down toàn bộ các trang mà chỉ chọn những trang "quan trọng". Vậy những trang như thế nào được coi là quan trọng và độ quan trọng được tính toán như thế nào?
19. - Bởi vì nội dung các trang Web liên tục thay đổi nên sau khi download, crawler phải thường xuyên thăm lại các trang đã được down để cập nhật sự thay đổi đó. Hơn nữa mức độ thay đổi của các trang là khác nhau nên crawler phải cẩn thận xem xét trang nào cần xem lại, trang nào bỏ qua. Vấn đề 1: Độ quan trọng Cho một trang Web P, chúng ta có các cách tính độ quan trọng sau: 1. Có một truy vấn Q. Độ quan trọng của P được định nghĩa là "sự giống nhau về từ ngữ" giữa P và Q 2. Biểu diễn Q và P bởi hai vector n chiều v=(w1, w2, , wn) với wi là biểu thị cho từ thứ i trong bộ từ vựng , cụ thể wi=số lần xuất hiện của từ thứ i. Độ chêch lệch giữa P và Q là giá trị cos của hai vector biểu diễn Gọi độ quan trọng nhận được từ phương pháp tính này là IS(P) 2. Trang nào được nhiều trang khác link đến sẽ quang trọng hơn, nên một cách để tính độ quan trọng của trang P là tính số link đến P Gọi độ quan trọng nhận được từ phương pháp tính này là IB(P) 3. Tính độ quan trọng bởi chính địa chỉ URL của nó. Nếu địa chỉ trang Web nào tận cùng bằng".com" hay có chứa từ "home" sẽ quan trọng hơn Gọi độ quan trọng nhận được từ phương pháp tính này là IL(P) 4. Một phương pháp nữa để tính độ quan trọng là đếm số lần người dùng truy cập vào trang trong một khoảng thời gian nào đó Vậy cuối cùng độ quan trọng của trang P sẽ là sự kết hợp của các độ quan trọng tính theo các cách trên, theo một tỷ lệ nào đó: IC(P)=k1. IS (P)+k2.IB(P)+ k3.IL(P)+k4.IU(P) (với k1,k2,k3,k4 và truy vấn Q là cho trước) Vấn đề 2: Sự cập nhật các trang đã download Có hai chiến lược cho sự cập nhật các trang đã download: 1. Cập nhật theo định kỳ tất cả các trang: crawler sẽ thăm lại tất cả các trang với cùng một tần số f, không tính đến mức độ thường xuyên thay đổi của chúng.Nghĩa là các trang được “đối xử” công bằng bất kể chúng thay đổi ra sao.
20. Cập nhật thường xuyên theo nghĩa là khi down được 10.000 trang chẳng hạn thì sẽ tính lại PageRank, index của word trong URL 2. Cập nhật theo một tỷ lệ: Trang nào càng nhiều thay đổi thì tần suất cập nhật càng lớn. VD: các trang e1, e2, ,en, thay đổi theo thứ tự k1,k2, ,kn lần a.2. Indexing (Quá trình đánh chỉ mục) Indexer Module sẽ tìm hiểu tất cả các từ trong từng trang Web được lưu trữ trong kho chứa các trang, và ghi lại các địa chỉ URL của các trang có chứa mỗi từ. Kết quả sinh ra một bảng chỉ mục rất lớn, và nhờ có bảng chỉ mục này nó có thể cung cấp tất cả các địa chỉ URL của các trang khi có yêu cầu. Hai modul đánh chỉ số (indexer) và collection analysis trên hình 1 làm nhiệm vụ xây dựng các chỉ số khác nhau cho các trang web đã down về. Modul Indexer xây dựng hai loại chỉ số cơ bản: Text(content)Index và H×nh1.2_§å thÞ minh ho¹ c¸c nút ( tài liÖu Hypertext) structor(link) index. và các cạnh nối (link) trong mét tËp tµi liÖu Hypertext Sử dụng 2 loại chỉ số trên và các trang web trong nơi lưu trữ các trang (repository), modul collection analysis đã xây dựng thêm nhiều chỉ sơ hữu ĩch khác. Dưới đây chúng ta mô tả ngắn gọn một vài loại chỉ số, tập trung vào cấu trúc và cách sử dụng của chúng. Link index Để xây dựng chỉ số liên kết (link indext), một phần của bộ dò (Crawler) được mã hóa dưới dạng một sơ đồ với các nút và các cạnh nối, trong đó các nút là các trang Web, các cạnh nối giữa các nút là các liên kết giữa các trang. Chỉ số index sẽ được xây dựng lần theo các nút và các cạnh của sơ đồ. (vẽ hình)
21. Thông thường, thông tin có cấu trúc phổ biến nhất được sử dụng bởi các thuật toán tìm kiếm trong các hệ tìm tin là các thông tin lấy từ các trang có liên kết, chính sơ đồ liên kết trên đã cung cấp một cách hữu hiệu sự truy cập tới các thông tin láng giềng đó. Những sơ đồ nhỏ với hàng trăm thậm chí hàng nghìn nút có thể được biểu diễn bởi bất kỳ một cấu trúc dữ liệu nào, song cùng sự thực hiện đó nhưng với một sơ đồ lớn hơn có hàng triệu nút lại là một thách thức lớn. Text Index Mặc dù kỹ thuật dựa vào liên kết đã được sử dụng để tăng cường chất lượng và độ liên quan giữa các kết quả tìm được, thì sự truy xuất dựa vào từ mục (tìm kiếm các trang có chứa các từ khóa) vẫn là một phương pháp chính để xác định các trang web có liên quan đến truy vấn. Cách đánh chỉ số hỗ trợ truy vấn dựa vào từ mục có thể được thực hiện bằng cách sử dụng bất kỳ phương pháp truy cập truyền thống nào để tìm trên toàn bộ nội dung tài liệu.Máy tìm kiếm sử dụng chỉ mục liên kết ngược (Inverted Index) cho việc biểu diễn tài liệu. Chỉ mục liên kết ngược (Inverted Index) là lựa chọn truyền thống cho cấu trúc chỉ số của các trang Web VÝ dô chóng ta cã 4 văn bản sau: văn bản 1: computer science văn bản 2: computer is about live văn bản 3: to live or not to live Quá trình tạo file Index như sau: - Lấy tÊt c¶ c¸c tõ cã mÆt trong c¶ 4 tµi liÖu - L−u tr÷ chóng theo thø tù a, b, c, - L−u tr÷ c¸c th«ng tin vÒ tµi liÖu (bao gåm m· tµi liÖu, ®Þa chØ URL, tiªu ®Ò, miªu t¶ ng¾n gän ) Kết quả thu đựơc một File Inverted index là một danh sách các thông tin sau: Tõ M· VÞ ®Þa Tiªu Miªu About 2 3 Computer 1 1 computer 2 1
22. Is 2 2 live 3 2 Live 3 6 Live 2 4 Not 3 4 Or 3 3 science 1 2 to 3 1 To 3 5 Tuy nhiên một thuật toán tìm kiếm thường sử dụng thêm những thông tin về sự xuất hiện của từ mục trong trang web, ví dụ từ mục được viết hoa (nằm trong thẻ ), hay từ mục nằm ở phần tiêu đề (nằm trong thẻ và ). Để kết hợp những thông tin này, một trường mới được thêm vào gọi là trường payload(tải trọng), trường này mã hóa các thông tin thêm về sự xuất hiện của các từ mục trong văn bản. Những thông tin này phục vụ cho thuật toán Ranking sau này. Inverted index Inverted index được lưu trữ qua file CSDL các bản ghi.Việc xây dựng một CSDL để lưu trữ Inverted Index cho bộ dữ liệu lớn như tập các trang web trên internet đòi hỏi một kiến trúc phân tán với độ mềm dẻo cao. Trong môi trường Web có hai chiến lược cơ bản cho việc chia các Inverted Index thành một tập các nút khác nhau để có thể lưu trữ phân tán tại nhiều nơi khác nhau. KiÓu thø nhÊt lµ local inverted file (IFL). Trong tổ chức kiểu IFL thì mỗi nút lưu trữ các danh sách inverted index của một tập nhỏ các trang Web khác nhau trong tập các trang Web lưu trữ trong bộ phận lưu trữ (page repository). Khi có yêu cầu tìm kiếm thì bộ phận search query sẽ truyền yêu cầu đi tất cả các nút, mỗi nút sẽ trả lại một danh sách riêng các trang có chứa các từ đang tìm kiếm KiÓu thø hai lµ Global inverted file (GFL). Trong tổ chức kiểu GFL, inverted index được chia theo các từ, vì vậy mỗi một query server lưu trữ danh sách inverted index của một tập nhỏ các từ trong bộ dữ liệu. Ví dụ hệ thống với hai query server A và B, thì A sẽ lưu trữ danh sách inverted index cho tất cả các từ với ký tự bắt đầu từ a đến o, còn B lưu trữ cho các từ còn lại từ p đến
23. z. Vì vậy khi bộ phận search query muốn tìm các trang có chứa từ “people” thì nó sẽ chỉ hỏi server A. Cấu trúc dữ liệu chính Modul Indexer lấy các trang đã được Crawler down về chứa trong Repository, Đánh chỉ sổ lưu vào CSDL. CSDL được tạo ra trong quá trình index. Đây là cấu trúc chính của cơ sở dữ liệu trong hầu hết các máy tìm kiếm: a. Một File Từ khóa gồm các bản ghi, mỗi bản ghi tối thiểu có hai trường : Mã số từ khóa, từ khóa (hình a). Các từ khóa này dược thiết lập trong quá trình Indexing: Đọc File văn bản, tách từ khóa, xem đã có trong file từ khóa chưa. Nếu chưa có tạo ra bản gi mới trong file từ khóa, trong đó có mã số từ khóa và tất nhiên có luôn được mã số. Nếu có rồi thì lấy mã số. Mã số lấy được dùng cho việc tạo ra bản ghi tếp theo. b. File chứa các văn bản quản lý trong hệ thống gồm các bản ghi, mỗi bản ghi cho một văn bản, tối thiểu có các trường là: Mã văn bản, tên văn bản (địa chỉ URL), địa chỉ trong máy hệ thống chứa file văn bản (cache của các trang web đó) (hình b) c. File chứa sự xuất hiện của các từ khóa trong văn bản gồm các bản ghi, mỗi bản ghi có ba trường: mã số văn bản, mã số từ khóa, vị trí xuất hiện từ khóa này trong văn bản (hình c)( Đây chính là file chỉ số liên kết ngược(Inverted index)) Cách tổ chức CSDL: Sử dụng cấu trúc hàm băm _theo các từ vựng Thách thức - Việc xây dựng một file chỉ mục liên kết ngược (inverted index) liên quan đến việc tiền xử lý các trang thành các phần nhỏ, sắp xếp chúng vào các chỉ số từ mục và định vị trí cho chúng, cuối cùng viết ra những phần đã được sắp xếp dưới dạng một tập hợp các danh sách liên kết ngược. Thời gian xây dựng file index không qua khắt khe, tuy nhiên khi làm việc với một tập hợp các trang Web, một số file chỉ số trở nên khó quản lý và yêu cầu nguồn tài nguyên lớn (chẳng hạn như bộ nhớ), và thường cần nhiều thời gian để hoàn thành. Sự so sánh với những hệ tìm tin truyền thống cho thấy, với hệ thống đang nghiên cứu, nơi lưu trữ (repository)chứa 40 triệu trang Web mặc dù chỉ biểu diễn được 4% của tổng các trang Web có khả năng đánh chỉ số, nhưng đã lớn hơn hệ thống tìm tin tiêu chuẩn (TREC-7 colection)là 100GB - Bởi vì nội dung của các trang web thay đổi nhanh chóng, nên việc xây dựng lại file chỉ số là rất cần thiểt cho việc làm mới các trang Web. Một phần công việc của
24. Crawler là cập nhật các trang Web đã down về, song song với công việc này việc xây dựng lại các file chỉ số - Cuối cùng, dạng bộ nhớ dành cho file inverted index cần phải được thiết kế cẩn thận. Một file chỉ số được nén sẽ cải tiến thao tác truy vấn hơn là cả file chỉ số được lưu trữ trong bộ nhớ. Tuy nhiên vấn đề gặp phải là tốn thời gian dành cho việc giải nén a.3. Tính toán đại lượng PageRank Các hệ tìm kiếm có hai đặc tính quan trọng giúp đưa ra kết quả có độ chính xác cao. Đầu tiên, nó sử dụng cấu trúc liên kết của Web để tính toán độ quan trọng cho từng trang Web, (PageRank).Thứ hai, hệ sử dụng liên kết để xếp hạng kết quả (Ranking). Chính sơ đồ các liên kết giữa các trang Web đã cho phép tính toán nhanh chóng đại lượng PageRank. Đại lượng PageRank được định nghĩa như sau: Giả sử trang A có các trang T1,T2, ,Tn trỏ tới. Tham số d là hệ số hãm có giá trị trong khoảng 0 và 1. Chúng ta thường đặt d=0.85. C(A) là số liên kết ra từ trang A. Khi đó PageRank của A được tính như sau: PR(A)=(1-d)+d (PR(T1)/C(T1)+ +PR(Tn)/C(Tn)). Trang V1 RV1/ NV1 Trang V2 Trang U RV1/NVm Trang Vm H×nh 2.2 Vì PageRank của một trang là đại lượng đại diện cho sự phân bổ xác suẩt trên các trang Web trong một tập các trang Web nhất định, do đó tổng các giá trị pagerank của tất cả các trang Web trong tập các dữ liệu có giá trị bằng 1
25. Quá trình tính toán được lặp đi lặp lại cho đến khi hội tụ. Với d=0.85, số vòng lặp =20 với khoảng vài triệu trang. Và để tính PageRank cho 26 triệu trang web với một trạm làm việc vừa phải thì thời gian tiêu tốn tới vài giờ. 2.3. NHƯỢC ĐIỂM CỦA CÁC MÁY TÌM KIẾM 1. Là các hệ tìm kiếm tự động, người sử dụng chưa có vai trò gì trong quá trình tìm kiếm, không có cơ chế phản hồi từ người sử dụng để cập nhật các tham số tìm kiếm nhằm tăng hiệu quả cho lần tìm kiếm sau 2. Coi độ quan trọng của các từ khóa là như nhau, do đó chưa cho phép tính độ quan trọng khác nhau của các từ khóa. Như trong các hệ tìm kiếm lớn như Google, Yahoo, nếu đưa vào từ “System Information” thì hệ số tìm kiếm tất cả các trang Web có liên quan đến 2 từ “System” và “Information”. Nếu người dùng muốn tìm kiếm từ “Computer Story” mà trong đó từ Computer có nghĩa nhiều hơn từ Story (chẳng hạn, từ Computer có trọng số 0.8, story có trọng số 0.2), thì vấn đề đặt ra là cần phải xây dựng một hệ tìm kiếm như vậy 3. Chưa quan tâm đến bản chất của xử lý văn bản, vấn đề từ đồng nghĩa, đa nghĩa Có rất nhiều tài liệu liên quan đến nội dung cần tìm nhưng không chứa các từ khóa đưa vào, mà chỉ chứa các từ đồng nghĩa với chúng và những tài liệu đó sẽ bị bỏ qua trong quá trình tìm kiếm. Vì các máy hầu hết tìm kiếm theo từ khóa, dựa vào việc đánh chỉ mục cho các trang Web(index-base search engine), có thể có hàng trăm tài liệu cùng chứa từ khóa đưa vào, dẫn đến một số lượng lớn tài liệu nhận được từ máy tìm kiếm, mà rất nhiều trong chúng ít hoặc không liên quan đến nội dung cần tìm 2.4. BÀI TOÁN TÌM KIẾM MỚI Hàng ngày có hàng tỷ người truy cập vào Internet và cũng có từng ấy người thực hiện các thao tác tìm kiếm với các máy tìm kiếm khác nhau. Nếu thống kê các thông tin của mỗi lần tìm kiếm này thì chắc chắn chúng ta sẽ được một nguồn thông tin khổng lồ, và nểu biết cách sử dụng chúng thì sẽ làm được rất nhiều công việc hữu ích. Các bài toán tìm kiếm trong các máy tìm kiếm thông thường chỉ đơn giản đáp ứng nhu cầu tìm kiếm thông tin của khách hàng mà chưa biết tận dụng những thông tin từ phía khách hàng qua mỗi lần tìm kiếm. Dưới đây là bài toán đề xuất thêm vào tính năng của các máy tìm kiếm và hướng giải quyết trong tương lai.
26. Bài toán: Căn cứ vào các tài liệu mà khách hàng xem hoặc down về, sau khi phân tích ta biết được khách hàng đó hay tập trung vào các trang có nội dung gì trên tập các trang Web của chúng ta, để từ đó bổ xung thêm nhiều tài liệu mà khách hàng quan tâm và ngược lại. Còn về phía khác hàng sau khi phân tích chúng ta cũng biết được khách hàng hay tập trung về vấn đề gì , từ đó có thêm những hỗ trợ cho khách hàng. Hướng giải quyết: Xây dựng một CSDL về các tài liệu, trong đó có một trường ClassificationID cho biết tài liệu này thuộc lĩnh vực nào dựa trên kết quả đã phân tích trước đó.(Bằng phân lớp) Xây dựng một CSDL về phía khách hàng: Trước khi khách hàng truy cập vào CSDL, yêu cầu đăng ký một account thông tin: tên, tuổi, địa chỉ, chúng ta cũng đưa thêm hai trường quan trọng là nghề nghiệp, trình độ (cho độ chính xác của thông tin là c%). Yêu cầu đăng ký account là tuỳ chọn với khách hàng. Sau đó trong quá trình mỗi lần khách hàng truy cập vào CSDL chúng ta sẽ ghi lại các tài liệu mà khách hàng truy nhập vào bảng thông tin khách hàng. Sau đó dựa vào các thông tin về tài liệu mà khách hàng truy nhập và thông tin về khách hàng, phân tích theo thuật toán cây quyết định để sinh luật cho biết khách hàng khách hàng có nghề nghiệp và trình độ như thế nào thì quan tâm đến lĩnh vực nào với độ tin cậy là ngưỡng c 2.5. KẾT LUẬN
27. Chương 3. BÀI TOÁN PHÂN LỚP 3.1. PHÁT BIỂU BÀI TOÁN Trong tù nhiªn, con ng−êi th−êng cã ý t−ëng chia sù vËt thµnh c¸c phÇn, c¸c líp kh¸c nhau. T−¬ng tù nh− vËy, gi¶i thuËt ph©n líp ®¬n gi¶n chØ lµ mét phÐp ¸nh x¹ c¬ së d÷ liÖu ®· cã sang mét miÒn gi¸ trÞ cô thÓ nµo ®ã, dùa vµo mét thuéc tÝnh hoÆc mét tËp hîp c¸c thuéc tÝnh cña d÷ liÖu. Líp 1 Gi¶i thuËt Líp 2 D÷ ph©n liÖu líp vµo ho¹t ®éng Líp n Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán các chủ đề đã được xác định cho trước vào các văn bản Text đựa trên nội dung của nó. Phân lớp văn bản là công việc được sử dụng để hỗ trợ trong quá trình tìm kiếm thông tin (Inrmation Retrieval), chiết lọc thông tin (Information Extraction), lọc văn bản hoặc tự động dẫn đường cho các văn bản tới những chủ đề xác định trước.Để phân loại văn bản, người ta sử dụng phương pháp học máy có giám sát (supervised learning). Tập dữ liệu được chia ra làm hai tập là tập huấn luyện và tập kiểm tra¸ trước hết phải xây đựng mô hình thông qua các mẫu học bằng các tập huấn luyện, sau đó kiểm tra sự chính xác bằng tập đữ liệu kiểm tra. Hình sau là môt khung cho việc phân lớp văn bản, trong đó bao gồm ba công đoạn chính: công đoạn đầu là biểu diễn văn bản, tức là chuyển các dữ liệu văn bản thành một dạng có cấu trúc nào đó, tập hợp các mẫu cho trước thành một tập huấn luyện. Công đoạn thứ hai là việc sử dụng các kỹ thuật học máy để học trên các mẫu huấn luyện vừa biểu diễn. Như vậy là việc biểu diễn ở công đoạn một sẽ là đầu vào cho công đoạn thứ hai. Công đoạn thứ ba là việc bổ sung các kiến thức thêm vào do người dùng cung cấp để làm tăng độ chính xác trong biểu diễn văn bản hay trong quá trình học máy. Trong công đoạn hai, có nhiều phương pháp học máy được áp dụng, mô hình mạng Bayes, cây quyết định, phương pháp k ngườii láng giềng gần nhất, mạng Neuron, SVM,
28. 3.2. CÁC PHƯƠNG PHÁP BIỂU DIỄN VĂN BẢN 3.2.1. Các phương pháp biểu diễn văn bản trong Cơ sở dữ liệu FullText Tồn tại ba mô hình CSDL FullText điển hình: Mô hình logic, mô hình cú pháp và mô hình Vector a. Mô hình phân tích cú pháp a.1. Quy tắc lưu trữ: - Mỗi văn bản đều phải được phân tích cú pháp và trả lại thông tin chi tiết về chủ đề của văn bản đó. - Sau đó tiến hành Index các chủ đề của từng văn bản. Cách Index trên chủ đề giống như khi Index trên văn bản nhưng chỉ Index trên các từ xuất hiện trong chủ đề. - Các văn bản được quản lý thông qua các chủ đề này để có thể tìm kiếm được khi có yêu cầu, câu hỏi tìm kiếm sẽ dựa trên các chủ đề trên. a.2. Quy tắc tìm kiếm: Câu hỏi tìm kiếm sẽ dựa vào các chủ đề đã được Index. Vậy đầu tiên phải tiến hành Index các chủ đề. Cách Index trên chủ đề giống như Index trên toàn bộ các từ có trong chủ đề đó, Câu hỏi đưa vào có thể được phân tích cú pháp để trả lại một chủ đềvà tìm kiếm trên chủ đề đó
29. Như vậy bộ phận xử lý chính đối với một hệ CSDL xây dựng theo mô hình này chính là hệ thống phân tích cú pháp và đoán nhận nội dung văn bản. a.2. ¦u ®iÓm, nh−îc ®iÓm ¦u ®iÓm Khi đã có sẵn chủ đề thì việc tìm kiếm theo phương pháp này lại khá hiệu quả và đơn giản do tìm kiếm nhanh và chính xác. Đối với những ngôn ngữ đơn giản về mặt ngữ pháp thì việc phân tích trên có thể đạt được mức độ chính xác cao và chấp nhận được. Nh−îc ®iÓm Chất lượng của hệ thống theo phương pháp này hoàn toàn phụ thuộc vào chất lượng của hệ thống phân tích cú phápvà đoán nhận nội dung tài liệu. Trên thực tế, việc xây dựng hệ thống này là rất phức tạp, phụ thuộc vào đặc điểm của từng ngôn ngữ và đa số vẫn chưa đạt đến độ chính xác cao. b. Mô hình Logic Theo mô hình này các từ có nghĩa trong văn bản được Index và nội dung văn bản được quản lý theo các chỉ số Index đó. b.1. Các quy tắc lưu trữ - Mỗi văn bản được Index theo quy tắc: Thống kê các từ có nghĩa trong các văn bản, đó là những từ mang thông tin chính về các văn bản lưu trữ. Index các văn bản đưa vào theo danh sách các từ khoá nói trên. Ứng với mỗi từ khoá trong danh sách sẽ lưu vị trí xuất hiện nó trong từng văn bản và tên văn bản tồn tại từ khoá đó. Ví dụ, có hai văn bản với mã tương ứng là VB1,VB2. “Cộng hòa xã hội chủ nghĩa Việt Nam” (VB1) “ Việt Nam dân chủ cộng hòa” (VB2)
30. Khi đó ta có cách biểu diễn như sau: Từ mục MãVB_Vị trí XH Cộng VB1(1), VB2(5) Hòa VB1(2), VB2(6) Xã VB1(3) hội VB1(4) chủ VB1(5), VB2(4) nghĩa VB1(6) Việt VB1(7), VB2(1) Nam VB1(8), VB2(2) Dân VB2(3) b.2. Các quy tắc tìm kiếm: Câu hỏi tìm kiếm được đưa ra dưới dạng Logic, tức là gồm một tập hợp các phép toán (AND, OR, ) được thực hiện trên các từ hoặc cụm từ. Việc tìm kiếm sẽ dựa vào bảng Index đã tạo ra và kết quả trả lại là các văn bản thoả mãn toàn bộ các điều kiện trên b.3. ¦u ®iÓm Nh−îc ®iÓm ¦u ®iÓm - Tìm kiếm nhanh và đơn giản. Thựcvậy, giả sử cần tìm kiếm từ “computer”. Hệ thống sẽ duyệt trên bảng Index để trỏ đến chỉ số Index tương ứng. Nếu từ “computer” tồn tại trong hệ thống. Việc tìm kiếm này là khá nhanh và đơn giản khi trước đó ta đã sắp xếp bảng Index theo vần chữ cái. Phép tìm kiếm trên có độ phức tạp cấp θ(nlog2n), với n là số từ trong bảng Index. Tương ứng với chỉ số index trên sẽ cho ta biết các tài liệu chứa nó.Như vậy việc tìm kiếm liên quan đến k từ thì các phép toán cần thực ehiện là k*n*log2n, với n là số từ trong bảng Index - Câu hỏi tìm kiếm nhanh và linh hoạt Có thể dùng các kí tự đặc biệt trong câu hỏi tìm kiếm mà không làm ảnh hưởng đến độ phức tạp của phép tìm kiếm. Ví dụ ta tìm “ta” thì kết quả sẽ trả lại các văn bản có chứa các từ “ta”, “tao”, “tay”, là các từ bắt đầu bằng từ “ta” Kí tự % được gọi là kí tự đại diện (wildcard character). Ngoài ra, bằng các phép toán Logic các từ cần tìm có thể tổ chức thành các câu hỏi một cách linh hoạt. Ví dụ: Cần tìm từ [tôi, ta, tao], dấu “[]” sẽ thể hiện việc tìm kiếm trên một trong số nhiều từ trong nhóm. Đây thực ra là một cách thể hiện linh hoạt phép toán OR trong đại số Logic thay vì phải viết là: Tìm các tài liệu có chứa từ “tôi” hoặc từ “ta” hoặc “tao”.
31. Nhược điểm: - Người tìm kiếm phải có chuyên môn trong lĩnh vực tìm kiếm Thực vậy, do câu hỏi đưa vào dưới dạng Logic nên kết quả trả lại cũng có giá trị Logic (Boolean). Một số tài liệu sẽ được trả lại khi thoả mãn mọi điều kiện đưa vào. Như vậy muốn tìm được tài liệu theo nội dung thì phải biết đích xác về tài liệu. - Việc Index các tài liệu là tốn nhiều thời gian và phức tạp. - Tốn không gian để lưu trữ các bảng Index. - Các tài liệu tìm được không được xắp xếp theo độ chính xác của chúng. - Các bảng Index không linh hoạt. Khi các từ vựng thay đổi (thêm, xóa, ) thì chỉ số Index cũng phải thay đổi theo c. Mô hình không gian Vector c.1. Quy tắc lưu trữ Một trong những phương pháp điển hình để biểu diễn văn bản nói chung là sử dụng không gian Vector. Trong cách biểu diễn này, mỗi văn bản được biểu diễn bằng một vector. Mỗi thành phần của Vector là một từ mục riêng biệt trong tập văn bản gốc(corpus)và được gán một giá trị là hàm f chỉ mật độ của từ mục trong văn bản. Chúng ta có thể biểu diễn các văn bản dưới dạng với từ mục là các từ đơn và hàm f biểu diến số lần xuất hiện của chúng, cách biểu diễn này còn gọi là biểu diễn theo túi các từ (bag of words) Chẳng hạn văn bản vb1, nó được biểu diễn bởi một vector V (v1,v2, ,vn) Với vi là số lần xuất hiện của từ khóa thứ i (ti) trong văn bản vb1. Ta xét hai văn bản sau: Computer is not only computer Computer is life Tõ Vector cho v¨n V Computer 2 1 Is 1 1 Life 0 1 Not 1 0 Only 1 0 Có nhiều tiêu chuẩn để chọn hàm f, do đó mà chúng ta có thể sinh ra nhiều giá trị trọng số khác nhau. Sau đây là một vài tiêu chuẩn để chọn hàm f
32. Mô hình Boolean Giả sử có một CSDL gồm m văn bản D={d1,d2, ,dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n từ mục T={t1,t2, ,tn}. Gọi W=(wij) là ma trận trọng số, trong đó wij là giá trị của từ mục ti trong văn bản dj. Mô hình Boolean là mô hình đơn giản nhấ, được xác định như sau: Wij = 0 nếu ti không có mặt trong dj 1 nếu ngược lại Ví dụ chúng ta có hai văn bản sau: Computer is not only computer Computer is life Tõ Vector cho v¨n V Computer 1 1 Is 1 1 Life 0 1 Not 1 0 Only 1 0 Mô hình tần số (Frequency Model) Mô hình tấn số xác định giá trị các số trong ma trận W=(wij) các giá trị là các số dương dựa vào tần số của cá từ suất hiện trong văn bản hoặc tần số xuất hiện của văn bản trong CSDL. Có ba phương pháp phổ biến sau: Phương pháp dựa trên tần số từ mục (TF_Term Frequency) Các giá trị của các từ mục được tính dựa trên số lần xuất hiện của của cá từ mục trong văn bản . Gọi tfij là số lần xuất hiện của từ mục ti trong văn bản dj, khi đó wij được tính bởi công thức: Wij = tfij hoặc wij = 1+log(tfij) hoặc w=tfij. Phương pháp dựa trên nghịch đảo t số văn bản(IDF_ Inverse Document Frequency) Giá trị từ mục được tính bởi công thức sau: m Wij= log =log(m)- log(dfi) dfij
33. Phương pháp TF.IDE Phương pháp này là tổng hợp của hai phương pháp TF và IDF, ma trận trọng số được tính như sau: m Wij = [1+log(tfij)] log ( ) nếu tfij >=1 dfi 0 nếu tfij =0 c.2. Các quy tắc tìm kiếm Các câu hỏi đưa vào được ánh xạ vector Q(q1,q2, ,qm) theo hệ số của các từ vựng là khác nhau. Tức là: Từ vựng càng có ý nghĩa với nội dung cần tìm có hệ số càng lớn. Qi =0 khi từ vựng đó không thuộc danh sách những từ cần tìm. Qi<>0 khi từ vựng đó thuộc danh sách các từ cần tìm và Qi càng lớn thì mức độ liên quan đến nội dung tài liệu càng cao. Tức là hệ thống sẽ ưu tiên hơn đối với các tài liệu có chứa các từ tìm kiếm có hệ số cao. Ví dụ: Nếu nội dung cần tìm có từ “Machine” quan trọng hơn từ “Computer”, thì trong đó vector Q ta có thể đặt qk=2,qh=1 tương ứng với tk=”Machine”, th=”đa số”. Khi đó, cho một hệ thống các từ vựng ta sẽ xác định được các vector tương ứng với từng tài liệu và ứng với mỗi câu hỏi đưa vào ta sẽ có một vector tương với nó với những hệ số đã được xác định từ trước. Việc tìm kiếm và quản lý sẽ được thực hiện trên tài liệu này. Từ cách xác định nội dung các tài liệu và câu hỏi theo các vector trệ cho ta phương pháp tìm kiếm và lưu trữ các tài liệu dạng Full-Text theo cách mới như sau: 1. Mỗi tài liệu được mã hóa bởi một vector 2. Phân loại các tài liệu theo các vector nói trên. 3. Mỗi câu hỏi đưa vào cũng được mã hóa bởi một vector Việc tìm kiếm các tài liệu được thực hiện bằng cách nhân lần lượt từng Vector câu hỏi với vector của từng tài liệu Kết quả trả lại sẽ là mọi tài có liên quan đến câu hỏi tìm kiếm c.3. Ưu, nhược điểm ¦u ®iÓm - Các tài liệu trả lại có thể được sắp xếp theo mức độ liên quan đến nội dung yêu cầu do trong phép thử mỗi tài liệu đều trả lại chỉ số đánh giá độ liên quan của nó đến nội dung yêu cầu. - Việc đưa ra các câu hỏi tìm kiếm là dễ dàng và không yêu cầu người tìm kiếm có trình độ chuyên môn cao về vấn đề đó
34. - Tiến hành lưu trữ và tìm kiếm đơn giản hơn phương pháp Logic. Người tìm kiếm có thể tự đưa ra số các tài liệu trả lại có mức độ chính xác cao nhất Nhược điểm - Việc tìm kiếm tiến hành khá chậm khi hệ thống các từ vựng là lớn do phải tính toán trên toàn bộ các Vector của tài liệu. - Khi biểu diễn các Vector với các hệ số là số tự nhiên làm tăng mức độ chính xác của việc tìm kiếm nhưng làm tốc độ tính toán giảm đi rẩt nhiều do các phép nhân vector phải tiến hành trên các số tự nhiên hoặc số thực, hơn nữa việc lưu trữ các vector sẽ tốn kém và phức tạp - Hệ thống không linh hoạt khi lưu trữ các từ khóa. Chỉ cần một thay đổi rất nhỏ trong bảng từ vựng sẽ kéo theo hoặc là vector hoá lại toàn bộ các tài liệu lưu trữ, hoặc là sẽ bỏ qua các từ có nghĩa bổ sung trong các tài liệu được mã hóa trước đó. Tuy nhiên, với những ưu điểm nhất định sự sai số nhỏ này có thể bỏ qua do hiện tại số các từ có nghĩa được mã hóa khá đầy đủ trước khi tiến hành mã hóa tài liệu. Vì ậy phương pháp Vector vẫn được quan tâm và sử dụng - Một nhược điểm nữa, chiều của mỗi Vector theo cách biểu diễn này là rất lớn, bởi vì chiều của nó được xác định bằng số lượng các từ khác nhau trong tập hợp văn bản. Ví dụ số lượng các từ có thể có từ 103 đến 105 trong tập hợp các văn bản nhỏ, còn trong tập hợpc ác văn bản lớn thì số lượng sẽ nhiều hơn, đặc biệt trong môi trường Web Cách khắc phục: Có một số phương pháp giảm bớt số chiều của Vector được áp dụng. Một phương pháp đơn giản và hiệu quả là loại bỏ các từ dừng (stop words). Từ dừng là các từ dùng để biểu diễn cấu trúc câu chứ không biểu đạt nội dung văn bản, ví dụ như các từ nối, các giới từ Những từ như vậy xuất hiện rất nhiều trong văn bản nhưng lại không liên quan đến chủ đề và nội dung văn bản. Do đó chúng ta có thể loại bỏ các từ này đi để làm giảm được số chiều của các vector biểu diễn mà lại không làm ảnh hưởng gì đến hiệu quả tìm kiếm. Một số ví dụ về các từ dùng TiÕng ViÖt TiÕng Anh Vµ a HoÆc the Còng do about
35. 3.2.2. Các phương pháp biểu diễn văn bản trong Cơ sở dữ liệu HyperText Trong chương I chúng ta đã nêu ra những khó khăn trong việc tìm kiếm dữ liệu Web và sự khác nhau giữa cấu trúc một văn bản truyền thống với một văn bản HyperText Chính v× nh÷ng khã kh¨n gÆp ph¶i nh− vËy mµ viÖc biÓu diÔn d÷ liÖu trong c¸c m¸y t×m kiÕm lµ rÊt quan träng. BiÓu diÔn c¸c trang web nh− thÕ nµo ®Ó cã thÓ l−u tr÷ ®−îc mét sè l−îng khæng lå c¸c trang web ®ã ®Ó m¸y t×m kiÕm cã thÓ thùc hiÖn viÖc t×m kiÕm nhanh chãng vµ ®−a ra c¸c kÕt qu¶ chÝnh x¸c cho ng−êi sö dông? a. Biểu diễn văn bản HyperText trong các máy tìm kiếm (inverted index) Modul Indexer lấy các trang đã được Crawler down về chứa trong Repository, Đánh chỉ sổ lưu vào CSDL. CSDL được tạo ra trong quá trình index. Đây là cấu trúc chính của cơ sở dữ liệu trong hầu hết các máy tìm kiếm: - Một File Từ khóa gồm các bản ghi, mỗi bản ghi tối thiểu có hai trường : Mã số từ khóa, từ khóa. Các từ khóa này dược thiết lập trong quá trình Indexing - File chứa các văn bản quản lý trong hệ thống gồm các bản ghi, mỗi bản ghi cho một văn bản, tối thiểu có các trường là: Mã văn bản, tên văn bản (địa chỉ URL), địa chỉ trong máy hệ thống chứa file văn bản (cache của các trang web đó) - File chứa sự xuất hiện của các từ khóa trong văn bản gồm các bản ghi, mỗi bản ghi có ba trường: mã số văn bản, mã số từ khóa, vị trí xuất hiện từ khóa này trong văn bản Ưu điểm: Biểu diễn được vị trí xuất hiện của các từ (Biết được từ khóa xuất hiện trong các loại thẻ khác nhau, xuất hiện ở tiêu đề hay thân văn bản). Lưu trữ được thông tin quan trọng của các từ khóa. Nhược điểm: Chưa biểu diễn được tấn số xuất hiện của các từ khóa. Dẫn đến thiếu chức năng tìm kiếm trangWeb theo nội dung b. Biểu diễn văn bản HyperText theo mô hình Vector Trong luận án tiến sỹ, tác giả Séan Slattery [May 2002_CMU-CS-02-142] đã đưa ra 4 cách biểu diễn theo mô hình Vector cho tài liệu HyperText Cách 1 Bỏ qua tất cả các thông tin liên kết giữa các tài liệu láng giềng mà chỉ biểu diễn riêng nội dung tài liệu đang cần biểu diễn. Đây là cách biểu diễn theo “túi các từ”.
36. Nếu khẳng định được nội dung các tài liệu láng giềng là hoàn toàn độc lập với lớp thì cách biểu diễn này là sự lựa chọn tốt. Thực tế là các tài liệu láng giềng cung cấp khá nhiều thông tin hữu ích cho việc phân lớp, do vậy cách biểu diễn này là không hiệu quả. Cách 2 Cách thức đơn giản nhất nhằm sử dụng nội dung các tài liệu láng giềng là kết hợp nội dung tài liệu cần biểu diễn với nội dung mọi tài liệu láng giềng của nó để tạo ra một “super_document”. Khi đó, thành phần vector biểu diễn chính là tần suất xuất hiện của từ khóa trong “super_document”. Hạn chế của cách biểu diễn này chính là việc xóa nhòa phân biệt tài liệu đang xét với láng giềng của nó, và vì thế tạo nên nhiều lộn xộn khi phân lớp. Cách biểu diễn này chỉ tốt trong trường hợp các tài liệu được trỏ tới có cùng chủ đề với tài liệu cần phân lớp. Cách 3 Trong cách biểu diễn này, vector biểu diễn được chia thành hai phần: Phần đầu biểu diễn các từ khóa trong chính tài liệu cần phân lớp, phần sau biểu diễn các từ khóa xuất hiện trong tất cả các tài liệu láng giềng với nó. Cách biểu diễn này khắc phục được nhược điểm của cách biểu diễn trước đó là tránh làm mờ nhạt tài liệu đích với các tài liệu láng giềng. Nếu các tài liệu láng giềng hữu ích cho việc phân lớp thì có thể dễ dàng truy cập đến nội dung của chúng. Tuy nhiên cách biểu diễn này có nhược điểm là số chiều của Vector lớn. Cách 4 Cách biểu diễn này được thể hiện qua các nội dung sau: - Tìm số lượng trang láng giềng trong toàn bộ văn bản hypertext đang xem xét, giả sử có d là số lượng láng giềng. - Cấu trúc vector biểu diễn thành d+1 phần: Phần đầu tiên biểu diễn trực tiếp tài liệu cần phân lớp. Từ phần thứ 2 đến phần d+1 biểu diễn các tài liệu láng giềng, mỗi phần tương ứng với một láng giềng. Dễ nhận thấy vector nhận được là rất lớn và mặt khác, lại không tuân theo một quy tắc duy nhất. Tồn tại nhiều cách chọn thứ tự từ phần thứ 2 trở đi. Chính vì sự đa dạng trong cách biểu diễn của phương pháp này đã gây khó khăn trong việc lựa chọn mẫu dữ liệu để xây dựng Qua các cách biểu diẽn trên, chúng ta đưa ra một số nhận xét về cách biểu diễn văn bản HyperText theo mô hình Vector như trình bày dưới đây.
37. Ưu điểm: - Khai thác được thông tin tiềm năng của các siêu liên kết. - Biểu diễn được tần số xuất hiện của các từ, nên có khả năng thực hiện chức năng tìm kiếm văn bản theo “Độ gần nhau về nội dung” Nhược điểm : - Không biểu diễn được vị trí xuất hiện của các từ. Dẫn đến bỏ qua các thông tin để lấy được độ quan trọng của từ khóa, như nếu từ khóa xuất hiện ở tiêu đề hay trong các thẻ in đậm sẽ quan trọng hơn ở các vị trí khác - Số chiều của Vector là rất lớn III 2.2.3 Biểu diễn văn bản HyperText theo mô hình quan hệ Biểu diễn văn bản theo mô hình quan hệ là cách biểu diễn tự nhiên cho văn bản HyperText. Chúng ta dễ dàng cấu trúc một quan hệ nhị phân (mối liên kết giữa các văn bản) mà đối số thứ nhất là tên của tài liệu có chứa các Hyperlink và đối số thứ 2 là tên của tài liệu được trỏ tới. a) Quan hệ là gì Để hiểu được những ưu thế của học quan hệ (relational learning), trước tiên ta so sánh chúng với những thuật toán định đề (propositional algorithms) mà làm việc với những ví dụ hay thực thể cô lập. Mọi điều mà học định đề cần biết về các ví dụ huấn luyện chỉ là các miêu tả hay thông tin về chính ví dụ đó. Hơn nữa khi thực hiện phân lớp cho một ví dụ, học định đề cũng chỉ quan tâm đến thông tin của chính ví dụ đó mà không quan tâm đến mối liên hệ giữa ví dụ đó với các ví dụ khác. Biểu diễn quan hệ bao gồm cả biểu diễn định đề (như biểu diễn theo mô hình vector, túi các từ (bag of word), tập hợp các từ (set of word)) cùng với các thông tin về mối quan hệ giữa các ví dụ với nhau. Chẳng hạn, nếu ví dụ huấn luyện của chúng ta là people , biểu diễn định đề chỉ chỉ mô tả các thông tin như tên, tuổi, công việc, lương, của từng người, trong khi đó biểu diễn quan hệ sẽ biểu diễn tất cả những thông tin trên cộng thêm một số thông tin khác nữa, ví dụ như mối quan hệ giữa ông chủ-người làm thuê hay mối quan hệ hôn nhân. Như vậy rõ ràng rằng một biểu diễn quan hệ cho ta một cơ hội để tìm kiếm toàn bộ không gian giàu có của các mối quan hệ. Nếu chúng ta tin tưởng rằng các ví dụ liên quan có thể là nguồn thông tin hữu ích cho sự phân lớp một vài ví dụ, thì cách biểu diễn quan hệ là phù hợp, còn ngược lại, các ví dụ liên quan không cung cấp thêm
38. thông tin nào cần thiết thì cách biểu diễn quan hệ (relation representation) không thể nào tốt hơn cách biểu diễn định đề (proposition representation) Biểu diễn quan hệ trong cho HyperText Các quan hệ : Link_to (page, page): Mối quan hệ này thể hiện các siêu liên kết (hyperlink) tham chiếu đến cấu trúc giữa các trang trong toàn bộ văn bản Web. Chúng ta có thể biểu diễn rằng trang 15 chứa siêu liên kết tham chiếu đến trang 37 như sau: link_to (page15, page37). Has_word (page): Cung cấp thông tin về nội dung của mỗi trang Web. Chúng ta sẽ chỉ biểu diễn những từ mà ta quan tâm (hay sau này sẽ chọn làm từ khóa). Chẳng hạn has_computer(A) có nghĩa là trang A có chứa từ computer. Ta có thể biểu diễn phủ định: not(link_to (page15, page37)) có nghĩa là page15 không liên kết với page17, còn not(has_computer(A) có nghĩa là trang A không có chứa từ computer Ví dụ: Có hai trang Web A và B sau: A B List Jame Vector Common Paul Link Giả sử A là trang chủ của sinh viên của tập hợp các trang Web của một trường đại học Khi đó trang A được biểu diễn như sau: A:- has_engine(A), has_list(A), has_vector(A), link_to(B,A), has_jame(B), has_link(B), has_paul(B), not(has_home(A)) Và nếu bằng ngôn ngữ thì ta có thể dịch ra thành luật như sau: Một trang mà chứa các từ khóa list, vector, common nhưng không chứa từ khóa home, và được liên kết bởi trang có chứa các từ jame, paul, link thì đó là trang chủ của sinh viên
39. 3.3. CÁC PHƯƠNG PHÁP HỌC MÁY 3.3.1. Thuật toán phân lớp Bayes Thuật toán phân lớp Bayes là một trong những thuật toán phân lớp điển hình nhất trong khai thac dữ liệu và tri thức. Ý tưởng chính của thuật toán là tính xác suất có sau của sự kiện c thuộc lớp x theo sự phân loại dựa trên xác suất có trước của sự kiện c thuộc lớp x trong điều kiện T p(c | x, τ) = Σ p(c | x,T) p(T |⎯x) T in τ Gọi V là tập tất cả các từ vựng. Giả sử có N lớp tài liệu: C1, C2, ,Cn Mỗi lớp Ci có xác suất p(Ci) và ngưỡng CtgTshi. Gọi p(C| Doc) là xác suất để tài liệu Doc thuộc lớp C. Cho một lớp C và một tài liệu Doc, nếu xác suất p(C|Doc) tính được lớn hơn hoặc bằng giá trị ngưỡng của C thì tài liệu Doc sẽ thuộc vào lớp C. Tài liệu Doc được biểu diễn như một vector có kích thước là số từ khoá trong tài liệu. Mỗi thành phần chứa một từ trong tài liệu và tần xuất xuất hiện của từ đó trong tài liệu. Thuật toán được thực hiện trên tập từ vựng V, vector biểu diễn tài liệu Doc và các tài liệu có sẵn trong lớp, tính toán p(C|Doc) và quyết định tài liệu Doc sẽ thuộc lớp nào. Xác suất p(C | DOC) được tính theo công thức sau: X¸c suÊt p(C | Doc) ®−îc tÝnh theo c«ng thøc sau: Với:
40. Trong ®ã: |V| : sè l−îng c¸c tõ trong tËp V Fj : tõ kho¸ thø j trong tõ vùng TF(Fj | Doc) : Tần xuất của từ Fj trong tài liệu Doc (bao gồm cả từ đồng nghĩa) TF(Fj | C) : Tần xuất của từ Fj trong lớp C (số lần Fj xuất hiện trong tất cả các tài liệu thuôc lớp C) P(Fj | C) : Xác suất có điều kiện để từ Fj xuất hiện trong tài liệu của lớp C Công thức F(Fi | C) được tính sử dụng ước lượng xác suất Laplace. Sở dĩ có số 1 trên tử số của công thức này để tránh trường hợp tần suất của từ Fi trong lớp C bằng 0, khi Fi không xuất hiện trong lớp C. Để giảm sự phức tạp trong tính toán và giảm thời gian tính toán, ta để ý thấy rằng, không phải tài liệu Doc đã cho đều chứa tất cả các từ trong tập từ vựng V. Do đó, TF(Fi | DOC) =0 khi từ Fi thuộc V nhưng không thuộc tài liệu Doc, nên TF(Fj, Doc) ta có, (P(Fj | C)) = 1. Như vậy công thức (1) sẽ được viết lại như sau: Với:
41. Như vậy trong quá trình phân lớp không dựa vào toàn bộ tập từ vựng mà chỉ dựa vào các từ khóa xuất hiện trong tài liệu Doc. 3.3.2. Thuật toán k-người láng giềng gần nhất. ThuËt to¸n ho¹t ®éng kh«ng dùa vµo tËp tõ vùng. Tuy nhiªn, nã vÉn sö dông ng−ìng CtgTsh, và thực hiện theo các bước như đã đề cập ở trên. Đó là tiến hành ngẫu nhiên k tài liệu và tính xác suất p(C|Doc) dựa trên sự giống nhau giữa tài liệu Doc và k tài liệu được chọn. Xác suất p(C| Doc) được tính theo công thức sau: Trong ®ã: n : Số lớp k : Số tài liệu được chọn để so sánh P(Ci | Dj ) : Có giá trị 0 hoặc 1, cho biết tài liệu Dj có thuộc lớp Ci không. Sở dĩ có giá trị này vì một tài liệu có thể thuộc hơn một lớp Sm(Doc,Dj) xác định mức độ giống nhau của tài liệu Doc với tài liệu được chọn Dj , được tính bằng cos của góc giữa hai Vector biểu diễn taì liệu Doc và tài liệu được chọn Dj. Cách biểu diễn các tài liệu trong thuật toán này hoàn toàn tương tự như trong thuật toán phân lớp Bayes thứ nhất, nghĩa là cũng gồm Fi từ khóa và tấn xuất Xi tương ứng. Trong c«ng thøc (4): Xi lµ tÊn xuÊt cña tõ kho¸ thø i (dùa trªn sè tõ ®ång nghÜa xuÊt hiÖn trong tµi liÖu Doc) Yi lµ tÇn xuÊt cña tõ thø i (dùa trªn sè tõ ®ång nghÜa xuÊt hiÖn trong tµi liÖu Di)
42. 3.3.3. Phân lớp dựa vào cây quyết định Học cây quyết định là phươgn pháp được sử dụng rộng rãi cho việc học quy nạp từ một mẫu lớn. Đây là phương pháp xấp xỉ hàm mục tiêu có giá trị rời rạc. Mặt khác, cây quyết định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng tri thức là các luật If-then. Trong các thuật toán học cây quyết định thì ID3 và C4.5 là hai thuậta toán nổi tiếng nhất. Sau đây là nội dung thuật toán ID3. ID3 (Example, Target attributes, Attributes) 1.Tạo một nút gốc Root cho cây quyết định 2. Nếu toàn bộ Examples đều là các ví dụ dương, tả lại cây Root một nút đơn, với nhãn +. 3. Nếu toàn bộ Examples đều là các ví dụ âm, trả lại cây Root một nút đơn, với nhãn -. 4. Nếu Attributes là rỗng thì trả lại cây Root một nút đơn với gàn nhãn bằng giá trị phổ biến nhất của Target_attribute trong Example. 5. Ngược lại Begin 5.1. A<= thuộc tính từ tập Attribute mà phân loại tốt nhất tập Examples 5.2. Thuộc tính quyết định cho Root<=A 5.3. For mỗi giá trị có thể có vi của A 5.3.1. Cộng thêm một nhánh cây con ở dưới Root, phù hợp với biểu thức kiểm tra A=vi. 5.3.2. Đặt Examplesvi là một tập con của tập các ví dụ có giá trị vi cho A 5.3.3. Nếu Examplesvi rỗng -Dưới mỗi nhánh mới thêm một nút lá với nhẵn bằng giá trị phổ biến nhất của Target_attribute trong tập Examples -Ngược lại thì dưới nhánh mới này thêm một cây con ID3(Examples, target_attribute, Attribute-{A}). End Return Root.
43. Thuộc tính tốt nhất là thuộc tính có độ lấy thông tin lớn nhất. Phương pháp học máy dùng cây quyết định và dựa trên cây quyết định là rất hiệu quả bởi vì nó có thể làm việc được với một số lượng lớn các thuộc tính, và hơn nữa từ cây quyết định có thể rút ra được một hệ thống luật học được 3.3.4. Thuật toán học quan hệ FOIL a. Khái niệm mệnh đề Horn (Horn Clause) Mệnh đề Horn là các mệnh đề có nhiều nhất một literal dương, có dạng như sau: H \/ (-L1)\/ (-L2)\/ \/ (-Ln)) Trong đó H, L1,L2, ,Ln gọi là các literal dương, còn –L1,-L2, -Ln gọi là các literal âm. Hay viết dưới dạng luật: ( L1^L2^ ^Ln)=>H. Dạng này được gọi là luật First_Order L1,L2, Ln gọi là tập các tiền điều kiện. H gọi là kết luận. VD về các luật First_Order: If Parents(x,y) then Ancestor (x,y) If (Parents(x,z) ^ Ancestor(z,y) ) then Ancestor(x,y). Trong đó Parents, Ancestor, gọi là các predicate b.Thuật toán Foil FOIL ®−îc ®Ò xuÊt vµ ph¸t triÓn bëi Quinlan (Quinlan, 1990). FOIL häc c¸c tËp d÷ liÖu chØ bao gåm hai líp, lớp các ví dụ “d−¬ng” và ví dụ “âm”. FOIL häc m« t¶ líp ®èi víi líp “d−¬ng”. Đầu vào của Foil gồm các tiền điều kiện và các kết luận. . Đầu ra là một tập các luật sinh từ các tiền điều kiện và các kết luận đó. Mỗi bước Foil sẽ thêm một literal vào các tiền điều kiện của luật đang huấn luyện. Thuật toán sử dụng hàm Foil_Gain để tính toán lựa chọn một literal trong tập các literal ứng cử FOIL lµ m« h×nh häc m¸y kh«ng t¨ng trong thuËt to¸n “leo ®åi” sö dông metric dùa theo lý thuyÕt th«ng tin x©y dùng mét luËt bao trïm lªn d÷ liÖu. Trong Foil có hai trạng thái chính : 1. separate stage (trạng thái phân tách) : Bắt đầu một trạng thái mới
44. 2. Conquer State (trạng thái chế ngự): Kết hợp các literal để xây dựng thân của mệnh đề. Pha “t¸ch rêi” cña thuËt to¸n b¾t ®Çu tõ luËt míi trong khi pha “chÕ ngù” x©y dùng mét liªn kÕt c¸c literal lµm th©n cña luËt. Mçi luËt m« t¶ mét tËp con nµo ®ã c¸c vÝ dô d−¬ng vµ kh«ng cã vÝ dô ©m. L−u ý r»ng, FOIL cã hai to¸n tö: b¾t ®Çu mét luËt míi víi th©n luËt rçng vµ thªm mét literal ®Ó kÕt thóc luËt hiÖn t¹i. FOIL kÕt thóc viÖc bæ sung literal khi kh«ng cßn vÝ dô ©m ®−îc bao phñ bëi luËt, vµ b¾t ®Çu luËt míi ®Õn khi tÊt c¶ mçi vÝ dô d−¬ng ®−îc bao phñ bëi mét luËt nµo ®ã. C¸c vÝ dô d−¬ng ®−îc phñ bëi mÖnh ®Ò sÏ ®−îc t¸ch ra khái tËp d¹y vµ qu¸ tr×nh tiÕp tôc ®Ó häc c¸c mÖnh ®Ò tiÕp theo víi c¸c vÝ dô cßn l¹i, vµ kÕt thóc khi kh«ng cã c¸c vÝ dô d−¬ng thªm n÷a. Sau đây là thiết kế bước 1 của FOIL: 1.Gọi POS là tập các ví dụ dương. 2. Gọi NEG là tập các ví dụ âm 3. Đặt NewClauseBody bằng rỗng 4. Trong khi POS chưa rỗng thực hiện: Separate: (Bắt đầu một luật mới) 5. Loại khỏi POS tất cả những ví dụ thoả mãn NewClauseBody. 6. Đặt lại NEG là tập các ví dụ âm ban đầu 7. Đặt lại NewClauseBody bằng rỗng Trong khi NEG chưa rỗng thực hiện. . Conquer (Xây dựng thân mệnh đề) 8. Chọn Literal L 9. Kết hợp vào NewClauseBody. 10. Loại khỏi NEG những ví dụ mà không thoả mãn L. FOIL sö dông thuËt to¸n leo ®åi ®Ó bæ sung c¸c literal víi th«ng tin thu ®−îc lín nhÊt vµo mét luËt. Víi mçi biÕn ®æi cña mét kh¼ng ®Þnh P, FOIL ®o l−îng th«ng tin ®¹t ®−îc. §Ó lùa chän literal víi th«ng tin ®¹t ®−îc cao nhÊt, nã cÇn biÕt bao nhiªu bé d−¬ng vµ ©m hiÖn t¹i ®−îc b¶o ®¶m bëi c¸c biÕn ®æi cña mçi kh¼ng ®Þnh ®−îc x¸c ®Þnh theo c¸ch dµn tr¶i.
45. Công thức tính infortmaion gain của Foil là: ++ Gain(Literal)=T *(log2(P1/P1+N1) - log2(P0/P0+N0)) P0 và N0 là số ví dụ dương và âm trước khi thêm một literal L vào mệnh đề P1 và N1 là số ví dụ dương và âm sau khi thêm literal L vào mênh đề. T++ là số ví dụ dương cố định cả trước và sau khi thêm literal .(nghĩa là số ví dụ đúng với cả hai luật R và R’_là R sau khi đã thêm vào literal L) Sau đây là một ví dụ minh họa cho thuật toán FOIL. Ta muốn học mối quan hệ Grandaughter(x,y) từ các quan hệ (Predicate) Grandaughter, Father, Mail, Femail và các hằng số: Victor, Sharon, Bob, Tom. Tập ví dụ: Là những giả định liên quan đến các Predicate Grandaughter, Father, Mail, Femail và các hằng số Victor, Sharon, Bob, Tom, trong đó có các ví dụ dương là Grandaughter(Victor, Sharon), Father (Sharon, Bob), Father(Tom, Bob), Femail(Sharon), Father(Bob, Victor). Các ví dụ còn lại là âm (Chẳng hạn như -Grandaughter(Tom,Bob),-Father(Victor, Victor), ). Để chọn các literal cho luật, FOIL xét các cách kết hợp khác nhau của các biến x,y,z,t với các hằng số ở trên. Chẳng hạn bước khởi đầu khi luật chỉ là : - Bước 1: Luật khởi đầu: Grandaughter (x,y) Å Sự kết hợp {x/Bob, y/Sharon}sẽ cho ta một ví dụ dương vì trong dữ liệu huấn luyện Grandaughter(Bob, Sharon) là đúng. Còn 15 cách kết hợp còn lại sẽ tương ứng với các ví dụ âm vì không tìm thấy sự xác nhận tương ứng trong tập huấn luyện - Mỗi trạng thái tiếp theo, luật được hình thành dựa trên tập các kết nối mà cho ra các ví dụ dương, âm. Khi mỗi literal được thêm vào luật, tập các ví dụ âm dương sẽ thay đổi. Chẳng hạn xét literal tiếp theo để đề cử vào luật là Father (y,z), thì thay ví kết nối {x/Bob,y/Sharon} ở trên, kết nối {x/ Bob, y/Sharon,z/ Bob} mới tưong ứng với một ví dụ dương. Tại mỗi bước, số ví dụ âm, dương sẽ được tính toán để có được độ lấy thông tin Foil_Gain (L,R).
46. CHƯƠNG 4. HỆ THỐNG THỬ NGHIỆM 4.1. MỘT SỐ CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN Hệ thống thử nghiệm được xây dựng dựa trên sự kết hợp những ưu điểm của các giải pháp trong các công trình nghiên cứu về vấn đề tìm kiếm và phân lớp văn bản trước đây. Sau đây là nội dung và kết quả của các công trình nghiên cứu 1 [Séan Slattery (May 20002_CMU-CS-02-142)] Luận án tiến sỹ ”HyperText Classification” Trong luận án tiến sĩ của mình, tác giả đã so sánh các thuật toán học máy áp dụng cho phân lớp trang Web cùng với các cách biểu diễn tương ứng, đó là: 1. Dùng Naïve Bayes với cách biểu diễn tài liệu thành một túi các từ (bag of words) 2. Dùng k người láng giềng gần nhất với mô hình tấn số cho biểu diễn trang Web (TF-IDF) 3. Thuật toán FOIL với cách biểu diễn thành tập các từ (set of words) cho mỗi tài liệu (không tính đến các liên kết trong mỗi tài liệu) 4. Thuật toán FOIL với cách biểu diễn thành tập các từ (set of words) và có tính đến các thông tin liên kết trong các tài liệu Tác giả đã cài đặt và thử nghiệm và đưa ra kết quả, với tiêu chuẩn đánh giá là Độ hồi tưởng(recall)và Độ chính xác( Precision) Cách tiếo cận 4 ưu điểm hơn cả, cho độ hồi tưởng và độ chính xác cao hơn hẳn. Tiếp đến, tác giả đã xây dựng một bộ phân lớp HyperText mới sử dụng thuật toán FOIL_PILES với cách biểu diễn văn bản theo mô hình quan hệ. 2. [Đoàn Sơn] Luận văn thạc sĩ ”Phương pháp sử dụng Logic mờ và ứng dụng trong khai phá dữ liệu FullText” Trong luận văn này, tác giả thực hiện phân lớp văn bản sử dụng cách biểu diễn văn bản bằng phương pháp sử dụng Logic mờ và ứng dụng thuật toán học cây quyết định. Với cách giải quyết bài toán như vậy đã cho ta thấy một số ưu điểm: Sử dụng các khái niệm mờ đã làm giảm số chiều của các thuộc tính, dẫn đến làm giảm thời gian tính toán khi học cây quyết định.
47. Tuy nhiên cách biểu diễn này còn có một số mặt hạn chế, đó là việc con người có thể sẽ tốn nhiều công sức cho việc xây dựng chủ đề, các khái niệm và mối liên quan giữa chúng. 3. [Bùi Quang Minh] “Máy tìm kiếm Vietseek”. Báo cáo kết quả nghiên cứu thuộc đề tài khoa học đặc biệt cấp ĐHQGHN mã số QG 02-02. Trong máy tìm kiếm Vietseek, các văn bản được tổ chức thành cơ sở dữ liệu. Vietseek đã xây dựng được cả ba loại chỉ mục (TextIndex, StructureIndex và UtilityIndex). Cơ sở dữ liệu Vietseek được chia thành hai phần: Phần 1: Dữ liệu về văn bản Web, Domain, Word được lưu trữ trong các bảng của CSDL mySQL Phần 2: Dữ liêu về chỉ mục (index) được lưu trữ riêng và có cơ cấu riêng. Do phần này đòi hỏi tốc độ cao nên không lưu trữ trong CSDL MySql mà lưu trữ trong 300 file nhị phân khác nhau. Vietseek thực hiện tìm kiếm theo cụm từ đưa vào và trả về các văn bản có chứa các cụm từ khóa đó chứ chưa thực hiện phân lớp 4. [Phạm Thị Thanh Nam] Luận văn Thạc sỹ “Một số giải pháp cho bài toán tìm kiếm trong CSDL HyperText”. Từ CSDL chỉ mục đã được xây dựng của Vietsek, tác giả đã xây dựng nên vector biểu diễn các trang Web, với thành phần của vector chính là tần suất xuất hiện của các từ khóa trong văn bản đang xét. Luận văn này đề xuất một số thuật toán: - Liệt kê danh sách các trang Web “Gần nghĩa nhất” với trang Web hoặc cụm từ tìm kiếm đưa vào theo tiêu chí “Gần nhau về nội dung”. Độ gần nhau về nội dung sẽ thu được khi so sánh các vector biểu diễn với nhau - Độ quan trọng của trang Web dựa vào mối liên kết với trang Web khác và tần số xuất hiện của các từ khóa tìm kiếm trong trang. - Kết hợp độ gần nhau về nội dung và độ quan trọng của trang web thành một tiêu chí gọi là “giá trị kết hợp”. Kết quả sẽ được hiển thị theo “giá trị kết hợp”. Nhận xét Tuy công trình đầu tiên [Séan Slattery] đã giới thiệu khá tổng quan về các phương pháp phân lớp và phân tích một số kết quả thử nghiệm, nhưng nói chung cả bốn công trình nghiên cứu nói trên chưa thực sự đề cập tới vấn đề thiết kế và cài đặt những giải pháp thực sự tinh tế giải quyết vấn đề từ đồng nghĩa và đa ngôn ngữ đối với hệ thống phân lớp trong CSDL Web. Thực hiện việc khảo sát những giải pháp cho vấn đề này và cài đặt thử nghiệm là một công việc nghiên cứu có ý nghĩa.
48. Tồn tại một số thuật toán điển hình giải quyết bài toán phân lớp trong các CSDL văn bản. Việc cài đặt thử nghiệm và đánh giá hiệu quả hoạt động của một số thuật toán phân lớp điển hình như vậy trong một CSDL web thực sự (khoảng vạn trang ) có thể được coi như những bước đi cần thiết đầu tiên trong việc xây dựng và phát triển các máy tìm kiếm tiếng Việt. 4.2. ĐỀ XUẤT MỘT CÁCH TỔ CHỨC CSDL VÀ THUẬT TOÁN ÁP DỤNG Theo những phương pháp biểu diễn văn bản HyperText đã và đang được sử dụng, nghiên cứu, ta có nhận xét tổng quát sau: cách biểu diễn văn bản HyperText trong các máy tìm kiếm có ưu điểm là khai thác được những thông tin quan trọng về vị trí xuất hiện của từ khóa, để từ đó xếp hạng được các trang Web tìm được theo thứ tự gần với nội dung từ khóa cần tìm, nhưng chưa thấy đề cập đến tần số xuất hiện của các từ khóa trong văn bản. Nên việc tìm theo nội dung là khó thực hiện được. Còn với cách biểu diễn theo mô hình Vector của Seán Slattery [2002] thì đã bỏ qua thông tin về vị trí xuất hiện của các từ khóa, một thông tin rất quan trọng cho phân lớp văn bản. Hơn nữa nếu theo cách biểu diễn 2, văn bản gốc cần phân lớp sẽ bị mờ nhạt đi trong tập hợp các văn bản liên qua đến nó, vì phân lớp sẽ mất chính xác nhất là khi các văn bản liên quan không có cùng chủ đề. Còn với cách biểu diễn 3 và 4, số chiều của vector sẽ rất lớn và có rất nhiều thành phần lặp (chính là các từ xuất hiện lặp đi lặp lại trong tập các văn bản liên quan). Từ những ưu nhược điểm của các phương pháp trên, đề tài đưa ra một cách biểu diễn riêng. Ý t ưởng chính vẫn là dựa trên mô hình vector, đồng thời trong cách xây dựng file từ khóa có tính đến các từ đồng nghĩa 4.2.1. Đặt bài toán Tồn tại một tập các văn bản HyperText cho trước, mỗi lớp chứa các tài liệu (dưới dạng *.html) thuộc cùng một thể loại. Xây dựng hệ thống với chức năng: Đọc một tài liệu mới, yêu cầu hệ thống phân tài liệu đó vào một lớp thích hợp. 4.2.2. Cách biểu diễn văn bản: Sử dụng mô hình Vector tính tần suất có tính đến độ quan trọng của vị trí xuất hiện các từ khóa, cùng với các liên kết giữa các trang Xây dựng vector cho trang Web A bằng cách: - Với mỗi trang Web A nào đó, thống kê các trang Web có liên kết tới A và được A trỏ tới.
49. - Đếm số lần của mỗi từ khóa xuất hiện trong A và trong các trang có liên quan đến A, giả sử count[i] là số lần xuất hiện của từ khóa thứ i trong vector biểu diễn của trang A, Nếu i xuất hiện trong thẻ body ( ) thì chỉ tăng count[i] lên 1, Nếu từ i xuất hiện trong thẻ tiêu đề ( ) thì tăng count[i] lên 3, Sau khi đếm xong trang A, nhân count [i] với 3 (chính là trọng số của văn bản cần biểu diễn), sau đó đếm tiếp trong các trang có liên kết, với nguyên tắc tính trọng số vị trí xuất hiện như trong văn bản A, trọng số của các văn bản liên quan bằng 1. Như vậy: Cách biểu diễn trên đã sử dụng kết hợp được các thông tin: Các liên kết vào ra của tài liệu HyperText, tính đến các tài liệu láng giềng nhưng cũng đặt ra trọng số cho tài liệu gốc, biểu diễn được số lần xuất hiện của từ khóa trong tài liệu đồng thời tính đến vị trí xuất hiện của các từ khóa đó trong tài liệu 4.2.3. Thiết kế CSDL. Các văn bản HyperText được mã hóa thành 3 bảng trong CSDL Access. 1. Bảng 1: bảng các từ khóa (KeyWords), Field Name Data Type Description KeyWordID Auto Number Mã từ khóa KeyWord Text Từ khóa Synonymous Memo Các từ đồng nghĩa với từ khóa Từ khóa (KeyWord) : Nội dung là một từ trong tiếng Anh nên nó phải thỏa mãn các điều kiện sau: Từ trong tiếng Anh có một âm tiết, mỗi âm tiết là một chuỗi ký tự a- z,A-Z. Các từ trong câu được tách biệt bởi dấu cách hoặc các ký tự bất kỳ (dấu chấm, dấu phảy, dấu hai chấm, ) không thuộc a-z, A-Z. Các từ đồng nghĩa (Synonymous): Là trường memo có dạng (word1, word2, ,wordn ). Vậy các từ đồng nghĩa có cùng mã (keywordID) với từ khóa. 2. Bảng 2: Bảng các văn bản (Documents) Field Name Data Type Description DocID Auto Number Mã văn bản DocName Text Tên văn bản CacheAdd Text Địa chỉ Cache Vector Memo Vector biểu diễn cho văn bản đó
50. Vector: là trường kiểu Memo, mỗi vector có dạng: (Mã từ khóa 1, số lần xuất hiện ở tiêu đề, tổng số lần xuất hiện trong văn bản);( Mã từ khóa 2, số lần xuất hiện ở tiêu đề, tổng số lần xuất hiện trong văn bản); Số thành phần của Vector chính là số từ khóa xuất hiện trong trang Web đang biểu diễn, chứ không phải là toàn bộ các từ khóa trong bảng KeyWord, do đó số chiều của vector sẽ giảm đi rất nhiều. Mỗi thành phần của vector biểu diễn số lần xuất hiện và vị trí xuất hiện của các từ khóa trong văn bản. VD: Một Vector có dạng: (1,1,4);(2,1,4);(4,2,7) có ý nghĩa: Từ khóa thứ nhất xuất hiện 4 lần, trong đó 1 lấn xuất hiện ỏ tiêu đề. Tứ khoá thứ 2 xuất hiện 4 lần trong đó 1 lần xuất hiện ở tiêu đề Tứ khoá thứ 4 xuất hiện 7 lần trong đó 2 lần xuất hiện ở tiêu đề DocID Cache Address Vector 1 C:\data\sport\s1.htm (1,1,4); (3,1,4); (4,2,7); . 2 C:\data\sport\s2.htm (1,2,7); (2,1,4); (3,2,8); . 3 C:\data\culture \ct3.htm (1,2,6); (5,1,4); (7,2,7); . 4 C:\data\ culture \c4.htm (2,1,4); (3,1,4); (4,2,7); . 3.Bảng 3 Thể hiện sự kiên kết giữa các văn bản. (LINKS) Field Name Field Type Descrription DocID1 Number Mã của văn bản liên kết đi DocID2 Number Mã văn bản được liên kết tới DocID1 là mã các văn bản có liên kết tới các văn bản có mã trong DocID2. 4. Bảng 4. Xác suất của các lớp Field name Fielsd type Description ClassName Text Tên lớp Probability Number(từ 0 100) Xác suất để có lớp 4.2.4.Thiết kế Modul chương trình
51. 1.Modul phân tích trang Web để tạo ra bảng KEYWORDS Thuật toán: Input: Các văn bản dùng để tạo từ khóa While (chưa đọc hết các văn bản) do 1. Đọc từng văn bản 2. While (chưa đọc xong văn bản) do 2.1.Đọc từng từ 2.2. Insert vào Cơ sở dữ liệu End End. Output: File các từ khóa Truờng Synonymous sẽ được bổ sung bằng tay đối với từng từ khóa Thêm chức năng nhập thêm từ khóa bằng tay, xóa từ khóa không cần thiết. 2.Modul lấy địa chỉ Cache (CacheAddress) của từng tài liệu huấn luyện và tạo ra mã tài liệu (DocID) để thêm vào hai trường đầu tiên của các bảng DOCUMENTS. Còn trường Vector sẽ tạo sau nhờ Modul thứ 4. Thuật toán: Input: Các văn bản dùng để huấn luyện While (chưa đọc hết các văn bản) do 1.1. Đọc địa chỉ Cache của từng văn bản Insert vào CSDL 1.2. Đọc tên văn bản Insert vào CSDL End Mã văn bản tự tăng. 3.Modul tạo bảng LINKS. Để tạo bảng LINKS trước hết phải có bảng DOCUMENTS để lấy địa mã của từng tài liệu (DocID) tương ứng. Thuật toán: 1. Đọc từ thư mục chứa các tài liệu từ trên đĩa cứng 2. Đặt biến TênTM=[đường dẫn của thư mục] 3. While (chưa phân tích hết các tài liệu) do 3.1. Lấy từng tài liệu trong thư mục kèm thêm địa chỉ Cache(CacheAdd). 3.2. Tìm trong bảng DOCUMENTS DocID của tài liệu này nhờ vào CacheAdd, được DocID1
52. 3.2.1. Phân tích để lấy được các thẻ siêu liên kết, đó là các cụm từ có dạng: href=[Tên tài liệu được trỏ tới], giả sử có N thẻ. 3.2.2. For i=1 to N do 3.2.2.1. Cộng TênTM và [tên tài liệu được trỏ tới] được địa chỉ Cache, duyệt trong DOCUMENTS để lấy DocID, được DocID2 3.2.2.2.Thực hiện lệnh Insert hai DocID đã lấy được ở trên vào hai trường DocID1 và DocID2 của bản LINKS End. End 4. Trả lại bảng LINKS trong CSDL 4. Modul tạo ra vector cho mỗi tài liệu, thêm vào trường Vector của bảng DOCUMENTS. Thuật toán: 1. Đọc từ bảng DOCUMENTS trong CSDL để lấy DocID và CacheAdd 2. While (chưa đọc hết các bản ghi) 2.1. Dùng CacheAdd để đọc tài liệu từ đĩa cứng 2.2. Gán DocID_curence=DocID 2.3. Gán total_occurence=0; header_occurence=0; vector=””; 2.4. Lấy từng từ khóa keyword trong bảng KEYWORDS để so sánh 2.4.1 While (chưa hết các từ khóa) 2.4.1.2. Phân tích tài liệu để lấy từng từ mục : word 2.4.1.2. Kiểm tra xem nếu word chưa có trong bảng KEYWORD thì bổ sung thêm 2.4.1.3. While (chưa đọc hết tài liệu) - Nếu (word= keyword) hoặc (word=từ đồng nghĩa) và (word nằm trong thẻ ) thì total_occurence+3 và header_occurence+1; - Nếu (word=keyword) hoặc (word=từ đồng nghĩa) và (word không nằm trong thẻ ) thì total_occurence ++; header_occurense++; End. 2.4.1.4. total_occurence*3; header_occurence*3; 2.4.1.5. Đọc tất cả các tài liệu mà tài liệu hiện thời liên kết tới(outgoing)
53. Lặp lại các bước phân tích như đối với tại liệu hiện thời, để tăng 2 biến total_occurence và header_occurence 2.4.1.6. Đọc tất các tài liệu liên kết tới tài liệu hiện thời (incoming) Lặp lại các bước phân tích như đối với tài liệu hiênh thời để tăng 2 biến total_occurence và header_occurence End. 2.5. Nếu (total_occurence !=0 ) thì vector += KeyWordID + “,” + total_occurence + “,” + header_occerence +”;” 2.6. Insert into DOCUMENTS (Vector) values vector where DocID=DocID_curence. 3. End. 5. Modul thực hiện phân lớp. Input:Tập hợp các tài liệu cần phân lớp. While (chưa đọc hết tài liệu) do Đọc vào tài liệu cần phân lớp 1. Phân tích tài liệu thành các vetor như trong modul tạo trường vector của bảng DOCUMENTS 2. Kết hợp với các vector của các tài liệu trong CSDL, áp dụng một trong các thuật toán học máy để phân lớp. End 4.2.5. Phân tích các chức năng của hệ thống a. Chức năng chính của hệ thống b. Chức năng chi tiết - Chức năng tạo CSDL - Chức năng phân lớp và tìm kiếm 4.2.6. Đánh giá hệ thống thử nghiệm a. Một số ví dụ kết quả trên hệ thống thử nghiệm Hệ thống đã chạy và cho một số kết quả ban đầu - Xây dựng được hệ thống CSDL như đã trình bày ở trên + Phân tích các văn bản để lấy từ khóa + Thể hiện được các liên kết (link) giữa các tài liệu siêu văn bản trong một siêu văn bản + Mã hóa các văn bản thành các vector và lưu trữ vào CSDL - Thực hiện việc phân lớp một tài liệu siêu văn bản cho trước
54. - Cho phép tìm kiếm một tài liệu siêu văn bản có nội dung gần với tài liệu đưa vào b. Hạn chế của hệ thống Do hạn chế về mặt thời gian nên hệ thống còn có một số mặt hạn chế - Các từ khóa vẫn chưa đầy đủ và chưa có chọn lọc - Chỉ phân lớp được từng tài liệu một (nếu còn thời gian sẽ tiếp tục sửa) - Độ chính xác chưa cao do chưa có dữ liệu học chính xác.