形式背景上基于矩阵信息熵的矩阵熵约简_贺青青.pdf
《形式背景上基于矩阵信息熵的矩阵熵约简_贺青青.pdf》由会员分享,可在线阅读,更多相关《形式背景上基于矩阵信息熵的矩阵熵约简_贺青青.pdf(9页珍藏版)》请在咨信网上搜索。
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(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式 背景 基于 矩阵 信息 熵约简 青青
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。