基于形式概念分析的约简数据立方体研究

Reductive Data Cube Based on Formal Concept Analysis

数据立方体格和形式概念格比较研究表明,两者都基于序结构,并且采用形式概念分析理论(FCA)的等价特征组与数据立方体覆盖等价类对数据单元有相同的划分结果.将FCA与概念格理论引入数据立方体研究,首次提出聚集概念格(ACL)结构.ACL与一般概念格同构,能完整保存立方体中的所有聚集结果,实现与商立方体相同比例的约简.ACL结构仍比较复杂,在ACL基础上,又提出一种约简聚集概念格结构(RACL),该结构只存储非对象概念,而不是所有概念.RACL与基本表联合仍然是完整立方体结构,但能实现更大的约简.给出了ACL和RACL的高效的查询方法,并使用模拟数据和实际数据作了一些实验.理论和实验都表明RACL结构比现有方法更节省空间,同时查询效率也较高.

A comparative examination of data cube lattice and formal concept lattice shows that both of them are based on order-structure; and furthermore, equivalent character groups based on formal concept analysis （FCA） and cover equivalence classes of cells in data cube have the same partitions for data. The theories of FCA and concept lattice are introduced into the research of data cube and aggregate concept lattice（ACL） is firstly brought forward in this paper. The ACL has the same structure with original concept lattice. It can reduce data cube in same ratio with quotient cube and contain all aggregations of cube integrally. But ACL is still complex. So another reductive structure called reduetive aggregate concept lattice （RACL） is proposed, which contains only non-object concepts but not all the concepts. The RACI. combined with base table is still a fully pre-eomputed cube and can realize the reduction of data cube in higher ratio. An efficient method of query answering in ACL and RACL is proposed at the same time. Experiments are also presented by using both the synthetic and real-world data sets. The theoretic and experimental results show that the space saving in RACL is more efficient than previous ones and query is efficient too.