波兰的数学家Pawlak在20世纪80年代提出的粗糙集是一种新型的用来处理不完全、不精确与不相容的数学工具和理论^{[1, 2]}。经过了30多年的研究和发展，粗糙集理论已在知识发现、数据挖掘、模式识别等领域得到了大量应用^{[3, 4]}。属性约简作为粗糙集理论的重要研究内容，已被广大学者所研究，提出了围绕完备决策表的属性约简算法，但是现实生活中的数据往往存在误差，缺失及多源等特征。如何对不完备决策表进行直接处理，已成为粗糙集理论的一个研究热点^[4]。近年来针对不完备决策表的研究也取得了显著的进步，已有学者提出很多有效的不完备决策表属性约简算法^{[5, 6, 7, 8, 9, 10, 11]}。知识粒度^{[12, 13]}作为粗糙集理论中度量属性约简的重要方法之一，被广泛运用于不完备属性约简算法。文献^[5]以属性重要性为启发信息,设计了一个基于知识粒度的属性约简算法^[5];文献^[6]通过不断向核属性集中添加属性的方法，设计出一种基于相对知识粒度的不完备决策表属性约简算法^[6]；文献^[7]定义了一个粒度差别矩阵，进而设计了基于知识粒度的不完备决策表的属性约简算法^[7],其时间复杂度 为max{O(|C|²|U||U_pos|)，O(|K||C|U|)}，其中K=max{|T_C(x_i)|,x_i∈U},其空间复杂度为max{O(|C||U||U_pos|),O(|U|)};文献^[8]给出了一个计算条件属性频率的公式，设计一个基于知识粒度的属性约简算法^[8]；文献^[9] 设计了一种基于对象矩阵的属性约简算法^[9]；文献^[11]提出简化差别矩阵定义，设计了一种快速的属性约简算法^[11]；文献^[12]中根据区分对象对集的思想，设计了基于正区域的属性约简算法^[12]；文献^[13]根据粒计算的思想构建了粒矩阵，在此基础上，设计了属性约简算法。文献^[14]在粒计算属性约简算法的基础上进行了改进，得到一个新的算法。上述算法大多因为要多次计算知识粒度，导致计算效率都不太理想，为此设计出基于知识粒度的高效属性约简算法具有非常重要的现实意义^[5]。

差别矩阵作为粗糙集理论的重要技术之一，被广泛应用，但是求解差别矩阵费时，本文引入了基于粒度的差别矩阵，利用条件属性在区分对象时出现频率的属性约简思想，设计一个基于粒度差别矩阵计算属性频率的启发函数。

定义1^[3] 五元组 S=(U,C,D,V,f)是一个不完备决策表，其中U={x₁,x₂,…,x_n}表示对象的非空有限集合，称为论域； C={c₁,c₂,…,c_m}表示条件属性的非空有限集合； D表示决策属性的非空有限集合，且 C∩D=∅； V_a,V_a是属性a的值域；f:U×C∪D→V是一个信息函数，它对一个对象的每一个属性赋予一个信息值，即∀a∈C∪D,x∈U，有f(x,a)∈V_a。

在五元组中，如果至少有一个属性a∈C，使得 V_a包含空值(用*表示)，即至少有一个属性a∈U，存在一个a∈U，使得f(x,a)=*，称之为不完备决策表。

定义2^[3] 在不完备决策表 s=(U,C,D,V,f)中，令B⊆C，定义U上的容差关系 T(B)为T(B)={(x,y)∈U×U|∀b∈B}，f(x,b)= f(y,b)∨f(x,b)=*∨f(y,b)=*}。用T_B(x)表示在B中与x具有容差关系的全体对象集{y∈U|(x,y)∈T(B)}。

定义3^[16] 在不完备决策表 S=(U,C,D,V,f)中 ,知识B⊆C的知识粒度定义为GD(B)= .其中U={x₁,x₂,…,x_n},|X|表示集合X的基数. 显然有CD(∅)=0。

性质1^[16] 设S=(U，C，D，V，f)是一个不完备信息系统，知识B⊆C的知识粒度定义为 GD(B)，则1/|U|≤GD(B)≤1。

性质2^[16] 设 S=(U,C,D,V,f)是一个不完备信息系统，其中P,Q⊆C，如果 ∀i∈{1,2,…,|U|}有T_P(x_i)⊆T_Q(x_i)，则GD(P)≤GD(Q)。

知识粒度可以描述知识的区分能力,知识粒度越小,其区分能力越强，反之区分能力越弱^[5]。

定义4^[5] 在不完备决策表 S=(U,C,D,V,f)中 ,知识B(B⊆C) 是C关于D的一个知识粒度的属性约简,当且仅当B满足条件:

1)GD(B)=GD(C);

2)∀b∈B⇒GD((B-{b}))≠GD(C)。

定义5^[7] 在不完备决策表 S=(U,C,D,V,f)中,∀B⊆C,U/D={D₁,D₂,…,D_K}表示由决策属性集D对论域U的划分，称为C关于D的正区域，设条件属性对论域的划分为U/C={[x_i1]_c, [x_i2]_c,…,[x_ik]_c}，U_pos={ x_ij|[x_ij]_c⊆POS_C(D)},U_neg= U-U_pos。

定义6^[11] 设在一个不完备决策表 S=(U,C,D,V,f)中，U=U_pos∪U_neg,定义粒度差别矩阵M=(m(i,j)),其元素定义如下：

定义7^[7] 设M =(m(i,j))为不完备决策表S=(U,C,D,V,f)的粒度差别矩阵,∀B⊆C,若B满足：

1)∀∅≠m(i,j)∈M,有B∩m(i,j)≠∅;

2)∀a∈B,B′=B-{a}均不满足(1)。

则称B是C关于D的一个属性约简，此约简记为基于粒度差别矩阵的属性约简。

定理1 在不完备决策表S=(U,C,D,V,f) 中，有R_C=∪a∈CR_{a}。

证明 由定义1知：命题显然成立。

定理2^[7] 基于知识粒度的属性约简定义与基于粒度差别矩阵的属性约简定义是等价的。

定理2说明基于知识粒度的属性约简可以转化到粒度差别矩阵上进行。

针对不完备决策表，文献^[7]中给出了一个基于粒度差别矩阵的属性约简算法，其时间复杂度为max{O(|C|²|U _pos||U|),O(K|U||C|)}。算法对粒度差别矩阵进行遍历，若只包含一个条件属性就将其放入属性约简中，并去掉差别矩阵中任何含有该条件属性的差别元素,直至差别矩阵为空。该算法 虽然有效降低了时间复杂度，但是构造粒度差别矩阵仍然需要占用大量的空间，对于处理大型数据集仍然具有一定的难度。

经分析，算法中在粒度差别矩阵中出现的条件属性才是能区分对象的条件属性，由于构造粒度差别矩阵耗费空间，参考文献^[16]的方法，设计一种计算粒度差别矩阵中含有的条件属性频率的函数，然后给出计算该函数的快速算法，无须构造粒度差别矩阵就可以将其中能有效区分对象的条件属性找出，以降低算法的时间和空间复杂度。

定理3 在决策表 S=(U,C,D,V,f)中，B⊆C，U/B={A₁,A₂,…,A_l} ，A_i/{a}={A_i1,A_i2,…,A_ik}， A_ij=pos_i∪Neg_j，U=U_pos∪U_neg，其中pos_i=A_ij∩U _pos,Neg_j=A_ij∩U_neg,pos_i/D={D_i1,D_i2,…,D_iD},Neg_j/D=。令s_i=|pos_i/D|=|D||D_ij|=|pos_i|,则所有集合中属于正域的集合对D划分pos_i/D总和为S= S= pos_i|，所有集合中属于正域的所有集合对D划分 pos_i/D中决策值相同集合总数为 T_j=D_ij。

根据定义6，粒度差别矩阵中包含的条件属性可由两部分产生，设对象都在U_pos里产生的条件属性的个数为

两个对象一个在U_pos中，另一个在 U_neg中，产生的条件属性频率为N₂，则

证明 由粒度差别矩阵的定义知，计算 A_i/{a}={A_i1,A_i2,…,A_ik}产生的条件属性频率，可分两部分计算，一种是对象都在 U_pos 中;另一种是一个在U_pos中，而另一个在U_neg中的。

1)若两个对象都在U_pos中，由划分的定义知，在同一个划分集合里的两个对象值相等，即只有不同划分集合里才有可能产生有效区分对象的条件属性。则只有不同划分集合的 U_pos之间才能产生条件属性频率；若两个对象都在U_pos中，产生的条件属性频率为N₁=pos_ipos_j，任意两个划分集合都可产生，因为在正域之间产生的差别矩阵的元素是对称的，故条件属性频率为2N₁。

2)若一个对象在U_pos中，另一个对象在U_neg中，由划分的定义知，同属一个集合里的两个对象值相等，即只有不同划分集合里才有可能产生条件属性频率，且U_pos和U_neg之间要求决策值不同，故需要对每个划分集合里属于U_pos的集合对D划分，同时属于U_neg的集合也对D划分。所以，Neg_j/D划分集合里每个集合与pos_i/D划分集合里对于决策属性在不同划分集合里就能产生条件属性频率。

为了方便叙述，假设将A_i{b}所有集合中属于正域的所有集合对D划分pos_i/D存放在一个矩阵中，矩阵的行表示每一个非空集合对D的划分，矩阵的列表示决策值相同的集合，生成的矩阵为

同理，将A_i{b}所有集合中属于负域的所有集合对D划分 Neg_j/D存放在另一个矩阵中，生成的矩阵为

从这两个矩阵中可以看出，$\bar D$_ij 只能与式(4)矩阵中与其不同行不同列的集合产生条件属性频率，为了求得所有条件属性频率且不重复计算，在式(4)矩阵中，定义任一行的和，即S_i=|pos_i/D|=D_ij|=|pos_i|，则所有行的总和S_i。

定义任一列的和：T_j=D_ij。

则若两个对象一个在 U_pos中，另一个在U_neg中，产生的条件属性频率 N₂=$\bar D$(S-S_i-T_j+D_ij)。故 F_B(U,a)=(2N₁+N₂)表示简化决策表中所有对象相对于条件属性集B产生的条件属性频率的总个数，证明完毕。

根据定义6可知，只有属性值不同且不为缺省值的才能包含条件属性，所以在本文的所有算法中，对象 U对属性a的划分，将含有缺省值的放在划分的最后一个集合里，不予处理。

首先，对不完备决策系统中的对象进行划分。

算法1 论域U对属性a的划分

输入 不完备决策表S=(U,C,D,V,f)，C={a₁,a₂,…,a_m}，U={x₁,x₂,…,x_|U|}

输出 U/a={A₁,A₂,…,A_t}

1)t=1；A_t={x_i}；

2)for(j=2;j<|U|+1;j++)。

若任一条件属性a_i∈C(i=1,2,…,|C|) 均有f(x_i,a_i)=f(x_j,a_i)≠*，则A_t=A_t∪{x_j}；否则t=t+1;A_t={x_j}；(其中在此求划分时*单独放到一块)。

3)输出U/a={A₁,A₂,…,A_t}。

算法1中，1)、3)时间复杂度忽略不计，2)的时间复杂度为O(|U|)，则算法2的时间复杂度是 O(|U|)，空间复杂度为O(|U|)。

算法2 求条件属性频率的函数

输入 U/A={A₁,A₂,…,A_t}，条件属性的最大值和最小值分别标记为M_b,m_b；

输出 U/(A∪{b})，条件属性频率函数|F_a(U,b)|；

1)|F_A(U,b)|=0，U/(A∪{b})=∅；

2)对∀A_i={x₁,x₂,…,x_j}∈U/A,以静态链表为存储空间，依次放入对象x₁,x₂,…,x_j;令表头指针指向x_i;

①建立M_b-m_b+2空队列，令front[k]和end[k](k=0,1,2,…,M_b-m_b+1)分别为第k个队列的头指针和尾指针，将链表中的对象x∈A_i按链表中的次序分配到第f(x,b)-m_b个队列中去，将链表中的对象值为*的对象分配到*队列中。

②对除*队列的每个非空队列作如下处理：

a)将非空队列中属于U_pos的对象放入 pos_i(i=0，1,2,…,k)中，属于U_neg的对象放入Neg_i(i=1,2,…,k)中。并计算两个对象都在U _pos中产生的条件属性频率N₁，则N₁=pos_ipos_j。

b)计算每个非空队列中pos_j/D= {D_j1,D_j2,…,D_j|D|}， Neg_j/D={D_j1,D_j2,…,D_j|D|}，则在正域矩阵中S_i=|pos_i/D|=D_ij|,S=S_i所有集合中属于正域的所有集合对D划分pos_j/D中决策值相同集合总数为T_j=D_ij。一个对象在U_pos中,一个在U_neg中，产生的条件属性总频率为N₂= $\bar D$_ij(S-S_i-T_j+D_ij) ，产生的条件属性总频率为|F_A(U,b)|=2N₁+N₂；

3)输出U/(A∪{b})，条件属性总频率数|F_A(U,b)|。

算法时间空间复杂度分析：算法2中1)的时间复杂度忽略不计，2)①的时间复杂度为O(|A_i|)，设pos_i/{b}={A_i1,A_i2,…,A_ik}，则2)②a时间复杂度为O(A_ij)(j=1,2,…,k)，2)②b时间复杂度为O(A_ij)，即2)②时间复杂度为 O(|A_i|)，2)时间复杂度 O(|A_i|)+O(|A₂|)+…+O(|A_i|)≤O(|U|)。故算法2的最坏时间复杂度为O(|U|)，同理可得最坏空间复杂度为O(|U|)。

算法3 以条件属性的频率为启发信息的属性约简算法

输入 不完备决策表S=(U,C,D,V,f),C=(c₁,c₂,…,c_m),U={x₁,x₂,…,x_n}；

输出 属性约简Red(C)。

1)由文献^[11]求出容差类T_ci(x_i)(x_i∈U)， U_pos,U_neg计算知识粒度|GD(c_i)|=|T_ci(x_i)|/|U|²，令|K_i|=GD(c_i)；

2)将K_i按从小到大运用快速排序方法得到 |K_i1|≤ |K_i2|≤…≤|K_im|，它们对应的属性为 c_i1，c_i2,…,c_im令 Red(C)={c_i1}；

3)for(k=2,k ＜m+1;k++)

由算法3计算；|F_red(U,c_i(k-1))|

4)输出属性约简Red(C)。

算法正确性分析：若|F_Red(U,c_i(k-1))|=0，即当前属性不能将两个对象区分开，则R_Red∪{cik}=R_Red，则由算法3知，当输出约简 Red(C) 时，有R_C=R_Red。由定理2知，算法3求出的属性约简就是基于知识粒度的属性约简。

算法时间复杂度分析：算法3的1)由文献^[11]知时间复杂度为 O(K|C||U|)(其中K=max{|T_c(x_i)|,x_i∈U}),空间复杂度为O(|U|)。2) 的时间复杂度为O(|C|)+O(|U|),空间复杂度为 O(|U|)(由算法1的复杂度分析可得)。3)的时间复杂度为O(|C||U|),空间复杂度为O(|U|)。故算法3的时间复杂度为O(K|C||U|)(其中K=max{|T_C(x_i)|,x_i∈U},空间复杂度为O(|U|)。

为了证明算法的可行性，以文献^[16]中的不完备决策表 1为例子进行相应说明。

为方便计算，将属性值从左至右简记为 P、M、S、X，则该表的条件属性为C={P,M,S,X}。

由算法3 1)求得各属性的知识粒度分别是 ：

|K₁|=GD(P)=(4+4+6+4+6+4)/36=28/36;

|K₂|=GD(M)=(6+6+6+6+6+6)/36=36/36;

|K₃|=GD(S)=(5+5+5+5+5+1)/36=26/36;

|K₃|=GD(X)=(3+3+4+4+4+6)/36=24/36;

U_pos={x₁,x₂,x₃},U_neg={x₄,x₅,x₆}

由2)排序|K₄|≤|K₃|≤|K₁|≤|K₂|，他们对应的属性为X、S、P、M，则有Red(C)={X}，R_C=∅。

由3)计算|F_∅(U,X)|=6，计算的|F_X(U,S)|=6，计算的|F _{X,S}(U，P)|=1，计算的|F_{X，S，P}{U,M}|=0，算法结束，输出约简Red(C)={X,S,P}。

由算法2求|F_Red(X)|。

输入  U/∅={x₁,x₂,x₃,x₄,x₅,x₆}

由算法2，2)的2)①对 A₁={x₁,x₂,x₃,x₄,x₅,x₆}求得：

front^[1]→x₁→x₂→end^[1]；

front^[2]→x₃→x₄→x₅→end^[2]；

front[*]→x₆→end[*]；

对第1个非空队列有pos₁={x₁,x₂},Neg₁= ∅；

对第2个非空队列pos₂={x₃},Neg₂={x₄,x₅},则 N₁=pos_ipos_j= |pos₁|*|pos₂|=2*1=2。

由算法2，2)的②计算每个非空队列中的pos_i/D。

D₁₁={x₁,x₂},D₁₂=∅,D₁₃=∅，

D₂₁=∅，D₂₂={x₃},D₂₃=∅ ,则

每个非空队列中的Neg_i/D：

对A_*={x₆},因A_*不能区分对象，故无需计算。

故|F_∅(U，X)|=2N₁+N₂=2*2+2=6,

求|F_X(U,S)|。

输入  U/(X)={{x₁,x₂},{x₃,x₄,x₅}}

由算法2 2)的①对A₁={x₁,x₂}求得front^[1]→x₁→x₂→end^[1];

对其划分有pos₁={x₁,x₂},Neg₁=∅;

易知，|F_X(U,S)|₁=0,

对A₂={x₃,x₄,x₅}求得

front^[1]→x₃→end^[1]；

front^[2]→x₄→x₅→end^[2]；

对第1个非空队列有pos₁={x₃},Neg₁=∅;

对第2个非空队列pos₂=∅,Neg₂={x₄,x₅}， 则N₁pos_ipos_j=1*0=0,对决 策属性划分后得

|F_X(U,S)|₂=2N₁+N₂=0+6=6

|F_X(U,S)|=|F_X(U,S)|₁+|F_X(U,S)|₂=6

输入  U/(X∪({S})={{x₁,x₂},{x₃},{x₄,x₅} 由算法2的2)①对 A₁={x₁,x₂}求得

front^[1]→x₁→end^[1]；

front^[2]→x₂→end^[2]；

对第1个非空队列有 pos₁={x₁}，Neg₁=∅;

对第2个非空队列pos₂={x₂}，Neg₂=∅。

则 N₁=pos_ipos_j=1*1=1易知N₂=0,

故|F_{X,S}(U,P)|₁=1。

对A₂={x₃} 求

front^[1]→x₃→end^[1];

易知，|F_{X,S}(U,P)|₂=0

对A₃={x₄,x₅}求得

front^[1]→x₄→end^[1];

front[*]→x₅→end[*];

易知，|F_{X,S}(U,P)|₃=0，

|F_{X,S}(U,P)|=|F_{X,S}(U,P)|₁+

|F_{X,S}(U,P)|₂+|F_{X,S}(U,P)|₃=1

输入  U/({X,S}∪{P})={{x₁},{x₂},{x₄}}

求得|F_{X,S,P}(U,M)|=0。

实例说明，该约简与文献^[5]相同。新算法不仅通俗易懂，且在粒度差别矩阵的基础上大大减少存储空间，且大大提高了算法收敛的时间速度，即新算法是一个高效可行的属性约简算法。

为了更好地说明新算法比其他同类算法更具有有效性和实用性，选用UCI机器学习数据库中的6个数据集：Credit、Car、Hepatitis、Soybean-large、Vote和Wine进行实验。选取比较新的算法进行对比，考察新算法的高效性，分别与文献^[17]、文献^[18]、文献^[11]进行对比，文献^[17]是在差别矩阵的基础上提出的属性约简算法，文献^[17]算法运行时间记为 t₁，文献^[18]是基于冲突域的属性约简算法，算法运行时间记为t₂，文献^[11] 算法运行时间 记为t₃，本文算法运行时间记为t_new，对比结果见表 2。为了增强实验结果的可靠性，本文所取的最终时间为 7次实验结果的平均值。实验运行的环境为：CPU为AMD，2.00 GB内存，在Visual Stdio2010平台。

图 1 UCI数据集对比 Fig. 1 The comparison of UCI data sets

图选项

表 2中的数据集,|C|代表条件属性个数,|U|代表对象个数。

从表 2 中的实验数据可以看出，对于小的数据集({Hepatitis,15,199}，{Wine,14,178})上,对比的4种算法的运行时间相差不大。但是对于较大的数据集，运行时间就相差很大，而且随着数据集的扩大，新算法的运行时间相对于其他3种算法的增长幅度小得多，表明新算法具有较好的可扩展性。

在决策表中，知识粒度是有效进行属性约简的方法，以往的属性约简算法由于计算知识粒度浪费了大量时间，算法效率不高。因此，本文设计一个基于知识粒度的计算条件属性频率的启发函数，以知识粒度为启发信息，提出新的属性约简算法，大大降低了算法的时间复杂度。在以后的研究中，可以将计算属性频率的思想利用到其他属性约简的方法中，如相容矩阵、差别矩阵等，也可进一步应用到规则获取中。