论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf

所需积分/C币:10 2019-09-16 10:21:08 521KB .PDF

属性约简是机器学习等领域中常用的数据预处理方法。在基于粗糙集理论的属性约简算法中,大多是根据单一的方法来度量属性重要度。为了从多角度对属性达到更为优越的评估效果,首先在已有的模糊邻域粗糙集模型中定义属性依赖度度量,然后根据粒计算理论中知识粒度的概念,在模糊邻域粗糙集模型下提出了模糊邻域粒度度量。由于属性依赖度和知识粒度代表了不同视角的属性评估方法,因此将这两种方法结合起来用于信息系统的属性重要度评估,最后给出一种启发式属性约简算法。实验结果表明,所提出的算法具有较好的属性约简性能。
任晓霞,薛凡:基于模糊邻域粗糙集的启发式属性约简算法 的比例,因而可以作为条件属性与决策属性之间的关系 性质对邻域决策信息系统NDS=(U,CUD 程度的度量。根据定义可以看出模糊相似关系RBW,,B1≌B∈C,那么模糊邻域粒度满足GK(B2)≤ 和邻城半径δ对依赖度有着很重要的影响 下文中,将适当地省略邻域半径δ的标记。 证明由于B1sB2=C,那么R。三R,根据定 性质对于邻域决策信息系统NDS=x,CUD义可以得到r∈U,[三[]l,所以由定义可以 V,f),B1sB2C,那么属性依赖度满是DEB(D)容易得到GK(B2)≤GK()。证毕 DE(D)。 性质对于邻域决策信息系统NDS=(U,CUD, 证明山于B1sBsC,那么显然有 RBCRB,V,,B≌C,邻域半径A,02满足0≤,那么模糊 根据定义可以得到xsxs|xl,所以根据邻城粒度满足GK(B)≤GK(B)。 定义可推出D∈UD满足R(D)=R(D,因此 证明由于01≤62,根据定义有Mx∈U,[x]∈ PS(EPQ即满足关系DED)<DD[,那么由定义可以容易得到G(B=<CKAB 证毕。 在定义中,依赖度是通过近似逼近的视角去对条 性质对于邻城决策信息系统NDsS=U,C∪D,件属性集进行评佔,而定义中的模糊邻域粒度可以体 V,f),B三C,邻域半径a1。满足1≤82,那么属性现出条件属性集对系统的分类性能,这两种方法表现出 依赖度满足DE(D)≤DEA(D 了对属性集的不同视角评估,因此将它们结合起来可以 证明由于心1≤02,根据定义有r∈U,[l 更为全面的评估属性,达到更好的属性重要度度量,同 时可以休现出两种方法的优越性 [r,所以对于YD∈U/D满足Ra( DIC RD),因 定义对于邻域决策信息系统NDS=(U,C∪D 而POS(D≤ POS:L),即满足关系DEB(D≤V,f,BC,RB是出B在U上诱导的模糊相似关 D)E()证毕。 系,设邻域半径δ,定义基于模糊邻域粗糙集的依赖度 粒计算理论是智能信息处理中一种很重要的研和知识粒度混合度量为: 究方法,其中粒结构模型是该理论的一种重要表现 DE(D HaB 形式,同时也是评价信息系统分类能力的一个重要的指 GK&(l 标。目前学者们提岀了多种粒结构模型·,本文这 般情况下,信息系统的论域非空,因此模糊邻域 里在模糊相似关系的基础上提出一种新的粒结构模型。粒度GK(B)≠0。结合性质可以发现,当邻城半 定义对于邻域决策信息系统NDS=U,CUD,径δ不变,随着属性集B的逐渐增大,HB)也是逐渐 v,),BC,邻域半径为0,由U在模糊相似关系增大的。当属性集B不变时,随着邻域半径δ的逐渐 R上诱导的模糊邻域粒结构定义为: 增大,H(B)是逐渐减小的。特别的,当B=时 K(B)={x1x21,…x H2(1)=0。 这里的U={x1,x2,…xn},[x]表示对象x在模糊相似 本文依据定义的混合度量给出信息系统的属性 约简如定义所示。 关系R下的模糊邻域。可以看出,模糊邻域粒结构表 定文对于邻域决策信息系统NDS=U,CUD, 示的是论域在模糊相似关系上的粒化。 V,f,若BC是该信息系统的个属性约简集当如 类似于模糊粗糙集中信息粒度的定义,这里给出下两点同时成立: 基于模糊邻域粒结构的知识粒度。 ()H(B)=H(C) 定义对于邻域决策信息系统NS=U,C∪D )VaEb, IIo(B-lak)<Ilo(C) V,f),|U|=n,BsC,邻域半径为δ,由L在模糊相 定义对于邻域决策信息系统NS={,CUD 似关系R上的模糊邻址知识粒度定义为: ,f,BC,R是由B在U上诱导的模糊相似关 GK(B)=∑ 系,设邻域半径δ,对于va∈B在D下关于B的第 种属性重要度定义为: 根据定义有r∈U,0≤[]≤n,所以模糊邻域 SIGna, B, D)=H,(B)-Ho(B-a)) 粒度满足0≤GK(B≤1。由于模糊邻域粒度展示的是 定义对于邻域决策信息系统NDS=U,CUD 论城所有对象模糊邻域在论域上占比的均值,因而它是V,),B∈C,R是由B在U上诱导的模糊相似关 对信息系统分类能力的一种很好的体现。 系,设邻域半径8,对于a∈C-B在D下关于B的第 () 计算机工程与应用 二种属性重要度定义为 属性重要度为时终止 SIGo(a, B, D)=H (BRa))-Ho(B) 步骤对于a∈md,找出所有使H1(d-l)= 这两种属性重要度的定义表示了两种不同的含义,H成立的属性,记Ⅱ←,将这些属性添加入Ⅱ 定义表示的是属性子集B中内部属性a关于B的属中,如果Ⅱ为空集,输到步骤,否则转到步骤。 性重要度而定义表示的是属性子集B的外部属性②步骤对于∈计算屈性重要度5 SIGa(a red, D) 关于B的属性重要度 并选择出属性重要度最小的属性在red中进行剔除 返回步骤。 启发式属性约简算法 步骡〈返回rea,算法终止。 属性约简作为粗糙集理论的一个重要的应用而得 步骤和步骤通过属性重要度函数对数据集的属 到学者的广泛关注,如何对信息系统中属性进行更精准性集进行启发式搜索,是一个不断选代的过程,算法刚 的重要度评估一真是该方向的研究重点。借助定义O开始时候,r-②,HAm=0,然后通过启发式函数 和定义的两种属性重要度作为启发式函数这里给SG#每次迭代选择出一个属性,并将这个属性添加入 出一和基于模糊邻域粗糙集的启发式属性约简算法。约简集/cl中根据定义,当约简集rcd逐渐增大时 对于邻域决策信息系统NDS=CUDV,∩),其IEr的值也是增大的,经过不断迭代直到满足 BsC,邻域半径δ,算法给出的是模湘邻域粗糙集Il(ved=I。C),此时达到收敛条件。正是由于Ⅰ() 的模糊粒度度量计算方法 函数的单调性,因此算法肯定是收敛的。在步骤屮 算法基于模糊邻域粗集的依焕度和模糊邻城算法每次让属性重要度SGa达到最大的属性加入 粒度混合度量I(B)。 red屮,这样就加速了算法的收敛速度。算法收敛 输入:NDs=,CUD,V,,BC,邻城半径δ。时,得到的集合ra是全集C的一个约简,但不一定是 输出:H(B)。 个最优的约简,因为集合rd内部可能存在属性之间 步骤初始化DE①D)=0,GK。(B)=0 的依赖导致某些属性冗余,因此该算法在步骤中进 步骤根据决策划分U/D计算模糊决策①,行了进一步的属性剔除,从而得到最终的约简结果,这 Dns 个结果既保持了原度量结果的收敛性,又保证了约简集 步骤计算出每个模樹决策D的模糊邻域粗糙集ed的板小性 的下近似,从而得到决策属性D)关于B的止区城 根据算法的时间复杂度和文献,算法的时间 POS2(D)。定义。 复杂度为Oc2n) 步骤计算论域U屮每个对象x的模糊邻域粒 x,从而得到属性集B的模糊邻域粒度GK(B)。 实验分析 定义。 为了验证本文所提出的启发式属性约简算法具有 步骤根据定义返回结果Il(B) 一定的优越性,本实验将所提出的算法与其他的相关算 在邻域决策信息系统屮,设C|=c,U|=n,U/D|=法对同一组数据集进行实验然后通过实验结果的约简 m,通常m是远小于n的。那么在算法中,时间复杂集、约简耗时和约简集的分类精度来较算法的优越 度主要集中在步骤和步骤中模糊邻域粒的计算上,性。参与实验的数据集均选取自标准数据集军,具 因此算法的时间复杂度为Ocn2)。在算法的基础体信息如表所示 上,这里给出本文所提出的启发式属性约简,其体如算 表 数据集 法所示。 编号名称对象属性类 算法基于模糊邻域粗糙集的启发式属性约简 算法 输入:NDs=,CUD,V,f),邻域半径8。 输出:属性约简red。 步骤初始化red=⑧,HeC)=0。 步骤对于a∈C-red,根据定义计算每个属 实验中选取参与比较的相关算法分別为:一种相对 性重要度 SIGO la;red,D),选择属性重要度最大的邢个决策熵度量的高效特征选择算法(算法),基于改进 属性,记为a′。 模糊粒化的模糊粗糙集属性约简算法(算法),基于 步骤rel←-rel∪a"},返回步骤,直到满足最人邻城组合测度的属性约简算法(算法),基于改进模 任晓霞,薛凡:基于模糊邻域粗糙集的启发式属性约简算法 糊粗糙集的一种模糊条件熵的特征选择算法(算法性,从而体现出属性约简在数据预处理中的重要性,同 ),基丁邻域属性区分度量的属性约简算法(算法时也说明这种算法的有效性。对比这种算法的属性 ),基于改进邻域粒化的模糊熵特征选择算法(算法约简结果,可以看岀算法和本文所提岀的算法约简 ),记本文所提出的算法为算法。 得到的属性子集大小整体比其他算法要小一些,例如数 在这些算法中算法算法、算法和算法是据集 和 。这主要是由于这两 于单一度量方法对属性进行度量,而算法算法和算种算法是基于多种度量方法的启发式属性约简,在约简 法是通过多种方法进行组合来度量属性。在实验开过程中对候选属性具有更好的度量效果降低∫度量偏 始之前,为了消除属性量纲的影响,所有数据集的属性差,因此能够得到更小的约简集。这表明,多种度量方 值均被归一化到·区间算法是针对离散型数据法的结合能对属件达到更好的评估从而鉴别出信总系 集的特征选择算法,因此在运用算法前需将连续数据统更为关键的属性。同时,本文所提出的算法在多数 进行离散化处理》在实验分析过程中需要运用分类器数揭集具有更小的约简结果这说明了基丁模椭集的模 来评估约简结果的优劣,本实验采用支持向量机/糊粒化比传统的明确集具有更好的集合求属关系表达 (分类器和分类决策树()分类器。各个算属性的度量效果更佳。另外观察表还可以发现算法 法采用 进行编程实现,实验运行的硬件环 在多数数据集的约简结果较大,这主要是由于算法 境为 的处理器,内存为的在属性约简前数据集经过了离散化处理,离散化的过程 个人主机。 可能导致了连续型数据集分类信息的丟失,这样不利于 对于本文所提出的属性约简算法,在开始之前需要数据集的属性约简。通过属性约简结果,证明了组合度 确定邻域半径θ的值,并且该值的选取对最终的属性约量方法具有更好的属性评估性能,能够搜索到更优的属 简结果有着很重要的影响,因此为了得到最优的实验结性子集,并且基于模糊集的方法具有更精准的度量结果 果,本实验尝试通过取多个值分别进行实验来选择最优 接下来将比较各个算法所选择出约简集的优越 结果,即让邻域半径从区间,按的间隔分別取性。本实验利用和两种分类器分别对种 值,并对每个邻域半径分别进行实验,然后运用分算法的属性约简结果运用十折交叉的方法对样本数据 类器对每个邻域半径下的属性约简结果进行分类训练,进行分类学习训练,然后计算出样本数据的分类精度, 从而得到对应实验结果的分类精度,本文所提出的算法其结果如表和表所示。 最终约简结果选取为分类精度最高的属性子集。表 在表和表中,川“"标记的分类精度为种算法 所示的是种算法约简结果集合基数的大小比较。 中的最大值。观察表和表可以发现,种算法的分类 表种算法的约简集大小比较 精度结果差别不是很大,均接近原始数据集的分类精 约简集大小 度,并且有一些算法在部分数据集的分类精度高于原始 总数算法算法算法算法算法算法算法_数据集的分类精度,这便体现了属性约简算法的有效 性。仔细比较分析可以看出,算法算法和算法约 简结果对应的分类精度在整体上同样比其他算法约简 结果的分类精度要高一些,这说明了,通过多种度量方 法结合后约简出来的属性子集能够达到更好的分类效 果,从而进一步证明了组合度量对属性评估的优越性。 观察表可以看出,种算法得到的约简结果均小同时,算法在部分数据集得到的约简结果具有更高的 于原数据集的属性总数,部分数据集远小于原数据集,分类精度,说明本文所提岀的属性约简算法在约简结果 这说明了现实中很多数据集普遍存在着很多的冗余属方面具有更好的约简性能。 表种算法约简结果在的分类精度比较 约简集分类精度 名称原始属性 算法 算法 算法 算法 算法 算法 算法 () 计算机工程与应用 表种算法约筒结果在下的分类精度比较 约简集 分类精度 名称原始属性算法 算法算法算法 算法 算法 算法 算法 算法 算法 算法 匚算法 算法 算法 算法 算法 算 数据集 数据集 ()部分数据集算法效率比较 )部分数据集算法效率比较 图算法效率比较 算法的时间复杂度是评估算法优劣的一项重要指的不足之处 标,因此接下来将比较种算法的约简效率。在实验 由于邻域半径对实验结果有着很重要的影响,因 中,为了防止偶然性,让每种算法分别对每个数据集重此接下来将探究邻城半径δ对实验结果是如何影响的 复约简多次,取多次属性约简时间开销的平均值作为对并且分析其取值问题,为以后的研究提供参考。图给 应数据集属性约简的时间结果,具体结果如图所示,出了数据集属性约简集大小、分类精度和邻城半 观察图可以发现,在各个数据集的属性约简时间开销径之间的关系。观察可以发现随着邻域半径的逐渐增 结果中,算法、算法和算法结果略多于其他算法,这大,算法约简出的属性子集大小是逐渐增大的,而分类 主要是由亍这三种算法的评估函数是多种方法的结合,精度刚开始逐渐增大,但是当邻域半径达到 时, 在进行计算方法无疑会增加时间的开销,但是这三种算其分类精度开始趋于稳定或略有降低,这主要是由于, 法都经过了优化,多种度量的计算都避免了重复计算,刚开始时候约简集较小,未能达到最佳的分类效果,所 尤其是本文所提岀的属性约简算法,其中依赖度和模糊以分类精度较低,但是当属性子集较大时,较多的属性 邻域粒度的计算都需要计算出每个对象的模糊邻域粒,可能会带来噪声数据的干扰,反而会不利于数据的分 因此可以将依赖度和模糊邻琙粒度进行同时计算,这样类,从而出现了分类精度降低的情形。根据图的实验 可以大大降低计算量,因此所提出的算法同样具有较高结果,本文所提出的属性约简算法中邻域半径可以取 的时间效率。 之间较为适宜。 综合以上算法的约简结果和算法的运行效率,可以 看出,本文所提出的算法通过多个度量方法可以对信息 结语 系统的属性达到更好的度量效果,其约简结果优于单 属性约简是一项重要的数据预处理技术,如何构 度量的启发式属性约简,同时本文所提出的算法是运用造有效的属性评估方法一直是目前研究的重点,在基 模糊集的视角去构造两种度量,同样具有更佳的评估效于粗糙集理论的属性约简算法中,本文针对目前属性 果。此外实验结果也表明本文所提出的算法具有较高评估单一性的问题,在模糊邻域粗糙集模型中定义属 的约简效率。另方面,本文所提出的算法在进行实验性依赖度的概念,并基于此提出了模糊邻域粒度度量 时,邻域半径是个需要设定的参数,这里是通过重复由于依赖度和模糊邻城粒度是两种不同视角的属性评 实验多次才能得到最优的结果,很难直接快逑地得到合估方法,因此本文将两种方法结合提出一种新的启发式 适的邻域半径取值,因此这也是本文所提岀算法的一个属性约简算法。最后实验结果证明了所提岀算法 任晓霞,薛凡:基于模糊邻域粗糙集的启发式属性约简算法 二囟日由 -÷-…… 0-约简集大小 约简集大小 分类精度 +分类精度 城半径 径 数据集随邻域半径变化实验结果)数据集随邻域半径变化实验结果 已日非日日 兴逗 禦匀 约简集大小 约简集大小 「a分类精度 一分类精度 邻域半径 邻域半径 )数据集随邻域半径变化实验结果()数据集随邻域半径变化实验结果 B自自÷自自色 米 约简集大小 一-约简集大小 分类精度 分类精度 邻域半径 邻域半径 ()数据集随邻域半径变化实验结果( 数据集随邻域半径变化实验结果 图各个数据集实验结果 的适用性和优越性。出于本文提出的算法只适用于数 值型数据,因此接下来探索可以适用混合型数据的属性 约简算法。 徐怡杨宏健纪霞基于双重粒化准则的邻域多粒度粗糙 参考文献 集模型控制与决策, 段洁,胡清华,张灵均,等基于邻城粗糙集的多标记分类 特征选择算法计算机研究与发展, 陈昊杨俊安,庄镇泉,等变精度粗糙集的属性核和最小 属性约简算法计算机学报, (下转页)

...展开详情
试读 7P 论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf 10积分/C币 立即下载
    1/7
    论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf第1页
    论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf第2页
    论文研究-基于模糊邻域粗糙集的启发式属性约简算法.pdf第3页

    试读已结束,剩余4页未读...

    10积分/C币 立即下载 >