Quy nạp quy tắc phân lớp sử dụng lý thuyết tập thô

i

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 C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG

LÊ QUANG ĐẠT

QUY NẠP QUY TẮC PHÂN LỚP

SỬ DỤNG LÝ THUYẾT TẬP THÔ

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

th¸i nguyªn - n¨m 2014

ii

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 C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG

LÊ QUANG ĐẠT

QUY NẠP QUY TẮC PHÂN LỚP

SỬ DỤ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: PGS.TS. NGUYỄN THANH TÙNG

Thái Nguyên, 2014

iii

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/

LỜI CẢM ƠN

Để hoàn thành được luận văn này tôi đã nhận được rất nhiều sự động

viên, giúp đỡ của nhiều cá nhân và tập thể.

Trước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS. Nguyễn

Thanh Tùng đã hướng dẫn tôi thực hiện nghiên cứu của mình.

Xin cùng bày tỏ lòng biết ơn chân thành tới các thầy cô giáo, người đã

đem lại cho tôi những kiến thức bổ trợ, vô cùng có ích trong những năm học

vừa qua.

Cũng xin gửi lời cám ơn chân thành tới Ban Giám hiệu, Phòng Đào tạo

sau đại học, Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học

Thái Nguyên đã tạo điều kiện cho tôi trong quá trình học tập.

Cuối cùng tôi xin gửi lời cám ơn đến gia đình, bạn bè, những người đã

luôn bên tôi, động viên và khuyến khích tôi trong quá trình thực hiện đề luận

văn của mình.

Thái Nguyên, ngày 18 tháng 07 năm 2014

Tác giả

Lê Quang Đạt

ii

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/

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng

dẫn của PGS.TS. Nguyễn Thanh Tùng. Các số liệu, kết quả nghiên cứu trong

luận văn là trung thực và chưa được ai công bố.

Tác giả

Lê Quang Đạt

iii

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/

MỤC LỤC

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

LỜI CAM ĐOAN .....................................................................................ii

MỤC LỤC...............................................................................................iii

DANH MỤC BẢNG................................................................................. v

DANH MỤC HÌNH .................................................................................vi

MỞ ĐẦU.................................................................................................. 1

Chương 1: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN PHÂN

LỚP .......................................................................................................... 4

1.1. Khái quát về khai phá dữ liệu................................................................. 4

1.1.1. Khai phá dữ liệu là gì ....................................................................... 4

1.1.2. Quy trình khai phá dữ liệu................................................................ 5

1.1.3. Các kỹ thuật khai phá dữ liệu........................................................... 6

1.1.4. Các ứng dụng của khai phá dữ liệu.................................................. 8

1.1.5. Một số thách thức đặt ra cho việc khai phá dữ liệu ...................... 11

1.2. Bài toán phân lớp.................................................................................. 12

1.2.1. Phát biểu bài toán .......................................................................... 12

1.2.2. Phương pháp tiếp cận chung để giải quyết bài toán phân lớp ....... 15

1.3. Kết luận chương 1................................................................................. 18

Chương 2: CƠ SỞ LÝ THUYẾT TẬP THÔ ........................................... 19

2.1. Giới thiệu .............................................................................................. 19

2.2. Hệ thông tin .......................................................................................... 20

2.3. Quan hệ bất khả phân biệt .................................................................... 21

2.3.1. Sự dư thừa thông tin....................................................................... 21

2.3.2. Quan hệ tương đương - Lớp tương đương..................................... 22

2.3.3. Thuật toán xác định lớp tương đương............................................ 23

2.3.4. Xấp xỉ tập hợp ................................................................................ 24

iv

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.3.5. Sự không chắc chắn và hàm thuộc................................................. 34

2.3.6. Sự phụ thuộc giữa các tập thuộc tính ............................................. 35

2.4. Rút gọn thuộc tính ................................................................................ 36

2.4.1. Khái niệm ....................................................................................... 36

2.4.2. Ma trận phân biệt và hàm phân biệt............................................... 39

2.5. Kết luận chương 2................................................................................. 42

Chương 3: SỬ DỤNG LÝ THUYẾT TẬP THÔ VÀO VIỆC QUY NẠP

QUY TẮC QUYẾT ĐỊNH TỪ TẬP CÁC VÍ DỤ HỌC.......................... 43

3.1 Mở đầu ................................................................................................... 43

3.2. Một số khái niệm về quy nạp quy tắc quyết định................................. 45

3.2.1. Quy tắc quyết định ......................................................................... 45

3.2.2. Các loại thuật toán quy nạp quy tắc ............................................... 49

3.3. Các thuật toán quy nạp quy tắc quyết định........................................... 50

3.3.1 Thuật toán sinh bộ quy tắc tối tiểu.................................................. 51

3.3.2 Thuật toán sinh bộ quy tắc vét cạn.................................................. 57

3.3.3 Các thuật toán sinh bộ quy tắc thỏa mãn yêu cầu ........................... 58

3.4. Về tính toán thực nghiệm ..................................................................... 61

3.5. Kết luận chương 3................................................................................. 63

KẾT LUẬN ............................................................................................ 65

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

v

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/

DANH MỤC BẢNG

Bảng 1.1 Tập đối tượng Động vật có xương sống......................................... 13

Bảng 1.2. Ma trận liên hợp (trường hợp 2 lớp) ............................................. 17

Bảng 2.1. Một hệ thông tin đơn giản ........................................................... 20

Bảng 2.2. Một hệ quyết định với C = {Age, LEMS} và D = {Walk} ............. 21

Bảng 2.3. Một bảng dữ liệu thừa thông tin .................................................. 22

Bảng 2.4. Một hệ quyết định điều tra vấn đề da cháy nắng............................ 25

Bảng 2.5. Hệ thông tin về thuộc tính của xe hơi ........................................... 28

Bảng 2.6. Bảng quyết định dùng minh họa hàm thuộc thô ............................ 35

Bảng 2.7. Hệ thông tin dùng minh họa ma trận phân biệt .............................. 39

Bảng 3.1. Một ví dụ về tập dữ liệu .............................................................. 53

a ba thuật toán (thể hiện bằng %) . 62

Bảng 3.3. So sánh đặc điểm của quy tắc quyết định ...................................... 63