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

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

Thêm vào BST

Báo xấu

11
lượt xem 2
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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 )   twuB j ( X ) . xác định cửa sổ hiện thời Wk . B j Wk 2. Tạo cây: - X được gọi là tập mục lợi ích TWU cao - Tạo nút gốc R của cây. Xây dựng bảng trong cửa sổ Wk nếu twuWk ( X )  minutilWk . đầu mục chứa tất cả các mục dữ liệu theo trật tự từ điển, giá trị twu gán bằng 0. Ví dụ: uW1 ( BD)  66, - Duyệt các khối Bj của cửa sổ hiện thời twuW1 ( BD)  twuB1 ( BD)  twuB2 ( BD)  twuB3 ( BD) Wk , với mỗi giao tác T  B j , tính lợi ích =71  0  0  71 tu (T ) . Giả sử các mục dữ liệu của T là Với minutilW1  58,8 thì BD là tập mục lợi [x | L] , ở đó x là mục dữ liệu đầu và L là ích cao và cũng là tập mục lợi ích TWU cao. phần còn lại, gọi hàm insert _ tree([x | L], R) . Hàm insert_tree([x | L], R): xét giao tác T 3. KHAI PHÁ TẬP MỤC LỢI ÍCH CAO thuộc khối giao tác thứ i của cửa sổ hiện thời. TRÊN DÒNG DỮ LIỆU Nếu R có nút con N nhãn x thì điều chỉnh giá trị thứ i trong dãy twu của nút N: Khai phá trên một cửa sổ giống như khai N.twu i : N.twu i  tu T  , trường twu của phá trên một CSDL. Dựa trên cách khai phá trong [1] và phương pháp cửa sổ trượt [2], mục mục x trong bảng đầu mục tăng thêm tu(T) . này đề xuất cách khai phá trên dòng dữ liệu, Ngược lại, tạo nút N mới là nút con của nút R gọi là thuật toán COUIS-Mine (Co-Occurrence và gán nhãn là x, giá trị thứ i trong dãy twu Utility Itemsets over Data Stream Mine). của nút N gán bằng tu(T): N.twu i : tu T  , 73
Tuyển tập Hội nghị Khoa học thường niên năm 2020. ISBN: 978-604-82-3869-8 trường twu của mục x trong bảng đầu mục 3.3. Khai phá cây HUI-tree tăng thêm tu(T) và bổ sung đường liên kết từ Khai phá cây HUI-tree của một cửa sổ bảng đầu mục đến nút mới N. Nếu L khác thực hiện như khai phá trên CSDL [1]. Với rỗng thì gọi đệ quy hàm insert _ tree(L, N) . minutilW2  57,3 , khai phá cây HUI-tree 3.2. Cập nhật cây HUI-tree hình 3.2 nhận được kết quả ở bảng 3.1. Khi khối giao tác mới B4 xuất hiện, ta cần Bảng 3.1. Kết quả khai phá xóa thông tin của khối B1 và đưa thông tin của khối B4 vào cây. Xóa thông tin của khối Tập ứng Lợi ích Tập mục TT Lợi ích viên TWU lợi ích cao B1 như sau: với mỗi nút của cây, thay đổi dãy [twu1 , twu 2 , twu 3 ] bằng cách chuyển dãy 1 E 151 25 không twu 2 , twu 3 dịch lên đầu thành [twu 2 , twu 3 , 0] . 2 BDE 111 111 có Nếu dãy này chuyển thành [0, 0, 0] thì nút 3 BE 111 105 có chứa nó bị tỉa khỏi cây. 4 DE 111 22 không (Hình 1.1) và (hình 2.2) minh họa cây 5 D 111 30 không HUI-tree với kích thước cửa sổ s = 3. 6 BD 111 106 có 7 B 111 110 có 4. KẾT LUẬN Bài báo đề xuất khai phá tập mục lợi ích cao trên dòng dữ liệu thực hiện theo thuật toán trong [1], với thay đổi mỗi nút của cây chứa dãy [twu1, twu2, …, twus] để giải quyết việc cập nhật các khối giao tác mới. Chiều cao của cây HUI-tree giới hạn bởi chiều dài của giao tác dài nhất (thường là nhỏ so với số Hình 1.1. Cây HUI-Tree của cửa sổ W1 mục dữ liệu), các kỹ thuật và máy tính hiện nay đủ đáp ứng về bộ nhớ để lưu cây tiền tố [4]. Thuật toán được thực nghiệm trên một số tập dữ liệu với kết quả thực hiện hiệu quả. 5. TÀI LIỆU THAM KHẢO [1] Nguyễn Huy Đức, 2019, Khai phá tập mục lợi ích cao với cây COFI-tree, Kỷ yếu Hội nghị Khoa học thường niên ĐH Thủy lợi, 2019. [2] J.H. Chang, W.S. Lee, Online data stream mining of recent frequent itemsets by sliding window method. Journal of Information Sciences , 31(2),76-90, 2005. Hình 2.2. Cây HUI-Tree của cửa sổ W2 [3] A foundational Approach to Mining Itemset Nhận xét: Đường đi từ một nút N bất kỳ lên Utilities from Databases. Proceedings of the gốc của cây xác định một mẫu có lợi ích TWU 4th SIAM International Conference on Data Mining, Florida, USA, 2004. bằng tổng giá trị của dãy twu tại nút N đó. Ví [4] X. Zhu, Y. Liu, An efficient frequent pattern dụ, trong cây hình 2.5, đường đi từ nút E đầu mining algorithm using a highly compressed tiên (từ bảng đầu mục trỏ ra) lên gốc xác định prefix tree, Intelligent Data Analysis, vol. 23, mẫu ECA có twu (ECA) = 12 + 0 + 0 = 12 . no. S1, pp. 153-173, 2019. 74