Thạc Sĩ Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song

MỞ ĐẦU

Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác.

Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phương pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những thông tin bổ ích. Những “ tri thức ” chiết su ất từ n guồn cơ sở dữ liệu trên sẽ là nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. T iến hành công việc như vậy chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả năng tích hợp các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data Warehouse) [19, 24].

Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ biến là phát hiện các luật kế t hợp. Phương pháp này nhằm tìm ra các tập thuộc tính thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính khác như thế nào. Bên cạnh đó, nhu cầu song s ong hóa và xử lý phân tán là rất cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp.

Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích

thước dữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho luật kết hợp.

Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a trên các bài báo khoa ọhc trong một số hội thảo quốc tế và các bài báo chuyên ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật toán khai phá luật kết hợp song song.

Nội dung luận văn được trình bày trong 3 chương và phần kết luận

Chương 1: Tổng quan về k hai phá dữ liệu: Giới thiệu tổng quan về quá trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu.

Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp; các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp; khai phá luật kết hợp với một số khái niệm mở rộng.

Chương 3: Một số phương pháp khai phá luật kết hợp song song và phân tích đánh giá các thuật toán song song .




MỤC LỤC

Trang phụ bìa Trang
Lời cám ơn Lời cam đoan Mục lục
Danh mục các kí hiệu, các chữ viết tắt
Danh mục các hình vẽ

Mở đầu 1

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 3

1.1. Khái niệm 3

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

1.3. Các giai đoạn của quá trình khai phá dữ liệu 4

1.4. Một số kỹ thuật khai phá dữ liệu 6

1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 10

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

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

1.8. Khai phá dữ liệu và các lĩnh vực liên quan 14

1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu 15

1.10. 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. Mở đầu 17

2.2 Luật kết hợp 18

2.2.1 Các khái niệm cơ bản 18

2.2.2. Khai phá luật kết hợp 21

2.2.3. Cách tiếp cận khai phá luật kết hợp 22

2.3 Luật kết hợp cơ sở 24

2.3.1 Phát hiện các tập mục phổ biến 24

2.3.2 Sinh luật kết hợp 30

2.4. Khai phá luật kết hợp với một số khái niệm mở rộng 32

2.4.1. Giới thiệu 32

2.4.2. Khai phá luật kết hợp trọng số 32

2.4.3 Khai phá luật kết hợp tổng quát 43

2.5. Kết luận chương 2 49

Chương 3: MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP 50
SONG SONG VÀ PHÂN TÍCH ĐÁNH GIÁ CÁC THUẬT TOÁN
3.1. Nguyên lý thiết kế thuật toán song song 50

3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song 51

3.2.1. Mô hình song song dữ liệu 51

3.2.2. Mô hình song song thao tác 51

3.3. Một số thuật toán khai phá luật kết hợp song song
52
3.3.1 Thuật toán Count Distribution (CD)
52
3.3.2. Thuật toán Data Distribution (DD)
54
3.3.3. Thuật toán Candidate Distribution
58
3.3.4. Thuật toán song song Fp-Growth
60
3.3.5 Thuật toán song song Eclat
65
3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán
71
3.4.1. Phân tích và đánh giá thuật toán song song
71
3.4.2. So sánh việc thực hiện các thuật toán
73
3.5. Kết luận chương 3
74
Kết luận
75
Tài liệu tham khảo
77