TRƢỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN
----------
BÁO CÁO
NGHIÊN CỨU KHOA HỌC
ĐỀ TÀI:
XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI
LIỆU TIẾNG VIỆT
TRẦN THỊ THU THẢO
VŨ THỊ CHINH
BIÊN HÒA, THÁNG 11/2012
TRƢỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN
----------
ĐỀ TÀI:
XÂY DỰNG HỆ THỐNG PHÂN
LOẠI TÀI LIỆU TIẾNG VIỆT
SVTH: TRẦN THỊ THU THẢO
VŨ THỊ CHINH
GVHD:ThS. TẠ NGUYỄN
BIÊN HÒA, THÁNG 11/2012
LỜI NÓI ĐẦU
Trong những năm gần đây, với sự phát triển mạnh mẽ của công nghệ thông tin và nhu
cầu sử dụng Internet của con ngƣời đã làm tăng vọt lƣợng thông tin giao dịch trên Internet.
Vì vậy mà số lƣợng văn bản điện tử tăng nhanh chóng mặt về số lƣợng và chủ đề đặc biệt là
thƣ viện điện tử, tin tức điện tử trên mạng toàn cầu….
Với lƣợng thông tin đồ sộ nhƣ vậy, một yêu cầu lớn đặt ra là làm sao tổ chức và tìm
kiếm thông tin một cách chính xác, có hiệu quả nhất. Phân loại thông tin là một trong những
giải pháp hợp lý cho yêu cầu trên. Nhƣng một thực tế cho thấy là khối lƣợng thông tin quá
lớn, việc phân loại dữ liệu thủ công là điều vô cùng khó khăn. Hƣớng giải quyết cho việc
này là xây dựng một chƣơng trình phân loại thông tin tự động bằng máy tính.
Phân loại văn bản là một vấn đề quan trọng trong lĩnh vực xử lý ngôn ngữ. Nhiệm vụ
của bài toán này là gán các tài liệu văn bản vào nhóm các chủ đề cho trƣớc. Đây là một bài
toán rất thƣờng gặp trong thực tế điển hình nhƣ việc phân nhóm tin tức, phân nhóm các văn
bản theo từng thể loại khác nhau. Tuy nhiên, chúng ta không thể cùng lúc đọc tất cả các tin
tức, bài viết, bài báo hay các tài liệu để rồi phân loại chúng theo đúng mục đích của mình
bởi vì số tài liệu lớn, nếu để đọc hết đƣợc tất cả thì sẽ mất rất nhiều thời gian. Đó là lý do
cần có một hệ thống phân loại tài liệu tiếng Việt.
Chúng em đã chọn thực hiện đề tài “Xây dựng hệ thống phân loại tài liệu tiếng Việt”
nhằm tìm hiểu và thử nghiệm các phƣơng pháp phân loại văn bản áp dụng trên tiếng Việt.
Trong luận văn này, chúng em cũng tìm hiểu một số cách phân loại tài liệu và thử nghiệm
một phƣơng pháp phân loại áp dụng thuật toán Naïve Bayes để xây dựng chƣơng trình dựa
trên tập dữ liệu huấn luyện từ đó hƣớng đến việc phân loại các bài báo khoa học trong lĩnh
vực Công nghệ thông tin nhằm tiết kiệm thời gian và công sức cho các nhà tổ chức trong
các hội thảo chuyên đề.
Việc thực hiện đề tài phân loại tài liệu tiếng Việt của chúng em hy vọng sẽ đem đến
một cách phân loại mới, nhanh chóng và hiệu quả hơn việc phân loại bằng thủ công nhƣ
hiện nay.
LỜI CẢM ƠN
Chúng em xin bày tỏ lòng biết ơn sâu sắc nhất tới Thầy Tạ Nguyễn đã tận tụy hƣớng
dẫn, động viên, giúp đỡ em trong suốt thời gian thực hiện đề tài.
Chúng em xin chân thành cảm ơn quý Thầy Cô trong khoa Công nghệ thông tin đã
truyền đạt những kiến thức quý báu và những kinh nghiệm quý báu cho chúng em trong
những năm học vừa qua.
Chúng con xin nói lên lòng biết ơn đối với Ông Bà, Cha Mẹ luôn là nguồn động viên,
chăm sóc trên bƣớc đƣờng học vấn của chúng con.
Xin chân thành cảm ơn các anh chị và bạn bè đã ủng hộ, giúp đỡ và động viên chúng
em trong thời gian học tập và nghiên cứu.
Mặc dù chúng em đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép
nhƣng chắc chắn chúng em sẽ không tránh khỏi những thiếu sót trong quá trình thực hiện đề
tài. Chúng em kính mong nhận đƣợc sự cảm thông và các ý kiến đóng góp của quý Thầy Cô
và các bạn.
Một lần nữa, xin chân thành cảm ơn.
Sinh viên thực hiện,
Trần Thị Thu Thảo & Vũ Thị Chinh
11/2012
Mục lục
CHƢƠNG 1: TỔNG QUAN ............................................................................................... 1
1.1 Đặt vấn đề .......................................................................................................... 1
1.2 Tổng quan tình hình nghiên cứu trong và ngoài nƣớc....................................... 1
1.2.1 Tổng quan thế giới ........................................................................................ 1
1.2.2 Tổng quan trong nƣớc ................................................................................... 2
1.3 Mục tiêu của luận văn ........................................................................................ 4
1.4 Nội dung thực hiện ............................................................................................ 4
CHƢƠNG 2: CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN BẢN ........................................ 6
2.1 Tổng quát về các phƣơng pháp phân loại văn bản ............................................ 6
2.2 Mô tả bài toán phân loại văn bản ....................................................................... 6
2.3 Các phƣơng pháp phân loại văn bản tiếng Anh................................................. 7
2.3.1 Support vector Machine (SVM) .................................................................... 7
2.3.2 Naïve Bayes (NB) ......................................................................................... 9
2.3.3 Biểu diễn văn bản ........................................................................................ 10
2.3.4 K–Nearest Neighbor (kNN) ........................................................................ 12
2.3.5 Linear Least Square Fit (LLSF) .................................................................. 13
2.3.6 Neural Network (NNet) .............................................................................. 14
2.3.7 Centroid- based vector ................................................................................ 15
2.4 Kết luận chung về các phƣơng pháp phân loại văn bản tiếng Anh ................. 16
2.5 Tách từ trong bài toán phân loại văn bản ........................................................ 17
2.5.1 Khó khăn vƣớng mắc .................................................................................. 18
2.5.2 Các phƣơng pháp tách từ ............................................................................ 19
CHƢƠNG 3: ỨNG DỤNG PHÂN LOẠI BÀI BÁO KHOA HỌC TRONG LĨNH VỰC
CÔNG NGHỆ THÔNG TIN ............................................................................................. 24
3.1 Hiện trạng ........................................................................................................ 24
3.2 Quy trình xử lý phân loại bài báo .................................................................... 25
3.2.1 Tách từ trong văn bản ................................................................................. 26
3.2.2 Loại bỏ các từ tầm thƣờng .......................................................................... 28
3.3 Trích chọn đặc trƣng văn bản .......................................................................... 28
3.3.1 Các ý tƣởng cơ bản ..................................................................................... 28
3.3.2 Phƣơng pháp rút trích đặc trƣng ................................................................. 29
3.3.3 Phƣơng pháp đặc trƣng đề nghị sử dụng..................................................... 30
3.4 Sử dụng thuật toán Naïve Bayes để phân loại văn bản ................................... 32
3.4.1 Lý do chọn Naïve Bayes ............................................................................. 32
3.4.2 Ý tƣởng và công thức Naïve Bayes ............................................................ 32
3.4.3 Ƣớc lƣợng P(X|Y) ....................................................................................... 33
3.4.4 Ƣớc lƣợng P(Y)........................................................................................... 34
3.4.5 Ƣớc lƣợng P(Y|X) ....................................................................................... 34
3.5 Ứng dụng Naïve Bayes vào bài toán phân loại ............................................... 34
3.5.1 Ý tƣởng ....................................................................................................... 34
3.5.1 Hƣớng dẫn cài đặt ....................................................................................... 35
CHƢƠNG 4: XÂY DỰNG CHƢƠNG TRÌNH ................................................................ 39
4.1 Xây dựng cơ sở dữ liệu .................................................................................... 39
4.1.1 Từ điển tiếng việt ........................................................................................ 39
4.1.2 Mô tả thực thể ............................................................................................. 40
4.1 Xây dựng giao diện phân loại văn bản ............................................................ 47
4.1.1 Lƣu đồ phân loại văn bản ...................................................................................... 47
4.1.2 Thiết kế giao diện ................................................................................................... 48
4.1.3 Xây dựng các chức năng ............................................................................. 49
CHƢƠNG 5: THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ............................................. 54
5.1 Ví dụ về chƣơng trình phân loại văn bản ........................................................ 54
5.2 Đánh giá kết quả .............................................................................................. 58
5.2.1 Dữ liệu đầu vào ....................................................................................................... 58
5.2.2 Kết quả thực nghiệm .............................................................................................. 59
5.2.3 Đánh giá kết quả ..................................................................................................... 60
KẾT LUẬN ....................................................................................................................... 62
TÀI LIỆU THAM KHẢO
Mục lục hình
Hình 2.1 Phân chia dữ liệu huấn huyện ............................................................................... 8
Hình 2.2 Biểu diễn văn bản ............................................................................................... 11
Hình 2.3 Hình Kiến trúc mô đun (Modular Architecture)................................................. 15
Hình 2.4 Xây dựng ôtômát âm tiết .................................................................................... 19
Hình 2.5 Xây dựng ôtômát từ vựng ................................................................................... 20
Hình 2.6 Một tình huống nhập nhằng trong phân tách từ ................................................. 21
Hình 3.1 Mô hình phân loại tài liệu tự động ..................................................................... 25
Hình 3.2 Chi tiết giai đoạn huấn luyện .............................................................................. 31
Hình 3.3 Mô tả bƣớc xây dựng bộ phân lớp ...................................................................... 35
Hình 4.1 Mô hình cơ sở dữ liệu ......................................................................................... 45
Hình 4.2 Lƣu đồ phân loại văn bản ................................................................................... 47
Hình 4.3 Giao diện chính chƣơng trình ............................................................................. 48
Hình 4.4 Huấn luyện văn bản ............................................................................................ 49
Hình 4.5 Phân loại văn bản................................................................................................ 50
Hình 4.6 Thông tin chủ đề ................................................................................................ 51
Hình 4.7 Thông tin bài báo ................................................................................................ 52
Hình 5.1 Giao diện phân loại văn bản ............................................................................... 54
Hình 5.2 Kết quả phân tách văn bản .................................................................................. 55
Hình 5.3 Kết quả dựa vào công thức tính trọng số Tf*idf................................................. 56
Hình 5.4 Thống kê kết quả phân loại từ máy .................................................................... 57
Mục lục bảng
Bảng 3.1 Bảng phân lớp .................................................................................................... 38
Bảng 4.1 Thuộc tính thực thể ............................................................................................ 39
Bảng 4.2 Bảng Chuyên ngành ........................................................................................... 40
Bảng 4.3 Bảng tài khoản.................................................................................................... 41
Bảng 4.4 Bảng từ điển ....................................................................................................... 41
Bảng 4.5 Bảng từ phổ thông .............................................................................................. 42
Bảng 4.6 Bảng từ đƣợc tách .............................................................................................. 42
Bảng 4.7 Bảng từ chuyên ngành ........................................................................................ 43
Bảng 4.8 Bảng bài báo ....................................................................................................... 43
Bảng 4.9 Bảng bài báo sau khi phân loại .......................................................................... 44
Bảng 4.10 Bảng biến tạm .................................................................................................. 44
Bảng 4.11 Bảng mối quan hệ thực thể............................................................................... 46
Bảng 4.12 Bảng mối kết hợp của thực thể......................................................................... 46
Bảng 5.1 Bảng số liệu xử lý theo con ngƣời ..................................................................... 58
Bảng 5.2 Bảng kết quả chƣơng trình phân loại văn bản tiếng Việt ................................... 59
Bảng 5.3 Tỷ lệ(%) phân loại văn bản ................................................................................ 60
1
CHƢƠNG 1: TỔNG QUAN
1.1 Đặt vấn đề
Trong thời đại bùng nổ công nghệ thông tin hiện nay, phƣơng thức sử dụng giấy tờ
trong giao dịch đã dần đƣợc số hoá chuyển sang các dạng văn bản lƣu trữ trên máy tính
hoặc truyền tải trên mạng. Bởi nhiều tính năng ƣu việt của tài liệu số nhƣ: cách lƣu trữ
gọn nhẹ, thời gian lƣu trữ lâu dài, tiện dụng trong trao đổi đặc biệt là qua Internet, dễ dàng
sửa đổi… nên ngày nay, số lƣợng văn bản số tăng lên một cách chóng mặt đặc biệt là trên
world-wide-web. Cùng với sự gia tăng về số lƣợng văn bản, nhu cầu tìm kiếm văn bản
cũng tăng theo. Với số lƣợng văn bản đồ sộ thì việc phân loại văn bản tự động là một nhu
cầu bức thiết.
Tại sao phải phân loại văn bản tự động? Việc phân loại văn bản sẽ giúp chúng ta
tìm kiếm thông tin dễ dàng và nhanh chóng hơn rất nhiều so với việc phải bới tung mọi
thứ trong ổ đĩa lƣu trữ để tìm kiếm thông tin. Mặt khác, lƣợng thông tin ngày một tăng lên
đáng kể, việc phân loại văn bản tự động sẽ giúp con ngƣời tiết kiệm đƣợc rất nhiều thời
gian và công sức.
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 đó.
1.2 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 luôn đƣợc các thƣ viện và cơ quan thông tin trên thế giới hết
sức quan tâm. Phân loại tài liệu là một khâu công tác quan trọng giúp cho việc kiểm soát
thƣ mục, góp phần thúc đẩy việc khai thác, trao đổi thông tin trong phạm vi quốc gia và
quốc tế. Trên thế giới và một số thƣ viện lớn ở Việt Nam, phân loại đƣợc áp dụng sâu
rộng trong việc tổ chức kho mở và tra cứu thông tin.
1.2.1 Tổng quan thế giới
Theo Yang & Xiu, 1999, “việc phân loại văn bản tự động là việc gán các nhãn
phân loại lên một văn bản mới dựa trên mức độ tƣơng tự của văn bản đó so với các văn
2
bản đã đƣợc gán nhãn trong tập huấn luyện”.
Từ trƣớc đến nay, phân loại văn bản tự động trong tiếng Anh đã có rất nhiều
công trình nghiên cứu và đạt đƣợc kết quả đáng khích lệ. Dựa trên các thống kê của
Yang & Xiu (1999)[6] và nghiên cứu của chúng em, một số phƣơng pháp phân loại
thông dụng hiện nay là: Support Vector Machine -Joachims, 1998[4], k-Nearest
Neighbor -Yang, 1994, Linear Least Squares Fit -Yang and Chute, 1994[7] Neural
Network -Wiener et al, 1995, Naïve Bayes -Baker and Mccallum, 2000, Centroid- based
- Shankar and Karypis, 1998. Các phƣơng pháp trên đều dựa vào xác suất thống kê
hoặc thông tin về 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 mỗi phƣơng pháp sẽ đƣợc chúng em trình bày ở 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, áp dụng công thức
khác nhau, tuy nhiên, nhìn một cách tổng quan thì các phƣơng pháp đó đều phải thực
hiện một số bƣớc chung nhƣ sau: đầu tiên, mỗi phƣơng pháp sẽ dựa trên các thông tin về
sự xuất hiện của từ trong văn bản (ví dụ tần số, số văn bản chứa từ…) để biểu diễn văn
bản thành dạng vector. Sau đó, tuỳ từng phƣơng pháp mà ta sẽ áp dụng công thức và
cách thức tính toán khác nhau để thực hiện việc phân loại.
Đối với tiếng Anh, các kết quả trong lĩnh vực này rất khả quan, còn đối với tiếng
Việt, các công trình nghiên cứu về phân loại văn bản gần đây đã có một số kết quả ban
đầu nhƣng vẫn còn nhiều hạn chế. Nguyên nhân là ngay ở bƣớc đầu tiên, chúng ta đã
gặp khó khăn trong việc xử lý văn bản để rút ra tần số xuất hiện của từ. Trong khi đó, để
phân loại văn bản thì có thể nói bƣớc đầu tiên là quan trọng nhất bởi vì nếu ở bƣớc tách
từ đã sai thì việc phân loại hầu nhƣ không thể thành công đƣợc. Phần trình bày tiếp theo
sẽ cho chúng ta biết những thách thức đặt ra trong việc tách từ tiếng Việt, cũng nhƣ
những ứng dụng thú vị của nó.
1.2.2 Tổng quan trong nƣớc
Vấn đề phân loại văn bản tiếng Việt đƣợc nhiều cơ sở nghiên cứu trong cả nƣớc
quan tâm trong những năm gần đây. Một số công trình nghiên cứu cũng đạt đƣợc những
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 đã đƣợc nghiên cứu bao
gồm: hƣớng tiếp cận bài toán phân loại bằng lý thuyết đồ thị[10], cách tiếp cận sử dụng
3
lý thuyết tập thô [9], cách tiếp cận thống kê [12], cách tiếp cận sử dụng phƣơng pháp học
không giám sát và đánh chỉ mục[14, 15]. Nhìn chung, những cách tiếp cận này đều cho
kết quả tốt.Tuy vậy để đi đến những triển khai khả thi thì vẫn cần đẩy mạnh nghiên cứu
nhƣng vẫn dựa trên hƣớng nghiên cứu trên. Một trong những khó khăn trong việc áp
dụng những thuật toán phân loại văn bản vào tiếng Việt là xây dựng đƣợc tập hợp từ
vựng của văn bản. Vấn đề này liên quan tới việc phân tách một câu thành các từ một cách
chính xác. Có thể kể đến công trình nghiên cứu của GS.TSKH Hoàng Kiếm và TS. Đỗ
Phúc[13]
Đối với tiếng Anh, “từ là một nhóm các ký tự có nghĩa đƣợc tách biệt với nhau
bởi khoảng trắng trong câu” (Webster Dictionary), do vậy việc tách từ trở nên rất đơn
giản. Trong khi đối với tiếng Việt, ranh giới từ không đƣợc xác định mặc định là
khoảng trắng mà tùy thuộc vào ngữ cảnh dùng câu tiếng Việt. Ví dụ các từ trong tiếng
Anh là “book”, “cat”, “stadium” thì trong tiếng Việt là “quyển sách”, “con mèo”, “sân
vận động”. Vấn đề trên thực sự đƣa ra một thách thức đối với chúng ta - những ngƣời
làm tin học.
Thách thức nào cũng có cái hay của nó. Khi chúng ta giải quyết đƣợc việc tách
từ một cách chính xác, thì kết quả mà chúng ta đạt đƣợc là bƣớc phát triển trong các
hƣớng nghiên cứu có liên quan đến việc xử lý ngôn ngữ tự nhiên nhƣ: phân loại văn bản,
dịch tự động, kiểm tra lỗi chính tả, kiểm tra ngữ pháp… Đây là các ứng dụng rất cần
thiết đối với con ngƣời và là mục tiêu của con ngƣời đang hƣớng tới.
Theo Đinh Điền (2004)[8], các phƣơng pháp tách từ sau có nguồn gốc từ tiếng
Hoa đã đƣợc thử nghiệm trên tiếng Việt: Maximum Matching: forward/backward hay
còn gọi LRMM (Left Right Maximum Matching); 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 (Weighted finite-state
Transducer); giải thuật dựa trên nén (compression);….Theo các cách tiếp cận trên, điều
kiện quan trọng cần có là một hệ thống từ điển và ngữ liệu đánh dấu đầy đủ, chuẩn xác.
Một từ điển hay một tập ngữ liệu không hoàn chỉnh sẽ làm giảm hiệu suất của thuật
toán.
Gần đây, một phƣơng pháp tách từ mới đƣợc giới thiệu có ƣu điểm là không cần
4
đến tập dữ liệu hay từ điển để lấy thông tin thống kê hay trọng số của từ, đó là phƣơng
pháp Internet and Genetics Algorithm-based Text Categorization (IGATEC) của H.
Nguyen et al (2005)[1]. Điểm sáng tạo của thuật toán là kết hợp thuật toán di truyền
với việc trích xuất thông tin thống kê từ Internet thông qua một công cụ tìm kiếm (ví
dụ nhƣ Google) thay vì lấy từ tập dữ liệu nhƣ các phƣơng pháp trƣớc.
Để thực hiện bƣớc tách từ trong luận văn này chúng em dựa trên ý tƣởng của mô
hình N-gram là chia văn bản ra thành nhiều chuỗi, mỗi chuỗi gồm hai, ba ký tự trở lên
với tập dữ liệu xây dƣng thô và dữ liệu đã đƣợc phân loại sẵn.
1.3 Mục tiêu của luận văn
Tìm hiểu thuật toán Naï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 tiếng Việt, bƣớc đầu ứng dụng vào việc phân loại các bài báo khoa học điện tử thuộc
lĩnh vực CNTT trong các hội thảo nhƣ: Hội thảo Fair, hội thảo @ Cần Thơ.
1.4 Nội dung thực hiện
Bƣớc 1:
-
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ài báo, luận văn thuộc chuyên ngành công nghệ thông tin trong
đó:
o 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
o Tập dùng để kiểm thử là tập hợp các bài báo đã đƣợc phân loại sẵn
dùng để kiểm thử chƣơng trình lấy kết quả thống kê khi hoàn thành
chƣơng trình
Bƣớc 2:
-
Tìm hiểu các phƣơng pháp tách từ hiện nay để chọn ra phƣơng pháp phù
hợp nhất
-
Tách từ, xóa những stop word dựa trên phƣơng pháp đã chọn trên tập dữ
liệu tìm đƣợc
5
Bƣớc 3:
-
Tìm hiểu các phƣơng pháp tính trọng số của từ, chọn lựa phƣơng pháp phù
hợp.Xây dựng bộ từ điển các từ trong lĩnh vực Công nghệ thông tin kèm
theo trọng số.
Bƣớc 4:
-
Rút trích đặc trƣng ƣớc lƣợng xác suất theo phƣơng pháp Naïve Bayes vào
chƣơng trình phân loại văn bản tiếng Việt
Bƣớc 5:
-
Thử nghiệm và thống kê kết quả xử lý khi hoàn thành chƣơng trình dựa trên
tập dữ liệu kiểm thử đã đƣợc phân loại sẵn.
-
Nhận xét và đánh giá
6
CHƢƠNG 2: CÁC PHƢƠNG PHÁP PHÂN
LOẠI VĂN BẢN
2.1 Tổng quát về các phƣơng pháp phân loại văn bản
Hiện nay phân loại văn bản tự động là một lĩnh vực đƣợc chú ý nhất trong những
năm gần đây. Để phân loại văn bản ngƣời ta sử dụng nhiều cách tiếp cận khác nhau nhƣ:
dựa trên từ khóa, dựa trên ngữ nghĩa các từ có tần số xuất hiện cao hay trọng số của từ, tập
dữ liệu, mô hình Maximum Entropy... Tiếng Anh là ngôn ngữ đƣợc nghiên cứu sớm nhất và
đã đạt đƣợc kết quả tốt. Rất nhiều phƣơng pháp đã đƣợc áp dụng nhƣ: mô hình hồi quy phân
loại dựa trên láng riềng gần nhất k-nearest neighbors phƣơng pháp dựa trên xác suất Naïve
Bayes, cây quyết định học luật quy nạp, máy vector hỗ trợ Support vector Machine, mô
hình cực đại entropy. Hiệu quả của các phƣơng pháp là rất khác nhau ngay cả khi chúng
đƣợc áp dụng trong tiếng Anh. Việc đánh giá gặp nhiều khó khăn do thiếu các tập dữ liệu
huấn luyện chuẩn. Chƣơng hai này để giới thiệu các thuật toán đƣợc sử dụng rộng rãi và so
sách sự giống và khác nhau giữa các phƣơng pháp.
2.2 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 chi 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.
7
Vì vậy, nhiệm vụ đầu tiên cần phải làm là biểu diễn văn bản dƣới dạng các từ, cụm
từ và các câu có chọn lọc. Lọc bỏ những từ, cụm từ và câu không có nghĩa hay không có tác
động tích cực tới việc phân loại.
Bƣớc tiếp theo là xác định các ràng buộc cho bài toán phân loại. Các ràng buộc
này sẽ đƣợc lấy ra từ tập dữ liệu huấn luyện. Mỗi ràng buộc thể hiện một đặc trƣng của dữ
liệu huấn luyện. Khi ta có đƣợc 1 bài báo, khi đó ta dựa vào một số đặc điểm hay thuộc
tính nào đó của bài báo để tăng khả năng phân loại . Các đặc điểm của bài báo nhƣ: tiêu
đề, nội dung… Càng nhiều những thông tin nhƣ vậy xác suất phân loại đúng càng lớn, tất
nhiên còn phụ thuộc vào kích thƣớc của tập mẫu huấn luyện.
Việc tính toán xác suất sẽ dựa vào công thức Naïve Bayes, từ xác suất thu đƣợc ta
đem so sánh với một giá trị ngƣỡng t nào đó mà ta xem là ngƣỡng để phân loại bài báo thuộc
thể loại nào.
2.3 Các phƣơng pháp phân loại văn bản tiếng Anh
2.3.1 Support vector Machine (SVM)
SVM - viết tắt tên tiếng Anh support vector machine là phƣơng pháp đƣợc Vapnik
giới thiệu vào năm 1995 [3] nhằm giải quyết vấn đề nhận dạng mẫu 2 lớp sử dụng nguyên lý
cực tiểu hóa rủi ro có cấu trúc.
Ý tƣởng
Cho trƣớc tập huấn luyện đƣợc biểu diễn trong không gian vector trong đó mỗi văn
bản là một điểm, phƣơng pháp tìm ra một siêu mặt phẳng h quyết định tốt nhất có thể chia
các điểm trên không gian này thành 2 lớp riêng biệt tƣơng ứng lớp + và lớp -. Hiệu quả xác
định siêu mặt phẳng này đƣợc quyết định bởi khoảng cách của điểm gần mặt phẳng nhất của
mỗi lớp. Khoảng cách càng lớn thì mặt phẳng quyết định càng tốt đồng nghĩa với việc phân
loại càng chính xác và ngƣợc lại. Mục đích cuối cùng của phƣơng pháp là tìm đƣợc khoảng
cách biên lớn nhất.
8
Hình 2.1 Phân chia dữ liệu huấn huyện
Công thức
Phƣơng trình siêu mặt phẳng chứa vector d i nhƣ sau:
di *wb 0
Đặt
1, d i .w b 0
h(d i ) sign(d i .w b)
1, d i .w b 0
Nhƣ vậy h( d i ) biểu diễn sự phân lớp của d i vào 2 lớp + và lớp -. Gọi yi = {±1}, yi = +1
văn bản d i thuộc lớp +, yi = -1 văn bản d i thuộc lớp -. Để có siêu mặt phẳng h ta đi giải bài
toán:
Tính Min|| w || với w và b thoản mãn điều kiện:
i 1, n : yi (sign(d i .w b)) 1
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 đặc biệt trong phƣơng pháp SVM là siêu mặt phẳng h chỉ phụ thuộc vào
các vector hỗ trợ. Khác so với các phƣơng pháp khác vì các phƣơng pháp khác có kết quả
phân loại phụ thuộc vào toàn bộ dữ liệu. Khi dữ liệu có sự thay đổi thì kết quả cũng thay
đổi.
9
2.3.2 Naïve Bayes (NB)
NB là phƣơng pháp phân loại dựa vào xác suất đƣợc sử dụng rộng rãi trong lĩnh
vực máy học và nhiều lĩnh vực khác nhƣ trong các công cụ tìm kiếm, các bộ lọc mail
[Sahami et al, 1998]
Ý tƣởng
Ý tƣởng cơ bản của cách tiếp cận Naïve Bayes (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 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. Nhƣ thế NB không tận dụng đƣợc sự phụ thuộc của
nhiều từ vào một chủ đề cụ thể. 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ới độ phức tạp theo số mũ vì nó không sử dụng việc kết
hợp các từ để đƣa ra phán đoán chủ đề.
Công thức
Mục đích chính là làm sao tính đƣợc xác suất Pr (Cj, d’), xác suất để văn bản
d’nằm trong lớp Cj. Theo luật Bayes, văn bản d’ sẽ đƣợc gán vào lớp Cj nào có xác suất
Pr(Cj, d’) cao nhất .
Công thức để tính Pr (Cj, d’) nhƣ sau:
d'
PrC .
Prw i | C j
j
i 1
H BAYES d ' argmax
d'
Prc'. Prw i | C'
i 1
c' c
c j C
Với:
-
TF(wi, d’) là số lần xuất hiện của từ wi trong văn bản d’
-
|d’| là số lƣợng các từ trong văn bản d’
-
wi là một từ trong không gian đặc trƣng F với số chiều là |F|
-
Pr(Cj) đƣợc tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp tƣơng
ứng trong tập dữ liệu huấn luyện
10
Pr C j
Pr w i | C j
Cj
C
Cj
C'
C' C
1 TF w i , c j
F
TF w ' , c j
w' F
Ngoài ra còn có các phƣơng pháp NB khác có thể kể ra nhƣ ML Naïve Bayes,
MAP Naïve Bayes, Expected Naïve Bayes. Nói chung Naïve Bayes là một công cụ rất
hiệu qủa trong một số trƣờng hợp. Kết qủa có thể rất xấu nếu dữ liệu huấn luyện nghèo
nàn và các tham số dự đoán (nhƣ không gian đặc trƣng) có chất lƣợng kém. Nhìn chung
đây là một thuật toán phân loại tuyến tính thích hợp trong phân loại văn bản nhiều chủ đề.
NB có ƣu điểm là cài đặt đơn giản, tốc độ thực hiện thuật toán nhanh, dễ dàng cập nhật dữ
liệu huấn luyện mới và có tính độc lập cao với tập huấn luyện.
2.3.3 Biểu diễn văn bản
Bƣớc đầu tiên của các phƣơng pháp phân loại văn bản là chuyển việc mô tả văn bản
dùng chuỗi ký tự thành dạng mô tả khác phù hợp với các thuật toán. Hầu hết các thuật toán
đều sử dụng cách biểu diễn theo vector đặc trƣng, khác nhau chủ yếu ở việc lựa chọn không
gian đặc trƣng. Cụ thể với mô hình cực đại entropy [11], thuật toán IIS chỉ có thể tính toán
đƣợc các tham số dựa trên các vector đặc trƣng. Vậy vector đặc trƣng là gì?
Mỗi vector đặc trƣng di đại diện cho một văn bản tƣơng ứng trong không gian các
từ w: di (TF(w1), TF(w2), ..., TF(wn)). Trong đó: TF(wi) là số lần xuất hiện của từ wi trong
chính văn bản đó ( di ); n là số chiều của không gian. Để không phụ thuộc vào chiều dài văn
bản vector đặc trƣng đƣợc chuẩn hóa nhƣ sau:
11
di (
TF ( wn )
TF ( w1 )
TF ( w2 )
,
,...,
)
2
2
TF ( wi ) TF ( wi )
TF 2 ( wi )
Hình 2.2 Biểu diễn văn bản
Trong thực tế để cải thiện tốc độ và kết quả ngƣời ta sử dụng IDF(w i) hay
TFIDF(w i) thay cho TF(wi) (trong luận văn sử dụng TFIDF):
IDF ( wi ) log(
m
)
DF ( wi )
TFIDF (wi ) TF (wi ).IDF (wi )
Trong đó:
-
m chính là số văn bản huấn luyện
-
DF(wi) là số văn bản có chứa từ wi
Biểu diễn văn bản theo các vector đặc trƣng sẽ nảy sinh các vấn đề nhƣ: cần phải lựa
chọn bao nhiêu từ để biểu diễn cho văn bản đó?. Và làm thế nào để lựa chọn đƣợc những từ
đó? Ở đây xin giới thiệu hƣớng tiếp cận sử dụng Information Gain [Yang & Petersen,
1997]. Phƣơng pháp sử dụng độ đo Mutual Information(MI) để chọn ra tập đặc trƣng con f
gồm những từ có giá trị MI cao nhất.
12
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
-
Việc kết hợp những đặc trƣng độc lập thƣờng không mang lại kết quả.
-
Vector di có nhiều giá trị 0 do không có đặc trƣng trong văn bản di.
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.
Ý 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.
Công thức
Trọng số của chủ đề cj đối với văn bản x đƣợc tính nhƣ sau:
W x, c j
sim x , . y , c j b j
d i d i
di {kNN}
Trong đó:
y (di, c) thuộc {0,1}, với:
-
y = 0: văn bản di không thuộc về chủ đề cj
- Xem thêm -