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. 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. 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.
KHÁI NIỆM CƠ BẢN TRONG KHAI PHÁ VĂN BẢN 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
Các phƣơng pháp đánh trọng số cho từ khóa 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,. 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 dj wi j = 0 ti dj 1.
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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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: m log log(m) log(h 1 ) nếu từ khóa ti xuất hiện trong tài liệu dj wij = hi 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: m [1+log(fij)] log nếu fij ≥1 hi wij = 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. MỘT SỐ PHƢƠNG PHÁP BIỂU DIỄN VĂN BẢN 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,. 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ừ - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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. 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 v1 Hình 1.1: Biểu diễn v2 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 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ộ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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ữ đó. 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ừ. 2 Không gian Các bước để chuyển từ 1 Từ khóa không gian các từ khóa 1 Khái niệm sang không gian khái niệm 1 Trọng số tương đối phức tạp.
Trước 1 Phương pháp tiên LSI lập ma trận từ-văn 0 Văn bản bản với trọng số là một 0 Hà Nội phương pháp đánh chỉ số 1 Ma trận nào đó 0 Việt Nam 0 Hoa Hồng … ….2: Biểu diễn văn bản theo túi - các - từ 1 LSI LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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.
PHƢƠNG PHÁP LỰA CHỌN TỪ TRONG BIỂU DIỄN VĂN BẢN 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. 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.