數據立方體格與概念格關系研究

張婷 都儀敏

摘要：數據立方體是數據倉庫和聯機分析處理研究領域的一種核心數據模型，而概念格是形式概念分析理論的一類重要數據結構，其在數據分析領域應用廣泛，它們都屬于格結構。目前，對數據立方體格與概念格之間的關系還沒有進行系統研究。為此，論證了數據立方體格與概念格在結構特性上的關系。在數據立方體格與概念格關系基礎上，進一步研究數據立方體格的相關分析及挖掘算法與概念格之間的互用性，分析它們在這兩種數據模型之間相互應用的優越性和局限性。實驗結果表明，數據立方體格與概念格在度分布、聚集系數、平均最短路徑等方面具有相似性。

關鍵詞：數據立方體格；概念格；度分布；聚集系數；平均最短路徑

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.

（責任編輯：杜能鋼）