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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.