·36· 智能系统学报 第1卷 l5)fX∈f(x)orXy∈f(x)Then 51)End if 16)f(x)的属性值X或者XY记为空值，原 52)For对于Mark中的每个格结点hm=(O, f(x一f(x) D',w)按D1降序排列Do 17)Generate() 53)If存在h EMark使得D'Cinter Then增 18)End if 加边Nw-hm: 19)Else 54)f存在hm是h.的双亲Then删去边ha 20)fX∈f(xW、Y∈f(x)Then +hm i 21)f(x)的属性值X、Y记为空值，原f(x)→ 55)End if f(x‘) 56)End for 22)Generate() 57)End if 23)End if 58)End Gennew() 24)End if 算法分析： 25)End if 在上述CCLA算法中，不但只根据新追加对象 26)End CCLA 内涵与原格内涵的交集结果，而且还要根据用户关 27)(Generate() 心和不关心的属性子集的组合决定格节点的生成， 28)ForL,中的每个格结点h,=((O,D),P列 用户不感兴趣的属性子集的内涵的格结点将不被生 按！Dl升序排列Da*更新约束概念*/ 成 29)IfD∈f(x)Then 对于一个新对象h:={x,f(x,w子，最多可能 30)0:=0U{x}; 存在2个内涵包含于f(x)的概念.因此，当所有 31)MarkMark U(h) 原始形式背景的行对象的属性都包含用户关心的属 32)IfD=f(x)Then退出For循环；Else 性集时，无节点被删除.根据文献[8]建格算法分析 33)调用过程Gennew0; 可知，若设1∫(x)丨=k,则算法的复杂度为 34)End if O21U1).而在实际应用中，对象x具有的属性内 35)End for 涵并不都是用户感兴趣的，不包含用户关心的属性 36)End Generate() 集的对象不进行渐进式构造，在实际概念格的构造 37)Gennew() 中，随着要处理数据量的增大，」U川的量减少，生成 38)f输入用户关心的属性子集X、X八Y或者 的节点数将明显减少，算法的复杂度要小于 XVy Then O21U1).同样地，在实际应用中，当生成用户定 39)inter:=Dnf(x划： 义的不含有某属性子集的内涵的格结点时，含有某 40)Else 属性子集的内涵的格结点将不被生成，随着要处理 41)inter:=D nf(x 数据量的增大，f(x)即k的量减少，因此，算法的复 42)Endif 杂度远小于021U1).所以，该算法能有效地节省 43)If inter≠Φ 概念格的存储空间和建格时间 44)f用户输入的子集为XVY,Then 5实验分析 45)If X Einter or y Einter Then/*约束新增 概念*1 当前我国正在建造一台大天区面积多目标光纤 46)f不存在h:∈Mark使得Dk:=inter Then 光谱望远镜（简称LAMOST),它是国家“九五”计 47)N,=(OUyx,inter);/*N,新增结点*/ 划重大工程项目，总投资达235亿人民币.由于 48)End if LAMOST具有以较高效率大规模测量天体光谱的 49)Mark:Mark UN,: 能力，可提供的研究课题将遍及天文学多个层次，从 50)增加边h.-N,: 恒星、银河系、星系、星系团、活动星系核，直到宇宙 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net15) If X ∈f ( x) or X Y ∈f ( x) Then 16) f ( x) 的属性值 X 或者 XY 记为空值 , 原 f ( x) →f ( x 3 ) 17) Generate () 18) End if 19) Else 20) If X ∈f ( x) 、Y ∈f ( x) Then 21) f ( x) 的属性值 X 、Y 记为空值 ,原 f ( x) → f ( x 3 ) 22) Generate () 23) End if 24) End if 25) End if 26) End CCLA 27) ( Generate () 28) For L r 中的每个格结点 h r = ( ( O , D) , P) 按| D| 升序排列 Do/ 3 更新约束概念 3 / 29) If D Α f ( x) Then 30) O : = O ∪{ x} ; 31) Mark : = Mark ∪{ hr} ; 32) If D = f ( x) Then 退出 For 循环 ; Else 33) 调用过程 Gennew () ; 34) End if 35) End for 36) End Generate () 37) Gennew () 38) If 输入用户关心的属性子集 X 、X ∧Y 或者 X ∨Y Then 39) inter : = D ∩f ( x) ; 40) Else 41) inter : = D ∩ f ( x 3 ) ; 42) Endif 43) If inter ≠Φ 44) If 用户输入的子集为 X ∨Y , Then 45) If X ∈inter or Y ∈inter Then/ 3 约束新增 概念 3 / 46) If 不存在 hk ∈Mark 使得 Dk : = inter Then 47) N r = ( O ∪{ x} ,inter) ;/ 3 N r 新增结点 3 / 48) End if 49) Mark : = Mark ∪N r ; 50) 增加边 hx ←N r ; 51) End if 52) For 对于 Mark 中的每个格结点 hm = ( O′, D′, w′) 按| D′| 降序排列 Do 53) I f 存在 h m ∈Mark 使得 D′< inter Then 增 加边 N w ←hm ; 54) If 存在 hm 是 h x 的双亲 Then 删去边 hx ←hm ; 55) End if 56) End for 57) End if 58) End Gennew () 算法分析 : 在上述 CCLA 算法中 ,不但只根据新追加对象 内涵与原格内涵的交集结果 ,而且还要根据用户关 心和不关心的属性子集的组合决定格节点的生成 , 用户不感兴趣的属性子集的内涵的格结点将不被生 成. 对于一个新对象 hx = { x , f ( x) , w′} ,最多可能 存在 2 f ( x) 个内涵包含于 f ( x) 的概念. 因此 ,当所有 原始形式背景的行对象的属性都包含用户关心的属 性集时 ,无节点被删除. 根据文献[8 ]建格算法分析 可知 , 若 设 | f ( x ) | = k , 则 算 法 的 复 杂 度 为 O(2 2 k | U| ) . 而在实际应用中 ,对象 x 具有的属性内 涵并不都是用户感兴趣的 ,不包含用户关心的属性 集的对象不进行渐进式构造 ,在实际概念格的构造 中 ,随着要处理数据量的增大 , | U| 的量减少 ,生成 的节 点 数 将 明 显 减 少 , 算 法 的 复 杂 度 要 小 于 O(2 2 k | U| ) . 同样地 ,在实际应用中 , 当生成用户定 义的不含有某属性子集的内涵的格结点时 ,含有某 属性子集的内涵的格结点将不被生成 ,随着要处理 数据量的增大 , f ( x) 即 k 的量减少 ,因此 ,算法的复 杂度远小于O(2 2 k | U| ) . 所以 ,该算法能有效地节省 概念格的存储空间和建格时间. 5 实验分析 当前我国正在建造一台大天区面积多目标光纤 光谱望远镜 (简称 LAMOST) ,它是国家“九五”计 划重大工程项目 ,总投资达 2135 亿人民币. 由于 LAMOST 具有以较高效率大规模测量天体光谱的 能力 ,可提供的研究课题将遍及天文学多个层次 ,从 恒星、银河系、星系、星系团、活动星系核 ,直到宇宙 · 63 · 智 能 系 统 学 报 第 1 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net