基于高頻詞匯的英文文本可視化

收稿日期：2011－06－25

〔摘要〕為探索高頻詞匯間上下文關系的遠近，本文研究了一種基于英文文本中高頻詞匯的可視化算法流程，并進行了可視化實現。我們首先用統計算法從英文文本中抽取出高頻詞匯及詞匯間的上下文，然后定義了3種詞匯間的連接方式，計算出有上下文關系的詞匯間的關系度，并通過k-means算法對詞匯間的關系度進行聚類，以體現出詞匯間關系的遠近，最后利用放射狀樹布局對聚類結果進行可視化。通過這種可視化形式，我們能夠快速理解英文文本的內容。

〔關鍵詞〕文本可視化；高頻詞匯；k-means聚類算法；放射狀樹布局

DOI：10．3969／j．issn．1008－0821．2011．08．006

〔中圖分類號〕TP391.43 〔文獻標識碼〕B 〔文章編號〕1008－0821（2011）08－0021－04

Visualization Based on High-frequency Words for English Text

Liu Chunjiang Yang Shihan Yang Ning

（Chengdu Branch of the National Science Library，CAS，Chengdu 610041，China）

〔Abstract〕Targeting at exploring whether high-frequency words context relations are close or distant，this paper studied on the algorithmic process of a kind of visual form based on high-frequency words in English texts and achieves this visual form.This paper firstly used statistic algorithm to extract high-frequency words and their context，then defined three kinds of context relations among words，compute values of relations among words that have context，cluster the values set through k-means cluster algorithm to show whether words context relations are close or distant.Finally，visualized these clustering results by means of radial layout graph.Through this visual form，can quickly understand the contents of the English text.

〔Key words〕text visualization;high-frequency words;k-means algorithm;radial layout graph

文本是一種最普通的信息載體，人們有各種形式的閱讀方式，對這些閱讀方式按照閱讀目的不同進行劃分，可以分成3種，包括事實性閱讀、理解性閱讀以及批判性閱讀［1］。但是不管閱讀目的如何不同，隨之而來 的閱讀方式有何差異，文本閱讀基本上都是采用逐句閱讀，聯系上下文的方式來進行。一般來說，這種閱讀方法耗時較多，而通過對文本進行可視化呈現的方式能夠增強我們對文本內容的理解，提高理解的速度和深度。在已有的可視化項目中，有的項目側重于對整個文本進行可視化，例如TextArc［2］；有的項目側重于對文本上下文檢索的結果進行可視化，例如Word Tree［3］；有的項目側重于對文本中抽象出來的概念進行可視化，例如Themeriver［4］。這些可視化項目對我們理解文本具有重要的幫助作用，但是目前專門針對詞匯間關系的可視化研究相對較少，而文本中重要詞匯的關系能更好的體現文本內容所呈現的意義。

根據G.K.Zipf的發現，在大量英文文本中對單詞進行詞頻統計，并從最高頻到最低頻進行排序，那么每個單詞出現的頻率與它的名次的常數次冪存在簡單的反比關系［5］。

在本文中，高頻詞匯指的是英文文本中除停用詞以外出現頻率較高的詞匯，這些高頻詞匯本身具有相對固定的含義，它們之間的連接關系對于我們分析文本的主旨，探索高頻詞匯在文本中的用途，尋找詞匯間的搭配方式具有重要的意義。

1 詞匯間的關系模型

在進行可視化之前，首先需要建立高頻詞匯間的關系模型。這種關系模型可以看作是一種節點關系模型。節點指的是文本中的高頻詞匯，關系指的是文本中這些詞匯的上下文關系。我們通過3個步驟來建立這個關系模型，首先從文本中提取出高頻詞匯，然后定義了3種詞匯間的連接方式，最后計算出詞匯間的關系度，并利用k-means算法對關系度進行聚類來建立這個模型。

1.1 高頻詞的提取

高頻詞的提取過程包括4個階段：文本的預處理，停用詞處理，詞干抽取，高頻詞提取。

1.1.1 文本的預處理

英文文本一般是由單詞、數字、標點符號等組成，因此在文本的預處理階段，需要去除單詞以外的文本其它組成部分，最后形成由單詞和空格組成的文本。

1.1.2 停用詞處理

停用詞指的是在對文本或數據進行自然語言處理前后被過濾掉的詞匯［6］。在英文文本中，停用詞是一些經常出現但是本身無意義或者意義比較抽象的詞，英文中典型的停用詞包括the、in、on等。我們進行停用詞處理的時候采用的是一個通用的停用詞列表［7］，該列表包括429個停用詞，基本上涵蓋了英文中使用頻繁的停用詞。

1.1.3 詞干抽取

詞干是一個單詞的主要組成部分，我們通常需要在不同的上下文中使用詞干的不同變形。例如對于詞干fish，它的動名詞變形是fishing，過去分詞變形是fished。但是在進行詞頻統計的時候，對于已變形的詞匯，我們應該先抽取出其詞干，然后和未變形的詞匯一起統計。

在這個過程中，我們采用了Porter詞干抽取算法［8］對已變形的詞匯進行詞干抽取。

1.1.4 高頻詞提取

經過前面3個步驟的處理之后，文本變成了由空格分隔的詞匯集合，例如：“Static visualizations have long been used to support storytelling”經過處理之后，變成了“static visualization support storytell”。經過該詞匯集合中的詞頻統計，我們從中提取了出現頻率最高的20個詞匯。相關算法如下所示：

初始化HashMap；

for each 處理后的文本T中的詞匯w do

if HashMap的key中包含w；

then 在HashMap中把key為w的對應value值加1；

else 把w放入HashMap中；

end for

對HashMap按照value值進行排序；

從排序結果中取出value值最大的前20個詞匯。

1.2 詞匯間的連接方式

在英文文本中，兩個詞匯之間的連接方式有3種：一種是直接相連，我們把這種緊挨著的連接方式定義為方式一；第二種是通過連接詞相連，我們把這種連接方式定義為方式二；不屬于前兩種的情況歸屬于第三種，我們把這種連接方式定義為方式三。在文本中，要確定詞匯間的連接方式是否屬于方式一比較容易，因此問題的關鍵在于確定詞匯間的連接方式是否屬于方式二。

英語連詞從結構上區分，主要有并列連詞和從屬連詞兩大類，其中并列連詞連接2個或2個以上句法地位同等重要的詞匯或分句，從屬連詞也被稱為主從連詞，在句中用于引導1個從屬子句。在判斷詞匯間的連接方式是否屬于方式二的過程中，我們使用了一定數量的連詞。我們使用的并列連詞有7個，從屬連詞有18個。

如上所述，兩個詞匯之間通常有3種連接方式，因此當我們在詞匯之間設置一定的間隔之后，我們就能夠找出兩個詞匯及其上下文的集合，然后就可以把集合按照不同的連接方式進行歸類。我們從示例論文［9］中選取了一些文本內容作為我們的測試文本，我們把詞匯之間間隔的單詞數目設置為1個以內，通過查找，最終找到了182個上下文。

1.3 詞匯間關系度的計算與聚類

1.3.1 詞匯間關系度的計算

關系度是通過定量的方式來描述詞匯間關系遠近的值。通過關系度，可以判斷詞匯間的連接關系是否緊密、一般或者疏遠。我們首先把前面定義的3種連接方式，分別定量地置為3（方式一）、2（方式二）、1（方式三），對于任意兩個詞匯間的不同上下文連接方式，計算出其算術平均值。

文本中data和story通過方式一連接的上下文數量為4個，通過方式二連接的上下文數量為4個，通過方式三連接的上下文數量為0個，根據前面的定量設值，得出data和story之間的關系度為2.5。

1.3.2 詞匯間關系度的聚類

聚類的過程就是把一個數據對象集中的數據分組成多個類的過程，同時使得在同一個類內對象之間具有較高的相似度，不同類之間的對象差別較大。在聚類算法中，k-means聚類算法［10］是一個比較經典的算法，該算法具有對大型數據集進行高效分類的優點，其計算復雜度為線性，特別適用于對數值型數據聚類，因此我們采用該算法對詞匯間的關系度進行聚類。

該算法的核心思想是找出K個聚類中心，使得聚類中所有對象到所屬聚類中心值的距離最短。我們把計算出的所有詞匯間的關系度當做一個數據對象集，從中指定3個數據對象為聚類中心，然后對該數據對象集中的數據進行聚類對于文本T，其中提取出高頻詞匯集合W，假設詞匯間的關系模型C，構造C的具體算法如下：

for each W中的詞匯w1 do

for each W中的詞匯w2 do

if w1和w2在同一個上下文中，并且詞匯間隔小于等于1；

then 在C中存儲詞匯w1及其在文本中出現的次數、詞匯w2及其在文本中出現的次數、上下文、詞匯間隔、連接方式等信息；

end for

end for for each W中的詞匯w1 do

for each W中的詞匯w2 do

for each C do

if C中存儲有詞匯w1和詞匯w2的信息；

then從C中取出w1和w2的信息，在C1中存儲w1和w2的連接方式r、上下文連接次數sum；

end for

for each C1 do

計算出w1和w2的關系度并放到數據對象集S；

end for

從S中指定3個對象為聚類中心，取出所有數據對象的平均值，計算平均值與聚類中心值的均方差距離，根據計算結果的最小值對數據對象進行聚類劃分，如果所有數據的平均值到所屬的聚類中心值的距離最短，那么返回聚類結果，否則從步驟2重新開始循環，直到聚類中所有對象到所屬聚類中心值的距離最短為止；

for each C do

根據聚類結果，在詞匯間的關系模型中設置關系類型；

end for

end for

end for

2 可視化設計與實現

可視化實現使用的是Java，結合開源的可視化開發包Prefuse［11］，下面分別從可視化設計和交互式實現兩個方面來介紹。

2.1 可視化設計

我們采用的是放射狀樹布局［12］進行可視化呈現，放射狀樹布局結合了放射狀布局和樹布局的特點，把樹中不同層次的節點按照圓半徑的長短通過放射狀的布局來顯示，層次越低離中心越近，層次越高離中心越遠。以詞匯story為中心節點，其它詞匯按照與story的上下文關系分布在中心節點的周圍，與story有上下文關系的詞匯離中心越近，與story無上下文關系的詞匯離中心越遠。

可視化圖形中節點的大小按照詞頻的高低進行顯示。由于有的文本所含的詞匯數量多，有的文本所含的詞匯數量少，要使得節點大小體現詞頻的高低，就需要對不同數量的文本設置不同的閾值。為了避免這種情況的發生，我們把所有的20個節點按照詞頻從多到少分成了3個層次，其中前3個詞匯屬于第1層次，在可視化圖形中用大號字體顯示；接下來的7個詞匯屬于第2層次，在可視化圖形中用中號字體顯示；最后的10個詞匯屬于第3層次，在可視化圖形中用小號字體顯示。

可視化圖形中節點之間通過線條進行連接，我們定義了3種形式的線條，分別用粗線條表示詞匯之間的連接關系緊密，細線條表示詞匯之間的連接關系一般，虛線條表示詞匯之間的連接關系疏遠。

2.2 交互式實現

為了能夠交互式查看不同節點的可視化圖形以及相應的上下文內容，我們結合采用了文字編輯框和放射狀樹布局的動態探索技術［13］。文字編輯框中主要通過副文本顯示了詞匯間的上下文信息；放射狀樹布局的動態探索技術使得整個布局可以隨著中心節點的變化而動態轉換。因此我們把整個可視化區域可以分成左右兩個部分，左邊區域的文字編輯框除了顯示了中心節點和圖中其它節點之間的上下文，還可以根據用戶與放射狀樹布局的交互，顯示中心節點和圖中其它節點之間有上下文關系的數量總和；右邊區域主要顯示了可以動態轉換的放射狀樹布局。當story被選擇的時候，與story有上下文關系的節點分別顯示在story的四周，它們之間的連接線條被高亮顯示，可視化圖形的上方顯示了story在文中的出現次數為62，左邊區域顯示了story和圖中其它節點的上下文關系數量為22，以及story和圖中其它節點的上下文內容。

3 結 論

本文基于英文文本中的高頻詞匯，實現了一種體現高頻詞匯間上下文關系遠近的可視化形式。針對不同長短的英文文本，通過這種可視化形式，我們能夠更快速更準確地理解文本內容。但由于抽取出的高頻詞中漏掉了不少本身在文本中具有重要意義，但是詞頻較低的詞，因此在今后的工作中，我們將繼續研究文本中的信息抽取，使得這種可視化形式在幫助理解文本的過程中更加有效。

參考文獻

［1］Dan Kurland.Three Ways to Read and Discuss Texts［EB／OL］.http:∥www.criticalreading.com/waystoread.htm，2010-09-10.

［2］W.B.Paley.TextArc:Showing Word Frequency and Distribution in Text［C］.Proceedings of IEEE Symposium on Information Visualization，Poster Compendium，2002.

［3］M.Wattenberg and F.B.Viégas.The word tree， an interactive visual concordance［J］.IEEE Trans.on Visualization and Computer Graphics，2008，14(6)：1221－1228.

［4］L.Nowell S.Havre，B.Hetzler and P.Whitney.Themeriver:Visualizing thematic changes in large document collections［J］.Transactions on Visualization and Computer Graphics，2001：9-20.

［5］G.K.Zipf.Human Behavior and the Principle of Least Effort［M］.Cambridge，MA:Addison-Wesley，1949.

［6］Stop words［EB／OL］.http:∥en.wikipedia.org/wiki/Stopwords，2010-09-17.

［7］Stop Word List［EB／OL］.http:∥www.lextek.com/manuals/onix/stopwords1.html，2010-09-17.

［8］M.F.Porter.An algorithm for suffix stripping［J］.Program:electronic library and information systems，14（3）：130－137.

［9］Edward Segel and Jeffrey Heer.Narrative Visualization:Telling Stories with Data［J］.IEEE Transactions on Visualization and Computer Graphics，2010，16(6):1139-1148.

［10］k-means clustering［EB／OL］.http:∥en.wikipedia.org/wiki/K-meansclustering，2010-10-20.

［11］Prefuse［EB／OL］.http:∥www.prefuse.org，2010-10-03.

［12］Di Battista，G.，Eades，P.，Tamassia，R.，and Tollis，I.G..Graph Drawing:Algorithms for the Visualization of Graphs.Upper［M］.Saddle River，NJ:Prentice Hall，1999.

［13］Yee，K.-P.，D.Fisher，R.Dhamija，and M.A.Hearst.Animated Exploration of Dynamic Graphs with Radial Layout［C］.InfoVis 01，2001：43-50.