Tài liệu Khai thác tập mục cổ phần theo giao tác cao

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NÔNG THỊ NINH Đề tài: KHAI PHÁ TẬP MỤC CỔ PHẦN THEO GIAO TÁC CAO LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên, tháng 7 năm 2014 Số hóa bởi Trung tâm Học liệu 1 http://www.lrc-tnu.edu.vn/ LỜI CẢM ƠN Luận văn này được hoàn thành với sự hướng dẫn tận tình của TS Lê Văn Phùng – Viên Công nghệ thông tin - Viện Hàn Lâm Khoa học Việt Nam. Trước tiên tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới TS. Lê Văn Phùng người đã tận tình hướng dẫn, động viên giúp đỡ tôi trong suốt thời gian thực hiện luận văn. Tôi cũng xin chân thành cảm ơn các thầy cô trong trường Công Nghệ thông tin và Truyền thông – Đại học Thái Nguyên, tạo điều kiện thuận lợi cho tôi hoàn thành tốt khóa học. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học CHK11g đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, người thân, bạn bè đã động viên, khuyến khích và hỗ trợ cần thiết để tôi hoàn thành luận văn này. Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót, kính mong được sự chỉ dẫn của các quý thầy cô và các bạn. Thái Nguyên, ngày 5 tháng 7 năm 2014 Ngƣời viết Nông Thị Ninh Số hóa bởi Trung tâm Học liệu 2 http://www.lrc-tnu.edu.vn/ LỜI CAM ĐOAN n luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Thái Nguyên, ngày tháng năm 2014 Ngƣời cam đoan Nông Thị Ninh Số hóa bởi Trung tâm Học liệu 3 http://www.lrc-tnu.edu.vn/ BẢNG KÝ HIỆU CHỮ VIẾT TẮT S Ký hiệu viết tắt TT Giải thích ABBM: Algorithm Based on Thuật toán dựa trên ma trận Boolean 1Boolean Matrix CSDL Cơ sở dữ liệu DBMS Hệ quản trị cơ sở dữ liệu IR (Information Retrieval) Truy xuất thông tin KPDL Khai phá dữ liệu OODBMS Hệ quản trị cơ sở dữ liệu hướng đối Object Oriented Database tượng 6Management System RDBMS Ralational Database 7Management System Hệ quản trị cơ sở dữ liệu quan hệ 8I Tập n mục dữ liệu 9 DB i1 , i2 ,..., in T1 , T2 ,..., Tm Cơ sở dữ liệu có m giao tác Cơ sở dữ liệu giao tác con của DB, db 1 0 db DB ip Mục dữ liệu thứ p Tq Giao tác thứ q 1 1 1 2 Số mục dữ liệu một cơ sở dữ liệu giao 1 3 n tác Số giao tác của một cơ sở dữ liệu giao 1 4 m tác Tên các mục dữ liệu trong cơ sở dữ liệu 1A,B,C….. Số hóa bởi Trung tâm Học liệu 4 http://www.lrc-tnu.edu.vn/ 5 giao tác 1 6 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 1 7 1 8 1 9 Số hóa bởi Trung tâm Học liệu 5 http://www.lrc-tnu.edu.vn/ DANH MỤC CÁC BẢNG Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang ........................................................ 13 Bảng 2. Biểu diễn cơ sở dữ liệu giao tác dọc ............................................................ 13 Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận ..................................................... 14 Bảng 4. Cơ sở dữ liệu minh họa thực hiện thuật toán COFI-tree ............................. 26 Bảng 5. Các mục dữ liệu và độ hỗ trợ ....................................................................... 27 Bảng 6. Các mục dữ liệu và độ hỗ trợ ....................................................................... 27 Bảng 7. Các mục dữ liệu trong giao tác sắp xếp giảm dần theo độ hỗ trợ ............... 27 Bảng 8. Cơ sở dữ liệu ví dụ...................................................................................... 34 Bảng 9. Giá trị lmv và cổ phần của các mục dữ liệu trong CSDL bảng 8 ................ 35 Bảng 10: Các tập mục cổ phần cao của CSDL bảng 8 ............................................. 36 Bảng 11: CSDL minh họa ngữ nghĩa của tập mục cổ phần cao ............................... 37 Bảng 12: Các giá trị lmv và hàm tới hạn với k=1. .................................................... 44 Bảng 13. Các giá trị lmv và hàm tới hạn với k=2. .................................................... 45 Bảng 14. Các giá trị lmv và hàm tới hạn với k=3. ................................................... 46 Bảng 15: CSDL minh họa có trường hợp hai hàm tới hạn bằng nhau. ..................... 51 Bảng 16: CSDL minh họa trường hợp hai hàm tới hạn luôn bằng nhau. ................. 51 Bảng 17: Giá trị hai hàm tới hạn khi k=1.................................................................. 52 Số hóa bởi Trung tâm Học liệu 6 http://www.lrc-tnu.edu.vn/ DANH MỤC CÁC HÌNH Hình 1.1. Kiến trúc điển hình của hệ thống khai phá dữ liệu ................................... 10 Hình 1.2. Hình cây FP-Growth ................................................................................. 28 Hình 1.3. Cây COFI-tree của mục D ........................................................................ 29 Hình 1.4.. Các bước khai phá cây D-COFI-tree.......................................................22. Số hóa bởi Trung tâm Học liệu 7 http://www.lrc-tnu.edu.vn/ MỞ ĐẦU 1. Đặt vấn đề Chúng ta đang sống trong thời đại bùng nổ về dữ liệu và máy tính đang giữ vai trò ngày càng trở nên quan trọng trong việc lưu trữ và xử lý thông tin. Bên cạnh đó, những thiết bị thu thập dữ liệu tự động cũng phát triển mạnh góp phần tạo ra những kho dữ liệu khổng lồ. Mặc dù trong môi trường tràn ngập dữ liệu như vậy nhưng con người vẫn thiếu thông tin. Theo thống kê của một tổ chức uy tín thì chỉ có 2% - 3% lượng dữ liệu được chuyển thành thông tin có ích. Khi xã hội càng phát triển, lượng thông tin cần càng nhiều thì công việc tổ chức, khai phá dữ liệu ngày càng khó khăn. Như vậy, trong quá trình sử dụng và khai thác thông tin người ta nhận thấy rằng có rất nhiều tri thức còn tiềm ẩn trong dữ liệu. Vấn đề đặt ra là làm thế nào để khai thác được thông tin và khai thác một cách có hiệu quả. Trong quá trình khai phá dữ liệu, có rất nhiều kỹ thuật đã và đang được nghiên cứu. Đặc biệt là các bài toán về khai phá luật kết hợp. Năm 1997, Hilderman đề xuất bài toán khai phá tập mục cổ phần cao. Cổ phần hay đóng góp của một tập mục là số đo tỷ lệ đóng góp của tập mục trong cơ sở dữ liệu. Khai phá tập mục cổ phần cao là khám phá tất cả các tập mục có cổ phần không nhỏ hơn ngưỡng quy định. Loại bài toán này đang được sự quan tâm đặc biệt trong nghiên cứu và đời sống xã hội vì sự đáp ứng to lớn của chúng đối với nhu cầu của thực tiễn. Chính vì vậy, chúng tôi đã chọn đề tài về khai phá tập mục cổ phần cao làm luận văn thạc sỹ của mình. 2. Đối tƣợng và phạm vi nghiên cứu - Đối tượng nghiên cứu là cơ sở dữ liệu giao tác -Phạm vi nghiên cứu trong khuôn khổ tập mục cổ phần cao cùng với các phương pháp, thuật toán khai phá, đặc biệt là tập trung thuật toán khai phá tập mục cổ phần theo giao tác cao là các giá trị theo giao tác của tập mục cần lớn hơn giá trị cổ phần tối thiểu. Số hóa bởi Trung tâm Học liệu 8 http://www.lrc-tnu.edu.vn/ 3. Hƣớng nghiên cứu của đề tài- Nghiên cứu về khai phá dữ liệu, tập trung vào khai phá tập mục thường xuyên, tập mục cổ phần cao, đặc biệt là tập mục cổ phần cao theo giao tác cao. - Cài đặt thực nghiệm tìm tập mục cổ phần cao theo giao tác cao từ dữ liệu bán hàng của một siêu thị cụ thể ở Thái Nguyên. 4. Những nội dung nghiên cứu chính Ngoài phần mở đầu thì luận văn gồm 3 chương sau: Chƣơng 1. KHÁI QUÁT KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN Chƣơng 2. KHAI PHÁ TẬP MỤC CỔ PHẦN CAO Chƣơng 3. ỨNG DỤNG KHAI PHÁ TẬP MỤC CỔ PHẦN CAO THEO GIAO TÁC CAO 5. Phƣơng pháp nghiên cứu - Kết hợp lý thuyết với đánh giá thực nghiệm - Sưu tâp và tổng hợp các kết quả nghiên cứu về tập mục thường xuyên, Khái phá tập mục cổ phần cao và tập mục cổ phần cao theo giao tác cao từ nguồn sách và các bài báo khoa học, hội thảo chuyên ngành trong nước và ngoài nước. - Phân tích bài toán ứng dụng và chọn lọc thuật toán thử nghiệm thích hợp. 6. Ý nghĩa khoa học của đề tài Nghiên cứu tập mục cổ phần cao theo giao tác cao là một nhiệm vụ khai phá dữ liệu quan trọng nhằm phát hiện những tri thức có ý nghĩa lớn, bảo đảm cơ sở khoa học trong chuyên ngành khoa học máy tính. Trong lĩnh vực kinh doanh việc tìm ra những tập mục cổ phần cao theo giao tác cao là thật sự cần thiết nhằm tăng hiệu suất và lợi nhuận hoạt động kinh tế của các doanh nghiệp. Số hóa bởi Trung tâm Học liệu 9 http://www.lrc-tnu.edu.vn/ Chƣơng 1 KHÁI QUÁT KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN 1.1. Tổng quan về khai phá dữ liệu 1.1.1 Kiến trúc của một hệ thống khai phá dữ liệu Kiến trúc của một hệ thống (KPDL) điển hình có thể có các thành phần như hình 1.1. Hình 1.1. Kiến trúc điển hình của hệ thống khai phá dữ liệu - Cơ sở dữ liệu (CSDL), kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data warehouse, …): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang tính hay các dạng lưu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thể hiện trên những dữ liệu này. - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse server): Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên các yêu cầu khai phá của người dùng. Số hóa bởi Trung tâm Học liệu 10 http://www.lrc-tnu.edu.vn/ - Cơ sở tri thức (Knowledge base): Đây là miền tri thức được dùng để hướng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc như: đặc trưng hoá, kết hợp, phân lớp, phân cụm, phân tích sự tiến hoá. - Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tương tác với các modun KPDL để duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể modun đánh giá mẫu được tích hợp vào modun khai phá, tuỳ theo sự cài đặt của phương pháp khai phá được dùng. - Giao diện đồ họa người dùng (Graphical user interface): Bộ phận này cho phép người dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này còn cho phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu (hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau. 1.1.2. Nhiệm vụ chính của khai phá dữ liệu Các bài toán liên quan đến KPDL về bản chất là các bài toán thống kê. Điểm khác biệt giữa các kỹ thuật KPDL và các công cụ phục vụ tính toán thống kê mà chúng ta đã biết là ở khối lượng cần tính toán. Khi dữ liệu đã trở nên khổng lồ thì những khâu như: thu thập dữ liệu, tiền xử lý và xử lý dữ liệu đều đòi hỏi phải được tự động hóa. Tuy nhiên ở công đoạn cuối cùng, việc phân tích kết quả sau khi đã KPDL vẫn luôn là công việc của con người. Do là một lĩnh vực đa ngành, KPDL thu hút các lĩnh vực khoa học khác như trí tuệ nhân tạo, cơ sở dữ liệu, hiển thị dữ liệu, marketing, toán học, vận trù học, tin sinh học, nhận dạng mẫu, tính toán thống kê … Điều mà KPDL có thể làm rất tốt là phát hiện ra những giả thuyết mạnh trước khi sử dụng những công cụ tính toán thống kê. Mô hình dự báo sử dụng kỹ thuật phân cụm (Crustering) để chia nhóm các sự vật, sự kiện sau đó rút ra các luật nhằm tìm ra đặc trưng cho mỗi nhóm và cuối cùng đề nghị một mô hình. Ví dụ, những bạn đọc đăng ký dài hạn của một tạp chí có thể phân nhóm dựa theo nhiều Số hóa bởi Trung tâm Học liệu 11 http://www.lrc-tnu.edu.vn/ tiêu chí khác nhau (lứa tuổi, giới tính, thu nhập…), sau đó tạp chí căn cứ vào đặc trưng riêng của từng nhóm để đề ra mức phí thu trong năm sao cho phù hợp nhất. Những nhiệm vụ cơ bản nhất của KPDL là: Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời câu hỏi: Một dữ liệu mới thu thập sẽ thuộc về nhóm nào? Quá trình này thường được thực hiện một cách tự động. Khai phá luật kết hợp. Nhiệm vụ là phát hiện ra những mối quan hệ giống nhau của các bản ghi giao dịch. Luật kết hợp X=>Y có dạng tổng quát là: Nếu một giao dịch đã sở hữu các tính chất X thì đồng thời nó cũng sở hữu các tính chất Y, ở một mức độ nào đó. Khai phá luật kế thợp được hiểu theo nghĩa: Biết trước các tính chất X, vậy các tính chất Y là những tính chất nào? Lập mô hình dự báo, bao gồm hai nhiệm vụ: Hoặc là phân nhóm dư liệu vào một hay nhiều lớp dữ liệu đã xác định từ trước, hoặc là sử dụng các trường đã cho trong một cơ sở dữ liệu để dự báo sự xuất hiện (hoặc không xuất hiện) của các trường hợp khác. Phân tích đối tượng ngoài cuộc: Một cơ sở dữ liệu có thể có thể chứa các đối tượng không tuân theo mô hình dữ liệu. Các đối tượng dữ liệu như vậy gọi là các đối tượng ngoài cuộc. Hầu hết các phương pháp KPDL đều coi các đối tượng ngoài cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng, chẳng hạn như phát hiện nhiễu thì sự kiện hiếm khi xảy ra lại được chú ý hơn những gì thường xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc được coi như là phai phá các đối tượng ngoài cuộc. Một số phương pháp được ứng dụng để phát hiện đối tượng ngoài cuộc: Sử dụng các hình thức kiểm tra mang tính thống kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các đối tượng có một khoảng cách đáng kể đến cụm bất kỳ khác được coi là đối tượng ngoài cuộc, dùng các phương pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc trưng chính của các nhóm đối tượng. Phân tích sự tiến hóa: Phân tích sự tiến hóa thực hiện việc mô tả và mô hình hóa các quy luật hay khuynh hướng của những đối tượng mà ứng xử của chúng Số hóa bởi Trung tâm Học liệu 12 http://www.lrc-tnu.edu.vn/ thay đổi theo thời gian. Phân tích sự tiến hóa có thể bao gồm cả đặc trưng hóa, phân biệt, tìm luật kết hợp, phân lớp hay phân cụm dữ liệu liên quan đến thời gian, phân tích dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên tính tương tự. [3] 1.2. Bài toán khai phá tập mục thƣờng xuyên 1.2.1. Khái niệm Tập mục thường xuyên Định nghĩa 1.1: Cho tập mục (item) I={I1,I2,…,Im}. 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à 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. 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 đó. Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang Mục dữ liệu Giao tác T1 A, C, D T2 B, C, E T3 A, B, C, E T4 B, E 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 2. Biểu diễn cơ sở dữ liệu giao tác dọc Mục dữ liệu Các giao tác A Số hóa bởi Trung tâm Học liệu T1, T3 13 http://www.lrc-tnu.edu.vn/ B T2, T3, T4 C T1, T2, T3 D T1 E T2, T3, T4 Biểu diễn ma trận nhị phân: Cơ sở dữ liệu giao tác trên tập mục (item) được biểu diễn bởi ma trận nhị phân M = (mpq)mxn ở đó Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận Mục T1 T2 T3 T4 A 1 0 1 0 B 0 1 1 1 C 1 1 1 0 D 1 0 0 0 E 0 1 1 1 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. Độ hỗ trợ (Support) của tập mục X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao tác chứa tập mục X trên tổng số giao tác trong DB, tức là: sup( X ) | {T DB | T | DB | Số hóa bởi Trung tâm Học liệu X}| 14 http://www.lrc-tnu.edu.vn/ Định nghĩa 1.3: Cho tập mục X I với ngưỡng hộ trợ tối thiểu (minimum [0,1] (được xác định trước bởi người sử dụng). X được gọi là tập support) minsup mục thường xuyên (frequent itemset hoặc large 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à 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) luật kết hợp, ký hiệu là sup(X độ hỗ trợ của tập mục X Y, sup(X Y), là 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) luật kết hợp, ký hiệu là 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 P( X / Y ) Và ta có 0 | {T Y chính là xác suất có điều kiện P(X/Y): DB | X T Y T } | | {T DB | X T } | conf(X Y) | {T DB | X Y T } | | {T DB | X T } | sup( X Y ) sup( X ) 1. 1.2.3. Bài toán khai phá luật kết hợp Xác định tất cả X Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu thì luật X Y được gọi là luật kết hợp mạnh. 1.2.4. Một số tính chất 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ó tính chất sau: (1) Nếu X, Y là các tập mục và X Số hóa bởi Trung tâm Học liệu Y thì sup(X) ≥ sup(Y) 15 http://www.lrc-tnu.edu.vn/ (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 là 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) là tính chất quan trọng, nó đượ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.5. Mô tả bài toán khai phá luật kết hợp Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Vấn đề này được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993 [9]. Sau đó năm 1996 được Rakesh Agrawal, Heikki Mannia, Ramakrishnan Srikant, Hannu Toivonen, A.Inkeri Verkamo tiếp tục cải tiến. Ngày nay bài toán khai thác các luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học. Việc khai thác các luật như thế nào vẫn là một trong các phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD – Knowledge Discovery and Data Minning). Mục đích chính của khai phá dữ liệu là trích rút tri thức một cách tự động, hiệu quả và “thông minh” từ kho dữ liệu. Trong hoạt động sản xuất kinh doanh, ví dụ kinh doanh các mặt hàng tại siêu thị, các nhà quản lý rất thích có được những thông tin mang tính thống kê như: “90% phụ nữ có xe máy màu đỏ và đeo đồng hồ Thụy Sỹ thì dùng nước hoa hiệu Chanel” hoặc “70% khách hàng là công nhân thì mua TV thường mua loại 21 inches”. Những thông tin như vậy rất hữu ích trong việc định hướng kinh doanh. Vậy vấn đề đặt ra là liệu có tìm được các luật như vậy bằng các công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể. Đó chính là nhiệm vụ khai phá luật kết hợp. Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi (records) của D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong những bản ghi đó. Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ hỗ trợ (support ration). Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U. Số hóa bởi Trung tâm Học liệu 16 http://www.lrc-tnu.edu.vn/ Vấn đề khám phá luật kết hợp được phát biểu như sau: Cho trước tỉ lệ hỗ trợ (support ration) và độ tin cậy (confidence) Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn và tương ứng. Ví dụ: Gọi D là CSDL mua bán và với = 40%, = 90% Vấn đề phát hiện luật kết hợp được thực hiện như sau: Liệt kê (đếm) tất cả những quy luật chỉ ra sự xuất hiện một số các mục kéo theo một số mục khác. Chỉ xét những quy luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90% Hay chúng ta hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có một CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ “tuổi, giới tính, nghề nghiệp => sản phẩm”. Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên. Ví dụ: trong lứa tuổi nào thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất (thỏa mãn một ngưỡng nào đó)? 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 minconf. 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 2 bài toán con. Bài toán thứ nhất: 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: 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 Số hóa bởi Trung tâm Học liệu 17 http://www.lrc-tnu.edu.vn/ 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. Bài toán thứ hai có thể giải quyết như sau: Giả sử X là tập mục thường xuyên, ta sinh ra luật kết hợp bằng cách tìm mọi Y là tập con của X, kiểm tra độ tin cậy của X\Y Y có thỏa mãn độ tin cậy tối thiểu không. 1.2.6. Một số tiếp cận khai phá tập mục thường xuyên Các nghiên cứu về khai phá tập mục thường xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thường xuyên. Bài toán khai phá tập mục thường xuyên: tìm các tập mục ứng viên và tìm các tập mục thường xuyên. Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thường xuyên, phải tính độ hỗ trợ của nó để kiểm tra. Tập mục thường xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng tối thiểu cho trước. Đã có rất nhiều thuật toán tìm tập mục thường xuyên được công bố, ta có thể phân chúng theo 2 tiêu chí: - Phương pháp duyệt qua không gian tìm kiếm - Phương pháp xác định độ hỗ trợ của tập mục Phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách: duyệt theo chiều rộng (Breadth First Search - BFS) và duyệt theo chiều sâu (Depth First Search - DFS) Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của tất cả các tập mục ứng viên có (k-1) mục trước khi tính độ hỗ trợ của các tập mục ứng viên có k mục. Với CSDL có n mục, lần lặp thứ k phải kiểm tra độ hỗ trợ của tất cả Ckn tập ứng viên có k mục Duyệt theo chiều sâu là duyệt qua CSDL đã được chuyển thành cấu trúc dạng cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có 2n tập con, rõ ràng đây là bài toán NP khó, do đó cần phải có phương pháp duyệt thích hợp, tỉa nhanh các tập ứng viên. Số hóa bởi Trung tâm Học liệu 18 http://www.lrc-tnu.edu.vn/ Phương pháp xác định độ hỗ trợ của tập mục X được chia làm 2 cách: cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ 2 là tính phần giao của các tập chứa định danh của các giao tác chứa X. 1.2.7. Một số tiếp cận khai phá luật kết hợp Luật kết hợp nhị phân (binary association rule hoặc boolean associaiton rule): là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp nhị phân. Trong dạng luật kết hợp này, các mục (thuộc tính) chỉ được quan tâm là có hay không xuất hiện trong giao tác của CSDL chứ không quan tâm về “mức độ” xuất hiện. Ví dụ: Trong hệ thống tính cước điện thoại thì việc gọi 10 cuộc điện thoại và 1 cuộc được xem là giống nhau. Thuật toán tiêu biểu nhất khai phá dạng luật này là thuật toán Apriori và các biến thể của nó. Đây là dạng luật đơn giản và các luật khác cũng có thể chuyển về dạng luật này nhờ một số phương pháp như rời rạc hóa, mờ hóa… Một ví dụ về dạng luật này: “gọi liên tỉnh = „yes‟ AND gọi di động = „yes‟ => gọi quốc tế =‟yes‟ AND gọi dịch vụ 108 = „yes‟, với độ hỗ trợ 20%và độ tin cậy 80%. Luật kết hợp có thuộc tính số và thuộc tính hạng mục (quantitative and categorial association rule): Các thuộc tính của các CSDL thực tế có kiểu rất đa dạng (nhị phân – binary, số - quantitative, hạng mục – categorial,…). Để phát hiện luật kết hợp với các thuộc tính này, các nhà nghiên cứu đã đề xuất một số phương pháp rời rạc hóa nhằm chuyển dạng luật này về dạng nhị phân để có thể áp dụng các thuật toán đã có. Một ví dụ về dạng luật này “phương thức gọi” = „Tự động‟ AND giờ gọi IN [‟23:00:39..23:00:59‟] AND thời gian đàm thoại IN [„200..300‟] => gọi liên tỉnh =‟có‟, với độ hỗ trợ là 23.53% và độ tin cậy là 80%”. Luật kết hợp tiếp cận theo hướng tập thô (mining association rules base on rough set): Tìm kiếm luật kết hợp dựa trên lý thuyết tập thô. Luật kết hợp nhiều (multi – level association rule): với cách tiếp cận theo luật này sẽ tìm kiếm thêm những luật dạng “mua máy tính PC => mua hệ điều hành AND mua phần mềm tiện ích văn phòng,…” thay vì chỉ những luật quá cụ thể như “mua máy tính IBM PC => mua hệ điều hành Microsoft Windows AND mua phần Số hóa bởi Trung tâm Học liệu 19 http://www.lrc-tnu.edu.vn/ mềm tiện ích văn phòng Microsoft Office,..”. Như vậy dạng luật đầu là dạng luật tổng quát hóa của dạng luật sau và tổng quát theo nhiều mức khác nhau. Luật kết hợp mờ (fuzzy association rule): với những hạn chế còn gặp phải trong quá trình rời rạc hóa các thuộc tính số (quantitave attributes), các nhà nghiên cứu đã đề xuất luật kết hợp mờ nhằm khắc phục các hạn chế trên và chuyển luật kết hợp về dạng tự nhiên hơn, gần gũi hơn với người sử dụng. Một ví dụ của dạng này là: “thuê bao tư nhân =‟yes‟ AND thời gian đàm thoại lớn AND cước nội tỉnh = „yes‟ => cước không hợp lệ =‟yes‟, với độ hỗ trợ là 4% và độ tin cậy là 85%”. Trong luật trên, điều kiện thời gian đàm thoại lớn ở về trái của luật là một thuộc tính đã được mờ hóa. Luật kết hợp với thuộc tính được đánh trọng số (association rule with weighted items): trong thực tế, các thuộc tính trong CSDL không phải lúc nào cũng có vai trò như nhau. Có một số thuộc tính được chú trọng hơn và có mức độ quan trọng cao hơn hơn các thuộc tính khác. Ví dụ khi khảo sát về doanh thu hàng tháng, thông tin về thời gian đàm thoại, vùng cước là quan trọng nhiều hơn so với thông tin về phương thức gọi… Trong quá trình tìm kiếm luật, chúng ta sẽ gán thời gian gọi, vùng cước các trọng số lớn hơn thuộc tính phương thức gọi. Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên cứu đề xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa). Khai thác luật kết hợp song song (parallel mining of association rules): Bên cạnh khai thác luật kết hợp tuần tự, các nhà làm tin học cũng tập trung nghiên cứu các thuật giải song song cho quá trình phát hiện luật kết hợp. Nhu cầu song song hóa và xử lý phân tán là cần thiết bởi kích thước dữ liệu ngày càng lớn đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ của hệ thống phải được đảm bảo. Có rất nhiều thuật toán song song khác nhau đã đề xuất để có thể không phụ thuộc vào phần cứng. Bên cạnh những nghiên cứu về những biến thể của luật kết hợp, các nhà nghiên cứu còn chú trọng đề xuất những thuật toán nhằm tăng tốc độ quá trình tìm kiếm tập phổ biến từ CSDL. Số hóa bởi Trung tâm Học liệu 20 http://www.lrc-tnu.edu.vn/