基于不相关属性集合的属性探索算法

摘要：

作为形式概念分析理论中的一个重要工具,属性探索算法能够以问题为导向,交互式地逐步发现系统知识,在知识的发现和获取中居于核心地位.但是,当形式背景的规模较大时,属性探索算法的计算过程过于耗时,严重制约了算法在当前大数据时代的推广与应用.耗时瓶颈主要存在于"寻找下一个与专家交互的问题"这一环节,传统算法在此过程中存在大量冗余计算.针对这个问题,在分析伪内涵和内涵与蕴涵集合的内在逻辑关系的基础上,提出并证明了3个定理,根据定理给出了一种基于不相关属性集合的属性探索算法,该算法在计算伪内涵与内涵的过程中,借助提出的定理,跳过违反该逻辑关系的属性集合是否为伪内涵或者内涵的判断过程,减小了算法的搜索空间,从而降低了算法的时间复杂度.所提算法最好的时间复杂度为O(mn 2 P 2),最坏的时间复杂度为O(mn 3 P 2).实验结果表明,与传统算法相比,该算法具有较为明显的时间性能优势.

关键词：形式概念分析、伪内涵、关联规则、属性探索、概念格、知识发现

所属期刊栏目：48

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;河南省科技厅科技攻关计划基金;河南省高等学校青年骨干教师培养计划项目;河南省高等学校重点科研项目

在线出版日期：2021-04-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：54-62