Xây dựng tập thuộc tính rút gọn theo cách tiếp cận tập thô

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 ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

-------------------

TRẦN THU PHƯƠNG

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH

TIẾP CẬN TẬP THÔ

LUẬN VĂN THẠC SỸ KHOA HỌCMÁY TÍNH

Chuyên ngành : Khoa học máy tính

Mã số : 60 48 01

Thái Nguyên, năm 2011

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ

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

1

LỜI CẢM ƠN

Để hoàn tất một luận văn Thạc sĩ yêu cầu sự tập trung, sự cố gắng và độc

lập nghiên cứu. Bản thân tôi sau những năm tháng học tập vất vả và nghiên

cứu cũng đã cố gắng để hoàn thành được luận văn này. Tôi luôn ghi nhận

những sự đóng góp giúp đỡ nhiệt tình của những người bên cạnh mình, sự

ủng hộ, sự hỗ trợ của bố mẹ, bạn bè giúp tôi có thêm động lực để hoàn thành

khóa luận tốt nghiệp, nhân đây tôi muốn gửi lời cảm ơn nhất tới họ.

Lời cảm ơn trân trọng đầu tiên tôi muốn dành tới GS.TS Vũ Đức Thi,

người thầy đã dìu dắt và hướng dẫn tôi trong suốt quá trình làm luận văn, sự

chỉ bảo và định hướng của thầy giúp tôi tự tin nghiên cứu những vấn đề mới

và giải quyết bài toán một cách khoa học.

Tôi xin trân trọng cảm ơn Ban giám hiệu Trường Đại học Công nghệ

Thông tin và Truyền thông, Đại học Thái nguyên; Trường Dự bị Đại học Dân

tộc Sầm Sơn, Thanh Hóa đã tạo các điều kiện cho chúng tôi được học tập và

làm khóa luận một cách thuận lợi.

Lời cảm ơn sâu sắc muốn được gửi tới các thầy giáo Viện Công nghệ

Thông tin - Viện khoa học Việt Nam, những người thầy đã dạy dỗ và mở ra

cho chúng tôi thấy chân trời tri thức mới, hướng dẫn chúng tôi cách khám phá

và làm chủ công nghệ mới.

Tôi muốn gửi lời cảm ơn chân thành đến tập thể lớp CHK8B-KHMT đã

cùng tôi đi qua những tháng ngày miệt mài học tập, cùng chia sẻ những niềm

vui, nỗi buồn, động viên tôi đi qua những khó khăn, để tôi vững bước vượt

qua những vất vả, quyết tâm hoàn thành luận văn này.

Tôi xin trân trọng cảm ơn bố mẹ, người thân, bạn bè, đồng nghiệp,

những người đã mang tới tất cả niềm tin, định hướng và theo dõi tôi trong

suốt chặng đường đời. Nâng đỡ và đến bên tôi những giây phút khó khăn nhất

của cuộc sống.

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ

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

2

Tuy nhiên do thời gian có hạn, mặc dù đã nỗ lực cố gắng hết mình nhưng

chắc rằng luận văn khó tránh khỏi những thiếu sót. Rất mong được sự chỉ bảo,

góp ý tận tình của Quý thầy cô và các bạn.

Thanh Hóa, tháng 9 năm 2011

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ

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

3

MỤC LỤC

LỜI CẢM ƠN.....................................................................................................1

DANH MỤC HÌNH VẼ ....................................................................................5

DANH MỤC BẢNG BIỂU................................................................................6

DANH MỤC TỪ VIẾT TẮT.............................................................................7

LỜI MỞ ĐẦU ....................................................................................................8

CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ .........................10

LÝ THUYẾT TẬP THÔ ..................................................................................10

1. 1 Khai phá dữ liệu...........................................................................................10

1.1.1 Khai phá tri thức ......................................................................................10

1.1.2 Khai phá dữ liệu ......................................................................................12

1.1.2.1 Một số khía cạnh khai phá chủ yếu..................................................13

1.1.2.2 Một số kỹ thuật Khai phá dữ liệu.....................................................14

1.2 Lý thuyết tập thô...........................................................................................18

1.2.1 Giới thiệu về tập thô ................................................................................18

1.2.2 Bảng quyết định.......................................................................................20

1.3 Kết luận chƣơng 1.........................................................................................22

CHƢƠNG 2. XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN..........................24

THEO CÁCH TIẾP CẬN TẬP THÔ .............................................................24

2.1 Luật và quá trình khám phá Luật trong Bảng quyết định.......................24

2.1.1 Định nghĩa về luật và các đặc trưng. .......................................................24

2.1.2. Khám phá luật bởi bảng phân bố tổng quát dựa trên tập thô và thuật toán

tối ưu hoá các luật.............................................................................................25

2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô ..........................................26

2.2.1. Các định nghĩa ........................................................................................27

2.2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô .........................................29

2.3 Một số thuật toán sử dụng lý thuyết tập thô ..............................................31

2.3.1. Thuật toán lựa chọn thuộc tính sử dụng tập thô theo phương pháp đánh

giá kinh nghiệm. ...............................................................................................31

2.3.2. Thuật toán tìm tập rút gọn dựa vào cặp số phân biệt được ....................35

2.3.3. Thuật toán sử dụng các phép toán đại số...............................................36

2.3.4 Thuật toán tìm lõi của bảng quyết định...................................................39

2.3.5. Thuật toán tìm tập rút gọn theo xấp xỉ ngoài .........................................39

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ

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

4

2.3.6. Thuật toán tìm tập rút gọn theo xấp xỉ trong..........................................40

2.4 Một số thuật toán lập nhóm văn bản ..........................................................42

2.4.1. Thuật toán K – means............................................................................42

2.4.2. Thuật toán lập nhóm theo cây phân cấp .................................................42

2.4.3. Xác định các thuật đại diện cho nhóm ...................................................44

2.4.4. Độ tương tự giữa văn bản và nhóm văn bản ..........................................44

2.5 Kết luận chƣơng 2.........................................................................................44

CHƢƠNG 3. SỬ DỤNG MỘT THUẬT TOÁN ĐỂ TÌM TẬP THUỘC TÍNH

RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ PHỤC VỤ.................................45

BÀI TOÁN TRA CỨU THÔNG TIN..............................................................45

3.1 Tra cứu thông tin ..........................................................................................45

3.2 Tra cứu thông tin văn bản ...........................................................................46

3.2.1 Tra cứu thông tin văn bản........................................................................46

3.2.2 Xử lý hệ thống thông tin văn bản ............................................................47

3.2.3 Một số kỹ thuật tra cứu thông tin văn bản...............................................48

3.3 Phƣơng pháp tra cứu thông tin áp dụng lý thuyết tập thô .......................50

3.3.1 Xây dựng tập văn bản..............................................................................50

3.3.2 Gán trọng số cho thuật ngữ bởi dung sai xấp xỉ......................................50

3.3.3 Phân cụm văn bản....................................................................................52

3.3.4 Biểu diễn đặc trưng các cụm ...................................................................53

3.3.5 Độ tương tự giữa văn bản và cụm ...........................................................54

3.4 Kết luận chƣơng 3.........................................................................................54

CHƢƠNG 4. XÂY DỰNG HỆ THỐNG VÀ THỬ NGHIỆM .......................55

4.1 Môi trƣờng và nền tảng phát triển..............................................................55

4.2 Một số giao diện của hệ thống .....................................................................55

4.2.1 Xây dựng cơ sở dữ liệu............................................................................55

4.2.2 Giao diện của hệ thống ............................................................................56

4.2.2.1 Phương pháp xây dựng kho dữ liệu .................................................56

4.2.2.2 Một số giao diện...............................................................................57

4.3 Kết luận chƣơng 4.........................................................................................58

KẾT LUẬN ......................................................................................................59

TÀI LIỆU THAM KHẢO................................................................................60

PHỤ LỤC : DANH SÁCH CÁC TỪ DỪNG, TỪ TẦM THƢỜNG ..............63

PHỤ LỤC TỪ DỪNG, TỪ TẦM THƢỜNG..................................................64

XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ

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

5

DANH MỤC HÌNH VẼ

Hình 1.1: Mô hình mô tả quá trình khai phá tri thức ...................................11

Hình 3.1 Nguyên lý tra cứu thông tin.............................................................45

Hình 3.2 Mô hình hệ thống tra cứu thông tin văn bản. ................................47

Hình 3.3 Các bƣớc mô tả xây dựng hệ thống. ...............................................48

Hình 3.4 Mô hình bài toán tra cứu thông tin áp dụng lý thuyết tập thô. .....50

Hình 3.5 Thuật toán phân cụm văn bản. .......................................................53

Hình 3.6 Tìm thuật ngữ đại diện cho cụm. ....................................................54

Hình 4.1 Bảng thông tin tài liệu. ....................................................................55

Hình 4.2. Bảng lƣu trữ thông tin các lĩnh vực. .............................................55

Hình 4.3 Bảng lƣu trữ thông tin ngôn ngữ....................................................56

Hình 4.4. Bảng thông tin từ chủ đề................................................................56

Hình 4.5 Giao diện trang chủ hệ thống tra cứu. ...........................................57

Hình 4.6. Kết quả tra cứu của hệ thống. ........................................................58