·748· 智能系统学报 第13卷 计算的平均执行时间相对更少。 均执行时间并对比其稳定性。结果见表2，单位 此外，为了更加精确地展现在线快速计算的 为s。可以观察到，对于同一数据集，对比经典 优势及其稳定性，我们将在占数据总量50%的 计算算法，在线快速计算可以大大节约算法执行 情况下，从1时刻到+5时刻，测试两类算法的平 时间。 表2t~什5时刻算法执行时间 Table 2 Experimental results examined from time tto +5 on UCI datasets ms 数据集 算法 +1 1+2 1什3 1+4 +5 平均值±标淮差 经典计算 2.280 1.860 1.890 1.770 1.740 1.800 1.890±0.007 Skin NoSkin 在线计算 0.055 0.043 0.040 0.039 0.039 0.038 0.042±0.006 经典计算 2.220 2.040 1.890 1.860 1.980 1.860 1.980±0.005 Shuttle 在线计算 0.063 0.046 0.045 0.043 0.041 0.039 0.046±0.009 经典计算 2.370 2.280 2.070 1.860 1.980 1.860 1.980±0.005 IRIS 在线计算 0.058 0.048 0.040 0.041 0.040 0.040 0.044±0.007 经典计算 2.340 1.920 2.100 1.800 1.770 1.800 1.950±0.008 Z00 在线计算 0.050 0.040 0.037 0.039 0.037 0.036 0.040±0.005 经典计算 1.950 1.620 1.500 1.500 1.440 1.500 1.590±0.006 Haberman 在线计算 0.043 0.034 0.038 0.031 0.030 0.029 0.034±0.005 经典计算 1.890 1.710 1.710 1.650 1.680 1.740 1.740±0.003 Breast-cancer 在线计算 0.044 0.036 0.034 0.033 0.031 0.032 0.035±0.005 经典计算 2.200 0.740 1.500 1.420 1.400 1.440 1.620±0.015 Letter 在线计算 0.079 0.074 0.058 0.052 0.051 0.049 0.061±0.013 经典计算 2.200 1.860 1.560 1.440 1.320 1.340 1.620±0.017 Magic 在线计算 0.071 0.059 0.053 0.041 0.039 0.043 0.053±0.012 同时，在不同数据集上，在线快速计算执行时 每次都需要执行时间复杂度为O(2IU/ADD的步 间的均值和方差比经典计算算法更小，显示了其 骤，其时间消耗极大，且与内存中的数据量及复 具有更好的效率及稳定性。 杂程度密切相关；而在线快速计算由于只需要对 2)不同内存容量算法执行时间对比 当前实时变化的数据对象进行局部计算，避免了 由于在线计算方法以内存计算为依托，内存 历史数据的重复学习，最多只需执行时间复杂度 空间的容量对于三支决策在线快速计算的执行效 为OU/A·DD的步骤，大大节省了此更新过程的 果是否有影响，是一个值得研究的问题。因此我 开销。 们选择以上8个UCI数据集中规模较大且复杂程 综上可知，在不同内存空间下，在线快速计算 度较高的Breast-.cancer数据集，构造和实验1相 的效率均远高于经典计算算法，且这一优势随着 似的对比实验，但是将内存容量分别为设定为 内存空间的增加更加明显。 100、500、1000、2000条记录，当上述数据集实施 3)不同阈值在线快速计算执行时间对比 两种算法实验的数据总量累计达到总数据量的 由于三支决策是一种典型的概率粗糙集参数 10%、40%、70%和100%时，分别记录这两种算法 化模型，实验结果可能会受参数设置的影响。设 此时的平均执行时间。 置内存空间为100b,并选取了5对阈值，分别测 由图3可以观察到，在相同实验数据累积量 出在线快速计算在8个数据集下执行完毕平均所 下，随着内存空间的增加，经典计算算法的平均 需时间，从而验证在线快速计算的性能与选取阈 执行时间几乎呈指数级速度增长，而在线快速计 值的关系。图4显示了算法平均执行时间随不同 算的时间消耗较为平稳。 阈值对的变化趋势，不难看出，算法的执行时间 由算法的时间复杂度可知，随着决策系统的 随着阈值的改变有轻微的波动，总体来说比较 每一次更新，经典计算算法需要进行所有数据等 稳定。由此也进一步验证了在线快速计算的时间 价类的重新划分及条件概率的重新计算，此过程 复杂度主要取决于动态数据的规模及其复杂程度。计算的平均执行时间相对更少。 此外，为了更加精确地展现在线快速计算的 优势及其稳定性，我们将在占数据总量 50% 的 情况下，从 t 时刻到 t+5 时刻，测试两类算法的平 均执行时间并对比其稳定性。结果见表 2，单位 为 ms。可以观察到，对于同一数据集，对比经典 计算算法，在线快速计算可以大大节约算法执行 时间。 同时，在不同数据集上，在线快速计算执行时 间的均值和方差比经典计算算法更小，显示了其 具有更好的效率及稳定性。 2) 不同内存容量算法执行时间对比 由于在线计算方法以内存计算为依托，内存 空间的容量对于三支决策在线快速计算的执行效 果是否有影响，是一个值得研究的问题。因此我 们选择以上 8 个 UCI 数据集中规模较大且复杂程 度较高的 Breast-cancer 数据集，构造和实验 1 相 似的对比实验，但是将内存容量分别为设定为 100、500、1 000、2 000 条记录，当上述数据集实施 两种算法实验的数据总量累计达到总数据量的 10%、40%、70% 和 100% 时，分别记录这两种算法 此时的平均执行时间。 由图 3 可以观察到，在相同实验数据累积量 下，随着内存空间的增加，经典计算算法的平均 执行时间几乎呈指数级速度增长，而在线快速计 算的时间消耗较为平稳。 由算法的时间复杂度可知，随着决策系统的 每一次更新，经典计算算法需要进行所有数据等 价类的重新划分及条件概率的重新计算，此过程 O(2|U (t) /A| · |D|) O(U(t) /A| · |D|) 每次都需要执行时间复杂度为 的步 骤，其时间消耗极大，且与内存中的数据量及复 杂程度密切相关；而在线快速计算由于只需要对 当前实时变化的数据对象进行局部计算，避免了 历史数据的重复学习，最多只需执行时间复杂度 为 的步骤，大大节省了此更新过程的 开销。 综上可知，在不同内存空间下，在线快速计算 的效率均远高于经典计算算法，且这一优势随着 内存空间的增加更加明显。 3) 不同阈值在线快速计算执行时间对比 由于三支决策是一种典型的概率粗糙集参数 化模型，实验结果可能会受参数设置的影响。设 置内存空间为 100 b，并选取了 5 对阈值，分别测 出在线快速计算在 8 个数据集下执行完毕平均所 需时间，从而验证在线快速计算的性能与选取阈 值的关系。图 4 显示了算法平均执行时间随不同 阈值对的变化趋势，不难看出，算法的执行时间 随着阈值的改变有轻微的波动，总体来说比较 稳定。由此也进一步验证了在线快速计算的时间 复杂度主要取决于动态数据的规模及其复杂程度。 表 2 t～t+5 时刻算法执行时间 Table 2 Experimental results examined from time t to t+5 on UCI datasets ms 数据集 算法 t t+1 t+2 t+3 t+4 t+5 平均值±标准差 Skin_NoSkin 经典计算 2.280 1.860 1.890 1.770 1.740 1.800 1.890±0.007 在线计算 0.055 0.043 0.040 0.039 0.039 0.038 0.042±0.006 Shuttle 经典计算 2.220 2.040 1.890 1.860 1.980 1.860 1.980±0.005 在线计算 0.063 0.046 0.045 0.043 0.041 0.039 0.046±0.009 IRIS 经典计算 2.370 2.280 2.070 1.860 1.980 1.860 1.980±0.005 在线计算 0.058 0.048 0.040 0.041 0.040 0.040 0.044±0.007 Zoo 经典计算 2.340 1.920 2.100 1.800 1.770 1.800 1.950±0.008 在线计算 0.050 0.040 0.037 0.039 0.037 0.036 0.040±0.005 Haberman 经典计算 1.950 1.620 1.500 1.500 1.440 1.500 1.590±0.006 在线计算 0.043 0.034 0.038 0.031 0.030 0.029 0.034±0.005 Breast-cancer 经典计算 1.890 1.710 1.710 1.650 1.680 1.740 1.740±0.003 在线计算 0.044 0.036 0.034 0.033 0.031 0.032 0.035±0.005 Letter 经典计算 2.200 0.740 1.500 1.420 1.400 1.440 1.620±0.015 在线计算 0.079 0.074 0.058 0.052 0.051 0.049 0.061±0.013 Magic 经典计算 2.200 1.860 1.560 1.440 1.320 1.340 1.620±0.017 在线计算 0.071 0.059 0.053 0.041 0.039 0.043 0.053±0.012 ·748· 智 能 系 统 学 报 第 13 卷