常麗娜 魏玲 彭超林
摘要 屬性約簡(jiǎn)作為形式概念分析中非常重要的一個(gè)研究分支,在三支概念分析中也同樣重要。基于對(duì)象導(dǎo)出三支概念格,提出了保持決策形式背景OE-協(xié)調(diào)性的屬性約簡(jiǎn)理論,豐富了三支概念分析的約簡(jiǎn)理論。首先,定義了決策形式背景的OE-協(xié)調(diào)集和OE-約簡(jiǎn),并將屬性按其特征分為3類。其次,指出OE-約簡(jiǎn)的本質(zhì)就是極小OE-協(xié)調(diào)集,給出了OE-協(xié)調(diào)集的幾個(gè)判定定理,通過(guò)研究OE-協(xié)調(diào)集的充要條件,獲取OE-約簡(jiǎn)的判定定理。最后,給出OE-差別矩陣和OE-差別函數(shù)的定義,并給出了利用OE-差別矩陣和OE-差別函數(shù)計(jì)算OE-約簡(jiǎn)的方法。
關(guān)鍵詞 三支概念分析;屬性約簡(jiǎn);OE-協(xié)調(diào)性;決策形式背景;對(duì)象導(dǎo)出三支概念格
Attribute reduction in formal decision contextsbased on OE-consistency
Abstract Attribute reduction, as a very important branch of formal concept analysis, is equally important in the three-way concept analysis. Based on object-induced concept lattices, attribute reduction theory which preserve OE-consistency of formal decision contexts is proposed, which enriches the reduction theory of three-way concept analysis. Firstly, OE-consistent set and OE-reduct of formal decision contexts are defined, and the attributes are classified into three categories according to their characteristics. Then, it is pointed out the essence of OE-reduct is minimal OE-consistent set, and several judgement theorems of OE-consistent set are given. By studying the necessary and sufficient conditions of OE-consistent set, judgement theorem of OE-reduct is obtained. Finally, the definition of OE-discernibility matrix and OE-discernibility function are given, and the method of calculating OE-reduct by using OE-discernibility matrix and OE-discernibility function is given.
Keywords three-way concept analysis; attribute reduction; OE-consistency; formal decision contexts; object-induced three-way concept lattices
形式概念分析[1-2](formal concept analysis, FCA)作為數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn)的有力工具, 是由德國(guó)數(shù)學(xué)家Wille于1982年提出的, 并被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、沖突分析等很多領(lǐng)域[3]。
在經(jīng)典形式概念分析的基礎(chǔ)上, Qi等結(jié)合三支決策理論[4](three-way decision, 3WD)于2014年提出了三支概念分析[5-6](three-way concept analysis, 3WCA), 既體現(xiàn)了三支決策的思想和應(yīng)用價(jià)值, 也是經(jīng)典形式概念分析的一種擴(kuò)展, 能同時(shí)反映“共同具有”和“共同不具有”兩種信息。目前, 三支概念分析已經(jīng)得到了很多學(xué)者的關(guān)注和認(rèn)可, 研究成果也越來(lái)越豐富。Ren等研究了兩類三支概念格的4種屬性約簡(jiǎn)問(wèn)題, 并討論了它們之間的關(guān)系[7]。Yu等通過(guò)考慮三支概念格(三支粗概念格)的原子、不可約元和補(bǔ)的性質(zhì), 研究了三支概念格(三支粗概念格)的性質(zhì),在具有這些特殊性質(zhì)的完備格與三支概念格(三支粗概念格)之間建立了一個(gè)同構(gòu)映射[8]。Zhi等提出了三支對(duì)偶概念格, 探討了三支對(duì)偶概念格與經(jīng)典對(duì)偶概念格的關(guān)系, 研究了三支概念格、三支對(duì)偶概念格、三支面向?qū)ο蟾拍罡窈腿嫦驅(qū)傩愿拍罡?種類型的三支概念分析模型之間的關(guān)系[9]。Yang等引入一對(duì)組合算子, 提出了一種構(gòu)造屬性誘導(dǎo)三支概念格和對(duì)象誘導(dǎo)三支概念格的新方法[10]。Zhao等對(duì)三支算子的性質(zhì)重新表述,研究了不同類型的三支概念格之間的關(guān)系[11]。
決策形式背景[12]這一概念是由魏玲提出的, 隨之決策形式背景的知識(shí)發(fā)現(xiàn)成為FCA的研究熱點(diǎn)。決策形式背景只有在滿足一定的協(xié)調(diào)意義下, 對(duì)其的知識(shí)發(fā)現(xiàn)才更具合理性。Wei等定義了決策形式背景的強(qiáng)、弱協(xié)調(diào)性, 并在此基礎(chǔ)上研究了兩種協(xié)調(diào)意義下的屬性約簡(jiǎn)[13]。Li等對(duì)決策形式背景的屬性約簡(jiǎn)與規(guī)則獲取進(jìn)行了較為系統(tǒng)深入的研究[14-15]。Chen等研究了大規(guī)模決策形式背景的屬性約簡(jiǎn)問(wèn)題,提出了一種計(jì)算決策形式背景差別矩陣簡(jiǎn)單有效的方法[16]。作為形式概念分析的擴(kuò)展, 決策形式背景的知識(shí)發(fā)現(xiàn)在三支概念分析中同樣重要。陳雪等基于AE-概念格, 研究了決策形式背景的保持非冗余規(guī)則信息不變的屬性約簡(jiǎn)問(wèn)題[17]。林洪等研究了三支粒協(xié)調(diào)決策形式背景的粒約簡(jiǎn)問(wèn)題[18]。劉琳等基于AE-概念格研究了決策背景的規(guī)則提取問(wèn)題[19-20]。Wei等基于兩類三支概念格定義了決策形式背景的OE-協(xié)調(diào)性和AE-協(xié)調(diào)性, 研究了三支規(guī)則提取問(wèn)題[21]。Long等基于三支概念格研究了不完備決策背景的規(guī)則獲取問(wèn)題[22]。
決策形式背景在滿足一定的協(xié)調(diào)意義下,其知識(shí)發(fā)現(xiàn)才更具合理性和可解釋性,因此,研究決策形式背景不同的協(xié)調(diào)性,可以挖掘出一個(gè)決策背景更多的信息與細(xì)節(jié)。本文根據(jù)文獻(xiàn)[20]提出的決策形式背景的OE-協(xié)調(diào)性的定義, 基于對(duì)象導(dǎo)出三支概念格,研究決策形式背景保持OE-協(xié)調(diào)性的屬性約簡(jiǎn)理論, 并通過(guò)實(shí)例表明協(xié)調(diào)集判定定理及約簡(jiǎn)計(jì)算方法的有效性。
1 預(yù)備知識(shí)
1.1 形式概念分析
將形式背景(G,M,I)的概念的全體記為L(zhǎng)(G,M,I),對(duì)于任意的(X1,A1),(X2,A2)∈L(G,M,I), 它們的偏序關(guān)系為
進(jìn)一步, 定義任意兩個(gè)概念的下確界和上確界為
則L(G,M,I)形成一個(gè)完備格,稱為概念格。
1.2 三支概念分析
下面給出三支算子的概念。
記形式背景(G,M,I)的所有OE-概念構(gòu)成的集合為OEL(G,M,I),所有OE-概念外延構(gòu)成的集合為OELE(G,M,I)。對(duì)于任意的(X1,(A1,B1)),(X2,(A2,B2))∈OEL(G,M,I), 定義它們的偏序關(guān)系為
如果(X1,(A1,B1))≤(X2,(A2,B2))且(X1,(A1,B1))≠(X2,(A2,B2)), 則記為(X1,(A1,B1))<(X2,(A2,B2))。如果(X1,(A1,B1))<(X2,(A2,B2)), 且不存在OE-概念(X,(A,B))使得(X1,(A1,B1))<(X,(A,B))<(X2,(A2,B2))成立, 則稱(X1,(A1,B1))是(X2,(A2,B2))的子概念, (X2,(A2,B2))是(X1,(A1,B1))的父概念, 記作(X1,(A1,B1))(X2,(A2,B2))。其中,任意兩個(gè)OE-概念的下確界和上確界為
則OEL(G,M,I)是一個(gè)完備格,稱為對(duì)象導(dǎo)出三支概念格,簡(jiǎn)記為OE-概念格。
2 決策形式背景的屬性約簡(jiǎn)
2.1 OE-協(xié)調(diào)性與屬性約簡(jiǎn)的相關(guān)定義
本節(jié)首先介紹決策形式背景OE-協(xié)調(diào)性的定義, 然后給出保持決策形式背景OE-協(xié)調(diào)性的協(xié)調(diào)集和約簡(jiǎn)的定義。
定義4[20] ?如果(G,M,I)和(G,N,J)是形式背景, M∩N=, 則稱五元組(G,M,I,N,J)為一個(gè)決策形式背景, 其中M稱為條件屬性集, N稱為決策屬性集。背景(G,M,I)的對(duì)象導(dǎo)出三支概念格記為OEL(G,M,I), 背景(G,N,J)的對(duì)象導(dǎo)出三支概念格記為OEL(G,N,J)。如果對(duì)于任意(Y,(E,F(xiàn)))∈OEL(G,N,J), 總存在(X,(A,B))∈OEL(G,M,I), 使得X=Y,則稱OEL(G,M,I)細(xì)于OEL(G,N,J), 記作OEL(G,M,I)≤OEL(G,N,J), 且稱決策形式背景(G,M,I,N,J)是對(duì)象導(dǎo)出三支協(xié)調(diào)的, 簡(jiǎn)稱為OE-協(xié)調(diào)的。
定義6 設(shè)OE-協(xié)調(diào)的決策形式背景(G,M,I,N,J)的所有OE-約簡(jiǎn)為{Di|Di是約簡(jiǎn),i∈τ}(τ為一個(gè)指標(biāo)集), 則條件屬性集M中的屬性可分為以下3類:
定理1 設(shè)決策形式背景(G,M,I,N,J)是OE-協(xié)調(diào)的, 則其OE-約簡(jiǎn)一定存在。
證明 因?yàn)椋℅,M,I,N,J)是OE-協(xié)調(diào)的, 故M是OE-協(xié)調(diào)集, 若m∈M, 都有(G,M-{m},IM-m,N,J)不是OE-協(xié)調(diào)的, 則M就是OE-約簡(jiǎn)。若m∈M, 使得(G,M-{m},IM-m,N,J)是OE-協(xié)調(diào)的, 令M1=M-{m}, 則M1是OE-協(xié)調(diào)集, 若m1∈M1, 都有(G,M1-{m1},IM1-m1,N,J)不是OE-協(xié)調(diào)的, 則M1是OE-約簡(jiǎn);否則, 再進(jìn)一步研究M1-{m1}。重復(fù)上述過(guò)程, 由于M是有限集, 所以至少可以找到?jīng)Q策形式背景(G,M,I,N,J)的一個(gè)OE-約簡(jiǎn), 故OE-約簡(jiǎn)必存在。
例1 表1給出了一個(gè)決策形式背景(G,M,I,N,J)。其中對(duì)象集G={1,2,3,4}, 條件屬性集為M={a,b,c,d,e,f}, 決策屬性集為N={g,h,i}。
背景(G,M,I)共有13個(gè)對(duì)象導(dǎo)出三支概念, 分別標(biāo)為TCi(i=1,2,…,13), 其對(duì)象導(dǎo)出三支概念格OEL(G,M,I)如圖1所示;背景(G,N,J)共有10個(gè)對(duì)象導(dǎo)出三支概念, 其對(duì)象導(dǎo)出三支概念格OEL(G,N,J)如圖2所示。
容易判斷,OEL(G,M,I)≤OEL(G,N,J), 所以該決策形式背景是OE-協(xié)調(diào)的。它的OE-約簡(jiǎn)共有4個(gè), 分別是D1={a,b,e}, D2={a,c,e}, D3={b,d,e}, D4={c,d,e}。其中OE-核心屬性為e, OE-相對(duì)必要屬性為a,b,c,d, 絕對(duì)不必要屬性為f。
由例1可知OE-協(xié)調(diào)的決策形式背景的OE-約簡(jiǎn)未必是唯一的。
利用上述定義和定理,得到以下推論。
推論1 OE-核心是OE-約簡(jiǎn)OE-約簡(jiǎn)唯一。
證明 。(反證法)假設(shè)若OE-核心是OE-約簡(jiǎn), 則OE-約簡(jiǎn)不唯一。不妨設(shè)Dj,Dk均為OE-約簡(jiǎn), 且Dj≠Dk。那么OE-核心∩i∈τDiDj∩DkDj, 由于Dj是OE-約簡(jiǎn), 而∩i∈τDiDj, 即∩i∈τDi是Dj的真子集, 所以O(shè)E-核心∩i∈τDi不可能是OE-約簡(jiǎn), 與已知條件矛盾, 故假設(shè)不成立。因此, 如果OE-核心是OE-約簡(jiǎn), 則OE-約簡(jiǎn)唯一。
顯然成立。
推論2 m∈M是OE-不必要屬性M-{m}是OE-協(xié)調(diào)集。
推論3 m∈M是OE-核心屬性M-{m}不是OE-協(xié)調(diào)集。
2.2 OE-協(xié)調(diào)集判定定理
因?yàn)闆Q策形式背景上的OE-約簡(jiǎn)D滿足以下兩個(gè)條件:首先, D是OE-協(xié)調(diào)集;其次, 對(duì)于任意的d∈D,D-{d}不是OE-協(xié)調(diào)集。即OE-約簡(jiǎn)的本質(zhì)就是極小OE-協(xié)調(diào)集。因此, 只要對(duì)OE-協(xié)調(diào)集的充要條件研究透徹, 就能獲得OE-約簡(jiǎn)的判定方法。下面給出OE-協(xié)調(diào)集的幾個(gè)充要條件, 即OE-協(xié)調(diào)集判定定理。
證明 必要性。由定理2必要性的證明可得。
證明 必要性。由定理3可證。
定理5 (OE-協(xié)調(diào)集判定定理4)設(shè)(G,M,
證明 必要性。由定理2可證。
上面給出了4個(gè)關(guān)于決策形式背景(G,M,I,N,J)的OE-協(xié)調(diào)集等價(jià)命題(定理2~5), 均可作為一個(gè)條件屬性子集D是否為決策背景的OE-協(xié)調(diào)集的判定方法。但是對(duì)于具體決策形式背景而言, 定理2、3的理論意義更強(qiáng), 定理4、5的可操作性更強(qiáng)。由于只考慮決策屬性集N×N中的元素, 因此,實(shí)際判斷時(shí)多選用定理5。
由定理5及OE-約簡(jiǎn)的定義易得OE-約簡(jiǎn)的判定方法。
例2 (續(xù)例1)針對(duì)表1所示的決策形式背景(G,M,I,N,J), 下面根據(jù)定理5對(duì)任意選取的條件屬性子集是否為OE-協(xié)調(diào)集進(jìn)行判斷,若條件屬性子集為OE-協(xié)調(diào)集,進(jìn)一步利用定理6判斷其是否為OE-約簡(jiǎn)。
設(shè)D={a,b,e,f}, 已知N={g,h,i}, 由于
其中,D滿足定理5, 所以D是OE-協(xié)調(diào)集。進(jìn)一步, D1=D-{f}={a,b,e}也是OE-協(xié)調(diào)集, 所以D不是OE-約簡(jiǎn)。而D1的所有真子集{a, b}, {a, e}, {b, e}均不是OE-協(xié)調(diào)集, 所以D1是OE-約簡(jiǎn)。同理, 可判定D2={a,c,e}, D3={b,d,e}, D4={c,d,e}均為OE-約簡(jiǎn), 與例1所得結(jié)果一致。
定理7 (OE-協(xié)調(diào)集判定定理5)設(shè)(G,M,I,N,J)為OE-協(xié)調(diào)的決策形式背景, 則D是OE-協(xié)調(diào)集的充要條件是
所以有
故
2.3 約簡(jiǎn)方法
下面介紹差別矩陣和差別函數(shù)的定義,通過(guò)差別矩陣和差別函數(shù)的方法可以得到OE-協(xié)調(diào)決策形式背景的OE-約簡(jiǎn)。
定義7 設(shè)(G,M,I,N,J)為OE-協(xié)調(diào)決策形式背景, (Xi,(Ai,Bi)),(Xj,(Aj,Bj))∈OEL(G,M,I), 稱
為(Xi,(Ai,Bi))與(Xj,(Aj,Bj))的OE-差別屬性集。稱
ΛOEL=(DISOE((Xi,(Ai,Bi)),
(Xj,(Aj,Bj))),(Xi,(Ai,Bi)),
(Xj,(Aj,Bj))∈OEL(G,M,I)
為該OE-協(xié)調(diào)決策形式背景的OE-差別矩陣。
例3 (續(xù)例1)根據(jù)定義7, 表2給出了例1中決策形式背景(G,M,I,N,J)的OE-差別矩陣ΛOEL。其中, 矩陣第i行第j列代表的是OE-條件概念TCi與TCj的差別屬性集DISOEL(TCi, TCj)。
為敘述方便,將OE-差別矩陣中的元素稍作變換, 若DISOEL((X,(A,B)),(Y,(C,D)))=(E,F(xiàn)), 則重新記DISOEL((X,(A,B)),(Y,(C,D)))為H=E∪F, 依然用ΛOEL來(lái)表示決策背景(G,M,I,N,J)的OE-差別矩陣。
定理8表明, OE-協(xié)調(diào)的決策形式背景的協(xié)調(diào)集與差別矩陣的每個(gè)元素相交都非空, 而約簡(jiǎn)就是找滿足這些條件的協(xié)調(diào)集中的極小集合。
定義8 設(shè)(G,M,I,N,J)為OE-協(xié)調(diào)決策形式背景, 則其OE-差別函數(shù)為
根據(jù)∧,∨的運(yùn)算律, 差別函數(shù)f可以變換為最小析取范式, 這個(gè)最小范式的所有合取式就是OE-協(xié)調(diào)的決策形式背景(G,M,I,N,J)的全部OE-約簡(jiǎn)。
例4 (續(xù)例1)求例1中決策形式背景(G,M,I,N,J)的OE-差別函數(shù)。
決策形式背景(G,M,I,N,J)共有4個(gè)約簡(jiǎn),分別是D1={a,b,e},D2={a,c,e},D3={b,d,e},D4={c,d,e}, 與例1所得結(jié)果相同。
3 結(jié)語(yǔ)
本文基于對(duì)象導(dǎo)出三支概念格, 在OE-協(xié)調(diào)的決策形式背景下, 首先定義了OE-協(xié)調(diào)集和OE-約簡(jiǎn); 其次,給出了OE-協(xié)調(diào)集的幾個(gè)判定定理和OE-約簡(jiǎn)的判定定理; 最后,給出了利用差別矩陣和差別函數(shù)求OE-約簡(jiǎn)的計(jì)算方法。對(duì)于OE-協(xié)調(diào)的決策形式背景, OE-約簡(jiǎn)也是保持OE-非冗余規(guī)則信息不丟失的約簡(jiǎn), 所以本文提出的OE-協(xié)調(diào)集的判定定理也是保持OE-非冗余規(guī)則信息不丟失的協(xié)調(diào)集判定定理, 豐富了三支概念分析的內(nèi)容。
研究決策形式背景的屬性約簡(jiǎn)理論是十分有意義的, 在約簡(jiǎn)后的決策背景上進(jìn)行知識(shí)的更新與獲取, 既能保證知識(shí)的完整性, 也更加精煉。本文是從對(duì)象導(dǎo)出三支概念格出發(fā),研究了決策形式背景保持OE-協(xié)調(diào)性的屬性約簡(jiǎn)問(wèn)題,下一步還可從屬性導(dǎo)出三支概念格出發(fā)來(lái)研究決策屬性背景的保持AE-協(xié)調(diào)性的約簡(jiǎn)問(wèn)題。
參考文獻(xiàn)
[1] WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts [C]∥RIVAL I. Ordered Sets. Dordrecht-Boston: Reidel, 1982: 445-470.
[2] GANTER B, WILLE R. Formal concept analysis: Mathematical foundations [M].Berlin: Springer-Verlag, 1999.
[3] ZHI H L, QI J J, QIAN T, et al.Conflict analysis under one-vote veto based on approximate three-way concept lattice[J]. Information Sciences, 2020, 516: 316-330.
[4] YAO Y Y. An outline of a theory of three-way decisions [C]∥Rough Sets and Current Trends in Computing. Berlin: Springer, 2012: 1-17.
[5] QI J J, WEI L, YAO Y Y. Three-way formal concept analysis [C]∥Rough Sets and Knowledge Technology. Cham: Springer, 2014: 732-741.
[6] QI J J, QIAN T, WEI L. The connections between three-way and classical concept lattices [J]. Knowledge-Based Systems, 2016, 91: 143-151.
[7] REN R S, WEI L. The attribute reductions of three-way concept lattices [J].Knowledge-Based Systems, 2016, 99: 92-102.
[8] YU H Y, LI Q G, CAI M J. Characteristics of three-way concept lattices and three-way rough concept lattices[J].Knowledge-Based Systems, 2018, 146: 181-189.
[9] ZHI H L, QI J J, QIAN T, et al. Three-way dual concept analysis[J].International Journal of Approximate Reasoning, 2019, 114: 151-165.
[10]YANG S C, LU Y N, JIA X Y, et al. Constructing three-way concept lattice based on the composite of classical lattices[J].International Journal of Approximate Reasoning, 2020, 121: 174-186.
[11]ZHAO X R, MIAO D Q, HU B Q. On relationship between three-way concept lattices[J].Information Sciences, 2020, 538: 396-414.
[12]魏玲. 粗糙集與概念格的約簡(jiǎn)理論與方法[D].西安: 西安交通大學(xué), 2005.
[13]WEI L, QI J J, ZHANG W X. Attribute reduction theory of concept lattice based on decision formal contexts [J].Science in China Series F: Information Sciences, 2008, 51(7): 910-923.
[14]LI J H, MEI C L, LYU Y J. Knowledge reduction in decision formal contexts[J].Knowledge-Based Systems, 2011, 24(5): 709-715.
[15]LI J H, MEI C L, WANG J H, et al. Rule-preserved object compression in formal decision contexts using concept lattices [J].Knowledge-Based Systems, 2014, 71: 435-445.
[16]CHEN J K, MI J S, XIE B, et al. Attribute reduction in formal decision contexts and its application to finite topological spaces [J].International Journal of Machine Learning and Cybernetics, 2021, 12: 39-52.
[17]陳雪, 魏玲, 錢婷. 基于AE-概念格的決策形式背景屬性約簡(jiǎn)[J].山東大學(xué)學(xué)報(bào)(理學(xué)版), 2017, 52(12): 95-103.
CHEN X, WEI L, QIAN T. Attribute reduction in formal decision contexts based on AE-concept lattices [J].Journal of Shandong University (Natural Science), 2017, 52(12): 95-103.
[18]林洪, 秦克云. 決策形式背景三支粒約簡(jiǎn)[J].計(jì)算機(jī)科學(xué), 2018, 45(10): 47-50.
LIN H, QIN K Y. Three-way granular reduction for decision formal context [J].Computer Science, 2018, 45(10): 47-50.
[19]劉琳, 錢婷, 魏玲. 基于屬性導(dǎo)出三支概念格的決策背景規(guī)則提?。跩].西北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 46(4): 481-487.
LIU L, QIAN T, WEI L.Rules extraction in formal decision contexts based on attribute-induced three-way concept lattices [J]. Journal of Northwest University (Natural Science Edition), 2016, 46(4): 481-487.
[20]劉琳, 魏玲, 錢婷. 決策形式背景中具有置信度的三支規(guī)則提?。跩].山東大學(xué)學(xué)報(bào)(理學(xué)版), 2017, 52(2): 101-110.
LIU L, WEI L, QIAN T. Three-way rules extraction in formal decision contexts with confidence [J].Journal of Shandong University (Natural Science), 2017, 52(2):101-110.
[21]WEI L, LIU L, QI J J, et al. Rules acquisition of formal decision contexts based on three-way concept lattices [J].Information Sciences, 2020, 516: 529-544.
[22]LONG B H, XU W H, ZHANG X Y. Double threshold construction method for attribute-induced three-way concept lattice in incomplete fuzzy formal context [J].The Journal of Engineering, 2020(13): 549-554.
西北大學(xué)學(xué)報(bào)(自然科學(xué)版)2024年2期