Thuật toán hiệu quả khai thác tập hiếm tối thiểu
Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00065
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU
Phan Thành Huấn1,2, Lê Hoài Bắc3
1Bộ môn Tin học, Trường Đại học Khoa học Xã hội và Nhân văn, Đại học Quốc gia Tp. Hồ Chí Minh
2Khoa Toán - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh
3Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh
[email protected], lhbac@fithcmus.edu.vn
TÓM TẮT: Trong khai thác dữ liệu, khai thác tập hiếm là một kỹ thuật khai thác rất quan trọng với các ứng dụng tiềm năng như
phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế. Trong bài viết này, chúng tôi
đề xuất thuật toán hiệu quả khai thác tập hiếm tối thiểu. Kết quả thực nghiệm trên bộ dữ liệu thực và giả lập, cho thấy thuật toán đề
xuất hiệu quả hơn so với thuật toán hiện hành.
Từ khóa: khai thác dữ liệu, tập hiếm, tập hiếm tối thiểu.
I. GIỚI THIỆU
Khai thác luật kết hợp là một kỹ thuật quan trọng trong lĩnh vực khai thác dữ liệu. Mục tiêu khai thác là phát
hiện những mối liên hệ giữa các giá trị dữ liệu trong dữ liệu giao dịch. Mô hình đầu tiên của bài toán khai thác luật kết
hợp là mô hình nhị phân hay còn gọi là mô hình cơ bản được Agrawal và đồng sự đề xuất vào năm 1993 [1], phân tích
dữ liệu giao dịch, phát hiện các mối liên hệ giữa các tập mục hàng hoá đã bán được tại các siêu thị. Từ đó có kế hoạch
bố trí, sắp xếp, kinh doanh hợp lý, đồng thời tổ chức sắp xếp các quầy gần nhau như thế nào để có doanh thu trong các
phiên giao dịch là lớn nhất.
Bài toán khai thác luật kết hợp là khai phá các luật kết hợp có độ phổ biến (support) cũng như độ tin cậy
(confidence) lớn hơn hoặc bằng một ngưỡng phổ biến tối thiểu (minsup) và ngưỡng tin cậy tối thiểu (minconf).
Các thuật toán được đề xuất để khai thác luật kết hợp chia thành 2 giai đoạn [1-5]:
Giai đoạn 1: Tìm tất cả các tập mục phổ biến từ dữ liệu giao dịch thoả mãn minsup;
Giai đoạn 2: Sinh các luật tin cậy kết hợp từ các tập mục phổ biến tìm thấy ở giai đoạn thứ nhất.
Giai đoạn thứ nhất chiếm hầu hết thời gian cho toàn quá trình khai thác luật kết hợp [1-5]. Giá trị ngưỡng phổ
biến tối thiểu minsup là yếu tố quan trọng trong quá trình rút gọn không gian tìm kiếm cũng như giới hạn các luật sinh
trong giai đoạn thứ hai. Các thuật toán khai thác luật kết hợp truyền thống chỉ dùng một giá trị ngưỡng phổ biến tối
thiểu minsup với ngầm định là các mặt hàng có cùng tính chất và tần số trong dữ liệu, điều này không thực tế. Trong
kinh doanh bán lẻ, thông thường các mặt hàng thiết yếu, hàng tiêu dùng và các sản phẩm giá rẻ được mua nhiều hơn,
trong khi các mặt hàng xa xỉ và các sản phẩm giá trị cao lại ít được mua (tập hiếm). Nếu chọn minsup quá cao thì các
mặt hàng được khai thác thông thường có giá thành thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Ngược
lại, nếu chọn minsup quá thấp thì các mặt hàng được khai thác quá lớn, điều này làm cho doanh nghiệp khó khăn khi ra
quyết định kinh doanh. Năm 1999, Liu và các đồng sự [6] đã mở rộng bài toán khai thác luật kết hợp với nhiều ngưỡng
phổ biến tối thiểu (mỗi mặt hàng có một ngưỡng phổ biến tối thiểu riêng) tương ứng mỗi mặt hàng khác nhau có tính
chất khác nhau và tần số giao dịch khác nhau. Nhóm tác giả này đã đề xuất thuật toán MSApriori - khai thác luật kết
hợp khác nhau thỏa ngưỡng phổ biến tối thiểu khác nhau phụ thuộc vào các mặt hàng có trong luật. Từ đó, thấy được
tầm quan trọng của tập hiếm, một số tác giả đã đề xuất thuật toán khai thác tập hiếm [7-10]:
Thuật toán Apriori-Inverse: Koh và các đồng sự [7] đề xuất hướng tiếp cận ngược theo thuật toán Apriori
trong khai thác tập hiếm tối thiểu. Thuật toán sử dụng hai ngưỡng minsup và maxsup. Thuật toán cho kết quả gồm cả
các itemset có độ phổ biến bằng 0 và itemset không có trong dữ liệu giao dịch. Ngoài ra, thuật toán này còn quét dữ
liệu nhiều lần.
Thuật toán ARIMA: Szathmary và các đồng sự [8] đề xuất hướng tiếp cận tựa thuật toán Apriori trong khai
thác tập hiếm tối thiểu. Thuật toán sử dụng cấu trúc dàn để lưu trữ dữ liệu giao dịch. Thuật toán khai thác tập hiếm tối
thiểu theo hướng tiếp cận từ dưới lên - không hiệu quả khi các mẫu hiếm tập trung ở phần đỉnh. Thuật toán cho kết quả
gồm cả các itemset có độ phổ biến bằng 0 và itemset không có trong dữ liệu giao dịch. Ngoài ra, thuật toán này còn
quét dữ liệu nhiều lần.
Thuật toán Rarity: Troiano và các đồng sự [9] đề xuất dựa trên các hạn chế của thuật toán ARIMA. Thuật
toán Rarity thực hiện chiến lược duyệt từ trên xuống trên cấu trúc dàn để khai thác các itemset hiếm tập trung ở đỉnh.
Ngoài ra, thuật toán Rarity khai thác tập hiếm tối thiểu không gồm các itemset có độ phổ biến bằng 0. Tuy nhiên, thuật
toán này sử dụng nhiều bộ nhớ so với ARIMA.
Thuật toán Walky-G: Szathmary và các đồng sự [10] đề xuất hướng tiếp cận tựa thuật toán Eclat [2] trong
khai thác tập hiếm tối thiểu. Thuật toán sử dụng cấu trúc IT-Tree để lưu trữ dữ liệu giao dịch. Thuật toán cho kết quả
498
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU
không gồm các itemset có độ phổ biến bằng 0. Thuật toán hiệu quả hơn so với ARIMA. Thuật toán sử dụng nhiều bộ
nhớ và không hiệu quả khi ngưỡng minsup nhỏ (duyệt theo chiều sâu).
Các thuật toán trên [7-10] chưa đáp ứng thực tế khi cần khai thác luật kết hợp thì người dùng có thể yêu cầu
thực hiện khai thác luật kết hợp thỏa ngưỡng minsup trong nhiều chuỗi thao tác liên tiếp khác nhau. Để đáp ứng thực
tế, nhóm tác giả đề xuất thuật toán NOV-mRI khai thác nhanh tập hiếm tối thiểu từ mảng chứa các itemset đồng xuất
hiện và không đọc lại dữ liệu cho lần khai thác tiếp theo, bao gồm các thuật toán con sau:
- Xây dựng mảng Index_LOOC chứa các item xuất hiện ít nhất trong một giao dịch của từng item hạt nhân;
- Thuật toán NOV-mRI khai thác hiệu quả tập hiếm tối thiểu dựa trên mảng Index_LOOC.
Trong phần II, bài báo trình bày các khái niệm cơ bản về khai thác tập phổ biến, tập hiếm và tập hiếm tối thiểu.
Phần III, xây dựng thuật toán xác định mảng chứa itemset đồng xuất hiện và itemset xuất hiện ít nhất trong một giao
dịch của từng item hạt nhân và thuật toán NOV-mRI khai thác tập hiếm tối thiểu. Kết quả thực nghiệm được trình bày
trong phần IV và kết luận ở phần V.
II. CÁC VẤN ĐỀ LIÊN QUAN
2.1. Khai thác tập phổ biến
Khai thác tập phổ biến truyền thống là các thuật toán [1-5] chỉ dùng duy nhất một giá trị ngưỡng phổ biến tối
thiểu minsup với ngầm định là các mặt hàng có cùng tính chất và độ phổ biến trong dữ liệu. Các hạn chế khi khai thác
tập phổ biến: giá trị minsup cao thì các tập mục hiếm bị bỏ qua hoặc khi giá trị minsup thấp thì sinh tập mục phổ biến
quá lớn. Sau đây là các khái niệm liên quan:
Cho I = {i1, i2,..., im} là tập gồm m mục hàng riêng biệt, mỗi mục hàng gọi là item. Tập các item
X
{i1,i2 ,...,ik }, (1
j
k ) gọi là itemset, tập mục có k mục hàng gọi là k-itemset. Ɗ là dữ liệu giao dịch, gồm
n bản ghi phân biệt gọi là tập các giao dịch T = {t1, t2,..., tn}, mỗi giao dịch ti {ik ,ik ,...,ik },ik (1 kj m)
.
1
2
j
j
Định nghĩa 1: Độ phổ biến (support) của itemset X I, ký hiệu sup(X), là số các giao dịch trong Ɗ có chứa X.
Định nghĩa 2: Cho X I, X gọi là itemset phổ biến nếu sup(X) ≥ minsup, trong đó minsup là ngưỡng phổ
biến tối thiểu. Ký hiệu FI là tập hợp các itemset phổ biến.
Tính chất 1: X Y: sup(Y) ≥ minsup sup(X) ≥ minsup;
Tính chất 2:
X Y: sup(X) < minsup sup(Y) < minsup;
Cho dữ liệu giao dịch Ɗ trong bảng 1.
Bảng 1. Dữ liệu giao dịch Ɗ
Mã giao dịch
Tập mục
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
A
A
C
C
E
F
F
G
E
H
A
A
C
C
D
D
G
G
E
E
E
A
A
A
A
B
B
C
C
C
C
E
E
G
G
F
Ví dụ 1: Dữ liệu giao dịch Ɗ trong bảng 1, có 8 item riêng biệt I = {A, B, C, D, E, F, G, H} và 10 giao dịch T =
{t1, t2, t3, t4, t5, t6, t7, t8, t9, t10} với giá trị ngưỡng minsup = 2, ta có:
Xét itemset X ={A, C, E}, sup(ACE) = 5 ≥ minsup, ta nói: “X ={A, C, E} phổ biến theo ngưỡng minsup = 2”;
Theo tính chất 1 thì các tập con của X ={A, C, E} cũng phổ biến, nghĩa là tất cả tập con của X đều phổ biến -
sup(A) = 8, sup(C) = 8, sup(E) = 7, sup(AC) , sup(AE) = 5, sup(CE) = 5 ≥ minsup.
Tương tự, với Y = {H} thì sup(H) = 1 < minsup, ta nói: “Y = {H} không phổ biến theo ngưỡng minsup = 2”;
Theo tính chất 2 thì các tập cha của Y ={H} cũng không phổ biến, nghĩa là Y = {EH} cũng không phổ biến, với
sup(EH) = 1 < minsup = 2.
Phan Thành Huấn, Lê Hoài Bắc
499
2.2. Khai thác tập hiếm và tập hiếm tối thiểu
Trong thực tế, nhiều ứng dụng tiềm năng cần khai thác các tập hiếm như ứng dụng phát hiện các cuộc tấn công
máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế,…. Nhiều tác giả đã đề xuất thuật toán [7-10]
khai thác tập hiếm tối thiểu thỏa một hoặc hai ngưỡng. Sau đây là các khái niệm liên quan:
Định nghĩa 3: Cho X I, X gọi là itemset hiếm - nếu sup(X) < minsup. Ký hiệu RI là tập hợp chứa các
itemset hiếm.
Định nghĩa 4: Cho X I, X gọi là itemset hiếm tối thiểu - nếu X là itemset hiếm và tất cả tập con thực sự của
X là phổ biến. Ký hiệu mRI là tập hợp chứa các itemset hiếm tối thiểu.
Tính chất 3: ik I, nếu sup(ik) < minsup thì ik mRI.
Ví dụ 2: Dữ liệu giao dịch Ɗ trong Bảng 1 với minsup = 2, ta có:
Xét itemset X ={F, G, E}, sup(FGE) = 1 < minsup, ta nói: “Itemset X ={F, G, E} là itemset hiếm”;
Xét itemset Y ={H, E}, sup(HE) = 1 < minsup, ta nói: “Itemset Y ={H, E} là itemset hiếm”;
Ngoài ra, itemset X ={F, G, E} còn là itemset hiếm tối thiểu, nghĩa là các tập con thực sự của itemset X là phổ
biến: sup(F) = 3, sup(G) = 5, sup(E) = 7, sup(FG) = 2, sup(FE) = 2, sup(GE) = 3 minsup = 2. Trong khi đó, itemset Y
= {H, E} không là itemset hiếm tối thiểu, do sup(H) = 1 < minsup.
Theo tính chất 3 thì các item có độ phổ biến nhỏ hơn minsup thì thuộc mRI, ta có: item H, sup(H) = 1 <
minsup, suy ra item H là item hiếm tối thiểu.
Bảng 2. Tập FI, RI và mRI trên dữ liệu giao dịch Ɗ với minsup =2
Tập hiếm
tối thiếu mRI
#mRI = 5
Tập phổ biến FI
Tập hiếm RI
#RI = 26
k-itemset
#FI = 39
1
2
B, D, F, G, E, A, C
BE, BA, BC, DA, DC, FA, FC, FG, FE, HE, DF, DG, BG
GA, GC, GE, EA, EC, AC
H
H
BG, DF, DG
BAC, BEA, BEC, DAC, FAC, FAG, FAE, BGE, BGC, BGA, DFG, DFC, DFA,
FGE
3
FCG, FCE, GAC, GAE, GCE, EAC
DGA, DGC, FGE
BEAC, FACG, FACE, GACE
BEFC, BGEA, BGAC, DFGC, DFGA,
DFAC, DGAC, FGEA, FGEC
BGEAC, DFGAC, FGEAC
4
5
Trong bảng 2, cho thấy tập phổ biến FI, tập hiếm RI và tập hiếm tối thiểu mRI chứa k-itemset với minsup = 2. Số
lượng tập mục phổ biến |FI| = 39, số lượng tập mục hiếm |RI| = 26 và số lượng tập mục hiếm tối phổ |mRI| = 5. Tỷ
suất mRI RI . Qua đó, ta dễ dàng thấy mối quan hệ giữa tập itemset hiếm và tập itemset hiếm
tối thiểu như sau: mRI RI.
2.3. Tổ chức lưu trữ dữ liệu giao dịch
Lưu trữ dữ liệu giao dịch dạng bit là cấu trúc dữ liệu hiệu quả trong khai thác tập phổ biến [4, 5]. Chuyển đổi dữ
liệu giao dịch thành một ma trận nhị phân BiM, trong đó mỗi dòng tương ứng với một giao dịch và mỗi cột tương ứng
với một mục hàng. Nếu mục hàng thứ ik xuất hiện trong giao dịch tj thì bit thứ k của dòng tj trong BiM sẽ mang giá trị
1, ngược lại sẽ mang giá trị 0.
Mã giao dịch
A
1
1
0
1
1
0
1
1
1
1
B
0
0
0
0
0
0
1
0
1
0
C
1
1
0
1
1
0
1
1
1
1
D
0
0
0
1
0
0
0
1
0
0
E
1
0
1
0
1
1
1
0
1
1
F
1
0
0
1
0
0
0
0
0
1
G
0
1
0
1
1
0
0
0
1
1
H
0
0
1
0
0
0
0
0
0
0
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
Hình 1. Biểu diễn dạng bit của dữ liệu giao dịch Ɗ
500
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU
III. CÁC THUẬT TOÁN
3.1. Tập chiếu và itemset đồng xuất hiện
Tập chiếu của mục hàng ik trên dữ liệu giao dịch Ɗ: (ik)={t Ɗ│ik t} là tập các giao dịch có chứa mục hàng
ik ( -đơn điệu giảm).
sup(ik) = | (ik)|
(1)
Tập chiếu của tập mục
X
{i1,i2 ,...,ik }, (1
j
k ) , (X) = (i1) (i2)…
(ik).
sup(X) = | (X)|
(2)
Ví dụ 3: Theo Bảng 1, có (A) = {1, 2, 4, 5, 7, 8, 9, 10} và (B) = {7, 9}. Khi đó, (AB) = (A) (B)=
{1, 2, 4, 5, 7, 8, 9, 10} {7, 9} = {7, 9}, (B) (A) và (AB) (A).
Định nghĩa 5: Cho ik I, ta gọi ik là item hạt nhân. Tập Xcooc I gọi đồng xuất hiện với ik: Xcooc là tập các item
xuất hiện cùng ik thì (ik) (ik xcooc), xcooc Ƥ (Xcooc). Ký hiệu, cooc(ik) = Xcooc
.
1
Ví dụ 4: Xem item B là item hạt nhân, ta xác định được itemset đồng xuất hiện cùng độ phổ biến với item B là
cooc(B) = {A, C, E} và sup(B) = sup(BACE) = 2.
Định nghĩa 6: Cho ik I, ta gọi ik là item hạt nhân. Tập Ylooc I chứa các item xuất hiện cùng với ik ít nhất
trong một giao dịch, nhưng không đồng xuất hiện: 1 | (ik ylooc)|<| (ik)|, ylooc Ƥ (Ylooc). Ký hiệu, looc(ik) = Ylooc
.
1
Ví dụ 5: Xem item G là item hạt nhân, ta xác định được các item xuất hiện cùng với item G ít nhất trong một
giao dịch là looc(G) = {B, D, E, F} có (G) = {2, 4, 5, 9, 10} và (GB) = {9}, (GE) = {5, 9, 10}.
3.2. Thuật toán sinh itemset đồng xuất hiện có thứ tự
Trong phần này, chúng tôi trình bày thuật toán sinh các item đồng xuất hiện và item xuất hiện ít nhất trong một
giao dịch với item hạt nhân, được lưu trữ vào mảng Index_COOC. Mỗi phần tử trong Index_COOC gồm có 4 thành
phần thông tin sau:
- Index_COOC[k].item: item hạt nhân thứ k;
- Index_COOC[k].sup: độ phổ biến của item hạt nhân thứ k;
- Index_COOC[k].cooc: các item đồng xuất hiện cùng item hạt nhân thứ k dạng bit;
- Index_COOC[k].looc: các item xuất hiện cùng item hạt nhân thứ k ít nhất trong một giao dịch dạng bit;
Mã giả thuật toán 1. Xây dựng bảng Index_COOC
Đầu vào: Dữ liệu giao dịch Ɗ
Đầu ra: Mảng Index_COOC, ma trận BiM
1: Với mỗi phần tử k của mảng Index_COOC thực hiện:
2:
3:
4:
5:
Index_COOC[k].item = ik
Index_COOC[k].sup = 0
Index_COOC[k].cooc= 2m - 1
Index_COOC[k].looc= 0
6: Với mỗi giao dịch ti thực hiện:
7:
Lưu giao dịch ti vào ma trận BiM
8:
Với mỗi item k có trong giao dịch ti thực hiện:
9:
Index_COOC[k].cooc = Index_COOC[k].cooc AND vectorbit(ti)
Index_COOC[k].looc = Index_COOC[k].looc OR vectorbit(ti)
Index_COOC[k].sup = Index_COOC[k].sup + 1
10:
11:
12: Sắp xếp mảng Index_COOC tăng dần theo sup
13: Trả về mảng Index_COOC, ma trận BiM
Từ dòng 1 đến dòng 5 là các bước khởi tạo cho mảng Index_COOC. Dòng 6 duyệt dữ liệu giao dịch, ứng với
từng giao dịch ta xem xét có chứa item thứ k thì thực hiện phép toán AND trên bit để xác định các item đồng xuất hiện
với item k (dòng 9) và thực hiện pháp toán OR trên bit để xác định các item xuất hiện với item k ít nhất trong một giao
dịch, nhưng không là đồng xuất hiện (dòng 10).
Phan Thành Huấn, Lê Hoài Bắc
501
Khởi tạo mảng Index_COOC: (thành phần cooc và looc biểu diễn dạng bit) số item là m = 8
Item
Sup
A
B
C
D
E
F
G
H
0
0
0
0
0
0
0
0
Cooc
Looc
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
Đọc giao dịch t1: {A, C, E, F} có biểu diễn dạng bit là 10101100
Item
Sup
A
B
C
D
E
F
G
H
1
0
1
0
1
1
0
0
Cooc
Looc
10101100 11111111 10101100 11111111 10101100 10101100 11111111 11111111
10101100 00000000 10101100 00000000 10101100 10101100 00000000 00000000
Duyệt lần lượt đến giao dịch t10: {A, C, E, F, G} có biểu diễn dạng bit là 10101110
Item
Sup
A
B
C
D
E
F
G
H
8
2
8
2
7
3
5
1
Cooc
Looc
10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001
11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001
Thuật toán 1, trả về mảng Index_COOC sắp tăng theo độ phổ biến của item theo Bảng 3.
Bảng 3. Trả về mảng Index_COOC sắp tăng theo độ phổ biến của item
Item
Sup
Cooc
Looc
H
1
B
D
2
F
3
A, C
G
5
E
7
A
8
C
8
2
A, C, E
G
E
Ø
A, C
F, G
A, C
Ø
C
A
D, E, G B, D, E, F
A, B, C, F, G, H B, D, E, F, G
B, D, E, F, G
Để tránh trùng lặp không gian sinh tập hiếm tối thiểu, chúng tôi đưa ra các định nghĩa và bổ đề rút gọn không
gian sinh tập hiếm tối thiểu như sau:
Định nghĩa 7: Cho ik I (i1
i2
…
im) thứ tự theo độ phổ biến, ta gọi ik là item hạt nhân. Tập Xlexcooc
I
gọi đồng xuất hiện có thứ tự với item ik: Xlexcooc là tập các item có thứ tự theo độ phổ biến, đồng xuất hiện cùng ik và
(ik) (ik xlexcooc), xlexcooc Ƥ (Xlexcooc), ij Xlexcooc, ik ij. Ký hiệu, lexcooc(ik) = Xlexcooc
.
1
Định nghĩa 8: Cho ik I (i1
i2
…
im) thứ tự theo độ phổ biến, ta gọi ik là item hạt nhân. Tập Ylexlooc
chứa các item xuất hiện có thứ tự cùng với ik ít nhất trong một giao dịch, nhưng không đồng xuất hiện:
1 | (ik ylexlooc)|<| (ik)|, ylexlooc Ƥ (Ylexlooc), ij Ylexlooc, ik ij. Ký hiệu, lexlooc(ik) = Ylexlooc
I
.
1
Bổ đề 1: lexcooc(ik) = Xlexcooc thì sup(ik xsub) = sup(ik), xsub Ƥ (Xlexcooc).
1
Chứng minh: lexcooc(ik) = Xlexcooc
,
xsub Ƥ (Xlexcooc). Theo định nghĩa 7, ta có (ik xsub) = (ik)
(xsub) =
1
(ik) và theo phương trình (1), (2) thì sup(ik xsub) = sup(ik), xsub Ƥ (Xlexcooc) ■.
1
Ví dụ 6: Xét item F, với sup(F) = 3. Ta có, lexcooc(F) = {A, C} thì 3 itemset kết hợp {A, C, AC} và sup(F) =
sup(FA) = sup(FC) = sup(FAC) = 3.
Bổ đề 2: nếu lexcooc(ik) = Xlexcooc và sup(ik) < minsup thì {ik xsub} RI, xsub Ƥ (Xlexcooc).
1
Chứng minh: theo bổ đề 1, ta có sup(ik xsub) = sup(ik) < minsup, nên {ik xsub} RI, xsub Ƥ (Xlexcooc) ■.
1
Ví dụ 7: Cho minsup = 5, xét item F, có sup(F)= 3< minsup. Theo ví dụ 6, ta có sup(F) = sup(FA) = sup(FC) =
sup(FAC) = 3 < minsup. Khi đó, các itemset {F, FA, FC, FAC} RI.
Bổ đề 3: nếu lexcooc(ik) = Xlexcooc và sup(ik) < minsup thì {ik xsub} mRI, xsub Ƥ (Xlexcooc).
1
Chứng minh: theo mệnh đề 1, ta có {ik xsub} RI, xsub Ƥ (Xlexcooc). Khi đó, ik { ik xsub} RI, mà
1
sup(ik) < minsup (định nghĩa 4), nên {ik xsub} mRI, xsub Ƥ (Xlexcooc) ■.
1
Ví dụ 8: Cho minsup = 5, xét item F, có sup(F)= 3< minsup. Theo ví dụ 6, ta có sup(F) = sup(FA) = sup(FC) =
sup(FAC) = 3 < minsup. Khi đó, các itemset {F, FA, FC, FAC} RI, nhưng các itemset {F, FA, FC, FAC} không là
các itemset hiếm tối thiểu - {FAC} RI, item F {FAC} và sup(F) = 3 < minsup (item F không phổ biến).
Bổ đề 4: ik
ij, nếu ij lexlooc(ik) thì sup(ik ij) < sup(ik).
Chứng minh: sup(ik ij) < sup(ik), hiển nhiên (ik ij) = (ik)
(ij)
(ik) ■.
Ví dụ 9: Xét item F, với sup(F) = 3. Ta có, lexlooc(F) = {G, E} thì 3 itemset kết hợp {G, E, GE} và sup(F) =
sup(FG) = sup(FE) = 2 < sup(F) và sup(FGE) = 1 < sup(F).
502
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU
Bổ đề 5: ik I, sup(ik) minsup, nếu lexlooc(ik) = Ylexlooc và sup(ik ysub) < minsup thì {ik ysub}, {ik xsub
} RI, xsub Ƥ (Xlexcooc), ysub Ƥ (Ylexlooc).
ysub
1
1
Chứng minh: theo bổ đề 1, 4, ta có sup(ik xsub) = sup(ik) và sup(ik ysub) = sup(ik xsub ysub) < minsup, nên {ik
xsub}, {ik xsub ysub RI, xsub Ƥ (Xlexcooc), ysub Ƥ (Ylexlooc) ■.
}
1
1
Ví dụ 10: Cho minsup = 5, xét item G, có sup(G)= 5 minsup. Ta có lexcooc(G) = {A, C}, lexlooc(G) = {E},
sup(GE) = sup(GAE) = sup(GCE) = sup(GACE) = 3 < minsup. Khi đó, các itemset {GE, GAE, GCE, GACE} RI.
Bổ đề 6: ik I, sup(ik) minsup, nếu lexlooc(ik) = Ylexlooc và sup(ik ysub) < minsup thì {ik xsub ysub
mRI, xsub Ƥ (Xlexcooc), ysub Ƥ (Ylexlooc).
}
1
1
Chứng minh: theo bổ đề 5, ta có {ik xsub}, {ik xsub ysub
xsub ysub mRI, xsub Ƥ (Xlexcooc), ysub Ƥ (Ylexlooc) ■.
}
RI, mà {ik xsub} {ik xsub ysub } nên {ik
}
1
1
Ví dụ 11: Cho minsup = 5, xét item G, có sup(G)= 5 minsup. Ta có lexcooc(G) = {A, C}, lexlooc(G) = {E},
sup(GE) = sup(GAE) = sup(GCE) = sup(GACE) = 3 < minsup. Theo định nghĩa thì các itemset {GAE, GCE, GACE}
mRI, do {G, E} là tập con thực sự của lần lượt {G, A, E}, {G, C, E}, {G, A, C, E} mà sup(GE) < minsup.
Theo các bổ đề trên, cần thiết phải rút gọn trường cooc trên mỗi phần tử của mảng INDEX_COOC. Chúng tôi,
đặt lại tên gọi của mảng INDEX_COOC thành INDEX_LOOC, chứa các item xuất hiện ít nhất trong một giao dịch
với item hạt nhân.
Bỏ dòng lệnh 4 và 9, đồng thời bổ sung 2 dòng lệnh sau vào thuật toán 1:
1: Với mỗi phần tử k của mảng Index_LOOC:
2:
Index_LOOC[k].looc= lexlooc(ik)
Xét item G, có các item xuất hiện ít nhất trong một giao dịch với item G, ta có looc(G) = {B, D, E, F} và B,
D
F
G E, nên lexlooc(G) = {E}.
Sau khi thực hiện thay đổi trên, ta có kết quả trong bảng 4.
Bảng 4. Trả về mảng Index_LOOC sắp tăng theo độ phổ biến của item, thành phần looc có thứ tự
Item
Sup
H
1
B
2
D
2
F
3
G
5
E
7
A
8
C
8
Looc
Ø
G
F, G
G, E
E
A, C
Ø
Ø
3.3. Thuật toán khai thác tập hiếm tối thiểu NOV-mRI
Thuật toán 2 - Từ mảng Index_LOOC xây dựng danh sách cây chứa các mẫu xuất hiện ít nhất trong một giao
dịch với item hạt nhân. Mỗi cây có nút gốc là item hạt nhân và các nút con là các item xuất hiện ít nhất trong một giao
dịch với item hạt nhân (có thứ tự theo độ phổ biến). Mỗi nút gồm 2 thành phần:
- nLOOC_Tree[k].item: item xuất hiện ít nhất với item hạt nhân (nút gốc);
- nLOOC_Tree[k].sup: độ phổ biến của item xuất hiện cùng với item hạt nhân;
Mã giả thuật toán 2. Xây dựng danh sách cây nLOOC-Tree
Đầu vào: Ma trận BiM, Mảng Index_LOOC
Đầu ra: Danh sách cây nLOOC-Tree
1: Với mỗi phần tử k của mảng Index_LOOC:
2:
3:
4:
5:
6:
7:
8:
9:
10:
nLOOC_Tree[k].item = Index_LOOC[k].item
nLOOC_Tree[k].sup = Index_LOOC[k].sup
Với mỗi item ik giao dịch tℓ :
Với mỗi item ij Index_LOOC[k].looc:
Nếu ij nút con của nút gốc nLOOC-Tree[k] thì
Thêm nút con ij vào nút gốc nLOOC-Tree[k]
Ngược lại
Thêm nút con ij vào nút gốc nLOOC-Tree[k]
Cập nhật sup của nút con ij của nút gốc nLOOC-Tree[k]
11: Trả về danh sách cây nLOOC-Tree
Phan Thành Huấn, Lê Hoài Bắc
503
Thuật toán 2 sinh cây nLOOC-Tree có các đặc trưng như sau:
- Chiều cao của cây nhỏ hơn hoặc bằng số lượng các item xuất hiện ít nhất trong một giao dịch với item hạt
nhân (các item có thứ tự theo độ phổ biến).
- Mỗi đường đi đơn (single-path) là một mẫu có thứ tự từ nút gốc (item hạt nhân) đến nút lá và độ phổ biến của
một mẫu là độ phổ biến của nút lá (ik ik+1
… iℓ).
- Mỗi phân đoạn đường đi đơn (sub-single-path) từ nút gốc đến nút con bất kỳ trong đường đi đơn là một mẫu
thứ tự và độ phổ biến của mẫu là độ phổ biến của nút con ở cuối của phân đoạn đường đi đơn.
Hình 2. Thuật toán 2 - sinh danh sách cây nLOOC-Tree theo mảng Index_LOOC ở bảng 4
Ví dụ 12: Xét item hạt nhân F, có đường đi đơn {F
G} và sup(FG) = 2 là độ phổ biến của nút con G.
G
E} và sup(FGE) = 1; phân đoạn đường đi đơn {F
Mã giả thuật toán 3. Khai thác tập hiếm tối thiểu NOV-mRI
Đầu vào: Mảng Dataset, Index_LOOC và minsup
Đầu ra: Tập hiếm tối thiểu mRI
1: Với mỗi Index_LOOC[k].sup < minsup
2:
3:
4:
5:
6:
7:
8:
mRI[k] = mRI[k] Index_LOOC[k].item//theo tính chất 3
Với mỗi (Index_LOOC[k].sup minsup) và (Index_LOOC[k].looc { }) // Bổ đề 6
nLOOC_Tree(Index_LOOC[k].item)
SSP GenPath(Index_LOOC[k].item)//sinh sub-single-path
Với mỗi sspj SSP
Nếu (sup(sspj) < minsup) và (sup(sspj \{iℓ}) minsup) thì
mRI[k] = mRI[k] {(sspj \{iℓ})}
9: Trả về tập hiếm tối thiểu mRI
Ví dụ 13: Cho dữ liệu giao dịch Ɗ trong bảng 1 và minsup = 2. Sau khi thực hiện thuật toán 1, ta có mảng
INDEX_LOOC chứa các item xuất hiện ít nhất trong một giao dịch với item hạt nhân, như trong bảng 4.
Dòng 1 và 2: các item hiếm tối thiểu theo tính chất 3 - có item H (sup(H) = 1 < minsup);
Dòng 3: loại bỏ item A và C khỏi danh sách các item khai phá; (Bổ đề 6)
Xây dựng các cây nLOOC-Tree cho các item cần khai phá: B, D, F và G ;
Xét item B, xem cây nLOOC-Tree(B): có một đường đi đơn {B G} và sup(BG) = 1 < minsup. Ta có, mRI[B]
= {(BG, 1)}.
Xét item D, xem cây nLOOC-Tree(D): có một đường đi đơn {D
mRI[D] = {(DF, 1), (DG, 1)}.
F
G} và sup(DFG) = 1 < minsup. Ta có,
Xét item F, xem cây nLOOC-Tree(F): có 2 đường đi đơn {F
G
E}, {F E} và 1 phân đoạn đường đi
đơn {F
G} lần lượt có sup(FGE) = 1 < minsup, sup(FG) = 2 minsup và sup(FE) = 2 minsup. Ta có, mRI[F] =
{(FGE, 1)}.
Xét item G, xem cây nLOOC-Tree(G): có một đường đi đơn {G
mRI[G] = { }.
E} và sup(GE) = 3 minsup. Ta có,
Xét item E, có đường đi đơn {E
A
C} và sup(EAC) = 5 minsup. Ta có, mRI[E] = { }.
504
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU
Tập hiếm tối thiểu mRI trên dữ liệu giao dịch Ɗ ở bảng 1 với minsup = 2:
Item hạt nhân
Tập hiếm tối thiểu mRI
H
B
D
F
(H, 1)
(BG, 1)
(DF, 1)
(FGE, 1)
(DG, 1)
IV. KẾT QUẢ THỰC NGHIỆM
Thực nghiệm trên máy tính CF-74, Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên C#, Microsoft Visual
Studio 2010.
Nghiên cứu thực nghiệm trên hai nhóm dữ liệu:
Nhóm dữ liệu thực có mật độ dày: sử dụng dữ liệu thực từ kho dữ liệu về học máy của Trường Đại học
University of California, School of Information and Computer Science) gồm 2 tập Chess và Mushroom.
Nhóm dữ liệu giả lập có mật độ thưa: sử dụng phần mềm phát sinh dữ liệu giả lập của trung tâm nghiên cứu
IBM Almaden (IBM Almaden Research Center, San Joe, California 95120, U.S.A [http://www.almaden.ibm.com])
gồm 2 tập T10I4D100K và T40I10D100K.
Bảng 5. Dữ liệu thực nghiệm
Số
giao dịch
3.196
8.142
100.000
100.000
Số mục nhỏ nhất/ Số mục lớn nhất/ Số mục trung bình/ Mật độ
Tên dữ liệu
Chess
Mushroom
T10I4D100K
T40I10D100K
Số mục
75
giao dịch
giao dịch
giao dịch
(%)
37
23
1
37
23
29
77
37 49,3 %
23 19,3 %
119
870
942
10
40
1,1 %
4,2 %
4
Trong phần thực nghiệm, chúng tôi sử dụng 4 tập dữ liệu được mô tả ở bảng 5 và so sánh thuật toán đề xuất
NOV-mRI với thuật toán AprioriRare [8] (loại bỏ các itemset có độ phổ biến bằng 0) và thuật toán Walky-G [10].
Để so sánh thời gian thực hiện giữa thuật toán đề xuất với thuật toán AprioriRare và Walky-G, chúng tôi chỉ tiến
hành so sánh theo từng ngưỡng minsup và cả 3 thuật toán đều cho cùng kết quả số lượng itemsets hiếm.
(a) Chess
(b) Mushroom
250000
200000
150000
100000
50000
0
500
400
300
200
100
0
AprioriRare
Walky-G
AprioriRare
Walky-G
NOV-mRI
NOV-mRI
11
12
13
14
15
0,1
0,2
0,3
0,4
0,5
Minsup (%)
Minsup (%)
Hình 3. Thời gian thực hiện NOV-mRI, Walky-G và AprioriRare trên dữ liệu Chess, Mushroom
Hình 3a và 3b là kết quả thực nghiệm trên nhóm dữ liệu có mật độ cao, ta thấy thuật toán NOV-mRI nhanh hơn
thuật toán Walky-G và AprioriRare.
(a) T10I4D100K
(b) T40I10D100K
1000000
100000
10000
1000
100
1000000
100000
10000
1000
100
AprioriRare
Walky-G
AprioriRare
Walky-G
NOV-mRI
NOV-mRI
10
10
1
1
0,010
0,015
0,020
0,025
0,030
0,075
0,080
0,085
0,090
0,095
Minsup (%)
Minsup (%)
Hình 4. Thời gian thực hiện NOV-mRI, Walky-G và AprioriRare trên dữ liệu T10I4D100K, T40I10D100K
Phan Thành Huấn, Lê Hoài Bắc
505
Hình 4a và 4b là kết quả thực nghiệm trên nhóm dữ liệu giả lập có mật độ thấp, ta thấy thuật toán NOV-mRI
nhanh hơn thuật toán Walky-G và AprioriRare. Hiệu suất của thuật toán NOV-mRI rất cao so với Walky-G và
AprioriRare trên dữ liệu thưa.
Kết quả trên cho thấy thuật toán khai thác tập hiếm tối thiểu NOV-mRI tốt hơn thuật toán Walky-G và
AprioriRare. Ngoài ra, thuật toán cũng cần thực nghiệm thêm trên nhiều tập dữ liệu có mật độ khác nhau, cũng như
trên nhiều dữ liệu cỡ lớn.
V. KẾT LUẬN
Nhóm tác giả đã đề xuất kiến trúc khai thác tập hiếm tối thiểu với một ngưỡng phổ biến tối thiểu gồm hai giai
đoạn: giai đoạn thứ nhất là tính nhanh mảng Index_LOOC chứa các item xuất hiện với item hạt nhân ít nhất trong một
giao dịch; giai đoạn thứ hai: đề xuất thuật toán NOV-mRI khai thác hiệu quả tập hiếm tối thiểu dựa trên mảng
Index_LOOC. Với kiến trúc như trên, khi người dùng khai thác tập hiếm tối thiểu với ngưỡng khác thì thuật toán đề
xuất chỉ thực hiện khai thác tập hiếm tối thiều trên mảng Index_LOOC đã tính ở lần khai thác trước làm giảm thời
gian xử lý đáng kể.
Tương lai, nhóm tác giả mở rộng thuật toán để có thể khai thác tập hiếm tối thiểu trên dữ liệu giao dịch có trọng
số của item, đây là hướng nghiên cứu đang được quan tâm vì khả năng ứng dụng vào nhiều lĩnh vực, đặc biệt là trong
kinh doanh, y khoa.
VI. LỜI CẢM ƠN
Nhóm tác giả cảm ơn sự hỗ trợ từ Trường Đại học Khoa học Xã hội và Nhân văn; Đại học Khoa học Tự nhiên
Đại học Quốc gia Tp.HCM.
VII.TÀI LIỆU THAM KHẢO
[1] R. Agrawal, T. Imilienski, A. Swami. “Mining association rules between sets of large databases”. Proc. of the
ACM SIGMOD International Conference on Management of Data, Washington, DC, pp.207-216, 1993.
[2] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li. “New Algorithms for Fast Discovery of Association Rules”. In:
Proc. of the 3rd International Conference on Knowledge Discovery in Databases, pp.283-286, 1997.
[3] J. Han, J. Pei, Y. Yin, R. Mao. “Mining frequent patterns without candidate generation: A frequent pattern tree
approach”. Data Mining and Knowledge Discovery, 8(1) pp.53-87, 2004.
[4] J. Dong, M. Han. “BitTableFI: An efficient mining frequent itemsets algorithm”. Knowledge-Based Systems
20(4), pp.329-335, 2007.
[5] W. Song, B. Yang. “Index-BitTableFI: An improved algorithm for mining frequent itemsets”. Knowledge-Based
Systems 21, pp.507-513, 2008.
[6] B. Liu, W. Hsu, Y. Ma. “Mining association rules with multiple minimum supports”. Proc. of the 15th ACM
SIGKDD International Conference on Knowledge discovery and Data mining, pp.337-341, 1999.
[7] Y. S. Koh, N. Rountree. “Finding sporadic rules using apriori-inverse”. In PAKDD’05, 3518, Springer, pp.97-106,
2005.
[8] L. Szathmary, A. Napoli, P. Valtchev. “Towards rare itemset mining”. Proc. of the 19th IEEE Int. Conf. on Tools
with Artificial Intelligence. Washington, DC, USA: IEEE Computer Society, pp.305-312, 2007.
[9] L. Troiano, C. Birtolo. “A fast algorithm for mining rare itemsets”. IEEE 19th International Conference on
Intelligent Systems Design and Applications, pp.1149-1155, 2009.
[10]L. Szathmary, P. Valtchev, A. Napoli, R. Godin. “Efficient vertical mining of minimal rare itemsets”. Proc. of the
19th International Conference on Concept Lattices and Their Applications, pp.269-280, 2012.
AN EFFICIENT MINING ALGORITHM FOR MINIMAL RARE ITEMSETS
IN TRANSACTINAL DATABASES
Phan Thanh Huan, Le Hoai Bac
ABSTRACT: In the field of data mining, rare itemsets mining is an important task for potential applications such as the detection of
computer attacks, fraudulent transactions in financial institutions, bioinformatics and medical. In this paper, we propose an efficient
mining algorithm for minimal rare itemsets. Finally, we present result experiments on both synthetic and real-life datasets, which
shows the proposed algorithm has better than the existing algorithms.
Keywords: Data mining, rare itemsets, minimal rare itemsets.
9 trang
17280
Free
Bạn đang xem tài liệu "Thuật toán hiệu quả khai thác tập hiếm tối thiểu", để 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:
- thuat_toan_hieu_qua_khai_thac_tap_hiem_toi_thieu.pdf
