-
作为形式概念分析(FCA)的核心数据结构,概念格刻画了概念之间的泛化和例化关系,在数据挖掘、机器学习和信息检索等领域取得了广泛的应用[1]。近年来,概念格研究取得了很多重要的成果,特别是文献[2]提出粗糙集框架下的概念格理论以来,一些学者借鉴粗糙集理论深入研究概念格的属性约简和规则提取等问题。文献[3-6]研究了粗糙集与信息系统的属性约简和规则提取问题,文献[7-10]探讨了粗糙集与概念格的属性约简理论以及基于概念格的决策形式背景规则获取问题。文献[11-12]针对不完备决策形式背景,研究了相应的近似概念构造、规则提取以及知识约简。
作为二支决策的推广,三支决策(3-way decisions)是文献[13]提出的一种新的决策理论框架,它将决策问题分为三类:接收、拒绝和不承诺。传统的形式概念分析仅支持二支决策,实际构造形式概念时,仅仅考虑“某些对象共同具有哪些属性”或“某些属性为哪些对象所共同具有”,而没有同时考虑“某些对象共同不具有哪些属性”或“某些属性为哪些对象所共同不具有”。为了更好地支持实际应用中的复杂决策问题,文献[14-15]引入三支决策思想,将具有二支决策的形式概念分析推广为支持三支决策的三支概念分析(3-way concept analysis),提出了两种具体的三支概念格(对象导出三支概念格和属性导出三支概念格),并研究了它们与经典概念格之间的关系。
自文献[14]提出三支概念格以来,就引起了有关学者的关注,并取得了一些初步的研究成果。文献[16]对概念格与三支决策相结合的研究历程、研究内容以及研究展望进行了系统的综述。目前,这些工作主要集中在基于三支概念格的属性约简方面[17],在基于三支概念格的规则提取方面则偏少。文献[18]在利用三支概念格进行规则提取方面做了有益的尝试,给出了基于属性导出三支概念格的决策背景规则提取方法,并通过与经典概念格下的生成规则进行比较,表明了基于属性导出三支概念格的决策背景规则提取方法的有效性和优越性。
本文在文献[18]的基础上进一步研究基于对象导出三支概念格的规则提取,并与经典概念格及属性导出三支概念格下的生成规则进行比较。同时通过对象导出三支概念格和属性导出三支概念格的合并,进一步改善三支概念格下的生成规则质量。
HTML
-
文献[18]给出基于属性导出三支概念格的决策背景规则提取方法,本文在其基础上进一步研究基于对象导出三支概念格的规则提取,并与经典概念格及属性导出三支概念格下的规则提取进行比较。
-
先定义对象导出三支概念格之间的细于关系,以及决策背景基于对象导出三支概念格的协调性。
定义11 设OEL(G, M, I)与OEL(G, N, J)是对象导出三支概念格,若对于任意(Y, (C, D))∈OEL(G, N, J),存在(X, (A, B))∈OEL(G, M, I),使得X=Y,则称OEL(G, M, I)细于OEL(G, N, J),记作OEL(G, M, I)≤ OEL(G, N, J),并称决策背景(G, M, I, N, J)是基于对象导出三支概念格协调的。
例1:表 1是一个决策形式背景[18],G={1, 2, 3, 4},M={a, b, c, d, e, f},N={g, h, k},其对象导出三支概念格OEL(G, M, I)和OEL(G, N, J)分别如图 1、图 2所示。
G a b c d e f g h k 1 × × × 2 × × × × × 3 × × × × × × × 4 × × × 由图 1、图 2可以看出,OEL(G, M, I)≤OEL (G, N, J),所以表 1所示决策背景是基于对象导出三支概念格协调的。
接着定义对象导出三支概念格下的生成规则。
定义12 设决策背景(G, M, I, N, J)是基于对象导出三支概念格协调的,若对于X、Y≠ $ \mathit{\emptyset} $ ,G,有(X, (A, B))∈OEL(G, M, I), (Y, (C, D))∈OEL(G, N, J), 且X=Y,则称A→C和B→D分别是一个规则。
例2:根据定义12,表 1所示决策背景在对象导出三支概念格下的生成规则集合TRo为:
d→g;de→g;ab→h;abc→h;f→k;def→gk;abde→gh;abcf→hk;abcef→hk
-
定义13 设决策背景(G, M, I, N, J)是协调的,若对于X, Y≠$ \mathit{\emptyset} $, G,有(X, A)∈L(G, M, I),(Y, B)∈L(G, N, J),且X=Y,则称A→B是一个规则。
例3:表 1所示决策背景的概念格L(G, M, I)和L(G, N, J)分别如图 3、图 4所示。
根据定义13,表 1所示决策背景在经典概念格下的生成规则集合R为:de→g;f→k;def→gk;abcef→hk
-
定理3 设(G, M, I, N, J)是决策形式背景,且OEL(G, M, I)≤OEL(G, N, J)。R表示经典概念格下的生成规则集合,TRo表示对象导出三支概念格下的生成规则集合,则R$\subseteq $TRo
证明:对任意A→B∈R,由定义13,存在(X, A)∈L(G, M, I),(Y, B)∈L(G, N, J),且X=Y。又因为OEL(G, M, I)≤OEL(G, N, J),由定义11,对于(Y, (B, Y*-J))∈OEL(G, N, J),存在(X, (C, X*-I))∈OEL(G, M, I)。由于C=X* I=A,所以(X, (C, X*-I))即(X, (A, X*-I))。由定义12,A→B∈TRo,因此R$\subseteq $TRo
例4:比较表 1所示决策背景分别在对象导出三支概念格及经典概念格下的生成规则集合TRo和R,可以看出,TRo不仅包含了R中每条规则,还包含了ab→h;abde→gh等其他更多规则。
定理4 设(G, M, I, N, J)是决策形式背景,且OEL(G, M, I)≤OEL(G, N, J),R表示经典概念格下的生成规则集合,TRo表示对象导出三支概念格下的生成规则集合,则对于A→B∈R,总存在C→B∈TRo,且C$\subseteq $A。
证明:对任意A→B∈R,由定义13,存在(X, A)∈L(G, M, I),(Y, B)∈L(G, N, J),且X=Y。由于存在保序嵌入[15] $\varphi $ :L(G, M, I)→OEL(G, M, I),$\varphi $:L(G, N, J)→ OEL(G, N, J),使$\varphi $((X, A))=(X, (A, X*-I)),$\varphi $((Y, B))= (Y, (B, Y*-J)),且OEL(G, M, I)≤OEL(G, N, J),因此对于(Y, (B, Y*-J))∈OEL(G, N, J),存在(Y, (C, Y*-I))∈OEL (G, M, I),使得C→B∈TRa。又因为Y=C* I$ \cap $Y*- I *-I ,所以Y$\subseteq $C* I,进而C$\subseteq $Y* I=X* I=A,即C$\subseteq $A。
例5:比较表 1所示决策背景分别在对象导出三支概念格及经典概念格下的生成规则集合TRo和R,可以看出,对于R中的每条规则A→B,在TRo中总存在相应的规则C→B,且C$\subseteq $A。
与经典概念格下的生成规则比较,对象导出三支概念格下的生成规则更为丰富也更为精炼。但是,由于对象导出三支概念格比经典概念格的概念数量更多,结构也更为复杂,因此构建对象导出三支概念格比构建经典概念格要付出更多的时间开销。
-
定义14 设决策背景(G, M, I, N, J)是基于属性导出三支概念格协调的,若(X, Y)、(Z, W) ≠($ \mathit{\emptyset} $, $ \mathit{\emptyset} $)、(G, G),有((X, Y), A)∈AEL(G, M, I),((Z, W), B)∈AEL(G, N, J),且X=Z、Y$\subseteq $W,则称A→B是一个规则。
例6:表 1所示决策背景的属性导出三支概念格AEL(G, M, I)和AEL(G, N, J)如图 5、图 6所示。
根据定义14,表 1所示决策背景在属性导出三支概念格下的生成规则集合TRa为:
d→g;de→g;ab→h;abe→h;abc→h;abcf→h;abcef→h;f→k;def→gk;abde→gh;abcf→hk;abcef→hk
-
先定义对象导出三支概念格与属性导出三支概念格之间的细于关系,以及决策背景基于对象导出三支概念格和属性导出三支概念格的协调性。
定义15 设(G, M, I)是形式背景,若对于任意(X, (A, B))∈OEL(G, M, I),存在((Y, Z), C)∈AEL (G, M, I),使得X=Y或Z,则称AEL(G, M, I)细于OEL(G, M, I),记作AEL(G, M, I)≤OEL(G, M, I),并称形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的。
例7:由定义15,对于图 1所示对象导出三支概念格OEL(G, M, I),图 5所示属性导出三支概念格AEL(G, M, I),有AEL(G, M, I)≤OEL(G, M, I),所以形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的;类似地,对于图 2所示对象导出三支概念格OEL(G, N, J),图 4所示属性导出三支概念格AEL(G, N, J),有AEL(G, N, J)≤OEL(G, N, J),所以形式背景(G, N, J)是基于AEL(G, N, J)和OEL(G, N, J)协调的。
接下来,给出相应的规则定义。
定义16 设形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的,若对于X≠$ \mathit{\emptyset} $、G,(Y, Z)≠($ \mathit{\emptyset} $, $ \mathit{\emptyset} $)、(G, G),有(X, (A, B))∈OEL(G, M, I),((Y, Z), C)∈AEL(G, M, I),且X=Y或Z,则称A→B是一个规则。
在上述定义的基础上,以下比较对象导出三支概念格与属性导出三支概念格下的生成规则。
定理5 设(G, M, I, N, J)是决策背景,且AEL (G, M, I)≤AEL(G, N, J),OEL(G, M, I)≤OEL(G, N, J), AEL(G, M, I)≤OEL(G, N, J),则TRo$\subseteq $TRa
证明:对于任意A→B∈TRo,由定义12,存在(X, (A, C)∈OEL(G, M, I),(X, (B, D)∈OEL(G, N, J)。因为AEL(G, M, I)≤OEL(G, N, J),因此对于(X, (B, D)∈OEL(G, N, J),存在((X, Z), A)或((Y, X), A)∈AEL(G, M, I)。又因为AEL(G, N, J)≤OEL(G, N, J),所以(X, (B, D)∈OEL(G, N, J)等价于((X, Z), A)或((Y, X), A)∈AEL(G, N, J),因此对于((X, Z), A)或((Y, X), A)∈AEL(G, N, J),存在((X, Z), A)或((Y, X), A)∈AEL(G, M, I)。因此A→B∈TRa,即TRo$\subseteq $TRa
例8:比较表 1所示决策背景分别在对象导出三支概念格及属性导出三支概念格下的生成规则集合TRo和TRa,可以看出,TRa不仅包含了TRo中每条规则,还包含了abe→h;abcf→h;abcef→h等规则。
通过与属性导出三支概念格下的生成规则进行比较,可以看出,属性导出三支概念格下的生成规则更为丰富。但是,属性导出三支概念格比对象导出三支概念格生成了更多的冗余规则,如图 5、图 6所示属性导出三支概念格生成了de→g、abc→h、abe→h、abcf→h、abcef→h、abcef→hk等6条冗余规则,而图 1、图 2所示对象导出三支概念格只生成了de→g、abc→h、abcef→hk等3条冗余规则。因此,在支持决策分析方面,属性导出三支概念格的能力要稍弱于对象导出三支概念格。