陳環(huán)環(huán)，陳小紅，阮 彤，高大啟，王昊奮

(1.華東理工大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200237； 2.盛趣信息技術(shù)(上海)有限公司，上海 201203)

(*通信作者電子郵箱1558589300@qq.com)

知識(shí)驅(qū)動(dòng)的游戲攻略自動(dòng)標(biāo)注算法

陳環(huán)環(huán)1*，陳小紅2，阮 彤1，高大啟1，王昊奮1

(1.華東理工大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200237； 2.盛趣信息技術(shù)(上海)有限公司，上海 201203)

(*通信作者電子郵箱1558589300@qq.com)

為了幫助用戶快速檢索感興趣的游戲攻略，提出了知識(shí)驅(qū)動(dòng)的游戲攻略自動(dòng)標(biāo)注算法。首先，對(duì)每款游戲的多個(gè)資訊網(wǎng)站進(jìn)行融合，自動(dòng)構(gòu)建游戲領(lǐng)域知識(shí)庫(kù)；然后，再通過游戲領(lǐng)域詞匯發(fā)現(xiàn)算法和決策樹分類模型，抽取游戲攻略中的游戲術(shù)語；由于游戲術(shù)語在攻略中大多以簡(jiǎn)稱的形式存在，故最后將攻略中游戲術(shù)語和知識(shí)庫(kù)進(jìn)行鏈接得到該術(shù)語所對(duì)應(yīng)的全稱即語義標(biāo)簽對(duì)攻略進(jìn)行標(biāo)注。在多款游戲上的實(shí)驗(yàn)結(jié)果表明，所提出的游戲攻略標(biāo)注方法的準(zhǔn)確率高達(dá)90%。同時(shí)，游戲領(lǐng)域詞匯發(fā)現(xiàn)算法與其他術(shù)語抽取方法n-gram語言模型相比取得了更好的效果。

游戲攻略；知識(shí)庫(kù)；游戲術(shù)語；語義標(biāo)簽；決策樹

0 引言

當(dāng)前游戲產(chǎn)品愈發(fā)同質(zhì)化，游戲能否成功占有市場(chǎng)，游戲玩家的用戶體驗(yàn)成為最關(guān)鍵的一步[1]。如今，游戲產(chǎn)品可供選擇的數(shù)量眾多，用戶偏好日趨多元化。只有將好的用戶體驗(yàn)利用在游戲設(shè)計(jì)上，才能贏得用戶玩家的心聲。目前，主要從游戲角色的設(shè)計(jì)、游戲視覺效果及游戲的操作等方面提升用戶的體驗(yàn)[2]。據(jù)統(tǒng)計(jì)，大量的熱門游戲的資訊網(wǎng)站中都包含豐富的游戲攻略，這是玩家的主要檢索對(duì)象，可幫助用戶特別是新手玩家快速地入門和升級(jí)，是提升用戶體驗(yàn)的重要組成部分。游戲攻略標(biāo)注問題近年來研究較少。因此，本文通過對(duì)游戲攻略進(jìn)行標(biāo)注幫助用戶快速檢索所需的游戲攻略從而提高用戶的游戲體驗(yàn)。

由于每款游戲有多個(gè)資訊網(wǎng)站，且有很少資訊網(wǎng)站提供搜索功能，玩家檢索自己感興趣的攻略時(shí)需輾轉(zhuǎn)于多個(gè)資訊網(wǎng)站之間，花費(fèi)大量的時(shí)間和精力，因此，對(duì)游戲攻略進(jìn)行標(biāo)注可以提高攻略檢索的效率。同時(shí)，玩家通過語義標(biāo)簽，可以更快更全面地了解攻略內(nèi)容，且語義標(biāo)簽的生成有助于游戲攻略的分類和語義搜索系統(tǒng)的構(gòu)建。

本文中的游戲攻略的標(biāo)注任務(wù)如下：給出一條基于文本的游戲攻略，識(shí)別出其中包含的游戲術(shù)語，并將這些術(shù)語作為該攻略的標(biāo)簽。然而，攻略中的游戲術(shù)語大多以簡(jiǎn)稱的形式存在，且游戲攻略內(nèi)容比較口語化，這是對(duì)攻略進(jìn)行標(biāo)注的難點(diǎn)。在本文中，游戲術(shù)語為游戲領(lǐng)域內(nèi)的專有詞匯且包含其簡(jiǎn)稱。例如，游戲“最終幻想14(FF14)”中的一個(gè)攻略標(biāo)題為“FF14劍術(shù)師及騎士入門技能分析和輸出手法”包含游戲術(shù)語“劍術(shù)師”和“騎士”，因此“劍術(shù)師”和“騎士”是該攻略的標(biāo)簽。首先，針對(duì)同一款游戲不同資訊網(wǎng)站的異構(gòu)現(xiàn)象，本文提出通過融合多個(gè)網(wǎng)站來構(gòu)建知識(shí)庫(kù)的思想，知識(shí)庫(kù)具有完善的層次結(jié)構(gòu)并存儲(chǔ)了豐富的游戲領(lǐng)域知識(shí)。其次，為了準(zhǔn)確地抽取游戲攻略中的游戲術(shù)語，本文提出一個(gè)新的方法：游戲領(lǐng)域詞匯發(fā)現(xiàn)算法。由于大多游戲術(shù)語以簡(jiǎn)稱的形式存在于游戲攻略中，因此，本文使用匹配算法將攻略中的游戲術(shù)語和知識(shí)庫(kù)進(jìn)行鏈接，從而得到游戲術(shù)語的全稱即語義標(biāo)簽。

本文的主要工作如下：

1)對(duì)于大多數(shù)熱門游戲，提出一套通用的方法構(gòu)建知識(shí)庫(kù)。對(duì)于知識(shí)庫(kù)構(gòu)建過程中所產(chǎn)生的沖突給予有效的解決方法。

2)針對(duì)游戲攻略的結(jié)構(gòu)特點(diǎn)及游戲術(shù)語特征，在原有“新詞發(fā)現(xiàn)算法”[3]基礎(chǔ)上進(jìn)行優(yōu)化得到“游戲領(lǐng)域詞匯發(fā)現(xiàn)算法”，并結(jié)合決策樹分類模型抽取游戲術(shù)語。

3)本文提出一種適合游戲領(lǐng)域的匹配算法，將游戲攻略中的術(shù)語與所構(gòu)建知識(shí)庫(kù)進(jìn)行連接，從而生成語義標(biāo)簽。

1 相關(guān)工作

本文研究的關(guān)鍵技術(shù)為：構(gòu)建游戲領(lǐng)域知識(shí)庫(kù)、抽取游戲攻略中游戲術(shù)語。近年來，知識(shí)庫(kù)的構(gòu)建和中文術(shù)語的抽取得到了廣泛的研究。下面將簡(jiǎn)要介紹。

構(gòu)建高質(zhì)量的知識(shí)庫(kù)是本文游戲攻略標(biāo)注的關(guān)鍵步驟，知識(shí)庫(kù)的完善與否直接影響游戲攻略標(biāo)注的準(zhǔn)確率。DBpedia[4]、Freebase[5]、YAGO(Yet Another Great Ontology)[6]都是通用知識(shí)庫(kù)，包含了豐富的數(shù)據(jù)，但是缺乏游戲領(lǐng)域知識(shí)。DBpedia是從維基百科中自動(dòng)抽取結(jié)構(gòu)化信息，被廣泛用于語義萬維網(wǎng)和商業(yè)環(huán)境。Freebase中的所有內(nèi)容由用戶添加，所有條目都采用結(jié)構(gòu)化數(shù)據(jù)的格式。YAGO主要信息來源于維基百科，具有足夠高的準(zhǔn)確度和覆蓋度。本文所建的知識(shí)庫(kù)和上述幾個(gè)知識(shí)庫(kù)相似，都是通過融合互聯(lián)網(wǎng)資源得到。

中文術(shù)語的抽取是中文信息處理的一項(xiàng)重要任務(wù)，在領(lǐng)域本體構(gòu)建方面有著重要應(yīng)用?，F(xiàn)有的術(shù)語抽取方法主要有以下三類：

1)基于規(guī)則的方法。通過人工總結(jié)的規(guī)則模板抽取術(shù)語，如術(shù)語的上下文、詞法模式、詞形等。文獻(xiàn)[7]利用術(shù)語的共同特征前綴信息，抽取前綴是名詞的文本片段為術(shù)語。類似的，還有一些其他的抽取規(guī)則，如首部修飾定律、五層術(shù)語抽取模型[8]等。該方法的優(yōu)點(diǎn)在于實(shí)現(xiàn)簡(jiǎn)單、準(zhǔn)確率較高，缺點(diǎn)在于規(guī)則由人員編寫，耗時(shí)耗力。

2)基于統(tǒng)計(jì)的方法。利用術(shù)語內(nèi)部各組成成分之間較高的關(guān)聯(lián)程度以及術(shù)語的領(lǐng)域特征信息來抽取術(shù)語。目前該方法在抽取術(shù)語時(shí)，用到的主要參數(shù)有：互信息(Mutual Information, MI)[9]、Term Frequency-Inverse Document Frequency(TF-IDF)[10]、詞頻[11]、似然比(Likelihood Ratio, LR)[12]等。陳士超等[13]在不更改互信息公式的前提下，通過設(shè)置雙閾值的方法進(jìn)行候選術(shù)語的選取與過濾。該方法的優(yōu)點(diǎn)是通用性較強(qiáng)，缺點(diǎn)是針對(duì)稀疏數(shù)據(jù)效果較差。

3)統(tǒng)計(jì)和規(guī)則相結(jié)合的方法。此方法綜合基于規(guī)則和統(tǒng)計(jì)的優(yōu)缺點(diǎn)而提出。樊夢(mèng)佳等[14]提出了采用左右信息熵?cái)U(kuò)展、邊界信息出現(xiàn)概率和TF-IDF相融合的統(tǒng)計(jì)方法，同時(shí)引入詞性搭配規(guī)則進(jìn)一步約束術(shù)語的構(gòu)成，從而抽取術(shù)語。Bonin等[15]先根據(jù)規(guī)則抽取候選集合，然后使用C-value和T檢驗(yàn)的方法計(jì)算，最后得到真正術(shù)語。目前，統(tǒng)計(jì)和規(guī)則相結(jié)合的方法在術(shù)語抽取方面還未達(dá)到理想水平。

本文抽取的是游戲攻略所包含的游戲術(shù)語，由于游戲攻略語言表達(dá)較口語化且游戲術(shù)語組成結(jié)構(gòu)也無規(guī)律可循，使用以上抽取方法效果不佳。本文提出的游戲術(shù)語抽取方法綜合詞組的詞頻和上下文信息得到候選詞，在統(tǒng)計(jì)方法的基礎(chǔ)上進(jìn)行了擴(kuò)展。

2 游戲攻略標(biāo)注算法的整體流程

2.1 游戲攻略標(biāo)注算法的思想

本文的目標(biāo)是找到一種適用于大多數(shù)熱門游戲的游戲攻略標(biāo)注方法。整體流程如圖1所示，通過對(duì)三個(gè)數(shù)據(jù)源的數(shù)據(jù)進(jìn)行解析融合后得到如圖2所示的知識(shí)庫(kù)結(jié)構(gòu)。從每款游戲的多個(gè)資訊網(wǎng)站中解析攻略文本數(shù)據(jù)構(gòu)成語料庫(kù)，每條攻略包含標(biāo)題和內(nèi)容兩部分。通過游戲領(lǐng)域詞匯發(fā)現(xiàn)算法得到候選詞，該算法包含兩個(gè)成詞標(biāo)準(zhǔn)“內(nèi)部凝固程度”和“自由運(yùn)用程度”。在進(jìn)行鏈接時(shí)，判斷標(biāo)題中是否包含候選詞。若包含，則選取最長(zhǎng)候選詞使用匹配算法和知識(shí)庫(kù)進(jìn)行鏈接。在鏈接的過程中，若攻略標(biāo)題中游戲術(shù)語以全稱的形式存在，則和知識(shí)庫(kù)完全匹配。若以簡(jiǎn)稱的形式存在，則通過相似度計(jì)算和知識(shí)庫(kù)匹配。通過匹配算法得到游戲術(shù)語全稱進(jìn)而對(duì)攻略進(jìn)行標(biāo)注。

圖1 算法整體流程

圖2 知識(shí)庫(kù)結(jié)構(gòu)

2.2 問題定義

本文主要研究對(duì)象為游戲，通過觀察發(fā)現(xiàn)，熱門游戲均滿足以下條件。

1)每款游戲至少有兩個(gè)資訊網(wǎng)站，資訊網(wǎng)站至少包含數(shù)據(jù)庫(kù)(Database)、游戲資料、游戲介紹中的一項(xiàng)，且它們都包含完善的分類體系及豐富的游戲領(lǐng)域知識(shí)。這是構(gòu)建知識(shí)庫(kù)(Knowledge Base)的主要數(shù)據(jù)來源。

2)游戲攻略(Strategy)每天都在不斷更新，每條攻略數(shù)據(jù)都由兩部分構(gòu)成：攻略標(biāo)題(title)和攻略內(nèi)容(content)，且94%左右的標(biāo)題都會(huì)包含一個(gè)或者多個(gè)游戲術(shù)語。游戲攻略構(gòu)成語料庫(kù)。標(biāo)題中的游戲術(shù)語是語義標(biāo)簽的來源。

3)在知識(shí)庫(kù)中，游戲術(shù)語均是以全稱的形式存在。

針對(duì)滿足以上條件的熱門游戲，本文的主要任務(wù)可以描述為：對(duì)于給定的語料庫(kù)(Corpus)，抽取出每條攻略所包含的游戲術(shù)語集合M={mention | mention in title}，在知識(shí)庫(kù)中找到其對(duì)應(yīng)的游戲術(shù)語全稱集合E={entity | entity in Knowledge Base}。本文輸入為大量的游戲攻略數(shù)據(jù)，輸出為游戲攻略及其標(biāo)簽{(strategy,tags) | strategy in corpus and tags in Knowledge Base}。具有以上條件的游戲均可使用本文所提出的方法進(jìn)行游戲攻略標(biāo)注，具體算法在下面的章節(jié)中會(huì)詳細(xì)介紹。

3 游戲攻略標(biāo)注算法設(shè)計(jì)

3.1 構(gòu)建游戲領(lǐng)域知識(shí)庫(kù)

本文提出一套通用的方法來構(gòu)建游戲知識(shí)庫(kù)。知識(shí)庫(kù)的主要來源為游戲資訊網(wǎng)站中的數(shù)據(jù)庫(kù)或游戲介紹或游戲資料，這些數(shù)據(jù)可能存在于同一款游戲的多個(gè)資訊網(wǎng)站中。它們具有完善的分類體系和豐富的游戲領(lǐng)域知識(shí)，可通過解析網(wǎng)頁(yè)的超文本標(biāo)記語言(Hyper Text Markup Language，HTML)結(jié)構(gòu)獲得，進(jìn)而構(gòu)成了知識(shí)庫(kù)的模式層和實(shí)例層。以“傳奇世界(http://woool.games.sdo.com/knowledge/index)”為例，圖2給出了這款游戲的部分知識(shí)庫(kù)結(jié)構(gòu)?！皞髌媸澜纭睌?shù)據(jù)庫(kù)中有“職業(yè)”和“裝備”，“裝備”下包含“盔甲”“武器”等，在頁(yè)面上點(diǎn)擊“武器”會(huì)出現(xiàn)具體的武器頁(yè)面如“軒轅人皇劍”且其下面沒有更細(xì)的劃分，因此“軒轅人皇劍”是“武器”的實(shí)例構(gòu)成實(shí)例層，且“武器”和“盔甲”是“裝備”子類和“裝備”一起構(gòu)成模式層。同理，“職業(yè)”也是如此。由于每款游戲有多個(gè)資訊網(wǎng)站且資訊網(wǎng)站之間存在差異性，因此需要進(jìn)行數(shù)據(jù)融合，同時(shí)需要解決融合過程中可能產(chǎn)生的沖突。

首先，對(duì)模式層進(jìn)行融合。模式層所產(chǎn)生的沖突主要表現(xiàn)為：同一個(gè)子類在不同的資訊網(wǎng)站中所屬父類不同?？梢悦枋鰹椋涸O(shè)有三個(gè)類A、B、C，類C在不同的網(wǎng)站中分別屬于不同的父類A和B。首先根據(jù)簡(jiǎn)單的投票機(jī)制計(jì)算類C屬于類A的網(wǎng)站數(shù)num(A)及屬于類B的網(wǎng)站數(shù)num(B)。若num(A)>num(B)，則將類C劃分到類A下。若num(A)

Ri=fi/(f1∪f2∪…∪fi)

(1)

其中，fi為類i的實(shí)例數(shù)，通過這個(gè)公式可得RA和RB。若RA>RB，將類C劃分到類A下；若RA

然后，對(duì)實(shí)例層進(jìn)行融合。在實(shí)例層會(huì)產(chǎn)生兩類沖突：一類是同一個(gè)實(shí)例在不同的網(wǎng)站分屬不同的類；另一類是同一類在不同的網(wǎng)站所包含的實(shí)例不同。對(duì)于第一種情況使用解決模式層沖突的方法，這里不再重復(fù)。對(duì)于第二種沖突，需要對(duì)此類中的實(shí)例進(jìn)行字符串相似度計(jì)算，這里使用簡(jiǎn)單的最長(zhǎng)公共字串的計(jì)算方法，公式如下：

(2)

其中：lcs(longest common substring)是最長(zhǎng)公共子串；length(lcs)指的是兩個(gè)實(shí)例最長(zhǎng)公共子串的長(zhǎng)度；length(fi)指網(wǎng)站i中實(shí)例f的長(zhǎng)度；length(fj)指網(wǎng)站j中實(shí)例f的長(zhǎng)度。通過實(shí)驗(yàn)，sim(fi,fj)取值有三種情況：

1)sim(fi,fj)=0，實(shí)例fi作為實(shí)例fj的補(bǔ)充加入知識(shí)庫(kù)中。

2)0.5

3)sim(fi,fj)=1，實(shí)例fi和實(shí)例fj完全相同，則進(jìn)行去重融合。

例如，“最終幻想14”這款游戲有兩個(gè)資訊網(wǎng)站“178(http://ff14.178.com/)”和“多玩(http://ff14.duowan.com/index.html)”?！?78”網(wǎng)站副本類中有實(shí)例“塔姆·塔拉墓園”，“多玩”網(wǎng)站副本類中有實(shí)例“地下靈殿塔姆·塔拉墓園”，計(jì)算相似度得到sim∈(0.5,1)，故將“地下靈殿塔姆·塔拉墓園”加入知識(shí)庫(kù)中。

本文通過以上方法，可對(duì)熱門游戲構(gòu)建知識(shí)庫(kù)。詳細(xì)介紹了知識(shí)庫(kù)數(shù)據(jù)的來源以及在融合過程中產(chǎn)生的沖突，并對(duì)融合中產(chǎn)生的沖突提出了統(tǒng)一的解決方法。構(gòu)建的知識(shí)庫(kù)使游戲領(lǐng)域知識(shí)更加結(jié)構(gòu)化且使玩家對(duì)游戲有更全面的認(rèn)識(shí)，有利于對(duì)游戲進(jìn)行組織和管理。但是，游戲知識(shí)庫(kù)構(gòu)建的完善與否直接影響其質(zhì)量，且構(gòu)建知識(shí)庫(kù)是本文標(biāo)注質(zhì)量的關(guān)鍵技術(shù)之一。本文將通過攻略數(shù)據(jù)的標(biāo)注效果對(duì)所構(gòu)建的游戲領(lǐng)域知識(shí)庫(kù)質(zhì)量進(jìn)行評(píng)測(cè)。

3.2 游戲攻略中游戲術(shù)語的抽取

游戲攻略所包含的游戲術(shù)語大多屬于未登錄詞即新詞，無法使用傳統(tǒng)的分詞方法進(jìn)行抽取。因?yàn)椋瑐鹘y(tǒng)的分詞方法要想達(dá)到分詞的準(zhǔn)確性必須依賴詞庫(kù)的完整性，然而目前詞庫(kù)無法窮舉出所有的未登錄詞?；谟螒蛐g(shù)語的特點(diǎn)，本文提出一種新的游戲術(shù)語抽取方法：游戲領(lǐng)域詞匯發(fā)現(xiàn)算法。

游戲領(lǐng)域詞匯發(fā)現(xiàn)算法在新詞發(fā)現(xiàn)算法[3]的基礎(chǔ)之上優(yōu)化得到。新詞發(fā)現(xiàn)算法判斷一個(gè)文本片段是否成詞的標(biāo)準(zhǔn)為：“內(nèi)部凝固程度”和“自由運(yùn)用程度”。由于語料庫(kù)的不同，對(duì)成詞標(biāo)準(zhǔn)的計(jì)算進(jìn)行了優(yōu)化以適應(yīng)游戲領(lǐng)域?！皟?nèi)部凝固程度”的計(jì)算公式為：

(3)

(4)

其中，λ1λ2λ3表示一個(gè)詞是由λ1、λ2、λ3三部分組成，在使用的時(shí)候可能不止這三部分其計(jì)算原理是一樣的。P(λ)為λ出現(xiàn)的概率，length為長(zhǎng)度，num為詞頻，Text是整個(gè)語料庫(kù)。例如，“蝙蝠俠”“自由運(yùn)用程度”就是P(蝙蝠俠)與P(蝙蝠)·P(俠)的比值和P(蝙蝠俠)與P(蝙)·P(蝠俠)的比值中的較小值。

“自由運(yùn)用程度”也是成詞的重要標(biāo)準(zhǔn)之一。一個(gè)文本片段可以成詞的話，肯定有非常豐富的左鄰字和右鄰字。例如“我最近眼睛痛，可能是用眼睛過度，應(yīng)該保證眼睛適當(dāng)?shù)男菹ⅲ驗(yàn)檠劬κ俏覀冃撵`的窗戶”。這句話中“眼睛”一次共出現(xiàn)四次，它的左鄰字集合為{近，用，證，為}，右鄰字集合為{痛，過，適，是}。這里，使用信息熵進(jìn)行衡量。通過對(duì)游戲攻略的觀察，發(fā)現(xiàn)每個(gè)攻略數(shù)據(jù)所包含的內(nèi)容較短且由多個(gè)段落組成，故屬于短文本。在計(jì)算信息熵時(shí)，會(huì)經(jīng)常出現(xiàn)一個(gè)詞的左鄰字是開頭或者是標(biāo)點(diǎn)符號(hào)，右鄰字是結(jié)尾或者標(biāo)點(diǎn)符號(hào)。針對(duì)這種情況本文的處理是視其左鄰字或右鄰字為一個(gè)未出現(xiàn)的新詞，并統(tǒng)計(jì)出現(xiàn)這種左鄰字或右鄰字的詞頻。通過以上的改進(jìn)得到信息熵的計(jì)算方法為：設(shè)一個(gè)詞W的左鄰字集合為{X1,X2,…,Xn}，則W的左鄰字信息熵為：

n+m=num(W)

(6)

由式(5)和式(6)可得：

其中：P(X)=num(XW)/num(W)，num(Otherl)為左鄰字是開頭或者標(biāo)點(diǎn)符號(hào)的次數(shù)。同理，設(shè)W的右它們鄰字集合為{Y1,Y2,…,Yn}，可得到W的右鄰字信息熵的計(jì)算公式為：

其中：P(Y)=num(YW)/num(W)，num(Otherr)為右鄰字是結(jié)尾或者標(biāo)點(diǎn)符號(hào)的次數(shù)。綜合左鄰字信息熵和右鄰字信息熵，可得信息熵的計(jì)算公式為：

H=min{H(X),H(Y)}

(9)

針對(duì)游戲攻略數(shù)據(jù)的特點(diǎn)，在實(shí)際的抽取過程中還進(jìn)行了如下改進(jìn)：

1)候選詞長(zhǎng)度d的調(diào)整。該算法必須設(shè)定候選詞長(zhǎng)度，候選詞長(zhǎng)度的選取直接影響鏈接的準(zhǔn)確率和效率：若過小，則會(huì)丟失很多游戲術(shù)語；若過大，則會(huì)摻雜很多無用的詞匯。針對(duì)不同的游戲，所設(shè)置的候選長(zhǎng)度也會(huì)不同。具體調(diào)節(jié)策略為：候選詞長(zhǎng)度為知識(shí)庫(kù)中游戲術(shù)語的長(zhǎng)度最大值。如此，所抽取的候選詞不會(huì)產(chǎn)生遺漏現(xiàn)象，也不會(huì)摻雜過多無關(guān)詞匯，從而提高抽取的質(zhì)量。

2)將語料庫(kù)中出現(xiàn)的英文和數(shù)字進(jìn)行預(yù)先處理存儲(chǔ)在候選詞集合中，然后進(jìn)行正常的抽取。之所以事先抽取英文詞語，是因?yàn)楣ヂ詳?shù)據(jù)絕大部分是中文，即使出現(xiàn)英文也是一個(gè)完整的英文單詞。如果在正常抽取過程中抽取英文單詞，則會(huì)將英文詞的子串加入到候選集合中。對(duì)于熱門游戲來說，游戲術(shù)語不會(huì)出現(xiàn)有數(shù)字的情況。預(yù)先處理數(shù)字可以提高抽取的效率和質(zhì)量。

該算法的偽代碼為：

輸入：setStrategies, Set of game strategy 輸出：setPhrases, Set of phrase that meet conditions

1)

foreachstrategy∈setStrategiesdo

2)

PhraseMap←length<=d(phrase;num)

3)

ifleftPhraseexiststhen

4)

LeftPhraseMap←leftPhrase

5)

ifleftPhraseispunctuationorbeginningthen

6)

PBMap← (LeftPhrase, 1)

7)

rightPhrasesame asleftPhrase

8)

if!leftPhrase‖!rightPhrasethenAsanewword

9)

PhraseSet← 1

10)

setPhrase←Phrase(C,H,num)

11)

endfor

該算法的輸入為游戲攻略數(shù)據(jù)，輸出為滿足條件的詞組集合，第2)行是抽取長(zhǎng)度不大于d的詞組的詞頻。該算法得到包括游戲術(shù)語在內(nèi)的詞組及該詞組的凝合度、信息熵和詞頻。得到的詞組包含大量的無用詞匯，比如得到的詞組中包含黑魔法師，但也包含魔法、法師等無用詞匯。對(duì)此，本文使用二分類模型進(jìn)行過濾。以每個(gè)詞的凝合度、信息熵、詞頻作為特征訓(xùn)練二分類模型：一類是需要的候選詞，另一類是不需要的。首先，從詞組列表中隨機(jī)選取2 000條數(shù)據(jù)進(jìn)行人工標(biāo)注，分別選取支持向量機(jī)(Support Vector Machine, SVM)、貝葉斯和決策樹[16]作為分類模型，使用十折交叉驗(yàn)證測(cè)試每個(gè)分類模型的準(zhǔn)確率。整個(gè)分類的過程使用機(jī)器學(xué)習(xí)工具Weka實(shí)現(xiàn)。最后，得到?jīng)Q策樹分類模型的準(zhǔn)確率最高，為97.4%。因此，選取決策樹作為分類模型過濾出所需的候選詞匯即mention列表。

3.3 實(shí)體鏈接

本文的實(shí)體鏈接任務(wù)為：將攻略標(biāo)題中出現(xiàn)的游戲術(shù)語和知識(shí)庫(kù)中的游戲術(shù)語進(jìn)行鏈接，從而得到每條攻略數(shù)據(jù)的標(biāo)簽。通過對(duì)多款熱門游戲觀察可知，攻略標(biāo)題包含游戲術(shù)語有以下幾種情況。

1)攻略標(biāo)題只包含一個(gè)游戲術(shù)語。例如，標(biāo)題為“傳奇世界傳承珠完全使用的攻略”的攻略，它包含一個(gè)游戲術(shù)語“傳承珠”。該攻略的標(biāo)簽類型為單標(biāo)簽。

2)攻略標(biāo)題中包含多個(gè)游戲術(shù)語。例如，標(biāo)題為“傳奇世界武士的終極裝備搭配”的攻略，它包含兩個(gè)游戲術(shù)語“武士”和“裝備”。該攻略的標(biāo)簽類型為多標(biāo)簽。

3)攻略標(biāo)題中游戲術(shù)語是知識(shí)庫(kù)中游戲術(shù)語的簡(jiǎn)稱。例如，標(biāo)題為“爆發(fā)吧黑魔法 黑魔副本輸出手法經(jīng)驗(yàn)談”的攻略，它包含的游戲術(shù)語“黑魔”是知識(shí)庫(kù)中“黑魔法師”的簡(jiǎn)稱。

基于上述情況的考慮，本文提出了適合游戲攻略的鏈接算法，實(shí)現(xiàn)了游戲攻略中術(shù)語和知識(shí)庫(kù)的一一映射，進(jìn)而達(dá)到標(biāo)注的目的。具體鏈接算法的流程如圖3所示。

在圖3中，mention列表是由游戲領(lǐng)域詞匯發(fā)現(xiàn)算法和決策樹分類模型得到的候選詞集合。若標(biāo)題中包含mention，必須選取長(zhǎng)度最長(zhǎng)的mention和知識(shí)庫(kù)鏈接。例如，知識(shí)庫(kù)中包含“白魔法師”“黑魔法師”，攻略標(biāo)題包含“黑魔法師”，候選詞有“法師”“黑魔法師”。若不選取最長(zhǎng)的候選詞則鏈接時(shí)會(huì)引入錯(cuò)誤標(biāo)簽“白魔法師”。mention和知識(shí)庫(kù)不完全匹配時(shí)的相似度計(jì)算公式為式(2)。

4 實(shí)驗(yàn)評(píng)測(cè)

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

本文語料庫(kù)為游戲攻略數(shù)據(jù)。選取4款熱門游戲進(jìn)行測(cè)試，分別為“部落沖突”“傳奇世界”“英雄聯(lián)盟”和“最終幻想14”。從這4款游戲的多個(gè)資訊網(wǎng)站中爬取游戲攻略數(shù)據(jù)，并進(jìn)行去重后，每款游戲各選取1 500條進(jìn)行實(shí)驗(yàn)。為了驗(yàn)證測(cè)試結(jié)果，本文采用文本標(biāo)注實(shí)驗(yàn)時(shí)經(jīng)常使用的評(píng)價(jià)標(biāo)準(zhǔn)：準(zhǔn)確率(Precision)和召回率(Recall)。若定義Num(right)為正確標(biāo)注的數(shù)據(jù)個(gè)數(shù)，Num(wrong)表示錯(cuò)誤標(biāo)注的數(shù)據(jù)個(gè)數(shù)，Num(null)表示沒有標(biāo)注的數(shù)據(jù)個(gè)數(shù)，則準(zhǔn)確率和召回率的定義分別如下：

(10)

(11)

圖3 實(shí)體鏈接算法流程

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

在抽取攻略數(shù)據(jù)中的游戲術(shù)語時(shí)，除了使用本文提出的方法抽取游戲術(shù)語外，還和n-gram語言模型進(jìn)行對(duì)比。n-gram語言模型是一種基于統(tǒng)計(jì)的文本模型，在抽取術(shù)語領(lǐng)域中得到廣泛的研究。這種方法主要通過對(duì)語料庫(kù)的機(jī)器學(xué)習(xí)來獲得字與字相鄰出現(xiàn)的統(tǒng)計(jì)信息而進(jìn)行分詞，它的一個(gè)明顯優(yōu)點(diǎn)是可以切分出未登錄詞，也是一種新詞發(fā)現(xiàn)方法。它的切分詞的思想和本文提出的游戲領(lǐng)域詞匯發(fā)現(xiàn)算法類似，成詞標(biāo)準(zhǔn)都與上下文信息有關(guān)。最后，根據(jù)標(biāo)注結(jié)果的準(zhǔn)確率和召回率對(duì)本文方法和n-gram模型進(jìn)行比較。

在游戲攻略標(biāo)注的過程中，標(biāo)注錯(cuò)誤的情況如表1所示。

表1 標(biāo)注錯(cuò)誤的類型

對(duì)于未標(biāo)注的攻略，發(fā)現(xiàn)大多為玩家心情類。例如，標(biāo)題為“去年和你一起跑復(fù)活節(jié)的那個(gè)人，今年在哪里”的攻略，標(biāo)題中并未包含游戲術(shù)語，因此本文對(duì)這類標(biāo)題無法標(biāo)注。對(duì)于這類文本的標(biāo)注還有待研究。使用本文方法和n-gram模型(n取2或3)對(duì)4款游戲進(jìn)行標(biāo)注，得到的準(zhǔn)確率和召回率如圖4所示。

通過圖4可以看出，在這4款游戲中，本文所提出的方法得到的準(zhǔn)確率和召回率均大于n-gram方法。在這4款游戲中，使用本文方法得到的準(zhǔn)確率平均為92.0%，平均召回率為87.1%；使用2-gram得到的平均準(zhǔn)確率為57.8%，平均召回率為72.0%；使用3-gram得到的平均準(zhǔn)確率為64.7%，平均召回率為67.0%。得出本文方法相比2-gram，平均準(zhǔn)確率提高了34.2個(gè)百分點(diǎn)，平均召回率提高了15.1個(gè)百分點(diǎn)；本文方法相比3-gram，平均準(zhǔn)確率提高了27.3個(gè)百分點(diǎn)，平均召回率提高了20.1個(gè)百分點(diǎn)。從數(shù)據(jù)分析可知，在抽取攻略中游戲術(shù)語時(shí)，本文所提出的方法相比n-gram語言模型更好。使用n-gram語言模型時(shí)，n的值一般取2或3。n過大，需要訓(xùn)練更龐大的語料，并且數(shù)據(jù)稀疏嚴(yán)重；同時(shí)，伴隨著n的增大，采用該模型所帶來的計(jì)算量和計(jì)算復(fù)雜度將遠(yuǎn)遠(yuǎn)超過現(xiàn)有的計(jì)算機(jī)水平。有的游戲術(shù)語較長(zhǎng)，當(dāng)n取2或3，會(huì)將游戲術(shù)語分割成多個(gè)更細(xì)粒度的詞匯，鏈接時(shí)會(huì)引入有歧義的標(biāo)簽。

圖4 不同游戲在不同詞匯抽取方法下的比較

通過統(tǒng)計(jì)這4款游戲的標(biāo)注情況，具體如表2，可知每款游戲標(biāo)注的攻略占總攻略數(shù)據(jù)的平均95%左右。對(duì)沒有標(biāo)注的數(shù)據(jù)，統(tǒng)計(jì)發(fā)現(xiàn)4%左右的攻略標(biāo)題中不包含游戲術(shù)語，從而可以驗(yàn)證使用本文所提出的方法構(gòu)建游戲領(lǐng)域知識(shí)庫(kù)覆蓋面廣，質(zhì)量高。

表2 不同游戲的游戲攻略標(biāo)注情況

5 結(jié)語

本文針對(duì)游戲攻略檢索需花費(fèi)大量時(shí)間問題，對(duì)游戲攻略進(jìn)行標(biāo)注。每個(gè)游戲攻略的標(biāo)簽為其所包含的游戲術(shù)語所對(duì)應(yīng)的全稱。本文的主要優(yōu)點(diǎn)為：針對(duì)游戲攻略中游戲術(shù)語的特點(diǎn)提出一種新的抽取游戲術(shù)語的抽取方法：游戲領(lǐng)域詞匯發(fā)現(xiàn)算法和決策樹分類模型。和n-gram語言模型進(jìn)行對(duì)比，結(jié)果顯示本文方法在游戲術(shù)語抽取問題上的有效性，解決了在領(lǐng)域詞匯術(shù)語抽取工作上一直存在的抽取質(zhì)量問題。數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的方法達(dá)到較高的準(zhǔn)確率和召回率。接下來計(jì)劃將攻略標(biāo)簽用于攻略分類及攻略搜索系統(tǒng)的構(gòu)建，并將本文方法應(yīng)用于其他領(lǐng)域進(jìn)行領(lǐng)域詞匯抽取，如計(jì)算機(jī)領(lǐng)域、醫(yī)療領(lǐng)域等。

References)

[1] 馬瑩瑩.對(duì)網(wǎng)絡(luò)游戲產(chǎn)業(yè)同質(zhì)化現(xiàn)象的分析[J].科技和產(chǎn)業(yè),2012,12(8):13-15.(MA Y Y.Analysis the online game industry homogenization phenomenon [J].Science Technology and Industry, 2012, 12(8): 13-15.)

[2] 王研,趙旭江.游戲設(shè)計(jì)中的用戶體驗(yàn)影響探析注——以“英雄聯(lián)盟”為例[J].設(shè)計(jì),2014(2):118-119.(WANG Y, ZHAO X J.The study on the influence of user experience in game design——an instance of “l(fā)eague of legends” [J].Design, 2014(2): 118-119.)

[3] 顧森.基于大規(guī)模語料的新詞發(fā)現(xiàn)算法[J].程序員,2012(7):54-57.(GU S.New word discovery algorithm based on large scale corpus [J].Programmer, 2012(7): 54-57.)

[4] LEHMANN J, ISELE R, JAKOB M, et al.DBpedia—a large-scale, multilingual knowledge base extracted from Wikipedia [J].Semantic Web, 2015, 6(2): 167-195.

[5] BOLLACKER K, EVANS C, PARITOSH P, et al.Freebase: a collaboratively created graph database for structuring human knowledge [C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2008: 1247-1250.

[6] RUAN T, LI Y, WANG H, et al.From queriability to informativity, assessing “quality in use” of DBpedia and YAGO [C]// Proceedings of the 2016 International Semantic Web Conference.Berlin: Springer, 2016: 52-68.

[7] JUSTESON J S, KATZ S M.Technical terminology: some linguistic properties and an algorithm for identification in text [J].Natural Language Engineering, 1995, 1(1): 9-27.

[8] VILARES J, ALONSO M A, VILARES M.Extraction of complex index terms in non-English IR: a shallow parsing based approach [J].Information Processing & Management, 2008, 44(4): 1517-1537.

[9] BLEI D M.Probabilistic topic models [J].Communications of the ACM, 2012, 55(4): 77-84.

[10] BOLSHAKOVA E, LOUKACHEVITCH N, NOKEL M.Topic models can improve domain term extraction [C]// Proceedings of the 2013 European Conference on Information Retrieval.Berlin: Springer, 2013: 684-687.

[11] 周浪,張亮,馮沖,等.基于詞頻分布變化統(tǒng)計(jì)的術(shù)語抽取方法[J].計(jì)算機(jī)科學(xué),2009,36(5):177-180.(ZHOU L, ZHANG L, FENG C, et al.Terminology extraction based on statistical word frequency distribution variety [J].Computer Science, 2009, 36(5): 177-180.)

[12] GELBUKH A, SIDOROV G, LAVIN-VILLA E, et al.Automatic term extraction using log-likelihood based comparison with general reference corpus [C]// Proceedings of the 2010 International Conference on Application of Natural Language to Information Systems.Berlin: Springer, 2010: 248-255.

[13] 陳士超,郁濱.面向術(shù)語抽取的雙閾值互信息過濾方法[J].計(jì)算機(jī)應(yīng)用,2011,31(4):1070-1073.(CHEN S C, YU B.Method of mutual information filtration with dual threshold for term extraction [J].Journal of Computer Applications, 2011, 31(4): 1070-1073.)

[14] 樊夢(mèng)佳，段東圣，杜翠蘭，等.統(tǒng)計(jì)與規(guī)則相融合的領(lǐng)域術(shù)語抽取算法[J].計(jì)算機(jī)應(yīng)用研究，2016,33(8):2283-2306.(FAN M J, DUAN D S, DU C L, et al.Domain-specific terms extraction algorithm based on combination of statistics and rules [J].Application Research of Computers, 2016, 33(8): 2283-2306.)

[15] BONIN F, DELL’ORLETTA F, VENTURI G, et al.A contrastive approach to multi-word term extraction from domain corpora [C]// Proceedings of the 7th International Conference on Language Resources and Evaluation.Malta: [s.n.], 2010: 19-21.

[16] ZHANG M, LI K, HU Y.A real-time classification method of power quality disturbances [J].Electric Power Systems Research, 2011, 81(2): 660-666.

This work is partially supported by the National Science Foundation of China (61402173), the Software and Integrated Circuit Industry Development Special Funds of Shanghai Economy and Information Technology Commission (140304).

CHEN Huanhuan, born in 1990, M.S.candidate.Her research interests include data mining, natural language processing.

CHEN Xiaohong, born in 1974.His research interests include big data, user behavior in virtual world.

RUAN Tong, born in 1973, Ph.D., professor.Her research interests include natural language processing, information extraction, data quality.

GAO Daqi, born in 1957, Ph.D., professor.His research interests include pattern recognition, machine learning.

WANG Haofen, born in 1982, Ph.D., lecturer.His research interests include knowledge graph, graph database, data mining.

Knowledge driven automatic annotating algorithm for game strategies

CHEN Huanhuan1*, CHEN Xiaohong2, RUAN Tong1, GAO Daqi1, WANG Haofen1

(1.DepartmentofComputerScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China;2.ShengquInformationTechnology(Shanghai)CompanyLimited,Shanghai201203,China)

To help users to quickly retrieve the interesting game strategies, a knowledge driven automatic annotating algorithm for game strategies was proposed.In the proposed algorithm, the game domain knowledge base was built automatically by fusing multiple sites that provide information for each game.By using the game domain vocabulary discovering algorithm and decision tree classification model, game terms of the game strategies were extracted.Since most terms existing in the strategies in the form of abbreviation, the game terms were finally linked to knowledge base to generate the full name semantic tags for them.The experimental results on many games show that the precision of the proposed game strategy annotating method is as high as 90%.Moreover, the game domain vocabulary discovering algorithm has a better result compared with then-gram language model.

game strategy; knowledge base; game term; semantic tag; decision tree

2016-08-18;

2016-09-06。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402173)；上海經(jīng)信委“軟件集成電路產(chǎn)業(yè)發(fā)展專項(xiàng)資金”項(xiàng)目(140304)。

陳環(huán)環(huán)(1990—)，女，山東菏澤人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、自然語言處理； 陳小紅(1974—)，男，浙江永康人，主要研究方向：大數(shù)據(jù)、虛擬世界的用戶行為； 阮彤(1973—),女，江蘇揚(yáng)州人，教授，博士，CCF會(huì)員，主要研究方向：自然語言處理、信息抽取、數(shù)據(jù)質(zhì)量； 高大啟(1957—)，男，湖北宜昌人，教授，博士，主要研究方向：模式識(shí)別、機(jī)器學(xué)習(xí)； 王昊奮(1982—)，男，上海人，講師，博士，CCF會(huì)員，主要研究方向：知識(shí)圖譜、圖數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘。

1001-9081(2017)01-0278-06

10.11772/j.issn.1001-9081.2017.01.0278

TP391.1

A