郭澤蔚，姜 麟，李金海

(1.昆明理工大學 理學院,云南 昆明 650500;2.昆明理工大學 數(shù)據(jù)科學研究中心,云南 昆明 650500)

形式概念分析(Formal concept analysis)是20世紀80年代初期由德國教授R.Wille提出的一種用于發(fā)現(xiàn)知識的理論。形式概念分析通過構(gòu)造概念格來進行數(shù)據(jù)的處理,也稱概念格理論[1]。以往關(guān)于概念格的研究主要集中于經(jīng)典的形式背景,即屬性值為Boolean值,然而,由于現(xiàn)實中數(shù)據(jù)的復(fù)雜性,更多的形式背景中的屬性值是區(qū)間形式的普通實值。經(jīng)典的概念格主要應(yīng)用于發(fā)現(xiàn)二值(或多值)形式背景的概念構(gòu)造,因此,傳統(tǒng)形式背景中概念格的構(gòu)造方法并不適用于實值形式背景[3-4]。而實值形式背景概念格的構(gòu)造存在算法復(fù)雜性大等缺陷,現(xiàn)階段圍繞這一類問題的研究也缺少較好的普適性,故進一步討論實值概念格的構(gòu)造具有一定的意義。

Matlab已成為數(shù)值計算領(lǐng)域的主流工具,其擁有的并行計算工具箱(Parallel computing toolbox,PCT)和并行計算服務(wù)(Distributed computing server,DCS)可以實現(xiàn)基于多處理器平臺和集群平臺的多種并行計算任務(wù),利用PCT和DCS,用戶無需關(guān)心多核、多處理器之間以及集群之間的底層數(shù)據(jù)通信,可以將更多的精力放在并行算法的設(shè)計,充分利用Matlab提供的數(shù)值計算模塊和數(shù)據(jù)顯示功能,高效便捷的完成并行計算任務(wù)[5]。

經(jīng)典形式背景下的建格算法并不適用于處理實值形式背景下的概念格,而串行算法在數(shù)據(jù)規(guī)模較大的情況下計算效率較低。針對實值形式背景的特點,結(jié)合經(jīng)典概念格的漸進式構(gòu)造思想,本文首先給出了計算實值概念格的方法；然后提出了一種實值概念格計算的漸進式構(gòu)造算法,并對其進行改進,得到并行算法,應(yīng)用Matlab對串、并算法進行程序的實現(xiàn)；最后通過數(shù)值實驗對該算法的串行與并行運行效率作了對比,對該算法在特定實值條件下的并行化可行性進行了評估。

1 實值形式背景與實概念格

1.1 實 集

定義1[6]設(shè)R為實數(shù)集。對于μ,v∈R,稱I=[μ,v]為R上的一個實區(qū)間,其中μ和v分別稱為實區(qū)間I的上界和下界。如果μ>v,則稱實區(qū)間I是空的,記為[,]。

顯然,當I=[μ,v]非空時,I就是由μ到v之間的全部實數(shù)構(gòu)成的集合。對于兩個實區(qū)間I1=[μ1,v1]和I2=[μ2,v2],它們的交Inter(I1,I2)滿足:

Inter(I1,I2)=[max(μ1,μ2),min(ν1,ν2)]

定義{I1,I2}的閉包為

Closure({I1,I2})=

n個實區(qū)間的閉包算子可表示如下:

Closure({I1,I2,…,In})=

Closure({Closure({I1,I2}),…,In})

并記U上所有實值構(gòu)成的集合為R(U)。

集合中的交運算和并運算也同樣適用于實集,實集中有兩種交(并)運算,分別為L-交(并)和S-交(并)。下面給出定義[7]。

1.2 實值形式背景與實概念格

例1表1給出了一個實值形式背景。

表1 實值形式背景

(?X∈P(U))

(?X∈P(U))

根據(jù)前面的討論,對于實值形式背景,可構(gòu)造兩類實概念格:L-實概念格和S-實概念格。然而,這兩種概念格框架的構(gòu)建及相關(guān)討論是類似的,故在此只給出基于L-實概念格構(gòu)建的背景屬性框架。需要指出的是,只要將該約簡框架的中所有與L-實概念格相關(guān)的符號都替換為S-實概念格中相應(yīng)的符號,就可以得到基于S-實概念格構(gòu)建的實值形式屬性背景框架。

1.3 概念格的構(gòu)造算法

概念格的構(gòu)造過程實際上就是概念聚類的過程,概念格一個重要的屬性就是其完備性使得對于同樣的一個數(shù)據(jù)集,每次生成的格都是唯一的,即對象、屬性的排列順序和格構(gòu)造算法均不會影響其構(gòu)造的結(jié)果。因此,現(xiàn)有的關(guān)于概念格的構(gòu)造算法都是為了提高建格的效率,減少建格的復(fù)雜度而設(shè)計的[9]。經(jīng)典形式背景概念格的串行構(gòu)造算法大致可分為兩類:批處理算法、漸進式算法。

批處理算法主要思想:首先要生成所有的格節(jié)點,即原形式背景中所有的概念的集合,然后根據(jù)它們之間的前驅(qū)-后繼關(guān)系生成邊,完成格的構(gòu)造。比較經(jīng)典的有Bordat算法[10-11]。批處理算法自頂向下通過遞歸的方式構(gòu)造其子節(jié)點,并展開運算,這種算法有利于消掉不滿足規(guī)則的節(jié)點,提高算法效率。

2 實值形式背景概念格構(gòu)造算法

2.1 設(shè)計實值概念格的漸進式構(gòu)造算法

以往圍繞概念格構(gòu)造算法的研究主要集中于經(jīng)典形式背景,而實值形式背景概念格的算法構(gòu)造目前并沒有充分的研究成果。原因是實值形式背景的轉(zhuǎn)化較為困難,而且算法的復(fù)雜性非常大,對數(shù)據(jù)的適應(yīng)性很差[8]。受Godin漸進式算法的啟發(fā),下面給出一種實值形式背景概念格提取的算法Real。

Algorithm Real

輸入:原始實值形式背景L

輸出:實概念矩陣L*

BEGIN

size(L)=[m,n];

L0=(?,[]);/*初始化概念*/

Xi=sealing(Xi);/*將對象序號0-1化*/

L_new=(X1,B1);/*存儲每次循環(huán)結(jié)束時所有概念*/

FORi=2:m

size(L_new)=[m_1,n_1];/*更新L_new中概念的個數(shù)*/

將(Xi,Bi)加入到L_new;

FORj=1:m_1

Z=Xi|Xj;

FORr=1:(n_1)/4

BZr=Bjr∪Bir;/*Xi和Xj在屬性r下對應(yīng)的區(qū)間比較*/

BZ=[BZBZr];

ENDFOR

L′=(Z,BZ);

IFL′

單獨形成一個概念

將概念L′添加進L_new;

ENDIF

ENDFOR

L_new=xiao(L_new);/*消除冗余概念*/

ENDFOR

L*=L0∪L_new;

END

該算法繼承了傳統(tǒng)概念格漸進式構(gòu)造算法的核心思路,即通過創(chuàng)建一個存儲概念的新格L_new,通過循環(huán)檢驗每次添加新節(jié)點后L_new中概念是否發(fā)生變化,繼而更新概念集合進入下次循環(huán),這樣做的好處在于算法可以在不停地添加新節(jié)點的同時,對已形成的邊進行維護,通過1.1節(jié)中描述的實值概念格提取規(guī)則的檢驗,增加相應(yīng)的邊,消除冗余的邊,當所有的概念添加完畢后,完成構(gòu)造。

針對實值形式背景取值復(fù)雜的特點,采用閉包算子的思想單獨在算法中設(shè)計子函數(shù)對區(qū)間值進行比較。

2.2 算法的并行化改造與實現(xiàn)

實值形式背景的概念格構(gòu)造算法之所以復(fù)雜程度高,是因為在同一屬性下不同對象的取值是由單個區(qū)間或多個不相交的區(qū)間組成的集合,它們之間的交并運算在算法設(shè)計中要考慮的情況既多又繁雜,因此,將串行算法進行并行化處理,是提高算法運算效率的有效途徑[14]。下面給出對算法Real進行改進后得到的并行算法Para-Real。

Algorithm Para-Real

輸入:原始實值形式背景L

輸出:實概念矩陣L*

BEGIN

size(L)=[m,n];

L0=(?,[]);/*初始化概念*/

Xi=sealing(Xi);/*將對象序號0-1化*/

Z_new=X1;

將Xi加入到Z_new；

size(Z_new)=[m_1,n_1];/*更新L_new中概念的個數(shù)*/

FORj=1:m_1

Z=Xi|Xj;

將Z加入到Z＿new;

ENDFOR

ENDFOR

PARFORr=1:(n-1)/4/*將形式背景中的數(shù)據(jù)按屬性進行分組執(zhí)行*/

B_newr=B1r;

FORi=2:m

將Bir加入到B_newr；

size(B_new)=[m_1,n_1];

FORj=1:m_1

BZr=Bjr∪Bir;/*Xi和Xj在屬性r下對應(yīng)的區(qū)間比較*/

將BZr加入B_new;

ENDFOR

ENDFOR;

B_new=[B_newB_newr];

ENDPARFOR

L_new=xiao(L_new);

L_new=[Z,B_new];

L*=L0∪L_new

END

由于Real算法的思想是在不斷添加新邊的同時又不斷更新概念,因此消除冗余概念的算法是在生成概念的算法中進行嵌套,而程序可以并行執(zhí)行的前提是算法可以分成多個單元交由多個核心同時計算并最后整合。因此,Para-Real的思想是:先將原實值形式背景按屬性的個數(shù)n劃分成縱向量[m,1]的形式,每組向量各自單獨執(zhí)行概念的生成算法(注:在不進行消除算法的情況下,各組向量生成的帶冗余的概念總數(shù)相同),最后合并再進行消除。

2.3 并行算法的實現(xiàn)

Matlab提供的多種并行計算的方式,其中MDCS是基于搭建集群的一種分布式計算服務(wù),在搭建好之后,可以通過一臺主機向集群中的其他機器分配任務(wù),最后各機器將計算結(jié)果返回主機,主機整合任務(wù),完成計算任務(wù)[5]。步驟如下:

1)mdce start/*MDCE實際上是一個進程*/

2)startjobmanager/*啟動一個任務(wù)管理進程*/

3)startworker/*需要啟動在sceduler中注冊過的若干個worker用于執(zhí)行任務(wù)*/

4)創(chuàng)建作業(yè)并提交至任務(wù)執(zhí)行隊列

5)返回結(jié)果,并銷毀作業(yè)任務(wù)釋放內(nèi)存。

圖1 集群上算法的并行計算流程Fig.1 Parallel Computing Program of Algorithm in Cluster

上述Par-Real算法的并行處理流程如圖1所示。利用findResource()函數(shù)調(diào)出已經(jīng)創(chuàng)建好的一個集群任務(wù)管理對象,打開Matlab的并行計算池,運行Par-Real算法程序,創(chuàng)建的任務(wù)提交至任務(wù)隊列中,通過JobManager為各個worker分配任務(wù),worker執(zhí)行完任務(wù)將結(jié)果返回給JobManager,JobManager歸并結(jié)果,并返回給主控制臺。

3 數(shù)值實驗

本節(jié)通過數(shù)值實驗對上一節(jié)提出的算法Real進行評估。由于實值形式背景的復(fù)雜性,本節(jié)實驗需要一些中、大型的實值形式背景,經(jīng)過實驗驗證[15],對于兩個對象和屬性個數(shù)相同的實值形式背景M1和M2,可以融合構(gòu)造一個新矩陣:

實驗環(huán)境采用Matlab 2012a Win64版本(含License Manager 11.9),并行計算平臺為MATLAB Distributed Computing Server 6.0,編譯環(huán)境為Microsoft Visual C++2010。MDCE集群由一臺主控制節(jié)點和兩臺從節(jié)點構(gòu)成,主節(jié)點配置為Inter(R)Core(TM)2 Quad CPU Q6600 @2.40GHz,4.00GB內(nèi)存和500GB硬盤。從節(jié)點的配置為AMD phenom(tm)8400 Triple-Core Processor 2.10 GHz,3.25GB內(nèi)存和300GB硬盤。其他采用系統(tǒng)默認配置。

表2 實值形式背景

表3 串、并行算法對比Tab.3 Comparison of Serial and Parallel Algorithms

表3中根據(jù)得出的串行和并行運行時間數(shù)據(jù),分別計算了two worker和four worker情況下的串并行加速比(串行時間/并行時間)?？梢钥闯?在數(shù)據(jù)量小的情況下,并行的效率比數(shù)據(jù)量大時低,這是因為并行的核心之間有數(shù)據(jù)通信,如果通信時間相對于計算時間所占的比例較高時,那么數(shù)據(jù)通信對并行效率的影響較大。隨著數(shù)據(jù)量的增大,運行時間的串并行加速比逐漸增大,并行的效率提高。當worker數(shù)增加,并行的效率進一步得到提高,這說明當條件允許的情況下,計算單元增加或集群中加入的計算機數(shù)量增加,都有助于進一步提高構(gòu)造實值概念格并行算法的效率。

需要說明的是,實值形式背景的數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜,因而構(gòu)造實值概念格的過程中算子的設(shè)計更為復(fù)雜,相較于文獻[7]中最高達到320個對象|U|,本文實驗的數(shù)據(jù)量僅提高了一個數(shù)量級,在面對大量數(shù)據(jù)集的概念格提取問題上,算法的改進還需要進一步的探索。

4 結(jié) 語

針對實值形式背景,本文結(jié)合了經(jīng)典概念格漸進式構(gòu)造算法時間性能好、穩(wěn)定等特點,提出了一種構(gòu)造實值概念格的算法Real,同時對其在Matlab集群環(huán)境下進行了并行化處理,通過實驗驗證了串并行算法的可行性,并給出實驗結(jié)果,對比了串并行運行時間加速比的變化,表明并行計算在數(shù)據(jù)量大的時候效率更高,計算節(jié)點越多并行算法相對串行算法的優(yōu)勢越明顯。由于算法的復(fù)雜性大,該算法在數(shù)值信息過大時并沒有很好的適應(yīng)性,下一步的工作需要尋找更好的方法來提高算法效率。進一步討論實值形式背景中的對象約簡問題和決策分析對概念格構(gòu)造算法效率的提高有借鑒意義。

參考文獻：

[1] WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[J]. Orderd Sets D Reidel, 1982, 83:314-339.

[2] 李金海, 鄧碩. 概念格與三支決策及其研究展望[J]. 西北大學學報(自然科學版), 2017, 47(3):321-329.

[3] 錢婷, 賀曉麗. 區(qū)間集概念格的構(gòu)造理論研究[J]. 西北大學學報(自然科學版), 2017, 47(3):330-335.

[4] 楊建峰, 魏玲. 基于差別矩陣的區(qū)間值形式背景屬性約簡[J]. 西北大學學報(自然科學版), 2012, 42(3):365-369.

[5] 劉維. 實戰(zhàn)Matlab之并行程序設(shè)計[M]. 北京:北京航空航天大學出版社，2012.

[6] JAOUA A, ELLOUMI S. Galois connection, formal concepts and Galois lattice in real relations: Application in a real classifier [J]. The Journal of Systems and Software, 2002, 60: 149-163.

[7] 李金海. 面向規(guī)則提取的概念格約簡方法及其算法實現(xiàn)[D]. 西安:西安交通大學, 2012.

[8] YANG H Z, LEUNG Y, SHAO M W. Rule acquisition and attribute reduction in real decision formal contexts[J].Soft Computing，2011, 15(6): 1115-1128.

[9] LI Y, LIU Z T, SHEN X J, et al. Theoretical research on the distributed construction of concept lattices[C]∥International Conference on Machine Learning and Cybernetics. IEEE, 2003，1:474-479.

[10] BORDAT J P. Calculpratique du treillis de Galois d′unecorrespondance[J].Matheématiques Informatiques Et Sciences Humaines, 1986, 96: 31-47,101.

[11] GANTER B. Two basic algorithms in concept analysis[C]∥International Conference on Formal Concept Analysis. Springer-Verlag, 2010: 312-340.

[12] GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices [J]. Computational Intelligence, 1995, 11(2): 246-267.

[13] LI J H, MEI C L, LV Y J. Incomplete decision contexts: Approximate concept construction, rule acquisition and knowledge reduction [J]. International Journal of Approximate Reasoning, 2013, 54(1): 149-165.

[14] 張磊. 基于同義概念和同類概念的概念格并行構(gòu)造模型[D].開封:河南大學,2006.

[15] 王磊, 魏玲, 姚廣. 橫向合成背景的概念生成[J].西北大學學報(自然科學版), 2010, 40(2):195-198.