GT-VMT 2001：概念图转换与概念格在理论计算机科学中的应用

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html7页概念图的转换：一种经验归纳的方法？John L. Pfaltz部计算机科学，大学jlp@virginia.edu1概念格设R是一个二元关系，如图1（a）所示，具有m行和n列。这样的关系可以表示许多现象，并且存在大量关于关系代数的文献[1]。在本文中，我们采取一个更有限的观点，并简单地认为R作为一个观察的一组属性A与一组对象O。在我们的公式中，对象由编号的行表示，属性由字母列表示“形式概念分析”[5]是由Rudolf Wille [15]，Bernard Ganter和他们在达姆施塔特的同事们开发的。在他们的方法中，概念格（概念的偏序集合）的构造和视觉显示是至关重要的。概念格的节点对应于被建模的现象的抽象概念，并且格内的关系反映外部世界中的关系。 他们的书有许多例子，他们的方法已经在工业应用中得到应用（由Ganter Wille报道）和代码重新设计[8，14]。这个研讨会的有趣之处在于研究这些概念格如何随着新信息的出现而转变我们首先简要介绍概念格。设R是任意两个集合O和A之间的二元关系，如图1（a）所示。我们把O看作一组对象，把A看作一组属性。 但是，它们可以是任意的集合。例如，Lindig和Snelting [8]通过在P（一组过程）和V（一组全局变量）之间创建关系R，将概念分析应用于遗留代码O关于R的闭包'R，我们指的是与所有O 2 O共享相同属性的对象的最大集合。 类似地，对属性集合A进行操作的R1选取所有满足每个a2A的对象所共有的任何其他属性。1Ganter和Wille[5]表明，R和？ 研究部分由美国能源部资助DE-FG 05 - 95 ER 25254。1更正式地说，关于R的O上的伽罗瓦闭包'R'由那些闭的c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。GT-VMT 2001 { J. Pfaltz2O2OiR1实 际 上是闭包算子，并且构成了一个伽罗瓦连接. 对于任何R，如图1（a）中的R，R和 R1 的 闭 包 系 统是同构的，可以用格LR表示 图1（b）中所示的闭集，它是由包含部分排序的。标记每个节点是阿布克代夫吉一一BC De FGh i123O45abdf56ADFabcdf6ACDF68ACDACDE7678ABC36ABGabgh23123abcgh3AGHACGHI4acgh34678（一）568公元5678年AB1235612345678AC34678AG1234234（b）第（1）款图1.一、一个关系R（a）及其概念格LR（b）例如，由伽罗瓦连接连接的一对闭集.集合abg在A中是封闭的; 123在O中是封闭的。在这种情况下，我们已经相对于属性集A对格进行了定向，其中论域A=abcdef ghi（必须是封闭的）是格上确界。单例集fa g是每个对象的一个属性，它是格下确界。它相对于集合包含是偏序的。容易地，概念格L是R的内容的视觉模型。在Ganter和Wille的书中有许多类似的应用概念分析的例子[5]。概念分析的后期扩展在[16]中报道。2闭包空间运算符'是闭合运算符，如果XX：'，XY ）X：'Y：'和X：'：'X：'。二元关系上的Galois闭包是一种离散闭包算子。在[9，12]中提出了一种更一般的闭包空间的处理方法在这些文件的一个中心思想是，发电机的一个封闭的集合，Z，表示Z：，我们的意思是一个最小的集合Y，使Y：'=Z。例如，对于一个凸n边形，其生成元是它的n个顶点（或端点）。 2集合OO，形式为O=Oi：R：R1，其中Oi：R=To：Ra和Ai：R1=Ta2Ai a：R1O。相反，一个形成闭合，R1关于AR由闭集A=Ak：R1：R组成. 集合Oi：R表示O中每个对象共享的所有属性的集合。因此，O i：'=O i：R：R 1表示共享（至少）这些公共属性的所有对象的集合。类似地，Ak：R 1表示共享Ak中每个属性的所有对象的集合，并且Ak：'= Ak：R 1：R由（至少）具有共同Y的对象共享的所有属性组成。2在离散几何文献[3]中，所有的生成元都被称为极值点。GT-VMT 2001 { J. Pfaltz3一个n边形是由它的生成元唯一确定的当一个闭集的生成子必须是唯一的时，我们说闭包算子是唯一生成的，并称由此产生的闭包空间为反拟阵。[3]许多闭包文献，例如[2，3，4，9，12]假设反类闭包。使用闭包空间中的概念，生成概念格，同时确定这些封闭概念的生成元是非常简单例如，单个属性e生成封闭概念acde。也就是说，fg：'R1 =facdeg. 为了在 R 中 看到这一点，观察每个具有属性e对象（只有一个！）还具有性质a、c和D也是。类似地，我们发现fbd g或fbfg将生成fabdfg，因为属性b和d只在对象5和6中一起找到，它们也共享属性abdf。这个封闭空间，以及大多数来自概念分析的封闭空间，并不是反类的。尽管如此，它们仍然保留了反拟阵闭包空间的大部分结构[7]。如果我们把R看作数据库意义上的关系，那么（o; a）2R表示a是对象o的属性。在图1（a）中，很明显abgh是对象2和3的共享属性属性bh生成abgh。所以我们可以断言在这个世界上（8o 2O）[o：bh）o：abgh];或者更简单地说，我们有属性蕴涵bh）abgh类似地，我们可以证明bcd和bcf都是abcdf的最小生成元;所以我们有属性蕴涵bcd_bcf）abcdf。通过导出所有闭概念集的生成元，我们提取了对R有效的所有逻辑蕴涵（在O上泛量化）。从现在开始，我们将使用）来表示属性蕴涵和闭包生成。在离散世界的基于规则的描述中，X：和X：'的解释分别在前面和后面，开辟了一种全新的知识发现方法[11]，可以在相对较小的离散世界中利用。[4] 虽然对概念格中闭集生成元的粗略描述可能过于简短，无法完全理解，但它应该足以表明通过增加对R的观察（行）来建模归纳学习的潜力。3感应变换如果一个概念格LR捕捉到了一个对象集合的所有逻辑属性含义;5自然会问：假设我们观察到3拟阵和反拟阵是相同的，除了拟阵的闭包算子满足交换公理，而反拟阵的闭包算子满足反交换公理。4弗吉尼亚大学的机器人项目。[6]在关系表中收集有关其世界中对象的传感器数据。它将使用我们的算法将这些数据转换为输入到其基于规则的规划组件的含义。5在[5]中，R1是通过儿童教育电视节目中关于池塘生活的断言获得的。这是一种对真实现象的孩子般的理解。GT-VMT 2001 { J. Pfaltz4RR多一个对象及其属性。这将如何改变晶格LR？“这就是离散的经验归纳法的本质。给定一个具有内部结构的观测集合R，用LR表示，新的信息如何转换这个结构？实际上，由于闭集的一个基本性质，这种变换本质上是“优美的”和“局部的|闭集的交集必须是闭的。这就导致了闭集Z=X：“与其生成元Z：”之间的一个有趣的矛盾。每次我们向R添加一行（对象/属性观察）时，我们至少向L R添加一个新的闭集，因为单个r w的属性构成A 6的闭集。设o0;A0 >表示这个新的r ow。若存在Z2L，则A0 =Z，则晶格保持未悬挂。别这样。则L中至少存在一个闭Z，使得A0 Z. 我们考虑A0\Y对所有闭Y;YZ。这是唯一的元素的概念格LR，其中A0 可以相互作用。例如，将具有属性a、c和g的对象9的新观察结果附加到R，产生图2（a）的关系和对应的概念阿布克代夫吉一一BCDeFGh i1234O5abdf56ADFabcdf6ACDF68acdACDE7678ABC36ABG123abghabcgh323ACGACGHI4acgh346789（一）568公元5678年AB12356123456789（b）第（1）款AC34678349AG12349AGH234图二、R2及其概念格LR2L-R~2格 图2（b）。 观察到acgac gh和acg\a gh=a g。这种局部交互发生在右下角，其中添加了一个新概念（闭集）acg，产生了虚线表示的新关系。这一新的观测数据也改变了L-R的世代结构。 在LR中，我们有一个ve（cg_ch））ac gh。 在LR2中，我们有一个 cg）ac g，所以cg不再是rgh的生成元。 N o winLR2，ch）ac gh.我们观察到，这个新的对象是不是很不同，从现有的ob-bellum。它包含在Z=ac gh中，而在L R中ch相当低。什么是Z= abcdef ghi =U，属性的宇宙？ 我们可以证明ef是a b c d e fg h i 的生成元，以及其他11个最小生成元。但是，没有与abcdef ghi=A关联的对象。在这个世界上，ef是一个合乎逻辑的6这不一定是严格正确的，但却是典型的，而且，我们可以假定它是正确的。GT-VMT 2001 { J. Pfaltz5矛盾 7在图3（a）中，我们现在已经改变了新对象9，使其具有属性a，d，e和f。 组合ef不再是矛盾。在LR3中，adef由Z=U转换。 它分别与ade和adf中的acde和abcdf相交（其中Z也涵盖）。闭集ade是新的，它递归地与acd相交（acd也被acde覆盖）。的阿布克代夫吉一一BCDeFGh i1234O5abdf56ADFabcdf6ACDF68ACDadef9Ade67879ABCACDE736ABGabgh23123abcgh3AGHACGHI4acgh34656897ad阿布-阿克234AG89（一）5678912356123456789（b）第（1）款346781234图3.第三章。R3及其概念格LR3图3（b）中的变化再次由虚线表示。举一个最终的例子，我们观察到a是每个对象的属性。它对应于R的单位中的逻辑重言式。加上第九个 如果我们改变它，就只能使用属性。它与acde和abcdf相交，分别创建了de和df，以及图4（b）中有趣的概念格。阿布克代夫吉一一BCDeFGh i1234O5abdf56ADFabcdf6ACDF68acdACDE7678ABC36ABG123abghabcgh323ACGACGHI4acgh346789（一）568公元5678年AB12356123456789（b）第（1）款AC34678349AG12349AGH234图四、R4及其概念格LR4向二元关系R所描述的逻辑世界添加新行（经验观察）产生基于迭代集交的概念格的正则优美变换。相反，已经证明[10，13]，从反拟阵闭包空间中删除元素，GT-VMT 2001 { J. Pfaltz67这种知识发现方法的优点之一是，除了导出所有真实的含义之外，它还识别出在这个对象中不可能为真的所有逻辑矛盾。GT-VMT 2001 { J. Pfaltz7在其闭包格L上导出格同态。[8]正如前面所观察到的，概念闭包空间通常不是反类素的。我们猜想，但尚未证明，删除概念格仍然会导致至少一个满足同态。总之，这些结果表明，“知识”是建立在序列性、经验性观察基础上的，是相对“稳定”的。当然，这与我们对知识的直觉、心理理解是一致的。但是，这仍然是非常活跃的研究。例如，我们推测，随着概念格变大，预期的增量变化幅度将变小。此外，我们还想知道概念格（一种世界理解）的重大重组会是什么样子|以及可能的原因引用[1] 克里斯·布林克，沃尔夫拉姆·卡尔，冈瑟·施密特。计算机科学中的关系方法。 Springer Verlag，维也纳，1997年。[2] Paul H. 埃 德 尔 曼 交 分 配 格 与 反 交 换 闭 包 。 代 数 普 遍 ， 10 （ 3 ） ：290{299，1980。[3] Paul H.作者声明：Robert E.贾米森凸几何理论。Geometriae Dedicata，19（3）：247{270，Dec. 一九八五年[4] Martin Farber和Robert E.贾米森图和超图中的凸性SIAM J.代数和离散方法，7（3）：433{444，1986年7月[5] 伯纳德·甘特和鲁道夫·威尔。形式概念分析-数学基础。Springer Verlag，Heidelberg，1999.[6] 作者：James P. Gunderson，Worthy N.马丁不确定性对模拟维护机器人领域计划成功的影响。J. of Experimental and Theoretic AI，12：153{164，2000.[7] Robert E. Jamison和John L.普法尔茨不是唯一生成的闭包空间。OrdinalandSymbolic Data Analysis，OSDA 2000，Brussels，Belgium，July 2000.[8] 克里斯蒂安·林迪格和格雷戈尔·斯内尔廷基于数学概念分析的遗留代码模块结构评估在1997年软件工程国际会议的过程中，第349页，波士顿，MA，1997年5月[9] John L. 普法尔茨 闭包格 离散数学，154：217{236，1996。[10] John L.普法尔茨反拟阵闭包空间中的删除变换。在第25届Combinatoric，Computing，and Graph Theory Conf. ，Boca Raton，FL，Mar. 1998年8实际上并不完全是格同态。它是满足保持，因此是顺序保持。但它只保留一个集合的上确界，如果上确界覆盖集合。GT-VMT 2001 { J. Pfaltz8[11] John L.普法尔茨封闭空间与知识发现 在2000年。知识光盘和数据挖掘，PKDD 2001，Freiburg，德国，2001。（已提交）。[12] John L. Pfaltz和Robert E.贾米森封闭系统及其结构在Jules Desharnais，编辑，第五届计算机科学中的关系方法国际研讨会，RelMICS 2000，第121页，第132页，魁北克省瓦尔卡地亚，2000年1月。[13] John L. Pfaltz和John E.卡洛反子阵闭包空间的变换。技术报告TR CS-98-13，计算机科学系，弗吉尼亚大学，1998年6月[14] 格雷戈尔·斯内尔廷和弗兰克·提普使用概念分析重构类层次结构。在Proc. ACM SIGSOFT第六届软件工程基础国际研讨会，FSE-6，第99页，第110页，Lake Buena Vista，FL，1998中。[15] 鲁道夫·威尔重构格理论：一种基于概念层次的方法。有序集，第445页{470，1982。[16] 卡尔·埃里希·沃尔概念、状态和系统。在1999年8月在比利时列日举行的第三届计算预期系统会议上，1999年