第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·