毛華，劉祎超

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

?

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

毛華，劉祎超

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

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

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

中文引用格式：毛華，劉祎超. 基于權(quán)值最大圈的概念格構(gòu)造算法[J]. 智能系統(tǒng)學(xué)報(bào)， 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]是對(duì)背景中屬性、對(duì)象及其關(guān)系進(jìn)行分析研究的理論。它提供了一種支持?jǐn)?shù)據(jù)分析和知識(shí)處理的數(shù)學(xué)工具[2-3]。目前,概念格已經(jīng)廣泛應(yīng)用于數(shù)據(jù)挖掘[4]、信息處理[5]、軟件工程[6]和其他方面[7-8]。概念格理論的研究不僅能用于解決知識(shí)發(fā)現(xiàn)領(lǐng)域中所涉及的關(guān)聯(lián)規(guī)則、蘊(yùn)含規(guī)則、分類規(guī)則的提取，還能夠?qū)崿F(xiàn)對(duì)信息的有機(jī)組織、減少冗余度、簡(jiǎn)化信息表，所以對(duì)概念格理論及其算法的研究具有重要的意義。

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

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

1　基本概念

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

1.1概念格

定義1

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

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

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

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

例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對(duì)應(yīng)的形式背景的概念格見圖1。

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

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

1.2圖論

定義21)稱數(shù)學(xué)結(jié)構(gòu)G={V(G),E(G), ψG}為一個(gè)圖，其中V(G)為非空集合，ψG是從集合E(G)到V(G)V(G)的一個(gè)映射, 則稱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)，簡(jiǎn)寫成e=uv，稱u是有向邊e的尾，v是有向邊e的頭。擦掉有向圖中的箭頭，則得到無(wú)向圖。

2)在頂邊交錯(cuò)鏈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)在一個(gè)無(wú)向圖中，只有一個(gè)頂?shù)娜凶鲎原h(huán)；ψG(e1)= ψG(e2)=(u,v)，則稱e1與e2是重邊。

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

1.3屬性拓?fù)鋱D

定義3設(shè)(O,M,I)是一個(gè)形式背景。按如下規(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之間的公共對(duì)象{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)對(duì)應(yīng)的屬性拓?fù)鋱D。

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

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

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

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

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

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

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

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

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

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

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

例3 下面圖3為圖2所對(duì)應(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)是一個(gè)形式背景，(R(O,M,I)，w)是(O,M,I)對(duì)應(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}的最大圈。

說(shuō)明3為了描述方便，有時(shí)將w(mi,mj)簡(jiǎn)寫為w。

2.2 算法過(guò)程

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

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

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

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

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

3)①初始將W(R(O,M,I)，w)賦值給Wr，對(duì)任意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)，又因?yàn)閃(R(O,M,I)，w)是有限的，因此有限步后算法可以停止。

若W(R(O,M,I)，w)中的元素滿足wi∩wj=wt，wt，此時(shí)會(huì)將新生成的wt添加到W(R(O,M,I)，w)中，由于wrws，wtO，O為有限的，因此經(jīng)過(guò)有限步后一定可以進(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)是只有一個(gè)頂點(diǎn)的圈；重邊是由兩個(gè)頂點(diǎn)的圈；由定義2中3)可知，非自環(huán)非重邊的圈之頂點(diǎn)個(gè)數(shù)大于2。

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

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

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

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

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

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

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

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)圈為重邊時(shí)

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。這就是說(shuō)，除m1,m2外，不存在其他屬性所擁有的對(duì)象集包含w(m1,m2)，所以(w(m1,m2)，Y)β(O,M,I)。

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

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

引理3設(shè)W(R(O,M,I)，w)是一個(gè)集族，則任意的其中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)是一個(gè)集族，則對(duì)于任意的wi,wj,wtW(R(O,M,I)，w)，wu有且僅有wi∩wj=、wi∩wj=wt或wi∩wj=wu，3種情況之一發(fā)生：

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

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

1)wi∩wj=

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

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

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

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

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

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

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

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

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

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

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

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

3　實(shí)例

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

表2　(O1,M1,I1)

其中，a1代表博主高學(xué)歷，a2代表博主中等學(xué)歷，a3代表博主低學(xué)歷，a4代表政治立場(chǎng)為左派，a5代表政治立場(chǎng)中立，a6代表政治立場(chǎng)為右派，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)}。

對(duì)于任意兩個(gè)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)中②，停止。

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

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

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

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

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

4　結(jié)束語(yǔ)

本文結(jié)合圖論的知識(shí)，將形式背景對(duì)應(yīng)的屬性拓?fù)鋱D弱化，提出了一種利用權(quán)值最大圈尋找概念的算法。與現(xiàn)有的算法比較，本文提出一種新的思路來(lái)搜索概念，此外通過(guò)弱化的屬性拓?fù)鋱D，對(duì)于概念的可視化也得到了很好的體現(xiàn)；通過(guò)實(shí)例可知，該方法能夠有效地構(gòu)造概念格，為知識(shí)獲取和數(shù)據(jù)處理提供了一種有益的思想。通過(guò)分析可知，雖然本文提出的算法產(chǎn)生全部概念的空間復(fù)雜度降低，但由于其時(shí)間復(fù)雜度仍為指數(shù)級(jí)，因此對(duì)于數(shù)據(jù)量較大的情況，計(jì)算時(shí)間方面需要進(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ì)算機(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]鄧君, 馬曉君, 張巨峰, 等. 基于概念格的實(shí)體檔案館用戶行為研究[J]. 圖書情報(bào)工作, 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ì)算機(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ì)算機(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]李立峰, 劉三陽(yáng), 羅清君. 弦二部圖的概念格表示[J]. 電子學(xué)報(bào), 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]. 長(zhǎng)春: 吉林人民出版社, 1982.

毛華，女，1963年生，教授，博士，主要研究方向?yàn)橛?jì)算機(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.

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

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

TP18

A

1673-4785(2016)04-0519-07