tailieunhanh - Báo cáo " Thuật toán khai thác dữ liệu tăng trưởng"

Thuật toán khai thác dữ liệu tăng trưởng | TẠP CHÍ KHOA HỌC VA CÔNG NGHỆ Tập 45. số 2 2007 Tr. 9-18 THUẬT TOÁN KHAI THÁC DỮ LIỆU TĂNG TRƯỞNG NGUYÊN XUÂN HUY ĐOẢN VĂN BAN NGUYÊN HỮU TRỌNG HUỲNH VĂN ĐỨC I. MỞ ĐÀU Bài toán tìm các luật kết hợp là bài toán cơ bản trong khai thác dữ liệu gồm hai bước chính như sau bước một tìm tất cả các tập thường xuyên theo ngưỡng JS0 cho trước và bước hai dựa vào các tập thường xuyên tìm các luật kết hợp. Tất cả khó khăn của việc giải quyết bài toán tập trung ở bước một một công việc tốn nhiều thời gian là xác định tất cả các tập mục dữ liệu thường xuyên theo một ngưỡng Sữ cho trước. Sự phát triển của bài toán khai thác dữ liệu được Qiankun Zhao tổng kết trong 1 . Từ thuật toán AIS lần đầu tiên được Agrawal. R giới thiệu nãm 1993 trong 2 thuật toán Apriori năm 1996 3 rồi từng bước được cải tiến thuật toán FP-Tree do Han J Pei H. Yin Y. đưa ra năm 2000 4 thuật toán DCI được nhóm của Claudio Lucchese đề nghị năm 2005 5 thuật toán CHARM được nhóm Mohammed J. Zaki đưa ra năm 2005 6 thuật toán LCM được nhóm Takeaki Uno đưa ra năm 2006 7 thuật toán BFS được Vicky Choi đưa ra năm 2006 8 . chủ yếu xử lí trên tập dữ liệu xác định trước. Ta biết rằng các tập dữ liệu được bổ sung và tăng trường theo thời gian do vậy các tập thường xuyên và các luật kết hợp đã được tính toán không còn giá trị. Ngoài ra với một dữ liệu ổn định khi cần tìm các tập thường xuyên với độ hỗ trợ khác công việc phải .tính lại từ đầu. Để khắc phục điều này chúng tôi đề nghị một thuật toán tăng trưởng với ý tưởng cơ bản như sau 1 Vớì một ngữ cảnh khai thác dữ liệu T I d với T m ỊỊIỊỊ n ban đầu thuật toán tính độ hỗ trợ của tất cả các tập mục dữ liệu có trong ổ rồi lưu trữ trong tập K X Supp X I X G I và X nằm trong ít nhất một giao tác nào đó . Theo thời gian số lượng các giao tác tăng dân thuật toán chỉ tính toán với dữ liệu tăng thêm không cân tính toán lại từ đâu. Với cách to chức này khi cần tìm các tập thường xuyên thỏa mãn ngưỡng So ta chỉ cần lọc ra những tập mục dữ liệu trong K thỏa Supp X Sộ. 2 Đe tính độ