Tài liệu Nghiên cứu một số thuật toán khai phá tập mục thường xuyên và tập mục cổ phần cao trong cơ sở dữ liệu

1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BẾ QUANG HUẤN NGHIÊN CỨU MỘT SỐ THUẬT TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ TẬP MỤC CỔ PHẦN CAO TRONG CƠ SỞ DỮ LIỆU Chuyên nghà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 Ngƣời hƣớng dẫn khoa học: GS. TS Vũ Đức Thi THÁI NGUYÊN 2012 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 LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng nội dung đề cƣơng cũng nhƣ nội dung mà cán bộ hƣớng dẫn giao cho. Nội dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm. Tác giả luận văn Bế Quang Huấ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 ii MỤC LỤC LỜI CAM DOAN ................................................................................................. i DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ................................ iv DANH MỤC CÁC BẢNG BIỂU ........................................................................ v DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................ vi MỞ ĐẦU ............................................................................................................. 1 Chƣơng 1 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG .............................................................................................................................. 5 1.1 MỞ ĐẦU .................................................................................................. 5 1.2 CÁC KHÁI NIỆM CƠ BẢN ................................................................... 6 1.2.1 Cơ sở dữ liệu giao tác........................................................................ 7 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......................................................... 12 1.3 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN .......................................... 14 1.3.1 Các cách tiếp cận khai phá tập mục thƣờng xuyên ......................... 14 1.3.2 Thuật toán Apriori ........................................................................... 16 1.3.3 Thuật toán FP-growth ..................................................................... 22 1.4 MỞ RỘNG BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN .. 31 1.5 KẾT LUẬN CHƢƠNG 1 ....................................................................... 33 Chƣơng 2 KHAI PHÁ TẬP MỤC CỔ PHẦN CAO ......................................... 34 2.1 GIỚI THIỆU ........................................................................................... 34 2.2 BÀI TOÁN KHAI PHÁ TẬP MỤC CỔ PHẦN CAO ........................... 35 2.3 THUẬT TOÁN FSM .............................................................................. 41 2.3.1 Cở sở lý thuyết của thuật toán FSM................................................ 41 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 2.3.2 Thuật toán FSM............................................................................... 42 2.3.3 Nhận xét thuật toán FSM ................................................................ 44 2.4 THUẬT TOÁN AFSM ........................................................................... 45 2.4.1 Cơ sở lý thuyết của thuật toán AFSM............................................. 45 2.4.2 Thuật toán AFSM............................................................................ 52 2.4.3 Đánh giá thuật toán AFSM ............................................................. 59 2.5 KẾT LUẬN CHƢƠNG 2 ....................................................................... 60 Chƣơng 3 THỰC NGHIỆM VÀ ĐÁNH GIÁ THUẬT TOÁN ........................ 61 3.1 ĐẶT BÀI TOÁN..................................................................................... 61 3.2 THIẾT KẾ MODUL CHƢƠNG TRÌNH VÀ GIẢI THUẬT................. 62 3.3 GIAO DIỆN SỬ DỤNG VÀ CHỨC NĂNG CHƢƠNG TRÌNH .......... 67 3.4 ĐÁNH GIÁ KẾT QUẢ VÀ HƢỚNG PHÁT TRIỂN CỦA CHƢƠNG TRÌNH ................................................................................................................ 70 KẾT LUẬN ........................................................................................................ 72 TÀI LIỆU THAM KHẢO .................................................................................. 73 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 KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải I={i1,i2,…,in} Tập n mục dữ liệu DB ={T1,T2,…,Tm} Cơ sở dữ liệu có m giao tác db Cơ sở dữ liệu giao tác con của DB, db  DB ip Mục dữ liệu thứ p Tq Giao tác thứ q n Số mục dữ liệu một cơ sở dữ liệu giao tác m Số giao tác của một cơ sở dữ liệu giao tác A, B, C,… Tên các mục dữ liệu trong cơ sở dữ liệu giao tác X, Y,… Tập con của tập mục dữ liệu I, X, Y  I X=ABC Thay cho X={A,B,C} trong các cơ sở dữ liệu giao tác minsup Ngƣỡng độ hỗ trợ minShare Ngƣỡng cổ phần tối thiểu minconf Ngƣỡng độ tin cậy tối thiểu X Số phần tử của tập hợp X CSDL Cở sở dữ liệu CNTT Công nghệ thông tin 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 BẢNG BIỂU Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác ...............................................8 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 họa thực hiện thuật toán Apriori ............... 20 Bảng 1.5: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán COFI-tree .......... 25 Bảng 1.6: Các mục dữ liệu và độ hỗ trợ ................................................................. 26 Bảng 1.7: Các mục dữ liệu thƣờng xuyên đã sắp thứ tự ......................................... 26 Bảng 1.8: Các mục dữ liệu trong giao tác sắp giảm dần theo độ hỗ trợ ................. 27 Bảng 2.1: Cơ sở dữ liệu ví dụ ................................................................................. 36 Bảng 2.2: Giá trị lmv và cổ phần các mục dữ liệu trong CSDL bảng 2.1............... 38 Bảng 2.3: Các tập mục cổ phần cao của CSDL bảng 2.1 ....................................... 38 Bảng 2.4: CSDL minh họa ngữ nghĩa của tập mục cổ phần cao ............................ 40 Bảng 2.5a: CSDL minh họa có trƣờng hợp hai hàm tới hạn bằng nhau ................. 51 Bảng 2.5b: CSDL minh học có trƣờng hợp hai hàm tới hạn luôn băng nhau ........ 51 Bảng 2.6: Giá trị hai hàm tới hạn khi k=1 .............................................................. 52 Bảng 2.7: Các giá trị lmv và hàm tới hạn với k=1 .................................................. 56 Bảng 2.8: Các giá trị lmv và hàm tới hạn với k=2 .................................................. 57 Bảng 2.9: Các giá trị lmv và hàm tới hạn với k=3 .................................................. 57 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 vi DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên ...................... 15 Hình 1.2: Cây FP-tree của CSDL bảng 1.5 ............................................................. 28 Hình 1.3: Cây COFI-tree của mục D ...................................................................... 28 Hình 1.4: Các bƣớc khai phá cây D-COFI-tree ...................................................... 31 Hình 2.1: Không gian tìm kiếm tập mục cổ phần cao theo thuật toán AFSM........ 58 Hình 3.1: Giao diện chính của chƣơng trình demo ................................................. 63 Hình 3.2: Giao diện hiển thị bảng dữ liệu ............................................................... 64 Hình 3.3: Giao diện cập nhật ngƣỡng cổ phần và ngƣỡng tin cậy cho bảng dữ liệu ........................................................................................................................... 65 Hình 3.4: Giao diện hiển thị kết quả tìm tập mục cổ phần cao ............................... 66 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 MỞ ĐẦU Một trong những ứng dụng quan trọng nhất của công nghệ thông tin trong đời sống là giúp giải quyết các bài toán quản lý. Kể từ khi máy tính điện tử trở thành một công cụ lao động quan trọng thì một trong những nhu cầu đầu tiên là lƣu trữ, tìm kiếm và xử lý số liệu thống kê. Đến nay, các cơ sở dữ liệu đã trở nên khổng lồ và ngƣời ta mong muốn kho dữ liệu đó cần đƣợc khai thác hiệu quả hơn trên nhiều bình diện. Trong những năm gần đây, khai phá dữ liệu (Data mining) đã trở thành một trong những hƣớng nghiên cứu lớn nhất của lĩnh vực khoa học máy tính và công nghệ thông tin. Khai phá dữ liệu đang đƣợc áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Khai phá dữ liệu và khám phá tri thức (Data Mining and Knowledge Discovery) đây là lĩnh vực đã thu hút đông đảo các nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu. Khai phá tập mục thƣờng xuyên là bài toán có 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 đƣợc biết đến ban đầu là bài toán con của bài toán khai phá luật kết hợp đƣợc giới thiệu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị, phân tích sở thích mua của khách hàng bằng cách tìm ra những mặt hàng khác nhau đƣợc khách hàng mua cùng trong một lần mua. Những thông tin nhƣ vậy sẽ giúp ngƣời quản lý kinh doanh tiếp thị trọn lọc và thu xếp không gian bày hàng hợp lý hơn, giúp cho kinh doanh hiệu quả hơn. Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực tế nhƣng có những hạn chế, không đáp ứng đầy đủ yêu cầu của ngƣời sử dụng. 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 Để đáp ứng nhu yêu cầu của thực tiễn, một số hƣớng mở rộng bài toán đã đƣợc quan tâm nghiên cứu. Một hƣớng mở rộng bài toán có rât nhiều ứng dụng là quan tâm đến cấu trúc dữ liệu và mức độ quan trọng khác nhau của các mục dữ liệu, các thuộc tính trong cơ sở dữ liệu. Theo hƣớng này, từ bài toán khai phá tập mục thƣờng xuyên ban đầu, nhiều nhà nghiên cứu đề xuất các mô hình mở rộng: Khai phá tập mục cổ phần cao, đánh giá sự đóng góp của tập mục dữ liệu trong tổng số các mục dữ liệu của cơ sở dữ liệu. Trên thế giới, các kết quả nghiên cứu về khai phá tập mục cổ phần cao đã đƣợc công bố nhiều từ các nhóm nghiên cứu tại một số trƣờng đại học ở Mỹ, Canada, Úc, Đài Loan, Singapo, Hồng Kông,… Tại Việt Nam, Khai phá luật kết hợp đã đƣợc các nhóm nghiên cứu tại Viện Công nghệ Thông tin thuộc Viện Khoa học và Công nghệ Việt Nam, các nhóm nghiên cứu tại một số trƣờng đại học nhƣ Đại học Quốc gia Hà Nội, Đại học Bách Khoa Hà Nội, Đại học Quốc gia thành phố Hồ Chí Minh thực hiện và đã có nhiều kết quả đƣợc công bố. Với mục đích đóng góp vào lĩnh vực nghiên cứu này, tôi đã chọn đề tài luận văn: “ Nghiên cứu một số thuật toán khai phá tập mục thường xuyên và tập mục cổ phần cao trong cơ sở dữ liệu” làm chủ đề nghiên cứu của mình. Mục đích của luận văn là phát triển một số thuật toán khai phá tập mục cổ phần cao trong cơ sở dữ liệu giao tác cỡ lớn. Trên cơ sở đó áp dụng vào một bài toán cụ thể là cài đặt trƣơng trình Với mục tiêu đó, luận văn đƣợc trình bày trong ba chƣơng: 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 1: Khai phá tập mục thƣờng xuyên và một số mở rộng Trình bày bài toán khai phá tập mục thƣờng xuyên: Các khái niệm cơ bản và các mô hình khai phá. Sau khi trình bày khái quát các thuật toán khai phá, trong trƣơng trình bày chi tiết hai thuật toán tiêu biểu cho hai cách tiếp cận khác nhau là thuật toán Apriori và thuật toán FP-growth. Thuật toán Apriori tiêu biểu cho phƣơng pháp sinh ra các tập mục ứng viên rồi duyệt cơ sở dữ liệu để tính độ hỗ trợ của nó. Thuật toán FP-growth là thuật toán đầu tiên giới thiệu cấu trúc cây FP-tree nén toàn bộ các giao tác của cơ sở dữ liệu lên cây với 2 lần duyệt, sau đó khai phá theo phƣơng pháp phát triển dần các mẫu ở trên cây mà không cần duyệt cơ sở dữ liệu nữa. Bên cạnh đó luận văn đã trình bày chi tiết phƣơng pháp COFI-tree khai phá cây FP-tree thay cho phƣơng pháp FP-growth. Chương 2: Khai phá tập mục cổ phần cao Trình bày mô hình khai phá cổ phần cao, giới thiệu thuật toán FSM là thuật toán nhanh khai phá tất cả các tập mục cổ phần cao trong cơ sở dữ liệu giao tác. Luận văn đề xuất khái niệm “tập mục cổ phần theo giao tác cao” và chứng minh nó có tính chất phản đơn điệu (Anti Monotone), có thể ứng dụng vào nhiều thuật toán khai phá tập mục thƣờng xuyên đã có để tìm đƣợc tập mục cổ phần theo giao tác cao, từ đó tìm ra tập mục cổ phần cao. Sử dụng ý tƣởng này, luận văn đề xuất thuật toán AFSM (Advanced FSM) dựa trên các bƣớc của thuật toán FSM với phƣơng pháp mới tỉa hiệu quả hơn các tập mục ứng viên. Chương 3: Thực nghiệm và đánh giá thuật toán Để có đƣợc kết quả này tôi đã nhận đƣợc sự quan tâm, động viên, giúp đỡ rất nhiều của các Thầy giáo, Cô giáo trong Khoa Công nghệ thông tin - Đại họ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 4 Thái Nguyên cũng nhƣ của bạn bè, đồng nghiệp, đặc biệt là sự chỉ bảo tận tình của GS. TS Vũ Đức Thi và sự nỗ lực của bản thân, đến nay tôi đã hoàn thành đề tài. Tuy nhiên trong quá trình làm việc, mặc dù đã cố gắng, nỗ lực hết sức nhƣng không thể tránh khỏi thiếu sót, em kính mong nhận đƣợc sự chỉ bảo của các thầy cô để đề tài đƣợc hoàn thiện hơn. Tôi xin chân thành cảm ơn ! Thái Nguyên, tháng 09 năm 2012 Học viên Bế Quang Huấ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 Chƣơng 1 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG 1.1 MỞ ĐẦU 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 bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng siêu thị trong mô hình của bài toán khai phá luật kết hợp. 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 trong cơ sở dữ liệu, các mối quan hệ đó chính là các luật kết hợp. Khai phá luật kết hợp có hai bƣớc: Bƣớc thứ nhất, tìm các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ tối thiểu minsup cho trƣớc, bƣớc thứ hai, từ các tập mục thƣờng xuyên tìm đƣợc, sinh ra các luật kết hợp thỏa mãn ngƣỡng độ tin cậy minconf cho trƣớc. Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bƣớc thứ nhất, đó là khai phá tất cả các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ cho trƣớc. Kể từ khi Agrawal đề xuất, khai phá tập mục thƣờng xuyên đã thu hút đƣợc sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu đƣợc công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có. Tâp mục thƣờng xuyên đã có vai trò quan trọng trong nhiều ứng dụng thực tế nhƣ quản lý quan hệ khách hàng, nâng cao hiệ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 6 quả của thƣơng mại điên tử, trong lĩnh vực tin sinh học, phân tích cấu trúc Protein va AND, mở rộng truy vấn, phát hiện xâm nhập mạng,… Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực tế nhƣng có những hạn chế, không đáp ứng đầy đủ yêu cầu của ngƣời sử dụng. Ràng buộc về độ hỗ trợ và độ tin cậy của luật kết hợp chỉ mang ngữ nghĩa thống kê, không phản ánh đƣợc vai trò khác nhau của các thuộc tính cũng nhƣ đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu. Để đáp ứng nhu cầu thực tiễn, khai phá tập mục thƣờng xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phƣơng pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có rất nhiều hƣớng mở rộng bài toán đƣợc quan tâm nghiên cứu. Chƣơng một này sẽ trình bày các vấn đề cơ bản của bài toán khai phá tập mục thƣờng xuyên và một số mở rộng của bài toán. 1.2 CÁC KHÁI NIỆM CƠ BẢN Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Mục tiêu khai phá là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn gọi là mô hình cơ bản) đƣợc R. Agrawal, T. Imielinski và A. Swami đề xuất vào năm 1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán đƣợc tại các siêu thị. Việc xác định các quan hệ này không phân biệt vai 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 trò khác nhau cũng nhƣ không dựa vào các đặc tính dữ liệu vốn có của các thuộc tính mà chỉ dựa vào sự xuất hiện cùng lúc của chúng. Phần tiếp sau đây nêu một số khái niệm cơ bản và phát biểu bài toán khai phá luật kết hợp, bài toán đầu tiên dẫn đến bài toán khai phá tập mục thƣờng xuyên. 1.2.1 Cơ sở dữ liệu giao tác Định nghĩa 1.1: igdfg 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à một 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 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. 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ó một định danh TID và một danh sách các mục dữ liệu trong 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 8 Ví dụ 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 B, C, D T2 B, C, D T3 A, B, D T4 C, D, F T5 C, D T6 A, C T7 A, B, C, F T8 A, C T9 A, B, E T10 A, E T11 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. 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 Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác. Mục dữ liệu Định danh giao tác A T3, T6, T7, T8, T9, T10, T11 B 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,T2,…,Tm} trên các tập mục (item) I = {i1,i2,…,in} đƣợc biểu diễn bởi ma trận nhị phân M = (mpq)mxn, ở đó: 1 khi iq  Tp mpq = 0 khi iq  Tp 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ụ 1.2: Cơ sở bản dữ liệu 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 0 1 1 1 0 0 T3 1 1 0 1 0 0 T4 0 0 1 1 0 1 T5 0 0 1 1 0 0 T6 1 0 1 0 0 0 T7 1 1 1 0 0 1 T8 1 0 1 0 0 0 T9 1 1 0 0 1 0 T10 1 0 0 0 1 0 T11 1 1 1 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ệ phần trăm 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. 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 nghĩa 1.3: Cho tập mục X  I và ngƣỡng hỗ trợ tối thiểu (minimum support) minisup 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 hoặc large itemset) với độ hỗ trợ tối thiểu minisup nếu sup(X)  minisup, 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à biểu thức dạng X  Y, trong đó X và Y là các 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). 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): 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 12 P(Y/X) = T  DB X  T  Y  T  T  DB X  T  = T  DB X  Y  T  T  DB X  T  = sup( X  Y ) sup( X ) Và ta có 0  conf(X  Y)  1. Các luật thỏa mãn cả hai ngƣỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf), tức thỏa 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 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 13 Yêu cầu: Tìm tất cả các luật kết hợp X  Y trên cơ sở dữ liệu DB sao cho sup(X  Y)  minsup và conf(X  Y)  minconf. Bài toán khai phá luật kết hợp này đƣợc gọi là bài toán cơ bản hay bài toán nhị phân, vì ở đây, giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện hay không xuất hiện). Bài toán khai phá luật kết hợp đƣợc chia thành hai bài toán con. Bài toán thứ nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trƣớc, tức là tìm tất cả các tập mục thƣờng xuyên. Bài toán thứ hai là sinh ra các luật kết hợp từ các tập mục thƣờng xuyên đã tìm đƣợc thỏa mãn độ tin cậy tối thiểu cho trƣớc. Bài toán thứ hai đƣợc giải quyết nhƣ sau: Giả sử đã tìm đƣợc X là tập mục thƣờng xuyên, ta sinh ra các luật kết hợp bằng cách tìm  Y  X, kiểm tra độ tin cậy của luật X\YY có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thƣờng xuyên. Phần tiếp theo sau đây sẽ trình bày chi tiết về khai phá tập mục thƣờng xuyê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