1、第 59 卷 第 1 期2023 年 1 月南京大学学报(自然科学)(NATURAL SCIENCE)Vol.59,No.1Jan.,2023JOURNAL OF NANJING UNIVERSITY形式背景上基于矩阵信息熵的矩阵熵约简贺青青,马建敏*,丁娜(长安大学理学院,西安,710064)摘要:概念格的属性约简是知识表示和数据处理的一种有力工具,已被成功应用到多个领域,寻求高效快速的属性约简算法仍然是概念格理论的主要研究热点.从信息熵和布尔矩阵的角度研究形式背景的属性约简,提出属性约简的新方法.首先,在形式背景上定义矩阵信息熵、矩阵条件熵、矩阵联合熵和矩阵互信息熵,研究它们的性质和相互之
2、间的关系.接着,在形式背景上提出基于矩阵信息熵的矩阵熵协调集和矩阵熵约简的定义,给出了属性的重要性度量,利用矩阵信息熵刻画核心属性、相对必要属性和不必要属性的属性特征,再给出获取矩阵熵约简的方法和算法.最后,利用 UCI数据集进行测试,验证了基于矩阵信息熵的矩阵熵约简算法的有效性.通过对比实验,证明该算法具有更加高效的约简性能且适用于大数据样本.关键词:形式背景,信息熵,矩阵,矩阵条件熵,属性约简中图分类号:TP18 文献标志码:AMatrix information entropy based matrix entropy reduction in formal contextsHe Qin
3、gqing,Ma Jianmin*,Ding Na(School of Science,Changan University,Xian,710064,China)Abstract:The attribute reduction of concept lattices is a powerful tool for knowledge representation and data processing,and has been successfully applied in many fields.Seeking efficient and fast attribute reduction al
4、gorithms is still a major research hotspot in concept lattice theory.This paper studies attribute reduction of a formal context in the view of information entropy and Boolean matrix,and proposes a new method for attribute reduction.Firstly,the matrix information entropy,matrix conditional entropy,ma
5、trix joint entropy and matrix mutual information entropy are defined in a formal context.The properties and relationship among them are studied.Then,the definitions of matrix entropy consistent set and matrix entropy reduction are proposed by using the matrix information entropy in a formal context.
6、The importance measures of attributes are given.The attribute characteristics of core attributes,relatively necessary attributes and unnecessary attributes are described by matrix information entropy.The methods and algorithms for obtaining matrix entropy reduction are then depicted.Finally,by testi
7、ng on datasets of UCI,the effectiveness for the matrix entropy reduction algorithm based on matrix information entropy is verified.Through comparative experiments,the proposed algorithm is more efficient for reduction and suitable for large data samples.Key words:formal context,information entropy,m
8、atrix,matrix conditional entropy,attribute reductionDOI:10.13232/ki.jnju.2023.01.010基金项目:国家自然科学基金(61772019,61603278)收稿日期:2022-09-29*通讯联系人,Email:第 1期贺青青等:形式背景上基于矩阵信息熵的矩阵熵约简近年来,随着计算机网络、存储和通信技术的飞速发展,数据库的数量和规模得到了快速的积累与扩张.大数据背景下从海量数据中挖掘有价值的信息并加以利用非常必要,也是当前亟待解决的任务,对于知识发现有重要的意义.1982 年Wille1基于哲学中概念的表示方法,在数据
9、分析与知识处理中提出一种概念数学化的表示形式形式概念分析.形式概念分析,又称概念格1-2,通过对象和属性特征之间的 Galois 连接形成概念,进而由全体概念生成概念格.形式概念分析的核心是形式背景和概念格,形式背景是由对象集、属性集以及对象和属性之间的二元关系构成的三元组,是形式概念分析的基础.基于信息熵的属性约简3根据属性重要度或属性关联度来依次剔除无关属性,直到所得属性集与原信息系统的分类能力相同为止.苗夺谦和王珏4提出了粗糙集中更加直观的概念与运算的信息表示.Wang et al5提出以条件信息熵为启发条件的约简算法,利用条件信息熵度量属性集之间的依赖程度.陈媛和杨栋6将信息熵、条件信
10、息熵和属性重要度相结合,在决策表中逐步添加引起互信息量变化大的属性,优化了算法结构.当条件属性较多时,时间复杂度会相应增加7.张清华和肖雨8在此基础上提出新的信息熵属性约简算法.马斌斌9提出基于奇异值分解熵的属性约简算法,有效提高了约简精确度.滕书华等10应用主观偏好和先验信息,利用精度构造了一种新的信息熵属性约简算法,提高了属性约简结果的分类能力.Huang et al11提出一种新的多源数据的条件熵,给出了条件熵的矩阵刻画,开发了相应的增量特征选择算法.Gao et al12提出粒度最大决策熵的单调不确定性度量,并开发了基于提出的不确定性度量的前向启发式属性约简算法.陶玉枝等13构造了基于
11、条件熵的集覆盖问题的近似算法.将信息熵应用到形式背景上的属性约简也取得了一些进展.胡峰等14利用置信度的概念以及决策熵能客观反映决策规则变化情况的优势,提出基于决策熵的值约简算法.马丽等15引入两种新的 Galois联络并推广了概念格的已有结果.Jia and He16从多源地理本体中提取基本属性,使用FCA(Formal Concept Analysis)构建合并的形式背景,从粗糙集理论和信息熵中引入包含度的重要性,计算形式背景中每个单一属性的组合重要性权重,进而构建加权形式背景.Chen et al17基于图论的新框架提出两种新的基于启发式图算法,给出了形式背景和决策形式背景上的粒度约简.
12、陈东晓等18从信息粒角度提出形式背景上基于信息熵的属性约简方法.张晓鹤等19通过形式背景中属性的信息熵获取单属性权重,采用均值方法计算对象权重,构造了对象加权概念格,有效简化了概念格的构造过程.李同军等20给出了多种形式的属性约简判定定理,通过引入模糊概念间的辨识属性集的概念,得到了基于辨识属性矩阵的属性约简方法.大数据环境下的海量数据对属性约简效率的要求更高.矩阵作为一种高效的数据处理工具,由于其在计算方面的可扩展性,已被广泛应用于各类数据的属性约简中.基于矩阵方法进行属性约简,不仅可以获得更简洁的知识,也有较高的时间效率.将布尔矩阵与对象粒建立联系,借助矩阵、信息熵探讨形式背景的属性约简是
13、一种值得探讨的有效方法.本文在陈东晓等18的基础上,借助布尔矩阵和信息熵刻画形式背景的属性重要度,给出属性约简方法.首先在形式背景下定义矩阵信息熵、矩阵条件熵、矩阵联合熵和矩阵互信息熵,利用矩阵条件熵和属性重要度给出核心属性等的特征刻画,进而讨论基于矩阵信息熵的属性约简方法.最后,讨论了熵约简与本文提出的基于矩阵信息熵的属性约简之间的关系.1 预备知识 三元组()U,A,I称为形式背景2,其中U=x1,x2,xn为 非 空 有 限 对 象 集,A=a1,a2,am为非空有限属性集,I U A为U与A之 间 的 二 元 关 系,对 任 意x U,a A,()x,a I表示对象x具有属性a.对任意
14、X U,B A,Ganter and Wille2定义了形式背景上的一对算子:X=a A|x X,()x,a IB=x U|a B,()x,a I 99南京大学学报(自然科学)第 59 卷特 别 地,对 任 意x U,a A,记x=x,a=a.易知X=x Xx,B=a Ba.()X,B是形式背景()U,A,I上的形式概念2(简称概念).若X=B,B=X,则X为概念的外延,B为概念的内涵.所有概念构成的集合称概念 格,记 为L()U,A,I.记LU()U,A,I=|X()X,B L()U,A,I为外延全体,LA()U,A,I=B|()X,B L()U,A,I为内涵全体.特别地,对任 意x U,a
15、 A,称()x,x为 对 象 粒 概 念,()a,a为属性粒概念,称x为对象粒,a为属性粒.显 然,对 象 粒 全 体x,x U构 成U的覆盖.对任意B A,()U,B,IB为()U,A,I的子形式 背 景2,其 中IB=I()U B.子 背 景()U,B,IB上的算子“,”分别记为“B,B”,则对任意X U,C B,有:XB=a B|x X,()x,a ICB=x U|a C,()x,a I显然有XB=X B,XA=X,CB=C.性质 121 设()U,A,I为形式背景.对任意C B A,X U,x U,有如下结论:(1)XC XB,xC xB;(2)XBB XCC,xBB xCC.对任意X
16、U,用()X=()X()x1,X()xn表 示 集 合X的 特 征 向 量,其 中X()xi=1 xi X.类 似 地,对 任 意B A,用()B=()B()a1,B()am表示集合B的特征向量.性 质 222 设N=()nijn m,P=()pijn m,Q=()qijm p是布尔矩阵,则以下性质成立:(1)N P nij pij,i=1,2,n,j=1,2,m;(2)N P=()nij pijn m,N P=()nij pijn m;(3)N Q=()dijn p,其中dij=1 k m()nik qkj;(4)N-P=()nij()1-pijn m,?N=()1-nijn m.张清新22
17、利用矩阵给出了形式背景上二元关系和对象粒的矩阵描述.定义 122 设()U,A,I为形式背景.记rij=1()xi,aj I,称MI=()rijn m是I的关系矩阵.令M=?()MI()?MTI,MTI为MI的转置,则矩阵M的第i行M()i,:为xi的对象粒的特征向量,即M()i,:=()xi()xi U,称M为 对 象 粒 矩 阵.对任意BA,MB=?()()MIRB()?()MIRBT为子形式背景()U,B,IB下的对象粒矩阵,其中RB=()B()Bn m为每行均为()B的n m阶矩阵,即MB()i,:=()xBBi()xi U.对任意B,C A,xi U,由性质 1、性质 2 及定义 1
18、可得:C=A-B MA=MB MC(1)C B xBBi xCCi()xBBi()xCCiMB()i,:MC()i,:MB MC(2)2 形式背景上的矩阵信息熵 应用对象粒矩阵引入形式背景上的矩阵信息熵、矩阵条件熵、矩阵联合熵和矩阵互信息熵.定 义 2 设()U,A,I为 形 式 背 景.对 任 意B A,B的矩阵信息熵(简称矩阵熵)定义为:ME()B=-1|()Uxi Ulg|MB()i,:|()U其中|MB()i,:|表示行向量MB()i,:中非 0 元的个数.对任意B,C A,B相对于C的矩阵条件熵定义为:ME()|B C=-1|()Uxi Ulg|MB()i,:MC()i,:|MC()
19、i,:B与C的矩阵联合熵定义为:ME()B:C=-1|()Uxi Ulg|MB()i,:MC()i,:|()UB与C的矩阵互信息熵定义为:ME()B;C=-1|()Uxi Ulg|MB()i,:|Mc()i,:|()U|MB()i,:MC()i,:由定义 2可得:ME(B:C)=ME(C:B)ME(B;C)=ME(C;B)100第 1期贺青青等:形式背景上基于矩阵信息熵的矩阵熵约简定 理 1 设()U,A,I为 形 式 背 景.对 任 意B,C A,有:ME()B:C=ME()C+ME()|B C=ME()B+ME()|C B证明 仅证第一个等式,第二个同理可证.由定义 2可知,对任意B,C
20、A,ME()B:C=-1|()Uxi Ulg|MB()i,:MC()i,:|()U=-1|()Uxi Ulg|MB()i,:MC()i,:|MC()i,:+1|()Uxi Ulg|MC()i,:|()U=ME()|B C+ME(C)定理 1 表明矩阵联合熵可由矩阵信息熵、矩阵条件熵表示.定 理 2 设()U,A,I为 形 式 背 景.对 任 意C B A,有:(1)ME()C ME()B ME()A;(2)ME()|C B=0;(3)ME()B:C=ME()B.证明(1)(3)易证.下证(2).由C B及式(2)知:MB()i,:MC()i,:MB()i,:MC()i,:=MB()i,:故而有
21、:ME()|C B=-1|()Uxi Ulg|MC()i,:MB()i,:|MB(i,:)=-1|()Uxi Ulg|MB()i,:|MB()i,:=-1|()Uxi Ulg 1=0.定理 2表明矩阵熵是单调的,且当C B时,矩阵条件熵ME()|C B的不确定性是 0.定 理 3 设()U,A,I为 形 式 背 景.对 任 意B,C A,下列结论成立:(1)ME()B;C=ME()B+ME()C-ME()B:C;(2)ME()B;C=ME()B-ME()|B C=ME()C-ME()|C B.证明 仅证结论(1).结论(2)由(1)及定理 1可知结论成立.由定义 2可知,对任意B,C A,ME
22、()B+ME()C-ME()B:C=-1|()Uxi Ulg|MB()i,:|()U-1|()Uxi Ulg|MC()i,:|()U+1|()Uxi Ulg|MB()i,:MC()i,:|()U=-1|()Uxi Ulg|MB()i,:|MC()i,:|()U|MB()i,:MC()i,:=ME()B;C定理 3说明矩阵互信息熵可由矩阵熵和矩阵联合熵表示,也可由矩阵熵与矩阵条件熵表示.定理 4 设()U,A,I为形式背景,且C B A,ME()B=ME()C xBBi=xCCi()xi U.证明 由C B及式(2)知:xi U,xBBi=xCCi MB()i,:=MC()i,:由定义 2得:x
23、i U,ME(B)=ME(C)MB()i,:=MC()i,:xBBi=xCCi定理4给出了矩阵信息熵和对象粒间的关系.3 形式背景上基于矩阵信息熵的矩阵熵约简 利用矩阵信息熵和矩阵条件熵引入属性的重要程度,并在此基础上讨论矩阵熵约简的方法.定 义 3 设()U,A,I为 形 式 背 景.对 任 意a A,若ME()A-a=ME()A,称a在A中是不必要的;否则,称a在A中是必要的.对任意B A,若ME()B=ME()A,称B为()U,A,I的矩阵熵协调集.进一步,若对任意a B,B-a不是矩阵熵协调集,则称B是()U,A,I的矩阵熵约简集.记Re()A=|B A B是()U,A,I 的矩阵熵约
24、简,A 中所有必要属性构成的集合为()U,A,I的核,记为Core()A.Re()A-Re()A中属性称为相对必要属性.易证:Core()A=Re()A=a A|ME()A-a ME()A(3)定理 5 设()U,A,I为形式背景.对任意a 101南京大学学报(自然科学)第 59 卷A,aCore()A当且仅当ME(|aA-a)0.证 明 设a Core()A.若ME(|aA-)a=0,由 定 义 2 知,M a()i,:MA-a()i,:=MA-a()i,:,i.即M a MA-a=MA-a.由 式(1)得MA=M a MA-a,所 以MA=MA-a.由定义 2知ME()A=ME()A-a,
25、这与a为核心属性矛盾.故ME()|aA-a 0.设a A且ME()|aA-a 0.若a不是核心属性,则ME()A-a=ME()A,对任意i,MA()i,:=MA-a()i,:.由式(1)得MA=MA-a,即ME()|aA-a=0.与已知矛盾,故a为核心属性.定理 5给出了利用矩阵条件熵判断核心属性的方法.由此易得推论 1.推 论 1 设()U,A,I为 形 式 背 景.对 任 意a A,a为 不 必 要 属 性 当 且 仅 当ME(|aA-a)=0.定 义 4 设()U,A,I为 形 式 背 景.对 任 意a A,a关于A的内重要度定义为:Siginner()A|a=ME()|aA-a-ME(
26、)|aA对任意B A,a A-B,a关于B的外重要度定义为:Sigouter()B|a=ME()|aB-ME()|aB a由定义 4 知,内重要度是从属性集A中删除属性a时的一致性损失,外重要度是将属性a添加到属性集B时一致性提高的程度,利用内、外重要度可给出核心属性、不必要属性和相对必要属性的判定方法.定 理 6 设()U,A,I为 形 式 背 景.对 任 意a A,a是核心属性当且仅当Siginner()A|a 0.证明 由a A及定理 2 可得ME()|aA=0,故Siginner()A|a=ME()|aA-a.由 定理 5 可知,a为核心属性 ME()|aA-a0 Siginner()
27、A|a 0.定 理 7 设()U,A,I为 形 式 背 景.对 任 意B A,a A-B,a是不必要属性 Sigouter()B|a=0.证 明 设a是 不 必 要 属 性,由 式(3)知ME()A-a=ME()A,对 任 意a A-B有ME()B=ME(A),即MB=MA.由MA M a得MB M a.则MB M a=MB,由 定 理 2 知Sigouter()B|a=ME()|aB=0.假 设Sigouter()B|a=0,由 定 理2 知ME()|aB=0,那 么MB=MB a,则 有MB=MA,且ME()B=ME()A,由定理 6 得证a是不必要属性.推 论 2 设()U,A,I为 形
28、 式 背 景.对 任 意B A,a A-B,a是 相 对 必 要 属 性Sigouter()B|a 0.推 论 3 设()U,A,I为 形 式 背 景.则Core()A=a A:Siginner()A|a 0.定 理 8 设()U,A,I为 形 式 背 景.对 任 意B A,B为 矩 阵 熵 约 简 当 且 仅 当ME()B=ME()A且a B,ME(|aB-a)0.证 明 设B为 矩 阵 熵 约 简.由 定 义 3 知ME()B=ME()A,且a B,ME()B-aME()A.若b B,使ME()|bB-b=0.由b B及 式(1)和 式(2)知MB MB-b且MB=MB-b M b.故 由
29、ME()|bB-b=0可 知MB-b=MB,于 是ME()B-b=ME()B=ME()A.所以B-b为矩阵熵协调集,这与B是矩 阵 熵 约 简 集 矛 盾.故 对 任 意a B,ME(|a)B-a 0.反 之,若ME()B=ME()A且a B,ME()|aB-a 0,则B为矩阵熵协调集.若存 在b B,使ME()B-b=ME()A,则ME()B-b=ME()B.由 定 理 4 及 式(1)得MB=MB-b M b,于 是ME()|bB-b=0,与已知矛盾.故aB,ME(B-a)ME(A).即B为矩阵熵约简.102第 1期贺青青等:形式背景上基于矩阵信息熵的矩阵熵约简推 论 4 设()U,A,I
30、为 形 式 背 景.对 任 意B A,B为 矩 阵 熵 约 简 集 当 且 仅 当ME()B=ME()A且对任意b B,Siginner()B|b 0.陈东晓等18利用对象粒定义了形式背景的熵协 调 集 和 熵 约 简.对 任 意B A,称H()B=-1|Ux Ulg2()|xBB|U为()U,A,I关 于B的 信 息熵,其中|表示集合的基数.若H()B=H()A,称B为()U,A,I的熵协调集.若对任意C B,C不是熵协调集,则称B是形式背景()U,A,I的熵约简集.定 理 9 设()U,A,I为 形 式 背 景.对 任意B A,(1)B为熵协调集当且仅当B为矩阵熵协调集;(2)B为熵约简集
31、当且仅当B为矩阵熵约简集.证 明(1)对 任 意B A,由 性 质 2 得xAA xBB,于 是H()B H()A.故H()B=H()A xAA=xBB,x U.由定理 4知:H()B=H()A x U,xBB=xAAME()B=ME()A即B为熵协调集当且仅当B为矩阵熵协调集.(2)设B为 矩 阵 熵 约 简 集.则ME()B=ME()A,且 对 任 意b B,ME()B-bME()A,由(1)知H()B=H()A.若b0 B,H()B-b0=H()A,由(1)的证明得ME(B-)b0=ME()A,即B-b0为矩阵熵协调集,与已知条件B为矩阵熵约简集矛盾.故B为熵约简集.反之,若B为熵约简集
32、,由(1)知B为矩阵熵协调集.若b0 B使ME()A=ME()B-b0,由式(3),xAA=xB-b0B-b0,故H()A=H()B-b0,与已知条件B为熵约简集矛盾.故B为矩阵熵约简集.定理 9证明矩阵熵约简与熵约简等价.定理 6 说明核心属性是内重要度大于 0 的属性.定理 7 和推论 2 给出了由外重要度判断相对必要或不必要属性的方法.由定理 6、定理 7和推论 2可给出形式背景上基于矩阵信息熵的矩阵熵约简算法,如下所示.算法 基于矩阵信息熵的矩阵熵约简算法输入:形式背景()U,A,I输出:矩阵熵约简集P、核心属性集Core()AStep 1.计 算 对 象 粒 矩 阵MA,令Core(
33、)A:=,P:=;Step 2.aiA,i=1,2,m,若Siginner(A|ai)0,Core()A Core()A ai;Step 3.令P=Core()A,计算ME()P和ME()A;Step 4.若ME()P=ME()A,则进行 Step 6,否则进行 Step 5;Step 5.令Q=A-P,b Q,若Sigouter(P|b)0,P P b,返回 Step 4;Step 6.输出矩阵熵约简集P和核心属性集Core()A.算法第一步的时间复杂度为O()|U|2|A|.第二 步 找 出 所 有 核 心 属 性,时 间 复 杂 度 为O()|U|2|A|2.第三步判断P是否为矩阵熵约简
34、集,时间复杂度为O()|U|2|A|.第四步的时间复杂度为O()2|A.第五步找到相对必要属性,时间复杂度为O()|U|2|A|2.因此算法的综合时间复杂度为O()|U|2|A|2+2|A.例 设()U,A,I为 形 式 背 景,其 中U=x1,x2,x3,x4,x5,属 性 集A=a1,a2,a3,a4,a5,如表 1所示.由表 1 知,关系矩阵MI=1010101010100011100101110,对表 1形式背景()U,A,ITable 1A formal context()U,A,IUx1x2x3x4x5a110110a201011a310001a401001a510110 103南
35、京大学学报(自然科学)第 59 卷象 粒 矩 阵MA=1000001001101100001000001,由MA-a1=1000001001101100001000001,Ma1=1011011111101101011011111计算得:Siginner()A|a1=ME()|a1A-a1-ME()|a1A=0同理得:Siginner()A|a2=-15lg13Siginner()A|a3=-15lg16Siginner()A|a4=-15lg23Siginner()A|a5=0由定理 6 知,a2,a3,a4为核心属性,a1,a5为非核心属性.令B=a2,a3,a4,求得:Sigouter(
36、)B|a1=-15lg110Sigouter()B|a5=-15lg110由 推 论 2 知,a1,a5为 相 对 必 要 属 性.由()B=(0,1,1,1,0)知RB=0111001110011100111001110,所 以MB=1000101001111110101100001.显然,MA MB且ME()B=-15lg12625 ME()A.取C=a1,a2,a3,a4,则()C=(1,1,1,1,0),所以RC=1111011110111101111011110,MC=1000001001101100001000001.于 是MA=MC且ME()A=ME()C=-15lg63125,
37、故C为矩阵熵约简集.类似可求得,a2,a3,a4,a5也是矩阵熵约简集.4 实验 为了验证形式背景上基于矩阵信息熵的矩阵熵约简算法的有效性,选取四组属性个数不同的UCI数据集构造形式背景,如表 2所示,分别针对算法 1进行约简实验.UCI 的原始数据为信息系统,将原始数据转化为形式背景:设()U,A,F为信息系统,F=f:U A V为信息函数集合.对任意a A,属性a的均值和标准差记为mean()a和std()a.对任意x U,定义二元关系:I U A:()x,a I|f()x,a-mean()a|std()a则()U,A,I为由信息系统诱导的形式背景.将表 2 中的每个 UCI数据集转化为形
38、式背景后应用算法进行约简实验.吕林霞等23在信息系统上提出了基于信息熵的属性约简.设()U,A,I为信息系统,对任意P A,P在U上 的 等 价 划 分U/IND()P=X1,X2,Xn,称H()P=-i=1np()Xilg p()Xi为P的信息熵,其中p()Xi=|Xi|U,i=1,2,n表示等价类Xi在U中的概率.张清新22从知识信息熵角度定义属性的重要性,以核为起点,对核以外的属性,以属性添加后对原有属性集所引起的信息熵变化的大小为启发式信息,选择属性,从而得到最小约简.本文通过对象粒和矩阵来定义的矩阵信息熵,定义了内属性重要度和外属性重要度,通过内属性重要度计算核心属性集,通过外属表
39、2实验数据集Table 2Experimental datasets名称AdultstretchBalancescaleCarkrvskp实例数2062517283196属性数5576 104第 1期贺青青等:形式背景上基于矩阵信息熵的矩阵熵约简性重要度计算相对必要属性集,最后输出核心属性集和约简集.分别用 Matlab 计算四个数据集的约简时间,比较两种约简方法所用的时间(如表 3 所示),可见用矩阵和信息熵对形式背景进行矩阵熵约简更方便简洁.通过上述实验可以看出,当数据集较大 时,算 法 也 具 有 较 高 的 可 用 性 和 时 间 运 行效率.5 结论 本文主要研究了形式背景上基于矩阵
40、信息熵的矩阵熵约简方法.首先通过对象粒矩阵定义了形式背景上的矩阵信息熵、矩阵条件熵、矩阵联合熵和矩阵互信息熵,讨论了它们的性质和关系.进而提出形式背景上基于矩阵信息熵的矩阵熵协调集和矩阵熵约简的定义.利用矩阵信息熵提出了属性的重要性度量,进而刻画了核心属性、相对或不必要属性的属性特征,最后给出了获取矩阵熵约简的方法.信息熵是研究信息粒不确定性度量的一种重要方法,下一步将应用矩阵信息熵研究三支概念格的属性粒约简及其应用.参考文献1Wille R.Restructuring lattice theory:An approach based on hierarchies of conceptsFer
41、r S,Rudolph S.Formal concept analysis.Springer Berlin Heidelberg,2009:314-339.2Ganter B,Wille R.Formal concept analysis:Mathematical foundations.Berlin:Springer Verlag,1999,157-192.3马捷,葛岩,蒲泓宇.属性约简方法研究综述.数据分析与知识发现,2020,4(1):40-50.(Ma J,Ge Y,Pu H Y.Survey of attribute reduction methods.Data Analysis a
42、nd Knowledge Discovery,2020,4(1):40-50.)4苗夺谦,王珏.粗糙集理论中概念与运算的信息表示.软件学报,1999,10(2):113-116.(Miao D Q,Wang J.An Information representation of the concepts and operations in rough set theory.Journal of Software,1999,10(2):113-116.)5Wang G Y,Zhao J,An J J,et al.Theoretical study on attribute reduction of
43、 rough set theory:Comparison of algebra and information viewsProceedings of the 3rd IEEE International Conference on Cognitive Informatics.Victoria,Canada:IEEE,2004:148-155.6陈媛,杨栋.基于信息熵的属性约简算法及应用.重庆理工大学学报(自然科学版),2013,27(1):42-46.(Chen Y,Yang D.Attribute reduction alogrithm based on information entro
44、py and its application.Journal of Chongqing Institute of Technology(Natural Science),2013,27(1):42-46.)7吴尚智,苟平章.粗糙集和信息熵的属性约简算法及 其 应 用.计 算 机 工 程,2011,37(7):56-58,61.(Wu S Z,Gou P Z.Attribute reduction algorithm on rough set and information entropy and its application.Computer Engineering,2011,37(7):5
45、6-58,61.)8张清华,肖雨.新的信息熵属性约简.计算机科学与探 索,2013,7(4):359-367.(Zhang Q H,Xiao Y.New attribute reduction on information entropy.Journal of Frontiers of Computer Science and Technology,2013,7(4):359-367.)9马斌斌.基于多重奇异值分解熵的属性约简方法研究及应用.硕士学位论文.合肥:安徽大学,2017.(Ma B B.Research on attribute reduction based on multi sc
46、ales singular value decomposition entropy and its applications.Master Dissertation.Hefei:Anhui University,2017.)10 滕书华,鲁敏,杨阿锋,等.基于一般二元关系的粗糙集加权不确定性度量.计算机学报,2014,37(3):649-665.(Teng S H,Lu M,Yang A F,et al.A weighted uncertainty measure of rough sets based on general binary relation.Chinese Journal of
47、 Computers,2014,37(3):649-665.)11 Huang Y Y,Guo K J,Yi X W,et al.Matrix representation of the conditional entropy for 表 3两种方法在各数据集上的约简时间(单位:s)Table 3Reduction time(unit:s)of the two methods on each dataset数据集AdultstretchBalancescaleCarkrvskp基于矩阵熵的约简算法0.0446030.0470020.0646030.079258吕林霞等23的属性约简算法0.27
48、305624.362580179.484235887.541358 105南京大学学报(自然科学)第 59 卷incremental feature selection on multi source data.Information Sciences,2022(591):263-286.12 Gao C,Lai Z H,Zhou J,et al.Granular maximum decision entropy based monotonic uncertainty measure for attribute reduction.International Journal of Approx
49、imate Reasoning,2019(104):9-24.13 陶玉枝,赵仕梅,谭安辉.一种基于决策表约简的集覆盖问题的近似解法.南京大学学报(自然科学),2018,54(4):821-828.(Tao Y Z,Zhao S M,Tan A H.A decision table reduction based approximate method for set covering problem.Journal of Nanjing University(Natural Science),2018,54(4):821-828.)14 胡峰,张杰,吉朝明,等.基于决策熵的值约简算法.南 京
50、大 学 学 报(自 然 科 学),2010,46(5):477-486.(Hu F,Zhang J,Ji C M,et al.Value reduction algorithm based on decision information entropy.Journal of Nanjing University(Natural Science),2010,46(5):477-486.)15 马丽,李仲玲,米据生.基于相似度的 Galois 格.南京 大 学 学 报(自 然 科 学),2012,48(4):445-451.(Ma L,Li Z L,Mi J S.Galois lattice de