引用本文
刘金岭, 倪晓红, 王新功. 手机短信文本信息流的自动文摘生成. 现代图书情报技术, 2013, 29(2): 43-49
Liu Jinling, Ni Xiaohong, Wang Xingong. Automatic Abstracting Generating Based on Mobile Short Message Text Information Flow. New Technology of Library and Information Service, 2013, 29(2): 43-49  
Permissions
手机短信文本信息流的自动文摘生成
刘金岭1, 倪晓红2, 王新功2
1.淮阴工学院计算机工程学院 淮安 223003
2.沧州师范学院计算机系 沧州 061001
修回日期:2013-02-11
基金:本文系河北省科技支撑计划项目“手机垃圾短信语义识别与分类”(项目编号: 10213581)和淮安市社会支撑基金项目“基于数据挖掘的淮安市人力资源及就业状况研究”(项目编号: HASZ2012046)的研究成果之一。
摘要
针对手机短信文本信息流的特点, 设计一种自动文摘生成模型。该模型利用词共现定义语义相似度, 根据TF-IDF定义特征词权值以及文摘候选句权值。算法通过清除孤立点、根据权值筛选文摘句以及文摘句排序, 生成冗余度较小且可读性较好的短信文本信息流文摘。相关数据实验证明, 文摘句的生成质量和算法效率都比较高。
关键词: 手机短信文本; 信息流; 文摘; 权值
Automatic Abstracting Generating Based on Mobile Short Message Text Information Flow
Liu Jinling1, Ni Xiaohong2, Wang Xingong2
1.Computer Engineering Faculty, Huaiyin Institute of Technology, Huaian 223003, China
2.Department of Computer, Cangzhou Teachers College, Cangzhou 061001, China
Abstract
Due to the characteristics of mobile short message text information flow in the practical application, an automatic digest generation model is designed. The model uses word co-occurrence to define the semantic similarity. Using the TF-IDF, weights of feature words and abstracts candidate sentence weights are defined in the model. By removing isolated points, the algorithm generates smaller redundancy and more readable short text messages flow digest according to the weight screening abstract and abstract sort. Experiments of the relevant data show that the model has better quality and higher efficiency in abstract generation.
Keyword: Mobile short message text; Information flow; Abstracts; Weights
1 引 言

手机短信在人们的生活中扮演着越来越重要的角色, 手机短信传播也被冠以“拇指文化”、“拇指文明”和“第五媒体”等美誉, 发展成为一种时代潮流。据12321 网络不良与垃圾信息举报受理中心调查报告[ 1], 2011年下半年中国手机用户平均每周收到短信息39.1条。手机短信可以说是最贴近民众的一种媒体, 具有极大价值的信息资源, 富含一些社会热点问题、突发事件信息, 社会舆情信息等。短信文本信息流通过信息压缩技术自动生成文摘, 可以给用户提供详实客观的热点事件信息, 自动追踪新闻事件, 提供事件的来龙去脉及发展趋势, 方便地识别出各种突发事件、新事件以及关于已知事件的新信息, 可广泛用于信息安全、舆情分析和预警等领域。本文从这些大量无序、杂乱、无结构的短信文本信息流中, 采用内容过滤的方法对动态内容的演化过程进行差异性分析, 利用统计的方法找出最能代表主题的句子作为摘要句, 使动态生成的文摘内容具有覆盖性、主题性, 以保持文摘的语义质量。

较早的基于话题的文摘抽取是1999年Carbonell等[ 2]提出的MMR(Maximal Marginal Relevance)算法, 该方法在计算句子权值时考虑到信息新颖程度和用户关注程度, 避免文摘中出现冗余句子。2006年, Mirella[ 3]提出一种利用时序排列文摘句的策略, 根据最先出现文摘句的文章发表日期作为这个句子的发生时间。对于短信文本集摘要提取, 2008年Hu等[ 4]提出的博客文章摘要方法和Zajic等[ 5]提出的电子邮件摘要方法都属于这一类。综上所述, 以上研究都是建立在增量式聚类基础上, 多采用传统静态文本处理方法, 没有考虑到短信文本信息流的一些突出特征:

(1)短信文本信息流中常常会出现网络用语、口语化短语和一些变形字等, 如网络用语“FB”意指“腐败”, 聊天常用语“小资”意指“单身女”, 论坛常用语“潜水”意指“呆在聊天室里不说话”等。变形字如垃圾短信中用“发piao”表达“发票”, 用“收费交底”表达“收费较低”等。

(2)作为手机短信等特殊媒体, 对重要话题、突发事件话题或舆情信息, 一般收到信息后或修改少量内容或不修改(绝大多数都不修改内容)就马上进行传播, 因此表达同一主题的短信文本集中会出现很多的相同特征词。

(3)当一个热点话题或突发事件发生时, 作为手机短信等特殊媒体传播速度非常快, 它们的实时性较高, 因此某一时间段内的“大类别”才是通常意义下的“热点”。

根据以上短信文本信息流的特点, 本文研究基于以下4个方面:

(1)短信文本信息流具有时序性, 将生存时间划分为多个时间片段进行讨论, 以提高算法的效率;

(2)传播同一热点话题的邻近短信文本片段必然包含一些相同特征词, 因此在邻近短信文本中利用共现词统计来描述它们的相关程度更为合理;

(3)根据短信文本信息流的特点定义了共现相关度意义下的孤立点概念, 并根据文献[6]思想, 处理掉了短信文本信息流中大量孤立点, 这是由于孤立点缺乏描述热点话题信息, 如果算法将大量运行时间浪费在孤立点数据处理上, 会导致算法的低效;

(4)对Single-Pass增量式聚类的算法进行改进, 将历史数据生成的文摘与当前短信文本集比较, 去掉冗余部分, 动态生成新的文摘。

2 基于短信文本信息流的共现相关度

短信文本信息流的动态文摘是一种具有时序偏向的多文本文摘, 它研究的对象是信息流动态演化信息的关联文本集。

2.1 基本概念

动态文摘是在主题相关性的基础上考虑多个文本集之间的时序关系, 如果把短信文本信息流S的生存时间T划分为n个时间段t1, t2, …, tn, 各个时段包含的文本集分别为STS1, STS2, …, STSn, 则短信文本信息流的文摘提取即为以文本集STS1, STS2, …, STSn-1中提取的文摘为基础, 进一步提取出短信文本集STSn中的文摘, 去掉历史数据文摘中的冗余部分, 进行合并。当n=1时, 问题就转化为静态短信文本集文摘提取问题。短信文本信息流的分解如图1所示:

图1 短信文本信息流的分解图

.

定义1: 称短信文本集STS1, STS2, …, STSn-1为历史短信文本集, 记为STh; 称STSn为当前短信文本集, 记为STc。

定义2: 设短信文本信息流S到文摘空间的映射为Φ, 历史短信文本集STh的文摘记为Φ(STh), 当前短信文本集STc的文摘记为Φ(STc)。

定义3: 设ST是短信文本, 取某一固定时刻T0(如2012年1月1日0时0分0秒)为时间基准, 定义ST接收时刻为距离T0的毫秒数, 记为τ(ST)。

2.2 短信文本的共现相关度

定义4: 设wi和wj是短信文本集STSi中的特征词, 如果存在短信文本ST∈STSi, 使得wi, wj∈ST, 则称特征词wi和wj关于短信文本ST共现, 简称词共现。

一般地, 作为短信文本信息流这一特殊的媒体, 如果两个短信文本在同一短信文本集STSi中传播某一热点话题时, 会出现多个特征词共现。

定义5: 特征词wi, wj的词共现度定义为:

其中, M表示STSi内互异的特征词的个数, N表示STSi内wi和wk或wj和wk关于某短信文本ST至少共现一次的词wk的数量。用n(wi, wj)表示特征词wi, wj共现的短信文本数, 则tf(wi, wj)定义如下:

定义5的意义在于STSi内与wi共现的特征词和与wj共现的特征词越多且特征词wi与wj共现的短信文本数量越多, 说明这两个特征词相关度越大。

另一方面, 当某一热点事件发生时, 各种媒体传播短信文本会连续地接收、转发, 因此短信文本数据流中如果两条短信文本STi和STj的|τ(STi)-τ(STj)|越小, 则STi和STj表述同一主题的可能性越大。以下给出两个短信文本特征词语义共现相关度概念。

定义6: 特征词wi∈STi, wj∈STj, 记t=|τ(STi)-τ(STj)|, wi与wj的共现相关度定义为:

其中, λ为影响因子。

定义6的特征词共现相关度考虑到了短信文本的时间特征。

定义7: 设短信文本ST中句子sensii=(wi1, wi2, …, wip), sensij=(wj1, wj2, …, wjq), 则sensii和sensij的共现相似度定义为:


类似的, 也可以用公式(4)定义短信文本STi和STj的共现相似度。

定义8: 短信文本表示为句子集合STi=(sensii1, sensii2, …, sensiim), STj=(sensij1, sensij2, …, sensijn)∈STSi, STi和STj的共现相似度定义为:


定义8说明: 如果两短信文本中彼此共现相关度较高的特征词越多, 而在各自文本中特征词共现的比例越高, 说明这些特征词更能反映它们在短信文本中的重要性。

定义9: 设ST0是短信文本集STSi中的一个短信文本, 实数δ> 0, 记:
Cohe_δ(ST0)=|{ST|STSim(ST0, ST)≥δ , ST∈STSi}|.

如果有:

则称ST0为共现相关度意义下的孤立点。其中α为调节参数, 0< α< 1, |STSi|表示短信文本集STSi中所含短信文本的篇数。

根据Power Laws和Pareto分布特征原理[ 7]可知, 短信文本信息流中孤立点短信文本数量远远大于非孤立点短信文本数量。本文定义孤立点的意义在于对海量短信文本信息进行研究的过程中, 清除掉孤立点的短信文本, 可以大大提高短信文本信息流文摘提取的效率。

3 基于短信文本信息流的自动文摘提取模型
3.1 自动文摘提取模型的主要思想

在短信文本信息流S中, 本文假设按图1进行了时间段划分, 并且历史信息集STh的文摘Φ(STh)已经生成, 对于当前短信文本集STc, 先用静态文本集生成文摘的方法生成文摘Φ(STc), 则S生成的动态文摘为Φ(STh)∪(Φ(STc)- Φ(STh)), 如图2所示:

图2 短信文本信息流S的动态文摘生成

.

基于短信文本信息流的自动文摘提取模型的工作流程为: 对短信文本信息流的历史数据STh和当前数据STc根据一些特征进行句子相似度计算; 根据句子权值选取句子并去除冗余信息; 对句子排序并选取相似度最低的句子实现短信文本信息流的文摘抽取。

3.2 候选句权值

短信文本信息流的文摘由历史数据和当前数据的相似度很小的重要句子按一定顺序排列而成。在文本中拥有词频率高的特征词通常对该语句的语义贡献较大, 称为拥有较高的权值, 同样对文本或类别语义贡献大的句子也称拥有较高的权值。如果t=τ(STi), w是短信文本STi的特征词, weight(STi, t, w)表示w在STi中的权值, 则有

其中, tf(STi, w)表示特征词w在短信文本STi中出现的次数, Nt表示STSi内t时刻前短信文本总数, dft(w)表示STSi内t时刻前的包含特征词w的短信文本总数。

候选句的权值是判定该语句能否成为文摘句的依据, 文献[9]和文献[10]都考虑到句子的特征词位置、长度等属性, 通过分析短信文本信息流的真实数据集信息发现, 在口语化表达模式下, 这些属性在短信文本信息流中没有规律性, 因此, 短信文本信息流句子权值主要依赖于特征词信息。例如, 一个问题的提出可能在句首也可能在句尾, 可以用简略句叙述也可以用复杂句叙述。候选句权值定义如下:

其中, n是句子sensi 包含的所有特征词数目。

为了保证当前短信文本信息流数据STc中选出的文摘句sensi和历史数据STh的文摘句不重复, 本文利用MMR技术[ 2]来动态调整候选句的权值如下:

其中, β是调节参数。由公式(9)可以看出, 当STc中句子sensi动态调整候选句权值越大, 则sensi与STh中句子相似度就越小。

3.3 短信文本信息流的自动文摘提取算法

算法是在历史数据文摘Φ(STh)已经生成的基础上进一步提取短信文本信息流文摘, 对于历史文摘Φ(STh)可以借助于静态文摘生成方法。

算法1: 基于短信文本信息流的自动文摘提取算法.

输入: 短信文本数据流S及历史数据文摘Φ(STh), 句子数阈值mc.

输出: 短信文本数据流S文摘.

对STc中的每篇短信文本进行分句、分词的预处理, 去掉停用词, 进行词频统计得到向量模型VSM.

for i=1 to |STc|.

if STi是共现相关度意义下的孤立点或STi不超过5个汉字短信 then.

STc= STc –{STi}.

Endif.

// 去掉短信文本的孤立点信息和低于5个汉字的非叙事信息.

endfor.

求出STc的句子集合, 记为STc_sensi.

利用公式(8), 计算STc_sensi中每一个句子的权值.

i=1.

while (i< =mc).

利用公式(9), 调整STc_sensi中的每一个句子的权值, 找出权值最大的句子sensimax.

Φ(STh)= Φ(STh)∪{sensimax},
STc_sensi=STc_sensi-{sensimax}.

i=i+1.

endwhile.

// 生成文摘候选句子集合STc_sensi.

对候选文摘句子集合STc_sensi进行聚类, 得到类别集合{Ck}.

// 将叙述同一个事件的文摘句聚为一类.

for (每一个文摘候选句类别Ck).

// 对每一文摘候选句类别Ck生成某事件的子文摘.

按文摘候选句的排序顺序如下:

如果两个句子分别属于两个短信文本STi和STj, 且τ(STi)< τ(STj), 则属于STi的句子在前.

如果两个句子属于同一个短信文本, 则短信文本中原句子先后排列顺序不变.

生成类别Ck的子摘要Sub_abstractk.

endfor.

将每一类别Ck的子摘要Sub_abstractk合并为短信文本信息流文摘.

输出短信文本信息流文摘.

该算法中去除了孤立点和不超过5个汉字的短信文本, 这是因为它们基本上不含热点事件信息。由于多文本摘要抽取的句子是从各个文本中抽取出来的, 句子间的连贯性较差, 对文摘句进行归类和排序, 归类目的是将叙述同一事件的候选文摘句聚为一类, 在同一类中根据文献[11], 如果文摘句子出现在同一个短信文本中, 按文摘句在文章内部的顺序对文摘进行排序, 如果文摘句在不同短信文本中出现时, 按照叙事线索的时序关系进行排序, 这样就会使生成的文摘尽可能地通畅。

4 实验结果及分析

时序多文本文摘是一个新的研究课题, 目前还没有公用的语料和评测。本文实验数据是从江苏某短信运营商截取从2012年2月1日0点整到4月30日24点整的短信息, 并从中挑选了9.85万条手机短信文本进行人工标注。抽取出如载有化学品的船在江阴段沉船、江苏沿江部分城市出现市民抢购矿泉水、房地产广告、元宵节祝福、房屋租赁、房屋销售、商品广告等142个话题。实验结果如图3所示:

图3 短信文本信息流文摘自动抽取实验结果

.

ROUGE[ 12]是文本信息集自动摘要提取的最常采用评测工具, 是一种基于词共现的召回率的指标。由于实验语料基于话题的性质, 所以选取ROUGE评价方法最为合适。

4.1 孤立点和特征词频率统计

为了简化问题, 先对9.85万条短信样本去重, 得到42 327条短信文本, 随机连续取某时间段内10 000条短信文本进行实验, 利用K-means算法进行聚类, 类别个数k取10 000, 该实验中对于短信文本个数超过15的类别定义为大类别, 短信文本个数小于5的为小类别, 实验中取δ=0.01, 结果如表1所示:

表1 大、小类别和孤立点数目实验结果

从表1可以看出, 在10000条短信文本中, 孤立点短信文本条数占样本总数的61.76%, 而大类别数目仅占34个, 大类别包含的短信文本的个数仅占样本数的9.34%。因此本文算法中去除孤立点可以大大提高算法的效率。

短信文本是一种典型的文本, 含有不超过74个汉字, 以叙事为主, 很少有修饰语, 所以存在很多的重复词。对上述10 000条短信文本的实验数据进行固定特征词个数的短信文本条数统计实验, 结果如图4所示:

图4 含有特征词个数的短信文本条数实验

.

分析该组实验结果可以看出, 约94%的短信文本含有8-14个关键词, 短信文本的平均长度为11个特征词, 所用特征词大多数出现在由 6 000 多个特征词组成的词表中。

4.2 抽取文摘句个数对文摘质量的影响

算法1中, 需要输入句子数阈值mc, 下面实验测试短信文本所选取的句子数对文摘抽取的影响, 仍然将上述10 000条短信作为实验样本, 实验范围取2-6个句子数进行, 并用目前常用的评价文摘质量好坏的标准ROUGE-2 评价指标[ 12]进行评价, 实验结果如图5所示:

图5 抽取短信文本句子数对文摘质量的影响

.

用ROUGE-2对生成文摘质量进行评价, 图5给出算法1随句子个数改变的变化趋势, 在句子数达到3或4时, 其质量最高。将短信文本特征词与句子结合实验样本比较分析, 每条文摘语句基本上含有3-4个特征词。

4.3 基于短信文本信息流的几种文摘生成方法比较

在前面实验的10 000条短信文本基础上进行, 为了便于叙述, 将文献[7]算法简记为Blog_abstr, 文献[9]的算法简记Email_abstr, 本文算法简记为Short_text。取话题个数为16, mc=3, λ=0.01, 为了减少文摘句冗余, 取β=0.4, δ=0.05, 将Short_text、Blog_abstr和Email_abstr算法进行比较实验, 得出三种压缩比例(5%, 10%, 15%)下的文摘, 如表2和表3所示:

表2 ROUGE-1评价结果
表3 ROUGE-2评价结果

从实验结果可以看出, ROUGE-1的值普遍高于ROUGE-2的值, 这是因为ROUGE-1是对单个词进行统计, 而ROUGE-2是针对2-gram统计的, 系统文摘的2-gram低于单个词共现频率; Short_text优于其他两种算法, 这是因为该算法充分考虑了时序短信文本的词共现率和文摘句子的冗余, 而Blog_abstr算法是通过回复评论和初始帖子之间主题、引用和提及关系计算句子权值, 然后抽取初始帖子中权值大的句子作为摘要结果, Email_abstr将整个邮件文本作为集合, 没有时间信息本身的形式化描述, 而且也没有充分考虑到文摘句子的排序, 因此抽取的文摘质量较差。

在算法运行的时间效率上, 由于Short_text在短信文本集STh和STc中先是清除孤立点信息和少于5个字的短信文本, 需要占用一些时间, 所以当低于2 000条短信文本时, Short_text所用时间较长, 当文本条数超过3 000时, 由于清除了大量孤立点信息和少于5个字的短信文本, Short_text速度明显增快, 而且短信文本数量越大, 效率越高。在Email_abstr和Bolg_abstr中, 由于Email_abstr没有根据句子权值进行排序, 因此速度要快一些。三种文摘生成算法时间比较如图6所示:

图6 三种文摘生成算法时间比较

.
5 结 语

短信文本信息流的文摘生成是为了达到特定任务或任务要求, 从动态短信文本信息流中提炼出来的最重要的内容生成的一个缩小版本。本文根据短信文本信息流的特点, 利用词共现定义短信文本的相似度, 利用TF-IDF定义特征词在短信文本中的重要程度, 进而又定义了句子在短信文本中的权值。对于文摘句的获取基于两个方面考虑: 在当前短信文本信息集STc中去掉与历史信息集STh的文摘句相似度大的候选句; 在STc- STh中选择出富含重要信息的文摘句。最后再利用和含文摘句较多短信文本的相似程度由小到大进行排序, 排序的目的是为了使生成的摘要有更好的可读性。未来工作将根据话题的种类生成有关各话题的文摘, 并提高文摘的准确度, 向更便于理解的自然语言领域靠近。

参考文献
[1] 12321 网络不良与垃圾信息举报受理中心. 2011 年下半年手机短信息状况调查报告[R/OL]. [2012-08-17]. http://12321.cn/pdf/sms1102.pdf. ( 12321 Report Center. Investigation Report of 2011 Second Half of Mobile Phone Short Message[R/OL]. [2012-08-17]. http://12321.cn/pdf/sms1102.pdf. ) [本文引用:1]
[2] Carbonell J, Goldstein J. The Use of MMR, Diversity-based Reranking for Reordering Documents and Producing Summaries[C]. In: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA: ACM, 1998: 335-336. [本文引用:2]
[3] Lapata M. Automatic Evaluation of Information Ordering: Kendall’s Tau[J]. Computational Linguistics, 2006, 32 (4) : 471-484. [本文引用:1] [JCR: 0.94]
[4] Hu M, Sun A, Lim E P. Comments-oriented Document Summarization: Understand ing Documents with Readers’ Feedback[C]. In: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA: ACM, 2008: 291-298. [本文引用:1]
[5] Zajic D, Dorr B J, Lin J. Single-document and Multi-document Summarization Techniques for Email Threads Using Sentence Compression[J]. Information Processing and Management, 2008, 44 (4) : 1600-1610. [本文引用:1] [JCR: 0.817]
[6] 彭泽映, 俞晓明, 许洪波, 等. 大规模短文本的不完全聚类[J]. 中文信息学报, 2011, 25 (1) : 54-59. (Peng Zeying, Yu Xiaoming, Xu Hongbo, et al. Incomplete Clustering for Large Scale Short Texts[J]. Journal of Chinese Information Processing, 2011, 25 (1) : 54-59. ) [本文引用:1] [CJCR: 1.13]
[7] Newman M E J. Power Laws, Pareto Distributions and Zipf’s Law[J]. Contemporary Physics, 2005, 46 (5) : 323-351. [本文引用:1] [JCR: 2.614]
[8] 黄承慧, 印鉴, 侯昉. 一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J]. 计算机学报, 2011, 34 (5) : 856-864. (Huang Chenghui, Yin Jian, Hou Fang. A Text Similarity Measurement Combining Word Semantic Information with TF-IDF Method[J]. Chinese Journal of Computers, 2011, 34 (5) : 856-864. ) [本文引用:1] [CJCR: 1.796]
[9] 郝秀兰, 胡运发, 申情. 中文论坛内容监测的方法研究[J]. 中文信息学报, 2012, 26 (3) : 129-136. (Hao Xiulan, Hu Yunfa, Shen Qing. Research on Content Monitoring on Chinese Web Forums[J]. Journal of Chinese Information Processing, 2012, 26 (3) : 129-136. ) [本文引用:1] [CJCR: 1.13]
[10] 刘美玲, 郑德权, 赵铁军, 等. 动态多文档文摘模型[J]. 软件学报, 2012, 23 (2) : 289-298. (Liu Meiling, Zheng Dequan, Zhao Tiejun, et al. Dynamic Multi-document Summarization Model[J]. Journal of Software, 2012, 23 (2) : 289-298. ) [本文引用:1] [CJCR: 2.181]
[11] 徐永东, 王亚东, 刘杨, 等. 多文档文摘中基于时间信息的句子排序策略研究[J]. 中文信息学报, 2009, 23 (4) : 27-33. (Xu Yongdong, Wang Yadong, Liu Yang, et al. Research on Temporal Information Based Sentences Ordering in Multi-document Automatic Summarization[J]. Journal of Chinese Information Processing, 2009, 23 (4) : 27-33. ) [本文引用:1] [CJCR: 1.13]
[12] Lin C Y. ROUGE: A Package for Automatic Evaluation of Summaries[C]. In: Proceedings of the ACL-04 Workshop. 2004: 74-81. [本文引用:2]