基于不完備背景的3類SE-ISI概念約簡

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

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

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

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

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

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

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

1 預備知識

定義1[19]稱四元組IK=(G,M,{+,?,-},J)為不完備形式背景。其中:G={g1,g2,…,gp}為對象集;M={m1,m2,…,mq}為屬性集;J為G、M及{+,?,-}之間的三元關系,即J?G×M×{+,?,-}。(g,m,+)∈J表示對象g具有屬性m;(g,m,?)∈J表示不確定對象g是否具有屬性m;(g,m,-)∈J表示對象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)。其中:對象集G={1,2,3,4};屬性集M={a,b,c,d,e,f,g}。若某對象具有某屬性,則表中對象所在行與屬性所在列的交叉位置記為+;若該對象不確定是否具有該屬性,則相應位置記為?;若該對象不具有該屬性,則相應位置記為-。IK對應的SE-ISI概念格L如圖1所示,其中,ci(i=1,2,…,11)是相應SE-ISI概念編號。

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

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

2 3類SE-ISI概念約簡

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

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

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

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

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

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

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

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

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

2.2 3類SE-ISI概念約簡之間的關系

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

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

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

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

證明因為CR?CCS,所以根據(jù)定理2可得:CR?CCS+,CR?CCS+?。

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

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

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

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

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

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

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

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

定義8設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)關于SE-ISI概念的正信息代表概念,簡稱正信息SE-ISI代表概念,其全體記為REP+((g,m))。

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

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

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

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

3類SE-ISI代表概念矩陣的相關性質如下。

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

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

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

結論3) 對任意(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))。

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

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

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) 類似于結論1)的證明,可得結論2)成立。

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

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

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

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

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

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

φ(Λ+)=

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

根據(jù)吸收律與分配律,φ(Λ+)對應的最小析取范式的所有合取式為IK的所有保持正信息不變的SE-ISI概念約簡。但通過φ(Λ+)計算時存在冗余的信息,因此記包含關系下所有極小REP+((g,m))組成的矩陣為最小正信息SE-ISI代表概念矩陣Λmin+,φ(Λmin+)對應的最小析取范式的所有合取式能更簡單得到所有保持正信息不變的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+=

進而正信息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”分別表示保持正信息、保持廣義正信息、保持關系不變這3類不同SE-ISI概念約簡含義。

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

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

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

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

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

例4表2為不完備背景(U,A,{+,?,-},S),其SE-ISI概念格如圖3所示。其中,ci(i=1,2,…,10)是相應SE-ISI概念編號。將所有SE-ISI概念根據(jù)定義10分類,其結果如表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設IK為不完備背景,L為其SE-ISI概念格,c0∈L。下列結論成立:

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

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

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

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

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

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

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

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

定理8設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 結語

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

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