百科實(shí)例的分類算法探究

王超 蔡潤(rùn)波

摘 要：在互聯(lián)網(wǎng)信息爆炸的時(shí)代，百科成為了互聯(lián)網(wǎng)用戶獲取可信結(jié)構(gòu)化信息的首選途徑，然而，現(xiàn)有的百科文檔的不規(guī)范、概念體系的不健全，造成了相當(dāng)一大部分百科文檔沒能歸入現(xiàn)有概念體系，影響了知識(shí)體系的構(gòu)造和再生。文章以百度百科作為研究對(duì)象，采用基于信息框?qū)傩缘姆诸愃惴ǎ约盎谙嚓P(guān)實(shí)體的分類算法對(duì)百度百科中的未分類文檔進(jìn)行分類，實(shí)驗(yàn)表明，兩種算法都具有較高的分類準(zhǔn)確率，結(jié)合兩種算法能覆蓋除部分只有標(biāo)題信息的絕大部分未分類文檔，因此，能對(duì)百科實(shí)例的分類問題給出較好的解答。

關(guān)鍵詞：百科；分類；信息框；相關(guān)實(shí)體

引言

自互聯(lián)網(wǎng)誕生以來，人類所面臨的信息就呈現(xiàn)著爆炸式的增長(zhǎng)。然而，面對(duì)著浩如煙海的海量信息，人類反而顯得不知所從。搜索引擎出現(xiàn)了，搜索引擎通過關(guān)鍵詞提取及信息檢索技術(shù)，幫助互聯(lián)網(wǎng)用戶迅速地找到信息。然而，這并不能完全滿足互聯(lián)網(wǎng)用戶的需求，因?yàn)榛ヂ?lián)網(wǎng)信息常常是非結(jié)構(gòu)化的——用戶想獲取的信息常常以不同的方式散落在互聯(lián)網(wǎng)的各個(gè)角落——而為了獲取這些完整的信息，用戶不得不翻閱很多網(wǎng)頁，花費(fèi)大量的時(shí)間和精力從這些信息中提取出有用的知識(shí)。如何有效、規(guī)范地定義并描述互聯(lián)網(wǎng)的實(shí)體，以結(jié)構(gòu)化的方式組織互聯(lián)網(wǎng)上的知識(shí)，使得互聯(lián)網(wǎng)上的知識(shí)能夠有效地融合，就顯得尤為迫切而重要。

百科作為互聯(lián)網(wǎng)知識(shí)的經(jīng)典表現(xiàn)形式，借助其開放性，互聯(lián)網(wǎng)的百科文檔成為了眾多互聯(lián)網(wǎng)用戶獲取知識(shí)的首選路徑。然而，正是由于其開放性，互聯(lián)網(wǎng)百科文檔呈現(xiàn)出了諸多不規(guī)范性：如概念體系的不完整，分類體系的不健全，實(shí)際上，目前互聯(lián)網(wǎng)百科文檔中有相當(dāng)一大部分并沒有得到合適的分類，而這造成的結(jié)果是，一方面，對(duì)實(shí)例本身的描述不全面，另一方面，形成知識(shí)的孤島，無法將實(shí)例文檔融入現(xiàn)有的知識(shí)體系，也難以基于該實(shí)例文檔推導(dǎo)出新的知識(shí)。因此，如何在現(xiàn)有百科的開放體系下，解決百科文檔概念體系不完整的問題，進(jìn)而構(gòu)造富有活力的知識(shí)生態(tài)，就顯得尤為重要。

因此，文章將以國(guó)內(nèi)最大的中文知識(shí)庫——百度百科為例，探究如何為未恰當(dāng)標(biāo)注類別的百科文檔添加類別標(biāo)簽，以健全現(xiàn)有百科文檔的知識(shí)體系。

1 問題定義

百科文檔通常呈現(xiàn)半結(jié)構(gòu)化的形式，百科文檔通常由若干個(gè)相對(duì)規(guī)范的部分組成，即標(biāo)題、類別、信息框、摘要、相關(guān)實(shí)體、正文等。因此可以用如下的六元組來表征百科文檔。

d={title，catogories，infobox，abstract，link，essay}

受實(shí)驗(yàn)數(shù)據(jù)限制，在本實(shí)驗(yàn)中，正文項(xiàng)缺失，因此，文章所探討的百科文檔可以僅表示為如下的五元組。

d={title，catogories，infobox，abstract，link}

其中，信息框通常為一系列“鍵-值”對(duì)所構(gòu)成，即信息框可以表示為<鍵，值>對(duì)的集合：

Infobox={（key1，value1），（key2，value2），…（keyn，valuen）}

不妨將其中的鍵所構(gòu)成的集合稱為keysetd。

此外，由于百科分類體系的不規(guī)范，同一個(gè)百科文檔通常會(huì)被歸為多個(gè)不同的類別，因此，類別字段通常也是一個(gè)組合，即由若干類標(biāo)簽構(gòu)成的組合。

catogories={c1，c2，…，cn}

同樣，同一個(gè)百科文檔通常會(huì)與多個(gè)實(shí)體相關(guān)聯(lián)，因此，相關(guān)實(shí)體字段也可以表示為一個(gè)集合，其中的每一個(gè)元素為一個(gè)百科文檔中的實(shí)體，即：

link={ent1，ent2，...，entn}；

文章將探討如何將百度百科中未分類的實(shí)例歸到12個(gè)根類別中，即藝術(shù)、技術(shù)、文化、生活、地理、社會(huì)、人物、經(jīng)濟(jì)、科學(xué)、歷史、自然、體育。因此，將百科的文檔的根類別定義為label，其取值在上述的十二個(gè)根類別當(dāng)中。標(biāo)注的百科文檔為“文檔-標(biāo)簽”對(duì)，即：

ld={d，label}；

因此，可以將文章研究的百科文檔分類問題定義為，尋找函數(shù)映射關(guān)系f，使得給定一個(gè)已標(biāo)注的百科文檔集合LdSet以及另一未標(biāo)注的百科文檔d，輸出文檔的類別屬性l；

f：→l

也可以將該分類過程形式化為兩個(gè)階段：第一階段，給定一個(gè)已標(biāo)注的百科文檔集合，訓(xùn)練出一個(gè)模型；第二階段，給定一個(gè)未分類的百科文檔，基于訓(xùn)練出來的模型即輸入文檔，輸出該文檔的類別屬性，即：

f1：LdSet→Model

f2：→l

下面，我們將對(duì)本章形式化的問題進(jìn)行求解，并對(duì)求解的方法進(jìn)行評(píng)測(cè)。

2 方法描述

實(shí)際上，在本實(shí)驗(yàn)中，初始的數(shù)據(jù)并不是在上一章中所描述的標(biāo)注文檔集以及未標(biāo)注文檔，而是一個(gè)混合的文檔集合--即該文檔包含有類別屬性的文檔和沒有類別屬性的文檔。其中，有類別屬性的文檔通常其類別集合不包含根類別，而這些文檔中有一部分包含根分類的子孫類別屬性，因此，基于百科的概念體系可以掛靠到根類別下，另外一部分文檔則沒有類別屬性，或者是其類別屬性不在現(xiàn)有的百科的概念體系中，因此無法掛靠到根類別下，而這正是文章需要分類的目標(biāo)文檔。因此，下面將首先介紹數(shù)據(jù)的預(yù)處理過程，即將輸入文檔轉(zhuǎn)化為已標(biāo)注的文檔集及未標(biāo)注的文檔集，然后介紹基于該數(shù)據(jù)集定義的兩個(gè)分類算法——基于信息框?qū)傩缘姆诸愃惴?，以及基于相關(guān)實(shí)體的分類算法。

2.1 數(shù)據(jù)的預(yù)處理

本實(shí)驗(yàn)的數(shù)據(jù)輸入為一個(gè)混合的百科文檔集，包括標(biāo)注（但標(biāo)注不規(guī)范）的百科文檔和未標(biāo)注的百科文檔，并將文檔規(guī)范化為<標(biāo)題、類別、信息框、摘要、相關(guān)實(shí)體>五元組。

為了獲取文檔的根類屬性首先必須構(gòu)建百科文檔的概念知識(shí)體系，百科的類別關(guān)系樹，輸入<父類，子類集合>構(gòu)建一棵分類樹，分類樹中的每一條邊表征一個(gè)類別的直接父子關(guān)系。

輸入如下所示：

“Root藝術(shù)；技術(shù)；文化；生活；地理；社會(huì)；人物；經(jīng)濟(jì)；科學(xué)；歷史；自然；體育

體育 體操M(fèi)id；棋牌運(yùn)動(dòng)；田徑運(yùn)動(dòng)；體育周邊；...”

輸出為如圖1所示的分類樹。

圖1

其中中心節(jié)點(diǎn)即概念體系的Root節(jié)點(diǎn)。

構(gòu)建了如上的概念樹之后，輸入一個(gè)百科文檔及其類別屬性集Catogories，我們就可以通過如下的方式獲取其根屬性。

GetRoot（catogories）

foreach type in catogories

root<-GetRootInTree（type）

if root not null then

return root

return null；

end

GetRootInTree（Node）

if node not in Tree

return null；

while parent（node）！=“Root”

node=parent（node）；

return node；

end

基于上述的方法，我們可以獲取一個(gè)輸入文檔的根類別屬性（或者找不到根類別屬性），若能為輸入的文檔找到根類別屬性，則將其加入<文檔，標(biāo)簽>集，若無法找到對(duì)應(yīng)的根類別屬性，則將其加入未分類的文檔集，作為分類的目標(biāo)對(duì)象。

2.2 基于信息框的分類算法

不同類別的百科文檔通常具有不同的屬性：如人物通常有“職業(yè)”，“畢業(yè)院系”等屬性；生活相關(guān)的通常有“主要食材”，“功效”等屬性等等。因此，一個(gè)文檔所具有的信息框?qū)傩酝ǔＤ軌驑?biāo)識(shí)這個(gè)文檔所屬的類別。此外，相比文檔的摘要、正文，信息框?qū)傩缘木S度更低、噪聲也更小，因此，比文檔的摘要和正文通常更具備有標(biāo)識(shí)意義，也能夠獲得更高的分類準(zhǔn)確度。因此，下面將基于文檔的信息框?qū)傩越o出百科文檔的一個(gè)分類算法。

基于信息框?qū)傩缘姆诸愃惴ǖ幕玖鞒倘缦拢?/p>

（1）初始化信息框?qū)傩约螷eySet=？覫

（2）對(duì)輸入的100萬個(gè)百科文檔（本實(shí)驗(yàn)僅研究實(shí)驗(yàn)數(shù)據(jù)中的前100個(gè)百科文檔），提取其信息框?qū)傩裕存I），若該屬性不在集合KeySet中，則將其加入到KeySet中，并置其詞頻為1，否則，將相應(yīng)鍵的詞頻加1。

（3）按照詞頻從高到低，選取前2000個(gè)信息框?qū)傩宰鳛樘卣鳎ǖ?000個(gè)信息框?qū)傩缘某霈F(xiàn)次數(shù)已經(jīng)不足100次）。

（4）初始化12個(gè)類別的特征向量Vec1=（0，0，...，0），...，Vec12=（0，0，...，0），其中每一個(gè)維度對(duì)應(yīng)（3）中選取的一個(gè)信息框?qū)傩浴?/p>

（5）對(duì)于已標(biāo)注文檔集合中的每個(gè)文檔，若其信息框?qū)傩栽冢?）中選取的2000個(gè)屬性中，則將其對(duì)應(yīng)類別的特征的相應(yīng)維度加1。

執(zhí)行完上面五個(gè)步驟之后，我們可以得到12個(gè)類別的特征向量，特征向量的每一個(gè)維度對(duì)應(yīng)一個(gè)信息框?qū)傩?，特征向量表征該類別通常與那些信息框?qū)傩韵嚓P(guān)聯(lián)。

有了12個(gè)類別的特征向量之后，就可以基于這12個(gè)特征向量對(duì)這未分類的文檔進(jìn)行分類了，其方法是：

（1）對(duì)于輸入的文檔，若其沒有信息框?qū)傩?，則直接返回，因?yàn)榛诖朔椒o法給出分類。

（2）提取輸入文檔的信息框?qū)傩?，并將其轉(zhuǎn)換為特征向量，每一維度對(duì)應(yīng)上面選取的一個(gè)信息框?qū)傩裕ü?000個(gè)）。

（3）計(jì)算輸入的文檔的特征向量與12個(gè)類別的特征向量之間的夾角的余弦，并以此表征輸入文檔與各類別之間的相關(guān)性：

Similarity=■

（4）將輸入文檔歸入與之相似性最大的類別中，返回類別標(biāo)簽。

2.3 基于相關(guān)實(shí)體的分類算法

盡管基于信息框?qū)傩缘姆诸愃惴ㄒ呀?jīng)能夠獲取不錯(cuò)的分類準(zhǔn)確度，由于未分類文檔中仍有相當(dāng)大部分的比例沒有信息框?qū)傩裕?00萬文檔約有30萬文檔沒有信息框?qū)傩裕?，上面的基于信息框?qū)傩缘姆诸愃惴o法對(duì)這類文檔進(jìn)行分類，因此，需要提出新的分類算法，對(duì)沒有信息框?qū)傩缘奈臋n進(jìn)行分類。

對(duì)30萬沒有信息框?qū)傩缘奈臋n統(tǒng)計(jì)發(fā)現(xiàn)，其中約有13萬實(shí)例只有標(biāo)題，沒有其他信息，由于這類文檔的信息量太少，分類對(duì)于沒有常識(shí)的計(jì)算機(jī)而言難度太大，在本實(shí)驗(yàn)中不予考慮；有約16萬文檔有相關(guān)實(shí)體屬性，有約5萬實(shí)例有摘要屬性，考慮到摘要屬性的詞頻信息更稀疏，噪聲更大，而相關(guān)實(shí)體屬性基本上能覆蓋除了13萬只有標(biāo)題的文檔外的絕大部分文檔，噪聲也更小，因此，本實(shí)驗(yàn)選取相關(guān)實(shí)體屬性對(duì)剩下的實(shí)例進(jìn)行分類。

為了基于相關(guān)實(shí)體進(jìn)行分類，首先我們必須獲取<實(shí)體，根類別>庫，即2.1中得到的標(biāo)注文檔集合，僅取其標(biāo)題（實(shí)體名）和根類別標(biāo)簽構(gòu)成<實(shí)體、根類別>庫。

對(duì)于輸入的每一個(gè)文檔，若其包含相關(guān)實(shí)體屬性，對(duì)其中的每一個(gè)實(shí)體，若其屬于根類別Ci，認(rèn)為該實(shí)例通過相關(guān)實(shí)體和根類別之間有一條邊。最后，將文檔實(shí)例歸入與其連邊最多的根類別。即認(rèn)為，該文檔與哪一個(gè)類別中的最多實(shí)例相關(guān)聯(lián)，則該文檔屬于該類別——基于同一個(gè)類別內(nèi)的實(shí)體之間的關(guān)聯(lián)大于類別間的實(shí)體的關(guān)聯(lián)的假設(shè)。

3 方法評(píng)測(cè)

在上文中，我們給出了基于信息框?qū)傩砸约盎谙嚓P(guān)實(shí)體的兩個(gè)分類算法。下面，將對(duì)這兩個(gè)算法進(jìn)行評(píng)測(cè)。

表1為經(jīng)過2.1數(shù)據(jù)預(yù)處理后（即根據(jù)實(shí)例的類別信息標(biāo)注其根類別）后，各個(gè)類別的實(shí)例數(shù)：

表1

從表1中可以看出，在現(xiàn)有的百科概念體系下，有約31.5%的實(shí)例無法掛靠到任意一個(gè)根類別下。因此，給出一個(gè)百科實(shí)例的分類算法是必要而且重要的。

因此，文章提出了基于信息框?qū)傩院突谙嚓P(guān)實(shí)體的分類算法。

表2為運(yùn)行文章提出的基于信息框?qū)傩缘姆诸愃惴ㄖ?，各個(gè)類別中的實(shí)例個(gè)數(shù)（僅針對(duì)在步驟1中無法區(qū)分根類別的314527個(gè)實(shí)體）。

表2

表2可以看出，由于未分類文檔中大部分文檔沒有類別屬性，因此，大部分未分類實(shí)體無法在這一步中給出根類別屬性。

那基于信息框?qū)傩缘姆诸愃惴ǖ臏?zhǔn)確率如何呢？

表3是基于信息框?qū)傩缘姆诸愃惴ǖ玫降奈幕瘜?shí)例的前10個(gè)實(shí)例：

表3

可以看出前十個(gè)實(shí)例都是屬于文化類的，其中除了“民間敘述詩”之外，其他都是書籍或者書籍相關(guān)的簡(jiǎn)介。

表4是基于信息框?qū)傩缘姆诸愃惴ńo出的人物實(shí)例的前10個(gè)實(shí)例：

表4

從表4可以看出，算法給出的10個(gè)實(shí)例都是屬于人物類別的。由此可以，基于信息框的屬性雖然召回率較低（受多數(shù)百科文檔沒有信息框?qū)傩韵拗疲瞧錅?zhǔn)確率還是很高的。

針對(duì)基于信息框?qū)傩缘姆诸愃惴o法完成分類的299940個(gè)文檔，我們使用了基于關(guān)聯(lián)實(shí)體的分類算法進(jìn)行分類，在2.2中已經(jīng)提到，針對(duì)約30萬未分類的文檔，除去約13萬僅有標(biāo)題的文檔之后，其余有16萬文檔包含相關(guān)實(shí)體屬性，因此基于相關(guān)屬性的分類算法基本上能覆蓋計(jì)算機(jī)所能分類的實(shí)體的大部分，由此，可以彌補(bǔ)基于信息框?qū)傩缘姆诸惙椒ㄕ倩芈瘦^低的劣勢(shì)。

表5是基于相關(guān)實(shí)體的分類算法給出的經(jīng)濟(jì)類的前10個(gè)實(shí)例：

表5

可以看出，給出的十個(gè)實(shí)例中，有兩個(gè)分錯(cuò)的實(shí)例，即“王鐸（北京大學(xué)教授）”以及“沙鷗（鳥類）”，其中王鐸（北京大學(xué)教授）是一位在北大教金融的老師，所以也是在經(jīng)濟(jì)圈的人物，所以從廣義上講，盡管將該實(shí)例分為人物更恰當(dāng)，但將其歸為經(jīng)濟(jì)類的一個(gè)實(shí)例也未嘗不可。因此，整體上來說，基于相關(guān)實(shí)體的分類算法的準(zhǔn)確度還是比較高的。

綜上可知，基于信息框?qū)傩缘姆诸愃惴ň哂休^高的精確度，但受限于大部分未分類的百科文檔沒有信息框?qū)傩裕倩芈瘦^低，而基于相關(guān)實(shí)體的分類算法能覆蓋絕大部分計(jì)算機(jī)“能分”（除去13萬只有標(biāo)題的實(shí)例），其精確度雖然比基于信息框?qū)傩缘姆椒缘鸵稽c(diǎn)，但是還是維持在比較高的水平，結(jié)合兩者的優(yōu)點(diǎn)，基本上能夠?qū)Π倏莆臋n中的未分類實(shí)例進(jìn)行較為準(zhǔn)確的分類。

4 結(jié)束語

文章以百度百科作為研究對(duì)象，力圖給出一個(gè)分類算法，能對(duì)百科中未分類的文檔進(jìn)行合理的歸類，以此完善現(xiàn)有的知識(shí)體系?；谛畔⒖?qū)傩跃哂休^強(qiáng)的標(biāo)識(shí)意義，噪聲較小，實(shí)驗(yàn)表明，該方法具有較高的分類準(zhǔn)確率，但首先于大部分文檔沒有信息框?qū)傩?，無法解決所有文檔的分類問題。因此，文章提出了基于相關(guān)實(shí)體的分類算法，該算法能覆蓋除只有標(biāo)題的文檔外的絕大部分未分類文檔，并具有較高的分類準(zhǔn)確率，結(jié)合這兩個(gè)方法，基本能解決百科文檔的分類問題。當(dāng)然，我們也意識(shí)到在分類結(jié)果中，仍然存在少數(shù)分錯(cuò)的實(shí)例，因此，算法仍然存在提升的空間，一方面，我們可以充分利用除了信息框?qū)傩院拖嚓P(guān)實(shí)體屬性外的其他屬性（如標(biāo)題屬性）。此外，我們也可以進(jìn)一步改進(jìn)我們的算法以獲得更高的準(zhǔn)確率及召回率。

文章通過對(duì)國(guó)內(nèi)最大的中文知識(shí)庫——百度百科的內(nèi)容進(jìn)行分析和改進(jìn)讓我們初步體會(huì)到了人可閱讀的知識(shí)與對(duì)機(jī)器可閱讀的知識(shí)之間的鴻溝。隨著信息爆炸的時(shí)代來臨，知識(shí)越來越需要能被機(jī)器理解，相信知識(shí)工程將會(huì)有更多的工具和更好的方法出現(xiàn)。