基于标签关联性的多标签Scratch分类算法

doi:10.13190/j.jbupt.2019-126

北京邮电大学学报 ›› 2019, Vol. 42 ›› Issue (6): 134-141.doi: 10.13190/j.jbupt.2019-126

基于标签关联性的多标签Scratch分类算法

彭聪, 孙岩, 戚鹏

北京邮电大学计算机学院, 北京 100876

收稿日期:2019-11-22 出版日期:2019-12-28 发布日期:2019-11-15
通讯作者: 孙岩(1970-),女,教授,博士生导师,E-mail:sunyan@bupt.edu.cn. E-mail:sunyan@bupt.edu.cn
作者简介:彭聪(1995-),男,硕士生.
基金资助:
国家自然科学基金项目（61672109，61772085，61877005）

Label Relevance Based Multi-Label Scratch Classification Algorithm

PENG Cong, SUN Yan, QI Peng

School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2019-11-22 Online:2019-12-28 Published:2019-11-15

摘要/Abstract

摘要： 为了实现Scratch可视化编程领域的作品分类，提出了一种基于标签关联性的多标签分类算法（MLLR），构建了一个有效的多标签Scratch分类模型.首先提取作品的Block使用特征、计算思维技能特征和复杂度特征3类特征作为分类特征；然后针对RAKEL算法随机选择标签子集，忽略了标签间的关联性，提出了改进的MLLR算法，该方法根据多标签之间的关联性来划分标签子集，再训练相应的标签幂集子分类器.实验结果表明，MLLR算法在分类性能和时间性能上优于RAKEL等多标签分类算法，构建的分类模型对于Scratch作品具有较强的适用性，分类的准确率达到81.3%.

关键词: Scratch, 标签关联性, 多标签分类, 分类模型

Abstract: In order to implement the classification of projects in visual programming field of Scratch, a multi-label classification algorithm (MLLR) appears based on label relevance. An effective multi-label classification model for Scratch projects was constructed. Firstly, the block usage features, the computational thinking skill features and the Halstead features of projects are extracted as classification features. Then, the RAKEL algorithm randomly chooses label subsets, ignoring the relevance between labels, thereafter an improved MLLR algorithm was proposed. This method divides label subsets according to the relevance between multiple labels, and then trains the corresponding label power set sub-classifiers. Experiments show that MLLR algorithm is superior to RAKEL and other multi-label classification algorithms in classification performance and time performance, The classification model constructed has a strong applicability for Scratch projects, and the accuracy of classification reaches 81.3%.

Key words: Scratch, label relevance, multi-label classification, classification model

中图分类号:

TP301.6

彭聪, 孙岩, 戚鹏. 基于标签关联性的多标签Scratch分类算法[J]. 北京邮电大学学报, 2019, 42(6): 134-141.

PENG Cong, SUN Yan, QI Peng. Label Relevance Based Multi-Label Scratch Classification Algorithm[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2019, 42(6): 134-141.

参考文献

[1] Chang Zhong, Sun Yan, Wu Tinyu, et al. Scratch analysis tool(SAT):a modern scratch project analysis tool based on ANTLR to assess computational thinking skills[C]//2018 14^th International Wireless Communications & Mobile Computing Conference (IWCMC). Limassol:IEEE Press, 2018:950-955.
[2] Techapalokul P. Sniffing through millions of blocks for bad smells[C]//Proceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science Education-SIGCSE'17. Washington:ACM Press, 2017:781-782.
[3] Aivaloglou E, Hermans F, Moreno-Leon J, et al. A dataset of scratch programs:scraped, shaped and scored[C]//2017 IEEE/ACM 14^th International Conference on Mining Software Repositories (MSR). Buenos Aires:IEEE Press, 2017:511-514.
[4] Moreno-Leon J, Robles G, Roman-Gonzalez M. Towards data-driven learning paths to develop computational thinking withscratch[J]. IEEE Transactions on Emerging Topics in Computing, 2017, 14(6):185-197.
[5] Szymański P, Kajdanowicz T, Kersting K. How is a data-driven approach better than random choice in label space division for multi-label classification?[J]. Entropy, 2016, 18(8):282-305.
[6] Zhang Minling, Zhou Zhihua. A review on multi-label learning algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8):1819-1837.
[7] Zhang Yahong, Li Yujian, Cai Zhi. Correlation-based pruning of dependent binary relevance models for multi-label classification[C]//2015 IEEE 14^th International Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC). Beijing, China:IEEE Press, 2015:399-404.
[8] Lena T, Lior R, Bracha S. Identification of label dependencies for multilabel classification[C]//Proceedings of the 2^nd International Workshop on Learning from Multi-Label Data. Dublin, Ireland:IEEE, 2010:53-60.
[9] Tsoumakas G, Katakis I, Vlahavas I. Random k-labelsets for multilabel classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(7):1079-1089.
[10] Charte F, Rivera A, del Jesus M J, et al. Improving multi-label classifiers via label reduction with association rules[M]//Lecture Notes in Computer Science. Berlin, Heidelberg:Springer Berlin Heidelberg, 2012:188-199.
[11] Liu Caizhi, Sheng Yanxiu, Wei Zhiqiang, et al. Research of text classification based on improved TF-IDF algorithm[C]//2018 IEEE International Conference of Intelligent Robotic and Control Engineering (IRCE). Lanzhou, China:IEEE Press, 2018:218-222.
[12] Moreno-Leon J, Robles G, Roman-Gonzalez M. Comparing computational thinking development assessment scores with software complexity metrics[C]//2016 IEEE Global Engineering Education Conference (EDUCON). Abu Dhabi, UAE:IEEE Press, 2016:1040-1045.
[13] Wang Zezhong, Cao Shuo. A power load association rules mining method based on improved FP-growth algorithm[C]//2018 China International Conference on Electricity Distribution (CICED). Tianjin, China:IEEE Press, 2018:2833-2837.
[14] Gibaja E, Ventura S. Atutorial on multilabel learning[J]. ACM Computing Surveys, 2015, 47(3):1-38.

基于标签关联性的多标签Scratch分类算法

Label Relevance Based Multi-Label Scratch Classification Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价