B ô GIÁO DUC VÀ ĐÀO TAO • • • TRƯỜNG ĐẠI HỌC s PHẠM HÀ NỘI • • • • = = = D ÍIIg8 = = = LÊ THỊ THU HÀ KHAI PHÁ LUẬT KẾT HỢP TRÊN D ữ LIÊU DÃY Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: TS Nguyễn Long Giang HÀ NỘI, 2015 L Ờ I CẢM ƠN Bằng kính trọng lòng biết ơn sâu sắc, em xin trân thành cảm ơn T.s Nguyễn Long Giang, người tận tình hướng dẫn giúp đỡ em suốt trình nghiên cứu hoàn thành luận văn Em xin trân thành cảm ơn thầy cô khoa Công nghệ thông tin, phòng Sau đại học Trường Đại học Sư phạm Hà Nội 2, thầy cô trực tiếp giảng dạy toàn khóa học truyền thụ kiến thức quý báu tạo điều kiện thuận lợi cho em suốt trình học tập nghiên cứu trường Trong trình nghiên cứu, hoàn thiện luận văn khó tránh khỏi thiếu sót Rất mong nhận góp ý Quý thầy cô bạn bè đồng nghiệp quan tâm đến luận văn Vĩnh Phúc, ngày 06 tháng 12 năm 2015 Học viên Lê Thị Thu Hà L Ờ I CAM ĐOAN Tôi xin cam đoan kết nghiên cứu hướng dẫn khoa học TS Nguyễn Long Giang Các số liệu, kết nêu luận văn trung thực chưa công bố công trình khác Học viên Lê Thị Thu Hà MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN MỤC LỤC i DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIÉT TẮT iii DANH MỤC CÁC BẢNG iv DANH MỤC CÁC HÌNH V MỞ ĐẦU CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN .4 1.1 Các khái niệm b ả n 1.1.1 Cơ sở liệu giao tá c 1.1.2 Tập mục thường xuyên luật kết hợp 1.1.3 Các tính chất tập mục thường xuyên 1.1.4 Bài toán khai phá luật kết h ợ p 1.2 Thuật toán A priori 1.3 Thuật toán FP-Growth 12 1.4 Tập mục thường xuyên có trọng số sở liệu giao tác 19 1.5 Kết luận chương 21 CHƯƠNG 2: KHAI PHÁ MÂU DÃY THƯỜNG XUYÊN CÓ TRỌNG SỐ 23 2.1 Bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn h ó a 24 2.1.1 Các khái niệm b ả n 24 2.1.2 Cơ sở toán học cho toán khai phá mẫu dãy thường xuyên với trọng số chuẩn h ó a 25 2.1.3 Ví dụ minh họa 28 ii 2.2 Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa (WprefixSpan) 35 2.2.1 Mô tả thuật toán W prefixSpan 35 2.2.2 Độ phức tạp thuật toán W prefỉxSpan 36 2.3 Kết luận chương 37 CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ CÁC THUẬT TO Á N 38 3.1 Công cụ thử nghiệm 38 3.2 Số liệu thử nghiệm 38 3.3 Môi trường thử nghiệm .39 3.4 Ket thử nghiệm đánh giá thuật to n 39 3.4.1 So sánh thời gian thực thuật toán PreíixSpan WPrefixSpan 39 3.4.2 So sánh số mẫu dãy thường xuyên thuật toán PrefixSpan W PrefixSpan 40 3.4.3 So sánh nhớ sử dụng thuật toán PrefixSpan WPrefixSpan 40 3.4.4 So sánh độ dài mẫu dãy thường xuyên thuật toán PreíixSpan W PrefixSpan 41 3.5 Kết luận chương 41 KẾT LUẬN 43 TÀI LIỆU THAM KHẢO 44 PHỤ LỤC DANH MUC CÁC KÝ HIÊU, • « CÁC CHỮ VIÉT TẮT Ký hiệu, chữ viết tắt Diễn giải CSDL Cơ sở liệu TID Transction Identifcation w Tập trọng số mục L Tập tât mục thường xuyên ck Tập k-tập mục ứng viên Lk Tập k-tập mục thường xuyên SC(X) Số đếm hỗ trợ tập mục X WFIk Tập k-tập mục thường xuyên có trọng sô WFI Tập tât tập mục thường xuyên có trọng sô MaxW Trọng sô có giá trị lớn nhât CSDL giao tác MinW Trọng sô có giá trị nhỏ nhât tập mục điêu kiện min_weight Ngưỡng trọng sô thiêu min_sup Ngưỡng hô trợ thiêu support Độ hỗ trợ tập mục conf Độ tin cậy minconf Độ tin cậy cực tiểu DANH MUC CÁC BẢNG Bảng 1.1 Biểu diễn ngang sở liệu giao tá c Bảng 1.2 Biểu diễn dọc sở liệu giao tá c Bảng 1.3 Ma trận giao tác sở liệu bảng 1.1 Bảng 1.4 CSDL giao tác minh họa thực thuật toán Apriori 10 Bảng 1.5 CSDL giao tác minh họa cho thuật toán FP- growth 13 Bảng 1.6 CSDL giao tác 21 Bảng 1.7 Trọng số m ục 21 Bảng 2.1 Cơ sở liệu dãy s 28 Bảng 2.2 Giá trị trọng số mục liệu 28 Bảng 2.3 Cơ sở liệu điều kiện với tiền tố < a> 31 Bảng 2.4 Cơ sở liệu điều kiện với tiền tố < aa> 32 Bảng 2.5 Cơ sở liệu điều kiện với tiền tố 33 V DANH MUC CÁC HÌNH • Hình 1.2 Cây FP-tree xây dựng dàn thêm giao tác ti, t2, t3 .14 Hình 1.3 Cây FP-tree CSDL DB b ảng .15 Hình 1.4 FP-tree phụ thuộc m 17 Hình 1.5 Các FP-tree phụ thuộc am, cm c am 18 Hình 3.1 Thời gian thực thuật toán PreíixSpan WprefixSpan 39 Hình 3.2 Số mẫu dãy thường xuyên thuật toán PrefixSpan WprefixSpan 40 Hình 3.3 Bộ nhớ sử dụng thuật toán PrefixSpan W prefixSpan 40 Hình 3.4 Độ dài mẫu dãy thường xuyên thuật toán PrefixSpan WprefixSpan 41 MỞ ĐẦU Lý chọn đề tài Khai phá luật kết hợp (Mining association rules) toán quan trọng lĩnh vực khai phá liệu Khai phá luật kết hợp giới thiệu Agrawal [2] vào năm 1994 phân tích sở liệu bán hàng siêu thị, phân tích sở thích mua khách hàng cách tìm mặt hàng khác khách hàng mua lần mua Những thông tin giúp người quản lý kinh doanh tiếp thị chọn lọc thu xếp không gian bày hàng hợp lý hơn, giúp cho kinh doanh hiệu Bài toán khai phá luật kết hợp bao gồm hai toán Bài toán thứ tìm tập mục thường xuyên (Frequent itemset) thỏa mãn ngưỡng hỗ trợ tối thiểu cho trước, toán thứ hai sinh luật kết hợp (Association rule) thỏa mãn ngưỡng tin cậy cho trước từ tập mục thường xuyên tìm Mọi khó khăn toán khai phá luật kết hợp tập trung toán thứ nhất, khai phá tất tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước, nghiên cứu khai phá luật kết hợp phần lớn tập trung vào toán khai phá tập mục thường xuyên Bài toán khai phá tập mục thường xuyên Agrawal cộng đề xuất [2] gọi toán khai phá tập mục thường xuyên nhị phân giá toi mục liệu giao tác 1, tức quan tâm mục liệu có xuất giao tác hay không Do đó, toán mang ngữ nghĩa thống kê, không phản ánh vai trò khác thuộc tính đặc tính liệu vốn có chúng sở liệu Để đáp ứng yêu cầu thực tiễn, toán khai phá tập mục thường xuyên có nhiều cách thức mở rộng ứng dụng Một hướng mở rộng xem xét mức độ quan trọng khác mục liệu cách gán cho mồi mục giá trị gọi trọng số (số lượng giá trị tập mục) Khi đó, toán khai phá luật kết hợp kinh điển trở thành toán khai phá luật kết hợp có trọng số [3] Hướng mở rộng thu hút quan tâm nhà nghiên cứu khai phá luật kết hợp dãy liệu, gọi liệu dãy (sequence) Khi đó, toán khai phá tập mục thường xuyên trở thành toán khai phá mẫu dãy thường xuyên (Mining sequential patterns) toán khai phá luật kết hợp truyền thống trở thành toán khai phá luật kết hợp dãy [5, 6, 7, 8, 9] Khai phá luật kết hợp dãy có ứng dụng thực tiễn cao thực tế tồn phổ biến dãy liệu như: dãy liệu mua sắm khách hàng, dãy liệu mô tả nhật ký truy cập Website Như trình bày trên, hướng nghiên cứu mở rộng khai phá luật kết hợp liệu dãy có ý nghĩa khoa học thực tiễn cao Do đó, chọn đề tài “Khai phá luật kết hợp liệu dãy” Mục đích nghiên cứu Nắm bắt kiến thức tổng quan toán khai phá luật luật kết hợp kinh điển hướng nghiên cứu mở rộng khai phá luật kết hợp có trọng số liệu dãy Trên sở cài đặt, thử nghiệm, đánh giá thuật toán số liệu mẫu 3.Nhỉệm vụ nghiên cứu Nắm bắt khái niệm thuật toán khai phá luật kết hợp kinh điển Apriori, FP-Growth Tìm hiểu thử nghiệm thuật toán khai phá tập mục thường xuyên có trọng số sở liệu dãy, gọi khai phá mẫu dãy thường xuyên có trọng số Đối tượng phạm vỉ nghiên cứu - Đổi tượng nghiên cứu : Là sở liệu dãy - Phạm vi nghiên cứu : Nghiên cứu hướng mở rộng toán khai phá tập mục thường xuyên liệu dãy Phương pháp nghiên cứu - Nghiên cứu lý thuyết: Tìm hiểu khái niệm, thuật toán công bố khai phá mẫu dẫy thường xuyên có trọng số - Nghiên cứu thực nghiệm: Luận văn thực cài đặt thuật toán, chạy thử nghiệm đánh giá kết thực thuật toán Cấu trúc luận văn Luận văn gồm: Lời mở đầu, ba chương nội dung, phần kết luận, tài liệu tham khảo phụ lục 42 kiểm tra để thực tỉa mục ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa, cho phép giảm đáng kể không gian tìm kiếm đảm bảo tính phản đơn điệu giải thuật Với nhận xét kết thử nghiệm số liệu mẫu cho phép kết luận: thuật toán WPrefixSpan thuật toán hiệu để khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa 43 KẾT LUẬN Những kết luận văn 1) Tìm hiểu nắm bắt khái niệm toán khai phá luật kết hợp Nắm bắt thuật toán kinh điển Apriori thuật toán FP-Growth theo cấu trúc khai phá tập mục thường xuyên 2) Xây dựng thuật toán khai mẫu dãy thường xuyên với trọng số chuẩn hóa WprefixSpan dựa thuật toán khai phá mẫu dãy thường xuyên PrefixSpan [5] đưa vào trọng số tập mục 3) Thử nghiệm so sánh hai thuật toán PreíixSpan WprefixSpan dựa tiêu chí: thời gian thực hiện, số mẫu dãy thường xuyên thu được, nhớ sử dụng độ dài mẫu dãy thường xuyên Kết thử nghiệm cho thấy thuật toán WprefixSpan hiệu PreílxSpan bốn tiêu chí sử dụng Hướng nghiên cứu đề tài Áp dụng thuật toán khai phá mẫu dãy thường xuyên có trọng số chuẩn hóa xây dựng phương pháp khai phá luật kết hợp dãy có trọng số vào toán thực tiễn lĩnh vực kinh doanh, tài chính, ngân hàng 44 TÀI LIỆU THAM KHẢO Tiếng Việt: Nguyễn Huy Đức, Khai phá tập mục cổ phần cao lợi ích cao sở liệu, Luận án tiến sĩ toán học, Viện Công nghệ thông tin, 2010 Tiếng Anh: Agrawal R And Srikant R., “Fast algorithms for mining association rules”, in proceedings o f 20th International Conference on Very Large Databases, Santiago, Chile, 1994 C.H.Cai, A.W.Chee Fu, C.H.Cheng, and W.W.Kwong “Mining Association Rules with Weighted Items”, IDEAS '98 Proceedings o f the 1998 International Symposium on Database Engineering & Applications, pp.68-77, 1998 J.Han, J.Pei, and Y.Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings o f the 2000 ACM SIGMOD International Conference on Management o f Data, pp 1-12 J.Pei, J.Han, B.M.Asi, and H.Pino PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Patte Growth Proceedings o f the Seventeenth International Conference on Data Engineering:2\5-224, 2001 Zhuo Zhang, Lu Zhang, Shaochun Zhong, Jiwen Guan, A New Algorithm for Mining Sequential Pattern, FSKD 2008:625-629, 2008 Floriana Esposito, Nicola Di Mauro, Teresa Maria Altomare Basile, Stefano Ferilli, Multi-Dimensional Relatio Sequence Mining, Fundam Inform 89, 2008, pp 23-43 Yu Ning, Hongbin Yang, Sequence Mining for User Behavior Patterns in Mobile Commerce, CMECG ’08 Proceedin o f the 2008 International Conference on Management o f e-Commerce and e-Government: 2008, pp 6164 Ming-Yen Lin, Sue-Chen Hsueh, Ming-Hong Chen, Hong-Yang Hsu, Mining Sequential Patterns for Ima Classification in Ubiquitous Multimedia Systems, 45 Intelligent Information Hiding and Multimedia Signal Proccessi 2009(IIHM SP ’09), 2009, pp 303-306 10 The UCI machine learning repository, PHỤ LỤC Một sổ giao diện chương trình thử nghiệm Giao diện hình 'Ị Ị ỹ L uận v ă n th a c sỹ - Lê Thị Th-U Fjie Tham sá Tjụjâttoản Thuật toán kh ptìá tậ p m ụ c thường xuyên FP-Gr[...]... Bài toán khai phá luật kết hợp Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu mỉnsup và ngưỡng độ tin cậy tối thiểu minconf Yêu càu: Tìm tất cả các luật kết hợp X —» y trên cơ sở dữ liệu DB sao cho sup(X —> Y ) > minsup và conf(X —>Y) > m in c o n f Bài toán khai phá luật kết hợp này được gọi là bài toán cơ bản hay bài toán nhị phân, vì ở đây giá trị của mục dữ liệu trong cơ sở dữ liệu là... CHƯƠNG 2: KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN CÓ TRỌNG SỐ Khai phá mẫu dãy (Mining Sequential Patterns) là một trong những lĩnh vực rất quan trọng trong nghiên cứu khai phá dữ liệu và được áp dụng trong nhiều lĩnh vực khác nhau Trong thực tế các dữ liệu dãy tồn tại rất phổ biến, như dãy dữ liệu mua sắm của khách hàng, dữ liệu điều trị y tế, nhật ký truy cập web Mục đích chính của khai phá mẫu dãy là phát hiện... trong dãy s Một cơ sở dữ liệu dãy s = fS], s 2, S J là một tập các bộ dữ liệu (sid,S) với sid là định danh của một dãy và s k là một dãy dữ liệu Định nghĩa 1 (Độ hồ trợ của một dãy) : Độ hồ trợ của một dãy Sa trong một cơ sở dữ liệu dãy 5 là số lượng xuất hiện các bản ghi trong 5 có chứa dãy Sa Định nghĩa 2 (Trọng số chuẩn hóa của dãy) : Cho I - {ij, i2, in} là tập hợp các mục dữ liệu Mỗi mục ijŒ I được... dãy Khi đó, s = {sh s2, smỊ và Sj có dạng (ỈJỈ2 ik) và it là một mục dữ liệu Một dãy 5 bị loại nếu chỉ có duy nhất một mục dữ liệu Một mục dữ liệu chỉ xuất hiện nhiều hơn 1 lần trong 1 thành phần của một dãy Sj, nhưng có thể xuất hiện nhiều lần trong các thành phần của một dãy s Kích thước |S| của một dãy là số lượng của các thảnh phần trong dãy s Độ dài 1(S) của dãy là tổng số mục dữ liệu trong dãy. .. 1.4 Một luật kết hợp là một biểu thức dạng X —> y , trong đó X và Y là các tập con của I, X n Y— 0 ; X gọi là tiền đề, Y gọi là kết luận của luật Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy Định nghĩa 1.5 Độ hỗ trợ (Support) của một luật kết hợp X —> Y , ký hiệu là sup(X —> 7 ) , là độ hỗ trợ của tập mục X u Y , sup(X —» Y) = sup(Z u 7 j Như vậy độ hỗ trợ của luật kết hợp X ~^>Y... phá mẫu dãy chỉ tính toán đến số lần xuất hiện (độ hỗ trợ) mà không quan tâm đến mức độ quan trọng khác nhau của các mục dữ liệu Vì vậy, luận văn xây dựng thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa Luận văn không chỉ quan tâm đến số lần xuất hiện của các dãy (độ hồ trợ) mà còn quan tâm đến mức độ quan trọng khác nhau (trọng số) của chúng Trọng tâm chính đối với khai phá mẫu dãy thường... pháp khai phá phát triển (growth) từng đoạn dựa trên cây FP-tree gọi là phương pháp FP-growth (3) Kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia, “chia để trị”, phân rã nhiệm vụ khai phá thành các nhiệm vụ nhỏ hơn Thuật toán FP-growth do nén toàn bộ cơ sở dữ liệu lên một cấu trúc dữ liệu 13 nhỏ hơn là cây FP-tree nên tránh được việc duyệt nhiều lần cơ sở dữ liệu (thuật toán chỉ duyệt cơ sở dữ. .. và một danh sách các mục dữ liệu trong giao tác đó Ví dụ 1.1 Bảng 1.1 sau đây biểu diễn ngang của cơ sở dữ liệu giao tác Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác TID Mục dữ liệu TI B, c, D T2 B, c, D A, B, D T3 T4 C ,D ,F T5 c, D T6 A, c T7 A, B, c, F T8 A, c T9 A, B, E T10 A, E T ll A, B, c Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mồi mục dữ liệu có một danh sách tất... kiểm ưa tập dữ liệu nhiều lần, dẫn tới chi phí lớn khi kích thước các tập mục tăng lên Nếu tập mục có độ dài k được sinh ra thì cần phải kiểm tra tập dữ liệu k+1 lần - Lặp nhiều lần duyệt cơ sở dữ liệu, số làn duyệt cơ sở dữ liệu của thuật toán Apriori bằng độ dài của tập mục thường xuyên dài nhất tìm được Thuật toán Apriori chỉ thích hợp cho các cơ sở dữ liệu thưa (sparse), với các cơ sở dữ liệu dày... đặt, thử nghiệm và đánh giá thuật toán WprefixSpan trên một số bộ dữ liệu mẫu 4 CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN Chương này trình bày một số khái niệm cơ bản trong khai phá luật kết và hai thuật toán khai phá tập mục thường xuyên kinh điển: thuật toán Apriori [2] và thuật toán FP-Growth [4] 1.1 Các khái niệm Ctf bản 1.1.1 Ctf sở dữ liệu giao tác Định nghĩa 1.1 Cho tập các mục (item)