形式概念中的内涵亏值及属性约简-模式识别与人工智能.pdfVIP

第26 卷摇 第 12 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 模式识别与人工智能摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Vol.26摇 No.12 摇 2013年12月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 PR AI摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Dec.摇 摇2013 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 形式概念中的内涵亏值及属性约简 马摇 垣 (辽宁科技大学 软件学院摇 鞍山114051) 摘摇 要摇 属性约简一直是概念格领域研究的热门话题.文中借助内涵亏值的思想证明在每个唯一上近邻概念的内 涵亏值中各任取一个元素组成的集合就是一个约简,从而给出一个求全部约简的简单算法,并且这个算法在Hasse 图中有较直观的形象.由于该算法只涉及唯一上近邻概念,所以不需求出全部概念格,只需对背景进行一些并交运 算即可全部完成,因此算法的时间复杂度及空间复杂度都是多项式的. 关键词摇 概念格,内涵亏值,唯一上近邻,属性约简 中图法分类号摇 TP 181 Intent Waned Values and Attribute Reduction in Format Concept MA Yuan (School of Software,University of Science and Technology LiaoNing,Anshan 114051) ABSTRACT Attribute reduction is a hot topic in the area of concept lattice. The idea of intent waned values is used to prove that the set composed of arbitrary elements taken from intent waned values of each unique upper鄄neighbor concept is a reduction,thereby providing a simple algorithm of seeking all reductions, and this algorithm hasa quite visual image in Hasse picture. Since the proposed algorithm only concerns unique upper鄄neighbor concepts,it canbefinishedby simply conducting someintersection calculationon context with no need to seek all the concept lattices. Therefore,the time and the space complexities of the proposed algorithm is still polynomial. Key Words摇 Concept Lattice,Intent Waned Value,Unique Upper Neighbor,Attribute Reduction 1摇 引摇 言 限管理、软件演化分析、命题逻辑约简等很多领 域[2-8] 都取得有效的应用.在这些应用中,多数场合 [1] 都要求形式背景是既约的. 形式概念的理论是Wille 于1982 年提出的, 现已在虚拟企业、电子