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 has a quite visual image in Hasse picture. Since the proposed algorithm only concerns unique upper-neighbor concepts, it can be finished by simply conducting some intersection calculation on context with no need to seek all the concept lattices. Therefore, the time and the space complexities of the proposed algorithm is still polynomial.
[1] Wille R. Restructuring Lattice Theory: An Approach Based on Hi-erarchies of Concepts∥ Proc of the 7th International Conference on Formal Concept Analysis. Darmstadt, Germany, 2009: 314-339 [2] Chen Xiang, Wu Yue. Mining Association Rules of Geographic Information System Based on Concept Lattice. Journal of Computer Applications, 2011, 31(3): 686-689 (in Chinese) (陈 湘,吴 跃.基于概念格挖掘GIS中的关联规则.计算机应用, 2011, 31(3): 686-689) [3] Xie Liming, Li Jianmin. Application Research of Concept Lattice in Intrusion Detection. Computer Engineering and Design, 2010, 31(5): 979-981, 998 (in Chinese) (谢丽明,李建民.概念格在入侵检测中的应用研究.计算机工程与设计, 2010, 31(5): 979-981, 998) [4] Yin Junhua, Li Guangqiang, Chen Yi, et al. A Spatial Clustering Method Based on Concept Lattices. Computer Systems and Applications, 2011, 20(6): 103-108 (in Chinese) (殷俊华,李光强,陈 翼,等.基于概念格的空间聚类方法.计算机系统应用, 2011, 20(6): 103-108) [5] Shen Le, Wang Liming. Analysis of Stability-Based Concept Lattice for Mining Folksonomy. Computer Engineering and Design, 2012, 33(3): 1213-1217 (in Chinese) (申 乐,王黎明.概念格稳定性分析及其在Folksonomy中的应用.计算机工程与设计, 2012, 33(3): 1213-1217) [6] He Yunqiang, Li Jianfeng. Permission Management of RBAC Based on Concept Lattice. Journal of Henan University: Natural Science, 2011, 41(3): 308-311 (in Chinese) (何云强,李建凤.RBAC中基于概念格的权限管理研究.河南大学学报:自然科学版, 2011, 41(3): 308-311) [7] Xu Jiaqing, Peng Xin, Zhao Wenyun. An Evolution Analysis Me-thod Based on Fuzzy Concept Lattice and Source Code Analysis. Chinese Journal of Computers, 2009, 32(9): 1832-1844 (in Chinese) (许佳卿,彭 鑫,赵文耘.一种基于模糊概念格和代码分析的软件演化分析方法.计算机学报, 2009, 32(9): 1832-1844) [8] Li Lifeng, Zhang Dongxiao. The Application of Concept Lattice Theory in the Reduction of the Proposition Set in Two-Valued Propositional Logic. Acta Electronica Sinica, 2007, 35(8): 1538-1542 (in Chinese) (李立峰,张东晓.概念格在二值命题逻辑命题集约简中的应用.电子学报, 2007, 35(8): 1538-1542) [9] Ganter B, Wille R. Formal Concept Analysis Mathematical Foundations. Berlin, Germany: Springer, 1999 [10] Zhang Wenxiu, Wei Ling, Qi Jianjun. Attributes Reduction of Concept Lattice-Theory and Methods. Science in China: Series E, 2005, 35(6): 628-639 (in Chinese) (张文修,魏 玲,祁建军.概念格的属性约简理论与方法.中国科学:E辑, 2005, 35(6): 628-639) [11] Wu Zhenxing. A Method of Semantic Similarity Computing Based on Attributes Reduction of Concept Lattice. Journal of Qiongzhou University, 2012, 19(2): 43-46 (in Chinese) (伍振兴.一种基于概念格属性约简的语义相似度计算方法.琼州学院学报, 2012, 19(2): 43-46) [12] Yan Li, Liu Penghui. Reduction of Attributes Based on Formal Concept Analysis. Journal of Xihua University: Natural Science, 2012, 31(4): 37-41 (in Chinese) (晏 力,刘鹏慧.基于形式概念分析的属性约简.西华大学学报:自然科学版, 2012, 31(4): 37-41) [13] Ren Miaomiao, Jiang Shuo, Wei Ling. Attribute Reduction in Concept Lattices Based on ECII Algebra. Journal of Guangxi University: Natural Science, 2011, 36(5): 802-807 (in Chinese) (任苗苗,蒋 硕,魏 玲.基于ECII代数的概念格属性约简.广西大学学报:自然科学版, 2011, 36(5): 802-807) [14] Lü Yuejin, Liu Hongmei. Improved Algorithm for Attribute Redu-ction on Concept Lattice. Computer Engineering and Applications, 2011, 47(8): 146-148 (in Chinese) (吕跃进,刘洪梅.改进的概念格属性约简算法.计算机工程与应用, 2011, 47(8): 146-148) [15] Sun Yuwei, Wang Dahui, Qiu Daiyuan. Attribute Reduction of Concept Lattice Based on Include-Operation. Journal of Science of Teachers' College and University, 2010, 30(6): 17- 19, 25 (in Chinese) (孙昱薇,王大辉,仇代远.基于包含运算的概念格属性约简.高师理科学刊, 2010, 30(6): 17- 19, 25) [16] Lin Peirong, Zhang Qisen, Li Jinjin. Concept Lattice Attribute Reduction Based on Intersectional Reducible Equivalence Class. Pa-ttern Recognition and Artificial Intelligence, 2010, 23(5): 720-726 (in Chinese) (林培榕,张其森,李进金.基于交可约等价类的概念格属性约简.模式识别与人工智能, 2010, 23(5): 720-726) [17] Gui Xiancai. Multi-Layered Attribute Reduction in Concept Lattice Based on Discernibility Matrix. Computer Engineering, 2010, 36(21): 76-77, 80 (in Chinese) (桂现才.基于差别矩阵的概念格多层次属性约简.计算机工程, 2010, 36(21): 76-77, 80) [18] Yang Sichun, Zhang Wei. Improved Method for Judgment of Consistent Sets in Concept Lattice. Journal of Shanxi University: Natural Science, 2010, 33(1): 67-70 (in Chinese) (杨思春,张 伟.改进的概念格协调集判定.山西大学学报:自然科学版, 2010, 33(1): 67-70) [19] Gong Weiming, Ma Yuan. Attribute Reduction Algorithm of Concept Lattices Based on Maxmode. Computer Engineering and Design, 2009, 30(24): 5650-5652, 5657 (in Chinese) (龚卫明,马 垣.基于最大模的概念格属性约简算法.计算机工程与设计, 2009, 30(24): 5650-5652, 5657) [20] Zhou Liangliang. A Reduction Method of Visual Words Based on Concept Lattice. Computer Development and Applications, 2012, 25(9): 15-17 (in Chinese) (周亮亮.基于概念格的视觉单词约简方法.电脑开发与应用, 2012, 25(9): 15-17) [21] Xie Chunli, Liu Yongkuo. Research on Attribute Reduction Algorithm of Concept Lattice Theory. Transducer and Microsystem Technologies, 2012, 31(3): 116-118 (in Chinese) (谢春丽,刘永阔.概念格理论属性约简算法研究.传感器与微系统, 2012, 31(3): 116-118) [22] Liu Yongkuo, Xie Chunli, Xia Hong. Research on Faults Data Processing and Attributes Reduction Arithmetic Based on Data Mining for Nuclear Power Plants. Nuclear Power Engineering, 2010, 31(5): 24-27, 38 (in Chinese) (刘永阔,谢春丽,夏 虹.基于数据挖掘的核动力装置故障数据处理及属性约简算法研究.核动力工程, 2010, 31(5): 24-27, 38) [23] Wu Zhenxing, Ouyang Liubo, Lan Xiaofei, et al. Ontology Merging Method Based on Attributes Reduction of Concept Lattice. Computer Systems and Applications, 2010, 19(9): 232-235 (in Chinese) (伍振兴,欧阳柳波,兰小飞,等.一种基于概念格属性约简的本体合并方法.计算机系统应用, 2010, 19(9): 232-235) [24] Guo Songtao, Li Jinhai, Lü Yuejin, et al. Heuristic Attribute Reduction Algorithm for Decision Formal Contexts. Computer Engineering and Applications, 2012, 48(10): 20-24 (in Chinese) (郭松涛,李金海,吕跃进,等.决策形式背景的启发式属性约简算法.计算机工程与应用, 2012, 48(10): 20-24) [25] Huang Jiazeng. Based on Rough Concept Lattice Attribute Reduction and Rule Acquisition. Software, 2011, 32(10): 16-19, 23 (in Chinese) (黄加增.基于粗糙概念格的属性约简及规则获取.软件, 2011, 32(10): 16-19, 23) [26] Pei Duo, Mi Jusheng, Li Meizheng. Type-irr Attribute Reduction in Decision Formal Concept. Journal of Frontiers of Computer Science and Technology, 2011, 5(1): 75-80 (in Chinese) (裴 铎,米据生,李美争.决策形式背景的irr-型属性约简.计算机科学与探索, 2011, 5(1): 75-80) [27] Hu Xuegang, Xue Feng, Zhang Yuhong, et al. Attribute Redu-ction Methods of Decision Table Based on Concept Lattice. Pattern Recognition and Artificial Intelligence, 2009, 22(4): 624-629 (in Chinese) (胡学钢,薛 峰,张玉红,等.基于概念格的决策表属性约简方法.模式识别与人工智能, 2009, 22(4): 624-629) [28] Yang Bin, Xu Baowen. Distributive Reduction of Attributes in Concept Lattice. Journal of Computer Research and Development, 2008, 45(7): 1169-1176 (in Chinese) (杨 彬,徐宝文.分布式概念格的属性约简研究.计算机研究与发展, 2008, 45(7): 1169-1176) [29] Meng Huili, Li Shuangqun, Xu Jiucheng. The Heuristic Attribute Reduction of Concept Lattice Based on Concept Background. Journal of Henan Normal University: Natural Science, 2012, 40(1): 154-157 (in Chinese) (孟慧丽,李双群,徐久成.基于概念背景的概念格启发式属性约简.河南师范大学学报:自然科学版, 2012, 40(1): 154-157) [30] Zhao Rongyong, Zhang Hao, Li Cuiling, et al. Disjunctive Normal Form Generation Algorithm for Discernibility Function in Rough Set Theory. Computer Engineering, 2006, 32(2): 183-185 (in Chinese) (赵荣泳,张 浩,李翠玲,等.粗糙集理论中分辨函数的析取范式生成算法.计算机工程, 2006, 32(2): 183-185)