基于边缘概念的概念格生成算法研究

维普资讯 http://www.cqvip.com 第２１卷第４期　洛阳大学学报　Ｖｏ１．２ｌ　Ｎｏ．４　２　０　０６年１　２月　ＪＯＵＲＮＡＬ　ＯＦ　ＩＪＵＯＹＡＮＧ　ＵＮⅣＥＲＳｒＩ　Ｄｅｃ．　２ｏ０６　基于边缘概念的概念格生成算法研究木　宫玲，谢福鼎　（辽宁师范大学计算机与信息技术学院，辽宁大连Ｉ１６０２９）　摘要：提出了一种新的基于边缘概念的概念格生成算法．通过已求出的概念内涵　及外延的交集和并集运算，分层构造概念格．和已有概念格的构造算法不同的是，本算　法在求出边缘概念后就不再依赖于形式背景．该算法同时解决了跨层概念间的关系．最　后结合实例说明了该算法的实现过程和有效性．　关键词：概念格；边缘概念；生成概念；分层　中图分类号：Ｇ２０２文献标识码：Ａ文章编号：１００７—１１３Ｘ（２００６）０４—００６４—０４　１　引　言　自从Ｗｉｌｌｅ　Ｒ教授［Ｉ　首先提出形式概念分析以来，形式概念分析及概念格（也称为Ｇａｌｏｉｓ格）已被证　明是进行数据分析的有力工具．概念格的每个节点是一个形式概念，由两部分组成：外延，即概念所覆盖　的实例；内涵，即概念的描述，亦即该概念覆盖实例的共同特征．概念格通过Ｈａｓｓｅ图生动而简洁地体现　了这些概念之间的泛化和特化关系．目前，概念格在信息检索、软件工程、文本分类和知识发现等领域得　到了广泛的应用　Ｊ．　在应用概念格的过程中，概念格的构造成为首要问题．已经提出的生成概念格的方法一般分为两　种：批处理算法［，】、［４　和增量算法［５】、［６］．增量算法是针对已经建成的概念格，当有少量对象（属性）增加或　减少时，可以在已有的概念格上进行更新得到新的概念格，不必重新建格．批处理算法是在有较多和较　完整的数据信息的情况下，进行一次建格的方法．因此增量算法适合对概念格的更新和维护，而批处理　算法则是在初始建格过程中更有效的方法．在批处理算法中，Ｂｏｒｄａｔ的算法具有简单、直观的特点，有一　定的代表性．此算法的缺点是生成了很多重复节点，每个节点的次数都与其父节点的个数相同　．　本文给出的算法是：首先基于形式背景求出边缘概念，在此基础上分层对已求出的概念的外延及内　涵作交集和并集运算，从而求出所需的概念格．　２概念格的基本概念　定义１…　背景是一个三元组（Ｕ，Ｄ，尺），其中Ｕ是对象的集合，Ｄ是属性的集合，尺是Ｕ和Ｄ之间　的二元关系，对于　Ｅ　Ｕ，Ｙ　ＥＤ，若　具有屙陆Ｙ，则说　与Ｙ是有关的，记为　Ｒ　Ｙ或者（　，Ｙ）Ｅ　Ｒ．＋　定义２…形式背景（Ｕ，Ｄ，尺）的—个形式概念（简称概念）是—个二元组（Ｘ，ｌ，），它满足Ｘ　＝Ｙ且　＝　，其中ＸＣ＿Ｕ，ＹＣ＿Ｄ，Ｘ　：＝｛ｄ　ＥＤ　Ｉ　Ｕ　Ｅ　Ｘ：（Ｕ，ｄ）Ｅ　Ｒ｝，　：＝｛Ｕ　Ｅ　Ｕ　Ｉ　ｄ　Ｅ　Ｙ：（Ｕ，ｄ）Ｅ　Ｒ｝．Ｘ是　概念（　，】，）的外延，Ｙ是概念（Ｘ，　的内涵：　定义３　对于给定的两个概念（　，ｙ１）和（　，ｙ２），若置　（或ｙ２　ｙＩ）成立，则称（置，　）　是（　，ｙ２）的子概念，或者说（　，ｙ２）是（置，ｙ１）的超概念．记为：（置，ｙ１）≤（　，ｙ２）．　关系“≤”在概念之间建立了一种偏序关系．根据偏序关系可生成概念格的Ｈａｓｓｅ图．如果有Ｃ　≥　，并且不存在另一个元素　，使得Ｃ　≥Ｃ　≥Ｃ　，则从Ｃ　到Ｃ　就存在一条边，即Ｃ　是　的直接超概念，　Ｇ２是Ｇ　的直接子概念．形式背景（Ｕ，Ｄ，尺）中，满足直接子概念一超概念关系的所有概念节点的集合是　一个完备格，称之为Ｇａｌｏｉｓ格，简称概念格．　收稿日期：２００６—０９—２７　・基金项目：辽宁省教育厅高等学校科学技术研究资助项目（项目编号２０４０Ｆ０９９）；辽宁省科技基金资助项目（项目编号１０４０２２５）　作者简介；宫玲（１９８２一），女。山东牟平人，硕士研究生。研究方向：人工智能。数掘挖掘．　维普资讯 http://www.cqvip.com 第４期　宫玲等：基于边缘概念的概念格生成算法研究　－６５・　定义４（　在概念格中，如果概念ｃ＝（　，ｙ）只有一个直接子概念，称概念ｃ为边缘概念．否则　称其为生成概念．即生成概念至少有两个子概念．　性质１设Ｃ１＝（　。，ｙ１），ｃ　＝（　，ｙ２），…，ｃ　＝（　，ｙ＾）为边缘概念，则Ｘ，ＵＸ　Ｕ…ＵＸ　＝　Ｄ，ｙ１　Ｕ　ｙ２　Ｕ…ｕ　ｙ＾＝　性质２　如果概念ｃ＝（　，ｙ）有两个或两个以上直接子概念，设Ｃ。＝（　，ｙ１），ｃ　＝（　，ｙ２），　…，Ｃ　＝（　，　）（ｎ＞１），则：　＝Ｘ。ＵＸ　２　ｕ…ｕ　，Ｙ＝ｙＩ　Ｕ　Ｕ…ｕ　。　也就是说生成概念的外延可以由其直接子概念的外延求并集得到．因此，只要我们求出所有的边缘　概念，就可以在此基础上求出生成概念从而构建完整的概念格．那么边缘概念的外延中必包含所有的对　象，内涵中必包含所有的属性．对于　Ｅ　Ｕ，　一定存在于某个边缘概念的外延中，所以可以通过ｃ＝　（　，　）求出所有的边缘概念．　定义５　在概念格中，若概念ｃ。　＝（　，ｙｌ　）与Ｃ　＝（　Ⅳ，ｙ２　）的内涵数目相同，即Ｉ　ｙｌ　Ｉ＝Ｉ　ｙ２　Ｉ　＝Ｎ，则Ｃ　与　位于同层，都是第Ⅳ层的概念．自底向上概念的内涵数目逐层减１．　性质３　同层概念中不会出现直接子概念一超概念关系，即不会有连线．　性质４　在概念格中，除去最小元（Ｄ　，Ｄ）外，至多可分为　层，且Ｔ＝ｍａｘ（　Ｉ），其中　∈　由于层数每增加ｌ时，下一层概念的内涵个数至少增加１个，所以这里的　实际上是单个对象属性　的个数的最大值，也就是边缘概念的内涵个数的最大值．　在分层原则的基础上进一步细化直接子概念一超概念关系可分为上层直接超概念和跨层直接超概念　定义６　概念Ｃ。＝（Ｘ　，Ｙ１），ｃ２＝（　，　），Ｃ。是ｃ２的直接超概念，ｃ２是Ｃ。的直接子概念，若Ｉ　ｙ２　Ｉ—　Ｉ　Ｉ＝１，则Ｃ。是ｃ２上层直接超概念；若Ｉ　Ｉ—Ｉ　Ｉ＞１，则Ｃｌ是ｃ２跨层直接超概念．　例１　形式背景（　，Ｄ，Ｒ）如表１所示．　表１　３　（１”，１　）＝｛１２３，ａｂｐ｝　（２”，２　）＝｛２３，ａｂｐｈ　（４”，４　）＝｛４，ａｂｃｄｆ｝　（５”，５　）＝｛５６，ａｂｄｆ｝　（６”，６　）＝｛６，ａｂｃｄｆ｝　（８”，８　）＝｛６８，ａｃｄｆ｝　维普资讯 http://www.cqvip.com ・６６・　洛阳大学学报　Ｓｔｅｐ　２首先将已经求出的边缘概念按分层原则放人概念格中的适当位置．其结果如图１所示．　图１　Ｓｔｅｐ　３自底向上分层求出生成概念．　（１）同层的概念两两做运算，内涵求交集得到新概念的内涵；外延求并集得到新概念的外延．并将　内涵相同的概念合并（即外延求并集，内涵不变）．其结果如图２所示．　｛４６，ａｃ｝　图２　（２）如果新概念的内涵数目恰好比其子概念的内涵数目少一，即新概念为上层直接超概念，那么它　是确定概念可确定其在概念格中的位置以及与其直接子概念的连线．否则将新概念作为待定概念．　（３）该层所有的确定概念都求出后，判定待定概念的取舍．设待定概念为ｃ＝（　，ｙ），其子概念为　Ｃ。＝（　。，ｙ。），Ｃ：＝（　，ｙ２），…，Ｃ　＝（　，　）（ｎ＞１），其子概念的上层直接超概念为Ｃ。　：（　。　，　），　，（　，ｙ２　），…，Ｃ　＝（　，ｙｍ　）（／７／，＞１）．　①若待定概念的内涵与其子概念的上层直接超概念的内涵没有包含关系，则该待定概念是其子概　念跨层直接超概念并确定下来；　②若待定概念的内涵仅与其子概念的上层直接超概念中的一个的内涵存在包含关系，假设：Ｙ　ｙｍ　，则修改待定概念．修改待定概念Ｃ＝（　，ｙ）到　＝（　，　）的子概念的连线为待定概念到Ｃ　＝（　，ｙｍ　）的连线；修改待定概念ｃ＝（　，ｙ）的外延为ＸＵＸ　；并将待定概念确定下来；　③若待定概念的内涵与其子概念的上层直接超概念中的两个或两个以上的内涵存在包含关系，则　忽略该待定概念，将其去掉．　（４）自底向上层数减一，重复３．１到３．２的步骤直到求出最大元（０，０　）．其结果如图３所示．　图３　维普资讯 http://www.cqvip.com 第４期　官玲等：基于边缘概念的概念格生成算法研究　・６７・　４小结　本文的算法是基于边缘概念生成概念格．在边缘概念求出后，无需再往返于概念格与形式背景之　间，而直接求生成概念，这样大大缩减了时间复杂度；同时该算法在分层时简单明了。并且能够实现跨　层连线．　参考文献：　［１］Ｗｉｌｌｅ　Ｒ．Ｒｅｓｔｒｕｃｔｕｒｉｎｇ　ｌａｔｔｉｃｅ　ｔｈｅｏｒｙ：Ａｎ　ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ｈｉｅｒａｒｃｈｉｅｓ　ｏｆ　ｃｏｎｃｅｐｔｓ［Ａ］．Ｏｒｄｅｒｅｄ　Ｓｅｔｓ［Ｃ］．Ｄｏｒｄｒｅｃｈｔ：Ｄ　Ｒｅｉｄｅｌ　Ｐｕｂｌｉｓｈ　Ｃｏｍｐａｎｙ，１９８２，４４５—４７０．　［２］胡可云，陆玉昌，石纯一．概念格的应用及进展［Ｊ］．清华大学学报（自然科学版），２０００，４０（９）：７７—８１．　［３］Ｇｏｄｉｎ　Ｒ．Ｉｎｃｒｅｍｅｎｔａｌ　ｃｏｎｃｅｐｔ　ｆｏｒｍａｔｉｏｎ　ａｌｇｏｒｉｈｔｍ　ｂａｓｅｄ　ｏｎ　Ｇａｌｏｉｓ（ｃｏｎｃｅｐｔ）ｌａｔｔｉｃｅｓ［Ｊ］．Ｃｏｍｐｕｔａｔｉｏｎａｌ　ＩｎｔｅＨｉｇｅｎｃｅ，１９８８，　１１（２）：２４６—２６７．　［４］Ｎｏｕｒｉｎｅ　Ｌ，Ｒａｙｎａｕｄ　０．Ａ　ｆａｓｔ　ｌａｇｏｒｉｔｈｍ　ｆｏｒ　ｂｕｉｌｄｉｎｇ　ｌａｔｉｔｃｅｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｌｅｔｔｅｒ，１９９９，（７１）：１９９—２ｏ４．　［５］Ｈｏ　Ｔ　Ｂ．Ａｎ　ａｐｐｒｏａｃｈ．ｔｏ　ｃｏｎｃｅｐｔ　ｆｏｒｍａｔｉｏｎ　ｂａｓｅｄ　Ｉｎ　ｆｏｍｒａｌ　ｃｏｎｃｅｐｔ　ａｎａｌｙｓｉｓ［Ｊ］．ＩＥＩＣＥ　Ｔｒａｎｓ　Ｉｆｎｏｒｍａｔｉｏｎ　ａｎｄ　Ｓｙｓｔｅｍｓ，１９９５，　Ｅ＇／８一Ｄ（５）：５５３—５５９．　［６］Ｃａｒｐｉｎｅｔｏ　Ｃ，Ｒｏｍａｎｏ　Ｇ．ＧＡＬＯＩＳ：Ａｎ　ｏｒｄｅｒ・ｔｈｅｏｒｅｔｉｃ　ａｐｐｒｏａｃｈ　ｔｏ　ｃｏｎｃｅｐｔｕａｌ　ｃｌｕｓｔｅｒｉｎｇ［Ａ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ［Ｃ］．Ｍｏｒｇａｎ：　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ。１９９３，３３—４０．　［７］Ｂｏｄａｔ　Ｊ　Ｐ．Ｃａｌｃｕｌ　ｐｒａｔｉｑｕｅ　ｄｕ　ｔｒｅｉｌｌｉｓ　ｄｅ　Ｇａｌｏｉｓ　ｄｆｉｎｅ　ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ［Ｊ］．Ｍａｔｈ　Ｓｃｉ　Ｈｕｍ，１９８６，（９６）：３１－４７．　［８］Ｖａｌｔｅｈｅｖ　Ｐ，Ｍｉｓｓａｏｕｉ　Ｒ，Ｌｅｂｒｕｎ　Ｐ．Ａ　ｐａｒｔｉｉｔｏｎ－ｂｒｉｎｅｄ　ａｐｐｒｏａｃｈ　ｔｏｗａｒｄｓ　ｃｏｎｓｔｒｕｃｔｉｎｇ　Ｇａｌｏｉｓ（ｃｏｎｃｅｐｔ）ｌａｔｔｉｃｅｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，２００２，（２５６）：８０１；８２９．　［９］Ｇａｎｔｅｒ　Ｂ，Ｗｉｌｈ　Ｒ．Ｆｏｒｍａｌ　Ｃｏｎｃｅｐｔ　Ａｎａｌｙｓｉｓ，Ｍａｔｈｅｍａｔｉｃａｌ　Ｆｏｕｎｄａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９９９．　Ｔｈｅ　Ｓｔｕｄｙ　ｏｆ　Ｈｉｅｒａｒｃｈｉｃ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　Ｃｏｎｃｅｐｔ　Ｌａｔｔｉｃｅ　Ｂａｓｅｄ　ｏｎ　Ｍａｒｇｉｎ　Ｃｏｎｃｅｐｔ　ＧＯＮＧ　Ｌｉｎｇ，ＸｌＥ　Ｆｕ－ｄｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｌｉａｏｎｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ，１　１６０２９，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ｔｈｉｓ　ｐａｐｅｒ　ｓｕｇｇｅｓ￣ａ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｍａｒｇｉｎ　ｃｏｎｃｅｐｔ　ｗｈｉｃｈ　ｃｏｎｓｔｒｕｃｔｓ　ｔｈｅ　ｃｏｎｃｅｐｔ　ｌａｔ　ｔｉｃｅ　ｗｉｔｈ　ｔｈｅ　ｈｉｅｒａｒｃｈｉｃａｌ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｔｈｅ　ｌａｔｔｉｏｅ　ｔｈｒｏｕｇｈ　ｃｏｍｐｕｔｉｎｇ　ｔｈｅ　ｉｎｔｅｒｓｅｃｔｉｏｎ　ａｎｄ　ｕｎｉｏｎ　ｏｆ　ｔｈｅ　ｉｎｔｅｎｔ　ａｎｄ　ｅｘｔｅｎｔ　ｏｆ　ｌｈｅ　ａｌｒｅａｄｙ　ｃｏｎｃｅｐｔｓ．Ｃｏｍｐａｒｉｎｇ　ｗｉｔｈ　ｔｈｅ　ｏｔｈｅｒ　ａｌｇｏｒｉｈｔｍｓ，ｔｈｉｓ　ｍｅｔｈｏｄ　ｗｉｌｌ　ｎｏｔ　ｄｅｐｅｎｄ　ｏｎ　ｔｈｅ　ｃｏｎｔｅｘｔ　ａｆｔｅｒ　ｉｆｎｄ　ｉ　ｎｇ　ａｌｌ　ｔｈｅ　ｍａｒｇｉｎ　ｃｏｎｃｅｐｔｓ．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ａｌｓｏ　ｃａｎ　ｓｏｌｖｅｄ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｉｎｄｉｒｅｃｔ　ｃｏｎｃｅｐｔｓ．　Ｆｉｎａｌｌｙ，ｔｈｅ　ｉｎｓｔａｎｃｅ　ｅｘｐｌａｉｎｓ　ｔｈｅ　ｒｅａｌｉｚａｔｉｏｎ　ｐｒｏｃｅｓｓ　ａｎｄ　ｔｈｅ　ｖａｌｉｄｉｔｙ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ．　ＫＥＹ　ＷＯＲＤＳ：ｃｏｎｃｅｐｔ　ｌａｔｔｉｃｅ；ｍａｔｉｎ　ｃｏｎｃｅｐｔ；ｐｒｏｄｕｃｔ　ｃｏｎｃｅｐｔ；ｈｉｅｒａｒｃｈｉｃ　（责任编辑：杨耕文）