形式概念分析(formal concept analysis,FCA)由德国数学家Wille于1982年首次提出[1],此后由Ganter等[2]多位学者逐步发展完善。FCA是基于形式背景进行数据分析的有力工具,目前已发展成为自身理论与交叉研究均较为成熟的科学理论。近年来,FCA在构建概念格[3]、属性约简[4]、规则获取[5]和知识发现[6-7]等方面取得诸多成果。
魏玲等[8-9]于2018年提出了保持形式背景的二元关系不变的概念约简理论。目前,概念约简已引起相关领域学者的关注。王霞等[10]通过构造概念可辨识矩阵找出所有概念约简;谢小贤等[11]研究了基于布尔矩阵的概念约简问题;Zhao等[12]给出了基于代表概念矩阵的概念约简方法;魏玲等[13]研究了对称形式背景及其概念约简问题;李炎等[14]探讨了保持规则前件信息的概念约简问题;朱朵朵等[15]给出了基于不完备背景的3类SE-ISI概念约简获取理论与方法;于亚琪等[16]研究了面向属性概念格的概念约简及其在知识空间理论中的应用。
Wille和Lehmann于1995年提出了三元概念分析(triadic concept analysis,TCA)[17-18]。TCA的数据基础是三元背景,可形式化表示为由对象集、属性集、条件集,以及三者间三元关系形成的四元组。Wille在三元背景上定义了对象集、属性集和条件集之间的诱导算子,并由此生成三元概念。三元概念将形式概念从二维空间推广至三维空间,通过增加条件维度来描述在一定条件下一个对象与一个属性之间是否存在具有关系。
近年来,国内学者们开始关注三元概念分析。魏玲等[19-20]对三元概念分析的研究工作进行了梳理并研究了三元背景基于二元关系不变的约简问题;祁建军等[21]给出了关于三元背景及概念三元格的简化方法;王霞等[22-23]给出了三元概念的一种构造方法并研究了基于条件属性蕴含的概念格构造及简化问题;李俊余等[24-25]探讨了三元概念与形式概念的关系并提出了基于三元因子分析的三元概念约简问题,给出了验证一个三元概念集合是否为三元概念约简的方法;李萱等[26]讨论了三元概念约简与概念约简的关系;王啸等[27]给出了基于待选集的三元概念构造方法。
李俊余等[25]提出的三元因子分析法即利用三元因子分析来验证给定的三元概念集合是否为一个三元概念约简,该方法虽然可以探讨三元概念约简问题,但是无法直接得到所有的三元概念约简。Zhao等[12]在形式背景中提出了基于代表概念矩阵求解所有概念约简的方法。受该方法的启发,本文将三元背景中的三元关系和三元概念之间的联系以矩阵的形式直观呈现,定义了代表三元概念矩阵,并基于代表三元概念矩阵给出了三元概念约简的求解方法。进一步,对代表三元概念矩阵进行简化,提出了最小代表三元概念矩阵,并从最小代表三元概念矩阵的角度分别给出了核心、相对必要和绝对不必要三元概念的特征。本文提出的方法能够直接获取所有的三元概念约简,丰富了三元概念分析及三元概念约简的理论研究。
1 预备知识
本节给出三元概念分析的相关基础知识。
定义1[17] 称(K1,K2,K3,Y)为三元背景,其中K1、K2、K3为非空集合,Y为K1、K2和K3之间的三元关系,即Y⊆K1×K2×K3。称K1、K2、K3分别为对象集、属性集和条件集,K1、K2、K3的元素分别为对象、属性和条件。若对象g、属性m和条件b具有关系Y,则记为(g,m,b)∈Y,表示对象g在条件b下具有属性m。
定义2[17] 设K=(K1,K2,K3,Y)为三元背景,{i,j,k}={1,2,3}且j<k。∀X⊆Ki,Z⊆Kj×Kk,定义(i)-诱导算子如下:
X(i)={(aj,ak)∈Kj×Kk|(ai,aj,ak)∈Y,∀ai∈X},
Z(i)={ai∈Ki|(ai,aj,ak)∈Y,∀(aj,ak)∈Z}。
定义3[17] 设K=(K1,K2,K3,Y)为三元背景,Ai⊆Ki,i=1,2,3。若满足Ai=(Aj×Ak)(i),其中{i,j,k}={1,2,3}且j<k,则称(A1,A2,A3)为三元背景K的三元概念,并称A1为外延,A2为内涵,A3为方式。
定义4[25] 设K=(K1,K2,K3,Y)为三元背景,T(K)是K的所有三元概念构成的集合,R⊆T(K)。若
Y= A1×A2×A3,
则称R为保持三元背景K不变的三元概念协调集。若进一步∀(A1',A2',A3')∈R都有
Y≠ A1×A2×A3,
则称R为保持三元背景K不变的三元概念约简。
定义5[25] 设K=(K1,K2,K3,Y)为三元背景,T(K)是K的所有三元概念构成的集合,{Ri|i∈τ,τ为指标集}为K的所有三元概念约简的集合,三元概念可分为以下三类:
1)核心三元概念集C= Ri;
2)相对必要三元概念集K= Ri- Ri;
3)绝对不必要三元概念集U=T(K)- Ri。
例1 表1给出三元背景K=(K1,K2,K3,Y),其中对象集K1={1,2,3,4,5,6},属性集K2={a,b,c,d,e,f},条件集K3={A,B,C}。
表1 三元背景K=(K1,K2,K3,Y)Tab.1 A triadic context K=(K1,K2,K3,Y) |
| 对象 | A | B | C | ||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | d | e | f | a | b | c | d | e | f | a | b | c | d | e | f | ||||||||||||||||||
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||||||||||||
| 2 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | |||||||||||||||||
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |||||||||||||||||
| 4 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||||||||
| 5 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||||||||
| 6 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | |||||||||||||||||
根据定义3计算出该三元背景的三元概念如下:
N1=({1,2,3,6},{c},K3),
N2=({2,3},{b,c,d,f},K3),
N3=({3},{a,b,c,d,f},{A,B}),
N4=({3,4,5},{a,b,d,f},{A,B}),
N5=({2,3,6},{c,d,e},K3),
N6=({4,5},K2,{B,C}),
N7=({2,3,4,5},{b,d,f},K3),
N8=({2,3,4,5,6},{d,f},K3),
N9=(K1,∅,K3),
N10=(K1,{c,d},{B,C}),
N11=({2,3,4,5,6},{b,c,d,f},{B,C}),
N12=(∅,K2,K3),
N13=({3,4,5,6},K2,{B}),
N14=({2,4,5,6},{a,b,c,d,f},{C}),
N15=(K1,K2,∅),
N16=({3,4,5},{b,c,d,e,f},{B,C}),
N17=({4,5},{a,b,d,f},K3),
N18=({4,5,6},{a,b,c,d,f},{B,C})。
根据定义4可找到该三元背景的三元概念约简分别为
R1={N1,N2,N4,N5,N10,N13,N14,N16},
R2={N1,N2,N4,N8,N10,N13,N14,N16},
R3={N1,N4,N5,N7,N10,N13,N14,N16},
R4={N1,N4,N7,N8,N10,N13,N14,N16},
R5={N1,N2,N3,N5,N10,N13,N14,N16,N17},
R6={N1,N3,N5,N7,N10,N13,N14,N16,N17},
R7={N1,N2,N3,N8,N10,N13,N14,N16,N17},
R8={N1,N3,N7,N8,N10,N13,N14,N16,N17}。
根据定义5,该三元背景的三元概念分类如下:
核心三元概念集C={N1,N10,N13,N14,N16},
相对必要三元概念集K={N2,N3,N4,N5,N7,N8,N17},
绝对不必要三元概念集U={N6,N9,N11,N12,N15,N18}。
2 基于代表三元概念矩阵的三元概念协调集的判定
本节通过定义三元组(g,m,b)∈Y的代表三元概念来识别具有(g,m,b)关系的三元概念,并给出构造代表三元概念矩阵和获取三元概念约简的方法。
定义6 设K=(K1,K2,K3,Y)为三元背景,|K1|=p,|K2|=q,|K3|=r,T(K)是K的所有三元概念构成的集合。∀(g,m,b)∈Y,(A1,A2,A3)∈T(K),若(g,m,b)∈A1×A2×A3,则称(A1,A2,A3)为三元组(g,m,b)的代表三元概念;称
REP((g,m,b))=
为(g,m,b)的代表三元概念集;称Λ=(REP((g,m,b)),(g,m,b)∈K1×K2×K3)为K的代表三元概念矩阵,该矩阵表示为Λ=Λ1|Λ2…|Λr,其中任一Λk(k=1,2,…,r)为p×q阶的矩阵。
例2(续例1) 根据定义6给出三元背景K的代表三元概念矩阵Λ,Λ=Λ1|Λ2|Λ3,其中,
Λ1=
,
Λ2=
,
Λ3=
。
事实上,只有非空REP((g,m,b))能识别三元组(g,m,b)∈Y,因此下文也用Λ表示所有非空REP((g,m,b))构成的集合。由于非空REP((g,m,b))给出了能体现(g,m,b)关系的所有三元概念,因此从每个非空REP((g,m,b))中任选一个三元概念所形成的集合,就能保持三元关系Y不变。由此,给出三元概念协调集的判定定理。
定理1 设K=(K1,K2,K3,Y)为三元背景,T(K)是K的所有三元概念构成的集合。对于R⊆T(K),R≠∅,下列命题等价:
1)R是三元概念协调集;
2)∀(g,m,b)∈Y,R∩REP((g,m,b))≠∅;
3)∀D⊆T(K),若R∩D=∅,则D∉Λ。
证明 1)⇒2)设R是三元概念协调集,则Y= A1×A2×A3,因此∀(g,m,b)∈Y,存在(A1,A2,A3)∈R使得(g,m,b)∈A1×A2×A3,即(A1,A2,A3)∈REP((g,m,b)),由此可得R∩REP((g,m,b))≠∅。
2)⇒1)∀(g,m,b)∈Y,由于R∩REP((g,m,b))≠∅,因此存在(A1,A2,A3)∈R使得(A1,A2,A3)∈REP((g,m,b)),(g,m,b)∈A1×A2×A3。由(g,m,b)的任意性可得
(A1×A2×A3)= {(g,m,b)}=Y,
即R是三元概念协调集。
2)⇒3)用反证法。假设D∈Λ,则存在(g0,m0,b0)∈Y使得REP((g0,m0,b0))=D,因此由2)知R∩D≠∅,这与3)的已知条件R∩D=∅矛盾,故D∉Λ。
3)⇒2)∀D⊆T(K),由R∩D=∅⇒D∉Λ可得D∈Λ⇒R∩D≠∅。因此∀(g,m,b)∈Y,由REP((g,m,b))∈Λ可得R∩REP((g,m,b))≠∅。
在定理1的基础上,结合定义4,可给出三元概念约简的判定定理。
定理2 设K=(K1,K2,K3,Y)为三元背景,T(K)是K的所有三元概念构成的集合。对于R⊆T(K),R≠∅,若下述条件成立:
1)∀(g,m,b)∈Y,R∩REP((g,m,b))≠∅;
2)∀(A1,A2,A3)∈R,存在(g0,m0,b0)∈Y使得(R\{(A1,A2,A3)})∩REP((g0,m0,b0))=∅;
则R是三元概念约简。
例3(续例2) 根据定理1和定理2判定一个三元概念集是否为三元概念协调集和三元概念约简。
令F1={N1,N2,N4,N5,N6,N10,N13,N14,N16},易得∀(g,m,b)∈Y,F1∩REP((g,m,b))≠∅,由定理1知F1是三元概念协调集。然而,对于F1\{N6}={N1,N2,N4,N5,N10,N13,N14,N16}和任意(g,m,b)∈Y,有F1\{N6}∩REP((g,m,b))≠∅,由定理2知F1不是三元概念约简。
令F2={N1,N2,N4,N5,N10,N13,N14,N16},∀(g,m,b)∈Y,F2∩REP((g,m,b))≠∅,由定理1知F2是三元概念协调集。同时,对于任意三元概念N∈F2,存在(g0,m0,b0)∈Y使得(F2\{N})∩REP((g0,m0,b0))=∅。比如,对于F2\{N1}={N2,N4,N5,N10,N13,N14,N16},存在{N1}∈Λ使得{N2,N4,N5,N10,N13,N14,N16}∩{N1}=∅。由定理2知F2是三元概念约简。
由于一个非空代表三元概念集中的任何三元概念都可反映该位置的三元关系,并且不同的非空代表三元概念集中的相同三元概念共同反映不同位置的三元关系,因此为了保持所有三元关系不变,只需找到包含关系下的极小代表三元概念集即可。由此,提出最小代表三元概念矩阵Λmin以简化代表三元概念矩阵。
定义7 设K=(K1,K2,K3,Y)为三元背景,Λ为K的代表三元概念矩阵。若∀REP((g,m,b))∈Λ,都不存在REP((g',m',b'))∈Λ,使得REP((g',m',b'))⊆REP((g,m,b)),则称Λ为K的最小代表三元概念矩阵,记为Λmin。
事实上,Λmin是由Λ中包含关系下的极小代表三元概念集构成的矩阵。下面给出最小代表三元概念矩阵与三元概念约简的关系。
定理3 设K=(K1,K2,K3,Y)为三元背景,{Ri|i∈τ,τ是指标集}是K的所有三元概念约简的集合,Λmin是K的最小代表三元概念矩阵,则∪i∈τRi= REP((g,m,b))。
证明 首先证明
∪i∈τRi⊆ REP((g,m,b))。
∀N∈∪i∈τRi,存在i0∈τ使得N∈ 。假设N∉ ∈ΛminREP((g,m,b)),则∀REP((g,m,b))∈Λmin,N∉REP((g,m,b))。由于 为三元概念约简,因此∀REP((g,m,b))∈Λmin,REP((g,m,b))∩ ≠∅。
又由于∀REP((g,m,b))∈Λmin,N∉REP((g,m,b)),因此
REP((g,m,b))∩( \{N})≠∅。
由定理1知 \{N}是三元概念协调集,因此 不是三元概念约简,与已知条件 是三元概念约简矛盾,故
N∈ REP((g,m,b))。
然后证明∪i∈τRi⊇ REP((g,m,b))。∀N∈ REP((g,m,b)),存在REP((g0,m0,b0))∈Λmin使得N∈REP((g0,m0,b0)),因此存在i0∈τ使得N∈ ,故N∈∪i∈τRi。
综合上述两方面可得
∪i∈τRi= REP((g,m,b))。
事实上,根据Λmin中所有非空元素的意义,可以得到获取所有三元概念约简的具体方法:从Λmin的每一个非空元素中任取一个三元概念构成的集合是三元概念协调集,其中极小的三元概念协调集就是三元概念约简。
例4(续例2) 根据定义7给出三元背景的最小代表三元概念矩阵Λmin如下。通过Λmin得到的所有三元概念约简同例1中通过定义4找到的8个三元概念约简一致。
Λmin=
。
由例2和例4可以看出,最小代表三元概念矩阵相较代表三元概念矩阵更加直观和清晰,相应地,三元概念约简的计算也更加简便。
算法1给出利用最小代表三元概念矩阵求解所有三元概念约简的方法。由于三元概念集的生成算法不影响最小代表三元概念矩阵的计算,因此算法1省略了生成三元背景K=(K1,K2,K3,Y)的三元概念集T(K)的相应步骤。事实上,可以使用任何现有的三元概念集生成算法作为算法1的前提条件。
| 算法1 基于最小代表三元概念矩阵的三元概念约简算法 输入: 三元背景K=(K1,K2,K3,Y)和三元概念集T(K)。 输出: 三元概念约简的集合RTC。 1)∀(g,m,b)∈Y,计算REP((g,m,b))={(A1,A2,A3)∈T(K)|(g,m,b)∈A1×A2×A3}。 2)计算Λ={REP((g,m,b))|(g,m,b)∈Y}。 3)计算Λmin={REP((g,m,b))∈Λ|不存在REP((g',m',b'))使得REP((g',m',b'))⊆REP((g,m,b))}。 4)输出 RTC= (A1,A2,A3)。 |
算法1中,计算代表三元概念矩阵Λ的时间复杂度为o(|K1|·|K2|·|K3|·|T(K)|),计算最小代表三元概念矩阵Λmin的时间复杂度为o(|Λ|2),计算三元概念约简的集合RTC的时间复杂度为o(max|REP((g,m,b))|·|Λmin|),因此整体的时间复杂度主要来自计算最小代表三元概念矩阵,为o(|Λ|2)。
3 基于最小代表三元概念矩阵的三元概念特征
从最小代表三元概念矩阵可得到所有三元概念约简,而利用所有三元概念约简可以对所有三元概念进行分类,即核心、相对必要和绝对不必要三元概念。因此,本节从最小代表三元概念矩阵的角度给出三类三元概念的判定定理。
核心三元概念是属于每一个三元概念约简的三元概念,而最小代表三元概念矩阵中的单点集出现在每一个三元概念约简中,因此Λmin中的单点集中的元素为核心三元概念。由此给出定理4。
定理4 设K=(K1,K2,K3,Y)是三元背景,T(K)是K的所有三元概念构成的集合。N∈T(K)是核心三元概念当且仅当存在(g,m,b)∈Y使得REP((g,m,b))={N}。
证明 N是核心三元概念⇔T(K)-{N}不是三元概念协调集⇔∃(g,m,b)∈Y使得(T(K)-{N})∩REP((g,m,b))=∅。因为REP((g,m,b))⊆T(K),所以(T(K)-{N})∩REP((g,m,b))=∅⇔T(K)∩ ∩REP((g,m,b))=∅⇔ ∩REP((g,m,b))=∅⇔REP((g,m,b))-{N}=∅。因为REP((g,m,b))≠∅,所以REP((g,m,b))-{N}=∅⇔REP((g,m,b))={N}。即∃(g,m,b)∈Y使得REP((g,m,b))={N}。
绝对不必要三元概念是不属于任意三元概念约简的三元概念。根据定理3,可得定理5中所描述的绝对不必要三元概念的特征。
定理5 设K=(K1,K2,K3,Y)是三元背景,T(K)是K的所有三元概念构成的集合。N∈T(K)是绝对不必要三元概念当且仅当∀REP((g,m,b))∈Λmin,N∉REP((g,m,b))。
证明 由定理3可得,N是绝对不必要概念⇔N∉∪i∈τRi⇔N∉ REP((g,m,b))⇔∀REP((g,m,b))∈Λmin,N∉REP((g,m,b))。
结合定理4与定理5,可得相对必要三元概念的判定方法。
推论1 设K=(K1,K2,K3,Y)是三元背景,T(K)是K的所有三元概念构成的集合。N∈T(K)是相对必要三元概念当且仅当存在REP((g0,m0,b0))∈Λmin使得N∈REP((g0,m0,b0)),且∀REP((g,m,b))∈Λmin,REP((g,m,b))≠{N}。
事实上,Λmin中非单点集的那些元素中的三元概念是相对必要三元概念。
例5(续例4) 用最小代表三元概念矩阵Λmin判断三类三元概念。
因为REP((1,c,A))={N1},所以由定理4知N1是核心三元概念。因为∀REP((g,m,b))∈Λmin,N6∉REP((g,m,b),所以由定理5知N6是绝对不必要三元概念。因为REP((2,b,A))∈Λmin且N2∈REP((2,b,A)),又∀REP((g,m,b))∈Λmin,REP((g,m,b))≠{N2},所以由推论1知N2是相对必要三元概念。
4 结语
本文从代表三元概念矩阵的角度研究保持三元背景不变的三元概念约简问题,提出了一种可以直接获取所有三元概念约简的方法。首先,定义了代表三元概念矩阵,并给出相应的三元概念协调集判定定理。其次,定义最小代表三元概念矩阵以简化代表三元概念矩阵,并在此基础上提出了基于最小代表三元概念矩阵的三元概念约简算法。最后,利用最小代表三元概念矩阵分别给出核心、相对必要和绝对不必要三元概念的特征。
三元概念约简理论中仍有许多有意义的问题亟待解决。如三元概念约简保存了三元背景的全部信息,那么是否能够以及如何用一个或若干个三元概念约简恢复所有三元概念是一个值得探究的问题。此外,在一般情形中,并不需要找出所有的三元概念约简,那么是否可以通过部分三元概念约简对所有三元概念进行分类?类似的问题在形式概念分析的属性约简中已被解决,在未来工作中我们将尝试从诱导算子的角度解决该问题,进一步完善三元概念约简理论。