（计算机应用技术专业论文）基于本体的web页面分类挖掘.pdf

摘要 w 曲是一个巨大的 广泛分布的全球化信息仓库 它提供了新闻 财经 广告 商务 文化 教育等多方面的信息服务 如何有效地帮 助用户从w 曲上发现他们感兴趣的资源 已经成为一个迫切需要解 决的课题 论文首先介绍了w 曲挖掘的一些基本概念 方法和技术 阐述 了什么是w 曲挖掘 为什么要进行挖掘 研究了基于主题特征词和 统计学知识的w 曲页面分类挖掘的一般过程和方法 作者针对一个 已有的系统进行分析 指出了该方法的局限性 在学习阶段对于训 练集依赖性大 导致在训练集不足的情形下分类的精度不高 针对基于主题特征词和统计学知识的w e b 页面分类挖掘的缺陷 提出了基于本体的w 曲页面分类挖掘模型 该模型利用本体来表述 已有知识 在此基础上对解析后的页面采用多种匹配方法进行信息抽 取 并结合三个算法来计算页面与本体的相关度 来提高相关度计算 的正确性 建立更为有效的分类规则 以力求提高分类的精度 建立了一个基于本体的w 曲页面分类挖掘原型系统 通过实验 表明 这种基于本体的方法确实能够在训练集数量较小的情况下 得 到较高的分类精度 同时也与原有的系统进行了对比性实验 确实证 明了该方法的在训练集较小的情形下 比基于主题特征词方法的能够 有更好的精度 最后对本文的工作进行了总结 并确定了进一步研究方向 关键字 w 曲挖掘 本体 分类 a b s t r a c t c u r r e n t l y w 曲i sa n e m e n d o u sw i d e g l o b a l i n f b r n l a t i o n a lw a r e h o u s e w h i c hi n v o l v e si nn e w s f l n a n c ea n d e c o n o m i c s a d s c o m m e r c e c u l t u r e e d u c a t i o na n do t h e ri n f o 衄a t i o ns e r v i c e h o wt o h e l pu s e r sf i n dw h a t t h e ya r ei n t e r e s t e di nh a sb e e nac h a l l e n g e t h i s p 印e rn r s t l y i n t r o d u c e ss o m ew e bm i n i n g sb a s i c c o n c e p t s w a y sa n dt e c h n i q u e s t h e n i ts t u d i e sc l a s s i c a lw e bp a g e sc l a s s i f y i n g p r o c e s sa n dt e c h n i q u e sb a s e d o n t o p i cf b a t l l r e sa n d s t a t i s t i c sa n da s y s t e m a sa ni n s t a n c e t h i st r a d i t i o n a ls 0 1 u t i o nb a s e do nc o o c u r r e n c eo f t e r m s b o t hr e c a l la n d p r e c i s i o na r en o ts a t i s i n e d e s p e c i a u yw h e nt h e 锄o u n to f t r a i n i n gd a t a i sn o t e n o u 曲 t br e s o l v em ea b o v e m e n t i o n e d p r o b l e m w ep r o p o s ea n 印p r o a c hf o r a p p l y i n gb a c k g r o u n dk n o w l e d g et oi m p r o v ec l a s s i f i y i n gr e s u l t s g i v e na n o n t o l o g ys p e c i f i c a t i o n w e p r o c e s s h t m ld o c u i i l e n t s a n de x t r a c t i n f o 肌a t i o nb a s e do nt h e o n t o l o g y t h e n 印p l y s e v e r a lh e u r i s t i c st o c o m p u t e s i m i l a r m e a s u r e m e n t s i no r d e rt ob u i l d m o r e p r e c i s e c l a s s i 6 c a t i o nm o d e lb a s e do nm a c h i n e l e 锄i n g w bh a v e c o n s t m c t e dad e m o n s t r a t i o n p r o t o t y p e b a s e do nt l l i s a p p r o a c h w eh a v ee x p e r i m e n t a l l ya n da n a l y t i c a l l ys h o w nt h a to u rm o d e l c o m p 2 l r e dt ot h es y s t e mb a s e do nt o p i c h i g h e rd e g r e eo f p r e c i s i o na n d r e c a l l f e a t u r e s a c h i e v e sas i g l l i f i c a t l t i y f i n a n y t h es u m m a r ya n dt h en j r t h e r s t e p sa r eg i v e n k e y w o r d w e b m i n i n g o n t o l o g y c i a s s i f l c a t i o n 原创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果 尽我所知 除了论文中特别加以标注和致谢 的地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料 与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明 作者签名 马和 日期 兰翌生年 月j 互日 关于学位论文使用授权说明 本人了解中南大学有关保留 使用学位论文的规定 即 学校 有权保留学位论文 允许学位论文被查阅和借阅 学校可以公布学位 论文的全部或部分内容 可以采用复印 缩印或其它手段保存学位论 文 学校可根据国家或湖南省有关部门规定送交学位论文 作者签名 曼垃导师签名 日期 型堡年工月立日 硕十学位论文第一章绪论 1 1 问题的提出 第一章绪论 自从2 0 世纪9 0 年代之后 随着网络技术的发展 尤其是i n t e m e t 的广泛应 用 w 曲已经成为了人们获取信息的主要场所 它涉及新闻 财经 广告 商务 文化 教育等多方面的信息服务 如何快速 准确地获得网络中有价值的信息 如何理解已有的历史数据并用于预测未来的行为 如何从这些海量数据中发现知 识 成为需要着手解决的问题 这样的需求促成了数据挖掘在w 曲方面的发展 w e b 挖掘的出现 w 曲挖掘是从 b 资源上获取知识的过程 是对w 曲资源中蕴含的 未知 的 有潜在应用价值的知识的提取 w e b 挖掘通过3 种不同的数据挖掘任务来获 取有用的知识 1 通过w e b 上内容的挖掘获取知识 2 通过对w e b 上结构的挖 掘获取知识 3 通过对w 曲上日志的挖掘获取知识 在完成w 曲数据挖掘任务 时 既需要使用一些传统数据挖掘技术 也要使用 些基于w 曲的数据挖掘的 特有技术 通过w e b 挖掘既可以使人们能够快速地找到自己所需要的资源 对w e b 网 页进行分类聚类 为站点管理者 投资者和广告商提供合理的建议 以及提供功 能强大智能检索服务和搜索引擎等 目前 在该领域的主要应用研究集中在 搜 索引擎 i n t e r n e t 信息推荐 共同社区的建设 个性化服务 白适应站点等 比 较典型的系统有g 0 0 9 l e 网络信息搜索工具 i b m 的t e x t m i n e r 川 以及 w e b m i n e r 2 w i n d 3 w e b w a t c h e r 4 s h o d b o t 5 1 等 本文的研究重点是满足特定需求的w e b 页面挖掘 其思想是根据信息需求 从w c b 上挖掘得到满意的信息 实际上就是一个w c b 页面的分类挖掘 现在的分类系统大多是根据主题分类 其中很多均采用有监督的学习方法 通过训练集生成相关主题的特征词向量 根据w e b 页面与特征词向量的相关度 来判断是否与主题相关 特征词的选取是该方法中的一个关键问题 如向量中特 征词数量太大影响性能 若特征词数量太小则不能全面正确反映主题 因此特征 词的规模很难把握 同时其正确性很大程度上依赖于训练集 训练集不足时 特 征词的选取更加有失偏颇 再者这类基于特征词的分类挖掘方法大多数运用统计 学知识 其中最为基本的一点是认为词与词之间是相互独立的 这样就忽略了特 征词之间的关系 从而影响了分类的正确率 硕十学位论文 第一章绪论 目前 我们已有一个主要采用上述方法的w 曲页面分类挖掘系统 2 9 但是 经过一段时间的使用之后 发现也存在上述所提到的问题 当然 也可以采用基于自然语言的方法 3 0 来提高分类的精确度 它能处理 更为复杂的文本分类 然而这样的方法是相当昂贵的 而且对于w 曲页面的海 量数据 这样的方法显然不合适 如何有效的提高分类的精确度 成为了我们需要解决的一个问题 2 问题的解决方案 对于需要分类的主题 其用户往往是对该领域比较熟悉的人 对主题有比较 全面地了解 可以充分利用这个已有的知识对需要分类的主题进行描述 目前本 体的概念来解决知识共享和重用的问题 其中应用本体用来描述现实中一个较小 的主题 采用概念关系实例模型来表示 这里我们提出了基于本体的w e b 页面 分类挖掘的方法 在已有的知识基础上 进行有监督的学习 生成分类规则 从 而实现w 曲页面的分类 依照这种思路 我们建立了一个w e b 分类挖掘的模型 该模型中 根据定义的本体生成本体匹配的规则 对训练页面进行解析生成有结 构酡页面表示文件 并根据本体匹配规则对页面表示文件进行匹配 生成与本体 相关的数据 并且结合三种启发式算法来计算相关度向量 相关度向量组成训练 数据集 并利用决策树学习算法生成分类的决策树从而构建了分类规则 实现分 类 并对分类的结果进行评估 进一步模型改进 当然应用本体的构建依赖领域 知识 这是相对原有的方法需要的额外的开销 但是在此基础上的分类大大减少 了特 i 5 f 词选取对分类精度的影响 1 3 本文的工作和组织 在广泛参考和整理相关资料的基础上 本文研究了w 曲页面分类挖掘的方 法 同盱 针对目前一个已有的网页分类挖掘系统存在的问题 提出了一个提高 准确率的分类挖掘方法 我们实现了该方法的实验原型 并进行了相关的实验 本文的主要工作和创新之处 1 着重研究w e b 的页面分类挖掘方法 传统的w e b 页面分类方法是基于 主题特征词和统计学知识的 通过分析一个使用该方法的网页分类挖掘系统 指 出了该方法的局限性 在此基础上 提出了利用先验知识来提高分类准确率的方 法 并建立了一个基于本体的w c b 页面分类挖掘模型 2 自定义了一些r d f 描述元语 并对描述本体r i f 文件进行解析 生成 本体映射规则 从页面的内容和结构两个方面来进行页面解析 采用一致性匹配 推理匹配和上下文匹配方法 实现页面与本体间的匹配映射 利用已有的本体知 硕十学位论文第一章绪论 识 采用密度算法 期望值算法和集合算法对解析匹配后的页面进行相关度向量 的计算 采用有监督的学习算法来生成分类规则 完成分类 对分类的结果进行 评估 并能进一步的对模型修正 3 实现了该模型的原型系统 为了提高该模型的通用性和可扩展性 原型 系统中将本体解析 页面解析 本体匹配 相关度计算和学习评估都独立成模块 4 在原型系统上进行了相关实验 实验表明 该方法在训练集较小的情况 下也可以达到较高的分类精度 同时结合三种方法进行匹配和结合三种方法进行 相关度向量计算确实能提高分类的精度 并在相同条件下进行对比试验 分析两 种方法之异同 本文共分为六章 各章的内容如下 第一章简要介绍本论文的课题背景 研究目的和意义以及论文的工作和组 织 第二章综述了w e b 挖掘现状 着重研究w 曲页面分类挖掘的过程和传统 的方法 针对现有的一个基于传统方法的w 曲页面分类挖掘系统 分析了基于 特征词和统计学方法的局限性 提出了利用先验知识来提高分类的精度的方法 第三章本体和本体的相关知识 第四章利用本体知识 提出了一个基于本体的w e b 页面分类挖掘模型 力 求提高分类的精度 第五章建立实验原型系统 进行两方面的试验 第一 对该模型性能评估 第二 与已有的基于特征词主题分类挖掘系统的的对比试验 第六章总结和展望 硕士学位论文第二章基于主题特征词的w 曲页面分类挖掘 第二章基于主题特征词的w e b 页面分类挖掘 2 1 w e b 数据挖掘的定义 o r e ne t i o n i 在1 9 9 6 年首次提出了w c b 数据挖掘这一概念 7 w 曲数据挖掘 技术是用数据挖掘技术在w e b 页面和服务器中自动发现和提取有用信息 w c b 挖掘技术 涉及w e b 数据挖掘 语言学 信息学 机器学习 人工智能 统计 学等多个领域 w e b 挖掘的定义可以从数据挖掘的概念扩展而来 简单讲 w 曲 挖掘指从w e b 服务器上的数据文件中提取人们感兴趣的知识 w e b 挖掘可以对 文档的内容 可利用资源的使用以及资源之间的关系进行分析 w 曲是一个巨大的 广泛分布的 高度异构的 半结构化的 超文本 超媒 体的 相互联系并且不断进化的信息仓库 是一个巨大的文档累积的集合 包括 超链信息 访问及使用信息 大量的非结构化数据无法使用现有的数据库管理系 统来操纵和管理 其用户群体也表现出多样性的特点 这些都对信息系统的研究 人员提出新的挑战 虽然w e b 数据挖掘起源于数据挖掘 但是传统的数据挖掘大多是针对关系 数据库或数据仓库的 所处理的数据具有完整的结构 而w e b 包含各种类型的 数据 w e b 数据的非结构化这一显著特征使w 曲数据挖掘必然更加复杂 w e b 挖掘与数据挖掘相比还是有很多独特之处 主要表现在以下几个方面 第一 对有效的数据仓库和数据挖掘而言 w 曲似乎太庞大了 w e b 的数 据量以几百兆兆字节计算 而且还在迅速增长 这使得不可能构造 个数据仓库 来存储 集成w e b 上的所有数据 第二 w e b 页面的复杂性比任何传统的文本文档复杂多 w 曲页面缺乏同 一的结构 它的风格和内容很丰富 它没有结构化的数据 它的数据是半结构化 的或无结构的 w 曲可以看成是一个巨大的数字图书馆 然而 这 图书馆中的 大量文档并不根据任何有关的排列次序加以组织 它没有分类索引 更没有按标 题 作者 出版时间等的索引 在这样一个图书馆中搜索自己希望的信息是极具 挑战性的 第三 w e b 是一个动态性极强的信息源 w 曲不仅以极快的速度增长 而 且它的信息不断发生更新 股票市场 金融市场 新闻等不断在更新自己的内容 链接信息和访问记录也在频繁更新 硕十学位论文第二章基于主题特征词的v 灿页面分类挖搦 第四 w e b 上的信息只有很小的一部分是相关的或有用的 据说9 9 的w e b 信息对于9 9 的用户是无用的 虽然这样的数据不是很精确 但是一个人只是 关心w e b 上很小一部分信息确是事实 w e b 所包含的其余信息对用户来说是不 感兴趣的 而且会淹没在很多无用的信息中 w e b 挖掘可以将w e b 上的文档进行分类 寻找文档主题 汇总搜索结果 使用户在i n t e m e t 上查找信息更加全面准确 对w 曲站点的分析可以用于重新组 织w e b 站点结构 借助用户对浏览站点情况的分析 可以对分布式或并行w e b 服务器的页面布局进行改进 为用户提供个性化服务 帮助用户导航 2 2w e b 数据挖掘的分类 w c b 页面是i n t e r n e t 上储存和发布信息最普遍的载体 是世界上最大的信息 仓库之一 w 如上存髓的信息量巨大且缺乏结构化组织的规整性 随意地散布在 i n t e m e t 的各个角落 人们访问w e b 留下的日志也是海量数据 现今最流行的对 w 曲数据挖掘的分类p 堤根据挖掘的对象将其分为 w 幻内容挖掘 w 曲结构挖 掘 w e b 同志挖掘 w 曲内容的挖掘是从w e b 的文档中抽取知识 w e b 结构的 挖掘是从w e b 的结构中从站点的页面结构推导出知识 而w e b 日志挖掘是从 w e b 的服务器同志中发现用户的访问模式 分析w 曲站点的使用情况 以下是 w e b 挖掘分类层次图 翮 内容挖掘 f 结构挖搁lih 志挖掘 巢裂 鬃幽避 智能查询 信息过滤1 1 个性化 l 多层敷 w e b 查询f 代理 粪 e b 代理 i 据库 系统l 2 2 lw 曲内容挖掘 四2 w e b 挖掘分类层次嘤 w 曲内容挖掘是从w 曲页面内容及其描述中获取有用知识 w c b 页面通 常包含以下几种数据类型 文本 图像 音频 视频 元数据和超链接 也有些 如h t m l 页面所含的半结构化数据 但大多还是无结构的文本数据 因此 b 内容挖掘通常是指对网页上文本数据进行挖掘 包括网页内容挖掘和搜索结果挖 掘 硕 学位论文第二章基于主题特征词的w 曲页面分类挖掘 2 2 2w 曲结构挖掘 大多数的w c b 信息检索工具仅仅利用网页上的文本 忽视了包含在链接中 的有价值的信息 w 曲结构挖掘是针对链接信息这一重要的w e b 数据 试图发 现页面间超链的链接结构 基于超链的拓扑结构 w 曲结构挖掘可进行网页分类 总结网站和网页的结构 生成诸如网站间相似性 网站间关系的信息 2 2 3w e b 日志挖掘 w e b 同志数据源有w e b 服务器日志 代理服务器臼志 浏览器日志 用户 自定义p r o f i l e 文件 用户注册数据 客户端c o o k i e s 用户访问期间 事务 用户 查询 书签数据和鼠标移动点击的信息 通常w e b 同志挖掘可分为三个阶段 数据预处理 数据挖掘和对挖掘出的 模式进行分析 7j 数据预处理将用户访问网站留下的原始日志整理成事务数据 库 供数据挖掘阶段使用 数据挖掘阶段需要先将事务数据库整理成与一定挖掘 技术相适应的数据存储形式 再利用数据挖掘算法挖掘出有效知识 在挖掘出用 户模式后 需要对其确认并将其转换为人们可理解的知识 同时剔除无用模式 2 3 w e b 文本挖掘 基于w e b 页面的文本挖掘 t e x tm i n i n g 是w e b 内容挖掘的主要研究内容 也是本文的研究重点 w e b 文本挖掘可以对w 曲上大量页面集合的内容进行总 结 分类 聚类 关联分析等 2 8 2 3 1 文本总结 文本总结是指从页面中抽取关键信息 用简洁的形式对页面内容进行摘要或 解释 其目的是对文本信息进行浓缩 给出它的紧凑描述 这样 用户不需要浏 览全文就可以了解页面和页面集合的总体内容 文本总结在有些场合十分有用 例如 搜索引擎在向用户返回查询结果时 通常需要给出页面的摘要 2 3 2 文本分类 文本分类就是将文本集中的文本根据相关度正确地归放到某个类中 可以在 已有的数据的基础上学会一个分类函数或构造一个分类模型 即我们通常所说的 分类器c l a s s m e r 分类器一般分为训练和分类两个阶段 第一步建立分类模型 第二步使用模型进行分类 如图2 2 所示 硕十学位论文第二章基于主题特征词的w e b 页面分类挖捌 州分类算法分析训练数据 i 型兰苎兰r 12 查竺 1 翌兰兰i 测试数据用于评估分类的准确率 图2 2 分类模型 分类往往表现为一棵分类树 根据数据的值从树根开始搜索 沿着数据满足 的分支往上走 走到树叶就能确定类别 分类器的构造方法有统计方法 机器学习方法 神经网络方法等等 统计方 法包括贝叶斯法和非参数法 紧邻学习或基于事例的学习 机器学习方法包括 决策树法和规则归纳法 前者对应的表示为决策树或判别树 后者则一般为产生 式规则 神经网络方法主要是b p 算法 它的模型表示是前向反馈神经网络模型 由代表神经元的节点和代表联接权值的边组成的一种体系结构 b p 算法本质 上是一种非线性判别函数 2 3 3 文本聚类 文本聚类是一种典型的无监督的机器学习问题 聚类是把一组个体按照相似 性归成若干类别 即 物以类聚 它的目的是使得属于同一类别的个体之间的 距离尽可能的小 而不同类别上的个体问的距离尽可能的大 目前的文本聚类方 法大致可以分为层次凝聚法和平面划分法两种类型 2 3 4 关联规则 关联规则模式属于描述型模式 发现关联规则的算法属于无监督学习的方 法 关联的规则定义为 若x y 为项目集 且爿n l o 蕴涵式x jy 称为 关联规则 x y 分别称为关联规则的前提和结果 项目集x u y 的支持率称为关联规则x j y 的支持率定义为 s u p p o r t x s u p p o n x u 关联规则x y 的置信度定义为 c 獭懈 一y 等等圳 j 印p 0 玎l j 支持率和鬻信度是描述关联规则的两个重要概念 前者用于衡量关联规则在 整个数据集中的统计重要性 后者用于衡量关联规则的可信程度 通常用户只对 硕士学位论文第二章基丁 主题特征词的w 曲页面分类挖掘 支持率和置信度均高的关联规则感兴趣 也只有支持率和置信度均高的关联规则 力是有用的关联规则 2 4 基于主题特征词的w e b 文本分类挖掘 目前的w 曲文本分类挖掘方法很多 但大多数是采用基于主题特征词和统 计学的方法 这类方法的一般处理过程可以概括为图2 3 所示 2 4 1 w e b 数据预处理 图2 3 分类挖掘一般过程 一个网页包含的内容是丰富多彩的 除了正文文本外 还有广告 图像 声 音等多媒体信息 一个h t m l 文件包含许多h t 格式标记 如 这些丰富多彩的h t n l l 格式在精美地表现信 息的同时 也增加了页面的信息量 如果很好的利用这些标记就能为提取文本格 式和抽取信息提供帮助 w 曲数据预处理就是去掉w e b 页面其中与需要信息无关的其他内容 提取 对分类和过滤有用的信息 2 4 2 文本表示 在文本信息处理前 我们需要把它变成一种机器能够识别的格式 计算机并 不具备人的智能 当入在阅读文章时可以根据自己的理解能力对文章的内容加以 模糊识别 而计算机并不能 读 文章 所以需要找到一种能够被计算机处理的 表示方法 文本表示中包含页面解析过程 而对于中文页面的解析关键部分是分词 其 中包括英文取词和中文分词 英文取词的主要工作是剔除虚词和词的躯干化 硕十学位论文第二章基于主题特征词的w e b 页面分类挖掘 虚词的剔除比较简单 首先建立一个有序的虚词表 当从字符流里面提取到 一个词时 采用查询效率较高的二分查找来判断这个词是否在虚词表里 如果在 则丢掉 否则保存 而词的躯干化工作可以视为对一个单词删除固定形式的后缀 将其化为词根 的拼写形式 由于中文在词法 语法以及语义上均比英文复杂 因而中文的分词相对英文 取词而言要困难得多 在过去的十几年里 中文自动分词工作虽取得了很大成 绩 但是同实用的需要相比较 还是有一定的差距 需要进一步的研究 根据国 内的研究情况 目前中文分词算法可以分为三类 基于字符串匹配的分词方法 机 械分词 6 基于理解的分词方法 6 平口基于统计的分词方法1 2 9 1 在信息处理领域 页面的表示方法很多种 如 向量空间模型 v s m n g m m s 表示法和文档概念分类表示法 其中向量空间模型最为常见 向量空间模型 v e c t o rs p a c em o d e l 简记为v s m 将每一页面都映射为由 一组规范化正交词条向量生成的向量空间中的一个点 它是近年来应用比较多而 且效果较好的方法之一 其基本思想是用向量来表示文本 该模型以特征项作为 页面表示的基本单位 特征项可以是字 词或短语 在向量空间模型中文本文件是由特征项 乃 乃 乃 n 构成 对于每一 个特征项正 都根据其在页面中的重要程度赋予一定的权重彤 这样文本文件 就可以表示成一个特征向量 醪 假如目标文件为u 而未知文 件为y 则两个文件的相似度s i m 可通过两个文件的特征向量间的夹角来度量 央角越小说明未知文件与目标文件越相似 如果目标文件己 为某个领域的样本 文件 则未知文件y 与目标文件的相似度越高 未知文件就越符合该主题的要 求 在经典的空间向量模型中 特征项的权重 也即特征项对文件的贡献度 正比于该特征项在文件矿内的频度 反比于该特征项在样本文件u 中出现的频 度 这种项的权重计算的策略是 某个项在一个页面中出现的频次越高 其贡献 就越大 在页面集中出现的页面数较多 说明它区分页面属性的能力低 其贡献 要相应的减弱 2 4 3 特征提取 对于一些信息量很大的文本经过分词 其切分出来的词汇量是非常巨大的 如果用v s m 来表示 则向量空间的维数很高 增加了计算机的处理工作和空间 丌销 另一方面 并不是每个词对于w 曲页面分类与过滤都是有用的 一些通 用的 各个类别都普遍存在的词汇对w 曲网页分类与过滤的贡献小 在某一特 硕十学位论文第二章基于主题特征词的w 曲页面分类挖掘 定主题中出现的比重大而在其他主题中出现比重小的词汇对w e b 网页分类与过 滤的贡献大 因此需要进行页面特征项的选择工作 删除那些贡献量不是很大的 词汇 保留该主题的特征项的集合 因此在基本不影响分类结果的前提下 进行特征子集的选取 其一般方法是 构造一个评价函数 对特征集中的特征向量进行评估 然后从中选取评价较高的 的特征向量作为特征子集 常用的评价函数有互信息 2 4 1 m u t u a l i n f o r m a l i o n 信 息增益 i n f o m a t i o ng a i n r 5 1 交叉熵 c r o s se n t r o p y 犯6 1 和几率比 o d d sr a t i o s 等 介绍其中两种算法 假定w 是词汇 c 为主题的集合 c 为某一特定主题 d 代表文档集 d 为 某一篇文档 1 互信息 m u t u a l i n f o h n a t i o n 互信息表示两个变量间的相关性 对于词汇w 其互信息为 脚 c w 1 0 9 譬刍 其中p 向叫为主题c 中存在词汇w 的概率 当w 对于主题c 的贡献大的时候 埘 c w 0 当w 和主题c 不相关的时候 埘 c w o 在实际的应用中有两种方式 一种是对所有主题求平均值 另一种是求最大 值 a 打 w p c 埘 c w 埘一 w 2 理野 m c w 2 信息增益 i n f o m a t i o ng a i n 汉语信息熵 e n t r o p y 指的是汉语字或词的熵 表示汉语平均每个字或词所负 载的信息量 对于自然语言根据s h a l l l l o n m c m i l l a n b r e i m a n 定理 对于一个示 例集墨它的熵研卿计为 n1 p 口 1 0 9 一 p 口 l o gp 盯f f l p 口f l 1 其中哦为 的属性 信息增益是信息论中的一个重要概念 广泛应用于机器学习中 它表示页面 中包含某词汇时主题的平均信息量 它定义为某一词汇在页面中出现前后的信息 熵之差 硕十学位论文第二章基于主题特征词的w 曲页面分类挖掘 佑 w c 一h c lw 一 p c l o g p c p w p 0 1 w l o g p c l w p w p c l w l o g p c l w 差似一s c 焉揣m 岫意静 其中 d p 5 尸 c 以w f f j p 计 户 c p wj c 信息增益越大 词汇w 对w c b 分类与过滤的贡献就越大 2 4 4 分类和评估 在这里文本的分类 t e x tc l a s s m e r 也称之为主题的识别 就是将文本集d 中 的文本西币确地归放到一个或几个主题c l 中 主题的类别和数量可以预先确定 也可以不确定 根据是否预先确定主题的类别 可以分为有指导的分类和无指导 的分类 有指导的分类是指预先确定好要分类的主题 每个主题有一批正确分好类的 文本集 即训练 学习 样本 在进行分类的时候 将要分类的文本与每个主题类 进行匹配 确定它属于哪一个或几个主题 用c 表示第f 个主题 d 表示要分类 的文本 有指导的分类就是找到一个映射函数厂 将d 映射到一个或几个主题 即 一 g 在本系统里使用的是有指导的分类 无指导的分类就是事先不确定分类的主题 但是用户需要事先定义好要分类 的主题数或分类半径 在很多情况下 例如电子会议 由于系统对要处理的文本 所属的领域缺乏任何先验知识 只能通过无指导的学习方法形成各个主题类别 在8 0 年代 用来构建文本分类器主要的方法是基于知识工程 即手工构建 一个能进行分类决策的专家系统 它包括一些由人工定义的用来指导分类的规 则 规则的形式如 缎满足规则r m 8 月 主题c 与专家系统相似 基于规则的分类器也存在知识获取的瓶颈 即规则的制定 必须在领域专家的帮助下由知识工程师手工完成 如果主题集发生更改或分类器 移植到另外一个完全不同的领域 则援则必须重新制定 从9 0 年代丌始 随着信息存储技术和通信技术的迅猛发展 大量的文字信 息开始以计算机可读的形式存在并且其数量每天仍在急剧的增加 这一方面增加 了对快速自动的文本分类的迫切需求 另一方面为机器学习的文本分类方法准备 了充分的资源 在这种情况下基于机器学习的文本分类逐渐取代了基于知识工程 硕十学位论文第二章基于主题特征词的 b 页面分类挖掘 的方法成为文本分类的主流技术 机器学习方法通过学习主题c 的页面集的特征 属性来自动构造主题c 的分类器 这种方法无需维护规则 自学习能力强 基于 机器学习的自动分类方法在分类处理上已经取得了很好的成绩 提出了多种分类 器方法 如回归模型 最近邻分类 贝叶斯分类 决策树 指导规则与知识库 神经网 支撑向量机 决策委员会 2 9 等 下面介绍两种分类算法 1 k n n 分类算法 k 最近邻算法 1 1 k n n 算法即k n e a r e s t n e i 曲b o r 分类算法 它是著名的模式识别统计学方法 已经有四十年历史 是较好的文本分类算法之一 该算法的基本思想是 对于某 一需要进行分类的文本d 在训练文本集d 中 通过相似度找到与它最相似的七 个训练文本 这 个训练样本是这篇新文本的近邻 然后根据这七篇文本所属类 别判断新文本的主题类别 算法的描述如下 训练样本根据特征项集合重新用v s m 表示 新的文本分词用v s m 表示 从训练样本集里找到新文本最相似的k 个近邻 文本相似度的计算公式 二 m 巩 d j 2 了笋 帚一 j 矽0 刍 y l i 为文本中特征项的权重 为特征集的项数 给每 主题类评分 分值为该主题类的页面与新文本的相似度的和 分值的 计算公式 s c o r e d c s f m f d d c de 如果矶 c 则 矾 c l 否则为o 对主题类评分进行排序 将新文本分到分值最大的那个主题类 日 n 的一个缺点是计算量大 计算的复杂度随着训练样本数的增加而增加 假设系统的训练样本包括m 篇文本 个主题类 特征项为挖 则算法的复杂度 为o 册 仃州 解决的途径可以采用快速算法 1 其基本的思路是将样本分成 一些不相交的子集 并在子集的基础上进行搜索 2 n a i v eb a y e s 分类算法 朴素贝叶斯算法 朴素贝叶斯算法基于这样的假设 在给定的语境下 文本的属性是相互对立 的 尽管构成文本的各个属性不可能是相互独立的 然而在实际中 这个假设可 以指数级降低了构建贝叶斯网络的复杂性 而且在许多领域 朴素贝叶斯也表现 出相当的有效性和健壮性 1 0 假设4 为某一篇文档 用它的特征项表示为d 硝 硕士学位论文第二章基于主题特征词的w e b 页面分类挖掘 w c c q g 为主题类别 要计算西属于哪个主题类c 根 据贝叶颠分类法有 刚 掣 对文本进行分类 就是计算p 扬l 矗 的概率值 概率值最大的那个主题类就 是文本函所属的主题类 又因为在相同的环境下p d 的值是相同的 所以只需 计算p c p 瞄 ic 的值 p d ic p w l w 2 w n ic 根据假定 讲奶 既 各个属性w 间相 互对立的 于是 p d lc p w w w jc p w lc p w lc p h ic 兀p i c 使用l a p l a c e a i l 先验概率可以计算p 陋j 和p r w i 1 璺 v 矾 p 2 彳矿 p w 辱趟血尘 i 矿i 艺 v 反 其中分子加1 是为了数据的平滑 朴素贝叶斯算法的时间复杂度是d 忙哪 其中女是主题类别的数目 是特征项的数目 与训练样本的数目无关 分类模型质量评估方法与传统的数据挖掘方法相似 主要采用国际上广泛使 用的两个评估指标查全率和准确率综合考虑的方法 3 准确程度的参照物是通 过专家对思考判断后对文本的分类结果 这里假设人工分类完全正确 与人工分 类结果越相近 分类的准确程度就越高 查全率 r e c a l l 是模型分类相关页数与专家分类相关页数的比率 用数学公 式表示为 查全率c r e d 萼罢筹羹碧引景喜 蕞撼 准确率 p r e c i s i o n 是模型分类相关页数与模型分类得到的页数的比率 用数 学公式表示为 准椭m 撕垆鼍雾鬻嚣磊警 硕十学位论文第二章基于主题特征词的w e b 页面分类挖掘 2 5 一个已有w e b 页面分类数据挖掘系统 2 5 1系统介绍 目前我们已有的一个w e b 页面分类挖掘系统 2 9 1 是根掘前述基于主题特征 词的w e b 页面分类挖掘方法构建的 该系统分类模型如图2 4 所示 图2 4 已有系统的分类模型 该系统主要划分为以下功能模块 w c b 数据采集模块 h t m l 内容提取模块 分词模块 特征词选择模块 主题管理模块 训练 学习 模块 w e b 分类与过滤 模型评估模块等主要模块 其中主要的几个模块功能描述如下 1 1 w e b 数据采集 主要功能 从指定的网站地址采取 下载 网页 根据用户的配置 可以采用 两种方式采集网页数据 一种是采集指定网站的所有网页 另外一种是采集指定 网站指定深度的网页 在网站内搜索的时候 采用宽度优先搜索算法 即层次式 的搜索方法 在采集完本层网页后 再采集下一层的网页 有的网页可能从上次 采集以来一直没有更新过 为了不重复采集这些没有更新的网页 在系统旱使用 了 去重 策略 即只采集从上次采集后更新了的网页 2 h t m l 内容提取 由于w e b 页面是一个半结构化的数据结构 服务器在i n t e m e t 上提供的超文 本是用一种超级文本标记语言h t m l h y p e r l l e x tm a r k u pl a n g u a g e 开发编制的 h t m l 是一种嵌入式语言 通过在文本中嵌入各种标记 使普通文本具有超级文 本的功能 硕十学位论文 第二章基于主题特征词的w e b 页面分类挖掘 预处理时 并不考虑标记 在一个网页里保留那些对网页分类和过滤有用的 信息 包括文本标题和文本j 下文 w e b 数据预处理是过滤掉那些无用的信息 提 取文本标题和文本 e 文并以t x t 格式保留为纯文本格式 预处理过程如图2 5 所 示 图2 5 w e b 页面预处理 h t m l 编制的w e b 文本分为文本首部和文本正文两部分 一个w 曲文本的表 示如下 文本首部 文本正文 吲h t m l h t m l 内容提取就是提取文本首部和文本正文的内容 去掉一些无关的h t m l 标记问的内容和h 佣l 标记 3 分词 分词模块包括对英文的取词和中文的分词处理两部分 对于英文词的躯干化 工作采用了简单易用的p o r t e r 算法 对于中文分词采用了逆向最大机械分词和统 计分词相结合的方法 4 特征提取 在该系统中对于特征词的提取采用了信息增益算法 描述主要如下 初始情况下 每个主题特征项是训练样本中所有出现的词 计算每个词的互信息 按互信息从高到低排序 选取前面互信息最大的n 的词为该主题特征项 n 的取值为多少 目前没有 很好的理论指导 一般是根据试验和测试结果 最终确定n 的取值 硕十学位论文第二章基于主题特征词的 b 页面分类挖掘 重复以上步骤 直到所有的主题都处理完毕 求主题特征项的并集 5 主题管理 主题管理模块的主要功能是定制要分类和过滤的w 曲网页主题 配置每个 主题的训练 学习 页面集和测试页面集 在系统中主题按中国图书馆图书分类法 分为3 8 个主题类 这些主题类涉及了国民经济的各个领域 用户通过主题管理 模块 可以按照自己的爱好定制主题类别和删除那些自己不感兴趣的主题类别 训练和测试页面集支持t x t 文本和h t m l 两种格式文件 在配置训练和测试页面集 的时候 用户只要指定训练和测试页面集所在的目录或采纳系统默认的目录 6 分类和评估 根据训练页面集中的页面和具体的分类算法 通过训练 学习 可以得到具体 的分类模型数据 采用朴素贝叶斯算法 n a i v eb a y e s 得到的是各种先验概率 而 k n n 分类算法 k 最近邻算法 得到的是各个页面 类 的向量表示 2 5 2 系统分析 目前该系统已经在运行阶段 经过一段时间的使用后 我们发现 该系统主 要存在这样的几个问题 第一 每个主题需要的训练集页面数量大 当训练集页面数量较小时 特征 词的抽取存在问题 导致一些相关性极小的词也成为了特征词 从而使得分类得 到的页面中不相关的页面数量比较大 正确率很低 第二 需要的特征词数量大 当特征词数量小时 特征向量不能很好的描述 主题 是的分类后得到的页面中无关页面较多 而相关页面的数量却比实际少很 多 从而导致查全率和准确率都很低 但是当特征项数量很大 一般5 0 0 0 左右 则会使得维护量大 而且分类所需时间长 第三 当定义的主题较小 主题类数目很多时 查全率和准确率均不高 在 特征词的数目一定时 主题类越多 则平均每个主题占有的特征项就越少 少到 了一定程度就会对分类产生较大的影响 对主题类而言训练集少 影响了训练的 精度 导致平均分类测试性能下降 当然 经过对系统的进行进一步的分析 我们认为可以通过改进算法来提高 其分类的精度 例如 1 在预处理阶段 对于h t m l 页面不能一味的只是将所有 标记都去掉 仅留下纯文本 而是利用这些标记表明词的权重 比如像一些黑体 词 加粗的词会得到不同的权重值 2 采用几率比 0 d d sr a t i o s 算法 4 9 来提高特 征词的选取精度 3 在分类算法上也可以加以改进 利用统计算法时加入词的 权重 硕十学位论文第二章基 主题特征词的w e b 页面分类挖掘 但是总的来说 这样的分类挖掘方法在训练集数量不足时 很难获取到正确 的特征词集 并且总存在特征词的筛选不当的问题 因而对于精度要求高的对候 很难从根本上达到我们期望的查全率和正确率 4 6 l 4 7 对于某个较小的主题而苦 当训练集数目不足时其分类精度不高 如何达到 9 0 以上的查全率和准确率 成为我们考虑的关键 可以采用基于自然语言的方法 3 0 1 来提高分类的精确度 它能处理更为复杂 的文本分类 然而这样的方法是相当昂贵的 而且对于w e b 页面的海量数据 这样的方法显然不合适 我们需要寻求一种适当的方法 既避免了代价很高 同 时能够达到我们想要的精度 我们发现对某个主题单纯从训练集中抽取特征向量来表示该主题的方法总 是与需要这个分类的用户的要求有这样或那样的偏差 而往往这个用户对其应用 主题有一个比较好的理解 既然是己知的 就应该充分利用 当然这个知识对不 同的人而占 肯定有差别 但从目前提倡的个性化服务的角度来讲 这个知识肯 定是有益的 因此 在进行分类之前 我们将所需要分类的类别的相关已知知识 描述出来 再在这个知识的基础上进行分类 尽量避免训练集小和特征词选取不 当造成的问题 从而提高分类的准确率和查全率 对于某个主题的相关知识我们可以用概念来描述 这个概念可以由与该主题 相关的一组词来表达 但是这种表达存在一定的缺陷 那就是概念相对独立 彼 此之 自j 的关系不能很好的表示 而往往某个主题是好几个概念的集合 且相互之 间存在关联 如果要想比较全面的将知识的表述清楚 并且得到更好的通用性和可扩展 性 本体不失为一种好的方法 而且基于本体的方法在一些其他相似应用 5 4 5 0 中也得到了较好的结果 能够提高性能 在下一章中将进一步的讨论本体的相关知识 硕七学位论文第三章本体 第三章本体 本体论原是哲学的分支 研究客观事物存在的本质 它与认识论相对 认识 论研究人类知识的本质和来源 也就是说 本体论研究客观存在 认识论研究主 观认知 而本体的含义是形成现象的根本实体 常与 现象 相对 在人工智能领域 知识建模必须在知识库和a g e n t 行为 问题求解技能 和 环境 问题存在的领域 两个子系统之间建立联系 l 而长期以来 a i 的研究 者较为注重前一个子系统 而领域知识的表达依赖于特定的任务 这样做的好处 是只需要考虑相关的领域知识 但是 大规模的模型共享 系统集成 知识获取 和重用依赖于领域的知识结构分析 因此 进入九十年代以来 与任务独立 t a s k i n d e p e n d e n t 的知识库 本体 的价值被发现 并受到广泛关注 人们引 入本体来表达信息 从而使之成为知识 实现计算机与信息的交流 3 1 本体的定义 近十年来 本体的研究曰趋成熟 在各种文献中 尽管与本体相关的概念和 术语的用法并不完全一致 但是事实的使用约定已经出现 我们首先列出本体的几种比较有代表性的定义 然后对相关的概念做简要的 描述 本体 o n t o l o g y 的几个代表性定义 1 本体是对 概念化