徐 怡,霍思林

1(安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,合肥 230039) 2(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230601)

1 引 言

形式概念分析(Formal Concept Analysis,FCA)是Wille在1982年[1]提出的一種基于形式背景進(jìn)行數(shù)據(jù)分析和規(guī)則提取的工具,強(qiáng)調(diào)以人的認(rèn)知為中心,提供了一種與傳統(tǒng)的、統(tǒng)計(jì)的數(shù)據(jù)分析和知識(shí)表示完全不同的方法,成為人工智能學(xué)科的重要研究方向,在機(jī)器學(xué)習(xí)、信息檢索、和軟件工程等諸多領(lǐng)域得到廣泛的應(yīng)用[2-4].

從粒計(jì)算[5]的角度,現(xiàn)有的形式概念分析所研究的屬性大多是基于單粒度和單層次的結(jié)構(gòu)[6,7],忽視了在實(shí)際應(yīng)用中,屬性具有多粒度和多層次的結(jié)構(gòu)[8,9].例如屬性“教育背景”可以細(xì)化為屬性“學(xué)歷”、“學(xué)位”、“畢業(yè)院?！?反之屬性“學(xué)歷”、“學(xué)位”、“畢業(yè)院?！币部梢苑夯癁閷傩浴敖逃尘啊?不同粒度層次的屬性選擇會(huì)影響形式概念分析的精度或效率,所以基于形式背景構(gòu)造形式概念時(shí),根據(jù)實(shí)際問(wèn)題的求解需要,將粗粒度(高層次)屬性細(xì)化為兩個(gè)或多個(gè)細(xì)粒度(低層次)屬性,可以提高問(wèn)題分析的精度,將兩個(gè)或多個(gè)細(xì)粒度屬性泛化為粗粒度屬性,可以提高問(wèn)題分析的效率.為此,本文基于屬性分類的多層次結(jié)構(gòu),給出屬性泛化與細(xì)化的形式概念分析方法.主要工作是:首先提出了基于形式概念分析的屬性泛化與細(xì)化方法,其中屬性泛化增強(qiáng)了屬性的外在特征,提高了形式概念計(jì)算效率;屬性細(xì)化增強(qiáng)了屬性的內(nèi)在特征,提高了形式概念分析精度.然后,基于屬性分類層次的變化,提出了動(dòng)態(tài)的形式概念構(gòu)造算法,該算法通過(guò)自學(xué)習(xí)的方式對(duì)原有的知識(shí)加以使用,它不僅繼承了漸進(jìn)式算法的優(yōu)點(diǎn),還可以處理形式概念自身數(shù)據(jù)的變化.最后,通過(guò)實(shí)例和仿真實(shí)驗(yàn)表明本文所提算法的有效性,可以根據(jù)問(wèn)題分析的需要,靈活選擇屬性粒度層次,即動(dòng)態(tài)構(gòu)造形式概念算法,可以有效提高形式概念構(gòu)造的效率

第2節(jié)給出形式概念的基本定義和性質(zhì).第3節(jié)給出屬性分類的泛化與細(xì)化方法,并提出了形式概念的動(dòng)態(tài)構(gòu)造算法.第4節(jié),通過(guò)仿真實(shí)驗(yàn)驗(yàn)證本文所提算法的有效性.第5節(jié)總結(jié)全文.

2 形式概念分析的相關(guān)定義與算法

2.1 形式概念分析的相關(guān)定義

定義1[10].形式背景K是一個(gè)三元組:K=(G,M,I)

其中,G為所有對(duì)象的集合,M為所有屬性的集合,I?G×M為G和M中元素之間的關(guān)系合.對(duì)于g∈G,m∈M,(g,m)∈I或者gIm表示“對(duì)象g具有屬性m”.

表1 問(wèn)題背景
Table 1 Problem background

學(xué)生成績(jī)特長(zhǎng)語(yǔ)言表達(dá)S1優(yōu)秀唱歌不合格S2不優(yōu)秀體育合格S3優(yōu)秀體育不合格S4不優(yōu)秀唱歌合格S5不優(yōu)秀無(wú)合格

這里,表1是一個(gè)問(wèn)題背景,表示5個(gè)學(xué)生的個(gè)人信息,分別代表學(xué)生的成績(jī)、特長(zhǎng)和語(yǔ)言表達(dá).現(xiàn)將問(wèn)題背景轉(zhuǎn)化為一個(gè)形式背景K=(G,M,I)如表2所示,用1表示(g,m)∈I,用0表示(g,m)?I.對(duì)象集G={s1,s2,s3,s4,s5}為學(xué)生集合,屬性集M={a,b,c}表示學(xué)生個(gè)人信息的屬性集合,a表示學(xué)習(xí)成績(jī)是否“優(yōu)秀”(用1表示優(yōu)秀,0表示不優(yōu)秀),屬性b表示學(xué)生是否有“特長(zhǎng)”(1表示有,0表示無(wú)),屬性c表示學(xué)生“語(yǔ)言表達(dá)”是否合格(1表示合格,0表示不合格).對(duì)于對(duì)象g∈G和屬性m∈M,(g,m)∈I表示學(xué)生具有屬性m.

表2 形式背景
Table 2 Formal context

GabcS1110S2011S3110S4011S5001

定義2[10].設(shè)形式背景K=(G,M,I),對(duì)于集合A?G,記

AI={m∈M|(g,m)∈I,?g∈A}

(1)

相應(yīng)地,對(duì)于集合B?M,記

BI={g∈G|(g,m)∈I,?m∈B}

(2)

定義3[10].設(shè)形式背景K=(G,M,I),A?G,B?M,稱X=(A,B)為K的一個(gè)形式概念,如果AI=B且BI=A,此時(shí),稱A為X的外延,B為X的內(nèi)涵,用B(K)表示K的所有概念組成的集合.

定義4[10].設(shè)形式背景K=(G,M,I),X1=(A1,B1),X2=(A2,B2)是K的兩個(gè)概念,規(guī)定:

X1°X?A1?A2(?B1?B2)

(3)

顯然,關(guān)系“°”是集合B(K)上的一個(gè)偏序,它可誘導(dǎo)出B(K)上的一個(gè)格結(jié)構(gòu),可以證明,它是一個(gè)完備格,并且此完備格稱為形式背景K的概念格[11],在沒(méi)有歧義的情況下,仍然記為B(K).

2.2 形式概念的計(jì)算方法

形式概念的計(jì)算是形式概念分析的理論基礎(chǔ),目前關(guān)于形式概念的計(jì)算方法主要有兩種形式:批處理算法[12]和漸進(jìn)式算法[13-16].其中漸進(jìn)式方法效率較高,已被廣泛使用.

下面通過(guò)定義6和定義7來(lái)描述漸進(jìn)式算法計(jì)主要思想.

定義6.給定形式概念集B(K),對(duì)于B(K)中的任意概念(A,B),待插入的屬性為m,若滿足A∩mI=A,則稱(A,B)是一個(gè)需要更新的概念,且更新后的概念是(A,B∪m).

定義7.給定一個(gè)形式概念集B(K),對(duì)于B(K)中的任意概念(A,B),待插入的屬性為m,若滿足A∩mI≠A且A∩mI?A,則稱(A,B)將產(chǎn)生一個(gè)子概念,若存在B(K)中除(A,B)外其它概念(A′,B′)使A′==A∩mI,則生成的子概念是(A∩mI,B∪m),若不存在B(K)中除(A,B)外其它的概念(A′,B′)使得A′ ≠A∩mI,則生成的子概念是(A′,B′∪m).

例1.基于表2中的形式背景K,由文獻(xiàn)[6]可計(jì)算出形式概念集合:

B(K)={({s1,s3},{a,b}),({s1,s2,s3,s4},),({s2,s4},{b,c}),({s2,s4,s5},{c}),({},{a,b,c}),({s1,s2,s3,s4,s5},{})}.

3 屬性分類的多層次形式概念分析

從粒計(jì)算的角度,現(xiàn)有的形式概念分析所研究的屬性大多是基于單粒度和單層次的,忽視了在實(shí)際應(yīng)用中,屬性具有多粒度和多層次的結(jié)構(gòu).根據(jù)實(shí)際問(wèn)題的求解需要,將粗粒度屬性細(xì)化為兩個(gè)或多個(gè)細(xì)粒度屬性,可以提高問(wèn)題分析的精度,將兩個(gè)或多個(gè)細(xì)粒度屬性泛化為粗粒度屬性,可以提高問(wèn)題分析的效率.為此,本節(jié)基于屬性粒度的細(xì)化與泛化,給出基于屬性分類的多層次形式概念分析.

3.1 屬性分類泛化與細(xì)化形式概念計(jì)算

在實(shí)際應(yīng)用中,很多屬性具有多粒度的性質(zhì).例如屬性“教育背景”可以細(xì)化為屬性“學(xué)歷”、“學(xué)位”、“畢業(yè)院?！?反之屬性“學(xué)歷”、“學(xué)位”、“畢業(yè)院校”也可以泛化為屬性“教育背景”.不同粒度層次的選擇會(huì)影響形式概念分析的精度或效率.

如何確定哪些屬性需要細(xì)化或泛化,可由相關(guān)領(lǐng)域?qū)＜姨峁?也可根據(jù)訓(xùn)練集自動(dòng)構(gòu)建而成.下面給出形式概念分析中,基于屬性分類的細(xì)化與泛化相關(guān)定義和性質(zhì).

首先定義兩個(gè)算子“∧”和“∨”,分別稱為屬性細(xì)化算子和屬性泛化算子.

定義8.給定一個(gè)K=(G,M,I),G={g1,g2,…,gn}是非空有限對(duì)象集,M={m1,m2,…,mr}是非空有限屬性集,若屬性mi∈M,可以細(xì)化為屬性集P={mi1,mi2,…,mip},p≥2,則∧mi={mi1,mi2,…,mip},記細(xì)化之后的形式背景為∧K=(G,∧M,∧I).∧M=(M-{mi})∪P.∧I和I之間通常具有下述兩種約束關(guān)系:

1)?g∈G,若(g,mi)∈I,則?mis∈P,滿足(g,mis)∈∧I.

2)?g∈G,若(g,mi)∈I,則?mis∈P,滿足(g,mis)∈∧I.

在實(shí)際應(yīng)用中,∧I和I之間的約束關(guān)系,可根據(jù)實(shí)際應(yīng)用的需要靈活選擇,本文采用約束關(guān)系(1).

定義9.形式背景K=(G,M,I),經(jīng)屬性mi(mi∈M)細(xì)化得到形式背景∧K,∧mi={mi1,mi2,…,mip},p≥2,則?(A,B)∈B(K),若mi?B,則(A,B)∈B(∧K);若mi∈B,則(A,B)在B(∧K)中表示為概念

下面給出一些性質(zhì)說(shuō)明K和∧K的關(guān)系.

性質(zhì)1.給定形式背景K,若由屬性進(jìn)行細(xì)化操作“∧”,得到一個(gè)新的形式背景∧K,則基于∧K可以得到更細(xì)粒度的形式概念.

證明:由定義9易知性質(zhì)1成立.

性質(zhì)2.給定形式背景K,若由屬性進(jìn)行細(xì)化操作“∧”,得到一個(gè)新的形式背景∧K,則|B(K)|≤|B(∧K)|,其中|B(K)|表示形式概念B(K)的基數(shù).

證明:因?yàn)閷傩约?xì)化,屬性個(gè)數(shù)增加,對(duì)應(yīng)的形式概念個(gè)數(shù)也增加,所以細(xì)化后的形式背景得到的形式概念數(shù)量要多于細(xì)化前的形式背景得到的形式概念數(shù)量.

定義10.給定形式背景K=(G,M,I),G={g1,g2,…,gn}是非空有限對(duì)象集,M={m1,m2,…,mr}是非空有限屬性集,設(shè)屬性集Q={mi1,mi2,…,miq},q≥2,Q?M.若Q中的屬性可以泛化一個(gè)屬性mq,則∨{mi1,mi2,…,miq}=mq,記泛化后的形式背景為∨K=(G,∨M,∨I),∨M=(M-Q)∪mq.∨I和I之間通常具有下述兩種約束關(guān)系:

1)?g∈G,若?mis∈Q,滿足(g,mis)∈I,則(g,mq)∈∨I.

2)?g∈G,若?mis∈Q,滿足(g,mis)∈I,則(g,mq)∈∨I.

在實(shí)際應(yīng)用中,∨I和I之間的約束關(guān)系,可根據(jù)實(shí)際應(yīng)用的需要靈活選擇,本文采用約束關(guān)系(1).

定義11.形式背景K=(G,M,I),經(jīng)屬性集Q={mi1,mi2,…,miq},q≥2,Q?M,泛化為屬性mq得到形式背景∨K,則?(A,B)∈B(K),若B∩Q=?,則(A,B)∈B(∨K);若B∩Q≠?,則(A,B)在B(∨K)中表示為概念(((B-(B∩Q))∪mq)I,((B-(B∩Q))∪mq)).

下面給出一些性質(zhì)說(shuō)明K和∨K的關(guān)系.

性質(zhì)3.給定形式背景K,若由屬性進(jìn)行細(xì)化操作“∨”,得到一個(gè)新的形式背景∨K,則基于∨K可以得到更粗粒度的形式概念.

證明:由定義11易知性質(zhì)3成立.

性質(zhì)4.給定形式背景K,若由屬性進(jìn)行泛化操作“∨”,得到一個(gè)新的形式背景∨K,則|B(∨K)|≤|B(K)|,其中|B(K)|表示形式概念B(K)的基數(shù).

證明:因?yàn)閷傩苑夯?引起屬性個(gè)數(shù)減少,使得對(duì)應(yīng)的形式概念個(gè)數(shù)也減少,所以泛化后的形式背景得到的形式概念數(shù)量要小于細(xì)化前的形式背景得到的形式概念數(shù)量.

下面通過(guò)例子說(shuō)明形式概念分析中,屬性細(xì)化和屬性泛化的方法.

例2.基于表2給出的形式背景K,如果把屬性b特長(zhǎng)細(xì)化為唱歌特長(zhǎng)b1和體育特長(zhǎng)b2,則可以得到新的形式背景K1如表3所示.

表3 屬性細(xì)化后的形式背景
Table 3 Formal context of attribute refinement

Gab1b2cs11010s20011s31100s40101s50001

對(duì)于表3的形式背景,由文獻(xiàn)[6]可計(jì)算出形式概念:B(K1)={({s1,s2},{b2}),({s1,s3},{a}),({s3,s4},{b1}),({s2,s4,s5},{c}),({s1},{a,b2}),({s2},{b2,c}),({s3},{a,b1}),({s4},{b1,c}),({s1,s2,s3,s4,s5},{}),({},{a,b1,b2,c})}.

通過(guò)比較B(K1)和B(K)中的形式概念集合,可見(jiàn)屬性細(xì)化后,可以得到更細(xì)的概念集合,從而提高問(wèn)題分析的精度.反之,如果初始給定的形式背景K如表3所示,為了提高問(wèn)題分析的效率,可以將屬性唱歌特長(zhǎng)b1和體育特長(zhǎng)b2泛化為屬性b特長(zhǎng),則得到新的形式背景∨K如表2所示.屬性泛化后,可以得到更粗的形式概念.由文獻(xiàn)[17]知,屬性個(gè)數(shù)減少,構(gòu)造形式概念時(shí)間減少,從而提高問(wèn)題分析的效率.

注:屬性細(xì)化和屬性泛化的結(jié)果并不是唯一的,只需滿足定義8或定義10中的約束關(guān)系即可.

3.2 屬性分類的多層次形式概念動(dòng)態(tài)構(gòu)造算法

給定一個(gè)形式背景,當(dāng)由于屬性細(xì)化或泛化產(chǎn)生新的形式背景時(shí),將有兩種方式計(jì)算新的形式背景下的形式概念.第一種是完全基于新的形式背景重新計(jì)算所有的形式概念(即傳統(tǒng)的漸進(jìn)式構(gòu)造算法[17]),該方法沒(méi)有利用已有形式概念進(jìn)行計(jì)算,對(duì)更新后的數(shù)據(jù)進(jìn)行重新計(jì)算,相對(duì)而言,計(jì)算效率較低.另一種方法是結(jié)合原形式背景的形式概念,只針對(duì)細(xì)化或泛化的屬性進(jìn)行計(jì)算,減少了計(jì)算時(shí)間,即動(dòng)態(tài)計(jì)算形式概念.

本節(jié)給出當(dāng)屬性細(xì)化或泛化產(chǎn)生新的形式背景時(shí),動(dòng)態(tài)構(gòu)造形式概念算法.

算法1.形式概念動(dòng)態(tài)構(gòu)造算法

Input:形式概念集B(K),待細(xì)化(泛化)的屬性集M1={b1,b2,…,bm},細(xì)化(泛化)后的屬性集M2={m1,m2,…,mn},經(jīng)屬性細(xì)化(屬性泛化)后的形式背景K′=(G,M′,I′).

Output:屬性細(xì)化(屬性泛化)后的形式概念集B(K′).

Step1.定義臨時(shí)的形式概念集B(K*)=?.

Step2.Foreach(A,B)∈B(K)

B′=B∩M1;

IfB′≠?

B(K)=B(K)-(A,B);//去除概念(A,B)

If(B-B′)≠?

B(K*)=B(K*)∪(A,B-B′);//添加(A,B-B′)

Endforeach

Step3.Foreach(A′,B′)∈B(K*)

If?(A,B)∈B(K),滿足B≠B′

B(K)=B(K)∪(A′,B′);

Endforeach

Step4.Foreachmj∈M2

Foreach(A,B)∈B(K)

ElseifA?mI

B(K)=(B(K)-(A,B))∪(A,B∪m);

Elseif?(A′,B′)∈B(K)&&(A′,B′)≠

B(K)=B(K)∪(A′,B′∪m);

Endforeach

Endforeach

Step5.將B(K′)=B(K)&&

B(K′)=B(K′)-({},B-M1)+({},B-M1+M2)

輸出B(K′).

假設(shè)形式背景中有l(wèi)個(gè)對(duì)象,n個(gè)屬性,通過(guò)文獻(xiàn)[17]漸進(jìn)式生成概念的算法構(gòu)造的形式概念個(gè)數(shù)為N(N<=2n-1-1),若將k1(k1

注:引入臨時(shí)的形式概念集B(K*)的目的是為了減少遍歷次數(shù),提高計(jì)算效率.

例3.給定細(xì)化前的形式背景K如表2所示.經(jīng)屬性細(xì)化得到的形式背景K1如表3所示.按照算法1的步驟給出屬性細(xì)化時(shí),形式概念動(dòng)態(tài)構(gòu)造算法的詳細(xì)計(jì)算過(guò)程如下所示.

Input:經(jīng)屬性細(xì)化得到的形式背景K1如表3所示.由形式

背景K得到的形式概念B(K)={({s1,s3},{a,b}),({s1,s2,s3,s4},),({s2,s4},{b,c}),({s2,s4,s5},{c}),({},{a,b,c}),({s1,s2,s3,s4,s5},{})},待細(xì)化的屬性集M1=,細(xì)化后的屬性集M2={b1,b2}.

Output:最終的形式概念B(K′).

Step1.定義臨時(shí)的形式概念B(K*)=?.

Step2.依次取B(K)中的概念進(jìn)行處理:

①.概念({s1,s3},{a,b})

處理結(jié)果是:B(K*)添加({s1,s3},{a}),B(K)刪除({s1,s3},{a,b}).

②.概念({s1,s2,s3,s4},)

處理結(jié)果是:B(K)刪除({s1,s2,s3,s4},).

③.概念({s2,s4},{b,c})

處理結(jié)果是:B(K*)添加({s2,s4},{c}),B(K)刪除({s2,s4},{b,c}).

④.概念({s2,s4,s5},{c})

處理結(jié)果是:不變.

⑤.概念({},{a,b,c})

處理結(jié)果是:B(K*)添加({},{a,c}),B(K)刪除({},{a,b,c}).

⑥.概念({s1,s2,s3,s4,s5},{})

處理結(jié)果是:不變.

此時(shí)B(K*),B(K)的結(jié)果是:

B(K)={({s2,s4,s5},{c}),({s1,s2,s3,s4,s5},{})}.

B(K*)={({s1,s3},{a}),({s2,s4},{}),({},{a,c})}.

Step3.依次取B(K*)中的概念進(jìn)行處理:

①.概念({s1,s3},{a})

處理結(jié)果是:B(K)添加({s1,s3},{a}).

②.概念({s2,s4},{c})

處理結(jié)果是:不變.

③.概念({},{a,c})

處理結(jié)果是:B(K)添加({},{a,c}).

此時(shí):B(K)={({s2,s4,s5},{c}),({s1,s2,s3,s4,s5},{}), ({s1,s3},{a}),({},{a,c})}.

Step4.依次取M2={b1,b2}中的屬性進(jìn)行處理:

處理結(jié)果是:B(K)={({s2,s4,s5},{c}),({s1,s2,s3,s4,s5},{}),({s1,s3},{a}), ({s4},{c,b1}),({s3},{a,b1}),({},{a,c}),({s3,s4},{b1})}.

處理結(jié)果是:B(K)={({s2,s4,s5},{c}),({s1,s2,s3,s4,s5},{}),({s1,s3},{a}),({s4},{c,b1}),({s3},{a,b1}),({},{a,c}),({s3,s4},{b1}),({s1,s2},

{b2}),({s1},{a,b2}),({s2},{b2,c}).

Step5.將B(K)賦值給B(K′)并修正B(K′),輸出B(K′).

B(K′)={({s2,s4,s5},{c}),({s1,s2,s3,s4,s5},{}),({s1,s3},{a}),({s4},{c,b1}),({s3},{a,b1}),({s3,s4},{b1}),({s1,s2},{b2}),({s1},{a,b2}),({s2},{b2,c}),({},{a,b1,b2,c}).

4 仿真實(shí)驗(yàn)

本節(jié)通過(guò)仿真實(shí)驗(yàn),對(duì)比分析,當(dāng)屬性細(xì)化或泛化時(shí),原有的形式背景自身數(shù)據(jù)發(fā)生變化.靜態(tài)的形式概念構(gòu)造算法(即傳統(tǒng)的漸進(jìn)式算法[17])和動(dòng)態(tài)的形式概念構(gòu)造算法的運(yùn)行時(shí)間對(duì)比.通過(guò)實(shí)驗(yàn)驗(yàn)證了本文所提算法的有效性.

由于形式概念計(jì)算中數(shù)據(jù)值較單一,且現(xiàn)有的形式概念算法的研究多以人工生成方式做為實(shí)驗(yàn)數(shù)據(jù).本章的仿真實(shí)驗(yàn)數(shù)據(jù)生成如下:首先指定形式背景的對(duì)象個(gè)數(shù)、屬性個(gè)數(shù)以及對(duì)象屬性關(guān)聯(lián)的概率(指屬性值非0個(gè)數(shù)的比率),然后由程序自動(dòng)生成實(shí)驗(yàn)數(shù)據(jù).例如,假定對(duì)象個(gè)數(shù)為100,屬性個(gè)數(shù)為10,對(duì)象屬性關(guān)聯(lián)概率是30%,表示數(shù)據(jù)集中非0的屬性值個(gè)數(shù)有300個(gè).而本實(shí)驗(yàn)中將設(shè)定對(duì)象的個(gè)數(shù)為200,屬性的個(gè)數(shù)為50,對(duì)象屬性關(guān)聯(lián)概率選擇33%,從而生成一個(gè)形式背景,用K′表示,并對(duì)形式背景K′進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)平臺(tái)為:windows7操作系統(tǒng)、Intel(R)Core(TM)i3CPU3.20GHz、2G內(nèi)存的微機(jī).在Eclipse中用Java語(yǔ)言編程實(shí)現(xiàn).

針對(duì)形式背景K′,通過(guò)屬性細(xì)化和屬性泛化方法,分別進(jìn)行實(shí)驗(yàn).對(duì)于屬性細(xì)化的情況,考慮單個(gè)屬性細(xì)化和多個(gè)(組)屬性細(xì)化兩種情況.所謂單個(gè)屬性細(xì)化是指,每次只考慮將一個(gè)屬性細(xì)化為若干個(gè)屬性, 考慮到實(shí)際情況和實(shí)驗(yàn)研究的意義,單個(gè)屬性細(xì)化最多設(shè)為10個(gè).實(shí)驗(yàn)中分別設(shè)置將一個(gè)屬性細(xì)化為2個(gè)屬性、3個(gè)屬性、….、10個(gè)屬性,對(duì)形式背景K′分別進(jìn)行單個(gè)屬性細(xì)化實(shí)驗(yàn),結(jié)果如圖1所示.其中橫軸表示單個(gè)屬性細(xì)化后的屬性個(gè)數(shù),縱軸表示運(yùn)行時(shí)間(單位為毫秒).所謂多個(gè)屬性細(xì)化是指,每次考慮將多個(gè)屬性同時(shí)細(xì)化為若干個(gè)屬性,如同時(shí)將兩組屬性進(jìn)行細(xì)化、同時(shí)將三組屬性進(jìn)行細(xì)化,考慮到實(shí)際情況和實(shí)驗(yàn)研究的意義,多個(gè)屬性細(xì)化最多設(shè)為20組.實(shí)驗(yàn)中分別設(shè)置同時(shí)細(xì)化的屬性組數(shù)為2組、4組、6組、…、20組.為了簡(jiǎn)化操作,對(duì)于多個(gè)屬性細(xì)化,我們僅考慮將每組屬性細(xì)化為兩個(gè)屬性的情況,即若同時(shí)將16組屬性進(jìn)行細(xì)化,那么原有的形式背景中的16個(gè)屬性將變成32個(gè)新的屬性,對(duì)形式背景K′分別進(jìn)行多個(gè)屬性細(xì)化實(shí)驗(yàn),結(jié)果如圖2所示.其中橫軸表示同時(shí)細(xì)化的屬性個(gè)數(shù),縱軸表示運(yùn)行時(shí)間(單位為毫秒).針對(duì)屬性泛化的情況,考慮單組屬性泛化和多組屬性泛化兩種情況.所謂單組屬性泛化是指,每次只考慮將若干個(gè)屬性泛化為一個(gè)屬性,考慮到實(shí)際情況和實(shí)驗(yàn)研究的意義,單個(gè)屬性泛化最多設(shè)為10個(gè).實(shí)驗(yàn)中分別設(shè)置泛化的屬性個(gè)數(shù)為2個(gè)、3個(gè)、…、10個(gè),對(duì)形式背景K′分別進(jìn)行單個(gè)屬性泛化實(shí)驗(yàn),結(jié)果如圖3所示.其中橫軸表示泛化的屬性個(gè)數(shù),縱軸表示運(yùn)行時(shí)間(單位為毫秒).所謂多組屬性泛化是指,每次考慮將多組屬性分別泛化為若干個(gè)屬性,如同時(shí)將兩組屬性分別泛化為兩個(gè)屬性,同時(shí)將三組屬性分別泛化為兩個(gè)屬性,考慮到實(shí)際情況和實(shí)驗(yàn)研究的意義,多個(gè)屬性泛化最多設(shè)為20組.實(shí)驗(yàn)中設(shè)置同時(shí)泛化的屬性的組數(shù)為2組、4組、6組、…、20組.為了簡(jiǎn)化操作,對(duì)于多組屬性泛化,我們僅考慮將兩個(gè)屬性泛化為一個(gè)屬性的情況,即若同時(shí)將16組屬性進(jìn)行泛化,那么原有的形式背景中這16個(gè)屬性將變成8個(gè)新的屬性,對(duì)形式背景K′分別進(jìn)行多個(gè)屬性泛化實(shí)驗(yàn),結(jié)果如圖4所示.其中橫軸表示屬性泛化的組數(shù),縱軸表示運(yùn)行時(shí)間(單位為毫秒).

圖1 單個(gè)屬性細(xì)化實(shí)驗(yàn)比較Fig.1 Comparison of single attribute refinement experiments

圖2 多組屬性細(xì)化實(shí)驗(yàn)比較Fig.2 Experimental comparison of multiple attribute refinement

從圖1中可以看出,對(duì)于“單個(gè)屬性細(xì)化”,動(dòng)態(tài)的形式概念構(gòu)造算法花費(fèi)的時(shí)間明顯少于靜態(tài)的形式概念構(gòu)造算法.關(guān)于靜態(tài)的形式概念構(gòu)造算法和動(dòng)態(tài)的形式概念構(gòu)造算法的運(yùn)行時(shí)間,隨著細(xì)化后子屬性個(gè)數(shù)的增加,兩者都是呈現(xiàn)單調(diào)上升的趨勢(shì).這是因?yàn)閷傩约?xì)化后,屬性個(gè)數(shù)增加導(dǎo)致運(yùn)行時(shí)間增加.

從圖2中可以看出,對(duì)于 “多組屬性細(xì)化”,動(dòng)態(tài)的形式概念構(gòu)造算法花費(fèi)的時(shí)間明顯少于靜態(tài)的形式概念構(gòu)造算法.關(guān)于靜態(tài)的形式概念構(gòu)造算法和動(dòng)態(tài)的形式概念構(gòu)造算法的運(yùn)行時(shí)間,隨著細(xì)化后子屬性組數(shù)的增加,兩種呈現(xiàn)出先上升后下降的趨勢(shì).原因是:雖然屬性細(xì)化后,屬性個(gè)數(shù)增加導(dǎo)致運(yùn)行時(shí)間增加,但是細(xì)化后的每個(gè)屬性中對(duì)象特征(屬性)關(guān)聯(lián)概率降低(按照定義8中的約束(1)),運(yùn)行時(shí)間減少,在這兩者的相互作用下,反而呈現(xiàn)下降的趨勢(shì),圖1中呈現(xiàn)單調(diào)上升,是由于對(duì)象特征關(guān)聯(lián)概率降低對(duì)單個(gè)屬性細(xì)化影響較小.

圖3 單個(gè)屬性泛化實(shí)驗(yàn)比較Fig.3 Comparison of single attribute generalization

從圖3中可以看出,對(duì)于“單個(gè)屬性泛化”,動(dòng)態(tài)的形式概念構(gòu)造算法花費(fèi)的時(shí)間都明顯少于靜態(tài)的形式概念構(gòu)造算法.需要注意的是圖3中,靜態(tài)的形式概念構(gòu)造算法和動(dòng)態(tài)的形式概念構(gòu)造算法的運(yùn)行時(shí)間,隨著泛化后屬性個(gè)數(shù)的減少,兩者呈現(xiàn)單調(diào)下降的趨勢(shì).這是因?yàn)閷傩苑夯?屬性個(gè)數(shù)減少會(huì)導(dǎo)致運(yùn)行時(shí)間減少.

圖4 多組屬性泛化的實(shí)驗(yàn)比較Fig.4 Experimental comparison of multiple attribute generalization

從圖4中可以看出,對(duì)于“多組屬性泛化”,動(dòng)態(tài)的形式概念構(gòu)造算法花費(fèi)的時(shí)間都明顯少于靜態(tài)的形式概念構(gòu)造算法.關(guān)于靜態(tài)的形式概念構(gòu)造算法和動(dòng)態(tài)的形式概念構(gòu)造算法的運(yùn)行時(shí)間,隨著泛化后屬性個(gè)數(shù)的減少,兩者呈現(xiàn)出先上升后下降的趨勢(shì),這是因?yàn)殡m然屬性泛化后,屬性個(gè)數(shù)減少會(huì)導(dǎo)致運(yùn)行時(shí)間減少,但是泛化后的每個(gè)屬性中對(duì)象特征(屬性)關(guān)聯(lián)概率增大(按照定義10中的約束(1)),運(yùn)行時(shí)間增加,在這兩者的相互作用下,沒(méi)有呈現(xiàn)出嚴(yán)格的單調(diào)下降.而圖3中呈現(xiàn)單調(diào)下降,是由于對(duì)象特征關(guān)聯(lián)概率增加對(duì)單個(gè)屬性泛化影響較小.

通過(guò)以上實(shí)驗(yàn)證明了本文提出的基于屬性分類多層次的形式概念動(dòng)態(tài)構(gòu)造算法的有效性.因?yàn)殪o態(tài)的形式概念構(gòu)造算法總是將所有的數(shù)據(jù)重新計(jì)算,而動(dòng)態(tài)的形式概念構(gòu)造算法是利用原有的形式概念數(shù)據(jù)基礎(chǔ)上對(duì)自身變化的數(shù)據(jù)進(jìn)行動(dòng)態(tài)的更新,所以動(dòng)態(tài)的形式概念構(gòu)造算法處理的數(shù)據(jù)較少.因此,基于屬性分類(屬性細(xì)化和屬性泛化)變化的形式概念,動(dòng)態(tài)的形式概念構(gòu)造算法更有效.

5 結(jié) 論

從粒計(jì)算的角度分析,現(xiàn)有的形式概念分析所研究的屬性大多是單粒度單層次的,忽視了在實(shí)際應(yīng)用中,屬性具有不同的粒度層次,基于形式背景構(gòu)造形式概念時(shí),根據(jù)實(shí)際問(wèn)題的求解需要,將粗粒度屬性細(xì)化為兩個(gè)或多個(gè)細(xì)粒度屬性,可以提高問(wèn)題分析的精度,將兩個(gè)或多個(gè)細(xì)粒度屬性泛化為粗粒度屬性,可以提高問(wèn)題分析的效率.所以,本文給出了屬性分類的屬性泛化與細(xì)化方法,實(shí)現(xiàn)了形式概念在不同層次泛化空間下相關(guān)性質(zhì).在此基礎(chǔ)上,提出了屬性分類的多層次形式概念動(dòng)態(tài)構(gòu)造算法,該算法通過(guò)自學(xué)習(xí)的方式對(duì)原有的知識(shí)加以使用,它不僅繼承了漸進(jìn)式算法的優(yōu)點(diǎn),還實(shí)現(xiàn)了形式概念自身數(shù)據(jù)的變化.

[1] Wille R.Concept lattices and conceptual knowledge systems[J].Computers & Mathematics with Applications,1992,23(6-9):493-515.

[2] Ignatov D I,Gnatyshak D V,Kuznetsov S O,et al.Triadic formal concept analysis and triclustering:searching for optimal patterns[J].Machine Learning,2015,101(1-3):271-302.

[3] Codocedo V,Lykourentzou I,Napoli A.A semantic approach to concept lattice-based information retrieval[J].Annals of Mathematics & Artificial Intelligence,2014,72(1-2):169-195.

[4] Sridhar M,Gill NS.A formal conceptual framework for dynamics within context of component-based system for designing robust software systems & metrics[J].International Journal of Software Engineering & Applications,2015,6(2):21-31.

[5] Yao J,Vasilakos A V,Pedrycz W.Granular computing:perspectives and challenges[J].Cybernetics IEEE Transactions on,2013,43(6):1977-1989.

[6] Li J,Mei C,Xu W,et al.Concept learning via granular computing:a cognitive viewpoint[J].Information Sciences,2015,298(1):447-467.

[7] Qu Kai-she,Zhai Yan-hui,Liang Ji-ye,et al.Representation and extension of rough set theory based on formal concept analysis[J].Journal of Software,2007,18(9):2174-2182.

[8] Zhang Lei,Zhang Hong-li,Yin Li-hua,et al.Theory and algorithms of attribute decrement for concept lattice[J].Journal of Computer Research & Development,2013,50(2):248-259.

[9] Qian Y H,Zhang H,Sang Y L,et al.Multigranulation decision-theoretic rough sets[J].Int J of Approximate Reasoning,2014,55(1):225-237.

[10] Ganter B,Wille R.Formal concept analysis:mathematic foundations[M].Berlin:Springer-Verlag,1999:17-58.

[11] Singh P K,Kumar C A,Li J.Knowledge representation using interval-valued fuzzy formal concept lattice[J].Soft Computing,2016,20(4):1485-1502.

[12] Wang Xing-xing,Zhang Ji-fu,Zhang Su-lan.A batch constructing algorithm of frequent weighted concept lattice[J].Pattern Recognition and Artificial Intelligence,2010,23(5):678-685.

[13] Li-Ping Q U.Attribute-based fast incremental algorithm for building relative reduced concept lattice[J].Computer Science,2008,35(4):135-138.

[14] Zhi Hui-lai,Zhi Dong-jie.Theory and algorithm of concept lattice incremental construction based on attributes[J].Computer Engineering and Applications,2012,48(26):17-21.

[15] Zou L,Zhang Z,Long J,et al.A fast incremental algorithm for deleting objects from a concept lattice[J].Knowledge-Based Systems,2015,89(C):411-419.

[16] Liu Zong-tian,Qiang Yu,Zhou Wen,et al.A fuzzy concept lattice model and its incremental construction algorithm[J].Chinese Journal of Computers,2007,30(2):184-188.

[17] Zou L,Zhang Z,Long J.A fast incremental algorithm for constructing concept lattices[J].Expert Systems with Applications,2015,42(9):4474-4481.

附中文參考文獻(xiàn)：

[7] 曲開(kāi)社,翟巖慧,梁吉業(yè),等.形式概念分析對(duì)粗糙集理論的表示及擴(kuò)展[J].軟件學(xué)報(bào),2007,18(9):2174-2182.

[8] 張 磊,張宏莉,殷麗華,等.概念格的屬性漸減原理與算法研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50(2):248-259.

[12] 王欣欣,張繼福,張素蘭.一種頻繁加權(quán)概念格的批處理構(gòu)造算法[J].模式識(shí)別與人工智能,2010,23(5):678-685.

[14] 智慧來(lái),智東杰.基于屬性的概念格漸進(jìn)式構(gòu)造原理與算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(26):17-21.

[16] 劉宗田,強(qiáng) 宇,周 文,等.一種模糊概念格模型及其漸進(jìn)式構(gòu)造算法[J].計(jì)算機(jī)學(xué)報(bào),2007,30(2):184-188.