Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị

i

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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

Trƣớc hết, tôi xin bày tỏ lòng biết ơn tới các thầy cô giáo trƣờng Đại học

Công nghệ thông tin & truyền thông đã tận tâm giảng dạy, cung cấp cho tôi

kiến thức, phƣơng pháp nghiên cứu trong khoá học vừa qua.

Đặc biệt tôi xin đƣợc bày tỏ sự biết ơn sâu sắc đến thầy giáo hƣớng dẫn

PGS.TS Đoàn Văn Ban, ngƣời đã tận tình hƣớng dẫn, giúp đỡ và động viên để

tôi thực hiện luận văn này.

Xin cảm ơn Ban giám hiệu trƣờng Đại học Công nghệ thông tin &

truyền thông, gia đình và các bạn đồng nghiệp đã tạo điều kiện giúp đỡ tôi trong

thời gian vừa qua.

ii

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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 bản luận vă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 này

là do tôi tự sƣu tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề

tài.

Nội dung luận văn này chƣa từng đƣợc công bố hay xuất bản dƣới bất kỳ

hình thức nào và cũng không đƣợc sao chép từ bất kỳ một công trình nghiên cứu

nào.

Tất cả phần mã nguồn của chƣơng trình đều do tôi tự thiết kế và xây

dựng, trong đó có sử dụng một số thƣ viện chuẩn và các thuật toán đƣợc các tác

giả xuất bản công khai và miễn phí trên mạng Internet.

Nếu sai tôi xin tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, tháng 10 năm 2011

TÁC GIẢ LUẬN VĂN

Bùi Thị Trung Thành

iii

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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

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

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

PHẦN MỞ ĐẦU ......................................................................................................1

CHƢƠNG 1 KHO DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU ........................................3

1.1 KHO DỮ LIỆU...................................................................................................3

1.1.1 Các chiến lƣợc xử lý và khai thác thông tin ......................................................3

1.1.2 Định nghĩa kho dữ liệu .....................................................................................4

1.1.3 Mục đích của kho dữ liệu .................................................................................5

1.1.4 Đặc tính của dữ liệu trong kho dữ liệu..............................................................6

1.2 Khai phá kho dữ liệu ...........................................................................................8

1.2.1 Định nghĩa khai phá dữ liệu.............................................................................9

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

1.2.3 Các bƣớc của quá trình khai phá dữ liệu.........................................................11

1.2.4 Các phƣơng pháp khai phá dữ liệu .................................................................12

1.2.5. Lựa chọn phƣơng pháp..................................................................................17

1.2.6. Thách thức trong ứng dụng và nghiên cứu kỹ thuật khai phá dữ liệu ............18

CHƢƠNG 2 KHAI PHÁ LUẬT KẾT HỢP ...........................................................23

2.1 Vài nét về khai phá luật kết hợp .......................................................................23

2.2 Luật kết hợp ......................................................................................................24

2.2.1. Mô hình hình thức.........................................................................................24

2.2.2 Một số hƣớng tiếp cận trong khai phá luật kết hợp ........................................26

2.2.3 Phát biểu bài toán phát hiện luật kết hợp ........................................................28

2.2.4 Phát hiện luật kết hợp dựa trên hệ thông tin nhị phân .....................................30

2.3 Thuật toán AprioriTID .....................................................................................38

2.4 Thuật toán AprioriHybrid.................................................................................41

iv

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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.5 Thuật toán K-Nearest Neighbors......................................................................42

2.6 Thuật toán K-Means.........................................................................................43

2.7 Kết luận cuối chƣơng ........................................................................................46

CHƢƠNG 3. CHƢƠNG TRÌNH THỰC NGHIỆM ................................................48

3.1 Giới thiệu bài toán.............................................................................................48

3.2 Tóm tắt và phân tích và thiết kế hệ thống ..........................................................48

3.3 CSDL vật lý với MS SQL Server 2008 ..............................................................49

3.4 CSDL của chƣơng trình.....................................................................................50

3.5 Một số chức năng và giao diện ............................................................................50

KẾT LUẬN ............................................................................................................54

1. Kết quả đạt đƣợc trong luận văn..........................................................................54

2. Hƣớng nghiên cứu tiếp theo ................................................................................54

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

v

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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, chữ viết tắt Ý nghĩa

Candidate itemset Một itemset trong tập Ck đƣợc sử dụng để sinh

ra các large itemset

Ck Tập các candidate k-itemset ở giai đoạn thứ k

Confidence Độ tin cậy của luật kết hợp

CSDL Cơ sở dữ liệu

DM Data mining – Khai phá dữ liệu

Frequent/large itemset Một itemset có độ hỗ trợ (support) >= ngƣỡng

độ hỗ trợ tối thiểu

ID Identifier

Item Một phần tử của itemset

Itemset Tập của các item

k-itemset Một itemset có độ dài k

Lk Tập các Large itemset ở giai đoạn thứ k

TID Transaction Identifier

Transaction Giao dịch

Classification Phân loại

Candidate Dự tuyển

vi

Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu siêu thị - Bùi Thị Trung Thành

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 HÌNH VẼ

STT Ý NGHĨA TRANG

Hình 1.1 Luồng dữ liệu trong một tổ chức 5

Hình 1.2 Mối quan hệ và cách nhìn nhận trong hệ thống 6

Hình 1.3 Quy trình phát hiện tri thức 11

Hình 2.1 Thiết lập để xác định danh giới các cụm ban đầu 43

Hình 2.2 Tính toán trong tâm các cụm mới 43

Hình 3.1 Mô hình quan hệ thực thể đã đƣợc lƣợc bỏ & tóm gọn 48

Hình 3.2 Cơ sở sữ liệu vật lý 48