《基于形式概念分析的模式匹配算法.pdf》由会员分享，可在线阅读，更多相关《基于形式概念分析的模式匹配算法.pdf（6页珍藏版）》请在三一文库上搜索。
1、第3 9卷第 1期 2 0 0 9年 1月 东 南 大 学 学 报 (自然科学版) J OU R NA L O F S OU T HE AS T U NI VE R S I T Y ( N a t u r a l S c i e n c e E d i t i o n ) Vo 1 3 9 No1 J a n 2 0 0 9 基于形式概念分析 的模式 匹配算法 王 峰 李小平 王 茜 ( 东南大学计算机科学与工程学院 ， 南京 2 1 0 0 9 6 ) ( 东南大学计算机网络与信息集成教育部重点实验室， 南京 2 1 0 0 9 6 ) 摘要 ： 提 出了一种基于形式概念分析的模式匹配的 F
2、 C AB S M 方法， 该方法由3部分组成： 首先， 以朴素贝叶斯文本分类算法为基础设计名称分类算法及描述分类算法， 分类 目标模式与待匹配 模式的元素名以及元素描述， 为模式间元素的匹配提供初始依据 其次， 利用形式概念分析技术 整合分类结果、 元素类型信息以及约束信息， 提高 匹配精度 该 阶段为待整合信息创建形 式上下 文、 获取形式上下文中蕴涵的概念 、 确立概念问偏序关系及构建概念格 最后， 以第二阶段的概念 格为计算依据， 引入基于结构的相似评估模型来计算出最终的匹配结果 实验表明， 基于 F C A的 模式匹配方法的平均性能优于缺少 F C A整合的直接匹配方法 关键词 ：
3、模式匹配； 形式概念分析 ； 朴素贝叶斯分类器 ； 相似评估 中图分类号： T P 3 9 l 文献标识码 ： A 文章编号 ：1 0 0 1 0 5 0 5 ( 2 0 0 9 ) 0 1 - 0 0 3 4 -06 Fo r ma l c o n c e p t a n a l y s i s b a s e d s c h e m a ma t c h i n g Wa n g F e n g L i X i a o p i n g Wa n g Q i a n ( S c h o o l o f C o mp u t e r S c i e n c e a n d E n g i n
4、e e r i n g ， S o u t h e a s t U n i v e r s i t y ， Na n j i n g 2 1 0 0 9 6， C h i n a ) ( K e y L a b o r a t o r y o f Co m p u t e r N e t w o r k a n d I n f o r ma t i o n I n t e g r a t i o n o f Mi n i s t r y o f E d u c a t io n ， S o u th e a s t Un i v e r s i t y ，N a n j i n g 2 1 0
5、 0 9 6 ，C h i n a ) Ab s t r a c t ： A n e w s c h e ma ma t c h i n g a p p r o a c h b a s e d o n f o r ma l c o n c e p t a n a l y s i s( F C A)i s i n t r o d u c e d Th e p r o c e d u r e c on t a i n s t hr e e s t e p s Fi r s t l y，t h e e v i d e n c e a b o u t e a c h e l e me n t b e
6、i n g ma t c h e d i s i n i t i a l i z e d b y a pp l y i n g n a me c l a s s i fie r a n d d e s c r i p t i o n c l a s s i fie r wh i c h a r e b u i l t o n Na i v e Ba y e s Te x t Cl a s s i fte r t o c l a s s i f y t h e n a me s a n d d e s c rip t i o n s o f t h e e l e me n t s S e c
7、on dl y，F CA i s a p p l i e d t o i n t e g r a t e t h e c l a s s i fie d r e s u l t s a s we l l a s t y p e me s s a g e s a n d c o ns t r a i n s t o i n c r e a s e t h e e v i d e n c e Th i s s t e p i s d e s i g n e d t o c r e a t e f o r ma l c o nt e x t f o r v a ilO U S i n f o rm
8、a t i o n t o b e i n t e g r a t e da c q u i r e t he c o n c e pt c o n t a i n e d，fig u r e ou t t h e p a r t i a l o r d e r be t we e n c on c e p t s a n d c o ns t r u c t t h e c o n c e p t l a t t i c e At l a s t ，a s t ruc t u r a l s i mi l a rit y me a s u r e i s i n t r o d u c e
9、d t o c a l c u l a t e t h e fin a l ma t c h e s Ex p e rime nt a l r e s u l t s d e mo n - s t r a t e t h a t F C A b a s e d ma t c h i n g o u t p e r f o rm s d i r e c t ma t c h i n g( w i t h o u t t h e b e n e fi t o f F C A) Ke y wo r ds：s c h e ma ma t c hi n g；f o r ma l c o nc e p t
10、 a n a l y s i s ；n a i v e Ba y e s c l a s s i fie r ；s i mi l a rit y me a s u r e 模式是通过结构联系的一系列元素的结合 模 式匹配是数据交换 的核心 ， 以 2个模式 s ， T作 为 输入， 产生匹配对， 每个 配对的一部分元素来 自 S， 另一部分元素来自T， 通过 配表达式指出两部 分元素如何关联。 m于准确 的语 义信息 只有模 式设计者才能真正掌握， 不能存模式中完全表达 ， 所 以模式 配 的 自动 实现 足一个难 以解决 的问题 目前主要有基于模式内部信息的模式 配和基于 大规模数据以及背景
11、知识的模式匹配 基于待匹配 模式内部 信息的模式 配有 C l i o法 、 S i mi l a r i t y F l o o d i n g法 一 、 C u p i d 、 P r o b a b i l i s t i c L o g i c法 p j 、 C o n t e x t u a l S c h e ma Ma t c h i n g 和基于字典的 配 方法 ， 其优点在于整合模式内聚信息； 其局限性 在于模式 自身语义的不完备 基于大规模数据以及 背景知识 的模 式 匹配 有 ： S e mI n t 法 、 D u p l i c a t e s 法 、 Mu t u
12、 a l E n h a n c e m e n t 法 和 C o r p u s法 ， 该类方法充分利用数据实例或者以往的 配结果， 但往往不具备通用性， 并且学习数据较难获取 现 收稿 臼期 ： 2 0 0 8 - 0 5 1 5 作者简介 ： 王峰 ( 1 9 8 4) ， 男， 硕十生 ； 王茜( 联 系人 ) ， 女， 教授 ， 博士生 导师， q i a n wa n g 6 4 9 1 2 6 3 n e t 基金项目：囝家 I=_ 然科学 鳗金资助项 目( 6 0 5 0 4 0 2 9 ， 6 0 6 7 2 0 9 2 ， 6 0 8 7 3 2 3 6 )、 国家高技术
13、研究发展计划( 8 6 3计划) 资助项 目( 2 0 0 8 A A 0 4 Z1 0 3 ) 引文格式 ：壬峰 ， 李小平， 一 茜 基于形式概念分析的模式 配赞 法 J j 东南大学学报 ： 自然科学版 2 0 0 9， 3 9 ( 1 ) ： 3 4 3 9 第 1期 王峰 ， 等 ： 基 于形式概念分析的模式匹配算法 3 5 有方法在处理复杂匹配 、 同名异义字段 的匹配 、 效 率方面都存在一定 的不足 针对上述 问题 ， 本文提 出基于 F C A 的模式 匹配算法 ( F C A B S M) 综合考 虑模式各方面的信息 ， 如字段名 、 字段描述等， 据此 构建信息文本 ，
14、利用朴素贝叶斯分类器来进行信息 文本的归类 ； 引入形式概念分析来整合上述归类信 息 以及模式的结构信息 、 约束信息 ； 在形式概念分 析的基础之上引入新 的相似评估模 型获取最终的 匹配结果 与文献 1 2 中算法相 比， 本算法在第一 阶段 引入的贝叶斯分类算法更有效地利用 了数据 库模式的内在信息 ， 第三阶段的相似评估模型简洁 而有效地计算 出最终匹配结果 1 形式概念分析与概念格 形式概念分析( F C A) 是一项 基于概念格 C 2 E o ， El ， E 3 ， E 4 ， 厶 理论以及命题演算的数据分析方法 ， 适用于发现形 式上下文 ， 已经被应用到软件工程 、 知识发
15、现 、 策略 分析和心理学 等领域 概念格 ( Ga l i o i s 格 ) 是形式 概念分析理论中的一种核心数据结构 概念格的每 个结点是一个形式概念， 由两部分组成 ： 外延 ， 即概 念覆盖的实例； 内涵 ， 即概念的描述 ， 实例的共同属 性特征 概念格通过结构化的方式抽象出人类思维 中的概念， 通常概念格通过 H a s s e图展现概念之间 的泛化与特化偏序关系 ， 每个概念以结点表示 ， 如 果概念 A在概念 之上且二者有关联 ， 则称概念 A 是概念 B的泛化 ， 即概念 A仅具 有概念 B的部分 属性 对于 图 1所示 概念格 ， 概念 c 为概念 c 2 ， C 3 ，
16、 c 4的泛化 ； 概念 c 2 ， C ， c 4 是概念 C 。的特化 ； ， ： ， E ， ， ， 表示概念 c 4 具有外延 ， E 2 ， E 3 和内涵 cl E o ， E l ， E 2 ， E 3 ， E 4 ， (2 j C 4 E o ， E 2 ， E 3 ， t b C 7 l e o ， E 3 ， L， l b ， l d 露C 8 ， 厶， 如， 厶， l a 图 1 概念格的 H a s s e图 形式概念分析的相关定义如下 ： 定义 1 设 x为所有对象的集合， y为所有属 r 性的集合 ， 形式背景是映射 ： X Y 一 0 ， 1 ， 如果 对象 XX
17、具有属性 Y Y ， 则 ， ( X ， Y )=1 ， 否则 ， ( X ， Y )=0 一 个包含对象集 1 ， 2， 3 ， 4， 5 ， 属性 集 a ， b ， C ， d 的形式背景可用表 1表示 表 1 形式背景的表示 对象 a b f d 定义 2 设厂 为 X X Y上的形式背景 ， 对于 x x， 贝 0 c ( X )= YY I -厂 ( X ， Y )=1 ， V XX 表示 x 中全体对象所共有的属性集 定义3 设， 为 X X Y 上 的形式背景 ， 对于 】 ， y ， 贝 0 c( Y )= X l -厂 ( ， Y )=1 ， V YY 表 示同时具有 y
18、中所有属性 的对象集 定义 4 设， 为 X Y 上的形式背景， X， y y ， 如果 X =C ( Y ) 且 Y =C ( X ) ， 则称( x ， Y )为-厂 上的形式概 念， x ， y 分 别称为形式概念 ( X ， Y ) 的外延和 内涵 6 表示XY 上形式背景 l厂 的所有形式概念集 定义5 设， 为 XY 上的形式背景 ， 如果 ( x。 ， Y ) ， ( X 2 ， )是 -厂的 2个 形式 概念 ， 规定 ： x X 2 铮 ( X。 ， Y 1 ) ( X 2 ， y 2 ) ， y 2 Y 。 铮( X1 ， Y 1 ) ( X 2 ， y 2 ) ( 其中“
19、 ”表示偏序关系 ) 称( x ， y 1 ) 为 ( ， y 2 ) 的子概念 ， ( ， y 2 ) 为( x。 ， y 1 ) 的超概念 显然 ， 关系“ ”是集合 6 上的一个偏序关 系， 可诱导出 6 上 的一个格结构 ， 可以证明其为 一 个完备格_ 】 相应 的上确界与下确界定义为 = ( c ( c( ) ) ， ，口 ) ， g ( ，口 ， c ( c ( ，U ， i j l E j i E J J ) ) ) 其中， ( x ， ， )6 ； ， 为指标集 该完备 格称为形式背景 ，的概念格 ， 在无歧义情况下仍然 记为 6 2 基于 F C A 的模式 匹配方法 基于
20、 F C A 的模式匹配方法分为 3个阶段 ： 归类 阶段 ， 对给定的 2个模式 ， 分别根据字段名 、 字 3 6 东南大学学报 (自然科学版) 第3 9卷 段描述和类型信息对源模式与 目标模式 的字段进 行分类 ； F C A阶段 ， 引入形式概念分析， 以上述 归类信息以及结构信息( 主外键特征) 为属性， 以 源模式与 目标模式的各字段为对象构建形式概念 上下文， 抽取 出其中的概念， 获得偏序关系； 相 似度计算 阶段 ， 通过文献 1 6 的相似评估模型计 算概念间的匹配度 ， 以确定字段问的匹配 2 I 归类 2 I 1 名称分 类算 法 以朴素贝叶斯学习文本分类算法的核心算法
21、 L N BT与 C NB T( D o c ) 为基础 ， 提出名称分类算 法 采 用 分 隔符 ( 如 “ fi r s t n a me ” 分 割 成 “ fi r s t n a m e ” ) 和字段表示( 如“ D e p N o ” 分割后变成“ D e p N o ” ) 等 2种策略对字段分割 ； 将分割后得 到的单 词进行扩展 ， 即根据应用的领域找出单词对应的同 义词 ， 形成单词集 以每个源模式字段为一个类别 ， 对该字段单词集中每个单词进行 七 一 段解析 ， 解析后 的数据作为该字段类 别的训练样例， 若 k取值 为 3 ， 则单词 “ a u t h o r ”
22、 解 析后 的数据 为 “ a u t u th t h o h o r ” 评价贝叶斯归类算法的技术指标为运行时间 和归类结果的平均估计概率两方面 不 同 k 值对算 法产生不同的影响 ， 为确定合适 的 k值 ， 考察 k分 别为 1 5的情况 ( 见表 2 ) 文本分类算法在切割 长度为 3的情况下 ， 既可维持较高的估计概率 ， 也 具备较快的运行时间， 所以合适的 k 值为 3 表 2 k值对朴素贝叶斯文本分类算法的影响 将 目标模式字段 3 一 段解析后的文本作为待分 类数据， 送入已经训练好 的朴素贝叶斯学 习器 ， 计 算出该 目标字段属于各源字段类别的估计概率， 各 源模式字
23、段以及按概率大小降序排列 的前 l 项 目 标字段， 共同组成一类 ： 一( e e e ， e ， ， ) ， f 1 ， m ， ， =ma x ( 2 ， n 5 ) ， 其 中 m 为源模式中字段 的数 目， 为目标模式字段的数 目 所提出的名称分类算法具体描述如下 ： S OURCENAM EA NAL YS I S ( S c h e ma S ) S o u r c e E le S e t - - - 源模式 中的所 有字段集 ， m一 源模式 字段 数， 一3 ， 类别集合 c 一 ， S a m p l e s , - ； 按字段命名特征选取 分割策 略分割 S o u r
24、 c e E l e S e t 中每个 字段 e ， i 1 ， m ； 按选取 的策略切割 e 后得 到的所有单 词形成 集合 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 中每个字段 e ， ( i E【 1 ， m ) ： C i P ， 文本集 一 ； C Cu c ； 扩 展 S o u r c e E l e l n i S e t 中每 个 单 词 的 同 义词 ， 并 加 入 S o u r c e E le l n i S e t 形成新集 合 S o u r c e E le S e t ； 对S
25、o u r c e E l e S e t 中的 每个单词W ， ( t 1 ， I S o u r c e E l e S e t 1 ) 进行k 段解析 S a m p l e s , - - S a mp l e s u 类别 C 与文本集 的匹配关 系 ； T e x t ， 一单词 w， 解析后的文本字符串； u T e x t ， ； 使用朴素 贝叶斯 文本文类 算法 L N B T( S a mp l e s ， C) 学 习 样例 TARGE T NAM EAN A L YS I S ( S c h e ma T) T a r g e t E l e S e t , 目标模式
26、中 的所有 字段 ， 一 3 ， E l e V a l u e s Ma p p i n g 一 ， n 一 目标模式字段数 ， i E【 1 ， n ， R e s u lt S e t 一 ； 对 T a r g e t E l e S e t 中每个字段 e ( i E 1 ， n ) 进行 段解析： T e x t 一单词 W ， 解析后的文本字符 串； R e s u l t S e t - - - R e s u l t S e t u C N B T( T e x t f ) ； E l e Va l u e s Ma p p i n g - - - E le Va l u e
27、 s Ma p p i n g u 字段名 e 与解析结果集 R e s u l t S e t 的 配关系 ； 返回 E l e V a l u e s Ma p p i n g； NAM E L E AR N NE R( S c h e ma S ， S c h e ma T ) m 一 源 模 式 字 段 数 ， n 一 目 标 模 式 字 段 数 ， b - m a x ( 2 ， ) ， E l e Va lu e s Ma p p i n g , - - ， Jp 一 ； S OURCE NAM EAN A L YS I S ( S c h e ma S ) ； El e Va l
28、 u e s Ma p p i n g E l e Va l u e s Ma p p i n g U TARGET NAME AN A L Y S I S ( S c h e m a T) ； 对 C中每个分类 c ， i 1 ， m 将 E l e V a l u e s Ma p p i n g中与 C f 匹配的各 目标字段按估 计概率 大小降序排列 ； 取前 1 项匹配的 目标模式字段 ， 与 c 亦即 e 共 同组 成分类 向量 P i 一 ( e l e f 1 e ， ， ) ； 尸 一Jp u P ； 返 回名称分类 向量集 P； 2 1 2描述 分类 算法 字段的描述在语义
29、上提供了对匹配的支持 与 字段名比起来 ， 描述更能解释字段的含义 由于字 段描述的质量很难控制 ， 为了获得更好 的分类效 果， 本文一方面在描述中加入了字段名， 作为冗余 信息加强描述的针对性； 另一方面从可能的角度对 字段名再描述 ， 丰富字段的含 义 每个源模式字段 为一个类别 ， 优化后的源模式各字段描述作该类别 的训练样例 ， 目标模式 的字段 描述作 为待分类 文 本， 得出该 目标字段属 于各源字段类 别的估计概 率 同上， 各源模式字段以及按概率大小降序排列 的前 项 目标字段 ， 共 同组成一类： q i 一( e e ， ， e e ， ) ， 1 ， m ， z =ma
30、 x ( 2 ， n 5 ) ， 其中 m为源模 式中字段的数 目， n为 目标模式字段的数 目 第 1期 王峰 ， 等 ： 基于形式概念分析的模式匹配算法 3 7 算法描述如下 ： S OURCE DESAN AL Y S I S ( S c h e ma S ) S o u r c e E l e S e t , - - 源模式 中的所有 字段 集 ， ， ， l 一 源模 式字 段 数 ， 类别集合 c一 ， S a mp l e s , - - ， 一提供的该 字段描述 的总数 ； 对 S o u r c e E l e S e t 中每个字段 e ， i E 1 ， m ci P ，
31、 + _ I ； ccU c ； 对字段 e 的所有可能的描述 d ， + _ 一 u ， ； S a mp l e s - - S a m p l e s U 类 别 与描述 集 的 匹配 关 系 ； 使用朴素 贝叶斯 文本文类算 法 L N B T( S a mp l e s ， C) 学 习 样例 ； TARGET DESAN AL YS I S ( S c h e ma T) T a r g e t E l e S e t -目标模式 中的所有字段 ， n 一 目标模式字段 数 ， i 1 ， n ， E l e Va l u e s Ma p p in g * - - ， d l 一
32、 目标 模式 各字段 描述 ， Re s u l t S e t ， + - - ； 对 T a r g e t E l e S e t 中每个字段 e ： Re s u l t S e t Re s u l t S e t ， U CLAS S I F Y NAI VE BAYES T E XT ( d ) ； E l e V a l u e s Ma p p i n g - - E l e Va l u e s Ma p p i n g U e ， 与对应 R e s u l t S e t 。 的匹配关系 ； 返 回 E l e V a l u e s Ma p p i n g ； DE
33、S CRI P TI ON L E A RN NE R( S c h e ma S ， S c h e ma T) m一 源模 式字 段数 ， n 一 目标模 式字 段 数， ， 一ma 】【 ( 2， n 5 ) E l e V a l u e s Ma p p i n g * - ， Q 一(2 j ； S OURCE DESA NA L YS I S ( S c h e ma S ) ； El e Va l u e s Ma p p i n g -El e Va l u e s Ma p p i n g U TARGE T DE S AN AL Y S I S ( S c h e ma
34、T) ； 对 C中每个分类 c ， ， i 1 ， ， 1 将 E l e V a l u e s Ma p p i n g中与 C 匹配的各 目标 字段按估 计概率大小降序排列 ； 取前 ， 项 目标模式 字段 ， 与 C 亦 即 e 共 同组 成分类 向量 q f 一( P P f l ， e ， 2 P ； QQu q i ； 返回描述分类向量集 Q 2 1 3类型 分类 策略 通过类型分类策略， 主要完成模式数据模式类 型的整合， 以 My S Q L数据库为例 ， 类型分为以下 3 类： 数值： T I N Y I N T ， S MA L L I N T ， ME D I U MI
35、 N T ， I N T ， B I G I N T ， F L O A T ， D O U B L E ， D E c I MA L ； 字 符串： c H A R， V AR C H AR， T I NY B L o B， B L O B， ME DI UM BLOB ， LONGBL0B ，TI NYTEXT， TEXT， ME D I u MT E x T， L 0N G T E x T， E N uM ， S E T； ( 日 期 及 时 问 ： D A T E， T I ME，D A T E T I ME， T I ME S TAM P YEAR 2 2 形式概念分析 在归类阶段
36、的基础之上 ， 以主键 、 外键 、 名称分 类、 描述分类、 类型分类的类别名为属性即I = ( k ， k 2 ， P 一 ， P ， q 一 ， q ， Nu mb e r ， S t r i n g ， T i m e ) ， 其 中， m为源模式字段的数 目 同时以源模式及 目标 模式中各字段为对象， 构建形式概念上下文 根据 第 1阶段的归类结果 ， 各字段在对应的分类处设值 “ 1 ” 以形式概念上下文为基础 ， 根据定义 3 ， 检索 形式概念上下 文中的形式概念 ， 根据定 义 4， 确定 形式概念之间的偏序关系 ， 构造概念格 2 3 相似度计算 采用文献 1 6 的相似评
37、估模型 ， 计算 F C A 阶 段概念格 中各形式概念的相似度 ， 定义如下 ： S ( a ， b )= l ( a V b ) I i ( a V b ) f + O t f ( a b ) f +( 1 一 ) f ( b a ) f ( 1 ) 式 中， ( a V b ) 表示概念格中 a ， b两结点公共 的 且只有一条 向上边 的祖先结点集合 ； ( ab ) 表 示那些只在 a中出现但未在 b中出现的只有一条 向上边的祖先结点集合； ( b a ) 表示只在 b中出 现但未在 a中出现 的只有 一条向上边的祖先结点 集合 本文取 值为0 5 ， 意为相似计算是对称性的， 即
38、a与 b的相似度等于 b与 a的相似度 以图 1为 例 ， 计算结点 a=5与结点b=7间的相似度 ： ( a V b ) = 2 ， ( ab ) = 3 ， ( ba ) = 4 ， 1 ( 以 ， ) 0 3 3 算法所得到 的匹配结果为第 2阶段所学 习到 的概念之间的匹配度 模式的字段包含在概念的外 延之中， 可以看出 ， 包含某 特定字段的所有概念 中 内涵最多的概念为完全覆盖该字段的概念 ， 通过找 到完全覆盖各字段 的概念便 可确定各字段之 间的 匹配度 ， 本文取匹配阈值 =0 5来获取最终的匹 配关系 算法整体描述如下： 分别根据源模式和目 标模式的字段名以及 字段描述对各
39、字段进行归类 分别产生归类 集 ： p +_- ( e e f l e f ， ， e f ， ) ， i 1 ， m ， z = ma x ( 2， n 5 ) ， q + _ -( e e f l e ， e ， ， ) ， i 1 ， m ， ， = ma x ( 2， n 5 ) 其中， m为源模式字段数 ， n 为 目标模 式字段数 以第 步的归类信息以及类型归类信息、 结构信息 ( 主、 外键 )三大类作为形式概念上下文 中的属 性，即： ， = ( k ， k 2 ， P 一 ， P ， q 一 ， q ， Nu mb e r ， S t r i n g ， T i me ) ，
40、 其 中， m为源模式字段数 以源模式 以及 目标模式 中各字段作为对象 ， 构建形 式概念上下文 以此为基础 ， 构建概念格 利 用 相 似 评 估 模 型 ， 即： S ( a ， b ) = l f a V 61 I ( a V b ) I + I( ab ) I +( 1一 )l( ba ) I 3 8 东南大学学报(自然科学版) 第 3 9卷 计算概念之间的相似度 ， 取阈值 =0 5获取最终 字段间的匹配关系 3 实验结果 为了评估匹配质量 ， 将本文算法与基于字典的 模式匹配算法 ( D M) 以及基于 C o r p u s的模式 配算法 ( C B N B ) 做 了比较，
41、评估采用 3个通用 指标： 查准率 ( 匹配结果中正确结果的 比率 ) ： = T P=7 “ ( T+ ) ； 查全率 ( 配结果中正确 结果占实际结果的比率) ： 口 =T R； 全面性( 评 估后期匹配所需要的工作量) ： y= 卢( 21 a) 其 中， 为正确识别的 配结果 ； P为匹配方法返回的 匹配结果 ； 尺为手工返回的匹配结果 ； F为错误 的 匹配 实验中源模式为 自主开发 的在线 目标制定系 统 2 4 Ho u r z ， 目标数据库为开源在线 日志或论坛 系 统 ， 包 括T e x t p a t t e r n， P i x e l p o s t ， Wo r
42、d P r e s s ， P h p b b ， D i s c u z 本实验分别将 2 4 Ho u r z 与各 目标模 式进行匹配操作 ( 见表 3 ) 表 3 各算法匹配质量比较 由表 3可以看 出， 在问题复杂度较小的设计规 范的T e x t p a t t e r n模式匹配问题中， 基于字典的 配 方法能够快速准确地找到匹配关系， 具备较高的查 准率0 9 2 ， 但查全率不及基于 C o rp u s 及基于 F C A 的算法策略， 只有 0 6 5 当问题规模扩大或者模式设 计不规范时， 只借助于字典或者仅通过单纯的文本 相似性的判断不能挖掘模式中蕴含的 配关系 ，
43、同 时也不能解决多对多的匹配问题， 具体表现为查全 率较低 ， 在 Wo r d P r e s s以及 D i s c u z的匹配查全率方 面， D M 仅为 0 5 5与 0 6 8 ， C B N B相对优越但也仅 有0 8 3与 0 8 0 ， 不及 F C A B S M 的 0 8 9与 0 8 0 在字段及描述归类的基础之上， 再借助于类型 归类和结构信息， 通过 F C A整合 ， 获得最终的匹配 结果的算法策略随着问题规模的扩大 以及复杂度 的增加， 能够有效获取 配项 ， 保证查准率与查全 率 ， 减少后期人工筛选 的工作量 在处理相对 复杂 的 P h p b b及 D
44、i s c u z的 配问题时， F C A B S M 的全 面性优势不明显， 分别只有 0 6 8与0 5 5 ， 而 C B NB 为0 6 6与0 5 2 ， 这是由于 F C A B S M 在借助多样信 息的同时也带来 了噪声与污染 阏此 ， 如何为 F C A 提供更精准 的属性特征 ， 如何 引入匹配依 据的权 重， 如何提高模式信息的质量从而减少信息量的增 加带来的负面影响 ， 是进一步研究的重点 为了考察 同义词对算法的影响， 在算法的归类 阶段中， 对源模式各字段切割之后不再进行同义词 及领域等价词 的扩展 将去除同义词的算法与完整 算法在处理 a i ms p o s
45、t s匹配 问题上 的表现作为 比 较 ： Ai m s ( a i m i d ， a i m a u t h o r i d ，a i m d a t e ， a i m d e s c rip t i o n，a i m t i t l e， a i m t y p e ) ， P o s t s ( p o s t i d ， p o s t writ e r ，po s t d a t e， p o s t t i t l e， p o s t c ont ent ， p o s t c a t e g o r y ， p o s t t y p e ) ， 正确匹配结果为 Ai m
46、 s ( i d ， a i d ， d a t e ， d e s ， t i t l e ， t y p e ) + P o s t s ( i d ， a i d ， d a t e ， ti t l e ， d e s ， t y p e ， “ n u l l ” ) 比较结果如表4所示 表 4 同义词对算法 匹配结果与质量 的影响 表 4中 T表示该匹配被正确获取； F表示未检 索到该 配 ； P表示检索到该匹配但同时也找到了 其他扰乱 性 匹配 ( 在借 助 同 义词 的情 况下 获取 a i m d e s c r ip t i o n p o s t c o n t e n
47、t 以及 a i m d e s c ri p t i o n - p o s t t y p e两个 配结果 ) 在无同义词 的情况下 ， 通过对除字段 名以外 的其他几方面 ( 描述 ， 类 型， 主外键信息 ) 的综合分析也能找到匹配关系 ai m d e s c rip t i o n po s t c o n t e n t 无 同义词 的情 况 中匹配 a i m t y p e p o s t c a t e g o ry未找到 的原因除 了失去 同 义词的依据外 ， 另一方 面也 由于扰乱性匹配 ai m t y p e p o s t t y p e的存在 利用同义词能显著提高算法的性能， 但非决定 性而是辅助性 算法的性能还是构建在整体技术框 架的基础之上 第 1 期 王峰， 等： 基 于形式概念分析的模式匹配算法 3 9 4 结语 提出 的基 于 F C A 的模 式 匹配算 法 ( F C A B S M) ， 利用第 1阶段的贝叶斯学 习器的分类结果 ， 作为构建形式概念上下文的依据 ， 然后通过获取形 式概念上下文 中的概念 ， 以及概念 之间 的偏序关