一般决策形式背景的属性约简.pdf

第 56 卷第 1 期郑 州 大 学 学 报(理 学 版)Vol.56 No.12024 年 1 月J.Zhengzhou Univ.(Nat.Sci.Ed.)Jan.2024收稿日期:2022-08-08基金项目:国家自然科学基金项目(61972052)。第一作者:谢业海(1984),男,博士研究生,主要从事形式概念分析、粗糙集研究,E-mail:xieyehai 。一般决策形式背景的属性约简谢业海,高秀巍(北京语言大学 信息科学学院北京 100083)摘要:决策形式背景是形式背景的重要扩展。属性约简是决策形式背景领域研究的热点问题。由现实数据所构建的决策形式背景通常是不一致的,文中面向实际应用,研究一般决策形式背景的广义属性约简方法。定义了一般决策形式背景的广义属性约简,并基于辨识函数给出了计算所有约简的算法。该算法具有良好的通用性,可应用于一致和不一致的决策形式背景。关键词:形式概念分析;决策形式背景;辨识函数;属性约简中图分类号:TP182文献标志码:A文章编号:1671-6841(2024)01-0075-06DOI:10.13705/j.issn.1671-6841.2022232 Attribute Reduction in General Decision Formal ContextsXIE Yehai,GAO Xiuwei(School of Information Science,Beijing Language and Culture University,Beijing 100083,China)Abstract:Decision formal contexts were a significant extension of formal contexts and attribute reduction was a hot issue in the field of decision formal contexts.The decision formal contexts formed by the real world data were usually inconsistent.Oriented on the practical application requirements,the approach of attribute reduction in general decision formal contexts was studied.Furthermore,the definition attribute reduction of general decision formal contexts was proposed.Based on the discernibility function,the cor-responding algorithm of finding all the reducts was given.The proposed algorithm had good generality and could be used in the consistent and inconsistent decision formal contexts.Key words:formal concept analysis;decision formal context;discernibility function;attribute reduction0引言1982 年,德国学者 Wille1提出了形式概念分析理论,也被称作概念格理论。形式概念分析理论通过构建一个概念完备格,直观地刻画出概念之间的层次结构,因而成为一种有效的数据处理工具,被广泛应用于信息检索、数据挖掘等领域2-3。面对海量数据,如何去除冗余信息,保留核心信息,降低数据的维度和计算复杂度,对于数据处理来说十分重要,因此属性约简4-5一直受到广泛的关注。概念格的属性约简本质上是在保持概念格某个特性不变的基础上,寻找最小属性集,使约简后的概念格比原概念格更加简洁,因而概念格的属性约简一直都是热点研究问题。Zhang 等6首先提出保持概念格结构不变的约简,即约简后的概念格与原概念格同构,并基于辨识矩阵给出获得所有约简的算法。Qi7对文献6 中的辨识矩阵加以改进,获得了计算效率更高的约简算法。Wu 等8从粒计算的角度定义了概念格的对象粒,并用对象粒去定义形式背景的粒约简,同时给出获得相应约简的方法。许多学者研究粗糙集的属性约简和形式背景的属性约简之间的关系。Wei 等9将形式背景当作一个属性值为 0 和 1 的信息系统,并研究了形式背景属性约简和信息系统绝对约简之间的关系。Liu 等10研究了面向对象的概念格的属性约简与信息系统的属郑 州 大 学 学 报(理 学 版)第 56 卷性约简之间的关系。Li 等11定义了形式背景的不可约简属性类,并用不可约简属性类刻画了形式背景的核心属性集、相对必要属性集和冗余属性集,同时给出了约简的判定定理。Ren 等12研究了三支概念格的属性约简问题,在对象导出三支概念格和属性导出三支概念格中分别定义了 4 种约简,并研究了约简之间的关系,同时给出了其中 7 种约简的计算方法。魏玲等13研究了强协调决策形式背景和弱协调决策形式背景的约简定义和约简方法。决策形式背景的提出,进一步丰富了形式概念分析的理论,得到了学术界的广泛关注。Li 等14面向规则提取,定义了决策形式背景的约简,并给出计算所有约简的算法。在文献8中,Wu 等定义了一致决策形式背景 的粒约简并 给出相应约 简算 法。Wang等15基于辨识矩阵,给出了计算广义一致决策形式背景约简的算法。相对一致决策形式背景而言,不一致决策形式背景在实际应用中更为常见,因此研究一般决策形式背景的属性约简更具有现实意义。基于此,本文给出一般决策形式背景的属性约简的定义,并利用辨识函数给出计算所有约简的算法。该算法可应用于一致决策形式背景和不一致决策形式背景。特别地,文献13中的强协调决策形式背景的约简是我们算法的特例。1形式概念分析的基本定义及性质本节介绍形式概念分析的基础知识,包括形式背景、决策形式背景、概念、概念格的定义及相关性质。定义 11形式背景是一个三元组(U,A,I),U是非空有限对象集,A 是非空有限属性集,I 是 U 和A 之间的二元关系,即 I U A。对于一个形式背景(U,A,I),可在对象集和属性集上定义两个运算16,X U,X=a Ax X,xIa,B A,B=x Ub B,xIb,其中:X表示 X 中所有对象所具有的共同属性的最大集合;B表示具有 B 中所有属性的对象的最大集合。特别地,对于 x X,b B,将 x和 b分别简记为 x和 b,显然有 X=xXx,B=bBb。设(U,A,I)为一个形式背景,对于 B A,令IB=I (U B),则(U,B,IB)也是一个形式背景6。为了区分不同形式背景下的“”运算,我们分别用“A”和“B”表示形式背景(U,A,I)和(U,B,IB)中的“”运算。对于 C B A,容易证明有 CA=CB 8。设(U,A,I)为一个形式背景,其中对象集为U=x1,x2,xm,属性集为 A=a1,a2,an。将(U,A,I)视为一张 m 行 n 列的信息表,其中信息表中元素的值域为 0,1。若信息表中第 i 行第 j列的元素为 1,则表示(xi,aj)I,即对象 xi具有属性 aj,反之则表示(xi,aj)I,即对象 xi不具有属性 aj。若形式背景(U,A,I)对应的信息表的每行每列既有 0 又有 1,则称(U,A,I)是正则的6。本文研究的形式背景在约简前均为正则的。定义 216假设(U,A,I)为形式背景,X U,B A,若 XA=B 且 BA=X,则称二元组(X,B)为形式背景(U,A,I)的概念,称 X 为概念(X,B)的外延,B 为概念(X,B)的内涵。记形式背景(U,A,I)的全体概念为 L(U,A,I),即 L(U,A,I)=(X,B)X U,B A,XA=B,BA=X;记全体概念的外延集为 LU(U,A,I),即LU(U,A,I)=X UB A,(X,B)L(U,A,I)。对于任意(X1,B1),(X2,B2)L(U,A,I),定义 L(U,A,I)上的偏序关系为(X1,B1)(X2,B2)X1 X2B2 B1。若(X1,B1),(X2,B2)L(U,A,I),在 L(U,A,I)上分别定义上、下确界为(X1,B1)(X2,B2)=(X1 X2,(B1 B2)AA),(X1,B1)(X2,B2)=(X1 X2)AA,B1 B2),则 L(U,A,I)为完备格,称之为形式背景(U,A,I)的概念格。性质 1假设(U,A,I)为形式背景,对于 X,X1,X2 U 和 B,B1,B2 A,容易证明有性质1)5)16:1)X1 X2X1A X2A,B1 B2B1AB2A;2)X BAB XA;3)X XAA,B BAA;4)XA=XAAA,BA=BAAA;5)(XAA,XA)L(U,A,I),(BA,BAA)L(U,A,I)。定义 36设(U,A1,I1)和(U,A2,I2)为形式背景,若 LU(U,A2,I2)LU(U,A1,I1),则称 L(U,A1,I1)细于 L(U,A2,I2),记为 L(U,A1,I1)L(U,A2,I2)。67第 1 期谢业海,等:一般决策形式背景的属性约简若 L(U,A1,I1)L(U,A2,I2),那么对于任意(X2,B2)L(U,A2,I2),总存在(X1,B1)L(U,A1,I1)使得 X1=X2。设(U,A,I)为形式背景,B A,那么不难验证有 L(U,A,I)L(U,B,IB)6。定义 4令(U,A,I)和(U,T,J)为形式背景,则称五元组(U,A,I,T,J)为决策形式背景13。其中,A 是条件属性集,T 是决策属性集。若 L(U,A,I)L(U,T,J),则称(U,A,I,T,J)为一致的决策形式背景,反之则称(U,A,I,T,J)为不一致的决策形式背景。定义 4 中的一致决策形式背景即是文献13中定义的强协调决策形式背景。2一般决策形式背景的广义约简对一般决策形式背景,定义一种新的约简,该约简是强协调决策形式背景的约简的扩展。需要指出的是,作为一个特例,用本节提出的约简算法,可获得强协调决策形式背景的所有约简。设(U,A,I,T,J)为决策形式背景,对于 B A,记 VB=LU(U,B,IB)LU(U,T,J),于是VA=LU(U,A,I)LU(U,T,J)。定义 5 令(U,A,I,T,J)为 决策形式 背 景,B A,若 B 满足1)VA=VB,2)对于任意 C B,那么 VC VA,则称 B 为决策形式背景(U,A,I,T,J)的约简。特别地,若(U,A,I,T,J)为一致决策形式背景,那么 VA=LU(U,T,J),则 VA=VB等价于 L(U,B,IB)L(U,T,J)。引理 1假设(U,A,I)为形式背景,则有1)a A,(aA,aAA)L(U,A,I);2)若(X,B)L(U,A,I),X U,那么 X=aBaA;3)X LU(U,A,I)且 X U B A 使X=aBaA。证明 1)对于 a A,根据性质 1 中的 4)有aA=aAAA,那么有(aA,aAA)L(U,A,I)。2)若(X,B)L(U,A,I),X U,那么由定义2 有 X=BA,又 BA=aBaA,所以 X=aBaA。3)“”:假设 X LU(U,A,I)且 X U,也就是 B A,有(X,B)L(U,A,I),那么由 2)有X=aBaA。“”:对于 a A,由 1)有(aA,aAA)L(U,A,I),那么有 aB(aA,aAA)=(aBaA,(aBaAA)AA)L(U,A,I),所以 aBaA LU(U,A,I),在正则形式背景中,显然有 aBaA U,所以令X=aBaA即可得证。定理 1设(U,A,I,T,J)为决策形式背景,对于任意 B A,条件 1)和 2)等价:1)VA=VB;2)对于 X VA且 X U,存在 C B,使得X=CA。证明 1)2):若 VA=VB,对于 X VA且 X U,有 X VB,也就是 C B 使(X,C)L(U,B,IB)。由定义 2 可知有 X=CB,又 CA=CB,所以X=CA。2)1):由 B A,有 L(U,A,I)L(U,B,IB),也 就 是 LU(U,B,IB)LU(U,A,I),所 以VB VA。下面证 VA VB。当 X VA且 X=U 时,显然有 X VB。当 X VA且 X U 时,由 2)可知存在 C B 使得 X=CA,又由 CA=CB可推出 X=CB,由引理 1 中 3)可推出 X LU(U,B,IB),即X VB,所以有 VA VB。综上可得 VA=VB。推论 1 设(U,A,I,T,J)为决 策形式背 景,B A,则 B 是(U,A,I,T,J)的约简,当且仅当 B 是 A 的满足定理 1 中 2)的极小子集。在决策形式背景(U,A,I,T,J)中,对于 X VA且 X U,记(X)=C AX VA,X U,X=CA,min(X)=D (X)C (X),C D,C D。由推论 1 可得计算一般决策形式背景约简的算法。算法 1一般决策形式背景的约简算法输入:一般决策形式背景(U,A,I,T,J)。输出:全部约简。步骤 1计算 VA=LU(U,A,I)LU(U,T,J)。步骤 2对于 X VA且 X U,计算min(X)。步骤 3构造辨识函数 f=XVA,XU(Dmin(X)(dDd)。步骤 4利用吸收率和分配率,将辨识函数由合取范式转换为最小析取范式:f=ni=1(rRir),得到所有约简的集合 R1,R2,Rn。算法 1 中的辨识函数是一个由辨识矩阵诱导的单调布尔函数。辨识矩阵和辨识函数最初由 Skow-ron 等17应 用 于 粗 糙 集 的 属 性 约 简 中。设 M=(Cij)m n为一个辨识矩阵,其中矩阵中的元素 Cij为77郑 州 大 学 学 报(理 学 版)第 56 卷属性的集合,那么 M 可诱导一个辨识函数 f=(Cij):1 i m,1 j n,Cij。将辨识函数f 由合取范式转换为最小析取范式后,其中任意一个质蕴涵项中的所有属性组成的集合即为一个约简,所有质蕴含项对应的约简组成的集合即为所有约简的集合。在算法 1 中,根据定理 1 可知,对于 X VA且 X U,(X)=C AX VA,X U,X=CA是辨识函数 f 对应的辨识矩阵中的非空元素。由于在将辨识函数 f 转换为最小析取范式的过程中会使用吸收率,所以取 min(X)以简化计算过程。算法 1 中的步骤 2 是构造辨识函数的基础,也是本文的主要研究成果,所以仅讨论步骤 2 的时间复杂度。设(U,A,I,T,J)为一般决策形式背景,X VA且 X U,(X,B)L(U,A,I),记 B 的幂集为 P(B),步 骤 2 计 算 min(X)时,首 先 要 计 算(X)=C AX VA,X U,X=CA。为了计算出(X),对于 C P(B),要计算 CA并判断CA是否等于 X,若 CA=X,则将 C 作为元素加入集合(X)中,这也是步骤 2 中时间复杂度最高的环节,所以步骤 2 的时间复杂度为 O(UA2|A|)。用文献13中的约简方法对一致决策形式背景进行 约 简 时,计 算 辨 识 矩 阵 的 时 间 复 杂 度 为O(U+A)AL(U,T,J)18,低于算法 1 中步骤 2 的时间复杂度。但是算法 1 可应用于不一致决策形式背景的属性约简,因此比文献13中的方法应用范围更广。下面用一个例子对算法 1 进行说明。例 1设决策形式背景 =(U,A,I,T,J)如表1 所示,其中:对象集 U=1,2,3,4,5;条件属性集A=a,b,c,d,e;决策属性集 T=f,g,h。表 1一个不一致决策形式背景Table 1An inconsistent decision formal contextUabcdefgh111000001211101010301110100410101011501110101在决策形式背景 中,L(U,A,I)和 L(U,T,J)的哈斯图分别如图 1、图 2 所示。可以看到,形式背景(U,A,I)共有 10 个概念,形式背景(U,T,J)共有 7 个概念。由于(145,h)L(U,T,J)但 1,4,5 LU(U,A,I),所以 是不一致决策形式背景。约简的具体计算过程如下。第一步 计算得到 VA=,2,4,3,5,U。图 1例 1 中概念格 L(U,A,I)的哈斯图Figure 1The Hasse diagram of L(U,A,I)in example 1图 2例 1 中概念格 L(U,T,J)的哈斯图Figure 2The Hasse diagram of L(U,T,J)in example 1第二 步 对 于 X VA且 X U,计 算min(X)得min()=a,d,d,e,min2,4=e,a,c,min3,5=d。第三步构造辨识函数f=(a d)(d e)(e (a c)d。第四步将辨识函数转换为最小析取范式f=(a c d)(d e)。第五步得到所有约简为 a,c,d 和 d,e。令 B=a,c,d,约简后的概念格 L(U,B,IB)的哈斯图如图 3 所示。由图 1 3 可以看到,LU(U,A,I)=,2,1,2,2,4,3,5,1,2,4,2,3,5,1,2,3,5,2,3,4,5,U,LU(U,T,J)=,4,5,2,4,3,5,1,4,5,U,LU(U,B,IB)=,2,4,3,5,1,2,4,2,3,4,5,U,那么 VB=LU(U,B,IB)LU(U,T,J)=,2,4,3,5,U=VA,约简后有 VB=VA。B=a,c,d是一个约简。假设(U,A,I,T,J)为强协调决策形式背景,那87第 1 期谢业海,等:一般决策形式背景的属性约简么 VA=LU(U,T,J)。定理 2设(U,A,I,T,J)为强协调决策形式背景,对于任意 B A,条件 1)和 2)等价:1)VA=VB;2)L(U,B,IB)L(U,T,J)。证明由于(U,A,I,T,J)为强协调决策形式背景,那么有 VA=LU(U,T,J)。1)2):由 VA=VB=LU(U,B,IB)LU(U,T,J)及 VA=LU(U,T,J),有 LU(U,T,J)=LU(U,B,IB)LU(U,T,J),可以推出 LU(U,T,J)LU(U,B,IB),即 L(U,B,IB)L(U,T,J)。2)1):由 L(U,B,IB)L(U,T,J)可 得LU(U,T,J)LU(U,B,IB),那么 VB=LU(U,B,IB)LU(U,T,J)=LU(U,T,J),又由 VA=LU(U,T,J),所以 VA=VB。若(U,A,I,T,J)为强协调决策形式背景,则使用算法 1 和使用文献13 中的算法对(U,A,I,T,J)进行约简,得到的结果一致。下面引用文献13中的例子对定理 2 进行说明。例 2设决策形式背景 =(U,A,I,T,J)如表2 所示,其中对象集 U=1,2,3,4,5,条件属性集A=a,b,c,d,e,决策属性集 T=f,g,h。表 2一个一致决策形式背景Table 2A consistent decision formal contextUabcdefgh110101001211011100311001100401110011501110011在决策形式背景 中,L(U,A,I)和 L(U,T,J)的哈斯图分别如图 4、图 5 所示,可以看到(U,A,I)共有 10 个概念,(U,T,J)共有 5 个概念。不难看出,为一致决策形式背景。约简的具体计算过程如下。第一步计算得到 VA=,2,3,4,5,1,4,5,U。第二 步 对 于 X VA且 X U,计 算min(X)得min()=a,b,c,b,c,e,c,d,e,a,c,d,min(23)=a,b,b,e,min(45)=b,c,c,d,min(145)=c。第三步计算辨识函数得到f=(a b c)(b c e)(c d e)(a c d)(a b)(b e)(b c)(c d)c。第四步将辨识函数转换为最小析取范式f=(a b c)(b c e)。第五步 得到所有约简为 a,b,c 和 b,c,e。可以看到,算法 1 的约简结果与文献13中的一致。令 B=a,b,c,约简后的概念格 L(U,B,IB)的哈斯图如图 6 所示,不难验证 VB=VA。3结论本文研究一般决策形式背景的属性约简方法,提出一般决策形式背景的属性约简的定义,并给出可计算所有约简的算法。未来,我们将从信息损失、计算效率等方面对比约简前、后决策形式背景在不同应用场景中的区别。图 3例 1 中概念格 L(U,B,IB)的哈斯图Figure 3The Hasse diagram of L(U,B,IB)in example 1图 4例 2 中概念格 L(U,A,I)的哈斯图Figure 4The Hasse diagram of L(U,A,I)in example 2图 5例 2 中概念格 L(U,T,J)的哈斯图Figure 5The Hasse diagram of L(U,T,J)in example 297郑 州 大 学 学 报(理 学 版)第 56 卷图 6例 2 中概念格 L(U,B,IB)的哈斯图Figure 6The Hasse diagram of L(U,B,IB)in example 2参考文献:1WILLE R.Restructuring lattice theory:an approach based on hierarchies of conceptsMRIVAL I.Ordered Sets.Dordrecht:Springer Press,1982:445-470.2CARPINETO C,ROMANO G.A lattice conceptual clus-tering system and its application to browsing retrievalJ.Machine learning,1996,24(2):95-122.3李金海,梅长林,张红英,等.基于遗传算法的决策形式背景的属性约简方法及其在决策分析中的应用J.小型 微 型 计 算 机 系 统,2015,36(8):1803-1808.LI J H,MEI C L,ZHANG H Y,et al.Attribute reduc-tion method for formal decision contexts based on genetic algorithm and its application to decision-making analysisJ.Journal of Chinese computer systems,2015,36(8):1803-1808.4万仁霞,高艳龙.基于粗糙集约简与狮群优化算法的机器人路径规划研究J.郑州大学学报(理学版),2022,54(2):32-38.WAN R X,GAO Y L.Robot path planning based on rough set reduction and lion swarm optimization J.Journal of Zhengzhou university(natural science edi-tion),2022,54(2):32-38.5王君宇,杨亚锋,赵佳亮,等.基于粒化可拓决策的属性约简算 法 研 究 J.郑 州 大 学 学 报(理 学 版),2022,54(5):72-81.WANG J Y,YANG Y F,ZHAO J L,et al.Research on attribute reduction algorithm based on granulation exten-sion decisionJ.Journal of Zhengzhou university(natu-ral science edition),2022,54(5):72-81.6ZHANG W X,WEI L,QI J J.Attribute reduction theory and approach to concept latticeJ.Science in China se-ries F:information sciences,2005,48(6):713-726.7QI J J.Attribute reduction in formal contexts based on a new discernibility matrix J.Journal of applied mathe-matics and computing,2009,30(1):305-314.8WU W Z,LEUNG Y,MI J S.Granular computing and knowledge reduction in formal contextsJ.IEEE trans-actions on knowledge and data engineering,2009,21(10):1461-1474.9WEI L,QI J J.Relation between concept lattice reduc-tion and rough set reductionJ.Knowledge-based sys-tems,2010,23(8):934-938.10 LIU M,SHAO M W,ZHANG W X,et al.Reduction method for concept lattices based on rough set theory and its applicationJ.Computers&mathematics with appli-cations,2007,53(9):1390-1410.11 LI T J,WU W Z.Attribute reduction in formal contexts:a covering rough set approachJ.Fundamenta informati-cae,2011,111(1):15-32.12 REN R S,WEI L.The attribute reductions of three-way concept lattices J.Knowledge-based systems,2016,99:92-102.13 魏玲,祁建军,张文修.决策形式背景的概念格属性约简J.中国科学(E 辑:信息科学),2008,38(2):195-208.WEI L,QI J J,ZHANG W X.Attribute reduction of concept lattice in decision-making formal backgroundJ.Science in China(series E:information sciences),2008,38(2):195-208.14 LI J H,MEI C L,LV Y J.Knowledge reduction in deci-sion formal contexts J.Knowledge-based systems,2011,24(5):709-715.15 WANG H,ZHANG W X.Approaches to knowledge re-duction in generalized consistent decision formal contextJ.Mathematical and computer modelling,2008,48(11/12):1677-1684.16 GANTER B,WILLE R.Formal concept analysis:mathe-matical foundationsM.Berlin:Springer Press,1999.17 SKOWRON A,RAUSZER C.The discernibility matrices and functions in information systems M.Dordrecht:Springer Press,1992:331-362.18 NOURINE L,RAYNAUD O.A fast algorithm for build-ing latticesJ.Information processing letters,1999,71(5/6):199-204.08