第39卷  计  算  机  学  报  Vol.39 2016 论文在线出版号  No.177  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.177 —————————— 本课题得到国家自然科学基金项目(61473030, 61572442, 61203247, 61273304, 61573259, 61472166)和浙江省自然科学基金项目(LY15F020012)资助. 邓大勇, 男, 1968年生, 博士, 副教授, 中国计算机学会(CCF)会员, 主要研究方向为粗糙集理论及应用, Email: dayongd@163.com. 卢克文, 男, 1992年生，硕士研究生，主要研究方向为数据挖掘, Email: 709882771@qq.com . 苗夺谦, 男, 1964年生, 博士, 教授, 主要研究方向数据挖掘、图像处理, Email：dqmiao@tongji.edu.cn. 黄厚宽, 男, 1940年生, 教授, 主要研究方向为数据挖掘、人工智能, Email: hkhuang@bjtu.edu.cn. 知识系统中全粒度粗糙集及概念漂移的研究 邓大勇1), 2), 3)    卢克文1)    苗夺谦3)   黄厚宽4) 1)(浙江师范大学数理与信息工程学院  浙江金华 321004) 2)(浙江师范大学行知学院  浙江金华 321004) 3)(同济大学电子与信息工程学院  上海201804) 4)(北京交通大学计算机与信息技术学院 北京100044)  摘  要 概念漂移探测是数据流挖掘的一个研究重点,不确定性分析是粗糙集理论的研究核心之一. 大数据、数据流中存在不确定变化和概念漂移现象，但是，除F-粗糙集外，几乎所有的粗糙集模型都是静态模型或半动态模型, 专注于各种不确定性研究, 难以处理不确定性变化, 也难以探测概念漂移. 结合量子计算、数据流、概念漂移和粗糙集、F-粗糙集的基本观点，以上、下近似为工具，定义了知识系统中的全粒度粗糙集和上、下近似概念漂移、上、下近似概念耦合等概念, 探讨了全粒度粗糙集的性质, 分析了知识系统内概念的全局变化. 全粒度粗糙集继承了Pawlak粗糙集和F-粗糙集的基本思想，以上、下近似簇为工具表示了概念在知识系统内的各种可能变化. 用嵌套哈斯图表示了概念不同情况下的同一性和差异性:同一层内的表示没有发生概念漂移,不同层之间的表示发生了概念漂移.以正区域为工具，定义了决策表中的全粒度正区域和概念漂移、概念耦合等概念, 探究了全粒度正区域的性质, 分析了决策表内整体概念的全局变化.全粒度正区域表示了决策表中各种可能情况下的正区域,用嵌套哈斯图表示了正区域簇的同一性和差异性:同一层内没有发生相对于正区域的概念漂移,不同层内发生了相对于正区域的概念漂移.在全粒度粗糙集意义下，定义了全粒度绝对约简、全粒度值约简、全粒度Pawlak约简等属性约简，并探讨其性质. 与大部分的属性约简不同(仅仅与并行约简和多粒度约简类似),全粒度属性约简要求保持概念的所有可能表示不发生概念漂移.进一步探讨了属性约简的优缺点,属性约简使得概念的表示变得单一,冗余属性的存在增加了概念表示的丰富性、多样性.在认识论方面,以粗糙集和粒计算为工具分析了人类认识世界的局部性与全局性, 对人类认识世界的方式进行了进一步探讨. 全粒度粗糙集在一定意义下能够表示人类认识的复杂性、不确定性、多样性、层次性和动态性, 在量子计算的帮助下能够实现从一个粒度转跳到另一个粒度，转跳自如毫无困难. 全粒度粗糙集的研究及其中的概念漂移探测为各种条件下的概念漂移探测和人类智能的模拟提供了有益的启示. 关键词   全粒度粗糙集；概念漂移；偏序关系；概念耦合；上、下近似  中图法分类号  TP18 论文引用格式 邓大勇,卢克文,苗夺谦,黄厚宽，知识系统中全粒度粗糙集及概念漂移的研究，2016，Vol.39：在线出版号 No.177 DENG Da-Yong,LU Ke-Wen,MIAO Duo-Qian,HUANG Hou-Kuan，Study on Entire-Granulation Rough Sets and Concept Drifting in a Knowledge System，Chinese Journal of Computers,2016, Vol.39: Online Publishing No.177  网络出版时间：2016-11-29 12:46:40网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161129.1246.004.html 2  计  算  机  学  报  2016年 Study on Entire-Granulation Rough Sets and Concept Drifting in a Knowledge System DENG Da-Yong1),2),3)    LU Ke-Wen1)    MIAO Duo-Qian3)    HUANG Hou-Kuan4) 1)(College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua    321004) 2)(Xingzhi College, Zhejiang Normal University, Jinhua    321004) 3)(School of Electronics and Information Engineering, Tongji University, Shanghai 201804) 4)(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044)  Abstract Concept  drifting  detection  is  one  of  hot  topics  in  data  stream  mining,  and  analysis  of uncertainty  is  dominant  in  rough  set  theory. There  exist  the  change  of  uncertainty  and  concept drifting  in  big  data  and  data  stream.  However,  except  for  F-rough  sets,  almost  all  of  rough  set models are static models or semi-dynamic models, which study on vagueness and uncertainty. It is hard for them to deal with the change of uncertainty, and to detect concept drifting. Combined the ideas of quantum computing, data stream, concept drifting, rough sets and F-rough sets, a rough set  model  for  entire granulations (called  entire-granulation  rough  sets) is  presented,  and  a  lot  of concepts,  such  as  concept  drifting  of  upper  approximation,  concept  drifting  of  lower approximation,  coupling  of  upper  approximation  and  coupling  of  lower  approximation,  etc.  are defined. The  properties  of  entire-granulation  rough  sets  are  investigated,  and  the  change  of uncertainty  for  a  concept  in  a  knowledge  system  is  analyzed  with  these  definitions. Entire-granulation rough sets inherit the basic ideas of Pawlak rough sets and F-rough sets, which describe all of the change of uncertainty for a concept with a family of upper approximations and lower approximations. Embedded Hasse diagram is employed to express the identity and diversity for  a  concept  in  different  cases:   There  exists  no  concept  drifting  for  the  same  level  of  concept expressions  but  exists  concept  drifting  for  the  different  level  of  concept  expressions. With  the positive region, the positive region for entire granulations is defined, and concept drifting, concept coupling are defined in a decision system. The properties of entire-granulation positive region are discussed, and the analysis and measurement for the change of concept uncertainty is conducted. Entire-granulation  positive  region  expresses  all  of  the  positive  regions  in  various  cases  in  a decision system. Embedded Hasse diagram is also employed to express the identity and diversity for the family of positive regions: There exists no concept drifting relative to positive region for the  same  level  of  concepts,  but  exists  concept  drifting  relative  to  positive  region  for  different levels  of  concepts.  In  entire-granulation  rough  sets,  entire-granulation  absolute  reducts, entire-granulation  value  reducts  and  entire-granulation  Pawlak  reducts  are  defined,  and  their properties  are  investigated. Not  like  most  types  of  attribute  reducts(Just  like  parallel  reducts and mutil-granulation conditional attribute reducts), entire-granulation conditional attribute reducts ask for  no  concept  drifting  for  all  of  concept  expressions.  The  advantages  and  faults  of  conditional attribute  reduction  are  further  investigated:  The  unicity  of  concept  expressions is  done  when condition  attribute  reduct is  conducted,  while  the  redundant  conditional  attributes  can  make concept  expression  more  diversity.  From  the  viewpoints  of  epistemology,  the  wholeness  and locality of human thinking are further analyzed with granular computing and rough sets. To some extent, entire-granulation rough sets can express complexity, uncertainty, diversity, hierarchy and  论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  3 dynamic  in  the  process  of  human  cognition.  With  the  help  of quantum  computing,  the  model of entire-granulation rough sets can transform one type of granulation to another fluently. The study on entire-granulation rough sets and concept drifting detection among them can provide heuristic information for various concept drifting detection and simulation of human intelligence.  Key  words  entire-granulation  rough  sets;  concept  drifting;  partial  ordering  relation;  concept coupling; upper and lower approximation 1  引言 现实中的数据往往随着时间的推移而变化，例如，证劵交易数据、微博、视频、传感器数据等，这种类型的数据被称为数据流[1].数据流具有按照时间顺序排列、快速变化、海量甚至无限并且可能出现概念漂移现象等特征[2-7].数据流挖掘是当前数据挖掘研究的一个热点，数据流分类和概念漂移探测是当前数据流挖掘的主要研究方向. 人们在判定、处理问题、形成概念的时候往往根据部分信息或所掌握的信息，而这些信息往往是变化的、不确定的、甚至是错误的,比如: 人们称赞一个女生漂亮,不同的人表达的意义和内涵是不一样的,有人看重其脸庞和肤色,有人注重身材,有人关注气质, 还有人重视品德.粒计算[8,9]是人类智能处理问题的思维方式，也是处理不确定性问题的方法.当前粒计算的主要方法有模糊集[10]、粗糙集[11-13]、商空间[14]和云模型[15]等. 粗糙集理论[11-13]是Pawlak 提出的处理不精确、不完全、含糊数据的数学工具，是数据挖掘和分类的一种重要方法.包括传统的粗糙集理论在内的粒计算理论不太灵活，因而不太适合研究海量的、动态变化的数据，也不太适合研究数据流，更不能从整体上把握数据的变化和人类思维的变化；F-粗糙集[16,17]是第一个动态粗糙集模型，它将粗糙理论从单个信息表或决策表推广到多个，能够把握数据的局部和全局变化，体现了中国古典哲学思想“道生一、一生二、二生三、三生万物”，比较适合研究数据流、概念漂移和数据的变化. 以粗糙集理论为工具研究数据流和概念漂移比较少见.文献[18-19]利用粗糙集上、下近似的变化去度量概念漂移；文献[20]把每个滑动窗口看成是一个决策子表，通过并行约简整体删除冗余属性，然后比较不同子表之间的属性重要性变化探测概念漂移. 文献[21]利用F-粗糙集的思想研究了单个信息表内的概念漂移现象,从粗糙集、粒计算的角度提出了认识收敛等概念.但是这些文献仅仅研究了单个概念或少数几个概念的变化,还不能完全反映人类认识的复杂性和多样性,也不能从全局上把握知识系统(或信息系统)中的概念漂移现象.人类认识世界的方式是极其复杂的,我们猜测人类认识世界的方式也许是一个量子计算的过程，所以需要从全局和局部等多方面把握人类思维的变化. 粗糙集一个非常大的优势是不确定性分析.研究者们提出了上、下近似[11-13]、隶属度[22]、互信息[23]、条件熵[24,25]、粗糙熵、模糊熵[26,27]等不确定性度量指标来刻画和描述数据的不确定性，而且不需要先验知识.文献[28]对定量的不确定性指标进行了分析、比较.所有的粗糙集模型中最原始、最本质、最核心的不确定性分析和度量指标是上、下近似. 经典的概念漂移现象是在数据流中由时间变化而引起的，但是现实的概念漂移或概念的变化不仅仅存在于数据流之中, 也不仅仅是时间变化引起的,更多的情况是由空间或条件变化引发的概念漂移.文献[21]扩展了概念漂移的定义和思想,研究了由空间或条件的变化而引发的概念漂移现象. 基于文献[21]概念漂移的思想,本文结合量子计算的思想,运用数据流、概念漂移和粗糙集、F-粗糙集的基本观点、基本方法，定义了知识系统(或信息表)内概念的全粒度度量和表示,揭示了知识系统(或信息表、决策表)内概念的整体变化和概念漂移. 首先利用上、下近似定义了知识系统内单个概念的上、下近似的概念漂移.其次，结合量子计算的思想,定义了全粒度粗糙集,用粗糙 4  计  算  机  学  报  2016年 集的思想和方法描述概念在知识系统内的全局表示方式，并分析其性质, 指出了它们之间的偏序嵌套关系.第三，在决策表内定义了全粒度正区域、概念漂移、概念耦合等概念，据此，分析了全粒度正区域内的偏序嵌套关系和概念漂移、概念耦合. 第四，定义了全粒度属性约简，包括：全粒度绝对约简、全粒度值约简和全粒度Pawlak约简，初步讨论了它们的性质. 最后，讨论了全粒度粗糙集的认识论意义. 2  基础知识 假设读者具有基本的离散数学知识，本节仅简单介绍粗糙集[11-13]的相关基本知识. 设) , ( A U IS=是一个知识系统，其中U是论域，A是论域U上的条件属性集(或知识). 对于每个属性A aÎ都对应着一个函数aV U a ® :，aV称为属性a的值域，U中每个元素称为个体、对象或行. 对于每一个属性子集A BÍ和任何个体U xÎ都对应着一个如下的信息函数： } : )) ( , {( ) ( B a x a a x InfB Î =. B-不分明关系(或称为不可区分关系)定义为: )} ( ) ( : ) , {( ) ( y Inf x Inf y x B INDB B = =. 任何满足关系) (B IND的2个元素x、y都不能由属性子集B区分，Bx] [表示由x引导的) (B IND等价类.   定义 1. 在知识系统) , ( A U IS=中, 对于任意A aÎ, 如果) ( }) { ( A IND a A IND = -, 则称A aÎ是可约去的, 否则称为必不可少的. 定义 2. 在知识系统) , ( A U IS=中, A BÍ称为IS的约简(绝对约简)iff A BÍ满足下列条件： (1)) ( ) ( A IND B IND =； (2)对于任意B SÌ,都有) ( ) ( A IND S IND ¹. 知识系统IS的所有约简记为) (IS RED,所有约简的交集称为知识系统IS的属性核, 记为) (IS RED I. 属性核中的每个元素称为核属性. 对于知识系统) , ( A U IS=、属性子集A BÍ和论域子集U XÍ(论域子集U XÍ通 常 也 称 为 概 念,  在 决 策 系 统) , , ( d A U DS=中一般情况下可以表示为} ) ( : { 常数 = = x d x X,条件属性子集A BÍ可以称为知识, 我们可以用它表达决策属性表示的概念)，上、下近似、边界域与负区域的个体表示为: } ] [ : { ) , ( ) ( Æ ¹ Ç Î = = X x U x X IS B X BB, }, ] [ : { ) , ( ) ( X x U x X IS B X B B Í Î = = ) , ( ) , ( ) , , ( X IS B X IS B X B IS BN - =, ) , ( ) , , ( X IS B U X B IS NEG - =. 上、下近似、边界域及负区域的信息粒表示分别为： , } ] [ : ] {[ ) , ( ) ( U Æ ¹ Ç Í = = X x U x X IS B X B B B, } ] [ : ] {[ ) , ( ) ( U X x U x X IS B X B B B Í Í = = ) , ( ) , ( ) , ( X IS B X IS B X B BN - =, ) , ( ) , ( X IS B U X B NEG - =. 在 决 策 系 统) , , ( d A U DS=中，Æ = ÇA d} {，决策属性d将论域U划分为块，} , , , { } /{2 1 p Y Y Y d U L =， 其 中) , , 2 , 1 ( p i Yi L =是 等 价 类.决 策 系 统) , , ( d A U DS=的正区域定义为： U} /{) ( ) (d U Yi AiY A d POSÎ=. 有时决策系统) , , ( d A U DS=的正区域 论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  5 ) (d POSA也记为) , ( d DS POSA或) , , ( d A DS POS. 定义3[11-13]. 在决策系统) , , ( d A U DS=中，A BÍ是DS的约简(Pawlak约简)iff A BÍ满足下列条件： (1)) ( ) ( d POS d POSA B =； (2)对于任意B SÌ,都有) ( ) ( d POS d POSB S ¹. 所有DS的 约 简 记 为) (DS RED. ) (DS RED I称为决策系统DS的属性核. ) (DS RED I中的每个元素称为核属性. 根据文献[11-13,29]可知，值约简可定义如下： 定义4. 在决策系统) , , ( d A U DS=中, } , , , { } /{2 1 p Y Y Y d U L =，则A BÍ是} /{d U YÎ的值约简iffA BÍ满足下列条件： (1)) ( ) ( Y A Y B =； (2)对于任意B SÌ都有) ( ) ( Y A Y S ¹.  值约简是保证决策规则中不含冗余条件属性的属性约简. } /{d U YÎ的所有值约简记为) , ( Y DS RED, ) , ( Y DS RED I称为值约简的属性核. ) , ( Y DS RED I中的每个元素称为核属性. 3  知识系统中的概念漂移 在文[21]中我们研究了信息表中的概念漂移，但是它仅仅表示了属性具有包含关系情况下的概念漂移，下面我们将文[19,21]中概念漂移的相关定义进行改造并运用于知识系统中一般情况下的概念漂移及其表示. 定义  5.  设) , ( A U IS=是一个知识系统，U XÍ是其中的一个概念，A BÍ1和A B Í2是两个不同的知识(属性子集)， 则概念U XÍ在不同的知识A BÍ1和A B Í2表示下的上、下近似漂移分别被定义为：     )}, ( ) ( ), ( ) ( { ) , , (1 2 2 1 2 1 X B X B X B X B X B B - - = D )}. ( ) ( ), ( ) ( { ) , , (1 2 2 1 2 1 X B X B X B X B X B B - - = D概念U XÍ在知识A BÍ1和A B Í2表示下的漂移被定义为：)) , , ( ), , , ( (2 1 2 1 X B B X B B D D.  其中，“-”为集合减法.     概念U XÍ的上、下近似漂移表明了概念U XÍ在不同的知识A BÍ1和A B Í2表示下的上、下近似的变化. 概念U XÍ在知识A BÍ1和A B Í2表示下的漂移则由概念U XÍ的上、下近似漂移的序偶来表示. 定义 6. 概念U XÍ在不同的知识A BÍ1和A B Í2表示下的上、下近似漂移量分别被定义为(条件同定义5)： | ) , , ( | ) , , (2 1 2 1 X B B X B B UD = d； | ) , , ( | ) , , (2 1 2 1 X B B X B B UD = d.     概念U XÍ在不同的知识A BÍ1和A B Í2表示下的上、下近似漂移量是概念U XÍ在知识A BÍ1和A B Í2表示下的上、下近似漂移并集的势，即概念U XÍ在知识A BÍ1和A B Í2表示下上、下近似的对称差的势. 概念U XÍ在知识A BÍ1和A B Í2表示下的上、下近似漂移量反映了概念U XÍ在不同表示下的变化量. 定义7. 知识系统) , ( A U IS=中概念U XÍ在不同的知识A BÍ1和A B Í2表示 6  计  算  机  学  报  2016年 下的上、下近似漂移度分别为被定义： | ) ( | | ) ( |) , , () , , (2 12 12 1X B X BX B BX B B d+=d, | ) ( | | ) ( |) , , () , , (2 12 12 1X B X BX B BX B B d+=d.     概念U XÍ的上、下近似漂移度分别表示在不同的知识A BÍ1和A B Í2下的上、下近似的差异程度. ①注：当0 | ) ( | | ) ( |2 1 = + X B X B时，规定0 ) , , (2 1= X B B d. 定义8. 知识系统) , ( A U IS=中概念U XÍ在不同的知识A BÍ1和A B Í2表示下的上、下近似耦合度定义为： ), , , ( 1| ) ( | | ) ( || ) ( ) ( | 2) , , (2 12 12 12 1X B B dX B X BX B X BX B B c- =+Ç=. ) , , ( 1| ) ( | | ) ( || ) ( ) ( | 2) , , (2 12 12 12 1X B B dX B X BX B X BX B B c- =+Ç=       概念的上、下近似耦合度表示概念在不同条件或情况下上、下近似的相似度, 是和上、下近似漂移度相对立的度量指标.  4  单个概念的全粒度粗糙集与概念漂移 一个概念，它既可用外延表示，也可用内涵表示.但概念不一定是精确的，所以粗糙集常用上、下近似来表示和逼近一个概念. 但不同的人、不同的时间、不同的地点对于同一个概念的表达意义可能是不同的. 本节我们以上、下近似为工具研究概念在同一个知识系统中的各种可能变化，即概念的全粒度粗糙集表示.下文规定} { / U U = Æ，即, 当没有任何知识(条件属性或决策属性)时，所有的个体都是不可区分的. 定义 9. 在知识系统) , ( A U IS=中, 概念U XÍ的全粒度上近似、全粒度下近似、全粒度边界区域与全粒度负区域分别定义为： } : ) , ( { ) , ( A B X IS B X IS EAPR Í =； } : ) , ( { ) , ( A B X IS B X IS EAPR Í =； } : ) , , ( { ) , ( A B X B IS BN X IS EBN Í =； } : ) , , ( { ) , ( A B X B IS NEG X IS ENEG Í =. 全粒度上近似、下近似、边界区域与负区域分别是知识系统) , ( A U IS=中概念U XÍ相对于所有属性子集的上近似、下近似、边界区域与负区域的集合. 它们分别是概念U XÍ在知识系统) , ( A U IS=中所有可能的上近似、下近似、边界区域与负区域的集合，是概念U XÍ在知识系统中的所有可能的粗糙集表达方式，也是概念U XÍ在知识系统) , ( A U IS=中所有可能变化的集合.序偶() , ( X IS EAPR,) , ( X IS EAPR)称为概念U XÍ在知识系统) , ( A U IS=中的全粒度粗糙集. 根据需要, 全粒度粗糙集也可以表示为} : )) , ( ), , ( {( A B X IS B X IS B Í，() , , ( X A IS EAPR,) , , ( X A IS EAPR) 或} : )) , , ( ), , , ( {( A B X A IS B X A IS B Í. 例如，设知识系统} , { A U IS=，其中} , { b a A=.U XÍ是知识系统中的一个概念，则： ) , , ( X A IS EAPR )} ( ), ( } { ), ( } { ), ( { X A X b X a X f = )} ( ), ( } { ), ( } { , { X A X b X a f = ) , , ( X A IS EAPR )} ( ), ( } { ), ( } { ), ( { X A X b X a X f =  论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  7 )} ( ), ( } { ), ( } { , { X A X b X a U = 分别用图1，图2表示.         f ) (X f                                           图1. 全粒度下近似) , , ( X A IS EAPR   U ) (X f                          +   ) ( } { X b       +   ) (X A 图2. 全粒度上近似) , , ( X A IS EAPR 与其他粗糙集模型比较，全粒度粗糙集体现了粗糙集动静结合的思想. 除F-粗糙集外,几乎所有的粗糙集模型从本质上来说都是静态的, 虽然不少粗糙集模型被用于研究动态的、增量式的数据挖掘,但是它们往往把动态的、增量式数据放入静态的模型当中，所以这些粗糙集模型在处理动态的、海量的数据方面显得非常局限和力不从心. F-粗糙集主要研究数据量的变化,不涉及关系(或属性)的变化, 全粒度粗糙集则主要研究关系(或属性)的全局与局部变化.全粒度粗糙集的静主要体现在它的上、下近似、边界区域都可以用一个集合的集合来表示； 它的动主要体现在全粒度粗糙集内部，无论是全粒度上近似、还是全粒度下近似的内部都包含概念在不同情况下的所有上、下近似，体现了一种粒度的变化以及概念表示的逼近过程. 全粒度粗糙集定义了概念U XÍ所有粒度层次上的上、下近似，可以体现量子叠加和纠缠，具有一定的量子计算思想. 全粒度粗糙集具有很强的表示能力,表示了概念在各种情况下的可能变化,能够进行并行计算, 但时间复杂性和空间复杂性高是其缺点. 在量子计算的条件下, 量子比特具有超强的表达能力和并行计算能力, 通过量子计算能够在叠加和纠缠中获得所需的上、下近似，体现人类智能的复杂性、不确定性和多样性, 也可以表示人类认识从一个粒度转跳到另一个粒度, 转跳自如, 毫无困难. 例 1.设) , , ( d A U DS=是决策表，如表1所示.a、b、c是条件属性，d是决策属性.令} , 0 ) ( : { U x x d x X Î = =, 则 表1 决策表DS U a b c d 1y 0   1  0  0 2y 1  1  0  1 3y 1  1  0  1 4y 0  1  0  0 5y 1  2  0  0 6y 1  2  0  1 ) ( } { X b ) (X A ) ( } { X a ) ( } { X a +  8  计  算  机  学  报  2016年 U X = Æ ) (；U X a = ) ( } {；U X b = ) ( } {；U X c = ) ( } {；} , , , { ) ( } , {6 5 4 1y y y y X b a =； U X c b = ) ( } , {；U X a c = ) ( } , {；} , , , { ) ( } , , {6 5 4 1y y y y X c b a =；所以， ), ( } { ), ( } { ), ( { ) , ( X b X a X X IS EAPR Æ = ), ( } , { ), ( } , { ), ( } , { ), ( } { X a c X c b X b a X c )} ( } , , { X c b a }} , , , { , {6 5 4 1y y y y U =. Æ = Æ ) (X；} , { ) ( } {4 1y y X a =；Æ = ) ( } { X b；Æ = ) ( } { X c；} , { ) ( } , {4 1y y X b a =；Æ = ) ( } , { X c b， } , { ) ( } , {4 1y y X a c =；} , { ) ( } , , {4 1y y X c b a =；所以， ), ( } { ), ( } { ), ( { ) , ( X b X a X X IS EAPR Æ = ) ( } , { ), ( } , { ), ( } , { ), ( } { X a c X c b X b a X c }} , { , { )} ( } , , { ,4 1y y X c b a Æ =.     下面结合绝对约简、值约简、核属性、概念漂移等, 讨论全粒度粗糙集的性质.      定理 1. 在知识系统) , ( A U IS=中, 概念U XÍ的可能表达方式个数为| |2A；所有可能的概念个数为| |2U(假设U Í Æ也是一个概念，称为空概念). 证明: 在知识系统) , ( A U IS=中，属性A的可能组合方式为A2(A的幂集)，对于每一种组合概念U XÍ都有一种表示方式，所以在知识系统) , ( A U IS=中概念U XÍ的可能表达方式个数为| |2A. 同理，在知识系统) , ( A U IS=中所有可能的概念个数为| |2U. 证毕. 根据定理1，知识系统) , ( A U IS=中所有可能的概念及其表现形式有| | | |2 * 2A U个. 推论1. 决策系统) , , ( d A U DS=中所有可能的概念及其表现形式有| |2 * | |Ad个. 定理2[30].在一个知识系统) , ( A U IS=中 ， 对 于A B B Í Í2 1和U XÍ，有) , ( ) , ( ) , ( ) , (1 2 2 1 X IS B X IS B X IS B X IS B Í Í Í. 推论2.在一个知识系统中) , ( A U IS=中 ， 对 于A B B Í Í2 1和U XÍ，有) ( ) (1 2X BN X BNB B Í. 定义10. 在知识系统) , ( A U IS=中, ) (A P表示A的幂集, A BÍ称为全粒度绝对约简iff A BÍ满足以下2个条件: (1) 对 于 任 意) (1A P AÎ, 存在) (1B P BÎ, 使得 1 1/ / B U A U =； (2)对于任意B SÌ，存在) (1A P AÎ，使得对于任意) (1S P BÎ，都有1 1/ / B U A U ¹. 知识系统中所有全粒度绝对约简的交集称为全粒度绝对约简的属性核, 属性核中的属性称为核属性. 全粒度绝对约简是知识系统中保持每一个属性子集对论域的划分都不变的最小属性子集. 显然, 知识系统绝对约简的核属性一定是全粒度绝对约简的核属性. 定理 3. 在知识系统) , ( A U IS=中,若A BÍ是) , ( A U IS=的全粒度绝对约简, 则对于任意U XÍ都有U XÍ关于A BÍ的 论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  9 全粒度粗糙集等于U XÍ关于A的全粒度粗糙集合. 即: ( ) , , ( X B IS EAPR,) , , ( X B IS EAPR) = ( ) , , ( X A IS EAPR,) , , ( X A IS EAPR  ). 证明: 由于A BÍ,显然有 ) , , ( ) , , ( X A IS EAPR X B IS EAPR Í,) , , ( ) , , ( X A IS EAPR X B IS EAPR Í, 因为A BÍ是) , ( A U IS=的全粒度绝对约简, 所以对于任意) (1A P AÎ,存在) (1B P BÎ,使得对于任意U xÎ都有1 1] [ ] [A Bx x =, 从而有对于任意U XÍ, ) , ( ) , (1 1 X IS A X IS B =且) , ( ) , (1 1 X IS A X IS B =成立. 所以有) , , ( ) , , ( X B IS EAPR X A IS EAPR Í,   ) , , ( ) , , ( X B IS EAPR X A IS EAPR Í.   于是有, ) , , ( ) , , ( X A IS EAPR X B IS EAPR =且) , , ( ) , , ( X A IS EAPR X B IS EAPR =.  证毕. 推论 3. 在知识系统) , ( A U IS=中, 若A BÍ是) , ( A U IS=的全粒度绝对约简, 则对于任意U XÍ和任意) (1 1 A B B B Í Í都有U XÍ关于A B Í1的全粒度粗糙集等于U XÍ关于A的全粒度粗糙集合. 即: ( ) , , (1 X B IS EAPR,) , , (1X B IS EAPR) =( ) , , ( X A IS EAPR,) , , ( X A IS EAPR  ). 知识系统) , ( A U IS=的全粒度绝对约简能保持知识系统中任意U XÍ的全粒度粗糙集不发生改变, 保持知识系统中所有的概念不发生概念漂移, 包括上近似漂移和下近似漂移.  在知识系统) , ( A U IS=中约简全粒度非核属性, 不会改变知识系统中的分类,也不会改变任何概念的上、下近似, 从而不会改变概念的全粒度粗糙集,也不会发生概念漂移.知识系统) , ( A U IS=全粒度核属性的约简,一定会改变知识系统的某些分类, 从而可能改变概念的上、下近似，可能改变概念的全粒度粗糙集，也可能发生概念漂移. 所以,知识系统) , ( A U IS=中全粒度绝对约简是保证所有概念的全粒度粗糙集不发生变化且不发生概念漂移的最小属性子集, 一旦某个核属性被约简,知识系统中的某些概念就会发生概念漂移,从而它们的全粒度粗糙集发生变化. 虽然从值的角度来看,全粒度绝对约简不会改变概念的全粒度粗糙集, 但是冗余属性的存在使得全粒度粗糙集表示得更加丰富多样, 而且冗余属性越多, 约简的个数和可能性更多. 所以, 从来源角度看, 全粒度绝对约简同样改变着概念的全粒度粗糙集, 它使得全粒度粗糙集的表示变得单一. 然而, 对于知识系统) , ( A U IS=和具体概念U XÍ, 有着类似却又不完全相同的情况. 定义 11. 在知识系统) , ( A U IS=中, ) (A P表示A的幂集, U XÍ是一个概念,A BÍ称为概念U XÍ全粒度值约简 iff A BÍ满足以下2个条件: (1) 对 于 任 意) (1A P AÎ, 存在) (1B P BÎ,  使得 ) , ( ) , (1 1 X IS A X IS B =； (2)对于任意B SÌ，存在) (1A P AÎ，使得对于任意) (1S P BÎ，都有 10  计  算  机  学  报  2016年 ) , ( ) , (1 1 X IS A X IS B ¹. 全粒度值约简是保持概念所有属性子集下近似不变的最小属性子集. 所有全粒度值约简的交集称为全粒度值约简的属性核,属性核中的属性称为全粒度值约简的核属性. 显然,概念值约简的核属性是全粒度值约简的核属性. 定理 4. 设) , ( A U IS=是一个知识系统, A BÍ是概念U XÍ的全粒度值约简, 则U XÍ关于A BÍ全粒度下近似等于U XÍ关于A的全粒度下近似. 即: ) , , ( ) , , ( X A IS EAPR X B IS EAPR =. 证明: ) , , ( ) , , ( X A IS EAPR X B IS EAPR Í显然成立.  下面证明: ) , , ( ) , , ( X B IS EAPR X A IS EAPR Í. 因为A BÍ是概念U XÍ的全粒度值约简, 所以对于任意) (1A P AÎ,存在) (1B P BÎ使得) , ( ) , (1 1 X IS A X IS B = 从而有) , , ( ) , , ( X B IS EAPR X A IS EAPR Í.  证毕. 推论4.  在知识系统) , ( A U IS=中, A BÍ是概念U XÍ的全粒度值约简, 则对于任意) (1 1 A B B B Í Í都有) , , ( ) , , (1 X A IS EAPR X B IS EAPR =. 定理 5. A aÎ是知识系统) , ( A U IS=中概念U XÍ值约简的核属性, 则) , , ( ) , , ( X A IS EAPR X B IS EAPR ¹,  其中 } {a A B - =. 证明:  因为A aÎ是 知 识 系 统) , ( A U IS=中概念U XÍ值约简的核属性, 所以有) , ( ) , ( X IS A X IS B ¹,  从 而 有) , , ( ) , ( X B IS EAPR X IS A Ï, 故 , ) , , ( ) , , ( X A IS EAPR X B IS EAPR ¹.  证毕. 知识系统) , ( A U IS=中某个概念U XÍ的全粒度值约简仅能保证概念U XÍ的全粒度下近似不发生变化, 不发生下近似概念漂移； 并不能保证概念U XÍ的全粒度上近似不发生变化, 从而可能发生上近似概念漂移. 知识系统) , ( A U IS=中某个概念U XÍ值约简的核属性也仅仅是相对于下近似而言的, 约简核属性导致下近似发生变化, 从而该概念的全粒度下近似发生变化, 也发生了下近似概念漂移.  下面讨论知识系统) , ( A U IS=中全粒度粗糙集内部之间的关系. 定理 6. 在知识系统) , ( A U IS=中, 概念U XÍ的全粒度上近似、下近似、边界区域与负区域中的元素相对于关系“Í”满足 自 反 、 反 对 称 、 传 递 ， 即( ) , ( X IS EAPR,Í)、() , ( X IS EAPR,Í)、() , ( X IS EBN,Í)、() , ( X IS ENEG,Í)均为偏序集. 证明: 根据关系“Í”性质, 易得. 证毕. ②注：在) , ( X IS EAPR、) , ( X IS EAPR、) , ( X IS EBN、) , ( X IS ENEG中将相等元素看成一个或用一个作为代表. 因 此 ，() , ( X IS EAPR,Í) 、() , ( X IS EAPR,Í)、() , ( X IS EBN,Í)、() , ( X IS ENEG,Í)均可用哈斯图表示. 定理 7. 在知识系统) , ( A U IS=中, 对于概念U XÍ有： (1)) , ( ) ( X IS EAPR X A U =； (2)U ) , ( X IS EAPR U=. 证明: (1)根据定理2, 对于任意的A BÍ都有) ( ) ( X A X B Í, 所 以 有) ( ) , ( X A X IS EAPR Í U；   又 论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  11 ) , ( ) ( X IS EAPR X A Î，所以有) , ( ) ( X IS EAPR X A U Í；于是) , ( ) ( X IS EAPR X A U =.  类似地, 我们可以证明(2). 证毕. 定理8. 在知识系统) ( ,A U IS=中, 对于概念U XÍ， ( ) , ( X IS EAPR,=)、() , ( X IS EAPR，=)、() , ( X IS EBN,=)、() , ( X IS ENEG,=)均为等价关系. 证明: 根据关系“=”的性质, 易得. 证毕. 推论5. 在知识系统) , ( A U IS=中, 对于 概 念U XÍ, ) , ( X IS EAPR/= ，) , ( X IS EAPR/=, ) , ( X IS EBN/=, ) , ( X IS ENEG/=  分别为) , ( X IS EAPR、) , ( X IS EAPR、) , ( X IS EBN和) , ( X IS ENEG相对于相等关系的划分. 对于知识系统) , ( A U IS=中的概念U XÍ, 在全粒度上近似、全粒度下近似、全粒度边界域、全粒度负区域中的等价类是同一个概念的不同表达方式，并没有发生概念漂移；而不同等价类中的表达方式则发生了概念漂移. 定理1表明了同一个概念在知识系统) , ( A U IS=中在不同的知识表示下可能的概念漂移.  ③注：对于知识系统) , ( A U IS=中概念U XÍ全粒度上近似等价类、全粒度下近似等价类、全粒度边界域等价类以及全粒度负区域等价类中的每个元素，它们既相等又不相等. 从值的角度看，等价类中的每个元素都相等；从来源角度看，等价类中的每个元素相互不相等. 于是有： 定理 9. 在知识系统) , ( A U IS=中, 对于概念U XÍ和相等关系对全粒度下近似、全粒度上近似、全粒度边界域及全粒度负 区 域 的 划 分 ) , ( X IS EAPR/= ，) , ( X IS EAPR/=, ) , ( X IS EBN/=, ) , ( X IS ENEG/=，同一个等价类中的概念U XÍ的不同表示方式概念漂移度为0, 不同的等价类中概念U XÍ的不同表示方式概念漂移度大于0. 证明:  根据相关定义,  容易证明该结论. 证毕. 定理 10. 在知识系统) , ( A U IS=中, 对于概念U XÍ和相等关系对全粒度下近似、全粒度上近似、全粒度边界域及全粒度负 区 域 的 划 分 ) , ( X IS EAPR/= ，) , ( X IS EAPR/=, ) , ( X IS EBN/=, ) , ( X IS ENEG/=，在同一个等价类中，每个元素的属性子集相对于关系”Í”构成偏序关系. 对于每个偏序集，每个极小元素为相应的值约简. 证明: 首先，在每个等价类中，所有元素相应的下近似、上近似、边界域或负区域相等；其次，极小元素意味着没有比其更小的元素. 因此,满足值约简的定义. 即定理成立. 证毕. 全粒度上近似、全粒度下近似、全粒度边界域、全粒度负区域中的元素对于关系“=”和“Í”可以构成嵌套哈斯图. 例  2.  续例1. = / ) , ( X IS EAPR、) , ( X IS EAPR/=分别如下： ), ( } { ), ( } { ), ( {{ / ) , ( X b X a X X IS EAPR Æ == )}, ( } , { ), ( } , { ), ( } { X a c X c b X c )}} ( } , , { ), ( } , { { X c b a X b a  . ), ( } { ), ( } { ), ( {{ / ) , ( X b X a X X IS EAPR Æ == ), ( } , { ), ( } { { )}}, ( } , { ), ( } { X b a X a X c b X c )}} ( } , , { ), ( } , { X c b a X a c . 可用嵌套哈斯图表示Í / ) , ( X IS EAPR 12  计  算  机  学  报  2016年 与= / ) , ( X IS EAPR内部（如图3 所示），) , ( X IS EAPR/Í与) , ( X IS EAPR/=内部（如图4所示）： ,) ( x ) ( } { x a ) ( } { x b ) ( } { x c) ( } , { x c b ) ( } ,,{x a c,, ,Æ} {b} {c} , , { c b a } , { b a ) ( } , { x b a ) ( } , , { x c b a } , { a c } , { c b} {a,, Æ 图3. ) ), , ( ( Í X IS EAPR与= / ) , ( X IS EAPR内部的嵌套哈斯图 ) ( x ) ( } { x b ) ( } { x c ) ( } , { x c b, , ,Æ} { b } { c} , { c b) ( } { x a) ( } , { x b a ) ( } , { x a c ) ( } , , { x c b a , ,,} { a} , { b a } , { a c} , , { c b aÆ 图4. （( , ) EAPR IS X,Í）与) , ( X IS EAPR/=内部的嵌套哈斯图 } }, , {{ ) }, , { }, , ({3 2 Æ = D y y X b a c b； }} , { , { ) }, , { }, , ({4 1 y y X b a c b Æ = D； ; 2| ) }, , { }, , ({ | ) }, , { }, , ({=D =U X b a c b X b a c b d; 2| ) }, , { }, , ({ | ) }, , { }, , ({=D =U X b a c b X b a c b d;514 62| ) ( } , { | | ) ( } , { |) }, , { }, , ({) }, , { }, , ({=+=+=X b a X c bX b a c bX b a c b dd; 12 02| ) ( } , { | | ) ( } , { |) }, , { }, , ({) }, , { }, , ({=+=+=X b a X c bX b a c bX b a c b dd;54) }, , { }, , ({ 1 ) }, , { }, , ({=- = X b a c b d X b a c b c. 0) }, , { }, , ({ 1 ) }, , { }, , ({=- = X b a c b d X b a c b c 5  决策系统中的全粒度粗糙集及概念漂移     上述讨论是针对知识系统内单个概念的概念漂移、耦合等进行的，对于整个决策表或信息表来说，这些指标显得非常局限，因为一个决策表或信息表中有多个概念，将多个概念放在一起讨论概念漂移、耦合及其度量是本节讨论的内容. 定义 12. 设) , , ( d A U DS=是一个决策系统，则DS的全粒度正区域定义为：     } : ) , , ( { ) ( A B d B DS POS DS EPOS Í =. 全粒度正区域() EPOS DS可以根据需要记为( , ) EPOS DS A.     DS的全粒度正区域) (DS EPOS是所有条件属性子集正区域的集合. 全粒度正区域具有动静结合、全局与局部相结合的思想. 全粒度正区域是一个全局的集合, 一个集合的集合, 是一种静态. 但全粒度正区域的内部包含很多正区域, 这些不同的正区域是局部的、也是变化的，是一个不断变化的内部过程.     与全粒度粗糙集一样，全粒度正区域的 论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  13 定义也可以体现量子叠加和纠缠，具有一定的量子计算思想. 全粒度正区域表达能力强, 能够表示各种粒度情况下信息粒的正区域, 适合并行计算, 但同样具有时间、空间复杂性高的缺点. 在量子计算情况下, 利用量子比特的叠加和纠缠, 进行并行计算和表示, 通过控制状态的变化获取人们所需的正区域. 所以, 全粒度正区域与全粒度粗糙集一样能够体现人类表达和思维的复杂性、多样性和不确定性, 同样也能够表示人类认识从一个粒度转跳到另一个粒度, 转跳自如, 毫无困难. 定理11[30]. 设) , , ( d A U DS=是一个决策系统, A B B Í Í2 1, 则有 ) ( ) ( ) (2 1d POS d POS d POSA B B Í Í. 定理 12. 设) , , ( d A U DS=是一个决策系统, 则有U ) ( ) ( DS EPOS d POSA =. 证明:  对于任何) ( ) , , ( DS EPOS d B DS POS Î,) ( A BÍ都有) ( ) , , ( d POS d B DS POSA Í,  所以, ) ( ) ( d POS DS EPOSA Í U.  又 因 为) ( ) ( DS EPOS d POSA Î,  所以U ) ( ) ( DS EPOS d POSA Í.  于是, U ) ( ) ( DS EPOS d POSA =. 证毕.     根据上述定理将文[19,21]中的指标进行改造, 我们得到下面概念漂移、概念耦合的度量指标.     定义13. 设) , , ( d A U DS=是一个决策系统, A B Í1和A B Í2， 则决策表中相对于1B、2B的概念漂移定义为： ), ( ) ( { ) , , (1 2 2 1 d POS d POS B B DSB B - = D )} ( ) (2 1d POS d POSB B -.     决策表的概念漂移表示在不同的知识下决策表中正区域的变化. 定义14. 设) , , ( d A U DS=是一个决策系统, A BÍ1和A B Í2, 则决策表中相对于1B、2B的概念耦合度定义为： | ) ( | | ) ( || ) ( ) ( | 2) , , (2 12 12 1d POS d POSd POS d POSB B DS cB BB B+Ç=.     决策表的耦合度表示了在不同的知识下正区域的相似度. 定义15. 设) , , ( d A U DS=是一个决策系统, A BÍ1和A B Í2, 则决策表相对于1B、2B的概念漂移度定义为： | ) ( | | ) ( || ) , , ( |) , , (2 12 12 1d POS d POSB B DSB B DS dB B +D=U ) , , ( 12 1 B B DS c - =. ④注:当0 | ) ( | | ) ( |2 1= + d POS d POSB B, 规定0 ) , , (2 1= B B DS d.0 ) , , (2 1= B B DS d  决策表的概念漂移度表明了在不同的知识下正区域的变化程度. 下文结合决策表中的属性约简、核属性、概念漂移等概念，讨论全粒度正区域的性质.  定义 16. 在决策系统) , , ( d A U DS=中, 设A BÍ是全粒度Pawlak约简 iff A BÍ满足下面2个条件:  (1)) , ( ) , ( A DS EPOS B DS EPOS =； (2)对于任意B SÌ,都有( , ) ( , ) EPOS DS B EPOS DS A ¹. 所有全粒度Pawlak约简的交集称为全粒度Pawlak约简的属性核，属性核中的属性称为全粒度Pawlak约简的核属性. 定理 13. A BÍ是决策系统 14  计  算  机  学  报  2016年 ) , , ( d A U DS=的全粒度Pawlak约简, 则对于任意) (1 1 A B B B Í Í都有) , ( ) , (1 A DS EPOS B DS EPOS =. 证明: 因为) , ( ) , ( A DS EPOS B DS EPOS =,又因为) , ( ) , (1 B DS EPOS B DS EPOS Í且) , ( ) , (1 A DS EPOS B DS EPOS Í,  所以) , ( ) , (1 A DS EPOS B DS EPOS =. 对于全粒度正区域来说, 全粒度Pawlak约简可以减少冗余属性，而不改变全粒度正区域的值, 但是减少了冗余属性的全粒度正区域表示单一，缺乏多样性和灵活性. 定理 14. 设A aÎ是决策系统) , , ( d A U DS=的核属性, 则) , ( ) , ( A DS EPOS B DS EPOS ¹,其中} {a A B - =. 证明: 因为A aÎ是) , , ( d A U DS=的核属性, 所以有) , ( ) , ( d DS POS d DS POSA B ¹, 于是, ) , ( ) , ( B DS EPOS d DS POSA Ï, 因此, ) , ( ) , ( A DS EPOS B DS EPOS ¹. 核属性对于正区域来说是必不可少的, 同样核属性对于全粒度正区域来说也是必不可少的.     定理 15.在决策系统) , , ( d A U DS=中，关系) ), ( ( Í DS EPOS满足自反、反对称和传递， 即关系) ), ( ( Í DS EPOS是偏序关系.     证明: 根据关系“Í”的性质, 易得. 证毕.     ⑤注：) (DS EPOS中正域相等的元素既相等又不相等. 从值来说，正域相等的元素完全相等；但从来源来说，因为正域相等的元素对应的属性子集不相等，所以又可认为它们不相等. 定理 16. 在决策系统) , , ( d A U DS=中,关系) ), ( ( = DS EPOS是等价关系, 对于= / ) (DS EPOS中的每一块，其相应的条件属性子集相对于关系“Í”构成偏序关系，每个偏序关系的极小元为相应等价类的属性约简. 证明: 根据离散数学知识，容易得到= / ) (DS EPOS中的每一块，其相应的条件属性子集相对于“Í”构成偏序关系，下面简单证明定理的后半部分。 在每个等价类中, 所有元素的值都相等, 即正域相等；其次，在每个等价类组成的偏序关系中的极小元素(属性子集)没有其它元素比它更小. 所以, 每个极小元素都为相应等价类的属性约简. 证毕. 对于) ), ( ( Í DS EPOS和= / ) (DS EPOS块内的属性子集而言，它们构成嵌套哈斯图. 即关系) ), ( ( Í DS EPOS构成一个哈斯图, = / ) (DS EPOS块内的属性子集对于关系Í来说构成另一个哈斯图. 定理 17. 在决策系统) , , ( d A U DS=中, 对于= / ) (DS EPOS的等价类, 块内的元素之间概念漂移度等于0；块间元素之间的概念漂移度大于0. 证明：根据相关定义，容易证明这个结论. 证毕. 例 3. 条件与例1同.  Æ =Æ) (d POS；} , { ) (4 1 } {y y d POSa=； Æ = ) (} {d POSb；Æ = ) (} {d POSc；} , , , { ) (4 3 2 1 } , {y y y y d POSb a =；Æ = ) (} , {d POSc b；} , { ) (4 1 } , {y y d POSa c =；} , , , { ) (4 3 2 1 } , , { y y y y d POSc b a =；所以 ), ( ), ( { ) (} { d POS d POS DS EPOSa Æ = ), ( ), ( ), (} , { } { } { d POS d POS d POSb a c b )} ( ), ( ), (} , , { } , { } , { d POS d POS d POSc b a a c c b }} , , , { }, , { , {4 3 2 1 4 1 y y y y y y Æ =,  论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  15 ), ( ), ( {{ / ) (} { d POS d POS DS EPOSb Æ == ), ( { )}, ( ), (} { } , { } { d POS d POS d POSa c b c )}} ( ), ( { )}, (} , , { } , { } , { d POS d POS d POSc b a b a a c  ． = / ) (DS EPOS内部与) ), ( ( Í DS EPOS的嵌套哈斯图表示如下(如图5所示)： Æ} {b} {cc} {b, ) (} {d Posa) (} , {d Posa c) (} {d Posb) (d PosÆ) (} {d Posc) (} , {d Posc b } , { a c} {a) (} , {d Posb a) (} , , {d Posc b a } , , { c b a } , { b a,,,, ,  图5. = / ) (DS EPOS与) ), ( ( Í DS EPOS的嵌套哈斯图 } }, , {{ }) , { }, , { , (3 2 Æ = D y y a c b a DS； = }) , { }, , { , ( a c b a DS d 312 42| ) ( | | ) ( || }) , { }, , { , ( |} , { } , {=+=+Dd POS d POSa c b a DSa c b aU, .32}) , { }, , { , ( 1 }) , { }, , { , (=- = a c b a DS d a c b a DS c 6  认识论意义与讨论 粗糙集理论认为“知识就是分类”. 每个人都具有自己的知识体系，但是，不同的情况下人们掌握的信息不一样， 有时候掌握的信息全面一些，有时候掌握的信息少些，无论哪种情况，我们都要根据自己的知识体系和所掌握的信息做出判断. 全粒度粗糙集可以对应着这种情况，知识系统就是我们所掌握的知识，属性子集就是我们所掌握的信息，我们总是根据我们的知识系统和所掌握的信息做出决策. 通常情况下, 成年人掌握的知识体系比较稳定，不太发生变化, 但是所接受的信息则千变万化，所以做出的决策或选择会有很大的不同. 从认识论和全粒度粗糙集角度看, 全粒度属性约简虽然不会导致全粒度粗糙集或全粒度正区域发生变化, 不改变分类或认识, 但是冗余属性的存在使得认识或表达具有多样性、灵活性和可替换性，因为约简掉冗余属性之后，知识的表达非常单一、非常死板，而且不可替换. 此外, 我们在表达一个概念的时候, 也许我们只是表示这个概念的某些意义, 而不是这个概念的全部意义, 所以同一个概念在不同的情况下由不同的人表示出来的意义会有一定的差异, 接受概念的意义与表达概念的意义也有一定的差异, 这就是概念漂移. 全粒度粗糙集也能够较好地表示这种情况. 另外, 同一个概念的同样意义我们可能用不同的方式表示, 在全粒度粗糙集中的上、下近似等价类可以描述这种情况. 与现有的粗糙集不一样, 全粒度粗糙集表示了知识系统中概念的可能变化, 非常具有灵活性, 更能够表示和分析概念的不确定性与概念漂移. 全粒度粗糙集可以从一个粒度转跳到另一个粒度, 转跳自如，毫无困难,与人类认识世界的方式相吻合. 但是, 在全粒度粗糙集中每一个概念都具有| |2A种表现形式, 在具体情况下如何快速地选择一个我们需要的一种形式, 需要高效的算法或量子算法才能解决.所以,如何用高效的方式存储或表示全粒度粗糙集并快速地找到我们所需要的表达方式? 是我们进一步研究的内容. 7  结论 从量子计算、粒计算、粗糙集和数据流、概念漂移的角度观察知识系统，以上、下近似为工具，本文定义了全粒度粗糙集、概念的上、下近似漂移、上、下近似耦合等概念，分析了知识系统内概念的全局变化与局部变化.从单个概念在知识系统中所有可能的 16  计  算  机  学  报  2016年 粒度层次上分析和度量了概念漂移和概念耦合. 在决策表中定义了全粒度正区域，分析了决策表中所有概念的可能变化和概念漂移. 结合属性约简、核属性和概念漂移等概念，探究了全粒度粗糙集和全粒度正区域的性质.讨论和分析了全粒度粗糙集的认识论意义. 全粒度粗糙集和全粒度正区域在一定程度上能够表示人类认识的复杂性、多变性和不确定性, 也能够在一定程度上表示人类认识粒度的可变性, 从一个粒度转跳到另一个粒度, 转跳顺畅, 毫无困难. 进一步研究为,  在全粒度粗糙集中运用更多的粒计算、粗糙集不确定性分析方法和指标，分析和度量数据流、大数据或知识系统中隐藏的不确定性，并将结果应用于集成分类器与人类智能的模拟. 参 考 文 献 [1] Babcock B, Babu S, Dater M, et al. Models and issues in data stream  systems//  Proceedings  of  the  21st  ACM SIGACT-SIGMOD-SIGART  Symp  on  Principles  Database Systems. New York，USA, 2002: 1-30 [2]  Wang  Tao,  Li  Zhoujun,  Yan  Yuejin,  et  al.  A  survey  of classification of data streams. Journal of Computer Research and Development. 2007, 44(11):1809-1815(in Chinese) (王涛, 李舟军, 颜跃进, 等. 数据流挖掘分类技术综述. 计算机研究与发展, 2007, 44(11):1809-1815) [3]  Xu  Wenhua,  Qin  Zheng,  Chang  Yang.  Semi-supervised learning  based  ensemble  classifier  for  stream  data.  Pattern Recognition  and  Artificial  Intelligence,  2012,  25(2): 292-299(in Chinese) (徐文华, 覃征, 常扬. 基于半监督学习的数据流集成分类算法. 模式识别与人工智能, 2012, 25(2): 292-299) [4] Du L, Song Q, Jia X. Detecting concept drift: An information entropy    based    method  using  an  adaptive  sliding  widow. Intelligent Data Analysis, 2014, 18(3): 337-364 [5] Yeon K, Song   M S, Kim Y, et al. Model averaging via penalized regression for tracking concept drift. Journal of Computational & Graphical Statistics, 2012, 19(19):457-473 [6] Mirza B,    Lin Z,    Liu N. Ensemble of subset online sequential extreme learning machine for class imbalance and concept drift[J]. Neurocomputing, 2015, 149(PA): 316-329 [7] SUN  Xue,  LI  Kun-lun,  HAN  Lei,  et  al. Construction  of  the concept  drift  detection  model  based  on  the information entropy  of  feature  distribution  and  dynamic  weighting algorithm.  ACTA  ELETRONICA  SINICA,  2015,  43(7): 1356-1361(in Chinese)       (孙雪,  李昆仑,  韩蕾,  等.  基于特征项分布的信息熵及特征动态加权概念漂移检测模型.  电子学报,  2015,  43(7): 1356-1361) [8] Hobbs J. R. Granularity//Proceedings of    the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, USA, 1985: 432-435. [9] Lin T. Y. Granular Computing. Announcement of the BASIC Special Interest Group on Granular Computing,   California, USA:Berkeley, 1997.  [10] Zadel L. A.. Fuzzy sets.Information and Control, 1965, 8(3):338-353. [11] Pawlak  Z.  Rough  Sets.  International  Journal  of  Computer and Information Sciences, 1982, 11(5):341-356 [12] Pawlak  Z. Rough  Sets —Theoretical  Aspect  of  Reasoning about  Data.  Dordrecht,  Holland  :Kluwer  Academic Publishers, 1991. [13]  Wang  Guoyin. Rough  Set  Theory  and  Knowledge Acquisition.  Xi’an:  Xi’an  Jiaotong  University  Press, 2001(in Chinese) (王国胤.Rough 集理论与知识获取. 西安:西安交通大学出版社, 2001) [14] Zhang Bo, Zhang Ling. Theories and applications for problem solving. Beijing: Tsinghua University Press, 1990(in Chinese). (张钹,张铃.问题求解理论及应用.北京:清华大学出版社,1990) [15] Li Deyi, Meng Haijun, Shi Xuemei. Membership clouds and Membership  cloud  generators.  Journal  of  Computer  Research and Development, 1995,32(6):16-18(in Chinese). (李德毅，孟海军，史雪梅.隶属云和隶属云发生器.计算机研究与发展，1995,32(6):16-18 ) [16] Deng Dayong, Chen Lin. Parallel reducts and F-rough sets // Cloud  Model  and  Granular  Computing.  Beijing:  Science Press, 2012:210-228(in Chinese) (邓大勇，陈林. 并行约简与F-粗糙集//云模型与粒计算.北京：科学出版社, 2012: 210-228) [17] Chen Lin. Parallel reducts and decision in various levels of granularity[Ph.D.  thesis],  Jinhua,  Zhejiang:  Zhejiang Normal University, 2013(in Chinese)    (陈林. 粗糙集中不同粒度层次下的并行约简及决策[博 论文在线出版号  No.177              邓大勇等：知识系统中全粒度粗糙集及概念漂移的研究  17 士论文].浙江金华:浙江师范大学,2013) [18]  Cao  Fuyuan,  Huang  Joshua  Zhexue.  A  concept-drfting detection  algorithm  for  categorical  evolving  data// Proceedings  of  the 17th  Pacific-Asia  Conf  on  Knowledge Discovery  and  Data  Mining.  Berlin,  Germany, 2013:485-496 [19] Deng Dayong, Pei Minghua, Huang Houkuan. The F-rough sets approaches to the measures of concept drift. Journal of Zhejiang  Normal  University:  Natural  Sciences,  2013, 36(3):303-308(in Chinese)      (邓大勇, 裴明华, 黄厚宽. F-粗糙集方法对概念漂移的度量. 浙江师范大学学报:自然科学版, 2013, 36(3):303-308) [20]  Deng  Dayong,  Xu  Xiaoyu,  Huang  Houkuan.  Concept Drifting  Detection  for  Categorical  Evolving  Data  Based  on Parallel  Reducts.  Journal  of  Computer  Research  and Development, 2015, 52(5): 1071-1079(in Chinese) (邓大勇，徐小玉，黄厚宽. 基于并行约简的概念漂移探测. 计算机研究与发展, 2015, 52(5): 1071-1079) [21] Deng Dayong, Miao Duoqian, Huang Houkuan. Analysis of concept  drifting  and  uncertainty  in  an  information  system. Journal  of  Computer  Research  and  Development, 2016,  53 (11): 2607-2612 (in Chinese). (邓大勇,  苗夺谦,  黄厚宽.  信息表中概念漂移与不确定性分析.  计算研究与发展, 2016, 53 (11): 2607-2612). [22] Z.Pawlak,  A.Skowron.  Rough  membership  functions.  In: R.R.Yager, M.Fedrizzy and J.Kacprzyk eds. Adances in the Dempster  Shafer  Theory  of  Evidence,  New  York,  USA: John Wiley, 1994:.251-271. [23]  Miao  Duoqian,  Hu  Guirong.  A  Heuristic  Algorithm  for Reduction  of  Knowledge.  Journal  of  Computer  Research and Development, 1999, 36(6): 681-684(in Chinese) (苗夺谦，胡桂荣. 知识约简的一种启发式算法. 计算机研究与发展, 1999, 36(6): 681-684)   [24]  Wang  Guoyin,  Yu  Hong,  Yang  Dachun.  Decision  Table Reduction  on  Conditional  Information  Entropy[J].  Chinese Journal of Computers, 2002, 25(7): 759-766(in Chinese) (王国胤，于洪，杨大春. 基于条件信息熵的决策表约简[J]. 计算机学报, 2002, 25(7): 759-766) [25]  Yang  Ming.  Approximate  Reduction  Based  on  Conditional Information  Entropy  in  Decision  Tables.ACTA ELETRONICA  SINICA,  2007,  35(11):  2156-2160(in Chinese) (杨明. 决策表中基于条件信息熵的近似约简.电子学报, 2007, 35(11): 2156-2160) [26]  Liang  J.  Y,  Chin  K.  S,  Dang  C.  Y.  A  new  method  for measuring  uncertainty  and fuzziness  in  rough  set  theory. International  Journal  of  General  Systems,  2002,  31(4): 331-342. [27] Liang Jiye, Li Deyu. Uncertainty and knowledge acquisition in  information  systems.  Beijing:  Science  Press,  2005(in Chinese).       (梁吉业，李德玉.  信息系统中的不确定性与知识获取.  北京:  科学出版社, 2005) [28] Wang Guoyin, Zhang Qinghua. Uncertanty of rough sets in different  knowledge  granularities.  Chinese  Journal  of Computers, 2008, 31(9):1588-1598(in Chinese).       (王国胤,  张清华.  不同知识粒度下粗糙集的不确定性研究.  计算机学报, 2008, 31(9):1588-1598) [29]  Lin  Jiayi,  Peng  Hong,  Zheng  Qilun.  A  new  algorithm  for value reduction  based  on  rough  set.  Computer  Engineering, 2003, 29(4):70-71(in Chinese).       (林嘉宜,  彭宏,  郑启伦.  一种新的基于粗糙集的值约简算法.  计算机工程, 2003, 29(4):70-71) [30]  Qian  Y.  H,  Liang  J.  Y,  Pedrycz  W,  et  al. Positive approximation :  An  accelerator  for  attribute  reduction  in rough set theory. Artificial Intelligence, 2010, 174: 597-618.            18  计  算  机  学  报  2016年 DENG  Da-Yong  ,  born in  1968,  PhD  and  associate professor.  His  main  research interests  include  rough  sets, granular  computing  and  data mining.  LU Ke-Wen , born in 1992, M.S. candidate. His main  research  interests  include  rough  sets,  data mining.                                   MIAO  Duo-Qian  ,  born  in  1964, Ph.D.  ,professor  and  PhD  supervisor.  His  main research  interests  include  rough  sets,  granular computing,  data  mining,  computational  intelligence and image processing.  HUANG  Hou-Kuan,  born  in  1940,  professor and  PhD  supervisor.  His  main  interests  include computational  intelligence,  data  mining  and mutil-agent system.   Background There  exist  many  rough  set  models, including Pawlak  rough  sets,  various  precision  rough  sets, covering  rough  sets,  three-way  decisions, neighborhood rough sets, multi-granulation rough sets and  S-rough  sets  etc.  They  focus  on  uncertainty  and vagueness.  However, it  is  hard  for  these  models  of rough  sets  to  deal  with  the  change  of  uncertainty. Some  researchers  try  to  handle  the  change  of uncertainty  with incremental algorithms,  but  to  some extent  incremental  methods  hide  the  change  of uncertainty. F-rough sets are the first dynamical model of  rough  sets,  which  have  been  employed  to  detect concept  drift  in  data  stream  and  concept  drift  caused by spaces or conditions. In order to address the change of  uncertainty  and  concept  drift,  these  models  of rough  sets  should  be  improved,  and  indexes  of uncertainty should also be improved.                  This paper presents a new rough set model called entire-granulation  rough  sets,  which  extends  Pawlak rough set model from a rough set to a family of rough sets  in  a  knowledge  system(information  system, decision system) from the viewpoints of F-rough sets. Entire-granulation  conditional  attribute  reducts  are defined.  Concept  drifting  is  detected  among entire-granulation  rough  sets.  To  some  extent, entire-granulation  rough  sets  can  express  complexity, uncertainty,  diversity,  hierarchy  and  dynamic  in  the process of human cognition. With the help of quantum computing, the model of entire-granulation rough sets can  transform  one  type  of  granulation  to  another fluently.