Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Khai phá dữ liệu văn bản bằng lý thuyết tập thô
Nội dung xem thử
Mô tả chi tiết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG
LA ĐỨC DŨNG
KHAI PHÁ DỮ LIỆU
VĂN BẢN BẰNG LÝ THUYẾT TẬP THÔ
LUẬN VĂN THẠC SỸ 0KHOA HỌC MÁY TÍNH
Thái Nguyên – 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG
LA ĐỨC DŨNG
KHAI PHÁ DỮ LIỆU
VĂN BẢN BẰNG LÝ THUYẾT TẬP THÔ
LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ Đức Thi.
Thái Nguyên – 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
a
MỤC LỤC
LỜI CẢM ƠN...................................................................................I
LỜI CAM ĐOAN..............................................................................II
DANH MỤC CÁC HÌNH VẼ.............................................................III
DANH MỤC CÁC BẢNG BIỂU........................................................IV
DANH MỤC CHỮ VIẾT TẮT.............................................................V
LỜI MỞ ĐẦU........................................................................................ 1
CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN VÀ
LÝ THUYẾT TẬP THÔ....................................................................... 4
1.1 Khai phá dữ liệu văn bản................................................................ 4
1.1.1 Khai phá dữ liệu.......................................................................... 4
1.1.1.1 Khái niệm ............................................................................. 4
1.1.1.2 Lịch sử nghiên cứu................................................................ 5
1.1.1.3 Các khía cạnh khai phá chủ yếu ............................................ 5
1.1.1.4 Quy trình của DM................................................................. 7
1.1.1.5 Các phương pháp của DM..................................................... 7
1.1.2 Khai phá dữ liệu văn bản............................................................11
1.1.2.1 Khái niệm ............................................................................11
1.1.2.2 Các kỹ thuật khai phá văn bản..............................................13
1.2 Khai phá tri thức ứng dụng lý thuyết tập thô ...............................17
1.2.1 Khai phá tri thức theo cách tiếp cận tập thô ............................17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
b
1.2.1.1 Một số khái niệm..................................................................17
1.2.1.1.1 Hệ thống thông tin............................................................17
1.2.1.1.2. Khái niêm về bảng quyết định………………………….19
1.2.1.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin.20
1.2.1.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định...22
1.2.1.2. Tập thô trong không gian xấp xỉ............................................22
1.2.1.3 Khai phá tri thức theo cách tiếp cận tập thô............................25
1.2.2 Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô ........................27
1.2.3 Lựa chọn thuộc tính dựa trên tập thô ..........................................27
1.2.4 Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô .......28
1.3 Kết luận chƣơng 1 ..........................................................................29
CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU TRONG
XỬ LÝ VĂN BẢN ................................................................................30
2.1. Biểu diễn văn bản ..........................................................................30
2.1.1. Biểu diễn văn bản......................................................................30
2.1.2. Các phương pháp biểu diễn văn bản..........................................30
2.1.2.1. Tiền xử lý văn bản ..............................................................30
2.1.2.2. Mô hình Logic ....................................................................32
2.1.2.3. Mô hình phân tích cú pháp.................................................34
2.1.2.4. Mô hình không gian vector .................................................35
2.1.2.5. Mô hình Boolean ................................................................36
2.1.2.6. Mô hình tần suất .................................................................37
2.1.2.7. Mô hình dựa trên tập mờ (Fuzzy Set)..................................39
2.1.2.8. Mô hình tập thô dung sai (Tolerance Rough Set Model-TRSM)
........................................................................................................41
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
c
2.2. Các thuật toán lập nhóm văn bản.................................................43
2.2.1. Thuật toán K – Means..............................................................43
2.2.2. Thuật toán lập nhóm theo cây phân cấp.....................................44
2.2.2.1. Thuật toán theo cây phân cấp từ trên xuống ( Top Down
Hierachical Clustering)....................................................................44
2.2.2.2. Thuật toán theo cây phân cấp từ dưới lên ( Bottom Up
Hierachical Clustering)....................................................................45
2.2.2.3. Giải thuật lập nhóm Non Hierachical Clustering Overlap ...45
2.2.2.4. Giải thuật lập nhóm Non Hierachical Clustering Non Overlap46
2.2.3. Xác định các thuật đại diện cho nhóm .......................................46
2.2.4. Độ tương tự giữa văn bản và nhóm văn bản ..............................47
2.3 Bài toán phân lớp văn bản .............................................................47
2.3.1 Bài toán......................................................................................47
2.3.2 Các nghiên cứu liên quan ...........................................................48
2.4 Các phƣơng pháp phân lớp............................................................49
2.4.1 Phân lớp dựa trên thuật toán Naive Bayes..................................49
2.4.2 Phương pháp K – Nearest Neighbor ( K-NN).............................51
2.4.3 Phân lớp sử dụng Support Vector Machines (SVM)...................52
2.5 Kết luận chƣơng 2 ..........................................................................54
CHƢƠNG 3. PHÂN LOẠI VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ ÁP
DỤNG LÝ THUYẾT TẬP THÔ .........................................................55
3.1 Kiến trúc hệ thống phân loại văn bản tiếng Việt tự động ............55
3.2. Các chức năng của hệ thống .........................................................56
3.2.1 Xây dựng tập văn bản dùng cho huấn luyện ...............................56
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
d
3.2.2 Xây dựng tập từ dừng, từ tầm thường.........................................56
3.2.3 Xây dựng tập thuật ngữ ..............................................................56
3.2.4 Tiền xử lý văn bản đầu vào ........................................................56
3.2.5 Huấn luyện.................................................................................57
3.2.6 Phân lớp văn bản........................................................................61
3.3 Kết luận chƣơng 3 ..........................................................................62
CHƢƠNG 4. XÂY DỰNG HỆ THỐNG PHÂN LOẠI VĂN BẢN TIẾNG
VIỆT THEO CHỦ ĐỀ .........................................................................63
4.1 Môi trường và nền tảng ứng dụng .................................................63
4.2 Giao diện hệ thống ........................................................................65
4.3 Kết luận chương 4.........................................................................67
PHỤ LỤC 1. DANH SÁCH CÁC TỪ DỪNG, TỪ TẦM THƢỜNG 73
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
I
LỜI CẢM ƠN
Tôi xin bày tỏ lòng biết ơn đến trường Đại học Công nghệ, Đại học Thái
Nguyên, Viện Công nghệ thông tin và các thầy cô giáo đã trực tiếp giảng dạy,
hướng dẫn tôi trong quá trình học tập và định hướng quan trọng trong việc hình
thành ý tưởng nghiên cứu.
Tôi xin chân thành cảm ơn Chi bộ, BGĐ, BCH Công đoàn, Tổ Tự nhiên
và cán bộ giáo viên, công nhân viên Trung tâm GDTX Thiệu Hóa đã động viên,
giúp đỡ và tạo điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu.
Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc GS.TS Vũ Đức Thi, người
thầy đã trực tiếp hướng dẫn và giúp đỡ tôi hoàn thành luận văn tốt nghiệp.
Xin được cảm ơn bố mẹ, anh chị em gia đình nội ngoại tạo điều kiện về
mọi mặt để bản thân hoàn thành tốt chương trình khóa học và bảo vệ luận văn
hôm nay.
Mặc dù đã có nhiều cố gắng, nhưng do thời gian có hạn và bản thân còn
những hạn chế nhất định nên luận văn không tránh khỏi thiếu sót. Mong nhận
được các ý kiến phê bình, góp ý của Hội đồng chấm luận văn, các thầy cô giáo
và đồng nghiệp để công trình nghiên cứu được hoàn chỉnh hơn.
Thái Nguyên, tháng 9 năm 2011
Tác giả
La Đức Dũng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
II
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là công trình do tôi tổng hợp và nghiên cứu.
Trong luận văn có sử dụng một số tài liệu tham khảo như đã nêu trong phần
tài liệu tham khảo.
Tác giả Luận văn
La Đức Dũng