Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC

-----------------

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

TRẦN PHÚ DƯ

KHAI THÁC DÀN TẬP PHỔ BIẾN ĐÓNG SỬ DỤNG CẤU TRÚC DSBV

Có thể bạn quan tâm!

Xem toàn bộ 72 trang tài liệu này.

Ngành: CÔNG NGHỆ THÔNG TIN

Mã số chuyên ngành: 60480201

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC

-----------------

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

TRẦN PHÚ DƯ

KHAI THÁC DÀN TẬP PHỔ BIẾN ĐÓNG SỬ DỤNG CẤU TRÚC DSBV

Ngành: CÔNG NGHỆ THÔNG TIN

Mã số chuyên ngành: 60480201

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC

LỜI CAM ĐOAN

Tôi cam đoan: báo cáo luận văn “Khai Thác Dàn Tập Phổ Biến Đóng Sử Dụng Cấu Trúc DSBV” là công trình nghiên cứu của riêng tôi và được sự hướng dẫn khoa học của PGS.TS.Lê Hoài Bắc.

Các kết quả nghiên cứu có tính độc lập riêng, không sao chép bất kỳ tài liệu nào và chưa công bố nội dung này ở bất kỳ đâu. Các số liệu trong luận văn được sử dụng trung thực, nguồn trích dẫn có chú thích rõ ràng, có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình nghiên cứu khác.

Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan của tôi.

TP. HCM, ngày 25 tháng 10 năm 2018

Tác giả Trần Phú Dư

Nhận xét của Thầy hướng dẫn:

...........................................................................................................................................

Nhận xét của Thầy phản biện:

...........................................................................................................................................

LỜI CẢM ƠN

Lời đầu tiên, Tôi xin chân thành bày tỏ lòng biết ơn sự nhiệt tình, và những kiến thức bổ ích mà các thầy cô giảng dạy trong khóa cao học của lớp chúng tôi, đã tận tình chỉ dẫn, truyền đạt khi Tôi học tập tại trường đại học Ngoại Ngữ Tin Học thành phố Hồ Chí Minh.

Tôi rất trân trọng ghi nhớ lòng biết ơn sâu sắc và gửi lời cảm ơn chân thành đến thầy PGS.TS Lê Hoài Bắc đã tận tình chỉ dẫn, và hướng dẫn rõ ràng các vấn đề liên quan trong quá trình thực hiện luận văn của tôi từ lúc bắt đầu đến khi hoàn thành.

Trong quá trình học tập và làm luận văn, ngoài sự giúp đỡ của thầy cô, Tôi luôn nhận được sự quan tâm, động viên từ ba mẹ, gia đình, và bạn bè. Tôi xin chân thành cảm ơn tất cả người thân yêu đã luôn động viên và giúp đỡ.

Lĩnh vực khai thác dữ liệu là hết sức rộng lớn, trong phạm vi của đề tài thực hiện khó tránh khỏi sai sót, rất mong nhận được sự cảm thông và ý kiến đóng góp quý báu của thầy cô, anh chị và bạn bè.

Trần Phú Dư

MỤC LỤC

LỜI NÓI ĐẦU 1

1. Mở đầu: 1

2. Bố cục đề tài 3

Chương 1: TỔNG QUAN 4

1. Khai thác dữ liệu: 4

2. Ứng dụng của khai thác dữ liệu 5

3. Khai thác dàn các tập phổ biến đóng 7

4. Ý nghĩa khoa học và thực tiễn của đề tài 8

5. Phương pháp nghiên cứu và đối tượng nghiên cứu 8

6. Khó khăn và Thách thức 9

7. Mục tiêu và phạm vi của luận văn 9

8. Đóng góp của luận văn 10

Chương 2: CƠ SỞ LÝ THUYẾT 11

1. Khái quát bài toán 11

2. Hướng tiếp cận khai thác tập phổ biến đóng 12

3. Hướng tiếp cận khai thác tập sinh (Minimal Generator) 16

4. Hướng tiếp cận khai thác Dàn các tập phổ biến đóng 16

5. Đề xuất cấu trúc dữ liệu 17

5.1 Superset bit-vector 17

5.2 Dynamic superset bit-vector 18

5.2.1 Tìm FCS từ cấu trúc DSBV 19

5.2.2 Tìm minimal FCS từ cấu trúc DSBV 20

5.2.3 Giao 2 DSBVs 21

5.2.4 Cập nhật 1 DSBV 22

Chương 3: ĐỀ XUẤT THUẬT TOÁN KHAI THÁC DÀN CÁC TẬP PHỔ BIẾN ĐÓNG VÀ CẢI TIẾN. 24

1. Phát biểu bài toán khai thác Dàn các tập phổ biến đóng 24

2. Thuật Toán BVCL 25

2.1 Lưu đồ tổng quát của thuật toán 30

2.2 Các bước chính của thuật toán 31

3. Đặc tả và phân tích thuật toán 36

4. Cải tiến thuật toán gốc 43

4.1 Cơ sở lý thuyết 43

4.1.1 Kết nối Galois: 43

4.1.2 Định nghĩa toán tử đóng: 43

4.1.3 Các tính chất của IT-pair 43

4.1.4 Minimal Generator (mG) 44

4.1.5 Một số nhận xét về mG 44

4.2 Thuật toán 44

5. Kết quả thực nghiệm và so sánh 46

5.1 Bộ dữ liệu Chess. 47

5.2 Bộ dữ liệu Mushroom. 49

5.3 Bộ dữ liệu Pumsb. 50

5.4 Bộ dữ liệu Retail. 52

5.5 Bộ dữ liệu T10I4D100K 54

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 57

1. Kết luận 57

2. Hướng phát triển 57

TÀI LIỆU THAM KHẢO 59