Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 2

DANH MỤC CÁC HÌNH

Hình 2.1 Thuật toán Apriori 12

Hình 2.2 Lưu đồ thuật toán xây dựng cây FP-Tree (bước 1) 16

Hình 2.3 Lưu đồ thuật toán xây dựng cây FP-Tree (bước 2) 16

Hình 2.4 Minh họa các bước xây dựng cây FP-Tree 18

Hình 2.5 Header table của cây FP-Tree 19

Hình 2.6 Cơ sở mẫu điều kiện cho nút p 20

Hình 2.7 Cơ sở mẫu điều kiện kiện cho nút m 21

Hình 2.8 Cơ sở mẫu điều kiện cho các nút của cây FP-Tree 21

Hình 2.9 Cây FP-Tree cho tập phổ biến của cơ sở mẫu điều kiện cho p 22

Hình 2.10 Cây FP-Tree cho tập phổ biến của mẫu cơ sở điều kiện cho m 22

Hình 2.11 Tất cả mẫu phổ biến liên quan đến p là: p:3 và cp:3 23

Hình 2.12 Tất cả mẫu phổ biến liên quan đến m là: m:3, fm:3, cm:3, am:3, fcm3:, fam:3, cam:3, fcam:3 24

Hình 2.13 Thuật toán CLOSET 25

Hình 2.14 Thuật toán CLOSET khai thác tập phổ biến đóng 26

Hình 2.15 Thuật toán Apriori, FP-Growth và PIETM 30

Hình 2.16 Thuật toán PIETM 30

Hình 2.17 Hàm Union_Intervals 31

Hình 2.18 Ví dụ xây dựng cây FP-Tree và các khoảng giao tác 32

Hình 2.19 Các thành phần của tập phổ biến đóng 36

Hình 2.20 Ví dụ cây FP-Tree 36

Hình 3.1 Biễu diễn cây tìm kiếm từ dưới lên 40

Hình 3.2 Biểu diễn cây tìm kiếm từ trên xuống 41

Hình 3.3 Mở rộng mục d, b, c trong không gian tìm kiếm của thuật toán ngang của tập dữ liệu bảng 3.1 42

Hình 3.4 Loại bỏ mục d, b, a, c của tập dữ liệu D 44

Hình 3.5 Loại bỏ b|a, b|c của tập dữ liệu cắt tỉa b-cond 45

Hình 3.6 Thuật toán MRIH 48

Hình 3.7 Khai thác tất cả hạng mục của tập dữ liệu D 49

Hình 4.1 Kết quả thực nghiệm với CSDL T10I4D100K (D1) 52

Hình 4.2 Kết quả thực nghiệm với CSDL T40I10D100K (D2) 52

Hình 4.3 Kết quả thực nghiệm với CSDL Retail 53

Hình 4.4 Kết quả thực nghiệm với CSDL Mushroom 54

Hình 4.5 Kết quả thực nghiệm với CSDL Accident 54

TRANG THÔNG TIN VỀ LUẬN VĂN THẠC SĨ

1. Họ tên học viên: NGUYỄN QUÝ TÍN Nam/ Nữ: Nam

2. Ngày tháng năm sinh: 08 tháng 4 năm 1980 Nơi sinh: TP.HCM

3. Ngành học: Công nghệ Thông tin Mã số: 604802015

4. Ngày nhập học: 6/2016

5. Các thay đổi trong quá trình đào tạo: (nếu có)

6. Tên đề tài luận văn (chính thức bảo vệ):

6.1. Tiếng việt: Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến

6.2 Tiếng Anh: Horizontal method for efficient frequent pattern mining

7. Cán bộ hướng dẫn (họ tên, học hàm, học vị): TS. CAO TÙNG ANH

8. Tóm tắt các kết quả của luận văn:

Khai thác tập phổ biến là một trong những phương pháp khai thác dữ liệu quan trọng nhất được sử dụng rộng rãi để trích xuất các quy tắc kết hợp hiệu quả từ khối lượng lớn dữ liệu. Một số thuật toán đã được đề xuất để khai thác các tập phổ biến như: Apriori, FP-Growth,… được áp dụng trong nhiều lĩnh vực. Vì thuật toán khai thác tập phổ biến truyền thống tạo ra một số lượng lớn các tập phổ biến. Hơn nữa, sự bùng nổ tổ hợp của các tập hợp trong bộ dữ liệu rất lớn làm khó khăn thêm trong khai thác. Trong luận văn này sẽ nghiên cứu cài đặt một thuật toán hiệu quả hơn, để tiến hành khai thác các tập phổ biến trong các tập dữ liệu rất lớn. Thuật toán Mining Row Item Horizontal (MRIH), sử dụng phương pháp khai thác từ dưới lên theo chiều ngang để thiết lập một sự cân bằng giữa kích thước ngang và dọc của cơ sở dữ liệu đầu vào của mỗi cấp khai thác. Với mục đích này, mỗi cơ sở dữ liệu sẽ được sắp xếp theo thứ tự tăng dần độ phổ biến của các hạng mục. Trong thuật toán, cơ sở dữ liệu giao tác chính được chia thành một số cơ sở dữ liệu nhỏ hơn và do đó giảm kích thước của vấn đề khai thác ở mỗi cấp. Kết quả thử nghiệm cho thấy rằng thuật toán đạt được hiệu quả khai thác tốt trên một số các tập dữ liệu đầu vào khác nhau. Hơn nữa, nghiên cứu về hiệu suất cho thấy rằng thuật toán này tốt hơn đáng kể.

9. Khả năng ứng dụng thực tiễn:

Ứng dụng phương pháp khai thác ngang kết hợp với các phương pháp xử lý ngôn ngữ tự nhiên để xây dựng ứng dụng phân tích dữ liệu tiếng việt được thu thập từ Facebook; xem xét dữ liệu nào liên quan tới học sinh phổ thông, xử lý thông tin đưa ra định hướng tư vấn cho học sinh phổ thông lựa chọn học nghề.

10. Những hướng nghiên cứu tiếp theo:

Nghiên cứu áp dụng phương pháp khai thác song song dựa trên vector bit động vào thuật toán để xử lý song song trong mô hình chia để trị làm tăng hiệu quả cho thuật toán này

11. Các công trình đã công bố có liên quan đến luận văn:

- Bài toán xác định luật kết hợp lần đầu tiên được Agrawal. R giới thiệu 1993 và sau đó được giải quyết trên cơ sở thuật toán Apriori [3].

- Thuật toán FP-Growth [4] được Han và các cộng sự đề xuất vào năm 2000. Thuật toán này tiếp tục được cải tiến với tên gọi là FP-Growth* [5] vào năm 2005 bởi các tác giả Grahne và Zhu.

- Khai thác tập phổ biến đóng có các công trình tiêu biểu như sau: Closet [6], Mafia[7].

- Khai thác tập phổ biến lớn là một giải pháp thay thế tốt cho vấn đề bùng nổ tập phổ biến [8,9].

- Các thuật toán khai thác sử dụng các kỹ thuật nén bằng bitmap [10-11].

- Thuật toán Erasable Itemsets fully [12] đề xuất một thuật toán hiệu quả sử dụng kỹ thuật phân chia và cắt tỉa để khai thác các hạng mục hoàn toàn có thể xoá được.

- Thuật toán MFS_DoubleCons [13] là khai thác các tập phổ biến với các ràng buộc kép được đề xuất.

- Thuật toán GENCLOSE [14] là một thuật toán hiệu quả khai thác các tập phổ biến và các tập phổ biến đóng bằng một tìm kiếm ngang trên một cây được xây dựng đặc biệt.

- Thuật toán Disclosed [15] là thuật toán hiệu quả đầu tiên khai thác theo chiều sâu, từ trên xuống cho các tập phổ biến đóng.

- Thuật toán khai thác các tập phổ biến PIETM [16] dựa trên nguyên lý Bao gồm- Loại trừ và ánh xạ giao tác.

CÁN BỘ HƯỚNG DẪN

(ký tên, họ và tên)

TS. Cao Tùng Anh

HỌC VIÊN (ký tên, họ và tên) Nguyễn Quý Tín

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

• Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 1
• Phương Pháp Khai Thác Theo Chiều Ngang Để Trích Xuất Các Tập Phổ Biến
• Một Số Thuật Toán Khai Thác Tập Phổ Biến
• Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 5

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

MỤC LỤC

LỜI CAM ĐOAN i

LỜI CẢM ƠN ii

TÓM TẮT iii

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT iv

DANH MỤC CÁC BẢNG v

TRANG THÔNG TIN VỀ LUẬN VĂN THẠC SĨ vii

MỤC LỤC ix

Chương 1. TỔNG QUAN 1

1.1. Đặt vấn đề 1

1.2. Mục tiêu và phạm vi nghiên cứu 3

1.3. Phương pháp nghiên cứu 4

1.3.1. Phương pháp nghiên cứu tài liệu 4

1.3.2. Phương pháp thực nghiệm 4

1.3.3. Phương pháp thống kê, phân tích dữ liệu 4

1.4. Bố cục luận văn 5

1.5. Kết luận chương 5

Chương 2. CƠ SỞ LÝ THUYẾT 6

2.1. Giới thiệu tổng quan 6

2.2. Các khái niệm và định nghĩa 7

2.2.1. Hạng mục 7

2.2.2. Tập hạng mục 7

2.2.3. Cơ sở dữ liệu giao tác 7

2.2.4. Độ phổ biến 7

2.2.5. Tập phổ biến: 8

2.2.6. Tập phổ biến đóng 8

2.2.7. Các tính chất của tập phổ biến 9

2.2.8. Cách biểu diễn dữ liệu 10

2.3. Một số thuật toán khai thác tập phổ biến 12

2.3.1. Thuật toán Apriori 12

2.3.2. Thuật toán FP-Growth 15

2.3.3. Thuật toán CLOSET 25

2.3.4. Thuật toán BitTableFI 29

2.3.5. Thuật toán PIETM 29

2.4. Một số chiến lược khai thác tập phổ biến 36

2.4.1. Phương pháp tìm kiếm theo chiều rộng và theo chiều sâu 36

2.4.2. Định dạng theo chiều ngang và định dạng theo chiều dọc 37

2.4.3. Kỹ thuật nén dữ liệu 37

2.4.4. Kỹ thuật loại bỏ để khai thác tập phổ biến 38

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

Chương 3. PHƯƠNG PHÁP KHAI THÁC THEO CHIỀU NGANG ĐỂ TRÍCH XUẤT CÁC TẬP PHỔ BIẾN 40

3.1. Khai thác dữ liệu theo cấu trúc cây tìm kiếm 40

3.1.1. Cây tìm kiếm duyệt theo giao tác 40

3.1.2. Cây tìm kiếm duyệt theo hạng mục 41

3.2. Phương pháp khai thác ngang 43

3.2.1. Sử dụng phương pháp chia để trị trong khai thác ngang 43

3.2.2. Định nghĩa 1: 44

3.2.3. Định nghĩa 2: 44

3.2.4. Định nghĩa 3: 45

3.3. Biểu diễn tập dữ liệu trên ma trận bit 45

3.4. Thuật toán MRIH 48

3.5. Minh họa thuật toán trên dữ liệu mẫu 49

3.6. Kết luận chương 50

Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ THUẬT TOÁN 51

4.1. Mô tả dữ liệu 51

4.2. Kết quả chương trình thực nghiệm 52

4.3. Kết luận chương 55

Chương 5. KẾT LUẬN 56

CÔNG BỐ KHOA HỌC CỦA TÁC GIẢ LUẬN VĂN 57

TÀI LIỆU THAM KHẢO 58

PHỤ LỤC 60

Chương 1. TỔNG QUAN

1.1. Đặt vấn đề

Trong những năm gần đây nhu cầu thu thập, lưu trữ, phân tích dữ liệu được đặt ra đòi hỏi phải xử lý thông minh và hiệu quả. Từ đó đã làm phát triển kỹ thuật mới và với kỹ thuật mới này cho phép chúng ta khai thác tích cực từ nguồn dữ liệu rất lớn được gọi là khai phá dữ liệu. Việc nghiên cứu khai phá dữ liệu là một trong những lĩnh vực rất quan trọng trong thế kỷ hiện nay, được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau. Trong thực tế dữ liệu tồn tại rất phổ biến trong các lĩnh vực như: giáo dục, y tế, khoa học kỹ thuật, kinh tế, xã hội... Chính vì nguồn dữ liệu vô cùng lớn, do đó việc khai thác dữ liệu có ích rất quan trọng và là việc cần thiết. Mục đích chính của khai phá dữ liệu là tìm kiếm và phát hiện tất cả các dữ liệu lặp đi lặp lại trong một CSDL theo yếu tố thời gian.

Trong đó việc khai thác tập phổ biến (FI) đóng vai trò rất quan trọng trong quá trình khai thác luật kết hợp và tốn rất nhiều thời gian khai thác. Vì vậy các công trình hiện nay đều tập trung nghiên cứu các thuật toán khai thác tập phổ biến. Luận văn sẽ tập trung nghiên cứu về thuật toán khai thác tập phổ biến.

Bài toán xác định luật kết hợp lần đầu tiên được Agrawal. R giới thiệu và sau đó được giải quyết trên cơ sở thuật toán Apriori [3]: Tác giả trình bày tính chất Apriori về tập phổ biến làm nền tảng cho các thuật toán sau này. Ý tưởng cơ bản của thuật toán này là khai thác các tập phổ biến 1-itemset, sau đó sinh ứng viên 2-itemset dựa trên tập phổ biến 1-itemset. Từ tập ứng viên 2-itemset sẽ lấy ra các tập phổ biến 2- itemset. Thuật toán duyệt cơ sở dữ liệu nhiều lần và tốn chi phí loại bỏ ứng viên.

Thuật toán FP-Growth [4] được Han và các cộng sự đề xuất vào năm 2000 sử dụng cấu trúc FP-Tree để nén cơ sở dữ liệu và từ đó xác định tập phổ biến. Ưu điểm của thuật toán là không sinh ứng viên và chỉ quét cơ sở dữ liệu hai lần. Thuật toán này tiếp tục được cải tiến với tên gọi là FP-Growth* [5] vào năm 2005 bởi các tác giả Grahne và Zhu. Thuật toán FP-Growth* sử dụng kỹ thuật FP-array làm giảm đáng kể quá trình duyệt cây FP-tree, do đó hiệu suất được cải thiện đáng kể cho các thuật toán dựa trên FP-tree, và thuật toán này hoạt động tốt đối với các tập dữ liệu thưa thớt. Tuy nhiên thuật toán FP-Growth* cũng gặp nhược điểm đó là tiêu tốn nhiều bộ nhớ khi các tập dữ liệu thưa thớt.

Thách thức lớn nhất trong khai thác tập phổ biến là tất cả tập con của một tập phổ biến cũng phổ biến, số tập con này tăng theo số mũ, kết quả thu được là một số lượng quá lớn các tập phổ biến. Do vậy khai thác tập phổ biến đóng sẽ hữu ích trong trường hợp này. Tập phổ biến đóng là tập phổ biến thỏa điều kiện không tồn tại tập phổ biến cha có cùng độ phổ biến với nó. Điều kiện này làm số lượng tập phổ biến đóng nhỏ hơn rất nhiều so với số lượng tập phổ biến. Khai thác tập phổ biến đóng có các công trình tiêu biểu như sau: Thuật toán Closet [6] là mở rộng của thuật toán FP- growth, trong đó xây dựng một cây FP-Tree và đệ quy có điều kiện cây FP-Tree từ dưới lên. Mặc dù thuật toán Closet sử dụng một số kỹ thuật tối ưu hóa để nâng cao hiệu quả hoạt động khai thác, hiệu quả của nó vẫn chưa cao trong bộ dữ liệu thưa thớt hoặc khi ngưỡng phổ biến thấp. Thuật toán Mafia [7] là thuật toán khai thác các tập phổ biến tối đại. Thuật toán tích hợp tìm kiếm theo chiều sâu trên dàn tập mục, và dùng 3 cách để loại bỏ các tập không phổ biến tối đại. Cơ sở dữ liệu của thuật toán được biểu diễn dạng vectơ bit theo chiều dọc. Thuật toán đặc biệt hiệu quả khi các tập phổ biến trong CSDL là rất dài.

Mặc dù khai thác tập phổ biến đóng đã giảm số lượng tính toán và số lượng đầu ra của quá trình khai thác, nhưng vẫn tồn tại một vấn đề trong khai thác là tốn rất nhiều thời gian và không gian bộ nhớ khi tập dữ liệu khai thác có kích thước quá lớn. Do đó khai thác tập phổ biến có kích thước lớn là một giải pháp thay thế tốt cho vấn đề bùng nổ tập phổ biến [8-9]. Ý tưởng chính của khai thác tập phổ biến lớn là phương pháp khai thác tìm và chỉ trích xuất các tập phổ biến có quy mô lớn mà không khai thác các tập phổ biến có quy mô nhỏ và vừa. Tiếp cận này phù hợp cho những trường hợp không cần khai thác tất cả các tập phổ biến và rất hữu ích khi khai thác các tập phổ biến có kích thước lớn.

Hầu như tất cả các thuật toán khai thác tập phổ biến được trình bày gần đây đều sử dụng các ưu điểm của nguyên lý Apriori và thuật toán FP-Growth, và kết hợp chúng với các phương pháp và kỹ thuật mới, bao gồm các phương pháp tìm kiếm mới, cấu trúc dữ liệu hiện đại và kỹ thuật nén mới, các tập phổ biến của tập dữ liệu. Một trong những kỹ thuật quan trọng được sử dụng để cải tiến thuật toán khai thác là sử dụng các kỹ thuật nén bằng bitmap trên các bộ dữ liệu. Gần đây, nhiều nỗ lực đã

được đưa ra để áp dụng các kỹ thuật nén bằng bitmap trong các thuật toán khai thác [10-11].

Phương pháp phân chia và cắt tỉa được sử dụng để thực hiện khai thác tập phổ biến một cách hiệu quả [12-16]. Tác giả bài báo [12] đề xuất một thuật toán hiệu quả sử dụng kỹ thuật phân chia và cắt tỉa để khai thác các hạng mục hoàn toàn có thể xoá được. Thuật toán MFS_DoubleCons [13] là thuật toán khai thác các tập phổ biến với các ràng buộc kép được đề xuất. Thuật toán khai thác nhanh tất cả các tập phổ biến mà đáp ứng những ràng buộc từ mạng lưới các tập phổ biến đóng thay vì khai thác chúng trực tiếp từ cơ sở dữ liệu. Thuật toán GENCLOSE [14] là một thuật toán hiệu quả khai thác các tập phổ biến và các tập phổ biến đóng bằng cách khai thác ngang trên một cây được xây dựng đặc biệt. Còn đối với thuật toán Disclosed [15] là thuật toán hiệu quả đầu tiên khai thác theo chiều sâu, từ trên xuống cho các tập phổ biến đóng. Một thuật toán khai thác các tập phổ biến thường gọi là PIETM [16] được đề xuất, phát hiện ra các tập phổ biến theo cách từ dưới lên bằng hai lần quét cơ sở dữ liệu.

Từ những tài liệu nghiên cứu trên, luận văn tập trung nghiên cứu áp dụng kỹ thuật chia để trị và cắt tỉa trong khai thác theo chiều ngang sử dụng phương pháp tìm kiếm chiều sâu để trích xuất tất cả các tập phổ biến và lưu chúng theo định dạng nén dữ liệu. Phương pháp nén này cải thiện thời gian khai thác và giảm kích thước của tập đầu ra. Dưới đây là những đóng góp chính của luận văn này:

(1) Biểu diễn tập dữ liệu trên ma trận bit.

(2) Sử dụng phương pháp chia để trị và cắt tỉa để trong khai thác ngang giảm kích thước cơ sở dữ liệu giao tác và giải quyết vấn đề khai thác cho các tập dữ liệu lớn một cách hiệu quả.

(3) Phương pháp nén trích xuất để lưu các tập phổ biến được trích từ cơ sở dữ liệu giao tác được xây dựng để cải thiện thời gian khai thác và giảm kích thước của tập tin đầu ra.

1.2. Mục tiêu và phạm vi nghiên cứu

Từ những vấn đề nêu trên, mục tiêu đặt ra của luận văn là:

- Giai đoạn thứ nhất: tìm hiểu các kiến thức nền tảng về khai thác dữ liệu, khai thác tập phổ biến, thuật toán gốc Apriori và các cải tiến của Apriori.