Chương 1. Khai thác mẫu phố biến truyền thống Bài toán khai thác tập phd biến được đề xuất bởi tác giả R.Agrawal vào năm 1993 đã đánh dấu sự ra đời của ngành khoa học khai thác dữ liệu. Nội dung cơ bản của bài toán được nêu như sau: Cho I={1,2,.m} là một tập danh mục, và cho T={I,2,.n} là một tập các giao tác. Co sở dit liệu đầu vào là một bảng nhị phân 8 c I xT.
Nếu một danh mục e xuất hiện trong một giao tác 1, được viết là (e,t) € 5, hoặc eat. Mot bang cơ sở đữ liệu được sắp xếp như một tập các giao tác, mỗi một giao tác chứa một tập các danh mục. Một tập X œ I thì được gọi là một tập danh mục. và một tập YcT thì được gọi là tập giao tác.
Thông thường một tập danh mục {A, C, W} được viết là ACW và một tập giao tác {2, 4, 5} được viết là 245. Độ hỗ trợ (độ phô biến) của một tập danh mục X, ký hiệu o(X), là SỐ lượng giao tác có tập danh mục X xuất hiện như là một tập con. Một tập danh mục (trong một số trường hợp gọi tắt là tập) là phô biến nếu độ hỗ trợ của nó lớn hơn hay bằng một độ hỗ trợ tối thiêu (minsup) cụ thé được xác định trước, nghĩa là, nếu ø@X)> minsup. Bai toán khai thác FI trên CSDL DB cho trước là bài toán tim tat cả các tập mục của CSDL có tần số xuất hiện trong các giao địch thỏa mãn ngưỡng minsup do người dùng xác định trước.
Tập các tập mục được khai thác theo ngưỡng minsup được gọi là FI của DB. Ví du: Xét CSDL trong Bang 1.1 với minsup = 0,5 ta có: ty A, B,D, E a | p Bang 1. Các tập phổ biến với độ hỗ trợ minsup=0,5 Độ hỗ trợ (số đếm) Các tập danh mục phố biến on J5. 83% (5) E, BE D, A, C, AC, AD, BD,AB, AE, CD, BC, BDE, ABE, 50% (3) DE, ABD, ABDE FI ={A, 8, C, D, E, AB, AD, AE, BC, BD, BE, DE, ABD, ABE, BDE, ABDE} Bài toán khai thác FI là bài toán tìm tat cả các tập mục của CSDL có tần suất xuất hiện thõa mãn ngưỡng minsup cho trước.
Kê từ khi được đề xuất, bài toán khai thác FI được nhiều sự quan tâm nghiên cứu với nhiều thuật toán được đề xuất dé giải quyết bài toán nay. Trong số đó có ba thuật toán thông dụng là thuật toán Apriori, thuật toán FP- Growth và thuật toán Eclat. Thuật toán Apriori [1, 3] do Agrawal và các đồng sự dé xuất nam 1994. Thuật toán khai thác FI trên CSDL ngang.
thuật toán này khai thác FI bằng cách quét CSDL nhiều lan. Y tưởng như sau: Thuật toán quét CSDL lần thứ nhất dé sinh ra tập1-irmser phd biến, từ tập 1-iemser phô biến quét CSDL lần thứ hai dé sinh ra tập 2-itemset phố biến, v. cho đến khi không tìm được bất kì tập phô biến nào nữa thì dừng. Thuật toán Apriori dựa trên tính chất được đặt tên là tính chất Apriori (còn được gọi là tính chất bao đóng giảm) như sau: Cho hai tập mục X và Y của CSDL DB: Nếu XŒ€ÿY => support(X) = support(Y) Do đó: Nếu support(X) < minsup = VY 2 X, support(Y)<minsup Nếu (Y) >minsup = WX © Y, support(X) > minsup Dựa vào tính chất trên, thuật toán Apriori [1] được mô tả như trong Hình 1.1; Apriori Input: CSDL DB và một ngưỡng minsup 1 Quét CSDL dé tinh support của các Ï - itemset, so sánh support với minsup dé loc ra FI gom ]-itemset (L]) thỏa man minsup 2.
Sử dụng Lk -J dé sinh ra ứng viên k-itemset. Sau đó quét CSDL de tính support của cdc ứng viên và loại bỏ các k-itemset không phải là FI thu được k-itemset pho biến (Lk). Lap lai bước 2 cho đến khi không tạo ra ứng viên nao nữa. FI khai thác được 112.
Thuật toán Ápriori trong khai thác FI Ngày nay các CSDL thực tế có xu hướng tăng rất nhanh vẻ dung lượng, bởi vậy việc quét CSDL nhiều lần là không khả thi do rất tốn thời gian. Đồng thời việc sinh ra tập các ứng viên ở mỗi bước quét CSDL cần lượng bộ nhớ lớn dé lưu trữ. Do đó thuật toán Apriori ít được quan tâm nghiên cứu và sử dụng trong thời gian gần đây. Thuật toán FP-Growth [2] do Han và đồng sự đề xuất năm 2000.
Đây là phương pháp khai thác FI trên CSDL dọc, thuật toán giúp giải quyết các hạn chế của Apriori về cả thời gian xử lý và bộ nhớ sử dụng. Tiếp sau đó Grahne và đồng sự đề xuất FP-Growth* [16]. Đây là một tiếp cận thú vị với việc sử dụng cấu trúc cây EP-tree (Frequent Partern-tree) để nén toàn bộ CSDL với mỗi nút trên FP-tree là các mục của CSDL ban đầu. Đông thời, thuật toan FP- Growth chi cần hai lần quét CSDL, giảm đáng ké thời gian so với thuật toán Apriori, đặc biệt là trong các trường hợp CSDL lớn.
Bước đầu tiên, thuật toán FP-Growth quét CSDL và sắp xếp lại trật tự các mục theo thứ tự tần suất xuất hiện giảm dần trên mỗi giao dịch. Bước thứ 2, FP-Growth quét CSDL và nén toàn bộ dit liệu lên cây FP-tree. duyét FP-tree dé khai thác các FI: Thuật toán FP-Growth được mô tả như trong Hình 1.2: FP-Growth Input: CSDL DB và một ngưỡng minsup Output: Cac Fl của DB thoa minsup 1. Quét toàn bộ CSDL DB và tinh độ hồ trợ (support) của từng mục.
Sau đó xác định những mục có support lớn hơn minsup và sắp xếp giảm dan theo support vao trong f_list. Tao cây FP-tree chi có một nút gốc được gán nhãn là “null” ký hiệu root. 4 Với mỗi giao địch trong DB được thẻ hiện như sau: chọn và sap xếp những danh mục phô biến theo thứ tự giảm dan trong flist. Chèn các mục lên cây FP-tree ớ Duyệt cây FP-tree dé khai thác các FI thỏa mãn minsup Hình 1.
Thuật toán FP-Growth khai thác FI dựa trên cấu trúc FP-tree Hạn chế của thuật toán nảy là quét CSDL đến hai lần và đặc biệt là tốn thời gian trong duyệt cây FP-tree dé xây dựng các FI. Thuật toán Eclat [3] được dé xuất bởi Zaki sử dụng cau trúc IT-tree (Tidset Itemset-tree) dé lưu tidset của các tap muc tren mỗi nút và đưa ra khái niệm lớp tương đương dé kết nối các tập mục trong cùng một lớp tương đương dé tạo ra tập mục mới. Thuật toán Eclat với chỉ một lần quét CSDL là một tiếp cận hiện đại, tiết kiệm thời gian xử lý và có thé áp dụng khai thác FI trên nhiều loại CSDL một cách hiệu quả. Trong đó, nhiều nghiên cứu đã mở rộng và biến đôi cau trúc IT-tree một cách phù hợp dé áp dụng khai thác FI trên nhiều loại CSDL khác như khai thác trên CSDL trọng số [5,7] CSDL số lượng [8,10] một cách hiệu quả hơn.
Tiếp cận Eclat sử dụng tính chất Apriori dé cắt nhánh các tập mục không thỏa ngưởng phô biến. Do vậy các tập mục trên IT-tree là các FI thỏa mãn ngưỡng muinsup. Như vậy nếu tập mục X không thoa mãn ngưỡng minsup thì các tập mục là phủ của X cũng không thỏa ngưỡng minsup, do vậy ta không cần xét nhánh do tập mục X tạo ra. Áp dụng tính chất bao đóng giảm trên cây IT-tree sẽ cắt nhánh được tất cả các nhánh chắc chắn không chứa FI và các tập mục trên IT- tree chính là FI cần khai thác.
Cấu trúc IT-tree IT-tree có cau trúc gồm nhiều mức, mỗi mức gồm nhiều lớp tương đương. Mỗi lớp tương đương gồm các nút có cùng nút cha ở mức trên. Mỗi nút gồm hai thành phan: - Tập mục X - Tidset của X Mỗi lớp tương đương được tạo ra từ một mục cha ở mức trên kết hợp lần lượt các nút phía sau nó trong cùng một lớp tương đương. Do vậy các nút trong cing một lớp tương đương có cling số lượng phan tử chỉ khác nhau phan tử cuối cùng.
Một nút mới được chèn vào IT-tree néu độ hỗ trợ (support) của nó thỏa mãn ngưỡng phô biến (minsup) do đó các nút trên IT- tree sau khi xây dựng xong chính là các FI cần khai thác. 10 Thuật toán Eclat Thuật toán 1.3: Eclat Input: CSDL DB và một ngưỡng minsup Output: Cac FI của DB thỏa minsup Method: Eclat 1. Quét toàn bộ CSDL DB dé xác định tập giao dich (tidset) của ác mục. Chọn các mục có support thỏa ngưỡng minsup (1-itemset).
Chèn I-itemset vào mức | của IT-tree 3. Mỗi nút ở mức k - 1 kết hợp với các nút có cùng nút cha với nó ạo ra các nút ở mức k nếu support của các nút này thỏa ngưỡng minsup. 4 Lặp lại bước 3 cho đến khi không thé tạo thêm nút mới trên IT- 5. Duyệt cây IT-tree dé lấy ra các FI (Tất cả các nút trên [T-tree là FI).
Thuật toán Eclat dựa trên cau trúc IT-tree Thuật toán Eclat với cau trúc IT-tree là hướng tiếp cận tốt được biết đến hiện nay với chỉ một lần quét CSDL. Tuy nhiên, phương pháp này có nhược điểm lớn là tốn bộ nhớ sử dụng dé lưu tidset của các tập mục, do mỗi giao dich chứa tập mục cần một ô nhớ. Đồng thời bộ nhớ tạm cần thiết trong quá trình tính toán trung gian cũng rất lớn. Các hạn chế nay làm cho thời gian tính toán của thuật toán Eclat chưa được tối ưu.
Do đó, nghiên cứu dé xuất các phương pháp mới nhằm tối ưu bộ nhớ dé nâng cao hiệu quả khai thác FI trên các loại CSDL theo hướng tiếp cận này có tính thực tế cao. Đây cũng chính là một trong những mục tiêu nghiên cứu của luận văn. Khai thác mẫu hữu ich trọng số pho biến Bài toán khai thác FWUI cũng nhận được một số quan tâm nghiên cứu [17, 18]. Việc khai thác FWUI liên quan đến việc xác định trọng số hữu ích của các giao dich twu (transaction weight utility) và độ hỗ trợ trọng số hữu ích wus (weight utility support).
Khan và đồng sự [17] đã đưa ra định nghĩa hai đại lượng là trọng số hữu ích của giao dich - transaction weight utility 11 (twu) và độ hỗ trợ trọng số hữu ích - weight utility support (wus) được biêu điển lại như sau: Định nghĩa 1. Trọng số hữu ích của các giao dich &v được định nghĩa như sau: — =1(Mj X X,) twu(t;,) = van) TP Trong đó: - nwu(t,) là trọng số hữu ích của ty; - Xx, là số lượng mục thứ i trong t„ ,¡ e{[l,., nÌ: - w; là trọng số của mục ¿: - #(£„)là tông các mục trong giao dịch tụ Ví dụ: Cho CSDL số lượng DB với tập các mục I = {A, B, C, D, E}, các giao dich T được biéu diễn trong Bang 1.3, trọng số các mục như trong bảng 1.