基于Wikidata和標簽云的搜索算法研究

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

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

關鍵詞關鍵詞：知識庫； Wikidata； 網頁檢索； 頁面排序； 標簽云； 搜索引擎

DOIDOI：10.11907/rjdk.161447

中圖分類號：TP312

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

0 引言

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

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

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

1 相關工作

1.1 知識庫相關應用

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

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。這類排序方法存在兩個缺陷： ①由于用戶可以隨意定義標簽且語言習慣不同，標簽的內容不夠規(guī)范，準確性有一定欠缺；②覆蓋的資源不足，用戶很可能只對一個網站的主域名標記標簽，而不會對網站中的每一個頁面都完成標簽操作，而實際的檢索過程需要精確到具體頁面。

若直接使用標簽向量來表示頁面，那么向量中的每一個元素的地位都相同，這與實際不符。因此需要在頁面和標簽之間建立相關的主題模型，采用諸如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：//www.wikidata.org/wiki/Wikidata：Glossary上找到。以實體水果蘋果（Q89）為例，可以得到表1中的內容。

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

3.2 網頁搜索模型構建

3.2.1 初始化標簽向量

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

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

3.2.2 主題模型

為了合理表現出詞語含義和標簽向量中各個元素的關系與分布，需要對詞語和標簽向量建立主題模型。 由于選取的標簽已經是人為標記的主題，所以將基于統(tǒng)計的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的大量內容，將詞語轉換為帶有不同權值的標簽，進而將搜索語句和頁面都轉換為標簽向量，通過向量間的匹配來實現最終的排序算法。 實驗結果表明，該算法相比于傳統(tǒng)基于關鍵詞的算法在準確度上有一定提升，能夠創(chuàng)建更多的搜索，保持一定的穩(wě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]劉凱鵬， 方濱興. 一種基于社會性標注的網頁排序算法[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.

（責任編輯：杜能鋼）