張婷 都儀敏

摘要：數(shù)據(jù)立方體是數(shù)據(jù)倉庫和聯(lián)機(jī)分析處理研究領(lǐng)域的一種核心數(shù)據(jù)模型，而概念格是形式概念分析理論的一類重要數(shù)據(jù)結(jié)構(gòu)，其在數(shù)據(jù)分析領(lǐng)域應(yīng)用廣泛，它們都屬于格結(jié)構(gòu)。目前，對數(shù)據(jù)立方體格與概念格之間的關(guān)系還沒有進(jìn)行系統(tǒng)研究。為此，論證了數(shù)據(jù)立方體格與概念格在結(jié)構(gòu)特性上的關(guān)系。在數(shù)據(jù)立方體格與概念格關(guān)系基礎(chǔ)上，進(jìn)一步研究數(shù)據(jù)立方體格的相關(guān)分析及挖掘算法與概念格之間的互用性，分析它們在這兩種數(shù)據(jù)模型之間相互應(yīng)用的優(yōu)越性和局限性。實(shí)驗(yàn)結(jié)果表明，數(shù)據(jù)立方體格與概念格在度分布、聚集系數(shù)、平均最短路徑等方面具有相似性。

關(guān)鍵詞：數(shù)據(jù)立方體格；概念格；度分布；聚集系數(shù)；平均最短路徑

DOIDOI：10.11907/rjdk.173305

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：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.

英文關(guān)鍵詞Key Words：data cube lattice； concept lattice； degree distribution； clustering coefficient； average shortest path

0 引言

在數(shù)據(jù)挖掘、數(shù)據(jù)倉庫以及知識表示、知識發(fā)現(xiàn)這兩個緊密交叉、融合的研究領(lǐng)域存在兩類重要的數(shù)據(jù)模型：數(shù)據(jù)立方體格[1]和概念格[2]，其實(shí)都屬于格結(jié)構(gòu)數(shù)據(jù)。數(shù)據(jù)立方體以符合星型模型的基本表為元組集，以維度屬性為坐標(biāo)軸，不同維度屬性（值）的交叉構(gòu)成了多維空間；該空間的每個點(diǎn)根據(jù)上卷、下鉆的計算依賴關(guān)系構(gòu)成了數(shù)據(jù)立方體。文獻(xiàn)[3]提出了商立方體（quotient cube）概念。商立方體是壓縮數(shù)據(jù)立方體的一種技術(shù)，其在保持?jǐn)?shù)據(jù)立方體語義的前提下，對數(shù)據(jù)立方體采用Cover Partition技術(shù)，將其上界相同的數(shù)據(jù)單元劃分為等價類。每個等價類的上界和下界被保存下來，從而實(shí)現(xiàn)數(shù)據(jù)立方體壓縮。封閉數(shù)據(jù)立方體（closed data cube）概念見文獻(xiàn)[4]，同樣通過等價類實(shí)現(xiàn)數(shù)據(jù)立方體壓縮，區(qū)別在于封閉數(shù)據(jù)立方體對于每個等價類只保存其上界，因此對數(shù)據(jù)立方體的壓縮效率更高。文獻(xiàn)[5]從圖結(jié)構(gòu)數(shù)據(jù)角度研究格結(jié)構(gòu)數(shù)據(jù)的統(tǒng)計特性和解析模型，并進(jìn)一步研究了數(shù)據(jù)立方體格結(jié)構(gòu)劃分方法。

德國數(shù)學(xué)家Wille R[6].于1982年基于概念和概念層次首先提出了形式概念分析（FCA）理論，其核心數(shù)據(jù)結(jié)構(gòu)概念格也稱Galois格，用于概念的發(fā)現(xiàn)、排序和顯示。目前，概念格的構(gòu)造方法分為批處理算法[7]和漸進(jìn)式算法[8-9]。張磊等 [10]研究了當(dāng)形式概念的某些屬性削減后，如何快速有效地在原有概念格上進(jìn)行調(diào)整，得到新形式背景的概念格，而不是傳統(tǒng)方式下的重新構(gòu)造算法。文獻(xiàn)[11]提出了減少多個屬性的一次性漸減算法，與減少單個屬性的漸減式算法相比，該算法只需執(zhí)行一次。文獻(xiàn)[12]對概念格進(jìn)行了深入研究，發(fā)現(xiàn)概念格與數(shù)據(jù)立方體格結(jié)構(gòu)有很大關(guān)聯(lián)，提出聚集概念和聚集概念格結(jié)構(gòu)（ACL）以及約簡聚集概念結(jié)構(gòu)（RAC）。隨著概念格理論與方法的進(jìn)一步完善，信息系統(tǒng)、空間聚類、Folksonomy等領(lǐng)域與形式概念分析及概念格交叉融合，產(chǎn)生了新的應(yīng)用[13-14] 。

當(dāng)前研究沒有對數(shù)據(jù)立方體格與概念格的關(guān)系進(jìn)行系統(tǒng)性分析和研究。本文從數(shù)據(jù)立方體格和概念格的生成機(jī)制、結(jié)構(gòu)特性（如度的分布、平均最短路徑、聚集系數(shù)等特性）上通過理論分析和實(shí)驗(yàn)論證探索它們之間的關(guān)系。研究數(shù)據(jù)立方體格與概念格之間的關(guān)系，能夠進(jìn)一步揭示它們之間的本質(zhì)，有利于相關(guān)分析和挖掘算法相互應(yīng)用。

1 相關(guān)概念

圖1是由表1對銷售額求和sum運(yùn)算聚合生成的數(shù)據(jù)立方體?！?”表示維屬性值A(chǔ)ll?；驹M集{（D，*，01，10）}與基本表元組{（D，17，01，4）}，{（D，15，01，6）}分別具有上卷、下鉆的語義關(guān)系，它們之間的偏序關(guān)系構(gòu)成一個數(shù)據(jù)立方體格。

根據(jù)概念格相關(guān)定義，由表2給出一個形式背景所生成的概念格如圖2所示。

圖2 形式背景對應(yīng)的概念格的Hasse

圖2是表2的形式背景對應(yīng)概念格的Hasse圖表示，圖中每一個節(jié)點(diǎn)表示一個概念，每一個概念用其外延和內(nèi)涵來標(biāo)識，概念之間的序關(guān)系用結(jié)點(diǎn)之間的邊表示。其中，概念格中外延最大的概念（對應(yīng)于內(nèi)涵最小）為概念格中的最大概念，它位于概念格的最頂部；概念格中內(nèi)涵最大的概念（對應(yīng)于外延最小）為概念格中的最小概念，位于格的最底部。

2 數(shù)據(jù)立方體格與概念格的結(jié)構(gòu)關(guān)系

格結(jié)構(gòu)數(shù)據(jù)的實(shí)質(zhì)就是圖，格節(jié)點(diǎn)代表圖中的節(jié)點(diǎn)，偏序關(guān)系構(gòu)成結(jié)點(diǎn)之間的邊。故本文從圖的視角出發(fā)，視格結(jié)構(gòu)數(shù)據(jù)為圖數(shù)據(jù)，依此研究數(shù)據(jù)立方體格和概念格的結(jié)構(gòu)關(guān)系。

2.1 度分布

一個節(jié)點(diǎn)的度（Degree）是指與該節(jié)點(diǎn)相連接的邊的數(shù)量，也就是該節(jié)點(diǎn)擁有的連線數(shù)目。度分布（Degree distribution）指整個網(wǎng)絡(luò)中不同度值的節(jié)點(diǎn)數(shù)量分布或節(jié)點(diǎn)度的概率分布，表示網(wǎng)絡(luò)中度數(shù)為該值的頂點(diǎn)個數(shù)占總個數(shù)的比例。

根據(jù)圖1和圖2得出，在數(shù)據(jù)立方體格與概念格中，中間層節(jié)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)大于兩邊層節(jié)點(diǎn)的數(shù)量，即“兩頭小，中間大”；根據(jù)數(shù)據(jù)立方體格和概念格中節(jié)點(diǎn)之間的偏序關(guān)系可知，處于同一層的任意兩個結(jié)點(diǎn)之間不存在邊，但都存在上、下界。結(jié)合公式（1）和公式（2）可得，在數(shù)據(jù)立方體格與概念格中，處于中間層所有結(jié)點(diǎn)的度分布之和較兩邊層大。

2.2 聚集系數(shù)

聚集系數(shù)（clustering coefficient，本文簡稱CCF）代表了一個網(wǎng)絡(luò)的聚集程度大小。設(shè)一個網(wǎng)絡(luò)中一共有L個節(jié)點(diǎn)。節(jié)點(diǎn)i與另外X個節(jié)點(diǎn)相連接，則這X個節(jié)點(diǎn)相互之間最多存在M條邊，而這X個結(jié)點(diǎn)相互之間存在的真實(shí)邊數(shù)為Y條，則該節(jié)點(diǎn)的聚集系數(shù)為實(shí)際邊數(shù)與最大邊數(shù)的比值Ci=Y/M。對整個網(wǎng)絡(luò)來說，平均聚集系數(shù)為所有節(jié)點(diǎn)聚集系數(shù)的平均值。

假設(shè)節(jié)點(diǎn)i與處于同一層的節(jié)點(diǎn)j和節(jié)點(diǎn)k兩個節(jié)點(diǎn)相連接，但節(jié)點(diǎn)j和節(jié)點(diǎn)k之間不存在邊，故r值很小。根據(jù)公式（3）可得出節(jié)點(diǎn)i具有較小的聚集系數(shù)，結(jié)合公式（4）可知數(shù)據(jù)立方體格和概念格均具有較小的聚集系數(shù)。

在數(shù)據(jù)立方體格中，處于同一層的結(jié)點(diǎn)具有相同的“*”數(shù)量，故同一層的節(jié)點(diǎn)之間不存在泛化（特化）關(guān)系。如圖1所示，同一層的任意兩節(jié)點(diǎn)之間不存在邊，但都存在上、下界，而跨層連接的節(jié)點(diǎn)較少，因此與同一個節(jié)點(diǎn)相連接的多個節(jié)點(diǎn)之間存在較少的邊。

對于概念格，如圖2所示，節(jié)點(diǎn)（12345，）與節(jié)點(diǎn)（125，ad）、（2，abd）、（1345，c）連接，但節(jié)點(diǎn)（125，ad）、（2，abd）及（1345，c）之間互相沒有邊，存在跨層連接的節(jié)點(diǎn)也很少。同樣，在概念格中與同一個節(jié)點(diǎn)相連接的多個節(jié)點(diǎn)之間也存在較少的邊。因此，數(shù)據(jù)立方體和概念格在圖結(jié)構(gòu)上的聚集系數(shù)非常小。

2.3 平均最短路徑

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)使用經(jīng)典數(shù)據(jù)庫Foodmart生成商立方體格，使用UCI機(jī)器學(xué)習(xí)庫中的Mushroom（http：//archive.ics.uci.edu/ml/datasets/mushroom）數(shù)據(jù)生成概念格。經(jīng)實(shí)驗(yàn)分別計算出商立方體格和概念格的度分布、聚集系數(shù)、平均最短路徑等結(jié)構(gòu)特性，并將兩者的結(jié)構(gòu)特性進(jìn)行對比，從而分析格結(jié)構(gòu)數(shù)據(jù)之間是否具有相似的結(jié)構(gòu)特性。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境：CPU為Intel（R） Core（TM） i5-2537M CPU@ 1.40GHz 1.40 GHz，內(nèi)存為4 GB，硬盤為450GB；使用的操作系統(tǒng)為Windows7，開發(fā)語言為C++，開發(fā)環(huán)境為Microsoft visual studio 2010。

3.2 數(shù)據(jù)立方體格與概念格特性對比

從Foodmart中隨機(jī)抽取出1萬條元組，利用格結(jié)構(gòu)構(gòu)造算法[3]生成商立方體格。從UCI的Mushroom數(shù)據(jù)集中隨機(jī)選取300條數(shù)據(jù)，利用In-Close算法[9]生成概念格，利用FcaStone（http：//fcastone.sourceforge.net.）進(jìn)一步將概念格轉(zhuǎn)化為圖結(jié)構(gòu)，形成一組數(shù)據(jù)如表3所示。

對表3中的兩種圖結(jié)構(gòu)數(shù)據(jù)通過實(shí)驗(yàn)分別計算其度分布、聚集系數(shù)、最短路徑等結(jié)構(gòu)特性，實(shí)驗(yàn)結(jié)果如圖3所示。本文將數(shù)據(jù)立方體格和概念格分別以CubeLattice，ConceptLattice簡稱。

圖3（a）是CubeLattice和ConceptLattice兩種不同格結(jié)構(gòu)數(shù)據(jù)的圖結(jié)構(gòu)度分布情況，其中橫軸表示節(jié)點(diǎn)的度值，縱軸表示度為該值時節(jié)點(diǎn)的總數(shù)。CubeLattice的度分布和ConceptLattice的度分布都符合指數(shù)度分布，即先急劇上升，達(dá)到一個峰值后再按照指數(shù)衰減。已知CubeLattice和ConceptLattice具有明顯的層次結(jié)構(gòu)，節(jié)點(diǎn)的數(shù)量分布是“兩頭小，中間大”，且同一層任意兩結(jié)點(diǎn)之間不存在邊，但都存在上、下界，故其度的分布在某個小范圍內(nèi)達(dá)到最大，而在其它范圍內(nèi)則很小。因此，在Cube Lattice的度分布中，當(dāng)節(jié)點(diǎn)的度為5時，節(jié)點(diǎn)數(shù)達(dá)到峰值5 450；在Concept Lattice的度分布中，當(dāng)節(jié)點(diǎn)的度為7時，節(jié)點(diǎn)數(shù)達(dá)到峰值2 440。經(jīng)對比可發(fā)現(xiàn)，CubeLattice的度分布情況與ConceptLattice的度分布情況具有相似性。

圖3（b）是CubeLattice和ConceptLattice兩種不同格結(jié)構(gòu)數(shù)據(jù)的圖結(jié)構(gòu)聚集系數(shù)分布情況，其中橫軸表示節(jié)點(diǎn)的度值，縱軸表示度為該值的所有節(jié)點(diǎn)的平均聚集系數(shù)。從圖3（b）可知兩者都是先急劇上升，到一個峰值后再緩慢下降，下降過程中幅度雖上下有反復(fù)，但整體呈現(xiàn)出下降趨勢。經(jīng)計算，CubeLattice的平均聚集系數(shù)為0.023 1，ConceptLattice的平均聚集系數(shù)為0.106 4，依據(jù)文獻(xiàn)[5]得小世界網(wǎng)絡(luò)的平均聚集系數(shù)為0.522 5…，格結(jié)構(gòu)數(shù)據(jù)的平均聚集系數(shù)都偏小，由此可得CubeLattice的聚集系數(shù)分布趨勢與ConceptLattice的聚集系數(shù)分布趨勢是相似的。

圖3（c）是CubeLattice和ConceptLattice兩種不同格結(jié)構(gòu)數(shù)據(jù)的圖結(jié)構(gòu)的最短路徑分布情況，其中橫軸表示路徑長度（跳數(shù)），縱軸表示路徑長度為該長度的結(jié)點(diǎn)對數(shù)量。經(jīng)對比發(fā)現(xiàn)，CubeLattice的最短路徑分布與ConceptLattice的最短路徑分布均是先緩慢上升，達(dá)到一個峰值后緩慢下降。經(jīng)計算得出CubeLattice的平均最短路徑為5.25，ConceptLattice的平均最短路徑為6.14。顯然，CubeLattice的最短路徑分布情況與ConceptLattice的最短路徑分布情況相似。

4 結(jié)語

本文通過建立數(shù)據(jù)立方體格和概念格概念，從結(jié)構(gòu)特性上論證了數(shù)據(jù)立方體格與概念格的關(guān)系，利用現(xiàn)實(shí)世界的數(shù)據(jù)集分別生成數(shù)據(jù)立方體格和概念格，經(jīng)實(shí)驗(yàn)驗(yàn)證了數(shù)據(jù)立方體格和概念格的圖結(jié)構(gòu)特性的相似性。下一步將根據(jù)格結(jié)構(gòu)數(shù)據(jù)的度分布等特性，對數(shù)據(jù)立方體格或概念格應(yīng)用相關(guān)分析或挖掘算法進(jìn)行比較。

參考文獻(xiàn)：

[1] HAN JIAWEI，KAMBER M，PEI JIAN.數(shù)據(jù)挖掘：概念與技術(shù) [J].第3版， 范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2012.

[2] 張文修，姚一豫，梁怡.粗糙集與概念格[M].西安：西安交通大學(xué)出版杜，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] 李盛恩，王珊.封閉數(shù)據(jù)立方體技術(shù)研究[J].軟件學(xué)報，2004，15（8）：1165-1171.

[5] 王洋，游進(jìn)國，張 婷，等.數(shù)據(jù)立方體格的圖結(jié)構(gòu)特性研究[J].計算機(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] 吳杰，梁妍，馬垣.基于內(nèi)涵虧值的概念格漸進(jìn)式構(gòu)建[J].計算機(jī)應(yīng)用，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].計算機(jī)研究與發(fā)展，2013，50（2）：248-259.

[11] 馬垣，馬文勝.概念格多屬性漸減式構(gòu)造[J].軟件學(xué)報，2015（12）：3162-3173.

[12] 師智斌.高性能數(shù)據(jù)立方體及其語義研究[D].北京：北京交通大學(xué)，2010.

[13] 康向平，苗奪謙.一種基于概念格的集值信息系統(tǒng)中的知識獲取方法[J].智能系統(tǒng)學(xué)報，2016，11（3）：287-293.

[14] 申樂，王黎明.概念格穩(wěn)定性分析及其在Folksonomy中的應(yīng)用[J].計算機(jī)工程與設(shè)計，2012，33（3）：1213-1217.

（責(zé)任編輯：杜能鋼）