数据立方体格与概念格关系研究

张婷 都仪敏

摘要：数据立方体是数据仓库和联机分析处理研究领域的一种核心数据模型，而概念格是形式概念分析理论的一类重要数据结构，其在数据分析领域应用广泛，它们都属于格结构。目前，对数据立方体格与概念格之间的关系还没有进行系统研究。为此，论证了数据立方体格与概念格在结构特性上的关系。在数据立方体格与概念格关系基础上，进一步研究数据立方体格的相关分析及挖掘算法与概念格之间的互用性，分析它们在这两种数据模型之间相互应用的优越性和局限性。实验结果表明，数据立方体格与概念格在度分布、聚集系数、平均最短路径等方面具有相似性。

关键词：数据立方体格；概念格；度分布；聚集系数；平均最短路径

DOIDOI：10.11907/rjdk.173305

中图分类号：TP391

文献标识码：A 文章编号：1672-7800（2018）008-0194-04

英文摘要Abstract：Data cubes are the core data model of data warehousing and OLAP，while concept is are a kind of important data model in formal concept analysis theory and widely used in the field of data analysis.They all belong to the lattice structure.At present，the relationship between the data cube lattice and the concept lattice has not been studied systematically.Therefore，this paper demonstrates the relationship between the data cube lattice and the concept lattice in structural characteristics.On the basis of the relationship between the data cube lattice and the concept lattice，the generality of correlation analysis and mining algorithm between the data cube lattice and the concept lattice are studied，the advantages and limitations of their mutual application in the two data models are analyzed.The experimental results show that the data cube has similarity in terms of degree distribution，clustering coefficient，average shortest path and so on.

英文关键词Key Words：data cube lattice； concept lattice； degree distribution； clustering coefficient； average shortest path

0 引言

在数据挖掘、数据仓库以及知识表示、知识发现这两个紧密交叉、融合的研究领域存在两类重要的数据模型：数据立方体格[1]和概念格[2]，其实都属于格結构数据。数据立方体以符合星型模型的基本表为元组集，以维度属性为坐标轴，不同维度属性（值）的交叉构成了多维空间；该空间的每个点根据上卷、下钻的计算依赖关系构成了数据立方体。文献[3]提出了商立方体（quotient cube）概念。商立方体是压缩数据立方体的一种技术，其在保持数据立方体语义的前提下，对数据立方体采用Cover Partition技术，将其上界相同的数据单元划分为等价类。每个等价类的上界和下界被保存下来，从而实现数据立方体压缩。封闭数据立方体（closed data cube）概念见文献[4]，同样通过等价类实现数据立方体压缩，区别在于封闭数据立方体对于每个等价类只保存其上界，因此对数据立方体的压缩效率更高。文献[5]从图结构数据角度研究格结构数据的统计特性和解析模型，并进一步研究了数据立方体格结构划分方法。

德国数学家Wille R[6].于1982年基于概念和概念层次首先提出了形式概念分析（FCA）理论，其核心数据结构概念格也称Galois格，用于概念的发现、排序和显示。目前，概念格的构造方法分为批处理算法[7]和渐进式算法[8-9]。张磊等 [10]研究了当形式概念的某些属性削减后，如何快速有效地在原有概念格上进行调整，得到新形式背景的概念格，而不是传统方式下的重新构造算法。文献[11]提出了减少多个属性的一次性渐减算法，与减少单个属性的渐减式算法相比，该算法只需执行一次。文献[12]对概念格进行了深入研究，发现概念格与数据立方体格结构有很大关联，提出聚集概念和聚集概念格结构（ACL）以及约简聚集概念结构（RAC）。随着概念格理论与方法的进一步完善，信息系统、空间聚类、Folksonomy等领域与形式概念分析及概念格交叉融合，产生了新的应用[13-14] 。

当前研究没有对数据立方体格与概念格的关系进行系统性分析和研究。本文从数据立方体格和概念格的生成机制、结构特性（如度的分布、平均最短路径、聚集系数等特性）上通过理论分析和实验论证探索它们之间的关系。研究数据立方体格与概念格之间的关系，能够进一步揭示它们之间的本质，有利于相关分析和挖掘算法相互应用。

1 相关概念

图1是由表1对销售额求和sum运算聚合生成的数据立方体。“*”表示维属性值All。基本元组集{（D，*，01，10）}与基本表元组{（D，17，01，4）}，{（D，15，01，6）}分别具有上卷、下钻的语义关系，它们之间的偏序关系构成一个数据立方体格。

根据概念格相关定义，由表2给出一个形式背景所生成的概念格如图2所示。

图2 形式背景对应的概念格的Hasse

圖2是表2的形式背景对应概念格的Hasse图表示，图中每一个节点表示一个概念，每一个概念用其外延和内涵来标识，概念之间的序关系用结点之间的边表示。其中，概念格中外延最大的概念（对应于内涵最小）为概念格中的最大概念，它位于概念格的最顶部；概念格中内涵最大的概念（对应于外延最小）为概念格中的最小概念，位于格的最底部。

2 数据立方体格与概念格的结构关系

格结构数据的实质就是图，格节点代表图中的节点，偏序关系构成结点之间的边。故本文从图的视角出发，视格结构数据为图数据，依此研究数据立方体格和概念格的结构关系。

2.1 度分布

一个节点的度（Degree）是指与该节点相连接的边的数量，也就是该节点拥有的连线数目。度分布（Degree distribution）指整个网络中不同度值的节点数量分布或节点度的概率分布，表示网络中度数为该值的顶点个数占总个数的比例。

根据图1和图2得出，在数据立方体格与概念格中，中间层节点的数量远远大于两边层节点的数量，即“两头小，中间大”；根据数据立方体格和概念格中节点之间的偏序关系可知，处于同一层的任意两个结点之间不存在边，但都存在上、下界。结合公式（1）和公式（2）可得，在数据立方体格与概念格中，处于中间层所有结点的度分布之和较两边层大。

2.2 聚集系数

聚集系数（clustering coefficient，本文简称CCF）代表了一个网络的聚集程度大小。设一个网络中一共有L个节点。节点i与另外X个节点相连接，则这X个节点相互之间最多存在M条边，而这X个结点相互之间存在的真实边数为Y条，则该节点的聚集系数为实际边数与最大边数的比值Ci=Y/M。对整个网络来说，平均聚集系数为所有节点聚集系数的平均值。

假设节点i与处于同一层的节点j和节点k两个节点相连接，但节点j和节点k之间不存在边，故r值很小。根据公式（3）可得出节点i具有较小的聚集系数，结合公式（4）可知数据立方体格和概念格均具有较小的聚集系数。

在数据立方体格中，处于同一层的结点具有相同的“*”数量，故同一层的节点之间不存在泛化（特化）关系。如图1所示，同一层的任意两节点之间不存在边，但都存在上、下界，而跨层连接的节点较少，因此与同一个节点相连接的多个节点之间存在较少的边。

对于概念格，如图2所示，节点（12345，）与节点（125，ad）、（2，abd）、（1345，c）连接，但节点（125，ad）、（2，abd）及（1345，c）之间互相没有边，存在跨层连接的节点也很少。同样，在概念格中与同一个节点相连接的多个节点之间也存在较少的边。因此，数据立方体和概念格在图结构上的聚集系数非常小。

2.3 平均最短路径

3 实验分析

实验使用经典数据库Foodmart生成商立方体格，使用UCI机器学习库中的Mushroom（http：//archive.ics.uci.edu/ml/datasets/mushroom）数据生成概念格。经实验分别计算出商立方体格和概念格的度分布、聚集系数、平均最短路径等结构特性，并将两者的结构特性进行对比，从而分析格结构数据之间是否具有相似的结构特性。

3.1 实验环境

实验环境：CPU为Intel（R） Core（TM） i5-2537M CPU@ 1.40GHz 1.40 GHz，内存为4 GB，硬盘为450GB；使用的操作系统为Windows7，开发语言为C++，开发环境为Microsoft visual studio 2010。

3.2 数据立方体格与概念格特性对比

从Foodmart中随机抽取出1万条元组，利用格结构构造算法[3]生成商立方体格。从UCI的Mushroom数据集中随机选取300条数据，利用In-Close算法[9]生成概念格，利用FcaStone（http：//fcastone.sourceforge.net.）进一步将概念格转化为图结构，形成一组数据如表3所示。

对表3中的两种图结构数据通过实验分别计算其度分布、聚集系数、最短路径等结构特性，实验结果如图3所示。本文将数据立方体格和概念格分别以CubeLattice，ConceptLattice简称。

图3（a）是CubeLattice和ConceptLattice两种不同格结构数据的图结构度分布情况，其中横轴表示节点的度值，纵轴表示度为该值时节点的总数。CubeLattice的度分布和ConceptLattice的度分布都符合指数度分布，即先急剧上升，达到一个峰值后再按照指数衰减。已知CubeLattice和ConceptLattice具有明显的层次结构，节点的数量分布是“两头小，中间大”，且同一层任意两结点之间不存在边，但都存在上、下界，故其度的分布在某个小范围内达到最大，而在其它范围内则很小。因此，在Cube Lattice的度分布中，当节点的度为5时，节点数达到峰值5 450；在Concept Lattice的度分布中，当节点的度为7时，节点数达到峰值2 440。经对比可发现，CubeLattice的度分布情况与ConceptLattice的度分布情况具有相似性。

图3（b）是CubeLattice和ConceptLattice两种不同格结构数据的图结构聚集系数分布情况，其中横轴表示节点的度值，纵轴表示度为该值的所有节点的平均聚集系数。从图3（b）可知两者都是先急剧上升，到一个峰值后再缓慢下降，下降过程中幅度虽上下有反复，但整体呈现出下降趋势。经计算，CubeLattice的平均聚集系数为0.023 1，ConceptLattice的平均聚集系数为0.106 4，依据文献[5]得小世界网络的平均聚集系数为0.522 5…，格结构数据的平均聚集系数都偏小，由此可得CubeLattice的聚集系数分布趋势与ConceptLattice的聚集系数分布趋势是相似的。

图3（c）是CubeLattice和ConceptLattice两种不同格结构数据的图结构的最短路径分布情况，其中横轴表示路径长度（跳数），纵轴表示路径长度为该长度的结点对数量。经对比发现，CubeLattice的最短路径分布与ConceptLattice的最短路径分布均是先緩慢上升，达到一个峰值后缓慢下降。经计算得出CubeLattice的平均最短路径为5.25，ConceptLattice的平均最短路径为6.14。显然，CubeLattice的最短路径分布情况与ConceptLattice的最短路径分布情况相似。

4 结语

本文通过建立数据立方体格和概念格概念，从结构特性上论证了数据立方体格与概念格的关系，利用现实世界的数据集分别生成数据立方体格和概念格，经实验验证了数据立方体格和概念格的图结构特性的相似性。下一步将根据格结构数据的度分布等特性，对数据立方体格或概念格应用相关分析或挖掘算法进行比较。

参考文献：

[1] HAN JIAWEI，KAMBER M，PEI JIAN.数据挖掘：概念与技术 [J].第3版， 范明，孟小峰，译.北京：机械工业出版社，2012.

[2] 张文修，姚一豫，梁怡.粗糙集与概念格[M].西安：西安交通大学出版杜，2006.

[3] LAKSHMANAN L V S，PEI J，HAN J.Quotient cube：how to summarize the semantics of a data cube[C].Proceedings of the 28th international conference on Very Large Data Bases，2002：778-789.

[4] 李盛恩，王珊.封闭数据立方体技术研究[J].软件学报，2004，15（8）：1165-1171.

[5] 王洋，游进国，张 婷，等.数据立方体格的图结构特性研究[J].计算机工程，2017，43（2）：1523-1529.

[6] WILLE R.Restructuring lattice theory：an approach based on hierarchies of concepts[M].Berlin：Springer Heidelberg，2009.

[7] GODIN R，MISSAOUI T，ALAUI H.An incremental concept formation algorithm based on Galois（concept） lattices[J].Computational Intelligence，1995，11（2）：246-267.

[8] 吴杰，梁妍，马垣.基于内涵亏值的概念格渐进式构建[J].计算机应用，2017，37（1）：222-227.

[9] ANDREWS S.In-Close，a fast algorithm for computing formal concepts[C].Berlin：Seventeenth International Conference on Conceptual Structures.2009.

[10] 张磊，张宏莉，殷丽华，等.概念格的属性渐减原理与算法研究[J].计算机研究与发展，2013，50（2）：248-259.

[11] 马垣，马文胜.概念格多属性渐减式构造[J].软件学报，2015（12）：3162-3173.

[12] 师智斌.高性能数据立方体及其语义研究[D].北京：北京交通大学，2010.

[13] 康向平，苗夺谦.一种基于概念格的集值信息系统中的知识获取方法[J].智能系统学报，2016，11（3）：287-293.

[14] 申乐，王黎明.概念格稳定性分析及其在Folksonomy中的应用[J].计算机工程与设计，2012，33（3）：1213-1217.

（责任编辑：杜能钢）