Khóa luận 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ớp (trừ lớp gốc) có đúng một lớp cha. – Cấu trúc đồ thị có hướng phi chu trình (Directed Acyclic Graph) trong đó một lớp có thể có nhiều hơn một lớp cha. ♦ Yêu cầu các lớp chứa văn bản : – Các tài liệu chỉ được gán vào các nút lá của hệ phân cấp. – Các tài liệu có thể được gán vào cả nút lá lẫn nút trong của hệ phân cấp. Khóa luận này chỉ giải quyết bài toán trong trường hợp cấu trúc hệ phân cấp là taxonomy và văn bản có thể được gán vào cả nút lá lẫn nút trong của taxonomy. 1.2.2.2. Phân lớp đa lớp sử dụng cấu trúc phân cấp Không giống như phân lớp phẳng trong đó các ứng dụng nhị phân là phổ biến (ví dụ, lọc thư rác, lọc văn bản), phân lớp văn bản sử dụng cấu trúc phân cấp là nhiều lớp. Thậm chí khi chúng ta chia bài toán lớn ban đầu thành các bài toán nhỏ hơn, hiếm khi số lớp là hai. Hầu hết các thuật toán học trạng thái ví dụ Naive Bayes, cây quyết định, mạng noron,... liên quan đến nhiều lớp. Tuy nhiên, có những thuật toán như máy máy vector hỗ trợ được xây dựng để làm việc chỉ với vấn đề nhị phân. Trong những trường hợp này, có một số phương pháp để chuyển bài toán phân lớp nhiều lớp thành bài toán phân lớp nhị phân. Cách đơn giản nhất là chúng ta chuyển vấn đề n lớp cho 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ệ 11 trước thành n vấn đề nhị phân: bài toán nhị phân thứ i tương ứng với một cây quyết định xem tài liệu có thuộc về lớp thứ i hay không?. 1.2.2.3. Phân lớp đa nhãn sử dụng cấu trúc phân cấp Hầu hết các ứng dụng thực của phân lớp phân cấp văn bản là bài toán đa nhãn, có nghĩa là một văn bản có thể được gán vào nhiều hơn một lớp. Ví dụ, bài báo về David Beckham và Victoria có thể thuộc lớp Sport/Football hoặc Entertainment/Music. Để giải quyết bài toán này, mỗi thuật toán phân lớp sẽ có những chiến lược khác nhau. Ví dụ, thuật toán Naive Bayes có thể gán một văn bản không chỉ vào lớp có xác suất dự đoán cao nhất mà sẽ gán vào tất cả các lớp có xác suất cao hơn một ngưỡng nào đó. Với các thuật toán khác, giải pháp phổ biến là chuyển bài toán n lớp thành n bài toán nhị phân. 1.2.2.4. Ứng dụng Rất nhiều ý tưởng nghiên cứu được được thử nghiệm trên tập dữ liệu Reuters- 21578 và 20 News Group và một số nguồn dữ liệu khác từ thư mục Yahoo và DMOZ.... Bên cạnh những tập hợp dữ liệu này, phân lớp phân cấp văn bản cũng thu được kết quả rất tốt khi áp dụng cho những miền dữ liệu khác. Phân loại thư cũng là một ứng dụng của phân lớp phân cấp văn bản. Một ứng dụng khác của phân lớp phân cấp văn bản là áp dụng cho máy tìm kiếm. Như chúng ta đã biết, khi người dùng tìm kiếm, số lượng kết quả trả về rất nhiều (có thể vài nghìn tài liệu liên quan đến từ khoá tìm kiếm), trong số đó chỉ có rất ít tài liệu đáp ứng mong muốn của người dùng. Vì vậy, thay vì trả về một danh sách các văn bản cho người sử dụng, những hệ thống này sẽ trả lại kết quả tìm kiếm được tổ chức thành một hệ phân cấp các chủ đề hữu hạn cho trước. Những biểu diễn như thế này sẽ giúp người sử dụng dễ dàng tìm kiếm thông tin họ cần. Việc này có thể thu được bằng cách tính hạng của kết quả trả về bởi máy tìm kiếm trong một hệ phân cấp chủ đề cho trước. 1.3. Quá trình tiền xử lý dữ liệu Phân lớp văn bản là quá trình gồm hai bước, với mục đích phân các tài liệu văn bản vào các lớp hữu hạn có trước. Trong bước thứ nhất, một mô hình của bộ phân lớp được xây dựng bằng cách phân tích nội dung các trang văn bản trong tập dữ liệu huấ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ệ 12 luyện thông qua việc áp dụng các thuật toán học. Tập dữ liệu huấn luyện là tập hợp các trang văn bản trong cơ sở dữ liệu đã được gán nhãn từ trước. Trong bước thứ hai, mô hình này được sử dụng cho việc phân lớp các trang văn bản chưa được gán nhãn. Để xây dựng mô hình trong bước thứ nhất, thông thường, được chia ra làm hai bước chính sau (Hình 1.2): ♦ Tiền xử lý dữ liệu: là quá trình biểu diễn văn bản thành một dạng biểu diễn logic mà thuật toán có thể xử lý được (ví dụ, dạng biểu diễn vector của văn bản). ♦ Học các bộ phân lớp : sử dụng các thuật toán phân lớp để xây dựng mô hình từ dữ liệu đã qua tiền xử lý. 1.3.1.1. Phương pháp biểu diễn tài liệu Trong bài toán phân lớp văn bản, cách biểu diễn văn bản đóng vai trò rất lớn. Một tài liệu được biểu diễn dưới dạng một tập hợp các từ, mỗi từ được xem là một thuộc tính (feature) và văn bản tương ứng với một vector thuộc tính. Đôi khi, thay vì những từ đơn, các thuộc tính có thể được biểu diễn bằng các cụm từ hoặc chuỗi n từ với n >= 2. Dễ dàng thấy, nhiều thuộc tính phức tạp có thể giàu thông tin hơn. Ví dụ, cụm từ “world wide web” mang nhiều thông tin hơn từng từ riêng biệt. Tuy nhiên, trong thực hành, sử dụng n-grams dẫn tới việc có quá nhiều số lượng thuộc tính và có thể làm việc giải quyết bài toán khó khăn hơn. Theo các nghiên cứu về các phương pháp biểu diễn văn bản khác nhau, đặc biệt là khi so sánh ảnh hưởng và hiệu quả của nó thì không có cách biểu diễn văn bản nào tốt hơn cách biểu diễn bằng tập các từ riêng biệt (isolated words) được lấy ra từ văn bản gốc. Tiền xử lý Phân lớp Văn bản Biểu diễn logic Cây phân cấp Mô hình Hình 1.2. Quá trình xây dựng mô hình được chia thành hai bước : tiền xử lý dữ liệu và học các bộ phân lớ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ệ 13 Sau khi xác định được các thuộc tính, chúng ta cần tính giá trị thuộc tính (hoặc trọng số từ khoá) cho mỗi văn bản. Mỗi từ mục ti trong một tài liệu được gán một trọng số wi và do đó, mỗi tài liệu được biểu diễn như một vector. Trọng số từ khoá có thể được tính toán bằng nhiều cách khác nhau. Cách đơn giản nhất là gán trọng số bằng một giá trị nhị phân chỉ ra từ mục có mặt hay không có mặt trong văn bản. Phương pháp khác là tính số lần xuất hiện của từ mục trong một tài liệu gọi là tần suất từ mục. Tần suất từ mục được tính theo công thức : ( , )( , ) k ik i occ t Dfreq t D N = Trong đó N là tổng số từ mục của tài liệu Di và occ(tk,Di) là số lần xuất hiện của từ tk trong văn bản Di . Phương pháp này có vẻ rất trực quan, nhưng mặt hạn chế của phương pháp này là : nếu một từ xuất hiện nhiều lần trong tài liệu sẽ có tần xuất cao. Tuy nhiên nếu những từ này đều xuất hiện trong tất cả các văn bản thì nó sẽ không mang nhiều thông tin ngữ nghĩa của văn bản, và do đó độ quan trọng của nó giảm đi. Thông thường tần suất của các từ mục trong văn bản là không đồng đều nhau. Một số từ mục xuất hiện rất thường xuyên, trong khi đó, một nửa số từ mục xuất hiện chỉ một lần. Để giải quyết hạn chế này, tần xuất logarit (tương tự với tần xuất từ mục) được đề xuất và tính theo công thức : )),(1log(),( ikik DtfreqDtfreq += Phương pháp thứ hai được sử dụng phổ biến hơn phương pháp tần suất từ mục, nhưng phương pháp này vẫn chưa giải quyết triệt để hạn chế của phương pháp tần suất từ mục. Theo đó, một từ xuất hiện nhiều lần có tần suất cao, từ xuất hiện ít có tần suất thấp. Phương pháp chuẩn thường được sử dụng là Term Frequency Inverse Document Frequency (TFIFF), hàm tính trọng số từ khoá được xác định bởi công thức : , , | |logl d l d l DTFIDF freq df ⎛ ⎞= ∗ ⎜ ⎟⎝ ⎠ Trong đó, tần xuất từ mục l trong tài liệu d : ,l dfreq là số lần xuất hiện của từ mục l trong tài liệu d 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ệ 14 Tần xuất văn bản ldf là số văn bản trong tập tài liệu có chứa từ mục l . D là tổng số tài liệu học. Trọng số TFIDF của một từ mục biểu diễn độ quan trọng của từ mục. TFIDF của một từ mục trong một tài liệu sẽ giảm nếu như từ đó xuất hiện trong hầu hết các văn bản. Vì vậy, một từ xuất hiện quá ít hoặc quá nhiều được đánh giá ít quan trọng hơn so với các từ xuất hiện cân bằng. Trọng số TFIDF của một từ mục trong toàn bộ tập tài liệu D được tính bởi : , l l d l d D TFIDF TFIDF TFIDF R ∈ = ∈∑ Với bài toán phân lớp sử dụng cấu trúc phân cấp, khóa luận đề xuất một phương pháp đánh trọng số đối với các nút trong cây phân lớp trong quá trình phân lớp. Như chúng ta thấy, đối với các thuộc tính ở một mức nào đó được xuất hiện nhiều lần, thì đó là những thuộc tính tốt để phân biệt các lớp ở mức trên, vì vậy chúng cần được đánh trọng số cao. Tuy nhiên, nếu các thuộc tính đó lại xuất hiện ở các lớp con của nó hoặc ở mức dưới hơn, thì độ quan trọng của nó sẽ giảm đi, do đó trọng số sẽ thấp hơn so với ở mức trên. Như vậy, chúng ta cần xác định một giá trị ϖ cho mỗi nút trong taxonomy, hoặc theo kinh nghiệm hoặc theo thống kê. Sau khi xác định được tập thuộc tính cho cho mỗi nút trong taxonomy, trọng số của các thuộc tính này sẽ được nhân với giá trị ϖ tương ứng với lớp đó. Và như vậy, trọng số mới của thuộc tính không chỉ thể hiện độ quan trọng của thuộc tính đối với văn bản đó, mà còn thể hiện được độ quan trọng của nó đối với toàn bộ cấu trúc phân cấp. 1.3.1.2. Quá trình lựa chọn thuộc tính Kích cỡ của tập từ vựng của tập hợp văn bản thường rất lớn, ví dụ 20.000 tài liệu của Reuters 21578, tập hợp dữ liệu có khoảng 15.000 từ mục khác nhau. Xử lý các vector thuộc tính đòi hỏi các thuật toán được tính toán mở rộng và có thể đôi khi không thể tính toán được đối với một số thuật toán học. Bên cạnh đó, nhiều thuộc tính không mang thông tin, nhập nhằng hoặc bị nhiễu, do đó có thể dẫn tới bộ phân lớp đạt được kết quả tốt trên dữ liệu học nhưng không tốt trên dữ liệu kiểm tra (overfitting). 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ệ 15 Lựa chọn thuộc tính là quá trình chọn ra những thuộc tính mang nhiều thông tin nhất trong không gian thuộc tính và loại bỏ những thuộc tính nhiễu. Trong phân lớp phân cấp văn bản, việc chọn lựa các thuộc tính là rất quan trọng vì tập văn bản rất lớn. Để giải quyết vấn đề này, quá trình lựa chọn thuộc tính được tiến hành bằng cách chỉ giữ những từ mục có giá trị về thông tin. Vì vậy, vấn đề phát hiện các từ mục không quan trọng phải được giải quyết để thu được không gian từ mục T T′ ⊂ với T T′ << . Đối với bài toán phân lớp sử dụng cấu trúc phân cấp, có hai cách tiếp cận khác nhau cho quá trình trích chọn thuộc tính được đề xuất: Lựa chọn thuộc tính toàn cục: Lựa chọn thuộc tính trong phân lớp văn bản sử dụng cấu trúc phân cấp gọi là toàn cục nếu nó lựa chọn tập các thuộc tính T ′ , T T′ << để phân biệt tất cả các lớp Ci trong một cấu trúc phân cấp cho trước. Lựa chọn thuộc tính cục bộ: Lựa chọn thuộc tính trong trong phân lớp văn bản sử dụng cấu trúc phân cấp gọi là cục bộ nếu nó lựa chọn tập các thuộc tính iT ′ , iT T′ << phù hợp cho mỗi lớp Ci trong cấu trúc phân cấp cho trước. Hình dưới mô tả cách lựa chọn thuộc tính toàn cục và cục bộ : Tin học Nông nghiệp Ngôn ngữ lập trình Hệ điều hành Trồng trọt Chăn nuôi Trang trại Máy tính Cây lúa mì Động vật Windows Java Sữa C++ Con bò Linux Con cừu Bệnh tật Hình 1.3.a : Lựa chọn thuộc tính theo hướng toàn cục 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ệ 16 Cách tiếp cận toàn cục để chọn lựa các thuộc tính thường được sử dụng trong phân lớp phẳng. Cách tiếp cận cục bộ, coi mỗi nút trong của cây phân cấp như một bài toán phân lớp và lựa chọn thuộc tính cho mỗi bài toán con độc lập nhau. Đối với bài toán phân lớp phân cấp, khi số lượng các lớp lên đến hàng trăm thì việc quản lý số lượng quá nhiều thuộc tính trở nên vô cùng khó khăn, đồng thời làm cho việc xử lý dữ liệu và thời gian học các bộ phân lớp tăng lên đáng kể. Giải pháp là lựa chọn thuộc tính theo phương pháp cục bộ, tức là sẽ chọn những thuộc tính phù hợp nhất tại mỗi mức của taxonomy để phân biệt giữa các lớp tại mức ấy. Với chiến lược này, chúng ta có thể giảm được thời gian huấn luyện các bộ phân lớp đồng thời quản lý số lượng thuộc tính nhỏ sẽ đơn giản hơn. Weigend năm 1999 (theo [xx]) là người đầu tiên đưa ra so sánh và phân biệt giữa hai chiến lược lựa chọn thuộc tính này. Trong học máy, một số kỹ thuật chính sau đây được xây dựng cho quá trình lựa chọn thuộc tính : Kỹ thuật thứ nhất thực hiện các phương pháp lọc (filtering) trên tập thuộc tính ban đầu. Với phương pháp này kết quả thu được từ tính toán thống kê được sử dụng để loại bỏ những từ mục không thích hợp. Sau đó, bộ phân lớp được huấn luyện trên không gian từ mục đã được rút gọn. Với chiến lược lựa chọn từ mục này, có một vài phương pháp như : lựa chọn từ mục theo tần suất văn bản (Documen Frequency), độ đo thông tin qua lại (Mutual Information). Sữa Con bò Con cừu Bệnh tật Tin học Nông nghiệp Ngôn ngữ lập trình Hệ điều hành Trồng trọt Chăn nuôi Trang trại Máy tính Cây lúa mì Động vật Windows Java Windows Java C++ Linux Hình 1.3.b : Lựa chọn thuộc tính theo hướng cục bộ 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ệ 17 Tần suất văn bản : Tần suất của văn bản là số tài liệu mà một từ mục xuất hiện. Để lựa chọn từ mục theo phương pháp tần suất văn bản, chúng ta phải tính tần suất văn bản với mỗi từ mục trong tập dữ liệu học và sau đó loại bỏ những từ mục có tần suất nhỏ hơn một ngưỡng nào đó để thu được không gian từ mục nhỏ hơn. Đây là kĩ thuật đơn giản nhất để làm giảm số lượng tâp thuộc tính. Độ đo thông tin qua lại (MI) : là phương pháp được sử dụng khá phổ biến để lựa chọn tập thuộc tính dựa vào mô hình thống kê. Với mỗi cặp từ mục t và lớp c , MI được tính theo công thức sau : ( ) ( )( ) ( ), log Pr t c I t c Pr t Pr c ∧= × Và được ước lượng : ( ) ( ) ( ), log A NI t c A C A B ×≈ + × + Trong đó : – A là số lần từ mục t và lớp c đồng thời xuất hiện. – B là số lần từ mục t xuất hiện mà không thuộc c. – C là số lần c xuất hiện không chứa t. – N là tổng số dữ liệu học. ( ),I t c nhận giá trị 0 nếu từ mục t và lớp c độc lập với nhau. Giá trị ( ),I t c càng cao thể hiện độ quan trọng của thuộc tính t với lớp c. Kỹ thuật thứ hai được gọi là kĩ thuật wrapper, trong đó việc lựa chọn từ mục phụ thuộc vào thuật toán phân lớp. Bắt đầu từ không gian từ mục ban đầu, một không gian từ mục mới được sinh ra bằng việc thêm hoặc bớt từ. Khi một tập hợp từ mục mới được tạo ra, bộ phân lớp dựa vào đó để xây dựng và sau đó kiểm tra trên tập dữ liệu kiểm tra. Tập dữ liệu cho kết quả tốt nhất sẽ được chọn. Không gian từ mục tốt nhất được tạo ra cho thuật toán phân lớp. Phương pháp này tạo thuận lợi cho thuật toán phân lớp; Tuy nhiên hạn chế của phương pháp này là sự phức tạp trong tính toán. Kỹ thuật thứ ba, đánh chỉ mục dựa vào ngữ nghĩa tiềm ẩn - Latent Semantic Indexing (LSI – Deerwester 1990, theo [xx]), nén các vector từ mục thành các vector 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ệ 18 có số chiều ít hơn trong không gian từ T ′ , số chiều thu được là sự liên kết các từ trong không gian từ mục ban đầu T. LSI sử dụng kĩ thuật toán học gọi là phép phân tích ma trận dựa vào giá trị suy biến (Sigular Value Decomposition - SVD). SVD chuyển ma trận từ mục – văn bản D ban đầu thành ma trận D% có số chiều nhỏ hơn sao cho khoảng cách giữa hai ma trận : đạt giá trị nhỏ nhất. Để làm được điều này, với ma trận từ mục – văn bản m nD × ban đầu, trong đó m là số từ mục và n là số tài liệu, SVD thực hiện như sau: Trong đó U là ma trận m r× , V là ma trận r n× . Các cột của m rU × trực giao với nhau và được gọi là các vector suy biến trái. Các cột của r nV × trực giao với nhau và được gọi là các vector suy biến phải. r rσ × là ma trận chéo của các giá trị suy biến từ ma trận ban đầu D, với ( )min ,r m n≤ là hạng của ma trận từ mục – tài liệu D ban đầu. Thông thường r là min(m,n). Tuy nhiên, nếu chúng ta chỉ giữ lại k từ có giá trị suy biến lớn nhất, xấp xỉ ma trận ban đầu thành ma trận mới sau: Ma trận D% thu được bằng cách xóa bỏ những giá trị suy biến nhỏ từ σ , U% và V% thu được bằng cách xóa bỏ hàng và cột tương ứng. Sau khi thu được kết quả từ SVD dựa trên dữ liệu học, một tài liệu mới được ánh xạ vào không gian từ mục nhỏ hơn như sau: Ngoài việc lựa chọn các thuộc tính mang nhiều thông tin từ tập thuộc tính ban đầu, quá trình lựa chọn thuộc tính có thể tạo ra các thuộc tính mới (ví dụ các khái niệm) để thay thế cho một nhóm các thuộc tính thông qua kỹ thuật phân cụm. Nhóm các từ có sự giống nhau về ngữ nghĩa sẽ được xem là một thuộc tính mới thay thế cho các từ đơn lẻ. Với phương pháp này, cần xác định độ tương tự giữa các từ và áp dụng các kĩ thuật phân cụm như k người láng giềng gần nhất 2 D D∆ = − % D U Vσ= T m k k k k nD U Vσ× × ×=% % %% ' 1 Td u dσ −=r r 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ệ 19 1.4. Các thuật toán phân lớp văn bản Phân lớp văn bản là quá trình gán nhãn các văn bản ngôn ngữ tự nhiên vào môt hoặc nhiều lớp từ tập các lớp hữu hạn cho trước. Hiện nay tồn tại rất nhiều thuật toán phân lớp văn bản như : thuật toán K người láng giềng gần nhất, thuật toán học cây quyết định, thuật toán Naive Bayes, thuật toán máy vector hỗ trợ, thuật toán Boosting... Phần này giới thiệu một số thuật toán điển hình, trong đó tập trung vào thuật toán máy vector hỗ trợ. 1.4.1. Thuật toán K người láng giềng gần nhất Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm x đến tất cả các điểm dữ liệu trong tập huấn luyện. Qua đó tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật toán K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật toán k-NN vào tài liệu văn bản, chúng ta sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức (1.1). Trong đó ),,( kDxcN là tập con chỉ chứa các đối tượng thuộc lớp c của tập ),,( kDxN . ( , , ) ( | ) c o s ( , ) (1 .1) x N c x D k S c o r e c x x x ′∈ ′= ∑ Khi đó tài liệu x sẽ được phân vào lớp oc nếu: { }CcxcscoreMaxxocscore ∈= ),|()|( 1.4.2. Thuật toán phân lớp AdaBoost Boosting là một phần đặc biệt của các "Bộ phân lớp ủy ban" (classifier committees). Ý tưởng của bộ phân lớp ủy ban là kết hợp k bộ phân lớp độc lập để xây dựng một bộ phân lớp mới. Với bộ phân lớp ủy ban, các nhà nghiên cứu thường sử dụng nhiều bộ phân lớp khác nhau như bộ phân lớp dựa cây quyết định, bộ phân lớ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ệ 20 dựa vào xác suất, bộ phân lớp tuyến tính.... Boosting điển hình chỉ sử dụng một bộ phân lớp gọi là bộ phân lớp yếu (weak classifier) hoặc bộ phân lớp cơ sở (base classifier). Ngược lại với bộ phân lớp ủy ban, Boosting không kết hợp các bộ phân lớp độc lập. Thay vào đó, Boosting kết hợp các giả thuyết phân lớp được xây dựng từ cùng một thuật toán trên các tập dữ liệu học khác nhau. Tại mỗi vòng lặp tính bộ phân lớp yếu, một tập dữ liệu học phù hợp được chọn và cuối cùng tất cả các giả thuyết phân lớp yếu được kết hợp với nhau. Hiện nay, AdaBoost là phương pháp phổ biến nhất của Boosting, được phát triển dựa trên lý thuyết thống kê. AdaBoost được phát triển vào năm 1994 bởi Freund và Schapire [12]. Theo các nghiên cứu, AdaBoost là bộ phân lớp nhanh và hiệu quả trong nhiều ứng dụng khác nhau. AdaBoost cũng đã được áp dụng với bài toán phân lớp văn bản và khá thành công. Hiện nay, nó được xem là một trong những thuật toán phân lớp nhanh và hiệu quả nhất. Cho { }1, .... ,i m mS d y d y= r r , idr là dữ liệu học và iy là nhãn tương ứng của dữ liệu id r từ tập nhãn hữu hạn Y . Trong trường hợp đơn giản { }1,1Y = − là bài toán phân lớp nhị phân và có thể dễ dàng mở rộng thành bài toán phân lớp nhiều lớp. Tập dữ liệu học S và phân phối B là đầu vào của thuật toán học yếu (weak learning algorithm) hoặc thuật toán học cơ sở (base learning algorithm) ( ),S BΦ để tính toán bộ phân lớp yếu :h I →ℜ . Dấu của ( )h dr , tức ( )( )sgn h dr thể hiện nhãn dữ đoán của văn bản d r và ( )h dr thể hiện độ tin cậy của dữ đoán. Mặc dù ( )h dr có thể nhận giá trị thực nhưng ta thừa nhận ràng buộc ( )h dr thuộc đoạn [ ]1,1− mà không mất tính tổng quát. Phân phối B của tập dữ liệu học được biểu diễn thông qua trọng số ( ) [ ]0,1B i ∈ cho mỗi văn bản. Tại mỗi vòng lặp, giả thuyết phân lớp yếu ( ),t th S B= Φ được tính toán dựa vào phân phối hiện tại của tập dữ liệu học. Sau đó, phân phối tB được cập nhật: ( ) ( ) ( )( )t1 exp - i t itt t B i y h d B i Z α + ∗ = r Trong đó: ( ) ( )( )texp -t t i t i i Z B i y h dα= ∗∑ r Đặt: ( ) ( )t 0 T t t f d h dα = =∑r r 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ệ 21 Là trọng số của hàm phân lớp yếu th . Hàm phân lớp cuối cùng ( )H dr được tính như sau: ( ) ( )( )sgnH d f d=r r Thuật toán: Input: { }1, .... ,i m mS d y d y= r r , id D∈r , { }1,1iy Y∈ = − với S... Tập dữ liệu học với nhãn tương ứng. Y... Nhãn của dữ liệu học, có giá trị 1 nếu là dữ liệu dương, -1 nếu dữ liệu âm. B....Phân phối của tập dữ liệu học với ( )tB i là trọng số của idr tại thời điểm t. Φ ... Hàm phân lớp yếu nhận S, B là đầu vào, đầu ra th . th : { }1,1D → − được tính bởi Φ với tB . Funtion AdaBoost Begin Khởi tạo: ( )1 1B i m= For 1,...,t T= Tính ( ),t th S B= Φ Chọn tα ∈ℜ For ( )t tB i B∈ do Cập nhật phân phối: ( ) ( ) ( )( )t1 exp - i t itt t B i y h d B i Z α + ∗ = r với: ( ) ( )( )texp -t t i t i i Z B i y h dα= ∗∑ r End for End for Output: ( ) ( )t 0 sgn T t t H d h dα = ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ r r End function 1.4.3. Thuật toán máy vector hỗ trợ Theo [16], thuật toán máy vector hỗ trợ (Support Vector Machines - SVM) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu chỉ được thiết kế để giải quyết bài toán phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài toán phân lớp văn bản [Soumen Chakrabarti, trang 183, Mining the web- discovering 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ệ 22 knowledge from Hypertext Data] [18] bởi vì đó là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài toán phân lớp văn bản. Cho tập dữ liệu học { }( , ), 1,...,i iD x y i n= = với mix R∈ và { }1,1iy ∈ − là một số nguyên xác định ix là dữ liệu dương hay âm. Một tài liệu ix được gọi là dữ liệu dương nếu nó thuộc lớp ic ; ix được gọi là dữ liệu âm nếu nó không thuộc lớp ic . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: { }0: ( ) 0Tx f x w w= + = Trong đó mw R∈ và 0w R∈ đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân { }: 0,1mh R → có thể thu được bằng cách xác định dấu của f(x) : Học bộ phân lớp của mô hình bao gồm việc xác định w và 0w từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn; tức là ( ) 0i iy f x > với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật toán đơn giản để xác định siêu phẳng : 1 ( ) 0 h x ⎧= ⎨⎩ nếu ( ) 0f x > ngược lại 1. 0w← 2. 0 0w ← 3. repeat 4. 0e ← 5. for 1,...,i n← 6. ( )( )0do Ti is sign y w x w← + 7. if 0s < 8. then i iw w y x← + 9. 0 0 i iw w y x← + 10. 1e e← + 11. until e = 0 12. return ( )0,w w 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ệ 23 Điều kiện cần để D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài toán phân lớp văn bản, bởi vì số lượng từ mục có thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. Trong hình 1.4, giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian , và được tạo ra với cùng một xác suất. Khi đó một siêu phẳng phân cách được gọi là lý tưởng nếu nó làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng mà chúng ta xây dựng nhằm phân cách các điểm dữ liệu mẫu có thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đó sẽ dẫn tới việc phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của không gian đầu vào m, vì với một số lượng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế sẽ tăng theo hàm mũ với lũy thừa m. Với bài toán phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. Siêu phẳng lý tưởng Siêu phẳng thực tế Hình 1.4. Mối quan hệ giữa các siêu phẳng phân cách 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ệ 24 Theo lý thuyết thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng : chúng ta có thể xác định một siêu phẳng tối ưu thoả mãn hai tính chất quan trong : nó là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; và khả năng overfitting là nhỏ hơn so với các siêu phẳng khác [16]. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 1.5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. Khoảng cách từ một điểm x đến siêu phẳng là : ( )01 Tw ww + Vì vậy siêu phẳng tối ưu có thể thu được bằng ràng buộc tối ưu sau: 0, max w w M Sao cho ( )01 , 1,...,Ti iy w x w M i nw + ≥ = Hình 1.5. Siêu phẳng tối ưu và biê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ệ 25 Trong đó ràng buộc yêu cầu mỗi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nó và khoảng cách từ điểm tới siêu phẳng lớn hơn hoặc bằng M. Đặt 1Mw = biểu thức trên được viết lại như sau: 0, min w w w Sao cho : ( )0 , 1,...,Ti iy w x w M i n+ ≥ = Đưa về phương trình Lagrangian: ( )2 0 1 1( ) 1 2 n T i i i L D w y w wα = ⎡ ⎤= − + + −⎣ ⎦∑ Sau đó tính đạo hàm của phương trình trên với 0,w w ta thu được: 1 1max 2 n T i iα α α α = − Λ +∑ thoả mãn : i 0 1,...,i nα ≥ = với Λ là ma trận n n× trong đó Tij i j i jy y x xα = . Đây là bài toán bậc hai, theo lý thuyết có thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thoả mãn điều kiện: ( )0 1 0Ti iy w wα ⎡ ⎤+ − =⎣ ⎦ Và do đó hoặc 0iα = hoặc ( )0 1Ti iy w x w+ = . Nói cách khác, nếu 0iα > thì khoảng cách từ điểm ix đến mặt phẳng phân cách là M. Các điểm thoả mãn 0iα > được gọi là các vector hỗ trợ. Hàm quyết định h(x) có thể được tính qua công thức dấu của f(x) hoặc tương đương với dạng sau: 1 ( ) n T i i i i f x y x xα = =∑ Nếu dữ liệu học không tách rời tuyến tính, thêm biến iξ và thay phương trình trên bằng phương trình: 0, 1 min n iw w i w C ξ = + ∑ thoả mãn ( )0 1 1,..., 0 1,..., T i i i i y w x w i n i n ξ ξ ⎧ + ≥ − =⎪⎨ ≥ =⎪⎩ Vấn đề này có thể đưa về dạ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ệ 26 1 1max 2 n T i iα α α α = − Λ +∑ thoả mãn: 0 1,....,i C i nα≤ ≤ = Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. 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ệ 27 Chương II. PHÂN LỚP VĂN BẢN WEB SỬ DỤNG CẤU TRÚC PHÂN CẤP TAXONOMY 2.1. Hai phương pháp phân lớp phân cấp Phân lớp phân cấp văn bản hướng tới việc gán tài liệu vào một hoặc nhiều lớp phù hợp của cây phân cấp. Các phương pháp giải quyết bài toán phân lớp phân cấp văn bản có thể được chia thành hai hướng [Sun and Lim, 2001][3]: – Phương pháp toàn cục (hoặc big-bang). – Phương pháp cục bộ (hoặc top down). Trong phương pháp big-bang, chỉ một bộ phân lớp được sử dụng trong quá trình phân lớp. Cho một tài liệu, bộ phân lớp sẽ gán nó vào một hoặc nhiều lớp trong hệ phân cấp. Các lớp được gán có thể là lá hoặc các nút trong của hệ phân cấp phụ thuộc vào cấu trúc của hệ phân cấp và từng bài toán khác nhau. Phương pháp big-bang có thể thu được với bộ phân lớp Rocchio, bộ phân lớp dựa vào luật và các phương pháp được xây dựng trên khai phá các luật kết hợp. Đánh giá kết quả được sử dụng trong những thực nghiệm này dựa trên số tài liệu được phân lớp đúng hoặc phần trăm tài liệu bị phân lớp sai. Trong phương pháp top-down, một hoặc nhiều bộ phân lớp được xây dựng tại mỗi nút của cây phân cấp và mỗi bộ phân lớp làm việc như một bộ phân lớp phẳng ở mức đó. Một tài liệu đầu tiên sẽ được phân lớp bởi bộ phân lớp ở mức gốc vào một hoặc nhiều lớp ở mức thấp hơn. Nó sẽ tiếp tục được phân lớp xa hơn ở các mức tiếp theo cho đến khi nó đạt được lớp cuối cùng có thể là lá hoặc nút trong của cây. Phương pháp top-down được thực hiện với các thuật toán như Bayesian, SVM. Ba độ đo: precision, recall, độ đo F được sử dụng trong phương pháp này. Phương pháp cục bộ có vẻ tự nhiên hơn cho phân lớp phân cấp bởi vì nó phản ánh cách mà con người thường thực hiện đối với những bài toán như vậy. Phân biệt giữa ít lớp đơn giản hơn so với phân biệt giữa hàng trăm lớp. Điều này là đúng với các hệ thống tự động. Trong học máy, nói chung theo kinh nghiệm, càng nhiều lớp thì bài toán càng khó hơn. Phân lớp vào các mức cao đơn giản hơn so với phân lớp vào tất cả các lớp không phải chỉ vì số lượng lớp ít hơn mà bởi vì chúng được phân biệt với nhau rõ hơn. Do đó, sau khi 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ệ 28 phân lớp ở mức cao, khả năng phân lớp ở mức thấp ít hơn bởi vì chúng ta chỉ xem xét lớp được lựa chọn. Dễ nhận thấy phương pháp toàn cục có những nhược điểm sau: – Nặng về tính toán. – Rất khó để biểu diễn tập thuộc tính khác nhau tại các mức khác nhau. – Không đủ mềm dẻo, linh hoạt vì mỗi khi cấu trúc taxonomy thay đổi thì bộ phân lớp phải được học lại. Do đó, trong khóa luận này, chúng tôi tập trung vào bài toán phân lớp phân cấp văn bản theo hướng tiếp cận top-down. 2.2. Phân lớp phân cấp văn bản theo hướng top-down Phân lớp phân cấp văn bản theo chiến lược top-down định hướng vào bài toán phân lớp lớn ban đầu theo phương pháp chia nhỏ và đệ quy. Với phương pháp này, ta cần xây dựng nhiều bộ phân lớp và phân lớp một tài liệu mới được thực hiện bằng cách bắt đầu từ gốc và duyệt qua cây phân cấp cho đến khi tìm được các lớp phù hợp. Đệ quy tại mỗi nút, và các bộ phân lớp tại các nút trong sẽ quyết định nhánh nào, cạnh nào của cây phân cấp sẽ được đi xuống sâu hơn. 2.2.1. Mô hình phân lớp Phương pháp phân lớp trong mô hình này là tính toán bộ phân lớp tại mỗi nút. Cho một tài liệu với đầu vào là một vector, bộ phân lớp sẽ xác định đường đi từ nút gốc của cây phân cấp. Phân lớp một tài liệu sẽ dừng lại nếu như không có lớp nào được chọn bởi bất kì bộ phân lớp nào. Như đã giới thiệu ở phần 2.1, đây là phương pháp top-down. Trong bài toán phân lớp với hệ phân cấp dạng taxonomy, mục tiêu cuối cùng là thu được độ chính xác cao nhất tại các bộ phân lớp lá. Thông thường, các bộ phân lớp nhánh đóng vai trò bổ trợ, làm tăng độ chính xác cho các nút lá. Tuy vậy, kết quả phân lớp của các nút lá trong taxonomy lại phụ thuộc vào các bộ phân lớp nhánh. Do đó, các các bộ phân lớp nhánh đóng vai trò rất quan trọng trong kết quả của hệ thống phân lớ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ệ 29 Với bài toán đa nhãn, giả sử có bốn lớp A, B, C, D và bốn bộ phân lớp nhị phân tương ứng. Các dữ liệu có thể được gán vào nhiều hơn một lớp. Những dữ liệu này sẽ được phân lớp bằng hai phương pháp : phân lớp phẳng và phân lớp phân cấp. Cấu trúc lớp được trình bày như hình 2.1 dưới đây : Giả sử hai dữ liệu kiểm tra là Doc-1 và Doc-2. Vì bài toán là phân lớp đa nhãn nên với phương pháp phân lớp phẳng, chúng ta áp dụng bốn bộ phân lớp tại cùng thời điểm với mỗi dữ liệu kiểm tra. Với phương pháp phân cấp, đầu tiên chúng ta áp dụng hai bộ phân lớp lá cho lớp A và D và bộ phân lớp nhánh BC. Nếu kết quả phân lớp cho nhánh BC là dương, chúng ta áp dụng hai bộ phân lớp lá cho B và C. Nếu kết quả phân lớp cho nhánh BC là âm thì sẽ không đi sâu xuống nhánh BC nữa. Như vậy, một tài liệu sẽ bắt đầu từ gốc của taxonomy, phân lớp cho tài liệu sẽ dừng lại nếu : – Không có nút nào được chọn. – Nút được chọn là nút lá của Taxonomy. Khi sử dụng phương pháp phân cấp, có hai thuận lợi so với phân lớp phẳng: tiết kiệm thời gian dự đoán và tăng độ chính xác của kết quả phân lớp. Bởi vì khi dự đoán một tài liệu mới bằng phương pháp top-down, chúng ta chỉ cần thực hiện chỉ một phần nhỏ của các bộ phân lớp và do đó có thể tiết kiệm đáng kể thời gian. Hơn thế nữa, nếu yêu cầu về độ chính xác không cao, chúng ta có thể giảm đáng kể thời gian học các bộ phân lớp phân cấp bằng cách chia tập dữ liệu học thành những nhóm phù hợp và sử Hình 2.1. Cấu trúc lớp của 4 lớ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ệ 30 dụng các bộ phân lớp nhị phân như SVMs. Sử dụng chiến lược top-down cho bài toán phân lớp phân cấp, tại mỗi mức của taxonomy, ta chỉ cần phân lớp với số lớp nhỏ hơn rất nhiều so với phân lớp với tất cả các lớp. Và do đó, kết quả phân lớp sẽ chính xác hơn. Bởi vì thực hiện bài toán với ít lớp sẽ đơn giản hơn so với nhiều lớp. Cấu trúc taxonomy cũng có thể được sử dụng để thiết lập tập dữ liệu âm và dữ liệu dương tại thời điểm phân lớp để thu được tập dữ liệu hoc tại các mức khác nhau. Và đôi khi có thể sử dụng tập thuộc tính nhỏ hơn cho mỗi lớp. Có nhiều thuộc tính tốt nhưng không hữu ích để phân biệt giữa các lớp trong bài toán phân lớp phẳng. Xem xét một taxonomy với cấu trúc như hình 2.2. dưới đây. Trong mô hình phân lớp phẳng, ta cần phân biệt giữa 6 lớp. Các lớp này đượ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. Một thuộc tính như “Máy tính” sẽ không được phân biệt lắm bởi vì nó có thể liên quan tới cả ba lớp: Phần cứng, phần mềm, tán ngẫu. Trong khi đó, với mô hình phân cấp, từ “Máy tính” là một thuộc tính tốt để phân biệt ở mức đầu tiên. Tại mức thứ hai nhiều từ chuyên biệt hơn có thể được sử dụng là các thuộc tính tốt để phân biệt ba lớp “Tán ngẫu”, “Phần cứng”, “Phần mềm” của cây con “Tin học”. Và một số thuộc tính giống nhau có thể được sử dụng để phân biệt các lớp ở mức hai đều là các thuộc tính tốt. Ví dụ, một số từ xuất hiện trong cả hai lớp “Thể thao/Tán ngẫu” và “Máy tính/Tán ngẫu”, nhưng ở mức hai, những từ này đều là các thuộc tính tốt cho cả hai lớp này. Trong bài toán phân lớp văn bản, việc lựa chọn thuộc tính đóng vai trò hết sức quan trọng, ảnh hưởng trực tiếp đến độ chính xác của thuật toán. Vì vậy, lựa chọn được tập thuộc tính tốt sẽ làm tăng kết quả phân lớp. Tin học Thể thao Phần mềm Phần cứng Bóng đá Tán ngẫu Tán ngẫu Quần vợt Hình 2.2. Một Taxonomy 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ệ 31 2.2.2. Xây dựng các bộ phân lớp nhị phân Các bộ phân lớp nhị phân thông thường được học với cả dữ liệu học dương và âm. Trong phương pháp phân lớp phân cấp, một bộ phân lớp nhị phân được xây dựng cho mỗi lớp. Các bộ phân lớp này được chia thành hai loại : – Bộ phân lớp xác định một tài liệu có thuộc lớp nào đó hay không gọi là bộ phân lớp cục bộ (local-classifier) – Bộ phân lớp xác định một tài liệu có thuộc nhánh nào đó không được gọi là bộ phân lớp nhánh (subtree-classifier). Sự phân biệt giữa bộ phân lớp cục bộ và bộ phân lớp nhánh được đề xuất bởi Dumais và Chen [21]. Để xây dựng các bộ phân lớp nhị phân trong phân lớp phân cấp, việc rất quan trọng là phải xác định tập dữ liệu học cho mỗi bộ phân lớp. Kí hiệu Parent( iC ) là lớp cha của iC và Coverage(Ci ) với Ci thuộc taxonomy là tập tất cả các lớp thuộc nhánh có gốc là Ci gồm cả Ci . Một tài liệu jd ∈Coverage(Ci ) là đúng nếu jd thuộc bất kì lớp nào của Coverage(Ci ). Ví dụ taxonomy hình 2.2 : Coverage(Tin học ) = {Tin học, Phần cứng, Phần mềm, Tán ngẫu } Tập dữ liệu học cho các bộ phân lớp được lựa chọn theo chiến thuật sau: ♦ Bộ phân lớp nhánh của lớp gốc rootC : – Dữ liệu dương : ( )j rootd Coverage C∈ – Dữ liệu âm : ( )j rootd Coverage C∉ ♦ Bộ phân lớp nhánh cho nút trong iC của taxonomy: – Dữ liệu dương : ( )j id Coverage C∈ – Dữ liệu âm : ( )j id Coverage C∉ và ( )( )j id Coverage Parent C∈ ♦ Bộ phân lớp cục bộ cho nút trong iC của taxonomy: – Dữ liệu dương : j id C∈ 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ệ 32 – Dữ liệu âm : j id C∉ và ( )j id Coverage C∈ ♦ Bộ phân lớp cục bộ cho lá lC của taxonomy: – Dữ liệu dương : j ld C∈ – Dữ liệu âm : j ld C∉ và ( )( )j ld Coverage Parent C∈ 2.3. Đánh giá Để đánh giá phương pháp phân lớp phân cấp, cách trực tiếp là áp dụng độ hồi tưởng (recall) và độ chính xác (precision) của phân lớp phẳng tại mỗi lớp của toàn bộ hệ phân cấp. Trong cấu trúc phân cấp, các lớp có mỗi quan hệ cha-con, anh-em. Càng đi sâu xuống cây phân cấp, sự phân biệt giữa các lớp càng khó khăn hơn. Hai lớp có thể tương tự nhau khi chúng cùng chứa một số tài liệu. Ví dụ, lớp Programming và Software Engineering có thể có chung một số thuộc tính cho phép tài liệu được phân lớp vào cả hai lớp đó. Vì vậy, nếu một tài liệu không được gán vào đúng lớp chứa nó, nhưng được gán vào lớp cha hoặc lớp con được xem là tốt hơn so với các lớp ở nhánh khác. 2.3.1. Đánh giá cho bài toán phân lớp phẳng Đánh giá kết quả phương pháp phân lớp văn bản có thể được tính toán theo nhiều cách khác nhau. Trong khóa luận này, chúng tôi tập trung vào độ chính xác của kết quả phân lớp cuối cùng. Theo khảo sát của Sebastiani [8], độ đo phổ biến nhất được sử dụng để đánh giá phân lớp phẳng là độ hồi tưởng và độ chính xác. Kí hiệu : Dữ liệu thực Lớp Ci Thuộc lớp Ci Không thuộc lớp Ci Thuộc lớp Ci TPi TNi Dự đoán Không thuộc lớp Ci FPi FNi 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ệ 33 – TP (true positives): số lượng ví dụ dương được thuật toán phân đúng vào Ci. – TN (true negatives): số lượng ví dụ âm được thuật toán phân đúng vào Ci. – FP (false positives): số lượng ví dụ dương được thuật toán phân sai vào Ci. – FN (false negatives): số lượng ví dụ âm được thuật toán phân sai vào Ci. Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ được thuật toán phân lớp vào lớp Ci : ii i i TNTP TP +=Pr Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự thuộc lớp Ci: ii i i FPTP TP +=Re Dựa vào độ chính xác và độ hồi tưởng chuẩn của mỗi lớp, độ chính xác và độ hồi tưởng cho toàn bộ các lớp, tức là { }1 2, ,..., mC C C có thể thu được bằng hai cách : Micro-Average và Macro-Average. • Microaveraging: 1 1 ˆ ( ) m i i m i i i TP Pr TP FP µ = = = + ∑ ∑ 1 1 ˆ ( ) m i i m i i i TP Re TP FN µ = = = + ∑ ∑ • Macroaveraging: 1ˆ m i M i Pr Pr m == ∑ 1ˆ m i M i Re Re m == ∑ Độ chính xác và độ hồi tưởng nếu sử dụng riêng biệt thì chưa đánh giá được năng lực của bộ phân lớp. Vì vậy, đánh giá bộ phân lớp văn bản thường được đo bằng tổ hợp của hai độ đo trên. Các độ đo phổ biến của tổ hợp hai độ đo này là : 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ệ 34 ♦ Break-Even Point (BEP): BEP được đề xuất bởi Lewis, xác định điểm mà tại đó độ chính xác và độ hồi tưởng bằng nhau. Tuy nhiên, trong một số trường hợp không thể xác định được BEP. Ví dụ, nếu chỉ có vài dữ liệu dương và rất nhiều dữ liệu âm, khi đó độ hồi tưởng có thể cao hơn nhiều so với độ chính xác, do đó không thể tính được BEP. ♦ Độ đo Fβ : độ đo Fβ được đề xuất bởi Rijbergen. Nó là độ đo đơn giản được tính từ độ chính xác và độ hồi tưởng phụ thuộc vào độ quan trọng mà người dùng định nghĩa ( β ). Thông thường, β = 1 . Công thức tính độ đo Fβ là : 2 2 ( 1). . . Pr ReF Pr Reβ β β += + Trong trường hợp β=1 chúng ta có F1 là độ đo thông dụng nhất trong việc đánh giá năng lực của các bộ phân lớp. ♦ Độ chính xác trung bình của 11 điểm: độ chính xác là nội suy của 11 điểm mà độ hồi tưởng là 0.0, 0.1, ...., 1.0. Độ đo này được sử dụng khi phương pháp phân lớp tính hạng tài liệu phù hợp với một lớp hoặc lớp tương tự với một tài liệu. Bên cạnh độ chính xác và độ hồi tưởng, một số độ đo phổ biến khác cũng được sử dụng như : tỉ lệ đúng (Accuracy) và tỉ lệ lỗi (Error) kí hiệu là iAc và Eri của lớp Ci : i i i i i i i TP TNAc TP TN FP FN += + + + 1i ii i i i i i FP FNEr Ac TP TN FP FN += = −+ + + 2.3.2. Đánh giá dựa vào độ tương tự Dễ nhận thấy, nếu phương pháp A và B đều không phân tài liệu vào đúng lớp Ci của nó, nhưng phương pháp A phân vào lớp tương tự với lớp Ci hơn thì phương pháp A được đánh giá là tốt hơn so với phương pháp B. Vì vậy, chúng ta sẽ mở rộng định nghĩa độ chính xác và độ hồi tưởng chuẩn để đánh giá bộ phân lớp A và B. 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ệ 35 Độ tương tự giữa hai lớp iC và kC , kí hiệu là ( ),i kCS C C có thể được tính bằng nhiều cách khác nhau. Trong phân lớp văn bản, nếu mỗi tài liệu được biểu diễn là một vector thuộc tính : { }1 1 2 2, ,...,i N NC w t w t w t= { }1 1 2 2, ,..., N Nk vC t v t v t= Độ tương tự (Category Similarity – CS) và độ tương tự trung bình (Average Category Similarity – ACS) được tính theo công thức : ( ) 1 2 2 1 1 , )( N n n n i k N N n n n n w v C w v CS C = = = × = × ∑ ∑ ∑ ( ) ( )1 1 2 , 1 m m i k i k i CS C C ASC m m = = + × = × − ∑ ∑ Trong đó tn là chỉ số từ mục và wn và vn là trọng số từ khoá. Dựa vào độ đo tương tự, chúng ta có thể tính mức độ đúng của việc tài liệu jd được gán vào lớp iC . Trường hợp đơn giản nhất là jd được gán vào đúng lớp iC , tức là j iTPd ∈ , jd được tính là 1 trong công thức tính độ chính xác và độ hồi tưởng của lớp iC . Tuy nhiên, nếu jd không được gán nhãn đúng (tức là j iFPd ∈ ) chúng ta sẽ xem xét độ tương tự của các lớp mà jd được gán nhãn với lớp iC bằng cách tính phân phối của jd đối với lớp iC , kí hiệu là ( ),j id CCon theo công thức : ( ) ( )( ) . , , 1 j i C d lbd j i CS C C ACS d C ACS Con ′∈ ′ − = − ∑ Trong đó, dj.lbd là các lớp mà jd được gán 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ệ 36 Tương tự, nếu jd là dữ liệu âm và thuật toán phân lớp cho giá trị sai, tức là j iFNd ∈ , thì phân phối của jd với lớp iC phụ thuộc vào độ tương tự giữa lớp iC và các lớp chứa jd ( kí hiệu là dj.agd) ( ) ( )( ) . , , 1 j i C d agd j i CS C C ACS d C ACS Con ′∈ ′ − = − ∑ Phân phối của một tài liệu có thể có giá trị âm hoặc dương, phụ thuộc vào độ tương tự giữa các nhãn được gán cho tài liệu và các lớp chứa tài liệu và độ tương tự trung bình ACS. Chú ý rằng một tài liệu có thể thuộc nhiều hơn một lớp. Phân phối của một tài liệu jd với lớp iC được hạn chế trong đoạn [ ]1,1− . Vì vậy, phân phối cải tiến (Refined – Contribution), kí hiệu ( ),j iRCon d C được xác định : ( ) ( )( )( ), min 1,max 1, ,j i j iRCon d C Con d C= − Với tất cả các tài liệu thuộc iFP , tổng phân phối iFpCon sẽ là : ( ), j i i j i d FP FpCon RCon d C ∈ = ∑ Tương tự, tổng phân phối iFnCon là : ( ), j i i j i d FN FnCon RCon d C ∈ = ∑ Độ chính xác và độ hồi tưởng mở rộng cho lớp iC dựa vào độ tương tự được xác định như sau : ( )max 0, i i iCS i i i i TP FpCon FnCon Pr TP FP FnCon + += + + ( )max 0, i i iCS i i i i TP FpCon FnCon Re TP FN FpCon + += + + Ngoài ra, chúng ta cũng có thể đánh giá dựa vào khoảng cách giữa các lớp trong cấu trúc phân cấp. Thay vì sử dụng độ tương tự giữa các lớp, chúng ta sử dụng độ đo khoảng cách giữa các lớp. Khoảng cách giữa hai lớp iC và kC , kí hiệu ( ),i kDis C C được định nghĩa là số đường liên kết giữa iC và kC . Nếu đường liên kết càng ngắn thì hai lớp càng gần nhau hơn. Từ đó, có thể tính được độ hồi tưởng, độ chính xác, độ đo F dựa vào khoảng cách giữa các lớ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ệ 37 Chương III. THỰC NGHIỆM 3.1. Dữ liệu và chương trình Cấu trúc của bộ dữ liệu sử dụng trong thực nghiệm : Mức 1 Mức 2 Mức 3 Alt.atheism Misc.forsale Soc.religion.christian Graphics Os.ms-windows.misc Windows.x Ibm.pc.hardware Com. Sys. Mac.hardware Autos Motor-cycles Baseball Rec. Sport. Hockey Crypt Electronics Med Sci. Space Guns Mideast Politics. Misc Talk. Religion.misc Hình 3.1: Cấu trúc Taxonomy của 20 lớp dữ liệu 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ệ 38 Tập dữ liệu trong chương trình thực nghiệm sử dụng 20 lớp dữ liệu (Lang, 1995) ( chứa 19997 bài báo thuộc 20 chủ đề khác nhau được lấy từ nguồn dữ liệu Usenet. Đây là tập dữ liệu chuẩn được sử dụng trong rất nhiều nghiên cứu về phân lớp văn bản. Đặc điểm của tập dữ liệu này là một số lớp khá giống nhau, ví dụ lớp chủ đề về hệ thống phần cứng của máy IBM và hệ thống phần cứng của máy Macintos, hay các bài báo thuộc chủ đề talk.politics.misc và talk.religion.misc. Một đặc điểm nữa là tập từ vựng của 20 chủ đề rất lớn, nên đòi hỏi các thuật toán phân lớp phải làm việc được với dữ liệu có số chiều lớn. Cấu trúc taxonomy của bộ dữ liệu được biểu diễn như hình 3.1. Tập dữ liệu có tất cả 19997 tài liệu thuộc 20 lớp khác nhau. Vì số lượng dữ liệu lớn nên chương trình thực nghiệm chỉ sử dụng 12 lớp thuộc 3 nhánh: rec, sci, talk: 1. Rec.autos 2. Rec.motor-cycles 3. Rec.sport.baseball 4. Rec.sport.hockey 5. Sci.crypt 6. Sci.electronics 7. Sci.med 8. Sci.space 9. Talk.politics.guns 10. Talk.politics.mideast 11. Talk.politics.misc 12. Talk.religion.misc Tập dữ liệu được chia thành hai tập con rời nhau, tập dữ liệu huấn luyện và tập dữ liệu kiểm tra, theo tỉ lệ tập dữ liệu huấn luyện : tập dữ liệu kiểm tra bằng 2:1. Bảng 3.1: Phân bố dữ liệu học và kiểm tra Tổng số tài liệu 12285 Tập dữ liệu học 8201 Tập dữ liệu kiểm tra 4084 Cấu trúc của 12 lớp dữ liệu lựa chọn trong thực nghiệm được biểu diễn theo cấu trúc taxonomy sau ( Hình 3.2): 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ệ 39 Tiền xử lý văn bản: module tiền xử lý tách văn bản thành các tập từ đơn (không tách các cụm từ). Sau khi tách từ và loại bỏ các từ dừng được liệt kê trong phụ lục A, và một số kí tự đặc biệt delim (delim = _@${}()-[]:;,.=?*&^%#!|+~/\'\), chương trình tính trọng số từ khoá TF.IDF và chương trình đưa mỗi tài liệu về dạng vector các từ mục. Bởi vì SVMs có thể giải quyết tốt với các bài toán có số chiều lớn nên thực nghiệm không làm Trích chọn thuộc tính và loại bỏ các từ mục xuất hiện ít hơn ba lần trong tập dữ liệu học . Mỗi văn bản được biểu diễn trên một dòng và dưới dạng vector như sau: : :<giá trị thuộc tính>.........: GỐC REC SCI TALK AUTOS MOTOR CYCLES SPORT BASEBALL CRYPT ELEC- TRONICS MED SPACE POLITICS RELIGION. MISC GUN MIDEAST MISC HOCKEY Hình 3.2. Cấu trúcTaxonomy tập dữ liệu 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ệ 40 Trong đó: ♦ : biểu diễn chủ đề của văn bản. – Với bài toán phân lớp văn bản nhị phân có giá trị +1 nếu ví dụ thuộc chủ đề đang xét và -1 nếu ví dụ không thuộc chủ đề đang xét. – Với bài toán phân lớp văn bản nhiều lớp là các số nguyên. ♦ : là số nguyên dương, tham chiếu đến tập thuộc tính được lựa chọn trong quá trình tiền xử lý dữ liệu. Văn bản được sắp xếp theo thứ tự tăng dần của . ♦ : biểu diễn độ quan trọng của thuộc tính trong tập dữ liệu học. Mỗi giá trị thuộc tính là một số thực, định dạng gồm 16 chữ số sau dấu phẩy và được tính theo công thức TFIDF: , , | |logl d l d l DTFIDF freq df ⎛ ⎞= ∗ ⎜ ⎟⎝ ⎠ 3.2. Môi trường thực nghiệm. Môi trường thực nghiệm: hệ điều hành Windows XP, vi xử lý Pentium 4, RAM 256. Khóa luận xây dựng chương trình thi hành phân lớp phân cấp được viết trên ngôn ngữ C/C++, môi trường Dev-C++ 4.9.8.0. Chương trình này tích hợp module chương trình tiền xử lý văn bản (do khóa luận xây dựng) và module phân lớp phẳng (khai thác mã nguồn bộ phân lớp SVMs nhị phân phiên bản 6.01, ngày 02/09/2004 tại 3.3. Kết quả và đánh giá 3.3.1. Thực nghiệm1 : Phân lớp phân cấp theo hướng top-down Với bài toán phân lớp phân cấp theo phương pháp top-down, ta cần xây dựng các bộ phân lớp nhánh và bộ phân lớp lá. Mỗi nút trong và nút lá của taxonomy được xây dựng một bộ phân lớp nhị phân. Và các bộ phân lớp này phải được học với cả dữ liệu âm và dữ liệu dương. Việc lựa chọn dữ liệu học cho các bộ phân lớp là rất quan 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ệ 41 trọng và không giống phương pháp lựa chọn tập dưa liệu cho bài toán phân lớp phẳng. Cách lựa chọn tập dữ liệu học cho các bộ phân lớp như phần 2.2.2 trình bày. Với cấu trúc taxonomy như hình 3.2, ta cần xây dựng 3 bộ phân lớp nhánh cho các nút trong tại mức 1; hai bộ phân lớp nhánh tại mức hai và 12 bộ phân lớp cục bộ cho các lá. Tổng cộng, ta cần xây dựng 17 bộ phân lớp, trong đó có 5 bộ phân lớp nhánh và 12 bộ phân lớp cục bộ. Kí hiệu P là số lượng dữ liệu dương, N là số lượng dữ liệu âm. Phân phối dữ liệu học cho các bộ phân lớp được biểu diễn như hình 3.3.a: GỐC P: 2646 REC N: 3024 P: 2667 SCI N: 3048 P: 2888 TALK P: 3304 P: 662 AUTOS N: 1984 P: 661 MOTOR CYCLES N: 1985 P: 1323 SPORT N: 1323 P: 661 BASEBALL N: 662 P: 666 CRYPT N: 2001 P: 667 ELEC- TRONICS N: 2000 P: 668 MED N: 1999 P: 666 SPACE N: 2001 P: 2142 POLITICS N: 746 P: 746 RELIGION. MISC N: 2142 P: 698 GUNS N: 1444 P: 666 MIDEAST N: 1476 P: 778 MISC N: 1364 P: 662 HOCKEY N: 661 Hình 3.3.a: Phân phối dữ liệu học cho các bộ phân lớ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ệ 42 Dữ liệu kiểm tra cũng được xây dựng tương tự như dữ liệu học. Tổng dữ liệu kiểm tra cho toàn bộ taxonomy là 4084 tài liệu thuộc 12 lá. Dữ liệu kiểm tra cho các bộ phân lớp nhánh và bộ phân lớp cục bộ của taxonomy được biểu diễn dưới hình 3.3.b : GỐC 4084 P: 1323 REC N: 2761 P: 1320 SCI N: 2764 P: 1441 TALK P: 2643 P: 308 AUTOS N: 1026 P: 325 MOTOR CYCLES N: 1009 P: 644 SPORT N: 690 P: 322 BASEBALL N: 340 P: 309 CRYPT N: 997 P: 305 ELEC- TRONICS N: 1001 P: 279 MED N: 1027 P: 306 SPACE N: 1000 P: 1073 POLITICS N: 462 P: 322 RELIGION. MISC N: 1213 P: 335 GUNS N: 881 P: 290 MIDEAST N: 856 P: 386 MISC N: 760 P: 319 HOCKEY N: 343 Hình 3.3.b: Phân phối dữ liệu kiểm tra cho các bộ phân lớ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ệ 43 Kết quả phân lớp cho các nút trong của taxonomy được biểu diễn trong bảng 3.2.a và biểu đồ 3.1.a : Bảng 3.2.a: Kết quả phân lớp cho các nút trong của taxonomy Tên lớp Tỉ lệ phân lớp đúng Độ chính xác Độ hồi tưởng Độ đo Fβ ( 1β = ) Rec 97.48% 95.73% 96.52% 96.12% Sci 94.42% 91.81% 90.83% 91.32% Talk 95.49% 90.94% 96.88% 93.82% Rec.sport 98.20% 96.83% 99.53% 98.16% Talk.politics 79.35% 82.98% 88.63% 85.71% 96.12 91.32 93.82 98.16 85.71 78 80 82 84 86 88 90 92 94 96 98 100 rec sci talk rec.sport talk.politics Lớp Đ ộ đo F 1 Biểu đồ 3.1.a: Biểu đồ biểu diễn độ đo F1 của các nút trong 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ệ 44 Nhận xét : Từ biểu đồ 3.1.a, ta thấy rằng, 5 bộ phân lớp nhánh của taxonomy làm việc rất hiệu quả và đạt kết quả cao. Cả 5 bộ phân lớp đều cho độ đo F gần 90%, đặc biệt, bộ phân lớp nhánh Rec.sport đạt kết quả gần 100% cho cả độ chính xác và độ hồi tưởng. Bộ phân lớp nhánh talk.politics thu được kết qủa thấp nhất với độ đo F là 85.71%. Kết quả cho các lá của taxonomy được biểu diễn trong bảng 3.6.b : Bảng 3.2.b: Kết quả phân lớp cho các lá của taxonomy Tên lớp Tỉ lệ phân lớp đúng Độ chính xác Độ hồi tưởng Độ đo Fβ ( 1β = ) Rec.autos 97.00% 94.08% 92.86% 93.47% Rec.motorcycles 97.68% 97.42% 92.29% 94.79% Rec.sport.baseball 94.56% 91.81% 97.52% 94.58% Rec.sport.hockey 96.22% 95.94% 96.24% 96.09% Sci.crypt 96.25% 94.83% 89.00% 91.82% Sci.electronics 92.50% 90.27% 76.07% 82.56% Sci.med 90.02% 95.22% 85.66% 90.19% Sci.space 96.17% 95.82% 89.87% 92.75% Talk.politics.guns 90.49% 81.56% 87.16% 84.27% Talk.politics.mideast 93.54% 94.37% 82.21% 87.87% Talk.politics.misc 83.94% 66.06% 75.17% 70.32% Talk.religion.misc 87.17% 66.07% 79.81% 72.29% 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ệ 45 93.47 94.79 94.58 96.09 91.82 82.56 90.19 92.75 84.27 87.87 70.32 72.29 0 20 40 60 80 100 120 rec .au tos rec .m oto rcy cle s rec .sp or t.b as eb all rec .sp or t.h oc ke y sc i.c ryp t sc i.e lec tro nic s sc i.m ed sc i.s pa ce tal k.p oli tic s.g un s tal k.p oli tic s.m ide as t tal k.p oli tic s.m isc tal k.r eli gio n.m isc Lớp Đ ộ đo F 1 Biểu đồ 3.1.b: Biểu đồ biểu diễn độ đo F1 các lá của taxonomy Kết quả thực nghiệm cho thấy rằng với phương pháp phân lớp phân cấp, kết quả thu được tốt cho cả 12 lá của taxonomy. Lớp Talk.politics.misc đạt kết quả thấp nhất với F1=70.32%, lớp Rec.sport.hockey đạt kết quả cao nhất với F1=96.09%. Sau khi tính tỉ lệ phân lớp đúng, độ chính xác và độ hồi tưởng cho mỗi bộ phân lớp. Một vài độ đo tổ hợp được tính toán theo công thức sau: ♦ Tỉ lệ phân lớp đúng trung bình: 1( ) N i i Acc Avg Acc N == ∑ ♦ Macroaveraging: 1ˆ m i M i Pr Pr m == ∑ 1ˆ m i M i Re Re m == ∑ 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ệ 46 ♦ Độ đo Fβ trung bình tính theo công thức: 1( ) N i F Avg F N β β == ∑ Kết quả được thể hiện như bảng 3.3 : Bảng 3.3 : Kết quả trung bình Tỉ lệ phân lớp đúng trung bình 92.97% Độ chính xác trung bình 89.51% Độ hồi tưởng trung bình 89.19% Độ đo F1 trung bình 89.18% 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. Ta biết rằng, việc lựa chọn tập thuộc tính là rất quan trọng vì nó ảnh hưởng trực tiếp tới thời gian huấn luyện và kết quả phân lớp. Đối với bài toán phân lớp phân cấp, ở các mức trên của cây phân cấp, chỉ cần chọn tập thuộc tính phù hợp nhất để phân biệt giữa các lớp ở mức đó. Quay trở lại hình 2.2, như phần 2.2.1 đã trình bày, “Máy tính” là một thuộc tính rất tốt để phân biệt giữa các lớp ở mức 1. Nếu đi sâu xuống nhánh “Tin học” sẽ có nhiều thuộc tính chuyên biệt hơn để phân biệt giữa các lớp ở nhánh này, và độ quan trọng của thuộc tính “Máy tính” tại nhánh “Tin học” sẽ bị giảm đi. Vì vậy, khoá luận tiến hành một vài thực nghiệm nhằm khảo sát sự phụ thuộc của việc lựa chọn tập thuộc tính tại mức 1 của cây phân cấp hình 3.2 với thời gian huấn luyện và kết quả phân lớp thu được. 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ệ 47 Tập thuộc tính của ba lớp ở mức 1 được thể hiện như sau (Bảng 3.4): REC SCI TALK 16238 18596 19622 Tập thuộc tính được lựa chọn theo độ đo thông tin qua lại(MI) : ( ) ( ) ( ), log A NI t c A C A B ×≈ + × + Thử nghiệm trên ba lần lựa chọn số lượng thuộc tính có MI lớn nhất cho mỗi lớp giảm dần theo thống kê sau (Bảng 3.5) : REC SCI TALK 50% 8119 9296 9622 40% 6495 7436 7697 30% 4871 5577 5773 Sử dụng tập dữ liệu kiểm tra cho ba lớp ở mức 1 như thực nghiệm 1 ta thu được kết quả như sau (Bảng 3.6): Lớp Phần trăm Bảng 3.5 : Số lượng thuộc tính được lựa chọn cho mỗi lớ Bảng 3.4 : Tập thuộc tính của mỗi lớp tại mức 1 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ệ 48 Tỉ lệ phân lớp đúng Độ chính xác Độ hồi tưởng Độ đo Fβ ( 1β = ) Không lựa chọn 97.48% 95.73% 96.52% 96.12% 50% 97.45% 95.79% 96.37% 96.08% 40% 96.84% 95.09% 95.06% 95.08% REC 30% 97.55% 97.51% 94.86% 96.17% Không lựa chọn 94.42% 91.81% 90.83% 91.32% 50% 94.54% 92.22% 90.76% 91.48% SCI 40% 94.86% 92.30% 91.74% 92.02% 30% 95.13% 93.08% 91.74% 92.41% Không lựa chọn 95.49% 90.94% 96.88% 93.82% 50% 95.77% 91.18% 96.81% 93.91% 40% 95.98% 91.87% 97.22% 94.47% TALK 30% 95.94% 93.22% 95.42% 94.31% Độ đo trung bình của cả ba lớp trong từng trường hợp được thể hiện trong bảng 3.7 và biểu đồ 3.2: Bảng 3.6: Kết quả phân lớp cho từng trường hợ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ệ 49 Độ đo Phần trăm Tỉ lệ phân lớp đúng trung bình Độ chính xác trung bình Độ hồi tưởng trung bình Độ đo F1 trung bình Không lựa chọn 95.68% 92.83% 94.74% 93.75% 50% 95.92% 93.06% 94.65% 93.82% 40% 95.89% 93.09% 94.67% 93.86% 305 96.21% 94.60% 94.01% 94.30% 93.57 93.82 93.86 94.3 93.2 93.4 93.6 93.8 94 94.2 94.4 Không lựa chọn 50% 40% 30% Các trường hợp Đ ộ đo F 1 Nhận xét : Từ biểu đồ 3.2, dễ nhận thấy với bài toán phân lớp phân cấp văn bản, khi lựa được tập thuộc tính phù hợp để phân biệt giữa các lớp thì kết quả phân lớp trung bình sẽ tăng lên. Từ bảng 3.6 và 3.7 ta thấy có một số lớp khi tập thuộc tính được rút gọn Bảng 3.7: Kết quả trung bình cho từng trường hợp Biểu đồ 3.2: Độ đo F1 của bộ phân lớp khi sử dụng độ đo thông tin MI 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ệ 50 thì kết quả giảm đi. Điều này là hoàn toàn tự nhiên, và sẽ tồn tại một ngưỡng mà tại đó kết quả phân lớp trung bình sẽ thấp hơn so với khi không lựa chọn tập thuộc tính. Vì vậy, đối với các ứng dụng lớn, cần xem xét lựa chọn ngưỡng phù hợp để kết quả phân lớp cao nhất có thể. REC SCI TALK Tổng thời gian Không lựa chọn 7.44 7.89 8.15 23.48 50% 6.58 7.01 7.65 21.24 40% 4.50 5.02 5.36 14.88 30% 3.12 3.75 3.48 10.35 23.48 21.24 14.88 10.35 0 5 10 15 20 25 Không lựa chọn 50% 40% 30% Phần trăm đặc trưng được lựa chọn Th ờ i g ia n (s ) Bảng 3.8 : Thời gian huấn luyện của từng lớp Biểu đồ 3.3 : Tổng thời gian huấn luyện theo phần trăm thuộc tính được lựa chọ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ệ 51 Lựa chọn được tập thuộc tính phù hợp không những làm tăng kết quả mà một điều rất quan trọng là thời gian huấn luyện các bộ phân lớp sẽ giảm đáng kể. Điều này được thể hiện trong bảng 3.8 biểu diễn thời gian huấn luyện cho từng lớp (tính theo đơn vị giây) cho từng trường hợp. Sự phụ thuộc tổng thời gian huấn luyện của cả ba lớp theo sự lựa chọn thuộc tính được thể hiện như biểu đồ 3.3. Nhận xét: Dễ nhận thấy, tập thuộc tính càng được rút gọn thì tổng thời gian huấn luyện cho cả ba lớp đều giảm đi rõ rệt. Đây là một trong những tiêu chí quan trọng mà các hệ thống phân lớp hướng tới, đặc biệt với các hệ thống lớn. Từ thực nghiệm có thể rút ra kết luận rằng : lựa chọn được tập thuộc tính phù hợp cho các mức của cây phân cấp không chỉ làm giảm thời gian huấn luyện các phân lớp mà còn làm tăng kết quả phân lớp cuối cù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ệ 52 KẾT LUẬN Từ việc nghiên cứu lý thuyết và kết quả thực nghiệm có thể khẳng định rằng bài toán phân lớp phân cấp văn bản thực sự tốt. Đặc biệt, đối với các hệ thống phân lớp mà số lượng các lớp nhiều, thì phân lớp phân cấp văn bản sẽ phát huy được những ưu điểm của mình, không chỉ về kết quả phân lớp mà cả mặt thời gian phân lớp. 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. Về mặt nội dung, khoá luận đã đạt được những kết quả sau : – Nghiên cứu một 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. – Nghiên cứu, phân tích hoạt động các thuật toán kNN, AdaBoost và SVM giải quyết bài toán phân lớp phân cấp. Đề xuất ý tưởng đưa trọng số vào mỗi nút trong quá trình phân lớp phân cấp. – Xây dựng chương trình thi hành phân lớp phân cấp được viết trên ngôn ngữ C/C++, môi trường Dev-C++ 4.9.8.0 được tích hợp từ module chương trình tiền xử lý văn bản (do khóa luận xây dựng) và module phân lớp phẳng (khai thác mã nguồn bộ phân lớp SVM nhị phân phiên bản 6.01). Kết quả thực nghiệm trên tập dữ liệu 20 NewsGroup cho thấy tính khả thi của chương trình phân lớp phân cấp với độ đo F1 xấp xỉ 90%. Bên cạnh đó, do thời gian và kiến thức có hạn, khoá luận vẫn còn một vài hạn chế sau : – Chương trình sử dụng thuật toán SVM cho bài toán phân lớp phân cấp mới thi hành trên một bộ dữ liệu nên chưa có kết quả trên nhiều bộ dữ liệu. Chưa thi hành nhiều thuật toán để chọn được phương án tốt. – Do chưa nhận được độ đo đánh giá phân lớp phân cấp chuẩn nên khóa luận tiến hành đánh giá kết quả phân lớp phân cấp theo các độ đo của phân lớp phẳng là độ chính xác, độ hồi tưởng và độ đo F1. Đây là một hạn chế của khóa luậ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ệ 53 Trong tương lai, khoá luận sẽ tiếp tục hoàn thiện theo hướng sau : – Thử nghiệm trên nhiều bộ dữ liệu khác nhau, đặc biệt áp dụng bài toán phân lớp với các trang Web tiếng Việt. – Sử dụng một số thuật toán phân lớp phẳng khác với SVM để từ đó tìm được thuật toán hiệu quả đối với bài toán phân lớp phân cấp. – Ý tưởng đánh trọng số cho các thuộc tính dựa vào độ sâu của taxonomy chưa tiến hành cài đặt được. Trong thời gian tới, chúng tôi sẽ tiến hành cài đặt chương trình này. 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ệ 54 TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt [1]. Đặng Thanh Hải. Thuật toán phân lớp văn bản web và thực nghiệm trên máy tìm kiếm Viettseek. Khoá luận tốt nghiệp 2004, Trường Đại học Công Nghệ - Đại học Quốc gia Hà Nội Tài liệu Tiếng Anh [2]. Ahswin K Pulijala, Susan Gauch. Hierachical Text Classification, International Conference on Cybernetics and Information Technologies, Systems and Applications: CITSA 2004, Vol. 1, Orlando, FL, July 2004, pp. 257-262. [3]. Aixin Sun and Ee-Peng Lim Hierarchical Text Classification and Evaluation – Proceedings of the 2001 IEEE International Conference on Data Mining (ICDM 2001) Pages 521-528, California, USA, November 2001. [4]. Andrew Mc Callum, Ronald Rosenfeld, Tom Mitchell, Andrew Y.Ng Improving Text Classification by Shrinkage in a Hierarchy of Classes, In Proceedings of The Eighteenth International Conference on Machine Learning, 1998. [5] .D.Wollersheim, W.J.Rahayu Using Medical Test Collection Relevance Judgement to Identify Ontological Relationships Useful for Query Expansion 21st International Conference on Data Engineering 2005. [6]. Daphne Koller, Mehran Sahami Hierarchical classifying documents using very few words Proceedings of the Fourteenth International Conference on Machine Learning (ML-97) pages 170-178, Nashville, Tennessee, July 1997. [7]. Delphi Group, a Perot Systems Company. Information intelligence: Content Classification and the Enterprise Taxonomy Practice, 2004. 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ệ 55 [8]. Fabrizio Sebastiani. Machine Learning in Automated Text Categorization. ACM Computing Survey, 34(1) pages 1-47, 2002. [9]. H.T.Kung, C.H.Wu Content Networks: Taxonomy and New Approaches The Internet as a Large-Scale Complex System, Kihong Park and Walter Willinger (Editors), published by Oxford University Press as part of Sante Fe Institute series, 2002. [10]. Ian H.Witten & Eibe Frank. Data Mining – Practical Machine Learning Tools and Techniques – second Edition Morgan Kaufmann Publishers. [11]. Lijuan Cai, Thomas Hofmann Hierarchical Document Categorization with Support Vector Machines Proceedings of the ACM Conference on Information and Knowledge Management, pages 78-87. [12]. Michael Granitzer. Hierarchical Text Classification using methods from Machine Learning, Master Thesis at Graz University of Technology, submitted by Michael Granitzer – Institute of Theoretical Computer Science (IGI) Graz University of Technology A-8010 Graz, Austria, 27th Octorber 2003. [13].Michael Granitzer,Peter Auer. Experiments With Hierarchical Text Classification. Proceedings of 9th IASTED International Conference on Artifical Interlligence, IASTED, ACTA Press, Benidorm, Spain. [14]. Miguel E.Ruiz , Padmini srinivasan Hierarchical Text Categorization Using Neural Networks Information Retrieval, 2002 Kluwer Academic Publishers. [15].OU Shi-yan, KHOO Christopher S.G, GOH Dion H. Division of Information Studies, Constructing a taxonomy to support multi-document summarization of dissertation abstracts. Proceedings Issue of the 1st International Conference on Universal Digital Library (ICUDL 2005). 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ệ 56 [16]. Pierre Baldi, Paolo Frasconi, Padhraic Smyth. Modeling the Internet and the Web: Probabilistic Methods and Algorithms, Published by John Wiley & Sons Ltd, The Southern Gate, Chichester West Sussex PO19 8SQ, England - 2003. [17]. Shrikanth Shankar, George Karypis. A weight adjustment algorithm for document categorization, SIGKDD Wordshop on Text Mining, Boston, MA. [18]. Soumen Chakrabarti, Indian Institute of Technology, Bombay, trang 183-188, Mining the web- discovering knowledge from Hypertext Data Morgan Kaufman Publishers. [19]. Soumen Chakrabarti, Byron Dom. Rakesh Agrawal, Prabhakar Raghavan Using taxonomy, discriminats, and signatures for navigating in text databases, Proceedings of the International Conference on Very Large Data Bases (VLDB). [20]. Svetlane Kiritchenko. Hierarchical Text Categorization and Its Application to Bioinformatics, Ph.D thesis in Computer Science – School of Information Technology and Engineering Faculty of Engineering University of Ottawa, Canada 2005. [21]. Susan Dumais, Hao Chen - Hierarchical Classification of Web Content, Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR), pages 256-263. [22]. Yiming Yang, Jan O.Pedersen A Comparative Study on Feature Selection in Text Categorization. Proceedings of the Fourteenth Internationcal Conference on Machine Learning (ICML ’97), 412-420, 1997. [23]. Yongwook Yoon, Changkl Lee, Gary Geunbae Lee An effective procedure for constructing a hierarchical text classification system. Journal of American Society for Information Science and Technology (JASIST), 57(3), (pp. 431-442). [24]. 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ệ 57 PHỤ LỤC A. DANH SÁCH TỪ DỪNG Danh sách các từ dừng được sử dụng trong thực nghiệm : (danh sách các từ dừng được sử dụng từ nguồn BOW toolkit – Andrew McCallum 1998,1999) a, able, about, above, according, accordingly, across, actually, after, afterwards, again, against, all, allow, allows, almost, alone, along, already, also, although, always, am, among, amongst, an, and, another, any, anybody, anyhow, anyone, anything, anyway, anyways, anywhere, apart, appear, appreciate, appropriate, are, around, as, aside, ask, asking, associated, at, available, away, awfully. b, be, became, because, become, becomes, becoming, been, before, beforehand, behind, being, believe, below, beside, besides, best, better, between, beyond, both, brief, but, by. c, came, can, cannot, cant, cause, causes, certain, certainly, changes, clearly, co, com, come, comes, concerning, consequently, consider, considering, contains, corresponding, could, course, currently. d, definitely, described, despite, did, different, do, does, doing, done, down, downwards, during. e, each, edu, eg, eight, either, else, elsewhere, enough, entirely, especially, et, etc, even, ever, every, everybody, everyone, everything, everywhere, ex, exactly, example, except. f, far, few, fifth, first, five, followed, following, follows, for, former, formerly, forth, four, from, further, furthermore. g, get, gets, getting, given, gives, go, goes, going, gone, got, gotten, greetings. h, had, happens, hardly, has, have, having, he, hello, help, hence, her, here, hereafter, hereby, herein, hereupon, hers, herself, hi, him, himsefl, his, hither, hopefully, how, howbeit, however. 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ệ 58 i, ie, if, ignored, immediate, in, inasmuch, inc, indeed, indicate, indicated, indicates, inner, insofar, instead, into, inward, is, it, its, itsefl. j, just, k, keep, kept, know, knows, known. l, last, lately, later, latter, latterly, least, less, lest, let, like, liked, likely, little, look, looking, looks, ltd. m, mainly, many, may, maybe, me, mean, meanwhile, merely, might, more, moreover, most, much, must, my, mysefl. n, name, namely, nd, near, nearly, necessary, need, needs, neither, never, nevertheless, new, next, nine, no, nobody, non, none, noone, nor, normally, not, nothing, novel, now, nowhere. o, obviously, of, off, often, oh, ok, okay, old, on, once, one, ones, only, onto, or, other, others, otherwise, ought, our, ours, ourselses, out, outside, overall, own. p, particular, particularly, per, perhaps, placed, please, plus, possible, presumably, probably, provides. q, que, quite, qv. r, rather, rd, re, really, reasonably, regarding, regardless, regards, relatively, respectively, right. s, said, same, saw, say, saying, says, second, secondly, see, seeing, seem, seeming, seems, seen, self, selves, sensible, sent, serious, seriously, seven, shall, she, should, since, six, so, some, somebody, somehow, someone, something, sometime, sometimes, somewhat, somewhere, soon, sorry, specified, specify, specifying, still, sub, such, sup, sure. t, take, taken, tell, tends, th, than, thank, thanks, thanx, that, thats, the, their, theirs, them, themselves, then, thence, there, thereafter, thereby, therefore, therein, theres, thereupon, these, they, think, third, this, thorough, thoroughly, those, though, three, through, throughout, thru, thus, to, together, too, took, toward, towards, tried, tries, truly, try, trying, twice, two. 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ệ 59 u, un, under, unfortunately, unless, unlikely, until, unto, up, upon, us, use, used, useful, uses, using, usually, uucp. v, value, various, very, via, viz, vs w, want, wants, was, way, we, welcome, well, went, were, what, whatever, when, whence, whenever, where, whereafter, whereas, whereby, wherein, whereupon, wherever, which, while, whither, who, whoever, whole, whom, whose, why, will, willing, wish, with, within, without, wonder, would. x, y, yes, yet, you, your, yours, yourself, yourselves, z, zero.