Tài liệu Khai phá tập mục lợi ích cao trong cơ sở dữ liệu lớn

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT&TT --------------------------- ĐỖ THỊ HẢI YẾN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU LỚN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT&TT --------------------------- ĐỖ THỊ HẢI YẾN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU LỚN CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN THANH TÙNG THÁI NGUYÊN - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan Luận văn "Khai phá tập mục lợi ích cao trong cơ sở dữ liệu lớn" là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS.TS Nguyễn Thanh Tùng. Kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ luận văn, những điều được trình bày là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Thái Nguyên, ngày 30 tháng 9 năm 2011 Ngƣời cam đoan Đỗ Thị Hải Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới PGS.TS. Nguyễn Thanh Tùng - Viện Công nghệ thông tin, người thầy đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này. Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện và khuyến khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo của Viện Công nghệ thông tin, Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên. Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè những người luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến khích tôi trong cuộc sống và trong công việc. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 30 tháng 9 năm 2011 Tác giả Đỗ Thị Hải Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i MỤC LỤC Trang Trang bìa phụ Lời cảm ơn Lời cam đoan Mục lục ..................................................................................................................i Danh mục các từ, các ký hiệu viết tắt ................................................................ iii Danh mục các bảng ............................................................................................iv Danh mục các hình .............................................................................................. v LỜI MỞ ĐẦU .............................................................................................................. 1 Chƣơng 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ........................................................................ 4 1.1. Khai phá dữ liệu ................................................................................................. 4 1.2. Khai phá tập mục thường xuyên......................................................................... 8 1.2.1. Cơ sở dữ liệu giao tác .................................................................................. 8 1.2.2. Tập mục thường xuyên và luật kết hợp ..................................................... 10 1.2.3 Bài toán khai phá luật kết hợp .................................................................... 11 1.3. Các cách tiếp cận khai phá tập mục thường xuyên .......................................... 12 1.3.1 Thuật toán Apriori ...................................................................................... 13 1.3.2 Thuật toán FP-growth ................................................................................. 17 1.4. Mở rộng bài toán khai phá tập mục thường xuyên ........................................... 23 1.5. Kết luận chương 1 ............................................................................................ 24 Chƣơng 2. KHAI PHÁ TẬP MỤC LỢI ÍCH CAO: BÀI TOÁN VÀ BA THUẬT GIẢI KIỂU APRIORI ............................................................................... 25 2.1. Mở đầu .............................................................................................................. 25 2.2. Bài toán khai phá tập mục lợi ích cao .............................................................. 26 2.3. Ba thuật toán khai phá tập mục lợi ích cao kiểu Apriori .................................. 30 2.3.1. Thuật toán UMining .................................................................................. 30 2.3.2. Thuật toán UMining-H .............................................................................. 32 2.3.3. Thuật toán hai pha HUMining ................................................................... 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii 2.4. Kết luận chương 2 ............................................................................................ 41 Chƣơng 3. THUẬT TOÁN HIỆU QUẢ KHAI PHÁ TẬP MỤC LỢI ÍCH CAO KIỂU FP-GROWTH....................................................................................... 42 3.1 Mở đầu ............................................................................................................... 42 3.2. Thuật toán COUI-Mine .................................................................................... 42 3.2.1. Xây dựng cây TWUI-tree .......................................................................... 44 3.2.2. Khai phá cây TWUI-tree ........................................................................... 48 3.2.3. Đánh giá độ phức tạp của thuật toán COUI-Mine ..................................... 55 3.2.4. Nhận xét thuật toán COUI-Mine ............................................................... 58 3.2.5. Khai phá tương tác với cây TWU-tree ...................................................... 59 3.3. Kết luận chương 3 ............................................................................................ 60 KẾT LUẬN ................................................................................................................ 62 TÀI LIỆU THAM KHẢO ........................................................................................ 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii DANH MỤC CÁC TỪ VIẾT TẮT Nghĩa của cụm từ viết tắt STT Cụm từ viết tắt 1 CNTT Công nghệ thông tin 2 CSDL Cơ sở dữ liệu 3 KDD Khám phá tri thức trong cơ sở dữ liệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv DANH MỤC CÁC BẢNG Trang Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác .................................................. 9 Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác ...................................................... 9 Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu bảng 1.1 ............................................... 10 Bảng 1.4: Cơ sở dữ liệu giao tác minh hoạ thực hiện thuật toán Apriori. .................. 16 Bảng 1.5: Cơ sở dữ liệu giao tác minh hoạ thực hiện thuật toán COFI-tree .............. 19 Bảng 1.6: Các mục dữ liệu và độ hỗ trợ...................................................................... 20 Bảng 1.7: Các mục dữ liệu thường xuyên đã sắp thứ tự ............................................. 20 Bảng 1.8: Các mục dữ liệu trong giao tác sắp giảm dần theo độ hỗ trợ. .................... 21 Hình 1.4: Các bước khai phá cây D-COFI-tree. ......................................................... 23 Bảng 2.1. Cơ sở dữ liệu giao tác ................................................................................. 27 Bảng 2.2. Giá trị lợi ích chủ quan của các mục trong bảng 1. ................................... 27 Hình 2.1. Dàn tập mục trong cơ sở dữ liệu bảng 1 .................................................... 29 Bảng 3.1: Lợi ích các giao tác của cơ sở dữ liệu ........................................................ 45 Bảng 3.2: Lợi ích TWU của các mục dữ liệu.............................................................. 45 Bảng 3.3: Các mục dữ liệu có lợi ích TWU cao sắp giảm dần theo twu .................... 46 Bảng 3.4: Các mục dữ liệu trong giao tác sắp giảm dần theo lợi ích TWU. .............. 46 Hình 3.7: Cây D-COUI-tree ........................................................................................ 50 Bảng 3.5: Lợi ích các tập mục ứng viên ..................................................................... 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH MỤC CÁC HÌNH Trang Hình 1.1. Các bước thực hiện của quá trình khai phá dữ liệu ....................................... 6 Hình 1.2: Cây FP-tree của CSDL bảng 1.5. ................................................................ 21 Hình 1.3: Cây COFI-tree của mục D .......................................................................... 21 Hình 2.2. Không gian tìm kiếm tập mục lợi ích cao theo thuật toán UMining ......... 32 Hình 2.3. Không gian tìm kiếm tập mục lợi ích cao theo thuật toán UMining-H ..... 33 Hình 2.4. Không gian tìm kiếm tập mục lợi ích cao theo thuật toán HUMining ............ 39 Hình 3.1: Cây TWUI-tree sau khi lưu thao tác T1. ..................................................... 47 Hình 3.2: Cây TWUI-tree sau khi lưu thao tác T1 và T2. .......................................... 47 Hình 3.3: Cây TWUI-tree của cơ sở dữ liệu bảng 3.1 và 3.2. .................................... 47 Hình 3.4: Cây C-COUI-tree sau khi lưu mẫu CBE..................................................... 49 Hình 3.5: Cây C-COUI-tree sau khi lưu mẫu CBE và CE .......................................... 50 Hình 3.6: Cây C-COUI-tree sau khi xây dựng xong. .................................................. 50 Hình 3.8: Cây B-COUI-tree ........................................................................................ 51 Hình 3.9: Các bước khai phá cây D-COUI-tree. ......................................................... 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI MỞ ĐẦU Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ thông tin, truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin không ngừng được nâng cao. Với lượng dữ liệu khổng lồ và luôn gia tăng theo thời gian, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai thác hiệu quả các cơ sở dữ liệu lớn, một lĩnh vực khoa học mới đã ra đời: Khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD). Khai phá dữ liệu (Data Mining) là một công đoạn chính trong qúa trình khám phá tri thức, nhằm tìm kiếm, phát hiện các tri thức mới, hữu ích tiềm ẩn trong các cơ sở dữ liệu lớn. Khai phá luật kết hợp là một nhiệm vụ quan trọng của khai phá dữ liệu. Bài toán truyền thống (hay còn gọi bài toán nhị phân) khai phá luật kết hợp do R. Agrawal, T. Imielinski và A. N. Swami đề xuất và nghiên cứu lần đầu tiên vào năm 1993 khi phân tích các cơ sở dữ liệu của các siêu thị. Mục tiêu của nó là phát hiện các tập mục thường xuyên, từ đó tạo các luật kết hợp phản ánh hành vi mua hàng của khách hàng. Những thông tin như vậy giúp nhà quản lý có thể lựa chọn phương án tiếp thị, kinh doanh hiệu quả hơn. Cho đến nay, bài toán khai phá luật kết hợp truyền thống có nhiều ứng dụng, tuy vậy do tập mục thường xuyên chỉ mang ngữ nghĩa thống kê nên mô hình bài toán truyền thống chỉ đáp ứng được phần nào nhu cầu ứng dụng thực tiễn. Thật ra, trong kinh doanh, điều mà người quản lý quan tâm hơn là phát hiện những khách VIP, đem lại lợi nhuận cao. Trong thực hành, có những tập mục thường xuyên nhưng chỉ đóng góp phần rất nhỏ, ngược lại có những tập mục không thường xuyên lại đóng góp phần đáng kể vào lợi nhuận chung của công ty. Gần đây, nhằm khắc phục hạn chế của bài toán truyền thống khai phá luật kết hợp, các nhà nghiên cứu đã mở rộng nó theo nhiều hướng khác nhau, trong đó có vấn đề khai phá tập mục lợi ích cao. Lợi ích của một tập mục là số đo lợi nhuận mà nó có thể mang lại trong kinh doanh, được tính toán dựa trên giá trị khách quan và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 giá trị chủ quan của các mục thành viên. Giá trị khách quan của một mục là số đơn vị mục bán được, dữ liệu này có sẵn trong cơ sở dữ liệu. Giá trị chủ quan của một mục là giá trị lợi nhuận mà mỗi đơn vị mục có thể đem lại, theo đánh giá của nhà kinh doanh. Khai phá tập mục lợi ích cao là khám phá tất cả tập mục X đem lại lợi ích u( X )   , trong đó  là ngưỡng quy định bởi người sử dụng. Trong khai phá luật kết hợp truyền thống, các thuật toán khám phá tập mục thường xuyên được xây dựng theo phương pháp tìm kiếm từng bước. Cơ sở của các thuật toán này là tính chất Apriori hay còn gọi là tính chất phản đơn điệu (anti monotone) của tập mục thường xuyên. Đó là tập con khác rỗng của một tập mục thường xuyên phải là tập thường xuyên. Điều này có nghĩa các (k+1)-tập mục thường xuyên chỉ có thể sinh ra từ các k-tập mục thường xuyên. Tính chất Apriori cho phép loại bỏ được phần lớn các tổ hợp mục không thường xuyên ra khỏi không gian tìm kiếm tại mỗi bước. Đáng tiếc là ràng buộc lợi ích cao không thỏa mãn tính chất Apriori. Do đó, việc tìm kiếm, phát hiện tập mục lợi ích cao không thể thực hiện được như trong khai phá tập mục thường xuyên. Cần phải nghiên cứu tìm ra những thuật toán hiệu quả cho việc phát hiện tập mục lợi ích cao. Trong những năm gần đây, vấn đề này đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trong và ngoài nước. Đã có một số thuật toán phát hiện tập mục lợi ích cao được đề xuất. Các thuật toán này có thể phân thành hai loại: - Thuật toán kiểu Apriori (Apriori-like) sinh ứng viên, duyệt theo chiều rộng. - Thuật toán kiểu FP-growth không sinh ứng viên, chuyển đổi cơ sở dữ liệu thành cấu trúc cây, duyệt đệ quy theo chiều sâu. Luận văn của học viên nhằm nghiên cứu vấn đề khai phá tập mục lợi ích cao trong cơ sở dữ liệu lớn. Nội dung chính của luận văn gồm ba chương. Chương 1: Trình bày khái quát về khai phá dữ liệu, bài toán khai phá tập mục thường xuyên với hai thuật toán quan trọng làm cơ sở cho việc trình bày nội dung hai chương tiếp theo. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 2: Phát biểu bài toán và trình bày ba thuật toán khai phá tập mục lợi ích cao kiểu Apriori. Đó là các thuật toán UMining , UMining-H và HUMining. Chương 3: Trình bày thuật toán kiểu FP-growth, được cho là hiệu quả nhất hiện nay, thuật toán COUI-Mine. Thái nguyên, tháng 09 năm 2011. Học viên Đỗ Thị Hải Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chƣơng 1 KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN 1.1. Khai phá dữ liệu Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ thông tin, truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin không ngừng được nâng cao. Theo đó, lượng thông tin được lưu trữ trên các thiết bị nhớ tăng nhanh mỗi ngày. Thống kê sơ bộ cho thấy, lượng thông tin trên các hệ thống thông tin cứ sau 20 tháng lại tăng lên gấp đôi [8, 11]. Với lượng dữ liệu tăng nhanh và khổng lồ như vậy, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Cần phải có những kỹ thuật mới: kỹ thuật khai phá dữ liệu (Data Mining). Khai phá dữ liệu là một lĩnh vực khoa học mới xuất hiện, nhằm tự động hóa khai thác những thông tin, tri thức hữu ích, tiềm ẩn trong các CSDL lớn cho các tổ chức, doanh nghiệp, ... từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh của tổ chức, doanh nghiệp này. Các kết quả nghiên cứu cùng với những ứng dụng thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có những ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Tuy mới ra đời khoảng 20 năm, nhưng khai phá dữ liệu là lĩnh vực khoa học phát triển vô cùng nhanh chóng. Do sự phát triển nhanh chóng cả về phạm vi áp dụng lẫn các phương pháp tìm kiếm tri thức, đã có nhiều quan điểm khác nhau về khai phá dữ liệu. Tuy nhiên, ở một mức độ trừu tượng nhất định, chúng ta định nghĩa khai phá dữ liệu như sau [9]: Khai phá dữ liệu là quá trình tìm kiếm, phát hiện các tri thức mới, hữu ích tiềm ẩn trong cơ sở dữ liệu lớn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Khám phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và KDD được các nhà khoa học xem là tương đương nhau. Thế nhưng, nếu phân chia một cách chi tiết thì khai phá dữ liệu là một bước chính trong quá trình KDD. Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành như: Tổ chức dữ liệu, xác suất, thống kê, lý thuyết thông tin, học máy, CSDL, thuật toán, trí tuệ nhân tạo, tính toán song song và hiệu năng cao, .... Các kỹ thuật chính áp dụng trong khám phá tri thức phần lớn được thừa kế từ các ngành này. Quá trình khám phá tri thức có thể phân thành các công đoạn sau [9]:  Lựa chọn dữ liệu: Là bước tuyển chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định.  Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu thiếu, dữ liệu nhiễu, dữ liệu không nhất quán, ...), tổng hợp dữ liệu, rời rạc hóa dữ liệu, Biến đổi dữ liệu. Đây được xem là bước quan trọng và tiêu tốn thời gian nhất của toàn bộ quá trình KDD. Sau bước tiền xử lý này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và rời rạc hóa.  Khai phá dữ liệu: Là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật học máy) nhằm khai thác dữ liệu, trích lọc những mẫu tin (information patterns), những mối quan hệ đặc biệt trong dữ liệu.  Đánh giá tri thức và biểu diễn: Những mẫu thông tin và mối quan hệ trong dữ liệu đã được phát hiện ở bước khai phá dữ liệu được đánh giá theo những tiêu chí nhất định và được biểu diễn ở dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, .... Hình 1.1 dưới đây mô tả các công đoạn của KDD: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Hình 1.1. Các bước thực hiện của quá trình khai phá dữ liệu Theo quan điểm của học máy (Machine Learning), thì các kỹ thuật khai phá dữ liệu bao gồm:  Học có giám sát (Supervised Learning): Là quá trình học luật phân lớp các đối tượng dựa trên một tập dữ liệu có giám sát (supervised data set), tức là tập các ví dụ (các bộ dữ liệu) huấn luyện trong đó mỗi ví dụ có chứa thông tin đã biết về các thuộc tính và nhãn lớp của một đối tượng.  Học không có giám sát (Unsupervised Learning): Là quá trình học luật phân chia một tập các đối tượng thành các cụm (clusters) tương tự nhau dựa trên một tập dữ liệu không có giám sát (unsupervised data set), tức là tập các ví dụ huấn luyện chỉ chứa thông tin về các thuộc tính mà không có thông tin về nhãn lớp của các đối tượng.  Học nửa giám sát (Semi-Supervised Learning): Là quá trình học luật phân chia một tập các đối tượng thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện chứa thông tin về các thuộc tính và nhãn lớp của một số đối tượng. Nếu căn cứ vào nhiệm vụ cần giải quyết, thì khai phá dữ liệu bao gồm các kỹ thuật sau:  Phân lớp và dự đoán (classification and prediction): Là việc xếp các đối tượng vào những lớp đã biết trước. Ví dụ, phân lớp các loài thực vật, phân lớp các bệnh nhân,.... Hướng tiếp cận này thường sử dụng một số kỹ thuật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 của học máy như cây quyết định (decision tree), mạng nơ-ron nhân tạo (neural network), ....  Phân cụm (clustering/segmentation): Là việc xếp các đối tượng theo từng cụm tự nhiên.  Luật kết hợp (association rules): Là việc phát hiện các luật biểu diễn tri thức dưới dạng đơn giản. Ví dụ: “70% nữ giới vào siêu thị mua phấn thì có tới 80% trong số họ cũng mua thêm son”.  Phân tích hồi quy (regression analysis): Là việc học một hàm ánh xạ một bộ dữ liệu thành một giá trị thực của đại lượng cần dự đoán. Bài toán phân tích hồi quy tương tự như bài toán phân lớp, điểm khác nhau là ở chỗ đại lượng cần dự đoán là liên tục chứ không phải rời rạc như nhãn lớp.  Phân tích các mẫu theo thời gian (sequential/temporal patterns): Tương tự như khai phá luật kết hợp nhưng có quan tâm đến tính thứ tự theo thời gian.  Mô tả khái niệm và tổng hợp (concept description and summari-zation): Thiên về mô tả, tổng hợp và tóm tắt các khái niệm. Ví dụ tóm tắt văn bản. Hiện nay, các kỹ thuật khai phá dữ liệu có thể làm việc với rất nhiều kiểu dữ liệu khác nhau. Một số dạng dữ liệu điển hình là: CSDL quan hệ, CSDL giao tác, CSDL quan hệ hướng đối tượng, dữ liệu không gian và thời gian, CSDL đa phương tiện, dữ liệu văn bản và web, .... Cho đến nay, khai phá dữ liệu đã và đang được ứng dụng rộng rãi trong nhiều lĩnh vực như: Phân tích dữ liệu hỗ trợ ra quyết định, Y học, Tin-sinh học (Bioinformatics), thương mại, tài chính, bảo hiểm, text mining, .... Rất nhiều tổ chức và công ty lớn trên thế giới đã và đang áp dụng thành công các kỹ thuật khai phá dữ liệu vào hoạt động sản xuất, kinh doanh của mình và thu được những lợi ích to lớn. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle đã tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá dữ liệu. Các ứng dụng này được chia thành 3 nhóm: Phát hiện gian lận (fraud detection), hỗ trợ tiếp thị và quản lý khách hàng, phát hiện và xử lý lỗi hệ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 thống mạng. Bộ Khai phá thông minh (Intelligence Miner) là sản phẩm điển hình của IBM. Mặc dù nổi lên như là một lĩnh vực khoa học tiềm năng, phát triển rất nhanh chóng, nhưng khai phá dữ liệu cũng phải đối mặt với nhiều thách thức. Các thách thức lớn thường được nhắc tới là: - Số đối tượng cũng như số chiều (thuộc tính) trong cơ sở dữ liệu khai phá thường là rất lớn; - Dữ liệu và tri thức luôn thay đổi có thể làm cho các mẫu đã phát hiện không còn phù hợp; - Dữ liệu bị thiếu hoặc nhiễu; - Quan hệ phức tạp giữa các thuộc tính; - Giao tiếp với người sử dụng và kết hợp với các tri thức đã có; - Tích hợp với các hệ thống khác; 1.2. Khai phá tập mục thƣờng xuyên Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thường xuyên xuất hiện như là bài toán con của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tương quan, phân lớp, phân cụm dữ liệu, khai phá web… Bài toán khai phá tập mục thường xuyên được giới thiệu lần đầu tiên bởi Agrawal năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị trong mô hình của bài toán khai phá luật kết hợp [3, 4]. Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các giá trị dữ liệu, các mối quan hệ đó chính là các luật kết hợp. 1.2.1. Cơ sở dữ liệu giao tác Định nghĩa 1.1: Cho tập các mục (item) I={i1, i2,..., in}. Một giao tác (transaction) T là một tập con của I, TI.. Cơ sở dữ liệu giao tác là tập các giao tác DB ={ T1, T2,..., Tm}. Mỗi giao tác được gán một định danh TID. Một tập mục con X I,, gồm k mục phân biệt được gọi là một k –tập mục. Giao tác T gọi là chứa tập mục X nếu X T. Biểu diễn cơ sở dữ liệu giao tác: cơ sở dữ liệu giao tác thường được biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có định danh TID và một danh sách các mục dữ liệu trong giao tác đó, (Bảng 1.1). Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác TID Mục dữ liệu T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 B,C,D B,C,D A, B, D C, D, F C, D A, C A, B, C, F A, C A, B, E A, E A, B, C Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, 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, (Bảng 1.2). Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác Định danh giao tác Mục dữ liệu A T3, T6, T7, T8, T9, T10, T11 S T1, T2, T3, T7, T9, T11 C T1, T2, T4, T5, T6, T7, T8, T11 D T1, T2, T3, T4, T5 E T9, T10 F T4, T7 Ma trận giao tác: Cơ sở dữ liệu giao tác DB  T1 , T ,...., Tn  trên tập các mục I  i1 , i2 ,..., in  được biểu diễn bởi ma trận nhị phân M  (m pq ) mxn ở đó: 1 khi i q  T p m pq   0 khi i q  T p Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Ví dụ, cơ sở dữ liệu bảng 1.1 biểu diễn ở dạng ma trận giao tác là: Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu bảng 1.1 TID A B C D E F T1 0 1 1 1 0 0 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 0 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1.2.2. Tập mục thƣờng xuyên và luật kết hợp Định nghĩa 1.2: Cho tập mục X  I . Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ các giao tác chứa X trên tổng số các giao tác trong DB, tức là: sup( X )  T  DB T  X  DB . Ta có: 0  sup( X )  1 với mọi tập mục X  I . Định nghĩa 1.3: Cho tập mục X  I và ngưỡng hỗ trợ tối thiểu (minimum support) minsup   0,1 (được xác định trước bởi người sử dụng). X được gọi là tập mục thường xuyên (frequent itemset) với độ hỗ trợ tối thiểu minsup nếu sup( X )  minsup , ngược lại X gọi là tập mục không thường xuyên. Định nghĩa 1.4: Một luật kết hợp là một biểu thức dạng X  Y , trong đó X và Y là tập con của I, X Y   ; X gọi là tiền đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy. Định nghĩa 1.5: Độ hỗ trợ (Support) của một luật kết hợp X  Y , ký hiệu là sup( X  Y ), là độ hỗ trợ của tập mục X  Y , sup( X  Y )  sup( X  Y ) . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Như vậy độ hỗ trợ của luật kết hợp X  Y chính là xác suất P( X  Y ) của sự xuất hiện đồng thời của X và Y trong một giao tác. Ta có: 0  sup( X  Y )  1 . Định nghĩa 1.6: Độ tin cậy (Confidence) của một luật X  Y , ký hiệu conf  X  Y  , là tỷ lệ phần trăm giữa số giao tác chứa X  Y và số giao tác chứa X trong cơ sở dữ liệu DB. conf ( X  Y )  sup( X  Y ) sup( X ) Độ tin cậy của luật kết hợp X  Y chính là xác suất có điều kiện P(Y/X): PY / X   T  DB | X  T  Y  T  T  DB | X  Y  T  sup X  Y    T  DB | X  T  T  DB | X  T  sup X  và ta có 0  conf ( X  Y )  1. Các luật thoả mãn cả hai ngưỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf), tức thoả mãn sup( X  Y )  minsup và conf  X  Y   minconf , được gọi là luật kết hợp mạnh. Tính chất cơ bản của tập mục thƣờng xuyên: Cho cơ sở dữ liệu giao tác DB và ngưỡng độ hỗ trợ tối thiểu minsup. Các tập mục thường xuyên có các tính chất sau: (1) Nếu X, Y là các tập mục và X  Y thì sup  X   sup Y  . (2) Nếu một tập mục là không thường xuyên thì mọi tập cha của nó cũng không thường xuyên. (3) Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thường xuyên Tính chất (3) được gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thường xuyên. 1.2.3 Bài toán khai phá luật kết hợp Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu minsup và ngưỡng độ tin cậy tối thiểu minconf. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn