摘要通过分析英语新闻报道的特点，提出了一种基于词汇区分和位置特征相结合的特征项抽取算法．词汇区分是指将单词分为首字母是大写的单词和首字母不是大写的单词，位置特征利用新闻报道的倒金字塔式的结构特点决定单词的重要性．提出了一种基于多个特征项抽取算法融合的特征项权值计算方法，该方法认为被越多的特征项抽取算法选中的特征项越重要．提出了一种基于多数投票策略的双重过滤算法，对报道和话题是否相关进行两次过滤，大大降低了系统的误报率．实验表明提出的3种算法不但取得了很好的效果，而且具有很好的可扩展性．
关键词话题跟踪；词汇区分；多数投票策略；双重过滤；归一化检测开销
技术．给定的与某个话题相关的新闻报道的个数用N￡表示，通常情况下，M=1，2，4．基于查询向量的方法是话题跟踪研究中简单而应用广泛的方法-l。J，其核心思想是根据训练集中的新闻报道构建一个查询向量，然后计算被跟踪的新闻报道与该向量的相似度，根据相似度与阈值的比较做出报道和话题是否相关的判断．基于分类算法的改进算法也是比较常用的话题跟踪算法，常用的分类算法有KNN算法L4。6J、决策树算法№J、Rocchio方法【5'7j以及SVMH J等，研究者们还尝试将多种分类算法结合起来实现话题跟踪Mj』．
另外，还有应用于广播新闻跟踪的基于HMM的方法【8 J．本文对基于查询向量的英语话题跟踪研究中的几个关键问题进行了探讨：特征项抽取、特征项权值计算以及报道和话题的相关性判断．目前常用的特征项抽取算法都未能充分体现话题跟踪面向新闻领域这一特点，结合对英语新闻报道的分析，提出了一种基于词汇区分和位置特征相结合的特征项抽取算法．词汇区分是指将单词区分为首字母是大写的词和首字母不是大写的词；位置特征利用新闻报道的头重脚轻的倒金字塔式结构【4』，认为出现在报道较前部分的单词比出现在报道较后部分的单词重要．为了突出表达话题内容的关键词汇，提出了一种基于多个特征项抽取算法融合的特征项权值计算方法，按照本文提出的“一个为主，其余为辅”的策略融合了TFIDF(即根据单词的tfidf值的高低抽取特征项)，IG，MI及CHI四个特征抽取算法旧j，认为被越多的抽取算法选中的特征项越重要．在话题跟踪研究中，通常在给出最后的相关性判断前只进行一次相似度比较．分析跟踪结果发现：不同的相似度函数都能正确地判断大部分相关报道，但是不同的相似度函数引入了不同的错误判断．鉴于此，提出了一种基于多数投票策略的双重过滤算法，该算法对于每个被跟踪的报道进行两次过滤，根据两次过滤的结果做出最后决策．
1基于词汇区分和位置特征相结合的特征项抽取算法(简称为CAPLOC算法)
本文采用单个单词作为查询向量的特征项．在抽取特征项之前，首先对新闻报道进行预处理，包括去停用词和词形还原．本文首先验证了TFIDF，CHI，MI，IG四种常用的特征项抽取算法在话题跟踪系统中的性能，结果发现：基于TFIDF抽取算法的系统性能最为稳定，受特征项个数的影响最小．由于实验中N￡=1，所以相关报道中的所有的单词的DF都是1，所以此处没有验证DF抽取算法的性能．
CAPLoC算法基于英语新闻报道的以下两个特点提出：
1)在英语报道中，表示名称(人名、地名及机构名)的单词的首字母通常都大写，而名称是区分相似话题的关键信息．基于此，本文提出了词汇区分的思想，即将单词区分为首字母是大写的词和首字母不是大写的词，并认为前者比较重要．
2)新闻报道具有独特的头重脚轻的倒金字塔式结构，一般把最重要的事实写在报道的开头部分，所以我们认为出现在报道较前部分的单词具有较高的重要性．结合以上的分析，CAPLOC算法抽取特征项的过程是：
1)使用式(1)计算给定的相关报道中所有单词的平均权值；
2)将所有的平均权值作降序排序，抽取前弘个平均权值较高的单词作为查询向量的特征项．
1)如果单词忌在第i个相关报道中的首字母不是大写的，那么C倪声(i，忌)=1；否则Cap(i，忌)=口，其中口>1，是一个可调参数，实验中a=1．5．
2)如果单词忌在第i个相关报道中的序号除以第i个相关报道的长度大于A，那么Loc(i，忌)=1；否则k(j，忌)=p，p>l，A和卢都是可调参数，实验中口=1．5，A=1／3．报道长度等于报道中出现的单词的总数，报道中出现的第1个单词的序号为1，后续出现的单词的序号依次累加；若某单词在报道中出现多次，那么该单词的序号定义为其第1次出现时的序号．
上述的CAPLOC算法是基于TFIDF抽取算法实现的(公式(1)中硼漫由tfidf公式计算)，但叫艟也可由其他的特征项抽取算法来计算，也就是说CAPLOC算法具有很好的可扩展性．
2基于多个特征项抽取算法融合的特征项权值计算方法话题之问
通常只是通过少数几个关键词汇来相互区分[11]．为了更加有效地突出这些关键词汇，提出了基于多个特征项抽取算法融合的特征项权值计算方法．该方法认为每种特征项抽取算法都只能反映单词在某一方面的重要程度，被越多的特征项抽取算法选中的特征项的重要性越高，权值也应该越高．我们提出了一种“一个为主，其余为辅”的融合策略对多个特征项抽取算法进行融合．算法1中融合了TFIDF，CHI，MI，IG四种特征项抽取算法，其中以TFIDF抽取算法为主，其余3种算法为辅．
算法1．基于多个特征项抽取算法融合的特征项权值计算方法．输入：话题的训练集；输出：表示该话题的查询向量QⅡP删．
1)设将要抽取的特征项个数为口；
2)分别使用TFIDF，CHI，MI，IG四个算法抽取特征
项3基于多数投票策略的双重过滤算法基于查询向量的话题跟踪研究中，通常只基于一次相似度比较便做出报道和话题是否相关的判断．实验发现不同的相似度函数都能正确的识别大部分的相关报道，但是不同的相似度函数却引入了不同的错误判断．受多分类器融合思想的启发，我们认为将多个相似度函数结合起来，使它们优势互补，应该能有效地提高话题跟踪系统的整体性能．多分类器融合是指将多个分类器得到的分类信息进行综合，从而得出最终的分类结果．
多分类器融合可以充分发挥各个分类器的优势，为提高系统的性能提供了新的思路．多分类器融合有两种实现方式：分类器输出综合及动态分类器选择，前者指并行利用各个分类器，然后用某种融合方法将它们的输出综合以获得一致决定；后者指对每个输入样本选择最可能分类正确的分类器，并将该分类器的输出结果作为最后决定。
4实验及结果
分析本文采用LDC提供的TDT Pilot语料作为评测语料，该语料包含15863个英语报道，所有报道组成一个文本文件，报道时间从1994年7月1日到1995年6月30日．语料中定义了25个话题，涵盖了所有报道所涉及的部分话题．
4．1 评价标准
依据TDT评测标准，本文采用归一化检测开销(CD。。)Nor。来评测话题跟踪系统的性能 。
4．2实验结果分析
为了验证本文提出的各个算法的有效性，设计了4组实验．所有实验中N￡=1，其中的相似度阈值经验确定．第1组实验验证了TFIDF，CHI，MI，IG以及本文提出的CAPLoC五种特征项抽取算法在不同特征项个数下的性能．
1)从CAPLoC算法和TFIDF算法的性能对比可知，CAPLOC算法取得了很好的效果，说明词汇区分和位置特征的使用发挥了很好的作用．
2)特征项个数比较小时，TFIDF和CAPLoC算法的性能明显好于IG，CHI，MI；特征项个数比较大时，几种抽取算法的性能几乎相当．TFIDF抽取算法和CAPLOC抽取算法性能比较稳定，受特征项个数的影响比较小．
3)无论采用哪种特征项抽取算法，话题跟踪系统的性能随着特征项个数的增加而改善，但是当特征项个数大到一定程度时(>90时)，性能开始下降．这是因为当特征项个数较大时，反映报道内容的关键词汇的作用将会被掩盖，从而影响系统的性能．第2组实验验证了基于多个特征项抽取算法融合的特征项权值计算方法的有效性．
为此，我们做了4个实验．第1个和第2个实验是使用TFIDF作为特征项抽取算法，其中第1个实验中使用式(2)计算特征项权值，记做豫fDF—TFmF，第2个实验使用以TFIDF为主，CHI，MI，IG为辅的多个特征项抽取算法融合的方法计算权值，记做TFmF—COM；第3个和第4个实验都采用cAPLoC算法抽取特征项，第3个实验采用式(2)计算特征项权值，记做G栌己oC一丁F四F，第4个实验使用以CAPLOC为主，CHI，MI，IG为辅的多个特征项抽取算法融合的方法计算权值，记做CAPLoC—COM．本组实验同样使用Cosine函数作为相似度判定函数，相似度阈值设为0．3．
5 结论
本文对基于查询向量的英语话题跟踪研究中的关键问题进行了探讨，提出一种基于词汇区分和位置特征相结合的特征项抽取算法、一种基于多个特征项抽取算法融合的特征项权值计算方法以及一种基于多数投票策略的双重过滤算法．实验结果表明，本文提出的这3种算法都取得了很好的效果，且具有很好的可扩展性，由此可得到以下几个结论：
1)特征项抽取、特征项权值计算以及相似度比较策略是基于查询向量的话题跟踪研究中的关键问题，对其中任何一个方面改进都可以提高系统整体性能；
2)话题跟踪研究的对象是新闻报道，所以合理的应用新闻报道的特点将会对话题跟踪的研究起到很大的帮助，如本文的词汇区分与位置特征的使用；
3)多分类器融合的思想在话题跟踪领域也可以发挥很好的作用．
