Khai thác luật phân lớp kết hợp trên cơ sở dữ liệu mất cân bằng về lớp

tra tiền tố. Dựa trên cấu trúc 
mới (MECR-tree), CAR-Miner phát triển hai định lý nhằm tỉa sớm các ứng viên không phổ biến và xác định nhanh các 
thông tin của nút con dựa trên thông tin của nút cha. Ngoài ra, Nguyen và các đồng sự cũng sử dụng kỹ thuật diffset để 
khai thác nhanh CARs [7]. Ngoài ra, việc khai thác CARs với ràng buộc [5] và khai thác CARs sử dụng trong dữ liệu 
chứng khoáng [1] cũng đã được đề xuất. 
B. Thuật toán K-means 
Thuật toán K-means do MacQueen đề xuất vào năm 1967 [4]. Thuật toán dựa trên độ đo khoảng cách của các 
đối tượng dữ liệu trong nhóm. Trong thực tế, nó đo khoảng cách đến giá trị trung bình của các dữ liệu trong nhóm, đó 
242 KHAI THÁC LUẬT PHÂN LỚP KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU MẤT CÂN BẰNG VỀ LỚP 
chính là trọng tâm nhóm. Do đó, cần khởi tạo một tập trọng tâm các nhóm ban đầu, thông qua đó lặp lại các bước: gán 
nhãn mỗi đối tượng tới trọng tâm gần nhất và tính lại trọng tâm của mỗi nhóm trên cơ sở gán mới cho các đối tượng. 
Quá trình này dừng lại khi các trọng tâm nhóm hội tụ. K-means là một thuật toán gom nhóm dữ liệu được ứng dụng 
rộng rãi trong cộng đồng khai thác dữ liệu [13]. Đây là một thuật toán được xếp thứ hai trong top 10 thuật toán khai 
thác dữ liệu (được đề cử bởi các nhà khoa học uy tín về khai thác dữ liệu tại hội nghị IEEE ICDM 2006) [14]. 
IV. PHƢƠNG PHÁP ĐỀ XUẤT 
Cách tiếp cận của bài báo được chia làm 2 giai đoạn. 
A. Giai đoạn tạo luật phân lớp dựa trên gom nhóm 
Trong giai đoạn này, tập dữ liệu huấn luyện được chia thành m tập con tương ứng với m lớp có trong CSDL 
huấn luyện. Với mỗi tập con có số mẫu lớn hơn k (với k là số mẫu của tập con chứa ít mẫu nhất), sử dụng thuật toán K-
means để gom các mẫu này thành k nhóm, mỗi nhóm chỉ giữ lại một mẫu đại diện (là phần tử gần trọng tâm nhóm nhất 
chẳng hạn). Như vậy, cuối cùng mỗi tập con sẽ giữ lại k mẫu. Cách tiếp cận này giúp CSDL tổng hợp có số mẫu thuộc 
mỗi lớp là cân bằng và vì vậy, phát huy tốt ưu điểm của các phương pháp khai thác luật phân lớp kết hợp. Các bước 
thực hiện của giai đoạn này được trình bày trong Hình 1. 
a) Các bước thực hiện 
Bước 1: Chia CSDL thành m bảng con tương ứng với m giá trị của thuộc tính lớp. Gọi k là số dòng dữ liệu 
của bảng con có số dòng ít nhất. 
Bước 2: Với mỗi bảng con có số dòng dữ liệu lớn hơn k, tiến hành gom nhóm các dòng dữ liệu trong bảng 
con đó thành k nhóm. Mỗi nhóm chỉ chọn một mẫu đại diện. 
Bước 3: Thực hiện khai thác luật phân lớp kết hợp trên tập dữ liệu tổng hợp từ m nhóm. 
Hình 1. Các bước thực hiện của phương pháp tạo luật phân lớp dựa vào gom nhóm 
Ở bước 2, chúng ta có thể chọn K-means, K-medoids hoặc phương pháp phân cấp để thực hiện. Do K-means là 
thuật toán lặp đơn giản và cũng gom nhóm khá hiệu quả nên trong phạm vi bài báo, chúng tôi sử dụng K-means cho 
bước này. Để chọn mẫu đại diện cho mỗi nhóm, cách đơn giản nhất là chọn phần tử gần trọng tâm của nhóm nhất. 
Ở bước 3, chúng ta có thể sử dụng bất kỳ thuật toán phân lớp kết hợp nào để khai thác luật. Kết quả thực 
nghiệm từ [6] cho thấy CAR-Miner thường hiệu quả hơn so với các thuật toán sinh luật trước đó nên chúng tôi sử dụng 
CAR-Miner cho bước này. Ở bước này, chúng ta có thể sử dụng phương pháp tỉa luật thừa như được sử dụng trong [2] 
hay [13] nhằm giảm thiểu số lượng luật cần xét trong giai đoạn 2. 
b) Ví dụ minh họa 
Bảng 2. Dữ liệu mất cân bằng về lớp (5 mẫu thuộc lớp 0 và 2 mẫu thuộc lớp 1) 
OID A B C D CLASS 
1 5 3 5 4 0 
2 4 1 4 3 0 
3 5 2 4 4 0 
4 6 6 5 4 0 
5 6 3 5 3 0 
6 2 1 2 2 1 
7 4 2 4 3 1 
Bước 1: Đầu tiên chia cơ sở dữ liệu thành 2 bảng con tương ứng với 2 lớp 0 và 1 
Do số dòng dữ liệu chứa lớp 1 là ít nhất (2 dòng) nên k = 2. 
Bước 2: Dùng K-means gom các dòng có lớp là 0 thành 2 cụm. Mỗi cụm rút ra 1 dòng đại diện, ta có kết quả 
như bảng 3 (bên dưới sau khi đã được đánh lại OID). 
Bước 3: Thực hiện khai thác luật phân lớp kết hợp bằng thuật toán CAR-Miner với dữ liệu trong bảng 3. 
Bảng 3. Bảng CSDL phân lớp 
OID’ A B C D CLASS 
1 2 1 2 2 1 
2 4 2 4 3 1 
3 6 6 5 4 0 
4 6 3 5 3 0 
Cây MECR được xây dựng từ CSDL trong bảng 3 như sau: Đầu tiên, nút gốc Lr của cây chứa các nút 1-itemset 
phổ biến như sau: 
Nguyễn Thị Thúy Loan, Trần Thị Minh Thúy, Giang Hào Côn 243 



)0,1(3
48
,
)1,1(24
38
,
)11(0,
28
,
)0,2(34
54
,
)1,0(2
44
,
)11(0,
24
,
,0)14(
32
,
,0)13(
62
,
)12(0,
22
,
 )11(0,
12 
,
,0)234(
61
,
)12(0,
41
,
)11(0,
21
Áp dụng thuật toán CAR-Miner với MinSup = 10% và MinConf = 60% để tính toán cho các itemset. Thủ tục 
CAR-Miner được gọi với tham số Lr 
Áp dụng thủ tục CAR-Miner được gọi với tham số Lr. Nút li = 
)11(0,
21 
 Xét nút lj =
)12(0,
 41 : hai nút li và lj có cùng thuộc tính và khác giá trị nên không kết với nhau. Tương tự các 
nút 
,0)234(
61 cũng không kết với nhau. 
 Xét nút lj = 
 )11(0,
12 : Vì hai nút này khác thuộc tính nhau, nên ba yếu tố được tính lại như sau O.att = li.att  
lj.att = 1 | 2 = 3 hoặc 11 theo biểu diễn bit; O.values = li.values  lj.values = 2  1 = 21 và O.Obidset = li.Obidset  
lj.Obidset = {1}  {1} = {1}. Bởi vì |li.Obidset| = |O.Obidset|, thuật toán sẽ chép thông tin từ li xuống O vì nút O là 
con của nút li. Điều đó có nghĩa rằng O.count = li.count = (0,1) và O.pos = 2. Vì O.count[O.pos] = 1 > MinSup, O được 
thêm vào Pi Pi = 



 )11(0,
213 
 Xét nút lj =
)12(0,
22 : Vì hai nút này khác thuộc tính nhau, nên ba yếu tố được tính lại như sau O.att = li.att  
lj.att = 1 | 2 = 3 hoặc 11 theo biểu diễn bit; O.values = li.values  lj.values = 2  2 = 22, và O.Obidset = li.Obidset  
lj.Obidset = {1}  {2} = {}. Vì O.count[O.pos] = 0 < MinSup, O không được thêm vào Pi. 
 Tương tự 
,0)13(
62 ,
,0)14(
32 Obidset giao nhau ={} do đó không thêm vào Pi. 
 Xét nút lj = 
)11(0,
24
: Vì hai nút này khác thuộc tính nhau, nên ba yếu tố được tính lại như sau O.att = li.att  
lj.att = 1 | 4 = 5 hoặc 101 theo biểu diễn bit; O.values = li.values  lj.values = 2  2 = 22, và O.Obidset = li.Obidset  
lj.Obidset = {1}  {1} = {1}. Bởi vì |li.Obidset| = |O.Obidset|, thuật toán sẽ chép thông tin từ li xuống O(theo định lý 
2.2). Điều đó có nghĩa rằng O.count = li.count = (0,1) và O.pos =2. Vì O.count[O.pos] = 1 ≥ MinSup, O được thêm vào 
Pi Pi = 



)11(0,
225
,
 )11(0,
213 
 Xét 
)1,0(2
44 
)0,2(34
54 Obidset giao nhau ={} do đó không thêm vào Pi 
 Xét nút lj = 
)11(0,
28
: Vì hai nút này khác thuộc tính nhau, nên ba yếu tố được tính lại như sau O.att = li.att  
lj.att = 1 | 8 = 9 hoặc 1001 theo biểu diễn bit; O.values = li.values  lj.values = 2  2 = 22, và O.Obidset = li.Obidset  
lj.Obidset = {1}  {1} = {1 Bởi vì |li.Obidset| = |O.Obidset|, thuật toán sẽ chép thông tin từ li xuống O. Điều đó có 
nghĩa rằng O.count = li.count = (0,1) và O.pos = 2. Vì O.count[O.pos] = 1 ≥ MinSup, O được thêm vào Pi 
 Pi = 



)11(0,
229
,
)11(0,
225
,
 )11(0,
213
 Xét 
)1,1(24
38
)0,1(3
48
 Obidset giao nhau ={} do đó không thêm vào Pi 
 Sau khi Pi được tạo ra, thuật toán CAR-Miner được gọi đệ quy với tham số Pi, MinSup, và MinConf để tạo ra 
các nút con của Pi. Xét việc xử lý để tạo ra các nút con của nút li =
 )11(0,
213 : 
244 KHAI THÁC LUẬT PHÂN LỚP KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU MẤT CÂN BẰNG VỀ LỚP 
o Xét nút lj =
)11(0,
225 : Vì hai nút này khác thuộc tính nhau, nên ba yếu tố được tính lại như sau O.att = li.att  
lj.att = 3 | 5 = 7 hoặc 11 theo biểu diễn bit; O.values = li.values  lj.values = 21  22 = 212, và O.Obidset = 
li.Obidset  lj.Obidset = {1}  {1} = {1} = lj.Obidset. Thuật toán sẽ chép thông tin từ lj xuống O, điều đó 
có nghĩa rằng O.count = lj.count = (0,1) và O.pos = 2. Vì O.count[O.pos] = 1 > MinSup, O được thêm vào Pi’ 
 Pi’ = 



)11(0, 
2217 
o Tương tự cho nút lj =
)11(0, 
229 , ta có kết quả Pi’ =



)11(0, 
21211
,
)11(0, 
2217
o Sau khi Pi được tạo ra, thuật toán CAR-Miner được gọi đệ quy với tham số Pi, MinSup, và MinConf để tạo 
ra các nút con của Pi. Xét việc xử lý để tạo ra các nút con của nút 
li=
)11(0, 
2217 . Ta tính được Pi’’ = 



)11(0, 
222115 
o Tương tự như trên để xét tiếp việc xử lý để tạo ra các nút con của nút li =
)11(0, 
225 và 
)11(0, 
229 
Tương tự cho đến khi thuật toán dừng (không còn nút nào được sinh ra). 
B. Giai đoạn kiểm tra 
Dựa vào các luật đã khai thác được trong giai đoạn 1, chúng tôi tiến hành thử nghiệm trên dữ liệu kiểm tra. Các 
bước cụ thể được trình bày trong Hình 2. 
Định nghĩa 5: Cho hai luật ri và rj, (kí hiệu ri  rj) ri có thứ bậc lớn hơn rj nếu: 
1. Độ tin cậy của ri lớn hơn rj, hoặc 
2. Độ tin cậy của chúng bằng nhau nhưng độ phổ biến của ri lớn hơn rj, hoặc: 
3. Cả độ tin cậy và độ phổ biến như nhau nhưng ri được tạo ra trước rj. 
Bước 1: Sắp xếp các luật theo chiều giảm dần của thứ bậc (Theo định nghĩa 5). 
Bước 2: Với mỗi dòng dữ liệu trong tập kiểm tra, xét lần lượt với tập luật đã được sắp xếp từ trên xuống, tìm 
luật đầu tiên chứa vế trái thỏa mãn điều kiện của dòng dữ liệu và vế phải của luật chính là kết quả dự đoán lớp của 
mẫu này. 
Hình 2. Các bước để dự đoán lớp của các mẫu thuộc dữ liệu kiểm tra 
V. KẾT QUẢ THỰC NGHIỆM 
A. Cơ sở dữ liệu và môi trường thực nghiệm 
Các thuật toán được sử dụng trong phần thực nghiệm đã được cài đặt trên máy tính chạy trên C# 2012 với cấu 
hình máy tính cá nhân như sau: Intel Core i3-350 2.26GHz, 4GB RAM, 320GB. Các CSDL thực nghiệm trong được 
lấy từ website UCI  
Bảng 4. CSDL Dữ liệu thực nghiệm 
Tập dữ liệu Số thuộc tính Số lớp Số mẫu Mô tả 
Breast 10 2 699 
Lớp 0: 458 (65.5%) 
Lớp 1: 241 (34.5%) 
Geman 21 2 1000 
Lớp 0: 700 (70%) 
Lớp 1: 300 (30%) 
Iris 4 3 150 
Lớp 0: 50 (33.33%) 
Lớp 1: 50 (33.33%) 
Lớp 2: 50 (33.33%) 
B. Kết quả thực nghiệm 
Kết quả thực nghiệm được đánh giá trên 3 tập dữ liệu từ bảng 4. Kết quả so sánh độ chính xác, giữa việc dùng 
CAR-Miner và K-means-CAR-Miner. 
Chúng tôi so sánh dữ liệu thực nghiệm trên cả 2 thuật toán sử dụng độ tin cậy cố định MinConf = 60% cho tất cả 
các lần thực nghiệm và độ hỗ trợ thay đổi lần lượt 10%, 5%, 3%, 1%. 
Nguyễn Thị Thúy Loan, Trần Thị Minh Thúy, Giang Hào Côn 245 
Độ chính xác phân lớp trên các CSDL ở bảng 4. Kết quả thực nghiệm so sánh độ chính xác giữa hai phương 
pháp K-means-CAR-Miner và CAR-Miner được trình bày trong các hình từ 3 đến 5. 
Hình 3. So sánh độ chính xác phân lớp giữa K-means-CAR-
Miner và CAR-Miner cho CSDL Breast 
Hình 4. So sánh độ chính xác phân lớp giữa K-means-CAR-
Miner và CAR-Miner cho CSDL German 
Hình 5. So sánh độ chính xác phân lớp giữa K-means-CAR-Miner và CAR-Miner cho CSDL Iris 
Các kết quả từ hình 3 đến hình 5 cho thấy đối với các CSDL mất cân bằng về lớp như Breast và German, K-
means-CAR-Miner có độ chính xác cao hơn CAR-Miner, đặc biệt là đối với các ngưỡng MinSup lớn. Đối với các 
CSDL không mất cân bằng về lớp chẳng hạn CSDL Iris thì hai phương pháp này có độ chính xác như nhau. 
VI. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 
Trong bài báo này chúng tôi đã đề xuất một phương pháp tích hợp giữa gom nhóm và phân lớp để giải quyết bài 
toán phân lớp trên CSDL mất cân bằng về lớp. Đối với các lớp có số mẫu lớn, chúng tôi tiến hành gom chúng thành k 
nhóm (với k là số mẫu của nhóm ít nhất), mỗi nhóm chọn một mẫu đại diện (trong bài báo này, chúng tôi chọn mẫu gần 
trọng tâm nhất). Sau đó, CAR-Miner được sử dụng trên CSDL đã được lấy mẫu nhờ gom nhóm để khai thác luật phân 
lớp kết hợp dùng cho dự đoán lớp của mẫu mới. Kết quả thực nghiệm bước đầu cho thấy phương pháp của chúng tôi 
cho độ chính xác cao hơn so với phương pháp không gom nhóm (sử dụng CAR-Miner trên CSDL gốc). 
Trong tương lai, chúng tôi sẽ tiếp tục thử nghiệm trên nhiều CSDL hơn để đánh giá khả năng ứng dụng của 
phương pháp đề xuất. Ngoài ra, phương pháp này cũng sẽ được áp dụng vào các loại phân lớp khác như cây quyết 
định, ILA, SVM, v.v. 
Lời cảm ơn: Nghiên cứu này được tài trợ bởi Quỹ Phát triển khoa học và công nghệ NTTU trong đề tài mã số 
2016.02.06. 
TÀI LIỆU THAM KHẢO 
[1] Y. W. C. Chien, Y. L. Chen (2010), Mining associative classification rules with stock trading data – A GA-based method. 
Knowledge-Based Systems, vol.23, no.6, pp. 605-614. 
[2] B. Liu, W. Hsu, Y. Ma (1998). Integrating classification and association rule mining. In Proc. of the 4th International 
Conference on Knowledge Discovery and Data Mining, New York, USA, pp. 80-86. 
[3] W. Li, J. Han, J. Pei (2001), CMAR: Accurate and efficient classification based on multiple class-association rules, 1st IEEE 
international conference on Data mining, pp. 369–376. 
[4] J. B. MacQueen (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth 
Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, Califormia, vol.1, 
pp. 281-297. 
70
80
90
100
1 0.5 0.3 0.1
Đ
ộ
 c
h
ín
h
 x
ác
(%
) 
MinSup(%) 
Breast 
K-Means_CAR-Miner
CAR-Miner
0
50
100
1 0.5 0.3 0.1
Đ
ộ
 c
h
ín
h
 x
ác
(%
) 
MinSup(%) 
German 
K-Means_CAR-Miner
CAR-Miner
72
74
76
78
80
82
1 0.5 0.3 0.1
Đ
ộ
 c
h
ín
h
 x
ác
(%
) 
MinSup(%) 
Iris 
K-Means_CAR-Miner
CAR-Miner
246 KHAI THÁC LUẬT PHÂN LỚP KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU MẤT CÂN BẰNG VỀ LỚP 
[5] D. Nguyen, L. T. T. Nguyen, B. Vo, T. P. Hong (2015). A novel method for constrained Class-association rule mining. 
Information Sciences, vol. 320, pp. 107-125. 
[6] L. T. T. Nguyen, B. Vo, T. P. Hong, H. C. Thanh (2013). CAR-Miner: An efficient algorithm for mining class-association 
rules. Expert Systems with Applications, vol.40, no.6, pp. 2305-2311. 
[7] L. T. T. Nguyen, N. T. Nguyen (2015). An improved algorithm for mining class association rules using the difference of 
Obidsets. Expert Systems with Applications, vol.42, no.9, pp. 4361-4369. 
[8] R. Quinlan (1992), C4.5: programs for machine learning, Machine Learning, vol.16, pp. 235-240. 
[9] F. A. Thabtah, P. Cowling, Y. Peng (2004), MMAC: A new multi-class, multi-label associative classification approach, the 4th 
IEEE International Conference on Data mining, pp. 217-224. 
[10] F. Thabtah, P. Cowling, Y. Peng (2005), MCAR: Multi-class classification based on association rule, 3rd ACS/IEEE 
international conference on computer systems and applications, pp. 33–39. 
[11] M. R. Tolun, S. M. Abu-Soud (1998), ILA: an inductive learning algorithm for rule extraction, Expert Systems with 
Applications, vol.14, no.3, pp. 361– 370. 
[12] B. Vo, B. Le (2008), A novel classification algorithm based on association rule mining. In Proc. of the 2008 Pacific Rim 
Knowledge Acquisition Workshop (Held with PRICAI’08), LNAI 5465, vol. 5465, pp. 61-75. 
[13] J. Wu (2012), Advances in K-means clustering: a data mining thinking. Springer Sceience & Business Media, pp. 17-35. 
[14] X. Wu et al. (2008), Top 10 algorithms in data mining. Knowledge and Information Systems, vol.14, no.1, pp. 1-37.