基于MapReduce的術(shù)語(yǔ)權(quán)重計(jì)算方法研究*

王 鍇 ，施水才 ，2，王 濤 ,2，呂學(xué)強(qiáng) ，2

（1.北京信息科技大學(xué)中文信息處理研究中心北京 100101；2.北京拓爾思信息技術(shù)股份有限公司 北京100101）

1 引言

領(lǐng)域術(shù)語(yǔ)[1]是各個(gè)領(lǐng)域的核心詞匯，和領(lǐng)域內(nèi)其他詞或短語(yǔ)相比，其更能代表本領(lǐng)域的特征信息。如何從領(lǐng)域內(nèi)眾多詞匯中識(shí)別出最能代表領(lǐng)域特征信息的領(lǐng)域術(shù)語(yǔ)一直是廣大研究者的研究重點(diǎn)。通常采用傳統(tǒng)信息檢索中的 TF-IDF[2]（term frequency-inverse document frequency）算法，它是一種統(tǒng)計(jì)方法，用以評(píng)估一個(gè)字詞對(duì)于一個(gè)文件集或一個(gè)資料庫(kù)中其中一份文件的重要程度。

由于領(lǐng)域術(shù)語(yǔ)是相對(duì)整個(gè)領(lǐng)域而言，因此需要對(duì)TF-IDF方法進(jìn)行改進(jìn)，使其能夠用于評(píng)估領(lǐng)域內(nèi)的詞或短語(yǔ)對(duì)于整個(gè)領(lǐng)域文獻(xiàn)集的重要程度。在計(jì)算領(lǐng)域術(shù)語(yǔ)權(quán)重時(shí)，通常采用程序和關(guān)系數(shù)據(jù)庫(kù)不斷交互的方式，一步一步實(shí)現(xiàn)術(shù)語(yǔ)權(quán)重的計(jì)算，整個(gè)過(guò)程相對(duì)復(fù)雜。本文在深入研究云計(jì)算[3]的思想后，嘗試在云平臺(tái)中實(shí)現(xiàn)領(lǐng)域術(shù)語(yǔ)權(quán)重的計(jì)算。通過(guò)使用MapReduce[4]編程模型，以分布式方式分步驟計(jì)算術(shù)語(yǔ)權(quán)重。

本文將詳細(xì)展示傳統(tǒng)計(jì)算方法和基于MapReduce的計(jì)算方法的執(zhí)行步驟，通過(guò)對(duì)比兩者的運(yùn)行效率和方法復(fù)雜度，分析X-射線領(lǐng)域術(shù)語(yǔ)權(quán)重計(jì)算的實(shí)驗(yàn)結(jié)果，并最終得出結(jié)論。

2 研究背景

2.1 MapReduce模型

MapReduce是一種編程模型，它與處理/產(chǎn)生海量數(shù)據(jù)集的實(shí)現(xiàn)相關(guān)[5]。該模型主要包含Map函數(shù)和Reduce函數(shù)兩部分。用戶通過(guò)Map函數(shù)處理鍵/值對(duì)，產(chǎn)生一系列的中間鍵/值對(duì)，然后使用Reduce函數(shù)合并所有的具有相同鍵/值的中間鍵/值對(duì)部分?；贛apReduce的程序?qū)⒁苑植际椒绞皆诩褐羞\(yùn)行，通常由4個(gè)步驟[6]執(zhí)行完成。

2.2 Hadoop云計(jì)算平臺(tái)

Hadoop是一個(gè)開(kāi)源云計(jì)算平臺(tái)，提供了一個(gè)穩(wěn)定的共享存儲(chǔ)和分析系統(tǒng)，存儲(chǔ)由HDFS[7]實(shí)現(xiàn)，分析由 Map/Reduce實(shí)現(xiàn)，這兩部分功能是Hadoop的核心。同時(shí)，Hadoop還有一些其他的功能，如分布式鎖服務(wù)ZooKeeper，其開(kāi)發(fā)團(tuán)隊(duì)還開(kāi)發(fā)了許多基于Hadoop的上層框架，方面使用者的開(kāi)發(fā)應(yīng)用。本實(shí)驗(yàn)就在Hadoop云平臺(tái)中實(shí)現(xiàn)。

2.3 改進(jìn)的TF-IDF公式

本文在參考傳統(tǒng)TF-IDF公式[8]的基礎(chǔ)上，進(jìn)一步考慮了以下幾個(gè)特征：要計(jì)算領(lǐng)域術(shù)語(yǔ)在整個(gè)領(lǐng)域文檔集中的權(quán)重；領(lǐng)域術(shù)語(yǔ)是短語(yǔ)，組成該短語(yǔ)的詞條數(shù)目對(duì)權(quán)重具有一定的影響，一般來(lái)說(shuō)，短語(yǔ)越長(zhǎng)越有可能是領(lǐng)域術(shù)語(yǔ)；領(lǐng)域文獻(xiàn)中不同位置術(shù)語(yǔ)的權(quán)重是不同的，例如文獻(xiàn)名稱中的術(shù)語(yǔ)權(quán)重要大于文獻(xiàn)內(nèi)容中的術(shù)語(yǔ)權(quán)重。針對(duì)上述問(wèn)題，本文對(duì)TF-IDF的改進(jìn)如下：

其中，L為組成領(lǐng)域術(shù)語(yǔ)的詞條數(shù)目，N為領(lǐng)域文檔集的總數(shù)，freqij為加權(quán)頻率，F(xiàn)reqTitleij為標(biāo)題中術(shù)語(yǔ)頻率，F(xiàn)reqAbsij為摘要中術(shù)語(yǔ)頻率。

3 設(shè)計(jì)與實(shí)現(xiàn)

3.1 傳統(tǒng)方法

本文首先對(duì)參考文獻(xiàn)[9]中提到的傳統(tǒng)術(shù)語(yǔ)權(quán)重計(jì)算方法進(jìn)行實(shí)驗(yàn)，采用MySQL數(shù)據(jù)庫(kù)存儲(chǔ)中間結(jié)果信息，通過(guò)程序不斷和數(shù)據(jù)庫(kù)交互操作實(shí)現(xiàn)術(shù)語(yǔ)權(quán)重計(jì)算，其具體步驟如下。

·將文本格式領(lǐng)域術(shù)語(yǔ)數(shù)據(jù)導(dǎo)入MySQL數(shù)據(jù)庫(kù)的termsrc表中。

·統(tǒng)計(jì)單個(gè)術(shù)語(yǔ)在所在領(lǐng)域文獻(xiàn)指定位置的出現(xiàn)次數(shù)以及該術(shù)語(yǔ)的中間平均詞條數(shù)目，形成表freqinfo。

·計(jì)算術(shù)語(yǔ)在所在文獻(xiàn)中的加權(quán)頻率和平均詞條組成數(shù)目，形成表weightfreq。

·統(tǒng)計(jì)每篇專(zhuān)利文獻(xiàn)中術(shù)語(yǔ)加權(quán)頻率最大的值，形成表maxweight。

·按照式（2）計(jì)算術(shù)語(yǔ)的TF值，并形成表termtf。

·計(jì)算術(shù)語(yǔ)的IDF值以及平均詞條長(zhǎng)度的權(quán)重，并最終得到候選術(shù)語(yǔ)的領(lǐng)域相關(guān)性權(quán)重。

3.2 基于MapReduce方法

本文進(jìn)行的基于MapReduce的權(quán)重計(jì)算在Hadoop平臺(tái)中實(shí)現(xiàn)，整個(gè)程序由4個(gè)順序執(zhí)行的MapReduce任務(wù)實(shí)現(xiàn)，具體步驟如下。

·統(tǒng)計(jì)術(shù)語(yǔ)在一篇文檔中出現(xiàn)的頻率，該頻率是一個(gè)加權(quán)頻率，同時(shí)計(jì)算組成術(shù)語(yǔ)的平均詞條數(shù)目。

·計(jì)算每篇文檔中術(shù)語(yǔ)的TF值，通過(guò)MapReduce內(nèi)在機(jī)制實(shí)現(xiàn)文檔中組成術(shù)語(yǔ)詞條最大數(shù)目的查找。

·計(jì)算術(shù)語(yǔ)在整個(gè)文檔集中的TF值、IDF值以及術(shù)語(yǔ)詞條長(zhǎng)度對(duì)術(shù)語(yǔ)權(quán)重的影響，并最終得到候選術(shù)語(yǔ)的領(lǐng)域相關(guān)性權(quán)重。

·根據(jù)計(jì)算得到的領(lǐng)域相關(guān)性權(quán)重，將候選領(lǐng)域術(shù)語(yǔ)按權(quán)值降序排列。

每一步都對(duì)應(yīng)一個(gè)MapReduce任務(wù)，每個(gè)任務(wù)完成相應(yīng)的功能，上一個(gè)任務(wù)的輸出作為下一個(gè)任務(wù)的輸入。

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

本實(shí)驗(yàn)的輸入數(shù)據(jù)是從X射線技術(shù)專(zhuān)利信息中提取出的文本格式信息，具體形式如圖1所示。

圖1中，第1列為專(zhuān)利號(hào)，第2列為術(shù)語(yǔ)名稱，第3列為術(shù)語(yǔ)出現(xiàn)位置標(biāo)識(shí)，第4列為組成術(shù)語(yǔ)詞條的長(zhǎng)度。標(biāo)識(shí)1表示術(shù)語(yǔ)出現(xiàn)在標(biāo)題中，標(biāo)識(shí)0表示術(shù)語(yǔ)出現(xiàn)在摘要中。

通過(guò)兩種方法計(jì)算得到的候選領(lǐng)域術(shù)語(yǔ)權(quán)重計(jì)算結(jié)果如圖2和圖3所示，結(jié)果以權(quán)值降序排列。

從計(jì)算結(jié)果可以看出，領(lǐng)域術(shù)語(yǔ)權(quán)重的排列順序是相同的，不過(guò)具體數(shù)值有細(xì)微差別，這是由兩種方法在計(jì)算精度和存儲(chǔ)精度上的差別造成的。分別對(duì)基于這兩種方法的程序進(jìn)行計(jì)時(shí)，得到它們的執(zhí)行時(shí)間對(duì)比結(jié)果，見(jiàn)表1。

基于MapReduce方法的程序在一個(gè)由4個(gè)節(jié)點(diǎn)組成的集群中運(yùn)行，包括一個(gè)名稱節(jié)點(diǎn)和3個(gè)數(shù)據(jù)節(jié)點(diǎn)。從表1可以看出，MapReduce方法的執(zhí)行時(shí)間大于傳統(tǒng)方法的執(zhí)行時(shí)間，這是因?yàn)镸apReduce是一個(gè)用于處理海量數(shù)據(jù)的編程模型，而本次實(shí)驗(yàn)的輸入數(shù)據(jù)非常小，即數(shù)據(jù)處理所花時(shí)間在程序執(zhí)行總時(shí)間中所占的比例很小。輸入數(shù)據(jù)的分片和處理完后數(shù)據(jù)的合并、節(jié)點(diǎn)之間數(shù)據(jù)的讀取、名稱節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)之間控制信息的交互等消耗了大量的時(shí)間。

表1 傳統(tǒng)方法和基于MapReduce方法的時(shí)間對(duì)比

表2 Hadoop 3種模式下的運(yùn)行結(jié)果

為了驗(yàn)證上述論斷，本文在Hadoop的3種運(yùn)行模式（本地模式、偽分布模式和集群模式）下分別進(jìn)行實(shí)驗(yàn)，并記錄程序運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

從表2可以看出，當(dāng)基于MapRedcue的權(quán)重計(jì)算方法以本地模式運(yùn)行時(shí)，由于本地模式不需要節(jié)點(diǎn)之間數(shù)據(jù)讀取等非數(shù)據(jù)處理的時(shí)間消耗，其運(yùn)行時(shí)間大大減少，僅需9 s，大大低于傳統(tǒng)方法的79.595 s，這表明MapReduce編程模型的數(shù)據(jù)處理效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的方法。而程序運(yùn)行在偽分布模式下時(shí)消耗105 s，遠(yuǎn)大于同樣只有一個(gè)運(yùn)行節(jié)點(diǎn)的本地模式，這是由于偽分布模式以集群的方式模擬運(yùn)行，在由一個(gè)節(jié)點(diǎn)組成的集群中交互數(shù)據(jù)，這將消耗大量的時(shí)間。因此，當(dāng)處理的數(shù)據(jù)變成海量數(shù)據(jù)，使數(shù)據(jù)處理時(shí)間遠(yuǎn)大于非數(shù)據(jù)處理時(shí)間時(shí)，集群模式將更加體現(xiàn)MapReduce分布式模型的優(yōu)勢(shì)。

從方法的設(shè)計(jì)角度看，基于MapReduce模型的術(shù)語(yǔ)權(quán)重計(jì)算方法較傳統(tǒng)方法也簡(jiǎn)便許多，實(shí)現(xiàn)步驟由傳統(tǒng)方法的6步縮減為4步，同時(shí)也減少了數(shù)據(jù)的冗余操作。因?yàn)镸apReduce編程模型在進(jìn)行數(shù)據(jù)分析和處理時(shí)都是采用鍵值對(duì)的形式，這種設(shè)計(jì)本身可以簡(jiǎn)化許多操作步驟，而且也提高了數(shù)據(jù)處理的效率。同時(shí)，通過(guò)定制Partitioner、OutputKeyComparactor等類(lèi)，可以方便快速地實(shí)現(xiàn)用戶需要的數(shù)據(jù)處理功能。

5 結(jié)束語(yǔ)

本文在研究傳統(tǒng)術(shù)語(yǔ)權(quán)重計(jì)算方法的基礎(chǔ)上，結(jié)合云計(jì)算思想，嘗試以MapReduce方法計(jì)算領(lǐng)域術(shù)語(yǔ)的權(quán)重，同時(shí)改進(jìn)傳統(tǒng)TF-IDF公式，使其更好地適應(yīng)領(lǐng)域術(shù)語(yǔ)權(quán)重的計(jì)算。實(shí)驗(yàn)結(jié)果表明，基于MapReduce的術(shù)語(yǔ)權(quán)重計(jì)算方法不僅在方法設(shè)計(jì)上簡(jiǎn)化了操作步驟，同時(shí)在算法的執(zhí)行效率上也大大提高。但由于需要處理的數(shù)據(jù)較少，集群模式下運(yùn)行MapReduce程序時(shí)，節(jié)點(diǎn)間數(shù)據(jù)交互消耗的時(shí)間遠(yuǎn)大于數(shù)據(jù)處理本身的時(shí)間，以至不能很好地體現(xiàn)分布式計(jì)算的優(yōu)勢(shì)。下一步工作將加大輸入處理數(shù)據(jù)，同時(shí)適當(dāng)增加集群節(jié)點(diǎn)的數(shù)目，更加明顯地展示MapReduce模型的優(yōu)勢(shì)。

1 王強(qiáng)軍，李蕓，張普.信息技術(shù)領(lǐng)域術(shù)語(yǔ)提取的初步研究.自然語(yǔ)言處理，2002(1):32～33

2 Ricardo Baeza-Yates,Berthier Riberio-Neto.Mordern Information Retrieval.北京:機(jī)械工業(yè)出版社，2005

3 Christina Hoffa,Gaurang Mehta,Timothy Freeman.On the use of cloud computing for scientific workflows.http://wenku.baidu.com/view eea16c2a3169a4517623a305.html,2008.

4 JeffreyDean,SanjayGhemawat.MapReduce:simplified data processing on large clusters.In:OSDI,2004

5 孫廣中，肖鋒，熊曦.MapReduce模型的調(diào)度及容錯(cuò)機(jī)制研究.微電子學(xué)與計(jì)算機(jī)，2007,24(7)

6 吳曉偉.MapReduce并行編程模式的應(yīng)用與研究.中國(guó)大學(xué)技術(shù)大學(xué)碩士學(xué)位論文，2009

7 許春玲，張廣泉.分布式文件系統(tǒng)Hadoop HDFS和傳統(tǒng)文件系統(tǒng)Linux Fs的比較與分析.蘇州大學(xué)學(xué)報(bào),2010,30(4)

8 高志翔.一種基于TF-IDF算法的本體關(guān)聯(lián)度算法.中國(guó)科技論文在線，2010(6)

9 張蓓蓓.基于關(guān)聯(lián)分析和聚類(lèi)的領(lǐng)域本體構(gòu)建方法及其應(yīng)用研究.南京理工大學(xué)碩士學(xué)位論文，2009