可變屬性粒度的中文文本概念格聚類研究

吳湘華 曹麗君

摘要：傳統(tǒng)的中文文本聚類方法需要將半結(jié)構(gòu)化或非結(jié)構(gòu)化的數(shù)據(jù)構(gòu)建數(shù)學(xué)模型，一般情況下都要進(jìn)行降維處理，這些操作均會(huì)帶來(lái)一定失真，影響聚類的準(zhǔn)確性和效果。該文以待聚類文本為研究對(duì)象，以文本特征詞為屬性，引入形式概念分析理論，采用概念格聚類的方式對(duì)中文文本進(jìn)行聚類，同時(shí)，將特征詞匹配至可變屬性粒度的屬性樹上，避免因?yàn)閷傩粤６冗^(guò)細(xì)導(dǎo)致聚類速度慢的問題，該算法聚類效果良好。

關(guān)鍵詞：中文文本聚類;形式概念分析;概念格;可變粒度;特征詞

中圖分類號(hào)：中圖分類號(hào)：TP319? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）26-0027-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

針對(duì)文本數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘與知識(shí)描述、知識(shí)發(fā)現(xiàn)的過(guò)程統(tǒng)稱為文本挖掘。隨著信息時(shí)代的日益發(fā)達(dá)，許多信息都是以文本的形式出現(xiàn)，與傳統(tǒng)數(shù)據(jù)挖掘中不同，文本是一種半結(jié)構(gòu)化或者非結(jié)構(gòu)化數(shù)據(jù)，文本挖掘成為數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)熱點(diǎn)，同時(shí)也是一個(gè)難點(diǎn)。文本數(shù)據(jù)一般具有高維度，一些傳統(tǒng)的數(shù)據(jù)挖掘方法在文本挖掘中往往無(wú)法獲得良好的效果。文本聚類技術(shù)[1]是文本挖掘中非常重要的一個(gè)方向，通過(guò)對(duì)文本之間的相似性挖掘，將相似的多個(gè)文本對(duì)象劃分至同一個(gè)類別，不相似的文本對(duì)象劃分至不同的文本類別中，最終將混亂的文本整理成為多個(gè)規(guī)范的文本集合。通過(guò)文本聚類，可以實(shí)現(xiàn)多文檔自動(dòng)文摘[2]、信息過(guò)濾[3]、搜索結(jié)果進(jìn)行聚類[4]、 數(shù)字圖書館推送服務(wù)[5]等。

1? 中文文本聚類

中文文本聚類是以中文文本為對(duì)象的文本聚類。在中文文本聚類之前，需要做一系列預(yù)處理工作，預(yù)處理一般包括分詞、去停用詞、詞條標(biāo)準(zhǔn)化、特征詞提取等等。中文文本預(yù)處理之后，將用一組特征詞代替原始文本，文本預(yù)處理過(guò)程會(huì)導(dǎo)致一定的失真，不同的預(yù)處理方法對(duì)后續(xù)的聚類會(huì)產(chǎn)生不同的影響。中文文本除了用標(biāo)點(diǎn)分隔句子之外，每一句話的詞與詞間是連續(xù)的，不存在明顯的分隔符號(hào)，必須進(jìn)行分詞處理，分詞處理技術(shù)一般有基于詞典匹配的分詞法、基于理解的分詞法和基于統(tǒng)計(jì)的分詞法等。停用詞是在文本集中出現(xiàn)對(duì)文本特征詞提取沒有意思的詞，且這些詞出現(xiàn)頻率較高，在所有文本中具有近似的分布概率;通過(guò)構(gòu)建一個(gè)停用詞表，刪除文本集中出現(xiàn)的停用詞，這個(gè)過(guò)程就叫作去停用詞。中文對(duì)同一個(gè)事物的表述往往有很多種方式，如“電腦”和“電子計(jì)算機(jī)”表述的是同一事物，為此，文本通過(guò)分詞與去停用詞后，需要將詞條進(jìn)行規(guī)范化，將不規(guī)范的自由詞替換為標(biāo)準(zhǔn)詞，通過(guò)去停用詞和詞條標(biāo)準(zhǔn)化后得到的詞條集合能夠更加精準(zhǔn)的反映原始文本、降低維度、提高文本聚類的精度和效率。經(jīng)過(guò)上述處理之后，就要采取一定的算法提取出合適數(shù)量最能代表和概括文本特征的特征詞，一般使用評(píng)估函數(shù)進(jìn)行特征詞的提取，用評(píng)估函數(shù)對(duì)詞條進(jìn)行賦值，并選取一定數(shù)量得分較高詞條特征詞提取的結(jié)果。文本一般都是半結(jié)構(gòu)化的或者非結(jié)構(gòu)化的，無(wú)法直接聚類，先要建立一個(gè)形式化的數(shù)學(xué)模型有效的反映原始文本的特征，常用的有布爾模型、向量空間模型、概率型等。接下進(jìn)行聚類分析，常用的有K-means算法、EM算法、層次聚類算法等，但是這些聚類對(duì)文本聚類效果沒有明顯的突破和創(chuàng)新。

2? 概念格聚類

Wille教授[6]提出基于序理論的形式概念分析理論。具有自反性、反對(duì)稱性、傳遞性的二元關(guān)系稱為偏序關(guān)系，集合N及其上的偏序關(guān)系≤組成的有序二元組稱為偏序集。格是一種特殊的偏序集，一個(gè)偏序集中，集合N中任意兩個(gè)元素都存在上確界和下確界，我們稱該偏序集為格;完全格則是格的特例，對(duì)于任意偏序集的子集都存在上確界和下確界，則該格稱為完全格。形式背景是一個(gè)三元組K=（G，M，I），G表示對(duì)象集合，M表示G中對(duì)象所有屬性的集合，I是集合G和集合M笛卡爾積的子集，[（g，m）∈I]表示對(duì)象[g]具有屬性[m]。集合A是集合G的子集，則將集合A中所有對(duì)象的共同屬性定義為A，集合B是集合M的子集，將含有B集合中所有屬性的對(duì)象集合定義為B，且A=B，B=A，則稱（A，B）為形式背景K的一個(gè)概念，β（G，M，I）是背景K上所有概念集合。若（A1，B1）和（A2，B2）分別是形式背景K的兩個(gè)概念，若A1包含于A2等價(jià)于B2包含于B1蘊(yùn)含A1包含A2則稱（A1，B1）是（A2，B2）的子概念，（A2，B2）是（A1，B1）的超概念，記為（A1，B1）≤（A2，B2），為偏序關(guān)系。將形式背景K上所有的偏序關(guān)系集合稱為該背景上的概念格，記為Β（G，M，I），概念格是一個(gè)完全格，具有對(duì)偶性，將形式背景中的對(duì)象和屬性交換，同樣可以得到一個(gè)概念格，只是在哈斯圖中與原概念格相比上下層順序倒過(guò)來(lái)了。概念格建立的過(guò)程就是一個(gè)聚類過(guò)程，概念格聚類是一個(gè)雙聚類，不僅可以對(duì)對(duì)象進(jìn)行聚類也可以對(duì)屬性進(jìn)行聚類。形式概念分析最重要的是構(gòu)建形式背景、生成概念格，概念格構(gòu)建算法一般有自頂向下和自底向上批處理算法和漸進(jìn)式算法。對(duì)于同一形式背景，不管構(gòu)建過(guò)程怎么樣，最終生成的概念格都是一樣的。使用形式概念分析方法進(jìn)行概念格聚類，會(huì)完整保留數(shù)據(jù)的細(xì)節(jié)信息，不會(huì)降低數(shù)據(jù)的復(fù)雜性。概念格中每一個(gè)概念代表一個(gè)聚類類別，概念的外延是文本對(duì)象集合，概念的內(nèi)涵為外延中文本對(duì)象的共同特征集合。概念格的上下層概念為包含與被包含的關(guān)系，下層概念為上層概念的細(xì)分，是一種較新的并且具有很多優(yōu)點(diǎn)的聚類方法，其缺點(diǎn)是待聚類對(duì)象數(shù)量大、屬性多的情況下，概念格構(gòu)建速度慢。

3? 可變屬性粒度中文文本概念格聚類

對(duì)象的屬性往往是指在一定粒度下的屬性，比方說(shuō)，對(duì)象具有某一屬性A，屬性A可以細(xì)分為L(zhǎng)A和RA兩個(gè)更加具體的屬性，如果在較粗的粒度，某個(gè)對(duì)象具有的屬性即為A，但是在比較細(xì)的粒度，某個(gè)對(duì)象具有的屬性為L(zhǎng)A或者是RA，屬性粒度的粗細(xì)也是具有層次性。粒度越粗所暴露的細(xì)節(jié)越少、屬性數(shù)量越少;粒度越細(xì)，描述越詳細(xì)、屬性數(shù)量越大。在中文概念格聚類中，通過(guò)構(gòu)建可變屬性粒度樹，實(shí)現(xiàn)對(duì)聚類效果的優(yōu)化，使得聚類結(jié)果更加有效、更加合理，避免屬性多過(guò)情況下聚類速度慢的情形。具體算法如下：（1）對(duì)于待聚類文本集，基于百度百科構(gòu)建屬性粒度樹;（2）將文本特征詞匹配至屬性粒度樹上;（3）以待聚類文本為對(duì)象，屬性粒度樹上詞條為屬性構(gòu)建概念格，實(shí)現(xiàn)可變屬性粒度中文文本概念格聚類。

取150篇文本進(jìn)行可變粒度概念格聚類，在不同粒度下的聚類結(jié)果如下圖1：

（1）細(xì)粒度下的概念格聚類

（2）中等粒度下的概念格聚類

（3）粗粒度下的概念格聚類

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，在細(xì)粒度下，聚類過(guò)程緩慢，在粗粒度下聚類結(jié)果粗糙，通過(guò)建立合適可變粒度的屬性書，在上述中等粒度下進(jìn)行概念格聚類，既保證了聚類結(jié)果的準(zhǔn)確性，又有比較快的聚類速度，該算法有效。

4 結(jié)束語(yǔ)

本文以中文文本為研究對(duì)象，以文本特征詞為屬性，采用形式概念分析理論，使用概念格的聚類方法，通過(guò)構(gòu)建合適粒度的可變屬性粒度樹，實(shí)現(xiàn)中文文本聚類，該算法比傳統(tǒng)的中文文本聚類方法更為準(zhǔn)確和有效。

參考文獻(xiàn)

[1] Rui X，Donald W.Survey of clustering algorithms[J].Neural Networks IEEE Transactions on，2005，16（3）：645-678.

[2] Hatzivassiloglou V，Klavans J L，Holcombe M L，et al.SIMFINDER：A flexible clustering tool for summarization[J].Proceedings of the Naacl Workshop on Automatic Summarization，2003：41-49.

[3] 林鴻飛，馬雅彬.基于聚類的文本過(guò)濾模型[J].大連理工大學(xué)學(xué)報(bào)，2002，42（2）：249-252.

[4] Zeng H J，He Q C，Chen Z，et al.Learning to cluster web search results[C].2004.

[5] Rauber A，F(xiàn)rühwirth M.Automatically Analyzing and Organizing Music Archives[C].2010.

[6] Wille R.Restructuring lattice theory：An approach based on hierarchies of concepts[J]. Springer，2009.

【通聯(lián)編輯：朱寶貴】