﻿ 混合信息系统的动态变精度粗糙集模型
 控制与决策  2020, Vol. 35 Issue (2): 297-308 0

### 引用本文 [复制中英文]

[复制中文]
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.
[复制英文]

### 文章历史

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 混合信息系统的变精度粗糙集模型

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

 (1)

 (2)

 (3)
 (4)

1.2 变精度粗糙集模型

 (5)
 (6)

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

 (7)
 (8)

 (9)
 (10)

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

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

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

 (14)
 (15)

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

 (16)
 (17)

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

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

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

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

 (18)

2) 对于Dj', 有

 (19)

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

 (20)

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').

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

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

 (21)

2) 对于Dj', 有

 (22)

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

 (23)

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

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

 (24)
 (25)

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

 (26)
 (27)

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

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

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

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

 (28)

2) 对于Dj', 有

 (29)

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

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

 (30)

2) 对于Dj', 有

 (31)

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

3.1 非增量式更新算法

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.

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.

3.2 增量式更新算法

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.

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.

4 实验分析

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

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

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

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

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

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

5 结论

 [1] Pawlak Z. Rough sets[J]. Int J of Parallel Programming, 1982, 11(5): 341-356. [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