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

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

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

1 引言

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

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

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

2 研究背景

2.1 MapReduce模型

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

2.2 Hadoop云計算平臺

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

2.3 改進的TF-IDF公式

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

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

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

3.1 傳統(tǒng)方法

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

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

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

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

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

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

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

3.2 基于MapReduce方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

2 Ricardo Baeza-Yates,Berthier Riberio-Neto.Mordern Information Retrieval.北京:機械工業(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)度及容錯機制研究.微電子學(xué)與計算機，2007,24(7)

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

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

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

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