Based on rectangle theory of formal concept and set covering theory, the concept reduction preserving binary relations is investigated in this paper. It is known that there are three types of formal concepts: core concepts, relative necessary concepts and unnecessary concepts. First, we present the new judgment results for relative necessary concepts and unnecessary concepts. Second, we derive the bounds for both the maximum number of relative necessary concepts and the maximum number of unnecessary concepts and it is a difficult problem as either in concept reduction preserving binary relations or attribute reduction of decision formal contexts, the computation of formal contexts from formal concepts is a challenging problem. Third, based on rectangle theory of formal concept, a fast algorithm for reducing attributes while preserving the extensions for a set of formal concepts is proposed using the extension bit-array technique, which allows multiple context cells to be processed by a single 32-bit or 64-bit operator. Technically, the new algorithm could store both formal context and extent of a concept as bit-arrays, and we can use bit-operations to process set operations "or" as well as "and". One more merit is that the new algorithm does not need to consider other concepts in the concept lattice, thus the algorithm is explicit to understand and fast. Experiments demonstrate that the new algorithm is effective in the computation of attribute reductions.
翻译:基于正式概念的矩形理论和涵盖理论的设定,本文件对保留二进制关系的概念进行了调查,并知道存在三种正式概念:核心概念、相对必要概念和不必要的概念。首先,我们提出相对必要概念和不必要概念的新判断结果。第二,我们从相对必要概念的最大数量和不必要概念的最大数量中得出新的判断结果。从技术上讲,新的算法可以储存一个概念的正式背景和范围,例如,在保留二进制关系或决定正式背景的属性方面,从正式概念中计算正式背景是一个具有挑战性的问题。第三,基于正式概念的矩形理论,一种在保留一套正式概念的扩展的同时减少属性的快速算法正在使用扩展比拉拉技术,使多个背景单元格能够由单一32位或64位操作员处理。从技术上讲,新的算法可以储存一个概念的形式背景和范围,作为一小拉轨的概念,我们可以使用比特操作来设置操作“或”以及“和”。还有一个更大的优点是,新的算法不需要考虑新的算法中的其他概念的快速理解。因此,在精确的算算法中可以理解另一个概念是快速地解释。