共現(xiàn)詞網(wǎng)絡(luò)的可視化算法.doc

精品論文共現(xiàn)詞網(wǎng)絡(luò)的可視化算法吳詩(shī)賢 重慶工商大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，重慶 (400067) e-mail: 摘要：基于大規(guī)模語(yǔ)料庫(kù)構(gòu)建的共現(xiàn)詞網(wǎng)絡(luò)在相當(dāng)程度上蘊(yùn)含著詞所代表的事物、現(xiàn)象之間的關(guān)聯(lián)強(qiáng)弱，但一般來(lái)說(shuō)，這樣的共現(xiàn)詞網(wǎng)絡(luò)非常復(fù)雜，使其實(shí)際應(yīng)用受到很大限制。本 文從降低共現(xiàn)詞網(wǎng)絡(luò)復(fù)雜度，提高其可視性的目標(biāo)出發(fā)，提出了一種共現(xiàn)詞網(wǎng)絡(luò)簡(jiǎn)化、可視 化算法。該算法通過(guò)去掉連接權(quán)值小于連接權(quán)閥值的連接來(lái)減少詞節(jié)點(diǎn)之間的連接邊，利用 鏈接強(qiáng)度指數(shù)衰減公式去掉無(wú)關(guān)節(jié)點(diǎn)，并用連線的粗細(xì)來(lái)對(duì)應(yīng)不同鏈接強(qiáng)度，從而提高目標(biāo) 詞關(guān)聯(lián)的可視度。關(guān)鍵詞：共現(xiàn)詞網(wǎng)絡(luò)；連接強(qiáng)度；衰減函數(shù)；可視化 中圖分類號(hào)：tp3911引 言共現(xiàn)詞是在大量文檔中經(jīng)常搭配、共同出現(xiàn)的詞匯，某詞的共現(xiàn)詞的集合在某種程度上 描述了該詞的語(yǔ)義環(huán)境，共現(xiàn)詞之間的關(guān)聯(lián)強(qiáng)度也在一定程度上反映了這些詞所代表的語(yǔ)義 之間的關(guān)聯(lián)強(qiáng)度，因此，以大規(guī)模語(yǔ)料庫(kù)為基礎(chǔ)，構(gòu)建詞之間的共現(xiàn)網(wǎng)絡(luò)，分析它們之間連 接強(qiáng)度，應(yīng)該是一種可行的分析詞所代表的語(yǔ)義關(guān)聯(lián)情況的定性定量化方法。基于此，本文 提出一種共現(xiàn)詞網(wǎng)絡(luò)模型及其變換算法，實(shí)現(xiàn)了基于共現(xiàn)詞網(wǎng)絡(luò)的詞關(guān)聯(lián)的可視化。2共現(xiàn)網(wǎng)絡(luò)2.1 共現(xiàn)詞抽取隨著信息爆炸時(shí)代的到來(lái)，為了從大量文本數(shù)據(jù)中抽取隱含的，未知的，可能有用的信 息，文本挖掘技術(shù)成為智能信息處理技術(shù)領(lǐng)域重要的研究方向，共現(xiàn)詞抽取作為一種重要的 文本挖掘技術(shù)也獲得了不少研究者的注目，并取得了大量的研究成果，其中，attar等提出基 于關(guān)聯(lián)聚類和距離聚類尋找文檔中的共現(xiàn)詞匯算法，1berry等提出潛在語(yǔ)義索引lsi求共現(xiàn) 詞匯算法,2有的學(xué)者采用在抽取共現(xiàn)信息之前先抽取文檔的關(guān)鍵字,然后針對(duì)關(guān)鍵字計(jì)算共 現(xiàn)詞的算法,3郭鋒等提出了一種基于詞匯吸引與排斥模型、并通過(guò)將多種常用統(tǒng)計(jì)量的組合 進(jìn)行共現(xiàn)詞提取的算法。4本文中，共現(xiàn)詞提取方案基于文獻(xiàn)4所提出的方法，假設(shè)(s,t) 是在文本中出現(xiàn)的詞對(duì),用score (t，s) 表示取詞對(duì)(s,t)為共現(xiàn)詞的評(píng)估值，其計(jì)算公式如下:- 4 -niscore(t, s) = (1 e u )e uk )(wti =1 scorei (t, s)（1）k表示s與t的平均距離為k 個(gè)詞。上式的 (1 eu )euk 部分表示t與s是共現(xiàn)詞的概率將隨 著k 的增加而呈指數(shù)下降。上式的后半部分通過(guò)i種評(píng)估方法加權(quán)組合來(lái)求取共現(xiàn)詞評(píng)估值，n為常用單一評(píng)估詞與詞結(jié)合緊密度的統(tǒng)計(jì)量個(gè)數(shù)，包括互信息、z-score 、students t-score以及頻次等, scorei (t， s)為第i種統(tǒng)計(jì)量評(píng)估詞對(duì)(s,t)為共現(xiàn)詞的評(píng)估值（各種方法的評(píng)估值進(jìn)行歸一化處理后的結(jié) 果），wti為第i種方法的權(quán)重。2.2 共現(xiàn)網(wǎng)絡(luò)通過(guò) 2.1 所示方法得到詞匯之間共現(xiàn)評(píng)估值后，以共現(xiàn)詞為節(jié)點(diǎn)，共現(xiàn)評(píng)估值為連接權(quán) 值，形成如圖 1 所示詞共現(xiàn)網(wǎng)絡(luò)，下面稱這樣的共現(xiàn)網(wǎng)絡(luò)為原始共現(xiàn)詞網(wǎng)絡(luò)。3共現(xiàn)網(wǎng)絡(luò)可視化算法圖 1 共現(xiàn)詞網(wǎng)絡(luò)上節(jié)構(gòu)筑的原始共現(xiàn)詞網(wǎng)絡(luò)，由于大量的節(jié)點(diǎn)之間連接在一起，連接關(guān)系異常復(fù)雜，其計(jì)算復(fù)雜度極大、圖示化時(shí)可視性葉非常差，通過(guò)這樣一個(gè)共現(xiàn)詞網(wǎng)絡(luò)，很難把握詞之間的 相互關(guān)聯(lián)關(guān)系，因此需要通過(guò)某種方法提高其可視性；在許多應(yīng)用場(chǎng)合，一些雖然沒(méi)有直接 連接或直接連接較弱但間接聯(lián)系較強(qiáng)的詞之間的關(guān)聯(lián)強(qiáng)度也需要進(jìn)行度量；另外，在利用共 現(xiàn)網(wǎng)絡(luò)進(jìn)行相關(guān)分析與決策的時(shí)候，常常需要求取指定的目標(biāo)詞之間的關(guān)聯(lián)情況。以上種種 情況，都可以歸結(jié)為共現(xiàn)詞網(wǎng)絡(luò)的變換及可視化問(wèn)題。下面介紹本文提出的共現(xiàn)詞網(wǎng)絡(luò)可視 化方法。3.1 共現(xiàn)網(wǎng)絡(luò)的簡(jiǎn)化共現(xiàn)網(wǎng)絡(luò)可視化簡(jiǎn)化時(shí)，可采用兩種方法，方法之一是定義一個(gè)共現(xiàn)詞的連接權(quán)閥值變 量，針對(duì)上節(jié)得到的要簡(jiǎn)化的共現(xiàn)詞網(wǎng)絡(luò)，去掉連接權(quán)值小于連接權(quán)閥值的連接，從而減少 詞節(jié)點(diǎn)之間的連接邊，在實(shí)際應(yīng)用中可根據(jù)具體情況設(shè)置不同的連接權(quán)閥值，從而得到不同 連接復(fù)雜度的共現(xiàn)詞網(wǎng)絡(luò)；方法之二是針對(duì)要處理的共現(xiàn)網(wǎng)絡(luò)，在應(yīng)用軟件中進(jìn)行可視化表 現(xiàn)的時(shí)候，用節(jié)點(diǎn)之間連接線的粗細(xì)來(lái)表征不同的連接權(quán)值，從而使詞節(jié)點(diǎn)之間的連接強(qiáng)度 的可視化得以實(shí)現(xiàn)。3.2 非相鄰詞節(jié)點(diǎn)間關(guān)聯(lián)度求取算法非相鄰節(jié)點(diǎn)詞之間，雖然沒(méi)有直接連接，但通過(guò)其它詞的橋接作用，相互之間仍然具有 相關(guān)性，本文采用指數(shù)衰減函數(shù)來(lái)求取其連接強(qiáng)度值。具有 n 個(gè)中間節(jié)點(diǎn)詞 r1,r2,rn 的第 k 條連接鏈路上非相鄰兩個(gè)節(jié)點(diǎn)詞（t,s）之間的連 接強(qiáng)度計(jì)算如下：uscorek (t, s) = min(score(t, r1), score(r1, r 2),., score(rn, s) e，u0(2)其中， eu 為衰減函數(shù)。具有 m 條連接鏈路的非相鄰兩個(gè)節(jié)點(diǎn)詞（t,s）之間的連接強(qiáng)度為mscore(t, s) = scorek (t, s)k =1（3）3.3 目標(biāo)詞集合的關(guān)聯(lián)網(wǎng)絡(luò)在進(jìn)行分析與決策的時(shí)候，根據(jù)實(shí)際問(wèn)題的具體情況，我們常常希望能得到若干目標(biāo)詞 之間關(guān)聯(lián)性強(qiáng)弱的可視化情報(bào)，結(jié)合 3.1、3.2 介紹的方法，下面給出針對(duì)特定目標(biāo)詞集合求 取其成員詞可視化關(guān)聯(lián)網(wǎng)絡(luò)的具體算法流程：（1）針對(duì)給定的目標(biāo)詞集合中的每一個(gè)成員詞，以該詞為中心節(jié)點(diǎn)從原始共現(xiàn)詞網(wǎng)絡(luò) 中提出所有相鄰節(jié)點(diǎn)構(gòu)成一個(gè)子網(wǎng)絡(luò)，然后將所有子網(wǎng)絡(luò)的共同節(jié)點(diǎn)連接，形成包含所有目 標(biāo)詞在內(nèi)的一個(gè)共現(xiàn)網(wǎng)絡(luò)（如果出現(xiàn)與其它目標(biāo)詞都沒(méi)有連接的成員詞，則說(shuō)明該目標(biāo)詞與 其它目標(biāo)詞的關(guān)聯(lián)都很弱，讓其作為孤立節(jié)點(diǎn)存在）。（2）消除上述共現(xiàn)網(wǎng)絡(luò)中非目標(biāo)詞的葉節(jié)點(diǎn)。（3）判斷剩下網(wǎng)絡(luò)的連接復(fù)雜度，如果過(guò)高，則利用 3.1 介紹的簡(jiǎn)化方法簡(jiǎn)化該網(wǎng)絡(luò)， 即去掉連接權(quán)值小于連接權(quán)閥值的連接，簡(jiǎn)化后如果出現(xiàn)非目標(biāo)詞的葉節(jié)點(diǎn)，則從網(wǎng)絡(luò)中消 去之；否則直接轉(zhuǎn)（4）；（4）如果剩下網(wǎng)絡(luò)中包含非給定的目標(biāo)詞的節(jié)點(diǎn) r，則利用式（2）、式（3）求取通過(guò)r 橋接的節(jié)點(diǎn)之間的鏈接強(qiáng)度，然后去掉節(jié)點(diǎn) r；否則直接轉(zhuǎn)（5）。（5）經(jīng)過(guò)以上步驟得到的網(wǎng)絡(luò)即作為目標(biāo)詞關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行可視化顯示，即用節(jié)點(diǎn)之間 連接線的粗細(xì)來(lái)表征不同的連接權(quán)值，實(shí)現(xiàn)詞節(jié)點(diǎn)之間的連接強(qiáng)度的可視化。圖 2 為上述算法的示例圖。圖 2 目標(biāo)詞關(guān)聯(lián)網(wǎng)絡(luò)求取算法示意圖（黑心節(jié)點(diǎn)為目標(biāo)詞）4. 結(jié)束語(yǔ)本文針對(duì)基于大規(guī)模語(yǔ)料庫(kù)構(gòu)建的共現(xiàn)詞網(wǎng)絡(luò)復(fù)雜度過(guò)大問(wèn)題，提出了一種共現(xiàn)詞網(wǎng)絡(luò) 簡(jiǎn)化算法，可在抓住主要關(guān)聯(lián)的基礎(chǔ)上大大提高給定目標(biāo)詞之間關(guān)聯(lián)的可視度，可適用于詞 所代表的事物、現(xiàn)象之間的關(guān)聯(lián)分析、因果分析。參考文獻(xiàn)1 attar r, fraenkel a s. local feedback in full-text retrieval systems j. jacm, 1977, 24(3):397417.2 berry m w, dumais s t, o brien g w. using linear algebra for intelligent information retrieval j. siam review,1995, 37(5):573595.3 yuen-hsien tseng , fast co-occurrence thesaurus construction for chinese newsa . proceedings of 2001ieee international conference on systems , man , and cyberneticsc , volume 2 , pages :853858 , oct. 2001.4郭鋒,李紹滋,周昌樂(lè)等.基于詞匯吸引與排斥模型的共現(xiàn)詞提取.中文信息學(xué)報(bào),第18卷第6期.visualization algorithm of co-occurrence network of termswu shixiancomputer science and information engineering college, chongqing technology and businessuniversity, chongqing (400067)abstractco-occurrence network of terms based on large-scale corpus hold the mirror up to relationship between terms, but its application is limited by reason of the complexity. in this paper, a visualizationalgorithm is proposed to simplify the network structure. in this algorithm, the following three methods is used to improve the visibility of co-occurrence network of target terms: using valve-value totake out the line that has light weight, using attenuation-function to take out the