属性序下的快速约简算法

计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报

CHINESEJOURNALOFCOMPUTERSVol.30No.8

Aug.2007

󰀁属性序下的快速约简算法

胡󰀁峰󰀁󰀁王国胤

(重庆邮电大学计算机科学与技术研究所󰀁重庆󰀁400065)(西南交通大学信息科学与技术学院󰀁成都󰀁610031)

摘󰀁要󰀁将分治法的思想溶入Rough集算法中,在给定属性序下,提出了基于分治策略的属性约简算法.利用该算法可以计算给定属性序下的唯一约简,并能快速得到海量数据的属性约简.在一次性将决策表的所有数据调入计算机内存的情况下,算法的平均时间复杂度为O(|U|󰀂|C|󰀂(|C|+log|U|)),空间复杂度为O(|U|+|C|).仿真实验结果说明了算法的高效性.关键词󰀁粗集;分治;属性约简;属性序中图法分类号TP18

QuickReductionAlgorithmBasedonAttributeOrder

HUFeng󰀁WANGGuo󰀁Yin

(InstituteofComputerScienceandTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing󰀁400065)

(SchoolofInformationScienceandTechnology,SouthwestJiaotongUniversity,Chengdu󰀁610031)

Abstract󰀁Theideaofdivideandconquerisadoptedinattributereductionofroughsettheory.Aquickalgorithmforattributereductionoforderedattributesisproposedbasedonthedivideandconquermethod.Auniqueattributereductioncanbeobtainedwiththisalgorithm.Itissuitablefordealingwithhugedatareduction.Ifalldataofadecisiontablecouldbeloadedinmemoryonetime,theaveragetimecomplexityofthisalgorithmwillbeO(|U|󰀂|C|󰀂(|C|+log|U|))anditsspacecomplexitywillbeO(|U|+|C|).Simulationexperimentalresultsshowitsefficiency.Keywords󰀁roughset;divideandconquer;attributereduction;attributeorder

时间复杂度为O(|C|3󰀂|U|2).文献[4]给出了基于

1󰀁引󰀁言

粗集(RoughSet,RS)理论[1]由波兰学者Paw󰀁lak教授于1982年提出,由于它能有效地分析和处理不精确、不一致、不完整等各种不完备信息,并能从中揭示潜在的规律,近年来在机器学习、数据挖掘等多个领域得到了广泛应用.

在基于粗集理论的知识获取研究中,许多学者已经对属性约简的算法进行了大量的研究[3󰀁11].文献[3]给出了较好的启发函数,使其属性约简算法的

[2]

条件信息熵的约简算法,其时间复杂度为O(|C|2󰀂|U|).文献[5󰀁6]通过快速排序的方法来计算正区域,将基于正区域的属性约简算法的时间复杂度降为O(|C|2󰀂|U|󰀂log|U|).文献[7]采用了基数排序的方法计算正区域,得到了时间复杂度为max{O(|C|󰀂|U|),O(|C|󰀂|U/C|)}的属性约简算法.文献[8]给出了基于Skowron分辨矩阵的属性约简算法.文献[3󰀁8]中的属性约简算法都是在无属性序的条件下给出的.对于属性序的属性约简算法,文献[9󰀁11]进行了深入的研究,在给定属性序的条件下,文献

2

2

收稿日期:2007󰀁03󰀁04;修改稿收到日期:2007󰀁05󰀁25.本课题得到国家自然科学基金(60373111,60573068)、新世纪优秀人才支持计划(NCET)、重庆市自然科学基金(2005BA2003)、重庆市教委科学技术研究项目基金(KJ060517)资助.胡󰀁峰,博士研究生,讲师,主要研究领域为RoughSet理论等.E󰀁mail:hufeng@cqupt.edu.cn.王国胤,博士,教授,博士生导师,主要研究领域包括RoughSet、智能信息系统、神经网络等.

1430计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2007年

[9]结合Skowron分辨矩阵给出了时间复杂度O(|U|󰀂|C|)的属性约简算法.文献[10]给出了树表示下的属性约简算法,其时间复杂度为O(|U|󰀂|C|2).然而,在一次性将决策表的所有数据调入内存,且不考虑这些数据本身所占内存的情况下,这些算法的空间复杂度至少为O(|U|󰀂|C|),有的甚至达到O(|U|󰀂|C|),当|U|>10时,算法所需的辅助空间会占用大量内存,导致算法性能急剧下降,这也是现有的约简算法不能很好地处理大数据集约简问题的主要原因.因此,在设计属性约简算法时,同时考虑时间复杂度和空间复杂度是非常必要的.

属性序的研究在面向领域用户的数据挖掘中具有重要意义.本文在给定属性序下,将分治法的思想融入到决策表的正区域计算和属性约简过程中,提出一种新的属性约简算法.该算法的平均时间复杂度为O(|U|󰀂|C|󰀂(|C|+log|U|)),空间复杂度为O(|U|+|C|).算法得到的属性约简是给定属性序下的唯一约简,改进了文献[9󰀁10]中的约简算法.实验结果表明,在|U|󰀂|C|和|C|󰀂|U|两种情况下,本文给出的约简算法都能快速地得到决策表的约简,适合海量数据集的属性约简处理.本文第2节介绍有关Rough集理论和属性序的基本概念;第3节提出一种新的属性约简算法,该算法充分结合了改进的分辨矩阵和分治法的思想;第4节给出在KDDCUP99数据集上的实验测试结果,并通过自定义数据集,在|U|󰀂|C|和|U| |C|两种情况下进行海量数据集的测试,且对实验结果进行分析;最后一节总结全文.

[11]2

5

2

f(y,a)且w(x,y)=1},其中x,y%U;

1,

w(x,y)=

1,1,

x%POSC(D),y

POSC(D)

xPOSC(D),y%POSC(D)

.

x,y%POSC(D),d(x)#d(y)

0,其它情况

󰀁󰀁本文将改进后的Skowron分辨矩阵简称为Skowron分辨矩阵或者分辨矩阵.此外,为了描述简洁,本文将f(x,a)(x%U,a%C)记做a(x).

命题1(基于Skowron分辨矩阵的约简规则).󰀁令M是决策表S= U,A=C!D,V,f∀的分辨矩阵.R(R∀A&R#!)是一个约简,当且仅当#󰀁%M(󰀁#!∃󰀁∋R#!).

我们给整个条件属性集合定义一个完整的序关系.根据这个序关系,我们可以给出Skowron分辨矩阵的等价关系.为了本文后续介绍的方便,在此先将文献[9]中关于属性序的基本概念进行简单介绍.

令S= U,A=C!D,V,f∀是一个决策表.我们在C上定义了一个完整的序关系(∃),同时,我们为C中的所有属性分别标上1到|C|.这样,我们在C上就得到了一个关于属性的序列,在本文中称为(属性序)SO:c1∃c2∃∗∃c|C|[9].

令M是S= U,A=C!D,V,f∀的Skowron分辨矩阵.#󰀂%M,󰀂中的属性从左到右继承着序列SO,例如:󰀂=cjB,cj%C,B是C中的一个属性子集,cj是在序SO下󰀂的第一个属性,在这里,我们把cj叫做󰀂的标签属性.

对于cj,我们定义集合:L(SO)={󰀂|󰀂=cjB,󰀂从左到右继承着序列SO,󰀂%M}.容易验证:L(SO)是M上的等价关系,而且将M划分为多个等价类.可以用商集来表示它的划分:M/L(SO)={[c1],[c2],∗,[c|C|]}.因为[ci]∋[cj]=!(当i#j时),因而这个划分是唯一的.所以,Skowron分辨矩阵中的每一个元素只属于一个等价类,且该等价类由分辨矩阵元素的标签属性决定.这个划分可以用属性的下标来表示:M/L(SO)={[1],[2],∗,[|C|]}[9].

在由L(SO)划分得到的等价类中,下标最大的标签属性对属性约简起着非常重要的作用.令N=max{[M/L(SO)]},1%N%|C|.它的标签属性是aN.R是一个约简,假定R=!.

算法1[9].󰀁属性序下的约简算法.

(1)令cN是一个约简属性,R=R!{cN};(2)E={󰀁:󰀁∋{cN}=!,󰀁%M},M=E;(3)N+=max{[M/L(SO)]},N=N+;(4)重复以上步骤,直到M=!.

则R是S= U,A=C!D,V,f∀的一个约简.[9]

2󰀁Rough集和属性序的基本概念

定义1(决策表

[2]

).󰀁一个决策表S= U,A=

C!D,V,f∀,其中U是对象的集合,也称为论域,A=C!D是属性集合,C和D分别称为条件属性集和决策属性集,D#!,V是属性值的集合,f:U󰀂A∃V是一个信息函数,它指定了U中每个对象x的属性值.

给定决策表S= U,A=C!D,V,f∀,Skowron给出了信息系统的分辨矩阵,Hu给出了分辨矩阵的另一种形式[3].然而,Hu给出的分辨矩阵在不相容决策表中是不完备的,文献[12󰀁13]中给出了改进后的Skowron分辨矩阵.

定义2[14].󰀁给定决策表S= U,A=C!D,V,f∀,设改进后的Skowron分辨矩阵为M,M中的分辨矩阵元素可以定义为Bxy={a%C|f(x,a)#

s

[8]

8期胡󰀁峰等:属性序下的快速约简算法1431

引理1[9].󰀁令k1,k2是属性下标,[k1],[k2]%M/L(S).它们的标签属性分别是b1和b2.如果k1[9][9]

也是O(|U|2󰀂|C|),算法的时间复杂度是平方级的,保持了与|C|的线性关系,但是空间复杂度太大,当决策表的数据量较大时,处理速度相当慢.因此,改进此算法,获得与算法1等价的约简结果且时空复杂度较小的算法是很有必要的.

使用快速排序后,计算正区域的算法的时间复杂度、空间复杂度都降低了,如果我们把分治法的思想也加入到属性约简过程中,就可以降低算法的复杂度.分析算法1的复杂度后发现,在进行算法1对决策表进行处理之前,需要保存一个Skowron分辨矩阵,这直接导致了算法1的时间、空间复杂度都必须在O(|U|󰀂|C|).因此,必须找到一条途径,使得不需要存储Skowron分辨矩阵,同时又能满足算法1所需要的数据.

基于以上分析,下面给出一个属性序下的快速约简算法.3&1&1󰀁计算非空标签等价类从算法1可知:计算属性序下的约简,在得到决策表的正区域后,需要得到非空标签属性集合.命题5给出了计算非空标签属性集合的方法.在这里,首先给出计算非空标签属性集合的递归函数(递归函数1)和具体的算法(算法2).

递归函数1(用于计算非空标签属性集合).

VoidNonEmptyLabelAttr(intr,ObjectSetOSet)󰀁󰀁󰀁󰀁//r为属性的编号(1%r%|C|),OSet(OSet%2U)

//为对象集

{

while(1%r%|C|){

if|OSet|=1,thenreturn;ElseIf#x%

OSet

3󰀁属性序下决策表的属性约简

在基于决策表正区域不变的属性约简中[3,5󰀁9],计算决策表的正区域是最重要的计算之一.文献[7]给出了基于基数排序计算正区域的算法,其时间复杂度为O(|C|󰀂|U|),空间复杂度为O(|U|󰀂|C|);文献[5󰀁6,15]给出了用快速排序的方法(快速排序的方法属于分治法)计算正区域,并指出其时间复杂度为O(|C|󰀂|U|󰀂log|U|),然而,我们发现,用快速排序对二维表排序的平均时间复杂度为O(|U|󰀂(|C|+log|U|)),空间复杂度为O(|U|)[17].考虑到空间复杂度的问题,本文采用快速排序的方法计算决策表的正区域,具体方法参见文献[5󰀁6,17],这里不再赘述,下面给出属性序下的属性约简算法.3&1󰀁属性序下的属性约简算法

命题4.M中的分辨矩阵元素Bxy不为空的充要条件是:对象x,y中至少有一个属于POSC(D)且d(x)#d(y).

命题5.令[k]%M/L(S),则[k]#!的充要条件是:∋x,y%U,满足以下两个条件:

(1)M中的分辨矩阵元素Bsxy不为空;

(2)#k1(1%k1(ck(x)#ck(y)).

命题6.󰀁给定决策表S= U,A=C!D,V,f∀,给定属性序SO:c1∃c2∃∗∃c|C|,属性ck(ck%C&2%k%|C|)是非空标签属性的充要条件是:在Skowron分辨矩阵中依次去掉包含属性c1,c2,∗,ck-1的分辨矩阵元素后,∋Bsxy%M满足ck%Bsxy.

结合定义2、属性序的基本概念和引理1、引理2的证明过程(见文献[9]),可以证明命题4、命题5、命题6.由于篇幅的原因,这里省略了命题4~命题6的证明过程.

在给定属性序下,算法1给出了一个求唯一Pawlak属性约简的完备算法,但是该算法的平均、最坏时间复杂度都是O(|U|2󰀂|C|),空间复杂度s

[16]

2

x

POSC(D),thenreturn;

//根据命题4和命题5

ElseIf#x,y%OSetcr(x)=cr(y),thenNonEmpty󰀁

LabelAttr(r+1,OSet);Else

{NonEmptyLabel[r]=1;//根据命题5,判断

󰀁//属性Cr是否非空标签属性,值为1表示󰀁//是非空标签属性

将OSet划分成两部分OSetr1,OSetr2;设X为OSet中所有对象在属性r上属性值的平均值,则OSetr1,OSetr2满足#x%OSetr1,y%OS󰀁etr2,有

cr(x)%XNonEmptyLabelAttr(r,OSetr1);NonEmptyLabelAttr(r,OSetr2);}}}1432计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2007年

算法2.󰀁求L(SO)划分得到的等价类的非空标签属性集合.

输入:决策表S= U,A=C!D,V,f∀输出:决策表S的非空标签属性集合R1

1.设C={c1,c2,∗,c|C|},给定一个属性序SO:c1∃c2∃∗∃c|C|.

2.R1=!,r=1,OSet11=U;Forj=1to|C|doNonEmptyLabel[j]=0;

3.调用NonEmptyLabelAttr(1,OSet11);4.Forj=1to|C|do

IfNonEmptyLabel[j]=1,then

R1=R1+{cj};

5.ReturnR1.

度为O(|U|);步3的平均时间复杂度为O(|U|󰀂(|C|+log|U|)),空间复杂度为O(|U|+|C|);步

4的平均时间复杂度为O(|U|󰀂|C|󰀂(|C|+log|U|)),空间复杂度为O(|U|+|C|).故算法3的平均时间复杂度为O(|U|󰀂|C|󰀂(|C|+log|U|)).空间复杂度为O(|U|+|C|).3&2󰀁算法3与算法1输出结果的等价性证明接下来,我们证明:算法3的输出结果与算法1的输出结果是相同的.

给定决策表S= U,A=C!D,V,f∀,S的分辨矩阵为M.条件属性子集C1∀C,设M1为这样的一个集合:MC1={󰀁1,󰀁2,∗,󰀁t},满足:(1)#󰀁%MC1󰀁i%iM(1%i%t);(2)#c%C1,如果存在󰀁%M,满足c%󰀁,则󰀁%MC1.

即,在分辨矩阵M中,MC1是包含了C1中至少一个属性的分辨矩阵元素的集合.

命题7.󰀁给定决策表S= U,A=C!D,V,f∀,条件属性子集C1∀C.根据U中所有对象在C1上的取值将U划分成U1,U2,∗,U|U/C1|,并根据U/C1的划分将决策表S分解成|U/C1|个子决策表S1,S2,∗,SU/C1,其中Si= Ui,C!D,V,f∀(1%i%|U/C1|).设S的分辨矩阵为M,Si的分辨矩阵为

|U/C|

C算法2的复杂度分析:文献[17]中给出了二维表快速排序的平均时间复杂度和空间复杂度,而算法2的时间复杂度与二维表快速排序的时间复杂度相同,故算法2的平均时间复杂度为O(|U|󰀂(|C|+log|U|)),空间复杂度为O(|U|+|C|).3&1&2󰀁基于属性序和分治法的属性约简算法在得到决策表在属性序下的非空标签属性集合后,接下来给出基于属性序和分治法的属性约简算法.

算法3.基于属性序和分治法的属性约简算法.

输入:决策表S= U,A=C!D,V,f∀输出:决策表S的属性约简Red

1.设C={c1,c2,∗,c|C|},给定一个属性序SO:c1∃c2∃∗∃c|C|,r=1,U=U,Red=!;

11

Mi(1%i%|U/C1|),则󰀁!󰀁=%M(注:若#x,y%

U

i

i=1!%M

!

1

!!!

i

%M1

!C

#c1%Cc1(x)=c1(y),则Mi=!).

|U/C|

1

i

证明.󰀁先证明󰀁!󰀁∀i!!!!%M=1!%M

2.利用快速排序计算决策表的正区域POSC(D);3.调用算法2计算决策表的非空标签属性集合R1;4.设cN+为R1中标号最大的标签属性,IfcN+%Red,then转步5;Else

Red=Red!{cN+},且cN+放在Red的最后一位;R1=R1-{cN+};C+=!;

合并属性集Red和R1,先将Red中的属性按标签属性下标的降序排列依次加入到C+中,然后将R1中属性按标签属性下标的升序排序依次加入到C+中;

C=!;󰀁C=C+;

调用算法2计算决策表在新属性序下的非空标签属性集合R1;转步4;EndIf5.ReturnRed.

%MC1

! .

#󰀁%M,设󰀁是对象x(x%U)和y(y%U)的分辨属性集合.经过U/C1的划分后,设x和y分别被划分到子决策表Si(1%i%|U/C1|)和Sj(1%j%|U/C1|)中.

若i=j,则x和y属于同一个子决策表Si,显

|U/C|

然有󰀁%Mi,且󰀁%

!!!.i=1!%M

i

1

否则,i#j,x和y不属于同一个子决策表,则

󰀁%MC1,且󰀁%!C .

%M1

|U/C|

1

|U/C|

1

因而,󰀁∀i!!!!!C ,即󰀁!󰀁∀i!!!=1!%M%M=1!%M

i

%M1

i

!!C .

%M1

|U/C|

同理可证󰀁!󰀁(i!%M=1

1

!%M

!!!

i

%M1

!C .故命题7

得证.证毕.分析递归函数1可知,在条件属性子集C1(C1∀C)上,通过递归函数1的反复调用,可以将U分解

C

为UC11,U21,∗,UCp1(p为递归函数1在条件属性子算法3的复杂度分析:在算法3中,步2的平均

时间复杂度是O(|U|󰀂(|C|+log|U|)),空间复杂8期胡󰀁峰等:属性序下的快速约简算法1433

集C1将U划分的子集的数目,1%p%|U/C1|),并

CCC

满足如下条件:U=UC11!U21!∗!Up1(Ui1∋

1#c%Cc(x)=U=!(1%iC

c(y)(1%k%p)和#x%UC1#z%U1∋c%Cc(x)#c(z)il1(1%i2等价于在算法3中调用一次递归函数1.因此,算法1的整个处理过程等价于算法3中的步4,故Red=R.证毕.

C

j1

4󰀁实验结果

为了验证本文方法的有效性,我们进行了多组测试.首先,我们采用KDDCUP99数据集进行测试;然后,通过自定义数据集,在|U|󰀂|C|和|U| |C|两种条件下分别测试算法3的性能.

4&1󰀁KDDCUP99数据集测试

为了考察算法3在大数据集环境下的运行性能,我们采用了KDDCUP99入侵检测数据集进行测试(数据集下载地址:http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html),原KDD󰀁CUP99数据集共有48432条记录,每条记录有41个属性.我们分别从中随机选出10%,20%,∗,100%记录生成新的数据集,采用等频率离散化方法对这10个数据集进行离散化处理,所有记录在各个属性上的取值范围是0~255,这样,只需要一个字节就可以存储一个属性值.用算法3对这些数据集进行测试,测试结果见表1,其中T表示算法的运行时间,单位为s;N表示约简结果的条件属性个数,MemUse表示程序在运行过程中使用的最大内存,单位为KB.本实验的硬件测试环境是:CPU为IntelPentium42&4GHz,内存为512MB,操作系统为WindowsXP,开发工具为VC++6&0.

表1󰀁KDDCUP99数据集测试结果

记录数比例/%

10

2030405060708090100

记录数484397968614695291959372244921629390593420239187440858848432

属性数

T/s

N29303130323234333334

MemUse1988042469723032323449843951444445793672317259237216

4161&23241741135&02314341218&74359841283&40626041384&72317341469&10303241602&92009941661&66316241753&581113337&205877

[2]

命题8.给定决策表S= U,A=C!D,V,f∀,

条件属性子集C1∀C.根据U中所有对象在C1上的取值将U划分成U1,U2,∗,U|U/C1|,与之对应的子决策表为Si,Si的分辨矩阵为Mi1(1%i%|U/C1|).在C1上,通过递归函数1的递归调用,将U分解为

CC

UC11,U21,∗,Up1(1%p%|U/C1|),与之对应的子决策表为S,S的分辨矩阵为M

|U/C|i=1󰀁%M

C

1j

C1j

C1jC

(1%j%p).则

!

1

1#c%Cc(x)=!󰀁=i=!1!C!(注:如果#x,y%UCj

i

p

!%M1

j

c(y),则M=!).

|U/C|

1

i

Cj1

证明.󰀁先证i!!󰀁(i!!C!.=1󰀁%M=1

!%Mj1

p

对于UCk1(1%k%p),有3种情况:(1)如果#x%UCPOSC(D),则Mi1=!;(2)如果#x,y%Ujk1x

#c%Cc(x)=c(y),则MCj1=!;(3)∋x,y%UC1(x%k

1POSC(D)&∋c%Cc(x)#c(y)),此时MCj#!.我们只需要分析第三种情况.根据递归函数1的调用过

C

程可知,必然存在Uq(1%q%|U/C1|),满足Uk1=Uj,即M=Mq,故i!!󰀁(i!!C!.=1󰀁%M=1

i

C

C

1k

|U/C|

1

p

!%M1

j

|U/C|

1

i

同理可得i!!󰀁∀i!!C!,故命题8得证.=1󰀁%M=1

!%Mj1

p

证毕.命题9.󰀁给定决策表S= U,A=C!D,V,f∀,给定属性序SO:c1∃c2∃∗∃c|C|,C1={c1,c2,∗,ck}(1%k%|C|).则,在C1上调用递归函数1的过程实质上是消除等价类[c1],[c2],∗,[ck],即在Skowron分辨矩阵M中不断消除所有标签属性为c1,c2,∗,ck的分辨矩阵元素的过程.

证明.󰀁从命题8可知:从消除Skowron分辨矩阵元素的角度分析,在C1上调用递归函数1的过程是划分等价类U/C1的过程.根据第3节属性序的基本知识易知命题成立.证毕.根据命题6、命题9和算法2可知,算法2的输出结果R1与文献[9]中非空标签属性集合的定义是一致的.

命题10.󰀁给定决策表S= U,A=C!D,V,f∀和属性序SO:c1∃c2∃∗∃c|C|,算法3的输出结果Red和算法1的输出结果R是相同的.

证明.󰀁由命题6和命题9可知,算法1中的步从表1可以看出,对于前9个数据集,算法3的处理速度是相当快的.但是,当记录数增加到48432时,算法3的运行时间突然急剧增加.从算法3的时间复杂度的表达式分析,不应该出现这样的运行时间急剧增加的情况.分析整个运行过程,我们发现:当记录数增加到48432时,算法3使用的内存过大,而此时CPU的利用率低于10%,使得算法3的性能急剧下降,从而运行时间急剧增加.由此1434计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2007年

可见,对于大数据集的处理,算法的空间复杂度非常重要,在某些情况下可能比时间复杂度更重要.4&2󰀁自定义数据集测试

为了充分测试算法3的性能,在|U|󰀂|C|和|U| |C|两种情况下,我们自定义了两组数据进行了测试.对这两组数据进行实验测试的硬件测试环境都是:CPU为IntelPentium42&4GHz,内存为256MB,操作系统为WindowsXP,开发工具为VC++6&0.

随机生成20个记录集,记录集的记录数由1󰀂105逐渐增加到3󰀂10,每条记录含有15个条件属性和1个决策属性,每条记录的条件属性和决策属性都在(0~9)上随机取值,用算法3对这些数据集进行测试,测试结果见图1.属性序由随机生成的属性标号任意给定.

6

从图2可以看出,当|U| |C|时,算法的执行速度非常快.从算法3的时间复杂度O(|U||C|(|C|+log|U|))分析,其运算速度不应该这么快.分析实验过程的每一步结果之后发现,随机生成的决策表为相容决策表,只需要大约log|U|个属性就可将数据集中所有对象区分开,因而算法2的时间复杂度降低到O(|U|log|U|).非空标签属性集合的势一般不超过log|U|,这导致算法3的时间复杂度下降到O(|U|log2|U|),这也是算法3运行效率高的原因.

此外,使用图1和图2中同样的数据集,我们对算法1进行了测试.实验结果是:算法1对于10个数据集均产生内存不足的现象,程序非正常终止,主要原因还是算法1的空间复杂度太大.

5󰀁结束语

虽然Rough集理论正日渐成熟,但是还没有能够在工业中取得广泛的应用.一个重要原因是:Rough集对于属性约简(特征提取)的优势,在海量数据集面前显得效率不够高.已有的许多属性约简算法对于空间复杂度考虑不足,导致了算法不能适应大数据集的约简处理.本文在属性序的基础上,将分治递归的思想融入到属性约简的过程中,设计了平均时间复杂度为O(|U|󰀂|C|󰀂(|C|+log|U|))、空间复杂度为O(|U|+|C|)的约简算法.该算法所得的属性约简结果与文献[9]中算法所得的结果相同.实验结果表明,该算法在|U|󰀂|C|和|U| |C|两种条件下都能快速得到约简结果.然而,算法本身存在着一个局限性:必须要以给定属性序为前提条件,当然,在面向领域用户的数据处理中,属性序的获得并不困难.在无属性序的条件下,如何快速地利用分治法获取属性序将是我们进一步的研究工作.另外,如何将分治法用于值约简等处理也是我们接下来需要研究的问题.

参

[1][2]

图1󰀁自定义数据集测试结果(|U|󰀂|C|)

从图1可以看出,算法3是高效的.

随机生成10个记录集,记录集的条件属性数由:0&5󰀂104逐渐增加到5󰀂104,决策属性个数为1,每个记录集含有1000条记录,每条记录的条件属性和决策属性都在(0~4)上随机取值,用算法3对这些数据集进行测试,测试结果见图2.属性序由随机生成的属性标号任意给定.

考文献

PawlakZ.RoughSet.InternationalJournalofComputerandInformationSciences,1982,11:341󰀁356

WangGuo󰀁Yin.RoughSetTheoryandKnowledgeAcquisi󰀁tion.Xi+an:Xi+anJiaotongUniversityPress,2001(inChi󰀁nese)

(王国胤.Rough集理论与知识获取.西安:西安交通大学出版社,2001)

HuXH,CerconeN.Learninginrelationaldatabase:Aroughsetapproach.InternationalJournalofComputationalIntelligence,1995,11(2):323󰀁338图2󰀁自定义数据集测试结果(|U| |C|)

[3]

8期

[4]

胡󰀁峰等:属性序下的快速约简算法

科学院自动化研究所,北京,2004)

[11][12]

1435

WangGuo󰀁Yin,YuHong,YangDa󰀁Chun.Decisiontablereductionbasedonconditionalinformationentropy.ChineseJournalofComputers,2002,25(7):759󰀁766(inChinese)(王国胤,于洪,杨大春.基于条件信息熵的决策表约简.计算机学报,2002,25(7):759󰀁766)

HanSQ,WangJ.Reductandattributeorder.JournalofComputerScienceandTechnology,2004,19(4):429󰀁449YeDong󰀁Yi,ChenZhao󰀁Jiong.Anewdiscernibilitymatrixandthecomputationofacore.ActaElectronicaSinica,2002,30(7):1086󰀁1088(inChinese)

(叶东毅,陈昭炯.一个新的差别矩阵及其求核方法.电子学报,2002,30(7):1086󰀁1088)

[5]NguyenSHetal.Someefficientalgorithmsforroughsetmethods//ProceedingsoftheConferenceonInformationPro󰀁cessingandManagementofUncertaintyinKnowledgeBasedSystems.Granada,Spain.1996:1451󰀁1456

[13]

WangGuo󰀁Yin.Thecomputationmethodofcoreattributeindecisiontable.ChineseJournalofComputers,2003,26(5):611󰀁615(inChinese)

(王国胤.决策表核属性的计算方法.计算机学报,2003,26(5):611󰀁615)

[6]LiuShao󰀁Hui,ShengQiu󰀁Jian,WuBin.Researchoneffi󰀁cientalgorithmsforroughsetmethods.ChineseJournalofComputers,2003,40(5):637󰀁2(inChinese)

(刘少辉,盛球戬,吴斌等.Rough集理论高效算法的研究.计算机学报,2003,5(26):524󰀁529)

[14]

LiDing󰀁Fang,LiGui󰀁Bin,ZhangWen.U/{a}partitionbasedsmallestreductionconstruction.JournalofWuhanUniversity(NatSciEd),2005,51(3):269󰀁272(inChinese)(李订芳,李贵斌,章文.基于U/{a}划分的最小约简构造.武汉大学学报(理学版),2005,51(3):269󰀁272)

[7]XuZhang󰀁Yan,LiuZuo󰀁Peng,YangBing󰀁Ru,SongWei.Aquickattributereductionalgorithmwithcomplexityofmax{O(|C||U|),O(|C|2|U/C|)}.ChineseJournalofComputers,2006,29(3):391󰀁399(inChinese)

(徐章艳,刘作鹏,杨炳儒,宋威.一个复杂度为max{O(|C||U|),O(|C|2|U/C|)}的快速属性约简算法.计算机学报,2006,29(3):391󰀁399)

[15]

(HuKe󰀁Yun,LuYu󰀁Chang,ShiChun󰀁Yi.Advancesinroughsettheoryanditsapplications.JournalofTsinghuaUniversity(Sci&Tech),2001,41(1):󰀁68(inChinese)(胡可云,陆玉昌,石纯一.粗糙集理论及其应用进展.清华大学学报,2001,41(1):󰀁68)

[8]SkowronA,RauszerC.Thediscernibilityfunctionsmatricsandfunctionsininformationsystems//SlowinskiRed.Pro󰀁ceedingsoftheIntelligentDecisionSupport,HandbookofApplicationsandAdvancesoftheRoughSetsTheory.Dor󰀁drecht:KluwerAcademicPublisher,1991:331󰀁362

[16]

YuXiang󰀁Xuan,CuiGuo󰀁Hua,ZhouHai󰀁Ming.Fundamen󰀁talsofComputerAlgorithms.Press,2001(inChinese)

(余祥宣,崔国华,皱海明.计算机算法基础.武汉:华中科技大学出版社,2001)

Wuhan:

HuazhongUniv

[9]WangJue,WangJu.Reductionalgorithmsbasedondiscern󰀁ibilitymatrix:Theorderattributesmethod.JournalofCom󰀁puterScienceandTechnology,2001,16(6):4󰀁504

[17]

HuFeng,WangGuo󰀁Yin.Analysisofthecomplexityofquicksortfortwodimensiontable.ChineseJournalofCom󰀁puters,2007,30(6):963󰀁968(inChinese)

(胡峰,王国胤.二维表快速排序的复杂度分析.计算机学报,2007,30(6):963󰀁968)

[10]ZhaoMin.Thedatadescriptionbasedonreduct[Ph.D.dis󰀁sertation].InstituteofAutomation,ChineseAcademyofSciences,Bejing,2004(inChinese)

(赵岷.基于Reduct理论的数据描述[博士学位论文].中国

HUFeng,bornin1978,Ph.D.

candidate,lecturer.Hisresearchinter󰀁estsincludeintelligentinformationpro󰀁cessing,datamining,etc.

WANGGuo󰀁Yin,bornin1970,professor,Ph.D.su󰀁pervisor.Hisresearchinterestsincludeintelligentinforma󰀁tionprocessing,datamining,roughset,neuralnetwork,etc.

Background

󰀁󰀁ThispaperispartiallysupportedbytheNationalNaturalScienceFoundationofChinaunderGrantsNo.60373111andNo.60573068,ProgramforNewCenturyExcellentTalentsinUniversity(NCET),NaturalScienceFoundationofChongqingundergrantNo&2005BA2003,Science&Tech󰀁nologyResearchProgramofChongqingEducationCommis󰀁sionundergrantNo&KJ060517.

Intheresearchofroughsettheory,manyresearchershaveproposedmanyalgorithmsforattributereduction.However,itisdifficultfortheexistedattributereductional󰀁gorithmstoprocesshugedatasets.Therearetworeasons.

Oneisthetimecomplexity,andtheotheristhespacecom󰀁plexity.Especiallyinprocessinghugedataset,thespacecomplexityofanalgorithmwillaffectgreatlyitsefficiency.Inthispaper,aquickalgorithmforattributereductionofor󰀁deredattributesisproposedbasedonthedivideandconquermethod.ItsaveragetimecomplexityisO(|U|󰀂|C|󰀂(|C|+log|U|))andspacecomplexityisO(|U|+|C|).Thealgo󰀁rithmissuitableforhugedataprocessing.Itmaybehelpfultoputroughsettheoryintoindustryapplications.