面向物联网的分布式均分Lasso算法

，，

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

物联网(Cyber-physical system)即物与物相连的互联网.目前，物联网一般定义：通过无线电频率识别(RFID)、红外传感器、全球卫星定位系统和激光扫描器等信息传感设备，依照一个统一协定的协议，把物品通过网络相互连接起来，达成物与物之间的信息交换，以实现对物联网中终端的智能化监控与管理的一种网络[1-4].近些年来，物联网技术逐渐地从理论研究开始延伸到现实生活中，越来越多的物联网公司与应用出现在人们面前，物联网技术与产品现在均处于一种快速生长的状态.这样的发展状态自然而然也带来了很多挑战，随着物联网的规模越来越大，物联网产生的数据也呈指数级增长，这些数据有着海量性、并发性和高维度性的特征.这些特征使得针对物联网数据的数据挖掘面临着许多困难，是当前必须解决的关键问题之一.

Tibshirani于1996年提出的Lasso算法作为一种具有稳定、快速和精准等特性的特征选择算法，可以在数据集进行分类之前通过对数据集使用Lasso算法，选择出强相关特征集来达到降低数据挖掘算法负担的效果[5- 6].Zou等[7]提出的弹性网络算法作为Lasso的一个改进算法，提高了算法的总体预测精度.Yuan等[8]提出了一种组Lasso算法，这一算法经过JACOB[9]和PUIG[10]的进一步改进，使得Lasso算法可以将某些需要同时加入强特征组的特征可以以一个组的形式进行特征选择.为了解决Lasso算法在海量高维度数据集上计算开销过大以及在高维度小样本集上的过拟合问题，施万锋等[11]提出了一种均分式的Lasso算法.笔者基于均分式Lasso算法，通过结合分布式计算平台，提出了一种分布式均分Lasso算法，在进一步提升Lasso算法计算效率的同时，通过并行化子集的特征选择过程，解决了均分式Lasso算法多次使用Lasso算法导致的计算消耗增加的问题.

1 背景介绍

1.1 物联网

Haller等[12]对物联网的概念提出了如下定义：“它是这样的一个世界，物理对象可以无缝集成到信息网络，并且可以成为业务流程的积极参与者.服务可以在网络中影响到这些‘智能对象’，找到他们的国家以及与他们相关联的任何问题，并能考虑到安全和隐私问题.”

从通讯的对象与过程来看，物与物以及人与物之间的信息交互是物联网的核心[13].基于这一核心，物联网有着3 个主要特征：1) 全面感知，主要表现在通过一些现有的电子与传感技术，随时对物联网中的物体(节点)进行信息采集与获取.2) 可靠传送，主要表现在通过将物联网中的物体接入信息网络，利用有线或是无线网络(如传感器网络、移动通信网和互联网等)，将获取到的关于物品的信息随时随地传输出去.3) 智能处理，主要表现在利用各种智能计算技术(如云计算、模糊识别和模式识别等)，将收集到的海量、异构性传感器数据与信息进行分析并处理，实现智能化地管理与控制.

1.2 Lasso算法基本概念

在统计学和机器学习中，Lasso算法(Least absolute shrinkage and selection operator，即称为最小绝对值收敛和选择算子或者又称为套索算法)是一种同时进行特征选择和正则化的特征选择方法，旨在增强统计模型的预测准确性和可解释性，最初由斯坦福大学统计学教授Robert Tibshirani于1996年基于Leo Breiman的研究提出[14-17].

Lasso最初是为最小二乘模型制定的，揭示了估计量行为的大量数据，包括其与岭回归和最佳子集选择的关系以及Lasso系数估计与所谓的软阈值之间的联系.同时，如标准线性回归一样，算法如果协变量是共线的，则系数估计不必是唯一的.

虽然最初目的比较单一，Lasso正则化可以简单地扩展到广泛的统计模型中去，包括广义线性模型，广义估计方程，比例风险模型和M估计[18-19].Lasso执行子集选择的能力取决于约束的形式，并具有多种解释，包括几何、贝叶斯统计和凸分析.

(1)

(2)

式(2)可重写成为

(3)

式中λ与t之间的关系取决于具体数据库.

接下来，笔者尝试分析一些Lasso估计器的基本属性.

首先假设协变量是正交的，因此(xi|xj)=δij，其中：(·|·)为内积空间；δij为克罗内克函数.然后，使用次级方法，可得

(4)

到目前为止，为了弥补原始算法的某些限制，并使该方法对于特定问题更有用，有很多种变种算法被提出.几乎所有算法都侧重于在协变量中尊重或利用不同类型的依赖关系.

1.3 LARS算法

统计学中，最小角度回归算法(LARS)是由Bradley Efron等开发的用于拟合高维数据的线性回归模型的算法[20].

LARS解决方案由表示参数向量的一范式的每个值的解的曲线组成而不是直接给出向量结果.该算法类似于前向逐步回归，而不是在每个步骤中包含变量，估计参数在等于每个与残差相关的方向上增加.

这一算法的基本步骤如下：

1) 将所有系数βj设为0.

2) 找出与y最相关的预测因子xj.

4) 在βj，βk的联合最小二乘方向上增加，直到一个新的预测因子xk与残差r有更大的相关性.

5) 重复2)～4)直到所有的预测变量都在模型中[21].

1.4 均分式Lasso算法

LARS算法在一般数据集上的表现十分优秀，其具有特征选择过程高效，选择结果稳定的特点.然而，随着数据集数据量和特征量的增加，LARS算法的一些问题也逐渐显露出来.这一算法在面对高维度海量数据集时，往往有着计算开销过大的问题；而面对高维度小样本数据集时，又会产生过拟合的问题.

为了解决这一问题，施万锋等[11]提出了一种均分式的Lasso算法.在普通Lasso算法中，特征选择的时间复杂度与维度的二次方和样本数成正比，高维度海量数据集就意味着高计算消耗.因此，均分式Lasso算法采用将数据集的特征集分割为K份，从而使得计算开销降低K的二次方.同样，在面对高维度小数据集时，将样本分为K份能够降低样本数与维度数的比例，从而有效地缓解过拟合问题.

这一算法的伪代码如下：

INPUT：预测数据集S，特征集X，样本集Y，分片数K

OUTPUT：强相关特征集X″

BEGIN

X′=[]；//初始化X′

FORi=1 toK

X′[i]=Lars(SX[i])；//X[i]为X的第i个分片，SX[i]为有这一分片的特征的数据自己

X′=X∪X′[i]；//将各个特征集合并为一个特征集

ENDFOR

X″=Lars(SX′)；//最后对特征集进行一次LARS选择

END

2 分布式均分Lasso算法

2.1 分布式Lasso算法

与均分式Lasso算法不同，分布式Lasso算法和LARS算法在本质上并没有不同之处，它是一个LARS算法的基于Hadoop云计算平台的分布式实现.这一算法的主要目的是在于将算法中的矩阵运算等过程并行化以达到提升算法执行效率的目的.

2.2 算法提出

针对均分式Lasso算法在对分片进行特征提取时，不能有效地利用物联网集群特性的问题，提出了一种分布式的均分Lasso算法.这一算法在分布式Lasso算法与均分式Lasso算法的基础上，将均分式Lasso算法中耗时显著的分片特征选择过程进行了并行化处理.

2.3 算法设计

1.4节与2.1节中的两种算法分别从数据集以及计算过程两个方面对LARS算法进行了运算效率上的改进.同时，考虑到物联网环境下数据本身的分布特性，本节中提出一种融合了上述2 种算法的新算法.

对于这一算法，除了将数据集均分后进行LARS算法时使用分布式计算，由于每个分块在首轮计算中的不相关性，还可以根据均分数K，将子数据集分配到不同节点上并行计算.

算法的伪代码如下：

INPUT：预测数据集X，样本集Y，分片数K

OUTPUT：强相关特征集X1

BEGIN

根据K与当前集群中节点数量，将集群分割为M个子群，并建立其任务队列QM；

初始化合并数据集X′；

FORi=1 toK

根据i与K取出数据集X中对应的子集XKi；

创建对XKi的分布式Lasso算法计算任务TKi；

遍历所有任务队列，找出其中最短的队列QMj，将TKi加入QMj中；

TKi完成后将结果Ai合并至X′中；

ENDFOR

对X′进行分布式Lasso算法运算，获得最终结果X1；

END

2.4 算法复杂度分析

假设应用分布式均分Lasso算法的数据集的特征集为Y，设特征数N=sizeof(Y).分片数为K，分片经过特征选择后的特征数为N′.传统的Lasso算法的时间复杂度可以表示为O(N3+N2n),则均分式Lasso算法的时间复杂度可表示为

而分布式均分Lasso算法的时间复杂度则可表示为

当N

同理，当N≥n时，算法的时间复杂度可简化为

3 实验与分析

3.1 实验设计

为了探索Lasso算法在物联网数据挖掘上应用的可行性，本节设计并实现一个对比不同Lasso算法(传统Lasso算法，均分式Lasso算法以及分布式均分Lasso算法)性能的实验.

为了保证实验的准确性，3 种Lasso算法均使用由Bradle提出的LARS改进型算法.传统LARS算法以及均分式Lasso算法运行于一台四核、4 G内存的虚拟机上，分布式Lasso算法运行于一个由4 台虚拟机组成的Hadoop集群上.每个算法具体的运行平台如表1所示.

表1 对比实验运行平台设置Table 1 Configuration of the platform for experiment

相较于LARS算法和均分式Lasso算法，分布式Lasso算法使用了4 台单核、1 G内存的虚拟机，使其总计算能力和前两者采用的虚拟机基本持平，以此来保证实验结果的公平性与准确性.

实验中采用9 个数据集，分别使用上述3 个算法.对于每个算法-数据集组合进行20 次实验，并求平均值以获得最终结果.

3.2 实验数据

为了测试分布式均分Lasso算法的有效性，从UCI数据仓库[22]中选取了9 个数据库进行实验.其中，前5 个为低维度的数据集，后4 个为高维度的数据集.数据集详情如表2所示.

表2 实验使用数据集Table 2 Datasets used for the experiments

3.3 小数据集上的实验数据对比

本节中，分布式均分Lasso算法与均分式Lasso算法的分片数采用了K取3,5,7这3 种情况.3 个算法在5 个数据集下的表现如表3，4所示，其中Iris，Breast数据集由于特征数较少，缺少部分数据.

通过表3可以看出：均分式Lasso算法和分布式均分Lasso与传统Lasso方法相比，精度基本上一致.少数数据集上精确度降低的原因在于，对特征集进行拆分后，某些与类标签强相关的特征可能在特征子集中无法显出这一特性，导致在对特征子集进行特征选择时，这些特征发生丢失，进而影响了总体分类算法的精确度.当然，由于Lasso算法本身的稳定性以及数据特征集分布的随机性，这类情况出现时对分类算法的精度影响并不明显.因而，可以认为，均分式Lasso算法与分布式Lasso算法在小数据集上均能够保证足够的精度.

从表4中可以看出：和传统Lasso算法相比，均分式与分布式均分Lasso算法在小数据集上的运算效率均显得较低.这是由于在小数据集上，特征集拆分导致的Lasso算法计算量下降程度要小于引入更多次Lasso算法带来的额外计算量.分布式均分Lasso算法相较于均分式Lasso算法，其计算效率有着显著的提升.在小数据集上，这一提升主要体现在子特征集的并行化计算上.

表3 不同算法在在小数据集上的精度性能Table 3 Accuracy performance of different algorithms over small dataset

表4 不同算法在在小数据集上的时间性能Table 4 Time performance of different algorithms over small dataset

3.4 大数据集上的实验数据对比

上节实验已证明分布式均分Lasso方法在低维度数据集上的可行性.接下来，本节将分别选择低维海量数据集Poker，高维海量数据集Gisette，高维小样本数据集Dorothea和Arcene，从不同方面验证改进Lasso方法的有效性.实验结果如表5，6所示.

对于低维海量数据集Poker，3 种算法都遇到了计算量过大的问题(运行时间超过4 h).这是由于对于低维度数据集Poker来说，计算量主要由其海量数据引起.Lasso算法对于其已经很小的特征集进行划分与否无法很明显地影响到计算量.这一实验结果与2.4中的理论分析保持一致.

对于高维度小样本集Dorothea来说，随着分片数的提升，3 种算法的分类精度基本保持一致，这一结论与3.3中算法在小数据集上的结论保持一致.同时，从表6中可以看出：随着分片数的上升，均分式Lasso算法的计算效率逐渐提升.然而，从K=20到K=40的计算效率提升明显高于从K=40到K=60的提升.再对比分布式均分Lasso算法的结果，可以明显看出：从K=40到K=60时，均分式Lasso算法的计算效率提升是由于对特征子集的Lasso算法计算效率提高导致.而通过检查第一轮特征选择后获得的强特征集的特征数(K=40时为279，K=60时为499)，可以发现：相较于K=40，K=60的分片对于Dorothea这个特征集来说过于细致.从另一个高维度小样本集Arcene的实验结果中可以观察到类似现象(在这一组实验中，最优分片数显然是在K=20附近).

除去分片数有最优解的现象外，还能从两个小样本集中发现：均分式与分布式均分Lasso算法可以解决传统Lasso算法在面对高维度小样本集时遇到的过拟合问题.同时，通过2 个数据集的对比，这一特性随着特征数的增加与样本数的减小而越发显著.

同时，随着分片数K的增长，Arcene数据集实验的计算效率显著降低，产生这一结果的原因类似于Dorothea数据集，即随着K的增长，对特征子集的特征选择并不能很好地排除弱相关特征，使得最终获得的强特征集过大，影响了计算效率.

对于一个样本数和特征数均较多的数据集，以Gisette为例，单纯拆分特征集虽然不会影响到分类精度，却不能非常有效地降低计算效率.这是由于对于被均分的特征子集，每一个都是低维度海量数据集.

表5 不同算法在在大数据集上的精度性能Table 5 Accuracy performance of different algorithms over large dataset

表6 不同算法在在大数据集上的精度性能Table 6 Accuracy performance of different algorithms over large dataset

4 结 论

设计实现了一种分布式均分Lasso特征选择算法，这一算法融合了了分布式计算与均分式Lasso算法，通过分布式并行化运算，消除了均分式Lasso算法需要进行多次迭代运算导致计算效率下降的问题.从实验结果可以看出：分布式均分Lasso算法在均分式Lasso算法的基础上进一步提升了计算效率，同时保持了分类算法精度，并且分布式均分Lasso算法的K取值有着最佳值.但是，分布式均分Lasso算法对于百万级别的低维海量数据集(如Poker)依然显得无力，无法提升计算效率.未来工作可以围绕着以下方向进行：1) 研究对于一个给定的高维数据集，如何通过计算或公式获得最佳的分片数K，使得分布式均分Lasso算法可以在这个分片数下获得最高的计算效率.2) 研究如何降低Lasso算法在海量数据集上的计算消耗；尝试通过对数据集的样本集进行拆分后分别进行Lasso算法的做法来达到这一目的；并研究这一方法对于分类精度的影响.3) 研究如何将笔者提出的算法应用到物联网中间层节点，利用物联网本身的分布性特征，在物联网数据被收集前提前进行特征选择运算，达到降低计算消耗和网络通讯量的目的.