共现词网络的可视化算法.doc

精品论文共现词网络的可视化算法吴诗贤 重庆工商大学计算机科学与信息工程学院，重庆 (400067) e-mail: 摘要：基于大规模语料库构建的共现词网络在相当程度上蕴含着词所代表的事物、现象之间的关联强弱，但一般来说，这样的共现词网络非常复杂，使其实际应用受到很大限制。本 文从降低共现词网络复杂度，提高其可视性的目标出发，提出了一种共现词网络简化、可视 化算法。该算法通过去掉连接权值小于连接权阀值的连接来减少词节点之间的连接边，利用 链接强度指数衰减公式去掉无关节点，并用连线的粗细来对应不同链接强度，从而提高目标 词关联的可视度。关键词：共现词网络；连接强度；衰减函数；可视化 中图分类号：tp3911引 言共现词是在大量文档中经常搭配、共同出现的词汇，某词的共现词的集合在某种程度上 描述了该词的语义环境，共现词之间的关联强度也在一定程度上反映了这些词所代表的语义 之间的关联强度，因此，以大规模语料库为基础，构建词之间的共现网络，分析它们之间连 接强度，应该是一种可行的分析词所代表的语义关联情况的定性定量化方法。基于此，本文 提出一种共现词网络模型及其变换算法，实现了基于共现词网络的词关联的可视化。2共现网络2.1 共现词抽取随着信息爆炸时代的到来，为了从大量文本数据中抽取隐含的，未知的，可能有用的信 息，文本挖掘技术成为智能信息处理技术领域重要的研究方向，共现词抽取作为一种重要的 文本挖掘技术也获得了不少研究者的注目，并取得了大量的研究成果，其中，attar等提出基 于关联聚类和距离聚类寻找文档中的共现词汇算法，1berry等提出潜在语义索引lsi求共现 词汇算法,2有的学者采用在抽取共现信息之前先抽取文档的关键字,然后针对关键字计算共 现词的算法,3郭锋等提出了一种基于词汇吸引与排斥模型、并通过将多种常用统计量的组合 进行共现词提取的算法。4本文中，共现词提取方案基于文献4所提出的方法，假设(s,t) 是在文本中出现的词对,用score (t，s) 表示取词对(s,t)为共现词的评估值，其计算公式如下:- 4 -niscore(t, s) = (1 e u )e uk )(wti =1 scorei (t, s)（1）k表示s与t的平均距离为k 个词。上式的 (1 eu )euk 部分表示t与s是共现词的概率将随 着k 的增加而呈指数下降。上式的后半部分通过i种评估方法加权组合来求取共现词评估值，n为常用单一评估词与词结合紧密度的统计量个数，包括互信息、z-score 、students t-score以及频次等, scorei (t， s)为第i种统计量评估词对(s,t)为共现词的评估值（各种方法的评估值进行归一化处理后的结 果），wti为第i种方法的权重。2.2 共现网络通过 2.1 所示方法得到词汇之间共现评估值后，以共现词为节点，共现评估值为连接权 值，形成如图 1 所示词共现网络，下面称这样的共现网络为原始共现词网络。3共现网络可视化算法图 1 共现词网络上节构筑的原始共现词网络，由于大量的节点之间连接在一起，连接关系异常复杂，其计算复杂度极大、图示化时可视性叶非常差，通过这样一个共现词网络，很难把握词之间的 相互关联关系，因此需要通过某种方法提高其可视性；在许多应用场合，一些虽然没有直接 连接或直接连接较弱但间接联系较强的词之间的关联强度也需要进行度量；另外，在利用共 现网络进行相关分析与决策的时候，常常需要求取指定的目标词之间的关联情况。以上种种 情况，都可以归结为共现词网络的变换及可视化问题。下面介绍本文提出的共现词网络可视 化方法。3.1 共现网络的简化共现网络可视化简化时，可采用两种方法，方法之一是定义一个共现词的连接权阀值变 量，针对上节得到的要简化的共现词网络，去掉连接权值小于连接权阀值的连接，从而减少 词节点之间的连接边，在实际应用中可根据具体情况设置不同的连接权阀值，从而得到不同 连接复杂度的共现词网络；方法之二是针对要处理的共现网络，在应用软件中进行可视化表 现的时候，用节点之间连接线的粗细来表征不同的连接权值，从而使词节点之间的连接强度 的可视化得以实现。3.2 非相邻词节点间关联度求取算法非相邻节点词之间，虽然没有直接连接，但通过其它词的桥接作用，相互之间仍然具有 相关性，本文采用指数衰减函数来求取其连接强度值。具有 n 个中间节点词 r1,r2,rn 的第 k 条连接链路上非相邻两个节点词（t,s）之间的连 接强度计算如下：uscorek (t, s) = min(score(t, r1), score(r1, r 2),., score(rn, s) e，u0(2)其中， eu 为衰减函数。具有 m 条连接链路的非相邻两个节点词（t,s）之间的连接强度为mscore(t, s) = scorek (t, s)k =1（3）3.3 目标词集合的关联网络在进行分析与决策的时候，根据实际问题的具体情况，我们常常希望能得到若干目标词 之间关联性强弱的可视化情报，结合 3.1、3.2 介绍的方法，下面给出针对特定目标词集合求 取其成员词可视化关联网络的具体算法流程：（1）针对给定的目标词集合中的每一个成员词，以该词为中心节点从原始共现词网络 中提出所有相邻节点构成一个子网络，然后将所有子网络的共同节点连接，形成包含所有目 标词在内的一个共现网络（如果出现与其它目标词都没有连接的成员词，则说明该目标词与 其它目标词的关联都很弱，让其作为孤立节点存在）。（2）消除上述共现网络中非目标词的叶节点。（3）判断剩下网络的连接复杂度，如果过高，则利用 3.1 介绍的简化方法简化该网络， 即去掉连接权值小于连接权阀值的连接，简化后如果出现非目标词的叶节点，则从网络中消 去之；否则直接转（4）；（4）如果剩下网络中包含非给定的目标词的节点 r，则利用式（2）、式（3）求取通过r 桥接的节点之间的链接强度，然后去掉节点 r；否则直接转（5）。（5）经过以上步骤得到的网络即作为目标词关联网络进行可视化显示，即用节点之间 连接线的粗细来表征不同的连接权值，实现词节点之间的连接强度的可视化。图 2 为上述算法的示例图。图 2 目标词关联网络求取算法示意图（黑心节点为目标词）4. 结束语本文针对基于大规模语料库构建的共现词网络复杂度过大问题，提出了一种共现词网络 简化算法，可在抓住主要关联的基础上大大提高给定目标词之间关联的可视度，可适用于词 所代表的事物、现象之间的关联分析、因果分析。参考文献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郭锋,李绍滋,周昌乐等.基于词汇吸引与排斥模型的共现词提取.中文信息学报,第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