基于联系度粗糙集的不完备信息系统属性约简

《基于联系度粗糙集的不完备信息系统属性约简》由会员分享，可在线阅读，更多相关《基于联系度粗糙集的不完备信息系统属性约简（4页珍藏版）》请在金锄头文库上搜索。

1、计算机科学2 0 0 7 V 0 1 3 4 N o 8 A 基于联系度粗糙集的不完备信息系统属性约简* ) A t t r i b u t eR e d u c t i o ni nI n c o m p l e t eI n f o r m a t i o nS y s t e m sB a s e do nC o n n e c t i o nD e g r c ：eR o u g hS e t 李华雄周献中黄兵杨佩 ( 南京大学控制与系统X - 程系南京2 1 0 0 9 3 ) A b s t r a c tA ni n x o 脚e dd e f i n i t i o nO nt

2、 o l e r a n tr e l a t i o nb a s e do ne o n m x - e d o nd e g r e ei Sp m p o s e dS Oa st oe n s u r et h er e f l e x i v i t y o fr e h t i o nw i t h o u tl O S So fi n f o r m a t i o n T op r e s e n tt h em e t h o df o rk n o w l e d g er e d u c t i o ni ni n c o m p l e t ei n f o r m

3、a t i o ns y s t e n 毽 b a s e dO nc o n n e c t i o nd e g r e er o u g hs e t ，a i d e n t i c a ld e g r e et o l e r a n tc l a s sr e d u c t i o n ，a - i d e n t i c a ld e g r e ed i s t r i b u t i o nr e d u c t i o n ， w i d e n t i c a ld e g r e ea s s i g n m e n tr e d u c t i o n ，a -

4、 i d e n t i c a ld e g r e eo r d e r e da s s i g n m e n tr e d u c t i o n ，a n da - i d e n t i c a ld e g r e eu p p e r ，1 0 W - e l “ a p p r o 血n n a t i o na r ed e f i n e dr e s p e c t i v e l y ，a n dt h er d a t i o n s h i p sa m o n gt h e ma l ea n a l y z e da n dd i s c u s s e d

5、 T h er e s u l t sw i l l m a k et h ef o u n d a t i o no fk n o w l e d g ea c q u i s i t i o ni nr o u g hs e tr m d db a s e do nc o n n e c t i o nd e g r e e K e y w 吣R o u g hs e t ，S e tp a i r ，C o n n e c t i o nd e g r e e ，I d e n t i c a ld e g r e e ，C o n s i s t e n ts e t ，R e d u

6、 c t i o n 1 引言 自从上世纪8 0 年代波兰学者P a w l a k 等人提出 粗糙集理论 1 2 以来，经典粗糙集理论和方法在众 多实际问题中得到了广泛的应用，并已成为人工智 能、认知科学数据和挖掘研究的基础之一 3 d 。然 而，经典的粗糙集方法主要适用于完备信息系 统每个对象的属性值均已知，而在实际问题中， 信息系统由于数据缺损、数据理解或获取的限制等 原因多是不完备信息系统信息表中有些对象的 属性值未知或不确定。为此，针对经典粗糙集理论 存在的这个问题，K r y s c k i e w i c zM 、JS t e f a n o w k i 和 AT s o u k

7、 e a s 将等价关系放宽为相容关系和相似关 系 卜7 1 ，王国胤提出了限制性相容关系 8 1 ，并以此为 基础提出了相应的不完备信息系统的粗糙集模型与 方法。此外，黄兵和周献中等人结合集对思想 9 , 1 0 】 将联系度的概念引人到相容关系中，提出了基于联 系度的相容关系，并以此为基础提出了基于联系度 的粗糙集模型，更进一步拓展了不完备信息系统的 粗糙集模型 1 1 1 3 。该粗糙集模型的主要优点在于 人们可以根据具体情况调节联系度中同一度的大 小，使相应的粗糙集模型更符合人的主观要求，这与 人机结合，以人为主的系统方法论思想是一致的。 随后，在近几年里有关基于联系度( 集对思想)

8、的粗糙集模型研究逐渐增多起来：赵翔等人提出了 基于加权联系度的粗集模型【1 4 1 ；周辉等人提出了基 于Q 同一度相似关系的粗糙集模型 l s ；刘富春等人 研究了基于集对分析的变精度粗糙集模型6 J 7 】；张 春英等人提出了基于集对分析的单向迁移粗糙集模 型 1 胡；周磊等人提出了基于模糊集对联系度的粗糙 集模型 1 钉；此外，吕丹等人对基于联系度粗糙集模 型作了改进，使其能有效处理空值过多和属性值不 唯一的信息系统 2 0 。从有关文献来看，基于联系度 的粗糙集模型理论与方法在一定范围内已逐渐受到 人们的重视。然而，目前对基于联系度的粗糙集模 型的研究大多停留在模型的建立上，而对于基于

9、联 系度粗糙集的不完备信息系统属性约简理论的研究 较为少见，尤其是系统研究该问题的文献尚未见报 道。为此，本文结合不协调目标信息系统约简理 论 z z , z 3 ，尝试给出基于联系度粗糙集的不完备信息 系统属性约简的系统化概念与有关约简方法。 2 基于联系度的粗糙集模型 2 1 基于联系度的相容关系 定义1r 1 2 3 设O a 2 a 1 ，对于信息系统g = ，定义集值函数P 翟：L 厂一P ( 【厂) ： P 窘( z ) 一 y E Ul u ( x ，了) = 口+ b i ，口+ 6 = 1 ， 口知2 ) ， 这里口，b 分别表示工和y 同一度与差异度。 易知P 宫( z )

10、 事实上定义了一个X U 上的二 元关系： R 磐( z ) = ( z ，y ) L 厂己厂I y E P Y ( z ) 。 若( z ，y ) R , 2 ，则表示z 与Y 相同属性值个数 与总属性个数之比不小于口。，并且工与Y 没有对立 的属性值。 在定义1 中，信息系统S 被替代为S7 ，相应论 * ) 资助项目：国家自然科学基金资助项目( 7 0 5 7 1 0 3 2 ) ，中国博士后科学基金项目( 2 0 0 6 0 3 9 0 9 1 6 ) 江苏省博士后科研资助项目( 0 6 0 1 0 1 9 ( ；) 李华雄博士生，主要研究方向为粗糙集理论与应用、智能信息处理；周献中教

11、授博士牛导师主要研究方向为粗糙集理论与应用、智能综 合自动化系统理论与技术，智能信息处理和信息系统【程等；黄兵博士后，讲师，主要研究方向为粗糙集理论弓应用、模糊粗糙集理论； 杨佩主要研究方向：人工智能、机器学习。 3 9 域U 替换为U ，即剔除那些已知属性个数小于n a 。 的对象，这样处理的目的在于保证二元关系R 吁的 自反性。然而，由于被剔除的对象不在R , 2 讨论范 围内，其中包含的信息也将丢失。为此，需对定义1 作进一步改进，使得基于联系度的相容关系在讨论 信息系统时既不丢失信息又能保证自反性。 定义2 设0 a 1 ，对信息系统S = ( U ，A ， V ，p ，B A ，定义

12、集值函数P ：U _ 一P ( U ) 如下： 咫( z ) 一( Y U I u ( x ，y ) = 口+ b i ，口+ 6 = 1 ，n 口 U z ) ， 这里口，b 分别表示X 和Y 同一度与差异度。与 定义2 类似，这里P 爸( z ) 定义了一个U U 上的二 元关系： R 暑= ( z ，y ) U U I Y P 备( z ) 。 与定义1 相比，定义2 的论域U 中的对象事先 不需作剔除处理，每个对象均在U 售的讨论范围内， 信息没有丢失，同时由于咫( z ) 在原有基础上并上 了 工 ，R 台满足自反性。 2 2 基于联系度粗糙集的上下近似 ， 根据定义2 确定的相容关

13、系，相应的上下近似 集定义如下。 定义3 设o 口1 ，S = U ，A ，V ，厂) ，其中：A = c u D ，C 、D 分别为条件属性集和决策属性集，分 别称R c o ( X ) 和咫( X ) 为X 的a 同一度下近似集和口 同一度上近似集，简称下近似和上近似，其中： 尺爸( X ) = z U I 咫( z ) X ) ， R 芒( X ) = z U IP c ( z ) N X 壬) ， 进一步若有决策属性值非空，且：U R D = D ， D 2 ，矾 ( R D 为决策属性集确定的等价关系，下 m 同) ，则定义相对正域P o 跷( D ) 为：P 0 兜( D ) =

14、U l = I ( D i ) 。 3 基于联系度的粗糙集模型属性约简 属性约简是粗糙集理论研究的核心课题之一， 其目的是在保证信息系统某些关键特征不变的前提 下，删除冗余的属性。按照约简所保留关键特征的 不同，属性约简可以分为多种不同的形式。目前关 于协调目标信息系统的研究已有很多，而实际大量 信息系统为不协调信息系统，对于这类约简的研究 更接近实际，也有学者作了相关研究，取得了有关研 究结果2 厶2 3 1 。事实上，建立在基于联系度的相容关 系上的目标信息系统也常出现不协调的情况。为 此，下面从不协调目标信息系统的角度给出各种基 于联系度的属性约简定义。 3 1 基于联系度的相容类约简

15、定义4 设o 口l ，S = ( U ，C U D ，V ，p ，若B C ，且对V z U 有：P 各( z ) = P 芒( z ) ，则称B 为口 4 0 同一度相容类协调集；若B 为a 同一度相容类协调 集，且B 的任意真子集不是a 同一度相容类协调 集，则称B 为口同一度相容类约简。 由定义4 可知，口同一度相容类约简能够保证 论域中每个对象的a 同一度相容类不变，从而使对 象的自身分类保持不变。而且，a 同一度相容类约 简是保持这种不变性质的约简。易知相容类约简是 条件相当苛刻的，它能保证对象相容类相对于决策 类的分布特征、分配特征、上下近似特征等各种特征 的不变性。 3 2 基于

16、联系度的分布约简 a 同一度相容类约简过于严格，其在实际应用 中并没有太大的价值。而分布约简的要求与相容类 约简相比要宽松一些，下面是基于联系度的分布约 简和最大分布约简定义。 定义5 设O 口1 ，S = ( U ，C U D ，V ，一，并设 决策属性值非空，= D 1 ，D 2 ，风) ，B C ，定 义条件属性子集B 的口同一度分布函数肺( z ) 为： 硒( z ) = ( D ! 泪( z ) ，D 泪( z ) ，D ；：B ( z ) ) ，z u ，其中，聊。B ( z ) ：止牦掣，l i m ，I x l 表 l B 工I 示X 的基数。若对V z U 有：肺( z ) = 膛( z ) ，则 称B 为口同一度分布协调集；若B 为口同一度分布 协调集，且B 的任意真子集不是口同一度分布协调 集，则称B 为口同一度分布约简