基于多属性同步消减的概念格构造算法  

Algorithms of Constructing Concept Lattice Based on Deleting Multiple Attributes Synchronously

作　　者：姜琴[1] 张卓[1] 王黎明[1] 

机构地区：[1]郑州大学信息工程学院,郑州450051

出　　处：《小型微型计算机系统》2016年第4期646-652,共7页Journal of Chinese Computer Systems

基　　金：国家青年科学基金项目(61303044)资助

摘　　要：渐进式算法是概念格构造的一类重要算法,目前有关属性消减的渐进式构造概念格算法效率并不高.针对这一情况,在原有概念格的基础上提出渐进式同步消减多个属性得到新概念格的构造算法,文中采用自底向上广度优先和自顶向下深度优先遍历格中节点,若当前节点内涵中含有消减属性,直接消去其内涵和父节点内涵所含有的全部消减属性,然后判断其内涵与父节点内涵是否一致,分析当前节点类型以做相应处理.新概念格中的节点是由原有概念格中的节点直接修改而来,并不产生新的概念(外延没有变化).本文从理论上和UCI与随机生成的数据集上进行的实验表明,两种算法是正确的,算法对于处理格规模庞大且消减属性个数较多时有较好的时间性能.Incremental algorithms for the construction of concept lattice are of key importance,The efficiency of incremental obtaining newconcepts by deleting one or more attributes from the old concept lattice is not high at present,Based on this,deleting multiple attributes synchronously which based on the original concept lattice is proposed to obtain the newconcept lattice,We use two ways called bottom-up（ breadth first search） and top-down（ depth first search） to visit the concepts in the original lattice,If the intent of the current concept contains decremantal attributes,we would delete all decremental attributes contained in it and so do it as its parents,Then we will judge whether its intent is equal to the intent of its parents and analyze its type to do the corresponding action for getting the newconcept lattice,The concepts of the newlattice are obtained by modifying the intents of concepts of the original lattice directly without producing the newconcepts whose extents have been changed,This paper has been proved its correctness and its high efficiency especially for large concept lattice and the large size of decremental attributes from theory and its implementations which rely on UCI data and random data.

关 键 词：概念格 算法 属性渐减 自底向上 自顶向下 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]