Mining Algorithm for Minimal Rule Based on Concept Lattice
QIU Wei-Gen
Computer Faculty, Guangdong University of Technology, Guangzhou 510090 State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084
Abstract:The concept lattice is an important mathematic tool for knowledge treatment and data analysis, its efficient construction algorithm is significant in rules acquisition of decision table. In this paper, the formal context and concept lattice model of decision table are constructed, the relationships among the extended indistinguishable matrix, concept lattice and minimal rule are analyzed. All the concept node intension comes from property element of extended indistinguishable matrix and all the condition properties of optimal decision rule are from the intension reduction of a concept lattice node. Two algorithms are developed for constructing the corresponding concept lattice incrementally and acquisition of minimal decision rule based on the concept lattice, and their simplicity and efficiency are proved by an enterprise example.
[1] Agrawl R, Imieliński T, Swami A. Mining Association Rules between Sets of Items in Large Databases // Proc of the ACM SIGMOD International Conference on Management of Data. Washington, USA, 1993: 207-216 [2] Hu Keyun, Lu Yuchang, Shi Chunyi. Advances in Concept Lattice and Its Application. Journal of Tsinghua University: Natural Sciences, 2000, 40(9): 77-81 (in Chinese) (胡可云,陆玉昌,石纯一.概念格及其应用进展.清华大学学报:自然科学版, 2000, 40(9): 77-81) [3] Wang Zhihai, Hu Keyun, Hu Xuegang, et al. General and Incremental Algorithms of Rule Extraction Based on Concept Lattice. Chinese Journal of Computers, 1999, 22(1): 66-70 (in Chinese) (王志海,胡可云,胡学钢,等.概念格上规则提取的一般算法与渐进式算法. 计算机学报, 1999, 22(1): 66-70) [4] Xie Zhipeng, Liu Zongtian. Concept Lattice and Association Rule Discovery. Journal of Computer Research and Development, 2000, 37(12): 1415-1421 (in Chinese) (谢志鹏,刘宗田.概念格与关联规则发现.计算机研究与发展, 2000, 37(12): 1415-1421) [5] Li Jinyang, Shen Hong, Topor R. Mining Optimal Class Association Rule Set // Proc of the Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Hongkong, China, 2001: 364-375 [6] Xie Zhipeng, Liu Zongtian. A Fast Incremental Algorithm for Building Concept Lattice. Chinese Journal of Computers, 2002, 25(5): 490-496 (in Chinese) (谢志鹏,刘宗田.概念格的快速渐进式构造算法. 计算机学报, 2002, 25(5): 490-496) [7] Zhang Jifu, Zhang Sulan, Zheng Lian. Weighted Concept Lattice and Incremental Construction. Pattern Recognition and Artificial Intelligence, 2005, 18(2): 171-176 (in Chinese) (张继福,张素兰,郑 链.加权概念格及其渐进式构造. 模式识别与人工智能, 2005, 18(2): 171-176) [8] Sun Guozi, Yu Dingwen, Wu Zhijun. Research on Global Product Structure Model Based on Rough Set. Chinese Journal of Computers, 2005, 28(3): 392-401 (in Chinese) (孙国梓,郁鼎文,吴志军.基于粗糙集的全局产品结构模型研究.计算机学报, 2005, 28(3): 392-401)