（计算机应用技术专业论文）基于rough集的序列粒及其在序列挖掘中应用的研究.pdf

摘要 基于r o u g h 集的序列粒及其在序列挖掘中应用的研究 摘要 粒计算是信息处理的一种新的计算模式，涉及到如何利用粒来求解问题的方法，时 日j 序列的挖掘作为数据挖掘的一个课题正引起广泛而深入的注意。论文针对时间序列挖 掘的问题，用粒的观点对时白j 序列进行了粒结构的定义，提出了一套挖掘时序规则的方 法并实现了所有的算法。 论文首先对于时白j 序列作了粒的描述，采用s a x 符号表示不仅仅因为它的适合性， 更重要的是为后面的逻辑推理建立良好的基础。然后对定义好的时序粒进行模式发现， 用基于s a x 距离的相似找出相近的模式，最后提出迭代挖掘的算法找出关联规则。所 实现的算法主要以粒计算理论和r o u 曲理论为基础，并实现了时序r o u g l l 挖掘的平台。 在研究中比较了当定义不同粒度的序列、选用不同的模式发现阀值时对挖掘结果的一些 影响。 论文所做的创新性工作有： 1 、构建了适合于时序挖掘的粒模型 本文在比较了各种表示方法的时| 日j 序列基础上采用一种新的粒表现形式s a x 来 表示时问序列。 2 、提出了一种时序粒的挖掘方法 在构建合适的粒模型基础上，本文提出了一种时序挖掘的方法：利用粒形式的距离 作为量度以发现相近的模式，然后用r o u 曲集的规则发现迭代找出多维时间序列之间的 某种联系。 3 、提出了模式发现算法和时序迭代规则发现算法 时序规则的挖掘要求从多维时自j 序列中找出它们之间的某种联系，是一种无监督的 分类，本文提出的时序迭代规则发现算法很好地实现了这个思想。首先通过s a x 距离作 为俊碴以发现相近的模式，然后从时问序列中发现某些规则进入下一轮规则发现，最后得 到所有时间序列的相关性联系。 关键词粒计算，时间序列挖掘，r o u g h 集，模式发现 a b s t r a c t a p p r o a c ht 0t e m p o r a l g r a n u l e sb a s e do n r o u g hs e ta n di t sa p p l i c a t l o nl nt i m es e r l e s m l n l n g a b s t r a c t g r a n u l a rc o m p u t i n gi san e w p a t t e r no fi n f o r m a t i o nd i s p o s a l ，w h i c hi n v o l v e sam e t h o d o fh o wt ou s eg r a n u l e st os o l v et h e s ep r o b l e m s t i m es e r i e sm i n i n gi sb r i n g i n gt ow i d e s p r e a d a n dt h o r o o 【g ha t t e n t i o na sad a t am i n i n gt o p i c t h i sa r t i c l eh a sn h a d et h ed e s e r i p t i o nw i t ha g r a n u l a rv i e w p o i n to nt h et i m es e r i e s ，p r o p o s e dak i n do fm e t h o dt om i n et i m es e r i e sa n d i m p l e m e n t e da l lt h ea l g o r i t h ma b o u tt h e m t h ep a p e rh a sf i r s tm a d eag r a n u l a rd e s c f i 【p f i o nr e g a r d i n gt h et i m es e r i e s u s i n gt h es a x s y m b o l i cr e p r e s e n t a t i o ni s n o tm e r e l yb e c a u s eo fi t ss u i t a b i l i t y , m o r ei m p o r t a n t l yi st o e s t a b l i s hag o o df o u n d a t i o nf o rt h el a t e rl o g i c a lr e a s o n i n g t h e ni td i s c o v e r st h ep a t t e r nw i t i l d e f i n e dt e m p o r a lg r a n u l e sb a s e do nt h es a xd i s t a n c es i m i l a r i t y , a n df i n a l l yp r o p o s e sa n i t e r a t i o ne x c a v a t i o na l g o r i t h mt od i s c o v e rt h e s er e l a t i v er u l e s i tm a i n l yt a k e sg r a n u l a r c o m p u t i n ga n dr o u g hs e tt h e o r ya saf o u n d a t i o n a n de s t a b l i s h e sar o u g he x c a v a t i o n p l a t f o r ma b o u tt i m es e r i e s i ta l s oc o m p a r e ss o m ei n n u e n c e si nt h er e s e a r c hw h e nd e f i n i n ga d i f f e r e n tg r a n u l a r i t yo f t i m es e r i e s ，o rs e l e c t i n gad i f f e r e n tp a t t e r nv a l v ev a l u e t h ef o l l o w i n gi st h ec r e a t i v ep o i n t si nt h i sp a p e r ： i e s t a b l i s h i n gas u i t a b l eg r a n u l a rm o d e li nm i n i n gt i m es e r i e s t h ep a p e ru s e san e wg r a n u l a rr e p r e s e n t a t i o ns a xt od e s c r i b et i m es e r i e sb a s e do n c o m p a r i n gs o m ek i n d so f r e p r e s e n t a t i o na b o u tt h e s et i m es e r i e s 2 p u t t i n gf o r w a r dam e t h o do f m i n i n gt i m es e r i e sw i t ht e m p o r a lg r a n u l e s o nt h ef o u n d a t i o no fe s t a b l i s h i n gas u i t a b l eg r a n u l a rm o d e l ，t h ep a p e rp u t sf o r w a r da m e t h o do fm i n i n gt i m es e r i e sw i t ht e m p o r a lg r a n u l e s ，t h a ti st os a y , f l 苫tt of i n ds i m i l a r m o d ew i t hd i s t a n c eo fg r a n u l a rr e p r e s e n t a t i o n , t h e ni t e r a t i v e l yd i s c o v e rs o m er e l a t i o n s w i t hr o u g hs e t sr u l eg e n e r a t i o n 3 p r o p o s i n gt h ea l g o r i t h m so fm o d ed i s c o v e r ya n d r u l ed i s c o v e r yo f t i m es e r i e s m i n i n gt e m p o r a lr u l e si st of i n ds o m er e l a t i o n sf r o mm u l t i p l ed i m e n s i o n a lt i m es e r i e s ， s oi ti sak i n do fu n s u p e r v i s e dc l a s s i f i c a t i o n , a n dt h i sp a p e rp r o p o s e sa l la l g o r i t h mo f i t e r a t i o nr u l ed i s c o v e r yw h i c he x c e l l e n t l ya p p l i e st h i si d e a i tf i r s td i s c o v e r ss i m i l a rm o d e b ys y m b o ld i s t a n c es a x t od e c i d es i m i l a r i t y , t h e nf i n ds o m er u l e st on e x tl o o p ，f i n a l l y a c h i e v e ss o m er e l a t i v er e l a t i o n so f a l it h et i m es e r i e s n a b s t r a c t k e yw o r d s ：c r r a n u l a rc o m p u t i n g ，t i m es e r i e sm i n i n g ，r o u g hs e t ，m o d ed i s c o v e r y u i 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 j ：作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华 尔交通人学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 关于论文使用授权的说明 本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 保密的论文在解密后遵守此规定，本论文无保密内容。 本人签名三塾竺望导师签 日期1 b ，w 华东交通大学 硕士学位论文任务书 研究生姓名凌仕勇学号 2 0 0 4 0 4 9 0 0 7 0 1 1 4 学院( 系)信息工程学院 争业计算机应用技术 争业方向人工智能 论文题目基于r o u g h 集的序列粒及其在序列挖掘中应用的研究 要求完成时间2 0 0 6 年1 0 月2 5 日 江西省自然科学基金：基于r o u g h 集的粒计算及其应用的研究( 项 选题来源 目编号：0 4 1 1 0 3 5 ) 丰要研究任务： 1 、建立挖掘时间序列的时序粒模型。 2 、在时序粒模型基础上提出基于r o u g h 集理论的挖掘方法，进而进行模型的验 证与修改。 3 、实现此模型的算法，包括数据的预处理，时序粒表示，数据的约简，规则提 取等等。 接受任务时问2 0 0 6 年2 月26 日学生签名 专pt 争 ，_ ) 导师签名 。形钔力 同期h 曲年、一月 第一章绪论 1 1引言 第一章绪论 人类认识、推理和作决策都是在大量的信息中进行的。一般情况下，信息可分为确 定性信息和不确定性信息，而不确定性信息包括模糊性信息、不精确性信息、不完整性 信息、可变化性信息等等。人类的思维是多样性的，虽然很多思维现象体现为对确定性 信息的处理，然而更多的思维现象却体现了对各种各样的不确定性信息的处理。因此， 真j f 的人工智能系统要能很好反映人脑思维的不确定性并能对各种不确定性信息进行 处理。 纯怠粒是指人们在进行推理和决策的时候，对大量的、复杂的信息通过它们的特征 和属性进行分割，形成一些块，或者说一些类、一些组、一些群等等，即为信息粒。粒 计饽是信息处理的一种新的概念和计算模式，它是税糙集理论、商空间理论、区间计算 等的超集，也是软计算科学的一个分支。它已成为模糊的、不完整的、不精确的及海量 信息处理的重要工具和人工智能研究领域的热点之一 2 0 世纪6 0 年代，美国著名数学家z a d e h 提出模糊集合论。在此基础上，于1 9 7 9 年首次 提出并讨论了模糊信息粒度化问题，推动了模糊逻辑理论及其应用的发展。接着，z a d e h 在1 9 9 6 年提出“词计算理论”【2 i ，标志着模糊粒度化理论的诞生。其旨在解决利用自然 语言，进行模糊推理和判断，以实现模糊智能控制。近期他提出必须开拓这个研究分支 一“词计算( c w ) ”口4 1 ，以为将来的智能计算以及基于词的信息系统计算而建立一个 邢论琏础，实现c w 的方法之一是通过粒计算。词计算理论对因特网上的海量信息资源 的“敛利川白着深远的影响。 r o u g h 集理论5 l 是由波兰科学家p a w l a k 在1 9 8 2 年提出的，主要是处理模糊和不确定 性问题。在处理不确定、不精确的含糊信息方面，r o u g h 集理论具有不需要外界信息或 允验知u l 晌独特优点，近年柬已成功地应用于人工智能、机器学习、数据挖掘、模式识 别和智能信息处理等领域。r o y l g h 集理论中最重要的概念是上、下近似集合，根据在论 域ul ：定义的不分明关系的不同，可以得到不同的上、下近似集合，从而可以形成一个 上、下近似集合的层次体系。而对论域u 进行粒化时，也因为粒化程度的不同选择。可 以形成一个相应的粒的层次体系，粒计算的基本概念就是对论域的粒化。从某种意义来 砸r o u g h 集理论中用到的粒化结构其实就是论域上的一个典型划分，即在论域的粒上 ，找论城r 集的近似集合。 序列挖掘最早是由a g r a w a l l 6 1 于1 9 9 5 年提出的，它的最初动机是发现某一时间段内 客户的购买活动规律，在带有交易时问属性的交易数据库中发现频繁项目序列。目前的 二扛要研究集中于在转换后的数据库中寻找频繁的序列，即大序列。在算法上主要是基于 第章绪论 改进的a p f i o f i 算法如a p f i o r i a l l 算法，a p f i o f i s o m e 算法，g s p 算法等等i l 。 1 2 粒计算的研究现状 s k o w r o n 使用包含度概念研究粒近似空间上的r o u 曲下近似和r o u g i l 上近似，设 x ，y 剑是u 上的两个子集，) ( 至少以p 程度包含于y 记成e 。y ， 形扯加 删肌? 7 唧等 于是粒近似空间是3 元组g a s = ( g s ，g t r ) ：其中 g s = ( e ，o , a v ) ，e 2 g l ，g n 是基本粒的集合，0 = o l ，o m ) 是粒运算的集合 g = g l ，g l 是在e 中的基本粒上使用o 中的运算而得到的合成粒的集合，v ：g g 一【0 ，1 是r o u g h 包含函数，它被解释为一个粒被包含于另一个粒的程度的量度。 c r = g s l , l ，o s h 是信息粒系统族。 t r x r 是r 上的二元传递关系。 由此可在粒近似空间g a s 上建立粒关于t ，的上、下近似集的定义： a p 足口( “s ，p ) = x e u i ( ，( 了) ，x ) p a p 0 ) 其中p q 。 爿j p ( a s ，x ，q ) = ( x u i ( ，( 工) ，j ) q g s l 其中p q s k o w r o n 研究各种近似空间上的r o u g h 上、下近似集的意义在于他在探讨r o u g h 集理论 将在各种环境下的引用，也就是建立r o u g h 集理论在各个专业领域中的应用前景。 近期，基于r o u g h 集理论来研究粒计算尤显活跃p a w l a k t ”】在不分明关系和r o u 曲 隶属函数的基础上，探讨了知识粒的结构和粒度问题。p o l k o w s k i 和s k o w r o n 等人【1 4 1 使用 r o u g hm e r e o l o g y 方法和神经网络技术，在基于知识粒化思想的基础上，提出了一个 r o u g h 神经计算( g n c ) 模型。p e t e r s 等人【”j 使用不分明关系将实数划分为多个子区j 日j ，利 用此划分将一个全域划成若干个网格单元，每个网格单元被看成是一个粒，提出了两个 信息粒之间的邻近关系以及包含关系的度量。l i n t 。6 】使用r o u g l 集中的近似空f b j 作为信息 粒结构，定义了粒隶属函数f x ( x ) ，进而提出了粒f u z z y 集，并得出了一些重要的性质。 j t y a o 和y y y a o l l7 j 使用粒计算模型来学习分类规则，用粒网格来表示学习所得的分类 知识，提出了粒之白j 关联粒网格的一个算法 在国内，张钹和张铃教授提出了基于商空间的粒度计算模型i 碡】，其利用子集来表示概 念，不同粒度的概念就体现为不同粒度的子集，一簇概念就构成空间的一个划分商空 2 第一章绪论 日j ( 知i = 基) ，不同的概念簇就构成不同的商空间。而粒度计算问题，也就等价于研究在给定 知识摹上的各种子集合之间的关系和转换。刘清和黄兆华教授在r o u g h 集理论的基础上 做了粒计算方面的相关研究工作，其所提出的关于“隐含”( 一) 和“等值” o v x u ) 。 定义2 3 ( 信息粒度粗细) 【3 7 1 设倪是论域上关系的全体，且r l ，r 2 e 吼，若对v x , y u ，x r l y - * x r 2 y ，则称r 1 比r 2 细，简记为r 2 r i ，一个关系代表一种分类，因此也可 表示粒度粗细。设r 0 r i r 2 。o 可看出a d 均与 b ，c 无关。 2 3 2 基于二进制数的粒计算 对每个粒中元素都可给出它在全域u 上的位置，用该元素的下标表示。若以下标对 应于二进制的位数，则该粒可用一个二进制数定义，即4 。e u 对应f 二进制数的槲应第 j 位上置l 。显然，二进制的长度恰好等于u 的基数。考虑信息表2 1 ( a ) 的单列关系分类视幽 表2 一l ( a ) 单列关系分类视图 0 b i e c th e i z h t ls h o r t 2s h o r t 3m l i 4 t a l l 5m i d 6m i d 7t a l i 8 s h o r t 用二进制形式来表示如表2 - 1 ( b ) 所示的单列关系位计算视图。 表2 - 1 ( b ) 单列关系位计算视图 0 b i e e t g r a n u l e l1 1 0 0 0 0 0 l 2 1 1 0 0 0 0 0 l 30 0 1 1 0 0 1 0 40 0 i 1 0 0 1 0 5 0 0 0 0 l j o o 6 0 0 0 0 1 1 0 0 70 0 11 0 0 1 0 81 1 0 0 0 0 0 l 9 第二章粒计算与r o u g h 集理论 进而用粒表示如表2 - l ( c ) 所示的单列关系粒计算视图。 表2 一i ( c ) 单列关系粒计算视幽 0 b i e c tg r a n u l e lf 0 1 0 2 0 8 l 2f 0 1 0 2 0 8 3 f 0 3 0 4 0 7 4 f 0 3 0 4 0 7 l 5 f 0 5 0 6 6 f 0 5 ，0 6 l 7 f 0 3 0 4 0 7 8 f 0 1 0 2 0 8 对于多列关系视图，如表2 2 所示的多列关系分类视图。 表2 - 2 多列关系分类视图 o b i e c th e i g h t h a i r e v c s ls h o r tb l o n db l u e 2s h o r tb l o n db r o w n 3t a l lr e db l u e 4t a l id a r kb l u e 5t a l ld a r kb l u e 6l a l lb l o n db l u e 7 t a l i d a r kb r o w n 8s h o r tb l o n db r o w n 对于单个h a i r , 我们有 b l o n d = l1 0 0 0 1 0 1 【r e d = 0 0 1 0 0 0 0 0 【d a r k = 0 0 0 1 1 0 1 0 时j ：单个e y e s 我们有 b l u e = 1 0 1 1 1 1 0 0 ( b r o w n = 9 1 0 0 0 0 1 1 通常的提取关联规则( x ，y ) 过程在这里可描述如下： ( i ) 计算所有可能的x 和y 的组合规则 ( i i ) 统计某种规则出现的支持度 ( i i i ) 找出在给定关系中超过最小支持度的关联规则。 用x n y 表示( x ，y ) ，则格式x n y 可扩充到任意有限多个粒的形式： n j ，n n z 。n kn kn n 艺，以上组合可看成是一条关联规则，而某个规 【| ! l j 的产小就足某此不分明关系的_ 进制数的布尔运算。 从个体的全域到粒的分类计算是产生较少的粒名数据表，再从粒名的数据表对粒进 ”纠【介，j “小炎纠【介数j ：l ：友，这“生的基于二进制的和尔a n d 运算是一种快速提取 关联觇则的锋法易于在计算机上实现。本文所实现的r o u g h 时序挖掘系统的约简与规 0 第二章粒计算与r o u g h 集理论 则提取算法就是基于这种二进制的布尔推理原理实现的，即将时闽序列首先用s a x 符 号串表示( 见本文第三章) ，再将s a x 符号串中的每一个字符用本节所阐述的方法表示 为二进制形式，这样经过编码后的二进制串就利用布尔计算进行r o u g h 集的一序列推 理，晟后得到约简后的关联规则。 2 4r o u g h 集理论 r o u g h 集理论由波兰数学家z p a w l a k 5 j 在1 9 8 2 年提出。它是一种处理含糊和不确定 性的新型数学工具。p a w l a k 建立的r o u g h 集理论有三个部分： ( 1 ) 使用上近似和下近 似表示知识的不确定性；( 2 ) 对数据的约简；( 3 ) 基于r o t l g l l 集的推理。他把那些无 法确定的个体归属于边界线的区域，而这种边界线区域被定义为上近似集和f 近似集的 差集，由于上近似集和下近似集都可以通过不分明关系给出确定的数学公式进行描述 所以含糊( v a g u e ) 元素数目可以被计算出来，即在真假二值之间的含糊程度可以计算出 来。r o u g h 集理论的主要贡献在于它恰好地反映了人们用r o u g h 集方法处理不分明问题 的常规性，即以不完全信息或知识去处理一些不分明现象的能力，或者是依据观察、度 量到的一些不确定性结果而进行分类数据的能力。 r o u 【g h 集理论在人工智能和认知科学研究领域有着十分重要的应用，尤其为机器学 习、知识获取、决策分析。数据库的知识发现、专家系统和模式识别等领域提供了一种 很有效的新的数学方法。 2 4 1 信息系统与决策表 定义2 8 1 4 2 l 令信息系统s = ( u ，a ，矿，厂) ，其中( ，是一个非空有限集，亦被称为个体 的全域；a 是个体属性的非空有限集；y 则是属性4 的值域( 矿= u 屹，屹称为。a 的 口t 值集) ，f 为映射函数( 也称信息函数) ，即f ：u x a _ v ，也可以为 f ( u ，口) = v ( “eu ，a a ，v y ) ，它为每个对象的每个属性赋予一个信息值。 r o u g h 集中的知识系统用决策表的形式表示，决策表的列为属性，行为样本，决策 表中的一个属性对应一个等价关系。其中的属性集r = c u d ，c n d = q ，c 为条件属性， 用于描述对象，d 为决策属性，用于描述分类。 2 4 2 不分明关系、划分、分明矩阵和分明函数 定义2 9 ( 不分明关系) 1 4 2 1 令r 为【，上的二元关系，工、) ，均为u 中的任一对象。 r 为所有与x 具有x r y 关系的y 的集合。若矗同时具有自反性、对称性和传递性。r 第二章粒计算与r o u g h 集理论 被称为是u 上的一种二元等价关系，也是一种不可分辨关系。因此，令任一子集r e ， a 址个体心性的非空有限集；v 则是属性爿的值域( r = u r o ，圪称为口4 的值集) ，厂 卯a 为映剁函数，i i f i ：a 呻v ，也即f ( u ，田= v ( “u ，a a ，v v ) ，它为每个对象的每 个属性赋予一个信息值，则不分明关系可表示为 1 n d ( r ) = ( 工，y ) u u ：v a r ，f ( x ，a ) = f o ，口) ) 。 定义2 1 0 【4 2 1 设关系r 是集合上的一个等价( 不分明) 关系，对每一个口a ，口 关于r 的等价类是集合忸i x r a ，工e 椰，记为【口h ，简记为 川称a 为等价类【叫的表示 元素。形式地，【口】。= 忸l ( 口，功e r 。 定义2 1 1 ( 划分) 4 2 1 给定非空集合彳和非空集合簇s = 4 ，a 2 ，以 ，如果 i 、a = u 彳 2 、a ，n 4 = 巾或者爿= a s ( f ，= 1 , 2 ，m ) 则称集合簇s 为a 的一个划分。 引理2 3 设a 是非空集合，盂是a 上的等价关系。异的等价类集合 口k f a a ) 是 a 的一个划分。 定义2 1 2 ( 分明矩阵) 【4 2 1 设信息系统s = ( u ，a ，v ，门，并置a = a ，a 。) ，用m ( s ) 表4 n x n 阶矩阵( c ，) 称它为s 的分明矩阵，使得 c = 口a f a ( u ，) a ( u ) ，t , ，u j u ，i ，_ ，= 1 ，疗 定义2 1 3 ( 分明函数) 【4 2 1 设信息系统s = ( u ，a ，v ，门，由此确定的分明矩阵为m ( s ) ，其中所有元素c 。的析取式v 。f 的合取称为系统s 的分明函数f ，( 印 2 4 3 近似空间与r o u g h 集 定义2 1 4 1 4 2 矗是论域上的一种不可分辨关系，并将分割为若干互不相交的基 小曾价类e 也称为基本集合( e l e m e n t a r ys e t ) e 妒，en ，= 且 u = u e ( f = 1 , 2 ，n ；j = l ，- ，2 ，彪) 。u r 表示分类的集合，即埘r 2 且，恳，磊 第二章粒计算与r o u g h 集理论 因此，二元对彳s 气u 昱) 构成一个近似空间。由此可知，若x 为u 的一个子集，且 x = u e , ( f = 1 , 2 ，) 则表明能够完全由上关系露的若干个基本等价类丘的并集构 成，因而称子集石是精确集合：否则，它是r o u g h 集合。 当子集腥r o u g h 集合时。它可出论域ui - 的逼近方式来描述。令r c x ) = x r ，则【x 】r 表示r 对l ，进行等价划分所得到的与x 具有不可分辨关系的所有对象的集合即 嘲旷抄u ：x r y 。拥有知识r 的智能体( 人，机器人等) 不能将缸k 中的对象与x 分辨，因 此，防l i 表达了智能体对x e x 的认识程度。 定义2 1 5 1 4 2 】子集x 关于等价关系r 的下近似为星( z ) = 缸u ：r ( x ) x ) ，是论 域u 中一定属于子集x 的所有等价类的元素的并集，下近似也被称为x 的正区域，记 作p o s r ( a 3 = r _ ( x ) 。子集x 关于等价关系r 的上近似为r ( x ) = 缸u ：r ( x ) n x ，表 示所有那些与z 有交的等价类的元素的并集。上近似与下近似之问的差异就构成了x 的 边界区域，定义为：b n r ( x ) = r ( 的一星( 的 论域u 中所有与子集x 完全不相交的等价类的元素的并集构成的x 负区域，记作 n e g r ( x ) 。显然，n e g 。( x ) = u r ( x ) 。因此正区域、负区域和边界区域是，上的 三个互不相交的区域，它们共同组成整个论域u 。正区域的元素完全且一定属于x ，负 区域的元素完全且一定不属于x ，边界区域的元素则可能或部分属于x 。 可见，通过近似空间的概念，r o u g h 集理论就实现了用确定的概念柬描述和定义模 糊概念的功能。正区域和负区域就是确定的，而边界区域就是模糊的。此外，从上面的 边界区域的定义可见，当b n r = 时，r ( x ) = 星( x ) ，则称x 关于矗是精确的或清晰 的：反之，x 关于r 是r o u g h 。近似空间的概念如图2 - 2 所示1 8 l 。 j d = r 弋s c k z 剑 、i0 3 ，入 ” j 留2 - 2 r o u g h 集示意图 f i g 2 - 2f i g u r eo fr o u g hs e t 第一二章粒计算与r o u g h 集理论 2 4 4 核与属性约简 定义2 1 6 ( 独立性) f 4 2 l 对任一r r 是r 中不可约去的，则等价关系r 是独立的， 行则怂年1 l 关的。 定义2 1 7 ( 属性约简) 1 4 2 j 令足为一个等价关系簇，对于 r r ? ：i n d ( r ) = i n d ( r 一 r ) ，则称，荭胄中是可约去的知识；如果p = r f f 是独立的， 则p 是r 中的一个约简。 定义2 1 8 ( 相对约简) 【4 2 1 设p 和q 都是等价关系，如果 p o s i x , c l , ) ( z ，d ( q ) ) = 户0 s ( ，- 册( 肌d ( q ) ) ，则称r ep 是q 可约去的，否则是q 一不可约 去的。 定义2 1 9 ( 核) 4 2 1r 中所有不可约去的关系称为核，由它构成的集合称为r 的核 集，庀为c o r e ( r ) 。 命题2 4p 的所有约简的交集称为p 的核。已作c o r e ( p 户n r e d ( p ) 。其中r e d ( p ) j i ! = p 的所仃约简族。 r o u g h 集决策表中，一个属性就对应着一个等价关系( 也称不分明关系或者不可分辨 天系) 。条件属性和决策属性分别对论域形成了各自的划分，这两个划分构成了条件属 性和决策属性对论域中对象的分类知识。基于r o u g h 集决策分析的数据约简一般需要进 f 列的约简( 属性约简) ，行的约简( 冗余对象的约简) 和属性值约筒三个环节。 属性约简就是从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属 性形成的，相对于决策属性的分类和所有条件属性所形成的，相对于决策属性的分类一 致。通常一个决策表中的条件属性对于决策属性的相对约简不是唯一的。人们往往希望 找jl 仃垃少条什槭性的约简，即最小条件属性 冗余对象的约简是因为决策表经过属性约简之后，表中的规则的适应性大大增强 了。但这罩存在多条样本互相包含了很多冗余信息。属性值约简就是在上述约简的基础 上。进一步从决策表中去掉每条样本的冗余条件属性。在进行属性值约简的时候，由于 处j - b 姚则的顺序不同，或者在一条规则中处理的属性的顺序不同时可能会得到不同的约 筒结果，得到的规则集也可能有所不同。 2 5 基于r o u g h 集的粒语言及语义 i 2 1 s = ( u a ) 足个信息系统，其中u 是所讨论对象的全域，a 是属性集。( a ，v ) 或a 址射彳定义d ! i si ：的一种描述其中a a 是属性集a 上的一个属性，v 是a 关于个体集u 上 的个体x e u 的属性值，也就是v a ( x ) 。- t 是( a 。v ) 或a ，被视为r o u g l l 逻辑中的一个原子公 1 4 第二章粒计算与r o u g h 集理论 式。经典逻辑联结词将诸多( a ，v ) 或a 。组合起来，则可得到r o u 曲逻辑中的合式公式。 m ( 伊) = ( x u ：x f 腰妒 被称做i s 上公式妒的意义集其中符号f i s 是满足或者可能 满足符，即所有满足妒或者可能满足p 的u 上个体的集合，其中m 是意义函数符。因此( 妒， m ( 妒) ) 是i s 上的一个关于伊的基本粒。原子公式a ，的基本粒i s 成( a ，m ( a ，) ) ，被称做基 本粒。显然m ( 伊户被认为伊在i s & 取假m ( 伊) = u 被认为由在i s 上取真；而妒c m ( o ) 卫， 则p 在i s 上为可满足。当p 在u 的任何子集x 卫上不可求其意义集时则m ( 妒) 在i sl ：为 不可观察于是可利用它的下近似粒( b 妒，b ( m ( 妒) ) ) 和上近似粒( b 。妒b ( m ( 旷) ) ) 来近似地表达其意义集b ( m ( 伊) ) 和b ( m ( 妒) ) 。其中b 卧是属性集a 上的一个子集。 如果m ( 伊户 x u ：x 一- - 伊伊 - - 1 3 ( m ( 妒) ) ，其中m 是妒的r o u g h t 意义函数符，则 称伊在i s & 是r o u g h 下真；若m ( 妒户 x e u ：x l d 伊 = 妒，则称p 在i s 上是r d u g h 下假。 如果m ( p ) = x u ：x i ”妒 = b ( m ( 妒) ) ，其中m 是妒的r o u 曲下意义函数符则 称伊在1 s 上是r o u g h 上真：若m ( 妒) = xe u ：x l “r , a ) = 妒。则称伊在i s 上是r o u g h 上假。 如果妒n ( 妒) ：b ( m ( 妒) ) 回( m ( 妒) ) 剑，则称妒在i s 上是r o u 曲可满足的。 定义2 2 0 ( 语法) 4 3 1l 表示t s 上v b 基本粒和粒组成的语言，它的语法被递归定义如 下： ( 1 ) 取自属性子集b a 上形如( a ，v ) 、m ( a ，v ) ) 或( a ，m ( a ，) ) 的基本粒是l m 中的语句。 ( 2 ) 形如下近似粒( b 伊，b ( m ( 伊) ) ) 和上近似粒( b 妒，b ( m ( 妒) ) ) 的粒，其中p 是一个 取自i s 上的描述或原子的布尔组合，当伊中不含r o u g h 逻辑联结词时，它便是一个描述 或原子，则这种形式也是l 。中的语句。 ( 3 ) 若p 和v 是l 肼中的语句，则 ( 仍历( 纠) ，( 妒 ，用( 伊 缈) ) ，( c a r 少，m c c v ) ) ， ( 且卜妒) ，珊( e ( - - 妒) ) ) ，( 占( 妒) ，埘( 占( 伊) ) ) ， ( 且( p ) ，m ( 且( p ) ) ) ，( b ( 伊 ，m ( b 。( 伊 少) ) ) ， ( e ( 妒v ) ，所( 且( 妒v ) ) ) ，( 占。( p v i c ，) ，m c b ( 伊v 妒) ) ) 第二章粒计算与r o u g h 集理论 也都是l 。中的语句。 ( 4 ) 经有限次引用( 1 ) ( 3 ) 得到的语句都被看成是l 。中的语句。 定义2 2 1 ( 语义) 被确定在信息系统i s = ( u ，a ) 上的语言l 。，其语句的语义被递归 定义如下： ( 1 ) m ( a ) = x u ：a ( x ) = - w e v ，其中v 是属性值集，m 为意义函数符，a ( x ) = - v 或可能等 j ：v 的x 均为m ( a 。) 中的元素以下类推： ( 2 ) m ( 妒) - u m ( 伊) ； ( 3 ) m ( 妒 1 l r ) = m ( 妒) nr n ( 1 l ) ； ( 4 ) m ( 妒vi i r ) = m ( 伊) u m ( 1 l ，) 带一和的联结词的语句都可用带和v 或 联结词的语句替换。 定义2 。2 2 ( 粒运算) 1 4 3 1 设和( 妒，用( 铲”( 弘肌( 缈) ) 是两个粒，它们关于联结词( g 否) ， o ( g 析取) ，o ( g 合取) ， ( g 隐含) 和 ( g 等值) 的运算被定义如下： 1 )( 妒，脚( 妒) ) ( 妒，u 一脚( 妒) ) ； 2 ) ( 妒，脚( 妒) ) o ( ，脚( ) ) = ( 妒v ，肌( 妒) u 历( 缈) ) ； 3 )( 妒，肌( 妒) ) 0 ( ，用( ) ) = ( 9a 妒，删( 伊) n 历( 矿) ) ； 4 ) ( 矿，脚( 妒) ) ( y ，m ( 矿) ) = ( 伊 矿，m ( 伊) 研( 缈) ) v ( 脚( p ) m ( 缈) m ( 伊) m ( ) ) ，、( 妒，州( 妒) ) ( ，用( ) ) = ( 伊+ y ，( m ( 伊) 删( ) 所( 缈) 册( 伊) ) v ( ( 耽( p ) m ( 妒) a m ( ) 册( 妒) ) ( 朋( 妒) m ( ) a m ( ) m ( 伊) ) ) ) 其中m 和m 。分别是妒或地定义域的下和上近似算子。 定义2 2 3 ( 粒度粗细) 一个划分而中的每块被包含在划分乃中的每块中定义为 万 及，表示万：比矾相糙。一个覆盖l 的每个粒子被包含在覆盖f ：中的每个粒子中， 定义为r l - kz 2 。表示f 2 比r l 粗糙。 定义2 2 4 ( 粒的度量) 对于公式妒的单个粒m ( 妒) ，g ( 伊) = l m ( 伊) l i u i( 2 - 9 ) 6 第二章粒计算与r o u g h 集理论 对于两个公式p 和y ，矿和之间的联系表示为矽；，则 a c c u r a c y ( j 缈) - 防细 ) ，l m ( 伊) i - i 研似，n m ( i v ) h m ( 9 ) c o v e r a g e ( 1 p = ，妒) = l 肼( 妒八) l i m ( 缈) i = 忉，尹jn 坍，y j m ( ) l 对于公式簇= 。 它隐含了一个划分 ，( 缈) = 历( yt ) ，r a ( 。) ) ， 设妒辛定义了伊和