zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Báo xấu

9
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 ngưỡng khai thác ban giao tác tăng thêm). Kết quả thu được như đầu đủ nhỏ thì những lần khai phá tập thường trong hình 1. xuyên về sau chỉ đơn giản là lọc ra những tập Bảng 1. Thông số của 4 CSDL mục X trong SC thỏa sup(X)  Si mà không cần phải tính toán lại từ đầu. Tiêu đề CSDL 1 CSDL 2 CSDL 3 CSDL 4 m 400 1000 2000 3000 n 10 10 10 10 m 100 200 300 500 Hình 2. Kết quả chạy Gia tăng 1 và Apriori với các ngưỡng khác nhau Như vậy, thuật toán Gia tăng 1 hiệu quả cho việc khai phá tập thường xuyên trên cơ sở dữ liệu khi ngưỡng hỗ trợ tối thiểu thay đổi. Hình 1. Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 1, 2,3, 4 4. KẾT LUẬN sau khi gia tăng Trên đây, tác giả đã cài đặt hai thuật toán Sau khi chạy thử nghiệm, ta rút ra nhận xét Apriori và Giải thuật Gia tăng 1 để nhằm đánh như sau: khi chạy trên cơ sở dữ liệu gia tăng, giá thực nghiệm về thuật toán Gia tăng 1. Qua thuật toán Gia tăng 1 hiệu quả hơn hẳn thực nghiệm ta rút ra nhận xét sau: Apriori. Thực nghiệm này là phù hợp với lý  Thuật toán Gia tăng 1 hiệu quả khi khai thuyết vì khi dữ liệu gia tăng, thuật toán Gia phá luật kết hợp với dữ liệu gia tăng. 115
Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1  Thuật toán Gia tăng 1 hiệu quả khi khai 5. TÀI LIỆU THAM KHẢO phá luật kết hợp trên cùng cơ sở dữ liệu với [1] Nguyễn Hữu Trọng (2007), “Thuật toán những ngưỡng hỗ trợ khác nhau. khai phá tập mục dữ liệu thường xuyên Về phần cài đặt, thuật toán Gia tăng 1 chạy trong cơ sở dữ liệu gia tăng dựa trên phân chấp nhận được với số giao tác 10000, số mục dữ nghệ, Viên Khoa học và Công nghệ Việt liệu >20) thì chương trình chạy chậm, khó Nam, số 3, tập 45. khả thi. Điều này có thể là do kỹ thuật cài đặt [2] Nguyễn Hữu Trọng (2007), “Một số thuật chưa được tối ưu. Việc sử dụng những cấu toán khai phá luật kết hợp trên cơ sở dữ liệu trúc dữ liệu cũng như các thủ tục xử lý cũng tăng trưởng”, Luận án tiến sĩ toán học, Viện sẽ gây ảnh hưởng đến tốc độ xử lý của công nghệ thông tin. chương trình. [3] Rakesh Agrawal, Ramarkrishnan Srikant (1994) “Fast algorithms for mining association rules”. In: Proceedings of the 20thVLDB conference. 116

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.