时俊鹏 ,张燕兰*
（1.闽南师范大学计算机学院,福建漳州 363000；
2.数据科学与智能应用福建省高校重点实验室,福建漳州 363000）
波兰学者Pawlak 提出的粗糙集理论[1]能被有效地用于定量处理和分析不确定、不协调、不完备等数据.Pawlak 粗糙集在近似目标概念时需要对论域中所有对象进行计算，这种粗糙集被称作全局粗糙集.而Qian等提出的局部粗糙集[2]，不需要用论域中的所有对象来近似目标概念，只需要考虑目标概念中的对象，为有限标签大数据集的知识发现提供了一种有效的方法.由于局部粗糙集的这一明显特性，学者们着重研究了几种针对不同信息系统的广义局部粗糙集模型[3-5].其中，局部邻域粗糙集[3]是一种处理数值型数据的重要模型.
随着信息技术的发展，社会各领域的数据都在不断变化.在粗糙集理论中，数据集的动态更新通常可以表示为信息系统的动态变化，这些变化主要体现在属性值、对象集和属性集的变化上.目前，已有很多关于动态信息系统的研究[6-18].Luo等[9-11]分别研究了在等价关系和特性关系下就对象变化时概率粗糙集近似集的更新问题，然后进一步探索了特征值变化时决策粗糙集在不完备多尺度信息系统中近似算子的增量更新方法；
Xu等[12-13]针对对象变化提出了概率粗糙集模型三支决策的增量更新算法，并进一步给出一种流数据环境下的快速计算三支决策域动态变化方法；
Zhang等[14]面向特征值改变的情况提出了动态的三支决策粗糙集；
赵小龙等[15]针对对象集变化，研究了邻域信息系统中邻域粒化条件熵的动态更新方法，并提出了相应的增量特征选择算法；
杨臻等[16]研究了混合型信息系统中对象变化时条件概率的变化关系，并提出了变精度粗糙集模型近似算子的增量式更新机制；
孙海霞等[17]借鉴文献[16]中关于变精度粗糙集的增量更新研究思路，构造出邻域信息系统中对象变化时决策粗糙集近似集的增量更新算法；
Li等[18]在有序信息系统中研究了对象集变化时全局和局部多粒度粗糙集上近似算子动态更新的相关算法.总之，关于动态数据环境下粗糙集模型的增量更新算法研究，已经取得了很多的成果.但是，这些研究成果大部分是基于全局粗糙集的，对局部粗糙集增量式更新的研究较少，且针对局部邻域粗糙集还未有相关研究.
针对邻域信息系统中对象集变化的情况，分析邻域信息系统中对象的邻域类与目标概念之间包含度的关系，然后基于该关系给出局部近似集的增量更新公式，最后提出了相应的增量更新算法.对比实验表明，所设计的增量更新算法在处理动态数值型数据时计算性能更高，有助于推动局部邻域粗糙集理论在动态数值型数据下知识发现的应用.
在粗糙集研究领域中，将数据集表示成信息系统IS=(U,AT)，其中U是非空有限对象集，称为论域，AT是非空有限属性集.如果属性集AT=C∪D且C∩D=∅，则C是条件属性集，D是决策属性集，那么此信息系统也被称为决策信息系统.对于∀x∈U和∀a∈AT，将对象x在属性a下的属性值表示为a(x).若条件属性值均为数值型数据时，那么该信息系统又称为邻域信息系统.
为了在邻域信息系统中进行高效的知识发现，Wang 等将邻域关系引入局部粗糙集模型[2]中，提出了局部邻域粗糙集[3]，下面给出相关定义.
定义1[3]设邻域信息系统IS=(U,C∪D)，定义属性集A⊆C下的邻域关系为
定义∀x∈U在邻域关系下的邻域类为
其中，δ为非负常数，称之为邻域半径.dA(x,y)表示对象x与y之间的距离，采用闵可夫斯基距离，定义为
基于邻域的思想，Wang等[3]提出了局部近似集及局部邻域粗糙集的定义.
定义2[3]设邻域信息系统IS=(U,C∪D)，属性集A⊆C.定义对象集X⊆U关于邻域关系NA的局部下近似和局部上近似为
其中，0≤β＜α≤1,D(X|δA(x))表示对象x的邻域类关于集合X的包含度，定义为
性质1[3]设邻域信息系统IS=(U,C∪D)，属性集A⊆C.那么，对于任何X,Y⊆U，0≤β＜α≤1，下列性质成立：
本节研究邻域信息系统中对象增加时局部邻域粗糙集的增量式更新公式.邻域类与目标概念之间包含度的计算是局部邻域粗糙集模型的基础，首先探究对象增加时包含度的关系.
记邻域信息系统为IS=(U,C∪D)，属性集A⊆C.当邻域信息系统中增加对象x+，记新的邻域信息系统为IS+=(U+=U∪{x+},C∪D).将对象x∈U在论域U下的邻域类记为，将对象x∈U+在论域U+下的邻域类记为.
命题1设X,Y⊆U，X+,Y+⊆U+且X+=X∪{x+}，Y+=Y，那么：
命题1 给出邻域信息系统的对象增加后，新信息系统中各对象的邻域类在目标概念下的包含度的关系，以这种关系为基础，可以得到局部下近似集的增量式更新公式.
定理1已知X,Y⊆U关于属性集A⊆C的局部下近似集.设X+,Y+⊆U+并且X+=X∪{x+}，Y+=Y，则
基于第2 节给出的局部近似集的增量更新公式，本节提出相对应的增量更新算法并通过例子阐述该算法.
算法1对象增加时局部邻域粗糙集的增量更新算法
对于算法1，步骤①至步骤③是信息系统增加一个对象时局部邻域下近似集的动态更新算法.如果对增加的对象集合ΔU中的对象按步骤①至步骤③进行迭代，则可在对象集增加时动态更新局部邻域下近似集.算法在迭代过程中需计算增加对象的邻域类和一些与该邻域类有关系的对象的邻域类.设条件属性集的个数为|C|，第j次迭代需计算的邻域类个数为sj+1.则第j次迭代算法的时间复杂度为O((sj+1)||U|+j||C|).设|ΔU|次迭代需重新计算的邻域类总数为S，则算法1的时间复杂度为
即O(S|C|(|U||ΔU|+|ΔU|2+|ΔU|)).
以下通过一个例子，分析并阐述邻域信息系统的对象增加后，如何利用本节所提出的更新算法，来实现局部下近似集的增量式更新.
例1表1是一个邻域信息系统IS=(U,C∪D)，C={a1,a2,a3,a4}是条件属性集，D={d}是决策属性集，设邻域半径δ=1.5，α=0.5，令属性集A=C.
表1 邻域信息系统Tab.1 A neighborhood information system
论域U关于决策属性集D的划分为U/D={D1={x1,x2},D2={x3}}.
假设将表2中的对象集加入到表1中，并利用定理1对局部下近似集进行增量式更新计算.
表2 新增数据对象Tab.2 A new data object
步骤1将x4添加到原信息系统IS中，新信息系统记为IS+=(U+,C∪D)，其中U+=U∪{x4}.
步骤2邻域信息系统IS+中论域U+关于决策属性集D的划分更新为，并计算新增对象x4的邻域类={x1,x4}.
本节通过实验来验证所提出的算法1的高效性和有效性.
表3 中列出了实验中使用的数据集，这些数据集都是从UCI机器学习数据库中下载的.实验的操作环境为：1)CPU为Intel(R)Core(TM)i5-8250U CPU，1.60 GHz；
2)操作系统为Windows 10 64位；
3)内存为8.0 GB；
4)开发平台为Eclipse IDE 2018-12，Java，JDK 1.8.0.
表3 数据集描述Tab.3 Descriptions of datasets
由于表3 中的6 组UCI 数据集是静态不变的，为模拟现实生活中数据的动态变化，本实验做如下处理：将表中的每份数据集分为10 份对象数相等且不相交的子数据集，继而逐步合并子数据集模拟现实中的动态数据集.针对信息系统中对象增加的情况，选择一份子数据集作为原始信息系统，然后选择其他的子数据集添加到原始信息系统中，构造出一次信息系统的动态变化过程.通过将10 份子数据集逐一合并，构造出9 次信息系统的动态变化过程.实验中对各数据集的属性值进行归一化处理，设定阈值α=0.5.文献[19]经过多次实验确定参数δ在[0.2，0.4]之间取值较为理想，故本实验设定邻域半径δ=0.2.
对于表3 中的六组不同的UCI 数据集，图1 分别比较了信息系统中对象添加时增量算法和非增量算法[3]的性能，实验重复进行5次取平均结果.图1中，横坐标表示数据集的动态变化次数，纵坐标表示算法的计算耗时.从图1 可以看出，增量算法的效率比非增量算法更高.随着邻域信息系统中动态变化次数的逐渐增加，增量算法和非增量算法的耗时均呈现逐渐增加的趋势.然而，非增量算法的耗时逐渐增加且增长率逐渐变大.和非增量算法相比，增量式算法的效率更加稳定，而且非增量算法与增量式算法的耗时差值随数据集动态变化次数的增加而逐渐增大.这验证了增量算法能有效地利用原信息系统中已有的知识，减小知识发现过程中的计算量.实验结果验证了在求解动态数值型数据的局部近似集时，设计的增量算法比非增量算法具有更好的性能和更高的效率.
图1 增量算法与非增量算法计算耗时对比图Fig.1 Comparison chart of calculation time consumption of incremental algorithm and non-incremental algorithm
动态数值型数据的分析与处理已成为数据挖掘领域中的一个重要研究课题.针对动态数值型数据，提出了一种针对对象变化的局部邻域粗糙集的增量更新算法.首先，给出了邻域信息系统的对象增加时局部邻域粗糙集中包含度的关系，并在此基础上提出了局部近似算子的增量更新公式.然后，针对邻域信息系统中添加对象的情况，设计了局部近似集的增量更新算法.所设计的算法可以避免重复计算，利用已有结果高效地求解局部近似集.
在仿真实验中，选取六组UCI 数据集，对非增量算法和所设计的增量算法计算近似集的耗时进行对比.实验结果验证了所设计的增量更新算法计算效率更高，并且增量算法的性能受数据集动态变化次数的影响较小.在下一步工作中，将研究当邻域信息系统的属性集和属性值发生变化时局部邻域粗糙集模型的更新问题.
猜你喜欢 论域粗糙集邻域 粗糙集与包络分析下舰船运行数据聚类算法舰船科学技术(2022年20期)2022-11-28基于隶属函数的模糊覆盖粗糙集新模型聊城大学学报（自然科学版）(2022年5期)2022-10-29基于混合变邻域的自动化滴灌轮灌分组算法农业工程学报(2022年7期)2022-07-09基于Simulink变论域算法仿真技术研究计算机仿真(2022年2期)2022-03-15含例邻域逻辑的萨奎斯特对应理论逻辑学研究(2021年3期)2021-09-29融合t-分布随机邻域嵌入与自动谱聚类的脑功能精细分区方法波谱学杂志(2021年3期)2021-09-07着舰指挥官非对称变论域模糊引导技术哈尔滨工程大学学报(2021年7期)2021-07-13基于变论域模糊控制的Taylor逼近型内模PID算法成都信息工程大学学报(2021年6期)2021-02-12双论域上基于加权粒度的多粒度粗糙集*计算机与数字工程(2019年8期)2019-09-03多粒度犹豫模糊粗糙集*计算机与数字工程(2019年8期)2019-09-03