欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

博士论文
当前位置:首页 > 博士论文
基于必然属性分析的粒描述
来源:一起赢论文网     日期:2020-02-15     浏览数:199     【 字体:

 rse when specific granularity principles are not available.Therefore,granuledescription is the foundation and basis of solving complicated problems by granular computing,and any further researches can be beneficial to the understanding and explanation of granules.Asis well-known,the existing study on granule description is mainly based on common attributeanalysis,and the key theoretical tools are formal concept analysis and rough set.Common attributeanalysis characterizes the commonness of a granule by extracting the common attributes possessedby all the objects of the granule.However,an attribute a granule has in the real world,may notonly be the one possessed by all the objects of the granule,but also be the one possessed by partof objects of the granule,or even sometimes the one possessed by an object of the granule.Infact,common attribute analysis emphasizes that the attribute a granule has must be the onepossessed by all the objects of the granule.Different from common attribute analysis,necessaryattribute analysis emphasizes that the attribute a granule has is the one belonging to the granuleonly.In other words,besides the attributes possessed by all the objects of a granule,necessaryattribute analysis of granule description may also involve the attributes possessed by part ofobjects of the granule.Currently,it still lacks of a thorough study on granule description fromthe perspective of necessary attribute analysis.In this paper,this problem is investigated byincorporating the idea of granules from formal concept analysis and the methods of upper andlower approximations from rough set theory.At the beginning,necessary attribute analysis basedgranule description logic is introduced.After that,granule description is studied in formal contextsand their complements,respectively.Specifically,in formal contexts,granules are described withthe necessary attributes they have,and in complement contexts,they are described with thenecessary attributes they do not have.Besides,unary descriptors are defined to express the intentsof concepts of the object-oriented concept lattices of a formal context and its complement,and aunary definable granule is described by one unary descriptor while a unary indefinable granule isdescribed by apair of unary descriptors called as the upper and lower approximation descriptions.And then,in order to use the information from both a formal context and its complement,necessaryattribute analysis based three-way concept lattices are proposed,and binary descriptors aredefined to express the intents of concepts of necessary attribute analysis based three-way conceptlattices.Also,a binary definable granule is described by a binary descriptor while a binaryindefinable granule is described by apair of binary descriptors called as the upper and lowerapproximation descriptions.Finally,three types of approximate description methods are comparedwith each other in terms of description accuracy.The obtained results show that the binary descriptorbased approximate description method is superior to the unary descriptor based approximatedescription method which is superior to those by using the object-oriented concept lattices of aformal context and its complement.Keywords  granular computing;granule description;formal concept analysis;necessary attributeanalysis;rough set;three-way concept lattice1 引 言粒计算(Granular Computing)是一种看待客观事物的世界观和方法论.随着 Zadeh教授对模糊信息粒化思想的逐步完善[1],研究人员对信息粒化的兴趣愈发浓厚.Zadeh教授认为很多领域都存在信息粒的概念,只是在不同领域中它的表现形式会有一定差异.实际上,信 息粒是对 实事物的 一种抽象,信息粒化是人类处理和存储信息的一种具体反映.粒计算通常把复杂问题进行抽象、分解、转化,从而得到若干相对简单的子问题,以实现复杂问题的123072期 智慧来等:基于必然属性分析的粒描述算的前提和基础,它可以看作是问题空间的一个划分过程.在给定粒化准则的情况下,信息粒化能够产生一系列描述问题空间的信息粒.这些粒之间再配备相应的偏序关系就构成多层次的粒结构.粒计算通过不同粒层上粒之间的转换与推理,以及同一粒层上粒之间的相互交互实现复杂问题求解[5-6].粒计算的很多思想在许多领域中得到了应用,如结构化问题求解、结构化信息处理、结构化哲学思维[7-9].从某种意义上,所有采用这一思维方式解决问题的方法都属于粒计算的研究内容.需要指出的是,采用不同的粒化方法,可以得到既有区别又有联系的粒计算模型.在利用粒计算思想求解复杂问题时,依据一定准则划分问题空间,得到问题空间的子集,称为粒.然而,若事先没有给出或者没有明确给出问题空间的划分准则,如何来描述问题空间的子集 ?则称这个问题为粒描述,它是粒计算领域中公认的重要问题之一.实际上,深入研究粒的描述,不仅能加深对粒的理解,并且对回答“为什么有的概念复杂且难以理解,而有的概念则相对简单”这一认知科学中的基本问题有很大帮助[10].广义上,只要是对问题空间子集进行描述的工作都属于粒描述的研究范畴.狭义的粒描述是指给定一个粒,找到描述这个粒的逻辑公式.巧合的是,粗糙集[11]与形式概念分析[12]在同一年被提出.有学者已阐明这两个理论实际上存在诸多互补性[13-16].不仅如此,它们均被认为是一种有效的粒计算方法[17-19].基于粗糙集的粒描述和基于形式概念分析的粒描述本质上是一致的,即依据一定的准则划分论域,得到粒的集合,进而利用近似刻画的方式描述原始划分准则所不能描述的目标概念或论域子集.不同的是基于形式概念分析的方法不仅得到了粒的集合,而且还建立了粒的偏序关系,并赋予每个粒一个特定的属性标签.所以,两者的区别在于基于粗糙集的粒描述是直接给出目标对象集的近似集,而基于形式概念分析的粒描述可以显式地给出目标对象集的属性刻画.另外,考虑到对象与属性之间可以定义 Galois连接,因此这两种描述方式又是紧密联系的.形式概念分析是研究知识表示的一种有效数学工具,它的核心数据结构概念格是对概念及其层次关系的 描 述,在 一 定 程 度 上 是 对 客 观 事 物 的 一种高度简化 的 抽 象 粒 描 述[20].由于该理论便于概念结构的开发 与讨论,在某种意义上,概念格已成为一种外部认知的手段,并在人工智能领域有广泛而成熟的应用基础[21-23].此外,研究人员在形式概念分析中引入粒计算思想,得到了一系列成果,如粒规则获取[24]、粒概念学习[25-26]、充分必要信息粒转化[19,27-28]、粒约简[29-30]、概念粒计算系统构建[31]等.粗糙集是一个处理不确定性的数学工具.运用该理论的特点在于求解问题时无需提供问题空间之外的任何先验知识,其有效性已从许多领域的成功应用中得到证实.目前,基于粗糙集的知识表示与处理是人工智能领域中的热点研究问题之一[17,32-35].粒计算思想在粗糙集中主要体现在粒规则与粒约简等方面[36-37].此外,为了适应多源信息处理,多粒度粗糙集[38]一经提出便受到广泛关注,并扩展到模糊、邻域、覆盖等类型的信息系统[39-42].另外,钱宇华等还提出了局部多粒度粗糙集[43],折延宏和贺晓丽使用多值逻辑方法论述了多粒度粗糙集的内部结构[44].狭义的粒描述已有一些探讨.文献[45]研究了粒的共性属性以及粒的稳定性,提出了基于形式概念分析的粒描述.在该文中,首先将粒分成原子粒,基本粒和复合粒三类;然后根据描述逻辑公式中采用的不同连接符提出了∧-可定义粒、(∧, )-可定义粒以及(∧,∨)-可定义粒,并针对每一种粒分别讨论了粒的描述方法.从目前已开展的研究不难看出,能够被完全描述的粒仅仅只是少数,大量的粒是不能被完全描述的.因此,在该文结尾部分又提出了粒的近似描述问题.文献[46]融合形式概念分析和粗糙集,提出将粗糙可定义粒作为基本粒,利用一对粗糙可定义粒来近似描述粗糙不可定义粒.实际上,在语义上粗糙可定义粒与面向对象概念格中的面向对象概念外延等价.文献[45]基于共性属性讨论了信息粒的描述问题.在实际应用中,基于共性属性的粒描述是十分常见的.例如,为了提升企业的核心竞争力,企业通常需要分析每个员工的特点并挖掘出员工的共性,以便有针对性地展开培训.但是,共性属性分析有时会存在缺陷,比如分析企业下属部门员工具备哪些技能,能够承担哪类任务,这种情况下基于共性属性分析就不能较好地解决问题.详细的讨论见例1.例1. 一个文秘办公室有4个员工,员工熟练掌握 的 技 能 包 括 英 文 写 作、LaTeX 排 版、WPS 排版、新闻报道.每个员 工具体掌 握 的技能如 表 1 所示,其中数字“1”表示员工具有相应列的技能,数字“0”表示员工不具有相应列的技能.4072计  算  机  学  报 2018年室员工技能统计英文写作 LaTeX 排版 WPS排版 新闻报道员工1  1  0  1  0员工2  1  1  0  0员工3  1  0  1  1员工4  0  1  0  0假设对象粒由员工1、2和3共同组成.下面讨论共性属性分析存在的缺陷.显然,使用共性属性分析可以得到员工掌握的共同技能,比如员工1、2和3都熟练掌握了英文写作.但是,该方法并不能得到员工1、2和3还掌握了哪些其他员工(员工1、2和3这个整体之外的员工)所不具有的技能.例如,员工1、2和3除了可以熟练进行英文写作外,这个整体中的某些人(显然可以代表员工1、2和3这个整体)还胜任 WPS排版和新闻报道的工作,这两个技能也是员工1、2和3这个整体所独有的,但是使用共性属性分析无法获得它们.此时,若文秘办公室需要完成对外宣传,就可以将任务(英文写作,WPS 排版和新闻报 道)分 配 给 员 工1、2和3这个整体.显而易见,使用共性属性分析不能完成这个任务的分配.此外,需要指出的是,虽然员工2还掌握了 LaTeX 排版,但是员工4也掌握了LaTeX排版,因此 LaTeX 排版不是员工 1、2 和 3这个整体所掌握的独有技能.上述问题实际上描述了对象群体的必然属性,也就是只属于这个对象群体的属性(显然,基于共性属性分析的粒描述无法胜任此类问题).类似的问题在许多领域都广泛存在.因此,从必然属性分析的角度研究粒描述,是一个与基于共性属性分析的粒描述有着同等研究意义的重要课题.需要指出的是,面向对象概念格是进行必然属性分析的一个有力工具,并已有一些相关的研究成果[47-54].例如,受面向属性概念格启发[48],Yao结合粗糙集与形式概念分析定义了必然属性分析算子,并研究 了 与 共 性 属 性 分 析 算 子 之 间 的 关 系[47,49].Medina研究了概念格、面向对象概念格、面向属性概念格之间的关联[50-51].文献[52]提出了一种快速构造面向对象概念格的算法.此外,Shao等人提出了基于面向对象概念格的属性约简方法[53],Wang和 Zhang进一步阐述了基于面向对象概念格与基于面向属性概念格的两种约简方法之间的联系[54].围绕上述问题,并受面向对象概念格启发,本文研究基于必然属性分析的粒描述.具体地,首先提出基于必然属性的粒描述逻辑;然后给出一元可定义粒、一元描述子、二元可定义粒以及二元描述子,在此基础上讨论一元不可定义粒和二元不可定义粒的近似描述;最后,对相关研究成果作了比较分析,并指出今后需要进一步探讨的若干问题.2 基本概念为了本文内容的完整性以及方便读者阅读,这一节介绍下文中即将涉及到的基本概念.2.1 必然属性与面向对象概念格众所周知,形式背景是形式概念分析中最基本的一个概念.定义1[12]. 一个形式背景 K=(G,M,I)是由两个集合G 和M 以及它们之间的二元关系I 组成.G 的元素称为对象,M 的元素称为属性,(g,m)∈I或gIm 表示对象g 拥有属性m.为了方便,记对象g所拥有的属性构成的集合为g*={m∈M|gIm},拥有属性m 的对象构成的集合为 m*={g∈G|gIm}.定义2[47-48]. 在形式背景 K=(G,M,I)中,设AG,BM.定义A□={m∈M|m*A} (1)B◇={g∈G|g*∩B≠} (2)通常,□称为必然性算子,◇称为可能性算子.A□是 A 的所有必然属性组成的集合,B◇ 是具有必然属性B 的最小对象集.定义3[47]. 在形式背景 K=(G,M,I)中,如果 AG,B M,A=B◇且 B=A□ ,则 称 二 元 组C=(A,B)是一个面向对象概念,A 是面向对象概念C 的外延,B 是面向对象概念C 的内涵.定义4[47]. 设C1=(A1,B1)和C2=(A2,B2)是形式背景 K=(G,M,I)的两个面向对象概念,定义C1C2A1A2B1B2,并称C2是C1的父概念,C1是C2的子概念,称为概念之间的层次序.形式背景 K=(G,M,I)的所有面向对象概念通过层次序构成一个完备格,称为面向对象概念格,记为L(G,M,I).若概念C1C2,且不存在概念C3使得C1C3C2,则称C2是 C1的上近邻,或 C1是C2的下近邻,并分别记为C1C2和C2C1.定义5[47]. 在面向对象概念格L(G,M,I)中,如果一 个 概念具有 形 式 ((g□)◇ ,g□)且g∈G,则称((g□)◇ ,g□)是一个对象诱导的面向对象概念,g是((g□)◇ ,g□)的对象标签;类似地,如果一个概念具有形式(m◇ ,(m◇ )□ )且 m∈M,则称 (m◇,125072期 智慧来等:基于必然属性分析的粒描述版日期:2017-12-20.本课题得到国家自然科学基金(61502150,61562050,61305057,61573173)资助.智慧来,男,1981年生,博士,讲师,中国计算机学会(CCF)会员,主要研究方向为粒计算、形式概念分析、粗糙集.E-mail:zhihuilai@126.com.李金海(通信作者),男,1984年生,博士,教授,博士生导师,主要研究领域为概念格、粗糙集、粒计算.E-mail:jhlixjtu@163.com.基于必然属性分析的粒描述智慧来1)  李金海2),3)1)(河南理工大学计算机科学与技术学院 河南 焦作 454000)2)(昆明理工大学数据科学研究中心 昆明 650500)3)(昆明理工大学理学院 昆明 650500)摘 要 粒计算是在Zadeh教授提出的模糊信息粒化思想的基础上,逐渐发展起来的一个有效处理信息的数学工具.粒计算利用粒化信息的思想解决复杂问题,而在信息粒化的过程中通常都伴随着粒描述.所谓粒描述,是指在没有明确粒化准则的情况下如何描述目标概念或论域子集.因此,粒描述是采用粒计算思维解决复杂问题的前提和基础,进一步研究将有利于粒的理解与解释.众所周知,现有的粒描述主要集中在共性属性分析的基础上开展相关研究,其核心的理论工具是形式概念分析与粗糙集.共性属性分析刻画了粒的共性,即粒中每个对象均拥有的属性.然而,现实中一个粒具有的属性有时不单指粒中所有对象共同拥有的属性,还有可能指粒中部分对象共同拥有的属性,甚至有时只需要粒中存在一个对象拥有该属性即可.实际上,共性属性分析强调的是所有对象共同拥有的属性才是这个粒的属性.与共性属性分析不同,必然属性分析强调的是只属于这个粒的属性才是它的属性.换言之,必然属性分析讨论粒描述时,除了涉及所有对象共同拥有的属性,还可能涉及部分对象共同拥有的属性.目前,从必然属性分析的角度研究粒描述尚未被详细讨论.该文基于形式概念分析中粒的思想和粗糙集理论中上、下近似的方法对这一问题展开研究.首先,介绍了必然属性分析视角下的粒描述逻辑.其次,分别基于形式背景及其补背景研究了粒描述.具体地,利用形式背景描述粒具有的必然属性,利用补背景描述粒不具有的必然属性.此外,定义了一元描述子用来特指形式背景及其补背景的面向对象概念格中的概念内涵,进而通过一个一元描述子刻画一个一元可定义粒,将一对一元描述子作为上、下近似以刻画一个一元不可定义粒.然后,为了同时使用形式背景及其补背景的信息,提出了基于必然属性分析的三支概念格,并定义二元描述子用来特指基于必然属性分析的三支概念格中的概念内涵,进而由一个二元描述子刻画一个二元可定义粒,将一对二元描述子作为上、下近似以刻画一个二元不可定义粒.最后,比较了三种近似描述的精度.有关结论表明基于二元描述子的近似描述方法优于基于一元描述子的近似描述方法,而基于一元描述子的近似描述方法又优于基于形式背景及其补背景的面向对象概念格的方法.关键词 粒计算;粒描述;形式概念分析;必然属性分析;粗糙集;三支概念格中图法分类号 TP18   DOI号 10.11897/SP.J.1016.2018.02702Granule Description Based on Necessary Attribute AnalysisZHI Hui-Lai 1) LI Jin-Hai 2),3)1)(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000)2)(Data Science Research Center,Kunming University of Science and Technology,Kunming 650500)3)(Faculty of Science,Kunming University of Science and Technology,Kunming 650500)Abstract  Granular computing is an effective mathematical tool of dealing with information andcan be considered as an extension of the idea of fuzzy information granularity proposed by professorZadeh.To the best of our knowledge,granular computing solves complicated problems viainformation granularity.It should be pointed out that information granularity is often accompaniedby granule description.The so-called granule description is to describe a target concept or a subset 的 面 向 对 象 概 念,m 是(m◇,(m◇)□ )的属性标签.在不产生歧义的情况下,面向对象概念简称为概念,面向对象概念格简称为概念格.定理1[49]. 在面向对象概念格L(G,M,I)中,任意两个概念(A1,B1),(A2,B2)的下确界和上确界分别定义为(A1,B1)∧(A2,B2)=((A1∩A2)□ ◇,B1∩B2)(3)(A1,B1)∨(A2,B2)=(A1∪A2,(B1∪B2)◇ □)(4)面向对象概念格的构造算法可以参考文献[52],也可以根据 Wille概念格与面向对象概念格算子之间的关系,通过修改 Wille概念格的构造算法得到.2.2 粗糙集为方便起见,下面的定义用等价关系代替划分.定义6[11]. 一个近似空间定义为一个关系系统S=(U,R),其中非空集合U 是论域,R 是U 上等价关系的一个集族.定义7[11]. 设 PR,且 P≠,称 P 中所有等价关系的交集为P 诱导的一个不可区分关系,记作IND(P).进一步,不可区分关系产生的等价类之间满足下列式子:[x]IND(P)= ∩p∈P[x]p(5)定义8[11]. 给定近似空间S=(U,R),称 XU 为U 上的一个概念.形式上,空集也视为一个概念.非空子集 PR 所诱导的不可区分关系IND(P)的所有等价类组成的集合称为基本知识,相应的等价类称为基本概念.定义9[11].  给定近似空间 S=(U,R),子集XU.X 的下近似和上近似分别定义为R*(X)={x∈U|[x]RX} (6)R*(X)={x∈U|[x]R∩X≠} (7)进一步,定义 X 的边界域为BNR=R*(X)-R*(X) (8)若BNR≠,则集合 X 就是一个粗糙集.下近似R*(X)是 X 肯定包含的基本知识组成的集合,它包括了所有使用知识 R 可确切分类到X中的元素;上近似R*(X)是 X 可能包含的基本知识组成的集合,它包括了所有使用知识 R 可能分类到X 中的元素.边界域则由不能肯定分类到这个子集或其补集中的所有元素组成.需要指出的是,文献[46]融合形式概念分析与粗糙集,提出了粗糙可定义粒,并以对象诱导的面向对象概念的外延作为基本粒,通过一对基本粒近似描述其它粗糙不可定义粒.在本文中,充分借鉴了上近似和下近似描述不可定义粒的思想.3 粒的描述逻辑语言本文中粒的描述语言采用粗糙集中的决策逻辑[55-56],并对其进行部分修正和扩展以适应基于必然属性的分析与推理.描述逻辑语言建立在一组原子公式的基础上,这些原子公式构成了复杂知识表示的基础.语义上,一个原子公式描述对象的一个属性,并用小写英文字母表示,例如a,b,c,d 等.以原子公式作为基础,通过使用逻辑连接符∧,∨, ,→ 和 ,以递归的方式可以构造更加复杂的逻辑表达式.形式化地,若φ和ψ是逻辑式,那么φ∧ψ,φ∨ψ,φ,φ→ψ和φψ也都是逻辑式.给定一个论域G,所有可能的粒组成G 的幂集,记作2G.描述论域G 的属性集用M 表示,论域中对象和属性的关系用二元关系I:G×M → {0,1}表示.因此,可以通过一个形式背景 K=(G,M,I)描述一个论域.定义10.  给定 一个粒 X∈2 G和 一 个 属 性 集A,若对于任意的a∈A,都有a*X,则称 X 必然具有属性集A,并记作 X aA.进一步,当属性集由逻辑式表达,下列式子的语义定义为X aA∧B (X aA)∧(X aB);X aA∨B (X aA)∨(X aB);X a A ~X aA;X aA→B (X aA)→(X aB);X aAB (X aA)(X aB).在文献[45]中,从共性属性的角度研究信息粒的描述:给定一个信息粒 X∈2 G和一个属性集A,若对于任意的a∈A,x∈X,都有xIa,则称 X 具有属性集A.显然,本文的研究角度与文献[45]完全不同.本文研究对象的必然属性,而文献[45]研究对象的共有属性.为了得到必然属性分析的粒描述逻辑语言,下面讨论共有属性分析的粒描述逻辑语言的一些性质.对于一个属性的合取式φ,记其中包含的文字为φ.定义11. 给定一个属性的合取式φ,称m(φ)={x∈G|x→φ} (9)是φ的外延.其中,集合内的约束条件表示对象具有合取式的所有共有属性.若 m-1(X)=φ且m(φ)=X,则称φ是X 的描述.6072计  算  机  学  报 2018年中用d(X)代替 m-1(X)来表示 X 的描述.命题1. 设φ和ψ是 两 个 公 式,则 以 下 命 题成立:(1)m(φ)=G-m(φ);(2)m(φ∧)=m(φ)∩m();(3)m(φ∨)=m(φ)∪m();(4)m(φ→)=(G-m(φ))∪m().定义12[45]. 设X 是形式背景K=(G,M,I)的一个粒,φ是一个公式.则φ对于 X 的查全率和查准率分别定义如下:α(φ,X)=m(φ)∩XX,β(φ,X)=m(φ)∩Xm(φ)(10)在不引起 歧 义 时,分 别 用α(φ)和β(φ)代 替α(φ,X)和β(φ,X).实际上,α(φ,X)刻画了能够准确描述的部分占粒 X 的比例,β(φ,X)刻画了能够准确描述的部分占φ的外延的比例.α(φ,X)和β(φ,X)的值越大表明公式φ对粒 X 的描述越贴近.实际上,粒描述的本质就是给定一个粒,找到查全率和查准率最大的公式.命题2. 设φ和ψ是 两 个 公 式,则 下 列 命 题成立:(1)α(φ)=1-α(φ);(2)α(φ∧)min(α(φ),α());(3)α(φ∨)max(α(φ),α());(4)α(φ∨)=α(φ)+α()-α(φ∧).命题3. 设φ和ψ是两个公式,则下列命题不成立:(1)β(φ)=1-β(φ);(2)β(φ∧)min(β(φ),β());(3)β(φ∨)max(β(φ),β());(4)β(φ∨)=β(φ)+β()-β(φ∧).4 基于一元描述子的粒描述本小节研究基于一元描述子的粒描述.具体地,定义正文字可定义粒和负文字可定义粒,这二者又统称为一元可定义粒,并将一元可定义粒的描述称为一元描述子.为了更加简洁地刻画一元可定义粒,给出了面向对象概念的最小产生子,并提出计算最小产生子的方法.此外,基于一元描述子还讨论了不可定义粒的近似描述.下面先介绍必然属性分析视角下形式背景的属性特征.4.1 形式背景的属性特征对于一个形式背景,通常存在一些冗余属性,删除这些属性并不改变面向对象概念格的结构,反而能够简化概念单元.定义13[20]. 设 K=(G,M,I)是一个形式背景,称 KN=(G,N,IN)是 K 的一个子背景,其中NM,IN=I∩(G×N).定义14[53-54]. 设 K=(G,M,I)是一个形式背景,NM.若对任意面向对象概念(A,B)∈L(K),存在(A,C)∈L(KN),则称 N 是K 的一个协调集.进一步,若 N 是K 的一个协调集,且 N 的任意真子集都不是 K 的一个协调集,则称 N 是 K 的一个约简集,并称b∈M-N 为冗余属性.定义15[53-54]. 若一个形式背景不存在冗余属性,则称 这个形 式背景为 净 化形式背景,并 称 净 化形式背景的面向对象概念格为净化的面向对象概念格.定义16[57]. 设L1、L2是两个完备格.若对于任意两个 元 素a,b∈L1,存在双射f:L1→L2使得f(a∨b)=f(a)∨f(b),f(a∧b)=f(a)∧f(b)成立,则称L1与L2同构.显然,对 于 形 式 背 景 K= (G,M,I)和 子 背 景KN=(G,N,IN),如果 N 是K 的一个协调集,那么L(K)与L(KN)同构.下列定理2提供了一个识别冗余属性的方法.定理2. 设 K= (G,M,I)是一个形 式 背 景,b∈M.如果存在若干属性bi∈M-{b}(i=1,2,…,t)使得∪ti=1b*i=b*,那么b是一个冗余属性.例2. 形式背景K1包含3个对象和4个属性,如表2所示.显然有a*∪b*=c*成立,因而根据定理2,可知c是一个冗余属性.删除冗余属性后的净化形式背景 K2见表3.原形式背景的面向对象概念格L(K1)见图1,净化的形式背景的面向对象概念格L(K2)见图2,其中外延和内涵均采用了集合的缩写.显然,面向对象概念格L(K1)与L(K2)同构.表 2 非净化的形式背景 K1a  b  c  d1  1  0  1  02  0  1  1  03  0  0  0  1表 3 净化的形式背景 K2a  b  d1  1  0  02  0  1  03  0  0  1127072期 智慧来等:基于必然属性分析的粒描述图 1 面向对象概念格L(K1)图 2 面向对象概念格L(K2)4.2 正文字可定义粒的描述本小节定义正文字可定义粒,并基于形式背景的面向对象概念格研究正文字可定义粒的描述问题.定义17. 设 K=(G,M,I)是一个形式背景,X∈2 G.若存在正文字的析取式φ使得m(φ)=X,则称 X 为正文字可定义粒.其中,m(φ)表示具有φ中所有必然属性的最小对象集.显然,对于形式背景 K=(G,M,I)中的一个粒X∈2 G,若存在一个面向对象概念C∈L(K)使得C的外延等于X,则 X 是一个正文字可定义粒.换言之,对于一个正文字可定义粒 X,一定存在一个正文字的析取式φ使得α(φ,X)=1,β(φ,X)=1.对于一个正文字可定义粒 X,若与其对应的面向对象概念为(X,B),那么X 的描述为(以下析取式的语义是指包含这些必然属性,区别于文献[45]的合取式的语义表示同时具有共有属性.)d(X)=∨a∈Ba (11)然而,对于一个正文字可定义粒 X,集合 B 中的属性并不都是必须的.换言之,当删除 B 中的某些属性后,仍有可能准确描述这个粒 X.在形式概念分析中,采用最小产生子(MinimalGenerator)[58]来表达一个概念的核心属性.有的文献亦称最小产生子为内涵亏值[59].最小产生子在稳定性计算[60]、粒的描述[45]等问题中 得 到 了 广 泛 应用.受此启发,下列定义18也提出了面向对象概念的最小产生子.定义18. 对于给定的面向对象概念 C=(X,B),如果属性集RB 满足R◇=B◇=X 且对于任意的SR 有S◇B◇,则称R 是C 的一个最小产生子.在此基础上,若 T 满足RTB,则称 T 是C 的一个内涵缩减集.定理3. 在一个净化的面向对象概念格中,若一个概念只有一个下近邻,则这个概念是一个属性诱导的面向对象概念.定理4. 在一个净化的面向对象概念格中,属性诱导的面向对象概念的最小产生子由这个概念的属性标签组成.换言之,定理3和定理4分别给出了属性诱导的面向 对 象 概 念 的 识 别 及 其 最 小 产 生 子 的 构 成.下面继续讨论非属性诱导的面向对象概念的最小产生子.引理1. 在面向对象概念格中,一个非属性

[返回]
上一篇:基于社会媒体内容和网络拓扑的特定话题推特摘要研究
下一篇:基于双深度网络的安全深度强化学习方法