形式背景上基于矩阵信息熵的矩阵熵约简_贺青青.pdf

第 59 卷 第 1 期2023 年 1 月南京大学学报（自然科学）（NATURAL SCIENCE）Vol.59,No.1Jan.,2023JOURNAL OF NANJING UNIVERSITY形式背景上基于矩阵信息熵的矩阵熵约简贺青青,马建敏*,丁娜（长安大学理学院，西安，710064）摘要：概念格的属性约简是知识表示和数据处理的一种有力工具，已被成功应用到多个领域，寻求高效快速的属性约简算法仍然是概念格理论的主要研究热点.从信息熵和布尔矩阵的角度研究形式背景的属性约简，提出属性约简的新方法.首先，在形式背景上定义矩阵信息熵、矩阵条件熵、矩阵联合熵和矩阵互信息熵，研究它们的性质和相互之间的关系.接着，在形式背景上提出基于矩阵信息熵的矩阵熵协调集和矩阵熵约简的定义，给出了属性的重要性度量，利用矩阵信息熵刻画核心属性、相对必要属性和不必要属性的属性特征，再给出获取矩阵熵约简的方法和算法.最后，利用 UCI数据集进行测试，验证了基于矩阵信息熵的矩阵熵约简算法的有效性.通过对比实验，证明该算法具有更加高效的约简性能且适用于大数据样本.关键词：形式背景，信息熵，矩阵，矩阵条件熵，属性约简中图分类号：TP18 文献标志码：AMatrix information entropy based matrix entropy reduction in formal contextsHe Qingqing,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 algorithms 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，matrix 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.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 testing 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,matrix,matrix conditional entropy,attribute reductionDOI：10.13232/ki.jnju.2023.01.010基金项目：国家自然科学基金（61772019，61603278）收稿日期：2022-09-29*通讯联系人，Email：第 1期贺青青等：形式背景上基于矩阵信息熵的矩阵熵约简近年来，随着计算机网络、存储和通信技术的飞速发展，数据库的数量和规模得到了快速的积累与扩张.大数据背景下从海量数据中挖掘有价值的信息并加以利用非常必要，也是当前亟待解决的任务，对于知识发现有重要的意义.1982 年Wille1基于哲学中概念的表示方法，在数据分析与知识处理中提出一种概念数学化的表示形式形式概念分析.形式概念分析，又称概念格1-2，通过对象和属性特征之间的 Galois 连接形成概念，进而由全体概念生成概念格.形式概念分析的核心是形式背景和概念格，形式背景是由对象集、属性集以及对象和属性之间的二元关系构成的三元组，是形式概念分析的基础.基于信息熵的属性约简3根据属性重要度或属性关联度来依次剔除无关属性，直到所得属性集与原信息系统的分类能力相同为止.苗夺谦和王珏4提出了粗糙集中更加直观的概念与运算的信息表示.Wang et al5提出以条件信息熵为启发条件的约简算法，利用条件信息熵度量属性集之间的依赖程度.陈媛和杨栋6将信息熵、条件信息熵和属性重要度相结合，在决策表中逐步添加引起互信息量变化大的属性，优化了算法结构.当条件属性较多时，时间复杂度会相应增加7.张清华和肖雨8在此基础上提出新的信息熵属性约简算法.马斌斌9提出基于奇异值分解熵的属性约简算法，有效提高了约简精确度.滕书华等10应用主观偏好和先验信息，利用精度构造了一种新的信息熵属性约简算法，提高了属性约简结果的分类能力.Huang et al11提出一种新的多源数据的条件熵，给出了条件熵的矩阵刻画，开发了相应的增量特征选择算法.Gao et al12提出粒度最大决策熵的单调不确定性度量，并开发了基于提出的不确定性度量的前向启发式属性约简算法.陶玉枝等13构造了基于条件熵的集覆盖问题的近似算法.将信息熵应用到形式背景上的属性约简也取得了一些进展.胡峰等14利用置信度的概念以及决策熵能客观反映决策规则变化情况的优势，提出基于决策熵的值约简算法.马丽等15引入两种新的 Galois联络并推广了概念格的已有结果.Jia and He16从多源地理本体中提取基本属性，使用FCA（Formal Concept Analysis）构建合并的形式背景，从粗糙集理论和信息熵中引入包含度的重要性，计算形式背景中每个单一属性的组合重要性权重，进而构建加权形式背景.Chen et al17基于图论的新框架提出两种新的基于启发式图算法，给出了形式背景和决策形式背景上的粒度约简.陈东晓等18从信息粒角度提出形式背景上基于信息熵的属性约简方法.张晓鹤等19通过形式背景中属性的信息熵获取单属性权重，采用均值方法计算对象权重，构造了对象加权概念格，有效简化了概念格的构造过程.李同军等20给出了多种形式的属性约简判定定理，通过引入模糊概念间的辨识属性集的概念，得到了基于辨识属性矩阵的属性约简方法.大数据环境下的海量数据对属性约简效率的要求更高.矩阵作为一种高效的数据处理工具，由于其在计算方面的可扩展性，已被广泛应用于各类数据的属性约简中.基于矩阵方法进行属性约简，不仅可以获得更简洁的知识，也有较高的时间效率.将布尔矩阵与对象粒建立联系，借助矩阵、信息熵探讨形式背景的属性约简是一种值得探讨的有效方法.本文在陈东晓等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.对任意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 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.对任意XU，用()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利用矩阵给出了形式背景上二元关系和对象粒的矩阵描述.定义 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为子形式