闫鑫闫俊辉
摘要：随着通信和计算机技术的迅速发展，各行各业都积累了大量数据且这些数据集每时每刻都在动态变化，如何快速计算动态数据属性约简的问题是人工智能领域中的一个重要研究课题。针对决策信息系统属性增加时，如何快速计算变化后决策信息系统约简更新的问题，首先分析了计算变化后决策信息系统相对知识粒度和等价关系矩阵的增量更新机制，然后提出了决策信息系统属性增加后的增量属性约简方法，最后从公共数据网站下载了4组UCI数据集并对所提出的增量属性约简算法进行了仿真实验。实验结果表明了所提出的增量属性约简算法是有效的。
关键词：粗糙集；增量机制；属性约简；知识粒度
中图分类号：TP8文献标志码：A文章编号：006-8228（208）03-53-05
Mtrx-drtlttrbutrdutthd
YX，YJuhu2
（ShXUvrstyfFEs，FultyfIfrtMt，Tyu，Shx030006，Ch；
2YuhUvrsty，DprttfPublCputrTh）
Abstrt：Wththfstdvlptfputrtrthlydutthly，yrldtdtsyvrydyllyHtqurldfftvlydtlyfrthdydthsbprttprblIthsppr，thrtlhsstlultquvltrlttrxdrltvldrulrtydtrsrtrdudhultplttrbutsrdddtthdssyst；Thrrspdtrx-drtlttrbutrdutthdsdvlpdExprtsfurdtstsdlddfrUCIshthtthprpsdtrx-drtlttrbutrdutthdsfftvdfft
Kyrds：ruhst；rtlhs；ttrbutrdut；ldrulrty
0引言
随着通信和计算机技术的迅速发展，各行各业都积累了大量数据，数据每时每刻都在动态变化。例如学校教务部门和人事部门都有教师的信息，如果把教务部门和人事部门的教师信息整合起来，就会造成信息系统属性增加等。针对决策信息系统属性增加时如何快速更新约简问题，如果使用非增量属性约简算法[-3]来处理动态数据属性约简时，不能有效利用先前的计算结果，导致运行速度较慢。
由于非增量属性约简算法不能有效处理动态变化数据属性约简的问题，因此很多学者设计了增量属性约简算法去解决动态变化数据属性约简的问题。Q等根据决策信息系统中属性动态增加和减少情况下的信息粒度变化规律，提出正向近似和逆向近似，并成功应用于启发式属性约简算法的加速，为基于粗糙集的知识发现性能优化提供了新思路[4]；W等分析了一些属性动态增加情况下三种信息熵的增量变化机制，提出了一种基于信息熵的增量属性约简算法[5]；J针对决策信息系统对象属性集动态变化时如何快速计算约简问题，讨论了计算等价关系矩阵和相对知识粒度的增量更新原理，提出了基于对象增加时动态属性约简算法[6]；王磊等分析了属性动态变化下用矩阵方法计算知识粒度的增量更新原理，提出了一种属性集动态变化增量属性约简算法[7]；Z等给出了一种新的混合距离概念，结合混合距离和高斯核，分析了当决策信息系统在属性变化下属性约简的增量更新机制，提出了混合决策信息系统中基于模糊粗糙集动态属性约简算法，并对该算法进行了实验验证[8]。Shu等在不完备系统中，分析了属性集动态增加或删除情况下决策信息系统正区域的动态更新机制，提出了基于正区域的动态属性约简算法[9]。根据上面分析，当决策信息系统属性增加时，大多數增量算法主要通过更新信息熵和正区域实现快速获取变化后决策信息系统的约简，而通过更新知识粒度实现快速获取变化后决策信息系统约简的算法研究较少。
矩阵在处理数值计算方面具有很大的优势，已被广泛应用到数据挖掘、数值分析和知识发现等学科领域中。针对决策信息系统属性增加后如何快速计算变化后决策信息系统约简的问题，首先探讨了计算变化后决策信息系统相对知识粒度和等价关系矩阵的增量更新机制，然后设计了决策信息系统属性增加后的增量属性约简方法，最后通过UCI数据对所提出的增量属性约简算法的性能进行了测试，实验结果验证了所提出的增量属性约简算法能有效处理动态属性约简的问题。
基于矩阵方法的非增量属性约简算法
定义[0]信息系统是一个四元组，其中U是信息系统论域，C是信息系统的条件属性集，D是信息系统的决策属性集，，V为信息系统条件属性的数值，是信息函数，且，有。
定义2[6]假设决策信息系统为，U/C={X，X2，…，X}是决策信息系统论域U上的划分，RC是决策信息系统的等价关系，是等价关系矩阵，则其元素被定义为：
为了表示方便，下文中可简写为。
定义3[7]假设决策信息系统为，U/C={X，X2，…，X}是决策信息系统论域U上的划分，决策信息系统条件属性C的知识粒度定义为，且是矩阵所用元素的平均值。
定义4[6]假设决策信息系统为，，分别是决策信息系统论域U上的等价关系矩阵，，决策信息系统C关于D的相对知识粒度定义为：
定义5[6]假设决策信息系统为，，，，分别是决策信息系统论域U上的等价关系矩阵，，在决策信息系统C相对于D的重要性（内重要性）被定义为：
定义6[6]假设决策信息系统为，C0?C，，，，分别是决策信息系统论域U上的等价关系矩阵，，属性在属性C0相对于D的重要性（外重要性）定义为：
定义7[]假设决策信息系统为，B?C，B是决策信息系统约简当且仅当：
⑴GD（D|B）=GD（D|C）；
⑵对于，使得GD（D|B-{}）≠GD（D|C）。
根据上述相关的定义，许多学者提出了一种基于矩阵方法的非增量属性约简算法[6]。
2基于矩阵方法的增量属性约简算法
当决策信息系统增加属性时，用非增量属性约简算法运行变化后的决策信息系统，因为不能有效利用先前的计算结果，导致运行速度较慢。为了快速获得变化后决策信息系统的约简，设计了决策信息系统增加属性后的增量属性约简算法。
2知识粒度的增量机制
定义8假设决策信息系统为，。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，。决策信息系统增加属性后的增量矩阵的元素定义为：
定义9假设决策信息系统为，。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，。决策信息系统增加属性后的增量矩阵的元素定义为：
定理假设决策信息系统为，是决策信息系统的等价关系矩阵。假设：增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵为，决策信息系统增加属性后的知识粒度变为：
其中，为矩阵所有元素的和。
定理2假设决策信息系统为，是决策信息系统的等价关系矩阵。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵为，决策信息系统增加属性后的知识粒度变为：
定理3假设决策信息系统为，、分别是决策信息系统的等价关系矩阵。假设增量属性集是P，Rp是决策信息系统论域U上的一个等价关系，决策信息系统增加属性后的增量矩阵分别为、，决策信息系统增加属性后的知识粒度变为：
22属性增加时基于矩阵方法的增量属性约简算法
当决策信息系统属性增加时，根据上述计算决策信息系统等价关系矩阵和相对知识粒度增量机制的定义和定理，在原来决策信息系统相对知识粒度和约简的基础上，设计了属性增加时基于矩阵方法的增量属性约简算法，算法的具体过程如Alrth所示。
23算法复杂度分析
基于矩阵方法的增量算法的时间复杂度计算过程如下：当决策信息系统增加属性时，计算其相对知识粒度的时间复杂度为（其中为增加属性的数值），计算属性增加后决策信息系统约简的时间复杂度为，删除属性约简中的冗余属性时间复杂度为。基于矩阵方法的增量约简算法总的时间复杂度为。而文献[6]所提出的非增量属性约简算法总的时间复杂度为：
通过上述分析，我们可得非增量属性约简算法的时间复杂度大于增量属性约简算法的时间复杂度，表明了所提出的基于矩阵的增量属性约简算法是可以有效处理动态数据。
3实验仿真分析
为了验证本文增量属性约简算法的有效性，我们从公共数据集上下载了4组UCI数据集作为仿真实验数据集，数据集描述如表所示，分别用增量和非增量属性约简算法运行这些数据集，并对增量属性约简算法和非增量属性约简算法的运行时间进行比较分析。
仿真实验的硬件环境：CPUPtu（R）Dul-CrE5800320GHz，内存SsuDDR3SDRAM，40GB。
实验仿真；软件环境：64-btWds0操作系统，64-bts（JDK60_20）和Elps37。
表数据集具体描述
[序号 数据集 行 条件属性 决策属性 Bup-lr 307 35 9 2 Kr-vs-p 396 36 2 3 Tdt2000 5822 85 2 4 Mushr 5644 22 2 ]
3增量屬性约简算法与非增量属性约简算法运行时间比较
在仿真实验的过程中，我们把表的数据集按照属性分成2部分，其中50%的条件属性和决策属性为基本数据集，剩余50%的数据在按照数学的20%、40%、60%、80%、00%依次作为增量属性集，分别用增量和非增量属性约简算法运行这些数据集，仿真实验结果如图（）-（d）所示，其中纵轴表示计算约简的运行时间，横轴表示数据集中增加属性的百分数。圆形蓝色线表示非增量属性约简算法的计算时间，方形红色线表示增量属性约简算法的计算时间。
（）Bup-lr
（b）Kr-vs-p
（）Tdt2000
（d）Mushr
图增量属性约简算法和非增量属性约简算法运行时间的比较
从图可得，当决策信息系统属性增加时，基于矩阵方法的增量属性约简算法的运行时间远远小于非增量属性约简算法的运行时间，说明了所提出的基于矩阵方法的增量属性约简算法是有效的。
32增量属性约简算法与非增量属性约简算法所得约简分类精确度比较
在计算分类精度实验过程中，我们把表中数据按照属性分成基本数据集和为增量数据集，其中基本数据集由50%的条件属性和决策属性组成，增量数据集由剩余部分的数据组成，当增量数据集被增加到基本数据集时，分别用非增量属性约简算法和增量属性约简算法计算数据集的约简。最后，运用贝叶斯分类方法和十字交叉方法计算增量与非增量属性约简算法所求約简的分类精确度，并对分类精确度进行分析比较，计算结果如表2所示。
表2比较增量属性约简算法和非增量属性约
简算法获得约简的分类精确度
[数据集 增量属性约简算法 非增量属性约简算法 Bup-lr 08075 0902280 Kr-vs-p 090439 0884543 Tdt2000 0730849 082405 Mushr 0997638 099889 ]
从表2可以看到非增量和增量属性约简算法所获得约简的分类精确度的数值是相近的，除数据集Kr-vs-p，对于剩下的三个数据集，增量属性约简算法获得约简的分类精确度大于非增量算法获得约简的分类精确度。实验结果表明了，当决策信息系统条件属性增加时，所提出的基于矩阵方法的增量属性约简算法能够找到一个有效的约简。
4结束语
针对决策信息系统属性增加时如何快速更新约简的问题，本文首先探讨了属性增加后基于矩阵方法计算等价关系矩阵的增量更新机制，然后提出决策信息系统增加属性时的增量属性约简方法，最后在公共数据集下载UCI数据集并对所提出的基于矩阵方法的增量属性约简算法进行仿真实验，实验结果验证了属性增加时的基于矩阵方法的增量属性约简算法是有效的。下一步将研究多粒度粗糙集模型中属性变化下如何快速更新约简的问题。
参考文献（Rfrs）：
[]苖夺谦，范世栋知识粒度的计算及其应用[J]系统工程理论
与实践，200222（）：48-5
[2]王国胤，于洪，杨大春基于条件信息熵的决策表约简[J]计算
机学报，200225（7）：760-765
[3]梁吉业，曲开社，徐宗本信息系统的属性约简[J]系统工程理
论与实践，2002（2）：76-80
[4]YuhuQ，JyL，WtldPdryz，ChuyD
Pstvpprxt：AlrtrfrttrbutrdutruhstthryArtflItll，20074（9-0）：597-68
[5]FW，JyL，ChuyDAttrbut
rdut：AdsrtlstrtyKld-
dSysts，20339：95-08
[6]YuJ，TruL，ChuLu，Sh-JHr，
GuyW，ZYuArtlpprhfrttrbutrdutdldrulrty[J]Kld-dSysts，20604（C）：24-38
[7]王磊，叶军知识粒度计算的矩阵方法及其在属性约简中的
应用[J]计算机工程与科学，20335（3）：98-02
[8]ApZ，TruL，DuLu，JubZh，H
ChAfuzzyruhstpprhfrrtlfturslthybrdfrtsystsFuzzyStsdSysts，205258：39-60
[9]WhShu，HShUpdtttrbutrdut
pltdssystsththvrtfttrbutstItrtlJurlfApprxtRs，20455：867-884
[0]刘清Ruhst及Ruh推理[M]科学出版社，200
文章来源于：计算机时代