基于图聚类的汉越双语新闻话题发现

王禹森 余正涛 高盛祥 周 超 洪旭东

(昆明理工大学信息工程与自动化学院，昆明，650500)

引 言

随着经济全球化，不同国家之间的联系日益紧密，共同关注的事件、话题也越来越多。跨语言新闻话题发现就是针对互联网上不同国家发布的不同语言新闻进行分析处理，获得的不同类别话题的新闻，帮助人们及时掌握当前国际和地区发生的热点事件，以及对同一事件不同国家的不同看法。目前话题发现研究基本都是在单语环境下做的，并取得了很好的成果。单语话题发现方法一般分为以下3类：(1)向量空间模型。它通过抽取文本词频、词性和语法结构等特征，将文本表征成多维特征向量，利用向量之间的关系实现文本相似度的计算，从而进行共同话题的挖掘[1-2]。(2)概率模型。它利用新闻文本中词语与话题分布的统计规律，构建话题统计概率模型，分析挖掘新闻文本话题[3-4]。(3)图模型。它提取新闻文档特征及特征之间的关系，如特征词之间关系，建立特征概率图模型，通过图的求解思路分析文本的话题[5]。相比单语环境下的话题发现，双语环境下的话题发现研究较少，其关键问题在于如何跨越语言障碍，目前主要基于以下3类方法，(1)基于机器翻译。它将不同语言的新闻文本转化到同一目标语言，在单语环境下进行共同话题的挖掘与分析，机器翻译的准确性对这种方法有着很大的影响。(2)借助双语词典。该方法对文本中的实体，关键词进行翻译，来构造跨语言特征词空间，进行话题发现[6]，这种方法忽略了没有互译关系却存在联系的词语，比如“阮富仲”和“越南国家领导人”在词典中是没有互译关系的，却表达相同的意义。(3)基于大规模双语语料[7-9]。如利用概率主题模型，对平行语料或者可比语料进行跨语言主题挖掘，将获得一系列的跨语言主题作为特征空间，这种方法难点在于大规模对齐语料收集整理。

在对汉越跨语言新闻话题发现方面，由于汉越双语新闻采用不同语言进行表征，而不同语言在不同的词空间下，导致不同语言文本很难表示在同一个特征空间上，这给汉越双语新闻话题发现工作带来了挑战。同时，新闻报道中的时间、地点、人物、事情经过和事情发生的原因具有真实性，这些关键内容必须具体、明确，对于同一事件的报道，汉语与越南语新闻在这些新闻要素上一致，这为进行汉越双语的话题发现研究提供了有效的途径。利用新闻要素表征文档，计算要素间相关性，可以计算出文本间的相似度，构成汉越双语新闻图模型，图中节点的紧密程度表示文本相似度高低，这样便将汉越双语新闻话题发现看成图模型的聚类问题来分析。

1 面向汉越新闻报道的图模型

汉越双语新闻图G={V,E,W}，表示汉越双语新闻集合N与图的一个映射。V是汉越双语新闻集合中的新闻文本在图中对应的文本集合，vi为汉语文本,vj为越南语文本，表示为V={vi,vj|1≤i≤n,1≤j≤m}。E是汉越双语新闻集合中的新闻文本在图中的边， (vi1,vi2)为汉语文档间的边，(vj1,vj2)为越南语文档间的边，(vi,vj)为汉越双语文档间的边，表示为E={(vi,vj),(vi1,vi2),(vj1,vj2)|i1≠i2,j1≠j2}。W表示图中边的权重，表示为W={w(i,j),w(i1,i2),w(j1,j2)}，权重由新闻要素相似度决定。新闻的事件要素一般包括时间、地点、人物、经过和原因，可以表示为When，Where，Who，What和Why，其中，时间可以用时间实体来表示，地点可以用地点实体来表示，人物可以用人物实体来表示，经过一般用要素中的动词来表示。规定两个新闻文本间具有连接线必须满足以下条件之一：(1)两篇新闻在时间、地点和人物等要素上有相同的要素对出现；(2)两篇新闻在What这个要素上相似度达到0.5以上。

计算单语文档间边权重时，考虑新闻文本中的词对于所在新闻文本的重要程度，采用TF-IDF方法计算。抽取新闻文本要素，以向量的形式表征一篇新闻文本，每个向量由其特征项及权重表示，构成文本向量空间。相同语言文档节点间的相似度采用两篇文档空间向量的夹角余弦来计算。

设任意两个节点∀xi,xk∈V，TF-IDF公式为

Wt,x=TFt,x×IDFt,x

(1)

(2)

IDFt,x=log(X/XN)

(3)

式中:Wt,x为新闻要素t在新闻文本x中的权重; TFt,x指词语t在文档x中出现的频率，如式(2)表示一篇有M个词的文档含有N个新闻要素t。IDFt,x反映新闻要素t在所有新闻文档中的常见程度，在一定程度上体现了该新闻要素的区分能力，其中X表示所有新闻文档的数目，XN表示所有新闻文档中包含新闻要素t的文档数。

利用文档向量间的夹角余弦分别计算相同语言文档节点间的权重为

(4)

式中：Wt,x1,Wt,x2分别为文档x1,x2中的第t个特征项的权重，从而得到相同语言文档间的权重，即w(i1,i2)，w(j1,j2) 。

计算汉越双语文档间边权重时，抽取新闻文档要素，将汉越双语文档表征成向量，计算汉语文档向量中新闻要素与越南语文档向量中每个新闻要素的相似度和，从而得到汉越双语文档间的相似度为

(5)

图1 汉越双语新闻图Fig.1 Chinese-Vietnamese bilingual news graph

式中：w(i,j)为汉越双语文档间边的相似度，即图中边vi与vj之间的权重；w(a,b)为汉越文档中两个要素的相似度。w(a,b)具体相似度的计算方法是借助维基百科中具有中越互译关系的概念，不同语言词语会出现在不同的概念页面上，且词语与其他概念之间存在一定的共现关系，首先提取维基百科中汉语越南语具有对应关系的概念集合，构建双语概念特征空间，然后根据词语在相应概念描述文本中出现的词频特征，以及词语与概念在其他概念文本中的共现特征构建词语的概念向量值，最后通过夹角余弦对两个向量进行词语相似度计算[10]。最后可以得到汉越新闻图模型，基本框架如图1所示。

2 随机游走相似度矩阵计算

汉越双语新闻图的转移概率矩阵可以表示为pz= (pij)，它是一个n×n矩阵,其中的每一个元素pi j表示任意一个顶点vi到其邻居节点vj的转移概率为

(6)

式中：wij为新闻文本节点vi与vj的相似度，即图中边的权重；k为图中以文本节点vi为端点的边的个数；∑wij为所有以文本节点vi为端点的边的权重之和；图中不具有连线关系的文本节点的转移概率为0。

定义1给定图G={V,E,W}，顶点vi到vj的路径是集合E中从顶点v0=vi出发到顶点vk+1=vj结束的一系列边的集(v0,v1),(v1,v2)，…，(vk-1,vk),(vk,vj)，可表示为Path(vi,vj)，如果有这样一条可以相通的路径就说明顶点vi和vj是相连的。路径上边的权重之和可以表示路径的长度，而顶点vi和vj之间的距离指长度中最大的一个。

采用随机游走模型来度量汉越新闻图中顶点之间的相似度，若两个顶点之间相通的路径越多，则说明两顶点之间的转移概率就越大，顶点之间的相似度就越大。

定义2图G的n×n的转移概率矩阵为pz，给定l为随机游走的路径长度，则顶点vi到vj的邻近随机游走相似度为

(7)

式中：Path(vi,vj)是顶点vi到vj的路径，其长度为length(Path(vi,vj))，p(Path(vi,vj))为转移概率。随机游走相似度矩阵可表示为

(8)

式中：pz为转移概率矩阵，l为随机游走的路径长度。过程如算法1所描述。

算法1汉越新闻图随机游走相似度矩阵算法。

输入：汉越新闻图。

输出：随机游走相似度矩阵。

(1)计算汉越新闻图的转移概率矩阵。

(2)计算汉越新闻图的邻近随机游走相似度。

(3)利用转移概率矩阵计算汉越新闻图的随机游走相似度矩阵。

(4)输出汉越新闻图的随机游走相似度矩阵。

3 基于信息传递的汉越新闻图聚类

利用汉越新闻文本相似度矩阵进行图聚类与一般聚类问题相比存在以下特点：(1)通过随机游走得到的汉越新闻文本相似度矩阵，描述的是节点之间的相关程度，而不是节点之间的欧式距离，故无法直接使用K-Means算法进行求解。(2)本文得到的汉越新闻文本相似度矩阵不对称，故无法使用谱聚类的方法进行求解。因此，本文采用信息传递算法[11]对汉越新闻文本图模型进行聚类，整个聚类的过程，利用汉越双语新闻图的随机游走相似度矩阵，通过迭代更新吸引度和归属度两种信息完成聚类，相应的更新公式为

(9)

(10)

(11)

式中：r(vi,vj)为从顶点vi发送到聚类中心vj的数值消息，反映顶点vj是否适合作为顶点vi的聚类中心；s(vi,vj)为顶点vi和vj的相似度；a(vi,vj)为从候选聚类中心vj发送到顶点vi的数值信息，反映顶点vi是否选择vj作为其聚类中心。在信息传递聚类算法的每次迭代更新顶点vi的过程中，吸引度Ri和归属度Ai要与上次迭代所得Ri-1与Ai-1的值进行加权更新，更新公式为

Ri=(1-lam)×Ri+lam×Ri-1

(12)

Ai=(1-lam)×Ai+lam×Ai-1

(13)

其中，lam∈[0,1]通过改变lam的值可以改进算法的收敛性。

算法满足以下条件之一，即停止迭代：

(1)达到预先设定的迭代次数；(2)顶点信息改变量低于设定的阈值；(3)所选的聚类中心在连续若干次的迭代中保持稳定的值。

根据r(vi,vj)+a(vi,vj)的值判断顶点vj能否作为聚类中心，最后，将其他顶点分配到与其最邻近的聚类中心。具体的聚类过程如算法2所示。

算法2信息传递聚类算法。

输入：邻接随机游走相似度矩阵。

输出：k个簇C1，C2，C3，…，Ck。

(1)初始化r(vi,vj)=0，a(vi,vj)=0

(2)迭代执行以下更新过程：

(6)Ri=(1-lam)×Ri+lam×Ri-1

(7)Ai=(1-lam)×Ai+lam×Ai-1

(8)对于任一个顶点vi，如果r(vi,vi)+a(vi,vi)达到迭代次数或者不再变化，则vi是一个聚类中心。

(9)基于s(vi,vi)，将其他顶点vj分配到与它最邻近的聚类中心。

(10)输出k个簇C1，C2，C3，…，Ck。

基于以上随机游走算法和信息传递算法，最后得到k个簇，认为每一个簇都是一个话题，完成了汉越双语新闻的话题发现任务。

4 实验结果与分析

4.1 实验数据

选取了180个中文门户网站和20个论坛以及125个不同专题的越南语网站。中文新闻包括新华社、人民日报、知名论坛、主流门户网站和越南网站(以每日快讯、越讯社和越共机关等核心平台为主)。在从爬取到的数据中选择训练集时，选取了5个话题：两会、朝核、中国反腐、南海争端和叙利亚反恐。因为在这5个话题上，越南的各大媒体和中国的各大媒体关注最多。另外，一个话题出现以后，会在一段时间内出现很多关于该话题的新闻报道，所以在进行新闻文档选取的时候只选取近10天的新闻数据进行实验。

新闻最核心的是What，Who，Where，When和Why 5个要素，而这5个要素的词性主要对应了动词、名词、时态词、形容词和数词，因此在对汉语和越南语新闻文本进行分词和词性标注后，将这些词性的词语抽取出来作为新闻要素。对于中文词性标注和命名实体识别，采用ICTCLAS3.0工具。利用越南语分词工具[12]对越南语新闻文本进行分词、词性标注等处理，根据处理结果，人工辅助抽取要素。各类新闻数如表1所示。

表1 实验数据集

4.2 评价方法

在话题发现研究中，经常会用错检率F和漏检率M作为评价指标。评价指标的具体含义见表2。

表2 评价指标的具体含义

在表2中用大写字母A，B，C，D来表示某一个话题的检测结果，用F=B/(B+D) 来表示话题检测的错检率，用M=C/(A+C)来表示话题检测的漏检率。此外，为了综合漏检率和错检率，定义耗费函数(Cost function)为

CDet=CmissPmissP(rel)+CfaPfa(1-P(rel))

(14)

式中：Cmiss和Cfa为话题检测中漏检和误检的代价，P(rel)表示某个新闻报道属于某一类的先验概率，Pmiss和Pfa为话题检测的漏检概率和误检概率。在TDT的标准中，令Cmiss=1.0，Cfa=0.1，P(rel)=0.02。由此可以看出耗费函数越小，话题发现效果越好。

4.3 实验结果与分析

本文通过3个不同方法进行汉越新闻话题发现，方法1通过基于多策略优化的分治多层聚类算法的话题发现方法，首先得出单语文档下的聚类结果，然后通过机器翻译的方法将其合并；方法2采用双语文档主题生成模型(Latent Dirichlet allocation, LDA)，利用Wikipedia中的10 000对汉越双语文档构建可比语料，训练双语主题模型，对不同语言文本进行表示[13]。认为一对文档主题上具有相同的概率分布。本文共设置了100个主题，利用获得的双语主题模型来对要聚类的500篇新闻进行推断，最后，采用K-Means进行聚类。方法3采用本文提出的话题发现方法。实验结果如表3所示。

表3 新闻话题发现对比实验结果

根据实验结果数据，分别计算每种方法的误检率、漏检率和消耗函数，对比结构如表4所示。通过表4的实验结果对比可以发现，在给定训练集的5个话题下，本文方法通过计算新闻要素的相似度，求得图模型，并通过随机游走算法求得相似度矩阵，在话题发现方面，不论是漏检率、误检率还是最后的耗费函数都要优于基于多策略优化的分治多层聚类算法和双语LDA方法。由此可见，本文提出的基于图模型的汉越双语新闻话题发现图聚类模型是可行的。

表4 误检率、漏检率和消耗函数

5 结束语

在双语环境下进行话题发现是一项比较困难的任务，本文提出基于图聚类的汉越双语话题发现方法，利用双语新闻要素作为跨语言的桥梁，根据不同语言新闻要素之间的关联计算不同语言新闻文本之间的相似度。通过本文的研究可以发现利用新闻要素可以更好地表征一篇新闻文档；此外，利用新闻要素作为跨语言桥梁，建立汉越双语新闻图模型，通过图中节点的紧密程度表示新闻相似程度，采用基于信息传递的汉越双语新闻图聚类算法能够有效地提高话题发现的效果。下一步工作将融合新闻主题句的关联，提高汉越双语话题发现的效果。

参考文献:

[1] Zhang Dan, Li Shengdong. Topic detection based on K-means[C]// International Conference on Electronics, Communications and Control. Ningbo, China:[s.n.], 2011:2983-2985.

[2] 赵华,赵铁军,于浩,等. 基于查询向量的英语话题跟踪研究[J].计算机研究与发展, 2007,44(8):1412-1417.

Zhao Hua, Zhao Tiejun, Yu Hao, et al. English topic tracking research based on query vector[J]. Journal of Computer Research and Development, 2007,44(8):1412-1417.

[3] Guo Xin, Xiang Yang, Chen Qian, et al. LDA-based online topic detection using tensor factorization[J]. Journal of Information Science, 2013, 39(4):459-469.

[4] Phan X H, Nguyen L M, Horiguchi S. Learning to classify short and sparse text & web with hidden topics from large-scale data collections[C]// International Conference on World Wide Web. Beijing, China:[s.n.], 2008:91-100.

[5] Zhao Wenqing, Hou Xiaoke. News topic recognition of Chinese microblog based on word co-occurrence graph[J]. CAAI Transactions on Intelligent Systems, 2012, 5: 444-449.

[6] Mathieu B, Fluhr C. Multilingual document clusters discovery[C]// Computer-assisted Information Retrieval. Avignon, France: [s.n.], 2004:116-125.

[7] Boyd-Graber J, Blei D M. Multilingual topic models for unaligned text[C]// Conference on Uncertainty in Artificial Intelligence. [S.l.]: AUAI Press, 2012:75-82.

[8] Mimno D, Wallach H M, Naradowsky J, et al. Polylingual topic models[C]// Conference on Empirical Methods in Natural Language Processing. Singapore: ACL, 2009:880-889.

[10] 杨启悦, 余正涛, 洪旭东,等.基于维基百科的汉越词语相似度计算[J].南京理工大学学报(自然科学版),2016,40(4):461-466.

Yang Qiyue, Yu Zhengtao, Hong Xudong, et al. Chinese-Vietnamese word similarity computation based on Wikipedia[J]. Journal of Nanjing University of Science and Technology, 2016,40(4):461-466.

[11] Frey B J, Dueck D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972-976.

[12] Cam Tu N, Xuan Hieu P, Thu Trang N. JVnTextPro: A Java-based Vietnamese text processing tool[EB/OL]. http: //jvntextpro.sourceforge.net/, 2010-1-1.

[13] Ni Xiaochuan, Sun Jiantao, Hu Jian, et al. Mining multilingual topics from Wikipedia[C]// International Conference on World Wide Web. Madrid, Spain:[s.n.], 2009:1155-1156.