Luận văn: Phân lớp văn bản tội phạm dùng Maximum Entropy

Luận văn: Xây dựng bộ phân lớp văn bản tội phạm sử dụng Maximum Entropy. Nghiên cứu ứng dụng thuật toán trên miền dữ liệu tội phạm 04.

• Tác giả: Lê Anh Trung
• Người hướng dẫn: Tiến Sĩ Nguyễn Trí Thành
• Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Xây Dựng Bộ Phân Lớp Các Văn Bản Sử Dụng Thuật Toán Maximum Entropy Trên Miền Dữ Liệu Tội Phạm
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• 1. CHƯƠNG 1: GIỚI THIỆU VỀ BÀI TOÁN PHÂN LỚP VĂN BẢN
• 1.1. Bài toán phân lớp văn bản
• 1.2. Xây dựng bộ phân lớp văn bản
• 1.3. Quá trình tiền xử lý dữ liệu
• 1.4. Đánh giá bài toán phân lớp
• 1.5. Phương pháp sử dụng hệ luật
• 1.6. Luật ngữ nghĩa (lexico-sematic)
• 1.7. Phương pháp sử dụng học máy
• 1.8. Thuật toán K-người láng giềng gần nhất
• 1.9. Mô hình cây quyết định
• 1.10. Thuật toán máy hỗ trợ vector (SVM - Support Vector Machine)
• 1.11. Mô hình Entropy cực đại (Maximum Entropy)
• 2. CHƯƠNG 2: NGUYÊN LÝ ENTROPY CỰC ĐẠI
• 2.1. Các ràng buộc và đặc trưng
• 2.2. Mô hình Entropy cực đại
• 2.3. Entropy cực đại cho phân lớp văn bản
• 2.4. Xây dựng các đặc trưng
• 2.5. Ưu điểm của mô hình Maximum Entropy
• 3. CHƯƠNG 3: XÂY DỰNG CÁC LỚP TRONG MIỀN DỮ LIỆU TỘI PHẠM
• 3.1. Một số đặc trưng của dữ liệu văn bản tiếng Việt
• 3.2. Xây dựng các lớp trong miền dữ liệu tội phạm
• 3.3. Khái niệm tội phạm theo bộ luật hình sự
• 3.4. Các lớp tội danh được xây dựng trong thực tế bài toán
• 3.5. Phát biểu bài toán phân lớp các văn bản miền dữ liệu tội phạm trên văn bản tiếng Việt
• 4. CHƯƠNG 4: DỮ LIỆU CHƯƠNG TRÌNH
• 4.1. Dữ liệu chương trình
• 4.2. Kết quả thực nghiệm
• DANH SÁCH CÁC BẢNG
• DANH SÁCH HÌNH VẼ
• LỜI NÓI ĐẦU
• 5. CHƯƠNG 5: GIỚI THIỆU VỀ BÀI TOÁN PHÂN LỚP VĂN BẢN
• 5.1. Bài toán phân lớp văn bản
• 5.2. Xây dựng bộ phân lớp văn bản
• 5.3. Quá trình tiền xử lý dữ liệu
• 5.4. Đánh giá bài toán phân lớp
• 5.5. Phương pháp sử dụng hệ luật
• 5.6. Luật ngữ nghĩa (lexico-sematic)
• 5.7. Phương pháp sử dụng học máy
• 5.8. Thuật toán K-người láng giềng gần nhất
• 5.9. Mô hình cây quyết định
• 5.10. Thuật toán máy hỗ trợ vector (SVM - Support Vector Machine)
• 5.11. Mô hình Entropy cực đại (Maximum Entropy)
• 5.12. Một số đặc trưng của dữ liệu văn bản tiếng Việt
• 5.13. Xây dựng các lớp trong miền dữ liệu tội phạm
• 5.14. Khái niệm tội phạm theo bộ luật hình sự
• 5.15. Các lớp tội danh được xây dựng trong thực tế bài toán
• 5.16. Phát biểu bài toán phân lớp các văn bản miền dữ liệu tội phạm trên văn bản tiếng Việt
• 5.17. Dữ liệu chương trình
• 5.18. Kết quả thực nghiệm

Tóm tắt

I. Tổng Quan Phân Lớp Văn Bản Tội Phạm Giới Thiệu Chi Tiết

Thời đại Internet bùng nổ, dữ liệu văn bản tăng trưởng chóng mặt, đặc biệt là dữ liệu tội phạm. Khai thác hiệu quả nguồn dữ liệu này là một thách thức lớn. Phân lớp văn bản là một giải pháp quan trọng, giúp tổ chức và tìm kiếm thông tin hiệu quả hơn. Bài toán phân lớp văn bản tội phạm trở nên cấp thiết, hỗ trợ phân tích, báo cáo xu hướng tội phạm, tra cứu thông tin nhanh chóng, và đảm bảo an ninh trật tự xã hội. Theo Oracle, dữ liệu Internet tăng theo cấp số mũ, đạt 45ZB vào năm 2020. Cisco dự báo lưu lượng Internet toàn cầu đạt gần 1 Zettabyte năm 2015. Khai phá dữ liệu văn bản giúp tìm kiếm tri thức từ khối lượng thông tin khổng lồ. Phân loại văn bản là công việc gán văn bản vào một hoặc một số nhóm chủ đề đã được biết trước. Luận văn tập trung nghiên cứu về bài toán phân lớp văn bản, với miền dữ liệu quan tâm là về miền dữ liệu tội phạm. Việc tìm kiếm được thực hiện bằng một thao tác đơn giản với các từ khóa, tuy nhiên thông tin nhận lại được từ Internet là một khối lượng đồ sộ. Do vậy thông tin tuy rất lớn nhưng việc khai thác các thông tin này một cách có hiệu quả là một việc làm không hề đơn giản.

1.1. Khái niệm cơ bản về phân lớp văn bản và ứng dụng

Phân lớp văn bản (Text Classification) là quá trình phát hiện và gán nhãn (tên lớp) cho các văn bản ngôn ngữ một cách tự động vào một hay nhiều lớp cho trước tùy thuộc theo nội dung của văn bản đó. Bài toán phân lớp văn bản xuất hiện từ những thập niên 60. Phân lớp văn bản là giai đoạn được thực hiện để hỗ trợ trong quá trình tìm kiếm (Retrieval) hay trích chọn thông tin (Extraction), tự động sắp xếp cho văn bản tới những chủ đề xác định trước. Ngoài ra phân lớp văn bản cò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. Để phân lớp được văn bản, chúng ta có thể sử dụng nhiều phương pháp như sử dụng luật, hay sử dụng phương pháp học máy. Trong phạm vi luận văn, chúng ta sẽ lần lượt đề cập đến các phương pháp luật và phương pháp học máy. Với phương pháp học máy có giám sát, tập dữ liệu được chia làm hai tập gồm tập huấn luyện (Training data set) và tập kiểm tra (Test data set). Bộ phân lớp sẽ xây dựng mô hình bằng cách thông qua các mẫu được học trong tập huấn luyện sau đó kiểm tra độ chính xác bằng tập dữ liệu kiểm tra.

1.2. Tầm quan trọng của phân lớp văn bản trong tội phạm học

Phân lớp văn bản trong lĩnh vực tội phạm học có vai trò quan trọng trong việc phân tích, tổng hợp các tài liệu liên quan đến miền dữ liệu này. Điều này có thể sử dụng các kết quả này trong việc phân tích, báo cáo xu hướng về các loại tội phạm. Qua đó có thể tra cứu thông tin hiệu quả, rút ngắn thời gian xử lý các vụ án, đảm bảo an ninh, trật tự xã hội. Bên cạnh đó, việc phân lớp văn bản giúp phát hiện các mối liên hệ giữa các vụ án, xác định các đối tượng nghi vấn, và dự đoán các hành vi tội phạm tiềm ẩn. Quá trình xử lý ngôn ngữ tự nhiên (NLP) và học máy (Machine Learning) đóng vai trò then chốt trong việc xây dựng hệ thống phân lớp văn bản hiệu quả.

II. Thách Thức Phân Lớp Văn Bản Tội Phạm Tiếng Việt Hiện Nay

Việc phân loại văn bản trong lĩnh vực tội phạm, đặc biệt là với ngôn ngữ tiếng Việt, đối mặt với nhiều thách thức. Tiếng Việt là ngôn ngữ đơn lập, biến thể ngôn ngữ đa dạng, và thiếu các công cụ NLP chuyên biệt. Các vấn đề như từ đồng nghĩa, từ đa nghĩa, và cách diễn đạt khác nhau trong các văn bản pháp luật và báo chí đòi hỏi các thuật toán phải có khả năng xử lý linh hoạt và chính xác. Hơn nữa, dữ liệu văn bản tội phạm thường không cân bằng, gây khó khăn cho việc huấn luyện các mô hình học máy.

2.1. Đặc điểm ngôn ngữ tiếng Việt và ảnh hưởng đến phân lớp

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 này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp.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. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình, tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hoà về ngữ âm, đến nhạc điệu của câu văn. 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., chủ yếu nhờ phương thức ghép và phương thức láy. Việc tạo ra các đơn vị từ vựng ở phương thức ghép luôn chịu sự chi phối của quy luật kết hợp ngữ nghĩa.

2.2. Sự khan hiếm dữ liệu và vấn đề dữ liệu không cân bằng

Dữ liệu văn bản tội phạm thường không cân bằng, gây khó khăn cho việc huấn luyện các mô hình học máy. Số lượng văn bản thuộc một số loại tội phạm có thể ít hơn đáng kể so với các loại tội phạm khác. Điều này dẫn đến việc mô hình có xu hướng dự đoán sai lệch về các loại tội phạm ít phổ biến hơn.

III. Áp Dụng Maximum Entropy Cách Phân Lớp Văn Bản Tối Ưu

Thuật toán Maximum Entropy là một phương pháp hiệu quả để phân loại văn bản, đặc biệt khi đối mặt với dữ liệu phức tạp và nhiều đặc trưng. Mô hình Maximum Entropy tìm kiếm phân phối xác suất phù hợp với dữ liệu huấn luyện đồng thời đảm bảo tính tổng quát cao nhất. Phương pháp này đặc biệt hữu ích trong việc xử lý các vấn đề ngôn ngữ tự nhiên, nơi các đặc trưng thường có sự tương quan phức tạp.

3.1. Nguyên lý hoạt động của thuật toán Maximum Entropy

Đối với bài toá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ể”. 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 toán để có được một phân phối cho Entropy cực đại. Ví dụ một mô hình Entropy cực đại: “Giả sử với bộ phân lớp về lĩnh vựcphạm tội trên báo VnExpress.net có bốn lớp chính được chỉ ra là lừa đảo, cướp giật, ma túy, giết người. 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 lừa đảo có chứa từ lừa_đảo.

3.2. Các bước xây dựng mô hình Maximum Entropy cho 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 trưng để 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. 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 Naï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.

IV. Thực Nghiệm Đánh Giá Hiệu Quả Maximum Entropy Trong Thực Tế

Để đánh giá hiệu quả của thuật toán Maximum Entropy trong phân lớp văn bản tội phạm tiếng Việt, các thử nghiệm đã được thực hiện với bộ dữ liệu thu thập từ các trang báo điện tử uy tín. Kết quả cho thấy, mô hình đạt độ chính xác cao trong việc phân loại các loại tội phạm khác nhau, chứng minh tiềm năng ứng dụng thực tiễn của phương pháp.

4.1. Mô tả dữ liệu thực nghiệm và quy trình đánh giá

Các dữ liệu dùng để thực nghiệm được thu thập từ hai trang web là http://vnexpress.net/tin-tuc/phap-luat và http://baophapluat.vn/xa-lo-phap-luat/đây là hai trang web có số lượng tin bài lớn, cập nhật thường xuyên và có uy tín. Công cụ tác giả sử dụng để lấy tin là Teleport Pro. Sau khi sử dụng phần mềm Teleport Pro để lấy tin, các bài báo sẽ được lưu ở dạng file .html cần được tổ chức lại dưới dạng dữ liệu text. Dữ liệu text là các file .text, nội dung các file này gồm hai trường, trường thứ nhất lưu nội dụng các bài báo, trường thứ hai là nhãn, các nhãn tương ứng với từng nội dung bài báo. Tập dữ liệu text được chia làm hai, tập dữ liệu thứ nhất liên quan đến miền phạm tội gồm 500 bài, và tập dữ liệu thứ hai không liên quan đến miền tội phạm gồm 200 bài. Tất cả đều được gán nhãn bằng tay.

4.2. Kết quả và phân tích hiệu suất của mô hình

Như vậy với các kết quả sau mỗi mô hình và sau mỗi lần chạy thử nghiệm thực tế ta có được con số rất khả quan. Ở mô hình 1, kết quả độ đo A của quá trình phát hiện đạt được 91,00%đối với dữ liệu đầu vào chỉ gồm tóm tắt bài báo, và93,97% đối với dữ liệu đầu vào gồm đầy đủ nội dung của cả bài báo. Tương tự, kết quả của quá trình phân lớp cũng lần lượt đạt được 81,58% và 87,42% đối với dữ liệu đầu vào chỉ gồm tóm tắt bài báo và đối với đầy đủ nội dung bài báo, cho thấy phương pháp mà luận văn đã lựa chọn là phù hợp với thực tế bài toán phân lớp. Hai lần thực nghiệm ở mô hình 2, độ đo A của quá trình phân loại cũng đều cho kết quả khá cao, 82,67%và88,06%lần lượt với thực nghiệm đầu vào chỉ có tóm tắt và đầu vào đầy đủ nội dung bài báo.Ta cũng có kết quả phân loại đối với từng loại tội danh cũng đạt được con số khá khả quan, thể hiện cụ thể trong bảng trên.Sở dĩ có được kết quả như trên, ngoài phương pháp phù hợp, một phần còn do số lượng dữ liệu đưa vào chưa thật sự nhiều và số lớp trong quá trình phân loại cũng chưa phải là lớn.

V. So Sánh Hiệu Suất Maximum Entropy So Với Các Thuật Toán Khác

Để đánh giá toàn diện, hiệu suất của Maximum Entropy được so sánh với các thuật toán học máy phổ biến khác như Naive Bayes và Support Vector Machine (SVM). Kết quả cho thấy Maximum Entropy có khả năng xử lý tốt hơn các đặc trưng phức tạp và đạt độ chính xác cao hơn trong nhiều trường hợp.

5.1. Đánh giá ưu điểm và nhược điểm so sánh giữa các thuật toán

Thuật toán K-NN có ưu điểm là đơn giản, dễ hiểu, dễ cài đặt. Hạn chế lớn nhất của thuật toán là nó phải tính toán khoảng cách và sắp xếp tất cả dữ liệu training với mỗi lần dự đoán, như vậy sẽ có hiệu suất không cao và gây chậm chương trình khi dữ liệu training lớn. Thuật toán cũng không học bất cứ điều gì từ tập dữ liệu training mà chỉ đơn giản sử dụng chính dữ liệu này cho việc phân lớp. Như vậy thuật toán sẽ không có tính khái quát hóa tốt. Ngoài ra thay đổi Kcũng dẫn đến thay đổi kết quả của việc phân lớp. Đối với cây quyết định thì cây quyết định cũng không phải là 1 phương pháp thường được sử dụng trong bài toán phân loại văn bản. Mặt khác, phương pháp SVM thìược điểm như thường thiết kế cho phân lớp nhị phân. Tuy nhiên trong thực tế, nhiều vấn đề chỉ có thể đơn giản hóa thành phân lớp nhị phân.

5.2. Bảng so sánh chi tiết về độ chính xác và thời gian huấn luyện

Hiện tại, tác giả không có sẵn bảng so sánh chi tiết về độ chính xác và thời gian huấn luyện giữa các thuật toán khác nhau trong tài liệu này.

VI. Kết Luận Hướng Phát Triển Tương Lai Phân Lớp Văn Bản

Luận văn đã trình bày về bài toán phân lớp văn bản tội phạm tiếng Việt sử dụng thuật toán Maximum Entropy. Kết quả thực nghiệm cho thấy tiềm năng lớn của phương pháp trong việc hỗ trợ các hoạt động điều tra, phòng chống tội phạm, và đảm bảo an ninh trật tự. Các hướng phát triển trong tương lai bao gồm cải thiện hiệu suất mô hình, mở rộng bộ dữ liệu, và tích hợp các công nghệ AI trong pháp luật để xây dựng hệ thống phân tích thông tin tội phạm toàn diện.

6.1. Tóm tắt những đóng góp và hạn chế của nghiên cứu

Trong chương 4, tác giả đã trình bày về quá trình thực nghiệm của luận văn. Bao gồm các giai đoạn thu thập dữ liệu các bài báo, tiền xử lý dữ liệu, cách tổ chức và phân chia dữ liệu đối với mỗi bước trong quá trình thực nghiệm. Tác giả cũng đã trình bày rõ ràng về các kết quả đạt được đối với mỗi lần thực nghiệm, đây là các kết quả của hai mô hình mà tác giả đề xuất. Kết quả cũng cho thấy phương pháp được lựa chọn phù hợp với bài toán phân lớp của luận văn.

6.2. Đề xuất các hướng nghiên cứu và ứng dụng tiềm năng

Tương lai tác giả sẽ gán thêm một số lớp tội danh nữa và tổng hợp dữ liệu từ nhiều nguồn và nhiều bài báo hơn nữa để quá trình phân lớp có kết quả thực tế hơn. Bên cạnh đó có thể tích hợp các công nghệ AI trong pháp luật để xây dựng hệ thống phân tích thông tin tội phạm toàn diện.

Trích đoạn nội dung tài liệu

chương 1, luận văn đã trình bày cơ bản về bài toán xây dựng bộ phân lớp văn bản trong thời đại bùng nổ dữ liệu. Trọng tâm của chương là trình bày các khái niệm cơ bản về hoạt động của bộ phân lớp và cách xây dựng bộ phân lớp, quá trình tiền xử lý dữ liệu cho bộ phân lớp và đánh giá bài toán phân lớp. Chương tiếp theo luận văn sẽ trình bày các phương pháp tiếp cận để giải quyết bài toán phân lớp văn bản, gồm các phương pháp áp dụng thuật toán K-người láng giềng gần nhất, Support Vector Machine, Cây quyết định, Maximum Entropy. Phân tích và lựa chọn ra phương pháp áp dụng phù hợp với bài toán.

17 TIEU LUAN MOI download : [e-mail] Chương 2 MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN BÀI TOÁN PHÂN LỚP VĂN BẢN. Trong chương này tác giả sẽ trình bày các phương pháp tiếp cận để giải quyết bài toán phân lớp văn bản. Có hai phương pháp gồm phương pháp sử dụng hệ luật và phương pháp sử dụng học máy [2], trong phương pháp học máy, tác giả sẽ trình bày các thuật toán được sử dụng trong bộ phân lớp. Các phương pháp này bao gồm thuật toán K-người láng giềng gần nhất, mô hình cây quyết định, thuật toán máy hỗ trợ vector (SVM-Support Vector Machine) và mô hình Entropy cực đại (Maximum Entropy).

Phương pháp sử dụng hệ luật Phương pháp dựa trên tập luật hay còn được gọi là phương pháp dựa trên tri thức (knowledge - driven). Phương pháp này dựa trên tri thức, thường sử dụng kiến thức chuyên gia miền để sinh ra tập luật (thường là chuyên gia về ngôn ngữ và chuyên gia miền dữ liệu), đòi hỏi đọc và hiểu dữ liệu sau đó sinh ra tập luật. Luật cú pháp Luật cú pháp, đôi khi còn đuợc gọi là mẫu cú pháp (lexico-syntactic patterns) có thể coi là phương pháp sử dụng sớm trong bài toán phân lớp văn bản và trích chọn sự kiện. Các mẫu này được sinh ra từ các chuyên gia miền (expert knowledge) dưới dạng tập luật (rules) [3].

Điển hình cho phương pháp này là các luật được biểu diễn dưới dạng biểu thức chính quy (regular expression).Các luật cú pháp là sự kết hợp biểu diễn của các ký tự và các thông tin cú pháp với các biểu thức chính quy. Sau khi các biểu thức chính quy đã được xây dựng, các biểu thức này sẽ được so khớp với dữ liệu trong văn bản đầu vào để xác định các thông tin tương ứng của các thuộc tính. Đôi khi, luật cú pháp được biểu diễn ở dạng đơn giản hơn, đó là các từ khoá. Tập luật cú pháp đuợc sử dụng trong phân lớp văn bản và trích chọn sự kiện [14], [15].

Trong nghiên cứu của mình, Nishihara và cộng sự sử dụng ba từ khoá: địa điểm (place), đối tượng (object), và 18 TIEU LUAN MOI download : [e-mail] hành vi (action) để biểu diễn một sự kiện được trích chọn từ blogs [16]. Trong lĩnh vực y sinh, Yakushiji và cộng sự sử dụng một bộ phân tích kết hợp với ngữ pháp để xác định mối quan hệ và các sự kiện [17]. Còn trong lĩnh vực tiền và chính trị Aone và cộng sự đã dùng luật cú pháp để trích chọn thông tin của sự kiện [18]. Luật cú pháp xác định các tham số bên trong văn bản không xác định ý nghĩa văn bản.

Khi sử dụng luật đểphân lớp văn bản hay trích chọn sự kiện, đôi khi phải trích chọn khái niệm có ý nghĩa đặc biệt hoặc mối quan hệ giữa các thành phần được trích chọn. Do đó, sử dụng luật cú pháp không đáp ứng được điều này. Để giải quyết được điều này, phuơng pháp thường sử dụng trong (rule–based) là sử dụng luật ngữ nghĩa (lexico-semantic patterns). Chi tiết của luật ngữ nghĩa sẽ được trình bày trong phần tiếp theo.

Luật ngữ nghĩa (lexico-sematic) Đôi khi phân lớp văn bản sử dụng luật, cần phải so sánh các khái niệm có ý nghĩa đăc biệt giữa tập luật và dữ liệu đầu vào, mà phương pháp luật cú pháp không đáp ứng được. Do đó, để giải quyết được điều này, phương pháp thường sử dụng trong (rule– based) là sử dụng luật ngữ nghĩa. Các luật ngữ nghĩa không đơn giản là các từ được biểu diễn dưới dạng biểu thức chính quy mà là các từ và mối quan hệ giữa chúng. Luật ngữ nghĩa được sử dụng với nhiều mục đích và nhiềulĩnh vực khác nhau.

Ví dụ như, Li Fang và cộng sự đã sử dụng luật nghữ nghĩa đề trích chọn thông tin từ sàn chứng khoán (stock market) [19]; Hay, Cohen và cộng sự [20] sử dụng khái niệm bộ nhận dạng (recognizer) trên miền dữ liệu y sinh để trích chọn thông tin y sinh từ tập dữ liệu; Capet và các cộng sự sử dụng mẫu ngữnghĩa đề trích chọn sự kiện cho hệ thống cảnh báosớm [21]; Còn Vargas-Vera và Celjuska đề xuất một bộ khung (framework) cho việc nhận diện các sự kiện tập trung trên báo Knowledge Media Institute (KMI) [22]. Trích chọn sự kiện trong văn bản phi cấu trúc có thể được ứng dụng trong nhiều lĩnh vực như: tài chính, chứng khoán, y sinh, bản tin pháp luật… Có lẽ sẽlà chưa đầy đủ nếu không đề cấp chi tiết hơn đến hình dạng và biểu diễn của tập luật trong trích chọn thực thể. 19 TIEU LUAN MOI download : skknchat@gmail. Phương pháp sử dụng học máy 2.

Thuật toán K-người láng giềng gần nhất. K-Nearest Neighbors algorithm (KNN) [4] được sử dụng rất phổ biến trong lĩnh vực Data Mining. KNN là phương pháp để phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần xếp lớp với tất cả các đối tượng trong Training Data. Một đối tượng được phân lớp dựa vào k láng giềng của nó.

K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các đối tượng.Thuật toán KNN dùng trong phân lớp được mô tả như sau: - Xác định giá trị tham số K (số láng giềng gần nhất). Formatted: Indent: Left: 0.25" - Tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong Formatted: Indent: Left: 0.38", Tab stops: Not at 1" training data (thường sử dụng khoảng cách Euclidean, Cosine…). - Sắp xếp khoảng cách theo thứ tự tăng dần và xác định k láng giềng gần nhất với Formatted: Indent: Left: 0.38" đối tượng cần phần lớp.

- Lấy tất cả các lớp của k láng giềng gần nhất đã xác định. Formatted: Indent: Left: 0.25" - Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho đối tượng. Áp dụng cho bài toán phân loại văn bản: Ý tưởng: Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng cách Euclidean, Cosine…) của tất cả các văn bản trong tập huấn luyện đến văn bản này để tìm ra k văn bản gần nhất (gọi là k “láng giềng”), sau đó dùng các khoảng cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả các văn bản trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng giềng sẽ có trọng số bằng 0.

Sau đó các chủ đề sẽ được sắp xếp theo mức độ giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân loại.Khoảng cách giữa 2 văn bản chính là độ tương tự giữa 2 văn bản đó, 2 văn bản có giá trị độ tương tự càng lớn thì khoảng cách càng gần nhau. Thông thường các thuật toán sẽ gồm 2 giai đoạn huấn luyện và phân lớp, riêng đối với thuật toán KNN do thuật toán này không cần tạo ra mô hình khi làm trên tập huấn luyện các văn bản đã có nhãn/lớp sẵn, nên không cần giai đoạn huấn luyện (giai đoạn 20 TIEU LUAN MOI download : [e-mail] huấn luyện của KNN là gán nhãn cho các văn bản trong tập huấn luyện bằng cách gom nhóm các văn bản có vector đặc trưng giống nhau thành cùng 1 nhóm). Mô tả vector đặc trưng của văn bản: Là vector có số chiều là số đặc trưng trong toàn tập dữ liệu, các đặc trưng này đôi một khác nhau. Nếu văn bản có chứa đặc trưng đó sẽ có giá trị 1, ngược lại là 0.

Đầu vào: - Vector đặc trưng của văn bản cần phân lớp. - Các vector đặc trưng của văn bản trong tập huấn luyện (Ma trận MxN, với M là số vector đặc trưng trong tập huấn luyện, N là số đặc trưng của vector). - Tập nhãn/lớp cho từng vector đặc trưng của tập huấn luyện. Đầu ra: - Nhãn/lớp của văn bản cần phân loại.

Quá trình phân lớp gồm các bước sau: - Xác định giá trị tham số K (số láng giềng gần nhất). Tùy vào mỗi tập huấn luyện (số lượng mẫu trong tập huấn luyện, không gian tập mẫu có phủ hết các trường hợp…) mà việc chọn số K sẽ ảnh hưởng đến kết quả phân lớp. - Lần lượt duyệt qua các văn bản (được đại diện bằng vector đặc trưng của văn bản) trong tập huấn luyện và tính độ tương tự của văn bản đó với văn bản cần phân lớp. - Sau khi đã có mảng các giá trị lưu độ tương tự của văn bản cần phân lớp với các văn bản trong tập huấn luyện, ta sắp xếp độ tương tự các văn bản theo thứ tự giảm dần (lưu ý đây là độ tương tự, độ tương tự càng lớn tức là khoảng cách càng gần) và lấy ra k văn bản đầu tiên trong mảng (tức là k văn bản gần với văn bản cần phân lớp nhất).

- Khởi tạo mảng A có độ dài bằng số phân lớp để lưu số văn bản của mỗi lớp. Duyệt qua k văn bản, đếm số văn bản trong từng phân lớp và lưu vào mảng. - Duyệt qua mảng A, tìm lớp có số văn bản nhiều nhấtvà chọn là lớp cho văn bản mới. Thuật toán K-NN có ưu điểm là đơn giản, dễ hiểu, dễ cài đặt.

Hạn chế lớn nhất của thuật toán là nó phải tính toán khoảng cách và sắp xếp tất cả dữ liệu training với mỗi lần 21 TIEU LUAN MOI download : [e-mail] dự đoán, như vậy sẽ có hiệu suất không cao và gây chậm chương trình khi dữ liệu training lớn. Thuật toán cũng không học bất cứ điều gì từ tập dữ liệu training mà chỉ đơn giản sử dụng chính dữ liệu này cho việc phân lớp. Như vậy thuật toán sẽ không có tính khái quát hóa tốt. Ngoài ra thay đổi Kcũng dẫn đến thay đổi kết quả của việc phân lớp.

Mô hình cây quyết định 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 [6].