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

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

關(guān)鍵詞關(guān)鍵詞：知識庫； Wikidata； 網(wǎng)頁檢索； 頁面排序； 標簽云； 搜索引擎

DOIDOI：10.11907/rjdk.161447

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）008-0042-04

0 引言

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

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

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

1 相關(guān)工作

1.1 知識庫相關(guān)應用

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

1.2 基于標簽的排序算法

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

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

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

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

該框架流程分為兩個部分：

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

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

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

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)頁搜索算法

3.1 標簽云構(gòu)建

本文用到實體、項和屬性3個維基數(shù)據(jù)。

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

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

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

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

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

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

3.2.1 初始化標簽向量

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

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

3.2.2 主題模型

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

3.3 向量匹配和排序

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

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

4 實驗

4.1 實驗數(shù)據(jù)

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

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

4.2 評價標準

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

4.3 實驗步驟

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

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

4.3.2 頁面標簽向量的生成

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

4.3.3 排序

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

4.4 實驗結(jié)果與分析

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

5 結(jié)語

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

今后將進一步研究開放式知識庫在刻畫語義關(guā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]劉凱鵬， 方濱興. 一種基于社會性標注的網(wǎng)頁排序算法[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.

（責任編輯：杜能鋼）