基于属性近似度的决策信息系统属性约简算法研究＊

何银川

(汕头文化艺术学校计算机技术系，广东汕头 515065)

1 引言

1982 年，Pawlak 首次提出“粗糙集”[1]的概念。之后，随着粗糙集理论[2]在处理不精确、不完备等数据方面的优势，它逐渐被广大学者所熟知。作为粗糙集的核心内容，属性约简[3]是逐步从属性集中删除不必要属性来达到提高数据处理效率。目前，许多学者先后从知识划分[4]、贴近度[5]、互信息[6]、粒度[7-8]、等方面提出自己的属性约简改进算法。基于文献[4]的知识划分与文献[5]的贴近度，本文提出了属性近似度及相关属性约简算法。另外，为了提高算法效率，在求解约简时，本文逐步删除备选非核集属性集中的不必要属性，不用重复计算不必要属性的属性重要度。另外，如果在决策信息系统中动态增加条件属性，本文还能以原约简集为基础进行动态属性约简，降低了数据处理工作量。

2 基本概念

定义1[3]]设S=(U，C∪D，V，f)为决策信息系统，其中：①U为非空对象集合，又称论域，且U={x1，x2，…，xn}(n为论域U中对象个数)；②C为条件属性集，D为决策属性集，且C∩D=，D≠；③V为所有属性值域，且V={Va|a∈C∪D，Va是a 的值域}；④f：U×C∪D→V，即对任意的aC∪D，xU，均有f(x，a)Va。

定义2[3]设S=(U，C∪D，V，f)为决策信息系统，PC，对任意x、yU，则称[x]P={y|f(x，P)=f(y，P)}为U上的关于P的条件等价类，[x]D={y|f(x，D)=f(y，D)}为U上的关于D的决策等价类，U/P={[x]P|xU}为P针对U的划分，U/D={[x]D|xU}为D针对U的划分。

性质1[3]设S=(U，C∪D，V，f)为决策信息系统，P、QC，对任意对象xU，任意属性aP，则有：

(1)若PQ，则有U/QU/P，且[x]Q[x]P，此时称划分U/Q更精细，划分U/P更粗糙。

(2)若P=Q，则有U/P=U/Q，且[x]P=[x]Q，此时称P、Q划分能力相同。

(3)[x]P=∩[x]{a}。

3 属性近似度

结合文献[4，5]，本文先给出等价类近似度的定义。

定义3 设S=(U，C∪D，V，f)为决策信息系统，PC，对任意的xU，定义

则称s([x]P，[x]D)为对象x在P条件属性相对于决策属性的近似度，它度量的是[x]P在对象x下相对于[x]D的近似程度，其值越大，说明[x]P、[x]D越近似。

性质2 设S=(U，C∪D，V，f)为决策信息系统，PC，对任意的xU，则有1/|U|≤s([x]P，[x]D)≤1。

证明：对于任意的xU，则有{x}[x]P∩[x]DU，且[xi]P、[xi]DU，则知1≤|[x]P∩[x]D|≤|U|，且|[x]P|≤|U|，从而1/|U|≤s([x]P，[x]D)≤1。

定义4 设S=(U，C∪D，V，f)为决策信息系统，PC，定义

则称S(P，D)为条件属性集P相对于决策属性集D之间的属性近似度，其值越大，说明条件属性集P的分类能力越近似于决策属性集D。

性质3 设S=(U，C∪D，V，f)为决策信息系统，PC，则有1/|U|≤S(P，D)≤1。

证明：由性质2 可知1/|U|≤s([x]P，[x]D)≤1，则1≤s（[xi]P，[xi]D）≤|U|，1/|U|≤≤1，即1/|U|≤S(P，D)≤1。

定理1 设S=(U，C∪D，V，f)为决策信息系统，PC，S(P，D)=1的充分必要条件是对任意的xiU，有[xi]P[xi]D。

证明：①若S(P，D)=1，则有s([xi]P，[xi]D)=|U|，由性质2 可知，对任意的xiU，有s([xi]P，[xi]D)=1，即，s([xi]P，[xi]D)==1，|[xi]P∩[xi]D|=|[xi]P|，由集合论可知[xi]P[xi]D。

②若对任意的xiU，有[xi]P[xi]D，则|[xi]P∩[xi]D|=|[xi]P|，s([xi]P，[xi]D)=1，进而S(P，D)=1。

定理2 设S=(U，C∪D，V，f)为决策信息系统，PQC，则有S(P，D)≤S(Q，D)。

证明：若PQC，则由性质1(1)可知，对任意的xiU，有[xi]Q[xi]P，根据[xi]D、[xi]P、[xi]Q的关系，下面分三种情况讨论：

①若[xi]Q[xi]P[xi]D，对任意的xiU，有s([xi]P，[xi]D)=，同理可得，s([xi]Q，[xi]D)=，进而可得S(P，D)=S(Q，D)；

②若[xi]Q[xi]D[xi]P，对任意的xiU，有s([xi]P，[xi]D)=≤1，s([xi]Q，[xi]D)==1，进而可得S(P，D)≤S(Q，D)；

③若[xi]D[xi]Q[xi]P，对任意的xiU，有s([xi]P，[xi]D)=，s([xi]Q，[xi]D)=，由于[xi]Q[xi]P，所以|[xi]Q|≤|[xi]P|，1/|[xi]P|≤1/|[xi]Q|，|[xi]D|/|[xi]P|≤|[xi]D|/|[xi]Q|，进而可得S(P，D)≤S(Q，D)。

综合①②③可证得S(P，D)≤S(Q，D)。

定理2说明，随着P中属性的不断增加，P针对U的划分越精细，其相对于D的属性近似度越高，分类能力越强。

性质4 设S=(U，C∪D，V，f)为决策信息系统，P、QC，若S(P，D)=S(Q，D)，则对任意的xU，有[x]P=[x]Q。

定理3 设S=(U，C∪D，V，f)为决策信息系统，PC，对任意属性a、bC-P，若S(P∪{a}，D)=S(P，D)，则S(P∪{a}∪{b}，D)=S(P∪{b}，D)。

定理3说明，对于属性集PC，若添加非P属性a后，若P的属性近似度没有发生变化(即S(P∪{a}，D)=S(P，D))，那么在P∪{b}中添加非P属性a后，P∪{b}的属性近似度仍然不会发生变化，若在求解约简时，逐步从属性集中删除类似属性，将会大大减少计算量。

4 属性约简

4.1 属性重要度

定义5 设S=(U，C∪D，V，f)为决策信息系统，对任意属性aC，令SigC(a)=S(C，D)-S(C-{a}，D)，则称SigC(a)为a在C中的属性重要度。显然，SigC(a)度量的是从C中删除属性a后C相对于D的属性近似度变化程度。由于C-{a}C，由定理2 可知S(C-{a}，D)≤S(C，D)，即SigC(a)≥0。SigC(a)值越大，属性a相对于C的重要性就越高，SigC(a)值越小，属性a相对于C的重要性就越低，特别地，若SigC(a)=0，则称属性a相对于C是不必要的。

性质5 设S=(U，C∪D，V，f)为决策信息系统，对任意属性aC，a在C中是必要的充分必要条件是SigC(a)＞0。

性质6 核集Core(C)={aC|SigC(a)＞0}。

在使用核集进行启发式属性约简时，往往通过某种方法向核集中添加属性来得到约简，所以下面给出属性重要度的另一种定义。

定义6 设S=(U，C∪D，V，f)为决策信息系统，PC，对任意属性aC-P，令SigP∪{a}(a)=S(P∪{a}，D)-S(P，D)，则称SigP∪{a}(a)为属性a相对于P的属性重要度。显然，SigP∪{a}(a)度量的是在属性集P中增加属性a后P相对于D的属性近似度变化程度。由于PP∪{a}，由定理2 可知S(P，D)≤S(P∪{a}，D)，即SigP∪{a}(a)≥0。

定义7 设S=(U，C∪D，V，f)为决策信息系统，PC，对任意的属性aP在P中是必要的且S(P，D)=S(C，D)，则称P为C的一个约简。

4.2 基于属性近似度的属性约简算法

本算法以核集为初始约简集，之后依次添加符合要求的非核集属性来获得决策信息系统的约简。在此期间，为了简化算法复杂度，结合定理3，在添加非核集属性时，若某个属性对于当前约简集是不必要的，则将从C中直接删除，避免了对其属性重要度的重复计算，提高约简效率。

步骤1：令Red(S)=，Core(C)=，计算S(C，D)；步骤2：对任意属性aC，计算属性重要度SigC(a)，令Core(C)=Core(C)∪{a}(SigC(a)＞0)；步骤3：令Red(S)=Core(C)；步骤4：若S(Red(S)，D)=S(C，D)，则转向步骤6，否则转向步骤5；步骤5：对任意属性aC-Red(S)，计算属性重要度SigRed(S)∪{a}(a)，如果SigRed(S)∪{a}(a)=0，则令C=C-{a}。之后，将使SigRed(S)∪{a}(a)值最大的属性(当多个属性取得最大值时，任选一个)并入Red(S)中，转向步骤4；步骤6：算法结束，输出约简Red(S)。

4.3 实例分析

为了验证本算法的可行性与有效性，本文选取UCI数据集中的4 个决策信息系统Soyb、Zoo、Chess、Mushroom 进行实验对比，4个数据集的信息如表1所示（其中|U|、|C|分别为数据集的对象数和条件属性数）。本实验硬件环境为CPU Intel i32．4GHZ，Win7操作系统，编程工具为VC 6．0。

表1 UCI数据集

由于粗糙集只能处理离散化数据，所以本文采用等频区间法、语义等级划分法等方法对数据进行离散化。接下来，一方面，运用OGSAR算法[9]、ARGDE算法[10]和本文的ADAS算法分别对这4个数据集进行属性约简，得到属性约简结果如表2所示。

表2 属性约简结果对比

其中，|C|、|Red|分别为数据集的原条件属性数、约简集属性数。

从表3可知，三种算法的约简集基本一致，说明本文算法能正常地计算出约简集，在方法是可行的。

另一方面，为了验证本文算法的有效性，下面从约简时间上进行实验对比，实验结果如图1所示。

图1 三种算法约简时间对比

由图1可知，随着数据集的对象和属性个数不断增多，ADAS算法约简效率明显优于前2种算法，这是由于在属性集很大时存在较多的不必要属性，而ADAS算法能利用定理3从搜索空间中不断删除从备选非核集属性中删除不必要属性，该类属性不再参与后续属性重要度计算和约简工作，降低了数据处理工作量，提高了约简效率。

5 动态属性约简

针对决策信息系统中条件属性集动态变化而引起属性约简的变化，结合定义7，下面本文将给出基于属性近似度的动态属性约简算法，该算法不仅无需重新计算属性约简，还能在约简中添加非核属性时动态删除不必要属性，减少了算法的时间复杂度，提高了约简效率。

5.1 基于属性近似度的决策信息系统动态属性约简算法

下面给出该算法的算法描述。

输入：决策信息系统S=(U，C∪D，V，f)，S的属性约简Red(S)，新增条件属性集C’，新决策信息系统S’=(U，A∪D，V，f)，其中A=C∪C’。

输出：动态属性约简Red’(S’)。

步骤1：令Core(C’)=，Red’(S)=Red(S)，计算S(A，D)；

步骤2：对任意属性aC’，依次计算属性重要度SigA(a)，令Core(C’)=Core(C’)∪{a}(SigA(a)＞0)；

步骤3：令Red’(S’)=Red(S)∪Core(C’)；

步骤4：若S(Red’(S’)，D)=S(A，D)，则转向步骤6，否则转向步骤5；

步骤5：对任意属性aA-Red’(S’)，计算属性重要度SigRed′(S′)∪{a}(a)，如果SigRed′(S′)∪{a}(a)=0，则令A=A-{a}。之后，将使SigRed′(S′)∪{a}(a)值最大的属性(当多个属性取得最大值时，任选一个)并入Red’(S’)中，转向步骤4；

步骤6：对任意属性aRed’(S’)，若S(Red’(S’)-{a}，D)=S(Red’(S’)，D)，则属性a为新约简集不必要属性，令Red’(S’)=Red’(S’)-{a}，转向步骤7；

步骤7：算法结束，输出约简Red’(S’)。

其中，步骤2是用来计算新增条件属性集C’中是否有核属性，步骤6用来剔除新约简集中的不必要属性。

算法复杂度分析：对于步骤1，计算S(A，D)的时间复杂度为O((|A|+|D|)|U|)(|A|、|D|为新条件属性与决策属性个数)；对于步骤2，由于要对C’中每个属性a，计算属性重要度SigA(a)，共计|C’|次，此步骤的时间复杂度为O((|C’|+|D|)|U|)；对于步骤4，计算S(Red’(S’)，D)的时间复杂度为O(|Red’(S’)|+|D|)|U|)；步骤5 最坏情况下需要计算|A|(|A|+1)/2 次SigRed′(S′)∪{a}(a)，所以步骤5 的时间复杂度为O((|A|(|A|+1)/2+|D|)|U|)。由于决策属性集的属性个数一般为1，所以可知本算法的复杂度为O(|A|2|U|)，这与文献[10]的时间复杂度O(|C|2|U|)是一致的，并且比文献[9]的时间复杂度O(|C||U|2)要低。

5.2 实例分析

接下来，本文选取UCI数据集中的Chess、Mushroom数据集（如表1所示）进行实验对比，本实验环境与4．3节一致。在本节实验中，选择本文4．3 节提出的ADAS 算法（非动态算法）和DADAS 算法（动态算法）。实验中，本节将数据集的60%条件属性作为初始数据集，之后依次以10%的条件属性个数作为增量条件模拟4次属性动态变化过程，可得约简时间如图2、3所示。

由图2、3 可知，DADAS 算法（动态算法）所用时间远远小于ADAS算法（非动态算法），并且随着增加属性量增多用时趋势越明显。这主要由于ADAS 算法（非动态算法）在每次数据动态更新后需要重新计算新数据集的属性约简，随着对象个数增多用时会越来越大，而DADAS算法（动态算法）在求解属性约简时，每次是以上次约简集为基础进行求解新约简集，仅需处理新增数据，减少约简工作量，节省了大量存储空间，而且还能对约简集进行精简，剔除约简集中不必要属性。所以，在不同数据集实验对比中，动态属性约简算法性能要优于非动态属性约简算法。

图2 Chess数据集实验对比

图3 Mushroom数据集实验对比

6 结束语

随着粗糙集在许多领域内的成功应用，关于粗糙集的研究成果层出不穷。属性约简作为粗糙集理论的核心内容之一，旨在寻找不影响整体分类能力的最小属性集。在等价类近似的基础上，本文提出了属性近似度，用以从整个论域角度反映条件属性集与决策属性集的近似程度。为了更好地度量属性的重要性，本文先后提出了两种方法用以度量属性集P中的属性及非P属性关于P的属性重要度，并先后给出了两种基于属性近似度的决策信息系统属性约简算法。最后，通过实例验证了算法的有效性，为决策信息系统的知识发现提供了新的研究思路。