一般决策形式背景的属性约简.pdf
《一般决策形式背景的属性约简.pdf》由会员分享,可在线阅读,更多相关《一般决策形式背景的属性约简.pdf(6页珍藏版)》请在咨信网上搜索。
1、第 56 卷第 1 期郑 州 大 学 学 报(理 学 版)Vol.56 No.12024 年 1 月J.Zhengzhou Univ.(Nat.Sci.Ed.)Jan.2024收稿日期:2022-08-08基金项目:国家自然科学基金项目(61972052)。第一作者:谢业海(1984),男,博士研究生,主要从事形式概念分析、粗糙集研究,E-mail:xieyehai 。一般决策形式背景的属性约简谢业海,高秀巍(北京语言大学 信息科学学院北京 100083)摘要:决策形式背景是形式背景的重要扩展。属性约简是决策形式背景领域研究的热点问题。由现实数据所构建的决策形式背景通常是不一致的,文中面向实际
2、应用,研究一般决策形式背景的广义属性约简方法。定义了一般决策形式背景的广义属性约简,并基于辨识函数给出了计算所有约简的算法。该算法具有良好的通用性,可应用于一致和不一致的决策形式背景。关键词:形式概念分析;决策形式背景;辨识函数;属性约简中图分类号:TP182文献标志码:A文章编号:1671-6841(2024)01-0075-06DOI:10.13705/j.issn.1671-6841.2022232 Attribute Reduction in General Decision Formal ContextsXIE Yehai,GAO Xiuwei(School of Informati
3、on Science,Beijing Language and Culture University,Beijing 100083,China)Abstract:Decision formal contexts were a significant extension of formal contexts and attribute reduction was a hot issue in the field of decision formal contexts.The decision formal contexts formed by the real world data were u
4、sually inconsistent.Oriented on the practical application requirements,the approach of attribute reduction in general decision formal contexts was studied.Furthermore,the definition attribute reduction of general decision formal contexts was proposed.Based on the discernibility function,the cor-resp
5、onding algorithm of finding all the reducts was given.The proposed algorithm had good generality and could be used in the consistent and inconsistent decision formal contexts.Key words:formal concept analysis;decision formal context;discernibility function;attribute reduction0引言1982 年,德国学者 Wille1提出了
6、形式概念分析理论,也被称作概念格理论。形式概念分析理论通过构建一个概念完备格,直观地刻画出概念之间的层次结构,因而成为一种有效的数据处理工具,被广泛应用于信息检索、数据挖掘等领域2-3。面对海量数据,如何去除冗余信息,保留核心信息,降低数据的维度和计算复杂度,对于数据处理来说十分重要,因此属性约简4-5一直受到广泛的关注。概念格的属性约简本质上是在保持概念格某个特性不变的基础上,寻找最小属性集,使约简后的概念格比原概念格更加简洁,因而概念格的属性约简一直都是热点研究问题。Zhang 等6首先提出保持概念格结构不变的约简,即约简后的概念格与原概念格同构,并基于辨识矩阵给出获得所有约简的算法。Qi
7、7对文献6 中的辨识矩阵加以改进,获得了计算效率更高的约简算法。Wu 等8从粒计算的角度定义了概念格的对象粒,并用对象粒去定义形式背景的粒约简,同时给出获得相应约简的方法。许多学者研究粗糙集的属性约简和形式背景的属性约简之间的关系。Wei 等9将形式背景当作一个属性值为 0 和 1 的信息系统,并研究了形式背景属性约简和信息系统绝对约简之间的关系。Liu 等10研究了面向对象的概念格的属性约简与信息系统的属郑 州 大 学 学 报(理 学 版)第 56 卷性约简之间的关系。Li 等11定义了形式背景的不可约简属性类,并用不可约简属性类刻画了形式背景的核心属性集、相对必要属性集和冗余属性集,同时给
8、出了约简的判定定理。Ren 等12研究了三支概念格的属性约简问题,在对象导出三支概念格和属性导出三支概念格中分别定义了 4 种约简,并研究了约简之间的关系,同时给出了其中 7 种约简的计算方法。魏玲等13研究了强协调决策形式背景和弱协调决策形式背景的约简定义和约简方法。决策形式背景的提出,进一步丰富了形式概念分析的理论,得到了学术界的广泛关注。Li 等14面向规则提取,定义了决策形式背景的约简,并给出计算所有约简的算法。在文献8中,Wu 等定义了一致决策形式背景 的粒约简并 给出相应约 简算 法。Wang等15基于辨识矩阵,给出了计算广义一致决策形式背景约简的算法。相对一致决策形式背景而言,不
9、一致决策形式背景在实际应用中更为常见,因此研究一般决策形式背景的属性约简更具有现实意义。基于此,本文给出一般决策形式背景的属性约简的定义,并利用辨识函数给出计算所有约简的算法。该算法可应用于一致决策形式背景和不一致决策形式背景。特别地,文献13中的强协调决策形式背景的约简是我们算法的特例。1形式概念分析的基本定义及性质本节介绍形式概念分析的基础知识,包括形式背景、决策形式背景、概念、概念格的定义及相关性质。定义 11形式背景是一个三元组(U,A,I),U是非空有限对象集,A 是非空有限属性集,I 是 U 和A 之间的二元关系,即 I U A。对于一个形式背景(U,A,I),可在对象集和属性集上
10、定义两个运算16,X U,X=a Ax X,xIa,B A,B=x Ub B,xIb,其中:X表示 X 中所有对象所具有的共同属性的最大集合;B表示具有 B 中所有属性的对象的最大集合。特别地,对于 x X,b B,将 x和 b分别简记为 x和 b,显然有 X=xXx,B=bBb。设(U,A,I)为一个形式背景,对于 B A,令IB=I (U B),则(U,B,IB)也是一个形式背景6。为了区分不同形式背景下的“”运算,我们分别用“A”和“B”表示形式背景(U,A,I)和(U,B,IB)中的“”运算。对于 C B A,容易证明有 CA=CB 8。设(U,A,I)为一个形式背景,其中对象集为U=
11、x1,x2,xm,属性集为 A=a1,a2,an。将(U,A,I)视为一张 m 行 n 列的信息表,其中信息表中元素的值域为 0,1。若信息表中第 i 行第 j列的元素为 1,则表示(xi,aj)I,即对象 xi具有属性 aj,反之则表示(xi,aj)I,即对象 xi不具有属性 aj。若形式背景(U,A,I)对应的信息表的每行每列既有 0 又有 1,则称(U,A,I)是正则的6。本文研究的形式背景在约简前均为正则的。定义 216假设(U,A,I)为形式背景,X U,B A,若 XA=B 且 BA=X,则称二元组(X,B)为形式背景(U,A,I)的概念,称 X 为概念(X,B)的外延,B 为概念
12、(X,B)的内涵。记形式背景(U,A,I)的全体概念为 L(U,A,I),即 L(U,A,I)=(X,B)X U,B A,XA=B,BA=X;记全体概念的外延集为 LU(U,A,I),即LU(U,A,I)=X UB A,(X,B)L(U,A,I)。对于任意(X1,B1),(X2,B2)L(U,A,I),定义 L(U,A,I)上的偏序关系为(X1,B1)(X2,B2)X1 X2B2 B1。若(X1,B1),(X2,B2)L(U,A,I),在 L(U,A,I)上分别定义上、下确界为(X1,B1)(X2,B2)=(X1 X2,(B1 B2)AA),(X1,B1)(X2,B2)=(X1 X2)AA,B
13、1 B2),则 L(U,A,I)为完备格,称之为形式背景(U,A,I)的概念格。性质 1假设(U,A,I)为形式背景,对于 X,X1,X2 U 和 B,B1,B2 A,容易证明有性质1)5)16:1)X1 X2X1A X2A,B1 B2B1AB2A;2)X BAB XA;3)X XAA,B BAA;4)XA=XAAA,BA=BAAA;5)(XAA,XA)L(U,A,I),(BA,BAA)L(U,A,I)。定义 36设(U,A1,I1)和(U,A2,I2)为形式背景,若 LU(U,A2,I2)LU(U,A1,I1),则称 L(U,A1,I1)细于 L(U,A2,I2),记为 L(U,A1,I1)
14、L(U,A2,I2)。67第 1 期谢业海,等:一般决策形式背景的属性约简若 L(U,A1,I1)L(U,A2,I2),那么对于任意(X2,B2)L(U,A2,I2),总存在(X1,B1)L(U,A1,I1)使得 X1=X2。设(U,A,I)为形式背景,B A,那么不难验证有 L(U,A,I)L(U,B,IB)6。定义 4令(U,A,I)和(U,T,J)为形式背景,则称五元组(U,A,I,T,J)为决策形式背景13。其中,A 是条件属性集,T 是决策属性集。若 L(U,A,I)L(U,T,J),则称(U,A,I,T,J)为一致的决策形式背景,反之则称(U,A,I,T,J)为不一致的决策形式背景
15、。定义 4 中的一致决策形式背景即是文献13中定义的强协调决策形式背景。2一般决策形式背景的广义约简对一般决策形式背景,定义一种新的约简,该约简是强协调决策形式背景的约简的扩展。需要指出的是,作为一个特例,用本节提出的约简算法,可获得强协调决策形式背景的所有约简。设(U,A,I,T,J)为决策形式背景,对于 B A,记 VB=LU(U,B,IB)LU(U,T,J),于是VA=LU(U,A,I)LU(U,T,J)。定义 5 令(U,A,I,T,J)为 决策形式 背 景,B A,若 B 满足1)VA=VB,2)对于任意 C B,那么 VC VA,则称 B 为决策形式背景(U,A,I,T,J)的约简
16、。特别地,若(U,A,I,T,J)为一致决策形式背景,那么 VA=LU(U,T,J),则 VA=VB等价于 L(U,B,IB)L(U,T,J)。引理 1假设(U,A,I)为形式背景,则有1)a A,(aA,aAA)L(U,A,I);2)若(X,B)L(U,A,I),X U,那么 X=aBaA;3)X LU(U,A,I)且 X U B A 使X=aBaA。证明 1)对于 a A,根据性质 1 中的 4)有aA=aAAA,那么有(aA,aAA)L(U,A,I)。2)若(X,B)L(U,A,I),X U,那么由定义2 有 X=BA,又 BA=aBaA,所以 X=aBaA。3)“”:假设 X LU(U
17、,A,I)且 X U,也就是 B A,有(X,B)L(U,A,I),那么由 2)有X=aBaA。“”:对于 a A,由 1)有(aA,aAA)L(U,A,I),那么有 aB(aA,aAA)=(aBaA,(aBaAA)AA)L(U,A,I),所以 aBaA LU(U,A,I),在正则形式背景中,显然有 aBaA U,所以令X=aBaA即可得证。定理 1设(U,A,I,T,J)为决策形式背景,对于任意 B A,条件 1)和 2)等价:1)VA=VB;2)对于 X VA且 X U,存在 C B,使得X=CA。证明 1)2):若 VA=VB,对于 X VA且 X U,有 X VB,也就是 C B 使(
18、X,C)L(U,B,IB)。由定义 2 可知有 X=CB,又 CA=CB,所以X=CA。2)1):由 B A,有 L(U,A,I)L(U,B,IB),也 就 是 LU(U,B,IB)LU(U,A,I),所 以VB VA。下面证 VA VB。当 X VA且 X=U 时,显然有 X VB。当 X VA且 X U 时,由 2)可知存在 C B 使得 X=CA,又由 CA=CB可推出 X=CB,由引理 1 中 3)可推出 X LU(U,B,IB),即X VB,所以有 VA VB。综上可得 VA=VB。推论 1 设(U,A,I,T,J)为决 策形式背 景,B A,则 B 是(U,A,I,T,J)的约简,
19、当且仅当 B 是 A 的满足定理 1 中 2)的极小子集。在决策形式背景(U,A,I,T,J)中,对于 X VA且 X U,记(X)=C AX VA,X U,X=CA,min(X)=D (X)C (X),C D,C D。由推论 1 可得计算一般决策形式背景约简的算法。算法 1一般决策形式背景的约简算法输入:一般决策形式背景(U,A,I,T,J)。输出:全部约简。步骤 1计算 VA=LU(U,A,I)LU(U,T,J)。步骤 2对于 X VA且 X U,计算min(X)。步骤 3构造辨识函数 f=XVA,XU(Dmin(X)(dDd)。步骤 4利用吸收率和分配率,将辨识函数由合取范式转换为最小析
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一般 决策 形式 背景 属性
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。