TAILIEUCHUNG - Một số cải tiến thuật toán Index-BitTableFI cho khai thác tập tin phổ biến

Bài viết trình bày một số cải tiến của thuật toán Index-BitTbaleFI bao gồm: 1) Chỉ tổ chức dữ liệu BitTable theo chiều dọc để tiết kiệm bộ nhớ; 2) Kiểm tra subsume đơn giản bằng cách xét xem g(item) có là con của g(j) hay không? Công việc này không tốn nhiều thời gian; 3) Cải tiến phương pháp duyệt theo chiều sâu nhằm hạn chế việc tính phần giao giữa các tid. | Một số cải tiến thuật toán Index-BitTableFI cho khai thác tập tin phổ biến Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 9 (29), tháng 6/2013 Một số cải tiến thuật toán Index-BitTableFI cho khai thác tập tin phổ biến Improvements of Index-BittableFI Algorithm for Mining Frequent Itemsets Lê Hoài Bắc, Nguyễn Thị Bảo Chi, Võ Đình Bảy Abstract: Index-BitTableFI is an algorithm based những chi phí bất thường như chi phí tính toán lớn, on BitTable which is very effective in recent (Song & việc lưu trữ các ứng viên đòi hỏi không gian bộ nhớ Yang, 2008). It finds out itemsets based on BitTable in lớn và tính toán độ hỗ trợ của các ứng viên này rất vertical and horizontal, and also sets up sorting array phức tạp. Để giải quyết vấn đề này, thuật toán Index- and equivalent computing method to fast identify BitTableFI được đề xuất, cấu trúc BitTable được sử itemsets which occur concurrently with representative dụng theo cả chiều ngang và chiều dọc, sự tìm kiếm items. Although Index-BitTableFI algorithm reduces kép được thực hiện và không gian tìm kiếm được giảm considerablely cost of finding out candidate itemsets đáng kể. and computing the support, but if number of Tuy nhiên, ngoài việc nén dữ liệu BitTable theo transactions and items is large then intersection chiều dọc ta cần nén dữ liệu theo chiều ngang để vận computing of vector-bits in BitTable still costs time. dụng phương pháp tính toán tương đương, trong khi số Besides, finding out frequent itemsets in depth has not lượng item thường nhỏ hơn rất nhiều lần so với số used property of equivalent computing method yet. To lượng giao tác. Mặt khác thuật toán chưa vận dụng resolve this problem, some improvements for triệt để tính chất của phương pháp tính toán tương improving more performance of Index-BitTableFI đương, vì thế trong bài báo này, chúng tôi đề xuất một algorithm are proposed in this research. số cải tiến bao gồm: không cần lưu trữ dữ .

• Kĩ thuật Viễn thông
• Thuật toán Index BitTableFI
• Tổ chức dữ liệu BitTable
• Kiểm tra subsume
• Thuật toán Apriori
• Cấu trúc BitTable