Khai phá tập mục lợi ích cao với cây COFI-tree trên dòng dữ liệu

Bài viết Khai phá tập mục lợi ích cao với cây COFI-tree trên dòng dữ liệu trình bày các nội dung chính sau: Các thuật ngữ cho khai phá tập mục lợi ích cao trên dòng dữ liệu; Khai phá tập mục lợi ích cao trên dòng dữ liệu.
Nội dung trích xuất từ tài liệu:
Khai phá tập mục lợi ích cao với cây COFI-tree trên dòng dữ liệu Tuyển tập Hội nghị Khoa học thường niên năm 2020. ISBN: 978-604-82-3869-8 KHAI PHÁ TẬP MỤC LỢI ÍCH CAO VỚI CÂY COFI-TREE TRÊN DÒNG DỮ LIỆU Nguyễn Huy Đức1, Đỗ Oanh Cường1 1 Trường Đại học Thủy lợi, email: ducnghuy@tlu.edu.vn 1. GIỚI THIỆU Ví dụ, dòng giao tác bảng 2.1 có các khối giao tác B1 - B5, mỗi cửa sổ chứa 3 khối giao Khai phá tập mục lợi ích cao là một hướng tác, W1 chứa 3 khối B1-B3 , W2 chứa 3 khối mở rộng và tổng quát của khai phá tập mục B2 - B4. Nếu hiện tại khai phá trên cửa sổ W1 phổ biến, được đề xuất vào năm 2004 [3]. thì thời điểm sau khai phá trên cửa sổ W2. Trong [1], tác giả đề xuất thuật toán khai phá hiệu quả tập mục lợi ích cao trên CSDL giao Bảng 2.1. Dòng dữ liệu giao tác tác, dựa trên cấu trúc cây COFI-tree. Trong thực tế, có nhiều ứng dụng sinh ra dòng dữ liệu (data streams) theo thời gian thực như dòng giao tác trong dây chuyền bán lẻ, dòng kích web trong các ứng dụng web,… Các dòng giao tác này xuất hiện liên tục, tuần tự theo thời gian và không giới hạn về số lượng. Do vậy, tại thời điểm khai phá, cần lấy các giao tác trong một khoảng thời gian nào đó. Khi chuyển sang thời điểm sau, một số giao tác cũ cần loại bỏ và cần xét thêm các giao tác mới Bảng 2.2. Bảng lợi ích xuất hiện. Điều quan trọng khi khai phá trên dòng dữ liệu là phải kế thừa được những kết quả cũ trong khoảng thời gian trước để tạo ra kết quả mới trong khoảng thời gian hiện tại. Dựa trên phương pháp cửa sổ trượt (Sliding window-based methods) trong khai phá tập mục phổ biến [2] và cách khai phá Ký hiệu các khối giao tác là Bj, các cửa sổ trong [1], bài báo đề xuất thuật toán khai phá là Wk, có một số thuật ngữ như sau: tập mục lợi ích cao trên dòng dữ liệu. - Lợi ích của tập mục X trong khối Bj, ký hiệu u B j ( X ) , là tổng lợi ích của tập mục X tại 2. CÁC THUẬT NGỮ CHO KHAI PHÁ TẬP MỤC LỢI ÍCH CAO TRÊN DÒNG các giao tác thuộc khối Bj, tức là: DỮ LIỆU uB j ( X )    u (i p , Tq ) . Tq B j i p X Tq Phân hoạch dòng giao tác thành từng khối - Lợi ích của tập mục X trong cửa sổ Wk, và định nghĩa cửa sổ gồm một số khối. Tại ký hiệu uWk ( X ) , là tổng lợi ích của tập mục X một thời điểm, ta khai phá trên một cửa sổ. Ở thời điểm sau, có khối giao tác đã cũ, cần loại tại các khối thuộc W k, tức là : ra khỏi cửa sổ, có khối giao tác mới xuất hiện uWk ( X )  u Bj ( X ). sẽ được thêm vào cửa sổ. B j Wk 72 Tuyển tập Hội nghị Khoa học thường niên năm 2020. ISBN: 978-604-82-3869-8 Ví dụ, dòng giao tác bảng 2.1 (với bảng lợi Thuật toán gồm hai bước : ích 2.2), uB1 ( BD)  u ( BD, T2 )  66 , Bước 1: Xây dựng cây HUI-Tree của cửa uW1 ( BD)  u B1 ( BD )  u B2 ( BD )  u B3 ( BD )  66 sổ hiện thời Wk, sau đó khai phá cây này tìm các tập mục có lợi ích TWU cao trong Wk . - Ngưỡng lợi ích tối thiểu Wk là phần trăm Bước 2: Duyệt lại cửa sổ Wk để tính lợi ích của tổng lợi ích của các giao tác trong cửa sổ thực sự của các tập mục tìm được ở bước 1, Wk. Giá trị lợi ích tối thiểu xác định là từ đó xác định được các tập mục lợi ích cao minutilWk  Wk .  tu (Tq ) . trong Wk . Tq Wk Để khai phá tiếp trên cửa sổ Wk+1 , thuật Ví dụ: toán loại bỏ thông tin của khối giao tác cũ và W1  30%, minutilW1 =30%.196  58,8. bổ sung thông tin của khối giao tác mới xuất hiện vào cây HUI-Tree . - Tập mục X được gọi là tập mục lợi ích cao trong cửa sổ Wk nếu uWk ( X )  minutilWk . 3.1. Xây dựng cây HUI-Tree - Khai phá tập mục lợi ích cao trong Wk là Giả sử kích thước cửa sổ (số khối giao tác tìm tập HUWk chứa tất cả các tập mục lợi ích trong cửa sổ) là s. Xây dựng cây HUI-Tree thực hiện theo thuật toán trong [1] với cải  cao, HUWk  X / X  I , uWk ( X )  minutilWk .  tiến: trường twu của mỗi nút thay là dãy - Lợi ích TWU của tập mục X trong khối [twu1 , twu 2 ,..., twu s ] - dãy giá trị TWU của s Bj, ký hiệu twu B j ( X ) , là tổng lợi ích TWU khối giao tác trong cửa sổ. của tập mục X tại các giao tác thuộc khối Bj, Thuật toán xây dựng cây HUI-tree tức là: twuB j ( X )   u (Tq ) . Input: Dòng DL giao tác, bảng lợi ích, kích X Tq B j thước khối b, kích thước cửa sổ s. - Lợi ích TWU của tập mục X trong cửa sổ Output: Cây HUI-tree. Wk, ký hiệu twuWk ( X ) , là tổng lợi ích TWU Method: Cây HUI-tree xây dựng như sau: của tập mục X tại các khối thuộc Wk, tức là : 1. Chia dòng giao tác thành các khối Bj, twuWk ( X )   twu ...