近似概念格及其增量构造算法研究*

针对传统概念格处理不完备信息的局限,给出了处理形式背景有缺值现象的概念格扩展模型———近似概念格,在此基础上提出改进的概念格增量构造算法。该算法引入哈希技术和最近父节点的增量计算方法,从加速定位生成元和更新边这两个关键过程改进Godin算法。采用随机数据集设计实验,实验表明,改进的算法可有效提高对形式背景有缺值现象概念格的建格效率,尤其是对数据规模和发生关系概率较大的数据集,算法的高效性更明显。

Approximation concept lattice and incremental constructing algorithm

The classic concept lattice is limited in incomplete information. In order to solve this limitation,presented a new concept lattice model-approximation concept lattice, witch could be used to deal with missing-value in formal context. On that basis, it designed an improved incremental constructing algorithm based on hash technique and incremental computation of nearest father nodes. Extensive experiments on the random data set demonstrate the improvements of the construction efficiency, especially for the data sets with large scale and density.