决策粗糙集

决策粗糙集（共12篇）

决策粗糙集 篇1

决策树方法[1]是一种通过构造决策树来发现数据集中分类知识的数据挖掘方法,决策树分类方法具有速度快、精度高、生成模式简单、能处理大数据集等优点,数据挖掘的分类方法受到许多研究者的关注,其中比较著名的是J.Ross Quinlan的ID3算法和C4.5算法[2],还有一些SLIQ、SPRINT也有相当广泛的应用。

粗糙集理论Rough Sets[3]是由波兰学者Z.Pawlak教授提出的,它从新的角度认识知识,把知识和分类[4]紧密联系起来,为处理不精确、不完全数据的分类问题提供了一种更符合人类认知的数学工具。Pawlak粗糙集模型的一个局限性就是它所处理的分类必须是完全正确的或肯定的,因为它是严格按照等价类来分“包含”或者“属于”。Pawlak粗糙集模型的另一个局限性是它所处理的对象是已知的且从模型中得到的所有结论仅仅适用于这些对象集。但在实际应用中,往往需要将一些小规模的对象集中得到的结论应用到大规模的对象集中去。变精度粗糙集模型是Ziarko W[5]提出的一种对粗糙集模型的扩充,在基本粗糙集模型的基础上引入错误分类率β(0≤β<0.5),允许一定程度上的错误分类存在,主要解决实际应用中属性间无函数或不确定关系的数据分类问题。文献[6]和[7]分别提出用变精度明确区域和变精度近似分类质量作为属性选择标准构造决策树,有效地减小了树的规模,提高了树的泛化能力。以变精度粗糙集模型为基础,对近似分类精度[8]属性选择方法加以改进,提出了以变精度加权平均粗糙度及其后继节点变精度加权平均粗糙度和值作为属性选择标准,对后继节点变精度加权平均粗糙度和值小的作为确定划分属性来构造决策树[9]。

1 相关概念

定义1:信息系统S=(U,A,V,F)。其中U={X1,X2,…Xn}是论域,A是属性集合,V是属性值集合,F是U×A→V的映射。若A=C∪D,C∩D=Φ,其中C是条件属性,D是决策属性,则该信息系统也称为决策表。IND(C)的等价类称为条件类,IND(D)的等价类称为决策类[10]。

定义2:多数包含关系[11](0≤β<0.5)

定义5:变精度加权平均粗糙度[13]

其中μβRi(Xj)=|RiβXj|/|RiβXj|,ω=|Xj|/|U|,Ri表示第i个条件属性,j表示决策属性的第j个等价类,m是决策树属性等价类的个数;Xj表示决策属性的第j个等价类集合,U表示非空有限集合(论域)。γβRi的取值范围是[0,1],γβRi越小则反映第i个属性包含的近似确定性越大。

2 改进的决策树构造算法

输入决策表和精度β,即可输出一棵决策树。

算法步骤如下:

步骤1:计算决策表中每一个条件属性的变精度加权平均粗糙度;

步骤2:计算分别以某一条件属性r作为决策划分属性时,其后继节点的变精度加权平均粗糙度之和,选择后继节点的变精度加权平均粗糙度的和值最小的属性r作为划分属性;

步骤3:用选择的属性r去划分训练集,相应于该属性的每一个取值产生一个分支(子表);

步骤4:若子表中属于某一类别实例个数占表中总实例个数大于等于(1-β)或表中没有可选的属性,则以该子表中占多数的实例类别标识该节点,并作为叶子结点;否则,将子表中的条件属性去掉已选划分属性r,重复上述过程;

步骤5:返回。

本算法与基于近似分类精度构造决策树方法的区别在于选择属性的标准不同,下面通过实例对两个算法进行比较。

3 实例分析

以表1为例构造决策树,比较用近似分类精度构造决策树和提出的改进算法生成的决策树。其中条件属性为:A、B、C、D,决策属性为E。

根据各条件属性及决策属性可以得到如下等价类:

在本例中设定β=0.29,计算各条件属性的变精度加权平均粗糙度,结果为:γAβ=0.9652,γBβ=0.7569,γβC=0.6597,γβD=0.6597。计算分别以属性A、B、C、D为根结点时其后继节点的变精度加权平均粗糙度的和值,属性C的和值最小,所以最终确定选择属性C作为根节点,并由它产生两个分支。每个分支对应着决策表中的一个子表,在每个子集上重复以上操作,直到分支子表某一类的数据个数占子表总数据个数比例不小于71%或表中没有可选的属性,以该类别名标识此节点作为叶子节点。图1就是本文提出的方法构造的决策树,图2是以近似精度为标准构造的决策树。

比较图1和图2,可以看出用改进算法构造的决策树可以使树的复杂度大大降低。本算法同时也允许叶子节点中有小于29%的误分数据,能够避免了分类过于细化,造成对训练集过度拟合,泛化能力不强等问题,更符合实际应用中经常存在噪声数据的情形。

结束语:提出以后继节点变精度加权平均粗糙度和值最小作为构造决策树的属性选择标准,通过一个具体的实例,可以看出用本文提出的改进方法构造决策树,可以有效弱化少数噪声数据对决策树造成的不良影响,虽然有时决策中可能存在一些误差,但决策树总体效果是比较好的,最终生成的决策树也比较简洁,并且大大提高了决策树的泛化能力。

摘要：决策树是一种有效的数据分类方法。粗糙集理论把知识和分类紧密联系起来,为处理不精确、不完全数据的分类问题提供了一种更符合人类认知的数学工具。提出了把后继节点的变精度加权平均粗糙度和值作为属性选择标准构造决策树的改进新算法。新算法用变精度代替近似精度,能有效地克服噪声数据在构造决策树过程中对刻画精度的影响,使生成的决策树复杂性降低,泛化能力更强。

关键词：决策树,粗糙集,变精度

决策粗糙集 篇2

其中，11例WHO I级，25例WHO II级，9例WHO III级，5例WHO IV级。

对上述患者进行MRI检查，平扫TIW1横断面与矢状面得出影像学资料。

由放射科专业医生对上述患者的MRI影像学资料进行分析研究，包括病灶位置、形状、囊变、TIW1、T2W1、水肿、钙化、出血、性变等等，按照影像学特征对不同指标进行分类。

并通过粗糙集方法、Logistic二元回归方法与分类回归树方法对影像学资料进行研究。

具体粗糙集方法：将决策表导入专门的Rosetta软件，通过软件对病例进行规则约简与属性约简。

在条件属性核产生的基础上，得到决策规则库，通过规则库过滤，达到知识的精简。

通过10折交叉验证方式测试胶质瘤数据，通过测试结果的诊断灵敏性、覆盖率、阳性预测值、特异度、阴性预测值等提取诊断性能，绘制ROC曲线。

结果显示，粗糙集方法的诊断准确性为85.2%，特异度为92.7%;决策树方法诊断准确性为83.0%，特异度为91.3%;Logistic二元回归方法诊断准确性为83.2%，特异度为85.6%。

决策粗糙集 篇3

摘 要：汽车物流供应链一个重要环节就是物流中心选址，于是选用合适的评价方法来进行物流中心选址就显得尤为重要。首先论述了汽车物流中心选址的重要性及影响因素，然后介绍了粗糙集的相关理论，并且运用实例验证了粗糙集方法在汽车物流中心选址中的应用。

关键词：汽车物流中心；影响因素；粗糙集

目前，物流产业已经成为国民经济中新的增长热点，是企业的第三利润源泉。物流中心在现代商品流通中发挥着重要作用，是整个物流系统中的枢纽环节物流中心选址是在一个经济区域内，选择一个地址构建物流中心的规划过程。因此，为了提高物流中心的运作效率和整个物流系统的绩效，对物流中心的选址问题的研究是建立物流系统中的一个关键环节。

1 物流中心选址的原则

为了保证所选物流中心以及整个物流系统的高效运作，在物流中心的选址过程中，必须遵循以下几个基本原则：

1.1 经济型原则

经济型原则考虑的是物流中心整体成本的因素。物流中心在运作过程中的总费用主要包括建设费用和经营费用两部分，建设费用是物流中心在建筑、设施、交通等中所花费的资金，经营费用是物流中心在提供服务的过程中所花费的管理费用。物流中心选址的地点不同，其所需建设费用和经营费用是不同的。

1.2 宏观性原则

宏观性原则是指在进行物流中心选址的时候，应从整体考虑，从长期考虑。在进行物流中心选址的过程中，要有战略眼光，不能只涉及部分，谋取短期利益。部分要服从整体，短期利益要服从长期利益。既要考虑整个物流中心的现在，又要考虑以后可能的发展。

1.3 一致性原则

物流中心的选址应将地区和国家的整体物流网络作为一个大系统来考虑，使得相关部分一致。在物流中心的固定设施与活动设施之间、自有设备与公用设备之间，各交通方式之间、区域之间、主要功能与其他物流中心功能之间、技术水平等方面达到协调一致。

1.4 适应性原则

物流中心的选址的时候，物流中心的设立与发展战略必须与国家以及省市的经济发展方针、政策相适应，与我国社会主义市场经济体制改革的方向相适应，与我国物流资源分布和需求分布相适应，与国民经济和社会发展的各个方面相适应。

2 物流中心选址的影响因素

在物流中心选址的过程中，一般主要考虑以下几方面的因素：

2.1 基础设施因素

基础设施因素主要考虑的是物流中心附近的交通条件和公共设施状况。由物流中心的性质决定，其必须具备方便的交通运输条件，良好的交通将对物流中心的发展以及各项功能的开展有很好的促进作用。在进行物流中心选址的时候，最好要靠近交通枢纽，有两种或两种以上交通运输方式相连接。

2.2 经营环境因素

在经营环境因素中，首先要考虑物流中心所在地区是否有对物流中心经济效益产生影响的优惠物流产业政策以及该地区的劳动力条件；然后考虑该地区的物流费用和商品特性，要选择物流费用低的地区，而且不同类型商品的物流中心要适应该地区的商品特性；其次要考虑该地区的物流服务水平，良好的物流服务水平会吸引顾客，提升综合能力；最后要考虑物流中心的周边状况，物流中心的规划要充分考虑周边情况的影响，要考虑保护自然环境与人文环境。

2.3 自然环境因素

自然环境因素主要包括土地资源利用因素、气象因素、地质因素、地形因素等。物流中心的规划应贯彻节约用地、充分利用国土资源的原则，考虑物流中心的发展，还需留有足够的备用地。

3 粗糙集理论介绍

粗糙集理论是波兰学者Z. Pawlak于1982年提出来的，它是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻画。

在粗糙集理论中，我们所要讨论和分析的对象用决策表来描述。在决策表中，每一列代表一种属性，每一行代表一个对象。属性来说又分为两种：条件属性、决策属性。为了方便理解和直观，我们用U代表论域，1，2，3……代表对象，A，B，C……代表属性。

表1 决策表

决策表1中，A、B、C、D代表四种不同的条件属性，E代表决策属性，1、2、3、4、5代表5个对象，表中的数字代表属性的值。当然，并不是所有的属性都是重要的，有些是多余的，去除掉这些属性也不会影响原来的分类。约简是指不含多余的属性并保证分类正确的最小条件属性集。当然，约简可能不是唯一的，一个决策表中可能存在多个约简。而所有这些约简的交集就构成了核，核中的属性就是影响分类的重要属性。posP(Q)表示论域U中所有根据分类U/P的信息可以准确地划分到关系Q的等价类中去的对象集合。当r∈p且posP(Q)=posP(p-{r})(Q)时，称r为P中Q不必要的，否则r为P中Q必要的。若r∈p都为P中Q必要的，则P相于Q独立。

4 粗糙集的应用

以某地要建一物流中心为例，介绍粗糙集理论在物流中心选址中的应用。在本文中，我们考虑四个最重要的影响因素作为我们选择物流中心的评价因素。四个评价因素分别是：基础设施、经营环境、候选地条件和竞争优势。表2为某地选择物流中心的决策表。

表2 某地选择物流中心的决策表

A1、A2、A3、A4代表条件属性，属性集{1，2，3}分别代表{一般，较好，好}。B代表决策属性集，属性集{1，2，3}分别代表{暂不考虑，一般考虑，重点考虑}。

根据粗糙集相关知识，首先整理决策表，消除决策表中重复的成员；再利用决策属性对于条件属性的依赖度，考察条件属性是否都是不可省略的，求出条件属性的所有决策属性相对约简，并对简化后的决策表中的重复成员进行合并，具体步骤如下：

U/{A1}={{1}，{2，3，4}，{5}}

U/{A2}={{1，2}，{3，4}，{5}}

U/{A3}={{1，2，3，5}，{4}}

U/{A4}={{1，3，4，5}，{2}}

U/{A1，A2，A3}={{1}，{2}，{3}，{4}，{5}}

U/{A1，A2，A4}={{1}，{2}，{3，4}，{5}}

U/{A1，A3，A4}={{1}，{2，3}，{4}，{5}}

U/{A2，A3，A4}={{1，2}，{3}，{4}，{5}}

U/{A1，A2，A3，A4}={{1}，{2}，{3}，{4}，{5}}

U/{B}={{1}，{2}，{3，4，5}}

posA(B)={1，2，3，4，5}

pos(A-A1)(B)={3，4，5} posA(B)

pos(A-A2)(B)={1，4，5} posA(B)

pos(A-A3)(B)= {1，2，5} posA(B)

pos(A-A4)(B)= {1，2，3，4，5}= posA(B)

所以，去掉属性A4不改变决策表的分类能力，所以A4为冗余属性，在决策表中去掉条件属性A4。

表3 去掉冗余属性后的决策表

得到5个规则，下面来求各规则的核值。第一条规则：A1[1] ，A2[1] ，A3[2]→B[1]。{ A1[1] ，A2[1] ，A3[2]}={{1}，{1，2}，{1，2，3，5}}，B[1]={1}，A1[1] A2[1]= {1} B[1]，A1[1] A3[2]= {1} B[1]，A2[1] A3[2]= {1，2} B[1]。由此可得，去掉A2[1]和A3[2]中任意一个，规则成立，但是去掉A1[1]，规则不成立，所以A1[1]是第一规则的核值。同理可以得到，A1[2]和A2[1]是第二规则的核值，A2[2]是第三规则的核值，第四规则和第五规则不存在核值。可以得到以下三个知识规则：A1[1]→B[1]；A1[2]，A2[1]→B[2]；A2[2]→B[3]。所以，在做本物流中心的选择的时候，选择的规则如下：(1)如果基础设施条件一般，我们暂不考虑将其考虑作为物流中心的选址地；(2)如果基础设施较好而经营环境一般，我们可以将其列为培养考虑对象；(3)如果经营环境较好，我们就可以将其列为发展考虑对象。根据规则(3)进行物流中心选址的时候，符合条件的是地址3、4、5。

5 结语

在物流快速发展和对经济贡献日趋重要的今天，物流中心的选择显得尤为重要。本文在研究同类文章的基础上，提出了运用粗糙集的知识来解决选址问题的方法，重点是运用粗糙集的约简理论来简化影响因素并找出知识规则，最后按照知识规则进行选址。

参考文献

[1] 史健. 区域物流中心选择的方法与实证研究[D].合肥工业大学硕士学位论文，2005，(4).

三枝决策粗糙集模型属性约简研究 篇4

粗糙集理论于1982年由波兰科学家Pawlak提出, 它是一种研究不确定、不完整知识和数据的表达、学习、归纳的理论方法。粗糙集理论引入上近似、下近似等概念开刻画知识的不确定性和模糊性;引入约减和求核进行知识的化简等计算。其中, 上下近似是粗糙集中的基础算子。经典的Pawlak粗糙集利用等价关系将论域分为正域、边界域和负域三个部分。但是, 它要求完全正确的决策才能进入正域, 这种严格的划分导致正域的对象非常少。针对上述Pawlak粗糙集模型没有考虑到容错的问题, 于是Wong和Ziarko将概率近似空间引入到粗糙集的研究中, 并提出0.5概率粗集模型。Ziarko提出了可变精度粗糙集模型。在1990年, Yao, Wong和Lingras提出了更一般性的概率粗糙集模型, 即决策粗糙集模型。随后, Yao进一步提出了三枝决策粗糙集, 它更能代表概率粗糙集的思想, 精确地反映了粗糙集的近似原理, 并可以用来解释实际生活中的很多决策现象。

属性约简是在保持系统分类能力不变的情况下, 为了提高数据处理的效率, 删除其中不重要的和无关属性, 也就是可以用较少的知识获得与原知识库相同的决策能力。属性约简是粗糙集理论的重要研究内容之一, 也是三枝决策粗糙集模型的主要研究内容。Yao和Zhao研究了决策粗糙集的属性约简, 指出决策粗糙集模型的约简理论不同于Pawlak粗糙集模型的约简理论, 它的约简考虑到不同的分类性能。

基于此, 本文主要在分析了决策粗糙集模型下的三枝决策思想的基础上, 介绍了三枝决策问题的粗糙集属性约简模型的属性约简方法, 并与Pawlak粗糙集属性约简、概率粗糙集模型的约简进行了比较, 最后简单说明了三枝决策在实际生活中的应用。

1 三枝决策粗糙集

1.1 决策粗糙集模型

由于在Pawlak粗集中, 只有完全包含于某个概念的等价类才属于集合X, 并没有考虑到规则的容错性, 这就需要引进条件概率、概率粗集等相关概念。Yao在文献[2,7]中论述决策粗糙集可转换为各种概率粗糙集。下面介绍相关决策粗集的基本概念和定义。

定义1 令Pr (X[x]) 表示任何一个实体属于[x]的条件属性X的条件概率。Prundefined表示集合中元素的基数。

定义2 用一对概率阈值来定义概率正、负和边界域。设0≤β<α≤1, 则 (β, α) 概率正、负和边界域为:

undefined

当β=0和α=1时, 上述模型将转化为Pawlak粗集模型。β=α=0.5时, 上述模型转换为0.5概率粗集模型。设S= (U, A, V, F) 是一个信息系统, Ω={w1, w2……wn}为n个状态集, A={a1, a2……am}为m个行动集。Pr (Wi|[x]) 表示x在状态wi下地条件概率。λ (aj|wi) 表示在状态wi下做出决策aj的损失。如果对象x采取了行动aj, 则其期望损失为:

undefined

贝叶斯决策论很广泛的应用于多个领域。决策粗糙集可以认为是贝叶斯决策理论的一个简单应用, 其描述如下:一个子集C⊆U, 可以构造一个含两个状态的集合Ω={C, Cc}, 对应于粗糙集的三个域, 我们可以构造一个决策动作集A={aP, aB, aN}, 其中, aP, aB和aN分别代表一个对象分类的动作, 即, 选择x∈POS (C) , x∈BND (C) 或x∈NEG (C) 。不同的决策会引导不同的分类错误, 也将产生不同的后果。这可以由一个3×2的矩阵表示, 如表1所示:

其中, λPP, λundefined和λNP分别表示当一个对象属于集合C时, 采用动作aP, aB和aN的损失。λPN, λundefined和λNN分别表示当一个对象不属于集合C时, 采用这些动作的损失。因此, 采取aP, aB和aN3种行动下的期望损失可分别表示为:

undefined

根据贝叶斯决策准则, 需要选择期望损失最小的行动集作为最佳行动方案, 于是可得到如下3条决策规则:

(P) : Ifundefinedandundefined, decidex∈POS (C) ;

(B) : Ifundefinedandundefined, decidex∈BND (C) ;

(N) : Ifundefinedandundefined, decidex∈NEG (C) (5)

由Pr (C|[x]) +Pr (Cc|[x]) =1, 上述规则只与概率Pr (C|[x]) 和相关的损失函数λ有关。对于决策代价函数值的大小, 有如下关系λPP≤λBP≤λNP, λNN≤λBN≤λPN。根据上述条件, 决策规则可重新定义为:

(P) : If Pr (C|[x]) ≥αand Pr (C|[x]) ≥γ, decidex∈POS (C) ;

(B) : If Pr (C|[x]) ≤αand Pr (C|[x]) ≥β, decidex∈BND (C) ;

(N) : If Pr (C|[x]) ≤βand Pr (C|[x]) ≤γ, decidex∈NEG (C) ;

其中, α, β和γ记为:

undefined

undefined

undefined (6)

在损失函数中如果增加一个条件:λ (P-B) Nλ (N-B) P>λ (B-N) Nλ (B-P) P, 可以得到α>β。由undefined, 即有α>γ>β≥0。决策规则仅用α和β来定义:

(P) : If Pr (C|[x]) ≥α, decidex∈POS (C) ;

(B) : If β

(N) : If Pr (C|[x]) ≤β, decidex∈NEG (C) ; (7)

决策粗糙集模型不仅基于概率模型, 而且阈值都是可计算得到的。正因如此, 决策粗糙集更能代表一般的概率粗糙集思想。

1.2 三枝决策的决策粗糙集理论

在决策粗糙集理论中, 论域α和β被划分为3个区域, 这3个区域对应了3个规则, 我们把这3个规则称为 (α, β) 三枝决策规则。如图1所示, 具体的说:

X发生的概率大于阈值α, 即从正域里获取的规则 (正规则) , 用来接受某事物 (acceptance) ;

X发生概率小于阈值β, 即从负域里获取规则 (负规则) , 用来表示拒绝某事物 (rejection) ;

X发生的概率介于阈值α和β之间, 即落在边界域上的规则 (边界规则) , 表示需要进一步观察, 即延迟决策 (deferment) 。

2 决策粗糙集理论的约简

属性约简是粗糙集理论的核心。约简是用来解决冗余或者可忽视的知识的问题, 直观地说, 属性约简就是从条件属性中发现部分必要的条件属性, 使这部分条件属性和所有条件属性相对于决策属性有相同的分类能力。

2.1 Pawlak约简

Pawlak约简R⊆C和决策属性D是密切相关的, 它被定义为正域不变的独立条件属性子集。π为条件属性集, πD={D1, D2, ..., Dm}为决策属性划分, πC为条件属性划分。假设一个信息表S= (U, At=C∪{D}, {Va|a∈At}, {Ia|a∈At}) , 一个属性集R⊆C是C关于D的一个pawlak约简, 则它满足如下2个条件:

(s) 正域不变性: POSπR (πD) =POSπC (πD)

(n) 独立性:∀a∈R, POSπR-{a} (πD) ≠POSπC (πD) (8)

在Pawlak粗糙集模型的约简中, 我们看到了2个极端置信度。根据Pawlk粗糙集中正域的定义, 正规则的置信度 (confidence) 为1。对于边界规则, 它的置信度大于等于0, 它是最小的置信度值。R⊆C是C关于D的一个pawlak约简, 则POSπR (πD) ∩BNDπR (πD) =ϕ;POSπR (πD) ∪BNDπR (πD) =U。POSπR (πD) =POSπC (πD) 等价于BNDπR (πD) =BNDπC (πD) 。因此, 在Pawlak约简中存在隐含的相同的边界域。

2.2 概率粗糙集模型约简

通过对Pawlak粗糙集模型约简的学习和分析, 发现该属性约简方法不适合概率粗糙集模型, 我们定义概率粗糙集模型的属性约简, 假设决定一个信息表, S= (U, At=C∪{D}, {Va|a∈At}, {Ia|a∈At}) 一个属性集R⊆C是C关于D的一个约简, 则它满足如下2个条件:

(s) 正域不变性:POSπR (α, β) (πD) =POSπC (α, β) (πD)

(n) 独立性: ∀a∈R, POSπR-{a} (α, β) (πD) ≠POSπC (α, β) (πD) (9)

概率粗糙集模型域的定义等价类[x]和决策类的交集不为空, 即[x]∩Dmax ([x]) ≠ϕ。负规则[x]→PDmax ([x]) 由阈值α决定, 边界规则[x]→BDmax ([x]) 由阈值β决定。阈值α可以不是最大值1, β可以不是最小值0。在概率粗糙集模型中, R⊆C是C关于D的一个约简, 则POSπR (πD) ∪BNDπR (πD) ≠U, 因此, 在约简时, 我们可以需要考虑正区域的概率和边界域的概率。

2.3 决策粗糙集约简

在Pawlak粗糙集模型中, 由于正域具有相对于条件属性的单调性, 约简只需保证条件属性相对决策属性的依赖度不变。然而, 在决策粗糙集模型中, 正域不再具有相对于条件属性的单调性, 仅保持依赖度γ不变不能作为决策粗糙集约简的判定依据, 还需要依靠其他的属性集度量标准 , 比如属性的置信度、覆盖度、代价等多个特性。在此对这些度量标准进行简单的介绍。

给定一个规则[x]→Di, 它的置信度被定义为:

undefined

=undefined (10)

规则的覆盖度可以表示为:

undefined

=undefined (11)

对于一个规则集而言, 它的共性度量如下:

undefined

=undefined (12)

对于某些属性而言, 它的表示方法不唯一。通常有三种表示形式:① eP, B, 主要是区分正域和边界域。它允许我们侧重强调正规则的有效性同时保持边界规则的有效性。②将边界规则和正规则相结合, 我们记为eP∪B, 但是这个方法降低了正规则的可信度③eP, P∪B, 分开计算正域和非负域。

考虑到这些度量标准和多个表示方法, Yao和Zhao等人在文献[9]中提出了一种适合决策粗糙集的新的约简方法。

给定一个信息表S= (U, At=C∪{D}, {Va|a∈At}, {Ia|a∈At}) 。假设通过E={e1, e2, ...}我们能够计算S的属性。R⊆C是C关于D的一个约简, 即满足如下2个条件:

(s) 性质保留性:e (πD|πR) ≥e (πD|πC)

(n) 属性独立性:∀R'⊂R, e (πD|πR') ≥e (πD|πC) (13)

3 结束语

决策粗糙集模型将粗糙集理论、贝叶斯分析以及概率进行结合。该模型是基于Pawlak粗集的容错性较差的基础上提出来的。三枝决策是基于粗糙集的正域、边界域和负域以及假设验证提出的, 它可以用来解释生活中得很多决策现象。比如:医生看病, 肯定的规则[x]→PWc就意味着对病人立即实施治疗;否定的规则[x]→PWH表示不治疗;边界规则[x]→PWc或者[x]→PWH意味着医生要对病人进行进一步的观察。这样的例子还很多。决策粗糙集理论在医疗、管理、网络支持系统、属性选择等方面应用广泛。例如, J.T.Yao等人给出了基于DTRS的医疗网络支持系统, Zhao等人设计了一种基于决策粗糙集方法的电子邮件过滤系统。可见, 决策粗糙集模型在实际生活中应用很广泛。

摘要：三枝决策粗糙集模型作为Pawlak粗糙集模型的推广, 它是将贝叶斯决策过程引入到概率粗集模型中得到的, 其区域分类以正、负和边界为基础, 可以更精确地体现粗糙集的近似基本原理。描述了三枝决策粗糙集模型的约简, 并与Pawlak粗糙集模型、概率粗糙集模型进行比较;最后讨论了三枝决策概率粗糙集在实际问题中的应用。

关键词：三枝决策,概率粗糙集,Pawlak粗糙集,属性约简

参考文献

[1]邱玉霞.进化计算玉粗糙集研究及应用[M].北京:冶金工业出版社, 2009.

[2]YAO Y Y, WONG S K M, LINGRAS P.A decision-theoretic ro-ugh set models[C].RAS Z W, ZEMANKOVAM, EMRICHM ML.Proceedings of the 5nd InternationalSymposium on Methodolo-gies for Intelligeny Systems 1990.North-Holland:[s.n.], 1990.

[3]YAO Y Y.Three-way decision with probabilistic rough sets[J].In-formation Sciences, 2010 (180) .

[4]刘盾, 姚一豫, 李天瑞.三枝决策粗糙集[J].计算机科学:2011 (6) .

[5]YAO Y Y, Xiaofei Deng.Sequential three-way decision with proba-bilistic rough sets[J].Information Sciences, 2010 (180) .

[6]YAO Y Y.Decision-theoretic rough set models[J].Lecture Notesin Artificial Intelligence, 2007 (4481) .

[7]YAO Y Y.Decision-theoretic rough set models[C].Yao J, LingrasP, Wu W Z, et al.Proceedings of the 2nd International conferenceon Rough sets and Knowledge technology 2007, Lecture Notes inComputer Science 4481.Heidelberg:Spring-er, 2007.

[8]李华雄, 刘盾, 周献中.决策粗糙集模型研究综述[J].重庆邮电大学学报, 2010 (6) .

决策粗糙集 篇5

基于粗糙集的社区卫生服务满意度评价 作者：李丽清 许跃峰 周小军 李钟捷

来源：《中国全科医学·学术版A》2013年第08期

决策粗糙集 篇6

关键词:入侵检测;粗糙集;网络安全;属性约简

中图分类号:TN915.08 文献标识码:A文章编号:1007-9599 (2010) 04-0000-01

Research of Intrusion Detection System Model Based on Rough Set Theory

Su Hang,Li Yanqing

(DalianTransportation University,Education Technical Center Network Technology Department,Dalian116028,China)

Abstract:The Intrusion Detection System as a key technology and important means to protect network security has become a hot research area.Rough sets as a new mathematical tool to deal with the fuzzy and uncertain knowledge.It has important practical significance to use it in intrusion detection.

Keywords:Intrusion detection;Rough sets;Network security;Attribute reduction

一、引言

随着计算机网络和信息技术的发展,人们对互联网的使用越来越频繁,这也使得网络安全问题变得越发重要[1]。入侵检测系统作为保护网络系统安全的关键技术和重要手段,已经成为当前网络安全方面研究的热点和重要方向。

二、粗糙集理论

(一)粗糙集基本概念

1.知识分类的概念

知识是人类通过实践认识到的客观世界的规律性的东西,是人类实践经验的总结和提炼,具有抽象和普遍的特性。人工智能研究中的一个重要概念是智能需要知识。从认知科学的观点来看,可以认为知识来源于人类以及其他物种的分类能力,知识即是将对象进行分类的能力。设 是我们感兴趣的对象组成的有限集合,称为论域。以分类为基础,可以将分类理解为等价关系,而这些等价关系对论域 进行划分。

2.粗糙集及其近似

定义1 设 是对象集, 是 上的等价关系[2]。

(1)称 为近似空间,由 产生的等价类为 ,其中 。

(2)对于任意 ,记 , ,称 为 的下近似, 为 的上近似。

(3)若 ,称 为可定义的集合,否则称 为粗糙集(图1)。

(4) 的 边界域定义为

(5)集合 称为 的 正域, 称为 的 负域。

(二)近似精度与粗糙度

定义设集合 是论域 上的一个关于 的粗糙集,定义 关于 的近似精度为 ,其中 ; 表示集合中所包含元素的数目,称集合的基数或势。

定义 设集合 是论域 上的一个关于 的粗糙集,定义 的 粗糙度为 。如果 ,则集合 关于 是普遍集合;如果 ,则集合 关于 是粗糙集合。

(三)核与约简

属性约简包括两个概念:约简(reduce)和核(core)。属性约简是指关系的最小不可省略子集,而属性的核则是指最重要的关系集。

定义* 对于一给定的决策系统 ,条件属性集合 的约简是 的一个非空子集 。它满足:1, 都是 不可省略的 2则称 是 的一个约简, 中所有约简的集合记作 。

三、入侵检测模型

(一)入侵检测系统

入侵检测系统全称为Intrusion Detection System,简称IDS。它从计算机网络系统中的若干关键点收集信息,并分析这些信息,检查网络中是否有违反安全策略的行为和遭到袭击的迹象。进行入侵检测的软件与硬件的组合便是入侵检测系统。入侵检测作为一种积极主动的安全防护技术,提供了对内部攻击、外部攻击和误操作的实时保护,在网络系统受到危害之前拦截和响应入侵。入侵检测系统能很好的弥补防火墙的不足,从某种意义上说是入侵检测是防火墙之后的第二道安全闸门。

(二)粗糙集理论在入侵检测中的应用

本文主要探讨判断当前的网络连接是正常连接还是入侵,实现这个功能的系统模型分为四个部分。第一,数据预处理。主要包括删除重复记录,决策表缺失内容修正,数据离散化。第二,属性约简。采集到的大量数据里面包含了多种信息,但是所有的信息并不是同等重要的,有些时候是冗余的,通过属性约简可以有效去掉冗余信息以便得到更为简捷的决策规则。第三,根据约简结果得到逻辑规则。本文入侵检测系统体系结构如图2所示。

(三)基于信息熵的属性约简改进算法

属性约简部分是基于粗糙集理论的入侵系统模型中非常重要的部分,本文对一种基于信息熵的属性约简算法进行改进,使得算法更高效。文献[3]提出的cebarkcc算法是一种比较典型的基于信息熵的属性约简算法,该算法是建立在决策属性集相对于条件属性集额条件熵的基础上的,以 作为启发式信息,以 作为算法的终止条件。它以决策表核属性集为起点,逐次选择使 最小的非核条件属性 添加到核属性集中,直到满足终止条件 。该算法步骤文献[44]中有详细说明,本文不在细述,现将改进算法步骤描述如下:

Cebarkcc的改进算法:

输入:一个决策表 ,其中, 为论域, 和 分别为条件属性集和决策属性集;

输出:决策表 的一个相对约简 ;

Step1:计算决策表 中决策属性集 相对条件属性集 的条件熵 ;

Step2:计算条件属性集 中相对于决策属性集 的核属性 ,并令 , ;

Step3:

Step3.1:计算条件信息熵 ,转Step3.4;

Step3.2:对 , 中的每个属性计算条件熵 ,求 得到属性 的重要度 ;

Step3.3:选择使 最大的属性 (若同时有多个属性达到最小值,则从中选取一个与 的属性值组合数最少的属性),把 从 中删除,并把 增加到 的尾部;同时从 中删除使 的值为零的属性 ;

Step3.4:如果 ,则转Step4,否则转Step3.2;

Step4:从 的尾部开始,从后向前判别每个属性的 是否可约。如果 ,则从 开始向前的属性都是核属性,不可约,算法终止;否则,如果 ,则 是可约简的,把 从 中删除。

四、结论

一个完善的入侵检测系统是对系统防火墙有益的补充,能够在网络系统受到危害之前拦截和响应入侵。但是现今网络数据量非常大,环境复杂,这就需要入侵检测系统更加智能,能够适应复杂多变的环境。粗糙集能够不需要任何附加信息和先验知识的情况下,对数据进行分析从而得出人们想要的结果。所以将粗糙集理论应用于入侵检测系统是可行而且有效的,本文同时给出了改进的约简算法,该算法较先前算法效率更高,约简效果更好。

参考文献:

[1]肖晓春.基于模型的网络安全风险评估的研究,复旦大学,2008

[2]张文修,仇国芳.基于粗糙集的不确定决策.清华大学出版社

决策粗糙集 篇7

UPS(不间断电源)的响应控制是指UPS根据输入设备及输出负载实时状态的变化,做出正确判断和相应切换动作,以确保负载正常运作和UPS安全、稳定。现代UPS的发展要求负载具有更宽的适应性,这对后备式UPS的响应控制提出了新的要求。

传统的UPS响应控制策略主要基于专家系统的规则提取法,借助设计者的经验,以人为的方式定义规则和参数,但由于不同设计者对于各种负载特性的理解和认识的差异,同一反馈现象所判定的负载类型和相应的动作规则都可能有所不同,甚至出现矛盾,这都是由于获取决策规则时的主观性所决定的[1,2]。

粗糙集作为处理不确定、不完整、不精确知识的数学基础和工具,具有两个显著的特点:一是粗糙集理论利用本身提供的信息,无需提供所处理数据集合以外的任何先验知识,在保持分类能力不变的情况下,仅根据观测数据本身的约简来删除冗余信息,导出问题的决策或分类规则;二是粗糙集理论具备从大量数据中求取不变集合(称为核)与求解最小规则集(称为约简)的能力,这一特征可用来简化冗余属性,提取有用的特征信息。基于以上优点,本文把粗糙集运用在后备式UPS的响应的控制中,处理UPS多种负载条件下的响应控制问题,通过实例验证,取得了较好的效果。

1粗糙集基本概念

粗糙集从模式分类的观点来描述知识,通过不可分辨的等价关系,将知识空间划分为不同的模式等价类,从而将知识空间表示为粒状结构,正是因为知识的这种粒状结构。造成知识表示的粗糙性。下面介绍几个粗糙集的基本概念[3]。

1.1不可分辨关系

令子集X⊆U,二元关系R是对论域U进行划分的一个等价关系,R满足自反性、对称性、传递性,则一个划分U/R定义如下。

定义 划分U/R={X1,X2,…,Xn };Xi⊆U,Xi≠Φ,Xi∩Xj=Φ;undefined;其中i≠j;i=1,2,…,n。

任意Xi⊂U/R称之为R等价类,∀x,y∈Xi(i=1,2,…,n),有(x,y)∈R,记做xRy,表示x和y关于R有不可区分性。其中包含x的等价类记做[x]R。论域U的所有等价关系族R={R},构成信息系统K=(U,R)。若P⊆R,且P≠Φ,则∩P(P中所有等价关系的交集)也是一个等价关系,称为P上的不可分辨关系,记为ind(P),且有:

undefined

1.2上下近似集和粗糙集

令子集X⊆U,R是U上的一个不可分辨等价关系,如果X能表达成U/R中某些等价类的并时,则称集合X是R可定义集或R精确集,否则集合X是R不可定义集或R粗糙集。粗糙集X可以用R上、下近似集

undefined

undefined称为X的R边界域,undefined称为X的R正域,negR(x)=U-undefined称为X的R负域。正域undefined是根据R判定肯定

属于X的U中的元素的集合,负域undefined是根据R判定肯定不属于X的U中的元素的集合,而undefined(x)是根据R判断可能属于X的U中的元素的集合,BNR(x)是根据R既不能判断肯定属于X、也不能判断肯定地属于～X(即U-X)的U中的元素的集合。

1.3属性的约简

关于属性的约简,目前最常用的方法就是利用DM(区分矩阵)[4,5]来计算,它的优点是能容易地计算约简和核。DM是由波兰数学家Skowron提出的,其定义为:对于知识系统S=(U,A,V,f),U为论域,Xi为论域中的对象,U={x1,x2,…,xn}。A为非空的属性集合,A=C∪D,C={c1,c2,…,cm}是条件属性集合,D={d}是决策属性,且C∩D=Φ。对于系统S的决策DM,其阶数与论域中的对象数量有关,即为n×n阶,记为MDS(C):

undefined

式中:1≤j≤i≤n;-1表示决策不一致时的论域对象所对应的DRDM矩阵的元素值。在生成决策区分矩阵的同时,通过-1值数量的增加,得到了不一致对象的数量。DRDM矩阵的元素mDSij是区分对象xi和xj的所有条件属性的集合。区分函数fDRDS的定义如下:

undefined

式中:mDSij={a|a∈mDSij};利用DM表示知识有许多优点,特别是它能容易地计算出约简和核。经过属性值约简,可以自动生成决策规则。

2基于粗糙集的决策规则提取

文献[6]阐述了粗糙控制的理论基础,并给出了粗糙控制的一些基本观点和方式,即粗糙控制是一种基于规则的控制,控制规则来源于对经验的化简,主要包括以下步骤。

2.1属性的选择及数据的获取

影响UPS响应动作的主要不确定因素在于外部多种不确定的负载类型以及内部电路的高频干扰,因此,UPS所有的决策动作都是基于发出动作响应前对当前UPS外界状态以及内部状态监测和判断。本文将所有输入输出的电压电流,以及内部电池电压选取为条件属性。再根据以往的设计经验,定义出UPS的响应动作,作为决策属性,如表1所示,其中C表示条件属性,D表示决策属性。

UPS通过精确的硬件电路对各条件属性的侦测点进行采样,获取即时的反馈数据。当然,从实现上,无论电压采集还是电流采集都是以电压值方式计算的。

2.2数据归一化处理

对于后备式UPS而言,外界负载类型的差异往往导致切换策略的不同,也就是各侦测点的采样数值不同,由于采样值均为电压值,且各功能电路的侦测点的幅值、频率响应等均存在很大的差异,因此,在使用粗糙集理论提取决策规则时,必须先对数据做归一化处理,本文中将实际测得的状态数据转化为决策类型的隶属度值。定义隶属度函数μ(x)的表达式如下:

undefined

式中:x为被侦测电路点的实际电压值;x0为UPS正常做出响应时应测得的标准电压的参考值;a为修正系数;e为侦测电路点的正常浮动范围,即容差;t为侦测电路点的极限偏差;μ为侦测电路点属于某种负载的隶属度。

这样,对于不同负载下的切换决策,粗糙集中的属性归一化时,x0、a、e、t值有所不同,归一化后数据具有同一性,便于离散化处理。

2.3数据离散化[7]

由于采样侦测数据经过归一化后的决策隶属度呈连续性,而粗糙集只能处理离散数据,所以还必须对连续的属性进行离散化处理。在目前已有的文献中,属性离散化方法主要有最小熵方法、最小误差方法及K均值动态聚类算法等。

本文采用K均值动态聚类算法,先选择若干聚类中心,再按事先确定的聚类准则进行聚类,根据聚类准则对聚类中心反复进行修改,直到分类合理为止。

在修改的过程中,K的取值很重要。K值过小,则属性的离散化较粗,可能导致划分的决策表不相容;如划分较细,则可能使划分后的决策表中仍然含有很多冗余信息,使得属性约简效率降低。因此,连续属性离散化的目标是:在保证划分后决策表相容的前提下,寻找使得约简效率最高的划分。

2.4属性约简及规则提取

组织决策表,条件属性为各采样侦测点测得数据经过归一化和离散预处理后的值,决策属性为UPS的对应的切换响应策略。本文使用DM进行属性约简,带入式(4)和式(5)进行计算,剔除冗余属性,找出核心属性,从中提出最简规则。规则的获取采用产生式规则表示法,形式如下:

if“条件1”and“条件2”…and“”,then“结论或动作”

将形如上面的所有的规则存入知识库,从而形成一整套控制决策系统。

3粗糙集决策系统在后备式UPS中的应用

3.1基本模型框架

基于粗糙集决策系统的后备式UPS的控制基本模型及基本流程如图1所示。

该控制模型的关键问题在于:对各条件属性所对应的侦测点采集数据,从中选取训练样本,通过训练,得到决策规则,并从采集的数据中选取一部分作为验证样本,以验证决策规则的有效性。如果验证结果不满意,必须调整样本的选取,重新选取训练样本及重新选取验证样本,直至决策结果满意为止。

3.2实际产品实验

以某公司后备式UPS产品代号为VT600的机型为实验对象,选取该机的动作响应的电压参考值为条件属性数据,输入到粗糙集决策系统模型中进行规则提取,其中D1、D2、D3的定义如表1所示,分别为UPS的AC-DC切换、DC-AC切换以及关机动作。

测试对象:VT600系列1台。

测试仪器:CP-660,AC SOURCE CIF-1030A,整流器,灯泡,Tektronix TPS2014示波器。

测试方法:分别以电阻和整流器作为VT600的负载,调整AC SOURCE 电压和频率,模拟输入市电的变动,测试UPS在空载、50%负载、80%负载、满载下的响应,记录响应时的输入电压、输出电压、电池电压。

样本选取:共记录120组数据,取其中的100组用做训练样本、20组用做验证样本。

表2为对取得的样本数据归一化处理后的决策隶属度数据,共100组。

表3为表2中的数据经过K均值动态聚类化离散处理后的的结果,其中a、b、c、为条件属性,分别与表2中的μ(c1)、μ(c2)、μ(c3)对应,D为决策属性,对应表2中的决策动作。

对表3中相同的知识进行合并预处理,接着用DM进行属性约简,得到约简后的决策表(见表4)。

在此基础上进行规则提取,并将相同的规则合并,如序号2和4,最终得到决策规则如下:

Rl:if a=1 and b=0 then d=1;

R2:if a=0 and b=2 then d=2;

R3:if a=0 and b=1 then d=2;

R4:if a=0 and b=0 then d=3。

将此规则使用验证数据进行验证,审视验证结果以确认决策是否满意。本文进行了5次取样,以构成不同的样本分布率,实验结果如表5所示。

可以看出,由于样本选取的关系,决策的验证结果存有不小的差距,其中2、3次取样已经取得了很好的效果,完全可以应用到后备式UPS的响应控制中。

4结束语

本文结合现今后备式UPS适用于多种负载的响应问题的特点,给出了一种基于粗糙集决策规则的提取方案,该方法先对原始侦测数据进行归一化和离散化预处理,然后形成决策表,用粗糙集进行属性约简,提取最终决策规则,再根据系统的要求调整样本的选取,以获得最佳的决策效果。通过实例验证,效果良好,有一定的实际应用价值。

参考文献

[1]菅利荣,达庆利,陈伟达.基于粗糙集的不一致信息系统规则获取方法[J].中国管理科学,2003,11(4):91-94.

[2]黄文涛,赵学增,王伟杰.汽轮发电机组振动故障诊断的粗糙集模型[J].电力系统自动化,2004,28(15):80-84.

[3]张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].北京:科学出版社,2003.

[4]PAWLAK Z.Rough sets and intelligent data analysis[J].In-formation Sciences,2002,147(1-4):1-12.

[5]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.

[6]MUNAKATA T.PAWLAK Z.Rough control application ofrough set theory to control[C]//Proceedings of 4th EuropeanCongress on Intelligent Techniques and Soft Computing,Sep2-5,1996,Aachen,Germany,1996:209-218.

决策粗糙集 篇8

复杂机电产 品 (complex mechatronic products)是由机械结构、电器设备、控制装置、检测装置等有机组合在一起的复杂系统,是机、电、液、 控、光、磁、热等多种物理过程融合于同一载体的复杂系统,是涉及多学科、多领域、多因素具有复杂功能的一类产品[1]。线缆作为传输能量和信号的介质,被大量应用于航空、航天、汽车、船舶等各类复杂机电产品中,是连接电子设备与各分机模块的“纽带”,线缆的敷设质量和装配质量已成为衡量产品整机性能和可靠性的一个重要指标[2,3]。

目前在复杂机电产品中由于缺乏有效的方法和工具支持,线缆的敷设主要还是依靠现场装配工作人员的经验,线缆的敷设质量和合理性在很大程度上取决于以往经验的总结和实验方法的验证,由此造成的线缆敷设过程的不规范、一致性差以及接插件可靠性问题直接影响到线缆的敷设质量[2],进而影响产品设备整体电气和电磁兼容性能的发挥,产品的最终性能也难以得到保证。因此迫切需要在线缆敷设过程中依据以往的成功经验和产品试运行参数值对线缆的敷设质量进行评估,将产品正式投入使用过程中可能出现的由于线缆敷设而造成的问题在早期就被发现并予以解决,从而缩短产品的研制周期、降低研发成本,最终提升产品在市场中的竞争力。为此,有学者开展了相关的研究工作,如Mazzuchi等[4]针对飞机上出现的线缆故障问题,利用获取到的线缆故障数据建立了相应的参数模型和故障率回归模型, 并在此基础上采用成对比较的实验方法进行了飞机布线风险评估。Tsai[5]采用灰色关联分析法和神经模糊技术开发了一个自适应诊断系统,并将其应用于集成电路装配中的引线接合工艺控制和质量评估中。王玉龙[6]针对目前复杂电子设备主要通过人工手段进行综合布线检测而存在周期长、效率低和漏检率高等问题,以CH+测试仪为基础,设计了一款系统综合布线测试平台,通过编程和自动学习功能来完成电缆和线束的自动测试,以提高布 线质量。 此外,美国福禄 克网络 (Fluke Networks)公司于2008年推出了一款全新的电缆测试结果分析软件LinkWare Stats,可用于对整个网络布线系统进行统计分析并制定测试报告,该软件能将大部分布线系统的数据进行汇总,使用人员可以全面查看电缆的性能数据[7]。 另有美国泰克(Tektronix)公司[8]、英国雷迪(Radiodetection/SPX)公司[9]等也研发出了相关的线缆性能测试仪。

上述学者的研究和相关公司研发出的产品主要面向集成电路和网络布线系统,而对于复杂机电产品(如卫星、雷达、导弹等)中的线缆敷设质量评估还存在很大的局限性。虽然Mazzuchi等[5]开展了对飞机布线风险评估的研究,但也只是在飞机正式投入使用后对线缆产生的故障数据进行分析研究,而不是在飞机正式投入使用前(即线缆敷设过程中)对其进行风险评估。

复杂机电产品的线缆敷设是一项耗时、耗力的工作,需要综合协调和满足线缆功能、布局设计、敷设工艺和维修以及检测等各环节的基本要求,其质量评估属于多目标决策问题。

本文采用变精度粗糙集理论,以某相控阵雷达天线阵的布线设计为研究对象,在建立线缆敷设质量评估模型的基础上,构建了线缆敷设质量的评估规则和知识表达方法,通过确定正确分类率和求解属性约简集,获取简化后的评估规则,最后结合加权相似性度量方法完成质量评估,给出了决策结果。

1变精度粗糙集基本概念

粗糙集(rough sets,RS)理论是由Pawlak[10]于1982年提出的一种处理模糊和不确定性知识的数学方法,该方法已成为机器学习、知识发现、 知识获取、决策分析等领域的一种重要研究方法。 但Pawlak提出的粗糙集模型所处理的信息必须是完全正确的或肯定的,而对模糊信息处理能力不强,容错性不高。为此,Ziarko[11]在Pawlak粗糙集模型的基础上引入了分类误差率β(0<β≤ 0.5),即允许一定程度的错误分类率存在,并于1993年提出了一种变精度粗糙集(variable precision rough set,VPRS)模型来克服上述问题。

1.1相对错误分类率

设X和Y为论域U的非空子集。如果对于每一个e∈X有e∈Y,则称Y包含X,记作Y X。令

式中,|X|为集合X的基数,它的值为其所包含对象的个数;c(X,Y)为集合X关于集合Y的相对错误分类率。

1.2β正域、负域及边界域

设(U,R)为近似空间,其中论域U为非空有限集合,R为U上的等价关系,U/R = {E1,E2, …,En}为R的等价类或基本集(Ei)构成的集合, 0<β≤0.5。对于XU,定义:

(1)X的β-R正域为

Ppos(β,X)=∪ {E ∈U/R|c(E,X)≤β}

(2)X的β-R负域为

Nneg(β,X)=∪ {E ∈U/R|c(E,X)≥1-β}

(3)X的β-R边界域为

Bbnr(β,X)=∪ {E ∈U/R|β<c(E,X)<1-β}

X的 β -R正域可理解为将论域U中的对象以不大于 β 的分类误差分于X的集合 ; X的 β -R负域可理解为将论域U中的对象以不大于 β 的分类误差分于X的补集 ( 即 ~ X ) 的集合 , 即对于成立 , 其中 , ~X =U-X 。 X的 β -R边界域则是由那些以不大于 β 的分类误差既不能分类于X又不能分类于 ~ X的U中对象所构成的集合 。

2线缆敷设质量评估模型

2.1评估模型的构建

在实际工程中,天线阵布线是相控阵雷达天线设计的一个难点,线缆敷设质量的优劣将直接影响雷达的战术技术指标。不合理的线缆敷设, 不仅会影响到天线阵内部设备安装,而且会给线缆接头处带来无法消除的应力,严重时将造成接触不良、断路、短路等故障而影响设备的正常工作[12]。为进行相控阵雷达线缆敷设质量的评估, 本文基于线缆的电气性能和机械性能两种物理约束构建了线缆敷设质量评估模型,如图1所示。

线缆敷设质量评估模型主要包含三个模块: 原始信息获取、指标属性提取与量化以及线缆敷设质量评估。

(1)原始信息获取。原始信息获取是质量评估模型的基础模块,该模块主要通过数据采集设备如线缆测试仪、绝缘测试仪、信号传感器、EMC测试器等获取线缆敷设的相关信息,通过对采集的数据进行特征提取(包括分布电容值、线间串扰值等)完成问题检测。原始信息的采集是线缆敷设质量评估的数据源。

(2)指标属性提取与量化。该模块是评估模型的中间过程,主要功能是完成指标属性的提取和关联,并对属性指标进行量化。指标属性的提取主要包含对线缆敷设和整机性能影响较大的因素,如电磁兼容性、线间耦合串扰程度、杂散电磁场强度等,通过属性指标的量化操作,使得指标属性具有相应的属性值,从而作为线缆敷设质量评估的依据。

(3)敷设质量评估。该模块是整个模型的评估层,也是为线缆敷设质量提供决策依据的层。 在这一模块中,通过建立指标属性中条件属性与决策属性之间的关联性,评估线缆敷设质量的达标要求,给出线缆敷设质量的达标程度。通过设置质量评估系统的误差程度,并反馈给指标属性提取与量化模块,对相关属性值作适当的调整和优化,不断改善敷设方法,提升敷设质量,最终达到整机的电气、电磁兼容等性能指标。

2.2评估指标属性设计

线缆敷设质量评估中评估的对象 有多种属 性,这些属性从不同角度反映了评估对象的不同特征,而这些特征往往又带有一定程度的模糊性, 即具有非线性特征。针对某相控阵雷达的线缆敷设,选取以下属性作为敷设质量的评估指标:电磁兼容性 (a1)、分布电容(a2)、杂散电磁场(a3)、线缆间绝缘强度(a4)、线间耦合串扰程度(a5)、线缆布设绑扎工艺(a6)、线缆布设防护工艺(a7)、线缆空间布局(a8)以及敷设质量(d)。其中“敷设质量 (d)”为决策属性,其余为条件属性。

对线缆敷设质量评估指标属性进行量化,结果如表1和表2所示。

3线缆敷设质量评估变精度粗糙集决策方法

VPRS模型允许 一定程度 的错误分 类率存在,具有对噪声数据的适应能力,可以有效地分析不完备或不精确信息。VPRS模型通过设置精度系数或包含度β,放宽了标准粗糙集理论对边界的严格定义,柔化了边界。β的取值有两种方式 , Ziarko[11]把β定义为分类误差率,其取值范围为 (0.0,0.5],而An等[13]定义β为分类正确率,其取值范围为(0.5,1],本文采用文献[13]的定义模式。

3.1敷设质量评估指标属性的粗糙化描述

形式上,设四元组S= (U,A,V,f)为一个线缆敷设质量评估知识表达系统。其中,U = {x1, x2,…,xn}为对象的非空有限集合,称为论域,本文中即为以往线缆敷设案例或样本集以及相对应的敷设结果质量等级;A为属性的非空有限集合, V =∪Va,a∈A,Va为属性a的值;f:U×A →V是一个信息函数,它为每个对象的每个属性赋予一个信息值,即 a∈A,x∈U,f(x,a)∈Va;属性A =C ∪D,且C ∩D = Ø,其中,C为质量评估要素的条件属性集,D = {d}为决策属性集,具有条件属性和决策属性的知识表达系统称为决策表。

定义1在决策表S = (U,A,V,f)中,对 P ∈A,定义P上的不可区分关系为ind(P)= {(x,y)∈U ×U|a∈P,f(x,a)=f(y,a)}, 其中ind(P)是一个等价关系,在U上形成一个划分U/ind(P),简写为U/P。

定义2设R为U上的一个等价关系 , X =R ( x ) 为由R产生的等价类 ,表示由R产生的一个划分;U/C= {c1,c2,…,cm}和U/D = {d1,d2,…,dn}分别表示U在条件属性集C和决策属性集D上产生的划分。则决策类的粗糙隶属函数可定义为

其中,|·|表示集合的基数;等价类R(x)=U/C, P(dj|R(x))表示x属于dj的置信度。

定义3对于PC、x∈U,给定阈值0.5< β≤1,定义dj的β下近似和β上近似分别为

定义4设决策表S= ( U , A , V , f ), C 、 D分别表示条件属性和决策属性 ,, C 对 D 的近似分类质量为

显然,0≤γβ(C,D)≤1,γβ(C,D)的大小从总体上反映了C可能正确的分类知识在现有知识中的百分比;若γβ(C,D)=0,则属性集C对于D是不重要的。近似约简γβ(C,D)表示为给定β值条件下保证正确分类的最小约简条件属性子集,且满足:1γβ(C,D)=γβ(γβ(C,D),D);2去掉γβ(C, D)中的任意一个属性都会使式1不成立。

3.2可辨别阈值β值的确定

由文献[11]可知,近似分类程度

若满足α(apr,β,dj)= 1,则称决策 类dj为β 可辨别 ,否则为β不可辨别 。决策类边 界的可辨 别概念是 相对的 ,如果在变 精度粗糙 集中允许 一个较小 的分类误 差率存在 ,则决策类 可能有较 大的可辨 别性 。β值的确定 原则可由 文献[14]给出 :选定β值下的分 类质量使 其尽可能 大 ,根据被选 定的β值给出的 约简属性 集中的属 性个数应 尽可能少。

对于每一个决策属性dj都存在一个阈值β, 使得dj在这个阈值水平上是可辨别的。令

其中,ndis(R,dj)为满足决策类dj不可分辨的β 值的集合;满足dj为可分辨的β的最大值称为可辨别的阈值,根据文献[15]给出的定理可知,该阈值等于ndis(R,dj)的最小上界[16],即

3.3条件属性的权重计算方法

在简约决策表中,不同的评估指标属性对线缆敷设质量评估的重要程度是不同的。当衡量各指标对敷设质量综合评价的贡献时,应赋予不同的权重。本文基于文献[17?18]的方法来求解属性的客观权重,即在由代数观和信息熵下的属性重要性确定权重的基础上,将两者进行有机地集成,从而最终确定属性的客观权重。

3.3.1基于代数观的属性权重

设C = {a1,a2,…,am}为条件属 性集,对 ai∈C(i=1,2,…,m),有

式中,P(d|C)为评估结果对整个条件属性域的依赖度; P(d|C- {ai})为评估结果对删除属性(即评估指标)ai后得到对剩余条件属性域的依赖度。

对式(7)中的P(d|ai)进行归一化处理,得到属性ai基于代数观的权重为

3.3.2基于信息熵的属性权重

定义5设决策表S = (U,C∪ D,V,f),C和D分别为条件属性集和决策属性集,设X和Y分别表示由等价关系ind(C)和ind(D)导出的U上的划分,X =U/ind(C)= {X1,X2,…,Xn}、Y =U/ind(D)= {Y1,Y2,…,Ym},且

则(p(X1),p(X2),…,p(Xn))和(p(Y1),p(Y2), …,p(Ym))分别为C和D在X和Y上的有限概率分布。

定义6属性集C的信息熵H (C)定义为

当pi=0时,规定0·lb0=0。

定义7属性集D(Y =U/ind(D)= {Y1, Y2,…,Ym})相对于属性集C(X =U/ind(C)= {X1,X2,…,Xn})的条件熵H(D|C)定义为

定义8设S = (U,C∪ D,V,f)是一个决策表系统,其中C为条件属性集合,D = {d}是决策属性集合,且AC,则对任意属性a∈C-A的重要性Ssig(a,A,D)定义为

其中,H(D|A)表示属性集D相对于属性集A的条件熵。若A = Ø,则Ssig(a,A,D)= H(D|A) -H(D|{a})称为条件属性a和决策D的互信息,记为I(a;D)。I(a;D)的值越大,说明属性a对于决策D就越重要。

定义9设S = (U,C∪ D,V,f)是一个决策表系统,其中C = {a1,a2,…,am}为条件属性集合,D = {d}是决策属性集合。设I(ai;D)表示条件属性ai与决策属性D的互信息,则属性ai基于信息熵的权值为

综合式(8)和式(14),属性ai的客观权重为

式中,μ为一系数;ωi为根据大量历史数据和粗糙集方法为ai确定的客观权重。

在实际的线缆敷设过程中,专家的经验知识对于线缆敷设质量的优劣也起着非常重要的作 用。设专家的经验知识直接确定属性ai的权重为 δi,则ai的综合权重可表示为

其中,η1和η2为系数,且η1+η2=1。当η1>η2时, 说明决策者重视客观权重;当η1<η2时,说明决策者重视专家的经验知识。在确定综合权重时,可以根据实际情况设置相应的权重。

3.4基于属性综合权重的相似性度量方法

属性特征相似度是描述两个不同事例在同一特征属性上接近程度的一个量。设线缆敷设状态为up,uq∈U,两者在属性ai上的相似度[19]可以表示为

其中,vp、vq分别为对象up、uq在属性ai上的取值,而amax、amin分别为属性ai在其值域Va中的最大值和最小值。考虑两个事例在所有特征属性上的综合相似度,采用加权相似性度量方法表示两者之间的相似度为

式中,|B|为条件属性约简集中属性的个数。

4实例分析

下面以某相控阵雷达的线缆敷设为例来介绍变精度粗糙集方法在线缆敷设质量评 估中的应用。收集到22组线缆敷设质量的状态数据,对这22组数据按照表1和表2的量化方式对其中的数据进行量化,得到的质量评估决策表如表3所示。

为获取线缆敷设质量评估规则,基于VPRS的线缆敷设质量评估过程可以分为以下几个环 节:正确分类率β值的确定、近似约简集B的求解、条件属性综合权重计算以及属性特征相似性度量,具体的求解步骤如下。

4.1确定正确分类率β值

根据表3中论域U上的条件属性集C和决策属性集D,记

列出C和D各自在论域U上产生的划分,得到条件属性集和决策属性集分别为

根据式(2)可求得

根据式(6)可求得β(d1)= 0.67;同理可得 β(d2)=0.8,β(d3)=0.67。当取阈值为0.8时, 有β值划分的两区间(0.5,0.8]和(0.8,1],根据式(4)求得两区 间的近似 分类质量 分别为 γ(0.5,0.8](C,D)=0.86和γ(0.8,1](C,D)=0.18;当取阈值为0.67时,有β值划分的 两区间 (0.5, 0.67]和(0.67,1],同理可求得两区间的近似分类质量分别为γ(0.5,0.67](C,D)=1和γ(0.67,1](C, D)=0.18。

综合上述近似分类质量和β的确定原则,得 β=0.67。

4.2近似约简集B求解及决策规则获取

根据分类质量的性质求解近似约简集B,使得γ0.67(C,d)=γ0.67(B,d),且BC。求得质量评估决策表的核为{a5},即属性“线间耦合串扰程度”在所有条件属性中对线缆的敷设质量具有很大的影响,严重的串扰会使设备遭受干扰而导致性能下降或功能不正常,这与实际情况基本符合。 据统计,当设备或系统因电磁干扰而导致性能降级或功能不正常时,90% 的原因是出在连接设备或系统的电线电缆上,而在发生的各种类型电磁干扰中,有60% 是由导线间耦合产生的[20?21]。由于计算步骤较多,具体求解过程在此省略,求得的近似约简集B及其决策规则分别如表4和表5所示。

4.3条件属性综合权重计算

根据约简后的条件属性集B= {a1,a3,a5}对对象空间U进行划分,得

( 1 ) 求代数观下的客观权重 。 由于

有

其中,PposB(D)表示D的B正域,其余同理。从而有

所以由式(7)得

从而根据式(8)得代数观下各权重分别为

(2)求信息熵下的客观权重。由

根据式(9)~式(12)可得

从而求得

进而根据式(14)得信息熵下的客观权重分别为

再由式(15),取μ=0.7,得属性a1、a3、a5的综合客观权重分别为

(3)求综合权重。给出相对的主观权重:δ1= 0.2、δ3=0.4、δ5=0.4,设η1=0.4、η2=0.6,即在线缆敷设过程中看重专家经验,从而由式(16) 可求得a1、a3、a5的综合权重分别为

4.4敷设质量评估方法验证

为验证本文方法的决策效果,现有一组线缆敷设结果:{电磁兼容性差,分布电容强度中等,杂散电磁场强度较弱,线缆间绝缘强度>300MΩ,线间耦合串扰程度一般,线缆布设绑扎工艺良好, 线缆布设防护工艺良好,线缆空间布局一般}。经量化后设x23= {2,1,0,0,1,0,0,1},按照本文方法对其进行处理,并根据式 (17)和式 (18)计算x23与评估决策知识库中各对象的加权相似度,结果如下:

由上述加 权相似度 计算结果 可知,x23与x4~x8的相似度值最大,表明x23与x4~ x8最相似。但由表3知,决策有两个:Q1和Q2,即“线缆敷设质量较高→直接应用”和“线缆敷设质量一般→需要进行局部修改”。根据状态x23的各属性值可知应为决策Q2,即线缆敷设质量为一般,需要进行局部修改。

在整个求解过程中,综合考虑了代数观和信息熵下的权重计算以及专家经验。代数观下的属性权重考虑的是该属性对论域中确定分类子集的影响,而信息熵下的属性权重考虑的是该属性对于论域中不确定分类子集的影响,两者相结合得到的权重更加科学、合理,从而使得最终的决策结果更加符合实际情况。

5结语

雷达、卫星等复杂机电产品具有结构复杂、零部件多、内部空间紧凑等特点,设备内部结构和电磁环境对线缆敷设质量要求较高,线缆敷设质量的高低将直接影响产品的可靠性指标及维修性指标。本文提出的基于变精度粗糙集的线缆敷设质量评估方法,通过决策规则的获取及结合代数观和信息熵得到属性的综合权重,实现了线缆敷设状态的质量评估,为实际工程中线缆敷设工人提供了更好的决策依据。

摘要：针对目前线缆敷设主要依靠现场装配工人的经验从而使得敷设质量难以得到保证的问题,提出了一种基于属性加权相似度的线缆敷设质量评估变精度粗糙集决策方法。首先通过综合考虑评估对象的多种属性,建立线缆敷设质量评估模型并对属性值进行量化处理;其次,在质量评估模型的基础上,结合变精度粗糙集理论形成线缆敷设质量评估规则;最后,应用属性加权相似度方法比较当前线缆敷设状态与决策系统中所有对象的相似程度,得到敷设质量决策结果,完成对线缆敷设的质量评估。实例结果表明,相较于传统的敷设质量评估方法,该方法能提供更加符合实际的决策结果。

决策粗糙集 篇9

电力负荷预测是电力调度、用电、计划等管理部门的重要工作之一，其关系到整个电力系统的安全性和经济性[1]。随着电力系统的进一步市场化，如何更加精确地进行电力负荷预测是需要迫切解决的一个重要问题。许多学者对电力负荷预测的方法进行了大量研究，其大致可以分为以下4类：传统的时间序列法以及回归预测方法[2,3];以支持向量机为代表的空间预测方法[4];以神经网络为代表的人工智能预测方法;以模糊[5]、混沌[6]等为例的其余不确定预测方法。但越来越多的研究指出，电力负荷预测尤其是短期负荷预测受许多复杂因素影响(如气温、湿度、季节等)呈非线性关系[7]。因此，无论采取上述何种方法进行预测，如果不考虑这些非线性复杂因素的影响，均会导致负荷预测的精度难以进一步提高。

近几年，诸多学者在考虑复杂因素的影响下利用组合方法对电力负荷预测进行预测，其中越来越多倾向于利用数据挖掘技术和电力负荷模型相互结合[8,9]。由于数据挖掘可以利用统计、模式识别等技术从大量的数据中挖掘出有序的、分层次的、易于理解的知识，因此可以首先利用数据挖掘技术挖掘各种复杂因素对电力负荷数据的影响知识，并根据得到的影响知识对电力负荷预测进行建模，可以对负荷预测的精度取得突破性的提高。文献[4]利用数据挖掘技术和支持向量机(SVM)对短期负荷预测方法进行了研究，研究结果表明利用数据挖掘考虑气候因素后的SVM预测精度得到了进一步提高。文献[10]利用模糊粗糙集的属性约简能力首先对可能影响负荷预测的因素进行约简，然后再利用神经网络进行负荷预测，研究结果同样表明该方法可以满足所要求的精度，并避免了网络结构冗余的情况。以上研究都说明将数据挖掘技术引入到电力负荷预测中不但是可行的，而且可以提高预测精度。

神经网络是电力负荷预测中较常见的人工智能预测方法，其具有可考虑数据型影响因素，无需识别变化规律，可模拟任意非线性复杂映射，经学习训练得到最终模型的智能性优点。但利用神经网络进行电力负荷预测需要解决以下2个难点问题：采用何种神经网络结构对负荷进行预测以及如何剔出数据波动对神经网络训练的干扰。此外，神经网络难以考虑各类定性因素对负荷预测产生的影响，不适合知识环境复杂因素影响下负荷预测工作对预测精度和速度的要求。而这些问题恰是数据挖掘技术所解决的主要问题，因此，本文提出一种结合数据挖掘技术和神经网络的短期负荷预测新模型。该模型与上述研究的不同点在于：该模型不但可用聚类技术预先对历史负荷数据进行分类，避免数据波动对神经网络的干扰，而且进一步利用粗糙集属性约简能力进行定性因素的约简，并且利用决策树的规则提取技术自动确定与预测点同等类型的历史数据序列，形成神经网络的训练数据;此外，该模型还可以对定性因素进行处理，考虑定性因素对负荷预测点的影响。

1 负荷数据的预处理

由于电力具有社会属性，因此电力负荷预测将会受到大量复杂因素的多重干扰影响，如气象、社会经济情况、政治活动、价格等，而这些因素中一些十分重要的因素是用定性的、描述性的知识表达。例如对于短期负荷预测而言，有些具有重要影响的气象因素就属于定性的描述，如晴、阴、小雨等。以往的负荷预测方法难以考虑这些定性因素，因此大多是将其忽略掉，或者利用布尔矩阵进行量化计算。而利用数据挖掘技术则可以挖掘这些定性因素和历史负荷数据之间的影响关系，从而提高负荷预测的精度。为能利用数据挖掘技术，如粗糙集、决策树分类、聚类等，首先将其与历史负荷数据组成如图1所示的记录结构。

然后进行如下处理：

a.利用聚类技术对历史负荷数据进行聚类分析;

b.根据聚类结果对定性因素属性利用粗糙集进行属性约简;

c.对约简后的定性因素进行决策树分类分析，寻找定性因素和负荷数据之间的联系。

1.1 聚类分析

聚类分析的算法可以大致分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法5种。其中，以划分方法中的k-means方法最为经典。k-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(重心)来进行。

k-means算法过程如下[11]：首先从n个数据对象任意选择k个对象作为初始聚类中心，对于所剩其余对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后，再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)。不断重复这一过程直到标准测度函数开始收敛为止。一般采用均方差作为标准测度函数，如式(1)所示：

其中，E是数据库中所有对象的平方误差的总和;p是空间中的点，表示给定的数据对象;mi是簇Ci的平均值(p和mi都是多维的)。该准则可以使生成的结果簇尽可能地独立和紧凑。

对于电力负荷预测而言，将历史电力负荷准确分类是进一步精确预测电力负荷的一个重要因素[12]。因为分类可以避免由于电力负荷的类别不同而带来的数据扰动造成的神经网络预测训练精度缺失甚至神经网络预测不收敛等问题，此外，准确的分类也为进一步挖掘定性因素和历史负荷之间的关系奠定了良好的基础。

1.2 利用粗糙集进行属性约简

粗糙集理论将知识看作是关于论域的划分，认为知识是有粒度的，并引入代数学中的等价关系来讨论知识。该理论主要用于知识约简和知识相依性的分析，可以作为机器学习和复杂数据分析的工具。下面描述其基本理论[13,14]。

设U是感兴趣的对象组成的有限集合，论域R是定义在U上的一个等价关系。则U/R表示R在U上导出的划分，[x]R表示包含x的R的等价类，其中xU。在粗糙集理论中，将序对(U,R)称为一个近似空间。任何子集X属于U，称为一个概念。对每个概念X可定义下、上近似集如下：

其中，下近似集表示由U中那些在现有知识R下肯定属于概念X的元素组成的集合，上近似集是可能属于概念X的元素组成的集合。对于U上的2个等价关系P、Q,Q的P-正区域定义为

POSP(Q)是U中所有那些通过知识P被肯定地分作U/Q的类的元素组成的集合。

设U是一个论域，P和Q是定义在U上的2个等价关系簇。如果式(4)成立，则称一个等价关系RP是Q-不必要的(或多余的)，否则，R在P中是Q-必要的。

其中，IND(Q)=∩P(所有属于P的等价关系的交)也是一个等价关系，并且称为P上的一个不可区分关系。P中所有Q-必要的等价关系组成的集合，称为P的Q-核，记作CORDQ(P)。

基于上述理论可以得出，可以将粗糙集理论应用于电力负荷定性因素的约简，若记P和Q分别表示影响电力负荷预测的定性因素属性和电力负荷的类别决策属性，若存在一个属性RP是Q-不必要的，则从P中去掉属性R不会改变对电力负荷类别的决策影响，而去掉P中那些属于Q-核中的属性将改变信息系统的决策。因此，利用粗糙集理论先对影响电力负荷的定性因素进行约简处理，可以减少电力负荷预测的计算量，从而提高电力负荷预测的运算速度。

1.3 决策树算法

决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出以决策树形式表示的分类规则。在决策树学习算法的各种算法当中，属Quinlan于1979年提出的以信息熵的下降速度作为选取测试属性标准的ID3算法最有影响。下面描述其算法[15]。

设S是训练集，其中类别标识属性有m个独立的取值，即定义了m个类Ci(i=1，…，m),Ri为数据集S中属于Ci类的子集，用ri表示子集Ri中元组的数量。S的期望信息量可以用式(5)计算：

设属性A有v个不同的取值{a1,a2，…，av}，则通过属性A的取值可将S划分为v个子集，其中Sj表示在S中属性A的取值为aj的子集，j=1，…，v。如果用Sij表示Sj子集中属于Ci类元组的数量，则属性A对于分类Ci(i=1，…，m)的期望信息量为

将A作为决策分类属性的信息增益为

该算法需要计算每个决策属性的信息增益，具有最大信息增益的属性被选择为给定数据集S的决策属性节点，并通过该属性的每个取值建立由该节点引出的分枝。在建立由该节点引出分枝的数据子集中继续计算除去已计算的决策属性节点后的各分类属性的信息增益，以此类推，一直计算至最后一个属性进而生成决策树。

2 负荷预测方法

2.1 算法流程

综合上述理论，本文提出一种新的基于粗糙集和决策树的变结构神经网络短期负荷预测方法，下面描述其流程。

a.将相关数据组织成图1所示的数据记录，进行相关的数据预处理。

b.对数据记录中的历史负荷数据利用k-means算法进行分类。

c.根据分类结果对各条数据进行分类标识。

d.利用粗糙集理论对分类标识后数据记录中的定性因素部分属性约简，确定影响负荷的属性因素核集。

e.利用决策树算法对约简后的定性因素和分类标识进行决策树生成，生成一系列分类规则。

f.对于分类后的各类负荷分别进行神经网络的训练，下面是自适应神经网络的结构确定方式。

输入层：L(t-24i)和L(t-j)(i=1，…，p;j=1，…，q)，分别表示预测时刻前几天同一时刻的历史数据以及前几个小时的历史数据。此外，输入单元还包括约简后的定性因素。

输出层：仅含一个单元L(t)，即预测时刻的负荷值。

隐含层：由于根据Kromogol定理，仅含一个隐含层的神经网络模型就可以逼近任意一个非线性映射，因此，神经网络的隐含层仅选取一层。而隐含层的神经元输入采用逐步确认的方式，即首先选取2个神经元，然后根据神经网络的Kromogol定理和设计经验确定神经元的最高上限以某种步长逐步训练神经网络，然后比较训练后的误差、收敛情况和网络性能来确定最佳的隐含层神经网络个数。

g.利用待预测数据中的定性数据给待预测数据进行归类，选取相应的神经网络进行预测。

2.2 负荷预测实例及分析

基于上述算法流程，选取某市电力局1999年6月至2004年6月的月度24小时历史负荷数据为例进行讨论，综合其月度气象历史数据，如气压相关数据、气温相关数据、湿度相关数据、降水量、风速相关数据、日照时间等共19项属性相关数据(数据来自中国气象数据共享网http：∥cdc.cma.gov.cn)，共组织形成61条记录形式。然后对此61条记录形式进行数据预处理。对于记录中的定性属性，首先对文字型的属性值进行数字型标识转化，如将一、二、三、四季度分别转化成1、2、3、4予以标识，而对于数值型的属性值利用专家经验或等距离方法将其离散化，从而得到初始分析记录集。另将61条记录中的前60条记录作为训练集，而最后一条记录作为测试使用。

按照上文中提到的流程对该记录集中的历史数据利用Matlab软件工具箱中的k-means算法进行聚类分析可将负荷分为4类，其聚类结果见图2。

由图2可以看出，利用k-means算法进行聚类后，61条负荷记录按照24个点的数值特性进行了自动聚类，数值相对较近的点被归为一类。其聚类结果如表1所示。产生结果的原因是由于年负荷最低的月份一般出现在2月份，而最高的月份一般出现在夏季，并且负荷随年份的增加呈现上升趋势。

接下来将得到的聚类结果对记录数据进行标识，利用粗糙集理论对其定性因素进行属性约简，可以去除其中的13项因素，保留其中的6项因素，再对此6项因素利用ID3算法进行归类分析，根据此6项因素的负荷分类决策树规则供预测使用。

分别对4类数据开始进行训练，其中输入层选取L(t-24i)和L(t-j)(i=1,2,3;j=1,2)，神经网络采用BP神经网络，设置训练次数最高为1000次，精度为10-5进行预测，根据逐步实验测试，当4类神经网络隐含层中的神经元节点个数分别为11、10、11、11时精度最好。取测试集记录，对比决策树规则预先分析定性因素可将测试集记录分为第4类负荷，因此取第4类记录的负荷数据训练成的神经网络进行预测。另外，选取同结构未分类的神经网络以及自回归滑动平均模型ARMA(1,1)(其中系数由AIC定阶准则得到)同样对上述数据进行预测，从而进行对比分析。误差分析采用平均相对误差eMAPE作为比较的依据，见式(8)。

其所得结果见表2。表中，P0为实际负荷值;P1、P2、P3分别为本文方法、同结构BP法、ARMA(1,1)法给出的预测值。

从表中可以看出，本文提出方法得到的大部分预测值都比其他2种方法更精确。其平均误差值为2.16%，而同结构BP神经网络的平均误差为2.67%，根据ARMA(1,1)得到的预测平均误差为3.81%。

图3绘制出3种方法给出的预测值和实际负荷的曲线图，可以直观地看出，本文的方法具有更高的拟合精度。

3 结论

a.本文将数据挖掘的k-means、粗糙集、决策树分类技术与神经网络预测技术相结合，提出一种根据负荷曲线的聚类结果对其相应的定性因素和文本因素进行分析约简，形成决策分类树，生成相应的规则，然后利用自适应神经网络进行预测的方法。由于对定性因素和文本因素进行了分析约简，可以剔出由于定性因素和文本因素的干扰对数据造成的波动，因此在进一步的神经网络预测上提高了精度。

b.在对神经网络进行训练时，输入层输入的数据是经过筛选后的数据，而隐含层神经元的选择采取了根据训练集自动选择精度结果最小的神经网络，实现了一种自动变结构的神经网络，不需要人为的干预，从而进一步提高了精度，并且也提高了该方法的实用性。

摘要：利用数据挖掘中的聚类技术将历史负荷数据进行聚类,根据聚类后的分类信息对定性属性利用粗糙集进行属性约简,由约简结果进一步生成决策规则树供短期预测使用。根据聚类的结果对每类进行BP神经网络的训练,神经网络的隐含层单元采取逐步试用的方法根据训练误差最小化进行选择。在实际预测中,首先对待预测的记录利用决策规则树进行归类,然后选取相应类别的神经网络予以预测。通过实例证明,该方法的平均相对误差为2.16%,而同结构BP神经网络预测的平均相对误差为2.67%,ARMA预测的平均相对误差为3.81%,证明所提方法有效。

决策粗糙集 篇10

本文在经典粗糙集分类模型[1]的基础上利用Ziarko提出的变精度模型VPRS(Variable Precision Rough Set)[2,3],和贝叶斯粗糙集模型,引入近似区分矩阵和全局相对增益函数的概念,提出了一种基于变精度粗糙集的图像分类模型和另一种基于贝叶斯粗糙集图像分类模型,用两种方法进行图像资源的分类,既能大大简化分类规则,又能处理噪声数据及决策不协调的分类问题,且形成的规则集便于用户理解,实验结果表明在处理决策表不协调的图像分类问题,贝叶斯粗糙集方法性能良好,分类更加准确和高效。

1 变精度粗糙集理论和贝叶斯粗糙集理论

为了后续叙述的方便,首先介绍一些变精度粗糙集相关的基本概念[4]。

定义1:(正域)R⊆C,Q⊆D,Q相对于R的β正域定义为,

undefined

定义2:(β依赖性)R⊆C,Q⊆D,决策属性集Q与条件属性集R的β依赖性γ(R,Q,β)=pos(R,Q,β)/U

定义3:(近似约简)条件属性集R关于决策属性集Q的β约简或近似约简是R的一个子集red(R,Q,β),且满足:

(1)γ(R,Q,β)=γ(red(R,Q,β),Q,β)

(2)从red(R,Q,β)中去掉任何一个属性,都将使(1)不成立。

定义4:(核)核是知识表达系统S=(U,A,V,f)的所有约简的交集,

core(S)=∩red(S)

定义5:(近似区分矩阵)知识表达系统S=(U,A,V,f)的近似区分矩阵M(S)是个U×U的矩阵,每个矩阵元素定义如下:

M(xi,xj)={a∈Cf(xi,a)≠f(xj,a),

且ω(xi,xj)=1}

undefined

将上面定义与Pawlak粗糙集模型相比较,如果β=0,那么Pawlak粗糙集模型就变成了变精度粗糙集模型的特殊情况。

下面介绍贝叶斯粗糙集相关概念[5]。

局部增益g(X[x]E),与E(E为U上的等价关系)中的每个元素相关,具体表达式如下

g(X[x]E)=Pr(X[x]E)/Pr(X)-1

局部增益反映的是相对于先验概率Pr(X)的准确度的增加(减少)[6]。

定义6:信息系统S中,对于E⊆C,U/D={X1,X2,…,Xl},则称,

undefined

为E相对于决策属性D的全局相对增益函数。

定义7:设X和E为等价关系,a∈E,如果RE-{a}(X)=RE(X),称a为E中X不必要的,否则a为E中X必要的。E中所有X必要的集合称之为E的X核。

定义8:信息系统S中,对于∀X⊆U,子集B⊆C,则B为X的R约简且满足:

(1)RB(X)=RC(X)。

(2)去掉B中的任意一个属性都会使(1)不成立。

2 图像特征提取

本文对图像二维空间进行4×4的划分。若划分过细,会增加计算的复杂度,导致描述一般性的损失,不利于主色选取;若划分过粗,又会减小分类的准确率。针对图像中的每一分块,提取象素点数目最多的那种颜色作为分块的主色,这样就可以得到一个综合空间颜色特征向量。分块主色法通过统计每个固定分块的主色来突出颜色的空间关系,适合于主题位置固定的图像分类,对于主题位置变化较大的图像就会失效。

3 粗糙集分类模型

3.1 属性约简

属性约简的目的就是在保持分类能力不变的情况下,求得最佳约简,本文采用属性的出现频率与属性的长度作为启发因素,利用近似区分矩阵进行属性约简,算法1如下:

算法1(基于近似区分矩阵的属性约简算法)。

输入:知识表达系统S,条件属性集C,决策属性集D。

输出:知识表达系统S的最佳约简red(S)。

Step1:首先计算posC(D),如果posC(D)=U,取β=0,如果posC(D)≠U,取β∈(0,0.5),然后求pos(C,D,β)。

Step2:建立近似区分矩阵M(S),计算系统的核core,各属性的出现频率frequency(ai)与长度length(ai),cardM=card(M),其中card(M)表示近似区分矩阵中非空元素集合的个数,frequency(ai)表示属性ai在近似区分矩阵中出现的次数,length(ai)表示近似区分矩阵中包含属性ai的含属性个数最少的集合的元素个数。

Step3:red=core,F=c-core。

Step4:M=M-{m},其中m是指近似区分矩阵中所有包含最佳约简中属性的元素,重新计算各属性的出现频率frequency(ai)与长度length(ai)。

Step5:如果M=Φ则停止;否则,继续下一步。

Step6:剩余属性集F中挑选出现频率最高的属性f加入到最佳约简中去,如果有两个或两个以上的属性的出现频率相同,则选择长度最短的属性,

red=red+{f},F=F-{f}

Step7:回到Step4循环。

以全局增益作为启发式信息,给出贝叶斯粗糙集属性约简的启发式算法。

算法2 (基于全局增益的贝叶斯粗糙集属性约简算法)。

输入:信息系统S=(U,C∪D,V,f)。

输出:贝叶斯粗糙集的一个R约简。

Step1:求出条件属性的核属性集合re,并计算RC(D)。

Step2:计算Rre(D),如果Rre(D)=RC(D)成立,则转到Step4,否则令,C=C-re对于∀Ci∈C,求得RCi(D)的值,构成集合M。

Step3:将集合M中的元素从小到大排列,并将其最大值添加到re中,即re=re∪Ci,M=M-RCi返回至Step2。

Step4:对re中条件属性进行冗余删除,参见文献[7],最后所得的就是贝叶斯粗糙集的一个R约简。

3.2 决策规则约简

决策规则的约简是利用决策逻辑分别消去决策算法中每一个决策规则的不必要条件,它不是整体上的简化属性,而是针对每一个决策规则,去掉该规则的冗余属性值,进一步简化决策算法。

本文在决策规则的约简过程中,对每一条决策规则,从第一个属性开始,依次去掉每一个属性,并且检查该属性去掉后决策表是否协调,如果决策表协调则该属性可以去掉,否则该属性予以保留,重复此过程,可以达到对每条决策规则进行约简的目的。

3.3 样品类别预测

由约简生成的所有决策规则构建分类模型,它用于类别预测时,将先计算被测对象与各决策规则的匹配度。所谓匹配度,是指两者中取值相同的属性的个数与规则内条件的属性总数的比值。然后决策类别相同的规则的匹配度相加,除以此类别规则的个数,由值最大的那类规则判定样本类别。

4 实验与结论

本文采用的图像数据来自WEBIIS Database[8],总共有10000个图像。在实验中取其中六类图像,每两类为一组,进行分类实验。下面以其中两类为例给予介绍:一类为蝴蝶图,另一类为海边风景图,每类各100个,从每类各取50个图像,作为训练样本,产生分类规则,对其余的图像进行分类。实验结果见表1。

β=0,β=0.1,β=0.2的准确率一样,等于经典粗糙集的准确率,β=0.3,β=0.4的准确率一样。

可以看出变精度粗糙集的属性约简与贝叶斯粗糙集属性约简的联系与区别。联系:贝叶斯粗糙集的属性约简是变精度粗糙集在不同的参数β的条件下所获得的属性约简的一种情况。区别:变精度粗糙集属性约简当参数β的取值不同时,会得到不同的属性约简。因此,贝叶斯粗糙集相对于变精度粗糙集而言放松了对参数的要求。可见,贝叶斯粗糙集具有一定的实际应用价值。

摘要：在经典粗糙集分类模型的基础上利用变精度粗糙集模型,引入近似区分矩阵的概念,提出了一种基于变精度粗糙集的图像分类模型及其分类算法,在变精度粗糙集分类模型的基础上利用贝叶斯粗糙集模型,通过引入全局相对增益函数给出了贝叶斯粗糙集属性约简的另外一种算法,最后提出了一种基于贝叶斯粗糙集的图像分类模型及其分类算法。实验结果表明在处理决策表不协调的图像分类问题,贝叶斯粗糙集图像分类方法性能良好,分类准确和高效。

关键词：变精度粗糙集,近似区分矩阵,贝叶斯粗糙集,全局相对增益,图像分类

参考文献

[1]赵凯,李春平.一种基于粗糙集的图像分类方法[J].微计算机应用,2007,28(5):449-453.

[2]Pawlak Z.Rough Sets[J].International Journal of Computer and Infor-mation Science,1982,11(5):341-356.

[3]Bao Yong-guang,Aoyama Satoshi,Yamada Kazutaka,et al.A RoughSet-Based Hybrid Method to Text Cate-gorization[J].IEEE Proceedingsof Second Intemational Conference on Web Information Systems Engi-neering,2001,1:254-261.

[4]张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].北京:科学出版社,2001.

[5]Slezak D,Ziarko W.Bayesian rough set model[J]//Proc of the Int.workshop on foundation of Data Mining(FDM’2002),December 9,Maebashi,Japan,2002:131-135.

[6]Han Jianwei.Data mining concepts and techniques[M].北京:机械工业出版社,2001:30-50.

[7]黄兵,周献中,胡作进.不完备信息系统中一个变精度粗糙集模型[J].中北大学学报:自然科学版,2006,27(4):283-287.

决策粗糙集 篇11

关键词:粗糙集 变精度粗糙集 离散化

DOI:10.3969/j.issn.1672-8289.2010.10.089

1 引言

变精度粗糙集(variable precision rough set ,VPRS)模型[1]是W.Ziarko教授在基本粗糙集理论的基础上针对其容噪能力差的缺陷而引入误差因子而得到的,引入因子的目的在于将精确的二元等价关系推广为一般的二元关系。本文将VPRS应用到连续属性的离散化[2]当中,以增强其泛化能力。

2 变精度粗糙集理论的基本概念

粗糙集(rough set,RS)理论的中心问题是分类分析。Pawlak粗糙集模型[3]的一个局限性是它所处理的分类必须是完全正确的或肯定的,因为它是严格按照等价类来分类的,亦即“包含”或“不包含”,而没有某种程度上的“包含”或“属于”。Pawlak粗糙集模型的另一个局限性是从模型中得到的结论仅仅适用于这些对象集,但在实际应用中,往往需要将一些从小规模的对象集中得到的结论应用到大规模的对象集中去。为此,W.ziarko提出了一种变精度粗糙集(VPRS)模型,该模型给出了错误率低于预先给定值的分类策略.

设X和Y表示有限论域U的非空子集,如果对于每一个

有,则Y称包含X,记做,令

其中 表示X集合的基数,称c(X,Y)为集合X关于集合Y的相对错误分类率。即如果我们将集合X中的元素分到集合Y中,则做出分类错误的比例c(X,Y)为*100%,真正错分类的元素数目为c(X,Y) .称其为绝对分类误差。令,“多数”包含关系定义为。“多数”即X与Y中的公共元素的数目大于X中元素数目的50%。显然,当且仅当c(X,Y)=0。对于任意X,关系恒成立,其中,

可以看出,X的 正域可以理解为将U中的对象以不大于 的分类误差分类于X的集合;X的负域 可以相应的理解为将U中的对象以不大于 的分类误差分类于X的补集~X;X的 边界区域是由那些以不大于 的分类误差既不能分类于X又不能分类于以~X的对象组成的集合,如果 ,则 . 3 基于变精度粗糙集的连续属性离散化方法

设给定训练数据集 ,共有n条记录,设属性A为连续属性。首先将连续值排序,设定误差因子 , 的值。起始数值从第O个记录开始,设此记录所属类别为 ,

,计算(第O个记录不计)把各记录归入的误分类,

比较得出最小的 将其对应的

属性A的最大取值作为划分点,否则不把任何数据归入正域中。从前一个划分点的下一个值开始,重复上述过程,找到所有划分点。

假设划分点数为 ,然后根据属性A的可能取值范围,以及各划分点对应的划分区间的宽度计算正域误分类度

。当或此离散区间对应的结果属性与前一个离散区间(若是第一个离散值则没有此过程)对应的结果属性值相同时,合并这两个离散区间,扩大正域。

如果连续取值属性A的某一取值 在用m(m为有限常数)条数据中出现时,统计这m条数据的不同结果属性的个数,个数最多的结果属性 作为这m条数据的结果属性,统一计算 。如果m条数据的不同结果属性取值对应的记录个数相同,则不计算。

在离散化过程中,当误差因子很小时,连续取值属性可能被离散成很多区间,即与数据过度匹配,这将导致生成的决策树的泛化能力降低。为此,在上述离散化过程中,首先通过Binning(基于等频)(即数据个数)方法计算将数据归入正域的误分类度,得到离散划分结果;然后再通过Binning(基于等宽)[4](训练数据或划分区间取值范围)方法计算误分类度,并修正离散结果。

4 实验过程与结果

(1)原始数据:选用iris数据库中的第一条属性sepal length作为研究对象。

(2)用Binning预离散化:利用等宽的方法将论域中的元素分割成小的单元(集合),令k=12,结果如下

Equal-Width

每个Bin中属于相应类别的元素数量

(3)使用基本RS模型二次离散化:根据上表可知”4.6,4.9,5.2”构成集合正域;”5.8,6.1”构成的正域; “5.5”为Y1 Y2、的边界域。

(4)使用VPRS模型二次离散化:引入了误差因子 使下列关系成立:

如果误差因子 =0.4,则 “5.5”以不大于误差因子 的分类误差分别分类于iris-versrcolor 。

由此可见应用了VPRs模型后算法的分类能力得到了提高,可以将一些因含有噪声而被划到边界域的数据重新划入正域。

参考文献:

[1] W Ziarko . Variable precision rough set model[J]. Journal of Computer and System Science , 1993 , 46(1):39-59.

[2] 张政超,周宪英,关欣.一种连续属性离散化的新方法[J].火力与指挥控制,2010,35(7):20-22.

[3] Pawlak Z. rough set: theoretical aspects of reasoning about data[M].Dordrecht: Kluwer Academic Publishers,1991.

[4] 何亚群,胡寿松。粗糙集中连续属性离散化的一种新方法[J].南京航空航天大学学报,2003,35(3):213-215.

基于矩阵初等变换的粗糙集 篇12

粗糙集[1]是一种处理不精确和不确定性知识的数学工具。其主要思想是在保持分类能力不变的前提下, 通过属性约简, 导出问题的决策和分类规则。近年来, 粗糙集在机器学习、知识发现、数据挖掘、过程控制、模式识别以及决策支持与分析等领域被广泛应用, 并取得了很大的成功[2,3], 其计算已引起许多学者的高度关注。

文献[4,5]用矩阵的方法定义粗糙集的上近似, 再用对偶关系计算下近似, 提出了一种通过矩阵乘法来计算粗糙集的途径。文献[6,7]引入关系矩阵和布尔列向量重量上乘法和下乘法的概念, 证明了上乘法就是上近似, 下乘法就是下近似。但这些方法较为抽象且计算上下近似的复杂度高。本论述定义了增广矩阵及其初等变换的概念, 给出了通过判断初等变换矩阵列元素的特征来计算上下近似的一种直观、简便、快速的算法, 该算法的复杂度远远低于上述文献中的算法复杂度。

2 增广矩阵及其初等变换

定义1设论域U={u1, u2, …, un}, R为U上的等价关系, 则R产生U的一个划分, 其划分类为U/R={E1, E2, …, Em}。由集合特征函数的定义可知, 每个Ei对应唯一的一个n维布尔列向量 = (e1i, e2i, …, eni) T, 其中分量eji=1或0, 若uj∈Ej, 则eji为1, 否则为0。因此从U的划分R可诱导出矩阵Enxm= ( :

称Enxm为U中R对应的划分矩阵。

对于任意的X哿U, X也对应唯一的一个n维布尔列向量 = (x1, x2, …, xn) T, 其中xj=1或0, 若uj∈X, 则xj为1, 否则为0。若把X对应的向量添写在划分矩阵Enxm的右边, 便得到n× (m+1) 矩阵 = (E|X) = :

称 为X在近似空间 (U, R) 中的增广矩阵。

例1设U={a, b, c, d, e}, X={a, c, d}, R为U上的等价关系, 对应的划分类为:E1={a, c}, E2={b, d}, E3={e}, 则R对应的划分矩阵和X对应的增广矩阵分别为:

定义2设 为X在近似空间 (U, R) 中的增广矩阵, 将其最后一列各元素的-1倍分别加到前m列对应元素的过程称为 的初等变换, 且规定-1+1=®。 (-1) 表示将向量各元素的-1倍加到向量 的对应元素上。经过初等变换后得到的同型矩阵称为 的初等变换矩阵, 记为。

例2上例中增广矩阵E軍X的初等变换过程及其初等变换矩阵为:

注:实际上, 近似空间中集合对应的增广矩阵的初等变换本质上是一般矩阵理论中的第三种初等列变换:将某列各元素的-1倍加到另外一列对应元素上, 只不过对-1+1=0的运算结果0记为®, 而其它运算不变。

3 基于初等变换的粗糙集模型

设 (U, R) 为近似空间, X⊆U, 定义两个子集:

分别称它们为X的R下近似和R上近似。

定理设 (U, R) 为近似空间, X⊆U, 为X的增广矩阵, 的初等变换矩阵, 则有:

(1) 中所有不含元素1的列对应的划分类的并是的下近似

(2) 的所有含元素®的列对应的划分类的并是X的上近似。 。

证明: (1) 设x∈RX, 则[x]R⊆X。设[x]R对应的列向量为EX的第i列, 将X对应的列向量各元素的-1倍加到第列上, 由[x]R⊆X知第i列是1的元素变为®, 是0的元素变为-1或不变, 从而不含元素1。反过来, 若的第i列不含元素1, 由上述变换可知, 第i列对应的划分类[x]R是X的子集, 从而x∈RX。

(2) 设x∈ , 则[x]R∩X≠覫。设[x]R对应的列向量为EX的第i列, 将X对应的列向量各元素的-1倍加到第i列上, 由[x]R∩X≠Ø知第i列至少有一个元素为-1+1=®。反过来, 若的第i列有元素®, 由初等变换的定义可知, 第i列对应的划分类[x]R与X相交非空, 从而x∈RX。

推论设 (U, R) 为近似空间, X, Y⊆U, 分别为X, Y对应的列向量, 则有:

(1) X哿U当且仅当向量 (-1) 的任一分量不等于1。

(2) X∩Y≠Ø当且仅当向量 (-1) 至少有一个分量为®。

例3在上例中, 第1列不含元素1, 第1列和第2列含元素®, 所以根据上述定理可知X的上下近似分别为:

在以上讨论的基础上, 得到了一种计算粗糙集上下近似的极为简单、高效的算法, 归纳如下:

第1步写出X在近似空间 (U, R) 中的增广矩阵E= (E|X) ;

第2步对 进行初等变换, 求出的初等变换矩阵; ;

第3步判断 的前m列是否含元素1和®, 则不含元素1的列对应的划分类的并是X的下近似RX, 含元素®的列对应的划分类的并是的上近似 。

例4设U={1, 2, 3, 4, 5, 6, 7, 8}, R为U上的等价关系, 对应的划分类为:

令X={1, 3, 4, 6}, 则X的上下近似可从增广矩阵的一步初等变换即得。

由初等变换矩阵 看出, 第1、3列不含元素1, 第1、3、4列含元素®, 故:

4 结束语

在近似空间中引入增广矩阵及其初等变换, 不仅为集合上下近似的计算提供了简便快速的算法, 而且为粗糙集的研究提供了一种新途径。实际上, 从初等变换的过程明确看出, 增广矩阵初等变换的关键是运算-1+1=®, 变换后重点考虑®的个数, 若某列变换后®的个数等于变换前1的个数, 则该列对应的划分类为集合X的子集, 若某列变换后®的个数不为零, 则该列对应的划分类与集合X相交非空, 并由此求出X的上下近似。

本论述只对经典粗糙集模型进行了讨论, 关于覆盖粗糙集模型的情况将另文介绍。

参考文献

[1]PAWLAK Z.Rough Sets[J.]International Journal of Information and Computer Science, 1982, 11, (5) :314-356.

[2]Ziarko W.Introduction to Special Issue on Rough Sets and Knowledge Discovery[J.]International Journal of Computa-tional Intelligence, 1995, 11, (2) 223-226.

[3]张文修, 吴伟志.粗糙集理论介绍和研究综述[J.]模糊系统与数学, 2000, 14, (4) :1-12.

[4]刘贵龙.模糊近似空间上的粗糙模糊集[J.]模糊系统与数学, 2002, 16:75-78.

[5]雷晓蔚.粗集理论的矩阵方法[J.]计算机工程与应用, 2006, 42, (17) :73-75.

[6]杨勇.粗糙集的矩阵定义[J.]计算机工程与应用, 2007, 43, (14) :1-2, 7.