概念格上规则提取的一般算法与渐进式算法  

GENERAL AND INCREMENTAL ALGORITHMS OF RULE EXTRACTION BASED ON CONCEPT LATTICE

作　　者：王志海[1] 胡可云[1] 胡学钢[1] 刘宗田[1] 张奠成[1] 

机构地区：[1]合肥工业大学计算机与信息学院人工智能应用研究室

出　　处：《计算机学报》1999年第1期66-70,共5页Chinese Journal of Computers

基　　金：国家教委博士点基金;安徽省自然科学基金

摘　　要：许多研究表明概念格是数据分析与规则提取的一种有效工具．本文首先提出一种在对象与描述符数目较多、概念聚类具有一定规模条件下，在已建造好的概念格上有效地提取规则的算法．这种方法主要依据格结点的直接泛化来产生相应无冗余规则；然后改进了一种渐进式更新概念格与相应Ｈａｓｓｅ图的算法，并将之应用于渐进式提取规则．目前，这些方法已用于我们所开发的数据库知识发现工具原型系统中．Many researches have shown that concept lattice (Galois lattice) is an efficient tool for data analysis and rule extraction. It is convenient to model dependence and casualty,and provide a vivid and concise account of the relations among the variables in the universe of discourse.The paper proposes an algorithm that can extract rules from built lattice efficiently.The basic idea is to generate all non redundant rule of each single node by examining the number and content of their parent nodes.If the average number of descriptors of objects is K ,and the average number of parents of objects is d , the time complexity of algorithm is O(K d‖O‖) .When the number of descriptors of node is relatively large,the algorithm is better than the algorithm in Missaoui′s paper(1994) whose time complexity is O(2 K‖O‖ ).In particular when the amount of object is large and the size of conceptual clustering is big,that is ,most of nodes in lattice have relatively few parent nodes,the algorithm shows much better performance.The paper also improves an incremental concept formation algorithm based on concept lattice and applies it to the incremental rule generation.In the process of undating a concept lattice incrementally,the new method to find the parent node of a new node is given.These algorithms have been used in authors' KDD tools system.

关 键 词：概念格 GALOIS格 规则 知识发现 算法 数据库 

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