Nghiên cứu thuật toán Charm trong khai phá tập mục thường xuyên đóng

Số hóa bởi Trung tâm Học liệu – ĐHTN 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

PHAN VĂN TUYÊN

NGHIÊN CỨU THUẬT TOÁN CHARM

TRONG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ĐÓ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 – ĐHTN 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

PHAN VĂN TUYÊN

NGHIÊN CỨU THUẬT TOÁN CHARM

TRONG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ĐÓ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 - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

LỜI CẢM ƠN

Để hoàn thành luận văn này tôi đã nhận được sự giúp đỡ tận tình của 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. Đặc biệt là TS. Nguyễn

Huy Đức, người thầy trực tiếp hướng dẫn tôi trong quá trình nghiên cứu và thực

hiện luận văn.

Nhân dịp này tôi xin được bày tỏ lời cảm ơn tới tất cả các thầy cô giáo

Viện Công nghệ thông tin – Viện Khoa học và Công nghệ Việt Nam, 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

đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ tôi trong quá trình học tập,

nghiên cứu.

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 này.

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 này.

Tác giả

Phan Văn Tuyên

Số hóa bởi Trung tâm Học liệu – ĐHTN 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à giáo viên 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

Phan Văn Tuyên

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

I

MỤC LỤC

Trang

Lời cảm ơn

Lời cam đoan

MỤC LỤC ..............................................................................................................................I

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

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

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

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

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

1.1. KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ...............................................3

1.2. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU...........................................5

1.3. QUÁ TRÌNH KHAI PHÁ DỮ LIỆU.........................................................................6

1.4. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU .................................................................8

1.4.1.Phân lớp dữ liệu...................................................................................................8

1.4.2.Phân cụm dữ liệu .................................................................................................8

1.4.3.Khai phá luật kết hợp...........................................................................................8

1.4.4.Hồi quy ................................................................................................................9

1.4.5.Giải thuật di truyền..............................................................................................9

1.4.6.Mạng nơron .........................................................................................................9

1.4.7.Cây quyết định.....................................................................................................9

1.5. MỘT SỐ ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU..............................................10

1.6. KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN...........................................................11

1.6.1. Cơ sở dữ liệu giao tác.......................................................................................11

1.6.2. Tập mục thƣờng xuyên.....................................................................................13

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

1.6.4. Một số thuật toán điển hình tìm tập mục thƣờng xuyên...................................16

1.6.4.1. Thuật toán Apriori.........................................................................................16

1.6.4.2. Thuật toán FP-Growth...................................................................................20

1.7. KẾT LUẬN CHƢƠNG 1.........................................................................................28

CHƢƠNG 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ĐÓNG....................................29

2.1. CƠ SỞ TOÁN HỌC ................................................................................................29

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

II

2.1.1. Ánh xạ đóng .....................................................................................................29

2.1.2. Tập đóng...........................................................................................................30

2.1.3. Kết nối Galois...................................................................................................30

2.1.4. Bao đóng của tập mục dữ liệu ..........................................................................31

2.2. TẬP MỤC THƢỜNG XUYÊN ĐÓNG ..................................................................32

2.2.1. Định nghĩa .......................................................................................................32

2.2.2. Các tính chất của tập mục thƣờng xuyên đóng.................................................32

2.3. THUẬT TOÁN CHARM ........................................................................................32

2.3.1. Giới thiệu thuật toán CHARM .........................................................................32

2.3.2. Cây tìm kiếm và lớp tƣơng đƣơng....................................................................33

2.3.3. Các tính chất cơ bản của cặp tập mục - tập định danh: ....................................34

2.3.4. Thiết kế thuật toán ............................................................................................35

2.3.5. Ví dụ minh họa .................................................................................................37

2.3.6. Đánh giá thuật toán...........................................................................................39

2.4. KẾT LUẬN CHƢƠNG 2.........................................................................................39

CHƢƠNG 3: CÀI ĐẶT THỰC NGHIỆM..........................................................................41

3.1. XÂY DỰNG CHƢƠNG TRÌNH.............................................................................41

3.2. GIAO DIỆN CỦA CHƢƠNG TRÌNH ....................................................................43

3.3. KẾT QUẢ THỰC NGHIỆM ...................................................................................44

3.4. NHẬN XÉT .............................................................................................................47

KẾT LUẬN..........................................................................................................................48

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

PHỤ LỤC ............................................................................................................................51

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

III

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 tập mục ứng viên

BFS Breadth First Search

CSDL Cơ sở dữ liệu

CHARM Closed Asociation RuleMning

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

DFS Depth First Search

FP -growth Frequent -Pattern Growth

FP -tree Frequent pattern tree

IT-tree Itemset-Tidset tree

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

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

KPDL Khai phá dữ liệu

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

Lk Tập các k-tập mục thƣờng xuyên

Supp Độ hỗ trợ (support)

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

T Giao tác (transaction)