TRƯỜNG ĐẠI HỌC SÀI GỊN
SAIGON UNIVERSITY
TẠP CHÍ KHOA HỌC
SCIENTIFIC JOURNAL
ĐẠI HỌC SÀI GÒN
OF SAIGON UNIVERSITY
Số 77 (06/2021)
No. 77 (06/2021)
Email: ; Website: />
KHAI THÁC LUẬT PHÂN LỚP KẾT HỢP THEO TẬP DỰ ĐOÁN
Mining class association rule based on predictive collection
ThS. Nguyễn Anh Tú
Trường Đại học Ngoại ngữ – Tin học TP.HCM

TĨM TẮT
Bài viết giới thiệu các thuật tốn khai thác luật phân lớp kết hợp, đặc biệt là thuật toán PCAR đề xuất tỷ
lệ dự đoán, được chọn ưu tiên hơn độ tin cậy, độ hỗ trợ… để đánh giá luật, tạo ra bộ phân lớp chính xác
hơn. Tuy nhiên, việc dự đoán đơn luật ưu tiên chọn tỷ lệ dự đoán dẫn đến việc dự đoán sai ở nhiều tập
dữ liệu mất cân bằng về lớp. Do đó, bài viết đề xuất thuật toán DPCAR để cải tiến giai đoạn dự đốn
bằng cách ưu tiên chọn nhóm cao nhất về số luật phủ; về trung bình điều hịa của tỷ lệ dự đoán và độ tin
cậy; và về độ hỗ trợ của luật trong bộ phân lớp. Kết quả thực nghiệm cho thấy thuật toán đề xuất đã tăng
khoảng 1.31% và 1.93% khi so sánh với hai phiên bản của thuật toán PCAR cũng như vượt trội so với
các thuật tốn trước đó về độ chính xác trên 14 tập dữ liệu trong tập UCI.
Từ khóa: phân lớp, luật phân lớp kết hợp, tập dự đoán, khai thác dữ liệu
ABSTRACT
This paper will present the algorithms for mining the class association rule, especially an algorithm
named PCAR that has proposed a novel measure, known as the predictive rate, which has priority over
confidence, support, etc., in the rule evaluation, has built the classifier with high accuracy. However, by
using single accurate rule prediction, many cases were incorrectly covered by the rule which higher
predictive rate, especially in imbalanced real datasets. Therefore, this paper proposes the DPCAR
algorithm to improve PCAR algorithm at the prediction phase by selecting the class with priority

dominant class groups; the highest harmonic mean ratio between predictive rate and confidence; and the
highest support of rule in the classifier. The experimental results show that the proposed algorithm has
increased by 1.31% and 1.93% compared to two versions of PCAR algorithm as well as outperformed
the previous algorithms over 14 data sets of UCI Repository.
Keywords: classification, class association rules, predictive collection, data mining

cho dữ liệu mới vào trong một những lớp
đã được xác định trước trong dữ liệu giao
dịch. Từ những định nghĩa trên, các nhà
nghiên cứu đã đề xuất phương pháp kết
hợp hai kỹ thuật đó lại để tạo ra một
phương pháp mới gọi là phân lớp kết hợp.
Phân lớp kết hợp (Associative
Classification - AC) là một phương pháp

1. Giới thiệu
Khai thác luật kết hợp và phân lớp là
những bài toán quan trọng được nghiên
cứu hiện nay trong khai thác dữ liệu. Trong
khi khai thác luật kết hợp là quá trình đi
tìm mối liên kết giữa các hạng mục thì bài
tốn phân lớp có nhiệm vụ xây dựng ra bộ
phân lớp từ dữ liệu huấn luyện để phân lớp
Email:

26


NGUYỄN ANH TÚ


TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

kết hợp việc khai thác luật kết hợp để xây
dựng bộ phân lớp hay mơ hình phân lớp
(classifier) và dự đốn các mẫu chưa biết
trước lớp trong bài toán phân lớp dữ liệu.
Đầu tiên, các luật kết hợp được tạo ra bằng
việc sử dụng các thuật toán khai thác tập
phổ biến để sinh luật, có thể kể đến như
Apriori [1], Eclat [2], FP-growth [3] v.v.
Sau đó, các luật được sinh ra dưới dạng
luật phân lớp kết hợp (Class Association
Rules - CARs) được giữ lại để đánh giá.
Luật phân lớp kết hợp là một dạng đặt biệt
của luật kết hợp mà vế trái (hay tiền đề) là
các hạng mục và vế phải (hay hệ quả) là
thuộc tính lớp. Trong giai đoạn đánh giá,
AC sử dụng các độ đo như độ tin cậy
(confidence - conf), độ hỗ trợ (support supp), độ dài tiền đề (cardinality) hay tần
suất xuất hiện từng lớp (frequency)… của
luật để xếp hạng, cắt tỉa luật dư thừa rồi
xây dựng bộ phân lớp phục vụ cho q
trình dự đốn.
Khai thác luật phân lớp kết hợp được
đề xuất bởi Liu và các cộng sự vào năm
1998 [4] bằng việc kết hợp hai kỹ thuật
trong khai thác dữ liệu là khai thác luật kết
hợp và phân lớp; thuật toán CBA cũng
được đề xuất trong cơng trình này. Thuật
tốn bao gồm hai giai đoạn chính: giai

đoạn sinh luật (áp dụng thuật tốn CBARG) và giai đoạn xây dựng bộ phân lớp (áp
dụng thuật toán CBA-CB) đã chứng minh
được sự cải thiện về độ chính xác so với
các thuật tốn phân lớp dựa trên luật trước
như cây quyết định [5], ILA [6] v.v. Vào
năm 2001, W. Li và các cộng sự đã đề xuất
thuật toán phân lớp dựa trên đa luật
(Classification
based
on
Multiple
Association Rules - CMAR) [7], sử dụng
cây FP (Frequent Pattern Tree) để nén dữ
liệu và dùng phép chiếu trên cây để tìm ra
luật phân lớp. Ở giai đoạn dự đoán luật

trong tập kiểm thử, CMAR chia các luật có
thể dự đốn được thành từng nhóm theo
thuộc tính lớp rồi tính giá trị chi bình
phương trọng số (Weighted Chi-square weighted2) cho mỗi nhóm và chọn thuộc
tính lớp của nhóm có giá trị weighted2 lớn
nhất để dự đoán cho mẫu kiểm thử. Thuật
toán CMAR đã đem lại hiệu quả cao trong
việc tăng độ chính xác của tập luật CARs
khai thác được. Tiếp sau đó, Thabtah và
các cộng sự đã đề xuất thuật toán MMAC
(Multi-class,
Multi-label
Associative
Classification) [8] để khai thác luật phân

lớp kết hợp đa lớp, đa nhãn vào năm 2004.
Thuật toán MMAC bao gồm ba giai đoạn:
đầu tiên, thuật toán sinh tập luật CARs thỏa
ngưỡng tin cậy tối thiểu (minimum
confidence - minconf) và xếp hạng, cắt tỉa
để bỏ các luật dư thừa; sau đó, thuật tốn
dùng đệ quy để khai thác các dòng dữ liệu
còn lại của tập dữ liệu huấn luyện sau khi
đã qua bước cắt tỉa ở giai đoạn đầu, sinh ra
một tập luật mới rồi gộp với tập luật đã
khai thác được ở giai đoạn đầu để tạo ra bộ
phân lớp có tính đa lớp, phục vụ cho giai
đoạn dự đoán lớp cho các dòng ở tập dữ
liệu kiểm thử. Với việc thực hiện các bước
ở giai đoạn 2, thuật toán MMAC đã cải
thiện được độ chính xác với các trường hợp
dự đốn các luật đa nhãn lớp so với các
thuật tốn trước đó. Vào năm 2005, chính
nhóm tác giả trên lại đề xuất một thuật toán
mới gọi là phân lớp luật kết hợp đa lớp
(Multi-class Classification based on
Association Rule - MCAR) [9] áp dụng kỹ
thuật tìm tập phổ biến hiệu quả để tạo tập
luật CARs và hướng tiếp cận đánh giá luật
mới để tạo bộ phân lớp có độ tin cậy và độ
chính xác cao, phục vụ cho q trình dự
đốn lớp chưa biết nhãn.
Một trong số những điểm còn hạn chế
của các thuật toán khai thác luật phân lớp
27



SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY

No. 77 (06/2021)

huấn luyện sẽ được chọn để dự đoán.
2. Nội dung nghiên cứu
2.1. Sơ bộ về khai thác luật phân lớp
kết hợp (Class association rule mining)
Khai thác luật phân lớp kết hợp là bài
tốn tìm ra một tập con của các luật kết
hợp có trong cơ sở dữ liệu mà mỗi luật kết
hợp trong tập con này chứa vế phải là giá
trị của thuộc tính lớp. Bài toán được phát
biểu như sau:

kết hợp kể trên là phụ thuộc chủ yếu vào
việc chọn ngưỡng hỗ trợ, ngưỡng tin cậy
tối thiểu. Một ngưỡng quá cao sẽ dẫn đến
các lớp chứa ít mẫu sẽ khơng phổ biến và
vì vậy không luật nào của lớp này được
nằm trong bộ phân lớp; trong khi một
ngưỡng quá thấp sẽ dẫn đến việc bộ phân
lớp sẽ chứa số lượng lớn luật đa lớp và cả
hai đều ảnh hưởng đến quá trình dự đốn
lớp. Vào năm 2017, nhóm tác giả Song và
Lee đề xuất một thuật tốn đưa ra một tiêu
chí mới gọi là tỷ lệ dự đoán (predictive rate
- pr), ưu tiên hơn độ tin cậy, độ hỗ trợ… để

đánh giá luật, xây dựng bộ phân lớp dự
đốn chính xác hơn các hướng tiếp cận
trước, đó chính là thuật tốn PCAR
(Predictability-based Collective Class
Association Rule mining) [10].
Tuy nhiên, ở giai đoạn dự đoán luật,
Song và Lee [10] chọn tỷ lệ dự đoán làm
tiêu chí ưu tiên hàng đầu dẫn đến nhiều
trường hợp bị dự đốn sai khi các luật có tỷ
lệ dự đốn thấp hơn lại có thuộc tính lớp
đúng với mẫu trong tập dữ liệu kiểm thử,
đặc biệt đối với trường hợp tập dữ liệu bị
mất cân bằng về lớp. Do vậy, bài viết này
đề xuất một hướng cải tiến để khắc phục
nhược điểm trên. Giải pháp của bài viết
này tập trung ở giai đoạn dự đoán, khi một
mẫu mới chưa biết trước lớp của tập kiểm
thử được đưa vào dự đoán, thuật tốn sẽ
chọn theo thứ tự lớp của nhóm có số lượng
luật phủ được mẫu kiểm thử nhiều nhất
(Dominant Class - DC), nhóm có giá trị
trung bình cộng của trung bình điều hịa
HM (Average Harmonic Mean - AHM)
giữa tỷ lệ dự đốn và độ tin cậy cao nhất,
nhóm có giá trị trung bình độ hỗ trợ
(Average Support - AS) cao nhất để dự
đốn. Trường hợp khơng có luật nào phủ
được mẫu, lớp mặc định (default class) – là
lớp xuất hiện nhiều nhất trong tập dữ liệu


Cho tập dữ liệu huấn luyện T với m
thuộc tính A1, A2,…, Am và 𝐶 là danh sách
thuộc tính lớp. |𝑇| là lực lượng của T.
Định nghĩa 1: AttributeValueSet là tập
các thuộc tính và giá trị của nó, ký hiệu <
(𝐴𝑖1 , 𝑎𝑖1 ), … , (𝐴𝑖𝑚 , 𝑎𝑖𝑚 ) >.
Định nghĩa 2: Một luật phân lớp kết
hợp r là một phép kéo theo có dạng
𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑉𝑎𝑙𝑢𝑒𝑆𝑒𝑡 → 𝑐 trong đó, 𝑐 ∈ 𝐶
là một nhãn lớp.
Định nghĩa 3: Số lần xuất hiện của một
luật r trong T, ký hiệu 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟), là số
dòng trong T chứa AttributeValueSet của r.
Định nghĩa 4: Số hỗ trợ của một luật r
trong T, ký hiệu 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟), là số
dòng trong T chứa AttributeValueSet của r
và thuộc tính lớp của C giống với thuộc
tính 𝑐 của r.
Định nghĩa 5: Một luật r vượt qua
ngưỡng hỗ trợ tối thiểu (minsupp) khi
𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟)
|𝑇|

≥ 𝑚𝑖𝑛𝑠𝑢𝑝𝑝.

Định nghĩa 6: Một luật r vượt qua
ngưỡng tin cậy tối thiểu (minconf) khi
𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟)
𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟)


≥ 𝑚𝑖𝑛𝑐𝑜𝑛𝑓.

Ví dụ 1: Cho T là cơ sở dữ liệu giao
dịch như Bảng 1 với 6 dịng dữ liệu |𝑇|=6,
các thuộc tính {X, Y, Z}, thuộc tính lớp là
thuộc tính quyết định Lớp = {Yes, No}.
28


NGUYỄN ANH TÚ

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

hai tập con: inner training set (TR i ) và
inner testing set (TEi ) theo tỷ lệ tương ứng
(k-1):1. Ở mỗi lần chạy, thuật tốn tính tỷ
lệ dự đốn của mỗi luật trong RS theo công
thức:

Bảng 1. Dữ liệu giao dịch T ví dụ 1
OID
X
Y
Z
Lớp
1

x1

y1


z1

Yes

2

x1

y2

z1

No

3

x2

y2

z1

No

4

x3

y1


z2

No

5

x3

y3

z1

No

𝑝̂ (𝑗|𝑖 ) =

𝑠𝑢𝑝𝑝 (𝑟)
𝑇

|𝑇𝐸𝑖 |

(1)

Trong đó, i là lần chạy vòng lặp trong
k và j là lần duyệt từng luật trong RS. Sau
đó, RS sẽ được xếp hạng theo thứ tự ưu
tiên như Hình 1 để sử dụng cho giai đoạn
cắt tỉa luật, xây dựng bộ phân lớp RSi ở lần
chạy thứ i.

Sau k lần chạy, các RSi sẽ được hợp
nhất lại thành bộ phân lớp chung URS,
trong quá trình hợp nhất, nếu một luật xuất
hiện nhiều lần ở các bộ phân lớp RSi, thuật
toán sẽ tính trung bình cộng của tỷ lệ dự
đốn cho luật đó theo cơng thức:
1
𝑝̂𝑗 = ∑𝑘𝑖=1 𝑝̂ (𝑗|𝑖 )
(2)

6
x1
y2
z2
Yes
Xét luật r: (𝑋, 𝑥1 ) → 𝑌𝑒𝑠 với A =
(𝑋, 𝑥1 ) và c = Yes, ta có:
𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟) = 3; 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟) = 2;
𝑐𝑜𝑛𝑓𝑇 (𝑟) = 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇

𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇𝐸𝑖 (𝑟𝑗 )

2

= 3.
(𝑟)

2.2. Thuật toán khai thác luật phân
lớp kết hợp dựa trên tập dự đoán PCAR
Phương pháp đề xuất của bài viết này

là một phiên bản cải tiến của thuật tốn
PCAR, vì vậy, giai đoạn sinh luật và đánh
giá luật để xây dựng bộ phân lớp hầu như
tương đồng với thuật toán ban đầu.
Trong nghiên cứu của mình, Song và
Lee [10] áp dụng thuật toán Eclat [2] (với
minsupp = 0.05 và minconf = 0.4) để khai
thác các luật kết hợp rồi từ đó chọn ra các
CARs tạo thành tập luật (RuleSet - RS).
Sau đó, thuật tốn áp dụng kỹ thuật đánh
giá chéo (cross-validation) chạy k vòng lặp,
mỗi lần chia tập dữ liệu huấn luyện thành

𝑘

Sau cùng, URS đã được xếp hạng được
dùng để dự đoán luật của tập dữ liệu kiểm
thử. Với một mẫu t trong tập dữ liệu kiểm
thử chưa biết lớp, thuật tốn sẽ tìm ra luật
đầu tiên trong tập URS có thể phủ được t và
chọn lớp của luật đó để dự đốn cho mẫu t.
Nếu khơng có luật nào trong URS phủ được
t, lớp mặc định sẽ được chọn để dự đốn cho
mẫu t.

Hình 1. Thứ tự xếp hạng luật của thuật toán PCAR
29


SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY


No. 77 (06/2021)

thường gặp phải vấn đề giới hạn ngưỡng
minsupp và minconf. Thông thường, ở giai
đoạn sinh luật hoặc cắt tỉa luật dư thừa, các
thuật toán này chỉ chọn những luật có giá
trị
𝑠𝑢𝑝𝑝 ≥ 𝑚𝑖𝑛𝑠𝑢𝑝𝑝
và
𝑐𝑜𝑛𝑓 ≥
𝑚𝑖𝑛𝑐𝑜𝑛𝑓 dẫn đến nhiều luật có ích bị loại
bỏ. Lấy ví dụ, với minsupp = 0.2 và
minconf = 0.6 thì một luật với supp = 0.6
và conf = 0.5 sẽ không được sinh ra trong
giai đoạn sinh luật hoặc giữ lại ở giai đoạn
tỉa luật. Bằng việc áp dụng cách tính trung
bình điều hịa giữa độ tin cậy và độ phổ
biến, vấn đề trên sẽ được giải quyết. Tương
tự như trên, bài viết này áp dụng cách tính
trung bình điều hịa giữa tỷ lệ dự đoán và
độ phổ biến để khắc phục vấn đề mà thuật
tốn PCAR gặp phải đó là chỉ chọn các luật
trong URS với tỷ lệ dự đoán từ cao xuống
thấp để dự đoán trước rồi mới xét đến độ
phổ biến khi các luật có cùng tỷ lệ dự đốn.
Xét ví dụ: luật r1: a  c1 có pr = 0.8, conf
= 0.5 và luật r2: a  c2 có pr = 0.6, conf =
0.65 trong URS; mẫu t cần dự đốn có vế
trái là a (thuộc tính lớp đúng là c2). Vì luật

r2 có giá trị HM là 0.624 lớn hơn giá trị
HM của luật r1 là 0.615 nên ta chọn lớp c2
để dự đoán cho mẫu t (nếu áp dụng trung
bình cộng giữa pr và conf trong trường hợp
này thì sẽ chọn lớp của luật r1 dẫn đến dự
đốn sai).
Nếu giá trị AHM của các nhóm tiếp tục
bằng nhau, thuật tốn sẽ tính AS là trung
bình cộng độ hỗ trợ của mỗi nhóm rồi chọn
lớp của nhóm có giá trị AS cao nhất để dự
đốn, trường hợp cịn lại thì chọn lớp của
nhóm ngẫu nhiên để dự đốn. Nếu khơng
có luật nào của URS phủ được mẫu t, lớp
mặc định sẽ được chọn để dự đoán cho t.
3.2. Thuật toán
 Đầu vào: Bộ phân lớp chung (URS),

3. Đề xuất thuật toán DPCAR cải
tiến giai đoạn dự đốn luật
3.1. Ý tưởng chính
Như đã trình bày ở trên, nhóm tác giả
Song và Lee [10] dựa vào tỷ lệ dự đốn
làm tiêu chí ưu tiên hàng đầu trong giai
đoạn dự đoán luật dẫn đến nhiều trường
hợp bị dự đoán sai. Do đó, bài viết này đề
xuất thuật tốn DPCAR để khắc phục
nhược điểm trên.
Với mỗi mẫu t cần dự đoán lớp trong
dữ liệu kiểm thử, thuật toán sẽ đếm số
lượng các luật phủ được t trong tập URS

khai thác được từ thuật tốn PCAR rồi chia
nhóm các luật đó theo lớp, sau đó lớp ở
nhóm có số lượng luật cao nhất gọi là
dominant class sẽ được chọn để dự đoán
lớp cho t. Phương pháp này giúp khắc phục
được việc các luật được xếp hạng cao hơn
nhưng dự đoán sai mẫu thử, đặc biệt là các
luật mà vế trái có ít thuộc tính thường có tỷ
lệ dự đốn, độ tin cậy, độ hỗ trợ… cao hơn
nên được xếp trên các luật khác ở bước xếp
hạng luật.
Trong trường hợp có hai nhóm
dominant class trở lên, thuật tốn sẽ tính
giá trị trung bình điều hịa (HM) của từng
luật ở mỗi nhóm theo cơng thức (3) rồi
chọn lớp ở nhóm có trung bình cộng HM
(AHM) cao nhất để dự đốn.
𝐻𝑀 =

2∗𝑝𝑟∗𝑐𝑜𝑛𝑓
𝑝𝑟+𝑐𝑜𝑛𝑓

(3)

Trong đó, HM là trung bình điều hịa
giữa tỷ lệ dự đốn và độ tin cậy. Về mặt lý
thuyết, trung bình điều hịa thường được
dùng để tính giá trị trung bình của các biến
được biểu diễn dưới dạng tỷ lệ hoặc giá trị
biến có trọng số thay vì sử dụng các giá trị

trung bình khác. Nhiều thuật tốn về AC
30


NGUYỄN ANH TÚ

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

Tập dữ liệu kiểm thử (TS)
 Đầu ra: lớp dự đoán
 Chi tiết thuật toán:
1 prs = ∅ ; // tập chứa các luật phủ
được mẫu của TS
2 for each i in TS
3 for each r in URS
if r phủ i
4
prs = prs + r;
5
end if
6
7 end for
8 if prs ≠ ∅
Chia prs thành các nhóm lớp;
9
Đếm số lượng luật mỗi nhóm;
10
Tính HM mỗi luật theo (3);
11
Tính trung bình cộng HM: 𝐴𝐻𝑀 =

12
𝐻𝑀1 +⋯+𝐻𝑀𝑛
;
𝑛
13 if prs chỉ có một nhóm lớp
14
Chọn lớp nhóm này dự đốn;
15 else
16 if nhóm có AHM lớn nhất = 1
17
Chọn lớp nhóm này dự đốn;
18 else
19
if nhóm có AS lớn nhất = 1
20
Chọn lớp nhóm này dự đốn;
21
else
22
Chọn lớp ngẫu nhiên giữa các
nhóm để dự đốn;
23
end if
24 end if
25 end if
26 else /*khơng có r nào phủ i*/
27 Chọn lớp mặc định dự đoán;
28 end if
29 end for


lớp (B, R, L) và chia ngẫu nhiên thành tập
dữ liệu huấn luyện (gồm 562 giao dịch) và
tập dữ liệu kiểm thử (63 giao dịch) (bảng
2). Sau khi chạy thuật toán PCAR [13] trên
tập dữ liệu huấn luyện (k = 5, minsupp =
0.05, minconf = 0.4) thu được URS gồm 20
luật như bảng 3.
 Xét trường hợp dữ liệu kiểm thử
TID 1: 2 4 3 4 => R.
Thuật toán PCAR sử dụng luật UID
11: NA 4 NA NA => L trong URS (với NA
là giá trị rỗng ở cột thuộc tính, luật UID 11
là luật đầu tiên tìm được trong tập URS phủ
được TID 1) để dự đoán dẫn đến dự đoán
sai.
Thuật toán DPCAR xác định được các
luật UID 11 (lớp L), UID 13 (lớp R), UID 15
(lớp R) có thể dự đốn được; nhóm lớp R có
số lượng là 2 trong khi nhóm lớp L có số
lượng là 1 nên chọn nhóm lớp R để dự đốn,
suy ra dự đoán đúng.
 Xét trường hợp dữ liệu kiểm thử
TID 13: 1 5 4 1 => L.
Thuật toán PCAR sử dụng luật UID 3:
NA NA NA => R để dự đoán dẫn đến
dự đoán sai.
Thuật toán DPCAR xác định được các
luật UID 3 (lớp R), UID 4 (lớp L), UID 6
(lớp L), UID 9 (lớp R) có thể dự đốn
được; xét số lượng thì cả hai nhóm đều có

hai luật nên ta tính HM của hai nhóm này:
Nhóm R:
Luật UID 3:
𝐻𝑀 =

(2×0.7741×0.7838)
(0.7741+0.7838)

= 0.77892

Luật UID 9:
𝐻𝑀 =

3.3. Ví dụ minh họa
Chọn tập dữ liệu Balance được lấy từ
bộ dữ liệu chuẩn UCI, gồm 625 giao dịch,
4 thuộc tính (Left Weight, Left Distance,
Right Weight, Right Distance) phân vào 3

(2×0.4985×0.6207)
(0.4985+0.6207)

= 0.55293

Nhóm L:
Luật UID 4:
𝐻𝑀 =
31

(2×0.7424×0.7477)

(0.7424+0.7477)

= 0.745


SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY

No. 77 (06/2021)

Luật UID 6:
𝐻𝑀 =

(2×0.7014×0.7043)
(0.7014+0.7043)

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

= 0.7028

Vì AHM (L) = 0.7239 > AHM(R) =
0.6659 nên chọn lớp L để dự đoán, suy ra

dự đoán đúng.
Tương tự như hai trường hợp trên,
trong khi thuật toán PCAR dự đốn đúng
được 49/63 (77.78%) mẫu thì thuật tốn
DPCAR dự đốn đúng tổng cộng 60/63
(95.23%) mẫu bao gồm 37 mẫu đúng
dùng Dominant Class, 14 mẫu đúng dùng
Average Harmonic Mean và 9 mẫu đúng
dùng luật đầu tiên tìm được, tăng 17.45%
so với thuật toán PCAR.
Bảng 2. Dữ liệu kiểm thử từ Balance
TID
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

19
20
21
22
23

LW
2
5
3
5
2
5
3
1
4
2
1
1
1
2
2
2
3
4
2
3
4
3
3


LD
4
2
3
2
4
2
1
2
3
2
2
2
5
3
2
4
2
3
1
2
2
4
4

RW
3
4
2

1
5
2
2
1
2
4
1
5
4
2
1
3
1
1
1
2
1
5
3

RD
4
1
5
3
3
3
2
3

2
3
4
2
1
4
3
1
1
4
4
2
3
1
1

Lớp
R
L
R
L
R
L
R
R
L
R
R
R
L

R
L
L
L
L
R
L
L
L
L

32

4
5
1
2
1
1
3
5
3
5
2
1
3
1
2
4
2

5
1
4
4
2
5
4
5
4
1
3
1
4
3
4
5
1
2
2
3
4
5
1

4
1
4
4
3
5

1
1
5
3
4
1
5
5
5
1
4
4
2
4
4
4
5
4
4
3
1
1
3
2
4
5
1
2
4
1

5
5
3
2

3
2
2
2
1
1
3
3
1
2
4
1
2
5
5
4
5
3
4
5
5
1
5
5
3

1
5
2
5
4
5
5
4
3
5
3
1
4
5
2

1
4
1
1
5
1
3
1
2
1
4
2
1
2

5
4
1
2
4
1
2
1
4
3
4
3
5
1
3
1
4
5
4
3
2
2
4
3
2
4

L
R
L

L
R
L
R
L
L
L
R
R
L
R
R
R
L
L
R
L
L
L
L
L
L
L
R
L
R
L
R
R
R

R
R
R
L
L
L
R


NGUYỄN ANH TÚ

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

Bảng 3. Tập URS khai thác bằng PCAR, k = 5, minsupp = 0.05, minconf = 0.4
UID LW

LD

RW

RD

Lớp

PR

Conf

Supp


0.8

Số phần Tần suất xuất
tử vế trái
hiện lớp

1

NA

NA

1

NA

L

0.8033

0.1566

1

50

2

NA


1

NA

NA

R

0.7825 0.7807 0.1584

1

50

3

1

NA

NA

NA

R

0.7741 0.7838 0.1548

1


50

4

NA

NA

NA

1

L

0.7424 0.7477 0.1423

1

50

5

NA

NA

5

NA


R

0.7163 0.7248 0.1406

1

50

6

NA

5

NA

NA

L

0.7014 0.7043 0.1441

1

50

7

NA


NA

NA

5

R

0.6856 0.6917 0.1477

1

50

8

5

NA

NA

NA

L

0.5432 0.693 0.1406

1


50

9

NA

NA

4

NA

R

0.4985 0.6207 0.1281

1

50

10

NA

NA

NA

2


L

0.413 0.5752 0.1157

1

46

11

NA

4

NA

NA

L

0.4092 0.5981 0.1139

1

50

12

4


NA

NA

NA

L

0.3884 0.5929 0.1192

1

50

13

NA

NA

NA

4

R

0.3802

0.1174


1

56

14

NA

2

NA

NA

R

0.3721 0.5818 0.1139

1

50

15

2

NA

NA


NA

R

0.2526 0.5586 0.1103

1

55

16

NA

NA

2

NA

L

0.2414 0.5625 0.1121

1

48

17


NA

3

NA

NA

L

0.1625

0.1032

1

50

18

3

NA

NA

NA

L


0.13

0.4867 0.0979

1

48

19

NA

NA

NA

3

L

0.1154 0.4107 0.0819

1

50

20

NA


NA

NA

3

R

0.1077 0.5089 0.1014

1

47

4. Cài đặt thực nghiệm và kết quả
4.1. Môi trường và dữ liệu thực nghiệm
Nghiên cứu này cài đặt thực nghiệm
trên 14 tập dữ liệu chuẩn UCI [11] như
bảng 4. Các thí nghiệm được tiến hành trên
máy tính cá nhân hệ điều hành Windows
10 (64-bit), cấu hình @Intel CPU core i7
2.60 GHz và RAM 8GB. Bên cạnh việc so
sánh với thuật toán PCAR [10] để chứng
minh sự cải thiện độ chính xác, nghiên cứu

0.6

0.5

này còn chạy thử nghiệm trên cùng các tập

dữ liệu bằng các thuật toán C4.5 [5],
RIPPER [12], CBA [4], MCAR [9] để so
sánh. Các thuật toán C4.5, RIPPER, CBA
được chạy bằng phần mềm WEKA [13];
MCAR, PCAR, PCAR2 (là một phiên bản
của PCAR nhưng ở giai đoạn tính tỷ lệ dự
đốn và xếp hạng, nhóm tác giả chỉ sử
dụng inner testing set thay vì sử dụng thêm
inner training set như PCAR) chạy bằng
33


SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY

No. 77 (06/2021)

ngôn ngữ R do nhóm tác giả Song và Lee
[10] cung cấp và thuật toán đề xuất
DPCAR chạy trên Java. Bài viết này vẫn
bảo đảm thiết lập các cài đặt giống như các
hướng tiếp cận trước, ở giai đoạn tiền xử lý
dữ liệu, những thuộc tính khơng có ý nghĩa

trong mơ hình (ví dụ: ID, tên v.v.) sẽ bị lọc
bỏ, các thuộc tính có giá trị liên tục sẽ
được rời rạc hóa; ở giai đoạn sinh luật
vẫn chọn minsupp = 0.05, minconf = 0.4
và k = 5 ở giai đoạn tính tỷ lệ dự đoán và
đánh giá luật.


Bảng 4. 14 tập dữ liệu mẫu UCI trong thực nghiệm
Tập dữ liệu

Số giao dịch Số thuộc tính

Số lớp

Phân bố lớp (%)

Balance

625

4

3

(7.84, 46.08, 46.08)

Balloon

20

4

2

(60, 40)

Breast Cancer Coimbra


116

10

2

(44.83, 55.17)

Breast Tissue

106

9

6

(19.81, 14.15, 16.98,
15.09, 13.21, 20.76)

Crx

690

9

2

(44.49, 55.51)


Cryotherapy

90

7

2

(46.47, 53.33)

Glass

214

10

7

(32.71, 35.52, 7.94, 6.07,
4.21, 13.55)

Iris

150

4

3

(33.33, 33.33, 33.33)


Led7

3200

7

10

(10.15, 10.41, 9.96, 8.44,
10.5, 10.47, 10.66, 9.5,
10.22, 9.69)

Lenses

24

4

3

(16.67, 20.83, 62.5)

Pima

768

8

2


(65.1, 34.9)

Seeds

210

7

3

(33.33, 33.33, 33.33)

Thyroid-new

215

5

3

(69.77, 16.28, 13.95)

Wine

178

13

3


(33.14, 39.89, 26.97)

độ chính xác so với các thuật tốn được so
sánh. Tỷ lệ thắng - thua - hòa (won – loss
- tied) của DPCAR so với C4.5, RIPPER,
CBA, MCAR và PCAR lần lượt là 9-4-1,
10-3-1, 8-4-2, 8-4-2, và 8-3-3; của
DPCAR2 so với C4.5, RIPPER, CBA,
MCAR và PCAR2 là 9-4-1, 12-1-1, 8-4-2,
8-3-3, và 9-2-3. Xét trên 14 tập dữ liệu, độ
chính xác trung bình của thuật tốn

4.2. Kết quả
Kết quả thực nghiệm ở bảng 5 thể
hiện độ chính xác khi chạy các thuật toán
sử dụng kỹ thuật kiểm tra chéo (k-fold
Cross Validation) với k = 10 trên 14 tập
dữ liệu mẫu, các giá trị in đậm thể hiện độ
chính xác cao nhất của thuật tốn tương
ứng cho từng tập dữ liệu. Nhìn chung,
thuật toán đề xuất của bài viết vượt trội về
34


NGUYỄN ANH TÚ

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

DPCAR và DPCAR2 đã cải thiện khoảng

1.31% và 1.93% tương ứng so với thuật
toán PCAR và PCAR2, đặc biệt đối với

các tập dữ liệu có sự chênh lệch trong
phân bố lớp như Balance, Glass, Lenses,
Pima, Thydroid-new, Wine.

Bảng 5. Độ chính xác (%) của C4.5, RIPPER, CBA, MCAR, PCAR, PCAR2,
DPCAR, DPCAR2 áp dụng kỹ thuật 10-fold cross validation
Tập dữ liệu

C4.5 RIPPER CBA MCAR PCAR DPCAR PCAR2 DPCAR2

Balance

76.64

80.32

71.52

76.31

77.28

87.52

77.91

87.66


Balloon

100

100

100

100

100

100

100

100

69.81

63.21

69.81

64.27

68.91

73.55


72.64

69.91

Breast Cancer
Coimbra
68.10

70.69

72.41

71.67

72.50

73.41

65.46

73.03

Crx

86.09

85.36

85.80


85.07

85.22

83.19

84.93

85.65

Cryotherapy

85.56

83.33

91.11

91.11

91.11

91.11

90.00

91.11

Glass


66.82

66.82

68.22

68.18

64.31

68.03

65.45

67.27

Iris

96.00

94.67

94.00

92.67

94.00

93.33


92.67

92.67

Led7

73.18

69.35

71.78

71.78

73.50

72.97

72.91

72.41

Lenses

83.33

75.00

66.67


68.33

70.00

70.00

71.67

76.67

Pima

73.83

75.13

77.47

77.74

75.39

75.40

73.94

76.69

Seed


90.48

91.43

92.38

90.95

92.38

92.86

93.33

93.33

Thyroid-new

92.09

92.56

93.02

95.37

94.00

94.94


92.99

93.94

Wine

93.82

94.94

96.07

97.75

97.22

97.78

97.78

98.33

Trung bình

82.55

81.63

82.16


82.23

82.56

83.86

82.26

84.19

Breast Tissue

Bên cạnh độ chính xác, một số thơng
số tác động đến hiệu suất của mơ hình dự
đốn như độ nhạy (sensitivity), độ đặc hiệu
(specificity), khả năng xác định (precision),
F1 (trung bình điều hịa giữa precision và
sensitivity) và diện tích dưới AUC (area
under the curve) của đường biểu diễn ROC
(Receiver operating characteristic) trên 3
tập dữ liệu về y khoa là Breast Cancer
Coimbra, Cryotherapy và Pima cũng được
nghiên cứu.
Các chỉ số trên thường được ứng

dụng rộng rãi trong máy học (machine
learning), phân lớp nhị phân (Binary
classification), được tính theo cơng thức
(4), cơng thức (5), cơng thức (6) và công

thức (7) dựa trên ma trận chéo phân phối
tần số 2 chiều như bảng 6.
𝑇𝑃

𝑆𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 = 𝑅𝑒𝑐𝑎𝑙𝑙 = 𝑇𝑃+𝐹𝑁 (4)
𝑇𝑁

𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 = 𝑇𝑁+𝐹𝑃

(5)

𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 𝑇𝑃+𝐹𝑃

(6)

𝐹1 =

(7)

𝑇𝑃

35

2∗𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛∗𝑅𝑒𝑐𝑎𝑙𝑙
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛+𝑅𝑒𝑐𝑎𝑙𝑙


SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY

No. 77 (06/2021)


Bảng 7, bảng 8, bảng 9 thể hiện sự cải
thiện về hiệu suất và hình 2, hình 3, hình 4,
hình 5, hình 6, hình 7 lần lượt là đường
biểu diễn ROC khi so sánh giữa thuật toán
DPCAR với PCAR, DPCAR2 với PCAR2
trên 3 tập dữ liệu tương ứng Breast Cancer
Coimbra, Cryotherapy và Pima.

Bảng 6. Confusion Matrix
Lớp
Dự đoán

Thực tế

Lớp thực tế
(Possitive)

Lớp khác
(Negative)

TP

FN

FP

TN

Bảng 7. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ

liệu Breast Cancer Coimbra
PCAR

DPCAR

PCAR2

DPCAR2

Sensitivity

58.21

71.5

50.1

72.24

Specificity

83.12

72.67

81.69

71.67

Precision


72.67

84.12

66.26

82.15

F1

63.43

75.33

51.11

76.17

AUC

70.67

72.09

65.9

71.96

Bảng 8. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ

liệu Cryotherapy
PCAR

DPCAR

PCAR2

DPCAR2

Sensitivity

93

92.62

93.24

89.67

Specificity

88.17

95.14

89.07

92.74

Precision


92.62

93

87.67

93.24

F1

91.15

91.15

88.79

89.9

AUC

90.59

93.88

91.16

91.21

Bảng 9. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ

liệu Pima
PCAR

DPCAR

PCAR2

DPCAR2

Sensitivity

49.04

63.72

41.56

66.61

Specificity

89.95

81.96

91.23

81.59

Precision


72.52

66.91

73

65.31

F1

57.47

64.82

51

65.54

AUC

69.5

72.79

66.4

74.1

36



NGUYỄN ANH TÚ

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

Hình 2. Đường biểu diễn ROC của PCAR
và DPCAR trên tập dữ liệu Breast Cancer
Coimbra

Hình 5. Đường biểu diễn ROC của PCAR2
và DPCAR2 trên tập dữ liệu Cryotherapy

Hình 3. Đường biểu diễn ROC của PCAR2
và DPCAR2 trên tập dữ liệu Breast Cancer
Coimbra

Hình 6. Đường biểu diễn ROC của PCAR
và DPCAR trên tập dữ liệu Pima

Hình 4. Đường biểu diễn ROC của PCAR
và DPCAR trên tập dữ liệu Cryotherapy

Hình 7. Đường biểu diễn ROC của PCAR2
và DPCAR2 trên tập dữ liệu Pima
37


SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY


No. 77 (06/2021)

cân bằng về lớp. Do phương pháp đề xuất
mang lại hiệu quả cao về độ chính xác so
với các phương pháp giải quyết bài tốn ra
quyết định trước đây nên nó cũng có thể áp
dụng tốt cho các bài toán khác như phân
lớp, nhận diện mẫu trong dữ liệu chuỗi tuần
tự và dữ liệu chuỗi thời gian v.v.
Trong tương lai, nghiên cứu này có thể
tiếp tục mở rộng cải tiến xây dựng bộ phân
lớp có tính đa lớp cho dự đốn các tập dữ
liệu đa lớp – là tập dữ liệu chứa các luật mà
một luật có thể thuộc về nhiều lớp. Ngồi
ra, việc áp dụng các kỹ thuật song song
làm tăng tốc độ khai thác đối với những tập
dữ liệu có số lượng thuộc tính cao cũng
được quan tâm.

5. Kết luận
Nghiên cứu này giới thiệu một thuật
toán đưa ra độ đo mới là tỷ lệ dự đoán và đề
xuất một phương pháp cải tiến ở giai đoạn
dự đoán luật của thuật toán trên để tăng
hiệu quả dự đoán của bộ phân lớp khai thác
được. Bằng phương pháp kết hợp việc chọn
lớp có số lượng cao nhất, trung bình cộng
của trung bình điều hịa giữa tỷ lệ dự đốn
và độ tin cậy, trung bình cộng của độ hỗ trợ
của các luật trong bộ phân lớp phủ được

mẫu trong tập dữ liệu kiểm thử đã hạn chế
được việc lạm dụng chọn các luật có tỷ lệ
dự đoán cao hay các luật mặc định nhưng
dự đoán sai, giúp cải thiện được độ chính
xác, đặc biệt đối với tập dữ liệu thực bị mất
TÀI LIỆU THAM KHẢO
[1]

Agrawal, R., & Srikant, R., "Fast algorithms for mining association rules in large
databases", Proceedings of the 20th International Conference on Very Large
Databases, 1994.

[2]

Zaki, M., "Scalable algorithms for association mining", IEEE Transactions on
Knowledge and Data Engineering, vol. 12(3), pp. 372-390, 2000.

[3]

Han, J., Pei, J., Yin, Y., & Mao, R., "Mining frequent patterns without candidate generation:
A frequent-pattern tree approach", Data mining and knowledge discovery, 2004.

[4]

Liu, B., Hsu, W., Ma, Y., "Integrating classification and association rule mining",
Proceedings of the 4th International Conference on Knowledge Discovery and Data
Mining, pp. (80-86), 1998.

[5]


Quinlan, J. R., "C4.5: Programs for Machine Learning", San Mateo: Morgan
Kaufmann, 1993.

[6]

Tolun, M.R., Abu-Soud, S.M., "ILA: An Inductive Learning Algorithm for Rule
Extraction", Expert Systems with Applications, vol. 14(3), pp. 361-370, 1998.

[7]

Li, W., Han, J., & Pei, J., "CMAR: Accurate and efficient classification based on
multiple-class association rule", Proceedings of the 1st IEEE International
Conference on Data Mining, pp. 369-376, 2001.

[8]

Thabtah, F., Cowling, P., & Peng, Y., "MMAC: A new multi-class, multi-label
associative classification approach", Proceedings of the 4th IEEE International
Conference on Data Mining , 2004.
38


NGUYỄN ANH TÚ

[9]

TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GỊN

Thabtah, F., Cowling, P., & Peng, Y., "MCAR: multi-class classification based on
association rule", Proceedings of the 3rd ACS/IEEE International Conference on

Computer Systems and Applications, 2005.

[10] Song, K., Lee, K., "Predictability-based collective class association rule mining",
Expert Syst. Appl., vol. 79, pp. 1-7, 2017.
[11] Dua, D., & Graff, C., "UCI Machine Learning Repository", 2019.
[12] Cohen, W. W., "Fast effective rule induction", Proceedings of the twelfth
international conference on machine learning, pp. 115-123, 1995.
[13] Hall, M., Franks, E., Holmes, G., Pfaringer, B., Reutemann, P., & Witten, I. H., "The
WEKA datamining software: an update", ACM SIGKDD explorations newsletter,
2009.
[14] Al-Tapan, A.A., Al-Maqaleh, B.M., "An effective mining of exception class
association rules from medical datasets", Int. J. Comput. Sci. Eng., vol. 7, pp. 191198, 2017.
[15] Alwidian, J., Hammo, H.B., & Obeid, N., "WCBA: Weighted classification based on
association rules algorithm for breast cancer disease", Appl. Soft Comput., vol. 62, pp.
536-549, 2018.
[16] Nguyen, L.T.T., Nguyen, N.T., "An improved algorithm for mining class association
rules using the difference of Obidsets", Expert Syst, Appl, vol. 42(9), pp. 4361-4369,
2015.
[17] Nguyen L.T.T., Vo B., Mai T., Nguyen TL., "A Weighted Approach for Class
Association Rules", Sieminski A., Kozierkiewicz A., Nunez M., Ha Q. (eds) Modern
Approaches for Intelligent Information and Database Systems. Studies in
Computational Intelligence, Springer, Cham, vol. 769, pp. 213-222, 2018.
[18] Thabtah, Hadi, W., Abdelhamid, N., & Issa, A., "Prediction phase in associative
classification mining",
International Journal of Software Engineering and
Knowledge Engineering, vol. 21, pp. 855-876, 2011.
Ngày nhận bài: 13/2/2020

Biên tập xong: 15/6/2021


39

Duyệt đăng: 20/6/2021