粒计算是当前信息处理中一种新的计算范式,可用于描述和处理不确定的、模糊的、不完整的和海量的信息以及提供一种基于粒和粒间关系的问题求解方法.它可对问题进行不同层次的抽象和处理来寻求不同粒度上的近似解,以达到简化问题和快速求解的目的.通过使用不同信息粒度,粒计算可以容忍不确定、不完全或有噪音的信息,从而获得具有鲁棒性的解决方案.粗糙集是一种处理不确定性和不精确性问题的有效数学工具,是粒计算理论中的一个重要组成部分.它无需提供问题所需处理的数据集合之外的任何先验知识,可以在保持分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则,为决策提供服务,已广泛应用于数据挖掘、机器学习、模式识别及商务智能等领域.

针对静态的信息系统,研究人员提出了许多基于粗糙集理论的知识发现方法.Blaszczynski等人设计了变精度粗糙集方法下的一个序列覆盖规则抽取算法^[1].Chen等人基于幂集树提出了一种特征提取的粗糙集方法^[2].Hong等人给出利用模糊粗糙集从不完备定量数据中挖掘知识的方法^[3].Inuiguchi给出了从两个决策表中基于粗糙集获取规则的方法^[4].Kaneiwa讨论了从多个数据集中知识发现的粗糙集方法^[5].Leung等人提出了从区间值信息系统中提取分类规则的方法^[6].Miao等人提出了基于粗糙集理论的杂合算法,用于信息检索中的文本分类^[7].Wang等人采用粗糙集方法来构造模糊决策树^[8].Wu等人提出了不完备模糊信息系统下粗糙集模型的知识获取方法^[9].Hu等人采用邻域粗糙集方法来构造邻域分类器^[10].Yao讨论了三枝决策应用于概率粗糙集模型的方法^[11].张清华等人提出了在已有知识基(粒)空间下寻找目标集合(概念)的近似集的方法^[12].

然而,这些针对静态的信息系统基于粗糙集的知识发现方法在面对大规模的复杂现实问题时,都面临高复杂性计算的困难.因此,如何提高基于粗糙集的知识发现算法的效率,以充分体现粗糙集解决不确定性问题的优势,成为粗糙集研究领域的主要任务之一.增量式知识更新方法由于其能够充分利用已有的知识,可以有效提高知识更新的效率,因此,很多学者致力于利用增量式知识更新方法来提高基于粗糙集的知识发现的效率.Shan等人首次提出了基于粗糙集的增量式规则获取算法^[13].Guo等人给出了基于搜索树的规则增量挖掘方法,其优点是不需要创建区分矩阵^[14].Zheng等人提出了基于规则树的增量式高效知识获取算法,其特点是在原有的决策树规则集基础上进行规则的增量式更新,避免了重复学习,提高了效率^[15].Fan等人提出了增量式提取具有最大长度的决策规则方法^[16].王利等人讨论了新增记录与已有条件属性等价类的关系以及对规则集的影响,提出了基于变精度粗糙集模型的增量式规则获取算法^[17].Liu等人在变精度粗糙集模型中定义了覆盖矩阵和支持矩阵,提出了对象增加时,通过动态更新覆盖矩阵和支持矩阵方法可以实现兴趣知识的快速更新^[18].Zhang等人给出了邻域粗糙集模型下多对象增加删除时近似集快速更新的方法^[19].

虽然目前粒度变化下基于粗糙集的增量式学习算法很多,但在文献里很少利用大规模数据集来进行测试评价算法的性能和适用性,而且不同算法之间的比较与性能测试的相关结果较少,极大地制约了基于粗糙集和粒计算的知识发现理论与方法的发展与实际应用;其次,由于云计算技术可以极大地提高海量数据处理的效率^[20],如何应用云计算技术提高基于粒计算和粗糙集理论的知识发现效率具有重要意义.但这方面的工作目前还很罕见,已有的工作有:Liu等人给出了基于改进的分辨矩阵规则增量挖掘的并行算法^[21];Qian等人提出了云计算环境下基于MapReduce的属性约简方法^[22];Zhang等人给出了一种基于MapReduce的并行计算粗糙近似集的方法^[23],并在此基础上提出了基于MapReduce的规则提取算法^[24].粗糙集上、下近似集的计算,是基于粗糙集的属性约简和知识获取方法的基础.本文在已有工作的基础上,结合增量更新技术,提出了基于MapReduce的快速更新粗糙集近似集的并行增量算法,可以有效地加快动态知识更新过程.

1 相关理论 1.1 云计算编程模型MapReduce

MapReduce是由Google公司提出的一种处理海量数据的并行编程模式^[25],Apache基金会在此基础上实现了开源的Hadoop并行平台^[26].用户将实际应用问题分解成若干可并行操作的子问题,设计相应的Map函数,Combine函数(可选)与Reduce函数就能将自己的应用程序运行在云计算环境中.

· Map函数:接受一个输入对,然后产生一个中间ákey,valueñ对集.MapReduce库把所有具有相同中间key I的中间value聚合在一起,经过归并/排序过程,然后把它们传递给Reduce函数.

· Combine函数(可选):是本地的Reduce过程.从本地的Map接受一个中间key和相关的一个value集,形成一个较小的value集,并传给Reduce.一般情况下,Combine函数与Reduce函数是一致的.

· Reduce函数:接受一个中间key I和相关的一个value集.它合并这些value,形成一个较小的value集.

图 1显示了MapReduce在开源云计算平台Hadoop上的流程图,其中,HDFS(Hadoop distributed file system)是指Hadoop分布式文件系统^[26].

1.2 粗糙集模型

本节我们回顾下本文用到的一些粗糙集的基本定义^[23,27].

设四元组S=(U,A,V,f)是一个信息系统,其中,U为非空有限的对象集合,称为论域;A表示非空属性集合; $V = \bigcup\nolimits_{a \in A} {{V_a}} {\rm{,}}$其中,V_a称为属性a的值域;f:UxA®V是一个信息函数,满足对任意xÎU,aÎA有f(x,a)ÎV_a.特别地,如果A=CÈD,其中,C为非空有限条件属性集,D为非空有限决策集,那么信息系统被称为决策表.

定义1(对象x关于属性集B的信息集^{[23, 27]}).设B={b₁,b₂,…,b_l}ÍA为非空属性子集.对任意xÎU,关于属性集B的信息集定义如下:

${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B} = \langle f(x,{b_1}),f(x,{b_2}),...,f(x,{b_l})\rangle $

(1)

关于属性B的等价关系,也称为不可区分关系,表示为IND(B),定义如下:

$IND(B) = \{ (x,y)|(x,y) \in U \times U,{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B} = {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} _B}\} $

(2)

等价关系IND(B)把论域U切分成若干个等价类,记为

U/IND(B)={[x]_B|xÎU} (3)

其中,[x]_B表示等价类,[x]_B={yÎU|(x,y)ÎIND(B)}.为简便起见,我们用U/B代替U/IND(B).

定义2(等价类E关于属性集B的信息集^{[23, 27]}). 设BÍA为非空属性子集.对任意EÎU/B,关于属性集B的信息集定义如下:

${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over E} _B} = {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B},x \in U$

(4)

定义3(上近似集与下近似集^{[23, 27]}). 设XÍU,R为一个等价关系,U/R={E₁,E₂,…,E_t}.X的上、下近似集定义如下:

$\left\{ {\begin{array}{*{20}{l}} {R(X) = \{ x \in U|{{[x]}_R} \subseteq X\} }\\ {\bar R(X) = \{ x \in U|{{[x]}_R} \cap X = \emptyset \} } \end{array}} \right.$

(5)

或者相当于:

$\left\{ {\begin{array}{*{20}{l}} {R(X) = \bigcup {\{ E \in U/R|E \subseteq X\} } }\\ {\bar R(X) = \bigcup {\{ E \in U/R|E \cap X = \emptyset \} } } \end{array}} \right.$

(6)

显然,$R(X) \subseteq X \subseteq \bar R(X)$.X的边界域定义如下:

$BN{D_B}(X) = \bar R(X) - R(X)$

(7)

定义4(决策D的上、下近似集^{[23, 27]}). 给出决策表S=(U,CÈD,V,f).U/D={D₁,D₂,…,D_r}决策类的集合,是决策属性D把对象集U切分成了r个互斥的子集.设BÍC为非空属性子集,IND(B)为等价关系,决策D的上、下近似集定义如下:

$\left\{ {\begin{array}{*{20}{l}} {{R_B}(D) = \{ {R_B}({D_1}),{R_B}({D_2}),...,{R_B}({D_r})\} }\\ {{{\bar R}_B}(D) = \{ {{\bar R}_B}({D_1}),{{\bar R}_B}({D_2}),...,{{\bar R}_B}({D_r})\} } \end{array}} \right.$

(8)

决策D的正域定义如下:

$PO{S_B}(D) = \bigcup\nolimits_{{D_i} \in U/D} {{R_B}({D_i})} $

(9)

2 基于MapReduce的粗糙近似集计算方法

本节简要回顾我们提出的并行计算粗糙近似集的方法^[23].

定义5(决策表的划分^[23]). 给出决策表S=(U,CÈD,V,f).设S_i=(U_i,CÈD,V,f),iÎ{1,2,…,m}.它满足:

(1) $U = \bigcup\nolimits_{i = 1}^m {{U_i}} {\rm{;}}$

(2) U_jÇU_k=Æ,"j,kÎ{1,2,…,m},j¹k.这意味着决策表S被切分为m个决策子表.

定理1(两个等价类的合并^[23]). 给出决策表S₁=(U₁,CÈD,V,f)与S₂=(U₂,CÈD,V,f).设BÍCÈD为非空属性子集,EÎU₁/B和FÎU₂/B是两个来自不同决策表的等价类.下面的结果成立:

(1) 如果${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over E} _B} = {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over F} _B}{\rm{,}}$那么等价类E和F可以合并为一个等价类G,G=EÈF且${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over G} _B} = {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over E} _B} = {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over F} _B}{\rm{;}}$

(2) 如果${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over E} _B} \ne {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over F} _B}{\rm{,}}$那么等价类E和F不能合并为一个等价类.

定理2(多个等价类的合并^[23]). 给出决策表S=(U,CÈD,V,f)和决策子表S_i=(U_i,CÈD,V,f),iÎ{1,2,…,m}.

"BÍC,令U/B={E₁,E₂,…,E_t},${U_i}/B = \{ {E_{i1}},{E_{i2}},...,{E_{i{p_i}}}\} $和${E_{all}} = \bigcup\nolimits_{i = 1}^m {{U_i}/B} = \{ {E_{11}},{E_{12}},...,{E_{1{p_1}}},...,{E_{m1}},{E_{m2}},...,{E_{m{p_1}}}\} {\rm{.}}$那么,"E_kÎU/B,我们有${E_k} = \bigcup {\{ F \in {E_{all}}|{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over F} }_B} = {E_{kB}}\} } {\rm{.}}$

定理3(决策类的合并^[23]). 给出决策表S=(U,CÈD,V,f)和决策子表S_i=(U_i,CÈD,V,f),iÎ{1,2,…,m}."BÍCÈD,令U/D={D₁,D₂,…,D_r},${U_i}/D = \{ {D_{i1}},{D_{i2}},...,{D_{i{q_i}}}\} $和${D_{all}} = \bigcup\nolimits_{i = 1}^m {{U_i}/B} = \{ {D_{11}},{D_{12}},...,{D_{1{p_1}}},...,{D_{m1}},{D_{m2}},...,{D_{m{q_1}}}\} {\rm{.}}$那么,"D_jÎU/D,我们有${D_j} = \bigcup {\{ F \in {D_{all}}|{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over F} }_D} = {D_{jD}}\} } {\rm{.}}$

定义6(等价类与决策类的相关性^[23]). 给出决策表S=(U,CÈD,V,f),BÍC.U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r}.如果E_kÇD_j=Æ,E_kÎU/B,D_jÎU/D,我们称E_k和D_j是相关的,表示为Ass(E_k,D_j)=True;否则,Ass(E_k,D_j)=False.

定理4(合并相关性^[23]). 给出决策表S=(U,CÈD,V,f)和决策子表S_i=(U_i,CÈD,V,f),iÎ{1,2,…,m}."BÍC,令U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r},${U_i}/B = \{ {E_{i1}},{E_{i2}},...,{E_{i{p_i}}}\} $和${U_i}/D = \{ {D_{i1}},{D_{i2}},...,{D_{i{q_i}}}\} {\rm{.}}$设

如果Ass(E_ih,D_ig)=True,那么Ass(E_k,D_j)=True.

定理5(等价类的Boolean表示^[23]). 给出决策表S=(U,CÈD,V,f)."BÍC,令U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r}.下面的结果成立:

(1) 如果$Ass({E_k},{D_{{j_1}}}) = True$且$Ass({E_k},{D_{{j_2}}}) = True,({j_1} \ne {j_2},{j_1},{j_2} \in \{ 1,2,...,r\} ,k \in \{ 1,2,...,t\} ){\rm{,}}$那么"D_jÎU/D,${E_k} \not\subset {R_B}({D_j}){\rm{,}}$表示为Boolean(E_k)=False;

(2) 如果$!jÎ{1,2,…,r},Ass(E_k,D_j)=True(kÎ{1,2,…,t}),那么${E_k} \subseteq {R_B}({D_j}){\rm{,}}$表示为Boolean(E_k)=True.

定理6(根据相关性计算上近似集). 给出决策表S=(U,CÈD,V,f)."BÍC,令U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r}."D_jÎU/D,D_j的上近似集可以表示为

${\bar R_B}({D_j}) = \bigcup {\{ {E_k} \in U/B|Ass({E_k},{D_j}) = {\rm{True}}\} } $

(10)

证明:因为Ass(E_k,D_j)=TrueÛE_kÇD_j¹Æ,那么根据定义3,有:

${\bar R_B}({D_j}) = \bigcup {\{ {E_k} \in U/B|{E_k} \cap {D_j} \ne \emptyset \} } = \bigcup {\{ {E_k} \in U/B|Ass({E_k},{D_j}) = {\rm{True}}\} } {\rm{.}}$

证毕.

定理7(根据相关性计算下近似集). 给出决策表S=(U,CÈD,V,f)."BÍC,令U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r}."D_jÎU/D,D_j的下近似集可以表示为

${R_B}({D_j}) = \bigcup {\{ {E_k} \in U/B|Ass({E_k},{D_j}) = {\rm{True}}|Boolean({E_k}) = {\rm{True}}\} } $

(11)

证明:证明过程同定理6的证明.证毕.

2.1MapReduce算法设计与实现

根据上文,我们给出了并行计算近似集的流程,如图 2所示.

根据定理2~定理4,我们给出了基于MapReduce的等价类、决策类及其相关性并行计算的流程图(如图 3所示),并设计了相关算法,见算法1.

算法1. 基于MapReduce的等价类、决策类、相关性并行计算算法(并行算法).

Map(key,value)

输入:key为文档名;value为S_i=(U_i,CÈD,V,f).

开始:

for each xÎU_ido

let key¢=‘E’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B}$ //‘E’标识符号,用于等价类

output.collect(key¢,1);

let key¢=‘D’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _D}$ //‘D’标识符号,用于决策类

output.collect(key¢,1);

let key¢=‘F’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _{B \cup D}}$ //‘F’标识符号,用于描述等价类与决策类是否相关

output.collect(key¢,1);

endfor

结束

Combine(key,V)/Reduce(key,V)

输入:key为相对于属性集B或D或BÈD的信息集;V为该信息集出现个数的列表;

开始:

if (key.startsWith(‘F’))

output.collect(key,1)

else:

let sum=0

for each val in V do

sum+=val

endfor

output.collect(key,sum)

endif

结束

我们通过以下两个方面优化了文献^[23]中提出的算法:

· 在算法设计上,将计算等价类、决策类与相关性放到同一个函数中,用标识符‘E’,‘D’,‘F’分别区分;

· 添加Combine阶段:用于Map结束后本地合并等价类、决策类与相关性.

在计算完等价类、决策类与相关性之后,根据定理5、定理6,根据已有的MapReduce结果,我们给出快速计算上、下近似集的流程图(如图 4所示).基于此,我们设计了快速计算上、下近似集的算法,见算法2.

算法2. 计算粗糙集上、下近似集计算算法.

输入:MapReduce程序输出的结果.

输出:各个决策D_j的上、下近似集的个数.

开始:

//计算决策D的上近似集的个数

for each $|R({D_j})|$ do

let $|\bar R({D_j})| = 0$;

for each S=(U,CÈD,V,f) do

if Ass(E_k,D_j)=True then

//||为信息集个数

;

endif

endfor

endfor

//计算决策D的下近似集的个数

for each E_k do

if $Ass({E_k},{D_{{j_1}}}) = = {\rm{True}}$ and $Ass({E_k},{D_{{j_2}}}) = = {\rm{True}},{j_1} \ne {j_2},{j_1},{j_2} \in \{ 1,2,...,r\} $ then

Boolean(E_k)=False;

else Boolean(E_k)=True

endfor

for each D_j do

let $|R({D_j})| = 0$;

for each E_k do

if Boolean(E_k)=True and Ass(E_k,D_j)=True then

; //||为信息集个数

end if

endfor

endfor

输出每个决策的上下近似集的个数$|\bar R({D_j})|,|R({D_j})|$.

结束

3 基于MapReduce的粗糙近似集的增量更新方法

这里,我们将讨论有新的数据进入到决策表的情况,假设新增决策表为S¢=(U¢,CÈD,V,f).下面我们将给出更新等价类、决策类及其相关性的相关理论.

推论1. 给出决策表S=(U,CÈD,V,f)."BÍC,令U/B={E₁,E₂,…,E_t}.新增决策表S¢=(U¢,CÈD,V,f),令U¢/B=$\{ {E'_1},{E'_2},...,{E'_{t'}}\} {\rm{.}}$对更新后的决策表S^*=(U,CÈD,V,f),U=UÈU¢,设${U^*}/B = \{ E_1^*,E_2^*,...,E_{{t^*}}^*\} {\rm{.}}$那么,$\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$$E_jÎ U/B或$\exists {E'_{j'}} \in U'/B{\rm{,}}$使得或换言之,$E_{{j^*}}^* = {E_j}$或$E_{{j^*}}^* = {E'_{j'}}$或$E_{{j^*}}^* = {E_j} \cup {E'_{j'}}{\rm{.}}$

证明:这里,我们用反证法来证明.$\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$假设使得或那么${E_j} \not\subset E_{{j^*}}^*$或${E'_{j'}} \not\subset E_{{j^*}}^*{\rm{,}}$也就是E_jÏU^*或${E'_{j'}} \notin {U^*}{\rm{.}}$而这与E_jÎUÍU^*且${E'_{j'}} \in U' \subseteq {U^*}$相矛盾.因此,假设不成立.那么,使得对于$E_jÎU/B或$\exists {E'_{j'}} \in U'{\rm{,}}$我们分3种情况来讨论:

(a) $\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$$E_jÎU/B且$\exists {E'_{j'}} \in U'{\rm{,}}$我们有$E_{{j^*}}^* = {E_j}{\rm{;}}$

(b) $\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$且$\exists {E'_{j'}} \in U'{\rm{,}}$我们有$E_{{j^*}}^* = {E'_{j'}}{\rm{;}}$

(c) $\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$$E_jÎU/B且$\exists {E'_{j'}} \in U'{\rm{,}}$我们有$E_{{j^*}}^* = {E_j} \cup {E'_{j'}}{\rm{.}}$

换言之,$\forall E_{{j^*}}^* \in {U^*}/B{\rm{,}}$$E_jÎU/B或$\exists {E'_{j'}} \in U'{\rm{,}}$或$E_{{j^*}}^* = {E'_{j'}}{\rm{;}}$或$E_{{j^*}}^* = {E_j} \cup {E'_{j'}}{\rm{.}}$

推论2. 给出决策表S=(U,CÈD,V,f),令U/D={D₁,D₂,…,D_r}.新增决策表S¢=(U¢,CÈD,V,f),令$U'/D = \{ {D'_1},$${D'_2},...,{D'_{r'}}\} {\rm{.}}$对更新后的决策表S^*=(U,CÈD,V,f),U=UÈU¢,设${U^*}/D = \{ D_1^*,D_2^*,...,D_{{r^*}}^*\} {\rm{.}}$那么,$\forall D_{{j^*}}^* \in {U^*}/D{\rm{,}}$$D_jÎ U/D或$\exists {D'_{j'}} \in U'{\rm{,}}$使得换言之,$D_{{j^*}}^* = {D_j}$或$D_{{j^*}}^* = {D'_{j'}}$或$D_{{j^*}}^* = {D_j} \cup {D'_{j'}}{\rm{.}}$

证明:证明过程同推理1的证明.

推论3. 给出决策表S=(U,CÈD,V,f)."BÍC,令U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r}.新增决策表S¢=(U¢,CÈD,V,f),$U'/B = \{ {E'_1},{E'_2},...,{E'_{t'}}\} ,U'/D = \{ {D'_1},{D'_2},...,{D'_{r'}}\} {\rm{.}}$对更新后的决策表S^*=(U,CÈD,V,f),U=UÈU¢,设U^*/B= $\{ E_1^*,E_2^*,...,E_{{t^*}}^*\} ,{U^*}/D = \{ D_1^*,D_2^*,...,D_{{r^*}}^*\} {\rm{.}}$设,如果Ass(E_k,D_j)=True或Ass(E_k¢,D_j¢)= True,那么有$Ass(E_k^*,D_j^*) = {\rm{True}}{\rm{.}}$

证明:证明过程同推理1的证明.

根据推论1~推论3,我们知道在数据增加时,等价类、决策类及其相关性可以通过增量更新方法快速得到.基于此,我们给出了并行增量更新的方法,如图 5所示.根据原有的中间结果和新增的决策表,我们分别处理,并合并成新的等价类、决策类及其相关性,然后根据算法2直接求得上、下近似集.具体的算法将在下一节中详细讨论.

3.1 并行增量算法设计与实现

根据推论1~推论3可知,我们需要额外的存储空间来保存原始决策表产生的中间结果.给出决策表S=(U,CÈD,V,f),BÍC,U/B={E₁,E₂,…,E_t},U/D={D₁,D₂,…,D_r},那么中间结果会产生t个等价类、r个决策类及txr个它们之间的相关性.因为每个等价类包含|B|个属性,每个决策包含|D|个属性,相关性只有一个值,所以需要的总的辅助存储空间为O(|B|xt+|D|xr+txr).

因为涉及到并行编程模型MapReduce,所以如何设计增量算法变得额外重要.不同于串行增量算法,如何将原有中间结果合并到现有过程,在并行增量算法变得至关重要.为此在本文中,我们尝试了从Map阶段和Reduce阶段分别导入原有中间结果,并为此设计了两种不同的基于MapReduce的并行增量算法.

3.1.1 并行增量算法I

对于原有决策表S=(U,CÈD,V,f)和新增决策表S¢=(U¢,CÈD,V,f).一般来说,MapReduce算法产生结果的数据规模远远小于之前的数据规模,这里,我们的更新方法很好地利用了这个性质,通过对原有决策表的MapReduce产生的中间结果保存,将其与新增决策表S¢=(U¢,CÈD,V,f)同时作为新的MapReduce算法的输入(即,从Map阶段导入原有中间结果),其流程如图 6(a)所示,具体操作详见算法3.在Map阶段,对新增决策子表及原来中间结果子集进行分别处理;在Combine和Reduce阶段,进行等价类、决策类及相关性的合并.然后,我们再调用算法2即可快速更新粗糙集上、下近似集.

算法3. 基于MapReduce的等价类、决策类、相关性并行增量更新算法(并行增量算法I).

Map(key,value)

输入:key为文档名.value为:

(1) 新增决策子表${S'_i} = ({U'_i},C \cup D,V,f){\rm{;}}$

(2) 原来的中间结果子集:OldRet_j=áInformationSet,Countñ键值对.

开始:

(1) 对新增决策表的处理:

for each $x \in {U'_i}$ do

let key¢=‘E’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B}$

output.collect(key¢,1);

let key¢=‘D’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _D}$

output.collect(key¢,1);

let key¢=‘F’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _{B \cup D}}$

output.collect(key¢,1);

endfor

(2) 原来的MapReduce结果子集处理:

for each val in OldRet_j do

let key¢=val.getKey(×);

let value¢=val.getValue(×);

output.collect(key¢,value¢);

endfor

结束

Combine(key,V)/Reduce(key,V)

输入:key为相对于属性集B或D或BÈD的信息集;V为该信息集出现个数的列表.

开始:

if (key.startsWith(‘F’))

output.collect(key,1)

else:

let sum=0

for each val in V do

sum+=val

endfor

output.collect(key,sum)

endif

结束

3.1.2 并行增量算法II

在第2种增量策略中,我们利用Hadoop中的分布式Cache直接将原有中间结果导入到Reduce阶段,其流程如图 6(b)所示,详细的算法描述见算法4.在Map阶段,只对新增决策子表进行处理;在Combine阶段,进行等价类、决策类及相关性的合并;在Reduce阶段,先进行初始化,导入原有的中间结果,再进行等价类、决策类及相关性的合并.之后,我们同样调用算法2即可快速更新粗糙集上、下近似集.

算法4. 基于MapReduce及分布式Cache的等价类、决策类、相关性并行增量更新算法(并行增量算法II).

Map(key,value)

输入:key为文档名;value为新增决策字表${S'_i} = ({U'_i},C \cup D,V,f){\rm{.}}$

开始:

//对新增决策表的处理:

for each $x \in {U'_i}$ do

let key¢=‘E’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _B}$

output.collect(key¢,1);

let key¢=‘D’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _D}$

output.collect(key¢,1);

let key¢=‘F’+${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} _{B \cup D}}$

output.collect(key¢,1);

endfor

结束

Combine(key,V)

输入:key为相对于属性集B或D或BÈD的信息集;V为该信息集出现个数的列表.

开始:

if (key.StartsWith(‘F’))

output.collect(key,1)

else:

let sum=0

for each val in V do

sum+=val

endfor

output.collect(key,sum)

endif

结束

Reduce(key,V)

初始化输入:原来的中间结果:OldRet_j=áInformationSet,Countñ键值对,存于分布式Cache.

输入:key为相对于属性集B或D或BÈD的信息集;V为该信息集出现个数的列表.

Let old_ret=Æ

初始化:

for each val in OldRet_j do

let key¢=val.getKey(×);

let value¢=val.getValue(×);

old_ret.put(key¢,value¢);

endfor

初始化结束

开始:

if (key.startsWith(‘F’))

output.collect(key,1)

else:

let sum=0

for each val in V do

sum+=val

endfor

old_val=old_ret.get(key); //如果不存在key,则返回值0;反之,则返回对应的值

sum+=old_val

output.collect(key,sum)

endif

结束

3.2 算法复杂度分析

给出决策表S=(U,CÈD,V,f),BÍC,在文献^[28]中,徐章艳等人利用基数排序的思想,给出了一种计算等价类U/B时间复杂度为O(|B||U|)的算法.因此,假定工作核数为p,并行计算等价类、决策类、相关性的时间复杂度(即算法1的时间复杂度)为

O(|B||U|/p+|D||U|/p+|BÈD||U|/p)=O(|BÈD||U|/p).

对应地,算法1将产生|U/B|个等价类、|U/D|个决策类和|U/BÈD|个相关性作为算法2的输入,因此,算法2的时间复杂度为

O(|U/D|log|U/BÈD|+|U/BÈD|log|U/BÈD|+|U/B|log|U/B|)=O(|U/BÈD|log|U/BÈD|).

因为并行算法由算法1和算法2构成,所以并行算法的时间复杂度为O(|BÈD||U|/p+|U/BÈD|log|U/BÈD|).

给出原有决策表S=(U,CÈD,V,f)的中间结果和新增决策表S¢=(U¢,CÈD,V,f),BÍC.在并行增量算法中,算法3针对新增决策表部分的时间复杂度与算法1相似,为O(|BÈD||U¢|/p).因为中间结果有|U/B|个等价类、|U/D|个决策类和|U/BÈD|个相关性,所以其时间复杂度为O(|BÈD||U/BÈD|/p).因此,算法3的时间复杂度为

O(|BÈD||U¢|/p+|BÈD||U/BÈD|/p)=O(|BÈD|(|U¢|+|U/BÈD|)/p).

因为并行算法由增量算法与算法2构成,令U^*=UÈU¢,所以并行增量算法的时间复杂度为O(|BÈD|(|U¢|+|U/BÈD|)/p+|U/BÈD|log|U/BÈD|).

在并行增量算法中,即算法3和算法4,它们只是导入原有中间结果的阶段有所不同,其时间复杂度相同.

假设原始对象集为U,增加的对象集为U¢,增加后的对象集为U^*=UÈU¢,并行算法和并行增量算法的时间复杂度分别为:

· 并行算法:O(|BÈD||U/p+|U/BÈD|log|U/BÈD|);

· 并行增量算法:O(|BÈD|(|U¢|+|U/BÈD|)/p+|U/BÈD|log|U/BÈD|);

我们不难发现:当U¢趋于无穷时,U=UÈU¢将近似等于U¢,两者时间复杂度趋于相等.这说明,随着增量数据的不断增多,增量算法的优势会越来越弱.

4 实验分析

在文献^[23]中,我们已经验证了基于MapReduce的并行算法可以很有效地处理大数据,这里我们只测试了并行增量算法的性能.

我们利用开源云计算平台Hadoop-1.0.1(http://hadoop.apache.org/)和Java 1.7.0_05在5台计算机(AMD Opteron Processor 2376处理器,8核,主频2.3 GHz,16GB内存)构建的云计算环境下进行实验,其中1台作为主节点,4台作为计算节点,每个计算节点提供4个Map槽和Reduce槽.

为了验证增量算法的性能,我们从UCI中选取了大数据集KDD99,该数据集含有近500万条记录和1个决策属性及41个条件属性,其中6个为符号型属性,35个数值型属性.我们的算法目前只针对符号型数据,因此,我们首先对35个数值型属性进行离散化处理.此外,我们用WEKA^[29]数据生成器RDG1,通过设置不同的样本数、属性个数、类别数据,产生了3个更大的数据集,大小分别为1.8GB,3.2GB和6.4GB,详细的数据描述见表 1.

我们把每个数据集平均分成10份,其中5份作为原有数据,另外5份作为增量数据,我们第1次增加1份,第2次增加2份,…令R_a为增量数据与原有数据的比值,称为增量变化率.这样,R_a分别为20%,40%,60%,80%和100%.然后测试这5种增量变化情况下,并行算法、并行增量算法I、并行增量算法II的性能,如图 7所示.

从图 7(a)中我们可以看出,在数据集KDD99上,随着数据的增多,运行时间基本维持不变.这是因为KDD99这个数据集相对于我们的云计算平台而言规模太小.从图 7(b)~图 7(d)可以看出,随着数据规模的不断增大,两种增量算法的性能越来越好.

为了更直观地表示增量变化率与运行时间之间的关系,我们采用以下增量加速比^[30]来说明:

$IncS = \frac{{{T_s}}}{{{T_i}}},$

其中,T_s表示并行算法的运行时间,T_i表示并行增量算法的运行时间.

表 2和表 3分别显示了并行增量算法I和并行增量算法II的增量加速比.与并行算法(非增量)相比,增量并行算法可以更快地执行完成.由结果可以看出:增量算法在数据集KDD99效果并不好,加速并不明显.其原因是Hadoop运行平台本身的延时较大,使得在小规模数据上表现不佳.总体而言,当增量变化率为20%时,并行增量算法I和并行增量算法II可以分别获得平均1.658 0倍和1.728 9倍的运行速度.同时,我们注意到,在前3个数据集上,增量加速比与增量变化率之间的关系并不明显,其中一个可能的原因是:当数据量不大时,系统测试时的波动性比较大.但是在最大的数据集Weka-6.4G,我们发现,随着增量变化率的增加,增量加速比递减,这与第3.2节中的算法复杂度分析相匹配.同时说明,随着新数据的逐渐增多,并行增量算法慢慢地失去优势;反之,新增数据越少,性能加速则越明显.从这一层面来看,并行增量算法对不断更新的实时模型有更好的支持,可以有效地应用于实时性要求更强的在线应用.

5 结 论

粗糙集算法已经广泛应用于数据挖掘与知识发现等领域.传统的粗糙集算法无法处理日益增长的海量数据.通过云计算中的MapReduce技术,用户可以很容易地使用云计算平台处理海量数据.不断变化的数据加大了云计算环境下知识更新的成本.本文结合MapReduce模型与增量更新算法,设计与实现了两种基于MapReduce的并行增量更新算法,并在较大的4个数据集上进行测试.结果表明:数据越多,增量算法取得的效果越好.同时,增量模型可以很好地利用原有结果,有效地减少运行时间,加快基于粒计算和粗糙集的海量数据挖掘与知识发现等的过程,继而降低云计算环境下知识更新的成本,对不断更新的实时模型有更好的支持,可以有效地应用于实时性要求更强的在线应用.我们将在未来的研究中,继续探讨基于粗糙集和MapReduce的并行增量算法在海量知识发现与知识提取中的应用与实现.