Algorithm 版 (精华区)

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 文本结构分析在文本过滤中的应用(zz)
发信站: 哈工大紫丁香 (2002年05月23日10:34:45 星期四), 站内信件


文本结构分析在文本过滤中的应用
摘  要：本文简要介绍了文本过滤的背景和中文文本结构分析，提出了文本层次分析方
法。依此，建立了基于示例的中文文本过滤模型。其基本思想是首先对于用户提出的示
例文本进行文本结构分析，主要是文本层次分析，提取文本特征，形成用户需求的逻辑
表示，即用户模版，然后进行文本过滤，在用户反馈的基础上，改进用户模版，提高过
滤效率。
关键词：文本过滤 文本结构分析 文本层次分析 用户模版
一 前言
随着信息技术的高速发展，尤其是因特网的不断普及，各种在线的电子文档如潮水般地
涌来，面对信息的“汪洋大海”，如何查找和利用所需的各类信息，往往使用户感到十
分的茫然，出现所谓的“信息过载”(information overload)问题，即信息浩如瀚海，
却又很难发现自己感兴趣的信息，而即使找到一些有用的信息，也经常混有很多的“噪
音”。因此，为了能够根据用户个人的兴趣，提供给用户真正感兴趣的信息，而尽量屏
蔽那些不为用户喜欢的信息，信息过滤技术应运而生。国际学术界和企业界对此也表现
出极大的兴趣。在著名TREC(Text REtrieval Conference)中，传统的两个主题是routi
ng task和Ad hoc task,而过滤是routing task重要的子任务，TREC在信息过滤的理论和
技术研究以及系统测试评价方面，对信息过滤的形成和发展提供了强有力的支持。
由于目前绝大多数信息均表现为文本方式，所以文本过滤技术得到极大的促进和发展。
文本过滤和文本检索，文本摘要、文本标注和文本分类等相关技术有着密切的关系，尤
其是与文本检索。所有这些方向为计算语言学的发展注入了新的活力，也是计算语言学
能够获得实际应用并且取得良好效果的领域。
文本过滤是“用相对稳定的查询在动态信息源中搜索”，而文本检索是“用新的主题在
相对静止的信息源中搜索”，文本过滤与文本检索有着极为密切的联系，过滤实质上是
建立在检索的基础之上的。因为它借鉴了许多检索的表示方法和技术。但两者又有着各
自不同的特点，认清这一点对于我们在设计中文文本过滤模型过程中充分利用成熟的检
索技术以及消除它存在的局限性是十分必要的。
二 基于示例的中文文本过滤模型
文本过滤的工作基本上可以概括为两项：一是建立用户需求模型，即用户模版，用于表
达用户对于信息的具体需求，建立用户需求模型的主要依据是用户提交的主题词或示例
文本；二是匹配技术，即用户模版与文本的匹配技术。文本过滤的主要流程是根据用户
的信息需求，建立用户需求模型，然后在相应的文本流中搜索符合用户需求的文本，再
利用反馈，改进需求模型。
    在本文设计的中文文本过滤模型中，用户需求的表示即用户模版采用基于示例文本
的主题词表示，文本表示采用向量空间模型，需求与文本的匹配技术采用向量夹角余弦
作为相似系数，按照相似系数的大小输出过滤文本，定期处理用户反馈，改进用户模版
。
基于示例的中文文本过滤模型设计的基本思想：首先，通过用户提交的示例文本，经过
文本结构分析，获取文本特征，建立用户需求模型，由基于示例文本的主题词组成用户
模版，依据用户模版，采用基于主题词过滤的方法在文本源中搜索与之相匹配的文本，
提供给用户，在用户反馈的基础上，改进用户模版。
在模型中，用户模版的存储结构为如下结构：
   主题词-模版索引表是模版的物理表示，它是以主题词为索引的链表，第一个域存储
模版的编号，如P1,P2,...,Pn；第二个域存储在该模版中主题词的权重。模版参数表中
相关阈值表示文本与模版匹配时的相似系数应大于或等于该值，而主题词数表示每个示
例文本所提取的主题词数目。
例如：设文本为“高等教育改革的重大举措”，文本向量为（<高等教育,1.00>,<改革,
1.00>,<举措,1.00>），模版P1为（<高等教育,1.00>,<改革,0.40>），则文本与模版的
相似系数为0.75 > 0.50，所以可以认为该文本符合用户需求，提供给用户。
三 文本结构分析与文本特征提取
在中文文本过滤过程中，进行文本结构分析的目的在于获取文本特征，主要是提取主题
词。作为文本的主题词应具有彻底性(Exhaustivity)和专门性(Specifity)。其中彻底性
指文本所讨论的内容被主题词覆盖的程度；专门性指主题词必须能反映文本的具体内容
，而不是泛泛而谈。为了满足彻底性要求，对文本进行层次分析，然后按层次抽取主题
词，以保证对文本各部分内容的最大限度的覆盖。为了满足专门性，需要消除停用词，
选择具有实际意义的名词及其短语，特别要注意选取面向内容的词汇。
文本结构包括物理结构和逻辑结构，对于输入的文本，首先识别出文本的物理结构，文
本的物理结构 = {标题，段落，句子，词汇}，它表示了文本的组成情况。可采用向量空
间模型表示文本及文本各个部分。然后进行文本结构分析，其中主要是文本的层次分析
，从而得到文本的逻辑结构。文本的逻辑结构 = {主题，层次，段落，句子，主题词}，
它更着重于表示文本所包含的思想内容和表达的逻辑方式。
文章是具有层次的。层次是文章思想内容的表现次序，它着眼于文章思想内容的逻辑关
系，是表示意义的结构单位，而段落是体现层次的外部形式。但是层次不象自然段那样
有明显的边界，必须由读者按照文章内容的表达方式来划分。需要强调的是层次的有序
性。层次是由若干连续有序的自然段组成。
在以往的文本结构分析中，将向量模型应用到文本的各个段落上，计算段落间的相似系
数，建立文本结构关系图，标号即为段号，带权的边表示相似系数，具有n个自然段的文
本结构图最大边数则为n(n-1)/2。选择适当的阈值，略去相似系数小于阈值的边，得到
简化的关系图，属于同一连通子图的段落，往往属于同一主题。通过调节阈值，观察段
落间的关系。如此这样，划分出若干主题，形成主题路径。这种方法形成的主题往往是
由不连续的段落组成，缺乏有序性，使得路径解释比较困难，因为一般文章都是有一定
层次的。鉴于此种情况，并注意到如下事实：
同一层次的若干连续自然段，由于共同支持该层次所表达主题思想，因此在选用的词汇
上以及用词的频率上往往具有很大的相同之处。根据这一事实，我们尝试采用有序聚类
的方式划分文本的层次。
设文本T具有n个自然段，K个层次，用H表示文本层次，P表示自然段，则有如下组成关系
：T = HH...H = {P...P}{P...P}...{P...P}
其中：i=1<=i<=..........<=i<=i-1=n （为了叙述和书写方便，P,P,...,P简记为1,2,
......,n）
设文本T的特征项集为{t,t,.......,t} 则设P=(w,w,......,w)为第i段的特征向量。其
中w是特征项t在第i段中权重。
将n个段落划分为K个层次，则所有可能的分法共有C种，设S(n,K)是任一种分法，其中S
(n,K) = {i=1,i+1,...,i-1},...，{i,i+1,...,i-1},...,{i,i+1,...,n}。有序聚类就
是寻找一种分法使K个层次内差异尽可能地小，而层次间的差异尽可能地大。设D(i,i-1
)表示第j层内的差异量，则总体误差函数:
  E(S(n,K)) = D(i,i-1)
为了使上述总体误差函数达到最小，寻求最优的K分法。相当把n个段落分成两个部分{i
=1,i+1,......,i}{i,.....,n},将前一部分进行最优K - 1分法，然后再考虑后一部分的
误差，由此寻找到最优K分法。设S(n,K,c)是使总体误差函数达到最小的分法，其中c是
上述最佳分法的分割点i。则有如下递推公式：
E(S(n,K,c) )= Min{ E(S(i,K-1,c) + D(i,n)) }
文本层数的确定关系到文本逻辑结构的建立，它可以通过如下方法确定最优层次划分的
数目，一是给定阈值，当时，则最优层数为K。二是根据语言学知识和实际经验，预先给
定层数K。这里，我们在运行过程中根据段落数目和总体误差情况给定层数，K的范围一
般情况下是从2到6。
当文本层次分析后，首先定义主题词权重函数，然后按层次分配主题词数目，选取该层
权重较大的主题词，最终建立整个文本的主题词集合，用于表达用户的信息需求。
在设计权重函数时，注意到如下事实：
主题词的段落频率越高，表明该主题词反映文本主题的能力越强，因此应赋予较大的权
重。另外，短词具有较高的频率，更多的含义，是面向功能的；而长词的频率较低，是
面向内容的。加大长词的权重，增强词汇的区分度。也可以减轻因分词造成的单个汉字
成词的不稳定性。文章的标题与主题紧密相关。国内有人抽样统计，国内中文期刊自然
科学论文的标题与文本的基本符合率为98%，新闻文本的标题与主题的基本符合率为95%
。大量统计资料表明，每个段落的开头和结尾都含有重要的主题词，因此应给予较高的
权重。美国学者P.E.Baxendale进行过统计，反映主题的句子，85%出现在段首，7%出现
在段尾。尤其对于新闻语料，Searchable Lead系统仅仅从文章开头部分抽取给定长度的
一部分形成摘要，就达到87%-96%的可接受率。 而对于带有摘要段的文本，其摘要段是
文本中含有主题词最多的部分，这里的主题词更能表现文本主题。另外，对于包含在诸
如“综上所述”、“总而言之”等类句子中的主题词，由于它们往往是结论性的句子，
所以也应获得较高的权重。
    词汇权重函数：  =
  其中： 表示主题词的权重函数；
         表示主题词在层次内的频数。
         表示主题词的段落频率。
         表示主题词的词长。
         C是比例因子。
         当主题词位于段首、段尾和结论性句子，否则。
文本主题词由两部分组成：文本标识部分（包括标题，子标题，摘要段，关键字表等）
的主题词和文本正文部分的主题词。假设主题词数目为t，则首先选取文本标识部分的主
题词，若标识部分的主题词数s < t，再选取正文部分的主题词，同时对各个层次按比例
分配。正文部分主题词集合生成算法：设定在文本正文中抽取主题词数目n = t - s，文
本层次为m，则各层主题词所占比例如下：
计算层次权重函数：
其中：文本的特征向量为，层次的特征向量为
则层次主题词数目为 。
如上所述，文本的标识部分的主题词具有最强的代表性，文本正文的主题词次之。而在
文本正文中，不同层次重要性也不同。因此，权重设计如下：
来自文本标识部分的主题词权重为1.0；来自文本首层的主题词权重为0.8，来自末层的
主题词权重为0.6，来自其它层的主题词权重为0.4。当提取的主题词在模版中已经存在
时，其权重值取两者的最大值。文本主题词与其权重构成用户模版的主题词表示，用来
代表用户的信息需求。
文本向量的构成方法与上述相同。
四  结论
   随着因特网在我国的迅速普及，中文在线文本的日益增多，越来越多的用户要求在网
上获取信息，信息服务的个性化是必然趋势，中文文本过滤正是顺应潮流的产物。本文
给出的基于示例的中文文本过滤模型，采用主题词过滤的方法可操作性强，速度快，易
理解。
我们的实验的文本选自94年《人民日报》语料库中310篇文章，其中有10篇人工确认相关
文章作为已知的示例文本，另外50篇相关文章和250篇无关文章作为测试集。根据PRECI
SION-RECALL曲线，其平均精度为42%  。
在实验中过滤效果受主题词选取准确程度的限制，尤其当示例文本增加时，“噪音”也
随之增加。更有效地选择主题词是关键问题，尤其名词短语的识别问题，下一步尝试采
用更为细致的词、句子和文本分析等自然语言理解技术和文本主题词可视化手段。其基
本思想是将选择更典型的主题词，并以可视化的方式提供给用户，让用户确认感兴趣的
主题词，并使之权重最大。也可作为反馈手段来提高效率。
参考文献：
[1]  姚天顺等，自然语言理解，清华大学出版社，1995
[2]  吴立德等，大规模中文文本处理，复旦大学出版社，1997
[3]  韦雄观等，基于关系图的篇章分析方法，模式识别与人工智能，Vol.10 No.2,199
7
[4]  刘开瑛等，中文文本中抽取特征信息的区域与技术，中文信息学报，Vol.12 No.2
,1998
[5]   Kendall, Multivariate analysis ,Charles Griffin & Company Limited,1975
.
[6]   G.Salton,J.Allen, C.Buckley and A.Singhal, Automatic Analysis, Theme G
eneration and Summarization of Machine - Readable Texts, Science , Vol.264 N
o.3,June 1994,1421-1426.
[7]  T.W.Yan and H.Garcia-Molina, Distributed selective dissemination of inf
ormation, In Proceeding of the Third International Conference on Parallel an
d Distributed Information system,1994,89-98.
[8]  Qi Lu, Matthias Eichstaedt and Daniel Ford, Efficient profile matching
for large scale    Webcasting, http://decweb.ethz.ch/WWW7/1923/com1923.htm
  
--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]