基于知识依赖度约简的知识发现研究

2015-06-24李化明王家云

软件导刊 2015年6期

李化明　王家云

摘要：粗糙集理论中的属性约简问题属于NP难问题。以教育技术学专业读者2013学年度图书借阅历史数据为原型，采用借阅类目的次数多少作为属性重要度进行启发式选择，利用粗糙集理论中的知识依赖度对类目约简，挖掘出本专业和各年级借阅类目的核心集，并经问卷调查证明其规律的正确性。通过与教育技术学专业学科知识体系结构的比较，能够发现学科知识体系结构建设的不足之处，以促进其更科学完善。

关键词：粗糙集；知识依赖度；数据挖掘；知识发现

DOIDOI：10.11907/rjdk.143896

中图分类号：TP391

文献标识码：A 文章编号

文章编号：16727800（2015）006013503

基金项目基金项目：安徽省高等学校图书情报工作委员会基金项目（TGW13B08）

作者简介作者简介：李化明（1974-），男，江西东乡人，硕士，淮北师范大学图书馆馆员，研究方向为数字图书馆、读者服务。

0 引言

高校图书馆自动化建设经过多年发展，已经积累了大量历史数据，这些数据不但完整，而且质量高，充分反映了读者学习成长的过程。如何对其进行挖掘提炼并从中发现有价值的知识，是了解读者需要、开展知识推送服务的重要信息来源。前人研究主要是根据读者的借阅历史数据，利用关联规则算法发现某类书籍之间的关联规则[14]，或利用聚类算法挖掘具有共同阅读兴趣的读者群体[5]，以及通过时间流分析得到读者借阅时间的分布规律[6]等。也可以利用粗糙集进行挖掘。例如，柳炳祥等[7]只是介绍有关理论，文章中并没有对粗造集挖掘进行深入阐述。这些挖掘结果往往只是反映读者已往的借阅规律，而不能反映其当前和今后一段时间的真实需要，因为这些读者还需要不断地进行知识更新和深化学习。本文通过对教育技术学专业读者群进行数据挖掘，利用知识依赖度约简方法发现其学科知识体系结构，并通过与相关专业的知识体系结构建设进行比较，以发现建设中的不足之处。如果利用所得的知识库进行推送服务，则能把读者真正需要的知识推送给他们。

1 粗造集有关理论

粗糙集理论认为“知识是一种对对象进行分类的能力”，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分[8]。

定义1（论域、知识）：设U 是感兴趣的对象组成的非空有限集合，称为一个论域。论域U 上的任一子集XU，称为论域U 的一个概念或范畴。论域U 中的任何子集簇（概念簇）称为关于U 的抽象知识，简称知识[9]。在二维表中，知识是由某些列对所有行的划分构成的集合所表示。

定义2（知识库）：给定一个论域U 和U上的一簇等价关系S，称二元组K=（U，S）是关于论域U 的一个知识库或近似空间。因此，论域上的等价关系即代表着划分和知识。这样，知识库就表示了论域上由等价关系导出的各种知识，即划分或分类模式，同时代表了对论域的分类能力，并隐含着知识库中概念之间存在的各种关系[9]。

定义3（不可分辨关系）：给定一个论域U 和U上的一簇等价关系S，若PS，且P≠，则∩P（P中所有等价关系的交集）仍然是论域U 上的一个等价关系，称为P上的一个不可分辨关系，记作IND（P）。IND（P）的等价类称为知识P的基本范畴[9]。

2 知识发现

2.1 样本数据选取

本研究以教育技术学专业学生作为研究原型，经统计，教育技术学专业自2008年以来每年招收1个班学生，系统有2008年以来的所有借阅历史记录，符合研究要求。为了简化样本数据，选择2013学年度（2013225～2014119日）教育技术学专业2010～2013级学生借阅历史数据作为研究对象（即大一至大四学生），借阅情况统计数据如表1所示。

2.2 数据预处理

在进行数据挖掘之前，需要对数据进行去噪、补缺和转换等预处理操作。数据预处理步骤如下：①根据年级、专业代码和时间段获取读者借阅历史记录，并通过汇总获得借阅图书的人数、未借阅人数和总借阅册数；②去除借阅书目的种次号，得到借阅类目，汇总后得到借阅类目数。由于中图法是通过标记符号代表各级类目和固定先后次序的分类体系，标记符号不同，其表示的知识类目也不同，故不能把相近类目合并为一类；③按类目进行汇总，求得各类目借阅册数和所有类目的平均借阅册数，并删除低于平均借阅册数的类目，因为其表现的只是某个学生的个人爱好，不是大家共同学习的知识，相当于噪音数据；④求出借过大于平均借阅册数类目的所有读者，这些读者即是进行知识约简的对象；⑤生成上述读者对象和其借阅类目的二维表，并对表中数据进行转换处理，如果此读者借过该类目书籍则为1，否则为0。类目列按类目总借阅册数降序添加到表中。

2.3 知识约简

经过上面的数据预处理后，得到了知识库的关系簇S 和论域U，即不小于平均借阅册数的类目和借阅这些类目的读者。然而，即使经过上述预处理后，其约简的类目数还有几十种；如果直接利用知识依赖度（定义5）来约简，其需要计算的次数为M*logM*2n（M是读者数，n是类目数），这是指数级时间复杂度，需要消耗大量计算时间。为了得到多项式时间算法，采用以类目借阅的册数多少作为属性重要度的启发式策略，应用知识依赖度来约简二维表，具体算法如下：

（1）置K={}，R={}；// K表示约简后得到的知识，R表示临时约简知识

//如果单个知识把论域全覆盖则作为约简知识放入K中

（2）For r0=1 to count（类目） do

取出count（r0）类目I，计算其划分。

如果I全覆盖论域U ，则把I并入K中；否则，退出循环。

（3）把I并入R中。

//计算剩下的类目依赖关系

（4）For r1=r0+1 to count（类目） do

取出count（r1）类目Q，根据类目Q求其对论域U 的划分。

根据R中的知识求其对论域U 的划分。

利用知识依赖度公式，求Q对R的知识依赖度γ；如果γ小于0.5，则把Q并入R中，否则认为知识Q归属于R而被约简掉。

（5）K=K∪R，并退出。 //即K就是所求的约简集合

此算法不能保证所有结果最优，但近似最优值。对教育技术学专业2013学年度的知识约简后的结果见表1“类目选择”列，这里按属性重要度（借阅册次多少）列出了前面5～6个约简后得到的类目（知识集合）。然后对各年级约简的类目扫描一遍，根据类目的位置和重复度多少，即可得到本专业的核心知识，即：TP391.41、I247.5为专业核心知识集。约简后一些主要类目借阅册数如表2所示。

2.4 结果分析

在表2中如果各约简后的主要类目借阅册数相差悬殊不大，则说明读者不了解专业知识结构，而是根据个人的兴趣爱好进行借阅；若相反，则表明其专业知识结构明确，借阅的针对性和目的性非常强。例如，表2中大一学生（2013年级）借阅TP391.41为14册，G40-057为6册，对应的表1中的几个主要借阅类目之间的最大比例是14/6≈2.3倍，这说明他们除了学习专业技术知识外，还阅读“I247.57 社会、言情小说”、“I561 英国文学”等书籍，阅读内容涉及面较宽，不了解专业知识体系结构；大二学生（2012年级）借阅TP391.41为69册，J06为7册，几个主要借阅类目之间的最大比例是69/7≈9.9倍，这显示他们初步抓住了专业知识体系结构，阅读内容较为集中；而大三、大四的学生几个主要借阅类目之间的最大比例≥12倍，表明他们主攻专业技术知识“TP391.41图像识别及其装置”、“TP393.092网络浏览器”，学习目标非常明确。

另外还可以看到，“I247.5新体长篇、中篇小说” 一直是读者热衷的书籍，但在教育技术学专业人才培养方案（2013）[13]中则没有反映出来，该专业主要课程包括：教育技术学导论、心理学、教学系统设计、远程教育基础、电视教材设计与制作、教育媒体理论、教育技术学研究方法、中学信息技术课程教学设计。并且从表2中还能看出，一些专业基础理论知识例如“J06 造型艺术理论”、“G40-057 教育技术学”，主要是由大一、大二学生借阅，而且数量都不大。这表明学科体系结构中相关基础理论课程设置较合理，基本满足学习者需要；相反，“TP393.092 网络浏览器”在大三、大四学生借阅量中却骤然增加，这反映了教育技术学专业学生更需要这方面的知识和技能，也说明该课程在学科体系结构中的重要性，以及体系结构设置的不合理性。

因此，通过对相关数据的分析，给出如下建议：①给大一、大二学生适当介绍本学科知识体系结构，使其开始就明确学习目标、方向和内容组成；②通过与教育学院教师交流发现，学院已开设《学科导论》课程，但效果不够理想。因此，对于开设《学科导论》课的院系，需要扎实推进本导制，发挥其引导作用；③深入研究小说等文学类与教育技术学专业之间的内在关系，将其纳入学科体系结构中，完善学科知识体系结构建设；④在低年级中适当开设“TP393.092 网络浏览器”课程，做好相关理论基础知识铺垫，使学科知识结构布局更加合理。

3 知识验证

为了验证以上发现的知识规律是否正确，对2011～2013级教育技术学专业读者进行问卷调查。问卷内容主要是根据表2约简后得到的几个类目，按借阅册次多少选择前3个类目，挑选出上一年级读者在2013学年度借阅最多的前几本书目及类目（配有类目解释和例子），加上读者自我推荐书目栏目，把这些作为2014年度本年级调查内容。这样设计的目的是：①验证以上发现的知识规律是否正确；②验证上一年级读者在上学年借阅最多的书目是否也是本年级读者在本学年借阅最多的，以确定推荐内容。调查统计结果如表3所示，按此知识规则进行推荐，其类目命中率（即约简后的知识类目中想借阅数/总想借阅数）都在87%以上。再把表2和表3内容合并后比较得出表4，从表4中也能看出其顺序基本一致。因此，采用这种方法得出的知识与实际相符，验证了规律的正确性。另外，从调查具体数据来看，上一年级读者借阅最多的书目并不一定是本年级读者最想看的书目，例如：在对2012级教育技术学专业学生问卷调查中，书目 Flash 8基础与实例精讲（腾飞科技编著.人民邮电出版社，2007）在2013学年被2011级教育技术学专业学生借阅了6次，问卷调查结果是34人想借阅；而书目Flash 8 角色与动画短片设计技术精粹（周国栋编著.人民邮电出版社，2007），则借阅了4次，问卷结果是41人想借阅。因此，在进行知识书目推荐时，需要从这些约简后的类目中分别挑选借阅最多的前几本书目，组合起来作为推荐内容，才能满足读者真正的需要。

4 结语

本文利用粗糙集理论中的知识依赖度约简方法对某专业读者群借阅历史数据进行挖掘，获得其学科体系结构知识，并通过比较，发现相应学科体系结构建设中的不足之处，促使学科结构体系建设更加合理、完善。如果利用所得的知识进行推送服务，则能够根据学生知识结构的变化进行预判，做到有的放矢，提高服务质量。当然，本文还有一些问题尚待解决，如表4类目顺序变化的真正原因是什么，蕴含了哪些知识？小说等文学类中哪些知识是教育技术学专业的本质需要，如何合理设计它在学科体系结构的布局等？相关问题有待进行下一步更深入的研究。

参考文献：

[1]陈锦，吴扬扬. Apriori算法在高校图书馆图书推荐中的应用[J]. 河南科技学院学报：自然科学版，2012，40（4）：9092.

[2]赵彦辉. 基于流通数据挖掘的读者阅读兴趣本体模型构建[J]. 图书情报工作， 2012，56（3）：121125.

[3]张红燕. 关联规则挖掘在高校图书馆借阅流通中的应用[J]. 数字技术与应用，2012（5）：76，78.

[4]薛琴荣，李响. 基于数据挖掘技术的图书馆个性化借阅服务研究[J]. 情报探索，2013（4）：110113.

[5]杨昌顺. 聚类分析在图书馆读者群体细分中的研究和应用[J]. 贵州师范学院学报，2012，28（6）：1117.

[6]蒋细芳，刘羽，冯现坤. 基于时间序列的图书馆个性化服务研究[J]. 软件导刊，2011，10（5）：125126.

[7]柳炳祥. 基于数据挖掘的图书馆个性化服务系统[J]. 现代情报，2007（3）：108109.

[8]李龙澍，王慧萍，徐怡. 二进制可分辨矩阵的最小属性约简算法[J]. 计算机技术与发展，2010，20（6）：9396，100.

[9]苗夺谦，李道国. 粗糙集理论、算法与应用[M]. 北京：清华大学出版社，2008.

[10]唐彬，李龙澍. 启发式属性约简算法完备性和规则发现算法的研究[J]. 计算机工程与应用，2003（30）：191194，229.

[11]石红. 关于粗糙集理论及应用问题的研究[J]. 计算机工程， 2003，29（3）：13，29.