Phương pháp khai phá dữ liệu dạng đóng và ứng 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

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ

TRUYỀN THÔNG

NGUYỄN HỒNG HẢI

PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU DẠNG ĐÓNG

VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ: KHOA 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 CÔNG NGHỆ THÔNG TIN VÀ

TRUYỀN THÔNG

NGUYỄN HỒNG HẢI

PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU DẠNG ĐÓNG

VÀ ỨNG DỤNG

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

Mã số: 60.48.01

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

HƯỚNG DẪN KHOA HỌC

PGS.TS. NGÔ QUỐC TẠO

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

LỜI CAM ĐOAN

Tôi xin cam đoan Luận văn “ Phƣơng pháp khai phá dữ liệu dạng đóng

và ứng dụng” là công trình nghiên cứu của riêng tôi dƣới sƣ̣ hƣớng dẫn của

PGS.TS. Ngô Quốc Tạo. Toàn bộ phần mềm do chính tôi lập trình và kiểm

thƣ̉ . Tôi xin chị u trách nhiệm về lời cam đoan của mình .

Các số liệu và thông tin sử dụng trong luận văn này là trung thực.

Tác giả

Nguyễn Hồng Hả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

MỤC LỤC

MỤC LỤC ......................................................................................................i

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT .................................... iv

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

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

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

Chƣơng 1: TÌM HIỂU PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU.................... 3

1.2. Khai phá dữ liệu là gì........................................................................... 3

1.2. Ứng dụng của việc khai phá dữ liệu ..................................................... 3

1.3. Qui trình khai phá tri thức .................................................................... 4

1.3.1. Qui trình khai phá tri thức ............................................................. 4

1.3.2. Kiến trúc hệ thống khai phá dữ liệu............................................... 5

1.4. Các nhiệm vụ chính của khai phá tri thức ............................................ 5

1.4.1. Dự đoán (predictive) ..................................................................... 5

1.4.2. Mô tả (discriptive)......................................................................... 6

1.5. Ý tƣởng kĩ thuật khai phá tri thức ........................................................ 7

1.6. Các thách thức của khai phá tri thức .................................................... 7

1.7. Qui trình chuẩn bị dữ liệu .................................................................... 7

1.7.1. Tại sao cần chuẩn bị dữ liệu .......................................................... 7

1.7.2. Làm sạch dữ liệu ........................................................................... 8

1.7.3. Chọn lọc dữ liệu ............................................................................ 9

1.7.4. Rút gọn dữ liệu.............................................................................. 9

1.7.5. Mã hóa dữ liệu ............................................................................ 11

1.8. Tập phổ biến ...................................................................................... 11

1.8.1. Giới thiệu tập phổ biến ................................................................ 11

1.8.2. Các khái niệm cơ bản .................................................................. 12

1.8.2.1. Cho cơ sở dữ liệu giao dịch .................................................. 12

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

1.8.2.2. Độ phổ biến và tập phổ biến ................................................. 13

1.8.2.3. Tính chất của tập phổ biến .................................................... 14

1.8.2.4. Tập phổ biến tối đại .............................................................. 14

1.8.2.5. Tập phổ biến đóng ............................................................... 14

1.8.2.6. Luật kết hợp.......................................................................... 15

1.8.2.7. Mô tả bài toán luật kết hợp .................................................. 15

1.9. Phân lớp dữ liệu................................................................................. 16

1.9.1. Định nghĩa thông qua ví dụ ......................................................... 16

1.9.2. Quy trình phân lớp ...................................................................... 16

1.10. Phân cụm dữ liệu ............................................................................. 17

1.10.1. Phân cụm là gì? ......................................................................... 17

1.10.2. Phân biệt phân lớp và phân cụm................................................ 17

1.10.3. Ứng dụng phân cụm .................................................................. 18

1.10.4. Ví dụ ......................................................................................... 19

Chƣơng 2: KHAI PHÁ TẬP PHỔ BIẾN ĐÓNG TRONG KHÔNG GIAN 2

CHIỀU VÀ KHAI PHÁ KHỐI ĐÓNG TRONG KHÔNG GIAN 3 CHIỀU 20

2.1. Tổng quan khai phá tập phổ biến đóng FCP trong không gian 2 chiều20

2.2. Mở đầu khai phá tập phổ biến đóng FCP trong không gian 2 chiều.... 20

2.3. Tiến hành khai phá tập phổ biến đóng FCP........................................ 22

2.3.1. Sơ lƣợc về quá trình khai phá tập phổ biến đóng ......................... 22

2.3.2. Thuật toán C-Miner.................................................................... 23

2.3.2.1. Thuật toán phân cụm (thuật toán increamental k-mean)........ 23

2.3.2.2 Quá trình chia không gian khai phá........................................ 25

2.3.2.3. Khai phá không gian con để tìm ra tập phổ biến đóng FCPs . 29

2.4. Tổng quan khai phá khối phổ biến đóng FCC trong không gian 3 chiều

................................................................................................................. 32

2.5. Mở đầu khai phá khối phổ biến đóng FCC trong không gian 3 chiều . 33

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

iii

2.6. Khai phá các lát cắt đại diện .............................................................. 36

2.6.1. Tạo ra các dàn đại diện................................................................ 38

2.6.2. Tạo ra các tập phổ biến đóng FCP............................................... 39

2.6.3. 3D FCC generation by post-pruning (Chiến lƣợc lƣợc bỏ các khối

đƣợc sinh ra không thỏa mãn) ............................................................... 39

2.6.4. Tính đúng đắn ............................................................................. 41

Chƣơng 3: CÀI ĐẶT THUẬT TOÁN VÀ ỨNG DỤNG ............................. 43

3.1. Cài đặt thuật toán trong không gian 2 chiều ....................................... 43

3.2. Cài đặt ứng dụng trong không gian 2 chiều........................................ 46

3.2.1. Cơ sở dữ liệu............................................................................... 47

3.2.2. Các bƣớc thực hiện...................................................................... 47

3.3. Cài đặt thuật toán trong không gian 3 chiều ....................................... 50

3.4. Cài đặt ứng dụng trong không gian 3 chiều........................................ 55

3.4.1. Cơ sở dữ liệu............................................................................... 55

3.4.2. Các bƣớc thực hiện...................................................................... 55

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

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

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

iv

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT

Các từ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt

EnumerateSubset Liệt kê các tập con

Slice Mặt cắt

Slices

Dàn tƣơng đƣơng với 1 tập

các mặt cắt kết hợp với

nhau.

CP Closed pattern Tập đóng

CS Compact subspace

Không gian con đặc (trong

bài toán đang xét: là không

gian con mà tất cả các ô có

giá trị là “1”.

FCC Frequent closed cube Khổi phổ biến đóng

FCP Frequent closed pattern Tập phổ biến đóng

Minlen

Là ngƣỡng giá trị Pattern

length mà các pattern phải

thỏa mãn

Minsup

Là ngƣỡng giá trị support

mà các pattern phải thỏa

mãn

RS Representative slices Dàn đại diện

RSM Representative slice Mining Khai phá lát cắt đại diện