形式概念分析国内外研究现状综述_许涛

第７卷第２期

软件导刊

２００８年２月ＳｏｆｔｗａｒｅＧｕｉｄｅ

Ｖｏｌ．７Ｎｏ．２Ｆｅｂ．２００８

形式概念分析国内外研究现状综述

许

涛，沈夏炯

（河南大学计算机与信息工程学院，河南开封４７５００１）

摘

要：采用文献统计方法，对有关形式概念分析的相关论文从数量、年代、来源期刊、关键词等方面进行了分析。由

约简和规则提取、与粗糙集结合等主题的研究成果以及此描述了概念格论文的主题分布，

简述了近年来关于建格、基于概念格理论的应用。

关键词：形式概念分析；概念格；文献统计；建格算法；约简；规则提取；粗糙集；ＩＣＦＣＡ中图分类号：ＴＰ３０１．２

文献标识码：Ａ

文章编号：１６７２－７８００（２００８）０２－００２１－０３

１统计分析

表１

年代

论文年代分布

２０００以前２０００２００１２００２２００３２００４２００５２００６２００７年前１０个月

１０．３

１１３．４

１２３．７

１４４．３

１９５．８

３０９．２

５１１５．６

９１２７．９

９７２９．８

本节采用文献统计方法，对我国有关概念格相论文数关论文从发文数、年代、来源期刊、主题等多方面进百分比（％）

行分析，并且和ＩＣＦＣＡ（２００３－０７年）历年会议论文作

对比，旨在明确概念格的核心期刊、发展趋势以及发现目前研究中存在的不足，从而推动概念格理论的发展。本节的统计数据主要来源于中国知网的中国学术期刊全文数据库、中国优秀博硕士学位论文全文数据库和中国重要会议论文全文数据库中收录的有关概念格的文献（截止２００７年１０月）和ＩＣＦＣＡ前五届会议出版的论文集。在对国内文献的统计中，笔者利用“概念格”、“形式概念分析”、“形式背景”等多个检索词在多个字段中进行检索，经过去重整理后得到了３２６篇相关文献。其中各类期刊学报中２３４篇，优秀学位论文８１篇，各类会议文章１１篇。以下是根据该统计结果进行的相关分析。

热点。

１．２期刊分布

对概念格领域的相关论文的来源期刊进行统计分析，有助

于认定该领域内的核心期刊，并对关注此类研究的读者起到导读和投稿指引的作用。概念格理论作为一种支持数据分析的有效工具已经引起了学术界的广泛重视，因此相关论文的来源期刊比较分散，其中各个高校的学报占了来源期刊的很大比例。笔者在表２中列出发文数排名前８位的期刊，可以看出，计算机类的核心期刊是概念格论文主要的来源刊物；合肥工业大学在概念格领域的研究已达到全国领先的水平，和其他高校相比，无论是论文的数量还是质量都一枝独秀。

笔者还注意到，国内会议论文的数量比较少，在国内还没有专门的概念格领域的会议。笔者检索到的会议文章都是发表在一些计算机类综合性会议上的。国际上概念格领域最权威的会议ＩＣＦＣＡ（ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｆＦｏｒｍａｌＣｏｎｃｅｐｔＡｎａｌｙ－会议每年都发ｓｉｓ）从２００３年起每年举行一次，至今已召开五届。

１．１年代分布

图１论文数量随年代变化趋势表一部论文集，反映关于形势概念分析的最新研究进展和应用水平，ＩＣＦＣＡ是概念格领域最高水平的国际性年会。

国内早在１９９５年就有学者开始关注概念格的发展（统计结果显示该类文章最早发表于１９９５年，是一般性介绍类文章），从图１中可以看出，２０００年以前概念格理论的发展相对缓慢，２０００年以后整体处于迅速上升的趋势。到２００４年，已经有很多学者开始关注概念格理论，且近两年以来一直保持在较高水平，呈现出快速发展的趋势。由此可以认为：概念格领域发展势头迅猛，且目前该领域的研究还处于发展的阶段，是学术界关注的

１．３关键词分布

关键词能简洁、全面的反映文章内容，本文设想通过对文

献中的关键词进行统计来确定概念格领域研究的主题。由于不同作者的研究角度不同，使得对同一个问题很难有一个统一的表述方式，因此在做统计时把意义相同但表述不同的关键词作为一类进行统计。统计结果显示，关键词主要集中在６个主要的

作者简介：许涛（１９７８－），男，河南开封人，河南大学硕士研究生，研究方向为软件工程、网络应用、知识发现；沈夏炯（１９６３－），男，河南开封人，河南

大学副教授，研究方向为软件工程、知识发现、分布式／并行计算及分布式存储。

・２２・

软件导刊２００８年

表２

发文数排名前８位的国内期刊列表序号

期刊名

相关论文数

占相关论文总数百分比（％）

１合肥工业大学学报３０９．２２计算机工程与应用

２４７．４３软件学报、计算机研究与发展１５９．２４计算机科学１４４．３５计算机工程１３４．０６中国科学Ｅ辑

１２３．７７计算机应用、河南大学学报１１６．７计算机学报、小型微型计算机

８

系统、西南交通大学学报、山９１３．８西大学学报、吉林大学学报

合计

１９０

５８．３

注：为便于说明问题，将统计结果中的研究生学位论文归入相应学校中。

方面，结果在表３中列出。

表３

国内概念格文献主题关键词分布统计

主题

相关关键词

占论文总数百分比（％）

建格算法建格算法、渐进式构造，并行算法等１６．４属性约简和剪枝

属性约简、内涵缩减、纵横向的维护等

１２．８规则提取和知识发关联规则、蕴含规则、数据挖掘、序列现

模式、知识发现等

２５．２与粗集理论的结合粗糙集合、粗糙隶属度、等１０．０与其他理论的结合本体、模糊概念格、语义Ｗｅｄ等１０．３概念格的应用很多，不再赘述

１７．４其他

８．０

从表３可以看出，文献主题分布比较平均，规则提取、建格算法和概念格的应用是研究的热点。由于概念格结构自身的优点，使概念格理论与其它理论的结合应用成为越来越多的学者密切关注的领域。需要说明的是，笔者对于“介绍性文章”和“综合评述”类文献没有单独分类，而是把它们归入符合其特点的相应类别。原因在于本次统计只限于期刊、会议和毕业论文，未将专业报纸列入统计源，因此这类文献数量不多，没有必要再

单独分类。

图２

国内期刊发表论文数比例

图３

国内外形式概念分析应用类文章比例对比

通过对２００３￣２００７年前五届ＩＣＦＣＡ会议收录的论文进行分析，在图３中可以发现，接近一半的文章都以概念格在各个领域的应用为主题（前五届会议共收录论文１２２篇，与应用相关的有

６２篇，并且每届会议中应用类文章占当年会议论文总数的比例

也都在半数左右，年度间没有太大的变化）。由此可见，国际上概念格理论的发展已经比较成熟，开始更多地关注概念格的具体应用。图３对国内外概念格的应用情况作了对比，清晰地反映了两者之间的差距，从而认识到国内概念格理论还处在初期发展阶段，应用类文章的比例低，研究人员更加注重理论体系的发展。因此，加强概念格的应用研究还需更多的各领域学者参与进来，给概念格理论带来新方法，注入新思想；同时还应密切关注国际上的发展动态，加强与国外研究人员的交流沟通，缩小于国际先进水平的差距。

２概念格各主题分析

本节以表３的主题分布为依据，简述了各主题在国内的研

究现状。

２．１建格算法分析

在应用概念格的过程中，概念格的构造效率始终是一大难

题，人们对此进行了广泛的研究，提出了各种不同的构造算法，但只有少数的算法能够同时生成相应的Ｈａｓｓｅ图。这些算法主要可以分为３大类：批处理算法、渐进式算法和并行算法。批处理算法思想是首先生成所有概念，然后根据它们之间的直接前驱－后继关系生成边，完成概念格的构造，例如Ｂｏｒｄａｔ算法、ＯＳ－

ＨＡＭ算法、Ｃｈｅｉｎ算法、Ｇａｎｔｅｒ的算法、Ｎｏｕｒｉｎｅ算法等。渐进式算

法思想是首先初始化概念格为空，将当前要插入的对象和现有格中所有的形式概念作交运算，根据交的结果不同采取不同的行动，典型的算法有Ｇｏｄｉｎ，Ｃａｐｉｎｅｔｏ和Ｔ．Ｂ．Ｈｏ的算法。概念格并行生成思想就是通过形式背景的拆分，形成分布存储的多个子背景，然后同时并行构造相应的子概念格，再由子概念格的合并得到所需的概念格。目前有关并行算法的研究不是很多，通常都是以其它算法原理为基础提出的，但不可否认，随着处理的形式背景的增多，概念格的时空复杂度也会随之急剧增大，并行算法是发展的一个大趋势。

２．１．１渐进式算法

渐进式算法中典型的是Ｇｏｄｉｎ的算法，它的基本思想就是

在给定原始形式背景Ｋ＝（Ｕ，Ａ，Ｒ）所对应的初始概念格Ｌ＝（ＣＳ（Ｋ），≤）以及新增对象ｘ＊的情况下，求解形式背景Ｋ＊＝（Ｕ∪

第２期许涛，沈夏炯：形式概念分析国内外研究现状综述・２３・

｛ｘ＊｝，Ａ，Ｒ）所对应的概念格Ｌ＊＝（ＣＳ（Ｋ＊），≤）。对于初始概念格

中的每个节点，根据它和新增对象ｘ＊的特征集ｆ（ｘ＊）之间的关系，格中节点可被分为更新格节点、产生子格节点和不变节点。当插入ｘ＊时就根据节点类型对概念格做不同处理，实现节点和相应边的更新。

２．１．２批处理算法

批处理算法按照生成节点和边的次序不同有两种途径：一

种是首先生成全部的概念集合，然后再找出节点间的边；另一种是每次生成少量概念，并将这些概念链接到节点集合中。前者称任务分割生成模型，如Ｇａｎｔｅｒ算法、Ｃｈｅｉｎ算法；后者称任务交叉生成模型，如Ｂｏｒｄａｔ算法。

２．１．３并行算法

随着数据规模的不断增大，传统的渐进式和批处理算法在

时间、空间复杂性方面的问题越来越突出，主要是因为生成概念格所采用的数据是集中式存储的，而算法是串行的。解决这一问题的有效途径是利用高性能并行计算机和网络并行计算的能力，因此近年来国内外的研究者纷纷将批处理算法的并行性和渐进式算法的高效性相结合提出了概念格的并行算法。

２．２约简和规则提取

概念格约简就是寻找最小的属性子集，它能够完全确定原

始形式背景上的概念及其层次结构。概念格约简使得形式背景中隐含知识的发现变得更容易，也使得这些知识的表示变得更简单。它进一步扩充了概念格理论，对概念格理论的研究和应用都有重要意义。

规则本身是用内涵集之间的关系来描述的，而体现于相应外延集之间的包含（或近似包含）关系。

由于概念格结点反映了概念内涵和外延的统一，结点间关系体现了概念之间的泛化和例化关系，因此非常适合作为规则发现的基础性数据结构，这也是概念格作为一种数学分析工具在ＫＤＤ方面非常重要的一个应用。根据数据挖掘任务的不同（如蕴涵规则、关联规则、分类规则、聚类分析、序列模式、时序摸索、决策规则等），国内研究人员做了大量研究，并且对概念格结构做了不同程度的扩展以适应规则挖掘的要求。

提取分类规则的模型又很多种（判断树、贝叶斯网、神经网络、概念格和粗糙集等），概念格模型只是其中的一种。基于概念格的分类规则的研究主要集中在概念格构建的优化和规则求解算法的优化上。

２．３与粗糙集理论的结合

粗糙集理论是一种处理模糊和不确定知识的软计算工具，

是一种重要的数据库知识发现方法，它的主要优势之一是不需要任何预备的或额外的有关数据信息。概念格与粗糙集之间具有相似之处，格的概念就是具有最大共同属性的对象的集合。在形式背景中，外延即是由内涵所确定的等价类。

因此，粗糙集的一些性质包括等价类、近似等都可以通过概念来描述。另外，粗糙集合理论中近似空间的概念给出了一种理解与处理知识的模型，它将知识定义为不可区分关系的族集，这就使得知识具有了清晰的数学意义。

２．４概念格的应用

概念格良好的结构特征使得概念格不仅仅能从数据中分

类和定义概念，发现对象之间、属性之间的依赖关系等信息，还能很好地利用概念格中的信息形成知识。因此在智能数据处理、知识发现、数据挖掘方面，概念格的应用很广泛。

目前，随着网络技术的普及，概念格在语义Ｗｅｂ、电子商务、Ｗｅｂ服务管理、

入侵检测、个性化导航、搜索引擎等方面已经有了广泛的应用。文献［２８］以本体论和概念格理论为基础，提出一种基于语义Ｗｅｂ服务相似度的功能匹配方法；根据该方法实现了一个原型系统，为语义Ｗｅｂ服务查找匹配提供了一种可行的解决方案。文献［２９］在Ｗｅｂ服务管理中引入了ＦＣＡ的方法，建立了描述服务间相互关联的概念格，分析了如何通过概念格对Ｗｅｂ服务进行有效地管理，并实现了概念格的增量维护。文献［３０］将概念格应用于入侵检测系统中，构造了一个基于规则分类判决的入侵检测模型，提出了决策规则格和决策规则格约简的概念，获得了入侵检测的分类规则集。文献［３１］在传统搜索引擎的基础上，采用Ｗｅｂ挖掘技术，引用概念格知识，提出了个性化搜索引擎。

通过以上对众多文献的分析，可以看到概念格作为数据分析工具，它的应用的本质是建立在数据库基础上的对各种不同类型数据的分析，通过格结构的约束找到数据之间的联系，形成满足需要的各类规则，再应用到实际的系统当中去，主要应用于知识发现、软件工程、信息检索、网络技术、人工智能等方面。由于格结构面对的都是大型的复杂数据库，因此，提高应用系统的数据分析速度和系统的响应速度将是应用系统成功的关键因素。

参考文献：［１］谢志鹏，刘宗田．概念格的快速渐进式构造算法［Ｊ］．计算机学报，

２００２（５）．

［２］李云，刘宗田．基于属性的概念格渐进式生成算法［Ｊ］．小型微型计算机系统，２００４（１０）．

［３］韩道军，沈夏炯，安广伟等．Ｇｏｄｉｎ算法扩展研究［Ｊ］．河南大学学报（自然科学版），２００６（２）．

［４］沈夏炯，韩道军，刘宗田等．概念格构造算法的改进［Ｊ］．计算机工程与应用，２００４（２４）．

［５］谢润，李海霞，马骏等．概念格的分层及逐层建格法［Ｊ］．西南交通大学学报，２００５（６）．

［６］翟岩慧，曲开社，曹桃云．基于矩阵秩的概念格生成算法［Ｊ］．电脑开发与应用，２００６（５）．

［７］张凯，胡运发，王瑜．基于互关联后继树的概念格构造算法［Ｊ］．计算机研究与发展，２００４（９）．

［８］卢明，胡成全，齐红等．一种使用属性表的快速概念聚类算法［Ｊ］．复旦学报（自然科学版），２００４（５）．

［９］胡学钢，张玉红，唐志军等．一种新的概念格并行构造方法［Ｊ］．合肥工业大学学报（自然科学版），２００５（１２）．

［１０］

李云，刘宗田，陈崚等．多概念格的横向合并算法［Ｊ］．电子学报，

２００４（１２）．

（责任编辑：赵

峰）