论文研究-快速的属性约简算法.pdf

所需积分/C币:5 2019-09-11 17:52:34 818KB .PDF

属性约简的效率是粗糙集等软计算理论的核心问题之一。为了提高约简效率,在分析不可分辨关系和基数排序特点的基础上,提出了一种时间复杂度为O(|C||U|)的求核算法。然后,运用改进的属性重要度作为启发信息,得到一种快速的属性约简算法,时间复杂度为O(|C|2|U|)。最后,通过UCI机器学习库中的一些数据集对算法进行测试,证明了算法对大型的数据集进行属性约简的高效性。
胡彧,白琳林:快速的属性约简算法 2009,45(28)135 列结果为S;若im,很容易想到只需在求Sc过程中对属性 ①对于a∈C-RED(C),按推论6计算sig(m,RED(C),D) cm排完序后记下S,便可得到U按属性集(1,e2,…,cm排若存在ag(a,RED(C),D)=0,定理6得,下次循环时不用再求 序的结果。证毕。 sig(a,REDC),D)了(因为其值还是0) ②选择使属性重要度取值最大的属性加入RED(C)末尾 算法2求核算法 ③计算 POS(D 输入:决策表DT=(U,A,V,),论域U′={x1,x2,…,x},A= CUD,PCC,C=(c1,c2,…,cm}, POSAD)。 (2)倒序扫描RED2(C) 输出:CORE从C)。 if(若属性a是核属性)∥处理REDC)末尾属性 初始化: CORED(C)=d return; 1)对U按c1,C2,…,cn的方向进行排序,记下S-,S。 (2)for(i=1;i<=m;i++) for( i=2; i<=IRED,(C)l; i++) 根据定理5,求得 IPOSc-e (D if(若属性a是核属性) if(IPOS(D)k<IPOS (D)D) return 则有 CORE(C)= CORED)Uc else 计算POS 时间复杂度分析:步骤1的时间复杂度为O(CHU),由定 RED, (C)-[a (D川 理5知,步骤2中,当2≤m时,需要对U再进行一次排序, if( iPOSRED (C)-al (D)=IPOSRED(C(D)D) 每个属性花的时间为U1,m-1属性共需(m-1)×U"<CHU≤ 则从集合RED(C)中删除属性a。 C,因此总的时间复杂度为:O(CU1)。 34属性约简算法 时间复杂度分析:步骤1最坏的情况下花费的时间为: 定义7属性重要度给定一决策表D(,A,),4=CUD,(+1)C2U,时间复杂度为o(CPUm),步骤2花费的时间 属性集PCC,neC-P,定义sira,D)= IPOSL(D)POSD) 为:O(C|-CORE(C川)U),时间复杂度为O(CHU),因此, 为属性a对属性集P相对于决策属性集D的重要度。 总的时间复杂度为O(|CH)。 推论6给定论域数目U和属性集P时,计算属性重要度 虽然时间复杂度和文献5-6的一样,但按照推论7和定理 可简化为:sig(a,P,D)=| POPuLa((D 6,不但简化了计算,而且使每次搜索的空间越来越小,进而减 证明同定理3证明。 少了约简花费的时间。 定理6给定一决策表DT=(U,A,V,),A=C∪D,属性集 PC,VaEC-P,b∈CP,且a≠b,若满足sig(a,P,D)=0,则4实验测试 sig(a, PU161, D)=0 为了测试算法的实际效率,实现了文献5]和文献6提出的 证明设UP=(P,P2,…,P},0<m≤POS(D),其中等价类两种算法,并和该文算法进行比较,这两种算法分别记为算法 P…P(1≤i<≤t≤m)满足P)D≠1,…,(PD≠1,而其余51和算法( 的等价类P…P(1≤j≤≤m)满足(P)D|=1,…,I(P)D|=1, 实验环境如表1 sig(a,P,D)=0,由定义7得POS(D)=POSD),又由推论2 表1实验环境 和推论3得ⅤX∈(PPU{a}),满足XDl≠1,…,X∈(P∥P 配置参数 参数值 d}),满足/D≠1;HX∈(PP∪{),满足D=1,…,HX∈ 机器配置 CPU: Intel pentium d 2. 66 gHz (P/PU{a}),满足D=1。同理推出:X∈(PP∪dU{b),满 内存:2048MB 足D=1,…,X∈(P,/P∪{a∪{b}),满足XD=1。即对于 IDE/开发语言 Ms Visual Studio 2008/C# x∈P,或…,或Vx∈P,x∈POS(D)且x∈ POspua uje(D) 数据库 MS SOL 原名 若彐X∈(PPU@dU{}减或…,或彐X∈(PPU@aU{b}),使得 缩写 X/D=1,则x∈x,x∈ POPUp(D)且x∈ POSpUla U(D);相反, 测试数据集 Congressional Voting Records (UCI机器学习库 T 则 x POspu(D)且 x POspulqui(D)。 Chess( King-Rook vs. King-Pawn) C 由上所得, POSP(D)= POSPURUB(d),即sig(a,PU{b},D)=0。 Mushroom 证毕。 Letter Recognition 算法3属性约简算法 对每个数据集各进行10次约简,然后取平均值,以使测试 输入:决策表DT=(U〃,A,V,f),论域U′={x,x2,…,x,A=结果更加客观、有效。为了表示方便,用DT表示测试的数据 CUD,PCC,C={c1,c2,…,cm}, POSAD), COREDCC)。 集,N表示论域中的对象个数,M表示约简前的条件属性个数 输出:REDC)。 m表示约简后的条件属性个数,T表示约简花费的时间(单位 初始化:REDD(C)= CORED(C) 为秒)。测试结果如表2。从表2可以看出,对每个数据集而言, (1)While(IPOSRED((D)I*IPOS(D)D) 采用三种算法约简后的条件属性个数都相同,这是由于这三种 算法都是使用属性重要度作为启发信息的;当论域中对象个数 http://archiveics.uci.edu/ml/datasets.html 1362009,45(28) Computer Engineering and Applications计算机工程与应用 比较少吋,三种算法花费的吋间差不多,如 Congressional infor mation system Intelligent Decision Support-Ilandbook of Ap oting records数据集,当随着对象个数的增加,该文算法和算 plication and Advantages of the Rough Sets Theory, 1991 法巧5要明显地好于算法6];对于无核的情况,如 Mushroom数[3 I Pawlak Z Rough sets[J]. International Journal of Computer and In- 据集,三种算法因为在约简前都要进行求核,但核实际并不 formation Science, 1982.11(5): 341-356 存在,而该文算法求核时间少的优点也就无法体现,导致该4苗夺谦李道国粗糙集理论、算法与应用[M北京:清华大学出版 文算法和算法6]对 Mushroom数据集约简的时间差不多。综合 社,2008:133-22 以上分析,该文算法要比算法5和算法[6]有更好的约简效率。5]刘少挥,盛秋戳,吴斌,等Romg集高效算法的研究计算机学报, 2003,26(5):524-529 表2属性约简测试结果 6]徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(CUn),O( CHUI) 算法5]算法6该文算法 DT 的快速属性约简算法J计算机学报,206,29(3):391-399 T/s T/s 4351690.1290.0790.0 7]周江卫,冯博琴,刘洋.一种新的快速求核算法J西安交通大学学 vTcM 958880.2180.1680.14 报,2007,41(6):688-691 C319636290.63290.38290.2 [8]Pawlak Z, Skowron A Rough sels: Some extensions [J].Informalion M81242254.3951.3751.31 Sciences,2007,177(1):28-40 L2000016116.5711196111.43 9]刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法J计算 机研究与发展,2003,40(5):637-642 5结论 「10徐章艳,杨炳儒,郭燕萍,等基于信息熵的快速求核算法J小型 在研究粗糙集相关理论的基础上,分析了运用基数排序算 微型计算机系统,2007,28(2):279-282 法求不可分辨关系的特点,得到了缩小论域大小的方法,给出1杨明一种基丁改进差别矩阵的核增量式更新算法计算机学 了一种时间复杂度为o(CU)的求核算法,低于文献[5提出的 报,2006,29(3):57-63 求核算法的时间复杂度O(CbU);在求约简的过程中,简12]杨明,孙志挥改进的差别矩阵及其求核算法J复旦学报自然科 化了求属性重要度的公式,并由此公式推理得到了定理6,从 学版,2004,43(5):865-868 而避免了在递归求属性重要度的过程中重复计算不重要的13] Chen y-H,YaoY-Y. A multiview approach for intelligent data 属性,缩小每次搜索的空间;其后给出了一种时间复杂度为 analysis based on data operators[J]. Information Sciences, 2008 O(CU1)的属性约简算法;最后通过实验测试,证明了本文算 178(1):1-20 法的正确性和高效性,适合于对大型的数据集进行属性约简。[14]叶东毅,陈昭炯.一种新的差别矩阵及其求核方法小电子学报, 2002,30(7):1086-1088 参考文献 「15]王俊祥,胡峰决策系统的快速属性约简算法J计算机工程与应 [1] Pawlak ZTheoretical aspects of reasoning about data [M]. Boston 用,2008,44(11):161-16 Kluwer Academic Publishers. 1991 16]王国胤决策表核属性的计算方法计算机学报,2003,26(5): [2] Skowron A, Rauszer CThe discernibility matrices and functions in 6l1-615 (上接132页) 符的 XPath表达,减少NFA的状态数,降低NFA的构造时 6000 间,从而提高 lazy dFA的查询速度和减少其内存消耗量;通过 口优化前 3000000 口优化前 定400优化后 求20000优化后 DTD的结构信息减少 XPath表达式中的“*”通配符和“∥”路 径关系这些不确定性因素,来提高 lazy dFA查询处理器的空间 2000 1000000 利用率。 1k 10k 100 k 1k10k100k XPath大 小 XPath大小 参考文献: (a)DTD预处理前后 lazy DFA (b)DTD优化前后 lazyDFA 运行时间比较 内存消耗比较 [ 1] Green T J, Miklau G, Onizuka M, et al. Processing XML streaming 图7基于DID语义信息优化算法前后 lazydFA查询性能比较 with deterministic automata[ C]//Calvanese D, Lenzerini M, Motwani R Proc of the Int'I Conf on Data Theory, Siena, Italy. New York: 3000000 口前 10000 USA: ACM Press. 2004: 752-788 0000口后 8004前 [2]张晓琳,崔敏,谭跃生基于 Lazy dFA的 XPath在XML数据流上的 6000 100000 4000 查询优化算法门计算机工程与应用,2008,44(28):125-127 海20 3 Chidlovskii B Using regular tree automata as XML schemas [Cy/ 1k10k100k 1k 10k100 k Proc of the ieee advances in digital libraries washington 2000 XPath大小 XPath大小 89-104 (a) lazy dFA内存消耗比较(b) azy dFA运行时间比较 [4 Frank N, Thomas SXPath containment in the presence of disjunc 图8基于DTD结构信思优化算法前后 lazy DFA查询性能比较 tion, DTDs, and variables[C]/Diego C, Maurizio L. Proc of the ICDE Heidelberg: Springer-Verlag, 2003: 315-329 5结束语 [5] Gao J, Yang D Q, Tang S W, et al. Tree-automata based efficient 基于DTD的语义和结构信息提出了对 XPath表达式进行 XPath evaluation over XML data stream[J]Journal of Software 优化的算法,优化算法可以提高 lazy DFA查询处理器的性能 2005,16(2):223-232 根据DTD的语言信息,丢弃XPath查询表达式中与DTD不相6]DtdpaRseRfol].http:/www.wutka.com/dtdparserhtml

...展开详情
试读 4P 论文研究-快速的属性约简算法.pdf
img
  • 至尊王者

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

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-快速的属性约简算法.pdf 5积分/C币 立即下载
    1/4
    论文研究-快速的属性约简算法.pdf第1页
    论文研究-快速的属性约简算法.pdf第2页

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

    5积分/C币 立即下载 >