大数据集背景下概念格的多粒度构造和存储研究

Due to the completeness of concept lattice，construction time and the number of nodes are increasing at an exponential rate with the increase of the size of foraml context. This has become a bottleneck problem of restricting the application of concept lattice. In the big data days, research on this issue is more urgent. Based on the idea of granular computing, this program intends to research constructing methods and storage methods of concept lattice corresponding to formal context of big data. This provides theoretical basis and algorithms guidance to solve constructing methods and storage methods of concept lattice. Firstly, this program clears the mapping relationship between granulation of concept lattice and complete lattice, analyzes mapping relationship between partial orders of granular lattices and globe lattice and mapping relationship between granular lattices in different granular layers; Secondly, decomposes concept lattice into granular lattices with different granularity in corresponding layers, converts construction of concept lattice to distribution construction based on progressive refinement, and builds multi-granulations computing model of concept lattice; Finally, builds distributed computing environments， constructs granular lattice by algorithm of granular construction, refines granulations by algorithm for converting granular layer, and rebuilds Hasse graph of concept lattice by algorithm for merge granular. The main points of the problem is graining concept lattice. The main result of this study provides theoretical basis and algorithms model for distributed construction of multi-granulations concept lattice, has great significance in both theory and practice to research and application of formal concept analysis in big data days.

概念格的完备性导致构造时间和空间需求随形式背景规模的增长呈指数级增大，无法满足大数据分析的需求。本项目将多粒度计算与概念格构造相融合，借助分布式和渐进式方法，拟提出针对大形式背景的概念格构造和存储方法，为解决大数据背景下的概念格构造问题提供理论依据和算法指引。本项目首先明确概念格的粒度划分与完备格之间的映射关系，分析粒子格与完整概念格之间偏序关系的映射关系，以及不同粒层上粒子格的映射关系；其次将概念格分解成不同粒度层次的粒子格，将概念格的构造转化为按粒度逐步求精的分布式构造，建立概念格的多粒度计算模型；最后，在上述研究基础上，构建分布式计算环境，利用粒子构造算法构造粒子格，粒层转换算法细化粒度，粒子合并算法重建概念格的Hasse 图。本项目的重点是对概念格的粒化，研究结果为多粒度概念格的分布式构造提供理论依据和算法模型，对促进大数据时代形式概念分析的研究和应用具有重要的理论意义和实用价值。

概念格在数据聚类和层次分析方面有着独特的优势。但概念格自身的完备性，使得概念格在大数据时代数据分析和处理面临着构造和存储困难的制约。本项目将多粒度计算理论引入概念格的构造过程，研究概念格的概念分层次构造和存储，以降低概念格构造对时间和空间的要求，取得了令人满意的研究成果。在本项目的研究中，首先基于概念格的概念层次结构与粒计算的粒度结构之间的天然关系来建立数学模型，然后将概念格分解成不同粒度层次的粒子格，对于每层都可以逐步细化为一个更底层的概念格，使得格的构造转化为按粒度逐步求精的分布式构造。最后建立了一个分布式环境下概念格的多粒度构造与存储模型，并将该模型应用到海量气象信息数据挖掘、大规模访问控制数据的角色挖掘、大规模无线传感器网络的权限规则发现及认证之中。