带对象结构信息形式背景的概念知识发现与演化_闫梦宇.pdf

第 1 期2023 年1 月电子学报ACTA ELECTRONICA SINICAVol.51 No.1Jan.2023带对象结构信息形式背景的概念知识发现与演化闫梦宇1，2，李金海1，2，刘文奇1，2，张文修3（1.昆明理工大学数据科学研究中心，云南昆明 650500；2.昆明理工大学理学院，云南昆明 650500；3.西安交通大学数学与统计学院，陕西西安 710049）摘要：形式概念分析是数据处理和知识发现的有力工具，然而仅利用形式概念分析中的传统方法已不能满足大数据环境的需求，这是因为大量数据不仅包括对象-属性信息，还有对象与对象之间的结构信息，因此扩展形式概念分析进行数据处理与知识发现是一个重要的研究课题.基于此，本文定义了带对象结构信息形式背景，并在形式概念的基础上引入连通性提出全局结构信息形式概念和局部结构信息形式概念（统称为结构信息形式概念），进而讨论基于结构信息形式概念的知识发现问题；由于现实中数据的动态变化及信息的传播与扩散是不可避免的，又进一步探讨了当带对象结构信息形式背景对象结构矩阵或连接矩阵发生变化时结构信息形式概念的演化规律，根据不同情况分别给出了对应的算法并对它们的时间复杂度进行分析；此外，通过实验表明了结构信息形式概念动态更新方法的可行性与有效性.关键词：形式概念分析；结构信息形式概念；知识发现；概念演化；动态更新基金项目：国家自然科学基金（No.11971211，No.12171388）中图分类号：TP182文献标识码：A文章编号：0372-2112(2023)01-0011-07电子学报URL:http:/DOI:10.12263/DZXB.20211559Conceptual Knowledge Discovery and Evolution in Formal Context with Object Structure InformationYAN Meng-yu1,2,LI Jin-hai1,2,LIU Wen-qi1,2,ZHANG Wen-xiu3(1.Data Science Research Center,Kunming University of Science and Technology,Kunming,Yunnan 650500,China;2.Faculty of Science,Kunming University of Science and Technology,Kunming,Yunnan 650500,China;3.School of Mathematics and Statistics,Xi an Jiaotong University,Xi an,Shaanxi 710049,China)Abstract:Formal concept analysis is a powerful tool for data processing and knowledge discovery.However,only using the traditional methods in formal concept analysis cannot meet the needs of big data environment since most data not only contain object-attribute information but also the structure information between objects.As a result,it is an important research topic to extend formal concept analysis for data processing and knowledge discovery.Based on the above analysis,this paper puts forward the notion of a formal context with object structure information.And then,the global structural information and local structural information formal concepts are proposed(collectively called structural information formal concepts)by combining with connectivity.Meanwhile,the problem of knowledge discovery on the basis of structural information formal concepts is discussed.Considering the fact that the dynamic changes of data and the dissemination or diffusion of information in our daily life are inevitable,we further explore the evolution rules of structural information formal concepts when a formal context with object structure information is updated gradually.Algorithms are developed for updating different structural information formal concepts when object structure matrix or connection matrix changes,and their time complexity are also analyzed.In addition,we conduct some experiments to show the feasibility and effectiveness of the proposed structural information formal concept updating methods.Key words:formal concept analysis;structural information formal concept;knowledge discovery;concept evolution;dynamic updatingFoundation Item(s):National Natural Science Foundation of China(No.11971211,No.12171388)收稿日期：2021-11-22；修回日期：2022-06-30；责任编辑：李勇锋电子学报2023 年1引言知识发现是从大量数据中抽取出有价值的知识的过程1，2.而概念是知识表示的一种有效手段，从数据库中发现概念知识是指将数据库中蕴含的知识形式化为有用的概念，这一过程称为概念知识发现，对处理和解释数据十分有益.形式概念分析（Formal Concept Analysis，FCA）是一种实用的概念知识发现工具，它是Wille3教授于1982年提出的，研究对象是一类特定的对象-属性关系数据库（又称为形式背景）.通过对象集与属性集之间的特定关联，建立由对象集和属性集序对形成的概念知识.近年来，FCA已被视为是“概念数据分析与知识表示”的重要数学工具，在知识发现4、机器学习5，6、数据挖掘7、软件工程8、特征选择9，10、概念认知11，12、异构数据13、属性拓扑14、决策蕴涵15等领域得到了广泛应用.FCA 主要处理对象集与属性集之间的关系数据库，忽略了对象与对象之间的信息.早期在FCA领域考虑对象-对象关系的相关成果是通过对象-对象形式背景和对象-属性形式背景讨论对象和属性之间的联系16，但并没有真正将对象之间的结构信息考虑在内.基于上述讨论，本文引入连通性定义了带对象结构信息形式背景，需要指出的是，一个形式概念可视为一类，在形式概念的基础上考虑对象之间的连通性只能够判断给定带对象结构信息形式背景中具有相同属性的对象是否属于同一类，这相当于全局连通性；然而，给定带对象结构信息形式背景中具有相同属性的部分连通对象构成同一类的现象也是经常存在的，若只考虑全局连通性则局部包含结构信息的概念知识将无法获得.因此，本文将对象的结构信息进一步又区分为全局信息与局部信息，提出2种结构信息形式概念知识发现模型.不仅如此，数据也会随时间不断动态更新17.在FCA领域，数据的动态更新主要指对象个数、属性个数以及属性值的变化18.对于这些不断动态更新的数据，如何快速准确地找到特定的知识受到了众多学者的关注19，20.受此启发，本文将进一步提出动态概念知识发现方法以探讨概念演化问题.2带对象结构信息形式背景的概念发现对于形式背景(G,M,C)，XG，BM，定义算子X*=mM|gX,(g,m)CB*=gG|mB,(g,m)C若X*=B且B*=X，则称(X,B)为形式概念，其中X为形式概念的外延，B为形式概念的内涵.定义1 四元组(G,M,A,C)称为带对象结构信息形式背景，其中G=g1,g2,gn是非空有限对象集，M=m1,m2,mp是非空有限属性集，A是G上的结构矩阵，即对任意的gi,gjG，aij=1表示对象gi,gj是相关联的，aij=0表示对象gi,gj不是相关联的；C是GM上的连接矩阵，即任意的giG和mkM，(gi,mk)=1表示对象gi拥 有 属 性mk，(gi,mk)=0表 示 对 象gi不 拥 有属性mk.一个图称为是连通的，当且仅当从任一节点出发，经过一个或多个中间节点，能够达到其余任意节点.定义 2 设(G,M,A,C)为带对象结构信息形式背景，若XG包含的所有节点由它们之间的结构信息诱导出的子图是连通的，则称X是连通的.定义 3 设(G,M,A,C)为带对象结构信息形式背景，XG，BM(X且B).若X*=B，B*=X且X连通，则称(X,B)为全局结构信息形式概念.记所有全局结构信息形式概念构成的集合为N(G,M,A,C).定义 4 设(G,M,A,C)为带对象结构信息形式背景，XG，BM(X且B).若X*=B，X连通且不存在gB*-X使得Xg连通，则称序对(X,B)为局部结构信息形式概念.记所有局部结构信息形式概念构成的集合为NL(G,M,A,C).为了方便，将全局和局部结构信息形式概念统称为结构信息形式概念.算法1和算法2分别给出了从给定线索中发现相应的全局和局部结构信息形式概念的具体过程.算法1全局结构信息形式概念发现输入:带对象结构信息形式背景(G,M,A,C)和线索集X输出:全局结构信息形式概念(X,B)1.IF X*连通且X*THEN2.令X=X*,B=X*,返回(X,B);3.ELSE4.返回(X,B)=;5.END IF算法2局部结构信息形式概念发现输入:带对象结构信息形式背景(G,M,A,C)和线索集X输出:局部结构信息形式概念(X,B)1.FOR X*的每个最大连通子集X12.令X=X1,B=X*1;3.IF B THEN4.返回(X,B);5.ELSE6.返回(X,B)=;7.END IF8.END FOR12第 1 期闫梦宇:带对象结构信息形式背景的概念知识发现与演化分析可得，算法1的时间复杂度为O(|X|G|(|A|+|G|)，算法2的时间复杂度为O(|X|A|G|2).3结构信息形式概念的演化本节讨论对象结构信息或对象-属性信息发生改变时，结构信息形式概念的演化情况.3.1对象结构矩阵改变时现有结构信息形式概念的演化此时只有对象结构矩阵A发生变化，设其更新为A.为了方便，记(G,M,A,C)的所有全局结构信息形式概念为N(G,M,A,C).根据定义3可