基于极大团聚类的汉泰双语话题在线发现
(1、昆明理工大学信息工程与自动化学院云南昆明 650500；2、昆明理工大学智能信息处理重点实验室云南昆明 650500）
摘要：双语话题发现是互联网+时代和经济全球化趋势下自然语言处理重要应用，目前没有双语话题发现方法可以解决双语话题分布不一致的问题，针对该问题，本文提出一种基于极大团的汉泰话题特征词聚类的双语话题发现方法，首先通过TextRank算法抽取每篇汉泰文档的关键词等新闻信息，通过汉泰词典结合相似度消歧，利用可信关联规则对汉泰特征词进行聚类生成双语极大团话题，最后对相似极大团话题聚类，得到最终话题集合，根据用户需要可以推荐不同粒度的双语话题。实验通过2016年1月汉泰新闻集测试取到了较好效果,算法从跨语言词聚类角度，合理地解决了双语话题分布不一致问题，具有不需要预估话题个数和时间复杂度低的优点，适合双语话题在线发现应用。
关键词：汉泰；极大团；可信关联规则；TextRank；双语话题发现
作者简介:让子强(1993-)，男，安徽，硕士，主要研究方向：自然语言处理；周兰江（1964-），通讯作者，男，云南，硕士生导师，副教授，主要研究领域为自然语言处理与嵌入式系统研究；张金鹏(1989-)，男，河南，硕士，主要研究方向：自然语言处理、数据挖掘
Chinese and Thai Bilingual topic detection online base on maximal clique clustering
RANG Ziqiang1,2, ZHANG Jinpeng1,2, ZHOU Lanjiang1,2, XIAN Yantuan1,2, YU Zhengtao1,2
(1. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming650500,China; 2. The Key Laboratory of Intelligent Information Processing, Kunming University of Science and Technology, Kunming650500, China)
Abstract: Bilingual topic detection is a vital application of natural language processing in the Internet plus Era and trend of economic globalization. At present, the method of bilingual topic detection can't solve the problem of bilingual topic inconsistent distribution. Aiming at the shortcoming, this paper introduces a based on maximal clique method to find bilingual topic detection of Chinese and Thai feature words. First of all, extract the information of news with keywords of each Chinese and Thai documents through the TextRank algorithm. Next, disambiguate by means of the similarity combined with Chinese and Thai dictionary. Then, use credible association rules to cluster Chinese and Thai feature words, which generates maximal clique of bilingual topic. Finally, cluster similar maximal clique of topic to obtain the collection of final topic. According to the needs of users, the method can recommend a bilingual topic of different sizes. The test of Chinese and Thai news texts in January 2016 made good achievement. From the perspective of cross-language word clustering, the algorithm effectively solves the problem of inconsistency of bilingual topic distribution reasonably, and has the advantages of no need to estimate the number of topics and low time complexity, so it is suitable for the application of online discovery in bilingual topic.
Keywords: Chinese-Thai, Maximal cliques, Credible association rule, TextRank, Bilingual topics detection
0引言
随着信息技术的发展，互联网日益成为组织或个人了解他国动向的重要渠道。互联网每天产生的海量数据，为提取有用新闻文本增加了难度，同时汉语与其它语言之间存在着巨大的语言障碍。因此，如何通过每天产生的新闻数据，及时有效得获取国外话题资讯成为舆情监控、情报竞争、双语信息检索领域的新热点。目前在跨语言话题发现领域，从解决语言障碍的角度主要分为机器翻译或双语词典和平行语料库两种方法。基于机器翻译[1]或双语词典[2]的方法主要把跨语言文本转化为同一语言,在单一语言的基础上进行话题分析，BNN在2000年提出一种基于机器翻译的汉语和英语间话题发现和追踪的系统[1]；Ying-Ju Chen等于2002年基于英汉词典使用词向量余弦相似度来计算多语言关联话题的检测，并比较了汉到英、英到汉和不翻译等方式的话题相似度[3]。基于平行语料库的方法如双语LDA,通过平行新闻文本得到跨语言话题分布[4,5]；Mimno D等在2009年提出的基于LDA扩展的多语言话题模型在语言差异较大的情况下取得比单语LDA效果略差的话题发现效果。
以上方法均取得了一定效果，但它们都没有在话题发现过程中解决双语话题特征词分布不一致的问题，且必须提前预测话题个数，而跨语言话题发现的语言障碍更增加了准确预测话题个数的难度，因此以上方法效果较差且不适合在线话题发现应用。本文针对以上问题提出基于极大团聚类的汉泰双语话题在线发现方法，采用TextRank算法[6]提取汉泰新闻文本的内容关键词，并结合命名实体和题目首段信息生成新闻特征词序列，再利用双语词典和相似度消歧算法统计汉泰特征词在新闻语料库中的共现关联关系，构建出汉泰特征词共现邻接矩阵，并通过极大团挖掘算法得到初始极大团话题集合，然后对相似极大团聚类得到最终话题集合。本文提供了不同粒度的有序双语新闻话题描述，通过对2016年1月汉泰新闻语料进行话题发现实验，比较了不同极大团话题生成方式及与其它双语话题发现方法的对比效果，结果表明本文的方法在时间效率最佳的同时F值达到了69.03%。
1可信关联规则和极大团算法
关联规则(association rule)旨在从大量数据中挖掘出未知但潜在有用的规则。最早被Agrawal等人利用Apriori算法发现应用交易数据库中项目之间的关联规则，它以项目的支持度和置信度为基础[7,8]。后来，肖波等改进了关联规则，并提出可信关联规则[9](credit association rule)，该规则忽略项目的支持度，只要求规则中的项目支持度在同一数量级而不用关心具体支持度大小，并通过重新定义的置信度，反映规则的可信度，不用考虑具体支持度的大小，从而有效地减少规则发现过程中的时间复杂度。可信关联规则的本质是规则中的任意两项规则满足共现关联关系。本文认为在话题新闻文档中，话题特征词满足可信关联规则，例如2016年1月6日的热点话题，朝鲜氢弹试验。在该新闻语料库中，朝鲜和氢弹属于共现关联关系，满足可信关联规则定义，同时因数据稀疏等原因，在语料库中不是每个话题特征词都满足支持度的要求。
2汉泰跨语言话题在线发现过程
2.1 TextRank算法提取新闻关键词和生成新闻信息
同一文本中，词汇为表达同一主题，一般词与词之间存在一定的语义关系。通过TextRank算法抽取每篇汉泰新闻的关键词，该算法本质上是一种基于图的排序算法，把汉泰词汇看作图中的顶点，顶点之间通过无向边，反映它们之间的关系。根据基于图的排序算法的基本理论,可以在具有语义关系的词语之间建立连线，并根据词语之间的相互“投票”递归计算词语分数,每个词的得分取决于其它词投票分数和投票词自身的分数大小。选择得分高的词语记为重要词语，不和任何词语有连线的词语记为孤立点[6,11]。Mihalcea R等已经证明图是否有向不会对关键词抽取有太大影响。本文采用无向图模型，在图中进行迭代计算每个词的得分，得分越高说明该词越重要，最后每篇汉泰新闻文档得到对应的前K个最重要关键词。候选词得分计算公式如公式1：
公式1中，WS(Vj)为顶点Vj即词j的得分，d为两部分得分的分配比例，Link(Vi)为与点有连线的点的集合。
本文分析关键词序列后，发现关键词序列可以包含新闻文本大部分内容，但仍有一定信息缺失。因此在关键词序列的基础上，增加了新闻文本中出现的命名实体和除关键词序列以外的题目和首段出现的词。命名实体可以反映话题事件要素，如地点对象等，首段和标题中的词接近新闻主题。利用关键词、命名实体和标题首段词构建的新闻特征词序列更接近新闻的主题。
2.2基于可信关联规则挖掘汉泰跨语言话题极大团
挖掘话题极大团理论基础为相关话题特征词共现关联关系，本文通过汉泰双语词典和汉语候选翻译词相似度消歧算法解决汉泰特征词关联关系的统计问题。
2.2.1汉泰特征词相似度消歧算法
本文考虑从泰语到汉语的翻译，将泰语文本用实验室开发的词法分析工具[19]进行分词词性标注、实体识别，并通过2.1的过程生成新闻特征词序列，词序列中的词基于双语词典结合词性找出汉语译词，因汉泰语言差异性，汉泰文本特征词中存在着部分歧义词，通过TextRank算法找出为待翻译泰语词投票打分最高的5个无歧义泰语名词，打分最高表明这五个名词与待翻译词联系最为紧密，将五个名词翻译为汉语词，通过候选译词与五个汉语词之间的相似度进行判断，相似度最高的词为汉语译词。例如
在泰汉双语词典中有两个解释义项，原子核的化学、物理或与之有关的核裂变或聚变链式反应（原子核）和生物中细胞核[17]，而与
相关的五个无歧义泰语名词翻译为汉语名词或命名实体后为朝鲜、国家、金正恩、武器和地震，很明显原子核较细胞核与五个关联词之间词分布相似度更高。判断汉语译词为原子核。
本文通过谷歌word2vec[12]工具计算词相似度。word2vec是Google在2013年开源的一款将词语表征为实数值向量的高效工具，向量空间上的相似度可以用来表示词汇语义相似度。把搜狗实验室的新闻语料分词用word2vec训练，得到每个汉语词200维词向量分布表示，利用余弦相似度计算任意两个词的相似度。
2.2.2汉泰一对多映射词典
汉语与泰语语言文化差异及新闻报道中的简写省略现象使一些汉泰话题特征词之间不是简单的词对齐关系，泰语存在动词名词化[13]和简单词组合形成的复合词[14]，如快递在汉语为一个词而在泰语中为 /件, /快（即快的东西）。汉语中的一些短语对应泰语一个词，同样也存在泰语中的一些短语对应汉语一个词，因此，本文制定了一个特殊汉泰词表，包含从泰语到汉语分词粒度不同但意义相同的汉泰词典适合双语新闻中汉泰词翻译，部分词示例如表1：
2.2.3汉泰词汇语义相似翻译
因汉泰新闻文本中对同一事件描述方式和详略程度不同，导致两种语言新闻报道内容上的用词差异。例如2016年1月9日的一例新闻，中国新闻为中国女游客泰国亲吻蟒蛇被咬，泰国的报道则为中国女游客在普吉岛亲吻蟒蛇被咬，可以看出中泰两国对该事件关注程度不同，中国报道关心是在泰国发生的，但在泰国国内的报道更关心是在普吉岛发生事故，虽然普吉岛与泰国不是同义词，但因中泰两国对同一事件的关注点不同，普吉岛在该话题下可代表泰国，即普吉岛泰国，两个词之间存在着部分整体关系。普吉岛属于泰国，类似的例子还有北京和中国，华盛顿和美国，永暑礁和南沙群岛等。本文认为在没有同义词情况下，部分可以代替整体，但反之不行，即泰国不能代替普吉岛。由于Wordnet能较好地反映词汇之间语义关系，且英文WordNet语义信息资源最丰富，利用不同语言版本间的WordNet同义词集合的synset_id对应关系，构建中泰文WordNet[14]与英文WordNet对应关系，即可在英文版WordNet上查询汉泰词的同义和部分整体语义关系。
2.2.4汉泰特征词二项可信集构造
可信关联规则和极大团算法[9]依据邻接矩阵来构造二项可信集和可信关联规则。本文把2.1节生成的汉泰特征词序列集去重，对泰语词按章节2.2.1-2.2.3的方式找到汉语译词形成汉泰等价词对，如果汉语独有词或泰语独有词没有合适的译项，则只以汉语或泰语形式表征，形成汉泰特征等价词表并将该词表按顺序标号。本文把邻接矩阵记为A，矩阵中的项为aij,i为行索引，j为列索引，它们均从0 开始，i和j代表了汉泰等价词表的一个词id号，id为i的特征等价词对记为wordi,等价词对中汉语部分或泰语部分在语料库中出现就认为该等价词对出现。按如下方式构造aij：a)当i＝j时,wordi每在一篇文档正文中出现则aii+1,如果该词出现在一篇文档标题或首段第一句，aii+2，每篇文档只对aii计数一次，取最大的加值。例如wordi在一篇文档中出现两次，一次出现在标题一次出现在正文则这篇文档对aii计数+2，不重复加;
b)当i≠j时，wordi与wordj从未出现在同一篇新闻中,则aij为0；
c)当i≠j时，wordi与wordj同时出现在一篇新闻文本标题中，aij+2,如果wordi、wordj出现在正文中或两者仅有一个词出现标题首段首句而另一个词出现在正文中aij+1，同样每篇文档只对aij计数1次，取最大加值。
通过以上过程构造出邻接矩阵A，aii反映了wordi在汉泰新闻语料库中出现的文本频度，aij反映了wordi与wordj共同出现的文本频度。通过邻接矩阵A进一步构造出二项可信集矩阵C，C中的元素cij反映了词wordi与wordj的共现关联关系,定义cij初始计算公式如下：
然后判断cij是否大于最低置信度θ。如果cij值大于本文认为wordi与wordj之间存在可信关联关系，cij更新为1，否则cij为0，最终生成二项可信集矩阵C，遍历矩阵C可以找出所有二项特征词可信关联关系集合。
2.2.5挖掘话题特征词极大团
以上生成的两项可信集矩阵记为C2，由于一个话题需要更多特征词表示，因此需要完成从k项可信集到k+1项可信集的构造，即矩阵Ck->Ck+1。本文按如下算法生成k项可信集:
1)初始状态为之前通过计算得到的2项可信集,记为C2。这一步需要建立由Ck到Ck+1的生成。从Ck中的任意选取两k项集,如果这两个集合的前k-1项完全相同且这两个k项集的最后一项出现在2项可信集中,则前k-1项和这两个k项集的最后一项成为Ck+1的候选集。然后判断其它所有k项集是否可信,如果可信,则产生Ck+1并标记其所有k项子集。当所有工作都完毕之后,如果存在k项集不可信,则它们不能合并。如2项可信集生成3项可信集过程中，朝鲜，氢弹与朝鲜，金正恩合并生成3项候选可信集并检查该3项可信集的任意子项均为可信集，即（朝鲜，氢弹），（氢弹，金正恩），（金正恩，朝鲜）均满足最低置信度，满足极大团挖掘算法要求，生成(朝鲜，氢弹，金正恩)3项可信集。
2.3极大团话题聚类生成准极大团话题
本文对以上过程生成的话题分析，发现生成的话题很多，但由于汉泰两国的语言文化、媒体翻译解释偏差和两国舆论对同一话题的角度及立场情感程度不同等原因，导致同一话题的汉泰语表示不同，即话题分布不一致。例如表2中的汉泰新闻话题：
q因汉泰话题的分布不一致，导致生成的话题极大团存在着差异。有些极大团符合该话题的汉语和泰语的新闻报道，但也存在一些极大团只接近话题的单语言报道。仔细分析这些话题,是关于朝鲜核试验的朝鲜国内和其他国家的反应，文本中中国、美国、俄罗斯等为同类词，反对与谴责也是近义词，考虑到汉泰话题虽然分布不完全一致但应属于同类话题，且一个话题包含的事件应当紧密联系而不同话题间接近正交，本文对满足一定相似度话题进行聚类生成准极大团。话题相似度按如下公式计算：
其中wi∩wj为两话题间同义及相似词对数，存在一对相同或同义词wi∩wj+1，如果存在一对相似词如中国与美国，反对与谴责，wi∩wj+0.5，主要通过word2vec查询汉语词的相似度，两词相似度超过0.5本文认为词相似。min(wi,wj)为两篇文档中词数较少所包含的词个数。合并极大团的步骤为：
1)载入全部的极大团集合,将每个团都放入一个词队列中,每个词初始权重计为1，将此数据结构放入链表中；
2)从链表中取出第一个团,并计算其与其他团的相似度；
3)如果都不相似,则将第一个团放入结果集中,回到步骤2,继续；
4)如果与第m个团通过公式3计算相似,则对两个团的词进行聚类统计,具体做法是相同词权重加1，相似词合并为词组权重加0.5,不同也不相似的词权重不变，对统计后词序列筛选去除权重小于1.5的词，筛选后的词组加入到新的团中,然后将新团放入链表m的位置替换掉原先的,再删掉第一个团,回到步骤2,继续；
5)直到链表为空结束。通过以上过程，话题1和话题2合并为如下话题准极大团：
{}表示一个相似词组，[]表示词在话题中权重。合并后词组再与其它词进行相似度计算时，则计算词与词组中的各个词的相似度累加求算术平均值即为词与该词组的相似度，同样本文认为超过0.5且与词组中的词词性一致为相似。
话题1和话题2聚类生成的话题准极大团与话题3按上面的方法聚类生成如下结果：
通过极大团聚类过程使一些特征词分布不一致但满足语义相关关系的双语话题合并，合并后的准极大团话题描述纯度较高，减少了噪音词对话题描述的影响，较真实地表示话题的汉泰双语内容。
2.4话题的个性化推荐
在互联网实时产生海量数据的今天，人们面对各种信息往往无从下手。本文设计的汉泰双语话题在线发现方法，向用户推荐话题合并后简略的准极大团话题描述，如果用户对某个话题事件较为感兴趣，向其推送聚类前关于该话题的极大团队列，对极大团队列中的汉泰双语话题分别计算与新闻语料库中文本相似性，取最相似新闻文本时间为话题出现时间，按话题出现时间排序，向用户提供关于该话题的有序话题集合，从而以双语形式反映话题事件的发展情况。关于朝鲜氢弹试验话题的个性化推荐结果如表3所示
3实验及评价
本文设计两组任务来考察汉泰双语话题在线发现效果，1.围绕不同关键词抽取方式来进行极大团汉泰双语话题发现效果比较；2.将本文方法与其它主流双语话题发现方法进行比较。实验语料集选取了2016年1月中泰两国互联网上的双语话题新闻语料161篇，包含汉语新闻86篇，泰语新闻75篇，涉及国际、东盟、经贸、文化娱乐四方面16个话题。
首先比较了不同关键词抽取方法的汉泰极大团话题发现效果，实验设计TextRank算法与主流的TF-IDF关键词抽取算法和不抽取关键词生成话题效果比较，TextRank设置共现窗口为5，阻尼系数d为0.85，可信关联规则置信度为0.22。评价指标包括了话题发现正确率，召回率和F值。
表4为不同关键词抽取方法的极大团话题发现效果。分析原因TF-IDF在汉泰文本抽取关键词过程中需要考虑词在其它文本的反频率外部知识但在汉泰词汇翻译过程中不可避免造成特征值偏差，本文认为TF-IDF适合需要找出文本差异特征的任务，如文本分本分类等，而不适合对单篇文本描述任务；极大团方法需要从汉泰新闻文本中找出文本间的共性，因此TextRank较TF-IDF更适合双语极大团话题发现；不抽取关键词直接移除了停用词后的全文词汇，生成的话题极大团包含的信息更全面因此效果最好，但也包含一些噪音和翻译错误，最终F值只比TextRank略好。考虑到不抽取关键词增加了邻接矩阵维度和翻译消歧次数，从而大大增加时间复杂度，因此本文采用TextRank抽取关键词生成话题。
为验证本实验的效果和性能，实验2将本文方法同主流的双语话题发现方法基于机器翻译的kmeans[16]文本聚类和双语LDA[4,5]进行比较。其中文本聚类和双语LDA方法需要提前指出话题个数K值，K值设为16。本文选取中国国际广播电台关于中国百科的汉泰平行文本621篇作为LDA模型的训练集，α=50/K，β=0.01，LDA方法只能筛选主题分布概率权重超过0.03的话题。
通过图3和表5可以发现：
a)本文方法F值最高，其次双语ＬＤＡ，文本聚类效果最差。文本聚类时需要进行话题向量与文档向量及文档向量之间的相似度比较，因需要跨语言文本层面的特征向量聚类，故不可避免相对本文词聚类方法增加了噪音特征和翻译错误。
b)双语LDA的双语话题发现效果并不是特别理想，分析认为双语LDA的训练集不能完全覆盖所有的话题分布；对新话题发现能力较差且每个话题都有固定数目的词项组成而在实际中话题的描述词数是不固定的；双语话题的对齐效果完全依赖于LDA平行语料训练集的数量和质量。尽管大规模收集汉泰新闻平行文本训练话题模型可以提高双语LDA的F值，但目前互联网汉泰平行语料特别是新闻平行语料资源稀少且需要较多人力及语言学知识参与，平行语料的质量不稳定影响双语LDA的效果。
c)本文方法通过TextRank算法选取关键词过滤了一定噪音，通过可信关联规则实现词聚类生成极大团，并聚类合并相关双语话题生成准极大团话题，取得了最高的效果。同时随着Twitter、微博等短文本社交媒体日益成为新闻事件的重要发布源，语料库中包含一定的短文本新闻，而K-means与LDA对短文本的建模能力较差[19]导致话题发现效果上逊色于本文的方法。准极大团话题有较好的话题纯度（与话题无关的噪音少），且召回率相对较高且不需要估计话题个数。
d)在时间复杂度上，由于抽取了新闻文档的关键词，进而大大减少了词处理对象的数量级，也没有Kmeans与LDA的文本迭代收敛过程，本文方法时间复杂度最低，最适合汉泰双语在线话题发现应用。
4结语
本文通过极大团聚类将跨语言词聚类生成双语话题，合理地解决了话题在双语环境下分布不一致问题，同时有效地解决了传统话题发现方法需要估计话题个数的缺陷。在时间复杂度最低同时取得了最佳效果，为双语话题在线发现应用提供了一种合理思路。下一步工作考虑将时间因素融入话题发现模型，并研究更合理的方式解决汉泰话题的特征词分布不一致问题，以期取得更好的双语话题发现效果。
参考文献
[1] Leek T, Jin H. The BBN Crosslingual topic detection and tracking system [C].WorkingNotes of the Third Topic Dectection and Tracking Workshop,2G00.
[2] Wactlar H D. New Directions in Video Information Extraction and Summarization [J]. Australian Veterinary Journal, 1999, 64(8):229–232.
[3] Chen Y J, Chen H H. NLP and IR Approaches to Monolingual and Multilingual Link Detection [C]// International Conference on Computational Linguistics-volume. 2002:1--7.
[4] Mimno D, Wallach H M, Naradowsky J, et al. Polylingual Topic Models. [C]// Empirical Methods in Natural Language Processing. 2009:880--889.
[5] Ni X, Sun J T, Hu J, et al. Mining multilingual topics from Wikipedia [C]// Proceedings of the 18th International Conference on World Wide Web, WWW 2009, Madrid, Spain, April 20-24, 2009. 2009:1155-1156.
[6] Mihalcea R, Tarau P. TextRank: Bringing Order into Texts [J]. Unt Scholarly Works, 2004:404-411.
[7] Agrawal R, Imieli&#, Ski T, et al. Mining association rules between sets of items in large databases [J]. Acm Sigmod Record, 1993, 22(2):207-216.
[8] Agrawal R, Srikant R. Fast algorithms for mining association rules. 20 [J]. Proc.int.conf.very Large Databases Vldb, 1994, 23(3):21-30.
[9]肖波,徐前方,蔺志青等.可信关联规则及其基于极大团的挖掘算法[J].软件学报, 2008, 19(10):2597-2610.
[10]李春英,汤庸,汤志康,等.面向大规模学术社交网络的社区发现模型[J].计算机应用, 2015, 35(9):2565-2568.
[11]杨洁.多文档关键词抽取技术的研究[D].沈阳航空工业学院沈阳航空航天大学, 2009.
[12] Mikolov T, Sutskever I, Chen K, et al. Distributed Representations of Words and Phrases and their Compositionality[J]. Advances in Neural Information Processing Systems, 2013, 26: 3111-3119.
[13]罗奕原.基础泰语[D].世界图书出版公司2011 [14]裴晓瑞.泰语语法新编[D].北京大学出版社出版2001 [15] Thoongsup S, Robkop K, Mokarat C, et al. Thai WordNet Construction [C] In:Proceedings of the 7th Workshop on AsianLanguage Resources. Association for Computational Linguistics, 2009: 139-144.
[16]袁方，周志勇，宋鑫.初始聚类中心优化的k-means算法[J].计算机工程, 2007, 33(3):65-69
[17]陈安龙,唐常杰,陶宏才,等.基于极大团和FP-Tree的挖掘关联规则的改进算法[J].软件学报, 2004, 15(8):1198-1207.
[18]泰语词法分析工具[EB/OL]. http://222. 197.200.124/seanlp/lexer/th
[19]泰语词典[EB/OL]. http://www.thai-language.com/ [20]韩忠明,张慧,张梦,等.大规模短文本的快速话题发现方法与评价研究[J].计算机应用研究, 2015, 32(3):717-722.
基金项目:老挝语词法分析及老汉双语平行语料抽取方法研究(61662040)