论文部分内容阅读
【摘 要】话题识别与跟踪旨在实现对新闻媒体信息流中新话题的自动检测以及对已知话题的动态跟踪。本文首先介绍话题识别与跟踪的基本概念、研究任务和相似度计算方法，然后对话题跟踪的方法进行详细论述。
【关键词】话题检测；话题跟踪；文本分类
0.引言
随着信息技术的飞速发展，互联网变得越来越普及，这就造成了网络信息的急剧膨胀，如何在浩瀚的信息海洋中获取自己所需信息成为困扰人类的新问题。话题识别与跟踪（Topic Detection an Tracking,TDT）技术就是在这种情况下产生的。TDT是一种新的信息处理技术，它将新闻信息流以主题为单位进行组织，实现对新闻流中新话题或新事件的自动检测以及对已知话题的后续报道的追踪。从1996年TDT概念的提出，1997年自马萨诸塞大学、卡内基一梅隆大学和Dragon System公司的学者和研究人员对这项技术进行了初步研究[1]，到2007年TDT共举行过七次公开的TDT任务评测，取得了很好的效果，渐渐使得TDT成为研究的热点。
1.TDT的相关技术
1.1基本概念
话题（Topic）是指由某些原因、条件引起，发生在特定时间、地点，并可能伴随某些必然结果的一个事件[2]。
主题（Subject）是与话题相应的一个概念，它的含义更广些。话题与某个具体事件相关，而主题可以涵盖多个类似的具体事件或者根本不涉及任何具体事件。
报道（Story）是指一个与话题紧密相关的、包含两个或多个独立陈述某个事件的子句的新闻片段。
1.2研究任务
美国国家标准技术研究院（NIST）为TDT研究设立了五项基础性研究任务：报道切分任务（SST）：将原始数据流切分成具有完整结构和统一主题的报道。话题跟踪任务（TT）：跟踪已知话题的后续报道。话题检测任务（TD）：检测和组织系统预先未知的话题，TD的特点在于系统欠缺话题的先验知识。首次报道检测任务（FSD）：从具有时间顺序的报道流中自动锁定未知话题出现的第一篇相关报道。关联检测任务（LDT）：裁决两篇报道是否论述同一话题，没有明确话题作为参照，自主地分析报道论述的话题，通过对比报道对的话题模型裁决其相关性。 1.3相似度计算方法
文本相似度是两篇文档相似程度的衡量，常用算法有欧式距离，余弦相似度，Jaccard Coefficient等。在下文的计算公式中xi和xj（i,j=1,2,…,n）为文本集中两个不同的向量，m为向量的维数。
欧式距离（Euclidean Distance）
d(xi,xj)=2
余弦相似度是最常用的一种衡量文本相似度的计算方法，它通过计算两个向量之间夹角余弦值来度量文本之间的相似度。
d(xi,xj)=
Jaccard Coefficient的相关系数衡量了两个文本之间的一致性，文本之间的共同点越多，相关系数值越大，文本越相似。
d(xi,xj)=
2.话题跟踪（TT）方法的研究
在TT中，每个话题实质上是一个类别，对待处理的报道，通常通过比较各个话题的相似度，选择相似度最大的话题类别作为待处理的文本的话题类别。因此，如何利用文本分类算法来处理TT任务成为研究的特点。目前，国内外在文本分类方面的研究主要是基于统计方法，其主要算法有：Rocchio，K最近邻居（KNN），朴素贝叶斯（NB），支持向量机（VSM），决策树（DT）和神经网络（NNET）。下面重点介绍这几种常见的分类算法，并分析其性能以及在TT系统的应用。
2.1 Rocchio算法
Rocchio算法基本思想是根据训练集合为每个类别构造一个类中心，对每个待分类的文本计算和所有类别之间的几何距离，并以此作为判别属于哪个类别的依据。
Rocchio分类算法属于有监督学习（Supervise Learning,SL）。对于给定一个训练集合D，类别c表示为：
(c)=(d)
其中，Dc表示在训练集合中属于类别c的文本集合，(d)表示归一化的文本向量d。对于给定一个待分类文本d，把d判为c，当且仅当：
c=argmaxcos((c),(d))
Rocchio算法简单易懂、容易实现，并且计算速度快。但是，它的缺点是每个类别只有一个类中心，而且它是判断待分类文本属于哪个类别子空间，对于处于那些判别面的文本却无能为力。
2.2 KNN算法
KNN是一种基于机械学习的分类算法，基本思想是在给定新文本后，考虑在训练文本集合中与该新文本距离最近（最相似）的K篇文本，根据这K篇文本所属的类别判断新文本所属的类别。
给定测试文本d，分类器通過遍历所有训练文本，计算训练文本和d的相似度，然后排序取前k个最相似的文本，假设为集合Dk，根据这ｋ个文本的归属来判断文本ｄ的类别[3]。
score(d,ci)=sim(d,dj)θ(dj,ci)
其中，
θ(dj,ci)=1 if ｄｊ∈ｃｉ0 else
最后选择得分最大的判别为d的类别。
KNN分类算法在理论上很成熟，简单易实现，被证明是向量空间模型下最好的分类算法之一，因而得到广泛的应用。但是它的一个假设是各个类别训练语料分布均匀，然而在实际应用中，各个类别的分布却千差万别，这时候的KNN分类系统性能会严重下降，在这些数据分布不平衡的系统中，KNN偏向大类别，也就是倾向于把待测试的文本分到训练语料较多的类别。
2.3 NB算法
NB算法是以概率理论为基础，即待考察的量遵循某种概率分布，并且可以根据这些概率以及观察到的数据进行推理，以做出最优的决策[4]。
给定文本d，计算特征词属于每个类别的几率向量，然后根据特征词分词，计算文本d属于类别Cj的概率：
Ｐ(cj│)= 其中，(cj│)=，為先验概率，Ｐ(cr│)的计算方法与之相同，C为类的总数，wk为特征词属于每个类别的几率向量，n为向量空间模型的特征词总数。
最后比较新文本属于所有类的几率，将文本分到几率最大的类别中。
NB作为一种不确定性推理方法，它基于概率和统计理论，具有坚实的数学基础，并且由于不错的分类性能和简单快速等优点，得到广泛的关注和应用。然而，它假设文本中所有特征词汇都是相互独立，实际中这些特征存在很强的相关性，这就造成了NB分类器性能的严重下降，增加了NB分类器学习的复杂度。
2.4 VSM算法
VSM是在统计学习理论的基础上发展的新的模式识别方法，通过非线性变换将输入空间变换到一个高维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当的内积函数实现的。
实践证明VSM是最好的分类器之一[5]，可以避免过度拟合问题，有效控制函数容量与有限的样本相适应。然而，SVM是基于二值分类的分类器，虽然有好多策略可以将SVM推广到多值分类，但随着类别的增加，复杂度也相应的增加。
3.总结
TDT是自然语言处理领域中的一个新兴的研究课题。通过评测驱动的方式，TDT的研究已经取得了相当大的进展。但目前关于话题跟踪方法的研究主要是基于统计方法，将来的发展应关注话题本身的特性，考虑多种方法的综合运用。
【参考文献】
［１］James Allan,Jamie Carbonell,George Dodington,Jonathan Yamron,and Yiming Yang.Topic Detection and Tracking Pilot Study:Final Report.In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop,San Francisco CA,1998.
［２］The National Institute of Standards and Technology (NIST).The 2002 Topic Detection and Tracking(TDT2002) Task Definition and Evaluation Plan[Z].ftp://jaguar.ncsl.nist.gov//tdt /tdt2002/evalplans/TDT02.Eval.Plan.Plan.vl.lps.
【关键词】话题检测；话题跟踪；文本分类
0.引言
随着信息技术的飞速发展，互联网变得越来越普及，这就造成了网络信息的急剧膨胀，如何在浩瀚的信息海洋中获取自己所需信息成为困扰人类的新问题。话题识别与跟踪（Topic Detection an Tracking,TDT）技术就是在这种情况下产生的。TDT是一种新的信息处理技术，它将新闻信息流以主题为单位进行组织，实现对新闻流中新话题或新事件的自动检测以及对已知话题的后续报道的追踪。从1996年TDT概念的提出，1997年自马萨诸塞大学、卡内基一梅隆大学和Dragon System公司的学者和研究人员对这项技术进行了初步研究[1]，到2007年TDT共举行过七次公开的TDT任务评测，取得了很好的效果，渐渐使得TDT成为研究的热点。
1.TDT的相关技术
1.1基本概念
话题（Topic）是指由某些原因、条件引起，发生在特定时间、地点，并可能伴随某些必然结果的一个事件[2]。
主题（Subject）是与话题相应的一个概念，它的含义更广些。话题与某个具体事件相关，而主题可以涵盖多个类似的具体事件或者根本不涉及任何具体事件。
报道（Story）是指一个与话题紧密相关的、包含两个或多个独立陈述某个事件的子句的新闻片段。
1.2研究任务
美国国家标准技术研究院（NIST）为TDT研究设立了五项基础性研究任务：报道切分任务（SST）：将原始数据流切分成具有完整结构和统一主题的报道。话题跟踪任务（TT）：跟踪已知话题的后续报道。话题检测任务（TD）：检测和组织系统预先未知的话题，TD的特点在于系统欠缺话题的先验知识。首次报道检测任务（FSD）：从具有时间顺序的报道流中自动锁定未知话题出现的第一篇相关报道。关联检测任务（LDT）：裁决两篇报道是否论述同一话题，没有明确话题作为参照，自主地分析报道论述的话题，通过对比报道对的话题模型裁决其相关性。 1.3相似度计算方法
文本相似度是两篇文档相似程度的衡量，常用算法有欧式距离，余弦相似度，Jaccard Coefficient等。在下文的计算公式中xi和xj（i,j=1,2,…,n）为文本集中两个不同的向量，m为向量的维数。
欧式距离（Euclidean Distance）
d(xi,xj)=2
余弦相似度是最常用的一种衡量文本相似度的计算方法，它通过计算两个向量之间夹角余弦值来度量文本之间的相似度。
d(xi,xj)=
Jaccard Coefficient的相关系数衡量了两个文本之间的一致性，文本之间的共同点越多，相关系数值越大，文本越相似。
d(xi,xj)=
2.话题跟踪（TT）方法的研究
在TT中，每个话题实质上是一个类别，对待处理的报道，通常通过比较各个话题的相似度，选择相似度最大的话题类别作为待处理的文本的话题类别。因此，如何利用文本分类算法来处理TT任务成为研究的特点。目前，国内外在文本分类方面的研究主要是基于统计方法，其主要算法有：Rocchio，K最近邻居（KNN），朴素贝叶斯（NB），支持向量机（VSM），决策树（DT）和神经网络（NNET）。下面重点介绍这几种常见的分类算法，并分析其性能以及在TT系统的应用。
2.1 Rocchio算法
Rocchio算法基本思想是根据训练集合为每个类别构造一个类中心，对每个待分类的文本计算和所有类别之间的几何距离，并以此作为判别属于哪个类别的依据。
Rocchio分类算法属于有监督学习（Supervise Learning,SL）。对于给定一个训练集合D，类别c表示为：
(c)=(d)
其中，Dc表示在训练集合中属于类别c的文本集合，(d)表示归一化的文本向量d。对于给定一个待分类文本d，把d判为c，当且仅当：
c=argmaxcos((c),(d))
Rocchio算法简单易懂、容易实现，并且计算速度快。但是，它的缺点是每个类别只有一个类中心，而且它是判断待分类文本属于哪个类别子空间，对于处于那些判别面的文本却无能为力。
2.2 KNN算法
KNN是一种基于机械学习的分类算法，基本思想是在给定新文本后，考虑在训练文本集合中与该新文本距离最近（最相似）的K篇文本，根据这K篇文本所属的类别判断新文本所属的类别。
给定测试文本d，分类器通過遍历所有训练文本，计算训练文本和d的相似度，然后排序取前k个最相似的文本，假设为集合Dk，根据这ｋ个文本的归属来判断文本ｄ的类别[3]。
score(d,ci)=sim(d,dj)θ(dj,ci)
其中，
θ(dj,ci)=1 if ｄｊ∈ｃｉ0 else
最后选择得分最大的判别为d的类别。
KNN分类算法在理论上很成熟，简单易实现，被证明是向量空间模型下最好的分类算法之一，因而得到广泛的应用。但是它的一个假设是各个类别训练语料分布均匀，然而在实际应用中，各个类别的分布却千差万别，这时候的KNN分类系统性能会严重下降，在这些数据分布不平衡的系统中，KNN偏向大类别，也就是倾向于把待测试的文本分到训练语料较多的类别。
2.3 NB算法
NB算法是以概率理论为基础，即待考察的量遵循某种概率分布，并且可以根据这些概率以及观察到的数据进行推理，以做出最优的决策[4]。
给定文本d，计算特征词属于每个类别的几率向量，然后根据特征词分词，计算文本d属于类别Cj的概率：
Ｐ(cj│)= 其中，(cj│)=，為先验概率，Ｐ(cr│)的计算方法与之相同，C为类的总数，wk为特征词属于每个类别的几率向量，n为向量空间模型的特征词总数。
最后比较新文本属于所有类的几率，将文本分到几率最大的类别中。
NB作为一种不确定性推理方法，它基于概率和统计理论，具有坚实的数学基础，并且由于不错的分类性能和简单快速等优点，得到广泛的关注和应用。然而，它假设文本中所有特征词汇都是相互独立，实际中这些特征存在很强的相关性，这就造成了NB分类器性能的严重下降，增加了NB分类器学习的复杂度。
2.4 VSM算法
VSM是在统计学习理论的基础上发展的新的模式识别方法，通过非线性变换将输入空间变换到一个高维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当的内积函数实现的。
实践证明VSM是最好的分类器之一[5]，可以避免过度拟合问题，有效控制函数容量与有限的样本相适应。然而，SVM是基于二值分类的分类器，虽然有好多策略可以将SVM推广到多值分类，但随着类别的增加，复杂度也相应的增加。
3.总结
TDT是自然语言处理领域中的一个新兴的研究课题。通过评测驱动的方式，TDT的研究已经取得了相当大的进展。但目前关于话题跟踪方法的研究主要是基于统计方法，将来的发展应关注话题本身的特性，考虑多种方法的综合运用。
【参考文献】
［１］James Allan,Jamie Carbonell,George Dodington,Jonathan Yamron,and Yiming Yang.Topic Detection and Tracking Pilot Study:Final Report.In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop,San Francisco CA,1998.
［２］The National Institute of Standards and Technology (NIST).The 2002 Topic Detection and Tracking(TDT2002) Task Definition and Evaluation Plan[Z].ftp://jaguar.ncsl.nist.gov//tdt /tdt2002/evalplans/TDT02.Eval.Plan.Plan.vl.lps.