序Vague 信息系统属性约简算法研究

张倩倩　徐天贺

摘要：重点成为常研究对象属性值为Vague概念的Vague信息系统，通过定义Vague值间的序关系，建立基于优势关系的序Vague 信息系统。借助于优势粒度熵来计算每个属性的重要性，进而提出一种基于优势粒度熵的序Vague信息系统属性约简算法，最后的实例验证了该算法的有效性。

关键词： 序Vague信息系统，优势粒度熵，属性约简

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）13-0261-02

Abstract： It researches vague information system that the object attribute value is vague concept. In this paper， the ordered relationship is defined. The ordered vague information system based on dominance relation has been introduced. The importance of each attribute is computed by defined dominance granularity entropy. Then an algorithm for attribute reduction from ordered vague information system based on dominance granularity entropy. The example proves the validity for the algorithm.

Key words： ordered Vague information system， Dominance granularity entropy， Attribute Reduction

粗糙集理论[1]是一种处理模糊和不确定知识的数学工具[2]，属性约简与规则提取是粗糙集理论研究的核心内容之一，目前已有很多学者对知识约简做了深入的研究，并取得了大量成果[3-4]。在粗糙集理论中，其所研究的信息系统的属性值是确定的，然而在实际应用中，我们有时候很难去获得一个属性的精确值，为此不少学者研究了复杂信息表的决策规则获取与属性约简方法[5-8]。目前以Vague集表示的数据分析手段还很少，Vague集是在模糊集基础上发展起来的一种更加符合人类思维的新型理论，对于数据本身未知性、不确定性的描述十分有效。文献[9]研究了Vague决策表的知识获取，其主要思想是通过定义Vague值之间的序关系，将Vague决策表转化为二元决策表，进而利用粗糙集理论对Vague决策表进行属性约简与规则提取。本文重新定义了一种更合理的序关系，并通过建立优势关系[11-13]对序Vague信息系统的属性约简进行了探讨，并给出了优势关系下序Vague信息系统的属性约简算法。

1 Vague集理论

定义1[14] 设论域U={x1， x2，[…]， xn}，其中元素xi （i=1， 2，[…]， n）是所讨论的对象。U上一Vague集A由真隶属度函数tA和假隶属度函数fA所描述： tA：U→[0，1]， fA：U→[0，1]。其中tA（xi）是由支持xi的证据所导出的肯定隶属度的下界，fA（xi） 则是由反对xi的证据所导出的否定隶属度的下界，且tA（xi）+fA（xi） ≤ 1。元素xi在Vague集A中的隶属度被区间[0，1]的一个子区间[tA（xi），1- fA（xi）]所界定，称该区间为xi在A中的Vague值。

定义2 设四元组[S′]=（U ， A ，[V′]，[f′]）是一个Vague信息系统，其中，U表示对象的非空有限集合，A表示属性概念集，[V′]=∪{[V′a] | a∈A}， [V′a]为属性a的Vague值域；[f′]：U×A→[V′]是一个信息函数，它将每个对象对应属性的Vague概念映射成Vague隶属度，即[?]a∈A，x∈U，有[f′]（x ， a）∈[V′a]。

2 序Vague信息系统

下面我们给出一种两个Vague对象值之间的序关系。

定义3 对于两个Vague值x=[tx ， 1-fx]，y=[ty ， 1-fy]，tx、ty∈[0 ， 1]，若tx≥ty 且fx≤fy，则表示针对对象x的评价至少和对象y一样好，或称Vague值x优于Vague值y，记作：x[?_]y。

如果在Vague信息系统中，对象之间具有满足定义3的序关系，此时，可以把Vague信息系统看作有序Vague信息系统。

定义4 在序Vague信息系统[S′]=（U ， A ，[V′]，[f′]）中，对于B[?]A，定义[R≥B]={（xi， xj）：[f′]（xi，a）[?_][f′]（xj，a），[?]a∈B}为属性集上的优势关系，则[[xi]≥B]={xj：（xi， xj）∈[R≥B]}为序Vague信息系统属性集上的优势类。

如果将优势关系看成是一种信息粒度，则[[xi]≥B]也可以看做是优势关系上的优势粒。

对于任意X[?]U，定义X关于优势关系[R≥B]的下近似和上近似分别定义为：

[R≥B_]（X） = {xi∈U：[[xi]≥B][?]X}，[R≥B]（X） = {xi∈U：[[xi]≥B]∩X≠Φ}。

定义5 设[S′]=（U ， A ）是一个序Vague信息系统，[R≥A]是U上的优势关系，U/[R≥A]={[[x1]≥A]， [[x2]≥A]， …， [[xn]≥A]}，知识[R≥A]的优势粒度熵GE（[R≥A]）定义为：

GE（[R≥A]）=[1Ui=1n1[xi]≥A]，其中，|·|表示集合的基数。

定理1设[S′]=（U ， A ，[V′]，[f′]）是一个序Vague信息系统，R≥是论域U上的优势关系，P、Q[?]A且P[?]Q，则有GE（[R≥P]）≤GE（[R≥Q]）。

证明：根据定义6有GE（[R≥P]）=[1Ui=1n1[xi]≥P]，GE（[R≥Q]）=[1Ui=1n1[xi]≥Q]，GE（[R≥Q]）-GE（[R≥P]） =[1U（i=1n1[xi]≥Q-i=1n1[xi]≥P）] ，由基于优势关系的序Vague信息系统的性质（3）可知，当P[?]Q时，有[[xi]≥Q][?][[xi]≥P]，因此|[[xi]≥Q]| ≤ |[[xi]≥P]|，有[1[xi]≥Q]| ≥ [1[xi]≥P]，则GE（[R≥Q]）≥ GE（[R≥P]），故有GE（[R≥P]） ≤ GE（[R≥Q]）成立。

定义6设[S′]=（U， A ）是一个序Vague信息系统，属性a∈A在A中的重要度定义为：

Sig（a， A） = GE（[R≥A]）-GE（[R≥A-{a}]）。

性质1 属性a∈A在A中是必要的当且仅当Sig（a， A） >0。

性质2 Core（A）={ a∈A| Sig（a， A） >0}。

定理2 设[S′]=（U ， A ）是一个序Vague信息系统，B[?]A，则B是A的一个约简的充分必要条件是：（1） GE（[R≥B]） = GE（[R≥A]），（2）对[?]b∈B都有Sig（b， B） > 0。

3 序Vague信息系统属性约简算法

根据上面的理论设计一种针对序Vague信息系统进行属性约简的算法，在该算法中依次计算各个属性的重要性，从中去掉对序Vague信息系统不重要的属性，最后得到属性集的一个约简。

算法1 基于优势粒度熵的序Vague信息系统属性约简算法

输入：序Vague信息系统[S′]=（U， A，[V′]，[f′]），U={x1， x2，[…]， xn}，A={a1， a2，…， am}

输出：属性A的一个约简B

Step1：计算U/[R≥A]={[[x1]≥A]，[[x2]≥A]，…，[[xn]≥A]}、 GE（[R≥A]）及U/[R≥（A-{aj}）]= {[[x1]≥（A-{aj}）]， [[x2]≥（A-{aj}）]，…，[[xn]≥（A-{aj}）]} （j=1， 2， …， m）和GE（[R≥A-{aj}]）。

Step2：令B1 = A = {a1， a2， …，an}，Att = ?。

Step3：如果B1 – Att = ?，则B = B1，转Step6；否则任选B1 - Att中的一个属性ai，计算Sig（ai， A）。

Step4：若Sig（ai， A） = 0，则B1 = B1 –{ai}，转Step4。

Step5：若Sig（ai， A） > 0，则Att = Att ∪{ai}，转Step4。

Step6：Att 为属性集A的一个约简B，输出B，算法结束。

4 实例分析

表1给出了一个序Vague信息表，其中U={x1，…， x6}为对象集， C={a， b， c， d}为属性集。

利用算法1对表1进行约简的步骤如下：

5 结束语

目前使用粗糙集的方法在Vague信息表上的推广还处于研究阶段，由于实际应用中取值的不确定性，本文研究了Vague信息系统的属性约简。文中首先探讨了Vague集的含义，进而寻求一种更合理的Vague值之间的序关系，定义了序Vague决策系统的优势关系，通过定义优势粒度熵来计算每个属性在该信息系统中的重要性，约简掉属性重要性为0的属性，从而达到简化信息系统的目的。

参考文献：

[1] Pawlak Z. Rough Sets. Theoretical Aspects of Reasoning about Data. Dordrecht， Netherlands： Kluwer Academic Publishers， 1991.

[2] Leung Y， Fischer M， Wu weizhi， et al. A Rough Set Approach for the Discovery of Classification Rules in Interval-valued Information Systems[J]. International Jounal of Approximate Reasoning， 2008， 47（2）：233-246.

[3] 孙士保， 秦克云. 基于包含度的决策表属性约简算法的研究[J].计算机工程与应用， 2006（3）：19-21.

[4] 孙林， 徐久成， 马媛媛.基于包含度的不一致决策表约简新方法[J].计算机工程与应用， 2007，43（24）：166-168，211.

[5] 陈子春，刘鹏惠，秦克云.区间值信息系统上决策规则的获取与优化[J]. 数学的实践与认识，2011，41（19）：89-96.

[6] 梁春华，曲开社，张海云. 区间值信息系统的启发式属性约简[J]. 计算机工程，2012，38（12）：139-142.

[7] 杨成福， 舒兰. 基于可辨识矩阵的模糊目标系统决策约简算法[J].数学的实践与认识，2009，39（5）：103-107.

[8] 张楠，苗夺谦，岳晓冬. 区间值信息系统的知识约简[J].计算机研究与发展，2010，47（8）：1362-1371

[9] 江莉， 刘三阳， 王珏， 等.Vague决策表的知识获取[J].计算机科学， 2004， 31（2）：111-112.

[10] Shao M W， Zhang W X. Dominance Relation and Rules in an Incomplete Ordered Information System. International Journal of Intelligent Systems， 2005（20）：13-17.

[11] 陈娟， 王国胤， 胡军.优势关系下不协调信息系统的正域约简[J]， 计算机科学， 2008， 35 （3）：216-218，227.

[12] 徐久成，史进玲，张倩倩.基于粒计算的序决策规则提取算法[J]，模式识别与人工智能，2009， 22（4）：660-665.

[13] 徐伟华，张文修.基于优势关系下不协调目标信息系统的分布约简[J].模糊系统与数学， 2007，21（4）：124-131.

[14] Gau W L， Buehrer D J. Vague sets[J]. IEEE Trans Syst Man Vybern， 1993， 23（2）： 610-614.