改進(jìn)型TF-IDF算法在軟件開(kāi)發(fā)過(guò)程控制中的應(yīng)用

張 鯤

(閩江學(xué)院軟件學(xué)院，福州 350011)

軟件企業(yè)隨著業(yè)務(wù)的積累與規(guī)模的增加，其所積累的領(lǐng)域知識(shí)與管理知識(shí)也變得愈加豐富。這些知識(shí)對(duì)于企業(yè)的發(fā)展有重要的意義，但由于內(nèi)容龐大，難以轉(zhuǎn)化為對(duì)當(dāng)前工作的支持。為了解決這一問(wèn)題，需要對(duì)文檔的相似程度即對(duì)文本進(jìn)行分類。

1 文本分類相關(guān)技術(shù)

文本分類是自然語(yǔ)言處理中的一大研究重點(diǎn)。在這一領(lǐng)域有許多的研究方法被應(yīng)用于文本的分類。參考文獻(xiàn)［1］中使用了向量空間模型，將文本內(nèi)容轉(zhuǎn)化為易于數(shù)學(xué)處理的向量形式。參考文獻(xiàn)［2］提出將各種特征加權(quán)算法與樸素貝葉斯分類器相結(jié)合，對(duì)不同的特征根據(jù)其分類重要性賦予不同的權(quán)值，使樸素貝葉斯擴(kuò)展為加權(quán)樸素貝葉斯，以提高分類器的性能。也有研究借助外部詞典分析詞項(xiàng)之間的語(yǔ)義相似度，使用詞項(xiàng)相似度加權(quán)樹(shù)及文本語(yǔ)義相似度來(lái)計(jì)算兩篇文本之間的相似度［3］。

TF-IDF算法是文本分類中一個(gè)重要的方法，該方法相關(guān)概念定義如下。

TF:TF為詞頻，反映某個(gè)詞(特征)在文本中出現(xiàn)的次數(shù)。由于一些高特征詞出現(xiàn)的頻率與反映文本特征的某些詞在詞頻上相差較大。因此取對(duì)數(shù)減少少數(shù)高特征詞對(duì)特征權(quán)重的影響。即:

IDF:即逆向文檔頻度，指的是某一特征區(qū)別于其他文檔的程度。根據(jù)統(tǒng)計(jì)結(jié)果，如果一個(gè)詞在文檔中大量出現(xiàn)，則該詞并不能反映文檔的特征。相反，若一個(gè)詞在其他位置不怎么出現(xiàn)，而在某文檔中雖然出現(xiàn)，但頻率不高，反而有較大的可能是反映文檔內(nèi)容的重要詞匯。因此IDF可表示為:

式中:n— 所有的訓(xùn)練樣本數(shù);ni— 出現(xiàn)特征詞ti的訓(xùn)練樣本數(shù)。

在獲得TF與IDF后，TF-IDF算法描述如下:

為了避免詞頻受長(zhǎng)文本的影響，通常需要對(duì)其做歸一化處理:

TF-IDF算法在文本分類領(lǐng)域應(yīng)用較多，但也有其缺點(diǎn)。例如其無(wú)法真實(shí)反映某個(gè)特征的重要程度。在一些研究中，則采用信息熵增益、文本權(quán)重等方法對(duì)其進(jìn)行了改進(jìn)［4］。

2 文檔搜索策略

軟件企業(yè)中的相關(guān)文檔有如下規(guī)律:

(1)長(zhǎng)文本。開(kāi)發(fā)性的文檔一般都比較長(zhǎng)，但內(nèi)容相對(duì)簡(jiǎn)單，存在大量重復(fù)的描述語(yǔ)句。關(guān)鍵詞出現(xiàn)的頻率高。

(2)有限分類。與普通文本的多元分類不同的是在軟件企業(yè)中，相關(guān)文檔的類別相對(duì)清晰。開(kāi)發(fā)類、管理類與市場(chǎng)類的文檔可進(jìn)一步分類，但類別較少。

對(duì)此，在相關(guān)規(guī)律的基礎(chǔ)上可設(shè)計(jì)本研究的推理策略。

2.1 詞典構(gòu)建

詞典構(gòu)建是分詞的前提。本研究中使用基于整詞二分的分詞詞典機(jī)制(見(jiàn)圖1)。

圖1 整詞二分的分詞詞典機(jī)制

整詞二分法只能對(duì)一個(gè)字符串S是否是一個(gè)詞進(jìn)行判斷，無(wú)法在掃描字符串的過(guò)程中判斷S的一部分是否是可能的詞。因此在查詢過(guò)程中需要進(jìn)行多次的試探。這種做法效率不高，但由于其原理簡(jiǎn)單，不需要復(fù)雜的構(gòu)造過(guò)程與維護(hù)過(guò)程。

2.2 自動(dòng)分詞

為了將最大的復(fù)合詞從語(yǔ)句中分離，本系統(tǒng)使用正向匹配算法(MM)來(lái)實(shí)現(xiàn)這一目標(biāo)。正向匹配算法的思想是:設(shè)置k為一個(gè)滑動(dòng)窗口，從文本中取出k個(gè)字符長(zhǎng)度的字符串后將這字符串與詞典進(jìn)行比對(duì)。如果匹配不成功，則從k個(gè)字符中去除最后一個(gè)字符進(jìn)行比對(duì)。如此反復(fù)，直到匹配切分出一個(gè)詞或字符串長(zhǎng)度為0為止。接著取k個(gè)長(zhǎng)度的字符串進(jìn)行分析，重復(fù)上述步驟直到文檔被掃描完為止。正向最大匹配法流程見(jiàn)圖2。

2.3 關(guān)鍵詞提取

關(guān)鍵詞的提取使用TF-IDF算法進(jìn)行。此時(shí)需要計(jì)算TF值與IDF。即TF-IDF=(詞頻)TF×(逆向文檔頻度)IDF。由于TF-IDF與文檔中出現(xiàn)的某個(gè)詞成正比，文檔中所有的詞數(shù)成反比，所以計(jì)算出文檔中每個(gè)TF-IDF值后按降序方式排列，并取出前N個(gè)詞，這N個(gè)詞則為自動(dòng)提取的關(guān)鍵詞。

由于TF-IDF算法存在一些不足，需進(jìn)行較多的改進(jìn)。此處根據(jù)應(yīng)用目標(biāo)的特征，對(duì)TF-IDF進(jìn)行適當(dāng)?shù)母倪M(jìn)。由于文檔的類別較少，因此可在詞庫(kù)中設(shè)置每個(gè)詞的權(quán)重。則:

式中:ωi—特征i的權(quán)重。其值的計(jì)算在分詞并統(tǒng)計(jì)詞頻后開(kāi)始計(jì)算。在計(jì)算時(shí)需要進(jìn)行同義詞的合并。將得到的特征按詞頻降序排列后得如下序列:

A、B、C、D、E、F

若E與B是同義詞，則將E的權(quán)重經(jīng)一定的折算后加入B的權(quán)重。B的權(quán)重計(jì)算過(guò)程如下:

ωi=特征i的權(quán)重的權(quán)重*0.5)

j是在特征序列中B之后出現(xiàn)的B的同義詞。

上述過(guò)程用偽代碼描述如下:

Step 1:對(duì)文章進(jìn)行分詞，按TF-IDF統(tǒng)計(jì)并降序排列后得序列S。

Step 2:按順序從S中取出一個(gè)特征T，并取其權(quán)重ω=0。

從詞典中取得其權(quán)重ωi賦值給ω，查找T后的T的同義詞T1，取其權(quán)重ωi*0.5加入ω。

刪除T1，并查找后面的同義詞，重復(fù)權(quán)重的加成，直到序列掃描完畢。

Step 3:對(duì)使用權(quán)重后的結(jié)果按降序重新排列，取前N個(gè)特征，達(dá)到關(guān)鍵詞自動(dòng)提取的目的。

在得到文章的自動(dòng)關(guān)鍵字后，將該信息存儲(chǔ)于文檔的關(guān)聯(lián)區(qū)域，后續(xù)進(jìn)行文本相似度檢索時(shí)不再重新計(jì)算。

圖2 正向最大匹配法流程圖

2.4 相似文章的檢索

當(dāng)使用者輸入檢索條件時(shí)，可將檢索條件看成一個(gè)n維的向量。相似文章的檢索問(wèn)題可以轉(zhuǎn)化為計(jì)算方向角來(lái)求解。

設(shè)用戶用以下順序輸入關(guān)鍵字進(jìn)行檢索:

則對(duì)于a1，…，an可為每個(gè)關(guān)鍵字自動(dòng)分配一個(gè)權(quán)重，可認(rèn)為第一個(gè)輸入的權(quán)重最高，第二個(gè)次之。則得到了一個(gè)n維向量，每個(gè)維度上的值使用詞典的默認(rèn)值。

而被搜索文檔中被自動(dòng)提取的關(guān)鍵字則組成了一個(gè)m維的向量。由于2個(gè)向量維度不一樣，在計(jì)算前需要降維。一般而言，被搜索文檔中的自動(dòng)關(guān)鍵詞維度大于用戶輸入的條件的維度，需要對(duì)文檔中的自動(dòng)關(guān)鍵詞進(jìn)行降維。即拋棄被搜索文檔中不在用戶輸入的條件中的自動(dòng)關(guān)鍵詞，被搜索文檔中的自動(dòng)關(guān)鍵詞是用戶輸入條件中的同義詞，則該關(guān)鍵詞的權(quán)重進(jìn)行處理后可以保留。

設(shè)用戶輸入的為{a，b，c，d，f}，而某文檔中的自動(dòng)關(guān)鍵詞及權(quán)重為:{a，c，d，e，f}，{0.9，0.81，0.80，0.79，0.66}，則自動(dòng)關(guān)鍵詞在用戶輸入維度上的向量為{0.9，0，0.81，0.80，0.66}。

當(dāng)2個(gè)向量具有相同維度后，可計(jì)算2個(gè)向量的相似性。根據(jù)向量代數(shù)的性質(zhì)，兩模相等的向量同向時(shí)兩向量相等，則可把兩向量的相似度轉(zhuǎn)化為求向量的夾角。

由向量數(shù)量積的概念可知:

式中:Ai，Bi是向量a，b在向量維度上的分量。

根據(jù)一定的閥值，過(guò)濾小于cosθ的查詢結(jié)果，就可得到與檢索條件接近的文檔。

在具體實(shí)施中還對(duì)查詢的結(jié)果進(jìn)行一定的排序，排序策略為:所有關(guān)鍵詞全部匹配檢索條件的文章首選，部分匹配檢索關(guān)鍵詞和部分匹配檢索關(guān)鍵詞的同義詞的文章排第二，部分匹配檢索關(guān)鍵詞的文章排第三，全部匹配檢索關(guān)鍵詞的同義詞的文章排第四，部分匹配檢索關(guān)鍵詞的同義詞的文章排第五。處理完畢后則可將結(jié)果呈現(xiàn)給查詢者。

2.5 關(guān)鍵詞糾錯(cuò)與詞庫(kù)的管理

由于用戶輸入的不一定是分割后的關(guān)鍵詞，更有可能是包含多個(gè)關(guān)鍵字的句子，對(duì)于關(guān)鍵詞也需要進(jìn)行分詞處理。然而用戶的輸出也存在眾多錯(cuò)誤的可能，最常見(jiàn)的是使用拼音輸入法造成的同音不同詞，因此需要對(duì)用戶的輸入進(jìn)行糾錯(cuò)。針對(duì)這一問(wèn)題，在詞庫(kù)中設(shè)立混淆集，即將同拼音的詞存放在一個(gè)集合中。當(dāng)掃描到一特征時(shí)，要從混淆集中查找是否有更為合適的特征。

詞庫(kù)維護(hù)時(shí)，詞庫(kù)中需要記錄混淆集中出現(xiàn)的特征的句子，并計(jì)算與其組合的其他特征的關(guān)聯(lián)程度。這是從混淆集中查找是否有更為合適特征的依據(jù)。

另外，詞庫(kù)還需要提供對(duì)新詞、同義詞的管理，此處不進(jìn)行介紹。

3 實(shí)驗(yàn)及結(jié)果

在本研究中對(duì)TF-IDF算法進(jìn)行了局部的改進(jìn)，在使用前要用實(shí)驗(yàn)來(lái)檢驗(yàn)算法的結(jié)果。檢驗(yàn)的文檔從公司的文檔服務(wù)器中提取共計(jì)1 762篇，其中公司治理文檔121篇，客戶資料208篇，開(kāi)發(fā)技術(shù)文檔591篇、市場(chǎng)文本299篇，行業(yè)新聞543篇。采用以下方法選擇訓(xùn)練集和測(cè)試集:在543篇行業(yè)新聞中選取501篇作為訓(xùn)練文本集。在其他類別的文檔中各抽取10篇，并與行業(yè)新聞中剩余的文檔組成測(cè)試集，自動(dòng)提取的關(guān)鍵詞與人工給出的結(jié)果見(jiàn)表1。

表1 實(shí)驗(yàn)結(jié)果

使用改進(jìn)式得到的結(jié)果與使用TF-IDF算法相比，關(guān)鍵詞提取的效果有了明顯的改進(jìn)。

4 結(jié)語(yǔ)

本研究目前已被應(yīng)用于一家軟件企業(yè)的日常管理。在人事管理、開(kāi)發(fā)管理、客戶管理等多個(gè)領(lǐng)域均發(fā)揮了重要作用。

［1］韓家煒.數(shù)據(jù)挖掘技術(shù)與概念［M］.北京:機(jī)械工業(yè)出版社，2007:223，258.

［2］秦鋒，任詩(shī)流，程澤凱，等.基于屬性加權(quán)的樸素貝葉斯分類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008(6):111-113.

［3］黃承慧，印鑒，侯昉.一種結(jié)合詞項(xiàng)語(yǔ)義信息和TF-IDF方法的文本相似度量方法［J］.計(jì)算機(jī)學(xué)報(bào)，2011(5):98-106.

［4］陸玉昌，魯明羽，李凡，等.向量空間法中單詞權(quán)重函數(shù)的分析和構(gòu)造［J］.計(jì)算機(jī)研究與發(fā)展，2002(10):55-60.