聶規(guī)劃，于珊珊，劉平峰，游懷杰

(武漢理工大學(xué)電子商務(wù)與智能服務(wù)研究中心，湖北武漢430070)

互聯(lián)網(wǎng)信息的爆炸式增長(zhǎng)給用戶帶來(lái)了高昂的搜索和瀏覽成本。整合多源信息，為用戶提供簡(jiǎn)單高效的信息檢索方式是一個(gè)難題，而解決這個(gè)難題的重要方法之一是進(jìn)行有效的信息融合。通過(guò)信息融合可以將具有相似主題的文本聚合在一個(gè)信息顆粒下，便于用戶檢索。目前有關(guān)信息融合的研究主要集中在Web 信息融合方面，特別是多源Web 信息檢索融合［1］、多源知識(shí)融合［2］和面向決策的Web 信息融合等［3］，部分學(xué)者也進(jìn)行了多粒度多層次的Web 信息劃分與融合的研究。多粒度劃分的方法主要包括層次聚類(lèi)法和模糊粒度計(jì)算等。其中劉平峰等［4］結(jié)合模糊熵空間理論與現(xiàn)有劃分方法，提出了一種基于模糊等價(jià)關(guān)系的方法。層次聚類(lèi)法等傳統(tǒng)的文本多粒度劃分方法多采用全量更新的方式，但在互聯(lián)網(wǎng)信息海量增長(zhǎng)的大背景下，其顯然無(wú)法滿足高效處理信息的需求。目前有部分學(xué)者開(kāi)始研究增量學(xué)習(xí)算法以解決快速處理信息的問(wèn)題。古平等［5］提出了一種基于類(lèi)別上下文特征的層次分類(lèi)模型及增量學(xué)習(xí)算法，提升了算法的自適應(yīng)性和分類(lèi)精度。王萬(wàn)良等［6］提出了一種稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法，利用迭代運(yùn)算提升了大數(shù)據(jù)處理中降維的時(shí)間效率及分解后數(shù)據(jù)的稀疏性。郭躬德等［7］提出了一個(gè)基于KNN 模型的增量學(xué)習(xí)算法，引進(jìn)層的概念達(dá)到增量學(xué)習(xí)的效果。趙耀紅等［8］提出快速支持向量機(jī)增量學(xué)習(xí)算法，有選擇地淘汰學(xué)習(xí)樣本。但以上方法在類(lèi)別有偏情況下存在算法精確度波動(dòng)大、應(yīng)用范圍存在局限性、測(cè)試時(shí)間較長(zhǎng)和樣本集的選取顯著影響增量學(xué)習(xí)效果等問(wèn)題，不利于大數(shù)據(jù)環(huán)境下信息顆粒的即時(shí)、高效和精準(zhǔn)更新。

基于以上研究，筆者采用增量式算法對(duì)新加入的文本進(jìn)行處理。在不對(duì)所有信息顆粒進(jìn)行重構(gòu)的情況下，僅進(jìn)行新增文本更新，使信息顆粒樹(shù)處于動(dòng)態(tài)更新的狀態(tài)，從而既能自適應(yīng)學(xué)習(xí)，又能保持良好的時(shí)間特性。

1 基于相似度的信息顆粒更新

1.1 信息顆粒更新流程

當(dāng)有新文本進(jìn)入后，對(duì)其預(yù)處理得到文本空間向量模型。結(jié)合原信息顆粒樹(shù)，得到新文本/信息顆粒樹(shù)的關(guān)鍵詞矩陣?；谟嘞蚁嗨菩运惴ㄓ?jì)算新文本關(guān)鍵詞與原信息顆粒關(guān)鍵詞的相似度，得到新文本/原信息顆粒的相似關(guān)系矩陣。依據(jù)相似度是否高于設(shè)定的閾值決定是否向上重新選擇信息顆粒，把新文本歸入最優(yōu)信息顆粒下，得到新增文本后的信息顆粒樹(shù)。根據(jù)新文本加入給信息顆粒主題帶來(lái)的變化，更新信息顆粒質(zhì)心，計(jì)算顆粒間的相似度情況并進(jìn)行顆粒的泛化、剪枝、細(xì)化和拆分操作，從而達(dá)到更新信息顆粒樹(shù)的目的。

1.2 文本動(dòng)態(tài)更新方法

每個(gè)底層信息顆粒的關(guān)鍵詞集合都由其所包含的文本實(shí)例計(jì)算得出，一旦加入數(shù)量足夠多的新文本，顆粒的主題就可能隨之發(fā)生變化。為了使整棵信息顆粒樹(shù)保持人類(lèi)認(rèn)知變化規(guī)律，首先需要將新文本歸入合適的顆粒中，其次判斷信息顆粒的主題是否發(fā)生變化而需要更新，最后進(jìn)行相應(yīng)的調(diào)整。而將新文本歸入信息顆粒同樣需要經(jīng)過(guò)3 個(gè)步驟，即文本預(yù)處理、關(guān)鍵詞相似度計(jì)算和插入新文本。

1.2.1 文本預(yù)處理

文本預(yù)處理的目的在于確定代表新文本的關(guān)鍵詞集合，主要操作包括詞語(yǔ)分解和TF -IDF 計(jì)算。通過(guò)使用現(xiàn)代漢語(yǔ)通用分詞系統(tǒng)(GPWS)對(duì)新文本進(jìn)行詞語(yǔ)分解和詞頻統(tǒng)計(jì)，并對(duì)分解出來(lái)的詞語(yǔ)進(jìn)行過(guò)濾。在過(guò)濾非關(guān)鍵詞后，再通過(guò)TF -IDF 計(jì)算進(jìn)一步篩選。給定文本集d= {d1，d2，…，dn}，以及出現(xiàn)的關(guān)鍵詞t={t1，t2，…，tm}，通過(guò)TF -IDF 計(jì)算一個(gè)詞語(yǔ)在一篇文檔中的重要性，考慮不同文本長(zhǎng)度對(duì)權(quán)重值的影響，對(duì)TF -IDF 的結(jié)果進(jìn)行歸一化［9］，其計(jì)算公式如下：

關(guān)鍵詞頻tft(d)為關(guān)鍵詞t在文本d中出現(xiàn)的頻率，逆向文件頻率IDF=lg(N/nt)，其中N為論域中文本總數(shù);nt為出現(xiàn)關(guān)鍵詞t的文本數(shù)。

利用向量空間模型(VSM)對(duì)文本進(jìn)行表示，把每一個(gè)文本d當(dāng)作空間內(nèi)的一個(gè)向量或空間點(diǎn)，表示為V(di)= (wi1，wi2，…，wip)，其中wip為文本di第p個(gè)關(guān)鍵詞在文本向量中的權(quán)重值，p為關(guān)鍵詞的個(gè)數(shù)，即文本空間維數(shù)。

1.2.2 關(guān)鍵詞相似度計(jì)算

建立新文本/信息顆粒-關(guān)鍵詞矩陣。假設(shè)新增n個(gè)文本，原信息顆粒樹(shù)中含m個(gè)底層信息顆粒，每條記錄分別為新文本及底層信息顆粒的各關(guān)鍵詞權(quán)重值。已知第i條記錄為V(di)=(wi1，wi2，…，wip)，采用余弦相似性算法，依次計(jì)算新文本與各信息顆粒向量的相似性，其中i∈［1，n］，j∈［n+1，n+m］，計(jì)算公式為：

可將新文本與信息顆粒向量的相似關(guān)系寫(xiě)成關(guān)系矩陣，如式(3)所示：

其中，Sij=sim(di，dj)，關(guān)系矩陣的第i行表示第i個(gè)新文本與每個(gè)底層信息顆粒的相似度。

1.2.3 插入新文本

計(jì)算關(guān)鍵詞相似度，若新文本與某底層信息顆粒的關(guān)鍵詞語(yǔ)義相似度最高，且高于預(yù)設(shè)的相似度閾值，系統(tǒng)則將新文本歸并到該信息顆粒下;若小于閾值，則向上逐層選擇信息顆粒，將新文本歸入最優(yōu)信息顆粒下，同時(shí)記錄下更新文本實(shí)例后信息顆粒的關(guān)鍵詞變化情況，包括關(guān)鍵詞詞頻、出現(xiàn)該關(guān)鍵詞的文本數(shù)等數(shù)據(jù)。

1.3 信息顆粒更新方法

加入新文本后，信息顆粒主題會(huì)發(fā)生一定變化，需要進(jìn)行有效的更新。CALEGARI 等［10］在研究應(yīng)用于本體的粒計(jì)算時(shí)提出4 種粒操作，即泛化、剪枝、細(xì)化和拆分。筆者的研究同樣涉及對(duì)信息顆粒進(jìn)行更新的4 種操作。

(1)泛化。信息顆粒是一個(gè)包含多個(gè)關(guān)鍵詞的集合。隨著信息顆粒下的文檔數(shù)量逐漸增多，部分主題相近的信息顆粒所包含的文本內(nèi)容趨于相似，導(dǎo)致類(lèi)間距離減小，分類(lèi)不明確。而泛化操作則是將一系列顆粒合并成一個(gè)更具概括性的信息顆粒，以降低顆粒間的分類(lèi)模糊性。

(2)剪枝。當(dāng)一個(gè)信息顆粒與其子信息顆粒具有過(guò)于類(lèi)似的關(guān)鍵詞集合，或者子信息顆粒下的文本數(shù)較少，自成一類(lèi)的意義不大時(shí)，就需要對(duì)信息顆粒樹(shù)進(jìn)行剪枝操作，即將子顆粒刪減，并把子顆粒下的文本升級(jí)為母顆粒的文本實(shí)例。

(3)細(xì)化。當(dāng)一個(gè)信息顆粒下所包含的文本數(shù)量較多時(shí)，可能會(huì)出現(xiàn)類(lèi)內(nèi)文本主題分散、分類(lèi)不統(tǒng)一的問(wèn)題，需要對(duì)該信息顆粒進(jìn)行細(xì)化，分解成更具體的不同主題。而細(xì)化操作則是為信息顆粒添加若干子顆粒，并根據(jù)文本主題的契合度將相應(yīng)文本進(jìn)行重新組織。

(4)拆分。拆分操作與細(xì)化操作的區(qū)別在于：①原信息顆粒在細(xì)化后依然存在，而拆分則是添加新的顆粒來(lái)替代原信息顆粒;②拆分操作無(wú)法對(duì)直接包含文檔的信息顆粒進(jìn)行操作。

2 實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)準(zhǔn)備與性能評(píng)價(jià)指標(biāo)

從復(fù)旦文本分類(lèi)語(yǔ)庫(kù)中選取200 篇有關(guān)計(jì)算機(jī)方面的文本，另外選取20 篇進(jìn)行劃分新增文本的實(shí)驗(yàn)。并將筆者提出的更新方法與層次聚類(lèi)方法進(jìn)行性能對(duì)比分析。性能評(píng)價(jià)考慮底層信息顆粒的類(lèi)內(nèi)距離和類(lèi)間距離，其公式為：

式中：α 和β 分別為類(lèi)內(nèi)距離和類(lèi)間距離的加權(quán)因子，視兩者的重要性而變化，但保持α+β =1，取α=β=0.5;Jw和Jb分別為信息顆粒的類(lèi)內(nèi)距離和類(lèi)間距離。

類(lèi)內(nèi)距離Jw是每個(gè)信息顆粒內(nèi)文本的權(quán)向量與質(zhì)心平均距離的歸一化表示，其公式為：

式中，Xi為信息顆粒j中第i個(gè)文本的權(quán)向量;為質(zhì)心;nj為顆粒內(nèi)的文本數(shù)量;k為底層信息顆粒的總數(shù)。

類(lèi)間距離Jb是每個(gè)信息顆粒與其他信息顆粒質(zhì)心的距離，其公式為：

信息顆粒j質(zhì)心的計(jì)算公式為：

其中，n為顆粒j中文本的個(gè)數(shù)。

2.2 更新算例

按照筆者方法，在完成新文本的插入更新后，對(duì)插入新文本后的信息顆粒的質(zhì)心進(jìn)行更新，計(jì)算新信息顆粒的類(lèi)內(nèi)距離和類(lèi)間距離。經(jīng)過(guò)泛化、剪枝、細(xì)化和拆分更新顆粒質(zhì)心后，得到新信息顆粒樹(shù)，計(jì)算機(jī)領(lǐng)域新信息顆粒樹(shù)如圖1 所示。

通過(guò)計(jì)算新信息顆粒樹(shù)中各信息顆粒的類(lèi)內(nèi)距離和類(lèi)間距離，得出筆者提出的信息顆粒更新方法與重新進(jìn)行層次聚類(lèi)方法相應(yīng)性能指標(biāo)J 的對(duì)比結(jié)果，如圖2 所示。

圖2 顯示，筆者提出的方法和層次聚類(lèi)法在聚類(lèi)數(shù)較少時(shí)就達(dá)到了較好的聚類(lèi)性能。隨著各層聚類(lèi)數(shù)的增加，用筆者方法構(gòu)建的新信息顆粒樹(shù)聚類(lèi)性能高于層次聚類(lèi)法，能夠更好地表述領(lǐng)域信息顆粒樹(shù)主題。

此外，由于筆者采用的是動(dòng)態(tài)插入新文本、增量更新信息顆粒樹(shù)的方式，相對(duì)于全量更新的層次聚類(lèi)法，效率更高。兩種方法的效率對(duì)比情況如圖3 所示。

圖1 計(jì)算機(jī)領(lǐng)域新信息顆粒樹(shù)

圖2 聚類(lèi)結(jié)果對(duì)比圖

圖3 運(yùn)行時(shí)間對(duì)比圖

3 結(jié)論

大部分文本粒度研究都只為獲得領(lǐng)域信息顆粒樹(shù)，忽視了由于增量更新文本而引起的信息顆粒樹(shù)的變化。筆者在以往信息顆粒樹(shù)生成研究的基礎(chǔ)上，探索了新文本的插入更新及新文本加入后信息顆粒樹(shù)的4 種更新機(jī)制，并進(jìn)行了驗(yàn)證。不足之處在于未能給出用于判斷執(zhí)行何種更新機(jī)制及其閾值設(shè)置依據(jù)。另外，由于各文本權(quán)向量與信息顆粒質(zhì)心的長(zhǎng)度由關(guān)鍵詞集合的大小而定，關(guān)鍵詞集合大小的設(shè)定也需要在未來(lái)的研究中進(jìn)一步探討。

綜上所述，信息顆粒更新方法無(wú)論是在性能還是在效率方面，都顯著優(yōu)于層次聚類(lèi)法，信息顆粒更新方法能有效表達(dá)動(dòng)態(tài)更新的信息顆粒樹(shù)主題，提高了更新效率。

［1］KEYHANIPOUR A H，MOSHIRI B，KAZEMIAN M，et al. Aggregation of web search engines based on users' preferences in WebFusion［J］. Knowledge -based Systems，2007，20(4)：321 -328.

［2］周芳，王鵬波，韓立巖.多源知識(shí)融合處理算法［J］.北京航空航天大學(xué)學(xué)報(bào)，2013(1)：23 -27.

［3］YU L A.Web warehouse：a new web information fusion tool for web mining［J］.Information Fusion，2008(9)：501 -511.

［4］劉平峰，余文艷，游懷杰.基于模糊等價(jià)關(guān)系的文本多粒度劃分方法［J］.情報(bào)學(xué)報(bào)，2012，31(6)：589-594.

［5］古平，羅志恒，歐陽(yáng)源遊.基于增量模式的文檔層次分類(lèi)研究［J］.計(jì)算機(jī)工程，2014，40(1)：209 -212.

［6］王萬(wàn)良，蔡競(jìng). 稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法［J］.計(jì)算機(jī)科學(xué)，2014，41(8)：241 -244.

［7］郭躬德，黃杰，陳黎飛.基于KNN 模型的增量學(xué)習(xí)算法［J］.模式識(shí)別與人工智能，2010，23(5)：701-707.

［8］趙耀紅，王快妮，鐘萍，等.快速支持向量機(jī)增量學(xué)習(xí)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010 (1)：161-163.

［9］張霞，尹怡欣. 基于模糊粒度計(jì)算的文本聚類(lèi)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(13)：53 -55.

［10］CALEGARI S，CIUCCI D. Granular computing applied to ontologies［J］. International Journal of Approximate Reasoning，2010，51(4)：391 -409.