基于關鍵詞的云計算語義文本自適應分類

沈佳杰，江 紅，王 肅

(華東師范大學信息科學技術學院，上海 200241)

1 概述

隨著互聯(lián)網(wǎng)和云計算技術的發(fā)展，越來越多的應用被部署到了云端。如何在保證分類準確度的情況下，提高文本在云計算環(huán)境下的分類效率以及減少對于整體網(wǎng)絡帶寬的開銷，從而高效地在云計算環(huán)境下對文本進行分類成為一個亟需解決的問題。

本文提出一個云計算環(huán)境下的基于語義的中文文本關鍵詞自適應分類算法，通過對于文本關鍵詞傳輸而不是文本本身的傳輸，減少云計算環(huán)境下對于分類通信的代價。

2 文本處理技術及云計算簡介

2.1 集中式情況下常見的關鍵詞提取技術

對于集中式文本關鍵詞提取算法大致可分成以下2步：

步驟1對于文本進行預處理，如分詞，并對詞語進行詞性標注。

步驟2使用一定的規(guī)則對文本中的信息進行關鍵詞的提取。

對于步驟1分詞已經(jīng)有了很多不同的算法[1-2]，而對于步驟2，現(xiàn)在比較主流的關鍵詞提取算法有基于統(tǒng)計特征的關鍵詞提取算法、基于語義的關鍵詞提取算法[3-4]以及基于詞語網(wǎng)絡的關鍵詞提取算法[5-6]，并且相關的語義提取技術也已經(jīng)應用到了很多的領域，如語義的相似性[7]、語義與頻率的關系[8]，以及對于網(wǎng)頁關鍵詞的抽取。

本文介紹基于語義的任務調(diào)度算法?；谖谋菊Z義的關鍵詞提取算法相較于一般的關鍵詞提取算法，其最大的區(qū)別在于這種算法不僅關心詞語在文本中的位置和數(shù)量信息，還需要結合語言本身的特點，如詞語的詞性和語法的信息。對于基于其他方法的關鍵詞提取算法還可以參考文獻[9]。圖1展示了一種基于語義的關鍵詞提取算法[4]。

圖1 基于語義的關鍵詞提取算法

2.2 集中式情況下中文文本分類算法

針對文本分類的算法，在集中式條件下已進行了很多相關方面的研究，如機器學習[10]、統(tǒng)計方法[11]、語義的方法、關鍵詞[12]和推理網(wǎng)絡[13]。但是如何在分布式的環(huán)境下，構建相應的文本分類算法依然是一個值得研究的問題。

2.3 云計算

云計算是現(xiàn)在研究的熱點問題，對于如何在云計算環(huán)境下進行程序的開發(fā)和部署以及云計算的定義已經(jīng)有很多的文獻對這個問題進行討論，如對于云計算進行綜述[14-15]，對云計算關鍵技術進行總結[16-17]。如何在云計算的情況下對已知的算法進行改造依然是一個值得研究的問題。

3 云計算文本分類算法

3.1 算法假設以及定義

本文中算法的假設以及定義如下：

假設1計算傳輸?shù)拇鷥r與傳輸?shù)奈谋咀謹?shù)成正比，本地的計算代價較網(wǎng)絡傳輸代價忽略不計。

假設1說明了云計算網(wǎng)絡的開銷代價與傳輸內(nèi)容的數(shù)量有關，而文本應用中主要的傳輸內(nèi)容為文字，所以需要盡量減少傳輸?shù)奈淖謹?shù)。

假設2文本提取的關鍵詞字數(shù)小于文本本身的字數(shù)。

假設3隨著正確關鍵詞數(shù)量的增多，文本的語義描述越明確，但是正確關鍵詞與傳輸關鍵詞字數(shù)的比值將變小，當全文傳輸時其比值接近于0。

對假設2和假設3，為了保證在每一個代理的關鍵詞提取算法可以優(yōu)先找出比較的重要關鍵詞，并且對應的文本分類算法可以根據(jù)正確關鍵詞進行有效的分類，而關鍵詞僅僅只是文本中的一部分，所以關鍵詞的字數(shù)將小于文本本身的字數(shù)。

假設4閱讀文本的人足夠聰明，可以有效地分辨文本關鍵詞和文本的類別。

定義1人工判斷和自動判斷均判斷為關鍵詞的數(shù)與傳輸字數(shù)的比值，稱為單位傳輸準確數(shù)，記為：

其中，A為人工及機器都判斷為關鍵詞的數(shù)量；n為傳輸?shù)奈淖謧€數(shù)。

定義2文本整體分類算法傳輸所需的字數(shù)與關鍵詞分類算法所需傳輸?shù)淖謹?shù)差值，叫做關鍵詞整體差，記為：

其中，Talli代表全文分類算法需要傳輸?shù)淖謹?shù)；Tkeywordi代表關鍵詞提取分類算法需要傳輸?shù)淖謹?shù)。

定義3人工提取和自動提取均判斷為關鍵詞的數(shù)量與人工提取和自動提取均判斷為關鍵詞的數(shù)量、人工提取為非關鍵詞而自動提取為關鍵詞的數(shù)量之和的比值，稱為知識點的查準率[4]，記為：

其中，B表示人工判斷不是關鍵詞而機器判斷是關鍵詞的數(shù)量。

定義4人工提取和自動提取均判斷為關鍵詞的數(shù)量與人工提取和自動提取均判斷為關鍵詞的數(shù)量、人工提取為關鍵詞而自動提取為非關鍵詞的數(shù)量之和的比值，稱為召回率[4]，記為：

其中，C表示人工判斷是關鍵詞而機器判斷不是關鍵詞的數(shù)量。

定義5查準率與召回率的乘積的2倍與2個和的比值稱為查準率P和召回率R的調(diào)和[4]，記為：

其中，P為查準率；R為召回率。

定義6節(jié)點查準率P和召回率R的調(diào)和與該節(jié)點傳輸文字數(shù)之間的比值稱為單位查準率P和召回率R的調(diào)和，記為：

其中，n為傳輸?shù)淖址麛?shù)。

定義7本文中提出的算法，根據(jù)詞性的不同確定詞語的重要性，對于詞性重要性定義的權值如下：當wi為名詞時， posi=0.8；當wi為簡略語時， posi=0.9；當wi為處所詞時， posi=0.7；當wi為動詞時， posi=0.2；當wi為形容詞時，posi=0.2；當wi為副詞時，posi=0.2；當wi為介詞時，posi=0.2；當wi為狀態(tài)詞時，posi=0.2；當wi為連詞時，posi=0.1；當wi為方位詞時，posi=0.1；當wi為時間詞時，posi=0.1；其他情況時，posi=0.01。其中，wi為第i個詞的詞性；posi為第i個詞的權值。

3.2 算法步驟描述

本文中的算法主要涉及4個主要的步驟，包括對于本地代理文本關鍵詞提取、中心端進行關鍵詞信息匯總、和中心端輸出全局分類結果。本文中的云計算環(huán)境下的語義提取算法步驟如下：

步驟1使用本地關鍵詞提取算法對本地代理文本進行關鍵詞提取。

步驟1.1輸入每一篇文本需要提取的關鍵詞數(shù)。

步驟1.2使用本地關鍵詞提取算法對每一篇文檔提取關鍵詞及其相應的屬性，如關鍵詞以及相應的數(shù)量等。

步驟1.3將關鍵詞及相應信息上傳到中心端進行統(tǒng)計。

步驟2中心端對進行代理關鍵詞的數(shù)據(jù)進行匯總。

步驟2.1中心數(shù)據(jù)端匯總不同的代理關鍵詞信息，調(diào)用信用分配算法對每一個關鍵詞分配一個信用值。

步驟2.2根據(jù)代理上傳關鍵詞及其生成信用值，生成目標類別以及關鍵詞列表。

步驟2.3將目標類別及關鍵詞列表傳輸?shù)矫恳粋€代理。

步驟3根據(jù)中心傳來的關鍵詞及類別信息進行文本分類。

步驟3.1接受來自中心數(shù)據(jù)庫的關鍵詞列表及目標類別。

步驟3.2根據(jù)中心數(shù)據(jù)庫的關鍵詞列表以及目標類別，比對本地文本關鍵詞進行性分類。

步驟3.3將分類結果上傳中心數(shù)據(jù)庫。

步驟4根據(jù)各個代理分類信息，中心端輸出全局分類結果。

3.3 算法性質(zhì)證明

定理1基于關鍵詞的分類算法的傳輸效率嚴格優(yōu)于傳統(tǒng)的基于文本分類的方法。

在軍工局資助下，北極星近幾年一直在穩(wěn)步推進新型鉬-99生產(chǎn)技術的研發(fā)工作。這種技術以鉬的穩(wěn)定同位素為原料，而不是以傳統(tǒng)技術使用的濃縮鈾為原料，因此可以消除與濃縮鈾相關的擴散和環(huán)境風險。

證明：

由于假設2，提取出的關鍵詞長度要嚴格小于文本傳輸?shù)淖謹?shù)，又因為假設1，隨著字數(shù)的增加傳輸代價也將增加，所以對于字數(shù)比較少的關鍵詞分類方法其傳輸效率較高。

定理2當關鍵詞提取的數(shù)量大于某一個常數(shù)時，隨著關鍵詞提取數(shù)量的增加，查準率P和召回率R的調(diào)和將單調(diào)上升。

證明：

將式(3)、式(4)代入式(5)，得：

隨著關鍵詞提取數(shù)量的增加，又根據(jù)假設3、假設4，在關鍵詞提取的過程中A,B,C將變大，而S是一個常量，又因為：

將式(9)代入式(7)，得：

又因為A單調(diào)遞增，所以原式單調(diào)上升。

證明：

將式(10)代入式(6)，得：

從定理2和推論中可以看到，只要關鍵詞提取算法足夠好(即滿足假設3)，通過關鍵詞提取的技術可有效地對各個代理中文本的關鍵詞，即準確度較高的關鍵詞先提取出來，就可以在傳輸?shù)倪^程中只傳輸前面有用的信息以代替對于文本全文的傳輸，從而達到通過傳輸少量關鍵詞對文本進行分類的目的。

定理3隨著每一個代理關鍵詞提取數(shù)量的增加，中心數(shù)據(jù)庫本文分類的準確率將上升，但是每增加一個關鍵詞，中心數(shù)據(jù)庫分類準確率的增加量將減少。

證明：

整個正確關鍵詞的數(shù)學期望，滿足以下公式：

其中，Ek為提取關鍵詞數(shù)為k時正確關鍵詞的期望；pk為第k個關鍵詞是正確關鍵詞的概率。

當提取關鍵詞k時，正確關鍵詞的數(shù)學期望為：

由于在假設2中，隨著正確關鍵詞數(shù)量的增加，文本語義的描述越明確，又因為隨著關鍵詞提取數(shù)量的增加正確的關鍵詞數(shù)也會增加，所以當每一個節(jié)點提取以及傳輸?shù)街行臄?shù)據(jù)庫的關鍵詞數(shù)增加時，對每一篇文本的內(nèi)容理解將會更加明確，從而提高在中心數(shù)據(jù)庫中的文本分類效果。

又因為正確關鍵詞與傳輸關鍵詞字數(shù)的比值將變小，當全文傳輸時其比值接近于0，所以每增加一個關鍵詞，產(chǎn)生正確關鍵詞的可能性變小，中心數(shù)據(jù)庫分類準確率的增加量也將減少。

由定理3可知，雖然隨著各個代理關鍵詞增加，中心數(shù)據(jù)庫文本的分類準確率將增加，但是每增加一個關鍵詞，中心數(shù)據(jù)庫分類準確率的增加量將減少。這樣當整個云計算系統(tǒng)網(wǎng)絡性能較差時，則可以通過減少各個代理對文本提取的關鍵詞數(shù)量，從而減少網(wǎng)絡中傳輸?shù)臄?shù)據(jù)量，最大程度保證分類的效率。而網(wǎng)絡條件較好時，通過對提取的關鍵詞進行調(diào)整，改變網(wǎng)絡中數(shù)據(jù)的傳輸量以及中心數(shù)據(jù)庫文本的分類準確率，實現(xiàn)算法自適應當前云計算系統(tǒng)網(wǎng)絡狀態(tài)的目的。

4 實驗分析

4.1 實驗環(huán)境和數(shù)據(jù)組成

本實驗環(huán)境是Matlab2010b，實驗的主要目的是為了證明本文算法的準確性。首先實驗中比較了基于語義關鍵分類算法與基于統(tǒng)計的關鍵詞分類算法對不同代理以及中心數(shù)據(jù)庫關鍵詞提取能力(主要比較查準率、召回率以及查準率P和召回率R的調(diào)和)。其次本文中的實驗比較改進分類算法與集中式基于統(tǒng)計和語義分類算法的分類準確率。最后通過對比提取關鍵詞個數(shù)與關鍵詞整體差的關系，說明改進的分類算法可以有效地提高云計算分布式網(wǎng)絡環(huán)境下網(wǎng)絡的傳輸效率。本實驗數(shù)據(jù)主要由人民日報1998年語料庫中隨機抽出120篇文章進行統(tǒng)計，整個數(shù)據(jù)集將隨機劃分成2個集合來模擬2個代理集合，每一個代理分別有60篇文章，與此同時，將原先的120篇文章作為集中式實驗的素材。其中對于各種不同詞語詞性權值的定義，如定義7所示。

4.2 實驗結果

為了比較不同的關鍵詞提取方法在云計算分布式情況下的影響，分別使用基于語義的關鍵詞提取和基于統(tǒng)計的關鍵詞提取，對2個代理進行關鍵詞提取，并在中心數(shù)據(jù)庫匯總并以此為依據(jù)進行文本分類。

表1展示了2個代理對關鍵詞提取的查準率、召回率以及查準率和召回率的調(diào)和。如表1所示，對于2個代理基于語義的關鍵詞提取方法和基于統(tǒng)計的關鍵詞提取算法，基本符合本文的假設3，隨著關鍵詞個數(shù)的增加，其查準率、召回率以及兩者的調(diào)和單調(diào)遞增，而且基于語義的關鍵詞提取算法明顯優(yōu)于基于統(tǒng)計的文本提取算法，所以在代理關鍵詞提取算法選擇中，選擇基于語義的關鍵詞提取算法性能優(yōu)于基于統(tǒng)計的關鍵詞提取算法，且隨著關鍵詞個數(shù)的增加，查準率P和召回率R的調(diào)和也將單調(diào)上升，這與定理2中的結論一致。表2展示了中心數(shù)據(jù)庫合成關鍵詞的查準率、召回率以及查準率和召回率的調(diào)和。

表1 各個代理關鍵詞的提取結果

表2 各個中心數(shù)據(jù)庫的關鍵詞合成結果

圖2展示了在2個代理中隨機選取5篇文章，其關鍵詞的權值分布情況?？梢钥吹讲煌恼碌年P鍵詞分布是不同的，如圖2(a)中第1篇、第2篇和圖2(b)中第1篇、第2篇的關鍵詞權值分布差別比較明顯，說明只需要提取部分關鍵詞便可以將文本描述清楚，而圖1(a)中的第4篇和第5篇和圖2(b)中的第3篇和第5篇權值的差別不大，所以對于這一類的文本則需要提取更多的關鍵詞，以求達到更加好的文本分類效果。

圖2 2個代理中5篇文章關鍵詞權值比較

圖3主要展示了關鍵詞提取算法代理和中心數(shù)據(jù)庫中單位查準率P和召回率R的調(diào)和與提取關鍵詞個數(shù)之間的關系。如圖3(a)主要展示了2個代理的單位查準率P和召回率R的調(diào)和，隨著提取關鍵詞個數(shù)的增加，每一個代理單位查準率與召回率的調(diào)和減少。圖3(b)主要展示了中心數(shù)據(jù)庫的單位查準率P和召回率R的調(diào)和，隨著提取關鍵詞個數(shù)的增加，中心數(shù)據(jù)庫端單位查準率與召回率的調(diào)和也減少，這與推論的結果一致。對比圖3(a)和圖3(b)可知，2個代理的單位查準率P和召回率R的調(diào)和是中心數(shù)據(jù)庫的2倍，其主要原因是中心數(shù)據(jù)庫的通信量是每一個代理的2倍，而中心數(shù)據(jù)庫中關鍵詞的質(zhì)量則與每一個代理的質(zhì)量大體相當。

圖3 查準率P和召回率R的調(diào)和

圖4主要展示基于關鍵詞的中文文本分類算法的準確率與集中式條件下基于語義的中文文本分類算法和統(tǒng)計算法的中文文本分類算法的準確率比較。如圖4(a)所示，隨著關鍵詞提取數(shù)的增加，每一個代理對于文本的分類準確率提高，接近于基于語義分類方法的準確率，并在提取關鍵詞大于一定數(shù)量后，其準確率升值超過了集中式的基于統(tǒng)計的文本分類方法。如圖4(b)所示，隨著關鍵詞提取數(shù)量的增加，中心數(shù)據(jù)庫的分類準確率上升，但是每多提取一個關鍵詞，其準確率的上升量卻在減少，這與定理3的結論一致。圖4說明了無論在代理端，還是在中心數(shù)據(jù)庫端，在每一個代理提取的關鍵詞數(shù)量達到一定數(shù)量之后，可以近似代替集中式的語義提取文本分類方法。

圖4 算法準確率比較

圖5展示了每一個代理和中心數(shù)據(jù)庫提取關鍵詞數(shù)與關鍵詞整體差之間的關系。如圖5(a)所示，隨著關鍵詞提取數(shù)量的增加，每一個代理提取的關鍵詞個數(shù)增加，每一個代理的關鍵詞整體差隨之下降。如圖5(b)所示，隨著關鍵詞提取數(shù)量的增加，中心數(shù)據(jù)庫的關鍵詞整體差也隨之下降，這與定理1的結論一致。綜合圖5(a)、圖5(b)雖然代理和中心數(shù)據(jù)庫的關鍵詞整體差，即使提取的關鍵詞數(shù)達到了20個，其中心數(shù)據(jù)庫關鍵詞整體差依然高達1.75×105，說明改進的關鍵詞提取分類算法可以有效地減少網(wǎng)絡的傳輸量，從而在保證分類效果的前提下，減少云計算對網(wǎng)絡傳輸?shù)拈_銷。

圖5 關鍵詞提取數(shù)與關鍵詞整體差之間的關系

5 結束語

本文展示了一個云計算環(huán)境下基于語義關鍵詞提取的分布式中文文本分類方法。通過理論推導和實驗，證明了相對于傳統(tǒng)的集中式文本分類方法，本文方法可以在近似保證分類效果的前提下，有效地減少云計算網(wǎng)絡的傳輸開銷。但是本文方法并沒有具體說明在提取關鍵詞數(shù)量和文本分類準確率的定量關系，僅對中文文本做了實驗，該方法是否對其他語言依然有效尚無定論，下一步工作將對這些方面進行研究。

[1]何國斌,趙晶璐.漢語文本自動分詞算法的研究[J].計算機工程與應用,2010,46(3):125-130.

[2]吳晶晶,荊繼武,聶曉峰,等.一種快速中文分詞詞典機制[J].中國科學院研究生院學報,2009,26(5):704-710.

[3]傅 鸝,涂春梅,付春雷,等.基于語義的成語檢索系統(tǒng)研究[J].計算機工程與應用,2011,47(13):147-149.

[4]王立霞,淮曉永.基于語義的中文文本關鍵詞提取算法[J].計算機工程,2012,38(1):1-3.

[5]Turney P D.Thumbs Up or Thumbs Down Semantic Orientation Applied to Unsupervised Classification of Reviews[C]//Proc.of the 40th Annual Meeting on Association for Computational Linguistics.[S.l.]:ACM Press,2002:417-424.

[6]Turney P D.Learning Algorithms for Keyphrase Extraction[J].Information Retrieval,2000,2(4):303-336.

[7]Turney P D.Similarity of Semantic Relations[J].Computational Linguistic,2006,32(3):279-416.

[8]Turney P D,Pantel P.From Frequency to Meaning:Vector Space Models of Semantics[J].Journal of Artificial Intelligence Research,2010,37(1):141-188.

[9]鄭家恒,盧嬌麗.關鍵詞抽取方法的研究[J].計算機工程,2005,31(18):194-195.

[10]蘇金樹,張博鋒,徐 昕.基于機器學習的文本分類技術研究進展[J].軟件學報,2006,17(9):1848-1859.

[11]姜 遠,周志華.基于詞頻分類器集成的文本分類方法[J].計算機研究與發(fā)展,2006,43(10):1681-1687.

[12]羅 杰,陳 力,夏德麟,等.基于新的關鍵詞提取方法的快速文本分類系統(tǒng)[J].計算機應用研究,2006,23(4):32-34.

[13]李曉黎,劉繼敏,史忠植.概念推理網(wǎng)及其在文本分類中的應用[J].計算機研究與發(fā)展,2000,37(9):1032-1038.

[14]Armbrust M,Fox A,Griffith R,et al.A View of Cloud Computing[J].Communications of the ACM,2010,53(4):50-58.

[15]Buyya R,Yeo C S,Venugopal S.Market-oriented Cloud Computing:Vision,Hype,and Reality for Delivering IT Services as Computing Utilities[C]//Proc.of the 10th IEEE International Conference on High Performance Computing and Communications.[S.l.]:IEEE Press,2008:5-13.

[16]陳 康,鄭緯民.云計算:系統(tǒng)實例與研究現(xiàn)狀[J].軟件學報,2009,20(5):1337-1348.

[17]陳 全,鄧倩妮.云計算以及其關鍵性技術[J].計算機應用,2009,29(9):2562-2567.