基于维度变化的矩阵增量属性约简算法

闫俊辉

摘  要： 随着计算机网络技术和人们生活节奏的加快，生活中很多数据都在随时发生着变化，那么快速及时的解决数据变化后的属性约简问题，就成了信息技术领域里研究的一个重要课题。剖析了数据更新后相对知识粒度和等价关系矩阵的增量机制，提出了对象属性值增加后的基于矩阵方法的增量属性约简算法。下载了2组UCI数据对提出的增量属性约简算法进行了测试，结果证明了增量属性约简算法能够处理属性值增加后的属性约简问题。

关键词： 属性约简; 知识粒度; 等价关系; 矩阵; 增量机制

中图分类号：TP18          文献标识码：A     文章编号：1006-8228（2022）04-47-04

Matrix incremental attribute reduction algorithm based on dimension change

Yan Junhui

（Yuncheng University， School of Mathematics and Information Technology， Yuncheng， Shanxi 044000， China）

Abstract： With the acceleration of computer network technology and people's pace of life， a lot of data in life are changing at any time. Quickly and timely solving the problem of attribute reduction after data changes has become an important topic in the field of information technology research. In this paper， the incremental mechanism of relative knowledge granularity and equivalence relation matrix after data update is analyzed. Then an incremental attribute reduction algorithm is proposed， which is after object attribute value increasing and based on matrix method. Finally， two groups of UCI data are downloaded to test the algorithm， and the results show that the incremental attribute reduction algorithm can deal with the attribute reduction problem with increased attribute values.

Key words： attribute reduction; knowledge granularity; equivalence relation; matrix; incremental mechanism

0 引言

近些年，計算机网络、通信以及存储技术的快速发展，使得各行各业信息系统都有大量的数据积累，其对象的属性值会发生动态变化。例如医院里医教科和人事科都有医生的信息，在整合医教科和人事科的医生信息时，信息系统的属性值会发生变化。此时，如何在原来的数据分析基础上，快速更新对象的属性值增加发生变化后决策信息系统的约简问题，成为信息科学研究领域普遍关注的热点。假若使用非增量属性约简算法[1-3]处理动态的数据属性约简，并不能充分利用先前计算的结果，导致运行速度减慢。

为了克服非增量属性约简算法在解决动态变化数据时属性约简的缺陷，很多学者提出了增量属性约简算法。Wang等通过分析三种信息熵在属性动态增加情况下的增量变化机制，设计了基于信息熵的一种增量属性约简算法[4];根据属性在动态增加和减少时决策信息系统中信息粒度的变化规律，Qian等提出了正向近似和逆向近似，并将其成功应用在启发式属性约简算法的加速中，为粗糙集基础上优化知识发现性能提出了新思路[5];王磊等分析了矩阵方法计算相对知识粒度在对象属性集动态变化时的增量更新原理，探讨了一种属性动态变化下增量属性约简算法[6]; Jing讨论了决策信息系统属性值细化时实现快速计算约简问题的相对知识粒度和计算等价关系矩阵的增量机制，设计了基于对象属性集增加时的动态属性约简算法[7];Shu等在不完备的系统中，讨论了对象属性集在动态增加或删除时基于正区域的决策信息系统动态属性约简算法[8]; Zeng等提出了新的混合距离的概念，并结合高斯核和混合距离，探讨了决策信息系统在属性值细化下的属性约简增量更新机制，提出了基于模糊粗糙集的混合决策信息系统动态属性的约简算法，并对该算法进行了实验验证[9]。通过以上分析，对信息熵和正区域的更新是大多数增量算法实现快速获取属性增加后决策信息系统约简的主要途径，而利用更新知识粒度的方法实现快速获取属性值细化后决策信息系统的约简算法研究很少。

利用矩阵计算处理数值是一种非常有效的方法，已被广泛应用到数值分析、知识发现和系统工程等诸多学科领域。针对决策信息系统如何快速地更新变化后的决策信息系统约简问题，首先探究了矩阵计算变化后的决策信息系统等价关系矩阵和相对知识粒度的增量机制，然后设计了增加对象及其方法，最后通过UCI数据仿真实验的结果，验证了所提出的增量属性约简算法可以有效处理对象的属性值增量后的属性约简问题。

1 基于矩阵的非增量属性约简算法

依据以上七个定义，很多研究该课题的学者就得到了基于矩阵的非增量属性约简算法[6]。

2 基于矩阵的增量属性约简算法

当决策信息系统属性发生细微变化，并且对象值增加时。仍然用上面的算法来计算数据变化后的决策信息系统，由于不能用到之前的运算结果，要重复计算等价关系矩阵（定义2）、相对知识粒度（定义4）和约简（定义7），这样就浪费了更多的时间和存储空间，使得运算速度变慢。为了解决对象值变化后决策信息系统约简速度变慢的问题，本文提出了决策信息系统属性值增加后的增量属性约简算法。

2.1 知识粒度的增量机制

2.2 属性增加时的增量属性约简算法

当决策信息系统属性发生细微变化，并且对象值增加时，参照上面运算得到的等价关系矩阵和知识粒度增量机制的定义和定理，在原有决策信息系统的知识粒度和约简基础上，提出了对象属性值增加后的增量属性约简算法，算法的具体步骤如下：

3 实验仿真测试

为了测试本文中提出的增量属性约简算法的可行性，我们下载了梁组UCI数据集作为仿真实验的数据集，数据集描述如（表1）所示，分别对这些数据集用非增量和增量属性约简算法进行计算，并对非增量属性约简算法和增量属性约简算法的运行时间进行对比分析。仿真实验的硬件环境要求，中央处理器： Pentium（R） Dual-Core E5800 3.20GHz，内存：Samsung DDR3 SDRAM 4.0GB以上配置;软件环境要求：64-bit Windows 10操作系统，64-bits（JDK 1.6.0_20）和Eclipse 3.7即可。

3.1 非增量属性约简算法与增量属性约简算法的运行时间比较

在仿真实验中，把表1中的数据集，按照属性分成两部分，其中50%的条件属性和决策属性为基本数据集，其余的50%数据，按照数学的20%、40%、60%、80%、100%作为增量属性集，非增量和增量约简算法分别运行这些数据集，仿真实验的结果（如图1）中的（a）、（b）所示，其中纵轴是约简算法的运行时间，横轴是数据集中增加属性的百分数。圆形线表示非增量约简算法的运行时间，方形线表示增量属性约简算法的运行时间。

从图1可以看出，当决策信息系统属性对象值增加时，增量属性约简算法的运行时间远远小于非增量属性约简算法的运行时间，结果证明了增量属性约简算法能够处理属性值增加后的属性约简问题，并大大提高了效率。

3.2 非增量约简算法所得约简与增量约简算法分类精确度比较

在运行分类精度实验中，把表1中的数据按照属性分成基本数据集和增量数据集，其中条件属性和决策属性由基本数据集的50%组成，增量数据集由剩余的50%组成，当增量数据集被增加到基本数据集时，用非增量和增量属性约简算法分别计算数据集的约简。然后，运用贝叶斯分类方法和十字交叉方法计算非增量与增量约简算法可以得到约简的分类精确度，再对分类精确度进行对比，实验结果如表2。

从表2可以看出非，增量约简算法和增量约简算法获得约简的分类精确度的值是相近的。实验结果证明，当决策信息系统条件属性对象值增加时，增量属性约简算法所得到的约简是有效地。

4 结束语

本文阐述了决策信息系统对象的属性值增加后快速解决约简更新的问题，首先分析了对象的属性值增加后基于矩阵的等价关系的增量机制，然后提出了对象属性值增加后的基于矩阵的增量属性约简算法。最后下载了UCI数据集并对提出的增量属性约简算法进行了仿真测试，结果证明了增量属性约简算法能够处理属性值增加后的属性约简问题。下一步将考虑属性值和属性同时变化时的增量属性约简算法，并把所提出的增量属性约简算法推广到多粒度粗糙集模型中。

参考文献（References）：

[1] 苖夺谦，范世栋.知识粒度的计算及其应用[J].系统工程理论与实践，2002，22（1）：48-5

[2] 王国胤，于洪，杨大春.基于条件信息系统的决策表约简[J].计算机学报，2002，25（7）：760-765

[3] 梁吉业，曲开社，徐宗本.信息系统的属性约简[J]. 系统工程理论与实践，2001，12（12）：76-80

[4] Feng Wang， Jiye Liang， Chuangyin Deng. Attributereduction：A dimension incremental strategy.Knowledge-Based Systems，2013，39：95-108

[5] Yuhua Qian， Jiye Liang， Witold Pedrycz， Chuangyin Deng. Positive approximation： An accelerator for attribute reduction in rough set theory. Artificial Intelligence，2010，174（9-10）：597-618

[6] 王磊，叶军.知识粒度计算的矩阵方法及其在属性约简中的应用[J].计算机工程与科学，2013，35（3）：98-102

[7] Yunge Jing， Tianrui Li， Chuan Luo， Shi-Jinn Horng，Guoyin Wang， Zeng Yu. An incremental approach for attribute reduction based on knowledge granularity[J]. Knowledge-Based Systems，2016，104（C）：24-38

[8] Wenhao Shu， Hong Shen. Updating attribute reduct inincomplete decision systems with the variation of attribute set. International Journal of Approximate Reasoning，2014，55：867-884

[9] Anping Zeng， Tianrui Li， Dun Liu，  Junbo Zhang， HongmeiChen. A fuzzy rough set approach for incremental feature selection on hybrid information systems. Fuzzy Sets and Systems，2015， 258：39-60

[10] 劉清.Rough set 及Rough推理[M].北京：科学出版社，2001