并行PSO结合粗糙集的大数据属性约简算法

李 华，刘占伟，郭育艳

(1.河南工程学院 计算机学院，河南 郑州 451191；2.河南工程学院 理学院，河南 郑州 451191；3.河南财经政法大学 科研处，河南 郑州 450046)

0 引 言

从海量复杂事件中按照既定要求提取所需信息是实现大数据分析与模式识别的首要步骤。然而，这些复杂事件通常具有分布式、多源异构以及冗余性较高等特征。因此，最大程度减少由于信息冗余或不相关数据引起的额外物理开销或时间开销是十分必要的。其关键技术称为数据集属性约简[1]。

文献[2]提出基于朴素贝叶斯数据过滤的属性约简算法，但该算法在数据属性数量或属性间关联度过大时，约简算法性能将呈现明显下降趋势。文献[3,4]提出基于数据封装和嵌入的属性约简算法，针对预先设定的归纳方法和区域，制定最佳的属性子集，然而这样的性能改进会消耗大量的计算资源[5,6]。文献[7]针对教育大数据高维度、不完备、增量型等现状，基于粗糙集理论构建了不完备决策表的差别信息增量更新算法，实现高维数据属性的有效约简。文献[8]指出，求解属性约简问题属于NP-hard问题，而传统串行启发式搜索方法存在求解耗时过长甚至无解的情形[9]。

因此，提出基于MapReduce(映射-归约)框架的并行粒子群算法结合粗糙集理论的数据属性约简算法。主要创新点总结如下：

(1)对基于粗糙集理论的大数据属性最小约简问题进行建模，通过定义数据集属性的上、下逼近实现了对数据属性不确定性的有效处理；

(2)提出了基于粗糙集大数据属性约简与并行粒子群算法相结合的完整算法设计步骤，相比传统串行求解算法，提出的并行算法在同样的迭代次数下，能够有效提升数据属性约简运行效率；

(3)基于MapReduce框架搭建了提出的并行求解算法的实验平台，分别给出了MapReduce框架中驱动程序、映射程序和汇总程序的算法步骤。

基于几个公开数据集，通过实验对提出的方法和其它现有方法进行比较分析，验证了提出方法的优越性。

1 提出的数据属性约简方法

1.1 粗糙集理论

数据集中隐藏的信息可用四元组(U,A,V,f)表示，其中U={u1,u2,…,uN}为N个对象或实例的非空有限集合，称为论域，A为具有(n+k)个属性或特征的集合。V为属性值集合，f为U×A→V的一个映射。此外，属性集A满足A=C∪D，其中C={a1,a1,…,an}是具有n维度的条件属性集，D={d1,d2,…,dk}为具有k维度的决策属性集。对于A中的每个元素a(即a∈A)，在属性值集合V中均能找到对应的值Va，从而属性值集合V即为A的值域。四元组(U,A,V,f)又称为决策表。

在对数据集进行分类时，相差不大的个体被归于同一类，而同一类中的数据间的关系称为不可分辨等价关系(indiscernibility relation，IND)。用数学语言描述为，对于任意一个非空属性集合P⊆C，不可分辨关系表述为

IND(P)={(u1,u2)∈U×U:∀a∈P,
f(u1,a)=f(u2,a),a∈P}

(1)

其中，f(u,a)表示实例u对应属性a的取值。若(u1,u2)∈IND(P)，则u1的属性无法与u2的属性区分开。进一步地，令[u]P表示P下的元素u(∈U)，从而集合U可约简出存在不可分辨关系的集合，称为基本等效类集合，记为U/P满足

[u]P∈U/P

(2)

对于集合X⊆U，当集合X能够表示为基本等效类集合时，则称其是可以精确定义的；反之，集合X仅能通过基本等效类集合以逼近的方式来刻画。其中，集合X关于不可分辨关系P的下逼近定义为

P_(X)={u∈U:[u]P⊆X}

(3)

其实际意义为根据已有知识来判定肯定属于集合X的对象所组成的最大集合，并将P_(X)称为集合X的正区，而根据已有知识来判定肯定不属于集合X的对象组成的集合则称为集合X的负区。

集合X关于不可分辨关系P的上逼近定义为

P_(X)={u∈U:[u]P∩X≠∅}

(4)

其实际意义为，P_(X)为所有与X相较非空的[u]P的并集，即那些可能属于集合X的对象所组成的最小集合。从而集合X关于P的边界区定义为

BN(X)=P_(X)-P_(X)

(5)

如果边界区域是空集，则称X为精确集合，反之则称其为粗糙集合。为了衡量两个不同属性间的依赖程度，引入依赖度量函数，定义如下：

设P、Q为集合U的两个不同属性，则属性Q对属性P的依赖度函数γP(Q)定义为

(6)

式中：γP(Q)∈[0, 1]，∪表示并集操作，|·|表示集合的势，用于度量集合规模的大小。若γP(Q)的取值更接近于1，表明Q更依赖于P。根据这一概念，若约简集合R是条件属性集合C的子集，则应存在γR(D)=γC(D)。

1.2 基于粗糙集的大数据属性约简建模

若属性a能够从集合P中移除而不改变U相对于P的等效类划分，则它在P中称为是多余的属性，反之则称其为不可或缺的属性。为此，定义条件属性集合C的最小约简集R*⊆C，删去R*中任何属性项，等价类集合P都将发生变化，即

[x](R*-{a})≠[x]C

(7)

集合R*同样被称为信息系统(U,A,V,f)的基本属性。不妨令集合R1为与γC(D)具有相同依赖度的所有约简集，则最小约简集的定义为

R*∈{R∈R1:|R|≤|S|,∀S∈R1

(8)

因此，可将最小约简问题的求解形式描述为

(9)

2 基于MapReduce的并行粒子群求解算法设计

对于大数据分析或模式识别问题而言，数据集存在格式多样、信息稀疏的特点，故暴力枚举或串行求解算法的时间复杂度极高。为提升对目标问题(9)的求解效率，从两个层面提升数据集属性约简效率：①采用并行粒子群算法代替串行粒子群算法对最小约简集进行求解；②采用MapReduce并行计算框架对数据集进行分解操作以降低问题求解规模。

2.1 MapReduc框架下总体求解方案

MapReduce作为谷歌公司开发的并行计算框架，如图1所示。

图1 MapReduce并行数据集属性约简框架

包含两个关键的操作：①map(映射)操作，即分解计算任务；②reduce(汇总)操作，即将子任务计算结果汇总。其核心思想是利用数据的局部特性将数据分割为相互独立的数据块，由多个映射器进行并行处理后，最终由reduce操作对映射器输出结果进行汇总。所提MapReduce框架的求解过程如图1所示(假设有4个计算节点)。Map-Reduce上运行数据集属性约简并行粒子群算法可分为3个主要部分：驱动程序、映射程序和汇总程序。

2.2 驱动程序

驱动程序的作用是在计算节点之间划分计算任务量，从而使得各计算节点能够根据划分的数据块计算生成前文所述的子信息系统。为保证每个计算节点的承担的任务量均衡，即平衡计算负载以确保计算性能，提出如算法1所示的驱动程序，其核心思想是每次MapReduce迭代完成后，通过计算每个计算节点要处理的数据块的起始索引和大小，实时调整下一次迭代时每个计算节点的任务量。其中m表示m次迭代结果，ST是m次和m-1次迭代结果的平均数，K表示计算节点数量。

算法1：驱动程序

(1)ST←m(m-1)/2；S← [ST/K]；

(2)is← 1;count← 1; %is为数据块的起始索引，count为计数器

(3)whilecount≤Kdo%程序在计算节点数量内运行

(4)a1←m-is;

(5)b← -(1+2a1);

(7) compute a valid value forn;

(8) saveis, n;

(9)is←is+n;count←count+ 1;

(10)endwhile

2.3 映射程序

映射程序是为了计算提取子数据集的信息系统参数，即生成子数据集的决策表。其中前N行表示条件属性，最后一行表示决策属性，最终生成的决策表记为b，其中的元素构造方法如下

(10)

(11)

算法2示出了计算节点生成子数据集决策表的流程，即首先从HDFS中读取数据集，并使用驱动程序进行数据集划分，最终计算节点的计算结果输出至汇总程序。

算法2： 映射程序

(1)r←is; %r为数据块起始索引， 由算法1确定

(2)whiler

(3)i←r+1;

(4)whilei≤mdo% 以下程序执行对数据集的划分

(5)ifd(r)≠d(i) then

(6) DistinctTable[r] = Compare(Dataset[r], Dataset[i])

(7) emit(DistinctTable[r]);

(8)endif

(9)i←i+1;

(10)endwhile

(11)r←r+1;

(12)endwhile

2.4 汇总程序

计算节点的输出结果可供所有的汇总节点使用，每个汇总节点负责收集各计算节点的决策表作为初始粒子群并执行并行粒子群算法操作。粒子群算法的程序同样由驱动程序执行，包含粒子数量、适应值计算、最优个体极值、最优全局极值[10]。

粒子群优化(particle swarm optimization，PSO)算法的基本概念是，建立一个群体中每个个体都遵循的运动模型，通过迭代获取个体和群体的最优解，也就是个体极值和全局(局部)极值。PSO算法的数学描述始于二维空间中，对个体运动的图形化表达，并由此延申到N维空间，构成了PSO算法的完整数学表达：Xi=(x1,x2,…,xN)表示粒子i在N维空间内的位置，Vi=(v1,v2,…,vN)表示粒子的飞行速度，对于第k次迭代，每个粒子的运动可以表示为

(12)

(13)

式中：群体粒子总数为M，i=1, 2,…,M，表示第k次迭代粒子i速度矢量的第d维分量，表示第k次迭代粒子i位置矢量的第d维分量，pid表示粒子i个体发现最好位置的第d维分量，pgd表示群体发现最好位置的第d维分量，c1、c2表示权重因子，w表示惯性权重函数。算法流程如图2所示。

图2 粒子群优化算法流程

并行PSO算法采用主从和多数据流结合的模式编程，完成初始化、任务分配、粒子选择和粒子适应性计算的过程。具体的迭代过程与式(12)和式(13)相同，即通过比较优选整个种群的最优值，更新每个粒子的速度及位置，最终找到满足要求的最小适应阈值。算法3示出了汇总操作阶段的算法流程。

算法3： 汇总程序

(1)gen ← 0;

(2)MaxFitness ← -In finity;

(3)InitializeParticleSwarm (ParticleSwarm); %初始化粒子群算法

(4)while Fitness≤finialvalue do %当适应度数值<终止条件时执行

(5)Evaluate (ParticleSwarm, DistinctTable);

(6)r← 1;

(7)whiler< NumParticleSwarm do

(8)UpdateSpeedPosition (ParticleSwarm, DistinctTable); %更新粒子速度与位置

(9)end while

(10) gen ← gen + 1;

(11)end while

(12)emit(MaxIndividual(ParticleSwarm))

3 实验结果及讨论

3.1 实验设置和数据集

为验证所提算法的优异性和可行性，采用传统串行PSO[11]、非MapReduce框架的并行粒子群算法[12]作为对比算法对同一数据集属性进行最小化约简。设置4个数据集进行实验，见表1，包括实例数(#Inst)、属性数(#Attr)、组合数(#Comb)和区分表中的行数(#DTRows)。并评估不同约简算法的性能：Spam-base[13]、NSL-KDD[14]、Kyoto[15]和CDMC2012[16]。这些数据集被广泛用作相关入侵软件检测、垃圾邮件过滤等算法的基准算例，且不同的数据集具有不同的统计特征，拥有大量的个体实例与特定的属性。实验使用分布式Hadoop集群[17]进行，软件环境为Java 7.0、Ubuntu 14.0.4系统，硬件配置为16 GB RAM、4核Intel处理器。分布式粒子群算法的种群大小设置为100，迭代终止阈值设置为属性约简维度变化小于1。其中，约简维度表示从原始高维数据映射到低维数据空间后所减少的维度数量。

表1 实验数据集

3.2 算法运行时长与数据属性约简性能对比

首先对比分析传统顺序粒子群算法和并行粒子群算法在同样迭代次数下的算法运行时长和属性约简性能。此外，本组实验还讨论了计算节点数量对运行时长与约简性能的影响。实验结果如图3所示。当计算节点数量设置为4时，相同迭代次数下，对4个数据集属性约简采用本文提出的MapReduce-并行PSO的运行时长比传统串行PSO分别缩短了69%、70.7%、72.7%和72.4%，平均运行时间降低了71.2%；而比非MapReduce-并行PSO[12]分别缩短了56.67%、57.89%、57.14%和60.81%，平均运行时间缩短了58.13%；而计算节点数量设置为8时，相同迭代次数下，对4个数据集属性约简采用本文提出的MapReduce-并行PSO的运行时长比传统串行PSO分别缩短了57.1%、62.2%、63.6%和62.9%；而比非MapReduce-并行PSO分别缩短了40%、45.61%、42.86和47.30%。故可知本文提出的MapReduce-并行PSO能够显著提升算法执行效率。此外，4个数据集下8计算节点的算法运行时长比4计算节点的运行时长上升了27.8%、22.6%、25%和25.6%。表明简单地增加计算节点并不能始终带来算法执行效率的提升，这是由于计算节点的增加导致MapReduce需要更多地执行数据迁移与存储操作，从而导致额外的物理开销与时间开销。

图3 3种算法对不同数据集的运行时长

进一步地，在相同迭代次数下，串行PSO与2个并行PSO对统一数据集的属性约简性能如图4所示。此外，同样讨论了计算节点数量对属性约简性能的影响。可知，相同迭代次数下，当计算节点为4时，本文提出的MapReduce-并行PSO对4个数据集的属性约简维度比串行PSO分别下降11.3%、16.7%、50%和46.7%；而比非MapReduce-并行PSO分别缩短了6%、9.09%、33.3%和20%；当计算节点为8时，提出的并行粒子群算法对4个数据集的属性约简维度比串行PSO则分别下降28.3%、4.2%、40%和40%。表明所提算法在规定的迭代次数中具有更好的属性约简效果。此外，4个数据集下8计算节点的约简维度比4计算节点的运行时长分别下降19.1%、-15%、-20%和-12.5%，而比非MapReduce-并行PSO分别缩短了24%、-4.55%、21.43%和10%，这表明通过简单地增加计算节点不能始终带来约简维度的下降。

图4 3种算法对不同数据集的属性约简效果

为进一步说明所提算法的优异性，分析达到相同属性约简效果下的算法运行时长。图5示出了随着属性约简维度的变化算法运行时长的变化趋势。图6为本文提出的MapReduce-并行PSO相比MapReduce-并行PSO、串行PSO的运行时长改进比例。

图5 不同算法运行时长随属性约简维度的变化趋势

图6 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的运行时长改进比例

从图5、图6可以看出，当约简维度从10变化到57时，串行PSO的运行时长增加了75.2%；非MapReduce-并行PSO运行时长增长了72.5%；而具有4个计算节点的并行粒子群算法运行时长则仅增加了57.1%，提出的Map-Reduce-并行PSO的初始运行时长比串行算法少64.3%。而随着约简维度由10变化到57时，对非MapReduce框架下并行PSO算法的改进比例由40%增长到63%，而对串行PSO算法的改进比例由59%增长到74%。由此可见，随着属性约简维度的上升，提出MapReduce-并行PSO运行时长并未显著增加，展现出了与传统算法相比更强的运行稳定性能。

3.3 算法性能影响因素分析

进一步讨论影响算法性能的其它因素。除去MapReduce框架为属性约简提供的计算节点数量外，数据块决策表的大小同样决定了算法的运行性能。具体而言，即数据块的属性数量以及数据块包含的个体数量。因此，不失一般性设置两组实验，即分别采用Spam base数据集和CDMC2012数据集作为实验算例，采用Weka中的滤波器随机形成具有不同大小的5组子数据集，分别包括2000、4000、6000、8000和10 000个样本。并对每个子数据集运行5次后的算法运行时间取其平均值作为对比。图7示出了不同数据规模下的传统串行PSO和所提出的并行粒子群算法运行时长，图8为本文提出的MapReduce-并行PSO相比非MapReduce-并行PSO[12]、串行PSO的运行时长改进比例。

图7 串行PSO和2个并行PSO运行时间比较

图8 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的运行时长改进比例

从图7、图8可知，初始规模下，两个算法之间的运行时间相差不大。然而，随着数据规模由2000增长到10 000，串行PSO的运行时长增长了8000 s，非MapReduce-并行PSO运行时长增长了5930 s，而提出的并行粒子群算法的运行时长则增加了2600 s。对非MapReduce框架下并行PSO算法的改进比例和对串行PSO算法的改进比例最终分别稳定在55%和67.5%左右。因此，本文提出的MapReduce-并行PSO能够有效减少算法运行时间。此外，随着数据规模的不断增长，仅设置4个计算节点的数据存储和迁移造成的时间开销已然不能忽视，为节约计算时间，提高属性约简效率，可通过增加计算节点的方式来分担计算任务量。

4 结束语

针对大数据分析和模式识别过程中的数据属性约简问题，提出了MapReduce环境下的并行粒子群算法与粗糙集理论相结合的约简算法。通过并行粒子群算法和MapReduce分布式计算两个层次来实现数据集属性约简计算的效率提升。算例结果表明，与传统串行PSO相比，在相同的迭代次数和数据集规模下，所提并行计算方法有效节约了运行时长，且对数据集属性的约简效果也更优。此外，实验结果还表明，当数据规模不断增大时，采用MapReduce分布式计算和并行粒子群算法的架构比传统串行粒子群算法能够在更短的时间内得到数据集属性约简结果，故而所提算法在工程应用中更具优异性和适用性。

未来将深入研究并行粒子群算法关键参数对数据集属性约简性能的影响以及约简性能，进一步提升算法性能。