Xemtailieu Tải về 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 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 ii 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ô Trường Đại học Công nghệ thông tin và Truyền thông 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.! iii MỤC LỤC LỜI CAM ĐOAN ..................................................................................................... i LỜI CẢM ƠN ......................................................................................................... ii MỤC LỤC .............................................................................................................iii Danh mục các ký hiệu, các chữ viết tắt .................................................................... v Danh mục các bảng ................................................................................................ vi Danh mục các hình ................................................................................................ vii 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.............................. 8 1.2.1. Cách tiếp cận khai phá tập mục thường xuyên ......................................... 8 1.2.2. Thuật toán Apriori ................................................................................. 10 1.2.3. Thuật toán FP-growth............................................................................ 14 1.3. Một số hướng mở rộng bài toán khai phá tập mục thường xuyên. ................ 23 1.4. Kết luận chương .......................................................................................... 23 Chương 2: KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN CÓ TRỌNG SỐ.............. 24 2.1. Thuật toán khai phá tập mục thường xuyên có trọng số MINWAL .............. 24 2.1.1. Các khái niệm cơ bản ............................................................................ 24 2.1.2. Thuật toán MINWAL khai phá tập mục thường xuyên có trọng số dựa trên thuật toán Apriori ..................................................................................... 28 2.1.3. Ví dụ minh họa thuật toán MINWAL .................................................... 31 iv 2.2. Thuật toán khai phá tập mục thường xuyên có trọng số WFIM .................... 35 2.2.1. Các khái niệm cơ bản ............................................................................ 36 2.2.2. Thuật toán WFIM dựa trên thuật toán Apriori ....................................... 40 2.2.3. Thuật toán WFIM dựa trên thuật toán FP-Growth ................................. 42 2.2.4. Ví dụ thuật toán WFIM ......................................................................... 44 2.3. Kết luận chương .......................................................................................... 47 Chương 3: ĐÁNH GIÁ CÁC THUẬT TOÁN VÀ ỨNG DỤNG........................... 48 3.1. Đánh giá các giải thuật ................................................................................ 48 3.2. Kiểm tra tập dữ liệu và môi trường thí nghiệm ............................................ 49 3.3. So sánh WFIM với các thuật toán khác........................................................ 50 3.4. Kiểm tra khả năng phát triển........................................................................ 54 3.5. Ứng dụng chương trình ............................................................................... 56 KẾT LUẬN ........................................................................................................... 60 TÀI LIỆU THAM KHẢO ..................................................................................... 62 PHỤ LỤC.............................................................................................................. 64 v 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 vi 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 ............................. 16 Bảng 2.1. CSDL giao tác ....................................................................................... 26 Bảng 2.2. Trọng số của các mục ........................................................................... 27 Bảng 2.3. CSDL giao tác D ................................................................................... 31 Bảng 2.4. Trọng số của các mục ........................................................................... 31 Bảng 2.5. CSDL giao tác ....................................................................................... 36 Bảng 2.6. Ví dụ các mục với các khoảng trọng số khác nhau ................................ 37 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 ....... 39 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ố) ........... 44 Bảng 3.1. Tổng hợp số liệu thực tế ........................................................................ 49 Bảng 3.2. Hiệu năng đối với các ngưỡng trọng số khác nhau ................................ 53 vii Danh mục các hình Hình 1.1. Phân loại các thuậ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: ................................. 17 Hình 1.3. Cây FP-tree của CSDL DB trong bảng ................................................. 18 Hình 1.4. FP-tree phụ thuộc của m ....................................................................... 21 Hình 1.5. Các FP-tree phụ thuộc của am, cm và cam............................................ 21 Hình 2.1. Cây FP-Tree tổng quát của thuật toán FP-Tree .................................... 45 Hình 2.2. Cây FP-Tree con với tiền tố {r} ............................................................. 46 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) .............................................................................................................................. 50 Hình 3.2. Thời gian thực hiện so với FP-Growth (Tập dữ liệu Connect) ............... 50 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) ................................................................................................................ 51 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)... 51 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) .............................................................................................................................. 52 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) .............................................................................................................................. 53 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) ...................................................................................................... 54 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%) ..................................................................................... 55 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%) ..................................................................................... 55 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 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ố. 2 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 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ủa khách hàng th́ ì thườ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 mua dao cạo râu th́ ì sẽ 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ững h́ ình thức khuyến mãi như 4 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 đó. 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 B C D E F T3, T6, T7, T8, T9, T10, T11 T1, T2, T3, T7, T9, T11 T1, T2, T4, T5, T6, T7, T8, T11 T1, T2, T3, T4, T5 T9, T10 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 ) mn , ở đó: 1 khi iq T p mpq 0 khi iq T p 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 số các giao tác trong DB, tức là: sup( X ) {T DB | T 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 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. 7 Đị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(XY) của sự xuất hiện đồng thời của X và 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. conf(X Y ) = sup(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): P(Y / X ) {T DB | X T Y T } {T DB | X Y T } sup(X Y ) {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ợ tối thiểu (minsup) và độ tin cậy tối thiểu (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: 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. 8 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 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. 9 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ỗ trợ của tất cả Cnk n! 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. 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: 10 BFS Đếm DFS Đếm Giao Giao AIS Apriori Partition FPgrowth Eclat Hình 1.1. Phân loại các thuậ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. Ý 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: 11 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ợ tối thiểu minsup). Mỗi phần tử của tập này có 2 trường: Lk Tập mục (itemsets) Độ 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 Tập mục (itemsets) Độ 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ếu chúng có (k-2) mục dữ liệu đầu bằng nhau, mục dữ liệu thứ (k-1) của l1 nhỏ hơn của l2: (l1[1] = l2[1]) (l1[2] = l2[2]) … (l1[k-2] = l2[k-2]) (l1[k-1]