Thạc Sĩ Một số thuật toán phân lớp tiêu biểu và Phương pháp biểu diễn văn bản dựa trên các khái niêm mờ

TÓM TẮT
Biểu diễn Văn bản là một trong những công đoạn quan trọng nhất và được quan
tâm đầu tiên trong các vấn đề xử lý văn bản. Nó có ảnh hưởng rất lớn đến các bài toán tìm
kiếm văn bản, phân lớp, phân cụm hay tóm tắt văn bản Khóa luận này trình bày và
nghiên cứu một phương pháp biểu diễn Văn bản mới dựa trên cơ sở lý thuyết tập mờ và áp
dụng vào bài toán phân lớp văn bản. Nội dung của khóa luận tập trung vào các vấn đề
sau:
1. Trình bày một số phương pháp biểu diễn Văn bản thông thường, trong đó, khóa
luận đi sâu vào cách biểu diễn theo mô hình vector, tức mỗi Văn bản sẽ được biểu diễn
như một vector có các thành phần là các từ khóa có mặt hoặc không có mặt trong văn bản.
Sau đó, khóa luận tìm hiểu phương pháp biểu diễn Văn bản trong máy tìm kiếm.
2. Trình bày về lý thuyết tập mờ, và đề cập một cách biểu diễn Văn bản mới dựa
trên các khái niệm mờ. Từ đó đề xuất hướng giải quyết khi xuất hiện các từ đồng nghĩa
trong văn bản.
3. Tiến hành thử nghiệm cách biểu diễn mới này vào bài toán phân lớp văn bản.
Chỉ ra một số kết quả phân lớp và so sánh với phương pháp biểu diễn theo mô hình vector
thông thường. Từ đó rút ra một số kết luận và hướng Phát triển tiếp theo.

MỤC LỤC
LỜI CẢM ƠN i
TÓM TẮT .ii
MỤC LỤC . iii
MỞ ĐẦU .1
Chương 1. KHAI PHÁ DỮ LIỆU VĂN BẢN. .3
1.1. Tổng quan về khai phá dữ liệu 3
1.1.1. Khái niệm 3
1.1.2. Các bước của quá trình khai phá dữ liệu 3
1.1.3. Ứng dụng của khai phá dữ liệu .5
1.2. Một số bài toán trong khai phá dữ liệu văn bản 6
1.2.1. Tìm kiếm Văn bản .6
1.2.2. Phân lớp văn bản . 7
Chương 2. CÁC PHƯƠNG PHÁP CƠ BẢN BIỂU DIỄN Văn bản .10
2.1. Tiền xử lý Văn bản 10
2.2. Mô hình Logic . 12
2.3. Mô hình phân tích cú pháp .14
2.4. Mô hình không gian vector .15
2.4.1. Mô hình Boolean 17
2.4.2. Mô hình tần suất .17
2.5. Biểu diễn Văn bản trong máy tìm kiếm .20
2.5.1. Giới thiệu về máy tìm kiếm 20
2.5.2. Mô hình biểu diễn Văn bản trong máy tìm kiếm 21
Chương 3. BIỂU DIỄN Văn bản SỬ DỤNG CÁC KHÁI NIỆM MỜ 23
Khóa luận tốt nghiệp Nguyễn Việt Cường
iv
3.1. Lý thuyết mờ .23
3.1.1. Tập mờ 23
3.1.2. Các phép toán trên tập mờ 25
3.1.3. Quan hệ mờ .27
3.1.4. Các phép toán trên Quan hệ mờ 27
3.2. Biểu diễn Văn bản sử dụng các khái niệm mờ 29
3.2.1. Khái niệm mờ .30
3.2.2. Biểu diễn Văn bản .32
3.2.3. Đề xuất giải pháp cho vấn đề đồng nghĩa .32
Chương 4. CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN 35
4.1. Tổng quan về bài toán phân lớp . .35
4.2. Các thuật toán phân lớp 36
4.2.1. Phân lớp dựa trên thuật toán Naive Bayes 36
4.2.2. Phân lớp dựa trên thuật toán K - Nearest Neighbor (KNN) .38
4.2.3. Phân lớp dựa vào thuật toán cây quyết định .39
4.2.4. Phân lớp sử dụng Support Vector Machines (SVM) 41
Chương 5. MỘT SỐ KẾT QUẢ THỰC NGHIỆM 43
5.1. Tập dữ liệu và tiền xử lý .43
5.2. Công cụ và phương pháp phân lớp .44
5.3. Kết quả thực nghiệm .45
KẾT LUẬN VÀ HƯỚNG Phát triển 53
TÀI LIỆU THAM KHẢO .55

MỞ ĐẦU
Ngày nay, sự Phát triển mạnh mẽ của Internet đã dẫn đến sự bùng nổ thông tin về
nhiều mặt kể cả về nội dung lẫn số lượng. Chỉ bằng một thao tác tìm kiếm đơn giản, ta có
thể nhận về một khối lượng khổng lồ các trang web có chứa thông tin liên quan tới nội
dung ta tìm kiếm. Tuy nhiên, chính sự dễ dàng này cũng mang đến cho con người rất
nhiều khó khăn trong việc chắt lọc ra các thông tin có ích để thu được các tri thức mới.
Phát hiện tri thức và khai phá dữ liệu là câu trả lời mới nhất cho vấn đề này nhằm phát
hiện ra các tri thức mới từ khối dữ liệu khổng lồ mà con người có được.
Trong các loại dữ liệu thì Văn bản là loại dữ liệu phổ biến mà con người thường
gặp phải nhất. Mô hình biểu diễn Văn bản phổ biến hiện nay là mô hình không gian
vector, trong đó mỗi Văn bản được biểu diễn bằng một vector của các từ khóa. Tuy nhiên
bài toán khai phá dữ liệu Văn bản thường gặp phải một số khó khăn như tính nhiều chiều
của văn bản, tính nhập nhằng của ngôn ngữ Trong khóa luận này, chúng tôi xin đề cập
đến một cách biểu diễn Văn bản mới: biểu diễn dựa trên các khái niệm mờ. Trong đó, mỗi
khái niệm sẽ được xác định bởi một tập các từ khóa liên quan. Và mức độ liên quan của
khái niệm đến Văn bản sẽ được xác định bằng hàm tích hợp mờ các từ khóa đó. Sau khi đã
có một tập các khái niệm liên quan đến một hay nhiều chủ đề cần phần lớp, mỗi Văn bản
sẽ được xem như là một vector có các thành phần là các khái niệm mờ đó.
Với lượng thông tin dạng Văn bản đồ sộ của Internet, một yêu cầu lớn đặt ra đối
với chúng ta là làm sao tổ chức và tìm kiếm thông tin có hiệu quả nhất. Phân lớp (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. Khóa luận sẽ trình
bày một số thuật toán phân lớp tiêu biểu và đưa ra hướng thực nghiệm cho phương pháp
biểu diễn Văn bản dựa trên các khái niêm mờ.
Chúng tôi áp dụng thuật toán KNN (k – người láng giềng gần nhất) và phần mềm
WEKA (K-người láng giếng gần nhất) để tiến hành phân lớp. Phần thực nghiệm cho thấy
rằng phương pháp biểu diễn Văn bản dựa khái niệm mờ có kết quả phân lớp tốt hơn so với
phương pháp biểu diễn Văn bản theo vector từ khóa.
Ngoài phần mở đầu và kết luận, nội dung của luận văn được trình bày trong 5
chương:
Khóa luận tốt nghiệp Nguyễn Việt Cường
2
Chương 1, giới thiệu tổng quan về khai phá dữ liệu văn bản, một số định nghĩa và
một số bài toán điển hình.
Chương 2, trình bày một số phương pháp biểu diễn Văn bản truyền thống: mô
hình tần suất, mô hình phân tích cú pháp, mô hình không gian vector . Đồng thời nêu ra
cách biểu diễn Văn bản thường dùng trong máy tìm kiếm.
Chương 3, giới thiệu tổng quan về lý thuyết tập mờ [9][14] và một số phép toán
trên tập mờ. Nội dung chính của chương là đề cập một cách biểu diễn Văn bản mới dựa
trên các khái niệm mờ.
Chương 4, trình bày bài toán phân lớp Văn bản và một số thuật toán phân lớp tiêu
biểu.
Chương 5, chỉ ra các kết quả thực nghiệm có được khi áp dụng mô hình biểu diễn
mới trong bài toán phân lớp văn bản. Đánh giá và so sánh với mô hình biểu diễn thông
thường.