Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng

Bài viết Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng trình bày về thuật toán khai phá luật kết hợp trên cơ sở dữ liệu gia tăng theo chiều dọc. Sau đó, tác giả xây dựng thực nghiệm trên bộ dữ liệu mẫu để đánh giá so sánh với thuật toán Apriori.
Nội dung trích xuất từ tài liệu:
Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG Nguyễn Ngọc Quỳnh Châu Trường Đại học Thủy lợi, email: chaunnq@tlu.edu.vn 1. GIỚI THIỆU CHUNG thường xuyên, thủ tục Candidate xây dựng tập ứng viên Ck+1 từ Lk. Thủ tục Candidate là Khai phá luật kết hợp là một kỹ thuật được thủ tục quan trọng trong giải thuật Gia tăng 1 sử dụng trong khai phá dữ liệu nhằm tìm ra để tìm ra tập mục ứng viên (là những tập mục các phần tử thường xuất hiện cùng nhau dữ liệu có khả năng trở thành tập mục thường trong cơ sở dữ liệu. Từ đấy rút ra được các xuyên). Thủ tục này trải qua ba bước: luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác.  Bước 1: Phân chia Lk thành các lớp Cơ sở dữ liệu gia tăng hay cơ sở dữ liệu tương đương Pi. tăng trưởng (incremental database) là cơ sở  Bước 2: Xây dựng tập W (mỗi phần tử dữ liệu mà các giao tác (hoặc các mục dữ của W gồm k+1 mục dữ liệu) bằng cách kết liệu) tăng lên theo thời gian. Bài báo này sẽ nối tiền tố Zi của Pi với mỗi cặp (x, y) LZi. trình bày về thuật toán khai phá luật kết hợp  Bước 3: Xây dựng tập ứng viên Ck+1 từ trên cơ sở dữ liệu gia tăng theo chiều dọc W. Những phần tử X nào trong W thỏa mãn [1,2]. Sau đó, tác giả xây dựng thực nghiệm điều kiện “mọi tập con của X thuộc Lk” thì trên bộ dữ liệu mẫu để đánh giá so sánh với phần tử X sẽ được cho thêm vào Ck+1. thuật toán Apriori [3]. 2.3. Tính độ hỗ trợ của tập mục ứng viên 2. PHƯƠNG PHÁP NGHIÊN CỨU Thủ tục này sử dụng cấu trúc SC = 2.1. Ý tưởng thuật toán {(X, Sup) | Sup = Sup(X)} để lưu lại độ hỗ trợ của các tập mục dữ liệu ứng viên đã tính. Thuật toán khai phá cơ sở dữ liệu gia tăng Sau đó, khi cần tính độ hỗ trợ của X  I, theo chiều dọc còn được gọi là Thuật toán trước hết ta tìm xem (X, *) đã có trong SC Gia tăng 1 do tác giả Nguyễn Hữu Trọng đề hay không. Nếu đã có (X, Sup) trong SC thì xuất [2]. Cơ sở dữ liệu theo chiều dọc là biểu ta có ngay Sup(X) = Sup mà không cần phải diễn của cơ sở dữ liệu giao tác trong đó các tính lại. giao tác được biểu diễn theo từng mục dữ liệu. Theo thời gian, các giao tác sẽ mới sẽ 2.4. Khai phá tập thường xuyên được thêm vào cơ sở dữ liệu giao tác (các Thủ tục Find_All_Frequent là thủ tục mục dữ liệu là vẫn giữ nguyên, không tăng chính của thuật toán Gia tăng 1 cho phép tìm thêm). Khi đó thuật toán sẽ tìm được tất cả tất cả các tập thường xuyên theo một ngưỡng các tập mục dữ liệu thường xuyên trên cơ sở Si bất kỳ của cơ sở dữ liệu giao tác đầu T. dữ liệu sau khi gia tăng (là cơ sở dữ liệu cũ Khi lần đầu tìm các tập thường xuyên theo cộng với cơ sở dữ liệu mới thêm vào). ngưỡng S0, thuật toán tính độ hỗ trợ của tất 2.2. Tìm tập mục ứng viên cả các tập mục dữ liệu và lưu lại vào SC. Ứng dụng tính chất cơ bản của tập thường Tập mục dữ liệu thường xuyên có đỗ hỗ xuyên: mọi tập mục dữ liệu chứa một tập con trợ S0 là FSo : không thường xuyên là một tập không FSo = {X | (X, Sup) SC và Sup S0 } 114 Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 Sau đó nếu cần tìm các tập thường xuyên tăng 1 chỉ tính toán trên dữ liệu tăng thêm, theo ngưỡng Si, có hai khả năng xảy ra: đồng thời kế thừa được tập SC từ lần khai - Nếu Si  S0 thì chỉ cần lọc trong SC phá trước. những (X, Sup) thỏa Sup  Si: Như vậy thuật toán Gia tăng 1 hiệu quả FSi  FS0  FSi   X |  X ,Sup   SC,Sup  Si  cho việc khai phá tập thường xuyên trên cơ sở dữ liệu gia tăng. - Nếu Si  S0: FS0  FSi 3.1. Đánh giá thuật toán với các ngưỡng hỗ trợ khác nhau  FSi   X |  X ,Sup   SC,Sup  Si  Chạy thử nghiệm thuật toán Gia tăng 1 và   X  I |  X ,Sup   SC,Supp  X   Si  Apriori trên cơ sở dữ liệu được sinh ngẫu Do đó, ta chỉ tính độ hỗ trợ của các tập nhiên vơi 1000 giao tác, 10 mục dữ liệu. ứng viên không có trong SC. Ngưỡng độ hỗ trợ tối thiểu qua những lần chạy thử nghiêm lần lượt là 3, 7, 9, 15. Kết 3. KẾT QUẢ NGHIÊN CỨU quả thu được như trong hình 2. Ta rút ra được 3.1. Đánh giá thuật toán khi chạy trên nhận xét như sau: khi ngưỡng hỗ trợ tối thiểu CSDL gia tăng ban đầu nhỏ hơn ngưỡng hỗ trợ tối thiểu của những lần khai phá sau thì ở những lần khai Chúng tôi thử nghiệm hai thuật toán phá sau, thời gian chạy của thuật toán Gia Apriori và Gia tăng 1 trên 4 cơ sở dữ liệu tăng 1 là không đáng kể (xấp xỉ 0 giây). Điều được sinh ngẫu nhiên như trong bảng 1 (m: này là hoàn toàn phù hợp với lý thuyết: trên số giao tác ban đầu, n: số mục dữ liệu, m’: số cùng cơ sở dữ liệu, khi ...