基于聚類分析的自動文摘中主題區域劃分方法研究

[摘要]針對在海量數據中，如何有效地自動獲取文摘以提高檢索效率的問題，提出了一種自動文摘中主題區域劃分的方法。該方法對文章段落向量模型進行聚類分析，得到文章的主題結構。這種方法適用于各種風格的文體，能克服文章主題分布自由的問題，準確地劃分出文章主題區域。

[關鍵詞]自動文摘；主題區域劃分；聚類分析

Study of Thematic Area Discovery from Chinese Text Based on Clustering Analysis

(School of Economics and Management， University of Science and Technology Beijing， Beijing 100083， P. R. China)

Abstract: A special method that discovers thematic area from Chinese text is proposed after analyzing how to get summarization effectively in large dataset to improve retrieval efficiency. This method analyzes the vector space model of the paragraphs with clustering method and gets the theme structure of the novel. This method is suitable to all kinds of styles， and is able to divide thematic area effectively.

Key words: automatic summarization， thematic area discovery， clustering analysis

1引言

隨著信息技術的飛速發展，互聯網上充斥著海量的數據。現有檢索技術難以在如此海量的數據里快速有效的檢索出用戶所需的信息資源，其查準率和查全率難以令人滿意。自動文摘技術能在一定程度上緩解這個問題。它是一種通過計算機對文檔內容進行處理，從中選出最能代表文章主旨的語句，將這些語句經過重組修飾后以簡潔的形式表達出來，形成摘要的技術。摘要在一定程度上涵蓋了文章的主要內容，信息比標題豐富又比全文簡練，如果針對摘要進行檢索，可以提高檢索質量、縮短檢索時間，既能比標題檢索查找出更多有效信息，又能剔除在全文檢索時出現的多余信息。用戶通過閱讀摘要能更簡潔準確的了解文章內容，節省瀏覽識別信息的時間。

國外對自動摘要的研究起步較早，1958年IBM公司的Luhn最早提出了自動文摘技術[1]的概念。按照自動文摘方法的不同大致可分為兩類：基于統計的機械性自動文摘和基于意義的理解性文摘。機械性文摘[2]主要使用統計方法獲取文檔的各種信息，如位置信息、頻率統計等，從原文中挑選出最能代表文章主題的句子，組合后形成文章摘要。理解性文摘[3]利用領域知識進行推理判斷，對文章進行句法分析和語義分析，得到文檔的意義表示，在理解文檔內容的基礎上，利用計算機的學習能力生成摘要。基于統計的機械性文摘可以具體分為無篇章結構分析型和基于篇章結構分析型[4]。前者首先計算全文句子的權重，然后依次挑選出權重較高的句子作為摘要句，依次輸出形成文摘。后者先對文章語義結構進行分析，找出文章的主題結構，然后從各個主題中分別抽取句子構成文摘，這樣產生的摘要能全面有效地涵蓋文章的主題內容。

基于篇章結構的文摘技術可分為三個階段：劃分文檔的主題區域結構、從各個主題區域中挑選合適的句子作為主題句、將主題句組合成文摘。本文主要研究的是一種基于聚類的主題區域結構發現方法。

2基于聚類的主題區域結構發現方法

文本的結構由三部分組成：文章的子主題、每個子主題所包含文章的段落以及主題內各段落之間、各個子主題區域之間的相似度。所謂子主題，是介于篇章與段落之間的一個語言單位，每一個子主題都相對獨立的表達或闡述一個相對獨立的意義或話題。文章中的每個子主題可能由一個或多個段落組成，這些段落可能是連續的，在一些寫作風格比較靈活的文檔中也可能是不連續的。

2.1基于聚類主題區域發現方法簡介

眾多研究者提出了不同的主題劃分方法，常見的可歸納為利用頁面信息（標題等）劃分主題區域、利用相似度劃分主題區域、通過句子矩陣奇異化劃分主題區域和通過聚類劃分文章主題區域四種方法。

本文提出的通過聚類劃分文章區域的方法首先需要把文檔表示成計算機能處理的空間向量模型VSM，得到段落或句子向量，然后利用聚類算法對這些向量進行聚類。得到聚類結果后，被聚成一類的段落或句子屬于同一個主題區域，不同的分類代表了不同的主題區域，從而得到了文檔的主題區域劃分。

2.2 構建段落空間向量模型

計算機無法直接理解自然語言語義，需要對文檔進行建模。文檔建模通常有兩種方式：基于統計建模和基于語義建模。基于統計建模主要是利用統計方法獲取文檔特征信息，建立模型；基于語義建模是通過對文檔進行語法和語義分析，建立模型。本文利用統計方法，獲得文本特征信息，在此基礎上通過特定算法得到文檔的特征信息，建立文檔模型，然后利用模型進行文章主題區域發現。

2.2.1空間向量模型

空間向量模型（VSM）由Salton等在20世紀60年代提出，是一個基于統計的文檔表示模型。它把文本表示為特征項和特征權重組成的向量，以一定的特征項（如詞條或段落等）來代表目標文本信息，利用統計手段得到特征項的特征值，兩者結合起來就表示了文本的特征信息。VSM模型的主要思想是：將每一個文檔都映射為由一組規范化正交詞條矢量組成的向量空間中的一個點。對于所有的文檔類和未知文檔，都可以用此空間中的詞條向量（T1，W1，T2，W2，…，Tn，Wn）來表示。其中Ti為特征向量詞條，即特征項；Wi為Ti的權重，即特征項Ti的特征值。為了得到特征值需要構造一個評價函數來表示詞條權重，在計算時一個很大的準則就是權值越大的特征項，要越能夠區別出不同類型的文檔。

從空間向量模型的特點可以看出，要建立目標文本的空間向量模型，首先需要選擇合適的特征項，常用的方法是利用詞、句子或者段落作為特征項，本文采用的是利用詞條作為特征項。提取目標文本中的特征項是一個對文本進行預處理的過程，目前存在很多方法。比如中文分詞技術，就是利用語義分析，對原文本進行詞條切分，除去停用詞、語氣詞等，把原文拆分成若干有實際意義的詞條的文本信息的分詞過程。也可以利用現成的語料庫，通過語料庫中的專業詞條到原文本中進行匹配查找，得到特征項。由于漢語語言的復雜性，中文分詞技術目前還不太成熟，在分詞的準確率和效率上都還有很多問題存在，本文的研究是在基于語料庫的基礎上進行的，認為已經有一個可用的開放式預料庫存在，采用漢語術語的抽取方法對原文檔進行預處理。術語比普通的詞匯更加完整、專業，能承擔更多的語義信息，通過術語抽取能得到更準確的原文檔信息。本文不涉及語料庫形成及更新的研究，把研究建立在已經根據語料庫對文章的術語進行了有效識別的基礎上，把術語作為文檔空間向量模型的特征項，并已經完成對術語特征項在文章中出現頻次的統計，統計出來的頻次信息包括術語特征項在原文中出現的總頻次，原文中包含某一特征項的段落的個數，某一段落包含某一特征項的個數等。

2.2.2 特征值的計算

文本的空間向量模型由兩部分組成，分別是特征項和特征值，在得到文本的特征項后，下一步就是計算特征項的特征值。我們已經利用即成的語料庫得到了文檔術語特征項和特征項的頻次信息，下面就利用算法函數計算特征項的特征值。常用的特征權值計算方法有布爾函數法、平方根函數法、對數函數法、TF*IDF法等。布爾函數法用0和1兩個值來表示一個詞是否出現在一篇文檔中，而沒有考慮詞在文本中的重要程度，平方根函數法、對數函數法只單純考慮了詞在文章中出現的頻次，沒有考慮詞在文本中的分布情況，這都不符合對特征值的要求。通過特征值構建文本空間向量模型并使用向量聚類對文檔進行主題區域發現要求特征值要能夠表現出詞語對原文內容的區分程度，特征值的大小要反映出詞對文檔內容代表程度的強弱，也就是對表現文章主要內容的重要程度，因此本文采用TF*IDF法。

TF*IDF算法包含了兩層含義：TF（Term Frequency）表示詞頻，即詞條在文檔中出現頻率，IDF（Inverse Document Frequency）表示反文檔頻率，是為了糾正單純詞頻統計帶來的不足。

TF*IDF算法的主要思想是：如果一個詞或短語在某一類別中（可能是一篇文章也可能是文章中的某一段）出現的頻率TF高，并且在其他類別中很少出現，也就是反文檔頻率越大，就認為此詞語或者短語具有較好的區分類別的能力，適合用來分類。也就是說，對區別文本最有意義的詞語應該是那些在少量分類中出現的頻率足夠高，而在整個文本集合中其他分類中出現的頻率足夠少的詞語，Salton的信息熵理論也對這種思想做了很好的解釋[5]。對于文檔特征的研究是在詞的基礎上進行，研究的范圍是單片文檔。首先要計算的特征值是詞（也就是特征項）在文中某一段落中的權值。

式中， 為第j個術語特征項在第i個段落中的特征值（權值）； 為第j個術語（特征項）在原文第i段中出現的頻次； 為文檔的段落總數； 為包含術語j的段落個數； 為文檔的特征總數（即術語總數）； 就是特征項的倒排段落頻率，其意義是如果某個特征詞在文章段落中分布越廣泛，其標識某一段落特殊性的效果就越差，利用這個因子可以在一定程度上克服單純依據頻次統計在描述術語段落重要性方面的不足。

但是該式中存在一個不足就是 受文章長度的影響比較大。如果文章很長， 的值會比較大，造成 的值之間比較離散，影響聚類效果。因此對式（2-1）進行了改進。

通過對 的值進行取對數處理，可以保證 時，新的TF因子同樣為0，同時減少 值之間離散程度，有利于后文的聚類運算。

但是TF*IDF也存在明顯的不足，其中一點就是IDF的計算過于簡單，只考慮了特征項的分布范圍，簡單認為分布范圍廣的特征項就不可能同時具有較高的集中度，就不具有高信息含量。如果一個詞在文章中頻繁出現，分布的段落也比較廣泛，可以認為這個詞對于表達文章內容具有重要意義。但根據式（2-1）中的IDF因子，這樣的詞的IDF值會比較小，其相應的特征值也會變小。而事實上這個詞雖然在原文中分布的段落比較廣泛，但可能在很多段落只是偶爾出現，其分布主要還是集中在某一個或幾個段落中，這樣的詞無論對于代表段落內容還是區分段落類別都具有重要的意義，在其分布集中的段落中應該具有較大的權值。為了克服這個不足，本文對式（2-2）再次做了改進，如式（2-3）所示。

式中 為第j個術語特征項在整篇文章中出現的頻次。在式（2-3）中，我們在計算特征項IDF時添加了對詞（特征項）在全文中出現頻次的考慮，這樣就可以在一定程度上表示出特征項在全文分布的重要性，特征項的特征值（權值）計算更合理。

2.2.3 段落的向量表示

對于文本的研究是以詞為基礎，以段落為單位。在已經計算出詞（特征項）的特征值基礎上，段落的向量表示為對于第i個段落Pi，用VPi表示段落向量，則 ，i=1，…，M，M是文檔的段落總數）。在得到所有段落的向量VPi后，對于文檔的空間向量模型構建就已經完成，然后對段落向量進行聚類，進而發現文章的主題區域。

2.3段落聚類與分析

利用構建好的的空間向量模型，假設N維樣本空間的每個樣本點分別對應于文本中的一個段落向量，我們可以把段落聚類問題直觀化為N維樣本空間中的M個樣本點的聚類問題。

兩個段落之間的距離定義為表示段落的兩個向量之間歐氏距離，段落距離的計算如下式（2-4）所示。

式中VPi，VPj表示要計算距離的兩個段落i和j的向量；WPiw為第w個術語特征項在第i段中的特征值；N為段落空間中術語的總個數；所有段落距離的平均值 ， 為所有段落的距離之和。

算法的步驟如下

步驟1：給段落編號，計算每兩個段落距離par1_par2_dis；

步驟2：計算所有段落距離的平均值ave_dis

步驟3：找出未聚類段落中距離最小的兩個段落A、B，令min_dis=parA_parB_dis。如果min_dis＜ *ave_dis，則把段落A、B歸為一類，如果A 或B有任何一個已經屬于已存在的類中，則把段落A、B分別屬于不同的類合為一類，否則新建一個類C_new，C_new中包含段落A、B。

步驟4：重復步驟3，直至min_dis≥ *ave_dis.如果min_dis≥ *ave_dis，則將未分類的段落每個都視為單獨的為一類

步驟5：輸出聚類結果

算法中的 為一個調整參數，調整段落聚類結果的收放程度。

當 時，相當于直接用段落間的最短距離直接與段落平均距離比較；當 時，相當于適當擴大了允許歸為一類的段落之間的距離， 的取值越大，類內的段落分布可能越相對稀疏；當 時，相當于縮小了允許歸為一類的段落之間的距離， 的取值越小，類內的段落分布可能越相對緊湊。

當被聚為一類的段落過于稀疏時，聚類效果可能不明顯，歸為同一類別的段落內聚度不夠，相似性變小；當被聚為一類的段落過于緊湊時，可能會使生成的類的數量過于多，類之間的差別度不夠。因此 的取值對段落的聚類效果會造成很大影響，在實踐中選擇一個合適的 值是一個應該被重視的問題。

根據聚類的輸出結果，可以把每一類所包含的段落視為一個子主題區域，這些段落描述的內容相近，并且可以認為包含段落越多、篇幅越長的子主題區域在文章中占有更重要的地位，也就是這樣的子主題區域所描述的內容越重要。這樣就完成了對文章的主題區域劃分。

2.4 段落聚類算例

本節選用了一小段文章對本章中的主題區域劃分算法加以說明。選取的術語集合 = {信息，摘要，自動摘要，主題，段落，相似性}，段落數M=5。

2.4.1 構建段落空間向量模型

首先統計術語特征項在文中出現的次數和出現的段落數，統計結果如下表1所示。

此處以第一個術語特征項“信息”為例，其中T11表示第一個術語“信息”在第一段中出現的次數，M1表示全文中包含術語“信息”段落個數。

2.4.2 對段落進行聚類與分析

利用前文4.3節中提到的聚類算法，我們嘗試對段落進行了聚類，

計算每兩個段落之間的距離得到如下數據：par1_par2_dis = 2.206271，par1_par3_dis = 2.303955，par1_par4_dis = 1.586165，par1_par5_dis = 1.952739，par2_par3_dis = 0.854734，par2_par4_dis = 2.388828，par2_par5_dis = 2.618612，par3_par4_dis = 2.496440，par3_par5_dis = 2.767200，par4_par5_dis = 0.559317，

所有段落兩兩之間距離之和為 ，(i = 1， …， 6， j = 1， …， 6， i≠j )，

計算total_dis = 19.734260，

（1）下面開始聚類過程，令 =1。

1）首先找到距離最小的兩個段落

根據計算出來的距離，最小的兩個段落為段4和段5，且 ，因此段4與段5被歸為一類C1。

2）重復步驟1），找到未聚類段落中距離最小的兩個段落是段2和段3，且 ，所以認為段2與段3屬于一類。因為段2與段3都還不屬于任何類，因此新建類C2，C2中包含段2、段3。

3）重復步驟1），此時未聚類段落中，距離最小的兩個段落是段1和段4，且 ，因為段4已經屬于類C1，因此段1也被歸為類C1。

4）重復步驟1），此時未聚類段落中，距離最小的兩個段落是段1和段5，且 ，因為類C1中已經包含段1與段5，所以此處無需進行任何操作。

5）重復步驟1），2），此時未聚類段落中，距離最小的兩個段落是段1和段2， ，聚類結束。

此次聚類共把段落分成兩類：C1、C2。C1中包含段落1、4、5，C2中包含段落2、3。

（2）下面我們調整α值進行重新聚類，令 =0.8，則

步驟1），2）與前面相同。

3）此時未聚類段落中，距離最小的兩個段落是段落1和段落4，但是 ，因此聚類結束，剩余的段落1被認為是單獨的一類，新建類C3，C3中只包含段落1。

當 =1的時候，類的半徑比較大，段落1被歸為段落4、5一類，但當將 值被調小的時候，相當于縮小了類的直徑，所以段落1單獨形成一類，不與段落4、5歸為一類。

3 總結

計算機網絡迅猛發展的今天，自動文摘技術的作用將會受到越來越多的關注，而通過劃分主題區域提取摘要是目前得到高質量摘要的有效方法。使用基于主題的 聚類方法對文檔進行主題劃分是一個可行并且有效的方法，可迅速劃分出文章整體結構，為進一步提取文章摘要打下良好的基礎。本文提出的方法在還需進一步改進，如何進一步提高聚類算法的效率，能否在對術語特征值的計算上考慮到用戶的主觀因素，這些也是今后要繼續研究的問題。

參考文獻

[1] Weil Ben H．Standards for writing abstracts[J]．Journal of the American Society for Information Science， 1970， 21(5): 351-357．http://web.ebscohost.com/ehost/detail

[2] 譚翀，陳躍新．自動摘要方法綜述[J]．情報學報，2008，27（1）：62-66．

[3] 王志琪，王永成，劉傳漢．論自動文摘及其分類[J]．情報學報，2005，24（2）：214-221．

[4] Luhn H P．The automatic creation of literature abstract [J]．IBM Journal of Research and Development， 1958， 2(2): 159-165．

[5] 龔靜，田小梅．基于文本表示的特征項權值計算方法[J]．電腦開發與應用，2008，21（1）：46-48．

作者簡介

魏桂英（1969-），女，河北承德人，北京科技大學經濟管理學院講師，主要研究方向：數據挖掘.