为了保证抽取信息的全面性,主题划分成了不可或缺的工作。如何通过计算机将文章中的主要思想抽取出来,并全面、准确地展示给读者,尤其是对于学术研究者,显得非常有意义,这样他们可以方便快捷地从中了解到感兴趣的信息。
大多数文章反映的不是单纯的一个主题,更多的是多主题,作者常常会从多角度进行思想论述,同时作者为了凸显某些主题的重要性,常常会在文章中多次强调阐述这些主题。若是采用传统的基于句子重要度抽取信息的方法,则会导致抽取的信息集中在主要主题,容易忽略次要主题的信息,从而抽取的信息完整性较差。同时,也会造成抽取信息的冗余度较大。因此,事先对文章进行主题划分的工作就显得非常重要。有了主题划分的预处理工作,可以确保抽的取信息能够全面、完整、准确地反映文章的主题,使得读者更好地把握文章的内容。
我们采用的算法首先基于同义词词林,从语义的角度计算段落间的相似度,并基于段落相似度建立文本关系图;然后基于文本关系图,采用归一化割分割准则予以进一步处理,将表达同一主题的段落归为一类,完成对文章划分主题的工作。
9.2.2.2 文本关系图的建立
该算法从语义相似度的角度计算了文章中各个段落间的相似度,这样描述段落间的相似度就更为准确。作者在表达阐述一个主题时,其所用重点词汇通常局限在能代表该主题所涉及内容的一个较小范围。通常两个段落间的相似度可以通过衡量段落间包含词汇的重复程度来表示,然而这种方法仅仅粗略地计算了段落相似度。
有些段落间包含词汇的重复程度不高,但是它们包含词语间的词义相同或是词义有很强的相关性,那么它们表达的内容很有可能属于同一主题。比如,“计算机”“微处理器”和“电脑”,“大豆”“黄豆”和“毛豆”,词义相同;“飞机”和“直升机”,“大炮”和“坦克”,“战斗机”和“武器”,“铁路”和“交通”,其词义间有很强的相关度。若是纯粹地以段落中含有高频词的吻合程度来衡量段落间的相似度,显然不够准确,我们采用基于同义词词林计算段落间的相似度能比较好地解决此问题。
文本关系图是一种描述文本之间关系的形式化模型,它是以文本中的某些特征项为顶点,特征项之间的关系为边建立的一种关系图结构。
建立文本关系图,首要工作需要选取合适的文本特征表示模型。在文本特征表示模型中,潜在语义分析与文本相似度模型相比向量空间模型,都有着自己的优势。潜在语义分析反映的不再是简单的词条出现频率和分布关系,而是强化的语义关系,在保持了原始的大部分信息的同时,克服了传统向量空间表示方法时产生的多义词、同义词和单词依赖的现象,且它不需要借助人工构建词典并进行语法和句法分析等。然而,潜在语义分析所谓的语义,是统计意义上的相似,其实基于同现分析,同现词条被认为是语义相关的。文本相似度模型反映了文本间真实的语义相似关系,但它基于语义词典进行词语相似度计算,需要借助于词典库。因此,在实验过程中,将依据实验结果选取合适的文本特征表示模型。
图9-2 文本关系
为了满足使用归一化割分割准则进行主题分块,将主题分块问题转变为图论中的最优化问题,我们以段落为基本单元、段落相似度为权值建立段落间文本关系图,具体如图9-2所示,其中,顶点p和q分别表示文章中的段落,连接顶点p和q的权值C pq表示两段落间的相似度。
9.2.2.3 归一化割准则
基于归一化的分割准则主要经历了两个大的阶段:第一个阶段是由Wu和Leahy共同提出的最小化割准则,第二个阶段则是由Shi和Malik提出的归一化割准则。
最小化割准则常常会把一些孤立点分割为独立的一类,这样最小化割分割准则容易受到噪声的影响。基于这些,归一化割准则的提出,是为了改进最小化割这一缺陷,改进后的归一化割分割准则从全局着手,同时度量不同分组之间的总体不相似性和各个组内的相似性的总和,既满足了类间的相似度最小,同时也满足了类间的相似度最大。因此,相对最小化割准则而言,归一化割准则更加符合聚类的思想。近年来,基于图论的图像分割技术已经成为研究者在图像分割领域的一个研究热点。该方法将图像用一幅无向带权图来表示,将图像中的像素看作图中的节点,利用基于图论的分割准则得到图像的分割。[24]该方法是一种点对聚类方法,在数据聚类方面有广泛的应用前景。
1.最小化割
一幅加权无向图G=(V,E)可以通过删去某些边,将其分为两个非连接性点集A、B,使得:A∪B=V,A∩B=∅。原先连接两部分而现在被删去的所有边的权的总和,在图论中被称作割(cut):
图9-3 加权无向
其中,w(i,j)是连接顶点i和顶点j边的权值,表示两点之间的相似程度。这样,只要使得cut(A,B)最小,那么就得到了图G=(V,E)的最优分割。然而,最小化割准则常常会把一些孤立点分割为独立的一类,这样最小化割分割准则容易受到噪声影响,当受到噪声的影响时,最小化割分割准则的性能就体现不出来了,如图9-3所示。
从图9-3可知,最小化割会将n1或者n2单独分为一类,而比较好的分割结果是中间那条虚线的分割结果。
2.归一化割
为了克服这一缺点,Shi和Malik提出了归一化割准则,将归一化割准则定义为:其表示类间的相似度,值越小,分割效果越好,其中,
其表示A部分内的节点与整幅图节点V的权重之和。同时,定义:
其表示类内的相似度,值越大,分割效果越好。可以推出
这样可得:归一化割准则既满足了类间的相似度最小,又满足了类间的相似度最大。因此,相对最小化割准则而言,归一化割准则更加符合聚类的思想。
3.归一化割算法的求解(www.xing528.com)
然而,归一化割是个NP-hard问题,随着G=(V,E)节点的增加,计算变得很复杂。在实际应用中,本研究采用近似的方法来求解Ncut算法。
设x是一个N=
维的指示向量,如果点i属于A,则x i=1;否则x i=-1。d i=
j表示点i与其他点的联系。所以有
设D=diag( d 1,d 2,…,d N),W是N×N的对称矩阵,且W(i,j)=w ij,这样寻找全局最优值转换为
其中
如果y只取实值,则可以通过解决广义特征值问题来求解式子:
y约束来自于相应的指示向量x的条件。公式(9-9)转换为规范特征值问题,如公式(9-10)所示:
其中,
。该特征值问题对应具有第二个最小特征值的特征向量满足规范约束,即可以利用该特征向量对图进行划分,最终得到图的最优化分。
4.归一化割算法描述
(1)首先基于前面的工作,以段落为节点、段落相似度为权值的文本关系图转换为加权无向图,计算权值矩阵W和D,其中W是N×N的对称矩阵,其元素值W (i,j)=w ij,即段落间的相似度;D为N×N对角矩阵,对角线上的元素为d i,d i=
是节点与所有节点的关系之和。
(2)求出特征系统(D-W)y=λD y的特征值和与其相对应的特征向量。
(3)使用上一步骤的第二最小特征向量分割段落为两部分。
(4)检查N cut值是否稳定或主题包含的最小段落数决定是否继续分割。
(5)若需要继续分割,则递归此算法分割上一次分割好的部分。
5.整体算法步骤
基于前面的工作,设计出基于归一化割主题划分算法,如下:
(1)输入文档,进行预处理,设待处理文档的段落为m段。
(2)基于同义词词林计算词语间的相似度,并在此基础上计算段落相似度。
(3)以m段落为节点、m段落间的相似度为权值建立文本关系图,并转换为加权无向图G=(V,E)。
(4)在加权无向图G=(V,E)的基础上,进行归一化割算法处理。
(5)完成对文档的主题划分。
9.2.2.2 句子重要度排序
基于图的排序算法采用的是通过分析图的全局特征来确定其顶点重要度,这种方法在网页排序方面应用广泛。图结构是以某些特征项为顶点、特征项之间的关系为边建立的一种关系图结构。PageRank算法是基于图的排序算法的一种,它是由Larry Page和Sergey Brin提出来的。PageRank算法在传统意义上是用在万维网的链接结构分析上,即它是基于有向图的,但是它也可以用在无向图上,只需将无向图看作入度等于出度的有向图即可。所以基于图的网页排序算法一般假定图是不带权的。然而,在文本排序模型中,所建立的文本关系图结构是带权的,这样更符合一般文本的特点,使得计算结果更加准确。
对传统的PageRank算法进行改进,使得它可以用到本书所建立的句子关系图中。在用PageRank算法计算顶点的权重时引入边的权值:
其中,d是阻尼系数,是介于0和1之间的一个数;R(V x)为V x的PR值;w ij为边(V i,V j)的权重,即关系图中顶点i与顶点j的相似度,且w ij=w ji;Out(V j)为节点V i的出度;In(V i)为节点V i的入度。改进后的PageRank算法,更适合处理一般文本信息,使得计算结果更加准确。
这个阶段的工作重点是要进行句子重要度排序,基于若与其中一个句子主题相关的重要句子越多,则该句子的重要性也将越高的思想,采用以句子为基本单元,利用句子间的相似度关系建立文本关系图,然后基于文本关系图利用改进后的PageRank算法,即可得出各个主题内的语句重要度排序。然而,改进后的PageRank算法中,没有考虑到句子位置的因素,而句子的位置因素对句子在段落中的重要度有着重要的影响,所以将句子在段落中所处位置的影响引入该算法中进行改进,以便改进后的新算法T-PageRank更合适地处理文本句子,得出更准确的结果。
有了以上的工作过程,在候选句库中,基于知识元结构特征,最终将知识元属性-内容描述语句提取出来。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
