Phân lớp phân cấp taxonomy văn bản Web và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Hương Thảo PHÂN LỚP PHÂN CẤP TAXONOMY VĂN BẢN WEB VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Hà Quang Thụy Cán bộ đồng hướng dẫn: CN. Đặng Thanh Hải HÀ NỘI - 2006 Tóm tắt nội dung Phân lớp văn bản là quá trình gán văn bản một cách tự động vào một hoặc nhiều lớp cho trước. Tuy nhiên, trong trường hợp có số lượng khá lớn các lớp, bài toán sẽ phức tạp hơn rất nhiều, do đó, khi tiến hành phân lớp thường cho kết quả có độ chính xác không cao. Vì vậy, một vấn đề được đặt ra là cần phân lớp các văn bản sử dụng cấu trúc phân cấp. Hiện nay, bài toán này đã và đang trở thành lĩnh vực nhận được nhiều sự quan tâm, nghiên cứu của nhiều nhà khoa học trên thế giới. Khoá luận tốt nghiệp với đề tài "Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng" nghiên cứu nội dung, các thuộc tính, các thuật toán giải quyết bài toán phân lớp phân cấp. Khóa luận đã tiến hành thực nghiệm trên 12 lớp dữ liệu, sử dụng thuật toán máy vector hỗ trợ, kết quả thu được rất tốt với độ đo F1 trung bình lên tới gần 90%. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 1 Lời mở đầu Trích chọn thông tin trên Web đã và đang tạo thêm nhiều tài nguyên thông tin, tri thức mới đáp ứng ngày càng hiệu quả nhu cầu thông tin của con người. Ngày nay, công nghệ trích chọn thông tin trên Web đã hình thành loại hình dịch vụ đầy triển vọng trong việc cung cấp thông tin phong phú và hữu ích từ nguồn dữ liệu được coi là vô hạn trên Web. Một trong những bài toán cơ bản và quan trọng trong trích chọn thông tin trên Web là bài toán phát hiện các quan hệ của các lớp đối tượng trên Web mà quan hệ phân cấp giữa chúng là một loại quan hệ điển hình. Để thực hiện việc phát hiện mối quan hệ phân cấp giữa các lớp đối tượng trên Web thì bài toán đầu tiên cần giải quyết đó là bài toán phân lớp tự động các đối tượng. Tự động phân lớp văn bản là một nhiệm vụ rất quan trọng có thể giúp ích trong việc tổ chức cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn này. Phân lớp văn bản là quá trình gán văn bản một cách tự động vào một hoặc nhiều lớp cho trước. Trong các nghiên cứu phân lớp văn bản, hầu hết đều tập trung vào bài toán phân lớp mà các lớp cho trước được xem là tách biệt nhau và không có cấu trúc xác định mối quan hệ giữa chúng. Những bài toán phân lớp như vậy được gọi là bài toán phân lớp phẳng (flat classification). Tuy nhiên, trong trường hợp có số lượng khá lớn các lớp, bài toán sẽ phức tạp hơn rất nhiều và khi thực hiện các giải pháp phân lớp thường cho kết quả không chính xác. Vì vậy, một vấn đề được đặt ra là cần phân lớp các văn bản sử dụng cấu trúc phân cấp. Thực hiện công việc này mặc nhiên cũng đã bao hàm vấn đề phát hiện quan hệ phân cấp giữa các lớp đối tượng như đã nói ở trên. Về bản chất đây cũng được coi là một loại quan hệ ngữ nghĩa giữa các đối tượng và lớp đối tượng. Bài toán cần được giải quyết là phát hiện các lớp và kiến trúc các lớp đã được phát hiện vào một cây phân cấp. Đây là bài toán phân lớp phân cấp. Phân lớp phân cấp cho phép định hướng vào bài toán phân lớp lớn ban đầu và sử dụng phương pháp chia nhỏ và đệ quy. Khoá luận tốt nghiệp với đề tài "Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng" nghiên cứu nội dung, các thuộc tính, các thuật toán giải quyết bài toán phân lớp phân cấp và cố gắng đưa ra một số nhận xét, đề xuất thích hợp và thi hành chương trình thực nghiệm để kiểm chứng tính khả thi của phương pháp. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 2 Khóa luận được tổ chức thành ba chương mà nội dung chính của các chương được giới thiệu như dưới đây. Chương 1. Tổng quan về Taxonomy và phân lớp văn bản trình bày những nét cơ bản nhất về taxonomy, các khái niệm và nội dung cơ bản về bài toán phân lớp văn bản. Chương này cũng trình bày một số thuật toán phân lớp văn bản điển hình, đặc biệt tập trung vào thuật toán SVM - thuật toán hiện nay được đánh giá là bộ phân lớp nhanh và hiệu quả nhất với bài toán phân lớp văn bản. Chương 2. Phân lớp phân cấp Taxonomy văn bản Web nghiên cứu các phương pháp giải quyết bài toán phân lớp phân cấp và cách xây dựng các bộ phân lớp cho cây phân cấp văn bản. Chương này cũng giới thiệu một số phương pháp đánh giá cho bài toán phân lớp phẳng và độ đo dựa vào khoảng cách và độ tương tự giữa các lớp. Chương 3. Thực nghiệm trình bày các kết quả thực nghiệm thu được khi áp dụng thuật toán SVM và phương pháp phân lớp phân cấp theo hướng top-down. Một số nhận xét, đánh giá kết luận cũng được trình bày. Phần kết luận tổng kết các kết quả của khóa luận và trình bày định hướng phát triển nội dung của khóa luận. Bài toán phân lớp phân cấp văn bản Web thực sự có ý nghĩa về nghiên cứu và triển khai. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 3 MỤC LỤC Chương I. TỔNG QUAN VỀ TAXONOMY VÀ PHÂN LỚP PHÂN CẤP ........5 1.1. Giới thiệu Taxonomy ........................................................................................5 1.2. Phân lớp văn bản..............................................................................................6 1. 2.1. Một số khái niệm......................................................................................7 1.3. Quá trình tiền xử lý dữ liệu ............................................................................11 1.3.1.1. Phương pháp biểu diễn tài liệu.............................................................12 1.3.1.2. Quá trình lựa chọn thuộc tính...............................................................14 1.4. Các thuật toán phân lớp văn bản ...................................................................19 1.4.1. Thuật toán K người láng giềng gần nhất .................................................19 1.4.2. Thuật toán phân lớp AdaBoost................................................................19 1.4.3. Thuật toán máy vector hỗ trợ ..................................................................21 Chương II. PHÂN LỚP VĂN BẢN WEB SỬ DỤNG CẤU TRÚC PHÂN CẤP TAXONOMY...........................................................................................................27 2.1. Hai phương pháp phân lớp phân cấp.............................................................27 2.2. Phân lớp phân cấp văn bản theo hướng top-down ........................................28 2.2.1. Mô hình phân lớp ....................................................................................28 2.2.2. Xây dựng các bộ phân lớp nhị phân.......................................................31 2.3. Đánh giá .........................................................................................................32 2.3.1. Đánh giá cho bài toán phân lớp phẳng ....................................................32 2.3.2. Đánh giá dựa vào độ tương tự .................................................................34 Chương III. THỰC NGHIỆM ...............................................................................37 3.1. Dữ liệu và chương trình .................................................................................37 3.2. Môi trường thực nghiệm.................................................................................40 3.3. Kết quả và đánh giá........................................................................................40 3.3.1. Thực nghiệm1 : Phân lớp phân cấp theo hướng top-down .....................40 3.3.2. Thực nghiệm 2 : Khảo sát sự phụ thuộc thời gian huấn luyện và kết quả vào tập thuộc tính. .............................................................................................46 KẾT LUẬN. .............................................................................................................52 Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 4 TÀI LIỆU THAM KHẢO.......................................................................................54 Tài liệu Tiếng Việt .................................................................................................54 Tài liệu Tiếng Anh .................................................................................................54 PHỤ LỤC A. DANH SÁCH TỪ DỪNG ...............................................................57 Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 5 Chương I. TỔNG QUAN VỀ TAXONOMY VÀ PHÂN LỚP PHÂN CẤP 1.1. Giới thiệu Taxonomy Vào những năm 90 của thế kỉ XX, khái niệm taxonomy được sử dụng trong nhiều lĩnh vực khác nhau như tâm lý học, khoa học xã hội và công nghệ thông tin... để thiết lập sự trùng hợp giữa thuật ngữ của người sử dụng và thuật ngữ của hệ thống. Các chuyên gia đầu tiên phát triển cấu trúc hệ thống Web đã dùng thuật ngữ taxonomy để nói về tổ chức nội dung các trang web. Và từ đó, khái niệm taxonomy được sử dụng rộng rãi với mục đích này. Do được sử dụng trong nhiều lĩnh vực khác nhau, nên có nhiều định nghĩa khác nhau về taxonomy. Từ năm 2000 đến năm 2005, có khoảng 36 định nghĩa khác nhau về taxonomy trong các nguồn tài liệu [24]. Trong lĩnh vực công nghệ thông tin, taxonomy được định nghĩa như sau : Định nghĩa : Taxonomy là sự phân loại của toàn bộ thông tin trong một hệ phân cấp theo một mối quan hệ có trước của các thực thể trong thế giới thực mà nó biểu diễn. Một taxonomy thường được mô tả với gốc ở trên cùng, mỗi nút của taxonomy – bao gồm cả gốc – là một thực thể thông tin đại diện cho một thực thể trong thế giới thực. Giữa các nút trong taxonomy có một mối quan hệ đặc biệt gọi là is subclassification of nếu hướng liên kết từ nút con lên nút cha hoặc là is superclassification of nếu hướng liên kết từ nút cha xuống nút con. Đôi khi những quan hệ này được xác định một cách chặt chẽ hơn là is subclass of hoặc is superclass of, nếu thực thể thông tin là một lớp đối tượng. Hình 1.1. mô tả một taxonomy đơn giản gồm lớp Person, lớp con của nó là Employee, Manager; Lớp cha của Person là Agent. Khi đi lên từ gốc của taxonomy, các thực thể chung chung hơn. Khi đi xuống những lá ở cuối, thực thể xác định rõ ràng hơn. Ví dụ, Agent chung chung hơn Person, Employee cụ thể hơn Person. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 6 Hình 1.1. Taxonomy đơn giản Taxonomy rất có ích cho việc phân lớp thực thể thông tin theo ngữ nghĩa, chúng thiết lập một quan hệ ngữ nghĩa đơn giản để phân biệt giữa các đối tượng trong một miền thông tin. Taxonomy đóng vai trò rất quan trọng trong việc tổ chức thông tin và tổ chức tri thức. Nó được sử dụng chủ yếu để giúp cho việc tìm kiếm và duyệt thông tin thuận lợi và nhanh chóng hơn, đặc biệt khi ta chỉ có những thông tin chung chung về vấn đề cần tìm kiếm. Khi tìm kiếm trên Internet, nếu sử dụng từ khoá để tìm kiếm thông tin, kết quả trả về có thể từ vài nghìn đến vài chục nghìn tài liệu về các chủ đề khác nhau. Sử dụng taxonomy để tìm kiếm và duyệt thông tin sẽ tiết kiệm được rất nhiều thời gian cho người dùng để tìm được thông tin cần thiết. Đồng thời, taxonomy cho phép các máy tìm kiếm và các ứng dụng có thể dễ dàng tìm được các thực thể thông tin nhanh và chính xác hơn nhiều. Taxonomy đã được áp dụng trong nhiều bài toán khác nhau: OU Shi-yan, KHOO Christopher S.G, GOH Dion H. (2005 [15]) xây dựng taxonomy hỗ trợ việc tóm tắt tự động văn bản; H.T.Kung và C.H.Wu xây dựng taxonomy cho mạng nội dung [9], Wollersheim và Rahayu (2002 [5]) xây dựng một taxonomy hỗ trợ việc duyệt cơ sở dữ liệu về y tế. 1.2. Phân lớp văn bản Trong những năm gần đây, với sự phát triển và ứng dụng của Internet, khối lượng dữ liệu đã tăng trưởng không ngừng theo cả hai phương diện tạo mới và lưu trữ. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 7 Sự mở rộng các dữ liệu khoa học về địa lý, địa chất, khí tượng do vệ tinh thu thập, sự giới thiệu quảng bá mã vạch đối với hầu hết các sản phẩm thương mại, việc tin học hoá sâu rộng các thương vụ và giao dịch, sự phát triển việc ứng dụng công nghệ thông tin trong quản lý hành chính nhà nước.... đã tạo ra một khối lượng dữ liệu khổng lồ. Tự động phân lớp văn bản là một nhiệm vụ rất quan trọng có thể giúp ích trong việc tổ chức cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn này. 1. 2.1. Một số khái niệm Phân lớp văn bản (Text Classification) là quá trình gán nhãn các văn bản ngôn ngữ tự nhiên một cách tự động vào môt hoặc nhiều lớp cho trước. Thông thường, các lớp cho trước là các chủ đề nào đó, nhưng cũng có nhiều ứng dụng mà các lớp được thiết lập theo những tiêu chí khác, ví dụ phân lớp theo thể loại, phân lớp theo độ ưu tiên.... Hầu hết các bài toán này sẽ tốn thời gian, công sức và đôi khi không chính xác nếu được phân loại một cách thủ công - tức là đọc từng văn bản và gán vào một lớp nào đó. Phân loại những đối tượng mới vào các lớp bằng phương pháp thủ công gặp phải những khó khăn sau: ♦ Đối với các lĩnh vực đặc biệt, phân loại các đối tượng mới (như cơ sở dữ liệu về y tế, pháp luật) vào các lớp cho trước cần có hiểu biết về các lĩnh vực đó. ♦ Phân lớp bằng tay đôi khi không chính xác vì quyết định phụ thuộc vào sự hiểu biết và động cơ của người thực hiện. ♦ Quyết định của hai chuyên gia khác nhau có thể nảy sinh bất đồng ý kiến. Vì vậy những công cụ để tự động phân lớp văn bản vào các lớp sẽ rất hữu ích với công việc này nhất là khi thông tin tràn ngập như ngày nay. Một số phương pháp phân lớp thống kê và kĩ thuật học máy như Bayesian, máy vector hỗ trợ (Support Vector Machines), K người láng giềng gần nhất (K-NN), mạng nơron ... được áp dụng để giải quyết bài toán này. Rõ ràng, kĩ thuật phân lớp văn bản là rất cần thiết, nhất là ngày nay khi hầu hết các thông tin được sinh ra và lưu trữ điện tử. Các bài báo khoa học và giải trí là những ví dụ về tập các tài liệu điện tử. Với sự phát triển ngày càng mạnh mẽ của mạng Internet và Intranet đã tạo ra nguồn thông tin vô cùng phong phú. Các kĩ thuật phân lớp văn bản sẽ giúp cho nguồn dữ liệu này được lưu trữ tự động một cách hiệu quả và được tìm kiếm nhanh chóng. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 8 Phân lớp văn bản được xuất hiện từ những năm 1960, nhưng chỉ 15 năm sau, nó đã trở thành lĩnh vực nghiên cứu chính trong hệ thống thông tin bởi sự đa dạng của các ứng dụng. Phân lớp văn bản được sử dụng để hỗ trợ trong quá trình tìm kiếm thông tin (Information Retrieval), trích 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. Một ứng dụng khác của phân lớp văn bản là trong lĩnh vực hiểu văn bản. Phân lớp văn bản có thể được sử dụng để lọc văn bản hoặc một phần văn bản chứa các 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. Định nghĩa phân lớp văn bản: Phân lớp văn bản là nhiệm vụ đặt một giá trị Boolean cho mỗi cặp (dj, ci) CD×∈ , trong đó D là tập các văn bản và C= {c1,c2.....cc} là tập các lớp cho trước. Giá trị T (True) được gán cho cặp ( ),j id c có nghĩa là tài liệu jd thuộc lớp ic ; Giá trị F (False) tức là tài liệu jd không thuộc lớp ic . Hoặc, phân lớp văn bản là bài toán tìm một hàm { }FTCD ,: →×Φ trong đó D là tập các văn bản và C= {c1,c2.....cc } là tập các lớp cho trước, hàm { }FTCD ,: →×Φ được gọi là bộ phân lớp. Tuỳ vào bài toán khác nhau, ta có các ràng buộc khác nhau. Nhìn chung có thể phân biệt bài toán phân lớp theo hai cách sau : • Phân lớp văn bản nhị phân/ đa lớp: Bài toán phân lớp văn bản được gọi là nhị phân nếu C =2, gọi là đa lớp nếu C >2. • Phân lớp văn bản đơn nhãn/ đa nhãn: Bài toán phân lớp văn bản được gọi là đơn nhãn nếu mỗi tài liệu được gán vào chính xác một lớp. Một bài toán phân lớp văn bản được gọi là đa nhãn nếu một tài liệu có thể được gán nhiều hơn một nhãn. Về mặt lý thuyết, thuật toán phân lớp nhị phân cũng có thể được sử dụng cho bài toán phân lớp đa lớp bằng cách chuyển bài toán đa lớp { }1 2, ,...., Cc c c thành |C| bài toán nhị phân { },i ic c với 1,...,i C= . Hơn nữa thuật toán phân lớp đa lớp có thể được sử dụng để giải quyết bài toán phân lớp đa nhãn. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 9 Do đó, bài toán phân lớp nhị phân là bài toán rất quan trọng trong các ứng dụng của phân lớp văn bản. Giải quyết bài toán phân lớp nhị phân cũng có nghĩa là giải quyết bài toán phân lớp đa lớp – ứng dụng quan trọng trong phân lớp văn bản. Bài toán lọc văn bản (text filtering), lọc thư rác (spam mail) là những ứng dụng điển hình của phân lớp nhị phân. 1. 2.2. Phân lớp văn bản sử dụng cấu trúc phân cấp Mặc dù các lớp văn bản được tổ chức thành cây phân cấp, ví dụ các tài liệu Web, thư viện điện tử, thư mục thư điện tử, các lớp sản phẩm.... Tuy nhiên cho đến giữa những năm 1990, nhiều nhà nghiên cứu hầu như bỏ qua cấu trúc phân cấp của các lớp. Đặc biệt với các hệ thống phân lớp lớn trong đó số lượng các lớp từ vài chục đến hàng trăm, nếu sử dụng các kĩ thuât phân lớp văn bản phẳng thì sẽ rất phức tạp đồng thời kết quả phân lớp không cao, bởi vì để phân biệt giữa hàng trăm lớp như vậy là rất khó khăn. Vì vậy vấn đề đặt ra là cần phân lớp phân cấp. Năm 1997 Koller và Sahami đưa ra bài báo đầu tiên về vấn đề phân lớp văn bản sử dụng cấu trúc phân cấp [6]. Từ kết quả thực nghiệm, bài báo chỉ ra rằng phân lớp phân cấp cho kết quả tốt hơn so với phân lớp phẳng. Sau bài báo này, rất nhiều hướng nghiên cứu về bài toán phân lớp phân cấp được đề xuất : Soumen Chakrabarti [19]; Dumais và Chen (2000 [21]); Sun và Lim (2001 [3]) ; Ruiz và Srinivasan (2002 [14]); Cai và Hofmann (2004 [11]), Yongwook Yoon (2005 [23]).... Trong khoảng bốn năm gần đây, phân lớp phân cấp đã trở thành lĩnh vực nhận được nhiều sự quan tâm và nghiên cứu của nhiều nhà khoa học trên thế giới. 1. 2.2.1. Định nghĩa và một số khái niệm Hệ đẳng cấp (H) : Một hệ đẳng cấp H = (N, E) là một đồ thị có hướng bao gồm tập các nút N và tập các cạnh (Np, Nc). Hướng của một cạnh (Np, Nc) được xác định từ nút cha Np đến nút con trực tiếp Nc , xác định qua toán tử quan hệ p cN N→ được gọi là liên kết trực tiếp (direct path) từ Np đến Nc. Tồn tại một nút gọi là nút gốc của cây phân cấp. Các nút không có con là là nút lá. Tất cả các nút trừ nút lá và nút gốc được gọi là các nút trong. Bài toán phân lớp sử dụng cây phân cấp H là việc tìm một hàm Φ sao cho : TCDTCD ji =Φ⇒=Φ ),(),( nếu , ,j i j iC C C C H→ ∈ Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 10 Trong đó H là cấu trúc phân cấp xác định mối quan hệ giữa các lớp. Mối quan hệ ji CC → thể hiện mối quan hệ IS-A trong đó lớp Cj là cha của Ci trong cây phân cấp H. Tất cả các tài liệu thuộc lớp Ci đều thuộc lớp Cj . Mối quan hệ này là bất đối xứng (Ví dụ, xem xét quan hệ giữa chó và động vật, chúng ta có "tất cả loài chó là động vật, nhưng không phải tất cả động vật đều là chó") và có tính chất bắc cầu (Ví dụ, xem xét quan hệ giữa cây, cây xanh và cây thông chúng ta có "tất cả cây thông là cây xanh và tất cả cây xanh là cây thì tất cả cây thông là cây"). Mục tiêu là tìm một hàm đánh giá bằng cách sử dụng tập tài liệu thoả mãn điều kiện ràng buộc của hệ phân cấp. Với bài toán phân lớp phân cấp, có hai vấn đề cần được quan tâm : ♦ Cấu trúc của hệ phân cấp: – Cấu trúc taxonomy (như trình bày ở phần 1) trong đó mỗi lớ