基于形式概念分析的模式匹配算法-东南大学学报.pdfVIP

第３９卷第１期 东南大学学报（自然科 学版 ） Ｖｏｌ３９ Ｎｏ１ 　 ２００９年１月 ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） 　 Ｊａｎ．２００９ 　　　　　　 基于形式概念分析的模式匹配算法 王　峰　 李小平　 王　茜 （东南大学计算机科学与工程学院，南京２１００９６） （东南大学计算机网络与信息集成教育部重点实验室，南京２１００９６） 摘要：提出了一种基于形式概念分析的模式匹配的ＦＣＡＢＳＭ方法，该方法由３部分组成：首先， 以朴素贝叶斯文本分类算法为基础设计名称分类算法及描述分类算法，分类目标模式与待匹配 模式的元素名以及元素描述，为模式间元素的匹配提供初始依据．其次，利用形式概念分析技术 整合分类结果、元素类型信息以及约束信息，提高匹配精度．该阶段为待整合信息创建形式上下 文、获取形式上下文中蕴涵的概念、确立概念间偏序关系及构建概念格．最后，以第二阶段的概念 格为计算依据，引入基于结构的相似评估模型来计算出最终的匹配结果．实验表明，基于ＦＣＡ的 模式匹配方法的平均性能优于缺少ＦＣＡ整合的直接匹配方法． 关键词：模式匹配；形式概念分析；朴素贝叶斯分类器；相似评估 中图分类号：ＴＰ３９１　　文献标识码：Ａ　　文章编号：１００１－０５０５（２００９）０１００３４０６ Ｆｏｒｍａｌｃｏｎｃｅｐｔａｎａｌｙｓｉｓｂａｓｅｄｓｃｈｅｍａｍａｔｃｈｉｎｇ ＷａｎｇＦｅｎｇ　ＬｉＸｉａｏｐｉｎｇ　ＷａｎｇＱｉａｎ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６，Ｃｈｉｎａ） （ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋａｎｄＩｎｆｏｒｍａｔｉｏｎＩｎｔｅｇｒａｔｉｏｎｏｆＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｎｅｗｓｃｈｅｍａｍａｔｃｈｉｎｇａｐｐｒｏａｃｈｂａｓｅｄｏｎｆｏｒｍａｌｃｏｎｃｅｐｔａｎａｌｙｓｉｓ（ＦＣＡ）ｉｓｉｎｔｒｏｄｕｃｅｄ． Ｔｈｅｐｒｏｃｅｄｕｒｅｃｏｎｔａｉｎｓｔｈｒｅｅｓｔｅｐｓ．Ｆｉｒｓｔｌｙ，ｔｈｅｅｖｉｄｅｎｃｅａｂｏｕｔｅａｃｈｅｌｅｍｅｎｔｂｅｉｎｇｍａｔｃｈｅｄｉｓｉｎｉｔｉａｌ ｉｚｅｄｂｙａｐｐｌｙｉｎｇｎａｍｅｃｌａｓｓｉｆｉｅｒａｎｄｄｅｓｃｒｉｐｔｉｏｎｃｌａｓｓｉｆｉｅｒｗｈｉｃｈａｒｅｂｕｉｌｔｏｎＮａｉｖｅＢａｙｅｓＴｅｘｔＣｌａｓ ｓｉｆｉｅｒｔｏｃｌａｓｓｉｆｙｔｈｅｎａｍｅｓａｎｄｄｅｓｃｒｉｐｔｉｏｎｓｏｆｔｈｅｅｌｅｍｅｎｔｓ．Ｓｅｃｏｎｄｌｙ，ＦＣＡｉｓａｐｐｌｉｅｄｔｏｉｎｔｅｇｒａｔｅ ｔｈｅｃｌａｓｓｉｆｉｅｄｒｅｓｕｌｔｓａｓｗｅｌｌａｓｔｙｐｅｍｅｓｓａｇｅｓａｎｄｃｏｎｓｔｒａｉｎｓｔｏｉｎｃｒｅａｓｅｔｈｅｅｖｉｄｅｎｃｅ．Ｔｈｉｓｓｔｅｐｉｓｄｅ ｓｉｇｎｅｄｔｏｃｒｅａｔｅｆｏｒｍａｌｃｏｎｔｅｘｔｆｏｒｖａｒｉｏｕｓｉｎｆｏｒｍａｔｉｏｎｔｏｂｅｉｎｔｅｇｒａｔｅｄ，ａｃｑｕｉｒｅｔｈｅｃｏｎｃｅｐｔｃｏｎ ｔａｉｎｅｄ，ｆｉｇｕｒｅｏｕｔｔｈｅｐａｒｔｉａｌｏｒｄｅｒｂｅｔｗｅｅｎｃｏｎｃｅｐｔｓａｎｄｃｏｎｓｔｒｕｃｔｔｈｅｃｏｎｃｅｐｔｌａｔｔｉｃｅ．Ａｔｌａｓｔ，ａ ｓｔｒｕｃｔｕｒａｌｓｉｍｉｌａｒｉｔｙｍｅａｓｕｒｅｉｓｉｎｔｒｏｄｕｃｅｄｔｏｃａｌｃｕｌａｔｅｔｈｅｆｉｎａｌｍａｔｃｈｅｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｄｅｍｏｎ ｓｔｒａｔｅｔｈａｔＦＣＡｂａｓｅｄｍａｔｃｈｉｎｇｏｕｔｐｅｒｆｏｒｍｓｄｉｒｅｃｔｍａｔｃｈｉｎｇ（ｗｉｔｈｏｕｔｔｈｅｂｅｎｅｆｉｔｏｆＦＣＡ）． Ｋｅｙｗｏｒｄｓ：ｓｃｈｅｍａｍａｔｃｈｉｎｇ；ｆｏｒｍａｌｃｏｎｃｅｐｔａｎａｌｙｓｉｓ；