第38卷第1期计算机仿真2021年1月文章编号:1〇〇6-9348(2021)01 -0251 -05
肖斌，孙乾智
(西南石油大学计算机科学学院，四川成都610500)
摘要：对于混合决策系统的属性约简，现有方法主要存在动态效果不佳、复杂度过髙，以及约简精度差等问题，为此，提出一
种启发式增量属性约简方法。针对混合决策系统的动态波动，基于粗糙集建立了邻域关系模型，根据邻域相对差异对增量 属性进行更新。同时，为进一步增强约简算法的动态适应性，引人条件熵求解相对差异。考虑到单纯利用邻域依赖虽然有
利于处理样本的分布不均，但是很难获得良好的属性评估，引人粒度模型进行优化，将邻域关系采用粒度重新描述，从而细
化邻域关系。利用邻域依赖性得到决策属性度量，构造启发计算，同时，通过条件和决策间的关联度，以及粒度模型的单调，
求解出条件和决策共同约束下的邻域关系。再根据决策属性度量作为启发，直至单一属性对子集决策性能不再有影响，完
成属性约简。基于数据集的仿真，验证了提出的启发式增量属性约简方法能够降低约简冗余度和约简长度，有效提高属性
约简精度和约简时间效率。
关键词：混合决策系统；邻域关系；条件熵；粒度模型；启发式属性约简
中图分类号:TP181 文献标识码：B
Research on Heuristic Incremental Attribute Reduction
Method of Hybrid Decision System西部开发报
XIAO Bin,SUN Qian-zhi
(S c h o o l o f Computer Sc ince,S o u t h w e s t P e t r o l e u m U n i v e r s i t y,Chengdu S i c h u a n610500, China) ABSTRACT ：F o r a t t r i b u t e r e d u c t i o n o f h y b r i d d e c i s i o n system,t h e e x i s t i n g me thods m a i n l y h a v e t h e p r o b l e m s o f
p o o r dynamic e f f e c t,h i g h c o m p l e x i t y and p o o r r e d u c t i o n ac cu r a c y,T h e r e f o r e,a h e u r i s t i c i n c r e m e n t a l a t t r i b u t e r e d u c
t i o n method i s pr op o s e d.I n v i e w o f t h e dy namic f l u c t u a t i o n o f t h e h y b r i d d e c i s i o n system,a n e i g h b o r h o o d r e l a t i o n
广东省机械设备成套局mo d e l was e s t a b l i s h e d b a s e d o n t h e r o u g h s e t,an d t h e i n c r e m e n t a l a t t r i b u t e was u p d a t e d a c c o r d i n g t o t h e r e l a t i v e
d i f f
e r e n c e o
f t h e n e i
g
h b o r h o o d.A t t h e same t
i m e,i n o r d e r t o f u r t h e r en ha nc e t h e dynamic a d a p t a b i l i t y o f r e d u c t i o n
a l g o r i t h m,c o n d i t i o n e n t r o p y was i n t r o d u c e d t o s o l v e t h e r e l a t i v e d i f f e r e n c e.C o n s i d e r i n g t h a t t h e u s e o f n e i g h
b o r h o o d
dependency a l o n e i s c o n d u c i v e t o d e a l i n g w i t h t h e uneven d i s t r i b u t i o n o f samples,b u t i t i s d i f f i c u l t t o o b t a i n a g o o d
a t t r i
b u t e e v a l u a t i o n,t h e p a r t i
c l e s i z e model wa s i n t r o
d u c
e d t o o p t i m i z e,The n e i g h b o r h o o d r e l a t i o n s h i p was r e de
s c r i b e d b y g r a n u l a r i t y,s o a s t o r e f i n e t h e n e i g h b o r h o o d r e l a t i o n s h i p.N e i g h b o r h o o d dependence was u s e d t o g e t d e c i
s i o n a t t r i b u t e measure and c o n s t r u c t h e u r i s t i c c a l c u l a t i o n.A t t h e same time,t h r o u g h t h e c o r r e l a t i o n be t w e e n c o n d i
t i o n s and d e c i s i o n s,and t h e monotony o f t h e g r a n u l a r i t y model,t h e n e i g h b o r h o o d r e l a t i o n s h i p un de r t h e common con
s t r a i n t s o f c o n d i t i o n s and d e c i s i o n s was s o l v e d.Then T a ki ng t h e d e c i s i o n a t t r i b u t e measurement a s a h e u r i s t i c,t h e
a t t r i
b u t e r e d u
c t i o n was c o m p l e t e
d u n t i l a s i n g l
e a t t r i b u t e no l o n g e r a
f f e c t s t h e d e c i s i o n- makin
g p e r f o r m a n c e o f t
h e
s u b s e t.Based on UCI d a t a s e t,t h e s i m u l a t i o n e x p e r i m e n t v e r i f i e s t h a t t h e p r o p o s e d h e u r i s t i c i n c r e m e n t a l a t t r i b u t e r e
d u c t i o n method ca n r
e d u c e t h e re du nd an cy and r e d u c t i o n l e n g t h and e
f f e c t i v e l y i m p r o v e t h e a c c u r a c y an d t i m e e f f i
c i e n c y o f a t t r i b u t e r e
d u c t i o n.
KEYWORDS：Hy br id d e c i s i o n system；N e i g h b o r h o o d r e l a t i o n s h i p；C o n d i t i o n a l e n t r o p y；G r a n u l a r i t y model；H e u r i s t i c
a t t r i
b u t e r e d u
c t i o n
基金项目：青年自然科学基金(41604114)
收稿日期:2020 - 06 - 25修回日期:2020 -07 -28
—251—
1引言
属性约简就是对信息系统中的特征进行选择"]，该技术 通常应用于数据处理与分析场景。约简过程中，需要从复杂 属性组建的数据集内完成属性的分类与去冗余等操作[2]，但 是在信息系统越来越复杂的情况下，无效冗余属性也随之复 杂难辨，对于目标信息的提取产生严重干扰。尤其是在大数 据应用场景中，数据规模与数据属性的动态变化，给属性约 简造成严峻挑战。当数据中存在决策属性时，约简结果存在 非确定性，当数据规模与数据动态变化，条件属性与决策之 间的组合形式将快速增加，如何从已知条件属性中搜索出有 利于正确决策的属性，变得尤为困难。
文献[3]考虑到系统信息的动态波动，将模糊理论与粒 度模型结合，对数据采取融合处理；文献[4 ]考虑到多论域对 象增量，设计了多粒度约简；文献[5]考虑到数据的散布特 性，利用粗糙集推导出决策属性的相似集；文献[6]结合不一 致性与正域分析，实现了动态非一致系统的属性约简；文献[7]基于邻域粗糙集对邻域信息的分析，实现了动态非确定 信息系统的属性约简。可以看出，现有研究的手段主要集中 在粗糙集、邻域分析，以及信息粒等方面。基于现有研究，同时考虑到启发算法的关联性，本文针对混合决策系统，提出 一种启发式增量属性约简方法，用以克服系统中数据动态变 化对属性约简的影响，优化混合决策系统属性约简的精度与 效率。
2混合决策系统邻域差异性分析
由于混合系统主要由论域和属性两部分构成，因此它的 数学模型一般表示为财/5=(/)，4)。/)=14,4,"<|代表论域集合，4 = 1ai,a2，…a…|代表属性集合。如果模型4中包含系统类属性，即4= |a, ,a2，…，a…，ci格式时，可以将系 统数学模型进一步描述成A/C/S= (U C),C= |c丨代表决 策属性集合。此时，对应的系统就是混合决策系统。假定属 性4的任意子集4'，考虑到其混合特征，将其描述为符号与 数值类型的混合关系1 =炙+\，同时设定两种属性的交集 为非空，于是，任意子集/!'对应邻域关系表示如下：\(4’）= I(»，y)e D x D|(Va=a(y))八4 (x,y)^r|(1)其中，r表示子集/T的邻域半径p和y表示系统中的不 同论域对象；是计算％和y距离。根据式（1)可以 得到邻域之间互为对称，经过推导得到邻域关系的重叠如下 D/N r(A') = |r A.(x x),r A.{x2),■■■|
(2)
r* (x) = \y s D\ (x,y)e N r(A')\
其中,/■,.(*)是映射范围内论域对象z所对应的邻域 类。通过对混合决策系统邻域关系的推导，将属性子集/!'的邻域差异性描述如下
n
0{A')= - ^ |^.(«,) (3)
/=!
假定决策系统中为单一信息，即仅包含一种类型属性，此时差异关系等价于无差异关系，利用粗糙理论可以求出无 差异关系，于是子集，邻域差异性可以描述如下
0{A')=n2 -X\D/6(A')12
«'= I
)= ^D^D\y a e A' ,a(x)=a(y)l
(4)其中，<4')代表子集.4'基于粗糙理论的邻域无差异关系。由于系统的整体差异性是邻域差异性的特殊情况，因此，根 据邻域差异性能够对混合决策系统中的数据进行分辨。在 单一信息基础上进行扩展，对于不同类型属性义和1混合 情况，利用其邻域重叠推导出它们之间相对差异性如下
〇a M^= X1^(^)r\r Ad{x{)(5)
i = 1 i = 1
假定u,]e表示任意论域对象与c构成的决策类，当属 性子集符合水条件时，C与间的相对差异计
算如下
0A-(C)-0B.(C)=^ ( I-rB(Xi)|)-
i=l
n
S(丨（r“A)-r“、））n[尤i]C I)(6)
i=l
依据前述分析，在系统属性增长的过程中，差异性式保 持单调非增长状态。由此，通过差异性能够实现属性约简。但是，这种处理方式无法很好的应用于动态变化系统的属性 约简。因此，在前述分析基础上，本文设计了启发式约简算法。
noteexpress3启发式增量属性约简算法
针对混合决策系统中的论域对象动态波动，这里采用条 件熵进行分析。当任意论域对象^与属性集/I相应的邻域 是q(^)，该对象相对_4信息熵表示如下
W)= “(1-^^)(7)其中，a表示调节系数，它是根据论域对象的相对差异计算 而来，公式如下
a=1I(8) A/l,U，y)表示*和y在属性集合4中的差异。结合信 息熵计算出决策类，得到C与4的条件熵如下
E I(C\a)=I f f U)丨(9)
假定u是论域集中新加入的对象，无论原来D中是否含 有u，当它满足条件且/T内邻域仅为自身，对应邻 域表示为,k(u)决策类表示为U]e，该过程中对集合4'邻 域没有影响，条件熵更新方式描述如下
£〇duui(cu，)= (\l D D\l\y E l(c l A，)(10)当新加人对象的邻域不仅仅包含自身时，考虑到精度改
—252—
变，前后两次的邻域之间满足关系=6,(A)U iul，因此引发如下关系
〜⑷_r c U.)= u UI-(li)进而得到此时条件熵的更新公式为
r〇uUI(C|r) = (l〇[+l);( |P|2g°(C|/t，) +
丨r r(M) _ [w]c I)(12)丫 C/l情况下，当存在邻域关系，对应的关系矩阵可
以描述为<4, = (%)丨D|x丨Z)丨，％的取值规则如下
r l,(^,x)e m r i A')
=\(13)
l〇，(U;)* mr(y4')
也就是当论域对象存在邻域关系时，矩阵元素为1，否则 为〇。根据该公式得到的关系矩阵，符合自反和对称，这样一 来，对于子集，，f O I U C，它们的邻域关系可以描述为M4. =(爪^)丨D|x丨D I和似B" = (m(/.)丨D|x丨D丨〇关系矩阵的八和V 、V f 1u i u i■■a、
计算如下
M r A Mff.= (v^)\〇^ \D\*V i j=|
[l,m。：=1 且=1
=0
(14)
L〇,^y:=0 且M r V Mg.={v^)=|
1"1,f l l j j::1且<=1
L0,^y:=〇且肌：=0
(15)
单纯利用邻域依赖虽然有利于处理样本的分布不均，但 是很难获得良好的属性评估，这里引人粒度模型进行优化。将论域对象^的，邻域采用粒度重新描述
(16)
通过式（16)能够把邻域关系中的所有对象采取细化分 析。当G(4')的值增加时，代表所包含的论域对象邻域类在 减小。对于不同的邻域范围~ &0，从邻域关系分析可知，在A/T(u〇矣〜成立时，A/T(;c，;k)矣r2 —定成立，进而 推导出邻域范围「，的粒度一定不小于Q的粒度，即0(4')备c q(/r)。对于不同属性子集/t’G B'e/l，从邻域关系分析 可知，在矣r成立时，A/l'(*,y)•—定成立，进而推导出1 -丨巧炉彡1 于是得到子集，粒度不大于子B’集粒度，即C(4')<G(B')。结合粒度表示后，决 策属性C的度量表示如下
\U N,(lxi c) |
M A C)= G(A')•lcl|〇|—（17)
I i>r(M c)I
其中，iel丨〇丨—项表示邻域依赖性。该项体现了决策与条件的密切程度，有利于启发计算。于是，这里采用 (C)当做启发函数，用于启发属性约简。启发过程中，需要 满足如下约束条件
r M y{C)= M A C)…、
l v* e A',M a..^(C)<M A C)
约束中的第一个等式用于限定约简后要与约简前具有 相同邻域决策度量。第二个不等式用于限定约简后的冗余 特性，为子集<4'内包含属性的必要条件。同时，考虑到属性 约简的效率，应该尽可能降低距离求解的次数。为此，子集 小和所包含元素之前的关系需要满足A/,. = A M lal。由于
Vae^'
决策主要体现了大部分粒度类型，粒计算时可能会受其分布 影响，因此这里考虑了条件与决策间的关联。条件属性，与 决策属性C之间的关联度量描述如下
\J M a,V M c
MrA.(C)= 1 - —|-f l-p—〇9)当，=</>，则心=(1) |D|X m，此时不管决策矩阵A/c 的取值如何,A^VA^M l)丨fl|x丨01始终成立，从而导致Mr,.
(C) =0。这表明在<4'=</>的情况下，属性/T对决策没有影 响，它们之间不存在关联。而当A/,.= M c= 1)丨D |x丨D丨，则有 V M C= 1) |/>|x |d|，从而給r(c) = 1 - 丁
此时表明一定能够在系统属性/l中搜索出某子集，使得和决策之间的关联取值最髙为1 - 令其决策效果和C较为接近。属性约简过程中，单一属性对子集决策性能的影响采 用如下方式评价
W(a,A',C)= Wr,.u|ol(C)- MrA,(C)(20)关联度量计算具有单调性，能够清晰体现出新增属性对 4和C的影响。这样，通过属性之间的关联，以及粒度模型 的单调，求解出条件和决策共同约束下的邻域关系。再根据 决策属性C的度量作为启发，直至单一属性对子集决策性能 不再有影响，完成属性约简。整体算法对应的处理复杂度可 以表示如下
f f = 〇(|C||f l M|C h l)|D|+〜 + (|C|-e)|D|)
(21)其中,e表示计算过程中条件属性的数量。
4仿真与结果分析
仿真选择UCI数据集作为混合决策系统的数据源，这里 从中抽取了 5组数据集，关于它们所含属性与决策的具体描 述如表1所示。其中的T i Ch d a t a2000包含了 5822条客户记 录，在五种实验数据集中，它所包含的数据量与属性都是最 多的，但是与German —样，其决策是最少的。S t u d e n t P e r f o r-mance中包含了学生成绩、学科，以及与学校联系的一些属性，它包含的决策是最多的;German包含了与信誉有关的信 息;Zoo包含了与动物关联的信息，一共由16组属性构成;
—253 —
数据集1数据集2数据集3数据集4数据集5
图1约简长度结果比较
■本文方法 口文献丨8]方法口文献[9]方法
数据集1
数据集2
数据集3
数据集4
炫苦哥数据集5
图2约简精度结果比较
从分类精度可以看出，不同数据集由于属性、决策、数据 规模等原因，会对方法的约简精度产生一定的影响，其中数 据集最为复杂，对约简精度性能的影响也最大。但是无论在 哪种数据集下，本文方法的约简结果都能获得最好的分类精 度。在五种实验数据集中的平均分类精度为76. 518%，比文 献[8]和文献[9]方法分别高出了 5. 414%、1. 944%。
除了约简长度和约简精度以外，约简效率也是衡量属性
约简长度的结果体现了方法约简后属性的冗余性能，冗 余性越低越好，但同时也要考虑约简的精度。为此，将各方 法在不同数据集上得到的约简结果，在分类器中进行分类， 从而得到约简精度的对比，结果如图2所示。
约简的重要指标。为此，本文通过改变混合决策系统中数据 量的大小，来得到约简方法的耗时情况。实验过程中，把各
数据集中论域平均分割成5段，并采取依次增加的方式改变 数据量，得到各方法约简时间结果如表2 ~表4所示，其中约 简时间的单位为S。
由于五种实验数据集的大小不同，每一段增加的数据量 存在很大差异，所以导致每一段增加的约简时间差异很大， 但是在不同数据集中的变化趋势是大体一致的，随着论域规 模的增加，各方法的约简时间随之增加。从数据可以看出， 本文方法的约简时间增速明显小于其它方法，而文献[9]的 约简时间增长速度越来越大。另外，无论在哪种数据集中， 同样的论域规模下，本文方法的约简时间最短，表明约简效 率最髙。该现象出现的原因是由于本文方法采用启发式计 算，在每一轮迭代更新的时候获取的都是局部最佳属性，并 且冗余性较低，每一轮迭代需要处理的数据量也较少。
表2
本文方法约简时间结果
数据集
12345Tichdata 2000 2.203 2.8423. 424 3. 658 3.803StudentPerformance
0.2850.4560.5210.5890.573German 0. 4350.7030.7890.8990.983ZO O 0.0510. 0870. 0900. 1130. 124Flag
0. 093
0. 154
0. 164
0.201
0. 239
表3
文献[8]方法约简时间结果
数据集
12345Tichdata 2000 2.936 4.028 4.962 6. 1277. 429StudentPerformance
0.2930.4740. 5920.6690. 804German 0. 5040.7120.883 1.028 1.346ZO O 0.0600.0870. 1080. 1270. 164Flag
0. 113
0. 193
0. 228
0.274
0.359
表4
文献[9]方法约简时间结果
数据集
12345Tichdata 2000 3.383 5. 3297.96310. 88414. 552StudentPerformance
0.3820.6810.788 1.029 1.347German
0.5670. 9941. 394 1.838 2.395ZO O 0. 0620. 1120. 1310. 1730.224Flag
0. 139
0. 208
0. 286
0.397
0.485
5结束语
针对混合决策系统，本文提出了一种启发式增量属性约
简方法。基于论域、条件和决策建立了系统邻域关系模型, 将系统信息差异转化为相对差异。并且引
入条件熵求解相 对差异，消除论域波动的影响，同时又引人粒度模型优化邻 域依赖的缺陷，利用决策属性度量的启发性，以及约简前后 邻域和冗余性约束，经过迭代完成新增属性的约简。仿真结
Flag 包含了与宗教关联的信息。表1
实验数据集描述
数据集西南宽频
属性数量
决策数量
样本数量
Tichdata 20008625822StudentPerforman
3317649German
2121000zoo
177101Flag
29
8
194
实验过程中，采用文献[8]和文献[9]中的约简方法，分 别从属性约简长度、分类精度，以及约简时间三个方面进行 性能比较。
比例电磁铁在五种数据集中，分别采用不同方法得到各自的属性约 简长度，结果如图1所示。从约简结果可以看出，在每一类 实验数据集中，显然本文方法的约简长度更短一些，约简后 的属性冗余度更小。
30
， 0 口本文方法25 fl ||
■：*；献间方法20
1 1
□文献[9!方法
5 0 5
8
0 Q Q
o 86
<4(2—254
—
果表明，本文方法对于混合决策系统具有良好的属性约简长
度和约简精度，并且显著提高了属性约简效率。
参考文献：
[1 ] Jing Y, Li T, Fujita H, et al. An incremental attribute reduction
method for dynamic data mining [ J ]. Information Sciences, 2018,
465：202 -218.
[2] Jing Y G, Li T, Huang J, et al. A group incremental reduction al
gorithm with varying data values[ J] . International Journal of Intel
ligent Systems, 2017,32(9) ：900 -925.
[3] Huang Y, Li T, Luo C, Fujita H, et al. Dynamic Fusion of Multi
-source Interval - valued Data by Fuzzy Granulation [ J ]. IEEE
Transactions on Fuzzy Systems, 2018: 1-15.
[4] Jing Y G, Li T R, Fujita H, Yu Z, Wang B. An incremental at
tribute reduction approach based on knowledge granularity with a
multi -granulation view [ J ]. Information Sciences, 2017,411
(10)：23 -38.
[5] Li S Y, Hong Z Y, Li T R. Efficient Composing Rough Approxi
mations for Distributed Data [ J ]. Knowledge -Based Systems,
2019, 182.
(上接第246页）
[5] 张连文，郭海鹏.贝叶斯网引论[M].北京：科学出版
社，2006.
[6]肖秦琨，高蒿.贝叶斯网络在智能信息处理中的应用[M].北
京：国防工业出版社，2012.
[7] Chickering D M. Learning Bayesian networks is NP -complete
[J].Networks, 1996,112(2)：121-130.
[8] Cooper B G F, Hersovits E. A Bayesian Method for the Induction
of Probabilistic Networks from D ata[J]. Machine Learning, 1992,
9(4)：309 -347.
[9 ] Tsamardinos I, Brown L E, Aliferis C F. The Max - min Hill -
climbing Bayesian Network Structure Learning Algorithm [ J ]. Ma
chine Learning, 2006,65(1) ：31 -78.
[10] Saoussen A, Salma J, Yassine B A. Particle swarm optimization
based method for bayesian network structure learning [ R ]. Pro
ceedings of 2013 5th International Conference on Modeling, Simu
lation and Applied Optimization. Hammamet, Tunisia ：IEEE,
2013. 1-6.
[11]刘浩然，孙美婷，李雷.基于蚁节点寻优的贝叶斯网络结构
算法研究[J].仪器仪表报，2017,38(1):143-150.
[12]魏中强，徐宏喆，李文.基于条件互信息和概率突跳机制的贝
叶斯网络结构学习算法[J].计算机科学，2015,42(03) :214[6] Xie X J, Qin X L. A novel incremental attribute reduction ap
proach for dynamic incomplete decision systems [ J ]. International
Journal of Approximate Reasoning, 2018,93：443 -462.
[7] Chen Y M, Xue Y, Ma Y, et al. Measures of uncertainty for
neighborhood rough sets [ J ] . Knowledge Based Systems, 2017,
120(C)：226-235.
[8]高阳，刘遵仁，纪俊.基于矩阵保留策略的邻域粗糙集属性约
简算法[J].计算机应用研究，2019,36(12) :3570-3573.
[9]李兵洋，肖健梅，王锡淮.基于多目标邻域差分进化和模糊粗
糙集的属性约简算法[J].控制与决策，2019,34 (05): 947
[作者简介]
肖斌（1978 -)，男（汉族），重庆人，硕士，副教
授，研究方向：数据翻。
孙乾智（1995 -)，男（汉族），吉林四平人，硕士生
在读，職純：?&据挖掘。
Zhao J, Zhou Y, Zhang X, et al. Part Mutual Information for
Quantifying Direct Associations in Networks [ J ] • Proceedings of
the National Academy of Sciences, 2016,113(18) ：5130 -5135. [14 ] Schreiber T. Measuring Information Transfer [ J ]. Physical Re
view Letters, 2000,85(2) ：461 -464.
[15 ] Stom R, Price K. Differential Evolution - A Simple and Efficient
Heuristic for Global Optimization over Continuous Spaces [ J ].
Journal of Global Optimization. 1997 ,(11) ：341 -359.
[16]何德琳，程勇.贝叶斯网络评分准则对MMHC算法学习效果
的影响[J].西南科技大学学报，2008，（2):56-61.
[17]邸若海，髙晓光，郭志高.基于改进BIC评分的贝叶斯网络结
构学习[J].系统工程与电子技术，2017,39(2) :437 -444. [18]张平.基于人工蜂算法的贝叶斯网络结构学习研究[D].
西安电子科技大学，2014.
[作者简介]
牛艳飞（1995 -)，男（汉族），河北省保定市人，硕
士研究生，主要研究领域为数据挖掘、故障诊断。
马洁（1965 -)，女（汉族），辽宁省庄河市人，教
授，硕士研究生导师，主要研究领域为数据驱动的
故障诊断与预测。
[13]
—255
—
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议