Chương 1 giới thiệu chung về bối cảnh, nhu cầu thực tế và khai phá dữ liệu. Đồng thời định hướng tiếp cận của luận văn. Chương 2 trình bày cơ sở lý thuyết về khai thác dữ liệu. Trong đó, luận văn giới thiệu chung về khái niệm, sơ lược các thuật toán khai thác tập phổ biến như Apiori, FP-Growth là các thuật toán cơ sở để phát triển các thuật toán sau này.
Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 3 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Chương 3 trình bày chi tiết cấu trúc dữ liệu Node-set,NegNode-set và thuật toán NegFin và áp dụng chúng trong khai thác tập phổ biến. Chương 4 trình bày về môi trường xây dựng chương trình dự đoán cũng như kết quả và đánh giá thực nghiệm của chương trình. Chương 5 trình bày kết luận chung cũng như định hướng phát triển của đề tài. Cuối cùng là chi tiết về các tài liệu tham khảo để hoàn thành luận văn này.
Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 4 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp CHƯƠNG 2: TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU 2.1 Giới thiệu sơ lược về khai thác dữ liệu 2.1 Khai thác luật kết hợp Bài toán khai thác luật kết hợp trong CSDL là một trong những chức năng chính của khai thác dữ liệu, là khai phá các luật kết hợp có độ phổ biến (support) cũng như độ tin cậy (confidence) lớn hơn hoặc bằng một ngưỡng phổ biến tối thiểu (minsup) và ngưỡng tin cậy tối thiểu (minconf). Bài toán khai thác luật kết hợp thường được chia thành 2 giai đoạn: Giai đoạn 1: Tìm tất cả các tập mục phổ biến từ dữ liệu giao dịch thoả minsup; Giai đoạn 2: Sinh các luật kết hợp mạnh từ tập mục phổ biến tìm thấy ở giai đoạn thứ nhất. Thông thường giai đoạn thứ nhất chiếm hầu hết thời gian cho quá trình khai thác luật kết hợp và là giai đoạn quan trọng vì nó là giai đoạn nâng cao hiệu suất trong khai thác luật kết hợp.2 Khai thác tập phổ biến Khai phá tập phổ biến là quá trình tìm kiếm tập các phần tử có số lần xuất hiện lớn hơn một ngưỡng cho trước và vấn đề này được R. Swami đề xuất năm 1993, xuất phát từ nhu cầu bài toán phân tích dữ liệu trong cơ sở dữ liệu giao dịch, nhằm phát hiện các mối quan hệ giữa các tập hàng hóa đã bán tại siêu thị.
Việc xác định này không phân biệt sự khác nhau giữa các hàng hóa, chỉ dựa vào sự xuất hiện của chúng. Phần tiếp theo đây nêu một số khái niệm cơ sở liên quan đến bài toán khai thác luật kết hợp và tập phổ biến.2 Các khái niệm cơ sở Cho D = {T1, T2,…Tm} là cơ sở dữ liệu giao dịch và I = {i1, i2,…,in} là tập các phần tử trong cơ sở dữ liệu D. Mỗi giao dịch Ti I. Tập X I có k phần tử được gọi là tập k-phần tử (k-itemset).
Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 5 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Bảng 2.1- CSDL giao dịch TID Items 1 e, b, g, d 2 c, e, b, a 3 c, b, a, i 4 a, d, h 5 a, d, c, b, f Trong bảng 2.1 là một cơ sở dữ liệu giao dịch gồm có 5 giao dịch trong đó I={a, b, c, d, e, f, g, h, i} là các phần tử hay còn gọi là item. Tập 1-itemset gồm {a, b, c, d, e, f, g, h, i}; Tập 2-itemset gồm {ab, ac, ae, af, ag, bc, bd, be, bf, bg, cd, ce, cf, cg, de, df, ef}; Tập 3-itemset gồm {abc, abe,,, ace, agc, bce, bcd, bcf, bde, bdf, bef, cde, cdf, cde, cdf, cef} tương tự ta có tập 4-itemset, 5-itemset,… k-itemset. (Độ hỗ trợ - Support): Độ hỗ trợ (support) của itemset 𝑋 𝐼, ký hiệu support(X), là số các giao dịch trong Ɗ có chứa X. Ví dụ 1: Xét CSDL giao dịch như Bảng 2.
{a} có độ phổ biến là 4, kí hiệu support(a)=4 vì {a} xuất hiện 4 lần trong 5 giao dịch D.Vậy độ hỗ trợ của {a} là 4. Tương tự, ta có độ hỗ trợ của các tập 1-itemset sau: Bảng 2.2-Bảng thể hiện độ hỗ trợ của các phần tử 1-itemset 1-itemset Độ hỗ trợ a 4 b 4 c 3 d 3 e 2 f 1 g 1 h 1 i 1 Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 6 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Khái niệm 2. (Tập phổ biến): Tập phần tử X được gọi là tập phổ biến nếu có support(X) ≥ minsup, với minsup là ngưỡng hỗ trợ tối thiểu cho trước. Ví dụ 2: Xét CSDL như bảng 2.1 có ngưỡng minsup là 2 nếu x có độ hỗ trợ support(x) nhỏ hơn 2, sẽ bị loại.
Ta gọi I là tập 1-itemset, ta được: I = {a, b, c, d, e} là tập phổ biến và các item g, h, i không là tập phổ biến do support(g) = support(h) = support(i) = 1 < minsup Khái niệm 2. (Luật kết hợp) Tập phổ biến thường dùng để sinh luật kết hợp. Luật kết hợp với dạng X → Y, với X, Y là hai tập phần tử, được xác định thông qua hai khái niệm độ hỗ trợ và độ tin cậy của luật được định nghĩa như sau: Khái niệm 2. |{𝑋 𝑌 𝑇𝑖 | 𝑇𝑖 ∈ 𝐷}| 𝑆𝑢𝑝𝑝𝑜𝑟𝑡 (𝑋 ∪ 𝑌) = |𝐷| Ví dụ 3: Độ hỗ trợ của luật X → Y = 40%, có nghĩa là 40% trong tất cả các giao dịch X và Y được mua cùng nhau.(Độ tin cậy của một luật (confidence)) Độ tin cậy của luật X → Y là tỉ số của số giao dịch trong D, kí hiệu là: Confidence(X →Y), chứa X Y và số giao dịch trong D có chứa tập X.
𝑆𝑢𝑝𝑝𝑜𝑟𝑡(𝑋∪𝑌) 𝐶𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒 (𝑋 →𝑌) = 𝑆𝑢𝑝𝑝𝑜𝑟𝑡(𝑋) Ví dụ 4: Độ tin cậy của luật X → Y = 70%, có nghĩa là 70% khách hàng mua X cũng mua Y. Luật X →Y được gọi là tin cậy nếu có Confidence(X →Y) ≥ minconf, với minconf là ngưỡng tin cậy tối thiểu cho trước. Tập phổ biến có một số tính chất sau: Tính chất 2. (Tính chất đóng của tập phần tử) Giả sử X, Y là hai tập phần tử, X, Y I.
Nếu Y là tập phổ biến và X Y thì X cũng là tập phổ biến. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 7 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Tính chất 2. Cho X, Y là hai tập phần tử, X Y và X là tập không phổ biến thì Y cũng là tập không phổ biến. Ví dụ 5: Xét CSDL như bảng 2.1 có ngưỡng minsup là 2.
Xép tập mục X = {a,b,c} , support(X) = 3 ≥ minsup. Ta được X={a,b,c} là tập phổ biến theo ngưỡng minsup = 2. Theo tính chất 2.1 thì tất cả tập con của X = {a,b,c} cũng là tập phổ biến: support (a) = 4, support (b) = 4, support (c) = 3, support (ab) = 3, support (ac) = 3, support (bc) = 3 ≥ minsup. Tương tự, với X= {g}, support(X) = 1 < minsup.
Ta được X={g} là tập không phổ biến theo ngưỡng minsup = 2. Theo tính chất 2.2 thì tất cả tập con của X = {g} cũng không là tập phổ biến với support(gh) = 1 < minsup.3 Các thuật toán khai thác tập phổ biến 2. Thuật toán Apriori: Phương pháp sinh ứng viên để tìm tập phổ biến được Agrawal đề xuất từ năm 1993 với thuật toán Apriori. Ý tưởng của thuật toán Apriori dựa trên kết luận: nếu một tập phần tử là tập phổ biến thì tất cả tập con của nó cũng phải phổ biến (tính chất 2.1 – tập phổ biến).
Do vậy không thể có trường hợp một tập phổ biến có tập con là không phổ biến hay nói cách khác tập phổ biến nhiều danh mục hơn chỉ có thể được tạo ra từ các tập phổ biến ít danh mục hơn. Nguyên lý hoạt động cơ bản của thuật toán Apriori như sau: − Bắt đầu từ các tập phổ biến chỉ có một danh mục. - Dùng tập phổ biến kích thước k-itemset để tạo các tập ứng cử k-itemset - Duyệt cơ sở dữ liệu và đối sánh mẫu để đếm số lần xuất hiện của các tập ứngviên trong các giao dịch, nếu số lần xuất hiện của tập ứng viên lớn hơn hoặc bằng minsup thì là tập phổ biến, ngược lại không phải tập phổ biến. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 8 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp − Quá trình lặp lại cho đến khi không còn tập phổ biến nào được tạo ra.
Thuật toán Apriori Input: cơ sở dữ liệu D, minsup Output: L L1 ={tập hợp 1 danh mục}; For (k = 2; Lk-1 ≠ ; k++) do begin 3) Ck = apriori-gen (Lk-1); // Tạo ứng viên mới. 4) For all giao dịch t D do begin //duyệt CSDL 5) Ct = subset(Ck, t); //các tập danh mục ứng viên có trong giao dịch t 6) For all ứng viên c Ct do 7) c. count ++; 8) End 9) Lk = {c Ck | c.count ≥ minsup} End Answer = k Lk; // Trả về tập hợp của các tập phổ biến Hình 2.1-Thuật toán Apriori Diễn giải thuật toán: - Bước đầu tiên của thuật toán đơn giản chỉ tính các danh mục xuất hiện để xác định tập hợp của các tập phổ biến 1-itemset. - Lặp bước k : + Tập hợp Lk-1 được sử dụng để tạo nên tập ứng viên Ck : sử dụng hàm apriori- gen được miêu tả là hàm lấy Lk-1 (tập hợp của các tập phổ biến k-itemset )là đầu vào và trả về Ck là tập hợp của tất cả các tập chứa k-itemset phát sinh từ tập hợp Lk-1 bằng cách hợp các tập 1-itemsettrong tập hợp Lk-1.
Chú ý một ứng viên thuộc Ck thì tất cả các tập con của ứng viên đó phải có mặt trong Lk-1 (theo tính chất 2.2 của tập phổ biến) + Bước kế tiếp, duyệt CSDL để tính độ phổ biến của các ứng viên trong tập hợp Ck. Từ đó, tính được tập hợp Lk. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 9 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp + Nếu Lk = ∅ thì dừng lại. - Hợp của các Lk chính là các tập phổ biến cần tìm.
Hạn chế của thuật toán Apriori: Để xác định độ phổ biến của các tập ứng viên, thuật toán Apriori phải quét lại toàn bộ giao dịch trong CSDL, do đó sẽ tiêu tốn rất nhiều thời gian khi phải quét CSDL nhiều lần để kiểm tra một lượng lớn các ứng viên, đặc biệt khi số danh mục lớn.