Đặt vấn đề Trong thời đại sô hóa ngày nay, việc khai thác thông tm từ cơ sở dữ liệu đang trở thành một thách thức ngày càng lớn, đặc biệt là khi muốn tìm hiểu mối quan hệ giữa các sản phâm trong danh mục có đánh trọng số. Điều này đặt ra câu hỏi về cách thức hiệu quả nhất đề khai thác thông tin từ dữ liệu có tính chất này. Các thuật toán khai thác truyền thống như Apriori, FP-growth, và Eclat đã chứng minh được sự hiệu quá trong việc khai thác tập phô biến từ cơ sở dữ liệu. Tuy nhiên, khi dữ liệu được đánh trọng SỐ, Sự phức tạp tăng lên, đặt ra thách thức trong việc xử lý thông tin trọng số của từng sản phẩm một cách hiệu quả.2 Mục tiêu ¬ ; Đề giải quyệt van đề này, để tài này tập trung vào bài toán khai thác Top-rank-k tập pho biến từ cơ sở đữ liệu được đánh trọng số.
Sự tiếp cận này đặt ra nhu cầu phát trién thuật toán mà không chỉ xử lý dữ liệu trọng số mà còn giảm thiêu lượng kết quả tạo ra, tăng tính hiệu quả trong việc hiểu và áp dụng thông tin. Để đối mặt với thách thức này, nghiên cứu giới thiệu hai cấu trúc dữ liệu tiên tiền là tidset và diffset. Bằng cách sử dụng những cấu trúc này, ba thuật toán cơ bản (TFWIT, TFWID, TFWIN, TFWIN+) duoc phat triển đê khai thác Top-rank-k tập phố biến. Mục tiêu là vượt qua những hạn chế của các thuật toán truyền thống, đồng thời cải thiện thời gian thực hiện và khả năng nén dữ liệu.
Những nghiên cứu này không chỉ đề cập đến vấn đề lý thuyết mà còn tập trung vào sự thực tế và tính ứng dụng của việc khai thác thông tin từ cơ sở dữ liệu có đánh trọng số. Kết quả của thử nghiệm thực nghiệm sẽ cung cấp cái nhìn rõ ràng về sự hiệu quả của các phương pháp đề xuất và mở ra hướng nghiên cứu tương lai trong lĩnh vực nảy. CHUONG 2 -— TONG QUAN VA CO SO LY THUYET Tổng quan: Đề tai nay tập trung vào lĩnh vực khai thác thông tin từ cơ sở dữ liệu có tính chất đặc biệt, khi dữ liệu được đánh trọng số. Mục tiêu chính của nó là phát triển thuật toán khai thác Top-rank-k tập phố biến, nơi tập trung vào xử lý thông tin có trọng số, giúp tìm ra những mẫu thông tin quan trọng mà không phải xử lý tất cả các kết quả có thể xuất hiện.1 Khai thác dữ liệu (Data mining) c Data mining — khai phá dữ liệu là quá trình phân loại, sắp xếp các tập hop dtr liệu nhất định đề xác định xu hướng, các mẫu và thiết lập các mối liên hệ hữu ích nhằm giải quyết các vấn đề nhờ phân tích dữ liệu.
Mục tiêu: cho phép các doanh nghiệp có thể dự đoán được xu hướng tương lai, nhằm đưa ra các quyết định được hỗ trợ dữ liệu từ các tập dữ liệu khong 16. Trọng số của một giao dịch được tính bằng trung bình của trọng số của các mục trong giao dịch đó. Mức hỗ trợ có trọng số của một tập mục (hoặc tập mục) được xác định bằng tý lệ của tổng trọng số của các giao dịch chứa tập mục đó trên tổng trọng số của tất cả các giao dịch. Điều này giúp đo lường sự quan trọng của một tập mục cụ thê trong dữ liệu, đặc biệt khi dữ liệu có sự biến đổi về trọng sé.
Ví dụ: nếu bạn có một tập dữ liệu về mua sắm và mỗi sản phâm có một trọng số dựa trên giá trị của nó, bạn có thé tinh trong số của mỗi giao dịch bằng cách lay trung bình của trọng số của các sản phâm trong giao dịch đó. Sau đó, mức hỗ trợ có trọng số cho một tập mục cụ thể sẽ đo lường mức độ phô biến của tập mục đó trong các giao dịch dựa trên tổng trọng số của các giao dịch mà tập mục đó xuất hiện.2 Khai phá luật kết hợp 121Đụnh nghĩa — Khai thác luật kết hợp là một phương pháp trong lĩnh vực khám phá tri thức từ dữ liệu (Knowledge Discovery in Databases - KDD). Nó nhằm mục đích tìm kiếm các mồi quan hệ kết hợp giữa các mục (items) trong cơ sở dữ liệu. Mục đích của luật kết hợp (Association Rule - AR) là tìm ra các mỗi quan hệ giữa các đôi tượng trong khối lượng lớn dữ liệu.
Ví dụ: Xét CSDL khảo sát tiện nghĩ sử dụng ở các hộ gia đình: Hộ Tiện nghi sở hữu 1 Tivi, maylanh 2 Tulanh, maylanh 3 Tivi, Tulanh, Maylanh 4 Tivi, Maygiat, Maylanh 5 Tivi, Tulanh, Maygiat, Maylanh, May Vitinh 6 Tivi, Maygiat, May Vitinh 7 Tivi, Tulanh, Maygiat 8 Tivi, Maygiat, May Vitinh Luật kết hop 1a biéu thức có dang: Tivi->MayVitinh [50%,57%] hay str dung:Tivi-> str dung: Mayvitinh [50%, 57%] Nghĩa là: “57% hộ gia dinh st dung Tivi thi cing st dung Mayvitinh. Tivi va Máyvitính xuất hiện chung trong 50% dòng dữ liệu." Khai thác luật kết hợp được chia làm hai giai đoạn: 1. Khai thác tập phố biến (FIs — Frequent Itemsets). Sinh luật từ các tập phố biến (ARs — Association Rules).2 Khai thác tập phố biến (Mining ƒrequent weighted itemset) Được đề xuất bởi Agrawal năm 1993.
Bài toán khai thác tập phé bién (frequent itemset) là lớp bài toán rat quan trọng trong lĩnh vực khai phá dữ liệu. Mục tiêu của nó là tìm tất cả các tập mẫu, liên kết, tương quan hoặc cầu trúc nhân quả có độ phô biến cao trong tập hợp tất cả các hạng mục hoặc đối tượng trong cơ sở dữ liệu giao dịch, cơ sở đữ liệu quan hệ và các kho thông tin dữ liệu khác. Đến nay, có nhiều phương pháp được phát trién như: 1. Phuong phap Apriori (Agrawal et al.
Phuong phap IT-tree (Zaki et al. Phuong phap FP-tree (Han et al., 2000) Bai toán tăng lợi nhuận: ° - Một cơ sở đữ liệu giao dich D= {{butter, bread, milk, sugar}; {butter, flour, milk, sugar}; {butter, eggs, milk, salt}; {eggs}; {butter, flour, milk, salt, sugar}} »Ö - Câu hỏi thú vị được đặt ra: items frequency À v — Cac mat: hang© nao sé thudng € dugc: mua chung. véiei {butter} {milk} 4 ị nhau? {butter, milk} 4 {sugar} 3 ag {butter, sugar} 3 > | ng dung {milk, sugar} 3 — Cai thién cach bé tri ctia hang (buttermilk, sugar} 3 {eggs} 2 = Tiếp thị chéo — Tập trung đính kèm thư / bán hàng bổ sung — => Duy trì các don hàng (Các cửa hàng nên làm gì để tăng doanh sốc) — Đồ điện tử gia dung =** (Các cửa hàng nào nên trữ các sản phẩm nào trong kho) Bài toán khai thác các tập phô biến được ứng dụng trong rất nhiều vấn đề, nỗi tiếng nhất là Basket data analysis (dự đoán, gợi ý các món hàng thường được cho cùng vào giỏ hàng với món đồ A đã được chọn mua trước đó). Ngoài ra nó còn được ứng dụng trong lớp các bài toán: tiếp thị chéo, thiết kế danh mục, phân tích thua lỗ, phân 11 cum, phan loai, hé thống khuyến nghị, v.
Và đặc biệt nó còn thê ứng dụng cho thiết kế các dịch vụ tiện ích trong nhà thông minh. “> Tap hang muc (Itemset): Tập hữu hạn I: Là một tập hữu hạn chứa các phần tử được gọi là hạng mục (Item). Tap hang muc X: La m6t tap con của tập hữu han I, tire la X chứa một hoặc nhiéu hang muc tv tap I Tập hạng mục mức k (k_1femset): Là một tập hạng mục X mà nó chứa chính xác k hạng mục. Ví dụ: [= {abc de}; a, b, c, d, e là các hạng mục; X = ƒa d e} là một tập hạng mục mức 3.
Nếu bạn đang làm việc với một cơ sở dữ liệu bán hàng và I là tập hữu hạn của các sản phẩm có săn, thì một k_itemset có thé là tập hạng mục X gồm 3 sản phẩm: {san pham A, san pham B, san pham C}, va đây là một ví dụ về k_itemset mức 3. “ Dộ hỗ trợ (Support- Sup) Độ hỗ trợ của một itemset cho biết tỷ lệ phần trăm (hoặc tần suất) của các giao dich trong tập dữ liệu chứa 1temset đó. Độ hỗ trợ (Sup) của một itemset X được tính bằng cách chia số lần mà X xuất hiện trong tập dữ liệu cho tông số giao dịch trong tập dữ liệu. Thường được biểu thị dưới dạng phần trăm.
_ SỐ lần X xuất hiệntrong tập dữ liệu Công thức: ¿(X) Tổng số giao dịch trong tập dữ liệu Ví dụ: nếu một itemset X có độ phô biến (Sup) là 5%, điều này có nghĩa rằng itemset X xuất hiện trong 5% các giao dịch trong tập dữ liệu. 12 Độ hỗ tro (Support - Sup) cua một luật kết hợp X= Y trong khai thác dữ liệu (data mining) là độ phô biến của cả itemset X và Y kết hợp lại với nhau trong tập dữ liệu. Số lầnitemset X U Y xuất hiệntrong tập dữ liệu ô we: 6(X 5 Y)= = - = Công thức : ) Tổng số giao dịch trong tập đữ liệu Trong đó: itemset X và Y xuất hiện cùng một lúc trong cùng một giao dịch % Độ tin cậy (Confidence - Conf) Độ tin cậylà một thước đo quan trọng trong lĩnh vực khai thác dữ liệu (data mining), đặc biệt khi bạn xem xét các luật kết hợp (association rules) hoặc quy tắc kết hợp giữa các mục (Items) trong tập dữ liệu. Độ tin cậy của một luật kết hợp X= Y (nghĩa là nếu X xuất hiện, thì Y cũng thường xuất hiện).
Số lần Iemset X UY xuất hiện trong tập dữ liệu ô ỨC: X¬ỲŸ)=—.: Ta Ta Công thức: Conf ( Số lần itemsetX xuất hiện trong tập đữ liệu Ví dụ: độ tin cậy của {bơ}——>{trứng} là 80% có nghĩa là 80% khách hàng mua {bơ} cũng mua {trứng}. => Đề thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí: độ hỗ trợ tối thiêu minsup và độ tin cậy tối thiêu minconf là hai giá trị ngưỡng tối thiêu cho trước. Luật kết hợp X— Y được coi là một mẫu có giá trị nếu xảy ra đồng thời minSup và minConf. Một tập X có độ hỗ trợ vượt quá ngưỡng minsup được gọi là một tập phô biến.2 Thuật toán Apriori “+ Dinh nghĩa: Thuật toán Apriori được phát triển bởi Rakesh Agrawal và Ramakrishnan Srikant vào năm 1994.
Đây là một trong những thuật toán đầu tiên được áp dụng rộng rãi trong lĩnh vực khai thác dữ liệu để tìm kiếm mẫu phố biến và luật kết hợp. Nó đã đánh dấu một bước quan trọng trong lĩnh vực này và là một phần quan trọng của nền tảng khai thác dữ liệu ngày nay. 13 Tư tưởng chính của thuật toán Apriori là sử dụng các tính chất quan trọng để tối ưu hóa quá trình tìm kiếm các mẫu phô biến và luật kết hop trong tập dữ liệu lớn.