基于集覆盖理论的覆盖信息系统属性约简方法.pdf

第 56 卷第 1 期郑 州 大 学 学 报(理 学 版)Vol.56 No.12024 年 1 月J.Zhengzhou Univ.(Nat.Sci.Ed.)Jan.2024收稿日期:2022-09-04基金项目:国家自然科学基金项目(11871259,62076221);福建省自然科学基金项目(2019J01748,2022J01912)。第一作者:徐晔(1997),男,硕士研究生,主要从事数据挖掘、粗糙集理论及应用研究,E-mail:3108427877 。通信作者:许晴媛(1977),女,教授,主要从事粗糙集、概念格、学习空间理论及应用研究,E-mail:xqyyuan871 。基于集覆盖理论的覆盖信息系统属性约简方法徐晔1,2,许晴媛1,2,李进金3,4(1.闽南师范大学 计算机学院福建 漳州 363000;2.闽南师范大学 数据科学与智能应用福建省高校重点实验室福建 漳州 363000;3.闽南师范大学 数学与统计学院福建 漳州 363000;4.闽南师范大学 福建省粒计算及其应用重点实验室福建 漳州 363000)摘要:针对覆盖信息系统属性约简问题,提出基于集覆盖理论的覆盖信息系统属性约简方法。首先,构造覆盖信息系统的相关矩阵,通过相关矩阵诱导出覆盖信息系统的集覆盖模型,并探讨了覆盖信息系统与其诱导的集覆盖模型之间的联系,发现集覆盖模型的一个极小覆盖恰是原覆盖信息系统的一个属性约简集,从而可以将求解覆盖信息系统的属性约简问题转化为求解对应集覆盖模型的极小集覆盖问题。其次,利用集覆盖启发式算法(set covering heuristic algorithm,SCHA)在解决集覆盖问题上具有更高的精度和更好的性能,给出了基于 SCHA 的覆盖信息系统属性约简的求解步骤及算法。最后,通过实例验证了所提方法的可行性和有效性。关键词:集覆盖;覆盖信息系统;集覆盖启发式算法;属性约简;粗糙集中图分类号:TP182文献标志码:A文章编号:1671-6841(2024)01-0060-08DOI:10.13705/j.issn.1671-6841.2022264 Attribute Reduction Method for Covering Information System Based on Set Covering TheoryXU Ye1,2,XU Qingyuan1,2,LI Jinjin3,4(1.School of Computer Science,Minnan Normal University,Zhangzhou 363000,China;2.Key Laboratory of Data Science and Intelligent Application in Fujian Provincial Universities,Minnan Normal University,Zhangzhou 363000,China;3.School of Mathematics and Statistics,Minnan Normal University,Zhangzhou 363000,China;4.Fujian Key Laboratory of Granular Computing and Application,Minnan Normal University,Zhangzhou 363000,China)Abstract:Aiming at the problem of attribute reduction in covering information systems,an attribute re-duction method for covering information systems based on set covering theory was proposed.Firstly,the correlation matrix of the covering information system was constructed,the set covering model of the cover-ing information system was induced by the correlation matrix and the relationship between the covering in-formation system and its induced set covering model was discussed.It was found that a minimal covering of the set covering model was exactly an attribute reduction set of the original covering information sys-tem,and the problem of attribute reduction in covering information system could be transformed into the problem of minimum covering of corresponding set covering model.Secondly,the set covering heuristic algorithm(SCHA)had higher accuracy and better performance in solving the set covering problem,and the steps and algorithm for solving the attribute reduction of covering information system based on SCHA were presented.Finally,the feasibility and effectiveness of the proposed method were verified by an ex-ample.第 1 期徐晔,等:基于集覆盖理论的覆盖信息系统属性约简方法Key words:set covering;covering information system;set covering heuristic algorithm;attribute reduc-tion;rough set0引言粗糙集理论是用于处理各种不确定性信息的有效工具1-2,已成功应用在机器学习、模式识别等人工智能领域。然而,现实中的各类信息系统具有不同类型的属性,如数值属性、集值属性、缺失属性等,经典粗糙集理论在处理这些数据时具有局限性。因此,人们提出许多方法去推广经典粗糙集理论,例如多粒度近似空间的模糊粗糙集3、多粒度决策粗糙集4、覆盖粗糙集5等。其中,覆盖粗糙集是一个比较重要的推广方向。覆盖信息系统属性约简问题是覆盖粗糙集方向的重要研究课题,探索覆盖信息系统的属性约简方法是当前的研究热点6-10。其中,文献6 通过产生相同上、下近似最小覆盖的方法得到属性约简,为覆盖信息系统属性约简提供了一种有效的方法;文献7 利用区分矩阵求解覆盖信息系统的属性约简;文献8在文献6的基础上利用信息熵刻画了覆盖约简的粗糙性。集覆盖问题是一个优化问题,已广泛应用于航空人员调度、运输车辆路线安排、服务位置、制造作业分配、操作人员选择等领域。解决集覆盖问题的经典算法有人工蜂群算法11、DNA 计算方法12、贪心算法13及近似算法14等。改进集覆盖问题的经典算法是当前的研究热点15-17,例如文献16针对unicost 集覆盖问题,提出一种改进的基于配置检查的算法。近年来,出现了集覆盖问题与粗糙集属性约简问题的交叉研究。其中,文献18提出利用集覆盖问题解决传统粗糙集属性约简问题;文献19-20提出利用集覆盖问题解决粗糙集扩展领域的属性约简问题。反过来,利用粗糙集理论来解决集覆盖问题的方法也相继被提出21-24。本文提出一种把覆盖信息系统的属性约简问题转化为集覆盖问题的方法,并应用集覆盖理论来研究覆盖信息系统的属性约简问题。通过构造覆盖信息系统的相关矩阵诱导出覆盖信息系统的集覆盖模型,进而建立集覆盖问题与覆盖信息系统属性约简问题之间的联系,得出集覆盖模型的一个极小覆盖恰是原覆盖信息系统的一个属性约简集,从而可以借助高效的集覆盖理论来求解覆盖信息系统的属性约简问题。集覆盖启发式算法(set covering heuristic algorithm,SCHA)25在解决集覆盖问题上具有较高的精度与较好的性能,本文给出了基于 SCHA 求解覆盖信息系统属性约简的算法,并通过一个实例验证了所提方法的可行性和有效性。本文工作丰富了集覆盖理论与覆盖粗糙集理论的交叉研究,为覆盖信息系统的属性约简问题带来了新的思路与方法,同时拓展了集覆盖理论的应用领域。1基本概念1.1集覆盖问题定义 1设 E=xq:1 q y 是一个非空有限对象集合,S=Sw:1 w r 是 E 的若干非空子集构成的集族。若 S=E,则称 S 为 E 的一个集覆盖,称(E,S)为一个集覆盖模型。集覆盖问题在于求解 S 的一个非空子集 S,使得 S=E,且 S的任意真子集都不是 E 的覆盖。S 也称为 E 关于覆盖 S 的一个极小覆盖。1.2覆盖信息系统及其属性约简问题定义 226给定一个论域 U=xi:1 i n,设 C=Xk:Xk U,1 k t。如果 C 中的所有子集都不为空,且 C=U,则称 C 是 U 的一个覆盖。定义 326设 U=xi:1 i n,C=Xk:1 k t 是 U 的一个覆 盖。xi U,记(xi)C=Xk:Xk C,xi Xk,记 Cov(C)=(xi)C:xiU,则 Cov(C)也是 U 的一个覆盖,称 Cov(C)为 C诱导的覆盖。定义 426设 =Cj:1 j m 是论域 U 上的一 族 覆 盖。对 于 任 意 的 x U,记(x)=(x)Cj:1 j m,称 Cov()=(x):x U为 诱导的覆盖,称(U,)为一个覆盖信息系统。设 ,若对于任意的 x U,有(x)(x),则记 Cov()Cov()。定义 5给定一个论域 U=xi:1 i n,设=Cj:1 j m 是论域 U 上的一族覆盖,定义 U上的一个关系 R=(xo,xp):xo(xp),xo U,xp U。定义 6设 =Cj:1 j m 是论域 U 上的一族覆盖,(U,)是一个覆盖信息系统。对于任意的 P ,若 Cov(P)Cov(),则称 P 是(U,)的16郑 州 大 学 学 报(理 学 版)第 56 卷一个覆盖协调集。若对于 Cj P,Cov(P-Cj)Cov()均不成立,则称 P 是(U,)的一个覆盖约简集。定义 7设(U,)是一个覆盖信息系统,若P=Pz:1 z e 是(U,)的所有约简集,则称Core()=P1 P2 Pn 是(U,)的核属性集。2覆盖信息系统的集覆盖模型在本节中首先定义关于覆盖信息系统(U,)的相关矩阵 M,然后通过矩阵 M 诱导出关于覆盖信息系统(U,)的集覆盖模型(U,S),并给出覆盖信息系统(U,)与其诱导的集覆盖模型(U,S)之间的一些联系。定义 8设(U,)是一个覆盖信息系统,U=xi:1 i n,=Cj:1 j m,R=(xo,xp):xo(xp),xo U,xp U。令 U=(xp,xo):(xp,xo)R,xp U,xo U,记 U=ui:1 i n2-R。定义一个 f 行 m 列的矩阵 M,其中 f=n2-R,M 中的行由 U 中元素构成,M 中的列由 中元素构成,M 的第 i 行第 j 列元素 Mij取值为 Mij=1,xo(xp)Cj,0,否则,称 M 为覆盖信息系统(U,)的相关矩阵。注:因为 U=xi:1 i n 中有 n 个元素,U中的元素为(xp,xo)的形式,所以 U 中元素个数最多为 n2个。由于 U=(xp,xo):(xp,xo)R,xpU,xo U,故 U 中元素个数等于 f=n2-R。定理 1设(U,)是一个覆盖信息系统,M 为(U,)的相关矩阵,M 中不存在所有列的值全为 0的行。证明设存在第 i 行所有列的值全为 0,ui=(xp,xo)U,则对于 Cj,Mij=0,有 xo(xp)Cj。根据(x)=(x)Cj:1 j m,可得xo(xp)。根据定义 5,ui=(xp,xo)R,与定义 8 中 U=(xp,xo):(xp,xo)R,xp U,xo U矛盾。因此,矩阵 M 中不存在所有列的值全为 0的行。定理 2设(U,)是一个覆盖信息系统,M 为(U,)的相关矩阵。令 ui=(xp,xo)U,若 Mij=1,则 Cj可以区分对象对 ui=(xp,xo)U。证明令 ui=(xp,xo)U,若存在 Mij=1,则存在 Cj 使得 xo(xp)Cj,故 xo(xp)。因此,Cj可以区分对象对 ui=(xp,xo)U。推论 1设(U,)是一个覆盖信息系统,U=(xp,xo):(xp,xo)R,xp U,xo U=ui:1 i n2-R。对于 U 中的任意一个元素 ui=(xp,xo),都存在一个覆盖 Cj使得 xo(xp)Cj。证明由定理 1 与定理 2 容易得证。接下来,给出一个由覆盖信息系统诱导的区分集合的定义。定义 9设(U,)是一个覆盖信息系统,U=ui:1 i n2-R,令 SCj=ui:Mij=1,uiU,则 SCj为 U 中所有能被 Cj区分的 ui构成的集合,称 SCj为 Cj诱导的区分集合。定理 3设(U,)是一个覆盖信息系统,=Cj:1 j m,U=(xp,xo):(xp,xo)R,xpU,xo U=ui:1 i n2-R。所有 Cj诱导的区分 集 合 的 并 集 构 成 U 的 一 个 集 覆 盖,即mj=1SCj=U。证明 1)充分性。假设存在一个 ui=(xp,xo)U,且 uimj=1SCj,则不存在一个 Cj,使得 xo(xp)ci,xo(xp),与推论 1 矛盾,故 U mj=1SCj成立。2)必 要 性。假 设 存 在 一 个 ui=(xp,xo)mj=1SCj,且 ui U,则根据推论 1,ui=(xp,xo)mj=1SCj,必存在一个 Cj 使得 xo(xp)Cj,则 xo(xp),ui=(xp,xo)R,与定义 8 中 U=(xp,xo):(xp,xo)R,xp U,xo U 矛 盾,因 此mj=1SCj U。由 1)和 2)得出 mj=1SCj=U。称 mj=1SCj为覆盖信息系统(U,)诱导的 U 的集覆盖。令 S=SCj:1 j m,称(U,S)为覆盖信息系统(U,)诱导的集覆盖模型。定理 4设(U,)是一个覆盖信息系统,=Cj:1 j m,U=(xp,xo):(xp,xo)R,xpU,xo U,S=SCj:1 j m,(U,S)为(U,)诱导的集覆盖模型。S S 是集覆盖模型(U,S)的一个集覆盖,当且仅当 P=Cj:SCj S 是覆盖信息系统(U,)的一个覆盖协调集。证明 1)充分性。设 S S 是集覆盖模型(U,S)的一个集覆盖,则 S=U。令 P=Cj:SCj S,由定义 6 可知,要证明 P 是(U,)的一26第 1 期徐晔,等:基于集覆盖理论的覆盖信息系统属性约简方法个覆盖协调集,需要证明 Cov(P)Cov(),即需要证明对于 xq U,有 P(xq)(xq)。对于(xq,xo)U,由定义 8 可得 xo(xq)。又由于 U=S,故(xq,xo)S,从而 Cj P,使得xo(xq)Cj,故 xo P(xq),所以 P(xq)(xq),则 Cov(P)Cov()。因此,P 是(U,)的一个覆盖协调集。2)必要性。设 P 是覆盖信息系统(U,)的一个覆盖协调集,Cov(P)Cov(),则 xqU,有 P(xq)(xq)。令 S=SCi:Ci P,对于(xq,xo)U,根据定义 8 可得 xo(xq),从而 xo P(xq),(xq,xo)S,故 U S。因 S=SCi:Ci P U,从而 S=U,即 S 是集覆盖模型(U,S)的一个集覆盖。推论 2设(U,)是一个覆盖信息系统,=Cj:1 j m,U=(xp,xo):(xp,xo)R,xpU,xo U,S=SCj:1 j m,(U,S)为(U,)的集覆盖模型。S S 是集覆盖模型(U,S)的一个极小集覆盖,当且仅当 P=Cj:SCj S 是覆盖信息系统(U,)的一个覆盖约简集。证明由定理 4 容易得证。3基于集覆盖模型的覆盖信息系统约简算法由上述讨论可知,求解覆盖信息系统的属性约简问题可以转化为求解集覆盖模型的极小集覆盖问题。本文选择 SCHA 来求解覆盖信息系统的属性约简,其在解决 SCP 上具有更高的精度与更好的性能。下面给出 SCHA 中用于解决 SCP 的 4 个完备策略。完备策略 1:设 E=xq:1 q y,S=Sw:1 w r,若 Sw=E,则选择 Sw作为最优化覆盖中唯一一个集合 Sw。完备策略 2:设 x E,x 只属于 Sw,Sw S,则选择 Sw作为最优化覆盖中的一个集合元素。完备策略 3:若 Sw和 Sw,Sw Sw,Sw Sw,则Sw可以被排除。完备策略 4:设 xp,xq E,xp xq,用 Sn(xp)来表示所有含 xp的 Sw的集合,若 Sn(xp)Sn(xq),则可以将 xq从 E 中删除。接下来,给出基于 SCHA 的覆盖信息系统属性约简问题的求解步骤。输入:一个覆盖信 息系统(U,),其 中 U=xi:1 i n,=Cj:1 j m。输出:覆 盖 信 息 系 统(U,)的 一 个 约 简RED。步骤 1:令 RED=。步骤 2:根据定义 8 构造(U,)的相关矩阵M,设矩阵 M 的行数和列数分别为、。步骤 3:对于矩阵 M 的第 j 列(j=1,2,),计算此列中所有行的元素和,若此列中所有行的元素和等于,则 RED=RED Cj,转到步骤 8。步骤 4:对于矩阵 M 的第 i 行(i=1,2,),计算此行中所有列的元素和,若此行中所有列的元素和为 1,则找出该行中元素值等于 1 的列,设该列为 Sj,则 RED=RED Cj,将此列从矩阵中删除,令 =-1,更新矩阵。步骤 5:对于矩阵 M 中任意两列 j、j,若对于任意 Mij=1,都有 Mij=1 且i=1Miji=1Mij,则将第 j 列从矩阵中删除,令 =-1,更新矩阵。步骤 6:对于矩阵 M 中任意两行 i、i,若对于任意 Mij=1,都有 Mij=1 且j=1Mijj=1Mij,则将第 i 行从矩阵中删除,令 =-1,更新矩阵。步骤 7:找到矩阵 M 中所有行元素和最大的列,假定为第 j 列,令 RED=RED Cj,将 i 从 1一直取到,去除 Mij=1 所在的行,并且在遍历结束后去除第 j 列,令 =-,=-1,更新矩阵,并返回步骤 3。步骤 8:输出 RED。在基于 SCHA 求解覆盖信息系统(U,)的属性约简前,首先需要获得(U,)的相关矩阵 M,下面给出生成覆盖信息系统(U,)的相关矩阵 M 的求解算法。算法 1生成覆盖信息系统相关矩阵的算法输入:一个覆盖信息系统(U,),其中 U=xi:1 i n,=Cj:1 j m。输出:覆盖信息系统(U,)的相关矩阵 M。1:for(p=1;p=n;p+)2:for(o=1;o=n;o+)3:i=1,a=0;4:for(j=1;j=m;j+)5:if(xo(xp)Cj)6:Mij=1;7:a=a+1;8:else 9:Mij=0;36郑 州 大 学 学 报(理 学 版)第 56 卷10:11:end for12:if(a=0)删除第 i 行;13:elsei=i+1;14:end for15:end for注:在算法 1 中,a 代表可以区分(xp,xo)的 Cj的个数。若 a=0,则表示所有 Cj均不能区分(xp,xo),故第 12 行相当于删去 R 中元素。算法最终得到 U=(xp,xo):(xp,xo)R,xp,xo U。根据上述基于 SCHA 的覆盖信息系统属性约简问题的求解步骤,下面给出基于 SCHA 求解覆盖信息系统一个属性约简的相关算法。算法 2基于 SCHA 的覆盖信息系统属性约简算法输入:一个覆盖信息系统(U,),其 中 U=xi:1 i n,=cj:1 j m。输出:覆盖信息系统(U,)的一个属性约简。1:求(U,)的相关矩阵 M;2:RED=;3:=矩阵 M 的行数;4:=矩阵 M 的列数;5:HasGetRED=false;6:while(HasGetRED=false)7:for(j=1;j=RED SCj;j+)8:if(当前 Cj列所有行的元素和=)9:RED=RED SCj;10:HasGetRED=true;11:return RED;算法结束12:end if13:end for14:for(i=1;i=;i+)15:if(第 i 行所有列的元素和=1)16:Mark=元素值为 1 的元素对应的列号;17:RED=RED SMark;18:M=M 删除 Mark 列;19:=-1;20:end if21:end for22:for(j=1;j=;j+)23:for(j=j;j=;j+)24:if(第 j 列元素为 1 的元素所在的行构成的集合 第 j 列元素为 1 的元素所在的行构成的集合)25:M=M 删除第 j 列;26:S=S-SCj;27:=-1;28:end if29:end for30:end for31:for(i=1;i=;i+)32:for(i=i;i=;i+)33:if(第 i 行元素为 1 的元素所在的列构成的集合第 i 行元素为 1 的元素所在的列构成的集合)34:M=M 删除第 i 行;35:=-1;36:end if37:end for38:end for39:Mark=所有行元素和最大的列号;40:RED=RED SMark;41:=Mark 列所有行的元素和;42:Mark2 Mark 列元素值为 1 的元素对应行号的集合;43:M M 删除 Mark2中的行;44:=-;45:=-1;46:S=S-SMark;47:end while48:将 RED 中的 SCj转化成对应的 Cj存入 P 中。注:在算法 2 中,第 2 行对应基于 SCHA 的覆盖信息系统属性约简问题的求解步骤 1,第 3 行、第 4行对应求解步骤 2,第 5 13 行对应求解步骤 3,第1421 行对应求解步骤 4,第 22 30 行对应求解步骤 5,第 3138 行对应求解步骤 6,第 3947 行对应求解步骤 7,第 48 行对应求解步骤 8。设 m 为(U,)的相关矩阵 M 的行数,n 为(U,)的相关矩阵 M 的列数,则完备策略 1 的时间复杂度 为 O(mn),完 备 策 略 2 的 时 间 复 杂 度 为O(mn),完备策略 3 的时间复杂度为 O(m2n),完备策略 4 的时间复杂度为 O(mn2)。文献7提出的覆盖信息系统约简方法是目前较新的方法之一,与文献7不同,本文不需要构造区分矩阵,并且若给定的覆盖信息系统具有符合完备策略 1 的属性,则本文算法将不再进行后续完备策略 24 的计算,即算法的时间复杂度有可能最小为 O(mn)。46第 1 期徐晔,等:基于集覆盖理论的覆盖信息系统属性约简方法4实例例 1考虑房子评估问题。价格,结构,颜色,环境为 4 个待评估属性集,价格属性值域为高,中,低,结构属性值域为合理,一般,差,颜色属性值域为好,差,环境属性值域为安静,轻度吵闹,吵闹,非常吵闹。设有 6 套房子 U1=x1,x2,x3,x4,x5,x6,表 1 是某公司若干位专家对这 6 套房子的评估信息表(注:每位专家的评估数据都十分重要,故会出现有的房子某个属性取值为整个值域的情况。例如,房子 x3、x4和 x6的价格属性值域均为高,中,低)。为了方便公司对房子进行评估,需要筛选掉冗余属性集(不影响最终分类结果的属性),以减轻评估的工作量。表 1房子评估信息表Table 1House appraisal information sheetU1价格结构颜色环境x1高合理好安静x2高合理所有安静,轻度吵闹x3所有合理所有安静,轻度吵闹x4所有合理差轻度吵闹x5低合理差轻度吵闹x6所有合理,一般所有所有注:所有表示包含该属性值域中所有属性。用 C1代表价格属性,C1中各元素分别代表价格为高、中、低 的 房 子 集 合,C1=x1,x2,x3,x4,x6,x3,x4,x6,x3,x4,x5,x6。用 C2代表结构属性,C2中各元素分别代表结构为合理、一般、差的房子集合,C2=x1,x2,x3,x4,x5,x6,x6。用 C3代表颜色属性,C3中各元素分别代表颜色为好、差的房子集合,C3=x1,x2,x3,x6,x2,x3,x4,x5,x6。用 C4代表环境属性,C4中各元素分别代表环境为安静、轻度吵闹、吵闹、非常吵闹的房子集合,C4=x1,x2,x3,x6,x2,x3,x4,x5,x6,x6。C1,C2,C3,C4构成 U1的一个覆盖族,令 1=C1,C2,C3,C4,则(U1,1)是一个覆盖信息系统。可得 1(x1)=x1,x2,x3,x6,1(x2)=x2,x3,x6,1(x3)=x3,x6,1(x4)=x3,x4,x6,1(x5)=x3,x4,x5,x6,1(x6)=x6。通过算法 1 可以得出此覆盖信息系统(U1,1)的相关矩阵 M1,如表 2 所示。利用算法 2 对矩阵 M1不断进行简化,可以得表 2覆盖信息系统(U1,1)的相关矩阵 M1Table 2The correlation matrix M1 of covering information system(U1,1)U1SC1SC2SC3SC4U1SC1SC2SC3SC4u10011u111000u21011u121000u30011u131011u40011u141000u51011u151111u61011u161101u71010u170101u80011u180111u91011u191111u101011注:表中 u1=x1,x4,u2=x1,x5,u3=x2,x1,u4=x2,x4,u5=x2,x5,u6=x3,x1,u7=x3,x2,u8=x3,x4,u9=x3,x5,u10=x4,x1,u11=x4,x2,u12=x4,x5,u13=x5,x1,u14=x5,x2,u15=x6,x1,u16=x6,x2,u17=x6,x3,u18=x6,x4,u19=x6,x5。到覆盖信息系统(U1,1)的覆盖约简集 RED1,具体情况如下。1)通过遍历矩阵 M1,没有发现符合基于 SCHA的求解步骤 3 的列,则从求解步骤 4 开始分析。通过基于 SCHA 的求解步骤 4 发现,矩阵 M1第 11 行所有列的元素和为 1,其值为 1 的列为 SC1,将第 1 列从矩阵 M1中删除,并将 SC1并入 RED1中,得到更新矩阵M2,如表 3 所示。表 3经过求解步骤 4 后的更新矩阵 M2Table 3The update matrix M2 after solving step 4U1SC2SC3SC4U1SC2SC3SC4u1011u11000u2011u12000u3011u13011u4011u14000u5011u15111u6011u16101u7010u17101u8011u18111u9011u19111u10011注:表中 u1至 u19代表的元素与表 2 相同。2)继续进行基于 SCHA 的求解步骤 5,通过求解步骤 5 发现,SC2与 SC4符合求解步骤 5 简化的条件,于是删去 SC2这列,得到更新矩阵 M3,如表 4所示。3)通过基于 SCHA 的求解步骤 6,进一步得到更新矩阵 M4,如表 5 所示。56郑 州 大 学 学 报(理 学 版)第 56 卷表 4经过求解步骤 5 后的更新矩阵 M3Table 4The update matrix M3 after solving step 5U1SC3SC4U1SC3SC4U1SC3SC4u111u811u1511u211u911u1601u311u1011u1701u411u1100u1811u511u1200u1911u611u1311u710u1400注:表中 u1至 u19代表的元素与表 2 相同。表 5经过求解步骤 6 后的更新矩阵 M4Table 5The update matrix M4 after solving step 6U1SC3SC4u710u1601注:表中 u7与 u16代表的元素与表 2 相同。4)最后,通过基于 SCHA 的求解步骤 7 得到RED1=C1,C3,C4。根据定义 4 可得 RED1(x1)=x1,x2,x3,x6,RED1(x2)=x2,x3,x6,RED1(x3)=x3,x6,RED1(x4)=x3,x4,x6,RED1(x5)=x3,x4,x5,x6,RED1(x6)=x6。Cov(RED1)Cov(1)成立,同时,Cov(C1,C3)Cov(1),Cov(C1,C4)Cov(1),Cov(C3,C4)Cov(1)均不成立,可得RED1=C1,C3,C4 是覆盖信息系统(U1,1)的一个属性约简。价格,颜色,环境 三个属性是对评估结果具有影响力的属性集,而结构属性对评估结果没有影响。因此,当公司在进行实际评估时可以不考虑结构属性。5结语本文研究了覆盖信息系统属性约简问题与集覆盖问题的相关性质,构造了覆盖信息系统的相关矩阵,建立了覆盖信息系统属性约简问题与集覆盖问题之间的联系,找到了将覆盖信息系统属性约简问题转化为集覆盖问题的方法,从而可以借助丰富且高效的集覆盖理论来研究覆盖信息系统的属性约简问题。此外,对于有特殊性质的覆盖信息系统属性约简问题,相应的集覆盖解决方法是值得进一步研究的课题。参考文献:1PAWLAK Z.Rough sets J.International journal of computer&information sciences,1982,11(5):341-356.2张文修,吴 伟 志,梁吉 业,等.粗 糙 集 理 论 与 方 法M.北京:科学出版社,2001.ZHANG W X,WU W Z,LIANG J Y,et al.Rough set theory and methodM.Beijing:Science Press,2001.3胡谦,秦克云.多粒度近似空间的模糊粗糙集模型J.郑州大学学报(理学版),2020,52(4):60-66.HU Q,QIN K Y.A fuzzy rough set model in multi-granulation spaces J.Journal of Zhengzhou university(natural science edition),2020,52(4):60-66.4钱进.多粒度决策粗糙集模型研究J.郑州大学学报(理学版),2018,50(1):33-38.QIAN J.Research on multigranulation decision-theoretic rough set models J.Journal of Zhengzhou university(natural science edition),2018,50(1):33-38.5ZAKOWSKI W.Approximations in the space(U,)J.Demonstratio mathematica,1983,16(3):761-769.6ZHU W.Topological approaches to covering rough setsJ.Information sciences,2007,177(6):1499-1508.7林艺东,张燕兰,林梦雷.覆盖信息系统一种新的约简方法J.模糊系统与数学,2017,31(4):175-181.LIN Y D,ZHANG Y L,LIN M L.A new method of re-duction in covering information systems J.Fuzzy sys-tems and mathematics,2017,31(4):175-181.8黄兵,何新,周献中.基于广义粗集覆盖约简的粗糙熵J.软件学报,2004,15(2):215-220.HUANG B,HE X,ZHOU X Z.Rough entropy based on generalized rough sets covering reductionJ.Journal of software,2004,15(2):215-220.9张燕兰,李进金.广义覆盖粗集的约简J.模糊系统与数学,2010,24(3):138-143.ZHANG Y L,LI J J.The reduction of covering general-ized rough sets J.Fuzzy systems and mathematics,2010,24(3):138-143.10 张亚军,王艳平,付上金.基于覆盖粗糙集理论中的约简与 求核 J.模 糊 系 统 与 数 学,2007,21(6):152-156.ZHANG Y J,WANG Y P,FU S J.On finding core and reduction in covering rough set theoryJ.Fuzzy systems and mathematics,2007,21(6):152-156.11 SUNDAR S,SINGH A.A hybrid heuristic for the set covering problem J.Operational research,2012,12(3):345-365.12 臧文科,刘希玉,刘文菊.基于面上 DNA 计算求解最小集 合 覆 盖 问 题 J.计 算 机 应 用 研 究,2012,29(4):1220-1222.ZANG W K,LIU X Y,LIU W J.DNA computing ap-66第 1 期徐晔,等:基于集覆盖理论的覆盖信息系统属性约简方法proach on surface to solve minimal set covering problemJ.Application research of computers,2012,29(4):1220-1222.13 CHVATAL V.A greedy heuristic for the set-covering problemJ.Mathematics of operations research,1979,4(3):233-235.14 NEMHAUSER G L,WOLSEY L A.Integer and combi-natorial optimizationM.New York:Wiley Press,1988.15 陆鹏.便民警务站选址算法以及改进研究D.长沙:国防科技大学,2019.LU P.Improved algorithms of the people-serving police station location problemD.Changsha:National Univer-sity of Defense Technology,2019.16 WANG Y Y,PAN S W,AL-SHIHABI S,et al.An im-proved configuration checking-based algorithm for the uni-cost set covering problemJ.European journal of opera-tional research,2021,294(2):476-491.17 徐