Tài liệu Phát hiện luật kết hợp mờ có hỗ trợ không giống nhau

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ HOÀNG VIỆT NGUYÊN Phát hiện luật kết hợp mờ có hỗ trợ không giống nhau LUẬN VĂN THẠC SĨ Người hướng dẫn: TS. Đỗ Văn Thành Hà nội - 2003 f n* r Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 1 MỤC LỤC LỜI GIỚI THIỆU CHƯƠNG I C ơ SỞ LÝ THUYẾT CỦA CÁC THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP CHARM VÀ ACLOSE..................................................................................10 I. Giới thiệu luật kết hợp.................................................................................................. 10 Lì. Ỷ nghĩa thực tiễn của luật kết hợp....................................................................10 1.2. Mô hình hình thức luật kết hợp........................................................................ 11 1.3. Phân loại thuật toán phát hiện luật kết hợp hiện c ó ...................................... 13 II. Cơ sở lý thuyết thuật toán CHARM và ACLOSE....................................................15 II. 1. Các kiến thức chuẩn b ị ....................................................................................15 II. 2. Phương pháp xây dựng thuật toán CHARM và ACLOSE......................... 19 III. Thuật toán CHARM và ACLOSE..........................................................................20 III. 1. Thuật toán CHARM........................................................................................20 III. 2. Thuật toán AC LO SE......................................................................................25 IV. So sánh thuật toán CHARM VÀ AC LOSE............................................................ 32 CHƯƠNG II MỘT SỐ CÁCH TIẾP CẬN PHÁI HIỆN LUẬT KẾT HỢP M ỚI..37 I. Phát hiện luật kết hợp có ràng buộc độ hỗ trợ............................................................ 38 1.1. Vấn đề đặt r a ..................................................................................................... 38 1.2. Các kiến thức chuẩn bị......................................................................................39 1.3. Thuật toán phát hiện luật kết hợp ràng buộc độ hỗ trợ ................................ 40 II. Phát hiện luật kết hợp gắn trọng số ............................................................................ 41 II. 1. Vấn đề đặt ra.....................................................................................................41 11.2. Các kiến thức chuẩn b ị....................................................................................41 II. 3. Thuật toán phát hiện luật kết hợp với mụcdữ liệu gắn trọng số ..................45 III. Phát hiện luật kết hợp có độ hỗ trợ không giống nhau........................................... 49 III. 1. Vấn đề đặt r a .................................................................................................. 49 111.2. Các kiền thức cần thiết...................................................................................49 Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQ(Ỉ Hà Nội __ ĐẠí học q u ò c gia hà. NÔI 'Ị TRÙNGTÃM THỜNGTỊN.THƯVIỆN I f f Phát hiện luật kêt hợp mờ có độ hô trợ không giỏng nhau Trang 2 III. 3. Thuật toán tìm tập phổ biến cực đại có độ hỗ trợ không giống nhau.... 51 CHƯƠNG III PHÁT HIỆN LUẬT KẾT HỢP MỜ VỚI MỤC DỮ LIỆU CÓ Đ ộ HỒ TRỢ KHÔNG GIỐNG NHAU............................................................................... 60 I. Tại sao cần phải phát hiện luật kết hợp m ờ............................................................... 60 II. Luật kết họp m ờ ...........................................................................................................62 II.ỉ. Luật kết hợp m ờ ...............................................................................................62 II.2. Một số thuật toán phát hiện luật kết hợp mờ hiện c ỏ .................................. 63 III. Các kiến thức cần thiết xây dựng thuật toán tìm tập phổ biến mờ cực đại có độ hỗ trợ không giống nhau..................................................................................................66 IV. Thuật toán phát hiện tập phổ biến mờ có độ hỗ trợ không giống nhau...............72 IV. 1. Tư tưởng xây dựng thuật toán.....................................................................72 IV.2. Thuật toán FUZZY CHARM-NEW.............................................................. 74 IV.3. Ví dụ minh hoạ thuật toán FUZZY CHARM-NEW..................................... 75 IV.4. Nhận xét - Đánh g iả ....................................................................................... 79 KÉT LUẬN TÀI LIỆU THAM KHẢO Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r ** r Phát hiện luật kêt hợp mờ cỏ độ hô trợ không giông nhau Trang 3 DANH MỤC HÌNH VẺ Hĩnh 1. Hệ thống một số thuật toán phát hiện luật kết hợp hiện có ....................... 14 Hình 2. Cây tìm kiếm minh hoạ thuật toán CHARM ...............................................24 Hình 3. So sảnh các thuật toán -Cây tìm kiếm thuật toán Apriori ..................35 Hình 4. So sảnh các thuật toán - Cây tìm kiếm thuật toán CHARM ........... 35 Hình 5. So sảnh các thuật toán - Cây tìm kiếm thuật toán ACLOSE............... 36 Hình 6. Cây tìm kiếm thuật toán CHARM-NEW.........................................................56 Hình 7.Rời rạc hoá mục dữ liệu Tuổi(Age) trong miền giá trị [10..40] thành 3 khoảng[10..20], [20..30], [30..40]............................................................................. 62 Hình s. Gắn ihuộc tính Tuổi(Age) trong miền giả trị [10..40] với tập mờ Tuỏi trẻ, Tuổi thanh niên, Tuổi trung niên. Các giá trị thuộc tính trong miền [20..30] thuộc về tập mờ Tuổi thanh niên.......................................................................................... 62 Hình 9. Cây tìm kiếm mô tả thuật toán FUZZY CHARM-NEW...............................77 Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r ~ r Phát hiện luật kêt hợp mờ cỏ độ hô trợ không giông nhau Trang 4 DANH MỤC BẢNG BIẺU • Bảng 1. Cơ sở dữ liệu tác v ụ ...........................................................................................12 Bảng 2. Độ ho trợ của các tập mục dừ liệu .................................................................. 12 Bảng 3. Luật kết hợp........................................................................................................13 Bảng 4. CSDL minh họa thuật toán CHARM.............................................................. 23 Bảng 5. Bảng ký kiệu thuật toán ACLOSE ...................................................................26 Bảng 6. CSDL ví dụ thuật toán ACLOSE .....................................................................30 Bảng 7. Ket quả thuật toán ACLOSE ........................................................................... 32 Bảng 8. Ví dụ minh hoạ ràng buộc độ ho trợ ...............................................................40 Bảng 9. CSDL minh huạ các mục dữ liệu gắn trọng sổ ............................................ 47 Bảng 10. Các biên K- hỗ trợ cho tập Y gắn trọng sổ .................................................48 Bảng 11. CSDL minh hoạ thuật toán CHARM-NEW.................................................. 55 Bảng 12. Rời rạc hoá dữ liệu trong trường hợp các thuộc tính định lượng rời rạ c .............................................................................................................................. 60 Bảng 13. Rời rạc hoá dữ liệu trong trường hợp các thuộc tính định lượng liên tụ c.............................................................................................................................. 61 Bảng 14. Cơ sở dữ liệu định lượng ban đần ................................................................. 68 Bảng 15. Cơ sở dữ liệu m ờ ............................................................................................69 Bảng 16. CSDL định lượng minh họa thuật toán FUZZY CHARM-NEW..................75 Bảng 17. Ngữ cảnh dữ liệu mờ của CSDL minh họa ................................................. 76 Bảng 18. Một ngữ cảnh phát hiện dữ liệu mờ của ví dụ minh hoạ ........................... 76 Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội Phát hiện luật kết hợp mờ có độ hỗ trợ không giống nhau Trang 5 KÝ HIỆU VÀ TỪ VIÉT TẤT Từ hoặc cụm từ Từ viêt tăt Từ tiêng Anh Cơ sở dữ liệu CSDL Database Định danh TID Transaction ID Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r ~ r Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 6 LỜI GIỚI THIỆU Vấn đề phát hiện luật kết họp từ các cơ sở dữ liệu tác vụ (CSDL có thuộc tính nhận giá trị nhị phân) được nhóm Data Quest thuộc Trung tâm nghiên cứu Amaden của tập đoàn IBM kết hợp cùng một số nhà khoa học của Trường Đại học Tổng hợp Hensinki đề xuất lần đầu vào năm 1993 [5]. Từ đó đến nay nó được đặc biệt quan tâm phát triển , hiện đã trở thành một trong những khuynh hướng nghiên cứu và ứng dụng quan trọng của khai phá dữ liệu (data mining). Việc phát hiện luật kết hợp không chỉ được ứng dụng trong thương mại mà hiện còn được ứng dụng trong rất nhiều ngành kinh tế, khoa học, xã hội khác như Tài chính, Ngân hàng, Y tế, Giáo dục, nghiên cứu môi trường,.. . [1-3,5-7,9,13]. Vấn đề phát hiện luật kết hợp được phân thành 2 vấn đề con đó là: (a) Tìm các tập phổ biến (đó là tập các mục dữ liệu có độ hỗ trợ không nhỏ hơn giá trị chung minsup nào đó) và (b) sinh ra luật kết hợp có độ tin cậy không nhỏ hơn một giá trị minconf nào đó từ các tập phổ biến vừa tìm được. Sự phức tạp và khó khăn của vấn đề phát hiện luật kết hợp chủ yếu tập trung ở vần đề tìm tập phổ biến (a). Việc cải tiến hoặc tìm kiếm các thuật toán hiệu quả hơn để tìm các tập phổ biến từ các CSDL nói chung là lớn, thậm chí rất lớn là hướng nghiên cứu được ưu tiên nhất trong vấn đề phát hiện luật kết hợp thời gian qua. Hiện tại đã có khá nhiều thuật toán phát hiện luật kết hợp theo nhiều cách tiếp cận khác nhau và các thuật toán này đều dựa trên việc tìm các tập phổ biến với độ hỗ trợ chung như nhau. Quan điểm sử dụng độ hỗ trợ chung để tìm các tập phổ biến đã cho thấy là chưa thật hợp lý với thực tế cuộc sống và người ta đã khắc phục vấn đề này bằng cách xây dựng thuật toán phát hiện luật kết hợp trong điều kiện có ràng buộc độ hỗ trợ [11] hoặc Phát hiện luật kết hợp khi tập dữ liệu (itemsets) được gắn với trọng số [8] hoặc các luật kết hợp được phát hiện thông qua việc tìm các tập phổ biển với các mục dữ liệu có độ hỗ trợ cực tiểu không giống nhau [2]. Thực tế việc phát hiện các luật kết hợp thực Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r /V f Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 7 sự trở lên có ý nghĩa ứng dụng to lớn khi người ta giải quyết được vấn đề phát hiện luật kết hợp từ các cơ sở dữ liệu định lượng (CSDL mà các thuộc tính nhận giá trị số hoặc phân loại). Phương pháp giải quyết ở đây là chuyển cơ sở dữ liệu định lượng thành cơ sở dữ liệu tác vụ (hay CSDL nhị phân), rồi sau đó áp dụng các thuật toán phát hiện luật kết họp từ CSDL tác vụ đã biết. Việc chuyển CSDL định lượng thành CSDL tác vụ có nhược điểm quan trọng là cồng kềnh và thiếu “tự nhiên” tại các điểm “gãy” như đã được chỉ rõ trong [8], Khắc phục tình trạng này người ta đề xuất ứng dụng lý thuyết tập mờ trong quá trình chuyển đổi CSDL định lượng thành CSDL mới thay thế vai trò của CSDL nhị phân (có thể gọi là CSDL mờ), và từ đó vấn đề phát hiện luật kết hợp mờ được ra đời. Dây ỉà vấn đề được quan tâm nghiên cứu mạnh trong vài năm gần đây. Các nghiên cứu trong [2,8] đã làm nẩy sinh vấn đề nghiên cứu và xây dựng kỹ thuật phát hiện luật kết hợp mờ với các mục dữ liệu có độ hỗ trợ cực tiểu không giổng nhau từ các CSDL có định lượng. Đề tài luận văn cao học “Phát hiện luật kết hợp mờ có độ hỗ trợ không giống nhau” được thực hiện theo hướng góp phần giải đáp vấn đề đó. Cụ thể mục đích của bản luận văn này là hệ thống những vấn đề liên quan theo hướng chuẩn bị một số kiến thức cơ bản cần thiết nhằm giải quyết vấn đề đặt ra và trình bầv một số kết quả nghiên cứu ban đầu về giải pháp kỹ thuật giải quyết vấn đề đó. Luận văn có 83 trang bao gồm phần mở đầu, 3 chương nội dung, phần kết luận và tài liệu tham khảo. Chương 1: Cơ sở lý thuyết của các thuật toán khai phá luật kết hợp CHARM và ACLOSE gồm các trang từ 10 đến trang 38. Sau khi trình bày tổng quát một số khái niệm, nội dung cơ bản nhất về vấn đề phát hiện luật kết hợp, các thuật toán phát hiện luật kết hợp, chương này sẽ tập trung trình bầy cơ sở lý thuyết của 2 thuật toán phát hiện luật kết họp mới và hiệu quả nhất hiện nay CHARM và ACLOSE cũng như giới thiệu chi tiết về 2 thuật toán đó. Thực sự 2 thuật toán này đã được xây dựng Hoàng Việt Nguyên - Luận văn ThạcSĩ Khoa Công nghệ ĐHQG Hà Nội - Phát hiện luật kết hợp mờ có độ hỗ trợ không giống nhau Trang 8 theo cách tiếp cận rất khác với các cách tiếp cận của các thuật toán được xây dựng trước đó và việc đánh giá so sánh hai thuật toán này với nhau cũng góp phần làm rõ thêm cách tiếp cận xây dựng của chúng. Chương 2: Một số cách tiếp cận phát hiện luật kết hợp mới từ trang 39 đến trang 61 sẽ tập trung trình bầy một số hạn chế của các luật kết họp được phát hiện trong điều kiện chúng có độ hỗ trợ cực tiểu chung như nhau (cho đến thời điểm này việc ứng dụng các luật kết họp chủ yếu được thực hiện trong điều kiện như vậy) và một số cách tiếp cận nghiên cứu nhằm khắc phục những hạn chế đó. Chương này trình bầy 3 cách tiếp cận chính hiện nay là phát hiện luật kết hợp khi các tập dữ liệu (itemsets) có ràng buộc độ hỗ trợ; phát hiện luật kết họp có các mục dữ liệu được gắn trọng số và phát hiện luật kết họfp khi các mục đừ liệu có độ hỗ trợ cực tiểu không giống nhau. Một số so sánh đánh giá ban đầu về 3 cách tiếp cận đó cũng được giới thiệu trong chương 2. Chương 3: Phát hiện luật kết hợp mờ có độ hỗ trợ cực tiếu không giống nhau gồm các trang từ trang 62 đến trang 82. Sau khi trình bầy một số lý do vì sao cần phát hiện luật kết hợp mờ, một số khái niệm cơ bản của phát hiện luật kết hợp mờ, chương 3 sẽ tập trung trình bầy một số kiến thức chuẩn bị và thuật toán FUZZY CHARM-NEW để tìm các tập phổ biến mờ với các tập thuộc tính có độ hỗ trợ cực tiểu không giống nhau. Trong Phần kết luận sẽ trình bầy tóm tắt những nội dung chính của luận văn, một số hạn chế chủ yếu và hướng nghiên cứu tiếp theo của bản luận văn này. Cuối cùng tác giả xin cảm ơn sự giúp đỡ và hướng dẫn tận tình của Ts. Đỗ Văn Thành - Văn Phòng Chính Phủ trong quá trình thực hiện luận văn. Tác giả xin chân thành cám ơn các thầy cô khoa Công nghệ- Đại học Quốc gia Hà Nội đã tạo điều Hoàng Việt Nguyên Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội - f ~ r Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 9 kiện và giúp đỡ trong quá trình học tập và làm luận văn và Xê mi na: “ Khai phá tri thức trong các cơ sở dữ liệu” của Khoa đã tạo điều kiện cho tác giả được trình bầy và đã góp ý kiến để tác giả chỉnh sửa, hoàn thiện bản luận văn này. Xin cám ơn sự giúp đỡ của bạn bè đồng nghiệp và các bạn lớp 7KT - Khoa Công Nghệ trong suốt quá trình học tập và làm khoá luận. Hà Nội, ngày 01 tháng 06 năm 2003 Học viên Hoàng Việt Nguyên Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r r ~ Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 10 CHƯƠNG I CO SỞ LÝ THUYÉT CỦA CÁC THUẬT TOÁN KHAI PHÁ LUẬT KÉT HỢP CHARM VÀ ACLOSE I. Giới thiệu luật kết hợp 1.1. Ỷ nghĩa thực tiễn của luật kết hợp Phát hiện luật kết hợp được đề xuất lần đầu bởi R. Agrawal vào năm 1993 [5], được quan tâm phát triển mạnh trong những năm qua và hiện đã trở thành một trong những khuynh hướng nghiên cứu ứng dụng quan trong của Khai phá dữ liệu (Data Mining) [5,6,7,9,13,14]. Xuất phát từ “rổ “ dữ liệu (data basket) về tình hình bán hàng cùa siêu thị, người ta mong muốn phát hiện được những tri thức tiềm ẩn có giá trị nhằm hỗ trợ cửa hàng trong việc hoạch định chiến lược kinh doanh như tiếp thị quảng cáo (nên thiết kế mẫu quảng cáo thế nào?), cơ cấu các mặt hàng cần được bán, bố trí hợp lý các gian hàng trong siêu thị (bố trí sắp xếp hàng hoá ra sao? cần bổ sung thêm những hàng hoá gì, số lượng bao nhiêu?),..., vấn đề phát hiện luật kết hợp đã ra đời [5,6 ]. về bản chất luật kết hợp biểu thị mối quan hệ giữa tập con các mặt hàng (gọi là tập mục dữ liệu ) trong cơ sở dữ liệu siêu thị. Như vậy, để phát hiện được các luật kết họp cần phải tìm tất cả các tập con của các mặt hàng được thường xuyên xuất hiện trong cơ sở dữ liệu (được gọi là tập phổ biến) và rút ra các luật cho biết tập con của các mặt hàng này đã ảnh hưởng thế nào đến sự xuất hiện của tập con các mặt hàng khác. Các phát biểu như: “90% những người mua bánh mì và bơ cũng mua sữa và cà phê”, là một dạng của luật kết hợp. Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội F f Trang 11 Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau 1.2. Mô hình hình thức luật kết hợp Giả sử I C 3 = { i|, i2, im} là tập của các thuộc tính nhị phân. X c tập dữ liệu (tên mỗi loại hàng được xem là một mục dữ liệu), Y) (0 < conf(r) < 1): c o n f ^ Y) = supp(X u Y) / supp(vY). Độ tin cậy cũng có thể định nghĩa thông qua xác suất có điều kiện như sau: c o n f ( ^ y) = P (7 |A )= V(XuY)IV(X). Nói cách khác độ tin cậy của luật r : X -> Y chính là xác suất có điều kiện của các tác vụ chứa Y xét trong điều kiện chứa X. Vỉ dụ 1: trong thực tế bán hàng thường ta nhận được các phát biểu kiểu như : "30% những người mua mua bia, ruợu mạnh cũng mua lạp xườn ”, hoặc "5% những người mua hàng mua cả 3 mặt hàng bia, rượu mạnh, lạp xườn". Khi đó 30% là độ tin cậy, 5% là độ hỗ trợ của luật. Tập phổ biến (Frequent Itemset) : Tập mục dữ liệu X được gọi là tập phổ biến nếu supp(Z) > minsupp là độ hỗ trợ cực tiểu do người sử dụng xác định. Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội I gọi là r r ~ Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 12 CSDL lưu trừ các dữ liệu tác vụ ( CSDL nhị phân) có thể được lưu trữ dưới dạng bảng m x n . Ví dụ 2: Bảng 1 mô tả CSDL tác vụ ( Transaction Database). Mỗi giá trị của mục dữ liệu thể hiện thuộc tính xuất hiện, hay không xuất hiện (nhận giá trị 0) trong tác vụ. Độ hỗ trợ được xác định thông qua việc xác định giá trị của các thuộc tính trên miền {0,1}. Item A Item B tl 1 0 1 1 t2 0 0 1 0 t3 1 0 1 1 t4 0 0 1 0 t5 0 0 1 tó 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 t7 t8 t9 tio Item c TID Item D Bảng 1. Cơ sở cữ liệu tác vụ Ví dụ 3: Bảng 2 lưu giá trị độ hỗ trợ của mỗi tập mục dừ liệu, tập mục dữ liệu in nghiêng là tập phổ biến với minsupp= 0.2. Ví dụ mục A xuất hiện 3 lần trong tác vụ và tổng số có 10 tác vụ, do đó supp(A) = 3 / 10 = 0.3, hai mục CD xuất hiện đồng thời 5 lần trong 10 tác vụ, do đó suppiCD) = 5 / 10 = 0.5. Itemset Supp(X) Itemset Supp(X) A 0.30 BD 0.10 B 0.10 CD 0.50 c 0.80 ABC 0.00 D 0.70 ABD 0.00 Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội Phát hiện luật kết hợp mờ có độ ho trợ không giống nhau Trang 13 AB 0.00 A CD 0.20 AC 0.20 BCD 0.10 AD 0.30 ACBC 0.00 BC 0.10 {} {} Bảng 2. Độ hồ trợ của các tập mục dữ liệu r 7 r Các luật kêt họp thu được từ các tập mục dữ liệu phô biên trong bảng 3: Luật kêt họp A -* B A,c -* D c - A A,D -» A -» D C,D -*• A c D -» A c - D D -* c Bảng 3. Luật kêt hợp 1.3. Phân loại thuật toán ph át hiện luật kết hợp hiện có Vấn đề phát hiện tất cả các luật kết hợp có độ hỗ trợ và độ tin cậy vượt quá ngưỡng xác định nào đó (tương ứng là minSupp và minConf do người sử dụng xác định) được phân rã thành 2 vấn đề con là tìm các tập có độ hỗ trợ lớn hơn một giá trị xác định trước và sinh luật từ tập tìm được. Có hai cách tiếp cận để xác định độ hỗ trợ của một tập mục dữ liệu [5,6], đó là: Counting: Độ hỗ trợ của một tập mục dữ liệu được tính thông qua các thể hiện của nó trong tập các tác vụ trong CSDL. Biến đếm được khởi tạo bằng 0 cho mỗi tập mục dữ liệu đang được xét, sau đó duyệt các tác vụ trong CSDL và mỗi khi xác định được ứng cử viên là tập con của tác vụ thì biến đếm tăng lên một đơn vị. Intersection'. Xác định độ hỗ trợ của tập mục dữ liệu bằng cách thiết lập các tập giao Tidlist là tập định danh của các tác vụ. Với mỗi tập mục dữ liệu X tồn tại một Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội f r ~ Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 14 x.tidlist. Tập giao Tidlist của tập mục dữ liệu c = X u Y là c.tidlist =x.tidlist nY.tidlist. Độ hỗ trợ của tập c sẽ là |C.tidlist| = II c.tidlistịl / II ơ||. Các thuật toán phát hiện luật kết họp hiện có được hệ thống theo sơ đồ dưới đây, việc phân loại tiến hành trước tiên theo chiến lược tìm kiếm, sau đóphân loại theo cách xác định giá trị độ hỗ trợ cho các tập mục dữ liệu. Có hai chiến lược tìm kiếm: BFS ( Breadth Fist Search - Tìm kiếm theo chiều rộng) và DFS (Depth First Search - Tìm kiếm theo chiều sâu ) . Có hai cách xác định độ hỗ trợ của tập mục dữ liệu là Counting và Intersection. Ta có sơ đồ phân loại các thuật toán phát hiện luật kết hợp thông thường như sau: n /\ C ou nting /\ intersection l / Apriori Pratition Apriori TID ACLOSE Counting Intersection l / FP-growth Eclat CHARM D ie Hình 1. Hệ thống một số thuật toán phát hiện luật kết hợp hiện có Trong sơ đồ trên, thuật toán CHARM và ACLOSE đánh giá là hiệu quả nhất vì cả hai thuật toán này đều dựa trên tính chất đóng của các tập phổ biến để tìm ra một số ít tập phổ biến có tính chất đặc biệt: các luật sinh ra từ những tập phổ biến này là tương đương với tập các luật sinh ra từ tất cả các tập phổ biến. Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r r *v Trang 15 Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau II. Cơ sở lý thuyết thuật toán CHARM và ACLOSE Sự khó khăn và phức tạp của phát hiện luật kết hợp từ CSDL chủ yếu là ở vấn đề tìm các tập phổ biến từ cơ sở dữ liệu đã cho. Thuật toán mới nhất và được xem là hiệu quả nhất để phát hiện luật kết họp cho đến thời điểm này là CHARM và ACLOSE [15,16]. Khác với các các thuật toán thông thường khác, cách tiếp cận của hai thuật toán này thể hiện ưu điểm ở chỗ: Các tác giả của hai thuật toán CHARM và ACLOSE đều chỉ ra được rằng các luật kết họp được sinh ra từ các tập phổ biến đóng cực đại và từ các tập phổ biến là như nhau. Do đó việc tìm các tập phổ biến được đưa về tìm các tập phổ biến đóng và vì thế không gian tìm kiếm trong cả hai thuật toán này được giảm nhiều đồng thời các luật kết hợp được sinh ra cũng được thu gọn, giảm bớt đáng kể các luật trùng lắp, dư thừa. Cả hai thuật toán CHARM và ACLOSE thực chất đều được xây dựng trên cơ sở lý thuyết toán học khá giống nhau [15,16]. Nội dung dưới đây sẽ tập trung trình bầy cơ sở lý thuyết toán học và giới thiệu cụ thể hai thuật toán này . II.l. Các kiến thức chuẩn biỉ Phần này trình bày một số khái niệm hình thức liên quan [15,16] Định nghĩa 1. Ngữ cảnh phát hiện dữ liệu (Data mining context) là bộ ba 'V = (ỡ, 3, R), trong đó o là tập hữu hạn các đối tượng (object), 3 là tập hữu hạn tất cả các mục dữ liệu và R c 0 x 3 là quan hệ nhị phân, ở đó mỗi cặp (o,i) c R ký hiệu cho sự kiện đối tượng oe o quan hệ với mục dữ liệu 1 G 3. Định nghĩa 2. (Kết nối Galois) Cho 2° với f(0) = { ie3( I Vog o , (o,i) 6 R}, g(I) = {o eớ I Vi el, (o,i)eR} f(0) là tập mục dữ liệu chung cho tất cả các đối tượng của o và g(I) là tập các đối tượng quan hệ với tất cả các mục dữ liệu trong I. Cặp ánh xạ (f,g) gọi là kết nối Galois giữa tập các tập con của o và tập các tập con của 3 . Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội r r ~ Phải hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 16 Từ định nghĩa này, có các tính chất sau đây: Tính chất 1: Với I], I2 c 3 và Oi, 0 2 CỊ o, ta có: ( l ’) 0 , c 0 2 => f ( 0 , ) 3 f ( 0 2) U l C l 2 =>g ( I i ) 3 g ( I 2) 2 .0 C g(I) « I C f(0) s là một tập. Hàm c: 2s -> 2S xác định giữa tập tất cả các tập con s, là toán tử đóng (closure operator) trên s nếu với tất cả I, I’ c s, c thoả mãn Định nghĩa 3. Cho của các tính chất sau: 1.MỞ rộng (Extension): I C c(I) 2.Đơn điệu (Monotonicity): nếu II C 12, thì c(Il) C c(I2) 3.Tính Idempotency: c(c(I)) = c(I); Tập con I của s được gọi là đóng (closed) nếu c(I) = I. Định nghĩa 4: Các ánh xạ họp h = f0g trong 21và h ’ = g0f trong 2° được gọi là các phép toán đóng Galois. Các ánh xạ này có các tính chất sau: Mở rộng: (3) I C h(I) (3’) 0 c h ’(0) Idempotency:(4) h(h(I)) = h(I) Đơn điệu: (5) I) c l 2 => h(Ii) C h(I2) (4’) h ’(h’(0)) = h ’(0) (5’) o , C 0 2 => h ’( 0 ,) c h ’( 0 2) Tập mục dữ liệu I C 3 được gọi là đóng nếu và chỉ nếu h(I) = I. Khi đó tập mục dữ liệu đóng nhỏ nhất chứa I chính là h(I) và h(I) được gọi là bao đóng của I. Tỉnh chất 2. Gỉa sử li I2 là 2 tập mục dữ liệu thể thì h (li I2 ) = h(h(Ii) h(I2)) Định nghĩa 5. (Dàn tập mục dữ liệu đóng) Ký hiệu c là tập tất cả các tập mục dữ liệu đóng nhận được từ rD theo phép toán Galois h. Cặp j£c = (C, < ) được gọi là dàn các tập mục dữ liệu, cấu trúc dàn này có hai 2 tính chất: 1.Tồn tại một sắp thứ tự từng phần trên các phần tử của dàn sao cho với mọi phần tử I, I’ c j£q, I < I’ khi và chỉ khi I c I’; 2.Tất cả các tập con của có một phần tử biên dưới lớn nhất (phần tử join) và có một phần tử biên trên nhỏ nhất (phần tử meet), và Ẩ>c là một dàn đầy đủ. Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội Phát hiện luật kết hợp mờ có độ hỗ trợ không giống nhau Trang 17 Định lý cơ bản của Dàn Galois: Join (S) = h(uC ) với C eS và Meet(S) = n C với C eS. Dưới đây ta định nghĩa các tập phổ biến vàtập phổ biếnđóng,cácluật kếthợp và luật kết hợp chắc theo kết nổi Galois: Định nghĩa 6. Giả s ử l c 3 là tập mục dữ liệucủa r/), độhỗ trợ của tập I trong rD là : support(I) = ||g(I)||/|ịỡỊ| . Định nghĩa 7. Tập mục dữ liệu I được gọi là tập phổ biến nểu support(I) > minsupp; tập phổ biến và đóng được gọi là tập phổ biến đóng. Ký hiệu Fc là tập tất cả các tập phổ biến đóng nhận được từ cơ sở dữ liệu rtì, tức là F c = { I c 3 / 1 = h(I) và support(I) > minsupp} Tính chất 3: Tập con của tập phổ biến là tập phổ biến. Chứng minh: Giả sử I, I’ c: 3 t, I là tập phổ biến, r c I. Theo tính chất của kết nối Galois I’c I => g(I’)3 g(I) => support (I’) > support(I) > minsupp. Tính chất 3 Mọi tập chứa tập con không phải là tập phổ biển đều không là phổ biến. Định nghĩa 8. Tập Mc gồm tất cả các tập phổ biến đóng không phải là tập con thực sự của bất kỳ một tập phổ biến đóng nào khác được gọi là tập các tập phổ biến đóng cực đại, nói cách khác: Mc - { IgFc / không tồn tại tập I’ e Fcvà I c l ’ } Tính chất 4: Tập các tập phổ biến cực đại và tập các tập phổ biến đóng cực đại là trùng nhau, tức là: ^ Chứng minh: Ta chỉ cần chứng minh ràng với mọi I eM, I sẽ là tập đóng tức là I = h(I). Theo tính chất (2) của dàn Galois ta có I ( h(I) và do I là tập phổ biến cực đại nên support(h(I)) = support(I) > minsupp, ta suy ra rằng I = h(I) hay I là tập phổ biến đóng cực đại. Định nghĩa 9. (theo cách sử dụng kết nối Galois) Luật kết hợp có dạng Ỉ! —» I2, ở đây It, I2 là các tập mục dữ liệu và I] n l 2 = 0 , định nghĩa: Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội au.oc G i A HA K'Óf ị THÔNGTlN.THƯVIỆNị r ** r Phát hiện luật kêt hợp mờ có độ hô trợ không giông nhau Trang 18 supportỢi -> I2) = II g(IiUl2)||/|| o II; conf(I, -> I2) = support(11 u l 2)/support(I!) = II g(IiUl2)/|| g(I])|| Tỉnh chất 4: Độ hồ trợ của tập mục dữ liệu ICZ 3 nhận từ cơ sơ dừ liệu D bằng độ hỗ trợ bao đóng của nó, tức là support(I) = support(h(I)). Chứng minh: Giả sử I C 3 là một tập mục dừ liệu, độ hồ trợ của I trong I2 được gọi là luật chính xác nếu conf(Ii -> I2) = 1 và được gọi là luật xấp xỉ nếu conf(l! —> I2) < 1 . Định nghĩa 10: Tập mục dữ liệu I từ h(I j ) - lị / Ij e \ là cơ sở đối với tất cả các luật chính xác, tức là với mọi r’ e (Q. ở đó: conf(r’) = 1 > minconf thì o 1= r \ Hệ quả 1. (Định lý cơ bản về luật tin cậy chính xác) Giả sử CỊ*P là tập các tập mục dữ liệu phổ biến giả đóng trong ('D. Tập = { r: It => h(l! ) - 1| / 1| G Cf^p \ là cơ sở đối với tất cả các luật tin cậy chính xác. Định lý 2. (Định lý về tập thu gọn của các luật kết hợp xấp xỉ) Giả sử ê là tập tất cả các tập mục dữ liệu đóng và li - h / Ỉ2 Trang 19 li và I ] , I2 e ê )■ là tập chuẩn được thu gọn đối với các luật kết hợp xấp xỉ, tức là với mọi r’ e <ĩl ở đó 1> conf(r’) > minconf thì d 1= r’. Hệ quả 2. (Định lý về tập thu gọn của các luật kết hợp tin cậy xấp xỉ) Giả sử là tập tất cả các tập mục dữ liệu đóng phổ biến trong 'Z) . Tập (B d = \ r: I2 => li - 12 / 12 c I] và I] , I2 e <7^ \ là tập chuẩn được thu gọn đối với tất cả các luật kết hợp tin cậy xấp xỉ (approximate valid association rules), tức với mọi f e d , thì (H = <1r: I2 => li - 12 / 12 c li và I] là tập phổ biến, minconf < conf(r’) í1 thì H d 1= r’. II.2. Phương pháp xăy dựng thuật toán CHARM và ACLOSE Có thể nhận thấy rằng tập mục dữ liệu đóng là tập cực đại của các mục dữ liệu là chung đối với các tác vụ. Dựa trên tính chất của dàn các tập mục dữ liệu đóng trong <ĩ) người ta có thể tìm được tất cả các tập phổ biến từ CSDL này bàng cách sinh ra các tập con của các tập phổ biến đóng cực đại với độ hỗ trợ của nó được suy dẫn từ độ hỗ trợ của các tập mục dữ liệu đóng phổ biến. Từ các tập phổ biến tìm được sẽ sinh ra tất cả các luật kết hợp theo đúng tinh thần của thuật toán Apriori [5,6,15,16]. Tuy nhiên theo hệ quả 2 có thể sinh ra trực tiếp tập các luật kết hợp tin cậy được thu gọn từ các tập phổ biến đóng cực đại. Các thuật toán A-CLOSE và CHARM về cơ bản được xây dựng theo các bước sau đây: 1. Tim tất cả các tập phổ biến đóng cực đại; 2. Xác định cơ sở luật kết hợp tin cậy chính xác (exact valid association rule basis): bằng cách xác định các tập giả đóng trong r: I2 —> li - 12 / 1 2 và sau đó sinh ra các luật c: l i , li là tập phổ biến đóng và I2 là tập giả đóng. 3. Xây dịmg tập thu gọn của các luật kết hợp tin cậy xấp xỉ: bằng cách sinh ra các luật ở dạng r: I2 —> li - 12 / 12 l i , I] I2 là các tập phổ biến đóng. Hoàng Việt Nguyên - Luận văn ThạcSĩ - Khoa Công nghệ ĐHQG Hà Nội