文必龍，李 菲，馬 強(qiáng)

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引 言

一篇具有明確主旨的文章，多采用一定的組織形式去組織文本內(nèi)容。從文本內(nèi)容中挖掘有用信息，是目前文本挖掘、文本信息抽取等相關(guān)領(lǐng)域研究的重點(diǎn)[1]。作為一種能將不同組織形式的文本根據(jù)內(nèi)容聚集成簇的關(guān)鍵技術(shù)，聚類技術(shù)為文本內(nèi)容的進(jìn)一步分析挖掘提供了有力的支撐。K-means算法是基于劃分思想的經(jīng)典聚類算法[2]，是一種采取隨機(jī)確定初始點(diǎn)作為中心點(diǎn)，然后不斷循環(huán)迭代求得最大相似性的類別劃分算法[3]。該聚類算法針對(duì)主題摻雜、內(nèi)容組織無(wú)序的文本，具有簡(jiǎn)單、收斂速度快、處理大數(shù)據(jù)文本集有效等優(yōu)點(diǎn)[4]。傳統(tǒng)K-means算法隨機(jī)初始化中心點(diǎn)，在迭代聚類時(shí)會(huì)有以下問(wèn)題：需要輸入最終結(jié)果的聚類個(gè)數(shù)k[5],而判斷一個(gè)未知數(shù)據(jù)集的劃分個(gè)數(shù)通常是很困難的；k個(gè)初始點(diǎn)的選擇對(duì)最終的聚類結(jié)果影響很大[6]；聚類過(guò)程中的迭代總次數(shù)增加使得聚類過(guò)程中的總耗時(shí)增加[7]。為解決以上問(wèn)題，文獻(xiàn)[8]從樣本幾何結(jié)構(gòu)角度，設(shè)計(jì)一種新的聚類有效性指標(biāo)，依此確定最佳聚類數(shù)。文獻(xiàn)[4]和文獻(xiàn)[9]在初始化中心點(diǎn)上分別采用最大距離積法、密度區(qū)域相距最遠(yuǎn)來(lái)確定初始化中心點(diǎn)。文獻(xiàn)[10]和文獻(xiàn)[11]分別提出了基于最近高密度點(diǎn)間的垂直中心點(diǎn)優(yōu)化初始聚類中心和基于密度峰值優(yōu)化的K-means文本聚類算法，解決了聚類效率低和局部最優(yōu)解等問(wèn)題。在對(duì)整篇文章的內(nèi)容和組織結(jié)構(gòu)進(jìn)行分析時(shí)，發(fā)現(xiàn)文本具有基于某一主題下的有序組織的線性文本，對(duì)其采用傳統(tǒng)的K-means算法會(huì)存在以下問(wèn)題：(1)篇章主題內(nèi)容劃分的隨意性較大。在不考慮線性文本具有的上下文內(nèi)容劃分的清晰界限，采取文本段落向量的相似性進(jìn)行聚集分類時(shí)，聚類主題的側(cè)移影響最終結(jié)果；(2)隨機(jī)初始中心點(diǎn)的方式增大了聚類初始點(diǎn)的不確定性，在選擇不當(dāng)?shù)那闆r下使得迭代次數(shù)增加或無(wú)窮迭代、延長(zhǎng)運(yùn)算時(shí)間等。同時(shí)，該算法在處理段落文本到各個(gè)中心點(diǎn)的距離相等時(shí)，歸類不當(dāng)也會(huì)造成聚類結(jié)果的不精確等問(wèn)題。

針對(duì)以上問(wèn)題，文中深入分析線性文本內(nèi)容的組織特性，提出一種隨機(jī)均勻初始化中心點(diǎn)的K-means文本聚類算法，主要用來(lái)解決線性文本自身段落內(nèi)容、層次、主題等的聚類問(wèn)題。同時(shí)改進(jìn)收斂函數(shù)，提出等距點(diǎn)歸類法以解決特殊段落到中心點(diǎn)距離相同時(shí)無(wú)法準(zhǔn)確歸類的問(wèn)題。

1 線性文本

1.1 定 義

線性文本指的是閱讀時(shí)有先后順序，基于一個(gè)共同主題下劃分各個(gè)相關(guān)子主題，子主題之間相互獨(dú)立、均勻分散、段落在組織上具有線性結(jié)構(gòu)的一類文本。傳統(tǒng)的教材課文不管文字排列的方式如何，文章的寫(xiě)作和學(xué)習(xí)者的知識(shí)學(xué)習(xí)都要依靠一種相繼的線性順序進(jìn)行，段落和章句之間必然依照邏輯、銜接和順序來(lái)聯(lián)結(jié)成一體，這是線性文本的特點(diǎn)。

線性文本具有較強(qiáng)的思維邏輯性和層次結(jié)構(gòu)性[12]。與非線性文本相比，避免了讓讀者在閱讀中肆意游蕩。非線性文本中的各子主題[13]內(nèi)容之間相互融合摻雜，文本段落在組織上雜亂無(wú)序、胡亂堆砌、毫無(wú)界限和標(biāo)志之分(結(jié)構(gòu)見(jiàn)圖1(a))。在采用傳統(tǒng)的K-means文本聚類分析時(shí)，隨機(jī)初始化中心點(diǎn)可保證雜亂主題被任意選取到，但是因?yàn)椴淮_定性的存在，會(huì)使得聚類迭代次數(shù)增加或無(wú)窮迭代、文本中心意義的曲解和偏差等。線性文本從始至終是基于一個(gè)主題的，主題一般以抽象概括的語(yǔ)言顯性或隱性地存在于整篇的篇章當(dāng)中[14]，并且以主題為軸心做邏輯導(dǎo)向劃分子主題，實(shí)現(xiàn)文本內(nèi)容的層次劃分。表現(xiàn)層次的完整的單位是段落，文本最終形成一棵文本的結(jié)構(gòu)樹(shù)[15](結(jié)構(gòu)見(jiàn)圖1(b))。文中把線性文本的邏輯結(jié)構(gòu)表示為：文本={文本主題，層次主題，段落主題，句子，主題詞}。

圖1 線性與非線性文本對(duì)比

在對(duì)線性文本進(jìn)行結(jié)構(gòu)分析時(shí)，其有序化的組織特性，決定了K-means聚類分析的有序性。文中基于一篇線性文本，對(duì)其內(nèi)容進(jìn)行K-means劃分。具體定義如下：設(shè)文本d具有個(gè)n自然段，k個(gè)子主題(也是k個(gè)內(nèi)容層次，認(rèn)為內(nèi)容層次是依據(jù)子主題進(jìn)行的劃分)，用H表示劃分的文本內(nèi)容，P表示自然段。

定義1：待分析文本d。

d={P1,P2,…,Pn}

定義2：文本聚類分析后的內(nèi)容劃分[14]。

d={H1,H2,…,Hk}={Pi1…Pi2-1}{Pi2…Pi3-1}…{Pik…Pik+1-1}

其中，i1=1≤i2-1≤…≤ik≤ik+1-1=n(為方便以后表示，d=P1,P2,…,Pn簡(jiǎn)記為1,2,…,n)。

而在文本邏輯結(jié)構(gòu)中更加強(qiáng)調(diào)的是文本所包含的思想內(nèi)容(內(nèi)容劃分)，段落單元是該段落的中心思想，作為文本結(jié)構(gòu)樹(shù)的葉子節(jié)點(diǎn)，段落間在表現(xiàn)主題時(shí)用詞上會(huì)存在差異，也就支撐了段落中心思想的聚集程度。線性文本的有序聚類就是尋找一種分法使k個(gè)內(nèi)容層次內(nèi)的差異盡可能小，而層次間的差異盡可能大。

1.2 線性文本的空間向量模型

為了讓計(jì)算機(jī)能對(duì)文本進(jìn)行操作，采用向量空間模型(VSM)對(duì)文本進(jìn)行表示[16-17]。其基本思想是：將文本中不同的詞語(yǔ)(一個(gè)詞語(yǔ)是一個(gè)維度)，按照它們的重要程度，賦予不同權(quán)重[17]。最后文檔集合D中的任一文本dk都表示成向量形式：dk=(Wk1,Wk2,…,Wkh)，其中Wkg是文本dk中第g個(gè)詞語(yǔ)的權(quán)重，h是D的維度，也稱文本向量的基數(shù)[18]。那么，針對(duì)線性文本有：

定義3：設(shè)文本d的特征項(xiàng)集為T(mén)={t1,t2,…,tm}(為了方便表示，亦可記為1，2，…，m)。則設(shè)Pi={Wi1,Wi2,…,Wim}為第i段的特征向量[19]。其中Wiq是特征項(xiàng)tq(q∈[1,m])在第i段中的權(quán)重，特征項(xiàng)計(jì)算的是詞語(yǔ)的權(quán)重，形成如下文本空間矩陣[11]：

在該模型中，使用TF-IDF作為特征詞權(quán)重的度量[16-17]。

Wkq=TFq×log(N/DFq)

(1)

計(jì)算TF(term frequency)，有不同的歸一化方式：

(2)

(3)

其中，sum(doc_length)為文本總詞頻；max(tfd)為文本d中的最大詞頻，文中選用的是單個(gè)段落的總詞頻；n為自然段落總數(shù)；DFq為包含詞語(yǔ)q的段落總數(shù)目。

1.3 K-means聚類算法的不足

K-means是一種基于迭代思想的聚類算法，從v篇預(yù)處理的文本集合D={d1,d2,…,dv}中選取k個(gè)初始簇中心，并依據(jù)相似程度將文本劃分到最相似的簇中，最終形成k個(gè)簇的集合C={c1,c2,…,ck}。具體算法的實(shí)現(xiàn)步驟如下[20]：

(5)輸出最終簇集合C*。

傳統(tǒng)的K-means算法在處理線性文本時(shí)，采取隨機(jī)挑選中心點(diǎn)并不斷迭代的聚類方式，中心點(diǎn)的不確定性較大，在選擇不當(dāng)?shù)那闆r下造成迭代次數(shù)增加、運(yùn)算時(shí)間加長(zhǎng)[21]。例如：初始化中心點(diǎn)時(shí)，在本屬于同一簇的文本中選取多個(gè)中心點(diǎn)，以及忽略線性文本具有的上下文內(nèi)容劃分的清晰界限，在中心點(diǎn)選取上不均勻，使得聚類中心主題的偏移，影響聚類最終結(jié)果；同一個(gè)文本到多個(gè)中心點(diǎn)距離相等以及孤立點(diǎn)時(shí)，會(huì)干擾文本的聚類效果，最終無(wú)法準(zhǔn)確歸類(見(jiàn)表1)。因此，急需改進(jìn)中心點(diǎn)選取算法及處理等距點(diǎn)現(xiàn)象的歸類方式。

表1 文本到中心點(diǎn)距離對(duì)比

2 隨機(jī)均勻初始化中心算法

針對(duì)線性文本特性采取均勻初始化中心點(diǎn)的方式，可以精確地確定主題范圍。因?yàn)榫€性文本的段落表意明確、集中，含有豐富的語(yǔ)義，在篇章當(dāng)中段落間會(huì)存在并列、順承等一些線性特征，也就使得表現(xiàn)主題內(nèi)容的各子主題之間線性排列。

具體采用的隨機(jī)均勻初始點(diǎn)算法(如圖2所示)如下：

設(shè)具有n個(gè)自然段的文章d={P1,P2,…,Pn}，P表示段落，共有n個(gè)自然段落，聚類數(shù)目為k。

為使聚類結(jié)果有意義(過(guò)大或過(guò)小的k值都會(huì)影響聚類結(jié)果)，在選定k值時(shí)，默認(rèn)取值范圍是[Kmin,Kmax]，其中Kmin=2，Kmax=sqrt(n)[22]。

一篇線性文本W(wǎng)可劃分成具有k個(gè)子主題的簇集C，k個(gè)主題的內(nèi)容在段落形式上呈線性排列，則選取初始化中心點(diǎn)也呈線性排列。其中，段落均勻間隔為dis=(n/k)。

(1)為了保證隨機(jī)選取的中心點(diǎn)有意義，隨機(jī)選擇的第一個(gè)中心點(diǎn)為Px(x∈[1,dis])。

(2)根據(jù)Px及dis獲取其他中心點(diǎn)p=Px+r*dis(r∈[1,k-1])。

(3)形成初始點(diǎn)簇成員集Cstart={Px,p}。

圖2 隨機(jī)均勻初始化中心點(diǎn)

文本中，各子主題間為了突出各自內(nèi)容，相互之間相似程度較小，從而在整篇文章上呈現(xiàn)主題間的并列或遞進(jìn)等線性排列特征。同時(shí)為避免文章冗余，主題內(nèi)容的規(guī)模分布上多呈現(xiàn)出均勻分布特性。根據(jù)這種均勻特性，采用隨機(jī)均勻初始中心點(diǎn)，可以更好地保證初始點(diǎn)間的相似度小。并且，該算法可使中心點(diǎn)均勻地分布到各個(gè)子主題內(nèi)容中，避免隨機(jī)性太大造成的初始點(diǎn)過(guò)于集中與分散的情況，有利于相似內(nèi)容最快歸類，提高聚類效果與速度。

3 等距點(diǎn)歸類法

通過(guò)前面的模型，得到隨機(jī)均勻選取初始點(diǎn)的K-means算法，但該算法在迭代時(shí)需要解決文本段落歸類的問(wèn)題。實(shí)驗(yàn)中發(fā)現(xiàn)，由于篇章內(nèi)容少這個(gè)特性，使得對(duì)段落聚類時(shí)，每個(gè)段落向量有可能與其他內(nèi)容都不相似或與多個(gè)簇的中心相似度相等，將這樣的段落稱為“等距點(diǎn)”，等距點(diǎn)可能即使多次迭代，仍不能將其劃分到相近的類中。為解決該問(wèn)題，提出如下歸類處理方法。

定義4：簇的平均值。

(4)

其中，h為文本內(nèi)容層次，ih屬于文本內(nèi)容h的一個(gè)自然段落。

該公式用于計(jì)算任意簇中所有自然段落空間向量坐標(biāo)的平均值，計(jì)算結(jié)果作為簇更新后的中心點(diǎn)。

定義5：最大迭代次數(shù)max=ε。

(1)計(jì)算非中心點(diǎn)pi(i≤(n-k))到簇集Cstart即(Cstart,pi)之間的相似度sim(pi,Cstart)，選取最大相似度的簇對(duì)sim(pi,Cz)(z∈{1,2,…,k})，將pi,Cz合并成新簇，Cnew=pi∪Cz；當(dāng)段落到多個(gè)中心點(diǎn)距離相等時(shí)，默認(rèn)先不進(jìn)行歸簇(增加一次迭代)。

定義6：計(jì)算任意兩個(gè)段落之間的相似度-夾角余弦距離[19,23]。

sim(pi,pe(pe∈Cstart))=

(5)

(2)計(jì)算新簇的平均值mean(Cnew)，從而構(gòu)成Cnew={Cnew1,Cnew2,…,Ck}。

(3)判斷Cnew?=Cstart，若相等或者t=ε，執(zhí)行步驟4，否則，進(jìn)行賦值：Cstart=Cnew，t=t+1。然后跳轉(zhuǎn)到步驟1。

(4)判斷d={p1,p2,…,pn}都合并，未合并的，將其單獨(dú)并為一類Ck+1。

(5)輸出聚類結(jié)果。

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

將改進(jìn)的K-means算法聚類結(jié)果進(jìn)行評(píng)價(jià)研究的過(guò)程稱為聚類有效性分析(cluster validity)。聚類有效性分析一般分為外部標(biāo)準(zhǔn)評(píng)價(jià)和內(nèi)部標(biāo)準(zhǔn)評(píng)價(jià)[24]。外部標(biāo)準(zhǔn)評(píng)價(jià)(external criteria appraisal)，用于標(biāo)定的聚類結(jié)果集，采用相應(yīng)的評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)聚類質(zhì)量。內(nèi)部標(biāo)準(zhǔn)評(píng)價(jià)(internal criteria appraisal)，直接評(píng)價(jià)聚類算法的目標(biāo)函數(shù)值，由該標(biāo)準(zhǔn)衍生出來(lái)的評(píng)價(jià)指標(biāo)稱為基于目標(biāo)函數(shù)的指標(biāo)[24]。

為驗(yàn)證該算法的有效性，以《人民日?qǐng)?bào)》語(yǔ)料中的整篇文檔作為實(shí)驗(yàn)文本，選取7個(gè)類別共8篇，每篇的段落數(shù)如表2所示：

基于內(nèi)部標(biāo)準(zhǔn)評(píng)價(jià)，采用類內(nèi)類間相似性度量函數(shù)[25]，對(duì)聚類質(zhì)量進(jìn)行評(píng)判。

具體計(jì)算公式如下：

(6)

其中，d(Xi,Xj)為文本之間的余弦相似值。該值越大，文本的相似性越高，反之，相似性越低。

實(shí)驗(yàn)結(jié)果如表3所示。

表3 聚類實(shí)驗(yàn)效果

圖3 相似度對(duì)比

由表3可以看出，當(dāng)未出現(xiàn)孤立點(diǎn)及文本段落到多個(gè)中心點(diǎn)距離相等時(shí)，改進(jìn)算法降低了聚類迭代次數(shù)，縮短了聚類時(shí)間。相反的情況下，采取最大迭代限制并進(jìn)行優(yōu)化歸類，提高了聚類結(jié)果的準(zhǔn)確度。如圖3的實(shí)驗(yàn)結(jié)果可以看出，傳統(tǒng)K-means聚類算法類間相似度大于改進(jìn)之后的算法結(jié)果，說(shuō)明傳統(tǒng)算法在簇間區(qū)分上不如文中算法的簇間區(qū)分性好，并且改進(jìn)算法很大程度上降低了文本的耦合性[26]；在類內(nèi)相似性上，傳統(tǒng)算法類內(nèi)相似性小于改進(jìn)之后的計(jì)算結(jié)果，說(shuō)明簇內(nèi)文本之間的緊湊程度要劣于文中算法。

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

針對(duì)組織有順序的線性文本，考慮文本結(jié)構(gòu)化特性，對(duì)傳統(tǒng)K-means聚類算法在內(nèi)容聚類上的不足進(jìn)行改進(jìn)，提出一種新的中心點(diǎn)確定方法—隨機(jī)均勻選點(diǎn)；基于文本分布和迭代次數(shù)的等距點(diǎn)歸類方法，構(gòu)造了一種基于線性特征的自動(dòng)文本內(nèi)容分析算法，對(duì)深入理解文本、挖掘文本中的主題和有用信息，具有重要的意義。實(shí)驗(yàn)結(jié)果表明，該算法提高了線性文本的聚類效率，在形成以子主題為中心的簇集分類上優(yōu)于傳統(tǒng)的K-means聚類算法。下一步將在此基礎(chǔ)上，依據(jù)文本的語(yǔ)義特性、相似度等特征自動(dòng)確定k值，以期達(dá)到更好的聚類效果。