分布式概念格的属性约简研究

Distributive Reduction of Attributes in Concept Lattice

概念格的属性约简是形式化概念分析理论的重要研究内容之一.传统的格属性约简方法主要是针对非分布式环境下单个形式背景的,而随着数据分布存储和处理的广泛应用,研究基于分布式环境下概念格的属性约简具有重要的意义.为此,提出属性的超集和确定集的概念,刻画了形式背景中不同类型属性的局部特征与全局特征,推导出属性约简的判定定理;在此基础上,给出计算分布式环境下概念格属性约简的ADSCL和DRCL算法.ADSCL算法用于计算属性的超集和最小确定集,这些约简信息将作为DRCL算法的输入,以计算得到全局形式背景的约简.理论分析和实验结果表明,该算法是有效可行的.

Attribute reduction is one of the key problems in formal concept analysis.A few approaches have been proposed but they are only applicable to formal context in a non-distributed environment.With the wide application of distributed data storage and processing,it is necessary to develop a method to adapt to this environment.To address this problem,the characterizations of different kinds of attributes are provided from the point of view of global context and local context.The notion of super set and consistent set are introduced to determine whether an attribute is reducible in a global context.The determinant theorem of attribute reductions is derived based on core attributes and dispensable attributes.Based on these results,two algorithms are designed to compute attribute reductions of context in a distributed environment.The first algorithm,DRCL,determines attribute reductions of global context.The local reductions can be computed by using the existing approaches.The second algorithm,ADSCL,determines the super sets and all minimal consistent sets for the attributes given by a context.This information is required by the first algorithm.Theory analysis and experimental results show the feasibility and effectiveness of the two algorithms.