屬性分類的多層次形式概念模型及動態(tài)算法研究

徐 怡,霍思林

1(安徽大學 計算智能與信號處理教育部重點實驗室,合肥 230039) 2(安徽大學 計算機科學與技術(shù)學院,合肥 230601)

1 引 言

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

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

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

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

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

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

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

表1 問題背景
Table 1 Problem background

學生成績特長語言表達S1優(yōu)秀唱歌不合格S2不優(yōu)秀體育合格S3優(yōu)秀體育不合格S4不優(yōu)秀唱歌合格S5不優(yōu)秀無合格

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

表2 形式背景
Table 2 Formal context

GabcS1110S2011S3110S4011S5001

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

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

(1)

相應(yīng)地,對于集合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的一個形式概念,如果AI=B且BI=A,此時,稱A為X的外延,B為X的內(nèi)涵,用B(K)表示K的所有概念組成的集合.

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

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

(3)

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

2.2 形式概念的計算方法

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

下面通過定義6和定義7來描述漸進式算法計主要思想.

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

定義7.給定一個形式概念集B(K),對于B(K)中的任意概念(A,B),待插入的屬性為m,若滿足A∩mI≠A且A∩mI?A,則稱(A,B)將產(chǎn)生一個子概念,若存在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,由文獻[6]可計算出形式概念集合:

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 屬性分類的多層次形式概念分析

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

3.1 屬性分類泛化與細化形式概念計算

在實際應(yīng)用中,很多屬性具有多粒度的性質(zhì).例如屬性“教育背景”可以細化為屬性“學歷”、“學位”、“畢業(yè)院?！?反之屬性“學歷”、“學位”、“畢業(yè)院?！币部梢苑夯癁閷傩浴敖逃尘啊?不同粒度層次的選擇會影響形式概念分析的精度或效率.

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

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

定義8.給定一個K=(G,M,I),G={g1,g2,…,gn}是非空有限對象集,M={m1,m2,…,mr}是非空有限屬性集,若屬性mi∈M,可以細化為屬性集P={mi1,mi2,…,mip},p≥2,則∧mi={mi1,mi2,…,mip},記細化之后的形式背景為∧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.

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

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

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

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

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

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

證明:因為屬性細化,屬性個數(shù)增加,對應(yīng)的形式概念個數(shù)也增加,所以細化后的形式背景得到的形式概念數(shù)量要多于細化前的形式背景得到的形式概念數(shù)量.

定義10.給定形式背景K=(G,M,I),G={g1,g2,…,gn}是非空有限對象集,M={m1,m2,…,mr}是非空有限屬性集,設(shè)屬性集Q={mi1,mi2,…,miq},q≥2,Q?M.若Q中的屬性可以泛化一個屬性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.

在實際應(yīng)用中,∨I和I之間的約束關(guān)系,可根據(jù)實際應(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ì)說明K和∨K的關(guān)系.

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

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

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

證明:因為屬性泛化,引起屬性個數(shù)減少,使得對應(yīng)的形式概念個數(shù)也減少,所以泛化后的形式背景得到的形式概念數(shù)量要小于細化前的形式背景得到的形式概念數(shù)量.

下面通過例子說明形式概念分析中,屬性細化和屬性泛化的方法.

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

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

Gab1b2cs11010s20011s31100s40101s50001

對于表3的形式背景,由文獻[6]可計算出形式概念: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})}.

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

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

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

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

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

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

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

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

Step1.定義臨時的形式概念集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)個對象,n個屬性,通過文獻[17]漸進式生成概念的算法構(gòu)造的形式概念個數(shù)為N(N<=2n-1-1),若將k1(k1

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

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

Input:經(jīng)屬性細化得到的形式背景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},{})},待細化的屬性集M1=,細化后的屬性集M2={b1,b2}.

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

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

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

①.概念({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é)果是:不變.

此時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*)中的概念進行處理:

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

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

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

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

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

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

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

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

處理結(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 仿真實驗

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

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

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

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

圖1 單個屬性細化實驗比較Fig.1 Comparison of single attribute refinement experiments

圖2 多組屬性細化實驗比較Fig.2 Experimental comparison of multiple attribute refinement

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

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

圖3 單個屬性泛化實驗比較Fig.3 Comparison of single attribute generalization

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

圖4 多組屬性泛化的實驗比較Fig.4 Experimental comparison of multiple attribute generalization

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

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

5 結(jié) 論

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

附中文參考文獻：

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

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

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

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

[16] 劉宗田,強 宇,周 文,等.一種模糊概念格模型及其漸進式構(gòu)造算法[J].計算機學報,2007,30(2):184-188.