第33卷第8期 华中科技大学学报(自然科学版) Vol.33 No.82005年 8月 J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition) Aug. 2005
基于粗糙集的属性约简算法研究
瞿彬彬 卢炎生
(华中科技大学计算机科学与技术学院,湖北武汉430074)
摘要:提出一种新的基于粗糙集的属性约简算法.该算法采用层次结构和近似精度的概念,约简集中的属性选择从空集开始,用启发函数ξ作为选择条件属性的衡量标准,逐步加入相对于决策而言重要的条件属性,并采用下近似值作为剪枝依据,逐步删除给定论域U中根据该属性子集能完全正确分类的对象,减小了属性约简过程中的搜索空间,处理过程是递归的,直到给定论域U为空集,保证了在分类精度不变的情况下,获得简化的属性集,最后运用粗糙集中正域的概念,约简冗余的属性值并求出其最简规则.对UCI机器学习数据库中7个数据库属性约简结果证明了该算法的正确性和可行性.关 键 词:粗糙集;层次结构;启发式算法
中图分类号:TP18 文献标识码:A 文章编号:1671()08Roughsets2reduction
BLansheng
Abstract:Awasproposed.Inthealgorithmapproximationqualitycon2ceptandwereadopted;beginningwithnullsetandtakingheuristicfunctionξasacri2teriontochoosetheessentialattributes;theimportantattributerelativetodecisionwasaddedstepbystep,searchingspaceduringthereductionwascutdown,intermsoflowerapproximationsandtheobjectstheu2niverseUmakingcompletelycorrectclassificationprogressively.Theprocessisrecursionuntiltheuniverse
Uisempty,gettingreducedattributesetwithunvariedclassificationaccuracy.Byusingtherelativeposi2
tiveregionconceptofroughsets,superfluousattributevalueswerereducedandsimplyrulesinduced.ThevalidityandfeasibilityofthealgorithmsweredemonstratedbytheresultsofreducingthesevendatabasesoftheUCI.
Keywords:roughsets;hierarchystructure;heuristic
QuBinbin DoctoralCandidate;CollegeofComputerSci.&Tech.HuazhongUniv.ofSci.&Tech.,
Wuhan430074,China.
粗糙集理论[1]是一种新的处理模糊和不精确问题的重要的数学工具,其主要思想是直接从给定问题的描述集合出发,在保持分类能力不变的前提下,通过知识约简,导出概念的分类规则.
属性约简是粗糙集理论研究的核心问题之一.Wong.S.K.M和Ziarko.W等已经从计算复杂性的角度证明了寻找最小约简是NP2hard问题[2].解决这类问题的方法一般采用启发式搜索,通过在算法中加入启发式信息,缩小问题的搜
收稿日期:2004209216.
索空间,进而获得最优解或近似最优解.
本文采用层次结构和近似精度的概念,提出了启发式的属性约简递归算法.该算法虽然不能保证是最优的,但给出解决大型复杂问题的一种途径.
1 粗糙集基本理论
本节简述与后面讨论相关的粗糙集理论[3,4]
作者简介:瞿彬彬(19702),女,博士研究生;武汉,华中科技大学计算机科学与技术学院(430074).
E2mail:[email protected]
基金项目:“十五”国防预研基金资助项目.
第8期 瞿彬彬等:基于粗糙集的属性约简算法研究 31
的主要概念.
定义1 信息系统.信息系统(简称IS)是一个4元组,即IS〈U,Q,V,ρ〉,U表示一个有限对象集合,即论域;Q是有限属性集合;V=∪Vq,Vq属性Q的值域;ρ=U×Q→V是一
q∈Q
d完全依赖于A;若k
2 属性约简算法描述
2.1 理论基础
个信息函数.
决策信息系统(简称DS)是一种信息系统,其属性Q被分成条件属性A和决策属性d(A∪
d=Q,A∩d= )两个不同的集合.
定义2 不可分辨关系.信息系统IS〈U,
Q,V,ρ〉.对于每个属性子集BΑA,定义一个不可分辨的二元关系IND(B)={(x,y)|(x,y)∈U×U:Πq∈Bρ(x,q)=ρ(y,q)}.IND(B)是一个等价关系.由这种等价关系导出
根据条件属性A,若在不可分辨集合中的对象都有相同的决策值,则该决策系统是相容的;否则,该决策系统是不相容的.
定义8 相容的决策信息系统DS〈U,A∪d,V,ρ〉有如下性质:Πx,y∈U(d(x)≠
d(y))→ϖa∈A(a(x)≠a(y)).
定理1[5] 一个决策信息系统DS〈U,A∪d,V,ρ〉,x∈U,有x|POSA({d})→Πy∈
U([x]IND(A)⁄[y]IND({d})).
的对U的划分记为U/IND(B),其中包含样本x的等价类记为[x]IND(B).
定义3 近似集合.上近似集和下近似集是粗糙集分析数据的两个基本概念.设X的一个子集(X
对于每个B(ΑA),X的下近似集BU:B(X)ΑX}.
X的上近似集B
3
证明 设
[′]IND().
y′∈且[x]IND(A)Α
Α
∈⁄
[x]IND(A)
A3[({d})A(d})),x
∈U
([x]IND(A)
,这与前提条件矛盾,所以x|A({d})→Πy
[y]IND({d})).
,B判定肯定属
于X的U中的对象组成的集合:B3(X)={X∈
(X),根据知识B判定可
定理2[5] 一个相容的决策信息系统DS〈U,A∪d,V,ρ〉,满足POSA({d})=U.
证明 必要性.设决策信息系统DS是相容的,且POSA({d})≠U,ϖx∈U(x|POSA({d})),根据定理1,Πy∈U([x]IND(A)⁄
[y]IND({d})),只有当[x]IND(A)的决策值不惟一时
能属于X的U中的对象组成的集合B3(X)=
{X∈U:B(X)∩X≠ }.
定义4 正域.POSB(X)=B3(X).根据知识B,U中一定能归入集合X的对象构成的集合.
定义5 约简与核.信息系统IS〈U,Q,V,ρ〉,设r∈A,若IND(A)=IND(A-{r}),则称
r为A中可省略的,否则r为A中可省略的;若A中的任意一个属性都是A中不可省略的,则A
才发生,与系统是相容的这个前提条件相矛盾,因此决策信息系统DS相容,可推出POSA({d})=
U.
充分性.设POSA({d})=U,且决策信息系统DS不相容.从定义1知道ϖx,y∈
U(d(x)≠d(y))∧Πa∈A(a(x)=a(y)).即x,y属于等价关系,x,y∈[x]IND(A),但它们的
是独立的.对于属性集PΑA,若存在Q=P-{r},QΑP,使得IND(Q)=IND(P),且Q为独
决策值[x]IND({d})却不相同.根据下近似的定义,
[x]IND(A)⁄POSA({d}),这与前面的假设相矛
立的,则Q称为P的约简,记为RED(P).一个属性集合可能有多个约简.核是P中所有的约简属性集都包含的不可省略属性的集合,记为CORE(P)=∩RED(P).
盾.因此,若POSA({d})=U,则可以推出决策信息系统DS是相容的.证毕.
一个相容的决策信息系统DS有如下性质:
|∪A3(x)||U|=1.a.γA(d)=∑x∈u/db.设C为A的属性子集(CΑA),若满足
定义6 近似精度.决策信息系统DS〈U,
A∪d,V,ρ〉,A∩d= ,A与d之间的依赖度由k定义,表示为A]kd,其中
k=γA(d)=
γC(d)=∑|
x∈u/d
∪C3(x)||U|=1,则子集C是
∑|
X∈U/d
∪A3(X)||U|,
约简的属性集之一.
2.2 算法描述
首先,计算相容决策信息系统中的所有条件属性等价关系.对于每个等价关系,计算其相对于
即给定论域U中所有对象都能根据属性A被唯一地归入决策属性d所划分的类中.若k=1,则
华 中 科 技 大 学 学 报(自然科学版) 第33卷32
决策值的上近似和下近似,并根据启发函数ξ=|B3(X)|-|B3(X)|/|U|.
(1)
计算ξ值,选择具有最小ξ值的属性列作为必须保留属性.给定论域采用下近似值作为剪枝的依据
U=U-POSRed{d},
(2)
新的论域.
U←U-POSRed{d},
U={1,2,4,5,6,8,9,10,11,14}.处理过程采用组合属性重复进行.表3和表4列出了组合属性及其ξ值.
表1 关于天气的决策系统
U
a1
a2
a3
a4
dNNPPPNPNPPPPPN
式中POSRed{d}表示根据约简集Red中的条件属性,一定能归入论域U中决策类d的所有对象集合.
重复选择属性的过程,选择必须保留的属性,每次都是将剩下的属性与约简集Red中的属性相结合产生新的等价关系.启发函数被应用于这些关系中作为选择属性的衡量标准.算法是递归的,直到给定论域为空集为止.算法如下.
输入一个相容的决策信息系统DS〈U,A∪
d,V,ρ〉;
输出决策信息系统的属性约简;初始化Red← ,A←A-Red.
步骤1 根据式(1)值.
步骤2 列.
步骤3 选择值最小的属性列.若存在多个属性列具有相同的ξ值,则选择具有最少属性值的属性列.
步骤4 Red←Red∪{ai},A←A-Red,
U←U-POSRed{d}.
[**************]晴晴多云雨雨雨多云晴晴雨热热热温暖冷冷冷温暖冷热高高高高正常正常正常高高正常否真否否否真真否否否真真否表2 4个条件属性和1个决策属性之间的
不可分辨集合关系
属性
d=N
a1
a2
a3
a4
下近似
上近似 下近似上近似ξ
1,2,8,9,10,11,4,5,6,14
3,7,12,13
U
U
U
U
U
U
U
d=P
步骤5 若U= ,转至步骤8,否则转至步骤6.
步骤6 将Red集里的属性与A集合里剩余的属性分别结合.
步骤7 采用组合属性,重复步骤1～5.步骤8 输出约简属性集Red.
10/7222
表3 算法第二轮时的不可分辨关系集属性
a1,a2
a1,a3
a1,a4
下近似1,21,2,8
d=N上近似1,2,4,10,1,2,8,4,
14,5,6,8,1114,5,6,10下近似d=P上近似
ξ
94,10,14,56,9,11,8
7/5
9,114,14,5,610,9,11
1
6,141,8,9,2,11,6,144,5,101,8,9,2,114,5,10
1
3 算例
用表1所示的天气决策表来说明如何用上述算法来获得约简的属性子集.表1中,a1,a2,a3,
a4是条件属性,分别代表天气、温度、湿度、风.d
表4 算法第三轮时的不可分辨关系集属性
d=Nd=P
a1,a3,a2
a1,a3,a4
是决策属性,论域U={x1,x2,…,x14}.
对于每个属性,采用式(1)计算ξ值,见表2.
根据算法,因为a1具有最小的ξ值,所以选择a1作为约简属性放入约简集Red中.
Red←{a1}, Red={a1},
A←A-Red, A={a2,a3,a4}.
下近似上近似
下近似上近似ξ
4,6,14,5
104,5,10,6,14
8/5
14,66,144,5,104,5,100
根据式(2),给定论域进行剪枝,得到缩减的
在本例中,a1a3和a1a4的ξ值相同,根据算
法,选择属性值最少的属性,由于a3和a4属性值相同,因此根据算法,随机选择a3作为约简属性.
第8期 瞿彬彬等:基于粗糙集的属性约简算法研究 33
Red←Red∪{a3}, Red={a1,a3},
U←U-POSRed{d}, U={4,5,6,10,14},
A←A-Red, A={a2,a4}.
U
表6 一张约简的天气决策表
a1
a3
a4
dNNPPPNPPPPPN
1,82345,[1**********]14
同样,选择a4作为约简属性.Red←Red∪{a4}, Red={a1,a4,a3},
A←A-Red, A={a2}.
此时U= ,即根据条件属性a1,a4,a3,可以分辨出等价关系IND(d),因此,约简的属性子集即为Red={a1,a4,a3}.
为了评估算法,采用机器学习通用的UCI数据库来做测试.表5显示了在这些数据库里的属性选择结果.Inst-n,attr-n,attr-n(red)分别代表实例数量、属性数量和约简后的属性数量.
表5 实验结果
数据集
Balloondatabase(1)Mushroomdatabase
Lenses
PostoperativepatientSolarFlareDatabase(2)
Tic2tac2toeZoo
Inst-n[1**********]58Attr-nAttr-n(red)42241017
24469810
晴晴多云雨雨雨多云晴晴多云多云雨高高高高正常正常正常正常正常高正常高否真否否否真真否真真否真
表7 属性核值
U
a1
a3
a4
dNNPPPNPPPPPN
1,8235,[1**********]14
实验表明,该算法能快速有效地选择一个好
的属性约简子集.
4 规则推理
采用参考文献[6]所提出的方法来产生规则.
定义9 一个相容的决策信息系统DS〈U,A∪d,V,ρ〉,Πa∈A,则以属性a为核值属性的决策规则集合为
Core(a)={dx:x∈(U-POSA-{a}(d))}. 表1中若仅用a1,a4,a3这三个属性,则元组(1,8)(5,10)相同,因此可以合并相同的元组,结果如表6所示.根据定义9,分别计算每个属性的核值core(a),Πa∈A,计算结果如表7所示.
对于每个依赖A]kd都可以被描述为“IF
ψ,ω是条件,…THEN”的决策规则,表示为ω→
ψ是结论,并有)”)”“和(∧“或(∨等连接词连接属性及其值.从表7中得到以下规则:
规则1 (a1,晴)∧(a3,高)→(d,N).规则2 (a1,多云)→(d,P).
规则3 (a1,雨)∧(a4,否)→(d,P).规则4 (a1,雨)∧(a4,真)→(d,N).规则5 (a1,晴)∧(a3,正常)→(d,P).
晴雨雨雨多云晴晴多云-----正常正常---
---
否否真-----
参
考
文
献
[1]PawlakZ.Roughsets[J].InternationalJournalof
ComputerandInformationSciences,1982,1(11):341—356
[2]WongSKM,ZiarkoW.Onoptionaldecisionrulesin
decisiontables[J].BulletinofPolishAcademyofSci2ence,1985,33:693—696
[3]PawlakZ.Roughsetapproachtomulti2attributedeci2
sionanalysis[J].EuropeanJournalofOperationalRe2search,1994,(12)72:443—459
[4]WalczakB,MassartDL.Roughsetstheory[J].
Chemometricsand1999,1(47):1—16
[5]赵 军,王国胤.一种高效的属性核计算方法[J].小
IntelligentLaboratorySystem,
型微型计算机系统,2003,24(11):1950—1953
[6]吴保福,李 奇,宋文忠.基于粗集理论知识表达系统
的一种归纳学习方法[J].控制与决策,1999,
14(3):206—211
第33卷第8期 华中科技大学学报(自然科学版) Vol.33 No.82005年 8月 J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition) Aug. 2005
基于粗糙集的属性约简算法研究
瞿彬彬 卢炎生
(华中科技大学计算机科学与技术学院,湖北武汉430074)
摘要:提出一种新的基于粗糙集的属性约简算法.该算法采用层次结构和近似精度的概念,约简集中的属性选择从空集开始,用启发函数ξ作为选择条件属性的衡量标准,逐步加入相对于决策而言重要的条件属性,并采用下近似值作为剪枝依据,逐步删除给定论域U中根据该属性子集能完全正确分类的对象,减小了属性约简过程中的搜索空间,处理过程是递归的,直到给定论域U为空集,保证了在分类精度不变的情况下,获得简化的属性集,最后运用粗糙集中正域的概念,约简冗余的属性值并求出其最简规则.对UCI机器学习数据库中7个数据库属性约简结果证明了该算法的正确性和可行性.关 键 词:粗糙集;层次结构;启发式算法
中图分类号:TP18 文献标识码:A 文章编号:1671()08Roughsets2reduction
BLansheng
Abstract:Awasproposed.Inthealgorithmapproximationqualitycon2ceptandwereadopted;beginningwithnullsetandtakingheuristicfunctionξasacri2teriontochoosetheessentialattributes;theimportantattributerelativetodecisionwasaddedstepbystep,searchingspaceduringthereductionwascutdown,intermsoflowerapproximationsandtheobjectstheu2niverseUmakingcompletelycorrectclassificationprogressively.Theprocessisrecursionuntiltheuniverse
Uisempty,gettingreducedattributesetwithunvariedclassificationaccuracy.Byusingtherelativeposi2
tiveregionconceptofroughsets,superfluousattributevalueswerereducedandsimplyrulesinduced.ThevalidityandfeasibilityofthealgorithmsweredemonstratedbytheresultsofreducingthesevendatabasesoftheUCI.
Keywords:roughsets;hierarchystructure;heuristic
QuBinbin DoctoralCandidate;CollegeofComputerSci.&Tech.HuazhongUniv.ofSci.&Tech.,
Wuhan430074,China.
粗糙集理论[1]是一种新的处理模糊和不精确问题的重要的数学工具,其主要思想是直接从给定问题的描述集合出发,在保持分类能力不变的前提下,通过知识约简,导出概念的分类规则.
属性约简是粗糙集理论研究的核心问题之一.Wong.S.K.M和Ziarko.W等已经从计算复杂性的角度证明了寻找最小约简是NP2hard问题[2].解决这类问题的方法一般采用启发式搜索,通过在算法中加入启发式信息,缩小问题的搜
收稿日期:2004209216.
索空间,进而获得最优解或近似最优解.
本文采用层次结构和近似精度的概念,提出了启发式的属性约简递归算法.该算法虽然不能保证是最优的,但给出解决大型复杂问题的一种途径.
1 粗糙集基本理论
本节简述与后面讨论相关的粗糙集理论[3,4]
作者简介:瞿彬彬(19702),女,博士研究生;武汉,华中科技大学计算机科学与技术学院(430074).
E2mail:[email protected]
基金项目:“十五”国防预研基金资助项目.
第8期 瞿彬彬等:基于粗糙集的属性约简算法研究 31
的主要概念.
定义1 信息系统.信息系统(简称IS)是一个4元组,即IS〈U,Q,V,ρ〉,U表示一个有限对象集合,即论域;Q是有限属性集合;V=∪Vq,Vq属性Q的值域;ρ=U×Q→V是一
q∈Q
d完全依赖于A;若k
2 属性约简算法描述
2.1 理论基础
个信息函数.
决策信息系统(简称DS)是一种信息系统,其属性Q被分成条件属性A和决策属性d(A∪
d=Q,A∩d= )两个不同的集合.
定义2 不可分辨关系.信息系统IS〈U,
Q,V,ρ〉.对于每个属性子集BΑA,定义一个不可分辨的二元关系IND(B)={(x,y)|(x,y)∈U×U:Πq∈Bρ(x,q)=ρ(y,q)}.IND(B)是一个等价关系.由这种等价关系导出
根据条件属性A,若在不可分辨集合中的对象都有相同的决策值,则该决策系统是相容的;否则,该决策系统是不相容的.
定义8 相容的决策信息系统DS〈U,A∪d,V,ρ〉有如下性质:Πx,y∈U(d(x)≠
d(y))→ϖa∈A(a(x)≠a(y)).
定理1[5] 一个决策信息系统DS〈U,A∪d,V,ρ〉,x∈U,有x|POSA({d})→Πy∈
U([x]IND(A)⁄[y]IND({d})).
的对U的划分记为U/IND(B),其中包含样本x的等价类记为[x]IND(B).
定义3 近似集合.上近似集和下近似集是粗糙集分析数据的两个基本概念.设X的一个子集(X
对于每个B(ΑA),X的下近似集BU:B(X)ΑX}.
X的上近似集B
3
证明 设
[′]IND().
y′∈且[x]IND(A)Α
Α
∈⁄
[x]IND(A)
A3[({d})A(d})),x
∈U
([x]IND(A)
,这与前提条件矛盾,所以x|A({d})→Πy
[y]IND({d})).
,B判定肯定属
于X的U中的对象组成的集合:B3(X)={X∈
(X),根据知识B判定可
定理2[5] 一个相容的决策信息系统DS〈U,A∪d,V,ρ〉,满足POSA({d})=U.
证明 必要性.设决策信息系统DS是相容的,且POSA({d})≠U,ϖx∈U(x|POSA({d})),根据定理1,Πy∈U([x]IND(A)⁄
[y]IND({d})),只有当[x]IND(A)的决策值不惟一时
能属于X的U中的对象组成的集合B3(X)=
{X∈U:B(X)∩X≠ }.
定义4 正域.POSB(X)=B3(X).根据知识B,U中一定能归入集合X的对象构成的集合.
定义5 约简与核.信息系统IS〈U,Q,V,ρ〉,设r∈A,若IND(A)=IND(A-{r}),则称
r为A中可省略的,否则r为A中可省略的;若A中的任意一个属性都是A中不可省略的,则A
才发生,与系统是相容的这个前提条件相矛盾,因此决策信息系统DS相容,可推出POSA({d})=
U.
充分性.设POSA({d})=U,且决策信息系统DS不相容.从定义1知道ϖx,y∈
U(d(x)≠d(y))∧Πa∈A(a(x)=a(y)).即x,y属于等价关系,x,y∈[x]IND(A),但它们的
是独立的.对于属性集PΑA,若存在Q=P-{r},QΑP,使得IND(Q)=IND(P),且Q为独
决策值[x]IND({d})却不相同.根据下近似的定义,
[x]IND(A)⁄POSA({d}),这与前面的假设相矛
立的,则Q称为P的约简,记为RED(P).一个属性集合可能有多个约简.核是P中所有的约简属性集都包含的不可省略属性的集合,记为CORE(P)=∩RED(P).
盾.因此,若POSA({d})=U,则可以推出决策信息系统DS是相容的.证毕.
一个相容的决策信息系统DS有如下性质:
|∪A3(x)||U|=1.a.γA(d)=∑x∈u/db.设C为A的属性子集(CΑA),若满足
定义6 近似精度.决策信息系统DS〈U,
A∪d,V,ρ〉,A∩d= ,A与d之间的依赖度由k定义,表示为A]kd,其中
k=γA(d)=
γC(d)=∑|
x∈u/d
∪C3(x)||U|=1,则子集C是
∑|
X∈U/d
∪A3(X)||U|,
约简的属性集之一.
2.2 算法描述
首先,计算相容决策信息系统中的所有条件属性等价关系.对于每个等价关系,计算其相对于
即给定论域U中所有对象都能根据属性A被唯一地归入决策属性d所划分的类中.若k=1,则
华 中 科 技 大 学 学 报(自然科学版) 第33卷32
决策值的上近似和下近似,并根据启发函数ξ=|B3(X)|-|B3(X)|/|U|.
(1)
计算ξ值,选择具有最小ξ值的属性列作为必须保留属性.给定论域采用下近似值作为剪枝的依据
U=U-POSRed{d},
(2)
新的论域.
U←U-POSRed{d},
U={1,2,4,5,6,8,9,10,11,14}.处理过程采用组合属性重复进行.表3和表4列出了组合属性及其ξ值.
表1 关于天气的决策系统
U
a1
a2
a3
a4
dNNPPPNPNPPPPPN
式中POSRed{d}表示根据约简集Red中的条件属性,一定能归入论域U中决策类d的所有对象集合.
重复选择属性的过程,选择必须保留的属性,每次都是将剩下的属性与约简集Red中的属性相结合产生新的等价关系.启发函数被应用于这些关系中作为选择属性的衡量标准.算法是递归的,直到给定论域为空集为止.算法如下.
输入一个相容的决策信息系统DS〈U,A∪
d,V,ρ〉;
输出决策信息系统的属性约简;初始化Red← ,A←A-Red.
步骤1 根据式(1)值.
步骤2 列.
步骤3 选择值最小的属性列.若存在多个属性列具有相同的ξ值,则选择具有最少属性值的属性列.
步骤4 Red←Red∪{ai},A←A-Red,
U←U-POSRed{d}.
[**************]晴晴多云雨雨雨多云晴晴雨热热热温暖冷冷冷温暖冷热高高高高正常正常正常高高正常否真否否否真真否否否真真否表2 4个条件属性和1个决策属性之间的
不可分辨集合关系
属性
d=N
a1
a2
a3
a4
下近似
上近似 下近似上近似ξ
1,2,8,9,10,11,4,5,6,14
3,7,12,13
U
U
U
U
U
U
U
d=P
步骤5 若U= ,转至步骤8,否则转至步骤6.
步骤6 将Red集里的属性与A集合里剩余的属性分别结合.
步骤7 采用组合属性,重复步骤1～5.步骤8 输出约简属性集Red.
10/7222
表3 算法第二轮时的不可分辨关系集属性
a1,a2
a1,a3
a1,a4
下近似1,21,2,8
d=N上近似1,2,4,10,1,2,8,4,
14,5,6,8,1114,5,6,10下近似d=P上近似
ξ
94,10,14,56,9,11,8
7/5
9,114,14,5,610,9,11
1
6,141,8,9,2,11,6,144,5,101,8,9,2,114,5,10
1
3 算例
用表1所示的天气决策表来说明如何用上述算法来获得约简的属性子集.表1中,a1,a2,a3,
a4是条件属性,分别代表天气、温度、湿度、风.d
表4 算法第三轮时的不可分辨关系集属性
d=Nd=P
a1,a3,a2
a1,a3,a4
是决策属性,论域U={x1,x2,…,x14}.
对于每个属性,采用式(1)计算ξ值,见表2.
根据算法,因为a1具有最小的ξ值,所以选择a1作为约简属性放入约简集Red中.
Red←{a1}, Red={a1},
A←A-Red, A={a2,a3,a4}.
下近似上近似
下近似上近似ξ
4,6,14,5
104,5,10,6,14
8/5
14,66,144,5,104,5,100
根据式(2),给定论域进行剪枝,得到缩减的
在本例中,a1a3和a1a4的ξ值相同,根据算
法,选择属性值最少的属性,由于a3和a4属性值相同,因此根据算法,随机选择a3作为约简属性.
第8期 瞿彬彬等:基于粗糙集的属性约简算法研究 33
Red←Red∪{a3}, Red={a1,a3},
U←U-POSRed{d}, U={4,5,6,10,14},
A←A-Red, A={a2,a4}.
U
表6 一张约简的天气决策表
a1
a3
a4
dNNPPPNPPPPPN
1,82345,[1**********]14
同样,选择a4作为约简属性.Red←Red∪{a4}, Red={a1,a4,a3},
A←A-Red, A={a2}.
此时U= ,即根据条件属性a1,a4,a3,可以分辨出等价关系IND(d),因此,约简的属性子集即为Red={a1,a4,a3}.
为了评估算法,采用机器学习通用的UCI数据库来做测试.表5显示了在这些数据库里的属性选择结果.Inst-n,attr-n,attr-n(red)分别代表实例数量、属性数量和约简后的属性数量.
表5 实验结果
数据集
Balloondatabase(1)Mushroomdatabase
Lenses
PostoperativepatientSolarFlareDatabase(2)
Tic2tac2toeZoo
Inst-n[1**********]58Attr-nAttr-n(red)42241017
24469810
晴晴多云雨雨雨多云晴晴多云多云雨高高高高正常正常正常正常正常高正常高否真否否否真真否真真否真
表7 属性核值
U
a1
a3
a4
dNNPPPNPPPPPN
1,8235,[1**********]14
实验表明,该算法能快速有效地选择一个好
的属性约简子集.
4 规则推理
采用参考文献[6]所提出的方法来产生规则.
定义9 一个相容的决策信息系统DS〈U,A∪d,V,ρ〉,Πa∈A,则以属性a为核值属性的决策规则集合为
Core(a)={dx:x∈(U-POSA-{a}(d))}. 表1中若仅用a1,a4,a3这三个属性,则元组(1,8)(5,10)相同,因此可以合并相同的元组,结果如表6所示.根据定义9,分别计算每个属性的核值core(a),Πa∈A,计算结果如表7所示.
对于每个依赖A]kd都可以被描述为“IF
ψ,ω是条件,…THEN”的决策规则,表示为ω→
ψ是结论,并有)”)”“和(∧“或(∨等连接词连接属性及其值.从表7中得到以下规则:
规则1 (a1,晴)∧(a3,高)→(d,N).规则2 (a1,多云)→(d,P).
规则3 (a1,雨)∧(a4,否)→(d,P).规则4 (a1,雨)∧(a4,真)→(d,N).规则5 (a1,晴)∧(a3,正常)→(d,P).
晴雨雨雨多云晴晴多云-----正常正常---
---
否否真-----
参
考
文
献
[1]PawlakZ.Roughsets[J].InternationalJournalof
ComputerandInformationSciences,1982,1(11):341—356
[2]WongSKM,ZiarkoW.Onoptionaldecisionrulesin
decisiontables[J].BulletinofPolishAcademyofSci2ence,1985,33:693—696
[3]PawlakZ.Roughsetapproachtomulti2attributedeci2
sionanalysis[J].EuropeanJournalofOperationalRe2search,1994,(12)72:443—459
[4]WalczakB,MassartDL.Roughsetstheory[J].
Chemometricsand1999,1(47):1—16
[5]赵 军,王国胤.一种高效的属性核计算方法[J].小
IntelligentLaboratorySystem,
型微型计算机系统,2003,24(11):1950—1953
[6]吴保福,李 奇,宋文忠.基于粗集理论知识表达系统
的一种归纳学习方法[J].控制与决策,1999,
14(3):206—211