Đề tài Bài toán phân lớp văn bản và áp dụng phân lớp dữ liệu tài chính ngân hàng

ĐH Cơng Nghệ - ĐH QGHN CNTT Khĩa luận tốt nghiệp Lê Thị Thùy Dương LỜI CẢM ƠN Trước tiên, em muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo, Phĩ Giáo sư Tiến sĩ Hà Quang Thụy, ThS. Đỗ Cẩm Vân và CN.Trần Mai Vũ, những người đã tận tình hướng dẫn em trong suốt quá trình thực hiện khĩa luận tốt nghiệp. Em xin bày tỏ lời cảm ơn sâu sắc đến những thầy cơ giáo đã giảng dạy em trong bốn năm qua, những kiến thức mà em nhận được trên giảng đường đại học sẽ là hành trang giúp em vững bước trong tương lai. Em cũng muốn gửi lời cảm ơn đến các anh chị và các bạn trong nhĩm seminar về “Khai phá dữ liệu” đã giúp đỡ và cho em những lời khuyên bổ ích về chuyên mơn trong quá trình nghiên cứu. Cuối cùng, em muốn gửi lời cảm ơn sâu sắc đến tất cả bạn bè, và đặc biệt là cha mẹ và anh trai, những người luơn kịp thời động viên và giúp đỡ em vượt qua những khĩ khăn trong cuộc sống. Sinh viên Lê Thị Thùy Dương ĐH Cơng Nghệ - ĐH QGHN CNTT Khĩa luận tốt nghiệp Lê Thị Thùy Dương 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. 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. Mặt khác, phân lớp văn bản là một trong những thành phần cơ bản nhưng quan trọng nhất trong kiến trúc tổng thể của hầu hết các máy tìm kiếm. Hiện nay, bài tố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. Khĩa luận tốt nghiệp với đề tài “Bài tốn phân lớp văn bản và áp dụng phân lớp dữ liệu tài chính ngân hàng” nghiên cứu nội dung, các thuộc tính, các thuật tốn giải quyết bài tốn phân lớp. Khĩa luận tập trung nghiên cứu phương pháp phân lớp văn bản trong lĩnh vực tài chính ngân hàng tiếng Việt dựa trên hướng tiếp cận Entropy cực đại (maxent). Dựa trên việc khảo sát các đặc trưng tiếng Việt, sử dụng mơ hình Entropy cực đại, khĩa luận đã tiến hành thực nghiệm trên 5 lớp dữ liệu về lĩnh vực tài chính ngân hàng tự đề xuất (Huy động vốn, Tín dụng, Dịch vụ thanh tốn, Ngoại tệ, Chứng khốn), kết quả thu được rất tốt với độ đo F1 trung bình là 90.22% và thời gian huấn luyện 0.4594 giây/lần với 10 bước lặp. ĐH Cơng Nghệ - ĐH QGHN CNTT Khĩa luận tốt nghiệp Lê Thị Thùy Dương MỤC LỤC LỜI MỞ ĐẦU ................................................................................................................1 Chương 1. BÀI TỐN PHÂN LỚP VĂN BẢN..........................................................3 1.1. Khái niệm .................................................................................................3 1.2. Phân loại bài tốn phân lớp văn bản.....................................................5 1.3. Mơ hình phân lớp văn bản .....................................................................5 1.3.1. Mơ hình phân lớp văn bản...............................................................5 1.3.2. Quá trình xây dựng bộ phân lớp văn bản ........................................6 1.3.3. Quá trình tiền xử lý dữ liệu .............................................................7 1.3.3.1. Phương pháp biểu diễn tài liệu.....................................................8 1.3.3.2. Phương pháp lựa chọn thuộc tính...............................................10 1.3.4. Đánh giá ........................................................................................12 1.3.4.1. Đánh giá cho bài tốn phân lớp..................................................12 1.3.4.2. Đánh giá dựa vào độ tương tự ....................................................14 Chương 2. CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN....................................17 2.1. Thuật tốn K người láng giềng gần nhất ............................................17 2.2. Mơ hình cây quyết định (Decision Tree) .............................................18 2.3. Thuật tốn máy hỗ trợ vector (SVM – Suport Vector Machine) .....21 2.4. Mơ hình Entropy cực đại ......................................................................26 2.4.1. Định nghĩa nguyên lý entropy cực đại ..........................................26 2.4.2. Các ràng buộc và đặc trưng...........................................................27 2.4.3. Mơ hình Entropy cực đại...............................................................27 2.3.4. Entropy cực đại cho phân lớp văn bản ..........................................28 Chương 3. BÀI TỐN PHÂN LỚP VĂN BẢN TÀI CHÍNH NGÂN HÀNG TIẾNG VIỆT................................................................................................................30 3.1. Một số đặc trưng của dữ liệu tài chính ngân hàng trong tiếng Việt.30 3.2. Xây dựng một số lớp trong lĩnh vực tài chính ngân hàng .................31 3.3. Bài tốn phân lớp văn bản tài chính ngân hàng trong Tiếng Việt ...33 ĐH Cơng Nghệ - ĐH QGHN CNTT Khĩa luận tốt nghiệp Lê Thị Thùy Dương 3.3.1. Phát biểu bài tốn: .........................................................................33 3.3.2. Phương pháp phân lớp...................................................................34 3.3.3. Mơ hình của bài tốn phân lớp văn bản tài chính ngân hàng........34 Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ..........................................................38 4.1. Dữ liệu và chương trình........................................................................38 4.2. Mơi trường thực nghiệm.......................................................................39 4.3. Thiết kế và kết quả thực nghiệm..........................................................40 4.3.1. Thiết lập thơng số cho Entropy cực đại.........................................40 4.3.2. Kết quả thực nghiệm .....................................................................40 4.4. Đánh giá kết quả thực nghiệm .............................................................44 KẾT LUẬN ..................................................................................................................45 TÀI LIỆU THAM KHẢO...........................................................................................46 Tài liệu Tiếng Việt ............................................................................................46 Tài liệu Tiếng Anh............................................................................................46 DANH SÁCH CÁC TỪ DỪNG..................................................................................49 ĐH Cơng Nghệ - ĐH QGHN CNTT Khĩa luận tốt nghiệp Lê Thị Thùy Dương Danh sách hình vẽ và bảng biểu Hình 1. Bài tốn phân lớp văn bản ..................................................................................3 Hình 2. Sơ đồ khung một hệ thống phân lớp văn bản .....................................................6 Hình 3. Quá trình xây dựng mơ hình được chia thành hai bước .....................................8 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách ......................................................1 Hình 5. Siêu phẳng tối ưu và biên ...................................................................................1 Hình 6. Mơ hình bài tốn phân lớp dữ liệu tài chính ngân hàng...................................35 Hình 7. Đồ thị biểu diễn sự phụ thuộc của độ đo F1 vào số lần lặp..............................43 Hình 8. Tổng hợp độ đo qua 10 lần huấn luyện ............................................................43 Hình 9. Biểu đồ biểu diễn độ đo F1 của các lớp trong lần lặp thứ 6.............................44 Bảng 1. Phân bố dữ liệu học và kiểm tra.......................................................................38 Bảng 2. Tập dữ liệu huấn luyện.....................................................................................39 Bảng 3. Tập dữ liệu kiểm tra .........................................................................................39 Bảng 4. Tham số huấn luyện mơ hình Entropy cực đại ................................................40 Bảng 5. Kết quả 10 lần huấn luyện với Entropy cực đại...............................................41 Bảng 6. Kết quả của bước lặp thứ 6 ..............................................................................42 ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 1 -  LỜI MỞ ĐẦU Hiện nay, sự phát triển mạnh mẽ của Internet đã dẫn đến sự bùng nổ thơng tin về nhiều mặt kể cả nội dung lẫn số lượng. Chỉ bằng một thao tác tìm kiếm đơn giản, ta cĩ thể nhận về một khối lượng khổng lồ các trang web cĩ chứa thơng tin liên quan tới nội dung cần tìm kiếm. Tuy nhiên, chính sự dễ dàng này cũng mang đến cho con người rất nhiều khĩ khăn trong việc chiết lọc ra các thơng tin cĩ ích để thu được các tri thức mới. Phát hiện tri thức và khai phá dữ liệu là câu trả lời mới nhất cho vấn đề này nhằm phát hiện ra các tri thức mới từ khối dữ liệu khổng lồ mà con người cĩ được. Trong thời gian gần đây, cùng với sự phát triển của nền kinh tế đất nước là sự phát triển vượt bậc của nền cơng nghệ thơng tin. Tin học đã được áp dụng trong tất cả các lĩnh vực như kinh tế, thương mại, y tế, ngân hàng… Hầu hết các lĩnh vực này đề lưu trữ một cơ sở dữ liệu rất lớn. Các kỹ thuật thống kê truyền thống và các cơng cụ quản lý dữ liệu trước đây khơng đáp ứng được nhu cầu phân tích tập dữ liệu lớn này. Từ địi hỏi đĩ phải cĩ những phương pháp tiếp cận mới để khai phá tri thức trong các cơ sở dữ liệu. Trong các loại dữ liệu thì dữ liệu văn bản là phổ biến nhất. Khai phá dữ liệu văn bản là sự khảo sát và phân tích một tập lớn các văn bản khơng cĩ cấu trúc một cách tự động hoặc bán tự động để khám phá ra những tri thức mới. Với lượng thơng tin dạng văn bản đồ sộ của Internet, một yêu cầu lớn đặt ra là làm sao tổ chức và tìm kiếm thơng tin cĩ hiệu quả nhất. Phân lớp thơng tin là một trong những giải pháp hợp lý cho vấn đề nêu trên. Bài tốn phân lớp văn bản là một trong những bài tốn cơ bản của khai phá dữ liệu văn bản. Cho trước một tập dữ liệu văn bản, bài tốn thực hiện quá trình gán nhãn (phân lớp) cho từng tài liệu tương ứng với nội dung của nĩ thơng qua bộ phân lớp. Luận văn tập trung nghiên cứu về bài tốn phân lớp văn bản, cụ thể là những văn bản mang thơng tin về lĩnh vực ngân hàng, tài chính với mục đích phân lớp cho những tài liệu này theo những lớp ứng dụng cụ thể trong lĩnh vực ngân hàng, tài chính. Vấn đề phân lớp văn bản đã được đặt ra từ rất lâu và đến nay đã cĩ một số phương pháp hiệu quả thực hiện việc phân lớp văn bản… Tuy nhiên việc phân lớp cho dữ liệu tiếng việt về lĩnh vực ngân hàng, tài chính là một bài tốn mới và cho đến nay chưa cĩ một kết quả nào được cơng bố. Thơng qua việc tìm hiểu một số phương pháp tiếp cận bài tốn thường được sử dụng như phương pháp K-người láng giềng, Máy hỗ trợ vector (SVM – Suport Vector Machine), Phương pháp sử dụng mơ hình Entropy cực đại và ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 2 -  nghiên cứu ưu nhược điểm của từng phương pháp, luận văn hướng tới nghiên cứu áp dụng mơ hình Entropy cực đại cho bài tốn này. Luận văn bao gồm 4 chương cĩ nội dung khái quát như sau: Chương 1. Bài tốn phân lớp văn bản phát biểu và trình bày về các khái niệm và những nội dung cơ bản về bài tốn phân lớ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 tốn phân lớp và độ đo dựa vào khoảng cách và độ tương tự giữa các lớp. Chương 2. Các phương pháp giải quyết bài tốn phân lớp văn bản. Trình bày một số thuật tốn phân lớp văn bản điển hình, chỉ ra ưu nhược điểm của từng phương pháp. Qua đĩ lựa chọn phương pháp tốt nhất để thử nghiệm trong tiếng Việt. Chương 3. Bài tốn phân lớp văn bản tài chính ngân hàng. Trình bày các đặc điểm đặc trưng của dữ liệu tài chính ngân hàng, xây dựng tập nhãn (lớp) trong lĩnh vực này và mơ tả mơ hình phân lớp sử dụng phương pháp Entropy cực đại đối với tập văn bản đĩ. Chương 4. Thực nghiệm và đánh giá. Trong chương này trình bày các kết quả thực nghiệm thu được khi áp dụng mơ hình Entropy cực đại trên tập dữ liệu tài chính ngân hàng tiếng Việt. Đưa ra một số nhận xét, đánh giá kết luận. Trong phần kết luận, luận văn tĩm lại những cơng việc đã thực hiện trong thời gian qua và các kết quả đã đạt được, đồng thời cũng đề cập đến những điểm cịn hạn chế của luận văn và đề ra phương hướng nghiên cứu trong thời gian tới. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 3 -  Chương 1. BÀI TỐN PHÂN LỚP VĂN BẢN 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 tốn cơ bản và quan trọng trong trích chọn thơng tin trên Web là bài tốn phát hiện các quan hệ của các lớp đối tượng. Để thực hiện việc phát hiện mối quan hệ giữa các lớp đối tượng trên Web thì bài tốn đầu tiên cần giải quyết đĩ là bài tố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. Ngày nay, khi mà sự phát triển và ứng dụng của Internet cực kỳ phổ biến thì 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ữ. Sự phát triển vượt bậc của cơng nghệ khoa học kỹ thuật và sự mở rộng các dữ liệu khoa học về địa lý, địa chất, khí tượng thủy văn… cùng với việc tin học hĩa sâu rộng trong hầu hết các lĩnh vự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 biệt là 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.1. Khái niệm Phân lớp văn bản (Text classification) là quá trình gán nhãn (tên lớp / nhãn lớp) 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. Hình 1. Bài tốn phân lớp văn bản 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, như phân lớp theo độ ưu tiên, Dữ liệu vào Thuật tốn phân lớp hoạt động Lớp 1 Lớp 2 Lớp n ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 4 -  phân lớp theo chủ đề… Hầu hết các bài tốn này sẽ tốn rất nhiều 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 đĩ. Đặc biệt với số lượng tài liệu cần phân lớp cực kỳ lớn như hiện nay thì việc phân lớp thủ cơng là một điều khơng thể. 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, tài chính, ngân hàng... ) 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 loại 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, mạng nơron... được áp dụng để giải quyết bài tốn này. Chính vì những nhược điểm của phương pháp thủ cơng nên việc xây dựng một bộ phân lớp văn bản tự động là một điều rất quan trọng và cần thiết, đặc biệt là 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 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 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. 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 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. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 5 -  Định nghĩa phân lớp văn bản [1]: 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à { }ccccC ,..., 21= là tập các lớp cho trước. Giá trị T (true) được gán cho cặp (dj, ci) cĩ nghĩa là tài liệu dj thuộc lớp ci Giá trị F (false) tức là tài liệu dj khơng thuộc lớp ci Hay nĩi cách khác, phân lớp văn bản là bài tốn tìm một hàm { }FTCD ,: →×Φ trong đĩ D là tập các văn bản và { }ccccC ,..., 21= là tập các lớp cho trước, hàm { }FTCD ,: →×Φ được gọi là bộ phân lớp. 1.2. Phân loại bài tốn phân lớp văn bản Tùy vào những ràng buộc khác nhau để phân loại bài tốn phân lớp văn bản. Nhìn chung cĩ thể phân biệt bài tố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 tố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 tố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. Bài tố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. Trên thực tế, phân lớp hai lớp (phân lớp nhị phân) chỉ là một trường hợp đặc biệt của bài tốn phân lớp song do xuất xứ cho nên phân lớp nhị phân cĩ vị trí riêng cả về đặt bài tốn lẫn về các giải pháp 1.3. Mơ hình phân lớp văn bản 1.3.1. Mơ hình phân lớp văn bản Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán 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 Text 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. Để phân loại văn bản, người ta sử dụng phương pháp học máy cĩ giám sát. Tập dữ liệu được chia ra làm hai tập là tập huấn luyện và tập kiểm tra, trước hết phải ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 6 -  xây dựng mơ hình thơng qua các mẫu học bằng các tập huấn luyện, sau đĩ kiểm tra sự chính xác bằng tập dữ liệu kiểm tra. Hình 2. Sơ đồ khung một hệ thống phân lớp văn bản Hình trên biểu diễn một sơ đồ khung một hệ thống phân lớp văn bản, trong đĩ bao gồm ba thành phần chính: - Biểu diễn văn bản, tức là chuyển các dữ liệu văn bản thành một dạng cĩ cấu trúc nào đĩ, tập hợp các mẫu cho trước thành một tập huấn luyện. - Thực hiện việc sử dụng các kỹ thuật học máy để học trên các mẫu huấn luyện vừa biểu diễn. Như vậy việc biểu diễn ở giai đoạn thứ nhất sẽ là đầu vào cho giai đoạn thứ hai. - Thực hiện bổ sung các kiến thức thêm vào do người dùng cung cấp để làm tăng độ chính xác trong biểu diễn văn bản hay trong quá trình học máy. Trong 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 này. Như vậy thành phần thứ ba được coi là trung tâm của một hệ thống phân lớp văn bản. Trong phần này, cĩ nhiều phương pháp học máy được áp dụng như mơ hình mạng Bayes, cây quyết định, phương pháp K người láng giềng gần nhất, mạng Neuron, SVM, mơ hình Maximum Entropy. 1.3.2. Quá trình xây dựng bộ phân lớp văn bản Quá trình phân lớp dữ liệu thường gồm hai bước: xây dựng mơ hình (tạo bộ phân lớp) và sử dụng mơ hình đĩ để phân lớp dữ liệu. Các cơng cụ phân lớp được xây dựng dựa trên một thuật tốn phân lớp qua bước học quy nạp. Trong bước học, hệ ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 7 -  thống cĩ tập dữ liệu đầu vào Dt (tập ví dụ) mà thuộc tính lớp của mỗi tài liệu (ví dụ) trong tập đĩ đã biết. Tại bước học, tập dữ liệu ban đầu được chia thành hai tập dữ liệu rời nhau, một tập được gọi là tập dạy (training set) và một tập được gọi là tập kiểm tra (test set). Thơng thường tập training chiếm 2/3 các ví dụ trong Dt, cịn tập test chiếm 1/3 số lượng ví dụ cịn lại. Hệ thống dùng tập training để xây dựng mơ hình (xác định tham số) phân lớp và dùng tập dữ liệu test để đánh giá thuật tốn phân lớp vừa được thiết lập. Quá trình hai bước như sau: - Bước 1: Xây dựng mơ hình. Một mơ hình sẽ được xây dựng dựa trên phân tích các đối tượng dữ liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này cịn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định bởi con người trước khi xây dựng mơ hình, vì vậy phương pháp này cịn được gọi là học cĩ giám sát (supervised learning). Trong bước này, chúng ta cịn phải tính độ chính xác của mơ hình, mà cịn phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính xác là chấp nhận được, mơ hình sẽ được sử dụng để xác định nhãn lớp cho các dữ liệu khác mới trong tương lại. Trong việc test lại mơ hình, sử dụng các độ đo để đánh giá chất lượng của tập phân lớp, đĩ là độ hồi tưởng, độ chính xác, độ đo F1… Tồn tại nhiều phương pháp phân lớp dữ liệu để giải quyết bài tốn phân lớp tùy thuộc vào cách thức xây dựng mơ hình phân lớp như phương pháp Bayes, phương pháp cây quyết định, phương pháp k người láng giềng gần nhất, phương pháp SVM, phương pháp Maximum Entropy… Các phương pháp phân lớp khác nhau chủ yếu về mơ hình phân lớp. Mơ hình phân lớp cịn được gọi là thuật tốn phân lớp. - Bước 2: Sử dụng mơ hình. Sử dụng mơ hình được xây dựng ở bước 1 để phân lớp dữ liệu mới. Như vậy, thuật tốn phân lớp là một ánh xạ từ miền dữ liệu đã cĩ sang một miền giá trị cụ thể của thuộc tính phân lớp, dựa vào giá trị các thuộc tính của dữ liệu. 1.3.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 luyện thơng qua việc áp dụng các thuật tốn học. Tập dữ liệu huấn luyện là tập hợp các ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 8 -  trang văn bản trong cơ sở dữ liệu đã 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: 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 3. Quá trình xây dựng mơ hình được chia thành hai bước - 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 tố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 tốn phân lớp để xây dựng mơ hình từ dữ liệu đã qua tiền xử lý. 1.3.3.1. Phương pháp biểu diễn tài liệu Trong bài tố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 hoặc đặc trưng 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ễ nhận 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 tốn khĩ khăn hơn. Theo các nghiên cứu về 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 được lấy ra từ văn bản gốc. 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ừ khĩa) cho mỗi văn bản. Mỗi từ khĩa ti trong một tài liệu Dj được gán một trọng số wij và do đĩ, mỗi tài liệu được biểu diễn như một vector. Trọng số từ khĩa cĩ thể được tính tố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ừ khĩa cĩ mặt hay khơng cĩ mặt trong văn bản, tức là giá trị trọng số wij là 1 nếu từ khĩa ti xuất hiện ít nhất một lần trong tập tài liệu Dj và wij là 0 trong trường hợp ngược lại – Đây là mơ hình Boolean. Phương pháp khác là ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 9 -  tính số lần xuất hiện của từ khĩa trong một tài liệu gọi là tần suất từ khĩa. Tần suất từ khĩa được tính theo cơng thức: N Dtocc Dtfreq jkjk ),( ),( = Trong đĩ N là tổng số từ khĩa của tài liệu Dj và occ(tk,Dj) là số lần xuất hiện của từ tk trong văn bản Dj. Phương pháp này được gọi là phương pháp dựa trên tần số từ khĩa (TF – Term Frequency). 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. Ví dụ, khi văn bản xuất hiện nhiều từ khĩa “máy tính”, điều đĩ cĩ nghĩa là văn bản đang xét chủ yếu liên quan đến lĩnh vực “Tin học”. Nhưng suy luận trên khơng phải lúc nào cũng đúng. Một ví dụ điển hình là từ “chúng tơi” xuất hiện nhiều lần trong văn bản, nhưng trên thực tế từ này lại khơng mang nhiều ý nghĩa như tần suất xuất hiện của nĩ. Thơng thường tần suất của các từ khĩa trong văn bản khơng đồng đều nhau. Một số từ khĩa xuất hiện rất thường xuyên, trong khi đĩ, một nửa số từ khĩa xuất hiện chỉ một lần. Để giải quyết hạn chế này, Phương pháp dựa trên nghịch đảo tần số văn bản (IDF – Inverse Document Frequency) với tần suất logarit (tương tự với tần suất từ khĩa) được đề xuất và tính theo cơng thức: )),(1log(),( jkjk DtfreqDtfreq += Hay giá trị của từ khĩa ti được tính theo cơng thức: )log()log(log i i ij dfmdf mw −== Trong đĩ, m là số lượng văn bản và dfi là số lượng văn bản trong hệ thống cĩ chứa từ khĩa ti. Trọng số wij trong cơng thức này được tính dựa trên độ quan trọng của từ khĩa ti trong văn bản dj. Nếu ti xuất hiện trong càng ít văn bản, điều đĩ cĩ nghĩa khi nĩ xuất hiện trong văn bản dj thì trọng số của nĩ đối với văn bản dj càng lớn hay nĩ là điểm quan trọng để phân biệt văn bản dj với các văn bản khác và hàm lượng thơng tin trong nĩ càng lớn. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 10 -  Phương pháp dựa trên nghịch đảo tần số văn bản IDF được sử dụng phổ biến hơn phương pháp dựa trên tần số IF, 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 số từ khĩa. 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 số thấp. Phương pháp chuẩn thường được sử dụng là Term Frequency Inverse Document Frequency ( IFIDF), hàm tính trọng số từ khĩa được xác định bởi cơng thức: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= l dldl df mfreqTFIDF log*,, Trong đĩ, tần suất từ khĩa l trong tài liệu d : freql,d là số lần xuất hiện của từ khĩa l trong tài liệu d. Tần suất văn bản dfl là số văn bản trong tập tài liệu cĩ chứa từ khĩa l . m là tổng số tài liệu học. Trọng số TFIDF của một từ khĩa biểu diễn độ quan trọng của từ khĩa. TFIDF của một từ khĩa 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ừ khĩa trong tồn bộ tập tài liệu m được tính bởi cơng thức: ∑= dlTFIDFTFIDF , RTFIDFl ∈ 1.3.3.2. Phương pháp 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. Việc xử lý các vector thuộc tính địi hỏi các thuật tốn được tính tốn mở rộng và cĩ thể đơi khi khơng thể tính tốn được đối với một số thuật tố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). 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. Để 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ừ khĩa cĩ giá trị về thơng tin. Vì vậy, vấn đề phát hiện các từ khĩa khơng quan trọng phải được giải quyết để thu được khơng gian từ khĩa TT ⊂' với |T’| << |T|. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 11 -  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 [16]: 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 tốn thống kê được sử dụng để loại bỏ những từ khĩa khơng thích hợp. Sau đĩ, bộ phân lớp được huấn luyện trên khơng gian từ khĩa đã được rút gọn. Với chiến lược lựa chọn từ khĩa này, cĩ một vài phương pháp như: lựa chọn từ khĩa theo tần suất văn bản (Document Frequency), độ đo thơng tin qua lại (Mutual Information). - 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ừ khĩa xuất hiện. Để lựa chọn từ khĩa theo phương pháp tần suất văn bản thì cần phải tính tần suất văn bản với mỗi từ khĩa trong tập tài liệu học và sau đĩ loại bỏ những từ khĩa cĩ tần suất nhỏ hơn một ngưỡng nào đĩ để thu được khơng gian từ khĩa 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ừ khĩa t và lớp c, độ đo thơng tin qua lại được tính theo cơng thức sau: ( ) ( ) ( )ct ctctI PrPr )Pr(log, × ∧= Và được ước lượng: ( ) ( ) ( )BACA NActI +×+ ×≈ log, Trong đĩ: - A là số lần từ khĩa t và lớp c đồng thời xuất hiện. - B là số lần từ khĩa t xuất hiện mà khơng thuộc c. - C là số lần c xuất hiện mà 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ừ khĩa 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ừ khĩa phụ thuộc vào thuật tốn phân lớp. Bắt đầu từ khơng gian từ khĩa ban đầu, một khơng ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 12 -  gian từ khĩa mới được sinh ra bằng việc thêm hoặc bớt từ. Khi một tập hợp từ khĩa 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ừ khĩa tốt nhất được tạo ra cho thuật tốn phân lớp. Phương pháp này tạo thuận lợi cho thuật tố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 tốn. Ngồ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. 1.3.4. Đánh giá 1.3.4.1. Đánh giá cho bài tốn phân lớp Đánh giá kết quả phương pháp phân lớp văn bản cĩ thể được tính tốn theo nhiều cách khác nhau. Theo khảo sát của Sebastiani [3], độ đo phổ biến nhất được sử dụng để đánh giá phân lớp 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ự đốn Khơng thuộc lớp Ci FPi FNi Trong đĩ: - TPi (true positives): số lượng ví dụ dương được thuật tốn phân đúng vào lớp Ci. - TNi (true negatives): số lượng ví dụ âm được thuật tốn phân đúng vào lớp Ci. - FPi (false positives): số lượng ví dụ dương được thuật tốn phân sai vào Ci. - FNi (false negatives): số lượng ví dụ âm được thuật tốn phân sai vào Ci. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 13 -  Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật tốn phân lớp cho giá trị đúng trên tổng số ví dụ được thuật tốn phân lớp vào lớp iC : ii i i TNTP TP +=Pr Độ hồi tưởng iRe của lớp iC là tỷ lệ số ví dụ dương được thuật tố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 iC : 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 tồn bộ các lớp, tức là { }mCCC ,...,, 21 cĩ thể thu được bằng hai cách: cực tiểu trung bình (Micro-Average) và cực đại trung bình (Macro-Average). - Microaveraging: 1 1 ˆ ( ) m i i m i i i TP Pr TP TN µ = = = + ∑ ∑ 1 1 ˆ ( ) m i i m i i i TP Re TP FP µ = = = + ∑ ∑ - 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à: - Break-Even Point (BEP): BEP được đề xuất bởi Lewis [3], 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 sẽ cao hơn rất nhiều so với độ chính xác, khi đĩ khơng thể xác định được BEP. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 14 -  - Độ đo βF : độ đo βF được đề xuất bởi Rijbergen [3]. 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à: ( ) RePr. Re.Pr.1 2 2 + += β β βF 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à iEr của lớp iC : iii ii i FNFPTP FNTP Ac ++ += i iiii ii i AcFNFPTNTP TNFP Er −=+++ += 1 1.3.4.2. Đánh giá dựa vào độ tương tự Nếu phương pháp A và B đều khơng phân tài liệu vào đúng lớp iC của nĩ, nhưng phương pháp A phân vào lớp tương tự với lớp iC 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, Sun và Lim [3] đã 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. Độ tương tự giữa hai lớp iC và kC , kí hiệu là ( )ki CCCS , 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: { }NNi twtwtwC ,...,, 2211= { }NNk tvtvtvC ,...,, 2211= Độ 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: ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 15 -  ( ) ( ) ∑ ∑ ∑ = − = × × = N n N n nn N n nn ki vw vw CCCS 1 1 22 1, ( ) ( )1 ,2 1 1 −× × = ∑ ∑ = += mm CCCS ASC m i m ik ki Trong đĩ tn là chỉ số từ khĩa và wn và vn là trọng số từ khĩa. 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 Ci. Trường hợp đơn giản nhất là jd được gán vào đúng lớp Ci , tức là do jd iTP∈ , jd được tính là một trong cơng thức tính độ chính xác và độ hồi tưởng của lớp Ci. Tuy nhiên, nếu jd khơng được gán nhãn đúng (tức là ij FPd ∈ ) 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 Ci bằng cách tính phân phối của jd đối với lớp Ci , kí hiệu là ( )ij CdCon , theo cơng thức: ( ) ( )( ) ACS ACSCCCS CdCon agddC i ij j − −′ = ∑ ∈′ 1 , , . Trong đĩ, agdd j . là các lớp mà jd được gán vào. Tương tự, nếu jd là dữ liệu âm và thuật tốn phân đúng vào lớp Ci , tức là ij TNd ∈ , thì phân phối của jd với lớp Ci phụ thuộc vào độ tương tự giữa lớp Ci và các lớp mà jd thực sự thuộc (kí hiệu là lbdd j . ): ( ) ( )( ) ACS ACSCCCS CdCon lbddC i ij j − −′ = ∑ ∈′ 1 , , . 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 Ci đượ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 ( )ij CdRCon , được xác định: ( ) ( )( )( )ijij CdConCdRcon ,,1max,1min, −= ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 16 -  Với tất cả các tài liệu thuộc FPi , tổng phân phối FpConi sẽ là: ( )∑ ∈ = ij FPd iji CdRConFpCon , Tương tự, tổng phân phối TnConi là: ( )∑ ∈ = ij TNd iji CdRConTnCon , Độ chính xác và độ hồi tưởng mở rộng cho lớp Ci dựa vào độ tương tự được xác định như sau: Precision: ( ) iii iiiCS i FpConTNTP TnConFpConTP ++ ++= ,0maxPr Recall: ( ) iii iiiCS i TnConFPTP TnConFpConTP ++ ++= ,0maxRe Ngồ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 [3]. 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 Ci và Ck, kí hiệu là Dis(Ci, Ck) được định nghĩa là số đường liên kết giữa Ci và Ck. 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 và độ đo F dựa vào khoảng cách giữa các lớp. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 17 -  Chương 2. CÁC PHƯƠNG PHÁP 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 tốn phân lớp văn bản như: thuật tốn K người láng giềng gần nhất, thuật tốn học cây quyết định [4][5][7], thuật tốn Nạve Bayes, thuật tốn máy hỗ trợ vector [13][11][14][12][16], thuật tốn Boosting, Mơ hình Maximum Entropy[15][16][2]… Chương này sẽ giới thiệu một số thuật tốn điển hình, trong đĩ tập trung vào thuật tốn Maximum Entropy. 2.1. Thuật tốn K người láng giềng gần nhất Bộ phân lớp dựa trên thuật tố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 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 tố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 tốn K người láng giềng 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 : ( , , ) ( | ) c o s ( , ) x N c x D k S c o r e c x x x ′∈ ′= ∑ Trong đĩ Nc(x, D, k) là tập con chỉ chứa các đối tượng thuộc lớp c của tập N(x, D, k). Khi đĩ tài liệu x sẽ được phân vào lớp c0 nếu: { }CcxcscoreMaxxocscore ∈= ),|()|( ¾ Phương pháp K người láng giềng gần nhất là một phương pháp đươn giản. Tuy nhiên, thuật tốn này ổn định và sai sĩt thấp khi số văn bản trong tập văn bản láng giềng phải lớn. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 18 -  2.2. Mơ hình cây quyết định (Decision Tree) Trong lý thuyết quyết định, một cây quyết định là một đồ thị những quyết định và những kết quả cĩ khả năng của chúng (bao gồm cả giá phải trả và độ rủi ro) được sử dụng để tạo ra một đường đi tới đích [4]. Cây quyết định là một dạng đặc biệt của cấu trúc cây được xây dựng để trợ giúp việc ra quyết định. Trong lĩnh vực học máy, cây quyết định là một mơ hình dự đốn, cĩ nghĩa là từ việc quan sát các item để rút ra kết luận về giá trị đích của item đĩ. Mỗi nút bên trong tương đương với một biến, mỗi cung đi tới một nút con tương ứng với giá trị cĩ thể của biến đĩ. Các là tương ứng với giá trị đích được dự đốn cho các biến. Kỹ thuật học máy sử dụng việc xây dựng cây quyết định trên tập dữ liệu được gọi là học cây quyết định hay đơn giản chỉ là cây quyết định. Học cây quyết định cũng là một phương pháp rất thơng dụng trong khai phá dữ liệu. Trong đĩ cây quyết định mơ tả cấu trúc cây mà ở đĩ các lá đại diện cho các lớp và các nhánh cây biểu diễn sự kết hợp của các đặc trưng dẫn dắt tới việc phân lớp. Một cây quyết định cĩ thể được học bằng cách chia tập nguồn thành các tập con dựa trên giá trị các thuộc tính kiểm tra [4], [5]. Quá trình này được lặp lại trên từng tập con thu được. Quá trình đệ quy sẽ kết thúc khi khơng thể chia tiếp được nữa hoặc khi từng phần tử của tập con được gán với một lớp đơn [5]. Cây quyết định được mơ tả bằng cách tính tốn xác suất cĩ điều kiện. Cây quyết định cũng cĩ thể được mơ tả như là một kỹ thuật tính tốn và hỗ trợ tốn học, kỹ thuật này hỗ trợ việc mơ tả, phân loại và khái quát tập dữ liệu đưa vào. Dữ liệu đưa vào dạng ghi cĩ dạng: (x, y) = (x1, x2, … ,xk, y ) Biến phụ thuộc y là biến mà chúng ta cố gắng để biết, phân lớp hay tổng quát hĩa, cịn các biến x1, x2,… là các biến giúp ta thực hiện cơng việc đĩ. Để xây dựng được cây quyết định của tập dữ liệu nào đĩ chúng ta phải hiểu được khái niệm độ đo Entropy và Information Gain (Lợi ích thơng tin). Khái niệm lượng thơng tin và độ đo Entropy: Khái niệm lượng thơng tin được Shanon (nhà tốn học, nhà vật lý) [7] đưa ra năm 1948 thơng qua khái niệm trung gian là “độ bất định” trong dự án khả năng xảy ra trước khi nhận được thơng tin. Sau khi nhận được thơng tin, nếu độ bất định giảm đi thì cĩ thể coi lượng thơng tin nhận được là bằng mức độ giảm đi của độ bất định. Nếu ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 19 -  dự đốn càng nhiều tình huống cĩ thể xảy ra thì độ bất định trong dự báo càng lớn. Tuy nhiên Shanon cũng cho rằng trong n tình huống dự đốn cĩ thể xảy ra khơng nhất thiết cả n tình huống đều cĩ khả năng xảy ra như nhau, do vậy cơng thức tính độ bất định do ơng đưa ra cĩ tính tới các xác suất khác nhau của dự báo. Độ đo entropy của biến ngẫu nhiên rời rạc x với n trạng thái cĩ thể 1, 2, … , n là: ∑ ∑ = = −=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= n i n i ipip ip ipxH 1 1 22 )(log)()( 1log)()( Cơng thức này hồn tồn trùng với cơng thức tính Entropy trong nhiệt động học do nhà tốn học Boltzmann người áo đưa ra. Theo nguyên lý thứ 2 của nhiệt động học thì một hệ kín, khơng cĩ trao đổi năng lượng bên ngồi tất yếu sẽ chuyển động đến trạng thái cân bằng tới khi các bộ phận cấu thành của hệ thống đĩ giống nhau, đồng nhất và mất đi cấu trúc hay là tan vỡ trật tự và trở nên hỗn độn. Entropy là đại lượng để đo trạng thái mất trật tự, mất cấu trúc trong hệ thống. Độ đo entropy luơn là một số dương [7]. Lợi ích thơng tin (Information Gain) Gain(S, A) là lợi ích thơng tin mà thuộc tính A mang lại cho sự phân lớp tập S. A cĩ m giá trị v1, v2, … , vm Ký hiệu Svi = {x ∈ S | x cĩ giá trị thuộc tính A là vi} U m i vi SS 1= = ∑ = = m i vi vi SEntropy S S ASGain 1 )( || || ),( |S| là số phần tử của tập S Thuật tốn tìm cây quyết định: Cho tập ví dụ huấn luyện D. Tìm cây quyết định phù hợp với D. Bước 1: Khởi tạo cây một đỉnh gốc Tồn bộ tập ví dụ huấn luyện D đều đi vào đỉnh này. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 20 -  Bước 2: Repeat Chọn một đỉnh lá chưa gán nhãn để phát triển gọi là đỉnh hiện thời Giả sử tập ví dụ huấn luyện đi vào đỉnh này là S 2.1 If (S = rỗng) Then (gán nhãn chung nhất trong D) Else 2.2 if (tất cả các ví dụ trong S đều được gán cùng một nhãn c) Then (đỉnh hiện thời được gán nhãn c) Else 2.3 Đỉnh hiện thời được gán nhãn là thuộc tính A trong đĩ A = argmax Gain (S, Ai) Ai: ứng viên là nhãn của đỉnh hiện thời và mỗi giá trị v của A được gán nhãn cho nhánh đi từ A tới đỉnh mới. Tập ví dụ huấn luyện đi tới đỉnh mới đĩ là Sv trong đĩ Sv = {s ∈ S | s cĩ giá trị của thuộc tính A là v} Until (tất cả các đỉnh của cây đều được gán nhãn) ¾ So với các phương pháp khác trong Data Mining, phương pháp cây quyết định cĩ những ưu điểm nổi bất như: - Rất dễ hiểu và dễ giải thích: mọi người đều cĩ thể hiểu mơ hình cây quyết định qua một số giải thích tổng quát ban đầu. - Dữ liệu dùng cho cây quyết định chỉ là những dữ liệu căn bản hoặc cĩ thể khơng cần thiết. Một số kỹ thuật khác cĩ thể địi hỏi dữ liệu chuẩn, tạo các biến giả và loại bỏ đi các giá trị trống. - Cĩ khả năng xử lý cả dữ liệu thực và dữ liệu mập mờ. Một số kỹ thuật khác chỉ sử dụng những tập dữ liệu đặc biệt chẳng hạn như mạng nơron cĩ thể chỉ sử dụng các biến là số. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 21 -  - Cĩ thể kiểm chứng mơ hình bằng cách thử thống kê. - Cĩ khả năng thực hiện tốt đối với dữ liệu lớn trong thời gian ngắn: một lượng lớn dữ liệu cĩ thể được phân tích bằng máy tính cá nhân trong thời gian ngắn đủ để người sử dụng đưa ra quyết định dựa trên sự phân tích đĩ. Tuy nhiên sử dụng phương pháp cây quyết định cĩ thể xảy ra hiện tượng overfit, tức là tồn tại một giả thuyết h phù hợp với tập ví dụ huấn luyện nhưng tiên đốn khơng chính xác bằng giả thuyết h’ ít phù hợp với tập ví dụ huấn luyện hơn so với h. Để giải quyết vấn đề này chúng ta phải dùng cách chặt bớt cây (pruning), bỏ bớt đi các nhánh dữ liệu nhiễu và dư thừa… 2.3. Thuật tốn máy hỗ trợ vector (SVM – Suport Vector Machine) Thuật tốn máy vector hỗ trợ (Support Vector Machines - SVM) được Corters và Vapnik giới thiệu vào năm 1995 [13]. SVM rất hiệu quả để giải quyết các bài tố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 tốn SVM ban đầu chỉ được thiết kế để giải quyết bài tố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 tốn phân lớp văn bản [13], bởi vì đĩ là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài tố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 tố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à 1 ( ) 0 h x ⎧=⎨⎩ Nếu 0)( >xf ngược lại ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 22 -  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 tốn đơn giản để xác định siêu phẳng : 1. w ←0 2. w0←0 3. repeat 4. e←0 5. for i←1,…,n 6. do s←sign(yi(wTxi +w0) 7. if s<0 8. then w ←w + yixi 9. w0←w0 + yixi 10. e←e+1 11. util e=0 12. return (w,w0) Đ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 tố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. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 23 -  Trong hình 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 tố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 4. Mối quan hệ giữa các siêu phẳng phân cách ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 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 [14]. Đị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 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 + ≥ = 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. Hình 5. Siêu phẳng tối ưu và biên ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 25 -  Đặ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 tố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: 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. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 26 -  ¾ Phương pháp SVM được coi là phương pháp hiệu quả để giải quyết bài tốn phân lớp với dữ liệu cĩ số chiều lớn như các vector biểu diễn văn bản. Về mặt lý thuyết, thuật tốn phân lớp nhị phân này cũng cĩ thể sử dụng cho bài tốn phân lớp đa lớp bằng cách chuyển bài tốn đa lớp thành bài tốn nhị phân. Tuy nhiên, đối với bài tốn phân lớp văn bản sử dụng phương pháp SVM thì việc lựa chọn thuộc tính cho từng phân lớp lại là vấn đề cực kỳ quan trọng, nĩ quyết định đến hiệu quả của phân lớp. 2.4. Mơ hình Entropy cực đại 2.4.1. Định nghĩa nguyên lý entropy cực đại Cĩ rất nhiều thuật tốn của phương pháp học giám sát đã được đưa ra để giải quyết bài tốn phân lớp văn bản như giả thiết Nạve Bayes [Lewis, 1998; McCallum and Nigam, 1998; Sahami, 1996], K - người láng giềng gần nhất [Yang, 1999], máy hỗ trợ vector [Joachims, 1998; Dumais et al., 1998], boosting [Schapire and Singer, 1996], Các thuật tốn học luật [Cohen and Singer, 1996; Slattery và Craven, 1998]. Tuy nhiên, trong số đĩ chưa cĩ một thuật tốn nào được chứng minh là làm tốt hơn các thuật tốn khác trên nhiều miền ứng dụng. Sử dụng kỹ thuật Entropy cực đại cho bài tốn phân lớp văn bản như là một cách thay thế các thuật tốn đã được dùng trước đây. Entropy cực đại đã được sử dụng rộng rãi cho nhiều ngơn ngữ tự nhiên. Entropy cực đại đã chứng tỏ được là một thuật tốn hiệu quả và cạnh tranh cao trong nhiều miền ứng dụng. Đối với bài tốn phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mơ hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng / đều nhất cĩ thể” [15]. Tập dữ liệu học (tức là tập gồm các dữ liệu đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mơ hình, đĩ là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mơ hình sẽ tiến hành tính tốn để cĩ được một phân phối cho Entropy cực đại [10], [15]. Ví dụ một mơ hình Entropy cực đại: “Giả sử với bộ phân lớp về lĩnh vực kinh tế trên báo VnEconomy cĩ bốn lớp chính được chỉ ra là ngân_hàng, chứng_khốn, bất_động_sản, doanh_nghiệp. Các thống kê dữ liệu chỉ ra rằng trung bình 70% các tài liệu trong lớp ngân_hàng cĩ chứa từ vay_vốn. Như vậy một cách trực quan cĩ thể thấy ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 27 -  rằng nếu một tài liệu D cĩ chứa từ vay_vốn thì xác suất được phân vào lớp ngân_hàng là 70% và xác suất phân vào ba lớp cịn lại là 10% đối với mỗi lớp. Nếu tài liệu D khơng chứa từ vay_vốn thì xác suất phân phối của D là 25% đều cho mỗi lớp.” Trong ví dụ trên, “nếu tài liệu chứa cụm từ vay_vốn thì cĩ xác suất phân vào lớp ngân_hàng là 70%” là một ràng buộc của mơ hình. 2.4.2. Các ràng buộc và đặc trưng Trong nguyên lý Entropy cực đại, chúng ta sử dụng tập dữ liệu mẫu làm để thiết lập ràng buộc cho phân phối điều kiện. Với mỗi ràng buộc được mơ tả bởi một đặc tính của tập dữ liệu học. Một đặc trưng trong mơ hình Entropy cực đại được biểu diễn bởi một hàm fi(d, c), trong đĩ d là tài liệu và c là lớp. Entropy cực đại cho phép giới hạn mơ hình phân phối để cĩ thu các giá trị kỳ vọng cho mỗi đặc trưng của tập dữ liệu. Vì vậy, ta cĩ thể đặt xác suất phân phối của dữ liệu d cho lớp c là P(c|d) thỏa mãn phương trình sau: Trong quá trình huấn luyện, phân phối tài liệu P(d) là khơng biết và chúng ta khơng cần quan tâm tới nĩ. Vì vậy, ta chỉ sử dụng tập dữ liệu mẫu như là một điều kiện để phân phối dữ liệu tuân theo ràng buộc sau: Như vậy khi sử dụng entropy cực đại, bước đầu tiên là cần xác định tập các hàm đặc tính sẽ sử dụng cho phân lớp. Sau đĩ, với mỗi đặc tính, ước lượng giá trị kỳ vọng thơng qua tập dữ liệu học và tạo ra các ràng buộc cho mơ hình phân phối. 2.4.3. Mơ hình Entropy cực đại 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 trưng của tài liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Tư tưởng cơ bản của phương pháp Entropy cực đại là tìm ra một mơ hình cĩ phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà khơng đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy cĩ điều kiện: ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 28 -  ( ) ( ) ( ) ( ) , | log |≡ −∑ % c d H p p c p c d p d c ( )* a rg m a x ∈ = p C p H p Trong đĩ p* là phân xác suất tối ưu. Mơ hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng được biểu diễn dưới một hàm nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mơ hình phải thỏa mãn. Mỗi đặc trưng fi được gán cho một trọng số iλ . Khi đĩ, bài tốn phân lớp được đưa về bài tốn ước lượng xác suất cĩ điều kiện: Trong đĩ Z(d) là biểu thức chuẩn hĩa để đảm bảo điều kiện ( ) 1| =∑ dcp . Từ đĩ đưa ra cơng thức sau: 2.3.4. Entropy cực đại cho phân lớp văn bản Để áp dụng mơ hình Entropy cực đại cho một miền, chúng ta cần phải chọn ra một tập các đặc trung để sử dụng thiết lập các ràng buộc. Đối với phân lớp văn bản với mơ hình Entropy cực đại, chúng ta sử dụng số lượng từ như là các đặc trưng. Trong nghiên cứu này cho với mỗi từ kết hợp, ta đưa ra một đặc tính như sau: Trong đĩ, N(d, w) là số lần từ w xuất hiện trong tài liệu d, và N(d) là số lượng các từ cĩ trong tài liệu d. Trong cơng thức này, nếu một từ xuất hiện thường xuyên trong một tài liệu, ta sẽ tính trọng số cho các cặp từ này và thấy rằng trọng số đĩ sẽ cao hơn so với trọng số của các từ ghép trong tài liệu. Trong hầu hết ngơn ngữ tự nhiên sử dụng Entropy cực đại thì các đặc trưng thường là đặc trưng nhị phân. Trong phân lớp văn bản, chúng ta mong muốn các đặc trưng được tính bằng số lần suất hiện của một từ trong một tài liệu cĩ thể củng cố cho phân lớp. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 29 -  Một trong những khía cạnh đặc biệt của Entropy cực đại là nĩ khơng bị bất kỳ giả thuyết độc lập nào ràng buộc. Ví dụ, với cụm từ “Buenos Aires”, hai từ này hầu như luơn xuất hiện động thời cùng nhau.Với giả thiết Nạve Bayes sẽ đếm số từ xuất hiện hai lần trong cụm từ này. Mặt khác, Entropy cực đại sẽ giảm giá trị trọng số iλ của mỗi đặc trưng đi một nửa. Một trong những hệ của việc khơng phụ thuộc vào bất kỳ giả thuyết độc lập nào đĩ là các sơ đồ và các cụm từ cĩ thể được thêm vào các đặc trưng của Entropy cực đại một cách dễ dàng mà khơng cần lo lắng rằng các đặc tính này chồng lên nhau. ¾ Ưu điểm của mơ hình Entropy cực đại: - Cho phép khả năng hầu như khơng hạn chế trong việc biểu diễn các vấn đề phức tạp về tri thức thơng qua dạng các hàm đặc trưng. - Cĩ thể giải quyết nhiều dạng thuộc tính khác nhau. - Các giả thiết khơng cần phải độc lập với nhau. - Trọng số của các đặc trưng được xác định một cách tự động. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 30 -  Chương 3. BÀI TỐN PHÂN LỚP VĂN BẢN TÀI CHÍNH NGÂN HÀNG TIẾNG VIỆT 3.1. Một số đặc trưng của dữ liệu tài chính ngân hàng trong tiếng Việt Luận văn tập trung nghiên cứu trên tập các văn bản về lĩnh vực tài chính ngân hàng Việt Nam với ngơn ngữ Tiếng Việt. Bất kỳ một ngơn ngữ nào cũng cĩ các đặc trưng riêng, hơn nữa Tiếng Việt cịn là ngơn ngữ rất đa dạng, phong phú về từ ngữ, ngữ pháp… Một số đặc điểm của Tiếng Việt được liệt kê dưới đây: - Tiếng Việt thuộc ngơn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. - Đặc điểm ngữ âm: Trong Tiếng Việt cĩ một loại đơn vị đặc biệt gọi là “tiếng”. Về mặt ngữ âm mỗi tiếng là một âm tiết. - Đặc điểm từ vựng: mỗi tiếng, nĩi chung, là một yếu tố cĩ nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị cĩ nghĩa của Tiếng Việt. Từ tiếng người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng nhờ phương pháp ghép và láy từ... Vốn từ vựng tối thiểu của Tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới nột cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, cĩ thể được biểu thị theo nhiều cách khác nhau. - Đặc điểm ngữ pháp: Từ của Tiếng Việt khơng biến đổi hình thái khi kết hợp các từ để làm thành kết cấu như ngữ, câu Tiếng Việt rất coi trọng trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong Tiếng Việt, nĩi “Anh ta lại đến” là khác với nĩi “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trị chính, từ đứng sau giữ vai trị phụ. Nhờ trật tự kết hợp từ mà ta thấy “cảm tình” khác với “tình cảm”. Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu Tiếng Việt. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 31 -  Phương thức hư từ cũng là phương pháp phổ biến trong Tiếng Việt. Nhờ hư từ mà tổ hợp từ “anh của em” khác với tổ hợp từ “anh và em” hay “anh vì em”. Ngồi những đặc điểm chung của Tiếng Việt, văn bản tài chính ngân hàng Việt Nam cịn cĩ những đặc điểm riêng, chẳng hạn cĩ chứa những từ, cụm từ đặc trưng như: “ngân hàng”, “cho vay”, “lãi suất vay vốn”, “lãi suất tiết kiệm”, “cổ phiếu”, “thị trường tiền tệ”, “huy động vốn”… 3.2. Xây dựng một số lớp trong lĩnh vực tài chính ngân hàng Trong phần này, khĩa luận sẽ đi xây dựng một tập các nhãn (lớp) trên lĩnh vực tài chính ngân hàng. Thơng qua việc khảo sát dữ liệu về tài chính ngân hàng được thu thập từ các trang Web và quá trình nghiên cứu về nghiệp vụ ngân hàng, tài chính Việt Nam [6], khĩa luận xin đề xuất một tập các nhãn (lớp) để đưa ra thử nghiệm ban đầu, với những khái niệm cơ bản sau: ƒ Huy động vốn: Ngân hàng được huy động vốn dưới các hình thức sau: - Nhận tiền gửi của tổ chức kinh tế, cá nhân và các tổ chức tín dụng khác dưới hình thức tiền gửi khơng kỳ hạn, tiền gửi cĩ kỳ hạn, tiền gửi tiết kiệm và các loại tiền gửi khác. - Phát hành chứng chỉ tiền gửi, trái phiếu và giấy tờ cĩ giá khác để huy động vốn của tổ chức, cá nhân trong nước và nước ngồi. - Đi vay vốn của các tổ chức tín dụng trong và ngồi nước. - Vay vốn ngắn hạn của Ngân hàng Nhà Nước. - Các hình thức huy động vốn khác theo quy định của Ngân hàng Nhà Nước. ¾ Dữ liệu thuộc lớp huy động vốn gồm những văn bản cĩ nội dung liên quan tới một trong những hoạt động huy động vốn vừa được nêu như: thơng tin về lãi suất gửi tiền tiết kiệm, các hình thức vay vốn của ngân hàng đối với các tổ chức tín dụng khác… ƒ Tín dụng: Ngân hàng thương mại được cấp tín dụng cho tổ chức, cá nhân dưới các hình thức cho vay, chiết khấu thương phiếu và giấy tờ cĩ giá khác, bảo lãnh, cho thuê tài chính và các hình thức khác theo quy định của Ngân hàng Nhà Nước. Trong các hoạt động cấp tín dụng, cho vay là hoạt động quan trọng và chiếm tỷ trọng lớn nhất. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 32 -  - Cho vay: Ngân hàng thương mại được cho các tổ chức, cá nhân vay vốn dưới các hình thức sau: o Cho vay ngắn hạn (dưới 12 tháng) nhằm đáp ứng nhu cầu vốn cho sản xuất, kinh doanh, dịch vụ và đời sống. o Cho vay trung hạn, dài hạn (trên 12 tháng) để thực hiện các dự án đầu tư phát triển sản xuất, kinh doanh, dịch vụ và đời sống. - Bảo lãnh: Ngân hàng thương mại được bảo lãnh vay, bảo lãnh thanh tốn, bảo lãnh thực hiện hợp đồng, bảo lãnh đấu thầu và các hình thức bảo lãnh ngân hàng khác bằng uy tín và bằng khả năng tài chính của mình đối với một khách hàng thương mại khơng được vượt quá tỷ lệ so với vốn tự cĩ của ngân hàng thương mại. - Chiết khấu: Ngân hàng thương mại được chiết khấu thương phiếu và các giấy tờ cĩ giá ngắn hạn khác đối với tổ chức, cá nhân và cĩ thể tái chiết khấu các thương phiếu và các giấy tờ cĩ giá ngắn hạn khác đối với tổ chức tín dụng khác. - Cho thuê tài chính: Ngân hàng thương mại được hoạt động cho thuê tài chính nhưng phải thành lập cơng ty cho thuê tài chính riêng. Việc thành lập, tổ chức và hoạt động của cơng ty cho thuê tài chính thực hiện theo Nghị định của Chính Phủ về tổ chức và hoạt động của cơng ty cho thuê tài chính. ¾ Dữ liệu thuộc lớp tín dụng gồm những văn bản mang thơng tin về hoạt động cho vay vốn, bảo lãnh, chiết khấu, cho thuê tài chính của ngân hàng đối với cá nhân và tổ chức. ƒ Dịch vụ thanh tốn: Để thực hiện các dịch vụ thanh tốn giữa các doanh nghiệp thơng qua ngân hàng, ngân hàng thương mại được mở tài khoản tiền gửi thanh tốn cho khách hàng trong và ngồi nước. Hoạt động dịch vụ thanh tốn của ngân hàng thương mại bao gồm các hoạt động sau: - Cung cấp các phương tiện thanh tốn như thẻ ghi nợ (debit card), thẻ tín dụng (credit card) cĩ phạm vi thanh tốn cĩ thể thực thanh tốn trong và ngồi nước. - Thực hiện các dịch vụ thanh tốn theo nhu cầu của khách hàng (ủy nhiệm chi, thanh tốn lương, thanh tốn hĩa đơn,…). ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 33 -  - Thực hiện dịch vụ thu hộ và chi hộ trong nội bộ ngân hàng hoặc liên ngân hàng trong nước. - Thực hiện các dịch vụ thanh tốn khác theo qui định của Ngân hàng Nhà Nước. - Thực hiện các dịch vụ thanh tốn quốc tế đối với khách hàng mở thư tín dụng (letter credit). - Thực hiện dịch vụ chuyển tiền trong và ngồi nước. ¾ Dữ liệu thuộc lớp dịch vụ thanh tốn gồm những văn bản mang thơng tin về các hoạt động dịch vụ thanh tốn của ngân hàng như: cung cấp các phương tiện thanh tốn, các dịch vụ liên quan đến thanh tốn như đã nêu ở trên… ƒ Ngoại tệ: Gồm các thơng tin về việc ngân hàng thương mại trực tiếp kinh doanh hoặc thành lập cơng ty trực thuộc để kinh doanh ngoại hối, tiền tệ và vàng trên thị trường trong nước và thị trường quốc tế. ƒ Chứng khốn: Tất cả các ngân hàng thương mại muốn kinh doanh chứng khốn đều phải lập cơng ty trực thuộc ngân hàng. Chẳng hạn, các ngân hàng ngoại quốc doanh như Vietcombank, Incombank, Ngân hàng Đầu tư và Phát triển, Ngân hàng Nơng nghiệp và phát triển nơng thơn,… đều cĩ thành lập cơng ty chứng khốn. Cơ sở hạ tầng của thị trường chứng khốn bao gồm những hệ thống và tổ chức cung cấp phương tiện cho giao dịch, thanh tốn, ký gửi và lưu ký cổ phiếu, trái phiếu. Ngồi ra, cịn bao gồm cả những quy định pháp lý làm cơ sở cho giao dịch và quản lý thị trường cổ phiếu. ¾ Dữ liệu thuộc lớp chứng khốn gồm những văn bản mang thơng tin về giao dịch, thanh tốn, ký gửi, lưu ký cổ phiếu, trái phiếu của ngân hàng trên thị trường chứng khốn. 3.3. Bài tốn phân lớp văn bản tài chính ngân hàng trong Tiếng Việt 3.3.1. Phát biểu bài tốn: - Input: một tập văn bản (text) dữ liệu thơng tin về tài chính ngân hàng. - Output: Phân loại từng văn bản vào các lớp tương ứng. Ví dụ, đưa vào một văn bản cĩ chứa nhiều cụm từ đặc trưng như “cho vay vốn” thì chương trình phải xác định được đặc trưng này và xếp văn bản này vào lớp tín dụng. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 34 -  3.3.2. Phương pháp phân lớp Như đã trình bày ở chương 3, cĩ rất nhiều phương pháp để giải quyết bài tốn phân lớp văn bản như: K người láng giềng gần nhất, Cây quyết định, Máy hỗ trợ vector (SVM), Mơ hình Entropy cực đại. Tùy đặc điểm của từng miền dữ liệu mà mỗi phương pháp cĩ những ưu nhược điểm riêng. Tuy nhiên, Dựa trên kết quả thực nghiệm của Hacioglu [25] và Li [22], Luận văn của Nguyễn Thị Hương Thảo [1], Trần Minh Tuấn [2] đã cho thấy sử dụng phương pháp SVM, Entropy vào bài tốn phân lớp văn bản cho kết quả rất khả quan. Mặt khác, trong quá trình nghiên cứu các thuật tốn đã nêu ở chương 2, mơ hình Entropy cực đại cĩ ưu điểm hơn so với phương pháp cây quyết định ở chỗ: việc ước lượng tham số trong mơ hình Entropy cực đại khơng cần phải phân chia dữ liệu dẫn tới khơng xảy ra hiện tượng phân mảnh dữ liệu, do đĩ khơng cần tới thuật tốn làm mịn để chặt bớt đi các nhánh dữ liệu dư thừa, thưa thớt . So với phương pháp SVM thì phương pháp Entropy cực đại cĩ một ưu điểm lớn là việc sử dụng các đặc trưng linh hoạt, dễ dàng khai báo các thuộc tính. Dựa vào kết quả thực nghiệm của khĩa luận Trần Minh Tuấn [2] cịn cho thấy, đối với miền dữ liệu Tiếng Việt thì phương pháp Entropy cực đại cho kết quả khả quan hơn phương pháp SVM. Do cĩ những ưu điểm so với các phương pháp đã trình bày, phần tiếp theo luận văn sẽ áp dụng mơ hình Entropy cực đại cho bài tốn phân lớp văn bản tài chính ngân hàng Tiếng Việt. 3.3.3. Mơ hình của bài tốn phân lớp văn bản tài chính ngân hàng Để xây dựng được bài tốn phân lớp văn bản dữ liệu về tài chính ngân hàng như trên, trước hết chúng ta cần thu thập dữ liệu và thực hiện việc tách từ trong các văn bản, loại bỏ từ dừng và biểu diễn các văn bản dưới dạng đặc trưng đầu vào cho mơ hình Entropy cực đại. Các bước trong quá trình phân lớp văn bản được thực hiện như sau: ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 35 -  Hình 6. Mơ hình bài tốn phân lớp dữ liệu tài chính ngân hàng Quá trình tiền xử lý (preprocessing) dữ liệu thơng tin về tài chính ngân hàng gồm cách bước sau: - Tách từ: Với một tập văn bản đầu vào, thơng qua module tách từ, các từ trong văn bản sẽ được nhận biết, mỗi từ sẽ được biểu diễn trong một cặp dấu ngoặc vuơng ( [ ] ) và cách nhau bởi một kí tự trắng. Module tách từ sẽ giúp chúng ta phân biệt được những từ cĩ nghĩa, là cơ sở để loại bỏ từ dừng. Ví dụ, với từ “cao cấp”, nếu văn bản khơng qua xử lý tách từ và trong bộ từ dừng cĩ từ Tập văn bản đầu vào Module tách từ Tiếng Việt Module loại bỏ từ dừng Biểu diễn tất cả các văn bản dưới dạng 1 văn bản đặc trưng Với mỗi một dịng trong văn bản đặc trưng Module phân lớp văn bản Tập văn bản kết quả Văn bản đã được phân lớp Lặp hết các dịng trong văn bản đặc trưng ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 36 -  “cao” thì khi qua xử lý loại bỏ từ dừng thì từ “cao” bị loại bỏ ngay lập tức mà khơng cần biết tới nghĩa của nĩ khi đi cùng từ đằng sau. Ngược lại, nếu văn bản được xử lý tách từ thì sẽ ko cĩ trường hợp loại bỏ này xảy ra. Module tách từ làm cho quá trình loại bỏ từ dừng chính xác hơn. Ví dụ, nội dung của một đoạn văn bản dữ liệu về tài chính ngân hàng sau khi qua bộ tách từ: [Đáy] [lãi suất] [cho vay] [về] [mức] [12%] / [năm][Lãi suất] [cho vay] [bằng] [đồng] [Việt Nam] [vừa] [thiết lập] [đáy] [mới] [ở] [mức] [12%] / [năm] [sau] [khi] [Ngân hàng] [Nhà nước] [cơng bố] [hạ] [lãi suất] [cơ bản] [VND] [xuống] [cịn] [11%] / [năm] .[Vietcombank] [tạo] [đáy] [lãi suất] [cho vay] [mới] [ở] [mức] [12%] / [năm][Từ] [nhiều] [ngày nay] , [các] [ngân hàng] [thương mại] [đã] [cùng] [vào] [cuộc đua] [giảm] [lãi suất] [cho] [vay] [nhằm] [giải] [ngân] [nguồn] [tiền] [đang] [được] [đánh giá] [là] [khá] [dư thừa] [trong] [kho]. - Loại bỏ từ dừng: Từ dừng (stop-words) dùng để chỉ các từ mà xuất hiện quá nhiều trong các văn bản của tồn tập kết quả, thường thì khơng giúp ích gì trong việc phân biệt nội dung của các tài liệu. Trong tiếng Anh, cĩ nhiều từ chỉ dùng để phục vụ cho biểu diễn cấu trúc chứ khơng biểu đạt nội dung của nĩ, như là “a”, “the” (mạo từ), “in” (giới từ), “but” (liên từ), động từ phổ biến cĩ dạng “to”, “be” và một số trạng từ và tính từ đặc biệt được xem là những từ dừng. Trong Tiếng Việt, các từ “và”, “hoặc”, “nhưng”, “cũng”… xuất hiện rất nhiều trong các văn bản, cũng được coi là các từ dừng. Luận văn tập trung nghiên cứu thực nghiệm trên tập dữ liệu tài chính ngân hàng, cho thấy những con số, dấu câu khơng cĩ ý nghĩa đối với quá trình phân lớp nên cũng coi đĩ là những từ dừng. Danh sách từ dừng được sử dụng đối với văn bản tài chính ngân hàng trong luận văn này sẽ được trình bày cuối luận văn. Vì đặc điểm của từ dừng nên chúng được loại bỏ mà khơng ảnh hưởng đến các cơng việc biểu diễn văn bản tiếp theo. Hơn thế nữa giai đoạn xử lý loại bỏ từ dừng sẽ làm cho văn bản kết quả giữ lại được các từ đặc trưng, loại bỏ được những từ gây nhiễu. Tách từ và loại bỏ từ dừng là hai bước trong quá trình tiền xử lý dữ liệu đầu vào cho bộ phân lớp, làm cho hiệu suất của quá trình phân lớp tăng. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 37 -  Các văn bản sau khi được xử lý tách từ sẽ là đầu vào cho bước loại bỏ từ dừng. Thơng qua modulo loại bỏ từ dừng, các tiếng trong một từ sẽ được cách nhau bởi một kí tự gạch dưới ( _ ) và các từ sẽ cách nhau bởi một kí tự trắng. Ví dụ, nội dung của một đoạn văn bản sau khi loại bỏ từ dừng: lãi_suất cho_vay mức Lãi_suất cho_vay đồng Việt_Nam thiết_lập mức Ngân_hàng Nhà_nước cơng_bố hạ lãi_suất cơ_bản VND xuống Vietcombank tạo đáy lãi_suất cho_vay mức Từ ngày_nay ngân_hàng thương_mại cuộc_đua giảm lãi_suất vay nhằm giải ngân nguồn tiền đánh_giá khá dư_thừa kho Mức lãi_suất cho_vay ưu_đãi đáy cũ thiết_lập - Biểu diễn tất cả các văn bản dưới dạng 1 văn bản đặc trưng: Tất cả các văn bản sau khi đã được tách từ và loại bỏ từ dừng sẽ được biểu diễn dưới dạng một văn bản đặc trưng đầu vào cho bộ phân lớp như sau: nội dung của mỗi văn bản được biểu diễn trên một dịng và từ cuối cùng trên dịng đĩ là tên lớp. Ví dụ: Nội dung văn bản A Tên_lớp_1 Nội dung văn bản B Tên_lớp_2 … ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 38 -  Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Dữ liệu và chương trình Dữ liệu dùng để thực nghiệm cho bộ phân lớp văn bản về tài chính ngân hàng là các văn bản được lấy từ trang Web: Tập dữ liệu cĩ tất cả 1075 tài liệu. Tồn bộ tập dữ liệu của thử nghiệm đều được gán nhãn bằng tay. 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 1. Phân bố dữ liệu học và kiểm tra Tổng số tài liệu 1075 Tập dữ liệu học 717 Tập dữ liệu kiểm tra 358 Các phân lớp của dữ liệu được xậy dựng như đã giới thiệu ở chương 3, mục 3.2 bao gồm 5 lớp (huy động vốn, tín dụng, dịch vụ thanh tốn, ngoại tệ và chứng khốn). Dữ liệu dùng cho huấn luyện cùng số lượng tài liệu cho mỗi lớp được mơ tả trong Bảng 2. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 39 -  Bảng 2. Tập dữ liệu huấn luyện STT Phân lớp Ký hiệu Số lượng tài liệu 1 Ngoại tệ NgoaiTe 273 2 Huy động vốn HuyDongVon 104 3 Dịch vụ thanh tốn DichVuThanhToan 60 4 Chứng khốn ChungKhoan 137 5 Tín dụng TinDung 143 Tổng số: 717 Tập dữ liệu dùng để kiểm tra được mơ tả trong bảng 3, số lượng tài liệu của mỗi lớp tỉ lệ với số lượng tài liệu trong tập dữ liệu dùng để huấn luyện. Bảng 3. Tập dữ liệu kiểm tra STT Phân lớp Ký hiệu Số lượng tài liệu 1 Ngoại tệ NgoaiTe 150 2 Huy động vốn HuyDongVon 34 3 Dich vụ thanh tốn DichVuThanhToan 34 4 Chứng khốn ChungKhoan 70 5 Tín dụng TinDung 70 Tổng số: 358 4.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. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 40 -  Khĩa luận xây dựng chương trình thực hành phân lớp được viết trên ngơn ngữ java, mơi trường Jcreator, Elipse. Chương trình này tích hợp module tiền xử lý văn bản (do khĩa luận xây dựng) và sử dụng thư viện của tác giả Phan, X.H [23]. 4.3. Thiết kế và kết quả thực nghiệm Khĩa luận thử nghiệm theo mơ hình nguyên lý Entropy cực đại. 4.3.1. Thiết lập thơng số cho Entropy cực đại Với thuật tốn Entropy cực đại, khĩa luận sử dụng thư viện của tác giả Phan Xuân Hiếu [23], việc sử dụng địi hỏi phải thiết lập một số thơng số cho mơ hình. Các thơng số này được lựa chọn qua nhiều lần thử nghiệm, chi tiết được mơ tả ở bảng 4. Bảng 4. Tham số huấn luyện mơ hình Entropy cực đại Tham số Giá trị Mơ tả numIterations 10 Số bước lặp trong quá trình huấn luyện. fRareThreshold 0 Các mệnh đề mơ tả thơng tin ngữ cảnh phải xuất hiện nhiều hơn số này thì sẽ được dùng để xây dựng các đặc trưng. cpRareThreshold 0 Các đặc trưng xuất hiện nhiều hơn số này thì sẽ khơng bị loại bỏ khỏi tập dữ liệu huấn luyện. 4.3.2. Kết quả thực nghiệm Tiến hành thực nghiệm trên tập dữ liệu huấn luyện với số lượng bước lặp là 10. Các kết quả phân lớp thu được khá khả quan với thời gian khoảng 0.4594 giây/lần và được mơ tả trong một số bảng biểu và đồ thị sau. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 41 -  Bảng 5. Kết quả 10 lần huấn luyện với Entropy cực đại Độ chính xác Độ hồi tưởng F1 Bước lặp Thời gian Avg 1 Avg 2 Avg 1 Avg 2 Avg1 Avg2 1 0.766 81.04 55.87 39.43 55.87 53.05 55.87 2 0.485 81.95 81.56 74.95 81.56 78.29 81.56 3 0.453 82.99 82.68 76.39 82.68 79.56 82.68 4 0.406 84.59 87.15 84.75 87.15 84.67 87.15 5 0.422 86.38 89.39 86.43 89.39 86.40 89.39 6 0.422 87.64 90.22 86.98 90.22 87.31 90.22 7 0.39 84.67 87.43 84.28 87.43 84.48 87.43 8 0.422 86.49 88.83 86.46 88.83 86.48 88.83 9 0.39 87.73 89.66 87.47 89.66 87.60 89.66 10 0.407 86.73 88.83 86.92 88.83 86.82 88.83 Trung bình 0.4563 84.821 84.162 79.406 84.162 81.466 84.162 ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 42 -  Qua bảng trên, cho thấy kết quả khả quan nhất là ở bước lặp thứ 6 với độ đo F1 đạt 90.22% chi tiết bước lặp này như sau: Bảng 6. Kết quả của bước lặp thứ 6 Tên lớp Độ chính xác Độ hồi tưởng F1 NgoaiTe 96.64 96.00 96.32 HuyDongVon 71.43 73.53 72.46 DichVuThanhToan 96.77 88.24 92.31 ChungKhoan 87.84 92.86 90.28 TinDung 85.51 84.29 84.89 Avg1 87.64 86.98 87.31 Avg2 90.22 90.22 90.22 Trong bảng kết quả trên thì kết quả của phân lớp HuyDongVon là kém nhất với độ đo chính xác là 72.46% và tốt nhất là phân lớp NgoaiTe với độ đo chính xác là 96.32%. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 43 -  0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ đo F 1 F1-Avg2 F1-Avg1 Hình 7. Đồ thị biểu diễn sự phụ thuộc của độ đo F1 vào số lần lặp 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ ch ín h xá c củ a ph ân lớ p Độ chính xác Độ hồi tưởng F1 Hình 8. Tổng hợp độ đo qua 10 lần huấn luyện ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 44 -  96.32 72.46 92.31 90.28 84.89 0 20 40 60 80 100 120 Ng oa iTe Hu yD on gV on Di ch Vu Th an hT oa n Ch un gK ho an Tin Du ng Lớp Đ ộ đo F 1 Hình 9. Biểu đồ biểu diễn độ đo F1 của các lớp trong lần lặp thứ 6 4.4. Đánh giá kết quả thực nghiệm Việc tiến hành thực nghiệm trên tập dữ liệu huấn luyện là 717 dữ liệu cho 5 phân lớp cho kết quả tốt về độ đo F1 là 90.22%. Cả 5 bộ phân lớp đều cho độ đo F1 gần 90%, đặc biệt, bộ phân lớp NgoaiTe đạt kết quả rất cao là 96.32% cho cả độ chính xác và độ hồi tưởng. Bộ phân lớp HuyDongVon thu được kết quả thấp nhất với độ đo F1 là 72.46%. Do số lượng dữ liệu mẫu cho từng lớp khá cân bằng nhau nên khả năng đốn nhận của bộ phân lớp là khá tốt. Nhưng muốn khả năng này cao hơn nữa thì tập dữ liệu huấn luyện cần gia tăng thêm về số lượng, đảm bảo cung cấp đầy đủ các ràng buộc từ dữ liệu cho mơ hình. Như đã trình bày ở mục 2.4, tư tưởng chủ đạo của nguyên lý Entropy cực đại là thay vì thêm vào các ràng buộc mới, mơ hình tự tìm ra trong dữ liệu (tập câu hỏi mẫu) những ràng buộc và đặc trưng riêng cho từng phân lớp. Điều này làm cho sự phân lớp trong khi sử dụng mơ hình Entropy cực đại được đảm bảo cả khi tập dữ liệu khơng cĩ số lượng quá lớn và mỗi tài liệu chỉ chứa ít đặc trưng. Từ kết quả của thực nghiệm cho thấy khi xây dựng bộ phân lớp văn bản tiếng Việt sử dụng mơ hình Entropy cực đại cho kết quả rất tốt. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 45 -  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 tốn phân lớp văn bản thực sự cĩ vai trị ý nghĩa rất quan trọng trong việc tổ chức, quản lý cũng như tìm kiếm thơng tin trên nguồn tài nguyên lớn, đặc biệt với nguồn tài nguyên về lĩnh vực tài chính ngân hàng. Sự đa dạng của các thuật tốn phân lớp dữ liệu làm cho việc lựa chọn thuật tốn để xây dựng module phân lớp văn bản cho từng ngơn ngữ trở nên khĩ khăn hơn. Khĩa luận tiếp cận các vấn đề nĩi trên và nghiên cứu các thuật tốn phổ biến hiện nay, từ đĩ đưa ra phương pháp và thuật tốn áp dụng vào phân lớp dữ liệu ngân hàng tài chính trong tiếng Việt. Về mặt nội dung, khĩa luận đã đạt được những kết quả sau: - Nghiên cứu về bài tốn phân lớp văn bản: khái niệm, mơ hình, đánh giá phân lớp. Luận văn đã tập hợp và trình bày một số phương pháp phổ biến nhất hiện nay như k người láng giềng gần nhất, mơ hình cây quyết định, mơ hình Entropy cực đại, SVM. Sau đĩ trình bày ưu nhược điểm của từng phương pháp, từ đĩ đưa ra quyết định sử dụng mơ hình entropy cực đại khi áp dụng cho tiếng Việt. - Xây dựng nhãn / lớp cho văn bản tài chính ngân hàng trong tiếng Việt. - Xây dựng chương trình thi hành phân lớp văn bản được viết trên ngơn ngữ Java, mơi trường Eclipse được tích hợp từ module tiền xử lý văn bản (do khĩa luận xây dựng) và module phân lớp (khai thác mã nguồn bộ phân lớp Entropy cực đại). Kết quả thực nghiệm trên tập dữ liệu về lĩnh vực tài chính ngân hàng được crawler từ Web cho thấy tính khả thi của chương trình phân lớp văn bản sử dụng phương pháp Entropy cực đại với độ đo F1 đạt 90.22%. Bên cạnh đĩ, do thời gian và kiến thức cĩ hạn, khĩa luận vẫn cịn một vài hạn chế sau: - Chương trình sử dụng thuật tốn Entropy cực đại cho bài tốn phân lớp văn bản mới thi hành trên một bộ dữ liệu tiếng Việt nên chưa đối sánh kết quả trên nhiều bộ dữ liệu. Chưa thi hành nhiều thuật tốn để chọn được phương pháp tốt. Trong tương lại, khĩa luận sẽ tiếp tục hồn thiện mặt hạn chế đã đưa ra đĩ là sử dụng một số thuật tốn phân lớp khác với Entropy cực đại để tìm ra được thuật tốn hiệu nhất đối với bài tốn phân lớp dữ liệu tiếng Việt. Đồng thời, thử nghiệm trên nhiều bộ dữ liệu tiếng Việt khác nhau. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 46 -  TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt [1]. 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”, Khĩa luận tốt nghiệp đại học, Đại học Cơng nghệ, ĐHQGHN, 2006. [2]. Nguyễn Minh Tuấn, “Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa Tiếng Việt trong lĩnh vực y tế ”, Khĩa luận tốt nghiệp đại học, Đại học Cơng Nghệ, ĐHQGHN, 2008. Tài liệu Tiếng Anh [3]. Aixin Sun, 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]. Decision Tree, Analysis mindtools.com [5]. T.M.Michell, Machine Learning, Mc Graw Hill [6]. Nghiệp vụ ngân hàng. TS. Nguyễn Minh Kiều. Trường Đại Học Kinh Tế TPHCM. Nhà xuất bản Thống Kê, tháng 12-2005. [7]. David J.C. MacKay. Information Theory, Inference, and Learning Algorthms Cambridge: Cambridge University Press, 2003. ISBN 0521642981 [8]. “Text Classification from Labeled and Unlabeled Documents using EM”. Machine Learning. Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. [9]. “An Extensive Empirical Study of Feature Selection Metrics for Text Classification”. George Forman, Intelligent Enterprise Technology Laboratory. HP Laboratories Palo Alto, HPL-2002-147 (R.1), November 20th , 2002*. [10]. K. Nigam, J. Lafferty, and A. McCallum, "Using maximunm Entropy for text classification", Proceeding of the 16th International Joint Conference Workshop on Machine Learning for Information Filtering: 61-67 Stockholm, Sweden, 1999. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 47 -  [11]. “Support Vector Machine Active Learning with Applications to Text Classification”. Simon Tong and Daphne Koller. [12]. Lewis, D. and W.Gale: 1994, “A Sequential Algorithm for Training Text Classifiers”. In: Proceedings of the Seventeenth Annual International ACM- SIGIR Conference on Research and Development in Information Retrieval.pp. 3-12, Springer-Verlag. [13]. Soumen Chakrabarti. Mining the web- discovering knowledge from Hypertext Data Morgan Kaufman Publishers, trang 183-188. [14]. 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. [15]. Nguyen Viet Cuong, Nguyen Thi Thuy Linh Ha, Quang Thuy and Phan Xuan Hieu (2006). A Maximum Entropy Model for Text Classification. The International Conference on Internet Information Retrieval 2006:134- 139, Hankuk Aviation University, December 6, 2006, Goyang-si, Korea. [16]. Sebastiani, F.:2001, “Machine Learning in Automated Text Categorisation”. Technical Report IEI-B4-31-1999, Istituto di Elaborazione dell’Informazione. [17]. 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. [18]. The Kluwer international Series in Engineering and Computer Science. “Data mining in finance”. Advances in Relational and Hybrid Methods. Boris Kovalerchuk, Central Washington University, USA and EvgenII Vityaev, Instutue of Mathematics Russian Academy of Sciences, Russia. [19]. “Classification of Text Documents”. Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, USA. [20]. “Flexible Text Classification for Financia, ApplicationL The Facile Systeml”, Fabio Ciravegna and Luca Gilardoni and Alberto Lavelli. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 48 -  [21]. “The Effect of Financial Statement Classification of Hybrid Financial Instrucments on Financial Analysts’s Stock Price Judgments”. Patrick E.Hopkis. [22]. Li, X. & Roth, D. “Learning Question Classifiers”, Proceedings of the 19th International Conference on Computational Linguistics (COLING):556– 562, 2002. [23]. Phan, X.H, “JTextPro: A Java-based Text Processing Toolkit”, [24]. Thorsten Joachims, SVM multiclass Multi-Class Support Vector Machine, Cornell University Department of Computer Science. [25]. Kadri Hacioglu and Wayne Ward. "Question Classification with Support Vector Machines and Error Correcting Codes". Proceedings of HLT- NAACL2003:28-30, Edmonton, Alberta, Canada, May 2003. ĐH Cơng Nghệ - ĐH QGHN CNTT                         ‐ 49 -  DANH SÁCH CÁC TỪ DỪNG Danh sách các từ dùng được sử dụng trong thực nghiệm: Nhận, rằng, cao, nhà, quá, riêng, gì, muốn, rồi, số, thấy, hay, lên, lần, nào, qua, bằng, điều, biết, lớn, khác, vừa, nếu, thời gian, họ, từng, đây, tháng, trước, chính, cả, việc, chưa, do, nĩi, ra, nên, đều, đi, tới, tơi, cĩ thể, cùng, vì, làm, lại, mới, ngày, đĩ, vẫn, mình, chỉ, thì, đang, cịn, bị, mà, năm, nhất, hơn, sau, ơng, rất, anh, phải, như, trên, tại, theo, khi, nhưng, vào, đến, nhiều, người, từ, sẽ, ở, cũng, khơng, về, để, này, những một, các, cho, được, với, cĩ, trong, đã, là, và, của, ảnh. Ngồi ra thì một số literal khơng cĩ ý nghĩa trong văn bản khi tiến hành phân lớp cũng được loại bỏ: {, }, “, “, (, ), /, \, :, -, _, ., ?, ,.