Xem mẫ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
nguon tai.lieu . vn
