粗糙集方法

第8章集合论方法（一）粗糙集方法8.1粗糙集方法8.1.1粗糙集概念8.1.2属性约简的粗糙集理论8.1.3属性约简的粗糙集方法8.1.4粗糙集方法的规则获取8.1.5粗糙集方法的应用实例8.1.1粗糙集概念粗糙集（RoughSet）是波兰数学家Z.Pawlak于1982年提出的。粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。它用上、下近似两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。上、下近似集可以通过等价关系给出确定的描述，边界域的含糊元素数目可以被计算出来。模糊集（Fuzzy）是用隶属度来描述集合边界的不确定性，隶属度是人为给定的，不是计算出来的。粗糙集理论用在数据库中的知识发现主要体现在：（1）利用等价关系对数据库进行属性约简。（2）利用集合的上、下近似关系获取分类规则。(1)信息表定义信息表S=(U，R，V，)的定义为:U:是一个非空有限对象(元组)集合,U={x1x2…xn},其中xi为对象(元组)。R:是对象的属性集合,分为两个不相交的子集,即条件属性C和决策属性D,R=CDV:是属性值的集合，Va是属性的值域。：是的一个信息函数，它为每个对象x的每个属性a赋予一个属性值，即ffVRUaaVxfUxRa)(,,（2）等价关系定义对于（A中包含一个或多个属性），，它们的属性值相同，即：成立，称对象x和y是对属性A的等价关系，表示为：AaUyUxRA,,)()(yfxfaa)}()(,,),(|),{()(yfxfAaUUyxyxAINDaa（3）等价类定义在U中，对属性集A中具有相同等价关系的元素集合称为等价关系的等价类，表示为：)(AIND)}(),(|{][AINDyxyxA（4）划分的定义在U中对属性A的所有等价类形成的划分表示为：具有特性：（i.）（ii.）当时，（iii.）....}21i][|{，＝，AiixEEAiEjijiEEiEU＝例1体温正常），（体温正常），（体温正常），体温高），体温高），（体温很高}对于属性A（体温）的等价关系有：({Uabc(d(ef}),,(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,{()(ffeeddccbbaadeedcbcabaAIND属性A的等价类有：U中对属性A的划分为：},,{][][][1cbacbaEAAA},{][][2ededEAA}{][3ffEA}}{},,{},,,{{},,{321fedcbaEEEA（1）集合X的下近似定义对任意一个子集属性A的等价类有：或表示等价类中的元素x都属于X，即，则x一定属于X。UXXEAEEXAiii|)(XxxXAA][|)(AixE][)(XAx[]iAEx(2)集合X的上近似定义对任意一个子集，属性A的等价类有：或表示等价类中的元素x可能属于X，即，则x可能属于X，也可能不属于X。UX[]iAExXEAEEXAiii|)(XxxXAA][|)(AixE][)(XAx（3）正域，负域和边界的定义全集U可以划分为三个不相交的区域，即正域（Pos），负域（NEG）和边界（BND）：从上面可见：)()(XAXPosA)()(XAUXNEGA)()()(XAXAXBNDA)()()(XBNDXAXAA用图说明正域、负域和边界，每一个小长方形表示一个等价类。图8.1正域、负域和边界NEG（X）Pos（X）=BND（X）X正域负域边界)(XA任意一个元素，它一定属于X；任意一个元素，它一定不属于X；集合X的上近似是其正域和边界的并集，即对于元素，是无法确定其是否属于X，因此对任意元素，只知道x可能属于X。)(XPosx)(XNEGx)()()(XBNDXPosXAAA)(XBNDx)(XAx（4）粗糙集定义若，即即边界为空，称X为A的可定义集；否则X为A不可定义的，即，称X为A的Rough集（粗糙集）)()(XAXA)(XBND)()(XAXA例2对上例1的等价关系A有集合是粗糙集，计算集合X的下近似、上近似、正域、负域和边界。U中关于A的划分为：有：},,{fcbX{{,,},{,},{}}Aabcdef},{},,{cbcbaX},{},,{cbcbaX可知有：},{edX}{}{ffX}{)(fXA},,,{}{},,{)(fcbafcbaXA()(){}APosXAXf},{)()(edXAUXNEGA},,{)()()(cbaXAXAXBNDA8.1.2属性约简的粗糙集理论属性约简概念在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。约简后的属性集称作属性约简集，约简集通常不唯一。求最小约简集（含属性个数最少的约简集）同样是一个困难问题，实际上它是一个NP-hard问题。研究者提出了很多启发式算法，如基于遗传算法的方法等。（1）约简定义给定一个信息表IT（U，A），若有属性集且满足，称B为A的一个约简。记为red（A）B=red(A)AB)()(AINDBIND（2）核定义属性集A的所有约简的交集称为A的核。记作Core(A)是A中为保证信息表中对象可精确定义的必要属性组成的集合，为A中不能约简的重要属性，它是进行属性约简的基础。()()coreAredA（3）正域定义设决策属性D的划分，条件属性C相对于决策属性D的正域定义为：（4）条件属性C相对于决策属性D的约简定义若，如果，则称c是C中相对于D不必要的，即可约简的，否则称c是C中相对于D必要的。12{,...}nAyyy)_()(jCyCDPosCc)()(}){(DPosDPosCcC（5）条件属性C相对于决策属性D的核定义若，如果R中每一个都是相对于D必要的，则称R是相对于D独立的。如果R相对于D独立的，且，则称R是C中相对于D的约简，记为，所有这样简约的交称为C的D核，记为：一般情况下，信息系统的属性约简集有多个，但约简集中属性个数最少的最有意义。CR)()(DPosDPosCR)(CredD)()(CredCCoreDD属性约简实例气候信息表是4个条件属性（天气a1，温度a2，湿度a3，风a4）和1个决策属性（类别d），见表8.1。NO.属性类别天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N令1）计算缺少一个属性的等价关系}{},,,,{4321dDaaaaC}}14{},13{},12{},11{},10{},9{},8{},7{},6{},5{},4{},3{},2{},1{{)(CIND}}13,12,11,10,9,7,5,4,3{},14,8,6,2,1{{)(DINDUDPosC)(}}13{},14,12{},11{},10{},7.6{},9,5{},8,4{},2{},3,1{{}){\(1aCIND}}14{},13{},12{},11{},9{},7{},6{},10,5{},4{},3{},2{},8,1{{}){\(2aCIND}}14{},13{},12{},11{},9{},8{},7{},6{},5{},10,4{},13,3{},2{},1{{}){\(3aCIND}}13{},12{},11{},10{},9{},8{},7{},6,5{},14,4{},3{},2,1{{}){\(4aCIND计算减少一个条件属性相对决策属性的正域由此可知，属性a2，a3是相对于决策属性d可省略的，但不一定可以同时省略，属性a1和a4是相对决策属性不可省略的，因此：UDPosaC}11,10,9,5,2{)(}){\(1)()(}){\(2DPosUDPoscaC)()(}){\(3DPosUDPoscaCUDPosaC}13,12,11,10,9,8,7,3,2,1{)(}){\(4},{)(41aacCore2）计算同时减少{a2,a3}的等价关系和正域说明{a2,a3}同时是不可省略的。}}12,7{},14,6{},10,5,4{},13,3}.{11,2{},9,8,1{{}),{\(32aaCINDUDPosaaC}14,13,12,10,7,6,5,4,3{)(}),{\(323）在{a2,a3}中只能删除一个属性即存在两个约简：从实例计算可以看出，信息表的属性约简是在保持条件属性相对决策属性的分类能力不变的条件下，删除不必要的或不重要的属性。一般来讲，条件属性对于决策属性的相对约简不是唯一的，即可能存在多个相对约简。}},,{},,,){{(421321aaaaaaCredD8.1.3粗糙集的属性约简方法1．属性依赖度定义信息表中条件属性C和决策属性D，属性D依赖属性C的依赖度为：其中表示正域的元素个数，表示整个对象集合的个数。||/|)(|),(UDPosDCC|)(|DPosC)(DPosC||U的性质：①若＝1，意味着，即已知条件C下，可将U上全部个体准确分类到决策属性D的类别中去，即D完全依赖于C。②若01,则称D部分依赖于C（DRough依赖于C），即在已知条件C下，只能将U上那些属于正域的个体分类到决策属性D的类别中去。),(DC)()(DINDCIND③若＝0，则称D完全不依赖C，即利用条件C不能分类到D中的类别中去。2.属性重要度定义,DA，C为条件属性集，D为决策属性集，a∈，属性a关于D的重要度定义为：其中表示在缺少属性a后，条件属性与决策属性的依赖程度。表示C中缺少属性a后，导致不能被准确分类的对象在系统中所占的比例。CC)},{(),(),,(DaCDCDCaSGF)},{(DaC),,(DCaSGF2.性质（1）∈[0，1]（2）若=0，表示属性a关于D是可省的。因为从属性集中去除属性a后，C-{a}中的信息，原来可被准确分类所有对象仍能准确划分到各决策类中去。),,(DCaSGF),,(DCaSGF),,(DCaSGF（3）≠0，表示属性a关于D是不可省的。因为为从属性集C中去除属性a后，某些原来可被准确分类的对象不再能被准确划分。),,(DCaSGF3.最小属性集概念大多数情况下，数据库中存在一些不重要属性，我们希望找到一个最小的相关属性集，它具有与全部条件属性同样的区分决策属性所划分的决策类的能力，从最小属性集中产生的规则会更简练和更有意义。最小属性集定义：设C，D分别是条件属性集和决策属性集，属性集是C的一个最小属性集，当且仅当并且若P是C的最小属性集，则P具有与C同样的区分决策类的能力。)(CPP),(),(DCDP),(),(,''DPDPPP需要注意的是，C的最小属性集一般是不唯一的，而要找到所有的最小属性集是一个NP问题。在大多数应用中，没有必要找到所有的最小属性集。用户可以根据不同的原则来选择一个他认为最好的最小属性集。8.1.4粗糙集方法的规则获取通过分析U中的两个划分和之间的关系，把C视为分类条件，D视为分类结论，我们可以得到下面的分类规则：{}iCE{}jDY（1）当EYj时，则有：rij：和分别是等价集Ei和等价集Yj中的特征描述。()()ijDesEDesY()iDesE()jDesYI①当EYj=Ei时（Ei完全被Yj包含）即下近似