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

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

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

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

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

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

1.1 信息顆粒更新流程

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

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

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

1.2.1 文本預(yù)處理

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

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

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

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

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

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

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

1.2.3 插入新文本

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

1.3 信息顆粒更新方法

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

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

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

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

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

2 實驗及結(jié)果分析

2.1 實驗準(zhǔn)備與性能評價指標(biāo)

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

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

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

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

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

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

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

2.2 更新算例

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

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

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

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

圖1 計算機領(lǐng)域新信息顆粒樹

圖2 聚類結(jié)果對比圖

圖3 運行時間對比圖

3 結(jié)論

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

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

［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］周芳，王鵬波，韓立巖.多源知識融合處理算法［J］.北京航空航天大學(xué)學(xué)報，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］劉平峰，余文艷，游懷杰.基于模糊等價關(guān)系的文本多粒度劃分方法［J］.情報學(xué)報，2012，31(6)：589-594.

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

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

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

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

［9］張霞，尹怡欣. 基于模糊粒度計算的文本聚類研究［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.