Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến

Chia sẻ: Bobietbo | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

30
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn "Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến" được hoàn thành với mục tiêu là 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. Tiếp sau đó người nghiên cứu sẽ tiến hành giai đoạn thứ hai: tập trung tìm hiểu và nghiên cứu thuật toán khai thác tập phổ biến đầy đủ theo chiều ngang, trong thuật toán có sử dụng ma trận bit để nén tập dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH NGUYỄN QUÝ TÍN PHƯƠNG PHÁP KHAI THÁC THEO CHIỀU NGANG ĐỂ TRÍCH XUẤT CÁC TẬP PHỔ BIẾN LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Mã số: 60480201 TP. HỒ CHÍ MINH – tháng 06 năm 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH NGUYỄN QUÝ TÍN PHƯƠNG PHÁP KHAI THÁC THEO CHIỀU NGANG ĐỂ TRÍCH XUẤT CÁC TẬP PHỔ BIẾN LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Mã số: 60480201 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. CAO TÙNG ANH TP. HỒ CHÍ MINH – tháng 06 năm 2019
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH Người hướng dẫn khoa học: TS. Cao Tùng Anh - Học viên đã bảo vệ thành công luận văn ngày 04 tháng 06 năm 2019, tại Hội đồng đánh giáluận văn thạc sĩ thành lập theo Quyết định số …. ngày …. /…./2019 của Hiệu trưởng Trường ĐH Ngoại ngữ -Tin học TP.HCM, với sự tham gia của: Chủ tịch Hội đồng: PGS.TS. Phạm Thế Bảo Phản biện 1: TS. Trần Minh Thái Phản biện 2: PGS.TS. Lê Hoàng Thái Ủy viên: PGS.TS Nguyễn Thanh Bình Thư ký: TS. Nguyễn Đức Cường - Có thể tìm hiểu Luận văn tại Thư viện Trường ĐH Ngoại ngữ-Tin học TP HCM, hoặc trên cổng thông tin điện tử, website của đơn vị quản lý sau đại học của Trường.
LỜI CAM ĐOAN Tôi xin cam đoan nội dung của luận văn này là công trình nghiên cứu của chính bản thân tôi. Tất cả các tài liệu tham khảo từ các nghiên cứu có liên quan đều đã được nêu rõ nguồn gốc trong phần tài liệu tham khảo. Các số liệu, kết quả nêu trong luận văn do tôi tự thực nghiệm. Tác giả luận văn Nguyễn Quý Tín i
LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc đến Thầy, TS. Cao Tùng Anh, người đã hết lòng hướng dẫn, động viên và giúp đỡ cho tôi hoàn thành luận văn này. Tôi cũng xin chân thành gửi lời cám ơn đến quý Thầy Cô trường Đại Học Ngoại ngữ - Tin học TP.HCM đã tận tình dạy dỗ, chỉ bảo kiến thức quý báu giúp tôi hoàn thành khóa học đúng tiến độ và là nền tảng cho nghiên cứu của mình. Xin cảm ơn Ban Hợp tác và Đào tạo Sau đại học đã nhiệt tình hỗ trợ trong suốt quá trình học tập tại trường. Cuối cùng, xin chân thành cảm ơn cha mẹ, vợ, bạn bè và đồng nghiệp đã khích lệ, động viên, tạo điều kiện thuận lợi cho tôi trong suốt thời gian thực hiện luận văn. TP. HCM, tháng 06 năm 2019 Tác giả luận văn Nguyễn Quý Tín ii
TÓM TẮT 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ể. iii
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT KÍ HIỆU Ý NGHĨA TIẾNG ANH Ý NGHĨA TIẾNG VIỆT BFS Breadth First Search Tìm kiếm theo chiều rộng cond Conditional Điều kiện CSDL Database Cơ sở dữ liệu Transaction database of Cơ sở dữ liệu giao tác có điều DB conditional database kiện Transaction database of Cơ sở dữ liệu giao tác có điều DB|i conditional database i kiện i DFS Depth-first search Tìm kiếm theo chiều sâu F.C.I Frequent closed itemset Tập phổ biến đóng FI Frequent Itemset Tập phổ biến FP-array Frequent Pairs Array Mảng phổ biến FP-Tree Frequent Pattern Tree Cây phổ biến Item Items Hạng mục Itemset Itemset Tập hạng mục minsup Minsup Độ phổ biến tối thiểu Thuật toán khai thác theo MRIH Mining Row Item Horizontal phương pháp ngang Thuật toán khai thác tập phổ Principle of Inclusion– biến dựa trên nguyên lý Bao PIETM Exclusion and Transaction gồm - Loại trừ và ánh xạ giao Mapping tác rowset Rowset Tập dòng sup Support Độ phổ biến TDB Transaction Database Cơ sở dữ liệu giao tác tid Transaction ID Mã giao tác tid-list Transaction ID-List Danh sách mã giao tác iv
DANH MỤC CÁC BẢNG Bảng 2.1 Cơ sở dữ liệu mẫu .................................................................................................. 7 Bảng 2.2 Cơ sở dữ liệu mẫu hạng mục được sắp xếp............................................................ 9 Bảng 2.3 Minh họa dữ liệu định dạng theo chiều dọc ......................................................... 10 Bảng 2.4 Minh họa dữ liệu biểu diễn bằng ma trận bit ....................................................... 11 Bảng 2.5 Các tập phổ biến có 1 danh mục........................................................................... 13 Bảng 2.6 Các tập phổ biến có 2 danh mục........................................................................... 14 Bảng 2.7 Các tập phổ biến có 3 danh mục........................................................................... 14 Bảng 2.8 Các tập phổ biến có 4 danh mục........................................................................... 15 Bảng 2.9 Cơ sở dữ liệu dùng làm dữ liệu xây dựng cây FP-Tree........................................ 17 Bảng 2.10 Minh họa các hạng mục phổ biến trong mỗi giao tác ........................................ 17 Bảng 2.11 Bảng kết quả cây FP-Tree điều kiện từ mỗi cơ sở mẫu điều kiện ...................... 23 Bảng 2.12 CSDL giao tác gồm 5 giao tác và 5 hạng mục ................................................... 26 Bảng 2.13 CSDL giao tác gồm 8 giáo tác và 17 hạng mục ................................................. 31 Bảng 2.14 Danh sách các khoảng giao tác........................................................................... 33 Bảng 2.15 Kết hợp các khoảng giao tác .............................................................................. 34 Bảng 2.16 Khai thác tập phổ biến bằng PIETM .................................................................. 35 Bảng 3.1 Tập dữ liệu D được cắt tỉa với minsup=2. ............................................................ 42 Bảng 3.2 Ma trận bit tập dữ liệu giao tác I ........................................................................... 46 Bảng 3.3 Ma trận bit D sau khi lược bỏ các cột không thỏa minsup = 2............................. 47 Bảng 3.4 Ma trận bit d-cond D sau khi lược bỏ cột d với minsup = 2 ................................ 47 Bảng 3.5 Ma trận bit chuyển đổi từ tập phần tử tương ứng với bảng 3.4 ............................ 47 Bảng 3.6 Ma trận bit Tỉa d-cond D ...................................................................................... 47 Bảng 4.1 Bảng mô tả CSDL mẫu (Dataset.txt).................................................................... 51 Bảng 4.2 Bảng mô tả các CSDL .......................................................................................... 51 v
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 vi
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ề. vii
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 HỌC VIÊN (ký tên, họ và tên) (ký tên, họ và tên) TS. Cao Tùng Anh Nguyễn Quý Tín viii
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 ix
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 HỌC CỦA TÁC GIẢ LUẬN VĂN ..................................................... 57 TÀI LIỆU THAM KHẢO ................................................................................................... 58 PHỤ LỤC............................................................................................................................ 60 x
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. 1
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 đã 2
đượ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. 3
- Tiếp sau đó người nghiên cứu sẽ tiến hành giai đoạn thứ hai: tập trung tìm hiểu và nghiên cứu thuật toán khai thác tập phổ biến đầy đủ theo chiều ngang, trong thuật toán có sử dụng ma trận bit để nén tập dữ liệu. Bên cạnh đó, sử dụng phương pháp phân chia và cắt tỉa nhằm lược bỏ các giao tác không thỏa độ phổ biến để rút ngắn thời gian khai thác các tập phổ biến cũng được áp dụng, cuối cùng là cài đặt thuật toán và đánh giá kết quả thực nghiệm. Với mục tiêu này, phạm vi nghiên cứu của luận văn là các thuật toán về khai thác tập phổ biến, khai thác dữ liệu duyệt theo hạng mục từ dưới lên, kỹ thuật phân chia và cắt tỉa, sau đó là xây dựng chương trình thực nghiệm để đánh giá kết quả đạt được. 1.3. Phương pháp nghiên cứu Nghiên cứu tổng quan về khai thác dữ liệu, khai thác tập phổ biến và tiến hành nghiên cứu các tài liệu có liên quan đến luận văn. Tìm hiểu các thuật toán khai thác tập phổ biến để tìm các phương pháp khai thác trong cơ sở dữ liệu có số lượng lớn các giao tác. Xây dựng chương trình thực nghiệm và kiểm chứng, đánh giá kết quả đạt được. 1.3.1. Phương pháp nghiên cứu tài liệu - Nghiên cứu các tài liệu và bài báo liên quan là cơ sở lý luận của luận văn. - Nghiên cứu các cách tiếp cận, các kỹ thuật, các phương pháp, hiện trạng đã được công bố của các tác giả trong và ngoài nước có liên quan đến lĩnh vực khai thác tập phổ biến nói riêng và lĩnh vực khai thác tập phổ biến trong khai thác dữ liệu nói chung. - Nghiên cứu các xu thế và hướng phát triển tương lai liên quan đến luận văn. - Nghiên cứu các tài liệu khác liên quan phục vụ cho việc nghiên cứu của luận văn. 1.3.2. Phương pháp thực nghiệm - Tiến hành thực nghiệm trên các bộ dữ liệu thực tế và bộ dữ liệu chuẩn để so sánh kết quả với kết quả của các phương pháp đã công bố trong và ngoài nước có liên quan đến luận văn. 1.3.3. Phương pháp thống kê, phân tích dữ liệu - Thống kê, tổng hợp các số liệu trong quá trình thực nghiệm để từ đó phân tích, đánh giá và đưa ra những kết luận hoặc điều chỉnh nội dung nghiên cứu. 4
1.4. Bố cục luận văn Luận văn được trình bày trong năm chương và tài liệu tham khảo với cấu trúc như sau: Chương 1: Tổng quan Chương này trình bày tổng quan về lĩnh vực nghiên cứu. Chương 2: Cơ sở lý thuyết Trong chương này, luận văn sẽ trình bày một số khái niệm, định nghĩa và tính chất của tập phổ biến, tập phổ biến đóng một số tiếp cận trong khai thác tập phổ biến. Ngoài ra, trong chương cũng trình bảy các thuật toán làm cơ sở nghiên cứu cho chương tiếp theo. 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 Trong chương này, luận văn sẽ trình bày các nghiên cứu về sử dụng cấu trúc vector bit trong khai thác dữ liệu, sử dụng phương pháp chia để trị và cắt tỉa trong khai thác ngang. Chương 4: Kết quả thực nghiệm và đánh giá Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu. Chương 5: Kết luận Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu. 1.5. Kết luận chương Các dữ liệu có ích tồn tại trong các CSDL có ý nghĩa rất lớn trong nhiều ngành, lĩnh vực. Do đó việc phát hiện và trích xuất các dữ liệu tìm ẩn từ các tập dữ liệu lớn ngày càng trở nên cần thiết, đặc biệt trong gia đoạn hiện nay khi mà sự phát triền nhanh chóng của các ứng dụng công nghệ thông tin ở nhiều lĩnh vực trong đời sống xã hội. Trong chương này, luận văn trình bày tổng quan về lĩnh vực nghiên cứu khai thác dữ liệu. Trong khai thác dữ liệu, kỹ thuật khai tác tập phổ biến là một trong những lĩnh vực đang được quan tâm và nghiên cứu mạnh mẽ. 5
Chương 2. CƠ SỞ LÝ THUYẾT 2.1. Giới thiệu tổng quan Bài toán xác định luật kết hợp lần đầu tiên được Agrawal. R [3] giới thiệu vào năm 1993. Khai phá luật kết hợp là một kỹ thuật được sử dụng trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuyên xuất hiện lặp đi lặp lại (hay phổ biến) trong cơ sở dữ liệu, từ đó rút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác. Các thuật toán khai phá luật kết hợp tìm kiếm các mối liên kết giữa các phần tử trong cơ sở dữ liệu. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến hay phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có. Chúng ta xem xét một bài toán về khai phá luật kết hợp như sau: phân tích hóa đơn mua hàng của khách hàng khi đi siêu thị. Việc khai phá luật kết hợp trong bài toán này nhằm tìm ra các luật kết hợp giữa các mặt hàng mà khách hàng đã mua. Thí dụ một số luật kết hợp rút ra được sau khi phân tích hóa đơn khách hàng mua: 60% khách hàng mà mua “bánh mì” tại siêu thị thì đều mua “sữa” chúng ta thấy có sự kết hợp giữa “bánh mì” với “sữa”. Những luật kết hợp như vậy rất có ích trong việc giúp các nhà quản lý nắm bắt được thói quen mua hàng của khách hàng khi mua một (hoặc một số) mặt hàng này thì khách hàng có xu hướng mua thêm một số mặt hàng nào nữa. Từ đó đề ra những chiến lược quản lý hợp lý. Như vậy, khai phá luật kết hợp có thể giải quyết được bài toán hết sức đời thường như: khách hàng vào siêu thị sẽ mua mặt hàng nào? Những mặt hàng nào mà khách hàng kết hợp cùng mua. Tất nhiên, khai phá luật kết hợp cũng có nhiều ý nghĩa trong các lĩnh vực khác như tài chính, y học, công nghệ… Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao tác lớn của một cơ sở dữ liệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thường xuyên) như thế nào. Bài toán tìm luật kết hợp là bài toán cơ bản trong khai thác dữ liệu gồm hai bước chính: Bước 1: Tìm tất cả các tập phổ biến theo ngưỡng phổ biến cho trước, Bước 2: Tìm ra luật kết hợp dựa vào tập phổ biến đã tìm thấy ở Bước 1. Nội dung luận văn này cũng đi sâu vào nghiên cứu thuật toán để tìm các tập phổ biến hiệu quả hơn. 6
2.2. Các khái niệm và định nghĩa 2.2.1. Hạng mục Cho I là một tập các thuộc tính nhị phân. Cho I = {I1, I2, …, Im}, mỗi Ik (1km) là một hạng mục. 2.2.2. Tập hạng mục Một tập 𝑋 ⊆ 𝐼 là một tập các hạng mục. 2.2.3. Cơ sở dữ liệu giao tác Một CSDL giao tác là một tập gồm nhiều hạng mục, mỗi hạng mục là một giao tác được định danh bởi một giá trị duy nhất là mã giao tác. Một CSDL giao tác trên I là một tập các định danh giao tác T = {t1, t2,…,tn}, với ti (1in) là một định danh giao tác trên I chứa một tập các danh mục dữ liệu X ⊆ I. Ví dụ 2.1: Trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lần mua hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những mặt hàng nào. Mã giao tác Nội dung giao tác 1 a, b, d, e 2 b, c, e 3 a, b, d, e 4 a, b, c, e 5 a, b, c, d, e 6 b, c, d Bảng 2.1 Cơ sở dữ liệu mẫu 2.2.4. Độ phổ biến Cho CSDL bao gồm: Tập các danh mục I, tập danh mục X  I và tập các giao tác D Độ phổ biến của X trong D có ký hiệu là sup(X) và được định nghĩa là số giao tác mà X xuất hiện trong D. Ví dụ 2.2: Sử dụng CSDL ví dụ 2.1 với số lượng 6 giao tác. Tập danh mục {a, b, c, d, e} Với CSDL mẫu trong bảng 2.1, thì ta có: 7