DATA MINING AND APPLICATION: KHAI THÁC TẬP PHỔ BIẾN & LUẬT KẾT HỢP

Mẫu phổ biến : là mẫu (tập các hạng mục, chuỗi con, cấu trúc con, đồ thị con, …) xuất hiện thường xuyên trong tập DL– Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ biến và luật kết hợp
Nội dung trích xuất từ tài liệu:
DATA MINING AND APPLICATION: KHAI THÁC TẬP PHỔ BIẾN & LUẬT KẾT HỢP KHAI THÁC DỮ LIỆU & ỨNG DỤNG(DATA MINING) GV : NGUYỄN HOÀNG TÚ ANH 1 BÀI 3- PHẦN 1 KHAI THÁCTẬP PHỔ BIẾN & LUẬT KẾT HỢP 2 1 NỘI DUNG 1. Giới thiệu 2. Các khái niệm cơ bản 3. Bài toán khai thác tập phổ biến 3 GIỚI THIỆU Mẫu phổ biến : là mẫu (tập các hạng mục, chuỗi con, cấu trúc con, đồ thị con, …) xuất hiện thường xuyên trong tập DL – Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ biến và luật kết hợp Mục đích : Tìm các hiện tượng thường xuyên xảy ra trong DL – Những sản phẩm nào thường được mua chung ? Bia và tã lót – Người ta thường mua gi tiếp theo sau khi mua máy PC ? – Dạng DNA nào có phản ứng với công thức thuốc mới ? – Làm thế nào đề phân loại tự động văn bản Web ? Ứng dụng : – Áp dụng trong phân tích CSDL bán hàng – Mở rộng sang quảng cáo, thiết kế catalog, phân tích chiến 4 dịch bán hàng, Web log, chuỗi DNA, … 2 GIỚI THIỆU Bài toán khai thác tập phổ biến là bài toán rất quan trọng lĩnh vực KTDL : vạch ra tính chất ẩn, quan trọng của tập DL Là nền tảng cho nhiều nhiệm vụ KTDL khác : – Phân tích luật kết hợp, mối tương quan – Mẫu tuần tự, cấu trúc ( Vd : đồ thị con) – Phân tích DL không gian, đa phương tiện, phụ thuộc thời gian – Phân loại : phân loại dựa trên luật kết hợp – Phân tích nhóm: gom nhóm dựa trên mẫu phổ biến – …. 5NỘI DUNG1. Giới thiệu2. Các khái niệm cơ bản3. Bài toán khai thác tập phổ biến 6 3 KHÁI NIỆM CƠ BẢN CSDL GIAO DỊCH1. TID Produces (Transaction DB) 1 MILK, BREAD, EGGS VD giỏ mua hàng: 2 BREAD, SUGAR 3 BREAD, CEREAL Giỏ 1: {Bánh mì, o 4 MILK, BREAD, SUGAR Trứng, Sữa} 5 MILK, CEREAL Giỏ 2: {Bánh 6 BREAD, CEREAL mì, o 7 MILK, CEREAL Đường} MILK, BREAD, CEREAL, … 8 EGGS Giỏ n: {Bánh qui, ngũ 9 MILK, BREAD, CEREAL o cốc, sữa} 7 KHÁI NIỆM CƠ BẢN TID Products TID A B C D E 1 A, B, E 1 1 1 0 0 1 2 B, D 2 0 1 0 1 0 3 B, C 3 0 1 1 0 0 4 A, B, D 4 1 1 0 1 0 5 A, C 5 1 0 1 0 0 Biến đổi CSDL về 6 B, C 6 0 1 1 0 0 dạng nhị phân 7 A, C 7 1 0 1 0 0 8 A, B, C, E 8 1 1 1 0 1 9 A, B, C 9 1 1 1 0 0 ITEMS: A = milk B= bread C= cereal D= sugar 8 E= eggs 4 KHÁI NIỆM CƠ BẢN CSDL GIAO DỊCH (tt)1. Định nghĩa : Hạng mục (Item) : mặt hàng trong giỏ hay một thuộc tính o Tập các hạng mục (itemset) I = {i1, i2, …, im} : o VD : I = {sữa, bánh mì, ngũ cốc, sữa chua} Tập k hạng mục (k-itemset) Giao dịch (Transation) : tập các hạng mục được mua trong o một giỏ ( có TID – mã giao dịch) : (Tid, tập hạng mục) Giao dịch t : tập các hạng mục sao cho t  I o o VD : t = { bánh mì, sữa chua, ngũ cốc} CSDL giao dịch : tập các giao dịch o CSDL D = {t1,t2, …, tn} , ti={ii1,ii2, …, iik} với iij  I : CSDL o giao dịch 9 KHÁI NIỆM CƠ BẢN 2 ...