·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、SVMxi(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% 的已 知特征值变为缺失值，使原始完备数据集变为不 完备数据集。对含有数值型数据的数据集 Hepat￾itis、Wisconsin、Dermatology 和 Ozone，将数值型特 征进行了离散化处理。如数据集 Hepatitis 包含 19 个特征，其中 6 个为数值型特征；数据集 Wis￾consin 含有 1 个数值型特征；数据集 Dermato￾logy 包含 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-CE￾IDS 所得特征子集的分类精度，对表 1 中 9 组数 据集选择其中 50% 对象，并且更新其特征值，然 后分别运行传统批量式算法 HFS-CE-IDS 和增量 式算法 IFS-CE-IDS 对特征值更新数据集进行特 征选择。使用决策树 J48、Naïve Bayes、SVM ·496· 智 能 系 统 学 报 第 16 卷