Luận văn Thạc sĩ Khoa học máy tính: Khai phá tập mục thường xuyên có trọng số trên cơ sở dữ liệu giao tác

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

Thêm vào BST

Báo xấu

32
lượt xem 20
download

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

luận văn có kết cấu chia làm 3 chương: Chương 1 - Tổng quan về khai phá dữ liệu; Chương 2 - Khai phá tập mục thường xuyên có trọng số; Chương 3 - Đánh giá các thuật toán và ứng dụng. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

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ĩ Khoa học máy tính: Khai phá tập mục thường xuyên có trọng số trên cơ sở dữ liệu giao tác

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN TÚ NAM KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dƣới sự hƣớng dẫn của TS Nguyễn Long Giang. Các số liệu, kết quả nghiên cứu trong luận văn là trung thực và mọi trích dẫn trong báo cáo đều đƣợc ghi rõ nguồn gốc. Nếu có sử dụng bất hợp pháp kết quả công trình nghiên cứu của ngƣời khác trong báo cáo tôi xin hoàn toàn chịu trách nhiệm. Tác giả Nguyễn Tú Nam Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
iii LỜI CẢM ƠN Lời đầu tiên tôi muốn bày tỏ lòng biết ơn sâu sắc và kính trọng của mình tới thầy giáo, TS Nguyễn Long Giang. Trong quá trình tìm hiểu nghiên cứu để hoàn thành luận văn tôi gặp không ít khó khăn, nhƣng những lúc nhƣ vậy tôi luôn nhận đƣợc sự động viên khích lệ của thầy. Thầy đã giúp đỡ tôi rất nhiều trong quá trình nghiên cứu, hƣớng dẫn tận tình trong cách thức và phƣơng pháp nghiên cứu khoa học cũng nhƣ hỗ trợ tôi trong việc tìm tài liệu. Để có đƣợc những kết quả trong luận văn này, tôi xin gửi lời cảm ơn sâu sắc đến Thầy, Cô Thái Nguyên đã tạo điều kiện cho tôi đƣợc học hỏi kiến thức thông qua các môn học cũng nhƣ hoàn thành khóa học. Cuối cùng tôi xin bày tỏ lòng cảm ơn chân thành đến gia đình, ngƣời thân và bạn bè đồng nghiệp đã khích lệ và động viên tôi hoàn thành luận văn này.! Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
iv MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ........................................................................................................... iii MỤC LỤC ................................................................................................................. iv Danh mục các ký hiệu, các chữ viết tắt ..................................................................... vi Danh mục các bảng .................................................................................................. vii Danh mục các hình .................................................................................................. viii MỞ ĐẦU .....................................................................................................................1 Chƣơng 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ...............................................3 1.1. Các khái niệm cơ bản trong khai phá luật kết hợp ...........................................4 1.1.1. Cơ sở dữ liệu giao tác .................................................................................4 1.1.2. Tập mục thƣờng xuyên và luật kết hợp ......................................................6 1.1.3. Bài toán khai phá luật kết hợp ....................................................................8 1.2. Một số thuật toán cơ bản khai phá tập mục thƣờng xuyên ...............................9 1.2.1. Cách tiếp cận khai phá tập mục thƣờng xuyên ..........................................9 1.2.2. Thuật toán Apriori ....................................................................................10 1.2.3. Thuật toán FP-growth ...............................................................................15 1.3. Một số hƣớng mở rộng bài toán khai phá tập mục thƣờng xuyên. .................24 1.4. Kết luận chƣơng ..............................................................................................24 Chƣơng 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ ..............25 ...............25 ...............................................................................25 ập mục thƣờng xuyên có trọng số dựa trên thuật toán Apriori ........................................................................................29 ......................................................32 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
v 2.2. Thuật toán khai phá tập mục thƣờng xuyên có trọng số WFIM .....................37 2.2 ...............................................................................38 2.2.2. Thuật toán WFIM dựa trên thuật toán Apriori .........................................42 2.2.3. Thuật toán WFIM dựa trên thuật toán FP-Growth ...................................44 2.2.4. Ví dụ thuật toán WFIM ............................................................................46 2.3. Kết luận chƣơng ..............................................................................................49 Chƣơng 3: ĐÁNH GIÁ CÁC THUẬT TOÁN VÀ ỨNG DỤNG ............................50 3.1. Đánh giá các giải thuật ...................................................................................50 3.2. Kiểm tra tập dữ liệu và môi trƣờng thí nghiệm ..............................................51 3.3. So sánh WFIM với các thuật toán khác ..........................................................52 3.4. Kiểm tra khả năng phát triển ..........................................................................56 3.5. Ứng dụng chƣơng trình ...................................................................................59 KẾT LUẬN ...............................................................................................................63 TÀI LIỆU THAM KHẢO .........................................................................................65 PHỤ LỤC ..................................................................................................................67 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
vi Danh mục 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ở dữ liệu TID Transction Identifcation W Tập các trọng số của các mục L Tập tất cả các mục thường xuyên Ck Tập các k-tập mục ứng viên Lk Tập các k-tập mục thường xuyên SC(X) Số đếm hỗ trợ của các tập mục X WFIk Tập các k-tập mục thường xuyên có trọng số WFI Tập tất cả các tập mục thường xuyên có trọng số MaxW Trọng số có giá trị lớn nhất trong CSDL giao tác MinW Trọng số có giá trị nhỏ nhất trong tập mục điều kiện min_weight Ngưỡng trọng số tối thiểu min_sup Ngưỡng hỗ trợ tối thiểu support Độ hỗ trợ của các tập mục conf Độ tin cậy minconf Độ tin cậy cực tiểu BFS Breadth First Search DFS Depth First Search WFIM Weighted Frequent Itemset Mining Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
vii Danh mục các bảng Bảng 1.1. Biểu diễn ngang của cơ sở dữ liệu giao tác ...............................................5 Bảng 1.2. Biểu diễn dọc của cơ sở dữ liệu giao tác ...................................................5 Bảng 1.3. Ma trận giao tác của cơ sở dữ liệu bảng 1.1 .............................................6 Bảng 1.4. CSDL giao tác minh họa thực hiện thuật toán Apriori ............................13 Bảng 1.5. CSDL giao tác minh họa cho thuật toán FP- growth ..............................17 Bảng 2.1. CSDL giao tác ..........................................................................................27 Bảng 2.2. Trọng số của các mục...............................................................................28 Bảng 2.3. CSDL giao tác D ......................................................................................32 Bảng 2.4. Trọng số của các mục...............................................................................32 Bảng 2.5. CSDL giao tác ..........................................................................................37 Bảng 2.6. Ví dụ các mục với các khoảng trọng số khác nhau ..................................38 Bảng 2.7. Tập các tập mục thường xuyên với các khoảng trọng số khác nhau .......41 Bảng 2.8. Mục thường xuyên có trọng số (sắp xếp tăng dần theo trọng số) ............46 Bảng 3.1. Tổng hợp số liệu thực tế ...........................................................................51 Bảng 3.2. Hiệu năng đối với các ngưỡng trọng số khác nhau .................................56 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
viii Danh mục các hình Hình 1.1. Phân loạ ật toán khai phá tập mục thường xuyên .......................10 Hình 1.2. Cây FP-tree được xây dựng dần khi thêm các giao tác ti, t2, t3. Từ tập dữ liệu ban đầu, ta xây dựng header table của cây FP như sau: ..................................18 Hình 1.3. Cây FP-tree của CSDL DB trong bảng....................................................19 Hình 1.4. FP-tree phụ thuộc của m ..........................................................................22 Hình 1.5. Các FP-tree phụ thuộc của am, cm và cam .............................................22 Hình 2.1. Cây FP-Tree tổng quát của thuật toán FP-Tree ......................................47 Hình 2.2. Cây FP-Tree con với tiền tố {r} ...............................................................48 Hình 3.1. Số lượng tập mục thường xuyên so với FP-Growth (Tập dữ liệu Connect) ...................................................................................................................................52 Hình 3.2. Thời gian thực hiện so với FP-Growth (Tập dữ liệu Connect) ................53 Hình 3.3. Số lượng tập mục thường xuyên so với các thuật toán khác (Tập dữ liệu Connect) ....................................................................................................................53 Hình 3.4. Thời gian thực hiện so với các thuật toán khác (Tập dữ liệu Connect) ...54 Hình 3.5. Thời gian thực hiện so với các thuật toán khác (Tập dữ liệu Mushroom) ...................................................................................................................................55 Hình 3.6. Thời gian thực hiện so với các thuật toán khác (Tập dữ liệu Mushroom) ...................................................................................................................................55 Hình 3.7. Khả năng phát triển của WFIM với các ngưỡng hỗ trợ khác nhau (tập dữ liệu T10I4DxK)..........................................................................................................57 Hình 3.8. Khả năng phát triển so với các thuật toán khác (Tập dữ liệu T10I4DxK và ngưỡng hỗ trợ = 0,1%).........................................................................................58 Hình 3.9. Khả năng phát triển so với các thuật toán khác (Tập dữ liệu T10I4DxK và ngưỡng hỗ trợ = 0,5%).........................................................................................58 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
1 MỞ ĐẦU Lý do chọn đề tài Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin. Đây là lĩnh vực đã thu hút đông đảo các nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu. Khai phá luật kết hợp (Mining association rules) là bài toán có vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu và có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau của đời sống, đặc biệt là trong lĩnh vực kinh doanh. Khai phá luật kết hợp đƣợc giới thiệu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị, phân tích sở thích mua của khách hàng bằng cách tìm ra những mặt hàng khác nhau đƣợc khách hàng mua cùng trong một lần mua. Những thông tin nhƣ vậy sẽ giúp ngƣời quản lý kinh doanh tiếp thị chọn lọc và thu xếp không gian bày hàng hợp lý hơn, giúp cho kinh doanh hiệu quả hơn. Bài toán khai phá luật kết hợp bao gồm hai bài toán con. Bài toán thứ nhất là tìm các 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, bài toán thứ hai là sinh ra các 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 đƣợc. Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bài toán thứ nhất, đó là khai phá tất cả các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ cho trƣớc, và các nghiên cứu về khai phá luật kết hợp tập trung vào bài toán khai phá tập mục thƣờng xuyên. Xuất phát từ những lợi ích thực tế trên tác giả đã mạnh dạn chọn đề tài “KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC” làm đề tài nghiên cứu cho luận văn tốt nghiệp của mình. Mục tiêu đề tài tiếp tục nghiên cứu và đề xuất các thuật toán khai phá tập mục thƣờng xuyên có trọng số trong CSDL giao tác Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
2 Xây dựng và đề xuất một số giải thuật khai phá tập mục thƣờng xuyên có trọng số. Lập trình, thử nghiệm các giải thuật khai phá tập mục thƣờng xuyên có trọng số. Đối tƣợng nghiên cứu các cơ sở dữ liệu giao tác đƣợc cập nhật từ kho dữ liệu mẫu UCI Phạm vi nghiên cứu nghiên cứu và thử nghiệm bài toán khai phá tập mục thƣờng xuyên có trọng số trên cơ sở dữ liệu giao tác. Phƣơng pháp nghiên cứu luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận văn đƣợc chứng minh dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm luận văn thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán. Bố cục luận văn Luận văn đƣợc chia làm 3 chƣơng: Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Chương 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ Chương 3: ĐÁNH GIÁ CÁC THUẬT TOÁN VÀ ỨNG DỤNG Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
3 Chƣơng 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Khai phá tập mục thƣờng xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thƣờng xuyên xuất hiện nhƣ là bài toán con của nhiều lĩnh vực khai phá dữ liệu nhƣ khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tƣơng quan, phân lớp, phân cụm dữ liệu, khai phá Web,…. Bài toán khai phá tập mục thƣờng xuyên đƣợc giới thiệu lần đầu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [6] trong mô hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó chính là các luật kết hợp. Khai phá dữ liệu bằng luật kết hợp là một phƣơng pháp quan trọng trong khai phá dữ liệu. Nó đƣợc ra đời và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên đƣợc Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất năm 1993[6]. Sau đó năm 2013 đƣợc A.KrishnaKumar, D.Amrita, N.Swathi Priya [11] tiếp tục phát triển và cải tiến. Đến nay những nghiên cứu về luật kết hợp tập trung xây dựng thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán để hiệu quả hơn. Khai phá luật kết hợp có hai bƣớc: bƣớc thứ nhất, tìm các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ tối thiểu minsup cho trƣớc, bƣớc thứ hai, từ các tập mục thƣờng xuyên tìm đƣợc, sinh ra các luật kết hợp thỏa mãn ngƣỡng độ tin cậy minconf cho trƣớc. Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bƣớc thứ nhất, đó là khai phá tất cả các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ cho trƣớc. Ứng dụng điển hình là trong siêu thị, ngƣời ta muốn biết rằng trong giỏ hàng mua hàng củ ờng mua những món hàng nào đi cùng với nhau. Nếu nhà kinh doanh siêu thị biết đƣợc thông tin này thì họ sẽ có chiến lƣợc kinh doanh phù hợp để tăng thêm lợi nhuận. Ví dụ nếu một luật đƣợc khám phá rằng “đa số ngƣời Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
4 mua dao cạ ẽ mua kem cạo râu”. Lúc đó nhà kinh doanh có thể sẽ đƣa tủ chứa kem cạo râu lại gần với dao cạo râu hoặc có nhữ ức khuyến mãi nhƣ mua nhiều kem cạo râu sẽ đƣợc tăng dao cạo râu…Không chỉ dừng lại nhƣng ứng dụng trong thƣơng mại, luật kết hợp đã có nhƣng ứng dụng rộng rãi trong các lĩnh vực khác nhƣ y tế, tài chính, thiên văn,… Chƣơng 1 sẽ trình bày các vấn đề cơ bản của khai phá luật kết hợp và bài toán khai phá tập mục thƣờng xuyên và một số hƣớng mở rộng của bài toán. 1.1. Các khái niệm cơ bản trong khai phá luật kết hợp Cho một tập I = {I1, I2, ..., Im} gồm m mục (Item). Tập X I đƣợc gọi là tập mục (itemset) T ={t1, t2,…,tn} là tập gồm n bản ghi (record - còn gọi là giao tác - transaction), mỗi bản ghi t là một tập mục, đƣợc định danh bởi TID (Transaction Identification). Tƣơng tự nhƣ khái niệm tập hợp, các bản ghi không đƣợc trùng lặp, nhƣng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau này, ngƣời ta đều giả thiết rằng các khoản mục trong một bản ghi và trong tất cả các tập mục khác, có thể coi chúng đã đƣợc sắp xếp theo thứ tự từ điển của các mục. Gọi D là CSDL của n bản ghi và mỗi bản ghi đƣợc đánh nhãn với một định danh duy nhất. 1.1.1. Cơ sở dữ liệu giao tác Định nghĩa 1.1. Cho tập các mục (item) I i1 , i2 ,..., in . Một giao tác (transaction) T là một tập con của I, T I. Cơ sở dữ liệu giao tác là một tập các giao tác DB T1 , T2 ,..., Tm . Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con X I , gồm k mục phân biệt đƣợc gọi là một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X T. Biểu diễn cơ sở dữ liệu giao tác: cơ sở dữ liệu giao tác thƣờng đƣợc biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có một định danh TID và một danh sách các mục dữ liệu trong giao tác đó. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
5 Ví dụ 1.1. 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 T1 B, C, D T2 B, C, D T3 A, B, D 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 T11 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 cả các định danh của các giao tác chứa mục dữ liệu này. Bảng 1.2. Biểu diễn dọc của cơ sở dữ liệu giao tác Mục dữ liệu Định danh giao tác A T3, T6, T7, T8, T9, T10, T11 B T1, T2, T3, T7, T9, T11 C T1, T2, T4, T5, T6, T7, T8, T11 D T1, T2, T3, T4, T5 E T9, T10 F T4, T7 Ma trận giao tác: Cơ sở dữ liệu giao tác DB T1 , T2 ,..., Tm trên tập các mục (item) I i1 , i2 ,..., in đƣợc biểu diễn bởi ma trận nhị phân M (mpq )m n , ở đó: 1 khi iq Tp mpq 0 khi iq Tp Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
6 Ví dụ 1.2. Cơ sở dữ liệu bảng 1.1 biểu diễn ở dạng ma trận giao tác là: Bảng 1.3. Ma trận giao tác của cơ sở dữ liệu bảng 1.1 TID A B C D E F T1 0 1 1 1 0 0 T2 0 1 1 1 0 0 T3 1 1 0 1 0 0 T4 0 0 1 1 0 1 T5 0 0 1 1 0 0 T6 1 0 1 0 0 0 T7 1 1 1 0 0 1 T8 1 0 1 0 0 0 T9 1 1 0 0 1 0 T10 1 0 0 0 1 0 T11 1 1 1 0 0 0 1.1.2. Tập mục thƣờng xuyên và luật kết hợp Định nghĩa 1.2. Cho tập mục X I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm các giao tác chứa X trên tổng {T DB | T X} số các giao tác trong DB, tức là: sup( X ) DB Ta có: 0 ≤ sup(X) ≤ 1 với mọi tập mục X I. Định nghĩa 1.3. Cho tập mục X I và ngƣỡng hỗ trợ tối thiểu (minimum support) minsup 0,1 (đƣợc xác định trƣớc bởi ngƣời sử dụng). X đƣợc gọi là tập mục Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
7 thƣờng xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu minsup nếu sup( X ) minsup , ngƣợc lại X gọi là tập mục không thƣờng xuyên. Định nghĩa 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 Y= Ø ; 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 Y ) , là độ hỗ trợ của tập mục X Y , sup (X Y) = sup (X Y) . Nhƣ vậy độ hỗ trợ của luật kết hợp X Y chính là xác suất P(X Y) của sự xuất hiện đồng thời của X Y trong một giao tác. Ta có: 0 sup (X Y) 1. Định nghĩa 1.6. Độ tin cậy (Confidence) của một luật X Y , ký hiệu conf ( X Y ) , là tỷ lệ phần trăm giữa số giao tác chứa X Y và số giao tác chứa X trong cơ sở dữ liệu DB. sup(X Y) conf(X Y) = sup(X ) Độ tin cậy của luật kết hợp X Y chính là xác suất có điều kiện P(Y/X): {T DB | X T Y T} {T DB | X Y T } sup(X Y) P(Y / X ) {T DB | X T} {T DB | X T } sup(X ) và ta có 0 conf(X Y) 1. Các luật thoả mãn cả hai ngƣỡng độ hỗ trợ (minsup) và độ tin cậ (minconf), tức thỏa mãn sup(X Y) minsup và conf(X Y) minconf , đƣợc gọi là luật kết hợp mạnh. Tính chất cơ bản của tập mục thƣờng xuyên: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
8 Cho cơ sở dữ liệu giao tác DB và ngƣỡng độ hỗ trợ tối thiểu minsup. Các tập mục thƣờng xuyên có các tính chất sau: (1) Nếu X, Y là các tập mục và X Y thì sup( X ) sup(Y ) . (2) Nếu một tập mục là không thƣờng xuyên thì mọi tập cha của nó cũng không thƣờng xuyên. (3) Nếu một tập mục là thƣờng xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thƣờng xuyên. Tính chất (3) đƣợc gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thƣờng xuyên. 1.1.3. 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 minsup 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) minconf . 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à 0 hoặc 1 (xuất hiện hay không xuất hiện). Bài toán khai phá luật kết hợp đƣợc chia thành hai bài toán con. Bài toán thứ nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trƣớc, tức là tìm tất cả các tập mục thƣờng xuyên. Bài toán thứ hai là sinh ra các luật kết hợp từ các tập mục thƣờng xuyên đã tìm đƣợc thỏa mãn độ tin cậy tối thiểu cho trƣớc. Bài toán thứ hai đƣợc giải quyết nhƣ sau: giả sử đã tìm đƣợc X là tập mục thƣờng xuyên, ta sinh ra các luật kết hợp bằng cách tìm Y X , kiểm tra độ tin cậy của luật X \ Y Y có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
9 giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thƣờng xuyên. Phần tiếp theo sau đây sẽ trình bày chi tiết về khai phá tập mục thƣờng xuyên. 1.2. Một số thuật toán cơ bản khai phá tập mục thƣờng xuyên 1.2.1. Cách tiếp cận khai phá tập mục thƣờng xuyên Các nghiên cứu về khai phá tập mục thƣờng xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thƣờng xuyên. Bài toán khai phá tập mục thƣờng xuyên có thể chia thành hai bài toán nhỏ: tìm các tập mục ứng viên và tìm các tập mục thƣờng xuyên. Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thƣờng xuyên, phải tính độ hỗ trợ của nó để kiểm tra. Tập mục thƣờng xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngƣỡng hỗ trợ tối thiểu cho trƣớc. Đã có rất nhiều thuật toán tìm tập mục thƣờng xuyên đƣợc công bố, ta có thể phân chúng theo hai tiêu chí sau: - Phƣơng pháp duyệt qua không gian tìm kiếm. - Phƣơng pháp xác định độ hỗ trợ của tập mục. Phƣơng pháp duyệt qua không gian tìm kiếm đƣợc phân làm hai cách: duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu (Depth First Search – DFS). Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của tất cả các tập mục ứng viên có (k-1) mục trƣớc khi tính độ hỗ trợ của các tập mục ứng viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k phải kiểm tra độ hỗ n! trợ của tất cả Cnk tập mục ứng viên có k mục. k !( n k )! Duyệt theo chiều sâu là duyệt qua cơ sở dữ liệu đã đƣợc chuyển đổi thành cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
10 Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có tất cả 2n tập con, rõ ràng đây là bài toán NP khó, do vậy cần phải có phƣơng pháp duyệt thích hợp, tỉa nhanh các tập ứng viên. Phƣơng pháp xác định độ hỗ trợ của tập mục X đƣợc chia làm hai cách: cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ hai là tính phần giao của các tập chứa định danh của các giao tác chứa X. Các thuật toán khai phá có thể phân loại nhƣ hình 1.2: DFS BFS Đếm Đếm Giao Giao AIS Partition FP- Eclat growth Apriori Dic Hình 1.1. Phân loạ ật toán khai phá tập mục thường xuyên Phần tiếp sau mô tả chi tiết nội dung hai thuật toán tiêu biểu và là cơ sở để phát triển các thuật toán mới. Thuật toán Apriori tiêu biểu cho phƣơng pháp sinh ra các tập mục ứng viên và kiểm tra độ hỗ trợ của chúng; Thuật toán FP-growth đại diện cho phƣơng pháp không sinh ra tập mục ứng viên, cơ sở dữ liệu đƣợc nén lên cấu trúc cây, sau đó khai phá bằng cách phát triển dần các mẫu trên cây này. 1.2.2. Thuật toán Apriori Apriori là thuật toán khai phá tập mục thƣờng xuyên do R. Agrawal và R. Srikant đề xuất vào năm 1993 [6]. Ý tƣởng của thuật toán Apriori còn là nền tảng cho việc phát triển nhiều thuật toán khai phá tập mục thƣờng xuyên khác về sau. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
11 Ý tƣởng chính của thuật toán nhƣ sau: sinh ra các tập mục ứng viên từ các tập mục thƣờng xuyên ở bƣớc trƣớc, sử dụng kỹ thuật “tỉa” để bỏ đi những tập mục ứng viên không thoả mãn ngƣỡng hỗ trợ cho trƣớc. Cơ sở của kỹ thuật này là tính chất Apriori (xem 1.1.2): Bất kỳ tập con nào của tập mục thường xuyên cũng phải là tập mục thường xuyên. Vì vậy các tập mục ứng viên gồm k mục có thể đƣợc sinh ra bằng cách kết nối các tập mục thƣờng xuyên có (k-1) mục và loại bỏ tập mục ứng viên nếu nó có chứa bất kỳ một tập con nào không phải là thƣờng xuyên. Giả sử các mục dữ liệu trong mỗi giao tác đƣợc lƣu theo trật tự từ điển. Thuật toán sử dụng các ký hiệu sau đây: Tập k mục Chức năng Tập các k-tập mục thƣờng xuyên (với độ hỗ trợ minsup). Mỗi phần tử của tập này có 2 trƣờng: Lk i) Tập mục (itemsets) ii) Độ hỗ trợ (count) Tập các k-tập mục ứng viên (các tập mục thƣờng xuyên tiềm năng). Mỗi phần tử của tập này có 2 trƣờng: Ck i) Tập mục (itemsets) ii) Độ hỗ trợ (count) Thuật toán duyệt cơ sở dữ liệu nhiều lần. Mỗi lần duyệt, thuật toán thực hiện hai bƣớc: bước kết nối và bước tỉa. Trong lần lặp thứ k, thuật toán nối hai (k-1)-tập mục để sinh ra k-tập mục, sử dụng tính chất Apriori để tỉa các tập ứng viên. Bƣớc nối và bƣớc tỉa nhƣ sau: Bước kết nối (tìm Ck): Tập các k-tập mục ứng viên Ck đƣợc sinh ra bởi việc kết nối Lk-1 với chính nó. Hai tập mục l1 và l2 của Lk-1 đƣợc nối nế - - 1 2: (l1[1] = l2[1]) (l1[2] = l2[2]) … (l1[k-2] = l2[k-2]) (l1[k-1] < l2[k-1]) Dạng của tập mục nhận đƣợc bởi nối l1 và l2 là: l1[1] l1[2] … l1[k-2] l1[k-1] l2[k-1]. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
12 Bước tỉa: Tập Ck chứa tập Lk, tức là tất cả các k-tập mục thƣờng xuyên đều thuộc tập Ck. Tập Ck có thể là rất lớn dẫn đến khối lƣợng tính toán lớn. Thuật toán áp dụng tính chất Apriori để rút gọn tập Ck. Nếu có một (k-1)-tập mục con nào đó của k-tập mục ứng viên mà không có mặt trong Lk-1 thì ứng viên đó không thể là thƣờng xuyên, có thể loại bỏ khỏi Ck. Việc kiểm tra các (k-1)-tập mục con có thể thực hiện nhanh bởi duy trì một cây băm của tất cả các tập mục thƣờng xuyên đã tìm thấy. Thuật toán Apriori (tìm các tập mục thƣờng xuyên) Input: Cơ sở dữ liệu DB, ngƣỡng độ hỗ trợ minsup Output: Tập các tập mục thƣờng xuyên L trong DB Method: (1) Tìm các 1-tập mục thƣờng xuyên, nhận đƣợc L1; (2) For (k=2; Lk-1≠ ; k++) do begin (3) Ck = apriori_gen(Lk-1, minsup); // Sinh tập ứng viên mới từ Lk-1 (4) For (each T DB) do begin (5) C = subset(Ck,T); // Các tập mục ứng viên chứa trong T (6) For (each c C) (7) c.count++; // tăng số đếm c lên một đơn vị (8) end; (9) Lk = { c Ck / c.count ≥ minsup}; (10) End; (11) L=  Lk ; Sinh các tập mục ứng viên của thuật toán Apriori: hàm Apriori_gen() Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/