基于可辨识矩阵的属性约简算法及应用

陈志恩， 田彦山， 马 旭

(宁夏师范学院 数学与计算机科学系,宁夏 固原756000)

1 引 言

粗糙集理论[1-2]由波兰数学家Pawlak.Z于1982年提出，它是一种新的处理信息系统中不精确、不完整、不一致数据的数学工具，近年来已在数据决策分析、机器学习与模式识别等多个邻域得到了广泛的应用[3-4].

属性约简[5-7]是粗糙集理论研究的主要内容之一，由于在原始数据集中，往往存在大量冗余和不确定性的信息，严重影响到后续数据挖掘和处理的效率.因此，通过删除冗余属性，能获得数据集合的本质信息和保持原始数据分类信息的完整性，从而提高数据的分类质量.目前粗糙集属性约简方法的研究已经取得了很多成果,各种高效的启发式约简算法相继被提出,这些启发式约简算法主要目的是寻找一个约简或近似约简.譬如，鲍迪等针对区间值决策表中对象集动态增加的情况，提出了区间值决策表的正域单增量和组增量启发式属性约简算法[8]；陈曦将新定义的两种信息熵结合，作为直觉模糊关系下信息系统的信息熵，并以该信息熵为启发式算子构造了一种属性约简算法[9]；陈东晓等基于属性重要度分别设计了熵协调和熵不协调的决策形式背景下的属性约简算法[10]；李萍等以粗糙模糊度为启发式算子对信息系统进行属性约简[11]；邓大勇等提出可变正区域约简，允许正区域在一定的范围内发生变化，从而提高泛化能力[12]；陈志恩等以粒包含度矩阵中隐含的信息作为启发式算子，设计了一种相容决策信息系统属性约简算法[13].

本文针对决策信息系统最大分部约简问题，从代数角度构建了一种新的启发式属性约简算法.该算法在核属性集基础上，将其它属性按其属性重要性大小逐次添加到核属性集中，再根据启发式算子对新的属性集做出最大分布约简的判断.重复以上步骤，直到找到最大分布约简.算例分析表明该算法的有效性和可行性.

2 基本概念

设S=(U,A,D)为一决策信息系统.其中U={x1,x2,…,xn}为对象的非空有限集合，即论域；A={a1,a2,…,am}为属性的非空有限集合；对任意a∈A,都存在映射aj∶U→Vj,Vj称为属性a的值域，j=1,2,…,m；任意B⊆A都对应U上的不可辨识关系

IND(B)={(x,y)∈U×U|∀aj∈B,aj(x)=aj(y)},

易见IND(B)为U上的一个等价关系，x基于B的等价类[x]B可表示为[x]B={y∈U|xBy},所有等价类的集合记为U/IND(B),简记为U/B；决策属性D导出的划分为U/D={D1,D2,…,Dr}.

若记

(1)

定义1[14]设S=(U,A,D)为一决策信息系统，B⊆A,若对任意x∈U， 有σA(x)=σB(x),则称B为最大分布协调集.若B为最大分布协调集，且B的任何真子集不是最大分布协调集，则称B为最大分布约简.

最大分布协调集保持了论域U中每个对象x在划分U/B下最大决策类不变的性质.

定义2设S=(U,A,D)为一决策信息系统，B(B⊆A)为S的最大分布协调集,若对任意a∈B,x∈U， 有σB(x)≠σB-{a}(x),则称a为B中必要的，否则称a为B中不必要的.B中所有必要属性组成的集合称为B的核，记为CORE(B).

如果对每一个a∈B，a都为B中必要的，则称B为独立的，否则称B是依赖的或不独立的.由此可知若B是最大分布协调集，且B是独立的.则B是S的一个最大分布约简.

定理1[14]设S=(U,A,D)为一决策信息系统，B⊆A,则B为最大分布协调集当且仅当对任意x，y∈U， 当σB(x)≠σA(x)时有[x]B∩[y]B=∅.

定义3[14]设S=(U,A,D)为一决策信息系统，U/A={C1,C2，…,Cm},记

D*={([x]A,[y]A),σA(x)≠σA(y)},

(2)

用fk(Ci)表示属性ak关于Ci的取值，则定义

(3)

为Ci与Cj的最大分布可辨识属性集.称MA={Dl(Ci,Cj)∶i,j≤m} 为S的最大分布可辨识属性矩阵,简称可辨矩阵.

显然，MA是对称矩阵，即Dl(Ci,Cj)=Dl(Cj,Ci)(∀i,j≤m} .

3 基于可辨矩阵的属性约简算法

3.1 基于可辨矩阵的属性约简

决策信息系统的最大分布约简就是在条件属性集中寻找一个最小的属性集，该属性集与条件属性全集所确定的最大决策分布完全一致.

定理2设S=(U,A,D)为目标信息系统，MA={Dl(Ci,Cj)∶i,j≤l} 为S的最大分布可辨识属性矩阵，对任意B⊆A,记

(4)

其中

若B满足条件：(i)γ(B)=1；(ii)对任意a∈B,γ(B-{a})=0,则B为S的一个最大分布约简.

证(i) 若γ(B)=1成立，则对任意Ci,Cj(i,j≤m),使得B∩Dl(Ci,Cj)≠∅ ,取x,y∈U,使得Ci=[x]A,Cj=[y]A,则有σA(x)≠σA(y),又因为B∩Dl(Ci,Cj)≠∅ ,则存在ak∈B,必有ak∈Dl(Ci,Cj),于是fk(Ci)≠fk(Cj),从而fk(x)≠fk(y),这说明[x]B∩[y]B=∅,于是由定理1知，B为S的一个最大分布协调属性集.

(ii) 对任意a∈B,γ(B-{a})=0,则存在Ci,Cj,(i,j≤m),使得

(B-{a})∩Dl(Ci,Cj)=∅ ,

取x,y∈U,使得Ci=[x]A,Cj=[y]A,则有σA(x)≠σA(y).因为(B-{a})∩Dl(Ci,Cj)=∅ ,则对任意ak∈B,必有ak∉Dl(Ci,Cj),于是fk(Ci)=fk(Cj),从而fk(x)=fk(y),这说明

[x]B-{a}∩[y]B-{a}≠∅,

由定理1知，B-{a}不是最大分布协调属性集，再由a的任意性知，B是独立的.

综合(i)、(ii)可知，B为S的一个最大分布约简.

3.2 算法原理和描述

定义4设S=(U,A,D)为目标信息系统，MA={D(Ci,Cj)∶i,j≤l} 为S的最大可辨识属性矩阵，B=(a1,a2,…,ar) (B⊆A)为S的一个最大分布约简，对任意ak∈B(k=1,2,…,r),记

(5)

显然，ξ(ak)的值越大，则表明属性ak最大分布决策分类的能力就越强，反之，则越弱.因此可利用ak在最大分布可辨识属性矩阵中出现的频数的大小来评价该属性的重要性.

在上述理论的基础上，本文以γ(B)为启发式算子，给出一种决策信息系统S的最大分布约简算法.该算法以最大分布核属性集为起点，然后根据定义4，逐次选择最重要的属性添加到核属性集中，再根据定理2对新的属性集做出最大分布约简的判断.重复以上步骤，直到满足终止条件.具体算法描述如下：

(i) 求核算法

输入：决策信息系统S=(U,A,D)；

输出：最大分布核属性集CORE(A)；

具体步骤：

第1步 赋值CORE(A)=∅；

第2步 计算S的最大分布可辨识属性矩阵MA；

第3步 ∀ak∈A,计算γ(A-{ak}),如果γ(A-{ak})≠1,则令CORE(A)=CORE(A)∪{ak},直到遍历条件属性全集中的每一个属性；

第4步 输出CORE(A),算法结束.

(ii) 基于可辨矩阵的属性约简算法

输入：决策信息系统S=(U,A,D)；

输出：决策信息系统S的一个最大分布约简B；

具体步骤：

第1步 计算S的最大分布可辨识属性矩阵MA及CORE(A)；

第2步 ∀ak∈ACORE(A),计算ξ(ak)；

第3步 令B=CORE(A)；

第4步 计算γ(B),如果γ(B)=1,则转到第6步，否则转到第5步；

第6步 输出B,算法结束.

在求核算法中，第2步计算可辨识矩阵MA的时间复杂度为O(|A||U|2),第3步计算核属性需要循环遍历所有属性，因此时间复杂度为O(|A||U|)；在基于可辨矩阵的属性约简算法中，第1步算法的时间复杂度为O(|A||U|2),第2步计算ξ(ak)的时间复杂度为O((|A|-|CORE(A)|)|U|),第3、4、5、6步皆为赋值操作，其时间复杂度为O(|1|).因此，计算基于可辨矩阵的属性约简最终时间复杂度为O(|A||U|2).

4 算例分析

给定一个决策信息系统S=(U,A,D),其中A={a1,a2,a3,a4}为条件属性，D={d}为决策属性(见表1).求解该决策信息系统的最大分布约简.

表1 决策信息系统S

在表1中，由等价关系可得

U/D={D1，D2},其中D1={x1,x4,x6,x8},D2={x2,x3,x5,x7}；

U/A={C1，C2，C3，C4},其中C1={x1,x3,x5},C2={x2,x6,x8},C3={x4},C4={x7}.

按照基于可辨矩阵的属性约简算法步骤：

首先，根据公式(1)计算论域中每个对象的最大决策分布(为了简化表示，用σA(Ci)代替σA(xk),其中xk∈Ci)为σA(C1)={D2},σA(C2)={D2},σA(C3)={D1},σA(C4)={D2}；

根据公式(2)计算：D*={(C1,C2), (C1,C3), (C2,C4), (C3,C4)}.

根据公式(3)计算得S的分布可辨识属性矩阵为

其次，根据公式(4),∀ak∈A,计算γ(A-{ak})得

γ(A-{a1})=γ(A-{a3})=γ(A-{a4})=1,γ(A-{a2})=0,

从而得核属性集CORE(A)={a2},ACORE(A)={a1,a3,a4}；

第三，根据公式(5),∀ak∈ACORE(A),分别计算ξ(ak)得：ξ(a1)=ξ(a4)=7,ξ(a3)=6；

第四，令B=CORE(A),计算得γ(B)=0,然后将a1(或a4)添加到核属性中去，并令B={a2,a1}(或B={a2,a4})，经计算γ(B)=1,从而算法结束，于是得{a2,a1}和{a2,a4}即为该决策信息系统S的两个最大分布约简.

根据最大分布约简{a2,a1},得到四组简化的最大分布决策规则表达式为

(a1,1)∧(a2,3)→(d,0)； (a1,2)∧(a2,3)→(d,1)；
(a1,3)∧(a2,3)→(d,1)； (a1,3)∧(a2,1)→(d,0).

5 结 论

传统的属性约简是在可辨识属性矩阵基础上，通过析取运算逐一消去所有Dl(Ci,Cj)中重复的元素，最后找到最大分布约简标准最小表达式.本文从代数的角度构建了一种新的启发式属性约简算法.该算法在最大分布可辨识属性矩阵基础上，以最大分布核属性集为起点，然后利用单个属性在可辨识属性矩阵中出现的频数来评价该属性的重要性，并逐次选择最重要的属性添加到核属性集中，再根据启发式算子对新的属性集做出最大分布约简的判断.重复以上步骤，直到找到最大分布约简.该算法简化了属性约简过程，提高了属性约简的速度.

致谢作者非常感谢相关文献对本文的启发以及审稿专家提出的宝贵意见.