基于矩阵信息熵的形式背景动态属性约简方法

关键词：形式概念分析，粒约简，动态属性约简，信息熵，对角矩阵条件熵，对象粒对角矩阵

中图分类号：TP391 文献标志码：A

在大数据时代，数据集规模快速扩张，从海量数据中挖掘有价值的信息并转化为知识显得非常必要. 1982 年，数学家Wille［1］对哲学中的“概念”一词给出数学化表达，提出形式概念分析理论（Formal Concept Analysis，FCA）. FCA通过挖掘概念和构建格结构为知识发现提供了强有力的理论依据，其中属性约简通过去除不重要的属性，不仅提高了数据分析结果的质量，还减少了计算过程中的资源需求和时间消耗. 但在真实应用场景下数据集往往会发生变化，如数据集的属性随时间的推移增加或减少，亟待一种属性约简算法来处理数据呈现的动态特征，因此基于较大规模数据集研究快速高效的属性约简算法具有重要的意义.

在现有的FCA 理论中，属性约简可以在静态和动态两种环境下进行. 静态属性约简算法最早由Ganter and Wille［2］建立基于对象集或属性集的约简框架. Zhang et al［3］保持概念格的结构和层次不变，提出一种基于辨识矩阵的属性约简方法.为了进一步简化Zhang et al［3］的工作，Qi et al［4］提出一种新的辨识矩阵，然而利用辨识矩阵来计算约简将导致高时间消耗，是难以直接求解的非确定性多项式难（Non⁃deterministic Polynomial⁃hard，NP⁃hard）问题. 因此，张清新［5］提出基于布尔矩阵的概念格属性约简方法. Wu et al［6］首次提出概念格的粒约简，讨论粒结构及其在知识约简中的应用，引起了研究者们的注意. Shao et al［7-8］从向量的线性相关性的角度来考虑属性约简和属性特征，针对模糊形式背景进行粒约简，给出了不需要构造格结构的基于辨识矩阵约简方法.Huang et al［9］提出信息熵和条件信息熵来衡量属性的显著性并开发了一种启发式算法. Lin et al［10］定义矩阵来表示形式概念的外延和内涵，在此基础上研究不可约元，为形式概念分析中的粒约简提供了新的框架. Zhang et al［11］进一步将基于矩阵的粒约简方法推广到协调决策形式背景. 陈东晓等［12］从信息粒角度提出形式背景上基于信息熵的属性约简方法. 贺青青等［13］在陈东晓等［12］的基础上从信息熵和布尔矩阵的角度研究了形式背景的属性约简，提出高效的属性约简的新方法.Chen et al［14-15］基于图论框架提出FCA 的启发式粒约简算法.

在真实的应用场景下，数据集往往不断地变化更新，势必对原形式背景的粒约简结果产生一定的影响，因此，不少研究者探讨了动态属性约简算法，例如，黄桃林等［16］讨论了形式背景的逐个对象增加之后原粒约简的变化规律，通过构造粒辨识属性矩阵来更新相应的约简. Li et al［17］结合了认知算子，研究对象和属性同时增加时形式背景的新粒约简更新算法. Niu and Chen［18］讨论了属性集在形式背景中更新时的粒约简更新机制，并进一步开发了相应的增量算法.

形式背景静态属性约简方法往往需要从头开始计算而不能充分利用已有约简结果，缺乏适应真实应用场景的增量更新机制. 动态属性约简方法虽然利用已有的约简结果设计相应的更新机制，但缺乏快速更新的运算方法，也不适合较大规模的数据集，需进一步提高计算效率. 本文受贺青青等［13］和Xu and Yang［19］的启发，利用矩阵快速运算特性，在定义对象粒对角矩阵后，研究形式背景属性集更新时基于矩阵信息熵的粒约简更新机制，并进一步设计动态快速属性约简算法.

本文的主要贡献如下.

（1）定义对象粒对角矩阵，引入对象粒对角矩阵信息熵、对象粒对角矩阵条件熵、DMCE （Di⁃agonal Matrix Conditional Entropy）属性内外重要性度量，讨论基于矩阵信息熵的形式背景属性约简算法MEAR （Matrix Entropy Attribute Redcu⁃tion）.

（2）探讨动态形式背景下属性增加和属性删除两种情况下对象粒对角矩阵的动态更新机制，并给出对应的基于矩阵信息熵属性约简算法MEAR_add 和MEAR_del.

（3）在UCI 六个数据集上进行实验验证. 结果表明在面对较大规模数据集时，提出的属性约简算法比其他算法在运行时间上更具优势.

命题4 和命题5 主要依赖于对角矩阵条件熵分别计算DMCE 属性内重要度和DMCE 属性外重要度，与定义6 和定义7 的计算结果是一致的.

推论2 给定矩阵信息熵属性约简集的判定方法，主要依赖于对角矩阵信息熵和对角矩阵条件熵的计算，与定理3一致.

2. 2矩阵信息熵约简算法MEAR 矩阵信息熵约简算法为静态约简算法，为动态形式背景的矩阵信息熵约简算法奠定基础，步骤如算法1 所示. 步骤2计算对象粒矩阵和对象粒对角矩阵，步骤3～8获得核心属性集，步骤9～16 以核心属性集作为初始约简子集，主要是从非核心属性集中找出相对必要属性，直至确定剩下的属性都是不必要属性.

3动态形式背景上的快速属性约简方法

在形式背景中，当属性发生变化后，往往需要重新计算，不能充分利用已有的约简结果，并且需要耗费大量的时间. 数据集的属性变化分为增加属性和删除属性，因此，提出了两种动态形式背景上的快速属性约简方法，它们利用矩阵快速运算的特性，在先前获得的约简结果的基础上对属性进行更新，这将在很大程度上降低算法的时间复杂度.

3. 1动态形式背景上增加属性时的矩阵信息熵属性约简方法

3. 1. 1增加属性时的矩阵信息熵属性约简方法的动态更新机制 形式背景添加属性时矩阵条件熵的动态更新方法的更新机制的关键是添加属性后，对象粒矩阵和对象粒对角矩阵如何更新.

步骤2 使用定义5和命题9分别计算约简属性集的对象粒对角矩阵、更新后的对象粒对角矩阵.

步骤4～12，当新属性集的矩阵信息熵大于等于原约简属性集的矩阵信息熵时，在可选属性集中选出DMCE属性外重要度最大的属性加入新约简集.

步骤13～19，删除不必要属性.

4实验

4. 1实验设置 为了构建实验所需的形式背景，从UCI 机器学习库中下载六个数据集，其详细信息如表2 所示. 构建形式背景只考虑条件属性，因此首先删除标签信息，同时鉴于所选数据集的属性值不满足0 或1，需对数据集进行离散化处理来生成形式背景. 若属性值是实值或整数数据时，将该属性划分为n 个不相交的区间，如果它们属于相应的区间，就会被n 替代. 若属性值是类别数据，不做特殊处理. 然后，使用独热编码（one⁃hot encod⁃ing）方式为每个属性编码，再将所有属性的独热编码拼接得到新的形式背景.

所有算法基于Pycharm 环境由Python语言编程实现，并在Intel i7⁃10510U 1. 80 GHz CPU、16. 0 GB 内存和64 位Windows 10操作系统的计算机环境下运行.

4. 2MEAR_add算法的时间性能对比与分析

为了验证本文提出的算法的性能，从运行时间角度对提出的MEAR_add 算法与现有两种属性约简算法进行对比，包含静态属性约简算法MEAR 和动态属性约简算法FC_IGR［13］. 此外，为了更好地验证增加属性数量对算法的影响，对表2 中的每个数据集构建五个测试集，分别随机选择10%，20%，30%，40% 和50% 的属性数量作为新增属性数据集，剩余属性构成初始数据集.

图1 为三种算法在不同数据集上运行时间的结果对比，显示了不同的变化趋势. 由图1 可见，随着属性集比例的不断增加，FC_IGR 和MEAR_add算法的计算时间呈上升趋势，基于矩阵的MEAR和MEAR_add 算法的运行时间明显比FC_IGR 算法短. 从子图可以看出，MEAR_add 算法的计算时间最短. 特别地，对于小规模数据集Zoo，Car 和Wine，MEAR_add 算法的时间消耗仅是FC_IGR算法的几分之一. 对于较大规模数据集如Abalo⁃ne，Clave 和Bean，MEAR_add 算法的时间消耗仅是FC_IGR 算法的几十分之一，具有显著的优势.三种算法所取得的属性约简结果一致，因此，MEAR_add 算法的计算效率更高.

4. 3MEAR_del 算法的对比与分析 为了验证本文提出的算法的性能，从运行时间的角度对提出的MEAR_del 和MEAR 算法与FC_DGR［13］算法进行对比分析. 此外，为了更好地验证删除属性数量对算法的影响，对表2 中的每个数据集构建五个测试集，分别随机选择10%，20%，30%，40% 和50%的属性数量作为删除属性数据集，全部属性构成初始数据集.

图2显示了不同数据集属性变化时算法的变化趋势. 由图2 可见，随着删除属性集的不断增加，FC_IGR 算法的计算时间增加. 从子图可以看出，除Zoo 数据集外，其他数据集上MEAR_del 算法的计算时间明显低于其他算法. 特别是对于较大规模数据集Abalone，Clave 和Bean，MEAR_del算法的时间优势更加明显. 三种算法所取得的属性约简结果是一致的，因此，MEAR_del 算法的计算效率更高.

5结论

本文提出一种动态形式背景下基于矩阵信息熵的属性特征约简算法. 首先定义对象粒对角矩阵、对角矩阵信息熵、对角矩阵条件熵等概念，在此基础上探讨形式背景下属性增加和属性删除时对象粒对角矩阵的动态更新机制；其次，设计相应的基于矩阵信息熵的属性约简算法MEAR_add 和MEAR_del；最后通过实验验证提出的算法的高效性.

面对较大规模的动态数据环境时，本文方法还存在一定局限，例如，对象和属性同时更新时的对象粒更新机制未被建立，以及对三支概念格的属性粒约简方法未探讨. 因此，未来将对上述问题进行深入研究.

（责任编辑 高善露）