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

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

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

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

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

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

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

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

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

0 引言

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

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

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

本文的主要工作如下：

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

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

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

1 相關(guān)工作

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

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

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

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

2)基于統(tǒng)計的方法。利用術(shù)語內(nèi)部各組成成分之間較高的關(guān)聯(lián)程度以及術(shù)語的領(lǐng)域特征信息來抽取術(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)點是通用性較強(qiáng)，缺點是針對稀疏數(shù)據(jù)效果較差。

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

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

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

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

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

圖1 算法整體流程

圖2 知識庫結(jié)構(gòu)

2.2 問題定義

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

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

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

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

針對滿足以上條件的熱門游戲，本文的主要任務(wù)可以描述為：對于給定的語料庫(Corpus)，抽取出每條攻略所包含的游戲術(shù)語集合M={mention | mention in title}，在知識庫中找到其對應(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é)中會詳細(xì)介紹。

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

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

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

首先，對模式層進(jìn)行融合。模式層所產(chǎn)生的沖突主要表現(xiàn)為：同一個子類在不同的資訊網(wǎng)站中所屬父類不同?？梢悦枋鰹椋涸O(shè)有三個類A、B、C，類C在不同的網(wǎng)站中分別屬于不同的父類A和B。首先根據(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ù)，通過這個公式可得RA和RB。若RA>RB，將類C劃分到類A下；若RA

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

(2)

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

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

2)0.5

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

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

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

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

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

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

(3)

(4)

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

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

n+m=num(W)

(6)

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

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

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

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

(9)

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

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

2)將語料庫中出現(xiàn)的英文和數(shù)字進(jìn)行預(yù)先處理存儲在候選詞集合中，然后進(jìn)行正常的抽取。之所以事先抽取英文詞語，是因為攻略數(shù)據(jù)絕大部分是中文，即使出現(xiàn)英文也是一個完整的英文單詞。如果在正常抽取過程中抽取英文單詞，則會將英文詞的子串加入到候選集合中。對于熱門游戲來說，游戲術(shù)語不會出現(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)行是抽取長度不大于d的詞組的詞頻。該算法得到包括游戲術(shù)語在內(nèi)的詞組及該詞組的凝合度、信息熵和詞頻。得到的詞組包含大量的無用詞匯，比如得到的詞組中包含黑魔法師，但也包含魔法、法師等無用詞匯。對此，本文使用二分類模型進(jìn)行過濾。以每個詞的凝合度、信息熵、詞頻作為特征訓(xùn)練二分類模型：一類是需要的候選詞，另一類是不需要的。首先，從詞組列表中隨機(jī)選取2 000條數(shù)據(jù)進(jìn)行人工標(biāo)注，分別選取支持向量機(jī)(Support Vector Machine, SVM)、貝葉斯和決策樹[16]作為分類模型，使用十折交叉驗證測試每個分類模型的準(zhǔn)確率。整個分類的過程使用機(jī)器學(xué)習(xí)工具Weka實現(xiàn)。最后，得到?jīng)Q策樹分類模型的準(zhǔn)確率最高，為97.4%。因此，選取決策樹作為分類模型過濾出所需的候選詞匯即mention列表。

3.3 實體鏈接

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

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

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

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

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

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

4 實驗評測

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

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

(10)

(11)

圖3 實體鏈接算法流程

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

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

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

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

對于未標(biāo)注的攻略，發(fā)現(xiàn)大多為玩家心情類。例如，標(biāo)題為“去年和你一起跑復(fù)活節(jié)的那個人，今年在哪里”的攻略，標(biāo)題中并未包含游戲術(shù)語，因此本文對這類標(biāo)題無法標(biāo)注。對于這類文本的標(biāo)注還有待研究。使用本文方法和n-gram模型(n取2或3)對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個百分點，平均召回率提高了15.1個百分點；本文方法相比3-gram，平均準(zhǔn)確率提高了27.3個百分點，平均召回率提高了20.1個百分點。從數(shù)據(jù)分析可知，在抽取攻略中游戲術(shù)語時，本文所提出的方法相比n-gram語言模型更好。使用n-gram語言模型時，n的值一般取2或3。n過大，需要訓(xùn)練更龐大的語料，并且數(shù)據(jù)稀疏嚴(yán)重；同時，伴隨著n的增大，采用該模型所帶來的計算量和計算復(fù)雜度將遠(yuǎn)遠(yuǎn)超過現(xiàn)有的計算機(jī)水平。有的游戲術(shù)語較長，當(dāng)n取2或3，會將游戲術(shù)語分割成多個更細(xì)粒度的詞匯，鏈接時會引入有歧義的標(biāo)簽。

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

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

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

5 結(jié)語

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

References)

[1] 馬瑩瑩.對網(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è)計中的用戶體驗影響探析注——以“英雄聯(lián)盟”為例[J].設(shè)計,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)計的術(shù)語抽取方法[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ī)應(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] 樊夢佳，段東圣，杜翠蘭，等.統(tǒng)計與規(guī)則相融合的領(lǐng)域術(shù)語抽取算法[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。

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

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

1001-9081(2017)01-0278-06

10.11772/j.issn.1001-9081.2017.01.0278

TP391.1

A