·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、Dermato￾logy、Wisconsin、Car、Ozone、kr-vs-kp 这 6 个数据 集上的评估值相同，虽然在其余 3 个数据集上的 评价值不同，但是评估值十分接近。 结合两种算法在 6 种评估函数下的结果，表 明算法 IFS-CE-IDS 在大部分数据集下能够取得 与算法 HFS-CE-IDS 相同的决策性能。 3.3 效率分析 为验证本文提出的增量式特征选择算法 IFS￾CE-IDS 的高效性，采用传统的批量式特征选择算 法 HFS-CE-IDS 作比较，该算法是一种与所提出 算法基于相同特征评估准则的非增量方法。对 表 1 中的每组数据集，依次选择其中的 5%, 10%, 15%, ···, 50% 数据对象并更新其对象特征值。同 时发生变化的特征值取决于对象特征的值域。当 有不同规模的数据对象特征值发生更新，分别使 用增量式特征选择算法 IFS-CE-IDS 和传统批量 式特征选择算法 HFS-CE-IDS 对数据集进行特征 选择，求解特征选择结果。计算时间的比较结果 如图 1 所示，图中详细给出两种算法计算时间随 数据对象特征值更新规模的变化而发生的变化。 ·498· 智 能 系 统 学 报 第 16 卷