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

【Abstract】 As an important tool in the theory of formal concept analysis, the attribute exploration algorithm is problem-oriented and can interactively discover system knowledge step by step, which plays a central role in knowledge discovery and acquisition.However, if the size of formal context is large, the calculation process of attribute exploration algorithm will spend too much time to restrict seriously the promotion and application of the algorithm in the current era of big data.The bottleneck of time-consuming mainly lies in "finding the next problem to interact with experts",traditional algorithms have a lot of redundant computation in this process.Aiming at this problem, three theorems are put forward and proved based on analyzing the logic relation between pseudo-intent, intent and implication set.According to these theorems, an attribute exploration algorithm based on an unrelated collection is given.During pseudo-intent and intent calculation, this algorithm, by means of the proposed theorems, can skip the process of determining whether or not an attribute set that violates the logical relationship is a pseudo-intent or intent, so as to reduce the search space and time complexity of the algorithm.The best time is O(mn~2P~2),the worst time is O(mn~3P~2).The experi-mental results show that the proposed algorithm has an obvious time performance advantage compared with the traditional algorithm.更多还原