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

收稿日期：2011－06－25

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

〔關(guān)鍵詞〕文本可視化；高頻詞匯；k-means聚類算法；放射狀樹(shù)布局

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

〔中圖分類號(hào)〕TP391.43 〔文獻(xiàn)標(biāo)識(shí)碼〕B 〔文章編號(hào)〕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

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

根據(jù)G.K.Zipf的發(fā)現(xiàn)，在大量英文文本中對(duì)單詞進(jìn)行詞頻統(tǒng)計(jì)，并從最高頻到最低頻進(jìn)行排序，那么每個(gè)單詞出現(xiàn)的頻率與它的名次的常數(shù)次冪存在簡(jiǎn)單的反比關(guān)系［5］。

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

1 詞匯間的關(guān)系模型

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

1.1 高頻詞的提取

高頻詞的提取過(guò)程包括4個(gè)階段：文本的預(yù)處理，停用詞處理，詞干抽取，高頻詞提取。

1.1.1 文本的預(yù)處理

英文文本一般是由單詞、數(shù)字、標(biāo)點(diǎn)符號(hào)等組成，因此在文本的預(yù)處理階段，需要去除單詞以外的文本其它組成部分，最后形成由單詞和空格組成的文本。

1.1.2 停用詞處理

停用詞指的是在對(duì)文本或數(shù)據(jù)進(jìn)行自然語(yǔ)言處理前后被過(guò)濾掉的詞匯［6］。在英文文本中，停用詞是一些經(jīng)常出現(xiàn)但是本身無(wú)意義或者意義比較抽象的詞，英文中典型的停用詞包括the、in、on等。我們進(jìn)行停用詞處理的時(shí)候采用的是一個(gè)通用的停用詞列表［7］，該列表包括429個(gè)停用詞，基本上涵蓋了英文中使用頻繁的停用詞。

1.1.3 詞干抽取

詞干是一個(gè)單詞的主要組成部分，我們通常需要在不同的上下文中使用詞干的不同變形。例如對(duì)于詞干fish，它的動(dòng)名詞變形是fishing，過(guò)去分詞變形是fished。但是在進(jìn)行詞頻統(tǒng)計(jì)的時(shí)候，對(duì)于已變形的詞匯，我們應(yīng)該先抽取出其詞干，然后和未變形的詞匯一起統(tǒng)計(jì)。

在這個(gè)過(guò)程中，我們采用了Porter詞干抽取算法［8］對(duì)已變形的詞匯進(jìn)行詞干抽取。

1.1.4 高頻詞提取

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

初始化HashMap；

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

if HashMap的key中包含w；

then 在HashMap中把key為w的對(duì)應(yīng)value值加1；

else 把w放入HashMap中；

end for

對(duì)HashMap按照value值進(jìn)行排序；

從排序結(jié)果中取出value值最大的前20個(gè)詞匯。

1.2 詞匯間的連接方式

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

英語(yǔ)連詞從結(jié)構(gòu)上區(qū)分，主要有并列連詞和從屬連詞兩大類，其中并列連詞連接2個(gè)或2個(gè)以上句法地位同等重要的詞匯或分句，從屬連詞也被稱為主從連詞，在句中用于引導(dǎo)1個(gè)從屬子句。在判斷詞匯間的連接方式是否屬于方式二的過(guò)程中，我們使用了一定數(shù)量的連詞。我們使用的并列連詞有7個(gè)，從屬連詞有18個(gè)。

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

1.3 詞匯間關(guān)系度的計(jì)算與聚類

1.3.1 詞匯間關(guān)系度的計(jì)算

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

文本中data和story通過(guò)方式一連接的上下文數(shù)量為4個(gè)，通過(guò)方式二連接的上下文數(shù)量為4個(gè)，通過(guò)方式三連接的上下文數(shù)量為0個(gè)，根據(jù)前面的定量設(shè)值，得出data和story之間的關(guān)系度為2.5。

1.3.2 詞匯間關(guān)系度的聚類

聚類的過(guò)程就是把一個(gè)數(shù)據(jù)對(duì)象集中的數(shù)據(jù)分組成多個(gè)類的過(guò)程，同時(shí)使得在同一個(gè)類內(nèi)對(duì)象之間具有較高的相似度，不同類之間的對(duì)象差別較大。在聚類算法中，k-means聚類算法［10］是一個(gè)比較經(jīng)典的算法，該算法具有對(duì)大型數(shù)據(jù)集進(jìn)行高效分類的優(yōu)點(diǎn)，其計(jì)算復(fù)雜度為線性，特別適用于對(duì)數(shù)值型數(shù)據(jù)聚類，因此我們采用該算法對(duì)詞匯間的關(guān)系度進(jìn)行聚類。

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

for each W中的詞匯w1 do

for each W中的詞匯w2 do

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

then 在C中存儲(chǔ)詞匯w1及其在文本中出現(xiàn)的次數(shù)、詞匯w2及其在文本中出現(xiàn)的次數(shù)、上下文、詞匯間隔、連接方式等信息；

end for

end for for each W中的詞匯w1 do

for each W中的詞匯w2 do

for each C do

if C中存儲(chǔ)有詞匯w1和詞匯w2的信息；

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

end for

for each C1 do

計(jì)算出w1和w2的關(guān)系度并放到數(shù)據(jù)對(duì)象集S；

end for

從S中指定3個(gè)對(duì)象為聚類中心，取出所有數(shù)據(jù)對(duì)象的平均值，計(jì)算平均值與聚類中心值的均方差距離，根據(jù)計(jì)算結(jié)果的最小值對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類劃分，如果所有數(shù)據(jù)的平均值到所屬的聚類中心值的距離最短，那么返回聚類結(jié)果，否則從步驟2重新開(kāi)始循環(huán)，直到聚類中所有對(duì)象到所屬聚類中心值的距離最短為止；

for each C do

根據(jù)聚類結(jié)果，在詞匯間的關(guān)系模型中設(shè)置關(guān)系類型；

end for

end for

end for

2 可視化設(shè)計(jì)與實(shí)現(xiàn)

可視化實(shí)現(xiàn)使用的是Java，結(jié)合開(kāi)源的可視化開(kāi)發(fā)包Prefuse［11］，下面分別從可視化設(shè)計(jì)和交互式實(shí)現(xiàn)兩個(gè)方面來(lái)介紹。

2.1 可視化設(shè)計(jì)

我們采用的是放射狀樹(shù)布局［12］進(jìn)行可視化呈現(xiàn)，放射狀樹(shù)布局結(jié)合了放射狀布局和樹(shù)布局的特點(diǎn)，把樹(shù)中不同層次的節(jié)點(diǎn)按照?qǐng)A半徑的長(zhǎng)短通過(guò)放射狀的布局來(lái)顯示，層次越低離中心越近，層次越高離中心越遠(yuǎn)。以詞匯story為中心節(jié)點(diǎn)，其它詞匯按照與story的上下文關(guān)系分布在中心節(jié)點(diǎn)的周圍，與story有上下文關(guān)系的詞匯離中心越近，與story無(wú)上下文關(guān)系的詞匯離中心越遠(yuǎn)。

可視化圖形中節(jié)點(diǎn)的大小按照詞頻的高低進(jìn)行顯示。由于有的文本所含的詞匯數(shù)量多，有的文本所含的詞匯數(shù)量少，要使得節(jié)點(diǎn)大小體現(xiàn)詞頻的高低，就需要對(duì)不同數(shù)量的文本設(shè)置不同的閾值。為了避免這種情況的發(fā)生，我們把所有的20個(gè)節(jié)點(diǎn)按照詞頻從多到少分成了3個(gè)層次，其中前3個(gè)詞匯屬于第1層次，在可視化圖形中用大號(hào)字體顯示；接下來(lái)的7個(gè)詞匯屬于第2層次，在可視化圖形中用中號(hào)字體顯示；最后的10個(gè)詞匯屬于第3層次，在可視化圖形中用小號(hào)字體顯示。

可視化圖形中節(jié)點(diǎn)之間通過(guò)線條進(jìn)行連接，我們定義了3種形式的線條，分別用粗線條表示詞匯之間的連接關(guān)系緊密，細(xì)線條表示詞匯之間的連接關(guān)系一般，虛線條表示詞匯之間的連接關(guān)系疏遠(yuǎn)。

2.2 交互式實(shí)現(xiàn)

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

3 結(jié) 論

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

參考文獻(xiàn)

［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.