郭澤蔚，姜 麟，李金海

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

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

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

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

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

1.1 實 集

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

顯然,當I=[μ,v]非空時,I就是由μ到v之間的全部實數構成的集合。對于兩個實區(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上所有實值構成的集合為R(U)。

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

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

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

表1 實值形式背景

(?X∈P(U))

(?X∈P(U))

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

1.3 概念格的構造算法

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

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

2 實值形式背景概念格構造算法

2.1 設計實值概念格的漸進式構造算法

以往圍繞概念格構造算法的研究主要集中于經典形式背景,而實值形式背景概念格的算法構造目前并沒有充分的研究成果。原因是實值形式背景的轉化較為困難,而且算法的復雜性非常大,對數據的適應性很差[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)結束時所有概念*/

FORi=2:m

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

將(Xi,Bi)加入到L_new;

FORj=1:m_1

Z=Xi|Xj;

FORr=1:(n_1)/4

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

BZ=[BZBZr];

ENDFOR

L′=(Z,BZ);

IFL′

單獨形成一個概念

將概念L′添加進L_new;

ENDIF

ENDFOR

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

ENDFOR

L*=L0∪L_new;

END

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

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

2.2 算法的并行化改造與實現

實值形式背景的概念格構造算法之所以復雜程度高,是因為在同一屬性下不同對象的取值是由單個區(qū)間或多個不相交的區(qū)間組成的集合,它們之間的交并運算在算法設計中要考慮的情況既多又繁雜,因此,將串行算法進行并行化處理,是提高算法運算效率的有效途徑[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中概念的個數*/

FORj=1:m_1

Z=Xi|Xj;

將Z加入到Z＿new;

ENDFOR

ENDFOR

PARFORr=1:(n-1)/4/*將形式背景中的數據按屬性進行分組執(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下對應的區(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的思想是:先將原實值形式背景按屬性的個數n劃分成縱向量[m,1]的形式,每組向量各自單獨執(zhí)行概念的生成算法(注:在不進行消除算法的情況下,各組向量生成的帶冗余的概念總數相同),最后合并再進行消除。

2.3 并行算法的實現

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

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

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

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

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

5)返回結果,并銷毀作業(yè)任務釋放內存。

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

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

3 數值實驗

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

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

表2 實值形式背景

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

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

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

4 結 語

針對實值形式背景,本文結合了經典概念格漸進式構造算法時間性能好、穩(wěn)定等特點,提出了一種構造實值概念格的算法Real,同時對其在Matlab集群環(huán)境下進行了并行化處理,通過實驗驗證了串并行算法的可行性,并給出實驗結果,對比了串并行運行時間加速比的變化,表明并行計算在數據量大的時候效率更高,計算節(jié)點越多并行算法相對串行算法的優(yō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ū)間集概念格的構造理論研究[J]. 西北大學學報(自然科學版), 2017, 47(3):330-335.

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

[5] 劉維. 實戰(zhàn)Matlab之并行程序設計[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ī)則提取的概念格約簡方法及其算法實現[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] 張磊. 基于同義概念和同類概念的概念格并行構造模型[D].開封:河南大學,2006.

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