.500. 智能系统学报 第11卷 表2约简变化与约简传承性比较 Table 2 Comparison of Reduct change and Reduct inheritance rate NewObject Case Red Red IR Red, Red IR Rede Red IR 21001 1) cact C2C1 1c2c3 C2C1 0.5 c3ca C3CAC1 1 10104 ① C2C1 C2C1 1 C2C3 C2C3 1 C3C4 C3C4 1 01012 ② C2Ci C2Ct 1 C2C3 C2C3 1 C3ca C3C4 1 02111 ② czc1 c2c 1 C2C3 C2C3 1 C3c4 c3caC1 1 01112 ③ C2C1 CaCt 1 C2C3 C2C1 0.5 C3C4 C3C4CI 1 01121 ④ C2C1 c2CiC3 1 C2C3 C2C3C1 1 C3C4 csea 1 合计 平均传承率 平均传承率 0.83 平均传承率 1 3实验验证 据集进行实验。每个数据集仅有1个决策属性。人 工数据集Datasetl每个属性值为1~5；而人工数据 为了评价所提出的增量式约简算法效率和约简 集Dataset2.每个属性值为1~9。表3描述了6个数 传承性，使用Windows7操作系统，2.4GHz处理器 据集特性。原始数据集的50%作为基本数据集，剩 和16GB内存的计算机和Visual C#2012实现了相 下50%数据集的20%、40%、60%、80%和100%作为 关实验。由于所提出的约简算法和经典的约简算法 5个增量数据集，非增量式属性约简算法(NIAR)、 仅能够处理离散型属性，先采用Rosetta软件(ht- 面向单个属性的增量式属性约简算法(SIAR)和面 tp:/www.lcb.uu.se/tools/rosetta)填充缺省值，并将 向成组数据集的属性增量式约简算法(GIAR)实验 数值型属性连续值离散化：然后，分别在4个来自 结果如图1所示。 UCI Repository机器学习公共数据集和2个人工数 105 10 103 102 10 一一 -----0 10 0- NIAR 10 -B-SIRA 一NIAR 10 GIAR 寺耀 10 10 8 100合8 10 爱 10 0…0⑨…0 1 10 2 3 5 3 4 2 3 4 增量数据集 增量数据集 增量数据巢 (a)Chess (b)mushroom (c)nursery 10 10 10 10 …0…00 104 10 -NIAR …o…GAR 10 。&S …0…0…0 。縱 10 10 … 3 4 5 2 3 3 3 3 4 5 增量数据集 增量数据集 增量数据集 (d)Connect (e)Dataset I (f)Dataset 2 图1增量式约简算法和非增量式约简算法运行时间比较 Fig.I Comparison of incremental and non-incremental Reduction algorithms on running time 由于面向单个属性的增量式约简算法(SLAR) 时间更长，而GLAR算法的运行时间明显少于NIAR 对大规模数据集运行时间太长，图1(e)-(f)未标 算法，特别对于较大数据集，算法的效果越明显。实 出。从图1可以看出，SIAR算法比GAR算法运行 验结果表明，所提出的面向成组对象集的增量式约表 ２ 约简变化与约简传承性比较 Ｔａｂｌｅ ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｃｈａｎｇｅ ａｎｄ Ｒｅｄｕｃｔ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ＮｅｗＯｂｊｅｃｔ Ｃａｓｅ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ２１００１ １） ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ１ ０．５ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ １０１０４ ① ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ １ ０１０１２ ② ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ １ ０２１１１ ② ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ ０１１１２ ③ ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ１ ０．５ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ ０１１２１ ④ ｃ２ ｃ１ ｃ２ ｃ１ ｃ３ １ ｃ２ ｃ３ ｃ２ ｃ３ ｃ１ １ ｃ３ ｃ４ ｃ３ ｃ４ １ 合计 平均传承率 １ 平均传承率 ０．８３ 平均传承率 １ ３ 实验验证 为了评价所提出的增量式约简算法效率和约简 传承性，使用 Ｗｉｎｄｏｗｓ ７ 操作系统，２．４ ＧＨｚ 处理器 和 １６ ＧＢ 内存的计算机和 Ｖｉｓｕａｌ Ｃ＃２０１２ 实现了相 关实验。 由于所提出的约简算法和经典的约简算法 仅能够处理离散型属性，先采用 Ｒｏｓｅｔｔａ 软件（ ｈｔ⁃ ｔｐ： ／ ／ ｗｗｗ．ｌｃｂ．ｕｕ．ｓｅ ／ ｔｏｏｌｓ／ ｒｏｓｅｔｔａ） 填充缺省值，并将 数值型属性连续值离散化；然后，分别在 ４ 个来自 ＵＣＩ Ｒｅｐｏｓｉｔｏｒｙ 机器学习公共数据集和 ２ 个人工数 据集进行实验。 每个数据集仅有 １ 个决策属性。 人 工数据集 Ｄａｔａｓｅｔ１ 每个属性值为 １ ～ ５；而人工数据 集 Ｄａｔａｓｅｔ２ 每个属性值为 １ ～ ９。 表 ３ 描述了 ６ 个数 据集特性。 原始数据集的 ５０％作为基本数据集，剩 下 ５０％数据集的 ２０％、４０％、６０％、８０％和 １００％作为 ５ 个增量数据集，非增量式属性约简算法（ＮＩＡＲ）、 面向单个属性的增量式属性约简算法（ ＳＩＡＲ） 和面 向成组数据集的属性增量式约简算法（ＧＩＡＲ）实验 结果如图 １ 所示。 图 １ 增量式约简算法和非增量式约简算法运行时间比较 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｉｎｃｒｅｍｅｎｔａｌ ａｎｄ ｎｏｎ－ｉｎｃｒｅｍｅｎｔａｌ Ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｒｕｎｎｉｎｇ ｔｉｍｅ 由于面向单个属性的增量式约简算法（ ＳＩＡＲ） 对大规模数据集运行时间太长，图 １（ ｅ） －（ ｆ） 未标 出。 从图 １ 可以看出，ＳＩＡＲ 算法比 ＧＩＡＲ 算法运行 时间更长，而 ＧＩＡＲ 算法的运行时间明显少于 ＮＩＡＲ 算法，特别对于较大数据集，算法的效果越明显。 实 验结果表明，所提出的面向成组对象集的增量式约 ·５００· 智 能 系 统 学 报 第 １１ 卷