毛華，劉祎超

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002)

?

基于權(quán)值最大圈的概念格構(gòu)造算法

毛華，劉祎超

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002)

概念格作為一種有效的知識發(fā)現(xiàn)與數(shù)據(jù)處理的工具，在許多領(lǐng)域得到了廣泛應(yīng)用。尋找形式背景下的所有概念是概念格理論研究的一個基本問題。對于一個給定的形式背景，在屬性拓?fù)鋱D的基礎(chǔ)上，結(jié)合圖論的思想，給出了一種概念格的構(gòu)造算法。算法過程如下:首先，構(gòu)造弱化的屬性拓?fù)鋱D；其次，通過尋找弱化的屬性拓?fù)鋱D中的每個權(quán)值最大圈方法來生成概念,形式背景的所有概念被生成；最后，構(gòu)造出概念格。通過分析說明此算法復(fù)雜度比以往的一些算法復(fù)雜度低。此外，用一個實例驗證了這一算法的有效性與正確性。為知識獲取提供了有益的思路與方法。

形式背景；概念格；概念；權(quán)值；最大圈；屬性拓?fù)?；?shù)據(jù)處理

中文引用格式：毛華，劉祎超. 基于權(quán)值最大圈的概念格構(gòu)造算法[J]. 智能系統(tǒng)學(xué)報， 2016, 11(4): 519-525.

英文引用格式：MAO Hua， LIU Yichao. An algorithm for concept lattice construction based on maximum cycles of weight values[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 519-525.

概念格[1]是對背景中屬性、對象及其關(guān)系進(jìn)行分析研究的理論。它提供了一種支持?jǐn)?shù)據(jù)分析和知識處理的數(shù)學(xué)工具[2-3]。目前,概念格已經(jīng)廣泛應(yīng)用于數(shù)據(jù)挖掘[4]、信息處理[5]、軟件工程[6]和其他方面[7-8]。概念格理論的研究不僅能用于解決知識發(fā)現(xiàn)領(lǐng)域中所涉及的關(guān)聯(lián)規(guī)則、蘊(yùn)含規(guī)則、分類規(guī)則的提取，還能夠?qū)崿F(xiàn)對信息的有機(jī)組織、減少冗余度、簡化信息表，所以對概念格理論及其算法的研究具有重要的意義。

概念是人類進(jìn)行知識表達(dá)的一種手段，數(shù)據(jù)庫知識發(fā)現(xiàn)的過程就是將數(shù)據(jù)庫中蘊(yùn)含的知識形式化成有用的概念的過程。對形式背景的表示及尋找背景下的所有概念是概念格理論研究的基本問題。近年來許多學(xué)者從圖論的方面對概念格進(jìn)行研究，例如，張濤等[9]提出用屬性拓?fù)鋱D來表示形式背景，并在此屬性拓?fù)鋱D的基礎(chǔ)上進(jìn)行概念計算；A.Berry等[10]將形式背景構(gòu)造成二部圖，利用團(tuán)的思想生成概念；此外，李立峰等[11]利用弦二部圖對概念格進(jìn)行表示，其中判斷弦二部圖中是否有圈，是判斷弦二部圖的關(guān)鍵。這也證實圖論特別是圖中的圈，在概念格的研究中之重要。

本文結(jié)合圖論的知識，將形式背景以屬性拓?fù)鋱D表示出來，通過構(gòu)造弱化的屬性拓?fù)鋱D，然后尋找弱化的屬性拓?fù)鋱D中的權(quán)值w之最大圈，用以生成概念，從而構(gòu)造出概念格，并結(jié)合實例分析了這一算法的有效性。

1　基本概念

本節(jié)將回顧概念格與圖論的一些性質(zhì)和定義，關(guān)于概念格的更多內(nèi)容參見文獻(xiàn)[12]，有關(guān)圖論詳細(xì)內(nèi)容參見文獻(xiàn)[13]，并且簡單描述形式背景的屬性拓?fù)鋱D表示方法，更多詳細(xì)內(nèi)容參見文獻(xiàn)[9，14]。

1.1概念格

定義1

1)形式背景(O,M,I)是一個三元組，其中O是對象集，M是屬性集，IOM。O和M中的元素分別稱為對象和屬性。

2)設(shè)A?O且B?M, 定義

若A′=B且B′=A，則元素對(A,B)是一個概念。A為概念(A,B)的外延，B為概念(A,B)的內(nèi)涵。形式背景(O，M，I)的所有概念的集合用β(O,M,I)表示，稱β(O,M,I)為(O,M,I)的概念格。

3)對于β(O,M,I)中的概念(A1,B1)和(A2,B2)，如果A1A2，我們寫作(A1,B1)≤(A2,B2)。很容易看到(β(O,M,I)；≤)是一個完備格。

例1形式背景(O,M,I)，其中O={1,2,3,4,5,6}，M={a,b,c,d,e,f,g}，關(guān)系I如表1所示。

表1　形式背景(O,M,I)

表1對應(yīng)的形式背景的概念格見圖1。

圖1　β(O, M, I)Fig.1　β(O, M, I)

說明1本文所討論的形式背景中不含有滿足以下條件的屬性和對象，mM,m′=O或m′=；gO,g′=M或g′=。

1.2圖論

定義21)稱數(shù)學(xué)結(jié)構(gòu)G={V(G),E(G), ψG}為一個圖，其中V(G)為非空集合，ψG是從集合E(G)到V(G)V(G)的一個映射, 則稱G是一個以V(G)為頂集合，以E(G)為邊集合的有向圖，V(G)中的元素稱為G的頂點(diǎn)。E(G)中的元素稱為G的邊，ψG稱為G的關(guān)聯(lián)函數(shù)。若ψG(e)=(u,v)，eE(G)，(u,v)V(G)V(G)，簡寫成e=uv，稱u是有向邊e的尾，v是有向邊e的頭。擦掉有向圖中的箭頭，則得到無向圖。

2)在頂邊交錯鏈P=v0e1v1e2…vkek中，eiE(G)，i=1,2,…,k，vjV(G)，j=1,2,…,k，且ei=vi-1vi，則稱P是G的一條道路，其中允許vi=vj或ei=ej，ij。稱v0是p的起點(diǎn)，vk是p的終點(diǎn)。各頂相異的道路稱為軌道；起點(diǎn)與終點(diǎn)重合的軌道稱為圈。

3)在一個無向圖中，只有一個頂?shù)娜凶鲎原h(huán)；ψG(e1)= ψG(e2)=(u,v)，則稱e1與e2是重邊。

說明2由上述定義可知自環(huán)、重邊均為圈。

1.3屬性拓?fù)鋱D

定義3設(shè)(O,M,I)是一個形式背景。按如下規(guī)則構(gòu)造屬性拓?fù)鋱D(A(O,M,I)，w):

1) 設(shè)m1，m2M且m1≠m2。

2) 設(shè)(A(O,M,I)，w)為(O,M,I)的屬性拓?fù)鋱D，e(mi,mj)E(A(O,M,I)，w))，E(A(O,M,I)，w)為(A(O,M,I)，w)的邊集，e(mi,mj)上的權(quán)值用w(mi,mj)表示，w(mi,mj)為屬性mi和mj之間的公共對象{g1,g2,…,gn}的集合，稱w(mi,mj)為mi和mj之間的權(quán)值。

3)設(shè)mM，bM，若與m連接的邊均為非單向入邊，即與m連接的邊均為mb或mb，則稱m為頂層屬性，頂層屬性的集合用T表示。

例2圖2為表1形式背景(O,M,I)對應(yīng)的屬性拓?fù)鋱D。

圖2　 (A(O,M,I)，w)Fig.2　(A(O,M,I)，w)

引理1 設(shè)(O,M,I)是一個形式背景，(A(O,M,I)，w)為(O,M,I)的屬性拓?fù)鋱D，若mT，則(m′, m)β(O,M,I)。

2　概念格的構(gòu)造

在搜索概念的過程中，為了不受方向的限制，首先進(jìn)行屬性拓?fù)鋱D弱化，將有向圖變?yōu)闊o向圖，實際上目前結(jié)合圖論生成概念格的算法，都是在無向圖的基礎(chǔ)上進(jìn)行的。其次，給出弱化后屬性拓?fù)鋱D關(guān)于某個權(quán)值的最大圈的定義。最后，給出利用權(quán)值的最大圈構(gòu)造概念算法，并進(jìn)行算法分析。

2.1弱化的屬性拓?fù)鋱D

設(shè)(O,M,I)是一個形式背景，按照如下規(guī)則對屬性拓?fù)鋱D進(jìn)行弱化：

1)去掉屬性拓?fù)鋱D中的方向，得一無向圖。

2)若m在(A(O,M,I)，w)中為頂層屬性，則在1)中的無向圖中，加一個以m為頂點(diǎn)的自環(huán)。

3)若在1)中的無向圖中，包含權(quán)值w(u,v)的只有一條邊e，其中，u、v為e的兩個端點(diǎn)，則在u與v之間再添加一條邊e1(圖中用虛線表示)，并且令e1的權(quán)值也為w(u,v)。

完成1)～3)后得到的加權(quán)無向圖稱為弱化的屬性拓?fù)鋱D，用(R(O,M,I)，w)表示。

此外，顯然，在上述3)中的e與e1是重邊。

例3 下面圖3為圖2所對應(yīng)的(A(O,M,I)，w)之弱化的屬性拓?fù)鋱D。

圖3　(R(O,M,I)，w)Fig.3　(R(O,M,I)，w)

定義4 設(shè)(O,M,I)是一個形式背景，(R(O,M,I)，w)是(O,M,I)對應(yīng)的弱化的屬性拓?fù)鋱D，{m1,m2，…，mh}M且{m1,m2，…，mh}，若不存在任意maM,ma{m1,m2，…，mh}, 使得{m1,m2，…，mh}={m1,m2，…，mh,ma}，則稱Y={m1,m2，…，mh}為權(quán)值w({m1,m2，…，mh})的最大圈。

例如圖3中，Y={bdga}為權(quán)值{2}的最大圈。

說明3為了描述方便，有時將w(mi,mj)簡寫為w。

2.2 算法過程

對于給定的形式背景(O,M,I)，構(gòu)造概念格的過程如下：

輸入形式背景(O,M,I)以及W(R(O,M,I)，w)={w1,w2,…,wn}，wr

輸出所有概念β(O,M,I){(O,)，(,M)}。

1)對于(O,M,I)，繪制屬性拓?fù)鋱D，根據(jù)屬性拓?fù)鋱D中的箭頭指向，確定頂層屬性集合T。

2)將屬性拓?fù)鋱D轉(zhuǎn)化為弱化的屬性拓?fù)鋱D。

3)①初始將W(R(O,M,I)，w)賦值給Wr，對任意wi，wjWr，求。若wi∩wj=或wi∩wj=wt，此處wi,wj,wt。則進(jìn)行4)。

②若wi∩wj=wt，wt，則將Wrr={wt：wi∩wj=wt，wi,wj,W(R(O,M,I)，w)，wtW(R(O,M,I)，w)}添加到W(R(O,M,I)，w)中。將Wrr賦值給Wr，執(zhí)行①。

5)①根據(jù)4)的原則，若W中存在ws+1，s=1,2,…,M2，則選定ws+1，重復(fù)4)。

②若W中不存在ws+1，則停止。

若W(R(O,M,I)，w)中的元素滿足3)中的①，若wi∩wj=，或wi∩wj=wt，此處wi,wj,wt，則能夠進(jìn)行4)、5)，又因為W(R(O,M,I)，w)是有限的，因此有限步后算法可以停止。

若W(R(O,M,I)，w)中的元素滿足wi∩wj=wt，wt，此時會將新生成的wt添加到W(R(O,M,I)，w)中，由于wrws，wtO，O為有限的，因此經(jīng)過有限步后一定可以進(jìn)行3)中①，因此有限步后算法可停止。

2.3算法分析

引理2圈有且僅有以下3種情況：

1)由一條邊構(gòu)成，也即自環(huán)；

2)由兩條邊構(gòu)成，也即重邊；

3)由3條或3條以上的邊構(gòu)成，也即非自環(huán)非重邊的圈。

證明由定義2中3)可知，自環(huán)是只有一個頂點(diǎn)的圈；重邊是由兩個頂點(diǎn)的圈；由定義2中3)可知，非自環(huán)非重邊的圈之頂點(diǎn)個數(shù)大于2。

當(dāng)圈只有一個頂點(diǎn)時，根據(jù)定義2中3)可知，此時的圈為一個自環(huán)；

當(dāng)圈有兩個頂點(diǎn)時，根據(jù)定義2中3)可知，此時的圈為重邊；

當(dāng)圈的頂點(diǎn)個數(shù)大于2時，符合定義2中2)。

因此，圈有且僅有自環(huán)、重邊、非自環(huán)非重邊的圈3種情況。

定理1設(shè)(O,M,I)是一個形式背景，(R(O,M,I)，w)是(O,M,I)對應(yīng)的弱化的屬性拓?fù)鋱D，權(quán)值最大圈一定能夠生成一個概念。

證明由引理2可知，弱化的屬性拓?fù)鋱D的權(quán)值w最大圈有且僅有3種情況，下面關(guān)于這3種情況分別說明。

1)當(dāng)圈為自環(huán)時

mM，圈Y={m}，由弱化的屬性拓?fù)鋱D的構(gòu)造1)可知，有mT。根據(jù)引理1，(m′,m)β(O,M,I)。而m′=w(m,m)，因此，(w(m,m),m)β(O,M,I)。

2)當(dāng)圈為重邊時

m1,m2M，圈Y={m1,m2}，由弱化的屬性拓?fù)鋱D的構(gòu)造2)可知，不存在其他權(quán)值為w(m1,m2)的邊，即不存在其他頂mi,mjM，使w(m1,m2)w(mi,mj),ij,i≥3,j≥1。這就是說，除m1,m2外，不存在其他屬性所擁有的對象集包含w(m1,m2)，所以(w(m1,m2)，Y)β(O,M,I)。

3)=當(dāng)圈的頂點(diǎn)個數(shù)大于等于3時

m1,m2, … ，miM，i≥3，若圈Y={m1,m2, … mi}，證明過程與第2種情況類似，易證(w(m1,m2)，Y)β(O,M,I)。

引理3設(shè)W(R(O,M,I)，w)是一個集族，則任意的其中wi,wj,wtW(R(O,M,I)，w)，wu，它們之間的關(guān)系有且僅有以下3種情況之一發(fā)生：

1)wi∩wj=；

2)wi∩wj=wt；

3)wi∩wj=wu。

證明根據(jù)文獻(xiàn)[15]，可得若W(R(O,M,I)，w)是一個集族，則對于任意的wi,wj,wtW(R(O,M,I)，w)，wu有且僅有wi∩wj=、wi∩wj=wt或wi∩wj=wu，3種情況之一發(fā)生：

定理2設(shè)(O,M,I)是一個形式背景，(R(O,M,I)，w)是(O,M,I)對應(yīng)的弱化的屬性拓?fù)鋱D，通過權(quán)值w最大圈算法一定能夠得到β(O,M,I){(O,)，(,M)}。

證明由引理3可知集族W(R(O,M,I)，w)中的權(quán)值之間有且僅有3種情況，對于任意的wi,wj,wtW(R(O,M,I)，w)，wu以下對引理3中的3種情況分別說明。

1)wi∩wj=

說明任意3個屬性之間沒有公共對象，根據(jù)屬性拓?fù)鋱D的構(gòu)造過程，其弱化的屬性拓?fù)鋱D為定理1的第2種情況，得到的W(R(O,M,I)，w)能夠包括所有概念的外延，因此，依次搜索W(R(O,M,I)，w)中的每一個權(quán)值w最大圈，即可得到β(O,M,I){(O,)，(,M)}。

2)wi∩wj=wt，wtW(R(O,M,I)，w)，i,j,t=1,2,…,M2，說明得到的W(R(O,M,I)，w)能夠包括所有概念的外延，符合定理的第2、3種情況。因此，依次搜索W(R(O,M,I)，w)中的每一個權(quán)值w最大圈，即可得到β(O,M,I){(O,)，(,M)}。

3)若wi∩wj=wt，wtW(R(O,M,I)，w)，i,j,t=1,2,…,M2，則說明當(dāng)前W(R(O,M,I)，w)中不能包含所有概念的外延，將Wr={wt：wi∩wj=wt，wtW(R(O,M,I)，w)}添加到W中，只需對Wr中的任意兩個元素取交集即可，由于O是有限的，因此一定會有wi∩wj=wt，wtW(R(O,M,I)，w)，i,j,t=1,2,…,M2，此時說明得到的W(R(O,M,I)，w)能夠包括所有概念的外延，并且W(R(O,M,I)，w)中的元素對應(yīng)的最大圈符合定理1的第2、3種情況。因此，依次搜索W(R(O,M,I)，w)中的每一個權(quán)值w最大圈，即可得到β(O,M,I){(O,)，(,M)}。

以上說明了本算法的正確性。下面將通過與已有的圖論方法構(gòu)造概念格的相關(guān)著名算法或方法的比較，分析得出本算法的優(yōu)勢。

1)張濤等[14]在屬性拓?fù)涞幕A(chǔ)上給出概念計算方法，實際上是將圖論中已有的深度優(yōu)先算法應(yīng)用于概念的尋找，如此可能導(dǎo)致產(chǎn)生冗余概念。冗余概念的產(chǎn)生必然導(dǎo)致算法的儲存空間的增加，引發(fā)空間復(fù)雜度的加大。

本文算法用圖論中的權(quán)值與最大圈結(jié)合來尋找概念，由于不會重復(fù)對同一權(quán)值尋找其相應(yīng)的最大圈，因此不會有冗余概念的產(chǎn)生。從而，必然在概念尋找中，降低數(shù)據(jù)的儲存空間，空間復(fù)雜度較張濤等的方法減少成為顯然之事。

對于弱化的屬性拓?fù)鋱D產(chǎn)生概念有：

以上兩種情形說明，當(dāng)情形1)時，本文算法的復(fù)雜度小于Berry等的；當(dāng)情形2)時，本文算法的復(fù)雜度與Berry等的相同。這說明，對于情形1)，本文的算法優(yōu)于Berry等的，雖然在其他情況(也就是情形2))，本文的算法與Berry等的具有相同的時間復(fù)雜度。

再有，由圖論知識可知，每一個團(tuán)必包含至少一個圈，所以在判斷團(tuán)的過程中必然存在對圈的判斷過程，當(dāng)一個團(tuán)中含有兩個以上圈時，此時對團(tuán)的判定過程會重復(fù)圈的判斷過程。因此，Berry等的方法會造成數(shù)據(jù)存儲量過大。而本文算法，不會對相同權(quán)值的圈進(jìn)行重復(fù)判斷與存儲，因此，降低了數(shù)據(jù)存儲空間復(fù)雜度。

3)李立峰等[11]僅是從理論方面指出弦二部圖的概念格表示，并沒有給出算法過程。所以他們的方法只是理論過程，而無法直接實現(xiàn)。

本文中不僅給出了理論分析，并且將理論的內(nèi)容通過一個可行的算法加以實現(xiàn)，故此，本文的思想和方法可操作性強(qiáng)，易于直接理解與實現(xiàn)。

由以上1)～3)的分析可以看出，本文給出的算法與已有算法相比，計算出全部概念的時間復(fù)雜度并不低于以往的算法，基本相同。在數(shù)據(jù)存儲空間方面，本文給出的算法與已有算法相比，空間復(fù)雜度降低。這樣必然使得本算法在整個計算過程能在占用更小內(nèi)存的情況下完成，同時也就對計算機(jī)器系統(tǒng)的運(yùn)行空間降低了要求。因此本文算法要優(yōu)于其他一些已有算法或方法。

3　實例

結(jié)合實例，說明第2.2節(jié)中的算法有效性。以表2為形式背景(O1,M1,I1)，進(jìn)行概念的搜索，該背景從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中，隨機(jī)選取BLOGGER數(shù)據(jù)集的前40個對象進(jìn)行試驗，整理后得到如表2所示的形式背景。

表2　(O1,M1,I1)

其中，a1代表博主高學(xué)歷，a2代表博主中等學(xué)歷，a3代表博主低學(xué)歷，a4代表政治立場為左派，a5代表政治立場中立，a6代表政治立場為右派，a7代表博客被當(dāng)?shù)孛襟w轉(zhuǎn)載。

根據(jù)1)，按照定義3中1)得到以表2為形式背景的屬性拓?fù)鋱D，如圖4。根據(jù)2)，按照定義4，構(gòu)造出弱化的屬性拓?fù)鋱D(R(O1,M1,I1)，w)，如圖5。

圖4　(A(O1,M1,I1)，w)Fig.4　(A(O1,M1,I1)，w)

根據(jù)3)，W={w(a1,a1),w(a2,a2),w(a3,a3),w(a4,a4),w(a6,a6),w(a7,a7),w(a1,a4),w(a1,a6),w(a1,a7),w(a2,a4),w(a2,a5),w(a2,a6),w(a2,a7),w(a3,a4),w(a3,a6),w(a4,a7),w(a5,a7),w(a6,a7)}。

對于任意兩個w(ai,aj)求交集，i，j=1,2,…,7，

根據(jù)3)中②，可以發(fā)現(xiàn)存在w(a1,a1)∩w(a4,a7)=w(a1,a4)∩w(a4,a7)=…={1}及w(a1,a1)∩w(a6,a7)=w(a1,a7)∩w(a6,a7)=…={3}，{1}，{3}W，將{1}與{3}添加到W，重復(fù)3)。

圖5　(R(O1,M1,I1)，w)Fig.5　(R(O1,M1,I1)，w)

根據(jù)4)，W={w(a1,a1),w(a2,a2),w(a3,a3),w(a4,a4),w(a6,a6),w(a7,a7),w(a1,a4),w(a1,a6),w(a1,a7),w(a2,a4),w(a2,a5),w(a2,a6),w(a2,a7),w(a3,a4),w(a3,a6),w(a4,a7),w(a5,a7),w(a6,a7), {1},{3}}。

根據(jù)5)中①，依次選擇W中的其他元素重復(fù)4)，概念分別為(1 3 7 9，a1)，(2 4 5 10，a2)，(1 5 8 9，a4)，(3 4 6 7，a6), (2 4 5，a2a7)，(1 5 8，a4a7)，(1 9，a1a4)，(3 7，a1a6)，(1 3，a1a7)，(2 10，a2a5)， (6 8，a3)，(3 4，a6a7)，(4，a2a6a7)，(5，a2a4a7)，(8，a3a4a7)，(6，a3a6)，(2,a2a5a7)，(1,a1a4a7)，(3,a1a6a7)。

根據(jù)5)中②，停止。

在本實例中，步驟2)，弱化屬性拓?fù)鋱D，以w(a1,a1)為例進(jìn)行復(fù)雜度計算，判斷是否有w(a1,a1)w(ai,aj)，其中i，j=1,2,…,16,對于w(a1,a1)進(jìn)行16次比較可得a1為頂層屬性。對每個wW重復(fù)上述比較過程，可得到弱化的屬性拓?fù)鋱D。

3)對任意兩個元素wi，wjW，i，j=1,2,…,16,取交集，此過程需要進(jìn)行次，得到W{1}{3}，對{{1}，{3}}執(zhí)行步驟3)中②，此過程進(jìn)行1次，可以看出符合3)中①，可轉(zhuǎn)4)。

4)取W中的元素w(a7,a7)，判斷w(a7,a7)w(ai,aj) 其中i，j=1,2,…,20，每個元素比較20次，尋找最大圈，得到概念(1 2 3 4 5 8，a7)。

5)依次取W中的其他元素，重復(fù)4)，在此例W中的18個元素，4)需要重復(fù)18次。

在復(fù)雜度上，本文算法與張濤等的算法相同。并且利用張濤等的算法對(O1,M1,I1)進(jìn)行概念的計算，得到的概念格與本文算法的結(jié)果相同。從而說明了本文算法的有效性與正確性。

4　結(jié)束語

本文結(jié)合圖論的知識，將形式背景對應(yīng)的屬性拓?fù)鋱D弱化，提出了一種利用權(quán)值最大圈尋找概念的算法。與現(xiàn)有的算法比較，本文提出一種新的思路來搜索概念，此外通過弱化的屬性拓?fù)鋱D，對于概念的可視化也得到了很好的體現(xiàn)；通過實例可知，該方法能夠有效地構(gòu)造概念格，為知識獲取和數(shù)據(jù)處理提供了一種有益的思想。通過分析可知，雖然本文提出的算法產(chǎn)生全部概念的空間復(fù)雜度降低，但由于其時間復(fù)雜度仍為指數(shù)級，因此對于數(shù)據(jù)量較大的情況，計算時間方面需要進(jìn)一步研究，以便提高應(yīng)用其進(jìn)行數(shù)據(jù)分析的效率。

[1]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Dordrecht: Springer, 1982.

[2]BELOHLAVEK R, SIGMUND E, ZACPAL J. Evaluation of IPAQ questionnaires supported by formal concept analysis[J]. Information sciences, 2011, 181(10): 1774-1786.

[3]NGUYEN T T, HUI S C, CHANG Kuiyu. A lattice-based approach for mathematical search using formal concept analysis[J]. Expert systems with applications, 2012, 39(5): 5820-5828.

[4]王旭楊, 李明. 基于概念格的數(shù)據(jù)挖掘方法研究[J]. 計算機(jī)應(yīng)用, 2005, 25(4): 827-829.

WANG Xuyang, LI Ming. Method of data mining based on concept lattice[J]. Computer applications, 2005, 25(4): 827-829.

[5]SIFF M, REPS T. Identifying modules via concept analysis[C]//Proceedings of International Conference on Software Maintenance. Washington, DC, USA: IEEE Computer Society, 1997: 170-179.

[6]FERJANI F, ELLOUMI S, JAOUA A, et al. Formal context coverage based on isolated labels: an efficient solution for text feature extraction [J]. Information sciences, 2012, 188: 198-214.

[7]鄧君, 馬曉君, 張巨峰, 等. 基于概念格的實體檔案館用戶行為研究[J]. 圖書情報工作, 2014, 58(12): 109-117.

DENG Jun, MA Xiaojun, ZHANG Jufeng, et al. Study on entity archives’ user behavior based on concept lattice[J]. Library and information service, 2014, 58(12): 109-117.

[8]張曉, 龍偉, 盧斌. 基于概念格的關(guān)聯(lián)規(guī)則在排產(chǎn)管理的應(yīng)用[J]. 計算機(jī)工程與應(yīng)用, 2014, 50(9): 264-270. v ZHANG Xiao, LONG Wei, LU Bin. Application of association rule based on concept lattice for scheduling management[J]. Computer engineering and applications, 2014, 50(9): 264-270.

[9]張濤, 任宏雷. 形式背景的屬性拓?fù)浔硎綶J]. 小型微型計算機(jī)系統(tǒng), 2014, 35(3): 590-593.

ZHANG Tao, REN Honglei. Attribute topology of formal context[J]. Journal of Chinese computer systems, 2014, 35(3): 590-593.

[10]BERRY A, SIGAYRET A. Representing a concept lattice by a graph[J]. Discrete applied mathematics, 2004, 144(1/2): 27-42.

[11]李立峰, 劉三陽, 羅清君. 弦二部圖的概念格表示[J]. 電子學(xué)報, 2013, 41(7): 1384-1388.

LI Lifeng, LIU Sanyang, LUO Qingjun. Representing chordal bipartite graph using concept lattice theory[J]. Acta electronica sinica, 2013, 41(7): 1384-1388.

[12]DAVEY B A, PRIESTLEY H A. Introduction to lattices and order[M]. 2nd ed. New York: Cambridge University Press, 2002: 66-69.

[13]王樹禾. 圖論[M]. 北京: 科學(xué)出版社, 2009.

[14]ZHANG Tao, REN Honglei, WANG Xiaomin. A calculation of formal concept by attribute topology[J]. ICIC express letters part B: applications, 2013, 4(3): 793-800.

[15]方嘉琳. 集合論[M]. 長春: 吉林人民出版社, 1982.

毛華，女，1963年生，教授，博士，主要研究方向為計算機(jī)數(shù)學(xué)及其應(yīng)用、擬陣?yán)碚?、離散數(shù)學(xué)。發(fā)表學(xué)術(shù)論文90余篇，其中被SCI、EI檢索20余篇。

An algorithm for concept lattice construction based on maximum cycles of weight values

MAO Hua， LIU Yichao

(School of Mathematics and Information Science, Hebei University, Baoding 071002， China)

As an effective tool for knowledge discovery and data processing, the concept lattice has been widely applied in many fields. Searching all concepts in a formal context is a basic problem for research into concept lattice theory. On the basis of attribute topology and combined with the idea of graph theory, an algorithm to construct a concept lattice in a fixed formal context is given. The process is as follows: firstly, a weakened attribute topology was built up; then, by applying the method of searching the maximum cycle with a weight in the above weakened attribute topology, all of the formal context concepts were obtained; finally the concept lattice was established. Subsequent analysis illustrated that the algorithm can reduce complexity compared with some existing algorithms. In addition, using an example, the accuracy and validity of the algorithm was verified. The result presents a useful idea and method for knowledge acquisition.

formal context; concept lattice; concept; weight value; maximum cycle; attributes topology; data processing

10.11992/tis.201606006

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.014.html

2016-06-02. 網(wǎng)絡(luò)出版日期：2016-08-08.

國家自然科學(xué)基金項目(61572011)；河北省自然科學(xué)基金項目(A2013201119).

劉祎超.E-mail：1026074348@qq.com.

TP18

A

1673-4785(2016)04-0519-07