Luận văn Tự động tổng hợp và phân loại tin trong hệ thống trang tin điện tử

ua kém nhiều so với SVM [15],[16]. Khóa luận cũng trình bày phương pháp đánh giá hiệu quả của cây phân lớp dựa vào các độ đo là độ chính xác (P), độ hồi tưởng (R) và độ đo (F1). 2.1. Xây dựng crawler 2.1.1. Khái niệm crawler Kích thước quá lớn và bản chất thay đổi không ngừng của Web đặt ra một nhu cầu mang tính nguyên tắc là, cần phải cập nhật không ngừng tài nguyên cho các hệ thống trích chọn thông tin trên Web. Thành phần crawler đáp ứng được nhu cầu này bằng cách đi theo các siêu liên kết trên các trang Web để tải về một cách tự động nội dung các trang Web. Web crawler khai thác sơ đồ cấu trúc của Web để duyệt không gian Web bằng cách chuyển từ trang Web này sang trang Web khác. 9 Hình 3. Sơ đồ cơ bản của một crawler đơn luồng [12] Hình vẽ biểu diễn sơ đồ khối một crawler đơn luồng. Chương trình crawler yêu cầu một danh sách các URL chưa được thăm (frontier). Ban đầu frontier chứa các URL hạt nhân do người dùng hoặc chương trình khác cung cấp. Mỗi vòng lắp crawling bao gồm: lấy ra các URL tiếp theo cần được tải về từ frontier, nạp trang Web tương ứng với URL đó bằng giao thức HTTP, chuyển nội dung trang Web vừa được tải về cho phục vụ kho chứa trang Web. Quá trình crawling được kết theo theo hai tình huống: - Đạt được điều kiện dừng cho trước, chẳng hạn như số lượng các trang Web được tải về đã đáp ứng được yêu cầu đặt ra. - Danh sách các URL tại frontier rỗng, không còn trang Web yêu cầu crawler phải tải về. Lưu ý rằng, điều kiện frontier rỗng được tính với một độ trễ nào đó, bởi có [done] [no URL] Cr aw lin g Lo o p Initialize frontier with seed URLs start Check for termination [not done] Fetch page Parse page Add URLs to frontier [URL] Pitch URL from frontier end 10 một số trường hợp, bộ điều khiển crawling chưa chuyển kịp các dánh sách URL sẽ tới thăm. Hoạt động của thành phần crawler có thể được xem như một bài toán duyệt đồ thị. Toàn bộ thế giới được Web xem như một đồ thị lớn với các đỉnh là các trang Web và các cung là các siêu liên kết. Quá trình tải một trang Web và đi tới một trang Web mới tương tự như quá trình mở rộng một đỉnh trong bài toán tìm kiếm trên đồ thị [2]. 2.1.2. Xây dựng crawler Đối với một trang Web X, muốn tổng hợp được những tin tức mới nhất của nó, trước tiên cần gieo cho frontier một hạt giống là URL trang Home (hoặc trang Portal) của Web X đó. Ví dụ đối với vnexpress.net thì trang Home có URL là: Dùng giao thức HTTP để tải về mã html - gọi là Y - của URL hạt giống. Mã html Y chứa rất nhiều các URL, trong đó chỉ một bộ phận nhỏ URL là siêu liên kết đến các detail-page của một tin bài cụ thể là có giá trị, còn phần lớn các URL có trong Y đều là liên kết không liên quan, chủ yếu là các liên kết quảng cáo... Nếu đưa tất cả các siêu liên kết này vào frontier thì sẽ là không tối ưu, do frontier phải duyệt qua các URL không chứa nội dung thông tin, như vậy sẽ ảnh hưởng đến tốc độ cập nhật tin mới của hệ thống, có thể gặp phải trường hợp như tin247.com ở trên. Để lấy được các URL chứa nội dung thông tin cần thiết (phù hợp), khóa luận đưa ra một tập mẫu cho phép nhận dạng thẻ HTML chứa siêu liên kết tới detail-page. Ví dụ đối với báo vnexpress.net, từ mã html của trang Home có thể dễ dàng nhận biết được các tin có nội dung thông tin được chứa trong các thẻ HTML với tên class như là link-topnews, folder-topnews, other-foldernews, link-othernews hay link-title. Tập dữ liệu đặc trưng này giúp dễ dàng nhận diện và lấy ra các siêu liên kết chứa nội dung thông tin đưa vào frontier. Để lấy được các tin mới một cách nhanh nhất, crawler dừng quá trình thêm vào URL vào frontier sau chỉ một lần duyệt frontier hạt giống. Sau khi toàn bộ URL thuộc frontier được xử lý hết, crawler được tạm dừng (delay) trong một khoảng thời gian xác định trước khi lặp lại quá trình. 11 Việc xây dựng crawler cũng chính là xây dựng luật lấy URL từ tập các đặc trưng. 2.2. Xây dựng bộ trích chọn thông tin 2.2.1. Trích chọn thông tin trên tài liệu Web Web là dữ liệu điển hình trong dữ liệu bán cấu trúc. Trích xuất thông tin Web đó là vấn đề trích xuất các thành phần thông tin mục tiêu từ những trang Web. Một chương trình hay một luật trích xuất thường được gọi là một wrapper [4]. Bài toán trích xuất thông tin cho dữ liệu bán cấu trúc là rất hữu dụng bởi vì nó cho phép thu thập và tích hợp dữ liệu từ nhiều nguồn để cung cấp cho những dịch vụ giá trị gia tăng như : thu được những thông tin Web một cách tùy ý, meta-search, hay các hệ thống tổng hợp tin tức. Ngày càng nhiều các công ty, các tổ chức phổ cập các thông tin ở trên Web, thì khả năng trích xuất dữ liệu từ các trang Web đó ngày càng trở nên quan trọng. Bài toán này đã được bắt đầu nghiên cứu vào giữa những năm của thập niên 1990 bởi nhiều công ty và các nhà nghiên cứu [4]. Thông tin bán cấu trúc trên Web rất đa dạng và phụ thuộc vào cách lưu trữ và trình bày của từng webstie cụ thể Trích trọng trông tin, dữ liệu từ những tài liệu Web bán cấu trúc là một vấn đề rất quan trọng trong trích chọn dữ liệu nói chung. Các Website thường được trình bày theo nhiều cách rất đa dạng, sử dụng nhiều định dạng về bảng biểu, màu sắc, font chữ, hình ảnh,... nhằm tạo ra sự bắt mắt, thoải mái cho bạn đọc. Đặc điểm của các thông tin, dữ liệu tồn tại ở dạng bán cấu trúc là ngoài những từ khóa (ngôn ngữ tự nhiên) thì còn những cứ liệu (evidence) khác như bảng biểu, danh sách, kích thước font chữ, màu sắc, định dạng, các thẻ HTML... giúp quá trình trích chọn dễ dàng khả thi hơn. Các phương pháp trích chọn thông tin dạng bán cấu trúc cũng thường phải tận dụng được hết các căn cứ này. 2.2.2. Xây dựng bộ trích chọn tài liệu Web Đối với một trang tổng hợp tin tức, việc trích chọn tài liệu cần phải lấy ra được các phần nội dung sau: - Phần bắt đầu và kết thúc bài báo từ đó trích rút ra các nội dung kế tiếp. 12 - Tiêu đề bài báo - Tóm tắt - Ảnh minh họa - Phần thân bài báo Tương tự với việc trích rút ra các URL để đưa vào frontier như phần crawler (2.1.2). Xậy dựng bộ trích chọn tài liệu cũng là việc tạo ra một tập gồm các đặc trưng, cho phép nhận biết để trích rút được các nội dung cần thiết như trình bày ở trên. Chính tập các đặc trưng này, kết hợp với URL hạt giống và tập các đặc trưng nhận biết URL chứa nội dung thông tin (được trình bày trong phần 2.1.2) tạo nên một tập dữ liệu đầu vào, cho phép crawling, trích chọn ra nội dung thông tin của một trang Web bất kì. 2.3. Xây dựng bộ phân lớp 2.3.1. Khái niệm phân lớp văn bản Phân lớp là một trong những mối quan tầm nhiều nhất của con người trong quá trình làm việc với một tập hợp đối tượng. Điều này giúp con người có thể tiến hành việc sắp xếp, tìm kiếm các đối tượng, một cách thuận lợi. Khi biểu diễn đối tượng vào hệ thống thông tin, tính chất lớp vốn có của đối tượng trong thực tế thường được biểu diễn bằng một thuộc tính “lớp” riêng biệt. Chẳng hạn, trong hệ thống thông tin quản lý tư liệu thuộc thư viện, thuộc tính về loại tư liệu có miền giá trị là tập tên chuyên nghành của tư liệu, gồm các giá trị như “Tin học”, “Vật lý”,... Trước đây các công việc gán các giá trị của thuộc tính lớp thường được làm một cách thủ công. Nhưng hiên nay, với sự bùng nổ của thông tin và các loại dữ liệu, việc đánh thuộc tính lớp một cách thủ công là rất khó khăn, có thể nói là không thể. Do vậy, cácphương pháp phân lớp tự động, trong đó có phân lớp văn bản là rất cần thiết và là một trong những chủ đề chính của khai phá dữ liệu. Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán tên các chủ đề (tên lớp/nhãn lớp) đã được xác định cho trước vào các văn bản dựa trên nội dung của nó. Phân lớp văn bản là công việc được sự dụng để hỗ trợ trong quá trình tìm kiếm thông tin (Information Retrieval), chiết lọc thông tin (Information Extraction), lọc văn bản hoặc tự động dẫn đường cho các văn bản tới những chủ đề xác định trước. 13 Hình 4. Lược đồ chung xây dựng bộ phân lớp văn bản Hình 4 biểu diễn một lược đồ chung cho hệ thống phân lớp văn bản, trong đó bao gồm ba thành phần chính: thành phần đầu tiên là biểu diễn văn bản, tức là chuyển các dữ liệu văn bản thành một dạng có cấu trúc nào đó. Thành phần thứ hai là học quy nạp – sử dụng các kỹ thuật học máy để phân lớp văn bản vừa biểu diễn. Thành phần thứ ba là tri thức ngoài – bổ sung các kiến thức thêm vào do người dung cung cấp để làm tăng độ chính xác trong biểu diễn văn bản hay trong quá trình học máy. Trong nhiều trường hợp, các phương pháp học hệ thống phân lớp có thể bỏ qua thành phần thứ ba này. Thành phần thứ hai được coi là trung tâm của một hệ thống phân lớp văn bản. Trong thành phần này, có nhiều phương pháp học máy được áp dụng như mô hình học Bayes, cây quyết định, phương pháp k láng giềng gần nhất, SVM, entropy cực đại (maximum entropy),... là phù hợp [2]. Dữ liệu văn bản Tri thức ngoài Học quy nạp Các công cụ phân lớp Biểu diễn ban đầu Biểu diễn ban Biểu diễn cuối Làm giảm số chiều hoặc lựa chọn thuộc tính (1) 14 2.3.2. Áp dụng thuật toán phân lớp entropy cực đại xây dựng bộ phân lớp văn bản Rất nhiều bài toán trong lĩnh vực xử lý ngôn ngữ tự nhiên (NLP) có thể được xem xét dưới dạng các bài toán phân lớp với việc ước lượng xác suất có điều kiện ( ),p a b của “lớp” a (class) xuất hiện trong “ngữ cảnh” b (context) hay nói cách khác là ước lượng xác suất xuất hiện của a với điều kiện b. Ngữ cảnh thường bao gồm các từ và việc chọn ngữ cảnh phụ thuộc theo từng bài toán cụ thể. Ngữ cảnh b có thể là một từ đơn lẻ, cũng có thể chứa một số từ xung quanh hoặc các từ cùng với các nhãn cú pháp tương ứng. Một lượng văn bản lớn sẽ cung cấp rất nhiều thông tin về sự xuất hiện đồng thời của các lớp a và ngữ cảnh b, nhưng lượng văn bản đó chắc chắn sẽ không đủ để chỉ ra một cách chính xác xác suất ( ),p a b của mọi cặp ( ),a b vì các từ trong b thường nằm rải rác. Do đó cần phải tìm một phương pháp ước lượng (có thể tin tưởng được) mô hình xác suất có điều kiện ( ),p a b sử dụng các cứ liệu về sự xuất hiện đồng thời của lớp a và ngữ cảnh b. Mô hình xác suất entropy cực đại cung cấp một cách đơn giản để kết hợp các cứ liệu ngữ cảnh khác nhau để ước lượng xác suất của một số lớp ngôn ngữ xuất hiện cùng với một số ngữ cảnh ngôn ngữ. 2.3.2.1. Biểu diễn các đặc trưng Theo [1],[7] các đặc trưng (feature) được biểu diễn bằng các mệnh đề biểu diễn thông tin ngữ cảnh (context predicate). Nếu A là tập các lớp thực hiện phân lớp và B là tập các ngữ cảnh mà quan sát được, thì mệnh đề biểu diễn thông tin ngữ cảnh là một hàm được mô tả như sau: : { , }cp B true false→ Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc không xuất hiện của các thông tin hữu ích trong một số ngữ cảnh b B∈ . Tập các mệnh đề biểu diễn thông tin ngữ cảnh được sử dụng rất nhiều trong các bài toán tuy nhiên với mỗi bài toán thì người thực nghiệm phải cung cấp một tập thông tin ngữ cảnh riêng. Các mệnh đề biểu diễn thông tin ngữ cảnh được sử dụng trong các đặc trưng – đó là một hàm có dạng như sau: : {0,1}f A B× → 15 Và được mô tả dưới dạng: ( ) ( ) , ' 1 ' and , 0cp a if a a cp b truef a b other  = = =   Hàm này kiểm tra sự xuất hiện đồng thời của lớp dự đoán a' với mệnh đề biểu diễn thông tin ngữ cảnh cp. Ví dụ nếu trong bài toán xuất hiện: - a' là lớp “THETHAO”, b là văn bản hiện tại. - cp = [ văn bản hiện tại chứa cụm từ “bóng_đá” ]. thì hàm đặc điểm này sẽ trả về giá trị 1 nếu như lớp dự đoán a là “THETHAO”. 2.3.2.2. Cách tiếp cận theo ngữ liệu Cho rằng tồn tại một tập dữ liệu huấn luyện 1 1{( , ),..., ( , )}N NT a b a b= trong đó một tập hợp lớn các ngữ cảnh 1{ , , }Nb b… được gắn nhãn tương ứng trong tập hợp các lớp 1{ , , }Na a… , sau đó tiến hành học cho mô hình phân lớp entropy cực đại trên tập dữ liệu huấn luyện đó. Ý tưởng tập dữ liệu huấn luyện bao gồm các cặp, mỗi cặp là một véc-tơ giá trị logic cùng với một lớp tương ứng rất phổ biến và được sử dụng với rất nhiều các thuật toán được mô tả trong các tài liệu về học máy.
Học với ước lượng likelihood cực đại trên mô hình mũ Để kết hợp các cứ liệu ta có thể đánh trọng số cho các đặc trưng bằng cách sử dụng một mô hình log-linear hay mô hình mũ: ( ) ( ) ( ), 1 1 , i k f a b i i p a b Z b λ = = ∏ (1) ( ) ( ), 1 i k f a b i a i Z b λ = =∑∏ trong đó k là số lượng các đặc trưng và ( )Z b là biểu thức chuẩn hóa để đảm bảo điều kiện ( | ) 1 a p a b =∑ . Mỗi tham số iλ tương ứng với một đặc điểm if và có thể được hiểu là “trọng số” của đặc điểm tương ứng ( iλ > 0). Khi đó xác suất ( ),p a b là kết quả được chuẩn hoá của các đặc trưng có ý nghĩa với cặp ( ),a b , tức là với các đặc điểm if mà 16 ( , ) 1if a b = . Các trọng số 1{ , , }kλ λ… của phân phối xác suất *p là phân phối xác suất phù hợp nhất với tập dữ liệu huấn luyện có thể xác định thông qua một kĩ thuật phổ biến của ước lượng likelihood cực đại: ( , ) 1 1{ | ( | ) }( ) i k f a b i i Q p p a b Z b λ = = = ∏ , ( ) ( , ) log ( , ) a b L p p a b p a b=∑ * arg max ( ) q Q p L q ∈ = trong đó Q là tập hợp các mô hình của dạng log-linear, ( | )p a b là xác suất thực nghiệm trên tập T, ( )L p là log-likelihood có điều kiện của tập dữ liệu huấn luyện T (được chuẩn hoá bởi số lượng sự kiện huấn luyện) và *p là phân phối xác suất tối ưu phụ thuộc theo tiêu chuẩn likelihood cực đại.
Học dưới mô hình entropy cực đại Trong khi có rất nhiều cách để kết hợp các cứ liệu dưới dạng nào đó của một mô hình phân phối xác suất, dạng (1) có tính tích cực riêng dưới hình mẫu entropy cực đại. Nguyên lý entropy cực đại trong [17] chỉ ra rằng mô hình xác suất tốt nhất cho dữ liệu là mô hình làm cực đại giá trị entropy trong số các mô hình phân phối xác suất thoả mãn các cứ liệu. 2.3.2.3. Mô hình entropy cực đại có điều kiện Trong hình mẫu được dùng để giải quyết bài toán đặt ra, có k đặc trưng và khi cho trước một lớp a A∈ cùng với một ngữ cảnh b B∈ thì công việc là phải tìm một ước lượng cho xác suất có điều kiện ( ),p a b . Trong các hình mẫu entropy cực đại có điều kiện được sử dụng trong các nghiên cứu [5],[8],[11],[13],[16],[18], lời giải tối ưu *p là phân phối “không chắc chắn nhất” (entropy đạt cực đại) thoả mãn k ràng buộc trên các kì vọng của các đặc điểm: * arg max ( ) p P p H p ∈ = , ( ) ( , ) log ( , ) a b H p p a b p a b=∑ 17 { | , {1... }}p i ipP p E f E f i k= = = , ( , ) ( , )i ip a b E f p a b f a b=∑ , ( ) ( , ) ( , )p i i a b E f p b p a b f a b=∑ Ở đây ( )H p kí hiệu cho entropy có điều kiện được tính trung bình trên tập huấn luyện, khác với entropy kết hợp, và xác suất biên của b sử dụng ở đây là xác suất thực nghiệm ( )p b , khác với xác suất mô hình ( )p b . p iE f là kì vọng của mô hình p của if , nó sử dụng ( )p b làm một xác suất biên. Tương tự như vậy ipE f là kì vọng thực nghiệm của p của if . ( , )p a b kí hiệu cho xác suất thực nghiệm của ( ),a b trong một số mẫu huấn luyện nhất định. Và cuối cùng P kí hiệu cho tập các mô hình xác suất thoả mãn các cứ liệu quan sát được. 2.3.2.4. Mối quan hệ với likelihood cực đại Thông thường hình mẫu likelihood cực đại và entropy cực đại là hai cách tiếp cận khác nhau trong mô hình hoá thống kê, nhưng chúng có cùng câu trả lời trong trường hợp này. Có thể thấy rằng việc ước lượng tham số của likelihood cực đại cho mô hình của dạng (1) tương đương với việc ước lượng tham số của entropy cực đại trên tập các mô hình thoả mãn. Điều đó có nghĩa là: * arg max ( ) arg max ( ) q Q p P p L q H p ∈ ∈ = = Điều này được mô tả trong [3] sử dụng lý thuyết thừa số nhân lagrange và trong [11] với các đối số lý thuyết thông tin (đối với trường hợp *p là một mô hình kết hợp). Dưới tiêu chuẩn likelihood cực đại, *p sẽ phù hợp với dữ liệu ở mức gần nhất có thể, trong khi đó dưới tiêu chuẩn entropy cực đại, *p sẽ không giả định bất kì điều gì vượt quá những trông tin trong các ràng buộc tuyến tính định nghĩa ra P. Trong [18] trình bày các chứng minh cho thấy rằng điều kiện * arg max ( ) q Q p L q ∈ = là tương đương với điều kiện * arg max ( ) p P p H p ∈ = . Điều này rất quan trọng để thấy rằng dạng (1) không phải là đưa ra 18 một cách không có căn cứ, lời giải cho entropy cực đại * arg max ( ) p P p H p ∈ = phải có dạng này. Sự tương đương này đã cung cấp một phương pháp mới cho phép ước lượng tham số cho các mô hình dựa trên nguyên lý entropy cực đại bằng cách sử dụng các phép ước lượng tham số cho likelihood cực đại. 2.3.2.5. Các thuật toán ước lượng tham số Cho tập huấn luyện 1 1{( , ),..., ( , )}N NT a b a b= . Phân phối mũ: ( ) ( ) ( ), 1 1| i k f a b i i p a b Z b λ = = ∏ trong đó 1{ ... }kλ λ λ= là tập trọng số, ( ) ( ), 1 i k f a b i a i Z b λ = =∑∏ là thừa số chuẩn hoá. Huấn luyện mô hình entropy cực đại chính là ước lượng tập trọng số 1{ ... }kλ λ λ= để cho phân phối ở trên đạt entropy cao nhất. Các thuật toán phổ biến được sử dụng bao gồm: Thuật toán GIS – Generalized Iterative Scaling – được đưa ra trong [8]; Thuật toán IIS – Improved Iterative Scaling – được đưa ra trong [11] là thuật toán ước lượng tham số của mô hình mũ do các thành viên trong nhóm nghiên cứu tại IBM’s T. J. Watson Research Center đưa ra vào những năm đầu của thập kỉ 90; Thuật toán L-BFGS – Limited memory BFGS – là phương pháp giới hạn bộ nhớ cho phương pháp quasi-Newton. 2.3.3. Phương pháp đánh giá hiệu suất phân lớp Việc đánh giá độ phân lớp dựa trên việc áp dụng mô hình đối với các dữ liệu thuộc tập dữ liệu kiểm tra testD , sử dụng mô hình cho từng trường hợp dữ liệu ở testD mà kết quả ra là lớp c dự báo cho từng dữ liệu. Hai độ đo được dùng phổ biến để đánh giá chất lượng của thuật toán phân lớp là độ hồi tưởng (recall) R và đọ chính xác (precision) P. Ngoài ra, một số độ đo kết hợp được xây dựng từ các độ đo này cũng được sử dụng, trong đó điển hình nhất là độ đo F1. Phần dưới đây trình bày các tính toán chi tiết giá trị của các độ đo hồi tưởng và độ chính xác trong bài toán phân lớp văn bản. 19 Xét trường hợp lực lượng của tập C các lớp trong bài toán lớn hơn hai (|C| > 2) với lưu ý rằng, trường hợp tập C chỉ gồm có hai lớp là đơn giản. Đối với lớp c, cho thực hiện mô hình phân lớp vừa được xác định với các dữ liệu thuộc testD nhận được các đại lượng cTP , cTN , cFP , cFN như bảng dưới đây: Giá trị thực tế Lớp c Thuộc lớp c Không thuộc lớp c Thuộc lớp c cTP cTN Giá trị qua bộ phân lớp Không thuộc lớp c cFP cFN Diễn giải bằng lời cho từng giá trị trong bảng: - cTP (true positives): số lượng ví dụ dương (tài liệu thực sự thuộc lớp c) được thuật toán phân lớp gán cho giá trị đúng thuộc lớp c. - cTN (true negatives): số lượng ví dụ âm (tài liệu thực sự không thuộc c) nhưng lại được thuật toán phân lớp gán cho giá trị đúng thuộc lớp c. - cFP (false positives): số lượng ví dụ dương được thuật toán phân lớp gán cho giá trị sai là không thuộc lớp c. - cFN (false negatives): số lượng ví dụ âm được thuật toán phân lớp gán cho giá trị sai là không thuộc lớp c. Khi đó, với mỗi lớp c, giá trị các độ đo cR và cP được tính như sau: c c c c TPR TP FP = + và c c c c TPP TP TN = + Với bài toán phân lớp nhị phân, các độ đo nói trên cho một lớp trong hai lớp là đủ để đánh giá chất lượng bộ phân lớp, tuy nhiên, trong trường hợp bài toán phân lớp K lớp, các Bảng 1. Các nhóm tài liệu sau phân lớp 20 độ đo trung bình được sử dụng bao gồm trung bình mịn (microaveraging) và trung bình thô (macroaveaging). Độ hồi tưởng trung bình thô (macroaveraging recall): 1 1 KM c c R R K = = ∑ và độ chính xác trung bình thô (macroaveaging precision): 1 1 KM c c P P K = = ∑ Độ hồi tưởng trung bình mịn (microaveraging recall): 1 1 ( ) K c M c K c c c TP P TP FP = = = + ∑ ∑ và độ chính xác trung bình mịn (microaveraging precision): 1 1 ( ) K c M c K c c c TP P TP TN = = = + ∑ ∑ Các độ đo trung bình mịn được coi là các độ đo tốt hơn để đánh giá chất lượng thuật toán phân lớp đa lớp tài liệu [2]. 21 Chương 3. Xây dựng hệ thống tổng hợp và phân loại tin tự động Việc xây dụng hệ thống tổng hợp và phân loại tin tự động là vấn đề quan trọng nhất của khóa luận. Ở chương này, khóa luận sẽ trình bày các bước xây dựng mô hình hệ thống trên cơ sở lý thuyết được trình bày trong chương 2. 3.1. Cơ sở thực tiễn Hiện nay, các trang Web đều được xây dựng bởi các ngôn ngữ lập trình Web như PHP, ASP.NET,... Nó cho phép sinh ra siêu văn bản một cách tự động. Khi một tin tức được đăng tải trên một báo điện tử, thì nó tuân theo định dạng HTML nhất định được sinh ra tự động. Điều này có nghĩa là, khi biết mẫu để trích xuất một tin trong một khuôn mẫu, thì cũng có thể trích xuất được tin ở trang có cùng khuôn mẫu đó. Ví dụ: Ở trang tin vnexpress.net, hai bài báo ở hình 5a và 5b là hai tin bài trong hai mục báo khác nhau Hình 5a. Mô tả phần nội dung cần lấy trên trang tin 1 22 Hình 5b. Mô tả phần nội dung cần lấy trên trang tin 2 Mặc dù detail-pages của chúng khác nhau nhưng chúng có cùng một câu DOM => có nghĩa là có cùng một khuôn mẫu. Hình 6. Mô hình cây DOM của 2 detail-pages HTML TABLE TD DIV TD BODY BODY TR TR Nội dung bài báo Quảng cáo 23 2 detail-pages này có cùng một cây DOM, nhưng khóa luận không sử dụng trích chọn thông tin dựa trên mô hình cây DOM mà sử dụng đặc trưng mẫu để tìm ra các nội dung thông tin cần thiết. Các đặc trưng này được thể hiện như trong hình 7a và 7b. Hình 7a. Các đặc trưng cho phép trích chọn thông tin bài báo 1 24 Hình 7b. Các đặc trưng cho phép trích chọn thông tin bài báo 2 Từ mẫu tìm được, dễ dàng nhận ra phần nội dung thông tin cần thiết, điều đó khiến việc trích chọn ra nội dung thông tin cần thiết là hết sức đơn giản. 3.2. Xây dựng mô hình hệ thống Trên cơ sở thực tiễn và mô hình lý thuyết đã phân tích ở chương 2, tiếp theo khóa luận sẽ trình bày mô hình hóa hệ thống tổng hợp và phân loại tin tức. Các module cấu thành sẽ cho thấy tính mở của hệ thống, cho phép dễ dàng mở rộng khi cần. 25 3.2.1. Mô hình tổng quan Hình 8. Mô hình tổng quan của hệ thống tổng hợp và phân loại tin tức Mô tả bài toán Đầu vào: File cấu hình hệ thống xnews.conf Đầu ra: Các tin tức đã được phân tích và tách thành các phần bao gồm: tiêu đề, tóm tắt, ảnh minh họa, nội dung... ghi vào CSDL. File cấu hình xnews.conf chứa tập các URLs hạt giống, tương ứng với mỗi URL hạt giống là một loạt các mẫu, cho phép trích xuất thông tin như mong đợi. Định dạng xnews.conf được trình bày như sau: Dòng 1: Chứa số nguyên dương N, với N là số nguồn sẽ sử dụng để tổng hợp tin tức. 8 dòng tiếp theo được trình bày theo định dạng cố định và lặp lại N lần 26 1. URL hạt giống 2. Dấu hiệu nhận biết link con cần lấy 3. Bắt đầu phần nội dung 4. Kết thúc phần nội dung 5. Tiêu đề bài báo 6. Đoạn tóm tắt nội dung chính 7. Tác giả bài báo 8. Dòng trống Đối với cụm 8 dòng này thì: 7 dòng đầu tiên chứa thông tin về một Web tin tức, nó cho phép crawl, trích xuất tất cả các tin bài cần lấy của Web tin tức đó. Dòng thứ 8 được để trống. Ví dụ đối với báo vnexpress.net để có thể lấy được đầy đủ các tin bài cần thiết, khóa luận xây dựng một bộ gồm các mẫu như sau: ~ ~class="link-topnews"~class="folder-topnews fl"~class="other-folder fl"~<a class="link-othernews"~<a class="link-title"~ ~class="content"~ ~style="margin-top:5px;margin-bottom:5px;"~ ~class=Title~ ~~ ~ormal align=right~ Mỗi một dòng được bắt đầu và kết thúc bởi dấu “~”, đồng thời dấu “~” cũng được sử dụng để làm phân cách cho các mẫu trên cùng một dòng. Đường đi của mô hình hệ thống 27 Trước hết, “module sinh file huấn luyện” được chạy để sinh ra file huấn luyện, cũng là dữ liệu vào, thành phần chính của “module phân lớp”. Tiếp theo, chương trình đọc file cấu hình xnews.conf để thu được các URLs hạt giống và các mẫu đi cùng với nó như được trình bày ở trên. Tạo một yêu cầu (request) HTTP để lấy về mã HTML của trang tin Home tương ứng với URL hạt giống. Đọc và trích xuất ra các siêu liên kết có trong mã HTML này dựa vào mẫu “Dấu hiệu nhận biết link con cần lấy” để thu được danh sách URLs. Truy vấn đến CSDL để kiểm tra các URLs thuộc danh sách này xem đã được thăm chưa, từ đó đưa ra được danh sách các URLs chưa thăm. Ở đây, khóa luận sử dụng lưu trữ trong CSDL bảng băm MD5 của URL thay cho việc lưu trữ trực tiếp URL, đồng thời sử dụng mã MD5 làm khóa chính của bảng tương ứng trong CSDL (sẽ được trình bày chi tiết hơn trong chương 4). Đối với mỗi URL trong danh sách URLs chưa thăm, lặp lại việc gửi yêu cầu HTTP để thu được mã HTML tương ứng. Sử dụng công cụ UnicodeConverter để chuẩn hóa Unicode mã HTML lấy về, và sau đó tiến hành trích xuất thông tin nhờ vào tập mẫu của file cấu hình xnews.conf. Thông tin trích xuất được, được đưa vào dữ liệu “các thông tin đầy đủ về bài báo” bao gồm bảng băm MD5 của URL, URL, tiêu đề bài báo, phần tóm tắt nội dung, link ảnh minh họa, và phần nội dung bài báo, đồng thời cung cấp “toàn bộ nội dung bài báo” (từ phần bắt đầu đến kết thúc của bài báo đó trong mã HTML) cho “module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình”. Qua bước này, chương trình thu được xâu đã được chuẩn hóa, làm dữ liệu vào cho “module phân lớp”, qua module thu được nhãn tương ứng của bài báo. Cung cấp nhãn này cho “các thông tin đầy đủ về bài báo” và cuối cùng là tiến hành ghi các thông tin này vào CSDL. Xử lý các văn bản không thuộc các lớp quan tâm Trên thực tế, xảy ra trường hợp tập các lớp mà bài toán phân lớp của chương trình quan tâm tới không bao quát hết các trường hợp văn bản, tin tức của hệ thống trang tin điện tử. Một phương pháp giải quyết với vấn đề này, là xây dựng thêm một phân lớp, là phân lớp “khác”. Tất cả các văn bản không thuộc các phân lớp văn bản thông thường sẽ được xếp vào phân lớp “khác”. Để giải quyết vấn đề theo cách đơn giản hơn, khóa luận đã áp dụng một số phương pháp để loại bỏ các trường hợp này từ danh sách URLs dựa vào đặc điểm URL và một số yếu tố khác. Làm như vậy cũng đồng thời tiết kiệm được công sức phải xử lý (từ lấy mã HTML, chuẩn hóa, phân lớp,…) một lượng các văn bản không thuộc lớp nào góp phần tăng tốc độ chung cho toàn hệ thống. 28 Ví dụ 1: Trên trang báo điện tử vnexpress.net có phân lớp “Tâm sự” là phân lớp không thuộc nhóm được quan tâm của nội dung khóa luận. Một số URL bài viết thuộc lớp này: - - Dễ dàng nhận thấy đặc điểm chung URL của các bài viết thuộc lớp này. Như vậy với báo điện tử vnexpress.net để loại các bài viết thuộc lớp “Tâm sự” đơn giản chỉ cần loại các URL có chứa xâu “vnexpress.net/GL/Ban-doc-viet/Tam-su/”. Ví dụ 2: Trong trường hợp của báo phapluattp.vn. Xuất hiện các bài báo thuộc lớp “Đô thị” là phân lớp chưa được khóa luận quan tâm tới. Dựa vào đặc điểm này, các bài báo thuộc lớp “Đô thị” cũng sẽ dễ dàng bị loại trước khi chương trình thực hiện trích xuất các nội dung thông tin cần thiết. Hình 9. Đặc điểm giúp loại tin thuộc lớp chưa quan tâm 29 Kiểm soát các trang trùng nhau Một vấn đề không kém phần quan trọng trong nội dung tổng hợp tin tức là kiểm soát các bài báo có cùng nội dung. Đối với hệ thống trang tin điện tử của Việt Nam, nhiều trang báo thực hiện việc tổng hợp từ các báo khác bằng phương pháp thủ công, và đi kèm với đó có một số vấn đề cần được xử lý như sau: - Tiêu đề của tin tức có thể được thay đổi. - Phần tóm tắt có thể được thêm bớt. - Ảnh minh họa có thể bị thay đổi. - Nội dung có thể được thêm bớt ít nhiều. Để xử lý trường hợp này phương pháp thường được sử dụng là Jaccard Index (chỉ số Jaccard) – còn được gọi là hệ số tương tự Jaccard, là một số thống kê được sử dụng để so sánh sự giống nhau và đa dạng của các bộ mẫu. Nhưng do có nhiều hạn chế về mặt thời gian, nên vấn đề này sẽ là định hướng phát triển trong tương lai. 3.2.2. Module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình Hình 10. Module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình 30 Mô tả bài toán Đầu vào: Xâu dữ liệu nội dung bài báo và file danh sách từ dừng1 Đầu ra: Xâu dữ liệu đã được gán nhãn “Xâu dữ liệu nội dung bài báo” là phần nội dung từ bắt đầu đến kết thúc bài báo dưới mã HTML đã được chuẩn hóa Unicode (là phần dữ liệu được trích xuất từ mã HTML của bài báo tương ứng). Đường đi của mô hình hệ thống Từ xâu dữ liệu vào, xóa bỏ các thẻ HTML để thu được tài liệu dạng văn bản phi cấu trúc thông thường. Sử dụng công cụ vnTokenizer phân tích dữ liệu thu được ra dạng từ đơn, từ ghép. Xóa bỏ các ký tự đặc biệt như dấu chấm, dấu phẩy, chấm phẩy, hai chấm, ba chấm,… thu được xâu dữ liệu chỉ bao gồm các từ đơn từ ghép ngoài ra không còn ký hiệu đặc biệt hay nào khác. Loại bỏ từ dừng ở xâu thu được bằng phương pháp khớp biểu thức chính quy. Từ file danh sách từ dừng sinh ra một mẫu biểu thức chính quy, cho phép khớp tất cả các từ dừng có trong danh sách. Sau khi loại bỏ từ dừng, chuẩn hóa xâu thu được, xóa bỏ các dấu trống đầu và cuối, thay tất cả các ký tự trống (ký tự tab, cuối dòng) bằng dấu khoảng cách, giữa hai từ bất kỳ chỉ giữ một dấu khoảng cách duy nhất. Thu được xâu đã được chuẩn hóa, thực hiện gán nhãn và trả ra xâu đã được gán nhãn. Ở đây, đối với mô hình huấn luyện, nhãn của dữ liệu đã được biết trước, thực hiện gán nhãn trên xâu đã được chuẩn hóa. Còn với mô hình kiểm tra, nhãn ở đây được gán theo dạng câu hỏi (dấu chấm hỏi “?”). 3.2.3. Module phân lớp Mô tả bài toán Đầu vào: File huấn luyện và xâu cần phân lớp đã được chuẩn hóa Đầu ra: Xâu được phân lớp và gán nhãn File huấn luyện được tạo bởi “module sinh file huấn luyện” và xâu cần được phân lớp được sinh bởi “module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình”. Đường đi của mô hình hệ thống 1 31 Từ file huấn luyện, sử dụng công cụ maxent cho việc học mô hình. Sau quá trình học, mô hình thu được được sử dụng để kiểm tra mô hình trên “xâu vào đã được chuẩn hóa” (sử dụng công cụ maxent) thu được xâu được gán nhãn. 3.2.4. Module sinh file huấn luyện Mô tả bài toán Đầu vào: Tập dữ liệu huấn luyện Đầu ra: File huấn luyện Tập dữ liệu huấn luyện được lấy từ báo vnexpress.net riêng biệt theo 10 phân lớp bao gồm: - XAHOI - THEGIOI - KINHDOANH Hình 11. Module phân lớp 32 - VANHOA - THETHAO - PHAPLUAT - ĐOISONG - KHOAHOC - VITINH - XE Mỗi phân lớp sử dụng 1.000 bài báo cho việc học mô hình. Như vậy file huấn luyện sẽ bao gồm nội dung được lấy từ 10.000 bài báo đã biết trước nhãn. Đường đi của module Đọc tập dữ liệu huấn luyện để thu được xâu, làm dữ liệu đầu vào cho “module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình” thu được xâu đã được gán nhãn ghi lại thành file huấn luyện. 3.3. Khả năng mở rộng của hệ thống Theo mô hình hệ thống của chương trình thể hiện tính module hóa cao. Các module làm việc ăn khớp với nhau, mỗi module đều có một chức năng rõ ràng và tương đối độc Hình 12. Module sinh file huấn luyện 33 lập với các module còn lại, các module chỉ tương tác với nhau theo dạng đầu vào của module này là đầu ra của module khác làm cho chương trình dễ dàng kiểm soát được lỗi phát sinh nếu có. Đồng thời việc nâng cấp toàn bộ hệ thống lấy tin cũng chỉ ảnh hưởng đến từng module riêng biệt chứ không tác động tới tất cả các module trong hệ thống. Ví dụ hệ thống cần được nâng cấp về số phân lớp, để mở rộng quy mô ra những lĩnh vực chưa được quan tâm trước đó, hệ thống chỉ cần nâng cấp làm việc với “module sinh file huấn luyện” để có thể phân lớp các văn bản thuộc các lớp mới đó. 34 Chương 4. Thực nghiệm và đánh giá kết quả Ở chương này, khóa luận sẽ trình bày thực nghiệm và kết quả để đánh giá chất lượng của hệ thống tổng hợp và phân loại tin tự động, khóa luận sẽ đưa ra hai nội dung đánh giá là chất lượng tổng hợp tin và hiệu suất của việc phân loại tin tự động. 4.1. Môi trường phần cứng và phần mềm 4.1.1. Môi trường phần cứng Thành phần Thông số CPU Intel Core 2 Duo T7600 2.0GHz RAM 3GB OS Ubuntu 9.04 Bộ nhớ ngoài 120GB 4.1.2. Công cụ phần mềm STT Tên phần mềm Giấy phép Nguồn 1 Netbean 6.5 GPL Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm Bảng 3. Các công cụ phần mềm sử dụng trong thực nghiệm 35 2 mysql 5.0.75- 0ubuntu10.3 GPL 3 OpenJDK 1.6.0_0 GPL 4 mysql-connector- java-5.1.12-bin.jar GPL 5 maxent-2.5.2.jar GPL 6 vn.hus.nlp.tokenizer- 4.1.1.jar GPL php 7 UnicodeConverter.jar v2.0 GPL Sử dụng các công cụ phần mềm trên khóa luận đã xây dựng chương trình tự động tổng hợp và phân loại tin trong hệ thống trang tin điện tử. Cấu trúc của chương trình gồm có 3 gói (packages) chính như sau:
J_Lib: Cung cấp các chức năng cần thiết ở mức thư viện cung cấp các chức năng tiện dụng nhất và có mức độ độc lập tương đối với các packages khác.
J_NLP: Cung cấp các chức năng tách từ tiếng Việt (sử dụng vnTokenizer) và học cũng như kiểm tra mô hình với phân lớp văn bản entropy cực đại (sử dụng maxent)
xnews: Sử dụng J_Lib và J_NLP để lấy tin, xử lý trích xuất, chuẩn hóa, phân lớp, ghi nội dung tin tức vào CSDL, làm và đánh giá các thực nghiệm... Chi tiết các lớp của 3 gói này được trình bày như bảng bên dưới: 36 Packages Classes Chức năng J_GET Tạo yêu cầu (request) GET để lấy về mã HTML của một URL J_Img Tải ảnh, phân loại và nén ảnh J_RmTag Xóa các thẻ HTML để thu được bài báo ở dạng văn bản thông thường J_SQL Kết nối với CSDL (sử dụng mysql- connector-java-5.1.12-bin.jar) J_Lib J_Utilities Sinh mã md5 của một xâu và các tiện tích trên file CreateModel Sinh mô hình từ tập dữ liệu huấn luyện (sử dụng maxent) Predict Kiểm tra mô hình, gán nhãn cho dữ liệu kiểm tra (sử dụng maxent) J_NLP J_Tokenizer Sử dụng biểu thức chính quy để chuẩn hóa xấu, loại ký tự đặc biệt, loại bỏ từ dừng, tách từ đơn, từ ghép (sử dụng vnTokenizer) Crawler Điều khiển lấy tin, trích xuất nội dung, chuẩn hóa, phân lớp, vào ra trên CSDL,... (sử dụng UnicodeConverter.jar) xnews Lab Tạo dữ liệu học, kiểm tra mô hình từ tập dữ liệu thô Bảng 4. Mô tả chức năng các lớp trong các gói 37 4.2. Cấu trúc Cơ sở dữ liệu Cơ sở dữ liệu của chương trình được thiết kế cho việc tối ưu hóa tốc độ truy vấn, khi số lượng tin tức được lưu là rất lớn. CSDL của chương trình được thiết kế gồm 3 bảng t_store01, t_store02 và t_store03 cụ thể như sau:
Bảng t_store01: Cho biết các tin theo ngày và theo thể loại được phép hiển thị. Ứng với mỗi một ngày, bảng t_store01 sinh ra thêm 10 hàng tương ứng với 10 phân lớp của tin tức, lưu trữ thông tin về các bài báo trong ngày theo 10 phân lớp tương ứng.
Bảng t_store02: Lưu trữ tất cả các thông tin chi tiết của một bài báo cụ thể.
Bảng t_store03: Được thiết kế các trường, các chức năng giống với t_store01, chỉ có một điểm khác duy nhất, ngược lại với t_store01 cho biết các tin được phép hiển thị, thì t_store03 lại cho biết các tin không được phép hiển thị. Bảng t_store03 nhằm phục vụ cho việc lưu trữ các bài báo được xóa bằng tay trong trường hợp tin bài không phù hợp. Tất cả các tin khi được lấy về, sẽ được mặc định ghi vào bảng t_store01 và bảng t_store02. Bảng t_store03 sẽ được sử dụng đến bởi chức năng của người biên tập báo. Dù là một hệ thống lấy tin tức tự động, nhưng việc hệ thống cần có một người biên tập báo là điều hoàn toàn hợp lý. Người biên tập sẽ có nhiệm vụ theo dõi và chuẩn xác lại các thông tin, ví dụ khi hệ thống được mở rộng nguồn cập nhật tin, hệ thống tự động lấy về một số bài báo có nội dung liên quan đến các vấn đề “nhạy cảm” về chính trị, người biên tập có nhiệm vụ đánh giá mức độ “nhạy cảm” của vấn đề và đưa ra quyết định có giữ bài báo hay không. Nếu bài báo cần được xóa, nó sẽ được chuyển từ bảng t_store01 sang t_store03 - nơi chỉ chứa các tin đã bị xóa (trên thực tế là bị ẩn) và trường vis của bảng t_store02 cũng thay đổi tương ứng. Ngoài ra t_store03 được tạo ra còn nhằm để cho phép khôi phục lại tin đã xóa nếu thấy cần thiết. Để phục vụ việc tối ưu hóa truy vấn, khóa luận thực hiện đánh chỉ mục (index) trên các bảng của CSDL tương ứng với các khóa chính của bảng đó: - data_type trên t_store01 và t_store03. - u5 trên t_store02. 38 Bảng Trường/ Khóa Kiểu dữ liệu Mô tả date_type (p) int Date là ngày theo kiểu int được viết dưới định dạng YYYYMMDD viết liền type, để chia ra tin tức theo 10 phân lớp trong ngày. nums int Số bài đến thời điểm hiện tại trong ngày ứng với mỗi một mục tin date_type. t_store01 lu5 text Danh sách bảng băm MD5 của nums tin tương ứng của mỗi mục tin trong ngày. Hai mã MD5 liên tiếp phân cách nhau bởi xâu “t_#”. Mỗi mã MD5 cho phép truy vấn tin theo u5 của t_store02. u5 (p) char(32) u5 gồm 32 ký tự là bảng băm MD5 của URL bài báo gốc. u5 được sử dụng làm khóa chính của bảng, đồng thời được đánh chỉ mục (index) cho phép tối ưu hóa truy vấn. Ngoài tập tất cả các u5 trong t_store02 cũng đại diện cho tất cả các URL đã thăm, như vậy nó cho phép kiểm tra URL chưa thăm. vis char(1) vis được ấn định 1 trong 2 trạng thái 0 hoặc 1. Mặc định vis bằng 1 có nghĩa là bài báo đó được phép hiển thị. Ngược lại khi vis bằng 0 thì bài báo đó không được phép hiển thị. t_store02 type int type là số có 2 chữ số 00, 01, …, 09 tương ứng với 10 phân lớp tin tức của hệ thống. Bảng 5. Chi tiết CSDL 39 infors text Thông tin tổng hợp về một bài báo bao gồm các nội dung thông tin: ngày tháng định dạng YYYYMMDDHHmm bài báo được lấy về, URL bài báo gốc, tiêu đề bài báo, tóm tắt, link ảnh minh họa. Các thông tin được ngăn cách nhau bởi ký hiệu “t_#”. view mediumtext Chứa toàn bộ phần nội dung thông tin bài báo, từ sau phần tóm tắt đến kết thúc. t_store03 Hoàn toàn tương tự với t_store01 về thành phần. 4.3. Đánh giá chất lượng tổng hợp tin Sau một thời gian thử nghiệm, quan sát và đánh giá, khóa luận đi tới một số kết luận về chất lượng tổng hợp tin của hệ thống:
Tốc độ lấy tin mới nhanh và ổn định. Chương trình đặt một độ trễ (delay) là 2 phút cho hai lần (lặp) lấy tin liên tiếp. Kết quả quan sát cho thấy, khi tin mới xuất hiện trên hệ thống nguồn, thì sau đó 1 đến 2 phút, tin tức sẽ được tự động cập nhật vào hệ thống.
Chất lượng tin lấy về với độ chính xác cao, hiện khóa luận chưa phát hiện việc trích rút sai nội dung tin tức như tiêu đều, tóm tắt, ảnh, nội dung… Khóa luận sẽ tiếp tục theo dõi và đánh giá trong thời gian tới. 4.4. Thực nghiệm và đánh giá hiệu suất phân loại tin tự động 4.4.1. Xây dựng tập dữ liệu huấn luyện và kiểm tra mô hình Để chuẩn bị dữ liệu huấn luyện và kiểm tra mô hình khóa luận thực hiện phân lớp bằng tay dựa vào các mục tin (category) của Website báo điện tử nguồn. Đối với mỗi một phân lớp, sau khi được phân bằng tay, khóa luận tạo một số đoạn mã chương trình bằng Java thực hiện việc lấy các tin tức cũ hơn của mục tin (phân lớp) đó theo ngày tháng. 40 STT Tên phân lớp VnExpress Mô tả 1 XAHOI Xã hội Giáo dục, lối sống, du lịch,… 2 THEGIOI Thế giới Tình hình thế giới, chủ yếu là tình hình chính trị. 3 KINHDOANH Kinh doanh Kinh doanh, tình hình kinh tế, thị trường chứng khoán,… 4 VANHOA Văn hoá Âm nhạc, thời trang, điện ảnh, nghệ sĩ, mỹ thuật,… 5 THETHAO Thế giới Tình hình thế giới, chủ yếu là tình hình chính trị. 6 PHAPLUAT Pháp luật Vụ án, vụ việc, các văn bản luật mới. 7 DOISONG Đời sống Tâm sự, gia đình, tình cảm, nội trợ, nhà ở, ẩm thực,… 8 KHOAHOC Khoa học Khoa học nói chung, không liên quan đến lớp Công nghệ. 9 VITINH Vi tính Công nghệ thông tin và truyền thông. 10 XE Ôtô-Xe máy Phương tiện đi lại. Dữ liệu dùng cho việc huấn luyện mô hình là các bài báo được lấy từ trang báo điện tử vnexpress.net, với số lượng các phân lớp như sau: Bảng 6. Các lớp tài liệu sử dụng trong thực nghiệm 41 STT Phân lớp Số lượng văn bản 1 XAHOI 1000 2 THEGIOI 1000 3 KINHDOANH 1000 4 VANHOA 1000 5 THETHAO 1000 6 PHAPLUAT 1000 7 DOISONG 1000 8 KHOAHOC 1000 9 VITINH 1000 10 XE 1000 Tổng số 10000 Ở đây, khóa luận xin đưa ra 2 thực nghiệm kiểm tra chất lượng phân loại tin tự động. 4.4.2. Thực nghiệm thứ nhất Mô tả thực nghiệm Thực nghiệm nhằm đánh giá chất lượng phân loại tin tự động đối với dữ liệu test cũng được lấy từ báo điện tử vnexpress.net. Bảng 7. Thống kê số lượng tài liệu dùng cho việc học mô hình 42 Đầu vào: Mô hình đã qua huấn luyện của hệ thống, và các dữ liệu lấy từ vnexpress.net ở dạng thô. Đầu ra: Bảng đánh giá kết quả độ chính xác theo các chỉ số bao gồm: độ hồi tưởng (R), độ chính xác (P) và độ đo F1. Tập dữ liệu được dùng cho việc kiểm tra mô hình được mô tả trong bảng STT Phân lớp Số lượng văn bản 1 XAHOI 100 2 THEGIOI 100 3 KINHDOANH 100 4 VANHOA 100 5 THETHAO 100 6 PHAPLUAT 100 7 DOISONG 100 8 KHOAHOC 100 9 VITINH 100 10 XE 100 Tổng số 1000 Kết quả thực nghiệm Bảng 8. Thống kê số lượng tài liệu thực nghiệm 1 dùng kiểm tra mô hình 43 Nhãn Độ chính xác (%) Độ hồi tưởng (%) F1 (%) XAHOI 92.93 92.00 92.46 THEGIOI 98.96 95.00 96.94 KINHDOANH 90.74 98.00 94.23 VANHOA 95.24 100.00 97.55 THETHAO 98.99 98.00 98.49 PHAPLUAT 94.23 98.00 96.08 DOISONG 93.20 96.00 94.58 KHOAHOC 97.92 94.00 95.92 VITINH 100.00 93.00 96.37 XE 98.97 96.00 97.46 Trung bình thô 96.11 96.00 96.01 Trung bình mịn 96.00 96.00 96.00 Nhận xét: - Kết quả thực nghiệm cho thấy kết quả phân lớp tự động được thực hiện với dữ liệu test mô hình của báo điện tử vnexpress.net là rất tốt. Tất cả các trường hợp độ đo F1 đều chính xác hơn 92%. Trung bình mịn của độ chính xác và độ hồi tưởng đều đạt 96%. - Đối với đặc trưng của tin tức. Một bài báo có thể thuộc cùng lúc nhiều phân lớp. Ví dụ, một bài báo với nội dung nói về “tình trạng móc túi diễn ra tại các bến xe bus ở Hà Nội” tin tức này hoàn toàn có thể xếp vào phân lớp PHAPLUAT Bảng 9. Kết quả thực nghiệm 1 44 xong cũng đồng thời có thể xếp vào phân lớp XAHOI. Chính bản chất đa lớp có thể có của một tin tức cụ thể có thể dẫn đến kết quả phân lớp bị sai. 4.4.3. Thực nghiệm thứ hai Mô tả thực nghiệm Thực nghiệm nhằm đánh giá chất lượng phân loại tin tự động đối với dữ liệu test lấy từ các báo khác bao gồm: dantri.com.vn, baodatviet.vn và tuoitre.vn. STT Phân lớp Số lượng văn bản 1 XAHOI 50 2 THEGIOI 50 3 KINHDOANH 50 4 VANHOA 50 5 THETHAO 50 6 PHAPLUAT 50 7 DOISONG 50 8 KHOAHOC 50 9 VITINH 50 10 XE 50 Tổng số 500 Bảng 10. Thống kê số lượng tài liệu thực nghiệm 2 dùng kiểm tra mô hình 45 Đầu vào: Mô hình đã qua huấn luyện của hệ thống, và các dữ liệu lấy từ 3 nguồn tin dantri.com.vn, baodatviet.vn và tuoitre.vn ở dạng thô. Đầu ra: Bảng đánh giá kết quả độ chính xác theo các chỉ số bao gồm: độ hồi tưởng (R), độ chính xác (P) và độ đo F1. Tập dữ liệu được dùng cho việc kiểm tra mô hình được mô tả trong bảng 10. Kết quả thực nghiệm Nhãn Độ chính xác (%) Độ hồi tưởng (%) F1 (%) XAHOI 34.85 46.00 39.66 THEGIOI 83.02 88.00 85.44 KINHDOANH 79.63 86.00 82.69 VANHOA 66.67 80.00 72.73 THETHAO 94.23 98.00 96.08 PHAPLUAT 89.58 86.00 87.75 DOISONG 69.23 54.00 60.67 KHOAHOC 76.67 46.00 57.50 VITINH 83.93 94.00 88.86 XE 100 84.00 91.30 Trung bình thô 77.78 76.20 76.25 Trung bình mịn 76.20 76.20 76.20 Bảng 11. Kết quả thực nghiệm 2 46 Nhận xét: - Kết quả thực nghiệm 2 trong bảng 11 cho biết trong tổng số lượng văn bản được phân lớp, thì có khoảng 76% văn bản được phân lớp đúng theo cách phân lớp của báo dùng để test. - Bảng 9 và bảng 11 cho thấy có sự khác biệt lớn về độ chính xác của thực nghiệm 2 so với thực nghiệm 1. Sở dĩ có sự khác nhau như vậy, là do trong thực nghiệm 2, khóa luận tiến hành kiểm tra với các báo điện tử khác với báo được sử dụng để học mô hình, các báo khác nhau này có cây phân lớp không tương đồng nhau, do đó dẫn đến việc phân lớp đúng theo báo học mô hình là vnexpress.net thì có thể không đúng với báo kiểm tra tuoitre.vn. Ví dụ: tin “Phá án buôn ma túy biên giới, 3 công an bị thương”1 theo cây phân lớp của tuoitre.vn được xếp vào lớp XAHOI, nhưng với một tin có nội dung hoàn toàn tương tự “3 cảnh sát bị thương khi truy bắt nhóm buôn ma túy”2 thì vnexpress.net lại xếp tin này vào phân lớp PHAPLUAT. 1 an buon-ma-tuy-bien-gioi-3-cong-an-bi-thuong.html 2 47 Kết luận Kết quả đạt được của khóa luận Từ việc nghiên cứu về các bài toán của hệ thống tổng hợp và phân loại tin tự động, khóa luận đã trình bày phương pháp tổng hợp và phân loại tin tức từ các trang báo điện tử khác nhau. Qua những kết quả thực nghiệm cho thấy tính hiệu quả của phương pháp này. Về mặt nội dung, khóa luận đã đạt được những kết quả như sau: - Giới thiệu các hệ thống tổng hợp tin hiện có của Việt Nam, ưu và nhược điểm. - Nghiên cứu cơ sở lý thuyết về trích chọn thông tin tài liệu Web, giới hiệu mô hình phân lớp văn bản entropy cực đại. Chỉ ra thế mạnh của phương pháp này trong phân lớp văn bản phù hợp với nội dung phân lớp tin tức. Giới thiệu các đại lượng sử dụng cho việc đánh giá kết quả phân lớp. - Thông qua mô hình lý thuyết nghiên cứu được về trích chọn tài liệu Web và phân lớp văn bản, khóa luận đã tiến hành xây dựng mô hình hệ thống tổng hợp và phân loại tin tự động. - Trên cơ sở mô hình có được, khóa luận đã cài đặt được chương trình chính là hệ thống tổng hợp và phân loại tin tự động bằng ngôn ngữ Java sử dụng môi trường Netbean. - Đánh giá chất lượng tổng hợp và hiệu suất phân loại tin của hệ thống, từ đó cho thấy chất lượng tổng hợp và hiệu suất phân loại đều rất tốt. Mặc dù vậy, do hạn chế về thời gian và kiến thức khóa luận vẫn còn hạn chế sau: - Khóa luận chưa xây dựng được giao diện người dùng cho hệ thống. - Chưa đưa ra được phương pháp xử lý thỏa đáng đối với trường hợp một bài báo thuộc nhiều hơn một phân lớp. - Chưa kiểm soát một cách toàn diện đối với trường hợp các bài báo có nội dung trùng nhau. Định hướng tương lai Trong tương lai, khóa luận sẽ tiếp tục nghiên cứu về các vấn đề sau: 48 - Phân lớp một bài báo có thể thuộc vào nhiều lớp sử dụng phân lớp mờ Fuzzy. - Kiểm soát trường hợp các bài báo có nội dung trùng nhau sử dụng chỉ số Jaccard. - Đồng thời khóa luận cũng cố gắng để sớm công bố hệ thống để phục vụ người sử dụng. 49 Tài liệu tham khảo [1]. Nguyen Viet Cuong, Nguyen Thi Thuy Linh, Phan Xuan Hieu and Ha Quang Thuy (2005). “A Maximum Entropy Model for Vietnamese Web Content Classification”. Proceedings of the 8th National Conference on Information Technology of Vietnam: pages 174-189, Vietnam. (in Vietnamese). [2]. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú. Giáo trình khai phá dữ liệu Web. Nxb GDVN, 2009, tr. 153-166, tr. 220-233. [3]. Berger, A., Della Pietra, S., and Della Pietra, V. A maximum entropy approach to natural language processing. Computational Linguistics, volume 22, number 1, 1996, pages 39-71. [4]. Bing Liu, Web Data Mining Exploring Hyperlinks, Contents, and Usage Data, ,December, 2006. [5]. Chieu, H. L. and Ng, H. T. A Maximum Entropy Approach to Information Extraction from Semi-Structured and Free Text. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), 2002, pages 786-791. [6]. Crescenzi V., Mecca G., and Merialdo P. Roadrunner: Towards Automatic Data Extraction from Large Web Sites.In Proc. of Very Large Data Bases (VLDB’01), pages 109–118, 2001. [7]. Cuong Nguyen Viet, Nguyen Thi Thuy Linh, Ha Quang Thuy and Phan Xuan Hieu (2006). “A Maximum Entropy Model for Text Classification”. Proceedings of International Conference on Internet Information Retrieval 2006 (IRC 2006), pages 143- 149, Korea. [8]. Darroch, J. and Ratcliff, D. Generalized iterative scaling for log-linear models. Annals Mathematical Statistics, volume 43, number 5, 1972, pages 1470–1480. [9]. Debnath S., Mitra P., and Giles C. L. Automatic extraction of informative blocks from webpages. In Proc. SAC, pages 1722-1726, 2005. [10]. Debnath S., Mitra P., Pal N., and Giles C. L. Automatic Identification of Informative , IEEE Trans. Knowl. Data Eng. 17 , 2005. 50 [11]. Della Pietra, S., Della Pietra, V. and Lafferty, J. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 19, number 4, 1997, pages 380–393. [12]. Gautam Pant, Parmini Srinivasan, and Filipo Menczer (2004). Crawling the Web. Web Dynamic 2004: pg. 153-178. [13]. Jaynes, E. R. (1957). Information Theory and Statistical Mechanics. Physic Review, volume 106, 1957, pages 620-630. [14]. Kushmerick WIEN N. Wrapper Induction for Information Extraction. Ph.D Thesis. Dept. of Computer Science, University of Washington, TR UW-CSE-11-04- 1997. [15]. NGAI Grace, WU Deka, CARPUAT Marine, WANG Chi-Shing, WANG Chi- Yung. Semantic Role Labeling with Boosting, SVMs, Maximum Entropy, SNOW, and Decision Lists. [16]. Nigam, K., Lafferty, J. and McCallum, A. Using maximum entropy for text classification. IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999, pages 61-67. [17]. Nigam K., McCallum, A., Thrun S. and Mitchell, T. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning, volume 39, number 2/3, 2000, pages 103-134. [18]. Ratnaparkhi, A. A simple introduction to maximum entropy models for natural language processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997.