三支面向?qū)傩愿拍罡竦臉?gòu)成

蘇 新，夏文富，陳永平

(1.馬鞍山職業(yè)技術(shù)學(xué)院電子信息系，安徽馬鞍山 243011；2.杭州市地鐵集團有限責(zé)任公司運營分公司，浙江杭州 310000)

形式概念是由德國數(shù)學(xué)家Gante 等于1982 年提出的，其主要思想是通過概念之間的泛化和例化關(guān)系，揭示數(shù)據(jù)之間的內(nèi)部關(guān)系和對象及屬性之間的關(guān)系。目前，形式概念分析已在數(shù)據(jù)挖掘、專家系統(tǒng)、軟件工程等領(lǐng)域得到廣泛應(yīng)用。傳統(tǒng)的形式概念分析理論研究的是對象(屬性)共同具有的屬性(對象)，或是對象(屬性)共同不具有的屬性(對象)。反映在實際應(yīng)用中，就是針對某一觀點，要么接受，要么拒絕，這與某些實際應(yīng)用不相符。因此，Yao提出三支決策理論，基于接受和拒絕外，增加了一種延遲決策方法。Qi等將三支決策理論和形式概念分析理論相結(jié)合，提出了三支概念分析理論。三支概念格理論包括由對象誘導(dǎo)的三支概念格(OE-概念格)和由屬性誘導(dǎo)的三支概念格(AE-概念格)。錢婷將面向?qū)ο?屬性)概念格理論和三支概念分析相結(jié)合，提出了三支面向?qū)ο?屬性)概念格。

關(guān)于三支概念格的構(gòu)造，由于三支概念的數(shù)量龐大，文獻[10]中在經(jīng)典概念格上定義一個等價映射，并求出每個等價類及其最大元素，在此基礎(chǔ)上給出三支概念格的構(gòu)造算法；文獻[11]中利用經(jīng)典概念格及其補背景的并置和疊置得到混合形式背景，以此生成OE-概念格和AE-概念格；文獻[12]中主要針對三支概念格構(gòu)造，定義候選三支概念和冗余三支概念，給出了在候選概念中滿足三支概念的條件，但沒有給出候選概念和三支概念格以及冗余概念和三支概念格之間的關(guān)系。目前，對于三支概念格生成方面的研究主要集中于OE-概念格和AE-概念格，對三支面向?qū)ο?屬性)概念格的生成算法關(guān)注較少；利用并置和疊置的方法分別生成三支面向?qū)ο蟾拍罡窈腿嫦驅(qū)傩愿拍罡?，但需生成一個比原形式背景大得多的新的形式背景，增加了三支概念格生成時復(fù)雜性。鑒于此，研究三支面向?qū)傩愿拍罡竦臉?gòu)造算法，基于時間復(fù)雜度的角度對其進行分析，以期提高算法效率。

1 預(yù)備知識

定義1設(shè)一個三元組

L

= (

G

,

M

,

I

)是一個形式背景，其中：

G

={

g

,

g

,…,

g

}，為一個對象集，

g

(

i

≤

n

)為一個對象；

M

= {

m

,

m

,

m

,…,

m

}，為屬性集，每個

m

(

j

≤

q

)為一個屬性；

I

為

G

和

M

之間的二元關(guān)系，即

I

?

G

×

M

。若(

g

,

m

) ∈

I

，則稱

g

具有屬性

m

，用1表示；若(

g

,

m

) ?

I

，則稱

g

不具有屬性

m

，用0表示。對于形式背景(

G

,

M

,

I

)，在對象集

X

?

G

和屬性集

Y

?

M

上定義*運算：

式中：

X

表示對象集

X

中所有對象共同具有的屬性集合；

Y

表示擁有屬性

Y

的對象集合；?

g

∈

G

,?

m

∈

M

。記{

g

}為

g

，{

m

}為

m

，稱形式背景(

G

,

M

,

I

)是正則的，對任意

g

∈

G

,

g

≠?,

g

≠

M

，且對任意

m

∈

M

,

m

≠?,

m

≠

G

。定義2設(shè)(

G

,

M

,

I

)為形式背景，若

X

=

Y

且

Y

=

X

，則稱(

X

,

Y

)是一概念，

X

為該概念的外延，

Y

為該概念的內(nèi)涵。對于任意概念(

X

,

Y

)，(

X

,

Y

)，定義偏序關(guān)系為(

X

,

Y

)≤(

X

,

Y

)?

X

?

X

?

Y

?

Y

，則形式背景(

G

,

M

,

I

)的所有概念在該偏序關(guān)系下是完備格，形式背景(

G

,

M

,

I

)的概念格記為Lattices(

G

，

M

，

I

)，簡寫為

L

(

G

,

M

,

I

)。

以上定義的算子是形式背景中的正算子。

定義3設(shè)(

G

,

M

,

I

)為形式背景，對于

X

?

G

,

Y

?

M

，一對負算子定義如下：

若

X

=

Y

且

Y

=

X

，則稱(

X

,

Y

)為負概念，形式背景(

G

,

M

,

I

)在負算子下生成的所有負概念的集合也稱為補概念集合，記為Negative Lattices(

G

,

M

,

I

)，簡寫為

L

(

G

,

M

,

I

)，在上述的偏序關(guān)系下

L

(

G

,

M

,

I

)也是完備格。根據(jù)形式背景(

G

,

M

,

I

)的補背景的定義，易得到形式背景(

G

,

M

,

I

)的負算子-*是其補背景(

G

,

M

,

I

)(

I

=

G

×

M

I

)的正算子，因此

L

(

G

，

M

，

I

)=

L

(

G

,

M

,

I

)。定義4對于形式背景(

G

,

M

,

I

)，引入一對近似算子，分別用□和?表示。對于?

X

?

G

及?

Y

?

M

，有

X

={

m

|?∈

M

,

m

?

X

},

X

={

m

|?

m

∈

M

,

m

?

X

≠?}；對應(yīng)的，對于?

Y

?

M

，有

Y

={

g

|?

g

∈

G

,

g

?

Y

},

Y

={

g

|?

g

∈

G

,

g

?

Y

≠?}。定義5設(shè)

K

=(

G

,

M

,

I

)為形式背景，如果?

X

?

G

,?

Y

?

M

，滿足

X

=

Y

,

Y

=

X

，則稱二元組(

X

，

Y

)為面向?qū)傩愿拍?。其中?p>X

為面向?qū)傩愿拍畹耐庋樱?p>Y

為面向?qū)傩愿拍畹膬?nèi)涵。由形式背景(

G

,

M

,

I

)產(chǎn)生的全體面向?qū)傩愿拍畹募戏Q為形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡?，記為Attribute Lattices(

G

,

M

,

I

)，簡寫為

L

(

G

，

M

，

I

)。設(shè)

K

=(

G

,

M

,

I

)為一形式背景，

L

(

K

)為一完備格，其中的偏序關(guān)系為(

X

,

Y

)≤(

X

,

Y

)?

X

?

X

(

Y

?

Y

)，在

L

(

G

,

M

,

I

)中的運算為：

L

(

G

,

M

,

I

)中的每個概念都是面向?qū)傩愿拍睿?

L

(

G

,

M

,

I

)，≤)為完備格，稱

L

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡瘛６x6對于形式背景(

G

,

M

,

I

)，分別定義□和?的負算子如下：

進一步定義該三支算子的逆算子如下：

其中：

DP

(

G

) =

P

(

G

) ×

P

(

G

)；

DP

(

M

) =

P

(

M

) ×

P

(

M

)。定義8對于形式背景(

G

,

M

,

I

)，

X

,

Y

?

G

,

A

?

M

，如果

A

=(

X

,

Y

)且

A

=(

X

,

Y

)，則稱((

X

，

Y

)，

A

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍睿洖锳ttribute-induced Lattices-概念，簡寫為AEL-概念，其中(

X

，

Y

)和

A

分別稱為AEL-概念的外延和內(nèi)涵。所有AEL-概念構(gòu)成的集合稱為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?，記為All Attribute-induced Lattices(

G

,

M

,

I

)，簡寫為

L

(

G

,

M

,

I

)，若((

X

，

Y

)，

A

)，((

Z

，

W

)，

B

)為形式背景(

G

,

M

,

I

)的AEL-概念，則定義偏序關(guān)系((

X

,

Y

),

A

)≤((

Z

,

W

)，

B

) ?(

X

,

Y

) ?(

C

,

D

) ?

A

?

B

。定 理1對 于 形 式 背 景(

G

,

M

,

I

)，對 于 任 意 的((

X

，

Y

)，

A

)，((

Z

，

W

)，

B

)∈

L

(

G

，

M

，

I

)，如 果 滿 足((

X

,

Y

),

A

) ∧((

Z

,

W

),

B

) =((

X

,

Y

) ?(

Z

,

W

),(

A

?

B

))和((

X

,

Y

),

A

)∨((

Z

,

W

),

B

)=(((

X

,

Y

)?(

Z

,

W

)),(

A

?

B

))，那么稱(

L

(

G

,

M

,

I

)，≤）構(gòu)成完備格。形式背景(

G

,

M

,

I

)的所有AEL-概念在該偏序關(guān)系下是完備格，舉例如下。例1 形式背景(

G

,

M

,

I

)中，

G

={1，2，3，4,5}，

M

={

a

，

b

，

c

，

d

},任意(

g

，

m

)∈

I

時，用1 表示；任意(

G

，

m

)?

I

時，用0表示，如表1。

表1 形式背景(G，M，I)Tab.1 Formal contexts(G,M,I)

形式背景(

G

,

M

,

I

)對應(yīng)的面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)和面向?qū)傩匝a背景概念格

L

(

G

,

M

,

I

)分別如圖1，2。

圖1 例1中形式背景(G，M，I)的概念格Fig.1 LA(G，M，I)for example 1

圖2 例1中形式背景(G，M，I)的面向?qū)傩载摳拍罡馞ig.2 LNA(G，M，I)for example 1

2 由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡竦纳?/h2>

在面向?qū)傩愿拍罡窦捌溲a背景概念格的基礎(chǔ)上，定義由屬性誘導(dǎo)的三支面向?qū)傩詷O大概念集和極小概念集，并生成由屬性誘導(dǎo)的三支面向?qū)傩愿拍睢?/p>定義9 假設(shè)

L

(

G

,

M

,

I

)和

L

(

G

,

M

,

I

)分別是形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡窈兔嫦驅(qū)傩缘难a背景概念格，對于任意(

X

，

Y

)∈

L

(

G

,

M

,

I

)，任意(

X

，

Y

)∈

L

(

G

,

M

,

I

)，(

X

，

Y

)和(

X

，

Y

)可以((

X

,

X

),

Y

?

Y

)的運算形式進行運算，稱這樣的運算為由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大運算，用Δ表示。定義10 假設(shè)

L

(

G

,

M

,

I

)和

L

(

G

,

M

,

I

)分別是形式背景(

G

，

M

，

I

)的面向?qū)傩愿拍罡窈兔嫦驅(qū)傩缘难a背景概念格，對于任意(

X

，

Y

)∈

L

(

G

,

M

,

I

)，任意(

X

，

Y

)∈

L

(

G

,

M

,

I

)，(

X

,

X

)Δ(

Y

,

Y

)=((

X

,

X

),

Y

?

Y

)被稱為由屬性誘導(dǎo)的三支面向性概念格的極大概念，所有由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大概念組成的集合稱為由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大概念集，記為Max All Attribute-induced Set(

G

,

M

,

I

)，簡寫為

S

(

G

，

M

，

I

)。由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大概念集

S

(

G

,

M

,

I

)和由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)之間的關(guān)系如下。定理2 假設(shè)

L

(

G

,

M

,

I

)和

L

(

G

,

M

,

I

)分別是形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡窈兔嫦驅(qū)傩缘难a背景概念格，

S

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向性的極大概念集，

L

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向性概念格，則

L

(

G

,

M

,

I

) ?

S

(

G

,

M

,

I

)。證明 假設(shè)?((

X

,

X

),

Y

) ∈

L

(

G

,

M

,

I

)，那么存在(

X

,

Y

)∈

L

(

G

,

M

,

I

)且(

X

,

Y

)∈

L

(

G

,

M

,

I

)。由面向?qū)傩愿拍罡窈推溲a背景概念格的定義可知

X

=

Y

,

Y

=

X

，

X

=

Y

,

Y

=

X

；根據(jù)由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡竦亩x可知

Y

=(

X

,

X

)，

Y

=(

X

,

X

)，又

Y

=(

X

,

X

)=(

X

?

X

)。令

Y

=

X

,

Y

=

X

，有

Y

=

Y

?

Y

，因 此 有((

X

,

X

),

Y

?

Y

)∈

L

(

G

,

M

,

I

)，再 根 據(jù) 定 義10 可 知((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,

I

)，因 此

L

(

G

,

M

,

I

) ?

S

(

G

,

M

,

I

)。例2 例1中的

L

(

G

,

M

,

I

)中的概念(45，

ac

)和

L

(

G

,

M

,

I

)中的概念(13，

ace

)按照定義9得到極大概念((45，13)，

ace

)，可以得出((45，13)，

ace

)∈

S

(

G

,

M

,

I

)，同時也有((45，13)，

ace

)∈

L

(

G

,

M

,

I

)；而

L

(

G

,

M

,

I

)中的概念(5，

a

)和

L

(

G

,

M

,

I

)中的概念(2，

bc

)按照定義9 可得到極大概念((5，2)，

ace

)，易知((5，2)，

ace

)∈

S

(

G

，

M

，

I

)，但((5，2)，

ace

)?

L

(

G

,

M

,

I

)。

定理2表明，由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡癜谟蓪傩哉T導(dǎo)的三支面向?qū)傩缘臉O大概念集中。

定義11 假設(shè)

L

(

G

,

M

,

I

)和

L

(

G

,

M

,

I

)分別是形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡窈兔嫦驅(qū)傩缘难a背景概念格，對于任意(

X

，

Y

)∈

L

(

G

,

M

,

I

)，任意（

X

，

Y

）∈

L

(

G

,

M

,

I

)，如果

X

?(

Y

?

Y

)或者

X

?(

Y

?

Y

)，那么稱(

X

,

X

)Δ(

Y

,

Y

)=((

X

,

X

),

Y

?

Y

)為由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念，稱所有由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念組成的集合為由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念集，記為Min All Attributeinduced Set(

G

,

M

,

I

)，簡寫為

S

(

G

,

M

,

I

)。定理3

S

(

G

,

M

,

I

)?

S

(

G

,

M

,

I

)。證 明 假 設(shè)?((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,),那 么 根 據(jù) 定 義11 存 在(

X

，

Y

)∈

L

(

G

,

M

,

I

)，(

X

，

Y

)∈

L

(

G

,

M

,

I

)，再根據(jù)定義9可知((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,

I

)，故有

S

(

G

,

M

,

I

)?

S

(

G

,

M

,

I

)。定理4

S

(

G

，

M

，

I

)為形式背景(

G

，

M

，

I

)的由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念集，

L

(

G

，

M

，

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡瘢瑒t

L

(

G

,

M

,

I

)?

S

(

G

,

M

,

I

)=?。證 明 假 設(shè)?((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,

I

)，由 定 義11 可 知

X

≠(

Y

?

Y

)，或 者

X

≠(

Y

?

Y

)，((

X

,

X

),

Y

?

Y

)?

L

(

G

,

M

,

I

)，

L

(

G

,

M

,

I

)?

S

(

G

,

M

,

I

)=?。定理3和定理4說明形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念集

S

(

G

,

M

,

I

)包含在形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大概念集

S

(

G

,

M

,

I

)中，但是和形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)之間的交集為空。由例2 中求出的極大概念((5，2)，

ace

)可知，((5，2)，

ace

)∈

S

(

G

,

M

,

I

)，但((5，2)，

ace

)?

L

(

G

,

M

,

I

)。定理5

S

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩缘臉O大概念集，

S

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩缘臉O小概念集，

L

(

G

,

M

,

I

)為形式背景(

G

,

M

,

I

)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?，則有

L

(

G

,

M

,

I

) =

S

(

G

,

M

,

I

) -

S

(

G

,

M

,

I

)。證明 由定理3 和定理4 知，

L

(

G

,

M

,

I

) ?

S

(

G

,

M

,

I

) -

S

(

G

,

M

,

I

)，對于任意((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,

I

) -

S

(

G

,

M

,

I

)，有((

X

,

X

),

Y

?

Y

)∈

S

(

G

,

M

,

I

)，且 有

X

?(

Y

?

Y

)，

X

?(

Y

?

Y

)，因((

X

,

X

),

Y

?

Y

)?

S

(

G

,

M

,

I

)，故

X

?(

Y

?

Y

)和

X

?(

Y

?

Y

)不成立；又因

X

=(

Y

?

Y

)和

X

=(

Y

?

Y

)，((

X

,

X

),

Y

?

Y

)∈

L

(

G

,

M

,

I

)，故

L

(

G

,

M

,

I

) =

S

(

G

,

M

,

I

) -

S

(

G

,

M

,

I

)。根據(jù)上述理論，可求得表1中形式背景(

G

,

M

,

I

)對應(yīng)的由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)，結(jié)果如圖3。

圖3 例1中形式背景(G，M，I)由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡馞ig.3 LAAE(G，M，I)for example 1

3 算法及算法分析

輸入面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)和面向?qū)傩匝a背景概念格

L

(

G

,

M

,

I

)，輸出由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?p>L

(

G

,

M

,

I

)。

假設(shè)形式背景(

G

,

M

,

I

)的對象個數(shù)為

s

、屬性個數(shù)為

t

，本文算法是在已知形式背景(

G

,

M

,

I

)面向?qū)傩愿拍罡窦捌溲a背景概念格的基礎(chǔ)上，求解由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?，其時間復(fù)雜度會隨形式背景(

G

,

M

,

I

)的面向?qū)傩愿拍罡窦捌溲a背景概念格個數(shù)的變化而變化。若取

n

=max(||

L

(

G

,

M

,

I

)||，||

L

(

G

,

M

,

I

)||)，則該算法的時間復(fù)雜度為

O

(

n

)?？偟膩碚f，在已知形式背景(

G

,

M

,

I

)的情況下，求由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡瘢帽疚乃惴煞殖蓛蓚€部分：利用相關(guān)知識求出形式背景(

G

,

M

,

I

)的

L

(

G

,

M

,

I

)和

L

(

G

,

M

,

I

)，按照文獻[4]和通用的面向?qū)ο蟾拍罡駱?gòu)造算法，其時間復(fù)雜度為

O

(2+ 2)；在第一部分的基礎(chǔ)上結(jié)合本文算法求出

L

(

G

,

M

,

I

)，其時間復(fù)雜為

O

(

n

+ 2+ 2)。基于文獻[4]提出的基于背景疊置的三支面向?qū)傩愿竦臉?gòu)造算法，首先利用形式背景(

G

,

M

,

I

)和其補形式背景(

G

,

M

,

I

)構(gòu)造一個混合形式背景，混合形式背景的對象個數(shù)為原形式背景(

G

,

M

,

I

)對象個數(shù)乘以2；然后求出混合形式背景的面向?qū)傩愿拍罡?，利用同?gòu)關(guān)系求出三支面向?qū)傩愿拍罡瘛；旌闲问奖尘暗膶ο髠€數(shù)多于原形式背景(

G

,

M

,

I

)的對象個數(shù)，按照文獻[4]和通用的面向?qū)ο蟾拍罡駱?gòu)造算法，其時間復(fù)雜度為

O

(2+ 2)，通常情況下

O

(

n

+ 2+ 2)<

O

(2+ 2)，故本文算法比文獻[4]算法的時間效率高。

4 結(jié) 論

定義極大和極小概念以及極大概念集和極小概念集，推導(dǎo)出由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡?、極大概念集和極小概念集三者之間關(guān)系，通過三者之間的關(guān)系求出由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡瘢粯?gòu)造由屬性誘導(dǎo)的三支面向?qū)傩愿拍罡竦纳伤惴?，比較分析通用面向?qū)ο蟾拍罡駱?gòu)造算法與本文算法的時間復(fù)雜度。結(jié)果表明，通用面向?qū)ο蟾拍罡駱?gòu)造算法的時間復(fù)雜度為

O

(

n

+ 2+ 2)，本文算法的時間復(fù)雜度為

O

(2+ 2)，通常情況下

O

(

n

+ 2+ 2)<

O

(2+ 2)，本文算法的時間效率高于通用面向?qū)ο蟾拍罡駱?gòu)造算法。