基于屬性導出三支概念格的決策背景規(guī)則提取

劉　琳，錢　婷，魏　玲

(西北大學 數學學院，陜西 西安　710127)

?

基于屬性導出三支概念格的決策背景規(guī)則提取

劉琳，錢婷，魏玲

(西北大學 數學學院，陜西 西安710127)

給出了決策形式背景在屬性導出三支概念格下的規(guī)則提取方法。首先定義了屬性導出的三支概念格間的細于關系, 以此為基礎給出了決策形式背景三支協(xié)調的定義以及在三支協(xié)調下提取規(guī)則的方法, 并研究了所獲規(guī)則與經典決策背景下所獲規(guī)則的關系。最后結合實例闡明了三支規(guī)則的有效性與優(yōu)越性。

決策形式背景; 三支概念格; 三支協(xié)調; 規(guī)則提取

形式概念分析(Formal concept analysis, FCA) 是由德國數學家Wille提出的一種從形式背景進行數據分析和規(guī)則提取的強有力工具。形式概念與其上的有序層次結構概念格共同構成FCA的基礎。其中, 概念格生動簡潔地體現(xiàn)了概念之間的泛化和特化關系[1-3]。到目前為止, FCA已經成為人工智能學科的重要研究對象, 在機器學習, 數據挖掘和信息檢索等領域也有廣泛的應用。 其研究思想與方法亦可進一步上升到概念分析[4]。 尤其是將FCA與其他理論領域相結合, 已經取得了豐碩成果。 Yao等研究了粗糙集理論框架下的概念格理論[5-6]。 張文修、王國胤等進一步研究了粗糙集與信息系統(tǒng)的屬性約簡和規(guī)則提取問題[7-10]。 以此為基礎, 魏玲等詳細探討了粗糙集與概念格的屬性約簡理論[11-14]。 另一方面, 為了得到由概念格形成的決策規(guī)則, 張文修、魏玲等人首先提出了由兩個形式背景合成的決策形式背景[8,12], 并借鑒粗糙集理論深入討論了基于概念格的決策形式背景規(guī)則獲取問題。 還有學者進一步探討了策形式背景規(guī)則提取方法以及相應的規(guī)則提取算法[15-19]。

作為決策選擇的標準結構,三支決策(3-way decisions, 3WD)的概念是Yao在2012年首先提出來的, 其思想是基于正域、負域和邊界域三個區(qū)域建立三支決策的規(guī)則獲取[20]。 結合FCA與3WD, Qi等人提出三支概念分析(3-way concept analysis, 3WCA)[21], 包括由對象導出的三支概念格和由屬性導出的三支概念格。 進而, 他們還深入研究了概念格與三支概念格之間的關系[22]。 本文主要研究如何在屬性導出的三支概念格下對決策形式背景進行規(guī)則提取, 并研究三支規(guī)則與原規(guī)則之間的關系。

1　基礎知識

首先給出本文所需的集合運算、 形式背景以及概念格有關的基本概念與性質。

設U是非空有限集合, P(U)表示U的冪集, DP(U)表示笛卡兒積P(U)×P(U)。 對于(A, B), (C, D) ∈ DP(U) 定義:

(A, B) ∩ (C, D)=(A ∩ C, B ∩ D),

(A, B)∪(C, D)=(A ∪ C, B ∪ D),

(A, B)c=(U-A, U-B)=(Ac, Bc),

1.1形式概念分析

定義1[2]稱三元組(G, M, I)為一個形式背景, 其中G={x1，x2，…，xn}, 每一個xi(i≤ n)被稱為一個對象; M={a1，a2，…，am},每一個aj(j≤ m)是一個屬性; 對于 x∈G與a∈M, 如果x I a, 記 (x, a)∈I, 并且稱對象x擁有屬性a, 或者屬性a被對象x擁有。

定義2[2]設(G,M,I)為一個形式背景, X ? G, A ?M。 一對算子被定義如下,*: P(G) →P(M), X*={a∈ M | ?x∈ X, (x, a)∈ I};*: P(M) →P(G), A*={x∈ G | ?a∈ A, (x, a)∈ I}。

定義3[2]設(G,M,I)為一個形式背景, 如果二元組(X,A)滿足X*=A并且A*=X, 稱(X,A)是一個概念。 X叫作概念的外延,A叫作概念的內涵。

用L(G,M,I)表示由形式背景(G,M,I)生成的所有概念的集合。 對于(X1, A1), (X2, A2)∈L(G, M, I) 定義其偏序關系為

(X1,A1)≤(X2,A2)X1?X2A1?A2。

其中,下確界和上確界分別為:

(X1, A1)∧ (X2, A2)=(X1∩ X2, (A1∪A2)**),

(X1, A1) ∨ (X2, A2)=((X1∪X2)**, A1∩ A2)，

則L(G,M,I)是一個完備格,稱為概念格。

定義4[12]設L(G,M,I)與L(G,N,J)是兩個概念格, 如果對于任意(X,A)∈L(G,N,J), 總存在(Y, B)∈L(G,M,I), 使得X=Y, 則稱L(G,M,I)細于L(G,N,J)。 記作L(G,M,I)≤L(G,N,J)。

定義5[12]設(G,M,I)與(G,N,J)是兩個形式背景, 則稱(G, M, I, N, J)是一個決策形式背景。 若L(G,M,I)≤L(G,N,J), 稱決策形式背景是協(xié)調的。

定義6[12]設 L(G, M, I) ≤ L(G, N, J), 若對于Y ≠?, U, 有(X, A) ∈ L(G, M, I), (Y, B) ∈ L(G, N, J), 且X ?Y, 則稱A → B是一個規(guī)則, 記作ifA,thenB。

定義7[21]設 (G, M, I) 是一個形式背景。 對于X ? G, A ?M, 一對負算子被定義為:

其中Ic=(G×M)-I。

用NL(G, M, I) 表示由形式背景 (G, M, I) 在負算子下生成的所有概念的集合, 并且NL(G, M, I)在上述 “≤” 偏序關系下也是一個完備格[21]。

若 (G, M, I) 是一個形式背景, 稱 (G, M, Ic) 是背景 (G, M, I) 的補背景[2]。

1.2三支概念分析

本節(jié)給出由屬性導出的三支概念格的相關定義與性質。

定義8[21]設 (G, M, I) 是一個形式背景, X ? G, A?M, 三支算子被定義如下:

≤: P(G) →DP(M),

≤: P(M)→DP(G), A≤=(A*,

三支算子的逆運算被定義如下:

≥:DP(M) →P(G)。

三支算子的諸多性質在文獻[21] 中有詳細介紹, 并由此產生了三支概念的定義。

定義9[21]設 (G, M, I) 是一個形式背景。 ((X, Y), A) 叫作由屬性導出的三支概念, 簡稱AE-概念, 當且僅當 (X, Y)≥=A且A≤=(X, Y)。 其中X, Y?G, A ?M。 (X, Y) 叫作AE-概念的外延, A叫作AE-概念的內涵。

對于((X, Y),A), ((Z, W),B), 定義其偏序關系如下[22]:

用AEL(G, M, I)表示由形式背景 (G, M, I) 生成的所有AE-概念的集合, 并且AEL(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 )。

2　基于屬性導出的三支概念格的規(guī)則提取

本節(jié)給出決策形式背景基于屬性導出三支概念格規(guī)則的提取方法, 為此先給出屬性導出的三支概念格之間細于關系的定義。

2.1基本概念

定義10設AEL(G, M, I) 與AEL(G, N, J) 是兩個由屬性導出的三支概念格。 若?((Z, W), B)∈ AEL(G, N, J), ?((X, Y), A)∈ AEL(G, M, I), 使得(X, Y)=(Z, W), 即X=Z 且Y=W, 則稱AEL(G, M, I) 細于AEL(G, N, J), 記作AEL(G, M, I) ≤ AEL(G, N, J)。

例1表1 所示的 (G, M1, I1, N1, J1) 是一個決策形式背景, 其屬性導出的三支概念格AEL(G, M1, I1) 和AEL(G, N1, J1) 分別如圖 1 和圖 2 所示。 不難看出 AEL(G, M1, I1) ≤ AEL(G, N1, J1)。

表1　決策形式背景(G, M1, I1, N1, J1)

圖1　AEL(G, M1, I1)Fig.1　AEL(G, M1, I1)

圖2　AEL(G, N1, J1)Fig.2　AEL(G, N1, J1)

定義11設(G, M, I, N, J) 是一個決策形式背景, AEL(G, M, I) ≤ AEL(G, N, J)。 若對于(Z, W) ≠ (?,?), (G, G), 有((X, Y), A) ∈ AEL(G, M, I), ((Z, W), B)∈ AEL(G, N, J), 滿足 (X, Y)?(Z, W), 即X ? Z且Y ?W, 則稱A → B是一個規(guī)則, 記為ifA,thenB。

例2(續(xù)例1) 由例1可知, ((24, 13), d) ∈AEL(G, M1, I1), ((24, 13), g)∈AEL(G, N1, J1), (24, 13)=(24, 13), 根據定義11, 可得規(guī)則d → g。 ((24, 1), de) ∈ AEL(G, M1, I1), ((24, 13), g) ∈AEL(G, N1, J1), (24, 1) ? (24, 13), 可得規(guī)則de → g。

屬性導出的三支概念的外延由原背景概念的外延與補背景概念的外延共同構成[21-22]。 定義11表明, 規(guī)則A → B是在兩個背景中同時成立的, 它既表示如果對象子集共同擁有屬性子集A中的所有屬性, 那么這個對象子集就共同擁有屬性子集B中的所有屬性, 又表示對象子集如果共同不擁有屬性子集A中的所有屬性, 那么這個對象子集就共同不擁有屬性子集B中的所有屬性。

例2中的規(guī)則d → g表示: 對象集{2,4}共同擁有屬性d, 它也共同擁有屬性g, 對象集{1,3}共同不擁有屬性d, 它也共同不擁有屬性g。

在例2中獲取的規(guī)則d → g和de → g, d → g一定能推出de→g。 為了描述de→g這類規(guī)則, 給出冗余規(guī)則的定義。

定義12 設 (G, M, I, N, J) 是一個決策形式背景, AEL(G, M, I) ≤ AEL(G, N, J)。 B → C與B′→ C′是屬性導出的三支格下的兩個規(guī)則, 若B ?B′, C′?C, 則稱規(guī)則B → C蘊含B′→ C′, 并稱B′→ C′是冗余的。

2.2決策形式背景基于屬性導出三支概念格的協(xié)調性

定義13 設 (G, M, I, N, J) 是一個決策形式背景, 若AEL(G, M, I) ≤ AEL(G, N, J), 則稱該背景是基于屬性導出三支概念格協(xié)調的。

例3(續(xù)例1)由圖1和圖2可知AEL(G, M1, I1) ≤ AEL(G, N1, J1), 所以 (G, M1, I1, N1, J1) 是基于屬性導出三支概念格協(xié)調的。

文獻 [22] 證明了以下結論:

引理1設 (G, M, I) 是一個形式背景, 則存在保序嵌入 φ: L(G, M, I) → AEL(G, M, I) 以及保序嵌入 ψ: NL(G, M, I)→AEL(G, M, I)。

利用這一結果我們給出基于屬性導出三支概念格協(xié)調性與背景協(xié)調性的關系:若決策形式背景是基于屬性導出三支概念格協(xié)調的,則它一定是協(xié)調的。

定理1設 (G, M, I, N, J) 是一個決策形式背景, 且AEL(G, M, I) ≤ AEL(G, N, J), 則L(G, M, I) ≤ L(G, N, J)。

下例表明,定理1的逆命題是不成立的,即如果一個決策形式背景是協(xié)調的,它不一定是基于屬性導出三支概念格協(xié)調的。

例4表2表示決策形式背景(G, M2, I2, N2, J2), 圖3和圖4分別表示 L(G, M2, I2) 和 L(G, N2, J2)。 由定義4知 L(G, M2, I2) ≤ L(G, N2, J2), 故背景協(xié)調。 圖5和圖6分別表示 AEL(G, M2, I2) 和 AEL(G, N2, J2)。 可以看出對于 ((4, 123), k) ∈ AEL(G, N2, J2), 在 AEL(G, M2, I2)中并無與之外延相同的AE-概念, 即 AEL(G, M2, I2) ≤ AEL(G, N2, J2) 不成立, 故背景不是基于屬性導出三支概念格協(xié)調的。

表2　決策形式背景(G, M2, I2, N2, J2)

2.3決策形式背景在兩種格下的規(guī)則比較

本節(jié)給出在屬性導出的三支概念格下的規(guī)則提取方法,并將結果與在概念格下獲取的規(guī)則(定義6下獲取的規(guī)則)進行比較。

圖3　L(G, M2, I2)Fig.3　L(G, M2, I2)

圖4　L(G, N2, J2)Fig.4　L(G, N2, J2)

圖5　AEL(G, M2, I2)Fig.5　AEL(G, M2, I2)

圖6　AEL(G, N2, J2)Fig.6　AEL(G, N2, J2)

定理2設(G, M, I, N, J)是一個決策形式背景,且 AEL(G, M, I) ≤ AEL(G, N, J)。 R表示決策形式背景在概念格下生成的所有規(guī)則的集合,TRa表示基于屬性導出的三支格下生成的所有規(guī)則的集合,則R ?TRa。

例5(續(xù)例1) 根據定義11,可得決策背景(G, M1, I1, N1, J1)在AEL格下的全部規(guī)則TRa如表3所示。 概念格下獲取的規(guī)則R如表4所示。顯然R ? TRa。

表3　TRa規(guī)則

表4　R規(guī)則

根據定理2, 基于屬性導出的三支格下的規(guī)則包含決策背景的所有規(guī)則。 更進一步,對于決策背景的某些規(guī)則,還可以在屬性導出的三支規(guī)則下找出比之前件更少的規(guī)則,即可以用更少的條件獲得同樣的決策結果。

定理3設(G, M, I, N, J)是一個決策形式背景,且AEL(G, M, I) ≤ AEL(G, N, J)。 ?A → B∈R,總存在C → B ∈TRa, 且 C ? A。

下例通過非冗余規(guī)則比較,結果會更明顯。

例6(續(xù)例1)表5和表6分別表示決策形式背景(G, M1, I1, N1, J1)的TRa非冗余規(guī)則和背景的R非冗余規(guī)則。 對于原決策背景的非冗余規(guī)則de→g以及abcef→hk, 存在AEL格下的非冗余規(guī)則d→g以及abcf→hk, 滿足j5i0abt0b ? {de}, {abcf} ? {abcef}。

表5　TRa非冗余規(guī)則

表6　R非冗余規(guī)則

2.4決策形式背景的補背景在兩種格下的規(guī)則比較

本節(jié)利用上述三支規(guī)則提取方法提取決策形式背景(G, M, Ic, N, Jc)的規(guī)則。 為此,首先給出決策背景補背景的定義。

定義14設(G, M, I, N, J)是一個決策形式背景,稱決策形式背景(G, M, Ic, N, Jc)為背景(G, M, I, N, J)的補背景。

類似于2.2節(jié)與2.3節(jié)決策形式背景(G, M, I, N, J)的有關性質,其補背景(G, M, Ic, N, Jc)有如下結論。

定理4設(G, M, I, N, J)是一個決策形式背景, 且AEL(G, M, I) ≤ AEL(G, N, J), 則背景L(G, M, Ic) ≤ L(G, N, Jc)。

定理5設(G, M, I, N, J)是一個決策形式背景,且AEL(G, M, I) ≤ AEL(G, N, J)。 Rc表示由補背景在概念格下生成的所有規(guī)則的集合, TRa表示在屬性導出的三支格下生成的所有規(guī)則的集合,則Rc? TRa。

定理6設(G, M, I, N, J)是一個決策形式背景,且AEL(G, M, I) ≤ AEL(G, N, J)。 ?A→B ∈ Rc,總存在C → B ∈TRa, 且C ? A。

由定理2和定理5可得如下結論:

定理7設(G, M, I, N, J)是一個決策形式背景,且AEL(G, M, I) ≤ AEL(G, N, J)。 則R ∪ Rc? TRa。

3　結　語

本文主要給出了基于屬性導出的三支概念格下決策形式背景協(xié)調的定義, 研究了基于屬性導出三支概念格下的規(guī)則獲取; 討論了在屬性導出的三支概念格下獲取的規(guī)則與決策形式背景在概念格下規(guī)則的關系, 并在理論上證明了利用屬性導出的三支概念格對決策形式背景的補背景提取規(guī)則的可行性, 豐富了三支概念分析規(guī)則獲取的內容。

事實上,決策形式背景的補背景的實際意義有其一定的復雜性與難解釋性。因此,我們將在本文的基礎上繼續(xù)研究決策形式背景的補背景及其三支規(guī)則具有的意義,并且進一步探討基于對象導出的三支概念格下對決策形式背景進行三支規(guī)則提取的方法，發(fā)掘其與本文獲取的三支規(guī)則以及原規(guī)則的不同之處。

[1]WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//. RIVAL I, ed. Ordered Sets. Reidel: Dordrecht-Boston, 1982, 445-470.

[2]GANTER B, WILLE R. Formal Concept Analysis[M].Mathematical Foundations. New York: Springer-verlag, 1999.

[3]PAWLAK Z. Rough Sets[J].International Journal of Computer and Information Sciences, 1982, 11: 341-356.

[4]魏玲,萬青,錢婷，等.三元概念分析綜述[J]. 西北大學學報:自然科學版, 2014, 44(5): 689-699.

[5]YAO Y Y. Concept lattices in rough set theory[C]//. DICK S, KURGAN L, PEDRYCZ W and REFORMAT M (Eds.), Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS 2004). IEEE Catalog Number: 04TH8736, June 27-30, 2004, 796-801.

[6]YAO Y Y, CHEN Y H. Rough set approximations in formal concept analysis[C]//. DICK S, KURGAN L, PEDRYCZ W and REFORMAT M (Eds.), Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS 2004), IEEE Catalog Number: 04TH8736, June 27-30, 2004, 73-78.

[7]張文修, 姚一豫, 梁怡. 粗糙集與概念格[M]. 西安: 西安交通大學出版社, 2006.

[8]張文修, 仇國芳. 基于粗糙集的不確定決策[M]. 西安: 西安交通大學出版社, 2006.

[9]王國胤. Rough集理論與知識獲取[M]. 西安: 西安交通大學出版社, 2001.

[10] 張文修, 梁怡, 吳偉志. 信息系統(tǒng)與知識發(fā)現(xiàn)[M]. 北京: 科學出版社, 2003.

[11] 張文修, 米據生, 吳偉志. 不協(xié)調目標信息系統(tǒng)的知識約簡[J]. 計算機學報, 2003, 26(1): 12-18.

[12] 魏玲, 張文修. 粗糙集與概念格的約簡理論與方法[D]. 西安: 西安交通大學, 2005.

[13] 張文修, 魏玲, 祁建軍. 概念格的屬性約簡理論與方法[J]. 中國科學E輯: 信息科學, 2005, 35(6): 628-639.

[14] 魏玲, 祁建軍, 張文修. 決策形式背景的概念格屬性約簡[J]. 中國科學E輯: 信息科學, 2008, 38(2): 195-208.

[15] LI J H, MEI C L, LV Y J. Incomplete decision contexts: Approximate concept construction, rule acquisition and knowledge reduction[J]. International Journal of Approximate Reasoning, 2013, 54(1): 149-165.

[16] 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-4454.

[17] 張清華, 王國胤, 劉顯全. 基于最大粒的規(guī)則獲取算法[J]. 模式識別與人工智能, 2012, 25(3): 388-396.

[18] 朱治春, 魏玲. 基于類背景的雙向規(guī)則的獲取[J]. 西北大學學報: 自然科學版, 2015, 45(4): 517-524.

[19] 李金海, 呂躍進. 基于概念格的決策形式背景屬性約簡及規(guī)則提取[J]. 數學實踐與認識, 2007, 39(7): 182-188.

[20] YAO Y Y. Three-way decision: An interpretation of rules in rough set theory[C]//WEN P, LI Y, POLKOWSKI L, et al. (eds.) RSKT, 2009, 5589: 642-649.

[21] QI J J, WEI L, YAO Y Y. Three-way formal concept analysis[J]. Lecture Notes in Computer Science, 2014, 8818: 732-741.

[22] QI J J, QIAN T, WEI L. The connections between three-way and classical lattices[J]. Knowledge-Based Systems, 2016, 91: 143-151.

(編輯亢小玉)

Rules extraction in formal decision contexts based on attribute-Induced three-way concept lattices

LIU Lin, QIAN Ting, WEI Ling

(School of Mathematics, Northwest University, Xi′an 710127， China)

This paper puts forward a method of rule extraction based on attribute-induced three-way concept lattice in a formal decision context. For this purpose, the finer relation is defined between two attribute-induced three-way concept lattices under which the consistence of formal decision context is given. Then approaches to rule extraction in formal decision context are obtained, and the relationship between the new rules with the rules based on concept lattices is discussed. Finally, a real example is used to demonstrate both its feasibility and effectiveness.

formal decision context; three-way concept lattices; three-way consistence; rules extraction

2016-03-04

國家自然科學基金資助項目(11371014，11071281)

劉琳，女，河南商丘人，從事形式概念分析、統(tǒng)計學研究。

魏玲，女，陜西楊陵人，西北大學教授，博士生導師，從事形式概念分析研究。

O29,TP18

A

10.16152/j.cnki.xdxbzr.2016-04-003