Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019
DOI: 10.15625/vap.2019.00021
FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
Huỳnh Triệu Vỹ1, Lê Quốc Hải2, Trương Ngọc Châu3
1
Trường ĐH Phạm Văn Đồng
2
Trường CĐSP Quảng Trị
3
Trường ĐH Bách khoa Đà Nẵng
htrvy@yahoo.com, hailq79@gmail.com, truongngocchau@yahoo.com
TÓM TẮT: Khai phá tập mục hữu ích cao hiếm nhằm mục đích tìm kiếm trong cơ sở dữ liệu giao tác (CSDL) tất cả các tập mục có
độ hỗ trợ thấp hơn hoặc bằng ngưỡng hỗ trợ tối đa và giá trị hữu ích lớn hơn hoặc bằng ngưỡng hữu ích tối thiểu được chỉ ra bởi
người dùng. Các thuật toán khai phá tập mục hữu ích cao hiếm hai pha sẽ tốn nhiều thời gian thực thi ở pha sinh tập ứng viên, đặc
biệt khi ngưỡng hỗ trợ tối đa tăng lên sẽ sinh ra nhiều tập ứng viên. Để khắc phục hạn chế này, trong bài báo này chúng tôi đề xuất
thuật toán khai phá tập mục hữu ích cao hiếm mà không cần sinh tập ứng viên. Để lưu trữ hiệu quả thông tin về giá trị hữu ích và
độ phổ biến của các tập mục chúng tôi sử dụng cấu trúc utility-list, đồng thời dựa trên cấu trúc này để tỉa không gian tìm kiếm hiệu
quả. Kết quả thực nghiệm cho thấy thuật toán của chúng tôi nhanh hơn các thuật toán hiện tại.
Từ khóa: Tập mục hữu ích cao, Tập mục hữu ích cao hiếm, Ngưỡng hỗ trợ cực đại.
I. GIỚI THIỆU
Các thuật toán khai phá tập phổ biến không đề cập đến vai trò của các mục và xem chúng có vai trò như nhau
trong cơ sở dữ liệu (CSDL) [1, 2]. Tuy nhiên, trong thực tế nếu các mục được xem xét về tầm quan trọng của chúng sẽ
có ý nghĩa hơn. Ví dụ như cơ sở dữ liệu bán hàng của một siêu thị, mỗi giao tác không chỉ lưu trữ các mặt hàng của
một đơn hàng mà còn có số lượng của mỗi mặt hàng và kèm theo đó là thông tin về giá hoặc lợi nhuận mang lại khi
bán các mặt hàng này. Để giải quyết hạn chế này, Hong Yao và các cộng sự [3] đã đề xuất một mô hình để khai phá tập
mục dựa trên độ hữu ích của chúng, gọi là Khai phá tập mục hữu ích cao (High Utility Mining). Dựa trên nền tảng này,
nhiều thuật toán khai phá tập mục hữu ích cao hiệu quả hơn cũng được đề xuất [4-11].
Trong khai phá tập mục hữu ích cao [2-11] chỉ cho biết thông tin duy nhất về giá trị hữu ích của các tập mục.
Tuy nhiên, trong thực tế, ngoài thông tin về giá trị hữu ích của tập mục, nếu biết thêm về độ phổ biến của tập mục hữu
ích cao sẽ mang lại nhiều ý nghĩa hơn nữa cho người dùng. Ví dụ, trong một chuỗi bán lẻ, có những mặt hàng ít được
bán ra nhưng lợi nhuận của chúng mang lại rất lớn khi được bán (ví dụ như bia, rượu cao cấp), vì vậy các nhà kinh
doanh sẽ có chiến lược khuyến mãi để kích thích người mua nhằm thu lại lợi ích lớn cho doanh nghiệp. Những chiến
lược đưa ra cần phải dựa trên tri thức khai thác được từ dữ liệu bán hàng. Để giải quyết yêu cầu này, J. Pillai và cộng
sự [12] đã đề xuất một hướng tiếp cận mới gọi là Khai phá tập mục hữu ích cao hiếm, tức khai phá tập mục hữu ích cao
có độ phổ biến thấp, các tác giả cũng đề xuất thuật toán có tên gọi là HURI. Để tìm tập mục hữu ích cao hiếm, HURI
thực hiện qua 2 pha. Nhược điểm của thuật toán HURI là sinh ra tập ứng viên lớn ở pha thứ nhất khi ngưỡng hỗ trợ cực
đại tăng lên. Để giảm tập ứng viên, V. Goyal và cộng sự [13] đề xuất thuật toán có tên gọi là UP-Rare Growth dựa trên
cấu trúc UP-Tree [9]. Các thuật toán tìm tập mục hữu ích cao hiếm phải trải qua bước sinh tập ứng viên tiêu tốn nhiều
thời gian thực thi và bộ nhớ lưu trữ tập ứng viên.
Trong bài báo này chúng tôi đề xuất thuật toán khai phá tập mục hữu ích cao hiếm mà không trải qua bước sinh
tập ứng viên, thuật toán này có tên gọi là FHURIM (Fast High Utility Rare Itemset Mining). Để tìm tập mục hữu ích
cao hiếm mà không cần sinh tập ứng viên chúng tôi dựa trên cấu trúc dữ liệu utility-list [7]. Ưu điểm của cấu trúc
utility-list chỉ cần quét CSDL 2 lần để xây dựng cấu trúc utility-list của các mục đơn có trọng số hữu ích lớn hơn
ngưỡng hữu ích tối thiểu, để xây dựng cấu trúc utility-list của các tập mục có k-mục chỉ dựa vào utility-list của tập mục
(k-1)-mục mà không cần quét lại CSDL. Đồng thời dựa trên utility-list có thể tính được độ phổ biến của tập mục k-mục
và chứa thông tin hueristic để tìm tập hữu ích cao hiếm có độ dài (k+1) mục.
Phần tiếp theo của bài báo được tổ chức như sau: Phần 2 trình bày về các vấn đề liên quan đến bài báo, phần 3
là chi tiết về thuật toán được đề xuất, kết quả thực nghiệm và cuối cùng là kết luận của bài báo.
II. CÁC VẤN ĐỀ LIÊN QUAN
A. Khai phá tập mục hữu ích cao
Mô hình khai phá tập mục hữu ích cao được đề xuất đầu tiên bởi Hong Yao và cộng sự [3]. Dựa trên mô hình
này, Liu. Y và các cộng sự [8] đề xuất thuật hai pha (TwoPhase), chiến lược tỉa không gian tìm kiếm trong [8] dựa vào
tính chất bao đóng giảm dần (downward closure) của đơn vị đo lường TWU (Transaction-Weighted-Utilization) nên
thuật toán hai pha rút gọn nhanh không gian tìm kiếm ở pha thứ nhất. Để thu gọn bớt tập ứng viên ở pha thứ nhất, V. S.
Tseng và cộng sự [9] đề xuất thuật toán có tên là UP-Growth (Utility Pattern Growth) và UP-Growth+, các thuật toán
này sử dụng cấu trúc UP-tree để duy trì thông tin về hữu ích của các tập mục sao cho các tập ứng viên có thể được tạo
ra hiệu quả chỉ với hai lần quét CSDL.
- 160 FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
Đơn vị đo lường TWU có giá trị lớn hơn rất nhiều giá trị hữu ích của tập mục nên tập ứng viên sinh ở pha thứ
nhất vẫn còn lớn nên ảnh hưởng đến hiệu suất của thuật toán. Để khắc phục hạn chế này, M. Liu và cộng sự [7] đề xuất
thuật toán HUI-Miner (High Utility Itemset Miner) để khai phá tập mục hữu ích cao mà không cần sinh tập ứng viên
dựa trên cấu trúc lưu trữ mới có tên gọi là utility-list. Các thuật toán khai phá tập mục hữu ích cao không trải qua bước
sinh tập ứng viên hiệu quả hơn cũng được đề xuất [4, 6, 11].
Các định nghĩa và tính chất liên quan đến khai phá tập mục hữu ích cao có thể tìm thấy chi tiết trong [3-11],
chúng tôi trình bày tóm tắt lại các nội dung liên quan đó như sau:
Định nghĩa 1 (CSDL Giao tác): Cho { } là một tập hữu hạn gồm các mục. Mỗi mục có
một giá trị hữu ích ngoại, ký hiệu là . Một tập mục { } là một tập mục gồm k mục, với
và k là độ dài của X. Một CSDL giao tác { } chứa n giao tác, mỗi giao tác có
một định danh gọi là Tid. Mỗi mục trong giao tác kết hợp với một trọng số gọi là hữu ích nội (số lượng), ký hiệu
là .
Bảng 1. CSDL Giao tác D
Tid Transaction Tid Transaction
T1 A(4), C(1), E(6), F(2) T6 B(1), F(2), H(1)
T2 D(1), E(4), F(5) T7 D(1), E(1), F(4), G(1), H(1)
T3 B(3), D(1), E(5), F(1) T8 B(1), D(1), E(1)
T4 D(1), E(2), F(6) T9 B (5), D(4), G(10)
T5 A(3), C(1), E(1)
Bảng 2. Bảng giá trị hữu ích ngoại của CSDL giao tác D
Item A B C D E F G H
Utility 3 4 5 2 1 1 1 2
CSDL cho trong Bảng 1 và 2 sẽ được sử dụng cho tất cả ví dụ trong bài báo này.
Ví dụ 1: q(A,T1)=4 và p(A)=3; q(C,T1)=1 và p(C)=5
Định nghĩa 2 (Hữu ích của một mục trong giao tác): Hữu ích của một mục trong một giao tác ký hiệu là
và được định nghĩa:
.
Ví dụ 2: u(A,T1)=q(A,T1) * p(A)=3 * 4=12
u(C,T1)=q(C,T1) * p(C)=1 * 5=5
Định nghĩa 3 (Hữu ích của tập mục trong giao tác): Hữu ích của một tập mục X trong một giao tác Tc ký hiệu
là và được định nghĩa:
∑ .
Ví dụ 3: u({A,C},T1)=u(A,T1)+u(C,T1)=17;
u({A,C},T5)=u(A,T5)+u(C,T5)=14
Định nghĩa 4 (Hữu ích của một tập mục trong CSDL): Hữu ích của một tập mục X trong một CSDL giao tác
D, ký hiệu là và được định nghĩa:
∑ .
Ví dụ 4: u({A,C})=u({A,C},T1)+u({A,C},T5)=17+14=31
Định nghĩa 5 (Hữu ích của giao tác): Giá trị hữu ích của một giao tác Tc ký hiệu là ) và được định
nghĩa:
∑ .
Ví dụ 5: TU(T1)=3*4+5*1+1*6+1*2=25
Định nghĩa 6 (Trọng số hữu ích giao tác): Trọng số hữu ích giao tác của một tập mục X, ký hiệu là
và được định nghĩa:
∑ .
- Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 161
Ví dụ 6: TWU({A})= TU(T1) + TU(T5) =25+15=40
TWU({A,C})= TU(T1) + TU(T5) =25+15=40
TWU({A,F})= TU(T1) =25
Tính chất 1: Trọng số hữu ích của một tập mục X luôn luôn lớn hơn hoặc bằng giá trị hữu ích của chính nó, tức
là: [8].
Tính chất 2: Cho thì trọng số hữu ích của tập mục X luôn luôn lớn hơn hoặc bằng trọng số
hữu ích của tập mục Y [8].
Như vậy, trọng số hữu ích giao tác của tập mục thỏa mãn tính chất bao đóng giảm dần.
Tính chất 3 (Tỉa không gian tìm kiếm): Cho X là một tập mục, nếu thì tập mục X và tất cả tập
cha của X không phải là tập mục hữu ích cao [8].
Định nghĩa 7 (Tập mục hữu ích cao): Một tập mục X được gọi là tập mục hữu ích cao trong CSDL D, nếu giá
trị hữu ích của X không nhỏ hơn ngưỡng hữu ích tối thiểu ( được đưa ra bởi người dùng). Gọi HUIs là tập các tập
mục hữu ích cao thì:
{ }.
Ví dụ 7: Với , tập mục hữu ích cao khai thác được từ CSDL được cho trong Bảng 1 và Bảng 2 gồm các
tập mục ở Bảng 3.
Bảng 3. Tập các tập mục hữu ích cao
Itemset Utility Itemset Utility Itemset Utility
AC 31 B 40 BDG 38
AE 28 BD 48 DEF 36
ACE 38 BG 30 EF 36
ACEF 25 BDE 26
B. Khai phá tập mục hữu ích cao hiếm
Các thuật toán khai phá tập mục hữu ích cao [3-11] chỉ cho biết duy nhất một thông tin là giá trị hữu ích của tập
mục. Khai phá tập mục hữu ích cao hiếm là một mở rộng của khai phá tập mục hữu ích cao với mục đích tìm kiếm
trong CSDL tất cả các tập mục có giá trị hữu ích không nhỏ hơn ngưỡng hữu ích tối thiểu nhưng có tần suất xuất hiện
thấp hơn một ngưỡng hỗ trợ tối đa [12-14]. Khai phá tập mục hữu ích cao hiếm có rất nhiều ý nghĩa trong thực tiễn, ví
dụ như trong các chuỗi bán lẻ, tập mục hữu ích cao hiếm sẽ cung cấp những tri thức hữu ích giúp cho nhà kinh doanh
có chiến lược khuyến mãi để kích thích người mua vì bán được các mặt hàng này sẽ thu lại một lợi nhuận rất lớn.
Để khai phá tập mục hữu ích cao hiếm, J. Pillai và cộng sự [12] đề xuất thuật toán hai phá có tên gọi là HURI: (1)
Pha 1: Duyệt qua CSDL để tìm tất cả các tập mục có độ phổ biến nhỏ hơn hoặc bằng độ hỗ trợ cực đại do người dùng
đưa ra; (2) Pha 2: Từ tập ứng viên ở pha 1, rút ra tất cả các tập mục có giá trị hữu ích không nhỏ hơn ngưỡng hữu ích
tối thiểu do người dùng đưa ra. Nhược điểm của thuật toán HURI là sinh ra tập ứng viên lớn ở pha thứ nhất khi ngưỡng
hỗ trợ cực đại tăng lên. Để giảm tập ứng viên, V. Goyal và cộng sự [13] đề xuất thuật toán có tên gọi là UP-Rare
Growth dựa trên cấu trúc UP-Tree [9]. Dựa trên cấu trúc UP-Tree thuật toán UP-Rare Growth có thể tính toán độ phổ
biến và giá trị hữu ích của tập mục cùng nhau và áp dụng tỉa không gian tìm kiếm tương tự như thuật toán UP-
Growth[9].
Các định nghĩa liên quan đến khai phá tập mục hữu ích cao hiếm có thể tìm thấy chi tiết trong [12, 13] và được
trình bày tóm tắt lại như sau:
Định nghĩa 8 (Độ hỗ trợ): Độ hỗ trợ của tập mục X là tỷ lệ xuất hiện của tập mục X trong CSDL giao tác D, ký
hiệu và được định nghĩa như sau:
,
Trong đó, g(X) là tập các giao tác trong CSDL D chứa X.
Định nghĩa 9 (Tập mục hiếm): Một tập mục X được gọi là tập mục hiếm nếu độ hỗ trợ của tập mục X nhỏ hơn
hoặc bằng ngưỡng hỗ trợ cực đại .
Định nghĩa 10 (Tập mục hữu ích cao hiếm): Một tập mục X được gọi là tập mục hữu ích cao hiếm trong
CSDL D nếu tập mục X là một tập mục hiếm và hữu ích cao. Gọi là tập các tập mục hữu ích cao hiếm thì:
{ }.
- 162 FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
Ví dụ 8: Cho và thì tập các tập mục hữu ích cao hiếm thu được từ CSDL D gồm các tập mục
trong Bảng 4
Bảng 4. Tập các tập mục hữu ích cao hiếm
Itemset Utility Support(%)
B 40 44,4
BD 48 33,3
EF 36 55,5
DEF 36 33,3
C. Cấu trúc utility-list và EUCS
Để khai phá tập mục hữu ích cao mà không cần sinh tập ứng viên, M. Liu và cộng sự [7] đề xuất một cấu trúc
dữ liệu mới có tên gọi là utility-list, từ cấu trúc này có thể trích xuất các tập mục hữu ích cao mà không cần quét lại
CSDL và đồng thời dựa trên utility-list tỉa không gian tìm kiếm hiệu quả. Tuy nhiên, một nhược điểm của utility-list là
khi xây dựng utility-list của các tập mở rộng tốn thời gian. Để khắc phục hạn chế này, P. Fournier-Viger và cộng sự [6]
đưa ra một cấu trúc mới có tên gọi là EUCS (Estimated Utility Co-Occurrence Structure) và dựa trên EUCS tỉa các
utility-list không cần thiết phải xây dựng. Các định nghĩa liên quan đến cấu trúc utility-list và EUCS được trình bày
vắn tắt lại như sau:
Định nghĩa 11 (Cấu trúc utility-list): Cho là một thứ tự toàn phần trên I*. Utility-list của một tập mục
trong CSDL D là một tập gồm các bộ ba tuple(tid, iutil, rutil) tương ứng với mỗi giao tác Tc chứa tập mục Px
(Px là tập mở rộng của tập P với mục x. Tập P được khởi tạo ban đầu là tập rỗng). Ở đây:
tid: Tid của giao tác Tc chứa tập mục Px.
iutil: Giá trị hữu ích của tập mục Px trong giao tác Tc.
rutil: Giá trị hữu ích còn lại của Px trong giao tác Tc.
Định nghĩa 12 (Tập mục còn lại trong giao tác): Cho tập mục Px và giao tác Tc, sao cho , tập mục
còn lại trong giao tác Tc là tập mục gồm tất cả các mục theo sau Px theo thứ tự đã sắp xếp tăng dần theo trọng số hữu
ích của các mục, ký hiệu là và được định nghĩa:
{ }.
Ví dụ 9: Cho tập mục Px = {AC}, tập còn lại của tập mục Px trong giao tác T1 là {FE}.
Định nghĩa 13 (giá trị hữu ích còn lại): Giá trị hữu ích còn lại của tập mục Px trong giao tác Tc, ký hiệu là
và được định nghĩa:
∑ .
Tính chất 4 (Tỉa không gian tìm kiếm) [7]: Cho Px.UL là utility-list của tập mục Px, nếu tổng của tất cả iutils
và rutils trong Px.UL nhỏ hơn ngưỡng hữu ích tối thiểu thì tập mục Px và tất cả tập mở rộng của Px đều là tập mục hữu
ích thấp.
Tính chất 4 được sử dụng để tỉa không gian tìm kiếm trong khai phá tập mục hữu ích cao dựa trên utility-list.
Ưu điểm của việc sử dụng cấu trúc utility-list để khai phá tập mục hữu ích cao hiếm là chỉ duy nhất với hai lần
quét CSDL và không cần sinh tập ứng viên, bởi vì từ utility-list của các mục đơn có thể xây dựng các utility-list của
các tập mục mở rộng. Đồng thời dựa trên utility-list sẽ tính được hữu ích, độ hỗ trợ của các tập mục và chứa thông tin
huristic để tỉa không gian tìm kiếm hiệu quả. Các bước xây dựng utility-list được đề xuất trong [7] được mô tả chi tiết
lại như sau:
(1) Khởi tạo utility-list: utility-list được khởi tạo ban đầu gồm utility-list của các mục có trọng số hữu ích lớn
hơn hoặc bằng ngưỡng hữu ích tối thiểu. Ở bước xây dựng utility-list này các mục có trọng số hữu ích thấp sẽ được tỉa
(theo Tính chất 3). Để xây dựng utlity-list của các mục đơn chỉ cần thực hiện qua 2 lần quét CSDL:
Quét CSDL lần thứ nhất để tính TWU của các mục . Khi TWU của các mục đơn được tính, các mục có
TWU nhỏ hơn ngưỡng hữu ích tối thiểu sẽ được loại bỏ và thu được tập { } và mục
trong được sắp xếp lại theo thứ tự tăng dần của TWU (nhằm mục đích áp dụng chiến lược tỉa không gian
tìm kiếm dựa trên utility-list).
Quét CSDL lần thứ hai để xây dựng các utility-list của các mục
Ví dụ 10: Với , thì { } và utility-list của các mục trong được biểu diễn như Hình 1.
(2) Utility-list của tập mục có độ dài
Để xây dựng utility-list của các tập mục gồm hai mục {xy} không cần phải quét CSDL mà chỉ cần thực hiện
phép giao giữa utility-list của x và utility-list của y.
- Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 163
Ví dụ 11: utility-list của các tập mục gồm 2 phần tử được mở rộng từ mục A được mô tả trong Hình 2.
{A} {C} {G} {B} {F} {E} {D}
1 12 13 1 5 8 7 1 7 3 12 8 1 2 6 1 6 0 2 2 0
5 9 6 5 5 1 9 10 28 6 4 2 2 5 4 2 4 2 3 2 0
8 4 3 3 1 5 3 5 2 4 2 0
9 20 8 4 6 2 4 2 2 7 2 0
6 2 0 5 1 0 8 2 0
tid iutil rutil 7 4 3 7 1 2 9 8 0
8 1 2
Hình 1. Utility-list của các mục đơn
{AC} {AF} {AE}
1 17 8 1 14 6 1 18 0
5 14 1 5 10 0
Hình 2. Utility-list của các tập mục gồm 2 phần tử được mở rộng từ mục A
Utility-list của tập mục có độ dài
Để xây dựng utility-list của các tập mục { }, (thứ tự của các mục trong tập mục đã được
sắp xếp theo thứ tự tăng dần của TWU) cũng không cần quét lại CSDL, chúng ta thực hiện thực hiện phép giao giữa
utility-list c ủa tập mục { } với utility-list của tập mục { }.
Ví dụ 12: Xây dựng utility-list của tập { } ta thực hiện giao giữa utility-list của { } với { }, kết quả được
mô tả trong Hình 3.
{ACE}
1 23 0
5 15 0
Hình 3. Utility-list của tập mục {ACE}
Sau đây là thuật toán được viết dưới dạng giả mã để xây dựng utility-list của các tập mục có độ dài k, thuật toán
có tên gọi là Construct[7]:
Thuật toán Construct
Vào: P: tập mục P; Px: tập mục mở rộng của P với mục x; Py: Tập mục mở rộng của P với mục y
Ra: Pxy.UL: utility-list của tập mục Pxy
1. ;
2.
3. {
4. {
5. ;
6. ;
7. }
8. ;
9. Thêm bộ vào ;
10. }
11. Return ;
Định nghĩa 14 (cấu trúc EUCS-Estimated Utility Co-Occurrence Structure): Cho { } là tập
hữu hạn các mục có trọng số hữu ích cao. Cấu trúc EUCS được định nghĩa là một tập của các bộ ba
. Trong đó: và { }
Ví dụ 13: Với CSDL cho trong Bảng 1 và Bảng 2, cấu trúc của EUCS được biểu diễn dưới dạng ma trận như
Hình 4.
Tính chất 5 (Tỉa không gian tìm kiếm): Cho tập mục P và hai mục , nếu không tồn tại một bộ
trong EUCS sao cho thì tập mở rộng của P là Pxy và tất cả tập cha của Pxy đều là tập mục hữu ích
thấp.
Tính chất 5 được sử dụng khi xây dựng utility-list của tập Pxy. Nếu Pxy thỏa mãn tính chất 5 thì không cần xây
dựng utility-list của Pxy vì Pxy không thể là tập mục hữu ích cao cũng như tất cả tập cha của Pxy.
- 164 FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
item A B C D E F G
A 0
B 0 0
C 40 0 0
D 0 74 0 0
E 40 36 40 105 0
F 25 28 25 51 76 0
G 0 38 0 48 10 10 0
Hình 4. Cấu trúc EUCS
III. THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
A. Đề xuất thuật toán
Thuật toán chúng tôi đề xuất có tên gọi là FHURIM là một thuật toán biến thể của thuật toán FHM [6] để khai
phá nhanh tập mục hữu ích cao hiếm từ CSDL giao tác chỉ trong một pha mà không cần sinh tập ứng viên.
Mô tả thuật toán: Thuật toán FHURIM thực hiện qua hai bước chính, cụ thể:
Bước 1: Khởi tạo (Thuật toán FHURIM_Initial)
Duyệt qua CSDL lần thứ nhất để tính trọng số hữu ích giao tác (TWU) của tất các các mục trong I.
Xác định tập I* gồm tất cả các mục có trọng số hữu ích lớn hơn hoặc bằng ngưỡng hữu ích tối thiểu, các
mục có trọng số hữu ích nhỏ hơn ngưỡng hữu ích tối thiểu được tỉa bỏ ở bước này (áp dụng tính chất 3).
Các mục trong I* được sắp xếp lại theo thứ tự tăng dần của trọng số hữu ích. Việc này nhằm mục đích để tỉa
không gian tìm kiếm dựa trên thông tin heuristics của utility-list (áp dụng tính chất 4).
Duyệt qua CSDL lần 2 để xây dựng các utility-list của tất cả các mục đơn trong I* và xây dựng cấu trúc
EUCS. Utility-list của các mục trong I* là các utility-list cơ sở để suy diễn ra các utility-list của các tập mở
rộng trong quá trình tìm tập mục hữu ích cao hiếm mà không cần quét lại CSDL và cấu trúc EUCS chứa
thông tin hueristics để tỉa bỏ các utility-list không cần thiết phải xây dựng (áp dụng tính chất 5).
Bước 2: Khai phá (Thuật toán FHURIM_Miner)
Duyệt qua từng utility-list của các tập mục Px (đầu tiên xét các tập mục có độ dài là 1). Với mỗi utility-list
của tập mục Px:
- Tính giá trị hữu ích của Px (hữu ích của Px được tính bằng cách tính tổng của các iutil của các bộ
tuple(tid, iutil, rutil) trong utility-list của Px, ta ký hiệu là Sum(Px.UL.iutil)) và tính độ phổ biến của tập
mục Px (độ phổ biến của Px được tính là tổng số bộ trong Px.UL của Px, ký hiệu là Count(Px.UL)).
- Kiểm tra Px có phải là tập mục hữu ích cao hiếm hay không? Bổ sung Px vào danh sách tập mục hữu ích
cao hiếm nếu .
- Nếu , xây dựng các utility-list của các tập mở rộng của Px
(tập mở rộng là tập ). Gọi đệ quy thuật toán FHURIM_Miner để xác định
tập mục hữu ích cao cho các tập mở rộng của Px
Sau đây là thuật toán FHURI được viết dưới dạng mã giả:
Thuật toán FHURIM
Vào: D: CSDL Giao tác; ngưỡng hữu ích tối thiểu; ngưỡng hỗ trợ cực đại.
Ra: HURIs: Tập gồm các tập mục hữu ích cao hiếm.
1. ;
2. ;
Thuật toán FHURIM_Initial
Vào: D: CSDL Giao tác; ngưỡng hữu ích tối thiểu;
Ra: : Tập gồm các mục có trọng số hữu ích lớn hơn hoặc bằng và được sắp xếp theo thứ tự tăng dần của
trọng số hữu ích của các mục; ULs: tập các utility_list của các mục đơn trong ; EUCS: Chứa dữ liệu theo cấu
trúc EUCS;
1. )
2. Tính ;
3. Xác định tập { };
4. Sắp xếp lại thứ tự của các mục trong { } ( ) ;
5. ){
- Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 165
6. Xây dựng tập ULs gồm các utility-list của các mục ;
7. Xây dựng cấu trúc EUCS
8. }
Thuật toán FHURIM_Miner
Vào: P.UL: Utility-list của tập mục P; ULs: tập các utility-list của các tập mục mở rộng của P; ngưỡng hữu
ích tối thiểu; ngưỡng hỗ trợ cực đại; : cấu trúc EUCS;
Ra: HURIs: Tập gồm các tập mục hữu ích cao hiếm;
1. {
2. { }
3. {
4. { };//tập các utility-list của các tập mở rộng của Px
5.
6.
7.
8. ;
9. }
10. }
B. Kết quả thực nghiệm
Mô tả CSDL: Các cơ sở dữ liệu liệu chạy thực nghiệm chúng tôi sử dụng CSDL được công bố tại [15], chi tiết
về các CSDL này được mô tả trong Bảng 5.
Bảng 5. Mô tả tập CSDL thực nghiệm
Databases #|D| #|I| #AvgLen #MaxLen
Foodmart 4.141 1.559 4,0 11
Mushroom 8.124 119 23 23
Chú thích: #|D|: Tổng số giao tác; #|I|: Tổng số mục trong CSDL; #AvgLen: Độ dài trung bình của giao tác
trong CSDL; #MaxLen: Độ dài cực đại của giao tác trong CSDL.
Mô tả hệ thống máy tính: CPU Core I5 2.4GHz, RAM 8GB, Windows 10.
Kết quả thực nghiệm: Chúng tôi so sánh thời gian thực thi giữa thuật toán FHURIM với thuật toán Up-Rare
Growth trên CSDL được mô tả trong Bảng 5. Kết quả thực nghiệm cho thấy thuật toán FHURIM có thời gian thực thi
nhanh hơn nhiều lần so với thuật toán Up-Rare Growth. Bởi vì thuật toán UP-Rare Growth dựa trên cấu trúc UP-Tree
để tính toán độ phổ biến và giá trị hữu ích của tập mục cùng nhau và áp dụng chiến lược tỉa không gian tìm kiếm tương
tự như thuật toán UP-Growth. Tuy nhiên, nhược điểm của UP-Tree là tốn nhiều thời gian và bộ nhớ để xây dựng cấu
trúc UP-Tree, đặc biệt khi ngưỡng hữu ích tối thiểu thấp và CSDL chứa mẫu dài và dày vì thuật toán chỉ tỉa các mục
đơn có TWU nhỏ hơn ngưỡng hữu ích tối thiểu và độ hỗ trợ của tập mục chỉ được tính khi toàn bộ dữ liệu được thêm
vào cây UP-Tree. Còn đối với thuật toán FHURIM sử dụng cấu trúc utility-list và EUCS để tính toán giá trị hữu ích và
độ phổ biến của các tập mục (từ utility-list của mục đơn được khởi tạo ban đầu) mà không cần quét lại CSDL, đồng
thời trên 2 cấu trúc này cũng chứa thông tin heuristic để tỉa không gian tìm kiếm hiệu quả.
Hình 5 biểu diễn thời gian thực thi giữa hai thuật toán Up-Rare Growth và FHURIM trên CSDL Foodmart và
Mushroom với các ngưỡng hỗ trợ cực đại và ngưỡng hữu ích tối thiểu khác nhau.
Foodmart Foodmart
(Min Utility=560) (Min Utility=600)
1500 1500
1200 1200
Run times(ms)
Run times(ms)
900 900
600 600
300 300
0 0
0.024 0.048 0.072 0.096 0.024 0.048 0.072 0.096
Max Support Max Support
UP-Rare Growth FHURIM UP-Rare Growth FHURIM
- 166 FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM
Mushroom Mushroom
(Min Utility=8050000) (Min Utility=8080000)
93500 93500
78500 78500
Run times(ms)
Run times(ms)
63500 63500
48500 48500
33500 33500
18500 18500
3500 3500
25 30 35 40 25 30 35 40
Max Support Max Support
UP-Rare Growth FHURIM UP-Rare Growth FHURIM
Hình 5. Kết quả so sánh thời gian thực thi của thuật toán Up-Rare Growth so với FHURIM trên CSDL Foodmart và
Mushroom
IV. KẾT LUẬN
Khai phá tập mục hữu ích cao hiếm là một mở rộng của bài toán khai phá tập mục hữu ích cao nhằm mục đích
tìm ra trong CSDL liệu giao tác tất cả tập mục hữu ích cao nhưng không phổ biến trong CSDL. Trong bài báo này
chúng tôi đề xuất thuật toán có tên gọi là FHURIM để khai phá nhanh tập mục hữu ích cao hiếm mà không cần trải qua
pha sinh tập ứng viên dựa trên cấu trúc utility-list và chiến lược tỉa EUCS. Chúng tôi chạy thực nghiệm trên 2 CSDL
thực với các trường hợp khác nhau về ngưỡng hữu ích tối thiểu và ngưỡng hỗ trợ cực đại, kết quả cho thấy thuật toán
của chúng tôi nhanh hơn thuật toán hiện tại.
TÀI LIỆU THAM KHẢO
[1] R. Agrawal, T. Imieliński, and A. Swami, "Mining association rules between sets of items in large databases," in
Acm sigmod record, 1993, pp. 207-216.
[2] N. Bloom, R. Sadun, and J. V. Reenen, "The organization of firms across countries," The Quarterly Journal of
Economics, vol. 7, pp. 1663-1705, 2012.
[3] H. Yao, H. J. Hamilton, and C. J. Butz, "A foundational approach to mining itemset utilities from databases," in
Proceedings of the 2004 SIAM International Conference on Data Mining, 2004, pp. 482-486.
[4] Q. H. Duong, P. Fournier-Viger, H. Ramampiaro, K. Nørvåg, and T. L. Dam, "Efficient high utility itemset
mining using buffered utility-lists," Applied Intelligence, vol. 48, pp. 1859-1877, 2018.
[5] A. Erwin, R. P. Gopalan, and N. Achuthan, "Efficient mining of high utility itemsets from large datasets," in
Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2008, pp. 554-561.
[6] P. Fournier-Viger, C. W. Wu, S. Zida, and V. S. Tseng, "FHM: Faster high-utility itemset mining using estimated
utility co-occurrence pruning," in International symposium on methodologies for intelligent systems, 2014, pp. 83-
92.
[7] M. Liu and J. Qu, "Mining high utility itemsets without candidate generation," in Proceedings of the 21st ACM
international conference on Information and knowledge management, 2012, pp. 55-64.
[8] Y. Liu, W. K. Liao, and A. Choudhary, "A fast high utility itemsets mining algorithm," in Proceedings of the 1st
international workshop on Utility-based data mining, 2005, pp. 90-99.
[9] V. S. Tseng, C. W. Wu, B. E. Shie, and P. S. Yu, "UP-Growth: an efficient algorithm for high utility itemset
mining," in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data
mining, 2010, pp. 253-262.
[10] H. Yao and H. J. Hamilton, "Mining itemset utilities from transaction databases," Data & Knowledge
Engineering, vol. 59, pp. 603-626, 2006.
[11] S. Zida, P. Fournier-Viger, J. C. W. Lin, C. W. Wu, and V. S. Tseng, "EFIM: a fast and memory efficient
algorithm for high-utility itemset mining," Knowledge and Information Systems, vol. 51, pp. 595-625, 2017.
[12] J. Pillai, O. Vyas, and M. Muyeba, "Huri–a novel algorithm for mining high utility rare itemsets," in Advances in
Computing and Information Technology, ed: Springer, 2013, pp. 531-540.
[13] V. Goyal, S. Dawar, and A. Sureka, "High utility rare itemset mining over transaction databases," in International
Workshop on Databases in Networked Information Systems, 2015, pp. 27-40.
[14] J. Pillai, O. Vyas, and M. K. Muyeba, "A Fuzzy Algorithm for Mining High Utility Rare Itemsets-FHURI,"
International Journal on Recent Trends in Engineering & Technology, vol. 10, p. 1, 2014.
[15] P. Fournier-Viger. (2019). An Open-Source Data Mining Library. Available: http://www.philippe-fournier-
viger.com/spmf/index.php?link=datasets.php
- Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 167
FHURIM: HIGH UTILITY RARE ITEMSETS MINING ALGORITHM
Huynh Trieu Vy, Le Quoc Hai, Truong Ngoc Chau
ABSTRACT: Mining rare high utility itemsets aims at discovering the itemsets such that their support are under maximal support
threshold and no less than minimal utility threshold given by users. The Two-phase rare high utility itemset mining algorithms
require high running time. Especially, at the high maximal support threshold, the set of candidate itemsets is very large. In order to
overcome this drawback, this paper proposes the rare high utility itemset mining algorithm without generating candidate itemsets.
The utility-list structure is applied to store utility and support value of itemsets and for effectively pruning searching space. The
experiment results indicate that the proposed algorithm is better than the state-of-the-art.
nguon tai.lieu . vn
