一种基于树图的属性约简算法

An Algorithm Based on Tree Graph for Calculation for Attribute Reduction

针对基于概念格对数据的规则挖掘中,概念格结构的复杂度随着形式背景的复杂化呈指数递增的问题,本文从树图的角度研究决策形式背景的属性约简问题,以树型结构为基础,首先提出了新的强弱背景的判定方法;进一步定义了条件树对象集与决策外延的相关函数,并以此作为启发信息,设计了基于树图的逐层属性约简算法,避免了计算区分矩阵这个既消耗时间又消耗空间的过程;最后在属性约简树的基础上,给出了约简后的概念树生成算法,以简洁、直观的概念树的代替错综复杂的概念格.理论分析和实验结果表明,该算法是有效可行的.

Based on lattice in rules mining, to address the problem that the complexity of lattice structure increase exponentially with the complicated of data. Attribute reduction in formal context is proposed in terms of tree graph. Firstly, based on the structure of tree, a new method of judging the context that strong and weak is proposed, on the basis of that, define a related function between the node of condition tree and the decision concept, then the formula measuring node importance is used as heuristic information to design an efficient attribute reduction algorithm based on the tree graph, and avoid the process of computing discernibility matrix with timeconsuming and space-consuming; finally, an algorithm to generate concept tree after reduction is presented, so the concise, intuitive concept tree replaces the concept lattice. Theoretical analysis and experimental results show that the algorithms of this paper are efficient and effective.