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

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

0 引 言

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

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

1 線性文本

1.1 定 義

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

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

圖1 線性與非線性文本對比

在對線性文本進(jìn)行結(jié)構(gòu)分析時，其有序化的組織特性，決定了K-means聚類分析的有序性。文中基于一篇線性文本，對其內(nèi)容進(jìn)行K-means劃分。具體定義如下：設(shè)文本d具有個n自然段，k個子主題(也是k個內(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簡記為1,2,…,n)。

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

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

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

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

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

Wkq=TFq×log(N/DFq)

(1)

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

(2)

(3)

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

1.3 K-means聚類算法的不足

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

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

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

表1 文本到中心點距離對比

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

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

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

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

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

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

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

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

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

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

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

3 等距點歸類法

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

定義4：簇的平均值。

(4)

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

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

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

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

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

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

(5)

(2)計算新簇的平均值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}都合并，未合并的，將其單獨并為一類Ck+1。

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

4 實驗結(jié)果分析

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

為驗證該算法的有效性，以《人民日報》語料中的整篇文檔作為實驗文本，選取7個類別共8篇，每篇的段落數(shù)如表2所示：

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

具體計算公式如下：

(6)

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

實驗結(jié)果如表3所示。

表3 聚類實驗效果

圖3 相似度對比

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

5 結(jié)束語

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