概念格理论属性约简算法研究

概念格论文：决策形式背景属性约简方法研究【中文摘要】1982年,德国数学家Wille.R教授首次提出了概念格理论,或称为形式概念分析.概念格是根据数据之间的关系建立起来的一种概念层次结构,能够生动简洁地表现概念之间的泛化与特化关系.作为数据分析和知识处理强而有力的工具,概念格理论受到许多学者的广泛关注,已经被应用于数据挖掘、软件工程、知识工程以及信息检索等领域.属性约简是概念格理论研究的核心问题之一.本文以王~、Mi~以及其他人得到的一些成果为基础,给出了决策形式背景和模糊环境下的概念格属性约简方法,主要工作如下:1.从不可约元的角度提出了决策形式背景的一种irr-型属性约简方法.在协调决策形式背景中讨论了保持对象概念中不可约元不变的概念格的属性约简问题,定义了一种irr-型属性协调集,给出了判别这种属性协调集的充分条件,并且将irr-型属性协调集与Zhang~提出的属性协调集进行了比较.在不协调决策形式背景中利用包含度理论定义了分布协调集和最大分布协调集,并且得到了相应的判别定理.2.研究了基于同态映射的决策形式背景的属性约简问题.定义了一种同态协调集,从同态的角度讨论决策形式背景下的属性约简问题,证明了这种同态协调...【英文摘要】The theory of concept lattice, proposed by Wille R. in 1982, is also called the theoryof formal concept. The concept lattice sets up a kind of relation of conceptualhierarchiesaccording to relations among data, and it vividly re?ects relationship of generalization andspecialization among concepts. As a useful tool in data analysis and knowledge management,many scholars devote themselves to the study of concept lattice. Now concept lattices have beenapplied in many research areas, such as data mining, softw...【关键词】概念格决策形式背景不可约元属性约简同态协调集模糊决策形式背景模糊概念格【英文关键词】concept lattice decision formal context irreducible element attribute reduc-tion homomorphism consistent set fuzzy decision formal context fuzzy concept lattice【索购全文】联系Q1：138113721 Q2：139938848【目录】决策形式背景属性约简方法研究中文摘要4-5英文摘要5 1 绪论8-10 1.1 概念格的研究背景及研究进展8 1.2 模糊概念格的研究背景及研究进展8-9 1.3 本文研究内容的安排9-10 2 基于不可约元的irr-型属性约简方法10-16 2.1 预备知识10-11 2.2 协调决策形式背景的属性约简11-13 2.3 不协调决策形式背景的属性约简13-14 2.4 小结14-16 3 同态映射下的属性约简方法16-24 3.1 预备知识16-17 3.2 协调决策形式背景的同态约简17-20 3.3 概念之间的可辨识属性集20-22 3.4 小结22-24 4 模糊决策形式背景的属性约简方法24-30 4.1 预备知识24-25 4.2 模糊决策形式背景上(α,β)属性约简的定义25-27 4.3 模糊决策形式背景属性约简方法27-28 4.4 小结28-30 5 结论与展望30-32 5.1 本文的主要研究成果30 5.2 进一步研究的问题30-32参考文献32-35致谢35-36攻读学位期间取得的科研成果清单36。

基于属性约简的概念格构造
刘利峰;吴孟达;王丹
【期刊名称】《计算机工程与科学》
【年(卷),期】2007(29)6
【摘要】概念格是数据处理和规则提取的重要工具.对于数据较大的形式背景,由于产生的概念格结构复杂,部分有用的信息将被这种复杂的结构所掩没.本文利用属性约简理论,首先在没有构造概念格的前提下将概念格的属性进行约简,从而进一步构造出约简后的概念格.实验证明,该方法简洁高效.
【总页数】3页(P140-142)
【作者】刘利峰;吴孟达;王丹
【作者单位】国防科技大学理学院,湖南,长沙,410073;国防科技大学理学院,湖南,长沙,410073;国防科技大学理学院,湖南,长沙,410073
【正文语种】中文
【中图分类】TP18
【相关文献】
1.概念格的贴近度及基于贴近度的概念格属性约简算法 [J], 孟慧丽
2.基于单边区间集概念格的不完备形式背景的属性约简 [J], 王振;魏玲
3.基于矩阵的模糊-经典概念格属性约简 [J], 林艺东; 李进金; 张呈玲
4.基于面向对象(属性)概念格的形式背景属性约简方法 [J], 岳晓威;彭莎;秦克云
5.基于OE-概念格的形式背景属性约简 [J], 张呈玲;李进金;林艺东
因版权原因，仅展示原文概要，查看原文内容请购买。

一种新的面向对象概念格属性约简方法万家良【摘要】为了研究概念格的属性约简方法，提出了面向对象概念格的可简化属性和不可简化属性，并研究相关性质。

给出了面向对象概念格知识约简的判定定理，及相应的面向对象概念格约简方法。

本文提出的属性约简方法，不用建立在差别矩阵上面，便可得到形式背景的约简集。

%To study attribute reduction in formal concept ,reducible attributes and irreducible attributes are introduced .And the related properties were studied .The judgment theorems of attributes reduction for object-oriented concept lattice are proposed .This is an effective method for reduction in object-orien-ted concept lattice .【期刊名称】《纺织高校基础科学学报》【年(卷),期】2013(000)003【总页数】4页(P355-358)【关键词】形式背景;面向对象概念格;可简化属性;不可简化属性;属性约简;差别矩阵【作者】万家良【作者单位】西北大学数学系，陕西西安710127【正文语种】中文【中图分类】TP18;O290 引言1982年德国数学家Wille R.提出了形式概念分析［1］，它是一种重要的知识表示和知识发现的数学工具，已在众多领域中得到了广泛的应用，如知识工程，软件工程和信息检索［2-4］等.概念格理论［5］是形式概念分析的核心内容，同时，粗糙集理论也是数据分析和处理的有力数学工具，文献［6-7］将这两种理论结合研究，提出了面向对象概念格和面向属性概念格，并研究了这两种格之间的联系，得出面向属性概念格和面向对象概念格是同构的，加深了概念格理论.但是，数据库的不断增大，概念格的简化问题引起了学者的广泛关注，成为了概念格理论研究的主要问题.Ganter和Wille通过删除形式背景的行或列约简经典概念格，文献［8］通过格同构定义了一种新的概念格约简理论，文献［9］沿用这种定义讨论了面向对象概念格和面向属性概念格的约简问题.而文献［10］得到了经典概念格，面向对象概念格与面向属性概念格三者之间的重要关系.文献［11］则从覆盖粗糙集的角度给出了概念格的一种简便方法，文献［12］对以上理论进行了综述.本文则是从文献［13-14］提出的覆盖粗糙集思想，提出了面向对象概念格的可简化属性概念，进而得到它的属性约简的判定定理，避开了差别矩阵的计算，得到面向对象概念格的属性约简的新方法.对概念格理论的研究有着切实的重要意义.1 预备知识定义1［1］三元组（U，A，R）是一个形式背景，其中U ＝｛x1，x2，…，xn｝为对象集，每个xi 称为一个对象，A＝｛a1，a2，…，as｝为属性集，每个ai称为一个属性，R是对象集U和属性集A之间的二元关系集，且R⊆U×A.如果（x，a）∈R，则称对象x具有属性a.对于形式背景（U，A，R），在对象集X⊆U和属性集B⊆A上分别定义运算＊与′：X＊＝｛a｜a∈A，∀x∈X，（x，a）∈R｝，B′＝｛x｜x∈U，∀a∈B，（x，a）∈R｝.式中，X＊表示X中所有的对象共同具有的属性集合；B′表示具有B中所有属性的对象集合.∀x∈U，x＊≠∅，x＊≠A且∀a∈A，a′≠∅，a′≠U，则称形式背景（U，A，R）是正则的，以下假定形式背景是正则的.文献［6］用“□”表示下近似算子，用“◇”表示上近似算子，对于X⊆U及B⊆A，定义这两个近似算子：X□＝｛a∈A｜a′⊆X｝，B◇ ＝｛x∈U｜x＊∩B≠ ∅｝.定理1［6］设（U，A，R）是形式背景，∀X，X1，X2⊆A及∀B，B1，B2⊆U，算子“□”与“◇”有以下性质：定义2［8］设（U，A，R）是形式背景，如果对于∀X⊆U，∀B⊆A，满足X＝B◇且B＝X□，则称二元组（X，B）为面向对象概念；其中X为概念的外延，B为概念的内涵.定理2［8］设（U，A，R）为形式背景，LO（U，A，R）＝｛（X，B）｜X＝B◇ ，B＝X□｝.令（X1，B1）≤ （X2，B2），则LO（U，A，R）为一个偏序集.在LO（U，A，R）上定义（X1，B1）∧ （X2，B2）＝（（X1 ∩X2）□◇，B1∩B2），（X1，B1）∨ （X2，B2）＝（X1 ∪X2，（B1 ∪B2）◇□ .（LO（U，A，R），∨，∧）是一个完备格，称为面向对象概念格.2 面向对象概念格的属性约简定义3［8］设形式背景（U，A，R），B⊆A，如果LO（U，B，RB）＝ULO （U，A，R），则称B是面向对象协调集；更进一步，B 是面向对象协调集，∀b∈B，若LO（U，B-｛b｝，RB-｛b｝）≠ULO（U，A，R），则称B是形式背景（U，A，R）的面向对象约简集.定理3 设（U，A，R）是形式背景，B⊆A，则B是面向对象协调集当且仅当X□B◇B＝X□A◇A，∀X⊆U.证明充分性由定义3即可得到，下面说明必要性.设B是协调集，则∀X⊆U，有X□B⊆X□A，X□B◇B ⊆X□A◇A，X□A◇A ∈LOU（U，A，R），LOU（U，A，R）＝LOU（U，B，RB），所以X□A◇A ∈LOU（U，B，RB），所以（X□A◇A）□B◇B＝X□A◇A，因为X□A◇A ⊆X，得（X□A◇A）□B⊆X□B（X□A◇A）□B◇B⊆X□B◇A，由于X□B◇A＝X□B◇B，（X□A◇A）□B◇A ＝（X□A◇A）□B◇B，故有X□A◇A ⊆X□B◇B.综上有，X□A◇A ＝X□B◇B.定义4 设（U，A，R）为形式背景，在属性集A 上定义等价关系R（U，A，R）为包含属性a的等价类记为［a］A，也就是［a］A ＝｛b∈ A｜（a，b）∈R（U，A，R）｝.在属性集 A 上由等价关系R（U，A，R）产生的分划记为A／R（U，A，R）.图 1 LO（U，A，R）例1 表1是一个形式背景（U，A，R）.其中U＝｛1，2，3，4，5｝是对象集，A＝｛a，b，c，d，e，f，g｝是属性集，1表示（x，a）∈R.其面向对象概念格如图1所示.为简便起见，本文中内涵与外延皆用相应集合的元素序列表示.表1 形式背景T＝（U，A，R）U a b c d e f g 1 1 0 1 0 1 1 0 2 1 1 0 1 0 0 13 0 0 1 0 0 1 04 0 0 1 0 0 1 05 1 1 0 0 0 0 1可以得到R（U，A，R）＝｛（a，a），（b，b），（b，g），（c，c），（c，f），（d，d），（e，e），（f，f），（f，c），（g，g），（g，b）｝.这样定义5 设（U，A，R）为形式背景，a∈A，［a］A 称为（U，A，R）的可简化类，如果存在一些由R（U，A，R）产生的等价类，［b1］A，［b2］A，…，［bk］A，且［bi］◇AA ≠ ［a］◇AA ，1≤i≤k.有否则，［a］A 称为（U，A，R）的不可简化类.相应的，如果［a］A 是（U，A，R）的可简化类，则称a是（U，A，R）的可简化属性；如果［a］A 是（U，A，R）的不可简化类，称a是（U，A，R）的不可简化属性.∀a∈A，因为a◇A ＝，则等式（1）可写成定理4 设（U，A，R）为形式背景，a∈A，则（1）a是（U，A，R）的不可简化属性当且仅当（2）a是（U，A，R）的可简化属性当且仅当证明可由等式（1）和定理3直接得到.例2 由定义4可知，所有的不可简化类可计算得到｛b，g｝，｛e｝，｛c，f｝，｛d｝.因此，｛a｝是（U，A，R）惟一的可简化类，（U，A，R）的所有不可简化属性是b，c，d，e，f，g.a是惟一的一个可简化属性.定理5 设a是（U，A，R）的可简化属性，则A-［a］A 是（U，A，R）的协调集.推论1 设a是（U，A，R）的可简化属性，则A-｛a｝是（U，A，R）的协调集. 证明因为｛a｝⊆［a］A，所以根据定理5可直接得到.推论1表明，删除形式背景的可简化属性或可简化类不会产生新的可简化属性，也不会使最初是可简化的属性变成新的形式背景的不可简化属性.因此，可以通过一个一个删除可简化属性，由此得到更小的协调集.把形式背景（U，A，R）的所有不可简化类组成的集合记为Irr＿class（U，A，R）.因此有推论2 ∪Irr＿class（U，A，R）是（U，A，R）的协调集.证明根据Irr＿class（U，A，R）的定义，可以直接得到.定理6 设（U，A，R）是形式背景，B⊆A，则B是（U，A，R）的协调集当且仅当B∩［a］A≠∅，∀［a］A∈Irr＿class（U，A，R）.推论3 设B是（U，A，R）的协调集，a∈B是（U，A，R）的不可简化属性，如果card（B∩ ［a］A）＞1，则B-｛a｝是（U，A，R）的协调集，否则B-｛a｝不是协调集.图 2 Lo（G，D，R）证明如果card（B∩［a］A）＞1，则B∩［a］A中至少有2个元素，分别记为a，b∈B ∩ ［a］A.因此，b∈ （B-｛a｝）∩ ［a］A，即（B-｛a｝）∩［a］A ≠∅.∀［b］A ≠ ［a］A 且［b］A ∈Irr＿class（U，A，R），因此，（B-｛a｝）∩ ［b］A ＝B∩ ［b］A ≠ ∅.由定理6可知，B-｛a｝是（U，A，R）的协调集.另外，如果card（B∩［a］A）≤1，也就是说B∩［a］A ＝｛a｝，因此（B-｛a｝）∩［a］A＝∅，因此，由定理6可知，B-｛a｝不是协调集.由定理6和推论3，可以直接得到形式背景的属性约简集的定理.定理7 （U，A，R）是形式背景，D⊆A，则D是（U，A，R）的属性约简集当且仅当card（D ∩ ［a］A）＝1，∀［a］A ∉Irr＿class（U，A，R）.且D ∩［a］A ≠ ∅，∀［a］A ∉Irr＿class（U，A，R）.例3 由以上定理可知，在预备知识的例题中，共有4个属性约简集，即｛b，c，d，e｝，｛b，d，e，f｝，｛c，d，e，g｝，｛d，e，f，g｝.对于属性约简集 D ＝｛b，c，d，e｝，LO（U，D，RD）如图2所示，对比图1和图2，可知，LO （U，A，R）和LO（U，D，RD）拥有相同的外延集.3 结束语本文首先定义了面向对象概念格的不可简化属性概念，从不可简化属性出发，提出了面向对象概念格的属性约简方法，然后给出了属性约简的判定定理.这无论在理论上还是在应用上都是有意义的，我们将更深入的探讨模糊概念格、粗糙概念格的约简方法.【相关文献】［1］WILLE R.Restructuring lattice theory：An approach based on hierarchies of concepts ［M］.Boston：Ordered Sets，1982：445-470.［2］CARPINETO C，ROMANO G.A lattice conceptual clustering system and its application to browsing retrieval［J］.Machine Learning，1996，10：95-122.［3］CHEN Y，YAO Y.A multiview approach for intelligent data analysis based on data operators［J］.Information Sciences，2008，178（1）：1-20.［4］胡可云，陆玉昌，石纯一.概念格及其应用进展［J］.清华大学学报，2000，40（9）：76-81.［5］GANTER B，WILLE R.Formal concept analysis：Mathematical foundations［M］.New York：Springer-Verlag，1999.［6］YAO Y Y.A comparative study of formal concept analysis and rough set theory in data analysis［J］.Lecture Notes in Artificial Intelligence，2004，3066：59-68.［7］DUNTSCH I，GEDIGA G.Approximation operators in qualitative data analysis［C］／／Theory and Application of Relational Structures as Knowledge Instruments，Heidelberg：Springer，2003.［8］ZHANG W X，WEI L，QI J J.Attribute reduction theory and approach to concept lattice［J］.Science in China：Ser F Information Science，2007，50（2）：188-197.［9］LIU M，SHAO M W，ZHANG W X.Reduction method for concept lattices based on rough set theory and its application［J］.Computers and Mathematics with Applications，2007，53（9）：1 390-1 410.［10］JESUS Medina.Relating attribute reduction in formal，object-oriented and property-oriented concept lattices［J］.Computers and Mathematics with Applications，2012，64：1 992-2 002.［11］LI T J，WU W Z.Attribute reduction in formal contexts：a covering rough set approach［J］.Fundamenta Informaticae，2011，111：15-32.［12］张文修，仇国芳.基于粗糙集的不确定性决策［M］.北京：清华大学出版社，2005.［13］ZHU W，WANG F Y.Reduction and axiomization of covering generalized rough set［J］.Information Sciences，2003，152：217-230.［14］ZHU W.Topological approaches to covering rough sets［J］.Information Sciences，2007，177（6）：1 499-1 508.。

粗糙集与概念格的属性约简研究粗糙集理论是波兰数学家Pawlak于1982年提出的一种用于分析数据的数学理论。

概念格理论(也叫形式概念分析)是德国数学家Wille在同一年提出的描述概念与概念之间层次关系的形式化工具。

粗糙集理论与概念格理论作为数据分析和知识发现的强有力工具,越来越受到人工智能研究者的广泛关注。

目前,这两种理论已经被广泛应用于软件工程、数据挖掘、信息检索、机器学习、不确定性规则获取与决策管理等领域。

知识发现的一个重要方面就是知识约简。

本文研究信息系统属性约简和概念格属性约简,分别提出了基于闭算子的目标信息系统属性约简方法和异于文献[29]的概念格属性约简新方法。

系统研究了两个同类形式背景在同态映射下的性质。

本文的主要工作如下:1.提出了目标信息系统属性约简的闭算子方法。

针对协调的目标信息系统,构造了条件属性集及其幂集上的一致关系,讨论了由这两种一致关系所导出的两个闭集族C_r与C_R的性质及相互之间的关系;证明了这两个闭集族相等的充分必要条件,并给出在此条件下目标信息系统的属性约简方法;证明了本文提出的属性约简与文献[12,28]中约简定义的等价性。

2.提出了概念格属性约简的一种新方法。

针对文[29]所给出的概念格属性约简理论,利用概念格中所有交不可约元得到一些极小属性集族,每个集族中任取一个元素然后求并集就是文[29]中所定义的形式背景的约简。

同时给除了求属性约简的相应算法。

3.研究了同态映射下同类形式背景各元素之间的关系。

定义了形式背景之间的同态映射。

对于无决策形式背景,分析了形式背景的概念以及协调集的同态性。

对于决策形式背景,讨论了协调性的同态不变性,并给出了约简的同态像仍为约简的充分条件。