第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 incomplete 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 Software, Jiangxi Agricultural University, Nanchang 330045, China; 3. Institute of Information Technology, Jiangxi University of Technology, 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 labeling, which can reduce the search space and improve the efficiency of attribute reduction. Besides, the dynamic updating mechanism of attribute reduction is analyzed based on the dynamic change of instances. In this study, an incremental attribute reduction algorithm is designed under a semi-supervised scene, and the experimental results show the feasibility and effectiveness of the proposed algorithm. Keywords: attribute reduction; rough set; discernibility pair; mixed data; incremental learning; semi-supervised learning; 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,A,Vf>是一个信息 框架和无监督学习框架，构造相对应的启发式半 系统，其中U表示实例的非空有限集合，称为论 监督属性约简算法。文献[14]基于粗糙集理论和 域；A表示属性的非空有限集合V=UVa,V。是属 信息熵的概念，在对无标记数据进行部分标注 性a∈A所有可能值的集合；f表示U×A→V,是 后，设计了一种基于信息嫡的半监督特征选择算 一个信息函数，它为每个实例的每一个属性赋予 法。文献[15]将粗糙集理论和集成学习框架相结 一个值，即YaeA,x∈U,fx,a)eVao 合，利用有标记的数据训练基分类器对无标记的 给定信息系统，如果至少有一个属性a∈A使 数据进行标注，扩充有标记的数据。文献[16)]提 得V。含有缺失值，其中缺失值用”*”表示，此时 出了一种基于流形正则化的半监督特征选择算 该系统称为不完备信息系统，用S=<U,A,Vf> 法，通过最大化不同类别之间的间距对特征的重 表示。 要性进行度量分析。文献[1刀提出了一种半监督 定义2在不完备信息系统IS=<U,A,V,f> 特征选择算法，算法通过组合半监督散点，有效 中，有A=AUA,其中Aa表示离散型属性集，A 利用大量未标记的视频数据中的信息来区分目标 表示连续型属性集，对于任意B二A,关于属性子 类别。上述这些方法为弱标记数据的属性约简， 集B的区分对定义为DisUL(B,U)={<x,>l。Hp∈ 提供了有效的解决方案。 B,对H<x,x,>有 另外，在大数据时代，许多数据随着时间的推 3p∈A,lf,p)-fx,p)川>6 移而动态变化。在这种复杂应用场景中，传统的 V3peAa,fx,p)≠f(x,p) 属性约简算法在处理这些动态数据时，将会产生 Af(x,P)+*Af(x,P)≠* 大量重复计算，无法快速更新属性约简结果。近 给定的不完备信息系统IS=<U,A,V,f>,对 年来，许多学者对动态属性约简算法进行了大量 YBSA,Disu(B,U表示属性集B重要度，其物理 的研究。文献[18]提出了一种基于信息嫡的组增 含义为属性集B的区分度。属性集区分的实例 量式属性约简算法，在动态增加一组实例后，快 对的数量越多，该属性集越重要。由定义可知 速更新属性约简结果。文献[19]采用一种复合粗 <,x>∈DisUL(B,U)满足自反性、对称性，因此在 糙集模型，处理动态的不完备数据，在数据动态 考虑实例之间的区分对<x,x>后，则不再重复
况下，剔除不重要或冗余的属性[5-6]。由于属性约 简的结果往往不是唯一的，找到数据所有约简的 结果，已经被证明是一个 NP-hard 问题。因此在 实际应用中通常采用启发式算法处理大规模数 据，获取满足知识发现要求的属性约简结果[7-9]。 然而，在众多现实应用领域中存在大量的高 维复杂数据。并且在数据采集阶段，由于采集成 本和技术的限制，导致这些高维数据往往存在缺 失。同时，给这些数据进行类别标注，需要耗费 大量的人力资源，并且利用经典粗糙集无法直接 处理不完备数据。针对上述问题研究人员引入容 差关系和限制容差关系等，拓展了经典粗糙集的 应用[10-12] ，但这些扩展的关系模型难以直接处理 含有连续型的不完备混合数据。同时，由于在实 际应用中，这些高维数据通常仅包含少量已标注 的数据。若仅利用带标记的数据进行属性约简， 约简结果不能有效反映数据的分布，且分类性能 较弱。 弱监督属性约简旨在有效利用无标记数据来 增强属性约简的有效性，从而提高学习模型的分 类性能。近年来，弱监督属性约简引起了许多研 究人员的关注和研究。文献 [13] 针对弱标记的符 号型数据，在区分对的基础上，利用有监督学习 框架和无监督学习框架，构造相对应的启发式半 监督属性约简算法。文献 [14] 基于粗糙集理论和 信息熵的概念，在对无标记数据进行部分标注 后，设计了一种基于信息熵的半监督特征选择算 法。文献 [15] 将粗糙集理论和集成学习框架相结 合，利用有标记的数据训练基分类器对无标记的 数据进行标注，扩充有标记的数据。文献 [16] 提 出了一种基于流形正则化的半监督特征选择算 法，通过最大化不同类别之间的间距对特征的重 要性进行度量分析。文献 [17] 提出了一种半监督 特征选择算法，算法通过组合半监督散点，有效 利用大量未标记的视频数据中的信息来区分目标 类别。上述这些方法为弱标记数据的属性约简， 提供了有效的解决方案。 另外，在大数据时代，许多数据随着时间的推 移而动态变化。在这种复杂应用场景中，传统的 属性约简算法在处理这些动态数据时，将会产生 大量重复计算，无法快速更新属性约简结果。近 年来，许多学者对动态属性约简算法进行了大量 的研究。文献 [18] 提出了一种基于信息熵的组增 量式属性约简算法，在动态增加一组实例后，快 速更新属性约简结果。文献 [19] 采用一种复合粗 糙集模型，处理动态的不完备数据，在数据动态 变化后快速更新近似集合。文献 [20] 提出了一种 基于知识粒度模型的动态属性约简算法，在实例 变化后动态更新属性约简集。文献 [21] 提出了一 种不完备动态属性约简算法，该算法在不完备决 策系统中单个实例变化后动态获取新的属性约简 结果集。上述研究都是针对所有实例均有标记的 数据，目前对弱标记数据的增量式属性约简研究 较少。为此，有效地利用无标记数据来增强属性 约简结果，并在保证分类精度前提下动态更新属 性约简结果，已成为了当前亟待解决的问题。 针对上述问题，本文提出了弱标记不完备数 据的区分对概念，给出了属性的相对重要度的度 量方法。并以此为基础，设计了启发式的半监督 属性约简算法，算法在每次迭代过程中能剔除相 对冗余的属性和当前属性约简集已能够区分的区 分对，算法的搜索空间显著缩减。同时，根据数 据中实例的动态变化情况，给出属性约简集的动 态更新机制，并通过实例分析详细说明动态属性 约简算法的计算过程。最后，采用来自 UCI 的真 实数据集，进一步验证了算法的高效性和可行性。 1 基本知识 IS =< U,A,V, f > 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 =< U,A,V, f > 给定信息系统，如果至少有一个属性 使 得 含有缺失值，其中缺失值用 表示，此时 该系统称为不完备信息系统，用 表示。 IIS =< U,A,V, f > A = Ad ∪ Ar Ad Ar B ⊆ A B DisUL(B,U 2 ) = { < xi , xj > } ∀p ∈ B, ∀ < xi , xj > 定义 2 在不完备信息系统 中，有 ，其中 表示离散型属性集， 表示连续型属性集，对于任意 ，关于属性子 集 的区分对定义为 。 对 有 ∃p ∈ Ar ,| f(xi , p)− f(xj , p) | > δ ∨∃p ∈ Ad, f(xi , p) , f(xj , p) ∧f(xi , p) , ∗ ∧ f(xj , p) , ∗ IIS =< U,A,V, f > ∀B ⊆ A |DisUL(B,U 2 )| B B < xi , xj >∈ DisUL(B,U 2 ) < xi , xj > 给定的不完备信息系统 ，对 ， 表示属性集 重要度，其物理 含义为属性集 的区分度。属性集区分的实例 对的数量越多，该属性集越重要。由定义可知 满足自反性、对称性，因此在 考虑实例之间的区分对 后，则不再重复 ·1080· 智 能 系 统 学 报 第 15 卷
第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1081· 考虑区分对<，x>。 U,根据定义4有Dis(BUa,U)≥Dis(B,U)。从 定义3对于给定信息系统IS=<U,A,V,f>, 而可证Dis(BUa,U2)+Disw(BUa,U)≥Dis(B,UP)+ 令A=CUD,其中子集C是条件属性集合，D是 DisM(B,UP),即Dis(BUa,U≥Dis(B,U)。 决策属性集合，又称四元组为决策系统，用DS=<U, 定义6给定弱标记不完备决策系统WTDS= CUD,Vf>表示。 <U,CUD,Vf>,设U=LUM,其中L表示有标记 对于给定决策系统DS=<U,CUD,Vf>,如果 实例的集合，M表示无标记实例的集合，RSC是 至少有一个属性c∈C使得V。含有缺失值，其中 一个属性约简，当且仅当R满足： 缺失值用”*”表示。此时，该系统称为不完备决 1)Dis(R,U2)=Dis(C,U2); 策系统，用DS=<U,CUD,Vf>表示。 2)VceR,Dis(R-c,U2)≠Dis(C,UP)。 定义4给定不完备决策系统DS=<U, 定义7给定弱标记不完备系统WDS= CUD,Vf>,有Ca,C,SB,其中C4表示离散型属 <U,CUD,V,f>,设U=LUM,其中L表示有标记 性，C,表示连续型属性，设<，x>EU,对Yp∈ 实例的集合，M表示无标记实例的集合，并且 B、B≤C,D关于B的区分对定义为Dis(B,UP)= B≤C.对Hc∈C-B,则 <x,x>(其中L表示有标记)，对V<,x>有 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=<U,CUD,Vf>, 如图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=<U,CUD,V,f>, 若决策属性d存在缺失值。此时该系统称为弱标 图1属性C相对于属性集B的重要度 记不完备决策系统，用WIDS=<U,CUD,V,f>表示。 Fig.1 Significance of attribute c with respect to B 定义5给定弱标记不完备决策系统WIDS= 性质2给定弱标记不完备决策系统WDS= <U,CUD,Vf>,设U=LUM,其中L表示有标记 <U,CUD,Vf>,设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,CUD,Vf>,设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∈
< xj 考虑区分对 , xi >。 IS =< U,A,V, f > A = C ∪ D C D DS =< U, C ∪ D,V, f > 定义 3 对于给定信息系统 ， 令 ，其中子集 是条件属性集合， 是 决策属性集合，又称四元组为决策系统，用 表示。 DS =< U,C ∪ D,V, f > c ∈ C Vc ” ∗ ” IDS =< U,C ∪ D,V, f > 对于给定决策系统 ，如果 至少有一个属性 使得 含有缺失值，其中 缺失值用 表示。此时，该系统称为不完备决 策系统，用 表示。 IDS =< U, C ∪ D,V, f > Cd,Cr ⊆ B Cd Cr < xi , xj >∈ U 2 ∀p ∈ B B ⊆ C D B DisL(B,U 2 ) = < xi , xj > L ∀ < xi , xj > 定 义 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 =< U,C ∪ D,V, f > ∀B ⊆ C |DisL(B,U 2 )| B B 给定的不完备决策系统 ， 对 ， 表示属性集 的重要度，其 物理含义为属性集 的区分度。属性集能区分 的实例对的数量越多，则表明该属性集越重要。 由于在现实应用中，在大量不完备数据中只 有少部分实例存在标记，若仅利用带标记的实例 获取属性约简结果，由于无标记的实例未得到有 效的利用，使得属性约简结果较难反映数据的整 体信息，分类算法难以学习有效的知识规则，导 致分类模型的分类性能较弱。为此，针对弱标记 不完备决策系统，设计有效的属性重性度量方法 显得尤为重要。本文在文献 [8,13] 的基础上，构 造了面向弱标记不完备数据的属性重要性度量方法。 IDS =< U,C ∪ D,V, f > d WIDS =< U,C ∪ D,V, f > 给定的不完备决策系统 ， 若决策属性 存在缺失值。此时该系统称为弱标 记不完备决策系统，用 表示。 WIDS = < U,C ∪ D,V, f > 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,C ∪ D,V, f > 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,C ∪ D,V, f > 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,C ∪ D,V, f > 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,C ∪ D,V, f > 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=<U, 除，时间复杂度为O(IPairllredl)。 C,V.f>; 输出属性约简集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 =< U, C,V, f > 输入 弱标记不完备决策系统 ； 输出 属性约简集 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, 1 X b 0.58 CUD,V,f>,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,>,<2,X>,<x4>,<,7>,<67>};在 算法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; {<,为>，<2，x>,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, C ∪ D,V, f > 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 = {< x1, x2 >,< x2, x3 >,< x4, x7 >,< x5, x7 >,< x6, x7 >} red = Ø RSig(c1,red, Pair0) = 3 RSig(c2,red,Pair0) = 2 RSig(c3,red,Pair0) = 2 RSig(c4,red,Pair0) = 2 Pair1 = { < x1, x2 >,< x2, x3 > } 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·