基于稀疏表示的大数据在政府统计工作中应用

张 乾，金升菊,罗玉坤

(1.贵州省模式识别与智能系统重点实验室，贵阳 550025；2.贵州民族大学 工程实训中心，贵阳 550025；3.贵州省统计科研教育中心，贵阳 550001)

0 引言

大数据(big data)是信息时代的产物，其指涉及的资料数量级上巨大到无法透过目前主流软件工具在合理时间内达到撷取、管理、处理、并整理，数据一般呈现结构化、非结构化和半结构化。随着大数据的到来，政府统计业务工作面临新的挑战，数据统计关键技术越显重要。在大数据应用技术越来越普及的背景下，对大数据的基础理论研究对大数据应用推广有着十分重要的意义。

牛津大学教授维克托·迈尔·舍恩伯格在其新书《大数据时代》[1]中说，这是一场“革命”，将对各行各业带来深刻影响，甚至改变我们的思维方式，但同时它也引发“数据暴政”的担忧。2012年国际著名的咨询机构Gartner发布了大数据技术成熟度曲线，分析提出了当前大数据面临的技术挑战和问题，主要包括对数据的属性约简(降维)、计算—存储—管理提升、数据复杂度理论、数据感知和数据安全等。

目前，大数据研究主要平台是Hadoop和Map Reduce框架下进行。大数据已经初步应用在医疗、金融、电子商务、零售、电信、交通等应用领域和SAP、Oracle、IBM、EMC、微软、浪潮等大厂家在大数据的发展定位和策略上。Spark由加州伯克利大学AMP实验室的Matei为主的小团队所开发，是一个基于内存计算的开源集群计算系统，使得数据分析更加快速。Spark是一种与Hadoop相似的开源集群计算环境，但是两者之间还存在一些不同之处，这些有用的不同之处使Spark在某些工作负载方面表现得更加优越，换句话说，Spark启用了内存分布数据集，除了能够提供交互式查询外，它还可以优化迭代工作负载。文献[2]和文献[3]对大数据目前研究现状进行综述后认为，大数据研究仍集中在管理模式创新和价值发现算法上，还有部分是大数据处理的调度算法研究。

本文主要探讨大数据的稀疏表示算法,提出一种改进的、有效的大数据稀疏表示算法，并做了大量数据实证分析。

1 研究现状

对大数据理论研究主要包括对数据的属性约简(降维)、计算—存储—管理提升、数据复杂度理论、数据感知和数据安全等。对属性约简(降维)研究主要有局部代替全局和优化处理等研究途径。

在大数据按需简约方面，经典的有主成分分析（PCA)将多个变量通过线性变换以选出较少个数重要变量的一种多元统计分析方法，主要考虑增强方差。线性判别分析（LDA）是一种提高类间方差降低类内方差的方法。等距映射（Isomap）主要目标是对于给定的高维流形，欲找到其对应的低维嵌入，使得高维流形上数据点间的近邻结构在低维嵌入中得以保持。局部线性嵌入（LLE）将高维数据中的某点用周边的数据点的线性表示。Laplacian特征映射基本思想是用一个无向有权图描述一个流形，然后通过用图的嵌入来找低维表示，简单来说，就是在保持图的局部邻接关系的情况下，将其图从高维空间中重新画在一个低维空间中。局部保留投影（LPP）主要目的是保存高维数据在局部上的相似性。局部切空间排列（LTSA）主要是先考虑用每一点处的局部切空间表示该点处的几何特征，然后用局部切空间进行排列。稀疏嵌入表示(SRE)利用稀疏的嵌入表示保留信息稀疏性质和结构。

除此之外，统计方法和复杂网络的方法也有用在属性约简研究的。多数研究集中在对样本特征属性的简约，其主要目的是在保持数据分类能力不变的情况下，消除冗余的属性提取出重要特征属性。例如，2008年墨西哥学者Cervantes等人采用最小封闭球聚类，提出一种基于支持向量机的数据简约方法[4];山西大学的Qian等人在2010年提出一种基于模糊集的数据简约方法来对数据进行特征提取[5]。但基于统计的属性约简方法在应对大数据时效率难以得到保障。从数据的中观和微观层面来挖掘数据中有用信息进行属性约简也是一种途径。例如，2004年学者Clauset等人利用基于贪心算法的社区划分算法寻找局部最优值来确定网络中的社区[6],2008年亚利桑那州立大学的Tang等人提出了基于密度的方法和动态演化特性启发式规则[7]选择最合适的社区数目,但这类研究至今尚未有系统化的成果[8]。

随着大数据的普及，面对目前大数据存在的缺陷，例如无法完成异构数据的融合，全量数据计算困难，数据结构与映射机制不完善等问题提出了大数据的稀疏表示算法。

2 大数据的稀疏表示

2.1 稀疏表示

数据稀疏性是大数据的主要特征之一，用数据矩阵稀疏表示大数据以达到降维目的是大数据存储基本方法之一。数据的稀疏表示定义为用尽可能少的非0系数表示信号的主要信息，非主要信息则用0元素表示，从而简化数据处理的求解过程。稀疏域模型可如表达式：

其中y∈Rn为待处理的原始大数据，A∈Rn*m为基函数字典，x∈Rm为稀疏表示向量，‖x‖0∈m。‖x‖0∈m为x的稀疏度，表示x中非0稀疏的个数，在数据稀疏表示中如何求A∈Rn*m最优解是关键。

求解‖x‖0是一个NP-hard问题，若x是足够稀疏的，上述问题转化为求解x的1范数，即‖x‖1。

一般条件下，大数据都是有噪声存在的，因此数据进一步表示为y=Ax+e。那么：

上式是一个凸优化问题。di表示与第i类相关的系数，则误差优化为：

在春季的“大麦黄”和秋季的白露前一星期，使用1次杀纤毛虫的药物，隔日再用1次消毒药物，以预防寄生虫病的发生。

2.2 大数据的稀疏表示

文献[9]是稀疏表示提出者，虽然从理论上证明了图像数据的稀疏表示和重构可能性和部分在稀疏表示在图像分类和理解上的应用，但是稀疏表示不能直接应用于大数据，因为在基元字典的建立上将会产生大量的计算导致计算延迟。为了保证计算结果的时效性和数据信息的完备性，提出了以下的算法。

第二步：因为在T1和T2可能是结构化、非结构化和半结构化数据，那么可能会存在两者之间结构不相似，难以融合，采用多形态保留相似性算法对T1和T2进行数据融合记为UT1=T1∪T2。信息融合过程如下：

设x×y∈Rk，那么令表示x和y之间的相似程度，令

那么求解UT1最优解就等于

第三步：这样得到的UT1仍然是含有大量0的数据，也就是数据是稀疏的。设x'∈UT1，那么对x'做以下变换：

p(x'|Ui，Bi，εi)中假设观察数据矩阵V由目标矩阵经过一个低秩矩阵变换得到，也既V=UBT，U是目标矩阵，B是低秩矩阵。

第四步：对UT1进行变换处理使得数据更加方便处理和富有信息。融合之后用UT1建立数据的字典基元D1。

这样不断反复进行后得到不同的Di，然后利用这些Di加权形成需要的基函数字典。即：

其中n为采用的集合数目，随着n不断增大逐渐趋向于完备字典。ωi的确定过程为：当只有1个字典基元时,ωi=1；否则，当有m个字典时I(Di)为字典Di所携带的信息量。将式(12)代入到式(4)和式(5)即可求得相应的最优解。

3 实验结果与分析

我们选用了加利福尼亚大学机器学习UCI数据库中的Gisette和Internet Advertisements两个数据集。Gisette数据集中包括13500条记录，每条记录由5000个属性组成；Internet Advertisements数据集中3279记录，每条记录有1558个特征数据构成。

在Gisette数据集实验中，用5000维数据来描述一个手写体数字。我们采用Bootstrap产生的T1和T2都是500*200的矩阵，通过式(9)、式(10)和式(12)经过11次后形成D1，D2，…，D10等10个基元字典，在ωi的计算中I(Di)采用Di的熵作为信息量衡量标准后代入式(4)和式(5)求解。我们选择50%样本作为训练数据，剩下的50%作为测试数据，实验结果如表1所示。

表1 不同的方法在Gisette数据集上实验结果对照

在Internet Advertisements数据集实验中，在数据集中采用1558维特征描述网页图像的几何形状，其中28%的样本数据中含有缺省值，最后判断该图像是否为广告图像。我们采用Bootstrap产生的T1和T2都是300*300的矩阵，通过式(9)、式(10)和式(12)经过6次后形成D1，D2，…，D5等5个基元字典，在ωi的计算中I(Di)采用Di的PCA作为信息量衡量标准后代入式(4)和式(5)求解。我们在总数据中随机选择50%样本作为训练数据，再随机选择50%作为测试数据，实验结果如表2所示。

表2 Internet Advertisements数据集上实验结果对照

4 结束语

充分利用大数据是稀疏的特征，在大数据中采用样本和属性特征随机采样形成不同子集后用多形态保留相似性算法对数据进行融合，利用数据变换使得数据更加方便处理和富有信息表达，信息的数据形成基元字典，通过基元字典加权形成最终的可用字典。

在统计学习经典测试数据集Gisette和Internet Advertisements上进行实验对比，实验结果表明，建议的算法在数据集都具有最高的分类正确率，同时由于建议算法只需要简单计算，所以运算速度都较其他算法要快。对有缺省值的数据也取得较好的分类能力。

[1]〔英〕迈尔-舍恩伯格,库克耶著，盛杨燕.大数据时代[M].周涛译.杭州：浙江人民出版社，2013.

[2]孟小峰,慈祥.大数据管理:概念、技术与挑战[J].计算机研究与发展,2013,(1).

[3]Crawford K.Big Data Stalking[J].Scientific American,2014,310(4).

[4]Cervantes J,Li X,Yu W,et al.Support Vector Machine Classification for Large Data Sets Via Minimum Enclosing Ball Clustering[J].Neurocomputing,2008,71(4-6).

[5]Qian Y,Liang J,Pedrycz W,et al.Positive Approximation:An Accelerator for Attribute Reduction in Rough Set Theory[J].Artificial Intelligence,2010,174(9).

[6]Tang L,Liu H,et al.Community Evolution in Dynamic Multi-Mode Networks[C]//Proceeding of The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2008.

[7]何非,何克清.大数据及其科学问题与方法的探讨[J].武汉大学学报(理学版),2014,(1).

[8]Candes E J,Romberg J K,Tao T.Stable Signal Recovery From Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics,2006,59(8).

[9]Guyon I,Hur A,Gunn S.Result Analysis of The NIPS 2003 Feature Selection Challenge[C].Advances in Neural Information Processing Systems.2014.

[10]Nicholas Kushmerick.Learning to remove Internet Advertisements[M].ACM Press,2010.