不协调决策形式背景的矩阵型属性约简*

张呈玲，李进金+，林艺东,2

1.闽南师范大学 数学与统计学院，福建 漳州363000

2.厦门大学 数学科学学院，福建 厦门361005

1 引言

形式概念分析（formal concept analysis）是由德国数学家Wille[1-2]提出的一种分析数据的有效工具。它的核心是形式背景和概念格。形式背景是由对象集、属性集以及对象和属性之间的二元关系构成的。而概念格是将形式背景里的对象子集和属性子集以一种概念层次体现出来。近年来，形式概念分析已被广泛应用于概念认知[3]、知识提取[4]等领域。

决策形式背景是形式背景的一个延伸。其中，属性约简是决策形式背景的一个研究热点。目前，研究工作者已获得了多种属性约简方法[4-16]。它旨在寻找极小的属性子集使得决策形式背景的决策分析更加简洁。而决策形式背景分为两类：一类决策形式背景是协调的；另一类决策形式背景是不协调的。针对第一类，魏玲等[8]给出了强协调和弱协调决策形式背景的定义，以及相应的协调集的判定定理。针对强协调决策形式背景研究了保持概念外延不变的属性约简的问题。而弱协调决策形式背景借助蕴含映射刻画了属性约简。陈秀[9]从等价关系的角度给出了协调决策形式背景的定义。并且通过构造等价关系的辨识矩阵，提出了属性约简的方法。裴铎等在文献[10]中针对协调决策形式背景，从并不可约元角度给出了irr-型协调集的概念。李仲玲等[11]借助集合交集讨论了协调决策形式背景下的交约简方法，并说明了概念格协调集与交协调集是等价的。然而，由于辨识矩阵和辨识函数的约简方法的时间复杂度较大，在实际中不容易实现。李金海等[4,12-14]针对决策形式背景提出了必要属性和不必要属性的等价刻画，并设计出了保持决策规则的属性约简的启发式算法。

然而，属性约简同样是不协调决策形式背景里的重要研究课题。其目的是删除冗余、不必要属性，进而获得较为简洁的知识表达。文献[7,15-21]已对属性约简的问题取得了重要的结果。郭松涛等[15]基于文献[4]的属性约简的框架，考虑一般决策形式背景的属性约简问题。给出了一个属性是否是必要的等价刻画，进而设计出了适用一般决策形式背景的属性约简的启发式算法。王亚丽等[16-17]针对下近似函数提出了保持条件属性子集在每个决策类不变的近似约简的问题，并给出了约简方法。基于对象幂集的同余关系，文献[18,21]给出了不协调决策形式背景下的属性约简方法。Wang 等[18]从同余关系的角度讨论了上、下近似的属性约简问题。在此基础上，通过构造辨识矩阵可以得到所有的约简集。Li 等[21]基于文献[18]约简的框架，提出了分布属性约简和极大分布属性约简的概念。接着，讨论了两者之间的关系，并给出了计算约简集的方法。Huang 等[7]在吴伟志等[5]研究的基础上，考虑了决策形式背景是不协调时，从信息粒角度，利用条件信息熵刻画了属性重要度，进而设计了计算一个极小近似约简的启发式算法。但此约简方法依赖信息粒之间的关系，并且在约简过程中计算量大。本文在文献[7]的基础上，借助布尔矩阵的运算，刻画不协调决策形式背景的属性重要度，并设计出更为简便的属性约简的启发式算法。

本文首先给出不协调决策形式背景下广义矩阵协调集的定义；然后通过矩阵刻画出属性之间的相似度；接着给出一个属性是否是核心属性的充要条件；最后提出一种比Huang 等[7]的约简算法时间复杂度更低的约简方法。

2 预备知识

本章主要介绍形式概念分析的基本定义和矩阵的运算等。为下文讨论方便，假设论域U是一个非空有限集合。

定义1[1]设F=(U,A,I)是形式背景，其中U={x1,x2,…,xn}为对象集，A={a1,a2,…,am}为属性集，I是U和A之间的二元关系，且I⊆U×A。若(x,a)∈I，表示对象x具有属性a；若(x,a)∉I，表示对象x不具有属性a。

对于X⊆U,B⊆A，Wille 给出形式背景F下的一对算子：

X∗={a∈A:∀x∈X,(x,a)∈I}

B∗={x∈U:∀a∈B,(x,a)∈I}

对于论域U={x1,x2,…,xn}，X⊆U，那么X的特征向量为λ(X)=(λX(x1),λX(x2),…,λX(xn))。其中：

通常，形式背景是以0-1 数值表呈现。1 是指对象具有x属性a，即(x,a)∈I；0 是指对象x不具有属性a，即(x,a)∉I。为表述方便，因此形式背景可看成布尔矩阵MI=(cij)n×m，称MI是F的一个关系矩阵。其中：

∀xi∈U,∀aj∈A，矩阵MI的第i行是的特征向量的第j行是的特征向量

注本文中，MI(i,:) 指矩阵MI的第i行；MI(:,j)指MI矩阵的第j列；MI(i,j)指矩阵MI的第i行第j列。

定义2[5]设F=(U,A,I)是形式背景，Q⊆A，IQ=I⋂(U×Q)，则FQ=(U,Q,IQ)称为F的一个子背景。

与形式背景F类似，也可给出在子背景FQ(U,Q,IQ)中的一对算子：

引理1A=(aij)n×m,B=(bij)n×m,C=(cij)m×p是布尔矩阵，有以下运算性质：

接着，通过上面的矩阵的运算给出对象的粒矩阵描述。

定义3[6]设F=(U,A,I)是形式背景，MI是I的关系矩阵，令矩阵M的第i行为对象xi内涵的外延的特征向量，称M为对象粒矩阵。

从定义3可以得出，对象粒矩阵M的第i行M(i,:)=

定义4[8]设(U,A,I)和(U,D,J)是两个形式背景，并且A⋂D=∅。A和D分别是条件属性集和决策属性集，称S=(U,A,I,D,J)是决策形式背景。

吴伟志等在文献[5]中提出了决策形式背景是粒协调的定义。然而，现实中不协调的决策形式背景要比协调决策形式背景出现的可能性要大。那应当如何定义协调性的程度，Huang 等在文献[7]中给出如下说明。

设S=(U,A,I,D,J)是一个决策形式背景，B⊆A，定义POSB(D)={x∈U:x∗B∗B⊆x∗D∗D}，正域是由子背景(U,B,I)的对象粒含在(U,D,J)的对象粒构成的。而子背景(U,B,IB,D,J)的协调性的程度是

定义5[7]设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，若τB(D)=τA(D)，则B称为S的一个广义粒协调集。如果B是S的一个广义粒协调集，且B的任意真子集都不再是S的广义粒协调集，则B称为是S的一个粒约简。

3 基于布尔矩阵的不协调决策形式背景的属性约简

在文献[5]中，吴伟志等给出决策形式背景协调性的定义。基于此，本文利用矩阵的表达形式给出决策形式背景的相关概念。在决策形式背景S=(U,A,I,D,J)中，与定义3 类似，MI是I的条件关系矩阵，MJ是J的决策关系矩阵，则是S的条件对象粒矩阵，是S的决策对象粒矩阵。若∀B⊆A，令RB是任意一行均为λ(B)的 U× A的矩阵。那么，在子背景SB=(U,B,IB,D,J)中有MB=～((MI∧RB)∙(～(MI∧RB)T)) 。根据条件对象粒矩阵MA和决策对象粒矩阵MD，可给出S协调的定义。

定义6设S=(U,A,I,D,J)是决策形式背景，MA和MD分别是S的条件对象粒矩阵和决策对象粒矩阵，若MA≤MD，则称S是协调的；否则S是不协调的。

例1 表1 为一决策形式背景，其中对象集、条件属性集、决策属性集分别为U={x1,x2,x3,x4,x5}，A={a1,a2,a3,a4,a5,a6}和D={d1,d2,d3,d4}。

Table 1 Decision formal context S=(U,A,I,D,J)表1 决策形式背景S=(U,A,I,D,J)

从表1 中可知，决策形式背景S的条件关系矩阵和决策关系矩阵分别为：

那么，S的条件对象粒矩阵和决策粒矩阵分别为：

可以看出MA≤MD不成立。由定义6 可知，S是不协调的。

设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，定义当MB(i,:)≤MD(i,:),1 ≤i≤n时，那么有：

从上述等式可以看出，在MB的每行小于等于MD对应行的情况下，VB(D)是由MB和MD共有的0的基数构成的。因此，可以给出在决策形式背景S下的协调性程度的定义。

定义7设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A。定义子背景SB=(U,B,IB,D,J)的协调性程度为

定义8设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，若ΓB(D)=ΓA(D)，B称为S的一个广义矩阵协调集。若B是S的一个广义矩阵协调集且∀C⊂B,C都不再是S的广义矩阵协调集，那么B称为S的一个约简集。记Bt(t≤r)是S所有的约简集，且有是S的核心。

定理1设S=(U,A,I,D,J)是一个不协调决策形式背景，C⊆B⊆A，则ΓC(D)≤ΓB(D)。

证明由C⊆B⊆A，则MA≤MB≤MC。要说明ΓC(D)≤ΓB(D)，只需证明VC(D)≤VB(D) 。由于当MC(i,:)≤MD(i,:),i=1,2,…,n时，一定会有MB(i,:)≤MD(i,:)。那么(～MC(i,:))∧(～MD(i,:)) ≤(～MB(i,:))∧(～MD(i,:)) ，故有VC(D)≤VB(D)，因此ΓC(D)≤ΓB(D)。 □

从定理1 可以看出，S中的条件属性集越小，它所对应的协调性的程度越低。为了获得不协调决策形式背景下的一个约简集，下面给出条件属性子集的相似度的概念。

定义9设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，称为属性B关于A的D的相似度。

定理2设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，B是广义矩阵协调集的充要条件是E(BA,D)=1。

证明(⇒)由于B是S的广义矩阵协调集，则ΓB(D)=ΓA(D) 。从定义7 可得，VB(D)=VA(D) 。因此E(BA,D)=1。(⇐) 由E(BA,D)=1 可知，VB(D)=VA(D)。根据定义7 和定义8 可知，B是S的一个广义矩阵协调集。 □

例2（续例1）不妨设B1={a1,a3,a5}，B2={a1,a2,a5,a6}。有下面结果：

同样地，也能得到：

定义10 设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，∀a∈B，则a关于B的内重要度为：

从定义10 可以看出，a∈B的重要度是通过E(BA,D)和E(B-{a}A,D)之间的差异得到的。换句话说，当a从B中删去时，a在B中的重要度是通过MB和MB-{a}对MD之间的相似度变化大小来衡量的。

利用定义10 可得如下核心判定定理，为下面设计启发式算法提供了简单的方法。

定理3设S=(U,A,I,D,J)是一个不协调决策形式背景，a∈A是核心属性的充要条件是Sig(Aa)>0，或者a∈A不是核心属性的充要条件是Sig(Aa)=0。

证明(⇒)因为a∈A是核心属性，则A-{a}不是广义矩阵协调集，即ΓA-{a}(D)≠ΓA(D) 。根据A-{a}⊆A，由定理1 知，ΓA-{a}(D)≤ΓA(D)，故ΓA-{a}(D)<ΓA(D)。由定义10 得：

(⇐)由Sig(Aa)>0 知，E(A-{a}A,D)<1。假设a不是核心属性，则至少存在一个约简集Q，使得a∉Q且Q⊆A-{a}。由定理1 知，ΓQ(D)≤ΓA-{a}(D)，即VQ(D)≤VA-{a}(D)。则E(QA,D)≤E(A-{a}A,D)<1，与Q是一个约简集矛盾。因此a是核心属性。 □

推论1设S=(U,A,I,D,J)是一个不协调决策形式背景，则Core(S)={a∈A:Sig(Aa)>0}。

证明由定理3 可直接得到。 □

定理4设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，若E(BA,D)=1 并且∀b∈B，Sig(Bb)>0，则B是S的一个约简集。

证明由E(BA,D)=1 及定理2 可知，B是S的一个广义矩阵协调集。∀E⊂B，∃b0∈BE，使得E⊆B{b0}。由定理1 可以得到ΓE(D)≤ΓB{b0}(D)≤ΓA(D)。同样有VE(D)≤VB{b0}(D)≤VA(D)。由假设∀b∈B，Sig(Bb)=。由 上述可知b0∈B，故VB(D)>，从而就可以得到VE(D)≤VB{b0}(D)<VB(D)≤VA(D) 。故能得到VE(D)<VA(D)，那么E(EA,D)<1。因此E不是S的广义矩阵协调集。综上所述，B是S的一个约简集。 □

定义11 设S=(U,A,I,D,J)是一个不协调决策形式背景，B⊆A，∀a∈A-B，则a关于B的外重要度为：

根据上述讨论，可以设计一个启发式算法寻找不协调决策形式背景下的一个极小约简。

算法1不协调决策形式背景S=(U,A,I,D,J)的一个约简集的启发式算法。

此算法第1 步的时间复杂度为O(U2A+U2D)；第2 步用于找出所有的核心属性，此时间复杂度为O(U2A2)；在第4、5 步的过程中，时间复杂度不超过O(U2A2)，故算法1 的时间复杂度为O(U2A2)。相较于文献[7]的时间复杂度O(U2(A3+D))更低。

例3（续例1）从例1 中可知，S是不协调决策形式背景以及S的协调性程度为

根据算法1 计算∀a∈A的重要度根据推论1 知

根据定义11，{a3,a4,a5,a6}关于Core(S)的外重要度分别为Sig(aiCore(S))=0(i=3,4,5)，以及从而有P={a1,a2,a6}。由定理4 可以得到E(PA,D)=1且Sig(Pa)>0，∀a∈P。故而有P={a1,a2,a6}是S的一个约简集。可以看出，把a3、a4、a5从不协调决策形式背景S的条件属性集A中删去，子背景(U,P,IP,D,J)的协调性程度仍为

4 结束语

属性约简是决策形式背景的重要研究热点之一。本文针对不协调决策形式背景的属性约简给出了相应的启发式算法。首先通过布尔矩阵的运算刻画属性之间的相似度。接着讨论了判断广义矩阵协调集和核心属性的等价条件。在此基础上，提出了启发式的约简算法，并通过实例说明该算法的有效性。值得注意的是，此方法的提出，为借助矩阵研究形式概念分析拓宽了新视角。本文下一步要考虑的是，借助矩阵运算考虑模糊形式背景的属性约简问题。