k級(jí)近似概念及其應(yīng)用

范 妍，魏 玲

(西北大學(xué) 數(shù)學(xué)學(xué)院, 陜西 西安 710127)

形式概念分析是由德國(guó)數(shù)學(xué)家Wille于1982年提出的[1]用于數(shù)據(jù)分析和知識(shí)發(fā)現(xiàn)的理論。國(guó)內(nèi)外許多學(xué)者對(duì)形式概念分析進(jìn)行了深入的研究,并在概念格的屬性約簡(jiǎn)[2-6]、規(guī)則提取[7-8]、概念格構(gòu)造[8-11]等方面取得了一定的成果。形式概念分析已廣泛應(yīng)用于軟件工程[12]、決策分析[13]等領(lǐng)域。

在形式概念的數(shù)據(jù)基礎(chǔ)—形式背景上,根據(jù)對(duì)象擁有的屬性是否相同,可將對(duì)象集進(jìn)行劃分,從而形成多個(gè)對(duì)象等價(jià)類。魏玲[14]等人通過(guò)研究對(duì)象等價(jià)類與概念的關(guān)系,證明了概念的外延一定是由若干個(gè)對(duì)象等價(jià)類的并得到的,而并非等價(jià)類的并一定是概念的外延,于是這些不是外延的對(duì)象子集涵蓋著的有用的信息就不能通過(guò)概念來(lái)獲取。其原因是概念對(duì)于對(duì)象集和屬性集的要求比較苛刻,通過(guò)概念來(lái)進(jìn)行形式背景的信息獲取有一定的局限性。于是很多學(xué)者將獲取概念的條件弱化后提出近似概念[8,11,15],從而進(jìn)一步獲取信息。

Wan和Wei在文獻(xiàn)[15]中提出基于k-階關(guān)系的近似概念,對(duì)某些不是概念卻有一定實(shí)際意義的二元對(duì)進(jìn)行獲取,并且賦予較為其合理的語(yǔ)義解釋。本文提出的k級(jí)近似概念則是對(duì)這種基于k-階關(guān)系的近似概念進(jìn)行改進(jìn),使其具有更符合實(shí)際應(yīng)用的語(yǔ)義。首先,本文研究了k級(jí)近似概念的相關(guān)性質(zhì),及其與形式概念、基于k-階關(guān)系的近似概念之間的關(guān)系。此外,本文利用k級(jí)近似概念為某些非外延等價(jià)類的并賦予合理的語(yǔ)義解釋,并據(jù)此語(yǔ)義對(duì)對(duì)象等價(jià)類進(jìn)行排序,最終為實(shí)際決策提供幫助。

1 預(yù)備知識(shí)

1.1 形式概念分析基礎(chǔ)知識(shí)

定義1[1-2]稱(G,M,I)為一個(gè)形式背景,其中G={g1,…,gn}為對(duì)象集,每個(gè)稱為一個(gè)對(duì)象,M={m1,…,mq}為屬性集,每個(gè)mj(j≤q)稱為一個(gè)屬性,I為G與M之間的二元關(guān)系,I?G×M。若(g,m)∈I,則g具有屬性m,記為gIm。

對(duì)于形式背景(G,M,I),在對(duì)象子集X?G和屬性子集B?M上可以定義一對(duì)對(duì)偶算子:

X*={m∈M|?g∈X,gIm}

B*={g∈G|?m∈B,gIm}

X*表示X中所有對(duì)象共同擁有的屬性集合,B*表示共同擁有B中所有屬性的對(duì)象集合。

本文記{g}*為g*,g∈G;記{m}*為m*,m∈M。若?g∈G,m∈M,都有g(shù)*≠?,g*≠M(fèi),m*≠?,m*≠G,則稱形式背景是正則的。本文研究的形式背景都是正則的,且是有限的。

定義2[2]設(shè)(G,M,I)為一個(gè)形式背景,X?G,B?M,如果二元組(X,B)滿足X*=B,B*=X,則稱(X,B)為一個(gè)形式概念,簡(jiǎn)稱概念。其中稱X為概念的外延, 稱B為概念的內(nèi)涵。

?g∈G,(g**,g*)是概念,稱其為對(duì)象概念。類似地,?m∈M,(m*,m**)也是概念,稱其為屬性概念。

文獻(xiàn)[2]給出了形式背景下算子的相關(guān)性質(zhì)。

性質(zhì)1[2]對(duì)于形式背景(G,M,I),設(shè)X1,X2,X?G,B1,B2,B?M,則有下列基本性質(zhì):

(ii)X?X**,B?B**，

(iii)X*=X***,B*=B***，

(iv)X?B*?B?X*，

(vii)(X**,X*)和(B*,B**)都是概念。

用L(G,M,I)表示形式背景(G,M,I)的全體概念。若在L(G,M,I)上定義偏序關(guān)系為:

(X1,B1)≤(X2,B2)?X1?X2(?B2?B1)

若(X1,B1),(X2,B2)∈L(G,M,I),有

(X1,B1)∧(X2,B2)=(X1∩X2,(B1∪B2)**)，

(X1,B1)∨(X2,B2)=((X1∪X2)**,B1∩B2)

也是概念,從而L(G,M,I)是格,并且是完備格,稱其為概念格。

?X?G,B?M,記IB=I∩(G×B),則有X*B={m∈B|?g∈X,(g,m)∈I}。當(dāng)B為屬性全集M時(shí),簡(jiǎn)記為X*。

定理2[14]設(shè)(G,M,I)為一個(gè)形式背景,G/RM為其上的劃分,記

則?(X,B)∈L(G,M,I),都成立X∈σ(G/RM)。

定理2表明,在形式背景(G,M,I)下,任何一個(gè)概念的外延都是由RM中某些等價(jià)類的并構(gòu)成,但等價(jià)類的并不一定都是外延。σ(G/RM),若Y**≠Y*,則稱Y為非外延類。

1.2 基于k-階關(guān)系的近似概念基本理論

定義3[15]設(shè)(G,M,I)為形式背景,?B?M,若

定義4[15]設(shè)(G,M,I)為形式背景,?g∈G,稱([g]k-,g*)是g的k-左鄰域近似概念,([g]k+,g*)是g的k-右鄰域近似概念,分別記為gk-LNAC和gk-RNAC。

定理3[15]設(shè)(G,M,I)為形式背景,?g∈G,有[g](|M|-2)+=g**。

定理3表明,當(dāng)k=|M|-2時(shí),相應(yīng)的右鄰域近似概念([g](|M|-2)+,g*)是概念格的對(duì)象概念。

例1我們將文獻(xiàn)15中例1的形式背景進(jìn)行凈化,得到本例形式背景表1。這是一個(gè)購(gòu)房者對(duì)于若干小區(qū)各項(xiàng)指標(biāo)是否滿意的調(diào)查表。其中,G={1,2,3,4,5} 是小區(qū)的集合,M={a,b,c,d,e}是調(diào)查指標(biāo)的集合,其中a-房屋價(jià)格,b-交通狀況,c-娛樂(lè)設(shè)施,d-物業(yè)管理,e-工程質(zhì)量。在表1中,×表示購(gòu)買者對(duì)此項(xiàng)滿意,空格則表示購(gòu)買者不滿意。

表1 形式背景(G, M,I)Tab.1 A formal context (G, M,I)

為了便于描述,本文例子中的集合均以元素序列形式給出。若取B=M={a,b,c,d,e}則根據(jù)定義3和定義4可以得到所有的gk-LNAC和gk-RNAC,如表2和3所示。

我們以對(duì)象5為例給出gk-LNAC和gk-RNAC的解釋。g0-LNAC=(5,abe):購(gòu)房者對(duì)5號(hào)樓盤的房屋價(jià)格,交通情況和工程質(zhì)量均滿意。gk-RNAC=(5,abe)(0≤k≤3):能夠讓購(gòu)房者在這三方面滿意的只有5號(hào)樓盤;g1-LNAC=(35,abe):若對(duì)房屋價(jià)格要求不高,3號(hào)樓盤可作為備選;g2-LNAC=(345,abe):若購(gòu)房者不考慮交通狀況和娛樂(lè)設(shè)施,則還可以將4號(hào)樓盤作為備選;g3-LNAC=(345,abe):在不考慮房屋價(jià)格、交通情況和工程質(zhì)量這3個(gè)指標(biāo)時(shí),{3,4,5}是最大的選擇范圍。

表2 gk-LNACTab.2 gk-LNAC

表3 gk-RNACTab.3 gk-RNAC

2 k級(jí)近似概念

針對(duì)以上分析,本節(jié)在k-階關(guān)系基礎(chǔ)上提出k級(jí)關(guān)系,進(jìn)一步定義k級(jí)近似概念,并為非外延類賦予更有助實(shí)際決策的語(yǔ)義解釋。

2.1 k級(jí)近似概念的定義及性質(zhì)

例2(續(xù)例1) 令B=M={a,b,c,d,e},0≤k≤3,我們可以得到每一個(gè)對(duì)象關(guān)于B的k級(jí)近似概念，如表4所示。

表4 gk-NACTab.4 gk-NAC

以對(duì)象5為例來(lái)說(shuō)明k級(jí)近似概念對(duì)非外延類賦予的語(yǔ)義解釋, 若某人對(duì)5號(hào)樓盤滿意:① 0-NAC:(5,abe)表示購(gòu)買者對(duì)5號(hào)樓盤的房屋價(jià)格,交通情況和工程質(zhì)量均滿意,并且只有5號(hào)樓盤能夠讓購(gòu)買者在這3個(gè)方面滿意;② 1-NAC:(135,abe)表示,若購(gòu)買者愿意放松一個(gè)條件以增多備選項(xiàng),那么放松交通狀況的要求,1,5將作為備選,若放松房屋價(jià)格的要求,3,5 將作為備選;③ 2-NAC:(12345,abe)表示,若購(gòu)買者愿意放棄交通情況和工程質(zhì)量?jī)蓚€(gè)條件,那么2和4進(jìn)入備選范圍,1,2,4,5將作為備選;同時(shí),5的2級(jí)近似概念表示在只剩一個(gè)條件要求時(shí),所有的樓盤均可作為備選。

根據(jù)定義5, 可以得出k級(jí)近似概念的以下性質(zhì)。

性質(zhì)2設(shè)(G,M,I)為形式背景,B?M,?g,gi,gj∈G,0≤k≤|B|-1,有

(i) 若k1≤k2,則Rk1(B)?Rk2(B);

證明根據(jù)性質(zhì)2的(iv)及定義5可證。

推論1和性質(zhì)2的(iii)將G上的等價(jià)關(guān)系和k級(jí)關(guān)系聯(lián)系起來(lái)。

2.2 k級(jí)近似概念與形式概念的關(guān)系

Düntsch和Gediga在文獻(xiàn)[9]中將模態(tài)邏輯中的可能性算子與必然性算子引入形式概念分析理論,提出了面向?qū)傩愿拍罡?進(jìn)而Yao又提出了面向?qū)ο蟾拍罡馵16]。隨后,這兩者的相關(guān)研究也已成為形式概念分析理論的重要研究?jī)?nèi)容之一。本節(jié),我們也考慮這兩種算子,并研究相應(yīng)的概念與k級(jí)近似概念的關(guān)系。以下的定理4、推論2及推論3給出相關(guān)結(jié)論。

定義6[9]設(shè)(G,M,I)為形式背景,X?G,B?M,定義□算子和算子:X□={m∈M|m*?X},B□={g∈G|g*?B},X={m∈M|m*∩X≠?},B={g∈G|g*∩B≠?}。

其中,X□表示的屬性集合是:具有其中屬性的對(duì)象一定在X中;X表示的屬性集合則是:具有其中屬性的對(duì)象一定與X有交集。對(duì)偶地,B□表示擁有的屬性包含在B中的對(duì)象集合;B則表示擁有的屬性與B交不為空的對(duì)象集合。

定理4設(shè)(G,M,I)為形式背景,B?M,g∈G,則g*B=G?[g]|B|-1=G。

證明g*B=G??gi∈G,都有?,且?G?(根據(jù)定義5) ?

該定理說(shuō)明, 如果一個(gè)對(duì)象和其余任意的對(duì)象都有共有屬性, 那么該對(duì)象能與任意對(duì)象構(gòu)成k級(jí)關(guān)系。

推論2設(shè)(G,M,I)為形式背景,?g∈G,([g]0,g*)是形式背景(G,M,I)的對(duì)象概念。

推論3設(shè)(G,M,I)為形式背景, (X,B)∈L(G,M,I),則?g∈X, 存在k使得([g]k,g*)滿足B?g*,X?[g]k。

推論3說(shuō)明,任一概念的內(nèi)涵和外延分別包含于某對(duì)象的k級(jí)近似概念的外延和內(nèi)涵,而且可能包含于不同對(duì)象的k級(jí)近似概念的內(nèi)涵與外延中。

2.3 k級(jí)近似概念與基于k-階關(guān)系的近似概念的關(guān)系

從本質(zhì)上,k級(jí)關(guān)系是對(duì)k-階關(guān)系的弱化,從而使得在基于k-階關(guān)系的近似概念的基礎(chǔ)上,k級(jí)近似概念的對(duì)象增多。定理5給出k級(jí)近似概念與基于k-階關(guān)系的近似概念的關(guān)系。

定理5設(shè)(G,M,I)為形式背景,?g∈G,([g]k+,g*)是g的k-階右鄰域近似概念,([g]k-,g*)是g的k-階左鄰域近似概念,([g]k,g*)是g的k級(jí)近似概念,則有

(i) [g]0=[g](|M|-2)+;

(ii)[g]k-?[g]k,k≤|M|-2。

證明(i) 根據(jù)定理3及推論2可證得。

例3(續(xù)例2)G={1,2,3,4,5}, ?g∈G,([g]k+,g*)是g的k-階右鄰域近似概念,根據(jù)定理5,有以下結(jié)論:

(i)[g]0=[g]3+,表5給出具體結(jié)果。即g0能夠表示出讓購(gòu)買者在g*這幾個(gè)方面滿意的所有選擇;如[5]0=[5]3+,則能夠讓購(gòu)買者在房屋價(jià)格, 交通情況和工程質(zhì)量這3個(gè)方面均滿意的樓盤只有5號(hào)樓盤一個(gè)。于是,對(duì)于購(gòu)房者在g*的條件下放松0個(gè)條件這一情況,([g]k+,g*)在k≤|M|時(shí)的取值都是多余的,而([g]0,g*)的表示更為簡(jiǎn)潔明了。

表5 [g]3+與[g]0Tab.5 [g]3+ and [g]0

(ii)[g]k-?[g]k,k≤3,表6給出具體結(jié)果。于是,對(duì)于購(gòu)房者在g*的條件下放松k(1≤k)個(gè)條件這一情況,相比于([g]k-,g*),([g]k,g*)會(huì)提供更多的選擇。如在2*={a,b}(房屋價(jià)格和娛樂(lè)設(shè)施)兩個(gè)條件上放松1個(gè)條件時(shí),相比于[2]1-={2,4},[2]1={1,2,4,5}會(huì)多提供選擇1和5,即在不考慮娛樂(lè)設(shè)施時(shí),1號(hào)和5號(hào)樓盤也可以作為備選。

表6 [g]k-與[g]kTab.6 [g]k- and [g]k

應(yīng)用k級(jí)近似概念的語(yǔ)義解決購(gòu)房推薦這一問(wèn)題,而這種思想可以進(jìn)一步拓展到更復(fù)雜的推薦工作中。

3 基于k級(jí)近似概念的等價(jià)類排序

k級(jí)近似概念為某些非外延等價(jià)類賦予了合理的語(yǔ)義解釋,從而給出了所有符合實(shí)際要求的決策,并且對(duì)基于k-階關(guān)系的近似概念的語(yǔ)義解釋做了進(jìn)一步補(bǔ)充。而實(shí)際情況下,滿足購(gòu)買者意愿的往往不只一個(gè),但購(gòu)買者只能選其一;或購(gòu)買者無(wú)法顧及所有選擇,從而有可能錯(cuò)失更為符合自己意愿的選擇。此時(shí),我們就需要根據(jù)購(gòu)買者的選擇,估測(cè)購(gòu)買者的意愿,進(jìn)而提供一種針對(duì)所有選項(xiàng)的推薦。

本節(jié)將對(duì)象g的k級(jí)近似概念推廣到任意對(duì)象子集的ki級(jí)近似概念,并將其一種語(yǔ)義解釋應(yīng)用于等價(jià)類排序。為了研究方便,取B=M。

設(shè)(G,M,I)為形式背景,X?G為某人滿意的對(duì)象集,G={g1,…,gn},?gi,gj∈G,記gj第一次出現(xiàn)在[gi]k中時(shí),k的取值為

kij=

其含義為:若D(X,gk)≤D(X,gj),則gk相對(duì)gj更接近X。則有以下結(jié)論成立。

該定理說(shuō)明,如果一個(gè)對(duì)象擁有的屬性包含另一對(duì)象擁有的屬性,前者更接近于滿意的對(duì)象集。

下面給例子說(shuō)明X的ki級(jí)近似概念的語(yǔ)義解釋。

例4(續(xù)例3) 若購(gòu)買者對(duì)于2和5號(hào)樓盤感興趣,即X={2,5},X={a,b,c,e}。表7給出D(X,gj)的確定,表8是X的ki級(jí)鄰域。

表7 D(X,gj)Tab.7 D(X,gj)

則ki的取值分別為:k1=5/4,k2=8/4,k3=16/4,k4=17/4,k5=21/4。

表8 X的ki級(jí)鄰域Tab.8 Grade kineighborhood of X

X的ki級(jí)近似概念的語(yǔ)義解釋為:針對(duì)購(gòu)買者的喜好:房屋價(jià)格、交通狀況、娛樂(lè)設(shè)施、工程質(zhì)量,樓盤1為最符合購(gòu)買者意愿,其次為5號(hào)樓盤,2號(hào)樓盤,3號(hào)樓盤,最后是4號(hào)樓盤。

由于X的ki級(jí)近似概念基本思想來(lái)源于k級(jí)近似概念,因此在這里也將其稱為k級(jí)近似概念。

推薦結(jié)果如上,k級(jí)近似概念的語(yǔ)義及其應(yīng)用有以下3個(gè)優(yōu)點(diǎn):①相比于基于k-階關(guān)系的近似概念的語(yǔ)義解釋,k級(jí)近似概念的語(yǔ)義擴(kuò)大了選擇范圍;②適用于購(gòu)買者有不只一個(gè)滿意對(duì)象時(shí)的推薦工作;③當(dāng)購(gòu)房者沒有辦法顧及所有選擇的情況下,給出更符合購(gòu)買者意向的最優(yōu)選擇, 比如, 購(gòu)房者對(duì)2和5號(hào)樓盤感興趣, 這種方法給出了更好的選擇1。

4 結(jié) 語(yǔ)

本文的主要目的是構(gòu)造一種近似概念,從而能夠從形式背景中提取出更有利于實(shí)際決策的信息。首先,在文獻(xiàn)[15]的基于k-階關(guān)系近似概念的研究基礎(chǔ)上,提出了k級(jí)近似概念;其次,通過(guò)k級(jí)近似概念,為非外延類賦予合理的語(yǔ)義解釋,并且將這種語(yǔ)義解釋應(yīng)用于推薦。最后,將k級(jí)近似概念推廣到任意對(duì)象子集,從而給出了一種等價(jià)類的排序的方法,使其語(yǔ)義解釋更適合實(shí)際推薦工作。進(jìn)一步,我們還可以在三支概念[17]上探究非外延類的性質(zhì)及特點(diǎn),并獲取更深層的信息。