Báo cáo Phá dữ liệu ứng dụng trong đào tạo

1 TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệp Đề tài: PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO 2 MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... 5 DANH MỤC CÁC HÌNH VẼ ............................................................................ 6 LỜI MỞ ĐẦU .................................................................................................... 7 Chương 1 .......................................................................................................... 9 TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC............ 9 1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu ...................................... 9 1.2. Các bước trong quá trình phát hiện tri thức[7]........................................ 10 1.3. Kiến trúc hệ thống khai phá dữ liệu........................................................ 12 1.4.1. Cơ sở dữ liệu quan hệ ...................................................................... 12 1.4.2. Kho dữ liệu ...................................................................................... 12 1.4.3. Cơ sở dữ liệu không gian ................................................................. 13 1.4.4. Cơ sở dữ liệu văn bản ...................................................................... 13 1.4.5. Dữ liệu Web..................................................................................... 13 3 1.5. Các phương pháp khai phá dữ liệu ......................................................... 13 1.5.1. Các thành phần của giải thuật khai phá dữ liệu ................................ 14 1.5.2. Phương pháp suy diễn / quy nạp ...................................................... 16 1.5.3. Phương pháp ứng dụng K-láng giềng............................................... 16 1.5.4. Phương pháp sử dụng cây quyết định và luật[14]............................. 17 1.5.5. Phương pháp phát hiện luật kết hợp ................................................. 18 1.6. Các nhiệm vụ trong khai phá dữ liệu ...................................................... 19 1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa..................................... 20 1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu ............................................... 20 1.6.3. Phát hiện sự sai lệch......................................................................... 21 1.6.4. Phát hiện luật kết hợp....................................................................... 21 1.6.5. Mô hình hoá sự phụ thuộc................................................................ 21 1.6.6. Mô hình hoá nhân quả...................................................................... 22 1.6.7. Phân cụm, nhóm .............................................................................. 22 1.6.8. Phân lớp........................................................................................... 23 1.6.9. Hồi quy ............................................................................................ 23 1.6.10. Tổng hợp ....................................................................................... 23 1.7. Các thách thức và giải pháp cơ bản ........................................................ 24 1.7.1. Thách thức ....................................................................................... 24 1.7.2. Một số giải pháp .............................................................................. 25 1.8. Kết luận.................................................................................................. 25 Chương 2 ........................................................................................................ 26 CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP ..................................................................... 26 2.1. Lý thuyết về luật và luật kết hợp ............................................................ 26 2.1.1. Luật thừa.......................................................................................... 26 2.1.2. Luật kết hợp ..................................................................................... 27 2.1.3. Một số tính chất của luật kết hợp[6] ................................................. 30 2.1.4. Phát biểu bài toán khai phá luật kết hợp[8] ...................................... 31 2.1.5. Một số hướng tiếp cận trong khai phá luật kết hợp........................... 32 2.2. Các đặc trưng của luật kết hợp ............................................................... 34 2.2.1. Không gian tìm kiếm của luật .......................................................... 34 4 2.2.2. Độ hỗ trợ của luật ............................................................................ 36 2.3.Một số giải thuật cơ bản khai phá các tập phổ biến ................................. 36 2.3.1.Kỹ thuật BFS .................................................................................... 37 2.3.2.Kỹ thuật DFS .................................................................................... 44 2.5. Thuật toán AIS ....................................................................................... 44 2.5.1. Bài toán đặt ra.................................................................................. 44 2.5.2. Thuật toán AIS................................................................................. 45 2.6. Thuật toán SETM ................................................................................... 47 2.6.1. Bài toán đặt ra.................................................................................. 47 2.6.2. Thuật toán SETM ............................................................................ 47 2.7. Thuật toán CHARM[9] .......................................................................... 50 2.7.1. Tư tưởng thuật toán CHARM .......................................................... 50 2.7.1.1. Cơ sở lý thuyết .......................................................................... 50 2.7.2.2. Bài toán đặt ra............................................................................ 52 2.7.2. Thuật toán CHARM......................................................................... 53 2.8. Kết luận.................................................................................................. 56 Chương 3 ........................................................................................................ 57 ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO .............. 57 3.1. Bài toán.................................................................................................. 57 3.2. Đặc tả dữ liệu ......................................................................................... 58 3.3. Chương trình thử nghiệm minh họa........................................................ 63 3.4. Kết luận .............................................................................................. 66 KẾT LUẬN...................................................................................................... 67 PHỤ LỤC ........................................................................................................ 68 TÀI LIỆU THAM KHẢO ................................................................................ 77 5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt ADO Activate X Data Object BFS Breadth First Search Tìm kiếm theo bề rộng Ck Ck Tập các K – itemset ứng cử Conf confidence Độ tin cậy CSDL Database Cơ sở dữ liệu DFS Depth First Search Tìm kiếm theo độ sâu DW Data Warehouse Kho dữ liệu Item item Khoản mục Itemset itemset Tập các khoản mục K- itemset K- itemset Tập gồm K mục KDD Knowledge Discovery and Data Mining Kỹ thuật phát hiện tri thức và khai phá dữ liệu Lk Lk Tập các K - itemset phổ biến Minconf Minimum Confidence Độ tin cậy tối thiểu Minsup Minimum Support Độ hỗ trợ tối thiểu MOLAP Multidimensional OLAP Phân tích đa chiều trực tuyến OLAP On Line Analytical Processing Phân tích trực tuyến ROLAP Relational OLAP Phân tích quân hệ trực tuyến Record record Bản ghi Supp suppport Độ hỗ trợ TID Transaction Indentification Định danh giao tác SQL Structured Query Language Ngôn ngữ vấn đáp chuẩn SQO Sematics Query Optimization TC Tính chất 6 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Các bước trong quá trình phát hiện tri thức ....................................................11 Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu ................................................................12 Hình 1.3: Ví dụ mô hình khai phá dữ liệu .......................................................................15 Hình 1.4: Ví dụ cây quyết định.........................................................................................17 Hình 1.5: Ví dụ về luật kết hợp ........................................................................................19 Hình 1.6: Ví dụ Form nhập liệu........................................................................................24 Bảng 2.1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D...............................................28 Bảng 2.2 : Các tập phổ biến trong cơ sở dữ liệu ở bảng 1 với độ hỗ trợ tối thiểu 50% 28 Hình 2.3: Dàn cho tập I = {1,2,3,4} .................................................................................34 Hình 2.4: Cây cho tập I = {1, 2, 3, 4} ..............................................................................35 Hình 2.5: Hệ thống hóa các giải thuật ..............................................................................37 Bảng 2.6: Ví dụ thuật toán Apriori ...................................................................................42 Bảng 2.7. Ví dụ thuật toán AIS ........................................................................................46 Bảng 2.8: Ví dụ thuật toán SETM ....................................................................................50 Bảng 2.9: Tập các giao dịch trong ví dụ thuật toán CHARM ........................................53 Bảng 2.10: Tập mục phổ biến trong ví dụ minh hoạ thuật toán CHARM .....................54 Hình 2.11: Thuật toán CHARM sắp xếp theo thứ tự từ điển..........................................54 Hình 2.12: Sắp xếp theo độ hỗ trợ tăng dần ....................................................................55 Hình 3.1: Trường Đại học Dân lập Hải phòng ................................................................57 Bảng 3.2: Ví dụ CSDL điểm của sinh viên......................................................................59 Bảng 3.3: Dữ liệu đã chuyển đổi từ dạng số sang dạng logic.........................................60 Bảng 3.4: Bảng ký hiệu tên các môn học.........................................................................63 Hình 3.5: Sơ đồ quan hệ CSDL điểm sinh viên ..............................................................63 Hình 3.6: Giao diện chương trình chính ..........................................................................63 Hình 3.7: Phần kết nối CSDL ...........................................................................................64 Hinh 3.8: Form cập nhật điểm sinh viên..........................................................................64 Hình 3.9: Form cập nhật thêm sinh viên..........................................................................64 Hình 3.10: Phần dữ liệu đã được mã hoá.........................................................................65 Hình 3.11: Phần tạo luật kết hợp dùng thuật toán Apriori ..............................................65 Hình 3.12: Phần mô phỏng thuật toán với dữ liệu nhập vào từ bàn phím .....................66 7 LỜI MỞ ĐẦU Ngày nay công nghệ thông tin luôn luôn phát triển và không ngừng đổi mới, cùng với sự phát triển đó là các hệ thống thông tin phục vụ việc tự động hoá trong các lĩnh vực của con người cũng được triển khai vượt bậc. Điều đó đã tạo ra những dòng dữ liệu khổng lồ. Nhiều hệ quản trị CSDL mạnh cũng đã ra đời giúp chúng ta khai thác hiệu quả nguồn tài nguyên đã thu thập được. Với lượng dữ liệu, thông tin thu thập được ngày càng nhiều như vậy đòi hỏi chúng ta phải trích rút ra những thông tin tiềm ẩn nhằm đưa ra các quyết định đúng đắn trong công việc. Xuất phát từ thực tiễn đó, vào những năm cuối của thế kỷ 20 khai phá dữ liệu ra đời. Đây là một lĩnh vực nghiên cứu khá mới mẻ của ngành khoa học máy tính và khai phá tri thức (KDD). Nó đã thu hút sự quan tâm của rất nhiều người ở các lĩnh vực khác nhau như : các hệ CSDL, thống kê, nhận dạng, máy học, trí tuệ nhân tạo... Khai phá dữ liệu sử dụng các công cụ phân tích dữ liệu như: truy vấn, báo cáo, dịch vụ phân tích trực tuyến (OLAP, ROLAP, MOLAP) để tìm ra các mẫu có giá trị trong kho dữ liệu. Khai phá dữ liệu đã và đang được ứng dụng thành công vào các ngành thương mại, tài chính, kinh doanh, sinh học, y học, giáo dục, viễn thông... Khai phá luật kết hợp từ CSDL lớn được khởi xướng từ năm 1993, nó đã và đang được nghiên cứu, phát triển mạnh vì khả năng tìm được các luật có ích, từ đó có những dự báo giúp chúng ta có kế hoạch các hướng phát triển cho tương lai. Việc khai phá luật kết hợp ứng dụng vào trong công tác đào tạo còn chưa được nghiên cứu và ứng dụng tối đa. Để từng bước nâng cao khả năng ứng dụng khai phá luật kết hợp vào giải quyết những công việc trong công tác đào tạo đạt hiệu quả cao, bằng những kinh nghiệm thực tế và qua kiến thức thu thập được trong những năm theo học tại khoa Công nghệ Thông tin trường đại học Quốc Gia Hà Nội, nghiên cứu giảng dạy tại trường đại học Dân Lập Hải Phòng, chính vì vậy tác giả chọn đề tài “KHAI PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO”. Nội dung chính của đề tài là đi sâu vào tìm hiểu một số thuật toán khai phá luật kết hợp và áp dụng thuật toán kinh điển Apriori ứng dụng trong công tác đào tạo của trường đại học Dân lập Hải Phòng. Kết quả nghiên cứu sẽ cung cấp các thông tin hỗ trợ cho sinh viên lựa chọn môn học, ngành học, hướng nghiên cứu, đồng thời hỗ trợ cán bộ làm công tác tư vấn đào tạo, cán bộ phòng đào tạo được thuận lợi hơn trong công tác đào tạo. Nội dung của luận văn gồm 3 chương và phần phụ lục: 8 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC. Chương này đề cập đến các giai đoạn của quy trình phát hiện tri thức, các vấn đề chính của khai phá dữ liệu, các phương pháp, các nhiệm vụ trong khai phá dữ liệu. Chương 2: CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP. Chương này trình bày một số vấn đề chính của khai phá luật kết hợp: lý thuyết luật kết hợp, bài toán khai phá và phát hiện luật kết hợp, các phương pháp phát hiện luật kết hợp, một số thuật toán điển hình giải quyết vấn đề, phân tích độ phức tạp của bài toán. Chương 3: ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO. Nội dung của chương là áp dụng kỹ thuật khai phá luật kết hợp vào trong đào tạo của trường Đại học Dân lập Hải phòng. Ứng dụng này nhằm đưa ra dự báo hỗ trợ cho công tác đào tạo của trường. Phần phụ lục đưa ra một số modul của chương trình ứng dụng. Cuối cùng là kết luận lại những kết quả đạt được của đề tài và hướng phát triển trong tương lai. 9 Chương 1 TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu Việc dùng các phương tiện tin học để tổ chức và khai thác các CSDL đã được phát triển từ những năm 60, nhiều CSDL đã được tổ chức, phát triển và khai thác ở mọi qui mô và khắp các lĩnh vực hoạt động của xã hội. Với sự phát triển mạnh mẽ của máy tính và các mạng viễn thông, người ta đã xây dựng được nhiều hệ CSDL lớn tập trung hoặc phân tán, nhiều hệ quản trị CSDL mạnh với các công cụ phong phú và thuận tiện giúp con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu trong các hoạt động kinh tế xã hội. Tuy nhiên từ đầu thập niên 90, con người mới thực sự bước vào giai đoạn bùng nổ thông tin. Nhờ áp dụng các công nghệ và kỹ thuật mới, rất nhiều các thiết bị tiên tiến ra đời có khả năng hỗ trợ đắc lực cho việc thu thập, lưu trữ và khai thác dữ liệu. Các thiết bị lưu trữ với tốc độ cao, dung lượng lớn như đĩa từ, CD/DVD-ROM, thiết bị điều khiển từ xa, vệ tinh nhân tạo… đã giúp con người hàng ngày thu thập được hàng chục, hàng trăm gigabytes dữ liệu. Sự phát triển nhanh chóng của một lượng lớn dữ liệu được thu thập và lưu trữ trong các CSDL lớn đã vượt ra ngoài khả năng của con người có thể hiểu được chúng nếu không có những công cụ hỗ trợ tốt. Kết quả là, dữ liệu thu thập được trong một lượng lớn CSDL đã trở thành những đống dữ liệu mà ít khi được xem xét đến. Do vậy, việc đưa ra những quyết định thường không dựa vào những thông tin hoặc dữ liệu thu thập được mà chỉ dựa vào nhận thức, suy đoán của người đưa ra quyết định. Đơn giản là vì họ không có những công cụ giúp cho việc lấy ra những tri thức từ lượng lớn dữ liệu. Tình huống này đã đặt chúng ta trong hoàn cảnh nhiều dữ liệu nhưng thiếu thông tin, thiếu tri thức. Với một khối lượng lớn dữ liệu như vậy rõ ràng là các phương pháp thủ công truyền thống áp dụng để phân tích dữ liệu như chia bảng không còn là phù hợp nữa. Và có một kỹ thuật mới ra đời đó là kỹ thuật khai phá tri thức trong cơ sở dữ kiệu (Knowledge Discovery in Database) gọi tắt là KDD. Thuật ngữ KDD được đưa ra vào năm 1989 với ý nghĩa là thực hiện các xử lý để tìm ra các tri thức trong CSDL và mục đích nhấn mạnh đến các ứng dụng ở mức cao hơn của khai phá dữ liệu (data mining). Khai phá dữ liệu thường được dùng trong các lĩnh vực thống kê, đánh giá dữ liệu và các hệ thống quản lý dữ liệu. 10 Chúng ta có thể phân biệt một cách tương đối giữa phát hiện tri thức trong CSDL và khai phá dữ liệu. KDD để chỉ một quá trình tổng thể bao gồm nhiều bước nhằm phát hiện ra các tri thức hữu ích trong dữ liệu còn khai phá dữ liệu chỉ tập trung vào việc ứng dụng các thuật toán nhằm phát hiện các mẫu từ dữ liệu mà không có thêm các bước của quá trình KDD như bước kết hợp với tri thức đã có hoặc bước đánh giá kết quả thu được. Các bước thêm vào này rất cần thiết để thấy rõ được rằng những thông tin thu được từ dữ liệu là thực sự hữu ích. Đối với quá trình khai phá dữ liệu, nhiều khi các mẫu thu được nhờ thực hiện một ứng dụng nào đó không có giá trị hoặc không phục vụ cho mục đích nào. Như vậy, một quá trình phát hiện tri thức từ dữ liệu được đặc trưng bằng các bước lặp chính là lặp lại các ứng dụng theo một thuật toán khai phá dữ liệu cụ thể và hiểu các mẫu thu được từ thuật toán này Định nghĩa: “KDD là một quá trình không tầm thường của việc xác định các mẫu mới, có giá trị, có hiệu quả sử dụng và cơ bản hiểu được trong cơ sở dữ liệu”.[7] Còn các nhà thống kê thì xem Khai phá dữ liệu như là một qui trình phân tích được thiết kế để thăm dò một lượng cực lớn các dữ liệu nhằm phát hiện ra các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm đưọc bằng cách áp dụng các mẫu đã phát hiện được cho các tập con mới của dữ liệu. Qui trình này bao gồm ba giai đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức/kiểm chứng. 1.2. Các bước trong quá trình phát hiện tri thức[7] Phát hiện tri thức bao gồm nhiều giai đoạn được lặp đi lặp lại nhiều lần mà không cần phân biệt từng bước trong quá trình thực hiện. 1. Giai đoạn 1: Hình thành, xác định và định nghĩa bài toán. Là việc tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. Bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng cùng với bản chất của dữ liệu. 2. Giai đoạn 2: Thu thập và tiền xử lý ( xử lý thô). Bước này còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (dữ liệu dư thừa), làm sạch dữ liệu, xử lý và khắc phục vấn đề thiếu hoặc thừa dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết. Bước này thường chiếm nhiều thời gian nhất (bước quan trọng) trong toàn bộ quy trình phát hiện tri thức. 11 Mẫu và mô hình Dữ liệu đã được biến đổi Dữ liệu đã được tiền xử lý Kho dữ liệu Mục tiêu dữ liệu Tri thức và cách sử dụng Khai phá dữ liệu Hình thành, xác định và định nghĩa vấn đề Biến đổi dữ liệu Thu thập và tiền xử lý Giải thích kết quả và đánh giá mẫu Internet,... 3. Giai đoạn 3: Biến đổi dữ liệu, chọn lựa một số phương pháp. Phân loại (Classification), hồi quy (Regression), phân nhóm (Clustering), quy nạp, tổng hợp kết quả (Summarization). Hình 1.1: Các bước trong quá trình phát hiện tri thức 4. Giai đoạn 4: Khai phá dữ liệu, hay nói cách khác là trích chọn, chiết xuất ra các mẫu hay các mô hình tiềm ẩn dưới các dữ liệu có ý nghĩa, hiểu được. Giai đoạn này rất quan trọng, bao gồm các công đoạn như: chức năng, nhiệm vụ và mục đích khai phá dữ liệu, dùng phương pháp khai phá nào là thích hợp?. 5. Giai đoạn 5: Giải thích kết quả và đánh giá các mẫu hay mô hình. Các mẫu và mô hình này là kết quả của giai đoạn 3 trong quy trình. Đây là công đoạn không thể thiếu trong quá trình khai phá tri thức. 6. Giai đoạn 6: Hiểu và sử dụng tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trên tất cả các lần thực hiện. Tóm lại: Quá trình phát hiện tri thức từ trong kho dữ liệu (KDD – Knowledge Discovery Database) là quá trình chiết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 12 1.3. Kiến trúc hệ thống khai phá dữ liệu Kiến trúc của hệ thống khai phá dữ liệu có thể chia thành các thành phần chính như trong hình. 1- Kho dữ liệu: là một tập các cơ sở dữ liệu, các công cụ làm sạch dữ liệu và tích hợp dữ liệu có thể thực hiện trên chúng. 2- Cơ sở tri thức: là yếu tố tri thức được dùng để đánh giá các mẫu kết quả khai phá được. Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu 3- Kỹ thuật khai phá: là các công cụ để thực hiện các nhiệm vụ: mô tả, kết hợp, phân lớp, phân nhóm dữ liệu. 4- Công cụ đánh giá mẫu: gồm một số modul sử dụng các độ đo và tương tác với các modul khai phá dữ liệu để tập trung vào các thuộc tính cần quan tâm. 5- Biểu diễn dạng đồ hoạ: modul này giao tiếp giữa người dùng và hệ thống khai phá dữ liệu. 1.4. Các loại dữ liệu sử dụng 1.4.1. Cơ sở dữ liệu quan hệ Các CSDL quan hệ là một trong những kho chứa phổ biến nhiều thông tin nhất và là dạng dữ liệu chủ yếu để nghiên cứu khai phá dữ liệu. 1.4.2. Kho dữ liệu 13 Kho dữ liệu (Data Warehouse) chứa thông tin thu thập từ nhiều nguồn, được lưu trữ trong một lược đồ hợp nhất. Kho dữ liệu được tổ chức theo các chủ đề và cung cấp tính lịch sử, tổng hợp cao với cấu trúc vật lý là CSDL quan hệ hoặc khối dữ liệu nhiều chiều. Kho dữ liệu là môi trường tốt nhất cho khai phá dữ liệu hoạt động hiệu quả. 1.4.3. Cơ sở dữ liệu không gian CSDL không gian chứa các thông tin có quan hệ về mặt không gian như CSDL địa lý, CSDL ảnh vệ tinh và y học…Dữ liệu được biểu diễn theo dạng mã vạch, chứa bản đồ bit n- chiều hoặc bản đồ các điểm pixel. Bản đồ có thể được biểu diễn thành dạng vectơ trong đó đường phố, cầu, toà nhà, hồ…Khai phá dữ liệu có thể phát hiện mẫu bằng cách mô tả đặc trưng của ngôi nhà gần một vị trí nào đó như hồ chẳng hạn. Nói chung, các khối dữ liệu không gian có thể tổ chức thành cáu trúc đa chiều và phân cấp. 1.4.4. Cơ sở dữ liệu văn bản CSDL văn bản chứa các mô tả từ như các câu, đoạn. Có nhiều CSDL văn bản có tính phi cấu trúc như các trang Web hoặc nửa cấu trúc như các message mail, trang XML…Để phát hiện các đặc tả chung của các lớp đối tượng, từ khoá, nội dung liên quan, đối tượng văn bản…các phương pháp khai phá dữ liệu cần tích hợp với các kỹ thuật lấy thông tin và xây dựng từ điển, từ điển đồng nghĩa… 1.4.5. Dữ liệu Web Dữ liệu Word Wide Web cung cấp các dịch vụ thông tin trực tuyến toàn cầu là cơ hội phong phú với nhiều thách thức mới cho khai phá dữ liệu. Khai phá dữ liệu Web với các mục đích như:  Khai phá nội dung Web để phát hiện ra các tri thức từ nội dung các trang Web  Khai phá cấu trúc Web: phát hiện mô hình nền tảng cấu trúc liên kết.  Khai phá sử dụng Web: phát hiện thông tin từ các phiên làm việc truy nhập của người dùng. Khi nắm bắt được các mẫu tra cứu trang có thể sắp xếp lại các liên kết và đưa các quảng cáo vào những trang mà người dùng thường quan tâm 1.5. Các phương pháp khai phá dữ liệu Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mực đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong 14 đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác định. Có thể kể ra đây một vài phương pháp như: sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị trung bình, phát hiện luật kết hợp, … Các phương pháp trên có thể được phỏng theo và được tích hợp vào các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách thức về mặt hiệu quả và quy mô. 1.5.1. Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm. Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu tả các mẫu có thể khai thác được. Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có mô hình chính xác cho dữ liệu. Tuy nhiên, nếu mô hình quá lớn thì khả năng dự đoán của học máy sẽ bị hạn chế. Như thế sẽ làm cho việc tìm kiếm phức tạp hơn cũng như hiểu được mô hình là không đơn giản hoặc sẽ không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Ví dụ: mô tả cây quyết định sử dụng phân chia các nút theo một trường dữ liệu, chia không gian đầu vào thành các siêu phẳng song song với trục các thuộc tính. Phương pháp cây quyết định như vậy không thể khai phá được dữ liệu dạng công thức “X = Y” dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy, việc quan trọng là người phân tích dữ liệu là cần phải hiểu đầy đủ các giả thiết miêu tả. Một điều cũng khá quan trọng là người thiết kế giải thuật cũng phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở lên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với tham số được xác định dựa trên dữ liệu (trong một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập các dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS, … một số giải thuật học máy (ví dụ như cây quyết định và các quyết định học có thầy khác), 15 mạng neuron, suy diễn hướng tình huống (case based reasoning), các kỹ thuật phân lớp. Hình 1.3: Ví dụ mô hình khai phá dữ liệu Kiểm định mô hình (model evaluation): Là việc đánh giá, ước lượng các mô hình chi tiết, chuẩn trong quá trình xử lý và phát hiện tri thức với sự ước lượng có dự báo chính xác hay không và có thoả mãn cơ sở logic hay không? Ước lượng phải được đánh giá chéo (cross validation) với việc mô tả đặc điểm bao gồm dự báo chính xác, tính mới lạ, tính hữu ích, tính hiểu được phù hợp với các mô hình. Hai phương pháp logic và thống kê chuẩn có thể sử dụng trong mô hình kiểm định. Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: tìm kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. Việc tìm kiếm không cần thiết đối với một số bài toán khá đơn giản: các đánh giá tham số tối ưu có thể đạt được bằng các cách đơn giản hơn. Đối với các mô hình chung thì không có các cách này, khi đó giải thuật “tham lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phương pháp giảm gradient trong giải thuật lan truyền ngược (backpropagation) cho các mạng neuron. Tìm kiếm mô hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: mô tả mô hình bị thay đổi tạo nên một họ các mô hình. Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản (closed form) không dễ đạt được. 16 1.5.2. Phương pháp suy diễn / quy nạp Một CSDL là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp. Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong CSDL. Ví dụ như toán tử liên kết áp dụng cho bảng quan hệ, bảng đầu chứa thông tin về các nhân viên và phòng ban, bảng thứ hai chứa các thông tin về các phòng ban và các trưởng phòng. Như vậy sẽ suy ra được mối quan hệ giữa các nhân viên và các trưởng phòng. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. Phương pháp quy nạp: phương pháp quy nạp suy ra các thông tin được sinh ra từ CSDL. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong CSDL. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật. 1.5.3. Phương pháp ứng dụng K-láng giềng Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là rất có ích đối với việc phân tích dữ liệu. Việc dùng các miêu tả này, nội dung của vùng lân cận được xác định, trong đó các bản ghi gần nhau trong không gian được xem xét thuộc về lân cận (hàng xóm – láng giềng) của nhau. Khái niệm này được dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần, trong đó K là số láng giềng được sử dụng. Phương pháp này rất hiệu quả nhưng lại đơn giản. Ý tưởng thuật toán học K- láng giềng gần là “thực hiện như các láng giềng gần của bạn đã làm”. Ví dụ: Để dự đoán hoạt động của cá thể xác định, K-láng giềng tốt nhất của cá thể được xem xét, và trung bình các hoạt động của các láng giềng gần đưa ra được dự đoán về hoạt động của cá thể đó. Kỹ thuật K-láng giềng gần là một phương pháp tìm kiếm đơn giản. Tuy nhiên, nó có một số mặt hạn chế giới hạn là phạm vi ứng dụng của nó. Đó là thuật toán này có độ phức tạp tính toán là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu. Vấn đề chính liên quan đến thuộc tính của bản ghi. Một bản ghi gồm nhiều thuộc tính độc lập, nó bằng một điểm trong không gian tìm kiếm có số chiều lớn. Trong các không gian có số chiều lớn, giữa hai điểm bất kỳ hầu như có cùng khoảng cách. Vì thế 17 mà kỹ thuật K-láng giềng không cho ta thêm một thông tin có ích nào, khi hầu hết các cặp điểm đều là các láng giềng. Cuối cùng, phương pháp K-láng giềng không đưa ra lý thuyết để hiểu cấu trúc dữ liệu. Hạn chế đó có thể được khắc phục bằng kỹ thuật cây quyết định. 1.5.4. Phương pháp sử dụng cây quyết định và luật[14] Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của quá trình xây dựng mô hình sẽ cho ra một cây quyết định. Cây này được sử dụng trong quá trình phân lớp các đối tượng dữ liệu chưa biết hoặc đánh giá độ chính xác của mô hình. Tương ứng với hai giai đoạn trong quá trình phân lớp là quá trình xây dựng và sử dụng cây quyết định. Quá trình xây dựng cây quyết định bắt đầu từ một nút đơn biểu diễn tất cả các mẫu dữ liệu. Sau đó, các mẫu sẽ được phân chia một cách đệ quy dựa vào việc lựa chọn các thuộc tính. Nếu các mẫu có cùng một lớp thì nút sẽ trở thành lá, ngược lại ta sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm cơ sở để phân chia các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa chọn, ta tạo ra các nhánh tương ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình trên cho tới khi tạo ra được cây quyết định, tất cả các nút triển khai thành lá và được gán nhãn. Hình 1.4: Ví dụ cây quyết định Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau được thỏa mãn:  Tất cả các mẫu thuộc cùng một nút.  Không còn một thuộc tính nào để lựa chọn. 18  Nhánh không chứa mẫu nào. Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng nhiều bộ nhớ. Lượng bộ nhớ sử dụng tỷ lệ thuận với kích thước của mẫu dữ liệu huấn luyện. Một chương trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài song lại có nhược điểm về tốc độ thực thi. Do vậy, vấn đề tỉa bớt cây quyết định trở nên quan trọng. Các nút lá không ổn định trong cây quyết định sẽ được tỉa bớt. Kỹ thuật tỉa trước là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa. 1.5.5. Phương pháp phát hiện luật kết hợp Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A => B. Cho một lược đồ R={A1, …, Ap} các thuộc tính với miền giá trị {0,1}, và một quan hệ r trên R. Một luật kết hợp trên r được mô tả dưới dạng X=>B với X  R và B  R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật như sau: nếu một bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc tính B cũng là 1 trong cùng bản ghi đó. Ví dụ như ta có tập CSDL về các điểm của sinh viên, các dòng tương ứng với các các sinh viên, các cột tương ứng với các điểm các môn học thì giá trị 1 tại ô (Trần Thu Hà, lập trình C đạt 8) xác định rằng sinh viên đó cũng đạt (Trần Thu Hà, hệ điều hành đạt 7). Cho W  R, đặt s(W, r) là tần số xuất hiện của W trong r được tính bằng tỷ lệ của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật X=>B trong r được định nghĩa là s(X  {B}, r) còn gọi là độ hỗ trợ của luật, độ tin cậy của luật là s(X  {B}, r)/s(X, r). Ở đây X có thể gồm nhiều thuộc tính, B là giá trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn trước khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm có kích thước tăng theo hàm mũ của số lượng các thuộc tính ở đầu vào. Do vậy cần phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm các luật kết hợp. Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X=>B sao cho tần số của luật không nhỏ hơn ngưỡng σ cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng θ cho trước. Từ một CSDL ta có thể tìm được hàng nghìn và thậm chí hàng trăm nghìn các luật kết hợp. 19 Ta gọi một tập con X  R là thường xuyên trong r nếu thỏa mãn điều kiện s(X,r) ≥ σ. Nếu biết tất cả các tập thường xuyên trong r thì việc tìm kiếm các luật rất dễ dàng. Vì vậy, giải thuật tìm kiếm các luật kết hợp trước tiên đi tìm tất cả các tập thường xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách ghép dần các tập thuộc tính dựa trên mức độ thường xuyên. Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất thích hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giải thuật tìm kiếm các luật kết hợp tạo ra số luật ít nhất phải bằng với số các tập phổ biến và nếu như một tập phổ biến có kích thước K thì phải có ít nhất là 2 K tập phổ biến. Thông tin về các tập phổ biến được sử dụng để ước lượng độ tin cậy của các tập luật kết hợp. Hình 1.5: Ví dụ về luật kết hợp 1.6. Các nhiệm vụ trong khai phá dữ liệu Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong CSDL (KDD) theo yêu cầu nhằm đáp ứng những đòi hỏi trong nhiều lĩnh vực khác nhau, việc phát hiện tri thức cũng trở lên đa dạng hơn. Do đó, nhiệm vụ của phát hiện tri thức trong CSDL cũng trở lên phong phú và có thể phát hiện rất nhiều kiểu tri thức khác nhau. Một trong các bước đầu tiên trong quá trình phát hiện tri thức trong CSDL là quyết định xem loại kiến thức nào mà thuật toán phát hiện tri thức trong CSDL cần phải kết xuất từ dữ liệu. Do đó, việc phân loại và so sánh các kiểu nhiệm vụ phát hiện tri thức trong CSDL là vấn đề đáng quan tâm nhằm tạo ra một hệ thống phát hiện tri thức trong CSDL hữu ích. Ta sẽ xem xét một số kiểu nhiệm vụ phát hiện tri thức sau: 20 1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa Các luật tối ưu truy vấn CSDL thông thường thực hiện một phép biến đổi cú pháp, hay sắp xếp lại thứ tự của các phép toán quan hệ trong một truy vấn và sản sinh ra một truy vấn hiệu quả hơn. Các phép biến đổi này thường dựa trên lý thuyết đại số quan hệ. Các luật được biến đổi trả lại cùng một câu trả lời như câu truy vấn ban đầu ở bất kỳ trạng thái nào của CSDL. Ngược lại, luật tối ưu truy vấn ngữ nghĩa biến đổi các câu truy vấn ban đầu thành một truy vấn mới bằng cách thêm vào hoặc xoá đi các mối liên kết bằng việc sử dụng các tri thức CSDL ngữ nghĩa bao gồm các ràng buộc về tính toàn vẹn và sự phụ thuộc hàm để sản sinh ra các câu truy vấn hiệu quả hơn. Như vậy câu truy vấn đã biến đổi cũng trả lại cùng câu trả lời giống như câu truy vấn ban đầu trong bất kỳ trạng thái nào của CSDL thoả mãn kiến thức về ngữ nghĩa được sử dụng trong phép biến đổi. Các hệ thống phát hiện luật SQO có thể được chia thành ba lớp: Các hệ thống hướng truy vấn (hệ thống báo cáo) trong đó thuật toán phát hiện tri thức trong CSDL nhằm phục vụ các truy vấn CSDL thực của người dùng; 1. Các hệ thống hướng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán phát hiện tri thức trong CSDL chủ yếu phục vụ sự phân bổ dữ liệu trong trạng thái hiện thời của CSDL; 2. Các hệ thống lại kết hợp các đặc tính của cả hệ thống hướng truy vấn và hướng dữ liệu. Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện tri thức khác, là việc chọn các thuộc tính để tổng hợp một SQO cần phải tính đến chi phí liên quan như dùng phương pháp truy cập nào và sơ đồ chỉ số trong hệ quản trị CSDL. Việc này là cần thiết để tiết kiệm thời gian xử lý truy vấn. Một thuật toán phát hiện tri thức trong CSDL loại này đòi hỏi phải xem xét tối ưu chi phí. 1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này thường được thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn. Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu này. Sự phụ thuộc CSDL được sử dụng trong thiết kế và duy trì một CSDL. Phương pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu nhiệm vụ của khai phá dữ liệu. 21 1.6.3. Phát hiện sự sai lệch Nhiệm vụ này nhằm phát hiện sự sai lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình sai lệch hay dùng là mô hình sai lệch theo thời gian và sai lệch nhóm. Sai lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Sai lệch theo nhóm là sự khác nhau không chờ đợi giữa dữ liệu trong hai tập con dữ liệu, ở đây tính đến cả trường hợp tập con này thuộc trong tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so với toàn bộ đối tượng không. Theo cách này, các sai sót dữ liệu hay sự sai lệch so với giá trị thông thường được phát hiện. 1.6.4. Phát hiện luật kết hợp Ta xét một ví dụ: Xét một tập các mặt hàng trong một giỏ mua hàng. Vấn đề đặt ra là tìm những mối liên quan giữa các mặt hàng trong giỏ hàng. Một cách chi tiết hơn, xét một tập các thuộc tính nhị phân với một tập các bộ, mỗi bộ được gọi là một giỏ. Các thuộc tính nhị phân được gọi là các mục hay các mặt hàng trong giỏ mà mỗi mục chỉ nhận một trong hai giá trị đúng hoặc sai tuỳ thuộc vào khách hàng có mua mặt hàng đó trong giao dịch hay không. Trên thực tế, loại dữ liệu này rất phổ biến và được gọi là dữ liệu giỏ. Chúng thường được thu thập thông qua công nghệ mã số, mã vạch trong các hoạt động kinh doanh siêu thị. Một giao dịch có thể chứa một số khoản mục, tập hợp tất cả các khoản mục sẽ thuộc vào một không gian T nào đó mà mỗi giao dịch khi đó là một tập con của T. Ta cần phát hiện những mối tương quan quan trọng hoặc mối quan hệ, mối kết hợp trong số các khoản mục chứa trong các giao dịch của một dữ liệu nào đó sao cho sự xuất hiện của một số khoả mục nào đó trong giao dịch sẽ kéo theo sự xuất hiện của một số khoản mục khác trong cùng một giao dịch đó. Một luật kết hợp là một quan hệ có dạng X  Y, trong đó, X và Y là tập các khoản mục và X  Y = . Mỗi luật kết hợp được đặc trưng bởi độ hỗ trợ (sup) và độ tin cậy (conf). sup được định nghĩa như tỷ lệ số giỏ thoả mãn cả X và Y trên toàn bộ số giỏ. conf được xác định như tỷ lệ số giỏ thoả mãn cả X và Y trên toàn bộ chỉ thoả mãn X. Ta sẽ tìm hiểu luật kết hợp ở phần sau. 1.6.5. Mô hình hoá sự phụ thuộc Nhiệm vụ này liên quan đến việc phát hiện sự phụ thuộc trong số các thuộc tính. Những phụ thuộc này thường được biểu thị dưới dạng luật “nếu thì”: “nếu (tiên đề là đúng) thì (kết luận là đúng)”. Về nguyên tắc, cả tiên đề và kết luận của luật đều có thể 22 là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiên đề thường là nhóm các giá trị thuộc tính và kết luận chỉ là một giá trị thuộc tính. Hệ thống có thể phát hiện các luật với phần kết luận nhiều thuộc tính. Điều này khác với luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do người dùng chỉ ra trong kết luận. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng Bayes. Đó là một đồ thị có hướng, không chu trình. Các nút biểu diễn các thuộc tính và trọng số của cung biểu diễn độ mạnh của sự phụ thuộc giữa các nút đó. 1.6.6. Mô hình hoá nhân quả Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong thuộc tính. Các luật nhân quả cũng là các luật “nếu - thì” giống các luật phụ thuộc, nhưng mạnh hơn. Luật phụ thuộc đơn giản chỉ ra một mối tương hỗ giữa tiên đề và kết luận của luật mà không có ý nghĩa nhân quả trong quan hệ này. Do đó, cả tiên đề và kết luận có thể quan hệ dưới sự ảnh hưởng của một biến thứ ba, tức là một thuộc tính hoặc có ở trong tiên đề hoặc có ở trong kết luận. Luật nhân quả không chỉ chỉ ra mối tương quan giữa tiên đề và kết luận mà còn cho biết tiên đề thực sự tạo ra kết luận và mối quan hệ giữa hai thành phần này là trực tiếp. Tập các mối quan hệ nhân quả có thể được biểu diến bằng đồ thị nhân quả. Thuật toán phát hiện các luật nhân quả CAUDISCO áp dụng các phép kiểm tra sự độc lập thống kê của từng cặp thuộc tính. Sau đó, đối với các thuộc tính phụ thuộc lẫn nhau, thuật toán sẽ xác định mối quan hệ có là xác thực, tiềm năng hay chỉ là một liên kết giả tạo, không phụ thuộc vào tập các điều kiện thoả mãn bởi quan hệ nhân quả. Các quan hệ nhân quả cần phụ thuộc vào thời gian theo nghĩa là nguyên nhân trước kết quả (kết luận). Nguyên nhân và kết quả đều có ít nhất một sự kiện thời gian đi kèm và thời gian của kết quả phải đi sau thời gian của nguyên nhân. Mặc dù yếu tố thời gian làm rõ ý nghĩa nhân quả nhưng hệ thống thường khó phân biệt các liên kết giả tạo. 1.6.7. Phân cụm, nhóm Một nhiệm vụ của các hệ thống phát hiện tri thức là phân tích các đối tượng dữ liệu dạng như các giỏ hàng mà không quan tâm tới lớp của chúng. Các hệ thống này phải tự phát hiện ra các lớp và sinh ra một sơ đồ phân nhóm của tập dữ liệu đó. Tuy nhiên, chất lượng của việc phân nhóm này là một vấn dề khó có thể xác định được. Bài toán phân nhóm xác định các nhóm dựa vào quan hệ nhiều - nhiều, tức là bất kỳ thuộc tính nào cũng có thể được sử dụng để xác định các nhóm và để dự báo các giá trị thuộc tính khác. Điều này trái với cách xác định nhiều - một liên quan đến 23 nhiệm vụ phân lớp các đối tượng, trong đó, một thuộc tính được xem như lớp và tất cả các thuộc tính khác được sử dụng để phán đoán giá trị cho thuộc tính lớp. 1.6.8. Phân lớp Trong nhiệm vụ phân lớp, mỗi bộ dữ liệu theo dạng giỏ mua hàng thuộc về một lớp nào đó đã được xác định trước. Các bộ dữ liệu bao gồm tập các thuộc tính dự báo và một thuộc tính phân lớp cụ thể. Lớp của bộ được chỉ ra bởi giá trị của thuộc tính lớp mà người dùng xác định trước. Ta xét ví dụ sau: Giả sử, mỗi bộ dữ liệu biểu diễn các thông tin về nhân viên, trong đó các thuộc tính dự báo là tuổi, giới tính, trình độ học vấn,... của nhân viên đó và thuộc tính phân lớp là trình độ lãnh đạo của nhân viên. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa các thuộc tính dự báo và thuộc tính phân lớp, từ đó sử dụng mối quan hệ này để dự báo lớp cho các bộ dữ liệu mới khác cùng khuôn dạng. Trong trường hợp những kiến thức được phát hiện biểu diễn dưới dạng các luật thì khuôn dạng của luật có thể là: “nếu các thuộc tính dự báo của một bộ dữ liệu thoả mãn các điều kiện của tiên đề, thì bộ dữ liệu đó có lớp chỉ ra trong kết luận”. 1.6.9. Hồi quy Về khái niệm, nhiệm vụ hồi quy tương tự như phân lớp. Điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, các phương pháp mô hình hoá cũng được sử dụng, chẳng hạn như cây quyết định, trong đó nút lá là mô hình tuyến tính phát sinh tập các lớp giả (pseudo - class) có giá trị thuộc tính đích tương tự nhau, sau đó sử dụng phương pháp quy nạp để thay thế các lớp trong luật quy nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các bộ dữ liệu theo luật. 1.6.10. Tổng hợp Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả (hoặc hầu hết) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp. Các mô tả đặc trưng thể hiện dưới dạng luật có dạng sau: ”nếu một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiên đề, thì bộ dữ liệu đó có tất cả các thuộc tính đã nêu trong kết luận”. Cần lưu ý là các luật này có những đặc trưng khác biệt so với luật 24 phân lớp. Luật phát hiện đặc trưng cho một lớp chỉ sản sinh khi các bộ dữ liệu đã thuộc về lớp đó. 1.7. Các thách thức và giải pháp cơ bản 1.7.1. Thách thức Cơ sở dữ liệu rất lớn: các CSDL với hàng trăm trường và bảng, hàng triệu bản ghi, chiếm nhiều gigabyte và terabyte. Kích thước chiều lớn: Tập dữ liệu lớn có nhiều thuộc tính và biến nên số chiều của bài toán tăng làm cho không gian tìm kiếm mẫu tăng rất nhanh. Nếu giả sử có 3 mẫu thuộc tính, mỗi thuộc tính có 2 giá trị thì số các bản ghi là 23=8 và số mẫu sẽ là 3*3*3=27. Nếu có p thuộc tính, mỗi thuộc tính có d giá trị thì số mẫu dữ liệu là dp Biến động dữ liệu và tri thức: Sự thay đổi nhanh chóng dữ liệu làm cho các mẫu đã phát hiện trước đây có thể không còn đúng. Hơn nữa các độ đo biến trong các CSDL ứng dụng có thể thay đổi, bị xoá, hoặc tăng lên theo độ đo mới. Các giải pháp có thể là các phương pháp gia tăng để cập nhật các mẫu. Thiếu dữ liệu và thừa dữ liệu: Đây là vấn đề có thể nói rất khó khăn cho việc khai phá dữ liệu. Thông thường các hệ tác nghiệp chỉ quan tâm đến các dữ liệu cần để giải quyết các hoạt động tác nghiệp hàng ngày, các dữ liệu khác chưa chú trọng thu thập hoặc người thao tác không nhập vào, nếu họ cảm thấy chưa dùng để làm gì. Hầu hết các thiết kế dữ liệu trong các hệ tác nghiệp về thuế cũng như bảo hiểm các số liệu về tài chính, tài sản, thu nhập, vốn, doanh số, hoặc khai báo chi tiết tình trạng sức khoẻ thường được bỏ qua mặc dù các thiết kế dữ liệu cũng như các Form nhập liệu đều đã được cài đặt. Hình 1.6: Ví dụ Form nhập liệu 25 1.7.2. Một số giải pháp  Có thuật toán hiệu quả và đủ mềm dẻo để tăng bộ nhớ.  Lấy ví dụ mẫu: Chọn lọc các bộ dữ liệu đặc trưng và tốt nhất.  Giảm chiều: Chọn lọc các thuộc tính thích hợp cho mục đích khai phá.  Tận dụng các xử lý song song: Hiện nay, do giá thành các thiết bị phần cứng không cao lắm, có thể áp dụng các giải pháp song song cho việc khai phá dữ liệu: Phân chia nhiệm vụ. dữ liệu cho nhiều bộ xử lý thực hiện đồng thời. 1.8. Kết luận Nội dung chương đã tìm hiểu quá trình phát hiện tri thức và các vấn đề khai phá dữ liệu. Phát hiện tri thức (KDD) là một quá trình rút ra tri thức từ dữ liệu mà trong đó khai phá dữ liệu là giai đoạn chủ yếu. Khai phá dữ liệu là nhiệm vụ khám phá các mẫu có ích từ số lượng lớn dữ liệu, ở đó dữ liệu có thể được lưu trữ trong các CSDL, kho dữ liệu hoặc kho lưu trữ thông tin khác. Nó là một lĩnh vực còn mới mẻ, phát triển từ các lĩnh vực như hệ thống CSDL, kho dữ liệu, thống kê, học máy, trực quan hoá dữ liệu…Khám phá tri thức bao gồm nhiều giai đoạn trong đó giai đoạn khai phá dữ liệu là giai đoạn quan trọng nhất. Chương này đã tóm tắt một số phương pháp phổ biến dùng để khai phá dữ liệu và phân tích việc khai phá dữ liệu. Trong các phương pháp khai phá dữ liệu, phát hiện các luật kết hợp là một lĩnh vực đang được quan tâm nghiên cứu nhiều. Phần này sẽ được trình bày rõ hơn trong chương sau. 26 Chương 2 CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 2.1. Lý thuyết về luật và luật kết hợp 2.1.1. Luật thừa a. Định nghĩa: Xét luật r: XY thuộc tập các luật {R} của một cơ sở tri thức. Luật r được gọi là luật thừa nếu với các luật còn lại thuộc tập R {r} nếu chúng ta có thể suy ra một luật r: XY Một định nghĩa khác: Gọi R: tập luật của cơ sở tri thức; r thuộc R: XY; (X)R- {r}: tập các mệnh đề suy ra từ X bằng các luật thuộc R-{r}; luật r: XY thuộc R gọi là thừa nếu Y thuộc (X)R-{r} Ví dụ: Xét tập luật sau:  R1: AB  R2: BC  R3: CD  R4: AD Trong các luật trên, ta thấy luật R4: AD là thừa bởi vì: Từ R1, R2, R3, ta có: ABCD Thuật toán xác định (X)R-{r} 1. Bước 1: Ket qua:= X; 2. Bước 2: Với mọi r thuộc R, nếu vế trái r thuộc kết quả thì ket qua:= ket qua  Vephai(r) 3. Bước 3: Lặp lại bước 2 cho đến khi nào ket qua không thay đổi nữa. Khi đó ta có (X)R-{r} b. Thuật toán loại bỏ luật thừa: Tư tưởng thuật toán gồm các bước sau: 1. Bước 1: t R = R {r}, từ định nghĩa của luật thừa trên, chúng ta có thuật toán kiểm tra luật r: X Y có thừa trong tập các luật R hay không: 27 2. Bước 2: Xác định (X)R = (Aj| Aj là các mệnh đề có thể suy diễn từ X dựa trên tập luật R) 3. Bước 3 : Kiểm tra nếu Y thuộc (X)R hay không:  nếu đúng: thì luật r là thừa đối với tập R  ngược lại: thì luật r không thừa đối với tập R Giải thuật chính loại bỏ luật thừa: Bước 1: Xét luật r trong tập luật R, kiểm tra r có thừa đối với tập R - {r} không? Bước 2 : Nếu thừa thì R= R {r}; lặp lại bước 1 với luật khác. Bước 3: Lặp lại cho đến khi không còn bỏ luật nào nữa. 2.1.2. Luật kết hợp Cho một tập I = {I1, I2,...,Im} là tập gồm m khoản mục (item), còn được gọi là các thuộc tính (attribute). Các phần tử trong I là phân biệt nhau. X  I được gọi là tập mục (itemset). Nếu lực lượng của X bằng k (tức là |X| = k) thì X được gọi là k-itemset. Một giao dịch (transaction) T được định nghĩa như một tập con (subset) của các khoản mục trong I (T I). Tương tự như khái niệm tập hợp, các giao dịch không được trùng lặp, nhưng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau này, người ta đều giả thiết rằng các khoản mục trong một giao dịch và trong tất cả các tập mục (item set) khác, có thể coi chúng đã được sắp xếp theo thứ tự từ điển của các item. Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một định danh duy nhất (Unique Transasction IDentifier-TID). Nói rằng, một giao dịch T  D hỗ trợ (support) cho một tập X  I nếu nó chứa tất cả các item của X, nghĩa là X  T, trong một số trường hợp người ta dùng ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ cho X. Kí hiệu support(X) (hoặc supp(X), s(X)) là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch trong D, nghĩa là: supp(X) =   D TXDT  Ví dụ về cơ sở dữ liệu D (dạng giao dịch) : I = {A, B, C, D, E}, T = {1, 2, 3, 4, 5, 6}. Thông tin về các giao dịch cho ở bảng sau : 28 Định danh giao dịch (TID) Tập mục (itemset) 1 A B D E 2 B C E 3 A B D E 4 A B C E 5 A B C D E 6 B C D Bảng 2.1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D Tập phổ biến (frequent itemset): Support tối thiểu minsup ( 0, 1] (Minimum Support) là một giá trị cho trước bởi người sử dụng. Nếu tập mục X  I có supp(X)  minsup thì ta nói X là một tập phổ biến-frequent itemset (hoặc large itemset). Một frequent itemset được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược lại, những tập không phải frequent itemset là những tập không đáng quan tâm. Trong các trình bày sau này, ta sẽ sử dụng những cụm từ khác như “X có support tối thiểu”, hay “X không có support tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa mãn support(X)  minsupp. Ví dụ: Với cơ sở dữ liệu D cho ở bảng 1, và giá trị ngưỡng minsupp = 50% sẽ liệt kê tất cả các tập phổ biến (frequent-itemset) như sau : Các tập mục phổ biến Độ hỗ trợ (supp) tương ứng B 100% (6/6) E, BE 83% (5/6) A, C, D, AB, AE, BC, BD, ABE 67% (4/6) AD, CE, DE, ABD, ADE, BCE, BDE 50% (3/6) Bảng 2.2 : Các tập phổ biến trong cơ sở dữ liệu ở bảng 1 với độ hỗ trợ tối thiểu 50% Một số tính chất (TC) liên quan đến các frequent itemset: TC 1. support cho tất cả các subset: nếu A B, A, B là các itemset thì supp(A)  supp(B) vì tất cả các giao dịch của D support B thì cũng support A. 29 TC 2. Nếu một item A không có support tối thiểu trên D nghĩa là support(A) < minsupp thì một superset B của A sẽ không phải là một frequent vì support(B)  support(A) < minsup. TC 3. Nếu item B là frequent trên D, nghĩa là support(B)  minsup thì mọi subset A của B là frequent trên D vì support(A)  support(B) > minsup. Định nghĩa luật kết hợp: Một luật kết hợp có dạng R: X  Y, trong đó X, Y là các itemset, X, Y  I và X Y = . X được gọi là tiên đề và Y được gọi là hệ quả của luật. Một số nhận xét :  Luật X  Y tồn tại một độ hỗ trợ support - supp. Supp(X  Y) được định nghĩa là khả năng mà tập giao dịch hỗ trợ cho các thuộc tính có có trong cả X lẫn Y, nghĩa là: Support(XY) = support(XY).  Luật X  Y tồn tại một độ tin cậy c (confidence - conf). Conf c được định nghĩa là khả năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Nói cách khác c biểu thị số phần trăm giao dịch có chứa luôn Y trong số những giao dịch có chứa X.  Ta có công thức tính conf c như sau: conf(X  Y) = p(Y  I | X  I ) = )(sup )(sup )( )( Xp YXp TXp TYp     TX  Ta nói rằng, luật X Y là thoả trên D nếu với một support tối thiểu minsup và một ngưỡng cofidence tối thiểu minconf cho trước nào đó mà: Support(X  Y) ≥ minsup và confidence(X Y) ≥ minconf Chú ý rằng, nếu luật XY mà thoả trên D thì cả X và Y đều phải là các Frequent Itemset trên D và khi xét một luật có thoả hay không, thì cả support và confidence của nó đều phải quan tâm, vì một luật có thể có confidence = 100% > minconf nhưng có thể là nó không đạt support tối thiểu minsup. Khi khai phá các luật kết hợp, có 2 vấn đề chính cần phải giải quyết :  Thứ nhất, đó là độ phức tạp của giải thuật. Số lượng luật tăng theo cấp độ luỹ thừa cùng với số lượng các mục (item). Tuy nhiên, các giải thuật hiện nay có thể giảm bớt không gian tìm kiếm này dựa trên các ngưỡng tối thiểu để đánh giá độ hiệu quả của luật.  Thứ hai, các luật tốt (tối ưu) phải được lấy ra từ tập hợp các luật tìm được. Điều này rất khó bởi vì tập hợp các luật tìm được là rất lớn, trong đó số 30 lượng các luật có thể dùng được lại chiếm tỷ lệ vô cùng nhỏ. Các nghiên cứu liên quan đến vấn đề thứ hai hầu hết chú trọng vào việc giúp người dùng duyệt tập luật cũng như việc phát triển các độ đo chất lượng của luật. 2.1.3. Một số tính chất của luật kết hợp[6] Trước hết ta phải giả sử rằng với luật X  Y, X có thể là rỗng, còn Y phải luôn khác rỗng và X  Y vì nếu không thì: confidence(XY) = 1 support(X) Y)support(X   Ta có các tính chất sau : 1) Nếu X  Z và YZ là thoả trên D, thì không nhất thiết là XYZ. Để ý đến trường hợp X  Y =  và các giao dịch trên D hỗ trợ Z nếu và chỉ nếu chúng hỗ trợ X hoặc hỗ trợ Y. Khi đó support(XY) = 0 và cofidence(XY) = 0. Tương tự ta cũng có : Nếu XY và ZZ không thể suy ra XYZ. 2) Nếu luật XYZ là thoả trên D thì XZ và YZ có thể không thoả trên D. Chẳng hạn, khi Z là có mặt trong một giao dịch chỉ nếu cả X và Y đều có mặt trong giao dịch đó, nghĩa là support(XY)=support(Z). Nếu support cho X và Y lớn hơn support(XY), thì 2 luật trên sẽ không có confidence yêu cầu. Tuy nhiên, nếu XYZ là thoả trên D thì có thể suy ra XY và XZ cũng thoả trên D Vì support(XY) ≥ support(XYZ) và support(XZ) ≥ support(XYZ). 3) Nếu XY và YZ là thoả trên D thì không thể khẳng định rằng XZ cũng giữ được trên D. Giả sử T(X)T(Y)  T(Z) và confidence(XY) = confidence(YZ) = minconf. Khi đó ta có confidence(XZ) = minconf < minconf vì minconf <1, nghĩa là luật XZ không có cofidence tối thiểu. 4) Nếu luật A (L-A) không có confidence tối thiểu thì cũng không có luật nào trong các luật B (L-B) có confidence tối thiểu trong đó L-A.B là các intemset và BA. Thật vậy, theo tính chất TC1, vì BA. Nên support(B) ≥ support(A) và theo định nghĩa của confidence, ta có : confidence(B (L-B)) =  )(sup )(sup Bport Lport )(sup )(sup Aport Lport <minconf. 31 Cũng vậy, nếu luật (L-C) C là thoả trên D, thì các luật (L-K) K với KC và K  cũng thoả trên D. 2.1.4. Phát biểu bài toán khai phá luật kết hợp[8] Bài toán khai phá luật kết hợp: Có thể diễn đạt một bài toán khai phá luật kết hợp như sau: Cho một tập các item I, một cơ sở dữ liệu giao dịch D, ngưỡng support tối thiểu minsup, ngưỡng confidence tối thiểu minconf, tìm tất cả các luật kết hợp XY trên D sao cho: support(XY) minsup và confidence(XY) minconf. Bài toán khai phá luật kết hợp có thể dùng nhiều thuật toán để khai phá nhưng nhìn chung là các bài toán này đều phải qua 2 giai đoạn chính sau : Khai phá tất cả các tập phổ biến-Frequent itemset (Large itemset) Số lượng các tập phổ biến có khả năng tương đương với kích thước mũ của tập các item, trong đó hàm mũ tăng theo số các item. Phương pháp cơ bản trong mỗi thuật toán là tạo một tập các itemset gọi là ứng cử viên (candidate) với hi vọng rằng nó là frequent. Điều mà bất kì thuật toán nào cũng phải quan tâm là làm sao để tập các ứng cử viên này càng nhỏ càng tốt vì nó liên quan chi phí bộ nhớ để lưu trữ các tập các ứng cử viên này chi phí thời gian cho việc kiểm tra nó là một tập phổ biến hay không. Để tìm ra những tập ứng cử viên (candidate itemset) là phổ biến (frequent) với các support cụ thể của nó là bao nhiêu thì support của mỗi tập ứng cử viên phải được đếm bởi mỗi giai đoạn trên CSDL (tức là thực hiện một phép duyệt trên từng giao dịch của cơ sở dữ liệu để tính giao dịch support cho mỗi tập ứng cử viên). Công việc khai phá các tập mục phổ biến được thực hiện lặp đi lặp lại qua một giai đoạn (pass) nhằm mục đích nhận được kết quả cuối cùng là mỗi tập mục phổ biến biểu thị tốt nhất sự tương quan giữa các item trong cơ sở dữ liệu giao dịch D. Khai phá luật kết hợp (sinh ra các luật kết hợp tốt từ các tập mục phổ biến) Sau khi xác định được tập mục phổ biến cuối cùng, người ta thực hiện tiếp thuật toán sinh ra các luật dưa trên mỗi tập mục phổ biến này đồng thời xác định luôn confidence của chúng trên cơ sở các số đếm support của mỗi tập mục phổ biến và subset của mỗi tập mục phổ biến. Với mỗi tập mục phổ biến X, mỗi subset riêng biệt của nó là được chọn như là tiền đề của luật và các item còn lại thì được đưa vào hệ quả của luật, do X chính nó là một frequent, và tất cả các subset của nó cũng là Frequent (theo tính chất 3 mục 2.1.3). Mỗi luật được sinh ra như trên có được chấp nhận hay 32 không chấp nhận còn phụ thuộc vào mức confidence tối thiểu (minconf) mà người sử dụng chỉ ra. Một luật sẽ được coi là chấp nhận nếu confidence của nó lớn hơn hoặc bằng cofidence tối thiểu này. Theo tính chất TC4, mục 2.1.3, nếu một luật là không được chấp nhận thì không có một subset nào của tiền tố của nó là có thể cân nhắc để sinh thêm các luật khác. Nói chung thì tư tưởng sinh ra luật kết hợp có thể mô tả như sau: Nếu ABCD và AB là các frequent itemset thì ta có thể xác định xem luật ABCD có được xem là chấp nhận hay không bằng cách tính confidence của nó theo định nghĩa conf = )(sup )(sup ABport ABCDport . Nếu conf  minconf thì luật được coi là chấp nhận được (để ý rằng luật là thoả mãn yếu tố support vì support (ABCD) = support(ABCD) minsup). 2.1.5. Một số hướng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai phá luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến tốc độ thuật toán, có những đề xuất nhằm tìm kiếm luật có ý nghĩa hơn… và có một số hướng chính sau đây. 1. Luật kết hợp nhị phân (binary association rule hoặc boolean association 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 dịch 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 hoá, mờ hoá, … 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%” 2. 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 hoá 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 “An toàn bảo mật thông tin [5..<7] AND đồ 33 hoạ máy tính [7.. hệ điều hành [5..<7], với độ hỗ trợ là 35%, và độ tin cậy là %”. 3. 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ô. 4. Luật kết hợp nhiều mức (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 có 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 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 hoá của dạng luật sau và tổng quát theo nhiều mức khác nhau. 5. 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 hoá 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ề một 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à : “An toàn bảo mật thông tin trung bình AND đồ hoạ máy tính khá => hệ điều hành trung bình, với độ hỗ trợ là 35%, và độ tin cậy là %”. Trong luật trên, điều kiện điểm các môn đã được mờ hoá ở mức điểm yếu kém, trung bình, khá, và giỏi. 6. 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 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 hơn nhiều 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). 7. Luật kết hợp song song (parallel mining of association rules): Bên cạnh khai phá luật kết hợp tuần tự, các nhà làm tin học cũng tập trung vào 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 hoá 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 hơn nê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. 34 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. Ngoài ra, còn có một số hướng nghiên cứu khác về khai phá luật kết hợp như: khai phá luật kết hợp trực tuyến, khai phá luật kết hợp được kết nối trực tuyến đến các kho dữ liệu đa chiều (Multidimensional data, data warehouse) thông qua công nghệ OLAP (Online Analysis Processing), MOLAP (multidimensional OLAP), ROLAP (Relational OLAP), ADO (Active X Data Object) for OLAP..v..v.. 2.2. Các đặc trưng của luật kết hợp 2.2.1. Không gian tìm kiếm của luật Như đã giải thích trên đây, ta phải tìm tất cả các itemset thỏa ngưỡng minsupp. Với các ứng dụng thực tiễn, việc duyệt tất cả các tập con của I sẽ hoàn toàn thất bại vì không gian tìm kiếm quá lớn. Trên thực tế, sự tăng tuyến tính số lượng các item vẫn kéo theo sự tăng theo cấp lũy thừa các itemset cần xem xét. Với trường hợp đặc biệt I ={1,2,3,4}, ta có thể biểu diễn không gian tìm kiếm thành một lưới như trong hình 2.3. Hình 2.3: Dàn cho tập I = {1,2,3,4} Các tập phổ biến nằm trong phần trên của hình trong khi những tập không phổ biến lại nằm trong phần dưới. Mặc dù không chỉ ra một cách tường minh các giá trị hỗ trợ cho mỗi itemset nhưng ta giả sử rằng đường biên đậm trong hình phân chia các tập phổ biến và tập không phổ biến. Sự tồn tại của đường biên như vậy không phụ thuộc 35 vào bất kỳ cơ sở dữ liệu D và minsupp nào. Sự tồn tại của nó chỉ đơn thuần được đảm bảo bởi tính chặn dưới của itemset thỏa ngưỡng minsupp. Nguyên lý cơ bản của các giải thuật thông thường là sử dụng đường biên này để thu hẹp không gian tìm kiếm một cách có hiệu quả. Khi đường biên được tìm thấy, chúng ta có thể giới hạn trong việc xác định các giá trị hỗ trợ của các itemset phía trên đường biên và bỏ qua các itemset phía dưới đường biên. Cho ánh xạ: I  {1,…, |I|} là một phép ánh xạ từ các phần tử xI ánh xạ 1-1 vào các số tự nhiên. Bây giờ, các phần tử có thể được xem là có thứ tự hoàn toàn trên quan hệ “<” giữa các số tự nhiên. Hơn nữa, với X  I, cho X.item: {1,…,|X|}  I: n a X.itemn là một ánh xạ, trong đó X.itemn là phần tử thứ n của các phần tử xX sắp xếp tăng dần trên quan hệ “<”. n-tiền tố của một itemset X với n|X| được định nghĩa bởi P={X.itemm |1 mn}. Cho các lớp E(P), PI với E(P) = {XI | |X| = |P|+1 và P là một tiền tố của X} là các nút của một cây. Hai nút sẽ được nối với nhau bằng 1 cạnh nếu tất cả các itemset của lớp E có thể được phát sinh bằng cách kết 2 itemset của lớp cha E’, ví dụ như trong hình. Hình 2.4: Cây cho tập I = {1, 2, 3, 4} Cùng với tính chặn dưới của itemset thỏa ngưỡng minsupp, điều này suy ra: Nếu lớp cha E’ của lớp E không có tối thiểu hai tập phổ biến thì E cũng phải không chứa bất kỳ một tập phổ biến nào. Nếu gặp một lớp E’ như vậy trong quá trình duyệt cây từ trên xuống thì ta đã tiến đến đường biên phân chia giữa tập phổ biến và không phổ biến. Ta không cần phải tìm tiếp phần sau đường biên này, tức là ta đã loại bỏ E và các lớp con của E trong không gian tìm kiếm. Thủ tục tiếp theo cho phép ta giới hạn một cách có hiệu quả số lượng các itemset cần phải duyệt. Ta chỉ cần xác định các support values của các itemset mà ta đã duyệt qua trong quá trình tìm kiếm đường biên giữa tập phổ biến và tập không phổ biến. Cuối cùng, chiến lược thực sự để tìm đường biên 36 là do lựa chọn của chúng ta. Các hướng tiếp cận phổ biến hiện nay sử dụng cả tìm kiếm ưu tiên bề rộng (BFS) lẫn tìm kiếm ưu tiên chiều sâu (DFS). Với BFS, giá trị hỗ trợ của tất cả (k-1)-itemset được xác định trước khi tính giá trị hỗ trợ của k-itemset. Ngược lại, DFS duyệt đệ quy theo cấu trúc cây mô tả ở trên. 2.2.2. Độ hỗ trợ của luật Trong phần này, một itemset có khả năng là phổ biến và ta cần phải xác định độ hỗ trợ của nó trong quá trình duyệt dàn, được gọi là một itemset ứng viên. Một hướng tiếp cận phổ biến để xác định giá trị hỗ trợ của một itemset là đếm các thể hiện của nó trong cơ sở dữ liệu. Với mục đích đó, một biến đếm (counter) được tạo ra và khởi tạo bằng 0 cho mỗi itemset đang duyệt. Sau đó, quét qua tất cả các giao dịch và khi tìm được một ứng viên là tập con của một giao dịch thì tăng biến đếm của nó lên. Thông thường, tập con tạo ra và bảng tìm kiếm ứng cử viên được tích hợp và cài đặt bằng một hashtree hay một cấu trúc dữ liệu tương tự. Tóm lại, không phải tất cả các tập con của mỗi giao dịch đều được tạo ra mà chỉ những giao dịch có chứa trong các ứng viên hoặc có một tiền tố chung với ít nhất một ứng cử viên mới được tạo ra. Một cách tiếp cận khác để xác định giá trị hỗ trợ của các ứng viên là sử dụng giao tập hợp (set intersection). Một TID (Transaction IDentifier) là một khóa-biến nhận dạng giao dịch duy nhất. Với một phần tử đơn, tidlist là tập hợp của các biến nhận dạng tương ứng với các giao dịch có chứa phần tử này. Do đó, các tidlist cũng tồn tại cho mỗi itemset X và được biểu diễn bởi X.tidlist. Tidlist của một ứng viên C = X  Y xác định bởi: C.tidlist=X.tidlistY.tidlist. Các tidlist được sắp xếp theo thứ tự tăng dần để các phép giao được hiệu quả. Lưu ý rằng bằng cách dùng vùng đệm cho tidlist của các ứng viên phổ biến như là các kết quả trung gian, ta có thể tăng đáng kể tốc độ phát sinh tidlist cho các ứng viên tiếp theo. Cuối cùng, các độ hỗ trợ thực sự của ứng cử viên chính là |C.tlist|. 2.3.Một số giải thuật cơ bản khai phá các tập phổ biến Phần này sẽ trình bày và hệ thống hóa một cách ngắn gọn các giải thuật đang được dùng phổ biến hiện nay để khai phá các tập phổ biến. Chúng sẽ được thực hiện dựa vào những nguyên tắc cơ bản của phần trước. Mục tiêu của chúng ta là thể hiện được những sự khác biệt giữa các cách tiếp cận khác nhau. Các giải thuật mà ta xem xét trong bài này được hệ thống hóa như hình vẽ 2.5. Các giải thuật được phân loại dựa vào việc: a) Duyệt theo không gian tìm kiếm (BFS, DFS) 37 b) Xác định giá trị hỗ trợ của tập item (itemset) c) Ngoài ra, một giải thuật có thể dùng một số các tối ưu khác để tăng tốc thêm. Hình 2.5: Hệ thống hóa các giải thuật 2.3.1.Kỹ thuật BFS Giải thuật phổ biến nhất của loại này là giải thuật Apriori, trong đó có trình bày tính chặn dưới của itemset thỏa ngưỡng minsupp. Giải thuật Apriori tạo ra việc sử dụng các tính chất này bằng việc tỉa bớt những ứng viên thuộc tập không phổ biến trước khi tính độ phổ biến của chúng. Cách tối ưu có thể thực hiện được vì các giải thuật tìm kiếm ưu tiên theo chiều rộng (BFS) bảo đảm rằng các giá trị hỗ trợ của các tập của một ứng viên đều được biết trước. Giải thuật Apriori đếm tất cả các ứng viên có k phần tử trong một lần đọc cơ sở dữ liệu. Phần cốt lõi của bài toán là xác định các ứng viên trong mỗi giao dịch. Để thực hiện được mục đích này phải dựa vào một cấu trúc gọi là hashtree. Các item trong mỗi giao dịch được dùng để đi lần xuống trong cấu trúc hashtree. Bất cứ khi nào tới được nút lá của nó, nghĩa là ta đã tìm được một tập các ứng viên có cùng tiền tố được chứa trong giao dịch đó. Sau đó các ứng viên này sẽ được thực hiện tìm kiếm trong giao dịch mà nó đã được mã hóa trước thành ma trận bit. Trong trường hợp thành công biến đếm các ứng viên trong cây được tăng lên. Giới thiệu bài toán: Apriori là thuật toán được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993. Bài toán được phát biểu: Tìm t có độ hỗ trợ s thỏa mãn s  s0 và độ tin cậy c  c0 (s0, c0 là hai ngưỡng do người dùng xác định và s0=minsupp, c0 38 =minconf). Ký hiệu Lk tập các tập k - mục phổ biến, Ck tập các tập k-mục ứng cử (cả hai tập có: tập mục và độ hỗ trợ). Bài toán đặt ra là: Tìm tất cả các tập mục phổ biến với minsupp nào đó. Sử dụng các tập mục phổ biến để sinh ra các luật kết hợp với độ tin cậy minconf nào đó. Quá trình thực hiện (duyệt):  Thực hiện nhiều lần duyệt lặp đi lặp lại, trong đó tập (k-1) - mục được sử dụng cho việc tìm tập k-mục. Lần thứ nhất tìm tất cả các độ hỗ trợ của các mục, xác định mục phổ biến (mục thoả mãn độ hỗ trợ cực tiểu-minsupp). Giả sử tìm được L1-mục phổ biến.  Các lần duyệt còn lại: Bắt đầu kết quả tìm được bước trước nó, sử dụng các tập mục mẫu (L1) sinh ra các tập mục phổ biến tiềm năng (ứng cử) (giả sử L2), tìm độ hỗ trợ thực sự. Mỗi lần duyệt ta phải xác định tập mục mẫu cho lần duyệt tiếp theo.  Thực hiện lặp để tìm L3,..., Lk cho đến khi không tìm thấy tập mục phổ biến nào nữa. Chú ý: Ứng dụng Lk-1 để tìm Lk bao gồm hai bước chính: 1. Bước kết nối: tìm Lk là tập k-mục ứng cử được sinh ra bởi việc kết nối Lk-1 với chính nó cho kết quả là Ck. Giả sử L1, L2 thuộc Lk-1. Ký hiệu Lij là mục thứ j trong Li. Điều kiện là các tập mục hay các mục trong giao dịch có thứ tự. Bước kết nối như sau: Các thành phần Lk-1 kết nối (nếu có chung k-2-mục đầu tiên) tức là:(L1[1]=L2[1])  (L1[2]=L2[2]) ...  (L1[k-2]=L2[k-2])  (L1[k- 1]=L2[k-1]). 2. Bước tỉa: Ck là tập chứa Lk (có thể là tập phổ biến hoặc không) nhưng tất cả tập k-mục phổ biến được chứa trong Ck. Bước này, duyệt lần hai CSDL để tính độ hỗ trợ cho mỗi ứng cử trong Ck sẽ nhận được Lk. Tuy nhiên để khác phục khó khăn, giải thuật Apriori sử dụng các tính chất: 1- Tất cả các tập con khác rỗng của một tập mục phổ biến là phổ biến; 2 - Nếu L là tập mục không phổ biến thì mọi tập chứa nó không phổ biến. Mô phỏng giải thuật Apriori: Như trên đã nói, các thuật toán khai phá Frequent Itemset phải thiết lập một số giai đoạn (pass) trên CSDL. Trong giai đoạn đầu tiên, người ta đếm support cho mỗi tập riêng lẻ và xác định xem tập nào là phổ biến (nghĩa là có support ≥ minsup). Trong mỗi giai đoạn tiếp theo, người ta bắt đầu với tập các tập phổ biến đã tìm được trong 39 giai đoạn trước để lại sinh ra tập các tập mục có khả năng là phổ biến mới (gọi là tập các ứng cử viên - candidate itemset) và thực hiện đếm support cho mỗi tập các ứng cử viên trong tập này bằng một phép duyệt trên CSDL. Tại điểm kết của mỗi giai đoạn, người ta xác định xem trong các tập ứng viên này, tập nào là phổ biến và lập thành tập các tập phổ biến cho giai đoạn tiếp theo. Tiến trình này sẽ được tiếp tục cho đến khi không tìm được một tập phổ biến nào mới hơn nữa. Để tìm hiểu các thuật toán, ta giả sử rằng, các item trong mỗi giao dịch đã được sắp xếp theo thứ tự từ điển (người ta sử dụng khái niệm từ điển ở đây để diễn đạt một thứ tự quy ước nào đó trên các item của cơ sở dữ liệu). Mỗi bản ghi - record của cơ sở dữ liệu D có thể coi như là một cặp trong đó TID là định danh cho giao dịch. Các item trong một itemset cũng được lưu theo thứ tự từ điển, nghĩa là nếu kí hiệu k item cử một k-itemset c là c[1],c[2],…,c[k], thì c[1]<c[2]<…<c[k]. Nếu c=X.Y và Y là một m-itemset thì Y cũng được gọi là m-extension (mở rộng) của X. Trong lưu trữ, mỗi itemset có một trường support-count tương ứng, đây là trường chứa số đếm support cho itemset này. Thuật toán Apriori Các kí hiệu:  Lk: Tập các k-mục phổ biến (large k-itemset) (tức tập các itemset có support tối thiểu và có lực lượng bằng k). Mỗi phần tử của tập này có 2 trường: itemset và support-count.  Ck: Tập các candidate k-itemset (tập các tập k-mục ứng cử viên). Mỗi phần tử trong tập này cũng có 2 trường itemset và support-count. Nội dung thuật toán Apriori được trình bày như sau:  Input: Tập các giao dịch D, ngưỡng support tối thiểu minsup  Output: L- tập mục phổ biến trong D  Thuật toán : 1. L1={large 1-itemset} //tìm tất cả các tập mục phổ biến: nhận được L1 2. for (k=2; Lk-1  ; k++) do 3. begin 4. Ck=apriori-gen(Lk-1); //sinh ra tập ứng cử viên từ Lk-1 5. for (mỗi một giao dịch TD) do 6. begin 7. CT = subset(Ck, T); //lấy tập con của T là ứng cử viên trong Ck 8. for (mỗi một ứng cử viên c CT) do 9. c.count++; //tăng bộ đếm tần xuất 1 đơn vị 10. end; 11. Lk = {c  Ck| c.count  minsup} 40 12. end; 13. return kLk Trong thuật toán này, giai đoạn đầu đơn giản chỉ là việc đếm support cho các item. Để xác định tập 1-mục phổ biến (L1), người ta chỉ giữ lại các item mà support của nó lớn hơn hoặc bằng minsup. Trong các giai đoạn thứ k sau đó (k>1), mỗi giai đoạn gồm có 2 pha. Trước hết các large(k-1)-itemset trong tập Lk-1được sử dụng để sinh ra các candidate itemset Ck, bằng cách thực hiện hàm Apriori_gen. Tiếp theo CSDL D sẽ được quét để tính support cho mỗi ứng viên trong Ck. Để việc đếm được nhanh, cần phải có một giải pháp hiệu quả để xác định các ứng viên trong Ck là có mặt trong một giao dịch T cho trước. Vấn đề sinh tập candidate của Apriori – Hàm Apriori_gen: Hàm Apriori_gen với đối số là Lk-1(tập các large(k-1)-itemset) sẽ cho lại kết quả là một superset, tập của tất cả các large k – itemset. Sơ đồ sau là thuật toán cho hàm này.  Input: tập mục phổ biến Lk-1 có kích thước k-1  Output: tập ứng cử viên Ck  Thuật toán : 1. function apriori-gen(Lk-1: tập mục phổ biến có kích thước k-1) 2. Begin 3. For (mỗi L1  Lk-1) do 4. For (mỗi L2  Lk-1) do 5. begin 6. If ((L1[1]=L2[1])  (L1[2]=L2[2]) ...  (L1[k-2]=L2[k-2])  (L1[k- 1]=L2[k-1])) then c = L1  L2; // kết nối L1 với L2 sinh ra ứng cử viên c 7. If has_infrequent_subset(c, Lk-1) then 8. remove (c) // bước tỉa (xoá ứng cử viên c) 9. else Ck = Ck  {c}; kết tập c vào Ck 10. end; 11. Return Ck; 12. End; Hàm kiểm tra tập con k-1 mục của ứng cử viên k-mục không là tập phổ biến: 1. function has_infrequent_subset(c: ứng cử viên k-mục; Lk-1 tập phổ biến k-1 mục) 2. Begin //sử dụng tập mục phổ biến trước 3. For (mỗi tập con k-1 mục s của c) do 4. If s  Lk-1 then return TRUE; 5. End; Có thể mô tả hàm Apriori_gen trên theo lược đồ sau:  Input: tập các large(k-1)- itemset Lk-1 41  Output: tập candidate k-itemset Ck  Thuật toán: Hàm Apriori-gen() //bước nối 1. insert into Ck 2. select p.item1, p.item2,..., p.itemk-1, q.itemk-1 3. from Lk-1p, Lk-1q 4. where p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1<q.itemk-1 //bước cắt tỉa: 5. for (mọi tập mục c  Ck) do 6. for (mọi (k-1) tập con s của c( do 7. if (s  Lk-1) then 8. delete c khỏi Ck; Với nội dung trên, ta thấy hàm này có 2 bước: 1. Bước nối (join step): Bước này nối Lk-1 với Lk-1. Trong bước này, cho rằng các item của các itemset đã được sắp xếp theo thứ tự từ điển. Nếu có k-2 item đầu tiên (gọi là phân tiền tố) của hai(k-1)-itemset i1và i2(i1  i2) nào đó mà giống nhau thì ta khởi tạo một candidate k-itemset cho Ck bằng cách lấy phần tiền tố này hợp với 2 item thứ k-1 của i1 và i2 (có thể phải sắp lại thứ tự cho các item này). Điều kiện p.itemk-1 <q.itemk-1 đơn giản chỉ là việc tránh k-itemset trùng lặp được đưa vào Ck. 2. Bước cắt tỉa (prune step): Đây là bước tiếp theo sau bước join. Trong bước này, ta cần loại bỏ tất cả các k-itemset cCk mà chúng tồn tại một(k-1)- subset không có mặt trong Lk-1. Giải thích điều này như sau: giả sử s là một(k-1)-subset của c mà không có mặt trong Lk-1. Khi đó, support (s)<minsup. Mặt khác, vì c s nên support(s)<minsup. Vậy c không thể là một large-itemset, nó cần phải loại bỏ khỏi Ck. Ví dụ : Giả sử tập các item I = {A,B, C, D, E} và cơ sở dữ liệu giao dịch: D = {, , ,}. Với minsup = 0.5 (tức tương đương 2 giao dịch). Khi thực hiện thuật toán Apriori trên ta có sơ đồ sau: 42 Bảng 2.6: Ví dụ thuật toán Apriori D (CSDL) TID Các mục 1 {A, C, D} 2 {B, C, E} 3 {A, B, C, E} 4 {B, E} C1 1 - itemset Count-support {A} 2 - 50% {B} 3 – 75% {C} 3 – 75% {D} 1 - 25% {E} 3 - 75% Quét toàn bộ D Xóa bỏ mục có support < minsup C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Tỉa L1 1 - itemset Count-support {A} 2 - 50% {B} 3 – 75% {C} 3 – 75% {E} 3 - 75% Kết nối L1 & L1 L2 2 - itemset Count-support {A, C} 2 – 50% {B, C} 2 – 50% {B, E} 3 – 75% {C, E} 2 – 50% Kết nối L2 & L2 Tỉa C3 3 - itemset Count- support {B, C, E} 2 - 50% Quét toàn bộ D C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Quét toàn bộ D C2 2 - itemset Count-support {A, B} 1 – 25% {A, C} 2 – 50% {A, E} 1 – 25% {B, C} 2 – 50% {B, E} 3 – 75% {C, E} 2 – 50% Xóa bỏ mục có support < minsup Xóa bỏ mục có support < minsup L3 3 - itemset Count- support {B, C, E} 2 - 50% 3 - itemset {B, C, E} 3 - itemset {B, C, E} 43 Một số biến thể của giải thuật Apriori Giải thuật Apriori_TID là phần mở rộng theo hướng tiếp cận cơ bản của giải thuật Apriori. Thay vì dựa vào cơ sở dữ liệu thô, giải thuật AprioriTID biểu diễn bên trong mỗi giao dịch bởi các ứng viên hiện hành. 1. L1= {Large 1-itemset}; 2. C’1 = Database D; 3. for (k=2; Lk-1  ; k++) do 4. Begin 5. Ck = apriori_gen(Lk-1); 6. C’k = ; 7. for tất cả t  C’k-1 do 8. begin // xác định tập ứng viên trong Ck chứa trong giao dịch với định //danh t. Tid (Transaction Code) 9. Ct = c  Ck | (c-c[k])  t.Set_of_ItemSets ^ (c-c[k-1] t.Set_of_ItemSets 10. for những ứng viên c  Ct do c.count ++; 11. if (Ct) then C’k+= 12. end 13. Lk = c Ck | c.count  minsup; 14. End 15. return = kLk; Thuật toán này cũng sử dụng hàm apriori_gen để sinh ra các tập ứng cử viên cho mỗi giai đoạn. Nhưng thuật toán này không dùng CSDL D để đếm các support với các giai đoạn k > 1 mà sử dụng tập C’k. Mỗi phần tử của C’k có dạng , trong đó mỗi Xk là một tập phổ biến k_itemset tiềm năng trong giao dịch Tid. Khi k = 1, C’k tương ứng với D, trong đó mỗi item i được coi là một itemset {i}. Với k>1, C’k được sinh ra bởi C’k+= . Phần tử của C’k tương ứng với giao dịch t là <t.Tid, {c | c chứa trong t}>. Nếu một giao dịch không chứa bất kỳ tập ứngviên k_itemset nào thì C’k sẽ không có một điểm vào nào cho giao dịch này. Do đó, số lượng điểm vào trong C’k có thể nhỏ hơn số giao dịch trong CSDL, đặc biệt với k lớn. Hơn nữa, với các giá trị k khá lớn, mỗi điểm vào có thể nhỏ hơn giao dịch tương ứng vì một số ứng viên đã được chứa trong giao dịch. Tuy nhiên, với các giá trị k nhỏ, mỗi điểm vào có thể lớn hơn giao dịch tương ứng vì một một điểm vào trong C’k bao gồm tất cả các ứng viên k_itemset được chứa trong giao dịch. Giải thuật AprioriHybrid kết hợp cả hai hướng tiếp cận trên. Ngoài ra còn có một số các giải thuật tựa Apriori(TID), chúng được định hướng để cài trực tiếp trong SQL. 44 Giải thuật DIC là một biến thể khác nữa của giải thuật Apriori. Giải thuật DIC làm giảm đi khoảng phân biệt nghiêm ngặt giữa việc đếm và việc phát sinh các ứng viên. Bất kỳ ứng viên nào tới được ngưỡng minsupp, thì giải thuật DIC bắt đầu phát sinh thêm các ứng viên dựa vào nó. Để thực hiện điều này giải thuật DIC dùng một prefix-tree (cây tiền tố). Ngược với hashtree, mỗi nút (nút lá hoặc nút trong) của prefix-tree được gán một ứng viên xác định trong tập phổ biến. Cách sử dụng cũng ngược với hashtree, bất cứ khi nào tới được một nút ta có thể khẳng định rằng tập item đã kết hợp với nút này trong giao tác đó. Hơn nữa, việc xác định độ hỗ trợ và phát sinh ứng viên khớp nhau sẽ làm giảm đi số lần duyệt cơ sở dữ liệu. 2.3.2.Kỹ thuật DFS Giả sử việc đếm các thể hiện được thực hiện trên tập các ứng viên có kích thước hợp lý, với mỗi tập các ứng viên đó thì cần một thao tác duyệt cơ sở dữ liệu. Chẳng hạn như, giải thuật Apriori dựa vào BFS thực hiện duyệt cơ sở dữ liệu mỗi k-kích thước ứng viên một lần. Khi thực hiện tìm kiếm ưu tiên theo chiều sâu (DFS) tập ứng viên chỉ gồm chỉ gồm một nút của cây từ phần 2.2.2. Một điều hiển nhiên là nếu phải thực hiện duyệt cơ sở dữ liệu cho mỗi nút thì tổng chi phí kết quả thật khổng lồ. Vì thế việc kết hợp DFS với việc đếm các thể hiện là không thật sự thích hợp. 2.5. Thuật toán AIS 2.5.1. Bài toán đặt ra Đầu tiên, duyệt toàn bộ CSDL để tìm tất cả các tập mục phổ biến L1. Tiếp theo, chừng nào Lk-1 ! =  ( k >= 2) 1. Tìm tập các ứng cử viên bằng cách quét toàn bộ CSDL, với mỗi giao dịch, ta tìm tổ hợp chập k của các mục có trong giao dịch và xác định các mục trong tổ hợp này có là phổ biến hay không? Nếu không phải thì bỏ qua. Trái lại, ta bổ sung tổ hợp đó vào tập hợp ứng cử viên bằng cách: kiểm tra xem tổ hợp này đã nằm trong tổ hợp ứng cử viên hay chưa? Nếu chưa thì bổ sung thêm và tăng độ hỗ trợ lên 1. Trái lại, tăng độ hỗ trợ của tổ hợp tương ứng trong tập ứng cử viên thêm 1. 2. Duyệt toàn bộ các ứng cử viên, loại bỏ tất các tổ hợp có độ hỗ trợ nhỏ hơn độ hỗ trợ yêu cầu của người sử dụng. Cuối cùng ta được tất cả các tập mục phổ biến thoả mãn, có độ hỗ trợ tối thiểu lớn hơn hoặc bằng độ hỗ trợ tối thiểu mà người sử dụng yêu cầu. 45 Thuật toán hoàn toàn sử dụng chiến lược “vét cạn”, xem xét toàn bộ các tập mục phổ biến bằng cách sinh tổ hợp tập các mục và kiểm tra độ hỗ trợ. 2.5.2. Thuật toán AIS Input: CSDL minsup Output: Các tập mục phổ biến 1. L1={ Các tập mục phổ biến }. 2. For ( k=2;Lk-1  ; k++ ) 3.{ Ck = ; 4. for ( tất cả các giao dịch t D ) 5.  Lt = subSet (Lk-1; t); 6. // Các tập mục phổ biến thuộc Lk-1 chứa trong giao dịch t 7. for (tất cả các tập mục phổ biến lt Lt) 8.  Ct = tăng lt thêm một mục có trong giao dịch t; 9. for (Các ứng cử viên c  Ct ) 10. if ( c  Ck) tăng biến đếm của c thêm l cho mục tương ứng thuộc Ck 11. else add c vào Ck và tăng biến đếm tương ứng thêm 1) 12.  13.  14. Lk =  c  Ck  c.count  minsup  15.  16.return L = kLk Ví dụ minh hoạ thuật toán AIS Cho CSDL trong bảng sau. Giả sử với độ hỗ trợ tối thiểu là 2 giao dịch CSDL L1 TID Các mục Tập mục Độ hỗ trợ 100 1, 3, 4 1 2 200 2, 3, 5 2 3 300 1, 2, 3, 5 3 3 400 2, 5 5 3 C2 L2 Tập mục Độ hỗ trợ Tập mục Độ hỗ trợ 1, 3 2 1, 3 2 1, 4 1 2, 3 2 46 3, 4 1 2, 5 3 2, 3 2 3, 5 2 2, 5 3 3, 5 2 1, 2 1 1, 5 1 C3 L3 Tập mục Độ hỗ trợ Tập mục Độ hỗ trợ 1,3,4 1 2,3,5 2 2,3,5 2 1,2,3 1 1,2,5 1 1,3,5 1 C4 Tập mục Độ hỗ trợ 1,2,3,5 1 Bảng 2.7. Ví dụ thuật toán AIS Theo bước 1 của thuật toán, ta thu được L1 là tập gồm các mục có số lần xuất hiện (độ hỗ trợ) lớn hơn hoặc bằng 2. Trong các bước từ 2 đến 14 ta thu được tập ứng cử viên C2 là tập tất cả các tập có hai mục (2-itemset) và độ hỗ trợ tương ứng. Bước 13, ta thu được tập phổ biến L2 từ C2, L2 là tập các 2 itemset có độ hỗ trợ lớn hơn hoặc bằng 2. Lặp lại các bước từ 2 đến 14 ta thu được tập các ứng cử viên C3 gồm tập tất cả các tập có ba mục có độ hỗ trợ lớn hơn hoặc bằng 2. Tương tự, ta thu được C4 là tập có bốn mục L4 bằng rỗng. Như vậy, tập các tập mục phổ biến mà ví dụ trên ta thu được là: 1, 2, 3, 5, 1,3, 2,3, 2,5, 3,5, 2,3,5}. Thuật toán kết thúc. 47 2.6. Thuật toán SETM 2.6.1. Bài toán đặt ra Thuật toán SETM được đề xuất do mong muốn dùng SQL để tìm các tập mục phổ biến. 1. Đầu tiên, duyệt toàn bộ CSDL để tìm tất cả các tập mục phổ biến L1 và các mục phổ biến cùng với TID của nó L1' được xếp theo TID. 2. Tiếp theo chừng nào Lk-1!=  (k >= 2) 3. Tìm tập các ứng cử viên bằng cách quét toàn bộ CSDL, với mỗi giao dịch ta tìm tổ hợp chập k của các mục có trong giao dịch và xác định các mục cùng với TID trong tổ hợp này có thuộc L'k-1 ? Nếu không phải thì bỏ qua. Trái lại, ta bổ sung tổ hợp đó vào tập ứng cử viên đồng thời lưu một bản sao của tập mục ứng cử viên cùng với TID của nó. 4. Sắp xếp lại các ứng cử viên theo tập mục. 5. Xoá tất cả các ứng cử viên có độ hỗ trợ nhỏ hơn độ hỗ trợ do người sử dụng đề ra. Kết quả lưu vào Lk'. 6. Xếp lại Lk' theo TID. 7. Cuối cùng ta được tất cả các tập mục phổ biến thoả mãn, có độ hỗ trợ tối thiểu lớn hơn hoặc bằng độ hỗ trợ tối thiểu mà người sử dụng yêu cầu. 2.6.2. Thuật toán SETM Input: CSDL D, minsup Ouput: Tập các tập mục phổ biến. 1.L1 = Các mục phổ biến 2.L1' = Các mục phổ biến cùng các TID của nó được xếp theo TID 3.for (k=2; Lk-1  ; k ++) 4.C'k = ; 5. for (tất cả các giao dịch t  D) 6. Lt = l L'k-1 \I.TID = t.TID // Các tập có ( k-1) - itemset phổ biến có trong giao dịch t 7.for (tất cả các tập mục phổ bíên lt  Lt) 8. Ct = tăng lt thêm một mục có trong t; // Các ứng cử viên có trong t 9. C'k + =  \ c  C1 ; 10.  11.  48 12. sort C'k theo các tập mục 13. delete các mục c  C'k có c.count < minsup đưa vào L'k; 14. Lk = \ l  L'k; kết hợp với bước 13 15. sort L'k theo TID 16.  17.return L =  kLk'; Giống như AIS thuật toán SETM cũng sinh ra các ứng cử viên dựa trên các giao dịch đọc được từ CSDL. Vì thế, nó sinh ra và đếm mỗi tập mục ứng cử viên mà thuật toán AIS sinh ra. Tuy nhiên, để dùng phép nối (JOIN) chuẩn của SQL. SETM chia sự phát sinh ứng cử viên từ việc đếm. Nó lưu một bản sao của tập mục ứng cử viên cùng với TID của việc phát sinh giao dịch trong cấu trúc tuần tự (bước 9). Cuối mỗi bước, đếm độ hỗ trợ của các tập mục ứng cử viên được xác định bởi việc xếp (bước 12) và việc kết hợp lại cấu trúc tuần tự này (bước 13). SETM ghi nhớ các TID của việc phát sinh các giao dịch với các tập mục ứng cử viên. Để tránh việc thao tác trên tập con, nó dùng thông tin này để xác định các tập mục lớn chứa trong giao dịch được đọc (bước 6). L'k  C'k và thu được bởi việc xóa các ứng cử viên này mà không có độ hỗ trợ tối thiểu (bước 13). Giả sử rằng CSDL được xếp thứ tự TID, SETM có thể dễ dàng tìm các tập mục phổ biến được chứa trong một giao dịch trong bước tiếp theo bằng việc xếp L'k theo TID (bước 15). Thực tế, nó cần thăm hỏi mỗi thành viên của L'k chỉ một lần theo thứ tự TID và việc sinh ứng cử viên ở các bước 5 đến 11 có thể thực hiện nhờ phép toán Merge-join. Nhược điểm chính của thuật toán này là dựa vào số các tập ứng cử viên C'k. Khi với mỗi tập các mục ứng cử viên có một TID kết hợp với nó, nó yêu cầu nhiều không gian để lưu trữ số lượng lớn các TID. Hơn nữa, khi độ hỗ trợ của tập mục ứng cử viên được tính vào cuối mỗi bước, C'k không theo thứ tự. Vì thế, việc xếp lại các mục là cần thiết (bước 12). Sau đó, các tập mục ứng cử viên được cắt tỉa bằng việc loại bỏ các tập mục ứng cử viên không thoả mãn ràng buộc độ hỗ trợ. Một sắp xếp khác trên TID là cần thiết đối với tập kết qủa L'k (bước 15) trước khi nó có thể được sử dụng để phát sinh các ứng cử viên trong bước tiếp theo. Ví dụ minh hoạ thuật toán SETM Xét CSDL cho trong bảng sau. Giả sử với độ hỗ trợ tối thiểu là 2 giao dịch CSDL L1 L’1 TID Các mục Tập mục Độ hỗ trợ TID Tập mục 100 1, 3, 4 {1} 2 100 {1} 200 2, 3, 5 {2} 3 100 {3} 49 300 1, 2, 3, 5 {3} 3 200 {2} 400 2, 5 {5} 3 200 {3} 200 {5} 300 {1} 300 {2} 300 {3} 300 {5} 400 {2} 400 {5} C’2 L2 L’2 TID Tập mục Tập mục Độ hỗ trợ TID Tập mục 100 {1, 3} {1, 3} 2 100 {1, 3} 100 {1, 4} {2, 3} 2 200 {2, 3} 100 {3, 4} {2, 5} 3 200 {2, 5} 200 {2, 3} {3, 5} 2 200 {3, 5} 200 {2, 5} 300 {1, 3} 200 {3, 5} 300 {2,3} 300 {1, 2} 300 {2, 5} 300 {1, 3} 300 {3, 5} 300 {1, 5} 400 {2, 5} 300 {2, 3} 300 {2, 5} 300 {3, 5} 400 {2,5} L'3 L3 TID Tập mục Tập mục Độ hỗ trợ 50 200 {2, 3, 5} {2, 3, 5} 2 300 {2, 3, 5} C'4 L4 =  L'4 =  TID Tập mục 300 {1, 2, 3, 5} Bảng 2.8: Ví dụ thuật toán SETM Như vậy, tập các tập mục phổ biến mà ví dụ trên thu được là: L = 1, 2,3,5,1, 3,2, 3,2, 5,3, 5,2, 3, 5. Thuật toán kết thúc. 2.7. Thuật toán CHARM[9] 2.7.1. Tư tưởng thuật toán CHARM 2.7.1.1. Cơ sở lý thuyết Cho quan hệ nhị phân R I x X. Cho R I & R T, xét các ánh xạ: t: I  T, t(X) = {yT/xX, x R y}; i:TI, i(Y) = {xl/yY, x R y}. Một ánh xạ t(X) là tập tất cả các giao dịch chứa tập mục X, tương tự i(Y) là tập mục tất cả các giao dịch chứa tập mục Y. Định nghĩa một kết nối Galois giữa P(I) và P(T) tương ứng là các tập khả năng của l và T. Chúng ta biểu diễn cặp (X, t(X) là X x t(X) và cặp (i(X),Y) là i(Y) x Y kết nối Galois thoả mãn các thuộc tính sau (trong đó X, X1, X2  P(I) và Y,Y1, Y2  P(T):  X X2  t(X1) t(X2).  Y1 Y2  i(Y1) i(Y2).  X i(t(X)) và Y i(t(Y)). Cho s là một tập. Hàm c: P(S)P(S) là một toán tử đóng trên S nếu với  X,Y  S, c thoả mãn các thuộc tính sau:  Extention: X c(X)  Monotonicity: Nếu X  Y, thì c(X) c(Y)  Idempotency: c(c(X)) = c(X) 51  Một tập con X của S được gọi là đóng nếu c(X) =X Cho X Y và Y T. Cho Cit (X) biểu diễn ánh xạ hợp i0t(X) = i(t(X)) và Cit (Y)= i0i(Y) = t(i(Y)). Thì Cit :P(I) P(I) và Cti :P(T) P(T) là hai toán tử đóng trên các tập mục và các tập giao dịch tương ứng. Một số định nghĩa :  Định nghĩa tập mục đóng: X được gọi là tập mục đóng nếu X = Cit(X)  Định nghĩa tập mục đóng phổ biến: X được gọi là tập mục đóng phổ biến nếu X là tập mục đóng và support(X)  minsup.  Định nghĩa tập giao dịch đóng: Y là tập giao đóng nếu Y=Cit(Y) Các ánh xạ Cit và Cti là các toán tử đóng, thoả mãn 3 thuộc tính Extension, monotonicity và Idempotency. Cho f: P(I)  N là ánh xạ 1-1 từ các tập mục sang số nguyên. Với bất kỳ hai tập mục X1 và X2 nào, chúng ta nói X1  X2 f(X1)  f(X2). Hàm f xác định thứ tự toàn thể trên tập tất cả các tập mục. Ví dụ: nếu f biểu diễn theo thứ tự các từ điển, thì tập mục AC < AD. Khi với mẫu khác, nếu f sắp xếp các tập mục theo thứ tự tăng dần độ hỗ trợ của chúng, thì AD < AC nếu độ hỗ trợ của AD nhỏ hơn độ hỗ trợ của AC. Giả sử rằng chúng ta đang xử lý nhánh X1  t(X1) và chúng ta muốn kết nối với anh em của nó X2  t(X2). Điều này là X1  X2 (dưới dạng một thứ tự phù hợp f). Việc tính toán trong CHARM dựa trên các thuộc tính dưới đây: 1. Nếu t(X1) = t(X2), thì t(X1  X2) = t(X1)  t(X2) = t(X1) = t(X2). Vì thế chúng ta có sự xuất hiện của X1 bằng X1  X2 và xoá X2 được xem xét từ xa, vì bao đóng của X2 được đồng nhất với bao đóng của X1  X2. Mặt khác, chúng ta coi như X1  X2 là một tập mục hợp. 2. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2) = t(X1)  t(X2). Ở đây ta có thể thay mọi sự xuất hiện của X1 bằng X1  X2, vì nếu X1 xuất hiện trong bất kỳ giao dịch nào, thì X2 cũng xuất hiện. Nhưng khi t(X1)  t(X2), chúng ta không thể xóa X2. Nó phát sinh ra bao đóng khác. 3. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2) = t(X1)  t(X2). Trong trường hợp này, chúng ta thay thế mọi sự xuất hiện của X2 bằng X1  X2, vì bất chỗ nào X2 xuất hiện thì X1 cũng xuất hiện. Tuy nhiên, X1 là kết quả của bao đóng khác và nó phải được giữ lại. 52 4. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2)  t(X1)  t(X2). Trong trường hợp này, không được loại bỏ cả X1 và X2 dẫn đến các bao đóng khác nhau. 2.7.2.2. Bài toán đặt ra CHARM thực hiện trên cả không gian các tập phổ biến (itemset) và không gian các tập định danh (TIDset). CHARM không tìm tất cả các tập con có thể của tập mục mà thuật toán kết hợp tìm tập đóng hiệu quả hơn (bottom-up). Nếu CSDL cảu tập mục là lớn và tập mục phổ biến là dày thì CHARM duyệt cả không gian tập mục và tập định danh. Đồng thời sẽ bỏ qua nhiều mức để đi tìm tập phổ biến đóng thay cho việc tính toán nhiều tập con không đóng. Hơn nữa, CHARM sử dụng hai kỹ thuật cắt tỉa: 1. Tỉa các ứng cử viên nếu tập con của nó không phổ biến đồng thời tỉa các nhánh dựa trên tính chất không đóng (non-closure-property). 2. Bất kỳ tập không đóng nào cũng đều bị tỉa. CHARM không sử dụng cấu trúc dữ liệu cây băm (hash tree), phép toán cơ sở được sử dụng là hợp 2 tập mục và giao 2 tập định danh. Thuật toán bắt đầu bằng việc khởi tạo các nút để kiểm tra các mục đơn phổ biến và các tập giao dịch của chúng trong dòng 1. Tính toán chính được thực hiện trong CHARM-EXTEND, nó trả về các tập mục đóng phổ biến C. CHARM-EXTEND có trách nhiệm kiểm tra mỗi nhánh có khả năng. Nó rút ra mỗi cặp tập mục – tập giao dịch (itemset-tidset) trong tập nút hiện tại Node (Xi  t(Xi), dòng 3), và kết nối nó với các cặp khác mà đứng sau nó (Xi  t(Xi),dòng 5) theo thứ tự tuyệt đối f. Việc kết nối các cặp itemset-tidsset được tính toán trong. Thủ tục CHARM-PROPERTY kiểm tra tập kết quả với độ hỗ trợ yêu cầu và cũng áp dụng 4 thuộc tính được thảo luận ở trên. Lưu ý rằng thủ tục này có thể thay đổi tập nút hiện tại bằng việc xoá các cặp itemset-tidset mà đã được chứa trong các cặp đó. Nó cũng chèn các cặp phổ biến con mới được sinh ra trong tập các nút mới New. Nếu tập này khác rỗng chúng ta thực hiện lại quá trình theo chiều sâu (dòng 8). Sau đó, chúng ta chèn tập mục mở rộng có thể có X của Xi trong tập các tập mục đóng, vì nó không thể được thực hiện; ở giai đoạn này bất kỳ tập mục đóng đang chứa Xi, đã từng được sinh ra, sau đó chúng ta quay lại dòng 3 để xử lý nhánh tiếp theo (không được tỉa). Thủ tục CHARM-PROPERTY kiểm tra đơn giản nếu cặp mới là phổ biến. Sau khi nó kiểm tra mỗi cặp itemset-tidset với 4 thuộc tính cơ bản, việc mở rộng các tập mục hiện có, xoá một nhánh được gộp từ các nút hiện có, hoặc việc chèn các cặp mới trong tập nút cho bước tiếp theo (theo chiều sâu). 53 2.7.2. Thuật toán CHARM CHARM (R  I  T, minsup) 1.Nodes = {Ij  t(Ij): Ij  I  t(Ij)   minsup } 2.CHARM-EXTEND (Nodes, C) 3.For (mỗi Xi  t(Xj)  Nodes) 4. NewN =  & X = Xi 5. for (mỗi Xj  t(Xj)  Nodes với f(j) > f