- Trang Chủ
- Cơ sở dữ liệu
- Thuật toán hiệu quả khai thác tập tương quan hiếm có trọng số kết hợp độ đo ALL-CONFIDENCE
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.00058
THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP TƯƠNG QUAN HIẾM
CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE
Phan Thành Huấn1,2, Lê Hoài Bắc3
1
Khoa 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
2
Bộ 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
3
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. Hồ Chí Minh
huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn
TÓM TẮT: Khai thác tập hiếm là một kỹ thuật khai thác rất quan trọng cù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 khai thác dữ liệu truyền thống trên dữ
liệu giao dịch thì các item không có trọng số (như nhau). Tuy nhiên, trong một số ứng dụng thực tế thì mỗi item có trọng số khác
nhau (thể hiện mức độ quan trọng hay ý nghĩa của từng item) - cần khai thác các tập phổ biến/ hiếm có trọng số của item. Trong bài
viết này, chúng tôi đề xuất một cách tiếp cận khai thác tập tương quan hiếm có trọng số theo hướng tiếp cận không thỏa tính chất
bao đóng giảm và đồng thời thỏa ràng buộc phản đơn điệu của độ đo tương quan all-confidence. Thuật toán chúng tôi đề xuất được
gọi là ALLCONF-CORSI. Chúng tôi tiến hành thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và bộ dữ liệu giả lập của trung
tâm nghiên cứu IBM Almaden, cho thấy thuật toán đề xuất hiệu quả.
Từ khóa: độ đo all-confidence, tập tương quan hiếm có trọng số, thuật toán ALLCONF-CORSI.
I. GIỚI THIỆU
Thuật toán khai thác luật kết hợp truyền thống [1-3] 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 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.
Từ đó, có nhiều thuật toán khai thác tập hiếm đƣợc đề xuất nhƣ Apriori-Inverse, Rarity, Walky-G. Các thuật toán
này dựa trên Apriori [8-9], Eclat [10] và có nhiều hạn chế nhƣ quét dữ liệu nhiều lần, sử dụng nhiều bộ nhớ, các chiến
lƣợc cắt tỉa (không tái sử dụng cho lần khai thác tiếp theo).
Những năm cuối của thế kỷ 20, C.H.Cai và đồng sự [5] đã đề xuất mô hình khai thác tập phổ biến có trọng số
của mục hàng (mức độ quan trọng hay mức ý nghĩa của các mục hàng là khác nhau) chứa nhiều tri thức hơn so với
khai thác tập phổ biến truyền thống (không trọng số). Sau đó, có nhiều tác giả nghiên cứu và đề xuất thuật toán [5-6]
giải quyết vấn đề này. Tuy nhiên, các thuật toán đều tiếp cận và giải quyết theo hƣớng thỏa tính chất bao đóng giảm.
Năm 2003, F.Tao có bàn luận đến hƣớng giải quyết bài toán trên theo cách tiếp cận “không thỏa tính chất bao đóng
giảm”, điều này làm gia tăng đáng kể không gian tìm kiếm. Nhƣng ở công trình [6] F.Tao và đồng sự vẫn giải quyết
bài toán theo hƣớng thỏa tính chất bao đóng giảm và thuật toán tựa Apriori. Trong những năm gần đây, S. Kamepalli
cùng đồng sự đề xuất thuật toán IWI [7] sử dụng cấu trúc FP-Tree và khai thác tập hiếm có trọng số theo hƣớng tiếp
cận không thỏa tính chất bao đóng giảm.
Trong những năm gần đây, để đáp ứng nhu cầu ứng dụng khai thác dữ liệu trong các bài toán 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ế,… S. Bouasker
và đồng sự [10] đã đề xuất thuật toán CORI khai thác tập hiếm không trọng số và kết hợp độ đo tƣơng quan bond [4]
(tương quan giữa độ phổ biến và độ phủ của tập mục hàng trong các giao dịch). Thuật toán sử dụng cấu trúc IT-Tree
khai thác tập hiếm và từ tập hiếm này xác định tập tƣơng quan hiếm. Tuy nhiên, thuật toán CORI khai thác tập tƣơng
quan hiếm trên dữ liệu không có trọng số. Từ những khảo sát trên, chúng tôi đề xuất thuật toán giải quyết bài toán khai
thác tập tƣơng quan hiếm có trọng số “không thỏa tính chất bao đóng giảm”, đây là thách thức lớn. Trong bài toán
này, chúng tôi giải quyết kết hợp khai thác tập hiếm có trọng số và độ đo tƣơng quan all_confidence [4] (tương quan
giữa độ phổ biến tập mục hàng và độ phổ biến tối đại của mục hàng trong tập). Dựa vào tập tương quan hiếm có trọng
số đã tìm đƣợc, chúng tôi khai thác luật kết hợp hiếm và tất cả luật kết hợp hiếm đều có độ tin cậy nhỏ hơn ngƣỡng
minallconf cho trƣớc. Thuật toán đề xuất bao gồm các thuật toán con nhƣ sau:
- Xây dựng mảng Index_COOC chứa các items đồng xuất hiện và 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;
- Xây dựng cây nLOOC-Tree chứa các mẫu xuất hiện ít nhất trong một giao dịch của item hạt nhân;
- Thuật toán ALLCONF-CORSI khai thác hiệu quả tập tƣơng quan hiếm có trọng số kết hợp độ đo tƣơng
quan All-Confidence dựa trên mảng Index_LOOC và cây nLOOC-Tree.
- Phan Thành Huấn, Lê Hoài Bắc 451
Trong phần 2, 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 không trọng số và có
trọng số. Phần 3, 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, danh sách cây nLOOC-Tree và thuật toán ALLCONF-CORSI khai thác tập tƣơng
quan hiếm có trọng số. Kết quả thực nghiệm đƣợc trình bày trong phần 4 và kết luận ở phần 5.
II. CÁC VẤN ĐỀ LIÊN QUAN
A. Khai thác tập phổ biến và tập hiếm không trọng số
Cho I = {i1, i2,..., im} là tập gồm m mục hàng, mỗi mục hàng gọi là item. Tập các item X ={i1, i2,..., ik}, ij I
(1 j k) gọi là itemset, itemset có k item 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 tk ={ik1, ik2,..., ikm}, ikj I (1 kj m).
Định nghĩa 1: Độ phổ biến (support) của itemset X I, ký hiệu sup(X) - tỷ lệ giữa số giao dịch trong Ɗ có
chứa X và n giao dịch.
Đị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.
Đị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.
Tính chất 1: X Y, sup(Y) ≥ minsup: sup(X) ≥ minsup;
Tính chất 2: ik I, sup(ik) < minsup: ik RI;
Tính chất 3: X Y, sup(X) < minsup: sup(Y) < minsup và X, Y RI.
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 A C E F
t2 A C G
t3 E H
t4 A C D F G
t5 A C E G
t6 E
t7 A B C E
t8 A C D
t9 A B C E G
t10 A C E F G
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 = 0,20, ta có:
Xét itemset X ={A, C, E}, sup({A,C,E}) = 0,50 ≥ minsup, ta nói: ”X ={A, C, E} phổ biến với minsup = 0,20”;
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}) = 0,80; sup({C}) = 0,80; sup({E}) = 0,70; sup({A, C}); sup({A, E}) = 0,50; sup({C, E}) = 0,50 ≥ minsup.
Theo tính chất 2, Y = {H} thì sup({H}) = 0,10 < minsup, ta nói: ”Y = {H} itemset hiếm ngƣỡng minsup = 0,20”;
Theo tính chất 3 thì các tập cha của Y ={H} cũng là itemset hiếm, nghĩa là Y = {E, H} cũng itemset hiếm, với
sup({E, H}) = 0,10 < minsup = 0,20.
B. Khai thác tập phổ biến và tập hiếm có trọng số
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 thỏa một hoặc hai ngƣỡng hoặc tập tƣơng quan hiếm [11]. 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, mỗi mục hàng gọi là item. Tập SIG = {sigi1, sigi2,..., sigim}, sigik
[0, 1] là tập các mức ý nghĩa hay mức độ quan trọng của từng item (trọng số của từng mục hàng). Tập các item X
={i1, i2,..., ik}, ij I (1 j k)gọi là itemset, itemset có k item 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 tk ={ik1, ik2,..., ikm}, ikj I (1 kj m).
Định nghĩa 4: Cho X I, mức ý nghĩa của itemset X đƣợc tính sig(X)=max(sigi1, sigi2,..., sigik), ij X (1 j k).
Định nghĩa 5: Cho X I, X gọi là itemset phổ biến nếu sigsup(X) ≥ minsigsup, trong đó minsigsup là ngƣỡng
mức ý nghĩa phổ biến tối thiểu (do người dùng chỉ định). Tập hợp chứa các itemset phổ biến có trọng số gọi là tập phổ
biến có trọng số, ký hiệu là FSI.
- 452 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE
Mức ý nghĩa phổ biến của itemset X:
sigsup(X) = sig(X) sup(X) (1)
Định nghĩa 6: Cho X I, X đƣợc gọi là itemset hiếm có trọng số, nếu sigsup(X) < minsigsup. Tập hợp chứa
các itemset hiếm có trọng số gọi là tập hiếm có trọng số, ký hiệu là RSI.
Tính chất 4: (mở rộng tính chất 2) ik I, sigsup(ik) < minsigsup: ik RSI.
Định nghĩa 7: Cho X I. Độ đo all_confidence của itemset X đƣợc tính:
sup( X )
all _ conf ( X ) (2)
max(sup( i j )| i j X)
Độ đo all_confidence thỏa tính chất bao đóng giảm: nếu X’ X thì all_conf(X’) ≥ all_conf(X).
Ta có thể nói: tất cả các luật kết hợp sinh từ itemset X thì đều có độ tin cậy conf lớn hơn hoặc bằng ngƣỡng
all_conf tối thiểu min_allconf.
Định nghĩa 8: Cho X RSI, X đƣợc gọi là itemset tƣơng quan hiếm có trọng số, nếu all_conf(X)
min_allconf, trong đó min_allconf là ngƣỡng độ tin cậy tối thiểu (do người dùng chỉ định). Tập hợp chứa các itemset
tƣơng quan hiếm có trọng số gọi là tập tương quan hiếm có trọng số, ký hiệu là CORSI.
Tính chất 5: (mở rộng tính chất 4) ik I, sigsup(ik) < minsigsup: all_conf(ik) = 1 và ik CORSI.
Bảng 2. Mức ý nghĩa của từng item trong Ɗ
Mục hàng A B C D E F G H
Mức ý nghĩa (sigi) 0,55 0,70 0,50 0,65 0,40 0,60 0,30 0,80
Ví dụ 2: Cho Ɗ trong Bảng 1, và mỗi item có mức ý nghĩa đƣợc cho trong Bảng 2 và minsigsup = 0,20
Xét itemset Y ={A,C,G}, ta có: sup({A,C,G}) = 0,50; sig({A,C,G}) = max(sigA, sigC, sigG) = max(0,55; 0,50;
0,30) = 0,55 và sigsup = 0,55 0,50=0,275 ≥ minsigsup=0,20 - ta nói: ”Y ={A,C,G} là itemset phổ biến có trọng số”;
Theo tính chất 1 (mở rộng cho trƣờng hợp có trọng số) thì các tập con của Y ={A,C,G} cũng phổ biến, nghĩa là
tất cả tập con của Y đều phổ biến - Các con của Y là Ysub = {(A; 0,44), (C; 0,40), (G; 0,15), (AC; 0,44), (AG; 0,275),
(CG; 0,25)}, tuy nhiên chỉ có các itemset {A, C, AC, AG, CG} là phổ biến; còn itemset {G}, ta có: sup({G}) = 0,50;
sig({G}) = 0,30 và sigsup({G}) = 0,15 < minsigsup = 0,20 là không phổ biến. Điều này cho chúng ta thấy: “Khai thác
tập phổ biến có trọng số (mức ý nghĩa của từng item) thì tính chất 1 là không thỏa”.
Theo tính chất 4, xét itemset Z = {G} có sup({G}) = 0,50; sig({G}) = 0,30 và sigsup({G}) = 0,15 < minsigsup
= 0,20, ta nói: “Itemset Z = {G} là itemset hiếm có trọng số”;
Theo tính chất 2 thì các tập cha của Z ={G} cũng không phổ biến. Tuy nhiên, ta có Z ={G} Y = {A,C,G}, mà
sup({A,C,G}) = 0,50; sig({A,C,G}) = max(0,55; 0,50; 0,30) = 0,55 và sigsup({A,C,G}) = 0,55 0,50=0,275 ≥
minsigsup=0,20 ; Y = {A,C,G} là itemset phổ biến. Điều này cho ta thấy: ”Khai thác tập hiếm có trọng số (mức ý
nghĩa của từng item) thì tính chất 2 là không thỏa ”.
Bảng 3. Tập RSI, CORSI trên dữ liệu giao dịch Ɗ với minsigsup = 0,15
Tập tương quan hiếm CORSI Tập tương quan hiếm CORSI
Tập hiếm RSI
k-itemset min_allconf = 0,25 min_allconf = 0,30
#RSI = 26
#CORSI = 23 #CORSI = 6
1 H, B, D H, B, D H, B, D
BA, BG, BE, BG, DA, DC, DG, DF, BE, BA, BC, DA, DC, DF, FE, DF, FG, EG
2
FE, FG, EG FG, EG
BEA, BEC, BAC, BGE, BGA, BGC, BEA, BEC, BAC, DAC, FEA,
3 DAC, DFA, DFC, DGA, DGC, DFG, FEC, FGA, FGC
FEA, FEC, FGA, FGC, FEG
BEAC, BGEA, BGEC, BGAC, BEAC, FEAC, FGAC
4 DFAC,DGAC, DFGA, DFGC,
FEAC, FGAC, FEGA, FEGC
5 BGEAC, DFGAC, FEGAC
Trong bảng 3, cho thấy tập hiếm có trọng số RSI và tập tƣơng quan hiếm CORSI chứa k-itemset với minsigsup
= 0,15. Số lƣợng tập hiếm |RSI| = 46, số lƣợng tập tƣơng quan hiếm |CORSI|0,25 = 23 và số lƣợng tập tƣơng
quan hiếm |CORSI|0,30 = 6. Tỷ suất CORSI 0,25 RSI 23 46 100% 50% . Qua đó, ta dễ dàng thấy mối
quan hệ giữa tập hiếm và tập tƣơng quan hiếm kết hợp độ đo all_confidence nhƣ sau: CORSI RSI.
- Phan Thành Huấn, Lê Hoài Bắc 453
C. 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 hiệu quả trong khai thác tập phổ biến [12]. Chuyển đổi dữ liệu
giao dịch thành ma trận nhị phân BiM, trong đó mỗi dòng ứng với một giao dịch và mỗi cột ứng với một item. Nếu
item thứ ik xuất hiện trong giao dịch tj thì bit thứ k của dòng tj trong BiM mang giá trị 1, ngƣợc lại mang giá trị 0.
III. CÁC THUẬT TOÁN
A. Tập chiếu và itemset đồng xuất hiện
Tập chiếu của item ik trên dữ liệu giao dịch Ɗ: (ik)={t Ɗ│ik t} là tập các giao dịch có chứa item ik.
sup(ik) = | ( ik)| (3)
Tập chiếu của itemset X ={i1, i2,..., ik}, ij I (1 j k), (X) = (i1) (i2)… (ik).
sup(X) = | ( X )| (4)
Ví dụ 3: Theo Bảng 1, có (A) = {t1, t2, t4, t5, t7, t8, t9, t10} và (B) = {t7, t9}. Khi đó, (AB) = (A) (B)=
{t1, t2, t4, t5, t7, t8, t9, t10} {t7, t9} = {t7, t9}, (B) (A) và (AB) (A).
Để tránh trùng lặp không gian sinh tập hiếm có trọng số, 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 có trọng số nhƣ sau:
Định nghĩa 9: Cho ik I (i1 i2 … im) thứ tự giảm dần theo mức ý nghĩa, 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 ij) , i j Xlexcooc, i k ij. Ký hiệu, lexcooc(ik) = Xlexcooc.
Định nghĩa 10: Cho ik I (i1 i2 … im) thứ tự giảm dần theo mức ý nghĩa, ta gọi ik là item hạt nhân. Tập
Ylexlooc I 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 ij) | < | ( ik)| , i j Ylexlooc, i k ij. Ký hiệu, lexlooc(ik) = Ylexlooc.
B. Thuật toán sinh itemset đồng xuất hiện có thứ tự
Trong phần này, trình bày thuật toán sinh các item đồng xuất hiện và 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 4 thành phần thông tin:
- 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: Index_COOC[k].item = ik
3: Index_COOC[k].sup = 0
4: Index_COOC[k].cooc= 2m - 1
5: 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)
10: Index_COOC[k].looc = Index_COOC[k].looc OR vectorbit(ti)
11: Index_COOC[k].sup = Index_COOC[k].sup + 1
12: Sắp xếp mảng Index_COOC giảm dần theo sig
13: Với mỗi phần tử k của mảng Index_LOOC:
14: Index_LOOC[k].cooc= lexcooc(ik)
15: Index_LOOC[k].looc= lexclooc(ik)
16: Trả về mảng Index_COOC, ma trận BiM
Dòng 1 đến dòng 5: 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:
nếu có chứa item thứ k thì thực hiện phép 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 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 (dòng 10).
- 454 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE
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 A B C D E F G H
sup 0 0 0 0 0 0 0 0
cooc 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
looc 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 A B C D E F G H
sup 1 0 1 0 1 1 0 0
cooc 10101100 11111111 10101100 11111111 10101100 10101100 11111111 11111111
looc 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 A B C D E F G H
sup 8 2 8 2 7 3 5 1
cooc 10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001
looc 11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001
Thuật toán 1, trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item theo Bảng 4.
Bảng 4. Trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item (dòng 1 đến 12)
item H B D F A C E G
sup 1 2 2 3 8 8 7 5
cooc E A, C, E A, C A, C C A Ø A, C
looc Ø G F, G D, E, G B, D, E, F, G B, D, E, F, G A, B, C, F, G, H B, D, E, F
Chỉ có itemset đồng xuất hiện của item C cần hiệu chỉnh. Ta có, cooc(C) = {A} và A C, nên lexcooc(C) =
{ }. Tƣơng tự, ta có looc(A) = {B, D, E, F, G} và B D F A E G, nên lexlooc(A) = {E, G}. Sau khi thực hiện
dòng 13, 14 và 15, ta có kết quả trong Bảng 5. Chúng tôi thêm vào mảng Index_COOC thành phần sig để minh họa
mảng có thứ tự giảm dần theo mức ý nghĩa.
Bảng 5. Trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item, thành phần cooc và looc có thứ tự
item H B D F A C E G
sig 0,80 0,70 0,65 0,60 0,55 0,50 0,40 0,30
sup 0,10 0,20 0,20 0,30 0,80 0,80 0,70 0,50
cooc E E, A, C A, C A, C C Ø Ø Ø
looc Ø G F, G E, G E, G E, G G Ø
C. Thuật toán xây dựng cây nLOOC-Tree
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ự giảm dần theo mức ý nghĩa). 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_COOC
Đầu ra: Danh sách cây nLOOC-Tree
1: Với mỗi phần tử k của mảng Index_COOC:
2: nLOOC_Tree[k].item = Index_COOC[k].item
3: nLOOC_Tree[k].sup = Index_COOC[k].sup
4: Với mỗi item ik giao dịch tℓ :
5: Với mỗi item ij Index_COOC[k].looc:
6: Nếu ij nút con của nút gốc nLOOC-Tree[k] thì
7: Thêm nút con ij vào nút gốc nLOOC-Tree[k]
8: Ngƣợc lại
9: Thêm nút con ij vào nút gốc nLOOC-Tree[k]
10: 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
Cây nLOOC-Tree có các đặc trƣng nhƣ sau:
- Phan Thành Huấn, Lê Hoài Bắc 455
- 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 1. Thuật toán 2 - sinh danh sách cây nLOOC-Tree theo mảng Index_COOC ở Bảng 5
Ví dụ 4: Xét item hạt nhân F, có đƣờng đi đơn {F E G} và sup({F,E,G}) = 0,10; phân đoạn đƣờng đi đơn
{F E} và sup({F,E}) = 0,20 là độ phổ biến của nút con E.
D. Thuật toán khai thác tập tương quan hiếm có trọng số ALLCONF-CORSI
Thuật toán 3 - ALLCONF-CORSI khai thác các itemset tƣơng quan hiếm có trọng số từ mảng Index_COOC
và cây nLOOC_Tree. Chúng tôi đề xuất các bổ đề rút gọn không gian sinh itemset tƣơng quan hiếm nhƣ sau:
Bổ đề 1: lexcooc(ik) Xlexcooc thì sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc).
Chứng minh: lexcooc(ik) Xlexcooc, xsub Ƥ 1(Xlexcooc). Theo định nghĩa 9, ta có (ik xsub) = (ik) (xsub) =
(ik) và theo phƣơng trình (3), (4) thì sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc) ■.
Ví dụ 5: Xét item F, với sup({F}) = 0,30. 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}) = 0,30.
Bổ đề 2: lexlooc(ik) Ylexlooc thì sup(ik ysub) < sup(ik), ysub Ƥ 1(Ylexlooc).
Chứng minh: Theo định nghĩa 10, 1 | ( ik ij) | < | ( ik)| , ij lexlooc(ik) và (4), ta có: sup(ik ysub) < sup(ik),
ysub Ƥ 1(Ylexlooc), hiển nhiên (ik ysub) = (ik) (ysub) (ik) ■.
Ví dụ 6: Xét item D, với sup({D}) = 0,20. Ta có, lexlooc(D) = {F, G} thì 3 itemset kết hợp {F, G, FG} và
sup({D,F}) = sup({D,G}) = sup({D,F,G}) = 0,10 < sup({D}) = 0,10.
Bổ đề 3: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sig(ik) sup(ik) minsigsup thì {ik
xsub} CORSI, xsub Ƥ 1(Xlexcooc).
Chứng minh: Theo bổ đề 1, sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc). Ta có, sigsup(ik xsub) =
max(sig(ik),{sig(ij)| ij xsub}) sup(ik) = sig(ik) sup(ik) minsigsup; khi đó, {ik xsub} RSI và hiển nhiên {ik xsub}
CORSI■.
Ví dụ 7: Cho minsigsup = 0,15, xét item F, có sup({F})= 0,30 và lexcooc(F) = {A, C}. Khi đó,
sup({F}) max(sig({F}), sig({A}), sig({C})) = sig({F}) sup({F}), = 0,60 0,30 = 0,18 minsigsup thì {FA, FC, FAC}
CORSI, vì sigsup({F,A}) = sigsup({F,C}) = sigsup({G,A,C}) = 0,18 minsigsup.
Bổ đề 4: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sig(ik) sup(ik) < minsigsup và sup(ik) <
min(sup(ij)| ij lexcooc(ik)) min_allconf thì {ik xsub} CORSI, xsub Ƥ 1(Xlexcooc).
Chứng minh: Theo bổ đề 1, sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc). Ta có, all_conf(ik xsub) = sup(ik
xsub)/max(sup(ik), {sup(ij)| ij xsub}) = sup(ik)/max(sup(ik), {sup(ij)| ij xsub}) < sup(ik)/min({sup(ij)| ij xsub}) <
sup(ik)/min({sup(ij)| ij lexcooc(ik)}) < min_allconf; khi đó, {ik xsub} CORSI, xsub Ƥ 1(Xlexcooc)■.
- 456 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE
Ví dụ 8: Cho minsigsup = 0,15 và min_allconf = 0,70; xét item D, có sup({D})= 0,20 và sig({D} = 0,65 với
lexcooc(D) = {A, C}. Khi đó, sigsup({D}) = 0,20 0,65 = 0,13 < minsigsup và sup({D}) = 0,20 < min(sup({A}),
sup({C})) min_allconf = 0,80 0,70 = 0,56 thì {DA, DC, DAC} CORSI, vì all_conf({D,A}) = 0,25,
all_conf({D,C}) = 0,25, all_conf({D,A,C}) = 0,25 < min_allconf.
Bổ đề 5: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sup(ik) < min(sup(ij)| ij lexlooc(ik)) min_allconf
thì {ik ysub} CORSI, ysub Ƥ 1(Ylexlooc).
Chứng minh: Theo bổ đề 2, sup(ik ysub) < sup(ik), ysub Ƥ 1(Ylexlooc). Ta có, all_conf(ik ysub) = sup(ik
ysub)/max(sup(ik), {sup(ij)| ij ysub}) < sup(ik)/max(sup(ik), {sup(ij)| ij ysub}) < sup(ik)/min(sup(ik), {sup(ij)| ij ysub})
< sup(ik)/min(sup(ik), {sup(ij)| ij lexlooc(ik)}) < min_allconf; khi đó, {ik ysub} CORSI, ysub Ƥ 1(Ylexlooc)■.
Ví dụ 9: Cho min_allconf = 0,70, xét item D, có sup({D})= 0,20 và lexlooc(D) = {G, F}. Khi đó, sup({D}) =
0,20 < 0,30 0,70 = 0,21 thì {DG, DF, DGF} CORSI, vì all_conf({D,G}) = 0,20, all_conf({D,F}) = 0,33,
all_conf({D,G,F}) = 0,20 < min_allconf.
Bổ đề 6: (Loại bỏ các đƣờng đi đơn không sinh CORSI) ik item hạt nhân và đƣờng đi đơn từ ik là spj
(ik ik+1 … iℓ) nếu sig(ik) sup(spj) minsigsup thì {ik sspl} CORSI, sspl spj.
Chứng minh: Theo đặc trƣng của cây nLOOC-Tree, sspl spj, sup(sspl) sup(spj). Ta có, sig(ik) sup(sspl)
sig(ik) sup(spj) minsigsup; khi đó, {ik sspl} RSI và hiển nhiên {ik sspl} CORSI, sspl spj ■.
Ví dụ 10: Cho minsigsup = 0,15, xét item hạt nhân A, có đƣờng đi đơn {A E G}, sup({A,E,G}) = 0,30 và
sigsup({A,E,G}) = sig({A,E,G}) sup({A,E,G}) = sig({A}) sup({A,E,G}) = 0,55 0,30 = 0,165 minsigsup và phân
đoạn đƣờng đi đơn {A E} và sigsup({A,E}) = sig({A,E}) sup({A,E}) = 0,55 0,50 = 0,275 minsigsup.
Mã giả thuật toán 3. Khai thác tập tương quan hiếm có trọng số ALLCONF_CORSI
Đầu vào: Mảng Dataset, Index_COOC, minsigsup và min_allconf
Đầu ra: Tập tƣơng quan hiếm có trọng số CORSI
1: Với mỗi Index_COOC[k].sigsup < minsigsup
2: CORSI[k] = CORSI [k] Index_COOC[k].item//theo tính chất 5
3: Với mỗi (Index_COOC[k].item)
4: Nếu ((Index_COOC[k].looc ={ }) và không thỏa Bổ đề 3 và 4)
5: CORSI[k]= {Index_COOC[k].item xsub | xsub Ƥ 1(Index_COOC[k].cooc)}
6: Nếu ((Index_COOC[k].looc { } và không thỏa Bổ đề 5)
7: nLOOC_Tree(Index_COOC[k].item)
8: SP GenPath(Index_COOC[k].item)//sinh single-path
9: Với mỗi spj SP
10: Nếu (Index_COOC[k].sig sup(spj) < minsigsup và
all_conf(Index_COOC[k].item spj) min_allconf)//Bổ đề 6
11: CORSI[k]= {Index_COOC[k].item sspl | sspl spj}
12: CORSI[k]= {Index_COOC[k].item sspl xsub| sspl spj,
xsub Ƥ 1(Index_COOC[k].cooc)
13: Nếu (Index_COOC[k].sig Index_COOC[k].sup < minsigsup và không thỏa Bổ đề 4)
14: CORSI[k]= {Index_COOC[k].item xsub | xsub Ƥ 1(Index_COOC[k].cooc)}
15: Trả về tập tƣơng quan hiếm có trọng số CORSI
Ví dụ 11: Cho dữ liệu giao dịch Ɗ trong Bảng 1, minsigsup = 0,15 và min_allconf = 0,25. Sau khi thực hiện
thuật toán 1 và 2, ta có mảng INDEX_COOC cùng với cây nLOOC-Tree, nhƣ trong Bảng 5 và Hình 1.
Dòng 1 và 2: các item hiếm theo tính chất 5 - có item H (sigsup(H) = 0,10 0,50 = 0,05 < minsigsup), B và D -
CORSI[H] = {(H; 0,10; 0,08)}, CORSI[B] = {(B; 0,20; 0,14)}, CORSI[D] = {(D; 0,20; 0,13)};
Dòng 4 và 6: không sinh CORSI từ item H và G;
Xây dựng các cây nLOOC-Tree cho các item cần khai phá: B, D, F, A và C ;
Xét item B, nLOOC-Tree(B) có một đƣờng đi đơn {B G}, sigsup({BG}) = 0,07 < minsigsup và
all_conf({BG}) = 0,20 < min_allconf , {BG} CORSI. Ta có, sigsup({B}) = 0,14 < minsigsup và không thỏa Bổ đề
4: sinh các itemset tƣơng quan hiếm có trọng số từ item B là CORSI[B] = {(BA; 0,20;0,14), (BC; 0,20;0,14), (BE;
0,20;0,14), (BAC; 0,20;0,14), (BAE; 0,20;0,14), (BCE; 0,20;0,14), (BACE; 0,20;0,14)}.
Xét item D, nLOOC-Tree(D) có một đƣờng đi đơn {D F G} và sigsup({DFG}) = 0,065 < minsigsup và
thỏa Bổ đề 4. Dòng 10, sinh phân đoạn đƣờng đi đơn {D F} có sigsup({DF}) = 0,065 < minsigsup và không thỏa Bổ
đề 4: sinh các itemset tƣơng quan hiếm có trọng số từ item D là CORSI[D] = {(DF; 0,10;0,065), (DA; 0,20;0,13), (DC;
0,20;0,13), (DAC; 0,20;0,13)}.
- Phan Thành Huấn, Lê Hoài Bắc 457
Xét item F, nLOOC-Tree(F) có hai đƣờng đi đơn {F E G} và {F G}: sigsup({FEG}) = 0,06 <
minsigsup và thỏa Bổ đề 4. Dòng 10, sinh phân đoạn đƣờng đi đơn {F E} có sigsup({FE}) = 0,12 < minsigsup và
không thỏa Bổ đề 4, sinh các itemset tƣơng quan hiếm có trọng số từ item F là CORSI[F] = {(FE; 0,20;0,12), {(FAE;
0,20;0,12), {(FCE; 0,20;0,12), {(FACE; 0,20;0,12)}, tƣơng tự đƣờng đi đơn {F G} sinh thêm các itemset tƣơng
quan hiếm có trọng số CORSI[F] = {(FG; 0,20;0,12), {(FAG; 0,20;0,12), {(FCG; 0,20;0,12), {(FACG; 0,20;0,12)}.
Xét item E, cây nLOOC-Tree(E): có một đƣờng đi đơn {E G} và ssigup(EG) = 0,12 < minsigsup và không
thỏa Bổ đề 4: sinh các itemset tƣơng quan hiếm có trọng số từ item E là CORSI[E] = {(EG; 0,30;0,12)}.
Tập tƣơng quan hiếm có trọng số CORSI trên Ɗ ở Bảng 1 với minsigsup = 0,15 và min_allconf = 0,25:
Item hạt
Tập tương quan hiếm có trọng số CORSI
nhân
H (H;0,1;0,08)
B (B;0,2;0,14) (BE;0,2;0,14) (BA;0,2;0,14) (BC;0,2;0,14) (BAE;0,2;0,14) (BCE;0,2;0,14) (BAC;0,2;0,14) (BACE;0,2;0,14)
D (D;0,2;0,13) (DA;0,2;0,13) (DC;0,2;0,13) (DF;0,1;0,065) (DAC;0,2;0,13)
F (FE;0,2;0,12) (FG;0,2;0,12) (FAE;0,2;0,12) (FCE;0,2;0,12) (FGA;0,2;0,12) (FGC;0,2;0,12) (FACE;0,2;0,12) (FGAC;0,2;0,12)
E (EG;0,3;0,12)
IV. KẾT QUẢ THỰC NGHIỆM
Thực nghiệm trên máy tính Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên C#, MVS 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
California (Lichman, M. (2013). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA:
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 6. Dữ liệu thực nghiệm
Số 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 Số mục
giao dịch giao dịch giao dịch giao dịch (%)
Chess 75 3.196 37 37 37 49,3
Mushroom 119 8.142 23 23 23 19,3
T10I4D100K 870 100.000 1 29 10 1,1
T40I10D100K 942 100.000 4 77 40 4,2
Trong bài viết này, chúng tôi đề xuất thuật toán khai thác tập tƣơng quan hiếm có trọng số kết hợp độ đo All-
Confidence và giải quyết bài toán theo hƣớng sinh các tập hiếm có trọng số không thoả tính chất bao đóng giảm. Đây
là đề xuất đầu tiên theo hƣớng tiếp cận trên, nên chƣa có thuật toán cùng hƣớng tiếp cận để so sánh hiệu năng thuật
toán. Vì vậy, chúng tôi đề xuất so sánh hiệu năng thuật toán theo 2 thực nghiệm sau:
A. Thực nghiệm thứ 1
Khai thác tập tƣơng quan hiếm có trọng số kết hợp độ đo tƣơng quan All-Confidence:
Trong thực nghiệm 1, chúng tôi dựa vào thuật toán IWI [7] và cải tiến thành thuật toán khai thác tập hiếm có
trọng số item đồng thời kết hợp độ đo All-Confidence, gọi là IWI. Trên cơ sở này, chúng tôi so sánh hiệu năng thuật
toán IWI với thuật toán đề xuất ALLCONF-CORSI: cho minsigsup thay đổi và cố định min_allconf.
Mức ý nghĩa (trọng số) của từng item đƣợc phát sinh ngẫu nhiên trong [0, 1] và cố định ngƣỡng min_allconf.
(a) Chess+min_allconf=0,30 (b) Mushroom+min_allconf=0,30
1000.000 1000.000
Thời gian (mili giây)
Thời gian (mili giây)
100.000 100.000
IWI IWI
10.000 10.000
ALLCONF-CORSI ALLCONF-CORSI
1.000 1.000
0,20 0,21 0,22 0,23 0,24 0,15 0,16 0,17 0,18 0,19
minsigsup minsigsup
Hình 2. Thời gian thực hiện ALLCONF-CORSI và IWI trên Chess, Mushroom
- 458 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE
Hình 2a và 2b 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 ALLCONF-CORSI
nhanh hơn thuật toán IWI.
(a) T10I4D100K+min_allconf=0,25 (b) T40I10D100K+min_allconf=0,25
1000.000 100.000
Thời gian (mili giây)
Thời gian (mili giây)
100.000
10.000
IWI IWI
10.000
ALLCONF-CORSI ALLCONF-CORSI
1.000 1.000
0,015 0,016 0,017 0,018 0,019 0,025 0,030 0,035 0,040 0,045
minsigsup minsigsup
Hình 3. Thời gian thực hiện ALLCONF-CORSI và IWI trên T10I4D100K, T40I10D100K
Hình 3a và 3b 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 ALLCONF-
CORSI nhanh hơn thuật toán IWI. Hiệu suất của thuật toán ALLCONF-CORSI rất cao so với IWI trên dữ liệu thƣa.
B. Thực nghiệm thứ 2
Khai thác ALLCONF-CORSI không trọng số:
sigi1 sigi2 ... sigim 1 (5)
Thuật toán ALLCONF-CORSI, có mức ý nghĩa (trọng số) các mục thỏa (5) là thuật toán khai thác tập tƣơng
quan hiếm không trọng số (mức ý nghĩa các item như nhau), đồng thời ngƣỡng độ đo tƣơng quan min_allconf = 0.
Trong thực nghiệm 2, chúng tôi so sánh thuật toán đề xuất ALLCONF-CORSI (có trọng số là như nhau và
ngưỡng độ đo tương quan minallconf = 0, ký hiệu là ALLCONF-CORSI-0) với thuật toán AprioriInverse [8], đây là
thuật toán khai thác tập tƣơng quan hiếm không trọng số hiệu quả trong những năm gần đây.
(a) Chess (b) Mushroom
1000.000 1000.000
Thời gian (mili giây)
Thời gian (mili giây)
100.000 100.000
10.000 10.000
AprioriInverse AprioriInverse
1.000 ALLCONF-CORSI-0 1.000 ALLCONF-CORSI-0
.100 .100
25 30 35 40 45 10 15 20 25 30
Minsup (% ) Minsup (% )
Hình 4. Thời gian thực hiện ALLCONF-CORSI-0 và AprioriInverse trên Chess, Mushroom
Hình 4a và 4b 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 ALLCONF-CORSI-
0 nhanh hơn thuật toán AprioriInverse.
(a) T10I4D100K (b) T40I10D100K
1000.000 1000.000
Thời gian (mili giây)
Thời gian (mili giây)
100.000 100.000
10.000 10.000
AprioriInverse AprioriInverse
1.000 ALLCONF-CORSI-0 1.000 ALLCONF-CORSI-0
.100 .100
0,1 0,2 0,3 0,4 0,5 0,3 0,4 0,5 0,6 0,7
Minsup (% ) Minsup (% )
Hình 5. Thời gian thực hiện ALLCONF-CORSI-0 và AprioriInverse trên T10I4D100K, T40I10D100K
Hình 5a và 5b 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 ALLCONF-
CORSI-0 hiệu quả hơn thuật toán AprioriInverse rất nhiều. Hiệu suất của thuật toán ALLCONF-CORSI-0 rất cao so
với AprioriInverse trên dữ liệu thƣa.
Kết quả trên cho thấy thuật toán khai thác tập tƣơng quan hiếm có trọng số ALLCONF-CORSI tốt hơn thuật
toán mới gần đây. 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.
- Phan Thành Huấn, Lê Hoài Bắc 459
V. KẾT LUẬN
Nhóm tác giả đã đề xuất thuật toán khai thác tập tương quan hiếm có trọng số gồm ba giai đoạn: giai đoạn thứ
nhất là tính nhanh mảng Index_COOC chứa các item đồng xuất hiện và 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: xây dựng cây nLOOC-Tree; giai đoạn thứ ba: thuật toán ALLCONF-CORSI khai
thác hiệu quả tập tương quan hiếm có trọng số dựa trên mảng Index_COOC và cây nLOOC-Tree. Với kiến trúc nhƣ
trên, khi ngƣời dùng khai thác tập tƣơng quan hiếm có trọng số với ngưỡng khác thì thuật toán đề xuất chỉ thực hiện
khai thác tập tƣơng quan hiếm trên mảng Index_COOC và cây nLOOC-Tree đã 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 tương quan hiếm có trọng số kết hợp độ đo
Any-confidence, Bond,… 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.
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] E. Omiecinski, “Alternative interest measures for mining associations in databases”. IEEE Transactions on
Knowledge and Data Engineering, 15(1), pp.57-69, 2003.
[5] C.H. Cai, A.W. Fu, C.H. Cheng, W.W. Kwong, “Mining association rules with weighted items”. Proceedings of
International Database Engineering and Applications Symposium (IDEAS 98), pp.68-77, 1998.
[6] F. Tao, F. Murtagh, M. Farid, “Weighted association rule mining using weighted support and significance
framework”. SIGKDD’03, pp.661-666, 2003.
[7] S. Kamepalli, R. S. R. Kurra, Y. K. K. Sundara, “Infrequent Pattern Mining from Weighted Transactional Data
Set”. International Journal of Research Studies in Computer Science and Engineering, 2(3), pp. 1-5, 2015.
[8] Y. S. Koh, N. Rountree, “Finding sporadic rules using apriori-inverse”. In PAKDD’05, 3518, pp.97-106, 2005.
[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.
[11] S. Bouasker, S. B. Yahia, “Key correlation mining by simultaneous monotone and anti-monotone constraints
checking”. Proc. of the 2015 ACM Symposium on Applied Computing (SAC 2015), pp. 851-856, 2015.
[12] Phan Thành Huấn, Lê Hoài Bắc, “Thuật toán hiệu quả khai thác tập hiếm tối thiểu”. Hội nghị 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); tr. 497-505, 2018.
AN EFFICIENT MINING ALGORITHM RARE CORRELATED SIGNIFICANCE ITEMSET
COHERENCE ALL-CONFIDENCE MEASURE
Phan Thanh Huan, Le Hoai Bac
ABSTRACTL: 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 the traditional data mining on transaction
databases, which items have no weight (equal weight, as equal to 1). However, in real world applications are often each item has a
different weight (the importance/significance of each item). Therefore, we need to mining weighted frequent/rare itemsets on
transaction databases. In this paper, we proposed an algorithm for mining rare correlated significance itemsets approach based on
NOT satisfy the downward closure property and coherence the anti-monotone constraint of correlation belong to the all-confidence
measure. We propose an efficient algorithm called ALLCONF-CORSI. The experimental results show that the proposed algorithms
perform faster than other existing algorithms on both real-life datasets of UCI and synthetic datasets generated by IBM Almaden.
Keywords: all-confidence measure, rare correlated significance itemset, ALLCONF-CORSI algorithm.
nguon tai.lieu . vn
