Tài liệu Nghiên cứu phân lớp tự động văn bản báo chí tiếng Việt về tài nguyên và môi trường

1 ®¹i häc quèc gia hµ néi tr-êng ®¹i häc c«ng nghÖ trÇn thÞ lan h-¬ng NGHIÊN CỨU PHÂN LỚP TỰ ĐỘNG VĂN BẢN BÁO CHÍ TIẾNG VIỆT VỀ TÀI NGUYÊN VÀ MÔI TRƯỜNG luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin Hµ néi - 2012 2 ®¹i häc quèc gia hµ néi Tr-êng ®¹i häc c«ng nghÖ trÇn thÞ lan h-¬ng NGHIÊN CỨU PHÂN LỚP TỰ ĐỘNG VĂN BẢN BÁO CHÍ TIẾNG VIỆT VỀ TÀI NGUYÊN VÀ MÔI TRƯỜNG Ngµnh : C«ng nghÖ th«ng tin Chuyªn ngµnh : HÖ thèng th«ng tin M· sè : 60 48 05 luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin Ng-êi h-íng dÉn khoa häc: PGS.TS §ç Trung TuÊn Hµ néi - 2012 3 MỤC LỤC Trang Mục lục Danh mục các bảng Danh mục các hình MỞ ĐẦU Chương 1: 1 KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN VÀ THUẬT 3 TOÁN K LÁNG GIỀNG GẦN NHẤT 1.1. Khai phá dữ liệu văn bản 3 1.2. Khái niệm cơ bản trong khai phá văn bản 3 1.2.1. Một số khái niệm sử dụng trong luận văn 3 1.2.2. Các phương pháp đánh trọng số cho từ khóa 4 1.3. Một số phương pháp biểu diễn văn bản 5 1.3.1. Mô hình Boolean 5 1.3.2. Mô hình không gian vector 6 1.3.3. Mô hình xác suất 7 1.3.4. Mô hình LSI 8 1.4. Phương pháp lựa chọn từ trong biểu diễn văn bản 8 1.4.1. Loại bỏ từ dừng 8 1.4.2. Thu gọn đặc trưng biểu diễn 8 1.5. Độ liên quan giữa các văn bản 13 1.6. Phân lớp văn bản 14 1.7. Thuật toán K láng giềng gần nhất (KNN) 17 1.8. Kết chương 18 Chương 2: BÀI TOÁN PHÂN LỚP TỰ ĐỘNG VĂN BẢN BÁO CHÍ TIẾNG VIỆT VỀ TÀI NGUYÊN VÀ MÔI TRƢỜNG 19 4 2.1. Một số đặc điểm tiếng Việt 19 2.1.1. Âm tiết 19 2.1.2. Từ 19 2.1.3. Câu 20 2.1.4. Các đặc điểm chính tả văn bản tiếng Việt 20 2.2. Phương pháp tách từ tiếng Việt 21 2.2.1. Phương pháp So khớp tối đa 21 2.2.2. Phương pháp Giải thuật học cải biến 22 2.2.3. Phương pháp đối sánh thuật ngữ dài nhất 23 2.3. Một số thông tin chuyên ngành Tài nguyên và môi trường 23 2.3.1. Tài nguyên đất 24 2.3.2. Tài nguyên nước 24 2.3.3. Tài nguyên khoáng sản 26 2.3.4. Tài nguyên biển 27 2.3.5. Khí tượng thủy văn 28 2.3.6. Môi trường 29 2.3.7. Đo đạc và bản đồ 29 2.4. Bài toán phân lớp tự động các văn bản báo chí tiếng Việt về tài nguyên và môi trường 31 2.5. Mô hình tiếp cận bài toán 31 2.5.1. Tiền xử lý văn bản 31 2.5.2. Lựa chọn đặc trưng theo chủ đề văn bản 34 2.5.3. Xử lý tập mẫu 34 2.5.4. Biểu diễn văn bản trong mô hình vector 35 2.5.5. Phép tính độ liên quan giữa hai vector 36 2.5.6. Phân lớp văn bản tiếng việt về tài nguyên và môi trường 36 2.6. Kết chương 36 5 Chương 3: THIẾT KẾ XÂY DỰNG HỆ THỐNG PHÂN LỚP VĂN BẢN 37 3.1. Thiết kế tổng thể 37 3.2. Thiết kế chi tiết 38 3.3. Sơ đồ khung cảnh mức 0 của hệ thống 39 3.4. Sơ đồ khung cảnh mức 1 của chức năng tiền xử lý 41 3.5. Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản mẫu 42 3.6. Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản phân lớp 43 3.7. Chức năng quản lý từ điển, từ dừng 44 3.8. Chức năng quản lý chủ đề 44 3.9. Thiết kế cơ sở dữ liệu 45 3.10. Kết chương 45 Chương 4: CÀI ĐẶT MÔ HÌNH VÀ KIỂM THỬ KẾT QUẢ 46 Cài đặt chương trình 46 4.1. 4.1.1. Lựa chọn công nghệ và môi trường cài đặt 46 4.1.2. Giao diện chương trình phân lớp văn bản báo chí tiếng Việt về tài nguyên và môi trường 46 4.2. Cơ sở dữ liệu 50 4.3. Kết quả 51 4.3.1. Kết quả tách từ 51 4.3.2. Kết quả phân lớp văn bản 53 4.4. Kết chương 58 KẾT LUẬN VÀ ĐỊNH HƢỚNG PHÁT TRIỂN 59 DANH MỤC TÀI LIỆU THAM KHẢO 61 PHỤ LỤC 63 6 DANH MỤC CÁC BẢNG Trang Bảng 1.1. Các đại lượng TPc, TNc, FNc, FPc 16 Bảng 3.1. Bảng thiết kế cơ sở dữ liệu 34 Bảng 4.1. Thông tin mô tả một số thông số của tập dữ liệu huấn luyện 50 Bảng 4.2. Trích kết quả kiểm thử phân lớp văn bản báo chí tiếng 54 Việt về tài nguyên môi trường 7 DANH MỤC CÁC HÌNH Trang Hình 1.1. Biểu diễn văn bản v1 và v2 trong không gian véc tơ ba chiều T1, T2, T3, trong đó Ti là các từ khóa 6 Hình 1.2. Biểu diễn văn bản theo túi - các - từ 7 Hình 1.3. Lược đồ thống kê tần số của từ theo định luật Zipf 10 Hình 1.4. Thuật toán lựa chọn đặc trưng cơ bản cho việc lựa chọn k đặc trưng tốt nhất 11 Hình 1.5. Mô tả bài toán phân lớp 14 Hình 1.6. Lược đồ chung quá trình xây dựng bộ phân lớp văn bản 15 Hình 2.1. Khai thác khoáng sản ở Thái Nguyên 26 Hình 2.2. Khai thác cát vô tội vạ làm diện tích đất ven các sông sạt lở 27 Hình 2.3. Mô hình tiếp cận bài toán phân lớp tự độngvăn bản tiếng Việt về tài nguyên và môi trường 32 Hình 2.4. Sơ đồ thuật toán tách từ 33 Hình 2.5. Mô hình xử lý tập mẫu 35 Hình 3.1. Sơ đồ phân rã chức năng chính của hệ thống phân lớp văn bản 37 Hình 3.2. Sơ đồ phân rã chức năng mức chi tiết của hệ thống phân lớp văn bản 38 Hình 3.3. Sơ đồ khung cảnh mức 0 39 Hình 3.4. Sơ đồ khung cảnh mức 1 chức năng tiền xử lý 41 Hình 3.5. Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản mẫu 42 Hình 3.6. Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản phân lớp 43 Hình 3.7.a. Quản lý từ điển từ dừng 44 Hình 3.7.b. Quản lý từ điển từ dừng 44 Hình 3.8. Quản lý chủ đề 44 Hình 4.1. Kết quả sau khi lọc nhiễu và tách từ dựa vào từ điển 52 Hình 4.2. Kết quả tách từ được thống kê theo tần số xuất hiện và 52 8 loại bỏ từ dừng 9 MỞ ĐẦU Phân lớp văn bản là bài toán cơ bản trong khai phá dữ liệu văn bản. Bài toán phân lớp văn bản là việc gán tên các chủ đề (tên lớp/nhãn lớp) đã được xác định trước, vào các văn bản dựa trên nội dung của chú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, chiết lọc thông tin, 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 lớp văn bản có thể thực hiện thủ công hoặc tự động sử dụng các kỹ thuật học máy có giám sát. Các hệ thống phân lớp có thể ứng dụng trong việc phân loại tài liệu của các thư viện điện tử, phân loại văn bản báo chí trên các trang tin điện tử,… những hệ thống tốt, cho ra kết quả khả quan, giúp ích nhiều cho con người. Đề tài "Nghiên cứu phân lớp tự động văn bản báo chí tiếng Việt về tài nguyên và môi trường", học viên vận dụng những kiến thức về kỹ thuật khai phá văn bản, kỹ thuật phân lớp văn bản nói riêng, và kiến thức về công nghệ thông tin nói chung, xây dựng bộ phân lớp văn bản báo chí tiếng Việt về tài nguyên và môi trường. Mong muốn ứng dụng hệ thống phân lớp này vào phục vụ nghiên cứu khoa học và công tác quản lý, phân loại các tài liệu văn bản các thông tin chuyên ngành về tài nguyên môi trường, bởi tài nguyên và môi trường hiện nay đang là vấn đề nóng bỏng không những Việt Nam mà cả thế giới đang rất quan tâm. Nội dung và phạm vi đề tài: Trình bày khái niệm khai phá dữ liệu, khai phá văn bản, một số kỹ thuật khai phá văn bản và phân lớp văn bản. Nghiên cứu một số đặc điểm đặc trưng của ngôn ngữ tiếng Việt, phương pháp tách từ tiếng Việt và loại bỏ từ dừng. Nghiên cứu các chủ đề về thông tin chuyên ngành tài nguyên và môi trường. Nghiên cứu, sử dụng thuật toán KNN xây dựng bộ phân lớp văn bản báo chí tiếng việt về tài nguyên và môi trường vào các chủ đề chuyên ngành. 10 Đầu vào của bộ phân lớp là văn bản báo chí tiếng Việt về tài nguyên và môi trường ở dạng tệp tin.doc,.txt, phông chữ Unicode. Đầu ra là kết quả phân lớp văn bản báo chí tiếng Việt vào một trong các chủ đề thông tin chuyên ngành: Tài nguyên đất; tài nguyên nước; tài nguyên khoáng sản; tài nguyên biển; khí tượng thuỷ văn; môi trường; đo đạc và bản đồ. Bố cục của luận văn bao gồm: Chương 1: Khái quát về phân lớp văn bản và thuật toán KNN. Chương này trình bày khái quát về khai phá văn bản, Phân lớp văn bản, thuật toán KNN Chương 2: Bài toán phân lớp văn bản báo chí tiếng Việt về tài nguyên và môi trường. Chương này trình bày đặc điểm cơ bản của tiếng Việt, kỹ thuật tách từ văn bản tiếng Việt, tìm hiểu thông tin chuyên ngành tài nguyên và môi trường, nêu và mô tả bài toán ứng dụng, … Chương 3: Thiết kế xây dựng hệ thống phân lớp văn bản tiếng Việt về tài nguyên môi trường: Trình bày thiết kế xây dựng hệ thống Chương 4: Cài đặt mô hình và kiểm thử kết quả: Trình bày một số giao diện chương trình, kết quả kiểm thử. Kết luận và định hướng phát triển. 11 Chương 1 KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN VÀ THUẬT TOÁN K LÁNG GIỀNG GẦN NHẤT 1.1. KHAI PHÁ DỮ LIỆU VĂN BẢN Khai phá dữ liệu văn bản là quá trình trích chọn ra các tri thức mới, có giá trị và tác động được, đang tiềm ẩn trong các văn bản, để sử dụng các tri thức này vào việc tổ chức thông tin tốt hơn nhằm hỗ trợ con người. Dữ liệu văn bản thường được chia thành hai loại [5]: 1. Dạng phi cấu trúc: là dạng văn bản chúng ta sử dụng hằng ngày được thể hiện dưới dạng ngôn ngữ tự nhiên của con người và không có một cấu trúc định dạng cụ thể nào. Ví dụ: các văn bản lưu dưới dạng tệp tin .TXT, .DOC 2. Dạng bán cấu trúc: là các loại văn bản không được lưu trữ dưới dạng các bản ghi chặt chẽ mà được tổ chức qua các thẻ đánh dấu để thể hiện nội dung chính của văn bản. Ví dụ: dạng tệp tin HTML, email, … Tùy từng mục đích sử dụng cụ thể mà việc xử lý văn bản được thực hiện trên dạng cấu trúc nào. Trong luận văn này, học viên quan tâm xử lý các dữ liệu văn bản ở dạng phi cấu trúc (biểu diễn dưới dạng tệp tin.TXT,.DOC). 1.2. KHÁI NIỆM CƠ BẢN TRONG KHAI PHÁ VĂN BẢN 1.2.1. Một số khái niệm sử dụng trong luận văn - Từ khóa: là các từ xuất hiện trong một văn bản có nghĩa trong từ điển. - Thuật ngữ: là các từ khóa có nghĩa liên quan đến một số lĩnh vực nào đó. ví dụ: "máy tính", "công nghệ phần mềm", "tính toán song song". Các thuật ngữ này thuộc về lĩnh vực "tin học". - Từ dừng: Nhiều từ được dùng để biểu diễn cấu trúc câu, xuất hiện thường xuyên trong các văn bản, nhưng hầu như không mang ý nghĩa về mặt 12 nội dung, chẳng hạn các giới từ, liên từ, … những từ đó được gọi là từ dừng. Ví dụ: Có thể, nếu, vì vậy, sau khi, thì, một số, với lại, quả thật, hầu như, … - Trọng số của từ là độ quan trọng hay hàm lượng thông tin mà từ đó mang lại cho văn bản. Trọng số của từ là đại lượng dùng để đo sự khác biệt giữa văn bản chứa nó với các văn bản khác. 1.2.2. Các phƣơng pháp đánh trọng số cho từ khóa 1.2.2.1. Phương pháp boolean Giả sử có một tập gồm m văn bản D = {d1, d2, d3,......dm}, T là một tập từ vựng gồm n từ khóa T = {t1, t2,......tn}. gọi w = (wi j) là ma trận trọng số, trong đó wi j là trọng số của từ khóa ti trong văn bản dj. Phương pháp boolean là phương pháp đánh trọng số đơn giản nhất, giá trị trọng số wi j được xác định như sau: 1 ti 0 ti dj wi j = dj 1.2.2.2. Phương pháp dựa trên tần số 1/ Phương pháp dựa trên tần số từ khóa TF: Các giá trị wij được tính dựa trên tần số xuất hiện của từ khóa trong văn bản. Gọi fij là số lần xuất hiện của thuật ngữ ti trong văn bản dj, khi đó wij được tính bởi một trong 3 công thức sau: wij = fij hoặc wij = 1 + log(fij) hoặc wij = f ij Trong phương pháp này, trọng số wij tỷ lệ thuận với số lần xuất hiện của từ ti trong văn bản dj. Khi số lần xuất hiện từ khóa ti trong văn bản dj càng nhiều thì điều đó có nghĩa là văn bản dj càng phụ thuộc vào từ khóa ti, hay nói cách khác từ khóa ti mang nhiều thông tin trong văn bản dj. Ví dụ: khi văn bản 13 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. 2/ Phương pháp dựa trên nghịch đảo tần số văn bản IDF: Trong phương pháp này, giá trị wij được tính theo công thức sau: log wij = m hi log(m) log(h 1 ) nếu từ khóa ti xuất hiện trong tài liệu dj 0 nếu ngược lại trong đó m là số lượng văn bản và hi là số văn bản mà từ khóa ti xuất hiện. 3/ Phương pháp TF × IDF: Phương pháp này là tổng hợp của hai phương pháp TF và IDF, giá trị của ma trận trọng số được tính như sau: [1+log(fij)] log wij = m nếu fij ≥1 hi 0 nếu ngược lại Phương pháp này kết hợp được ưu điểm của cả 2 phương pháp trên. Trọng số wij được tính bằng tần số xuất hiện của từ khóa ti trong văn bản dj và độ hiếm của từ khóa ti trong toàn bộ cơ sở dữ liệu. 1.3. MỘT SỐ PHƢƠNG PHÁP BIỂU DIỄN VĂN BẢN 1.3.1. Mô hình Boolean Giả sử có một tập gồm m văn bản D = {d1, d2, d3,......dm}, T là một tập từ vựng gồm n từ khóa T = {t1, t2,......tn}. gọi w = (wi j) là ma trận trọng số, trong đó wi j là trọng số của từ khóa ti trong văn bản dj và được xác định như sau: 1 ti dj wi j = 0 ti dj Trong mô hình boolean, văn bản vốn là tập hợp của các từ khóa, được biểu diễn bởi chỉ số từng từ và trọng số của chúng. Trọng số của từng từ - 14 dùng để đánh giá độ quan trọng của chúng - trong mô hình này chỉ mang hai giá trị 0 và 1, tùy theo sự xuất hiện của từ đó trong văn bản. 1.3.2. Mô hình không gian vector Mô hình không gian véc tơ là mô hình toán học được sử dụng rộng rãi. Mỗi văn bản được biểu diễn thành một vector, trong một không gian véc tơ nhiều chiều, mỗi chiều tương ứng với một từ khóa trong văn bản. Mỗi thành phần của một vector văn bản, là một từ khóa riêng biệt trong tập văn bản gốc và được gán một giá trị là hàm f của từng từ khóa trong văn bản. (thường là gán trọng số từ khóa). Cách biểu diễn văn bản thông dụng nhất là thông qua mô hình không gian vector, đây là một cách biểu diễn tương đối đơn giản. Khi áp dụng xử lý vector thưa, mang lại hiệu quả cao cho bài toán ứng dụng. Xử lý vec tơ thưa T2 Hình 1.1: Biểu diễn văn bản v1 và v2 trong không gian véc tơ ba chiều T1, T2, T3, trong đó Ti là các từ khóa v1 v2 θ v T1 2 T3 Xử lý các phép toán trên vector sẽ phụ thuộc vào độ lớn của ma trận Wnm, ở đây n là số lượng thuật ngữ hay số chiều của vector, và m là số lượng văn bản có trong cơ sở dữ liệu. Trên thực tế, số lượng thuật ngữ và số văn bản có thể lên đến vài chục nghìn. Khi đó số lượng phần tử trong ma trận Wnm sẽ lên đến con số trăm triệu và lưu trữ ma trận Wnm sẽ tốn rất nhiều tài nguyên bộ 15 nhớ, đồng thời các phép toán trên các vector sẽ phức tạp. Để khắc phục, ta có thể sử dụng kỹ thuật xử lý vector thưa. Các vector thực sự thưa: số phần tử có trọng số khác 0 nhỏ hơn rất nhiều so với số thuật ngữ trong cơ sở dữ liệu. Phép xử lý vector đơn giản. Đối với vector chuẩn: d0 = (6, 5, 0, 0, 0, 0); d1 = (0, 0, 4, 0, 3, 1); d2 = (0, 0, 0, 3, 0, 4). Đối với vector thưa: d0 =((1, 6), (2, 5)); d1 = ((3, 4), (5, 3), (6, 1)); d2 = ((4, 3), (6, 4)). Kiểu phần tử của vector thưa có thay đổi so với vector chuẩn. Mỗi phần tử gồm hai giá trị là mã biểu diễn thuật ngữ và giá trị trọng số tương ứng của thuật ngữ đó. 1.3.3. Mô hình xác suất Mô hình xác suất là mô hình toán học làm việc với các biến ngẫu nhiên và phân bố xác xuất của nó. Theo thuật ngữ toán học, một mô hình xác suất có thể coi như một cặp (Y, P), trong đó Y là tập các quan sát (biến ngẫu nhiên) và P là tập các phân bố xác suất trên Y. Khi đó, sử dụng suy diễn xác suất sẽ cho ta kết luận về các phần tử của tập Y. Văn bản trong mô hình xác suất được coi như một quan sát trong tập Y, trong đó các từ trong văn bản được giả thiết là độc lập, không phụ thuộc vào vị trí cũng như ngữ pháp của văn bản. Khi đó văn bản sẽ gồm các từ mà nó chứa trong đó, chính vì vậy phương pháp này được gọi là biểu diễn túi - các - từ. Các bước để chuyển từ không gian các từ khóa sang không gian khái niệm tương đối phức tạp. Trước tiên LSI lập ma trận từ-văn bản với trọng số là một phương pháp đánh chỉ số nào đó 2 1 1 1 1 0 0 1 0 0 … 1 Không gian Từ khóa Khái niệm Trọng số Phương pháp Văn bản Hà Nội Ma trận Việt Nam Hoa Hồng …. LSI 1 LSI Hình 1.2: Biểu diễn văn bản theo túi - các - từ 16 1.3.4. Mô hình LSI LSI đánh chỉ số ngữ nghĩa tiềm năng, là phương pháp được áp dụng nhiều trong bài toán phân lớp. Ý tưởng chính của phương pháp này là, ánh xạ mỗi văn bản vào một tập không gian ít chiều hơn, trong đó mỗi chiều được gắn với một khái niệm. Như vậy bản chất của phương pháp này là chuyển từ không gian các từ khóa sang không gian các khái niệm. 1.4. PHƢƠNG PHÁP LỰA CHỌN TỪ TRONG BIỂU DIỄN VĂN BẢN 1.4.1. Loại bỏ từ dừng Trước hết có thể quan sát thấy rằng, trong một văn bản có nhiều từ chỉ dùng để phục vụ cho biểu diễn cấu trúc câu, chứ không biểu đạt nội dung của nó, chẳng hạn như các giới từ, từ nối,… Những từ xuất hiện nhiều trong văn bản mà không có liên quan gì tới nội dung văn bản. Có thể loại bỏ những từ như vậy, nó được xem như là những từ dừng. 1.4.2. Thu gọn đặc trƣng biểu diễn Với các tài liệu văn bản, mỗi một từ khóa duy nhất sẽ biểu diễn một chiều trong không gian biểu diễn. Do đó, kích thước của không gian biểu diễn văn bản thường rất lớn, việc tính toán sẽ tốn nhiều thời gian. Thêm nữa, một tài liệu văn bản khi được biểu diễn dưới dạng một vector, thì số lượng các phần tử trong vector đó có giá trị 0 là rất lớn, điều này cũng có thể là một nguyên nhân làm cho việc tính toán phân lớp phức tạp và khó khăn hơn. Một trong những giải pháp để khắc phục những vấn đề trên là thu gọn số lượng các từ để biểu diễn văn bản hay là thu gọn số lượng các đặc trưng bằng cách lựa chọn các đặc trưng có khả năng ảnh hưởng đến chất lượng phân lớp của các giải thuật phân lớp, còn các đặc trưng khác có thể bỏ qua. Việc thu gọn này cần đảm bảo sao cho các đặc trưng còn lại vẫn có khả năng "đại diện" cho toàn bộ văn bản, không làm giảm chất lượng phân lớp. 17 Lựa chọn đặc trưng là tiến trình lựa chọn một tập các đặc trưng (hay còn gọi là tập phổ biến) xuất hiện trong tập đào tạo và chỉ sử dụng các tập này như là các đặc trưng để biểu diễn văn bản. Thứ nhất, nó làm cho quá trình huấn luyện các bộ phân lớp hiệu quả hơn bằng cách giảm kích thước của không gian các đặc trưng, điều này đặc biệt quan trọng đối với các giải thuật có chi phí huấn luyện là đắt. Thứ hai, Lựa chọn các đặc trưng thường tăng tính đúng đắn cho quá trình phân lớp, vì nó có thể giúp loại bỏ các đặc trưng nhiễu. Một đặc trưng nhiễu là một đặc trưng mà khi thêm vào biểu diễn tài liệu, nó sẽ làm tăng các lỗi phân loại trên dữ liệu mới. Chúng ta có thể xem lựa chọn đặc trưng như một phương pháp để thay thế một bộ phân lớp phức tạp (sử dụng tất cả các đặc trưng) bằng một bộ phận phân lớp đơn giản hơn (do nó chỉ sử dụng một tập hợp con của các đặc trưng). *Các phương pháp để lựa chọn đặc trưng (các từ) để biểu diễn văn bản hay được sử dụng: 1.4.2.1. Định luật Zipf Để giảm số chiều của vector biểu diễn văn bản ta dựa vào một quan sát sau: các từ xuất hiện ít lần (tần số xuất hiện nhỏ) thì ảnh hưởng rất bé đến nội dung các văn bản. Tiền đề cho việc lý luận để loại bỏ những từ có tần suất nhỏ được đưa ra bởi Zipf năm 1949. Gọi tổng số tần số xuất hiện của từ t trong tài liệu D là ft. Sau đó sắp xếp tất cả các từ trong tập hợp theo chiều giảm dần của tần số xuất hiện ft, và gọi thứ hạng của mỗi từ là rt. Định luật Zipf được phát biểu dưới dạng công thức như sau: rt. ft ≈ K (với K là một hằng số). Hay rt. ≈ K/ ft 18 Tần số xuất hiện f Vùng cao Vùng những từ Mang ý nghĩa Thứ hạng của từ Vùng thấp r Hình 1.3. Lược đồ thống kê tần số của từ theo Định luật Zipf Năm 1958 Luhn đề xuất những từ "phổ biến" và "hiếm" và không cần thiết cho quá trình xử lý. Các từ có tần số xuất hiện cao nhất hiển nhiên là những từ này không góp nhiều trong việc phản ánh nội dung văn bản. Mặt khác, những từ chỉ xuất hiện ít lần (1 đến 3 lần) cũng không đóng vai trò quan trọng. Những từ đóng vai trò quan trọng là những từ có tần số xuất hiện trung bình. Luhn đưa ra một phương pháp đơn giản cho việc lựa chọn các từ để biểu diễn văn bản [5] (lựa chọn đặc trưng) như sau: 1. Cho một tập gồm n văn bản, tính tần số của mỗi từ duy nhất (xuất hiện một lần) trong mỗi văn bản. 2. Tính tần số xuất hiện của mỗi từ trong toàn bộ tập n văn bản 3. Sắp xếp tần số các từ giảm dần. Chọn một giá trị ngưỡng trên để loại bỏ các từ có tần số cao hơn ngưỡng đó. Việc này sẽ loại bỏ các từ có tần số cao. 4. Cũng như vậy, chọn một giá trị ngưỡng dưới để loại bỏ các từ có tần số thấp. 5. Các từ còn lại là các từ được dùng trong quá trình đánh chỉ số văn bản. Việc chọn các từ để đánh chỉ số văn bản hay còn gọi là lựa chọn đặc trưng. 19 Phương pháp này được sử dụng phổ biến là lược bỏ những từ có tần số xuất hiện thấp (từ 1 đến 3 lần) trong văn bản tùy theo từng ứng dụng cụ thể, và loại bỏ những từ có tần số xuất hiện cao. 1.4.2.2. Thuật toán lựa chọn k đặc trưng tốt nhất [5] Thuật toán lựa chọn đặc trưng cơ bản được mô tả ở hình 1.5 cho một lớp c, tính toán một hàm tiện ích A (t, c) cho mỗi thuật ngữ trong tập từ vựng, sau đó lựa chọn k thuật ngữ có giá trị A (t, c) là cao nhất. Tất cả các thuật ngữ còn lại sẽ bị loại bỏ. SELECT FEATURES (ID, c, k) 1. V EXTRACT VOCABULARY (ID) (Trích rút tập từ vựng V từ tập văn bản) 2. L [] (Tập đặc trưng ban đầu gán là rỗng, L = ø) 3. for each t 4. do A (t, c) V (lấy mọi từ khóa t thuộc tập từ vựng V) COMPUTE FEATURE UTILITY (id, t, c) (Tính hàm tiễn ích đặc trưng A(t, c) nhờ mỗi từ khóa t, mỗi chủ đề c, mỗi tập văn bản đã đánh chỉ số id) 5. APPEND (L, A(t, c), t ) (đánh giá lựa chọn cho bộ (L, A(t, c), t )) 6. Return FEATURESWITHLARGESTVALUES (L, k) (trả về tập đặc trưng L với k đặc trưng tốt nhất, có A(t, c) lớn nhất). Hình 1.4. Thuật toán lựa chọn đặc trưng cơ bản cho việc lựa chọn k đặc trưng tốt nhất 1.4.2.3. Thông tin tương hỗ [5] Một phương pháp lựa chọn đặc trưng phổ biến để tính toán A (t, c) là thông tin tương hỗ MI của thuật ngữ t với lớp c. MI đo mức độ thông tin (xuất hiện/không xuất hiện) của thuật ngữ t góp phần làm cho quyết định quá trình phân lớp đúng đắn trên lớp c. 20 Công thức của MI là: I (U , C ) p(U et , C ec ) log et {1, 0} ec {1, 0} p(U et , C ec ) . p(U et ) p(C ec ) Với U là biến ngẫu nhiên, nó có giá trị là et = 1 (tài liệu hiện tại chứa thuật ngữ t) và et = 0 (tài liệu không chứa thuật ngữ t), và C là biến ngẫu nhiên, nó có giá trị e c = 1 (tài liệu có trong lớp c) và e c = 0 (tài liệu không có trong lớp c). Công thức trên được tính theo phương pháp ước lượng maximum likelihood estimation (MLE), được biểu diễn bằng công thức: I(U, C) = N Log NN N NN 11 11 2 1. .1 N Log NN N NN 01 01 2 0. .1 N Log NN N NN 10 10 2 1. .0 N Log NN N NN 00 00 2 0. .0 Trong đó các biến N được tính thông qua các giá trị e 1 và ec (được ký hiệu bằng các con số trong phần chỉ số dưới). N10 là số tài liệu mà có chứa t (et = 1) và không có trong c (e c = 0). N1. = N10 + N11 là số tài liệu mà có chứa t (et = 1). Các biến Nij khác được giải thích tương tự. Và N là tổng các tài liệu: N = N11 + N01 + N10 + N00. Để lựa chọn k các thuật ngữ: t1, …, tk cho bởi lớp nào đó, sử dụng thuật toán lựa chọn đặc trưng trong hình 1.4, tính toán các hàm tiện ích cho tất cả các thuật ngữ A (t, c) = I (Ut, Cc) và sau đó lựa chọn k thuật ngữ có các giá trị lớn nhất. 1.4.2.4. Giải thuật Apriori [3] Giải thuật này được sử dụng để lựa chọn đặc trưng (tập dữ liệu thường xuyên) Thuật toán này sử dụng các k-itemset (tập thuật ngữ gồm k items) để thăm dò (k+1)-itemset và qua đó khai thác được toàn bộ các tập thuật ngữ thường xuyên (Fls) trong tập dữ liệu. - Đầu tiên tính 1-itemsets, 2-itemsets và sau đó là 3-itemsets…