Khai phá dữ liệu trên cơ sở phương pháp Luật kết hợp 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

1

Công trình được hoàn thành tại:

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

Người hướng dẫn khoa học:

PGS.TS. Nguyễn Trọng Bình

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

KHOA CÔNG NGHỆ THÔNG TIN

----------------------

NGUYỄN KHẢI HOÀI ANH

KHAI PHÁ DỮ LIỆU TRÊN CƠ SỞ PHƯƠNG PHÁP

LUẬT KẾT HỢP VÀ ỨNG DỤNG

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH

MÃ SỐ : 604801

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

THÁI NGUYÊN 2010

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

Công trình được hoàn thành tại:

Khoa công nghệ thông tin – Đại học Thái Nguyên

Người hướng dẫn khoa học: PGS.TS.Vũ Đức Thi

Phản biện 1:

Phản biện 2:

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn họp

tại:

Khoa Công nghệ thông tin – Đại học Thái Nguyên, vào hồi......

giờ...... ngày....... tháng........ năm 2010.

Có thể tìm hiểu luận văn tại trung tâm học liệu Đại học Thái

Nguyên và thư viện Trường CĐCN – Thái Nguyên

1

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 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

Nguyễn Khải Hoài Anh

2

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

Trang

Trang phụ bìa

Lời cam đoan

Mục lục………………………………………………………………………………………i

Danh sách các ký hiệu, các từ viết tắt……………………………………………………...iv

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

Danh mục các hình…………………………………………………………………………vi

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

CHƢƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU………………………………...3

1.1. Khai phá dữ liệu………………………………………………………………………3

1.1.1. Khái niệm về khám phá tri thức và khai phá dữ liệu…………………………3

1.1.2. Kiến trúc của một hệ thống khai phá dữ liệu ………………………………..5

1.1.3. Các loại dữ liệu được khai phá……………………………………………….6

1.1.4. Chức năng khai phá dữ liệu…………………………………………………..6

1.2. Một số phƣơng pháp khai phá dữ liệu thông dụng…………………………………7

1.2.1. Phương pháp luật kết hợp……………………………………………….......7

1.2.2. Phương pháp cây quyết định……………………………………………......7

1.2.3. Phương pháp k-Mean………………………………………………………...8

1.3. Một số ứng dụng của khai phá dữ liệu………………………………………………9

1.3.1. Phân tích dữ liệu gen và sinh học y học……………………………………...9

1.3.2. Phân tích dữ liệu tài chính………………………………………………........9

1.3.3. Dịch vụ bán lẻ……………………………………………………….............10

1.3.4. Công nghiệp viễn thông…………………………………………………….10

1.4. Các khuynh hƣớng và thách thức trong khai phá dữ liệu………………………...11

CHƢƠNG 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU LỚN……..13

2.1. Khai phá luật kết hợp………………………………………………………….........13

2.1.1. Một số khái niệm cơ bản …………………………………………………13

2.1.2. Cách khai phá luật kết hợp………………………………………………….14

2.1.3. Các tính chất của frequent itemset………………………………………….14

3

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.1.4. Các tiêu chuẩn để phân loại luật kết hợp……………………………………15

2.1.4.1. Kiểu của giá trị được quản lý trong luật……………………………..15

2.1.4.2. Chiều của dữ liệu được đề cập trong luật……………………….......15

2.1.4.3. Mức trừu tượng được đề cập trong luật…………………………..15

2.2. Khai phá luật kết hợp boolean một chiều từ CSDL giao dịch…………………...16

2.2.1. Thuật toán Apriori: Tìm các frequent itemset sử dụng việc sinh ra các ứng

viên……………………………………………………………………….16

2.2.2. Sinh luật kết hợp từ các frequent temset [5, 8, 15]…………………….........19

2.2.3. Cải tiến hiệu quả thuật toán Apriori………………………………………...19

2.2.3.1. Phương pháp dựa trên bảng băm……………………………........20

2.2.3.2. Giảm số giao dịch……………………………………………………….20

2.2.3.3. Phân đoạn………………………………………………………………..21

2.2.3.4. Lấy mẫu…………………………………………………………………..21

2.2.4. Khai phá các frequent itemset bằng cách không sinh ứng cử viên……........21

2.3. Khai phá luật kết hợp đa thức từ CSDL giao dịch………………………………...24

2.3.1. Luật kết hợp đa thức………………………………………………………...24

2.3.2. Các phương pháp khai phá luật kết hợp đa mức………………………........26

2.3.2.1. Đồng nhất độ hỗ trợ tối thiểu cho tất cả các mức…………………..26

2.3.2.2. Giảm dần độ hỗ trợ tối thiểu ở mức thấp hơn…………………….27

2.3.2.3. Độc lập theo từng mức………………………………………………….27

2.3.2.4. Lọc chéo mức bởi một itemset………………………………………….........27

2.4. Khai phá luật kết hợp đa chiều từ CSDL quan hệ và kho dữ liệu………………..28

2.4.1. Luật kết hợp đa chiều……………………………………………………….28

2.4.2. Khai phá luật kết hợp đa chiều sử dụng việc rời rạc hoá tĩnh các thuộc tính số

lượng……………………………………………………………………….29

2.4.3. Khai phá luật kết hợp số lượng……………………………………………..30

2.4.4. Khai phá luật kết hợp dựa vào khoảng cách………………………………...31

CHƢƠNG 3: MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP……………..34

3.1. Khám phá các frequent itemset……………………………………………….34

3.1.1. Thuật toán AIS………………………………………………….......34

4

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.1.2. Thuật toán SETM……………………………………………….......35

3.1.3. Thuật toán Apriori…………………………………………………..39

3.1.3.1. Hàm Apriori_gen……………………………………….40

3.1.3.2. Hàm subset……………………………………………...40

3.1.4. Thuật toán AprioriTID…………………………………….41

3.1.5. Thuật toán AprioriHybrid…………………………………………...43

3.2. Khám phá luật kết hợp……………………………………………………...44

3.2.1. Thuật toán sinh luật đơn giản……………………………………….45

3.2.2. Thuật toán nhanh………………………………………………........45

3.3. Thuật toán DHP (Direct Hashing with Efficent Pruning)………………...46

3.3.1 Thuật toán DHP……………………………………………………...46

3.3.2. Giảm kích thước của cơ sở dữ liệu giao dịch………………….........51

3.3.3. Giảm số lần quét cơ sở dữ liệu (Scan – Reduction method)………..53

3.4. Thuật toán PHP (Perfect Hash and Pruning)……………………………...53

3.5. So sánh các thuật toán khám phá các frequent itemset…………………...55

3.5.1. Sinh dữ liệu tổng hợp………………………………………….........55

3.5.2. So sánh các thuật toán AIS, SETM, Apriori và AprioriTID………..56

CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM……………........63

“ MÔ PHỎNG THUẬT TOÁN APRIORI”

4.1. Phát biểu bài toán …………………………………………………………..63

4.2. Phân tích bài toán …………………………………………………………...63

4.3. Xây dựng dữ liệu…………………………………………………………….64

4.4. Cài đặt chƣơng trình thử nghiệm…………………………………………..64

4.5. Giao diện chính của chƣơng trình………………………………………….65

KẾT LUẬN VÀ ĐỀ NGHỊ…………………………………………………........67

TÀI LIỆU THAM KHẢO……………………………………………………….68

5

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

Ký hiệu Diễn giải

Ck Tập các k-itemset ứng viên

Ck

Tập các k-itemset ứng viên mà TID của giao dịch sinh ra liên kết với

tập mục ứng viên

D Cơ sở dữ liệu giao dịch

Di Phần thứ i của cơ sở dữ liệu D

I Tập các mục

Lk Tập các k-itemset phổ biến

T Giao dịch (transaction)

X ⇒Y Luật kết hợp (với X là tiền đề, Y là hệ quả)

Conf Độ tin cậy (Confidence)

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

Min_conf Ngưỡng tin cậy tối thiểu

Min_sup Ngưỡng hỗ trợ tối thiểu

Sup Độ hỗ trợ (support)

Tid Định danh của giao dịch

Tid-List Danh sách các định danh của giao dịch

ARCS Association Rule Clustering System

SQL Structured Query Language

FP -growth Frequent -Pattern Growth

FP -Tree Frequent pattern tree

min_sup_count minimum support count

DHP Direct Hashing with Efficent Pruning

PHP Perfect Hash and Pruning