一种基于柔性语义相似性度量的中文新闻故事分割方法

摘要

本发明公开了一种基于柔性语义相似性度量的中文新闻故事分割方法，所述方法包括以下步骤：输入目标文集，对文集中的每个新闻故事脚本Ti进行分词；建立上下文关系图；通过所述上下文关系图和快速排序算法对词语之间的上下文相关性进行迭代传播获取柔性语义相关性矩阵；通过所述柔性语义相关性矩阵对句子间的柔性语义相似性进行定义；使用所述柔性语义相似性对中文新闻故事进行分割。本发明提出的柔性度量方法能够更加合理的表示词语之间以及词语集合之间的语义相似性。实验结果表明，在中文新闻故事分割技术中，基于相同的分割准则，与传统的相似性度量方法相比，使用该柔性语义相似性度量方法能够将分割精度提高到3%-10%。

说明书

技术领域

本发明涉及中文新闻故事分割领域，特别涉及一种基于柔性语义相似性度量的中文新闻 故事分割方法。

背景技术

随着网络的普及和发展，例如：广播新闻、会议记录、网上公开课之类的多媒体内容正 在急速增加，现在急需一种有效的方法将这类多媒体数据进行自动的组织，以用于基于主题 的文本检索和分析。一个多媒体的文档，例如一小时的广播新闻节目，通常由多个故事（Story） 组成，为了进行高效率的语义检索，指导使用者去找到他们感兴趣主题的开始和结束是很重 要的，同时，一个分割好的多媒体文档是进行主题跟踪^[1]、分类和总结^[2]等高层次的语义浏览 的重要前提条件。新闻故事分割技术的目的就在于将新闻故事脚本分割成主题一致的故事。 从技术上讲，新闻故事分割技术的效率与两个因素相关：一是词语之间的相似性以及此语句 集合之间的相似性的度量方法；二是分割新闻故事脚本的准则。

之前的许多工作都着眼于设计合理的分割准则，例如：TextTiling^[3][4]最小归一化分割准 则（Minimum NCuts）^[5][6]、最大词汇连接准则^[7]等。与广泛研究的分割准则相比，现阶段的 大多数工作都使用简单的基于重复的硬性相似性度量方式，即相同词语之间的相似性为1， 不同词语之间的相似性为0。很明显这种基于重复的硬性相似性度量方法忽略了不同词语之 间潜在的语义相关性，使得语义关系度量不准确，得到的中文新闻故事分割结果不准确。因 此需要提出一种更加合理的语义相似性度量方式以助于提高分割的效率和精度。

发明内容

本发明提供了一种基于柔性语义相似性度量的中文新闻故事分割方法，本发明能够合理的 表示词语之间的语义相似性，并且可以显著提高中文新闻故事分割技术的精度，详见下文描述：

一种基于柔性语义相似性度量的中文新闻故事分割方法，所述方法包括以下步骤：

（1）输入目标文集对文集中的每个新闻故事脚本T_i进行分词；

（2）建立上下文关系图；

（3）通过所述上下文关系图和快速排序算法对词语之间的上下文相关性进行迭代传播获 取柔性语义相关性矩阵；

（4）通过所述柔性语义相关性矩阵对句子间的柔性语义相似性进行定义；

（5）使用所述柔性语义相似性对中文新闻故事进行分割。

所述建立上下文关系图的步骤具体为：

1）依次读入每个新闻故事脚本，对所包含的词语进行词频统计；

2）根据定义好的词频阈值，将高频词语和低频词语删除；

3）将保留下的词语作为上下文关系图中的结点，其集合即为V；

4）判断集合中的任意两个词语是否同时出现在某一新闻故事脚本中，且这两个词语之间 的距离小于或等于距离阈值，如果是则在这两个词语之间建立边，边的集合即为E；如果否 重新判断其他任意两个词语，直至整个集合中的词语都被遍历；

5）边的权值S_C由词语之间的权值sim_C(a,b)、词语本身的权值sim_C(a,a)表示；

6）所述上下文关系图表示为G=V,E,S_C。

所述词语之间的权值sim_C(a,b)具体为：

${\mathrm{sim}}_C(a,b)=\frac{\mathrm{freq}(a,b)}{{\mathrm{freq}}_{\max }+ϵ}$

其中，freq(a,b)表示词语a和词语b同时出现的次数，freq_max=max(_i,j){freq(i,j)}表示 词对(i,j)的频率最大值，ε是一个常数用以确保0≤sim_C(a,b)≤1。

所述词语本身的权值sim_C(a,a)=1。

所述通过所述上下文关系图和快速排序算法对词语之间的上下文相关性进行迭代传播获 取柔性语义相关性矩阵的步骤具体为：

1）定义上下文关系图中词语之间的语义相似性为sim_S(a,b)，满足以下三条准则：

词语与它本身的相似性为1，即sim_S(a,a)=1；sim_S(a,b)与sim_C(a,b)正相关；sim_S(a,b) 与他们邻居之间的相似性成正比；

2）定义语义相似性的迭代传播过程：

${\mathrm{sim}}_S^{\left(0\right)}(a,b)={\mathrm{sim}}_C(a,b);$${\mathrm{sim}}_S^{\left(t\right)}(a,b)=\frac{c}{Z}\underset{u~a,v~b}{\Sigma }\mathrm{si}{m}_S^{(t-1)}(a,b);$${\mathrm{sim}}_S(a,b)=\underset{t\to \infty }{\lim }{\mathrm{sim}}_S^{\left(t\right)}(a,b);$

其中，u～a,v～b表示u和v在上下文关系图中分别是词语a和词语b的邻居节点，Z是 归一化因子，c是控制因子，表示第t次迭代时词语a和词语b的语义相似性， 表示第t-1次迭代时词语a和词语b的语义相似性，表示初始化；

3）使用快速排序算法求解2）中定义的关系式，获取语义相关性，对每两个词语都求取 语义相关性，若干个语义相关性组成了柔性语义相关性矩阵，该相关性矩阵记为S_S。

所述通过所述柔性语义相关性矩阵对句子间的柔性语义相似性进行定义的步骤具体为：

$\mathrm{Sim}(s_i,s_j|S_S)=\frac{{{f_i}^{T}S}_S{f}_i}{\left|\right|f_i\left|\right|\left|\right|f_j\left|\right|}$

其中s_i和s_j分别表示句子，||f_i||和||f_j||分别表示两个句子词频向量的二范数，T为转置。

本发明提供的技术方案的有益效果是：本发明通过快速排序算法提出一种非监督式的语 义相似性度量方法，对传统的余弦相似性进行改进以使之能够融入词语之间的潜在语义关系， 并利用该柔性语义相似性改进中文新闻故事分割技术。本发明提出的柔性度量方法能够更加 合理的表示词语之间以及词语集合之间的语义相似性。实验结果表明，在中文新闻故事分割 技术中，基于相同的分割准则，与传统的相似性度量方法相比，使用该柔性语义相似性度量 方法能够将分割精度提高到3%-10%。

附图说明

图1为基于柔性语义相似性的中文新闻故事分割技术的流程图；

图2为上下文关系图的示意图；

图3为在标准数据集CCTV和TDT2上故事之间和故事内部句子相似性比值的对比图；

图4为在标准数据集CCTV-75-s上中文新闻故事分割算法在100组随机参数上使用三种 不同相似性度量方式的结果对比图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进 一步地详细描述。

语义相似性的度量是自然语言处理中一个极具挑战性的研究课题。现有的方法主要分为 两类：监督式和非监督式。监督式的方法主要包括WordNet^[8][9]和DISCO。WordNet用于度 量任意两个英文词语之间的相似性。WordNet依靠标识好的文集，将名次、动词、形容词和 副词进行层次划分，划分的依据是语言专家对这些词的语义定义。由于WordNet的简洁性和 有效性，WordNet已经被广泛应用到自然语言处理任务中。与WordNet类似，DISCO作为另 一种常用的监督式方法，用于检索任意给定的两个词之间的相似性。与WordNet相比，DISCO 支持更丰富的语种，例如：英语、德语、法语、西班牙语等。监督式的方法能够直接被用于 提前定义好的语言空间，不需要任何额外的计算，同时，监督式的方法也几乎覆盖了全部的 常用词。不过，监督式的方法依赖于语言学家的知识，词语之间相似性的度量通常由主观意 识所定义，同时，监督式的方法不适用于基于特定文集的应用。非监督式的方法主要包括PMI、 LSA和pLSA。PMI通过查询网站搜索引擎获取到的统计数据，统计两个词同时出现在同一 个网页中的次数，次数越多，那么这两个词的PMI得分就越高。LSA也是一种非监督式的语 义相似性度量方法，它融入了人类学习知识的机理去获取词语或者文本段落之间的相似性。 LSA的关键步骤是通过奇异值分解来进行降维。同时LSA也可以解决自然语言处理中同义性 的问题。pLSA是对LSA的一个改进算法。与源于线性代数的LSA算法不同，在继承LSA 优点的基础上，pLSA使用概率论的方法对成对的词语之间的相关性进行分析，并且能够很好 的处理同义性和多义性的问题。与LSA相比，pLSA更具有普遍性。

近年来，图论的发展引起了自然语言处理学家们的重视，Widdows等人提出了一种基于 图模型的非监督式方法用于获取语义相似性。在该图模型中，结点表示词语，边便是词语之 间的关系。此外，该图模型基于特定的文集，可以处理词语的歧义性。Ambwani等人提出另 一种度量词语语义相似性的图模型，每个词语被表示为一系列的结点，每个结点对应于一个 在该词语影响范围内的句子，边上的权值表示词语之间的相关性。该模型将词语之间的相互 影响融入其中，同时依据上下文来决定词语之间的相关性。以上讨论的语义相似性计算的非 监督式方法都基于特定文集，与监督式方法相比更适用于具体的应用。在这些非监督式的方 法里面，由于图模型的简洁性和高效性，使得基于图模型的语义相似性计算方法引起了越来 越多自然语言处理研究专家的关注。

词语集合（例如段落、文本等）之间的语义相似性度量也是一个亟待解决的问题。词语 集合语义相似性度量的传统方法为余弦相似性。基于词袋假设，每个词语集合被表示为词频 向量，余弦相似度用于度量词频向量之间的夹角，夹角越大，相似性越小；反之，越大。由 于余弦相似性的使用十分简单和有效，因此余弦相似性被广泛应用与词语集合语义相似性的 度量，但是余弦相似性只考虑了相同词语之间的关系，忽略了词语集合中词语之间的相互关 系，这使得词语集合相似性的度量不准确。为了使词语集合语义相似性的度量更加准确和有 意义，在度量词语集合之间相似度的时候，将词语之间的相关性考虑进去更为有意义。因此， 亟需提出一种将词语之间的相互关系融入到词语集合之间相似性度量的方法。

为了能够合理的表示词语之间的语义相似性，并且可以显著提高中文新闻故事分割技术 的精度，本发明实施例提供了一种基于柔性语义相似性度量的中文新闻故事分割方法，参见 图1，本方法在进行语义相似性计算以及新闻故事分割过程中，均是针对某一特定数据集。 同时，为了体现柔性语义相似性度量方法的合理性，重新设计了验证准则对该合理性进行验 证，详见下文描述：

101：输入目标文集对文集中的每个新闻故事脚本Ti进行分词；

即通过该步骤将新闻故事脚本中的每句话分割若干个词语，该步骤为本领域技术人员所 公知，本发明实施例对此不做赘述。

102：建立上下文关系图；

1）依次读入新闻故事脚本，对其中所包含的词语进行词频统计；

2）根据定义好的词频阈值，将高频词语和低频词语删除。

3）将保留下的词语作为上下文关系图中的结点，其集合即为V。

4）判断集合中的任意两个词语是否同时出现在某一新闻故事脚本中，且这两个词语之间 的距离小于或等于距离阈值，如果是则在这两个词语之间建立边，边的集合即为E；如果否 重新判断其他任意两个词语，直至整个集合中的词语都被遍历。

5）边的权值S_C由词语之间的权值sim_C(a,b)、词语本身的权值sim_C(a,a)表示；

词语之间的权值sim_C(a,b)由以下公式定义：

${\mathrm{sim}}_C(a,b)=\frac{\mathrm{freq}(a,b)}{{\mathrm{freq}}_{\max }+ϵ}$

其中freq(a,b)表示词语a和词语b同时出现的次数，freq_max=max(_i,j){freq(i,j)}表示词 对(i,j)的频率最大值，ε是一个常数用以确保0≤sim_C(a,b)≤1(a≠b)。

同时，词语本身的权值sim_C(a,a)=1。

6）因此上下文关系图可以表示为G=V,E,S_C，图2为构建数据集中某一文档的上下文 关系图的示意图，其中，w_u表示T_i中的第u个词语，线条表示词语之间的关系。

103：通过上下文关系图和快速排序算法^[10][11]对词语之间的上下文相关性进行迭代传播 获取柔性语义相关性矩阵；

1）定义上下文关系图中词语之间的语义相似性为sim_S(a,b)，其满足以下三条准则：

词语与它本身的相似性为1，即sim_S(a,a)=1；

sim_S(a,b)与sim_C(a,b)正相关；

sim_S(a,b)与他们邻居之间的相似性成正比。

2）定义语义相似性的迭代传播过程由以下关系式定义如下：

${\mathrm{sim}}_S^{\left(0\right)}(a,b)={\mathrm{sim}}_C(a,b);$

${\mathrm{sim}}_S^{\left(t\right)}(a,b)=\frac{c}{Z}\underset{u~a,v~b}{\Sigma }\mathrm{si}{m}_S^{(t-1)}(a,b);$

${\mathrm{sim}}_S(a,b)=\underset{t\to \infty }{\lim }{\mathrm{sim}}_S^{\left(t\right)}(a,b)$

其中，u～a,v～b表示u和v在上下文关系图中分别是词语a和词语b的邻居节点，Z是 归一化因子，c是控制因子，表示第t次迭代时词语a和词语b的语义相似性， 表示第t-1次迭代时词语a和词语b的语义相似性，表示初始化。

3）使用快速排序算法求解2）中定义的关系式，获取语义相关性，对每两个词语都求取 语义相关性，若干个语义相关性组成了柔性语义相关性矩阵，该相关性矩阵记为S_S。与之类 似，将传统的硬性语义相似性定义为S_H=I，其中I表示单位矩阵。

快速排序算法所基于的假设：如果两个词语的邻居词语比较相似（相关性大于或等于 0.5），那么这两个词语也比较相似；

快速排序算法以上下文关系图作为输入；算法复杂度为O(k|V|²)，其中，k为G中的平 均度数，|V|表示上下文关系图中的节点数，O为算法复杂度。

该发明中实现了快速排序算法基于GPU的全点对并行算法。通过实验观察发现，以同一 上下文关系图作为输入，基于GPU实现的快速排序算法的速度比传统基于CPU实现的快速 排序算法的速度提升了大约1000倍。

快速排序算法的输出为进行迭代传播之后的柔性语义相关性矩阵S_S={sim_S(a,b)}_a,b∈C；

104：通过柔性语义相关性矩阵对句子（即为新闻故事脚本中连续出现的一段词语的集合） 间的柔性语义相似性进行定义；

在新闻故事分割技术中，除词语语义相似性之外，也需要度量词语集合也就是句子之间 的相似性。故事中每个句子可以被标识为词频向量，用于记录每个词语在句子中出现的次数。 对于给定的柔性语义相关性矩阵，句子间的柔性语义相似性定义如下：

$\mathrm{Sim}(s_i,s_j|S_S)=\frac{{f_i}^T{S}_S{f}_i}{\left|\right|f_i\left|\right|\left|\right|f_j\left|\right|}$

其中s_i和s_j分别表示句子，||f_i||和||f_j||分别表示两个句子词频向量的二范数，T为转置。 该定义是对传统的余弦相似性的改进，它将不同词语之间潜在的语义相关性考虑进去，因此 能够更为合理的表示句子之间的语义相似性。

105：使用柔性语义相似性对中文新闻故事进行分割。

1）中文新闻故事分割技术基于的准则为归一化准则^[5][6]；

其中，归一化准则具体为：该准则基于图模型；句子被标识为图模型中的结点，句子之 间的关系表示为图模型中的边；句子之间的相似性表示为边上的权值；新闻故事分割问题转 化为图模型分割问题。

2）使用句子间柔性语义相似性对输入数据集中所包含的新闻故事脚本进行中文新闻故事 分割。

下面以具体的试验对本发明提供的一种基于柔性语义相似性度量的中文新闻故事分割方 法的可行性进行验证：

在标准数据集上进行实验：

为验证本方法的有效性，本方法在两个标准数据集CCTV和TDT2上进行了实验。CCTV 数据集共包含了71个汉语新闻故事脚本，根据新闻故事长度和识别错误率可以讲CCTV数 据集分为8个子集，分别记为CCTV_59_f/s,CCTV_66_f/s,CCTV_75_f/s和CCTV_ref_f/s,其 中f表示长故事集，s表示短故事集，ref表示参考数据集。TDT2数据集包含177个汉语新闻 故事脚本，根据识别错误率可以讲这177个脚本分为两个子集，分别记为TDT2_ref和 TDT2_rcg。分别使用硬性语义相似性S_H、上下文语义相似性S_C和柔性语义相似性S_S对CCTV 和TDT2数据集中的新闻故事进行分割，并比较其分割精度的好坏。其中分割精度由F1评分 来表示。表1列出了使用不同相似性度量方式在CCTV和TDT2数据集上的分割精度。

表1

从表1中可以观察到，与传统的硬性语义相似性相比，使用柔性语义相似性能够使分割 精度有明显的提高，提高幅度约在3%到10%。同时还可以发现上下文语义相似性要比硬性 的语义相似性好，并且通过快速排序算法可以使上下文语义相似性得到提升。为了表明本方 法的健壮性，本方法在CCTV_75_s数据集上实施了另一个更为严格的实验，通过比较不同方 法使用100组随机参数的分割精度。图4显示了该实验结果。在新闻故分割技术中，句子之 间相似性的好坏可以用故事之间的相似性和故事内部的相似性的比值来度量，该比值对应句 子的可区分性，其中，比值越小则证明相似性越好，该比值由以下公式来定义：

$R\left(C\right|S_S)=\frac{\exp \left({\mathrm{mean}}_{\mathrm{lab}\left(s_i\right)\ne \mathrm{lab}\left(s_j\right)}\mathrm{Sim}(s_i,s_j|S_S)\right)}{\exp \left({\mathrm{mean}}_{\mathrm{lab}\left(s_i\right)=\mathrm{lan}\left(s_j\right)}\mathrm{Sim}(s_i,s_j|S_S)\right)}$

其中lab(s_i)表示句子s_i所属故事的标号，lab(s_j)表示句子s_j所属故事的标号，mean表示 取平均值。

本方法将硬性语义相似性S_H、上下文语义相似性S_C和柔性语义相似性S_S在标准数据集 上进行了对比，对比结果表示在图4中。通过实验发现，使用柔性语义相似性S_S所得到的R 比值要比另外两种相似性要低，而上下文语义相似性S_C要比硬性语义相似性要低S_H。该实 验表明柔性语义相似性S_S要比传统的硬性语义相似性S_H更加合理，并且通过快速排序算法 求解的柔性语义相似性（即经过迭代传播后的语义相似性）更加合理。将本方法应用到中文 新闻故事分割技术中可以使分割精度有显著的提高。

参考文献：

[1].J.Allan,Ed.,Topic Detection and Tracking:Event-based Information Organization,Kluwer  Academic Publishers,2002.

[2].L.-S.Lee and B.Chen,“Spoken document understanding and organization,”vol.22,no.5,pp. 42–60,2005.

[3].S.Banerjee and I.A.Rudnicky,“A TextTiling based approach to topic boundary detection in  meetings,”in INTERSPEECH,2006.

[4].L.Xie,J.Zeng,and W.Feng,“Multi-scale TextTiling for automatic story segmentation in  Chinese broadcast news,”in AIRS,2008.

[5].I.Malioutov and R.Barzilay,“Minimum cut model for spoken lecture segmentation,”in ACL, 2006.

[6].J.Zhang,L.Xie,W.Feng,and Y.Zhang,“A subword normalized cut approach to automatic  story segmentation of Chinese broadcast news,”in AIRS,2009.

[7].Z.Liu,L.Xie,and W.Feng,“Maximum lexical cohesion for fine-grained news story  segmentation,”in INTERSPEECH,2010.

[8].T.Pedersen,S.Patwardhan,and J.Michelizzi,“Wordnet::similarity-measuring the  relatedness of concepts,”in AAAI(Intelligent Systems Demonstration),2004.

[9].Christiane Fellbaum,Ed.,WordNet:An Electronic Lexical Database,MIT Press,1998.

[10].G.Jeh and J.Widom,“SimRank:A measure of structural-context similarity,”in ACM  SIGKDD,2002.

[11].G.He,H.Feng,C.Li,and H.Chen,“Parallel SimRank computation on large graphs with  iterative aggregation,”in ACM SIGKDD,2010.

本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅 仅为了描述，不代表实施例的优劣。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之 内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。