Tài liệu Phát triển thuật toán khai phá luật kết hợp dựa vào sự phân lớp dữ liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- Bùi Chí Thành PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP DỰA VÀO SỰ PHÂN LỚP DỮ LIỆU Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN HỮU TRỌNG HÀ NỘI – 2013 LỜI CẢM ƠN Trước hết, tác giả muốn gửi lời cảm ơn đến người Thầy hướng dẫn khoa học TS. Nguyễn Hữu Trọng - Trường Đại học Nha Trang đã làm một công việc tuyệt vời. Mặc dù rất bận rộn với với tư cách là một nhà quản lý, một nhà nghiên cứu và một giảng viên nhưng thầy luôn luôn dành thời gian để giúp đỡ, hỗ trợ tác giả hoàn thành luận văn này. Tác giả xin chân thành cảm ơn quý Thầy Cô Viện Công nghệ thông tin và Truyền Thông – Trường Đại học Bách Khoa Hà Nội, quý Thầy cô Trường Đại học Nha Trang, … bởi sự quan tâm giúp đỡ tận tâm trong quá trình học tập, nghiên cứu cũng như trong quá trình hoàn thành luận văn. Cuối cùng xin chân thành cảm ơn đến người vợ thân yêu, những người thân, bạn bè và đồng nghiệp đã động viên, giúp đỡ trong suốt quá trình học tập và viết luận văn. Hà Nội, tháng 3 năm 2013 Bùi Chí Thành 2 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn của TS Nguyễn Hữu Trọng. Các số liệu, kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Hà Nội, ngày 15 tháng 3 năm 2013 Bùi Chí Thành 3 MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT..........................................6 DANH MỤC CÁC BIỂU BẢNG .............................................................................7 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................8 MỞ ĐẦU ....................................................................................................................9 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .....................................11 1.1 MỞ ĐẦU .........................................................................................................11 1.2 CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU .........................................................14 1.2.1 Luật kết hợp ..............................................................................................14 1.2.2 Phân lớp dữ liệu ........................................................................................15 1.2.3 Phân nhóm dữ liệu ....................................................................................16 1.3 CÁC KHÁI NIỆM CƠ BẢN...........................................................................17 1.3.1 Cơ sở dữ liệu giao tác ...............................................................................17 1.3.2 Tính chất của tập thường xuyên ...............................................................20 1.4 KHAI PHÁ LUẬT KẾT HỢP.........................................................................21 1.4.1 Cách tiếp cận khai phá luật kết hợp ..........................................................21 1.4.2 Nhóm thuật toán duyệt theo chiều rộng....................................................23 1.4.3 Nhóm thuật toán duyệt theo chiều sâu......................................................29 1.4.4 Thuật toán Partition_P_Tree .....................................................................36 1.4.5 Thuật toán phân hoạch kép ......................................................................37 1.5 KẾT LUẬN .....................................................................................................39 CHƯƠNG 2. PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP DỰA VÀO SỰ PHÂN LỚP DỮ LIỆU ..................................................................40 4 2.1 PHÂN LỚP DỮ LIỆU ...................................................................................40 2.1.1 Một số định nghĩa trên CSDL giao tác .....................................................40 2.1.2 Phân lớp CSDL giao tác ...........................................................................41 2.2 THUẬT TOÁN PHÂN LỚP DỮ LIỆU ..........................................................42 2.2.1 Mô tả bài toán ...........................................................................................42 2.2.2 Xử lý .........................................................................................................42 2.3 PHÁT TRIỂN THUẬT TOÁN TÌM TẬP THƯỜNG XUYÊN TRÊN CSDL ĐÃ PHÂN LỚP .....................................................................................................45 2.3.1 Phát triển thuật toán xây dựng FP_Tree ...................................................45 2.3.2 Thuật toán Apriori ....................................................................................45 2.4 VÍ DỤ MINH HỌA .........................................................................................46 CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM ...................................................................................................................................50 3.1 CẤU TRÚC DỮ LIỆU ....................................................................................50 3.2 CÁC THỦ TỤC CÀI ĐẶT .............................................................................51 3.3 KẾT QUẢ THỬ NGHIỆM .............................................................................57 3.4 ĐÁNH GIÁ THUẬT TOÁN ...........................................................................58 PHẦN KẾT LUẬN ..................................................................................................59 1. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC ....................................................................59 2. HƯỚNG PHÁT TRIỂN ....................................................................................60 TÀI LIỆU THAM KHẢO ......................................................................................61 0. 5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Trong suốt luận văn này, các ký hiệu, chữ viết tắt dùng thống nhất: Ký hiệu: I = {x 1 , x 2 , …, x n }: Tập n mục dữ liệu. T = {t 1 , t 2 , …, t m }: Cơ sở dữ liệu có m giao tác. x j : Mục dữ liệu thứ j. t i : Giao tác thứ i. m: Số giao tác của một cơ sở dữ liệu giao tác. n: Số mục dữ liệu của một cơ sở dữ liệu giao tác. A, B, C, …: Tên của các mục dữ liệu trong cơ sở dữ liệu giao tác ví dụ. X, Y: Là các tập con của tập mục dữ liệu I, X, Y ⊆ I. S: Là tập con các giao tác của cơ sở dữ liệu giao tác T, S ⊆ T. X = ABC thay cho X = {A, B, C} trong các ví dụ minh họa. S = 1234 thay cho S = {t 1 , t 2 , t 3 , t 4 } trong các ví dụ minh họa. S 0 , Minsup: Ngưỡng tối thiểu. Supp(x i ) thay cho Supp({x i }). ∥X∥: Số phần tử của tập hợp X. Subset(U) = {X | X ⊆ U}: Tập các tập con của U. Viết tắt: CSDL: Cơ sở dữ liệu. DL: Dữ liệu. MDL: Mục dữ liệu. TT: Thuật toán. 6 DANH MỤC CÁC BIỂU BẢNG Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác ...............................................18 Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác ...................................................18 Bảng 1.3 Ma trận giao tác của cơ sở dữ liệu giao tác cho ở bảng 1.1.......................19 Bảng 2.1 CSDL giao tác mẫu..................................................................................496 Bảng 2.2 CSDL đã được sắp xếp giảm dần của độ hỗ trợ ........................................47 Bảng 2.3 CSDL có trọng số rút gọn ..........................................................................48 Bảng 2.4 CSDL có trọng số được loại bỏ những mục không thường xuyên ............49 Bảng 2.5 CSDL có trọng số được rút gọn thỏa ngưỡng S 0 =2 ..................................49 Bảng 3.1 So sánh kết quả trước và sau khi phân lớp ................................................57 7 1. DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Quá trình khám phá tri thức .............................................................12 Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu ..................................................13 Hình 1.3 Cây quyết định...................................................................................16 Hình 1.4 Phân loại thực toán khai phá luật kết hợp .........................................23 Hình 1.5 Kết quả thuật toán AIS ......................................................................24 Hình 1.6 Kết quả thuật toán Apriori .................................................................26 Hình 1.7 Những biến đổi dữ liệu của FP_Tree ................................................30 Hình 1.8 FP_Tree của dữ liệu bảng 1.1 ............................................................31 Hình 1.9 Thành phần của FP_Tree...................................................................31 Hình 1.10 Cấu trúc cây SOTrieIT ....................................................................34 Hình 1.11 SOTrieIT của dữ liệu ở bảng 1.1 .....................................................35 Hình 2.1 Cây trọng số W_Tree ........................................................................42 Hình 2.2 Cây trọng số W_Tree dựa vào bảng 2.1 ............................................48 Hình 2.3 Cây FP_Tree trên CSDL có trọng số rút gọn ..................................489 2. 8 3. MỞ ĐẦU Thông tin được thu thập hầu như ở khắp mọi nơi trong cuộc sống của chúng ta ở rất nhiều lĩnh vực đời sống xã hội, quản lý kinh tế, khoa học kỹ thuật, …và với sự phát triển nhanh chóng các ứng dụng công nghệ thông tin và Internet đã tạo ra nhiều cơ sở dữ liệu khổng lồ mức độ terabytes đến mức độ petabytes. Để khai thác hiệu quả nguồn thông tin từ các cơ sở dữ liệu lớn hỗ trợ tiến trình ra quyết định, bên cạnh các phương pháp khai thác thông tin truyền thống, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và phần mềm mới hỗ trợ tiến trình khám phá, phân tích tổng hợp thông tin. Có nhiều kỹ thuật khai phá dữ liệu trong đó khai phá luật kết hợp là kỹ thuật rất nổi tiếng. Bài toán khai phá luật kết hợp được giải theo hai bước chính: Bước một, tìm tất cả các tập thường xuyên theo ngưỡng S 0 cho trước. Bước hai, dựa vào các tập thường xuyên, tìm các luật kết hợp. Tất cả khó khăn của bài toán tập trung ở bước một. Các nghiên cứu về khai phá luật kết hợp đều tập trung cải tiến tốc độ xử lý, dung lượng bộ nhớ và số lần truy cập đĩa. Tốc độ xử lý phụ thuộc vào số giao tác trong cơ sở dữ liệu giao tác. Mục tiêu của luận văn là tìm hiểu một số thuật toán khai phá luật kết hợp, đề xuất phương án phân lớp dữ liệu giao tác bằng cách thêm ”trọng số” cho mục dữ liệu, rút gọn số giao tác trong cơ sở dữ liệu nhằm rút gọn không gian xử lý, lưu trữ. Đưa ra thuật toán cải tiến thuật toán Apriori và FP_Growth để tìm tập thường xuyên trên cơ sở dữ liệu đã phân lớp. Bố cục của luận văn bao gồm phần mở đầu, ba chương nội dung, phần kết luận và tài liệu tham khảo. Chương 1 trình bày tổng quan về khai phá dữ liệu: Các mô hình khai phá dữ liệu, các khái niệm cơ bản về khai phá luật kết hợp và một số thuật toán khai phá luật kết hợp: Các thuật toán duyệt theo chiều rộng (AIS, Apriori, DIC), các thuật 9 toán duyệt theo chiều sâu (FP_Tree, RARM), thuật toán PARTITION_P_TREE, thuật toán phân hoạch kép. Đóng góp chính của luận văn được trình bày trong chương 2. Chương này, tác giả đề xuất phương án phân lớp dữ liệu để rút gọn số giao tác trong CSDL và phát triển 2 thuật toán (Apriori, Fp_Tree) trên cơ sở dữ liệu đã phân lớp để tìm tập thường xuyên. Chương 3. Xây dựng chương trình và kết quả thử nghiệm Cuối cùng, phần kết luận nêu những đóng góp của luận văn, hướng phát triển và những vấn đề quan tâm của tác giả. 10 4. CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1 MỞ ĐẦU Khai phá dữ liệu – Data Mining là tiến trình khám phá tri thức tiềm ẩn trong các cơ sở dữ liệu. Cụ thể hơn, đó là tiến trình trích lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chưa biết nhưng hữu ích từ các cơ sở dữ liệu lớn. Khai phá dữ liệu là tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính khái quát, tính quy luật hỗ trợ tích cực cho các tiến trình ra quyết định. Nguồn dữ liệu phục vụ cho khai phá dữ liệu có thể là các cơ sở dữ liệu lớn hay các kho dữ liệu có hoặc không có cấu trúc. Có thể chia khai phá dữ liệu thành hai dạng chính: khai phá dữ liệu theo hướng kiểm tra và khai phá dữ liệu theo hướng khám phá. Trong khai phá dữ liệu theo hướng kiểm tra tính đúng đắn của giả thiết. Khai phá dữ liệu theo hướng kiểm tra, người dùng đề xuất giả thiết. Khai phá dữ liệu theo hướng kiểm tra bao gồm: truy vấn, báo cáo, phân tích đa chiều, phân tích thống kê, … Ngược lại, khai phá dữ liệu theo hướng khám phá sẽ tìm kiếm các tri thức tiềm ẩn trong cơ sở dữ liệu bằng cách tiến hành xem xét tất cả các giả thiết khả dĩ. Do không gian tìm kiếm lớn, nên rất nhiều heuristic đã được đề xuất nhằm nâng cao hiệu suất của các thuật giải tìm kiếm. Tri thức rút ra có thể được dùng để: - Giải thích dữ liệu: Cung cấp sự hiểu biết sâu sắc và rất hữu ích về hành vi của các đối tượng, giúp cho các doanh nghiệp hiểu rõ hơn những khách hàng của họ. - Dự báo, dự đoán giá trị của những đối tượng mới như: Khuynh hướng mua hàng của khách hàng, xác định rủi ro tín dụng đối với một khách hàng, định hướng tập trung nguồn lực của doanh nghiệp. Các bước của quá trình khai phá dữ liệu: 1. Tìm hiểu lĩnh vực của bài toán (ứng dụng): Các mục đích của bài toán, các tri thức cụ thể của lĩnh vực 11 2. Tạo nên (thu thập) một tập dữ liệu phù hợp 3. Làm sạch và tiền xử lý dữ liệu 4. Giảm kích thước của dữ liệu, chuyển đổi dữ liệu: Xác định các thuộc tính quan trọng, giảm số chiều, … 5. Lựa chọn chức năng khai phá dữ liệu: Tóm tắt hóa, phân loại/phân lớp, hồi quy/dự đoán, kết hợp, phân cụm 6. Lựa chọn/phát triển các giải thuật khai phá dữ liệu phù hợp 7. Tiến hành quá trình khai phá dữ liệu 8. Đánh giá mẫu thu được và biểu diễn tri thức: Hiện thị hóa, chuyển đổi, bỏ đi các mẫu dư thừa, … 9. Sử dụng các tri thức được khám phá Khai phá dữ liệu đóng vai trò quan trọng trong quá trình khám phá tri thức, được Han và Kamber [8] mô tả trong hình 1.1: Hình 1.1. Quá trình khám phá tri thức 12 Kiến trúc hệ thống khai phá tri thức được Han và Kamber [8] mô tả trong hình 1.2: Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu Quá trình khai phá dữ liệu trải qua ba bước: Bước một: Lọc dữ liệu hay gọi là tiền xử lý. Khi dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Chẳng hạn, trong bài toán tìm quy luật mua hàng của khách hàng trong một siêu thị, ta tìm xem một khách hàng thường cùng mua những mặt hàng nào để sắp xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể có nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng, nhà cung cấp, đơn giá hàng, người bán hàng… Các thuộc tính này cần cho quản lý bán hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này khỏi dữ liệu trước khi khai phá dữ liệu. 13 Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu. Bước ba: Hậu xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật khác nhau cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những tiêu chí đánh giá nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. 1.2 CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU Nói chung, có hai mô hình khai phá dữ liệu: Mô tả và suy diễn. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu. Suy diễn là quá trình dựa trên dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu. Có nhiều cách khai phá dữ liệu được nghiên cứu, trong đó có ba cách được các nhà nghiên cứu sử dụng nhiều nhất là: Luật kết hợp, phân lớp dữ liệu và phân nhóm dữ liệu. 1.2.1 Luật kết hợp Khái niệm luật kết hợp được Agrawal và nhóm nghiên cứu đưa ra năm 1993[9]. Mục tiêu của luật kết hợp là tìm ra những mối tương quan giữa những mục dữ liệu thường xuyên trong cơ sở dữ liệu được lưu trữ trong kho dữ liệu. Ví dụ 1.1 Trong một hiệu sách lưu lại các phiếu mua sách, người ta phát hiện ra rằng: Trong số những người mua quyển "Các khái niệm và kỹ thuật khai phá dữ liệu" thì có 40% số người đó mua thêm quyển "Hệ quản trị cơ sở dữ liệu", và 25% mua thêm quyển "Kho dữ liệu". Trong ví dụ trên, hai luật kết hợp được tìm thấy: - Có 40% số người mua quyển "Các khái niệm và kỹ thuật khai phá dữ liệu" thì đồng thời mua quyển "Hệ quản trị cơ sở dữ liệu". 14 - Có 25% số người mua quyển "Các khái niệm và kỹ thuật khai phá dữ liệu" thì đồng thời mua quyển "Kho dữ liệu". Với những quy tắc được khám phá trên, ta có thể sắp xếp các quyển sách có liên quan với nhau ở vị trí gần nhau để giúp cho người mua sách thuận tiện hơn. Những quy tắc đó cũng giúp cho nhà sách có chiến lược kinh doanh tốt hơn. Luật kết hợp được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau như: Kinh doanh, sản xuất, giao thông, viễn thông, giáo dục, quản lý thị trường, … 1.2.2 Phân lớp dữ liệu Khái niệm phân lớp dữ liệu được Han và Kamber tổng kết năm 2000 trong [8]. Phân lớp dữ liệu là xây dựng một mô hình mà có thể chia các đối tượng thành những lớp khác nhau để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai. Quá trình phân lớp dữ liệu được thực hiện qua hai bước. Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm. Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán: Murthy S. K. đã nghiên cứu toàn diện về cây quyết định [10], phân lớp Bayes. 15 Một ví dụ tiêu biểu về cây quyết định: Tuổi <30 30-35 Sinh viên Yes >35 Giáo sư Yes No Yes No Hình 1.3 Cây quyết định Trong hình 1.3 là một cây quyết định cho lớp mua máy laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là "Yes" hay "No". Sau khi mô hình này được xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính tuổi và nghề nghiệp của khách hàng. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực. 1.2.3 Phân nhóm dữ liệu Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu. Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, và nhóm những đối tượng vào trong những lớp tương đương [8], để những đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong những nhóm khác. Trong phân lớp dữ liệu, bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những hàm đánh giá sự tương tự. Thông thường những hàm định lượng như hàm đo khoảng cách, hàm xác định độ đo,… được xác định bởi những chuyên gia trong lĩnh vực chuyên môn của mình. 16 Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị trường. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể cung cấp những dịch vụ khác nhau tới từng nhóm khách hàng một cách thuận lợi. Ví dụ, dựa vào số tiền trong tài khoản, mục đích chi tiêu và việc rút tiền của khách hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tương ứng. 1.3 CÁC KHÁI NIỆM CƠ BẢN 1.3.1 Cơ sở dữ liệu giao tác 1.3.1.1 Định nghĩa 1.1 Cho I = {x 1, x 2 , …, x n} là tập hợp các mục dữ liệu. Mỗi x i ∈ I gọi là một mục dữ liệu hay là một thuộc tính. Một tập con {x i1 , xi2 , …, x ik} ⊆ I được gọi là một giao tác trên I. Đặt t i = {x i1 , x i2 , …, x ik}, t i gọi là định danh của giao tác {x i1 , x i2 , …, x ik}. Một tập hợp gồm m định danh giao tác T = {t 1 , t 2 , …, t m }, với m bất kỳ được gọi là một cơ sở dữ liệu giao tác trên I. Mỗi tập con X ⊆ I với ‖X‖ = k được gọi là tập k-mục dữ liệu hay k-thuộc tính của I (trong trường hợp không quan tâm đến số mục dữ liệu của X, ta gọi tắt: X là tập mục dữ liệu), mỗi tập con S ⊆ T gọi là tập định danh giao tác. Để thuận tiện trong các ví dụ, ta viết S = {t 1 , t 2 , t 3 }, XY thay cho X ∪ Y. 1.3.1.2 Biểu diễn cơ sở dữ liệu giao tác Có hai cách biểu diễn tập cơ sở dữ liệu giao tác: Biểu diễn ngang và biểu diễn dọc. Biểu diễn ngang: Một 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 giao tác (t id ) và một danh sách những mục dữ liệu trong giao tác đó. 17 Ví dụ 1.2 Giao tác Mục dữ liệu t1 A, B, E t2 B, D t3 B, C t4 A, B, D t5 A, C t6 B, C t7 A, C t8 A, B, C, E t9 A, B, C Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác Biểu diễn dọc: Một cơ sở dữ liệu là một danh sách những mục dữ liệu, với 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. Mục dữ liệu Định danh giao tác A t1, t4, t5, t7, t8, t9 B t1, t2, t3, t4, t6, t8, t9 C t3, t5, t6, t7, t8, t9 D t2, t4 E t1, t8 Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác Ma trận giao tác: Cho một cơ sở dữ liệu giao tác T = {t1, t2, …, tm} trên I = {x1, x2, …, xn}. Ma trận giao tác của T là ma trận M = (mij)mxn được định nghĩa: 1 khi x j ∈ t i m ij =  0 khi x j ∉ t i 18 Ví dụ 1.3 Với cơ sở dữ liệu giao tác ở bảng 1.1 ta có ma trận giao tác là: A B C D E t1 1 1 0 0 1 t2 0 1 0 1 0 t3 0 1 1 0 0 t4 1 1 0 1 0 t5 1 0 1 0 0 t6 0 1 1 0 0 t7 1 0 1 0 0 t8 1 1 1 0 1 t9 1 1 1 0 0 Bảng 1.3 Ma trận giao tác của cơ sở dữ liệu giao tác cho ở bảng 1.1 1.3.1.3 Độ hỗ trợ (support) Độ hỗ trợ của một tập mục dữ liệu X ⊆ I trong cơ sở dữ liệu giao tác T, ký hiệu Supp(X) là tổng số các giao tác trong T chứa X. Supp(X) = ∥{t ∈ T | X ⊆ t}∥. Với cơ sở dữ liệu cho ở bảng 1.1 ta có: Supp(A) = 6, Supp(B) = 7, Supp(ABC) = 2, Supp(DE) = 0. 1.2.1.4 Tập mục dữ liệu thường xuyên (frequent itemset) Cho S 0 là một số nguyên, ta nói X là tập mục dữ liệu thường xuyên theo ngưỡng S 0 (gọi tắt là tập thường xuyên) nếu Supp(X) ≥ S 0 . Nếu X = {x i } và Supp(X) ≥ S 0 ta nói : x i là mục dữ liệu thường xuyên. Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:  AB, AC, BC: là các tập thường xuyên theo ngưỡng S 0 = 4. 19  A, B, C: là các mục dữ liệu thường xuyên theo ngưỡng S 0 = 5. 1.2.1.5 Luật kết hợp (Association rule) Một luật kết hợp trên cơ sở dữ liệu giao tác T là một biểu thức có dạng X → Y, với X, Y ⊆ I và X ∩ Y = φ. Độ hỗ trợ của luật kết hợp X → Y, được định nghĩa và ký hiệu: Supp(X → Y) = Supp(XY). Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có: Supp(A → B) = Supp(AB) = 4, Supp(AB → C) = Supp(ABC) = 2, Supp(AB → E) = Supp(ABE) = 2, Supp(BC → E) = Supp(BCE) = 1. Luật kết hợp f: X → Y trên T là luật thường xuyên theo ngưỡng S 0 nếu Supp(X → Y) ≥ S 0 . Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có: f: A → B là luật thường xuyên theo ngưỡng S 0 = 4 vì Supp(AB) = 4 ≥ 4 f: AB → C không là luật thường xuyên theo ngưỡng S0 = 4 vì Supp(ABC) = 2 < 4 Độ tin cậy (Confidence) của luật X → Y, được định nghĩa và ký hiệu: p = Conf(X → Y) = Supp(XY) / Supp(X). Với C 0 ∈ (0, 1] ta nói f: X → Y gọi là luật tin cậy (Confident rule) theo ngưỡng S 0 và C 0 nếu f là luật thường xuyên theo ngưỡng S 0 và Conf(X → Y) ≥ C 0 . Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có: f: A → B là luật tin cậy theo ngưỡng S 0 = 4 và C 0 = 0.5 vì Supp(AB) = 4 ≥ 4 và Conf(A → B) = Supp(AB) / Supp(A) = 4/7 = 0.55 > 0.5. 1.3.2 Tính chất của tập thường xuyên Tính chất 1.1 Gọi Fre(T, S 0 , I) là tập tất cả các tập mục dữ liệu thường xuyên theo ngưỡng S 0 của cơ sở dữ liệu giao tác T trên I. Ta có các tính chất sau: 20