基于关联规则后件扩展的越英跨语言信息检索

黄武锋，何冬蕾，黄名选

(广西财经学院 信息与统计学院，广西 南宁 530003)

1 概 述

跨语言信息检索(cross-language information retrieval，CLIR)指的是以一种语言的查询去检索其他语言信息资源的技术，其中表达查询的语言称为源语言，所检索文档的语言称为目标语言。长期以来，跨语言信息检索存在严重的查询主题严重漂移、词不匹配以及查询项翻译歧义和多义性等问题，这些问题一直是制约跨语言信息检索技术发展的瓶颈。近年来，跨语言信息检索模型研究取得了丰富的研究成果，主要集中在基于查询翻译优化的和基于查询扩展的跨语言信息检索等方面。

基于查询翻译优化的跨语言信息检索针对源语言查询翻译过程中如何得到最优的、最准确的目标语言查询项开展研究。其典型的工作有：Geraldo等[1]提出了基于关联规则挖掘的西班牙语-英语跨语言信息检索方法；姚寒冰等[2]针对跨境电商涉及不同语言的供需双方信息的跨语言检索需求，提出了基于自然语言的跨语言协同机器翻译的信息检索算法；吴丹等[3]提出基于相关反馈的跨语言信息检索查询翻译优化技术；Giang等[4]提出基于词典翻译的越英跨语言信息检索方法，在此基础上提出了基于伪相关反馈的越英跨语言检索模型[5]，有效提升了检索性能；Debasis等[6]分别为源语言文档和目标语言文档估计一个基于主题的相关性模型，在此基础上，Wang等[7]提出了基于主题模型和伪相关反馈的跨语言信息检索系统，取得了良好的实验结果；刘伟成等[8]提出基于核典型相关分析算法的中英跨语言信息检索方法，实验结果证明了该方法的有效性。

基于查询扩展的跨语言信息检索研究的核心问题是如何得到原查询相关的扩展词实现跨语言查询扩展，以改善和提高跨语言信息检索性能。其典型的工作有微软亚洲研究院Gao等[9]提出的两步伪相关反馈法，在此基础上，吴丹等[10]通过计算前列n篇初检文档的语词权重并降序排列，抽取权重比较高的前列m个语词作为扩展词实现跨语言查询扩展，同时深入研究跨语言查询翻译前扩展、翻译后扩展以及两者结合的扩展效果。Lam等[11]结合词分布表示方法和查询词与扩展词间的互信息计算扩展词权值实现跨语言信息检索，黄名选[12]提出一种基于矩阵加权关联模式的印尼-中跨语言信息检索模型，均取得了良好的实验效果。

当前，针对东盟小语种越南语言的跨语言信息检索研究报道不是很多，而中国与越南的政治、经济、文化等往来更加频繁和密切，面向越南语言的跨语言信息检索研究显得更加迫切和重要。为此，在原有的研究基础上，文中开展面向东盟国家语言的跨语言信息检索研究，提出一种基于完全加权关联规则后件扩展的越英跨语言信息检索模型。

2 融合完全加权模式挖掘与查询扩展的越英跨语言信息检索模型

2.1 模型基本思想

检索模型将越南语查询式通过机器翻译系统翻译为英文查询式，在原始英文文档集中检索英文文档，提取前列n篇初检英文文档提交给用户，通过用户的相关性判断得到用户相关反馈初检文档，采用基于支持度-条件概率增量比-兴趣度评价框架的完全加权词间关联规则挖掘技术对该文档进行挖掘，得到与原查询相关的关联规则模式，从规则模式中提取扩展词，和原查询组合成新查询再次检索原始英文文档集，得到最终检索结果，即英文文档结果集，再通过机器翻译系统将结果文档翻译为越南语文档，返回给用户。

2.2 模型结构图及其功能模块

根据上述检索模型的基本思想，给出了融合完全加权模式挖掘与查询扩展的越英跨语言信息检索模型结构，如图1所示。该检索模型结构由6个模块和2个数据库组成，即文本翻译模块、文本检索模块、初检结果用户相关反馈模块、面向越英跨语言检索的完全加权关联模式挖掘模块、越英跨语言查询扩展词生成模块和越英跨语言查询扩展实现模块，以及完全加权关联规则库和英文扩展词库等。各个模块的功能简述如下：

图1 融合完全加权模式挖掘与查询扩展的 越英跨语言信息检索模型结构

文本翻译模块：该模块的功能是将越南语用户查询式翻译为英文查询式，将最终检索结果英文文档翻译为越南语文档。文本采用现有的机器翻译系统作为文本翻译模块，即微软的必应机器翻译接口(Microsoft translator API)。

文本检索模块：该模块负责将翻译后的查询和原始文档集合中的文档进行相似度计算，并降序排列相似度，将排在前列的相似文档返回给用户。文中采用经典的、传统的向量空间模型方法计算查询与文档的相似度，即计算查询向量和文档向量之间夹角的余弦值作为其相似度值。

初检结果用户相关反馈模块：该模块负责收集用户对初检英文前列文档的相关性判断结果，提取被判断为相关的初检文档构建用户相关反馈文档集，同时，对该文档集进行英文词干提取、去除停用词和提取特征词等预处理。

面向越英跨语言检索的完全加权关联模式挖掘模块：该模块的功能是运用基于支持度-条件概率增量比-兴趣度评价框架的完全加权词间关联规则挖掘技术对用户相关反馈文档集进行挖掘，得到包含有原查询词项的完全加权频繁项集和词间关联规则模式，构建完全加权关联规则库。

越英跨语言查询扩展词生成模块：该模块负责从完全加权关联规则库中提取扩展词，计算其权值，构建英文扩展词库。

越英跨语言查询扩展实现模块：该模块负责从英文扩展词库提取扩展词，将扩展词和原查询词组合为新查询提交到文本检索模块对原始文档集再次进行检索，得到最终检索的英文文档集，并将其送到文本翻译模块翻译为越南语文档集，最后将最终检索结果的越南语文档及其对应的英文文档返回给用户界面。

2.3 模型关键技术

2.3.1 面向越英跨语言检索的完全加权词间关联模式挖掘

面向越英跨语言检索的完全加权词间关联模式挖掘基本思想是：采用基于支持度-条件概率增量比CPIR-兴趣度评价框架的完全加权关联模式挖掘技术，结合用户原查询信息，对越英跨语言检索初检结果用户相关反馈文档集挖掘与原查询相关的完全加权频繁项集和关联规则模式。其中采用文献[13]的支持度计算公式计算关联模式的支持度，将条件概率增量比CPIR作为关联模型的置信度，其计算公式详见文献[14]，对关联模式进行兴趣度评估，其评估公式采用文献[15]的关联模式兴趣度计算公式。在挖掘过程中，采取如下剪枝策略：剪除项集频次或者权值为0的候选项集；当挖掘到2_项集时，只保留含有原查询词的候选2_项集，其他的剪除；从候选2_项集以后，对应每个候选项集，如果包含该项集的后续(k+1)_项集权值阈值KIWT(k,k+1)[16]大于该项集权值W(k)，根据文献[16]的定理，可以剪除该候选项集。

上述挖掘思想可以形式化为算法AWAPM_CLIR(all-weighted association patterns mining for cross language information retrieval)：

算法1：AWAPM_CLIR。

输入：QV(越南语用户查询)，DocCLIR(跨语言初检英文相关反馈文档集)，ms(最小支持度阈值)，mc(最小置信度阈值)和mi(最小兴趣度阈值)；

输出：awARq(含有译后英文原查询词项的完全加权关联规则模式集合)。

Begin

1.Let awFIq←Ø；awARq←Ø;

//清空完全加权频繁项集模式集合awFIq及其关联规则模式集合awARq

2.Preproc(DocCLIR);

//对初检英文相关文档进行词干提取、去除停用词和提取英文特征词等预处理工作。模型中所用的英文词干提取程序是Porter程序(见http://tartarus.org/～martin/PorterStemmer)

3.MiningawL1(DocCLIR);

//挖掘完全加权频繁1_项集awL1

3.1 扫描文档集DocCLIR，计算完全加权候选1_项集C1的权值w(C1)

3.2 计算文档集DocCLIR中所有项目权值的总和W

3.3 if(w(C1)/W≥ms) thenL1←C1，awFIq←aw FIq∪L1

3.4 计算KIWT(1,2)的值。KIWT(1,2)[16]的计算公式见文献[16]

4.for(k=2;Ck≠Ø;k++)

//挖掘含有原查询项的完全加权频繁k_项集Lk

{

4.1 if(W(Ck-1)

4.2Ck←CreateCk(Ck-1);//通过Aproiri连接[17]产生候选项集Ck

4.3 if (k=2) then {剪除不含英文查询项的候选2_项集C2}

4.4 计算Ck权值w(Ck)和KIWT(k,k+1)的值。KIWT(k,k+1)[16]的计算公式见文献[16]

4.5 if(w(Ck)=0) then {剪除该候选项集Ck}

4.6 if(w(Ck)/W≥ms)thenLk←Ck，awFIq←aw FIq∪Lk

4.7 if(k大于给定的所挖掘的候选项集长度阈值)then break;

}

5.对于完全加权频繁项集模式集合awFIq中的每个频繁项集Lk，挖掘中所有含原查询项的完全加权关联规则(q→Et)，其中，q为Lk中的原查询项项目，Et为Lk中除了原查询项项目以外的项目

{

5.1 计算规则q→Et的条件概率增量比CPIR的值及其兴趣度的值。CPIR值的计算公式见文献[14]，规则兴趣度的计算公式见文献[15]

5.2 if(CPIR的值≥mc and兴趣度≥mi) then awARq←awARq∪{q→Et}；

}

6.output(awARq);

//输出含有查询项的完全加权关联规则

End

2.3.2 越英跨语言扩展词生成

文中跨语言扩展词来源于关联规则q→Et中的后件Et词项，并将其条件概率增量比CPIR和兴趣度作为扩展词权值的计算依据。因此，给出如下扩展词权值WEt的计算公式:

WEt=max(CPIR值+规则兴趣度值)

(1)

此外，对于原查询项的权值Wq的计算详见文献[18]。

根据上述的越英跨语言扩展词产生的基本思想，给出生成算法GetCLawET。

算法2：GetCLawET。

输入：awARq(完全加权关联规则模式集合)；

输出：En_ExpTerm(英文扩展词)。

Begin

1.for 对于awARq集合中的每个规则q→Et do

{

提取规则q→Et的后件Et；

根据式1计算扩展词的权值；

En_ExpTerm←En_ExpTerm∪Et，并将扩展词及其权值存入英文扩展词库;

}

2.ETOutput(En_ExpTerm);

//输出英文扩展词

End;

2.3.3 融合完全加权模式挖掘与查询扩展的越英跨语言检索算法

根据上述给出的基本思想，文中提出的越英跨语言检索算法(Vietnamese-English cross language information retrieval based on all-weighted patterns mining and query expansion，VECLIR_AWAM&QE)具体的描述如下:

算法3：VECLIR_AWAM&QE。

输入：QV(越南语用户查询)，ms，mc，mi，n(跨语言初检前列文档数)；

输出：越英跨语言检索结果(即越南语文档和英文文档)。

Begin

1．QE←QVMachineTranQE(QV);

//接受越南语用户查询式，将其翻译为英文查询式QE

2．DocCLIR←QEText Retrieval_First(QE，n);

//初检英文文档，构建用户相关反馈文档集DocCLIR

for原始英文文档集中的每一篇文档Docido

{

计算查询QE与文档Doci的相似度并降序排列;

提取前列n篇初检文档提交给用户进行相关性判断；

根据用户的相关性判断结果，构建初检用户相关反馈文档集DocCLIR

}

3．awARq←AWAPM_CLIR(QV，ms,mc,mi);

//调用上述挖掘算法AWAPM_CLIR，运行后得到含有原查询词项的完全加权关联规则模式集合awARq

4．En_ExpTerm←GetCLawET(awARq)；

//调用算法GetCLawET，得到英文扩展词及其权值

5．NewQE←QE∪En_ExpTerm;

//将原查询和扩展词组合为新查询

6．En_Doc←NewQEText Retrieval (NewQE);

//扩展后的新查询再次检索得到最终英文文档En _Doc

6.1 for 原始英文文档集中的每一篇文档Docido

计算新查询NewQE与文档Doci的相似度并降序排列;

6.2 提取前列文档作为最终检索结果英文文档En_Doc；

7．Viet_Doc←DVMachineTranDE(En_Doc);

//通过机器翻译系统将最终检索结果英文文档翻译为越南语文档Viet_Doc

8．VEDocOutput(Viet _Doc,En_Doc);

//输出扩展后的检索结果：英文文档和越南语文档

End

3 实验设计及结果分析

3.1 实验数据及实验硬件环境

实验数据是NTCIR-5 CLIR提供的英文语料，即Korea Times的2001年新闻文本(简称为ktn01)，共25.3 MB，以及Mainichi Daily News的2000年和2001年新闻文本(简称为mdn00和mdn01)，共9.9 MB，共计26 224篇，其中ktn01为14 069篇，mdn00为6 608，mdn01为5 547。采用TITLE查询和DESC查询进行实验。NTCIR-5 CLIR语料没有越南语版本的查询集，邀请专门翻译机构将NTCIR-5 CLIR中文版50个查询主题人工翻译为越南语查询，作为实验过程中用到的越南语用户查询。

3.2 基准实验及评价指标说明

文中实验对比算法是单语言检索算法(monolingual retrieval baseline，MRB)、越英跨语言检索算法(cross-language retrieval baseline，CLRB)和传统的基于伪相关反馈扩展的越英跨语言检索算法(Vietnamese-English cross-language retrieval based on pseudo relevance feedback，VECLR_PRF)，即MRB指用英文查询直接检索英文文档得到的检索结果，CLRB指将越南语查询经机器翻译为英文后检索英文文档得到的检索结果，VECLR_PRF指按照文献[10]的跨语言扩展方法来实现越英跨语言信息检索。具体实验参数是：跨语言初检前列伪相关文档数是20篇，跨语言扩展词数是其权值较高的前列20个特征词。使用R-查准率(R-prec)作为实验评价指标。

3.3 实验结果及其分析

为了便于实验的开展，将跨语言初检前列n篇文档中包含的已知结果集中的相关文档当作用户进行的相关反馈信息结果，构建用户相关反馈文档集。运行MRB、CLRB、VECLR_PRF和VECLIR_AWAM&QE等源程序，提交50个越南语的TITLE和DESC查询进行基准检索实验，得到各个算法的实验结果R_prec值如表1和表2所示。实验参数设置如下：n=50，挖掘的项集长度为2，支持度ms变化时：ms∈[0.001,0.002,0.003,0.004,0.005]，mc=0.01，mi=0.000 1，置信度mc变化：mc∈[0.01,0.04,0.06,0.08,0.1]，ms=0.001，mi=0.000 1，兴趣度mi变化：mc=0.01，ms=0.005，mi∈[0.001,0.003,0.005,0.007,0.009]。

表1 文中算法与基准对比算法的检索性能(R_prec)比较(Title查询)

表2 文中算法与基准对比算法的检索性能(R_prec)比较(Desc查询)

由表1和表2可以看出，在TITLE和DESC查询实验中，在支持度阈值ms、置信度阈值mc和兴趣度阈值mi等参数分别变化的情况下，算法VECLIR_AWAM&QE的检索结果的R_prec值均比MRB、CLRB和VECLR_PRF的高，效果比较显著。结果表明提出的越英跨语言信息检索模型是有效的，能有效地减少查询主题漂移，改善和提高跨语言检索性能。

4 结束语

将完全加权关联模式挖掘技术引入越英跨语言信息检索模型，结合用户相关反馈，提出一种基于完全加权关联规则后件扩展的越英跨语言信息检索模型，阐述了检索模型结构及其各个功能模块，以及实现的关键技术，进行了深入的实验分析，实验结果证明了该模型的有效性。下一步是将该越英跨语言检索模型实用化，以便应用到实际的检索系统中。