粗糙集理论方法及其应用

粗糙集理论方法及其应用南京航空航天大学：菅利荣粗糙集理论方法及其应用粗糙集理论方法及其应用内容简要粗糙集产生与发展的时代背景粗糙集的基础理论与方法粗糙集与其它软计算技术的杂合粗糙集理论方法的应用粗糙集理论方法及其应用粗糙集理论方法及其应用Internet和数据库技术的迅猛发展和广泛应用，数据库中存储的数据量以惊人的速度在增加，庞大的数据量渗透到社会生活和生产的各个领域，例：金融投资：股票指数和价格、利率、银行卡数据及诈骗监测等；卫生保健：存储在医院管理系统中的诊断数据；生产和制造：过程优化和故障检测；远程通讯网络：呼叫模式和故障管理系统；科学领域：天文观测、语音数据及生物数据等。1粗糙集产生与发展的时代背景粗糙集理论方法及其应用粗糙集理论方法及其应用其结果导致传统的统计技术及数据管理工具不再适用于分析这些巨量的数据集。海量的数据被描述为“丰富的数据，贫乏的知识”。人们需要采用自动化程度更高、效率更高的数据处理方法来处理大量数据，并提供有用的知识。1粗糙集产生与发展的时代背景粗糙集理论方法及其应用粗糙集理论方法及其应用从金融业到制造业，越来越多的公司正依赖于巨量数据的分析获得竞争优势，知识已成为社会生活和生产的第一推动力。为了帮助人们智能化地分析海量数据，自动地分析一些事例，出现了新一代的技术和工具，这些技术和工具主要用于数据挖掘（Datamining，DM）和知识发现(Knowledgediscoveryindatabase，KDD)领域。KDD指从大型数据库中自动提取知识，目标是发现数据中隐藏的、以前未知的、潜在有用的知识，本质上是在大的数据集合中寻找数据间的规则及普遍模式。数据挖掘的经典案例：啤酒与婴儿尿片问题1粗糙集产生与发展的时代背景粗糙集理论方法及其应用粗糙集理论方法及其应用数据库数据准备数据清理与选择数据挖掘规则聚类分类可视化有用的知识图1.1KDD的流程1粗糙集产生与发展的时代背景粗糙集理论方法及其应用粗糙集理论方法及其应用Pawlak于1982年提出的粗糙集理论（Roughsettheory，RST)是一种描述不完整性和不确定性的数学理论粗糙集理论，能有效地分析不精确、不一致、不完整等各种不完备的信息，是关于数据推理的一种强大工具。粗糙集学习算法能够被用于从决策表中获取以IF-THEN形式表示的规则集。粗糙集方法提供了一种从数据库中获取知识的一种有效的方法。2粗糙集理论思想粗糙集理论方法及其应用粗糙集理论方法及其应用粗糙集概念示意图粗糙集方法是将数据转化为知识的一种规范的方法。•将知识视为分类的能力，每一个对象与一些信息相联系，且对象仅能用获得的信息表示。•发现分类问题给定属性间的冗余及依赖，具有相同或相似信息的对象不能被识别。2粗糙集理论思想粗糙集理论方法及其应用粗糙集理论方法及其应用粗糙集理论思想2粗糙集理论思想粗糙集理论方法及其应用粗糙集理论方法及其应用粗糙集的主要思想粗糙集的主要思想：是基于不可分辨关系，每一个对象与一些信息相联系，且对象仅能用获得的信息表示。具有相同或相似信息的对象不能被识别。论域的不可分辨对象形成了不可分辨对象的聚类，即知识粒度。用于近似的知识将U划分为由条件属性集判断是不可分辨的对象元素集，元素集被视为用于近似的“知识粒度”；被近似的知识将U划分为由决策属性集生成的决策类，在此基础上，用一种知识近似另一种知识。2粗糙集理论思想粗糙集理论方法及其应用粗糙集理论方法及其应用表1所示的关于全球变暖的一个信息系统,a1—太阳能(Solarenergy)，a2—火山活动(Volcanicactivity),a3—二氧化碳含量（ResidualCO2,），d—温度（Temperature）例粗糙集理论方法及其应用粗糙集理论方法及其应用2.1信息系统设S=(U,A,V,f)为一个信息系统，也称为知识表示系统。其中，U={U1,U2,U3,…,U|u|}为有限非空集合，称为论域对象空间；A={a1,a2,a3,…,a|A|}为属性的非空有限集合。若A中的属性又可分为两个不相交的子集，即条件属性集C和决策属性集D，A=C∪D,C∩D=φ,则S也称为决策表。V=∪Va其中a∈A，Va为属性a的值域；f：U×A→V为信息函数，对于a∈A，x∈U，f(x,a)∈Va，它指定了U中每一对象的属性值。2粗糙集理论方法粗糙集理论方法及其应用粗糙集理论方法及其应用令a∈A，x∈U，f(x,a)∈Va；对于任一子集φ≠P∈A，在U上的不可分辨关系I定义为：I={(x,y)∈U×U：f(x,q)=f(y,q)q∈P}若(x,y)∈I，则称x和y是不可分辨的。2.2不可分辨关系（Indiscribilityrelation)粗糙集理论方法及其应用粗糙集理论方法及其应用不可分辨关系是一个等价关系(自反的、对称的、传递的）。包含对象x的等价类记为I(x)。等价类与知识粒度的表达相对应，它是粗糙集主要概念，如近似、依赖及约简等，定义的基础2.2不可分辨关系（Indiscribilityrelation)粗糙集理论方法及其应用粗糙集理论方法及其应用)()()(})(:{)(})(:{)(})(:{)(XaprXaprXbndXxIUxXnegXxIUxXaprXxIUxXapr定义给定一个知识表示系统),,,(fVAUS，AP，UX，Ux，集合X关于I的下近似、上近似、负区及边界区分别为})(:{)(XxIUxXaprp})(:{)(XxIUxXaprP})(:{)(XxIUxXnegp)()()(XaprXaprXbndppP2.3粗糙近似粗糙集理论方法及其应用粗糙集理论方法及其应用集合X的下近似实际上是由那些根据已有知识判断肯定属于X的对象所组成的最大的集合，也称为X的正区,记作pos(X)；集合X的负区neg(X)为根据已有知识判断肯定不属于X的对象组成的集合;集合X的上近似由所有与X相交非空的等价类的并集组成，即那些可能属于X的对象组成的最小集合。集合X的边界区bnd(X)为集合X的上近似与下近似之差，如果bnd(X)是空集，则称X关于I是清晰的；反之如果bnd(X)不是空集，则称集合X关于I是粗糙的。2.3粗糙近似粗糙集理论方法及其应用粗糙集理论方法及其应用定义AP，X的近似精度定义为|)(|/|)(|)(XaprXaprXP近似精度反映了根据现有知识对X的了解程度。显然，0≤)(XP≤1，若)(XP=1，则称集合X相对于I是清晰的；若)(XP1，则称集合X相对于I是粗糙的。2.4近似精度与近似质量粗糙集理论方法及其应用粗糙集理论方法及其应用定义令X={X1,X2,…,Xn}为U的一个划分，其中Xi，i=1,2,…,n，为X的一个类别，PC，则X的近似质量定义为|||)(|)(1UXaprXiniP其中，|.|表示基，近似质量)(XP表示由属性集P正确分类的对象数与系统中所有对象数的比率。2.4近似精度与近似质量粗糙集理论方法及其应用粗糙集理论方法及其应用(1)约简约简的属性集的分类质量与原属性集的分类质量相同。若最小的属性子集ACP，满足)(XP=)(XC，则集合P称为C的一个约简，记为RED(P)。简单地说，约简是不含多余属性并保证正确分类的最小条件属性子集。属性间依赖的发现导致生成与原始属性集具有相同分类质量的最小属性子集约简的生成。（2）核信息系统可能有不只一个约简，所有约简的交称为信息系统的核，表示为：CORE(P)=)(PREDRiiR,i=1,2,…核是信息系统最重要的属性集，它也可能是空集。2.5属性约简与核粗糙集理论方法及其应用粗糙集理论方法及其应用论域中所有条件元素的集合，称为S中的条件类，由Xi(i=1,2,…,k)表示；论域中所有决策元素的集合，称为S中的决策类，用Yj(j=1,2,…,n)表示，jiYX,则r:)()(jDiCYDesXDes称为（C,D）的决策规则,表示为｛rij｝，对于i,j，若XiYj，则规则rij在S中是决策的，否则为非决策的。规则的语法表示如下：iff(x,q1)=rq1∧f(x,q2)=rq2…∧f(x,qp)=rqpthenx∈Yj1∨Yj2∨…∨Yjk其中，{q1,q2,…,qp}C；(rq1,rq2,…,rqp)∈Vq1×Vq2×…×Vqp若结果一致，则k=1，那么规则是确切的，否则规则为近似的。2.6决策规则粗糙集理论方法及其应用粗糙集理论方法及其应用对论域进行划分，可得如下等价类U/C={X1,X2,X3,X4,X5,X6}其中：X1={n1}，X2={n2}，X3={n3}，X4={n4,n5,n6,n9}，X5={n7}，X6={n8}YH={n2,n3,n4,n5,n6,n8}，YL={n1,n7,n9}2.7算例条件属性(C)决策属性(D)Ua1a2a3dn1HighLowLowLown2MediumHighLowHighn3HighHighHighHighn4MediumLowHighHighn5MediumLowHighHighn6MediumLowHighHighn7LowLowLowLown8HighHighMediumHighn9MediumLowHighLow粗糙集理论方法及其应用粗糙集理论方法及其应用(1)求整个条件属性集的分类质量：分类质量=5/9=0.56(2)求约简由属性a1对论域进行划分，可得如下等价类U/a1={X1,X2,X3,X4,X5,X6}其中：X1={n1,n3,n8}，X2={n2,n4,n5,n6,n9}，X3={n7}YL={n2,n3,n4,n5,n6,n8}，YH={n1,n7,n9}显然，属性a1的分类质量小于总的分类质量，属性a1不是约简2.7算例条件属性(C)决策属性(D)Ua1a2a3dn1HighLowLowLown2MediumHighLowHighn3HighHighHighHighn4MediumLowHighHighn5MediumLowHighHighn6MediumLowHighHighn7LowLowLowLown8HighHighMediumHighn9MediumLowHighLow粗糙集理论方法及其应用粗糙集理论方法及其应用由属性a1,a2对论域进行划分，可得如下等价类U/C={X1,X2,X3,X4,X5,X6}其中：X1={n1},X2={n2},X3={n3,n8}，X4={n4,n5,n6,n9},X5={n7}YL={n2,n3,n4,n5,n6,n8}，YH={n1,n7,n9}分类质量=5/9=0.56，与整个属性集的分类质量相同因此，属性子集{a1,a2}是约简。条件属性(C)决策属性(D)Ua1a2a3dn1HighLowLowLown2MediumHighLowHighn3HighHighHighHighn4MediumLowHighHighn5MediumLowHighHighn6MediumLowHighHighn7LowLowLowLown8HighHighMediumHighn9MediumLowHighLow2.7算例粗糙集理论方法及其应用粗糙集理论方法及其应用2.7算例条件属性(C)决策属性(D)Ua1a2a3dn1HighLowLowLown2MediumHighLowHighn3HighHighHighHighn4MediumLowHighHighn5MediumLowHighHighn6MediumLowHighHighn7LowLowLowLown8HighHighMediumHighn9MediumLowHighLow规则支持数a1=Highanda2=Low%100d=Low1a1=Mediumanda2=High%100d=High1a1=Highanda2=High%100d=Hi