0 引言

属性约简是粗糙集理论的重要研究内容之一.目前许多属性约简的方法是基于核属性的，因此，求核是这些方法的基础.常见的核属性求解方法有：基于正区域的方法^[1]、基于信息熵的方法^[2-3]和基于差别矩阵的方法^[4-7].然而，基于核定义求核过程比较烦琐.文献[4]给出一种较简单的基于差别矩阵的求核方法，其时间与空间复杂度均为O(|C||U|²)；文献[5]通过实例揭示文献[4]方法应用于不相容决策表信息系统时，存在所求核与正域核不一致的不足，同时给出差别矩阵新定义及求核方法；但是该方法的时间与空间复杂度与文献[4]相同，故求核效率并没有得到改善.为了提高求核效率，文献[6]给出一种改进差别矩阵的定义及求核算法，求核效率比文献[4-5]有所提高，其时间复杂度为max(O(|C||U|lg|U|), O(|C||U₁||U|))，空间复杂度为O(|C||U₁||U|).文献[7]在文献[6]的基础上，对差别矩阵求核算法做了进一步改进，首先将决策表中重复数据进行合并，然后利用差别矩阵的定义进行求核计算，其时间复杂度为max(O(|C||U|), O(|C||U′/C||U′₁|))，空间复杂度为O(|C||U′/C||U′₁|).若决策表数据中不存在重复数据，则文献[6-7]所涉及的时间和空间复杂度是等同的.

通过对差别矩阵的研究，本文提出一种压缩差别矩阵的构造方法及相关的属性集求核算法.所提算法能够有效减少差别矩阵中大量的空值存储，并且避开对象之间的盲目比较，由此设计的求核算法的时间复杂度为max(O(|C||U₁||U₂|), O(|C′||U′₁|²))，空间复杂度为max(O(|C||U′₁||U′₂|), O(|U′₁|²))，提高了属性核求解效率.

1 基本概念

决策表信息系统S=(U, C, D, V, F)，U={x₁, x₂, …, x_n}为非空有限论域，C={c₁, c₂, …, c_m}为条件属性集，D为决策属性集且C∩D=∅，V=∪_b∈C∪DV_b，其中V_b表示属性b的值域.信息函数F:U×(C∪D)→V为对象赋属性值，即∀b∈C∪D，x∈U，有F(x, b)∈V_b.令R⊆C∪D且R≠∅，则ind(R)={(x_i, x_j)|F(x_i, b)=F(x_j, b), ∀b∈R}称为S的不可区分等价关系，其含x的等价类记为[x]_R，U/R表示等价关系ind(R)确定的等价类集.设b∈R，若ind(R)=ind(R-{b})，则称b是R中不必要的，否则，称b是R中必要的.设P, Q⊂C∪D，Q的P正域为POS_P(Q)=∪_X∈U/QP(X)，其中P(X)={x∈U[x]_P⊆X}.

定义1^[4]   决策表信息系统S=(U, C, D, V, F)中，b∈C，如果POS_C(D)=POS_C-{b}(D)，则称b为C中相对D不必要的；否则，称b为C中相对D必要的.C中所有必要属性的集合称为C相对D的核，记为core_C(D).

定义2(不相容决策表的差别矩阵)^[6]  决策信息系统S=(U, C, D, V, F)中，令U/D={y₁, y₂, …, y_v}，相容子论域${{U}_{1}}=\cup _{i=1}^{h}\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{C}({{y}_{i}})\left( h\le v \right)$，不相容子论域U₂=U-U₁.差别矩阵IDM=(m_ij)的元素确定如下：

$ {{m}_{ij}}=\left\{ \begin{align} &\{b\in C|F({{x}_{i}}, b)\ne F({{x}_{j}}, b)\}, \forall {{x}_{i}}, {{x}_{j}}\in {{U}_{1}}, d\in D, F({{x}_{i}}, d)\ne F({{x}_{j}}, d); \\ &\{b\in C|F({{x}_{i}}, b)\ne F({{x}_{j}}, b)\}, \forall {{x}_{i}}\in {{U}_{1}}, {{x}_{j}}\in {{U}_{2}}; \\ &\varnothing, 其他 \\ \end{align} \right. $

命题1   $cor{e_C}\left( D \right) = \{ \alpha \left( {\alpha \in C} \right) \wedge (\exists {m_{ij}}(({m_{ij}} \in \mathit{\boldsymbol{IDM}}) \wedge ({m_{ij}} = \left\{ \alpha \right\}) \wedge {m_{ij}} = 1))\} .$

定义2表明，差别矩阵算法求不相容决策表信息系统中核属性时，首先将论域U中所有对象分为完全相容子论域U₁与完全不相容子论域U₂，其次将U₁中对象两两比较，并将U₁中的对象与U₂中的对象两两比较，最后根据命题1从差别矩阵中找出简单属性(单个属性).

2 基于差别矩阵的属性集求核算法 2.1 差别矩阵的空值

根据定义2可知，差别矩阵求解核属性时会出现空值，这些空值元素的出现会占用大量存储空间，使得求核属性浪费了大量计算时间.因此，提出一种压缩差别矩阵的构造方法.

定理1(空值优化)  在决策表信息系统S=(U, C, D, V, F)中，记相容子论域U₁={x₁, x₂, …, x_k}.当x_i, x_j∈U₁∧F(x_i, D)=F(x_j, D)时，则忽略对象x_i，x_j的比较运算.

证明  因∀x_i, x_j∈U₁(1≤i≠j≤k)，所以信息系统S中，∀b∈C存在如下关系：① F(x_i, b)=F(x_j, b); ② F(x_i, b)≠F(x_j, b).由定义2知，当∀x_i, x_j∈U₁, F(x_i, d)≠F(x_j, d)时，m_ij={b∈C|F(x_i, b)≠F(x_j, b)}，否则，m_ij=∅.因此，差别矩阵中的空值与条件属性值的取值无关；显然，当∀x_i, x_j∈U₁∧F(x_i, D)=F(x_j, D)时，忽略对象x_i，x_j的比较运算.

算法1  空值优化执行过程.

输入：决策表S=(U, C, D, V, F)；输出：可以忽略比较的对象.

步骤1  得到完全相容子论域U₁与完全不相容子论域U₂, 记U₁={x₁, x₂, …, x_|U1|};

步骤2   L=∅;//L用于收集U₁中可以忽略比较的对象；

步骤3   for(i=1;i < |U₁|; i++)

          for(j=2;j≤|U₁|; j++)

               if(F(x_i, D)=F(x_j, D))

                   L=L∪{x_i, x_j};

步骤4  输出L.

算法1以决策表信息系统中的决策属性值D为划分依据，将论域U划分成相容子论域U₁与不相容子论域U₂，然后对U₁中的对象按照决策属性值的不同划分成多个对象集，进而减少当决策属性值相同时的不必要计算，同时也压缩了差别矩阵中空值元素.一般情形下，算法1的时间复杂度为O(|U₁|²).在实际应用中，上述算法虽然有2个循环，但是内循环在循环过程中，当对象x_i与x_j可以忽略比较，对象x_i与x_k(k≠j)可以忽略比较时，由传递性可得对象x_j与x_k可以忽略比较.因此, 算法在执行过程中减少了内循环次数，即算法1的时间复杂度为O(|U₁|).

2.2 差别矩阵的属性集求核机理

在决策表信息系统S中，若∀b∈C, x_i, x_j∈U₁，F(x_i, b)=F(x_j, b)∧F(x_i, D)=F(x_j, D)成立，或∀b∈C, x_i, x_j∈U₂，F(x_i, b)=F(x_j, b)∧F(x_i, D)≠F(x_j, D)成立，则利用差别矩阵算法求得的属性集相同，这不但占用大量存储空间，而且也浪费了大量计算时间.

定义3(决策表化简)   在决策表信息系统S=(U, C, D, V, F)中，定义新决策表S′=(U′, C, D, V′, F′).信息函数F′满足：F′(x_i, C)=F(x_i, C)，d∈D且

$ F\prime ({{x}_{i}}, d)=\left\{ \begin{align} &DU+1, \forall {{x}_{i}}\in {{U}_{2}}, \exists {{x}_{j}}\in {{U}_{2}}, F({{x}_{i}}, C)=F({{x}_{j}}, C)\wedge F({{x}_{i}}, d)\ne F({{x}_{j}}, d)时, \\ &将对象{{x}_{i}}, {{x}_{j}}进行合并, DU为累计合并次数; \\ &F({{x}_{i}}, d), \forall {{x}_{i}}\in {{U}_{1}}, \exists {{x}_{j}}\in {{U}_{1}}, F({{x}_{i}}, C)=F({{x}_{j}}, C)\wedge F({{x}_{i}}, d)=F({{x}_{j}}, d)时, \\ &将{{x}_{j}}从S中删除, 取{{x}_{i}}中决策属性值; \\ &F({{x}_{i}}, d), 其他. \\ \end{align} \right. $

进而，F′自然确定U′与V′.

根据定义2可知，当∀x_i∈U₁, x_j∈U₂时，m_ij≠∅.当Ǝx_k∈U₂∧F(x_k, C)=F(x_j, C)∧F(x_i, d)≠F(x_j, d)成立，则m_ij=m_ik.又因x_j, x_k∈U₂，根据定义2可知m_jk=∅.故在利用差别矩阵求解核属性时，当∀x_j, x_k∈U₂时，将U₂中具有“相同条件属性值但不同决策属性值”的对象进行合并不影响核属性的求解结果.在决策表S′中，∀x_i, x_j∈U′，b∈C，均有|m_ij| < C.基于定理1与定义3，下面分析差别矩阵的属性集求核机理.

定理2  当m_ik⊂m_jk∧|m_jk|-|m_ik|=1∧{(x_i, x_j)|F(x_i, b)≠F(x_j, b)}=∅, ∀b∈m_ik时，m_ij=m_jk-m_ik∧|m_ij|=1.

根据定理2可知，当m_ik∩m_jk=∅时，显然m_ij={m_ik∪m_jk}∧|m_ij|≥2.定理2揭示了核属性集的关系，即在对象x_i，x_j比较之前，先判定属性集m_ik与m_jk是否满足数量之差为1.若为1，则判定m_ikm_jk是否成立.因m_ik，m_jk中的属性集合是有序的，因此判断m_ik⊂m_jk时，其时间复杂度为max(O(|m_jk|)).

定义4(改进差别矩阵)  决策表信息系统S′=(U′, C, D, V′, F′)中，令U′/D={y′₁, y′₁, …, y′_v}，相容子论域${{{{U}'}}_{1}}=\cup _{i=1}^{h}\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{C}({{{{y}'}}_{i}})\left( h\le v \right)$，不相容子论域U′₂=U′-U′₁.改进差别矩阵SIDM=(m′_ij)的元素确定如下：

$ {{{{m}'}}_{ij}}=\left\{ \begin{align} &\{b\in C|F\prime ({{x}_{i}}, b)\ne F\prime ({{x}_{j}}, b)\}\forall {{x}_{i}}\in {{{{U}'}}_{1}}, {{x}_{j}}\in {{{{U}'}}_{2}}; \\ &—, 当\forall {{x}_{i}}, {{x}_{j}}\in {{{{U}'}}_{1}}, F\prime ({{x}_{i}}, D)=F\prime ({{x}_{j}}, D); \\ &\varnothing, 其他. \\ \end{align} \right. $

其中:“—”表示无需考虑比较的对象.

基于定义4求不相容决策表信息系统中核属性时，只需要将U′₁和U′₂中对象两两比较，并利用定理2属性集求核机理求解核属性.进而，根据命题1从差别矩阵中找出单个属性.

2.3 属性集求核算法描述

假设论域U′中前|U′₁|个为完全相容子表，U′₂=U′-U′₁为论域U′中完全不相容子表.采用分布计数的基数排序思想求解等价类^[7]，即求解U′/C时的时间复杂度为O(|C||U′|).获得U′₁和U′₂的时间复杂度为O(|U′/C||U′/D|)，其中U′/C表示按照条件属性集C划分后等价类的数目，U′/D表示按照决策属性集D划分后等价类的数目.上述过程与文献[6-7]中求相容子表与不相容子表的过程是一致的，即上述过程中算法的时间复杂度为O(|C||U′|)+O(|U′/C||U′/D|).

算法2  基于差别矩阵的属性集求核算法.

输入：决策表信息系统S=(U, C, D, V, F)；输出：决策表信息系统的核core_C(D).

步骤1   执行算法1;

步骤2  根据定义3创建新的决策表S′;

步骤3   core_C(D)=∅, core1_C(D)=∅, core2_C(D)=∅;

步骤4   for(i=1;i≤|U′₁|; i++)

          for(j=|U′₁|+1;j≤|U′|; j++)

              m′_ji=∅;M=∅;//用于存储属性集m_{|U′1|+1, i}

              for(r=1;r≤|C|; r++)

                if(F(x_i, c_r)≠F(x_j, c_r))

                  m′_ji=m′_ji∪{c_r};

                  M=M∪m_{|U′1|+1, i};

                  if(|m′_ji|=1)

                    core1_C(D)=core1_C(D)∪m′_ji;

步骤5   m′_ji=∅;M=M∪m_{|U′1|+1, i};

步骤6   for(i=1;i≤|U′₁|-1;i++)

        for(j=i+1;j≤|U′₁|; j++)

            if (|m_{|U′1|+1, i|}-|m_{|U′1|+1, j}|=1)

                执行定理2;

                m′_ji=m_{|U′1|+1, i}-m_{|U′1|+1, j};

                if (|m′_ji|=1)

                core2_C(D)=core2_C(D)∪{m′_ji};

步骤7   core_C(D)=core1_C(D)∪core2_C(D);

步骤8   输出core_C(D).

在算法2中，步骤1时间复杂度为O(|U′₁|)；步骤2时间复杂度为O(|U′₂|)；步骤4时间复杂度为O(|C||U′₁||U′₂|)；步骤6时间复杂度为O(|C′|)=O(max(m_{|U′1|+1, i})) < O(|C|).因此，算法2的总时间复杂度为max(O(|C||U₁||U|₂), O(C′U′₁²))，空间复杂度则为max(O(|C||U′₁||U′₂||), O(|U′₁|²)).在利用差别矩阵求核过程中，以往的算法需要将每个对象两两进行比较求解核属性.然而，随着对象数目的增多，其算法复杂度在逐渐增大，求取的时间也会越来越长.而且在决策表信息系统中，两个对象之间可能具有相同的条件属性值和大量空值.算法2基于差别矩阵来实施属性集求核思想，用完全相容子表与完全不相容子表之间进行比较，然后利用定理2求得所有的核属性值.

通过比较可知，本文算法的时间和空间复杂度均低于文献[6]和文献[7]所提算法的时间和空间复杂度.

3 实例分析

利用一个决策表实例(表 1)来说明本文的求核算法，差别矩阵元素均采用简单形式.其中c₁、c₂、c₃为条件属性，D={d}为决策属性集，共有8个样本对象.根据定义3可知，F′(x₃, d)=3.化简后的决策表S′如表 2所示.其中U′₁={x₁, x₆, x₇, x₈}，U′₂={x₃}.根据定理1知，在表 2中，对象x₁、x₆、x₈是不需要做比较运算的.

在表 2基础上，根据定义4方法构建差别矩阵SIDM, 如表 3所示.分析差别矩阵SIDM可知core_C(D)={c₁, c₂}.

如果采用文献[6]方法创建差别矩阵IDM为5×8规模, 如表 4所示，共有40个元素；如果采用文献[7]方法创建差别矩阵IDM′为4×5规模，如表 5所示, 共有20个元素.采用本文方法创建的差别矩阵SIDM为2×4规模，实际存储的元素为7个.可见采用本文方法既减少了样本对象的个数，又降低了差别矩阵的空间占用，从而减少了数据的处理量，提高了求核效率.事实上，基于表 1和表 2，“表 4→表 5→表 3”的改变过程清楚地体现了“文献[6]→文献[7]→本文”3种算法的差别矩阵改进过程.

4 实验结果

采用文献[7]中使用的UCI数据集(http://archive.ics.uci.edu/ml/datasets.html)，在Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz、RAM 2 GB环境下，对文献[6]、文献[7]与本文算法进行了比较.UCI数据集及其特征如表 6所示，其中|U/C|表示按照条件属性集C划分后等价类的数目；|IDM|、|IDM′|、|SIDM|分别表示文献[6]、文献[7]以及本文算法差别矩阵实际存储元素的个数.可以看出，本文算法创建的简化差别矩阵中所存储的元素数目|SIDM|要少于文献[6]和文献[7]差别矩阵中存储的元素个数.

图 1与图 2分别给出3种算法在4种UCI数据集上执行时间与执行空间的比较.基于图 1，本文求核算法的执行效率要优于文献[6]和文献[7]的求核算法，并且随着样本对象的增加，该算法效率更加明显.基于图 2，对于不相容决策表(如Patient与Car)和包含重复元素比较多的决策表(如Cancer)，本文求核算法在执行过程中对存储空间的需求小于文献[6]和文献[7].

5 结束语

文献[4]的求核算法不能处理不相容决策表，存在一定的局限性.文献[5]提出了改进算法，并解决了文献[4]算法不能处理不相容决策表的问题，但该算法的时空效率并不太理想.文献[7]则在文献[6]的基础上，对决策表中相同对象合并来提高求核效率.研究发现，利用差别矩阵求解核属性的算法效率还能得到进一步的提高.因此，本文提出了一种基于差别矩阵的属性集求核算法.该算法首先将决策表划分成相容与不相容部分；其次运用定理1找到可以忽略比较的对象，运用定义3化简决策表.算法2给出了基于差别矩阵的属性集求核算法伪码，由此设计的算法的时间与空间复杂度均低于文献[6]和文献[7]的时间与空间复杂度，实验结果表明该算法是有效的.