基于证据理论刻画多粒度覆盖粗糙集的数值属性

2016-09-27 06:34车晓雅李磊军米据生
智能系统学报 2016年4期
关键词:论域粗糙集粒度

车晓雅,李磊军,2,米据生,2

(1.河北师范大学 数学与信息科学学院,河北 石家庄 050024; 2.河北省计算数学与应用重点实验室,河北 石家庄 050024)



基于证据理论刻画多粒度覆盖粗糙集的数值属性

车晓雅1,李磊军1,2,米据生1,2

(1.河北师范大学 数学与信息科学学院,河北 石家庄 050024; 2.河北省计算数学与应用重点实验室,河北 石家庄 050024)

在经典多粒度粗糙集模型的基础上,基于论域中对象的极大描述和极小描述,定义了4种应用更为广泛的悲观多粒度覆盖粗糙集模型。然后通过集合的交、并运算与关系划分函数,构造了对象关于覆盖族的单粒度的多元覆盖及单粒度划分。在此基础上,基于证据理论,探讨了4种悲观多粒度覆盖粗糙集的上、下近似与信任函数和似然函数之间关系,并描述了该模型所具备的相关数值属性。对比分析表明悲观多粒度覆盖粗糙集模型既具备经典多粒度粗糙集模型能够融合多源信息的优势,又克服了其应用范围狭窄的缺点。实例分析验证了所提模型的有效性。

粗糙集理论;覆盖;粒度;证据理论;近似;特性描述

中文引用格式:车晓雅,李磊军,米据生. 基于证据理论刻画多粒度覆盖粗糙集的数值属性[J]. 智能系统学报, 2016, 11(4): 481-486.

英文引用格式:CHE Xiaoya, LI Leijun, MI Jusheng. Evidence-theory-based numerical characterization of multi-granulation covering rough sets[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 481-486.

粗糙集理论由Pawlak[1]于1982年提出,是一种有效处理模糊和不确定性知识的数学工具,其在机器学习、模式识别、决策分析和数据挖掘等领域得到广泛应用[2-5]。经典粗糙集理论基于等价关系定义集合的上、下近似,然而随着现实世界中的数据在结构和形式上日益复杂化和多样化,经典粗糙集有时不再能满足实际问题的处理需求。为此众多学者从不同角度对经典粗糙集模型进行了扩展[5-8],提出了覆盖粗糙集、多粒度粗糙集、变精度粗糙集、概率粗糙集、模糊粗糙集等。其中,覆盖粗糙集是将经典粗糙集中的划分推广成更一般的覆盖,增强了其处理数据的能力[7,9]。

从粒计算的角度来看,Pawlak粗糙集及推广形式都是基于单一二元关系,均可被称做单粒度粗糙集。然而,在许多实际应用中,需要由多个二元关系诱导出的多粒度结构对目标概念进行刻画。为此,钱宇华等[8,10]提出了基于全域中多个等价关系的经典多粒度粗糙集模型。苗夺谦等[11]在覆盖近似空间中提出4种乐观多粒度覆盖粗糙集模型,其中集合的第一、二型近似分别基于论域中对象极小描述的交和并,集合的第三、四型近似分别基于论域中对象极大描述的交和并。

另一方面,Dempster-Shafer(DS)证据理论产生自20世纪60年代。Dempster[12]提出了集值映射的概念,并定义了上、下概率。 随后, Shafer[13]用信度函数对上、下概率重新进行诠释, 创立“证据的数学理论”。 Dempster还定义了著名的Dempster证据组合规则,该理论中的基本概念是信度函数,包括信任函数和似然函数,并以此来度量知识的不确定性。与粗糙集理论相类似,证据理论也是一种处理不确定性的有力工具[14-16]。许多专家对粗糙集和证据理论之间的关系进行了研究和推广。姚一豫[17]指出可以用信任函数和似然函数对粗糙集中的上、下近似算子进行解读;吴伟志等[16]将信任结构与近似空间相结合,从证据理论的角度研究Pawlak粗糙集的知识约简;陈德刚等[18]在统一框架下对若干覆盖近似算子进行分类,基于粒和证据理论对这些覆盖粗糙近似算子进行度量,并且用信任函数和似然函数对邻域覆盖粗糙集中上、下近似算子进行了度量,进而建立了上述函数与邻域信息系统属性约简之间的关系[19]。

将证据理论与多粒度粗糙集模型相结合是目前的研究热点之一[20-21],谭安辉[22]基于证据理论刻画了不完备信息系统中多粒度粗糙集的数值属性,指出只有悲观多粒度粗糙集的数值属性可以由信任结构刻画,并构建了一种多粒度粗糙集的属性约简算法;林国平[14]结合证据理论和多粒度粗糙集,提出一种新的融合多源信息的方法。然而,上述研究都没有考虑过如何构建多粒度覆盖粗糙集的信任结构以及如何用证据理论刻画多粒度覆盖粗糙集的数值属性。基于上述启发,本文首先在苗夺谦等[11]提出的4种乐观多粒度覆盖粗糙集模型的基础上定义4种悲观多粒度覆盖粗糙集模型,然后基于证据理论给出多粒度覆盖粗糙集的信任结构。通过集合的交运算和关系划分函数建立多粒度覆盖与单粒度划分之间的关系,进而建立了多粒度覆盖粗糙集和证据理论之间联系。

1 相关概念

1.1Pawlak 粗糙集相关概念

∀B⊆C决定一个二元不可辨识关系[1]RB,定义为

1.2覆盖粗糙集相关概念

1.3多粒度粗糙集相关概念

下面简要给出多粒度粗糙集的两种模型,即乐观多粒度粗糙集和悲观多粒度粗糙集。

式中~X=U-X。

式中~X=U-X。

2.4证据理论相关概念

信任函数满足下列性质:

2 多粒度覆盖粗糙集(MGCRS)

本节选取苗夺谦等[11]提出的4种乐观多粒度覆盖粗糙集模型。上述模型基于论域中极小描述或极大描述的交或并定义。

谭安辉等[22]指出,在信息系统中,集合的悲观多粒度近似可以由信度函数刻画,但是集合的乐观多粒度近似一般不具备这种特性。因而本文首先基于苗夺谦等[11]提出的4种乐观多粒度覆盖粗糙集模型定义悲观多粒度覆盖粗糙集模型。

x的极大描述包含近似空间中所有与x相关的对象,当讨论近似空间U,C中集合近似的问题时,极大描述可以提供一个详细且综合的对于x的概括。

显然,如果C是U上的一族划分,上述4种多粒度覆盖粗糙集模型将退化为经典悲观多粒度粗糙集模型。因此,上述4种模型是对经典多粒度粗糙集模型的推广,并且也是粗糙集模型和覆盖粗糙集模型的推广。

3 MGCRS与证据理论之间联系

∀X⊆U,x∈U,X在上述4种悲观多粒度覆盖粗糙集模型中上、下近似的定义分别基于论域中x极小描述或极大描述的交或并所得x的相关元。因为X定义于多粒度环境中,所以无论x的极小描述还是x的极大描述均同时与覆盖C1,C2,…,Cm相关。即 ∀j∈{1,2,3,4}如果集合{(ij(x))i=1,2,…,m}中所有元均为X子集,则x属于,如果至少存在一个与X相交不为空,则x属于。鉴于此, ∀x∈U,本文对集族取并集后得是论域U上一个单粒度覆盖,从而悲观多粒度覆盖粗糙集转化为单粒度覆盖粗糙集。进一步,定理1借助关系划分函数,将覆盖与划分建立联系,将覆盖粗糙集转化为经典粗糙集,进而在定理2中得出证据理论与多粒度悲观覆盖粗糙集之间联系。

证明∀j=1,2,3,4

其中,j=1,2,3,4代表用相应信度函数分别刻画4种多粒度覆盖粗糙集的近似。

下面用例子进一步解释其具体含义。

表1 一个关于房屋评价的信息系统

由属性集A诱导出的一族覆盖C={Ci,i=1,2,…,4}和等价关系R={Ri,i=1,2,…,4}及由决策集B诱导出覆盖的C5,如下:C1={{x1,x2,x3},{x1,x2,x3,x4,x5,x6},{x6}}, C2={{x1,x3,x6},{x2,x3,x6},{x4,x5}},C3={{x1,x2,x6},{x2,x3,x5},{x2,x3,x4,x6}},C4={{x1,x2},{x2,x3},{x3,x4,x5,x6}},C5={{x1,x2,x6},{x1,x2,x3,x4},{x2,x3,x5,x6}},R1= {{x1,x2,x3},{x4,x5},{x6}},R2={{x1},{x2},{x3,x6},{x4,x5}},R3={{x1},{x2},{x3},{x4},{x5},{x6}},R4={{x1},{x2},{x3},{x4,x5,x6}}

是关于覆盖族C的多粒度覆盖。

显然,本文所提出的模型相较于经典多粒度粗糙集模型,更具实际应用价值。

4 结论

经过上述讨论,本文得出以下结论:

1)通过对现有多粒度覆盖粗糙集模型进行分析,构造了4种悲观多粒度覆盖粗糙集模型,以使其能够与证据理论更好地结合;

2)基于集合的交、并运算和关系划分函数,实现了悲观多粒度覆盖粗糙集到单粒度多元覆盖粗糙集再到单粒度经典粗糙集的转化,进而实现简化上述4种模型的目的;

3)结合证据理论,刻画了上述模型的近似及其不确定性。

在后续研究中,可以进一步给出基于信任函数和似然函数的多粒度覆盖粗糙集属性约简算法。

[1]PALAWK Z. Rough set[J]. International journal of computer & information sciences, 1982, 11(5): 341-356.

[2]CHEN Degang, KWONG S, HE Qiang, et al. Geometrical interpretation and applications of membership functions with fuzzy rough sets[J]. Fuzzy sets and systems, 2012, 193: 122-135.

[3]LIANG Jiye, CHIN K S, Dang Chuangyin, et al. A new method for measuring uncertainty and fuzziness in rough set theory[J]. International journal of general systems, 2002, 31(4): 331-342.

[4]LIANG Jiye, WANG Feng, DANG Chaungyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE transactions on knowledge and data engineering, 2014, 26(2): 294-308.

[5]TAN Anhui, LI Jinjin, LIN Guoping. Extended results on the relationship between information systems[J]. Information sciences, 2015, 290: 156-173.

[6]BONIKOWSKI Z, BRYNIARSKI E, WYBRANIEC-SKARDOWSKA U. Extensions and intentions in the rough set theory[J]. Information sciences, 1998, 107(1/2/3/4): 149-167.

[7]FENG Tao, MI Jusheng, WU Weizhi. Covering-based generalized rough fuzzy sets[M]//WANG Guoying, PETERS J F, SKOWRON A, et al. Rough Sets and Knowledge Technology. Berlin Heidelberg: Springer, 2006: 208-215.

[8]QIAN Y H, LIANG J Y. Rough set method based on multi-granulations[C]//Proceedings of the 5th IEEE International Conference on Cognitive Informatics. Beijing: IEEE, 2006: 297-304.

[9]徐伟华, 刘士虎, 张文修. 一般二元关系下信息系统知识的粒度描述[J]. 计算机工程与应用, 2011, 47(18): 40-44.

XU Weihua, LIU Shihu, ZHANG Wenxiu. Granularity representation of knowledge in information system based on general binary-relation[J]. Computer engineering and applications, 2011, 47(18): 40-44.

[10]QIAN Yuhua, LIANG Jiye, YAO Yiyu, et al. MGRS: a multi-granulation rough set[J]. Information sciences, 2010, 180(6): 949-970.

[11]LIU Caihui, MIAO Duoqian, QIAN Jin. On multi-granulation covering rough sets[J]. International journal of approximate reasoning, 2014, 55(6): 1404-1418.

[12]DEMPSTER A P. Upper and lower probability inferences based on a sample from a finite univariate population[J]. Biometrika, 1967, 54(3/4): 515-528.

[13]SHAFER G. A mathematical theory of evidence[J]. Technometrics, 1978, 20(1): 242.

[14]LIN Guoping, LIANG Jiye, QIAN Yuhua. An information fusion approach by combining multigranulation rough sets and evidence theory[J]. Information sciences, 2015, 314: 184-199.

[15]林国平. 覆盖广义粗糙集与信任函数[J]. 漳州师范学院学报: 自然科学版, 2010(2): 1-4.

LIN Guoping. Connections between covering generization rough set and dempster-shafer theory of evidence[J]. Journal of Zhangzhou normal university: natural science, 2010(2): 1-4.

[16]WU Weizhi, MI Jushneg. Knowledge reduction in incomplete information systems based on dempster-shafer theory of evidence[M]//WANG Guoying, PETERS J F, SKOWRON A, et al. Rough Sets and Knowledge Technology. Berlin Heidelberg: Springer, 2006: 254-261.

[17]YAO Y Y, LINGRAS P J. Interpretations of belief functions in the theory of rough sets[J]. Information sciences, 1998, 104(1/2): 81-106.

[18]CHEN Degang, ZHANG Xiaoxia, LI Wanlu. On measurements of covering rough sets based on granules and evidence theory[J]. Information sciences, 2015, 317: 329-348.

[19]CHEN Degang, LI Wanlu, ZHANG Xiao, et al. Evidence-theory-based numerical algorithms of attribute reduction with neighborhood-covering rough sets[J]. International journal of approximate reasoning, 2014, 55(3): 908-923.

[20]WU Weizhi, LEUNG Y, ZHANG Wenxiu. Connections between rough set theory and Dempster-Shafer theory of evidence[J]. International journal of general systems, 2002, 31(4): 405-430.

[21] 吴伟志, 米据生, 李同军. 无限论域中的粗糙近似空间与信任结构[J]. 计算机研究与发展, 2012, 49(2): 327-336.

WU Weizhi, MI Jusheng, LI Tongjun. Rough approximation spaces and belief structures in infinite universes of discourse[J]. Journal of computer research and development, 2012, 49(2): 327-336.

[22]TAN Anhui, WU Weizhi, LI Jinjin, et al. Evidence-theory-based numerical characterization of multi-granulation rough sets in incomplete information systems[J]. Fuzzy sets and systems, 2016, 294: 18-35.

[23]ZAKOWSKI B W. Approximations in the space (u, π)[J]. Demonstratio mathematica, 1983, 16(3): 761-769.

车晓雅,女, 1991年生, 硕士研究生, 主要研究方向为人工智能的数学基础。

李磊军,男,1985年生,讲师,博士,主要研究方向为粗糙集,概念格,粒计算与集成学习等,已发表学术论文10余篇,其中被SCI检索5篇。

Evidence-theory-based numerical characterization of multi-granulation covering rough sets

CHE Xiaoya1, LI Leijun1,2, MI Jusheng1,2

(1.College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China; 2. Hebei Key Laboratory of Computational Mathematics and Applications, Shijiazhuang 050024, China)

Considering classical multi-granulation rough sets and using the maximal and minimal descriptors of objects in a given universe, this paper proposes four pessimistic multi-granulation covering rough set models, suitable for extensive application. Based on set union and portion functions, the notion of multi-granularity covering connected to a number of coverings and a single granularity partition in the domain are defined. On this basis, belief and plausibility functions from evidence theory are employed to define the relationship between the upper and lower approximations, the belief function, and the likelihood function, and to characterize the set approximations in the four models. Compared with classical multi-granulation rough sets, the pessimistic multi-granulation covering rough set models not only have distinct advantages and combine multi-source information, but also avoid the shortcomings of a narrow application range. Finally, a real example is used to demonstrate the effectiveness of the presented models.

rough sets theory; covering; granulation; evidence theory; approximation; characterization

10.11992/tis.201606011

网络出版地址:http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.006.html

2016-06-03. 网络出版日期:2016-08-08.

国家自然科学基金项目(61573127,61502144,61300121,6147 2463);河北省自然科学基金项目(A2014205157);河北省高校创新团队领军人才培育计划项目(LJRC022);河北省高校自然科学基金项目(QN2016133);河北师范大学博士科学基金项目(L2015B01);河北省教育厅研究生创新项目(sj2015001).

车晓雅.E-mail:chexiaoya@163.com.

TP18

A

1673-4785(2016)04-0481-06

猜你喜欢
论域粗糙集粒度
粗糙集与包络分析下舰船运行数据聚类算法
基于Simulink变论域算法仿真技术研究
粉末粒度对纯Re坯显微组织与力学性能的影响
着舰指挥官非对称变论域模糊引导技术
基于Pawlak粗糙集模型的集合运算关系
基于变论域模糊控制的Taylor逼近型内模PID算法
动态更新属性值变化时的最优粒度
大众文化视域下流行音乐的论域、对象与定义
双粒度混合烧结矿颗粒填充床压降实验
一种基于粗糙集理论的社交网络潜在路径研究