正在加载图片...
Vol.28 No.6 鄂旭等：基于扫描向量的属性约简方法 607. 最小属性约简 表2差别向量组 Table 2 Discernible vector array 0 CD F 0 CD F (x1,x2) (b.e.g) (0,1/3.0,0,1/3,1/3) (x3,x4) (b.c,d) (0,1/3,1/3,1/3,0,0) (x1,x3) (b,c.d,e,g) (0,1/5,1/5,1/5,1/5,1/5) (x3,x5) (a,b,c,d) (1/4,1/4,1/4,1/4,0,0) (x1,x4) (c.d,e,g) (0,0,1/4,1/4,1/4,1/④ (x3,x6) (a,b,c,d) (1/4,1/4,1/4,1/4,0,0) (x1,x5) (a e,g) (1/3,0,0,0,1/3,1/3) （x3,3x7) (b,c,d) (0,1/3,1/3,1/3,0,0) (x1,x6) (a,e,g) (1/3,0,0,0,1/3,1/3) (x4,x5) (a.c,d) (1/3,0,1/3,1/3.0,0) (x1,x7) (e,g) (0,0,0,0,1/2,1/2) (x4,x6) (a.c,d) (1/3,0,1/3,1/3.0,0) (x2,x3) (b,c.d,e,q) (0,1/5,1/5,1/5,1/5,1/5) (x4,x7) (c,d) (0,0.1/2.1/2,0,0) (x2x4） (b,c,d,e,g） (0,1/5,1/5,1/5,1/5,1/5) (x5,x6) (a) (1,0,0,0,0,0,0) (x2,x5) (a:b,e,g) (1/4,1/4,0,0,1/4,1/4 (x5,x7) (a) (1,0,0,0,0,0,0) (x2:x6) (a.b,e,q) (1/4,1/4,0,0,1/4,1/4) (x6,x7) (a) (1,0,0,0,0,0,0) (x2,x7) (b,e,g） (0,1/3,0,0,1/3,1/3) 为了进一步验证本算法的有效性，从世界著 低寻找属性约简集的搜索范围，从数值实例和数 名的测试数据库UCI中挑选了3个典型的数据 据库运算结果可以看出本文的算法是有效可 库，利用本文提出的算法做测试，测试结果如图1 行的 所示 参考文献 60 [1]Pawlak Z.Rough set.Int J Comput Inf Sci.1982 (1):341 [2]鄂旭，高学东，武森，等。信息表中不完备数据的填补方法 42 Mushroon Lung Cancer Balloon 北京科技大学学报，2005,27(3)：364 (adult-stretch) [3]鄂旭，高学东，谭文东，等.基于超立方体与信息熵的离散 划试数据库 化方法.北京科技大学学报，2005,27(6)：760 图1属性约简对比图 [4]武森，高学东，Bastian M.数据仓库与数据挖掘.北京：冶 Fig.1 Results of attributes reduction 金工业出版社，2003 [5]王国胤.Rough集理论与知识获取.西安：西安交通大学出 版社，2003 4 结论 [6]张文修，吴伟志，梁吉业，等.粗糙集理论与方法.北京： 科学出版社，2001 根据原始信息表，应用粗糙集中的不可分辨 [7]Hu X H.Cercone N.Learning in relational databases:a rough 关系将原始信息表转换成差别向量组，由于在差 set approach.Comput Intell.1995,11(2):323 别向量中定义了频率向量，同时又根据相应的定 [8]Jelonek J,Krawiec K,Slowinski R.Rough set reduction of 理证明定义了差别向量的加法运算，因此本算法 attributes and their domains for neural networks.Comput In" tel,1995,11(2):339 大大降低了算法的时间复杂，经典的基于分辨矩 [9]苗夺谦.Rough Set理论中连续属性的离散化方法.自动化 阵的属性约简算法，如Hu的差别矩阵方法[8]求 学报，2001,27(3)：296 核属性的时间复杂度为O(nm),n=card(u), [10]孟庆生：信息论.西安：西安交通大学出版社，1986 m=card(c):而本算法只是通过对差别向量进行 [11]Wong S K M,Ziarko W.On optional decision rules in deci- 一次扫描就能将核属性识别出来，算法的时间复 sion tables.Bull Pol Acad Sci.1985.33,693 [12]Ohrn A.Discernibility and Rough Sets in Medicine:Tools 杂度最大仅为O(nm)·同时在识别核属性的过 and Applications [Dissertation].Trondheim:Department of 程中通过差别向量的加法运算，形成了数目少却 Computer and Information Science.Norwegian University 具有典型代表意义的差别属性集，这样将大大降 and Science and Technology,1999:53最小属性约简． 表2 差别向量组 Table2 Discernible vector array O CD F O CD F （ x1x2） （ beg） （01／3001／31／3） （ x1x3） （ bcdeg） （01／51／51／51／51／5） （ x1x4） （ cdeg） （001／41／41／41／4） （ x1x5） （ aeg） （1／30001／31／3） （ x1x6） （ aeg） （1／30001／31／3） （ x1x7） （ eg） （00001／21／2） （ x2x3） （ bcdeg） （01／51／51／51／51／5） （ x2x4） （ bcdeg） （01／51／51／51／51／5） （ x2x5） （ abeg） （1／41／4001／41／4） （ x2x6） （ abeg） （1／41／4001／41／4） （ x2x7） （ beg） （01／3001／31／3） （ x3x4） （ bcd） （01／31／31／300） （ x3x5） （ abcd） （1／41／41／41／400） （ x3x6） （ abcd） （1／41／41／41／400） （ x3x7） （ bcd） （01／31／31／300） （ x4x5） （ acd） （1／301／31／300） （ x4x6） （ acd） （1／301／31／300） （ x4x7） （ cd） （001／21／200） （ x5x6） （ a） （1000000） （ x5x7） （ a） （1000000） （ x6x7） （ a） （1000000） 为了进一步验证本算法的有效性从世界著 名的测试数据库 UCI 中挑选了3个典型的数据 库利用本文提出的算法做测试测试结果如图1 所示． 图1 属性约简对比图 Fig．1 Results of attributes reduction 4 结论 根据原始信息表应用粗糙集中的不可分辨 关系将原始信息表转换成差别向量组．由于在差 别向量中定义了频率向量同时又根据相应的定 理证明定义了差别向量的加法运算因此本算法 大大降低了算法的时间复杂．经典的基于分辨矩 阵的属性约简算法如 Hu 的差别矩阵方法［8］ 求 核属性的时间复杂度为 O（ n 2m）n＝card（ u） m＝card（ c）；而本算法只是通过对差别向量进行 一次扫描就能将核属性识别出来算法的时间复 杂度最大仅为 O（ nm）．同时在识别核属性的过 程中通过差别向量的加法运算形成了数目少却 具有典型代表意义的差别属性集这样将大大降 低寻找属性约简集的搜索范围．从数值实例和数 据库运算结果可以看出本文的算法是有效可 行的． 参 考 文 献 ［1］ Pawlak Z．Rough set．Int J Comput Inf Sci1982（1）：341 ［2］ 鄂旭高学东武森等．信息表中不完备数据的填补方法． 北京科技大学学报200527（3）：364 ［3］ 鄂旭高学东谭文东等．基于超立方体与信息熵的离散 化方法．北京科技大学学报200527（6）：760 ［4］ 武森高学东Bastian M．数据仓库与数据挖掘．北京：冶 金工业出版社2003 ［5］ 王国胤．Rough 集理论与知识获取．西安：西安交通大学出 版社2003 ［6］ 张文修吴伟志梁吉业等．粗糙集理论与方法．北京： 科学出版社2001 ［7］ Hu X HCercone N．Learning in relational databases：a rough set approach．Comput Intell199511（2）：323 ［8］ Jelonek JKrawiec KSlowinski R．Rough set reduction of attributes and their domains for neural networks．Comput Intell199511（2）：339 ［9］ 苗夺谦．Rough Set 理论中连续属性的离散化方法．自动化 学报200127（3）：296 ［10］ 孟庆生．信息论．西安：西安交通大学出版社1986 ［11］ Wong S K MZiarko W．On optional decision rules in decision tables．Bull Pol Acad Sci198533：693 ［12］ Ohrn A．Discernibility and Rough Sets in Medicine：Tools and Applications ［Dissertation ］．Trondheim：Department of Computer and Information ScienceNorwegian University and Science and Technology1999：53 Vol．28No．6 鄂旭等： 基于扫描向量的属性约简方法 ·607·