張 乾，金升菊,羅玉坤

(1.貴州省模式識(shí)別與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，貴陽 550025；2.貴州民族大學(xué) 工程實(shí)訓(xùn)中心，貴陽 550025；3.貴州省統(tǒng)計(jì)科研教育中心，貴陽 550001)

0 引言

大數(shù)據(jù)(big data)是信息時(shí)代的產(chǎn)物，其指涉及的資料數(shù)量級(jí)上巨大到無法透過目前主流軟件工具在合理時(shí)間內(nèi)達(dá)到擷取、管理、處理、并整理，數(shù)據(jù)一般呈現(xiàn)結(jié)構(gòu)化、非結(jié)構(gòu)化和半結(jié)構(gòu)化。隨著大數(shù)據(jù)的到來，政府統(tǒng)計(jì)業(yè)務(wù)工作面臨新的挑戰(zhàn)，數(shù)據(jù)統(tǒng)計(jì)關(guān)鍵技術(shù)越顯重要。在大數(shù)據(jù)應(yīng)用技術(shù)越來越普及的背景下，對(duì)大數(shù)據(jù)的基礎(chǔ)理論研究對(duì)大數(shù)據(jù)應(yīng)用推廣有著十分重要的意義。

牛津大學(xué)教授維克托·邁爾·舍恩伯格在其新書《大數(shù)據(jù)時(shí)代》[1]中說，這是一場(chǎng)“革命”，將對(duì)各行各業(yè)帶來深刻影響，甚至改變我們的思維方式，但同時(shí)它也引發(fā)“數(shù)據(jù)暴政”的擔(dān)憂。2012年國(guó)際著名的咨詢機(jī)構(gòu)Gartner發(fā)布了大數(shù)據(jù)技術(shù)成熟度曲線，分析提出了當(dāng)前大數(shù)據(jù)面臨的技術(shù)挑戰(zhàn)和問題，主要包括對(duì)數(shù)據(jù)的屬性約簡(jiǎn)(降維)、計(jì)算—存儲(chǔ)—管理提升、數(shù)據(jù)復(fù)雜度理論、數(shù)據(jù)感知和數(shù)據(jù)安全等。

目前，大數(shù)據(jù)研究主要平臺(tái)是Hadoop和Map Reduce框架下進(jìn)行。大數(shù)據(jù)已經(jīng)初步應(yīng)用在醫(yī)療、金融、電子商務(wù)、零售、電信、交通等應(yīng)用領(lǐng)域和SAP、Oracle、IBM、EMC、微軟、浪潮等大廠家在大數(shù)據(jù)的發(fā)展定位和策略上。Spark由加州伯克利大學(xué)AMP實(shí)驗(yàn)室的Matei為主的小團(tuán)隊(duì)所開發(fā)，是一個(gè)基于內(nèi)存計(jì)算的開源集群計(jì)算系統(tǒng)，使得數(shù)據(jù)分析更加快速。Spark是一種與Hadoop相似的開源集群計(jì)算環(huán)境，但是兩者之間還存在一些不同之處，這些有用的不同之處使Spark在某些工作負(fù)載方面表現(xiàn)得更加優(yōu)越，換句話說，Spark啟用了內(nèi)存分布數(shù)據(jù)集，除了能夠提供交互式查詢外，它還可以優(yōu)化迭代工作負(fù)載。文獻(xiàn)[2]和文獻(xiàn)[3]對(duì)大數(shù)據(jù)目前研究現(xiàn)狀進(jìn)行綜述后認(rèn)為，大數(shù)據(jù)研究仍集中在管理模式創(chuàng)新和價(jià)值發(fā)現(xiàn)算法上，還有部分是大數(shù)據(jù)處理的調(diào)度算法研究。

本文主要探討大數(shù)據(jù)的稀疏表示算法,提出一種改進(jìn)的、有效的大數(shù)據(jù)稀疏表示算法，并做了大量數(shù)據(jù)實(shí)證分析。

1 研究現(xiàn)狀

對(duì)大數(shù)據(jù)理論研究主要包括對(duì)數(shù)據(jù)的屬性約簡(jiǎn)(降維)、計(jì)算—存儲(chǔ)—管理提升、數(shù)據(jù)復(fù)雜度理論、數(shù)據(jù)感知和數(shù)據(jù)安全等。對(duì)屬性約簡(jiǎn)(降維)研究主要有局部代替全局和優(yōu)化處理等研究途徑。

在大數(shù)據(jù)按需簡(jiǎn)約方面，經(jīng)典的有主成分分析（PCA)將多個(gè)變量通過線性變換以選出較少個(gè)數(shù)重要變量的一種多元統(tǒng)計(jì)分析方法，主要考慮增強(qiáng)方差。線性判別分析（LDA）是一種提高類間方差降低類內(nèi)方差的方法。等距映射（Isomap）主要目標(biāo)是對(duì)于給定的高維流形，欲找到其對(duì)應(yīng)的低維嵌入，使得高維流形上數(shù)據(jù)點(diǎn)間的近鄰結(jié)構(gòu)在低維嵌入中得以保持。局部線性嵌入（LLE）將高維數(shù)據(jù)中的某點(diǎn)用周邊的數(shù)據(jù)點(diǎn)的線性表示。Laplacian特征映射基本思想是用一個(gè)無向有權(quán)圖描述一個(gè)流形，然后通過用圖的嵌入來找低維表示，簡(jiǎn)單來說，就是在保持圖的局部鄰接關(guān)系的情況下，將其圖從高維空間中重新畫在一個(gè)低維空間中。局部保留投影（LPP）主要目的是保存高維數(shù)據(jù)在局部上的相似性。局部切空間排列（LTSA）主要是先考慮用每一點(diǎn)處的局部切空間表示該點(diǎn)處的幾何特征，然后用局部切空間進(jìn)行排列。稀疏嵌入表示(SRE)利用稀疏的嵌入表示保留信息稀疏性質(zhì)和結(jié)構(gòu)。

除此之外，統(tǒng)計(jì)方法和復(fù)雜網(wǎng)絡(luò)的方法也有用在屬性約簡(jiǎn)研究的。多數(shù)研究集中在對(duì)樣本特征屬性的簡(jiǎn)約，其主要目的是在保持?jǐn)?shù)據(jù)分類能力不變的情況下，消除冗余的屬性提取出重要特征屬性。例如，2008年墨西哥學(xué)者Cervantes等人采用最小封閉球聚類，提出一種基于支持向量機(jī)的數(shù)據(jù)簡(jiǎn)約方法[4];山西大學(xué)的Qian等人在2010年提出一種基于模糊集的數(shù)據(jù)簡(jiǎn)約方法來對(duì)數(shù)據(jù)進(jìn)行特征提取[5]。但基于統(tǒng)計(jì)的屬性約簡(jiǎn)方法在應(yīng)對(duì)大數(shù)據(jù)時(shí)效率難以得到保障。從數(shù)據(jù)的中觀和微觀層面來挖掘數(shù)據(jù)中有用信息進(jìn)行屬性約簡(jiǎn)也是一種途徑。例如，2004年學(xué)者Clauset等人利用基于貪心算法的社區(qū)劃分算法尋找局部最優(yōu)值來確定網(wǎng)絡(luò)中的社區(qū)[6],2008年亞利桑那州立大學(xué)的Tang等人提出了基于密度的方法和動(dòng)態(tài)演化特性啟發(fā)式規(guī)則[7]選擇最合適的社區(qū)數(shù)目,但這類研究至今尚未有系統(tǒng)化的成果[8]。

隨著大數(shù)據(jù)的普及，面對(duì)目前大數(shù)據(jù)存在的缺陷，例如無法完成異構(gòu)數(shù)據(jù)的融合，全量數(shù)據(jù)計(jì)算困難，數(shù)據(jù)結(jié)構(gòu)與映射機(jī)制不完善等問題提出了大數(shù)據(jù)的稀疏表示算法。

2 大數(shù)據(jù)的稀疏表示

2.1 稀疏表示

數(shù)據(jù)稀疏性是大數(shù)據(jù)的主要特征之一，用數(shù)據(jù)矩陣稀疏表示大數(shù)據(jù)以達(dá)到降維目的是大數(shù)據(jù)存儲(chǔ)基本方法之一。數(shù)據(jù)的稀疏表示定義為用盡可能少的非0系數(shù)表示信號(hào)的主要信息，非主要信息則用0元素表示，從而簡(jiǎn)化數(shù)據(jù)處理的求解過程。稀疏域模型可如表達(dá)式：

其中y∈Rn為待處理的原始大數(shù)據(jù)，A∈Rn*m為基函數(shù)字典，x∈Rm為稀疏表示向量，‖x‖0∈m?！瑇‖0∈m為x的稀疏度，表示x中非0稀疏的個(gè)數(shù)，在數(shù)據(jù)稀疏表示中如何求A∈Rn*m最優(yōu)解是關(guān)鍵。

求解‖x‖0是一個(gè)NP-hard問題，若x是足夠稀疏的，上述問題轉(zhuǎn)化為求解x的1范數(shù)，即‖x‖1。

一般條件下，大數(shù)據(jù)都是有噪聲存在的，因此數(shù)據(jù)進(jìn)一步表示為y=Ax+e。那么：

上式是一個(gè)凸優(yōu)化問題。di表示與第i類相關(guān)的系數(shù)，則誤差優(yōu)化為：

在春季的“大麥黃”和秋季的白露前一星期，使用1次殺纖毛蟲的藥物，隔日再用1次消毒藥物，以預(yù)防寄生蟲病的發(fā)生。

2.2 大數(shù)據(jù)的稀疏表示

文獻(xiàn)[9]是稀疏表示提出者，雖然從理論上證明了圖像數(shù)據(jù)的稀疏表示和重構(gòu)可能性和部分在稀疏表示在圖像分類和理解上的應(yīng)用，但是稀疏表示不能直接應(yīng)用于大數(shù)據(jù)，因?yàn)樵诨值涞慕⑸蠈?huì)產(chǎn)生大量的計(jì)算導(dǎo)致計(jì)算延遲。為了保證計(jì)算結(jié)果的時(shí)效性和數(shù)據(jù)信息的完備性，提出了以下的算法。

第二步：因?yàn)樵赥1和T2可能是結(jié)構(gòu)化、非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)，那么可能會(huì)存在兩者之間結(jié)構(gòu)不相似，難以融合，采用多形態(tài)保留相似性算法對(duì)T1和T2進(jìn)行數(shù)據(jù)融合記為UT1=T1∪T2。信息融合過程如下：

設(shè)x×y∈Rk，那么令表示x和y之間的相似程度，令

那么求解UT1最優(yōu)解就等于

第三步：這樣得到的UT1仍然是含有大量0的數(shù)據(jù)，也就是數(shù)據(jù)是稀疏的。設(shè)x'∈UT1，那么對(duì)x'做以下變換：

p(x'|Ui，Bi，εi)中假設(shè)觀察數(shù)據(jù)矩陣V由目標(biāo)矩陣經(jīng)過一個(gè)低秩矩陣變換得到，也既V=UBT，U是目標(biāo)矩陣，B是低秩矩陣。

第四步：對(duì)UT1進(jìn)行變換處理使得數(shù)據(jù)更加方便處理和富有信息。融合之后用UT1建立數(shù)據(jù)的字典基元D1。

這樣不斷反復(fù)進(jìn)行后得到不同的Di，然后利用這些Di加權(quán)形成需要的基函數(shù)字典。即：

其中n為采用的集合數(shù)目，隨著n不斷增大逐漸趨向于完備字典。ωi的確定過程為：當(dāng)只有1個(gè)字典基元時(shí),ωi=1；否則，當(dāng)有m個(gè)字典時(shí)I(Di)為字典Di所攜帶的信息量。將式(12)代入到式(4)和式(5)即可求得相應(yīng)的最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果與分析

我們選用了加利福尼亞大學(xué)機(jī)器學(xué)習(xí)UCI數(shù)據(jù)庫(kù)中的Gisette和Internet Advertisements兩個(gè)數(shù)據(jù)集。Gisette數(shù)據(jù)集中包括13500條記錄，每條記錄由5000個(gè)屬性組成；Internet Advertisements數(shù)據(jù)集中3279記錄，每條記錄有1558個(gè)特征數(shù)據(jù)構(gòu)成。

在Gisette數(shù)據(jù)集實(shí)驗(yàn)中，用5000維數(shù)據(jù)來描述一個(gè)手寫體數(shù)字。我們采用Bootstrap產(chǎn)生的T1和T2都是500*200的矩陣，通過式(9)、式(10)和式(12)經(jīng)過11次后形成D1，D2，…，D10等10個(gè)基元字典，在ωi的計(jì)算中I(Di)采用Di的熵作為信息量衡量標(biāo)準(zhǔn)后代入式(4)和式(5)求解。我們選擇50%樣本作為訓(xùn)練數(shù)據(jù)，剩下的50%作為測(cè)試數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同的方法在Gisette數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果對(duì)照

在Internet Advertisements數(shù)據(jù)集實(shí)驗(yàn)中，在數(shù)據(jù)集中采用1558維特征描述網(wǎng)頁圖像的幾何形狀，其中28%的樣本數(shù)據(jù)中含有缺省值，最后判斷該圖像是否為廣告圖像。我們采用Bootstrap產(chǎn)生的T1和T2都是300*300的矩陣，通過式(9)、式(10)和式(12)經(jīng)過6次后形成D1，D2，…，D5等5個(gè)基元字典，在ωi的計(jì)算中I(Di)采用Di的PCA作為信息量衡量標(biāo)準(zhǔn)后代入式(4)和式(5)求解。我們?cè)诳倲?shù)據(jù)中隨機(jī)選擇50%樣本作為訓(xùn)練數(shù)據(jù)，再隨機(jī)選擇50%作為測(cè)試數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 Internet Advertisements數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果對(duì)照

4 結(jié)束語

充分利用大數(shù)據(jù)是稀疏的特征，在大數(shù)據(jù)中采用樣本和屬性特征隨機(jī)采樣形成不同子集后用多形態(tài)保留相似性算法對(duì)數(shù)據(jù)進(jìn)行融合，利用數(shù)據(jù)變換使得數(shù)據(jù)更加方便處理和富有信息表達(dá)，信息的數(shù)據(jù)形成基元字典，通過基元字典加權(quán)形成最終的可用字典。

在統(tǒng)計(jì)學(xué)習(xí)經(jīng)典測(cè)試數(shù)據(jù)集Gisette和Internet Advertisements上進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果表明，建議的算法在數(shù)據(jù)集都具有最高的分類正確率，同時(shí)由于建議算法只需要簡(jiǎn)單計(jì)算，所以運(yùn)算速度都較其他算法要快。對(duì)有缺省值的數(shù)據(jù)也取得較好的分類能力。

[1]〔英〕邁爾-舍恩伯格,庫(kù)克耶著，盛楊燕.大數(shù)據(jù)時(shí)代[M].周濤譯.杭州：浙江人民出版社，2013.

[2]孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J].計(jì)算機(jī)研究與發(fā)展,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]何非,何克清.大數(shù)據(jù)及其科學(xué)問題與方法的探討[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),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.