文本挖掘_文本挖掘pdf下载_爱问共享资料
文本挖掘.pdf
文本挖掘.pdf
文本挖掘.pdf
简介：本文档为《文本挖掘pdf》，可适用于人文社科领域，主题内容包含文本上的算法v路彦雄yanxionglugmailcom一、理论篇第一章、你必须知道的一些基本知识概率论信息论贝叶斯法则第二章、我们生活在一个寻求最符等。
侵权或盗版
*若权利人发现爱问平台上用户上传内容侵犯了其作品的信息网络传播权等合法权益时，请按照平台要求书面通知爱问！
赌博犯罪类
添加成功至
资料评价：
所需积分：5当前位置： >>
Web文本挖掘中的文本分类研究
湖南大学 硕士学位论文 Web文本挖掘中的文本分类研究 姓名：唐剑波 申请学位级别：硕士 专业：计算机应用技术 指导教师：周炎涛
硕士学位论文摘要随着 Internet 网络的高速发展，信息爆炸时代也随之到来。由于 Internet 的开放 性、动态性、异构性使得用户很难快速、准确的从 WWW上获取所需的信息，因 此如何有效的从网络上获取有价值的信息成为当前研究的热点。 Web 文本挖掘技 术就是解决上述问题的一种方法，它借鉴数据挖掘的基本思想和理论方法，从大 量半结构化、异构的 Web 文档的集合中发现潜在的、有价值的知识。 文本分类技术是 Web 文本挖掘中一项最重要的技术，随着中文网页数量的急 剧增加，中文文本分类也逐渐成为了 Web 挖掘研究的热点，它的关键技术包括文 本分词、文本表示、文本预处理、特征选择以及分类算法，其中特征选择的好坏 对文本分类的训练时间、分类的准确率都有显著的影响； TFIDF 特征选择是文本 分类中使用较普遍而且比较有效的方法，但存在不足，如没有考虑词条文档在分 类系统中的分布。本文对传统的 TFIDF 特征选择算法进行了简单介绍和分析，并 对 TFIDF 方法利用词条信息熵进行改进， 提出了一种新的基于 TFIDF 的特征选择算 法。而且通过实验对传统的 TFIDF 方法和本文改进后的方法进行了比较，证明本 文提出的方法有更好的查全率和查准率。 Web 文本分类的方法较多，常用的如：最近邻分类、贝叶斯分类、决策树、 支持向量机、向量空间模型、回归模型和神经网络等。但传统的分类方法存在着 不足，当前 Web 文本分类的方法大都将网页归属到某一特定类中，而许多网页包 含多个主题，应该有多个归属类。本文还提出了一种基于向量空间模型的多主题 Web 分类方法，该方法通过网页与每个类的相似度来计算动态阀值，并对相似度 进行聚类，实现了将多主题网页划分到多个类中的目的。最后，也通过实验证明 了该方法的有效性。 关键字：文本分类；信息熵；多主题文本分类； TFIDF ；特征选择IWeb 文本挖掘中的文本分类研究AbstractWith the rapid development of Internet Technology, the information exploring era is coming. Quickly and accurately obtaining what users need on WWW is getting more and more difficult because of Internet’s opening and dynamic and heterogeneity, how to obtain valuable information becomes a research hotspot now. Web text mining technology is a method to solve the above question. It can find latent and valuable knowledge from a great deal of semi-structured heterogeneous data by the methods of data mining. Text classification is an important technology of text mining based on web, with the rapidly increasing of Chinese web, Chinese text classification gradually become the Hotpoint of web mining, the essential technologies of text mining include participle technology ,text expression ,preprocess ,weight computation, feature selection and classification arithmetic. The quality of text feature selection affects the accuracy and efficiency of text categorization greatly. TFIDF is a main method of feature selection in text classification, and because of traditional TFIDF without considering the distribution of feature the paper analyzed the TFIDF feature selection algorithm, and proposed a new TFIDF feature selection method with concept of information entropy. Experimental results show the method is valid in improving the accuracy of text categorization, the precision and recall is quite satisfying. Many technologies have been applied in text categorization, such as the Nearest Neighbore, Bayesian, decision trees, support vector machines, vector space model and neural networks etc. But these common methods have some shortages. Current many text classification methods only focus on the web pages including one topic, while many web pages including several topics should belong to different classification. This paper proposes a multi-topic web classification method based on vector space model, through comparing the value of every classification similarity with dynamic threshold value, we have accomplished the task that classifying a multi-topicc web page to several different classes, and the experiment results show the method is valid. Key Words ： Text C Information E Multi-topic Text CII硕士学位论文TFIDF; Feature SelectionIIIWeb 文本挖掘中的文本分类研究插图索引图 1.1 论文结构图 ................................................................................................... 3 图 2.1 W EB 挖掘分类结构图 ..................................................................................... 6 图 2.2 文本挖掘过程 ............................................................................................... 10 图 3.1 特征选择的过程 ........................................................................................... 14 图 3.2 三层前馈 BP 网络图 ................................................................................... 18 图 5.1 分类过程示意图 ........................................................................................... 33 图 5.2 基于向量空间的多主题分类过程 ................................................................ 34 图 5.3 动态阀值与传统向量空间模型的召回率比较 ............................................. 38 图 5.4 动态阀值与传统向量空间模型的精确度的比较 .......................................... 39IV硕士学位论文附表索引表 4.1 单词频度分布表 ........................................................................................... 25 表 4.2 传统 TFIDF 特征选择 .................................................................................. 29 表 4.3 基于信息熵的 TFIDF 特征选择 ................................................................... 30 表 5.1 多主题分类实验结果 ................................................................................... 38VWeb 文本挖掘中的文本分类研究湖 南 大 学 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密□，在 ______ 年解密后适用本授权书。 2 、不保密□。 √ （请在以上相应方框内打“√” ）作者签名： 导师签名：日期： 日期：年 年月 月日 日硕士学位论文第 1 章 绪论1.1 课题背景与意义在这个信息技术高速发展的时代中，信息和知识的获取、处理和应用已经成 为经济、科学、军事、文化等各个领域发展的关键活动，另外，随着数据库技术 的不断发展，数据库中存储的数据量急剧增加，在这些数据中潜藏了大量有价值 的信息，如果能将这些有用的信息加以利用，将为公司乃至整个社会创造巨大的 价值。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程。而 这些用于获取信息和形成知识的源泉，即原始数据可以是结构化的，如关系数据 库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网 络上的异构型数据。发现信息和知识的方法可以是数学的，也可以是非数学的； 可以是演绎的，也可以是归纳的。发现的信息可以被用于信息管理、查询优化、 决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很 广泛的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理 统计、可视化、并行计算等方面的学者和工程技术人员[1]。随着网络技术的高速发展，Internet 上网络信息资源呈指数级增长，据估计网 页数量每 4 到 6 个月翻一翻，使得 Web 上的信息量以惊人的速度增长， Internet 包含了大量的信息资源，在这些大量的、异质的信息资源中，隐藏着具有巨大潜 在价值的知识，所以它已经成为了世界性的图书馆，变成了各行各业人们交流思 想、获取信息的平台。但是面对 Web 如此丰富的内容，巨大的数据量，加上万维 网动态开放的特点，人们要去快速准确的寻找自己需要的东西不是一件容易的事 情，通常需要耗费大量的人力和物力，因此迫切需要一种能快速、有效地从 Web 上发现资源和知识的工具，这样就给数据挖掘带来了新的发展平台， Web 技术与 数据挖掘技术的结合，出现 Web 挖掘。但由于传统的数据挖掘工具主要是针对结 构化的数据库，很少涉及处理 Web 上异质的、非结构化的信息，因此，Web 挖掘 不是简单的将数据挖掘技术搬到 web 中，而是一个引起人们高度重视的新课题。 当前研究 Web 挖掘一般分为三大类： （ 1 ）Web 内容挖掘。它是指从网页内容 出发，从中获取潜在的，有价值的知识，以实现 Web 资源的高效率自动检索，提 高资源的利用率。通常可以分为 Web 文本挖掘和 Web 多媒体挖掘[2],Web 文本挖掘是指对文档的内容进行总结、分类，聚类，关联分析等 ,Web 多媒体挖掘是指从1Web 文本挖掘中的文本分类研究Web 多媒体数据如 Web 音频、视频、图像中抽取潜在信息的过程； （ 2 ）Web 结构 挖掘 。它是指从 WWW 组织结构及其链接关系中获取数据的过程； （ 3 ） Web 使 用挖掘。它通过从 Web 的访问信息的挖掘获取信息，分析用户和 Web 网页之间 交互结果，包括 Web 日志、点击次数、以及一组相关网页间的数据交换等。 由于网络上的信息大多以文本的形式表达，文本提供给用户大量丰富的信 息，在这些信息中包含了潜在的、有巨大价值的知识，而面对如此庞大的文本资 源，传统的文本分析处理工具已经无法满足现实需要的要求，因此， Web 文本挖 掘成为了数据挖掘中一个日益流行而重要的研究课题，是 Web 挖掘研究的重心。 Web 文本挖掘最关键的技术是文本分类， 文本分类是指在给定的分类体系下， 根据文本的内容自动确定文本类别的过程， 是一种典型的有教师机器学习的方法。 随着网络技术的高速发展，网页的数量成几何速度增长，如何有效的处理和高效 的搜索这些信息是一个越来越重要的课题， 这就给文本分类提供了新的发展平台。 因此文本分类的研究变得越来越有意义和实用价值。1.2 研究内容本文的主要研究内容是 Web 网页的多主题分类技术。 当前文本分类的方法大 多都是针对单主题的，简单的将待测文本划分到某一个类中，而许多网页都包含 了多个主题，针对这种情况，在对向量空间模型的分类方法进行深入研究的基础 上，结合常用的 K-means 聚类数据挖掘方法，提出了基于向量空间模型的多主题 分类算法。 本文的另一个研究内容是特征选择算法。文本特征选择的质量对文本分类的 精确性有着非常重要的影响。 本文针对传统的 TFIDF 没有考虑特征词条在各个类 之间的分布的不足，对 TFIDF 特征选择算法进行了深入的分析，并结合信息熵的 概念提出了一种新的 TFIDF 特征选择算法。1.3 本文主要工作本文的主要工作包括以下几个方面： 介绍了 Web 挖掘的研究现状；主要包括 Web 文本挖掘的研究现状和文本分类 的研究现状。 分析了 Web 文本分类的主要步骤，比较了当前主要的 Web 文本分类的主要使 用方法，阐述了数据挖掘的 K-means 聚类方法 . 并针对当前分类方法对多主题 分类研究较少的情况，结合聚类思想，提出了基于向量空间的多主体分类算 法。2硕士学位论文介绍了几种常用的文本特征选择算法，阐述了信息熵的概念，并深入研究了 TFIDF 算法，针对 TFIDF 算法没考虑特征词条在类之间分布的不足，提出了 基于信息熵的改进算法。1.4 论文结构本文的结构如图 1.1 所示：绪论Web文本挖掘Web文本分类基于信息熵的 TFIDF 特征选择改进算法基于向量空间模型的 Web多主题文本分类图 1.1 论文结构图3Web 文本挖掘中的文本分类研究第 2 章 Web 文本挖掘相关研究2.1 Web 挖掘Web 挖掘是使用数据挖掘技术自动地从 Web 文档和 Web 活动中发现和提取潜 在有用的信息和知识的技术[3]，它以从 Web 上挖掘有用知识为目标，以数据挖掘、文本挖掘、多媒体挖掘为基础，并综合运用计算机网络、数据库与数据仓储、人 工智能、信息检索、可视化、自然语言理解等技术，将传统的数据挖掘技术与 Web 结合起来。一般的将 Web 挖掘定义为[4]:定义 1: Web 数据挖掘是指从大量 Web 文档的集合 C 中发现隐含的模式 p 。如果 将 C 看作输入，将 p 看作输出，那么 Web 挖掘的过程就是从输入到输出的一个映射ξ :C → p。近年来，随着 Internet/Web 技术的快速普及和迅猛发展，电子商务正以令人难 以置信的速度发展，因特网目前已成为一个巨大的、分布广泛的和全球性的信息 服务中心和交易平台，各种信息可以以非常低的成本在网络上获得，可以从中取 得的数据量难以计算，而且 Internet/WWW 的发展趋势继续看好，另外 Web 的巨大、 分布广泛和内容多样使得目前的 Web 挖掘面临着众多问题和挑战，如何在 WWW 这个全球最大的数据集合中发现有用信息无疑将成为数据挖掘研究的热点。2.1.1 Web 挖掘的特点Web 挖掘的特点主要包括以下几点异构数据环境 从数据库研究的角度出发， Web 网站上的信息也可以看作一个数据库，一个 更大，更复杂的数据库。 Web 上的每一个站点就是一个数据源，每个数据源都是 异构的，因而每一个站点之间的信息和信息的组织都不一样，这就构成了一个巨 大的异构数据环境。如果想要利用这些数据进行挖掘，首先，必须要研究站点之 间异构数据的继承问题，只有将这些站点的数据都集成起来，提供给用户一个统 一的视图，才有可能从巨大的数据资源中获取所需要的信息。其次，还要解决 Web 上的数据查询问题，因为如果不能很有效地得到所需的数据，对这些数据进行分 析、集成、处理就无从谈起。 数据量巨大、内容丰富，分布广泛[5~7]：Internet 把分布于世界不同位置的电脑连接了起来 , 每个电脑上都存有丰富的4硕士学位论文数据 , 这些数据涉及各种不同的行业和领域 , 又由于连接于 Internet 的电脑数量非 常巨大 , 所以 Web 站点中的数据量也非常巨大。既有涉及经济、文化、教育、新闻、 娱乐、电子商务等丰富的信息服务 , 又蕴涵着访问页面特性、访问路径特性、访 问时间特性这些潜在的访问信息，内容相当丰富。 半结构化数据结构 半结构化数据有两层含义，一种是指在物理层上缺少结构的数据，另一种是 指在逻辑层上缺少结构的数据。有一些结构化数据，如元组，为用于 Web 页面的 显示而与 HTML 语言的标记呼号嵌在一起，构成了物理上的半结构化数据。 Web 中有大量丰富的数据：文本、图片、声音、图像等，这些数据多存在于 HTML 文 件中，没有严格的结构及类型定义，这些都是逻辑层半结构化的数据。 Web 上的 数据与传统数据库中数据不同，传统的数据库都有一定的数据模型，可以根据模 型来具体描述特定的数据。而 Web 上的数据非常的复杂，没有特定的模型描述， 每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性。因 而 ,Web 上的数据具有一定的结构性，从而是一种非完全结构化的数据，这也被称 之为半结构化数据。半结构化是 Web 上数据的最大特点。 解决半结构化数据源问题Web 数据挖掘技术首先要解决半结构化数据源模型和半结构化数据模型的查询与集成问题。解决 Web 上的异构数据的集成与查询问题，就必须要有一个模型 来清晰地描述 Web 上的数据。针对 Web 上的数据半结构化的特点，寻找一个半结 构化的数据模型是解决问题的关键所在。除了要定义一个半结构化数据模型外， 还需要一种半结构化模型抽取技术，即自动地从现有数据中抽取半结构化数据模 型的技术。面向 Web 的数据挖掘必须以半结构化模型和半结构化数据模型抽取技 术为前提。 数据的动态性Web 是一个不断变化的、动态更新的系统， Web 上的数据信息也是不断更新的。因此，其数据源具有很强的动态性，需要利用数据库及数据仓库等技术保存 不断变化的 Web 数据。2.1.2 Web 挖掘过程传统的数据挖掘都是针对数据库、数据仓库等结构化的数据进行分析、加工 和模式挖掘，而 Web 网页呈现的是半结构化甚至是非结构化的数据，这些数据没 有统一的结构和形式，是一个异质的、动态的、分布的数据源。所以不能直接对Web 网页数据进行数据挖掘，必须经过必要的数据处理。典型的 Web 挖掘过程如下[8]：5Web 文本挖掘中的文本分类研究1) 资源查找。从网络上查找需要的网页，包括 Web 文档、电子邮件、新闻组、网站的日志数据、或者是通过 Web 形成的交易数据库中的数据。2) 信息选择和预处理。从取得的 Web 资源中剔除无用信息和将信息进行必要的整理。例如从 Web 文档中自动去除广告连接、去除多余格式标记、 自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。3) 模式发现。选择合适的挖掘工具，进行挖掘工作。 4) 模式分析。验证上一步产生的模式的正确性。2.2 Web 挖掘的分类Web 挖掘大致可以分为三大类： Web 内容挖掘、 Web 使用挖掘和 Web 结构挖掘， 图 2.1 给出了 Web 挖掘的分类图。Web挖掘Web内容挖掘Web 使用挖掘Web结构挖掘文本挖掘多媒体挖掘内部结构挖掘超链挖掘URL挖掘用户访问模式追踪分析定制 Web 站点图 2.1 Web 挖掘分类结构图2.2.1 Web 内容挖掘Web 内容挖掘是一种基于网页内容的挖掘，是从大量的 Web 页面描述数据中发现信息，进而抽取知识的过程，是一项涉及互联网技术、计算机语言、信息检 索、统计学、人工智能等诸多领域的综合技术。 Web 内容挖掘所处理的数据对象 既有文本和超文本数据，也有图形、图像、语音等多媒体数据；既有来自于数据 库的结构化数据，也有半结构化数据和无结构的自由文本。 目前主要的 Web 内容挖掘技术有：①文本分类：将自由文本文献自动归入一 个或多个事先定义好的类目中；② 文本聚类：文本聚类没有事先定义好类，完全 依据文献间的相似度，把文献分入到一个或多个类中；③ 自动摘要：自动摘要有Extraction( 提取 ) 和 Abstraction( 抽取 ) 两种方法， 前者是通过从原始文本提取句子的6硕士学位论文方法来生成摘要，后者生成的摘要中则可以包含原文中没有的句子；④文本可视 化：用二维或三维的图形显示文献集的语义模式，使用户可以迅速地发掘出大型 文献集中的语义关系[9]。Web 内容挖掘主要应用于信息过滤、知识抽取、网络文档分类、网络本体论的发现以及网络数据的综合和存储等方面。2.2.2 Web 结构挖掘Web 页面与一般文档页面的区别就是页面中不但有内容信息，还有与其它页面的链接等结构信息， Web 结构挖掘就是通过分析不同网页之间的超链接结构、 网 页 内 部 的 可 以 用 HTML 和 XML 表 示 成 的 树 形 结 构 , 以 及 文 档 URL 中 的 目 录 路 径结构等 , 发现许多蕴涵在 Web 内容之外的对我们有价值的模式和知识的过程，即 从 Web 组织结构和链接关系中推导信息和知识。 World Wide Web 由大量的 Web 站点 构成，而每个 Web 站点又包含许多的 Web 页，Web 页中包含了网页及文档之间的超 链接，这些 Web 页之间的超链接结构中又包含了许多有价值的信息。一个页面被 引用的次数体现了该页面的重要性，指向某一网页的链接越多意味着这个网页的 普及性越强，同时如果一个页面被重要网页引用也说明了这个网页的重要性。另 外， 从某一网页指出的链接越多则暗示着此网页的内容或是题目越丰富。例如： 当网页 A 到网页 B 存在一个超链接时，则说明网页 A 的作者认为网页 B 的内容非常 重要。因此，指向一个文档的超链接体现了该文档的被引用情况，如果大量的链 接都指向了同一个网页，我们就认为它是一个权威页。 目前，有很多团体和科研机构对 Web 上超文本系统的链接结构进行研究，并 提 出 了 许 多 有 关 Web 结 构 挖 掘 的 算 法 ， 其 主 要 算 法 有 两 个 ： PageRank 算 法[10]及HITS 算法[11]。PageRank 算法 该算法由 Brin 和 Page 提出 ，是最早利用超链接信息进行 Web 挖掘的算法，该 算法主要用来发现权威页面，被 GOOGLE 搜索引擎采用。其基本思想如下：设页 面 i 的链入集合为 (T1 , T2 , &, Tn ) ，即 (T1 , T2 , &, Tn ) 中的每一个页面都链接到页面 i ，c(i) 为页面 i 的链出页面数，则页面 i 的等级值 PR(i) 可以通过以下计算得出：用概率 e 随 机取 Web 上任一页面，用概率 1-e 随机取当前页面任一链出页面。则计算页面等级 值的公式如下：PR(i ) = 1 ? e + e * ( PR(T1 ) / C (T1 ) + & + PR(Tn ) / C (Tn ))果页面中，根据网页的等级值排序，等级值越高的网页排序的位置越靠前。 HITS 算法(2.1)那么，PR(i) 值越大则该页面权威性越高。在 GOOGLE 搜索引擎中，在搜索的结7Web 文本挖掘中的文本分类研究HITS 算法是 Kleinberg 提出的一种更为精确的关于页面权威性的算法，他认为页面的重要性应该建立在用户查询条件的基础上，每一页面都分别有 Authority 值 和 Hub 值 。 通 常 ， 好 的 Hub 是 指 向 许 多 好 的 权 威 页 面 ， 好 的 权 威 是 指 由 许 多 好 的Hub 所指向的页面[12]。这种 Hub 和 Authority' 之间的相互作用可用于权威页面的挖掘和高质量 Web 结构和资源的自动发现，这就是 HITS 方法的基本思想。HITS 算法 的内容如下：将查询 q 提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页 面，从中取前 n 个页面作为根集 (Root set) ，用 s 表示。通过向 s 中加入被 s 引用的页 面和引用 s 的页面将 s 扩展成一个更大的集合 t ，作为基本集 (Base set) 。首先，为基 本集中的每一个页面赋予一个非负的权威权重 a p 和非负的 Hub 权重 h p ，并将所有 的 a 和 h 值初始为同一个常数。 Hub 与权威的权重可按如下公式进行迭代计算：ap =q:q → p∑hq，hp =q:q ← p∑aq(2.2)经过大约多次迭代计算，a 和 P 值将趋于稳定，迭代终止。最后 HITS 算法输出 一组具有较大 Hub 权重的页面和具有较大 Authority 权重的页面[13]。2.2.3 Web 使用挖掘网络使用挖掘是通过挖掘 Web 日志记录以发现用户访问 Web 页面的模式、挖 掘有用模式和预测用户浏览行为的技术[14 ，15]。 Robert Cooly 将 Web 使用挖掘定义[16 ， 17]为数据挖掘技术应用在大型 Web 资源中以分析 Web 站点的使用 惯和模式等。主要应用于以下几个方面：。Web 使用挖掘的结果通常是用户群体的共同行为和共性兴趣 , 以及个人用户的检索偏好、习1) 站点的改进根据实际用户的浏览情况，调整网站的网页的连接结构和内容，更好的服务 用户；2) 个性化服务根据发现的用户喜好，动态地为用户定制观看的内容或提供浏览建议；3) 页面推荐收集和统计活动用户对站点的近期访问信息 , 分析其浏览路径 , 并与挖掘的 模式进行比较匹配 , 并根据匹配程度进行排序 , 为活动用户预测下一步最有可能 访问的页面 , 并将排序结果附加在现行用户请求页面之后， 从而进行页面推荐[18]；4) 商业智能目前许多公司都有自己网站产生出来的大量用户消费信息，通过分析处理这 些消费信息和统计数据，确定特定消费群体或个体的兴趣、消费习惯和消费需求， 进而推断出他们下一步的消费行为，识别潜在的客户 , 确定电子商务的潜在客户8硕士学位论文群 , 以此可以指导商务决策，使企业处于竞争的优势地位。Web 使用挖掘的过程一般分为四个部分： （ 1 ）数据收集，即从网络上找到适合特定应用的网页； （ 2 ）预处理，即删除 Web 日志记录中与数据挖掘不相关的数 据 , 把 Web 日志转化为适合数据挖掘的可靠的精 确数据，包括删除传输协议、传 输的字节数、错误码等；并进行用户识别和事物识别； （ 3 ）模式识别，即对经过 处理后的数据利用合适的数据挖掘方法进行挖掘，以发现有用模式，比如路径分 析、关联规则挖掘、序列模式挖掘、聚类和分类技术等； （ 4 ）模式分析，即对挖 掘出来的模式，采用合适的工具和技术对其进行分析、解释和可视化，从中筛选 出有用的模式，使之成为人们可以理解的知识[16]。2.3 Web 文本挖掘2.3.1 Web 文本挖掘定义Web 文本挖掘是指针对包括 Web 页面内容、页面之间的结构、用户访问信息、电子商务信息等在内的各种 Web 数据，应用数据挖掘方法以发现有用的知 识来帮助人们从大量 Web 文档集合中发现隐含的模式，也即从 Web 信息资源中 提取潜在的、有价值的知识。它的主要功能如同其它数据挖掘包含了两个高层次 目标：预测和描述。所谓预测是指用一些变量或数据库的若干已知字段预测其它 感兴趣的变量或字段的位置或未来的值； 而描述指找到描述 Web 数据的可理解模 式[19]。2.3.2 Web 文本挖掘主要内容Web 文本挖掘主要包括文本总结、文本分类、文本聚类、关联分析以及利用 Web 文档进行趋势预测。文本摘要 文本总结是一篇文章的简单概括，是从文章中抽取的关键信息，以简洁的形 式，对文本内容进行摘要和描述。用户不需要阅读全文就可以从文本总结中了解 到文章的大致内容。例如一些搜索引擎返回给用户的查询结果都是文本的摘要。 目前许多搜索引擎都是选择文本的前几句作为文本的摘要，也有些使用中心词来 表示文本。 文本分类 文本分类是指根据预先确定的主题类别，为文本集合中的每一个文本都确定 一个类别的过程。分类是一个典型的机器学习问题，分类的目的是让机器学会一9Web 文本挖掘中的文本分类研究个分类规则，该规则能够将 Web 文本映射到一个或者多个已经存在的主题类中， 这样不但方便浏览文件，而且使用户能快速、准确的查找自己需要的文本。文本 分类一般分为训练和分类两个阶段。 文本聚类 文本聚类与文本分类一样，都是将文本归类，但其实现的方法不一样，文本 分类是文本归类到预先已经存在的类中，而文本聚类则是在没有预先定义好主题 类别的情况下，根据文本的内容，将文本集中的所有文本分成若干类，要求类中 的文本之间的相似度尽可能小，而不同类中文本之间的相似度尽可能大。 关联分析 关联分析是指从文档集合中找出不同词语之间的关系， Brin 提出了一种从大 量文档中发现一对词语出现模式的算法 , 并用来在 Web 上寻找作者和书名的出现 模式 , 从而发现了数千本在 Amazon 网站上找不到的新书籍 。 Wang 等人以 Web 上的电影介绍作为测试文档 , 通过使 OEM 模型从这些半结构化的页面中抽取词 语项 , 进而得到一些关于电影名称、导演、演员、编剧的出现模式 趋势预测 趋势预测是指通过对 Web 页面的分析，得到数据在未来的变化趋势，例如， 通过分析关于经济方面的权威 Web 网页，可以对股票市场进行预测，指导股民的 进行投资。[20]。2.3.3 文本挖掘的过程文本挖掘过程由文本收集、文本预处理、特征提取、文本挖掘、模式生成等 步骤组成，如图 2.2 中所示。Web文本收集文本预处理特征提取文本分类 模式生成 文本聚类 文本挖掘 挖掘结果显示图 2.2 文本挖掘过程a) 首先，利用网页搜索软件自动通过 Web 进行文本的搜索，收集一定数量的网页，然后，为了提高 Web 挖掘的效率和精确性，必须进行文本预处理，去掉10硕士学位论文跟文本挖掘无关的标记，例如 GIF 和 JPEG 等类型的图象文件、声音文件、脚 本程序等，中文文本的预处理较英文文本的预处理更为复杂，因为中文各词 之间没有固定的分隔符。b) 对经过预处理的文本进行分词处理，把文本切分成词条或者单个字。 c) 由于 Web 文本使用的是人类的自然语言，计算机是无法理解的，所以必须将 Web 文本表示成计算机能够理解的形式，目前用于文本特征表示的方法很多，矢量空间模型（ VSM ）是最近几年用的较多且效果较好的方法之一。d) 文本的数据量信息非常的大，所以特征向量的维数特别高，为了提高运行效率，必须进行特征提取，对特征向量进行降维处理，将一些通用的、各个类 别都普遍存在的对分类贡献小的词条去除。通过适当的特征选择算法计算出 每个特征词的权值，仅保留权值较高的词条作为文本的特征项。e) 在完成特征向量降维后，便可利用数据挖掘算法（关联规则、分类、聚类等）获取面向特定应用目的的知识模式。f)在获得知识模式后，并对挖掘的模式进行分析评价，通过可视化、图形图像 处理等技术显示符合一定标准的挖掘结果，便于用户理解和应用。2.4 小结本章首先简单介绍了 Web 挖掘的概念、 Web 挖掘的主要过程及 Web 挖掘的 分类，Web 挖掘主要分为 Web 内容挖掘、Web 结构挖掘和 Web 使用挖掘三大类， 其中 Web 内容挖掘又主要包括 Web 文本挖掘和 Web 多媒体挖掘。接着主要介绍 了 Web 文本挖掘的定义、文本挖掘的意义、文本挖掘的主要内容以及文本挖掘的 主要过程。11Web 文本挖掘中的文本分类研究第 3 章 Web 文本分类相关研究3.1 文本分类简介文本分类是指在给定分类体系下，根据文本内容或属性自动确定文本类别的 过程。经过文本分类处理，便于用户浏览文本，并通过限制搜索范围加快文本的 查找速度。随着中文网页的急速发展，中文文本分类也逐渐成为为了数据挖掘研 究的热点。 20 世纪 90 年代以前，占主导地位的文本分类方法一直是基于知识工程 的分类方法，即由专业人员手工进行分类。人工分类周期长、费用高、效率过低。 网页数量的飞速增加使得手工分类方式已经不能适应时代的要求， 90 年代以后， 众多的统计方法和机器学习方法应用于自动文本分类，越来越多的研究人员投入 中文文本分类的相关研究。3.2 Web 文本分类的关键技术文本分词 计算机没有类似人类的智能，人类阅读文章后可以产生自身对文章的理解， 而计算机却没有这样的能力。为了便于计算机的处理 , 文本必须表示为计算机可以 识别的格式，目前文本分类的研究主要采用向量空间模型。在向量空间模型中， 文本被表示为一个高维向量，向量的每一维代表一个特征 , 通常是一个字或词， 而其取值则是相应的权值。与英文网页不同的是，中文网页使用汉字，词与词之 间没有间隔，不像英语单词之间存在空格符，所以需要对中文文本进行切词处理， 并且切词的准确与否将很大程度的影响分类的效果。那么首先我们要在文本中区 分出每一个词或者是字，这样，分词是一个必要的步骤。 归纳起来，目前国内公开报道过的汉语自动分词系统采用的分词方法和算法 主要有三种类型[21]：1) 机械分词法机械分词法主要有最大匹配法 (MM 法 ) 、逆向最大匹配法 (RMM 、 OMM 、IMM) 、逐词匹配法、部件词典法、词频统计法、设立标志法、并行分词法、词库划分和联想匹配法等。2) 语义分词法语义分词法引入了语义分析 , 对自然语言自身的语言信息进行更多的处理 , 如12硕士学位论文扩充转移网络法、知识分词语义分析法、邻接约束法、综合匹配法、后缀分词法、 特征词库法、约束矩阵法、语法分析法等。3) 人工智能法又称理解分词法，人工智能是对信息进行智能化处理的一种模式，主要有两 种处理方式：一种是基于心理学的符号处理方法。模拟人脑的功能，像专家系统。 即是希望模拟人脑的功能，构造推理网络，经过符号转换，从而可以进行解释性 处理。一种是基于生理学的模拟方法。神经网络旨在模拟人脑的神经系统机构的 运作机制来实现一定的功能。以上两种思路也是近年来人工智能领域研究的热点 问题，应用到分词方法上，产生了专家系统分词法和神经网络分词法。 文本的表示 计算机没有类似人类的智能，文本一般采用人类的自然语言，计算机无法识 别，必须把文本转化为机器理解的格式 。而词、词组、短语又是组成文本的基本 元素，在不同主题的文本中，各词组和短语出现的频率规律性是不一样的，不同 的特征词条可以用来区分不同主题的文本，因此我们可以提取一些特征词条来表 示文本的主要内容，常用的文本表示方法有：矢量空间模型、布尔模型、概率型、 混合模型等。以下简单介绍了布尔模型和矢量空间模型。 布尔模型：它定义了一个二值映射函数 f ： T → {0 ， 1} ，元数据 t i 的值不再是 权值，而是一个布尔值。文本表示的结果是 0-1 向量，即：d = (val (t1 ), val (t 2 ),&, val (t m ))? val (t i ) = 0 t i 在 d 中没有出现 其中 ? t i 在 d 中出现 ?val (t i ) == 1矢量空间模型：在 VSM 模型中，文本空间被看作由一组词条向量组成的向 量空间，即将 Web 文本看成是有一组词条 (t1 , t 2 ,&, t n ) 构成，对其中的每一个词条t i 都根据该词条在文本中的重要程度赋予一定的权值 Wi ， w1 , w2 ,& , wn 可以看成 N维坐标系中的一个坐标值， 因此每一篇 Web 文本都可以映射为由一组特征词条及 其权值矢量构成的向量空间中的一点 文本的预处理[22]。Web 文本作为一种非结构化的数据类型 , 其特点表现为特征空间的高维性、文本特征表示向量的稀疏性及文本主题特征表现不突出等特点。通过分词切分出来 的所有词条中含有大量无用信息，所以必须对文本进行预处理，将这些无用信息 过滤掉： （ 1 ）经过研究发现分词得到的单个独立字不仅所携带的文本信息量较少，而 且还对其他实词起到一定的抑制作用，降低了分类系统的处理效率和准确度，因 此，文本预处理过程有必要将所有的单个独立字过滤[23 ， 24]。（ 2 ）由于 WWW 上的信息主要是以 HTML 页面的形式出现的，用 HTML 语言13Web 文本挖掘中的文本分类研究写成的源文本由标记 ( 用“ 〈〉 ”括起来的代表特定含义的标示 ) 和文本组成 ，这些标 记没有实际意义，无法表达文本的主题，应该将其删除。 （ 3 ）引入停用词表和高频词表剔除对分类没多大影响的词语。其中停用词指 的是那些语法词以及一些虚词、感叹词、连词等；另外有些高频词汇在所有的文 本中出现的频率都基本相同 , 区分性差 , 也不能作为文本类别的特征。 特征选择 对文本经过分词、预处理之后我们获得了表示整个文本的特征向量，但构成 文本的词的数量非常之大，导致了表示文本的向量空间的维数也相当多，因此我 们需要对文本进行特征选择，去除不能表示文本内容的词，降低特征向量的维数， 以提高分类效率、减少计算复杂度以及提高分类精度。特征选择就是从特征集T = {t1 , t 2 , &t s } 中选择一个真子集 ： T ' = {t1 , t 2 , & t s ' } ，满足 s ' & s 。其中， s 为原始特征集的大小， s ' 为选择后的特征集大小。文本特征选择的一般处理过程如图所 示：文本集 分词处理器 文本预处理缩减后特征集特征选择算法特征集的建立图 3.1 特征选择的过程特征选择的准则是经特征选择后能有效提高文本准确率， 加快程序运行速度。 一个好的特征集必须满足以下三个条件[25]：完全性：特征项集能够完全表达文本的主要内容。 区分性：根据特征项集能够将待分文本同其他文本区分开来。 精练性：特征矢量的维数应该尽可能地小。 常用的文本特征选择方法有：文档频率 (DF) 、信息增益 ( IG) 、互信息 (MI) 、x 2 统计量 (CHI) , 期望交叉熵 , 文本证据权 , 优势率等。这些方法的基本思想都是对每一个特征 ( 在这里是中文词 ) , 计算某种统计度量值 , 然后设定一个阈值 T , 把度量 值小于 T 的那些特征过滤掉 , 剩下的即认为是有效特征。 本文第四章对主要的特征 选择算法进行了简单介绍。3.3 文本分类的几种主要方法3.3.1 经典文本分类方法简单向量距离文本分类14硕士学位论文简单向量距离文本分类是基于向量空间模型的一种分类算法，向量空间模型 以统计学习理论和结构最小原理为基础， 将文档转化为一组线性无关的特征向量， 特征向量由特征项和特征项权值组成，如文档 D 可以定义为：D = (T1 ,W1 ; T2 , W2 ;&; Tn ,Wn )（ 3.1 ）其中 Tk 是特征项，Wk 是特征项权重。特征项是组成文本内容的基本语言的集 合，如字、词、词组和短语等。特征项权重表示特征项在文本中的重要程度，为 了描述方便，一般将文档简记为 D = (W1 ,W2 ,&, Wn ) 。把 (T1 , T2 , &, Tn ) 看成一个 n 维的 坐标系， (W1 ,W2 ,&, Wn ) 为相应的坐标值，则 D = (W1 , W2 ,&,Wn ) 可以看成 n 维空间中 的一个矢量。 在向量空间模型中 , 文本和类别都被表示为空间中的一个点向量 , 文本向量和 类 别 向 量 之 间 就 存 在 空 间 上 的 距 离 远 近 ,而 这 种 距 离 就 可 以 采 用 向 量 间 夹 角 的 余 弦来度量 , 定义如下 :nSC (d , c) =n∑ (ωi =1di× ω ci )n? 2 2 ? ?∑ (ω di ) × ∑ (ω ci )? i =1 ? i =1 ?1 2(3.2)公式（ 3.2 ）中 d = (d1 , d 2 , &, d n ) 为文本 d 的特征向量 , c = (c1 , c 2 ,& , c n ) 为类别 特征向量，即用两个向量之间的夹角的余弦来表示文本与类别之间的相似度，夹 角越小，距离越近，余弦越大，相似度越大，反之相似度越小。计算出文本与所 有类别的相似度后，将其归入相似度值最大的类别中[22]。简单向量距离的分类思路十分简单，根据算术平均为每类文本集生成一个代 表该类的中心向量 ; 然后在新文本来到时，确定新文本向量，计算该向量与每类中 心向量间的距离 ( 相似度 ) ；最后判定文本属于与文本距离最近的类。 简单向量距离法效率高，易于实现，分类的精度能满足一般性的要求，但随 着信息量的增大、文本格式的多样化， VSM 效果不如人意，而且产生的无用信 息量会非常大，根本无法实现个性化查询，也很难提高用户的满意度和工作的效 率，因此，目前存在多种基于向量空间模型的分类算法，例如，支持向量机算法、 神经网络方法、最近 K 邻居方法和贝叶斯方法等等，下面都有介绍。 K- 近邻算法 (KNN) K 近邻分类模型，是最著名的模式识别统计学方法之一，它在很早就被用于 文本分类研究[23]，而且是取得最好结果的文本分类算法之一。KNN 分类模型的原理如下：首先，对于一个待分类文本，计算它与训练样本集中每个文本的文本相 似度，根据文本相似度找出 K 个最相似的训练文本，根据这 K 篇文本的类别来判断 待分类文本的类别值。即将待测文本与 K 个文本的相似度对每个类加权平均，求 得待测文本与所有类的类别值，类别值最大的类就为文本的归属类。类别值的计15Web 文本挖掘中的文本分类研究算公式如下：W ( c i | x ) = ∑ S ( x, x j ) p ( c i | x j )j =1 k(3.3)公式（ 3.3 ）中 S ( x, x j ) 是待测文本与 K 个文本的相似度， x1 ~ x k 是训练集中与 x 余弦相似度最大的 K 个文本向量，而 p (ci | x j ) 当 x j 属于类别 ci 时为 1 , 否则为 0 。其 中最重要的是参数 K 的选择，K 过小，不能充分体现待分类文本的特点；而 K 过大， 会造成噪声增加而导致分类效果降低 朴素贝叶斯分类 (NB) 朴素贝叶斯分类算法[27] [26]。是一种最常用的有指导意义的方法，它以贝叶斯理论为基础，是一种在已知先验概率与条件概率的情况下的模式识别方法。利用贝叶 斯公式通过类别的先验概率和词的分布来计算未知文本属于某一类别的概率。贝 叶斯分析方法的特点是使用概率去表示所有形式的不确定性，学习或其他形式的 推理都用概率规则来实现。贝叶斯学习的结果表示为随机变量的概率分布，它可 以解释为我们对不同可能性的信任程度。其公式如下：P (c i | d ) =P (c i ) P ( d | c i ) p(d )(3.4)其中， P(ci | d ) 为待测文本 d 属于类 ci 的概率， P(d | ci ) 为类 ci 中含有文本 d 的 概率。计算出文本 d 属于所以类的概率，假设总共有m个类，如果在所有P (ci | d )(i = 1,& m) 中， P(c j | d ) 的值最大，则文本 d 属于 c j 类支持向量机[28]。Vapnik 对统计学习理论深入分析 , 提出结构风险最小化准则，在此理论基础上的支持向量机方法 (SVM) ， 能够有效解决小样本集的机器学习问题 将 SVM 方法应用到文本分类， 并取得好的分类性能 现方法包括 Joachims 的 SVMlight 系统[31,32] [30] [29]， Joachims 。。 目前， 比较有效的 SVM 实[33]和 Platt 的序列最小优化算法支持向量机主要是针对两类分类问题，在高维空间寻找一个满足分类要求的 最优超平面作为两类的分割，既要保证分类精确度，又要使超平面两侧的空白区 域最大化，以保证最小的分类错误率。 决策树分类 决策树是一种常用数据分类技术，同样适用于文本分类，决策树的建立算法 有很多，其中包括：基于信息增益的启发式算法 ID3 ；基于信息增益率的解决连 续属性分类的算法 C4 ． 5 ；基于 Gini 系数的算法 CART ；针对大样本集的可伸缩 算法 SLIQ ； 可并行化算法 SPRINT ； 将建树和剪枝集成到一起的算法 PBULIC 等。 各种算法进行文本分类的基本过程相似[34,35]：首先，特征提取。对训练样本集中所有文本进行预处理 , 得到特征词条。16硕士学位论文其次，决策树的建立。决策树中每个非叶结点对应着一个非类别属性，一个 叶结点就代表了从树根到叶结点之间的路径所对应得文本所属的类别。建树的过 程就是依据某种规则选择一个测试属性，并根据这个测试属性将非叶结点不断分 裂的过程。建树的基本步骤如下： （ a ）若结点包含样本为同一类别 , 或无属性可选 择 , 或样本数量过少 , 则将其处理为叶结点并标记合适的类别 ; 否则根据某种标准选 （ b ）利用上一 择合适的属性 , 根据属性值将结点的样本集划分成两个或多个子集； 步递归处理各个子集，即在建树的过程中，测试属性的选择非常重要，主要的选 择方法有：例如信息增益、信息增益比、 gini 索引、距离度量、 G 统计、证据权 重、相关度等等方法 成了一条分类规则 。[1]。最后，规则抽取。从决策树的根结点到任一个叶结点所形成的一条路径就构3.3.2 文本分类的新模型潜在语义分类模型 潜在语义分析 ( Latent Semantic Analysis ,L SA) 是一种用于知识获取和表示 的理论和方法。其基本思想是文本中一个词往往有多个不同的含义、多个不同的 词也可以表示相同的语义、词与词之间存在某种潜在的语义关系，比如： “难过” 可以有“遇到困难，难以渡过”的意思，也可以理解为“心情不好”的意思； “立 刻” 、 “马上”也几乎有相同的含义。像这样的情况计算机是很难判断的，会导致 分类文档没有分到最相关的类上。因此 L SA 通过分析大量的文本集，自动生成关 键 字 / 概 念 (语 义 ) 之 间 的 映 射 规 则 ,并 通 过 统 计 方 法 提 取 和 量 化 这 些 潜 在 的 语 义 结构 , 进而消除同义词、多义词的影响 , 提高了文本分类的准确性[36]。潜在语义分类算法基于文本向量矩阵，通过对矩阵进行奇异值分解 (SingularValue Decomposition , SVD) ，计算得到一个比原始空间小的多的有效语义空间：?σ 1 0 ? ?υ1 ? ?# ? X = ∑ u iσ iυ i = [u1 & u r ]? % ? ? ? ? ? i =1 ? ? ? ? 0 σ r ? ?υ r ? ?r r（ 3.5 ）公式 （ 3.5 ） 中 r 是矩阵 X 的阶，∑ ≡ diag (σ 1 &σ r ) 是由特征值构成的对角矩阵， 一般 r 个特征值是按顺序排列的，只需要保留较大的前 k （ k & r ）个值，经过 SVD 降维处理后，矩阵 X 可以近似表示为： X ≈ X k = U k ∑ k VkT 。 U k 和 Vk 分别被称为 矩阵 X k 的左、右奇异向量 ,∑k是奇异值按递减排列的对角矩阵 , 对角元素被称[37,38]为矩阵 X k 的奇异值。当文档向量用 k 维表出来后，可以用夹角余弦公式或者向量 点积公式来判断待分文档所属的类别 。潜在语义分类模型还有很多改进方17Web 文本挖掘中的文本分类研究法，如基于潜在语义的多类文本分类模型、基于核方法的潜在语义文本分类模型、 这些方法都是分别针对传统潜在语义分类模型 基于粗糙集 - 潜在语义分类模型等， 某种不足的情况下提出的，有较好的性能。 神经网络分类算法 基于神经网络文本分类模型[39]的分类过程分为两个阶段[40]: (1) 网 络 训 练 阶段，为系统可以识别的每一个文本类别分别创建满足该类别特性的神经网络模 型 ; (2) 网络工作阶段，根据系统训练形成的若干神经网络模型对一篇未知类别的 文本进行分类，判别该文本所属的类别。 通 常 用 于文本分类的神经网络模型可采用一种三层前馈型 BP 网络如图 3.2 所 示[41]，来进行自动知识获取。输入层 输出层图 3.2 三层前馈 BP 网络图BP 网络有三个基本层，即输入层、隐含层和输出层。每个层都包含若干节点（神经元） 。 输入层的节点数通常为矢量的个数， 输出层节点数为输出矢量的个数， 确定适当的隐含层节点很重要，它直接影响网络的性能。层与层之间的每个连接 都有一个可以调整的权，权是根据样本数据所估计的系数，它模仿一个输入矢量 对输出矢量的影响[41]。给定一段文本及其特征集，输入层神经元的个数设定为特征集的大小，输出层神经元的个数设定为类别集的大小。输入层一个神经元对应 关键词集的一个词汇，输出层一个神经元则代表一个类别。 分类时，对一个待分文本将它的特征和权重输入到输入单元，这些单元通过 网络向前传播，最后输出单元的值就代表分类的结果。典型 的 神 经网络的学习 方法遵循“正向传播―反向修正”模式，不断重复。通过迭代地处理一组训练样 本，将每个样本的网络预测与实际知道的类标号比较，将比较结果反馈到网络的 前层单元中，修改单元之间的权重，使得网络预测和实际类之间的均方误差最小。 基于本体的分类模型 本体本来是一个哲学上的概念，从哲学的范畴来说 , 本体是客观存在的一个 系统的解释或说明，用于描述事物的本质，直观地讲，本体是一个实体，能够把18硕士学位论文现实世界中的某个领域抽象为一组概念和概念之间的关系。 目前，一般的文本分类方法都包括训练阶段和测试阶段，首先确定一个分类 体系，根据类别搜索训练文本，通过训练文本得到分类器，然后才能进行文本分 类。训练文本的好坏直接影响分类的结果，并且要耗费大量的人力物力。而将本 体运用到文本分类中，能够克服这方面的不足，不需要训练文本，不需要抽取特 征项。3.4 文本分类效果评价文本分类的效果评价参数主要有以下几个 文本数的比值，其公式如下： 召回率 = 分类的正确文本数 应有文本数[23]：召回率（查全率）是指通过分类系统正确分类的文本数与人工分类中应有的精确度（查准率）是指通过分类系统正确分类的文本数与实际分类的文本数 的比值，其公式如下： 精确度 = 分类的正确文本数 实际的文本数召回率（查全率）和精确度（查准率）反映了分类性能的两个不同方面，召 回率与精确度是相互制约的关系，可以通过牺牲精确度来提高召回率，同样也可 以通过降低召回率来改善精确度。往往在实际情况下两者必须综合考虑，因此有 人提出一种新的测试方法， F1 测试值。其数学公式描述如下： 查全率 × 查准率 × 2 查全率 + 查准率F1测试值 =另外 , 有微平均和宏平均两种计算准确率、查全率和 F1 值的方法。 微平均 : 计算每一类的准确率、查全率和 F1 值。 宏平均 : 计算全部类的准确率、查全率和 F1 值。 所有文本分类系统的目标都是使文本分类过程更准确 , 更快速。3.5 文本分类的应用文本分类的应用范围比较广泛，其主要应用环境如下所示： 电子邮件过滤。 电子邮件已被越来越多的人使用，成为因特网的重要应用之一，是网络使用 者互相交流信息的不可缺少的工具，但同时也有很多不法分子利用电子邮件传播19Web 文本挖掘中的文本分类研究反动信息、虚假广告、封建迷信等，严重扰乱社会秩序，近些年来垃圾邮件日益 严重，不仅耗费网络带宽而且还严重影响用户的正常工作，因此怎样将这些垃圾 邮件过滤成为了研究热点，而文本分类扮演了重要角色，它能对大量的电子邮件 进行分类，区分出垃圾邮件，便于邮件过滤系统的处理。 搜索引擎。 网络上的信息资源是越来越多，在这个浩瀚的网络资源里，要想找到自己需 要的资料必须借助于搜索引擎，搜索引擎就是一个信息处理系统，它以一定的方 法对互联网上的资源进行搜索、分析、整理、分类、并存贮在网络数据库中便于 用户查询，从而起到信息导航的作用。通常主要包含有全文搜索引擎和目录索引 搜索引擎两大类，全文搜索引擎主要是通过关键词匹配的方式在因特网上检索信 它虽然经过了相关度排序 , 但是相关和不相 息 , 检索的结果是一个线性文档的列表。 关的文档仍然相互混杂 , 其中绝大部分与用户的请求无关 , 用户需要逐个浏览才能 找出所需要的信息，而当返回结果很多时 , 往往使得检索的效率很低。目录索引搜 索引擎则有利于缩小查询的范围，加快查询速度，提高查询准确率。但使用前必 须对文本进行分类，如果使用人工方法分类，则实时性差，更新速度慢。通过将 文本自动分类技术应用到搜索引擎上 , 通过文本分类器自动将检索结果快速分类 , 以 分 类 目 录 树 的 方 式 显 示 检 索 结 果 ,这 样 可 以 大 大 降 低 用 户 需 要 浏 览 的 检 索 结 果 数量 , 方便用户快速找到与检索请求相关的信息 文档管理。 文档管理是十分烦琐而又非常重要的工作，通过文本分类将大量杂乱无序的 文档进行分类，可以对成千上万的文档实现高效的管理，便于很快地根据文档所 属的类别找到需要查询的文档的所在位置，以及其包含的基本内容。这样能提高 文档管理的效率，减轻文档管理员的负担。 信息检索服务 信息检索和信息获取服务充分利用网络跨越时空传递信息的优势 , 是 Internet 提供给广大网络用户服务的一个非常重要的组成部分，是一种快速、准确地查询 所需信息的重要方法。网络文本数据库一般来说是很庞大的，信息检索系统就需 要处理大量的数据，它的最终目标是为了帮助广大网络用户快速、准确地定位和 获取网络中的各种资源。文本分类系统能够对文档进行有序的组织，把内容大致 相同的文档组织在一起， 为信息检索系统提供高效的搜索方法和精确的查询结果。[42]。3.6 小结文本分类是 Web 文本挖掘的主要内容之一， 本章首先简单介绍了文本分类的 主要过程、文本分类的关键技术；接着重点介绍了几种文本分类的境地方法以及20硕士学位论文最新文本分类模型；本章最后简单介绍了文本分类性能评价的几种常用方法，阐 述了文本分类的主要应用环境。21Web 文本挖掘中的文本分类研究第 4 章 基于信息熵的 TFIDF 特征选择改进算法4.1 引言在第三章节我们介绍了文本分类大致可以分为以下四个步骤： 文本的预处理、 文本的向量空间模型表示、文本特征选择和分类器的训练。数量巨大的训练样本 和过高的向量维数是文本分类的两大特点，而这些高维的特征集对分类学习不全 是重要和有效的，同时这些高维的特征集会加重计算的负担。所以需要对文本信 息进行预处理 , 过滤一些无关的属性 , 以降低文本向量空间的维数并减少无关信息 对文本信息处理过程的干扰 , 使文本信息处理的精度得到提高。 那么特征选择的精 确性对文本分类的训练时间、分类准确性有着显著的影响，因此特征选择是文本 分类准确率和效率的关键。在文本分类中使用较多的特征选择方法包括文档频率 DF(Document Frequency) 、 互 信 息 MI(Mutual Information) 、 信 息 增 益 IG(Information Gain) 、 x 统计 CHI 、期望交叉熵 CE(Expected Cross Entropy) 、 文本证据权 WR 和优势率 ODD 等。本章对传统的 TFIDF 特征选择算法进行了简单介绍 和分析，并对 TFIDF 方法利用词条信息熵进行改进，提出了一种新的基于 TFIDF 的 特征选择算法。4.2 常用的几种特征选择算法信息增益 信息增益在机器学习领域应用比较广泛的特征选择方法，经常用作特征词的 评判标准。在数据挖掘分类算法中，用来对非类别属性进行排序，并依此构造决 策树。它是一个基于信息熵的的评估函数，定义为某特征在文本中出现前后的信 息熵的差值。其定义如下：IG ( w) = ∑ p (ci ) log 2 (i =1 m m1 ) p (c i ) 1 ) p (c i ) ∧ w? p ( w)∑ p (ci ∧ w) log 2 (i ?1 m? p( w)∑ p(ci ∧ w) log 2 (i ?11 ) p (c i ) ∧ w(4.1)公式（ 4.1 ）中 ci ( 其中 i = 1,2,&, m ) 表示第 i 类 , p(ci ) 是在训练样本集中样本是22硕士学位论文ci 类的概率， p ( w) 是名词 w 在训练样本集中出现的概率， p(ci | w) 是名词 w 出现的 前 提 下 样 本 是 ci 类 的 概 率 , p(ci | w) 是 名 词 w 不 出 现 的 前 提 下 样 本 是 ci 类 的 概 率。 IG 值越高，对分类预测提供的信息就越多。通过设定阀值，可以将 IG 值小 于阀值的名词删除掉，从而降低特征空间维数[43]。显然，某个特征项的信息增益值越大，贡献越大，对分类也越重要。因此， 在进行特征选择时，通常选取信息增益值大的若干个单词构造文本的特征向量。 在分类时先计算出各个特征词的信息增益，按照信息增益的值从大到小排序，根 据给定阀值，删除信息增益较小的词。 文档频率 它是最简单的评估函数，其值为训练集合中此单词发生的文本数在总的文本 数的概率，其理论假设为稀有词条或者对分类作用不大 , 或者是噪声 , 可以被删除。 虽然它在计算量上比其它的评估函数小得多，但是在实际运用中它的效果却是出 奇地好。但是它也有缺点，如果某一稀有词条主要在某类文本中出现的情况下, 可能会把该类的显著特征错误地过滤掉 和其他方法联合使用。 互信息 在文本预处理系统中互信息衡量的是特征和类别之间的统计关联程度。假设 有词条 w 和类 ci ，则互信息定义如下[44] [43]所以，一般此种方法不单独使用，通常：MI ( w, ci ) = logp ( w ∧ ci ) p ( w) p (ci )(4.2)其中， p( w, ci ) 为 w 和 ci 同时出现的概率，即在类 ci 中出现特征 w 的文本数除 以训练集中文本的总数。 p ( w) 为 w 出现的概率，即在整个训练文本集中出现特征w 的文本数除以文本集的总数。 p(ci ) 为类别 ci 出现的概率，即属于类别 ci 的文本数除以文本集的总数。在实际计算中 , 这些概率可以用训练集中相应的出现频率 予以近似 . 假设 w 和 c 在训练集中的出现频率为 A , N 为训练集中文本的总数目 ,B 为 w 在 训 练 集 中 出 现 的 文 本 数 , C 为 c 在 训 练 集 中 出 现 的 文 本 数 ,那 么 互 信 息 MI ( w, c) 可以近似为[45]： MI ( w, ci ) = logA× N 。那么在有 m 个类的训练集中，特制 B×C词条 w 的互信息可以定义为 w 与所有类的互信息值的平均值：MI avg = ∑ p(ci ) MI ( w, ci )i =1m(4.3)其中， MI ( w, ci ) 为特征词条 w 与类别 ci 之间的互信息， p(ci ) 为类别 ci 的概率。χ 2 统计量 χ 2 评估函数被定义为：23Web 文本挖掘中的文本分类研究CHI ( w, ci ) =n[ p ( w, ci ) × p ( w, ci ) ? p ( w, ci ) × p ( w, ci )] 2 p ( w) × p (ci ) × p ( w) × p (ci )(4.4)公式（ 4.4 ）中 n 为训练集的文本数， p( w, ci ) 为词条 w 和类 ci 同时出现的概率， 即出现词条 w 并属于类 ci 的文本数除以训练集中文本的总数； p ( w, ci ) 为词条 w 和 类 ci 都不出现的概率，即训练集中不出现词条 w 并不属于类 ci 的文本数除以训练 集中文本的总数； p ( w, ci ) 等于出现词条 w 但不属于类 ci 的文本数除以训练集文本 的总数。 p ( w, ci ) 等于不出现词条 w 而属于类 ci 的文本数除以训练集文本总数。这 个公式衡量了词条 w 和类 ci 之间的相互依赖程度。 CHI ( w, ci ) 值越小， 说明词条 w 与 类 ci 的独立程度越高，相反值越大，则说明词条 w 越依赖于类 ci 。另外，这个公 式还有另外一种相似表达形式，假设 N 是文本总数， A 是词条 w 出现在类 ci 中的 次数 , B 是词条 w 出现但不在类 ci 中的次数， C 是 w 不出现的次数， D 是 w 和 ci 都 不出现的次数，则，评估函数表达如下：CHI ( w, ci ) = N × ( AD ? BC ) 2 ( A + C ) × ( B + D) × ( A + B) × (C + D)(4.5)TFIDF 函数 TFIDF 是向量空间模型中经典的特征权值函数， 目前 TFIDF 的变种公式较多，但基本上都可以表示成词条频率与文档频率的函数，即 W (d ) = f (tf (d )) × g (df (d )) （ 4.6 ） 其中 tf (d ) 指词条频率，表示词条 d 在文本中出现的次数。df (d ) 指文档频率，表示词条 d 在整个文档集中出现的文档数，通常词条在文中出现的次数越多，则 表明词条越能表达文档的内容；另外词条在文档集出现的文档数越多，则词条的 区分度越差，对分类贡献越小，所以在传统的 TFIDF 特征选择方法中，词条的权 值与词条频率成正比，与文档频率成反比。4.3 TFIDF 特征选择的不足由于 TFIDF 函数在特征选择中使用较多，本文对其进行了认真研究，通过实 验发现这个方法存在着明显的不足之处：这种方法受训练集的影响较大，对于文 档频率，只考虑了包含某个词条文档数绝对量的多少，并没有考虑这些文档在每 个类中的分布情况。这样就会将文档数量稍多但基本都在同一个类中的一些重要 词条忽略，而将文档数量虽少但在各类中分布均匀的词条当作特征词条，这类词 条通常区分度是较低的，对分类的贡献应该不大。例如：在某个训练集中有财经、 科技、军事三个类，文档总数是 30 ，其中，股市、军舰、启动、指数四个词条的 分布如表 4.1 所示。 假定某被测文档 d 中股市和指数两个词条出现的次数都为 2 ，我们根据常用的24硕士学位论文TFIDF 公式 (4.7) 计算词条股市和指数的权值。表 4.1 单词频度分布表系统类别 财经 科技 军事股市启动军舰指数13 1 08 7 7 tf ik (d ) log( N + 0.01) nk0 0 31 1 1Wik (d ) =N (tf ik (d )) 2 × log 2 ( + 0.01) ∑ nk k =1n(4.7)由于在同一文档中，分母的值是相等的，设其为β ( β &0) ，则计算的权值如下： 股市： W股市 (d ) = 指数： W指数 (d ) =0.166β1.75β从计算的权值结果我们可以看出，即使股市在文本中出现的次数是指数出现 次数的 10 倍，其权值还是小于指数的权值，但从词条的分布情况看，包含股市这 个词条的文本很可能是属于财经类的，而包含词条指数的文本根本就无法区分应 该属于那个类，因此我们在计算特征词条的权重时，应该将词条文档在分类系统 中的分布考虑进去，这才符合实际情况，传统的方法没有考虑这一点，那么通过 这种方法进行的特征选择会造成分类不精确。基于上述原因，本文对传统 TFIDF 方法进行了改进。4.4 词条信息熵4.4.1 定义熵，是德国物理学家在十九世纪中叶创建的一个术语，用它来表示任何一种 能量在空间中分布的均匀程度。能量分布得越均匀，熵就越大。后来，香农 （ Shannon ）在创立信息论是，找到了一个唯一的量来度量信源的不确定性 , 解决 了对信息的量化度量问题，这个量与热力学和统计力学中的熵在数学形式和物理 意义都相近 , 所以也称为熵，在信息论中成为信息熵。下面是与信息熵有关的几个 定义[1]：25Web 文本挖掘中的文本分类研究定义 1若存在 n 个相同概率的消息，则每个消息的概率 p=1 ，一个消息传递的 n信息量为 ? log 2 ( p ) = log 2 (n) 。 定义 2 的熵，即 若给定的概率分布 P = ( p1 , p 2 ,& p n ) ，则有该分布传递的信息量称为 PI ( p) = ?( p1 ? log 2 ( p1 ) + p 2 ? log 2 ( p 2 ) + & + p n ? log 2 ( p n )) = ?∑ p k * log 2 ( p k )k =1 n（ 4.8 ）其中，若 P 是 (0.5 ， 0.5) 则 I(P) 是 1 ；若 P 是 (0.67 ， 0.33) ，则 I(P) 是 0.92 ；若P 是 (1 ， 0) ，则 I(P) 是 0 ，可以看出概率分布越均匀，其信息量越大。定义 3 若一个文档集合 T 中所有文档被分成相互独立的类 (C1 , C 2 ,& , C n ) ，其中 包含词条δ的文档在每个类中的概率分布为 P ，则词条δ的分布熵就是 I(P) ，其 中 P= (d 1/ n, d 2 / n,&, d k / n) 。 例如：在表 1 中，词条“股市”的分布熵为 I(P)=I(13/14 ， 1/14 ， 0)=0.389 ，词条 “指数”的分布熵等于 I (P)=I(1/3 ， 1/3 ， 1/3)=1.585 。4.4.2 性质信息熵的主要性质有以下几条[46]：（ 1 ）信息熵没有负值，由于概率值为 0 ≤ pi ≤ 1 的数，当对数的底大于 1 时， 必有 log(p)i ≤ 0 ，因此恒有： I(P)&0 ，即不管 P 的分布如何， I(P) 的值总大于 0 。 （ 2 ）信息熵满足对称性，当概率空间中 P(x1),)P(x2)… 序任意互换时，熵函 数的值不变，例如下面两个信源空间：? x1 x 2 x3 ? [ X , P( x)] = ? 1 1 1 ? ? ? ? ?3 6 2 ?? y1 y 2 y 3 ? [Y , P( y )] = ? 1 1 1 ? ? ? ? ?6 2 3 ? ?（ 4.9 ）其信息熵 I(X)=I(Y) ，该性质说明，熵只与随机变量的总体结构有关。 （ 3 ）信息熵有可加性，即统计独立信源 X 和 Y 的联合信源的熵等于它们各 自的熵之和。如果有两个随机变量 X 和 Y ，它们彼此是独立的，假如 X 的概率分 布为 [ P( x1 ), P( x 2 ),& , P( x n )] ，而 Y 的分布概率为 [ P( y1 ), P( y 2 ),&, P( y m )] ，则联合信 源的熵 I ( XY ) = I ( X ) + I (Y ) 。 （ 4 ）信息熵有极大值，信源各个状态为等概率分布时，熵值最大。对于有 N 个状态的信源， 当 P(x 1 )=P(x 2 )=...= P(x N )=1/N 时， I ( X ) = ?∑ (1 / N ) log(1 / N ) = log N ，i =1 n为信息熵的最大值。26硕士学位论文（ 5 ）递增性，即 I n + m ?1 ( p1 , p 2 ,& , p n ?1 , q1 , q 2 , &, q m )= I n ( p1 , p 2 , & , p n ?1 , p n ) + p n I m (其中，q q1 q 2 , ,&, m ) pn pn pn（ 4.10 ）∑ pi = 1 ， ∑ q j = p ni =1 j =1nm这性质表明，若原信源 X（ n 个符号的概率分布为 p1 ,& , p n ）中有一个元素划 分（或分割）成 m 个元素（符号） ，而这 m 个元素的概率之和等于原元素的概率， 则新信源的熵增加。4.5 基于信息熵的 TFIDF 改进方法从以上定义及其计算我们知道“股市”这个词条的信息熵为 0.389 ，词条“指 数”的信息熵为 1.585 ，而从表 4.1 可以看出“指数”的分布比“股市”的分布要 均匀，因此可以得出一个结论：包含某个词条的文档分布越均匀，其熵越大，越 不能表达文本的真实内容，对分类贡献也越小，越不能作为特征值。既然词条分 布熵反映了词条文档在各类之间的分布均匀程度， 而我在 4.3 节中又分析了 TFIDF 方法又受词条文档在训练集中各类之间的分布的影响较大，没有考虑到词条分布 情况，所以词条信息熵正好可以弥补 TFIDF 函数的不足，我们可以把两者结合起 来考虑，利用信息熵改进 TFIDF 算法。 我们在传统 TFIDF 函数的基础上乘上一个信息熵因子，即：Wik (d ) = f (tf k (d )) × g (df (d )) × ? ( I k ( p ))（ 4.11 ）其中 I k ( p) 表示词条 k 的信息熵， ? ( I k ( p)) 是信息熵因子，根据上面的分析， 词条分布越均匀，分类的不确定性越大，则熵也越大，该词条的特征值就应该越 小，所以首先我们设 ? ( I k ( p)) 为信息熵的倒数，即 ? ( I k ( p)) = 1 / I k ( p) ，但是，当某 个词条只分布在一个类中时，该词条的分布可能为 P(1,0,& 0) ，由公式（ 4.8 ）可 以计算信息熵取零，而分母是不能等于零的，所以继续改进这个函数，在分母上 加上一个极小值 0.01 ，这样又出现另一个问题，假如计算出的信息熵小于 0.01 ， 甚至比 0.01 的数量级更小，那么起主要影响的不是信息熵而是 0.01 ，所以这种方 法不可取，必须修改这个方法，我们可以先根据词条文档的数量计算出词条信息 熵的次小值，然后在分母上加上这个次小值，因为除了信息熵的最小值 0 以外， 对于词条的任何其它分布，信息熵都是大于这个值的，所以能避免以上情况发生。 由词条信息熵的定义，我们知道，假设包含词条 k 的文本数为 nk ，而分类系 统中的类别数为 c ，则对于词条 k 的所有分布，当所有的文本分布在同一个类中， 信息熵取最小值为零；当所有的文本平均分布在所有类中时，信息熵取最大值为? (1 / c) * log 2 (1 / c) ，那么，我们有理由推断当所有文本只分布在其中两个类中且其27Web 文本挖掘中的文本分类研究中一个类中只分布一个文本时，取次小值为? [(nk ? 1) / nk ] * (log((nk ? 1) / nk ) + (1 / nk ) * log(1 / nk )) ，其证明过程如下： (1) 由信息熵的递增性，文本分布的类越多则信息熵越大，则次小值只能出现在文本分布在两个类中这种情况。(2)根据(1)和信息熵的计算公式,构造函数φ k ( x) = ?((nk ? x) / nk * log 2 ((nk ? x) / n) + x / nk * log 2 ( x / nk )) ，其中 x 取值 (1,2, & nk ) ，求信息熵的次小值转化为求函数 φ k ( x) 的最小值， 根据信息熵的对称性， 可知 φ k ( x) 是 关于 x = nk / 2 对称的，所以我们考虑其在区间（ 0 ，nk / 2 ）之间的单调性对其求导：d (φ k ( x)) / dx = ?1 / nk * log( x / nk ? x) ，很明显当 x & nk / 2 时，倒数的值都大于 0 ，所以φ k ( x) 在 区 间 （ 0 ， nk / 2 ） 上 是 单 调 递 增 的 ， 当 x=1 时 ， 取 最 小 值? [(nk ? 1) / nk ] * (log((nk ? 1) / nk ) + (1 / nk ) * log(1 / nk )) ， 这个值也就是词条信息熵的次小值 φ k (1) 。 根 据 以 上 的 分 析 ， 我 们 可 以 得 到 改 进 后 的 信 息 熵 因 子π ( I k ( p)) = 1 /( I k ( p) + φ k (1)) 。但是通过实验我们发现，这个信息 熵因子对特征值的大小影响太大，为了减少其对特征值计算的影响，我们对 π ( I k ( p)) 取对数，同时 为了保证信息熵因子都为正数，给 π ( I k ( p)) 先加 1 然后再取对数， 得到信息熵因 子的计算公式为 ? ( I k ( p)) = log 2 (1 + 1) 。 I k ( p) + φ k (1)最后，提出一种基于词条信息熵的 TFIDF 特征提取方法，其公式如下：tf ik (d ) log( Wik (d ) =nN + 0.01) nk2N (tf ik (d )) × log ( + 0.01) ∑ nk k =12× log 2 (1 + 1) I k ( p) + φ k (1)(4.12)其中 tf ik (d ) 为词 k 在文档 d 中出现的频率， N 为训练文档的总数， nk 为训 练文档集中出现词 k 的文档数，I k ( p) 就是指词条 k 的信息熵，φ k (1) 指根据词条文 档总数计算出的该词条的次小信息熵的值 ? (nk ? 1 n ?1 1 1 log( k ) + log( )) 。 nk nk nk nk我们对表 4.1 中的文本数相同的词条“军舰”和“指数”进行验证，假设两 者在待测文档中出现的次数相同，都为 λ ，因为在分类系统中包含它们的文档数 相同，所以根据传统 TFDIF 特征选择公式，它们的特征权重相同都为λ ，而根据 β表中的分布情况，很明显包含“军舰”的文本很可能就属于军事类，根据词条“指 数”就很难判断，传统的公式没有体现出来，而利用改进后的 TFIDF 公式我们计 算出来的特征权重分别是：军事0.924λβ、指数0.455λβ。 “军事”的权重几乎是“指28硕士学位论文数”权重的两倍，这样应该更能反映实际情况。4.6 实验结果利用向量空间模型进行文本分类时，通常是先计算出待分文档与每一个类之 间的相似度，然后取相似度最大的类作为待分文档的归属类，一般相似度的计算 公式采用两个特征向量间的余弦夹角来表示：sim ( d i , c j ) =∑Wk =1 nnik× W jkn? ?? 2 ? ? ∑ W ik2 ? ? ∑ W jk ? ? k =1 ? ? k =1 ?(4.13)其中 Wik ， W jk 分别表示文本的 d i 和类 c j 第 k 个特征项的权值，本文也采用这 种方法。由于目前还没有一个通用的标准中文文本分类语料库，为了证明本文提 出的基于信息熵的 TFIDF 改进算法的有效性， 本文下载了中文自然语言处理开放 平台（ CNLP ）上的中文本文分类语料库 TanCorpV1.0 作为实验对象[47 ， 48]。该语料 库 包 括 三 个 分 类 语 料 集 ： TanCorp-12( 单 层 语 料 ) 、 TanCorp-60( 单 层 语 料 ) 、TanCorpHier( 两层语料 ) 。本文使用了 TanCorpHier 语料集，从中选取了教育类中的七个类：招生、校园、培训、留学、考试、就业、出版，共 808 篇文本。选取 其中 400 篇作为训练文本，其余 404 篇文档作为测试文本。在实验中使用精确度 和召回率两个常用的文本分类评估测试值，精确度等于正确归类的页面数与分类 系统分类的页面数的比值， 召回率等于正确归类的页面数与应有的页面数的比值。 我们分别使用传统 TFIDF 特征选择方法和基于信息熵的 TFIDF 特征选择方法对 其进行实验，分类实验结果分别如表 4.2 、表 4.3 所示。表 4.2 传统 TFIDF 特征选择（平均精确度 76.3% ，平均召回率 80.1% ）专家分类结果 出版 24 就业 73 考试 86 留学 34 培训 11 校园 112 招生 64 精确度（ % ） 召回率（ % ）出版 就业 考试 留学 培训 校园 招生20 2 0 2 0 0 3 74.1 83.30 55 3 5 0 6 1 78.6 75.31 6 72 0 1 4 0 85.7 83.7291 6 2 24 1 3 0 64.9 70.61 1 3 0 8 1 1 53.3 72.70 2 2 0 1 97 3 92.4 86.61 1 4 3 0 1 56 84.8 87.5Web 文本挖掘中的文本分类研究从测试结果可以看出，使用修改后的 TFIDF 特征选择方法后，分类的效果比 大多数类的精确度和召回率都有不同程度 使用传统的 TFIDF 特征选择方法要好， 的提高，另外，修改后的特征选择使平均精确度提升了 4.2 个百分点，平均召回 率提高了 3.0 个百分点，这样也证明了不仅包含词条文档的数量对权重有影响， 而且其在不同类中的分布也对词条权重有影响，考虑这一点能够提高分类的精确 度和召回率。表 4.3 基于信息熵的 TFIDF 特征选择（平均精确度 80.5% ，平均召回率 83.1% ）专家分类结果 出版 24 就业 73 考试 86 留学 34 培训 11 校园 112 招生 64 精确度（ % ） 召回率（ % ）出版 就业 考试 留学 培训 校园 招生21 0 0 1 0 2 1 84.0 87.50 57 1 2 1 4 1 86.4 78.10 3 80 2 1 8 3 82.5 93.22 4 1 27 1 0 0 77.1 79.41 1 0 0 8 3 1 57.1 72.70 2 2 1 0 90 0 94.7 80.40 6 2 1 0 5 58 80.6 90.64.7 小结本文首先简单介绍了信息增益、文档频率、互信息、 χ 2 统计量几种常用的特 征选择算法，并重点介绍了 TFIDF 特征选择算法，分析了 TFIDF 特征选择算法的不 足，指出传统 TFIDF 算法没有考虑词条文档在分类系统中的分布情况，使得计算 出的特征值不符合实际情况。接着本章简单介绍了信息熵的定义，信息熵是信息 论中的一个概念，是总体的平均不确定性的量度。本章最后结合信息熵，提出了 改进的 TFIDF 算法，并通过实验证明了本章改进算法的有效性。30硕士学位论文第 5 章 基于向量空间模型的多主题 Web 分类5.1 引言Web 文本分类是当前文本挖掘的研究热点之一，本文第三章已经介绍了其主要分类方法，包括贝叶斯分类算法 (Naive Bayesian Classifier) 、最近邻接参照分 类算法 ( K-Nearest Neighbor) 以及基于本体的文本分类算法等，这些算法只是将Web 页面分到某一个类中，而许多网页包含多个不同的主题，就要求分到不同的类中，例如，某个网页 A 是关于“教育乱收费”的，我们就应该把该 A 分到“教 育”和“法制法规”两个类中；某网页 B 主要内容是关于“农作物的价格”报道， 就应该把 B 分到“农业”和“财经”两个类中。目前对此问题的研究较少，普遍 采用的方法是首先设定一个固定阀值，然后分别计算待测文档与每个类之间的相 似度，当待测文档与某个类的相似度大于设定的阀值时，就将待测文档分到这个 类中。这种方法中，阀值的大小对分类的精确度和召回度的影响比较大，如果阀 值过大，则有可能把原本属于某个类的文档排除在外，召回率变小，如果阀值太 小则把原本不属于某个类的文档划分到了这个类中，精确度变小。设置一个恰当 的阀值是同时保证较高精确度和召回率的关键， 本章提出的多主题 Web 分类方法 根据待分页面与所有类之间的相似度动态的计算一个阀值，实现了将多主题网页 分到多个类中。实验证明这种方法有很好的精确度和召回率。5.2 基于向量空间模型的单主题 Web 分类5.2.1 Web 文档的表示在 向 量 空 间 模 型 ( VSM ) 中 ， 每 个 文 档 被 表 示 成 特 征 向 量 ：V (d ) = (t1 ,w1 (d ); t 2 , w2 (d );&; t n , wn (d )) ，其中 ti 为特征词条， wi (d ) 为特征词条 i 在文档中的权重。可以将 d 中出现的所有词作为 ti ，但这样就会使得特征向量的维数 特别高，包含噪声，特征不明显，而一个文档的内容主要是动词、名词、形容词 等实词决定的，虚词和一些在所有文档中都出现的高频词对分类是没有任何意义 的，所以必须进行特征提取，降低特征空间的维数，达到降低计算的复杂度、提 高分类准确率的目的。31Web 文本挖掘中的文本分类研究5.2.2 特征向量的计算特征项在文档中的权重 wi (d ) 的计算对 Web 文本分类也是至关重要的一步，wi (d ) 一般被定义为 ti 在文档 d 中出现的频率 tf i (d ) 的函数，即 wi (d ) = F (tf i (d )) 。常有的 F 有布尔函数、平方根函数、对数函数、TF-IDF 公式为[51] [49 ， 50]函数，而 TF-IDF 公式是一种有效而较普遍使用的方法，目前这种方法存在许多变体公式，一般采用的 ：W (t, d ) = tf (t, d ) × log(Nt∈dnt+ 0.01) + 0.01)]2∑[tf (t, d ) × log(N× [1 +∑aj∈L rjnt∑ai =1]i(5.1)其中， w(t , d ) 为词 t 在文档 d 中的权重， tf (t , d ) 为词 t 在文档 d 中出现的频率，N 为训练文档的总数， n 为训练文档集中出现词 t 的文档数， r 为特殊标记的数目， ai （ i = 1,2,&, r ）为特殊标记的权重， L 为网页中修饰词条 t 的所有特殊标记 组成的集合。从公式可以看出： （ 1 ）权重 w(t , d ) 的大小与词 t 在文档 d 中出现的频 率成正比，词条 t 在文档中出现的次数越多则权重越大； （ 2 ）权重 w(t , d ) 的大小与 可成反比，即训练文档集中出现词 t 的文档数越多则权重越小； （ 3 ）词条 t 在网页 中被标记的特殊标签的数目对权重 w(t , d ) 的大小也有影响，被标记的特殊标签越 多，表明词条 t 在文档中越重要，则权重也越大。5.2.3 相似度的计算利用向量空间模型进行文本分类时，通常是先计算出待分文档与每一个类之 间的相似度，然后取相似度最大的类作为待分文档的归属类，一般相似度的计算 公式采用两个特征向量间的余弦夹角来表示：2 sim(d i , c j ) = (∑ Wik × W jk ) / (∑ Wik2 )(∑ W jk ) k =1 k =1 k =1 n n n（ 5.2 ）其中 Wik ， W jk 分别表示文本的 d i 和类 c j 第 k 个特征项的权值。5.2.4 分类系统结构及算法分类过程如图 5.1 所示。 我们可以把图 5.1 的分类过程概括为训练和分类两个阶段，其中训练算法的工 作是对训练文档集合中每篇文本对应的词表进行统计 , 计算出类别向量矩阵同时 进行归一化 , 最后保存训练得到的向量表 , 即得到了分类知识库 ; 分类算法则依据训 练得到的分类知识库并用一定的算法对待分类文本进行分类。详细分类过程描述 如下：32硕士学位论文预处理 待分类文本 特征向量预处理 训练文本集 特征向量训练 类特征向量 分类算法分类结果图 5.1 基于向量空间模型的单主题分类过程1) 训练阶段：步骤一 确定分类体系，即明确分类系统中包含了那些类别，通常用(c1 , c 2 ,& , c n ) 表示，其中 n 为类别数量。步骤二 从 Intel 网络上下载网页，经过专家进行分类后，将所有文本分为训练 文本集 Tr （ Training set ）和测试文本集 Te （ Test set ）两个部分。 步骤三 对训练文本集 Tr 中所有文本进行分词处理，然后进行预处理，去掉停 用词以及 HTML 标签等无用信息，每篇文本生成一个向量 d 。 步骤四 利用词条互信息、 x 2 统计量 (CHI) 、信息增益 ( IG) 等特征提取方法对 上一步生成的向量 d 降维。 步骤五 利用 TFIDF 公式计算每个特征词条 t i 的权值 wi 。 步骤六 根据每个词条的权重 wi 进行排序，抽取排在前面一定数量的词条作 为特征项，生成特征向量表 , 每篇文档表示为向量(t1 , w1 ; t 2 , w2 ;&t i ,&t n , wn ) , t i 特征项词条 , wi 为对应的权值。步骤七 计算整个训练集中某类文档集的特征向量， 分别对每个类 ci 中的所有 特征词条 t i ，将 t i 在 ci 中的所有文本中的权值 wi 相加，然后求得算术平 均值 wi ，将 wi 作为特征词条 t i 在类 ci 特征向量中的权值。 步骤八 为所有类构造类别特征向量 ci : (t1 , w1 ; t 2 , w2 ;&; t n , wn ) ，假设训练集总 共分为 n 个类，对这 n 个类分别通过训练算法得到 n 个类特征向量的集 合，即得到该训练集的类特征向量集。2) 分类阶段：步骤一 对待测文本进行分词、预处理，生成一个向量。 步骤二 对上一步得到的向量进行降维处理，利用 TFIDF 公式计算每个特征 词 条 t i 的 权 值 wi ， 生 成 该 文 本 的 特 征 向 量 d : (t1 , w1 ; t 2 , w2 ;&t i ,&t n , wn ) 。 步骤三 利用两个特征向量间的余弦夹角公式计算特征向量 d 与每一个类的 类特征向量之间的相似度。 步骤四 选择相似度最大的类别作为待测文本的归属类。33Web 文本挖掘中的文本分类研究5.3 基于向量空间模型的多主题 Web 分类5.3.1 多主题分类基本思想如前所述， 当前许多基于向量空间模型的 Web 文本自动分类方法都是通过比 较某个网页与所有类之间的相似度，把相似度最大的类作为网页的归属类，只是 笼统的将网页划分到最相似的类中，没有考虑到存在多个主题的网页应该被划分 到多个类的情况，针对这种不足，本章提出了一种多主题分类方法，实现了将包 含多个主题的网页划分到相应的多个类中，其实现过程如图 5.2 所示。预处理 训练文本集 特征向量 训练 类特征向量预处理 待分类文本 特征向量相似度集 分类结果 比较分类 动态阀值图 5.2 基于向量空间的多主题分类过程分类基本思想：给定一个网页，提取特征向量，计算与所有类的相似度，然 后根据本文上述方法计算分类动态阀值，将所有的相似度和这个阀值进行比较， 如果某个相似度大于这个阀值则该网页就属于相应的类。5.3.2 动态阀值阀值的确定是分类的关键，因为待分类页面与所有类的相似度可能都很小也 可能都很大，所以在分类前确定一个固定阀值是比较困难的，而且也是不恰当的， 我们可以根据每个待分类页面与各个类的相似度的实际情况动态的计算出一个阀 值，这样每个待分类页面在分类时使用的阀值是不相同的，不是固定的。我们将 动态阀值设定为所有相似度的平均值，即vt =1 n ∑ si n i =1计算相似度(5.3)但是，在从实验中计算出的相似度发现，相似度小的值比较多而相似度大的 值比较少，这样计算得到的阀值往往都偏小，导致原本不属于某个类 c 的网页错 误的划分到类 c 中，分类的精确度较差，另外在进行网页分类时，一般分类规则34硕士学位论文是将相似度较大的类作为网页的归属类，所以我们要修改以上方法，尽量让动态 阀值偏向于较大相似度。利用待分页面 α 与某个类 ε 的相似度越大， α 被划分到 类 ε 的可能性就越大这种特征，我们根据相似度的大小给每一个相似度分配一个 权重 ws ，并得到向量 WS （ ws1 ， ws 2 ， ws 3 … ws n ） , 其权重的计算方法如下：WS i =si∑sj =1n(5.4)j从以上公式可以看出，相似度越大则对应的权重值就越大。将所有的相似度以空 间向量的形式表示为 S （ s1 ， s 2 ， s3 … s n ） ， 然后将权重值和相似度进行线性组 合得到动态阀值的计算公式如下：vt = S × WS = ∑ S i × WS ii =1 n(5.5)利用这种方法计算的阀值随着相似度的变化而变化，当相似度都大时阀值就 偏大，当相似度都小时阀值偏小，又因为相似度越大对应的权重就越大，所以由 上述公式可以知道阀值介于最大相似度和最小相似度之间， 并偏向于较大相似度。 例如由相似度 7 、2 、2 、1 、1 、1 、3 、2 得到的动态阀值近似等于 3.6, 由相似度 7 、6 、 1 、 1 、 2 、 2 、 2 、 3 、 3 、 4 得到的动态阀值近似等于 4.3 。通过实验和理论分析我们发现，当类较少时，这种方法比较理想，能够得到 较好的精确度和召回率。但是在类很多的情况下，由于大部分类都是与待测网页 关系不大甚至是毫不相关的，那么就很有可能计算出大量较小的相似度，导致阀 值偏小，使得分类精确度降低。所以，我们继续修改，由上所述我们知道，相似 度越大，对应的类作为归属类的可能性越大，而且只有少数相似度值都比较大， 因此，我们可以使用聚类方法将相似度划分为较大，中等，较小三个部分，然后 在相似度值大的部分寻找归属类，这样就能提高精确度。5.3.3 聚类聚类分析的算法可以分为以下几大类：分裂法、层次法、基于密度的方法、 基于网格的方法和基于模型的方法等。下面是常见的几大类聚类分析算法的基本 思想[1]：1. 分裂法给定一个有 N 个元组或者记录的数据集，分裂法将构造 K 个分组，每一个分 组就代表一个聚类， K&N 。而且这 K 个分组满足下列条件： （ 1 ） 每一个分组至少包含一个数据记录。 （ 2 ） 每一个数据记录属于且仅属于一个分组。35Web 文本挖掘中的文本分类研究使用这个基本思想的算法有： K-MEANS 算法、 K-MEDOIDS 算法、 CLARANS 算法等。2. 层次法这种方法对给定的数据集进行层次的分解，直到某种条件满足为止。基体又 可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”方案中，初 始时每一个数据记录都组成一个单独的组，在接下来的迭代中，它把那些互相邻 近的组合成一个组，直到所有的记录组成一个分组或者某个条件满足为止。代表 算法有： BIRCH 算法、 CURE 算法、 CHAMELEON 算法等。3. 基于密度的方法这种方法的指导思想就是，只要一个区域中的密度大过某个阀值，就把它加 到与之相近的聚类中去，代表算法有：DBSCAN 算法、OPTICS 算法、DENCLUE 算法等。4. 基于网格的方法这种方法首先将数据空间划分成为有限个单元的网格结构，所有的处理都是 以单个单元为对象的。这样处理的一个突出优点就是处理速度很快，通常与目标 数据库中记录的个数无关，它只与把数据空间分为多少个单元有关。代表算法有：STING 算法、 CLIQUE 算法、 WAVE-CLUSTER 算法。 5. 基于模型的方法基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这 个模型的数据集。 这样一个模型可能是数据点在空间中的密度分布函数或者其他。 它的一个潜在的假定就是：目标数据集是由一系列的概率}