基于双属性综合依赖度的属性约简方法研究

2021-01-08李法朝任夜星靳晨霞

山西大学学报（自然科学版） 2020年4期

李法朝,任夜星,靳晨霞

(1.河北科技大学理学院,河北石家庄 050018;2.河北科技大学经济管理学院,河北石家庄 050018)

0 引言

粗糙集的概念是由Pawlak1982年提出的,是处理不精确、不一致、不完整信息的一种有效工具,其基本思想是通过案例库的分类归纳出概念和规则[1-2]。随着粗糙理论的发展与完善,其应用已遍及自然科学的各个领域,其中属性约简(在保持信息系统的某种性能不变的前提下,删除冗余属性)是最为典型的应用之一。

由于信息系统的属性约简大都不唯一,且寻求信息系统的属性个数最少的约简是NP-hard问题[3],因而,如何通过某种启发式算法来实现属性约简是该研究领域的热点研究内容[4-5],众多学者进行了诸多有益的探讨。文献[6]以属性引起的互信息大小作为属性的重要性度量依据,提出了一种基于粗糙集和信息熵的属性约简算法。文献[7]提出了基于差别集的属性约简方法,通过删减属性来求得最终约简集。文献[8]通过改进差别矩阵和度量属性显著性的方法,提出了一种基于差别矩阵吸收律的完全启发式约简算法,有效地降低了差别矩阵约简算法的空间复杂度。文献[9]提出基于可辨识矩阵的Core Searching算法(该算法首先找出信息系统的核,然后去掉矩阵中包含核的矩阵项,将剩下的矩阵项中出现次数最多的元素加到核中,直到矩阵为空)。文献[10]对 Core Searching 算法进行改进,通过给属性设立计数器来减少计算量。文献[11]根据Skowron可分辨矩阵[12]提出一种基于属性重要性的启发式属性约简算法。文献[13]提出了一种基于样本选择的启发式算法,首先从样本集中挑选重要的样本,进而利用选取出的样本构建新的决策系统再利用启发式算法求解约简集。文献[14]利用二进制区分矩阵便于计算且直观的优点,提出了一种压缩二进制矩阵的方法。文献[15]基于知识的信息量定义了属性的重要性,以此为启发式信息提出了基于信息量的属性约简算法。文献[16]给出了一个新的、较好的、度量属性重要性的计算公式,并分析了其性质,给出了一个时间复杂度较低的属性约简算法。文献[17]提出了基于投票式属性重要度的快速属性约简算法。文献[18]研究基于可区分度属性约简与全粒度Pawlak约简的关系,理论分析表明决策系统中基于正区域可区分度属性约简在通常情况下和全粒度Pawlak约简完全相等。文献[19]给出了布尔矩阵如何表示粗糙集理论中概念与运算,证明了布尔矩阵表示的属性约简与代数形式表示的属性约简是等价的,并在此基础上提出了条件区分能力的概念,构造了一个属性约简启发式算法。文献[20]给出了基于布尔矩阵表示的核属性的判断方法。文献[21]定义了优势关系下协调目标信息系统的约简,并给出了相应的优势矩阵方法。文献[22]将等价关系上的浓缩布尔矩阵属性约简方法扩展到优势关系上,基于优势矩阵提出了浓缩布尔矩阵的基于概念,建立了相应的高效约简方法。文献[23]利用图论的相关理论和方法,对基于区分矩阵的粗糙集属性约简方法给出了直观和等价的刻画,在此基础上提出了基于图论的粗糙集属性约简算法。文献[24]提出了一种基于多粒度视图的属性约简算法,用于发现大规模数据集的约简集。上述研究基本上反映了该领域的研究现状,其中的一个共性是采用启发式算法，每次只启发一个属性,主要考虑的是单个属性的区分能力,对属性集的综合区分能力涉及较少。由于最小约简的特征在于强调属性集的综合区分能力,因而从多个属性的综合区分能力出发，进行属性约简，可能更有助于获得最小约简。

在利用逐步添加属性的方式来进行约简时,总希望添加进来的属性尽可能地提高属性集的综合区分能力,然而每次添加一个属性时,依次添加的两个属性的综合区分能力不一定是最大的。针对此问题,本文以信息系统为基础,主要做了以下几方面工作:1)提出了属性集综合区分能力的概念;2)给出了布尔辨识矩阵新的表达形式及在矩阵化简过程中的一种形式化描述;3)讨论并给出双属性综合依赖度的递进式计算方法;4)设计了基于双属性综合依赖度的约简算法;5)结合具体算例和几个常用的UCI数据库验证了此方法的有效性。理论分析和仿真试验表明,该算法在一定程度上可以避免上述情况的发生,而且可以减少属性启发次数,更易得到最小约简。

1 预备知识

下文中约定:1)(U,A,FA)表示一个信息系统(其中,U={x1,x2,…,xn}表示对象集,A={a1,a2,…,am}表示属性集,FA={fa:U→Va|a∈A}表示U与A之间的关系函数集,Va为a的值域);2)对(U,A,FA)及B⊂A,记RB={(xi,xj)|fa(xi)=fa(xj),a∈B}表示B确定的U上的等价关系,[xi]B={xj|xj∈Uand (xi,xj)∈RB}表示xi的RB等价类,U/B={[xi]B,xi∈U};3)a∨b=max{a,b},|C|表示集合C中的元素个数,MT表示矩阵M的转置。

定义1[2]设(U,A,FA)是一个信息系统,B⊂A,a∈A。1)若RB=RA,则称B是A的一个划分协调集;2)若B是A的一个划分协调集,且B的任何真子集均不是A的划分协调集,则称B为A的一个划分约简集;3)若a∈B对A的任何划分约简集B恒成立,则称a为A的一个划分核心属性。

由于信息系统中的等价类是构建属性约简方法的一个核心指标,且等价类常常作为一个整体来考虑,因而,为了便于叙述,我们引入辨识信息系统和综合依赖度的概念。

1)称(U,B,FB)为(U,A,FA)的子系统;

(1)

1)若sign(fai(x),fai(y))=1,则称ai可区分x,y;否则,则称ai不能区分x,y;

(2)

(3)

(4)

(5)

称G(ai)为ai的区分能力;G(B)为属性集B的综合区分能力;D(ai|B)为B对属性ai的依赖度;D(C|B)为属性集B对属性集C的综合依赖度,特别的,当属性集C只包含两个属性时则称为属性集B的双属性综合依赖度。

2 双属性综合依赖度的计算方法

本部分以辨识信息系统为基础,着重讨论综合依赖度的基本性质及其相关的计算方法。为了便于叙述,下文中约定:

3)对X=(x1,x2, …xn),Y=(y1,y2,…yn),Xi=(xi1,xi2, …,xin),i=1, 2, …,s:

δ(x)=(δ(x1),δ(x2),…,δ(xn));

X-Y=(x1-y1,x2-y2,…,xn-yn);

X∨Y=(x1∨y1,x2∨y2, …,xn∨yn);

∨i∈IXi=(∨i∈Ixi1,∨i∈Ixi2,…,∨i∈Ixin)。

4)若矩阵Q第1行为(a1,a2,…,am),而其余各行的元素均为0或1,则称Q为a1,a2,…,am的标识布尔矩阵,记为

2.1 单属性辨识矩阵及作用特征分析

(6)

(7)

为信息系统(U,A,FA)的单属性辨识矩阵。

1)G(ai)=2·S(P(M,ai));

2)G(B)=2·S(∨at∈BP(M,at));

3)D(C|B)=2·S(δ(∨au∈CP(M,au)-∨at∈BP(M,at)))

4)G(B∪C)=G(B)+D(C|B);

5)B是A的划分协调集的充分必要条件是G(B)=N(N-1)(即∨at∈BP(M,at)是一个分量均为1的向量)。

证明1)～4)可利用定义3得出,下面给出4)的证明。

2.2 递进式双属性综合依赖度的计算方法

为了便于叙述,下文中约定:1)M⊖{ak}表示在矩阵M中删除ak所在的列中元素1所对应的行以及ak所在列后形成的矩阵;2)设B⊂A,M⊖B表示在矩阵M中删除∨at∈BP(M,at)中元素1所对应的行以及B中属性所对应的列后形成的矩阵;3)M⊖φ=M。按照上述约定,不难看出下面的运算规律: 1)交换律(即M⊖{ai,aj}=M⊖{aj,ai});2)递推律(即M⊖{ai,aj}=(M⊖{ai})⊖{aj},M⊖{ai,aj,ak}=(M⊖{ai,aj})⊖{ak})。

利用上述约定及定理1可知,对A的非空子集B,C以及{ai,aj}⊂A,有

D({ai,aj}|B)=2·

S(P(M⊖B,ai)∨P(M⊖B,aj)),

(8)

D(C|B)=2·S(∨au∈CP(M⊖B,au))。

(9)

不难看出:1)双属性综合依赖度D({ai,aj}|B)是单属性依赖度D(ai|B)的一种延伸,同时也是D(C|B)的一种特殊情形;2)公式(8)和(9)是针对属性添加过程的一种递进式属性重要性计算方法;3)当|C|较大时,每次添加B的综合依赖度最大的|C|个属性集具有较高的计算复杂度。基于上述分析,本文设计了一种一次添加两个属性的属性约简算法。下文中给出双属性最优综合依赖度的概念。

(10)

为B的双属性最优综合依赖度。

下面结合一个具体算例来分析双属性最优综合依赖度的计算过程。

例1 表1是某手机生产商对大学生关于手机性能的调查结果。其中U={x1,x2, …,x10}为调查对象集;A={a1,a2,a3,a4,a5}为属性集(其中,a1表示手机的尺寸,其取值为V1={小(1),中(2),大(3)};a2表示手机的价格,其取值为V2={高(1),中(2),低(3)};a3表示手机的综合性能,其取值为V3={好(1),较好(2),一般(3)};a4表示手机的内存,其取值为V4={大(1),中(2),小(3)};a5表示手机的显示像素,其取值为V5={高(1),一般(2)})。

表1 手机情况的调查结果

表2 表1的简化结果

利用等价关系可将信息系统简化，如表2所示。即U/A={[x1]A, [x2]A, [x5]A, [x6]A, [x7]A, [x8]A}{U1,U2,U3,U4,U5,U6}。由此及定义4可得:

根据定理2可得:

D({a1,a2}|{a5})=10,

D({a1,a3}|{a5})=10,

《北爱》让我赚到了人生中第一笔片酬。那是我第一次觉得自己“有钱了”。当时给家里人买了吃喝用的，剩余的都存进了我妈的银行卡里。

D({a1,a4}|{a5})=12,

D({a2,a3}|{a5})=12,

D({a2,a4}|{a5})=10,

D({a3,a4}|{a5})=10,

D({a1,a2}|{a3,a5})=4,

D({a1,a4}|{a3,a5})=4,

D({a2,a4}|{a3,a5})=4,

由此及定义5可得

D({ai,aj}|{a3,a5})=4。

3 基于双属性综合依赖度的属性约简算法

从上面的分析可以得出依赖度可以作为启发式属性约简中属性添加的一个选择依据。文献[20] 以属性集对单个属性的依赖度为依据,建立了属性约简算法(下文称之为算法1),其执行过程如下:

输入:信息系统(U,A,FA);

输出:该信息系统的一个约简B;

步骤1:根据信息系统构造对应的单属性辨识矩阵M,令B=φ;

步骤2:计算M⊖B中各行的元素之和,若存在和为1的行,则将该行中1对应的属性a添加到B中,并将B更新为B∪{a},同时更新M⊖B;否则,转步骤3;

步骤3:计算M⊖B中各列的元素之和,选取结果最大的对应的属性a添加到B中,并将B更新为B∪{a},同时更新M⊖B,转步骤4;

步骤4:若M⊖B不是行向量,则转步骤3;否则,输出B。

值得注意的是,在算法1中约简集对依次添加的两个属性的综合依赖度未必是最大的(见第4部分的算例分析),此表明考虑一次添加多个属性可能更有助于获取最小约简。由于一次添加的属性太多将导致计算复杂度的增大,因而本文设计了一种基于双属性综合依赖度的属性约简算法(下文称之为算法2),其执行过程如下:

输入:信息系统(U,A,FA);

输出:该信息系统的一个约简B;

步骤1:利用等价关系分类,在每类中选取一个对象作为新的对象集;

步骤2:计算简化了的信息系统的单属性辨识矩阵M,令B=φ;

步骤3:计算M⊖B中各行的元素之和,若存在和为1的行,则将该行中1对应的属性a添加到B中,并将B更新为B∪{a},同时更新M⊖B,进行步骤6;否则,进行步骤4;

步骤4:若M⊖B中存在元素全是1的列,则将该列对应的属性a添加到B中,并将B更新为B∪{a},同时更新M⊖B,进行步骤6;否则,进行步骤5;

步骤5:计算属性集B的双属性最优综合依赖度,并将其对应的属性集{ai,aj}添加B中,并将B更新为B∪{ai,aj},同时更新M⊖B,进行步骤6。

步骤6:若M⊖B是行矩阵,则输出B;否则,转步骤4。

本算法的基本思想是:首先将核心属性加入约简集B中,更新矩阵M⊖B;判断矩阵M⊖B是否有一列元素全是1,若有则添加该列所对应的属性得到约简,否则说明添加一个属性不能得到约简,至少还需要添加两个属性,此时添加双属性最优综合依赖度对应的属性到B中有助于更快的得到约简,此表明算法2是算法1的一种改进。

下面分析算法1与算法2的时间复杂度:假设信息系统等价类个数为n,计算单属性辨识矩阵的时间复杂度为O(n2×|A|)。算法1中步骤4计算矩阵列和的最坏时间复杂度为O(n2×|A|),故算法1的时间复杂度为O(n2×|A|);算法2中步骤5计算最优双属性综合依赖度的最大时间复杂度为O(n2×|A|2),此表明算法2在一次属性添加过程中的时间复杂度高于算法1,但算法2的迭代次数少于算法1,因而算法2与算法1的实际运行时间无明显差异(参见第4部分的仿真实验)。

4 仿真与比较分析

本部分结合一个具体算例和几个UCI数据集来进一步解释基于双属性综合依赖度的属性约简算法。

情形1以2.2部分中的例1为案例,比较本文的算法(算法2)与算法1的性能差异。

1)算法1的约简结果:

① 由于单属性辨识矩阵M中没有各元素之和是1的行,因而该信息系统没有核心属性,令B=φ;

② 经计算可知属性a1区分能力最大,因而添加属性a1到B中,得B={a1},

经计算可知属性集B对属性a3的依赖度最大,因而添加a3到B中,得B={a1,a3},

经计算可知属性集B对属性a2的依赖度最大,因此添加a2到B中,得B={a1,a3,a2},M⊖B=(a4a5),即B={a1,a3,a2}为约简。

2)算法2的约简结果:

① 由于单属性辨识矩阵M中没有各元素之和是1的行,因而该信息系统没有核心属性,令B=φ;

② 经计算可得:

D({a1,a2}|B)=26,D({a1,a3}|B)=28,

D({a1,a4}|B)=28,D({a1,a5}|B)=26,

D({a2,a3}|B)=30,D({a2,a4}|B)=24,

D({a2,a5}|B)=26,D({a3,a4}|B)=28,

D({a3,a5}|B)=26,D({a4,a5}|B)=26,

K2(B)=30,因而添加属性a2,a3到B中,得B={a2,a3},M⊖B=(a1a4a5), 即B={a2,a3}为约简。

上述计算结果表明,在最小约简意义下算法2优于算法1。

情形2在UCI数据库中的8个数据集,比较本文的算法(算法2)、算法1及文献[25]提出的ARABP算法的约简性能(由于本文的算法是针对信息系统设计的,因而当数据集是决策表时,只选择条件属性集进行处理),其结果如表3—表4(其中,|U|表示示例个数,|A|表示属性个数,|B|表示约简集的属性个数,T表示平均运行时间(s))。

从表3中可看出:1)算法1和算法2相对于ARABP算法在约简结果上都有一定的优势,约简后的属性个数都相对较少;2)算法2是算法1的一种改进,在上述示例中算法2与算法1的约简结果相同。下面给出了不同的数据集进一步地比较两种算法的性能。

表3 约简结果分析

表4 约简结果及运行时间

从表4的结果可看出,算法2相对于算法1更易得到最小约简。综上所述,虽然本文提出的算法在时间复杂度上有所提高,但本算法减少了添加属性的次数且能够更快的降低单属性辨识矩阵的维数,表4的实验结果也表明算法2与算法1在运行时间相差不大的情况下约简结果更好,实验结果与理论分析相吻合,验证了该算法的有效性。

5 结论

在目前的添加式属性约简算法中每次只启发一个属性,主要考虑的是单个属性的区分能力,但依次添加区分能力最大的一个属性不能保证前后添加的两个属性的综合区分能力最大,因而从多个属性的综合区分能力出发进行属性约简更有助于获得最小的增长下约简。本文针对如何获取属性个数较少的属性约简问题,设计了一种基于双属性综合依赖度的属性约简算法,并结合具体算例及UCI数据集分析和验证了该算法的特点和有效性。该算法以最大限度地提高约简集的综合区分能力为目标,依次添加约简集综合依赖度最大的两个属性,直至约简集的综合区分能力与原属性集的区分能力相同。理论分析和试验结果表明,本文设计的算法较现有添加式属性约简算法而言,更易于获得属性个数较少的约简,且适用于决策表的属性约简,在数据处理、数据挖掘等领域具有较强的应用价值。