·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 in￾formation system，IIS)；对于决策系统来说，如果 ，称这样的决策系统为不完备决策系 统 (incomplete decision system， IDS)；对于 这样的决策系统，称为完备决策系统。 P ⊆ C IND(P) 完备信息系统中条件特征的任何子集 可诱导一种不可辨识关系 ，定义为 ·494· 智 能 系 统 学 报 第 16 卷