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

团购合买资源类别：文库，文档格式：PDF，文档页数：12，文件大小：4.26MB

第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表示实例的非空有限集合，称为论监督属性约简算法。文献[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、Dermatology、Cylinder Bands 数据集随机分为两部分，一部分作为训练集，另一部分作为测试集，获取分类精度；Mushroom 和 Letter Recognition 数据集采用 10 倍交叉验证，获取分类精度。针对数据中的连续型属性，本文的计算方式为，其中，为每个连续型属性的标准差，为连续型属性标准差的平均值，由于每个数据集的连续型属性的平均标准差为固定值，的取值由决定[22]。在本文中先对连续型的属性采用 MinMax 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期程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·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) 中随着标记缺失比例的增加，WIDAR 算法使用弱标记的数据获取的属性约简结果在 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) 相比较，本文提出的 WIDAR 算法能够获取一个分类性相对较优的属性约简结果。在实验过程中发现，本文的 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 卷

点击进入文档下载页（PDF格式）

共12页，试读已结束，阅读完整版请下载

点击下载（PDF格式）

浏览记录