程 傳 鵬

(中原工學(xué)院 計(jì)算機(jī)學(xué)院，鄭州 450007)

1 引 言

關(guān)鍵詞指的是文檔中比較能夠體現(xiàn)文檔的重要信息和核心內(nèi)容的詞語，主要應(yīng)用在搜索引擎搜索結(jié)果的展示、自動(dòng)文摘、推薦系統(tǒng)、自動(dòng)問答等方面[1].目前對(duì)關(guān)鍵詞抽取的研究主要分為四類，一種是基于詞頻的方法，比如詞語共現(xiàn)、TFIDF，在這類研究中主要應(yīng)用的是TF*IDF的方法來計(jì)算關(guān)鍵詞的權(quán)重，然后根據(jù)句子中候選關(guān)鍵詞的權(quán)重來選擇出主題句，該方法的程序?qū)崿F(xiàn)簡單，原理較為直觀，應(yīng)用也最為廣泛，但該方法在計(jì)算關(guān)鍵詞的權(quán)重時(shí)只是簡單的考慮了詞語共現(xiàn)的關(guān)系，沒有考慮到詞語之間的聯(lián)系，第二類方法是利用文檔的篇章結(jié)構(gòu)來抽取關(guān)鍵詞，文獻(xiàn)[2]利用段落和句子的不同位置，分別給出了初始權(quán)重，接下來根據(jù)主題單詞與前后相鄰單詞之間的相關(guān)性進(jìn)行詞組篩選合并，形成備選關(guān)鍵詞組集合.最后綜合考慮數(shù)字、大小寫、單詞數(shù)、平均單詞長度和主題單詞選取順序5個(gè)因素，對(duì)備選關(guān)鍵詞進(jìn)行評(píng)分，并選取得分高的關(guān)鍵詞作為最后的結(jié)果.第三類方法是利用機(jī)器學(xué)習(xí)的方法來抽取關(guān)鍵詞[3-5]，該方法利用大量的訓(xùn)練語料來學(xué)習(xí)出關(guān)鍵詞模型的特征，通過大量訓(xùn)練集所得出的學(xué)習(xí)模型來選擇關(guān)鍵詞，比較適合多文檔關(guān)鍵詞的抽取，關(guān)鍵詞抽取的好壞依賴于所選擇機(jī)器學(xué)習(xí)訓(xùn)練語料質(zhì)量的優(yōu)劣.第四類方法是基于語義理解的方法[6-9]，該類方法利用同義詞詞典對(duì)候選詞語進(jìn)行過濾或者利用語義詞典(HowNet或WordNet)將詞語用詞義替代，從而提高了關(guān)鍵詞提取的準(zhǔn)確度.

本文利用詞語之間的聯(lián)系來構(gòu)造詞語聯(lián)系圖，基于TextRank算法，在Spark平臺(tái)上利用GraphX圖計(jì)算框架，快速高效的計(jì)算出候選關(guān)鍵詞的權(quán)重.文章主要由三部分組成，第一部分分析了候選關(guān)鍵詞權(quán)重的計(jì)算原理；第二部分介紹了基于Spark Graph X的關(guān)鍵詞抽取算法的具體實(shí)現(xiàn)步驟.第三部分利用真實(shí)的語料，根據(jù)本文所提出的方法進(jìn)行實(shí)驗(yàn)論證，并對(duì)實(shí)驗(yàn)結(jié)果做出了合理的評(píng)價(jià)和分析；第四部分，對(duì)文中方法進(jìn)行了總結(jié)，并指出了不足的地方以及未來研究的方向.

2 基本理論介紹

1998年，斯坦福大學(xué)兩個(gè)博士生Sergey Brin(謝爾蓋·布林 )和Lawrence Page(拉里·佩奇)提出了一種名為PageRank算法，該算法根據(jù)網(wǎng)頁之間相互的鏈接關(guān)系計(jì)算網(wǎng)頁排名，算法采用遞歸的定義，不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計(jì)值能收斂到它們的真實(shí)值[10].2004年Rada Mihalcea and Paul Tarau應(yīng)用圖的排序算法，在谷歌的 PageRank算法思想的基礎(chǔ)上提出了TextRank 算法[11]，TextRank 算法綜合考慮了單詞間的位置關(guān)系和出現(xiàn)頻率，其算法的核心思想和 PageRank 相同，即在文本網(wǎng)絡(luò)中節(jié)點(diǎn)(詞)的重要程度取決于與它相連的單詞的分給它的票數(shù)，其計(jì)算公式如公式(1)所示.

(1)

其中，W(Wordi)為候選關(guān)鍵詞的權(quán)重，In(Wordi)為Wordi與相連的詞語，Out(wordj)為與wordj相連的詞語個(gè)數(shù)，d取值一般為0.85，文獻(xiàn)里稱之為阻尼系數(shù)[13].

使用TextRank對(duì)文本提取關(guān)鍵字的一般需要經(jīng)過文本預(yù)處理、詞語過濾、構(gòu)造文本圖、迭代計(jì)算候選詞權(quán)重、關(guān)鍵詞輸出五個(gè)步驟，在文本文本預(yù)處理階段，將文本按照完整句子進(jìn)行切分并進(jìn)行詞性標(biāo)注處理；在詞語過濾階段，過濾掉停用詞，只保留指定詞性的單詞，如名詞、動(dòng)詞、等能夠體現(xiàn)文本中心思想，具有豐富語意的詞；構(gòu)造文本圖的主要操作是根據(jù)設(shè)定的詞語選擇窗口截取文本的分詞結(jié)果，將每個(gè)詞語作為候選關(guān)鍵詞圖的節(jié)點(diǎn)，截取的每一段文本中的詞語作為相鄰的邊，以此構(gòu)建候選關(guān)鍵詞圖；循環(huán)迭代計(jì)算候選關(guān)鍵詞權(quán)重， 每個(gè)節(jié)點(diǎn)的權(quán)重初始化化為1.0，通過設(shè)定的迭代次數(shù)達(dá)到穩(wěn)定后；對(duì)節(jié)點(diǎn)權(quán)重進(jìn)行倒序排序，從而得到最重要的一些詞語，作為候選關(guān)鍵詞.下面以一段具體的文本，給出關(guān)鍵詞的選擇過程.

長期以來，判定醫(yī)療質(zhì)量的指標(biāo)多是以出院病人的終末結(jié)果為依據(jù)，這是從醫(yī)務(wù)人員角度設(shè)計(jì)的判斷標(biāo)準(zhǔn).隨著醫(yī)療作為一種服務(wù)業(yè)進(jìn)入市場，越來越多的病人將以自己對(duì)醫(yī)療質(zhì)量的理解和觀念來評(píng)選醫(yī)院和醫(yī)師，參與醫(yī)療質(zhì)量的評(píng)價(jià).

在指定滑動(dòng)窗口為2的時(shí)候，構(gòu)造的文本圖如圖1所示.

圖1 文本網(wǎng)絡(luò)Fig.1 Text network

根據(jù)前面的公式(1)，“醫(yī)療”詞語的權(quán)重，由公式(2)給出，其它詞語的權(quán)重計(jì)算方法類似.

(2)

經(jīng)過迭代20次以后，權(quán)重趨于收斂，文本圖中每個(gè)詞語的權(quán)重如表1所示.

3 基于Spark GraphX的候選關(guān)鍵詞權(quán)重計(jì)算

GraphX是構(gòu)建在Spark之上的圖計(jì)算框架，它將圖數(shù)據(jù)以RDD分布式地存儲(chǔ)在集群的節(jié)點(diǎn)上，使用頂點(diǎn)RDD(VertexRDD)、邊RDD(EdgeRDD)存儲(chǔ)頂點(diǎn)集合和邊集合，高效地實(shí)現(xiàn)了圖的分布式存儲(chǔ)和處理，并提供了屬性操作、結(jié)構(gòu)操作、關(guān)聯(lián)操作、聚合操作、緩存操作等實(shí)用的圖操作方法.除此之外，目前最新版本GraphX已支持PageRank、數(shù)三角形、最大連通圖和最短路徑等6種經(jīng)典的圖算法.GraphX對(duì)Spark RDD進(jìn)行了封裝，采用了Pregel的編程模型，他們自定義了sendMessage函數(shù)，vertexProgram函數(shù)，和mergeMessage函數(shù)，然后交給Pregel去運(yùn)行，而在Pregel中，他的核心函數(shù)是圖的mapReduceTriplets，通過一定的規(guī)則不斷迭代，直到產(chǎn)生的activeMessage為0或者滿足預(yù)先指定的迭代次數(shù)，最后計(jì)算得到相應(yīng)的結(jié)果.GraphX在圖頂點(diǎn)信息和邊信息存儲(chǔ)上做了優(yōu)化，使得圖計(jì)算框架性能相對(duì)于原生RDD實(shí)現(xiàn)得以較大提升，接近或達(dá)到GraphLab等專業(yè)圖計(jì)算平臺(tái)的性能，可以方便且高效地完成圖計(jì)算的一整套流水作業(yè)，其架構(gòu)如圖2所示.

表1 詞語權(quán)重Table 1 Word weight

圖2 Spark GraphX 框架結(jié)構(gòu)圖Fig.2 Spark GraphX frame structure

GraphX綜合了Pregel和GAS兩者的優(yōu)點(diǎn)，即接口相對(duì)簡單，又保證性能，可以應(yīng)對(duì)點(diǎn)分割的圖存儲(chǔ)模式，勝任符合冪律分布的自然圖的大型計(jì)算.基于Spark GraphX圖計(jì)算框架的特點(diǎn)，本文給出關(guān)鍵詞抽取步驟主要有以下5個(gè)步驟：

第1步. 程序運(yùn)行環(huán)境的配置

首先在程序的開始，導(dǎo)入Spark運(yùn)行環(huán)境配置包，Spark GraphX圖計(jì)算框架包，控制程序輸出信息包以及分詞所需要的包.

第2步. 文本預(yù)處理階段

結(jié)合語料的性質(zhì)，可以增加切分度更高的自定義詞典，自定義詞典文本中每一行存放一個(gè)詞，逐行讀入文本文件，將其添加到自定義詞典中.在添加完用戶自定義字典和停用詞詞典后，用SparkContext對(duì)象sc讀入要分詞的文件，將文本轉(zhuǎn)換為彈性分布式數(shù)據(jù)集(RDD)，其中停止詞過濾字符串為("w"，null，"ns"，"r"，"u"，"e"，""，"uj"，"a"，"c"，"p"，"d"，"j"，"q").

第3步. 文本圖的構(gòu)建

為了在Spark GraphX中運(yùn)行程序，需要構(gòu)造文本圖，分為兩個(gè)部分，一個(gè)是構(gòu)造圖的頂點(diǎn)，由詞語組成，第二部分是構(gòu)造圖的邊，由滑動(dòng)窗口內(nèi)的詞對(duì)組成圖的邊.對(duì)文本進(jìn)行分詞，從分詞結(jié)果中去掉詞性為方位詞、標(biāo)點(diǎn)符號(hào)、助詞、介詞等詞語，并對(duì)每個(gè)詞進(jìn)行標(biāo)號(hào)，頂點(diǎn)列表vertexList=List((1L，WordType(word1))，(2L，WordType(word2))，(3L，WordType(word3))，……(iL，WordType(wordi))，……(nL，WordType(wordn)))，邊列表edgeList= List(Edge(WordNo(wordi)，NextWordNo(wordi)，iniWeight))，WordNo(wordi)意思是第i個(gè)詞語的詞標(biāo)號(hào)，NextWordNo(wordi)意思是第i個(gè)詞語的鄰接詞語的詞標(biāo)號(hào)，iniWeight是初始權(quán)重，在程序中設(shè)置為1.在構(gòu)造完頂點(diǎn)列表和邊列表后，將它們RDD化，并利用Spark graphX提供的Graph方法構(gòu)造圖.

第4步. 并行化計(jì)算候選關(guān)鍵詞的權(quán)重

將上一步所構(gòu)造的圖的頂點(diǎn)數(shù)據(jù)更新為出度，設(shè)置邊界的值為出度數(shù)目的倒數(shù)，頂點(diǎn)數(shù)據(jù)設(shè)置為1.所有頂點(diǎn)的消息初始化為0 ，遍歷每個(gè)triplet，將頂點(diǎn)的出度數(shù)發(fā)射給目標(biāo)對(duì)象，目標(biāo)對(duì)象合并所有的出度數(shù)后，將頂點(diǎn)數(shù)據(jù)進(jìn)行更新.最終處理具體代碼如下：

val outWordDegreesGraph=wordsGraph.outerJoinVertices(outDegrees){

(vId，vData，OptOutDegree) =>

OptOutDegree.getOrElse(0)

}

val weightWordEdgesGraph=outWordDegreesGraph .mapTriplets { EdgeTriplet=>

1.0/EdgeTriplet.srcAttr

}

val inputGraph=weightWordEdgesGraph .mapVertices((id，vData) => 1.0)

val firstMessage=0.0

val itr=25

val edgeDirection=EdgeDirection.Out

val updateWordVertex=(vId： Long，vData： Double，msgSum：Double)=>0.15+0.85*msgSum

val sendMsg=(triplet：EdgeTriplet[Double，Double])=>Iterator((triplet.dstId，triplet.srcAttr * triplet.attr))

val aggregateMsgs=(x： Double，y： Double)=>x+y

val influenceGraph=inputGraph.pregel(firstMessage，itr，edgeDirection)(updateWordVertex ，sendMsg，aggregateMsgs)

第5步. 候選關(guān)鍵詞詞語權(quán)重的輸出

對(duì)計(jì)算所得到的候選關(guān)鍵詞的權(quán)重按從大到小進(jìn)行排序，輸出一定數(shù)量(程序中輸出10個(gè)關(guān)鍵詞)候選關(guān)鍵詞以及相應(yīng)的權(quán)重值.

圖3 關(guān)鍵詞抽取算法流程Fig.3 Flow chart of keyword extraction algorithm

候選關(guān)鍵詞權(quán)重計(jì)算流程如圖3所示.

4 實(shí)驗(yàn)及評(píng)價(jià)

4.1 實(shí)驗(yàn)環(huán)境的配置

本實(shí)驗(yàn)采用了8臺(tái)計(jì)算機(jī)組成局域網(wǎng)，在每臺(tái)計(jì)算機(jī)上安裝的操作系統(tǒng)為Centos 6.5，JDK的版本為64位的jdk1.8.0_144，Hadoop的版本為2.7.4，Spark的版本為spark-2.1.2-bin-hadoop2.7.Master機(jī)的IP為192.168.80.121，hostname名稱為master，7臺(tái)slaves機(jī)的IP為：192.168.80.122～ 192.168.80.128，hostname名稱分別為：slave1～slave7.并確保每臺(tái)計(jì)算機(jī)之間可以兩兩ping通，8臺(tái)計(jì)算機(jī)的防火墻都為關(guān)閉狀態(tài)，確保通訊順暢.IDE采用了linux平臺(tái)的Intelli IDEA UTLIMATE 2017.2，在IDEA的Project Structure界面分別添加JDK、Spark、Scala 等工程依賴庫，其中Scala SDK的版本為2.11.0.

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

利用網(wǎng)絡(luò)爬蟲從人民網(wǎng)上爬取的時(shí)政要聞作為實(shí)驗(yàn)語料，從中篩選出7357條新聞，提取出每條新聞的標(biāo)題和新聞的正文部分，使用hadoop fs-put命令將新聞?wù)Z料存儲(chǔ)到HDFS文件系統(tǒng)，采用ansj所提供的分詞jar包對(duì)每條新聞進(jìn)行分詞并進(jìn)行詞性標(biāo)注.本文的實(shí)驗(yàn)分為4個(gè)，第一個(gè)實(shí)驗(yàn)將實(shí)驗(yàn)語料集分為不同的四組，第一組、第二組和第三組分別有1800條新聞，第四組為剩余的1957條新聞.分別用本文中所提到的方法與應(yīng)用最廣泛的TFIDF算法以及基于文檔結(jié)構(gòu)的方法進(jìn)行比較，文檔結(jié)構(gòu)方法中權(quán)值取值如表2所示.

表2 文檔結(jié)構(gòu)權(quán)重取值Table2 Weight of document structure

本文采用召回率(Recall)來衡量各個(gè)算法的優(yōu)劣，其計(jì)算公式如公式(3)所示.

(3)

其中NumManual指的是由人工選擇出的關(guān)鍵詞數(shù)量，并假設(shè)人工選擇的關(guān)鍵詞完全正確，NumManual指的是有計(jì)算機(jī)選擇出同等數(shù)量的關(guān)鍵詞中和人工選擇關(guān)鍵詞一致的詞語數(shù)量，經(jīng)過實(shí)驗(yàn)形成如圖4所示的實(shí)驗(yàn)數(shù)據(jù).

從圖4中的實(shí)驗(yàn)數(shù)據(jù)，可以看出本文中的方法在數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)3上都有較好的表現(xiàn)，在數(shù)據(jù)集4上測試的結(jié)果，本文中的方法和TFIDF的方法都沒有基于文檔結(jié)構(gòu)的測試結(jié)果好，究其原因TextRank和TFIDF的方法都和詞頻有關(guān)，而測試集4中有很多同義詞在簡單的進(jìn)行詞頻統(tǒng)計(jì)時(shí)，被當(dāng)成了不同的詞語來對(duì)待，在構(gòu)造文本圖頂點(diǎn)或者詞頻統(tǒng)計(jì)時(shí)理應(yīng)對(duì)這些同義詞進(jìn)行合并處理，這也是我們下一步工作的需要改進(jìn)的地方.

第二個(gè)實(shí)驗(yàn)是時(shí)間效率的比較，主要用本文中所提到的方法和不使用分布式計(jì)算以及h andoop平臺(tái)上的MapReduce并行分布式式計(jì)算進(jìn)行比較，其中數(shù)據(jù)集DS1共有130條新聞，DS2共有500條新聞，DS3共有2500條新聞，DS4共有7000條新聞，比較結(jié)果如圖5所示.

從圖中可以看出在小數(shù)據(jù)集的情況下，三種算法計(jì)算時(shí)間差別很小，但隨著數(shù)據(jù)量的增大，使用MapReduce的方法要優(yōu)于不使用分布式計(jì)算的方法，而本文中使用Spark 平臺(tái)的算法在時(shí)間效率上，隨著數(shù)據(jù)量的增大有著更為明顯的提高.

第三個(gè)實(shí)驗(yàn)是自身參數(shù)的調(diào)節(jié)，分別調(diào)節(jié)的迭代次數(shù)，滑窗的大小，程序運(yùn)行界面如圖6所示.

圖6 程序運(yùn)行界面Fig.6 Program interface

在程序主界面上設(shè)置Spark Maserter機(jī)的地址為spark：//master：7070，Spark Slave機(jī)數(shù)量為4，迭代次數(shù)為25，分別設(shè)置滑動(dòng)窗口的大小為2、3、4、5時(shí)，本文中的方法在四個(gè)測試數(shù)據(jù)集上所得出的實(shí)驗(yàn)結(jié)果如圖7所示.

滑動(dòng)窗口的大小為2、3，迭代次數(shù)為25，分別設(shè)置Spark Slave機(jī)數(shù)量為2、4、8時(shí)，本文中的方法在四個(gè)測試數(shù)據(jù)集上所得出的實(shí)驗(yàn)結(jié)果如圖8所示.

從圖7中可以看出滑動(dòng)窗口取值為3和4時(shí)，所抽取的關(guān)鍵詞，要好于滑動(dòng)窗口取值為2和5的時(shí)候，這說明滑動(dòng)窗口的取值大小對(duì)實(shí)驗(yàn)結(jié)果的準(zhǔn)確率有較大的影響，滑動(dòng)窗口取值過小或者過大，實(shí)驗(yàn)的效果并不理想.從圖8中可以看出在數(shù)據(jù)量較小的情況下，從機(jī)的數(shù)量對(duì)時(shí)間效率并沒有多大的影響，但隨著實(shí)驗(yàn)數(shù)據(jù)量的增大，從機(jī)數(shù)量越大，那么時(shí)間效率就越好.

5 結(jié) 語

本文利用大數(shù)據(jù)技術(shù)中的spark平臺(tái)在迭代計(jì)算上的優(yōu)勢，結(jié)合TextRank文檔關(guān)鍵詞抽取算法，實(shí)現(xiàn)了大規(guī)模文本關(guān)鍵詞的快速高效提取.利用詞語之間的聯(lián)系構(gòu)造文檔候選關(guān)鍵詞文本圖，利用Spark所提供的GraphX圖計(jì)算框架，計(jì)算出每個(gè)候選關(guān)鍵詞的權(quán)重，選擇一定數(shù)量權(quán)重較大的詞語作為文本的關(guān)鍵詞.實(shí)驗(yàn)表明，數(shù)據(jù)規(guī)模較大時(shí)，本文中的方法能夠大大縮短計(jì)算時(shí)間，選出的關(guān)鍵詞與人工標(biāo)注的結(jié)果非常接近.文本圖的構(gòu)建是本文計(jì)算方法的基礎(chǔ)，在后續(xù)研究中，將采用詞法分析的方法，利用詞語之間的相似度構(gòu)建更加合理的文本圖，對(duì)領(lǐng)域內(nèi)的文本分詞時(shí)，將添加專業(yè)詞典，提高詞語切分精度.