基于近似子图的规则空间压缩算法

黄宏涛; 梁存良; 李大鹏; 叶海智

doi:10.16383/j.aas.2017.c170272

基于近似子图的规则空间压缩算法

doi: 10.16383/j.aas.2017.c170272

1.
河南师范大学河南省教育大数据分析与应用工程技术研究中心新乡 453007
2.
南京邮电大学通信与信息工程学院南京 210003

基金项目:

河南省高等教育教学改革研究与实践重点项目 2017SJGLX042

河南省教育厅科学技术研究重点项目 15A880010

教育部人文社会科学研究项目 16YJC880017

河南省哲学社会科学规划项目 2016BJY010

江苏省自然科学基金 BK20161518

详细信息

作者简介:
梁存良  河南师范大学教育学院副教授.2008年获得河南师范大学教育技术专业硕士学位.主要研究方向为教学支持系统, 远程教育.E-mail:lcl@htu.cn

李大鹏  南京邮电大学通信与信息工程学院副教授.2011年获得上海交通大学无线通信研究所博士学位.主要研究方向为认知无线网络, 绿色通信技术和远程教育.E-mail:dapengli@njupt.edu.cn

叶海智  河南师范大学教育学院教授.2009年获哈尔滨工程大学计算机应用技术专业博士学位.主要研究方向为计算机网络, 远程教育和自动教学机器.E-mail:yhz87@163.com

通讯作者:
黄宏涛河南师范大学教育学院副教授.2012年获哈尔滨工程大学计算机应用技术专业博士学位.主要研究方向为教学支持系统, 自动教学机器和计算机化认知诊断.本文通信作者.E-mail:huanght@outlook.com

计量
- 文章访问数: 1289
- HTML全文浏览量: 229
- PDF下载量: 67
- 被引次数: 0
出版历程
- 收稿日期: 2017-05-21
- 录用日期: 2017-11-21
- 刊出日期: 2019-08-20

Rule-space Compression Algorithm Using Approximate Subgraph

1.
Henan Provincial Engineering Research Center for Analysis and Application of Educational Big Data, Henan Normal University, Xinxiang 453007
2.
College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003

Funds:

Henan Provincial Key Projects of Research and Practice for Higher Education Teaching Reform 2017SJGLX042

Key Project of Science and Technology of Education Department of Henan Province 15A880010

Humanities and Social Sciences Research Project of Ministry of Education 16YJC880017

Henan Provincial Philosophy Social Sciences Plan Project 2016BJY010

Jiangsu Provincial Natural Science Foundation BK20161518

More Information

Author Bio:
Associate professor at the Institute of Education, Henan Normal University. He received his Ph. D. degree in educational technology from Henan Normal University in 2008. His research interest covers teaching support system and distance education

Associate professor at the College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications. He received his Ph. D. degree from the Institute of Wireless Communications, Shanghai Jiao Tong University in 2011. His research interest covers cognitive wireless network, green communication technology, and distance education

Professor at the Institute of Education, Henan Normal University. He received his Ph. D. degree in computer application technology from Harbin Engineering University in 2009. His research interest covers computer network, distance education, and automatic teaching machine

Corresponding author: HUANG Hong-Tao Associate professor at the Institute of Education, Henan Normal University. He received his Ph. D. degree in computer application technology from Harbin Engineering University in 2012. His research interest covers teaching support system, automatic teaching machine, and computerized cognitive diagnosis. Corresponding author of this paper

摘要

摘要: 规则空间模型是一种高效的知识结构诊断模型，但较高的规则空间构造代价阻碍了在小规模、实时认知诊断中的应用.为了提高规则空间模型的可扩展性，提出使用近似子图生成理想属性模式集进而压缩规则空间的方法.近似子图能够通过忽略和测试项目无关的属性降低子图规模量级，从而有效缩减理想属性模式集规模，达到压缩规则空间的目的；同时通过构建顶点间的虚拟边模拟领域知识图上的传递依赖关系，使近似子图在不引入额外属性的前提下保持领域知识图上的依赖关系，实现对不合理属性模式的有效过滤.在此基础上，给出了构造规则空间所需的近似子图构造算法以及由近似子图生成理想属性模式集的方法.最后在标准测试集上开展了近似子图与依赖保持子图和顶点导出子图两种方法的性能对比实验，并将近似子图应用于实际教学认知诊断中验证其诊断准确率，实验结果表明近似子图能够在不损失诊断结果准确率的前提下显著压缩规则空间，降低规则空间模型应用于小规模、实时诊断的门槛.
- 规则空间 /
- 近似子图 /
- 依赖保持 /
- 压缩 /
- 理想属性模式
Abstract: Rule-space model is an effective method to diagnose knowledge structure of subjects. But high time cost of rule-space construction is a major obstacle to its application in the small and real time cognitive diagnosis. In order to improve the scalability of rule-space model, an algorithm is proposed to compress rule space by constructing an ideal attribute pattern set using the approximate subgraph. Approximate subgraph can decrease the order of subgraph by ignoring attributes unrelated to testing items so as to reduce the scale of ideal attribute set effectively, then the rule space can be compressed accordingly. At the same time, virtual edges between vertexes are constructed to simulate transitive dependencies on the domain knowledge graph, and these virtual edges preserve indirect dependences on the domain knowledge graph without introducing additional attributes, which ensures effective filteration of unreasonable attribute pattern. On this basis, the approximate graph construction algorithms and ideal attribute pattern generation algorithm supported by approximate subgraph are given for rule space construction. Finally, experiments for comparing the performance among approximate subgraph, dependency preserving subgraph and vertex derived subgraph on the benchmark dataset were carried out, followed by an application in practical teaching cognitive to verify the diagnosis accuracy of approximate subgraph based method. It is concluded that approximate subgraph compresses rule space remarkably without loss of diagnosis accuracy and makes it possible to apply rule space model to small and realtime cognitive diagnosis.
- Rule space /
- approximate subgraph /
- dependency preserving /
- compression /
- ideal attribute pattern
注释:

1) 本文责任编委王立威

HTML全文

图 1 领域知识图$G$

Fig. 1 Domain knowledge graph

下载: 全尺寸图片幻灯片

图 2 $G$关于$K(Q_{\rm sub})$的近似子图

Fig. 2 The approximate subgraph of $G$ on division criteria $K(Q_{\rm sub})$

下载: 全尺寸图片幻灯片

图 3 测试项目集的导出子图

Fig. 3 Subgraphs exported from test item set

下载: 全尺寸图片幻灯片

图 4 第1组实验规则空间生成时间

Fig. 4 Time performance of rule space generation in the first experiment

下载: 全尺寸图片幻灯片

图 5 第2组实验规则空间生成时间

Fig. 5 Time performance of rule space generation in the second experiment

下载: 全尺寸图片幻灯片

表 1 测试项目及其对应的属性

Table 1 Test item and its attributes

属性	$q_1$	$q_2$	$q_3$	$q_4$	$q_5$
相交线	$\surd $			$\surd $
三角形		$\surd $			$\surd $
三角形高			$\surd $		$\surd $
三角形面积				$\surd $

下载: 导出CSV

表 2 由$Q_{\rm sub}$生成的理想属性模式

Table 2 Ideal attribute pattern generated by $Q_{\rm sub}$

ID	$m$	$L(m)$
1	$0000$	{}
2	$1000$	{相交线}
3	$1100$	{相交线, 三角形}
4	$1110$	{相交线, 三角形, 三角形高}
5	$1111$	{相交线, 三角形, 三角形高, 三角形面积}

下载: 导出CSV

表 3 理想属性模式与期望反应模式的对应关系

Table 3 Expected response pattern corresponding to ideal attribute pattern

ID	$m$	$L(m)$	$R(m)$
1	$0000$	{}	00000
2	$1000$	{相交线}	10000
3	$1100$	{相交线, 三角形}	11000
4	$1110$	{相交线, 三角形, 三角形高}	11101
5	$1111$	{相交线, 三角形, 三角形高, 三角形面积}	11111

下载: 导出CSV

表 4 由VDS导出的理想属性模式集

Table 4 Ideal attribute set exported from VDS

ID	$m$	$L(m)$
1	$0000$	{}
2	$0100$	{三角形}
3	$0110$	{三角形, 三角形高}
4	$0111$	{三角形, 三角形高, 三角形面积}
5	$1000$	{相交线}
6	$1100$	{相交线, 三角形}
7	$1110$	{相交线, 三角形, 三角形高}
8	$1111$	{相交线, 三角形, 三角形高, 三角形面积}

下载: 导出CSV

表 5 第1组实验中子图及理想属性模式规模

Table 5 Scale of subgraphs and ideal attribute pattern in the first experiment

ID	$\|Q_{\rm sub}\|$	$\|K(Q_{\rm sub})\|$	$\|V\|$			$\|E\|$			$\|M\|$
ID	$\|Q_{\rm sub}\|$	$\|K(Q_{\rm sub})\|$	DPS	VDS	AS	DPS	VDS	AS	DPS	VDS	AS
1	5	4	5	4	4	6	2	5	14	11	5
2	5	6	9	6	6	13	3	7	134	31	16
3	6	5	6	5	5	8	3	6	28	18	9
4	6	7	10	7	7	13	4	9	195	54	26
5	10	9	13	9	9	18	5	11	802	156	82
6	11	7	11	7	7	15	4	9	258	49	24
7	12	15	19	15	15	29	11	20	4 836	763	392
8	15	11	17	11	11	23	7	14	6 751	538	262
9	17	14	20	14	14	28	9	18	19 735	3 365	1 144
10	17	12	19	12	12	27	7	15	9 754	1 044	393

下载: 导出CSV

表 6 第2组实验中子图及理想属性模式规模

Table 6 The scale of subgraphs and ideal attribute pattern in practical teaching cogonitive diagnosis in the second experiment

ID	$\|Q_{\rm sub}\|$	$\|K(Q_{\rm sub})\|$	$\|V\|$			$\|E\|$			$\|M\|$
ID	$\|Q_{\rm sub}\|$	$\|K(Q_{\rm sub})\|$	DPS	VDS	AS	DPS	VDS	AS	DPS	VDS	AS
1	6	6	10	6	6	13	4	5	130	28	19
2	6	6	8	6	6	10	4	5	44	31	18
3	6	5	8	5	5	10	3	5	43	20	11
4	6	6	10	6	6	14	4	6	126	28	19
5	7	7	11	7	7	15	4	8	210	60	29
6	8	7	10	7	7	13	5	6	135	49	32
7	7	8	13	8	8	17	5	8	763	102	48
8	8	6	9	6	6	12	4	7	76	27	15

下载: 导出CSV

表 7 诊断结果准确率

Table 7 Accuracy of diagnostic results

编号	Valid	$H$(91~100 %)	$M$(81~90 %)	$L$(0~80 %)
1	49	89.38	8.01	2.61
2	51	92.79	5.03	2.18
3	50	88.09	8.38	3.53
4	51	95.13	3.62	1.25
5	53	90.43	6.72	2.85
6	52	86.11	9.22	4.67
7	53	85.23	9.81	4.96
8	55	94.91	3.31	1.78

下载: 导出CSV

参考文献(30)

[1]	石俊飞, 刘芳, 林耀海, 刘璐.基于深度学习和层次语义模型的极化SAR分类.自动化学报, 2017, 43(2): 215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtml Shi Jun-Fei, Liu Fang, Lin Yao-Hai, Liu Lu. Polarimetric SAR image classification based on deep learning and hierarchical semantic model. Acta Automatica Sinica, 2017, 43(2): 215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtml
[2]	曾帅, 王帅, 袁勇, 倪晓春, 欧阳永基.面向知识自动化的自动问答研究进展.自动化学报, 2017, 43(9): 1491-1508 http://www.aas.net.cn/CN/abstract/abstract19126.shtml Zeng Shuai, Wang Shuai, Yuan Yong, Ni Xiao-Chun, Ouyang Yong-Ji. A survey on question answering systems towards knowledge automation. Acta Automatica Sinica, 2017, 43(9): 1491-1508 http://www.aas.net.cn/CN/abstract/abstract19126.shtml
[3]	白天翔, 王帅, 沈震, 曹东璞, 郑南宁, 王飞跃.平行机器人与平行无人系统:框架、结构、过程、平台及其应用.自动化学报, 2017, 43(2): 161-175 http://www.aas.net.cn/CN/abstract/abstract18998.shtml Bai Tian-Xiang, Wang Shuai, Shen Zhen, Cao Dong-Pu, Zheng Nan-Ning, Wang Fei-Yue. Parallel robotics and parallel unmanned systems: framework, structure, process, platform and applications. Acta Automatica Sinica, 2017, 43(2): 161-175 http://www.aas.net.cn/CN/abstract/abstract18998.shtml
[4]	Hooshyar D, Ahmad R B, Yousefi M, Fathi M, Horng S J, Lim H. Applying an online game-based formative assessment in a flowchart-based intelligent tutoring system for improving problem-solving skills. Computers and Education, 2016, 94: 18-36 doi: 10.1016/j.compedu.2015.10.013
[5]	Rau M A, Michaelis J E, Fay N. Connection making between multiple graphical representations: a multi-methods approach for domain-specific grounding of an intelligent tutoring system for chemistry. Computers and Education, 2015, 82: 460-485 doi: 10.1016/j.compedu.2014.12.009
[6]	Duffy M C, Azevedo R. Motivation matters: interactions between achievement goals and agent scaffolding for self-regulated learning within an intelligent tutoring system. Computers in Human Behavior, 2015, 52: 338-348 doi: 10.1016/j.chb.2015.05.041
[7]	戴汝为, 张雷鸣.思维(认知)科学在中国的创新与发展.自动化学报, 2010, 36(2): 193-198 http://www.aas.net.cn/CN/abstract/abstract15990.shtml Dai Ru-Wei, Zhang Lei-Ming. The creation and development of noetic (cognitive) science in China. Acta Automatica Sinica, 2010, 36(2): 193-198 http://www.aas.net.cn/CN/abstract/abstract15990.shtml
[8]	Tatsuoka K K. Rule space: an approach for dealing with misconceptions based on item response theory. Journal of Educational Measurement, 1983, 20(4): 345-354 doi: 10.1111/j.1745-3984.1983.tb00212.x
[9]	辛涛, 焦丽亚.测量理论的新进展:规则空间模型.华东师范大学学报(教育科学版), 2006, 24(3): 50-56, 61 doi: 10.3969/j.issn.1000-5560.2006.03.007 Xin Tao, Jiao Li-Ya. A new perspective for testing theory: the rule-space model. Journal of East China Normal University (Educational Sciences), 2006, 24(3): 50-56, 61 doi: 10.3969/j.issn.1000-5560.2006.03.007
[10]	Bernacki M L, Aleven V, Nokes-Malach T J. Stability and change in adolescents' task-specific achievement goals and implications for learning mathematics with intelligent tutors. Computers in Human Behavior, 2014, 37: 73-80 doi: 10.1016/j.chb.2014.04.009
[11]	Gálvez J, Guzmán E, Conejo R, Mitrovic A, Mathews M. Data calibration for statistical-based assessment in constraint-based tutors. Knowledge-Based Systems, 2016, 97: 11-23 doi: 10.1016/j.knosys.2016.01.024
[12]	Gutierrez F, Atkinson J. Adaptive feedback selection for intelligent tutoring systems. Expert Systems with Applications, 2011, 38(5): 6146-6152 doi: 10.1016/j.eswa.2010.11.058
[13]	Shikatani B, Vas S N, Goldstein D A, Wilkes C M, Buchanan A, Sankin L S, Grant J E. Individualized Intensive treatment for obsessive-compulsive disorder: a team approach. Cognitive and Behavioral Practice, 2016, 23(1): 31-39 doi: 10.1016/j.cbpra.2014.09.002
[14]	Özyurt Ö, Özyurt H. Learning style based individualized adaptive e-learning environments: content analysis of the articles published from 2005 to 2014. Computers in Human Behavior, 2015, 52: 349-358 doi: 10.1016/j.chb.2015.06.020
[15]	Belcadhi L C. Personalized feedback for self assessment in lifelong learning environments based on semantic web. Computers in Human Behavior, 2016, 55: 562-570 doi: 10.1016/j.chb.2015.07.042
[16]	Im S, Yin Y. Diagnosing skills of statistical hypothesis testing using the rule space method. Studies in Educational Evaluation, 2009, 35(4): 193-199 doi: 10.1016/j.stueduc.2009.12.004
[17]	Xin T, Xu Z Y, Tatsuoka K. Linkage between teacher quality, student achievement, and cognitive skills: a rule-space model. Studies in Educational Evaluation, 2004, 30(3): 205 -223 doi: 10.1016/j.stueduc.2004.09.002
[18]	Badaracco M, Martínez L. A fuzzy linguistic algorithm for adaptive test in intelligent tutoring system based on competences. Expert Systems with Applications, 2013, 40(8): 3073-3086 doi: 10.1016/j.eswa.2012.12.023
[19]	Qin C Y, Zhang L, Qiu D L, Huang L, Geng T, Jiang H, Ren Q, Zhou J Z. Model identification and Q-matrix incremental inference in cognitive diagnosis. Knowledge-Based Systems, 2015, 86: 66-76 doi: 10.1016/j.knosys.2015.05.024
[20]	汪玲玲, 陈平, 辛涛, 衷克定.基于BP神经网络的认知诊断计算机化自适应测验实现.北京师范大学学报(自然科学版), 2015, 51(2): 206-211 http://d.old.wanfangdata.com.cn/Periodical/bjsfdxxb201502019 Wang Ling-Ling, Chen Ping, Xin Tao, Zhong Ke-Ding. Realizing cognitive diagnostic computerized adaptive testing based on BP neural network. Journal of Beijing Normal University (Natural Science), 2015, 51(2): 206-211 http://d.old.wanfangdata.com.cn/Periodical/bjsfdxxb201502019
[21]	Cui Y, Gierl M, Guo Q. Statistical classification for cognitive diagnostic assessment: an artificial neural network approach. Educational Psychology, 2016, 36(6): 1065-1082 doi: 10.1080/01443410.2015.1062078
[22]	Bandyopadhyay S, Bhadra T, Mitra P, Maulik U. Integration of dense subgraph finding with feature clustering for unsupervised feature selection. Pattern Recognition Letters, 2014, 40: 104-112 doi: 10.1016/j.patrec.2013.12.008
[23]	Cameron D, Kavuluru R, Rindflesch T C, Sheth A P, Thirunarayan K, Bodenreider O. Context-driven automatic subgraph creation for literature-based discovery. Journal of Biomedical Informatics, 2015, 54: 141-157 doi: 10.1016/j.jbi.2015.01.014
[24]	Azimi S, Gratie C, Ivanov S, Petre I. Dependency graphs and mass conservation in reaction systems. Theoretical Computer Science, 2015, 598: 23-39 doi: 10.1016/j.tcs.2015.02.014
[25]	Yap K C, Chia K P. Knowledge construction and misconstruction: a case study approach in asynchronous discussion using knowledge construction-message map (KCMM) and knowledge construction-message graph (KCMG). Computers and Education, 2010, 55(4): 1589-1613 doi: 10.1016/j.compedu.2010.07.002
[26]	Baier C, Katoen J P. Principles of Model Checking. Cambridge: MIT Press, 2008.
[27]	Huang S B, Huang H T, Chen Z Y, Lv T Y, Zhang T. Lazy slicing for state-space exploration. Journal of Computer Science and Technology, 2012, 27(4): 872-890 doi: 10.1007/s11390-012-1271-7
[28]	Akgün Ö. Extensible automated constraint modelling via refinement of abstract problem specifications. Constraints, 2017, 22(1): 91-92 doi: 10.1007/s10601-016-9258-6
[29]	Pelechano N, Fuentes C. Hierarchical path-finding for Navigation Meshes (HNA). Computers and Graphics*, 2016, 59: 68-78 doi: 10.1016/j.cag.2016.05.023
[30]	张绍辉.集成参数自适应调整及隐含层降噪的深层RBM算法.自动化学报, 2017, 43(5): 855-86 http://www.aas.net.cn/CN/abstract/abstract19063.shtml Zhang Shao-Hui. Deep RBM algorithm with adaptive adjustment parameters and de-noising in hidden layer. Acta Automatica Sinica, 2017, 43(5): 855-865 http://www.aas.net.cn/CN/abstract/abstract19063.shtml