属性增加时基于矩阵方法的增量属性约简算法

闫鑫 闫俊辉

摘 要： 随着通信和计算机技术的迅速发展，各行各业都积累了大量数据且这些数据集每时每刻都在动态变化，如何快速计算动态数据属性约简的问题是人工智能领域中的一个重要研究课题。针对决策信息系统属性增加时，如何快速计算变化后决策信息系统约简更新的问题，首先分析了计算变化后决策信息系统相对知识粒度和等价关系矩阵的增量更新机制，然后提出了决策信息系统属性增加后的增量属性约简方法，最后从公共数据网站下载了4组UCI数据集并对所提出的增量属性约简算法进行了仿真实验。实验结果表明了所提出的增量属性约简算法是有效的。

关键词： 粗糙集； 增量机制； 属性约简； 知识粒度

中图分类号：TP18 文献标志码：A 文章编号：1006-8228（2018）03-53-05

Matrix-based incremental attribute reduction method

Yan Xin1， Yan Junhui2

（1. ShanXi University of Finance Economics， Faculty of Information Management， Taiyuan， Shanxi 030006， China；

2. Yuncheng University， Department of Public Computer Teaching）

Abstract： With the fast development of computer network technology and communication technology， many real data in databases may vary dynamically. How to acquiring knowledge effectively and timely from the dynamic data has become an important problem. In this paper， the incremental mechanisms to calculate equivalent relation matrix and relative knowledge granularity based on matrices are introduced when multiple attributes are added into the decision system； The corresponding matrix-based incremental attribute reduction method is developed. Experiments on four data sets downloaded from UCI show that the proposed matrix-based incremental attribute reduction method is effective and efficient.

Key words： rough set； incremental mechanism； attribute reduction； knowledge granularity

0 引言

随着通信和计算机技术的迅速发展，各行各业都积累了大量数据，数据每时每刻都在动态变化。例如学校教务部门和人事部门都有教师的信息，如果把教务部门和人事部门的教师信息整合起来，就会造成信息系统属性增加等。针对决策信息系统属性增加时如何快速更新约简问题，如果使用非增量属性约简算法[1-3]来处理动态数据属性约简时，不能有效利用先前的计算结果，导致运行速度较慢。

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

矩阵在处理数值计算方面具有很大的优势，已被广泛应用到数据挖掘、数值分析和知识发现等学科领域中。针对决策信息系统属性增加后如何快速计算变化后决策信息系统约简的问题，首先探讨了计算变化后决策信息系统相对知识粒度和等价关系矩阵的增量更新机制，然后设计了决策信息系统属性增加后的增量属性约简方法，最后通过UCI数据对所提出的增量属性约简算法的性能进行了测试，实验结果验证了所提出的增量属性约简算法能有效处理动态属性约简的问题。

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

定义1[10] 信息系统是一个四元组，其中U是信息系统论域，C是信息系统的条件属性集，D是信息系统的决策属性集，，Va为信息系统条件属性a的数值，是信息函数，且，有。

定义2[6] 假设决策信息系统为， U/C={X1，X2，…，Xm}是决策信息系统论域U上的划分，RC是决策信息系统的等价关系，是等价关系矩阵，则其元素被定义为：

为了表示方便，下文中可简写为。

定义3[7] 假设决策信息系统为，U/C={X1，X2，…，Xm}是决策信息系统论域U上的划分，决策信息系统条件属性C的知识粒度定义为，且是矩阵所用元素的平均值。

定义4[6] 假设决策信息系统为，，分别是决策信息系统论域U上的等价关系矩阵，，决策信息系统C关于D的相对知识粒度定义为：

定义5[6] 假设决策信息系统为，，，，分别是决策信息系统论域U上的等价关系矩阵，，a在决策信息系统C相对于D的重要性（内重要性）被定义为：

定义6[6] 假设决策信息系统为，C0?C，，，，分别是决策信息系统论域U上的等价关系矩阵，，属性a在属性C0相对于D的重要性（外重要性）定义为：

定义7[1] 假设决策信息系统为， B?C，B是决策信息系统约简当且仅当：

⑴ GD（D|B）=GD（D|C）；

⑵ 对于，使得GD（D|B-{a}）≠GD（D|C）。

根据上述相关的定义，许多学者提出了一种基于矩阵方法的非增量属性约简算法[6]。

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

当决策信息系统增加属性时，用非增量属性约简算法运行变化后的决策信息系统，因为不能有效利用先前的计算结果，导致运行速度较慢。为了快速获得变化后决策信息系统的约简，设计了决策信息系统增加属性后的增量属性约简算法。

2.1 知识粒度的增量机制

定义8 假设决策信息系统为，。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，。决策信息系统增加属性后的增量矩阵的元素定义为：

定义9 假设决策信息系统为，。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，。决策信息系统增加属性后的增量矩阵的元素定义为：

定理1 假设决策信息系统为，是决策信息系统的等价关系矩阵。假设：增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵为，决策信息系统增加属性后的知识粒度变为：

其中，为矩阵所有元素的和。

定理2 假设决策信息系统为，是决策信息系统的等价关系矩阵。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵为，决策信息系统增加属性后的知识粒度变为：

定理3 假设决策信息系统为，、分别是决策信息系统的等价关系矩阵。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵分别为、，决策信息系统增加属性后的知识粒度变为：

2.2 属性增加时基于矩阵方法的增量属性约简算法

当决策信息系统属性增加时，根据上述计算决策信息系统等价关系矩阵和相对知识粒度增量机制的定义和定理，在原来决策信息系统相对知识粒度和约简的基础上，设计了属性增加时基于矩阵方法的增量属性约简算法，算法的具体过程如Algorithm 1所示。

2.3 算法复杂度分析

基于矩阵方法的增量算法的时间复杂度计算过程如下：当决策信息系统增加属性时，计算其相对知识粒度的时间复杂度为（其中w为增加属性的数值），计算属性增加后决策信息系统约简的时间复杂度为，删除属性约简中的冗余属性时间复杂度为。基于矩阵方法的增量约简算法总的时间复杂度为。而文献[6]所提出的非增量属性约简算法总的时间复杂度为：

通过上述分析，我们可得非增量属性约简算法的时间复杂度大于增量属性约简算法的时间复杂度，表明了所提出的基于矩阵的增量属性约简算法是可以有效处理动态数据。

3 实验仿真分析

为了验证本文增量属性约简算法的有效性，我们从公共数据集上下载了4组UCI数据集作为仿真实验数据集，数据集描述如表1所示，分别用增量和非增量属性约简算法运行这些数据集，并对增量属性约简算法和非增量属性约简算法的运行时间进行比较分析。

仿真实验的硬件环境：CPU 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。

表1 数据集具体描述

[序号 数据集 行 条件属性 决策属性 1 Backup-large 307 35 19 2 Kr-vs-kp 3196 36 2 3 Ticdata2000 5822 85 2 4 Mushroom 5644 22 2 ]

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

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

（a） Backup-large

（b） Kr-vs-kp

（c） Ticdata2000

（d） Mushroom

图1 增量属性约简算法和非增量属性约简算法运行时间的比较

从图1可得，当决策信息系统属性增加时，基于矩阵方法的增量属性约简算法的运行时间远远小于非增量属性约简算法的运行时间，说明了所提出的基于矩阵方法的增量属性约简算法是有效的。

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

在计算分类精度实验过程中，我们把表1中数据按照属性分成基本数据集和为增量数据集，其中基本数据集由50%的条件属性和决策属性组成，增量数据集由剩余部分的数据组成，当增量数据集被增加到基本数据集时，分别用非增量属性约简算法和增量属性约简算法计算数据集的约简。最后，运用贝叶斯分类方法和十字交叉方法计算增量与非增量属性约简算法所求約简的分类精确度，并对分类精确度进行分析比较，计算结果如表2所示。

表2 比较增量属性约简算法和非增量属性约

简算法获得约简的分类精确度

[数据集 增量属性约简算法 非增量属性约简算法 Backup-large 0.811075 0.902280 Kr-vs-kp 0.901439 0.884543 Ticdata2000 0.730849 0.812405 Mushroom 0.997638 0.998819 ]

从表2可以看到非增量和增量属性约简算法所获得约简的分类精确度的数值是相近的，除数据集Kr-vs-kp，对于剩下的三个数据集，增量属性约简算法获得约简的分类精确度大于非增量算法获得约简的分类精确度。实验结果表明了，当决策信息系统条件属性增加时，所提出的基于矩阵方法的增量属性约简算法能够找到一个有效的约简。

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] 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

[5] Feng Wang， Jiye Liang， Chuangyin Deng. Attribute

reduction：A dimension incremental strategy. Knowledge-

Based Systems，2013.39：95-108

[6] 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

[7] 王磊，叶军.知识粒度计算的矩阵方法及其在属性约简中的

应用[J].计算机工程与科学，2013.35（3）：98-102

[8] Anping Zeng， Tianrui Li， Dun Liu， Junbo Zhang， Hongmei

Chen. A fuzzy rough set approach for incremental feature selection on hybrid information systems. Fuzzy Sets and Systems， 2015.258：39-60

[9] Wenhao Shu， Hong Shen. Updating attribute reduct in

incomplete decision systems with the variation of attribute set. International Journal of Approximate Reasoning，2014.55：867-884

[10] 刘清.Rough set 及Rough推理[M].科学出版社，2001.