第6章粗糙集决策方法

《第6章粗糙集决策方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

第6章粗糙集决策方法粗糙集的基础理论粗糙集的扩展理论变精度粗糙集理论基于优势关系的粗糙集理论开始返回目录

16.1粗糙集概述1.软技术产生的时代背景和意义随着Internet和数据库技术的迅猛发展和广泛应用，数据库中存储的数据量以惊人的速度在增加，庞大的数据量渗透到社会生活和生产的各个领域，其结果导致传统的统计技术及数据管理工具不再适用于分析这些巨量的数据集。海量的数据被描述为“丰富的数据，贫乏的知识”。人们需要采用自动化程度更高、效率更高的数据处理方法来处理大量数据，并提供有用的知识。从金融业到制造业，越来越多的公司正依赖于巨量数据的分析获得竞争优势，知识已成为社会生活和生产的第一推动力。为了帮助人们智能化地分析海量数据，自动地分析一些事例，出现了新一代的技术和工具，这些技术和工具主要用于数据挖掘（datamining，DM）和知识发现(Knowledgediscoveryindatabase，KDD)领域。如粗糙集理论、模糊集理论、灰色系统、遗传算法和神经网络等

26.1粗糙集概述2.粗糙集的发展粗糙集是处理不精确、不确定与不完全数据的新的理论，最初是由波兰科学家Z.Pawlak于1982年提出的。由于最初关于粗糙集理论的研究大部分是用波兰语发表的,因此当时没有引起国际计算机学界和数学界的重视,研究地域也仅局限在东欧一些国家,直到20世纪80年代末才逐渐引起各国学者的注意。1992年,第一届关于粗糙集理论国际学术会议在波兰召开。1995年,ACMCommunication将其列为新浮现的计算机科学的研究课题。1998年,国际信息科学杂志(InfomationSciences)还为粗糙集理论的研究出了一期专辑。我国目前期刊网上发表的有关粗糙集的文章已有2千篇。

33.粗糙集的特点RS方法已被成功地应用于机器学习、知识获取、决策分析、知识发现、模式识别、专家系统和决策支持系统等领域。有趣的结果已激励各个领域的专家研究RST及它的应用。它的成功是由于具有如下特征：发现最小知识表示；不修正不一致性，将生成的不一致规则划分为确定性规则和可能性规则；约简冗余的属性，且约简算法较为简单。6.1粗糙集概述

43.粗糙集的特点作为一种软计算方法，粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息，如统计学中的概率分布、模糊集理论中的隶属度等，所以对问题的不确定性的描述或处理可以说是比较客观的。

54.粗糙集与KDD关系RST和KDD关系密切，它为KDD提供了一种新的方法和工具，理由如下：(1)KDD研究的实施对象多为关系数据库，关系表可被看作为RST中的决策表，这给RS方法的应用带来极大的方便；(2)现实世界中规则有确定性的，也有不确定性的。从数据库中发现不确定性的知识，为RS方法提供了用武之地；(3)从数据中发现异常，排除知识发现过程中的噪声干扰也是RS方法的特长；

64.粗糙集与KDD关系(4)运用RS方法得到的知识发现算法有利于并行执行，可以极大地提高发现效率。对于大规模数据库中的知识发现来说，这是非常重要的；(5)利用RS方法进行预处理，去掉多余属性，可提高发现效率，降低错误率；(6)与模糊集方法或神经网络方法相比，由RS方法得到的决策规则及推理过程更易于被证实和解释。

75.粗糙集的不足由于对数据的过拟合而使其对新对象的预测能力大为降低；不能处理偏好多属性决策分类问题；对于粗糙集边界区域的刻画比较简单，如基于等价关系的粗糙集的分类是确定的，而没有一定程度的属于或包含；不能识别仅由少数事例支持的随机规则；对原始数据本身的模糊性缺乏相应的处理方法等。

86.粗糙集的发展趋势据概率统计，没有一种方法对于所有的问题都是最好的。每一种方法都有其适用范围，在实践应用中，常将几个技术合并起来构造一个“杂合”的方法。RST与人工神经网络、概率理论、模糊集合理论、遗传算法等理论有较强的互补性。已有一些学者探讨了将人工神经网络、概率理论、模糊集合理论、粗糙集理论、遗传算法等两个或多个技术杂合在一起的方法。

96.2粗糙集6.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中每一对象的属性值。

106.2.2不可分辨关系（Indiscribilityrelation令a∈A，x∈U，f(x,a)∈Va；对于任一子集φ≠PA，在U上的不可分辨关系I定义为：I={(x,y)∈U×U：f(x,q)=f(y,q)q∈P}若(x,y)∈I，则称x和y是不可分辨的。

116.2.2不可分辨关系Indiscernibilityrelation显然，这样定义的不可分辨关系是一个等价关系(自反的、对称的、传递的）。包含对象x的等价类记为I(x)。等价类与知识粒度的表达相对应，它是粗糙集主要概念，如近似、依赖及约简等，定义的基础

12粗糙集的主要思想粗糙集的主要思想是基于不可分辨关系，每一个对象与一些信息相联系，且对象仅能用获得的信息表示。因此，具有相同或相似信息的对象不能被识别。论域的不可分辨对象形成了不可分辨对象的聚类，即知识粒度。用于近似的知识将U划分为由条件属性集判断是不可分辨的对象元素集，元素集被视为用于近似的“知识粒度”；被近似的知识将U划分为由决策属性集生成的决策类，在此基础上，用一种知识近似另一种知识。

136.2.3粗糙近似

146.2.3粗糙近似定义给定一个信息系统（知识表示系统）S=(U,A,V,f)，A=C∪D

156.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是粗糙的。

166.2.4粗糙隶属函数

176.2.4近似精度与近似质量

186.2.5算例表1所示的关于全球变暖的一个信息系统,a1—太阳能(Solarenergy)，a2—火山活动(Volcanicactivity),a3—二氧化碳含量（ResidualCO2,），d—温度（Temperature）

196.2.5算例对论域进行划分，可得如下等价类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}

206.2.5算例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}据此可求得粗糙近似如下:YH的下近似：apr(Yn)={{n2},{n3},{n8}}YH的上近似：{{n2},{n3},{n8},{n4,n5,n6,n9}}YL的下近似：apr(YL)={{n1},{n7}}YL的上近似：{{n1},{n7},{n4,n5,n6,n9}}YL的分类精度=3/7=0.43YH的分类精度=2/6=0.33分类质量=5/9=0.56`

216.2.6属性约简与核

226.2.7决策规则

236.2.7约简算法

246.2.7约简算法约简对于在模型中分类对象最终构建一系列规则是重要的，有关的文献探讨了约简的两个主要方面，一方面是为给定的系统寻找约简的问题，这个问题是一个NP完全问题，常见的约简算法有：快速约简、遗传算法、动态约简、相容性约简等。

256.2.8算例下面通过一个简单的例子说明，如表1所示，S=(U,A,V,f)，其中U={n1,n2,n3,n4,n5,n6,n7},条件属性集C={a1,a2,a3,a4,a5,a6}，决策属性集D={d}。

266.2.8算例对论域进行划分，可得如下等价类U/C={X1,X2,X3,X4,X5}其中：X1={n1,n4,n6}，X2={n2}，X3={n3}，X4={n5}，X5={n7}U/D={YN,YP}其中：YN={n1,n2,n3}，YP={n4,n5,n6,n7}

276.2.8算例X1={n1,n4,n6}，X2={n2}，X3={n3}，X4={n5}，X5={n7}YN={n1,n2,n3}，YP={n4,n5,n6,n7}YN的下近似：apr(YN)={n2,n3}YN的上近似：={n2,n3,n4,n1,n6}YP的下近似：apr(Yp)={n5,n7}YP的上近似：apr(Yp)={n5,n7,n4,n1,n6}YN的分类精度=2/5=0.4YP的分类精度=2/5=0.4分类质量=4/7=0.57

286.2.8求约简算例U/D={YN,YP}以a1对论域进行划分，我们求分类质量：YN={n1,n2,n3}，YP={n4,n5,n6,n7}X1={n1,n2,n4,n6}，X2={n3,n5,n7}，因此分类质量为：分类质量=0/7=0显然属性a1不是约简。

296.2.8求约简算例U/D={YN,YP}以属性集{a1,a2}对论域进行划分，我们求分类质量：YN={n1,n2,n3}，YP={n4,n5,n6,n7}X1={n1,n2,n4,n6}，X2={n3,n5,n7}，因此分类质量为：分类质量=0/7=0显然属性集{a1,a2}不是约简。

306.2.8求约简算例U/D={YN,YP}以属性集{a1,a3}对论域进行划分，我们求分类质量：YN={n1,n2,n3}，YP={n4,n5,n6,n7}X1={n1,n4,n6}，X2={n2}，X3={n3}，X4={n5,n7}因此分类质量为：分类质量=4/7=0.57由于{a1,a3}与全部条件属性集具有相同的分类质量，且为最小的条件属性子集，因此为约简。

316.2.8求约简算例可求得约简为：{a1,a3}，{a4,a5}，{a5,a6}由约简{a1,a3}构造的决策规则为:Ifa1＝1∧a3=2thend=N支持对象数1Ifa1＝2∧a3=1thend=N支持对象数1a1＝2∧a3=2thend=P支持对象数为2分类质量=4/7=0.57

326.2.8算例表1所示的关于全球变暖的一个信息系统,a1—太阳能(Solarenergy)，a2—火山活动(Volcanicactivity),a3—二氧化碳含量（ResidualCO2,），d—温度（Temperature）

336.2.8求约简算例(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不是约简

346.2.8求约简算例由属性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}是约简。

356.2.8求约简算例由属性a1,a3对论域进行划分，可得如下等价类U/C={X1,X2,X3,X4,X5,X6}其中：X1={n1}，X2={n2}，X3={n3}，X4={n4,n5,n6,n9}，X5={n7}，X6={n8}YL={n2,n3,n4,n5,n6,n8}，YH={n1,n7,n9}分类质量=5/9=0.56，与整个属性集的分类质量相同因此，属性子集{a1,a3}也是约简，同理可求得属性子集{a2,a3}也为约简。

366.2.8求约简算例

37四类粗糙集

38数据离散粗糙集理论分析要求，数据必须以类别的形式出现。因此，连续数据必须首先进行离散化处理，离散的结果可能会减小原始数据的精度，但将会提高它的一般性。数据离散问题是一个NP完全问题，数据离散可分为专家离散与自动离散，专家离散指由某一领域的专家根据他的判断或使用该领域确定的标准进行的离散；自动离散指按自动定义的方式进行的离散。自动离散方法又可分为有监督离散法和无监督自动离散法，无监督离散法可视为一个简单的聚类过程，如等频率区间法、等大小宽度区间法。有监督的的离散化方法又可分为两类，全局离散方法与局部离散方法。注:将信息系统中的连续型数据离散为粗糙集模型可用的数据时，会产生潜在的信息损失，这个问题值得探讨。

396.3变精度粗糙集理论

406.3变精度粗糙集理论在RST中，集合的粗糙近似和模糊之间，及不确定性与粗糙隶属间有密切的联系。为了导出用于决策概率估计的非强决策规则，应考虑交迭度，Ziarko扩展了粗糙隶属函数的思想，提出了粗糙集的一种概率方法—变精度粗糙集。

416.3.1变精度粗糙集中的β当对象按变精度粗糙集分类时，需定义一个正确分类的阈值β。Ziarko称β为分类误差，定义区域为0≤β<0.5，An等人将β定义为正确分类的比例，在这种情况下，近似范围为0.5<β≤1.0，并将此技术称为强化粗糙集。本文将β定义为0.5<β≤1

426.3.1变精度粗糙集中的β变精度粗糙集是对标准粗糙集理论的一种扩展，它通过设置阈值参数β，放松了标准粗糙集理论对近似边界的严格定义，变精度粗糙集是允许概率分类。与标准粗糙集相比，当对象在变精度粗糙集中分类时，在它的正确分类中有一个置信度，这一方面完善了近似空间的概念，另一方面也有利于根据粗糙集理论从认为不相关的数据中发现相关信息。

436.3.2β-近似根据变精度理论的基本思想，给出如下定义

446.3.3β值与分类精度关系

456.3.4变精度粗糙集的分类质量

466.3.5变精度粗糙集中的近似约简

476.3.6概率规则获取

486.3.7算例1对论域进行划分，可得如下等价类：U/C={X1,X2,X3,X4,X5}其中：X1={n1,n4,n6}，X2={n2}，X3={n3}，X4={n5}，X5={n7}U/D={YN,YP}其中：YN={n1,n2,n3}，YP={n4,n5,n6,n7}求得一个β-约简为{a1,a3},β=0.6，则

49β-粗糙近似令：β=0.6，则β-粗糙近似分别为:显然，分类质量为1

50β-粗糙近似令：β=70%，则β-粗糙近似为：显然，分类质量为4/7=0.57

51求β-约简算例1U/D={YN,YP}YN={n1,n2,n3}，YP={n4,n5,n6,n7}令：β=0.6，求β-粗糙约简如（1）求属性a1的分类质量以a1对论域进行划分X1={n1,n2,n4,n6}，X2={n3,n5,n7}，因此分类质量为：分类质量=3/7=0.43<1显然属性a1不是约简。

52求约简算例1U/D={YN,YP}YN={n1,n2,n3}，YP={n4,n5,n6,n7}(2)以属性集{a1,a2}对论域进行划分，我们求分类质量：X1={n1,n2,n4,n6}，X2={n3,n5,n7}，因此分类质量为：分类质量=3/7=0.43<1显然属性集{a1,a2}不是约简。

53求β-约简算例1U/D={YN,YP}YN={n1,n2,n3}，YP={n4,n5,n6,n7}以属性集{a1,a3}对论域进行划分，我们求分类质量：X1={n1,n4,n6}，X2={n2}，X3={n3}，X4={n5,n7}因此分类质量为：分类质量=7/7=1由于{a1,a3}与全部条件属性集具有相同的分类质量，且为最小的条件属性子集，因此为约简。同理，可以求得{a4,a5}，{a5,a6}也为约简.

54由β-约简{a1,a3}构造的概率决策规则

55求β-约简算例2对论域进行划分，可得如下等价类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}

56β-粗糙近似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}令：β=70%，则β-粗糙近似为：

57求β-约简算例(1)求整个条件属性集的分类质量：分类质量=1(2)求约简由属性a1对论域进行划分，可得如下等价类U/a1={X1,X2,X3,X4,X5,X6}其中：X1={n1,n3,n8}，X2={n2,n4,n5,n6,n9}，X3={n7}YH={n2,n3,n4,n5,n6,n8}，YL={n1,n7,n9}显然，显然，属性a1的分类质量小于总的分类质量，属性a1不是约简

58求约简算例由属性a1,a2对论域进行划分，可得如下等价类U/C={X1,X2,X3,X4,X5,X6}其中：X1={n1}，X2={n2}，X3={n3,n8}，X4={n4,n5,n6,n9}，X5={n7}YH={n2,n3,n4,n5,n6,n8}，YL={n1,n7,n9}分类质量=9/9=0.56，与整个属性集的分类质量相同因此，属性子集{a1,a2}是约简。

59求约简算例由属性a1,a3对论域进行划分，可得如下等价类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}分类质量=9/9=1，与整个属性集的分类质量相同因此，属性子集{a1,a3}也是约简，同理可求得属性子集{a2,a3}也为约简。

60概率规则获取

616.4基于优势关系的粗糙集理论经典粗糙集理论不能发现多标准决策表中与指定标准相关的不相容性，文中的标准指具有偏好信息的属性及偏好决策类，如在经济及金融决策问题中常遇到的属性：投资回报率、利润率、市场占有率及负债率等，这些属性是具有偏好信息的，这个问题的解决对于将粗糙集方法应用于多标准决策分析是至关重要的。Greco等人已提出了一个扩展的粗糙集理论，该理论能够处理多标准决策分析（MultiCriteriaDecisionAnalysis,MCDA）中典型事例决策的不一致性。这种改进主要基于在决策类的粗糙近似中，用优势关系代替不可分辨关系，这样处理后的一个重要结果是，能够根据逻辑语句“if…,then”表示的决策规则，由事例决策导出偏好模型。

626.4基于优势关系的粗糙集理论a1：营利利润率，即公司的营业利润与营业收入的比率。a2：资本报酬率，即公司利润总额与公司所有者投入企业的资本的比率。a3：资产负债率，也称负债比率，是公司负债总额（包括流动负债与长期负债）与资产总额的比率。

636.4.1优势关系(dominancerelation)优势关系:令x,y∈U，若对于q∈P，f(y,q)≥f(x,q)，则yDPx，这种关系称为优势关系。这样定义的优势关系实际为弱优势关系，表达了对象集在标准q上的一个偏好，若对于q∈P，f(y,q)>f(x,q)成立，该关系转换为强优势关系；若对于q∈P，f(y,q)=f(x,q)成立，该关系便转换为不可分辨关系。优势关系是自反的及传递的。对于x∈U，则xDPx。，由此可以得出优势关系是自反的，对于x,y,z∈U，若f(y,q)≥f(x,q)且f(x,q)≥f(z,q)，则f(y,q)≥f(z,q)，所以优势关系是传递的。

646.4.1优势关系(dominancerelation)标准(偏好信息)的出现要求在数据分析中考虑优势关系。若对象A和对象B满足以下两个条件，则对象A优于对象B。(1)在所有考虑的标准中，A至少和B一样好；(2)在所有考虑的标准中，A和B有一致或相似的描述。据此推理，将对象分配至具有偏好信息的类别，应该考虑如下优势原则：若对象A优于对象B，那么A应该分配至一个不比B差的类中。当对象A和B不满足优势原则时，则认为这两个对象(A,B)是不相容的，决策类别也可以表达偏好，如决策者将破产风险分为高风险、中风险及低风险等级别，这种类型的分类也称为排序。

656.4.1优势关系(dominancerelation)换句话说，决策者已经按照以下的综合评价将决策表中的对象分配至Cl的类别中：最坏的对象在Cl1类，最好的对象在Cln类，其它的对象属于剩下的类别Clt中。按照这个原则，t∈{1,2,…,n}越高，则类别Clt越好。

666.4.2优势集与劣势集

676.4.2优势集与劣势集

686.4.3基于优势关系的不相容性与不可分辨类

696.4.4优势粗糙近似

706.4.4优势粗糙近似

716.4.5分类质量

726.4.6偏好决策规则

736.4.7例1a1：营利利润率，营业利润率越高，说明企业营业收入的获利水平越高。a2：资本报酬率，资本报酬率反映了资本金的获利能力。从投资者角度来看，资本金报酬率总是越高越好。a3：资产负债率

746.4.7例1

756.4.7例1

76粗糙近似

776.4.7例1

786.4.7例2表1为某公司工厂经理收到的十个有关运输方案的建议。每个运输方案包括4个条件属性，条件属性集C={c1,c2,c3,c4}，一个决策属性，决策属性集D={d},其中，c1：运输成本；c2：批量规模；c3：库存量成本；c4：反应时间；d：运输方案评价。

796.4.7例2

806.4.7例2U/D={Cl1,Cl2}其中：Cl1={n2,n3,n6,n7,n10}，Cl2={n1,n4,n5,n8,n9}分类质量为：5/9

816.4.7例2分类质量为：5/9

82举例2

836.4.7例2