張 鯤
(閩江學(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)行分類。
文本分類是自然語(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]。
軟件企業(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ì)本研究的推理策略。
詞典構(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ò)程。
為了將最大的復(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。
關(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 正向最大匹配法流程圖
當(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)給查詢者。
由于用戶輸入的不一定是分割后的關(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)行介紹。
在本研究中對(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)。
本研究目前已被應(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.