《基于泛逻辑的泛容差关系的研究-刘城霞.pdf》由会员分享，可在线阅读，更多相关《基于泛逻辑的泛容差关系的研究-刘城霞.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2016年6月第34卷第3期西北工业大学学报Joumal of Nonhwestem Polytechnical UniversityJune 2016V0134 No3基于泛逻辑的泛容差关系的研究刘城霞12，何华灿13，张仰森2，朱敏玲21北京邮电大学计算机学院，北京 100876；2北京信息科技大学，北京3西北工业大学，陕西西安710072摘要：粗糙集是用确定的方法处理不确定信息和数据，但它要求属性信息是离散的，而且针对的是完备信息系统。而泛逻辑是研究人工智能领域中的不确定性、不完全性以及模糊性，它针对的信息可以是离散的，也可以是连续的。针对不完备信息系统扩展泛逻辑中的泛等价关系，得到泛容
2、差关系，并对连续或离散的属性取值应用泛容差关系进行分类，代替原来的扩展粗糙集中的容差关系，定义新的相似度的计算方法，进而进行数据填充，最后用实例进行了应用说明。关键词：粗糙集；泛逻辑；容差关系；泛容差关系中图分类号：11P3016 文献标志码：A 文章编号：10002758(2016)03047307粗糙集理论1在1982年由波兰数学家Pawlak提出的一种处理不精确、不确定和模糊数据的数学工具，它能有效地从数据本身提供的信息中发现有效、潜在的知识。近年来该理论成功地在机器学习、数据挖掘、智能数据分析等领域得到了广泛应用，受到了众多学者的重视，取得了很大的发展。泛逻辑理论心。是本世纪初由何华灿
3、教授提出的，它是针对人工智能等领域中传统逻辑无法解决的问题而开展的。它是在二值逻辑、多值逻辑和模糊逻辑的基础上，研究人工智能领域中的不确定性、不完全性以及模糊性的一种柔性逻辑。其中对命题的真值域、命题连接词、量词等都进行了柔性化，可以全面反映命题真值的不确定性、真值误差的不确定性、命题之间相关关系的不确定性等，使之更适合于现实世界的推理规则。泛逻辑和粗糙集都适用于处理不精确、不确定的信息，而这也给二者的结合带来了可行性与便利性。粗糙集理论基础及其扩充11完备信息系统下的粗糙集理论基础给定信息表s=(u，A，y，F)，其中u是非空论域，记u=z。，z：，戈。；A为非空有限属性集(口。，o：，口。
4、)，其中A=C ud，其中c为条件属性集，d是决策属性；圪f是属性口，A的值域，y=u屹i；F mE。是uA到y的关系集，其中厂为U(C ud)一y的映射函数，它为每个对象的每个属性赋予一个信息值，即V口fA，zU，八戈i，口f)屹 (1)若V n，C使得y中不含空值，即八z。，口i)咖，则称S是完备信息系统，即所处理的信息表是完备的，每个样本对象的所有属性值都是已知的。粗糙集理论正是基于完备信息系统这样一个假设。为便于数学推导，粗糙集中通常用等价关系代替分类。定义尺代表论域u上的一种关系，它可以是一种属性的描述，也可以是一个属性集合的描述。在一般叙述中，尺等价关系和尺属性都是同一概念。在属性
5、约简中，把任意非空属性子集看做是关系尺。任取非空属性子集尺A，如果z。，x，u，V口I尺以z。，n女)=以z，d。)均成立，则称戈i，戈，关于尺不可分辨，R为不可分辨关系，记为IND(尺)。IND(尺)即可把论域u中的元素分为若干个等价类，全体等价类的集合记为wIND(R)。收稿日期：20151027基金项目：“促进高校内涵发展专业建设面向大类人才培养模式的2016专业培养方案修订”项目资助作者简介：刘城霞(1978一)，女，北京邮电大学博士研究生，主要从事数据挖掘、粗糙集及泛逻辑的研究。万方数据西北工业大学学报 第34卷给定信息系统S=(u，A，y，F)，VxU和等价关系尺，则x关于尺的下近
6、似和上近似分别定义如下：下近似：R一(x)=u戈I石u戈R戈=u；。x算月(2)上近似：尺一(x)=uz zU戈R n x咖=u。nx十戈R (3)式中，戈。表示的是包含元素zU的尺等价类。根据上、下近似的定义给出边界域、正域和负域的概念如下：BND。(x)=尺一(x)一尺一(x)称为X的尺边界域。POS。(x)=尺一(x)称为X的尺正域。NEG。(x)=U一尺一(x)称为x的尺负域。由上述定义可知下近似尺一(x)和正域POS。(x)表示在知识尺下论域u中确定属于集合x的对象集，上近似尺一(X)表示在知识R下论域U中可能属于集合X的对象集，所以边界域BND。是在知识尺不能确定是否属于集合x的对
7、象集，负域NEG。(|f)则表示在知识尺下论域u中与集合x无关的对象集。12不完备信息系统中扩充粗糙集模型的容差关系及量化容差关系粗糙集理论是基于完备信息系统的，当信息系统不完备时，需要进行数据补齐或对粗糙集模型进行扩充。数据补齐主要采用某种方法(通常是概率统计)对所有未知属性值进行填补，将不完备信息系统转化为完备信息系统，然后用经典粗糙集理论来处理。比如现有的c45、删除法、最大频率法等”。数据补齐法应用起来十分简便，但它是对原始信息系统中未知属性值的一种人为估计，对原始信息系统的信息有不同程度的扰动，不能反映原始系统的真实情况，获得的知识可用性差。模型扩展主要是将经典粗糙集理论中的不可分辨
8、关系这一等价关系扩充为非等价关系，直接处理不完备信息系统。比如Kryszkiewicz提出容差关系H J，Stefanowski等人提出的非对称相似关系j，stefanowski等人提出的量化容差关系J，王国胤等人提出的限制容差关系o，Grzymala-Buss提出的特征关系1等，都是对粗糙集运算模型的扩充。文献9对不完备系统的粗糙集扩充方法进行了总结和研究。121容差关系当不完备信息系统S中所有未知属性值是遗漏型时，对属非空属性子集BA，MKryszkiewicz提出了如下容差关系：=(戈，)，)扩I V 6曰(6(戈)=6()，)V 6(戈)=术V 6(y)=木)(4)对任意对象戈U的容差
9、类(戈)=yu I(z，)，) (5)对象子集xu的下近似和上近似分别为B：(x)=戈U r。(x)X (6)B卜(X)=戈U 1(z)n X咖 (7)容差关系满足自反性和对称性，但不一定满足传递性。122量化容差关系对于不完备信息系统中的个体，由于已知信息的不同，也可以根据已知信息的相同程度来刻画它们之间的相近似程度。据此，stefanowski等人提出了基于量化容差关系的扩充Rough集模型。在不完备信息系统|s中，V 6A记K=6(z)I zU6(戈)木 (8)若U中对象对每个属性的取值独立且均匀分布，则任意对象V戈，y E U关于属性子集的相似度可定义为尺?(z，y)=r 1 6(戈)
10、=6()，)八6(z)术八6(y)木o 6(戈)6()，)八6(z)丰八6(y)爿c(9)【1l K 6(戈)=木V 6(y)=术容差关系所描述的样本对象之间相似度的取值范围是O，1，I型量化容差关系虽然将样本对象相似度的取值范围扩充到了0，1，但需要知道属性取值的概率分布等相关知识。量化容差关系还有不同的改进模型，在文献10中，定义了改进的量化容差关系。尺，(戈，y)=1 6(戈)=6(y)八6(z)爿c八6(y)术0 6(戈)6()，)八6(戈)牢6(y)丰忌： (6(算)=6，6(y)=水)至后： V(6()，)2屯八6(菇)=木)至善批)：丰6(y)：半51后：(10)万方数据第3期
11、刘城霞，等：基于泛逻辑的泛容差关系的研究式中，6。，(江1，2，m)为属性6目前已知的互不相同的属性值，后：(江l，2，m)为属性值为6i的已知对象数量。这种改进的量化容差关系中对象间相似度的度量使用的是已知属性值的统计数据，某属性值出现的次数越多，未知属性是该属性值的可能性就越大，两者的相似程度就越大，这更符合实际。关于量化容差关系的改进还有许多，比如文献11提出了基于目的限制容差关系等，这里不再赘述，有兴趣的可参看相关文献。2泛逻辑理论基础本文第二作者为了探索逻辑的一般规律，提出建立能包容各种逻辑形态和推理模式的泛逻辑学理论。泛逻辑学针对现代逻辑中存在的缺陷，基于三角范数理论，利用广义相关
12、性和广义自相关性将逻辑关系定义为一组连续可变的算子簇，并提出了和如何使用该算子簇中的算子，真正实现了模糊逻辑关系的柔性化。这里为简化计算，先不考虑广义自相关性，只考虑广义相关性，那么用到的零级泛逻辑理论。1)零级泛与及泛或经过多年的发展，现在普遍认同的是以T范数表示逻辑与，以T余范数S表示逻辑或。T范数和s范数是是泛逻辑学研究泛与或运算的数学基础。用表示的是广义相关性，对零级不确定性问题，用2个仅受控制的函数R(x，)=算“和G。(戈，)=1一(1一z)”作为零级T性生成元完整簇和零级S性生成元完整簇，把它们带入泛与何泛或运算的基模型分别生成的零级丁范数完整簇丁(z，)，)和零级S范数完整簇J
13、s(工，y，)如下：r(z，y，)=(max(0“，戈“+y“一1)“(11)5(戈，)，矗)=1一(max(0“，(1一戈)“+(1一y)“一1)1佃 (12)式中，nR，(0，1)，m=(34危)(4(1一)=(1+m)一(1+m)23m)2)(2m)由于广义相关系数是连续变化的，因此会有无限多个连续的丁(戈，y，危)算子和s(戈，y，矗)算子。2)零级泛蕴含与泛等价由零级丁性生成元完整簇R(z，)=z“代入蕴含运算的基模型生成零级I范数完整簇，(戈，y，)=(min(1+0“，1一x”+)，“)1“(13)记作由零级T性生成元完整簇F。(z，九)=戈”代人等价运算的基模型生成零级I范数完
14、整簇Q(z，y，危)=(1l戈“一)，“I)1“ (14)记作H。其中075为+，否则为一，m=(34)(4(1一)，=(1+，n)一(1+m)23m)12)(2m)。它有的4个特殊算子是：最小等价，又称zadeh等价Q(戈，)，1)=Q3=ite1 I戈=)，；min(戈，y)(15)中极等价，又称概率等价Q(菇，)，O75)=Q：=min(戈y，戈) (16)(I等价)中心等价，又称有界等价Q(戈，y，05)=Q。=1一l戈一y (17)最大等价又称突变等价Q(z，y，0)=Q0=ite戈I y=l；y I戈=l；1(18)3泛容差关系与相似度计算在完备系统不可分辨关系定义中要求菇。，zi
15、u，Vo。R以z。，o。)=八戈，n。)均成立，这个定义适合离散型属性，对于连续型的属性，一般的做法是先将其离散化，然后再使用不可分辨关系进行等价类的划分。然而，离散化的算法、精度都会影响分类的效率和准确性，进而影响属性约简的效率。如果能直接对连续属性进行不可分辨关系的分类，就可以避免人为离散化引起的取值误差，而且可以省略离散化过程，提高效率和精度。完备信息系统中可以用泛逻辑的泛等价关系Q6(戈，)，)=(1l 6(戈)“一6(y)“I)1“(19)来作为不可分辨关系，则当Q。(戈，y，)1一a时认为等价，其中a为阀值，否则不等价。其中m=(34危)(4(1一)五=(1+m)一(1+m)23m
16、)12)(2m)这里为广义相关系数，可以在使用时根据实际需要进行调整。在多数情况下系统中用到的是相容相关，即05，1，文中案例也是相容相关情况的万方数据西北工业大学学报 第34卷实例。戈“，zm代表戈i，戈f的属性n。的值。利用该泛等价关系处理离散属性时和原等价关系一致，连续属性可以直接处理而不需要进行离散化，有关该泛等价的性质及证明在另外的文章中有详细论述。31泛容差关系当信息系统不完备时，所有未知属性值是遗漏型时，对属非空属性子集曰A，定义泛容差关系B=(戈，)，)l V 6B(Q6(戈，y，)1一a V 6(石)=木V 6(y)=：Ic)I(20)对任意对象戈u的容差类(戈)=yu l(
17、戈，y)。 (21)对象子集XU的下近似和上近似分别为：曰!(x)=戈u I。(戈)x (22)日卜(x)=戈u IB(戈)n x咖 (23)泛容差关系满足自反性和对称性，但不一定满足传递性。对于泛容差关系，可以对其进行量化，参考122中量化容差关系的定义，定义泛容差关系的量化方法1 Q6(戈，y，)(1一a)八6(戈)木八6(y)木0 Q。(x，)，危)(1一a)的该属性的阀值。表示所有在属性6上有值的对象的个数，J7、r“表示对属性6分类后每类的对象个数，6为离散属性时即为属性6取值等于6i，扣1，m的对象个数，6为连续属性时即为属性6取值分类每类的对象个数。性质1 当属性全部为离散值时，
18、泛容差关系。相当于容差关系；性质2 当属性全部为离散值时，量化泛容差关系尺?相当于型量化容差关系R?。性质l证明 当属性全部为离散值时，泛容差关系710。相当于容差关系。即当属性全部为离散值时，泛容差关系。中Q6(戈，)，)1一d等价于6(菇)=6(y)。显然，当6(z)=6(y)时，Q6(戈，y，)=11一a成立。当Q6(戈，)，)10c即Q6(戈，)，危)=(1I 6(x)”一6(y)“I)1“1一d以=05为例，此时m=1Q6(算，y，)=1一l 6(戈)一6(y)I1一a6(z)一6(y)I1一d等价于6(x)=6(y)，则R?(z，y)和尺?(戈，)，)前两行定义等价。当(6(戈)=
19、6i6(，)=木)V(6(y)=6f八6(戈)=术)时，取6。I 6(戈)一6(y)I，则(6i6。)即为J|：，即为尼：，第三行两定义等价。当6(戈)=木八6()，)=木时，由第三行等价知第四行定义也是等价的。32 实例分析现以某医院有关流感诊断的原始数据信息表Js。=(u，A，y，F)为例，进行对比分析。论域u=戈l，戈2，算3，戈4，z5，z6，戈7，戈8，戈9，属性集合A=口1，n：，口，口。，d分别代表肌肉酸痛、咳嗽、头痛、体温和决策属性是否为流感，口，o：，o，取值集合为0，1，2，3，分别代表无症状，轻微，较严重，严重)，口。取值集合为连续型数据，取值范围35，40，d为决策属性
20、，取值集合为0，1，2分别代表不是，疑似，是。“木”表示遗漏值。万方数据第3期 刘城霞，等：基于泛逻辑的泛容差关系的研究表l连续型不完备信息系统表|so 3，分别代表偏低，正常，偏高，高。表2离散化后的不完备信息系统表瓯对体温属性进行离散化，35，3625)离散化为o，3625，375)离散化为1，375，3875)离散化为 ?量化容差关系得到的量化容差矩阵2，3875，40离散化为3，离散化后取值0，l，2，表3 R?量化容差矩阵r。表4根据R?量化容差矩阵r。进行补齐后的信息表s。由于r中对象间相似度都不同，所以取相似度大的进行补齐，得到了完备信息系统S。万方数据西北工业大学学报 第34卷
21、尺?量化容差关系得到的量化容差矩阵表5足量化容差矩阵瓦茗3 X4 算5 菇6 菇7 X80 0 O 0 12 O0 0 0 0 0 01 0 121 2147 0 00 1 0 0 0 l12121 0 l 0 O 02147 O 0 1 0 00 0 0 0 l 00 112 0 0 0 10 4147 0 O 0 244l0O其中对于连续型属性口。的相似度计算是按照半掣进矾呦口R芝(戈。，戈，)=戈。在口。上取值0625范围内的取值个数口。有值的个数型!：!主竺：型一16 6戈。，戈。2个对象的相似度R。(戈。，戈。)=尺?。(戈。，戈。)木尺芝(z。，x。)木尺芝(戈。，)木尺芝(z。，
22、戈。)=l木(詈)2+(吉)2+(吉)2)木：c吉=2表6根据R量化容差矩阵瓦进行补齐后的信息表s。40003O参考文献：由实验结果可见，补齐后的信息表也是一个完备信息系统。由当前实例的补齐结果来看，用R?量化容差关系补齐同R?量化容差关系的补齐结果相同。这说明应用量化泛容差关系后算法基本性能保持不变，但可以省略掉离散化过程，扩展了粗糙集的应用范围，使得扩展后粗糙集理论可以直接应用于连续型属性。4 结 论应用粗糙集理论指导数据挖掘已经应用非常广泛，但粗糙集有自身的局限性。比如必须要使用离散型数据，必须是完备系统等。本文从对理论扩展的角度，针对不完备系统应用泛容差对容差关系进行了重新定义，使之可
23、以针对连续型数据进行划分，是对不完备系统下粗糙集运算模型的扩展。1 Pawlak zRough setsJIntemational Joumal of computer aIld Info珊ation science，1982，ll(5)：3413562 何华灿泛逻辑学原理M北京：科学出版社，2001He HuacanThe Theory of universal Lo舀cMBeijing，science Press，2001(in chinese)一71奶一ooo小ooo似。一420O00O尼0O肌见勘舢职加如胁一13233122码一232l2221l万方数据第3期 刘城霞，等：基于泛逻辑的
24、泛容差关系的研究 4793 GrzylanlaBusse J w，Hu MA comparison of severaJ Approaches to Missing Attribute Vdues in Data MiningcPmceedingsof the second Intemational comrence on Rou曲Sets a11d current Trends in conlputing RscTC 2000，Banf，c柚ada，s曲ngerBerlin，2000：3403474Kryszkiewicz MRough set Approach to Incomplete
25、Infonnation SystemsJInf011nation Sciences，1998，112：39495 stefanowski J，TsoukiaLs AIncomplete Infomation Tables and Rough classincaIionJcomputation出Intelligence，200l，17(3)：5455666 stef矗owski J，Tsoukias AValued Tolerance aIld Decision RulescVolume 2005 of Lecture Notes in Ani6cial IntelligenceBerlin，S
26、pringer，200l：2122197 王国胤Rough集理论在不完备信息系统中的扩充J计算机研究与发展，2002，39(10)：12381243wang GuoyinExtension of Rough set under Incomplete Inf0珊ation systemJJoumal of computer Research and Development，2002，39(10)：12381243(in Chinese)8 GrzymaIaBusse J wRough Set strate百es to Data wilh Missing Attribute ValuesCThe
27、3rd Incemational Conference on DataMiningMelboume，FL，USA，2003：56-639 官礼和基于粗糙集理论的不完备信息处理方法研究J重庆邮电大学学报，2009，2l(4)：461466Guan LihePmcessing Incomplete Infonnation Methods Based on Rough setJJoumal of chongqing university of Posts andTelecommunications，2009，2l(4)：461466(in Chinese)10邓耀进，李仁发一种粗糙集理论中量化容差关
28、系的改进J计算机工程与科学，2009，3I(10)：105一108Deng Yaojin，Li RenfaAn Impr0Vement on the Valued Tolerance Relation in the Rough Set TheoryJComputer Engineering&Science，2009，31(10)：105-108(in Chinese)1 1Gao Yuqin，Fang Guohua，Liu YaqinpImpmved Limited 7rolerance Relation Model of Incomplete Inf0丌nation system fbr E
29、valuation of water Conservancy Project Management ModemizafionJwater Science and Engineering，20 l 3，6(4)：469477The Study of UniVersal Tolerance Relation Based on UniVersal LogicLiu Chengxial_，He Huacanl，Zhang Yangsen2，Zhu Minlin92厂，1computer school，Beijing university of Posts and Telecommunications，
30、Beijing 100876，china、2Beijing Info丌nation and Technology university，Beijing 10010l，china3Nonhwestem Polytechnical Universitv，Xian 710072，China JAbstract：Rough set theory can be used to deal with the imprecise data and infbmlation by certain method but itsbasis is that the attributes value must be di
31、screte and the svstem must be completeUniversal logic can do with theuncertain，incomplete and fhzzv infbnllation in arti6cial intelligence and the data can be discrete or continuousUsethe universal lo如c to rede6ne the tolerance relation and use universal tolemnce relation to classi“the continuous or
32、discrete attribute，we can extend the scope of application of Iough set theory and uniVersal logicThis paper makesfocus on the new concept of universal tolerance relation and new computation method of similarity between objectsand then we can complete the data based on thisAt last an example is giVen to illustrate itKeyword-s：rough set；universal logic；t01erance relation；uniVersal tolerance relation万方数据