面向線性文本的K-means聚類算法研究

文必龍，李 菲，馬 強

(東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318)

0 引 言

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

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

1 線性文本

1.1 定 義

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

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

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

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

定義1：待分析文本d。

d={P1,P2,…,Pn}

定義2：文本聚類分析后的內容劃分[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)。

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

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

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

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

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

Wkq=TFq×log(N/DFq)

(1)

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

(2)

(3)

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

1.3 K-means聚類算法的不足

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

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

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

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

2 隨機均勻初始化中心算法

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

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

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

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

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

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

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

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

圖2 隨機均勻初始化中心點

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

3 等距點歸類法

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

定義4：簇的平均值。

(4)

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

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

定義5：最大迭代次數max=ε。

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

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

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

(5)

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

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

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

(5)輸出聚類結果。

4 實驗結果分析

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

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

基于內部標準評價，采用類內類間相似性度量函數[25]，對聚類質量進行評判。

具體計算公式如下：

(6)

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

實驗結果如表3所示。

表3 聚類實驗效果

圖3 相似度對比

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

5 結束語

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