intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Đề 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”

Chia sẻ: Nguyen Huu Phuoc | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST
Báo xấu
231
lượt xem 68
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phân lớp văn bản là quá trình gán văn bản một cách tự động vào một hoặc nhiều lớp cho trước. 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 toán này đã và đang trở thành lĩnh vực nhận được nhiều sự quan tâm, nghiên cứu của nhiều...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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”

  1. ĐỀ 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” Giáo viên hướng dẫn : Sinh viên thực hiện : Lê Thị Thùy Dương
  2. ĐH Công Nghệ - ĐH QGHN CNTT 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 Khóa luận tốt nghiệp Lê Thị Thùy Dương
  3. ĐH Công Nghệ - ĐH QGHN CNTT 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 toán này đã và đang trở thành lĩnh vực nhận được nhiều sự quan tâm, nghiên cứu của nhiều nhà khoa học trên thế giới. Khóa luận tốt nghiệp với đề 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” nghiên cứu nội dung, các thuộc tính, các thuật toán giải quyết bài toán phân lớp. 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 toán, Ngoại tệ, Chứng khoá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. Khóa luận tốt nghiệp Lê Thị Thùy Dương
  4. ĐH Công Nghệ - ĐH QGHN CNTT MỤC LỤC LỜI MỞ ĐẦU ................................................................................................................1 Chương 1. BÀI TOÁ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 toá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 toá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 toá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 toá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 TOÁ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 toán phân lớp văn bản tài chính ngân hàng trong Tiếng Việt ...33 Khóa luận tốt nghiệp Lê Thị Thùy Dương
  5. ĐH Công Nghệ - ĐH QGHN CNTT 3.3.1. Phát biểu bài toán: .........................................................................33 3.3.2. Phương pháp phân lớp...................................................................34 3.3.3. Mô hình của bài toá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 Khóa luận tốt nghiệp Lê Thị Thùy Dương
  6. ĐH Công Nghệ - ĐH QGHN CNTT Danh sách hình vẽ và bảng biểu Hình 1. Bài toá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 toá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 Khóa luận tốt nghiệp Lê Thị Thùy Dương
  7. ĐH Công Nghệ - ĐH QGHN CNTT 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 toán phân lớp văn bản là một trong những bài toá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 toá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 toá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 toá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 toá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à              ‐ 1 -            
  8. ĐH Công Nghệ - ĐH QGHN CNTT 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 toá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 toá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 toá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 toá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 toán phân lớp văn bản. Trình bày một số thuật toá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 toá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.              ‐ 2 -            
  9. ĐH Công Nghệ - ĐH QGHN CNTT Chương 1. BÀI TOÁ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 toán cơ bản và quan trọng trong trích chọn thông tin trên Web là bài toán phát hiện các quan hệ của các lớp đối tượng. Để 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 toán đầu tiên cần giải quyết đó là bài toán phân lớp tự động các đối tượng. Tự động phân lớp văn bản là một nhiệm vụ rất quan trọng có thể giúp ích trong việc tổ chức cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn. 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. Lớ p 1 L ớp 2 Thuật toán Dữ liệu vào phân lớp hoạt động L ớp n Hình 1. Bài toá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,              ‐ 3 -            
  10. ĐH Công Nghệ - ĐH QGHN CNTT phân lớp theo chủ đề… Hầu hết các bài toá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 toá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.              ‐ 4 -            
  11. ĐH Công Nghệ - ĐH QGHN CNTT Đị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) ∈ D × C , trong đó D là tập các văn bản và C = {c1 , c 2 ,...cc } 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 toán tìm một hàm Φ : D × C → {T , F } trong đó D là tập các văn bản và C = {c1 , c 2 ,...cc } là tập các lớp cho trước, hàm Φ : D × C → {T , F } được gọi là bộ phân lớp. 1.2. Phân loại bài toá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 toán phân lớp văn bản. Nhìn chung có thể phân biệt bài toán phân lớp theo hai cách sau: - Phân lớp văn bản nhị phân / đa lớp: Bài toán phân lớp văn bản được gọi là nhị phân nếu |C|=2, gọi là đa lớp nếu |C|>2. - Phân lớp văn bản đơn nhãn / đa nhãn: Bài toán phân lớp văn bản được gọi là đơn nhãn nếu mỗi tài liệu được gán vào chính xác một lớp. Bài toán phân lớp văn bản được gọi là đa nhãn nếu một tài liệu có thể được gán nhiều hơn một nhãn. 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 toá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 toá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              ‐ 5 -            
  12. ĐH Công Nghệ - ĐH QGHN CNTT 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 toán phân lớp qua bước học quy nạp. Trong bước học, hệ              ‐ 6 -            
  13. ĐH Công Nghệ - ĐH QGHN CNTT 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 toá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 toá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 toá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 toá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 toán học. Tập dữ liệu huấn luyện là tập hợp các              ‐ 7 -            
  14. ĐH Công Nghệ - ĐH QGHN CNTT 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: Biểu diễn logic Văn bản Mô hình Phân lớp Tiền xử lý Cây phân cấp 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 toán có thể xử lý được (ví dụ, dạng biểu diễn vector của văn bản). - Học các bộ phân lớp: sử dụng các thuật toán phân lớp để xây dựng mô hình từ dữ liệu đã qua tiền xử lý. 1.3.3.1. Phương pháp biểu diễn tài liệu Trong bài toán phân lớp văn bản, cách biểu diễn văn bản đóng vai trò rất lớn. Một tài liệu được biểu diễn dưới dạng một tập hợp các từ, mỗi từ được xem là một thuộc tính 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 toá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 toán bằng nhiều cách khác nhau. Cách đơn giản nhất là gán trọng số bằng một giá trị nhị phân chỉ ra từ 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à              ‐ 8 -            
  15. ĐH Công Nghệ - ĐH QGHN CNTT 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: occ(t k , D j ) freq(t k , D j ) = N 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: freq (t k , D j ) = log(1 + freq (t k , D j )) Hay giá trị của từ khóa ti được tính theo công thức: m wij = log = log(m) − log(df i ) df i 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.              ‐ 9 -            
  16. ĐH Công Nghệ - ĐH QGHN CNTT 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: ⎛m ⎞ TFIDFl ,d = freq l , d * log⎜ ⎟ ⎜ df ⎟ ⎝l ⎠ 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 toàn bộ tập tài liệu m được tính bởi công thức: TFIDF = ∑ TFIDFl ,d TFIDFl ∈ R 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 toán được tính toán mở rộng và có thể đôi khi không thể tính toán được đối với một số thuật toán học. Bên cạnh đó, nhiều thuộc tính không mang thông tin, nhập nhằng hoặc bị nhiễu, do đó có thể dẫn tới bộ phân lớp đạt được kết quả tốt trên dữ liệu học nhưng không tốt trên dữ liệu kiểm tra (overfitting). 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 T ' ⊂ T với |T’|
  17. ĐH Công Nghệ - ĐH QGHN CNTT 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 toá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: Pr( t ∧ c ) I (t , c ) = log Pr (t ) × Pr (c ) Và được ước lượng: A× N I (t , c ) ≈ log (A + C )× (A + B) 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 toán phân lớp. Bắt đầu từ không gian từ khóa ban đầu, một không              ‐ 11 -            
  18. ĐH Công Nghệ - ĐH QGHN CNTT 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 toán phân lớp. Phương pháp này tạo thuận lợi cho thuật toán phân lớp. Tuy nhiên hạn chế của phương pháp này là sự phức tạp trong tính toán. Ngoài việc lựa chọn các thuộc tính mang nhiều thông tin từ tập thuộc tính ban đầu, quá trình lựa chọn thuộc tính có thể tạo ra các thuộc tính mới (ví dụ các khái niệm) để thay thế cho một nhóm các thuộc tính thông qua kỹ thuật phân cụm. Nhóm các từ có sự giống nhau về ngữ nghĩa sẽ được xem là một thuộc tính mới thay thế cho các từ đơn lẻ. Với phương pháp này, cần xác định độ tương tự giữa các từ và áp dụng các kỹ thuật phân cụm như k người láng giềng gần nhất. 1.3.4. Đánh giá 1.3.4.1. Đánh giá cho bài toá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 toá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 C i Thuộc lớp Ci Không thuộc lớp Ci Thuộc lớp Ci TPi TNi Dự đoán Không thuộc lớp Ci FPi FNi Trong đó: - TPi (true positives): số lượng ví dụ dương được thuật toán phân đúng vào lớp Ci. - TNi (true negatives): số lượng ví dụ âm được thuật toán phân đúng vào lớp Ci. - FPi (false positives): số lượng ví dụ dương được thuật toán phân sai vào Ci. - FNi (false negatives): số lượng ví dụ âm được thuật toán phân sai vào Ci.              ‐ 12 -            
  19. ĐH Công Nghệ - ĐH QGHN CNTT Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ được thuật toán phân lớp vào lớp Ci : TPi Pri = TPi + TN i Độ hồi tưởng Re i của lớp C i là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự thuộc lớp Ci : TPi Re i = TPi + FPi Dựa vào độ chính xác và độ hồi tưởng chuẩn của mỗi lớp, độ chính xác và độ hồi tưởng cho toàn bộ các lớp, tức là {C1 , C 2 ,..., C m } 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: m m ∑ TP ∑ TP i i ˆ ˆ Pr µ = Re µ = i =1 i =1 m m ∑ (TPi + TN i ) ∑ (TP + FP ) i i i =1 i =1 - Macroaveraging: m m ∑ Pr ∑ Re i i ˆ ˆ Pr M = Re M = i =1 i =1 m 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.              ‐ 13 -            
  20. ĐH Công Nghệ - ĐH QGHN CNTT - Độ đ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à: (β + 1). Pr . Re 2 Fβ = β . Pr + Re 2 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à Aci và Eri của lớp Ci : TPi + FN i Aci = TPi + FPi + FN i FPi + TN i Eri = = 1 − Aci TPi + TN i + FPi + FN i 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 Ci của nó, nhưng phương pháp A phân vào lớp tương tự với lớp Ci hơn thì phương pháp A được đánh giá là tốt hơn so với phương pháp B. Vì vậy, 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 Ci và C k , kí hiệu là CS (C i , C k ) 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: Ci = {w1t1 , w2 t 2 ,..., wN t N } C k = {v1t1 , v 2 t 2 ,..., v N t N } Độ 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:              ‐ 14 -            
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.26: Bộ 320 Luận Văn Thạc Sĩ Y Học
320 tài liệu
1253 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2