1、毕业设计开题报告 计算机科学与技术 文本特征信息的搜索与分类系统设计 一、选题的背景、意义 信息无时不在，无时 不 有，具有普遍性、载体依附性、价值的相对性、时效性、共享性、可伪性等一般特征。 随着信息技术的应用与发展和互联网的普及，庞杂的文本信息流急剧增多，对于我们的认知与决策带来了很大的压力， 如何有效地组织和管理这些信息并快速、准确、全面地从中找到用户所需要的信息是当前信息技术领域面临的一大挑战。 文本信息是网络信息中很重要的一部分。对于 文本信息 的整理和显示，需要经过一定的步骤和方法来完成的。文本的搜索是 要求用 户提交查询关键词 （文本特征） 来查找与之匹配的 一系列 信息 ，通过
2、相关的调整，进而能够让用户有效、迅捷地为用户获取所要的文本信息。 文本特征信息的搜索与分类离不开搜索引擎技术和文本挖掘相关的技术。这两者缺一不可。 先谈一下搜索引擎技术的发展状况。现 如今，搜索引擎已成为仅次于门户的互联网第二大核心技术。在短短十年的时间内，搜索引擎迅猛地发展起来。随着互联网的普及和网上信息的爆炸式的增长，搜索引擎越来越引起人们的重视 ， 搜索引擎已成为一个非常热门的话题。搜索引擎技术现在已成为计算机产业界和学术界争相研究和开发的对象。通 过对搜索引擎技术和检索任务方面的词语进行统计和分析，一方面可以反映出学术界对搜索引擎的关注程度，另一方面也能大致分析出搜索引擎的发展现状以及
3、发展趋势。 搜索引擎的发展 大致可以 分割成 3 个阶段 。 第一个阶段里 的搜索引擎 以雅虎为标志，主要依靠人工分拣信息 ， 用分类目录搜索信息 。这一阶段的搜索引擎技术还 处于萌芽阶段。 虽然这样，但 此时各种搜索引擎概念 也 相继出现 了 ，如目录式搜索引擎、全文搜索引擎、元搜索引擎等。这一阶段，词频相对较高的关键词是全文检索、智能检索、多媒体、图像搜索、语义网络、分类目录、分类主题等。这个时期分 类搜索是网络搜索的主流。 搜索引擎在第二个阶段里开始迅速发展。最负盛名的搜索引擎当数 Google，它在 1999 年以不可抵挡的势头走向世界 ， 依靠机器抓取、分析进行网页搜索 1， 带动了
4、新技 术 PageRank 和锚文本技术的发展。此阶段的热点词语有关键词检索、倒排索引、全文索引、自动摘要、链接分析等。这段时期链接分析技术、 PageRank 算法以及 Hit 算法等如火如荼地展开。人们基本认为 Web 信息检索开始进入了新一代搜索引擎阶段 2。 第三个阶段里搜索引擎的研究变得非常火热，搜索引擎越来越向智能化、个性化、专业化 的方向发展，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品。通过对文本分类、聚类、用户行为分析、分布式、相关反馈、智能代理、查询扩展等高频词的分析，我们可以看出，人工智能、数据库、数据挖掘、自然语言理解等领域的研究有力地促进了搜索引擎的发展。 再谈一
5、下文本挖掘相关的发展。虽然信息通讯技术的发展及由此带来的信息量的增长，极大地促进了人们的沟通和交流，为人类的文明和发展做出了巨大的贡献。但同时，信息爆炸式增长带来的消极影响正在凸现。在此，国际上提出了多项文本挖掘计划，以期对网上 “ 堆积如山 ” 的巨大的信息矿床进行 有效的过滤、开发与综合利用，把信息变成能够方便利用的知识和财富。 NIST（美国国家技术标准局）和 DARPA（美国国防高级研究计划局）组织的 TREC（文本检索会议）会议是国际上文本挖掘领域的著名评测会议，从 1992 年起每年召开一次，迄今已经召开了 13届。 1991-1998 年， DARPA 资助了 TIPSTER 文
6、本计划，主要着眼于三项基础技术的评测：文档检测、信息提取、摘要。 2003 年， DARPA 开始启动以机器学习为核心的计划 PAL4，为期 5 年，首期 (1-1.5年 )投资 2900 万美元。 PAL 包含 2 个子计划：其中， CALO5 子计划是整个 PAL 计划的核心 (2200 万 )，将机器学习技术放到了国家安全的角度来考虑。美国主要大学与公司参加这个子计划。由此可见，对海量网络信息的有效处理和深层次综合利用离不开文本挖掘技术，文本挖掘将成为人们应对信息时代挑战的强大利器之一 3。 二、研究的基本内容与拟解决的主要问题 在该系统中要实现文本信息的搜索与分类，就必须期望实现以下功
7、能： 1)美观的搜索界面，按文本关键字搜索； 2)搜索引擎，完成把所要查询的关键字与网上文本信息进行匹配； 3)数据库设计，实现把网上匹配的文本特征信息下载并 记录，为显示结果提供依据； 4)结果显示界面，显示项目包括关键字、相似度和网址，并按一定的顺序罗列。 研究 要求是在已有的专业理论知识和应用能力的基础上，掌握 Java 编程 和 WEB 技术 ，能较熟练的运用 Java 开发工具 Myeclipse 及 SQL SERVER 2000 数据库，研究开发出具有上述功能的文本特征信息的搜索与分类系统。 在研究途中最主要的一个问题是如何设计一个搜索引擎来实现在网上根据文本特征搜索文本信息并进
8、行分类。这一点很重要，但充满着困难。第二个问题是如何构建数据库。搭建一个好的数据库结构会省去很多不 必要的烦恼与省下不少的精力。第三个问题是自己所学的知识面很窄，技术掌握不到位，不全面，不能一下子就能解决可能碰到的问题。针对这一点就需要查阅大量的文档和书籍，还可以请教导师来帮忙解决。 三、研究的方法与技术路线、研究难点，预期达到的目标 文本挖掘是以半结构（如 Web 网页）或者无结构（如纯文本）的自然语言文本为对象的数据挖掘。它是从大规模文本数据集中发现隐藏的、重要的、新颖的、潜在有用的规律的过程 4。文本挖掘首先要从文本中提取适当的特征，将文本表示成计算机能够理解的数字形式。根据处理速度和精
9、度的需要，可以 对文本中的特征进行选择优化。然后采用各种文本挖掘方法发现隐藏的知识模式，以满足用户评价标准的模式最终输出，成为指导人们实践的有用知识。 文本挖掘之前，用信息抽取技术 (Information Ex traction， IE)进行非结构化的信息挖掘。但随着 IE 系统的发展，人们认为它更适合利用精确的查询相匹配概念和文字找出关系。 IE 系统的主要优势在于以下几点：查询的精确，输出结果的透明和直接进入数据库或真实地显示出来。“文本挖掘”这个词通过类似于传统的数据挖掘系统一样被应用到这些系统中。针对 IE 对自然语言处理的不足 ，文本挖掘可以通过统计共现方法处理自然语言。 文本具有
10、有限的结构，有的甚至没有结构，此外计算机不能直接处理人类的自然语言，所以对文本数据源要进行数据预处理。数据预处理主要包括分词技术 (英文文本则需要 Stemming 技术 )和特征表示和特征提取。因为中文词与词之间没有固有的间隔符 (空格 )，需要进行分词处理 5。 文本经过分词、特征表示和特征提取后就可进行挖掘了。对于非结构化问题，一条途径是发展全新的数据挖掘算法直接对非结构化数据进行挖掘，由于数据非常复杂，导致这种算法的复杂性很高；另一条途径就是将非结构化问题 结构化，利用现有的数据挖掘技术进行挖掘，目前的文本挖掘一般采用该途径进行处理。对于语义关系，则需要集成计算语言学和自然语言处理等成
11、果进行分析6。常用的文本挖掘技术有：文本结构分析、文本摘要、文本分类、文本聚类、文本关联分析、分布分析和趋势预测。 要表示文本首先要提取文本特征 7。文本的特征应该具有以下特点：特征是能够对文本进行充分表示的语言单位；文本在特征空间中的分布具有较为明显的统计规律；文本映射到特征空间的计算复杂度不太大。要表示好文本，就要寻找最有代表性的文本特征。对于计算机来说，文本就是由最基 本的语言符号组成的字符串。西文文本是由字母（ letter）和标点符号组成的字符串，中文文本就是由汉字和标点符号组成的字符串。在西文文本中，字母构成词（ word）。由于字母数量太少，无法作为特征，因此普遍使用词作为特征。
12、在中文文本中，字构成词，词构成短语，进而形成句、段、节、章、篇等语言文字结构。文本挖掘中常用的文本特征有字、词或短语等。在实际应用中，到底选择何种特征来表示文本需要结合处理速度、精度要求、存储空间等方面的具体要求来决定。 由于 Web 文本的特点， Web 信息提取算法的特征选择一般不采用自然语言处理 中的语法和语义特征，而使用下列特征 8： 符号特征： HTML 文档中的符号包括标记符号和文本中的符号。对于英文文本，文本的符号化很简单，可以用非数字字母符号将文本字符序列隔开成字符串，这些隔开的字符串称之为 token。对于标记符号 token,特征有标记名、属性等。对于文本符号 token,
13、特征有类型（数字、单词等）、值（文本实际内容）等。 除符号特征外，符号之间的关系也可能是信息提取的重要线索。关系特征考虑符号之间的关系。 文本片段特征：单纯从 token 层次来描述文本特征是不够的，要提取的信息一般是由很多个token 组成的文本片段，因此从文本片段层次上来描述特征是必要的。 文档结构特征：由于 HTML 文档中含有大量的标记信息，而标记之间是层层嵌套的。大多数的文本都处于标记之内，有些类型网页的标记出现有一定规律可循，另外有少数标记具有语义线索，如 ,标记中的内容一般对整个文档的语义起概括作用。可以利用的文档结构特征有符号所在的标记、父标记等。 特征表示是指以一定特征项 (
14、如词条或描述 )来代表文档，在文本挖掘时只需对这些特征项进行处理，从而实现对非结构化的文本的处理，这是一个非结构化向 结构化转化的处理步骤。特征表示的构造过程就是挖掘模型的构造过程，特征表示模型有多种，常用的有布尔逻辑型、概率型、向量空间型等 9。我们采用了应用较多的向量空间模型 (Vector Space Model ， VSM )。 向量空间模型 (Vector Space Model, VSM)是由 G. Salton 等人在 20 世纪 60 年代提出的信息检索模型，是效果较好、近些年来被广泛应用的一种方法 。 最典型的向量空间模型原型系统是康奈尔大学的 SMART(System fo
15、r the Manipulation and Retrieval of Text)系统，它提供源代码开放下载，目前已经被成千上万的研究者所采用。向量空间模型 (Vector Space Model)把文本表示成n 维欧式空间的向量，并用它们之间的夹角余弦作为相似性的度量。在向量空间模型中，首先要建立文本向量和用户查询的向量，然后对这些向量进行相似性计算 (匹配运算 )，在匹配结果基础上进行相关反馈，以优化用户的查询，提高检索效率 10。 虽然各个搜索引擎的具体实现不尽相同，但是一般包含爬虫程序、分析程序、索引程序、检索程序和用户接口界面 5 个基本部分，而且大致的工作 原理是相同的。 WEB
16、搜索引擎主要是通过爬虫程序定期遍历互联网，将网页的统一资源定位符（ URL）、内容和采集时间等相关信息收集到 WEB服务器中，然后通过必要的信息索引和存储优化处理，利用特定的检索界面对 WEB 用户直接提供服务 11。 它的具体工作流程包括以下几步： 第一步，爬虫程序采用一定的搜索策略对 WEB 网络进行遍历并下载网页，系统维护一个超链队列或者堆栈，其中包含一些起始 URL；爬虫程序从这些 URL 出发，下载相应的页面，并从中抽取出新的超链队列加入到队列或者堆栈中。 第二步，由分析程序对爬虫程序下载的网 页进行分析以用于索引，网页分析技术一般包括分词（有些仅从文档某些部分抽词，如 Altavi
17、sta）或者使用停用词表（ stop list）来过滤网页信息，同时还提供诸如单复数转换、词缀去除和同义词替换等词语转换，这些技术的具体实现往往与处理方式以及系统的索引模型密切相关。 第三步，索引程序将网页信息表示为一种便于检索的方式并存储在索引数据库中。 第四步，检索程序从索引中找出与用户查询请求相关的网页信息，采用与分析网页文档相似的方法来处理用户查询请求，最后将相关度大于阈值的所有网页按照相关度递减的顺序并返还给用户 ，当然搜索引擎的相关度判断并不一定与用户的需求完全吻合。 最后，用户接口为用户提供可视化的查询输入和结果输出界面。 向量空间模型具体步骤如下： 首先把文档分解成若干词语，去
18、掉出现频率较高但又没有实际意义的词语，比如 “ 虽然 ” 、 “ 但是 ” 等等，此时文档 D(Document)就可以由一系列实词建立的 n 维向量空间来表示 12。 然后利用余弦相似度定理，判断该文档与描述用户兴趣的文档之间的内容相关度，即两个文档向量之间的夹角余弦值即可得出这两篇文档之间的相似性 (夹角越小相似性越大 )。通常用户至少提供一个关键词形成用户 模板，以此表明用户的兴趣取向，权重大小由输入的先后顺序决定。在进行向量匹配时，用户模板在检索时可被看成是由 n 个词语组成的向量。首先得到同时包括这几个词的文献，然后一一比较，描述文件向量和文献向量的相似程度，最后根据相似程度把命中的
19、文献排序返回给用户 13。 向量空间模型可将文本和查询简化为项及权重集合的向量表示，从而把检索操作变成向量空间上的向量运算，其权重计算可以通过简单的频数统计来完成，通过定量分析，匹配文本和查询。在这个基础上，引入各种成熟的统计方法，更大程度地挖掘文本中蕴涵的语义信息，如主成分分析 、因子分析、聚类分析等等。具有较强的可计算性和可操作性的特点，特别是随着网络信息的迅速膨胀，其应用已经不仅仅局限于文本检索、自动文摘、关键词自动提取等传统问题，还可以应用到搜索引擎、个人信息代理、网上新闻发布等信息检索领域。在向量空间模型中，文档的内容被形式化为多维空间的一个点，把文档以向量的形式定义到实数域中，能够
20、使用模式识别和其它领域中各种成熟的计算方法，极大地提高自然语言文档的可计算性和可操作性，因而在文本过滤中获得广泛应用并取得良好效果。 向量空间模型的缺点在于项之间线性无关的假设，在自然语言中，词 或短语之间存在着十分密切的联系，即存在 “ 斜交 ” 现象，很难满足假设条件，对计算结果的可靠性造成一定的影响。此外，将复杂的语义关系，归结为简单的向量结构，将会丢失许多有价值的线索。 通过以上分析，可以看出 特征 文本 信息的搜索与 分类技术存在着以下几种发展趋势： 一是新 的搜索引擎 不断涌现：比如 智能化搜索引擎 。新 引擎 出现得益于人工智能、机器学习、进化计算等领域中新技术的涌现和发展。 二
21、是传统方法的进一步发展：比如支持向量机 14的不断改进发展。传统分类方法的发展主要利用了机器学习、进化计算、数据挖掘、模糊集和粗糙集 15等理论中的原理和方法。 三是多技术融合：一方面根据实际问题需要，有针对性地综合众多领域的技术，以提高分类的性能；另一方面，文本、语音和图像 搜索分类 技术的融合，随着互联网和多媒体技术的进一步发展，文本 搜索和 分类技术将与图像识别、语音识别融合，比如图像文本的分类、语音文本的分类、多媒体数据库索引等。 而本系统暂时停留在只对文本特征信息进行搜索和分类。通过建立一个搜索引擎，根据文本特征对文本信息实现搜索和分类。这就是预期达到的目标。 四、论文详细工作进度和
22、安排 第七学期第 10 周至第 15 周（ 2010 年 12 月 27 日前）：文献检索和资料收集，完成毕业论文（设计）文献综述、开题报告和外文翻译； 第八学期 第 1 周 至第 3 周（ 2011 年 03 月 19 日前）：撰写论文提纲，完成毕业论文（设计）初稿；需求分析，系统设计； 第八学期 第 4 周 至第 11 周（ 2011 年 04 月 11 日前）：详细设计； 第八学期第 12 周至第 13 周（ 2011 年 04 月 18 日前）：完成应用软件系统的设计，毕业论文定稿； 第八学期第 12 周（ 2011 年 04 月 24 日前）：完善毕业论文（设计）文档，完成答辩准备工
23、作； 第八学期第 13 周：开始参加毕业论文（设计）答辩。 五、主要参考文献 1 冯英健 .什么是第三代搜索引擎 EB/OL.http:/www. marketingman. net,2005-02-18. 2 马少平 ,张敏 .信息检索研究 :过去三十年中我们走了多远 C.中国中文信息学会二十五周年学术会议 .北京 :清华大学计算机科学与技术系 ,2006:11-17. 3 周旭 .知识经济 J.重庆市科学技术协会 ,2004,12(2):50-54. 4 Tom M.Mitchell.Machine LearningM. New York:McGraw-Hill,1997. 5 袁军鹏 ,
24、朱东华 ,李毅等 .文本挖掘技术研究进展 J.计算机应用研究 ,2006(2):1 4 6 程红莉 ,周宁 ,肖爽 .文本驱动的商务智能 研究 J.情报科学 ,2007(10):1525 1529 7 张忠平 .文本挖掘（ TextMining） R.河北 :燕京大学 计算机科学与工程系 ,2002.03.18. 8 李效东 ,顾毓清 .基于 DOM 的 Web 信息提取 J.计算机学报 ,2002,25(5):526-533. 9 KollerD,Sahami M.Hierarchically classifying documents using very few wordsJ.ICML9
25、7,1997:170-178. 10 Buckley C.Implementation of the SMART information retrieval systemR.New York:Cornell University, 1985. 11 李树青 ,韩忠愿 .个性化搜索引擎原理与技术 M.北京 :科学出版社 ,2008. 12 夏迎炬 .文本过滤关 键技术研究 D.上海 :复旦大学 ,2003. 13 林冬雪 .基于改进向量空间模型的网络信息检索技术研究 D.四川 :重庆大学 ,2005. 14 Fung G,Mangasarian O L.Incremental support vector machine classificationC.Proceedings of the Second SIAM International Conference on DataMining.SIAM(2002).2002:247-260. 15 付 雪峰 ,王明文 .基于模糊 粗糙集的文本分类方法 J.2004 年度全国搜索引擎和网上信息挖掘学术研讨会 .华南理工大学学报 (自然科学版 ),2004,32:73-76.
