计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于下确界不可约的概念格属性约简方法

吴杰 a,梁妍 b,马垣 a   

  1. (辽宁科技大学 a.软件学院; b.应用技术学院,辽宁 鞍山 114051)
  • 收稿日期:2015-11-12 出版日期:2016-11-15 发布日期:2016-11-15
  • 作者简介:吴杰(1981—),男,讲师、博士研究生,主研方向为数据挖掘、数据库技术、形式概念分析;梁妍,讲师、硕士;马垣,教授、博士、博士生导师。
  • 基金项目:
    辽宁科技大学青年基金“基于粒计算的概念格约简方法研究”(2014QN21)。

Attribute Reduction Method of Concept Lattice Based on Infimum Irreducibleness

WU Jie  a,LIANG Yan  b,MA Yuan  a   

  1. (a.School of Software; b.School of Applied Technology, University of Science and Technology Liaoning,Anshan,Liaoning 114051,China)
  • Received:2015-11-12 Online:2016-11-15 Published:2016-11-15

摘要: 对概念格的属性约简方法进行研究。证明概念格中任意属性亏值都为可辨识属性集,下确界不可约概念的属性亏值集合与全部属性亏值集合的辨识函数具有相同的最小析取范式,概念元素为下确界不可约概念当且仅当其必为属性概念,并且每个属性概念的属性亏值中任取一 个元素构成的集合必定是一个属性约简。在上述研究的基础上,提出一种针对大背景概念格快速获得全部属性约简的方法,并给出相应算法,证明其时间复杂度与空间复杂度都是多项式形式。分析结果表明,该方法无苛刻条件,化简幅度较大,运行时间快,具有较好的约简效果 。

关键词: 概念格, 属性亏值, 最小析取范式, 下确界不可约, 属性概念, 属性约简

Abstract: This paper researches on attribute reduction method of concept lattice.It proves that any attribute defective value of concept lattice is a discernible attribute set.It also proves that discernibility functions for attribute defective values set of infimum irreducible concepts and all attribute defective value set have the same minimum disjunction normal form.Meanwhile,this paper proves that concept element is an infimum irreducible concept if and only if it is an attribute concept.The set composed of arbitrary elements taken from attribute defective values of each attribute concept definitely is an attribute reduction.A rapid method is presented for obtaining all attribute reductions of concept lattice from the large context based on the existing correlative method and corresponding algorithm is given.The time and space complexity of the algorithm are proved in the polynomial form.Analysis result shows that the proposed method has the advantages of no harsh terms,wide reduction range,short running time and good reduction effect.

Key words: concept lattice, attribute defective value, minimal disjunction normal form, infimum irreducibleness, attribute concept, attribute reduction

中图分类号: