【知识工程】弱标记不完备决策系统的增量式属性约简算法

第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0L:10.11992tis.202001017 弱标记不完备决策系统的增量式属性约简算法 程龙2，钱文彬2，王映龙，胡剑锋3 (1.江西农业大学计算机与信息工程学院，江西南昌330045：2.江西农业大学软件学院，江西南昌330045,3.江 西科技学院信息技术研究所，江西南昌330098) 摘要：在许多现实应用领域中，由于数据标注代价昂贵，且数据往往呈现动态变化，因此存在大量弱标记的不 完备数据。针对上述复杂应用场景，本文以粒计算理论为基础，从区分性视角给出不完备数据的区分对概念， 同时给出属性相对重要度的度量方法，并设计面向弱标记不完备决策系统的属性约简算法。该算法能在迭代 过程中不断缩减搜索空间.提高属性约简效率：并根据实例的动态变化情况，分析属性约简的动态更新机制： 在此基础上，设计了半监督条件下的增量式属性约简算法。最后，通过实验验证了算法的可行性和有效性。 关键词：属性约简；粗糙集；区分对；混合数据：增量学习；半监督学习；相对重要度：动态数据 中图分类号：TP391 文献标志码：A文章编号：1673-4785(2020)06-1079-12 中文引用格式：程龙，钱文彬，王映龙，等.弱标记不完备决策系统的增量式属性约简算法.智能系统学报，2020,15(6)： 1079-1090. 英文引用格式：CHENG Long,QIAN Wenbin,.WANG Yinglong,ctal.An incremental attribute reduction algorithm for incom- plete decision system with weak labeling[J].CAAI transactions on intelligent systems,2020,15(6):1079-1090. An incremental attribute reduction algorithm for incomplete decision system with weak labeling CHENG Long2,QIAN Wenbin2,WANG Yinglong',HU Jianfeng' (1.School of Computer and Information Engineering,Jiangxi Agricultural University,Nanchang 330045,China;2.School of Soft- ware,Jiangxi Agricultural University,Nanchang 330045,China;3.Institute of Information Technology,Jiangxi University of Tech- nology,Nanchang 330098,China) Abstract:Due to the high cost of data annotation and dynamic change of data,many practical applications have a lot of incomplete data with weak labeling.In view of the above complex scenarios,based on the theory of granular computing, the concept of discernibility pairs of incomplete data is proposed and provides a measurement method for the relative importance of attributes.The attribute reduction algorithm is designed for an incomplete decision system with weak la- beling,which can reduce the search space and improve the efficiency of attribute reduction.Besides,the dynamic updat- ing mechanism of attribute reduction is analyzed based on the dynamic change of instances.In this study,an increment- al attribute reduction algorithm is designed under a semi-supervised scene,and the experimental results show the feasib- ility and effectiveness of the proposed algorithm. Keywords:attribute reduction;rough set;discernibility pair;mixed data;incremental learning:semi-supervised learn- ing:relative importance;dynamic data 粗糙集理论是一种有效的数据分析方法， 主要用于处理不确定、不一致和模糊的数据， 收稿日期：2020-01-09. 基金项目：国家自然科学基金项目(61966016)：江西省自然科 已被广泛地应用于知识发现、数据挖掘和机器学 学基金项日(20192BAB207018):江西省教育厅科学 习等领域。属性约简是粗糙集理论的重要研究内 技术研究项目(G切180200). 通信作者：钱文彬.E-mail:qianwenbinl027@126.com 容之一，它旨在保持原属性集区分能力不变的情

DOI: 10.11992/tis.202001017 弱标记不完备决策系统的增量式属性约简算法 程龙1,2，钱文彬1,2，王映龙1 ，胡剑锋3 （1. 江西农业大学 计算机与信息工程学院，江西 南昌 330045; 2. 江西农业大学 软件学院，江西 南昌 330045; 3. 江 西科技学院 信息技术研究所，江西 南昌 330098） 摘 要：在许多现实应用领域中，由于数据标注代价昂贵，且数据往往呈现动态变化，因此存在大量弱标记的不 完备数据。针对上述复杂应用场景，本文以粒计算理论为基础，从区分性视角给出不完备数据的区分对概念， 同时给出属性相对重要度的度量方法，并设计面向弱标记不完备决策系统的属性约简算法。该算法能在迭代 过程中不断缩减搜索空间，提高属性约简效率；并根据实例的动态变化情况，分析属性约简的动态更新机制； 在此基础上，设计了半监督条件下的增量式属性约简算法。最后，通过实验验证了算法的可行性和有效性。 关键词：属性约简；粗糙集；区分对；混合数据；增量学习；半监督学习；相对重要度；动态数据 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)06−1079−12 中文引用格式：程龙, 钱文彬, 王映龙, 等. 弱标记不完备决策系统的增量式属性约简算法 [J]. 智能系统学报, 2020, 15(6): 1079–1090. 英文引用格式：CHENG Long, QIAN Wenbin, WANG Yinglong, et al. An incremental attribute reduction algorithm for incom￾plete decision system with weak labeling[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1079–1090. An incremental attribute reduction algorithm for incomplete decision system with weak labeling CHENG Long1,2 ，QIAN Wenbin1,2 ，WANG Yinglong1 ，HU Jianfeng3 (1. School of Computer and Information Engineering, Jiangxi Agricultural University, Nanchang 330045, China; 2. School of Soft￾ware, Jiangxi Agricultural University, Nanchang 330045, China; 3. Institute of Information Technology, Jiangxi University of Tech￾nology, Nanchang 330098, China) Abstract: Due to the high cost of data annotation and dynamic change of data, many practical applications have a lot of incomplete data with weak labeling. In view of the above complex scenarios, based on the theory of granular computing, the concept of discernibility pairs of incomplete data is proposed and provides a measurement method for the relative importance of attributes. The attribute reduction algorithm is designed for an incomplete decision system with weak la￾beling, which can reduce the search space and improve the efficiency of attribute reduction. Besides, the dynamic updat￾ing mechanism of attribute reduction is analyzed based on the dynamic change of instances. In this study, an increment￾al attribute reduction algorithm is designed under a semi-supervised scene, and the experimental results show the feasib￾ility and effectiveness of the proposed algorithm. Keywords: attribute reduction; rough set; discernibility pair; mixed data; incremental learning; semi-supervised learn￾ing; relative importance; dynamic data 粗糙集理论[1-2] 是一种有效的数据分析方法， 主要用于处理不确定、不一致和模糊的数据[3-4] ， 已被广泛地应用于知识发现、数据挖掘和机器学 习等领域。属性约简是粗糙集理论的重要研究内 容之一，它旨在保持原属性集区分能力不变的情 收稿日期：2020−01−09. 基金项目：国家自然科学基金项目 (61966016)；江西省自然科 学基金项目 (20192BAB207018)；江西省教育厅科学 技术研究项目 (GJJ180200). 通信作者：钱文彬. E-mail：qianwenbin1027@126.com. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020

·1080· 智能系统学报 第15卷 况下，剔除不重要或冗余的属性5。由于属性约 变化后快速更新近似集合。文献[20]提出了一种 简的结果往往不是唯一的，找到数据所有约简的 基于知识粒度模型的动态属性约简算法，在实例 结果，已经被证明是一个NP-hard问题。因此在 变化后动态更新属性约简集。文献[21]提出了 实际应用中通常采用启发式算法处理大规模数 种不完备动态属性约简算法，该算法在不完备决 据，获取满足知识发现要求的属性约简结果。 策系统中单个实例变化后动态获取新的属性约简 然而，在众多现实应用领域中存在大量的高 结果集。上述研究都是针对所有实例均有标记的 维复杂数据。并且在数据采集阶段，由于采集成 数据，目前对弱标记数据的增量式属性约简研究 本和技术的限制，导致这些高维数据往往存在缺 较少。为此，有效地利用无标记数据来增强属性 失。同时，给这些数据进行类别标注，需要耗费 约简结果，并在保证分类精度前提下动态更新属 大量的人力资源，并且利用经典粗糙集无法直接 性约简结果，已成为了当前亟待解决的问题。 处理不完备数据。针对上述问题研究人员引入容 针对上述问题，本文提出了弱标记不完备数 差关系和限制容差关系等，拓展了经典粗糙集的 据的区分对概念，给出了属性的相对重要度的度 应用12]，但这些扩展的关系模型难以直接处理 量方法。并以此为基础，设计了启发式的半监督 含有连续型的不完备混合数据。同时，由于在实 属性约简算法，算法在每次迭代过程中能剔除相 际应用中，这些高维数据通常仅包含少量已标注 对冗余的属性和当前属性约简集已能够区分的区 的数据。若仅利用带标记的数据进行属性约简， 分对，算法的搜索空间显著缩减。同时，根据数 约简结果不能有效反映数据的分布，且分类性能 据中实例的动态变化情况，给出属性约简集的动 较弱。 态更新机制，并通过实例分析详细说明动态属性 弱监督属性约简旨在有效利用无标记数据来 约简算法的计算过程。最后，采用来自UCI的真 增强属性约简的有效性，从而提高学习模型的分 实数据集，进一步验证了算法的高效性和可行性。 类性能。近年来，弱监督属性约简引起了许多研 究人员的关注和研究。文献[13]针对弱标记的符 1基本知识 号型数据，在区分对的基础上，利用有监督学习 定义1四元组IS=是一个信息 框架和无监督学习框架，构造相对应的启发式半 系统，其中U表示实例的非空有限集合，称为论 监督属性约简算法。文献[14]基于粗糙集理论和 域；A表示属性的非空有限集合V=UVa,V。是属 信息熵的概念，在对无标记数据进行部分标注 性a∈A所有可能值的集合；f表示U×A→V,是 后，设计了一种基于信息嫡的半监督特征选择算 一个信息函数，它为每个实例的每一个属性赋予 法。文献[15]将粗糙集理论和集成学习框架相结 一个值，即YaeA,x∈U,fx,a)eVao 合，利用有标记的数据训练基分类器对无标记的 给定信息系统，如果至少有一个属性a∈A使 数据进行标注，扩充有标记的数据。文献[16)]提 得V。含有缺失值，其中缺失值用”*”表示，此时 出了一种基于流形正则化的半监督特征选择算 该系统称为不完备信息系统，用S= 法，通过最大化不同类别之间的间距对特征的重 表示。 要性进行度量分析。文献[1刀提出了一种半监督 定义2在不完备信息系统IS= 特征选择算法，算法通过组合半监督散点，有效 中，有A=AUA,其中Aa表示离散型属性集，A 利用大量未标记的视频数据中的信息来区分目标 表示连续型属性集，对于任意B二A,关于属性子 类别。上述这些方法为弱标记数据的属性约简， 集B的区分对定义为DisUL(B,U)={l。Hp∈ 提供了有效的解决方案。 B,对H有 另外，在大数据时代，许多数据随着时间的推 3p∈A,lf,p)-fx,p)川>6 移而动态变化。在这种复杂应用场景中，传统的 V3peAa,fx,p)≠f(x,p) 属性约简算法在处理这些动态数据时，将会产生 Af(x,P)+*Af(x,P)≠* 大量重复计算，无法快速更新属性约简结果。近 给定的不完备信息系统IS=,对 年来，许多学者对动态属性约简算法进行了大量 YBSA,Disu(B,U表示属性集B重要度，其物理 的研究。文献[18]提出了一种基于信息嫡的组增 含义为属性集B的区分度。属性集区分的实例 量式属性约简算法，在动态增加一组实例后，快 对的数量越多，该属性集越重要。由定义可知 速更新属性约简结果。文献[19]采用一种复合粗 ∈DisUL(B,U)满足自反性、对称性，因此在 糙集模型，处理动态的不完备数据，在数据动态 考虑实例之间的区分对后，则不再重复

况下，剔除不重要或冗余的属性[5-6]。由于属性约 简的结果往往不是唯一的，找到数据所有约简的 结果，已经被证明是一个 NP-hard 问题。因此在 实际应用中通常采用启发式算法处理大规模数 据，获取满足知识发现要求的属性约简结果[7-9]。 然而，在众多现实应用领域中存在大量的高 维复杂数据。并且在数据采集阶段，由于采集成 本和技术的限制，导致这些高维数据往往存在缺 失。同时，给这些数据进行类别标注，需要耗费 大量的人力资源，并且利用经典粗糙集无法直接 处理不完备数据。针对上述问题研究人员引入容 差关系和限制容差关系等，拓展了经典粗糙集的 应用[10-12] ，但这些扩展的关系模型难以直接处理 含有连续型的不完备混合数据。同时，由于在实 际应用中，这些高维数据通常仅包含少量已标注 的数据。若仅利用带标记的数据进行属性约简， 约简结果不能有效反映数据的分布，且分类性能 较弱。 弱监督属性约简旨在有效利用无标记数据来 增强属性约简的有效性，从而提高学习模型的分 类性能。近年来，弱监督属性约简引起了许多研 究人员的关注和研究。文献 [13] 针对弱标记的符 号型数据，在区分对的基础上，利用有监督学习 框架和无监督学习框架，构造相对应的启发式半 监督属性约简算法。文献 [14] 基于粗糙集理论和 信息熵的概念，在对无标记数据进行部分标注 后，设计了一种基于信息熵的半监督特征选择算 法。文献 [15] 将粗糙集理论和集成学习框架相结 合，利用有标记的数据训练基分类器对无标记的 数据进行标注，扩充有标记的数据。文献 [16] 提 出了一种基于流形正则化的半监督特征选择算 法，通过最大化不同类别之间的间距对特征的重 要性进行度量分析。文献 [17] 提出了一种半监督 特征选择算法，算法通过组合半监督散点，有效 利用大量未标记的视频数据中的信息来区分目标 类别。上述这些方法为弱标记数据的属性约简， 提供了有效的解决方案。 另外，在大数据时代，许多数据随着时间的推 移而动态变化。在这种复杂应用场景中，传统的 属性约简算法在处理这些动态数据时，将会产生 大量重复计算，无法快速更新属性约简结果。近 年来，许多学者对动态属性约简算法进行了大量 的研究。文献 [18] 提出了一种基于信息熵的组增 量式属性约简算法，在动态增加一组实例后，快 速更新属性约简结果。文献 [19] 采用一种复合粗 糙集模型，处理动态的不完备数据，在数据动态 变化后快速更新近似集合。文献 [20] 提出了一种 基于知识粒度模型的动态属性约简算法，在实例 变化后动态更新属性约简集。文献 [21] 提出了一 种不完备动态属性约简算法，该算法在不完备决 策系统中单个实例变化后动态获取新的属性约简 结果集。上述研究都是针对所有实例均有标记的 数据，目前对弱标记数据的增量式属性约简研究 较少。为此，有效地利用无标记数据来增强属性 约简结果，并在保证分类精度前提下动态更新属 性约简结果，已成为了当前亟待解决的问题。 针对上述问题，本文提出了弱标记不完备数 据的区分对概念，给出了属性的相对重要度的度 量方法。并以此为基础，设计了启发式的半监督 属性约简算法，算法在每次迭代过程中能剔除相 对冗余的属性和当前属性约简集已能够区分的区 分对，算法的搜索空间显著缩减。同时，根据数 据中实例的动态变化情况，给出属性约简集的动 态更新机制，并通过实例分析详细说明动态属性 约简算法的计算过程。最后，采用来自 UCI 的真 实数据集，进一步验证了算法的高效性和可行性。 1 基本知识 IS = U A V = ∪ a∈A Va Va a ∈ A f U × A → V ∀a ∈ A x ∈ U f(x,a) ∈ Va 定义 1 四元组 是一个信息 系统，其中 表示实例的非空有限集合，称为论 域； 表示属性的非空有限集合 ， 是属 性 所有可能值的集合； 表示 ，是 一个信息函数，它为每个实例的每一个属性赋予 一个值，即 ， ， 。 a ∈ A Va ” ∗ ” IIS = 给定信息系统，如果至少有一个属性 使 得 含有缺失值，其中缺失值用 表示，此时 该系统称为不完备信息系统，用 表示。 IIS = A = Ad ∪ Ar Ad Ar B ⊆ A B DisUL(B,U 2 ) = { } ∀p ∈ B, ∀ 定义 2 在不完备信息系统 中，有 ，其中 表示离散型属性集， 表示连续型属性集，对于任意 ，关于属性子 集 的区分对定义为 。 对 有    ∃p ∈ Ar ,| f(xi , p)− f(xj , p) | > δ ∨∃p ∈ Ad, f(xi , p) , f(xj , p) ∧f(xi , p) , ∗ ∧ f(xj , p) , ∗ IIS = ∀B ⊆ A |DisUL(B,U 2 )| B B ∈ DisUL(B,U 2 ) 给定的不完备信息系统 ，对 ， 表示属性集 重要度，其物理 含义为属性集 的区分度。属性集区分的实例 对的数量越多，该属性集越重要。由定义可知 满足自反性、对称性，因此在 考虑实例之间的区分对 后，则不再重复 ·1080· 智 能 系 统 学 报 第 15 卷

第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1081· 考虑区分对。 U,根据定义4有Dis(BUa,U)≥Dis(B,U)。从 定义3对于给定信息系统IS=, 而可证Dis(BUa,U2)+Disw(BUa,U)≥Dis(B,UP)+ 令A=CUD,其中子集C是条件属性集合，D是 DisM(B,UP),即Dis(BUa,U≥Dis(B,U)。 决策属性集合，又称四元组为决策系统，用DS=表示。 ,设U=LUM,其中L表示有标记 对于给定决策系统DS=,如果 实例的集合，M表示无标记实例的集合，RSC是 至少有一个属性c∈C使得V。含有缺失值，其中 一个属性约简，当且仅当R满足： 缺失值用”*”表示。此时，该系统称为不完备决 1)Dis(R,U2)=Dis(C,U2); 策系统，用DS=表示。 2)VceR,Dis(R-c,U2)≠Dis(C,UP)。 定义4给定不完备决策系统DS=,有Ca,C,SB,其中C4表示离散型属 ,设U=LUM,其中L表示有标记 性，C,表示连续型属性，设EU,对Yp∈ 实例的集合，M表示无标记实例的集合，并且 B、B≤C,D关于B的区分对定义为Dis(B,UP)= B≤C.对Hc∈C-B,则 (其中L表示有标记)，对V有 1)属性c相对于属性集合B的区分度 (3peC,lfxp)-fx,p川>) RSig(c,B,U2)= Dis(BUc,U2)-Dis(c.U2).B+O V]p∈Cdfx,p)+fxp) Dis(c,U儿，B=O f(x,p)≠*Afx,p)≠* 2)当RSig(c,B,U)=0时，则称属性c相对于 f(x,D)≠f(xiD) B是不必要的（相对冗余的）。 给定的不完备决策系统DS=, 如图1所示，利用Dis(BUc,U-Dis(c,U)|= 对YBcC,Dis(B,UP引表示属性集B的重要度，其 RSig(c,B,UP)计算属性c相对于属性集B的重要 物理含义为属性集B的区分度。属性集能区分 度时，仅需要在属性集B无法区分的区分对中， 的实例对的数量越多，则表明该属性集越重要。 搜索属性c能够区分的实例对。由于相对重要度 由于在现实应用中，在大量不完备数据中只 的引人，在算法的迭代过程中，可不断地剔除当 有少部分实例存在标记，若仅利用带标记的实例 前属性约简集已能够区分的实例对和相对冗余的 获取属性约简结果，由于无标记的实例未得到有 属性，使得算法的搜索空间不断缩减，避免了大 效的利用，使得属性约简结果较难反映数据的整 量的重复计算，从而有效地减少算法的计算时间。 体信息，分类算法难以学习有效的知识规则，导 致分类模型的分类性能较弱。为此，针对弱标记 Dis (B,U2) 不完备决策系统，设计有效的属性重性度量方法 显得尤为重要。本文在文献[8,13]的基础上，构 Dis(c,U) -RSig (C.B.U-) 造了面向弱标记不完备数据的属性重要性度量方法。 给定的不完备决策系统DS=, 若决策属性d存在缺失值。此时该系统称为弱标 图1属性C相对于属性集B的重要度 记不完备决策系统，用WIDS=表示。 Fig.1 Significance of attribute c with respect to B 定义5给定弱标记不完备决策系统WIDS= 性质2给定弱标记不完备决策系统WDS= ,设U=LUM,其中L表示有标记 ,设U=LUM,其中L表示有标记 实例的集合，M表示无标记实例的集合，属性集 实例的集合，M表示无标记实例的集合，并且 B二C的重要度定义为 R≤C是C的一个属性约简集有 Dis(B,L2+DisM(B,UL2),L≠O,M≠O Dis(B,U2)= Dis(B,L2),L≠O,M=0 1)RSig(c,R,U2)=0,VcEC-R; Dis(B.UL2),L=0,M 2)RSig(c,R-c,UP)≠0，Yc∈R。 性质1给定弱标记不完备决策系统WDS= 证明因为R二C是C的一个属性约简集， ,设U=LUM,其中L表示有标记 根据定义6有Dis(R,U)=Dis(C,U),对Yc∈C-R 实例的集合，M表示无标记实例的集合，对 RSig(c,R,U2)=Dis(c,U2)-Dis(c.U2)nDis(R,U2)= Va∈C-B满足： Dis(c,U2)-Dis(c,U2)nDis(c,U2)=0 Dis(BUa,U≥Dis(B,U) 证明了1)的充分性。 证明根据定义2可得DisM(BUa,UP)≥DisM(B, 若RSC是C的一个属性约简集，对Yc∈

。 IS = A = C ∪ D C D DS = 定义 3 对于给定信息系统 ， 令 ，其中子集 是条件属性集合， 是 决策属性集合，又称四元组为决策系统，用 表示。 DS = c ∈ C Vc ” ∗ ” IDS = 对于给定决策系统 ，如果 至少有一个属性 使得 含有缺失值，其中 缺失值用 表示。此时，该系统称为不完备决 策系统，用 表示。 IDS = Cd,Cr ⊆ B Cd Cr ∈ U 2 ∀p ∈ B B ⊆ C D B DisL(B,U 2 ) = L ∀ 定 义 4 给定不完备决策系统 ，有 ，其中 表示离散型属 性 ， 表示连续型属性，设 ，对 、 ， 关于 的区分对定义为 (其中 表示有标记)，对 有       (∃p ∈ Cr ,| f(xi , p)− f(xj , p)| > δ) ∨∃p ∈ Cd, f(xi , p) , f(xj , p) f(xi , p) , ∗ ∧ f(xj , p) , ∗    ∧ f(xi ,D) , f(xj ,D) IDS = ∀B ⊆ C |DisL(B,U 2 )| B B 给定的不完备决策系统 ， 对 ， 表示属性集 的重要度，其 物理含义为属性集 的区分度。属性集能区分 的实例对的数量越多，则表明该属性集越重要。 由于在现实应用中，在大量不完备数据中只 有少部分实例存在标记，若仅利用带标记的实例 获取属性约简结果，由于无标记的实例未得到有 效的利用，使得属性约简结果较难反映数据的整 体信息，分类算法难以学习有效的知识规则，导 致分类模型的分类性能较弱。为此，针对弱标记 不完备决策系统，设计有效的属性重性度量方法 显得尤为重要。本文在文献 [8,13] 的基础上，构 造了面向弱标记不完备数据的属性重要性度量方法。 IDS = d WIDS = 给定的不完备决策系统 ， 若决策属性 存在缺失值。此时该系统称为弱标 记不完备决策系统，用 表示。 WIDS = U = L∪ M L M B ⊆ C 定义 5 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，属性集 的重要度定义为 Dis(B,U 2 )=    DisL(B,L 2 )+DisM(B,UL2 ), L , Ø, M , Ø DisL(B,L 2 ), L , Ø, M = Ø DisM(B,UL2 ), L = Ø, M , Ø WIDS = U = L∪ M L M ∀a ∈ C − B 性质 1 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，对 满足： Dis(B∪a,U 2 ) ⩾ Dis(B,U 2 ) DisM(B∪a,U 2 证明 根据定义 2 可得 ) ⩾ DisM(B, U 2 ) DisL(B∪a,U 2 ) ⩾ DisL(B,U 2 ) DisL(B∪a,U 2 )+DisM(B∪a,U 2 ) ⩾ DisL(B,U 2 )+ DisM(B,U 2 ) Dis(B∪a,U 2 ) ⩾ Dis(B,U 2 ) ，根据定义 4 有 。从 而可证 ，即 。 WIDS = U = L∪ M L M R ⊆ C R 定义 6 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合， 是 一个属性约简，当且仅当 满足： Dis(R,U 2 )= Dis(C,U 2 1) ) ； ∀c ∈ R Dis(R−c,U 2 ) , Dis(C,U 2 2) ， )。 WIDS = U = L∪ M L M B ⊆ C ∀c ∈ C − B 定 义 7 给定弱标记不完备系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，并且 ，对 ，则 1) 属性 c 相对于属性集合 B 的区分度: RSig(c,B,U 2 ) = { |Dis(B∪c,U 2 )|−|Dis(c,U 2 ) |, B , Ø |Dis(c,U 2 )|, B = Ø RSig(c,B,U 2 ) = 0 c B 2) 当 时，则称属性 相对于 是不必要的 (相对冗余的)。 |Dis(B∪c,U 2 )|−|Dis(c,U 2 ) | = RSig(c,B,U 2 ) c B B c 如图 1 所示，利用 计算属性 相对于属性集 的重要 度时，仅需要在属性集 无法区分的区分对中， 搜索属性 能够区分的实例对。由于相对重要度 的引入，在算法的迭代过程中，可不断地剔除当 前属性约简集已能够区分的实例对和相对冗余的 属性，使得算法的搜索空间不断缩减，避免了大 量的重复计算，从而有效地减少算法的计算时间。 Dis (c,U2 ) Dis (B,U2 ) RSig (c,B,U2 ) 图 1 属性 c 相对于属性集 B 的重要度 Fig. 1 Significance of attribute c with respect to B WIDS = U = L∪ M L M R ⊆ C C 性质 2 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，并且 是 的一个属性约简集有 RSig(c,R,U 2 1) ) = 0， ∀c ∈ C −R ； RSig(c,R−c,U 2 2) ) , 0， ∀c ∈ R。 R ⊆ C C Dis(R,U 2 )= Dis(C,U 2 ) ∀c ∈ C −R RSig(c,R,U 2 ) =   Dis(c,U 2 )−Dis(c,U 2 )∩Dis(R,U 2 )    =   Dis(c,U 2 )−Dis(c,U 2 )∩Dis(c,U 2 )    = 0 证明 因为 是 的一个属性约简集， 根据定义 6 有 ，对 有： 证明了 1) 的充分性。 若 R ⊆ C 是 C 的一个属性约简集，对 ∀c ∈ 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1081·

·1082· 智能系统学报 第15卷 C-R,假设RSig(c,R,U)≠0，根据定义6有Dis(R, red=redUce,Pair'=Dis(ce,Pair,); U=Dis(C,U),根据定义7可知： C=C'Uck; RSig(c,R,U2)=Dis(c,U2)-Dis(c,U2)Dis(R,U2) Pair#1=Pair,-Pair∥别除当前属性集已经能区 =Dis(C.U)-Dis(C.U2)nDis(C.U)=0 分的区分对 与假设矛盾。证明了1)的必要性，同理可证2)。 C#1=C,-C/别除已加入属性约简集的属性 和相对冗余的属性 2弱标记不完备决策系统的属性约简 j=j+1} 基于属性重要度设计启发式属性约简算法， 4)对可能存在的冗余属性进行逆向剔除 被广泛地用于粗糙集理论的属性约简，传统的启 计算Pair=Dis(red,UP) 发式算法每次迭代时，每次将最重要的属性增加 对于Yck∈red,如果RSig(ck,red-ck,Pair)=0, 到属性约简集中，但是在迭代过程中无法剔除相 red red-cx 对冗余的属性。本文提出一种基于区分对的向前 5)输出属性约简集red 启发式属性约简算法，在每次迭代中，将相对于 2.2时间复杂度分析 当前属性约简集最重要的属性加入属性约简集 算法1的1)初始化变量：2)根据定义2和定 中，并剔除相对冗余属性和当前属性集已经能够 义4计算实例在属性集C上的区分对，其时间复 区分的实例对，快速缩减算法的搜索空间。 杂度为OU1C):3)是在性质2的基础上，采用相 对重要度为标准设计启发式算法，在迭代过程中 2.1属性约简算法 不断缩减算法的搜索空间，其时间复杂度为 算法1弱标记不完备决策系统属性约简算 法(WIDAR算法) oPair C小)对可能存在的冗余属性进行剔 输入弱标记不完备决策系统WIDS=; 输出属性约简集red。 3弱标记不完备决策系统的增量式 1)j=0,Pairj=0,Cj=C,C=0,Pair'=0, 属性约简 red=0; 在动态数据中使用传统的属性约简方法，往往 2)计算属性集C的区分对Pair=Dis(C,UP) 无法快速获取约简结果，而增量式属性约简算法能 3)while(Pair,l≠O) 有效地利用原约简结果，避免大量的重复计算。针 {对ck∈C,计算RSig(ck,red,Pair 对数据动态变化的情况，本节分析了数据动态变化 当RSig(c,red,Pair)=0,ck相对red为冗余属 对实例区分对的影响，图2给出了属性约简的增量 性，C'=C'Uc; 式更新机制，并针对动态数据中的实例变化情况， C=argmax(RSig(ce,red,Pair )ICk EC-C); 算法2设计了属性约简增量式更新算法。 原不完备信息系统 U,属性约简集：red 删除实例 新增实例 更新Dis,(C) 更新Disw(C 更新Dis,(C 更新Disw(C 存在冗余属性 维持最大区分度 Y 更新约简结 维持原约简 更新原约简 果：redd 结果：red 结果：reda 图2属性约简的增量式更新机制 Fig.2 Incremental updating mechanism of attribute reduction

C −R RSig(c,R,U 2 ) , 0 Dis(R, U 2 ) = Dis(C,U 2 ) ，假设 ，根据定义 6 有 ，根据定义 7 可知： RSig(c,R,U 2 )= |Dis(c,U 2 )−Dis(c,U 2 )∩Dis(R,U 2 )| = |Dis(c,U 2 )−Dis(c,U 2 )∩Dis(C,U 2 )| = 0 与假设矛盾。证明了 1) 的必要性，同理可证 2)。 2 弱标记不完备决策系统的属性约简 基于属性重要度设计启发式属性约简算法， 被广泛地用于粗糙集理论的属性约简，传统的启 发式算法每次迭代时，每次将最重要的属性增加 到属性约简集中，但是在迭代过程中无法剔除相 对冗余的属性。本文提出一种基于区分对的向前 启发式属性约简算法，在每次迭代中，将相对于 当前属性约简集最重要的属性加入属性约简集 中，并剔除相对冗余属性和当前属性集已经能够 区分的实例对，快速缩减算法的搜索空间。 2.1 属性约简算法 算法 1 弱标记不完备决策系统属性约简算 法 (WIDAR 算法) WIDS = 输入 弱标记不完备决策系统 ； 输出 属性约简集 red。 j = 0 Pairj = Ø Cj = C C ′ = Ø Pair′ = Ø red = Ø 1 ) ， ， ， ， ， ； C Pairj = Dis(C,U 2 2) 计算属性集 的区分对 ) ; while(|Pairj 3) | , 0) ck ∈ Cj RSig(ck {对 ,计算 ,red,Pairj) : RSig(ck ,red,Pairj) = 0 ck red C ′=C ′ ∪ck 当 ， 相对 为冗余属 性， ; ck= argmax{RSig(ck ,red,Pairj )|ck ∈ Cj −C ′ }; red = red∪ck Pair′ = Dis(ck ,Pairj , ) ; C ′ = C ′ ∪ck ; Pairj+1 = Pairj −Pair′ //剔除当前属性集已经能区 分的区分对 Cj+1 = Cj −C ′ //剔除已加入属性约简集的属性 和相对冗余的属性 j = j+1 ;} 4) 对可能存在的冗余属性进行逆向剔除 Pair = Dis(red,U 2 计算 ) ∀ck ∈ red RSig(ck ,red−ck ,Pair) = 0 red = red−ck 对 于 , 如 果 ， ; 5) 输出属性约简集 red 2.2 时间复杂度分析 C O(|U| 2 |C|) O (∑ |red| j=0 |Pairj ||Cj | ) O(|Pair||red| 2 ) 算法 1 的 1) 初始化变量；2) 根据定义 2 和定 义 4 计算实例在属性集 上的区分对，其时间复 杂度为 ；3) 是在性质 2 的基础上，采用相 对重要度为标准设计启发式算法，在迭代过程中 不断缩减算法的搜索空间，其时间复杂度为 ；4) 对可能存在的冗余属性进行剔 除，时间复杂度为 。 3 弱标记不完备决策系统的增量式 属性约简 在动态数据中使用传统的属性约简方法，往往 无法快速获取约简结果，而增量式属性约简算法能 有效地利用原约简结果，避免大量的重复计算。针 对数据动态变化的情况，本节分析了数据动态变化 对实例区分对的影响，图 2 给出了属性约简的增量 式更新机制，并针对动态数据中的实例变化情况， 算法 2 设计了属性约简增量式更新算法。 删除实例 新增实例 存在冗余属性 维持最大区分度 原不完备信息系统 U，属性约简集：red 更新 DisL (C) 更新 DisM (C) 更新 Dis 更新 DisM (C) L (C) 维持原约简 结果：red N Y Y N 更新约简结 果：reddel 更新原约简 结果：redad 图 2 属性约简的增量式更新机制 Fig. 2 Incremental updating mechanism of attribute reduction ·1082· 智 能 系 统 学 报 第 15 卷

第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1083· 3.1增量式属性约简算法 表1弱标记不完备决策系统 算法2弱标记不完备决策系统的增量式约 Table 1 Incomplete decision system with weak labeling 简算法(WIDIAR算法) U C1 C2 C3 D b 0.71 1 输入弱标记不完备决策系统WDS=,U=LUM,删除的实例△Ue=△MaeU 0 b a 0.80 △Lue,增加的实例△Ud=△MaU△Lad,原属性约简 X4 b 0.65 结果red; b 0.72 输出属性约简结果red。 6 0.72 l)计算删除实例△U后存在的区分对Pairde; a a 0.77 2)对于Yc.∈red',red=red,如果满足条件： RSig(ck,red-c,Pair)=0,则根据定义7逆向剔除 根据表1详细描述算法1属性约简的具体 冗余属性，red'=red'-ck; 步骤：算法1中的1)变量初始化；2)计算关于属 3)计算增加的区分对△Pairad, 性集C的区分对，确定算法的搜索空间Pairo= 4)j=0,C'=red,C=C-C'; {Kx1,>,,,,};在 算法1的3)中第一次迭代时red=O、RSig(c1,red, △Paird=△Pairad; Pairo)=3 RSig(c2,red,Pairo)=2 RSig(ca,red,Pairo)= while(△Paird≠O): 2、RSig(c4,red,Pairo)=2,第一次迭代结束后，Pair1= {Vck E Cj,if(RSig(ck,red,Pairj)=0),C'=C'UC; {，,red={clo由于此时Pair≠0， ck=argmax(RSig(ck,red',△Paird)lc∈Cj-C"i 因此需进行第二次迭代，red={c},RSig(c2,red, red'=red'Uck.C'=C'Uck; Pair)=0,RSig(c3,red,Pair)=0,RSig(ca,red,Pair)=2, Pair'=Dis(c,APair); C=C-C,APair=APair -Pair'; 第2轮迭代结束后，Pair=0、red={c1,c4}循环结 束：算法1在4)中未发现冗余属性，最后输出属 j=j+1} 性约简结果red={c,ca}。 5)对可能存在的冗余属性进行逆向剔除，计 为进一步详细说明算法2针对不同实例变化 算Pair=Dis(red',(U-△Uae)U△Ua));Yc∈red',如果 后对原属性约简结果产生的影响，下面首先分析 RSig(ck,red'-ck.Pair)=0,red'=red'-c&; 算法2的2)中实例动态删除情况。在数据中删 6)输出新的属性约简结果red。 除实例将存在6种情况：1)只删除有标记的实 3.2时间复杂度分析 例{x},对于Yc.∈red={c1,ca}有RSig(ck,red-Ck, 算法2中：1)计算删除实例后属性集red的 Pair)≠0，属性约简集保持不变red'={c,c:2)只 区分对，其时间复杂度为O(U-△Uae)red);2)对 删除有标记的实例{，有RSig(ca,red-c4,Pair)=0, 可能存在的冗余属性逆向删除，其时间复杂度为 此时c4相对于c为冗余属性，属性约简集更新为 O(U-△U)2red);3)计算由于增加实例△Uu而 red={c;3)只删除无标记的实例{x4,对Yc∈ 增加的区分对，其时间复杂度为OU-△U△U red={c,cal,RSig(c,red-ck,Pair)≠0，属性约简集保 IC):4)若原属性约简集red'无法维持最大区分 持不变red'={c1,ca:4)只删除无标记的实例{， 度，则需要在属性集C-C'中筛选属性加入属性 有RSig(ca,red-c4,Pair)=0,此时c4相对于c1为冗 余属性，属性约简集更新为red={c;5)同时删 约简集，其时间复杂度为O∑APairC:5)对 除有标记的实例{x}和无标记的实例{x},对 =0 可能存在的冗余属性进行别除，时间复杂度为 Yck∈red={c1,ca},RSig(ck,red-c,Pair)≠0，属性约 O(PairllredP)。 简集维持不变red={c1,ca;6)同时删除有标记的 实例{x}和无标记的实例{xl,有RSig(c,red-c, 4实例分析 Pair)=0,此时c1相对于c4为冗余属性，属性约简 集更新为red={ca}。 为进一步详细说明算法的流程。以表1中的 由于在许多现实动态场景中不仅存在数据删 弱标记不完备数据为例，进行分析说明。其中共 除还有数据动态增加的情况，为了进一步分析算 有6个实例和4个属性，U={1,2,3,x45,x6,x}为 法2的3)和4)的计算流程，在上述实例中若在原 实例集，C={c1,c2,c3,c4}为条件属性集，D为决策 始数据集中删除实例U={x,x,删除实例后属 属性，“*”表示缺失值，阈值6=01。 性约简集为red={ca},在此基础上，在数据中增

3.1 增量式属性约简算法 算法 2 弱标记不完备决策系统的增量式约 简算法 (WIDIAR 算法) WIDS = U = L∪ M ∆Ude = ∆Mde∪ ∆Lde ∆Uad = ∆Mad ∪∆Lad red 输入 弱标记不完备决策系统 ， ，删除的实例 ，增加的实例 ，原属性约简 结果 ； red 输出 属性约简结果 ′。 1) 计算删除实例 ∆Ude 后存在的区分对 Pairde； ∀ck ∈ red′ red′ = red RSig(ck ,red′ −ck ,Pairde) = 0 red′ = red′ −ck 2) 对于 ， ，如果满足条件： ，则根据定义 7 逆向剔除 冗余属性， ; 3) 计算增加的区分对 ∆Pairad; j = 0 C ′ = red′ Cj = C −C ′ 4) , , ; ∆Pairj ad = ∆Pairad; while(∆Pairj ad , 0) : ∀ck ∈ Cj if(RSig(ck ,red,Pairj) = 0) C ′=C ′ { ， ， ∪ck； ck= argmax{RSig(ck ,red′ ,∆Pairj ad)|ck ∈ Cj −C ′ }; red′ = red′ ∪ck ,C ′ = C ′ ∪ck ; Pair′ = Dis(ck ,∆Pairj ad); Cj+1 = C −C ′ ,∆Pairj+1 ad = ∆Pairj ad −Pair′ ; j = j+1 ;} Pair = Dis(red′ ,((U −∆Ude)∪∆Uad) 2 ) ∀ck ∈ red′ RSig(ck ,red′ −ck ,Pair) = 0 red′ = red′ −ck 5) 对可能存在的冗余属性进行逆向剔除，计 算 ; ,如果 ， ; red′ 6) 输出新的属性约简结果 。 3.2 时间复杂度分析 red O((U −∆Ude) 2 |red|) O((U −∆Ude) 2 |red| 2 ) ∆Ude O(|U −∆Ude||∆Uad| |C|) red′ C −C ′ O (∑ j i=0 |∆Pairi ad||Ci | ) O(|Pair||red′ | 2 ) 算法 2 中：1) 计算删除实例后属性集 的 区分对，其时间复杂度为 ；2) 对 可能存在的冗余属性逆向删除，其时间复杂度为 ；3) 计算由于增加实例 而 增加的区分对，其时间复杂度为 ；4) 若原属性约简集 无法维持最大区分 度，则需要在属性集 中筛选属性加入属性 约简集，其时间复杂度为 ；5) 对 可能存在的冗余属性进行剔除，时间复杂度为 。 4 实例分析 U = {x1, x2, x3, x4 x5, x6, x7} C = {c1, c2, c3, c4} D δ = 0.1 为进一步详细说明算法的流程。以表 1 中的 弱标记不完备数据为例，进行分析说明。其中共 有 6 个实例和 4 个属性， 为 实例集， 为条件属性集， 为决策 属性，“*”表示缺失值，阈值 。 表 1 弱标记不完备决策系统 Table 1 Incomplete decision system with weak labeling U c1 c2 c3 c4 D x1 a b * 0.71 1 x2 a * b 0.58 0 x3 a b a 0.80 1 x4 b a * 0.65 * x5 b a b 0.72 * x6 b * b 0.72 * x7 a b a 0.77 * C Pair0 = {,,,,} red = Ø RSig(c1,red, Pair0) = 3 RSig(c2,red,Pair0) = 2 RSig(c3,red,Pair0) = 2 RSig(c4,red,Pair0) = 2 Pair1 = { , } red = {c1} |Pair1| , 0 red = {c1} RSig(c2,red, Pair1) = 0 RSig(c3,red,Pair1) = 0 RSig(c4,red,Pair1) = 2 Pair2 = Ø red = {c1, c4} red = {c1, c4} 根据表 1 详细描述算法 1 属性约简的具体 步骤：算法 1 中的 1) 变量初始化；2) 计算关于属 性集 的区分对，确定算法的搜索空间 ； 在 算法 1 的 3) 中第一次迭代时 、 、 、 、 ，第一次迭代结束后， ， 。由于此时 ， 因此需进行第二次迭代， ， 、 、 ， 第 2 轮迭代结束后， 、 循环结 束；算法 1 在 4) 中未发现冗余属性，最后输出属 性约简结果 。 {x1} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck , Pair) , 0 red′ = {c1, c4} {x2} RSig(c4,red−c4,Pair) = 0 c4 c1 red′ = {c1} {x4} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck ,Pair) , 0 red′ = {c1, c4} {x7} RSig(c4,red−c4,Pair) = 0 c4 c1 red′ = {c1} {x1} {x4} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck ,Pair) , 0 red′ = {c1, c4} {x1} {x7} RSig(c1,red−c1, Pair) = 0 c1 c4 red′ = {c4} 为进一步详细说明算法 2 针对不同实例变化 后对原属性约简结果产生的影响，下面首先分析 算法 2 的 2) 中实例动态删除情况。在数据中删 除实例将存在 6 种情况：1) 只删除有标记的实 例 ，对于 有 ，属性约简集保持不变 ；2) 只 删除有标记的实例 ，有 ， 此时 相对于 为冗余属性，属性约简集更新为 ； 3) 只删除无标记的实例 ，对 ， ，属性约简集保 持不变 ；4) 只删除无标记的实例 ， 有 ，此时 相对于 为冗 余属性，属性约简集更新为 ；5) 同时删 除有标记的实例 和无标记的实例 ，对 ， ，属性约 简集维持不变 ；6) 同时删除有标记的 实例 和无标记的实例 ，有 ，此时 相对于 为冗余属性，属性约简 集更新为 。 Ude = {x1, x7} red′ = {c4} 由于在许多现实动态场景中不仅存在数据删 除还有数据动态增加的情况，为了进一步分析算 法 2 的 3) 和 4) 的计算流程，在上述实例中若在原 始数据集中删除实例 ，删除实例后属 性约简集为 ，在此基础上，在数据中增 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1083·

·1084· 智能系统学报 第15卷 加实例将存在如下6种情况：1)只增加有标记实 为：CPU Intel(R)Core(TM)i5-6500(3.20Hz),内存 例{}={[a,b,*,0.62,0],原属性约简能够维持最大 8.0GB,操作系统为Windows10,采用Python编 区分度，根据性质2属性约简集维持不变，ed= 程语言，开发工具为Pycharm2018.2.4。 {ca:2)只增加有标记实例{x}={[a,a,*,0.62,0]l, 表2数据集描述 原属性约简无法维持最大区分度，3c∈C-red'使 Table 2 Description of UCI data sets 得RSig(c,C-c,△Pairad)≠0，根据性质2可知red'= 数据集 实例个数 属性个数属性值缺失 {c2}不满足约简条件，在算法2的4)中属性约简 Automobile 205 26 是 更新为ed={c4,c2};3)只增加无标记的实例 Soybean(Large) 307 35 是 {x}={[b,a,b,0.68,*,同理根据性质2属性约简集 Dermatology 366 34 是 维持不变，red={ca;4)只增加无标记的实例 Cylinder Bands 512 40 {x}={[b,a,*,0.62,0,原属性约简集无法维持最大 shroom 8124 22 是 区分度，同理属性约简更新为red={c4,c;5)同 Letter Recognition 20000 17 否 时增加有标记的实例{}={[a,b,*,0.77,1]}和无标 记的实例{xs}={[b,a,a,0.65,*,同理属性约简集维 本节详细讨论标记缺失对算法1的影响，首 持不变，red={c;6)同时增加有标记的实例 先以数据集的40%为基础数据，数据集大小的 {x}={[a,b,*,0.77,1]}和无标记的实例{xg}={[b,a,a, 10%为梯度递增，对数据集的标记进行随机缺失 0.65,,原属性约简无法维持最大区分度，同理可 处理。然后分别对弱标记的数据(weak labeled 得属性约简集更新为red'={c4,c3l。 data)采用算法I(WIDAR)、SemiD算法 通过上述实例分析可知，本文算法1采用相 Semi P算法o进行属性约简，并和算法1对有标 对重要度为属性重要度的度量标准，在迭代过程 记数据(Labeled data)的约简结果进行比较分析。 中不断剔除当前属性集已能够区分的区分对和相 对属性约简结果的分类性能评估，将采用KNN、 对冗余的属性，使得每次迭代的搜索空间不断缩 CART、Naive Bayes三个分类器的精度作为约简 减，避免了大量的重复计算。算法2通过分析实 结果的评价指标，将Automobile、Soybean、Derma- tology、Cylinder Bands数据集随机分为两部分，一 例动态变化对原属性约简集的影响，在实例变化 部分作为训练集，另一部分作为测试集，获取分 后动态获取属性约简集，无需重新计算属性约简 类精度；Mushroom和Letter Recognition数据集采 集。在删除实例后，对可能存在的冗余属性逆向 用10倍交叉验证，获取分类精度。针对数据中的 剔除：增加实例后，通过搜索原属性约简集无法 连续型属性，本文的6计算方式为6=(S:/n)/d, 辨识的区分对，确定算法的搜索空间。为弱标记 其中，S,为每个连续型属性的标准差，S:/n为连 混合数据的属性约简提供了一种可借鉴的处理 续型属性标准差的平均值，由于每个数据集的连 方法。 续型属性的平均标准差为固定值，6的取值由入 5实验分析 决定2。在本文中先对连续型的属性采用Min- Max Normalization归一化方法处理，d取0.6。由 为进一步验证本文算法的有效性，从UCI数 于Semi P和Semi D算法的属性约简结果的分类 据集中选取了6个真实数据集进行测试和分析， 精度基本相同，本节以Semi D算法为例进行比 数据的详细信息如表2所示。实验的运行环境 较分析，实验结果如图35所示。 1.0r WIDAR 0.7 ◆WIDAR Labeled data -Labeled data 0.9 -o-Semi D 0.6 o-Semi D 09 0.7 04 0.6 0.3 0.5d 02 0.4 0.1 40 50 60 70 0 40 50 60 70 80 90 标记缺失比例/% 标记缺失比例% (a)Automobile (b)Soybean (Large)

{x7} = {[a,b,∗,0.62,0]} red′ = {c4} {x7} = {[a,a,∗,0.62,0]} ∃c ∈ C −red′ RSig(c,C −c,∆Pairad) , 0 red′ = {c2} red′ = {c4, c2} {x7} = {[b,a,b,0.68,∗]} red′ = {c4} {x7} = {[b,a,∗,0.62,0]} red′ = {c4, c1} {x7} = {[a,b,∗,0.77,1]} {x8} = {[b,a,a,0.65,∗]} red′ = {c4} {x7} = {[a,b,∗,0.77,1]} {x8} = {[b,a,a, 0.65,∗]} red′ = {c4, c3} 加实例将存在如下 6 种情况：1) 只增加有标记实 例 ，原属性约简能够维持最大 区分度，根据性质 2 属性约简集维持不变， ； 2) 只增加有标记实例 ， 原属性约简无法维持最大区分度， 使 得 ，根据性质 2 可知 不满足约简条件，在算法 2 的 4) 中属性约简 更新为 ； 3 ) 只增加无标记的实例 ，同理根据性质 2 属性约简集 维持不变， ； 4 ) 只增加无标记的实例 ，原属性约简集无法维持最大 区分度，同理属性约简更新为 ；5) 同 时增加有标记的实例 和无标 记的实例 ，同理属性约简集维 持不变， ； 6 ) 同时增加有标记的实例 和无标记的实例 ，原属性约简无法维持最大区分度，同理可 得属性约简集更新为 。 通过上述实例分析可知，本文算法 1 采用相 对重要度为属性重要度的度量标准，在迭代过程 中不断剔除当前属性集已能够区分的区分对和相 对冗余的属性，使得每次迭代的搜索空间不断缩 减，避免了大量的重复计算。算法 2 通过分析实 例动态变化对原属性约简集的影响，在实例变化 后动态获取属性约简集，无需重新计算属性约简 集。在删除实例后，对可能存在的冗余属性逆向 剔除；增加实例后，通过搜索原属性约简集无法 辨识的区分对，确定算法的搜索空间。为弱标记 混合数据的属性约简提供了一种可借鉴的处理 方法。 5 实验分析 为进一步验证本文算法的有效性，从 UCI 数 据集中选取了 6 个真实数据集进行测试和分析， 数据的详细信息如表 2 所示。实验的运行环境 为：CPU Intel(R)Core(TM)i5-6500(3.20 Hz),内存 8.0 GB，操作系统为 Windows 10，采用 Python 编 程语言，开发工具为 Pycharm 2018.2.4。 表 2 数据集描述 Table 2 Description of UCI data sets 数据集 实例个数 属性个数 属性值缺失 Automobile 205 26 是 Soybean(Large) 307 35 是 Dermatology 366 34 是 Cylinder Bands 512 40 否 shroom 8124 22 是 Letter Recognition 20000 17 否 δ δ = (S i/n)/λ S i S i/n δ λ λ 本节详细讨论标记缺失对算法 1 的影响，首 先以数据集的 40% 为基础数据，数据集大小的 10% 为梯度递增，对数据集的标记进行随机缺失 处理。然后分别对弱标记的数据 (weak labeled data) 采用算法 1(WIDAR)、Semi_D 算法[ 1 3 ] 、 Semi_P 算法[10] 进行属性约简，并和算法 1 对有标 记数据 (Labeled data) 的约简结果进行比较分析。 对属性约简结果的分类性能评估，将采用 KNN、 CART、Naive Bayes 三个分类器的精度作为约简 结果的评价指标，将 Automobile、Soybean、Derma￾tology、Cylinder Bands 数据集随机分为两部分，一 部分作为训练集，另一部分作为测试集，获取分 类精度；Mushroom 和 Letter Recognition 数据集采 用 10 倍交叉验证，获取分类精度。针对数据中的 连续型属性，本文的 计算方式为 ， 其中， 为每个连续型属性的标准差， 为连 续型属性标准差的平均值，由于每个数据集的连 续型属性的平均标准差为固定值， 的取值由 决定[22]。在本文中先对连续型的属性采用 Min￾Max Normalization 归一化方法处理， 取 0.6。由 于 Semi_P 和 Semi_D 算法的属性约简结果的分类 精度基本相同，本节以 Semi_D 算法为例进行比 较分析，实验结果如图 3~5 所示。 WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D 40 50 60 70 80 90 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (a) Automobile 40 50 60 70 80 90 0.1 0.2 0.3 0.4 0.5 0.6 0.7 分类精度 标记缺失比例/% (b) Soybean (Large) ·1084· 智 能 系 统 学 报 第 15 卷

第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1085· 0.9 1.0 0.8d 0.9 0.7 0.8 0.6 0.7 0.5 0.6 0.4 -◆-WIDAR -◆-VIDAR 0.3 -Labeled data 0.5 Labeled data o-Semi D -o-Semi D 0.2 0.4 40 50 60 70 80 90 40 50 60 70 8090 标记缺失比例% 标记缺失比例% (c)Dermatology (d)Cylinder bands 1.000◆ 1.0r 0.998 0.9 0.996 0.994 0.8 0.992 $0.990 点0.7 0.988 ◆WIDAR 0.6 ◆-WIDAR 0.986 ▲-Labeled data ▲Labeled data o-Semi D o-Semi D 0.984 0. 0 6070 80 90 30 40 50 60708090 标记缺失比例% 标记缺失比例% (e)Mushroom (①Letter recognition 图33N分类器的分类精度 Fig.3 Classification accuracy with the 3NN classifier 0.9 1.0 0.9 0.8 0.7 0.4 0.6 ◆-WIDAR 0.3 ◆WIDAR 0.5 Labeled data ▲-Labeled data 02 0- Semi D 0- Semi D 0.4 0 50 60 70 80 90 0 50 60 70 80 90 标记缺失比例/% 标记缺失比例% (a)Automobile (b)Soybean (Large) 1.0 0.9 1.0◆ 0.8 0.9 0.7 0.8 0 05 0.7 0.4 0.6 ●-NIDAR WIDAR 0.3 Labeled data 0.5 Labeled data 0- Semi D -o-Semi D 02 90 0.4 0 50 6070 50 60 70 80 90 标记缺失比例% 标记缺失比例% (c)Dermatology (d)Cylinder bands

40 50 60 70 80 90 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 分类精度 标记缺失比例/% (c) Dermatology 40 50 60 70 80 90 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (d) Cylinder bands 40 50 60 70 80 90 0.984 0.986 0.988 0.990 0.992 0.994 0.996 0.998 1.000 分类精度 标记缺失比例/% (e) Mushroom 30 40 50 60 70 80 90 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (f) Letter recognition WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D 图 3 3NN 分类器的分类精度 Fig. 3 Classification accuracy with the 3NN classifier 40 50 60 70 80 90 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 分类精度 标记缺失比例/% WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D (a) Automobile 40 50 60 70 80 90 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (b) Soybean (Large) 40 50 60 70 80 90 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (c) Dermatology 40 50 60 70 80 90 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (d) Cylinder bands 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1085·

·1086· 智能系统学报 第15卷 1.000 1.0 0.9 0.95 0.8 0.90 WIDAR 0.6 WIDAR -Labeled data ◆-Labeled data 0- Semi_D 0- Semi D 0.85 60 0. 0 50 70 80 90 40 50 60 70 80 90 标记数据所占比例/% 标记缺失比例% (e)Mushroom (①Letter recognition 图4CART分类器的分类精 Fig.4 Classification accuracy with the CART classifier 0.8 0.7 0.7 0.6 0.6 0.4 0.5 0.3 ◆-WIDAR 0.4 ◆-WIDAR 0.2 ▲-Labeled data ▲-Labeled data 0 o-Semi_D -o-Semi D 0.3 40 50 60 70 80 90 0 50 60 70 80 90 标记缺失比例/% 标记缺失比例% (a)Automobile (b)Soybean (Large) 0.9 1.0 08 0.9 0.7 0.6 0.5 0.79 0.4 0.3 WIDAR ◆-WIDAR 0.2 ▲-Labeled data 0.5 Labeled data o-Semi D -o-Semi D 0.1 0. 0 60 7080 90 40 50 60 70 80 90 标记缺失比例/% 标记缺失比例% (c)Dermatology (d)Cylinder bands 0.8 1.0 ● 0.7 0.9 0.89 0.6 0 0.7 ◆-VIDAR 0.5 -Labeled data o-Semi D 0.6 0.4 ◆WIDAR -Labeled data -o-Semi D 0. 0.3 40 50 60 70 80 90 0 50 60 70 80 90 标记缺失比例% 标记缺失比例/% (e)Mushroom (f)Letter recognition 图5 Naive Bayes分类器分类精度 Fig.5 Classification accuracy with the Naive Bayes classifier

40 50 60 70 80 90 0.85 0.90 0.95 1.00 分类精度 标记数据所占比例/% (e) Mushroom 40 50 60 70 80 90 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (f) Letter recognition WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D 图 4 CART 分类器的分类精 Fig. 4 Classification accuracy with the CART classifier 40 50 60 70 80 90 0.1 0.2 0.3 0.4 0.5 0.6 0.7 分类精度 标记缺失比例/% WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D WIDAR Labeled data Semi_D (a) Automobile 40 50 60 70 80 90 0.3 0.4 0.5 0.6 0.7 0.8 分类精度 标记缺失比例/% (b) Soybean (Large) 40 50 60 70 80 90 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 分类精度 标记缺失比例/% (c) Dermatology 40 50 60 70 80 90 0.4 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (d) Cylinder bands 40 50 60 70 80 90 0.5 0.6 0.7 0.8 0.9 1.0 分类精度 标记缺失比例/% (e) Mushroom 40 50 60 70 80 90 0.3 0.4 0.5 0.6 0.7 0.8 分类精度 标记缺失比例/% (f) Letter recognition 图 5 Naive Bayes 分类器分类精度 Fig. 5 Classification accuracy with the Naive Bayes classifier ·1086· 智 能 系 统 学 报 第 15 卷

第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1087· 由图3~5可知，WIDAR算法能够有效利用有 与Semi D算法相比分类精度从83.7%下降到 标记和无标记的数据，获取分类性能较优的属性 58.4%。而在CART和Naive Bayes分类器中， 约简集。特别地，随着标记缺失比例的增加，若 WIDAR算法的表现更加稳定，CART分类器的分 采用WIDAR算法仅处理有标记数据(Labeled 类精度稳定在100%，Naive Bayes分类器的分类 data)获取的属性约简结果，由于信息利用率的下 精度则在73.6%~76.3%，与Semi D算法相比具有 降，分类器难以学习到较好的分类模型，在3个分 较明显的优势。 类器中分类性能总体偏低，分类精度较低并且不 为了进一步详细分析属性约简结果，本文以 稳定。相反，充分利用弱标记数据获取的属性约 数据标记缺失比率为50%的情况为例，在表3中 简结果，能够较好地利用原数据集的信息。分类 列举出了详细的属性约简结果，属性C:简写为i。 模型的分类精度较高且稳定，分类性能较优。在 在同一数据集上，不同的算法属性结果存在一定 前4个数据集中，由于数据的规模较小，使得分类 的差异，结合图5和表3中的信息可知，仅利用有 器较难准确学习到其内在规则或模式，且对小数 标记的数据获取的属性约简结果会丢失部分有效 据集的标记进行随机缺失，对分类效果产生了一 的分类信息。Semi_D算法和Semi P算法中 定影响。因此不同分类器在同一属性约简结果上 Automobile和Cylinder Bands数据集的约简结果 的分类表现差异较大，但仅利用有标记的数据获 完全相同，而这两个算法在其他数据集中属性约 取属性约简结果的分类性能显著偏弱。随着数据 简结果大致相同，分类精度相近，为此在讨论属 规模增大，在Mushroom、Letter Recognition数据集 性约简结果的分类性能时，本文以Semi D算法 中，随着标记缺失比例的增加，WIDAR算法在有 为例。与Semi D算法和WIDAR算法仅利用有 标记的数据中和Semi D算法在弱标记数据中获 标记数据(Labeled data)相比较，本文提出的WID- 取的属性约简结果分类精度出现较大的波动，但 AR算法能够获取一个分类性相对较优的属性约 采用WIDAR算法利用弱标记的数据获取的属性 简结果。在实验过程中发现，本文的WIDAR算 约简结果分类精度稳定且对比Semi D算法有较 法在规模较小的数据集上对比Semi D算法，其 明显的优势。以数据集Letter Recognition为例， 分类性能有时存在效果偏弱的情况，但随着数据 在图(3)的()中随着标记缺失比例的增加，WID- 规模的增大，WIDAR算法的性能表现趋于稳定， AR算法使用弱标记的数据获取的属性约简结果 并且对比Semi D算法存在较明显的优势。综上 在KNN分类器上的分类精度仅出现了较小的波 可得，本文的算法在大数据集中能够有效利用无 动，在标记缺失比例为40%时分类精度为99.0%， 标记的数据，增强属性约简结果的分类性能，显 在标记缺失比例为90%时，分类精度仍有92.4%， 著提升了算法的鲁棒性。 表3属性约简结果的对比 Table 3 Comparison of attribute reduction results 数据集 WIDAR算法 Labeled data Semi D算法 Semi P算法 Automobile 3,247.6,8.5 3,24,76 1,22,5.4,6,3.8 1,22,5,4,6,3,8 Soybean(Large) 1,7,6,15,10,17,35,4,12,8,21,3,30 1,7,6,22,10,35,3,2 1,7,6,10,4,22,3,8,9,30 1,29,3.4,6,7,10,89,30 Dermatology 16,4,3,19,2,32,17,26,18.5 16,4,3,19,2,32,17 34,16.4,19,32,17,5,1334,17,29.283,17,1,32.16 Cylinder Bands 2,35,25,3 2,4,14 1,24,2 1,24,2 93.22.12.15,5,21,14 59,321.1322,1.15,2. 9,3,22,1,2,15,521.14 Mushroom 5,20,22,21 1320,12,17,7,6 14,20,12,17,7,6 13,20,12,17,7,6 2.15,89,113.6.47,1 2,15.89.113.6.47,1 2.10,7,8.15,9,11,3.12. Letter Recognition 2.15,8.9.11.12.1310.61 12,10,5,16,13,14 12,10,5,16,13,14 13.6.4,1,5,16,14 综上可知，无标记数据也内含丰富的分类信 性能较优的属性约简结果，且算法具有良好的鲁 息，仅利用有标记的数据获取属性约简集，往往 棒性。另外，为了进一步说明算法2(WIDIAR算 会丢失部分信息，导致分类器的分类性能偏低。 法)的有效性，在数据集的标记随机缺失50%后， 充分利用有标记数据和无标记数据，获取的属性 将6组数据集划分为基准数据集和候选数据集两 约简结果，在分类器中的表现较优。WDAR算法 部分，取原数据集的前50%作为基准数据集。为 在对大数据进行属性约简时，能够快速获取分类 应对现实应用领域中常见的复杂应用场景，每次

由图 3~5 可知，WIDAR 算法能够有效利用有 标记和无标记的数据，获取分类性能较优的属性 约简集。特别地，随着标记缺失比例的增加，若 采用 WIDAR 算法仅处理有标记数据 (Labeled data) 获取的属性约简结果，由于信息利用率的下 降，分类器难以学习到较好的分类模型，在 3 个分 类器中分类性能总体偏低，分类精度较低并且不 稳定。相反，充分利用弱标记数据获取的属性约 简结果，能够较好地利用原数据集的信息。分类 模型的分类精度较高且稳定，分类性能较优。在 前 4 个数据集中，由于数据的规模较小，使得分类 器较难准确学习到其内在规则或模式，且对小数 据集的标记进行随机缺失，对分类效果产生了一 定影响。因此不同分类器在同一属性约简结果上 的分类表现差异较大，但仅利用有标记的数据获 取属性约简结果的分类性能显著偏弱。随着数据 规模增大，在 Mushroom、Letter Recognition 数据集 中，随着标记缺失比例的增加，WIDAR 算法在有 标记的数据中和 Semi_D 算法在弱标记数据中获 取的属性约简结果分类精度出现较大的波动，但 采用 WIDAR 算法利用弱标记的数据获取的属性 约简结果分类精度稳定且对比 Semi_D 算法有较 明显的优势。以数据集 Letter Recognition 为例， 在图 (3) 的 (f) 中随着标记缺失比例的增加，WID￾AR 算法使用弱标记的数据获取的属性约简结果 在 KNN 分类器上的分类精度仅出现了较小的波 动，在标记缺失比例为 40% 时分类精度为 99.0%， 在标记缺失比例为 90% 时，分类精度仍有 92.4%， 与 Semi_D 算法相比分类精度从 83.7% 下降到 58.4%。而在 CART 和 Naive Bayes 分类器中， WIDAR 算法的表现更加稳定，CART 分类器的分 类精度稳定在 100%，Naive Bayes 分类器的分类 精度则在 73.6%~76.3%，与 Semi_D 算法相比具有 较明显的优势。 Ci i 为了进一步详细分析属性约简结果，本文以 数据标记缺失比率为 50% 的情况为例，在表 3 中 列举出了详细的属性约简结果,属性 简写为 。 在同一数据集上，不同的算法属性结果存在一定 的差异，结合图 5 和表 3 中的信息可知，仅利用有 标记的数据获取的属性约简结果会丢失部分有效 的分类信息。Semi_D 算法和 Semi_P 算法中 Automobile 和 Cylinder Bands 数据集的约简结果 完全相同，而这两个算法在其他数据集中属性约 简结果大致相同，分类精度相近，为此在讨论属 性约简结果的分类性能时，本文以 Semi_D 算法 为例。与 Semi_D 算法和 WIDAR 算法仅利用有 标记数据 (Labeled data) 相比较，本文提出的 WID￾AR 算法能够获取一个分类性相对较优的属性约 简结果。在实验过程中发现，本文的 WIDAR 算 法在规模较小的数据集上对比 Semi_D 算法，其 分类性能有时存在效果偏弱的情况，但随着数据 规模的增大，WIDAR 算法的性能表现趋于稳定， 并且对比 Semi_D 算法存在较明显的优势。综上 可得，本文的算法在大数据集中能够有效利用无 标记的数据，增强属性约简结果的分类性能，显 著提升了算法的鲁棒性。 表 3 属性约简结果的对比 Table 3 Comparison of attribute reduction results 数据集 WIDAR算法 Labeled data Semi_D算法 Semi_P算法 Automobile 3,24,7,6,8,5 3,24,7,6 1,22,5,4,6,3,8 1,22,5,4,6,3,8 Soybean(Large) 1,7,6,15,10,17,35,4,12,8,21,3,30 1,7,6,22,10,35,3,2 1,7,6,10,4,22,3,8,9,30 1,29,3,4,6,7,10,8,9,30 Dermatology 16,4,3,19,2,32,17,26,18,5 16,4,3,19,2,32,17 34,16,4,19,3,2,17,5,13 34,17,29,28,3,17,1,32,16 Cylinder Bands 2,35,25,3 2,4,14 1,24,2 1,24,2 Mushroom 9,3,22,1,2,15,5,21,14, 13,20,12,17,7,6 5,20,22,21 5,9,3,21,13,22,1,15,2, 14,20,12,17,7,6 9,3,22,1,2,15,5,21,14, 13,20,12,17,7,6 Letter Recognition 2,15,8,9,11,3,6,4,7,1, 12,10,5,16,13,14 2,15,8,9,11,12,13,10,6,1 2,15,8,9,11,3,6,4,7,1, 12,10,5,16,13,14 2,10,7,8,15,9,11,3,12, 13,6,4,1,5,16,14 综上可知，无标记数据也内含丰富的分类信 息，仅利用有标记的数据获取属性约简集，往往 会丢失部分信息，导致分类器的分类性能偏低。 充分利用有标记数据和无标记数据，获取的属性 约简结果，在分类器中的表现较优。WIDAR 算法 在对大数据进行属性约简时，能够快速获取分类 性能较优的属性约简结果，且算法具有良好的鲁 棒性。另外，为了进一步说明算法 2 (WIDIAR 算 法) 的有效性，在数据集的标记随机缺失 50% 后， 将 6 组数据集划分为基准数据集和候选数据集两 部分，取原数据集的前 50% 作为基准数据集。为 应对现实应用领域中常见的复杂应用场景，每次 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1087·

·1088· 智能系 统学报 第15卷 实验剔除基准数据集中5%的数据后增加数据， 加，与WIDAR算法、Semi P算法和Semi D算法 并且增加的数据以候选数据集的10%为梯度增 进行对比分析，实验结果如图6所示。 22 24 22 ◆VIDAR 2 WIDIAR -Semi D 21 2入 -Semi P ◆-VIDAR ◆-WIDIAR 入 2 -Semi D -*-Semi P 2 20 40 60 80 100 0 20 40 60 80 100 数据增量% 数据增量% (a)Automobile (b)Soybean (Large) 25 量 23 22 WIDAR WIDIAR 21 20 -Semi D 米-Semi P 20 ·-WIDAR ·-WIDIAR 22 --Semi D 2 -Semi P 2 0 20 40 60 80 100 0 20 4 60 80 100 数据增量% 数据增量% (c)Dermatology (d)Cylinder Bands 2 21 26 2 2 ·-WIDAR 0 WIDAR WIDIAR 25 WIDIAR -Semi D -Semi D -Semi p 22 *Semi p 士2 20 25 2 28 20 40 60 80 100 0 20 40 60 80100 数据增量% 数据增量% (e)Mushroom (f)Letter recognition 图64种算法的计算时间对比 Fig.6 Comparison of time consumption of four algorithms 由图6(a)(c)可知，WIDAR算法引入了相对 简算法，获取属性约简需要花费423.521s,与静态 重要度作为属性重要度的度量标准，在迭代中不 属性约简算法相比较能够节约50.38%的时间。 断缩减算法搜索空间。因此在处理数据规模较小 在Letter Recognition数据集中，采用动态属性约 的数据集时，WIDIAR算法与WIDAR算法计算效 简算法动态更新属性约简结果需要的时间仅为 率相近，但相比Semi P算法和Semi D算法有较 356.823S,而采用WIDAR算法获取属性约简需要 明显的优势。但随着数据规模的增大，WIDAR算 花费2776.922s,与WIDAR算法相比较能够节约 法在动态数据中更新属性约简结果需要进行大量 87.15%的时间。 的重复计算。采用WIDIAR算法，对属性约简集 表4为增加的数据达到100%时，WIDIAR算 进行增量式更新，能够有效减少重复的计算，相 法和WIDAR算法的属性约简结果的对比，属性C: 比WIDAR算法，能够节约大量的时间。当增加 简写为i。从表4中可以看到，WIDIAR算法的属 的数据集的大小为100%时，在Mushroom数据集 性约简结果与WIDAR算法相比，在较小的数据 中，采用动态属性约简算法动态更新属性约简结 集中存在一定差异，但随着数据规模的增加，算 果需要的时间仅为210.156s,而采用静态属性约 法的属性约简结果差异逐步缩减，在Mushroom

实验剔除基准数据集中 5% 的数据后增加数据， 并且增加的数据以候选数据集的 10% 为梯度增 加，与 WIDAR 算法、Semi_P 算法和 Semi_D 算法 进行对比分析，实验结果如图 6 所示。 WIDAR WIDIAR Semi_D Semi_P WIDAR WIDIAR Semi_D Semi_P WIDAR WIDIAR Semi_D Semi_P WIDAR WIDIAR Semi_D Semi_P WIDAR WIDIAR Semi_D Semi_P WIDAR WIDIAR Semi_D Semi_P 0 20 40 60 80 100 2 −5 2 −4 2 −3 2 −2 2 −1 2 0 2 1 2 2 计算时间/s 数据增量/% (a) Automobile 0 20 40 60 80 100 2 −4 2 −3 2 −2 2 −1 2 0 2 1 2 2 2 3 2 4 计算时间/s 数据增量/% (b) Soybean (Large) 0 20 40 60 80 100 2 −4 2 −3 2 −2 2 −1 2 0 2 1 2 2 2 3 2 4 2 5 计算时间/s 数据增量/% (c) Dermatology 0 20 40 60 80 100 2 −3 2 −2 2 −1 2 0 2 1 2 2 2 3 2 4 计算时间/s 数据增量/% (d) Cylinder Bands 0 20 40 60 80 100 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 计算时间/s 数据增量/% (e) Mushroom 0 20 40 60 80 100 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 计算时间/s 数据增量/% (f) Letter recognition 图 6 4 种算法的计算时间对比 Fig. 6 Comparison of time consumption of four algorithms 由图 6(a)~(c) 可知，WIDAR 算法引入了相对 重要度作为属性重要度的度量标准，在迭代中不 断缩减算法搜索空间。因此在处理数据规模较小 的数据集时，WIDIAR 算法与 WIDAR 算法计算效 率相近，但相比 Semi_P 算法和 Semi_D 算法有较 明显的优势。但随着数据规模的增大，WIDAR 算 法在动态数据中更新属性约简结果需要进行大量 的重复计算。采用 WIDIAR 算法，对属性约简集 进行增量式更新，能够有效减少重复的计算，相 比 WIDAR 算法，能够节约大量的时间。当增加 的数据集的大小为 100% 时，在 Mushroom 数据集 中，采用动态属性约简算法动态更新属性约简结 果需要的时间仅为 210.156 s，而采用静态属性约 简算法，获取属性约简需要花费 423.521 s，与静态 属性约简算法相比较能够节约 50.38% 的时间。 在 Letter Recognition 数据集中，采用动态属性约 简算法动态更新属性约简结果需要的时间仅为 356.823 s，而采用 WIDAR 算法获取属性约简需要 花费 2 776.922 s，与 WIDAR 算法相比较能够节约 87.15% 的时间。 Ci i 表 4 为增加的数据达到 100% 时，WIDIAR 算 法和 WIDAR 算法的属性约简结果的对比,属性 简写为 。从表 4 中可以看到，WIDIAR 算法的属 性约简结果与 WIDAR 算法相比，在较小的数据 集中存在一定差异，但随着数据规模的增加，算 法的属性约简结果差异逐步缩减，在 Mushroom ·1088· 智 能 系 统 学 报 第 15 卷