利用二部图生成概念格  

Constructing concept lattice using bipartite graph

作　　者：窦林立[1] 展正然[1] DOU Linli;ZHAN Zhengran(Basic Teaching Department,The Great Wall College,China University of Geosciences,Baoding 071002,China)

机构地区：[1]中国地质大学长城学院基础课教学部,河北保定071002

出　　处：《智能系统学报》2018年第5期687-692,共6页CAAI Transactions on Intelligent Systems

基　　金：河北省高校科研基金项目(Z2015137)

摘　　要：概念格作为一种有效的知识发现与数据处理的工具,在许多领域得到了广泛应用,概念格的构造在其应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图,本文通过二部图的极大完全子图的概念来生成概念格,给出了基于二部图的深度优先的概念格的迭代算法。首先,对形式背景进行必要的约简;其次,利用二部图的极大完全子图得到顶层概念的直接子概念;最后,通过求二部图的导出子图来简化形式背景,并得出每个概念的直接子概念和所有子概念,从而生成概念格。As an effective tool for knowledge discovery and data processing,concept lattices have been widely applied in many fields,and in these applications,it is important to efficiently construct concept lattice.The formal context of each concept lattice corresponds to a bipartite graph.In this paper,the maximum complete subgraph of a bipartite graph is used to generate a concept lattice,and then where an iterative algorithm with depth priority is proposed based on a bipartite graph.The process is as follows:first,a formal context is reduced;then,the direct subconcepts of the top concept are obtained using maximal complete-subgraph of bipartite graph;finally,through the derivation of the induced subgraph of bipartite graph to reduce the formal context,and find direct subconcepts and all subconcepts of every concept,then the concept lattice was established.

关 键 词：形式背景 概念格 二部图 极大完全子图 直接子概念 Hasse示图 图论 导出子图 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]