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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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].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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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. Cơ sở dữ liệu giao tác Định nghĩa 1. Cho tập các mục (item) I i1 , i2 ,.
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 ,. 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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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. 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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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.
Ma trận giao tác của cơ sở dữ liệu bảng 1. Tập mục thƣờng xuyên và luật kết hợp Định nghĩa 1. 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.
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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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ƣ 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. Độ 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. 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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
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.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. Một số thuật toán cơ bản khai phá tập mục thƣờng xuyên 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.