（计算机应用技术专业论文）基于后缀树模型的流文本表示研究及其应用.pdf

i h i 摘要 摘要 随着因特刚的不断普及，流数掘处理逐渐受到人们的关注。相对j 二传统的静 态数掘，流数掘只有高度的流幼性，对实时更新的要求较高。本文面向网络信息 内容分析这一背景，针对流数挺处理中的流文本表示问题，考察了现有的文本表 示方法，提出并实现了基f i 缀埘模型( s t m ) 的流文本衷示方法。该表示方法具 有以下特点： 利用f 舌缀树模型动念增删的特性，支持对流文本表示进行实时更新，直 接对后续操作结果产7 l 影响； 利用后缀树模型快速旺配的特性，可以实时获得表示流文本的向量，不 需要进行分词以及特征提取等复杂计算： 采用不定长匹配，得到合适的语0 粒度，能够较好地反映文本特征： 利用了上下文的位霄信息，可以为后续操作提供更多的信息量； 由于不需要进行分词和特征提取，该表示方法与具体语种无关。 在此基础上，本文将基于后缀树的文本表示方法结合分类算法，以 s p a m a s s a s s i n 邮件过滤平台为依托，实现了一个垃圾邮件过滤系统。 该过滤系统采用通用后缀树删( g s t m ) 表示训练集中的邮件，对于到达的 新邮件，利用邮件内容的上下文位詈信息，进行文本位置的不定长多元统计，从 而获得新邮件与不同训练集的相似程度，确定邮件所属类别。理论分析和实验表 明： 将长度为n 的新邮伺加入训练集，训练时问为0 ( n ) ，满足了训练集的动 念变化； 对长度为n 的新邮件进i ，过滤，过滤时廿j 为0 ( n ) ： 在相同语科上，该系统的准确串和召回二誊均达到或超过了其他基| 空日j 向量模型的邮件过滤办法； 完全独立f 语种，适川，：多i g 利，邮件几 时存在的情况。 通过理沦分析和实验验订l ：，本文所提出的基f 后缀树模型的流文本表示方法 具有有效性和实j h 性，有助j 流放训处州问题的进一步研究。 关键字：流文本表示，后缀村，文本分类，垃圾邮件过滤 t h i 了 r a b s t r a c t t h es t u d yo fs t r e a m i n gt e x tr e p r e s e n t a t i o nm e t h o db a s e do r l s u f f i xt r e em o d e l ( s t m ) a n di t sa p p l i c a t i o n z h a n gj i ，i n s t i t u t e o f c o m p u t i n g i e c h n o l o g y , c h i n e s e a c a d e m y o f s c i e n c e s d i r e c t e db yg u ol i 人b s t r a c t w i t ht h ep o p u l a r i t yo fi n t e r a c t m o r ea n dm o r ep e o p l ep a ya t t e n t i o nt ot h e m a n a g e m e n to fd a t as t r e a m d i f f ：r e n tf r o ms t a t i cd a t a , t h er e p r e s e n t a t i o no fs t r e a m i n g t e x ta p p e a lf o rh i g h e rs p e e do fu p d a t i n g f a c e dt on e t w o r kc o n t e n ts e c u r i t y , w er e v i e w o t h e rr e p r e s e n t a t i o nm e t h o da n dp r o p o s ear e p r e s e n t a t i o nm e t h o db a s e do ns u f f i xt r e e m o d e l ( s t m ) t h ea d v a n t a g eo f t h i sm e t h o di sa sf o l l o w ： b yt h es u p p o r to fs u f f i xt r e e t h ea l t e r a t i o no ft h et r a i n i n gc o r p u sc a l l a f f e c t s u b s e q u e n to p e r a t i o n si nr e a lt i m e b yt h es u p p o r to fs u f f i xt r e e t h em o d e lc a np e r f o r mf a s tm a t c h i n g o b t a i nt h e v e c t o rp r e s e n t a t i o no ft e x ta n da v o i dt h ec o m p l e xc o m p u t a t i o ns u c ha sw o r d s e g m e n t a t i o no rf e a t u r ee x t r a c t i o no f t h et e x t t h em o d e lc a nt a k ea d v a n t a g eo fc o n t e x tl o c a t i o na n dd os t r i n gm a t c ho fu n f i x e d l e n g t h ，w h i c hp r o v i d em o r ei n f o r m a t i o nt os u b s e q u e n to p e r a t i o n s t h ea v o i d a n c eo fw o r ds e g m e n t a t i o na n df e a t u r ee x t r a c t i o ns h o w st h a tt h e c a t e g o r i z i n gp r o c e s si si r r e l e v a n t t od ow i t ht h ec o n c r e t el a n g u a g ea n di sa l a n g u a g ei n d e p e n d e n tm e t h o d b a s e do nt h es p a m a s s a s s i n u 7 h i c hi saf r e es o f t w a r eo fs p a mf i l t e r i n g ，w ec o m b i n e d t h er e p r e s e n t a t i o nm e t h o dw i t ht h ec l a s s i f i c a t i o na l g o r i t h ma n dc o m p l e t e das p a m f i l t e r i n gs y s t e m t h ef i l t e r i n gs y s t e mb a s e do ns u f f i xt r e em o d e la n dt o o ka d v a n t a g e o fc o n t e x t l o c a t i o na n ds t r i n gm a t c ho fu n f i x e dl e n g t h t h e nc o m p u t e dt h es i m i l a r i t yb e t w e e nt h e t e s tm a i la n dt h ec o r p u st od e t e r m i n et h es o r to fe m a i lf i n a l l y e x p e r i m e n ta n d a n a l y s i so f t h ea l g o r i t h ms h o wt h a t t h et i m ec o m p l e x i t yo f t e x tp r c p r o c e s s i n gi no u rs y s t e mi so ( n ) ，w h i c hs a t i s f i e d t h es p e e do f u p d a t i n g ； t h et i m ec o m p l e x i t yo ff l i t t e r i n gi no u rs y s t e mi s ( ) ( n ) ； v 基于后缀树模型的流史小衷，j ：疗法研究及奠应用张占 a st ot h es a m ec o r p u s t h er e c a l la n dt h ep r e c i s i o ni sh i g h e rt h a no t h e rm e t h o d s b a s e do nv e c t o rs p a c em o d e l ： t h e c a t e g o r i z i n gp r o c e s si s i r r c l c v a n tt od ow i t ht h ec o n c r e t el a n g u a g ea n di sa l a n g u a g ei n d e p e n d e n tm e t h o d o v e r a l l ，e x p e r i m e n ta n da n a l y s i so ft h er c p r e s e n t a t i o ni n d i c a t et h a t ，t h er e p r e s e n t a t i o n o fs t r e a m i n gt e x ti sn o to n l yp r a c t i c a lb u ta l s oe f f e c t i v e w h i c hw i l lh e l pi ns t u d yo f d a t as t r e a m k e y w o r d ： r e p r e s e n t a t i o no f s t r e a m i n gt e x t s u f f i xt r e em o d e l ，t e x tc a t e g o r i z a t i o n ，s p a r ef i l t e r i n g v 毖于后缀树模型的；氚文本表j 方法研究及典应用张吉 图目录 圈2 一la v l 树结点及水体。8 图2 2b 树结点及整体9 图2 3链式容器散列9 图2 - 4 扩展散列9 图2 5线性散列1 0 图2 - 6改进的线性散列1 0 图2 7 t 树结点及整体1l 图3 一l字符串d i a b a b $ ”的后缀树2 0 圈3 2字符串d 结束舀：边e | ：2 l 图3 3添加d = “a b a b $ ”的# 符b t 的扩展操作2 2 图3 4添加d = “a b a b $ ”的字符b 时的添加操作2 2 图3 5添加d = “a b a b $ ”的7 符“$ ”时的分裂操作2 3 图3 - 6d l = “a b a b $ ”，d 1 - b a c $ ”的通用后缀树2 6 图3 7d - - a b a b $ ”的后缨树上添加后缀“b a c $ ”2 6 图3 8 d l 一a b a b $ ”，d 2 “b a c $ “的后缀树上删除后缀“a b a b $ ”2 7 图4 1 电j 二邮件系统j ：意一3 4 图4 2基fs p a m a s s a s s i n 平台的邮件过滤系统4 l 图5 1使用朴素贝叶斯方法在p u ib a r e 上的结果5 2 图5 2使用朴素贝叶斯力法在p u is t o p 上的结果5 2 图5 3 使用朴素贝叶妇方法在p u ll e m m 上的结果5 3 图5 - 4使用朴索贝叶斯疗江庄p u il e m ms t o p 上豹结果5 3 图5 一s 不同p 值在l i n gs p a mb a r e 上的结果5 4 图5 - 6 不同p 值在p b a r ej + 的结果：5 4 图5 7 不同预处理程艘n 0p u l 的实验结粜5 5 图5 - 8 不同预处理程艘的i i n gs p a m 的实验结果5 5 x 一蒙 表目录 衷2 1传统模型经排序牡刚 i 的索引6 表2 2文本实例7 表2 3数掘项的散列f r 7 农2 - 4文本的签名值8 衷4 1邮件传输代理软f j i ( mi a ) l l 较：4 0 表5 一l基于s t m 的分类方法的测试结果及统计结果4 6 表5 2 不同分类方法准确：缸耐比一4 7 表5 3系统定义变量说明4 8 表5 - 4p u l 系列语料说明5 0 表5 5基于s t m 的分类疗法方法部分实验结累5 l 表5 - 6 a n d r o u t s o p o u l o s 等人使用朴素贝叶斯算法的实验结果5 l 表5 - 7 语料l i n g s p a m i 的结粜对比一5 3 表5 8不同分类方法的时h j 复杂度比较5 5 x 荜于后缀树模型的流艾本表示疗法研究及其应用 张吉 声明 本人卢i ”】所譬交的论文址找个人n i 蛩师指导下进行的研究工作及取得的研 究成果。就我所知，除了文中轴别加以标 i ：和敛谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果。与我一川工作的同志对本研究所做的任何贡献 均已在论文中作了明确的 既f j 行表示了谢意。 作右签名：劫0 吨 日期：以占， 关于论文使用授权的说明 中囡科学院计算技术研究所仃权处理、保留送交论文的复印件，允许论文被 查阅和借阅；并可以公布论文的伞部或部分内容，可以采用影印、缩印或其它复 制手段保存该论文。 作者签名：张喀导师签名：却枥日期：0 x 6 f l l 第1 牵引言 1 1 问题的提出 第1 章引言 随着因特网在全世界的普及。网络传输技术的迅速发展，每天世界上有海量 的各种类型的信息在互联网一卜流动，比如文本信息、声音信息、图像信息等。信 息的高速增长迫切需要信息处理技术的不断进步。 根掘数据的存在形态，一般口丁以将数掘处理划分为两种对偶的形式：静态数 掘处理和流动数掘处理。静念数掘处理以数据为中心，整个数据集存储在一个庞 大的、相对稳定的中央存储介质中，并随时准备接受随机到来的用户数掘请求。 在数据集的尘命周期，绝大部分数据是稳定不变的，而频繁变化的是用户随时可 能提交的查询。静念数掘处理方式的典型应用包括：数据库管理系统、信息检索 系统、数据仓库系统等。长久以束，静态数掘处理得到了广泛深入的研究。 流动数据处理以查询为中心，数掘集仍然是庞大的，但具有高度的流动性。 而相对稳定的是用户查询，大虽预先定义的用户查询被注册到处理系统中，等待 数掘的到束。一旦数据到来，将驱动查询的执行。显然，数据密集的生产系统所 产生的同志数掘，都具有这种海鞋且流动的特点，这样的系统包括：互联网管理 系统、证券交易系统、电信系统、余融交易系统，实时传感器信号分析系统等。 这些应用面对的都是在线的、持续的高速流数据，系统处理的对象形态完全不同 于传统的静念数掘处理，由丁二存储窄问的限制，这些数据往往不可能完全保存到 存储器中，同时又必须不问断尤延迟地处理这些流数掘，以获得实时处理结果。 由此产生了一些新的基础性研究题。 流数据是数据元素的有序序列，序列中的数据元素顺序到达流数掘处理系 统。在某些具有并发性的应刚环境卜，流数掘中的元素可能同时到达，我们把同 时到达的元素视为一个列表，那么町以把流数掘建模为数掘元素列表的序列。流 数掘处理系统的输入数掘并小保仃在叮随机访问的磁盘或主存中，输入数掘以一 种瞬念的、持续的流的形式到达。概括来说，相对于传统数掘库模型，流数掘模 型主要有如f 儿个方面的特自l ： 流中的数抛，亡索在线到达： 从理论t i 兑，流数据的潲征人小足a ：限的：系统能存储的数据相对流数掘的 大小则是 e 常有限的： 一旦流数据中的某个元索终过处珲，要么被丢弃，要么被归档在储。但被丢 弃的数据元素可能需要再次破访6 d ； p 荩于后缀树模型的流文本表示方法研究及其应用 张吉 分析流数掘元素的结构，从简币剑复杂有这样几种： 不关心语义的7 - 行流，返利流j l 仃j j c 值为字符的一维结构； 结构化流数据，这样的浼数抛的数掘元袭町以视为关系元组，关系具仃剐定 的域，因此这样的流数扒l 仃一：f l i 结构，一维为元组序列，另一维为无组内 的域： f 耋占构化流数掘，如x m i 支流，这样的流数掘中存在着用户定义的，具 有一定语义的杯记，可用这! ! 杯记将流数掘划分为独立的流数据元素； 无结构数掘，如具有自描述结构的文本流，以及连续的视频流、音频流等， 这种流的结构信息完全包含在数扼的语义中，无法孤立地对数掘进行元素划 分。 本文上要针对第一种数据厄东结构，解决数掘表示的问题，即流文本衷示问 题。流文本表示针对不同的应川，将后续操作所需要的信息量表示在内存中，随 着文本的不断变动，动念地维护文本，并实时地对文本变动做出反应。针对流数 据模型特性，本文提出了流文本表示所要达到的目标： 。 t 线性增删，当增加或者删除部分文本时，不需要对其他文本的表示进行改动， 从而满足文本流动性的需求； 线性查找，当需要查找的文本内容长度为n 的情况下，必须在o ( n ) 的时问内 得到与该内容相关的信息： 线性空日j ，当被表示的文本内容长度为n 的情况下，流文本表示所需的空间 最大不超过0 ( n ) ； 尽可能多保留信息量，以伦后线操作进行正确的判断。 1 2 应用背景 f l x , lr 静态数据类型，流文小的衷尔仃很多实时性要求很高的应用需求，如 文本在线分类等。通常柬晓，文小分炎足面向自然语矗处理的，在这种分类中旷 确性远比分类的速度更重要。f h 足红刚络内容分析中，本文认为分类的速度和分 类的j f 确性都必须充分考虑。l i 对流文本，还需要考虑当训练集变动的惝况f ， 分类结果能否及时地反映这种变z 川 况。日6 h ，在文本分类研究领域，占统治地 位的文本表示方法是s a l t o n 挺 i j 的向量宅删模型。基于向量空问模型的文本 分类方法训练过 。l 中大都需要分、特征提取等繁琐过程，当训练集中部分文本 变动时，需耍霞复整个训练霸、的训练过柑。叫此i 焉受一种新的流文本表示方法， 以满足训练集实时更新的需求。 筇1 章引言 垃圾邮件过滤、实时新闻分炎等等都是文本在线分类的具体应用。 垃圾邮件是互联网上一个 1z & ，7 峻的问题，邮件发送者通过互联网十j 描、 窃取邮件列表等手段获得目杯h l _ j l f 。 圾邮件的发送引擎造价低廉，发送者也无 需为发送邮件另外付费，而il j 眨发送肯发送的信息不违法，他们的发送行为就 不违法。所有这些部导致了丁i 驳网u l 界中垃圾邮件的泛滥，这已经给人们带来了 极大的不便，并极大地消耗j ，州络资源。中国互联网协会公布了2 0 0 4 年中国垃 圾邮件状况调查报告。报告甚示，中因今年处理垃圾邮件浪费的g d p 高达4 8 亿 元人民币，中困邮件用户现在，均每人每天收到邮件7 0 5 封，其中有1 8 5 封为 垃圾邮件，占2 6 2 。另掘新华 十报道，中国互联网协会反垃圾邮件协调小组负 责人透露，截至1 1 月底，2 0 0 3 午向中因服务器发的垃圾邮件约有1 5 0 0 亿封， 占我国互联网用户收到的电子邮件总数的3 0 。大型的邮件服务系统一般都非 常繁忙，尤其是在受到垃圾邮件攻一右的时候，必须对接收到的邮件迅速进行处理， 同时不对正常的邮件收发产! l 影响。对垃圾邮件进行识别的分类器可以配置在大 型邮件服务器中，对出入的邮件是否足垃圾邮件进行迅速判断。 在线分类还可以应用于新闻分类。在竞争同趋激烈的传媒界，第一时问报 道突发性事件是所有的编辑梦寐以求的事情；而对于某些提供最新资讯供高层决 策的情报机构，对f 突发事件所自信息的获耿更是至关重要。比如对于伊拉克战 争，在战争丌始以前，人们都知道战争会爆发，可谁也无法预测战争具体什么时 候开始，于足各大报纸、新闻网站不得不派专人同夜守护在网络上，以待战争丌 始的蛛丝马逊。这种守护工作址i r 常繁琐的，而应用在线分类系统可以代替人来 守护前端不停从网络收策最新的信息，在线分类系统将这些信息迅速判断其 类别，一旦有用户感兴趣的f ；。息，可以i j 上向用户反馈。在线分类系统对于新闻 机构和情报系统的实时采编是作常有帮助的。 1 3 内容安排 本文的t 要r 作包括： 提出并实现了基于后缀埘嵌掣( s t m ) 的流文本表示方法，该方法能够在线 性时日j 、线性空日j 内衷1 ：流文本，当部分文本增删时，不影响其它文本的 表示，j f h 能够对j l 舌 l 操作j “7 1 - 直接的影响。 将後流文本表示方法羊分炎算法棚结合，以s p a m a s s a s s i n 垃圾邮件过滤 平台为基础，实现了垃圾邮件过滤系统，并通过实验和理论分析证明了该 系统的性能，从而证明j ，旗j 二后缀树模型的流文本表示方法的有效性和实 用性。 轼于后缀树模型的流文本表示方法研究及其应用张吉 第二章讨论了以往在文本农乃i 办丽的研究成果。第三章提出了基于后缀树模 型的流文本表示方法并针对小的廊川肿毙进行改进。第e q 参介绍了垃圾邮件过 滤方法的研究现状和垃圾邮t i 过沈p 台s p a m a s s a s s i n ，并阐述了如何结合该平 台，将基于s t m 的流文本表_ ：方江年分类方法应用到垃圾邮件过滤系统中。第 五章给出了文本分类及邮件过滤的实验结果，并对实验结果进行分析比较。第六 章对全文进行总结，川时展掣卜步工作。 毓2 章研究现状 2 1 概述 第2 章研究现状 一个文本炭现为一个山77 7 和 ，j 、点符号组成的字符串，由字组成词，由词组 成短语，进而形成句、段、节、囊、篇等结构。由于目前的计算机从本质上束讲 还只能处理o l 数字串，不能贞矿理解文本的语义，因此直接使用整个字符串作 为分类的原始输入足很不方便的，有必要寻找一种更精练的形式化表示方法来将 文本数量化。 目前，在信息处理方向，卜，文本的表示主要采用向量空日j 模型( v s m ) 。经典 的向量空问模型是s a l t o n 等人十年代未提出的，并成功地应用于著名的s m a r t 系统，已成为最简便高效的文本表示模型之一，它在大规模真实文本处理方面具 有很强的优势 s a l t o n1 9 9 4 】。 v s m 的几个基本概念： 文档( d o c u m e n t ) ：泛指一般的文本或文本中的片断( 段落、句群或句子) ，一 般指一篇文章。尽管在某些文章中文本可以足多媒体对象，但在我们以后的 讨论中只认为是文本对象。并且对文档与文本不加以区别。 特征项( t e r m ) ：文档的内容特征常常用它所含有的基本语言单位( 字、词、 词组或短语等) 来表示，返些基本的语占单位统称为项，即文档可以用项集 ( t e r m l i s t ) 表示为d ( t l ，1 2 ，t n ) ，其中“是项，l k s 烈。 特征项的权重( t e r mw e i g h t ) ：对j 二含有n 个项的文档d ( t l ，t 2 ，t n ) ，项 t k 常常被赋予一定的权重w k ，表示它们在文档d 中的重要程度，即：d = d ( t i ，w i ：t 2 ，w 2 ；t n ，w h ) ，简记为d = d ( w i ，w 2 ，w l c v ) 。这时我 们晚项t k 的权重为w k ，1 k o _ 当两类完全不交叠时j p 取得最大值 _ 当两类概率分白完令相同时，即两类在特征空间概率分布完全重叠 时，j p = o 这种概率分白距离可一般表示为： 印( ) = i g p ( x1w d ，p ( xw 2 ) ，p l ，p 2 d x 其中p l 、p 2 分别为两类的先验概：善，p ( x w 1 ) 为特征空| 日j 上w l 类的概率密 度函数。 常用的概率分却距离足b h a t t a c h a r y y a 距离。 基于熵函数的可分离性判掘 上面的基于概率分白的距离刈掘足定义在先验的类条件概率分柿上的，而基 于熵函数的可分离性判掘足定义在后验概；蕃上的。如果各类后验概率相等，即 p ( w i l x ) - q c ( c 为分类数目) ，则村小的炎别元法判断；如果某一类的后验概率为1 ， 其它类的后验概率为零，则a r 以免错误地做出把样本归属于后验概率为1 的类 别。一般的，后验概率越集中在很少的几个类别上，则分类的错误率就越小，反 之，后验概率分响1 越平缓，即接近均匀分如，则分类的错误概率越大。 为了衡最后验概率分却的欠。”秤皮，町以借助信息论中熵的概念作为衡嫠指 标。- 一般使用的墒函数有： s h a n n o n 熵 川”= 一p ( w i l x ) l o g ，j p ( w i l ) ，t i 第2 章研究现状 平方熵 ? = 2 1 1 - 尸2 ( w i l ) i = 1 2 4 2