Khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch có lợi nhuận âm
Nguyễn Văn Lễ, Nguyễn Thị Thanh Thủy, Mạnh Thiên Lý
KHAI THÁ C TẬP HỮU Í CH CAO TƯƠNG
QUAN TRÊN CƠ SỞ DỮ LIỆU GIAO DỊCH
CÓ LỢI NHUẬN Â M
Nguyễn Văn Lễ*, Nguyễn Thị Thanh Thủy+, Mạnh Thiên Lý+
*Khoa Cô ng nghệ thô ng tin, Trường Đại học Cô ng nghiệp Thực phẩm TPHCM
+Khoa Cô ng nghệ thông tin, Trường Đại học Cô ng nghiệp Thực phẩm TPHCM
thấy có thể rất lớn vì chúng chỉ tìm thấy các HUI dựa trên
ngưỡng tối thiểu và bỏ qua mối tương quan giữa các mục
bên trong mẫu. Nhiều HUI chứa các mặt hàng có tương
quan yếu và thực tế không mang lại ý nghĩa. Để giải quyết
vấn đề này, J. C. W. Lin và cộng sự đã đề xuất thuật toán
FDHUP [10] để khai thác HUI có ràng buộc tần suất cao.
Sau đó, vào năm 2017, W. Gan và cộng sự đề xuất thuật
toán CoHUIM [11] xem xét cả tính tương quan và lợi
nhuận giữa các sản phẩm trong giao dịch. Tuy nhiên, thuật
toán này tạo ra một tập hợp lớn các ứng cử viên và việc
quét lại cơ sở dữ liệu gốc nhiều lần làm tăng đáng kể thời
gian thực hiện và bộ nhớ lưu trữ. Năm 2019, nhóm tác giả
W. Gan và cộng sự đề xuất thuật toán CoUPM [12] cải
tiến từ thuật CoHUIM bằng việc sử dụng cấu trúc lưu trữ
Ulility-List tăng hiệu suất khai thác tập hữu ích cao tương
quan. Tuy nhiên, thuật toán này vẫn kém hiệu quả khi
thực thi trên cơ sở dữ liệu có lợi nhuận âm. Để giải quyết
vấn đề này, chúng tôi đề xuất một thuật toán mới có tên là
CHN để khai thác tập hữu ích cao tương quan một cách
hiệu quả trên cơ sở dữ liệu giao dịch có lợi nhuận âm.
Tóm tắt: Việc khai thác tập hữu ích cao tương quan
(Correlated Hight Utility Itemset) trong cơ sở dữ liệu
giao dịch đã được nghiên cứu rộng rãi để khám phá hành
vi mua hàng của người dùng. Từ đó, các nhà quản lý
doanh nghiệp có thể điều chỉnh chiến lược bán hàng một
cách phù hợp để tăng lợi nhuận. Các cách tiếp cận khai
thác tập hữu ích cao tương quan trước đây chỉ thực hiện
trên cơ sở dữ liệu có lợi nhuận dương mà ít khi quan tâm
đến các giá trị lợi nhuận âm. Trên thực tế, các doanh
nghiệp có thể giảm lợi nhuận của các mặt hàng tồn kho
lâu ngày để kích thích người mua, thậm chí có thể giảm
lợi nhuận đến mức âm để tiêu thụ hết lượng hàng tồn
kho. Để khai thác tập hữu ích cao tương quan hiệu quả
trên cơ sở dữ liệu giao dịch có lợi nhuận âm, chúng tôi đề
xuất thuật toán CHN (Correlated High utility itemset with
Negative profit). Đánh giá thử nghiệm trên cả năm cơ sở
dữ liệu Chess, Mushroom, Pumsb, Retail và Kosarak và
cho thấy thuật toán CHN có hiệu suất thực thi một cách
hiệu quả.
Những đóng góp chính của bài báo:
Từ khóa: Tập hữu ích cao, tính tương quan, khai thác
dữ liệu, cơ sở dữ liệu giao dịch, tập hữu ích cao tương
quan.
a) Áp dụng cấu trúc dữ liệu PNU – List để lưu trữ dữ
liệu trong quá trình khai thác tập hữu ích cao tương quan
CHUIs trên cơ sở dữ liệu giao dịch có lợi nhuận âm.
I. GIỚI THIỆU
b) Áp dụng nhiều chiến lược tỉa để giảm không gian
tìm kiếm như: U-Prune, LA-Prune, Kulc-Prune, EUCS.
Xã hội ngày càng phát triển thì nhu cầu mua sắm của
khách hàng ngày càng tăng. Các tổ chức kinh doanh cũng
đã được thành lập ở khắp mọi nơi với các hình thức bán
hàng đa dạng. Khi khách hàng càng có nhiều sự lựa chọn
thì doanh nghiệp càng phải nghiên cứu thói quen mua
hàng của họ. Ban đầu, các doanh nghiệp quan tâm đến
việc tìm hiểu các mặt hàng thường được khách hàng mua
cùng nhau. Nhiều thuật toán đã được đề xuất để khai thác
các luật kết hợp để giải quyết hiệu quả nhu cầu này [1,2].
Tuy nhiên, luật kết hợp có sự giới hạn là1không đề cập
đến lợi nhuận của sản phẩm. Các thuật toán khai thác tập
hữu ích cao (HUIM) đã được nghiên cứu để tìm ra tập các
sản phẩm có lợi nhuận cao (High Utility Itemset – HUI)
như: Thuật toán Two-Phase [3], UP-Growth [4], HUI-
Miner [5], FHM [6], EFIM [7], D2HUP [8]. Năm 2016,
Lin và cộng sự đề xuất thuật toán FHN [9] khai thác HUI
trên cơ sở dữ liệu có lợi nhuận âm một cách hiệu quả.
Mặc dù các thuật toán này khá hữu ích trong việc khám
phá các tập hữu ích cao, tuy nhiên số lượng HUI được tìm
c) Kết quả thực nghiệm so sánh với thuật toán CoUPM
cho thấy thuật toán CHN có thời gian thực hiện nhanh hơn
thuật toán CoUPM trên 5 cơ sở dữ liệu là Chess,
Mushroom, Pumsb, Retail và Kosarak.
Cấu trúc bài báo được chia làm 6 phần. Phần 1 trình
bày giới thiệu; Phần 2 trình bày các công trình liên quan;
Phần 3 trình bày các định nghĩa và ký hiệu; Phần 4 trình
bày thuật toán đề xuất CHN; Phần 5 trình bày kết quả thực
nghiệm và đánh giá; Phần 6 trình bày kết luận và hướng
phát triển.
II. CÁ C CÔ NG TRÌ NH LIÊN QUAN
Khai thác tập hữu ích cao (HUI) đã được nghiên cứu
rộng rãi và có nhiều ứng dụng trong thực tế để hỗ trợ việc
kinh doanh hiệu quả hơn. Các tiếp cận ban đầu khai thác
HUI chủ yếu dựa trên hai pha, trong đó pha một sinh ra
các ứng viên có khả năng là tập hữu ích cao, pha hai thực
hiện quét lại cơ sở dữ liệu để xác định ứng viên nào thực
sự là HUI. Một số thuật toán được đề xuất trong giai đoạn
này như: Two-Phase [3], CTU-Mine [13], TWU-Mining
Tác giả liên hệ: Nguyễn Văn Lễ,
Email: [email protected]du.vn
Đến tòa soạn: 8/2020, chỉnh sửa: 9/2020, chấp nhận đăng: 10/2020.
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
94
KHAI THÁ C TẬP HỮU ÍCH CAO TƯƠNG QUAN TRÊN CƠ SỞ DỮ LIỆU GIAO DỊCH CÓ LỢI NHUẬN Â M
[14], UP-Growth [4], UP-Growth+ [15]. Những thuật toán
này tốn nhiều thời gian và bộ nhớ vì phải thực hiện trên
hai pha và quét cơ sở dữ liệu nhiều lần. Năm 2012, Liu và
cộng sự đề xuất thuật toán HUI-Miner [5] cùng với cấu
trúc dữ liệu mới là Utility-List để khai thác HUI trên một
pha cùng với chiến lược tỉa TWU đã làm giảm đáng
không gian tìm kiếm và tăng hiệu suất thực thi của thuật
toán. Năm 2014, Fournier và cộng sự bổ sung chiến lược
tỉa EUCP vào thuật toán HUI-Miner và đề xuất thuật toán
FHM [6] có thời gian khai thác HUI nhanh vượt trội so
với thuật toán HUI-Miner. Năm 2017, Zida cùng cộng sự
đề xuất thuật toán EFIM [7] sử dụng cơ chế chiếu và gộp
trên cơ dữ liệu có hiệu quả cao khi khai thác trên cơ sở dữ
liệu thưa. Năm 2018, Krishnamoorthy đề xuất thuật toán
HMiner [16] với cấu trúc dữ liệu mới là CUL và nhiều
chiến lược tỉa hiệu quả cho hiệu suất thực thi vượt trội cả
về thời gian và bộ nhớ sử dụng so với thuật toán EFIM.
Tuy nhiên, các thuật toán này vẫn kém hiệu quả và tìm ra
số lượng HUI không đầy đủ khi khai thác trên cơ sở dữ
liệu có lợi nhuận âm. Để giải quyết vấn đề này, Lin và
cộng sự đã đề xuất cải tiến cấu trúc Utility-list để lưu trữ
tách biệt lợi nhuận dương và âm và đề xuất thuật toán
FHN [9] để khai thác đầy đủ tập HUI trên cơ sở dữ liệu
giao dịch có lợi nhuận âm. Ngoài ra, năm 2019, Singh và
cộng sự đề xuất thuật toán EHNL [17] để khai thác HUI
hiệu quả với ràng buộc chiều dài tập mục trên cơ sở dữ
liệu có lợi nhuận âm.
Cho tập 퐼 = {ꢀ1, ꢀ2, . . . , ꢀ푚} gồm m mục phân biệt
trong cơ sở dữ liệu giao dịch 퐷 = {푇 , 푇2, . . . , 푇 }, với n là
1
푛
{ |
số lượng giao dịch trong 퐷 . ∀ 푇 ∈ 퐷 , 푇 = 푥푙 푙 =
푗
푗
1, 2, … , 푁 , 푥푙 ∈ 퐼}, với 푁 là số các mục trong giao dịch
푗
푗
푇 . Bảng 1 trình bày ví dụ về cơ sở dữ liệu giao dịch 퐷 và
푗
Bảng 2 trình bày lợi nhuận các mục.
Mỗi mục 푥푖 trong tập mục I có một giá trị lợi nhuận
xác định là 푃(푥푖) và có một số lượng mua 푄(푥푖, 푇 ) trong
푗
giao dịch 푇 . Độ hữu ích của mục 푥푖 trong giao dịch 푇 ký
푗
푗
( )
hiệu là 푈(푥푖, 푇 ) với 푈(푥푖, 푇 ) = 푃 푥푖 ∗ 푄(푥푖, 푇 ).
푗
푗
푗
{
}
Độ hữu ích của một tập mục 푋 = 푥1, 푥2, … , 푥푘 ⊆ 푇
푗
∑
định nghĩa là 푈(푋, 푇 ) = 푥 ∈푋 푈(푥푖 , 푇 ) . Độ hữu ích
푗
푗
푖
dương của tập mục 푋 trong giao dịch 푇 được định nghĩa
푗
∑
là 푃푈(푋, 푇 ) =
푈(푥푖 , 푇 ). Độ hữu ích âm
푗
푗
푥 ∈푋 푈(푥 ,푇 )>0
푖
푖
푗
của tập 푋 trong giao dịch 푇 được định nghĩa là
푗
∑
푁푈(푋, 푇 ) =
푈(푥푖 , 푇 )
.
Ta
có
푗
푗
푥 ∈푋 푈(푥 ,푇 )<0
푖
푖
푗
푈(푋, 푇 ) = 푃푈(푋, 푇 ) + 푁푈(푋, 푇 ).
푗
푗
푗
Độ hữu ích dương của tập mục 푋 trong cơ sở dữ liệu
( )
∑
퐷 được định nghĩa 푃푈 푋 = 푋⊆푇 푇 ∈퐷 푃푈(푋 , 푇 ). Độ
푗
푗
푗
( )
hữu ích âm của 푋 trong 퐷 được định nghĩa 푁푈 푋 =
∑
푋⊆푇 푇 ∈퐷 푁푈(푋 , 푇 ). Độ hữu ích của tập mục 푋 trong
푗
푗
푗
( )
( )
cơ sở dữ liệu 퐷 được định nghĩa là 푈 푋 = 푃푈 푋 +
푁푈(푋). Độ hữu ích dương của một giao dịch 푇 ∈ 퐷
푗
Tập hữu ích cao được khai thác với các thuật toán
trình bày ở trên đã có nhiều ứng dụng hữu ích trong thực
tế. Tuy nhiên, các thuật toán này chỉ quan tâm đến độ hữu
ích của tập mục kết quả mà không quan tâm đến sự tương
quan giữa các mục bên trong. Do đó, kết quả khai thác
được còn chứa nhiều tập mục có mối tương quan thấp
giữa các mục bên trong và không có ý nghĩa trong thực tế.
Ví dụ, trong cơ sở dữ liệu phát sinh một giao dịch mua
hàng gồm một sản phẩm (A) có trị giá lợi nhuận rất cao
kèm với một sản phẩm (B) có lợi nhuận thấp và chỉ có
một giao dịch này trong cơ sở dữ liệu.
∑
được định nghĩa là 푃푇푈(푇 ) =
>0 푈(푥푖 , 푇 )
푗
( )
푥 ∈푇 U 푥
푖
푗
푖
푗
[9].
Bảng I. Cơ sở dữ liệu giao dịch có lợi nhuận âm
Độ hữu ích
TID Giao dịch (푻) Số lượng (푸) Độ hữu ích (푼)
dương (푷푻푼)
푇1
푇2
푇3
푎, 푏, 푐, 푑
푎, 푏, 푐
3, 1, 4, 2
3, 3, 2
9, -1, 16, -4
9, -3, 8
25
17
25
32
38
16
17
32
푎, 푐, 푑, 푒, 푓
푏, 푐, 푒
4, 1, 2, 2, 1
2, 5, 4
12, 4, -4, 6, 3
-2, 20, 12
푇
4
푇5
푇6
푇7
푇8
푏, 푐, 푑, 푒
푎, 푏, 푐, 푑, 푒, 푓
푐, 푒
6, 5, 4, 6
-6, 20, -8, 18
Khi khai thác HUI, tập gồm hai sản phẩm này sẽ được
tìm thấy vì lợi nhuận cao vượt ngưỡng mức lợi nhuận tối
thiểu. Tuy nhiên, sự tương quan giữa hai sản phẩm này là
rất kém vì chỉ có một giao dịch trong cơ sở dữ liệu nên khi
kết luận rằng khi khách hàng mua sản phẩm A thì sẽ mua
kèm sản phẩm B là không chính xác. Để giải quyết vấn đề
này, nhiều nghiên cứu đã được đề xuất để tính toán mối
tương quan giữa các mục trong một tập mục được khai
thác. Khái niệm về "độ đo" giữa các mục được
Omiecinski [18] đưa ra từ rất sớm để khai thác luật kết
hợp với ba độ đo là any-confidence, all-confidence và
bond. Tuy nhiên, ba độ đo này vẫn chưa đánh giá được
mối tương quan giữa các mục trong tập mục được khai
thác. Năm 2018, Fournier-Viger và cộng sự [19] đã trình
bày khái niệm "Correlation" dựa trên ba độ đo trên và đề
xuất thuật toán CHIs để khai thác tập hữu ích cao tương
quan trên cơ sở dữ liệu giao dịch. Bên cạnh đó, Lin và
cộng sự đề xuất thuật toán CoHUIM [11] khai thác tập
hữu ích cao tương quan (CoHUI) dựa trên độ đo Kulc và
cơ chế chiếu trên cơ sở dữ liệu trong quá trình khai thác.
Năm 2019, Gan và cộng sự [12] đề xuất thuật toán
CoUPM khai thác CoHUI dựa trên cấu trúc dữ liệu
Utility-list với nhiều chiến lược tỉa khác nhau đã cho kết
quả khai thác CoHUI hiệu quả hơn thuật toán CoHUIM.
2, 5, 1, 3, 1, 1 6, -5, 4, -6, 3, 3
2, 3
8, 9
푐, 푑, 푒
5, 2, 4
20, -4, 12
Bảng II. Lợi nhuận của các mục
Các mục (Items)
Lợi nhuận (P)
1
3
2
3
4
4
5
6
3
-1
-2
3
Định nghĩa 1. Tập mục 푋 được gọi là một tập mục
hữu ích cao (퐻푈퐼) nếu độ hữu ích của 푋 lớn hơn hoặc
bằng giá trị ngưỡng độ hữu ích tối thiểu (minUtil). Trong
đó giá trị minUtil được cung cấp bởi người dùng [16]. Ta
{ |
có: 퐻푈퐼푠 = 푋 푈(푋) >= 푚ꢀ푛푈푡ꢀ푙}
Định nghĩa 2. Giá trị Positive Transaction Weighted
Utility (푃푇푊푈) của tập mục 푋 trong 퐷 ký hiệu là
푃푇푊푈 푋 = 푋⊆푇 ∈퐷 푃푇푈(푇 ) [9]. Ví dụ, trong Bảng 1,
( )
∑
푗
푗
(
)
( ) ( )
(
)
ta có 푃푇푊푈 푎푏 = 푃푇푈 푇 + 푃푇푈 푇2 + 푃푇푈 푇6 =
1
25 + 17 + 26 = 68. Bảng 3 trình bày các giá trị 푃푇푊푈
của các tập mục gồm một phần tử trong D.
( )
Tính chất 1. Nếu 푃푇푊푈 푋 < 푚ꢀ푛푈푡ꢀ푙 thì mọi tập
mục mở rộng từ 푋 đều không là 퐻푈퐼 [16].
Định nghĩa 3. Độ hỗ trợ của tập mục 푋 trong cơ sở dữ
liệu 퐷 ký hiệu 푆푈푃(푋) là số lượng các giao dịch chứa 푋
III. CÁ C ĐỊNH NGHĨA VÀ KÝ HIỆU
(
)
trong 퐷 [16]. Ví dụ 푆푈푃 푎푏 = 3 vì có 3 giao dịch chứa
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG 95
Nguyễn Văn Lễ, Nguyễn Thị Thanh Thủy, Mạnh Thiên Lý
{ab} là 푇 , 푇2 và 푇6. Độ hỗ trợ của mỗi mục trong cơ sở
dữ liệu 퐷 thể hiện ở Bảng 3.
Định nghĩa 8. Độ hữu ích dương còn lại sau tập mục
푋 trong giao dịch 푇 , ký hiệu là 푃푅푈(푋, 푇 ), là tổng độ
1
푗
푗
hữu ích của tất cả các mục có độ hữu ích dương trong tập
Bảng III. Độ hỗ trợ của các mục
푅푒(푋, 푇 ) [9]:
푗
Items
f
41
2
a
83
4
b
128
5
d
136
5
e
160
6
c
202
8
푃푅푈(푋, 푇 ) =
∑
푈(푥푖, 푇 )
푗
PTWU
푗
푥 푅푒(푋,푇 )푈(푥 ,푇 )>0
SUPPORT
푖
푗
푖
푗
(
)
=
)
Ví dụ: Với dữ liệu trong Bảng 4, 푃푅푈 푎푏, 푇6
Định nghĩa 4. (Thứ tự các mục) Thứ tự toàn phần của
các mục trong cơ sở dữ liệu 퐷 được sắp xếp tăng dần
theo độ hỗ trợ [11]. Xét 2 mục x và y, Ta có 푥 ≺ y nếu
(
)
(
)
(
푈 푒, 푇6 + 푈 푐, 푇6 = 3 + 4 = 7. Trong đó 푈 푑, 푇6 sẽ
không tính vào 푃푅푈 vì có độ hữu ích âm.
( )
( )
푆푈푃 푥 < 푆푈푃(푦). Trường hợp 푆푈푃 푥 = 푆푈푃(푦) thì
thứ tự dựa vào thứ tự Alphabet của x và y. Với cơ sở dữ
liệu 퐷 (Bảng 1) và độ hỗ trợ (Bảng 3) thì thứ tự toàn
phần được xác định là f ≺ a ≺ b ≺ d ≺ e ≺ c
IV. THUẬT TOÁ N CHN
A. Cấu trúc PNU-List
PNU-List được cấu trúc lại từ cấu trúc dữ liệu Utility-
List [5,9]. Mỗi tập mục được biểu diễn bởi một PNU-List
tương ứng. Cấu trúc PNU-List của một tập mục 푋 lưu trữ
tập các bộ dữ liệu, mỗi bộ chứa bốn thành phần là
(푇ꢀ푑, 푃푢푡ꢀꢂ, 푁푢푡ꢀꢂ, 푃푟푢푡ꢀꢂ). Trong đó, 푇ꢀ푑 là số thứ tự
của giao dịch có chứa 푋, 푃푢푡ꢀꢂ 푣à 푁푢푡ꢀꢂ là độ hữu ích
dương và độ hữu ích âm của tập mục 푋 trong giao dịch
푇ꢀ푑, 푃푟푢푡ꢀꢂ là tổng độ hữu ích dương của các mục sau 푋
trong giao dịch 푇ꢀ푑.
Với giá trị minUtil = 42, mục 푓 bị loại bỏ khỏi cơ sở dữ
liệu 퐷 (Tính chất 1) và toàn bộ cơ sở dữ liệu 퐷 được sắp
xếp lại theo thứ tự toàn phần được trình bày trong Bảng 4.
Định nghĩa 5. Sự tương quan giữa các phần tử trong
một tập mục 푋 = {푥1, 푥2, … , 푥푘} được định nghĩa là
1
푆푢푝(푋)
( )
푘푢ꢂ푐 푋 =
∑
( )
)). Với 0 푘푢ꢂ푐 푋 1 [11].
(
푥 ∈푋
푖
(
푘
sup 푥
푖
( )
Giá trị 푘푢ꢂ푐 푋 càng gần 1 thì tính tương quan giữa các
PNU-List của tập mục một phần tử gồm năm mục
được sắp xếp theo thứ tự toàn phần a ≺ b ≺ d ≺ e ≺ c.
Trong đó, mục 푓 đã bị loại do 푃푇푊푈(푓) < ꢁꢀ푛푈푡ꢀꢂ
(Tính chất 1). PNU-List của tập mục {a} gồm 4 bộ với
Tid lần lượt có giá trị là 1, 2, 3, 6 nghĩa là tập mục {a}
( )
mục trong 푋 càng cao. Ngược lại, 푘푢ꢂ푐 푋 càng gần 0 thì
tính tương quan giữa các mục trong X càng thấp.
1
sup (푎푏)
1
(
)
Ví dụ: 푘푢ꢂ푐 푎푏 = (
+
sup (푎푏)) = (3 + 3) =
( )
sup 푎
2
sup (푏) 2 4 5
0.675
xuất hiện trong các giao dịch tương ứng 푇 , 푇2, 푇3, 푇6 trong
1
Tính chất 2. Xét thứ tự toàn phần 푥1 ≺ 푥1 ≺ ⋯ ≺
푥푘 ≺ 푥푘+1 của các mục trong cơ sở dữ liệu 퐷, khi đó, giá
trị kulc thỏa tính chất Downward closure là
cơ sở dữ liệu D (Bảng 4). Xét bộ thứ nhất với Tid=1, ta có
(
)
độ hữu ích dương 푃푢푡ꢀꢂ = 푈 푎, 푇 = 9, độ hữu ích âm
1
푁푢푡ꢀꢂ = 0 (vì tập mục {푎} chỉ có 1 phần tử là a có giá trị
độ hữu ích dương là 9, không có phần tử nào khác có giá
trị độ hữu ích âm); độ hữu ích dương của các mục sau {푎}
(
)
(
)
푘푢ꢂ푐 푥1, … , 푥푘+1 ≤ 푘푢ꢂ푐 푥1, … , 푥푘 [11].
Bảng IV. Cơ sở dữ liệu giao dịch sau khi loại bỏ 푓 và sắp
là 푃푟푢푡ꢀꢂ = 16 (vì các mục sau {푎} trong giao dịch 푇
1
xếp theo thứ tự toàn phần
gồm {b, d, c} nhưng chỉ 푐 có độ hữu ích dương là 16 còn
b và d có độ hữu ích âm). Tương tự cho các bộ còn lại và
các PNU-List khác.
Độ hữu ích
TID Giao dịch (푻) Số lượng (푸) Độ hữu ích (푼)
dương (푷푻푼)
푇1
푇2
푇3
푎, 푏, 푑, 푐
3, 1, 2, 4
9, -1, -4, 16
25
17
22
32
38
13
17
32
B. Các chiến lược tỉa
푎, 푏, 푐
3, 3, 2
9, -3, 8
푎, 푑, 푒, 푐
푏, 푒, 푐
4, 2, 2, 1
2, 4, 5
12, -4, 6, 4
-2, 12, 20
-6, -8, 18, 20
6, -5, -6, 3, 4
9, 8
Chiến lược tỉa được áp dụng trong quá trình khai thác
tập 퐶퐻푈퐼푠 nhằm thu hẹp không gian tìm kiếm đồng thời
tăng hiệu suất thực thi của thuật toán, đặc biệt là thời gian
thực hiện và dung lượng bộ nhớ sử dụng. Các chiến lược
tỉa áp dụng trong bài báo này gồm: U-Prune, Kulc-Prune,
LA-Prune và EUCS-Prune [5,6,10,11].
푇
4
푇5
푇6
푇7
T8
푏, 푑, 푒, 푐
푎, 푏, 푑, 푒, 푐
푒, 푐
6, 4, 6, 5
2, 5, 3, 1, 1
3, 2
푑, 푒, 푐
2, 4, 5
-4, 12, 20
Chiến lược 1 (U-Prune): Nếu tổng độ hữu ích dương
của tập mục 푋 và tổng độ hữu ích dương của các mục sau
푋 nhỏ hơn ꢁꢀ푛푈푡ꢀꢂ thì mọi tập mở rộng từ 푋 đều không
Định nghĩa 6. Tập mục 푋 được gọi là tập hữu ích cao
tương quan (Correlated High Utility Itemset - CHUI) nếu
( )
( )
푘푢ꢂ푐 푋 ≥ ꢁꢀ푛퐶표푟 và 푈 푋 ≥ ꢁꢀ푛푈푡ꢀꢂ . Trong đó
minUtil là giá trị ngưỡng độ hữu ích tối thiểu và minCor
là giá trị ngưỡng tương quan tối thiểu [11].
( )
( )
phải là 퐶퐻푈퐼 . Nghĩa là nếu 푃푈 푋 + 푃푅푈 푋 <
ꢁꢀ푛푈푡ꢀꢂ thì 푌 푋, 푌 퐶퐻푈퐼. Khi đó ngừng mở rộng
với tập mục 푋.
{
( )
}
퐶퐻푈퐼푠 = 푋 ⊆ 퐼 | 푈 푋 ≥ ꢁꢀ푛푈푡ꢀꢂ ∧ 푘푢ꢂ푐(푋) ≥ ꢁꢀ푛퐶표푟
Ví dụ: Xét tập mục {푎, 푒} với PNU-List tương ứng
(
)
(
)
Ví dụ, trong Bảng 4, 푈 푎푏푐 = 43, 푘푢ꢂ푐 푎푏푐 =
0.575 . Với ꢁꢀ푛푈푡ꢀꢂ < 43 và ꢁꢀ푛퐶표푟 < 0.575 thì tập
mục {푎푏푐} là một CHUI. Ngược lại, tập mục {푎푏푐} không
phải CHUI.
(
)
(
)
∑(
)
trong Hình 1, 푈 푎푒 + 푅푈 푎푒 = 푃푢푡ꢀꢂ + 푃푟푢푡ꢀꢂ =
27 + 8 = 35 < ꢁꢀ푛푈푡ꢀꢂ = 42. Khi đó ngừng mở rộng
với tập {푎, 푒}.
Chiến lược 2 (LA-Prune): Xét 2 tập 푋 và 푌, nếu
Định nghĩa 7. Xét tập mục 푋 ⊆ 푇 , tập tất cả các mục
푗
( ) ∑
푃푈 푋 + 푃푅푈 푋 −
푋⊆푇 ∈ 퐷푌푇
( )
푃푈(푋 , 푇 ) +
푗
푗
푗
sau 푋 trong 푇 được định nghĩa là 푅푒(푋, 푇 ) =
푗
푗
푃푅푈(푋, 푇 ) < ꢁꢀ푛푈푡ꢀꢂ thì tập mục 푋푌 không phải là
{푥푖푇 |푦푋, 푦 ≺ 푥푖 }.
푗
푗
퐶퐻푈퐼 và mọi tập mở rộng từ 푋푌 cũng không phải là
퐶퐻푈퐼 (nghĩa là 푍 푋푌 thì 푍 không phải là 퐶퐻푈퐼 ).
Ví dụ: Với dữ liệu trong Bảng 4, 푅푒(푎푑, 푇 ) = {푐} ,
1
(
)
(
)
푅푒 푎푑, 푇3 = 푅푒 푎푑, 푇6 = {푒, 푐}
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
96
KHAI THÁ C TẬP HỮU ÍCH CAO TƯƠNG QUAN TRÊN CƠ SỞ DỮ LIỆU GIAO DỊCH CÓ LỢI NHUẬN Â M
Hì nh 1. PNU-List của các tập mục 1 phần tử và 2 phần tử
Chiến lược 3 (EUCS-Prune): Xét 푋, 푌 là hai tập
mục 1 phần tử, Nếu 푃푇푊푈(푋, 푌) < ꢁꢀ푛푈푡ꢀꢂ thì tập mục
푋푌 không phải 퐶퐻푈퐼 và mọi tập mở rộng từ 푋푌 cũng
không phải 퐶퐻푈퐼. Khi đó dừng mở rộng với itemset 푋푌.
trong danh sách PNU-List 푈퐿푠. Dòng 2 kiểm tra điều kiện
( )
( )
nếu 푈 푋 ꢁꢀ푛푈푡ꢀꢂ và 푘푢ꢂ푐 푋 ꢁꢀ푛퐶표푟 푋 là một tập
hữu ích cao tương quan 퐶퐻푈퐼. Dòng 5 kiểm tra điều kiện
( )
( )
nếu 푃푈 푋 + 푃푅푈 푋 ꢁꢀ푛푈푡ꢀꢂ ( chiến lược tỉa U-
( )
Prune) và điều kiện 푘푢ꢂ푐 푋 ꢁꢀ푛퐶표푟 (chiến lược tỉa
( )
4 (Kulc-Prune): Nếu 푘푢ꢂ푐 푋 <
Chiến lược
Kulc-prune) thì tạo danh sách các PNU-List mở rộng
(푒푥푈퐿푠 ) từ PNU-List 푋 từ dòng 6 đến 11. ngược lại
ngừng mở rộng với 푋. Dòng 8 áp dụng chiến lược tỉa
EUCS-Prune, nếu 퐸푈퐶푆(푋, 푌) ꢁꢀ푛푈푡ꢀꢂ thì thực hiện
thủ tục 푃푁푈Construct(푃, 푋, 푌) để tạo PNU-List 푋푌 từ 2
PNU-List 푋 và 푌 và thêm vào danh sách 푒푥푈퐿푠, ngược lại
không tạo PNU-List 푋푌. Dòng 12 gọi đệ quy thủ tục
푆푒푎푟푐ℎ퐶퐻푈퐼 để tiếp tục mở rộng không gian tìm kiếm.
ꢁꢀ푛퐶표푟 thì mọi tập mở rộng từ 푋 không phải lài một
퐶퐻푈퐼. Giả sử rằng 푦 là phần tử mở rộng từ tập 푋 để có
(
)
( )
tập 푋푦, theo tính chất 2, ta có 푘푢ꢂ푐 푋푦 < 푘푢ꢂ푐 푋 <
ꢁꢀ푛퐶표푟. Do đó mọi tập mở rộng từ 푋 không phải là
퐶퐻푈퐼.
C. Thuật toán CHN
Thuật toán chính 퐶퐻푁 có dữ liệu đầu vào là cơ sở dữ
liệu giao dịch 퐷 có lợi nhuận âm, kết quả thực hiện thuật
toán là tập hữu cao có tương quan (CHUIs). Đầu tiên quét
Thuật toán 2: 푆푒푎푟푐ℎ퐶퐻푈퐼
Vào: 푃: PNU-List với vai trò là tiền tố; 푈퐿푠: Danh sách
các PNU-List có tiền tô là PNU-List 푃, ꢁꢀ푛푈푡ꢀꢂ:
Ngưỡng độ hữu ích tối thiểu, ꢁꢀ푛퐶표푟 : Ngưỡng
tương quan tối thiểu, 퐸푈퐶푆: Cấu trúc EUCS
Ra: Các tập mục độ hữu ích cao có tương quan (퐶퐻푈퐼푠).
1. for each 푋 푈퐿푠 do
( )
cơ sở dữ liệu 퐷 để tính 푆푈푃 ꢀ , 푅푇푊푈(ꢀ) và 푈(ꢀ) cho
mỗi mục ꢀ 퐼 trình bày
ở
dòng 1. Nếu
푅푇푊푈(ꢀ) ꢁꢀ푛푈푡ꢀꢂ thì đưa i vào tập 퐼∗ và loại bỏ các
mục ꢀ ∉ 퐼∗ khỏi cơ sở dữ liệu 퐷 trình bày ở dòng 2. Dòng
3 sắp xếp các mục trong tập 퐼∗ tăng dần theo độ hỗ trợ
푆푈푃 đồng thời sắp xếp các mục trong cơ sở dữ liệu 퐷
theo thứ tự của 퐼∗. Dòng 4 quét cơ sở dữ liệu 퐷 để xây
dựng danh sách PNU-List cho từng phần tử ꢀ ∉ 퐼∗, ký hiệu
là 푈퐿푠. Dòng 5 khởi tạo cấu trúc 퐸푈퐶푆 và dòng 6 gọi
thực hiện thuật toán 2 là 푆푒푎푟푐ℎ퐶퐻푈퐼.
( )
퐶퐻푈퐼푠 푋
4. end if
5. if
( )
2. if 푈 푋 ꢁꢀ푛푈푡ꢀꢂ 푘푢ꢂ푐 푋 ꢁꢀ푛퐶표푟 then
3.
( )
(푃푈 푋 +
( )
và Kulc-Prune
( )
푃푅푈 푋 ꢁꢀ푛푈푡ꢀꢂ 푘푢ꢂ푐 푋 ꢁꢀ푛퐶표푟) //U-Prune
Thuật toán 1: (Thuật toán chính - CHN)
6.
푒푥푈퐿푠 = //Khởi tạo danh sách PNU-List mở
Vào: 퐷: Cơ sở dữ liệu giao dịch có lợi nhuận âm,
ꢁꢀ푛푈푡ꢀꢂ: Ngưỡng độ hữu ích tối thiểu, ꢁꢀ푛퐶표푟:
Ngưỡng tương quan tối thiểu.
rộng từ X
7.
8.
for each 푌 after 푋 in 푈퐿푠 do
if 퐸푈퐶푆(푋, 푌) ꢁꢀ푛푈푡ꢀꢂ then //Áp dụng chiến
Ra: Các tập mục độ hữu ích cao có tương quan (퐶퐻푈퐼푠)
lược tỉa EUCP
( )
1. Quét cơ sở dữ liệu 퐷 để tính 푆푈푃 ꢀ , 푅푇푊푈(ꢀ) và
9.
10.
푒푥푈퐿푠 푃푁푈Construct(푃, 푋, 푌);
end if
푈(ꢀ) cho mỗi mục ꢀ có trong 퐼.
2. Tính 퐼∗ = {ꢀ 퐼 | 푅푇푊푈(ꢀ) ꢁꢀ푛푈푡ꢀꢂ} và loại bỏ
các mục ꢀ ∉ 퐼∗ khỏi cơ sở dữ liệu 퐷.
3. Sắp xếp 퐼∗ tăng theo 푆푈푃, sắp xếp các mục trong 퐷
theo thứ tự của 퐼∗.
11. end for
12. 푆푒푎푟푐ℎ퐶퐻푈퐼(푋, 푒푥푈퐿푠, ꢁꢀ푛푈푡ꢀꢂ, ꢁꢀ푛퐶표푟,
퐸푈퐶푆); //gọi đệ quy thuật toán.
13.end if
14.end for
4. Quét cơ sở dữ liệu 퐷 để tính PNU-List cho mỗi phần
tử ꢀ ∉ 퐼∗ là 푈퐿푠
5. Khởi tạo cấu trúc 퐸푈퐶푆
6. 푆푒푎푟푐ℎ퐶퐻푈퐼(, 푈퐿푠, ꢁꢀ푛푈푡ꢀꢂ, ꢁꢀ푛퐶표푟, 퐸푈퐶푆)
Thuật toán 3 (푃푁푈퐶표푛푠푡푟푢푐푡) thực hiện kết hợp 2
PNU-List 푃푥 và 푃푦 thành PNU-List 푃푥푦. Dòng 1 khởi
tạo giá trị ban đầu cho 푈퐿퐴 là tổng độ hữu ích dương
푃푈(푃) và độ hữu ích còn lại sau 푃 là 푃푅푈(푃). Dòng 2, 3
duyệt qua từng phần tử 푒푥 푃푥 và tìm phần tử 푒푦 푃푦
sao cho 푒푥. 푡ꢀ푑 = 푒푦. 푡ꢀ푑. Nếu tìm thấy thì tạo phần tử
푒푥푦 kết hợp từ 푒푥 và 푒푦 trong các trường hợp xem xét tại
dòng 4. Nếu PNU-List tiền tố 푃 (trường hợp 1 dòng
4), nghĩa là PNU-List 푃푥푦 đang xây dựng có từ 3 mục trở
lên, ngược lại (trường hợp 2 dòng 7) thì 푃푥푦 là PNU-List
Thuật toán 2 (푆푒푎푟푐ℎ퐶퐻푈퐼) thực hiện đệ quy mở
rộng không gian tìm kiếm để xác định một tập mục có
phải là 퐶퐻푈퐼 hay không. Thuật toán có đầu vào gồm P:
một PNU-List ở mức trên đóng vai trò là tiền tố, danh
sách các PNU-List có tiền tố là P; ngưỡng độ hữu ích tối
thiểu minUtil; ngưỡng tương quan tối thiểu minCor và cấu
trúc 퐸푈퐶푆. Đầu ra là các tập mục hữu ích cao có tương
quan (퐶퐻푈퐼푠). Dòng 1 duyệt qua từng PNU-List 푋 có
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
97
Nguyễn Văn Lễ, Nguyễn Thị Thanh Thủy, Mạnh Thiên Lý
đang xây dựng chỉ có 2 mục. Dòng 6 tạo phần tử 푒푥푦 ứng
với trường hợp 1, dòng 8 tạo phần tử 푒푥푦 ứng với trường
hợp 2, dòng 10 thêm 푒푥푦 vào PNU-List 푃푥푦. Dòng 12 xét
điều kiện nếu không tồn tại 푒푦 푃푦 mà 푒푥. 푡ꢀ푑 = 푒푦. 푡ꢀ푑
thì áp dụng chiến lược tỉa LA-Prune từ dòng 13 đến 15 để
loại bỏ sớm những tập mục không phải là 퐶퐻푈퐼. Dòng 18
trả về kết quả là PNU-List 푃푥푦.
thử nghiệm được tải từ thư viện SPMF [20] là các cơ sở
dữ liệu giao dịch có lợi nhuận âm gồm Chess, Mushroom,
Pumsb, Retail và Kosarak. Chi tiết các cơ sở dữ liệu trình
bày trong Bảng 5. Thực nghiệm của thuật toán CHN được
so sánh với thuật toán mới nhất cùng khai thác tập CHUI
là CoUPM [12]. Kết quả thực nghiệm được đánh giá dựa
trên thời gian thực thi và dung lượng bộ nhớ sử dụng.
Bảng V. Đặc điểm các cơ sở dữ liệu thực nghiệm
Thuật toán 3: (푃푁푈퐶표푛푠푡푟푢푐푡)
Vào: 푃: PNU-List với vai trò là tiền tố; 푃푥, 푃푦: Hai
PNU-List cần kết hợp; ꢁꢀ푛푈푡ꢀꢂ: Ngưỡng độ hữu
ích tối thiểu.
Ra: 푃푥푦: PNU-List sau khi kết hợp 푃푥 và 푃푦.
1. 푆푒푡 푈퐿퐴 = 푃푈(푃) + 푃푅푈(푃);
Cơ sở dữ Số lượng Số lượng Độ dài trung Độ dày
liệu
Chess
Mushroom 8,124
giao dịch item (I)
bình (A)
37
(A/I) %
49.3333
3,196
75
119
23
19.3277
3.5021
0.0625
0.0196
Pumsb
Retail
49,046
88,162
990,002
2113
16,470
41,270
74
2. for each element 푒푥 푃푥 then
10.3
8.1
3.
4.
5.
6.
if 푒푦 푃푦 푒푥. 푡ꢀ푑 = 푒푦. 푡ꢀ푑 then
if 푃 then
Kosarak
Tìm 푒 푃 sao cho 푒. 푡ꢀ푑 = 푒푥. 푡ꢀ푑;
푒푥푦 =< 푒푥. 푡ꢀ푑, 푒푥. 푃푢푡ꢀꢂ + 푒푦. 푃푢푡ꢀꢂ −
푒. 푃푢푡ꢀꢂ, 푒푥. 푁푢푡ꢀꢂ + 푒푦. 푁푢푡ꢀꢂ −
푒. 푁푢푡ꢀꢂ , 푒푦. 푃푟푢푡ꢀꢂ >;
Hình 2, 3 trình bày kết quả thực nghiệm so sánh giữa
thuật toán CHN và thuật toán CoUPM về thời gian thực
thi và bộ nhớ sử dụng. Kết quả thực nghiệm cho thấy
thuật toán CHN có thời gian thực thi hiệu quả hơn thuật
toán CoUPM trên tất cả các cơ sở dữ liệu từ rất dày như
Chess đến cơ sở dữ liệu rất thưa như kosarak. Tuy nhiên
bộ nhớ sử dụng của thuật toán CHN chỉ có hiệu quả hơn
thuật toán CoUPM ở cơ sở dữ liệu Pumsb trên tất cả các
ngưỡng và các ngưỡng tương quan lớn.
7.
else
8. 푒푥푦 = < 푒푥. 푡ꢀ푑, 푒푥. 푃푢푡ꢀꢂ + 푒푦. 푃푢푡ꢀꢂ, 푒푥. 푁푢푡ꢀꢂ +
푒푦. 푁푢푡ꢀꢂ, 푒푦. 푃푟푢푡ꢀꢂ >;
9.
end if
10. 푃푥푦 푒푥푦;
11. else
Hình 2 trình bày kết quả thực nghiệm của hai thuật
toán CHN và CoUPM trên cơ sở dữ liệu rất dày Chess và
dày trung bình Mushroom. Với cơ sở dữ liệu Chess, tại
ngưỡng minCor=0.86 thời gian thực hiện của thuật toán
CHN nhanh hơn thuật toán CoUPM từ 5 đến 7 lần. Đặc
biệt, khi giảm ngưỡng minCor còn 0.7 thì thời gian thực
hiện của CHN càng hiệu quả và có thời gian thực hiện ít
hơn thuật toán CoUPM lên đến 25 lần tại ngưỡng
minUtil=130,000. Với cơ sở dữ liệu Mushroom, thời gian
thực hiện của thuật toán CHN tốt hơn thuật toán CoUPM
ở tất cả các ngưỡng minCor và minUtil. Kết quả này
chứng tỏ rằng các chiến lược tỉa và cấu trúc dữ liệu sử
dụng trong thuật toán CHN là phù hợp khi khai thác tập
CHUI trên cơ sở dữ liệu có lợi nhuận âm.
12. 푈퐿퐴 = 푈퐿퐴 − 푒푥. 푃푢푡ꢀꢂ − 푒푥. 푃푟푢푡ꢀꢂ;
13. if 푈퐿퐴 < ꢁꢀ푛푈푡ꢀꢂ then // áp dụng chiến lược tỉa
LA-Prune
14.
return null;
15. end if
16. end if
17. end for
18. return 푃푥푦;
V. THỰC NGHIỆM
Thuật toán 퐶퐻푁 được cài đặt bằng ngôn ngữ lập trình
Java, chạy thử nghiệm trên máy tính Dell Precision Tower
3620, Intel Core i7-7800X CPU @3.5GHz, bộ nhớ RAM
32GB trên hệ điều hành Windows 10. Các cơ sở dữ liệu
Hì nh 2. So sánh thời gian thực thi trên cơ sở dữ liệu dày
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
SOÁ 03 (CS.01) 2020
98
KHAI THÁ C TẬP HỮU ÍCH CAO TƯƠNG QUAN TRÊN CƠ SỞ DỮ LIỆU GIAO DỊCH CÓ LỢI NHUẬN Â M
Hì nh 3. So sánh thời gian thực thi trên cơ sở dữ liệu thưa
Hì nh 4. So sánh bộ nhớ sử dụng trên cơ sở dữ liệu dày
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
99
Nguyễn Văn Lễ, Nguyễn Thị Thanh Thủy, Mạnh Thiên Lý
Hì nh 5. So sánh bộ nhớ sử dụng trên cơ sở dữ liệu thưa
Hình 3 trình bày kết quả thực nghiệm trên cơ sở dữ
liệu từ thưa như Pumsb cho đến rất thưa như Kosarak.
Kết quả thực nghiệm cho thấy thuật toán CHN có thời
gian thực hiện thấp hơn thuật toán CoUPM trên cả 3 cơ
sở dữ liệu thử nghiệm. Với cơ sở dữ liệu lớn, có độ dài
trung bình của giao dịch cao nhất như cơ sở dữ liệu
Pumsb thì thời gian thực hiện của thuật toán CHN nhanh
hơn thuật toán CoUPM từ 5 đến 10 lần tại ngưỡng
minCor=0.85, từ 10 đến 30 lần tại ngưỡng minCor=0.8.
Đặc biệt với ngưỡng minCor=0.75 thì thuật toán CHN
cho ra kết quả ở tất cả các ngưỡng minUtil còn thuật toán
CoUPM chỉ có kết quả ở 2 ngưỡng minUtil là 10,000,000
và 9,800,000, các ngưỡng còn lại không cho kết quả.
Hình 4,5 so sánh bộ nhớ sử dụng của hai thuật toán
CHN và CoUPM trên hai nhóm cơ sở dữ liệu dày và
thưa. Kết quả thực nghiệm cho thấy thuật toán CHN có
dung lượng bộ nhớ sử dụng thấp hơn thuật toán CoUPM
ở hầu hết các cơ sở dữ liệu thực nghiệm tại các ngưỡng
minCor cao. Khi ngưỡng minCor giảm xuống thấp hơn
thì thuật toán CHN sử dụng bộ nhớ nhiều hơn thuật toán
CoUPM ở hầu hết các cơ sở dữ liệu, ngoại trừ cơ sở dữ
liệu lớn Pumsb. Kết quả này cho thấy rằng việc sử dụng
các chiến lược tỉa và cấu trúc dữ liệu lưu trữ có ảnh
hưởng đến bộ nhớ sử dụng của thuật toán CHN. Thật
vậy, Với cấu trúc dữ liệu PNU-List sử dụng trong thuật
toán CHN, mỗi bộ của một PNU-List gồm 4 giá trị là
<Tid, Putil, Nutil, Prutil> trong khi cấu trúc dữ liệu
Utility-List trong thuật toán CoUPM thì mỗi bộ chỉ gồm
3 giá trị <Tid, Iutil, Rutil>. Ngoài ra, thuật toán CHN áp
dụng chiến lược tỉa EUCS để lưu ma trận các giá trị
RTWU của 2 phần tử dẫn đến tốn kém bộ nhớ trong quá
trình thực thi.
Với cơ sở dữ liệu Retail, biểu đồ thực nghiệm (Hình
3) cho thấy thuật toán CHN có tốc độ xử lý nhanh hơn
hơn thuật toán CoUPM khoảng 25 lần tại ngưỡng
minCor=0.3 và minUtil=5000. Tại các ngưỡng khác,
thuật toán CHN vẫn chứng tỏ được tính hiệu quả hơn
thuật toán CoUPM. Với cơ sở dữ liệu rất thưa như
Kosarak, thuật toán CHN có thời gian thực thi ổn định
trung bình khoảng 5 giây ở tất cả các ngưỡng minCor và
minUtil. Trong khi thuật toán CoUPM có thời gian thực
hiện cao hơn, trung bình khoảng 25 giây cho tất cả các
ngưỡng.
VI. KẾT LUẬN
Bài báo này đề xuất thuật toán 퐶퐻푁 khai thác tập hữu
ích cao tương quan (퐶퐻푈퐼푠) trên cơ sở dữ liệu có lợi
nhuận âm. Thuật toán sử dụng cấu trúc PNU-List biểu
diễn tách biệt các giá trị lợi nhuận âm và dương để khai
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
100
KHAI THÁ C TẬP HỮU ÍCH CAO TƯƠNG QUAN TRÊN CƠ SỞ DỮ LIỆU GIAO DỊCH CÓ LỢI NHUẬN Â M
thác đầy đủ tập 퐶퐻푈퐼푠 trên các cơ sở dữ liệu có lợi
nhuận âm. Ngoài ra, thuật toán còn áp áp dụng nhiều
chiến lược tỉa hiệu quả để cắt giảm không gian tìm kiếm
như: U-Prune, Kulc-Prune, LA-Prune và EUCS-Prune.
Kết quả thực nghiệm cho thấy thuật toán CHN có thời
gian thực hiện nhanh hơn thuật toán CoUPM trên tất cả
các cơ sở dữ liệu có lợi nhuận âm được thử nghiệm. Bộ
nhớ sử dụng của thuật toán CHN tốt hơn thuật toán
CoUPM ở các ngưỡng minCor cao, tuy nhiên, với các
ngưỡng minCor thì thuật toán CHN có dung lượng bộ
nhớ sử dụng nhiều hơn.
H. Fujita, "Extracting non-redundant correlated purchase
behaviors by utility measure," Knowledge-Based Systems,
vol. 143, pp. 30-41, 2018.
[12] W. Gan, J. C. W. Lin, H. C. Chao, H. Fujita, and S. Y.
Philip, "Correlated utility-based pattern mining,"
Information Sciences, vol. 504, pp. 470-486, 2019.
[13] A. Erwin, R. P. Gopalan, and N. R. Achuthan, "CTU-
Mine: An efficient high utility itemset mining algorithm
using the pattern growth approach," IEEE International
Conference on Computer and Information Technology, pp.
71-76, 2007.
Hướng phát triển tiếp theo là cải tiến cấu trúc dữ liệu
lưu trữ và chiến lược tỉa để tăng hiệu suất thực thi của
thuật toán trên các cơ sở dữ liệu có lợi nhuận âm, khai
thác 퐶퐻푈퐼푠 trên các dạng cơ sở dữ liệu khác như cơ sở
dữ liệu động và cơ sở dữ liệu tăng trưởng.
[14] B. Le, H. Nguyen, T. A. Cao, and B. Vo, "A novel
algorithm for mining high utility itemsets," First Asian
Conference on Intelligent Information and Database
Systems, pp. 13-17, 2009.
[15] V. S. Tseng, B. E. Shie, C. W. Wu, and S. Y. Philip,
"Efficient algorithms for mining high utility itemsets from
transactional databases," IEEE transactions on knowledge
and data engineering, vol. 25, pp. 1772-1786, 2012.
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,"
Proceedings of the 1993 ACM SIGMOD International
Conference on Management of Data, pp. 207-216, 1993.
[16] S. Krishnamoorthy, "HMiner: Efficiently mining high
utility itemsets," Expert Systems with Applications, vol. 90,
pp. 168-183, 2017.
[2] R. Agrawal and R. Srikant, "Fast algorithms for mining
association rules," In Proc. 20th Int. Conf. Very Large
Data Bases (VLDB), pp. 487-499, 1994.
[17] K. Singh, A. Kumar, S. S. Singh, H. K. Shakya, and B.
Biswas, "EHNL: An efficient algorithm for mining high
utility itemsets with negative utility value and length
constraints," Information Sciences, vol. 484, pp. 44-70,
2019.
[3] Y. Liu, W. K. Liao, and A. Choudhary, "A two-phase
algorithm for fast discovery of high utility itemsets," In
Pacific-Asia Conference on Knowledge Discovery and
Data Mining, pp. 689-695, 2005.
[18] E. R. Omiecinski, "Alternative interest measures for
mining associations in databases," IEEE Transactions on
Knowledge and Data Engineering, vol. 15, pp. 57-69,
2003.
[4] 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, pp. 253-262, 2010.
[19] P. Fournier-Viger, Y. Zhang, J. C. W. Lin, D. T. Dinh, and
H. B. Le, "Mining correlated high-utility itemsets using
various measures," Logic Journal of the IGPL, vol. 28, no.
1, pp. 19-32, 2020.
[5] 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, pp. 55-64, 2012.
[20] P. Fournier-Viger, A. Gomariz, A. Soltani, and H. Lam.
(2014) An Open-Source Data Mining Library. [Online].
[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," International Symposium
on Methodologies for Intelligent Systems, vol. 8502, pp.
83-92, 2014.
MINING CORRELATED HIGH UTILITY
ITEMSETS ON TRANSACTION DATABASE
WITH NEGATIVE PROFITS
[7] 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, no. 2, pp. 595-625, 2017.
Abstract: Correlated High Utility Itemset mining on
transaction databases have been extensively studied in
order to discover user buying behavior. As a result,
business managers can adjust sales strategies accordingly
to increase profits. The previous correlated high utility
itemset mining approaches are mostly performed on
transaction databases that have positive profit with little
regard for negative profit. In fact, businesses often reduce
profit margin of perennial inventories to stimulate
purchasers. Profit can even be reduced to negative
numbers so that all inventory can be consumed. In this
paper, we propose the CHN algorithm to mine effectively
correlated high utility itemset on the transaction database
with negative profits. The experimental results show that
the CHN algorithm has effective performance on all five
databases as Chess, Mushroom, Pumsb, Retail, and
Kosarak.
[8] J. Liu, K. Wang, and B. C. Fung, "Direct discovery of high
utility itemsets without candidate generation," IEEE 12th
international conference on data mining, pp. 984-989,
2012.
[9] J. C. W. Lin, P. Fournier-Viger, and W. Gan, "FHN: An
efficient algorithm for mining high-utility itemsets with
negative unit profits," Knowledge-Based Systems, vol. 111,
pp. 283-298, 2016.
[10] J. C. W. Lin, W. Gan, P. Fournier-Viger, T. P. Hong, and
H. C. Chao, "FDHUP: Fast algorithm for mining
discriminative high utility patterns," Knowledge and
Information Systems, vol. 51, pp. 873-909, 2017.
[11] W. Gan, J. C. W. Lin, P. Fournier-Viger, H. C. Chao, and
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
101
Nguyễn Văn Lễ, Nguyễn Thị Thanh Thủy, Mạnh Thiên Lý
Keywords: high utility itemset, correlation, data
mining, transaction database, correlated high utility
itemset.
Nguyen Văn Lễ, nhận học vị
Thạc sỹ năm 2011, chuyên ngành
Truyền dữ liệu & Mạng máy tính
tại Học viện Công nghệ Bưu chính
Viễn Thông TPHCM. Hiện công
tác tại khoa Công nghệ thông tin,
trường Đại học Công nghiệp Thực
phẩm TPHCM. Hướng nghiên
cứu: Khai thác luật kết hợp, tập
hữu ích cao trên cơ sở dữ liệu
giao dịch, phân lớp văn bản.
Nguyễn Thị Thanh Thủy, tốt
nghiệp khoa Công nghệ thông tin,
Trường Đại học Khoa học tự
nhiên - Đại học quốc gia TP.HCM
năm 2003 và nhận bằng thạc sỹ
ngành Quản trị kinh doanh,
Trường Đại học Kinh tế TP.HCM
năm 2013. Hiện tại, đang là giảng
viên khoa Công nghệ thông tin,
Trường Đại học Công nghiệp
Thực phẩm TP.HCM. Các hướng
nghiên cứu gồm: khai thác luật kết
hợp, khai thác tập hữu ích cao
trong khai phá dữ liệu.
Mạnh Thiên Lý, tốt nghiệp đại
học ngành Công nghệ Thông tin
tại Đại học Vinh năm 2006, nhận
bằng Thạc sỹ Hệ thống Thông tin
tại Học viện Kỹ thuật Quân sự Hà
Nội năm 2010. Hiện tại là giảng
viên trường Đại học Công nghiệp
Thực phẩm TP.HCM. Một số
hướng nghiên cứu chính: khai
thác luật kết hợp, khai thác tập
hữu ích cao trong khai phá dữ
liệu.
SOÁ 03 (CS.01) 2020
TAÏP CHÍ KHOA HOÏC COÂNG NGHEÄ THOÂNG TIN VAØ TRUYEÀN THOÂNG
102
9 trang
14180
Free
Bạn đang xem tài liệu "Khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch có lợi nhuận âm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- khai_thac_tap_huu_ich_cao_tuong_quan_tren_co_so_du_lieu_giao.pdf
