（通信与信息系统专业论文）基于潜在语义分析的web文本分类研究.pdf

华北电 力大学硕 士学位论文摘要 摘要 本文提出潜在语义分析的w eb 文本分类方法，该方法认为在词汇之间， 词汇与 文本之间存在着某种上下文的关系， 多篇文本与多个词汇可以由各自的关系构成一 定的 语义结构。 对这个语 义结构进行计算、 处理， 保留文本与词汇间最主要的关系， 去除 其它庞大、冗余、次要的影响因素。 优化后的语义结构， 不但比原始的文本词 汇相关结构小巧得多， 而且保留了其中 最为主要的相关关系， 从而可以挖掘出文本 与词汇的潜在语义关系， 较传统的基于词空间的文本分类方法能更加有效的处理文 本的 高维特性。 从而能在该语义结构的基础上， 计算出 文本和文本之间的潜在相似 度 ，提高 w eb 文本分类的精度。 关键词:潜在语义分析， w eb文本分类，向量空间 模型，奇异值分解， 局部特征空 间 abs tract t b l s p aperp r o p o s e da me t h o dtow七 bt e x t c at e g o ri z ati o nb ase do nl at e nt s e ma nti c anal y s i s ， i t thi nks thats o me c o nte x t re l at i o n s exi stb e twe e nt e rms ， b e twe e nt e rm s and d o c u 刀 。 e n t s ， and as e m ant i c st ruc tur e c an b ec o n s i sto f r e s p e c ti v e r e l at i o nb et we e n many d o c u me nis a n d t e rm s . t h e s e m anti c s t ruc t u r e i s c o m p u t e dand d e a 1 withthe s tru c ture t o k e e p th e m o stm a i nr e l at i o nb e t w e e nd o c uments and t e rms an de l i m i n a t e s e l s e h u g e ， r e d und a n t ， 血n o r facto r.th es truc t u r eo pti 面z e di s n o t o ulys marte r than the o r i g i n a l s t ru c t ur e ， b ut al s ok e e p sth em o stm a i nr e l at i o n ， i se as i e r t od e al with th ehi g h d i me n s i o n al i ty c h arac t e r i s t i co f t li et e xt d o c um e nt b ase do nv s m， s oitc an min eth e l ate nt s e ma n t i cr e l at i o n . i ns e que nt s e arc h ， thei at e ni s i mi l arity i sc o m p ut e db et we e n d o c um e nts and i mp rov e sthe e ffectiv e o n the p e r fo rm anc e o fthe w已 b te xt c at e g o ri z at i o n . w自 n gj i an fe n g( c o nunumc at i o nandi n fo rmat i o ns y stem ) d i r e ct e db yp r o f.yuan j i n s h a k e ywor d s : l a t e n t s e ma n t i c a n a ly s i s ，we b t e x t c a t e g o riz a t i o n ，vec t o r s p a c e mo d e l ，s i n g u l a r val u e d e c o mp o s i t i o u ，l o c a l fe a t u res p a c c 二七.口口 尸明 本人郑重声明: 此处所提交的硕士学位论文 基于潜在语义分析的w 已 b 文本分 类研究 ， 是本人在华北电力大学攻读硕士学位期间， 在导师指导下进行的研究工 作和取得的研究成果。 据本人所知，除了文中 特别加以 标注和致谢之处外， 论文中 不包含其他人己 经发表或撰写过的研究成果， 也不包含为获得华北电力大学或其他 教育机构的学位或证书而使用过的材料。 与 我一同 工作的同志对本研究所做的任何 贡献均已在论文中作了明 确的说明并表示了谢意。 学 位 论 文 作 者 签 名 : .五 刃 举。 ， : ，! 。 / .了 关于学位论文使用授权的说明 本人完全了 解华北电力大学有关保留、 使用学位论文的规定， 即: 学校有权 保管、并向 有关部门 送交学位论文的原件与复印件; 学校可以 采用影印、缩印 或 其它复制手段复制并保存学位论文; 学校可允许学位论文被查阅或借阅: 学校 可以学术交流为目 的， 复制赠送和交换学位论文: 同意学校可以 用不同 方式在不 同媒体上发表、 传播学位论文的 全部或部分内 容。 ( 涉密的学 位论 文在解密后遵守此 规定 ) 作 者 签 名 : 工 剑 碎 日期 : 夕 沪2 2 了 导 师 签 名 澎禅 奥 日期 : 立卫 妇里一 华北电力大学硕士学位论文 第一章引言 课题 的背景和意义 1 . 1 . i w e b 文本分类定义 w e b 文本分类是指按照预先定义的 分类体系，将待分类的w eb 文本测试集合中 的每个文本归入一个或多 个类别中， 是一种典型的有教师的机器学习问题。 经过文 本分 类处理， 用户不但能够方便浏览文本， 而且可以通过限制搜索范围来使文本的 查找更为容易。目 前 ，y ahoo 仍然是通过人工对 w eb 文本进行分类，这大大限制了 其索引页面的数目 和覆盖范围， 可以说研究w eb文本分类有着广泛的商业前景和应 用 价 值 1 1， 1 。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到 己有的类别中，用数学公式表示如下:f : a 冲b 其中， a为待分类的文本集合， b 为分类体系中的类别集合。 文本分类是系统根据训练集 的样本数据信息总结分类规律并确定待分类文本 的 相关 类别3 .文本分类是处理海量文本的有效方法，它能提供文本集的良 好组织 结构， 大大简化文本的存取和操作， 提高文本处理效率。 文本分类在数字存储技术 日 益普及的今天， 应用的范围十分广泛，例如:数字图书馆、电子邮件分类、新闻 分 类 、 文 本 检 索 等 等 141 15 6 . 1 . 1 2 w eb 文本分类的重要性 随着工 nternet 及其相关技术的飞速发展， 互联网 上出 现了海量的、 异质的w eb 信息资源，在这些庞大的信息资源中， 蕴含着具有巨大潜在的 有价值的知识.人们 迫切需要能够从w eb上快速、 有效地发现资源和知识的工具。 于是功能强大的搜索 引擎问世了( 如g oog le， a i t a v i s ta和b aidu等) ，这些搜索引擎可以 按照知识的种 类进行分门 别类建立索引， 有效的减轻了人们从海量的信息资源中 寻找有价值信息 的负担。 但是， 由 于网络信息的爆炸式增长， 搜索引擎的覆盖率有限， 其查全率低; 同时， 大多数搜索引擎都 是基于全文的检索， 不能达到赋词标引的效果， 也导致查 准率较低。 再者， 绝大多数搜索引擎智能化水平低， 不能有效地提供个性化用户服 务; 加之最重要的一点是， 搜索引擎的目的 在于定位 w eb上的资源， 就w eb上的知 识 发 现 而言， 搜索 引 擎不 能 够 胜任 171 181 91 . 为了从海量数据中发现有效、新颖、 潜在有用、可最终理解的 模式， 数据库领 华北电力大学 硕士学 位论文 域引入了数据挖掘( d atam ini ng) 。但是，数 据挖掘的主要对象是结构化的数据仓 库( d ata w a reh o u se) ， 对于w eb上的异质、非结构化信息，并不能直接应用数据挖 掘的 技 术: 为 了 解决 这 个问 题， 人们 将传 统 的 数据 挖 掘 技 术跟web 技 术相 结 合形 成 了现在的w eb挖掘技术， w eb挖掘作为一个具有挑战性的 新课题被提了出来，并得 到了 业界人士的广泛关注。 另外研究发现，在海量的w eb信息资源中，有 8 。 % 以上 的信息是以 文本的形式存在的， 因此隶属于w eb 内容挖掘的w eb文本挖掘显得尤为 重要。 w e b 文本分类是w eb文本挖掘的一项重要技术， 是指将w eb文本集合中每个文 本归入一个预先定义的类别之中。 这样， 用户在浏览w eb文本时，就不会因为纵横 交错的超链接而 “ 迷路” ， 而是基于一种主题分类的指导。目 前， y ahoo还是基于 人 工手工来对w eb 上的文本进行分类， 这种作法存在弊端: 一是耗费了大量的人力和 物力， 二是由于个人的主观因素导致分类结果存在不一致现象;同时大大降低了索 引数目，另外由于互联网的飞速发展，w eb 上大量的文本信息急剧增加，这种超出 想象的信息增长迫切需要更高效更智能化的文本分类技术的产生， 从而使得分类的 正 确率 提高 ， 保 证检 索结 果的 查全 率 和 准确 率 110 i1 11 。 随着w eb文本分类技术在搜索引擎技术、 数字图书 馆技术、 信息过滤、信息检 索、 互联网信息监控等领域的广泛应用， w eb文本分类的研究己经成为信息处理的 一个前沿课题，有着广泛的应用前景和重要的研究意义。 1 .z we b 文本分类技术的研究现状 1 .2 . 1文本分类方法的研究现状 在 砰 eb 出现之前， 人们已 经对文本自 动分类问题进行了大量的研究， 形成了 文 本自 动分类技术。 随w eb 上海量的文本信息的增加， 文本自 动分类技术的处理对象 从普通的文本扩展到了w eb 文本。 很显然， 文本自 动分类技术也成为w eb文本分类 技术的基础。 国 外对于文本自动分类的研究开展较早， 50 年代末， h .p .l uhn在这个领域 进行了开创性的研究，提出了基于词频统 计思想的文本自 动分类方法。1 9 60 年， m a r o n发表了 关于自 动分 类算法的第一篇论 文，随后以 k . spark ， g .s alt on 以 及 k .5 .jones 等人为代表的众多学者也在这一领域进行了很有成效的 研究工作。目 前国 外的文本分类研究己 经从实验性阶段进入到了实用化阶段， 并在邮件分类， 电 子会议等方法取得了 广泛的应用， 其中 较为成功的有麻省 理工学院为白宫开发的邮 件分类系统和卡内 基集团 为路透社开发的constru e 系统112 ll 3 。 国内对于文本自 动分类的 研究起步较晚， 1 9 81年， 侯汉清教授对计算机在文本 2 华北电力大学硕士学位论文 分类工作中应用作了探讨和阐述。此后， 我国陆续研究 产生了 一些文本分类系统， 其中 有具有代表性的有上海交通大学研制的基于神经网 络算法的中文自 动分类系 统， 清华大学的自 动分类系统等等。 同时在不伺的分类算法方面也展开了 广泛的 研 究和实现，中科院计算所的李晓黎、 史忠植等人应用概念推理网进行文本分类， 查 全率 达 到 94 . 2 ， 准确 率达到99 ，ll4 。 中 国 科 技 大 学的 范 众等 人 在 k n n 、 贝 叶 斯 和 文档相似性研究的 基础上提出了一个超文本协调分类器， 正确率接近 8 0%，它的 特 点是适当的考虑了html 文本中结构化信息。 复旦大学和富士通研究中心的黄营著、 吴立德等人研究了 独立语种的文本分类，并以 词汇和类别的互信息量为评分函 数， 考虑了单分类和多分类， 最好的查全率为88. 8 7%。 上海交通大学的刁倩、 王永成等 人结合词权重和分类算法进行分类类， 基于向 量空间模型 ( v ect or s p acem odel， v s m )的封闭式测试实验中分类正确率达到97%o 目 前， 一些比较成熟的文本分类算法己 经被应用到了w eb文本分类中， 其中 有 基于vsm 的向 量距离法、贝叶斯分类算法、 knn 分类算法、支持向 量机分类算法、 决策树分类算法和神经网络分类算法等等， 近些年还出现了基于粗糙集合理论的文 本 分 类 算法和 一 些 结合 多 种方 法的 混 合 分类 方 法 115 i 6 。 1 . 2 2 分类关键技术的研究现状 在对 乳b 文本进行分类的过程中，包括几个关键步骤:文本预处理、 分词、 权 重计算、特征提取、降维技术，这些关键技术的研究和实现对最终的分类算法都有 一定程度上的影响，下面将对分词、权重计算、特征提取和降维技术的研究现状做 简单介绍。 ( 1)分词的研究现状 汉语分词是中文文本分类的一个基础环节。 汉语不像英语那样， 词与词之间存 在明显的分词标记，如空格、换行和标点符号;而汉语是一种无明显词间间隔的语 言， 词与词之间没有分割标记和界限， 因而存在一个如何分词的问 题就是分词技术。 汉语自 动分词是机器翻译、 文献标引、 智能检索、 自 然语言理解与处理的基础， 也是中文文本分类的一个关键的环节。自 从 80 年代初自 动分词被提出以 来，有众 多的专家和学者为 之付出了不懈的努力， 涌现了 许多成功的汉语分词系统，主要有 北京航空航天大学研制的cdw s 和c w ss 分词系统， 分词速度为2 00 字每秒。 清华大 学黄昌宁、马晏等开发的s e g 系统， 分词速度为2 58字每秒，正确率为9 9 .3%。 东北大学姚天顺建立的基于规则的汉语分词系统。 南京大学王启祥等人实现的w s bn 分词系统。中科院 计算所研制出的汉语词法分析系 统 ictcl as 等等。 汉语自 动分词系统的实现及效果依赖于分词理论与方法。目 前国内分词系统所 华北电力大学硕士学 位论文 采用的或者正在研究的方法基本上分为三类: 机械分词、 基于理解的分词和基于统 计 的 分 词 1 ，1 ，: 。 (2) 权重计算的研究现状 文本的基本元素是词、 词组和短语，文本经预处理和分词后， 抽取能表示文本 的 特 征 项组 成 文本 的 特征向 量 形 式， v (d ) = 拭， 不 (d) ，兀 ， 巩(d) ， ， 兀 ，嗽( d) ) 其中爪 (d) 表示对应特征项的权重。 特征项的权重综合反映了该特征项对标识文本内容的贡献 度和文本之间的区分能力。 常用的 特征项权重计算函数有以下几种: 布尔函数、开 根 号函 数、 w id f 函 数、 著 名的t f 一 工 dp公 式 法【19 。 1 . 2. 3特征提取的研究现状 特 征提 取 就是 从 特征 集t = tl ， ，t，中 提 取 一 个真 子 集t= tl ，一 ，t，. ， 其中， ， 为 原始特征集的大小，了为提取后的特征集大小. 提取的准则是经特征选择后能有效 提高文本分类准确率。选择没有改变原始特征空间的性质，只是从原始特征空间中 提取了一部分重要的特征，组成一个新的低维空间。 文本分类中，用于特征提取的统计量大致有:特征频度，文档频度，特征嫡， 互信息，信息增益，尸统计量， 特征权，期望交叉嫡等。 这些统计量从不同的角度 度量特征对分类起作用。 目 前， 也出 来了 一些新的特征提取方法， 如低损降维方法、 频率差方法、 b aye s 准则 法、fi值准则法和f i s h e r 简便量法等120 。 1 .3 本文的研究工作 本文着重于对基于潜在语义分析的w eb 文本分类技术进行讨论与研究， 主要工 作包括: ( 1)详细地讨论了文本标引与标引词一文本矩阵的生成， 包括文本标引、标引 词权值的选择、归一化公式的选择、 w eb文本矩阵的 特征表示; ( 2)给出了潜在语义分析的理论基础并阐述了其基本原理及相关问题， 对比基 于传统的向量空间模型，给出 基于潜在语义分析的份 eb文本分类的步骤及方法; ( 3)分析了标引词的局部性， 通过提取局部特征空间提高标引词集合的质量， 给出 语义空间提取方案，从而对潜在语义分析的w eb文本分类方法进行改进。 1 . 4 本文的内容组织 本文共六章组成: 华北电力大学硕士学位论文 第一章 引言， 该章介绍课题的背景和研究意义，分析we b 文本分类的研究现状， 其中主要分析 w 己 b 文本分类方法和文本分 类关键技术的 研究现状， 给出论文的主要 研究工作和组织结构。 第二章 w 七 b 文本分类前预处理，该章介绍w e b 文本分类前预处理的重要性和所包 括的重要内 容， 包括文本 采集和分词。 给出 文本采集的方法和分词算法， 并对分词 中出现的歧异性问 题进行了 详细分析，给出 解决方案。 第三章 文本标引与标引词一 文本矩阵的 生成， 该章主要介绍了 文本标引的重要性， 给出标引词一 文本矩阵的生成方法，包括文本标引词的权值的选择和归一化方法。 第四章 认 飞 b文本分类方法研究与实现，该 章首先分析传统的 基于空间向量模型的 文本分 类方法的不足， 介绍了潜在语义分析的 基本原来， 给出 基于潜在语义分析的 w七 b 文本分类方法和关键步骤，并给出 各步的实现方法。 第五章 基于潜在语义分析w 七 b 文本分类方 法的改进， 该章详细分析了 标引词的 局 部性，给出局部语义空间的提取方案，对文本分类方法进行改进 . 第六章 总结与展望，该章总结了本文的研究成果和本课题可以继续研究的工作。 华北电力大学硕士学位论文 第二章 w eb文本分类前预处理 文本预处理是文本分 类的 第一步， 对文本分类效果的影响 至关重要。 与传统的 数据库中的结构化数据相比，w eb文本具有有限的结构，或者根本就没有结构，即 使具有一些结构， 也还是着重于格式，而非文本的内 容， 且没有统一的结构，因此 需要对这些文本数据进行相应的标准化预处理; 此外文本的内容是使用 自 然语言描 述， 计算机难以直接处理其语义， 所以 还需要进行文本数据的信息预处理。该章给 出文本预处理中 重要的两部分: 文本采集和分词， 并给出各部分的算法和并且对实 现中可能出现的奇异性问 题给出 解决方案。 2 .i w匕 b 文本信息采集 w eb信息采集( w ebcrawl in g ) ， 主要是指通过 w eb页面之间的链接关系211 ，从 脆b 上自 动地获取页面信息， 并且随着链接不断向整个 w eb扩展的过程。 可以 通过 程序完成信息采集， 程序的 过程为: 从一个初始的u rl集出发，将这些 u rl 全部放 入到 一个有序的待采集队 列里。 而采集器从这个队列里按顺序取出 u rl， 获取 u rl 所指向的页面，然后从这些已 获取的页面中提取出 新的 u rl。 并将它们继续放入到 待采集队列里，然后重复上面的过程，直到采集器根据自己的策略停止采集 。对于 有些采集器， 到此就算完结了， 而对于另一些采集器，它还要将采集到的页面数据 和相 关数据存储、 索引并在此基础上对内容 进行分析。 目 前，国内外的信息采集研究已 有十余年的历史，已 经实现了一些系统， 从采 集器的采集 目标来看，它们可以分为两种类型: ( 1) 基于整个w eb 的信息采集器， 它的目 标是从一些种子 url 出发， 尽可能多 地采集信息页面甚至是整个 w eb上的资源122 。 这类采集器主要作为门 户搜索引擎和 大型的w eb服务提供商的 数据收集部分，由 于需要采集的页面数量过于庞大，因此 在消 耗巨大的系统资源和网络资源的同时， 这类采集器信息覆盖率日 益下降， 页面 失效 率不断增长，采集下来的页面利用率很低。 ( 2) 基于主题的 w eb 信息采集器，它的目 标是只采集与特定主题相关的信息 页面。 这类采集器对整个 w eb页面进行分类， 按类别采集， 有效地减少采集页面的 数量， 增加采集页面的规整程度，因此大大减少系统资源和网 络资源的消耗，并且 提高采集下来的页面利用效率。 每个采集器是一 s p i d er，是系统与 w eb 直接进行交互的 部分 主要通过 w eb 协议自 动采集 工 n t e r ne 上所有与主题相关的 信息。 为保持高速获取页面， 在并行机 制的 基础上， 对各个采集器采用多线程技术，在一般情况下， 每个采集器能启动数 6 华北电力大学硕士学位论文 百个线程. u r l管理器采取交织存取的方式管理待采集 u rl 队列和向各个采集器分 配采集任务， 因此可以保证同一个采集器上最多只有一个线程同时连接同 一个信息 服务器，从而有效避免导致该服务器因访问量骤增而出 现阻塞甚至死机。 2. 2 w 七 b 信息采集的关键技术 信息采集是信息分类的第一步，即通过网络 s p i d er 在网 络上 “ 爬行”来获取 信息。 大多数搜索引擎， 如 a l t a v i s t a ， g o o g l e 和l y c o s 都是用广泛的 “ 爬行” 来 获得较高的覆盖率。由于一般的搜索引擎的目 标是提供搜索这个w eb 的能力， 故搜 索引 擎就致力于尽可能多的寻找不同的w eb网页， 所以一般搜索引擎都采取广度优 先的 策略。 而对于特殊领域的搜索引 擎，则要求它的 s p i d er 能够避开那些与本领 域无关的链接， 将注意力集中在相关链接上， 现在常采取的方法是效率优先的巩固 学习 方 法( r e i n f o r c e m e n tl e ar n i n g ) 。 ( 1) 广度优先策略 信息采集的每一次搜索都从外部指定的一条 u rl 开始，这条 u rl 被称作 “ 种 子” 。我们将网络复杂的图结构简化为一个具有冗余节点的树结构。之后，就可以 采用遍历树的 方法来遍历网络了。由 于希望s p ider: 每回抓取的站点都集中在“ 种 子” 周围，因 此选用宽度优先算法， 这样离 “ 种子” 越近的 u rl 越先被获取. 采 用链表结构来记录需要获取的 url ，具体步骤是: 将 “ 种于”的u r l加入链表; 读取链表中第一个 u r 工 ，抓取相应 h t ml文本，进行分析，提取概要信 息， 并在h t m l 文本中找出 指向其它h t m l 文本的超链接， 若不与链表 中任一元素重复，则将此 u r l加入链表尾部; 判断程序是否结束，若没结束，则返回 。 通过指定抓取的 最大节点数来设置结束 条件或不限节点数而让 s pid er 自 动遍 历终止。 ( 2 ) 效 率 优先 的 巩固 学习 策 略(r e in fo r c e l e a r n in g ) 有效的网 络爬行是令人关注的。 对于特殊领域的搜索引 擎来说， 因为己经圈定 了搜索的主题范围，此时 广度搜索己 是次要的了， 而主要的是搜索效率。 巩固学习 是通过对反馈的信息进行奖惩来学习的. 其最大特点是: 学习者并未被告知何谓正 确行为， 而仅仅被告诉其所选择的行为是好或者坏， 好或坏的 程度以 分等级的 “ 奖 惩”来表示。 若设状态的 集合为5 ， 对于任何一种状态5 ， 满足条件5 5 ; 行为的集合为a， 对于任何一种行为a ，满足条件a a:函数 r :s* a兮5是状杰一行为转换函数， 华北电力大学硕士学位论文 该函数可以将一种状态经过一种行为而映射到另一种结果状态;函数r : 5 * a 峥贝 是奖 励函数， 该函数将对于一种状态经历过一种行为后给予分级的奖励。 在每一个 时间段内学习者( 或称为代理) 选择一种行为， 将会获得一个奖励和转换到一种新的 状态。 巩固学习策略的目的就是学习一种策略，即学习一个从状态映射到行为的策略 二 : 5 斗a， 使得学习者在学习的全部时间内获得奖励值的和最大; 通过极限方式来 近似的得到奖励值之和是最常用的方法。通常的方法如下:设。 y 0) 或 者叱= 0( 巩二 0) 布尔模型的特点是在权重计算时采用布尔权重进行评估。 七 e r m 作为向量的维数 来表示文本，向 量完全是以 0 ，1形式来表示，即 如果文本中出现了该词，那么文 本向量的该维为 1 ，否则为 0 。权重函数为布尔函数，定义为: 1 . .” 职 0 代 = to. ，. 城= 。 但是这种方法无法体现标引词在文本中的作 用程度， 所以0 和 1 逐渐地被更精 确的词频代替。词频分为绝对词频和相对词频:绝对词频，即使用标引词在文本中 出 现的频率;相对词频为归一化的词频，其计算方法主要运用t f 工 d f 公式。 ( 2 ) t f i d f 型权重 tf: 叽二 巩 tf ， 刃 尸 : 巩二 巩 ， fo g( 叼职 ) ( 3 一 2 ) ( 3 一 3 ) 叽“ 巩 ， fo g 洲 刀 双 ) 艺 itfx，* 10 9 ( n/ 鱿) ， ( 3 一 4 ) ( 3 ) 基于嫡概念的 权重( e n t r o p y， e i g h t i n g ) 华北电力大学硕士学位论文 巩 = 1 0 9 ( te， + 1 0 ) * 10 9 ( 叼刀 月 ) 艺l 0 9 ( tfb + 1 0 ) * lo g( n/dfk) ， ( 3 一 5 ) t f i d f 法的指导思想的 前提是这样一条基本假设: 如果一个单词 在一个文本中 出现的次数很多， 那么该单词在另一个同类文本中出 现次数也会很多，反之亦然. 所以 ， 如果将特征空间的坐标系取tf 词频作为测度， 就可以体现同 类文本的特点。 接受t f i d f 法的基本假设，就是说如果以t f 词频作为特征空间的 坐标系测度， 那 么文本向 量彼此之间的夹角可以反映出两个文本的差异 大小， 进而判断它们是否同 类。 那么现在面临的问题是: 一个文本中对分类有用的词只占 很小部分， 而大部分 词与我们要判别的类无关，属于 “ 噪音词” ，结果两个文本之间的夹角在很大程度 上是由 这些噪音词的词频差异， 而非有用词的词频差异决定。 这些噪音完全可能淹 没有用信息，从而导致以作为坐标系测度的分类方法精 度极低。 对于这个问题，一种解决方法是对各 t erln 加权，权重大小取决于 t e r m有用的 程度，有用的 t e r m 乘的权重高，无用的 t e rm 乘的权重低。由于每个文本向量的长 度都是归一化了的，加权的结果实际上是使向量在特征空间中向有用的 t e r ln所代 表的那些维旋转了一个角度.旋转后，无用的 t e r m词频的差异对向量夹角的影响 被减小，而有用的 t er。词频的差异对向量夹角的影响被加强，也就是说噪音被抑 制，有用信号被加强。 3 .4 权值的选择与归一化 标引词不仅与一个文本有关，同时与文本集的关系也较密切，故对标引词的加 权过程由三个部分组成:局部、全局、规范化。 对 标引 词 一文 本矩阵 a 二 (au) ， 。 中 的 每 一个 元 素马定 义 如 下: 几= l ( 1 ， j ) x g ( 1 ) x n(力( 3 一 6 ) 其 中， l( i， 力为 标 引词汽 在 文 本吮中的 局部 权 值， 仅 与标 引 词 在 文本呜中 的 信 息有 关:g (i) 为标引 词毛 的 全 局 权值，同 整 个文 本 集中 标引 词毛 的 使用 情况 有关; n(力 为 文本呜的 归一 化因 子 下 面给出 最 常用的 l( i， 力，g( i)， n 仃 ) 的公 式列 表 12 81 2 91 ， 见 表3 一 1 ， 表3 一 2 ， 表3 一 3 华北电力大学硕士学位论文 表3 一 1 局部权值l(i ， j)计算公式 符号 名称公式 b二值 x ( 儿) t 标引词频率 儿 c 增强的规范化标引词频 率 天 u ) i xl j，) +j ma x ; 几 l对数 10 9 ( 儿 + 1 ) 表 3 一 2 全局权值g (i)计算公式 符号 名称公式 x无 l f 倒排文本频率 ， 。 1 l 乙 ， ， ，不 、 八 ) p 频率倒排 ， n 一 艺 一_lx (几 ) ) l二，x u ， )j 表 3 一 3 文本归一化因子n 名 称 的计算公式 符号 无 余弦 公式 1 艺 几 1(l (i ， )x g (i ) 万 加权的 方案由 一个三个字母所组成的串 指示， 三个字母相应地代表局部、 全局、 规范化。例如 ，使用加权策略 hn ，则表示， fo g ( 几+ 1 ) 内 = ( 3 一 7) 乏几 ， 10 9 ( 凡 十 1 ) ， )王 局部权值l(i ， 力的选择依赖于文本集中的标引词，对于一般或变化的 词汇， 选 择标引词频率公式作为局部权值， 对于标引词表很短( 或者说标引词一文本矩阵维 数很小 ) 时， 选择二值公式作为局部权值。 倒排文本频率公式( 力和概率倒排公式( 力 华北电力大学硕士学位论文 是最好的全局权值公式。 文本归一化因子的 余弦公式( n)对于较长的文本不是很有 效 。 3 .5 本章小结 该章主要介绍了三个方面的内容， 首先介绍了文本标引的方法和本文所采用的 方法， 然后重点介绍了 标引词一文本矩阵的生成方法和步骤，由于标引词一文本矩 阵中每个元素代表标引词在文本中出 现的 加权频率， 权值的选择对于矩阵的生成有 重要影响，所以在该章最后部分给出 标引词权重的选择与归一化方法. 华北电力大学硕士学位论文 第四章 web 文本分类方法研究与实现 该章主要介绍利用潜在语义分析方法进行 w eb 文本分类的方法和步骤， 并对比 传统的基于向量空间模型的方法， 给出基于潜在语义分析方法进行w eb 文本分类的 优点。 传统的 基于文本关键字的向 量空间 模型( v s m)，用m个关键字维构成的文本向 量d ， 只= 心 ， 姚 ， ，心 ， 表示 文 本集中 的 一个 文 本， 并 基于 此 进 行文 本 过滤、 检索 的处 理.它将非结构化的文本表示为向量形式， 使得各种数学处理成为可能. 它的 优点 在于处理逻辑简单、快捷。 但是，向 量空间模型关于词间 关系相互独立的 基本 假设( 正交假设) 在实际环境中很难满足， 文本中出 现的词往往存在一定的相关性。 在某种程度上会影响计算的结果。同时，这种基于关键字的文本处理方法，主要依 据词频信息，两个文本的相似度取决于它们拥有的共同词汇的数量，因而无法分辨 自 然语言的 语义模糊性。自 然语言中 存在着大量的同义词和多义词现象， 语义的准 确表达不仅取决于词汇本身的恰当使用，也取决于上下文对词义的限定。如果忽视 上下文语境的限制，仅以孤立的关键字来表示文本的内容，势必影响查询结果的准 确性和完整性 。另外基于向量空间模型的文本矩阵维数过高，增加了计算的复杂度 使得分类算法的精度降低。 本文利用潜在语义分析 ( l a t e n t s e m a n t i ca n a l y s i s ) 方法进行文本分类，认 为词语在文本中的使用模式内存在着潜在的语义结构，同义词之间应该具有基本相 同语义结构， 多义词的使用必定具有多种不同的语义结构13 2 。 潜在语义分析就是通 过统计方法提取并量化这些潜在的语义结构，进而消除同义词、多义词的影响:利 用奇异值分解 ( s i n g u l ar v a l u e d e c o m p o s i t i o n ) 对文本矩阵 进行降维，从而提高 文本表示的准确度。 利用潜在语义分析进行 w eb 文本分类的步骤为: ( 1)生成标引词文本矩阵。 ( 2)在特征空间上运用文本聚类方法将样本集合分为若干簇。 ( 3)提取每一类别的特征，对得到的鉴别特征利用鉴别变换进行特征抽取，进 行降维。 (4) 最后用得到的各个簇的特征矢量对待分类的文本进行分类 。 4 . 1 向量空间模型 ( vec t o r s p a c e mo d e l ) 传统 向量空间模型把文本和查询式表示成向量形式， 从而将信息检索转化为向 华北电力大学硕士学位论文 量空间的向 量匹配问 题【291。为便于描述问 题，给出以 下有关 概念的 定义: 定义1文本:指一般的 文献或文献中的片断，通常指一篇文章，记为d。 定义2索引项: 是指文本中 含有且能 够代表该文本性质的基本语言单位， 记为 定义3 索引 项 权重、: 表 示索 引 项兀 对 文 本几的 重 要 程 度。 气= l (i ，k )xg (i)， 其中 l( i， k)， 代 表 索引 项兀 在 文 档几中的 局部 权 重，g (i)为 索 引 项界 的 全 局权 重。 其计算方法主要运用犷 一 idf 公式，目 前存在多种扩一 可 公式， 现给出一个常用的归 一化公式， 呱= 呱x l o g ( 叼) ( 4 一1 ) 酞。 。 【呱 109 ( 叼 们 式(4 一 1)中， 关表 示索 引 项兀 在 文 本几中出 现的 次 数( 即 索 引 项 频 率) ， 几越 高， 意 味 着索 引 项界 对 于文 本只越重 要; 或表 示含 有索 引 项兀 的 文 本 数 量( 即 索 引 项的 文本 频 率 ) ， 听越高， 意 味 着索 引 项界 在 衡量 文 本之 间 相 似性 方 面 的 作用 越低; n = 回， 即 全 部文 档的 数 量， 分 母 为归 一 化因 子; 晰= lo g( 叼或) 为 逆向 文本 频 率， 晰 越 高， 意味 着 索引 项界 对 于 文本的 区 别 作用 越 大。 如 果一 个 索引 项兀 仅出 现 在 一个文本中，则峨 二 fo g( 刃 。如果一个索引项界出 现在所有的文本中，则 ida = 1 0 9 1 = 0 。 定 义4 向 量空 间 模 型: 设 文本 集 合中 共 有n 个不同 的 索引 项不 ，兀 ， ，二 ， 兀 ， 根 据 式 (4 一 1)计 算 文 本只的 索引 项 权 重、， 如果 把文 本不 ， 兀 ， ，兀 ， 看成 一 个n 维 坐 标 系， 、为 坐 标系 的 值， 则试 = ( 衅， 峭， ， ， 嵘， )t 成为n 维空 间中 的 一 个向 量， 即 文 本只的向量 表示。 设 用 户 查 询式向 量为马 = ( 衅， 峭， ， ， 嵘，) ， 为 索引 项 界 在 查询 式q 中 的 权 重， 并根据布尔模型进行确定，则用户查询式的向量化过程可表示为， 吧= 抒 l u ， 若界。 q 若界必 q ( 4 一 2) 定义5相似度: 衡量一篇文本向量与用户查询式向量的相近程度， 即 判断某篇 文本是否是用户所需要的。 计算相似度的 方法有许多种， 通常用两个向 量的夹角余 弦或 j accard 相似度函数，其中 j accar d 相似函数为: 艺心)心， 5 ( 全 ， 试 ) = j ( 弓 ， 试 ) = ， 不 一-二 一一 一 一 二 一 一 一 一 一 - 艺 ( 昨， )， + 艺 ( 嵘，) ， 一 艺 ( 嵘， )( 嵘，) ( 4 一3 ) 华北电力大学硕士学位论文 标引 词 权重、的 直观 含 义是 一个 标引 词 对于 一 个文 本的 重要程 度， 即 一 个标 引 词 在多 大 程 度上 可以 将 该 文 本与 其 它文 本区 分 开 来。 采 用梦 一 idf方 法对 标引 词 加 权， 在一定程度上给那些经常出现在较少文本中， 而不常出 现在绝大部分文本中的 标引词赋予更高的权重130 l3 1 。 由 于 w eb文本的半结构化特征， 一些标引词出现在特殊位置上，比 如:标 题， 小标题，超链接等不 同域。这些特殊位置的内容代表了 w eb 文本的重要信息，因此 标引词出现的位置与其权重密切相关。 而向 量空间模型中采用了一 idf 方法计算标引 词权重时忽略了这些信息的 重要性， 这是造成w eb信息检索系统输出结果排序能力 差的主要原因之一。 另外， 文本向 量计算过程中采用了扩 一 idf 方法， 这样导致每增加一个， eb 文本 都需要重新计算向 量，从而增加了系统的负载，使分类速度变慢32卜 135 。 4 .2 潜在语义分析基本原理(l a t e n t s e man t i 。 a n a l y s i s ) 潜在语义分析方法认为在特征词条之间存在潜在的语义关联， 而这种语义关联 仅仅通过特征词条的词频特性不能很好地描述136 l3 7 。 对任一w eb 文本数据库， 特征 词 条的 数目 国和 文本 数目 剑通 常 会很 大， 如 此高 的 维 数会 导致 非 常大 的 稀 疏向 量， 进而影响计算效率， 增加寻找类特征的难度。 潜在语义分析出发点就是文本中的词 与词之间存在某种联系，即存在某种潜在的语义结构。这种潜在的语义结构隐藏在 文本中词语的上下文使用模式中，因此采用统计计算的方法，对大量的文本中进行 分析来寻找这种潜在的语义结 构，它不需要确定的语义编码， 仅依赖于上下文中事 物的联系， 并用语义结构来表示词和文本，达到消除词之间的相关性， 简化文本向 量的目 的 38 139 140 。 三 维 一潜 在 语义 空间 示 例如 图4 一 1 所 示 正交) 语义维一1 护 语义维一2 护 词向量 八 妇 文本向量e 妇 (正交 语义维一3 图4 一 1三维 一潜在语义空间示例 潜在语义分析首先对文本矩阵进行奇异值分解导出潜在语义结构模型. 将矩阵 分解成三个特殊矩阵的过程就是将文本矩阵 所表示的词与词间的关系分解成线性 l 9 华北电力大学硕士学位论文 独立的分量的过程。 这些分量中 有许多非常小， 完全可以 忽略， 从而得到维数少得 多 的 近 似 模 型 14 ， 11 ， 14 3 。 4 .3 奇异值分解 ( 5 认 g u l arval u e d e c o m p o s it io n ) 奇异值分解可以 把任何一个实矩阵 转换为对角阵形式。 对于矩阵a，a t a 具有 非负的特征值。a t a 的特征值的非负平方根称为a 的奇异值， 非零奇异值的 数目 等 于a 的 秩仓 口 月 无 ( a) ) 。 设a 为m x n 矩阵 ， 并 且仓 口 ” k( a) ) = r ，a 的 奇异 值分 解定 义 为 1 5 0 1 . a= u 下 f 7 t( 4 一 4 ) 其中u和v为正交矩阵，矩阵u的大小为mx m，矩阵v的大小为 n x n ，牙为 奇异对角阵，大小为m x n ，是原矩阵a 的消减矩阵。牙对角元素为a 的奇异值: al ，0 2 ， ， a， ， 0 ， ， 。 ， 且al之 几乡 二 之 口 ， 0 。 由 于 矩阵平中 的 对 角 元素由 大到 小 排列， 可以保留前k 个最大的特征值，而对较小的特征值取为零。如此 ，对u、平和v做 相 应的 处 理， 可以 得 到 矩阵a 的 一 个 近似 矩 阵再， 且rank( 凡) = k ， 再= 认巩 叮( 4 一 5 二 其中 ， 删去u 的 第k +1到 第m 列 得 到认， 删 去vt的 第k +1到 第n 行 得到可。 奇异值分解的步骤为， 先求出 矩阵的秩， 再求出 矩阵的所有非零奇异值，奇异 值的 个数小于等于矩阵的秩:根据奇异值构成一个对角线矩阵 5 ， 5的主对角线上 的 元素是奇异值， 其它元素为零; 根据奇异值计算出奇异值对应的奇异向量构成两 个奇异矩阵，分解得到三个矩阵( 一个对角线矩阵，两个奇异矩阵) ，这三个矩阵相 乘 就 能 得 到 初 始 矩 阵 44 4 5 . 进行奇异值分解时主要是求出矩阵的奇异值然后根据奇异值算出两个奇异矩 阵， 设a 的 非 零奇 异值 有r 个， 分 解生 成 的 三 个矩 阵 是嵘 ， 呱和珠。 根 据 矩阵a 新生成一个矩阵b ， b 是a 和a 的转置的乘积即b = aar 或者b = a t a， 这样b 的 特征值的非负平方根就是a 的奇异值， 而且aar 和a t a 有相同的特征值，因此通过 求aar( 或a t a ) 的特征值的 平方根就可以 得到矩阵a 的奇异值。 矩阵朋r 的特征向 量 称为 左 奇 异向 量，r 个 左 奇异向 量 构 成呱 ; 矩 阵a t a 的 特征向 量 称为 右奇 异向 量， 产 个 右 奇异向 量 构 成珠。 因 此根 据 特 征 值求出 aar 和矛a 的 特征向 量， 就能 得 到 两 个 奇异 矩阵嵘 和玲. 上述获得的两个奇异矩阵和一个对角线 矩阵是高维矩阵，需要对其进行简化， 根据前面选取的k 值来确定奇异值分解得到的三个矩阵的 维数， 分解得到的三个矩 阵嵘 、 凡 和珠中的 k 就 是 选取的 k 值. 通 过 选 取恰当 的k 值可以 减少 三 个矩阵 的 维数， 而且简化后的三个矩阵的乘积与初始矩阵是非常近似的， 对于进行下一步计