论文研究-基于加权浓缩树的粗糙集属性约简算法.pdf

所需积分/C币:6 2019-09-13 03:30:03 840KB .PDF

针对基于分辨矩阵约简算法中存在冗余元素,从而导致空间存储代价高的问题,提出一种基于加权浓缩树的属性约简算法。该算法可以进一步剔除冗余元素,压缩存储分辨矩阵中的信息,并且在构建树结构的过程当中考虑了属性重要度的影响。实验结果与C-Tree及差别信息树算法进行比较,提出的算法可以获得更优的属性约简结果,有效地降低了空间复杂度。
78 018,54(2) Computer Engineering and Applications计算机工程与应用 从图1可以看出,表2的分辨矩阵的非空元素项被压缩阵的压缩储,面给出加权浓缩树的相关定义。 存储到3条路径中因此该方法可以有效地降低空间存定义8如权浓缩树为颗有序树其子树也是有序 储代价 树,并且每个结点最多只有(棵子树(C是条件属性集, 结点表 表示集合的基数)具体定义如下 属性名头指针 (1)根结点用root”标记 (2)根结点的每个子结点由4个城组成, attrName parentPointer, childPointer, nodePointer, #f H, attrName 记录该结点的条件属性名, parentPointer指向当前结点 的 父结点 ter指向当前结点的孩子结点 C nodepointer指向与该结点属性名相同的下一结点。 3)结点表:由3个域组成, attrName, Weights, first 图1差别信息树 Pointer, attrName记录该结点的条件属性名, Weights表 示当前结点的权重, first pointer指向第一个与该结点属 数为: 根据分辨矩阵M中的信息计算出对应的分辨幽性名相同的结点 fB=(c1Vc2VC3VC4)A(GI VC2 Ve3Vc4)A 加权浓缩树是一棵有序的虚拟树结构。结合定义8 下面给出加权浓缩树具体的构造算法。 c2Vcs)A(C2 VC3VC4AC4=C2c4Ac;C 从分辨函数/2可以看出,属性c为核属性,因此包 算法1生成加权浓缩树算法 含核属性的路径在分辨函数计算过程中会被析取,不会 输入:決策表S=U,CUD,V,f 影响最终的计算结,但是在差别信息树的构建过程中 输出:加权浓缩树T 仍然将包含核属性的路径插入到树结构中,增加了时间 步骤Ⅰ属性集中的各属性根据某种顺序进行排序, 复杂度和空间复杂度。同时根据分辨函数的结果可以序记为; 得出属性约简结果为{c2,c}或(,C4},而根据文献[20」 步骤2根据顺序§创建结点表 屮的属性约简算法求得的约简结果为{c2,c4},这科计算 步骤3创建树T的根结点,并标记为'root'; 方法只考虑最右孩子结点,而没有考虑到与孩子结点在 步骤4fori=1 to u do 同一结点上的其他结点,在属性约简中没有考虑属性的 for j=i+1 to U do 重要性可能会丢失最优约简集合。因此,有必要设计 if(f(x24)≠f(r,)是&x2x:∈U1 种新的数据结构以及算法来解决上述问题 x∈U1Ax∈U)ther 根据定义5产生分辨矩阵元素mn,; 3加杈浓缩树数据结构的实现 ifm;≠then{ 31加权的设计与实现 根据顺序§将m中条件属性排序记为B 由上一章示例可知,在属性约简的过程中,没有考 调用 insert Tree(b,n); 虑属性的重要性会影响最终的约简结果。因此在构造 根据定义7更新结点表中的属性权重信息; 树结构的过程中应该记录属性的重要度。基于此,本文 将属性进行加权作为启发式信息来提高算法效率。 定义7给定一个决策表S=(U,C∪D,V,)和条 步骤5 return 7 件属性子集B≤C。对应的分辨矩阵为M。则对任 insert tree(B,T)函数将分辨矩阵中的非空元素项 意条件属性a∈B的权重定义为: 插入到树T中,下面给出具体步骤: sy count a (8) 步骤1创建指针head指向根结点; 步骤2iB= C ther 其中,|B表示条件属性集B的基数, count表示属性 goto步骤10; 在分辨矩阵中出现的频率,频率越高,该属性的重要性 步骤3获取B中的第一个条件属性a,并令B= 越大,B表示属性所在的非空元素项越短属性的重6-l 步骤4 if head不存在属性名为a的子结点N 要性越大。 then go to步骤7; 32加杈浓缩树构建算法 步骤5iN是叶子结点,B中剩余结点不再插入 为了消除分辨矩阵中的非空元素项,实现对分辨矩 then go to步骤10; 唐坤剑,容强:基于加权浓缩树的粗糙集属性约简算法 2018,54(2 79 步骤6if'B 压缩仵储,降低了空间存储代价,并在构建树结构的过 删除T屮以结点N为根结点的所有子树,并保留程中动态计算所有条件属性的权重,为后面的属性约 根结点N; 简算法提供了计算的依据。 o步骤10 结点表 属性名权重头指 步骤7 if head子结点中存在结点与B中相同 the 步骤10 LI null 步骤8创建新结点N′,且结点的属性名为a,将 N作为T的子结点插入到T中,将 nodepointer指针连 接到与该结点属性名相同的结点上,构成同名属性结 点链; 步骤9令head指向子结点N′,goto步骤2 步骤10结東。 图2加权浓缩树 根据定义7和算法1可知加权浓缩树中包含了分辨 矩阵中的所有分辨信息。下面给出加权浓缩树的相关4基于加权浓缩树的属性约简算法 定理。 41算法介绍 定理1给定一个决策表S=U,CUD,V,)和条 为了验证本文所提算法的有效性,在使用算法I生 件属性子集BCC。B对应的的分辨矩阵为M,根据 成加权浓缩树以后,基于所生成的树结构并结合启发式 算法1生成的加权浓缩树为T,a∈CoeU)当且仪" 信息提出一个完备属性约简算法。算法根据从右到左 中存在只有个结点的路径a。 的顺序迭代树结构将根结点中的必要条件属性添加到 证叨根据算法1,只有一个元素的非空元素项在树约简集合中,并删除根结点中的必要属性以及包含该结 点的路径,直到树中只剩根结点时结束 T中必定存在一个只有一个结点的路径与之对应 算法2基于加权浓缩树的属性约简算法 由性质1可知,当a∈ Core(l)可得{a}为分辨矩阵 输入:加权浓缩树T M的非空元素项,因此,a∈(ore当且仅当T中存 输出:约简集合red 在只有一个结点的路径a 步骤1初始化,令约简集合re=②; 定理2给定一个决策表S=(U,C∪D,V,)和条 步骤2获取根结点中所有只有一个子结点的路径, 件属性子集BC。B对应的分辨矩阼为M,根据算并将该结点集合所对应的属性集合记为R; 法1生成的加权浓缩树为T,对仟意RCB为属性约简 ifR≠ A then{ 当且仅当满足如下条件 删除树结构中所有包含集合R中属性的路径; (1)对于T中任意路径P,有P∩R≠ 令redl=reht∪R (2)对丁任意QCR,T中必作在一条路径P1,使 得P1∩Q=0。 步骤3if根结点不包含子结点then 证明R是一个属性约简当且仅当R与分辨矩阵 goto步骤5; M中的任意非空元素项相交非空,且Q∝R,存在 步骤4 个非空元素项m使得m∩Q=,不妨设m在T中对 步骤4.l选择根结点中最右孩了结点及其子树的 应的路径为P1。R是一个属性约简,则对于T中任意所有结点信息,记为B; 路径P,由算法1可知树T中包含了所有分辨矩阵M 步骤4.2fort=1 to U do{ 中非空元素项的信息,因此有P∩R≠,而对vQ 根据结点表获取其中权重最大的结点,标记为a R,有P1∩Q= 令rel-relU{a} 反之,对于T屮的任意·条路径P,P∩R≠⑧, 删除结点a以及树结构中包含该结点的所有路径; 且对QCR,中必存在一条路径P使得P1∩Q= goto步骤3; ¢成立,则由算法1可知,R与分辨矩阵M中的任意 非空元素项相交非空,且存在m∈M使得m∩Q=, 步骤5 return rec 其中,m对应的路径为P,囚而R是一个属性约简 结合算法2,在考虑了属性的权重以后,表1的约简 例2根据算法1中方法,利用表1构造的加权浓缩结果为(2C}或者c3,c4 树如图2所示。可以看出,相比较文献[20中的方法,本42时间复杂度分析 文提出的算法进一步对分辨矩阵中的冗余元素进行了 分辨矩阵中最多拥有个非空元素项,每个元素 208,54(2) Computer Engineering and Applications计算机工程与应用 项最多有C个元素,因此,构造的加权浓缩树中最多有增大3个算法的时间开销都不断增大。其中,C-Iree算 C个结点。而根据算法2,在迭代过程中最多删除法的时间开销最大,呈现指数型增长,差别信息树算法 C|U哔,因此时间复杂度为O(CL)。 的时间开销约为C-Tree算法的一半,而加权浓缩树算法 的时间开销最小,增长也最缓慢。因此,相对于两种对 5实验分析 比算法,加权浓缩树的构造算法最有效。 51实验准备 200——C-Tre 为了验证本文所提算法的有效性,从UCI机器学习 0-差别信息树 数据库中选用了5组数据集,其体描述如表3所示。 合加权浓缩树 表3数据集描述 数据集对象数条件属性数決策类别数 101 s3196 3190 2 Nursery 12 960 Chess数据集缺失比例% 实验环境为一台i3.5GHz(4GB内存,Win8操作 图3 Chess数据量变化的时间开锴 系统),采用Java语言实现所有算法,同时通过以下对比 B-Tree 算法来与本文算法进行比较,对比算法分别为: 差别信息树 (1)基于C-Tree的算法" 加权浓缩树 (2)基于差别信息树的算法° 52树的构建时间和空间开销比较 本节内容是比较在树的构建过程中所耗费的时间 和空间开销。 由表4可以看出,差别信息树构造算法的时间和空 间复杂度明显低于C-Tre算法,这是因为构造差别信息 树过程中剔除了冗余的父集元素,实现了更好的压缩存 Gene数据集缺失比例 储。而构造加权浓缩树的时间和空间开销要低于差別 图4Gcne数据量变化的时间开销 信息树算法,这是因为在构造加权浓缩树时考虑插入路5.3属性约简比较 径时如果当前树结构中已存在根结点中只有一个子结 从表5中可以看出,3种约简算法都可以不同程度 点的路径时,不再插入到树结构中,因此降低了存储代地剔除冗余属性,说明3种算法都适用于属性约简。从 价。而在处理 Nursery数据集时,CIre算法利差别信单个数据集来看,在大部分数据集中,加权浓缩树算法 息树算法因为空间存储消耗过大导致内存溢出,但是加获得的条件属性数量少丁 C-Tree算法,与差别信息树算 权浓缩树算法却可以对数据进行处理。因此,相对于两法的数量基本致,这是因为加权浓缩树算法在计算属 种对比算法,加权浓缩树算法更有效 性约简时考了属性的重要度,相比较于差别信息树算 为了验证不同的数据集大小下各种算法的时间开法能获得更好的属性约简结果,但是并不会减少约简属 销,本文分别从Ches和〔ene数据集中按照10%,性的数量,这是符合实际情况的。从总体情况来看,C 20%,…,100%的比例远择数据形成新的决策表。分别Tree的平均属性数为11,差别信息树的平均属性数为 用3个算法对数据集进行实验,数据集的大小变化情况10.加权浓缩树的平均数为10。因此加权浓缩树算法具 的时间开销如图3和图4所示,可以看出,随着数据量的有较好的约简能力。 表4时间和空间开销比较 C-T 数据集 差别信息树 加权浓缩树 时间/s空间MB时间/s空间 时间/s空间MB 2.732 0.330 13.472 0.169 11.996 0.1310 5.332 Che 222.150080.896|1.163 542.216 43.8190 272.848 1479.524 741.676 Nursery 内存溢出 内存溢出 16.04102094496 唐坤剑,容强:基于加权浓缩树的粗糙集属性约简算法 2018,54(2 表5约简前后属性数量比较 ion[J] Journal of Computational Information Systems 数据集原始数量CTe差别信息树加权浓缩树 2013,9(16):6621-6628 6 5 Qu F fAn attribute reduction algorithm in 4 4 rough set theory based on information entropy[c] /Inter Chess 36 national Symposium on Computational Intelligence and (iene 6 Nursery [9] Miao D Q Information representation of the concepts 平均数 26 11 10 and operations in rough set theory[J]Journal of Soft- 1999,22:113-116 6结束语 本文为了消除在构造树结构中出现的冗余元素提0 Beaubouer n, Petry F E, Arora G.n formalion-cheorelic measures of uncertainty for rough sets and rough rela 出了一种加权浓缩树的数据结构,可以进一步剔除冗余 tional databases[J]. Information Sciences, 1998, 109(1/4 元素,压缩储分辨矩阵中的信息。并且在构建树结构 185-195 的过程当考虑了属性重要度的影响。基于此提出了[11hmYM,wuKs, Chen X H, et al. An entropy 加权浓缩树的属性约简算法,可以获得优的属性约简 based uncertainty measurement approach in neighbor- 结果。最后通过实验证明了本文所提算法的有效性。 hood systems[J]. Information Sciences, 2014, 279: 239-250 下一步的研究重点是如何在对象动态增加的情形下实121QianYH,LingJy.combInatiOnentropyandcombina 现对属性约简结果的动态更新 tion granulation in rough set theory [J]. International Journal of Uncertainty Fuzziness and Knowledge-Based 参考文献 Systems,2011,16(2):179-193 [1] Pawlak 7. Rough sets[J]. Int of Computer and Informa [13] Yang M, Yang P.A novel approach to improving C- tion sciences,1982,11(5):341-356 tree for Teature selection[J] Applied Soft Computing [21 Sarah V, Lynn D, Yvan S, et al. Applications of fuzzy 201l,11(2):19241931 rough set theory in machine learning: a survey J. Funda-.[14]徐章艳,刘作鹏,杨炳儒等一个复杂度为mx(O(n) menta Informaticae, 2015, 142(1/4): 53-86 O(C~2UC|))的快速属性约简算法[计算机学报, [3] Rahman A, Muhammad H S, Sungyoung L. Rough set- 2006,29(3):391-399 based approaches for discretization a compact rev [15 Miao D Q, Zhao Y, Yao YY, et al. Relative reducts in Artificial Intelligence Review, 2015, 44(2): 235-263 consistent and inconsistent decision tables of the pay [4 Wang D L, Song X F, Yuan J Y Forecasting core busi lak rough set model[J] Information Sciences, 2009, 179 ness transformation risk using the optimal rough set (24):4140-4150. and the neural network[J] Journal of Forecasting, 2015, [16] Yao Y, Zhao Y Discernibility matrix simplification for 34(6):478-491 constructing attribute reducts [J] Information Sciences [5] Chen L F, Tsai C T Data mining framework based on 2009,179(7):867-82 rough set theory to improve location selection decisions:7高学东,丁军基于简化差别矩阼的属性约简算法叭系 a case study of a restaurant chain[J]. Tourism Manage 统工程理论与实践.2006,26(6):101-107 nent,2016,53:197-206. [18]葛浩,李龙澍,杨传健.可信度差别矩阵及其属性约简[ [6 Wei w, Jiye L, Wang JH, et al. Decision-relative discerni 四川大学学报:工程科学版,2011,43(5):146-152 bility matrices in the sense of entropies[].International19杨明,吕静.种基于Cree属性约简增量式更新算 Journal of General Systems, 2013, 42(7): 721-738 法[J控制与决策,2012,27(12):1769-17 ]xieJ,ShenⅹF, Liu h e,etal! Research on an incre-[20]蒋瑜基于差别信息树的 rough set属性约简算法[J.控制 mental attribute reduction based on relative positive re- 与决策,2015,30(8):1531-1536

...展开详情
试读 6P 论文研究-基于加权浓缩树的粗糙集属性约简算法.pdf
img
  • 至尊王者

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

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于加权浓缩树的粗糙集属性约简算法.pdf 6积分/C币 立即下载
    1/6
    论文研究-基于加权浓缩树的粗糙集属性约简算法.pdf第1页
    论文研究-基于加权浓缩树的粗糙集属性约简算法.pdf第2页

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

    6积分/C币 立即下载 >