第6期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1205· 决策值ac(x: 要将其转为不完备决策系统。采用文献[16]中的 3)依据决策系统中每个对象的广义决策值 方法对完备决策系统进行处理，具体处理方式 ac(x)和多特定类Dme构造相应差别矩阵Mmes; 为：除决策属性之外，每个条件属性对应列选取 4)依据差别矩阵Mms构造相应多特定类 10%的属性值进行缺失处理，缺失值使用*表示。 的广义决策约简区分函数DF(Mms); 3.1约简结果对比 5)利用吸收律和分配律将多特定类区分函 两种约简算法所得平均约简长度对比如表3 数DF(Mmcs)转变为极小析取范式DF'(Mme): 所示。表3中，“全决策类”表示经典全决策类约 6)依据极小析取范式DF'(M)输出多特 简算法所得约简结果，“单特定类”表示MG- 定类D的广义决策约简，算法结束。 DRDM算法选定一个特定类时所得约简结果， 算法1中，步骤1)的时间复杂度为OCIU), “多特定类”表示MGDRDM算法选定多个特定类 步骤2)的时间复杂度为OU),步骤3)、步骤4) 时所得约简结果，“决策值”表示对应算法选取的 的时间复杂度为OCU),步骤5)的过程是一个 一个或多个特定类所表现决策值，“平均约简长 NP-hard问题，该步骤的时间复杂度为OICr),因 此算法1的整体时间复杂度为OCF)。 度”表示对应算法所得约简的平均约简长度。 由表3可知，相比全部决策类，当选定特定类 3实验结果与分析 数量较少时，平均约简长度往往会比全决策类所 得平均约简长度要短。若多特定类选择为所有决 针对本文提出的多特定类不完备决策系统广 策类，则算法将退化为全决策类约简，平均约简 义决策约简算法进行实验验证与分析。本节实验 长度不会缩短。 选择与经典不完备决策系统广义决策约简针对约 简结果、占用空间以及约简效率进行比较。 表3平均约简长度 本节采用6组标准UCI数据集进行实验，数 Table 3 Average reduct length 据集从htp://archive.ics.uci.cdu/ml/datasets.php处下 全决策类 单特定类 多特定类 载。数据集使用WEKA3.6进行等频率离散化预 D数据集 平均约决策平均约决策平均约 处理，因某些原始数据中存在缺失数据数量极 简长度 值 简长度 值 简长度 少，无法直接作为实验使用，所以针对缺失数据 1 Z00 10.3 2 7.6 2,4 8.0 使用相应属性下出现频率最高属性值作为替换， 2 Audiology 24.1 16.7 1.4,611 20.0 针对名词性数据使用整数作为替换。数据集详细 3 Glass 10.0 6 7.0 5,6 8.0 信息如表2所示。表2中，ID表示数据集编号， “数据集”表示数据集名称，U表示数据集中对象 House 13.0 0 10.0 0,2 12.0 数目，1C1表示数据集中条件属性数目，U/Id表 Connec- 5 9.0 0 7.5 0,2 8.0 示数据集中决策类数目。本节实验环境：操作系 tionist Windows7-64 bit;CPU Intel Core i5-6500(3.2 6 Yeast 8.0 7.0 58 7.0 GHz):内存4GB;运行环境Python3.6:开发工具 3.2占用空间对比 PyCharm 本节通过比较两种算法生成的差别矩阵中非 表2数据集 空属性集占比进而比较两种算法占用空间大小。 Table 2 Data Sets 两种算法生成差别矩阵中非空属性集占比如表4 ID 数据集 UI ICI 1U/dl 所示，其中“占比(%)”表示对应不同算法构造差 1 Zoo 101 16 7 别矩阵中非空属性集所占比例。 2 Audiology 200 69 24 由表4可知，当选定一个或者几个特定类，特 3 Glass 214 10 6 定类数量相对全部决策类数量较少时，MG- DRDM算法所构造差别矩阵中非空属性集占比 4 House 506 3 4 J 要小于经典算法构造差别矩阵中的非空属性集占 Connectionist 528 10 11 比。因此，在保证约简目标不变的前提下，MG 6 Yeast 1484 8 10 DRDM算法所构造差别矩阵占用空间要小于经 因本节采用UCI标准数据集，预处理之后数 典算法构造差别矩阵占用空间。除此之外，利用 据集所表示的决策系统为完备决策系统，所以需 差别矩阵中非空属性集构造区分函数以及求取极决策值 ∂C(xi) ； ∂C(xi) Dmcs Mmcs 3) 依据决策系统中每个对象的广义决策值 和多特定类 构造相应差别矩阵 ； Mmcs DF(Mmcs) 4) 依据差别矩阵 构造相应多特定类 的广义决策约简区分函数 ； DF(Mmcs) DF′ (Mmcs) 5) 利用吸收律和分配律将多特定类区分函 数 转变为极小析取范式 ； DF′ (Mmcs) Dmcs 6) 依据极小析取范式 输出多特 定类 的广义决策约简，算法结束。 O(|C||U| 2 ) O(|U| 2 ) O(|C||U| 2 ) O(|C| |U| 2 ) O(|C| |U| 2 ) 算法 1 中，步骤 1) 的时间复杂度为 ， 步骤 2) 的时间复杂度为 ，步骤 3) 、步骤 4) 的时间复杂度为 ，步骤 5) 的过程是一个 NP-hard 问题，该步骤的时间复杂度为 ，因 此算法 1 的整体时间复杂度为 。 3 实验结果与分析 针对本文提出的多特定类不完备决策系统广 义决策约简算法进行实验验证与分析。本节实验 选择与经典不完备决策系统广义决策约简针对约 简结果、占用空间以及约简效率进行比较。 |U| |C| |U/{d}| 本节采用 6 组标准 UCI 数据集进行实验，数 据集从 http://archive.ics.uci.edu/ml/datasets.php 处下 载。数据集使用 WEKA3.6 进行等频率离散化预 处理，因某些原始数据中存在缺失数据数量极 少，无法直接作为实验使用，所以针对缺失数据 使用相应属性下出现频率最高属性值作为替换， 针对名词性数据使用整数作为替换。数据集详细 信息如表 2 所示。表 2 中，ID 表示数据集编号， “数据集”表示数据集名称， 表示数据集中对象 数目， 表示数据集中条件属性数目， 表 示数据集中决策类数目。本节实验环境：操作系 统 Windows7-64 bit；CPU Intel Core i5-6500(3.2 GHz)；内存 4 GB；运行环境 Python 3.6；开发工具 PyCharm。 表 2 数据集 Table 2 Data Sets ID 数据集 |U| |C| |U/{d}| 1 Zoo 101 16 7 2 Audiology 200 69 24 3 Glass 214 10 6 4 House 506 13 4 5 Connectionist 528 10 11 6 Yeast 1 484 8 10 因本节采用 UCI 标准数据集，预处理之后数 据集所表示的决策系统为完备决策系统，所以需 要将其转为不完备决策系统。采用文献 [16] 中的 方法对完备决策系统进行处理，具体处理方式 为：除决策属性之外，每个条件属性对应列选取 10% 的属性值进行缺失处理，缺失值使用*表示。 3.1 约简结果对比 两种约简算法所得平均约简长度对比如表 3 所示。表 3 中，“全决策类”表示经典全决策类约 简算法所得约简结果， “ 单特定类 ” 表 示 MG￾DRDM 算法选定一个特定类时所得约简结果， “多特定类”表示 MGDRDM 算法选定多个特定类 时所得约简结果，“决策值”表示对应算法选取的 一个或多个特定类所表现决策值，“平均约简长 度”表示对应算法所得约简的平均约简长度。 由表 3 可知，相比全部决策类，当选定特定类 数量较少时，平均约简长度往往会比全决策类所 得平均约简长度要短。若多特定类选择为所有决 策类，则算法将退化为全决策类约简，平均约简 长度不会缩短。 表 3 平均约简长度 Table 3 Average reduct length ID 数据集 全决策类 单特定类 多特定类 平均约 简长度 决策 值 平均约 简长度 决策 值 平均约 简长度 1 Zoo 10.3 2 7.6 2,4 8.0 2 Audiology 24.1 4 16.7 1,4,6,11 20.0 3 Glass 10.0 6 7.0 5,6 8.0 4 House 13.0 0 10.0 0,2 12.0 5 Connec￾tionist 9.0 0 7.5 0,2 8.0 6 Yeast 8.0 5 7.0 5,8 7.0 3.2 占用空间对比 本节通过比较两种算法生成的差别矩阵中非 空属性集占比进而比较两种算法占用空间大小。 两种算法生成差别矩阵中非空属性集占比如表 4 所示，其中“占比 (%)”表示对应不同算法构造差 别矩阵中非空属性集所占比例。 由表 4 可知，当选定一个或者几个特定类，特 定类数量相对全部决策类数量较少时， MG￾DRDM 算法所构造差别矩阵中非空属性集占比 要小于经典算法构造差别矩阵中的非空属性集占 比。因此，在保证约简目标不变的前提下，MG￾DRDM 算法所构造差别矩阵占用空间要小于经 典算法构造差别矩阵占用空间。除此之外，利用 差别矩阵中非空属性集构造区分函数以及求取极 第 6 期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1205·