張 乾，金升菊,羅玉坤

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

0 引言

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

2.1 稀疏表示

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

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

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

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

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

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

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

文獻[9]是稀疏表示提出者，雖然從理論上證明了圖像數(shù)據(jù)的稀疏表示和重構(gòu)可能性和部分在稀疏表示在圖像分類和理解上的應(yīng)用，但是稀疏表示不能直接應(yīng)用于大數(shù)據(jù)，因為在基元字典的建立上將會產(chǎn)生大量的計算導(dǎo)致計算延遲。為了保證計算結(jié)果的時效性和數(shù)據(jù)信息的完備性，提出了以下的算法。

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

在Internet Advertisements數(shù)據(jù)集實驗中，在數(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個基元字典，在ωi的計算中I(Di)采用Di的PCA作為信息量衡量標(biāo)準(zhǔn)后代入式(4)和式(5)求解。我們在總數(shù)據(jù)中隨機選擇50%樣本作為訓(xùn)練數(shù)據(jù)，再隨機選擇50%作為測試數(shù)據(jù)，實驗結(jié)果如表2所示。

表2 Internet Advertisements數(shù)據(jù)集上實驗結(jié)果對照

4 結(jié)束語

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

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

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

[2]孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[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é)報(理學(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.