对概念格的属性约简方法进行研究。证明概念格中任意属性亏值都为可辨识属性集,下确界不可约概念的属性亏值集合与全部属性亏值集合的辨识函数具有相同的最小析取范式,概念元素为下确界不可约概念当且仅当其必为属性概念,并且每个属性概念的属性亏值中任取一个元素构成的集合必定是一个属性约简。在上述研究的基础上,提出一种针对大背景概念格快速获得全部属性约简的方法,并给出相应算法,证明其时间复杂度与空间复杂度都是多项式形式。分析结果表明,该方法无苛刻条件,化简幅度较大,运行时间快,具有较好的约简效果.
概念格是隶属数学概念和概念层次结构的应用数学领域[1],理论上结构严格,能形象地描述事物之间的特化与泛化,在空间聚类方法、病症智能诊断、Folksonomy、信息修复与文件浏览、软件演化分析、访问权限管理、命题集约简等诸多领域都有成功的应用。虽然概念格应用广泛,但是一个形式背景中概念的个数是随着背景的尺寸指数级增长的[2],这样一旦形式背景稍大,概念个数的计算就相当困难,影响实际应用。因此,要求形式背景是既约的就显得非常重要。对概念格进行约简的主要方向有:确保概念格同构的约简[3],确保对象等价类不变的约简[4],确保对象概念外延不变的约简[5],确保决策规则完备的约简[6]。这些约简方法化简幅度都很小,即使是大背景基于同构的约简可能也只减少几个属性;而且,这些约简是由格的结构决定的,而不是按照用户的需求决定的,并且只有一个层次。另外,可能的约简有很多个,要全部找出可能的约简,计算次数是形式背景尺寸的指数级。这些约简方法构思独特,但却不适合作为大背景约简工具。近年来对背景的约简也提出了很多新思想和新方法。例如决策背景下的属性约简方法[7]、基于支撑函数的属性约简方法[8]、利用辨识矩阵计算全部外延覆盖约简的方法[9]、利用最大模的计算方法[10]、基于覆盖度函数的方法[11]、利用交可约等价类的运算方法[12]、运用交式可约元概念进行属性约简的方法[13]等。文献[3]给出了利用辨识函数求得属性约简的一种重要方法:对于给定的背景K,求出其可辨识属性集,进一步求出可辨识属性矩阵,并得到一个辨识函数,最后将辨识函数利用吸收律与分配律变为最小析取范式,则其中的每个合取项就为背景K的一个属性约简。文献[3]算法为指数级的,背景的概念数目随着背景尺寸指数级增长,背景K尺寸稍大,求出其所有属性约简就相对困难,而且文献[3]的方法较抽象,在概念格Hasse图中无直观的图像。
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
全部0条评论
快来发表一下你的评论吧 !