朱朵朵,任睿思,趙思雨,魏 玲,3

(1.西北大學(xué) 數(shù)學(xué)學(xué)院,陜西 西安 710127;2.西北大學(xué) 概念、認(rèn)知與智能研究中心,陜西 西安 710127;3.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建 漳州 363000)

形式概念分析(formal concept analysis, FCA)是德國數(shù)學(xué)家Wille[1]在1982年提出的以形式背景為基礎(chǔ)進(jìn)行數(shù)據(jù)分析和知識(shí)發(fā)現(xiàn)的有效數(shù)學(xué)工具。目前,該理論已在概念格的構(gòu)造[2-4]、屬性約簡[5-7]、規(guī)則提取[8]以及與其他理論的結(jié)合[9-10]等方面取得諸多成果。

約簡理論是形式概念分析的一個(gè)重要研究課題。屬性約簡用部分屬性保持全部屬性所具有的某種特性不變,從而消除冗余屬性和數(shù)據(jù),但這個(gè)過程會(huì)損失原始信息。為避免原始信息的損失,2018年,魏玲等受布爾因子分析中因子分解的啟發(fā),提出保持二元關(guān)系不變的概念約簡[11-12]。概念約簡不僅完整保留了形式背景中的原始信息,而且減少了概念數(shù)量,降低了用形式概念分析解決問題的復(fù)雜性。近期,王霞等基于概念可辨識(shí)矩陣給出了概念約簡方法[13];謝小賢等借助矩陣運(yùn)算給出了概念特征和生成概念約簡的方法[14];Zhao等給出了一套基于代表概念矩陣獲得概念協(xié)調(diào)集判定定理、概念約簡及概念特征的理論方法[15];馬文勝等基于同效關(guān)系給出了概念約簡和概念特征的獲取方法[16]。此外,智慧來等提出了形式背景下面向?qū)ο蟾拍罴s簡[17];李俊余等研究了保持三元背景中所有三元關(guān)系不變的三元概念約簡[18]。

實(shí)際生活中,信息缺失無處不在,不完備背景[19]的存在比形式背景更為普遍。針對(duì)不完備背景,Li等定義了近似概念并構(gòu)建了近似概念格[20];Yao基于區(qū)間集理論定義了SE-ISI概念、ISE-SI概念和ISE-ISI概念3種部分已知概念[21];Ren等在Yao的研究基礎(chǔ)上充分討論了部分已知概念格的結(jié)構(gòu)和關(guān)系[22];Wang等研究了不完備背景上SE-ISI概念格的屬性約簡[23];Li等將三支決策引入不完備背景,研究了基于三支近似概念格的屬性約簡[10]。

不完備背景上有SE-ISI概念、ISE-SI概念和ISE-ISI概念3種部分已知概念,本文探討不完備背景的SE-ISI概念約簡,其他兩種部分已知概念約簡問題可以進(jìn)行類似的研究。

本文首先從確定擁有角度、可能擁有角度與所有原始背景信息角度,提出保持正信息、保持廣義正信息與保持關(guān)系不變的SE-ISI概念約簡;其次,給出這3類SE-ISI概念約簡的求解方法;最后,討論SE-ISI概念在每類SE-ISI概念約簡下的特征與聯(lián)系。

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

定義1[19]稱四元組IK=(G,M,{+,?,-},J)為不完備形式背景。其中:G={g1,g2,…,gp}為對(duì)象集;M={m1,m2,…,mq}為屬性集;J為G、M及{+,?,-}之間的三元關(guān)系,即J?G×M×{+,?,-}。(g,m,+)∈J表示對(duì)象g具有屬性m;(g,m,?)∈J表示不確定對(duì)象g是否具有屬性m;(g,m,-)∈J表示對(duì)象g不具有屬性m。

為簡單起見,本文把不完備形式背景統(tǒng)稱為不完備背景。

[B1,C1]∩[B2,C2]=[B1∩B2,C1∩C2],

[B1,C1]∪[B2,C2]=[B1∪B2,C1∪C2],

[B1,C1]-[B2,C2]=[B1-B2,C1-C2]。

(1)

(2)

(3)

(4)

(5)

(6)

例1表1為不完備背景IK=(G,M,{+,?,-},J)。其中:對(duì)象集G={1,2,3,4};屬性集M={a,b,c,d,e,f,g}。若某對(duì)象具有某屬性,則表中對(duì)象所在行與屬性所在列的交叉位置記為+;若該對(duì)象不確定是否具有該屬性,則相應(yīng)位置記為?;若該對(duì)象不具有該屬性,則相應(yīng)位置記為-。IK對(duì)應(yīng)的SE-ISI概念格L如圖1所示,其中,ci(i=1,2,…,11)是相應(yīng)SE-ISI概念編號(hào)。

圖1 SE-ISI概念格LFig.1 SE-ISI concept lattice L

表1 不完備背景IKTab.1 Incomplete context IK

2 3類SE-ISI概念約簡

本節(jié)在不完備背景上分別定義保持正信息、廣義正信息及關(guān)系不變的SE-ISI概念約簡,并進(jìn)一步討論3者之間的關(guān)系。

2.1 3類SE-ISI概念約簡的定義及存在性

首先給出保持正信息不變的SE-ISI概念約簡。

與定義5類似,還可定義以下兩種SE-ISI概念約簡。

與前兩種SE-ISI概念約簡不同,保持關(guān)系不變的SE-ISI概念約簡可用部分SE-ISI概念來保留不完備背景的全部信息。

不完備背景的關(guān)系取值只有+、-、?,若保持任意兩種關(guān)系取值不變,則剩下一種也不變。后文通過保持取值為+和?的關(guān)系不變得到保持關(guān)系不變的SE-ISI概念約簡。

定理1設(shè)IK為不完備背景,保持正信息不變的SE-ISI概念約簡、保持廣義正信息不變的SE-ISI概念約簡以及保持關(guān)系不變的SE-ISI概念約簡必存在。

類似地,可以證明保持廣義正信息不變的SE-ISI概念約簡和保持關(guān)系不變的SE-ISI概念約簡必存在。

例2(續(xù)例1) 根據(jù)定義5、定義6及定義7可以驗(yàn)證SE-ISI概念集合F1={c2,c4,c5,c8},F2={c2,c5,c6,c8},F3={c2,c4,c5,c6,c8}分別是保持正信息、保持廣義正信息及保持關(guān)系不變的SE-ISI概念約簡。以F1為例,如果只需要例1不完備背景中確定擁有的信息,則不需要圖1中所有SE-ISI概念,只需要F1中的4個(gè)SE-ISI概念即可。

2.2 3類SE-ISI概念約簡之間的關(guān)系

根據(jù)2.1節(jié)給出的3類SE-ISI概念約簡定義,本小節(jié)研究3類SE-ISI概念約簡之間的關(guān)系。

定理2設(shè)IK為不完備背景,L為其SE-ISI概念格,有CCS=CCS+∩CCS+?。

定理2表明保持關(guān)系不變的SE-ISI概念協(xié)調(diào)集一定是保持正信息和保持廣義正信息不變的SE-ISI概念協(xié)調(diào)集。反之,如果一個(gè)集合同時(shí)是保持正信息和保持廣義正信息不變的SE-ISI概念協(xié)調(diào)集,則其一定是保持關(guān)系不變的SE-ISI概念協(xié)調(diào)集。

推論1設(shè)IK為不完備背景,有CR?CCS+,CR?CCS+?。

證明因?yàn)镃R?CCS,所以根據(jù)定理2可得:CR?CCS+,CR?CCS+?。

根據(jù)推論1,保持關(guān)系不變的SE-ISI概念約簡一定是保持正信息和保持廣義正信息不變的SE-ISI概念協(xié)調(diào)集。

定理3設(shè)IK為不完備背景,L為其SE-ISI概念格,有CR+∩CR+??CR。

由定理3可知,如果一個(gè)集合同時(shí)是保持正信息和保持廣義正信息不變的SE-ISI概念約簡,則其一定是保持關(guān)系不變的SE-ISI概念約簡。

基于上述分析,3類SE-ISI概念約簡之間的關(guān)系如圖2所示。其中,∧表示合取。

圖2 3類SE-ISI概念約簡的關(guān)系Fig.2 Relationships among three types of SE-ISI concept reducts

3 3類SE-ISI概念約簡的獲取方法

本節(jié)給出3類SE-ISI概念約簡的代表概念矩陣和協(xié)調(diào)集判定定理,并在此基礎(chǔ)上給出3類SE-ISI概念約簡的計(jì)算方法。

首先定義3類SE-ISI代表概念矩陣。

定義8設(shè)IK=(G,M,{+,?,-},J)為不完備背景,L為其SE-ISI概念格,g∈G,m∈M,(X,[B,C])∈L。

1) 如果(g,m)∈X×B,則稱(X,[B,C])是(g,m)關(guān)于SE-ISI概念的正信息代表概念,簡稱正信息SE-ISI代表概念,其全體記為REP+((g,m))。

2) 如果(g,m)∈X×C,則稱(X,[B,C])是(g,m)關(guān)于SE-ISI概念的廣義正信息代表概念,簡稱廣義正信息SE-ISI代表概念,其全體記為REP+?((g,m))。

3)稱REP((g,m))=

是(g,m)關(guān)于SE-ISI概念的關(guān)系代表概念集,簡稱關(guān)系SE-ISI代表概念集。

在此基礎(chǔ)上,稱Λ+=(REP+((g,m))),Λ+?=(REP+?((g,m))),Λ=(REP((g,m)))分別為IK的正信息SE-ISI代表概念矩陣、廣義正信息SE-ISI代表概念矩陣及關(guān)系SE-ISI代表概念矩陣。

3類SE-ISI代表概念矩陣的相關(guān)性質(zhì)如下。

性質(zhì)1設(shè)IK=(G,M,{+,?,-},J)為不完備背景,g∈G,m∈M。Λ=(REP((g,m))),Λ+=(REP+((g,m)))與Λ+?=(REP+?((g,m)))分別為其關(guān)系SE-ISI代表概念矩陣、正信息SE-ISI代表概念矩陣和廣義正信息SE-ISI代表概念矩陣。下列結(jié)論成立:

3) REP+((g,m))?REP+?((g,m))。

證明根據(jù)定義8,結(jié)論1)和結(jié)論2)顯然成立。

結(jié)論3) 對(duì)任意(X,[B,C])∈REP+((g,m)),(g,m)∈X×B,又X×B?X×C,所以(g,m)∈X×C。由定義8知(X,[B,C])∈REP+?((g,m)),故REP+((g,m))?REP+?((g,m))。

事實(shí)上,要得到保持正信息不變的SE-ISI概念協(xié)調(diào)集,只需要找出與所有非空REP+((g,m))相交非空的SE-ISI概念集即可。保持廣義正信息和保持關(guān)系不變的SE-ISI概念協(xié)調(diào)集也是類似的。即定理4所述。

定理4設(shè)IK為不完備背景,L為其SE-ISI概念格,F?L。下列結(jié)論成立:

1)F∈CCS+??REP+((g,m))≠?,F∩REP+((g,m))≠?;

2)F∈CCS+???REP+?((g,m))≠?,F∩REP+?((g,m))≠?;

3)F∈CCS??REP((g,m))≠?,F∩REP((g,m))≠?。

2) 類似于結(jié)論1)的證明,可得結(jié)論2)成立。

由定理4和性質(zhì)1可得保持正信息不變的SE-ISI概念約簡判定定理。

定理5設(shè)IK為不完備背景,L為其SE-ISI概念格。對(duì)任意F?L,若滿足以下條件:

則F是保持正信息不變的SE-ISI概念約簡。

保持廣義正信息和保持關(guān)系不變的SE-ISI概念約簡判定定理也可類似得到。

基于SE-ISI代表概念矩陣可給出SE-ISI概念約簡的計(jì)算方法。

定義9設(shè)IK為不完備背景,L為其SE-ISI概念格。正信息SE-ISI代表概念函數(shù)定義為

φ(Λ+)=

∧REP+((g,m))∈Λ+(∨(X,[B,C])∈REP+((g,m))(X,[B,C]))。

根據(jù)吸收律與分配律,φ(Λ+)對(duì)應(yīng)的最小析取范式的所有合取式為IK的所有保持正信息不變的SE-ISI概念約簡。但通過φ(Λ+)計(jì)算時(shí)存在冗余的信息,因此記包含關(guān)系下所有極小REP+((g,m))組成的矩陣為最小正信息SE-ISI代表概念矩陣Λmin+,φ(Λmin+)對(duì)應(yīng)的最小析取范式的所有合取式能更簡單得到所有保持正信息不變的SE-ISI概念約簡。類似可得φ(Λmin+?),φ(Λmin)。

例3(續(xù)例1)根據(jù)定義8,可得REP+((1,a))={(1,[abdeg,abdeg]),(14,[ab,ab])}={c2,c7}。類似地,可得到所有REP+((g,m))。因此,正信息SE-ISI代表概念矩陣為

Λ+=

最小正信息SE-ISI代表概念矩陣為

Λmin+=

進(jìn)而正信息SE-ISI代表概念函數(shù)為φ(Λmin+)=(c2∧c5∧c4∧c3)∨(c2∧c5∧c4∧c8)。即CR+={{c2,c3,c4,c5},{c2,c4,c5,c8}}。類似地,可得CR+?={{c2,c3,c4,c5},{c2,c3,c5,c8},{c2,c5,c6,c8},{c2,c5,c8,c9}};CR={{c2,c3,c4,c5},{c2,c4,c5,c6,c8},{c2,c4,c5,c8,c9}}。

4 SE-ISI概念特征分析

本節(jié)根據(jù)SE-ISI概念在每種SE-ISI概念約簡的作用將其分為3類,并研究其特征。

記Δ取“+”“+?”“R”分別表示保持正信息、保持廣義正信息、保持關(guān)系不變這3類不同SE-ISI概念約簡含義。

定義10設(shè)IK為不完備背景,L為其SE-ISI概念格,{FΔi|i∈τ,τ為指標(biāo)集}為某類SE-ISI概念約簡的集合。L可分為3類:

1) 核心SE-ISI概念集CΔ=∩i∈τFΔi;

2) 相對(duì)必要SE-ISI概念集KΔ=∪i∈τFΔi∩i∈τFΔi;

3)絕對(duì)不必要SE-ISI概念集UΔ=L∪i∈τFΔi。

式中,Δ∈{+,+?,R}。

例4表2為不完備背景(U,A,{+,?,-},S),其SE-ISI概念格如圖3所示。其中,ci(i=1,2,…,10)是相應(yīng)SE-ISI概念編號(hào)。將所有SE-ISI概念根據(jù)定義10分類,其結(jié)果如表3所示。

圖3 SE-ISI概念格Fig.3 SE-ISI concept lattice

表2 不完備背景(U,A,{+,?,-},S)Tab.2 Incomplete context(U,A,{+,?,-},S)

表3 SE-ISI概念分類Tab.3 Classifications of SE-ISI concepts

從SE-ISI代表概念矩陣角度來說,SE-ISI概念在每類SE-ISI概念約簡下的特征類似,故本文只給出保持正信息不變的SE-ISI概念約簡下的3類SE-ISI概念判定定理。

定理6設(shè)IK為不完備背景,L為其SE-ISI概念格,c0∈L。下列結(jié)論成立:

2)c0∈U+?對(duì)任意REP+((g,m))∈Λmin+,有c0?REP+((g,m));

2)必要性。假設(shè)存在REP+((g0,m0))∈Λmin+,使c0∈REP+((g0,m0)),由定理4知,存在F0∈CR+,使c0∈F0,即c0?U+,矛盾。故對(duì)于任意的REP+((g,m))∈Λmin+,有c0?REP+((g,m))。

充分性。假設(shè)c0?U+,則存在F0∈CR+,使c0∈F0,即存在REP+((g0,m0))∈Λmin+,使c0∈REP+((g0,m0)),矛盾。故c0∈U+。

3) 由結(jié)論1)與結(jié)論2)直接可得。

定理7給出3類SE-ISI概念約簡下核心SE-ISI概念集之間的關(guān)系。

定理7設(shè)IK為不完備背景,L為其SE-ISI概念格,有C+∪C+?=CR。

綜上,C+∪C+?=CR。

3類SE-ISI概念約簡下不必要SE-ISI概念集的關(guān)系,如定理8所述。

定理8設(shè)IK為不完備背景,L為其SE-ISI概念格,有U+∩U+??UR。

綜上,c0∈UR,故U+∩U+??UR。

例5(續(xù)例4)由表3可知,C+={c2,c3},C+?=?,CR={c2,c3},U+∩U+?={c1,c10},UR={c1,c6,c10}。顯然,C+∪C+?=CR,U+∩U+??UR,即滿足定理7和定理8。但c6∈UR,c6?U+∩U+?,即UR?U+∩U+?不一定成立。

5 結(jié)語

本文針對(duì)不完備背景,提出了3類SE-ISI概念約簡,研究了它們之間的關(guān)系,并基于SE-ISI代表概念矩陣給出了SE-ISI概念約簡與SE-ISI概念特征的獲取方法。不同的SE-ISI概念約簡保留不完備背景的信息不同,根據(jù)所需信息選取SE-ISI概念約簡后,可以減少SE-ISI概念的數(shù)量,在一定程度上可以降低用SE-ISI概念進(jìn)行知識(shí)挖掘的復(fù)雜度。

事實(shí)上,每類SE-ISI概念約簡數(shù)量并不唯一,那么對(duì)于每類SE-ISI概念約簡,約簡集間存在怎樣的關(guān)系,以及如何通過評(píng)價(jià)指標(biāo)衡量約簡的優(yōu)劣,將是進(jìn)一步要研究的工作。