基于优势关系的正协调模糊决策形式背景的规则融合

张晓鹤,陈德刚,米据生

(华北电力大学 1.控制与计算机工程学院;2.数理学院,北京 102200;河北师范大学 3.数学科学学院;4.河北省计算数学与应用重点实验室,河北 石家庄 050024)

知识表示的重要方式之一就是规则,通常包含两部分内容,即条件与结论。条件是结论产生的必要条件,所以规则能够帮助完成对象分类、获取决策等任务。规则挖掘的一个重要工具就是形式概念分析理论。形式概念分析[1]于1982年由Wille教授提出,Ganter等[2]在其专著中进一步总结了形式概念分析相关知识。形式概念分析理论将对象与属性的内在联系用数学语言进行描述,进而获取规则。该理论已在信息检索[3-6]、故障诊断[7]、数据挖掘[8-9]、气象分析[10]等领域得到了广泛应用。

概念格的节点之间可以进行相互推理,在此基础上能够实现规则提取,它被认为是概念内涵之间的一种诱导关系[11-12]。在形式概念分析中,更为一般的规则通过蕴涵刻画属性之间的依赖关系。目前,已经有诸多学者针对形式背景中决策规则获取进行研究,形成了完整的理论体系[13]。Ishibuchi等[14]提出了一种从数值数据中生成模糊规则的算法,并利用产生的模糊规则进行模糊推理。於东军等[15]利用SOM对原始样本进行学习,再使用Wang-Mendel方法从SOM的原型向量中提取规则。王丽娟等[16]将多粒度理论与不完备决策系统结合,提出多粒度近似分布约简与规则获取方法。Kuznetsov[17]通过分析属性集之间的隐含关系提出了一种概念构造算法从而生成所有可能的基于概念的分类规则,也称假设。Wu等[18]将粒计算与概念格理论进行结合,提出了粒概念与粒决策规则。为了获取更为简便的决策规则,基于决策规则的约简模型被陆续提出,Shao等[19]给出了在形式背景中“if-then”规则的获取方法,并提出了保持最大规则不变的属性约简方法,且进一步在模糊形式背景中提出了一种基于可变阈值概念格的知识约简方法[20]。Li等[21]提出了在保持由全体对象集构造的决策规则不变的决策形式背景的约简方法。Li等[22]提出了保持最大规则的决策形式背景中的两种新型约简方法。Yang等[23]基于蕴涵映射,研究了实数集决策形式背景中的属性约简与规则获取。林艺东等[24]提出了基于矩阵的模糊-经典概念格属性约简。Ren等进一步研究了三支概念格的属性约简[25]与规则提取[26]。Zhang等[27]在具有模糊决策的格值信息系统上给出了复杂系统中所有对象的排序方法并讨论了近似约简和规则获取问题。张文修等[28]提出了协调近似表示空间的规则融合方法。为进一步提升规则提取效率,王志海等[29]利用增量式建格实现规则动态提取。谢志鹏等[30]借助概念格与内涵缩减技术挖掘关联规则。梁吉业等[31]给出闭项集概念,只提取核心规则,基于规则推理诱导形成剩余规则。

目前研究的决策形式背景中的决策规则大部分是基于条件概念外延与决策概念外延之间的包含关系给出,而这些决策规则不能够解决条件属性所有可能取值的决策问题。本文首先基于优势关系获取决策类,然后基于确定性的粒决策规则获取各个决策类对应的条件属性最小取值,给出规则融合方法,通过该方法可以获取全部条件属性取值对应的决策规则。

1 预备知识

首先对形式背景中的相关知识进行简单介绍。

定义4[28]设Vl(l≤m) 是非空有限集,记P={(u1,u2,…,um):ul⊂Vl(l≤m)},称P为集合向量空间。对于P中的两个集合向量E=(u1,u2,…,um),S=(v1,v2,…,vm),若l≤m,均有ul⊆vl,记E≤S,则(P,≤)为偏序集。且有

E∧S=(u1,u2,…,um)∧(v1,v2,…,vm)=

(u1∧v1,u2∧v2,…,um∧vm)

2 基于优势关系的模糊决策形式背景的协调性

本节给出模糊决策形式背景中3种不同协调性的定义,并对其关系进行讨论。

从而获得U上的一个覆盖并按决策值排序有

U/RD={RD(x):x∈U}={D1,D2,…,Dr}

式中:RD(x)={y∈U:(x,y)∈RD}。

定理2正协调的模糊决策形式背景必为序协调的。

从定理1可知,正协调的模糊决策形式背景同样也是粒协调的。

例1表1给出了一个模糊决策形式背景,其中对象集U={x1,x2,x3,x4,x5},D={d}为决策属性集。A={a1,a2,a3}为条件属性集。

表1 模糊决策形式背景

计算可知:

根据RD={(x,y)∈U×U:d(x)≤d(y)}可产生U上的覆盖。

D1={x1,x2,x3,x4,x5},D2={x1,x2,x3,x4},D3={x2}。

而

f(x1)=(0.7,0.7,0.8)

f(x2)=(0.9,0.8,0.9)

f(x3)=(0.7,0.7,0.8)

f(x4)=(0.7,0.8,0.9)

f(x5)=(0.6,0.7,0.8)

f(x5)≤f(x1)=f(x3)≤f(x4)≤f(x2)

d(x5)≤d(x1)=d(x3)≤d(x4)≤d(x2)

则F1是一个正协调模糊决策形式背景。

仅有f(x1)=f(x3),此时d(x1)=d(x3),则F1是一个序协调模糊决策形式背景。

继续计算可知

gf(x1)={x1,x2,x3,x4}⊆RD(x1)=D2

gf(x2)={x2}⊆RD(x2)=D3

gf(x3)={x1,x2,x3}⊆RD(x3)=D2

gf(x4)={x2,x4}⊆RD(x4)=D2

gf(x5)={x1,x2,x3,x4,x5}⊆RD(x5)=D1

所以F1是一个粒协调模糊决策形式背景。

3 基于优势关系的正协调模糊决策形式背景上的规则融合

本节给出正协调决策形式背景中粒决策规则获取算法,进一步讨论基于优势关系的正协调决策形式背景上规则融合算法,并给出相关实例。

3.1 粒决策规则获取

算法1给出了具体算法。

算法1正协调模糊决策形式背景的粒决策规则获取算法

2: 1≤l≤|D|

3: 如果dl(x)≤dl(y)

4:(x,y)∈RD

5:U/RD={RD(x):x∈U}={D1,D2,…,Dr}

6: 计算(Dt,Tt)

7: 对1≤k≤|U|

8: 计算(gf(xk),f(xk))⟹(RD(xk),Tt)

该算法最坏复杂度为O(|U|(|U||D|+|U|r+|A|r))。

3.2 规则融合

对于正协调模糊决策形式背景来说,对x∈U,必有gf(x)⊆RD(x)。于是可得到|U|条决策规则,这些决策规则都是确定性规则。但显然决策形式背景中还存在其他不确定性规则,下面给出用|U|条确定性规则得到全部规则的规则融合方法。

U/RD={D1,D2,…,Dr}

(2)对于决策类Dj(j≤r),记

Mj={(f(xi)(a1),f(xi)(a2),…,

f(xi)(a|A|)):xi∈Dj}

S1≤S2≤…≤Sr

即决策类越大,对象的条件属性隶属度向量越大。用S1

S1

①若f(x)≥Sr,则d(x)=r。

②若f(x)≥Sj,且f(x)≯Sj+1时d(x)=j(1≤j≤r-1)。

③若f(x)≯S1时d(x)=0。

规则①表示当对象的条件属性隶属度向量不小于Sr的时候,其决策值与Dr的决策值相同。规则②表示当对象的条件属性隶属度向量处于Sj和Sj+1之间的时候,其决策值与Dj的决策值相同。规则③表示当对象的条件属性隶属度向量不大于S1的时候,其决策值与D1的决策值相同,也可以根据具体情况进行调整,使d(x)=1,总表示最差的一类。用这些决策规则就能够得到所有决策。

算法2给出了具体算法。

算法2正协调模糊决策形式背景的规则融合算法

输出:决策规则;

2:如果dl(x)≤dl(y)

3:(x,y)∈RD

4:U/RD={RD(x):x∈U}={D1,D2,…,Dr}

5:计算(Dj,Tj)

6:对Dj(j≤r)

7:Mj={(f(xi)(a1),…,f(xi)(a|A|)):xi∈Dj}

∧(f(xi)(a2)),…,∧(f(xi)(a|A|)),xi∈Dj

10:如果f(x)≥Sr,则d(x)=r;

如果f(x)≥Sj,f(x)≯Sj+1则d(x)=j(1≤j≤r-1);

如果f(x)≯S1则d(x)=0。

该算法最坏复杂度为O(|U|2(|D|+|A|+r)+|U||A|r)。

表2 模糊决策形式背景

计算可知:U/RD={D1,D2,D3},其中D1={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10},D2={x1,x2,x3,x4,x7,x9,x10},D3={x2,x7,x10}。则所有决策概念计算如下:

({x1,x2,x3,x4,x5,x6,x7,x8,x9,x10},{d=1})

({x1,x2,x3,x4,x7,x9,x10},{d=2})

({x2,x7,x10},{d=3})

可计算出所有的经典-模糊对象概念,如表3所示。

表的经典-模糊对象概念

从而可以获取所有的粒决策规则如下:

根据算法2继续计算

M1={(0.6,0.7,0.9,0.6),(0.6,0.7,0.6,0.6),

(0.7,0.7,0.6,0.6),(0.7,0.9,0.8,0.9),

(0.9,0.9,0.6,0.9)}

M2={(0.7,0.7,0.6,0.6),(0.7,0.9,0.8,0.9),

(0.9,0.9,0.6,0.9)}

M3={(0.9,0.9,0.6,0.9)}

故

S1=(0.6,0.7,0.6,0.6)

S2=(0.7,0.7,0.6,0.6)

S3=(0.9,0.9,0.6,0.9)

可知S1

①若f(x)≥S3,则d(x)=3;

②若f(x)≥S2,且f(x)≯S3时d(x)=2;

③若f(x)≥S1,且f(x)≯S2时d(x)=1;

④若f(x)≯S1,则d(x)=0。

根据以上方法可以得到全部的决策规则:

4 结束语

规则提取是决策形式背景中的重要问题,其目的是为了获取最优决策。本文在模糊决策形式背景中仅条件属性部分构造概念格模型,在决策部分基于优势关系获取关于对象集的覆盖,从而确定决策类,能够缩短计算时间。针对这一模型提出了基于优势关系的模糊决策形式背景的粒协调、序协调及正协调的定义,并对其关系进行讨论。

本文在基于优势关系的正协调模糊决策形式背景中基于确定性的粒决策规则给出规则融合方法,获取了正协调模糊决策形式背景的全部规则,其中不仅包括粒决策规则这样的确定性规则,也包括不确定性规则,甚至可以给出和原形式背景中对象取值不同的对象的决策规则。目前本文只针对正协调模糊决策形式背景的决策规则融合进行谈论,在实际问题中,有很多数据是不符合这一协调性的,因此,在今后的工作中将进一步探讨不协调的模糊决策形式背景上的规则融合问题。