多源形式背景的信息融合

（西南交通大学数学学院，四川 成都 611756）

1982 年，Wille 提出了形式概念分析(FCA)理论[1]实现了哲学意义上概念的形式化描述。FCA的研究对象为形式背景，通过概念生成算子产生形式背景中的形式概念。形式背景中的所有形式概念按照特定的序关系构成完备格（概念格），这种序关系描述了概念之间的层次结构。作为数据分析与知识获取的一种有效工具，FCA 已广泛应用于知识工程、决策分析、机器学习、数据挖掘等领域。目前，形式概念分析的主要研究方向包括概念格扩展模型[2－6]、属性约简与规则获取理论[7－15]、三支概念分析[16－19]等。在概念格扩展模型研究方面，Düntsch 等[2]基于模态算子提出了面向属性的形式概念并建立了面向属性概念格。Yao[3－4]进一步对基于粗糙集理论及基于形式概念分析理论的决策规则进行了对比分析，并提出了面向对象的形式概念。Burusco 等[5]与Belohlavek 等[6]等将模糊集理论与FCA 相结合，提出了模糊形式概念分析理论。

多源数据是针对特定的研究对象从若干信息源获取的数据。随着科学技术的发展及计算机技术的进步，科学研究与社会实际中的数据不断增长且呈现出多源化趋势。基于多源数据的知识发现理论与方法研究成为近年来相关领域的研究热点。Xu 等[20]借助信息熵刻画信息源重要度，给出了一种多源信息系统融合方法，进而将多源信息系统转化为单源信息系统，讨论了相应的程度粗糙集模型及多粒度粗糙集模型。Wu 等[21]提出了多粒度标记信息系统的概念。多粒度标记信息系统由多个具有相同对象集和属性集的信息系统构成，这些信息系统中属性具有特定的细化关系。人们对多粒度标记决策信息系统的最优粒度选择方法、基于多粒度粗糙近似算子的知识获取等进行了大量研究[22－24]。最近，Wei 等[25]对基于粗糙集理论的多源信息系统信息融合方法进行了系统分析。

在多源形式概念分析方面，Huang 等[26]从信息融合角度提出了三支概念认知算子，给出了一种三支概念认知学习方法。李金海等[27]提出了多粒度标记形式背景的概念，通过正向尺度化和反向尺度化方法刻画了多粒度标记信息系统与多粒度标记形式背景之间的相互转化关系，并讨论了多粒度标记下的蕴涵规则。曾望林等[28]通过属性树将面向对象概念从单粒度拓展至多粒度，刻画了不同粗细粒度下面向对象的形式概念之间的内在联系。杨涵等[29]对不同粒度标记下形成的面向属性的概念格之间的关系进行了研究，提出了相应的概念格生成的方法。魏玲等[30]研究了多源决策形式背景基于粒概念的属性约简问题，刻画了多源与单源决策形式背景属性约简的关系，提出了多源决策形式背景的规则获取方法。

总体上讲，由于形式背景数据的特殊性及概念格构造的复杂性，从形式概念分析角度探索多源数据情形下的知识发现研究还比较少见。另外，现有研究大多采用“融合知识”的手段，即首先研究多源形式背景中各单源形式背景的概念格结构及属性约简，然后通过适当的聚合算子融合这些概念格结构及属性约简得到多源形式背景的结构。本文针对多源形式背景提出一种“融合数据”的研究方法，首先借助完备剩余格将多源形式背景融合为模糊形式背景，进而研究该模糊形式背景的模糊概念格与相应的单源形式背景的概念格之间的关系，并给出相关概念格之间的相互诱导方法。本文的工作将为多源形式概念分析提供一种新思路。

1 预备知识

本节给出形式概念分析中的一些基本概念及基本性质。

定义1[1]称三元组(G,M,I)是一个形式背景，其中G是非空有限对象集，M是非空有限属性集，I是G和M上的二元关系，即I⊆G×M。对于任意g∈G和m∈M，若(g,m)∈I，则称对象g具有属性m；若(g,m)∉I，则称对象g不具有属性m。

在形式背景(G,M,I)上，Wille[1]提出了一对概念生成算子↑:2G→2M和↓:2M→2G，对于任意X⊆G,A⊆M：

概念生成算子具有如下基本性质。

性质1[1]设(G,M,I)是一个形式背景，对于任意X,X1,X2⊆G,B,B1,B2⊆M，有：

1)X1⊆X2⇒X2↑⊆X1↑，B1⊆B2⇒B2↓⊆B1↓；

2)X⊆X↑↓,B⊆B↓↑；

3)X↑=X↑↓↑,B↓=B↓↑↓；

4)X⊆B↓⇔B⊆X↑；

5)(X1∪X2)↑=X1↑∩X2↑,(B1∪B2)↓=B1↓∩B2↓。

定义2[1]设(G,M,I)是一个形式背景，对任意X⊆G,B⊆M，若X↑=B且X=B↓，则称二元序对(X,B)为该形式背景的一个形式概念，其中X称为(X,B)的外延，B称为(X,B)的内涵。

设(G,M,I)的所有形式概念构成的集合为L(G,M,I)，定义形式概念之间的大小关系为：对任意的(X1,B1),(X2,B2)∈L(G,M,I)，

则(L(G,M,I)≤)构成完备格，称为（G,M,I）的概念格。对应的上、下确界分别为：

由形式概念的定义及概念生成算子的性质可知，对于任意x∈G,(x↑↓,x↑)为一个形式概念，称为由对象x导出的概念，简称为对象概念，其中x↑为{x}↑的简写。结合粒计算的基本思想，将对象概念称为粒概念。

定义3[31]设L=(L,∧,∨,⊗,→,0,1)，若L满足：

1）(L,∧,∨,0,1)是一个有最大元1 和最小元0 的格；

2）(L,⊗,1)是一个交换幺半群，即运算 ⊗满足：

3）⊗和→构成一个伴随对，即对任意x,y,z∈L,x≤y→z⇔x⊗y≤z成立。

则称L=(L,∧,∨,⊗,→,0,1)为一个剩余格。

若(L,∧,∨,0,1)是一个完备格，则称剩余格L=(L,∧,∨,⊗,→,0,1)为一个完备剩余格。

性质2[31]设L=(L,∧,∨,⊗,→,0,1)为一个完备剩余格，则下列性质成立：

1）运算 ⊗关于每个变元都是单调的，即对任意x1,x2,y1,y2∈L，若x1≤x2,y1≤y2，则x1⊗y1≤x2⊗y2；

2）蕴涵→关于第1 个变元是反单调的，关于第2 个变元是单调的，即对于任意x1,x2,y∈L，若x1≤x2，则x2→y≤x1→y，y→x1≤y→x2；

3）x→y=1当且仅当x≤y；

4）x⊗y≤x,x⊗y≤y；

5）对于任意x∈L,{yi;i∈τ}⊆L，有；

6）对于任意x∈L,{yi;i∈τ}⊆L，有。

基于剩余格理论，可以将FCA 理论模糊化。

定义4[6]称三元组是一个L模糊形式背景，其中G是非空有限对象集，M是非空有限属性集，是G和M之间的L模糊关系，即:G×M→L，L是一个完全剩余格。

在L模糊形式背景中，对于任意x∈G,a∈M，表示对象x具有属性a的程度。以下用LG和LM分别表示G和M上的所有L模糊集构成的集合，即。

定义5[6]设三元组是一个L模糊形式背景。定义算子↑:LG→LM和↓:LM→LG如下：对于任意，

性质3[6]设是一个L模糊形式背景。对于任意，下列性质成立：

式（5）和（6）是式（1）和（2）中概念生成算子的推广。若满足，则称二元组是一个L模糊形式概念。其中称为该L模糊形式概念的外延，称为该L模糊形式概念的内涵。L模糊形式背景中所有L模糊形式概念构成的集合记为。

2 多源形式背景的融合

为了将形式概念分析方法应用于多源数据处理，魏玲等[30]提出了多源形式背景的概念。

定义6[30]多源形式背景可表示为MK={Ki|Ki=(U,M,Ii),i∈τ}，其中：

1）U是非空有限对象集，M是非空有限属性集；

2）τ={1,2,···,n}为指标集，对于任意的i∈τ，Ii是U与M之间的二元关系；

3）对于任意i∈τ，称Ki为多源形式背景的第i源单源形式背景，在不引起混淆的情况下，简称为单源形式背景。

由此定义，多源形式背景是由若干单源形式背景构成，这些单源形式背景具有相同的对象集与属性集。

例1考虑研究生学位论文评价问题。假设G={x1,x2,x3,x4}为4 份研究生学位论文的集合，M={a1,a2,a3,a4}为论文评价指标的集合，a1、a2、a3、a4分别表示论文选题、写作、内容、研究成果。一般情况下，学位论文评价结果是多位评审专家评审意见的综合。令τ={1,2,3}为3 位评审专家的集合，对于任意i∈τ，第i个评审专家对学位论文的评价可以表示为一个形式背景（G,M,Ii），如表1所示。其中1表示合格，0 表示不合格。3 位评审专家的评审意见构成一个多源形式背景MK={Ki|Ki=(G,M,Ii),i∈τ}。

表1 多源形式背景MK={Ki|Ki=(U,A,Ii),i ∈τ}

针对多源形式背景，魏玲等[30]从单源形式背景的角度研究了它的属性约简及规则获取问题。下面将从数据融合的角度讨论多源形式背景的结构。

命题1[32]L={0,1}n={(x1,x2,···,xn)|xi∈{0,1},i∈{1,2,···,n}}，则(L,∧,∨,⊗,→)构成一个完备剩余格，其中对于任意(x1,x2,···,xn),(y1,y2,···,yn)∈L，有：

在完备剩余格L={0,1}n中，(x1,x2,···,xn)≤(y1,y2,···,yn)当且仅当：对任意i∈{1,2,···,n}有xi≤yi。

定义7[32]设MK={Ki|Ki=(G,M,Ii),i∈τ}是一个多源形式背景。称KMK=(G,M,)为MK 的融合形式背景，其中对于任意x∈G,m∈M，

Ii(x,m)为Ii的特征函数。

由此定义，多源形式背景的融合形式背景是L模糊形式背景，其中真值域L为完备剩余格L={0,1}n。

例2表2 给出了例1 中的多源形式背景的融合形式背景。

表2 融合形式背景(U,A,)

表2 融合形式背景(U,A,)

3 融合形式背景中的形式概念

设KMK=是多源形式背景MK=Ki|Ki={(G,M,Ii),i∈τ}的融合形式背景。第i源单源形式背景Ki中的概念生成算子记为↑i和↓i，KMK中的概念生成算子记为↑和↓。对于任意g∈G，g在KMK中生成的模糊粒概念为(g↑↓,g↑)，在Ki中生成的粒概念为。以下用表示外延的特征函数，x∈G。下面的定理刻画了KMK中的模糊粒概念与Ki中的粒概念之间的关系。

定理1设KMK=是多源形式背景MK={Ki|Ki=(G,M,Ii),i∈τ}的融合形式背景，τ={1,2,···,n}。对于任意x,g∈G，有

证明对于任意x,g∈G,m∈M，

从而有

为叙述方便，设fi为上式的第i个分量，即。由定义可知fi=0或fi=1，又

故有fi=，即g↑↓(x)=成立。

例3考虑例1 中的多源形式背景及其融合形式背景。对x1,x2∈G，有，从而。另一方面，有

定理2设MK={Ki|Ki=(G,M,Ii),i∈τ}是一个多源形式背景，τ={1,2,···,n}，KMK=为其融合形式背景。对于任意∈LG，x∈G，令,，则

证明由L模糊形式概念的定义知

从而有

形式概念的外延与内涵可以互相确定。L(G,M,)中所有模糊形式概念的外延构成的集合记为，显然有。注意到在定理2 中有∈ExtL(G,M,Ii)，故有推论1。

推论1设MK={Ki|Ki=(G,M,Ii),i∈τ}是一个多源形式背景，τ={1,2,···,n}，KMK=为其融合形式背景。则

定理3设MK={Ki|Ki=(G,M,Ii),i∈τ}是一个多源形式背景，τ={1,2,···,n}，KMK=(G,M,)为其融合形式背景。则

证明对于任意(X1,X2,···,Xn)∈ExtL(G,M,I1)×ExtL(G,M,I2)×···×ExtL(G,M,In)，令为：对于任意x∈G，有

其中Xi(x)表示Xi的特征函数。由定理2 可得：对于任意x∈G，有

对于任意i∈τ，由Xi∈ExtL(G,M,Ii)可得=Xi，从而有

由推论1 和定理3 可得推论2。

推论2设MK={Ki|Ki=(G,M,Ii),i∈τ}是一个多源形式背景，τ={1,2,···,n}，KMK=为其融合形式背景。则

此推论表明融合形式背景的模糊概念格与其单源形式背景的Wille 概念格可以互相确定。

形式背景的融合方法可推广至多源模糊形式背景。

定义8多源模糊形式背景可表示为，MFK={Ki|Ki=(G,M,Li,),i∈τ}，其中：

1）G是非空有限对象集，M是非空有限属性集；

2）τ={1,2,···,n}为指标集且对于任意i∈τ，Li为完备剩余格，:G×M→Li是G与M之间的模糊关系；

3）对于任意i∈τ，称Ki为第i源单源模糊形式背景。

若L1,L2,···,Ln为完备剩余格，L=L1×L2×···×Ln为L1,L2,···,Ln的笛卡儿积，则L也构成完备剩余格，其中运算按照逐点定义。利用完备剩余格的笛卡儿积，可以考虑多源模糊形式背景的融合问题。

定义9设MFK={Ki|Ki=,i∈τ}为多源模糊形式背景，τ={1,2,···,n}为指标集。称KMFK=为MFK 的融合模糊形式背景，其中L=L1×L2×···×Ln且对于任意x∈G,m∈M，有

由此定义，多源模糊形式背景的融合形式背景仍为模糊形式背景。以下将单源模糊形式背景Ki中的概念生成算子记为↑i和↓i，KMFK中的概念生成算子记为↑和↓。

定理4设MFK={Ki|Ki=,i∈τ}是一个多源模糊形式背景，τ={1,2,···,n}，KMFK=为其融合模糊形式背景。对于任意∈LG，x∈G，令

则有

证明对于任意m∈M，由L模糊形式概念的定义知

于是，有

定理5设MFK={Ki|Ki=,i∈τ}是一个多源模糊形式背景，τ={1,2,···,n}，KMFK=(G,M,L,)为其融合模糊形式背景。则

证明由定理4 可得

对于任意(X1,X2,···,Xn)∈ExtL(G,M,L1,I1)×ExtL(G,M,L2,I2)×···×ExtL(G,M,Ln,In)，存在∈LG满足：对于任意x∈G，有=(X1(x),X2(x),···,Xn(x))。由定理4 可得

对于任意i∈τ，由Xi∈ExtL(G,M,Li,Ii)可得=Xi，从而有

4 结论

本文研究形式概念分析中的多源形式背景融合方法。针对多源同域形式背景，现有的研究工作大多是对相应的单源形式背景分别进行处理，然后融合处理结果。一般情况下，其具有较高的时间复杂度。本文借助剩余格理论提出了一种将多源形式背景融合为一个L模糊形式背景的方法，然后讨论融合后的形式背景，其中真值域L具有形式L={0,1}n，刻画了融合形式背景中的L模糊概念与单源形式背景中的经典形式概念之间的相互诱导方法。另外，相关研究结果被推广至多源模糊形式背景。基于本文的研究结果，可以进一步讨论多源形式背景的属性约简与单源形式背景属性约简的关系，提出多源形式背景的属性约简、规则获取方法。