夏瑀+葛佳琦+馬秀+曹際全+李海巍

摘 要：知識(shí)庫(kù)是一種結(jié)構(gòu)化、易于操作、有組織的知識(shí)集群。針對(duì)Wikidata這一開放知識(shí)庫(kù)的內(nèi)容及結(jié)構(gòu)，提出一種構(gòu)建標(biāo)簽云的方法，對(duì)信息進(jìn)行標(biāo)簽化處理，并將轉(zhuǎn)換得到的標(biāo)簽向量應(yīng)用于信息檢索和頁(yè)面排序。首先，提取Wikidata中的結(jié)構(gòu)化數(shù)據(jù)，構(gòu)建以實(shí)體為單位的標(biāo)簽云；然后，將需要檢索的文檔和用戶的檢索語(yǔ)句映射為相應(yīng)的標(biāo)簽，并采用處理向量的相關(guān)方法實(shí)現(xiàn)網(wǎng)頁(yè)的排序算法；最后，采用信息檢索常用的標(biāo)準(zhǔn)對(duì)該算法進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的基于關(guān)鍵詞的搜索方法相比，新算法在一定程度上能夠提高頁(yè)面排序的準(zhǔn)確率。

關(guān)鍵詞關(guān)鍵詞：知識(shí)庫(kù)； Wikidata； 網(wǎng)頁(yè)檢索； 頁(yè)面排序； 標(biāo)簽云； 搜索引擎

DOIDOI：10.11907/rjdk.161447

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2016）008-0042-04

0 引言

信息呈現(xiàn)幾何式爆炸增長(zhǎng)，面對(duì)如此龐大的信息數(shù)量，搜索引擎成為互聯(lián)網(wǎng)的絕佳入口。目前主流的搜索引擎算法仍以關(guān)鍵詞的匹配程度檢索，但是相同的詞語(yǔ)在不同的語(yǔ)境中有著不同的意義，而不同的人對(duì)同樣的詞語(yǔ)也會(huì)有不同的理解， 因此簡(jiǎn)單地基于關(guān)鍵詞的搜索引擎既不能識(shí)別出關(guān)鍵詞的意義，亦不能從語(yǔ)義的角度進(jìn)行結(jié)果排序。在網(wǎng)頁(yè)排序算法方面，諸如著名的PageRank[1]、HITS[2]以及結(jié)合前兩者的SALSA[3]算法都是根據(jù)網(wǎng)頁(yè)間鏈接的關(guān)系進(jìn)行排序的。 如果僅考慮網(wǎng)頁(yè)間的鏈接結(jié)構(gòu)來(lái)分析頁(yè)面的權(quán)威性，就容易忽視頁(yè)面的具體內(nèi)容并且剝離搜索語(yǔ)句和最終搜索結(jié)果之間的聯(lián)系，從而影響搜索的查全率和查準(zhǔn)率。

知識(shí)庫(kù)是一種用來(lái)儲(chǔ)存結(jié)構(gòu)化知識(shí)的數(shù)據(jù)庫(kù)。 Wikidata是一個(gè)自由、開放、協(xié)作的知識(shí)庫(kù)[4]，Wikidata不僅存儲(chǔ)對(duì)實(shí)體的描述，還存儲(chǔ)著這些描述的來(lái)源和實(shí)體間的聯(lián)系，以結(jié)構(gòu)化的形式存儲(chǔ)所有的數(shù)據(jù)，計(jì)算機(jī)能夠極其便利地獲得和處理這些數(shù)據(jù)。Wikidata擁有超過(guò)280種不同語(yǔ)言的知識(shí)庫(kù)數(shù)據(jù)，盡管對(duì)各種語(yǔ)言覆蓋的程度不一，但其中的英文內(nèi)容極其豐富，對(duì)于中文也有著不錯(cuò)的支持。Wikidata依托于維基媒體基金會(huì)，采用類似于維基百科的管理和編輯方式，能夠廣泛且準(zhǔn)確地反應(yīng)出用戶對(duì)實(shí)體的理解。本文研究了Wikidata知識(shí)庫(kù)中存儲(chǔ)的數(shù)據(jù)及其結(jié)構(gòu)，提出了一種基于Wikidata和標(biāo)簽云的搜索算法。

本文創(chuàng)新內(nèi)容包括：①提出一種以知識(shí)庫(kù)為基礎(chǔ)構(gòu)建標(biāo)簽云的方法；②將TF-IDF算法與標(biāo)簽云相結(jié)合，提出TC-ITF算法用于計(jì)算標(biāo)簽特征權(quán)重；③提出基于標(biāo)簽云的網(wǎng)頁(yè)搜索算法。

1 相關(guān)工作

1.1 知識(shí)庫(kù)相關(guān)應(yīng)用

搜索引擎方面，知識(shí)庫(kù)主要應(yīng)用在知識(shí)圖譜上。 例如在谷歌的知識(shí)圖譜[5]中，它能根據(jù)各種知識(shí)庫(kù)中的聯(lián)系為用戶提供擁有完整知識(shí)體系的搜索結(jié)果。這樣雖然能擺脫鏈接分析的禁錮，開辟一種直接提供知識(shí)或信息的方式，但是其結(jié)果只是在一定體系中的內(nèi)容，超出該體系結(jié)構(gòu)的知識(shí)或信息仍然需要通過(guò)搜索其它網(wǎng)站獲得。它還壟斷圖譜的內(nèi)容、控制結(jié)果的權(quán)威性。 因此，利用知識(shí)庫(kù)來(lái)改進(jìn)以檢索網(wǎng)頁(yè)為基礎(chǔ)的搜索算法仍有很大的發(fā)展空間。

1.2 基于標(biāo)簽的排序算法

以標(biāo)簽的形式進(jìn)行網(wǎng)頁(yè)排序的方法主要利用社會(huì)性標(biāo)注形成的四元組，相關(guān)的算法有Bao等[6]提出的SocialSimRank算法、Hotho等[7]提出的FolkRank算法、Noll等[8]提出的SPEAR算法以及劉凱鵬等[9]提出的利用二部圖模型的基于社會(huì)性標(biāo)注網(wǎng)頁(yè)排序算法等。這類算法都是以名為Folksonomy的社會(huì)性標(biāo)注數(shù)據(jù)為基礎(chǔ)提取相應(yīng)的內(nèi)容。Folksonomy描述了用戶、資源、標(biāo)簽以及用戶對(duì)資源分配的標(biāo)簽，形成了如下定義，F(xiàn)：=（U，T，D，R），其中U、T、D分別代表用戶、標(biāo)簽、資源或文檔，R是前三者的關(guān)系，即r=（u，t，d），標(biāo)識(shí)用戶u對(duì)文檔d標(biāo)注了標(biāo)簽t，用于搜索引擎的數(shù)據(jù)主要來(lái)自書簽分享網(wǎng)站del.icio.us。這類排序方法存在兩個(gè)缺陷： ①由于用戶可以隨意定義標(biāo)簽且語(yǔ)言習(xí)慣不同，標(biāo)簽的內(nèi)容不夠規(guī)范，準(zhǔn)確性有一定欠缺；②覆蓋的資源不足，用戶很可能只對(duì)一個(gè)網(wǎng)站的主域名標(biāo)記標(biāo)簽，而不會(huì)對(duì)網(wǎng)站中的每一個(gè)頁(yè)面都完成標(biāo)簽操作，而實(shí)際的檢索過(guò)程需要精確到具體頁(yè)面。

若直接使用標(biāo)簽向量來(lái)表示頁(yè)面，那么向量中的每一個(gè)元素的地位都相同，這與實(shí)際不符。因此需要在頁(yè)面和標(biāo)簽之間建立相關(guān)的主題模型，采用諸如TF-IDF[10]、LSI[11]或LDA[12]等主題模型算法。

2 基于Wikidata和標(biāo)簽云的網(wǎng)頁(yè)搜索框架

本文提出一種基于Wikidata和標(biāo)簽云的搜索算法，其框架如圖1所示。

該框架流程分為兩個(gè)部分：

（1）數(shù)據(jù)預(yù)處理：①建立標(biāo)簽云；②建立一定數(shù)量的文檔庫(kù)，若是用于全網(wǎng)檢索可以使用爬蟲爬取方法；若是站內(nèi)搜索可以直接使用網(wǎng)站提供的接口來(lái)獲取精確的文檔；③將文檔轉(zhuǎn)換為標(biāo)簽向量。

（2）搜索排序：①在用戶搜索時(shí)，將搜索語(yǔ)句轉(zhuǎn)換為標(biāo)簽向量；②將搜索標(biāo)簽和文檔標(biāo)簽進(jìn)行匹配處理，然后進(jìn)行排序，得到最終的查詢結(jié)果。

數(shù)據(jù)預(yù)處理偽代碼：

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 網(wǎng)頁(yè)搜索算法

3.1 標(biāo)簽云構(gòu)建

本文用到實(shí)體、項(xiàng)和屬性3個(gè)維基數(shù)據(jù)。

（1）實(shí)體是由實(shí)體ID唯一標(biāo)識(shí)的維基數(shù)據(jù)內(nèi)容，它可以是一個(gè)項(xiàng)、屬性或者別的內(nèi)容。一個(gè)實(shí)體會(huì)用不同的語(yǔ)言表述，每個(gè)語(yǔ)言還有對(duì)應(yīng)的標(biāo)簽（可以理解為名稱）、描述和可能的別名。

（2）項(xiàng)是指現(xiàn)實(shí)存在的對(duì)象、概念或者事件等內(nèi)容，以“Q”+數(shù)字作為標(biāo)識(shí)。

（3）屬性是數(shù)據(jù)值或關(guān)系的描述，它不是數(shù)據(jù)值本身，以“P”+數(shù)字作為標(biāo)識(shí)。 每個(gè)實(shí)體都會(huì)有很多的屬性和對(duì)應(yīng)的值，值可以是實(shí)體、網(wǎng)頁(yè)鏈接、圖片聲音等。

更加詳細(xì)的說(shuō)明可以在網(wǎng)頁(yè)https：//www.wikidata.org/wiki/Wikidata：Glossary上找到。以實(shí)體水果蘋果（Q89）為例，可以得到表1中的內(nèi)容。

本文直接將所有的實(shí)體數(shù)據(jù)下載下來(lái)，并且導(dǎo)入數(shù)據(jù)庫(kù)中，使用的版本是20150907。此時(shí)，維基數(shù)據(jù)擁有超過(guò)15 000 000個(gè)實(shí)體，其中有1763個(gè)屬性。通過(guò)分析這些屬性，將表示從屬和被包含關(guān)系的屬性篩選出來(lái)，它們分別是父類（P279）、屬于（P361）、性質(zhì)（P31）和主分類（P910）。同時(shí)聯(lián)系實(shí)際搜索需求，把人的職業(yè)（P106）也考慮進(jìn)來(lái)。將這些篩選出的屬性對(duì)應(yīng)的屬性值作為最終的標(biāo)簽云。

3.2 網(wǎng)頁(yè)搜索模型構(gòu)建

3.2.1 初始化標(biāo)簽向量

在進(jìn)行頁(yè)面檢索和排序前需要將頁(yè)面轉(zhuǎn)換成標(biāo)簽向量。先利用中文分詞方法或者英文詞干提取方法得到詞語(yǔ)；再利用維基數(shù)據(jù)上的API將分得的詞語(yǔ)轉(zhuǎn)換為相應(yīng)的實(shí)體。一個(gè)頁(yè)面對(duì)應(yīng)多個(gè)詞語(yǔ)，一個(gè)詞語(yǔ)對(duì)應(yīng)多個(gè)實(shí)體，一個(gè)實(shí)體又對(duì)應(yīng)多個(gè)標(biāo)簽，見圖2（a），圖中Ck為頁(yè)面P中含有詞語(yǔ)Wk的個(gè)數(shù)，其余連線表示的數(shù)量均為1，圖2（b）同理。

為了消除一個(gè)詞語(yǔ)通過(guò)API獲得的相同標(biāo)簽分布不能正確反映因特網(wǎng)中實(shí)際的分布問(wèn)題，將該詞語(yǔ)對(duì)應(yīng)的所有標(biāo)簽數(shù)量都置為1，得到如圖2（b）所示的關(guān)系。

3.2.2 主題模型

為了合理表現(xiàn)出詞語(yǔ)含義和標(biāo)簽向量中各個(gè)元素的關(guān)系與分布，需要對(duì)詞語(yǔ)和標(biāo)簽向量建立主題模型。 由于選取的標(biāo)簽已經(jīng)是人為標(biāo)記的主題，所以將基于統(tǒng)計(jì)的TF-IDF算法與標(biāo)簽云相結(jié)合，提出TC-ITF算法 （Tags Count - Inverse Term Frequency）。 對(duì)于某一詞語(yǔ)Ti的某一標(biāo)簽tj，有：

3.3 向量匹配和排序

將頁(yè)面轉(zhuǎn)換為標(biāo)簽向量后，采用相同的方法可以將搜索語(yǔ)句轉(zhuǎn)換為標(biāo)簽向量S（s1，s2，s3，…sn）。根據(jù)頁(yè)面向量和搜索向量中元素的匹配與否來(lái)檢索頁(yè)面，再利用余弦相似度來(lái)計(jì)算搜索語(yǔ)句和各個(gè)頁(yè)面之間的相似度，相似度算法如下：

最后將計(jì)算出來(lái)的相似度按遞減順序排序，得到最終搜索結(jié)果。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文主要研究搜索引擎的排序算法，為了評(píng)價(jià)算法性能，尤其是對(duì)中文的支持度，本文選用了搜狐新聞數(shù)據(jù)集。

該數(shù)據(jù)集中的每一條記錄包括頁(yè)面URL、頁(yè)面ID、頁(yè)面標(biāo)題和頁(yè)面內(nèi)容，信息分布較為合理，涵蓋了政治、經(jīng)濟(jì)、科技、文化、體育以及社會(huì)生活等方面。

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用了信息檢索常用的兩個(gè)評(píng)價(jià)標(biāo)準(zhǔn)NDCG[13]（Normalized Discounted Cumulative Gain）和MAP（Mean Average Precision）。 假設(shè)一共有q個(gè)查詢，對(duì)于某個(gè)查詢Q，共有n個(gè)結(jié)果，其中有m個(gè)相關(guān)結(jié)果。若第i個(gè)結(jié)果是相關(guān)的，則r（i）=1，否則r（i）=0。那么查詢前i個(gè)結(jié)果集的查準(zhǔn)率（Precision）：

4.3 實(shí)驗(yàn)步驟

4.3.1 數(shù)據(jù)抽樣和人工標(biāo)注

選擇了“蘋果”、“水果”、“公司”、“手機(jī)”、“蘋果 水果”、“蘋果 公司”、“蘋果 手機(jī)”這7個(gè)搜索語(yǔ)句。 根據(jù)含有關(guān)鍵詞“蘋果”的文檔在總文檔中的比例，抽樣了100條顯示包含“蘋果”字樣的記錄和500條沒(méi)有“蘋果”字樣的記錄， 對(duì)這些記錄作出一定的劃分， 并結(jié)合有關(guān)評(píng)價(jià)標(biāo)準(zhǔn)，得到表2和表3。

4.3.2 頁(yè)面標(biāo)簽向量的生成

使用Python上的jieba中文分詞組件對(duì)抽樣文本進(jìn)行分詞操作。為了提高分詞準(zhǔn)確率，將維基數(shù)據(jù)上的實(shí)體標(biāo)簽和別名都加入分詞詞庫(kù)并去除各種停止詞，然后構(gòu)建標(biāo)簽向量。

4.3.3 排序

建立實(shí)驗(yàn)組A和對(duì)照組B，A組使用本算法進(jìn)行排序，B組使用基于關(guān)鍵詞的全文檢索方法和余弦相似度算法進(jìn)行排序。

4.4 實(shí)驗(yàn)結(jié)果與分析

由于用戶只注重排名靠前的搜索結(jié)果的正確率，所以實(shí)驗(yàn)中分別計(jì)算了A、B兩組在n=20和n=50時(shí)的NDCG值和前一百條記錄的MAP值。 A、B兩組的MAP值分別為0.82182和0.63799。查詢的NDCG值和AP值見表4和圖3。

5 結(jié)語(yǔ)

本文研究了Wikidata知識(shí)庫(kù)的結(jié)構(gòu)和內(nèi)容，并基于此構(gòu)建了標(biāo)簽云，提出了利用標(biāo)簽云的搜索引擎算法。利用Wikidata的大量?jī)?nèi)容，將詞語(yǔ)轉(zhuǎn)換為帶有不同權(quán)值的標(biāo)簽，進(jìn)而將搜索語(yǔ)句和頁(yè)面都轉(zhuǎn)換為標(biāo)簽向量，通過(guò)向量間的匹配來(lái)實(shí)現(xiàn)最終的排序算法。 實(shí)驗(yàn)結(jié)果表明，該算法相比于傳統(tǒng)基于關(guān)鍵詞的算法在準(zhǔn)確度上有一定提升，能夠創(chuàng)建更多的搜索，保持一定的穩(wěn)定性。

今后將進(jìn)一步研究開放式知識(shí)庫(kù)在刻畫語(yǔ)義關(guān)系方面的作用，以此來(lái)改進(jìn)基于知識(shí)庫(kù)的頁(yè)面搜索算法，還將研究以標(biāo)簽為中間體的個(gè)性化搜索和推薦算法。

參考文獻(xiàn)：

[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]劉凱鵬， 方濱興. 一種基于社會(huì)性標(biāo)注的網(wǎng)頁(yè)排序算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.

（責(zé)任編輯：杜能鋼）