文档介绍：Approximate Lineag,Extr习LctionLineage Extraction Techniques forEmails by YuJunfeng Supervisor:Professor Yang Xiaochun Northeastern University June 2011 独创性声明本人声明,所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外,不包含其他人己经发表或撰写过的研究成果,也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名:香俊钤日期: 彦c,It拜多闷辨自学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后: 半年口一年/ 一年半口两年口学位论文作者签名:专饿蝽签字日期:弘J忻参闰骅怠导师签名: 签字日期:彩昧≯}I缉多A皿q 东北大学硕士学位论文摘要面向电子邮件的近似世系关系抽取技术摘要随着社会的进步和科学的发展,信息数据量呈爆炸性增长。面对海量数据, 人们往往希望知道某些数据是从09JL来的,怎么来的。数据世系描述了数据的产生、以及随时间推移而演变的整个过程,被广泛应用到科学计算、生物工程、数据库等领域中。然而现存的世系关系抽取技术,并不支持近似世系关系的抽取, 这给世系技术的应用带来了一定的局限。本文研究面向电子邮件的近似世系关系抽取技术。Email是信息时代的产物, 已被广泛应用在日常生活中。对于电子邮件的使用者来说,当邮件数量过于庞大且无法明确分类时,需要有一种简便、高效的管理和查询方法,用以帮助获得更多的有效信息。而世系概念的引入能很好地解决以上需求。抽取电子邮件之间存在的世系关系,不但可以将讨论同一主题的Email邮件聚集到一起,还能够描述这些邮件内在的衍生关系。但是目前并没有一种成熟的、针对于Email邮件的世系关系抽取技术。本文针对电子邮件的特点,重点研究支持电子邮件的有效近似世系关系抽取技术。本文首先给出了邮件世系关系、近似邮件以及近似邮件世系关系的形式化定义。其次通过分析EML邮件数据的特征,提出了一种针对于EML格式邮件的信息抽取方法,该算法能够对已有邮件数据进行高效的信息抽取和解码。然后在已有的定义以及邮件信息抽取结果的基础上,提出了邮件世系关系抽取算法,用以抽取邮件之间潜在的衍生关系。并使用建立索引、查询优化等方法,对该算法进行了简单优化。分析了实际应用中可能出现的两种近似邮件世系关系,包括查询内容的近似和主题的近似,分别结合q-gram算法和文本聚类的思想,处理了这两种可能存在的近似情况,并提出支持近似邮件世系关系抽取的算法。最后,,对本文所提出的算法进行了性能测试,并对测试结果进行了对比和分析。实验结果表明本文提出的算法能够高效支持近似邮件世系关系的抽取。关键词:世系;邮件;抽取;近似;聚类一II—东北大学硕士学位论文 Abstract Approximate Lineage Extraction Techniques forEmails Abstract With theprogress of society and science,the amount ofinformation data increases confront mass data,people always wants toknow where es fromand lineage describes thegeneration, and the whole process ofpropagate used,involving puting,bio-engineering,database and other ,the existing data lineage extraction technologies are not suitable forapproximate problem brings acertainlimitations totheapplication ofdatalineage technique. The problem we studied inthisthesisistheapprox