控制与决策  2020, Vol. 35 Issue (2): 297-308  
0

引用本文 [复制中英文]

杨臻, 邱保志. 混合信息系统的动态变精度粗糙集模型[J]. 控制与决策, 2020, 35(2): 297-308.
[复制中文]
YANG Zhen, QIU Bao-zhi. Dynamic variable precision rough set model of mixed information system[J]. Control and Decision, 2020, 35(2): 297-308. DOI: 10.13195/j.kzyjc.2018.0484.
[复制英文]

基金项目

国家自然科学基金项目(U1304614);河南省基础与前沿技术研究项目(152300410191);河南省科技攻关项目(162102310238)

作者简介

杨臻(1973—), 女, 讲师, 从事数据挖掘、计算机网络等研究, E-mail: husz1979@163.com;
邱保志(1964—), 男, 教授, 博士, 从事数据挖掘、计算机网络等研究, E-mail: luckyao12@163.com

通讯作者

杨臻, E-mail: husz1979@163.com

文章历史

收稿日期:2018-04-18
修回日期:2018-09-13
混合信息系统的动态变精度粗糙集模型
杨臻 1, 邱保志 2     
1. 郑州师范学院 信息科学与技术学院,郑州 450044;
2. 郑州大学 信息工程学院,郑州 450002
摘要:粗糙集是一种针对不确定性数据的数据挖掘理论, 邻域粗糙集是处理混合型数据的常用模型.为了提高对混合型数据的抗噪能力, 提出一种混合信息系统的变精度粗糙集模型; 由于现实环境下信息系统的动态性, 进一步提出对象增加和减少时的动态变精度粗糙集模型.首先研究混合信息系统中条件概率随对象增加和减少时的变化关系, 然后在该变化关系的基础上提出混合信息系统变精度粗糙集上下近似的增量式更新机制, 最后根据这一更新机制提出相应的增量式近似更新算法.实验结果表明, 所提出的增量式更新算法比非增量的算法具有更高的计算效率, 从而验证了所提出模型的有效性, 同时也表明所提出模型更加适用于复杂的数据环境.
关键词信息系统    混合属性    变精度粗糙集    对象变化    动态更新    增量式学习    
Dynamic variable precision rough set model of mixed information system
YANG Zhen 1, QIU Bao-zhi 2     
1. College of Information Science and Technology, Zhengzhou Normal University, Zhengzhou~450044, China;
2. College of Information Engineering, Zhengzhou University, Zhengzhou~450002, China
Abstract: Rough set is a data mining theory for uncertainty data, and neighborhood rough sets are common models for dealing with mixed data. In order to improve the anti noise ability of mixed data, a variable precision rough set model of the mixed information system is proposed. Due to the dynamics of the information system in the real environment, this paper further proposes a dynamic variable precision rough set model when the object is increased and reduced. Firstly, the changed relation of conditional probability with the increasing and decreasing object in the mixed information system is studied. Then, on the basis of this changed relation, an incremental updating mechanism of the upper and lower approximation of the variable precision rough set of the mixed information system is proposed. Finally, according to this updating mechanism, the corresponding incremental approximation updating algorithm is proposed. Experimental results show that the proposed incremental updating algorithm has higher computational efficiency than the non-incremental algorithm, thus the effectiveness of the proposed model is validated, meanwhile, the proposed model is more suitable for complex data environments.
Keywords: information system    mixed attribute    variable precision rough set    object change    dynamic update    incremental learning    
0 引言

粗糙集理论[1]是波兰学者Pawlak提出的一种重要的数据挖掘模型, 它通过对信息系统中的知识进行信息粒化, 从而对不确定性概念进行粗糙逼近计算.由于该模型自身的优越性, 目前已广泛应用于信息系统的特征选择、数据分类和决策分析[2-5]中.

传统的粗糙集模型建立在理想的数据环境下[1], 由于现实应用中数据的复杂性, 学者们针对传统的粗糙集模型进行了扩充与拓展[6], 使得新提出的粗糙集模型具有更广泛的适用性.混合型数据是一种离散型属性和连续型属性并存的数据形式, 并且普遍存在于各类应用系统中. Hu等[7]利用邻域关系处理数值型数据, 并提出了混合型信息系统的邻域粗糙集模型.在此基础上, 学者们将邻域粗糙集模型不断改进和推广[8-11], 同时研究了混合型信息系统的属性约简问题[8-9, 11].因此, 关于混合型信息系统粗糙集的研究已成为目前的一个热点内容.另一方面, 传统的粗糙集模型对含有噪声的数据不具有较好的处理能力, 为了进行改进, Ziarko[12]提出了一种更为稳健的粗糙集模型, 即变精度粗糙集, 该模型通过设定可变精度的方式提高模型的容噪性能, 使得粗糙集模型具有更广泛的运用[13-14].然而, 针对已提出的混合信息系统粗糙集模型, 目前还较少有对抗噪声性能方面的相关研究.

随着计算机与互联网技术的迅速发展, 数据的规模与状态发生了很大变化, 动态性已成为目前数据一个很重要的特征, 传统的数据挖掘模型与算法对动态性的数据不具有较好的处理性能.增量式学习是目前解决数据动态性的一种常用方法, 在粗糙集理论中, 目前已有多种增量式模型和算法被提出.例如, Wang等[15]研究了当信息系统属性增加时条件熵的增量式更新问题, 其中条件熵的增量式计算依赖于发生变化的等价类, 随着属性的增加, 其等价类变化的数量是不确定的, 因此所提出算法的增量式效率并不是很稳定. Liang等[16]针对信息系统对象增加的情形, 研究了条件熵的增量式更新并构造属性约简, 由于与文献[15]的研究思路类似, 算法的效率也不是很稳定. Chen等[17]对决策粗糙集进行了增量式更新的构造, 通过矩阵方法实现, 因此不适合较大规模的数据. Liu等[18]对概率粗糙集进行了增量式更新的构造, 同时Liu等[19]也在动态不完备信息系统下提出了相应的增量式更新方法, 这些增量式算法均仅对新增加的数据进行非矩阵计算, 然后对最终的模型进行更新, 因此两种算法均具有较高的计算效率. Li等[20-21]在优势粗糙集模型中, 分别针对属性的更新和属性值的更新构造了两种增量式更新方法, 然而这两种更新方法都是基于矩阵的计算方式, 也不适合较大规模的数据. Jing等[22]构造了粗糙集中知识粒度随对象增加时的增量式更新, 并提出了一种增量式属性约简算法, 该算法也仅对新增加的数据进行相关计算, 然后在原来知识粒度的基础上更新出最终结果, 因此有较高的属性约简效率.总之, 关于粗糙集理论的增量式学习研究, 目前已取得了大量的成果.然而, 这些相关成果大多是针对离散型的各类信息系统, 对混合型信息系统增量式更新的研究较少.

根据目前的研究现状, 已提出的混合型信息系统粗糙集模型对含噪声的数据不具有较好的处理性能, 因此在混合型信息系统中融入变精度粗糙集, 提出混合信息系统下的变精度粗糙集模型.同时, 对于混合信息系统下粗糙集模型的增量式更新问题, 曾安平[23]提出一种高斯核的动态模糊粗糙集模型, 然而这一动态模型未考虑数据的容噪处理, 促使本文在所提出变精度粗糙集模型的基础上进一步探究相应的增量式更新方法.

本文首先提出混合信息系统下的变精度粗糙集模型, 然后针对混合信息系统对象的动态增加和动态减少, 分别分析变精度粗糙集模型中对象与决策类之间条件概率的更新关系, 同时在该更新关系的基础上分别给出混合信息系统变精度粗糙集上下近似的快速增量更新, 最后提出相应的增量更新算法. UCI实验结果表明, 所提出的增量式更新算法比非增量式的更新算法具有更高的动态更新效率, 更适用于动态的数据环境, 有助于推动粗糙集理论在现实环境下的应用.

1 混合信息系统的变精度粗糙集模型

在粗糙集理论中, 数据集表示为信息系统的形式, 通常信息系统包含多种类型, 如离散型信息系统、连续型信息系统以及混合型信息系统.混合型信息系统简称混合信息系统, 由离散型属性和连续型属性并存构成, 现实中很多信息系统都是混合型的, 针对混合型信息系统的处理分析是机器学习和数据挖掘中一项重要的研究内容.

通常混合型信息系统可以表示为MIS=(U, AT).其中: U为混合型信息系统的论域, 即数据集的样本空间, 每个样本又称为信息系统的对象; AT为属性集, 即数据集的特征空间.若混合型信息系统论域中每个对象都有一个确定的类标记, 则该信息系统又称为混合型决策信息系统, 记为MIS=(U, CD).其中: C为条件属性集, D为决策属性集.

1.1 混合型信息系统的粗糙集模型

传统的Pawlak粗糙集仅能处理离散型信息系统, 为了解决这一局限性, Hu等[7]在信息系统中提出了邻域关系, 使得推广的粗糙集模型可以处理混合型数据.

定义1[7]  设混合型信息系统MIS=(U, AT), 令属性集A⊆AT且A=ADAN, 其中ADAN分别表示属性集A中的离散型属性集和连续型属性集.那么混合信息系统中属性集确定的混合邻域关系定义为

(1)

其中: dAN(x, y)为对象x与对象y之间的距离, 通常采用闵可夫斯基距离[7]度量; δ为邻域半径, 是非负常数; a(x)为对象x在属性a下的属性值.

根据邻域关系, 可以诱导出混合信息系统中对象的邻域类以及整个信息系统的邻域粒化.

定义2[7]  设混合型信息系统MIS=(U, AT), 混合属性集A⊆AT确定的混合邻域关系为MNAδ, 其中δ为邻域半径.那么对于∀xU在邻域关系MNAδ下的混合邻域类定义为

(2)

从粒计算的视角, 对象的混合邻域类也称为该对象的混合邻域粒.将混合信息系统论域中每个对象的混合邻域类看作一个整体, 记

其中U={x1, x2, ..., xn}, 则GSA也称为该混合信息系统的一个粒结构.

定义3[7]  设混合型信息系统MIS=(U, AT), 混合属性集A⊆AT确定的混合邻域关系为MNAδ, 其中δ为邻域半径.对于近似目标集XU, 关于混合邻域关系MNAδ的下近似和上近似分别定义为

(3)
(4)

其中 < MNAδ(X), MNAδ(X)>为近似目标集X的粗糙集, 它是粗糙集理论进行各类粗糙计算的理论基础.

1.2 变精度粗糙集模型

传统的Pawlak粗糙集模型通过在等价类与近似目标集之间进行严格的集合运算来逼近近似集, 这种定义方法比较严格[1], 对于包含噪声数据的信息系统不具有较好的处理效果, 因此近年来学者们提出变精度粗糙集模型[12].

定义4[12]  设离散型信息系统IS=(U, AT), 属性集A⊆AT确定的等价关系为EA, ∀xU在等价关系EA下的等价类定义为[x]A.近似目标集XU关于等价关系EAβ下近似和β上近似分别定义为

(5)
(6)

其中: < EAβ(X), EAβ(X)>为近似目标集X的变精度粗糙集, β为精度且β∈(0.5, 1].这里P(X|[x]A)=|X∩[x]A|/|[x]A|, 即X在[x]A下的条件概率, 表示等价类[x]A中对象分类入X的比例.

1.3 混合型信息系统的变精度粗糙集模型

传统的Pawlak粗糙集拓展为混合数据的邻域粗糙集, 使得粗糙集理论可以处理更多类型数据.传统的Pawlak粗糙集改进为变精度粗糙集, 使得粗糙集理论具有较好的容噪性能.为了使粗糙集理论适用于更为复杂的数据环境, 将混合数据的邻域粗糙集与变精度粗糙集进行结合, 提出混合型信息系统的变精度粗糙集模型.

定义5  设混合型信息系统MIS=(U, AT), 混合属性集A⊆AT确定的混合邻域关系为MNAδ, ∀xU在MNAδ下的混合邻域类为δA (x).近似目标集XU关于混合邻域关系MNAδβ下近似和β上近似分别定义为

(7)
(8)

其中: < MNAβ(X), MNAβ(X)>为近似目标集Xβ变精度粗糙集, β∈(0.5, 1].这里P(X|δA(x))=|XδA (x)|/|δA(x)|, 即XδA (x)下的条件概率.

对于混合型决策信息系统MIS=(U, CD), 混合型属性子集A⊆AT确定的混合邻域关系为MNAδ.决策属性D诱导出的划分为U/D={D1, D2, ..., Dm}, 其中∀DiU/D称为混合型信息系统的决策类.那么决策类Di关于混合邻域关系MNAδβ下近似和β上近似分别定义为

(9)
(10)

决策属性D关于混合邻域关系MNAδ的正区域、边界域和负区域分别为

(11)
(12)
(13)
2 混合信息系统变精度粗糙集模型的动态更新

上节根据已有的研究成果提出了混合信息系统的变精度粗糙集模型, 然而现实中的信息系统是不断动态更新的[15], 因此需要对传统的模型和算法进行增量式学习的构造[15-22].本节, 在混合信息系统变精度粗糙集模型的基础上, 进一步探究该模型的增量式更新问题.

论域中对象的增加和减少是信息系统中一种常见的动态变化类型[16-17], 本文主要研究混合信息系统中对象增加和减少时变精度粗糙集模型的增量更新.一般情况下, 信息系统中对象的增加和减少都是多个的, 本文采用其他学者常用的处理方法[24], 通过逐个分析增加和减少对象进行增量式学习, 对于多个对象可以按照一个对象的更新方法进行迭代, 这样即可以便利地完成整个增量更新过程.

2.1 对象增加时模型的增量式更新

本节主要研究混合信息系统对象增加时变精度粗糙集模型的增量式更新.混合邻域类与决策类之间条件概率的计算是变精度粗糙集模型的基础, 首先探究对象增加时条件概率的增量式更新.

定理1  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 论域UD下的划分为U/D={D1, D2, ..., Dm}.当论域U增加一个对象x'后, 新信息系统表示为MIS' =(U'=U∪{x'}, CD), 论域U'在D下的划分为U'/D={D1', D2', ..., Dm'}, 这里∀Dij'∈ U'/D, Di' = Di, 且Dj'=Dj ∪ {x'}.对象xU在论域U下的混合邻域类记为δAU(x), 对象xU'在论域U'下的混合邻域类记为δAU'(x), 则有:

1) ∀xδAU'(x')-{x'}, 有

(14)
(15)

2) ∀xU'-δAU'(x'), 有

(16)
(17)

证明  1)根据定义2, ∀xδAU'(x')-{x'}满足δAU'(x)=δAU(x)∪ {x'}, 由于Di'=Di, ij, 有

P(Di'|δAU'(x)) < P(Di|δAU(x)), ij.由于Dj'=Dj∪{x'}, 有

g=|DjδAU(x)|, h=|δAU(x)|, 有

则有

由于0 < gh, ≥0, 有

2) 对于∀xU'-δAU'(x'), 根据定义2可得δAU'(x)=δAU(x).由于Di'=Di, ij, 且Dj'=Dj∪ {x'}, 有

定理1给出当混合信息系统论域增加一个对象后, 原先论域中对象条件概率的变化情况, 根据这种变化关系, 可以构造出混合型信息系统更新后变精度粗糙集模型的增量式更新.

定理2  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 决策类划分U/D={D1, D2, ..., Dm}, 决策类Di(1≤ im)在混合属性集Aβ变精度粗糙集下近似为MNAβ(Di).增加对象x'后决策类划分更新为U'/D={D1', D2', ..., Dm'}, 这里∀Dij'∈ U'/D, Di'=Di, 且Dj'=Dj∪{x'}.那么决策类Di'(1≤ im)的β变精度粗糙集下近似MNAβ(Di')可通过如下3个步骤更新完成:

1) 对于Di'(1≤ im, ij), 有

(18)

2) 对于Dj', 有

(19)

3) 若∃P(Di'|δAU'(x'))≥β, 1≤ im, 则有

(20)

证明  1)对于∀xU-MNAβ(Di), i=j, 满足P(Di|δAU(x)) < β, 当信息系统增加对象x'后, 由定理1, 若xδAU'(x') - {x'}, 则条件概率满足P(Di'|δAU'(x)) < P(Di|δAU(x)); 若xU'-δAU'(x'), 则条件概率满足P(Di'|δAU'(x))=P(Di|δAU(x)).因此对于∀xU-MNAβ(Di)均有xMNAβ(Di').

对于∀xMNAβ(Di), ij中的对象均满足P(Di|δAU(x))≥ β.当信息系统增加对象x'后, 根据定理1, 若xδAU'(x')-{x'}, 满足P(Di'|δAU'(x)) < P(Di|δAU(x)), 则此时P(Di'|δAU'(x))与β之间的大小关系无法确定, 当P(Di'|δAU'(x)) < β时, xMNAβ(Di').若xU' - δAU'(x'), 则由定理1可以得到P(Di'|δAU'(x))=P(Di|δAU(x)), 满足xMNAβ(Di').

2) 对于∀xMNAβ(Dj), 当信息系统增加对象x'后, 若xδAU'(x') - {x'}, 根据定理1可得P(Dj'|δAU'(x)) ≥ P(Dj|δAU(x))≥β, 则有xMNAβ(Dj'); 若xU'- δAU'(x'), 则P(Dj'|δAU'(x))= P(Dj|δAU(x))≥β, 同样有xMNAβ(Dj').因此, 对于∀xMNAβ(Dj)均有xMNAβ(Dj').

对于∀xU-MNAβ(Dj), 当信息系统增加对象x'后, 若xU'-δAU'(x'), 由定理1可得P(Dj'|δAU'(x))= P(Dj|δAU(x)) < β, 则有xMNAβ(Dj').若xδAU'(x') -{x' }, 由定理1可得P(Dj'|δAU'(x))≥ P(Dj|δAU(x)), 则由于P(Dj|δAU(x)) < β, P(Dj'|δAU'(x))与β的大小关系无法确定, 当P(Dj'|δAU'(x)) ≥ βxMNAβ(Dj').综上, 当xδAU'(x')-MNAβ(Dj), 条件概率满足P(Dj'|δAU'(x))≥β时, xMNAβ(Dj').

3) 最后分析新添加的对象x', 根据混合信息系统变精度粗糙集下近似的定义, 显然成立.

定理3  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 决策类划分U/D={D1, D2, ..., Dm}, 决策类Di(1≤ im)在混合属性集Aβ变精度粗糙集上近似为MNAβ(Di).增加对象x'后, 决策类划分更新为U'/D={D1', D2', ..., Dm' }, 这里∀D'ijU'/D, Di'=Di, 且Dj'=Dj∪{x'}.那么决策类Di'(1≤ im)的β变精度粗糙集上近似MNAβ(Di')可通过如下3个步骤更新完成:

1) 对于Di'(1≤ im, ij), 有

(21)

2) 对于Dj', 有

(22)

3) 若∃P(Di'|δAU'(x'))>1-β, 1≤ im, 则有

(23)

证明过程类似定理2, 此略.

定理2和定理3分别给出了混合信息系统增加一个对象后, 每个决策类下近似和上近似的增量更新方法.对于更新后的信息系统, 定理2和定理3表明, 只需要对δAU'(x')中的部分对象进行计算便可完成更新.这主要是由于当混合信息系统增加对象x'后, U'-δAU'(x')中的所有对象与每个决策类的条件概率是不发生任何变化的, 而δAU'(x')中的对象虽然发生了条件概率的改变, 但并不是所有的改变都影响到上下近似的变化, 因此真正对模型上下近似的影响只是δAU'(x')中一部分对象, 从而在增量式更新时只对这一部分进行重新计算, 避免了论域中其他对象的重复计算, 这种增量更新方法极大地提高了动态环境下的处理效率.

当混合信息系统增加多个对象, 即增加对象集ΔU={x1', x2', ..., x's }后, 可以将ΔU中的每个对象依次添加入混合信息系统, 每添加一个对象便按照定理2和定理3的方法进行更新, 通过这种迭代的方式完成整个对象集ΔU的增量式更新.

2.2 对象减少时模型的增量式更新

第2.1节给出了混合信息系统对象增加时变精度粗糙集模型的增量更新, 本节将给出对象减少时模型的更新, 其研究思路类似于第2.1节的方法, 即首先分析对象减少后条件概率的变化, 然后根据条件概率分析模型上下近似的增量更新.

定理4  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 论域UD下的划分为U/D={D1, D2, ..., Dm}.当论域U减少一个对象x'后, 新信息系统表示为MIS'=(U'=U-{x'}, CD), 同时决策类划分更新为U'/D={D1', D2', ..., Dm'}, 这里∀D'ijU'/D, Di'=Di, 且Dj'=Dj-{x'}.对象x在论域U下的混合邻域类记为δAU(x), 在论域U'下的混合邻域类记为δAU'(x), 则有:

1) ∀xδAU(x')-{x'}, 有

(24)
(25)

2) ∀xU-δAU(x'), 有

(26)
(27)

证明  1)根据定义2, ∀xδAU(x')-{x'}满足δAU'=δAU(x)-{x'}, 由于Di'=Di, ij, 有

P(Di'|δAU'(x))>P(Di|δAU(x)), ij.由于Dj'=Dj-{x'}, 有

g=|DjδAU(x)|, h=|δAU(x)|, 有

则有

由于0 < ghh>1, ≤0, 有P(Dj'|δAU'(x))≤ P(Dj|δAU(x)).

2) 证明过程类似定理1.

定理4给出当混合信息系统论域减少一个对象后, 原先论域U中对象条件概率的变化情况, 类似第2.1节的研究过程, 下面可以诱导出混合型信息系统对象减少时变精度粗糙集模型的增量更新.

定理5  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 决策类划分为U/D={D1, D2, ..., Dm}, 决策类Di(1≤ im)在混合属性集Aβ变精度粗糙集下近似为MNAβ(Di).减少对象x'后决策类划分更新为U'/D={D1', D2', ..., Dm'}, 这里∀D'ijU'/D, Di'=Di, 且Dj'=Dj-{x'}.那么决策类Di'(1≤ im)的β变精度粗糙集下近似MNAβ(Di')可通过如下2个步骤更新完成:

1) 对于Di'(1≤ im, ij), 有

(28)

2) 对于Dj', 有

(29)

证明  1)对于∀xU-MNAβ(Di), ij, 满足P(Di|δAU(x)) < β, 当论域减少对象x'后, 若xδAU(x')-{x'}, 由定理4满足P(Di'|δAU'(x))>P(Di|δAU(x)), 则有P(Di'|δAU'(x))与β的大小关系无法确定, 当P(Di'|δAU'(x)) ≥ β时, xMNAβ(Di'); 若xU - δAU(x'), 由定理4有P(Di'|δAU'(x)) < β, 则xMNAβ(Di').

对于∀xMNAβ(Di), ij中的对象满足P(Di|δAU(x))≥β, 当信息系统减少对象x'后, 若xδAU(x') - {x'}, 由定理4有

则有xMNAβ(Di').因此对于∀xMNAβ(Di)均有MNAβ(Di').

2) 对于∀xU-MNAβ(Dj), 当信息系统减少对象x'后, 若xU - δAU(x'), 由定理4可得P(Dj'|δAU'(x))= P(Dj|δAU(x)) < β, 则有xMNAβ(Dj'); 若xδAU(x')-{x'}, 由定理4可得

则也满足xMNAβ(Dj').因此∀xMNAβ(Dj)均有xMNAβ(Dj').

对于∀xMNAβ(Dj), 当信息系统减少对象x'后, 若xδAU(x')-{x'}, 由定理4可得

则当P(Dj'|δAU'(x)) < βxMNAβ(Dj'); 若xU-δAU(x'), 由定理4可得

则有xMNAβ(Dj').

定理6  设混合型决策信息系统MIS=(U, CD), 混合属性集AC, 决策类划分为U/D ={D1, D2, ..., Dm}, 决策类Di(1≤ im)在混合属性集Aβ变精度粗糙集上近似为MNAβ(Di).减少对象x'后决策类划分更新为U'/D={D1', D2', ..., Dm'}, 这里∀D'ijU'/D, Di'=Di, 且Dj'=Dj-{x'}.那么决策类Di'(1≤ im)的β变精度粗糙集上近似MNAβ(Di')可通过如下2个步骤更新完成:

1) 对于Di'(1≤ im, ij), 有

(30)

2) 对于Dj', 有

(31)

证明过程类似定理5, 此略.

类似第2.1节, 定理5和定理6给出的更新方法同样只需对δAU(x')中的部分对象进行计算分析, 便可以快速得到更新结果, 因此避免了对论域中其他对象进行重复计算.

同样地, 当混合信息系统减少多个对象, 即减少对象集ΔU={x1', x2', ..., x't}后, 同样可以将ΔU中的每个对象依次从混合信息系统中移除, 每移除一个对象便按照定理5和定理6的方法进行更新, 通过这种迭代方式也可以完成整个对象集ΔU的增量式更新.

3 混合信息系统变精度粗糙集模型的动态更新算法

本节将提出混合型信息系统下动态变精度粗糙集模型的非增量式更新算法和增量式更新算法.

3.1 非增量式更新算法

为了验证增量式更新算法的有效性, 首先给出混合型信息系统下变精度粗糙集模型的非增量式更新算法, 如算法1和算法2所示.

算法1  混合信息系统对象增加时变精度粗糙集模型的非增量更新算法.

输入: 1)混合型决策信息系统MIS=(U, CD), 属性集AC; 2)增加的对象集ΔU, 新的混合决策信息系统为MIS'=(U', CD), 其中U'=UΔU.

输出:新信息系统中每个决策类Di'(1≤ im)关于属性集Aβ变精度粗糙集下近似MNAβ(Di')和上近似MNAβ(Di').

Step 1:计算新信息系统的决策类划分U'/D={D1', D2', ..., Dm'}, 初始化MNAβ(Di') = ∅, MNAβ(Di') =∅.

Step 2:对于论域U', 计算对象∀xU'的混合邻域类δAU'(x), 若P(Di'|δAU'(x))≥β, 则xMNAβ(Di'), 若P(Di'|δAU'(x))>1-β, 则xMNAβ(Di'), 其中Di'∈ U'/D.

Step 3:返回MNAβ(Di')和MNAβ(Di'), 1≤ im.

算法2  混合信息系统对象减小时变精度粗糙集模型的非增量更新算法.

输入: 1)混合型决策信息系统MIS=(U, CD), 属性集AC; 2)减少的对象集ΔU, 新的混合决策信息系统为MIS'=(U', CD), 其中U'=U- ΔU.

输出:新信息系统中每个决策类Di'(1≤ im)关于属性集Aβ变精度粗糙集下近似MNAβ(Di')和上近似MNAβ(Di').

Step 1:计算新信息系统的决策类划分U'/D={D1', D2', ..., Dm'}, 初始化MNAβ(Di')=∅, MNAβ(Di') =∅.

Step 2:对于论域U', 计算对象∀xU'的混合邻域类δAU'(x), 若P(Di'|δAU'(x))≥ β, 则xMNAβ(Di'), 若P(Di'|δAU'(x))>1-β, 则xMNAβ(Di'), 其中Di'∈ U'/D.

Step 3:返回MNAβ(Di')和MNAβ(Di'), 1≤ im.

算法1和算法2的整体结构一致, 当混合型决策信息系统对象发生增加或减少时, 变精度粗糙集模型上下近似的非增量式更新算法即按照模型的原始定义进行计算, 因此存在大量的重复计算, 效率较低.算法1和算法2的时间复杂度主要集中在Step 2, 即关于论域中每个对象混合邻域类的计算.在算法1中, 每个混合邻域类的计算时间复杂度为O(|A||UΔU|), 因此算法1的时间复杂度为O(|A| |UΔU|2), 类似地, 算法2时间复杂度为O(|A||U-ΔU|2).

3.2 增量式更新算法

根据本文第2节提出的混合信息系统变精度粗糙集模型的更新方法, 下面给出相应的增量式更新算法, 如算法3和算法4所示.

算法3  混合信息系统对象增加时变精度粗糙集模型的增量式更新算法.

输入: 1)混合型决策信息系统MIS=(U, CD), 属性集AC; 2)每个决策类Di(1≤ im)关于属性集Aβ变精度下近似和上近似分别为MNAβ(Di)和MNAβ(Di); 3)增加的对象集ΔU={x1', x2', ..., x's}, 新的混合决策信息系统MIS'=(U', CD), 其中U'=UΔU.

输出:新信息系统中每个决策类Di'(1≤ im)关于属性集Aβ变精度粗糙集下近似MNAβ(Di')和上近似MNAβ(Di').

Step 1:对于对象xj'∈ΔU, 1≤ js, 将xj'添加入信息系统MIS(j-1)后, 更新的信息系统为MIS(j) =(U(j), CD), 记U=U(0), MIS=MIS(0)并且U(j)=U(j-1)∪{xj'}.

Step 2:更新信息系统MIS(j)中论域U(j)的决策类划分U(j)/D={D1(j), D2(j), ..., Dm(j)}.

Step 3:计算对象xj'的混合邻域类δ^UA(j)(xj'), 根据定理2和定理3增量式更新决策类Di(j)β变精度粗糙集下近似MNAβ(Di(j))和上近似MNAβ(Di(j)).

Step 4:对ΔU中每个对象按照Step 1 ~ Step 3进行迭代计算.

Step 5:返回更新后的β变精度粗糙集下近似MNAβ(Di')=MNAβ(Di(s)), 上近似MNAβ(Di')=MNAβ(Di(s)), 1≤ im.

算法4  混合信息系统对象减小时变精度粗糙集模型的增量式更新算法.

输入: 1)混合型决策信息系统MIS=(U, CD), 属性集AC; 2)每个决策类Di(1≤ im)关于属性集Aβ变精度下近似和上近似分别为MNAβ(Di)和MNAβ(Di); 3)减少的对象集ΔU={x1', x2', ..., x't}, 新的混合决策信息系统MIS'=(U', CD), 其中U'=U-ΔU.

输出:新信息系统中每个决策类Di'(1≤ im)关于属性集Aβ变精度粗糙集下近似MNAβ(Di')和上近似MNAβ(Di').

Step 1:对于对象xj'∈ΔU, 1≤ jt, 将xj'从信息系统MIS(j-1)中移除, 更新后的信息系统为MIS(j) =(U(j), CD), 记U=U(0), MIS=MIS(0), 且U(j) =U(j-1)-{xj'}.

Step 2:更新信息系统MIS(j)中论域U(j)的决策类划分U(j)/D={D1(j), D2(j), ..., Dm(j)}.

Step 3:计算对象xj'的混合邻域类δ^UA(j)(xj'), 根据定理5和定理6增量式更新决策类Di(j)(1≤ im)的β变精度粗糙集下近似MNAβ(Di(j))和上近似MNAβ(Di(j)).

Step 4:对ΔU中每个对象按照Step 1 ~ Step 3进行迭代计算.

Step 5:返回更新后的β变精度粗糙集下近似MNAβ(Di')=MNAβ(Di(t)), 上近似MNAβ(Di')=MNAβ(Di(t)), 1≤ im.

同样地, 算法3和算法4的整体结构也是类似的.其中Step 1 ~ Step 3选择ΔU中的对象按照第2节的增量更新方法对上下近似进行更新, 然后将ΔU中剩余的对象重新按照Step 1 ~ Step 3进行迭代, 当ΔU中的对象迭代结束, 整个模型也更新结束.算法3和算法4与算法1和算法2相比, 本质的区别在于算法3和算法4是在更新前模型结果的基础上进行更新, 这种更新是增量式的, 算法1和算法2是对更新后的信息系统进行重新计算, 因此算法3和算法4的处理效率会更高.

对于算法3, Step 1 ~ Step 3是针对一个对象加入信息系统后模型的增量更新, 该更新过程可能会存在少部分对象需要计算混合邻域类, 对于对象xj', 设这部分对象的数量为kj, 有kj < δA^U(j)(xj'), 那么第j次迭代时Step 1 ~ Step 3的时间复杂度为O(|A|(|U|+j)+kj|A|(|U|+j)), 即O((kj+1)|A|(|U|+j)).令需要计算邻域类的对象总数为K, ΔU中所有对象迭代完成后的时间复杂度为

因此算法3的时间复杂度可以表示为

由第3.1节, 算法1的时间复杂度可整理为

由于|ΔU|K < |U|, 对应比较两个表达式中的每一项, 都可以看出算法3的计算量要小于算法1.同理, 算法4的时间复杂度为

同样也可以证明算法4的计算量小于算法2.

4 实验分析

本节通过一系列实验以验证所提出混合信息系统动态变精度粗糙集模型的有效性.实验使用的UCI数据集如表 1所示, 其属性集均包含离散型属性和数值型属性.实验硬件平台为Intel(R) Core(TM) i5-4 570, 3.2 GHz和8 G内存, 所有算法采用JDK1.8进行编程并运行在Eclipse 4.7上.

表 1 实验数据集

实验环节主要分为3个部分: 1)将非增量式更新算法1与增量式更新算法3分别对对象不断增加的混合信息系统进行动态更新, 比较其更新效率; 2)将非增量式更新算法2与增量式更新算法4分别对对象不断减少的混合信息系统进行动态更新, 比较其更新效率; 3)关于模型中阈值参数与增量式更新算法进行更新效率的探究.

由于表 1中的数据集均为静态的, 实验按照一般增量式学习的研究方法, 将数据集分割成多个子数据集, 然后通过数据集的合并与分解来模拟数据集的动态变化.将表 1中的数据集平均分成10份, 每份看成一个子信息系统, 任意选择一个子信息系统作为初始信息系统, 从剩余的子信息系统中任意选择一个添加入初始信息系统, 模拟出一次动态增加过程, 然后按照该模式依次进行添加, 直到达到最终完整的信息系统.对于信息系统论域逐渐减少的过程, 首先从完整的信息系统开始, 每次移除一个子信息系统, 直到剩余最后一个子信息系统.

本文所提出的混合型信息系统变精度粗糙集模型中, 邻域半径δ是一个输入参数, 文献[7]通过大量实验确定邻域半径δ=0.2是一个较好的选择, 所以本文所有实验均选择邻域半径δ=0.2.另外, 在构建模型的混合邻域关系中, 距离函数选用欧氏距离.

4.1 对象增加时的更新效率比较

图 1为混合信息系统对象动态增加时, 算法1和算法3的变精度粗糙集上下近似更新效率比较结果, β =0.7. 图 1中每幅子图代表了对应数据集的实验结果, 由于10份子信息系统中选择一份作为初始信息系统, 因此实验结果中展示出9次动态更新的结果.

图 1 各数据集对象动态增加时模型更新效率比较

图 1可见, 算法3的上下近似更新效率要高于算法1.随着混合信息系统论域的逐渐动态增加, 非增量式算法的更新用时逐渐增大且增长速率是逐渐加快的, 这主要是由于算法1的时间复杂度与论域大小的平方成正比, 因此随着论域的增大, 算法所消耗的时间会越来越多.而对于算法3, 其增量式更新的时间消耗要比非增量式算法少很多, 随着更新次数增多, 增量式更新算法的时间消耗也是逐渐增长的, 但是增长速率明显比非增量式更新算法低很多.在有些数据集中, 例如Abalone、Thyroid和Chess, 当更新接近结束时, 增量式更新算法的时间消耗结果已经远小于非增量式更新算法的时间消耗结果.实验结果表明, 对于混合信息系统变精度粗糙集模型的动态更新, 算法3具有更高的更新效率.

4.2 对象减小时的更新效率比较

图 2为混合信息系统对象动态减少时, 算法2和算法4的变精度粗糙集上下近似更新效率比较结果, 精度同样设置为β =0.7.

图 2 各数据集对象动态减小时模型更新效率比较

图 2可见, 算法4的上下近似更新效率要高于算法2.在图 2的每个数据集实验结果中, 数据集第1次动态减少时, 增量式更新算法的时间消耗大幅度低于非增量式更新算法的时间消耗, 随着论域逐渐动态减少, 非增量式算法的更新用时也逐渐减小, 并且用时的减少速率是逐渐变慢的, 这与算法2的时间复杂度相吻合, 即时间复杂度与论域大小的平方成正比.对于算法4, 增量式更新的时间消耗比非增量式算法要少很多, 随着更新次数增多, 增量式更新算法的时间消耗也是逐渐减少的, 并且减小得较为平缓.对于信息系统论域的减小, 算法4的时间消耗总体上大幅度低于算法2.实验结果表明, 对于混合信息系统变精度粗糙集模型的动态更新, 增量式更新算法4同样具有较高的更新效率.

4.3 不同精度下增量式更新效率比较

变精度粗糙集模型通过对传统的粗糙集模型设定精度β的方式克服噪声数据, β的取值不同决定了抗噪能力的大小, 因此在本节将探究精度β对算法3和算法4更新效率的影响. 图 3 ~ 图 6分别为部分数据集在不同精度β下的增量式更新效率结果.

图 3 Heart实验结果
图 4 Credit实验结果
图 5 German实验结果
图 6 Thyroid实验结果

图 3 ~ 图 6可见, 两类算法在不同精度β下的时间消耗结果相差不大, 基本上可以认为精度β的大小对增量式更新效率没有较大的影响.这主要是由于精度β决定了模型的抗噪声能力, 而与变精度粗糙集模型中的条件概率没有任何关系, 所以不会影响到增量式更新算法的效率, 因此可以看出本文所提出的增量式更新算法具有较好的稳固性.

综合以上实验结果可以看出, 本文所提出的混合型信息系统变精度粗糙集模型的增量更新算法具有较高的更新效率, 保证了混合型数据下变精度粗糙集模型动态处理的时效性, 适用于更广泛的数据处理问题.

5 结论

混合型数据是一种常见的数据形式, 而动态性是现实中数据的一个重要特征.本文首先提出了混合信息系统下的变精度粗糙集模型; 然后针对混合信息系统对象的动态增加和动态减少, 给出了变精度粗糙集模型上下近似的快速增量更新, 并提出了模型的增量更新算法.实验结果表明, 所提出的增量式更新算法具有更高的动态更新效率.由于现实环境下数据动态变化的普遍性, 这一研究成果将进一步扩大变精度粗糙集模型的应用范围, 例如基于动态混合数据的知识挖掘、动态混合数据的变精度粗糙集属性约简等.接下来可以进一步研究混合信息系统属性增加和减少时模型的动态更新以及属性值变化时模型的更新问题.

参考文献
[1]
[2]
续欣莹, 张扩, 谢珺, 等. 基于互信息下粒子群优化的属性约简算法[J]. 电子学报, 2017(11): 2695-2704.
(Xu X Y, Zhang K, Xie J, et al. An attribute reduction algorithm based on mutual information of particle swarm optimization[J]. Acta Electronica Sinica, 2017(11): 2695-2704. DOI:10.3969/j.issn.0372-2112.2017.11.017)
[3]
Luo C, Li T R, Chen H M, et al. Incremental rough set approach for hierarchical multicriteria classification[J]. Information Sciences, 2018, 429: 72-87. DOI:10.1016/j.ins.2017.11.004
[4]
Lang G M, Miao D Q, Cai M J. Three-way decision approaches to conflict analysis using decision-theoretic rough set theory[J]. Information Sciences, 2017, 406-407: 185-207. DOI:10.1016/j.ins.2017.04.030
[5]
陈泽华, 宋波, 闫继雄, 等. 基于概念格的不完备信息系统最简规则提取算法[J]. 控制与决策, 2019, 34(5): 1011-1017.
(Chen Z H, Song B, Yan J X, et al. Concise rule extraction algorithm of incomplete information system based on concept lattice[J]. Control and Decision, 2019, 34(5): 1011-1017.)
[6]
王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[J]. 计算机学报, 2009, 32(7): 1229-1246.
(Wang G Y, Yao Y Y, Yu H. A survey on rough set theory and applications[J]. Chinese J of Computers, 2009, 32(7): 1229-1246.)
[7]
Hu Q H, Yu D R, Liu J F, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information Sciences, 2008, 178(18): 3577-3594. DOI:10.1016/j.ins.2008.05.024
[8]
Zhao H, Qin K Y. Mixed feature selection in incomplete decision table[J]. Knowledge-Based Systems, 2014, 57(2): 181-190.
[9]
何松华, 康婵娟, 鲁敏, 等. 基于邻域组合测度的属性约简方法[J]. 控制与决策, 2016, 31(7): 1225-1230.
(He S H, Kang C J, Lu M, et al. Attribute reduction method based on neighborhood combination measure[J]. Control and Decision, 2016, 31(7): 1225-1230.)
[10]
Lin G P, Qian Y H, Li J J. NMGRS: Neighborhood-based multigranulation rough sets[J]. Int J of Approximate Reasoning, 2012, 53(7): 1080-1093. DOI:10.1016/j.ijar.2012.05.004
[11]
Fan X D, Zhao W D, Wang C Z, et al. Attribute reduction based on max-decision neighborhood rough set model[J]. Knowledge-Based Systems, 2018, 151(1): 16-23.
[12]
Ziarko W. Variable precision rough set model[J]. J of Computer & System Sciences, 1993, 46(1): 39-59.
[13]
Kang Y, Wu S X, Li Y W, et al. A variable precision grey-based multi-granulation rough set model and attribute reduction[J]. Knowledge-Based Systems, 2018, 148: 131-145. DOI:10.1016/j.knosys.2018.02.033
[14]
Feng T, Mi J S. Variable precision multigranulation decision-theoretic fuzzy rough sets[J]. Knowledge-Based Systems, 2016, 91: 93-101. DOI:10.1016/j.knosys.2015.10.007
[15]
Wang F, Liang J Y, Qian Y H. Attribute reduction: A dimension incremental strategy[J]. Knowledge-Based Systems, 2013, 39(2): 95-108.
[16]
Liang J Y, Wang F, Dang C Y, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE Trans on Knowledge & Data Engineering, 2014, 26(2): 294-308.
[17]
Chen H M, Li T R, Luo C, et al. A decision-theoretic rough set approach for dynamic data mining[J]. IEEE Trans on Fuzzy Systems, 2015, 23(6): 1958-1970. DOI:10.1109/TFUZZ.2014.2387877
[18]
Liu D, Li T R, Zhang J B. Incremental updating approximations in probabilistic rough sets under the variation of attributes[J]. Knowledge-Based Systems, 2015, 73(81): 81-96.
[19]
Liu D, Li T R, Zhang J B. A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems[J]. Int J of Approximate Reasoning, 2014, 55(8): 1764-1786. DOI:10.1016/j.ijar.2014.05.009
[20]
Li S Y, Li T R. Incremental update of approximations in dominance-based rough sets approach under the variation of attribute values[J]. Information Sciences, 2015, 294: 348-361. DOI:10.1016/j.ins.2014.09.056
[21]
Li S Y, Li T R, Liu D. Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set[J]. Knowledge-Based Systems, 2013, 40(1): 17-26.
[22]
Jing Y G, Li T R, Fujita H, et al. An incremental attribute reduction approach based on knowledge granularity with a multi-granulation view[J]. Information Sciences, 2017, 411: 23-38. DOI:10.1016/j.ins.2017.05.003
[23]
曾安平.混合动态信息系统中的高效知识更新算法研究[D].成都: 西南交通大学信息科学与技术学院, 2015.
(Zeng A P. Research on efficient knowledge updating algorithm in hybrid dynamic information system[D]. Chengdu: School of Information Science and Technology, Southwest Jiaotong University, 2015.) http://cdmd.cnki.com.cn/Article/CDMD-10613-1016166542.htm
[24]
Xu J F, Miao D Q, Zhang Y J, et al. A three-way decisions model with probabilistic rough sets for stream computing[J]. Int J of Approximate Reasoning, 2017, 88: 1-22. DOI:10.1016/j.ijar.2017.05.001