Phát hiện luật kết hợp ứng dụng trong cơ sở dữ liệu quản lý sinh viên

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

0

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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

VÀ TRUYỀN THÔNG

LÊ XUÂN LƢỢNG

PHÁT HIỆN LUẬT KẾT HỢP ỨNG DỤNG TRONG

CƠ SỞ DỮ LIỆU QUẢN LÝ SINH VIÊN

Chuyên nghà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

Ngƣời hƣớng dẫn khoa học: TS Vũ Mạnh Xuân

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 toàn bộ nội dung trong Luận văn hoàn toàn theo đúng

nội dung đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội

dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai

sót tôi hoàn toàn chịu trách nhiệm.

Tác giả luận văn

Lê Xuân Lượ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

MỤC LỤC

Lời cam đoan..................................................................................................................i

Mục lục ...............................................................................................................ii

Danh mục các chữ viết tắt.......................................................................................iv

Danh mục các bảng...................................................................................................v

Danh mục các hình vẽ .............................................................................................vi

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

Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ

DỮ LIỆU........................................................................................................ 3

1.1. Một số khái niệm về cơ sở dữ liệu ........................................................ 3

1.1.1. Cơ sở dữ liệu ................................................................................... 3

1.1.2. Hệ quản trị cơ sở dữ liệu................................................................. 4

1.2. Tổ chức và khai thác cơ sở dữ liệu truyền thống................................... 5

1.3. Kho dữ liệu ............................................................................................ 6

1.3.1. Đinh nghĩa kho dữ liệu.................................................................... 6

1.3.2. Cấu trúc của kho dữ liệu ................................................................. 7

1.3.3. Mục đích của việc xây dựng kho dữ liệu........................................ 9

1.4. Khai phá dữ liệu ................................................................................... 11

1.4.1. Khái niệm...................................................................................... 11

1.4.2. Các bước của quá trình phát hiện tri thức..................................... 11

1.4.3. Một số phương pháp khai phá dữ liệu ......................................... 13

1.4.3.1. Phương pháp suy diễn và quy nạp ......................................... 13

1.4.3.2. Cây quyết định và luật ........................................................... 14

1.4.3.3. Phân nhóm và phân đoạn....................................................... 16

1.4.3.4. Phương pháp ứng dụng K-láng giềng gần ............................. 16

1.4.3.5. Các phương pháp dựa trên mẫu ............................................. 17

1.4.3.6. Phát hiện các luật kết hợp ...................................................... 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

iii

1.4.4. Nhiệm vụ chính của khai phá dữ liệu ........................................... 19

1.4.5. Những khó khăn trong nghiên cứu khai phá dữ liệu .................... 21

1.4.6. Một số ứng dụng khai phá dữ liệu ................................................ 24

Chƣơng 2. PHÁT HIỆN LUẬT KẾT HỢP.............................................................. 25

2.1. Các khái niệm và tính chất của luật kết hợp ........................................ 25

2.1.1. Một số khái niệm .......................................................................... 25

2.1.2. Thuật toán cơ bản.......................................................................... 28

2.1.3. Tính chất của luật kết hợp và tập mục phổ biến ........................... 32

2.1.4. Một số hướng tiếp cận trong khai phá luật kết hợp ...................... 33

2.2. Một số thuật toán phát hiện luật kết hợp.............................................. 35

2.2.1. Thuật toán AIS.............................................................................. 35

2.2.2. Thuật toán SETM.......................................................................... 36

2.2.3. Thuật toán Apriori......................................................................... 38

2.2.4. Thuật toán Apriori-TID................................................................. 44

2.2.5. Thuật toán Apriori-Hybrid............................................................ 46

2.2.6. Thuật toán PARTITION ............................................................... 47

2.2.7. Sinh các luật kết hợp từ tập mục phổ biến................................... 48

Chƣơng 3. ỨNG DỤNG PHÁT HIỆN LUẬT KẾT HỢP KHAI PHÁ

DỮ LIỆU QUẢN LÝ SINH VIÊN....................................................... 52

3.1. Đặt vấn đề ............................................................................................ 52

3.2. Xây dựng chương trình demo thuật toán Apriori ứng dụng phát

hiện luận kết hợp trong CSDL quản lý sinh viên ......................... 54

3.2.1. Các bước tiến hành khai phá dữ liệu quản lý sinh viên ................ 54

3.2.2. Xây dựng bảng cơ sở dữ liệu để khai phá..................................... 54

3.2.3. Chương trình demo ....................................................................... 57

3.2.4. Một số kết quả thử nghiệm ........................................................... 58

KẾT LUẬN .......................................................................................................................... 64

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

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 CHỮ VIẾT TẮT

Ký hiệu Diễn giải

supp: Độ hỗ trợ (support)

conf: Độ tin cậy (confidence)

minsup: Ngưỡng độ hỗ trợ tối thiểu

mincof: Ngưỡng độ tin cậy tối thiểu

SQL: Structured Query Language

KDD: Kownledge Discovery in Database

FI: Frenquent Itemset

MFI: Maximally Frequent Itemset

CSDL: Cơ sở dữ liệu

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

v

DANH MỤC CÁC BẢNG

Bảng 2.1. Giao dịch mua hàng........................................................................ 30

Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng ........................ 30

Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng ....................................... 31

Bảng 2.4. Ma trận biểu diễn cơ sở dữ liệu ...................................................... 43

Bảng 2.5. Vector biểu diễn nhị phân cho tập 1 thuộc tính.............................. 43

Bảng 2.6. Vector biểu diễn nhị phân cho các tập 2 thuộc tính ....................... 43

Bảng 2.7. Vector biểu diễn nhị phân cho các tập 3 thuộc tính ....................... 44

Bảng 2.8. Vector biểu diễn nhị phân cho các tập 4 thuộc tính ....................... 44

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

vi

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Cấu trúc kho dữ liệu.......................................................................... 8

Hình 1.2. Quy trình phát hiện tri thức............................................................. 12

Hình 1.3. Mẫu kết quả với phương pháp cây quyết định................................ 15

Hình 3.1. Sơ đồ khai phá dữ liệu quản lý sinh viên........................................ 54

Hình 3.2. Bảng cơ sở dữ liệu khai phá............................................................ 56

Hinh 3.3. Giao diện chính của chương trình demo......................................... 57

Hình 3.4. Giao diện “Thao tác với CSDL” ..................................................... 58

Hình 3.5. Kết quả khai phá lần thứ 1 .............................................................. 59

Hình 3.6. Kết quả thử nghiệm lần thứ 2.......................................................... 60

Hình 3.7. Kết quả thử nghiệm lần thứ 3.......................................................... 61