TỔNG QUAN
Đặt vấn đề
Trong thời đại công nghệ thông tin bùng nổ, việc sử dụng giấy tờ trong giao dịch đã được số hoá, chuyển sang dạng văn bản lưu trữ trên máy tính và truyền tải qua mạng Tài liệu số mang lại nhiều ưu điểm như lưu trữ gọn nhẹ, thời gian lưu trữ lâu dài, tiện lợi trong trao đổi qua Internet và dễ dàng sửa đổi Do đó, số lượng văn bản số ngày càng tăng nhanh chóng, đặc biệt trên mạng toàn cầu Cùng với sự gia tăng này, nhu cầu tìm kiếm văn bản cũng tăng theo, khiến cho việc phân loại văn bản tự động trở thành một nhu cầu bức thiết.
Phân loại văn bản tự động là cần thiết để tối ưu hóa quá trình tìm kiếm thông tin, giúp người dùng dễ dàng và nhanh chóng truy cập dữ liệu mà không cần phải lục lọi trong ổ đĩa lưu trữ Khi khối lượng thông tin ngày càng gia tăng, việc áp dụng công nghệ phân loại văn bản tự động không chỉ tiết kiệm thời gian mà còn giảm thiểu công sức cho con người.
Do vậy, các phương pháp phân loại văn bản tự động đã ra đời để phục vụ cho nhu cầu chính đáng đó.
Tổng quan tình hình nghiên cứu trong và ngoài nước
Công tác phân loại tài liệu là một nhiệm vụ quan trọng được các thư viện và cơ quan thông tin trên toàn thế giới chú trọng Việc phân loại giúp kiểm soát thư mục, đồng thời thúc đẩy khai thác và trao đổi thông tin cả trong nước và quốc tế Nhiều thư viện lớn ở Việt Nam cũng áp dụng phương pháp phân loại này để tổ chức kho mở và hỗ trợ tra cứu thông tin hiệu quả.
Theo Yang & Xiu (1999), phân loại văn bản tự động là quá trình gán nhãn cho văn bản mới dựa trên sự tương đồng với các văn bản đã được gán nhãn trong tập huấn luyện Trong lĩnh vực này, đã có nhiều nghiên cứu đáng chú ý, đặc biệt là trong tiếng Anh, với những kết quả khả quan Dựa trên thống kê của Yang & Xiu (1999) và các nghiên cứu hiện tại, một số phương pháp phân loại phổ biến hiện nay bao gồm Support Vector Machine (SVM).
Các phương pháp như k-Nearest Neighbor (Joachims, 1998), Linear Least Squares Fit (Yang và Chute, 1994), Neural Network (Wiener et al, 1995), Nạve Bayes (Baker và Mccallum, 2000), và Centroid-based (Shankar và Karypis, 1998) đều dựa vào xác suất thống kê hoặc thông tin trọng số của từ trong văn bản Chi tiết về ý tưởng và công thức tính toán của từng phương pháp sẽ được trình bày trong chương 2, mục 2.3.
Mỗi phương pháp phân loại văn bản đều có cách tính toán và công thức riêng, nhưng nhìn chung, chúng đều trải qua một số bước chung Đầu tiên, các phương pháp dựa vào thông tin về sự xuất hiện của từ trong văn bản để chuyển đổi văn bản thành dạng vector Sau đó, tùy thuộc vào từng phương pháp, các công thức và cách tính toán sẽ được áp dụng để thực hiện phân loại Trong khi các kết quả phân loại văn bản tiếng Anh đạt được nhiều thành công, thì nghiên cứu về phân loại văn bản tiếng Việt vẫn còn nhiều hạn chế, đặc biệt là ở bước xử lý văn bản để rút ra tần số xuất hiện của từ Bước tách từ là rất quan trọng, vì nếu sai ở giai đoạn này, việc phân loại sẽ khó có thể thành công Bài viết tiếp theo sẽ trình bày những thách thức trong việc tách từ tiếng Việt và các ứng dụng thú vị liên quan.
Trong những năm gần đây, vấn đề phân loại văn bản tiếng Việt đã thu hút sự quan tâm của nhiều cơ sở nghiên cứu trong cả nước, với một số công trình đạt kết quả khả quan Các hướng tiếp cận bài toán phân loại văn bản bao gồm lý thuyết đồ thị, lý thuyết tập thô, thống kê, học không giám sát và đánh chỉ mục, đều cho kết quả tốt Tuy nhiên, để triển khai khả thi, cần tiếp tục nghiên cứu dựa trên các hướng này Một thách thức lớn trong việc áp dụng thuật toán phân loại cho tiếng Việt là xây dựng tập hợp từ vựng, liên quan đến việc phân tách câu thành từ chính xác Khác với tiếng Anh, nơi từ được phân tách bởi khoảng trắng, tiếng Việt có ranh giới từ phụ thuộc vào ngữ cảnh Giải quyết vấn đề tách từ chính xác sẽ mở ra nhiều cơ hội phát triển trong các lĩnh vực như phân loại văn bản, dịch tự động, kiểm tra chính tả và ngữ pháp, đáp ứng nhu cầu thiết yếu của con người.
Nghiên cứu cho thấy các phương pháp tách từ từ tiếng Hoa như Maximum Matching (LRMM), giải thuật học cải biến TBL, mạng chuyển dịch trạng thái hữu hạn có trọng số WFST, và giải thuật dựa trên nén đã được áp dụng cho tiếng Việt Tuy nhiên, để đạt hiệu quả cao, cần có một hệ thống từ điển và ngữ liệu đánh dấu đầy đủ và chính xác; nếu từ điển hoặc ngữ liệu không hoàn chỉnh, hiệu suất của thuật toán sẽ bị giảm.
Gần đây, phương pháp tách từ mới mang tên Internet and Genetics Algorithm-based Text Categorization (IGATEC) do H Nguyen et al (2005) giới thiệu đã nổi bật nhờ không cần tập dữ liệu hay từ điển để thu thập thông tin thống kê Sự sáng tạo của thuật toán này nằm ở việc kết hợp thuật toán di truyền với việc trích xuất thông tin từ Internet qua công cụ tìm kiếm như Google, thay vì dựa vào tập dữ liệu như các phương pháp trước Để thực hiện tách từ, luận văn này áp dụng mô hình N-gram, chia văn bản thành các chuỗi gồm hai hoặc ba ký tự trở lên, sử dụng tập dữ liệu thô và dữ liệu đã được phân loại trước.
Mục tiêu của luận văn
Tìm hiểu thuật tốn Nạve Bayes ứng dụng vào xây dựng một chương trình phân loại văn bản.
Nội dung thực hiện
i) Tìm tập dữ liệu bao gồm tập kiểm thử chương trình và tập máy học bao gồm các bộ test trong đó:
+ Tập máy học bao gồm các bài báo đƣợc phân loại theo tri thức, phân loại thủ công hay dựa vào đề tài để phân loại làm dữ liệu
Tập dữ liệu kiểm thử là tập hợp các bài báo đã được phân loại, dùng để kiểm tra chương trình và thu thập kết quả thống kê Đầu tiên, cần tìm hiểu các phương pháp tách từ hiện tại để chọn ra phương pháp tối ưu Sau đó, thực hiện tách từ và loại bỏ các stop word dựa trên phương pháp đã chọn cho tập dữ liệu Tiếp theo, cần nghiên cứu các phương pháp tính trọng số từ và lựa chọn phương pháp phù hợp Cuối cùng, rút trích đặc trưng ước lượng xác suất bằng phương pháp Nạve Bayes trong chương trình phân loại văn bản tiếng Việt, tiến hành thử nghiệm và rút ra kết luận.
CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN
Tổng quát về các phương pháp phân loại văn bản
Phân loại văn bản tự động đang trở thành một lĩnh vực thu hút sự quan tâm lớn trong những năm gần đây, với nhiều phương pháp tiếp cận khác nhau như dựa trên từ khóa, ngữ nghĩa từ, và mô hình Maximum Entropy Tiếng Anh là ngôn ngữ được nghiên cứu sớm nhất và đã đạt được nhiều thành tựu đáng kể thông qua các phương pháp như k-Nearest Neighbors, Nạve Bayes, cây quyết định, Support Vector Machine và mô hình cực đại entropy Tuy nhiên, hiệu quả của các phương pháp này có sự khác biệt rõ rệt, ngay cả trong tiếng Anh, và việc đánh giá còn gặp khó khăn do thiếu tập dữ liệu huấn luyện chuẩn Chương hai sẽ giới thiệu các thuật toán phổ biến và so sánh sự tương đồng cũng như khác biệt giữa các phương pháp.
Mô tả bài toán phân loại văn bản
Ý tưởng của phương pháp phân loại các chủ đề, cần dự đoán văn bản đó thuộc vào chủ đề nào trong số các chủ đề đã cho
Gọi X là tập các văn bản cần phân loại và Y là tập các chủ đề có thể đƣợc gán cho các văn bản Khi đó ta cần phải chỉ ra một văn bản x X thuộc vào chủ đề y Y nào Trong đó, x bao gồm các từ, cụm từ, câu đƣợc dùng cho nhiệm vụ phân loại Để rõ hơn ta xét ví dụ gồm 6 lớp các bài báo có thể đƣợc phân loại: báo pháp luật, báo gia đình, báo thể thao, báo văn hóa, báo về giới tính, báo nhân dân Và chúng ta có ràng buộc, nếu một văn bản có từ “bóng đá” xuất hiện thì khả năng văn bản đó thuộc vào lớp “báo thể thao” là 30% và 70% là khả năng mà văn bản đó thƣợc vào 5 lớp còn lại Với ví dụ này thì chúng ta có thể dễ dàng tính đƣợc Nhƣng thực tế thì không phải chỉ một vài ràng buộc đơn giản nhƣ vậy, mà là hàng trăm hàng nghìn ràng buộc phức tạp hơn nhiều
Nhiệm vụ đầu tiên là chuyển đổi văn bản thành các từ, cụm từ và câu có chọn lọc Cần loại bỏ những từ, cụm từ và câu không có ý nghĩa hoặc không có ảnh hưởng tích cực đến quá trình phân loại.
Bước tiếp theo trong bài toán phân loại là xác định các ràng buộc từ tập dữ liệu huấn luyện, với mỗi ràng buộc thể hiện một đặc trưng của dữ liệu Khi có một bài báo, chúng ta sẽ dựa vào các đặc điểm như tiêu đề và nội dung để nâng cao khả năng phân loại Số lượng thông tin thu thập được càng nhiều thì xác suất phân loại đúng càng cao, tuy nhiên điều này còn phụ thuộc vào kích thước của tập mẫu huấn luyện.
Việc áp dụng công thức Nạve Bayes trong tính toán xác suất cho phép so sánh xác suất thu được với một giá trị ngưỡng t nhất định, từ đó phân loại bài báo vào thể loại phù hợp.
Các phương pháp phân loại văn bản
SVM, hay Support Vector Machine, là một phương pháp được giới thiệu bởi Vapnik vào năm 1995, nhằm giải quyết bài toán nhận dạng mẫu hai lớp Phương pháp này dựa trên nguyên lý cực tiểu hóa rủi ro có cấu trúc, giúp cải thiện độ chính xác trong việc phân loại dữ liệu.
Trong không gian vector, mỗi văn bản được biểu diễn như một điểm, và phương pháp tìm kiếm siêu mặt phẳng h nhằm phân chia các điểm thành hai lớp riêng biệt (+ và -) Hiệu quả của siêu mặt phẳng này phụ thuộc vào khoảng cách giữa các điểm gần nhất của mỗi lớp đến mặt phẳng; khoảng cách lớn hơn đồng nghĩa với khả năng phân loại chính xác cao hơn Mục tiêu cuối cùng là tối ưu hóa khoảng cách biên lớn nhất giữa các lớp.
Hình 2.1 Phân chia dữ liệu huấn huyện b) Công thức
Phương trình siêu mặt phẳng chứa vector như sau: ̅ ̅ Đặt
Nhƣ vậy ( ̅ ) biểu diễn sự phân lớp của ̅ vào 2 lớp + và lớp - Gọi yi = {±1}, yi
= +1 văn bản ̅ thuộc lớp +, y i = -1 văn bản ̅ thuộc lớp - Để có siêu mặt phẳng h ta đi giải bài toán:
Tính Min || ̅|| với ̅ và b thoản mãn điều kiện: ̅̅̅̅̅ ( ̅ ̅ )
Bài toán SVM có thể đƣợc giải bằng toán tử Lagrange để biến đổi thành dạng đẳng thức
Một điểm nổi bật của phương pháp SVM là siêu mặt phẳng h chỉ phụ thuộc vào các vector hỗ trợ, điều này khác biệt so với các phương pháp phân loại khác mà kết quả của chúng phụ thuộc vào toàn bộ dữ liệu Do đó, khi dữ liệu thay đổi, kết quả phân loại cũng sẽ thay đổi.
Phương pháp Naive Bayes (NB) là một kỹ thuật phân loại dựa trên xác suất, phổ biến trong máy học và nhiều lĩnh vực khác như công cụ tìm kiếm và bộ lọc email Ý tưởng chính của NB là sử dụng xác suất có điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của văn bản cần phân loại Điểm nổi bật của phương pháp này là giả định rằng sự xuất hiện của tất cả các từ trong văn bản là độc lập, điều này giúp giảm độ phức tạp tính toán và làm cho NB nhanh chóng hơn so với các phương pháp khác.
Mục đích chính là tính toán xác suất để xác định lớp cho văn bản Theo quy luật Bayes, văn bản sẽ được phân loại vào lớp có xác suất cao nhất.
Công thức để tính | nhƣ sau:
Mục tiêu trong phân lớp Nạve Bayes là tìm lớp cĩ giá trị lớn nhất của :
Likelihood: Giả sử rằng các mẫu quan sát độc lập và các đặc trƣng độc lập Với mỗi vector đặc trƣng x i = (x i1 , x i2 , ã ã ã , x id ):
- là số lần đặc trƣng xik xuất hiện trong lớp
- là tổng số tất cả các đặc trƣng trong lớp
Priori: Xác suất trước được tính như sau:
- là tổng số tất cả các mẫu của tập dữ liệu D
Evidence: Có giá trị nhƣ nhau với tất cả các lớp
Ngoài các phương pháp Naive Bayes như Naive Bayes, MAP Naive Bayes và Expected Naive Bayes, thuật toán Naive Bayes được coi là một công cụ hiệu quả trong nhiều trường hợp Tuy nhiên, kết quả có thể kém nếu dữ liệu huấn luyện không đầy đủ và các tham số dự đoán có chất lượng thấp Thuật toán này thường được sử dụng cho phân loại văn bản với nhiều chủ đề nhờ vào tính chất phân loại tuyến tính của nó.
NB có những ưu điểm nổi bật như cài đặt dễ dàng, tốc độ thực hiện thuật toán nhanh chóng, khả năng cập nhật dữ liệu huấn luyện mới một cách thuận lợi và tính độc lập cao với tập huấn luyện.
Bước đầu tiên trong phân loại văn bản là chuyển đổi mô tả văn bản từ chuỗi ký tự sang dạng mô tả phù hợp với các thuật toán Hầu hết các thuật toán sử dụng biểu diễn theo vector đặc trưng, với sự khác biệt chủ yếu ở việc chọn không gian đặc trưng Đối với mô hình cực đại entropy, thuật toán IIS chỉ có thể tính toán các tham số dựa trên vector đặc trưng Vậy vector đặc trưng là gì?
Mỗi vector đặc trưng ̅ biểu thị một văn bản trong không gian từ vựng w: ̅(TF( ), TF( ), , TF( )) Ở đây, TF( ) đại diện cho tần suất xuất hiện của từ trong văn bản, và n là số chiều của không gian từ.
Hình 2.2 Biểu diễn văn bản
Biểu diễn văn bản bằng các vector đặc trưng thường gặp khó khăn trong việc xác định số lượng từ cần thiết để đại diện cho văn bản Một thách thức quan trọng là cách lựa chọn những từ này một cách hiệu quả Để giải quyết vấn đề này, chúng tôi giới thiệu phương pháp tiếp cận dựa trên Information Gain, như đã được đề xuất bởi Yang và Petersen vào năm 1997.
Các đặc trưng của văn bản khi biểu diễn dưới dạng vector:
- Số chiều không gian đặc trưng thường rất lớn
2.3.4 K–Nearest Neighbor (kNN) kNN là phương pháp truyền thống khá nổi tiếng theo hướng tiếp cận thống kê đã đƣợc nghiên cứu trong nhiều năm qua KNN đƣợc đánh giá là một trong những phương pháp tốt nhất được sử dụng từ những thời kỳ đầu trong nghiên cứu về phân loại văn bản a) Ý tưởng Ý tưởng của phương pháp này đó là khi cần phân loại một văn bản mới, thuật toán sẽ xác định khoảng cách (có thể áp dụng các công thức về khoảng cách nhƣ Euclide, Cosine, Manhattan,…) 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 Nearest Neighbor – k láng giềng gần nhất, sau đó dùng các khoảng cách này đánh trọng số cho tất cả các chủ đề Khi đó, trọng số của một chủ đề chính là tổng tất cả các khoảng cách ở trên của 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 giá trị trọng số giảm dần và các chủ đề có trọng số cao sẽ đƣợc chọn làm chủ đề của văn bản cần phân loại b) Công thức
Trọng số của chủ đề cj đối với văn bản x đƣợc tính nhƣ sau:
- y = 0: văn bản di không thuộc về chủ đề
Để phân loại văn bản thuộc chủ đề cjsim, ta sử dụng độ giống nhau giữa văn bản cần phân loại x và văn bản d Khoảng cách này có thể được tính bằng cách áp dụng độ đo cosine.
Bj là ngưỡng phân loại cho chủ đề cj, được xác định tự động qua một tập văn bản hợp lệ từ dữ liệu huấn luyện Để tìm ra tham số k tối ưu cho quá trình phân loại, thuật toán cần thử nghiệm với nhiều giá trị k khác nhau; giá trị k càng lớn thì độ ổn định của thuật toán càng cao và tỷ lệ sai sót càng giảm.
2.3.5 Linear Least Square Fit (LLSF)
LLSF là một cách tiếp cận ánh xạ đƣợc phát triển bởi Yang và Chute vào năm
Năm 1992, LLSF được thử nghiệm trong việc xác định từ đồng nghĩa và sau đó được áp dụng trong phân loại vào năm 1994 Các thử nghiệm cho thấy hiệu suất phân loại của LLSF có thể đạt được tương đương với phương pháp kNN cổ điển.
LLSF áp dụng phương pháp hồi quy để học từ tập huấn luyện và các chủ đề hiện có [Yang & Chute, 1994] Tập huấn luyện được thể hiện dưới dạng cặp vector đầu vào và đầu ra.
- Vector đầu vào một văn bản bao gồm các từ và trọng số
Kết luận chung về các phương pháp phân loại văn bản
Các thuật toán phân loại như SVM, kNN, NB và LLSF đều yêu cầu văn bản được biểu diễn dưới dạng vector đặc trưng Trong khi các thuật toán kNN, NB và LLSF cần ước lượng tham số và ngưỡng tối ưu cho việc phân loại, SVM có khả năng tự xác định các tham số này trong quá trình thực hiện Về thời gian, kNN, NB và LLSF có thời gian huấn luyện và phân loại nhanh hơn, đồng thời dễ cài đặt hơn so với các thuật toán khác Một câu hỏi quan trọng đặt ra là: “Để đạt được kết quả phân loại tốt, cần những yếu tố gì?”
Có 3 yếu tố quan trọng tác động đến kết quả phân loại văn bản: i) Cần một tập dữ liệu huấn luyện chuẩn và đủ lớn để cho thuật toán học phân loại Nếu chúng ta có đƣợc một tập dữ liệu chuẩn và đủ lớn thì qúa trình huấn luyện sẽ tốt và khi đó chúng ta sẽ có kết quả phân loại tốt sau khi đã đƣợc học ii) Các phương pháp trên hầu hết đều sử dụng mô hình vector để biểu diễn văn bản, do đó phương pháp tách từ trong văn bản đóng vai trò quan trọng trong qúa trình biểu diễn văn bản bằng vector Yếu tố này rất quan trọng, vì có thể đối với một số ngôn ngữ nhƣ tiếng Anh chẳng hạn thì thao tác tách từ trong văn bản đơn giản chỉ là dựa vào các khoảng trắng, tuy nhiên trong các ngôn ngữ đa âm tiết nhƣ tiếng Việt và một số ngôn ngữ khác thì sử dụng khoảng trắng khi tách từ là không chính xác, do đó phương pháp tách từ là một yếu tố quan trọng iii) Thuật toán sử dụng để phân loại phải có thời gian xử lý hợp lý, thời gian này bao gồm: thời gian học, thời gian phân loại văn bản, ngoài ra thuật toán này phải có tính tăng cường (incremental function) nghĩa là không phân loại lại toàn bộ tập văn bản khi thêm một số văn bản mới vào tập dữ liệu mà chỉ phân loại các văn bản mới mà thôi, khi đó thuật toán phải có khả năng giảm độ nhiễu ( noise ) khi phân loại văn bản.
Tách từ trong bài toán phân loại văn bản
Hiện nay, các phương pháp tách từ tiếng Việt chủ yếu dựa vào tập huấn luyện và từ điển, nhưng số lượng phương pháp vẫn còn hạn chế Việc xây dựng hệ thống dữ liệu cho tách từ là một nhiệm vụ khó khăn, yêu cầu đầu tư lớn về công sức, thời gian và tiền bạc Trong tiếng Việt, đơn vị nhỏ nhất là “tiếng”, được cấu thành từ nhiều ký tự trong bảng chữ cái Phương pháp tách từ thường sử dụng kỹ thuật rút trích như unigram hoặc n-gram, với các nghiên cứu như của Lê An Hà [2003] đã chứng minh tính hiệu quả qua việc xây dựng tập ngữ liệu thô 10MB bằng phương pháp quy hoạch động Ưu điểm của phương pháp này là tính đơn giản, dễ ứng dụng, và chi phí thấp cho việc tạo chỉ mục và xử lý nhiều câu truy vấn.
Sau đó, em sẽ cài đặt, thử nghiệm độ chính xác của phương pháp tách từ này trong khía cạnh phân loại văn bản
Phân định từ loại trong tiếng Việt là một vấn đề phức tạp do tiếng Việt thuộc loại hình phi hình thái Việc phân biệt các loại từ như danh từ, động từ, tính từ và ý nghĩa của chúng gặp nhiều khó khăn, ngay cả khi tham khảo từ điển.
Tiền xử lý văn bản, bao gồm các bước như tách từ, tách đoạn và tách câu, trở nên phức tạp hơn khi phải xử lý các hư từ, phụ từ, từ láy và từ ghép.
Ví dụ: lấp lánh, lung linh Hiện đại → hại điện, thầy giáo → tháo giầy…
Phương thức ngữ pháp chính là trật tự từ, do đó việc áp dụng phương pháp tính xác suất xuất hiện của từ có thể không đạt được độ chính xác như mong đợi.
Ranh giới từ trong tiếng Việt không được xác định chỉ bằng khoảng trắng, điều này gây khó khăn trong việc phân tích hình thái và tách từ Việc nhận diện ranh giới từ rất quan trọng, vì nó là tiền đề cho các xử lý tiếp theo như kiểm lỗi chính tả, gán nhãn từ loại và thống kê tần suất từ.
Từ chỉ loại, hay phó danh từ chỉ loại, là loại từ đặc biệt đi kèm với danh từ, ví dụ như cái ghế, cuốn vở, hay con mèo Tuy nhiên, tập ngữ liệu hiện tại vẫn còn hạn chế về số lượng, ảnh hưởng đến khả năng tách từ một cách phong phú Việc xây dựng ngữ liệu chủ yếu dựa trên phương pháp thủ công cũng dẫn đến tính chủ quan Hơn nữa, quá trình đánh giá và cập nhật thay đổi diễn ra chậm, dễ dẫn đến hiện tượng flip-flop, khi việc sửa lỗi này lại gây ra lỗi khác Trong cách tiếp cận từ điển, các từ được tách cần phải tương ứng với những từ có trong từ điển, nhưng hiện tại, chúng ta vẫn chưa có một bộ từ điển tiếng Việt đầy đủ.
2.5.2 Các phương pháp tách từ a) Phương pháp dựa trên Otomat
Phương pháp này sử dụng tập dữ liệu gồm bảng âm tiết tiếng Việt (khoảng
Phương pháp này sử dụng 6700 âm tiết và khoảng 30.000 từ từ điển tiếng Việt, với các từ điển được lưu dưới dạng tệp văn bản định dạng TCVN hoặc Unicode (UTF-8) Các bước giải quyết được thực hiện để đảm bảo tính chính xác và hiệu quả trong việc xử lý ngôn ngữ.
- Xây dựng ôtômát âm tiết đoán nhận tất cả các âm tiết tiếng Việt
- Xây dựng ôtômát từ vựng đoán nhận tất cả các từ vựng tiếng Việt
Dựa trên các ôtômát đã nêu, chúng ta cần xây dựng đồ thị tương ứng với câu cần phân tích và áp dụng thuật toán tìm kiếm trên đồ thị để liệt kê các cách phân tích khả thi Bảng chữ cái của ôtômát âm tiết sử dụng bảng chữ cái tiếng Việt, với mỗi cung chuyển được ghi một ký tự Chẳng hạn, với ba âm tiết "phương", "pháp", "trình", chúng ta sẽ có ôtômát để nhận diện âm tiết như trong Hình 2.4.
Ôtômát âm tiết được xây dựng bằng cách ghi số hiệu của trạng thái kết thúc trên mỗi cung chuyển, thay vì ghi âm tiết như trong ôtômát từ vựng Phương pháp này giúp giảm kích thước của ôtômát từ vựng, tối ưu hóa quá trình nhận diện âm tiết của từ.
Khi áp dụng ôtômát âm tiết cho hai từ "phương pháp" và "phương trình", các âm tiết "phương", "pháp", "trình" sẽ dẫn đến các trạng thái kết ghi với các số n1, n2, n3 Trên các cung chuyển tương ứng, chúng ta ghi lại các số n1, n2, n3.
Hình 2.5 Xây dựng ôtômát từ vựng
Thuật toán phân tách từ vựng dựa trên việc phân tách câu thành các đường đi trên một đồ thị có hướng, không có trọng số Câu ban đầu được biểu diễn dưới dạng dãy âm tiết s0, s1, , sn, và đồ thị được xây dựng với n+2 đỉnh v0, v1, , vn, vn+1 Mỗi cung giữa các đỉnh vi và vj (i < j) tương ứng với việc các âm tiết si, si+1, , sj-1 tạo thành một từ Các cách phân tách câu khác nhau tương ứng với các đường đi từ đỉnh đầu v0 đến đỉnh cuối vn+1, trong đó phương pháp phân tích chính xác nhất thường liên quan đến đường đi qua ít cung nhất Khi có sự nhập nhằng trong câu, đồ thị sẽ có nhiều hơn một đường đi ngắn nhất, do đó cần liệt kê tất cả các đường đi ngắn nhất để đưa ra các phương án tách từ, cho phép người dùng lựa chọn dựa trên ngữ nghĩa hoặc ngữ cảnh.
Hình 2.6 Một tình huống nhập nhằng trong phân tách từ
Cụm từ này gây nhầm lẫn giữa "thuộc địa" và "địa bàn", dẫn đến hai cách phân tách là “thuộc địa/bàn” và “thuộc/địa bàn” Trong tiếng Việt, có nhiều cụm từ tương tự gây nhập nhằng, như “tổ hợp âm tiết” và “bằng chứng cớ”.
Khi một câu chứa âm tiết không có trong từ điển, ôtômát âm tiết sẽ không nhận diện được âm tiết đó, dẫn đến việc đồ thị xây dựng từ câu trở nên không liên thông Điều này cho thấy, nếu đồ thị không liên thông, ta có thể dễ dàng xác định rằng âm tiết không được nhận diện không nằm trong từ điển, có thể là do viết sai chính tả hoặc là một đơn vị âm tiết (từ vựng) mới.
Bài toán phân tách từ vựng trong câu tiếng Việt đã được giải quyết hiệu quả, đặc biệt trong việc tách các tổ hợp từ tương đương với đơn vị từ vựng như cụm từ cố định, cụm từ gợi ý và thành ngữ Đối với những câu có sự nhập nhằng từ vựng, phương pháp liệt kê toàn bộ các phương án tách từ có thể được áp dụng, cho phép người dùng lựa chọn kết quả phù hợp Trong số các phương án phân tách này, luôn tồn tại ít nhất một phương án đúng Để nâng cao độ chính xác, mô hình n-gram và phương pháp xác suất thống kê được sử dụng.
Hướng tiếp cận này thường quy định tham số đầu vào n trong mô hình n-gram, với n thường là 2, do số lượng từ ghép hai tiếng chiếm ưu thế trong từ điển tiếng Việt Mô hình n-gram tách các từ liên tiếp nhau trong văn bản, giả sử có văn bản S = {t1, t2,…, ti} với ti là tiếng trong văn bản, mô hình này sẽ gom các tiếng liên tiếp thành một từ Với i tiếng, sẽ có (i-(n-1)) từ được tạo ra.
Ví dụ ta có câu: “Bài báo trình bày một phương pháp hoàn toàn mới”
Dùng mô hình n-gram với n=2 ta sẽ có các từ: w 1 =”Bài báo”, w 2 =”báo trình”, w 3 =”trình bày”, w 4 =”bày một”, w 5 =”một phương”, w 6 = “phương pháp”, w 7 =”pháp hoàn”, w 8 =”hoàn toàn”, w 9 =”toàn mới”
ỨNG DỤNG PHÂN LOẠI TÀI LIỆU
Quy trình xử lý phân loại bài báo
Để tiến hành phân loại văn bản nói chung, chúng ta sẽ thực hiện các bước như sau:
Hình 3.1 Mô hình phân loại tài liệu tự động
Bước 1: Rút trích đặc trưng văn bản và tính trọng số của từ
Trong bước 2, chúng tôi áp dụng thuật toán phân loại văn bản Navie Bayes để xử lý các chủ đề đa dạng Thuật toán này nổi bật với cài đặt đơn giản, tốc độ thực hiện nhanh và khả năng cập nhật dữ liệu huấn luyện dễ dàng, đồng thời có tính độc lập cao với tập huấn luyện Để rút trích đặc trưng của văn bản, chúng tôi thực hiện tách từ, xác định từ loại và tính trọng số cho các từ trong văn bản.
3.1.1 Tách từ trong văn bản
Do thời gian hạn chế và kiến thức chưa đầy đủ, tôi chưa thể áp dụng phương pháp tách từ bằng N-gram Thay vào đó, tôi đã sử dụng phương pháp tách từ dựa trên dấu câu, khoảng trắng và các ký tự đặc biệt.
Ví dụ ta có câu : “báo cáo, tốt;nghiệp ,sinh viên! Hồ #diên @công”
Khi tách ta đƣợc các từ :
3.1.2 Loại bỏ các từ tầm thường
Sau khi tách từ trong văn bản, bước tiếp theo là loại bỏ các từ tầm thường (stopword) Không phải tất cả các từ đều mang ý nghĩa tương đương hay mô tả nội dung của văn bản Các từ không mang ngữ nghĩa được gọi là stopword và cần được loại bỏ Trong ngôn ngữ tự nhiên, các mạo từ, giới từ, liên từ thường là stopword, bên cạnh một số động từ, tính từ và phó từ cũng được xem là như vậy Danh sách chi tiết các từ stopword được liệt kê trong phụ lục.
Trích chọn đặc trƣng văn bản
Các phương pháp rút trích thông tin cổ điển xem mỗi văn bản là một tập hợp các từ khóa, hay còn gọi là tập các term Mỗi từ trong tập từ khóa mang ngữ nghĩa quan trọng, góp phần hình thành nội dung văn bản Do đó, tập từ khóa được sử dụng để tạo chỉ mục và tóm lược nội dung của văn bản một cách hiệu quả.
Trong một tập từ khoá của một văn bản, không phải tất cả các từ đều có mức độ quan trọng như nhau trong việc mô tả nội dung Ví dụ, nếu một từ A xuất hiện trong một trăm nghìn văn bản, có thể khẳng định rằng từ A không quan trọng và sẽ bị loại ra khỏi tập từ khoá Để xây dựng tập từ khoá cho văn bản, cần xác định trọng số cho từng từ Gọi k_i là từ thứ i trong tập từ khoá, d_j là văn bản j, và w_ij là trọng số của từ k_i trong văn bản d_j Trọng số này rất quan trọng trong việc miêu tả nội dung văn bản Nếu một từ không xuất hiện trong văn bản, trọng số của nó sẽ là 0 Do đó, văn bản d_j được biểu diễn bằng vector d_j với các trọng số tương ứng.
3.2.2 Phương pháp rút trích đặc trưng
Theo truyền thống, văn bản D được biểu diễn bằng một vector đặc trưng dưới dạng (d1, d2, …, dn), trong đó di là trọng số của đặc trưng thứ i và n là tổng số đặc trưng Mỗi đặc trưng tương ứng với một từ trong tập huấn luyện, sau khi đã loại bỏ các stopword khỏi văn bản.
Phương pháp phổ biến nhất để rút trích đặc trưng từ văn bản là dựa vào tần suất xuất hiện của các từ Quy trình này bao gồm hai bước chính: đầu tiên, loại bỏ các từ chung không ảnh hưởng đến nội dung bằng cách sử dụng từ điển đặc biệt hoặc danh sách các từ tầm thường (stopword) Tiếp theo, xác định tần suất xuất hiện của các từ còn lại trong văn bản và tính giá trị trọng số cho chúng Cuối cùng, n từ có giá trị trọng số lớn nhất sẽ được chọn làm n đặc trưng chính của văn bản.
Một phương pháp hiệu quả để rút trích đặc trưng văn bản là kết hợp tần suất xuất hiện của từ (TF) trong văn bản với tần suất ngược (IDF) Phương pháp này giúp xác định độ quan trọng của từ trong ngữ cảnh, từ đó cải thiện chất lượng phân tích và tìm kiếm thông tin Sự kết hợp này không chỉ tăng cường khả năng nhận diện các đặc điểm nổi bật của văn bản mà còn tối ưu hóa cho các công cụ tìm kiếm.
IDF) Lúc này chúng ta có công thức tính giá trị trọng số cho từ T j trong văn bản D i , nhƣ sau:
Trong tập văn bản N, df j đại diện cho số lượng văn bản chứa từ T j Tương tự như phương pháp 1, n từ T j có trọng số cao nhất sẽ được lựa chọn làm n đặc trưng cho văn bản.
3.2.3 Phương pháp đặc trưng đề nghị sử dụng
Chúng ta sẽ áp dụng phương pháp rút trích đặc trưng phù hợp với mục tiêu của đề tài, lựa chọn phương pháp Tf*idf weighting do những lý do sau đây.
- Phương pháp này không phụ thuộc vào tần suất xuất hiện của các từ trong văn bản
- Phương pháp này cân bằng giữa yếu tố mức độ bao phủ và số luợng các đặc trƣng đuợc sử dụng để biểu diễn văn bản
Chi tiết các bước thực hiện của phương pháp này: i) Loại bỏ các từ tầm thường (stopword) ii) Đếm tần suất xuất hiện của các từ trong bước 1.
Sử dụng thuật tốn Nạve Bayes để phân loại văn bản
3.4.1 Lý do chọn Nạve Bayes
Naive Bayes (NB) là một phương pháp phân loại dựa trên xác suất, phổ biến trong máy học và nhiều lĩnh vực khác như công cụ tìm kiếm và bộ lọc email Điểm nổi bật của NB là giả định rằng sự xuất hiện của các từ trong văn bản là độc lập, điều này giúp tính toán nhanh chóng và hiệu quả hơn so với các phương pháp phức tạp khác Thuật toán này phù hợp cho việc phân loại văn bản với nhiều chủ đề nhờ vào cài đặt đơn giản, tốc độ thực hiện nhanh và khả năng cập nhật dữ liệu huấn luyện dễ dàng Chính vì những ưu điểm này, Naive Bayes được khuyến nghị sử dụng rộng rãi trong phân loại văn bản.
3.4.2 Ý tưởng và cơng thức Nạve Bayes
Mục tiêu chính là tính xác suất P(wi, xi), tức xác suất văn bản xi thuộc lớp wi Theo định luật Bayes, văn bản xi sẽ được phân loại vào lớp wi có xác suất P(wi, xi) cao nhất.
Công thức để tính P (w i , x i ) nhƣ sau:
Mục tiêu trong phân lớp Nạve Bayes là tìm lớp cĩ giá trị lớn nhất của :
Likelihood: Giả sử rằng các mẫu quan sát độc lập và các đặc trƣng độc lập Với mỗi vector đặc trƣng x i = (x i1 , x i2 , ã ã ã , x id ):
- là số lần đặc trƣng x ik xuất hiện trong lớp
- là tổng số tất cả các đặc trƣng trong lớp
Priori: Xác suất trước được tính như sau:
- là tổng số tất cả các mẫu của tập dữ liệu D
Evidence: Có giá trị nhƣ nhau với tất cả các lớp.
Ứng dụng Nạve Bayes vào bài tốn phân loại
3.5.1 Ý tưởng Ý tưởng: Cơ bản của cách tiếp cận Nạve Bayes là sử dụng xác suất cĩ điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của một văn bản cần phân loại Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện của tất cả các từ trong văn bản đều độc lập với nhau Giả định đó làm cho việc tính toán NB hiệu quả và nhanh chóng hơn các phương pháp khác vì không sử dụng việc kết hợp các từ để đưa ra phán đoán chủ đề Kết quả dự đoán bị ảnh hưởng bởi kích thước tập dữ liệu, chất lƣợng của không gian đặc trƣng…
Mô hình tổng quát việc phân loại:
Hình 3.3 Mô tả bước xây dựng bộ phân lớp
Thuật toán gồm 2 giai đoạn huấn luyện và phân lớp: a) Huấn luyện: tính N(w ij )/C i : Đếm số lần xuất hiện của từ trên văn bản nào đó Đầu vào:
Các vector đặc trưng của văn bản trong tập huấn luyện được biểu diễn dưới dạng ma trận MxN, trong đó M là số lượng vector đặc trưng và N là số đặc trưng của mỗi vector.
- Tập nhãn/lớp cho từng vector đặc trƣng của tập huấn luyện b) Phân lớp: Đầu vào:
- Vector đặc trƣng của văn bản cần phân lớp
- Các giá trị xác suất | và Đầu ra:
- Nhãn/lớp của văn bản cần phân loại
Công thức tính xác suất thuộc phân lớp i khi biết trước mẫu X :
Dựa vào vector đặc trưng của văn bản, ta áp dụng công thức để tính xác suất thuộc từng phân lớp Cuối cùng, chọn lớp có xác suất cao nhất để phân loại văn bản.
Thực tế ta chỉ cần tính | và so sánh Bởi vì là giống nhau đối với tất cả các lớp
Cho tập dữ liệu huấn luyện:
- d5: (“very bad, very bad.”,"spam")
Tập dữ liệu kiểm tra:
Các bước của thuật tốn Nạve Bayes i) Tính xác suất trước (prior probability):
P (spam) = N spam /(N ham + N spam ) = 3/(2 + 3) = 0.60 ii) Sử dụng mô hình ngôn ngữ (unigram language model) - cộng 1 vào (add-one smoothing):
P (very |ham) =(T very|ham + 1)/((T very|ham + 1) + (T good|ham + 1) + (T bad|ham + 1))
P (good|ham) =(T good|ham + 1)/((T very|ham + 1) + (T good|ham + 1) + (T bad|ham + 1))
P ( bad|ham) =(T bad|ham + 1)/((T very|ham + 1) + (T good|ham + 1) + (T bad|ham + 1))
P (very|spam)=(T very|spam + 1)/((T very|spam + 1) + (T good|spam + 1) + (T bad|spam + 1))
P (good|spam) =(T good|spam + 1)/((T very|spam + 1)+(T good|spam + 1)+(T bad|spam + 1))
P (bad|spam) =(T bad|spam + 1)/((T very|spam + 1) + (T good|spam + 1) + (T bad|spam + 1))
P( d 6 |ham) =P(good|ham) × P(bad|ham) × P(very|ham) × P(bad|ham)
P(d 6 |spam) =P(good|spam) × P(bad|spam) × P(very|spam) × P(bad|spam)
= 0.10 × 0.50 × 0.40 × 0.50 = 0.010 iv) Tính xác suất sau (posterior probability):
Phân lớp: vì P(ham|d 6 ) < P(spam|d 6 ) ⇒ d 6 thuộc lớp "spam".
XÂY DỰNG CHƯƠNG TRÌNH
Xây dựng cơ sở dữ liệu
Trong quá trình xây dựng chương trình phân loại văn bản, cần thực hiện các bước như huấn luyện và phân loại văn bản Ngoài ra, còn có các bước quan trọng như tách từ, loại bỏ ký tự đặc biệt, xóa topsword và giữ lại các từ có nghĩa Để thực hiện hiệu quả các bước này, một cơ sở dữ liệu để lưu trữ thông tin là rất cần thiết.
Bảng 4.1 Thuộc tính thực thể
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU KÍCH CỠ
1 ChuyenNganhID Mã chuyên ngành Số nguyên
2 TenChuyenNganh Tên chuyên ngành Chuỗi 100
3 BaiBaoID Mã bài báo Số nguyên
4 TenBaiBao Tên bài báo Chuỗi 100
5 DuongDan Đường dẫn bài báo Chuỗi 100
6 TuID Mã từ đƣợc tách Số nguyên
7 Tu Từ đƣợc tách Chuỗi 50
8 WordWeight Số lần xuất hiện của từ Số nguyên
9 TPTID Mã từ phổ thông Số nguyên
10 TPT Từ phổ thông Chuỗi 50
11 UserID Mã tài khoản Số nguyên
13 FullName Tên đầy đủ Chuỗi 50
14 Sex Giới tính Số nguyên
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU
1 ChuyenNganhID Mã chuyên ngành Số nguyên
2 ChuyenNganh Tên chuyên ngành Chuỗi
Tên thực thể : Chuyên ngành Ý nghĩa : Dùng để lưu trữ tên chuyên ngành
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU
1 UserID Mã tài khoản Số nguyên
2 Pass Mật khẩu tài khoản Chuỗi
3 FullName Tên đầy đủ Chuỗi
4 Sex Giới tính Số nguyên
Tên thực thể : Tài khoản đăng nhập chương trình để quản lý Ý nghĩa : Dùng để lưu trữ thông tin người dùng
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU
1 TuID Mã từ đƣợc tách Số nguyên
2 Tu Từ đƣợc tách Chuỗi
3 WordWeight Số lần xuất hiện Số nguyên
4 BaiBaoID Mã bài báo chứa từ đƣợc tách Số nguyên
Tên thực thể : Từ đƣợc tách Ý nghĩa : Lưu trữ các từ được tách từ bài báo nào và số lần xuất hiện của từ đó trong bài báo đó
Bảng 4.5 Bảng từ phổ thông
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU
1 TPTID Mã từ phổ thông Số nguyên
2 TPT Từ phổ thông Chuỗi
Tên thực thể : Từ phổ thông Ý nghĩa : Dùng để lưu trữ các từ thông dụng thường xuất hiện trong các bài báo
STT TÊN TRƯỜNG DIỄN GIẢI KIỂU DỮ LIỆU
1 BaiBaoID Mã bài báo Số nguyên
2 TenBaiBao Tên bài báo Chuỗi
3 DuongDan Đường dẫn bài báo Chuỗi
4 ChuyenNganhID Mã chuyên ngành Số nguyên
Tên thực thể : Bài báo Ý nghĩa : Dùng để lưu trữ thông tin các bài báo đã được huấn luyện
4.1.3 Mô hình cơ sở dữ liệu
Hình 4.1 Mô hình cơ sở dữ liệu
Bước 1: Chuyển thực thể thành mối quan hệ tương ứng và tạo khóa chính cho quan hệ
Bảng 4.11 Bảng mối quan hệ thực
Tên quan hệ Quan hệ
User User(UserID,Pass,Fullname,Sex)
TuDuocTach TuDuocTach(TuID, Tu, WordWeight)
BaiBao BaiBao(BaiBaoID,TenBaiBao,DuongDan)
Bước 2: Chuyển mối kết hợp thành quan hệ có khóa chính và khóa ngoại
Bảng 4.12 Bảng mối kết hợp của thực thể
Tên quan hệ Quan hệ
User User(UserID,Pass,Fullname,Sex)
TuDuocTach TuDuocTach(TuID, Tu, WordWeight,#BaiBaoID)
BaiBao BaiBao(BaiBaoID,TenBaiBao,DuongDan,#ChuyenNganhID)
4.1 Xây dựng giao diện phân loại văn bản
4.1.1 Lưu đồ phân loại văn bản
Hình 4.2 Lưu đồ phân loại văn bản
(thƣ mục, bài báo) Giai đoạn huấn luyện (tách từ, loại bỏ từ phổ thông, loại bỏ ký tự đặc biệt,…)
Dữ liệu thu đƣợc sau khi huấn luyện
Giao đoạn phân loại ( Sử dụng thuật tốn Nạve Bayes)
Lớp văn bản mới Văn bản đã đƣợc phân loại
Giao diện chương trình được thiết kế với mục đích đem lại sự dễ dàng trong việc huấn luyện cũng nhƣ phân loại văn bản
Hình 4.3 Giao diện chính chương trình
- Button đăng nhập: Dùng để thực hiện thao tác đăng nhập
- Button đăng xuất: Dùng để thực hiện thao tác đăng xuất khỏi hệ thống
- Button đổi mật khẩu: Dùng để thực hiện thao tác đổi mật khẩu
- Button thông tin: Hiển thị thông tin chương tình
- Button trợ giúp: Hiện thị form trợ giúp hướng dẫn sử dụng chương trình
4.1.5 Xây dựng các chức năng i) Huấn luyện văn bản
Hình 4.4 Huấn luyện văn bản
- Combobox Chuyên Ngành: Hiện thị các chuyên ngành
- Button Duyệt file: Tìm bài báo cần huấn luyện
- Button Thực hiện: Thực hiện quá trình huấn luyện các bài báo ở GridView
- Button Xóa: Gỡ bài báo vừa chọn khỏi danh sách chuẩn bị huấn luyện
– Datagrid View: Hiển thị danh sách bài báo đã chọn ii) Phân loại văn bản
Hình 4.5 Phân loại văn bản
- Textbox: Hiện thị đường dẫn file cần phân loại
- Button Duyệt file: Tìm bài báo cần phần loại
- Button Thực hiện: Thực hiện quá trình phân loại
- Textbox : Hiện thị quá trình tính và thông báo văn bản đó thuộc lớp nào iii) Quản lý cơ sở dữ liệu
Chương trình không chỉ huấn luyện và phân loại văn bản mà còn hỗ trợ quản lý thông tin như bài báo, từ phổ thông và chuyên ngành.
Quản lý chuyên ngành: Cho phép thao tác thêm, sửa, xóa chuyên ngành
Hình 4.6 Quản lý chuyên ngành
- Textbox Chuyên Ngành: Cho phép nhập liệu tên chuyên ngành
- Button Thêm:Thực hiện thao tác thêm một chuyên ngành
- Button Xóa: Thực hiện thao tác xoá một chuyên ngành đã có sẵn trong cơ sở dữ liệu
- Datagrid View Chuyên ngành: Hiển thị danh sách các chuyên ngành
Quản lý bài báo: Quản lý các bài báo đã sử dụng trong quá trình huấn luyện
Hình 4.7 Quản lý bài báo
- Datagrid View bài báo: Hiển thị danh sách các bài báo
- Button Xóa: Thực hiện thao tác xoá một bài báo đã huấn luyện trong cơ sở dữ liệu
- Button Xem nội dung bài báo: Xem nội dung bài báo.