陳小紅 陳環(huán)環(huán) 方之家 阮 彤 王昊奮

1(盛大游戲 上海 201203)2(華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系 上海 200237)

基于領(lǐng)域本體的游戲攻略文本標(biāo)注算法研究與實(shí)現(xiàn)

陳小紅1陳環(huán)環(huán)2方之家2阮 彤2王昊奮2

1(盛大游戲 上海 201203)2(華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系 上海 200237)

游戲門戶網(wǎng)站為提升玩家們的游戲體驗(yàn),建立了大量站點(diǎn)用以提供游戲資訊及相關(guān)攻略。然而這些站點(diǎn)間異構(gòu)現(xiàn)象明顯，且缺乏統(tǒng)一的知識(shí)體系。提出基于領(lǐng)域本體的文本標(biāo)注算法，通過(guò)融合站點(diǎn)間的數(shù)據(jù)，構(gòu)建游戲領(lǐng)域本體。同時(shí)，針對(duì)游戲領(lǐng)域的應(yīng)用，優(yōu)化了新詞發(fā)現(xiàn)算法，并進(jìn)一步對(duì)攻略文本進(jìn)行語(yǔ)義標(biāo)注。通過(guò)這些語(yǔ)義標(biāo)簽，不僅能直觀地了解攻略中的內(nèi)容，也能更好地為攻略文本的語(yǔ)義檢索服務(wù)。實(shí)驗(yàn)證明，所提出的本體構(gòu)建方法在游戲領(lǐng)域具有一定的推廣性，同時(shí)游戲領(lǐng)域詞匯發(fā)現(xiàn)算法與傳統(tǒng)的分詞工具相比也取得了更好的結(jié)果。

領(lǐng)域本體 游戲領(lǐng)域詞匯發(fā)現(xiàn)算法 語(yǔ)義標(biāo)注

0 引 言

隨著游戲產(chǎn)業(yè)在我國(guó)迅速的發(fā)展，游戲的種類和數(shù)量也在不斷地增加。為了能夠讓玩家對(duì)游戲有一個(gè)更為全面的認(rèn)識(shí)，各大游戲資訊網(wǎng)站都開發(fā)了自己的游戲攻略主頁(yè)。在這些站點(diǎn)中，不僅描述了各個(gè)游戲的基礎(chǔ)知識(shí)，還有大量玩家自己撰寫的游戲攻略。游戲玩家通過(guò)閱讀這些游戲攻略，可以快速入門，并且掌握大量與游戲相關(guān)的進(jìn)階知識(shí)，可以有效地提升玩家的游戲體驗(yàn)。

然而，對(duì)于目前大多數(shù)的主流游戲而言，游戲攻略大多分散在各大資訊網(wǎng)站之中。當(dāng)玩家需要查閱攻略時(shí)，通常需要輾轉(zhuǎn)于多個(gè)資訊網(wǎng)站之間進(jìn)行檢索。同時(shí)，只有部分資訊網(wǎng)站提供了攻略搜索功能，玩家需要耗費(fèi)大量時(shí)間去尋找與自己的游戲內(nèi)容相關(guān)的攻略。這些問題不同程度降低了這些資訊網(wǎng)站的用戶體驗(yàn)。為了能夠解決這些問題，本文提出了一種基于領(lǐng)域本體的游戲攻略文本標(biāo)注算法。使用本體建立起一套統(tǒng)一的描述方法，從而融合了各大資訊網(wǎng)站以及游戲內(nèi)部的數(shù)據(jù)?；谠摫倔w，可以有效地通過(guò)實(shí)體鏈接的思想，將攻略中的文本內(nèi)容映射到本體中的相關(guān)概念，從而達(dá)到語(yǔ)義標(biāo)注的目的。玩家可以通過(guò)這些語(yǔ)義標(biāo)簽，更快更全面地了解到攻略中所包含的信息，以便更快地定位到與自己相關(guān)的游戲內(nèi)容；同時(shí)語(yǔ)義標(biāo)簽的生成，還可以為這些游戲站點(diǎn)構(gòu)建更高效、更有實(shí)用價(jià)值的語(yǔ)義搜索系統(tǒng)，為玩家們提供更為精準(zhǔn)的檢索服務(wù)。

本文的主要貢獻(xiàn)有以下幾點(diǎn)：

(1) 針對(duì)資訊網(wǎng)站間的數(shù)據(jù)異構(gòu)問題，提出了使用本體進(jìn)行建模的思想。通過(guò)對(duì)游戲數(shù)據(jù)庫(kù)、資訊網(wǎng)站導(dǎo)航頁(yè)面以及玩家論壇中的數(shù)據(jù)進(jìn)行融合，從而針對(duì)游戲內(nèi)容本身構(gòu)建了一個(gè)統(tǒng)一的本體。

(2) 在原有的基于大規(guī)模語(yǔ)料的領(lǐng)域詞匯發(fā)現(xiàn)算法[1]的基礎(chǔ)上，本文針對(duì)游戲術(shù)語(yǔ)簡(jiǎn)稱、游戲內(nèi)容用語(yǔ)等游戲領(lǐng)域詞匯的用法及規(guī)則進(jìn)行了優(yōu)化，并生成了一系列可用于實(shí)體鏈接的錨文本。

(3) 基于實(shí)體鏈接[2]的思想，提出了對(duì)游戲攻略文本進(jìn)行語(yǔ)義標(biāo)注的算法。利用已構(gòu)建好的游戲本體中的層次結(jié)構(gòu)以及實(shí)例集合，對(duì)由錨文本所產(chǎn)生的候選歧義實(shí)體進(jìn)行去歧義，選擇最為契合的實(shí)體作為鏈接實(shí)體，從而生成語(yǔ)義標(biāo)簽。

1 相關(guān)工作

文本中的術(shù)語(yǔ)大多以簡(jiǎn)稱的形式存在，因此需要構(gòu)建游戲領(lǐng)域知識(shí)庫(kù)存儲(chǔ)術(shù)語(yǔ)全稱，從而和文本建立一一映射關(guān)系。DBpedia、Freebase、YAGO都是通用知識(shí)庫(kù)，包含了豐富的數(shù)據(jù)，但是缺乏游戲領(lǐng)域知識(shí)。DBpedia[9]是從維基百科中自動(dòng)抽取結(jié)構(gòu)化信息，被廣泛用于語(yǔ)義萬(wàn)維網(wǎng)和商業(yè)環(huán)境。Freebase[10]所有內(nèi)容由用戶添加，所有條目都采用結(jié)構(gòu)化數(shù)據(jù)的格式。YAGO[11]主要信息來(lái)源于維基百科，具有足夠高的準(zhǔn)確度和覆蓋度。本文所建的知識(shí)庫(kù)和以上幾個(gè)知識(shí)庫(kù)相似，都是從互聯(lián)網(wǎng)資源及百科資源進(jìn)行數(shù)據(jù)融合得到。故本文針對(duì)游戲領(lǐng)域，從三個(gè)不同數(shù)據(jù)源爬取了游戲領(lǐng)域相關(guān)知識(shí)，構(gòu)建了游戲領(lǐng)域知識(shí)庫(kù)。

文本標(biāo)注技術(shù)是信息抽取的一個(gè)應(yīng)用，在過(guò)去的幾年中得到了廣泛的研究。Mihalcea等[3]提出了排序算法TextRank，主要思想是將文本看成一個(gè)詞的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的鏈接表示詞與詞之間的語(yǔ)義關(guān)系，但是該方法不適用于稀疏文本。Park等[4]等提出了基于sigmoid貝葉斯模型的關(guān)鍵詞自動(dòng)抽取方法，解決了數(shù)據(jù)稀疏的問題，然而該方法要求數(shù)據(jù)值必須遵循sigmoid分布才能在貝葉斯結(jié)構(gòu)中表現(xiàn)出來(lái)，具有局限性。本文面向的是游戲領(lǐng)域，游戲攻略內(nèi)容表述比較偏口語(yǔ)化，直接提取關(guān)鍵詞或主題詞比較困難，且攻略標(biāo)題包含大量游戲術(shù)語(yǔ)，因此提出了通過(guò)提取文本數(shù)據(jù)中游戲術(shù)語(yǔ)作為文本標(biāo)簽的思想。

術(shù)語(yǔ)抽取是本文攻略文本標(biāo)注的關(guān)鍵技術(shù)，現(xiàn)有的領(lǐng)域術(shù)語(yǔ)研究主要分為：基于規(guī)則的方法、基于統(tǒng)計(jì)的方法和規(guī)則與統(tǒng)計(jì)相結(jié)合的方法?；谝?guī)則的方法主要利用術(shù)語(yǔ)詞典和規(guī)則模板來(lái)進(jìn)行術(shù)語(yǔ)抽取。Buitelaar等[5]提出利用不同詞性的組合規(guī)則得到名詞性詞組，然后利用過(guò)濾算法得到領(lǐng)域術(shù)語(yǔ)。基于規(guī)則的方法比較簡(jiǎn)單，但是要求規(guī)則編寫人員具有豐富的語(yǔ)言知識(shí)?；诮y(tǒng)計(jì)的方法是利用術(shù)語(yǔ)內(nèi)部各組成成分之間較高的關(guān)聯(lián)程度及術(shù)語(yǔ)的領(lǐng)域特征信息來(lái)抽取術(shù)語(yǔ)。Tomokiyo等[6]提出利用語(yǔ)言模型之間的相對(duì)熵來(lái)計(jì)算詞之間的耦合度和術(shù)語(yǔ)的領(lǐng)域相關(guān)性?；诮y(tǒng)計(jì)的方法[7]不局限于一種領(lǐng)域，通用性較強(qiáng)，但是算法性能依賴于語(yǔ)料庫(kù)規(guī)模的大小和候選術(shù)語(yǔ)的詞頻，將一些低頻率但合法的術(shù)語(yǔ)忽略掉，不適用于稀疏的文本。Sui等[8]提出使用統(tǒng)計(jì)方法計(jì)算術(shù)語(yǔ)的置信度，然后使用規(guī)則過(guò)濾領(lǐng)域術(shù)語(yǔ)候選，這是將統(tǒng)計(jì)和規(guī)則相結(jié)合的方法，但是術(shù)語(yǔ)抽取的準(zhǔn)確率還是沒有達(dá)到理想水平。本文使用游戲領(lǐng)域詞匯發(fā)現(xiàn)算法對(duì)術(shù)語(yǔ)進(jìn)行抽取，它不依賴任何詞庫(kù)，針對(duì)稀疏的文本也能達(dá)到很好的效果。

2 整體思想

2.1 問題定義

游戲的資訊網(wǎng)站包含了豐富的游戲內(nèi)容，為玩家了解游戲提供了方便的平臺(tái)。資訊網(wǎng)站數(shù)據(jù)庫(kù)包含了大量的游戲術(shù)語(yǔ)，是構(gòu)建游戲領(lǐng)域本體的主要來(lái)源，具有較高的可靠性及通用性。資訊網(wǎng)站中導(dǎo)航頁(yè)幫助玩家快速找到想要的游戲內(nèi)容，具有一定的分類結(jié)構(gòu)，作為領(lǐng)域本體構(gòu)建的補(bǔ)充。游戲論壇中玩家總結(jié)了大量的游戲術(shù)語(yǔ)，這些術(shù)語(yǔ)經(jīng)常出現(xiàn)在攻略數(shù)據(jù)中，進(jìn)一步豐富了領(lǐng)域本體。本文是從以上三個(gè)數(shù)據(jù)源構(gòu)建游戲領(lǐng)域本體存儲(chǔ)到知識(shí)庫(kù)中，具體構(gòu)建方法在第3節(jié)中會(huì)詳細(xì)介紹。本文所用語(yǔ)料來(lái)源于資訊網(wǎng)站中游戲攻略文本數(shù)據(jù)，每一條數(shù)據(jù)包含“標(biāo)題”和“內(nèi)容”兩部分，大多標(biāo)題中都會(huì)出現(xiàn)游戲術(shù)語(yǔ)或其簡(jiǎn)稱。本文的輸入為大量的游戲攻略文本數(shù)據(jù)，輸出為所有數(shù)據(jù)的標(biāo)簽。本文的主要任務(wù)可以描述為：對(duì)每條數(shù)據(jù)，抽取出標(biāo)題中所包含的游戲術(shù)語(yǔ)或其簡(jiǎn)稱的集合M(m1,m2,…,mn)，在知識(shí)庫(kù)E{e1,e2,…,em}中找到集合M中每個(gè)元素所代表的游戲術(shù)語(yǔ)或其簡(jiǎn)稱所對(duì)應(yīng)的游戲術(shù)語(yǔ)全稱，即集合A{a1,a2,…,an|a1,a2,…,an∈E}。

以圖1給出的攻略數(shù)據(jù)為例，標(biāo)題中出現(xiàn)了“黑魔”，將“黑魔”和知識(shí)庫(kù)進(jìn)行鏈接，“黑魔”在知識(shí)庫(kù)中所對(duì)應(yīng)的全稱為“黑魔法師”，“黑魔法師”即是該數(shù)據(jù)的標(biāo)簽。在構(gòu)建知識(shí)庫(kù)時(shí)，將爬取的資訊網(wǎng)站和游戲論壇數(shù)據(jù)轉(zhuǎn)化成標(biāo)準(zhǔn)的Ontology[12]語(yǔ)言格式，在知識(shí)庫(kù)中存儲(chǔ)成如圖1所示的結(jié)構(gòu)(只給出了部分結(jié)構(gòu))，共包含兩層：模式(schema)層和實(shí)例(instance)層。模式層表達(dá)了類與類之間的關(guān)系，即父類與子類的關(guān)系。如“攻略”是頂層類，“攻略”下包含“職業(yè)”和“副本”等子類，職業(yè)類下又包含“基礎(chǔ)職業(yè)”和“進(jìn)階職業(yè)”等子類。知識(shí)庫(kù)結(jié)構(gòu)的最底層是實(shí)例層，如進(jìn)階職業(yè)類下包含“黑魔法師”等實(shí)例。

圖1 基于領(lǐng)域本體的文本標(biāo)注

2.2 整體流程

基于領(lǐng)域本體的游戲攻略文本標(biāo)注主要包括三個(gè)階段(如圖2所示)：構(gòu)建知識(shí)庫(kù)、抽取領(lǐng)域詞匯、實(shí)體鏈接。本文知識(shí)庫(kù)的來(lái)源多樣化，從三個(gè)不同的數(shù)據(jù)源爬取游戲領(lǐng)域知識(shí)構(gòu)建游戲領(lǐng)域本體存儲(chǔ)在知識(shí)庫(kù)中，知識(shí)庫(kù)中存在的游戲術(shù)語(yǔ)全稱稱為“實(shí)體”。然后從多個(gè)資訊網(wǎng)站中抽取游戲攻略文本數(shù)據(jù)作為語(yǔ)料庫(kù)，每條攻略數(shù)據(jù)包括“標(biāo)題”和“內(nèi)容”兩部分內(nèi)容。使用游戲領(lǐng)域詞匯發(fā)現(xiàn)算法從語(yǔ)料中抽取出游戲領(lǐng)域詞匯稱之為“指代項(xiàng)”(Mention)即可進(jìn)行實(shí)體鏈接的錨文本，其包含游戲術(shù)語(yǔ)全稱或簡(jiǎn)稱和其他游戲詞匯。對(duì)每一個(gè)標(biāo)題判斷是否包含“Mention”，若包含“Mention”，則和知識(shí)庫(kù)中的實(shí)體使用匹配算法進(jìn)行鏈接，鏈接到的游戲術(shù)語(yǔ)的全稱即文本標(biāo)簽從而對(duì)攻略數(shù)據(jù)進(jìn)行語(yǔ)義標(biāo)注。

圖2 整體流程

3 構(gòu)建知識(shí)庫(kù)

本節(jié)將分別從知識(shí)庫(kù)結(jié)構(gòu)的模式層與實(shí)例層，詳細(xì)闡述如何融合多個(gè)資訊網(wǎng)站的游戲知識(shí)，并同時(shí)對(duì)融合過(guò)程中所產(chǎn)生的沖突予以解決。首先，在構(gòu)造知識(shí)庫(kù)模式層的過(guò)程中，本文利用兩部分的數(shù)據(jù)源，分別是資訊網(wǎng)站提供的導(dǎo)航欄，以及網(wǎng)站以網(wǎng)頁(yè)方式提供的游戲數(shù)據(jù)庫(kù)。通過(guò)解析網(wǎng)頁(yè)的HTML結(jié)構(gòu)，可以得到該導(dǎo)航欄或知識(shí)庫(kù)定義的分類目錄結(jié)構(gòu)。例如：“裝備”在資訊網(wǎng)站數(shù)據(jù)庫(kù)分類目錄下有“頭部防具”、“身體防具”、“手部防具”、“腰部防具”等。故在知識(shí)庫(kù)的結(jié)構(gòu)中，“頭部防具”、“身體防具”等均可作為“裝備”的子類。

本文將位于各資訊網(wǎng)站分類目錄中葉節(jié)點(diǎn)的數(shù)據(jù)作為知識(shí)庫(kù)結(jié)構(gòu)的實(shí)例層。例如，上述例子中，“頭部防具”類下還包含有葉節(jié)點(diǎn)“風(fēng)化兜帽”、“風(fēng)化眼睛”等，均存在唯一的URI可以鏈接到具體介紹“風(fēng)化兜帽”、“風(fēng)化眼睛”等的頁(yè)面。因此，“風(fēng)化兜帽、風(fēng)化眼睛”將作為“頭部防具”的實(shí)例存儲(chǔ)于知識(shí)庫(kù)中。

此外，游戲論壇中會(huì)總結(jié)游戲攻略中玩家自定義的游戲術(shù)語(yǔ)和資訊網(wǎng)站游戲術(shù)語(yǔ)形成的同義詞表。本文對(duì)游戲論壇進(jìn)行抽取，并將同義詞表存儲(chǔ)于知識(shí)庫(kù)中。例如，游戲攻略中玩家通常會(huì)用英文的簡(jiǎn)寫來(lái)表征游戲術(shù)語(yǔ)，使用“DPS”來(lái)表示“輸出職業(yè)”，因此，“DPS”作為“輸出職業(yè)”的同義詞存儲(chǔ)于知識(shí)庫(kù)中。

在融合資訊網(wǎng)站構(gòu)建知識(shí)庫(kù)的過(guò)程中，由于網(wǎng)站間的異構(gòu)問題，會(huì)產(chǎn)生兩種沖突。其一是在融合模式層時(shí)，同一個(gè)類在不同網(wǎng)站所屬父類不同。其二是在融合實(shí)例時(shí)，同一個(gè)實(shí)例在不同網(wǎng)站的類別不同。

融合網(wǎng)站間模式出現(xiàn)的沖突，可定義為對(duì)于類M，在不同的網(wǎng)站中分別歸屬于兩個(gè)不同的父類E和C。本文將通過(guò)判斷類E和類C之間的關(guān)系來(lái)解決沖突。計(jì)算公式為：

(1)

其中，nei表示在i網(wǎng)站E類中實(shí)例數(shù)目，ncj表示j網(wǎng)站C類的實(shí)例數(shù)目。IEi,Cj代表這兩個(gè)類的實(shí)例重疊比。若該值較高，則本文將類E和類C視為相等關(guān)系；反之，則可認(rèn)為類E和類C之間是父類和子類關(guān)系。對(duì)于后者，將進(jìn)一步復(fù)用式(1)計(jì)算類M與類E的實(shí)例重合比IM,E以及類M與類C的實(shí)例重合比IM,C。若IM,E>IM,C,則認(rèn)為E是C的父類，否則C是E的父類。例如，在“多玩(http://ff14.duowan.com/index.html)”網(wǎng)站中“劍”是“單手武器”的一個(gè)子類，但是在“178(http://ff14.178.com/)”網(wǎng)站中“劍”是“武器”的一個(gè)子類，因此，融合時(shí)會(huì)產(chǎn)生沖突。通過(guò)式(1)計(jì)算可知，“武器”是“單手武器”父類，最后形成的關(guān)系為“單手武器”是“武器”的子類，“劍”是“單手武器”的子類。

在處理實(shí)例融合產(chǎn)生沖突時(shí)，我們會(huì)綜合考慮每個(gè)實(shí)例所在類的出現(xiàn)頻次以及該類的豐富程度，進(jìn)而形成一個(gè)綜合指標(biāo)來(lái)解決沖突。每個(gè)實(shí)例所在類的出現(xiàn)頻次可通過(guò)式(2)進(jìn)行歸一化計(jì)算：

(2)

(3)

max{Fi×Ri}

(4)

對(duì)于上述例子，可根據(jù)式(4)，計(jì)算得到“采礦工”作為“采集職業(yè)”類的綜合指標(biāo)值較大，因此，最終“采礦工”作為“采集職業(yè)”的實(shí)例存儲(chǔ)于知識(shí)庫(kù)中。

4 實(shí)體鏈接

4.1 游戲領(lǐng)域詞匯發(fā)現(xiàn)

對(duì)于中文來(lái)說(shuō)[7]，文本中沒有空格標(biāo)志詞語(yǔ)邊界，沒有首字母大寫等明顯特征來(lái)表征一個(gè)術(shù)語(yǔ)。術(shù)語(yǔ)識(shí)別過(guò)程通常要和中文分詞過(guò)程相結(jié)合，然而漢語(yǔ)詞匯具有開放性，無(wú)論建立多大的詞典，都不可能包含所有的詞匯，而且隨著時(shí)間的推移還會(huì)不斷出現(xiàn)大量新詞。使用傳統(tǒng)的分詞方法處理起來(lái)比較困難且難以達(dá)到預(yù)期的效果，在此基礎(chǔ)之上，我們提出了游戲領(lǐng)域詞匯發(fā)現(xiàn)算法。

游戲領(lǐng)域詞匯發(fā)現(xiàn)算法是在新詞發(fā)現(xiàn)算法基礎(chǔ)之上所做的改進(jìn)。新詞發(fā)現(xiàn)算法[1]是顧森提出來(lái)的一種基于大規(guī)模語(yǔ)料挖掘新詞的方法。他所使用的語(yǔ)料是人人網(wǎng)2011年12月前半個(gè)月部分用戶狀態(tài)，而本文所使用的語(yǔ)料是游戲攻略數(shù)據(jù)。由于語(yǔ)料庫(kù)有所不同，因此在此基礎(chǔ)上進(jìn)行了改進(jìn)得到游戲領(lǐng)域詞匯發(fā)現(xiàn)算法。游戲領(lǐng)域詞匯發(fā)現(xiàn)算法有兩個(gè)成詞標(biāo)準(zhǔn)分別是“內(nèi)部凝固程度”和“自由運(yùn)用程度”。凝合度的計(jì)算公式為：

(5)

(6)

其中N為出現(xiàn)次數(shù),P為出現(xiàn)的概率，length為所含字?jǐn)?shù)。在式(5)中“ABC”表示要抽取的詞由A、B、C三部分組成，實(shí)際操作時(shí)，候選詞可能不止這三部分，其計(jì)算公式相同。文本片段的自由運(yùn)用程度也是判斷其是否成詞的標(biāo)準(zhǔn)之一，在此，用“信息熵”衡量。具體計(jì)算公式如下所示：

設(shè)Z的左鄰字集合為{X1,X2,…,Xn},則Z的左鄰字信息熵為：

(7)

其中n+m=N(Z)，對(duì)上式化簡(jiǎn)后如下所示：

(8)

同理，設(shè)Z的右鄰字集合為{Y1,Y2,…,Yn},化簡(jiǎn)后則Z的右鄰字信息熵：

(9)

信息熵為min{H(X),H(Y)}。

本文提出的游戲領(lǐng)域詞匯發(fā)現(xiàn)算法在原有新詞發(fā)現(xiàn)算法基礎(chǔ)之上做出以下改進(jìn)：

(1) 鑒于游戲中很多副本的名稱往往很長(zhǎng)，比如“山中戰(zhàn)線澤梅爾要塞”、“劍斗領(lǐng)域日影地修煉所”。若所抽取候選詞的長(zhǎng)度太小，容易將較長(zhǎng)的游戲術(shù)語(yǔ)分割成更小的詞語(yǔ)組成；若所抽取的候選詞的長(zhǎng)度太大，所抽取的游戲術(shù)語(yǔ)中易混雜無(wú)關(guān)詞組。經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，候選詞語(yǔ)的長(zhǎng)度設(shè)置為10效果最佳。

(2) 在計(jì)算信息熵時(shí)，對(duì)于左鄰字是標(biāo)點(diǎn)符號(hào)或沒有左鄰字(詞語(yǔ)本身是開頭)，以及右鄰字是標(biāo)點(diǎn)符號(hào)或沒有右鄰字(詞語(yǔ)本身是結(jié)尾)的情況，視其左鄰字或右鄰字是一個(gè)全新的從未出現(xiàn)過(guò)的字，并在實(shí)際操作時(shí)分別統(tǒng)計(jì)該種左鄰字與右鄰字的出現(xiàn)次數(shù)，以做等效計(jì)算(見上述信息熵的計(jì)算式)。開頭、結(jié)尾和標(biāo)點(diǎn)符號(hào)的存在，起到了分詞的作用，對(duì)于抽取領(lǐng)域詞匯大有裨益。之所以不據(jù)此將詞語(yǔ)的左鄰字或右鄰字信息熵直接設(shè)為無(wú)窮大，而僅僅是把每一個(gè)開頭、結(jié)尾或標(biāo)點(diǎn)符號(hào)視作一個(gè)全新的從未出現(xiàn)過(guò)的字，是為了提高新詞發(fā)現(xiàn)的容錯(cuò)程度，以避免因?yàn)楣ヂ灾姓`出現(xiàn)標(biāo)點(diǎn)符號(hào)或誤作開頭、結(jié)尾，而執(zhí)行了錯(cuò)誤的分詞。使用此方法之后，如果攻略中偶爾出現(xiàn)一個(gè)筆誤，則其對(duì)信息熵的計(jì)算不會(huì)造成太大的影響；如果是正常情況下多次出現(xiàn)標(biāo)點(diǎn)符號(hào)或多次作為開頭、結(jié)尾，由此便能通過(guò)提高信息熵而起到分詞的作用。

(3) 針對(duì)英文單詞與純數(shù)字的情況，我們?cè)诔槿『蜻x詞時(shí)，先將文本中所有出現(xiàn)的英文單詞抽取加入到候選詞集合中，之后再做正常抽取時(shí)，如果碰到詞語(yǔ)是全英文或全數(shù)字，則不放入候選集，從而大大提高了抽取的準(zhǔn)確率與效率。因?yàn)樵谥形臐h字占主體的攻略文本中，偶爾出現(xiàn)幾個(gè)連續(xù)的英文字母，其必然是一個(gè)完整的英文單詞，英漢字符的不同已經(jīng)能夠很好地起到分詞的作用。而如果將英文單詞也放到正常的流程中抽取，則在抽取的過(guò)程中會(huì)將英文單詞的子串也一并加入候選詞集合，從而影響分詞效率。至于不將全數(shù)字字符串加入候選集，是因?yàn)槟康氖浅槿∮螒蛐g(shù)語(yǔ)，而純數(shù)字一般不作為游戲術(shù)語(yǔ)出現(xiàn)，將其加入會(huì)增加干擾、影響抽取質(zhì)量。

游戲領(lǐng)域詞匯發(fā)現(xiàn)算法偽代碼如下：

算法1 游戲領(lǐng)域詞匯發(fā)現(xiàn)算法

Input：setStrategies, Set of game strategy

Output：setPhrases, Set of phrase that meet conditions

1: for each strategysetStrategies do

2: PhraseMap lengthd(phrase; num)

3: if leftPhrase exists then

4： LeftPhraseMap leftPhrase

5： if leftPhrase is punctuation or beginning then

6: PBMap (LeftPhrase, 1)

7： rightPhrase same as leftPhrase

8: if !leftPhrase || ! rightPhrase then As a new word

9： PhraseSet 1

10: setPhrases(Phrase, C>5&&H>0.6&&Num4)

11: end for

最后凝合度、信息熵、出現(xiàn)的次數(shù)的閾值的選擇是通過(guò)多次實(shí)驗(yàn)得到的最佳值。使用此算法后，得到比如“巴哈姆特大迷宮”、“極水神”、“煉金術(shù)師”等可用于實(shí)體鏈接的錨文本即Mention列表。

4.2 語(yǔ)義標(biāo)注

游戲術(shù)語(yǔ)在文本中經(jīng)常以簡(jiǎn)稱的形式存在，例如“白魔法師”在文本中常常記為“白魔”，由于知識(shí)庫(kù)中存儲(chǔ)游戲術(shù)語(yǔ)的全稱，因此需要進(jìn)行鏈接。從而得到知識(shí)庫(kù)中所對(duì)應(yīng)的游戲術(shù)語(yǔ)全稱即文本標(biāo)簽對(duì)攻略數(shù)據(jù)進(jìn)行語(yǔ)義標(biāo)注。文本中的簡(jiǎn)稱無(wú)法直接和知識(shí)庫(kù)中實(shí)體進(jìn)行關(guān)聯(lián)，因此需采取匹配算法。通過(guò)觀察數(shù)據(jù)知每個(gè)標(biāo)題包含的Mention個(gè)數(shù)可能不止一個(gè)，這種對(duì)應(yīng)的標(biāo)簽即為多標(biāo)簽，如表1所示。Mention可能和知識(shí)庫(kù)中的實(shí)體完全匹配，或者M(jìn)ention是知識(shí)庫(kù)中實(shí)體的簡(jiǎn)稱或縮寫，或者M(jìn)ention是知識(shí)庫(kù)中實(shí)體相鄰詞組成的子串，或者M(jìn)ention是知識(shí)庫(kù)中實(shí)體不相鄰字組成的子串(此時(shí)通過(guò)計(jì)算相似度進(jìn)行匹配)，或者知識(shí)庫(kù)中實(shí)體是Mention的相鄰字組成的子串等，如表2所示?；谝陨嫌^察結(jié)果，提出了進(jìn)行鏈接的匹配算法，具體算法及思想在下面的內(nèi)容中會(huì)詳細(xì)介紹。

表1 標(biāo)題中的標(biāo)簽類型

表2 Mention和實(shí)體之間的關(guān)系

通過(guò)以上對(duì)數(shù)據(jù)的觀察和分析，得出以下匹配算法：

算法2 匹配算法

Input：

1)setMentions：Set of mentions in corpus;

2)setEntities：Set of entities in knoeledge base;

3)setStrategies：Set of strtegies，each of the strategy contains a title and the text;

Output：{(strategy,setWords)} pair list;

Initiation：The English letters in setMentions and setEntities and setStrategies are unified in Uppercase, remove the blank space in setStrategies;

1: if titile.contains(mention) then

2: if mention.equal(entity) then

3: setWordsentity

4: else simlarRate(mention, entity)

5: setWordslargestRate(entity)

6: or else setWords is empty then

7:entity=entity.replace(mention,“”),setWordslength(entity)

8: title=title.replace(mention, “”)

9: perform steps 1-6

10：mapStrategySetEntities(strategy,setWords)

5 實(shí)驗(yàn)結(jié)果和分析

5.1 實(shí)驗(yàn)數(shù)據(jù)與設(shè)置

本文所用的語(yǔ)料庫(kù)是“最終幻想14”這款游戲不同資訊網(wǎng)站中每天都不斷更新的游戲攻略文本數(shù)據(jù)，每條數(shù)據(jù)包括標(biāo)題和內(nèi)容兩部分，爬取這些攻略文本數(shù)據(jù)并進(jìn)行去重后，共計(jì)1788條數(shù)據(jù)。

雖然本文提出的方法是無(wú)監(jiān)督的，但是還是需要人工對(duì)數(shù)據(jù)進(jìn)行標(biāo)注來(lái)評(píng)估標(biāo)注質(zhì)量。本文使用準(zhǔn)確率Precision和召回率Recall作為評(píng)價(jià)標(biāo)準(zhǔn)，若A表示正確標(biāo)注的數(shù)據(jù)條數(shù)，B表示錯(cuò)誤標(biāo)注的數(shù)據(jù)條數(shù)，C表示沒有進(jìn)行標(biāo)注的數(shù)據(jù)條數(shù)，則準(zhǔn)確率和召回率的定義分別如下：

5.2 結(jié)果分析

在抽取文本游戲領(lǐng)域術(shù)語(yǔ)或其簡(jiǎn)稱時(shí)，分別使用了游戲領(lǐng)域詞匯發(fā)現(xiàn)算法、Ansj、N-grams(n一般取2或3，若n過(guò)大，會(huì)導(dǎo)致計(jì)算復(fù)雜度增高，且結(jié)果數(shù)據(jù)過(guò)于稀疏)，最后分別統(tǒng)計(jì)每一種方法所得標(biāo)注數(shù)據(jù)的準(zhǔn)確率和召回率，如圖3所示。錯(cuò)誤標(biāo)注的情況分別如下所示：

圖3 不同詞匯抽取方法的比較

(1) 少標(biāo)簽。如果一個(gè)標(biāo)題中出現(xiàn)的游戲術(shù)語(yǔ)或其簡(jiǎn)稱不止一個(gè)，則這條文本數(shù)據(jù)屬于多標(biāo)簽，在標(biāo)注時(shí)可能會(huì)發(fā)生遺漏標(biāo)簽的情況。比如標(biāo)題“FF14龍騎和武僧輸出大對(duì)比 誰(shuí)更難操作？”，標(biāo)題中出現(xiàn)的游戲術(shù)語(yǔ)或其簡(jiǎn)稱為“龍騎”、“武僧”，該數(shù)據(jù)的正確標(biāo)簽為“龍騎士”、“武僧”。若最后給出的標(biāo)簽少了其中任何一個(gè)，都認(rèn)為標(biāo)注錯(cuò)誤。

(2) 多標(biāo)簽。比如標(biāo)題“暴擊流黑暗魔法師在2.4版本中裝備怎么進(jìn)階”，其正確的標(biāo)簽為：“2.4版本、黑魔法師、裝備”。若最后給出的標(biāo)簽為“2.4版本、黑魔法師、裝備、白魔法師”，相對(duì)于正確的標(biāo)簽多出了“白魔法師”標(biāo)簽，則認(rèn)為該標(biāo)注是錯(cuò)誤的。

(3) 標(biāo)簽錯(cuò)誤。比如標(biāo)題“最終幻想14數(shù)據(jù)分析告訴你騎士起手仇恨究竟有多高”， 正確的標(biāo)簽為“騎士”。若最后給出的標(biāo)簽為“龍騎士”則認(rèn)為該標(biāo)注是錯(cuò)誤的。

對(duì)于沒有標(biāo)注的數(shù)據(jù)，據(jù)觀察文本內(nèi)容多偏向于玩家心情類的攻略，與游戲本身并不相關(guān)。比如標(biāo)題為“FF14讓你更快適應(yīng)游戲之你所不知道的小竅門集合”，標(biāo)題中沒有出現(xiàn)與游戲術(shù)語(yǔ)相關(guān)的詞匯，因而本文所提出的方法無(wú)法進(jìn)行標(biāo)注。

從圖3中可以看出，使用游戲領(lǐng)域發(fā)現(xiàn)算法所得標(biāo)注的準(zhǔn)確率和召回率明顯高于Ansj、2-gram、3-gram。Ansj是基于詞典的分詞方法，針對(duì)新聞、文章等普通文本的分詞，能夠得到比較高的準(zhǔn)確率，而本文語(yǔ)料數(shù)據(jù)包含的游戲術(shù)語(yǔ)多，使用Ansj大多將游戲術(shù)語(yǔ)分成更細(xì)粒度的詞，比如“白魔法師”會(huì)分成“白魔”和“法師”兩個(gè)詞，因此標(biāo)注效果難以滿足要求。N-grams需要相當(dāng)規(guī)模的語(yǔ)料來(lái)確定模型參數(shù)，N不宜取過(guò)大，N值一般為2或3。有些游戲術(shù)語(yǔ)由3個(gè)或4個(gè)字組成，使用此語(yǔ)言模型會(huì)將這些詞分開，因此和知識(shí)庫(kù)進(jìn)行鏈接時(shí)匹配率不高，會(huì)生成與文本數(shù)據(jù)無(wú)關(guān)的標(biāo)簽。

6 結(jié) 語(yǔ)

本文主要研究了游戲領(lǐng)域中攻略文本的標(biāo)注算法，在對(duì)同一個(gè)游戲的不同資訊網(wǎng)站進(jìn)行信息融合的基礎(chǔ)之上，建立了統(tǒng)一的本體；提出了一種全新的領(lǐng)域詞匯抽取算法即游戲領(lǐng)域詞匯發(fā)現(xiàn)算法，并據(jù)此從語(yǔ)料庫(kù)中抽取出文本標(biāo)題所包含的游戲術(shù)語(yǔ)或其簡(jiǎn)稱，再和知識(shí)庫(kù)進(jìn)行鏈接，最終得到文本數(shù)據(jù)的標(biāo)簽。在抽取游戲領(lǐng)域詞匯時(shí)，將游戲領(lǐng)域詞匯發(fā)現(xiàn)算法與Ansj和N-grams這兩個(gè)已有的自然語(yǔ)言處理工具進(jìn)行對(duì)比，結(jié)果顯示該方法在領(lǐng)域詞匯抽取方面具有優(yōu)越性。本文的優(yōu)點(diǎn)是將文本標(biāo)注問題看成是實(shí)體鏈接問題，并且解決了在領(lǐng)域詞匯抽取工作上一直存在的抽取質(zhì)量問題。數(shù)據(jù)集上的結(jié)果表明，本文提出的方法達(dá)到較高的準(zhǔn)確率和召回率。接下來(lái)計(jì)劃將攻略標(biāo)簽用于游戲攻略上的語(yǔ)義搜索和將游戲領(lǐng)域詞匯抽取方法應(yīng)用于其他領(lǐng)域進(jìn)行領(lǐng)域詞匯抽取，如計(jì)算機(jī)領(lǐng)域、醫(yī)療領(lǐng)域等。

[1] 顧森.基于大規(guī)模語(yǔ)料的新詞發(fā)現(xiàn)算法[J].程序員,2012(7):54-57.

[2]MeijE,BalogK,OdijkD.Entitylinkingandretrieval[C]//Proceedingsofthe36thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM,2013:1127.

[3]MihalceaR,TarauP.TextRank:bringingorderintotexts[C]//Proceedingsofthe2004ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,2004:401-411.

[4]ParkYC,HanYS,ChoiKS.AutomaticthesaurusconstructionusingBayesiannetworks[C]//ProceedingsoftheFourthInternationalConferenceonInformationandKnowledgeManagement.ACM,1995:212-217.

[5]BuitelaarP,OlejnikD,SintekM.Aprotégéplug-inforontologyextractionfromtextbasedonlinguisticanalysis[C]//FirstEuropeanSemanticWebSymposium.Springer,2004:31-44.

[6]TomokiyoT,HurstM.Alanguagemodelapproachtokeyphraseextraction[C]//ProceedingsoftheACL2003WorkshoponMultiwordExpressions:Analysis,AcquisitionandTreatment.AssociationforComputationalLinguistics,2003:33-40.

[7] 季培培,鄢小燕,岑詠華.面向領(lǐng)域中文文本信息處理的術(shù)語(yǔ)識(shí)別與抽取研究綜述[J].圖書情報(bào)工作,2010,54(16):124-129.

[8]SuiZ,ChenY,HuJ,etal.Theresearchontheautomatictermextractioninthedomainofinformationscienceandtechnology[C]//Proceedingsofthe5thEastAsiaForumoftheTerminology,Haikou,Hainan,China,2002:444-451.

[9]LehmannJ,IseleR,JakobM,etal.DBpedia-alarge-scale,multilingualknowledgebaseextractedfromWikipedia[J].SemanticWeb,2015,6(2):167-195.

[10]BollackerK,EvansC,ParitoshP,etal.Freebase:acollaborativelycreatedgraphdatabaseforstructuringhumanknowledge[C]//Proceedingsofthe2008ACMSIGMODInternationalConferenceonManagementofData.ACM,2008:1247-1250.

[11]SuchanekFM,KasneciG,WeikumG.Yago:acoreofsemanticknowledge[C]//Proceedingsofthe16thInternationalConferenceonWorldWideWeb.ACM,2007:697-706.

[12]ArefMM,ZhouZ.Theontologyweblanguage(OWL)foramulti-agentunderstatingsystem[C]//Proceedingsofthe2005InternationalConferenceonIntegrationofKnowledgeIntensiveMulti-AgentSystems.IEEEComputerSociety,2005:586-591.

RESEARCH AND IMPLEMENTATION OF ANNOTATION ALGORITHM FOR WALKTHROUGH TEXT BASED ON DOMAIN ONTOLOGY

Chen Xiaohong1Chen Huanhuan2Fang Zhijia2Ruan Tong2Wang Haofen2

1(ShengdaGameLimited,Shanghai201203,China)2(CollegeofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Nowadays, game web portals set up plenty of websites, providing game information and related walkthroughs, for players to enhance their gaming experience. However, these sites has obvious isomerism and lacks unified hierarchy. Thus, an annotation algorithm based on domain ontology is proposed. It is started with a data fusion step from a set of web portals to build a game domain ontology. Meanwhile, the neologism discovering algorithm is optimized according to its application in game domain, and the semantic annotation for walkthrough text is further developed. Thus these semantic tags not only embody the intent of each guides, but also serve the semantic search for walkthrough text. Experiments have proved that the proposed ontology construction method is scalable. Moreover, the optimized domain vocabulary discovering algorithm has a better result compared with the traditional segmentation tools.

Domain ontology Game domain vocabulary discovering algorithm Semantic annotation

2015-12-11。國(guó)家自然科學(xué)基金項(xiàng)目(61402173)；上海市經(jīng)信委軟件和集成電路產(chǎn)業(yè)專項(xiàng)資金(140304)。陳小紅，高工，主研領(lǐng)域：大數(shù)據(jù)和虛擬世界的用戶行為。陳環(huán)環(huán)，碩士生。方之家，碩士生。阮彤，副教授。王昊奮，博士。

TP391

A

10.3969/j.issn.1000-386x.2017.02.014