優(yōu)化的覆蓋算法在文本挖掘中的應(yīng)用研究

周瑛　牛瀏

摘要：文章首先分析了覆蓋算法中存在的兩個主要缺點，即由于分類邊界的粗糙而造成的測試樣本拒識的概率較大以及當(dāng)所得的覆蓋存在交叉時，測試樣本的類別確定問題，在此基礎(chǔ)上應(yīng)用基于商空間的粒度計算理論針對覆蓋算法中的第二個缺點進(jìn)行優(yōu)化，即對覆蓋算法中的由于覆蓋交叉而誤判的樣本進(jìn)行二次識別。通過減小識別樣本的粒度，使覆蓋粒度在由粗到細(xì)的變化過程中，實現(xiàn)對誤判樣本的漸進(jìn)識別，在更小的空間上實現(xiàn)對誤判樣本的二次識別，從而提高了識別率。最后在已進(jìn)行過預(yù)處理的中文文本數(shù)據(jù)庫中使用優(yōu)化后的覆蓋算法，實驗結(jié)果表明，優(yōu)化后的方法減少了誤判樣本的數(shù)量，降低了識別樣本時的出錯率，有效地提高了分類的精度。

關(guān)鍵詞：覆蓋交叉；粒度計算理論；文本挖掘

中圖分類號：TP391.1 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）33-8065-05

Abstract： The authors analysis two shortcomings of Covering Algorithm， that is， the high rate of refused samples because of the rough boundary of classification and the class which are in the cross of coverage belong to. Based on this， the author apply the granular computing theory based on quotient into the improvement and optimization of the second shortcoming of covering algorithm， that is， classify the misclassified samples because of the cross of coverage again. In the course of decreasing granular from big to small by using the different granular of classifying the samples， the authors classify the misclassified samples gradually and improve the classified correct rate by reduced the misclassified samples in the smaller granular. The authors apply the optimized Covering Algorithm in Chinese Text Database which has been cut into words. The computer experiments show that this method reduce the number of misclassified samples and enhance the accuracy of test samples by decreasing the error rate in the test.

Key words： cross of coverage； granular computing theory； text mining

文本挖掘的研究包括文本分類、文本聚類、文本數(shù)據(jù)信息訪問（信息檢索、信息瀏覽、信息過濾、信息報告）、知識發(fā)現(xiàn)（數(shù)據(jù)分析、數(shù)據(jù)預(yù)測）和文本信息提取等內(nèi)容。它能從大量文本的集合中發(fā)現(xiàn)隱含的模式。如果將文本的集合看作輸入，將模式看作輸出，那么文本挖掘的過程就是尋找一個從輸入到輸出的映射。而文本分類的目的是讓機(jī)器找到一個分類函數(shù)或分類模型，該模型能把測試的文本映射到己經(jīng)存在的多個類別中的某一類，使檢索或查詢的速度更快，準(zhǔn)確率更高。文本分類是文本挖掘的一個重要內(nèi)容。而對于文本分類來說，它的核心部分是用于文本分類的算法。在眾多的文本分類的方法中，除了傳統(tǒng)的貝葉斯方法、神經(jīng)網(wǎng)絡(luò)方法、粗糙集方法、向量空間模型法、遺傳算法、決策樹方法、支持向量機(jī)等方法外，覆蓋算法在文本分類中取得了不錯的效果[1]。但覆蓋算法自身存在著兩個缺點，該文通過對該算法的優(yōu)化，改進(jìn)它的性能，提高該算法的分類精度。

粒度計算的方法產(chǎn)生于十九世紀(jì)七十年代，它模仿人類在思考和分析問題的時候的幾種過程。有時先從總體進(jìn)行分析，然后再在局部進(jìn)行細(xì)化分析，對各種有用的信息加以考慮，這是一個由粗到細(xì)的分析過程；或者相反地，先從局部開始分析各種數(shù)據(jù)，再到全局進(jìn)行總體分析，這是一個由細(xì)到粗的分析過程；也有可能從不同的角度對問題進(jìn)行不同層面的分析，再對所獲得的有用數(shù)據(jù)進(jìn)行總體的分析，這是一個多方位、多角度的綜合分析過程[2]。近年來，人們開始將粒度計算的理論與算法應(yīng)用到數(shù)據(jù)挖掘的相關(guān)領(lǐng)域，取得了一些成果，粒度計算方法也成為數(shù)據(jù)挖掘領(lǐng)域的一個新的研究方向。

本文使用粒度計算理論對覆蓋算法進(jìn)行優(yōu)化處理，并將優(yōu)化后的覆蓋算法應(yīng)用于文本挖掘領(lǐng)域。利用粒度計算的思想對文本分類算法——覆蓋算法進(jìn)行優(yōu)化，對覆蓋算法中的由于覆蓋交叉而誤判的樣本進(jìn)行二次識別。通過減小覆蓋的半徑來減小樣本識別的粒度，使覆蓋粒度在由粗到細(xì)的變化過程中，實現(xiàn)對誤判樣本的漸進(jìn)識別，在更小的空間上實現(xiàn)對誤判樣本的二次識別，從而提高了識別率。最后在已進(jìn)行過預(yù)處理的中文文本數(shù)據(jù)庫中使用優(yōu)化后的覆蓋算法，實驗結(jié)果表明，優(yōu)化后的方法減少了誤判樣本的數(shù)量，降低了識別樣本時的出錯率，從而有效地提高了分類的精度。

1 覆蓋算法的缺陷分析

覆蓋算法（Cover Algorithm，CA）是張鈴教授和張鈸院士根據(jù)M—P神經(jīng)元的幾何意義提出的一種前向神經(jīng)網(wǎng)絡(luò)的新的學(xué)習(xí)算法[3]。這種算法僅需對訓(xùn)練樣本學(xué)習(xí)一次，便可以構(gòu)造性地得到對于訓(xùn)練樣本幾乎完全正確分類的神經(jīng)網(wǎng)絡(luò)，而不需要像傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)BP算法那樣反復(fù)地進(jìn)行迭代訓(xùn)練而未必能得到理想的分類結(jié)果。覆蓋算法減少了隱層神經(jīng)元的個數(shù)，縮小了問題求解的規(guī)模，具有訓(xùn)練時間短、計算量小、識別效率高等優(yōu)點。該算法對海量數(shù)據(jù)的處理效果尤為特出，比較適合象文本分類、手寫漢字的識別、圖像檢索等問題的處理。

覆蓋算法的主要思想是：給定一個有m類的訓(xùn)練樣本集，構(gòu)造一個前向神經(jīng)網(wǎng)絡(luò)，將n維空間中的p個樣本分成指定的m類。在該算法的學(xué)習(xí)算法中，首先將n維空間中的樣本經(jīng)過變換投影到n+1維的超球上，超球的半徑R一般取所有樣本最大模的2—3倍（這是一個經(jīng)驗值）。然后求一組包含圓心和半徑的覆蓋，一個覆蓋只包含同一類樣本點。所有覆蓋的集合就是覆蓋算法得到的解。這個過程等價于求出一組領(lǐng)域，這組領(lǐng)域?qū)⒉煌惖狞c分隔開來，使屬于第k類的點的輸出均為Y =（0，…，1，…，0，0）（即第i個分量為1，其余分量為0的向量），i=1，2，…，p。在樣本的測試算法中，首先將測試樣本也同樣投影到超球上，其類別是由所覆蓋的球形領(lǐng)域的類別決定的。對于一個測試樣本，先給定一個閾值α，當(dāng)測試樣本落在距各覆蓋的距離均大于α?xí)r，認(rèn)為是拒識狀態(tài)，否則按“就近原則” 進(jìn)行判別其類別歸屬。

但是我們在進(jìn)行實際的計算時，所取的超球半徑R往往等于最大樣本模長的兩倍或三倍，因此在樣本所投影的球面上往往存在著較大范圍的不屬于任何一類覆蓋的空白區(qū)域，記為E。功能函數(shù)取特征函數(shù)σ，那么在這些空白區(qū)域上有σ（E）= 0，按照Vapnik的支持向量機(jī)理論，E就是分類的邊界。這個邊界十分粗糙，在測試樣本的識別過程中，當(dāng)測試樣本投影到空白區(qū)域時，無法確定空白區(qū)域E中的樣本的類別，即被拒識。拒識的樣本數(shù)量會直接影響到測試樣本的精度，這是覆蓋算法的第一個缺點。這個缺點是由于分類邊界的過于粗糙而造成的，在對樣本沒有處理之前，邊界無法變精確，只能對拒識的樣本進(jìn)行再次識別。對于這個缺點的優(yōu)化改進(jìn)，即怎樣對落入空白區(qū)域的拒識樣本進(jìn)行再次識別，以便確定拒識樣本的真正類別，從而提高分類的精度，我們已在論文[4]中進(jìn)行了詳細(xì)描述。

除此之外，當(dāng)我們把功能函數(shù)取特征函數(shù)σ時，“球形領(lǐng)域”內(nèi)的樣本點的輸出都為1，然而當(dāng)“球形領(lǐng)域”之間存在重疊交叉且重疊交叉的球形領(lǐng)域不屬于同一類別時，則出現(xiàn)了交叉的覆蓋。此時按“就近原則”對交叉區(qū)域的樣本點進(jìn)行處理，即根據(jù)待測樣本點距離覆蓋中心的遠(yuǎn)近來確定樣本點的類別。這種方式處理的結(jié)果可能會造成離半徑大的覆蓋較近的樣本點被誤判為與其相鄰的半徑較小的覆蓋所屬的類別，這樣可能產(chǎn)生誤判，影響分類的精確度。這是覆蓋算法的第二個缺點。這個缺點是由于訓(xùn)練樣本的分布過于密集和對訓(xùn)練樣本的學(xué)習(xí)順序的差別造成的，一種方法是增大所投影的超球的半徑，讓訓(xùn)練樣本的投影盡可能分散開。但這種方法增大了投影半徑R，大大增加了不屬于任何一個覆蓋的空白區(qū)域，使得分類的邊界更加粗糙，其直接后果是加大了第一種缺點的影響，讓更多的測試樣本落入空白區(qū)域而被拒識，降低了分類精確度。而對于海量數(shù)據(jù)來說，到目前為止沒有一個公認(rèn)的好的算法來確定訓(xùn)練樣本的學(xué)習(xí)順序。因此對這個缺點的優(yōu)化改進(jìn)的重點應(yīng)放在交叉區(qū)域樣本的類別的判定上。

2 優(yōu)化改進(jìn)的覆蓋算法的模型

2.1 基于商空間的粒度計算理論

粒度計算方法是以信息顆粒來表示信息并且進(jìn)行信息計算的理論，是對人類全局分析能力的一種模擬。它主要用于處理海量的、不確定的、模糊的信息。與我們所熟悉的數(shù)值計算相比是有明顯不同的。數(shù)值計算是面向數(shù)據(jù)的計算，而粒度計算則是面向知識的計算。只要在分析問題和求解問題的過程中，應(yīng)用了分組方法、分類方法和聚類等方法都屬于粒度計算的研究范疇。自上世紀(jì)九十年代中期以來，粒度計算方法一直受到國內(nèi)外研究學(xué)者的關(guān)注，成為人工智能研究中的一個新熱點。

粒度計算理論最早是美國的著名數(shù)學(xué)家、模糊數(shù)學(xué)的創(chuàng)始人Zadeh于20世紀(jì)70年代末提出來的，他首次提出并討論了模糊信息的粒度化問題，但在當(dāng)時并未引起足夠的重視。接著，Zadeh在20世紀(jì)末提出了粒度計算的三個重要的概念[5]——粒化、組織和因果關(guān)系，對粒度計算理論進(jìn)行了完善。此外，波蘭學(xué)者Pawlak在1982年提出了粗糙集理論，加拿大里賈納大學(xué)教授Y.Y.Yao（姚一豫）等提出了基于鄰域系統(tǒng)的粒度計算模型。而在國內(nèi)，清華大學(xué)計算機(jī)學(xué)院的張鈸院士和安徽大學(xué)的張鈴教授提出了基于商空間的粒度計算的模型。目前計算機(jī)科學(xué)的研究者一致認(rèn)為粒度計算最主要的三大理論分別是[6]：Zadeh提出的基于模糊邏輯的粒度計算理論、Pawlak提出的基于粗糙集的粒度計算理論[7]和張鈸等提出的基于商空間的粒度計算理論。該文主要討論張鈸等提出的基于商空間的粒度計算理論在覆蓋算法中的優(yōu)化應(yīng)用。

基于商空間的粒度計算理論模型是張鈸等在1990年獨立地提出的，該模型在問題求解的過程中是基于問題的分層表示來研究的。商空間的理論使我們把粒度計算看成是結(jié)構(gòu)化問題求解的一種方式。商空間理論的主要思想是：在研究問題求解時，概念是用粒度或子集來表示，不同概念的子集表現(xiàn)為不同的粒度。而對于空間的一個劃分——商空間與一簇概念是等價的，不同的概念簇就構(gòu)成了不同的商空間。粒度計算可表示為在一個給定的商空間中的各種子集間的關(guān)系的轉(zhuǎn)換。在研究一個問題時，我們可采用不同的粒度，通過綜合合成不同粒度的分析結(jié)果來得到原問題的解。

2.2 基于商空間的粒度計算理論在覆蓋算法中的優(yōu)化

覆蓋算法[8]通過對訓(xùn)練樣本進(jìn)行一次掃描，構(gòu)造出對應(yīng)于訓(xùn)練樣本完全正確分類的神經(jīng)網(wǎng)絡(luò)，再將被測試樣本的分類問題轉(zhuǎn)化成為訓(xùn)練時尋找球形領(lǐng)域的中心和半徑的覆蓋問題。覆蓋算法的最大優(yōu)點是速度快，準(zhǔn)確率高，它不需要像其它神經(jīng)網(wǎng)絡(luò)那樣反復(fù)地進(jìn)行迭代訓(xùn)練，還難以獲得好的分類效果。在測試時，測試樣本的類別是由覆蓋它的球形領(lǐng)域的類別所決定，縮小了問題的求解規(guī)模和計算量。

在覆蓋算法中，一個確定的覆蓋是用覆蓋中心和覆蓋半徑兩個參數(shù)表示的，如果將訓(xùn)練時得到的每個覆蓋與粒度計算理論中的信息顆粒相對應(yīng)，那么覆蓋的個數(shù)就與粒度計算理論中的粒度的粗細(xì)相對應(yīng)。也就是說，信息顆粒的多少表示研究問題的粒度的粗細(xì)，而在覆蓋算法中，覆蓋數(shù)目的多少也可以用來表示研究問題的粗細(xì)。如果信息粒越單一它就越小，處理問題的粒度細(xì)；相反，信息粒越抽象就越大，處理問題的粒度粗[9]。對應(yīng)于覆蓋算法，覆蓋的半徑小，數(shù)目多，處理問題的粒度就細(xì)，而覆蓋的半徑大，數(shù)目少，處理問題的就粗。為了提高算法的效率，我們要在粗粒度上分析問題，找盡可能少的覆蓋數(shù)，這樣需要增大覆蓋半徑，也就是說要找盡可能大的信息粒。但是隨著信息粒的增大，覆蓋算法存在的兩個主要缺點就顯得很明顯——測試樣本識別時拒識的概率較大以及當(dāng)所得的覆蓋存在交叉時，測試樣本的類別確定問題。

上述第一個問題已解決，為了解決第二個問題，即在不增大測試樣本錯誤率的情況下，我們利用商空間的“保真原理”可以對覆蓋算法中的交叉部分誤識樣本進(jìn)行再次識別，通過減小處理問題的粒度，使覆蓋半徑在由粗到細(xì)的變化過程中，實現(xiàn)對交叉部分誤識樣本的漸進(jìn)識別，在更細(xì)的空間中減少錯誤識別的樣本數(shù)，提高識別率。具體過程如下：

對于覆蓋交叉部分被錯誤識別的樣本，我們假設(shè)該錯誤識別樣本記為x，在圖1中用綠色的實心圓點表示，實線表示兩個已經(jīng)存在的同時覆蓋樣本x的兩個覆蓋，兩個覆蓋的中心分別是C1和C2，以實線表示的兩個圓表示這兩個交叉覆蓋，其半徑分別為r1和r2。覆蓋C1中的點用小空心圓表示，覆蓋C2中的點以實心方塊表示，C1和C2中的點不屬于同一類別。測試樣本x同時屬于C1和C2，在原覆蓋算法中，樣本x與圓心C2距離近，因而被判為屬于覆蓋C2。在對x進(jìn)行重新識別時，分別將覆蓋C1和覆蓋C2的半徑r1和r2縮小為原半徑的1/2（即r1=n/m* r1， r2=n/m* r2，此時n=1，m=2） ，重新對樣本x進(jìn)行識別。這時會出現(xiàn)三種情況：一是樣本x僅屬于覆蓋C1和C2中的一個，則直接判定樣本x的類別，圖1中的虛線所在的覆蓋，算法結(jié)束；二是樣本x仍然屬于覆蓋C1和C2交叉部分，則m= m+1，通過r1=n/m* r1， r2=n/m* r2得到新的r1和r2，繼續(xù)判定樣本x的類別；三是樣本x不屬于覆蓋C1和C2中的任一個，則n= n+1，通過r1=n/m* r1， r2=n/m* r2得到新的r1和r2，繼續(xù)判定樣本x的類別。在圖1中，樣本x屬于覆蓋C1，這樣就可將樣本x判定為覆蓋C1所在的類別。在原來的算法中，樣本x被誤判為覆蓋C2所在的類別，現(xiàn)在通過細(xì)化覆蓋的粒度，確定了樣本x的類別，這樣降低了測試樣本的錯誤率，從而提高了測試樣本的識別精度。

4 結(jié)束語

本文將粒度計算理論應(yīng)用于覆蓋算法的優(yōu)化中，對覆蓋算法中的位于不同類別的覆蓋交叉部分的測試樣本進(jìn)行二次處理。在原覆蓋算法中，按“就近原則”對交叉區(qū)域的樣本點進(jìn)行處理，即根據(jù)待測樣本點距離覆蓋中心的遠(yuǎn)近來確定樣本點的類別。這種方式處理的結(jié)果可能會造成離半徑大的覆蓋較近的樣本點被誤判為與其相鄰的半徑較小的覆蓋所屬的類別，這樣可能產(chǎn)生誤判，影響分類的精確度。在覆蓋算法中，將每個覆蓋看作粒度計算中的信息粒，粒度的粗細(xì)則表示為覆蓋個數(shù)的多少。覆蓋半徑越大，覆蓋數(shù)量越少，處理問題的粒度就越粗，反之，覆蓋半徑越小，覆蓋數(shù)量越多，處理問題的粒度就越細(xì)。對于位于不同類別的覆蓋交叉部分的測試樣本來說，通過減小覆蓋半徑來改變處理問題的粒度，使覆蓋粒度在由粗到細(xì)的變化過程中，實現(xiàn)對位于交叉部分樣本的精確識別，在更細(xì)的空間中減少交叉的樣本數(shù)，提高識別率。再將優(yōu)化后的覆蓋算法應(yīng)用于已進(jìn)行分詞預(yù)處理的中文文本數(shù)據(jù)庫。計算機(jī)實驗表明通過減小覆蓋的粒度而進(jìn)行優(yōu)化后的覆蓋算法實現(xiàn)了覆蓋交叉部分樣本的精確識別，降低了識別錯誤。與原覆蓋算法相比，它在增加有限的訓(xùn)練時間的前提下提高了實驗結(jié)果的精度，該方法有效地提高了實驗結(jié)果的精確度，進(jìn)而驗證了這種方法的優(yōu)化作用。

參考文獻(xiàn)：

[1] 周瑛，劉政怡.覆蓋算法在文本分類中的應(yīng)用[J].情報理論與實踐，2006，29（1）：115-117.

[2] 張鈴，張鈸.問題求解理論及應(yīng)用——商空間粒度計算理論及應(yīng)用[M]. 2版.北京：清華大學(xué)出版社，2007 .

[3] 張鈴，張鈸，殷海風(fēng).多層前向網(wǎng)絡(luò)的交叉覆蓋算法[J].軟件學(xué)報，1999，10（7）：737-742.

[4] 周瑛，牛瀏.基于粒度計算的覆蓋算法在文本挖掘中的應(yīng)用研究[J].電腦知識與技術(shù)，2014，10（11）：2548-2552.

[5] Zadeh LA.fuzzy logic computing with words[J].IEEE Transactions on Fuzzy Systems， 1996， 4（1）：103-111.

[6] 李道國，苗奪謙.粒度計算研究綜述[J].計算機(jī)科學(xué)，2005，32（9）：1-12.

[7] Yao YY.Granular computing： basic issues and possible solutions[C]//Wang PP.Proceedings of the 5th Joint Conference on Information Sciences， Vol I. Atlantic， NJ： Association for Intelligent Machinery， 2000：186-189.

[8] 周瑛.優(yōu)化的覆蓋算法在信息檢索中的應(yīng)用[J].情報理論與實踐，2010，33（5）：92-94.

[9] 蘇頻.基于DFS的并行粒度計算模型及其應(yīng)用[D].蘇州：蘇州大學(xué)，2007.

[10] 周瑛.有限混合模型在文本分類中的應(yīng)用[J].計算機(jī)技術(shù)與發(fā)展，2010，20（6）：18-20.

[11] 周瑛.神經(jīng)網(wǎng)絡(luò)作為分類器的算法研究及在信息檢索中的應(yīng)用[D].合肥：安徽大學(xué)，2006.