，，

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

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

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

1 背景介紹

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

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

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

1.2 Lasso算法基本概念

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

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

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

(1)

(2)

式(2)可重寫成為

(3)

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

接下來，筆者嘗試分析一些Lasso估計器的基本屬性.

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

(4)

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

1.3 LARS算法

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

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

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

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

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

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

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

1.4 均分式Lasso算法

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

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

這一算法的偽代碼如下：

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

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

BEGIN

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

FORi=1 toK

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

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

ENDFOR

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

END

2 分布式均分Lasso算法

2.1 分布式Lasso算法

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

2.2 算法提出

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

2.3 算法設(shè)計

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

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

算法的偽代碼如下：

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

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

BEGIN

根據(jù)K與當前集群中節(jié)點數(shù)量，將集群分割為M個子群，并建立其任務(wù)隊列QM；

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

FORi=1 toK

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

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

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

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

ENDFOR

對X′進行分布式Lasso算法運算，獲得最終結(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算法的時間復(fù)雜度可以表示為O(N3+N2n),則均分式Lasso算法的時間復(fù)雜度可表示為

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

當N

同理，當N≥n時，算法的時間復(fù)雜度可簡化為

3 實驗與分析

3.1 實驗設(shè)計

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

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

表1 對比實驗運行平臺設(shè)置Table 1 Configuration of the platform for experiment

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

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

3.2 實驗數(shù)據(jù)

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

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

3.3 小數(shù)據(jù)集上的實驗數(shù)據(jù)對比

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

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

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

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

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

3.4 大數(shù)據(jù)集上的實驗數(shù)據(jù)對比

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

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

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

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

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

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