基于属性的相对约简格快速渐进式构造算法

Attribute-based Fast Incremental Algorithm for Building Relative Reduced Concept Lattice

相对约简格作为简化的概念格,在数据挖掘和知识发现等领域具有广泛的应用。相对约简格的构造在其应用过程中是一个主要问题。本文提出了采用树结构对相对约简格节点进行组织,研究了基于属性的相对约简格渐进式构造算法。相对约简格节点的树结构组织可以约束更新格节点、产生子格节点及新生格节点的子结点的搜索范围,从而可以有效地减少算法的执行时间。该算法不仅为相对约简格的构造提供了一种方法,还解决了在已构造好相对约简格的前提下,增加属性所带来的更新问题。在随机生成的数据集上进行的实验测试表明,本算法的时间性能更优越。

Relative reduced concept lattice, a simplified concept lattice, can be used widely in data mining and knowledge discovery, etc. The main difficulty with relative reduced concept lattice-based system comes from the lattice construction itself. In this paper, tree structure is employed to organize the set of concepts in relative reduced concept latrice. Based on attribute, a fast incremental algorithm is developed. The organization of concepts in tree structure can reduce the search space of update concept node, generator concept node and children of new born concept node, and consequently improve the speed of the algorithm. It provides an approach for building relative reduced concept lattice and resolves the problem of lattice update caused by appending new attributes into an existing context of the lattice. The algorithm is experimental evaluated and compared for random generated data. The results show that the algorithm performance is superior.