基于随机游走模型的高校图书馆知识发现系统构建

刘爱琴 贾一帆 冷长青

摘 要：[目的]为了实现知识的快速聚类和关联分类，由传统的以资源检索为目标的高校图书馆系统转变为完全面向用户需求的、主动发现和推送知识的图书馆知识发现系统。[过程]本文融合网络爬虫技术和学术资源网站结构化数据的特征，构建了基于随机游走模型，依据摘要词频对文献资料进行主题词的提取、聚类;随后在标签信息标注的基础上，根据相似性对游走过程进行加权处理;最终完成了知识关联分类的知识发现系统。[结果]本文实现了用高效的知识提取手段，基于智慧云、物联网构建更加准确和更具关联性的知识发现系统，提高了高校图书馆知识检索系统的查全率和查准率。

关键词：高校图书馆;摘要信息标注;加权处理;随机游走模型;知识发现系统

DOI：10.3969/j.issn.1008-0821.2020.05.012

〔中图分类号〕G250.74 〔文献标识码〕A 〔文章编号〕1008-0821（2020）05-0096-08

Construction of Knowledge Discovery System in

University Library Based on Random Walking Model

Liu Aiqin Jia Yifan Leng Changqing

（School of Economics and Management，Shanxi University，Taiyuan 030006，China）

Abstract：[Purpose]In order to realize the fast association classification of knowledge，the traditional university library system with the goal of resource retrieval should transform into a library knowledge discovery system that completely faces the needs of users and actively discovers and pushes knowledge.[Process]In this paper，based on the combination of web crawler technology and the characteristics of structured data of academic resources websites，a random walk model was constructed，and the subject words were extracted and clustered according to the abstract word frequency;then，on the basis of label information tagging，the walking process was weighted according to similarity;Finally， the knowledge discovery system of knowledge association classification was completed.[Result]This paper realized the use of efficient knowledge extraction means to build a more accurate and relevant knowledge discovery system based on the cloud of wisdom and the Internet of things，which improved the recall and precision of the university library knowledge retrieval system.

Key words：university library;information tagging of the abstract;weighted processing;random walk model;knowledge discovery system

1 研究背景

用戶知识需求的不断增加，要求获取信息的准确性和关联性越来越高[1]，高校图书馆利用高效的知识提取手段和知识发现技术，基于智慧云、物联网构建更加准确和更具关联性的知识发现系统，实现短时间内准确获取知识[2]，解决用户的特定问题和满足用户日益增长的个性需求，要比高校图书馆提供传统数据库更吸引用户的使用[3]。由传统的以资源检索为目标转变为完全面向用户需求的、主动发现和推送知识的图书馆知识发现系统的工作已迫在眉睫。

根据研究对象的数据特点，国内外学者正在展开积极的研究。国外学者Sen S等[4]利用标签的推荐算法，Yildirim H等[5]利用RWR算法来消减协同过滤中稀疏性问题，其根据项目之间的相似度针对不同用户的初始评分信息在项目空间中进行不同的随机游走过程;Zhou D Y等[6]基于超图的随机游走方法;Li D C等[7]基于超图的半监督关键词排序算法的定义，Meila M等[8]基于马尔可夫链的随机游走聚类算法解决传统服务中推荐算法准确性不高以及推荐结果缺乏多样性等问题。国内学者在具体模型的构建上进行了大量的研究，何胜等[9]提出一种以文献“混合关联”为主要内容的图书馆文献推荐方案及实现算法;刘爱琴等[10]基于SOM神经网构件关联数据集，并结合语义检索和属性值匹配等技术，构建高校图书馆用户个性化推荐服务系统;赵荣珍等[11]针对知识发现中数据资源化保护的原始故障问题，借助数据驱动构建了基

于粗糙集理论的知识获取模型，为智能决策的优化提供了一种可行方案入PDA资源建设模式，帮助读者在海量书目资源中方便快捷地发现自己需要的图书资源;姜璐[12]通过利用现代信息分析技术，构建了图书馆嵌入式知识发现情报分析服务模型。马慧芳等[13]将文献标题与标题中的词项视为超边与超点构造超图，对超边与超点同时加权，设计了一种基于加权超图随机游走的关键词提取算法;赵红霞等[14]提出了基于随机游走的最优路径集合选取算法，解决了网络规模过大造成的准确性和执行效率丢失问题;王丽莎等[15]在随机游走算法的基础上进行了改进，提出了一种项目—标签导向的随机游走推荐模型，针对特定用户分别在项目空间和标签空间中根据对象之间的相似性计算转移概率，进行有限步长的随机游走，在两个空间中都生成若干个待推荐项目，然后重新计算预测评分，最后对该用户进行个性化信息推荐;方晨等[16]提出了基于随机游走和多样性图排序的个性化服务推荐方法，解决了传统服务推荐算法由于数据稀疏性而导致推荐准确性不高，以及推荐结果缺乏多样性等问题;在随机游走模型的数据处理方面，余思东等[17]考虑随机游走转移概率的求解问题在边界条件下的求解方法。可见，目前已有研究多集中于对文献的题目或文献列出的关键词进行分析和聚类，容易造成文献信息获取不全面、关键词题目等对文献的描述存在局限性等问题，同时，聚类标准的单一会使知识发现结果存在偏移。

综上所述，本文融合網络爬虫技术和学术资源网站结构化数据的特征，首先基于文献摘要，利用网络爬虫、Python对摘要主题词进行提取，对数据进行预处理，对图书馆中海量的文献数据进行爬取、加工和整合，随后将主题词作为文献分类的基础，基于超图模型、k-means算法构建随机游走模型，通过设置标记点文献并游走遍历所有文献的摘要主题词，在诸多文献之间的游走过程中，依据摘要的相似关键词数量为从起点文章开始的不同游走路程进行加权处理，获得文献间的关联性;最后在完成所有文献的游走过程后，将达到概率标准的文章划分为同类，实现知识发现系统的关联、聚类和规范，达到知识集成和整合。

2 知识发现系统模型构建

2.1 理论基础

随机游走模型是通过随机选取某一文献作为起点，随机游走所有的文献，根据信息特征相似性对游走线路作加权处理，查阅所有文献后完成聚类。

随机游走算法通过对数据集进行统一的定义，把给定的数据集合作为固定数目的节点和边的离散对象，将数据聚类分析问题转化为无向加权图来实现求解。首先，将数据集映射成一个无向加权图G=（V，E），由数据值的节点vi∈V和表示数据与其相邻数据间关系的边界e∈E组成。eij表示连接两个顶点vi、vj的边，每条边用权重wij来表示两个顶点之间的相似或差异程度。顶点vi的度定义为di=∑wij，等于所有与结点Vi相关联边的权值和;其次，根据数据性质设置k个标记点，通过为每个未被标记的数据节点分配一个k维向量，来表示一个未被标记点到达所有标记点的随机游走过程。第三，每个一维向量均表示从每个未标记点出发，第一次到达k个标记点的概率，k个概率中最大的值为未标记点所属的类标签。该方法将具有相似性的数据就可归为一类，根据不同类别之间的差异实现数据聚类。

两个文本数据X和Y的相似度可根据Tanimoto系数表示为式（1）：

其中，X与Y的相似度x、y即由二者相同的关键词与所有关键词之和的比值来表示，该相似度在进行归一化后也作为游走概率即游走过程中的权重处理。

在一定的边界条件下，随机游走转移概率的求解问题与联合狄利克雷求解问题的解相似。因此，本文通过求解联合狄利克雷问题的解来实现随机游走算法求解，在区域Ω上，给定定义文献节点的函数u，其狄利克雷积分形式为式（2）：

D[u]=12∫ΩΔu2dΩ（2）

随机游走从一个非标记点到标记点的概率等于该标记点在边界条件下的狄利克雷函数，求解的问题即在某个边界条件下求解拉普拉斯函数，定义该文献由二维参数i与j描述，如式（3）所示：

拉普拉斯Lij的值由节点vi与vj共同决定，该矩阵是满足边界条件下的对称正定矩阵。di为节点vi的度，定义di=∑nj=1wij，表示w第i行所有元素之和。

由式（5）可知，关联矩阵由边eij和节点vk决定，图中eij为任意方向，A为联合梯度算子，AT为联合散度算子。

构造一个大小为m×n的对角阵C，其对角线上的值为映射图边上的权值，见式（6）：

如果连续，联合梯度算子和联合散度算子之积可以表示各向同性的联合拉普拉斯矩阵即L=ATA。在映射图中，矩阵C可看作向量上一个加权内积大小的度量，当C=I时，L=ATCA可简化为L=ATA。因此，调和函数求解问题可通过上述定义解决即：在固定标记点值已知情况下，非标记点到标记点的概率值可求，式（2）可转化为：

其中，L为联合的拉普拉斯矩阵，x为图中数据的概率值，D[x]的最小值可通过联合调和函数x求得，映射图中的所有节点可分为未标记点集合和标记点集合集将拉普拉斯矩阵按标记点和未标记点排列得：

其中，XB、XU分别为标记点和非标记点的随机游走概率值，D[xU]对xU求的微分得：

令xsi表示未标记点到达标记点为s的概率，定义一个表示所有标记点集合的函数：Q（vj）=s，vj∈VM且0

因此，通过求解：LUxs=-BTms得到到达单个标记点的概率;通过LUX=-BTM求得到所有种子点的概率，其中，k个列矢量xs组成X，k个列矢量ms组成M。因为对任意未被标记节点来说，它到所有种子点的概率之和为1，即：

对于k个标记种子点来说，计k-1组方程，求可得出k-1个概率值。

在获得每个结点vi第一次到达k个种子点的概率后，逐个比较大小，以最大转移概率maxs（xsi）实现聚类。

2.2 系统构建

基于随机游走模型的高校图书馆知识发现系统由数据层、匹配层和用户层3个层次组成。其中，数据层主要完成对文献数据通过随机游走模型进行整合统计，包括数据库，分为文献资源数据库与用户资源数据库，用来管理系统中所有的原始数据;数据处理操作，包含对用户搜索历史、目标学科信息的提取保存和文献摘要关键词的提取，以及通过关键词相似度进行文献聚类，即随机游走模型在系统中的应用。

匹配层主要完成数据层与用户层的连接，输入处理主要是针对用户搜索的文献进行资源库搜索或对新录入的文献进行聚类处理，以便后续搜索或相关文献推荐;资源匹配则是将数据库的文献资源与用户搜索匹配。

用户层是展示给知识发现系统用户的层面，其主要功能就是向用户展示资源匹配的结果，内容的形式以关联文献来表现，详见图1。

该知识发现系统将资源整合与用户服务相结合，将数据层、匹配层和用户层相联系，具体服务操作流程如图2所示：首先，系统起始操作由用户或系统管理者发起。系统管理者发起对系统进行文献录入，并由系统的匹配层完成输入处理，匹配层提取文献摘要关键词并进行随机游走完成聚类，计入文献资源库的某一聚类集群中。其次，用户在登入系统后，系统通过访问用户资源库提取用户的数据，包括历史访问、偏爱集群和用户信息，获取用户可能感兴趣的文献或集群。在用户输入信息进行搜索后，系统的匹配层完成输入处理，并将用户搜索输入时提供的新用户特征，如感兴趣的学科内容等录入用户资源库。第三，用户输入搜索，匹配层完成资源匹配，将数据库中的文献资源与用户搜索内容进行匹配。最后，系统完成匹配，将用户的搜索与资源库的文献或集群的关联展示给用户，与此同时，新的用户搜索增加新的用户特征与关联图谱。通过此系统，提高了高校图书馆信息检索的查全率和查准率，实现了知识聚类。

3 系统实现

利用中国知网数据库进行上述高校图书馆知识发现系统中关于文献摘要聚类的性能的算法仿真验证。本文应用Python爬虫技术，在检索栏输入“信息”，选取前200篇文献，随机抓取文献摘要，并基于该摘要词频对相应句意进行主题词提取。获取文献摘要并提取主题词的部分代码，如图3所示，随机获得文献摘要样本后，根据词频对句意提取主题词的部分代码，如图4所示。文献间基于主题词相似度获取文献间游走路径的权重，部分获取结果如图5所示。

根据权重在200篇文献中进行随机游走，最终部分结果如图6所示，游走遍历所有文献的摘要关键词聚类，关联性强的文献在如图所示的结果中被聚集在了一起，读者可以方便、快捷地查找到同类文献，实现高校图书馆知识发现系统的构建。

游走结果展示出了起点文献或中心文献及与该文献关联的文献标题与数目，如图7所示，由此可以完成对具体聚类数目的规划，较已有图书馆文献聚类系统拥有更加细致的分类。

为使数据更加直观，从视觉感官上獲取数据信息的频度关联程度，可通过方块面积来展示数据信息频度的Masico图，和文字大小代表关键词频度的词云，以及背景图片的形状变换相应数据的位置来实现列表数据的可视化图示。以“CEO特征对企业社会责任信息披露影响研究”为中心文献为例，与该文献关联的，并以矩形方片中心椭圆式向外扩散的可视化最终显示结果，如图8所示。其中，关键词出现频度不高，设置最低字体大小词汇，以远离中心显示。

在此为基础，构建的高效图书馆知识发现系统，由用户界面与后台管理界面组成，用户和管理员可在此界面均可完成上述操作，详见图9、图10所示。

4 结 语

融合网络爬虫技术和学术资源网站结构化数据的特征，本文基于随机游走模型构建了高校图书馆知识发现系统。该系统依据摘要词频作为聚类标准，对文献摘要进行主题词的提取、聚类;随后在标签信息标注的基础上，遍历文献，并根据相似性对游走过程进行加权处理，一方面有效地实现了知识的快速聚类和关联分类;另一方面聚类类目的细化及起点或中心文献及与该文献关联的文献标题与数目关联可视化显示，有效地提高了高校图书馆知识检索系统的查全率和查准率。

参考文献

[1]李祎.基于图书情报机构智库建设的知识发现系统构建研究[J].图书馆工作与研究，2017，（2）：61-65.

[2]王勋.基于深度学习的数字图书馆网络知识发现研究[J].图书馆学刊，2018，（7）：116-120.

[3]Doug Way.The Impact of Web-scale Discovery on the Use of a Library Collection[J].Serials Review，2010，36（4）：214-220.

[4]Sen S，Vig J，Riedl.J.Tagommenders：Connecting Users to Items through Tags[C]//Proceedings of the 18th International World Wide Web Conference，Madrid，Spain， 2009：671-680.

[5]Yildirim H，Krishnamoorthy M S.A Random Walk Method for Alleviating the Sparsity Problem in Collaborative Filtering[C]//Proceedings of the 4th ACM Conference on Recommender Systems，Lausanne，Switzerland 2008：131-138.

[6]Zhou D Y，Huang J Y，et al.Learning with Hypergraphs：Clustering，Classification，and Embedding[A].Proceedings of the 20th International Conference on Neural Information Processing Systems[C]//Vancouver，Canada：MIT Press，2006：1601-1608.

[7]Li D C，Li S J.Hypergraph-based Inductive Learning for Generating Implicit Key Phrases[A].Proceedings of the 20th International Conference on World Wide Web[C]//Hyderabad，India：Springer，2011：77-78.

[8]Meila M，Shi J.Learning Segmentation By Random Walks[C]//NIPS，Den，Co，USA：MIT Press，2000：873-879.

[9]何胜，熊太纯，柳益君，等.基于Spark的高校图书馆文献推荐方案及实证研究[J].图书情报工作，2017，61（23）：129-137.

[10]刘爱琴，李永清.基于SOM神经网络的高校图书馆个性化推荐服务系统构建[J].图书馆论坛，2018，38（4）：95-102.

[11]赵荣珍，邓林峰.基于粗糙集数据分类概念的故障知识发现[J].振动、测试与诊断，2012，32（1）：17-22，158.

[12]姜璐.大数据时代图书馆嵌入式知识发现情报分析服务研究[J].农业图书情报学刊，2018，30（8）：152-155.

[13]马慧芳，刘芳，夏琴，等.基于加权超图随机游走的文献关键词提取方法[J].电子学报，2018，46（6）：1410-1414.

[14]趙红霞，刘高森，李愈.基于随机游走的分类垃圾回收最优路径规划[J].交通运输工程于信息学报，2018，16（3）：103-108.

[15]王丽莎，张绍武，林鸿飞.基于项目和标签的随机游走个性化信息推荐模型[J].情报学报，2012，31（3）：289-296.

[16]方晨，张恒巍，王娜，等.基于随机游走和多样性图排序的个性化服务推荐方法[J].电子学报，2016，46（11）：2773-2780.

[17]余思东，万荣泽，黄欣.一种基于随机游走的复杂网络生成[J].计算机应用与软件，2015，32（2）：120-123.

[18]何明，要凯升，杨芃，等.基于标签信息特征相似性的协同过滤个性化推荐[J].计算机科学，2018，45（6）：415-422.

（责任编辑：郭沫含）