第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0L:10.11992tis.202006045 不完备数据中面向特征值更新的增量特征选择方法 唐荣，罗川，曹潜，王思朝 (四川大学计算机学院，四川成都610065) 摘要：实际应用中，数据常常表现出不完备性和动态性的特点。针对动态不完备数据中的特征选择问题，提 出了一种基于相容粗糙集模型和信息嫡理论的增量式特征选择方法。首先，建立了不完备信息系统中特征值 动态更新时论域上条件划分与决策分类的动态更新模式，分析了作为特征重要度评价准则的不完备相容信息 嫡的增量计算机制，并将该机制引入到启发式最优特征子集搜索过程中特征重要度的迭代计算，进一步设计了 不完备数据中面向特征值动态更新的增量式特征选择算法。最后，在标准UCI数据集上从分类精度、决策性 能和计算效率3个方面对文中所提出的增量算法的有效性和高效性进行了实验验证。 关键词：特征选择；维度约简；粗糙集；信息嫡；不完备数据；缺失值；启发式搜索：增量学习 中图分类号：TP18文献标志码：A 文章编号：1673-4785(2021)03-0493-09 中文引用格式：唐荣，罗川，曹潜，等.不完备数据中面向特征值更新的增量特征选择方法J儿.智能系统学报，2021,16(3)： 493-501. 英文引用格式：TANG Rong,.LUO Chuan,.CAO Qian,etal.Incremental approach for feature selection in incomplete data while updating feature values J.CAAI transactions on intelligent systems,2021,16(3):493-501. Incremental approach for feature selection in incomplete data while updating feature values TANG Rong,LUO Chuan,CAO Qian,WANG Sizhao (College of Computer Science,Sichuan University,Chengdu 610065,China) Abstract:In practical application,data often exhibits incomplete and dynamic characteristics.For the feature selection problem in dynamic incomplete data,an incremental feature selection method based on the tolerance rough set model and information entropy theory is proposed.First,the update patterns of conditional partition and decision classification are established based on the variation of feature values in incomplete information systems.The incremental computing mechanism of incomplete tolerance information entropy as the evaluation criterion of feature importance is built sub- sequently.Such an incremental mechanism is integrated into the iterative calculation of feature importance during the heuristic search of optimal feature subset,and an incremental feature selection algorithm for dynamic variation of fea- ture values is developed.Finally,the effectiveness and efficiency of the proposed incremental algorithm are verified on several standard UCI datasets in terms of classification accuracy,decision performance,and computing efficiency. Keywords:feature selection;dimensional reduction;rough set;information entropy;incomplete data;missing values, heuristic search:incremental learning 特征选择的目标是在给定评价标准下选择非冗 性，在数据挖掘与知识发现中起着重要的作用山。 余的特征子集，其作为一项重要的数据预处理步骤， 数据中存在一些缺失值是一种非常普遍的现 能够有效地提高数据分析模型的准确性和高效 象，缺失值给数据中的分类知识带来了不一致性 问题。粗糙集理论是一种能够有效应对不精确、 收稿日期：2020-06-27. 不一致信息的数据建模与知识获取工具。近年来， 基金项目：国家自然科学基金项目(62076171)：四川省科技厅 应用基础研究计划项目(2019YJ0084). 人们基于粗糙集理论针对不完备数据的特征选择 通信作者：罗川.E-mall:cluo@scu.edu.cn 间题进行了深人的分析和讨论。Kryszkiewicz)
DOI: 10.11992/tis.202006045 不完备数据中面向特征值更新的增量特征选择方法 唐荣，罗川，曹潜，王思朝 （四川大学 计算机学院，四川 成都 610065） 摘 要：实际应用中，数据常常表现出不完备性和动态性的特点。针对动态不完备数据中的特征选择问题，提 出了一种基于相容粗糙集模型和信息熵理论的增量式特征选择方法。首先，建立了不完备信息系统中特征值 动态更新时论域上条件划分与决策分类的动态更新模式，分析了作为特征重要度评价准则的不完备相容信息 熵的增量计算机制，并将该机制引入到启发式最优特征子集搜索过程中特征重要度的迭代计算，进一步设计了 不完备数据中面向特征值动态更新的增量式特征选择算法。最后，在标准 UCI 数据集上从分类精度、决策性 能和计算效率 3 个方面对文中所提出的增量算法的有效性和高效性进行了实验验证。 关键词：特征选择；维度约简；粗糙集；信息熵；不完备数据；缺失值；启发式搜索；增量学习 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2021)03−0493−09 中文引用格式：唐荣, 罗川, 曹潜, 等. 不完备数据中面向特征值更新的增量特征选择方法 [J]. 智能系统学报, 2021, 16(3): 493–501. 英文引用格式：TANG Rong, LUO Chuan, CAO Qian, et al. Incremental approach for feature selection in incomplete data while updating feature values[J]. CAAI transactions on intelligent systems, 2021, 16(3): 493–501. Incremental approach for feature selection in incomplete data while updating feature values TANG Rong，LUO Chuan，CAO Qian，WANG Sizhao (College of Computer Science, Sichuan University, Chengdu 610065, China) Abstract: In practical application, data often exhibits incomplete and dynamic characteristics. For the feature selection problem in dynamic incomplete data, an incremental feature selection method based on the tolerance rough set model and information entropy theory is proposed. First, the update patterns of conditional partition and decision classification are established based on the variation of feature values in incomplete information systems. The incremental computing mechanism of incomplete tolerance information entropy as the evaluation criterion of feature importance is built subsequently. Such an incremental mechanism is integrated into the iterative calculation of feature importance during the heuristic search of optimal feature subset, and an incremental feature selection algorithm for dynamic variation of feature values is developed. Finally, the effectiveness and efficiency of the proposed incremental algorithm are verified on several standard UCI datasets in terms of classification accuracy, decision performance, and computing efficiency. Keywords: feature selection; dimensional reduction; rough set; information entropy; incomplete data; missing values; heuristic search; incremental learning 特征选择的目标是在给定评价标准下选择非冗 余的特征子集，其作为一项重要的数据预处理步骤， 能够有效地提高数据分析模型的准确性和高效 性，在数据挖掘与知识发现中起着重要的作用[1]。 数据中存在一些缺失值是一种非常普遍的现 象，缺失值给数据中的分类知识带来了不一致性 问题[2]。粗糙集理论是一种能够有效应对不精确、 不一致信息的数据建模与知识获取工具。近年来， 人们基于粗糙集理论针对不完备数据的特征选择 问题进行了深入的分析和讨论。Kryszkiewicz[3] 收稿日期：2020−06−27. 基金项目：国家自然科学基金项目 (62076171)；四川省科技厅 应用基础研究计划项目 (2019YJ0084) . 通信作者：罗川. E-mall：cluo@scu.edu.cn. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021
·494· 智能系统学报 第16卷 认为不完备数据中缺失值应是已有值域中的某一 制，可用于多个数据集之间信息嫡的高效融合。 特征值，进而提出了一种基于广义差别矩阵的特 Shu等21针对含有缺失值的不完备数据，提出了 征选择方法。Parthalin等为了保留分类所产生的不 基于正域的增量特征选择算法。Xie等提出了 致决策区域，研究了基于容差粗糙集的特征选择 3种不完备数据中相容类的更新策略，并设计了 方法。Meng等讨论了不一致不完备决策系统中 相应的增量特征选择算法。考虑到动态数据中特 基于区分矩阵的特征选择方法。Grzymala-Busse 征值存在频繁的修改和更新操作，Wang等2)针 等6将缺失值考虑为丢失值和不在乎值，提出了 对完备数据集研究了特征值动态更新时信息嫡的 基于广义特征关系粗糙集模型的特征选择方法。 增量更新机制，进一步设计了相应的动态特征选 Qian等m提出了一种高效的正向近似加速器，用 择算法。刘吉超等2针对不完备数据中数据集 于加速不完备数据特征选择的启发式特征搜索过 维数动态增加的情形，分析了互补信息熵的更新 程。Dai阁为了处理不完备数值型数据，建立了一 机制，进而提出了一种增量特征约简算法。钱进 种新的容差模糊粗糙集模型，并提出了基于差别 等2刀提出一种基于正域处理面向成组对象集的 矩阵的特征选择方法。Yang等定义了多准则 增量式特征选择算法。综合上文所述，大部分研 决策系统中相似优势关系的概念，提出了4种基 究者针对完备决策系统的动态更新特征选择问题 于差别矩阵的近似分布约简方法。Liang等o提 进行深入的研究，鲜有对不完备决策系统动态更 出了一种不完备信息系统中基于粗糙熵的启发式 新特征问题研究。基于正域处理不完备决策系统 特征选择算法。Qian等四基于不完备信息系统中 的特征选择存在无法处理边界域中的样本分类的 的最大一致块概念，提出了一种新的组合信息熵 不确定性问题。信息嫡作为度量信息不确定性的 用于度量信息系统的不可分辨能力。Dai等a在 度量标准，有助于不完备数据特征选择问题研 不完备决策系统中提出一种新的满足单调性约束 究，而引入增量计算机制可以加速特征选择过 的条件信息嫡。Zhao等11提出了一种新的邻域 程，有效减少计算时间。本文针对不完备决策系 容差条件嫡，并将其应用于混合不完备数据中的 统，设计了一种面向特征值动态更新的特征选择 特征选择问题。 算法。文中首先分析了特征值更新时不完备决策 另一方面，实际应用中数据随时间的推移呈 系统中相容类和决策类的动态变化模式，并以此 现出动态更新的变化趋势，数据的采集与分析是 给出了条件信息熵的增量计算机制，进而设计了 一个不断优化升级的动态过程。面向动态数据的 基于增量条件信息熵的动态特征算法，最后通过 高效特征选择方法成为了当前人们普遍关注的一 实验验证进一步说明了算法的有效性和高效性。 个研究热点。增量技术可以利用已有计算结果进 行特征选择增量计算，以发现新的特征子集，从 1基本概念 而避免重新计算整个特征空间以获取新的特征子 粗糙集理论中，信息系统表示为一个四元组 集41。近年来，许多学者通过将增量学习技术 S=(U,A,V,f),其中，U表示对象的非空有限集合， 引入到特征选择问题中，对动态数据环境下的高 称为论域；A表示特征的非空有限集合，即特征 效特征选择方法进行了广泛深入的研究。Xu等6 集；Va表示特征aEA的值域，并且有V=UaeA Va; 将特征选择问题转化为0-1整数规划问题，提出 对任意a∈A和x∈U,f:U×A→V是一个信息函 了一种对象更新条件下的动态特征选择方法。Qian 数，通过信息函数给每一个对象x∈U一个特定 等刀设计了一种新的基于相对不可辨识对象对 的特征值f(x,a)∈Va,a∈A。决策系统表示为 的属性重要度度量方式，并提出了动态粒度空间 DS=(UCU{d,VfD,其中，C代表条件特征的非空 下的基于序贯三支决策模型的增量特征选择方 有限集合；d表示决策特征。在实际应用中，信息 法。Yang等uI分析了对象动态变化时相对可辨 系统中某些对象的特征值容易丢失，如果一个信 识关系的增量更新机制，提出了基于模糊粗糙集 息系统中V包含缺失的特征值，记作“*”，那么该 的动态特征选择算法。Lang等1)提出了覆盖信 信息系统被称为不完备信息系统(incomplete in- 息系统中基于相关族的动态特征选择方法。Wei formation system,IIS);对于决策系统来说，如果 等20设计了基于辨识矩阵和压缩辨识矩阵的增 *∈Vc,*V,称这样的决策系统为不完备决策系 量特征选择算法，以获得数据动态变化时最优的 统(incomplete decision system,IDS);对于 特征子集。Zeng等2u基于高斯核模糊粗糙集模 *生Vc,*使V这样的决策系统，称为完备决策系统。 型，研究了混合信息系统的动态特征选择方法。 完备信息系统中条件特征的任何子集P≤C Liang等2)提出了信息熵的批增量递推计算机 可诱导一种不可辨识关系NDP),定义为
认为不完备数据中缺失值应是已有值域中的某一 特征值，进而提出了一种基于广义差别矩阵的特 征选择方法。Parthalin 等 [4] 为了保留分类所产生的不 一致决策区域，研究了基于容差粗糙集的特征选择 方法。Meng 等 [5] 讨论了不一致不完备决策系统中 基于区分矩阵的特征选择方法。Grzymala-Busse 等 [6] 将缺失值考虑为丢失值和不在乎值，提出了 基于广义特征关系粗糙集模型的特征选择方法。 Qian 等 [7] 提出了一种高效的正向近似加速器，用 于加速不完备数据特征选择的启发式特征搜索过 程。Dai[8] 为了处理不完备数值型数据，建立了一 种新的容差模糊粗糙集模型，并提出了基于差别 矩阵的特征选择方法。Yang 等 [9] 定义了多准则 决策系统中相似优势关系的概念，提出了 4 种基 于差别矩阵的近似分布约简方法。Liang 等 [10] 提 出了一种不完备信息系统中基于粗糙熵的启发式 特征选择算法。Qian 等 [11] 基于不完备信息系统中 的最大一致块概念，提出了一种新的组合信息熵 用于度量信息系统的不可分辨能力。Dai 等 [12] 在 不完备决策系统中提出一种新的满足单调性约束 的条件信息熵。Zhao 等 [13] 提出了一种新的邻域 容差条件熵，并将其应用于混合不完备数据中的 特征选择问题。 另一方面，实际应用中数据随时间的推移呈 现出动态更新的变化趋势，数据的采集与分析是 一个不断优化升级的动态过程。面向动态数据的 高效特征选择方法成为了当前人们普遍关注的一 个研究热点。增量技术可以利用已有计算结果进 行特征选择增量计算，以发现新的特征子集，从 而避免重新计算整个特征空间以获取新的特征子 集 [14-15]。近年来，许多学者通过将增量学习技术 引入到特征选择问题中，对动态数据环境下的高 效特征选择方法进行了广泛深入的研究。Xu 等 [16] 将特征选择问题转化为 0-1 整数规划问题，提出 了一种对象更新条件下的动态特征选择方法。Qian 等 [17] 设计了一种新的基于相对不可辨识对象对 的属性重要度度量方式，并提出了动态粒度空间 下的基于序贯三支决策模型的增量特征选择方 法。Yang 等 [18] 分析了对象动态变化时相对可辨 识关系的增量更新机制，提出了基于模糊粗糙集 的动态特征选择算法。Lang 等 [19] 提出了覆盖信 息系统中基于相关族的动态特征选择方法。Wei 等 [20] 设计了基于辨识矩阵和压缩辨识矩阵的增 量特征选择算法，以获得数据动态变化时最优的 特征子集。Zeng 等 [21] 基于高斯核模糊粗糙集模 型，研究了混合信息系统的动态特征选择方法。 Liang 等 [22] 提出了信息熵的批增量递推计算机 制，可用于多个数据集之间信息熵的高效融合。 Shu 等 [23] 针对含有缺失值的不完备数据，提出了 基于正域的增量特征选择算法。Xie 等 [24] 提出了 3 种不完备数据中相容类的更新策略，并设计了 相应的增量特征选择算法。考虑到动态数据中特 征值存在频繁的修改和更新操作，Wang 等 [25] 针 对完备数据集研究了特征值动态更新时信息熵的 增量更新机制，进一步设计了相应的动态特征选 择算法。刘吉超等[26] 针对不完备数据中数据集 维数动态增加的情形，分析了互补信息熵的更新 机制，进而提出了一种增量特征约简算法。钱进 等 [27] 提出一种基于正域处理面向成组对象集的 增量式特征选择算法。综合上文所述，大部分研 究者针对完备决策系统的动态更新特征选择问题 进行深入的研究，鲜有对不完备决策系统动态更 新特征问题研究。基于正域处理不完备决策系统 的特征选择存在无法处理边界域中的样本分类的 不确定性问题。信息熵作为度量信息不确定性的 度量标准，有助于不完备数据特征选择问题研 究，而引入增量计算机制可以加速特征选择过 程，有效减少计算时间。本文针对不完备决策系 统，设计了一种面向特征值动态更新的特征选择 算法。文中首先分析了特征值更新时不完备决策 系统中相容类和决策类的动态变化模式，并以此 给出了条件信息熵的增量计算机制，进而设计了 基于增量条件信息熵的动态特征算法，最后通过 实验验证进一步说明了算法的有效性和高效性。 1 基本概念 S = (U,A,V, f) U A Va a ∈ A V = ∪a∈AVa a ∈ A x ∈ U f : U × A → V x ∈ U f(x,a) ∈ Va a ∈ A DS = (U,C ∪ {d},V, f) C d V ∗ ∈ VC,∗ < Vd ∗ < VC,∗ < Vd 粗糙集理论中，信息系统表示为一个四元组 ，其中， 表示对象的非空有限集合， 称为论域； 表示特征的非空有限集合，即特征 集； 表示特征 的值域，并且有 ； 对任意 和 ， 是一个信息函 数，通过信息函数给每一个对象 一个特定 的特征值 ， 。决策系统表示为 ，其中， 代表条件特征的非空 有限集合； 表示决策特征。在实际应用中，信息 系统中某些对象的特征值容易丢失，如果一个信 息系统中 包含缺失的特征值，记作“*”，那么该 信息系统被称为不完备信息系统 (incomplete information system，IIS)；对于决策系统来说，如果 ，称这样的决策系统为不完备决策系 统 (incomplete decision system， IDS)；对于 这样的决策系统，称为完备决策系统。 P ⊆ C IND(P) 完备信息系统中条件特征的任何子集 可诱导一种不可辨识关系 ，定义为 ·494· 智 能 系 统 学 报 第 16 卷
第3期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·495· NDP)={(x,y)eU×UIMa∈P,fx,a=fy,a)l 征值发生更新时相容类和决策类的变化情况。由 ND(P)是具有自反性、对称性与传递性的等 于条件嫡的计算与相容类和决策类中的对象顺序 价关系。等价关系ND(P)将论域U划分为等价 无关，为了方便阐述，下文中假设决策系统中 类的集合，表示为UND(P)={[xPx∈U,其中 发生特征值修改的对象集合为{xi=p+1,P+2,…,qh, [xp=byx,y)∈ND(P)I。为了处理含有缺失值的不 则更新后不完备决策系统中相容类的更新为 完备决策系统，Kryszkiewicz提出一种新的二元关 U/T'(P)={T'(xi=1,2,…,p,p+1…, 系T(P),PsC,定义为 9,9+1,…,k,k+1,…,m T(P)={(x,y)∈U×UNa∈Pfx,a=fy,aV 式中：x(=1,2,…,p)表示相容类保持不变的对象， f(x,a)=*vf(y.a)=* 即T()=T(x;x(i=p+1,p+2,…,q)表示特征值 T(P)是具有自反性和对称性，但不具有传递性 发生变化的对象，其相容类需根据定义计算，即 的相容关系。在P下任意一个对象x∈U的相容 T(x)={西∈UI(,)eT'(P)hx=q+1,q+2,…,k)和 类定义为T(x)=y∈UI(x,y)∈T(P)I。U/T(P)表示相 x(i=k+1,k+2,…,)分别表示相容类可能出现的 容类集合{T(Px∈U。U/T(P)中构成论域U上的 两种更新模式的对象集合。对于对象集合 一个覆盖，对于论域中任意一个对象x∈U,T(x)≠O, x(i=q+1,9+2,…,k),相容类更新为T(x)=(T(x)- 并且UxeUTp(x)=U。给定一个不完备决策系统 T(x)UT(x,对于对象集合xi=k+1,k+2,…,m, DS=(U,CU{d,V,fD,决策属性d将对象分类为m 相容类更新方式为T(x)=T(x)-T(x),其中， 个确定互斥的子集U/d={D,D2,…,Dm}。目标决 Tp(x)={xlx,xl∈T(P),p+1≤l≤q小；T(x)={lx,x}∈ 策概念D:∈U/D的上、下近似集定义为 T'(P),p+1≤I≤qlo apr(D)=(xEUIT(x)C D.) 不完备决策系统中决策特征值发生变化后决 apr(D)={x∈UITp(x)nD≠O] 策类的更新为 基于粗糙集理论的特征选择方法根据特征重 U/d={Dj=1,2,…,q,q1+1,…,92,q2+1,…,m 要度的不同度量标准，可笼统地归纳为依赖性度 式中：D=1,2,…,q)表示决策类保持不变的对 量、一致性度量、距离度量和信息度量。前面 象，即D=Dj;Dj=q1+1,q1+2,…,q2)表示需要 3种度量方法都局限于数据的实际值，对含有噪 从当前决策类中删除特征值更新的可辨识对象， 声或缺失值的数据处理十分敏感。而基于信息论 即D=D,-D;Dj=q2+1,2+2,…,m)表示不仅 的度量方法仅关注随机变量的概率分布，不关注 需要删除特征值发生更新的可辨识对象集合，同 其实际值，成为了高维数据中常用的特征重要度 时要增加新特征值下不可辨识的对象集合，即 度量方式。借鉴香农熵的传统定义形式，Dai等四 D=(D-D)UD,其中D={x归x,∈D,fx,d)= 定义了一种新的满足单调性的条件熵来度量不完 fx,d0,p+1≤I≤ql,D={xl旧x,∈D,f,d)=fxr,d0, 备决策系统协调程度的不确定性。给定一个不完 p+1≤l≤ql。 备决策系统DS=(U,CUd,Vf),其中，U={x,2,…, 根据上文中不完备决策系统中特征值动态修 xn};U/T(P)={Tp(ci=1,2,…,n;UId={D,D2,… 改后相容类和决策类的更新模式，下面进一步可 Dm}。决策特征d关于条件特征子集P的条件嫡 得相容类与决策类交集的动态更新方式。 定义为 Hd=-∑∑lnDl 对于任意对象xi=1,2,…,p)的相容类和决 (1) 策类Dj=1,2…,m),有T()nD=Tn()nDl 1 IT( 成立，对于任意对象x(i=p+1,p+2,…,9),由于其 根据式(1)，通过从特征子集P删除某个特 相容类需根据定义计算，无法利用已有结果，因 征a引起的条件熵的变化大小，可定义特征的重 此相容类和决策类Dj=1,2,…,m)的交集表示为 要度度量函数： T()nD。 sig(a,P.d)=H(dlp)-H(dlp-(a) 对于任意对象x(i=q+1,q+2,…,k)的相容类 2不完备数据集中特征值更新的增 和决策类DG=1,2,…,m),其交集的更新模式为 量特征选择 IT'(x)ODI= T(x)nDl,1≤j≤q1 当不完备决策系统中特征值发生动态更新时， ITr(x)OD-ITE(x)0D- IT()ODil+IT()ODil q1+1≤j≤q2 由特征子集所诱导的相容关系和由决策特征所诱 IT()0D-ITE(ODl- 导的等价关系会随之变化，进而使得特征度量准则 IT (x)OT(x+T()0Dil+ 条件熵发生变化。下面，首先分析一组对象的特 IT:(x)ODil ,92+1≤j≤m
IND(P) = {(x, y) ∈ U ×U|∀a ∈ P, f(x,a) = f(y,a)} IND(P) IND(P) U U/IND(P) = {[x]P|x ∈ U} [x]P = {y|(x, y) ∈ IND(P)} T(P),P ⊆ C 是具有自反性、对称性与传递性的等 价关系。等价关系 将论域 划分为等价 类的集合，表示为 ，其中 。为了处理含有缺失值的不 完备决策系统，Kryszkiewicz 提出一种新的二元关 系 ，定义为 T(P) = {(x, y) ∈ U ×U|∀a ∈ P, f(x,a) = f(y,a)∨ f(x,a) = ∗ ∨ f(y,a) = ∗} T(P) x ∈ U TP(x) = {y ∈ U|(x, y) ∈ T(P)} U/T(P) {T(P)|x ∈ U} U/T(P) U x ∈ U,TP(x) , Ø ∪x∈U TP(x) = U IDS = (U,C ∪ {d},V, f) d m U/d = {D1,D2,··· ,Dm} Di ∈ U/D 是具有自反性和对称性，但不具有传递性 的相容关系。在 P 下任意一个对象 的相容 类定义为 。 表示相 容类集合 。 中构成论域 上的 一个覆盖，对于论域中任意一个对象 ， 并且 。给定一个不完备决策系统 ，决策属性 将对象分类为 个确定互斥的子集 。目标决 策概念 的上、下近似集定义为 apr(Di) = {x ∈ U|TP(x) ⊆ Di} apr(Di) = {x ∈ U|TP(x)∩ Di , Ø} IDS = (U,C ∪ {d},V, f) U = {x1, x2,··· , xn} U/T(P) = {TP(xi)|i = 1,2,··· ,n} U/d = {D1,D2,··· , Dm} d P 基于粗糙集理论的特征选择方法根据特征重 要度的不同度量标准，可笼统地归纳为依赖性度 量、一致性度量、距离度量和信息度量。前面 3 种度量方法都局限于数据的实际值，对含有噪 声或缺失值的数据处理十分敏感。而基于信息论 的度量方法仅关注随机变量的概率分布，不关注 其实际值，成为了高维数据中常用的特征重要度 度量方式。借鉴香农熵的传统定义形式，Dai 等 [8,12] 定义了一种新的满足单调性的条件熵来度量不完 备决策系统协调程度的不确定性。给定一个不完 备决策系统 ，其中， ； ； 。决策特征 关于条件特征子集 的条件熵 定义为 H(d|P) = − ∑n i=1 ∑m j=1 |TP(xi)∩ Dj | |U| log2 |TP(xi)∩ Dj | |TP(xi)| (1) P a 根据式（1），通过从特征子集 删除某个特 征 引起的条件熵的变化大小，可定义特征的重 要度度量函数： sig(a,P,d) = H(d|P)− H(d|P− {a}) 2 不完备数据集中特征值更新的增 量特征选择 当不完备决策系统中特征值发生动态更新时， 由特征子集所诱导的相容关系和由决策特征所诱 导的等价关系会随之变化，进而使得特征度量准则 条件熵发生变化。下面，首先分析一组对象的特 {xi |i = p+1, p+2,··· ,q} 征值发生更新时相容类和决策类的变化情况。由 于条件熵的计算与相容类和决策类中的对象顺序 无关，为了方便阐述，下文中假设决策系统中 发生特征值修改的对象集合为 ， 则更新后不完备决策系统中相容类的更新为 U/T ′ (P) = {T ′ P(xi)|i = 1,2,··· , p, p+1,··· , q,q+1,··· , k, k+1,··· ,n} xi(i = 1,2,··· , p) T ′ P (xi) = TP(xi) xi(i = p+1, p+2,··· ,q) T ′ P (xi) = {xl ∈ U|(xi , xl) ∈ T ′ (P)} xi(i = q+1,q+2,··· ,k) xi(i = k+1, k+2,··· ,n) xi(i = q+1,q+2,··· , k) T ′ P (xi) =(TP(xi)− T − P (xi))∪T + P (xi) xi(i = k+1,k+2,··· ,n) T ′ P (xi) = TP(xi)−T − P (xi) T − P (xi)={xl |{xi , xl} ∈T(P), p+1⩽l⩽q} T + P (xi)={xl |{xi , xl} ∈ T ′ (P), p+1 ⩽ l ⩽ q} 式中： 表示相容类保持不变的对象， 即 ； 表示特征值 发生变化的对象，其相容类需根据定义计算，即 ； 和 分别表示相容类可能出现的 两种更新模式的对象集合。对于对象集合 ，相容类更新为 ，对于对象集合 ， 相容类更新方式为 ，其中， ； 。 不完备决策系统中决策特征值发生变化后决 策类的更新为 U/d = {D ′ j | j = 1,2,··· ,q1 ,q1 +1,··· ,q2 ,q2 +1,··· ,m} D ′ j (j = 1,2,··· ,q1) D ′ j = Dj D ′ j (j = q1 +1,q1 +2,··· ,q2) D ′ j = Dj − D − j D ′ j (j = q2 +1,q2 +2,··· ,m) D ′ j = (Dj−D − j )∪ D + j D − j = {xl |∃xr ∈ Dj , f(xl ,d) = f(xr ,d),p+1⩽l⩽q} D + j = {xl |∃xr ∈ Dj , f(xl ,d) = f(xr ,d), p+1 ⩽ l ⩽ q} 式中： 表示决策类保持不变的对 象，即 ； 表示需要 从当前决策类中删除特征值更新的可辨识对象， 即 ； 表示不仅 需要删除特征值发生更新的可辨识对象集合，同 时要增加新特征值下不可辨识的对象集合，即 ，其中 ， 。 根据上文中不完备决策系统中特征值动态修 改后相容类和决策类的更新模式，下面进一步可 得相容类与决策类交集的动态更新方式。 xi(i = 1,2,··· , p) D ′ j (j = 1,2,··· ,m) |T ′ P (xi)∩ D ′ j | = |TP(xi)∩ Dj | xi(i = p+1, p+2,··· ,q) D ′ j (j = 1,2,··· ,m) |T ′ P (xi)∩ D ′ j | 对于任意对象 的相容类和决 策 类 ， 有 成立，对于任意对象 ，由于其 相容类需根据定义计算，无法利用已有结果，因 此相容类和决策类 的交集表示为 。 xi(i = q+1,q+2,··· , k) D ′ j (j = 1,2,··· ,m) 对于任意对象 的相容类 和决策类 ，其交集的更新模式为 |T ′ P(xi)∩ D ′ | = |TP(xi)∩ Dj |, 1 ⩽ j ⩽ q1 |TP(xi)∩ Dj | − |T − P (xi)∩ Dj |− |TP(xi)∩ D − j |+|T − P (xi)∩ D − j |, q1 +1 ⩽ j ⩽ q2 |TP(xi)∩ Dj | − |T − P (xi)∩ Dj |− |TP(xi)∩T − P (xi)|+|T − P (xi)∩ D − j |+ |T + P (xi)∩ D + j | , q2 +1 ⩽ j ⩽ m 第 3 期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·495·
·496· 智能系统学报 第16卷 对于任意对象xi=k+1,k+2,…,m)的相容类 计算时间为OCIU川△UD,步骤6)中删除掉冗余 和决策类D,G=1,2,·,m),其交集的更新模式为 特征的时间复杂度为O(ACIU川△UD。因此，算法 IT)OD= IFS-CE-IDS总的时间复杂度为O(ICIUIAU+ IT-(x)nDl,1≤j≤q1 ICPIUI川I△UI+AIICIUI△U=O(CPIUI△UD。 IT()OD-IT()0Dl- IT(x)ODil+ITE(x)ODil. 91+1≤j≤m 3实验及分析 通过分析不完备决策系统中相容类和决策 类，以及其交集的动态更新模式，可得特征值发 本文选取了9组UCI数据集进行性能测试， 生修改时决策特征d关于任意条件特征子集P 数据集详细信息如表1所示。对于完备数据集 的条件熵的增量计算机制为 Car和kr-vs-kp,随机删除原始数据集中5%的已 Hu(dlP)=Hu(dlP)+ 知特征值变为缺失值，使原始完备数据集变为不 其中4的值如下所示： 完备数据集。对含有数值型数据的数据集Hepat- 4=-22rn IT'()OD itis、Wisconsin、Dermatology和Ozone,将数值型特 UI log2 IT' 征进行了离散化处理。如数据集Hepatitis包含 22 IT(xODl 19个特征，其中6个为数值型特征；数据集Wis 101 IT-(x consin含有1个数值型特征；数据集Dermato- (ITF(ODA+IT()ODI logy包含1个数值型特征；数据集Ozone都是数 IUI 值型特征。实验环境配置为：Intel(R)Core(TM)i5- ITF(x)ODl+IT(x)OD+IT()nDil 4210MCPU2.60GHz,8GB内存，操作系统为 IU八 Windows1O,程序开发平台为ntelliJ IDEA,编程 log IT'P(x)ODI 语言为Java。 IT'() 表1数据集描述 基于上述分析，算法1给出了不完备决策系 Table 1 Description of the datasets 统中特征值更新时基于条件熵的增量式特征选择 数据集 样本数 特征数 类别数 算法来计算新的特征子集。 Hepatitis 155 20 2 算法1不完备决策系统中基于条件熵的增 Audiology 226 69 24 量式特征选择算法(FS-CE-DS) Cancer 286 9 2 输入不完备决策系统DS=(U,CU{d,Vf), Soybean 307 35 19 原始数据U上的特征子集RED∈C,以及数据中 Dermatology 366 34 6 发生修改对象的集合△U; Wisconsin 699 2 1728 4 输出特征选择后的特征子集A。 Car 6 Ozone 2534 72 2 1)初始化特征子集A=RED; kr-vs-kp 3196 36 2 2)根据特征值更新对象集合△U更新后U/d= {D,D3,…,Dm,U/T'(C)=(T(x,T(2,…,T(xl, 为验证本文所提出算法IFS-CE-IDS处理数 U/T'(A)={TA(x),T(,…,TA(x》,计算Tp(c)、 据集特征值更新问题具有高效性和可行性，使用 T()、D、D: 传统批量式特征选择算法HFS-CE-IDS与算法 3)计算H(dC)和H(dA): FS-CE-IDS在9组UCI数据集上进行测试，从分 4)如果H(dC)≠H(dA)进入7)，否则进入5)： 类精度、决策性能以及计算效率三方面对传统批 5)当H(dC)≠H(dA)时，对任意a∈C-A,计算 量式特征选择算法HFS-CE-IDS和IFS-CE-IDS进 sig(a,AU{al,d),并且选择其中拥有最大sig(a,AU{a,d 行比较。 的a,A=AU{ah 3.1分类精度分析 6)对任意特征a∈A计算sig(a,A,d),如果 为比较算法HFS-CE-IDS与算法IFS-CE- sig(a,A.d)=0,A=A-la); DS所得特征子集的分类精度，对表1中9组数 7)返回A。 据集选择其中50%对象，并且更新其特征值，然 该算法中条件嫡的计算时间是O(CU川△U小， 后分别运行传统批量式算法HFS-CE-IDS和增量 在算法IFS-CE-DS中，步骤1)3)的计算时间是 式算法FS-CE-IDS对特征值更新数据集进行特 OCU川△U),步骤5)的向特征集A中添加特征的 征选择。使用决策树J48、Naive Bayes、SVM
xi(i = k+1, k+2,··· ,n) D ′ j (j = 1,2,··· ,m) 对于任意对象 的相容类 和决策类 ，其交集的更新模式为 |T ′ P(xi)∩ D ′ j | = |TP(xi)∩ Dj |, 1 ⩽ j ⩽ q1 |TP(xi)∩ Dj | − |T − P (xi)∩ Dj |− |TP(xi)∩ D − j |+|T − P (xi)∩ D − j |, q1 +1 ⩽ j ⩽ m d P 通过分析不完备决策系统中相容类和决策 类，以及其交集的动态更新模式，可得特征值发 生修改时决策特征 关于任意条件特征子集 的条件熵的增量计算机制为 H ′ U (d|P) = HU (d|P)+∆ 其中 ∆ 的值如下所示： ∆ = − ∑q i=p+1 ∑m j=1 |T ′ P(xi)∩ D ′ j | |U| log2 |T ′ P(xi)∩ D ′ j | |T ′ P(x ′ i)| + ∑n i=p+1 ∑m j=1 |TP(xi)∩ Dj | |U| log2 |TP(xi)∩ Dj | |TP(xi)| + ∑n i=q+1 ∑m j=q1+1 ( |T − P (xi)∩ Dj |+|TP(xi)∩ D − j | |U| − |T − P (xi)∩ D − j |+|TP(xi)∩ Dj |+|T + P (xi)∩ D + j | |U| ) · log2 |T ′ P(xi)∩ D ′ | |T ′ P(xi)| 基于上述分析，算法 1 给出了不完备决策系 统中特征值更新时基于条件熵的增量式特征选择 算法来计算新的特征子集。 算法 1 不完备决策系统中基于条件熵的增 量式特征选择算法 (IFS-CE-IDS) IDS = (U,C ∪ {d},V, f) U RED ∈ C ∆U 输入 不完备决策系统 ， 原始数据 上的特征子集 ，以及数据中 发生修改对象的集合 ； 输出 特征选择后的特征子集 A。 1) 初始化特征子集 A = RED ； ∆U U/d = {D ′ i ,D ′ 2 , ··· , D ′ m },U/T ′ (C) = {T ′ C (x1), T ′ C (x2), ··· , T ′ C (xn)} U/T ′ (A) = {T ′ A (x1),T ′ A (x2),··· ,T ′ A (xn)} T − P (xi) T + P (xi) D − j D + j 2) 根据特征值更新对象集合 更新后 ， ，计算 、 、 、 ； H ′ U (d|C) H ′ U 3) 计算 和 (d|A) ； H ′ U (d|C) , H ′ U 4) 如果 (d|A) 进入 7)，否则进入 5)； H ′ U (d|C) , H ′ U (d|A) a ∈ C − A sig(a,A∪ {a},d) sig(a,A∪ {a},d) a A = A∪ {a} 5) 当 时，对任意 ，计算 ，并且选择其中拥有最大 的 ， ； a ∈ A sig(a,A,d) sig(a,A,d) = 0 A = A− {a} 6 ) 对任意特征 计 算 , 如 果 ，则 ； 7) 返回 A。 O(|C||U||∆U|) O(|C||U||∆U|) 该算法中条件熵的计算时间是 ， 在算法 IFS-CE-IDS 中，步骤 1)~3) 的计算时间是 ，步骤 5) 的向特征集 A 中添加特征的 O(|C| 2 |U||∆U|) O(|A||C||U||∆U|) O(|C||U||∆U|+ |C| 2 |U||∆U|+|A||C||U||∆U|) = O(|C| 2 |U||∆U|) 计算时间为 ，步骤 6) 中删除掉冗余 特征的时间复杂度为 。因此，算法 IFS-CE-ID S 总的时间复杂度为 。 3 实验及分析 本文选取了 9 组 UCI 数据集进行性能测试， 数据集详细信息如表 1 所示。对于完备数据集 Car 和 kr-vs-kp，随机删除原始数据集中 5% 的已 知特征值变为缺失值，使原始完备数据集变为不 完备数据集。对含有数值型数据的数据集 Hepatitis、Wisconsin、Dermatology 和 Ozone，将数值型特 征进行了离散化处理。如数据集 Hepatitis 包含 19 个特征，其中 6 个为数值型特征；数据集 Wisconsin 含有 1 个数值型特征；数据集 Dermatology 包含 1 个数值型特征；数据集 Ozone 都是数 值型特征。实验环境配置为：Intel(R)Core(TM)i5- 4210M CPU 2.60 GHz，8 GB 内存，操作系统为 Windows 10，程序开发平台为 IntelliJ IDEA，编程 语言为 Java。 表 1 数据集描述 Table 1 Description of the datasets 数据集 样本数 特征数 类别数 Hepatitis 155 20 2 Audiology 226 69 24 Cancer 286 9 2 Soybean 307 35 19 Dermatology 366 34 6 Wisconsin 699 10 2 Car 1728 6 4 Ozone 2534 72 2 kr-vs-kp 3196 36 2 为验证本文所提出算法 IFS-CE-IDS 处理数 据集特征值更新问题具有高效性和可行性，使用 传统批量式特征选择算法 HFS-CE-IDS 与算法 IFS-CE-IDS 在 9 组 UCI 数据集上进行测试，从分 类精度、决策性能以及计算效率三方面对传统批 量式特征选择算法 HFS-CE-IDS 和 IFS-CE-IDS 进 行比较。 3.1 分类精度分析 为比较算法 HFS-CE-IDS 与算法 IFS-CEIDS 所得特征子集的分类精度，对表 1 中 9 组数 据集选择其中 50% 对象，并且更新其特征值，然 后分别运行传统批量式算法 HFS-CE-IDS 和增量 式算法 IFS-CE-IDS 对特征值更新数据集进行特 征选择。使用决策树 J48、Naïve Bayes、SVM ·496· 智 能 系 统 学 报 第 16 卷
第3期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·497· (support vector machines)分类器验证这两种算法 DS在9个数据集上的分类精度结果表明新提出 的分类性能。实验结果如表2~4所示。 算法在大部分数据集上的分类精度不比算法 表2J48分类精度比较 HFS-CE-IDS的分类精度差，例如在数据集Can- Table 2 J48 classification accuracy comparison cer、Car和kr-vs-kp上两种算法的分类精度基本 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 相同。 Hepatitis 70.32±0.4570 67.10±0.4818 从表4可知，在SVM分类器中，与算法HFS Audiology 30.53±0.2041 30.09±0.2058 CE-IDS相比，新提出算法的分类精度在Hepatit- Cancer 60.14±0.5114 60.14±0.5114 is、Audiology、Cancer、Soybean、Dermatology、Wis Soybean 44.66±0.1907 43.78±0.1931 consin、Car、Ozone、kr-vs-kp等7个数据集上相等 Dermatology 41.26±0.3753 41.53±0.3745 甚至更好。 Wisconsin 72.25±0.4441 72.39±0.4380 实验结果表明，算法IFS-CE-IDS在大部分数 Car 49.83±0.3667 49.83±0.3667 据集上能够在特征子集和分类精度上取得和算法 Ozone 73.28±0.4425 73.28±0.4425 HFS-CE-DS相接近的，甚至更好的结果，可以证 kr-vs-kp 70.06±0.4195 70.06±0.4195 明算法FS-CE-IDS是一种有效的特征选择算法。 3.2决策性能分析 表3 Naive Bayes分类精度比较 为检验算法FS-CE-DS的决策性能，本文使 Table 3 Naive Bayes classification accuracy comparison 用文献[28]中对不完备数据进行评估所提出的 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 6种评估函数评估算法HFS-CE-IDS以及算法 Hepatitis 63.87±0.4789 66.45±0.4722 Audiology FS-CE-DS计算的特征子集的决策性能。 28.76±0.1862 30.09±0.1858 6种评估函数中，特征集合C下不完备决策系 Cancer 65.73±0.4911 65.73±0.4911 Soybean 34.55±0.2048 32.21±0.2076 统DS=(U,CU{d,V,f)近似准确评估函数定义为 Dermatology 46.72±0.3368 44.54±0.3382 lapr (D) Wisconsin 73.82±0.4509 73.10±0.4436 ac(F)= Car 49.07±0.3687 49.07±0.3687 丁p(D,l D,evlD Ozone 69.81±0.4882 69.65±0.4869 kr-vs-kp 63.74±0.4715 63.74±0.4715 式中：apr,=U{EUIMCe E Dj.D,∈U/Dl,1≤i≤n, 是下近似值；aprc=U{x∈UIMCcnD,≠O,D,∈U/D, 表4SVM分类精度比较 1≤i≤n,是上近似值；F=U/D。其中，MCc表示 Table 4 SVM classification accuracy comparison % 在特征子集C下所得最大一致块集合。 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 不完备决策系统DS=(U,CU{d,Vf)特征集 Hepatitis 70.32±0.5448 70.32±0.5448 合C下的一致性度量评估函数的定义为 Audiology 23.01±0.2533 24.78±0.2504 Cancer 64.69±0.5943 64.69±0.5943 2D,p(D,》 Cc(D)= Soybean 43.19±0.2445 42.31±0.2464 I0I Dermatology 46.72±0.4214 47.54±0.4182 不完备决策系统DS=(U,CU{d,Vf)在 Wisconsin 73.53±0.5145 72.82±0.5214 RULE={ZlZ:des(X)→des(D,),X∈MCc,D,EMC Car 49.07±0.4513 49.07±0.4513 下的确定性度量α评估函数定义为 Ozone 73.24±0.5173 73.28±0.5169 11XOD kr-vs-kp 69.06±0.5563 69.06±0.5563 a(IDS)=- mN台X 见表2，从两种算法在J48分类器的分类精度 式中：N:是在不完备决策表中由最大一致块X所 比较可知，算法IFS-CE-IDS在数据集Hepatitis、 诱导得到的决策类数目；X∈U表示在PSC下， Audiology和Soybean上所得的分类精度相较算 (,)∈T(P),u,v∈X,且不存在一个子集Y∈U, 法HFS-CE-IDS所得分类精度差一些，而在其他 XcY,(u,)∈T(P,u,v∈Y,称X为最大一致块。 6个数据集上算法FS-CE-IDS所得分类精度与算 不完备决策系统DS=(U,CU{d,V,f)在RULE= 法HFS-CE-IDS所得分类精度相同甚至更好。从 {ZlZ:des(X)→des(D,X:eMCc,D,eMCa}下的一 表3可知，在Naive Bayes分类器中，算法FS-CE 致性度量B评估函数定义为
(support vector machines) 分类器验证这两种算法 的分类性能。实验结果如表 2~4 所示。 表 2 J48 分类精度比较 Table 2 J48 classification accuracy comparison % 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 Hepatitis 70.32±0.457 0 67.10±0.4818 Audiology 30.53±0.204 1 30.09±0.2058 Cancer 60.14±0.511 4 60.14±0.5114 Soybean 44.66±0.190 7 43.78±0.1931 Dermatology 41.26±0.375 3 41.53±0.3745 Wisconsin 72.25±0.444 1 72.39±0.4380 Car 49.83±0.366 7 49.83±0.3667 Ozone 73.28±0.442 5 73.28±0.4425 kr-vs-kp 70.06±0.419 5 70.06±0.4195 表 3 Naïve Bayes 分类精度比较 Table 3 Naïve Bayes classification accuracy comparison % 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 Hepatitis 63.87±0.478 9 66.45±0.4722 Audiology 28.76±0.186 2 30.09±0.1858 Cancer 65.73±0.491 1 65.73±0.4911 Soybean 34.55±0.204 8 32.21±0.2076 Dermatology 46.72±0.336 8 44.54±0.3382 Wisconsin 73.82±0.450 9 73.10±0.4436 Car 49.07±0.368 7 49.07±0.3687 Ozone 69.81±0.488 2 69.65±0.4869 kr-vs-kp 63.74±0.471 5 63.74±0.4715 表 4 SVM 分类精度比较 Table 4 SVM classification accuracy comparison % 数据集 HFS-CE-IDS算法 IFS-CE-IDS算法 Hepatitis 70.32±0.544 8 70.32±0.5448 Audiology 23.01±0.253 3 24.78±0.2504 Cancer 64.69±0.594 3 64.69±0.5943 Soybean 43.19±0.244 5 42.31±0.2464 Dermatology 46.72±0.421 4 47.54±0.4182 Wisconsin 73.53±0.514 5 72.82±0.5214 Car 49.07±0.451 3 49.07±0.4513 Ozone 73.24±0.517 3 73.28±0.5169 kr-vs-kp 69.06±0.556 3 69.06±0.5563 见表 2，从两种算法在 J48 分类器的分类精度 比较可知，算法 IFS-CE-IDS 在数据集 Hepatitis、 Audiology 和 Soybean 上所得的分类精度相较算 法 HFS-CE-IDS 所得分类精度差一些，而在其他 6 个数据集上算法 IFS-CE-IDS 所得分类精度与算 法 HFS-CE-IDS 所得分类精度相同甚至更好。从 表 3 可知，在 Naïve Bayes 分类器中，算法 IFS-CEIDS 在 9 个数据集上的分类精度结果表明新提出 算法在大部分数据集上的分类精度不比算法 HFS-CE-IDS 的分类精度差，例如在数据集 Cancer、Car 和 kr-vs-kp 上两种算法的分类精度基本 相同。 从表 4 可知，在 SVM 分类器中，与算法 HFSCE-IDS 相比，新提出算法的分类精度在 Hepatitis、Audiology、Cancer、Soybean、Dermatology、Wisconsin、Car、Ozone、kr-vs-kp 等 7 个数据集上相等 甚至更好。 实验结果表明，算法 IFS-CE-IDS 在大部分数 据集上能够在特征子集和分类精度上取得和算法 HFS-CE-IDS 相接近的，甚至更好的结果，可以证 明算法 IFS-CE-IDS 是一种有效的特征选择算法。 3.2 决策性能分析 为检验算法 IFS-CE-IDS 的决策性能，本文使 用文献 [28] 中对不完备数据进行评估所提出的 6 种评估函数评估算法 HFS-CE-IDS 以及算法 IFS-CE-IDS 计算的特征子集的决策性能。 C IDS = (U,C ∪ {d},V, f) 6 种评估函数中，特征集合 下不完备决策系 统 近似准确评估函数定义为 aC(F) = ∑ Dj∈U/D |apr C (Dj)| ∑ Dj∈U/D |aprC (Dj)| apr C =∪{x ∈ U|MCC ⊆ Dj , Dj ∈ U/D},1 ⩽ i ⩽ n aprC = ∪{x ∈ U|MCC ∩ Dj , Ø,Dj ∈ U/D}, 1 ⩽ i ⩽ n F = U/D MCC C 式中： ， 是下近似值； ，是上近似值； 。其中， 表示 在特征子集 下所得最大一致块集合。 IDS = (U,C ∪ {d},V, f) C 不完备决策系统 特征集 合 下的一致性度量评估函数的定义为 cC(D) = ∑ Dj∈U/D |apr C (Dj)| |U| IDS = (U,C ∪ {d},V, f) RULE = {Zi j|Zi j : des(Xi) → des(Dj),Xi ∈ MCC,Dj ∈ MCd} α 不完备决策系统 在 下的确定性度量 评估函数定义为 α(IDS) = 1 m ∑m Ni 1 Ni ∑Ni j=1 |Xi ∩ Dj | |Xi | Ni Xi Xi ∈ U P ⊆ C (u, v) ∈ T(P),∀u, v ∈ Xi Y ∈ U Xi ⊂ Y (u, v) ∈ T(P),∀u, v ∈ Y Xi 式中： 是在不完备决策表中由最大一致块 所 诱导得到的决策类数目； 表示在 下， ，且不存在一个子集 ， ， ，称 为最大一致块。 IDS = (U,C ∪ {d},V, f) RULE = {Zi j|Zi j : des(Xi) → des(Dj),Xi ∈ MCC,Dj ∈MCd} β 不完备决策系统 在 下的一 致性度量 评估函数定义为 第 3 期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·497·
·498· 智能系统学报 第16卷 Ds=点-2xnDX- 不完备决策系统DS=(U,CU{d,V,f)在 RULE={ZlZ:des(X)→des(Di,X;EMCc,.Dj∈MCal 式中：N:是在不完备决策表中由最大一致块X,所 下的覆盖度量0评估函数定义为 诱导得到决策类数目，且4(Z)=XnD/IX。 9DS)= 1 不完备决策系统DS=(U,CU{d,V,f)在RULE= 而名可 {ZlZ:des(X)→des(D,X;E MCc,D,∈MC下的支持 选择表1中每组数据集中50%数据对象，更 度量y评估函数定义为 新其特征值，然后分别运行算法HFS-CE-IDS和 算法IFS-CE-IDS对特征值更新数据集进行特征 y(IDS)= 选择。并且使用上述6种评估函数评估每组数据 集更新后两种算法特征选择的特征子集的决策性 式中N是条件部分关于D,的最大一致块数。 能，实验结果如表5所示。 表5HFS-CE-IDS与IFS-CE-IDS的度量比较 Table 5 Measurement comparison of HFS-CE-IDS with IFS-CE-IDS 评价指标 算法 Hepatitis Audiology Cancer Soybean Dermatology Wisconsin Car Ozone kr-vs-kp HFS-CE-IDS 1.0000 1.0000 1.0000 0.8402 1.0000 1.0000 0.00120.8471 0.8464 ac IFS-CE-IDS 1.0000 1.0000 1.0000 0.8402 1.0000 1.0000 0.00120.8471 0.8464 HFS-CE-IDS 1.0000 1.0000 1.0000 0.9239 1.0000 1.0000 0.0052 0.9183 0.9312 Cc IFS-CE-IDS 1.0000 1.0000 1.0000 0.9239 1.0000 1.0000 0.0052 0.9183 0.9312 HFS-CE-IDS 1.0000 1.0000 1.0000 0.9669 1.0000 1.0000 0.26360.95910.9678 IFS-CE-IDS 1.0000 1.0000 1.0000 0.9667 1.0000 1.0000 0.26360.95910.9678 HFS-CE-IDS 1.0000 1.0000 1.0000 0.9372 1.0000 1.0000 0.22950.94770.9375 IFS-CE-IDS 1.0000 1.0000 1.0000 0.9369 1.0000 1.0000 0.22950.9477 0.9375 HFS-CE-IDS 0.0075 0.0051 0.0019 0.0015 0.0028 0.0019 0.00170.0012 0.0004 IFS-CE-IDS 0.0077 0.0052 0.0019 0.0016 0.0028 0.0019 0.00170.0012 0.0004 HFS-CE-IDS 0.0067 0.0045 0.0014 0.0016 0.0027 0.0014 0.00340.0013 0.0004 IFS-CE-IDS 0.0067 0.0045 0.0014 0.0016 0.0027 0.0014 0.00340.00130.0004 从表5的实验结果可知，算法IFS-CE-DS与 与算法HFS-CE-DS相同的决策性能。 算法HFS-CE-IDS相比，在近似准确评估ac、一致 3.3效率分析 性度量评估cc以及覆盖度量评估0这3种评估 为验证本文提出的增量式特征选择算法FS 函数下的评估值是相同的；在数据集Soybean上， CE-DS的高效性，采用传统的批量式特征选择算 算法IFS-CE-IDS与算法HFS-CE-IDS在确定性度 法HFS-CE-IDS作比较，该算法是一种与所提出 量α评估函数以及一致性度量B评估函数下的评 算法基于相同特征评估准则的非增量方法。对 估值不相同，而在其他8个数据集上两种算法的 表1中的每组数据集，依次选择其中的5%，10%， 确定性度量α评估函数以及一致性度量B评估函 15%,…,50%数据对象并更新其对象特征值。同 数的评估值是相同的；在支持度量y评估函数所 时发生变化的特征值取决于对象特征的值域。当 得评估值结果中，两种算法在Cancer、Dermato- 有不同规模的数据对象特征值发生更新，分别使 logy、Wisconsin、Car、Ozone、kr-vs-kp这6个数据 用增量式特征选择算法FS-CE-IDS和传统批量 集上的评估值相同，虽然在其余3个数据集上的 式特征选择算法HFS-CE-IDS对数据集进行特征 评价值不同，但是评估值十分接近。 选择，求解特征选择结果。计算时间的比较结果 结合两种算法在6种评估函数下的结果，表 如图1所示，图中详细给出两种算法计算时间随 明算法IFS-CE-IDS在大部分数据集下能够取得 数据对象特征值更新规模的变化而发生的变化
β(IDS) = 1 m [1− 4 |Xi | ∑Ni j=1 |Xi ∩ Dj |µ(Zi j)(1−µ(Zi j))] Ni Xi µ(Zi j) = |Xi ∩ Dj |/|Xi | 式中： 是在不完备决策表中由最大一致块 所 诱导得到决策类数目，且 。 IDS = (U,C ∪ {d},V, f) RULE = {Zi j|Zi j : des(Xi) → des(Dj),Xi ∈ MCC,Dj ∈MCd} γ 不完备决策系统 在 下的支持 度量 评估函数定义为 γ(IDS) = ∑n j=1 |Dj | Nj |U| ∑Nj k=1 |Xk ∩ Dj | |U| 式中 Nj 是条件部分关于 Dj 的最大一致块数。 IDS = (U,C ∪ {d},V, f) RULE = {Zi j|Zi j : des(Xi) → des(Dj),Xi ∈ MCC,Dj ∈ MCd} ϑ 不完备决策系统 在 下的覆盖度量 评估函数定义为 ϑ(IDS) = 1 |U| ∑m i=1 |Xi | |U| 选择表 1 中每组数据集中 50% 数据对象，更 新其特征值，然后分别运行算法 HFS-CE-IDS 和 算法 IFS-CE-IDS 对特征值更新数据集进行特征 选择。并且使用上述 6 种评估函数评估每组数据 集更新后两种算法特征选择的特征子集的决策性 能，实验结果如表 5 所示。 表 5 HFS-CE-IDS 与 IFS-CE-IDS 的度量比较 Table 5 Measurement comparison of HFS-CE-IDS with IFS-CE-IDS 评价指标 算法 Hepatitis Audiology Cancer Soybean Dermatology Wisconsin Car Ozone kr-vs-kp aC HFS-CE-IDS 1.000 0 1.0000 1.000 0 0.840 2 1.000 0 1.0000 0.001 2 0.8471 0.846 4 IFS-CE-IDS 1.000 0 1.0000 1.000 0 0.840 2 1.000 0 1.0000 0.001 2 0.8471 0.846 4 cC HFS-CE-IDS 1.000 0 1.0000 1.000 0 0.923 9 1.000 0 1.0000 0.005 2 0.9183 0.931 2 IFS-CE-IDS 1.000 0 1.0000 1.000 0 0.923 9 1.000 0 1.0000 0.005 2 0.9183 0.931 2 α HFS-CE-IDS 1.000 0 1.0000 1.000 0 0.966 9 1.000 0 1.0000 0.263 6 0.9591 0.967 8 IFS-CE-IDS 1.000 0 1.0000 1.000 0 0.966 7 1.000 0 1.0000 0.263 6 0.9591 0.967 8 β HFS-CE-IDS 1.000 0 1.0000 1.000 0 0.937 2 1.000 0 1.0000 0.229 5 0.9477 0.937 5 IFS-CE-IDS 1.000 0 1.0000 1.000 0 0.936 9 1.000 0 1.0000 0.229 5 0.9477 0.937 5 γ HFS-CE-IDS 0.007 5 0.0051 0.001 9 0.001 5 0.002 8 0.0019 0.001 7 0.0012 0.000 4 IFS-CE-IDS 0.007 7 0.0052 0.001 9 0.001 6 0.002 8 0.0019 0.001 7 0.0012 0.000 4 ϑ HFS-CE-IDS 0.006 7 0.0045 0.001 4 0.001 6 0.002 7 0.0014 0.003 4 0.0013 0.000 4 IFS-CE-IDS 0.006 7 0.0045 0.001 4 0.001 6 0.002 7 0.0014 0.003 4 0.0013 0.000 4 aC cC ϑ α β α β γ 从表 5 的实验结果可知，算法 IFS-CE-IDS 与 算法 HFS-CE-IDS 相比，在近似准确评估 、一致 性度量评估 以及覆盖度量评估 这 3 种评估 函数下的评估值是相同的；在数据集 Soybean 上， 算法 IFS-CE-IDS 与算法 HFS-CE-IDS 在确定性度 量 评估函数以及一致性度量 评估函数下的评 估值不相同，而在其他 8 个数据集上两种算法的 确定性度量 评估函数以及一致性度量 评估函 数的评估值是相同的；在支持度量 评估函数所 得评估值结果中，两种算法在 Cancer、Dermatology、Wisconsin、Car、Ozone、kr-vs-kp 这 6 个数据 集上的评估值相同，虽然在其余 3 个数据集上的 评价值不同，但是评估值十分接近。 结合两种算法在 6 种评估函数下的结果，表 明算法 IFS-CE-IDS 在大部分数据集下能够取得 与算法 HFS-CE-IDS 相同的决策性能。 3.3 效率分析 为验证本文提出的增量式特征选择算法 IFSCE-IDS 的高效性，采用传统的批量式特征选择算 法 HFS-CE-IDS 作比较，该算法是一种与所提出 算法基于相同特征评估准则的非增量方法。对 表 1 中的每组数据集，依次选择其中的 5%, 10%, 15%, ···, 50% 数据对象并更新其对象特征值。同 时发生变化的特征值取决于对象特征的值域。当 有不同规模的数据对象特征值发生更新，分别使 用增量式特征选择算法 IFS-CE-IDS 和传统批量 式特征选择算法 HFS-CE-IDS 对数据集进行特征 选择，求解特征选择结果。计算时间的比较结果 如图 1 所示，图中详细给出两种算法计算时间随 数据对象特征值更新规模的变化而发生的变化。 ·498· 智 能 系 统 学 报 第 16 卷
第3期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·499· 0.80 110 0.610F 0.64 88 0.488 048 6.6 量0366 -HFS-CE-IDS 4.4 -eIFS-CE-IDS 0.16 22 HFS-CE-IDS 0.122 ∀-HFS-CE-IDS eIFS-CE-IDS -e-IFS-CE-IDS 0 0 5101520253035404550 5101520253035404550 5101520253035404550 数据修改量/% 数据修改量% 数据修改量% (a)Hepatitis (b)Audiology (c)Cancer 15.50r 11.50g 17.0g 12.40 9.20 又∀∀∀ 13.6 9.30 行 6.90 10.2 6.20 4.60 001 6.8 HFS-CE-IDS HFS-CE-IDS -∀HFS-CE-IDS 3.10 IFS-CE-IDS 2.30 -eIFS-CE-IDS 3.4 -eIFS-CE-IDS 0 5101520253035404550 09吊骨分号品品品书司 0 0009-9999-⊙0 5101520253035404550 数据修改量/% 数据修改量% 数据修改量% (d)Soybean (e)Dermatology (f)Wisconsin 12.0 5100 人 130 9.6 4080 104 7.2 3060 78 b6-00000006 4.8 2.4 ∀-HFS-CEDS 1020 ∀-HFS-CE-IDS HFS-CE-IDS -eIFS-CE-IDS eIFS-CE-IDS 26 eIFS-CE-IDS 0 0 5101520253035404550 5101520253035404550 101520253035404550 数据修改量% 数据修改量/% 数据修改量/% (g)Car (h)Ozone (0）kr-vs-kp 图1算法HFS-CE-IDS与算法FS-CE-IDS计算时间比较 Fig.1 Computational time comparison between HFS-CE-IDS and IFS-CE-IDS 从图1可知，当不同规模的数据对象特征值 法IFS-CE-IDS的分类精度、决策性能和计算效率 发生更新后，传统批量式特征选择算法HFS-CE- 三部分实验结果可知，算法IFS-CE-IDS与算法 IDS比增量式特征选择算法IFS-CE-IDS花费更多 HFS-CE-DS相比，在大部分数据集上进行特征选 时间来选择特征值更新后的特征子集，主要的原 择所得特征子集数量相接近，两种算法分类精度 因是增量式算法IFS-CE-IDS能够避免重复的计 和决策性能基本相同，但算法FS-CE-DS的计算 算，可以利用之前已有的计算结果，从而使得特 时间小于算法HFS-CE-IDS,尤其在数据规模较大 征选择的计算效率得以提高。算法IFS-CE- 的数据集上计算时间的优势更加明显。通过本节 IDS在9组数据集上的计算效率普遍比算法HFS- 分类精度、决策性能和计算效率三部分实验分 CE-DS高，尤其是在一些数据规模较大的数据集 析，证明FS-CE-IDS是一种高效的处理数据对象 上，算法FS-CE-DS的高效性更加明显。比如在 特征值更新问题的增量式特征选择算法。 Ozone数据集上算法IFS-CE-IDS的计算效率远优 4结束语 于算法HFS-CE-IDS的计算效率。图1中两种特 征选择算法的计算时间都存在一些波动，如数据 本文提出了不完备决策系统中面向特征值动 集Ozone中对象数据对象特征值更新20%时，算 态更新的增量式特征选择算法。通过分析不完备 法HFS-CE-IDS的计算时间突然变得比其他比例 决策系统中条件特征值和决策特征值同时更新时 耗时更大，因为数据集的数值对象特征值发生更 相容类和决策类的动态更新模式，构造了条件信 新后，它的相容类与决策类因数据对象特征更新 息嫡的增量计算机制，并进一步设计了一种基于 而产生变化，从而导致计算时间发生波动。 动态不完备决策系统的增量式特征选择算法。实 在实验分析中，通过算法HFS-CE-IDS与算 验选取了9组UCI公共数据集，并通过分类精
5 10 15 20 25 30 35 40 45 50 0 0.16 0.32 0.48 0.64 0.80 0 2.2 4.4 6.6 8.8 11.0 0 0.122 0.244 0.366 0.488 0.610 0 3.10 6.20 9.30 12.40 15.50 0 2.30 4.60 6.90 9.20 11.50 HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS HFS-CE-IDS IFS-CE-IDS (f) Wisconsin 0 3.4 6.8 10.2 13.6 17.0 (g) Car 0 2.4 4.8 7.2 9.6 12.0 (h) Ozone 0 1 020 2 040 3 060 4 080 5 100 (i) kr-vs-kp 0 26 52 78 104 130 计算时间/s 计算时间/s 计算时间/s 计算时间/s 计算时间/s 计算时间/s 计算时间/s 计算时间/s 计算时间/s 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% 5 10 15 20 25 30 35 40 45 50 数据修改量/% (a) Hepatitis (b) Audiology (c) Cancer (d) Soybean (e) Dermatology 图 1 算法 HFS-CE-IDS 与算法 IFS-CE-IDS 计算时间比较 Fig. 1 Computational time comparison between HFS-CE-IDS and IFS-CE-IDS 从图 1 可知，当不同规模的数据对象特征值 发生更新后，传统批量式特征选择算法 HFS-CEIDS 比增量式特征选择算法 IFS-CE-IDS 花费更多 时间来选择特征值更新后的特征子集，主要的原 因是增量式算法 IFS-CE-IDS 能够避免重复的计 算，可以利用之前已有的计算结果，从而使得特 征选择的计算效率得以提高。算 法 IFS-CEIDS 在 9 组数据集上的计算效率普遍比算法 HFSCE-IDS 高，尤其是在一些数据规模较大的数据集 上，算法 IFS-CE-IDS 的高效性更加明显。比如在 Ozone 数据集上算法 IFS-CE-IDS 的计算效率远优 于算法 HFS-CE-IDS 的计算效率。图 1 中两种特 征选择算法的计算时间都存在一些波动，如数据 集 Ozone 中对象数据对象特征值更新 20% 时，算 法 HFS-CE-IDS 的计算时间突然变得比其他比例 耗时更大，因为数据集的数值对象特征值发生更 新后，它的相容类与决策类因数据对象特征更新 而产生变化，从而导致计算时间发生波动。 在实验分析中，通过算法 HFS-CE-IDS 与算 法 IFS-CE-IDS 的分类精度、决策性能和计算效率 三部分实验结果可知，算法 IFS-CE-IDS 与算法 HFS-CE-IDS 相比，在大部分数据集上进行特征选 择所得特征子集数量相接近，两种算法分类精度 和决策性能基本相同，但算法 IFS-CE-IDS 的计算 时间小于算法 HFS-CE-IDS，尤其在数据规模较大 的数据集上计算时间的优势更加明显。通过本节 分类精度、决策性能和计算效率三部分实验分 析，证明 IFS-CE-IDS 是一种高效的处理数据对象 特征值更新问题的增量式特征选择算法。 4 结束语 本文提出了不完备决策系统中面向特征值动 态更新的增量式特征选择算法。通过分析不完备 决策系统中条件特征值和决策特征值同时更新时 相容类和决策类的动态更新模式，构造了条件信 息熵的增量计算机制，并进一步设计了一种基于 动态不完备决策系统的增量式特征选择算法。实 验选取了 9 组 UCI 公共数据集，并通过分类精 第 3 期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·499·
·500· 智能系统学报 第16卷 度、决策性能以及计算效率3个方面与传统批量 based systems,2002,10(1):95-103 式特征选择算法进行了性能对比。实验结果表 [11]QIAN Yuhua,LIANG Jiye,WANG Feng.A new method 明，本文算法所选择的特征子集与批量式算法在 for measuring the uncertainty in incomplete information 分类精度和决策性能具有基本一致的性能表现。 systems[J].International journal of uncertainty,fuzziness 同时，在面对不完备数据中特征值的动态变化环 and knowledge-based systems,2009,17(6):855-880. 境下，本文算法的计算效率远优于传统批量式算 [12]DAI Jianhua,WANG Wentao,XU Qing.An uncertainty 法，可在较短时间内计算出一个可行的特征子 measure for incomplete decision tables and its applica- 集。实验中部分数据集使用算法IFS-CE-IDS需 tions[J].IEEE transactions on cybernetics,2013,43(4): 要进行特征转化，导致失去部分有效信息，降低 1277-1289 [13]ZHAO Hua,QIN Keyun.Mixed feature selection inin- 算法结果质量，未来将致力于寻求更有效处理混 complete decision table[J].Knowledge-based systems, 合数据的增量特征算法。 2014,57:181-190. 参考文献： [14]RAGHAVAN V,HAFEZ A.Dynamic data mining[Cl// Proceedings of the 13th International Conference on In- [1]KWAK N,CHOI C H.Input feature selection by mutual dustrial and Engineering Applications of Artificial Intelli- information based on Parzen window[J].IEEE transac- gence and Expert Systems.New Orleans,Louisiana, tions on pattern analysis and machine intelligence,2002, USA.2000 2412):1667-1671. [15]LI Tianrui,RUAN Da,GEERT W,et al.A rough sets [2]SLOWINSKI R.VANDERPOOTEN D.A generalized based characteristic relation approach for dynamic attrib- definition of rough approximations based on similarity[J]. ute generalization in data mining[J].Knowledge-based IEEE transactions on knowledge and data engineering, systems,2007,20(5)485-494. 2000,12(2):331-336. [16]XU Yitian,WANG Laisheng,ZHANG Ruiyan.A dynam- [3]KRYSZKIEWICZ M.Rough set approach to incomplete ic attribute reduction algorithm based on 0-1 integer pro- information systems[J].Information sciences,1998, gramming[J].Knowledge-based systems,2011,24(8): 112(1/2/3/4:39-49. 1341-1347. [4]PARTHALAIN N M.SHEN Qiang.Exploring the bound- [17]QIAN Jin,DANG Chuangyin,YUE Xiaodong,et al.At- ary region of tolerance rough sets for feature selection[J]. tribute reduction for sequential three-way decisions under Pattern recognition,2009,42(5):655-667. dynamic granulation[J].International journal of approx- [5]MENG Zuqiang,SHI Zhongzhi.Extended rough set-based imate reasoning,2017,85:196-216. attribute reduction in inconsistent incomplete decision sys- [18]YANG Yanyan,CHEN Degang,WANG Hui,et al.Incre- tems[J].Information sciences,2012,204:44-69 mental perspective for feature selection based on fuzzy [6]GRZYMALA-BUSSEJ W.CLARK P G.KUEHNHAUSEN M. rough sets[J].IEEE transactions on fuzzy systems,2018. Generalized probabilistic approximations of incomplete 26(31257-1273. data[J].International journal of approximate reasoning, [19]LANG Guangming,CAI Mingjie,FUJITA H,et al.Re- 2014,55(1):180-196. lated families-based attribute reduction of dynamic cover- [7]QIAN Yuhua,LIANG Jiye,PEDRYCZ W.et al.An effi- ing decision information systems[J].Knowledge-based cient accelerator for attribute reduction from incomplete systems,.2018,162:161-173 data in rough set framework[J].Pattern recognition,2011, [20]WEI Wei,WU Xiaoying,LIANG Jiye,et al.Discernibil- 44(8):1658-1670 ity matrix based incremental attribute reduction for dy- [8]DAI Jianhua.Rough set approach to incomplete numerical namic data[J].Knowledge-based systems,2018,140: data[J].Information sciences,2013,241:43-57. 142-157. [9]YANG Xibei,YANG Jingyu,WU Chen,et al.Dominance- [21]ZENG Anping,LI Tianrui,LIU Dun,et al.A fuzzy rough based rough set approach and knowledge reductions in in- set approach for incremental feature selection on hybrid complete ordered information system[.Information sci- information systems[J].Fuzzy sets and systems,2015, ences,2008,178(4):1219-1234 258:39-60 [10]LIANG Jiye,XU Zongben.The algorithm on knowledge [22]LIANG Jiye,WANG Feng,DANG Chuangyin,et al.A reduction in incomplete information systems[J].Interna- group incremental approach to feature selection applying tional journal of uncertainty,fuzziness and knowledge rough set technique[J].IEEE transactions on knowledge
度、决策性能以及计算效率 3 个方面与传统批量 式特征选择算法进行了性能对比。实验结果表 明，本文算法所选择的特征子集与批量式算法在 分类精度和决策性能具有基本一致的性能表现。 同时，在面对不完备数据中特征值的动态变化环 境下，本文算法的计算效率远优于传统批量式算 法，可在较短时间内计算出一个可行的特征子 集。实验中部分数据集使用算法 IFS-CE-IDS 需 要进行特征转化，导致失去部分有效信息，降低 算法结果质量，未来将致力于寻求更有效处理混 合数据的增量特征算法。 参考文献： KWAK N, CHOI C H. Input feature selection by mutual information based on Parzen window[J]. IEEE transactions on pattern analysis and machine intelligence, 2002, 24(12): 1667–1671. [1] SLOWINSKI R, VANDERPOOTEN D. A generalized definition of rough approximations based on similarity[J]. IEEE transactions on knowledge and data engineering, 2000, 12(2): 331–336. [2] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39–49. [3] PARTHALÁIN N M, SHEN Qiang. Exploring the boundary region of tolerance rough sets for feature selection[J]. Pattern recognition, 2009, 42(5): 655–667. [4] MENG Zuqiang, SHI Zhongzhi. Extended rough set-based attribute reduction in inconsistent incomplete decision systems[J]. Information sciences, 2012, 204: 44–69. [5] GRZYMALA-BUSSE J W, CLARK P G, KUEHNHAUSEN M. Generalized probabilistic approximations of incomplete data[J]. International journal of approximate reasoning, 2014, 55(1): 180–196. [6] QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J]. Pattern recognition, 2011, 44(8): 1658–1670. [7] DAI Jianhua. Rough set approach to incomplete numerical data[J]. Information sciences, 2013, 241: 43–57. [8] YANG Xibei, YANG Jingyu, WU Chen, et al. Dominancebased rough set approach and knowledge reductions in incomplete ordered information system[J]. Information sciences, 2008, 178(4): 1219–1234. [9] LIANG Jiye, XU Zongben. The algorithm on knowledge reduction in incomplete information systems[J]. International journal of uncertainty, fuzziness and knowledge- [10] based systems, 2002, 10(1): 95–103. QIAN Yuhua, LIANG Jiye, WANG Feng. A new method for measuring the uncertainty in incomplete information systems[J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2009, 17(6): 855–880. [11] DAI Jianhua, WANG Wentao, XU Qing. An uncertainty measure for incomplete decision tables and its applications[J]. IEEE transactions on cybernetics, 2013, 43(4): 1277–1289. [12] ZHAO Hua, QIN Keyun. Mixed feature selection in incomplete decision table[J]. Knowledge-based systems, 2014, 57: 181–190. [13] RAGHAVAN V, HAFEZ A. Dynamic data mining[C]// Proceedings of the 13th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. New Orleans, Louisiana, USA, 2000. [14] LI Tianrui, RUAN Da, GEERT W, et al. A rough sets based characteristic relation approach for dynamic attribute generalization in data mining[J]. Knowledge-based systems, 2007, 20(5): 485–494. [15] XU Yitian, WANG Laisheng, ZHANG Ruiyan. A dynamic attribute reduction algorithm based on 0-1 integer programming[J]. Knowledge-based systems, 2011, 24(8): 1341–1347. [16] QIAN Jin, DANG Chuangyin, YUE Xiaodong, et al. Attribute reduction for sequential three-way decisions under dynamic granulation[J]. International journal of approximate reasoning, 2017, 85: 196–216. [17] YANG Yanyan, CHEN Degang, WANG Hui, et al. Incremental perspective for feature selection based on fuzzy rough sets[J]. IEEE transactions on fuzzy systems, 2018, 26(3): 1257–1273. [18] LANG Guangming, CAI Mingjie, FUJITA H, et al. Related families-based attribute reduction of dynamic covering decision information systems[J]. Knowledge-based systems, 2018, 162: 161–173. [19] WEI Wei, WU Xiaoying, LIANG Jiye, et al. Discernibility matrix based incremental attribute reduction for dynamic data[J]. Knowledge-based systems, 2018, 140: 142–157. [20] 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, 2015, 258: 39–60. [21] LIANG Jiye, WANG Feng, DANG Chuangyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE transactions on knowledge [22] ·500· 智 能 系 统 学 报 第 16 卷
第3期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·501· and data engineering,2014,26(2):294-308. plete decision table[J].Data&knowledge engineering, [23]SHU Wenhao,SHEN Hong.Incremental feature selec- 2008.65(3):373-400 tion based on rough set in dynamic incomplete data[J]. 作者简介： Pattern recognition,2014,47(12):3890-3906. 唐荣，硕士研究生，主要研究方向 [24]XIE Xiaojun,QIN Xiaolin.A novel incremental attribute 为数据挖掘与知识发现、粒计算与粗 reduction approach for dynamic incomplete decision sys- 糙集。 tems[J].International journal of approximate reasoning, 2018.93:443-462 [25]WANG Feng,LIANG Jiye,DANG Chuangyin.Attribute reduction for dynamic data sets[J].Applied soft comput- ing,2013,13(1):676-689. 罗川，副教授，博土，中国人工智 [26]刘吉超，王锋，宋鹏.缺失数据的维数增量式特征选择 能学会粒计算与知识发现专业委员会 [).计算机工程与应用，2019,55(17)：95-99， 委员，中国计算机学会会员、中国人工 LIU Jichao,WANG Feng,SONG Peng.Dimension incre- 智能学会会员，主要研究方向为数据 挖掘与知识发现，粒计算与粗糙集。 mental feature selection algorithm for missing data[J]. 主持国家自然科学基金项目2项，中 Computer engineering and applications,2019,55(17): 国博土后科学基金2项。发表学术论 95-99. 文40余篇。 [27刀钱进，朱亚炎.面向成组对象集的增量式属性约简算法 [J.智能系统学报，2016,11(4)：496-502 曹潜，硕士研究生，主要研究方向 QIAN Jin,ZHU Yayan.An incremental attribute reduc- 为数据挖掘、粒计算与粗糙集。 tion algorithm for group objects[J].CAAI transactions on intelligent systems,2016,11(4):496-502. [28]QIAN Yuhua,DANG Chuangyin,LIANG Jiye,et al.On the evaluation of the decision performance of an incom-
and data engineering, 2014, 26(2): 294–308. SHU Wenhao, SHEN Hong. Incremental feature selection based on rough set in dynamic incomplete data[J]. Pattern recognition, 2014, 47(12): 3890–3906. [23] XIE Xiaojun, QIN Xiaolin. A novel incremental attribute reduction approach for dynamic incomplete decision systems[J]. International journal of approximate reasoning, 2018, 93: 443–462. [24] WANG Feng, LIANG Jiye, DANG Chuangyin. Attribute reduction for dynamic data sets[J]. Applied soft computing, 2013, 13(1): 676–689. [25] 刘吉超, 王锋, 宋鹏. 缺失数据的维数增量式特征选择 [J]. 计算机工程与应用, 2019, 55(17): 95–99. LIU Jichao, WANG Feng, SONG Peng. Dimension incremental feature selection algorithm for missing data[J]. Computer engineering and applications, 2019, 55(17): 95–99. [26] 钱进, 朱亚炎. 面向成组对象集的增量式属性约简算法 [J]. 智能系统学报, 2016, 11(4): 496–502. QIAN Jin, ZHU Yayan. An incremental attribute reduction algorithm for group objects[J]. CAAI transactions on intelligent systems, 2016, 11(4): 496–502. [27] QIAN Yuhua, DANG Chuangyin, LIANG Jiye, et al. On the evaluation of the decision performance of an incom- [28] plete decision table[J]. Data & knowledge engineering, 2008, 65(3): 373–400. 作者简介： 唐荣，硕士研究生，主要研究方向 为数据挖掘与知识发现、粒计算与粗 糙集。 罗川，副教授，博士，中国人工智 能学会粒计算与知识发现专业委员会 委员，中国计算机学会会员、中国人工 智能学会会员，主要研究方向为数据 挖掘与知识发现，粒计算与粗糙集。 主持国家自然科学基金项目 2 项，中 国博士后科学基金 2 项。发表学术论 文 40 余篇。 曹潜，硕士研究生，主要研究方向 为数据挖掘、粒计算与粗糙集。 第 3 期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·501·