（计算机应用技术专业论文）基于加权模糊概念格的模式匹配算法.pdf

摘要 摘 面 之 模式匹配是数据交换的重要组成 由于数据模型表达能力的欠缺 准确的语义信息只有模 式设计者才能真正理解 模式匹配自动实现历来都是一个难以解决的问题 现有的模式匹百己算 法在处理复杂匹配和同名异义字段的匹配等方面以及匹配的效率方面都存在一定的不足 使得 模式的匹配工作经常需要用户大量参与 成为数据交换应用中的瓶颈问题 针对模式匹配中存在的上述问题 本文主要研究了基于加权模糊概念格的模式匹配算法 研究内容及成果如下 1 研究了模式分类的策略 利用机器学习中重要算法贝叶斯学习法分析模式信息的语 义 并以此为基础提出名称分类算法 描述分类算法以及类型分类策略归类模式元素 2 研究了模式信息整合方法 通过形式概念分析法整合分类结果 元素类型信息以及 约束信息 并提出了基于矩阵分析的概念格快速构建算法 该算法通过对形式背景对应矩阵的 深入分析 找出该矩阵与形式概念之间的内在联系 从而使得算法在概念的搜索过程更有目的 性 减少了计算步骤 提高了搜索效率 实验结果表明 本文提出的概念格构造算法性能优于 s s p c g 及n e x t c i o s u r e 算法 3 研究了概念相似度的计算问题 在传统形式概念的基础上引入了权值及模糊值 提 出一种针对加权模糊概念格的相似度计算模型 4 基于上述模式分类的策略 模式整合方法以及相似度计算模型 提出基于加权模糊 概念格的模式匹配算法 在对初始模式信息归类后 将权值与模糊值引入传统形式概念分析法 整合归类信息 具体包括 创建加权模糊形式背景 获取蕴涵的概念 确立概念问偏序关系以 及生成加权模糊概念格 建立加权模糊概念格的相似计算模型 设定格式阈值 计算最终概念 之间的匹配度 获取模式元素之问的匹配关系 实验结果表明 基于加权模糊概念格的模式匹 配算法策略在问题规模大且复杂的情况下 能够有效获取匹配项 保证查准率与查全率 减少 后期人工筛选的工作量 关键词 模式匹配 形式概念分析 概念格 相似计算模型 a b s t r a c t t h es c h e m am a t c h i n gi sa ni m p o r t a n tp a r to fd a t ae x c h a n g e s t h ee x a c ts e m a n t i c so ft h es c h e m a c a n n o tb ef u l l ye x p r e s s e db yt h es c h e m ai t s e l fa n d c a no n l yb eu n d e r s t o o df u l l yb yt h ed e s i g n e r s t h e r e f o r e i ti sd i f f i c u l tt op r o d u c em a t c h e sa u t o m a t i c a l l ya n dm o r ee f f o r ti sr e q u i r e dt om a t c h s c h e m a sc o m p l e t e l y t h e r ea r es e v e r a l1 1 1 1 s o l v e dp r o b l e m si nc u r r e n tm a t c h i n ga l g o r i t h m s s u c ha s c o m p l i c a t e dm a p p i n g m a t c h i n gh o m o n y m i ce l e m e n t sa n dm a t c h i n ge f f i c i e n c y w h i c hb e c o m et h e b o t t l e c e c ki nd a t ae x c h a n g ea p p l i c a t i o n s f o rt h e s ep r o b l e m sm e t i o n e da b o v e t h es c h e m am a t c h i n gb a s e do nw e i g h t e df u z z yc o n c e p t l a t t i c ei ss t u d i e di nt h i sp a p e r t h er e s e a r c h e sa n da c h i e v e m e n t sa r ea sf o l l o w s 1 t h es c h e m ac l a s s i f i c a t i o ns t r a t r e g y i ss t u d i e d t h en a m ec l a s s i f i e ra n dt h e d e s c r i p t i o n c l a s s i f i e rw h i c ha r eb u i l to nt h en a i v eb a y e st e x tc l a s s i f i e ri sa p p l i e dt oc l a s s i f yt h en a m e sa n d d e s c r i p t i o n so ft h ee l e m e n t s 2 t h es c h e m ai n f o r m a t i o ni n t e g r a t i o nm e t h o di ss t u d i e d t h ef o r m a lc o n c e p ta n a l y s i s f c a i s i n t r o d u c e dt oi n t e g r e a t et h ec l a s s i f i e dr e s u l t sa sw e l la st y p em e s s a g e sa n dc o n s t r a i n st oi n c r e a s et h e e v i d e n c e w h a ti sm o r e c o n c e p t sg e n e r a t i o na l g o r i t h mb a s e do nm a t r i xa n a l y s i si sb r o u g h tu p t h e a l g o r i t h mf i n d st h er e l a t i o n s h i pb e t w e e nt h em a t r i xa n dt h ef o r m a lc o n c e p t sa n dm a k e st h es e a r c hf u r c o n c e p t sm o r ed i r e c t l yw h i c hr e d u c e st h ew a s t eo nc o m p u t i n ga n di m p r o v e st h ee f f i c i e n c y t h e r e s u l t ss h o wt h a tt h ea l g o r i t h mp e r f o r m sm u c hb e t t e rt h a ns s p c ga n dn e x t c i o s u r e 3 t h es m i l a r i t ym e a s u r e m e n tf o rt w oe l e m e n t si sa n a l y s i s e da n dan e ws i m i l a r i t ym e a s u r e m o d e lb a s e do nt h ew e i g h t e df u z z yc o n c e p tl a t t i c ei sb u i l t t h i sm o d e ls u p p l i e st h ew a yt oc a l c u l a t e t h ed e g r e eo fs i m i l a r i t yf o rf o r m a lc o n c e p ta n a l y s i sw h i c hi so p t i m i z e db yw e i g h ta n df u z z yv a l u e a n df a c i l i t a t e sa c q u i r i n gt h ef i n a lm a t c h i n gr e l a t i o n s 4 t h ea l g o t i t h mo fs c h e m am a t c h i n gb a s e d0 1 1w e i g h t e df u z z yc o n c e p tl a t t i c ei sd e s i g n e da n d i m p l e m e n t e do nt h eb a s i so ft h es c h e m ac l a s s i f i c a t i o ns t r a t r e g y t h es c h e m ai n f o r m a t i o ni n t e g r a t i o n m e t h o da n dt h es m i l a r i t ym e a s u r e m e n tm o d e l a f t e rt h ec l a s s i f i c a t i o no fi n i t i a ls c h e m ai n f o r m a t i o n t h ew e i g h ta n df u z z yv a l u e sa r ei n t r o d u c e dt ot r a d i t i o n a lf c at oc r e a t ew e i g h t e df u z z yf o r m a lc o n t e x l a c q u i r et h ec o n c e p t si n v o l v e di nt h ef o r m a lc o n t e x t f i g u r eo u tt h ep a r t i a lo r d e rb e t w e e nc o n c e p t sa n d c o n s t r u c tt h ec o n c e p tl a t t i c e a tl a s t as t r u c t u r a ls i m i l a r i t ym e a s u r em o d e li si n t r o d u c e dt oc a l c u l a t e t h ef i n a lm a t c h e s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t ef c a b a s e dm a t c h i n go u t p e r f o r m sd i r e c t m a t c h i n g w i t h o u tt h eb e n e f i to ff c a a n df i n d st h em a t c h i n ge l e m e n t se f f e c t i v e l yw h e nt h e m a t c h i n gt a s ki sc o m p l i c a t e da n dt h es c a l e i sl a r g e s a t i s f y st h et a r g e to fp r e c i s i o na n dr e c a l l r e d u c e st h eh u m a nw o r k l o a d k e y w o r d s s c h e m am a t c h i n g f o r m a lc o n c e p ta n a l y s i s c o n c e p tl a t t i c e s m a l i r i t ym e a s u r em o d e l h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人 已经发表或撰写过的研究成果 也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意 研究生签名 东南大学学位论文使用授权声明 东南大学 中国科学技术信息研究所 国家图书馆有权保留本人所送交学位论文 的复印件和电子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文档 的内容和纸质论文的内容相一致 除在保密期内的保密论文外 允许论文被查阅和借 阅 可以公布 包括刊登 论文的全部或部分内容 论文的公布 包括刊登 授权东 南大学研究生院办理 善猛 第l 章绪论 第1 章绪论 1 1 研究背景 信息化技术与通信网络飞速发展和高度融合的今天 信息化的水平已经成为衡量一个国家 和地区综合竞争力 生产力水平和发展潜力的重要标志 但是 很多信息系统就像一个个 信 息孤岛 相互间缺乏信息共享与交互 造成了大量的信息资源浪费 主要原因如下 1 各 个信息系统在网络环境下是分布的 它们很难获知其它信息系统的网络位置及其包含的数据信 息 发现对其有价值的信息和数据 2 各个信息系统往往使用不同的系统平台 互操作困难 3 各个信息系统使用不同的数据库管理系统 给数据库互访带来难度 4 各个信息系统 的语义描述能力不同 导致不同的信息系统难以理解其它系统中的信息 数据分析和处理困难 5 网络的复杂性及防火墙等原因 给网络环境下的数据传输带来难度 而上述5 点的主要 障碍就是模式匹配 模式匹配是数据交换的核心 所谓模式是通过结构联系的一系列元素的结合i l j 典型的模 式有 x m ls c h e m a 数据库模式 o n t o l o g y 等 模式匹配的任务是以两个模式s t 作为输入 产生匹配对 每个匹配对的一部分元素来自s 另一部分元素来自t 通过匹配表达式指出两 部分元素是如何关联 匹配集是匹配对的集合 模式匹配中还会涉及到源模式与目标模式元素 之间的1 对1 l 对n n 对l n 对n 的匹配 这个称为匹配势 根据匹配依据的内容 模式匹配算法包括以下6 类 1 实例级 匹配的依据是实例 算法分析实例数据的内容 借助语言学的技术 对数据组合 分割 或者对某些词频率进行统 计等 以此为基础进行数据挖掘 寻找匹配依据 2 模式 s c h e m a 级 匹配的依据是模式 s c h e m a 如 x m ls c h e m a 数据库模式 o n t o l o g ys c h e m a 等 信息 算法主要分析模式的 相关信息如模式元素名称 数据类型 数据描述以及模式的结构方面等 3 元素级 匹配的 依据是元素 分析局部数据特征 如属性等 4 结构级 匹配的依据是结构 算法分析模式 数据组织结构的特征 5 语言级 利用基于语言学的相关知识如分析元素名称的同义词 同 一范围或同一概念领域的词 需要借助字典 分析来自同一命名空间的元素名称 对元素名 称进行规范性处理 分析元素名称或描述的公共字符串 读音 编辑距离等特性 6 约束级 借助主外键约束等信息进行算法设计 模式匹配在许多应用中都起着关键作用 如数据仓库中的数据抽取过程需要将数据源的数 据按仓库的格式转换 电子商务信息交换的处理中的异构消息的映射 以及数据集成中全局视 图的构建 由于准确的语义信息不能在模式本身中完全表达 只有模式设计者才能真正掌握 所以模 式匹配的自动实现是一个难以解决的问题 使得模式的匹配工作经常要用户大量参与 成为数 据交换的应用中的瓶颈问题 一个高效的模式匹配算法需要一系列的基础技术的组合 包括综 合考虑语言学相关知识 数据类型的内在关联 数据实例间的关系以及领域知识等等 本文主 要研究的模式匹配算法分别借助了模式级 结构级以及语言级三方面信息 解决数据库模式之 东南大 硕一 j 学位论文 问语义的自动匹配 1 2 研究现状 针对不同的技术环境 应用场景和用户需求 国内外学者们提出了不同的解决方案 目前 模式匹配主要有基于模式内部信息的模式匹配和基于大规模数据以及背景知识的模式匹配等 两类 基于待匹配模式内部信息的模式匹配主要有c l i o 法 2 1 s i m i l a r i t yf l o o d i n g 法 3 1 c u p i d l 4 1 p r o b a b i l i s t i cl o g i c 澍5 1 c o n t e x t u a ls c h e m am a t c h i n 9 1 6 1 和基于字典的匹配方 法 7 1 等 其优点在于 整合模式自身信息 如深入挖掘字段名 描述信息等以获取模式匹配关系 其局限性在于模式 自身携带语义不完备 基于大规模数据以及背景知识的模式匹配主要有 s e m i n t 法1 引 d u p l i c a t e s 法 9 1 m u t u a le n h a n c e m e n t 法1 1 0 和c o r p u s 法 1 u 等 该类方法的优点在于能通过对数据实例的挖 掘或者以往匹配结果的学习 获取关于模式更多的信息 但该类算法往往不具备通用性 并且 大规模的学习数据较难获取 上述的模式匹配的研究在一定程度上解决了模式的自动匹配问题 但在实际应用中还存在 以下几点问题 1 复杂匹配的处理 复杂匹配是指1 n n l n n 的匹配 复杂匹配是模式匹配 中的难点问题 模式信息如果处理不当将会成为干扰信息 直接影响正确匹配对的生成 算法 主要表现为查全率较低 例如对于s i d 一f i r s t n a m e l a s t n a m e 一n i c k n a m e 和t i d n a m e d i s p l a y n a m e 正确的匹配关系应为 s i d f n i n n n t i d f n l n 加 但在不完全信息挖掘的情 况下 匹配算法很可能不能区分各字段名 从而不能找出匹配关系或者找出类似l a s t n a m e d i s p l a y n a m e 的错误关系 2 同名异义的元素匹配 即元素的名称相同但语义信息相异 例如模式s 有t y p e 字段 模式t 中具有b p e c a t e g o r y 字段 s 中的t y p e 与t 中的c a t e g o r y 均用整型量来描述用户所 提交文本的分类 t 中的t y p e 表示用户所提交文本的风格 如果不考虑完整的语义以及逻辑信 息 很可能就直接将s 中的t y p e 与t 中的t y p e 直接匹配 算法在该项指标的欠缺主要表现为 查准率较低 3 匹配效率 如果待匹配模式的元素数 属性数较少则算法具有较好的效率及质量 实际应用在元素及属性的数目都很大的情况下 效率及质量都有所下降 针对出现的这些问题 有必要进行新算法的研究工作从而有效解决上述难题 1 3 研究目标与内容 本文主要研究数据库模式的匹配问题 研究目标是 设计基于加权模糊概念格的数据库模 式匹配算法 在算法中通过朴素贝叶斯文本分类算法对模式基本信息归类以增加字段匹配的依 据 通过形式概念分析整合归类阶段的输出结果 并构建加权模糊概念格 最后基于加权模糊 概念格计算概念之间的匹配度从而得出最终的匹配结果 实现模式的自动匹配 具体如下 1 提出名称分类算法以及描述分类算法分类模式元素 在贝叶斯文本分类算法的基础上 提出名称分类算法以及描述分类算法 分别根据元素名 称以及元素描述将目标模式元素与相应的源模式元索归类 并提供评估值 作为后续的匹配度 计算依据 2 提出一种基于矩阵分析的概念格快速构建算法 2 第l 章绪论 概念格的构建是形式概念分析的重要结果 概念格的构造效率始终是人们关注的问题 本 论文提出一种基于矩阵分析的概念格快速构建算法 c o n c e p t sg e n e r a t i o na l g o r i t h mb a s e do n m a t r i x a n a l y s i s c g m a 通过引入权值和模糊的概念 使得 在形式概念分析阶段能够从加权 模糊形式上下文的输入中快速构建产生出加权模糊概念格 3 提出一种针对加权模糊概念格的相似度计算模型 本文在d es o u z a 与d a v i s 相似计算模型的基础上提出针对加权模糊概念格的相似计算模 型 用于计算加权模糊概念格中概念之间的相似度 4 提出基于加权模糊概念格的模式匹配算法 本文提出的基于加权模糊概念格的模式匹配算法 s c h e m am a t c h i n gb a s e do nw e i g h t e d f u z z yc o n c e p tl a t t i c e s m w f c l 一方面对模式信息进行深挖掘 通过获取到丰富的语义信 息来增加匹配的精度 另一方面综合考虑并整合模式各方面的信息 如结构性信息 约束信息 等并进行整合 该算法主要解决数据库模式的匹配问题 采用朴素贝叶斯分类算法对数据库模 式中的字段元素的名称及描述信息预分类 通过形式概念分析来整合预分类结果 主外键信息 及类型信息 并引入权重 生成加权模糊概念格 最后在加权模糊概念格的基础上利用加权模 糊概念格相似计算模型计算最终匹配结果 算法以源数据库及目标数据库模式的x m l 文档为 输入参数 以两模式元素问匹配关系的x m l 文档为输出 1 4 相关知识 1 4 1 贝叶斯学习 机器学习的中心问题是概念学习 概念学习是指从有关某个布尔函数的输入输出训练样例 中推断出该布尔函数 1 2 1 布尔函数就是待学习的概念 称为目标概念记为c 一般来说 c 可 以是定义在训练样例集 实例集 x 上的任意布尔函数 表示为c x 一 o 1 每个训练样例 为x 中的一个实例x 它的目标概念值为c z x l f c x l 的训练样例被称为正例 对于 c x 0 的实例为反例 符号d 表示训练样例的集合 一旦给定目标概念c 的训练样例集 概念学习面临的问题就是假设和估计c 使用符号片 来表示所有可能的假设的集合 这个集合是为确定目标概念所考虑的范围 通常 按设计者所 选择的假设表示而定 日中每个假设表示x 上定义的布尔函数 即h x o 1 机器学习 的口标就是寻找一个假设h 使对于x 中所有工 办o c x 贝叶斯学习算法是机器学习算法中的重要方法 它基于如下的假定 1 2 待考查的量遵循某 概率分布 且可根据这些概率及已观察到的数据进行推理 以做出最优的决策 朴素贝叶斯学 习器是贝叶斯学习方法中实用性比较高的学习器 通过详细研究并比较了朴素贝叶斯学习器和 其他学习算法 包括决策树和神经网络 后 发现 朴素贝叶斯分类器在多数情况下与其他学 习算法性能相当 而在文本分类的学习问题 朴素贝叶斯学习器是最有效的算法之 1 1 2 l 3 东南大学硕 土学位论义 本文在朴素贝叶斯文本分类算法的基础上分别设计出名称分类算法以及描述分类算法 对 源模式及目标模式的元素名称及元素描述进行初始分类 并计算出相似概率 作为初始的分类 依据 以做进一步的分析 1 4 2 形式概念分析与概念格 形式概念分析 f o r m a lc o n c e p ta n a l y s i s f c a 1 3 1 4 1 是一项基于概念格理论以及命题演 算的数据分析方法 适用于通过形式上下文 也称为形式背景 进行信息整合 并进行形式化 描述 已经被应用到许多领域如软件工程 知识发现 策略分析和心理学等 概念格 或g a l i o i s 格 是形式概念分析理论中的一种核心数据结构 概念格的每个结点是 一个形式概念 由两部分组成 外延 即概念覆盖的实例 内涵 即概念的描述 实例的共同 属性特征 概念格通过结构化的方式抽象出人类思维中的概念 通常概念格通过h a s s e 图展现 概念之间的泛化与特化偏序关系 每个概念以结点表示 如果概念a 在概念b 之上且二者有直 线关联 则称概念a 是概念b 的泛化 即概念a 仅具有概念b 的部分属性 对于图1 所示概 念格 概念l 为概念2 概念3 概念4 的泛化 概念2 概念3 概念4 是概念l 的特化 图 中4 0 2 3 b 表示概念4 具有外延0 2 3 具有内涵b 3 1 2 c 6 2 b e 图l 概念格的h a s s e 图 形式概念分析的相关定义如下 定义l 设x 为所有对象的集合 y 为所有属性的集合 形式背景是映射 x 一 o 1 如果对象x x 具有属性y y 贝j jf x y l 否则厂 五y o 一个包含对象集 l 2 3 4 5 属性集 口 b c d 的形式背景 可用表l 表示 表l 形式背景的表示 定义 2 设 为xx y 上的形式背景 对于x s x 则 c x j r l f x y l v x x 表示x 中全体对象所共有的属性集 定义3 设厂为x 上的形式背景 对于j y 贝i jc r x x i 厂 x y l v yey 4 第l 章绪论 表示同时具有j 中所有属性的对象集 定义4 设 为x j 上的形式背景 x x y 如果x c y 且y c x 则称 x 为f 上的形式概念 x 分别称为形式概念 x y 的外延和内涵 以 r 表示 x 上形式背景f 的所有形式概念集 定义5 设 为x x y 上的形式背景 如果 五 置 e 是厂的两个形式概念 其中 表示偏序关系 规定 x x 2 营 x x x e 艺 誓 x i x 艺 称 x 为 x 2 艺 的子概念 置 艺 为 一 i 的超概念 显然 关系 是集合矗 上的一个偏序关系t 它可诱导出矗 r 上的一个格结构 可以证明 它是一个完备格 有关格结构与完备格证明见 1 5 相应的上确界与下确界定义为 卜c c 拦计口 g 口 c c 其中 一 r 是指标集 该完备格称为形式背景 的概念格 在无歧义情况下仍然 记为矗 本文在传统的形式概念分析以及概念格的基础上 针对形式背景中属性重要性的不同 引 入权值w o sw 1 表示属性的重要程度 同时 为了整合朴素贝叶斯分类算法相似度 将 传统的针对标准形式背景 或称为单值背景 的概念格扩展为模糊概念格 形成本文的加权模 糊概念格 以便整合更多的匹配依据并最大限度的减少有效信息的丧失 1 4 3 相似计算 基于几何学的相似计算模型是相似计算的一类重要模型 该类模型将对象问相似性定义为 各对象属性空间之间的距离 属性空间是相似性计算的一种标准衡量空间 1 6 1 标准衡量空问是 相似计算依据的通称 是指利用一些对象在感官或心理上的描述性名词来计算对象之间的距 离 在这里 属性空间专指一般意义上的名称属性空间 旧 基于几何学的基本相似计算模型是通过先验相似性d 以及后验相似性 之间的关系来定 义1 1 刀 若a b 分别是待计算对象口 6 在属性空间上的表示 通常以坐标点d 彳 b 来形式 化表达a b 在属性空间上的距离 1 8 1 9 1 称为对象口 b 的先验相似性 定义 f a 召 g d a 口 1 3 为对象a b 的后验相似性 其中g 为某合适的单调非递减函数并满足以下条件 1 自相似 d a 彳 d b 口 2 最低限度 d a 曰 d a 彳 3 对称 d a 曰 d b 彳 4 三角定理 d a 曰 d b c d 彳 c 5 东南大学硕 l 学位论殳 t v e r s k y 与心锄乞扩川证明如果上述条件被满足并且先验相似性是属性空问上的直线距离 则d 是m i n k o w s k i 距离 即 厂1 三 d p a b l 4 一置 9i 4 l j 其中a 4 a n b e 氐j p 0 p 是标识函数特征的常量 通过对基于几何学的相似计算模型的调整以及对函数条件的修改 可以衍生出多种不同的 相似计算模型 一般来说 相似度计算模型可分为两类 2 q 连续度量空问模型以及基于集合的 匹配模型 前者的例子是s h e p a r d 模型 1 6 1 它是基于概率分布的 后者 又可以分为基于几何 学 基于变形 基于特征以及基于联盟的模型 基于几何学的模型是指利用代表两个实体的特 征向量 通过l 或0 来表示实体具有某一特征或不具备某一特征 的距离 通过n 维空间计算 得来 来评估相似度 基于变形的模型是基于使两个实体相等而需要做出的变形的次数 如 d n a 序列a c c g 需要两次变形才能变成a c g a 基于特征的模型 即考虑了共有的属性 也 考虑了各自独特的属性 典型的例子就是t v e r s k y 的对比模型 2 2 1 根据模型中利用的度量法的 数目 相似度计算模型还可分为单一模型与组合模型f 2 3 1 组合模型是指相似度的计算结果根据 两个或两个以上度量法综合得出 单一模型包括j a c c a r dc o e f f i c i e n t 模型及c o s i n em e a s u r e 模型 等 后者包括了m u l t i w e i g h t e dm e a s u r e 模型 2 4 1 s i m i l a r i t yf l o o d i n g 模型 3 j 以及混合计算模型等 混合计算模型可以是基于语言学的计算模型与结构性相似计算模型的组合1 2 5 1 或者基于特征的 计算模型与结构性相似计算模型的组合 2 6 1 5 论文主要创新点 1 提出名称分类算法 描述分类算法以及类型分类策略归类模式元素 2 提出了针对加权模糊形式上下文的加权模糊概念格的快速构建算法 该算法以形式 上下文与其中蕴含的概念的关系为基础进行设计 运行结果表明 在一定量数据规模下算法执 行效率优于目前的概念格构建算法 3 提出针对加权模糊概念格的相似计算模型 在现有相似计算模型的基础之上 研究 加权模糊概念格特征 设计新的针对加权模糊概念格的相似计算模型 4 提出面向数据库模式匹配的新算法 该算法深入挖掘模式的语义信息及结构信息 并利用形式概念分析法来整合 引入的权重因子及模糊因子最大限度的防止算法处理过程中有 效信息的流失 实验结果表明 本文提出的匹配算法在在解决复杂匹配和同名异义的问题上和 效率问题上有所突破 提高了匹配的查准率与查全率 1 6 论文组织结构 本文首先分析了模式匹配的研究背景及现状 针对现有方案的不足 设计并实现了一种基 于加权模糊概念格的模式匹配方案 在方案的设计中提出了概念格的快速构建算法 并提出以 该加权模糊概念格为研究对象的相似计算模型 论文的组织结构如下所示 6 第l 章绪论 第l 章绪论 概述本文的研究背景及研究现状 分析现有方案中存在的不足 简要介绍 本文的研究目标 内容及创新点 第2 章模工弋信息分类策略 介绍模式信息分类相关知识背景 设计模式信息分类策略 名称分类算法 描述分类算法以及类型分类策略 第3 章模式信息整合方法 介绍模式信息整合相关知识背景 提出基于加权模糊概念格 的模式信息整合方法 并设计了一种快速构建概念格的算法 第4 章匹配度的相似计算模型 介绍相似计算模型相关知识 提出新的基于加权模糊概 念格的相似计算模型 第5 章基于加权模糊概念格的模式匹配算法 详细介绍了s m w f c l 算法的执行步骤 并 通过与其他方案的比较评估本算法性能 第6 章总结与展望 对本文进行总结 并指出了本文待完善之处及今后的研究方向 7 东南大学硕f j 学位论义 第2 章模式信息分类策略 对模式信息分类是模式匹配的第一步 根据名称 描述以及类型分别对模式元素进行分类 将模式的每个元素定义为一个类别 分别计算目标模式各元素隶属各源模式元素的隶属度 若 隶属度大于某阈值 则将该目标模式与对应的源模式元素归为一类 同时保留其隶属度值 以 备后用 模式信息分类涉及名称分类算法 描述分类算法以及类型分类策略 其中 名称分类 算法及描述分类算法基于文献 2 7 q b 提出的朴素贝叶斯文本分类法 类型分类策略以通用数据 库所定义的类型为对象分类 朴素贝叶斯文本分类法是贝叶斯分类法的典型应用 贝叶斯分类 法是机器学习中一种直接操作概率的学习方法 本章首先介绍了机器学习中贝叶斯分类法的原 理 贝叶斯法则 然后介绍了朴素贝叶斯分类法及其在文本分类中的应用 最后阐述了在朴素贝 叶斯文本分类法基础上的模式信息分类方法 2 1 相关概念 机器学习中 我们的主要问题是解决在给定的训练数据d 时 确定假设空问日中的最佳假 设 所谓最佳假设 一种方法是把它定义为在给定的数据d 以及 中不同假设的先验概率的 有关知识下的最可能假设 贝叶斯理论提供了一种直接计算这种可能性的方法 更精准的讲 贝叶斯法则提供了一种计算假设概率的方法 它基于假设的先验概率 给定假设下观察到不同 数据的概率以及观察到的数据本身 尸 办 表示在没有训练数据前假设h 拥有的初始概率 被称为h 的先验概率 p r i o r p r o b a b i l i t y 它反映了我们所拥有的关于h 是一正确假设的机会的背景知识 如果该先验知识 缺失 那么可以简单地将每个候选假设赋予相同的先验概率 尸 d 代表将要观察到训练数据d 的先验概率 即在没有确定某一假设成立时d 的概率 p di 办 代表假设h 成立的情况下观察到数据d 的概率 在机器学习的问题中 我们感兴趣的是p hj d 即给定训练数据d 时h 成立的概率 p hl 功称为h 的后验概率 p o s t e r i o rp r o b a b i l i t y 因为它反映了在看到训练数据d 后h 成立的 置信度 注意 后验概率p hld 反映了训练数据d 的影响 相反 先验概率尸 是独立于d 的 贝叶斯法则是贝叶斯学习方法的基础 以为因为它提供了从先验概率尸 办 以及尸 d 和 p d l 办 计算后验概率p h l d 的方法 贝叶斯公式 砌 等铲 从直观上来看 p h ld 随着p h 和p d ih 的增长而增长 同时也可以看出p h id 随 着p d 的增加而减少 这是很合理的 因为如果d 独立于h 时被观察剑的可能性越大 那么d 对h 的支持度越小 在许多学习场景中 概念学习考虑候选假设集合 并在其中寻找给定数据d 时可能性最大 第2 章模式信息分类方法 的假设h h 如果存在多个这样的假设时选择兵一 这样的具有最大n 7 能性的假设被称为极 大后验假设 确定极大后验假设的方法是用贝叶斯公式计算每个候选假设的后验概率 更精准 的说 当下式成立的时候 称 为m a p 假设 m a x p h l d 月e 盯 m 毅 幽垒出生 拓片 尸 d m a x p d i h p h 6 公式6 中去掉了p d 因为它是不依赖于h 的常量 在某些情况下 可假定h 中每个假设有相同的先验概率 即对h 中任意囊和勺 尸 囊 尸 勺 这时把等式进一步简化 只考虑p dj 来寻找极大可能假设 p d i 办 常被称为给 定h 时数据d 的似然度 而使p d l 矗 最大的假设被称为极大似然假设 m a x i m u m l i k e l i h o o d m l 假设 m a xp dh 与机器学 3 问题相结合后 我们把数据d 称为某目标函数的训练样例 而把日称为候选 目标函数空间 2 2 朴素贝叶斯分类 朴素贝叶斯分类器是贝叶斯学习方法中实用性比较很高的学 3 器 在朴素贝叶斯应用的学 习任务中 每个实例x 由属性值的合取来描述 目标函数 曲从各类别集合y 中取值 提供学 习器一些关于目标函数的i i l 练样例以及待学习的目标实例 以属性的 l 维特征向量表示 然后要求预测新实例所属的分类 贝叶斯方法的新实例分类目标是在给定描述实例的特征向量 下 得到最可能的 目标值 m a x e v i 口i 口 q 航 帮 掣 m a xp a a 2 巳l 尸 7 现在需要获取公式7 中p q a 2 a nl p 两项的值 估计每个p 很容易 只要 计算每个分类 出现在训练数据中的频率就可以 同时 朴索贝叶斯分类器给予一个简单的假 定 在给定分类时属性值之间相互条件独立 该假定说明在给定实例的分类的情况下 观察到 东南大学硕上学位论文 q 以的联合概率等于每个单独属性的概率的乘积 e a 口 ql n p qi f 将其代入公式7 得 v m a x 尸 耳p 口j l 其中 表示朴素贝叶斯分类器的输出的分类 2 3 朴素贝叶斯分类在文本分类中的应用 8 9 所谓文本分类问题是指 考虑问题空间x 包含j 所有的文本文档 即任葸长度的所有司能 的单词和标点字符串 给定某未知目标函数厂 的一组训练样例 厂 x 的取值来自于某有限 集合v 此任务是从训练样例中学习 以预测后续文本文档的目标值 利用朴素贝叶斯分类原 理 文献1 2 8 给出了贝叶斯文本分类算法l n b t e x a r n p l e c 与c n b t d o c 该算法基于以下两 个假定 1 一个位置上出现某单词的概率独立于另外一个位置出现任何单词的概率 2 一 个特定的单词出现的概率与单词所在位置无关 l n b t e x a m p l e c 与c n b t o o c 算法描述如 下 l e a r n n a i v e b a y e s t e x t e x a m p l e v 收集e x a m p l e 中所有的单词 标点符号以及其它记号 v o c a b u l a r y 在e x a m p l e 中任意文本文档中出现的所有单词及其记号的集合 计算所需要的概率项尸 和尸 i 对y 中每个目标值 d o c s 卜e x a m p l e s 中目标值为v 的文档子集 p 卜阐 d o c s t e x t y 6d o c s 中所有成员连接起来建立的单个文档 刀卜et e x t 中不同单词位置的总数 对v o c a b u l a r y 中每个单词m 体卜单词 i e e t e x t 中的次数 1 0 第2 章模式亿息分类方法 p i 卜可丽n k 网1 停止 算法时间复杂度为d 旷i l 场c 曲甜肠秒i e x a m p l e 为一组文本文档以及它们的目标值 类 别 矿为所有可能目标值的集合 此函数作用是学习概率项尸 叱iv j 它描述了从类别 中 的一个文档中随机抽取的一个单词为英文单词 的概率 该函数也学习类别的先验概率 尸 c l a s s i f l l n a i v e b a y e s t e x t d o e p o s i t i o n4 在d o e 中所有单词位置 它包含能在v o c a b u l a r y 中找到的记号 返回 2 蛩p 旭曼尸 口 停止 对文档d o e 返回其估计的目标值 谚代表在d o e 中的第i 个位置上出现的单词 在新文档中出现但不在训练集的文档中出现的任何单词将被简单的忽略 2 4 模式匹配中的信息分类方法设计 本节介绍模式信息分类的名称分类算法 描述分类算法以及类型分类策略 2 4 1 名称分类算法 以朴素贝叶斯学习文本分类算法的核心算法l n b t e x a m p l e c 与c n b t d o e 为基础 提出 名称分类算法 算法思想如下 1 采用分隔符 如 f i r s t n a m e 分割成 f i r s t n a m e 和字段表示 如 d e p n o 分割 后变成 d e pn o 等两种策略对字段分割 2 将分割后得到的单词进行扩展 即根据应用的领域找出单词对应的同义词 形成单词 集 3 以每个源模式字段为一个类别 对该字段单词集中每个单词进行露 段 k 为解析字 符数 即解析后每个子段具有k 个字符 解析 解析后的数据作为该字段类别的训练样例 若 七取值为3 则单词 a u t h o r 解析后的数据为 a u tu t h t h o h o r 不同七值对算法的评价指标 运行时间和归类结果的平均估计概率 产生不同的影响 为 确定合适的k 值 考察k 分别为1 2 3 4 5 的情况 七值对算法评价指标影响的实验结果 如表2 所示 由表2 可以看到 文本分类算法在切割长度为3 的情况下 既可维持较高的估计概率 也 东南大学硕 i 位论文 具备较快的运行时间 所以合适的k 值为3 表2k 值对朴素贝叶斯文本分类算法的影响 4 将目标模式字段3 段解析后的文本作为待分类数据 送入已经训练好的朴素贝叶斯 学习器 计算出该目标字段属于各源字段类别的估计概率 各源模式字段以及按概率大小降序 排列目标字段 共同组成一类 只卜 f l m 其中m 为源模式中字段的数 目 刀为目标模式字段的数目 本文提出的名称分类算法具体描述如下 1 根据源模式字段名称 建立初始类别 构建训练样例并送入学习器 s o u r c e n a m e j 烈a l y s i s s c h e m a s s o u r c e e l e s e t 卜源模式中的所有字段集 用4 源模式字段数 k4 3 类别集合 c 卜a s a m p l e s 卜o 按字段命名特征选取分割策略分割s o u r c e e l e s e t 中每个字段乞 i 1 m 按选取的 策略切割q 后得到的所有单词形成集合s o u r c e e l e l n i s e t 对s o u r c e e l e s e t 中每个字段q f l m q4 p 文本集z 卜o c 卜c u q 扩展s o u r c e e l e l n i s e t j 中每个单词的同义词 并加入s o u r c e e l e l n i s e t 形成新集合 s o u r c e e l e s e t j s o u r c e e l e s e t 中的每个单词h t 1 s o u r c e e l e s e t i 进行七段解析 s a m p l e s 卜s a m p l e su 类别q 与文本集z 的匹配关系 t e x t 卜单词w 解析后的文本字符串 巧卜z u t e x t 调用朴素贝叶斯文本文类算法l n b t s a m p l e s c 学习样例 停止 2 根据目标模式字段描述建立待分类样例 t a r g e 飞奠a m e a n a l y s i s s c h e m a t t