周瑛　牛瀏

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

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

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

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

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

1 覆蓋算法的缺陷分析

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

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

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

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

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

2.1 基于商空間的粒度計(jì)算理論

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

[4] 周瑛，牛瀏.基于粒度計(jì)算的覆蓋算法在文本挖掘中的應(yīng)用研究[J].電腦知識(shí)與技術(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].計(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].情報(bào)理論與實(shí)踐，2010，33（5）：92-94.

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

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

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