Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song

tận tình chỉ dạy và hướng dẫn tôi trong suốt thời gian học tập và làm luận văn. Tôi cũng xin xin lời biết ơn chân thành đến quý Thầy giáo, cô giáo Viện Công nghệ Thông đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt quá trình học tập tại Khoa. Xin cảm ơn tất cả các anh chị em học viên Cao học khóa 5, cám ơn cán bộ công chức, giảng viên – Khoa Công nghệ Thông tin - Đại học Thái Nguyên đã tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập và làm luận văn. Cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã giúp đỡ tôi trong suốt thời gian học tập và hoàn thành luận văn này. Thái Nguyên, tháng 9 năm 2008 Tác giả Lê Thị Việt Hoa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN Tôi xin cam đoan đề tài khoa học “Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song” này là công trình nghiên cứu của bản thân tôi. Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong luận văn. Tôi xin chịu trách nhiệm về luận văn của mình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC Trang phụ bìa Trang Lời cám ơn Lời cam đoan Mục lục Danh mục các kí hiệu, các chữ viết tắt Danh mục các hình vẽ Mở đầu 1 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 3 1.1. Khái niệm 3 1.2. Kiến trúc của một hệ thống khai phá dữ liệu 3 1.3. Các giai đoạn của quá trình khai phá dữ liệu 4 1.4. Một số kỹ thuật khai phá dữ liệu 6 1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 10 1.6. Các phương pháp chính trong khai phá dữ liệu 11 1.7. Các ứng dụng của khai phá dữ liệu 13 1.8. Khai phá dữ liệu và các lĩnh vực liên quan 14 1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu 15 1.10. Kết luận chương 1 16 Chương 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU 17 2.1. Mở đầu 17 2.2 Luật kết hợp 18 2.2.1 Các khái niệm cơ bản 18 2.2.2. Khai phá luật kết hợp 21 2.2.3. Cách tiếp cận khai phá luật kết hợp 22 2.3 Luật kết hợp cơ sở 24 2.3.1 Phát hiện các tập mục phổ biến 24 2.3.2 Sinh luật kết hợp 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4. Khai phá luật kết hợp với một số khái niệm mở rộng 32 2.4.1. Giới thiệu 32 2.4.2. Khai phá luật kết hợp trọng số 32 2.4.3 Khai phá luật kết hợp tổng quát 43 2.5. Kết luận chương 2 49 Chương 3: MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP SONG SONG VÀ PHÂN TÍCH ĐÁNH GIÁ CÁC THUẬT TOÁN 50 3.1. Nguyên lý thiết kế thuật toán song song 50 3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song 51 3.2.1. Mô hình song song dữ liệu 51 3.2.2. Mô hình song song thao tác 51 3.3. Một số thuật toán khai phá luật kết hợp song song 52 3.3.1 Thuật toán Count Distribution (CD) 52 3.3.2. Thuật toán Data Distribution (DD) 54 3.3.3. Thuật toán Candidate Distribution 58 3.3.4. Thuật toán song song Fp-Growth 60 3.3.5 Thuật toán song song Eclat 65 3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán 71 3.4.1. Phân tích và đánh giá thuật toán song song 71 3.4.2. So sánh việc thực hiện các thuật toán 73 3.5. Kết luận chương 3 74 Kết luận 75 Tài liệu tham khảo 77 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC KÝ HIỆU VIẾT TẮT Ký hiệu Diễn giải Ck Tập các k-itemset ứng viên kC Tập các k-itemset ứng viên mà TID của giao dịch sinh ra liên kết với tập mục ứng viên Conf Độ tin cậy (Confidence) CFPT FP-Tree điều kiện cơ sở (Fisst conditional FP-Tree) D Cơ sở dữ liệu giao dịch Di Phần thứ i của cơ sở dữ liệu D Item Mục Itemset Tập mục I Tập các mục KDD Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) CSDL Cơ sở dữ liệu (Database) k-itemset Tập mục gồm k mục Lk Tập các k-itemset phổ biến MPI Truyền thông điệp minconf Ngưỡng tin cậy tối thiểu minsup Ngưỡng hỗ trợ tối thiểu OLAP Phân tích trực tuyến OLTP Xử lý giao dịch trực tuyến SC Số đếm hỗ trợ (support count) sup Độ hỗ trợ (support) T Giao dịch (transaction) Tid Định danh của giao dịch Tid-List Danh sách các định danh của giao dịch X ⇒Y Luật kết hợp (với X là tiền đề, Y là hệ quả) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC HÌNH VẼ VÀ BẢNG Trang Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình 3 Hình 1.2. Các bước của quy trình khai phá dữ liệu 5 Hình 1.3: Cây quyết định 7 Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu 8 Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy 8 Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu 14 Hình 2.1. Sơ đồ tổng quan của thuật toán khai phá tập mục phổ biến 24 Hình 2.2: Ví dụ thuật toán Apriori 28 Bảng 2.1.a. Thông tin của một cửa hàng bán lẻ 33 Bảng 2.1.b. Tập giao dịch D của cửa hàng 33 Hình 3.1. Mô hình song song dữ liệu 51 Hình 3.2. Mô hình song song thao tác 52 Hình 3.3. Sơ đồ thuật toán Count Distribution 52 Hình 3.4. Phát hi ện các tập mục phổ biến bởi thuật toán song song CD 54 Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution 55 Hình 3.6: Sơ đồ luồng thuật toán Data Distribution 56 Hình 3.7: Phát hi ện các tập mục phổ biến bởi thuật toán song song DD 57 Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu 61 Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở 62 Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P1 và P2 63 Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc 70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 MỞ ĐẦU Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phương pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những thông tin bổ ích. Những “ tri thức” chiết suất từ nguồn cơ sở dữ liệu trên sẽ là nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. T iến hành công việc như vậy chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả năng tích hợp các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data Warehouse) [19, 24]. Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ biến là phát hiện các luật kế t hợp. Phương pháp này nhằm tìm ra các tập thuộc tính thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính khác như thế nào. Bên cạnh đó, nhu cầu song song hóa và xử lý phân tán là rất cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp. Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 thước dữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho luật kết hợp. Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a trên các bài báo khoa học trong một số hội thảo quốc tế và các bài báo chuyên ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật toán khai phá luật kết hợp song song. Nội dung luận văn được trình bày trong 3 chương và phần kết luận Chương 1: Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu. Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp; các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp; khai phá luật kết hợp với một số khái niệm mở rộng. Chương 3: Một số phương pháp khai phá luật kết hợp song song và phân tích đánh giá các thuật toán song song . Thái Nguyên 01 tháng 10 năm 2008 Tác giả Lê Thị Việt Hoa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Khái niệm Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80, nó là quá trình tìm kiếm, khám phá d ưới nhiều góc độ khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ liệu, đối tượng bên trong CSDL, kết quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại bên trong nhưng chúng nằm ẩn ở các CSDL [3]. Về bản chất nó là giai đoạn duy nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn quan trọng nhất trong quá trình phát hiện tri thức từ CSDL, các tri thức này hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh doanh. Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong các CSDL, cụ thể hơn, đó là tiến trình lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chưa biết những thông tin hữu ích từ các CSDL lớn. 1.2. Kiến trúc của một hệ thống khai phá dữ liệu Khai phá d ữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu lớn. Khai phá d ữ liệu là quá trình chính trong khai phá tri th ức từ cơ sở dữ liệu. Kiến trúc của một hệ thống khai phá dữ liệu có các thành [2] phần như sau: Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 • CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các tập CSDL, các khi dữ liệu, các trang tính hay các dạng khác của thông tin được lưu trữ. Các kỹ thuật làm sách dữ liệu và tích hợp dữ liệu có thể được thực hiện. • Máy chủ CSDL (Database or Warehouse Server): Máy chủ có trách nhiệm lấy những dữ liệu thích hợp dựa trên những yêu cầu khám phá của người dùng. • Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để tìm kiếm hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có thể bao gồm một sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá trị thuộc tính ở các mức trừu tượng khác nhau. • Máy khai phá dữ liệu (Data mining engine): là một hệ thống khai phá dữ liệu cần phải có một tập các Modul chức năng để thực hiện công việc, chẳng hạn như kết hợp, phân lớp, phân cụm. • Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tương tác với các Modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể Modul đánh giá mẫu được tích hợp vào Modul khai phá dữ liệu, tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng. • Giao diện đồ họa cho người dùng (Graphical user interface) Bộ phận này cho phép người dùng giao tiếp với hệ thống khai phá dữ liệu. Thông qua giao diện này người dùng tương tác với hệ thống bằng cách đặc tả một yêu cầu khai phá hay một nhiệm vụ, c ung cấp thông tin trợ giúp cho việc tìm kiếm và thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. Ngoài ra bộ phận này còn cho phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu, các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau. 1.3. Các giai đoạn của quá trình khai phá dữ liệu Các thuật toán khai phá dữ liệu thường được mô tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, bước đầu tiên là thuật toán thường nạp toàn bộ tệp (file) dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 chỉ bởi nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích. Hình 1.2. Các bước của quy trình khai phá dữ liệu Quá trình xử lý khai phá dữ liệu bắt đầu bằng việc xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định dữ liệu liên quan dùng để xây dựng giải pháp. Tiếp theo là thu thập dữ liệu có liên quan và xử lý chúng thành dạng sao cho thuật toán khai phá dữ liệu có thể hiểu được. Quá trình khai phá dữ liệu [2] trải qua ba bước: Bước một: Lọc dữ liệu được thực hiện trong quá trình tiền xử lý. Công việc đầu tiên là tích hợp và chỉnh sửa dữ liệu. Khi dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Ví dụ, trong bài toán tìm quy luật mua hàng của khách hàng trong một siêu thị, ta tìm xem khách hàng thường cùng mua những mặt hàng nào để sắp xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể có nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng, nhà cung cấp, đơn giá hàng, người bán hàng… Các dữ liệu này cần cho quản lý bán hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này khỏi dữ liệu trước khi khai phá dữ liệu. Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu. Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý dữ liệu Giải thuật khai phá dữ liệu DL trực tiếp Thống kê tóm tắt Mẫu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 Bước ba: Sau xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. 1.4. Một số kỹ thuật khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp dữ liệu [24] Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000. Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai. Quá trình phân lớp dữ li ệu được thực hiện qua hai bước. Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán. Một ví dụ tiêu biểu về cây quyết định: Hình 1.3: Cây quyết định Trong hình 1.3 là một cây quyết định cho lớp mua laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là Yes hay No. Sau khi mô hình này được xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực. Phân nhóm dữ liệu [13, 24] Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu. Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá trình nhóm nhữn g đối tượng vào trong những lớp tương đương, đến những đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những chức năng giống nhau. Thông thường những sự giống nhau về định lượng như khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia trong lĩnh vực của mình. Tuổi 30-35 >35 Yes Sinh viên Giáo sư Yes No Yes No TID Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị trường. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận lợi. Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tương ứng cho việc mua nhà, mua xe, … Trong trường hợp này ngân hàng có thể cung cấp những dịch vụ tốt hơn, và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi được. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân nhóm trong. Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ hồi qui 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 rời rạc [13, 23]. 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ểm chẳng hạn như hồi qui tuyến tính. Tuy nhiên, phương pháp mô hình hóa cũng được sử dụng [13, 24]. + + + + + + + + + + + + + + + + + + + + + + nhóm 1 + + nhóm 2 nhóm 3 Nợ Thu nhập + + + đường hồi quy tuyến tính Nợ Thu nhập + + + + + + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát quang hiện thời trong khi rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm chuẩn đoán; dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo… hình 1.5 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, ở đây tổng số nợ được điều chỉnh cho phù hợp giống như một hàm thu nhập tuyến tính. Việc điều chỉnh này là không đáng kết bởi vì chỉ tồn tại một tương quan yếu giữa hai biến. Tổng hợp (summarization): Là công việc liên quan đến các phương pháp tìm kiếm một mô tả cô đọng cho tập con dữ liệu [23, 24]. Các kỹ thuật tổng hợp thường được áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô hình mô tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại ở hai mức:  Mức cấu trúc của mô hình (thường dưới dạng đồ thị) xác định các biến phụ thuộc cục bộ vào các biến khác;  Mức định lượng của mô hình xác định mức độ phụ thuộc của các biến [13, 24]. Những phụ thuộc này thường được biểu thị dưới dạng luật. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy [24]. Đó là đồ thị có hướng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng số chỉ liên kết phụ thuộc giữa các nút đó. Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các giá trị chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch thường dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trường hợp tập con của đối tượng này thuộc 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 nhau đáng kể so với toàn bộ đối tượng [13, 24]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ liệu thành các loại khác nhau. Cơ sở dữ liệu quan hệ Đến nay, hầu hết dữ liệu được lưu giữ dưới dạng cơ sở dữ liệu quan hệ. Cơ sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tượng mà chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu được mô tả bởi một tập những thuộc tính và lưu trong những bảng. Khai phá dữ liệu trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ liệu của một ngân hàng, ta có thể tìm được những khách hàng có mức chi tiêu cao, ta có thể phân loại những khách hàng này dựa vào quá trình chi tiêu của họ. Cũng với việc phân tích những mục chi tiêu của khách hàng, chúng ta có thể cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu được phép, ngân hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng thời trang. Cơ sở dữ liệu giao tác Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các trường hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ chức. Với tính phổ biến của máy tính và thương mại điện tử, ngày nay có rất nhiều cơ sở dữ liệu giao tác. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập trung vào khai phá luật kết hợp, tìm mối tương quan giữa những mục dữ liệu của bản ghi giao dịch. Nghiên cứu sâu về cơ sở dữ liệu giao tác được mô tả chi tiết ở phần sau. Cơ sở dữ liệu không gian Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý. Những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các đặc trưng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có dạng X ⇒ Y, với X, Y là tập hợp những vị từ không gian. Những thuật toán Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 khai phá luật kết hợp không gian tương tự như khai phá luật kết hợp nhưng thêm những vị từ về không gian. Cơ sở dữ liệu có yếu tố thời gian Giống như cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. Ví dụ, từ luật kết hợp cơ bản {Bia} ⇒ {Thuốc lá}, với dữ liệu có yếu tố thời gian chúng ta có thể có nhiều luật: Độ hỗ trợ của luật {Bia} ⇒ {Thuốc lá} là 20% từ 9 giờ đến 13 giờ, là 50% trong thời gian 19 giờ tới 22 giờ. Rõ ràng rằng, những người bán lẻ có thể xác định chiến lược để buôn bán tốt hơn. Hầu hết nghiên cứu về lĩnh vực này ngày nay hình thành một hướng khai phá dữ liệu mới gọi là khai phá mẫu lặp liên tục, khai phá tập mục dữ liệu thường xuyên trong cơ sở dữ liệu thời gian. Cơ sở dữ liệu đa phương tiện Số lượng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi, duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang phát triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đ ã trở thành một lĩnh vực nghiên cứu chính của khai phá dữ liệu, được các nhà nghiên cứu đặc biệt quan tâm. Khai phá d ữ liệu web thông thường được chia thành ba phạm trù chính: Khai phá cách dùng web (web usage mining), khai phá c ấu trúc web (web structure mining) và khai phá nội dung web (web content mining). Khai phá cách dùng web tập trung vào việc khai phá thông tin của người truy nhập web. Với những thông tin này người khai phá dữ liệu có thể cung cấp những thông tin hữu ích cho người dùng và các nhà kinh doanh. 1.6. Các phương pháp chính trong khai phá d ữ liệu • Phân lớp và dự đoán (Classification & Prediction) Xếp một đối tượng vào một trong những lớp đa biết. Ví dụ : phân lớp vùng địa lý theo dữ liệu thời tiết. Đối với hướng tiếp cận này thường áp dụng một số kỹ thuật như học máy (Machine learning), cây quyết định (Decision Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 tree), mạng nơron nhân tạo (Neural network). Với hướng này, người ta còn gọi là học có giám sát hạy học có thầy (Supervised learning). • Phân cụm và phân đoạn (Clusterring and Segmentation) Sắp xếp các đối tượng theo từng cụm (số lượng và tên của cụm chưa được biết trước). Các đối tượng được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán phân cụm còn được gọi là học không giám sát hạy học không thầy. • Luật kết hợp (Association rules) Luật kết hợp là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mẫu đầu của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Ví dụ về luật kết hợp: Một cửa hàng bán văn phòng phẩm đăng thông tin quảng cáo mỗi tuần trên một tờ báo địa phương. Khi một mặt hàng, chẳng hạn như mực in đã được chỉ định bán giảm giá, người bán hàng xác định các mặt hàng khác nào sẽ được mua cùng lúc với mực in. Họ thấy rằng giấy A4 và mực in được khách hàng mua cùng chiếm 30% và kẹp giấy được mua kèm với mực in là 40%. Dựa vào các mối quan hệ này, người bán hàng bày bán giấy A4 và kẹp giấy gần với mặt hàng mực in khi bán giảm giá. Họ cũng quyết định không đưa các mặt hàng này vào danh sách các mặt hàng giảm giá. Các hành động này nhằm mục đích tăng thêm toàn bộ khối lượng hàng bán ra bởi việc bán các mặt hàng mua mực in. Có 2 luật kết hợp được đề cập ở ví dụ trên. Luật thứ nhất là: “30% khách hàng mua mực in lẫn giấy A4 ”. Luật thứ hai là: “40% khách hàng khi mua mực in thì cũng mua kẹ p giấy”. Các luậ t kết hợp này thường được sử dụng bởi các cửa hàng bán lẻ để phân tích các giao dịch của cửa hàng. Đối với người quan lý kinh doanh, các luậ t kết hợp được phát hiện có thể được dùng trong chiến dịch Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 quảng cáo, tiếp thị, quản lý hàng tồn kho và dự trữ hàng. Các luật kết hợp cũng được sử dụng cho các ứng dụng khác như dự đoán lỗi, cho các mạng điện thoại bằng việc xác định các sự kiện xuất hiện trước đó. • Khai phá chuỗi theo thời gian (Sequential temporal patterns) Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi vì chúng có tính dự báo cao. • Mô tả khái niệm và tổng hợp hóa (Summarization) Liên quan đến các phương pháp tìm kiếm một mô tả cho một tập con dữ liệu. Các kỹ thuật toán tắt thường được áp dụng cho các phân tích dữ liệu tương tác có tính thăm dò và tạo báo cáo tự động. 1.7. Các ứng dụng của khai phá dữ liệu Khai phá dữ liệu tuy là một lĩnh vực mới nhưng đã thu hút được sự quan tâm của rất nhiều nhà nghiên cứu, nhờ có nhiều những ứng dụng trong thực tiễn, các ứng dụng điển hình, có thể liệt kê như sau: - Phân tích dữ liệu và hỗ trợ ra quyết định (Analysis & decition support). - Điều trị trong y học (Medical): mối liên hệ giữa triệu chứng, chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật). - Phân lớp văn bản, tóm tắt văn bản và phân lớp các trang Web (Text mining & Web mining). - Tin sinh học (Bio-informatics): Tìm kiếm, đối sánh các hệ gen và thông tin di truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền. - Nhận dạng. - Tài chính và thị trường chứng khoán (Finance & stock market): Phân tích tình hình tài chính và dự đoán giá cổ phiếu. - Bảo hiểm (Insurance). - Giáo dục (Education). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 1.8. Khai phá dữ liệu và các lĩnh vực liên quan Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu được c._.oi là trung tâm của nhiều ngành khoa học, nó liên quan đến rất nhiều ngành, nhiều lĩnh vực khác nhau như tài chính, ngân hàng, thương mại, y tế, giáo dục, thống kê, máy móc, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song, thu nhận tri thức trong các hệ chuyên gia, quan sát dữ liệu. Lĩnh vực học máy và nhận dạng mẫu là giống nhau trong khai phá dữ liệu nghiên cứu các lý thuyết và thuật toán của hệ thống trích ra các mẫu và mô hình dữ liệu. Khai phá dữ liệu tập trung vào việc mở rộng các lý thuyết và thuật toán cho các vấn đề về tìm ra các mẫu đặc biệt, đây được coi là những mẫu hữu ích hoặc tri thức quan trọng tập dữ liệu lớn. Đặc biệt, phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật…, kho dữ liệu và các công cụ xử lý trực tuyến (OLAP – online analytical processing) tập trung vào phân tích dữ liệu đa chiều, tốt hơn SQL trong tính toán và phân tích thống kê đa chiều cũng liên quan chặt chẽ đến khai phá dữ liệu. Đặc trưng của hệ thống khai phá dữ liệu là nhờ vào các phương pháp thuật toán và kỹ thuật từ những lĩnh vực khác nhau, nhằm mục đích cuối cùng là trích ra tri thức từ dữ liệu trong CSDL khổng lồ. Khai phá dữ liệu Cơ sở dữ liệu Thương mại Y tế Thống kê Giáo dục Các ngành khoa học khác Máy móc, trí tuệ nhân tạo Tài chính, ngân hàng Thuật toán học Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu Khai phá dữ liệu ngày càng đóng một vai trò quan trọng trong việc tìm ra các tri thức thực sự có ích, hiệu quả tiềm ẩn trong các khối dữ liệu thông tin khổng lồ vẫn hàng ngày đang được thu thập, lưu trữ để giúp các cá nhân và tổ chức đưa ra được các quyết định chính xác và nhanh chóng. Tuy đã có rất nhiều các giải pháp và phương pháp được ứng dụng trong khai phá dữ liệu nhưng trên thực tế quá trình này vẫn gặp không ít khó khăn và thách thức như: - Cơ sở dữ liệu lớn - Số chiều các thuộc tính lớn - Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp - Dữ liệu bị thiếu hoặc bị nhiễu - Quan hệ giữa các trường phức tạp - Giao tiếp với người sử dụng và kết hợp với các tri thức đã có - Tích hợp với các hệ thống khác Cơ sở dữ liệu lớn có thể lớn về số lượng các bản ghi, lớn về số lượng các thuộc tính trong CSDL. Số lượng các bản ghi trong CSDL lớn có khi dung lượng tới hàng gigabyte, terabyte; số các thuộc tính trong CSDL có thể rất nhiều và đa dạng. Để giải quyết vấn đề này, người ta thường đưa ra một ngưỡng nào đó cho CSDL bằng các cách như chiết xuất mẫu, xấp xỉ hoặc xử lý song song. Trong CSDL khi mà số các thuộc tính là rất lớn , cùng với số lượng lớn các bản ghi sẽ dẫn đến kích thước độ phức tạp của bài toán tăng lên. Vì vậy, không gian tìm kiếm, không gian trạng thái gia tăng, n hiều mẫu hay mô hình thừa, trùng lặp phát sinh nhiều luật thừa, đây được coi là vấn đề nan giải trong quá trình khai phá dữ liệu. Nhằm giải quyết được những vấn đề trên , phải sử dụng một số các tri thức đã biết trước để loại bỏ và trích lọc ra những dữ liệu thích hợp với yêu cầu của bài toán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 Vấn đề dữ liệu bị thay đổi phụ thuộc theo thời gian, có nghĩa là dữ liệu bị ảnh hưởng và phụ thuộc vào thời điểm quan sát, lấy mẫu, thời điểm khai phá. Kết quả đạt được sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu, như các mẫu được khai phá ở bước trước, có thể không còn giá trị hay vô nghĩa đối với thời điểm sử dụng, hoặc có thể làm nhiễu hay phát sinh hiệu ứng phụ làm sai lệch kết quả. Để khắc phục được vấn đề này cần phải chuẩn hóa, cải tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi này là mục đích của khai phá và tìm kiếm các mẫu bị thay đổi. Thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị trong các miền thuộc tính đã làm ảnh hưởng rất lớn trong khai phá dữ liệu . Trong quá trình khai phá dữ liệu, khi các hệ thống tương tác với nhau phụ thuộc nhau mà thiếu vắng một vài giá trị nào đó , sẽ dẫn đến các mẫu không được chính xác, bị thiếu, không đầy đủ. Để giải quyết cho vấn đề này, người ta coi sự thiếu vắng của các dữ liệu này là giá trị ẩn, chưa biết và có thể được tiên đoán bằng một số phương pháp nào đó. Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần được quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối liên hệ phức tạp với nhau trong CSDL đòi hỏi khai phá dữ liệu phải có các giải pháp, các kỹ thuật để có thể áp dụng được, nhận ra được các mối quan hệ này trong quá trình khai phá dữ liệu. 1.10. Kết luận chương 1 Các tri thức tiềm ẩn trong các CSDL có ý nghĩa rất lớn trong nhiề u lĩnh vực vì vậy việc phát hiện, rút trích tự động các tri thức ẩn từ các tập hợp dữ liệu lớn thông qua các mẫu, mô hình dữ liệu càng đóng một vai trò hết sức quan trọng, đặc biệt là trong bối cảnh hiện nay khi mà sự phát triển nhanh chóng của các ứng dụng công nghệ thông tin ở nhiều ngành nghề trong đời sống xã hội , ngày càng tạo ra nhiều CSDL khổng lồ. Chương này trình bày tóm tắt các phương pháp khai phá dữ liệu phổ biến, các thành phần chủ yếu của một giải thuật khai phá dữ liệu và những thành tựu cũng như những thách thức trong khai phá dữ liệu. Trong các phương pháp khai phá dữ liệu, khai phá các luật kết hợp là một trong những lĩnh vực đang được quan tâm và nghiên cứu mạnh mẽ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 Chương 2 KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU 2.1. Mở đầu Khai phá dữ liệu là quá trình phát hiện ra các thômg tin có giá trị tiềm ẩn trong CSDL và được xem như là một công đoạn trong quá trình khai thác tri thức. Chức năng của khai phá dữ liệu bao gồm phân lớp, phân cụm, dự đoán và phân tích kết hợp. Ứng dụng khai phá kết hợp là một trong những ứng dụng quan trọng của khai phá dữ liệu. Luật kết hợp được giới thiệu đầu tiên vào năm 1993 [19], được sử dụng để xác định các mối quan hệ giữa các tập thuộc tính trong CSDL. Việc xác định các quan hệ này không được dựa vào các đặc tính dữ liệu vốn có của chúng (như các phụ thuộc hàm), mà nên dựa vào sự xuất hiện cùng lúc của các thuộc tính dữ liệu. Ví dụ 1.1 Trong một hiệu sách lưu lại các phiếu mua sách, người ta phát hiện ra rằng: Trong số những người mua quyển "Các khái niệm và kỹ thuật khai phá dữ liệu" thì có 40% số người đó mua thêm quyển " Hệ quản trị cơ sở dữ liệu", và 25% mua thêm quyển "Kho dữ liệu". Trong ví dụ trên, tìm được hai luật kết hợp: - Có 40% số người mua quyển " Các khái niệm và kỹ thuật khai phá dữ liệu" thì đồng thời mua quyển "Hệ quản trị cơ sở dữ liệu". - Có 25% số người mua quyển " Các khái niệm và kỹ thuật khai phá dữ liệu" thì đồng thời mua quyển "Kho dữ liệu". Với những quy tắc được khám phá trên, ta có thể sắp xếp các quyển sách có liên quan với nhau ở v ị trí gần nhau để giúp cho người mua sách thuận tiện hơn. Những quy tắc đó cũng giúp cho nhà sách có chiến lược kinh doanh tốt hơn. Luật kết hợp được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau như: Kinh doanh, sản xuất, giao thông, viễn thông, giáo dục, quản lý thị trường, … Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 Luật kết hợp cho biết phạm vi mà trong đó, sự xuất hiện của tập các thuộc tính A nào đó trong các bản ghi của CSDL D sẽ kéo theo sự xuất hiện của tập các thuộc tính khác B, cũng trong những bản ghi đó, có dạng A ⇒ B. Mỗi luật kết hợp được đặc trưng bởi một cặp tỷ lệ đó, là độ hỗ trợ và độ tin cậy. Thông tin mà luậ t kết hợp mang lại là rất to lớn và hỗ trợ đáng kể cho quá trình ra quyết định trong kinh doanh cũng như trong nghiên cứu khoa học. 2.2 Luật kết hợp 2.2.1 Các khái niệm cơ bản [18, 22] Đặt: I = {i1,…,in}: tập n mục (Item, còn gọi là thuộc tính) phân biệt. D: CSDL giao dịch Mỗi giao dịch (Transaction - còn gọi là bản ghi - record) T ∈ D được định nghĩa như một tập con các mục trong I (T ⊆ I) và có một định danh duy nhất có dạng . Một giao dịch T ∈ D hỗ trợ cho tập mục X, X ⊆ I nếu nó chứa tất cả các mục 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 sup(X) (support(X) hoặc 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 có trong D, nghĩa là: sup(X) = Pr(X) = { } || | D TXDT ⊆∈ (2.1) Ta có 0 ≤ sup(X) ≤ 1 với mọi tập mục X. Định nghĩa 2.1: Cho một tập X ⊆ I và một ngưỡng hỗ trợ tối thiểu (minimum support) minisup∈ (0,1] (được xác định bởi người sử dụng). Một tập mục X được gọi là một tập mục phổ biến (Frequent Itemset hoặc Large Iteset) với độ hỗ trợ tối thiểu minsup nếu và chỉ nếu sup(X) ≥ minsup. Một tập mục phổ biến được sử dụng như là một tập đáng quan tâm trong các thuật toán, ngược lại, những tập mục không phải tập mục phổ biến là những tập không đáng quan tâm. Trong các trình bày sau này, ta sử dụng những cụm từ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 khác như ‘‘X có độ hỗ trợ tối thiểu ’’ , ‘‘X không có độ hỗ trợ tối thiểu ’’ cũng chỉ để nói lên X thỏa mãn hay không thỏa mãn sup(X) ≥ minsup. Một tập mục X được gọi là k-itemset nếu lực lượng của X bằng k (tức làX= k). Một số tính chất liên quan đến tập mục phổ biến: Tính chất 2.1: Nếu A ⊆ B, A, B là các tập mục thì sup(A) ≥ sup(B) vì tất cả các giao dịch của D hỗ trợ B thì cũng hỗ trợ cho A. Tính chất 2.2: Một tập mục B không có độ hỗ tối thiểu trên D nghĩa là sup(B) < minsup thì mọi tập cha A của B sẽ không phải là tập mục phổ biến vì sup(A) ≤ sup(B) < minsup. Tính chất 2.3: Nếu tập mục B là một tập mục phổ biến trên D, nghĩa là sup(B) ≥ minsup thì mọi tập con A của B đều là tập phổ biến trên D vì sup(A) ≥ sup(B) > minsup. Định nghĩa 2.2: Một luật kết hợp là một quan hệ có dạng X ⇒Y, trong đó X, Y ⊂ I là tập các mục còn gọi là itemset, và X ∩Y = φ . Ở đây, X được gọi là tiền đề, Y là hệ quả của luật. Hai thông số quan trọng của luật kết hợp là độ hỗ trợ và độ tin cậy. Định nghĩa 2.3: Độ hỗ trợ (support) của luận kết hợp X ⇒ Y là tỷ lệ phần trăm giữa các giao dịch chứa X ∪ Y và tổng số các giao dịch trong CSDL. sup(X ⇒ Y) = Pr(X ∪ Y ) = { } || | D TYXDT ⊆∪∈ (2.2) Bởi vậy, ta nói độ hỗ trợ của luật bằng 5% nghĩa là có 5% tổng số giao dịch có chứa X ∪ Y. Độ hỗ trợ mang ý nghĩa thống kê của luật kết hợp. Trong khi, một độ hỗ trợ cao cho luật kết hợp thường được mong muốn nhất, tuy nhiên điều đó không phải luôn luôn đúng. Ví dụ, nếu ta sử dụng luật kết hợp để dự đoán thất bại các nút chuyển mạch trong mạng điện thoại dựa vào tập sự kiện nào đó xuất hiện trước một thất bại, mặc dù hai sự kiện này không thường xuyên xuất hiện, các luật kết hợp chỉ ra quan hệ này vẫn có tầm quan trọng đáng kể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Định nghĩa 2.4: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) của luật kết hợp X ⇒ Y là tỷ lệ phần trăm giữa số giao dịch có chứa X ∪ Y và số giao dịch chứa X. conf (X ⇒ Y) = p (Y ⊆ I X ⊆ I) = )sup( )sup( )( )( X YX TXp TXTYp ∪ = ⊆ ⊆∧⊆ (2.3) Vì vậy, nếu ta nói rằng một luật có độ tin cậy conf = 85% có nghĩa là 85% các giao dịch hỗ trợ cho X thì cũng hỗ trợ cho Y. Độ ti n cậy của luật cho biết mức độ tương quan trong tập dữ liệu (dataset) giữa hai tập mục X và Y và là tiêu chuẩn đánh giá độ tin cậy của một luật. Việc khai thác các luật kết hợp từ cơ sở dữ liệu D chính là việc tìm tất cả các luật có độ hỗ trợ và độ tin cậy lớn hơn ngưỡng hỗ trợ (độ hỗ trợ tối thiểu) và ngưỡng tin cậy (độ tin cậy tối thiểu) do ngư ời sử dụng xác định trước. Ngưỡng hỗ trợ và ngưỡng tin cậy lần lượt được ký hiệu là minsup và mincof. Chú ý r ằng, nếu luật X ⇒ Y thỏa mãn trên D thì c ả X và Y đều là các t ập mục phổ biến trên D. Một số tính chất liên quan đến luật kết hợp Tính chất 2.4: Nếu X ⇒ Z và Y ⇒ Z là thỏa mãn trên D thì không nhất thiết X ∪ Y ⇒ Z là đúng. Xét trư ờng hợp X ∩Y = ∅ và các giao d ịch trong D có hỗ trợ cho Z nếu và chỉ nếu chúng chỉ chứa X hoặc Y, khi đó conf(X ∪ Y ⇒ Z) = 0. Tương t ự, ta cũng có: Nếu X ⇒ Y và Z ⇒ Z thỏa mãn trên D thì cũng không thể suy ra X ⇒ Y ∪ Z. Tính chất 2.5: Nếu luật X ∪ Y ⇒ Z thỏa mãn trên D thì không nhất thiết X ⇒ Z và Y ⇒ Z thỏa mãn trên D. Chẳng hạn, khi Z có mặt trong giao dịch chỉ khi cả X và Y đều có mặt trong giao dịch đó, nghĩa là sup(X ∪ Y) =sup(Z). Nếu sup(X) ≥ sup(X ∪ Y) và sup(Y) ≥ sup(X ∪ Y) thì 2 luật trên sẽ không có độ tin cậy yêu cầu. Tuy nhiên, nếu X ⇒ Y ∪ Z thỏa mãn trên D thì suy ra được X ⇒ Y và X ⇒ Z cũng thỏa mãn trên D. Tính chất 2.6: Nếu X ⇒ Y và Y ⇒ Z thỏa mãn trên D thì không thể khẳng định X ⇒ Z cũng thỏa mãn trên D. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 Giả sử T(X) ⊆ T(Y) ⊆ T(Z) và conf(X ⇒ Y) = conf(Y ⇒ Z) = minconf. Khi đó, ta có conf(X ⇒ Z) = minconf2 < minconf vì minconf< 1, nghĩa là luật X ⇒ Z không có độ tin cậy tối thiểu. Tính chất 2.7: Nếu luật X ⇒ (L - X) không có độ tin cậy tối thiểu thì không có luật nào trong các luật Y ⇒ (L – Y) có độ tin cậy tối thiểu, trong đó Y ⊆ X ; X,Y ⊂ L. Thật vậy, theo tính chất 2.1, vì Y ⊆ X nên sup(Y) ≥ sup(X) và theo định nghĩa độ tin cậy, ta có: confidence(Y ⇒ (L – Y)) = conf Xport Lport Yport Lport min )(sup )(sup )(sup )(sup <≤ Nếu luật (L – X) ⇒ X thỏa mãn trên D thì các luật (L – Y) ⇒ Y với Y ⊆ X và Y ≠ ∅ cũng thỏa mãn trên D. 2.2.2. Khai phá luật kết hợp Trong mục này sẽ giới thiệu chi tiết bài toán khai phá luật kết hợp (Association Rule Mining). Nh ững kết quả khác nhau trong khai phá luật kết hợp sẽ được trình bày chi tiết cùng với những thuật toán và những ví dụ kinh điển. Bài toán khai phá luật kết hợp trên một cơ sở dữ liệu được chia thành hai bài toán nhỏ. Bài toán thứ nhất là tìm tất cả các tập mục dữ liệu có độ hỗ trợ thỏa ngưỡng tối thiểu cho trước, gọi là tập các tập mục dữ liệu thường xuyên. Bài toán thứ hai là tìm ra những luật kết hợp từ những tập mục dữ liệu thường xuyên thỏa độ tin cậy tối thiểu cho trước. Bài toán thứ hai được giải quyết như sau: Giả sử ta có tập các mục dữ liệu thường xuyên Lk, với { }k21 iiik x,...,x,xL = , những luật kết hợp theo ngưỡng tin cậy tối thiểu C0 với những mục dữ liệu thường xuyên này được phát sinh ra bằng cách: Luật thứ nhất: { } { }k1k21 iiii xx,...,x,x →− , kiểm tra đ ộ tin cậy củ a luật n ày có thỏa ngưỡng tin cậy tối thiểu cho trước hay không. Luật thứ hai: { } { } 1kk2k21 iiiii xx,x,...,x,x −− → , kiểm tra độ tin cậy của luật này có thỏa ngưỡng tin cậy tối thiểu cho trước hay không. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 Luật thứ k+1: { } { } k1k2k21 iiiii x,xx,...,x,x −− → , kiểm tra độ tin cậy của luật này có thỏa ngưỡng tin cậy tối thiểu cho trước hay không. Tổng quát: ∀X ⊂ Lk, ta kiểm tra độ tin cậy của luật X → Lk \ X có thỏa ngưỡng tin cậy tối thiểu cho trước hay không. Bài toán th ứ hai là đơn giản, hầu hết nghiên cứu về luật kết hợp tập trung ở bài toán th ứ nhất. Sau đây chúng ta tập trung giải quyết bài toán thứ nhất. 2.2.3. Cách tiếp cận khai phá luật kết hợp Khai phá luật kết hợp là một lĩnh vực nghiên cứu được nhiều người quan tâm và có nhiều kết quả đã được công bố. Ở đây chỉ giới thiệu một số cách tiếp cận kinh điển và cơ bản, làm cơ sở để phát triển các thuật toán mới. Bài toán thứ nhất có thể chia nhỏ hơn nữa thành hai bài toán: Tìm các tập mục dữ liệu ứng viên và tìm các tập mục dữ liệu thường xuyên. Tập mục dữ liệu ứng viên là những tập mục dữ liệu, mà ta phải tính độ hỗ trợ để xem nó có phải là tập mục dữ liệu thường xuyên hay không. Tập mục dữ liệu thường xuyên là những tập mục dữ liệu có độ hỗ trợ lớn hơn hay bằng ngưỡng tối thiểu cho trước. Phát triển thuật toán khai phá luật kết hợp, là làm giảm độ phức tạp tính toán của thuật toán để cải thiện tốc độ xử lý. Ta có thể phân loại các thuật toán tìm tập thường xuyên theo hai tiêu chí:  Phương pháp duyệt qua không gian tìm kiếm  Phương pháp xác định độ hỗ trợ của tập mục dữ liệu. Với phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách: Duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu (Depth First Search – DFS). Duyệt theo chiều rộng là duyệt qua dữ liệu nguyên bản, để tính độ hỗ trợ của tất cả các tập ứng viên có k-1, mục dữ liệu trước khi tính độ hỗ trợ của các tập ứng viên có k mục dữ liệu. Một cơ sở dữ liệu có n mục dữ liệu, trong lần lặp thứ k để tìm những tập k-mục dữ liệu ứng viên, phải kiểm tra tất cả )!kn(!k !nCkn − = tập k-mục dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Duyệt theo chiều sâu, là duyệt qua cơ sở dữ liệu đã được chuyển thành cấu trúc cây, quá trình duyệt được gọi đệ quy theo chiều sâu của cây. Với cơ sở dữ liệu có n mục dữ liệu, I = {x1, x2, …, xn}, thì không gian tìm kiếm là tập tất cả các tập con của I, đây là bài toán NP khó, nếu không có phương pháp duyệt thích hợp thì bài toán không giải được khi n đủ lớn. Phương pháp xác định độ hỗ trợ của tập mục dữ liệu X ⊆ I được phân làm hai cách: Cách thứ nhất: Đếm số giao tác trong cơ sở dữ liệu chứa X. Cách thứ hai: Tính phần giao của các tập định danh giao tác chứa X. Phát biểu bài toán phát hiện luật kết hợp Cho một tập các mục I, một cơ sở dữ liệu giao dịch D, ngưỡng hỗ trợ minsup, ngưỡng tin cậy minconf. Tìm tất cả các luậ t kết hợp X ⇒Y trên CSDL D sao cho: sup(X ⇒ Y) ≥ minsup và conf(X ⇒ Y) ≥ minconf. Bài toán khai thác luật kết hợp có thể được chia ra làm 2 bài toán con được phát biểu trong thuật toán sau: Nội dung thuật toán Vào: I, D, minsup, minconf R: Các luận kết hợp thỏa mãn minsup và minconf Phương thức: (1) Tìm tất cả các tập mục phổ biến từ CSDL D tức là tìm tất cả các tập mục có độ hỗ trợ lớn hơn hoặc bằng minsup. (2) Sinh ra các luật từ các tập mục phổ biến (large itemsets) sao cho độ tin cậy của luật lớn hơn hoặc bằng minconf. Bước 1: Tìm các tập mục phổ biến như được mô tả trong hình 2.1. Bước 2: Sinh các luật kết hợp từ tập mục phổ biến tìm được ở bước 1. Tùy theo ngữ cảnh các thuộc tính dữ liệu, cũng như phương pháp sử dụng trong các thuật toán; người ta có thể phân bài toán khai phá luật kết hợp ra nhiều nhóm khác nhau. Chẳng hạn, nếu giá trị của các thuộc tính có kiểu boolean thì ta gọi là khai phá luật kết hợp Boolean (Mining Boolean Association Rules) … 2.3 Luật kết hợp cơ sở Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 2.3.1 Phát hiện các tập mục phổ biến Các thuật toán phát hiện tập mục phổ biến, phải thiết lập một số giai đoạn trên CSDL. Trong giai đoạn đầu, ta thực hiện tính độ hỗ trợ support cho mỗi mục riêng lẻ và xác định xem mục nào là phổ biến, nghĩa là có support ≥ minsup. Trong mỗi giai đoạn tiếp theo, ta bắt đầu với các tập mục phổ biến đã tìm được trong giai đoạn trước, để sinh ra các tập mục có khả năng là tập phổ biến mới (còn gọi là tập mục ứng cử - candidate itemset) và tính độ hỗ trợ cho các tập mục ứng cử này bằng một phép duyệt CSDL. Cuối mỗi giai đoạn, người ta xác định xem trong các tập mục phổ biến cho giai đoạn tiếp theo. Tiến trình này sẽ tiếp tục, cho đến khi không tìm được một tập các tập mục phổ biến mới hơn nữa. Ta giả sử các mục trong mỗi giao dịch đã được sắp xếp theo thứ tự từ điển (diễn tả một thứ tự quy ước nào đó cho các mục của CSDL). Các mục trong một tập mục cũng được lưu trữ theo thứ tự từ điển, nghĩa là, một k-itemset ci kí hiệu là ci[1], ci[2],…, ci[k] thì ci[1] < ci[2] <…< ci[k]. Nếu ci = X.Y và Y là một m-itemset thì Y cũng được gọi là một m -mở rộng (m-extention) của X. Trong lưu trữ, mỗi tập mục có một trường support_count tương ứng, dùng để lưu độ hỗ trợ cho tập mục này. 2.3.1.1 Thuật toán Apriori [18, 21, 22] L = φ, L1 = {large 1+itemset}, k = 2 tập mục ứng cử Ck, từ tập Lk+1 support cho các phần tử của tập Ck Lk từ Ck bằng phép kiểm tra minsup L là tập cần tìm NO Bổ sung Lk vào L, k++ Hình 2.1. Sơ đồ tổng quan của thuật toán khai phá tập mục phổ biến Lk ≠ φ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Apriori là thuật toán khai phá luậ t kết hợp do RaKesh Agrawal, Tomasz Imielinski, Anin Sawami đưa ra vào năm 1993, là nề tảng cho việc phát triển những thuật toán sau này. Thuật toán sinh tập mục ứng cử từ những tập mục phổ biến ở bước trước, sử dụng kĩ thuật “tỉa” để bỏ đi tập mục ứng cử không thỏa mãn ngưỡng hỗ trợ cho trước. Các ký hiệu sử dụng trong thuật toán: Lk = {l1, l2,…, li, …} tập các k-itemset phổ biến. Ck = {c1, c2,…, ci, …} tập các k -itemset ứng cử, mỗi c i có 2 trường itemset và count dùng để chứa tập mục và số đếm hỗ trợ của tập mục đó trong cơ sở dữ liệu. Nội dung thuật toán Dữ liệu vào: Tập các giao dịch D, ngưỡng hỗ trợ minsup Dữ liệu ra: Tập Answer bao gồm các tập mục phổ biến trên D Phương pháp: L1 = {large 1-itemset}; for (k = 2; Lk-1 ≠ φ; k++) do begin Ck = apriori_gen(Lk-1); // sinh tập mục ứng cử mới Ck; forall giao dịch t ∈ D do begin Ct = subset(Ck, t); // các tập mục ứng cử chứa trong t; forall tập mục ứng cử ci ∈ Ct do ci.count ++ ; end; Lk = {ci ∈ Ckci.count ≥ minsup} end; Answer = ∪kLk ; Giải thích thuật toán Trong thuật toán này, giai đoạn đầu đơn giản chỉ là việc tính độ hỗ trợ của các mục. Để xác định L1, ta chỉ giữ lại các mục có độ hỗ trợ 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: Pha thứ 1: Các (k-1)-itemset phổ biến trong tập L k-1 tìm được trong giai đoạn thứ k-1 được dùng để sinh ra các tập mục ứng cử Ck bằng cách thực hiện hàm apriori_gen(). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 Pha thứ 2: CSDL D sẽ được quét để tính độ hỗ trợ cho mỗi tập mục ứng cử trong Ck. Các tập mục ứng cử trong Ck mà được chứa trong giao dịch t có thể được xác định một cách hiệu quả bằng việc sử dụng cây băm. Hàm apriori_gen() thực hiện hai bước: Bước kết nối (Join step): Bước này kết nối các phấn tử trong Lk-1. Trong này, giả sử rằng các mục của các tập mục đã đượ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 l1, l2 nào đó mà giống nhau thì ta khởi tạo một k-itemset ứng cử 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 l1 và l2 (có thể phải sắp lại thứ tự cho các item này). Điều kiện l 1[k-1] < l2[k-1] nhằm tránh trường hợp 2 tập mục l1 và l2 giống nhau kết nối với nhau. Bước cắt tỉa (Prune step): Trong bước này, ta cần loại bỏ tất cả các k-itemset ci ∈ Ck mà tồn tại một (k-1)-itemset s, s ⊂ ci và s ∉ Lk-1. Giải thích điều này như sau: một (k-1)-itemset s, s ⊂ ci và s ∉ Lk-1. Khi đó, sup(s) < minsup vì s không phải là tập phổ biến, mặt khác do ci ⊃ s nên sup(ci) ≤ sup(s) < minsup. Vậy ci không thể là tập phổ biến, nó cần được loại bỏ ra khỏi Ck. Ví dụ: Cho tập các mục phổ biến L3 = {{a; b; c}; {a; b; d}; {a; c; d}; {a; c; e} ; {b; c; d}}. Chúng ta kết nối tập mục phổ biến l 1 = {a; b; c} và tập mục phổ biến l2 = {a; b; d}, ta được tập mục ứng cử c 1 ={a; b; c; d}. Cả 3 tập con ( {a; b; c}; {a; b; d} ; {b; c; d}) s ⊂ c1 đều thuộc L3 do đó c1 được giữ lại và C4 ← c1. Cũng tương tự, ta kết nối tập mục phổ biến l 3 = {a; c; d} và tập mục phổ biến l4 = {a; c; e}, ta sinh ra được tập mục ứng cử c 2 = {a; c; d; e}. Ta có tập mục s = {a; d; e} ⊂ c2 mà s ∉ L3 nên tập mục ứng cử c2 bị loại. Hàm subset và cấu trúc cây băm (hash-tree) Cấu trúc cây băm: Để tăng hiệu quả cho việc tìm các tập mục thường xuyên và tính độ hỗ trợ cho các tập mục ứng cử, thuật toán sử dụng cấu trúc cây Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 băm để lưu trữ các tập mục ứng cử Ck. Mỗi nút của cây băm hoặc chứa một danh sách của các tập mục (nếu là nút lá) hoặc một băm (hash table) (nếu là nút trong). Tại mỗi nút trong, mỗi phần tử (bucket) của bảng băm trỏ đến một nút khác. Gốc của cây được định nghĩa có độ sâu bằng 1. Nút ở độ sâu d thì trỏ đến nút ở độ sâu (d + 1). Các tập mục được lưu trữ trong các nút lá tạo thành một danh sách liên kết và đã được sắp xếp. Khi số tập mục lưu trong nút lá vượt quá ngưỡng thì nút lá chuyển thành nút trong. Khi thêm một tập mục ci vào cây, ta bắt đầu duyệt từ nút gốc trên cây cho đến khi tìm được nút lá phù hợp, cách thực hiện như sau: ở mỗi nút trong độ sâu d, chúng ta quyết định đi theo nhánh nào bằng cách sử dụng hàm băm đối với mục thứ d (ci[d] lưu mục thứ d) của tập mục ci. Hàm subset(Ck, t): Hàm này dùng để tìm tất cả các tập mục ứng cử trong Ck có chứa trong giao dịch t. Để tìm tập mục ứng cử ta bắt đầu từ nút gốc: nếu nút gốc là nút lá thì ta xem các tập mục trong nút lá đó có chứa trong giao dịch t hay không. Trường hợp nút trong, và là kết quả của việc áp dụng hàm băm cho mục thứ i của giao dịch t , thì ta tiếp tục thực hiện hàm băm cho mục thứ (i +1) của giao dịch t, cho đến khi tìm gặp nút lá. Thủ tục tìm này được thực hiện đệ quy. 2.3.1.3 Ví dụ minh họa thuật toán Apriori Cho cơ sở dữ liệu giao dịch D, I = {bánh mì, bơ, trứng, sữa, đông sương, kem}. Áp d ụng thuật toán Apriori để tìm các tập phổ biến thỏa minsup = 60%. Sau khi áp dụng thuật toán Apriori c ác tập mục phổ biến thu được chỉ ra trong hình 2.2. L = L1 ∪ L2 ∪ L3 = {{bánh mì}; {bơ}; {sữa}; {bánh mì, bơ}; {bánh mì, sữa}; {bơ, sữa}; {bánh mì, bơ, sữa}} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Hình 2.2: Ví dụ thuật toán Apriori 2.3.1.4 Các thuật toán phát hiện tập mục phổ biến khác Có rất nhiều thuật toán được đề xuất để phát hiện các tập mục phổ biến đây là bước quan trọng và chiếm nhiều thời gian nhất trong quá trình khai phá luật kết hợp trong CSDL. Sau đây là một số thuật toán tiêu biểu và đặc điểm của nó.  Thuật toán Apriori-TID Như đã đề cập ở phần trên, thuật toán Apriori quét to àn bộ CSDL trong mỗi giai đoạn để tính độ hỗ trợ. Việc quét toàn bộ CSDL có thể là không cần thiết đối với tất cả các giai đoạn. Với ý tưởng, Agrawal đã đề xuất một thuật toán khác, gọi là thuật toán Apriori-TID. TID Giao dịch 100 {kem, bánh mì, sữa, bơ} 200 {sữa, bánh mì, trứng, đường, bơ} 300 {trứng, bánh mì, bơ, đường} 400 {bơ, bánh mì, sữa} Cơ sở dữ liệu D 1-itemset Độ hỗ trợ {bánh mì} 100% {bơ} 100% {trứng} 50% {sữa} 75% {đường} 50% {kem} 25% C1 Quét D 2-itemset {bánh mì, bơ} {bánh mì, sữa} {bơ, sữa} C2 2-itemset {bánh mì, bơ} {bánh mì, sữa} {bơ, sữa} C2 1-itemset Độ hỗ trợ {bánh mì} 100% {bơ} 100% {sữa} 75% L1 Xóa bỏ các mục có support < minsup 2-itemset {bánh mì, bơ} {bánh mì, sữa} {bơ, sữa} 1-itemset Độ hỗ trợ {bánh mì} 100% {bơ} 100% {sữa} 75% Quét D L2 3-itemset {bánh mì, bơ, sữa} 3-itemset {bánh mì, bơ, sữa} C3 C3 1-itemset Độ hỗ trợ {bánh mì, bơ, sữa} 75% Quét D L3 Kết nối L1 và L2 Tỉa Tỉa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Tương tự thuật toán Apriori, thuật toán Apriori-TID cũng sử dụng hàm apriori_gen() để xác định các tập mục ứng cử trước khi bắt đầu mỗi giai đoạn. Điểm khác nhau chủ yếu của thuật toán này so với thuật toán Apriori là; nó không sử dụng CSDL để tính độ hỗ trợ trong các giai đoạn k > 1. Thay vào đó nó sử dụng mã khóa của các tập mục ứng cử đã sử dụng trong giai đoạn trước, kC . Nhiều thí nghiệm trên nhiều CSDL chỉ ra rằng thuật toán Apriori cần ít thời gian hơn giải thuật Apriori-TID trong các giai đoạn đầu ,nhưng mất nhiều thời gian cho các giai đoạn sau, mô tả chi tiết trong [20, 21].  Thuật toán Apriori-Hybrid Thuật toán này dựa vào ý tưởng “không cần thiết phải sử dụng cùng một thuật toán cho tất cả các giai đoạn lên trên dữ liệu”. Như đã đề cập ở trên, thuật toán Apriori thực thi hiệu quả ở các giai đoạn đầu, thuật toán Apriori-TID thực thi hiệu quả ở các giai đoạn sau. Phương pháp của thuật toán Apriori-Hybrid là sử dụng thuật toán Apriori ở các giai đoạn đầu và chuyển sang sử dụng thuật toán Apriori-TID ở các giai đoạn sau, được trình bày chi tiết trong [21].  Thuật toán AIS (Agrawal Imielinski Swami) Trong thuật toán AIS, tập các mục ứng cử được sinh ra và được tính khi quét toàn bộ CSDL. Với mỗi giao dịch t, thuật toán chọn các tập mục phổ biến nào đã được phát hiện ở giai đoạn trước có chứa trong giao dịch t. Các tập mục ứng cử mới được sinh ra bằng việc mở rộng các tập phổ biến này với các mục khác trong giao dịch t [18, 21].  Thuật toán DIC (Dynamic Itemset Counting) Thuật toán DIC bắt đầu tính độ hỗ trợ cho các k-itemset sau khi quét ((k - 1) * M) giao dịch, M < D và dừng việc t ính sau khi các k-itemset này được thấy trong tất cả các giao dịch. Thuật toán Apriori là trường hợp đặc biệt của thuật toán DIC, ứng với M = D. Vì vậy, thuật toán DIC thực hiện tốt hơn thuật toán Apriori nếu M được chọn thích hợp [18, 21].  Thuật toán OCD (Of-line Candidate Determination) Kỹ thuật OCD được giới thiệu bởi Mannila vào năm 1994, dựa vào ý tưởng “các mẫu có kích thước nhỏ thường là khá tốt cho việc tìm kiếm các tập Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 mục phổ biến”. Kỹ thuật này sử dụng các kết quả của phép phân tích tổ hợp thông tin thu được ở các giai đoạn trước , để lo ại b ỏ đi các tập mụ c ứng cử không cần thiết. Nếu một tập Y ⊆ I là một tập không phổ biến thì cần quét ít nhất (1 - s) giao dịch trong CSDL, s là ngưỡng hỗ trợ. Vì vậy, đối với những giá trị ngưỡng hỗ trợ s nhỏ thì hầu như toàn bộ các giao dịch phải được quét. Thuật toán OCD sinh ra một tập tất cả các k-itemset phổ biến Lk [18, 20].  Thuật toán phân hoạch [21] Thuật toán này chia CSDL thành các phân hoạch nhỏ, mỗi phân hoạch có thể được lưu trữ trên bộ nhớ chính. Cho các phân h._. 5:1 3:4 8:4 P2 0:1 9:3 5:2 0:1 7:1 6:2 7:1 0:1 0:1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 Để sinh các FP-Tree điều kiện ta sử dụng mô hình Chủ - Tớ. Bộ xử lý Chủ chuyển các mục cần được khai phá cho các bộ x ử lý Tớ. Các bộ xử lý Tớ sinh các FP-Tree điều kiện cho các mục đó, khi bộ xử lý Tớ hoàn thành việc sinh FP-Tree điều kiện, nó chuyển một mã thông báo đến bộ xử lý Chủ yêu cầu mục kế tiếp. Nhiệm vụ của bộ xử lý chủ là lắng nghe các yêu cầu đến từ bất kì bộ xử lý Tớ. Nó trả lời bằng cách chuyển mục kế tiếp đến bộ xử lý Tớ đó. Khi mà bộ xử lý Tớ nhận mục kế tiếp từ bộ xử lý Chủ chuyển đến, nó sẽ bắt đầu sinh CFPT cho mục này. Chi phí truyền thông trong thuật toán này tương đối thấp vì mỗi bộ xử lý chỉ chuyển mã thông báo. Hơn nữa, khối lượng công việc là cân bằng giữa các bộ xử lý trong nhóm do mỗi khi một bộ xử lý Tớ nào đó hoàn thành nhiệm vụ nó nhận một nhiệm vụ khác ngay lập tức. Items Các mẫu điều kiện cơ sở Các FP-Tree điều kiện P0 P1 P2 Trước khi lượt bỏ Sau khi lượt bỏ 7 9 8 3 : 1 0 6 5 9 8 3 : 1 0 6 3 : 1 0 6 5 9 8 3 : 1 6 5 : 1 6 5 9 8 3 : 1 0 9 8 3 : 1 (3:6, 8:5, 9:5, 5:4, 6:5, 0:4) (3 : 6) 0 6 5 9 8 3 : 1 6 3 : 1 5 9 3 : 1 6 5 9 8 3 : 1 8 3 : 1 6 5 9 8 3 : 1 9 8 3 : 1 (3:7, 8:5, 9: 5, 5:4, 6:4 ) (3 : 7) 6 5 9 8 3 : 2 3 : 1 5 9 8 3 : 1 5 : 1 5 9 8 3 : 2 (3:6, 8:5, 9:5, 5:6) (3:6, 5:6) 5 9 8 3 : 2 9 3 : 1 9 8 3 : 2 9 8 3 : 2 (3:7, 8:6, 9:7) (3:7, 8:6, 9:7) 9 8 3 : 3 3 : 1 8 3 : 2 8 3 : 3 (3:9, 8:8) (3:9, 8:8) 8 3 : 3 3 : 2 3 : 4 (3 : 9) (3 : 9) 3 ∅ ∅ ∅ ∅ ∅ Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở Sinh các tập mục phổ biến Sinh các tập mục phổ biến bằng cách xây dựng lầm lượt các mẫu điều kiện cơ sở và các cây điều kiện FP-Tree bởi mỗi bộ xử lý. Khi một nhánh của FP-Tree điều kiện được xây dựng, ta thu được các tập hợp các mục khả năng như trong thuật toán FP-Growth tuần tự được trình bày trong [15]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 Mô hình song song được áp dụng là mô hình Chủ - Tớ. Bộ xử lý Chủ chuyển các mục cơ sở cần được khai phá cho các mục này và sinh các tập mục phổ biến. Trong mô hình này, khi một bộ xử lý Tớ hoàn thành nhiệm vụ, nó nhận được nhiệm vụ khác ngay lập tức, điều này làm cho các bộ xử lý bận cho đến khi kết thúc quá trình khai phá. Ở đây, việc cân đối khối lượng công việc xảy ra trong thời gian thực thi (runtime). Mô hình Chủ - Tớ được duy trì cho đến khi tất cả các tập mục phổ biến được sinh ra ứng với mỗi mục phổ biến trong F1-itemset. Sau đó tất cả các bộ xử lý Tớ này chuyển các tập mục phổ biến mà nó sinh ra đến bộ xử lý Chủ, giai đoạn khai phá kết thúc. Tương ứng với mỗi mục i ∈ F1-itemset, các tập mục phổ biến được sinh đệ quy bởi các mẫu điều kiện cơ sở và các FP -Tree điều kiện được chỉ ra trong hình 3.9. Ở đây, ta có 3 bộ xử lý và vì thế 2 bộ xử lý Tớ P1, P2 sinh tập mục phổ biến; Hình 3.9 cũng chỉ ra các tập mục phổ biến của CSDL D. Bộ xử lý 1 Bộ xử lý 2 Item Các FP-Tree điều kiện mức 1 Các tập mục phổ biến Item Các FP-Tree điều kiện mức 1 Các tập mục phổ biến 7 (3 7 : 6) 0 (3 0 : 7) 6 Mức đệ qui đầu tiên (3 6 : 6) (5 6 : 6) 5 (9 5 : 7) (3 5 : 7) (8 5 : 6) (3 9 5 : 7) (3 8 5 : 6) (8 9 5 : 6) (8 3 9 5 : 6) 8 (3 8 : 9) 9 (3 9 : 9) (8 9 : 8) (3 8 9 : 8) Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P1 và P2 Nội dung thuật toán FP-Growth Vào: Các phân hoạch CSDL DN/P và minsup. Ra: Tập các mục phổ biến Phương pháp: P1 3:6 P2 3:7 5:5 3:6 5:1 P1 P1 3:9 P2 3:9 8:8 9:1 8:6 3:7 P2 9:6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 1) Quét CSDL cục bộ DN/P; 2) Tính số đếm hỗ trợ cục bộ của mỗi mục i flocal(i); 3) if (Bộ xử lý chủ) then 4) for (mỗi Bộ xử lý Tớ) do 5) Nhận flocal(i); 6) Gán F1-itemset = {i| ∑flocal(i); ≥ minsup, ∀ i} và truyền F1-itemset đến các Bộ xử lý Tớ 7) else Chuyển flocal(i), ∀ i đến Bộ xử lý chủ và Nhận 1-itemset ph ổ biến F1-itemset; 8) Xây dựng FP-Tree cục bộ FPTlocal của các mục trong F1-itemset bằng cách quét DN/P cục bộ. 9) Duyệt toàn bộ FPTlocal và sinh ra các mẫu điều kiện cơ sở và truyền đến tất cả các bộ xử lý; 10) if (Bộ xử lý chủ) then begin 11) for(mỗi mục phổ biến i ∈ F1-itemset) do // Lập lịch tạo ra các CFPTs 12) Nh ận yêu cầu Bộ xử lý Tớ và chuyển mục i; 13) for(mỗi mục phổ biến i ∈ F1-itemset) do // Lập lịch cho việc khai phá 14) Nh ận yêu cầu Bộ xử lý Tớ và chuyển mục i cần được khai phá; 15) for(mỗi Bộ xử lý Tớ) do 16) Tập hợp các tập mục phổ biến và xuất tất cả các tập mục phổ biến; 17) end 18) else do //hợp nhất các mẫu điều kiện cơ sở 19) Yêu c ầu mục i tiếp theo và sinh FP-Tree đi ều kiện CFPTi cho mục i; 20) until (hết các mục phổ biến); 21) Truyền CFPTs đến tất cả các Bộ xử lý (từ Bộ xử lý Chủ) và nhận tất cả các CFPTs; 22) do 23) Yêu c ầu mục i tiếp theo và gọi FP-Growth-OneItem (CFPTs, null i); 24) until (hết các mục phổ biến); 25) Chuyển các tập mục phổ biến đến Bộ xử lý Chủ; Thủ tục con FP-Growth-OneItem (Tree, α, i) Phương pháp: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 1) if(Tree chứa đường dẫn đơn) and (i ≠ null) then 2) Sinh tập mục có độ hỗ trợ ≥ minsup đối với mỗi tổ hợp các nút trong đường dẫn 3) else if(i ≠ null) then 4) Sinh tập mục β = i ∪ α và Xây dựng các mẫu điều kiện cơ sở của β và CFPTβ 5) else for mỗi i trong bảng tiêu đề của Cây 6) Sinh tập mục β = i ∪ α và Xây dựng các mẫu điều kiện cơ sở của β và CFPTβ 7) if CFPTβ ≠ ∅ then FP-Growth-OneItem(CFPTβ, β, null); 3.3.5 Thuật toán song song Eclat 1) Nhóm tập mục và giao dịch Phương pháp đ ể nhóm các tập mục phổ biến có liên quan với nhau bằng cách sử dụng lược đồ phân chia lớp tương đương. Mỗi lớp tương đương chứa tập các mục ứng cử quan h ệ tương đương với nhau. Bên cạnh, ta cũng sử dụng kỹ thuật tổ chức CSDL theo chiều dọc để nhóm các giao dịch có liên quan với nhau. Phân lớp tương đương Gọi Lk là tập các itemset phổ biến. Không mất t ính tổng quát, giả sử Lk được sắp xếp theo thứ tự từ điển. Ta có thể phân hoạch các tập mục trong Lk thành các lớp tương đương như sau: Nếu các phần t ử trong Lk có k – 1 thành viên đầu tiên giống nhau thì chúng thuộc cùng một lớp. Ký hiệu: Lớp tương đương chứa a là Sa = [a]. Trong phạm vi một lớp, ta sinh k-itemset ứng cử bằng cách kết nối tất cả ( ) 2/1SS 2 S ii i −=      cặp với tiền tố là định danh của lớp. Trong đó: |Si| là số phần tử của lớp có định danh là i. Các k- itemset ứng cử ứng cử được sinh ta từ các lớp khác nhau sẽ độc lập với nhau. Tổ chức cơ sở dữ liệu Thuật toán Eclat sử dụng cách tổ chức dữ liệu theo chiều dọc. Với các tổ chức dữ liệu theo chiều dọc, một CSDL gồm một danh sách các mục. Mỗi mục Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 xác định một danh sách các định danh của giao dịch có chứa mục đó, ký hiệu tid-List. Những ưu điểm của cách tổ chức theo chiều dọc: - Nếu tid-List đã được sắp theo thứ tự tăng dần thì độ hỗ trợ của k-itemset ứng cử có thể đã được tính toán bởi phép lấy giao các tid-List của hai (k-1)- subset b ất kỳ, Với cách tổ chức này, thuật toán không cần phải duy trì cấu trúc dữ liệu phức tạp, không như cây băm và c ũng không phải sinh ra tất cả các k-subset c ủa các giao dịch hoặc thực hiện các thao tác tìm kiếm trên cây băm. - Các tid-List chứa tất cả các thông tin liên quan về một tập mục, vì vậy, khi tính độ hỗ trợ cho một tập mục không cần phải quét toàn bộ CSDL. Vì tất cả các thông tin về một lớp tương đương là được nhóm cùng nhau nên có thể sinh ra các tập mục phổ biến trước khi chuyển sang lớp tiếp theo. Ví dụ: Giả sử tid-List của AB, AC là: T(AB) = {1, 5, 7, 10, 50}; T(AC) = {1, 4, 7, 10, 11} Thì T(AB) ∩ T(AC) sẽ cho T(ABC) = {1, 7, 10} Ta có thể tính ngay độ hỗ trợ bằng cách đếm số phần tử trong tid-List, nếu số phần tử của tid-List lớn hơn hoặc bằng độ hỗ trợ tối thiểu thì chèn ABC vào L3. 2) Thuật toán song song Eclat Nội dung thuật toán Begin /* Pha khởi tạo*/ 1) Duyệt qua các phân hoạch CSDL cục bộ 2) Tính toán số đếm hỗ trợ cục bộ cho tất cả các 2-itemset 3) Xây dựng số đếm hỗ trợ tổng thể cho các tập mục chứa trong L2 /*Pha biến đổi*/ 4) Phân hoạch L2 thành các lớp tương đương 5) Lập lịch L2 trên tập các bộ xử lý 6) Tổ chức phân hoạch dữ liệu cục bộ theo chiều dọc 7) Truyền các tid-List có liên quan tới các bộ xử lý khác 8) L2 cục bộ = nhận các tid-List từ các bộ xử lý khác /*Pha đồng thời*/ 9) forparallel mỗi lớp tương E2 trong L2 cục bộ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 Compute_Frequent(E2) /*Pha rút gọn*/ 10) Tập hợp các kết quả đưa ra các kết hợp end. Giải thích thuật toán 1) Phần khởi tạo Pha khởi tạo bao gồm việc tính toán tất cả các 2 -itemset phổ biến trong CSDL cần khai phá. Ta không cần tính số đếm hỗ trợ của các 1 -itemset vì việc xác định số đếm hỗ trợ của 2 -itemset có thể đạt được chỉ trong một lần duyệt CSDL. Để tính toán cho các 2-itemset, trên mỗi bộ xử lý sử dụng một mảng cục bộ và tiến hành chỉ số hóa các mục trong CSDL theo cả hai chiều. Mặt khác, mỗi bộ xử lý tính số đếm hỗ trợ cục bộ cho các 2-itemset và thực hiện phép lấy tổng rút gọn (sum-reduction) của tất cả các bộ xử lý để xây dựng các số đếm hỗ trợ tổng thể. Kết thúc pha khởi tạo, tất cả các bộ xử lý đều có những số đếm hỗ trợ tổng thể của tất cả các 2-itemset phổ biến L2 trong CSDL. 2) Pha biến đổi gồm 2 bước Bước 1: Đầu tiên L2 được phân hoạch thành các lớp tương đương. Sau đó các lớp tương đương này được gán cho các bộ xử lý sao cho cân bằng nhau. Bước 2: CSDL đã được biến đổi từ định dạng theo chiều ngang thành chiều dọc và được phân phối lại. Do đó, trong bộ nhớ cục bộ của mỗi bộ xử lý, các tid-List của tất cả các 2-itemset trong một lớp tương đương bất kỳ được nó gán cho nó. Lập lịch phân lớp tương đương Đầu tiên, ta phân hoạch L2 thành các lớp tương đương bằng cách sử dụng tiền tố chung như mô tả ở trên. Tiếp theo, phân chia cho mỗi bộ xử lý một lớp tương đương. Mỗi lớp tương đương được gán một trọng số dựa vào số các phần tử trong một lớp. Vì phải khảo sát tất cả các cặp trong bước lặp tiếp theo, nên ta gán trọng số       2 m cho mộ t lớp với m là số các phần tử của lớp tương đương tương ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 68 Sắp xếp các lớp dựa theo các trọng số và lần lượt gán cho bộ xử lý đã nạp ít nhất, nghĩa là bộ xử lý đó có trọng số toàn phần của các lớp nhỏ nhất. Nếu ước lượng tốt được số các tập mục phổ biến mà có thể nhận được từ một lớp tương đương thì có thể sử dụng ước lượng này làm một trọng số. Trong phạm vi một lớp, cũng có thể lấy độ hỗ trợ trung bình của các tập mục làm trọng số. Biến đổi CSDL theo chiều dọc Sau khi phân hoạch các lớp tương đương cân bằng giữa các bộ xử lý, ta biến đổi CSDL cục bộ từ định dạng theo chiều ngang theo chiều dọc. Điều này có thể thực hiện được trong 2 bước: Bước 1: Mỗi bộ xử lý duyệt CSDL cục bộ của nó và xây dựng các tid-List cục bộ cho tất cả các 2-itemset. Bước 2: Mỗi bộ xử lý cần xây dựng các tid-List toàn cục cho các tập mục trong các lớp tương đương của nó. Do đó, nó phải gửi các tid -List này cho các bộ xử lý khác và nhận các tid-List từ các bộ xử lý khác gửi đến. 3) Pha đồng thời Cơ sở dữ liệu đã được phân bố lại, vì vậy các tid -List của tất cả các 2 - itemset trong các lớp tương đương cục bộ của nó là đã thường trú trên đĩa cục bộ. Mỗi bộ xử lý có thể tính toán tất cả các tập mục phổ biến một cách độc lập. Nó đọc trực tiếp từ bộ nhớ cục bộ các tid-List của các 2-itemset, sau đó sinh tất cả các tập mục phổ biến có thể trước khi chuyển sang bước tiếp theo, bước này bao gồm việc quét phân hoạch CSDL cục bộ đã được biến đổi một lần. Trong phạm vi mỗi lớp tương đương, cần khảo sát tất cả các cặp 2-itemset và thực hiện lấy giao các tid-List tương ứng. Nếu số các phần tử của tid-List kết quả lớn hơn hoặc bằng độ hỗ trợ tối thiểu thì tập mục mới được bổ sung vào L3. Sau đó, tiếp tục phân hoạch L 3 thành các lớp tương đương dựa trên các tiền tố chung độ dài bằng 2. Quá trình này được lặp lại thủ tục được thực hiện như sau: Begin Compute_Frequent(Ek-1) for tất cả các itemset I1 và I2 trong Ek-1 if((I1.tidList ∩ I2tidList) ≥ minsup) Bổ sung (I1 ∪ I2) vào Lk; Phân hoạch Lk thành các lớp tương đương; forparallel mỗi lớp tương đương Ek trong Lk Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 69 Compute_Frequent(Ek); End Compute_Frequent 4) Pha rút gọn Tại thời điểm cuối của pha đồng thời, chúng ta trích rút các kết quả từ mỗi bộ xử lý và đưa ra kết quả. Quá trình thực hiện các bước truyền thông khác nhau của thuật toán. *) Giai đoạn khởi tạo: Khi đã thu được các số đếm hỗ trợ của tất cả các 2 -itemset, ta cần thực hiện một phép lấy tổng rút gọn để tính số đếm tổng thể. Ta chỉ định một mảng kích thước       2 m (m là số các mục) trên vùng kênh bộ nhớ dùng chung, sau đó mỗi bộ xử lý truy cập mảng chung này (theo phương thức loại từ lẫn nhau) để tăng số đếm hỗ trợ hiện hành lên bởi các số đếm hỗ trợ cục bộ của nó và rồi đợi ở rào chắn cho tới bộ xử lý cuối cùng thực hiện xong việc truy cập mảng dùng chung để tăng số đếm hỗ trợ. Các số đếm hỗ trợ cục bộ được sử dụng để xây dựng các tid-List đảo toàn cục. *) Giai đoạn biến đổi Mỗi bộ xử lý quét phân hoạch CSDL cục bộ của nó lần thứ hai và xây dựng các tid-List theo chiều dọc đối với tất cả các 2 -itemset phổ biến L 2. Vì CSDL gốc ban đầu được phân hoạch theo dạng khối nên CSDL đảo của mỗi bộ xử lý gồm các vùng định danh không liên tiếp. Ta sử dụng thông tin này cùng với thông tin của các số đếm hỗ trợ cục bộ để đặt tid-List của các bộ xử lý khác gửi đến vào các khoảng trống thích hợp, vì vậy tid-List toàn cục thu được xuất hiện theo thứ tự từ điển, Với các lưu giữ này, chúng ta tiết kiệm được chi phí sắp xếp cho các tid-List các giao dịch được phân tán một cách ngẫu nhiên. Quá trình biến đổi được hoàn thành qua 2 bước sau: Bước 1: Biến đổi tid-List cục bộ. Trước tiên, ta chia L2 thành hai nhóm. Các tập mục thuộc các lớp tương đương mà được gán cho bộ xử lý cục bộ, kí hiệu là G, các tập mục còn lại thuộc các lớp tương đương khác, kí hiệu là R. Với mỗi bộ xử lý Pi, bộ nhớ dành ra một vùng nhớ có kích thước Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 ∑∑ ∈∈ + RrGg Pircountpartialgcountglocal ),(_)(_ Với g ∈ G, r ∈ R: các tập mục partial_count(r, Pi): Số đếm hỗ trợ của tập mục r trên bộ xử lý Pi. Sau đó, mỗi bộ xử lý thực hiện việc biến đổi và ghi tid -List của các phần tử của G vào các khoảng trống thích hợp. Các phần tử của R được để trống. Hình 3.10 dưới đây mô tả bước biến đổi CSDL trên ba bộ xử lý: L2 12 13 15 23 25 34 35 Số đếm hỗ trợ tổng thể 10 13 10 15 16 14 17 Số đếm hỗ trợ cục bộ P0 3 2 10 4 11 8 5 P1 3 10 0 7 1 3 5 P2 4 1 0 4 4 3 7 Phân chia L2 thành các l ớp tương đương và gán cho các bộ xử lý P0, P1, P2 P0 – (12, 13, 15); P1 – (23, 25); P2 – (34, 35). Kí hiệu: tid- List của P0, P1, P2 lần lượt là: Lớp tương đương cục bộ (G) 12 13 15 Lớp tương đương cục bộ sau khi truyền 12 13 15 Lớp tương đương cục bộ (G) 23 25 Lớp tương đương cục bộ sau khi truyền 23 25 Lớp tương đương cục bộ (G) 34 35 Lớp tương đương cục bộ sau khi truyền 34 35 Lớp khác (R) 23 25 34 35 Lớp khác (R) 23 25 34 35 Lớp khác (R) 23 25 34 35 Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 71 Bước 2: Truyền tid-List Một khi việc biến đổi CSDL cục bộ hoàn thành, ta cần phải nhận các tid- List của tất cả các 2-itemset trong G từ các bộ xử lý khác truyền đến và truyền các tid-List của R đến các bộ xử lý khác. Các tid-List đến được sao chép vào các khoảng trống thích hợp. Vì các phần giao dịch là phân biệt tăng đều, các tid-List của các tập mục trong G đã được viết ra ngoài đĩa, còn trong R thì bị loại bỏ. Để truyền các tid-List cục bộ qua kênh bộ nhớ, chúng ta sử dụng lợi thế của việc truyền thông điệp nhanh ở mức người sử dụng. Mỗi bộ xử lý xác định kích thước bộ đệm (2MB) cho một vùng truyền, một vùng nhận và dùng chung một định danh. Việc truyền thông được tiến hành theo cách khóa luân phiên các pha ghi đọc. Trong pha ghi, mỗi bộ xử lý ghi các tid-List của các tập mục trong P vào vùng truyền của nó ch o đến khi đạt đến giới hạn không gian bộ đệm. Tại thời điểm này, nó đi vào pha đọc, nó lần lượt quét vùng nhận của mỗi bộ xử lý và đặt các tid-List này của G vào các khoảng trống thích hợp. Khi vùng đọc đã được quét xong, nó đi vào pha ghi. Quá trình này được lặp lại cho đến khi nhận được tất cả các tid-List bộ phận. Tại thời điểm cuối của pha này, CSDL được định dạng theo chiều dọc. Sau đó, mỗi bộ xử lý đi vào pha đồng thời và tính toán các tập mục phổ biến như mô tả ở trên. Việc phép rút gọn cuối cùng được thực hiện tương tự như phép rút gọn trong pha khởi tạo. 3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán 3.4.1. Phân tích và đánh giá thuật toán song song Đánh giá thuật toán tuần tự có thể căn cứ chủ yếu vào thời gian thực hiện tính theo hàm của kích cỡ dữ liệu vào (input). Hàm này được gọi là độ phức tạp tính toán thời gian f(n) của thuật toán và được ký hiệu là O(f(n)). Một cách hình thức, O() được định nghĩa như sau: Một thuật toán có độ phức tạp tính toán tính toán f(n) = O(g(x)) ⇔ Tồn tại số dương C và số nguyên x0 sao cho 0 ≤ f(x) ≤ C * g(x), với mọi số lượng dữ liệu vào x ≥ x0. O(1) ký hiệu cho một hằng số bất kỳ. Ngoài ra, độ phức tạp tính toán của thuật toán song song còn phụ thuộc vào kiến trúc máy tính song song và số lượng bộ xử lý được phép sử dụng trong hệ thống và do vậy phụ thuộc vào thời gian trao đổi dữ liệu giữa các bộ xử lý. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 72 Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song. Giả sử rằng mô hình tính toán của chúng ta có p bộ xử lý; dẫn đến mức độ song song có giới hạn; ngược lại, không bị giới hạn khi số lượng bộ xử lý không bị chặn. Mức độ hiệu quả của thuật toán được thể hiện ở mức độ song song của thuật toán. Là số lượng cực đại các phép toán độc lập có thể thực hiện đồng thời ở mỗi thời điểm thực hiện của thuật toán. Ký hiệu p(w) là độ song song của thuật toán, thì thuật toán đạt hiệu quả để giải bài toán có kích cỡ w là thuật toán chỉ cần sử dụng nhiều nhất p(w) bộ xử lý. Độ phức tạp thời gian của thuật toán song song sử dụng p bộ xử lý để giải một bài toán có kích cỡ n là hàm f(n, p) xác định thời gian cực đại trôi qua giữa điểm bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết thúc của các bộ xử lý đối với bộ dữ liệu vào bất kỳ. Có hai thao tác khác nhau trong các thuật toán song song: Các phép toán cơ sở như: +, -, *, /, AND, OR,… Các phép truyền dữ liệu trên kênh truyền. Vì độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép toán cơ s ở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Nên từ đó suy ra, đ ộ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình tính toán mà còn ph ụ thuộc vào bộ xử lý được sử dụng. Định nghĩa liên quan đến độ phức tạp của giải thuật song song là: Định nghĩa 3.1: Một thuật toán song song có độ phức tạp tính toán O(t) với p bộ xử lý khi nó thực hiện nhiều nhất là O(t * p) phép toán cơ sở. Định nghĩa 3.2: Một thuật toán song song có độ phức tạp tính toán O(t) sử dụng nhiều bộ xử lý để thực hiện O(e) phép toán cơ sở khi cài đặt với p bộ xử lý thì sẽ có độ phức tạp thời gian là O([e/p]+t). Định nghĩa 3.3: Một thuật toán song song có độ phức tạp tính toán O(t) với p bộ xử lý có thể cài đặt với [p/f] bộ xử lý (1≤ f ≤ p) thì sẽ có độ phức tạp thời gian là O(f * t). Ngoài ra, trong đánh giá thuật toán song song chúng ta còn cần phải xét tới độ tăng tốc và hiệu suất của nó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 73 3.4.2. So sánh việc thực hiện các thuật toán Dựa vào việc thực thi của thuật toán trên CSDL khác nhau cho thấy thuật toán FP-Growth thực thi nhan h nhất, tiếp đến là thuật toán Eclat, thuật toán Candidate distribution, CD, DD. Việc theo thứ hạng này mang tính tương đối, mỗi thuật toán đều có những ưu điểm và nhược điểm riêng. Trong số các thuật toán khai phá dữ liệu luật kết hợp song song, các thuật toán song song được cài đặt dựa trên thuật toán Apriori (chẳng hạn như thuật toán CD, DD, Candidate distribution) được sử dụng phổ biến bởi vì thực thi chúng đơn giản và dễ dàng. Hơn nữa, các luật kết hợp có thể được sinh trực tiếp dựa vào cách thức khai phá tập mục. Bởi vì các tập mục ứng cử được sinh ta thì tất cả các thông tin của tập con đều được tính toán. Tốc độ thực hiện các thuật toán này tỉ lệ với số lượng các giao dịch nhưng có thể gặp khó khăn trong việc xử lý quá nhiều mục và nhiều mẫu khi CSDL quá lớn. Thuật toán song song Eclat có ưu điểm là tính toán nhanh độ hỗ trợ thông qua tập giao dịch tid-List. Thuật toán được thiết kế dựa trên mô hình song song thao tác, có tốc độ thực thi nhanh trên hệ thống đa bộ xử lý bộ nhớ phân tán. Hạn chế chủ yếu của thuật toán này là chúng cần phải sinh ra và phân bố lại các tid-List. Hơn nữa, với một tập mục phổ biến có kích thước lớn, các phần chung chủ yếu của các tid-List này được lấy giao lặp lại nhiều lần đối với tất cả các tập con của nó. Để giảm bớt tình trạng này, một cách thiết lập tối ưu khác là chỉ kiểm tra những thay đổi trong tid-List thay cho việc lưu giữ các tid-List toàn cục thông qua các vòng lặp sao cho nó giảm đáng kể khối lượng dữ liệu được tính toán. Thuật toán FP-Growth xử ký lượng lớn CSDL rất hiệu quả và có tốc độ thực thi tỷ lệ rất hiệu quả so với lượng giao dịch lớn, sự lặp lại nhiều lần hay lặp lại nhiều lần cục bộ các giao dịch sẽ được kết hợp lại tạo thành các nhánh của FP-Tree. Tuy nhiên ích lợi này không tăng khi tăng thêm số lượng bộ xử lý bởi vì nhiều FP-Tree cho các tập giao dịch khác nhau là hoàn toàn dư thừa. Lợi ích này cũng rất hạn chế đối với các CSDL rải rác. Thuật toán này có thể xử lý một số lượng lớn các mục bằng việc gán mục này cho nhiều bộ xử lý mà không quan tâm về không gian lưu trữ các tập mục. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 74 3.5. Kết luận chương 3 Trong chương này đã trình bày nguyên lý thiết kế thuật toán song song và hai hướng tiếp cận chính trong việc thiết kế thuật toán khai phá luật kết hợp song song đó là: Mô hình song song dữ liệu và mô hì nh song song giao tác. Một số thuật toán khai phá luật kết hợp song song được thiết kết dựa trên hai mô hình này như thuật toán Count Distribution, Data Distribution, Candidate Distribution, Eclat, FP-Growth. Chương này cũng đánh giá chung về những ưu nhược điểm và so sánh việc thực hiện của mỗi thuật toán làm cơ sở cho việc cải tiến thuật toán và phát hiện các thuật toán song song mới Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 75 KẾT LUẬN 1. Kết quả đạt được trong luận văn Khai phá dữ liệu là một lĩnh vực quan trọng, nó bao gồm nhi ều lĩnh vực và nhiều kỹ thuật khác nhau. Luận văn đề cập đến các nội dung về phát hiện tri thức, khai phá dữ liệu. Ứng dụng của khai phá dữ liệu là rất lớn và có ích trong mọi hoạt động sản xuất, kinh doanh và trợ giúp cho việc hoạch định chiến lược của các nhà quản lý cũng như hỗ trợ ra quyết định. Bên cạnh, luận văn còn đề cập đến những khó khăn, thách thức trong việc ứng dụng và nghiên cứu các kỹ thuật khai phá dữ liệu. • Về mặt lý thuyết, khai phá dữ liệu là một công đoạn trong tiến trình lớn , tiến trình khám phá tri thức từ CSDL. Phương pháp khai phá dữ liệu có thể là: phương pháp sử dụng cây quyết định và luật, phương pháp quy nạp, phương pháp phát hiện luật kết hợp, các phương pháp dựa trên mẫu, mô hình phụ thuộc dựa trên đồ thị xác suất, các phương pháp phân lớp và hồi quy phi tuyến tính…, các phương pháp trên có thể áp dụng trên dữ liệu thông thường và trên tập mờ. Trong luận văn đã trình bày chi tiết các vấn đề về khai phá luật kết hợp: từ các khái niệm cơ sở, bài toán xuất phát đến mô hình hình thức , các thuật toán khai phá luật kết hợp cơ sở và các thuật toán khai phá luật kết hợp trọng số, luật kết hợp định lượng và luật kết hợp tổng quát. • Về thuật toán khai phá luật kết hợp, luận văn trình bày một số thuật toán tuần tự tiêu biểu về khai phá luật kết hợp như: Apriori, phân hoạch, AIS, SETM,… • Trên cơ sở các thuật toán tuần tự, luận văn trình bày chi tiết các thuật toán song song như Count Distribution, Data Distribution, Candidate Distribution, Eclat, FP-Growth. Việc đánh giá thuật toán làm rõ bản c hất của luật kết hợp cũng là một trong những nội dung được trình bày trong luận văn. 2. Hướng nghiên cứu tiếp theo Trên cơ sở những nghiên cứu đã được trình bày trong luận văn, tiếp tục nghiên cứu sâu hơn các thuật toán khai phá luật kết hợp song song , tìm cách cải tiến nhằm khắc phục các nhược điểm của các thuật toán song song hiện có và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 76 các thuật toán khai phá dữ liệu song song khác để áp dụng vào một số bài toán khai phá dữ liệu phù hợp cho giai đoạn hiện nay như: quy luật thị trường, chứng khoán và bất động sản, dự đoán rủi ro tín dụng, định hướng kinh doanh, y tế… Trong quá trình học tập, tìm hiểu và nghiên cứu cùng với khoảng thời gian làm luận văn, tôi đã cố gắng tập trung tìm hiểu và tham khảo các tài liệu liên quan. Tuy nhiên do thời gian nghiên cứ u có hạn nên không tránh khỏi những thiếu sót rất mong nhận được sự nhận xét và những đóng góp ý kiến của các thầy cô giáo và những ai quan tâm để luận văn được hoàn thiện hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 77 TÀI LIỆU THAM KHẢO Tiếng việt 1. Đoàn Văn Ban, Nguyên Mậu Hân (2006) Xử lý song song và phân tán, Nxb Khoa học & Kỹ thuật, Hà Nội. 2. Nguyễn Thanh Bình (2007), Khai phá dữ liệu: Khái niệm và kỹ thuật, Huế. 3. Đỗ Phúc (2006), Giáo trình khai phá dữ liệu , Nxb Đại học Quốc gia TP Hồ Chí Minh. 4. Hồ Thuần, Hồ Cẩm Hà (2006), Các hệ cơ sở dữ liệu Lý thuyết và Thực hành, Tập 2, Nxb Giáo dục. 5. Nguyễn Thanh Thủy (2003), Phát hiện tri thức và khai phá dữ liệu: Công cụ, phương pháp và ứng dụng, Bài gi ảng Trường Thu, Hà Nội. Tiếng Anh 6. A. Savaere, E Omiecinski and S.Navathe (1995), An efficient algorihm for mining association rules in large databases, In 21st VLDB Con&. 7. Agrawal and J.Shafer (1996), Parallel mining of association rules, In IEEE Trans, on Knowledge and Data Engg, pages 8(6): 962 – 969. 8. CAI, Chun Hing (1998), Mining Association Rules With Weighted Items, The Chinese University of Hong Kong, August. 9. H.Mannila, H. Toivonen and I.Verkamo (1994), efficient algorithms for discovering association rules, In AAAI Wkshp, Knowledge Discoverry in Databases, July. 10. J.Han, J.Pei and Y.Yin (2000), Mining Frequent Pattens Without Candidate Generation, In ACM SIGMOD. 11. J.S.Park, M.Chenand P.S.Yu (1995), Efficient parallel data mining for association rules, In ACM Intl, Conf Information and Knowledge Management, November. 12. Jiamwei Li, Ying Lui, Wei-Keng Liao, Alok Choudhay (2006), Parallel Data Mining Algorithms for Association Eules and Clustering, by CRC Press, LLC. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 78 13. Kwok-Leung Tsui, Victoria C,P. Chen, Wei Jiang, Y. Alp Aslandogan, (2001), Data Minning Methods and applications. 14. M, Holshimer, M.Kersten, H.Manila and H. Toivonen (1995), A perspectiveon databases and data mining, In lsr Ind, Conf Knowledge Discovery and Data Mining, August. 15. M.Houtsma and A.Swami (1995), Set-oriented miningof association rules in relational databases, In 1 lth Intln, Conf Data Engineeng. 16. M.J. Zaki, S.Parthasarathy, W.Li and M.Ogihara (1997), Evaluation of sampling for data mining of association rules, In 7 th Intl, Wkshp. Research Issues in Data En, gg, Apr. 17. Ming-Syan Chen, Jiawei Han and Philip S.Yu (1996), Data Mining: An Overview from a Databases Perpective, IEEE Transactions on Knowledge and Data Engineering, Vol.8, No.6, pp. 866-883. 18. Margaret H. Dunham, Yongqiao Xiao, Le Gruenwald, Zahid Hossain, (2003) A survey of Assocition rules, Department of Computer Science and Engineering Southerm Methodist University Dallas. 19. O.R.Zaiane, Mohammad El-Haijj and Paul L (2001), Fast Parallel Association Rule Mining Without Candidacy Generation, Proc. Of the IEEE 2001 International Conference in Data Minning (ICDM’2001), San Jose, CA, USA, November 29-December 2. 20. R Agmwal, H.Manila, R. Srikant, H. Toivonen and A. 1. Verkamo (1996), Fast discovery of association rules, In U.Fayyad and et al, editors, Advances in Knowledge Discovery and Data Minning. MIT Press. 21. R. Agrawal and R. Srikant, (1994), Fast algorithms for minning association rules, In 20th VL.DBConf, Sept. 22. R. Agrawal, T. Imielinski and A. Swami (1993), Minning association rules between sets of items i large databases, In ACM SIGMOD Intil. C@ Managenment of Data, May. 23. Two Crows (2005), Introduction to Data Minning and Knowledge Discovery, Edition third. 24. Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth, (2002) From Data Minning To Discory Knowledge in Database. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 79 Địa chỉ trên Internet 25. ://www.cs.cmu.edu/~scandal/nesl/algorithms.html 26. ://computing.llnl.gov/tutorials/parallel_comp/index.html 27. MPI home page. ._.