Tài liệu Một số phương pháp khai phá luật kết hợp trên cơ sở dữ liệu gia tăng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ =======  ====== NGUYỄN NGỌC QUỲNH CHÂU MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ =======  ====== NGUYỄN NGỌC QUỲNH CHÂU MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG Ngành : Công nghệ thông tin Chuyên ngành : Kỹ thuật phần mềm Mã số : 60480103 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: GS. TS.Vũ Đức Thi Hà Nội - 2015 1 LỜI CAM ĐOAN Tôi xin cam đoan kết quả trong luận văn là sản phẩm của riêng cá nhân tôi. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc 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 hoàn toàn chịu trách nhiệm theo quy định cho lời cam đoan của mình. Hà Nội, ngày 15/5/2015 Người cam đoan Nguyễn Ngọc Quỳnh Châu 2 LỜI CẢM ƠN Trước tiên, tôi xin chân thành cảm ơn tới các thầy cô giáo trong Khoa Công nghệ thông tin, Đại học công nghệ, Đại học quốc gia đã nhiệt tình giảng dạy, truyền đạt kiến thức. Tôi cũng xin bày tỏ lời cảm ơn sâu sắc nhất tới thầy giáo GS Vũ Đức Thi đã tận tình hướng dẫn, định hướng giải quyết các vấn đề trong luận văn. Tôi xin cảm ơn Ban lãnh đạo và các đồng nghiệp trong Khoa Công nghệ thông tin, Đại học Thủy Lợi đã tạo điều kiện cho tôi trong suốt quá trình học tập. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè đã đồng hành cùng tôi trong quá trình học tập. 3 MỤC LỤC LỜI CAM ĐOAN ........................................................................................................ 1 LỜI CẢM ƠN ............................................................................................................. 2 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................... 5 DANH MỤC HÌNH VẼ .............................................................................................. 6 DANH MỤC BẢNG BIỂU ......................................................................................... 7 CHƯƠNG 1: KHAI PHÁ LUẬT KẾT HỢP ............................................................ 9 1.1 Tổng quan về khai phá dữ liệu ............................................................................. 9 1.2 Giới thiệu về khai phá luật kết hợp .................................................................... 10 1.3 Một số khái niệm cơ bản [3, 5, 7] ...................................................................... 11 1.3.1 Cơ sở dữ liệu giao tác ............................................................................... 11 1.3.2 Tập mục thường xuyên ............................................................................. 13 1.3.3 Luật kết hợp .............................................................................................. 14 1.4 Một số thuật toán khai phá luật kết hợp ............................................................. 16 1.4.1 Thuật toán AIS .......................................................................................... 16 1.4.2 Thuật toán Apriori..................................................................................... 18 CHƯƠNG 2: KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG 21 2.1 Mở đầu .............................................................................................................. 21 2.2 Thuật toán xử lý dữ liệu gia tăng theo chiều dọc - Thuật toán Gia tăng 1........... 21 2.2.1 Ý tưởng thuật toán .................................................................................... 21 2.2.2 Chuyển đổi cơ sở dữ liệu sang chiều dọc................................................... 23 2.2.3 Các thủ tục phụ trợ .................................................................................... 24 2.2.4 Tìm tập mục ứng viên ............................................................................... 27 2.2.5 Tính độ hỗ trợ của tập mục ứng viên ......................................................... 28 2.2.6 Khai phá tập thường xuyên ....................................................................... 29 2.2.7 Xử lý dữ liệu gia tăng................................................................................ 31 2.2.8 Ví dụ minh họa ......................................................................................... 32 2.2.9 Nhận xét về thuật toán gia tăng 1 .............................................................. 34 2.3 Thuật toán xử lý dữ liệu gia tăng theo chiều ngang – Thuật toán Gia tăng 2 ...... 35 4 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 2.3.7 Ý tưởng thuật toán .................................................................................... 35 Xây dựng cây gia tăng............................................................................... 36 Khai phá tập thường xuyên ....................................................................... 39 Lưu trữ và khôi phục cây gia tăng ............................................................. 41 Ví dụ minh họa ......................................................................................... 44 Nhận xét về thuật toán Gia tăng 2 ............................................................. 47 Đề xuất ý tưởng cải tiến cấu trúc cây gia tăng ........................................... 47 CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH THỬ NGHIỆM.................................. 53 3.1 Mô tả chương trình chạy.................................................................................... 53 3.2 Thử nghiệm đánh giá thuật toán Gia tăng 1 ....................................................... 56 3.2.1 Thử nghiệm và đánh giá thuật toán trên nội dung 1, 2 ............................... 56 3.2.2 Thử nghiệm và đánh giá thuật toán trên nội dung 3 ................................... 60 3.3 Kết luận ............................................................................................................. 62 KẾT LUẬN ............................................................................................................... 64 TÀI LIỆU THAM KHẢO ......................................................................................... 65 5 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu xi tj I T X={ sup(X) S0 ||X|| CSDL ,…, } Ý nghĩa Mục dữ liệu thứ i Giao tác thứ j Tập hợp gồm n mục dữ liệu {xi, …, xn} Cơ sở dữ liệu giao tác trên I là tập hợp gồm m giao tác T= {t1, …, tm} Tập mục dữ liệu X gồm k mục dữ liệu Độ hỗ trợ của tập mục dữ liệu X Ngưỡng hỗ trợ tối thiểu cho trước Tập các tập thường xuyên theo ngưỡng S0 Độ dài của tập X = số các phần tử của X Cơ sở dữ liệu 6 DANH MỤC HÌNH VẼ Hình 1-1: Ví dụ minh họa thuật toán AIS................................................................... 18 Hình 1-2: Ví dụ về thuật toán Apriori ........................................................................ 20 Hình 2-1: Cấu trúc cây gia tăng ................................................................................. 36 Hình 2-2: Cây gia tăng với 6 giao tác được thêm vào ................................................. 46 Hình 2-3: Cây gia tăng sau khi được khôi phục.......................................................... 47 Hình 2-4: Cây gia tăng ở mục 2.3.4 sau khi sử dụng thuật toán cải tiến có cấu trúc nhỏ gọn hơn...................................................................................................................... 52 Hình 3-1: Kết quả chạy thử nghiệm ban đầu của Gia tăng 1 ....................................... 54 Hình 3-2: Cơ sở dữ liệu test cho Apriori và Gia tăng 1 .............................................. 54 Hình 3-3: Kết quả chạy Apriori và Gia tăng 1 dữ liệu ban đầu hình 3.2 ..................... 55 Hình 3-4: Dữ liệu tăng thêm T’ .................................................................................. 55 Hình 3-5: Kết quả chạy Apriori và Gia tăng 1 trên T+T’ ............................................ 56 Hình 3-6: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 1, 2, 3,4 ban đầu ...... 58 Hình 3-7: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 1, 2,3, 4 sau khi gia tăng............................................................................................................................ 58 Hình 3-8: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 5, 6, 7, 8 ban đầu ..... 59 Hình 3-9: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 5, 6, 7, 8 sau khi gia tăng............................................................................................................................ 60 Hình 3-10: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ..................... 61 Hình 3-11: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ..................... 61 Hình 3-12: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 3 ..................... 62 7 DANH MỤC BẢNG BIỂU Bảng 1.1: Ma trận giao tác của cơ sở dữ liệu giao tác T ............................................. 12 Bảng 1.2: Biểu diễn ngang của cơ sở dữ liệu giao tác T ............................................. 12 Bảng 1.3: Biểu diễn dọc của cơ sở dữ liệu giao tác T ................................................. 13 Bảng 3.1: Giải thích tiêu đề ....................................................................................... 57 Bảng 3.2: Bộ cơ sở dữ liệu thứ nhất ........................................................................... 57 Bảng 3.3: Kết quả thu được trên bộ cơ sở dữ liệu thứ nhất ......................................... 57 Bảng 3.4: Bộ cơ sở dữ liệu thứ hai ............................................................................. 58 Bảng 3.5: Kết quả thu được trên bộ cơ sở dữ liệu thứ hai ........................................... 59 Bảng 3.6: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ....................... 60 Bảng 3.7: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 2 ...................... 61 Bảng 3.8: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 3 ...................... 61 8 MỞ ĐẦU Khai phá dữ liệu nhằm phát hiện các tri thức mới giúp ích cho hoạt động của con người đã trở thành một lĩnh vực quan trọng. Nhiều hướng tiếp cận khác nhau trong khai phá dữ liệu như phân lớp, phân cụm, hồi quy, luật kết hợp. Khai phá luật kết hợp là một kỹ thuật cơ bản và quan trọng được sử dụng trong khai phá dữ liệu. Khai phá luật kết hợp nhằm tìm ra được những tập phần tử thường xuất hiện đồng thời trong cơ sở dữ liệu hay còn gọi là tập mục thường xuyên (frequent patterns), từ đó rút ra được luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của một tập phần tử khác như thế nào. Khitìm các tập mục thường xuyên với các ngưỡng hỗ trợ khác nhau, công việc tìm kiếm lại phải bắt đầu lại từ đầu. Điều này là lãng phí. Ngoài ra, trong thực tế, cơ sở dữ liệu luôn được bổ sung và gia tăng theo thời gian. Do vậy yêu cầu cần có những thuật toán hiệu quả cho việc phát hiện luật kết hợp khi dữ liệu tăng thêm. Xuất phát từ nhu cầu tìm hiểu về một số phương pháp khai phá luật kết hợp trong bối cảnh gia tăng dữ liệu, học viên đã chọn đề tài “Một số phương pháp khai phá luật kết hợp trong cơ sở dữ liệu gia tăng”. Nội dung luận văn được chia thành 3 chương:  Chương 1: Khai phá luật kết hợp. Chương này giới thiệu về khai phá dữ liệu, các bước trong khai phá dữ liệu, một số kỹ thuật được sử dụng trong khai phá dữ liệu. Tiếp theo, chương này đưa ra những khái niệm trong khai phá luật kết hợp nhưtập mục dữ liệu, cơ sở dữ liệu giao tác, độ hỗ trợ, độ tin cậy của luật kết hợp. Hai thuật toán khai phá luật kết hợp được đề cập trong chương 1 là AIS và Apriori.  Chương 2: Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng. Chương này tập trung vào nghiên cứu hai thuật toán khai phá dữ liệu trên cơ sở dữ liệu gia tăng: thuật toán khai phá luật kết hợp trên cơ sở dữ liệu gia tăng theo chiều dọc và thuật toán khai phá luật kết hợp trên cơ sở dữ liệu gia tăng theo chiều ngang. Trong chương này, học viên cũng đề xuất thuật toán cải tiến cấu trúc cây gia tăng trong thuật toán Gia tăng 2.  Chương 3: Cài đặt chương trình thử nghiệm. Chương này trình bày về cài đặt hai thuật toán Apriori và thuật toán Gia tăng 1.Sau đó là phần chạy thử nghiệm hai thuật toán trên một số cơ sở dữ liệu nhằm đánh giá hai thuật toán trên ba nội dung: thử nghiệm trên cơ sở dữ liệu ban đầu, thử nghiệm trên cơ sở dữ liệu gia tăng, thử nghiệm trên cơ sở dữ liệu ổn định với những ngưỡng khai phá khác nhau. Từ đó rút ra được những so sánh, nhận xét và đánh giá về tính hiệu quả của thuật toán Gia tăng 1 khi dữ liệu gia tăng. 9 CHƯƠNG 1: KHAI PHÁ LUẬT KẾT HỢP Nắm được những kiến thức cơ bản về khai phá dữ liệu và những khái niệm liên quan đến khai phá luật kết hợp như: tập mục dữ liệu, cơ sở dữ liệu giao tác, biểu diễn của cơ sở dữ liệu giao tác, độ hỗ trợ và độ tin cậy của tập mục dữ liệu, tập mục thường xuyên, bài toán khai phá luật kết hợpv.v…Trong phần tiếp theo của chương này, học viên sẽ trình bày hai thuật toán đầu tiên của khai phá luật kết hợp là AIS và Apriori.Thuật toán Apriori là một nội dung cơ sở để phục vụ cho nội dung chính của luận văn. 1.1 Tổng quan về khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Chúng ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) hữu ích, tiềm ẩn và mang tính dự báo trong các tập dữ liệu lớn. Theo [7]: Khai phá dữ liệu là một quá trình phức tạp để tìm kiếm những mẫu hoặc những tri thức có giá trịtừ một lượng lớn dữ liệu. Các nguồn dữ liệu có thể bao gồm cơ sở dữ liệu, kho dữ liệu, các trang web, các kho thông tin khác, hoặc dữ liệu được nhập vào hệ thống một cách tự động. Khai phá dữ liệu gồm những bước sau [7]: 1. Làm sạch dữ liệu: dữ liệu sau khi thu thập được có thể bị lỗi, nhiễu, không đầy đủ, có mâu thuẫn.Những dữ liệu dạng này được xem như thông tin dư thừa, gây nên những kết quả sai lệch. Do đó, cần phải làm sạch dữ liệu như gán các giá trị còn thiếu, sửa chữa các dữ liệu nhiễu/lỗi. 2. Tích hợp dữ liệu: dữ liệu từ nhiều nguồn có thể được tích hợp với nhau. 3. Trích lọc dữ liệu: lấy ra những tập dữ liệu từ cơ sở dữ liệu ban đầu theo một số tiêu chí nhất định. 4. Chuyển đổi dữ liệu: dữ liệu được chuyển từ bộ giá trị này sang một bộ giá trị thay thế phù hợp cho việc khai phá dữ liệu. 5. Khai phá dữ liệu: sử dụng một kỹ thuật phương pháp nào đó để lấy ra được những mẫu dữ liệu (patterns.) 6. Đánh giá các mẫu: đánh giá những mẫu theo tiêu chí nào đó. 7. Biểu diễn tri thức: biểu diễn các mẫu trích xuất được dưới dạng dễ hiểu như đồ thị, hình vẽ, bảng,… Một số kỹ thuật được sử dụng trong khai phá kết hợp (chính là được sử dụng trong bước 5 của khai phá dữ liệu): Phân loại: phương pháp phân loại cho phép chúng ta phân loại một đối tượng vào một lớp. Mỗi lớp được đặc trưng bởi một số thuộc tính nào đó.Ví dụ chúng ta có 10 thể phân loại thành các lớp xe máy khác nhau theo các thuộc tính như nhãn hiệu, phân khối, màu sắc. Khi có một chiếc xe mới chúng ta so sánh thuộc tính của nó với thuộc tính của những lớp đã được định nghĩa để phân xe đó vào một lớp cụ thể. Quá trình phân loại dữ liệu thường gồm hai bước: xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu.  Bước 1(bước học): Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước.  Bước 2 (bước phân loại): Sử dụng mô hình để phân loại dữ liệu. Phân cụm: Phân cụm dữ liệu là quá trình chia một tập dữ liệu ban đầu vào các tập con (subsets). Mỗi một tập như vậy gọi là một cụm (cluster). Các phần tử trong cùng một cụm thì tương tự nhau (similar), các phần tử trong các cụm khác nhau thì sẽ phi tương tự với nhau (dissimilar). Những phương pháp phân cụm khác nhau có thể sẽ sinh ra các cụm khác nhau trên cùng tập dữ liệu ban đầu. Phân cụm được sử dụng rộng rãi trong nhiều ứng dụng như kinh doanh thông minh (business intelligence), nhận dạng ảnh, tìm kiếm web, sinh học và an ninh,… Hồi quy: Theo Wikipedia, hồi quy là một phương pháp thống kê mà giá trị kỳ vọng của một hay nhiều biến ngẫu nhiên được dự đoán dựa vào điều kiện của các biến ngẫu nhiên (đã tính toán) khác. Cụ thể, có hồi qui tuyến tính, hồi qui lôgic, hồi qui Poisson và học có giám sát. Khai phá luật kết hợp: nhằm phát hiện ra những phần tử nào thường hay đi kèm với nhau. 1.2 Giới thiệu về khai phá luật kết hợp Khai phá luật kết hợp (Mining association rules) lần đầu được RakeshAgrawal Agrawal đưa ra vào năm 1993 [5]. Khai phá luật kết hợp là một kỹ thuật được sử dụng trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuất hiện cùng nhau trong cơ sở dữ liệu;từ đấyrút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác. Ví dụ, sự xuất hiện của A kéo theo sự xuất hiện của B nên ta có luật kết hợp (A→B). Dạng luật như vậy được gọi là luật kết hợp và quá trình tìm ra được các luật kết hợp được gọi là khai phá luật kết hợp. Luật kết hợp là dạng luật khá đơn giản nhưng mang lại khá nhiều ý nghĩa. Thông tin mà luật kết hợp cung cấp hỗ trợ đáng kể trong quá trình đưa ra quyết định. Các giải thuật khai phá luật kết hợp tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có. Chúng ta xem xét một bài toán kinh điển về khai phá luật kết hợp được nêu ra trong [7]: bài toán phân tích giỏ hàng. Khách hàng vào siêu thị mua hàng. Họ sẽ bỏ 11 vào giỏ hàng của họ những mặt hàng mà họ cần mua.Khai phá luật kết hợp trong bài toán này nhằm tìm ra các luật kết hợp giữa các mặt hàng mà khách hàng đã mua. Một số luật kết hợp rút ra được sau khi phân tích các mặt hàng được mua:  “98% khách hàngmàmua tạp chí thể thao thì đều mua các tạp chí về ôtô” sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô”.  “60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em” sự kết hợp giữa “bia” với “bỉm trẻ em”. Những luật kết hợp như vậy rất có ích trong việc giúp các nhà quản lý nắm bắt được thói quen mua hàng của khách hàng, khi mua một (hoặc một số) mặt hàng này thì khách hàng có xu hướng mua thêm một số mặt hàng nào nữa. Từ đấy có những chiến lược quản lý hợp lý. Như vậy, khai phá luật kết hợp có thể giải quyết được bài toán hết sức đời thường như: hàng triệu khách hàng vào siêu thị sẽ mua mặt hàng nào? Những mặt hàng nào mà khách hàng kết hợp cùng mua. Tất nhiên, khai phá luật kết hợp cũng có nhiều ý nghĩa trong các lĩnh vực khác như tài chính, y học, công nghệ… Khai phá luật kết hợp nhằm tìm ra sự tương quan (correlations) của các sự kiện xuất hiện thường xuyên một cách đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơsởdữliệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tảcác sựkiện xảy ra đồng thời (một cách thường xuyên) nhưthếnào. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ:  Bài toán 1: Tìm các tập mục dữ liệu thường xuyên theo một ngưỡng S0 cho trước.  Bài toán 2: Từ các tập mục dữ liệu thường xuyên tìm được ở bài toán 1, tìm các luật kết hợp thỏa mãn độ tin cậy cho trước. Bài toán thứ hai là bài toán đơn giản. Hầu hết các nghiên cứu về luật kết hợp tập trung vào bài toán thứ nhất. Nội dung luận văn này cũng đi sâu vào nghiên cứu một số thuật toán để tìm các tập mục dữ liệu thường xuyên. 1.3 Một số khái niệm cơ bản [3, 5, 7] 1.3.1 Cơ sở dữ liệu giao tác Tập hợp các mục dữ liệuI={x1, x2, …, xn} là tập n thuộc tính (mục dữ liệu) riêng biệt. Mỗi xi ∈ I gọi là một mục dữ liệu (item) hay là một thuộc tính. Ví dụ: I= {bánh mì, sữa, bỉm,…). Một giao tác chứa một tập con {x , x , … , x } ⊆ I . Đặt ti = {x , x , … , x } , ti được gọi là định danh của giao tác{x , x , … , x }. Một cơ sở dữ liệu giao tác (Transaction Database) trên I là một tập các định danh giao tác T = {t1, t2,…,tm}, với ti là một định danh giao tác trên Ichứa một tập các mục dữliệu X ⊆ I. Ví dụ, trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lầnmua 12 hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những mặt hàng nào. Mỗi tập con X ⊆ I chứa k mục dữ liệu được gọi là tập mục k phần tử (k-itemset). Khi đó ta nói rằng lực lượng của X bằng k (||X|| = k). 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. Biểu diễn 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 tập mục dữ liệu I={x1, x2, …, xn}. Ma trận giao tác của T là ma trận m×n được định nghĩa: 1 ℎ ∈ = 0 ℎ ∉ Với một cơ sở dữ liệu giao tácTnhư sau thì ta sẽ có ma trận giao tác như trong bảng 1.1: t0 = {x0, x1, x2} t1 = {x0,x1,x2,x3,x4} t2 = {x0, x2, x3} t3 = {x0, x2, x3, x4} t4 = {x0, x1, x2, x3} Bảng 1.1: Ma trận giao tác của cơ sở dữ liệu giao tác T x0 x1 x2 x3 x4 t0 1 1 1 0 0 t1 1 1 1 1 1 t2 1 0 1 1 0 t3 1 0 1 1 1 t4 1 1 1 1 0 -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 chứa danh sách những mục dữ liệu trong giao tác đó. Như vậy chúng ta có thể hình dung theo cách này thì các mục dữ liệu được biểu diễn theo chiều ngang. Bảng1.2: Biểu diễn ngang của cơ sở dữ liệu giao tác T Giao tác t0 t1 t2 t3 t4 Mục dữ liệu x0, x1, x2 x0, x1, x2, x3, x4 x0, x2, x3 x0, x2, x3, x4 x0, x1, x2, x3 -Biểu diễn dọc: Một cơ sở dữ liệu là danh sách các mục dữ liệu, mỗi một mục dữ liệu 13 có một danh sách tất cả các định danh của giao tác chứa mục dữ liệu này. Như vậy chúng ta có thể hình dung theo cách này thì các mục dữ liệu được biểu diễn theo chiều dọc. Bảng1.3: Biểu diễn dọc của cơ sở dữ liệu giao tác T Mục dữ liệu x0 x1 x2 x3 x4 Giao tác t0, t1, t2, t3, t4 t0, t1, t4 t0, t1, t2, t3, t4 t1, t2, t3, t4 t1, t3 -Độ hỗ trợ (support):X là một tập mục con của I: X⊆ I và t là một định danh giao tác, t ∈ T. Nếu X∈ t thì ta nói rằng t chứa X. Độ hỗ trợ của X (ký hiệu là support(X) hay sup(X)) là tần suất xuất hiện X trong T: sup( ) = ố ị ℎ ℎứ ố ị ℎ ổ Như trong bảng 1.1, ta có sup(x0)=5/5=1, sup(x0, x1)= sup(x0, x1) = 3/5=0.6. Từ khái niệm trên của độ hỗ trợ, chúng ta cũng có thể tính rằng: độ hỗ trợ sup(X) của tập mục dữ liệu X là số các giao tác mà xuất hiện X. Theo cách này: sup(x0)=5, sup(x0, x1)= 3. Về bản chất, hai cách tính này là tương đương nhauvì đều cung cấp thông tin về mục dữ liệu xuất hiện trong cơ sở dữ liệu là nhiều hay ít, từ đó biết được rằng nó có phải là tập mục dữ liệu thường xuyên hay không. 1.3.2 Tập mục thường xuyên Cho một tập mục X ⊆ I và một ngưỡng hỗ trợ tối thiểu minsup> 0 (được cho bởi người sử dụng). Tập mục X được gọi là tập mục thường xuyên hay tập mục phổ biến (Frequent ItemSet hay Large ItemSet) theo độ hỗ trợ tối thiểu minsup khi và chỉ khi sup(X) ≥ minsup. Gọi là tập tất cả các tập mục dữ liệu thường xuyên theo ngưỡng hỗ trợ tối thiểu S0 của cơ sở dữ liệu giao tác T trên I. Ta có các tính chất sau: Tính chất 1: Mọi tập con của tập thường xuyên là một tập thường xuyên: ∀ ∈ à∀ ⊆ ℎỏ ⊆ ℎì ∈ Tính chất 2: Mọi tập mục dữ liệu chứa một tập con không thường xuyên thì là một tập không thường xuyên: 14 ∀ ∉ à∀ ⊆ ℎỏ ⊆ ℎì ∉ Tính chất 3: Nếu ⊆ thì sup(X) ≥ sup(Y) vì tất cả các giao tác chứa XY thì cũng chứa X nhưng không phải giao tác nào chứa X thì cũng chứa cả Y. 1.3.3 Luật kết hợp 1.3.3.1 Khái niệm Một luật kết hợp (Association Rules) trên cơ sở dữ liệu giao tácT là một biểu thức có dạng → , với , ⊆ à ∩ = .  A gọi là tiên đề (hoặc nguyên nhân).  B gọi là hệ quả. Độ hỗ trợ của luật kết hợp → được định nghĩa: ( → )= ( ∪ )= ( ) Với cơ sở dữ liệu giao tác ở bảng 2.1 ở ta có: sup(x0→ x1) = sup({x0,x1}) = sup(x0x1) = 3 sup(x0x1→ x2) = sup(x0x1x2) = 3 sup(x0→ x4) = sup(x0x4) = 2 Luật kết hợp A→ B là thường xuyên theo ngưỡng S0 nếu sup(A→ B) ≥ S0. Ở ví dụ trên, với S0 = 2, luật sup(x0→ x1), sup(x0x1→ x2) là luật thường xuyên theo ngưỡng hỗ trợ S0. Ý nghĩa của độ hỗ trợ: độ hỗ trợ mang ý nghĩa thống kê của luật. Nói rằng độ hỗ trợ của luật A→ B là 20 nghĩa là có 20 giao tác chứa {AB}. Độ tin cậy (Confidence) của luật A→ Blà tỷ lệ giữa số lượng các giao dịch trong T chứa A ∪ và số giao dịch chứa A: ( → ) = ( )/ ( ). Luật kết hợp → được gọi là luật tin cậy (confidence rule) theo ngưỡng S0 và ( → )≥ C0 nếu → là luật thường xuyên theo ngưỡng S0và ớ 0< ≤ 1. Ý nghĩa của độ tin cậy: độ tin cậy đo mức độ “đúng đắn” của luật, và người ta quan tâm đến luật có độ tin cậy cao. Một luật kết hợp A→ B là thường xuyên nhưng độ tin cậy của nó thấp thì nó cũng không có ý nghĩa trong công tác quản lý. Ví dụ, khi phân tích giỏ hàng của khách hàng trong một siêu thị ta rút ra được luật như sau: 40% khách hàng mua cùng lúc cả sữa và bánh mì, 75% khách hàng mua sữa thì cũng mua bánh mì. Như vậy, 30% là độ hỗ trợ của luật và 75% là độ tin cậy của luật. Bài toán khai phá luật kết hợp có thể được phát biểu như sau: Cho một tập mục dữ liệu I gồm n mục dữ liệu I={x1, x2, …, xn}và cơ sở dữ liệu giao tác T gồm m giao tácT = {t1, t2,…,tm}, độ hỗ trợ tối thiểu minsup và độ tin cậy tối thiểu minconf. Tìm tập các luật kết hợp: R = {X→ Y | X, Y ⊆ I, s(X→ Y) ≥ minsup, conf (X→ Y) ≥ minconf}. 15 Giải quyết bài toán: bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ:  Bài toán 1 (Bài toán khai phátập mục thường xuyên): tìm tất cả những tập mục dữ liệu mà có độ hỗ trợ lớn hơn hoặc bằng minsup.  Bài toán 2 (Bài toán khai phá luật kết hợp): từ những tập mục thường xuyên tìm được ở bài toán 1, tìm tất cả các luật kết hợp có độ tin cậy lớn hơn hoặc bằng mincof. Ví dụ minh họa cho bài toán khai phá luật kết hợp: chúng ta sử dụng bài toán giỏ hàng trong siêu thị: siêu thị có 4 mặt hàng (4 mục dữ liệu) và có 4 giao tác (4 hóa đơn mua hàng) như sau: Giao tác Mặt hàng được mua bánh mì, bơ, trứng bơ, trứng, sữa bơ bánh mì, bơ Tìm luật kết hợp với minsup = 40% và minconf = 60% Ta tính được độ hỗ trợ của các tập mục dữ liệu như sau: Tập mục dữ liệu bánh mì bơ trứng sữa bánh mì, bơ bánh mì, trứng bánh mì, sữa bơ, trứng bơ, sữa trứng, sữa bánh mì, bơ, trứng bánh mì, bơ, sữa bơ, trứng, sữa bánh mì, bơ, trứng, sữa Độ hỗ trợ 50% 100% 50% 25% 50% 25% 0% 50% 25% 25% 25% 0% 25% 0% Từ đó, ta tìm được tập mục thường xuyên là (bánh mì, bơ), (bơ, trứng), ta tính được độ tin cậy của các luật kết hợp thường xuyên. 16 Luật kết hợp bánh mì → bơ bơ → bánh mì bơ → trứng trứng → bơ Độ tin cậy 50% 100% 100% 50% Vậy luật kết hợp thỏa mãn minsup và minconf cho trước là bơ → bánh mì, bơ → trứng. 1.3.3.2 Một số tính chất của luật kết hợp Tính chất 1: Không hợp luật Nếu X → Y và X → Z thì không thể suy ra X → YZ. Nếu X → Y và Z → Y thì không thể suy ra XZ → Y. Tính chất 2: Không tách luật Nếu XY → Z thì không thể suy ra X → Z và Y → Z. Tuy nhiên đảo lại X → YZ thì X → Y và X → Z. Tính chất 3: Các luật kết hợp không có tính chất bắc cầu Nếu X → Y và Y → Z thì không thể suy ra X → Z. Tính chất 4: Nếu luật X → (L – X) không thỏa mãn độ tin cậy tối thiểu thì Y → (L – Y) cũng không thỏa mãn độ tin cậy tối thiểu với Y ⊆ X và X, Y ⊂ L. 1.4 Một số thuật toán khai phá luật kết hợp 1.4.1 Thuật toán AIS Thuật toán AIS [5] là thuật toán đầu tiên được đề xuất cho khai phá luật kết hợp. Nội dung cơ bản của thuật toán AIS:  Duyệt cơ sở dữ liệu lần thứ nhất để tính độ hỗ trợ của từng mục dữ liệu, lấy ra tập L1 gồm những mục dữ liệu có độ hỗ trợ ≥ngưỡng hỗ trợ tối thiểu S0 cho trước.  Từ L1 (là tập 1 mục dữ liệu thường xuyên), tìm C2 là tập ứng viên có 2 mục dữ liệu bằng cách: duyệt từng giao tác, ghép từng cặp mục dữ liệu có trong giao tác thành tập ứng viên. Ứng với mỗi tập ứng viên, duyệt lại cơ sở dữ liệu để đếm số giao tác có chứa tập mục này để tính độ hỗ trợ và thu được tập các tập thường xuyên có 2 mục dữ liệu. 17  Lặp lại, tìm được tập mục ứng viên có k phần tử từ những tập mục dữ liệu k phần tử lấy từ các phần tử trong giao tác. Tiếp tục cho đến khi tập những tập mục dữ liệu thường xuyên có k+1 phần tử là rỗng. Ví dụ: chạy thuật toán AIS với độ hỗ trợ tối thiểu S0 = 3 và cơ sở dữ liệu như sau: t0 t1 t2 t3 t4 x0 1 1 1 1 1 x1 1 1 0 0 1 x2 1 1 1 1 1 x3 0 1 1 1 1 x4 0 1 0 1 0 Ta có các bước khi chạy thuật toán AIS như sau: Bước 1: Mục dữ liệu x0 x1 x2 x3 x4 Độ hỗ trợ 5 3 5 4 2 L1 x0 x1 x2 x3 Bước 2: Mục dữ liệu x0 x1 x0 x2 x1 x2 x0 x3 x0 x4 x1 x3 x1 x4 x2 x3 x2 x4 Độ hỗ trợ 3 5 3 4 2 2 1 4 2 L2 x0 x1 x0 x2 x1 x2 x0 x3 x2 x3 18 Bước 3: Mục dữ liệu x0 x1 x2 x0 x1 x3 x0 x1 x4 x1 x2 x3 x1 x2 x4 x2 x3 x4 x0 x2 x3 x0 x2 x4 Độ hỗ trợ 3 2 1 2 1 2 2 2 L3 x0 x1 x 2 Độ hỗ trợ 2 1 2 1 L4 ∅ Bước 4: Mục dữ liệu x0 x1 x2 x3 x0 x1 x2 x4 x0 x2 x3 x4 x1 x2 x3x4 Hình 1-1: Ví dụ minh họa thuật toán AIS Thuật toán AIS phải tính nhiều mục dữ liệu ứng viên, ngoài ra phải duyệt nhiều lần toàn bộ cơ sở dữ liệu để tính độ hỗ trợ của các tập ứng viên. 1.4.2 Thuật toán Apriori Apriori là một thuật toán được đề xuất bởi R. Agrawal và R. Srikant vào năm 1994 [6] nhằm khai khá những tập mục dữ liệu thường xuyên. Sở dĩ thuật thuật toán có tên như vậy là do thuật toán sử dụng những hiểu biết của tập mục thường xuyên (prior knowledge). Apriori sử dụng cách tiếp cận lặp đi lặp lại được biết như là một phương pháp tìm kiếm khôn ngoan: sinh ra các tập ứng viên Ck (gồm những phần tử cók mục dữ liệu) từ các tập thườngxuyên Lk-1 (gồm những phần tử thường xuyên có k1 mục dữ liệu).Thuật toán Apriori sử dụng tính chất sau đây của tập thường xuyên: Mọi tập con của một tập mục thường xuyên là tập thường xuyên. Thuật toán Apriori: Input: cơ sở dữ liệu giao tác T, min_sup Output: Answer là tập các tập mục thường xuyên theo ngưỡng min_sup Method: