·374· 智能系统学报 第12卷 的。对于数值型数据集，首先进行离散化并构造等 计算正域POS,(D) 价关系。若两个样本在所有属性上取值一样，那么 这两个样本就为一类，否则不是一类。而在离散化 Va,eA,计算可辨识矩阵y 过程中，避免不了信息流失，而这恰恰是当今研究 计算可辨识矩阵W 的热点。本算法通过定义一个距离参数，考虑某两 个样本在属性上的相似程度。如果两个样本之间 赋初值REDA 距离小于阈值，则这两个样本就可以聚为一类，这 a,eRED,计算N:Ro和sUm(N,En】 比经典粗糙集的理论显然更多地考虑了样本之间 选择最优的a,并且RED-{A-a} 的联系，避免大量信息的流失，从而提高了属性约 简的精度。由于利用定理3去搜索决策表的全部约 <(sum(N)-sum(NU 简是一个NP问题，因此利用本文提出的辨识矩阵 的概念来构造一个启发式算法。 N 算法辨识矩阵属性约简算法(DISRS)。 输出约简RED 输入(U,A,D={d}),阈值0/10是用于算法 图1属性约简算法流程图 停止搜索的阈值。 Fig.1 Flow chart of attribute reduction 输出约简RED。 本实验采用K近邻(KNN,K=3)和支持向量机 1)计算正域POS(D)。 (RBF-SVM)分类器来评估这些属性约简算法的优 2)计算出关系矩阵N。,即对于任意的样本x:, 劣，RBF-SVM分类器中参数采用默认值。数据的分 x∈U,若d(x:)≠d(x),令No(i,ji)=0,否则，令 类精度是基于十折交叉验证方法计算的。从UCI N,(i,j)=1。 数据集中选择了5个数值型的数据集，其属性和分 3)Va,∈A,计算可辨识矩阵N,对于任意x:∈ 类信息描述如表3所示。在本文所提的算法 POS(D)和任意x∈U,当N(i,j)=0时，若 (DISRS)中，停止搜索的阈值0设置为0=0.005。 f(x)-f(x)>e,令N,(i)=1,否则令N,(i,j)= 为了说明该算法的有效性和可行性，首先对各个数 0:当N(i,j)=1,令N,(i,j)=0。 据集进行了属性约简，选取约简数据的最高分类精 4)计算N4=UN,RED-A。 度所对应的属性数目进行比较，具体结果如表4所 5)a,∈A,计算N1ta和sum(N1i-a),其中 示，其中ε列表示对应数据约简后所取得的最高分 sum(N)表示对矩阵V的行列求和。 类精度的相似度阈值的取值。表5和表6分别给出 6)选择满足sum（Niod-a4l）=max（sum 了各个数据集属性约简前后的分类精度。 (Nid)的ak,令RED4-{A-ak}。 表3数据描述 7)如果(sum(N4)-sum(N))/|U<8,输出约 Table 3 Data information 简RED。否则，转到5)。 序号 Data sets Samples Numerical Classes 了更好地理解所提出的算法，下面给出该算法 1 Glass 214 10 6 的流程图，如图1。 2 Colon 62 1224 2 3实验分析 Wine 178 13 3 为了验证算法的有效性，从一些文献中选出4 Wdbe 569 30 2 个相关的属性约简方法与本文所提的算法作比较。 这4个算法分别是经典粗糙集算法(FCMRS)[)、邻 Prostate 102 12625 2 域粗糙集算法(NBRS)[、邻域粗糙信息测度算法 从表4中可以看出，这5种属性约简方法都能 (NBIM)[]以及自适应邻域粗糙集模型 够有效地对数据集进行属性约简。FCMRS算法选 (APTNB))。本实验主要从算法选择的属性数目 取的属性数目最少，DISRS算法次之。表5和表6 和相应的分类精度两个方面进行比较。计算机运 表明，DISRS算法的分类精度最高，FCMRS算法的 行的环境参数为：奔腾双核，CPUE52001.90GHz, 分类精度最低。同时，DISRS算法所对应的分类精 RAM4.0GB,软件为MATLAB2007。 度明显好于其他方法。10次分类任务，DISRS算法的。 对于数值型数据集，首先进行离散化并构造等 价关系。 若两个样本在所有属性上取值一样，那么 这两个样本就为一类，否则不是一类。 而在离散化 过程中，避免不了信息流失，而这恰恰是当今研究 的热点。 本算法通过定义一个距离参数，考虑某两 个样本在属性上的相似程度。 如果两个样本之间 距离小于阈值，则这两个样本就可以聚为一类，这 比经典粗糙集的理论显然更多地考虑了样本之间 的联系，避免大量信息的流失，从而提高了属性约 简的精度。 由于利用定理 ３ 去搜索决策表的全部约 简是一个 ＮＰ 问题，因此利用本文提出的辨识矩阵 的概念来构造一个启发式算法。 算法 辨识矩阵属性约简算法（ＤＩＳＲＳ）。 输入 （Ｕ，Ａ，Ｄ＝ ｛ｄ｝），阈值 θ ／ ／ θ 是用于算法 停止搜索的阈值。 输出 约简 ＲＥＤ。 １）计算正域 ＰＯＳＡ（Ｄ）。 ２）计算出关系矩阵 ＮＤ，即对于任意的样本 ｘｉ， ｘｊ∈Ｕ，若 ｄ（ ｘｉ ） ≠ｄ（ ｘｊ ），令 ＮＤ（ ｉ，ｊ） ＝ ０， 否则，令 ＮＤ（ｉ，ｊ）＝ １。 ３）∀ａｌ∈Ａ，计算可辨识矩阵 Ｎｌ，对于任意 ｘｉ∈ ＰＯＳＡ （ Ｄ） 和任意 ｘｊ ∈ Ｕ， 当 ＮＤ （ ｉ， ｊ） ＝ ０ 时， 若 ｆ ｌ（ｘｉ）－ｆ ｌ（ｘｊ） ＞ε，令 Ｎｌ（ｉ，ｊ） ＝ １，否则令 Ｎｌ（ ｉ，ｊ） ＝ ０；当 ＮＤ（ｉ，ｊ）＝ １，令 Ｎｌ（ｉ，ｊ）＝ ０。 ４）计算 ＮＡ ＝∪Ｎｌ，ＲＥＤ←Ａ。 ５）∀ａｌ∈Ａ，计算 Ｎ｛ｒｅｄ－ａｌ ｝ 和 ｓｕｍ（Ｎ｛ｒｅｄ－ａｌ ｝ ），其中 ｓｕｍ（Ｎ｛ｒｅｄ－ａｌ ｝ ）表示对矩阵 Ｎ｛ｒｅｄ－ａｌ ｝的行列求和。 ６） 选 择 满 足 ｓｕｍ （ Ｎ｛ｒｅｄ－ａｋ ｝ ） ＝ ｍａｘ ｉ （ ｓｕｍ （Ｎ｛ｒｅｄ－ａｉ ｝ ））的 ａｋ，令 ＲＥＤ←｛Ａ－ａｋ｝。 ７）如果（ｓｕｍ（ＮＡ ）－ｓｕｍ（Ｎｒｅｄ ）） ／ Ｕ ＜θ，输出约 简 ＲＥＤ。 否则，转到 ５）。 了更好地理解所提出的算法，下面给出该算法 的流程图，如图 １。 ３ 实验分析 为了验证算法的有效性，从一些文献中选出 ４ 个相关的属性约简方法与本文所提的算法作比较。 这 ４ 个算法分别是经典粗糙集算法（ＦＣＭＲＳ） ［１］ 、邻 域粗糙集算法（ＮＢＲＳ） ［５］ 、邻域粗糙信息测度算法 （ＮＢＩＭ ） ［８］以 及 自 适 应 邻 域 粗 糙 集 模 型 （ＡＰＴＮＢ） ［７］ 。 本实验主要从算法选择的属性数目 和相应的分类精度两个方面进行比较。 计算机运 行的环境参数为：奔腾双核，ＣＰＵ Ｅ５２００ １．９０ ＧＨｚ， ＲＡＭ ４．０ ＧＢ，软件为 ＭＡＴＬＡＢ ２００７。 图 １ 属性约简算法流程图 Ｆｉｇ． １ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ 本实验采用 Ｋ 近邻（ＫＮＮ，Ｋ ＝ ３）和支持向量机 （ＲＢＦ⁃ＳＶＭ）分类器来评估这些属性约简算法的优 劣，ＲＢＦ⁃ＳＶＭ 分类器中参数采用默认值。 数据的分 类精度是基于十折交叉验证方法计算的。 从 ＵＣＩ 数据集中选择了 ５ 个数值型的数据集，其属性和分 类信 息 描 述 如 表 ３ 所 示。 在 本 文 所 提 的 算 法 （ＤＩＳＲＳ） 中，停止搜索的阈值 θ 设置为 θ ＝ ０． ００５。 为了说明该算法的有效性和可行性，首先对各个数 据集进行了属性约简，选取约简数据的最高分类精 度所对应的属性数目进行比较，具体结果如表 ４ 所 示，其中 ε 列表示对应数据约简后所取得的最高分 类精度的相似度阈值的取值。 表 ５ 和表 ６ 分别给出 了各个数据集属性约简前后的分类精度。 表 ３ 数据描述 Ｔａｂｌｅ ３ Ｄａｔａ ｉｎｆｏｒｍａｔｉｏｎ 序号 Ｄａｔａ ｓｅｔｓ Ｓａｍｐｌｅｓ Ｎｕｍｅｒｉｃａｌ Ｃｌａｓｓｅｓ １ Ｇｌａｓｓ ２１４ １０ ６ ２ Ｃｏｌｏｎ ６２ １ ２２４ ２ ３ Ｗｉｎｅ １７８ １３ ３ ４ Ｗｄｂｃ ５６９ ３０ ２ ５ Ｐｒｏｓｔａｔｅ １０２ １２ ６２５ ２ 从表 ４ 中可以看出，这 ５ 种属性约简方法都能 够有效地对数据集进行属性约简。 ＦＣＭＲＳ 算法选 取的属性数目最少，ＤＩＳＲＳ 算法次之。 表 ５ 和表 ６ 表明，ＤＩＳＲＳ 算法的分类精度最高，ＦＣＭＲＳ 算法的 分类精度最低。 同时，ＤＩＳＲＳ 算法所对应的分类精 度明显好于其他方法。 １０ 次分类任务，ＤＩＳＲＳ 算法 ·３７４· 智 能 系 统 学 报 第 １２ 卷