基于外存的概念格維護算法

王春月，王黎明，張 卓

(鄭州大學 信息工程學院，河南 鄭州 450001)

0 引 言

在實際應用中，生成概念格[1-3]的形式背景隨著時間的推移會發生變化，此時原始概念格的結構也會改變。目前已經有許多概念格的維護算法[4-7]，這些傳統的算法適用于計算環境的內存大小不受限制的情況下使用。隨著形式背景的規模不斷增長，概念格的傳統維護算法對于內存需求呈指數增加。內存的增長速率無法趕上數據量的增長，這勢必會導致內存不足的情況出現。針對內存不足問題，超內存概念格的維護可以采用外存算法解決。外存算法是指由于數據規模太大導致無法一次性裝入內存，此時需借助外存的反復讀寫數據的算法。例如，文獻[8,9]在LOD技術基礎之上提出一種數據分塊與內外存調度策略相結合的數據處理算法，它們將大規模數據采用四叉樹、二叉樹或分片標記的分割方式將數據分塊，然后采用LRU內外存調度算法釋放內存中近期不使用的塊，并從外存中調入所需塊，從而減少了內存的開銷，提高了大規模數據繪制的實時性。文獻[10]提出一種基于外存后綴樹的top-k字符串局部比對算法，該算法依次從磁盤中讀取原字符串的后綴樹的各子樹，深度優先遍歷子樹并根據子樹的維護信息從內存和磁盤中分別找到參與局部對比的子串、計算比對結果。該方法從根本上消除了內存空間對于算法的束縛。

因此本文以形式背景中對象與屬性之間的二元關系消減情況為應用背景，提出了一種基于外存的超內存概念格維護算法，該算法以概念簇為基本單位劃分大規模概念格，并將劃分后得到的小規模概念塊依次讀入內存中進行迭代處理，最終得到完備概念格的方法。該方法能夠通過設置概念塊的大小，達到充分利用內存，減少外存的訪問次數的目的。本文算法能夠在有限的內存資源下，借助外存的大容量空間，實現超內存概念格的有效維護，并且能夠輔助超內存概念格完成具體的應用。

1 相關定義

本節針對概念格內外存調度維護算法的相關定義進行詳細介紹，對于二元關系消減理論參見文獻[11]，本節對文獻[11]中節點類型進行形式化的表述。即受影響的節點、保留節點、減對象節點、減屬性節點、分割節點以及刪除節點,分別用ES(K)、RS(K)、OS(K)、AS(K)、PS(K)與DS(K)表示。

定義2 概念簇：如果C∈ES(K)，那么C節點與其父節點Parent(C)和子節點Child(C)統稱為概念簇，記作Cluster(C),C稱為聚集中心。

定義3 概念塊：在L(K)中，如果存在n個受影響的節點，首先將這n個節點按外延基數升序排列，然后將此序列分割成m個子序列，前m-1個序列中節點個數均為α，其中m<=n，最后得到每個子序列中各個節點的概念簇，最終得到m個概念塊，記作Block。

定義4 父基節點：如果對于?C∈RS(K),存在某個節點C′∈AS(K)∪DS(K),滿足C′C且Int(C)=Int(C′)-{m},則稱C節點為C′的父基節點，記作fBase(C′)。

定義5 子基節點：如果對于?C∈RS(K),存在某個節點C′∈OS(K)∪DS(K),滿足CC′且Ext(C)=Ext(C′)-{g}, 則稱C節點為C′的子基節點,記作cBase(C′)。

定義6 輔助節點：對于?C∈Blocki，i=1,2,…,n且C為聚集中心，其中n表示概念格劃分的概念塊數。如果C存在父基節點或子基節點，那么Child(fBase(C))與Parent(cBase(C))統稱為Blocki的輔助節點。

2 概念格內外存調度維護算法

本文以消減形式背景中單個對象與屬性之間的二元關系的情況下維護原始概念格為應用背景，研究當傳統算法在有限的內存資源下維護概念格失效時，解決如何借助外存空間實現規模數據的有效維護問題。

2.1 理論基礎

本節根據父子節點的類型對二元關系消減理論中邊的更新過程進行優化，從而提高規模數據的維護效率。二元關系消減理論中節點的映射規律仍保持不變。根據父子節點的類型邊可能會有25種情況，下面通過討論哪些邊的情況不存在，從而減少不必要的遍歷，降低算法的時間復雜度。

定理1 如果C′∈OS(K),如果C=(A,B),使得C′C成立，則C必然滿足下列兩種情況之一：①C∈RS(K),且C為父基節點；②C∈OS(K)。

證明：設C1=(A1,B1)為C′的父基節點，則B1=B′-{m}。

(1)由于C′C且C∈RS(K)，則B?B′且m?B，因此B?B′-{m}=B1?B′, 若C≠C1,有C′C1≤C, 故C′C不成立。

(2)由于CS(K)=RS(K)∪OS(K)∪AS(K)∪PS(K)∪DS(K)和(1),只需證明C?AS(K)∪PS(K)∪DS(K)即可。用反證法，假設C∈AS(K)∪PS(K)∪DS(K), 因C′C,故Ext(C′)?Ext(C)。 得到Ext(C′)-{g}?Ext(C)-{g}=Ext(cBase(C))， 因此cBase(C)節點與C′節點存在交集Ext(C′)-{g}， 此時與AS(K)、PS(K)、DS(K)的定義相矛盾，所以假設不成立。

由定理1可知，減對象節點的父節點只有兩種情況：唯一的保留節點(父基節點)或減對象節點。

定理2 如果C′∈AS(K)，如果C=(A,B), 使得CC′成立，則C必然滿足下列兩種情況之一：

(1)C∈RS(K),且C為子基節點；

(2)C∈AS(K)。

證明：由于概念格內涵與外延的對偶性，由定理1同理可證該定理的正確性。

定理2說明，減屬性節點的子節點只有兩種情況：唯一的保留節點(子基節點)或減屬性節點。

根據定理1～定理3以及文獻[11]的命題2、命題3可知，如表1所示有7種邊的情況不存在。

表1 父子間邊關系不存在的情況

定理3 在L(K)中,?C1,C2∈ES(K) 且C1C2,若在L(K*)中C1=(A,B-{m})，C2=(A-{g},B), 則在L(K*)，C1C2不成立。

證明：反證法，因為C1∈ES(K)， 所以g∈A。假設在L(K*)中，C1C2成立，則存在Ext(C1)?Ext(C2)， 與條件矛盾，所以假設不成立。

由定理3說明，原始概念格中若父節點在L(K*)中更新為內涵不變，外延減g對象的節點，而子節點更新為外延不變，內涵減去m屬性的節點，則原始概念格中的父子關系在新概念格中不成立。滿足以上情況的邊見表2。

表2 滿足定理3情況的邊

因此以上情況的邊在概念格的維護過程中需要刪除，為了保證格的偏序關系還要判斷父節點與子節點的子節點以及子節點與父節點的父節點是否存在直接的前驅后繼關系，若存在則新增邊。由文獻[11]命題2可知，此時需要遍歷所有的子節點和所有的父節點，而根據定理1、定理2可知可以根據父子節點的類型，減少不必要的比較，具體比較方式如圖1所示。

圖1 在L(K*)中，減對象-減屬性邊關系的變化規律

由定理1、定理2可知，C2的子節點與C1的父節點類型如圖1所示。再由定理3可知，在L(K*)中，C2與C1的OS(K)父節點以及C1與C2的AS(K)子節點不存在直接前驅后繼關系，因此它們之間不用新增邊，故C1減對象節點與C2減屬性節點間邊關系刪除時僅考慮兩條邊關系是否增加，即fBase(C1)與C2以及cBase(C2)與C1。若Ext(fBase(C1))與Parent(C2)-C1集合中任意節點的外延都不存在包含關系，fBase(C1)與C2新增邊。同樣若Ext(cBase(C2))與Child(C1)-C2集合中任意節點的外延都不存在包含關系，則cBase(C2)與C1新增邊。這樣只需記錄節點的父基節點與子基節點即可，從而減少遍歷C1的父節點與C2的子節點，提高邊更新效率。表2中其它邊的變化規律同樣依據父子節點的類型，如圖2所示。

圖2 在L(K*)中，表2其余邊關系的變化規律

由文獻[11]定義4可知，分割節點C在新概念格中被分割成兩個節點，此處重新定義兩個節點的形式化表示，即分割成C與divided(C)兩個父子節點。除了表2的邊關系需要刪除外，刪除節點與其父子節點的邊同樣需要刪除，變化規律遵循文獻[11]的規律。總之，根據以上邊和節點的變化規律更新原始概念格就可以得到新的完備格。

2.2 內外存調度策略

外存算法通過利用大容量的外存空間，將暫時不需要的數據存到磁盤中，當需要的時候再調入內存，對數據進行分塊處理，從而實現在一個小的內存空間上運行一個比它大的規模數據。此時算法的性能主要取決于I/O讀寫數據塊的次數，故本文算法在設計上要盡量減少磁盤I/O的操作。本節將二元消減理論與概念格特性相結合，設計合理分塊方式和內外存調度策略以此實現超內存的概念格的維護。

2.2.1 分塊技術

在形式概念分析的實際應用中，為達到塊內高內聚，塊間低耦合的目的，需要受影響的節點與其父子節點盡量在同一塊中，即基于定義2的概念簇為單位劃分概念塊使得分塊的質量變高。按照定義3方式劃分概念格，使得部分無用的保留節點不必讀入內存中，從而減少I/O讀寫次數與內存資源的消耗。同時按受影響的節點的外延升序排列，保證了子節點一定先于父節點處理，在算法設計中為找到表2中的多種情況，當前節點只需要遍歷子節點即可，若父節點與當前節點之間存在表2情況，等到處理該父節點時在處理該邊的情況，這樣可以簡化算法處理流程。

概念塊的大小影響算法的性能，隨著概念塊內節點數的增加，塊處理的時間/空間需求增大，為了保證塊的處理效率，塊中節點數不宜過多，反之太少，又會增加內外存讀寫次數。因此概念塊大小的設置取決于主存空間的大小。

2.2.2 調度算法

在形式概念分析應用中，通常利用概念節點與節點之間的層次關系解決實際問題，此時對于概念節點的遍歷過程通常采用自底向上或自頂向下的廣度優先或深度優先的方式遍歷概念格的節點。為契合概念格的應用過程本文的算法采取自底向上的方式依次處理各個概念塊，同時為避免相鄰兩塊中重復節點的多次讀取，概念節點增設使用頻率域count，設置count的原則是如果當前節點類型為C∈AS(K)∪PS(K)， 若其k個父節點不是Blocki中要處理的受影響節點，則置C的count域為k，如果C∈AS(K) 還需要將Parent(C)、cBase(C)的使用頻率count加上k值，如果C∈PS(K)將divided(C)節點count域加上k值。

基于上述概念塊的處理順序以及塊間節點的關系，本文采取最近最少使用(LRU)調度策略：即當Blocki概念塊處理過后若塊中的節點不會在Blocki+1塊中使用(即count域值為0)，則將這些從內存中釋放，其余節點保留在內存中用于Blocki+1塊中節點的處理，這樣可以減少兩個概念塊中重復節點的讀取次數，降低I/O量。

2.3 算法描述

BlockLattice算法按照LRU調度策略逐個處理概念塊。每個概念塊的維護包括3個主要過程：①讀入內存，即將概念塊中不在內存中的概念節點讀入內存中等待進一步處理。②處理概念塊，判斷概念塊中每個受影響節點的具體類型，然后根據父子節點的類型更新邊，在維護過程中將不在內存中的輔助節點信息讀入內存中。③寫入外存，即將概念塊中不需要駐留到內存中的概念節點寫回外存。對以上3個過程進行循環處理，直至處理完最后一個概念塊為止，該算法結束。本文算法的偽代碼描述如下：本文算法的偽代碼描述如下：

算法：BlockLattice

輸入：形式背景K以及對應的概念格L(K)，被減二元關系gIm

輸出：新形式背景K*下的概念格L(K*)

Begin

list=getAffectedNodes(g,m，β);

inMemoryBlock=readBlock(list，α);

whilelist≠? do

judgeType(list,inMemoryBlock,α);

updateEdges(list,inMemoryBlock,α);

writeBlock(inMemoryBlock);

iflist≠? then

inMemoryBlock=readBlock(list,α);

End

BlockLattice算法的while循環實現了概念塊的LRU調度順序。函數getAffectedNodes()目的是遍歷磁盤上的所有概念節點找出受影響節點，并將受影響的節點按外延所含對象數升序排列，即得到list受影響節點的索引表，按照此索引表劃分概念塊。函數偽代碼描述如下：

函數：getAffectedNodes

輸入：關系對象g以及關系屬性m，每次讀取概念節點數β

輸出：list受影響節點的索引表

Begin

start:=0;

while start <= totalNums do

連接數據庫，查詢從start開始的β條記錄；

for eachC∈ReultSet do

ifg∈Ext(C) andm∈Int(C)then

將C添加入list列表中；

概念節點按外延升序排列。

sart:=start+β;

End

totalNums變量保存概念節點總數。概念格存儲在數據庫中，數據庫中的每條記錄與概念節點一一對應，通過利用關系數據庫的性能實現高效查詢。getAffectedNodes()函數為了優化數據庫查詢效率，盡量合并多條記錄進行統一查詢，同時為防止結果集中數據過大，超出內存限制，將數據進行分頁查詢，β閾值即為分頁大小。

本文算法中readBlock()函數是將list索引表中前α個受影響節點的概念簇讀入inMemoryBlock內存等待處理。函數judgeType()判斷當前塊中受影響節點的具體類型，對節點進行相應的Ext(C)-{g} 或者Int(C)-{m} 處理，同時設置count域值。writeBlock(inMemory)函數是將count域為0的概念節點逐個寫入外存文件，函數updateEdges()是對概念塊中邊進行更新處理并修改count域值。函數描述如下：

函數：updateEdges

輸入：受影響節點列表list，駐留內存節點inMemory，概念塊閾值α

輸出：受影響節點列表list，駐留內存節點inMemory

Begin

count:=0;

whilelist≠? andcount<αdo

C=remove(0);

ifC.type:="ds" then //刪除節點

讀入Child(fBase(C))與Parent(cBase(C))；

isAddEdge(cBase(C),Parent(C));

isAddEdge(fBase(C),Child(C));

刪除Child(C)與C以及Parent(C)與C的邊；

從概念塊中移除并銷毀節點C；;

else ifC.type:="os" then //減對象節點

for eachCc∈Child(C) do

ifCc.type:="as"then

刪除C與Cc之間的邊；

isAddEdge(Cc,fBase(C));

isAddEdge(C,cBase(Cc));

upadateAsCount(Cc);

else ifCc.type:="ps"then

刪除C與Cc之間的邊；

isAddEdge(C,Cc.divided);

isAddEdge(Cc,fBase(C));

else ifC.type:="ps" then //分割節點

updatePS(C);

else //減屬性節點，設置count域

ifC.count>0 then

for eachCp∈Parent(C)do

Cp.count=Cp.count+C.count;

cBase(C).count=cBase(C).count+C.count;

for eachCc∈Child(C) do

ifCc.type:="as"then

upadateAsCount(Cc);

End

updateEdges函數循環處理當前概念塊中的受影響的節點，除減屬性節點之外的其余受影響節點需遍歷其所有子節點，若當前處理的節點與其子節點的邊關系滿足表2的情況。則該邊需要刪除。isAddEdge()用于判斷兩個節點間是否需要新增邊，依據2.1節的定理這里不再贅述。upadateAsCount(Cc)表示如果節點Cc不是當前塊中處理的減屬性節點，則將Cc、Parent(Cc)以及cBase(C)的count域減1，表示這些節點已經被使用過一次。以下是對updatePS()的詳細描述。

函數：updatePS

輸入：受影響節點列表list，駐留內存節點inMemory，分割節點C

輸出：受影響節點列表list，駐留內存節點inMemory

Begin

將C節點分割得到以下兩個節點：

dividedC=(A-{g},B)與C=(A,B-{m})；

dividedC與C有相同子節點；

清空C的下界；

增加dividedCC父子關系；

C.dividedC=dividedC;

ifC.count>0 then //保留dividedC節點

dividedC.count=dividedC.count+C.count

for eachCc∈Child(dividedC) do

ifCc.type:="as"then

刪除dividedC與Cc之間的邊；

isAddEdge(C,cBase(Cc));

upadateAsCount(Cc);

ifCc.type:="ps"then

刪除dividedC與Cc之間的邊；

C與Cc新增邊;

dividedC與Cc.dividedC新增邊;

ifCc.count>0 and

Cc不是當前塊處理的節點then

Cc.dividedC.count--;

End

函數updatePS是對分割節點進行處理，for循環是遍歷分割節點的子節點，如果節點的類型為減屬性或分割節點，則需要刪除邊關系，并判斷是否新增邊。

2.4 時間復雜度分析

2.5 實例分析

借助本文算法可以輔助概念格完成具體的應用。當概念格較大而無法一次裝入內存的情況時，利用本文算法的分塊技術與調度策略，實現超內存概念格邊維護邊應用的過程。以下針對文獻[12]的具體應用來說明BlockLattice算法的執行過程與實用價值。如表3所示給出一類場景下的BOV形式背景[12]，同時生成如圖3所示的BOV概念格[12]。

文獻[12]提出一種基于概念格層次分析的視覺詞典生成方法，通過動態地調整外延數閾值β，獲取各場景語義的約簡視覺詞典。當BOV形式背景生成的概念格規模較大

表3 BOV模型形式背景

圖3 表3對應的BOV概念格

超出內存限制時，且形式背景中I1IV1二元關系消減的情況下，此時可以利用本文算法實現超內存BOV概念格的維護與應用。本文算法執行過程如下，外延數的閾值β[12]設置為2：

(1)遍歷磁盤上所有概念節點，找到受影響節點列表：list={C0,C2,C4，C8,C7}， 同時計算外延數大于等于β的保留節點的內涵并集獲得約簡視覺單詞為V1V2V3V5。

(2)邏輯上將概念格分塊，設置概念塊閾值α=2，則將概念格分成3個概念塊，如圖4所示。

圖4 概念格劃分的3個概念塊

(3)逐個處理概念塊，同時計算每個塊中受影響節點的約簡視覺單詞。根據就緒隊列list列表，首先處理Block1塊，將Block1讀入內存并判斷節點類型，同時計算約簡視覺單詞。根據文獻[11]定義3可知，C0、C2是減屬性節點，將C0,C2節點的內涵減去m屬性，然后根據定理3可知以AS(K)為父節點的邊不需要更新。處理完Block1得到約簡視覺單詞為V1V2V3V5。最后將Block1塊寫入磁盤，根據節點的外延與內涵可知，C4、C8均為受影響的節點，但不在該塊中處理，故C2.count置為2，同樣C3、C4、C8的count域也置為2。因此count域不為0的節點將駐留到內存中，其余節點寫入外存。接下來依次處理Block2、Block3。最終每個塊處理之后節點和邊關系如圖5所示。

圖5 3個概念塊處理后的狀態

以上概念塊中沒有涉及到的邊或節點，表示該邊或節點從原始概念格至新概念格中保持不變，由2.1節的理論基礎為依據。最終得到該場景下的視覺詞典向量[12]為111010。同樣利用以上的方法計算其它類場景下的視覺單詞向量，并進行異或運算以消除多義詞，從而實現圖像場景的分類。詳細過程參考文獻[12]這里不再贅述。

通過以上實例分析可以看出本文的算法的分塊技術和內外存調度算法可以很好的幫助概念格完成具體的應用，體現了本文算法的實用性。

3 實驗結果與分析

本節使用Java語言編程實現本文所涉及的算法，程序運行在AMD Athlon(tm) 4core 3.4GHz CPU，4G內存，Win8OS的計算環境上，經測試JVM最大可用內存為1453 M。實驗使用的是UCI公共數據集和隨機產生的數據集。本文基于MySQL關系型數據庫方式存儲原始概念格，概念節點與數據庫中的記錄一一對應，利用關系數據庫的性能來實現高效的查詢與更新。

3.1 算法完備性驗證

為了驗證BlockLattice的生成概念格的完備性，在3個UCI公共數據集分別使用Godin算法[7]、AddIntent算法[8]和本文算法生成概念格，對比3種算法構造的概念格是否相同。對3個公共數據集CMSC[13]、ForestType[14]和BreastCancer[15]進行預處理得到形式背景，然后隨機刪除某個對象與屬性之間的二元關系，Godin算法和AddIntent算法在新形式背景下夠格，本文算法在原始概念格基礎上調整得到新概念格。實驗結果見表4。從表4中可以看出，本文算法與其余兩種算法構造概念格所得概念節點數相同，并且概念節點之間的偏序關系也保持一致，從而驗證了BlockLattice的正確性。

表4 3種算法產生的概念節點數

3.2 針對小規模數據集，算法時間效率對比

圖時，3種算法時間效率對比

圖時，3種算法時間效率對比

由圖6、圖7所示，相對于同樣數量級的概念格，不管在稀疏還是稠密的數據集下，本文算法明顯優于其它兩類傳統算法。這是由于本文算法不僅是在原始概念格的基礎上調整得到新概念格，而且具有較低的時間復雜度，所以隨著形式背景的規模不斷增大，本文算法的執行效率相對于傳統算法要好的多。

3.3 針對規模數據，BlockLattice算法效率分析

本節首先測試概念塊α閾值對算法性能的影響，本組實驗分別統計了I/O讀寫外存次數、內存計算時間Ti、外存操作時間To和總時間T，外存操作時間是指讀寫外存花費時間。本實驗使用約2.83 GB的原始概念格，概念節點總數為1 422 225個，其中隨機刪除某個位置的二元關系使得受影響的節點數為988個。實驗中概念塊α閾值分別設置為1，10，100，1000。分頁閾值β設置為105個，實驗結果見表5、表6。

表5 當變化α閾值時的算法運行時間比較/s

表6 當變化α閾值時的I/O讀寫外存次數比較

由表5、表6所示，隨著概念塊α閾值的增加，To減少。具體地，因為α閾值的增加導致I/O讀寫次數減少。隨著概念塊α閾值的增加內存計算的時間曲線存在一個拐點(先降低后增加)，這是因為α閾值的增加使得存在父子關系的受影響節點盡量在同一塊，減少了count域的維護，使得內存計算減少，但是對于內存中概念節點的查找時間隨著內存中節點數的增加而增加，所以Ti隨著α的進一步增加而增大。

然后測試分頁β閾值對于算法性能的影響。本組實驗分別統計了I/O讀寫外存次數、To、Ti以及T時間，α閾值設置為1000。實驗結果見表7、表8。

由表7、表8所示，隨著分頁β閾值的增加，To減少，這是因為I/O讀取次數減少。β閾值設置只作用于尋找磁盤上的受影響節點索引表的過程，它是為防止數據庫的結果

表7 當變化β閾值時的算法運行時間比較/s

表8 當變化β閾值時的I/O讀寫外存次數比較

集過大出現內存溢出的情況而設置的并不影響內存的分塊。在α相同且β不同的情況下，對于概念格中概念節點處理流程相同，因此內存計算的時間大致相同。

接著測試概念塊α閾值對于內存中含有的最大概念節點數的影響。本組實驗統計了程序運行過程中包含的最大概念節點數。實驗結果見表9。

表9 當變化α閾值時駐留在內存中最大概念數比較(n=1422225)

由表9所示，隨著概念塊α閾值的增加，駐留在內存中的概念節點數也增加。當α閾值達到最大值1000時(概念格中受影響的節點數988)，駐留在內存中最大概念節點數只占總概念格節點數的2.43%，有效地降低了內存的消耗。

接著測試對于同一個規模數據，受影響節點總數對于算法性能的影響，由于刪除不同位置的二元關系可得到不同的受影響節點總數。實驗中概念塊α閾值為1000，β閾值為105，刪除3個位置的二元關系得到如表10所示的實驗結果。

表10 受影響節點總數對算法性能的影響

由表10所示，針對同一個規模數據，在α與β相同的情況下，To、Ti和T時間以及I/O讀寫外存的次數隨著受影響節點數的增加而增加。

表11 3組隨機數據集描述

實驗中概念塊α閾值設置為5、35、350、3500。限制內存空間為500 M，分頁閾值β為105。實驗分別統計了To、Ti以及T時間，實驗結果如圖8所示。橫坐標表示概念塊α閾值。

圖8 不同數據集下，算法各項指標對比

由圖8所示，在α、β閾值相等時，隨著數據規模的增大，To、T時間增加，相反Ti減小。具體地，因為數據量增大導致I/O讀寫外存次數增加致使To、T時間增加；又因為Ti主要與受影響節點總數以及α閾值有關，當α相同時，Ti隨著受影響節點總數的減少而減少。

通過以上多組實驗得到以下結論：①影響算法性能的主要因素為外存操作時間，即I/O讀寫外存的次數。數據規模、受影響節點總數以及α與β閾值都會影響I/O讀寫外存的次數，表現為I/O讀寫外存的次數隨著α與β閾值的增加而減少，隨著數據規模、受影響節點總數的增加而增加。②算法消耗內存的情況主要取決于數據規模、受影響節點總數、α以及β閾值。α與β閾值的增加使得消耗的內存也增加，但由于受影響節點總數是有限的，當α閾值增加到一定程度時，駐留在內存中的最大概念數存在最大值，內存消耗不會無限制增加，且通過調節α閾值可以明顯降低內存的消耗。因此依據當前平臺參數、概念格的規模以及受影響節點總數，合理調整α與β閾值，使得BlockLattice算法執行效率達到最優。

4 結束語

本文對超內存概念格維護問題進行了研究，和以往的傳統的基于內存的維護算法相比，本文研究的問題還需要考率如何充分利用內存資源，減少I/O讀寫次數。為了解決上述問題，本文以形式背景中對象與屬性之間二元關系消減為應用背景，提出一種有限內存空間下超內存概念格內外存調度維護算法。本文首先將二元關系消減理論進一步改進優化以提高數據處理能力。然后利用基于概念簇的方式劃分概念格使得分塊質量變高(塊內高內聚，塊間低耦合)，為契合概念格在實際應用中遍歷概念格的方式，采用自底向上最近最少使用的調度策略處理概念塊，最后通過實例驗證本文算法在概念格實際應用中的實用價值。本文從理論分析與實驗結果兩方面表明本文算法與傳統算法相比，不僅節約了大量的運行時間，而且也降低了內存的消耗，解決了內存不足的現象，實現了超內存概念格的維護，為概念格的具體應用提供保障。

[1]Yang Kai,Jin Yonglong.Research of coke ratio prediction based on concept lattice and genetic algorithm[C]//Mechatronics and Automation.IEEE,2016:1407-1411.

[2]Roman Ilin.Classification with concept lattice and choquet integral[C]//Information Fusion.IEEE,2016:1554-1561.

[3]Shi Chongyang,Lai Linjing,Fan Jing,et al.Similarity model based on CBR and FCA[C]//Software Engineering,Arti-ficial Intelligence,Networking and Parallel/Distributed Computing.IEEE,2016:597-603.

[4]Goidn R.Incremental concept formation algorithm based on Galois (concept) lattices[J].Computation Intelligence,1995,11(2):246.

[5]Merwe D V D,Obiedkov S,Kourie D.AddIntent:A new incremental algorithm for constructing concept lattice[G].LNCS 2961:Proc of the 2nd Int Conf on Formal Concept Analysis.Berlin:Springer,2004:372.

[6]MA Yuan,MA Wensheng.Construction of multi-attributes decrement for concept lattice[J].Journal of Software,2015,16 (12):3162-3173(in Chinese).[馬垣,馬文勝.概念格多屬性漸減式構造[J].軟件學報,2015,16(12):3162-3173.]

[7]JIANG Qin,ZHANG Zhuo,WANG Liming.Algorithms of constructing concept lattice based on deleting multiple attributes synchronously[J].Journal of Chinese Computer Systems,2016,37(4):646-652(in Chinese).[姜琴,張卓,王黎明.基于多屬性同步消減的概念格構造算法[J].小型微型計算機系統,2016,37(4):646-652.]

[8]Zhang Zhifeng,Zhang Na.A LOD algorithm based on out-of-core for large scale terrain rendering[C]//Mechatronic Sciences,Electric Engineering and Computer.IEEE,2013:2168-2171.

[9]GU Runnan,AI Zhongliang.Massive data processing algorithm based on LOD control and out-of-core techniques[J].Computer Engineering & Software,2016,37(3):89-93(in Chinese).[古潤南,艾中良.基于LOD控制與內外存調度的大規模網絡態勢數據節點處理算法[J].軟件,2016,37(3):89-93.]

[10]Baralis E,Cerquitelli T,Chiusano,et al.Scalable out-of-core itemset mining[J].Information Sciences,2015,293(1):146-162.

[11]WANG Chunyue,WANG Liming,ZHANG Zhuo.Algorithm of maintaining concept lattice based on binary relation decrement[J].Computer Science,2016,43(14A):34-41(in Chinese).[王春月,王黎明,張卓.基于二元關系消減的概念格維護算法[J].計算機科學,2016,43(14A):34-41.]

[12]ZHONG Lihua,ZHANG Sulan,HU Lihua,et al.A concept lattice hierarchy based generating method of visual dictionary[J].Journal of Computer-Aided Design & Computer Graphics,2015,27(1):136-141(in Chinese).[鐘利華,張素蘭,胡立華,等.基于概念格層次分析的視覺詞典生成方法[J].計算機輔助設計與圖形學學報,2015,27(1):136-141.]

[13]Lucas DD,Klein R,Tannahill J,et al.Climate model simulation crashes dataset[EB/OL].[2016-12-18].http://archive.ics.uci.edu/ml/datasets/Climate+Model+Simulation+Crashes#.

[14]Brian Johnson.Forest type mapping data set[EB/OL].[2016-12-18].http://archive.ics.uci.edu/ml/datasets/Fo-rest+type+mapping.

[15]William H.Breast cancer wisconsin (diagnostic) data set[EB/OL].[2016-12-18].http://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29.