基于划分的信息系统属性约简

基于划分的信息系统属性约简 Vo l. 26 No. 12 第 26卷第 12期计算机应用 2006年 12月 Comp u te r App lica tion s D ec. 2006 ( ) 文章编号 : 1001 - 9081 2006 12 - 2961 - 03 基于划分的信息系统属性约简 1 , 2 1 , 2 1 , 2张海云 ,梁吉业 ,钱宇华 ( 1. 计算智能与中文信息处理省部共建教育部重点实验室 ,山西 太原030006; ) 2. 山西大学 计算机与信息技术学院 ,山西 太原 030006 ( )seaddy@ sxu. edu. cn 摘 要 :从信息系统中属性间划分能力不同的角度出发 ,提出了属性左划分和属性右划分的观 点 ,研究了它们的特点与性质 ,给出了在属性划分意义下核属性判定方法 ,设计了一种基于划分的属 性约简算法 ARAB P,并进行了理论和实验仿真 ,结果表明该约简算法在效率上较现有的启发式 算法有显著的提高 。 关键词 :粗糙集 ;属性约简 ;属性划分 ;区分度 中图分类号 : TP311文献标识码 : A A ttr ibu te reduc t ion ba sed on pa r t it ion in in form a t ion sy stem 1 , 2 1 , 2 1 , 2ZHAN G H a i2yun, L IAN G J i2ye, Q IAN Yu2hua ( 1. Key L abora tory of Com pu ta tiona l In telligence and Ch inese Inform a tion P rocessing of M in istry of Educa tion, Ta iyuan S hanx i 030006, Ch ina; )2. S chool of Com pu ter and Inform a tion Technology, S hanx i U n iversity, Ta iyuan S hanx i 030006, Ch ina A b stra c t: B a sed on the viewpo in t tha t a ttribu te s have d iffe ren t p a rtition ab ility, left2p a rtition and righ t2p a rtition of the a ttribu te s we re p ropo sed. Cha rac te ristic s and p rop e rtie s of them we re inve stiga ted. The judgm en t m e thod of co re a ttribu te wa s given in rega rd to the a ttribu te p a rtition view. A new a ttribu te reduc tion a lgo rithm nam ed ARAB P ba sed on a ttribu te p a rtition wa s b rough t fo rwa rd, and the va lid ity of the a lgo rithm wa s illu stra ted by theo re tica l ana lysis and exp e rim en ta l re su lts. Key word s: rough se t; a ttribu te reduc tion; a ttribu te p a rtition; d isce rnb ility degree [ 1 ]( ) ( ) ( ) 利用区分矩阵 可以方便地得到信息系统的核 ,但是基于 , IN D P 是一个等价关系 。关系 IN D P P Α A 决 显然 ( ) 定了 U 的一个划分 , 用 U / IN D P 表示 , 简记为 U / P。 区分矩阵的属性约简算法的时间和空间复杂度都较高 。利用 [ 2 ]()生物仿真算法 例如遗传算法和蚁群优化算法等 进行属性约 在信息系统 S 中 , 若 P, Q Α A , 则 Q 的 P正 定义 3 简可以得到约简结果 ,但是它自身的局限性 ,如函数参数的选 () () 域 PO S Q 定义为 : PO SQ = PX , 其中 , PX 为 X? P P ()X ?U / IND Q 的 P的下近似 。 择 ,约简结果的收敛 ,都直接影响到该类算法的实际应用 。 [ 3 ]本文从区分关系出发 ,利用区分度和相对区分度的概念 定义 4 在信息系统 S 中 , P Α A , 如果 : 刻画了属性对论域对象的区分能力和相对区分能力 ,定义了 ) ( ) () 1IN D P = IN D A ; 属性间的左划分和右划分 。利用属性左右划分的特点可以很 ) ) ( () 2Π P ′< P, IN D P ′? InD A ; 容易得到信息系统的一个约简属性 ,随后基于属性划分的思 则称 P 是 A 的一个约简 。 核属性想 ,给出一种新的属性约简算法 ,并证明该算法是完备的 。理 集是所有约简的交集 。 论分析和实验结果表明 ,该约简算法在效率上较现有的启发 1. 2 区分关系与区分度式算法有显著的提高 。 在信息系统 S 中 , P Α A , U / P = { X, X, , X } , 其中 r 1 2 r pp U 在属性集 P下取值的个数 。显然 , 不同等价类之间表示论域 1 信息系统中的区分关系与区分度 的对象都是可区别的 。属性集 P Α A 中所有可区别的对象序 1. 1 信息系统的基本概念 ( ) 偶决定了一个二元可区分关系 D IS P : [ 2 ]() 定义 1 = U , A , V , f, 一个信息系统 S可以表示为 S ( ) ( ) ( ) ( ) D IS P = { x, xϖ a ? P, f x, a ? f x, a } i j i j | U 表示对象的非空有限集合 , U = { x, x,其中 , x} ; A 表示 1 2 n 容易知道 , 下面性质成立 :属性的非空有限集合 , A = { a, a, , a} ; V = ? , V 是 1 2 m a i a ?A i( ) ( ) 性质 1IN D P ? D IS P = U ×U。 a的值域 ; f表示 U ×A ?V 是一个信息函数 , 即对 x?属 性 i i ( ) ( ) 性质 2当 IN D P = U 时 , D IS P = Ø 。) ( U , Π a? A , 有 f x, a? V 。 i i i a i U 的划分能力 , 而区不可区分关系反映了属性集对论域 [ 2 ]定 义 2 在信息系统 S中 , 每个属性子集 P Α A决定了 分关系则决定了属性集区别对象的能力 。为了更好地反映属 ( ) 一个二元不可区分关系 IN D P : 性集的区分能力 , 下面给出属性区分度的定义 。 ( ) ( ) ( ) ( ) IN D P = { x, xΠ a ? P, f x, a= f x, a } i j i j | () 定义 5 设 S = U , A 是一个信息系统 , P Α A , U / P = ( ) 基金项目 : 国家自然科学基金资助项目 70471003 ; 高等学校博士学科点专项科研 收稿日期 : 2006 - 06 - 14; 修订日期 : 2006 - 08 - 26 ( ) 基金资助项目 20050108004 ;山西省高等学校拔尖创新人才基金 ( ) ( ) 作者简介 :张海云 1980 - ,男 ,山西襄垣人 ,助教 ,硕士研究生 ,主要研究方向 : 粗糙集理论 ; 梁吉业 1962 - ,男 , 山西晋城人 ,教授 , 博 ( ) 士生导师 ,博士 ,主要研究方向 :粗糙集理论 、数据挖掘 、人工智能 ; 钱宇华 1976 - ,男 ,山西晋城人 ,博士研究生 ,主要研究方向 : 粒度计算. 定义 6 给定属性集 P Α A , U / P = { X, X, , X } , 则( ) { X, X, , X } , 属性 P的区分度 D P 定义为 : 1 2 r 1 2 r p p r p 属性 a ? A P对属性集 P决定的划分定义为 :| X U - X i i ? | | || i = 1 [ X / a ]? / a ] ?P / / a = [U / P ] / a = [ X r 1 ( )D P =p )( - 1 U U | | | | P / / a 反映了在已知属性集 P对论域 U 的划分基础上 , 另 5反映了可相互区分的对象对数在最大可区分对象定义 一属性 a对 U / P 中形成的每个等价类的划分过程 , 虽然划分 对数中所占的比重 。 的结果与属性集 P和 a共同对论域 U 形成的划分是相同的 , ( ) 显然 , 当 U / P = { U } 时 , D P 取得最小值 0, 当 U / P =( ) 即 U / IN D P ? a = P / / a, 但这样的划分过程是在已有的划 ( ) { x x ? U } 时 , D P 取得最大值 1。 分基础上完成的 , 因此 P / / a可以降低划分的计算时间 。选择 | 属性集 A 中每个属性对前面属性集产生的划分进行划分 , 最终 () 定理 1 设 S = U , A 是一个 信息系统 , P, Q Α A。若 形成 A 对论域 U 的划分 U /A ,因此有 U /A = a/ / a/ / / / a, ( ) () U /Q < U / P, 则 D P < D Q 。 1 2 m () m = ca rd A 。 证明令 U / P = { X, X, , X } , U /Q = { Y, Y, , 1 2 r 1 2 p () 是 一 个 信 息 系 统 , P, Q Α A , S = U , A 定义 7 设 Y} 。因为 U /Q < U / P, 所以 r< r。因此存在 { 1, 2, , r} r p Q Q Q } , 则属性集 Q 相对于属性集 P 的区分, X U / P = { X, X, r 1 2 p ( 的一个划分 E = { E, E, , E} 满足 X = ? Yj = 1, 2, , 1 2 r i j p j?E i() 度 D Q 定义为 : P r s ) = Y p i r, 且存在某个 E? E满足 E> 0。因此 X jp i ii| | | ?|| 0 0 j jj?E iX X - X i i i ?? | | || i =1 j = 1 ( ) j = 1, 2,, r, 且 : () D Q = p | P ( )- 1 U U r r r | | | | p p Q 2 2 2 j 1 2 s i( )> Y 其中 X ? X /Q = { X , X , , X } 。X = Y i i i i i i j j ? | |?? | | ? | | 1 j = i = 1 i = 1 j?E i() 性质 3 设 S = U , A 是一个信息系统 , P, Q Α A , 如果 故 :() U / P Α U /Q , 则 D Q = 0。 P 2 2 r r p Q Y X j i | | | | 证明从定义 7容易得到 。 1 - < 1 - 2 2 ? ? i = 1 j = 1 U U 利用属性间的相对区分度 , 可以判断属性间的相对重要 | | | | 2 2 r r r r 性 。若一个新属性对原有属性集划分能力不改变 , 即属性间的 p p Q Q XX YY i i j j | | | | | | | | - < - Ζ 相对区分度为 0, 则该属性是不重要的 , 称该属性为原有属性 2 2? ??? i = 1 i = 1 j = 1 j = 1 U U U U | | | | | | | | 集的相对冗余属性 。 2 2 r r r r p p Q Q U X XU Y Y 显然 , 利用这个特点 , 可以去除属性集中对区分能力不改 i j j i | | | | | | | | | | ||- - < Ζ 2 2 2 2 ? ??? , 变的冗余属性 这为约简求解提供方便 。依次选择新属性对前 i = 1 i = 1 j = 1 j = 1 U U U U | | | | | | | | 面属性的划分进行划分 , 删除不改变划分的相对冗余属性 , 就 r p 可以得到一个新的属性集 A ′。属性集 A ′只消除了相对冗余属 r X U - X Q i i ? | | || U - Y Y j j | | || i =1 性 , 但无法保证消除所有的冗余属性 。< Ζ 2 2 ? j = 1 U U | | | | 属性的左划分与右划分3 r r p Q 相对区分度能够反映属性间的相互划分能力 。 X U - X YU -Yi i j j ? | | ||? | | || i = 1 j = 1 < 因此有 : () () 定义 8 设信息系统 S = U , A , P, Q Α A , 若 D Q > P ( )( )- 1 - 1 U U U U | | | | | | | | ( ) 0, 则称 Q 右划分 P, 记为 P / / Q; 若 DP > 0, 则称 P左划分 rQ ( ) () 即 : D P < D Q 。 Q , 记为 Q / / P。 l () 定理 2 设 S = U , A 是一个 信息系统 , P, Q Α A , 则 () 性质 4 设信息系统 S = U , A , P, Q Α A , 下列性质成 ( ) () U /Q = U / P的充要条件是 D P = D Q 。立 : ( ) () ( ) 1 若 Q / / P, 则 D Q < D P ? Q ; 2 相对区分关系与相对区分度r ( ) ( ) ( ) 2 若 Q / / P, 有 D P < D P ? Q 。 l 设在信息系统 S中 , P, Q Α A , U / P = { X, X, 1 2 } , 属, X r p 需要注意的是 , 若 P / / Q 成立 , 通常 Q / / P 不一定成立 , rl () 性集 Q 关于 P 的相对区分关系 D IS Q 定义为 : P 反之亦然 。 ( ) ( )() ( ) f x, P = f x, P and () D IS Q = { x, xϖ a ? Q ,定理 3 设信息系统 S = U , A , P Α A , a ? A - P, 若i j P i j | P / / a, 则对于 Π a? P, a/ / a成立 。 r i i r ( ) ( ) f x, a ? f x, a} i j 证明设 P = { a, a, , a} , U / P = { X, X, , X } 。 1 2 p 1 2 r 属性间的相对区分关系决定了属性集 Q 对属性集 P的相 p ( ) 若 P / / a, 有 D a > 0, 则至少存在一组对象 x, x? X, m对区分能力 , 相对区分能力的大小可以反映属性集 Q 相对属 r P i j m ( ) ( ) ( ) ( ) ? { 1, 2, , r} , 有 x, x| D IS P , 且 x, x?D IS a成 性集 P的重要程度 。 p i j i j ) ) ( ) ( ( 立 。那么对于 Π a? P, x, x| D IS a成立 , 即 D a>() 设信息系统 S = U , A , P Α A , X Α U , 属性 P对 X 的划 i i j i a i 分表示 为 X / P, 划 分 形 成 的 等 价 类 集 合 用 [ X / P ] 表 示 。令 0成立 , 因此 a/ / a成立 , 即属性 a右划分 P 中每一个属性 。 i r [ X / P ] = { X, X, , X} , 则属性集 P对集合 X的区分度为 : 1 2 m 然而 , 定理 3的逆定理有时是不成立的 。设 P Α A , a ?A - m P, 若 Π a? P / / a, 则 P / / a不一定成立 。 i r r X U - X i i ? | | || i =1 X 举例说明如下 , 设 A = { a, a, a } , P = { a, a} , U / a= 1 2 1 2 1 ( )P D= ( )- 1 X X { { x, x} , { x, x, x, x} } , U / a= { { x, x, x, x} , { x, 1 2 3 4 5 6 2 1 2 3 4 5 | | | | X x} } , U / a = { { x, x} , { x, x} , { x, x} } , 显 然 有 a/ / a, ( ) 6 1 2 3 4 5 6 1 r DP 表示属性 P 对集合 X 的区分能力大小 。 2963 第 12期张海云等 :基于划分的信息系统属性约简 a/ / a成立 , 但是有 U / P = U / a, 因此 P / / a不成立 。:令 B 表示已选择的属性集且 B = Ø , I表示等价 初始化 2 r r () 定理 4 设信息系统 S = U , A , P Α A , a ? A - P, 若类集合且 I = U , R 表示约简属性集且 R = Ø , S e表示属性序 P / / a, 则对于 Π a? P, a/ / a成立 。 集且 S e = Ø , se lec ted = fa lse, DA 表示信息系统的区分度 ; l i i l 证明同定理 3可得 。步 骤 1:任意选择属性 a ?A , I = [ I / a ], R = R ? a, B = () () 定理 5 设信息系统 S = U , A , a ? A , 若 A - a / / a, B ? a;r 则 a是属性集 A 的核属性 。 步骤 2:选择属性 b ? A - B , B = B ? b, 利用属性 b依次 X 证明 令 A ′= A - a, 有 A ′/ / a, 根据定理 3的证明思想 , ( ) 右划分 I中的每个等价类 X , 若 D b> 0, 则置 se lec ted = r 则至少存在一组对象 x, x?U , 在属性 a的划分下被区分 , 而 ( ) true, I = I - X ? [ X / b ], 直到属性 b右划分完毕 I中的每 i j x, x在属性集 A ′下没有被区分 , 因此 , 如果去除了属性 a, 那 i j 个等价类 X; 么属性集 A ′对论域 U的划分与属性集 A对论域 U的划分是不 步骤 3:若 se lec ted = true,则 R = R ? b, se lec ted = fa lse, 相同的 , 显然 , 该属性是核属性 。证毕 。 ( ) 转步骤 2, 直到 A - B = Ø ; 计算 DA = D R ; () 同理 , 若 A - a/ / a, 则 a也是属性集 A 的核属性 。 定 l 步骤 4:令 A = R , I = U , R = Ø , se lec ted = fa lse; 理 5给出了寻找核属性的方法 。判断属性 a ?A是否是 步骤 5:将属性集 A 中最右边的属性 a 移至 A 的最左边 , () A 中的核属性 , 只要判断 A - a/ / a 是否成立 , 若右划分成 r A =A - a, R = R ? a, R 对 I划分形成的等价类集合 I, 计算 立 , 则 a是属性集 A 中的核属性 。 ( ) ( ) D R , 若 D R 与 DA 相等 , 则输出属性集 R; () 性 质 5 设信息系统 S = U , A , R Α A 是 A 中的一个约 步骤 6:按照属性集 A 中从左到右的顺序 , 依次选择属性 X 简 , 则对于 Π a ? R , a是 R 中的核属性 。 ( ) b ?A 右划分 I中的每个等价类 I, 若 Db> 0, 则置 se lec ted 由于在约简属性集中 , 每个属性都是必要属性 , 显然性质 ( ) = true, I = I - X ? [ X / b ], 直到属性 b右划分完毕 I中的 5成立 。性质 5同时给出了寻找约简的方法 , 如果能够得到约 每个等价类 X; 简中每一个核属性 , 那么核属性集就是一个约简 。 步骤 7:若 se lec ted = true,则 B = B ? b, se lec ted = fa lse, 下面给出寻找一个约简的核属性的过程 。 转步骤 6, 直到 A - B = Ø , 转步骤 4; 在信息系统 S 中 , 选择属性集 A 中的每一个属性 , 保证选 输出的属性集 R 就是信息系统的一个约简 。 择的属性使 a/ / a/ / / / a成立 , 这样就可以得到一个属 i1 r i2 r r im 4. 3 算法复杂度分析) (性集 A ′= { a, a, , a} , m = ca rd A ′, A ′Α A , A ′中删除 i1 i2 im 在时间复杂度方面 , 步骤 1计算的是属性 a对论域 U的划 了不具有右划分能力的属性 , 根据定理 5, A ′中最右边的属性 分 , 在划 分 之 前 先 对 论 域 对 象 进 行 排 序 , 则 时 间 复 杂 度 为 a就是 A ′中的一个核属性 , 它保证了 U /A ′= U /A , 更重要的 im ) ( O U log U , 步骤 2中选择的属性对先前属性集划分生成 | | | | 是属性 a也是所求约简中的一个核属性 。 im ) ( 的每个等价类 X进行划分 , 时间复杂度为 O X log X , 每 | | | | 在属性集 A ′中 , a/ / a/ / / / a的成立形成了一 i r i+1 r r i+m - 1 [ 4 ] m m 个属性序 S e。属性序的形成是在依次选择属性保持 / / 成 r ( ) 个属性划分总的复杂度为 X log X X = U , 显i i i ? | | | | ? 立的情况下形成的一种属性间的序关系 。如果属性序变化以 i = 1 i = 1 m 后 , a/ / a/ / / / a有可能不成立 。因此属性集 A ′中 i r i +1 r r i +m - 1 然 X log X < U log U , 因此 , 步骤 3时间复杂度i i ? | | | | | | | | 是可能存在冗余属性的 , 而唯一可以确定的是最右边属性 a imi = 1 是一个约简的核属性 。为了确定得到下一个约简的核属性 , 可 ) ( 小于 O A U log U , 同理 , 步骤 5时间复杂度为 U log | | || | | | | 以用属性集 A ′- a中的每个属性按照 A ′中的属性序依次右 im ( ) A ′表示U , 而步骤 6时间复杂度为 O A ′ U log U , | | | | | || || | 划分属性 a, 得到一个新的属性序 S e′, 而属性序 S e′中最右 im 步骤 3得到的属性集的个数 。步骤 7有一个重复过程 , 时间复 边的属性就是另一个核属性 。重复上述过程 , 直到得到约简中 ( ) ) ( 杂度为 O A ′A ′- 1 U log U , 因此 , 整个算法的 | | | | | | | | 的每一个核属性 , 则得到的核属性集就是信息系统 S 的一个 2约简 , 它保证了约简中的每个属性对其他属性都具有右划分 ) ( 时间复杂度为 O A U log U 。这与文献 [ 5 ]中的启发式| | | | | 能力 。 3 2 ) ( 算法的时间复杂度 O A 明显有很大提高 , 而且在启 U | | | | 4 基于划分的信息系统属性约简算法 发式算法中需要计算属性核 , 属性核计算的时间复杂度就为 2 2 4. 1 算法思想 ( ) O A U , 在启发式算法计算出属性核的时候 , 该算法 | | | | 该算法主要分为两个阶段 ,第一阶段根据属性右划分的 已经得到一个约简 , 这是该算法的优势所在 。对于空间复杂度 思想 ,删除所有对右划分没有贡 献的属性 , 生成一个属 性 序 来讲 , 主要表现在等价类集合 I的存储上 , 所以 , 空间复杂度 集 ,计算该属性集的区分度 ,此区分度也是 信息系统的 区 分 ) ( 为 O U 。 | | 度 。在算法的第二阶段 ,选择属性序集最右边的属性并入约 5 实验结果与分析 简属性集中 ,计算当前约简属性集的区分度 ,若与信息系统的 区分度相同 ,则输出约简集 ,否则 ,按照属性序 ,依次在当前约 从 UC I机器学习数据库中选择了 10个属性离散数据库 , 简集形成的划分基础上进行属性右划分 ,删除所有对右划分 使用本文提出的 ARAB P 算法对这些 数据库进行属性 约 简 。 由于本文中的算法是针对信息系统设计的 ,因此 ,在实验中所 没有贡献的属性 ,重复上述过程 ,最后输出的约简属性集就是 处理的数据库如果是决策表 ,那么只选择条件属性集来进行 信息系统一个约简 ,并且该属性集不包含对划分不起作用的 处理 ,最后得到的约简属性个数与决策表的约简属性个数是 属性 ,所以该算法对于计算出的约简集来说是完备的 。 不一 样 的 。实 验 环 境 使 用 的 是 W indow s 2000, CPU2. 4 GH z, 4. 2 算法描述 RAM 256MB , D e lp h i编程 , SQL Se rve r用作后台数据库服务器 。 ( 根据算法 思 想 , 设 计 了 新 的 约 简 算 法 ARAB P A ttribu te为了比较该算法的约简求解的效率 ,分别与文献 [ 5 ]提出基 )R edu tion A lgo rithm B a sed on Pa rtition算法 。 () 下转第 2966页 () 输入 :一个信息系统 S = U, A ,其中 U为论域 , A为属性集 。 输出 :该信息系统一个约简 。 陷 ,结合比例参数调整适当 ,能得到较优的 F值 。实验所用的 6 实验及结果分析 词汇相似度软件只能计算出部分词汇相似度 ,特别是对多字 实验选取了 433 篇 W eb 收集的体育类 短文报道组成文 词组 ,计算能力尤其有限 ; 领域内概念树建立带有主观性 ,真 ( )档集合对 3式的结合模型进行测试 ,其中与“亚运会球类比 正全面反映领域内容需要采用领域专家构建的概念树 ; 词的 赛 ”主有 关 的 有 92 篇 , 输 入 的 查 询 词 为“亚 运 会 球 类 比 同义 、歧义等现象在结合模型中的语义概念检索部分没有考 赛 ”,将“运动会 ”作为“亚运会 ”的父概念 ,将“篮球 ”等几种 ( ) 具体名称作为“球类 ”的子概念 。词汇相似度 D X, Y计算参 虑 ,会对检索结果有一定影响 ;实验中所选查询词的父子概念 α ββ考文献 [ 9 ] ,其中的参数为 = 1. 60、1 = 0. 50、2 = 0120、 没得到权威认证 ,带有主观性 ;另外一些查询词和文档并不适 β(βγ δ 3 = 0. 17、4 = 0. 13、= 0. 20、= 0. 20 参数含义见文献 合语义概念扩展 ,这些都是下一步研究改进的重点 。 参考文[ 3 ]) [ 9 ] ; 文档采用 TF ID F评估函数进行特征选择 ,共选出文档 献 : () ( ) ( ) 集特征词条 词组 577个 ;检准率 P 与检全率 R 的平衡 [ 1 ] FAN XZ, L I HQ , L I L F. H yb rid Ch ine se Info rm a tion R e trieva l Mode l 采用 F值度量 , F越大 , 平衡越好 ; 返回文档取相似度值大于 B a sed on the Com b ina tion of Keywo rd and Concep t [ J ]. Jou rna l of 0108的所有文档 。结果如表 1所示 。 B e ijing in stitu te of techno logy, 2003 , 12: 120 - 123. ()() [ 2 ] 美 MANN IN G CD , 德 SCHU TZE H. 统计自然语言处理基础 表 1 结合模型中不同 a, b取值的实验结果表 [M ]. 苑春法 ,李庆中 ,王昀 ,等译. 北京 :电子工业出版社 , 2005. 335 - 338. a, b a = 1 a = 0. 8 a = 0. 5 a = 0. 2 a = 0 SAL TON G, WON G A , Yang CS. A V ec to r Model fo r A u tom atic In2 [ 3 ] 的取值b = 0 b = 0. 2 b = 0. 5 b = 0. 8 b = 1 () dexing[ J ]. Comm un ication of the ACM , 1975 , 18 11 : 613 - 620. 袁检索模型 结合 结合 结合 语义概念 关键词 [ 4 ] 占亭 ,张爱民 ,张余秋. 基于概念的 W eb信息检索 [ J ]. 计算机 相关文档数 29 31 35 40 44 () 工程与应用 , 2003 , 39 36 : 173 - 181.返回文档数 82 90 104 121 153 [ 5 ] 0. 354 0. 344 0. 337 0. 331 0. 288 ( ) 张敏 ,宋睿华 ,马少平. 基于语义关系查询扩展的文档重构方法检准率 P ( ) 0. 315 0. 337 0. 380 0. 435 0. 478 () 检全率 R [ J ]. 计算机学报 , 2004 , 27 10 : 1395 - 1400. 0. 333 0. 340 0. 357 0. 376 0. 359 F 值 [ 6 ] 知网 [ EB /OL ]. ] h ttp: / /www. keenage. com , 2006. L IN D , PAN TEL P. Concep t d iscove ry from text [A ]. P roceed ings of [ 7 ] Confe rence on Comp u ta tiona l L ingu istic s 2002 [ C ]. Ta ip ei, Ta iwan, 7 结语 2002. 577 - 583. 文中提出基于语义概念检索的向量空间模型 ,其性能较 [ 8 ] 邱树雄 ,李志蜀 , 王娣. 语义网络及其 W eb 信息检索机制研究关键词检索的向量空间模型有所改善 ; 将关键词与语义概念 () [ J ]. 计算机工程 , 2004 , 30 23 : 118 - 120.结合进行信息检索 ,一定程度上弥补了关键词检索的向量空 [9 ] 刘群 ,李素建. 基于《知网 》的词汇语义相似度计算 [A ]. 第三届 间模型的检全率低 ,而概念检索的语义网络的检准率低的缺 中文词汇语意学研讨会集 [ C ]. 2002. ()(上接第 2963页 简集为 { a1, a3, a4, a6, a7, a8, a9, a10, a13, a16, a21, a30 } 注 : ()为了实验显示的方便 , 将原有数据库的属性名依次用 a1 , 于信息熵的启发式约简算法 算法 1进行比较 。实验系统的 ) 实验结果如表 1所示 。 a35表示 。实验结果与理论分析相吻合 , 验证了该算法的可 行性 、高效性 。 表 1 约简算法效果分析 算法 1 ARAB P算法 UC I 属 6 结语 实 数 性 约简后 执行平 约简后 执行平 例 据 分析了属性之间左划分和右划分的特点 ,给出了属性区分 个 均时间 均时间 的属性 的属性 库 数 数 / s / s 个数 个数 能力的度量方法 ,通过不断的属性右划分 ,逐步删除对右划分 B rea st2cance r 没有贡献的冗余属性 ,将约简的求解过程转化为求解某个约简 699 9 9 1. 625 9 0. 984 2w iscon sin 的每一个核属性的过程 ,文中给出的 ARAB P算法的计算复杂 2 Car 1728 6 6 1. 938 6 1. 250 ) ( 度为 O A U log U , 且不存在伪约简 ,并通过实验验证 | | || | | de rm a to logy 366 33 14 14. 687 15 5. 375 了该算法的有效性 。基于属性划分的思想同样可以运用于求 M u sh room 8124 22 15 97. 672 15 74. 719 Che ss and2gam e 3196 36 34 76. 891 32 67. 188 解决策表的相对约简中 ,也是我们下一步的研究工作 。 soybean 307 35 12 8. 875 12 5. 428 参考文献 : 625 4 4 0. 382 4 0. 187 ba lance2sca le [ 1 ] SKOW RON A , RAU SZER C. The d isce rn ib ility m a trice s and func2 Monk1 432 6 6 0. 281 6 0. 250 tion s in info rm a tion system s [ A ]. In te lligen t D ec ision Suppo rt: adu lt + stretch 20 4 4 0. 046 4 0. 031 H andbook of App lica tion s and A dvance s of the Rough Sets Theo ry 20 4 4 0. 047 4 0. 031 ye llow2sm a ll [ C ]. Kluwe r A cadem ic Pub lishe rs, Do rd rech t, 1992. 331 - 362. [ 2 ] 张文修 ,吴伟志 ,梁吉业 ,等. 粗糙集理论与方法 [M ]. 北京 : 科学 从表 1中的数据可以看出 , ARAB P算法相对基于属性核 出版社 , 2001.[ 3, 5 ] 的启发式约简算法 在效率上 有一定优势 , 尤其在处理属 [ 3 ] 梁吉业 ,曲开社 ,徐宗本. 信息系统的属性约简 [ J ]. 系统工程理 性核集不是约简的情况下 ,该算法效率的提高更为明显 。在 () 论与实践 , 2001 , 21 12 : 76 - 80. 处理 de rm a to logy数据 库时 ,算法 1 比 ARAB P 算 法 得 到 的 约 WAN G J , WAN G J. R educ tion a lgo rithm s ba sed on d isce rn ib ility m a2 [ 4 ] 简个数少 1 个 ,但实验验证表明两个算法得到的属性集都是 trix: The o rde red a ttribu te s m e thod [ J ]. Jou rna l of Comp u te r Science 约简 。即使约简集个数相同 ,约简集也可能不同 。ARAB P算 () & Techno logy, 2001 , 16 6 : 489 - 504. 法对 soybean数据库进行约简计算得到的约简集为 { a1, a3, [ 5 ] 王国胤 ,于洪 ,杨大春. 基于条件信息熵的决策表约简 [ J ]. 计算 () 机学报 , 2002 , 25 7 : 759 - 766. a4, a6, a7, a8, a9, a10, a11, a16, a21, a30} , 而算法 1 得到的约