面向物聯(lián)網(wǎng)的分布式均分Lasso算法

，，

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

物聯(lián)網(wǎng)(Cyber-physical system)即物與物相連的互聯(lián)網(wǎng).目前，物聯(lián)網(wǎng)一般定義：通過無(wú)線電頻率識(shí)別(RFID)、紅外傳感器、全球衛(wèi)星定位系統(tǒng)和激光掃描器等信息傳感設(shè)備，依照一個(gè)統(tǒng)一協(xié)定的協(xié)議，把物品通過網(wǎng)絡(luò)相互連接起來(lái)，達(dá)成物與物之間的信息交換，以實(shí)現(xiàn)對(duì)物聯(lián)網(wǎng)中終端的智能化監(jiān)控與管理的一種網(wǎng)絡(luò)[1-4].近些年來(lái)，物聯(lián)網(wǎng)技術(shù)逐漸地從理論研究開始延伸到現(xiàn)實(shí)生活中，越來(lái)越多的物聯(lián)網(wǎng)公司與應(yīng)用出現(xiàn)在人們面前，物聯(lián)網(wǎng)技術(shù)與產(chǎn)品現(xiàn)在均處于一種快速生長(zhǎng)的狀態(tài).這樣的發(fā)展?fàn)顟B(tài)自然而然也帶來(lái)了很多挑戰(zhàn)，隨著物聯(lián)網(wǎng)的規(guī)模越來(lái)越大，物聯(lián)網(wǎng)產(chǎn)生的數(shù)據(jù)也呈指數(shù)級(jí)增長(zhǎng)，這些數(shù)據(jù)有著海量性、并發(fā)性和高維度性的特征.這些特征使得針對(duì)物聯(lián)網(wǎng)數(shù)據(jù)的數(shù)據(jù)挖掘面臨著許多困難，是當(dāng)前必須解決的關(guān)鍵問題之一.

Tibshirani于1996年提出的Lasso算法作為一種具有穩(wěn)定、快速和精準(zhǔn)等特性的特征選擇算法，可以在數(shù)據(jù)集進(jìn)行分類之前通過對(duì)數(shù)據(jù)集使用Lasso算法，選擇出強(qiáng)相關(guān)特征集來(lái)達(dá)到降低數(shù)據(jù)挖掘算法負(fù)擔(dān)的效果[5- 6].Zou等[7]提出的彈性網(wǎng)絡(luò)算法作為L(zhǎng)asso的一個(gè)改進(jìn)算法，提高了算法的總體預(yù)測(cè)精度.Yuan等[8]提出了一種組Lasso算法，這一算法經(jīng)過JACOB[9]和PUIG[10]的進(jìn)一步改進(jìn)，使得Lasso算法可以將某些需要同時(shí)加入強(qiáng)特征組的特征可以以一個(gè)組的形式進(jìn)行特征選擇.為了解決Lasso算法在海量高維度數(shù)據(jù)集上計(jì)算開銷過大以及在高維度小樣本集上的過擬合問題，施萬(wàn)鋒等[11]提出了一種均分式的Lasso算法.筆者基于均分式Lasso算法，通過結(jié)合分布式計(jì)算平臺(tái)，提出了一種分布式均分Lasso算法，在進(jìn)一步提升Lasso算法計(jì)算效率的同時(shí)，通過并行化子集的特征選擇過程，解決了均分式Lasso算法多次使用Lasso算法導(dǎo)致的計(jì)算消耗增加的問題.

1 背景介紹

1.1 物聯(lián)網(wǎng)

Haller等[12]對(duì)物聯(lián)網(wǎng)的概念提出了如下定義：“它是這樣的一個(gè)世界，物理對(duì)象可以無(wú)縫集成到信息網(wǎng)絡(luò)，并且可以成為業(yè)務(wù)流程的積極參與者.服務(wù)可以在網(wǎng)絡(luò)中影響到這些‘智能對(duì)象’，找到他們的國(guó)家以及與他們相關(guān)聯(lián)的任何問題，并能考慮到安全和隱私問題.”

從通訊的對(duì)象與過程來(lái)看，物與物以及人與物之間的信息交互是物聯(lián)網(wǎng)的核心[13].基于這一核心，物聯(lián)網(wǎng)有著3 個(gè)主要特征：1) 全面感知，主要表現(xiàn)在通過一些現(xiàn)有的電子與傳感技術(shù)，隨時(shí)對(duì)物聯(lián)網(wǎng)中的物體(節(jié)點(diǎn))進(jìn)行信息采集與獲取.2) 可靠傳送，主要表現(xiàn)在通過將物聯(lián)網(wǎng)中的物體接入信息網(wǎng)絡(luò)，利用有線或是無(wú)線網(wǎng)絡(luò)(如傳感器網(wǎng)絡(luò)、移動(dòng)通信網(wǎng)和互聯(lián)網(wǎng)等)，將獲取到的關(guān)于物品的信息隨時(shí)隨地傳輸出去.3) 智能處理，主要表現(xiàn)在利用各種智能計(jì)算技術(shù)(如云計(jì)算、模糊識(shí)別和模式識(shí)別等)，將收集到的海量、異構(gòu)性傳感器數(shù)據(jù)與信息進(jìn)行分析并處理，實(shí)現(xiàn)智能化地管理與控制.

1.2 Lasso算法基本概念

在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)中，Lasso算法(Least absolute shrinkage and selection operator，即稱為最小絕對(duì)值收斂和選擇算子或者又稱為套索算法)是一種同時(shí)進(jìn)行特征選擇和正則化的特征選擇方法，旨在增強(qiáng)統(tǒng)計(jì)模型的預(yù)測(cè)準(zhǔn)確性和可解釋性，最初由斯坦福大學(xué)統(tǒng)計(jì)學(xué)教授Robert Tibshirani于1996年基于Leo Breiman的研究提出[14-17].

Lasso最初是為最小二乘模型制定的，揭示了估計(jì)量行為的大量數(shù)據(jù)，包括其與嶺回歸和最佳子集選擇的關(guān)系以及Lasso系數(shù)估計(jì)與所謂的軟閾值之間的聯(lián)系.同時(shí)，如標(biāo)準(zhǔn)線性回歸一樣，算法如果協(xié)變量是共線的，則系數(shù)估計(jì)不必是唯一的.

雖然最初目的比較單一，Lasso正則化可以簡(jiǎn)單地?cái)U(kuò)展到廣泛的統(tǒng)計(jì)模型中去，包括廣義線性模型，廣義估計(jì)方程，比例風(fēng)險(xiǎn)模型和M估計(jì)[18-19].Lasso執(zhí)行子集選擇的能力取決于約束的形式，并具有多種解釋，包括幾何、貝葉斯統(tǒng)計(jì)和凸分析.

(1)

(2)

式(2)可重寫成為

(3)

式中λ與t之間的關(guān)系取決于具體數(shù)據(jù)庫(kù).

接下來(lái)，筆者嘗試分析一些Lasso估計(jì)器的基本屬性.

首先假設(shè)協(xié)變量是正交的，因此(xi|xj)=δij，其中：(·|·)為內(nèi)積空間；δij為克羅內(nèi)克函數(shù).然后，使用次級(jí)方法，可得

(4)

到目前為止，為了彌補(bǔ)原始算法的某些限制，并使該方法對(duì)于特定問題更有用，有很多種變種算法被提出.幾乎所有算法都側(cè)重于在協(xié)變量中尊重或利用不同類型的依賴關(guān)系.

1.3 LARS算法

統(tǒng)計(jì)學(xué)中，最小角度回歸算法(LARS)是由Bradley Efron等開發(fā)的用于擬合高維數(shù)據(jù)的線性回歸模型的算法[20].

LARS解決方案由表示參數(shù)向量的一范式的每個(gè)值的解的曲線組成而不是直接給出向量結(jié)果.該算法類似于前向逐步回歸，而不是在每個(gè)步驟中包含變量，估計(jì)參數(shù)在等于每個(gè)與殘差相關(guān)的方向上增加.

這一算法的基本步驟如下：

1) 將所有系數(shù)βj設(shè)為0.

2) 找出與y最相關(guān)的預(yù)測(cè)因子xj.

4) 在βj，βk的聯(lián)合最小二乘方向上增加，直到一個(gè)新的預(yù)測(cè)因子xk與殘差r有更大的相關(guān)性.

5) 重復(fù)2)～4)直到所有的預(yù)測(cè)變量都在模型中[21].

1.4 均分式Lasso算法

LARS算法在一般數(shù)據(jù)集上的表現(xiàn)十分優(yōu)秀，其具有特征選擇過程高效，選擇結(jié)果穩(wěn)定的特點(diǎn).然而，隨著數(shù)據(jù)集數(shù)據(jù)量和特征量的增加，LARS算法的一些問題也逐漸顯露出來(lái).這一算法在面對(duì)高維度海量數(shù)據(jù)集時(shí)，往往有著計(jì)算開銷過大的問題；而面對(duì)高維度小樣本數(shù)據(jù)集時(shí)，又會(huì)產(chǎn)生過擬合的問題.

為了解決這一問題，施萬(wàn)鋒等[11]提出了一種均分式的Lasso算法.在普通Lasso算法中，特征選擇的時(shí)間復(fù)雜度與維度的二次方和樣本數(shù)成正比，高維度海量數(shù)據(jù)集就意味著高計(jì)算消耗.因此，均分式Lasso算法采用將數(shù)據(jù)集的特征集分割為K份，從而使得計(jì)算開銷降低K的二次方.同樣，在面對(duì)高維度小數(shù)據(jù)集時(shí)，將樣本分為K份能夠降低樣本數(shù)與維度數(shù)的比例，從而有效地緩解過擬合問題.

這一算法的偽代碼如下：

INPUT：預(yù)測(cè)數(shù)據(jù)集S，特征集X，樣本集Y，分片數(shù)K

OUTPUT：強(qiáng)相關(guān)特征集X″

BEGIN

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

FORi=1 toK

X′[i]=Lars(SX[i])；//X[i]為X的第i個(gè)分片，SX[i]為有這一分片的特征的數(shù)據(jù)自己

X′=X∪X′[i]；//將各個(gè)特征集合并為一個(gè)特征集

ENDFOR

X″=Lars(SX′)；//最后對(duì)特征集進(jìn)行一次LARS選擇

END

2 分布式均分Lasso算法

2.1 分布式Lasso算法

與均分式Lasso算法不同，分布式Lasso算法和LARS算法在本質(zhì)上并沒有不同之處，它是一個(gè)LARS算法的基于Hadoop云計(jì)算平臺(tái)的分布式實(shí)現(xiàn).這一算法的主要目的是在于將算法中的矩陣運(yùn)算等過程并行化以達(dá)到提升算法執(zhí)行效率的目的.

2.2 算法提出

針對(duì)均分式Lasso算法在對(duì)分片進(jìn)行特征提取時(shí)，不能有效地利用物聯(lián)網(wǎng)集群特性的問題，提出了一種分布式的均分Lasso算法.這一算法在分布式Lasso算法與均分式Lasso算法的基礎(chǔ)上，將均分式Lasso算法中耗時(shí)顯著的分片特征選擇過程進(jìn)行了并行化處理.

2.3 算法設(shè)計(jì)

1.4節(jié)與2.1節(jié)中的兩種算法分別從數(shù)據(jù)集以及計(jì)算過程兩個(gè)方面對(duì)LARS算法進(jìn)行了運(yùn)算效率上的改進(jìn).同時(shí)，考慮到物聯(lián)網(wǎng)環(huán)境下數(shù)據(jù)本身的分布特性，本節(jié)中提出一種融合了上述2 種算法的新算法.

對(duì)于這一算法，除了將數(shù)據(jù)集均分后進(jìn)行LARS算法時(shí)使用分布式計(jì)算，由于每個(gè)分塊在首輪計(jì)算中的不相關(guān)性，還可以根據(jù)均分?jǐn)?shù)K，將子數(shù)據(jù)集分配到不同節(jié)點(diǎn)上并行計(jì)算.

算法的偽代碼如下：

INPUT：預(yù)測(cè)數(shù)據(jù)集X，樣本集Y，分片數(shù)K

OUTPUT：強(qiáng)相關(guān)特征集X1

BEGIN

根據(jù)K與當(dāng)前集群中節(jié)點(diǎn)數(shù)量，將集群分割為M個(gè)子群，并建立其任務(wù)隊(duì)列QM；

初始化合并數(shù)據(jù)集X′；

FORi=1 toK

根據(jù)i與K取出數(shù)據(jù)集X中對(duì)應(yīng)的子集XKi；

創(chuàng)建對(duì)XKi的分布式Lasso算法計(jì)算任務(wù)TKi；

遍歷所有任務(wù)隊(duì)列，找出其中最短的隊(duì)列QMj，將TKi加入QMj中；

TKi完成后將結(jié)果Ai合并至X′中；

ENDFOR

對(duì)X′進(jìn)行分布式Lasso算法運(yùn)算，獲得最終結(jié)果X1；

END

2.4 算法復(fù)雜度分析

假設(shè)應(yīng)用分布式均分Lasso算法的數(shù)據(jù)集的特征集為Y，設(shè)特征數(shù)N=sizeof(Y).分片數(shù)為K，分片經(jīng)過特征選擇后的特征數(shù)為N′.傳統(tǒng)的Lasso算法的時(shí)間復(fù)雜度可以表示為O(N3+N2n),則均分式Lasso算法的時(shí)間復(fù)雜度可表示為

而分布式均分Lasso算法的時(shí)間復(fù)雜度則可表示為

當(dāng)N

同理，當(dāng)N≥n時(shí)，算法的時(shí)間復(fù)雜度可簡(jiǎn)化為

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了探索Lasso算法在物聯(lián)網(wǎng)數(shù)據(jù)挖掘上應(yīng)用的可行性，本節(jié)設(shè)計(jì)并實(shí)現(xiàn)一個(gè)對(duì)比不同Lasso算法(傳統(tǒng)Lasso算法，均分式Lasso算法以及分布式均分Lasso算法)性能的實(shí)驗(yàn).

為了保證實(shí)驗(yàn)的準(zhǔn)確性，3 種Lasso算法均使用由Bradle提出的LARS改進(jìn)型算法.傳統(tǒng)LARS算法以及均分式Lasso算法運(yùn)行于一臺(tái)四核、4 G內(nèi)存的虛擬機(jī)上，分布式Lasso算法運(yùn)行于一個(gè)由4 臺(tái)虛擬機(jī)組成的Hadoop集群上.每個(gè)算法具體的運(yùn)行平臺(tái)如表1所示.

表1 對(duì)比實(shí)驗(yàn)運(yùn)行平臺(tái)設(shè)置Table 1 Configuration of the platform for experiment

相較于LARS算法和均分式Lasso算法，分布式Lasso算法使用了4 臺(tái)單核、1 G內(nèi)存的虛擬機(jī)，使其總計(jì)算能力和前兩者采用的虛擬機(jī)基本持平，以此來(lái)保證實(shí)驗(yàn)結(jié)果的公平性與準(zhǔn)確性.

實(shí)驗(yàn)中采用9 個(gè)數(shù)據(jù)集，分別使用上述3 個(gè)算法.對(duì)于每個(gè)算法-數(shù)據(jù)集組合進(jìn)行20 次實(shí)驗(yàn)，并求平均值以獲得最終結(jié)果.

3.2 實(shí)驗(yàn)數(shù)據(jù)

為了測(cè)試分布式均分Lasso算法的有效性，從UCI數(shù)據(jù)倉(cāng)庫(kù)[22]中選取了9 個(gè)數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn).其中，前5 個(gè)為低維度的數(shù)據(jù)集，后4 個(gè)為高維度的數(shù)據(jù)集.數(shù)據(jù)集詳情如表2所示.

表2 實(shí)驗(yàn)使用數(shù)據(jù)集Table 2 Datasets used for the experiments

3.3 小數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)對(duì)比

本節(jié)中，分布式均分Lasso算法與均分式Lasso算法的分片數(shù)采用了K取3,5,7這3 種情況.3 個(gè)算法在5 個(gè)數(shù)據(jù)集下的表現(xiàn)如表3，4所示，其中Iris，Breast數(shù)據(jù)集由于特征數(shù)較少，缺少部分?jǐn)?shù)據(jù).

通過表3可以看出：均分式Lasso算法和分布式均分Lasso與傳統(tǒng)Lasso方法相比，精度基本上一致.少數(shù)數(shù)據(jù)集上精確度降低的原因在于，對(duì)特征集進(jìn)行拆分后，某些與類標(biāo)簽強(qiáng)相關(guān)的特征可能在特征子集中無(wú)法顯出這一特性，導(dǎo)致在對(duì)特征子集進(jìn)行特征選擇時(shí)，這些特征發(fā)生丟失，進(jìn)而影響了總體分類算法的精確度.當(dāng)然，由于Lasso算法本身的穩(wěn)定性以及數(shù)據(jù)特征集分布的隨機(jī)性，這類情況出現(xiàn)時(shí)對(duì)分類算法的精度影響并不明顯.因而，可以認(rèn)為，均分式Lasso算法與分布式Lasso算法在小數(shù)據(jù)集上均能夠保證足夠的精度.

從表4中可以看出：和傳統(tǒng)Lasso算法相比，均分式與分布式均分Lasso算法在小數(shù)據(jù)集上的運(yùn)算效率均顯得較低.這是由于在小數(shù)據(jù)集上，特征集拆分導(dǎo)致的Lasso算法計(jì)算量下降程度要小于引入更多次Lasso算法帶來(lái)的額外計(jì)算量.分布式均分Lasso算法相較于均分式Lasso算法，其計(jì)算效率有著顯著的提升.在小數(shù)據(jù)集上，這一提升主要體現(xiàn)在子特征集的并行化計(jì)算上.

表3 不同算法在在小數(shù)據(jù)集上的精度性能Table 3 Accuracy performance of different algorithms over small dataset

表4 不同算法在在小數(shù)據(jù)集上的時(shí)間性能Table 4 Time performance of different algorithms over small dataset

3.4 大數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)對(duì)比

上節(jié)實(shí)驗(yàn)已證明分布式均分Lasso方法在低維度數(shù)據(jù)集上的可行性.接下來(lái)，本節(jié)將分別選擇低維海量數(shù)據(jù)集Poker，高維海量數(shù)據(jù)集Gisette，高維小樣本數(shù)據(jù)集Dorothea和Arcene，從不同方面驗(yàn)證改進(jìn)Lasso方法的有效性.實(shí)驗(yàn)結(jié)果如表5，6所示.

對(duì)于低維海量數(shù)據(jù)集Poker，3 種算法都遇到了計(jì)算量過大的問題(運(yùn)行時(shí)間超過4 h).這是由于對(duì)于低維度數(shù)據(jù)集Poker來(lái)說，計(jì)算量主要由其海量數(shù)據(jù)引起.Lasso算法對(duì)于其已經(jīng)很小的特征集進(jìn)行劃分與否無(wú)法很明顯地影響到計(jì)算量.這一實(shí)驗(yàn)結(jié)果與2.4中的理論分析保持一致.

對(duì)于高維度小樣本集Dorothea來(lái)說，隨著分片數(shù)的提升，3 種算法的分類精度基本保持一致，這一結(jié)論與3.3中算法在小數(shù)據(jù)集上的結(jié)論保持一致.同時(shí)，從表6中可以看出：隨著分片數(shù)的上升，均分式Lasso算法的計(jì)算效率逐漸提升.然而，從K=20到K=40的計(jì)算效率提升明顯高于從K=40到K=60的提升.再對(duì)比分布式均分Lasso算法的結(jié)果，可以明顯看出：從K=40到K=60時(shí)，均分式Lasso算法的計(jì)算效率提升是由于對(duì)特征子集的Lasso算法計(jì)算效率提高導(dǎo)致.而通過檢查第一輪特征選擇后獲得的強(qiáng)特征集的特征數(shù)(K=40時(shí)為279，K=60時(shí)為499)，可以發(fā)現(xiàn)：相較于K=40，K=60的分片對(duì)于Dorothea這個(gè)特征集來(lái)說過于細(xì)致.從另一個(gè)高維度小樣本集Arcene的實(shí)驗(yàn)結(jié)果中可以觀察到類似現(xiàn)象(在這一組實(shí)驗(yàn)中，最優(yōu)分片數(shù)顯然是在K=20附近).

除去分片數(shù)有最優(yōu)解的現(xiàn)象外，還能從兩個(gè)小樣本集中發(fā)現(xiàn)：均分式與分布式均分Lasso算法可以解決傳統(tǒng)Lasso算法在面對(duì)高維度小樣本集時(shí)遇到的過擬合問題.同時(shí)，通過2 個(gè)數(shù)據(jù)集的對(duì)比，這一特性隨著特征數(shù)的增加與樣本數(shù)的減小而越發(fā)顯著.

同時(shí)，隨著分片數(shù)K的增長(zhǎng)，Arcene數(shù)據(jù)集實(shí)驗(yàn)的計(jì)算效率顯著降低，產(chǎn)生這一結(jié)果的原因類似于Dorothea數(shù)據(jù)集，即隨著K的增長(zhǎng)，對(duì)特征子集的特征選擇并不能很好地排除弱相關(guān)特征，使得最終獲得的強(qiáng)特征集過大，影響了計(jì)算效率.

對(duì)于一個(gè)樣本數(shù)和特征數(shù)均較多的數(shù)據(jù)集，以Gisette為例，單純拆分特征集雖然不會(huì)影響到分類精度，卻不能非常有效地降低計(jì)算效率.這是由于對(duì)于被均分的特征子集，每一個(gè)都是低維度海量數(shù)據(jù)集.

表5 不同算法在在大數(shù)據(jù)集上的精度性能Table 5 Accuracy performance of different algorithms over large dataset

表6 不同算法在在大數(shù)據(jù)集上的精度性能Table 6 Accuracy performance of different algorithms over large dataset

4 結(jié) 論

設(shè)計(jì)實(shí)現(xiàn)了一種分布式均分Lasso特征選擇算法，這一算法融合了了分布式計(jì)算與均分式Lasso算法，通過分布式并行化運(yùn)算，消除了均分式Lasso算法需要進(jìn)行多次迭代運(yùn)算導(dǎo)致計(jì)算效率下降的問題.從實(shí)驗(yàn)結(jié)果可以看出：分布式均分Lasso算法在均分式Lasso算法的基礎(chǔ)上進(jìn)一步提升了計(jì)算效率，同時(shí)保持了分類算法精度，并且分布式均分Lasso算法的K取值有著最佳值.但是，分布式均分Lasso算法對(duì)于百萬(wàn)級(jí)別的低維海量數(shù)據(jù)集(如Poker)依然顯得無(wú)力，無(wú)法提升計(jì)算效率.未來(lái)工作可以圍繞著以下方向進(jìn)行：1) 研究對(duì)于一個(gè)給定的高維數(shù)據(jù)集，如何通過計(jì)算或公式獲得最佳的分片數(shù)K，使得分布式均分Lasso算法可以在這個(gè)分片數(shù)下獲得最高的計(jì)算效率.2) 研究如何降低Lasso算法在海量數(shù)據(jù)集上的計(jì)算消耗；嘗試通過對(duì)數(shù)據(jù)集的樣本集進(jìn)行拆分后分別進(jìn)行Lasso算法的做法來(lái)達(dá)到這一目的；并研究這一方法對(duì)于分類精度的影響.3) 研究如何將筆者提出的算法應(yīng)用到物聯(lián)網(wǎng)中間層節(jié)點(diǎn)，利用物聯(lián)網(wǎng)本身的分布性特征，在物聯(lián)網(wǎng)數(shù)據(jù)被收集前提前進(jìn)行特征選擇運(yùn)算，達(dá)到降低計(jì)算消耗和網(wǎng)絡(luò)通訊量的目的.