﻿ 基于知识粒度的增量约简算法
 «上一篇 下一篇»
 山东大学学报(工学版)  2016, Vol. 46 Issue (1): 1-9  DOI: 10.6040/j.issn.1672-3961.2.2015.033 0

### 引用本文

JING Yunge, LI Tianrui. An incremental approach for reduction based on knowledge granularity[J]. Journal of Shandong University(Engineering Science), 2016, 46(1): 1-9. DOI: 10.6040/j.issn.1672-3961.2.2015.033.

### 文章历史

1. 西南交通大学信息科学与技术学院, 四川 成都 611756;
2.运城学院公共计算机教学部, 山西 运城 044000

An incremental approach for reduction based on knowledge granularity
JING Yunge1, 2, LI Tianrui1
1.School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, Sichuan, China;
2.Department of Public Computer Teaching, Yuncheng University, Yuncheng 044000, Shanxi, China
Abstract: The object set in a decision table varied dynamically nowadays. It cost a lot of time for non-incremental algorithms solving reduction of dynamical data set. Incremental technique supplied an efficient and effective soluation to such dynamic data. An incremental mechanism for updating knowledge granularity was introduced and then an incremental approach for attribute reduction based on knowledge granularity was developed. With the existing knowledge granularity and reduction, the new reduction could be obtained by the proposed method when multiple objects were added to the decision table. Theoretical analysis validated that incremental approach could reduce complexity of time for computing attribute reduction. Experiments conducted on different data sets from UCI showed that the proposed incremental algorithm could achieve better performance than the non-incremental approach.
Key words: knowledge granularity    attribute reduction    incremental method    rough set theory    decision table
0 引言

1 粗糙集的相关知识

2 知识粒度约简算法 2.1 知识粒度基本知识

GD(D|C)=GD(C)-GD(CD)=$\frac{8}{9}$log 2-$\frac{6}{9}$log 2=$\frac{2}{9}$log 2。

2.2 经典知识粒度约简算法

Step 1: 计算条件属性C相对于决策属性D的核Core,令RedU←Core;

Step 2: If(GD(D|RedU)=GD(D|C))then

go to Step 5;

else

go to Step 3;

End if

Step 3: P←RedU,while(GD(D|RedU)≠GD(D|C)) do

｛对每个aiC-P,计算属性重要度2,即SigUouter(ai,P,D),选择SigUouter(ai,P,D)最大的属性ai作为扩展属性,

RedU←RedU∪｛ai｝｝;

Step 4: For(a∈RedU)

If(GD(D|P)=GD(D|C))then

RedUP-｛a｝;

End if

End

Step 5: 输出属性约简RedU,算法结束。

3 知识粒度增量约简算法

3.1 知识粒度增量机制

 $U \cup {U^+}/B - \left\{ {\left\{ {{x_5},{x_3}} \right\},\left\{ {{x_1},{x_2}} \right\},\left\{ {{x_3},{x_4}} \right\},\left\{ {{x_6},{x_7}} \right\},\left\{ {{y_1},{y_2}} \right\}} \right\}.$

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left(C \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}} } \right.+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } \right). \end{array}$

X′i=XiYi(i=1,2,…,k),则:

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| {{X_i}} \right|+\left| {{Y_i}} \right|} \right)\sum\limits_{i=1}^k {\log \left({\left| {{X_i}} \right|+\left| {{Y_i}} \right|} \right)+\left| {{X_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|+\left| {{Y_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } } \right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \left| {{X_i}} \right|+\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \left| {{Y_i}} \right|} } }+} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}+\left| {{X_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|+\left| {{Y_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } } \right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|\left({\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=1}^k {\log \left| {{X_i}} \right|+\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|} } } \right)} \right.+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{U^+}} \right|\left({\frac{{\left| {{Y_i}} \right|}}{{\left| {{U^+}} \right|}}\sum\limits_{i=1}^k {\log \left| {{Y_i}} \right|+\frac{{\left| {{Y_i}} \right|}}{{\left| {{U^+}} \right|}}\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}+\left| {{Y_i}} \right|+\sum\limits_{i=1}^K {\log \left| {{Y_i}} \right|} } \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} \right) \end{array}$

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left(C \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}}+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\;\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}} } \right). \end{array}$

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left({C \cup D} \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({C \cup D} \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)+\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}}+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\;\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } \right). \end{array}$

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left({D \cup C} \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({D \cup C} \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({D \cup C} \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}}+\\ \;\left.{\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - \left({\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} } \right) \end{array}$

 $\begin{array}{l} G{D_{U \cup {U^+}}}\left({D\left| C \right.} \right)=G{D_{U \cup {U^+}}}\left(C \right)- G{D_{U \cup {U^+}}}\left({C \cup D} \right)=\\ \;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| U \right|G{D_U}\left(C \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({C \cup D} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)+} \right.\\ \;\;\;\;\;\;\;\;\left.{\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)=\\ \;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| U \right|G{D_U}\left(C \right)- \left| U \right|G{D_U}\left({C \cup D} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)- } \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)} \right)+\\ \;\;\;\;\;\;\;\;\;\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|} \sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - } \\ \;\;\;\;\;\;\;\;\;\left.{\left({\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} \right)=\\ \;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({D\left| C \right.} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left({D\left| C \right.} \right)+} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|} \sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - } \\ \;\;\;\;\;\;\;\;\;\;\;\left.{\left({\left| {{M_i}} \right|} \right)\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right). \end{array}$

 $\begin{array}{l} {\rm{S}}ig_{U \cup {U^+}}^{{\rm{inner}}}\left({a,C,D} \right)=\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|} \right.{\rm{Sig}}_U^{{\rm{inner}}}\left({a,C,D} \right)+\left| {{U^+}} \right|{\rm{Sig}}_U^{{\rm{inner}}}\left({a,C,D} \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{E_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{E_i}} \right|+\left| {{F_i}} \right|}}{{\left| {{E_i}} \right|}}+\left| {{F_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{E_i}} \right|+\left| {{F_i}} \right|}}{{\left| {{F_i}} \right|}}} } - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{Z_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Z_i}} \right|+\left| {{L_i}} \right|}}{{\left| {{Z_i}} \right|}}+\left| {{L_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Z_i}} \right|+\left| {{L_i}} \right|}}{{\left| {{L_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left.{\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{M_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} \right). \end{array}$

 $\begin{array}{l} {\rm{S}}ig_{U \cup {U^+}}^{{\rm{outer}}}\left({a,{C_0},D} \right)=\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|} \right.{\rm{Sig}}_U^{{\rm{outer}}}\left({a,{C_0},D} \right)+\left| {{U^+}} \right|{\rm{Sig}}_U^{{\rm{outer}}}\left({a,{C_0},D} \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{Q_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Q_i}} \right|+\left| {{O_i}} \right|}}{{\left| {{Q_i}} \right|}}+\left| {{O_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Q_i}} \right|+\left| {{O_i}} \right|}}{{\left| {{O_i}} \right|}}} } - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{G_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{G_i}} \right|+\left| {{T_i}} \right|}}{{\left| {{G_i}} \right|}}+\left| {{T_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{G_i}} \right|+\left| {{T_i}} \right|}}{{\left| {{T_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{H_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{H_i}} \right|+\left| {{W_i}} \right|}}{{\left| {{H_i}} \right|}}+\left| {{W_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{H_i}} \right|+\left| {{W_i}} \right|}}{{\left| {{W_i}} \right|}}} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left.{\left| {{P_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{P_i}} \right|+\left| {{I_i}} \right|}}{{\left| {{P_i}} \right|}}+\left| {{I_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{P_i}} \right|+\left| {{I_i}} \right|}}{{\left| {{I_i}} \right|}}} } } \right)} \right). \end{array}$
3.2 知识粒度增量约简算法

Step 1: P←RedU,计算U／P=｛X1B,X2B,…,XjB｝,U+P=｛M1B,M2B,…,XjB｝,U／C=X1C,X2C,…,XmC｝,U+C=｛Y1C,Y2C,…,YmC｝;

Step 2: 计算UU+P=｛X1B,X2B,…,X′kB,Xk+1B,Xk+2B,…,XjB,Mk+1B,Mk+2B,…,Mj′B｝和UU+C=｛X1C,X2C,…,XKC,XK+1C,,XK+2C,…,XmC,,YK+1C,YK+2C,…,YCm′｝;

Step 3: 计算GDU+(D|P)和GDU+(D|C),if(GDU+(D|P)=GDU+(D|C)),then

go to Step 6;

else

go to Step 4;

Step 4: While(GDUU+(D|P)≠GDUU+(D|C))do

｛对每个aiC-P,按照定理5计算属性重要度2,即SigUU+outer(ai,P,D),选择SigUU+outer(ai,P,D)最大的属性ai作为扩展属性,

RedU←RedU∪｛ai｝｝;

Step 5: For(aP)

If(GDUU+(D|P-｛a｝)=GDUU+(D|C)then

PP-{a};

End if

End

Step 6: RedUU+P,输出增加对象后的约简RedUU+,算法结束。

4 算例

(1)P←RedU,根据Step 2可得,UU+／P=｛｛1,10｝,｛2,4,11,12,8,9｝,｛3,5｝,｛6,7｝｝,UU+C=｛｛1｝,｛2,4,11｝,｛3,5｝,｛6,7｝,｛8,9｝,｛10｝,｛12｝｝;

(2)根据Step 3可得,GDUU+(D|P)≠GDUU+(D|C),所以需要从C-P中选取属性增加到P=｛a,f｝中直到他们相等为止;

(3)根据Step 4我们增加属性｛b,e｝到P=｛a,f｝中,可到GDUU+(D|P)=GDUU+(D|C),然后执行Step 5;

(4)最后得到增加后的属性约简为RedUU+=｛a,f,b,e｝。

5 仿真分析 5.1 数据集和仿真环境

5.2 运行时间

6 结束语

 [1] SUN Lin, XU Jiucheng, TIAN Yun. Feature selection using rough entropy-based uncertainty measures in incomplete decision systems[J].Knowledge-Based Systems, 2013(36):206-216.(1) [2] YAO Yiyu, ZHONG Ning. Potential applications of granular computing in knowledge discovery and data mining[C]// Proceedings of the World Multi-conference on Systemics, Cybernetics and Informatics.[S.l.]: Betascript Publishing, 1999:573-580.(1) [3] ROMAN W, SWINIARSKI, ANDRZEJ Skowron A. Rough set methods in feature selection and recognition[J].Pattern Recognition Letters, 2003, 24(6):833-849.(1) [4] ANANTHANARAYANA V S, NARASIMHA Murty M, SUBRAMANIAN D K. Tree structure for efficient data mining using rough sets[J].Pattern Recognition Letter, 2003, 24(6):851-862.(1) [5] SHUSAKU Tsumoto. Automated extraction of medical expert system rules from clinical databases based on RST[J]. Information Sciences,1998,112(1-4):67-84.(1) [6] 王磊,叶军. 知识粒度计算的矩阵方法及其在属性约简中的应用[J].计算机工程与科学, 2013,35(3):98-102.WANG Lei, YE Jun. Matrix-based approach for calculating knowledge granulation and its application in attribute reduction[J]. Computer Engineering ＆ Science, 2013, 35(3):98-102.(1) [7] 翟俊海,高原原,王熙照,等. 基于划分子集的属性约简算法[J].山东大学学报(工学版),2011,41(4):25-28.ZHAI Junhai, GAO Yuanyuan, WANG Xizhao,et al. An attribute reduction algorithm based on a partition subset[J]. Journal of Shandong University(Engineering Science), 2011, 41(4):25-28.(1) [8] 邱桃荣,刘清,黄厚宽. 多值信息系统中基于粒计算的多级概念获取算法[J].模式识别与人工智能,2009,22(1):22-27.QIU Taorong, LIU Qing, HUANG Houkuan. Granular computing based hierarchical concept capture algorithm in multi-valued information system[J].Pattern Recognition and Artificial Intelligence, 2009, 22(1):22-27.(1) [9] 钟珞,梅磊,郭翠翠,等. 粒矩阵属性约简启发式算法[J].小型微型计算机系统,2011,2(3):516-520.ZHONG Lu, MEI Lei, GUO Cuicui,et al. Heuristic algorithm for attribute reduction on granular matrix[J]. Journal of Chinese Computer Systems, 2011, 2(3):516-520.(1) [10] ZENG Anping, LI Tianrui, LIU Dun, et al. A fuzzy rough set approach for incremental feature selection on hybrid information systems[J]. Fuzzy Sets and Systems, 2014(258):39-60.(1) [11] LIANG Jiye, WANG Feng, DANG Chuangyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2):1-31.(2) [12] QIAN Yuhua, LIANG Jiye, PEDRYCZB W. et al. Positive approximation: An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9-10):597-618.(1) [13] 刘洋,冯博琴,周江卫. 基于差别矩阵的增量式属性约简完备算法[J].西安交通大学学报,2007,41(2):158-161.LIU Yang, FENG Boqin, ZHOU Jiangwei. Complete algorithm of increment for attribute reduction based on discernibility matrix[J]. Journal of Xi′an Jiaotong University, 2007, 41(2):158-161.(1) [14] CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A rough set-based method for updating decision rules on attribute values coarsening and refining[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(12):2886-2899.(1) [15] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822.YANG Ming. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese Journal of Computer, 2007, 30(5):815-822.(1) [16] SHU Wenhao, SHEN Hong. Updating attribute reduction in incomplete decision systems with the variation of attribute set[J].International Journal of Approximate Reasoning, 2014, 55(3):867-884.(1) [17] LI Shaoyong, LI Tianrui, HU Jie. Update of approximations in composite information systems[J]. Knowledge-Based Systems, 2015(83):138-148.(1) [18] 刘清.Rough set及Rough推理[M].北京:科学出版社,2001:7-16.(3) [19] YAO Yiyu. Probabilistic approaches to rough sets[J]. Expert Systems, 2003, 20(5):287-297.(2) [20] 苗夺谦,范世栋.知识粒度的计算及其应用[J].系统工程理论与实践,2002,22(1):48-56.MIAO Duoqian, FAN Shidong. The calculation of knowledge granulation and its application[J]. Systems Engineer-Theory & Practice, 2002, 22(1):48-56.(6) [21] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度max(O(|C||U|,O(|C|2|U／C|))的快速约简算法[J].计算机学报,2006,29(3):391-398.XU Zhangyan, LIU Zuopeng, YANG Bingru, et al. A quickly attribute reduction algorithm with complexity of max(O(|C||U|,O(|C|2|U／C|))[J]. Chines Journal of Computer, 2006, 29(3):391-398.(1)