基于知识依赖度约简的知识发现研究
摘要：粗糙集理论中的属性约简问题属于NP难问题。以教育技术学专业读者2013学年度图书借阅历史数据为原型，采用借阅类目的次数多少作为属性重要度进行启发式选择，利用粗糙集理论中的知识依赖度对类目约简，挖掘出本专业和各年级借阅类目的核心集，并经问卷调查证明其规律的正确性。通过与教育技术学专业学科知识体系结构的比较，能够发现学科知识体系结构建设的不足之处，以促进其更科学完善。
关键词：粗糙集；知识依赖度；数据挖掘；知识发现
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 样本数据选取
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就是所求的约简集合
2.4 结果分析
因此，通过对相关数据的分析，给出如下建议：①给大一、大二学生适当介绍本学科知识体系结构，使其开始就明确学习目标、方向和内容组成；②通过与教育学院教师交流发现，学院已开设《学科导论》课程，但效果不够理想。因此，对于开设《学科导论》课的院系，需要扎实推进本导制，发挥其引导作用；③深入研究小说等文学类与教育技术学专业之间的内在关系，将其纳入学科体系结构中，完善学科知识体系结构建设；④在低年级中适当开设“TP393.092 网络浏览器”课程，做好相关理论基础知识铺垫，使学科知识结构布局更加合理。
3 知识验证
4 结语
本文利用粗糙集理论中的知识依赖度约简方法对某专业读者群借阅历史数据进行挖掘，获得其学科体系结构知识，并通过比较，发现相应学科体系结构建设中的不足之处，促使学科结构体系建设更加合理、完善。如果利用所得的知识进行推送服务，则能够根据学生知识结构的变化进行预判，做到有的放矢，提高服务质量。当然，本文还有一些问题尚待解决，如表4类目顺序变化的真正原因是什么，蕴含了哪些知识？小说等文学类中哪些知识是教育技术学专业的本质需要，如何合理设计它在学科体系结构的布局等？相关问题有待进行下一步更深入的研究。
参考文献：
[3]张红燕. 关联规则挖掘在高校图书馆借阅流通中的应用[J]. 数字技术与应用，2012（5）：76，78.
[4]薛琴荣，李响. 基于数据挖掘技术的图书馆个性化借阅服务研究[J]. 情报探索，2013（4）：110113.
[7]柳炳祥. 基于数据挖掘的图书馆个性化服务系统[J]. 现代情报，2007（3）：108109.
[9]苗夺谦，李道国. 粗糙集理论、算法与应用[M]. 北京：清华大学出版社，2008.
[14]中国图书馆分类法编辑委员会. 中国图书馆分类法[M]. 第4版. 北京： 书目文献出版社，1999.