Thuật toán khai thác mẫu phổ biến hiệu quả trên cây FP-Tree

Bài viết này đề xuất một phương pháp khai thác hiệu quả dựa trên cấu trúc dữ liệu FP-Tree giúp giảm số lượng mẫu phát sinh trong quá trình khai thác. Kết quả thực nghiệm cho thấy hiệu quả của thuật toán tốt hơn so với một số phương pháp hiện có.
Nội dung trích xuất từ tài liệu:
Thuật toán khai thác mẫu phổ biến hiệu quả trên cây FP-Tree HUFLIT Journal of Science THUẬT TOÁN KHAI THÁC MẪU PHỔ BIẾN HIỆU QUẢ TRÊN CÂY FP-TREE Trần Anh Duy1, Phạm Đức Thành2 1,2 Khoa Công nghệ thông tin, Trường Đại học Ngoại ngữ -Tin học TP.HCM duy.ta@huflit.edu.vn, phamducthanh@huflit.edu.vnTÓM TẮT— Khai thác mẫu phổ biến là bài toán quan trọng trong lĩnh vực khai thác dữ liệu. Mẫu phổ biến được ứng dụngtrong nhiều lĩnh vực như hệ thống bán hàng, truy tìm mẫu thâm nhập hệ thống, xác định mẫu lặp lại trong phân tích gen ditruyền, … Đã có rất nhiều thuật toán được đề xuất để khai thác mẫu phổ biến. Các phương pháp đã đề xuất đa phần sử dụngchiến lượt phát sinh mẫu và kiểm thử. Do đó, xuất hiện rất nhiều mẫu cần phải kiểm tra. Bên cạnh đó, việc phát sinh mẫu sẽdẫn đến trường hợp các mẫu phát sinh không có trong cơ sở dữ liệu. Bài viết này đề xuất một phương pháp khai thác hiệuquả dựa trên cấu trúc dữ liệu FP-Tree giúp giảm số lượng mẫu phát sinh trong quá trình khai thác. Kết quả thực nghiệm chothấy hiệu quả của thuật toán tốt hơn so với một số phương pháp hiện có.Từ khóa— Khai thác mẫu phổ biến, luật kết hợp, dữ liệu giao tác, cấu trúc FP-Tree, khai thác tập sự kiện. I. GIỚI THIỆUKhai thác dữ liệu đã và đang thu hút rất nhiều sự chú ý trong cộng đồng nghiên cứu cơ sở dữ liệu, vì khả năngứng dụng trong nhiều lĩnh vực. Khai thác mẫu phổ biến là một kỹ thuật khai thác dữ liệu, đóng vai trò thiết yếutrong nhiều nhiều lĩnh vực khai thác như khai thác mối liên hệ, khai thác tính tương quan, xác định quan hệ nhânquả, khai thác mẫu tuần tự, khai thác tập phổ biến đa chiều, khai thác tập mẫu tối đại, xác định tính tuần hoàn,v.v…Khai thác tập phổ biến được Agrawal [1-2]đề xuất lần đầu tiên trong một bài viết về phân tích thị trường ứngdụng kỹ thuật khai thác luật kết hợp. Nhiệm vụ của luật khai thác luật kết hợp là tìm ra các mối liên hệ của cácmặt hàng khác nhau được khách hàng chọn mua, thông qua việc xác định sự xuất hiện đồng thời của các mặthàng đó trong cùng hóa đơn mua hàng tại cửa hàng. Ví dụ như dựa vào việc phân tích hóa đơn mua hàng, ngườita phát hien ra rang nhưng ngươi mua ta thường mua kèm bia trong cùng hóa đơn. Thông tin về những sảnphẩm xuất hiện trong cùng hóa đơn có thể được sử dụng để phân tích thị trường riêng biệt của từng cửa hàng,lên kế hoạch kinh doanh, sắp xếp gian hàng sao cho tiện dụng nhất cho khách hàng, phân nhóm khách hàng, …Kể từ khi xuất hiện, bài toán khai thác dữ liệu phổ biến đã nhận được sự quan tâm của giới nghiên cứu với hàngtrăm công trình khác nhau, từ nghiên cứu thuật toán khai thác [3-10] cho đến các lĩnh vực ứng dụng. Mặc dù cónhiều công trình được đề xuất để giải quyết vấn đề khai thác tập phổ biến, nhưng thiết kế phương pháp khai tháchiệu quả với từng loại dữ liệu vẫn là bài toán còn nhiều thách thức.Trong bài báo này, chúng tôi đề xuất một phương pháp khai thác mới FP-Extend dựa trên cấu trúc FP-Tree [10]đã được Han đề xuất năm 2004. FP-Extend sử dụng cấu trúc Node-List để lưu trữ vị trí của các mẫu trên cây FP-Tree phục vụ cho quá trình phát sinh mẫu từ cây. Bằng cách duyệt ngược cây kết hợp với việc lưu trữ thông tinmẫu trên Node-List, phương pháp sẽ tìm ra tất cả các tập phổ biến mà không cần tạo ra ứng viên mới.Thuật toán FP-Extend đạt được hiệu quả so với thuật toán FP-Growth ở các khía cạnh sau. Đầu tiên là thuật toánduyệt cấu trúc FP-Tree để phát sinh mẫu nên không phát sinh mẫu không tồn tại trong CSDL. Thứ hai, trong quátrình khai thác, thuật toán có kiểm tra độ hỗ trợ của các mẫu trước khi thực hiện bước khai thác kế tiếp. Do đó,thuật toán không phát sinh tất cả các mẫu có thể có giống như thuật toán FP-Tree, giúp giảm đáng kể thời giankhai thác. Thứ 3, việc lưu vết mẫu phổ biến trong Node-List cho phép nhanh chóng phát sinh mẫu kế tiếp. Đồngthời độ hỗ trợ của các mẫu được tính thông qua việc cộng dồn thuộc tính đếm của nút trong cây FP-Tree nên việckiểm tra trở nên đơn giản.Để đánh giá hiệu suất của FP-Extend chúng tôi tiến hành thực nghiệm so sánh với thuật toán FP-Growth [10] vàPrePost [9]. Kết quả thực nghiệm cho thấy thuật toán hiệu quả hơn so với các thuật toán khảo sát về thời gianthực hiện và vùng nhớ sử dụng.Phần còn lại của bài báo được sắp xếp như sau. Mục II trình bày về các công trình có liên quan. Mục III trình bàyvề thuật toán khai thác đề xuất. Mục IV trình bày kết quả thực nghiệm. Mục V là phần kết luận và hướng pháttriển trong tương lai. II. CÁC CÔNG TRÌNH LIÊN QUANHầu hết các thuật toán được đề xuất trước đây để khai thác các tập phổ biến có thể được nhóm lại thành hainhóm: phương pháp dựa trên nguyên lý Apriori [2] và phương pháp cải tiến dựa trên cây FP-Tree [7][10-12].Nguyên lý Apriori nói rằng nếu bất kỳ ite ...