基于Wikidata和标签云的搜索算法研究

摘 要：知R库是一种结构化、易于操作、有组织的知识集群。针对Wikidata这一开放知识库的内容及结构，提出一种构建标签云的方法，对信息进行标签化处理，并将转换得到的标签向量应用于信息检索和页面排序。首先，提取Wikidata中的结构化数据，构建以实体为单位的标签云；然后，将需要检索的文档和用户的检索语句映射为相应的标签，并采用处理向量的相关方法实现网页的排序算法；最后，采用信息检索常用的标准对该算法进行验证。实验结果表明，与传统的基于关键词的搜索方法相比，新算法在一定程度上能够提高页面排序的准确率。

关键词关键词：知识库； Wikidata； 网页检索； 页面排序； 标签云； 搜索引擎

DOIDOI：10.11907/rjdk.161447

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）008-0042-04

0 引言

信息呈现几何式爆炸增长，面对如此庞大的信息数量，搜索引擎成为互联网的绝佳入口。目前主流的搜索引擎算法仍以关键词的匹配程度检索，但是相同的词语在不同的语境中有着不同的意义，而不同的人对同样的词语也会有不同的理解， 因此简单地基于关键词的搜索引擎既不能识别出关键词的意义，亦不能从语义的角度进行结果排序。在网页排序算法方面，诸如著名的PageRank[1]、HITS[2]以及结合前两者的SALSA[3]算法都是根据网页间链接的关系进行排序的。 如果仅考虑网页间的链接结构来分析页面的权威性，就容易忽视页面的具体内容并且剥离搜索语句和最终搜索结果之间的联系，从而影响搜索的查全率和查准率。

知识库是一种用来储存结构化知识的数据库。 Wikidata是一个自由、开放、协作的知识库[4]，Wikidata不仅存储对实体的描述，还存储着这些描述的来源和实体间的联系，以结构化的形式存储所有的数据，计算机能够极其便利地获得和处理这些数据。Wikidata拥有超过280种不同语言的知识库数据，尽管对各种语言覆盖的程度不一，但其中的英文内容极其丰富，对于中文也有着不错的支持。Wikidata依托于维基媒体基金会，采用类似于维基百科的管理和编辑方式，能够广泛且准确地反应出用户对实体的理解。本文研究了Wikidata知识库中存储的数据及其结构，提出了一种基于Wikidata和标签云的搜索算法。

本文创新内容包括：①提出一种以知识库为基础构建标签云的方法；②将TF-IDF算法与标签云相结合，提出TC-ITF算法用于计算标签特征权重；③提出基于标签云的网页搜索算法。

1 相关工作

1.1 知识库相关应用

搜索引擎方面，知识库主要应用在知识图谱上。 例如在谷歌的知识图谱[5]中，它能根据各种知识库中的联系为用户提供拥有完整知识体系的搜索结果。这样虽然能摆脱链接分析的禁锢，开辟一种直接提供知识或信息的方式，但是其结果只是在一定体系中的内容，超出该体系结构的知识或信息仍然需要通过搜索其它网站获得。它还垄断图谱的内容、控制结果的权威性。 因此，利用知识库来改进以检索网页为基础的搜索算法仍有很大的发展空间。

1.2 基于标签的排序算法

以标签的形式进行网页排序的方法主要利用社会性标注形成的四元组，相关的算法有Bao等[6]提出的SocialSimRank算法、Hotho等[7]提出的FolkRank算法、Noll等[8]提出的SPEAR算法以及刘凯鹏等[9]提出的利用二部图模型的基于社会性标注网页排序算法等。这类算法都是以名为Folksonomy的社会性标注数据为基础提取相应的内容。Folksonomy描述了用户、资源、标签以及用户对资源分配的标签，形成了如下定义，F：=（U，T，D，R），其中U、T、D分别代表用户、标签、资源或文档，R是前三者的关系，即r=（u，t，d），标识用户u对文档d标注了标签t，用于搜索引擎的数据主要来自书签分享网站del.icio.us。这类排序方法存在两个缺陷： ①由于用户可以随意定义标签且语言习惯不同，标签的内容不够规范，准确性有一定欠缺；②覆盖的资源不足，用户很可能只对一个网站的主域名标记标签，而不会对网站中的每一个页面都完成标签操作，而实际的检索过程需要精确到具体页面。

若直接使用标签向量来表示页面，那么向量中的每一个元素的地位都相同，这与实际不符。因此需要在页面和标签之间建立相关的主题模型，采用诸如TF-IDF[10]、LSI[11]或LDA[12]等主题模型算法。

2 基于Wikidata和标签云的网页搜索框架

本文提出一种基于Wikidata和标签云的搜索算法，其框架如图1所示。

该框架流程分为两个部分：

（1）数据预处理：①建立标签云；②建立一定数量的文档库，若是用于全网检索可以使用爬虫爬取方法；若是站内搜索可以直接使用网站提供的接口来获取精确的文档；③将文档转换为标签向量。

（2）搜索排序：①在用户搜索时，将搜索语句转换为标签向量；②将搜索标签和文档标签进行匹配处理，然后进行排序，得到最终的查询结果。

数据预处理伪代码：

Table 1 Pseudocode for data pretreatment

Input：documentList

Output： doc_vectorList

1： Build_tag-cloud（）

2： for each document in documentList{

3： doc_vector = doc2vec（document）

4： doc_vectorList.add（doc_vector）

5： }

6： return doc_vectorList

搜索排序伪代码：

Table 2 Pseudocode for search and sorting

Input：query，doc_vectorList

Output： result

1： query_vector = query2vec（query）

2： ori_result = search（doc_vectorList，query）

3： result = sort（ori_result）

4： return result

3 网页搜索算法

3.1 标签云构建

本文用到实体、项和属性3个维基数据。

（1）实体是由实体ID唯一标识的维基数据内容，它可以是一个项、属性或者别的内容。一个实体会用不同的语言表述，每个语言还有对应的标签（可以理解为名称）、描述和可能的别名。

（2）项是指现实存在的对象、概念或者事件等内容，以“Q”+数字作为标识。

（3）属性是数据值或关系的描述，它不是数据值本身，以“P”+数字作为标识。 每个实体都会有很多的属性和对应的值，值可以是实体、网页链接、图片声音等。

更加详细的说明可以在网页https：///wiki/Wikidata：Glossary上找到。以实体水果苹果（Q89）为例，可以得到表1中的内容。

本文直接将所有的实体数据下载下来，并且导入数据库中，使用的版本是20150907。此时，维基数据拥有超过15 000 000个实体，其中有1763个属性。通过分析这些属性，将表示从属和被包含关系的属性筛选出来，它们分别是父类（P279）、属于（P361）、性质（P31）和主分类（P910）。同时联系实际搜索需求，把人的职业（P106）也考虑进来。将这些筛选出的属性对应的属性值作为最终的标签云。

3.2 网页搜索模型构建

3.2.1 初始化标签向量

在进行页面检索和排序前需要将页面转换成标签向量。先利用中文分词方法或者英文词干提取方法得到词语；再利用维基数据上的API将分得的词语转换为相应的实体。一个页面对应多个词语，一个词语对应多个实体，一个实体又对应多个标签，见图2（a），图中Ck为页面P中含有词语Wk的个数，其余连线表示的数量均为1，图2（b）同理。

为了消除一个词语通过API获得的相同标签分布不能正确反映因特网中实际的分布问题，将该词语对应的所有标签数量都置为1，得到如图2（b）所示的关系。

3.2.2 主题模型

为了合理表现出词语含义和标签向量中各个元素的关系与分布，需要对词语和标签向量建立主题模型。 由于选取的标签已经是人为标记的主题，所以将基于统计的TF-IDF算法与标签云相结合，提出TC-ITF算法 （Tags Count - Inverse Term Frequency）。 对于某一词语Ti的某一标签tj，有：

3.3 向量匹配和排序

将页面转换为标签向量后，采用相同的方法可以将搜索语句转换为标签向量S（s1，s2，s3，…sn）。根据页面向量和搜索向量中元素的匹配与否来检索页面，再利用余弦相似度来计算搜索语句和各个页面之间的相似度，相似度算法如下：

最后将计算出来的相似度按递减顺序排序，得到最终搜索结果。

4 实验

4.1 实验数据

本文主要研究搜索引擎的排序算法，为了评价算法性能，尤其是对中文的支持度，本文选用了搜狐新闻数据集。

该数据集中的每一条记录包括页面URL、页面ID、页面标题和页面内容，信息分布较为合理，涵盖了政治、经济、科技、文化、体育以及社会生活等方面。

4.2 评价标准

本文采用了信息检索常用的两个评价标准NDCG[13]（Normalized Discounted Cumulative Gain）和MAP（Mean Average Precision）。 假设一共有q个查询，对于某个查询Q，共有n个结果，其中有m个相关结果。若第i个结果是相关的，则r（i）=1，否则r（i）=0。那么查询前i个结果集的查准率（Precision）：

4.3 实验步骤

4.3.1 数据抽样和人工标注

选择了“苹果”、“水果”、“公司”、“手机”、“苹果 水果”、“苹果 公司”、“苹果 手机”这7个搜索语句。 根据含有关键词“苹果”的文档在总文档中的比例，抽样了100条显示包含“苹果”字样的记录和500条没有“苹果”字样的记录， 对这些记录作出一定的划分， 并结合有关评价标准，得到表2和表3。

4.3.2 页面标签向量的生成

使用Python上的jieba中文分词组件对抽样文本进行分词操作。为了提高分词准确率，将维基数据上的实体标签和别名都加入分词词库并去除各种停止词，然后构建标签向量。

4.3.3 排序

建立实验组A和对照组B，A组使用本算法进行排序，B组使用基于关键词的全文检索方法和余弦相似度算法进行排序。

4.4 实验结果与分析

由于用户只注重排名靠前的搜索结果的正确率，所以实验中分别计算了A、B两组在n=20和n=50时的NDCG值和前一百条记录的MAP值。 A、B两组的MAP值分别为0.82182和0.63799。查询的NDCG值和AP值见表4和图3。

5 结语

本文研究了Wikidata知识库的结构和内容，并基于此构建了饲┰疲提出了利用标签云的搜索引擎算法。利用Wikidata的大量内容，将词语转换为带有不同权值的标签，进而将搜索语句和页面都转换为标签向量，通过向量间的匹配来实现最终的排序算法。 实验结果表明，该算法相比于传统基于关键词的算法在准确度上有一定提升，能够创建更多的搜索，保持一定的稳定性。

今后将进一步研究开放式知识库在刻画语义关系方面的作用，以此来改进基于知识库的页面搜索算法，还将研究以标签为中间体的个性化搜索和推荐算法。

参考文献：

[1]BRIN S， PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks & Isdn Systems， 1998， 30（98）：107-117.

[2]KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM （JACM）， 1999， 46（5）： 604-632.

[3]LEMPEL R， MORAN S. SALSA： the stochastic approach for link-structure analysis[J]. ACM Transactions on Information Systems， 2001， 19（2）：131-160.

[4]VRANDECIC D， KROTZSCH M. Wikidata： a free collaborative knowledgebase[J]. Communications of the ACM， 2014， 57（10）： 78-85.

[5]DONG X，GABRILOVICH E，HEITZ G，et al.Knowledge vault：a web-scale approach to probabilistic knowledge fusion[C].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2014：601-610.

[6]BAO S， XUE G， WU X， et al. Optimizing Web search using social annotations[J]. Proc of Www'， 2007：501-510.

[7]HOTHO A， JASCHKE R， SCHMITZ C， et al. Folkrank：a ranking algorithm for folksonomies[J].University of Hildesheim Institute of Computerence， 2006：111-114.

[8]NOLL M G， AU YEUNG C， GIBBINS N， et al. Telling experts from spammers： expertise ranking in folksonomies[C].Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2009：612-619.

[9]刘凯鹏， 方滨兴. 一种基于社会性标注的网页排序算法[J]. 计算机学报， 2010， 33（6）：1014-1023.

[10]SALTON G， WONG A， YANG C S. A vector space model for automatic indexing[J]. Communications of the ACM， 1975， 18（11）： 613-620.

[11]SCOTT D， DUMAIS S T， FURNAS G W， et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science， 1990， 41（6）：391-407.

[12]BLEI D M， NG A Y， JORDAN M I. Latent dirichlet allocation[J]. Journal of Machine Learning Research， 2003（3）：993-1022.

[13]JARVELIN K， KEKALAINEN J. Cumulated gain-based evaluation of IR techniques[J]. Acm Transactions on Information Systems， 2002， 20（4）：422-446.