基于区间值信息系统的信息熵增量式属性约简算法

焦玉清 张 勇

（巢湖学院信息工程学院 安徽合肥 238000）

属性约简是粗糙集理论和粒计算理论的重要研究问题[1-2]，其目的是为了消除数据集内部的冗余属性，提高数据集的知识发现性能。然而实际应用中的数据集总是处于不断动态更新之中，针对这类数据环境，一种被称为增量式属性约简的方法被提出[3-5]，从而提高了动态数据的属性约简性能。

针对增量式属性约简，学者在各种类型的信息系统进行了相关的研究。Shu等[6]在传统的完备型信息系统中提出了对象增加时的增量式属性约简算法；在不完备信息系统方面，丁棉卫等[7]利于矩阵的方法设计出了相应的增量式属性约简算法，Xie等[8]在其基础上提出了一种改进的不完备信息系统增量式属性约简算法；在数值型的邻域信息系统中，赵小龙等[9]研究了邻域条件熵的增量式更新，并进一步地提出了一种邻域条件熵的增量式属性约简算法；在数值型和离散型混合类型的信息系统中，段海玲等[10]通过构造邻域知识粒度的增量式更新设计出相应的增量式属性约简，同时在不完备混合型信息系统，王映龙等[11]利用变精度粗糙集模型设计出一种增量式属性约简算法。此外，在多粒度的数据环境下，Hu等[12]研究了一种多粒度视角的增量式更新方法；在集值信息系统中，Lang等[13]提出一种高效的增量式属性约简算法。总之各类信息系统的增量式属性约简研究已是目前属性约简领域的研究热点。

区间值信息系统是一种以区间值为属性值的信息系统，多见于医学诊断应用中，然而对于这种类型的信息系统，目前很少有相关的增量式属性约简研究。在文献[14]中，Xie等在区间值信息系统下提出了一种θ信息熵的不确定性度量方法，并利用θ信息熵提出了相应的属性约简算法。本文将在该算法的基础上，进一步提出一种论域动态增加的θ信息熵增量式属性约简算法。文章中采用由简单到复杂的研究思路，首先研究区间值信息系统论域增加单个对象时θ信息熵的增量式更新，然后在其基础上，进一步研究增加多个对象时θ信息熵的增量式更新。根据θ信息熵的增量式更新方法，本文提出了相应的增量式属性约简算法，实验证明了所提出算法的有效性和优越性。

一、区间值信息系统的信息熵模型

二、区间值信息系统信息熵的增量式属性约简算法

由于实际环境下的信息系统是不断动态更新的，因此传统的属性约简算法不再有效。近年来，学者们进一步提出了增量式属性约简，使得大幅度提升了动态环境下属性约简的性能[3-5]。本文将针对区间值信息系统对象增加的环境，提出一种信息熵的增量式属性约简算法。

（一）区间值信息系统的信息熵增量式更新。

定理2表明，当区间值信息系统论域增加多个对象时，可以依次对每个增加的对象在对应的论域下计算相应的相似类，然后按照定理2所示的增量式更新公式得到最终新的θ信息熵，大幅度减少了重复的计算量。

（二）增量式属性约简算法。

以上推证得到了区间值信息系统信息熵随对象增加时的增量式变化关系，利用这种关系可以进一步得到区间值信息系统的信息熵增量式属性约简算法。

定义6表明，属性约简集与条件属性全集具有相同的θ信息熵结果，并且删除属性约简集中任意一个属性都不满足此条件。当区间值信息系统增加对象后，对应的θ信息熵会发生变化，我们需要进一步探究θ信息熵的大小是具体如何变化的，这样为增量式属性约简算法的构造提供一定的理论基础。

算法1所示的增量式属性约简算法，不同于文献[14]的非增量式算法，算法2在原先旧区间值信息系统的信息熵和约简集的基础上进行进一步属性约简搜索，首先根据旧信息熵计算新的信息熵，然后比较新旧信息熵的大小来进行相应的搜索属性策略，最后得到新信息系统的属性约简结果。文献[14]中所示的非增量式属性约简算法的时间复杂度为O(|C|2⋅|U⋃ΔU|2),本文算法2的时间复杂度可表示为O(|C-red|⋅|red|⋅|U|⋅|ΔU|).

三、实验分析

本节将通过实验来验证所提出的区间值信息系统增量式属性约简算法的有效性。整个实验环节主要分为三个部分，第一部分是将本文的增量式属性约简算法与文献[14]所提出的非增量式算法针对动态区间值数据集进行属性约简，比较它们的属性约简效率。第二部分将本文所提出的增量式属性约简算法与文献[15]提出的区间值信息系统增量式属性约简算法进行动态数据集属性约简效率的比较，验证本文算法的优越性。第三部分是研究不同阈值参数θ对本文增量式属性约简算法的效率影响。

表1所示的是实验中进行属性约简的数据集，这里的数据集1～3来源于UCI数据集库，数据集4～5为人工随机生成的区间值数据集，其中每个数据集均为静态的，为了模拟数据集对象动态增加的环境，本实验采用文献[3,9-10]的处理方法，将原始数据集根据对象平均分割成多个子数据集，然后将这些子数据集进行逐步合并，其中合并的过程便构造出数据集对象的动态增加，本实验将数据集平均分割成10个部分，这样可以构造数据集的9次更新。本实验运行的硬件环境为英特尔酷睿i57500CPU(主频3.4GHz)，内存为DDR4 8GB，算法采用Matlab2016进行编程实现。

表1 实验数据集

图1所示的是区间值信息系统θ信息熵的非增量式属性约简和增量式属性约简的用时比较结果,其中θ取值为0.7进行实验，并且实验结果采用的是多次重复实验的平均值。观察图1中各个数据集的实验结果，可以发现随着数据集增量次数的增加，非增量式属性约简算法的处理时间大幅度高于本文提出的增量式属性约简算法，并且非增量式属性约简算法的时间增长速率也是高于本文的算法，本文算法的约简用时增长得较为缓慢。产生这一差距的主要原因是由于它们的算法机制不同导致的，对于区间值数据集的每次增量式更新，非增量式属性约简算法基于新的完整数据集进行属性约简计算，而增量式属性约简算法是在原始信息系统约简结果的基础上进行进一步的计算，这样避免了对旧信息系统的重复计算，提高了约简的效率，因此随着数据集的逐渐增大，增量式属性约简算法的约简用时增长的较为缓慢，效率更加的高。

图1 增量式算法与非增量式算法的动态属性约简时间比较

图2所示的是本文提出的区间值信息系统增量式属性约简算法与文献[15]提出的增量式属性约简算法(记为对比增量式算法)在各个数据集的区间值信息系统下进行动态属性约简的时间比较结果，其中每个子图对应了每个数据集的结果。观察每个子图可以发现，本文提出的增量式属性约简算法的更新约简用时低于对比增量式属性约简算法，并且随着增量更新次数的增加，这种时间的差距愈加明显。产生这一现象的主要原因是由于这两种算法属性约简的度量方法不一样导致的，本文提出的增量式算法以区间值信息系统的信息熵为基础，每次仅需要计算对象的相似类，然后按照信息熵的计算公式便可完成信息熵结果的更新计算，而对比增量式算法是一种基于正区域的方法计算约简，首先需要计算对象的相似类，然后利用相似类进行决策类下近似集的计算，这额外增加了一定的计算量，因此进行增量式计算时产生更高的时间消耗，因此更新属性约简的效率略低于本文算法。

图2 本文算法与对比增量式算法的效率比较

图1和图2的实验结果表明了所提出的增量式属性约简算法有效性和优越性，接下来将进一步分析区间值信息系统中阈值θ对本文增量式属性约简算法效率的影响。

图3所示的是选取不同阈值θ进行各个数据集增量式属性约简的用时比较结果，其中阈值θ在区间[0.5,0.9]中以0.1为间隔分别进行取值。观察图3可以发现，无论θ取为何值，随着数据集增量次数的增加，其属性约简的用时都是逐渐增大的，同时，对于阈值θ的逐渐减小，其同一次增量式属性约简的约简用时是逐渐增大的。这主要是由于随着阈值θ的减小，区间值信息系统中每个对象的相似类都是增大的，而本文算法在进行增量式计算中，需要计算新增对象的相似类，因而其计算时间会增加，所以表现出了图3所示的结果。

图3 不同阈值θ时增量式属性约简用时比较

四、结语

区间值信息系统是一种较为常见的信息系统类型，基于区间值信息系统的属性约简是目前粗糙集领域的研究热点之一。然而由于实际环境下数据集的动态性，使得传统的属性约简算法不具有较高的约简性能。本文针对区间值信息系统论域中对象逐渐动态增加的情形，提出一种信息熵的增量式属性约简算法。文中首先研究了信息系统论域增加单个对象时，区间值信息系统信息熵的增量式更新，然后以单个对象变化为基础，通过迭代的方式给出了信息系统增加多个对象时的信息熵增量式更新问题，最后设计出对应的增量式属性约简算法，实验分析证明所提出增量式属性约简算法的有效性。本文所研究的是区间值信息系统对象增加环境下的增量式属性约简问题，因此接下来可以进一步探索区间值信息系统属性增加时的增量式属性约简，从而可以进一步推动区间值信息系统属性约简的实用化进程。