Thạc Sĩ Nghiên cứu một số phương pháp phân lớp cải tiến, ứng dụng vào hệ truy tìm văn bản

Luận văn thạc sĩ
Đề tài: NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP CẢI TIẾN, ỨNG DỤNG VÀO HỆ TRUY TÌM VĂN BẢN

MỤC LỤC
Trang
MỤC LỤC . i
DANH MỤC CÁC BẢNG iii
DANH MỤC CÁC HÌNH VẼ . iv
MỞ ĐẦU . 1
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP VĂN BẢN . 4
1.1 Giới thiệu bài toán phân lớp văn bản 4
1.1.1 Phân lớp văn bản dựa trên cách tiếp cận hệ chuyên gia . 4
1.1.2 Phân lớp văn bản dựa trên cách tiếp cận máy học . 5
1.2 Phương pháp tách từ 8
1.2.1 Các đặc điểm của văn bản tiếng Việt 9
1.2.2 Phương pháp tách từ bằng cách xây dựng các ôtômát . 10
1.3 Phương pháp biểu diễn văn bản 15
1.3.1 Các kỹ thuật trích chọn đặc trưng của văn bản . 15
1.3.2 Phương pháp biểu diễn văn bản bằng mô hình không gian vector . 18
1.4 Phương pháp đánh giá hiệu quả phân lớp . 20
CHƯƠNG 2: CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN PHỔ BIẾN 22
2.1 Thuật toán K-trung bình (K-means) 22
2.2 Thuật toán cây quyết định (Decision tree) 24
2.3 K-láng giềng gần nhất (K-Nearest Neighbor) . 27
2.4 Support Vector Machines (SVM) . 31
2.4.1 Giới thiệu 31
2.4.2 Bài toán và cách giải quyết . 32
2.4.3 Hàm nhân Kernel 38
2.4.4 Thuật toán huấn luyện Sequential Minimal Optimization (SMO) . 38
2.5 Đánh giá các thuật toán phân lớp văn bản phổ biến 39
CHƯƠNG 3: CÁC THUẬT TOÁN CẢI TIẾN DỰA TRÊN PHƯƠNG PHÁP
PHÂN LỚP VĂN BẢN SUPPORT VECTOR MACHINES . 42
-ii-3.1 Fuzzy Support Vector Machines (FSVM) . 42
3.1.1 Bài toán và cách giải quyết . 42
3.1.2 Hàm thành viên . 44
3.1.3 Thuật toán huấn luyện Kernel-Adatron 47
3.2 Support Vector Machines Nearest Neighbor (SVM-NN) 47
3.2.1 Ý tưởng của thuật toán SVM-NN . 48
3.2.2 Thuật toán SVM-NN 48
3.3 Chiến lược phân lớp đa lớp . 51
3.3.1 Chiến lược One-against-Rest (OAR) 51
3.3.2 Chiến lược One-against-One (OAO) 53
3.3.3 Phân lớp đa lớp mờ (Fuzzy OAO) 57
3.4 Đánh giá các thuật toán phân lớp cải tiến 59
CHƯƠNG 4: TỔNG QUAN VỀ BÀI TOÁN TRUY TÌM VĂN BẢN . 61
4.1 Hệ truy tìm văn bản . 61
4.2 Các mô hình của hệ truy tìm văn bản 62
4.3 Hệ truy tìm văn bản theo mô hình không gian vector (VSM) . 65
4.3.1 Giới thiệu mô hình VSM 65
4.3.2 Số hóa văn bản theo mô hình VSM 66
4.3.3 Ma trận biểu diễn tập văn bản theo mô hình VSM . 66
4.3.4 Truy vấn văn bản theo mô hình VSM 68
CHƯƠNG 5: XÂY DỰNG THỬ NGHIỆM HỆ PHÂN LỚP VÀ TRUY TÌM VĂN
BẢN 70
5.1. Phân hệ phân lớp văn bản . 72
5.1.1 Thiết kế phân hệ phân lớp văn bản . 72
5.1.2 Module lựa chọn các từ đặc trưng và biểu diễn văn bản tiếng Việt . 73
5.1.3 Module phân lớp 2 lớp sử dụng SVM-NN . 73
5.1.4 Phân lớp đa lớp . 75
5.1.5 Cài đặt phân hệ phân lớp văn bản . 76
5.1.6 Kết quả thử nghiệm của phân hệ phân lớp văn bản 79
-iii-5.2. Phân hệ truy tìm văn bản VSM 80
5.2.1 Thiết kế phân hệ truy tìm văn bản VSM 80
5.2.2 Cài đặt phân hệ truy tìm văn bản VSM 84
5.2.3 Đánh giá kết quả cải tiến của phân hệ truy tìm văn bản VSM . 86
CHƯƠNG 6: KẾT LUẬN 88
6.1 Đánh giá kết quả 88
6.2 Hướng phát triển 89
TÀI LIỆU THAM KHẢO . 90

MỞ ĐẦU
Ngày nay, việc tìm kiếm thông tin nói chung cũng như thông tin văn bản nói
riêng có vai trò rất quan trọng trong mọi lĩnh vực hoạt động của con người, nó trở
đã thành một nhu cầu thiết yếu không thể thiếu. Với sự xuất hiện của internet thì
khối lượng thông tin văn bản trên mạng ngày càng tăng, hình thành một kho văn
bản khổng lồ, làm cho việc tìm kiếm những thông tin văn bản cần thiết, hữu ích thì
ngày càng trở nên khó khăn hơn.
Xuất phát từ thực tế đó, đã có một số nghiên cứu xây dựng các hệ truy tìm
văn bản theo các mô hình khác nhau, trong đó hệ truy tìm văn bản theo mô hình
không gian vector được đánh giá là có nhiều ưu điểm nhất. Tuy nhiên, đối với một
hệ truy tìm văn bản theo mô hình không gian vector cơ bản, việc xử lý truy tìm phải
thực hiện trên toàn bộ tập văn bản. Điều này làm mất rất nhiều thời gian xử lý, tốc
độ truy tìm sẽ chậm, đồng thời phải tiêu tốn nhiều không gian lưu trữ, tài nguyên
tính toán, nếu tập văn bản lớn (hoặc số lượng từ đặc trưng lớn).
Bài toán đặt ra là làm thế nào để xây dựng một hệ thống tự động phân lớp và
phục vụ truy tìm thông tin văn bản theo mô hình không gian vector VSM có cải tiến
so với hệ thống truy tìm theo mô hình không gian vector VSM cơ bản, để việc truy
tìm được nhanh chóng và hiệu quả hơn.
Hướng tiếp cận giải quyết như sau: Việc cải tiến hệ thống truy tìm văn bản
theo mô hình không gian vector VSM được thực hiện bằng cách kết hợp sử dụng
các kết quả phân lớp văn bản trên kho văn bản trước khi thực hiện các kỹ thuật xử
lý truy tìm. Kết quả của việc cải tiến này là phân hệ truy tìm văn bản sẽ cải thiện
đáng kể tốc độ, hiệu quả truy tìm vì không phải thực hiện xử lý truy tìm trên toàn bộ
kho văn bản mà chỉ thực hiện truy tìm trên một hoặc vài nhóm văn bản có liên quan
với câu truy vấn.
Hiện tại, đã có một số nghiên cứu về kỹ thuật phân lớp văn bản cũng như về
kỹ thuật truy tìm thông tin văn bản. Luận văn này nhằm mục đích tìm hiểu các kỹ
-2-thuật trên và áp dụng vào việc xây dựng thử nghiệm một hệ thống tự động phân lớp
và phục vụ truy tìm thông tin văn bản thực tế.
Đối với các kỹ thuật phân lớp văn bản, luận văn tìm hiểu cụ thể kỹ thuật
phân lớp văn bản Support Vector Machines (SVM) do kết quả phân lớp rất tốt của
phương pháp này theo các đề tài đã nghiên cứu trước đây. Ý tưởng chính của SVM
là tìm một siêu phẳng “tốt nhất” trong không gian n-chiều để phân chia các điểm dữ
liệu (văn bản) sao cho các điểm dữ liệu thuộc 2 lớp khác nhau nằm ở 2 phía của siêu
phẳng. Luận văn cũng nghiên cứu các thuật toán phân lớp văn bản cải tiến dựa trên
kỹ thuật SVM là thuật toán Fuzzy SVM cho phép loại bỏ các dữ liệu nhiễu trong
quá trình huấn luyện và cải thiện độ chính xác của quá trình phân lớp, nghiên cứu
và cài đặt áp dụng thuật toán SVM Nearest Neighbor với việc kết hợp ý tưởng của
thuật toán K-Nearest Neighbor và thuật toán SVM để cải thiện hiệu quả phân lớp.
Đồng thời luận văn còn nghiên cứu và cài đặt áp dụng các chiến lược phân lớp văn
bản đa lớp OAR (One - against - Rest), OAO (One - against - One) và kỹ thuật cải
tiến việc phân lớp đa lớp này là phân lớp đa lớp mờ Fuzzy OAO (Fuzzy One -against - One).
Đối với các kỹ thuật phục vụ truy tìm văn bản, luận văn tìm hiểu sử dụng mô
hình truy tìm văn bản theo mô hình không gian vector VSM (Vector Space Model).
Nguyên lý hoạt động cốt lõi của hệ truy tìm văn bản VSM là tự động hóa quy trình
tìm kiếm các văn bản có liên quan bằng cách tính độ đo tương tự giữa câu truy vấn
và các văn bản đó.
Từ kết quả nghiên cứu trên, các kỹ thuật phân lớp và phục vụ truy tìm văn
bản sẽ được cài đặt áp dụng để xây dựng thử nghiệm một hệ thống tự động phân lớp
và phục vụ truy tìm thông tin văn bản thực tế theo mô hình không gian vector VSM
có cải tiến so với hệ thống truy tìm theo mô hình VSM cơ bản.
-3-Nội dung luận văn gồm 6 chương:
- Chương 1: Tổng quan về bài toán phân lớp văn bản.
- Chương 2: Các phương pháp phân lớp văn bản truyền thống.
- Chương 3: Các thuật toán cải tiến dựa trên phương pháp phân lớp văn bản
Support Vector Machines.
- Chương 4: Tổng quan về bài toán truy tìm văn bản.
- Chương 5: Xây dựng thử nghiệm hệ phân lớp và truy tìm văn bản.
- Chương 6: Kết luận.

CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP VĂN BẢN
1.1 Giới thiệu bài toán

TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Nguyễn Kim Anh, Nguyễn Thị Kim Ngân (2006), “Phân lớp văn bản
tiếng Việt sử dụng phương pháp Support Vector Machines”, Khoa
Công nghệ thông tin, ĐHBK Hà Nội.
[2] Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê Hồng Phương (2003),
“Sử dụng bộ gán nhãn từ loại xác suất QTAG cho văn bản tiếng Việt”,
Kỷ yếu Hội thảo ICT.rda’03, trang 22-23.
[3] Trang Nhật Quang (2007), “Đề xuất một công cụ hỗ trợ thu thập và
phân loại thông tin tiếng Việt trên internet”, Luận văn Thạc sĩ, Đại học
Khoa học Tự nhiên TP.HCM, TP.HCM.
Tiếng Anh
[4] Enrico Blanzieri, Anton Bryl (2007), “Evaluation of the Highest
Probability SVM Nearest Neighbor Classifier With Variable Relative
Error Cost”, University of Trento, Italy.
[5] Enrico Blanzieri, Anton Bryl (2007), “Instance-Based Spam Filtering
Using SVM Nearest Neighbor Classifier”, University of Trento, Italy.
[6] Li-Cheng Jin (2004), “Application of Fuzzy Support Vector Machines in
Medical Engineering and Bioinformatics”, Master Thesis, Institute of
Electronics and Information Engineering National Kaohsiung
University of Applied Sciences, Taiwan.
[7] Shigeo Abe and Takuya Inoue (2002), “Fuzzy Support Vector
Machines for Multiclass Problems”, ESANN‟2002 proceedings, pp.
113-118.
[8] Shigeo Abe and Takuya Inoue (2001), “Fuzzy Support Vector
Machines for Pattern Classification”, In Proceeding of International
-91-Joint Conference on Neural Networks (IJCNN ‟01), volume 2, pp.
1449-1454.
[9] Tsui-Feng Hu (2004), “Fuzzy Correlation and Support Vector Learning
Approach to Multi-Categorization of Documents”, Master Thesis,
Institute of Information Management I-Shou University, Taiwan.
[10] T.Joachims (1998), “Text Categorization with Support Vector
Machines: Learning with Many Relevant Features” in Proceedings of
ECML-98, 10
th
European Conference on Machine Learning, number
1398, pp. 137–142.
[11] Xiufeng Jiang, Zhang Yi and Jian Cheng Lv (2006), “Fuzzy SVM with
a new fuzzy membership function”, Neural Computing and
Applications, Volume 15(3), pp. 268-276.
[12] Yiming Yang, Jan O. Pedersen (1997), "A comparative Study on
Feature Selection in Text Categorization", Proceedings of {ICML}-97,
14th International Conference on Machine Learning, pp. 412-420.