Sử dụng cây quyết định phân lớp dữ liệu mất cân đối

Bảng 4-17: Kết quả tập dữ liệu Contraceptive Method Choice

Classifier

TPR	FPR	AUC
SC4.5	0.225	0.076	0.574
CSC4.5	0.333	0.092	0.621
AUC4.5	TPRmean = 0.661	FPRmean = 0.430	AUCmean = 0.616

Có thể bạn quan tâm!

Xem toàn bộ 81 trang tài liệu này.

Thuật toán AUC4.5 cho kết quả AUCmean = 0.616 thấp hơn chút đỉnh so với thuật toán SC4.5

và CSC4.5. Nhưng với giá trị TPRmean = 0.661 cao hơn rất nhiều nói lên thuật toán AUC4.5 đã phân lớp chính xác hơn trên lớp thiểu số so với thuật toán SC4.5 và CSC4.5, mặc dù kết quả không cao.

Ngoài ra, tập Contraceptive Method Choice giá trị của thuộc tính thuộc loại liên tục. Ảnh hưởng lớn đến quá trình phân lớp. Kết quả kiểm tra có độ lệch chuẩn = 0.02028.

Tic-Tac-Toe Endgame: Thuộc tính rời rạc = 9, tỉ lệ lớp thiểu số = 34.62%.

Bảng 4-18: Bảng kết quả 10 lần test trên tập dữ liệu Tic-Tac-Toe Endgame

Lần test

TPR	FPR	AUC	Phương sai	Độ lệch chuẩn
1	0.745	0.105	0.820
2	0.807	0.104	0.851
3	0.708	0.070	0.819
4	0.779	0.098	0.840
5	0.748	0.101	0.823
6	0.776	0.105	0.835
7	0.794	0.112	0.841
8	0.753	0.097	0.828
9	0.785	0.126	0.829
10	0.764	0.151	0.807
	TPRmean=0.766	FPRmean=0.107	AUCmean=0.829	0.00017	0.01285

Nguồn từ: nghiên cứu của tác giả

Bảng 4-19: Kết quả tập dữ liệu Tic-Tac-Toe Endgame

Classifier

TPR

FPR

AUC

SC4.5

0.631	0.062	0.784
CSC4.5	0.640	0.062	0.789
AUC4.5	TPRmean = 0.766	FPRmean = 0.107	AUCmean = 0.829

Thuật toán AUC4.5 cho kết quả phân loại tốt hơn trong cả 3 chỉ số TPR, FPR và AUC trên tập dữ liệu mất cân đối. Lại một nữa khẳng định, tập dữ liệu với thuộc tính có giá trị kiểu rời rạc, cho kết quả phân lớp tốt hơn thuộc tính có giá trị kiểu liên tục. Độ lệch chuẩn = 0.01285 khá nhỏ.

4.5 Đánh giá kết quả thực nghiệm

Qua kết quả thực nghiệm, phân tích trên tám tập dữ liệu đã được kiểm tra trên tập DTest 10 lần

và lấy kết quả trung bình cho các chỉ số TPRmean, FPRmean và AUCmean (bảng V) và chỉ số phương sai – độ lệch chuẩn (bảng IV) có những nhận xét sau:

+ Tỉ lệ mất cân đối giữa các lớp không ảnh hưởng lớn đến kết quả phân lớp của thuật toán đề xuất AUC4.5.

+ Đối với tập dữ liệu với thuộc tính có giá trị rời rạc:

- Cho kết quả phân lớp tốt ở lớp thiểu số trên tập dữ liệu mất cân đối.

- Trong đó, tất cả các tập dữ liệu đều cho kết quả phân loại tốt, vượt trội so với hai thuật toán SC4.5 và CSC4.5. Đặc biệt tập dữ liệu Car Evaluation và Mushroom có kết quả phân lớp chính xác 100%.

- Độ lệch chuẩn của hai tập Car Evaluation và Mushroom bằng không (=0). Còn độ lệch của hai tập Nursery và Tac-Tic-Toe Endgame không lớn, chứng tỏ tính ổn định thuật toán cũng như dữ liệu thuộc nhóm có giá trị kiểu rời rạc.

+ Đối với tập dữ liệu với thuộc tính có giá trị liên tục:

- Chỉ có tập dữ liệu Ecoli có kết quả phân loại cao hơn so với hai thuật toán SC4.5 và CSC4.5. Tuy nhiên độ lệch chuẩn của tập Ecoli khá cao, chỉ đứng sau tập Wine Quality

– Red, chứng tỏ cần xem lại dữ liệu loại liên tục.

- Ba tập dữ liệu còn lại Wine Quality – Red, Wine Quality – White và Contraceptive Method Choice thì chỉ số TPRmean cao hơn so với thuật toán SC4.5 và CSC4.5. Nếu bỏ qua chỉ số FPRmean (phân loại lớp đa số nhầm vào lớp thiểu số) để đạt kết quả AUCmean

cao thì thuật toán AUC4.5 đã đạt được mục đích là nâng cao độ chính xác phân lớp của

lớp thiểu số trong tập dữ liệu mất cân đối.

- Độ lệch chuẩn của tất cả bốn tập dữ liệu loại liên tục đứng cao nhất trong tám tập dữ liệu. theo thứ tự 0.02028, 0.02631, 0.03022 và 0.09520. Cho thấy sự ổn định, sự phân bố dữ liệu trong tập dữ liệu liên tục là vấn đề cần xem xét.

CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Trong luận văn này, thuật toán AUC4.5 được cải tiến từ thuật C4.5 dùng giá trị AUC thay cho Gain-entropy trong tiêu chí tách và cắt tỉa cây nhằm nâng cao hiệu quả phân lớp dữ liệu mất cân đối, cụ thể trên lớp thiểu số, thích hợp cho phân lớp mất cân đối nhị phân. Các kết quả thực nghiệm đánh giá trên tám tập dữ liệu mất cân đối thực từ kho học máy UCI [28] đã chỉ ra rằng thuật toán cải tiến AUC4.5 cho hiệu quả phân lớp tốt hơn thuật toán SC4.5 và SCS4.5. Điều này khẳng định tầm quan trọng khi dùng trực tiếp giá trị AUC vào việc huấn luyện trong tập dữ liệu có ảnh hưởng tới quá trình phân lớp. Đặc biệt, phương pháp cải tiến không hy sinh giá trị FPR nhằm gia tăng giá trị TPR để đạt giá trị AUC cao nhất.

Phương pháp đề xuất không cần cài đặt các chi phí khác nhau như chi phí phân loại sai như trong phương pháp học với chi phí nhạy cảm, cho nên thời gian huấn luyện ít hơn nhưng hiệu quả phân lớp tốt hơn.

Phương pháp cải thiện được tỷ lệ phân loại chính xác trên lớp thiểu số trong tập dữ liệu mất cân đối. Tuy nhiên dữ liệu có giá trị kiểu liên tục cũng là vấn đề cần quan tâm và xử lý trước khi đưa vào phân loại khi áp dụng trên thuật toán AUC4.5.

Với những kết quả đạt được của thuật toán. Nếu áp dụng hệ thống vào ứng dụng chẩn đoán y học sẽ nâng cao hiệu quả chẩn đoán, nếu áp dụng vào lĩnh vực phát hiện xâm nhập, tấn công sẽ năng cao hiệu quả giám sát hệ thống. Tuy nhiên, hiện nay, chưa có một phương pháp nào tối ưu hơn hẳn cho tất cả các tập dữ liệu thực tế và trong ngành khai thác dữ liệu thì đều chấp nhận điều này. Trên cơ sở nghiên cứu và các kết quả đạt được, chúng tôi nhận thấy có nhiều vấn đề cần được tiếp tục nghiên cứu và phát triển để đóng góp vào lĩnh vực phân lớp dữ liệu mất cân đối nói riêng và lĩnh vực khai thác dữ liệu nói chung.

TÀI LIỆU THAM KHẢO

[1] J. R. Quinlan, “Induction of Decision Trees,” Mach. Learn., vol. 1, no. 1, pp. 81–106, 1986.

[2] J. Han, M. Kamber, and J. Pei, Data mining : Concepts and Techniques. Elsevier/Morgan Kaufmann, 2012.

[3] I. H. Witten, E. Frank, and M. a. Hall, Data Mining: Practical Machine Learning Tools and Techniques, Third Edition, vol. 54, no. 2. 2011.

[4] V. Ganganwar, “An overview of classification algorithms for imbalanced datasets,” Int.

J. Emerg. Technol. Adv. Eng., vol. 2, no. 4, pp. 42–47, 2012.

[5] Y. Yang and G. Ma, “Ensemble-based active learning for class imbalance problem,” J. Biomed. Sci. Eng., vol. 03, no. 10, pp. 1022–1029, Oct. 2010.

[6] B. Zadrozny, J. Langford, and N. Abe, “Cost-sensitive learning by cost-proportionate example weighting,” in Third IEEE Int. Conf. on Data Mining, 2003, pp. 435–442.

[7] Y. Tang, S. Krasser, D. Alperovitch, and P. Judge, “Spam Sender Detection with Classification Modeling on Highly Imbalanced Mail Server Behavior Data,” in Proc. of Intl. Conf. on Artificial Int. and Pattern Recognition, 2008, pp. 174–180.

[8] V. Engen, “Machine learning for network based intrusion detection.,” Bounemouth University, 2010.

[9] X. Liu, J. Wu, and Z. Zhou, “Exploratory Under-Sampling for Class-Imbalance Learning,” in Sixth Int. Conf. on Data Mining (ICDM’06), 2006, pp. 965–969.

[10] S.-J. Yen and Y.-S. Lee, “Cluster-based under-sampling approaches for imbalanced data distributions,” Expt. Syst. with Appl., vol. 36, no. 3, pp. 5718–5727, Apr. 2009.

[11] N. M. Phương, T. T. Ánh Tuyết, N. T. Hồng, and Đ. X. Thọ, “Random Border Undersampling: Thuật toán mới giảm phần tử ngẫu nhiên trên đường biên trong dữ liệu mất cân bằng,” in FAIR - Nghiên cứu cơ bản và ứng dụng CNTT, 2015.

[12] N. Japkowicz, “Learning from Imbalanced Data Sets: A Comparison of Various Strategies,” AAAI wsh. Learn. from imb. data sets, vol. 68, pp. 10–15, 2000.

[13] N. V Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “SMOTE: Synthetic Minority Over-sampling Technique,” J. Artif. Intell. Res., vol. 16, pp. 321–357, 2002.

[14] H. Han, W.-Y. Wang, and B.-H. Mao, “Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning,” Springer, Berlin, Heidelberg, 2005, pp. 878– 887.

[15] G. Weiss, K. McCarthy, and B. Zabar, “Cost-sensitive learning vs. sampling: Which is best for handling unbalanced classes with unequal error costs?,” Dmin, pp. 1–7, 2007.

[16] C. Drummond and R. C. Holte, “Exploiting the Cost(In)sensitivity of Decisions Tree Splitting Criteria,” Int. Conf. Mach. Learn., vol. 1, no. 1, pp. 239–246, 2000.

[17] W. Fan, S. Stolfo, J. Zhang, and P. Chan, “AdaCost: Misclassification Cost-Sensitive Boosting,” ’99 Proc. Sixt. Intl. Conf. Mach. Learn., pp. 97–105, 1999.

[18] Y. Sun, M. S. Kamel, A. K. C. Wong, and Y. Wang, “Cost-sensitive boosting for classification of imb. data,” Patt. Recog., vol. 40, no. 12, pp. 3358–3378, 2007.

[19] H. Guo and H. L. Viktor, “Learning from Imbalanced Data Sets with Boosting and Data Generation : The DataBoost-IM Approach,” ACM SIGKD Explor. Newsl. - Spec. issue Learn. from imb. datasets, vol. 6, no. 1, pp. 30–39, 2004.

[20] M. a Maloof, “Learning When Data Sets are Imbalanced and When Costs are Unequal and Unknown,” Analysis, vol. 21, no. Ii, pp. 1263–1284, 2003.

[21] J. R. Quinlan, “J. Ross Quinlan. C4.5 - Programs for Machine Learning,” Morgan Kaufmann, vol. 5, no. 3. p. 302, 1993.

[22] T. Fawcett, “An introduction to ROC analysis,” Pattern Recognit. Lett., vol. 27, no. 8, pp. 861–874, 2006.

[23] M. R. Tolun and S. M. Abu-Soud, “An Inductive Learning Algorithm for Production Rule Discovery,” 1999.

[24] P. T. Huấn and L. H. Bắc, “Khai thác tập phổ biến từ dữ liệu giao dịch với nhiều ngưỡng phổ biến tối thiểu trên bộ xử lý đa nhân,” Can Tho Univ. J. Sci., vol. CN, p. 155, Oct. 2017.

[25] A. Tran, T. Truong, and L. H. Bac, “Efficiently mining ass. rules based on max. single constraints,” Vietnam J. Comp. Sci., vol. 4, no. 4, pp. 261–277, Nov. 2017.

[26] D. Nguyen, B. Vo, and L. H. Bac, “CCAR: An efficient method for mining class association rules with itemset constraints,” Eng. Appl. Artif. Intell., vol. 37, pp. 115–124, Jan. 2015.

[27] S. M. A.-S. Mehmet R. Tolun, Hayri Sever, Mahmu, Hayri Sever, Mahmut Uludag, “ILA-2: An Inductive Learning Algorithm For Knowledge Discovery,” Cybern. Syst., vol. 30, no. 7, pp. 609–628, Oct. 1999.

[28] C. L. Blake and C. J. Merz, “UCI Repository of machine learning databases,” Univ. Calif., p. http://archive.ics.uci.edu/ml/, 1998.

[29] J.-S. Lee, J. Lee, and B. Gu, “AUC-based C4.5 decision tree algorithm for imbalanced data classification”, 2016.