Khai phá luật kết hợp trong cơ sở dữ liệu 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

ĐẠ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 VĂN TƢ

KHAI PHÁ LUẬT KẾT HỢP

TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG

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

Thái nguyên, năm 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

ii

ĐẠ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 VĂN TƢ

KHAI PHÁ LUẬT KẾT HỢP

TRONG CƠ SỞ DỮ LIỆU 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

NGƢỜI HƢỚNG DẪN KHOA HỌC

TS. NGUYỄN HUY ĐỨC

Thái nguyên, năm 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 là đƣợc thực hiện

theo đúng đề cƣơng đã đƣợc hội đồng khoa học trƣờng Đại học Thái nguyên￾khoa Công nghệ thông tin phê duyệt, nội dung thực hiện trong đề cƣơng đã

đƣợc cán bộ hƣớng dẫn giao cho và kiểm soát. 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

Nguyễn Văn 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

ii

LỜI CẢM ƠN

Tôi xin chân thành cảm ơn các thầy cô Trƣờng Đại học Công nghệ

Thông tin và Truyền thông – Đại học Thái Nguyên, các Thầy cô Viện công

nghệ thông tin – Viện Khoa học và Công nghệ Việt Nam, các anh chị lớp Cao

học K8 - khóa 2009-2011 đã giúp đỡ tôi trong quá trình nghiên cứu và thực

hiện luận văn.

Tôi xin trân trọng cảm ơn TS. Nguyễn Huy Đức – Khoa Thông tin -

Máy tính, Trƣờng Cao đẳng Sƣ phạm Trung ƣơng, ngƣời thầy trực tiếp hƣớng

dẫn, đƣa ra ý tƣởng, định hƣớng, đóng góp các ý kiến chuyên môn và tận tình

giúp đỡ tôi trong suốt quá trình nghiên cứu và thực hiện luận văn thạc sĩ

ngành khoa học máy tính.

Tôi xin cảm ơn các bạn bè đồng nghiệp và gia đình đã giúp đỡ, đóng

góp ý kiến và động viên tôi trong suốt qua trình học, quá trình nghiên cứu và

hoàn thành luận văn .

Tác giả

Nguyễn Văn 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

iii

MỤC LỤC

Trang

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

Lời cảm ơn…..…………………………………………….…………….……………….ii

Mục lục……………………..…………………………………….….……………..……iii

DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT .............................................................v

DANH MỤC CÁC BẢNG BIỂU................................................................................................. vi

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ...................................................................................... vii

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

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

1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu. ........................................ 3

1.2. Kiến trúc của hệ thống khai phá dữ liệu ............................................... 6

1.3. Quá trình khai phá dữ liệu.................................................................... 8

1.4. Nhiệm vụ của khai phá dữ liệu. .......................................................... 10

1.5. Các phƣơng pháp chính trong khai phá dữ liệu .................................. 11

1.5.1. Phƣơng pháp luật kết hợp ............................................................ 12

1.5.2. Phƣơng pháp cây quyết định........................................................ 12

1.5.4. Các phƣơng pháp dựa trên mẫu.................................................... 14

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

Kết luận chƣơng 1:.................................................................................... 16

Chƣơng 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU......................................17

2.1. Bài toán mở đầu ................................................................................. 17

2.2. Các khái niệm cơ sở........................................................................... 18

2.2.1.Cơ sở dữ liệu giao tác ................................................................... 19

2.2.2. Biểu diễn cơ sở dữ liệu giao tác ................................................... 19

2.2.3. Tập mục thƣờng xuyên ................................................................ 21

2.2.4. Luật kết hợp................................................................................. 22

2.2.5. Độ hỗ trợ và độ tin cậy của luật kết hợp....................................... 22

2.3. Khai phá luật kết hợp ......................................................................... 24

2.4. Các cách tiếp cận khai phá tập mục thƣờng xuyên ............................. 26

2.5. Các thuật toán điển hình khai phá tập mục thƣờng xuyên................... 27

2.5.1 Thuật toán Apriori ........................................................................ 28

2.5.2.Thuật toán FP_growth................................................................... 33

2.6. Thuật toán sinh luật kết hợp:.............................................................. 41

2.7. Một số mở rộng khai phá luật kết hợp trong cơ sở dữ liệu.................. 44

Kết luận chƣơng 2:.................................................................................... 46

Chƣơng 3: KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ ......................................................47

3.1. Một số khái niệm về luật kết hợp có trọng số ..................................... 47

3.2. Khai phá luật kết hợp trọng số không chuẩn hóa ................................ 49

3.3. Khai phá luật kết hợp trọng số chuẩn hóa........................................... 52

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

3.3.1. Một số khái niệm về trọng số chuẩn hóa..................................... 52

3.3.2. Thuật toán khai phá luật kết hợp trọng số chuẩn hóa

(MINVAL(W))...................................................................................... 54

Kết luận chƣơng 3:.................................................................................... 56

Chƣơng 4: THỰC NGHIỆM KHAI PHÁ LUẬT KẾT HỢP....................................................57

4.1. Giới thiệu bài toán.............................................................................. 57

4.2. Dữ liệu thực nghiệm........................................................................... 58

4.3. Xây dựng chƣơng trình ...................................................................... 60

4.4. Thực nghiệm khai phá........................................................................ 61

4.5. Kết quả thực nghiệm.......................................................................... 63

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN....................................................................................63

1. Những kết quả đã đạt đƣợc.................................................................... 63

2. Hƣớng phát triển của đề tài là: .............................................................. 64

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

PHỤ LỤC...................................................................................................................................67

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 KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT

Ký hiệu Diễn giải

KPDL Khai phá dữ liệu

CSDL Cơ sở dữ liệu

DB Cơ sở dữ liệu giao tác

TID Định danh của giao tác

I Tập các mục dữ liệu

T Giao tác (transaction)

Ck Tập các ứng viên là tập mục có k mục dữ liệu

Lk Tập các tập mục thƣờng xuyên có k mục dữ liệu

k-itemset Tập mục gồm k mục

BFS Breadth First Search

DFS Depth First Search

FP-growth Frequent-Pattern Growth

FP-tree Frequent pattern tree

Sup Độ hỗ trợ (support)

Minsup Ngƣỡng hỗ trợ tối thiểu

SC(X) Số lƣợng giao dịch chứa tập mục X

SRC Kỹ thuật lấy mẫu ngẫu nhiê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

vi

DANH MỤC CÁC BẢNG BIỂU

Bảng 2.1: Danh mục các tập mục trong CSDL ............................................. 19

Bảng 2.2: Biểu diễn ngang của CSDL giao tác............................................. 20

Bảng 2.3: Biểu diễn dọc của CSDL giao tác................................................. 20

Bảng 2.4: Ma trận giao tác của CSDL bảng 2.2............................................ 21

Bảng 2.5: Cơ sở dữ liệu DB ......................................................................... 24

Bảng 2.6: Độ hỗ trợ của các mục.................................................................. 25

Bảng 2.7: Độ hỗ trợ của các tập mục ............................................................ 25

Bảng 2.8: Độ tin cậy của các luật ................................................................. 26

Bảng 2.9: CSDL giao tác minh hoạ cho thuật toán Apriori........................... 31

Bảng 2.10: CSDL giao tác minh hoạ cho thuật toán FP- growth................... 34

Bảng 3.1.a. Tập giao tác DB......................................................................... 48

Bảng 3.1.b. Thông tin của cửa hàng.............................................................. 48

Bảng 4.1: Dữ liệu đã trích chọn để khai phá ................................................. 58

Bảng 4.2: Mã hóa các mặt hàng.................................................................... 59