استفاده از ارتباطات بین برچسب‌ها در ایجاد زنجیره رده‌بندها برای بهبود رده‌بندی چندبرچسبی

نویسندگان

تهران - دانشگاه تربیت دبیر شهیدرجایی - دانشکده مهندسی کامپیوتر

چکیده

در این مقاله، با فرض وجود ارتباطات معنادار بین برچسب‌ها در مسائل چندبرچسبی، دو روش جدید برای بهبود روش پایه زنجیره رده‌بندها (CC) در رده‌بندی چندبرچسبی پیشنهاد شده است. در این مقاله، برای اولین‌بار از قوانین انجمنی برای تعیین ترتیب رده‌بندها در روش CC استفاده شده است. در روش‌های پیشنهادی این مقاله، ابتدا از قوانین انجمنی برای مدل‌سازی ارتباطات بین برچسب‌ها استفاده می‌شود و سپس با استفاده از قوانین انجمنی استخراج‌شده، یک گراف ارتباط ساخته می‌شود و درنهایت، این گراف مبنای تعیین ترتیب زنجیره رده‌بندها قرار می‌گیرد. از آن‌جا که در مسائل واقعی چندبرچسبی مانند رده‌بندی متون، تصاویر و کاربردهای پزشکی ارتباطات معناداری بین برچسب‌ها وجود دارد، روش‌های پیشنهادی به بهبود رده‌بندی در این حوزه‌ها منجر خواهد شد. آزمایش‌های تجربی گسترده انجام‌شده روی مجموعه داده‌های استاندارد و رایج در حوزه رده‌بندی چندبرچسبی نشان می‌دهند، استفاده از ارتباطات بین برچسب‌ها در ساخت زنجیره رده‌بندها باعث بهبود معیارهای مهم ارزیابی در رده‌بندی مبتنی بر زنجیره رده‌بندها می‌شود.

کلیدواژه‌ها


عنوان مقاله [English]

To Use the Relationships between Class Labels in Creating Classifier Chains to Improve Multi-label Classification

نویسندگان [English]

  • K. Ghafouri pour
  • Z. Mirzamomen
School of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
چکیده [English]

In this paper, we have supposed that there is meaningful relationships between the class labels in the multi-label classification problems and based on it, we have proposed two novel methods to improve the base classifier chains (CC) method for multilabel classification. In this paper, association rules are employed to determine the order of classifiers in the CC method for the first time. In the proposed methods, association rule mining is first employed to model the relationships between the class labels and then, an association graph is built based on the extracted rules and finally, the classifier chains is built based on the obtained graph. As there is meaningful relationships between the class labels in the real multi-label problems such as classifying the images and texts and medical applications, the proposed methods will improve the classification results in such contexts. Extensive experimental evaluations conducted on the benchmark datasets in the multi-label classification context show that to use the associations between the labels in constructing the classifier chains improves the results obtained by the main evaluation measures.

کلیدواژه‌ها [English]

  • Multi-label classification
  • relationship between labels
  • Association rules
  • classifier chains
[1] محمدعلی زارع چاهوکی  و  حمیدرضا محمدی، "بهینه‌سازی هسته‌های چندگانه در ماشین‌بردارپشتیبان جفتی برای کاهش شکاف معنایی تشخیص صفحات فریب‌آمیز"، مجله مهندسی برق دانشگاه تبریز،  دوره 46، شماره 4، زمستان 1395، صفحه 135-145
[2] ندا خانبانی، امیرمسعود افتخاری مقدم، "ارائه یک روش تشخیص زبان علامت مبتنی بر رویکرد MLRF فازی با استفاده از اطلاعات عمق تصویر"، مجله مهندسی برق دانشگاه تبریز، انتشار آنلاین از تاریخ 13 اسفند 1395
[3] J. Read, B. Pfahringer, G. Holmes, and E. Frank, "Classifier chains for multi-label classification", Springer, Mach Learn Vol 85. pp 333–359, 2011.
[4] M. Zhang and Z. Zhi-Hua, "A Review on Multi-Label Learning Algorithms", IEEE Transactions on Knowledge and Data Engineering, Vol. 26, Issue 8, 2013.
[5] W. Bi, J. Kwok, "Multi-Label Classification on Tree- and DAG-Structured Hierarchies", Appearing in Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, USA, 2011.
[6] J. Han, J. Pei , and M.Kamber, Data Mining concepts and techniques, Elsevier third Edition Book, pp. 243-278, 2012.
[7] R. Agrawal and R. Srikant, Fast Algorithms for mining Association Rules in Large Databases, 20th International Conference on Very Large Data Bases, pp. 478-499, 1998.
[8] J. Read, B. Pfahringer, G. Holmes, and E. Frank, "Classifier Chains for Multi-label Classification", Springer-Verlag Berlin Heidelberg, LNAI. 5782, pp. 254–269, 2009.
[9] L. S. Enrique, C. Bielza, E. F. Morales, P. Hernandez-Leal, J. H. Zaragoza, and P. Larrañaga, "Multi-label classification with Bayesian network-based chain classifiers", ELSEVIER, Pattern Recognition Letters Vol. 41, pp. 14–22, 2014.
[10] K. Dembczy´nski, W. Cheng, and E. H¨ullermeier, "Bayes Optimal Multilabel Classification via Probabilistic Classifier Chains", 27 th International Conference on Machine Learning, Haifa, 2010.
[11] J. Read, L. Martino, P. M. Olmos, and D. Luengo, "SCALABLE MULTI-OUTPUT LABEL PREDICTION: FROM CLASSIFIER CHAINS TO CLASSIFIER TRELLISES", arXiv: 1501.04870v1 [stat.ML], 2015.
[12] T. Kajdanowicz and P. Kazienko, "Heuristic Classifier Chains for Multi-label Classification", Springer-Verlag Berlin Heidelberg FQAS, LNAI. 8132, pp. 555–566, 2013.
[13] E. A. Cherman, C. M. Maria, and M. Jean, "Multi-label Problem Transformation Methods: a Case Study", CLEI ELECTRONIC JOURNAL, Vol. 14, pp. 4 -14, 2011.
[14] J. Read, B. Pfahringer, and G. Holmes, "Multi-label Classification using Ensembles of Pruned Sets", 8th IEEE International Conference on Data Mining, 2008.
[15] M. Zhang and Z. Zhi-Hua, "ML-KNN:Alazy learning approach to multi-label learning",  ELSEVIER, Pattern Recognition Vol. 40, pp. 2038 – 2048, 2007.
[16] C. Vens, J. Struyf, L. Schietgat, S. Džeroski, and H. Blockeel, "Decision trees for hierarchical multi-label classification", Springer, Mach Learn Vol. 73, pp. 185–214, 2008.
[17] J. Read and F. Perez-Cruz, "Deep Learning for Multi-label Classification", arXiv:1502.05988v1 [cs.LG], 2014.
[18] L. E. Menc´ıa and J. F¨urnkranz, "Pairwise Learning of Multilabel Classifications with Perceptrons",  IEEE  978-1-4244-1821-3/08, 2008.
[19] G. Tsoumakas, I. Katakis, and I. Vlahavas, "Random k-Labelsets for Multilabel Classification", IEEE Transactions on Knowledge and Data Engineering Vol. 23, NO. 7, 2011.
[20] Sh. Wang, J. Wang, Z. Wang, Q. and Ji, "Enhancing multi-label classification by modeling dependencies among lables", Elsevier, Pattern Recognition Vol. 47, pp. 3405-3413, 2014.
[21] F. Charte, A. Rivera, J.M. Jesus, and F. Herrera, "Improving Multi-label classifiers via Label Reduction with Association Rules", Springer-Verlag Berlin Heidelberg HAIS part II, LNCS 7209, pp. 188-199, 2012.
[22] R. Alazaidah, F. Thabtah, and Q. Al-Raaidehi, "A Multi-Label Classification Approach Based on Correlations Among Labels", International Journal of Advanced Computer Science and Applications Vol. 6, No. 2, pp.  52-59, 2015.
[23] K. Patel, N. Kapadia, and M. Parikh, "Discover Multi-label Classification using Association Rule Mining", International journal of  Advance Engineering and  Research Development, Vol. 1, Issue. 1, ISSN 2348-4470, 2014.
[24] Y. Rong, Q. Yanpeng and D. Ansheng, Multi-label Fuzzy Similarity-Based Nearest-Neighbour Classification Using Association Rule, International Conference on Intelligent Data Engineering and Automated Learning. Springer International Publishing, LNCS 9937, pp. 542-551, 2016.
[25] F. Benites and E. Sapozhnikova, "Improving Multi-label Classification by Means of Cross-Ontology Association Rules." Bioinformatics, vol. 2, no. 9, 2015.
[26] خلیل غفوری‌پور و زهرا میرزامؤمن، "بهبود رده‌بندی چندبرچسبی بر اساس استخراج قوانین انجمنی مثبت و منفی از روی برچسب‌ها"، بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر ایران، پژوهشگاه دانش‌های بنیادی، تهران، 18-20 اسفند 94.
[27] Waikato Environment for Knowledge Analysis, Version 3.6.10, 2013, www.cs.waikato.ac.nz/~ml/weka (دسترسی در 5/11/1394)
[28] A Multi-label Extension to WEKA, Version 1.7.7, 2015, www.meka.sourceforge.net (دسترسی در 5/11/1394)
[29] J. Han, Pei J. and Yin Y, "Mining frequent patterns without candidate generation", Proceeding of the 2000 ACM-SIGMID International Conference on Management of Data, pp. 1-12, 2000.