及歆榮侯翠琴侯義斌*

①(北京工業(yè)大學(xué)嵌入式軟件與系統(tǒng)研究所 北京 100124)

②(河北工程大學(xué)信息與電氣工程學(xué)院 邯鄲 056038)

無線傳感器網(wǎng)絡(luò)下線性支持向量機(jī)分布式協(xié)同訓(xùn)練方法研究

及歆榮①②侯翠琴①侯義斌*①

①(北京工業(yè)大學(xué)嵌入式軟件與系統(tǒng)研究所 北京 100124)

②(河北工程大學(xué)信息與電氣工程學(xué)院 邯鄲 056038)

針對無線傳感器網(wǎng)絡(luò)中分散在各節(jié)點(diǎn)上的訓(xùn)練數(shù)據(jù)傳輸?shù)綌?shù)據(jù)融合中心集中訓(xùn)練支持向量機(jī)(Support Vector Machine, SVM)時存在的高通信代價和高能量消耗問題，該文研究了僅依靠相鄰節(jié)點(diǎn)間的相互協(xié)作，在網(wǎng)內(nèi)分布式協(xié)同訓(xùn)練線性SVM的方法。首先，在各節(jié)點(diǎn)分類器決策變量與集中式分類器決策變量相一致的約束下，對集中式SVM訓(xùn)練問題進(jìn)行等價分解，然后利用增廣拉格朗日乘子法，對分解后的SVM問題進(jìn)行求解和推導(dǎo)，進(jìn)而提出基于全局平均一致性的線性SVM分布式訓(xùn)練算法(Average Consensus based Distributed Supported Vector Machine, AC-DSVM)；為了降低AC-DSVM算法中全局平均一致性的通信開銷，利用相鄰節(jié)點(diǎn)間的局部平均一致性近似全局平均一致性，提出基于一次全局平均一致性的線性SVM分布式訓(xùn)練算法(Once Average Consensus based Distributed Supported Vector Machine, 1-AC-DSVM)。仿真實(shí)驗(yàn)結(jié)果表明，與已有算法相比，AC-DSVM算法的迭代次數(shù)和數(shù)據(jù)傳輸量略高，但其能夠完全收斂到集中式訓(xùn)練結(jié)果；1-AC-DSVM算法具有較好的收斂性，而且在收斂速度和數(shù)據(jù)傳輸量上也表現(xiàn)出顯著優(yōu)勢。

無線傳感器網(wǎng)絡(luò)；支持向量機(jī)；分布式學(xué)習(xí)；增廣拉格朗日乘子法；平均一致性

1 引言

在無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)的眾多應(yīng)用中，對監(jiān)測到的信息進(jìn)行分類是最重要也是最基礎(chǔ)的一項任務(wù)[1,2]。支持向量機(jī)(Support Vector Machine, SVM)作為一款性能非常出色的分類器，因其堅實(shí)的理論基礎(chǔ)和良好的分類效果，在WSN中得到了越來越廣泛的應(yīng)用[3-5]。然而，在WSN中，SVM的訓(xùn)練數(shù)據(jù)都分散在各個傳感器節(jié)點(diǎn)上，僅依靠單個節(jié)點(diǎn)上的數(shù)據(jù)訓(xùn)練效果較差；而通過多跳路由將所有訓(xùn)練數(shù)據(jù)傳輸?shù)綌?shù)據(jù)融合中心進(jìn)行集中式訓(xùn)練，需要占用大量的帶寬、消耗大量的能量，這與WSN節(jié)點(diǎn)上能源替換代價非常高甚至不可替換、帶寬資源非常有限相沖突，同時也容易使數(shù)據(jù)中心周圍的節(jié)點(diǎn)成為整個系統(tǒng)的瓶頸。針對上述問題，通過相鄰節(jié)點(diǎn)間的相互協(xié)作，在網(wǎng)內(nèi)分布式協(xié)同訓(xùn)練SVM的方法研究，近年來引起越來越多研究者的關(guān)注。

在SVM分布式協(xié)同訓(xùn)練的相關(guān)研究中，專門針對WSN的特性提出訓(xùn)練SVM的算法比較少。其中，文獻(xiàn)[6,7]針對WSN的特性，提出了以在相鄰節(jié)點(diǎn)間傳輸支持向量的協(xié)作方式，每個節(jié)點(diǎn)使用局部訓(xùn)練樣本和從鄰居節(jié)點(diǎn)發(fā)送過來的支持向量進(jìn)行增量訓(xùn)練，將全部節(jié)點(diǎn)訓(xùn)練完后得到的支持向量集合作為集中式訓(xùn)練結(jié)果的近似。由于該算法對每個節(jié)點(diǎn)的增量訓(xùn)練只進(jìn)行一次，所以訓(xùn)練結(jié)果收斂性差，而且當(dāng)支持向量規(guī)模很大時，通信代價仍然會很大。文獻(xiàn)[8,9]提出了基于一致性約束的分布式線性SVM的訓(xùn)練算法MoM-DSVM，該算法在相鄰節(jié)點(diǎn)決策變量相等的約束下，利用并行優(yōu)化技術(shù)，以在相鄰節(jié)點(diǎn)間傳遞少量決策結(jié)果的方式，經(jīng)過多次迭代來實(shí)現(xiàn)各節(jié)點(diǎn)訓(xùn)練結(jié)果的一致。由于僅依靠相鄰節(jié)點(diǎn)間的一致性約束，該算法存在收斂速度慢和收斂性差等缺點(diǎn)。此外，為了解決SVM在大規(guī)模數(shù)據(jù)或分布式數(shù)據(jù)上的訓(xùn)練問題，學(xué)者們提出了許多并行或分布式訓(xùn)練SVM的算法[10-12]，但這些算法沒有考慮WSN資源受限的特性，不適于WSN應(yīng)用。

針對已有研究中存在的通信代價高、收斂性差和收斂速度慢等問題，本文致力于研究在不依賴數(shù)據(jù)融合中心的WSN中，僅依靠相鄰節(jié)點(diǎn)間的相互協(xié)作，在各節(jié)點(diǎn)分類器決策變量與集中式分類器決策變量相一致的約束下，利用分布式優(yōu)化方法，對分布式訓(xùn)練線性SVM的問題進(jìn)行求解和推導(dǎo)?；诖?，提出了基于平均一致性的分布式線性SVM訓(xùn)練算法AC-DSVM和改進(jìn)算法1-AC-DSVM(once Average Consensus based Distributed SVM)。仿真實(shí)驗(yàn)從收斂性、收斂速度和通信代價3個方面對提出的兩個算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，并與已有算法進(jìn)行對比分析。

2 分布式線性SVM協(xié)同訓(xùn)練

2.1 問題描述

考慮一個由J個節(jié)點(diǎn)構(gòu)成的WSN。為了清楚表達(dá)WSN節(jié)點(diǎn)間的相鄰關(guān)系，使用無向圖G={V,E}對其進(jìn)行表示，其中，V表示W(wǎng)SN中J個節(jié)點(diǎn)的集合，E代表相鄰節(jié)點(diǎn)間邊的集合，節(jié)點(diǎn)J的所有鄰居節(jié)點(diǎn)用集合Bj表示。此外，假定圖G是連通的，即圖中的任意兩個節(jié)點(diǎn)之間至少存在一條路徑，也就是圖中不存在孤立節(jié)點(diǎn)。為了方便表述節(jié)點(diǎn)上的訓(xùn)練樣本，每個節(jié)點(diǎn)j∈J上的訓(xùn)練樣本都用一個訓(xùn)練樣本集Sj:={(xjn,yjn):n=1,2,???,Nj}來表示，其中xjn∈Rp是訓(xùn)練樣本的特征向量，p是特征向量維數(shù)，yjn∈Y:={-1,1}是訓(xùn)練樣本對應(yīng)的分類標(biāo)簽，Nj是訓(xùn)練樣本的數(shù)量。本文針對線性SVM訓(xùn)練的問題，研究在WSN下，僅依賴相鄰節(jié)點(diǎn)間的相互協(xié)作，在網(wǎng)內(nèi)分布式協(xié)同訓(xùn)練SVM的方法。

2.2 線性SVM訓(xùn)練問題的分解和推導(dǎo)

SVM的訓(xùn)練問題可以歸結(jié)為求解一個受約束的凸二次規(guī)劃問題[13]。在WSN中，訓(xùn)練樣本都分散在各個傳感器節(jié)點(diǎn)上，而且不同傳感器節(jié)點(diǎn)上的訓(xùn)練樣本個數(shù)有可能不同。因此，本研究采用了文獻(xiàn)[14]中給出的與訓(xùn)練樣本數(shù)量相關(guān)的二次規(guī)劃問題形式。線性SVM問題使用此形式的表示如式(1)：

在式(1)中，W和b分別表示要求解的最優(yōu)分類超平面的權(quán)向量和閾值。ix和iy對應(yīng)的是第i個訓(xùn)練樣本的特征向量和類別標(biāo)簽。iξ和C分別表示松弛變量和懲罰因子，是對個別離群點(diǎn)訓(xùn)練樣本進(jìn)行間隔放松和施加懲罰，iξ是一個未知量，而 C是一個給定值。N表示訓(xùn)練樣本的個數(shù)。

假定分散在各個傳感器節(jié)點(diǎn)上的訓(xùn)練樣本都可以集中起來進(jìn)行SVM訓(xùn)練，此時，線性SVM訓(xùn)練問題對應(yīng)的凸二次規(guī)劃問題形式如式(2)：

式(2)是由J組分散的訓(xùn)練樣本構(gòu)成的集中式訓(xùn)練對應(yīng)的凸二次規(guī)劃問題形式，和同樣訓(xùn)練樣本條件下不分組情況下的表示形式式(1)是完全一致的。為了有利于SVM訓(xùn)練在各節(jié)點(diǎn)上進(jìn)行，將式(2)變換為等價的易于分解的形式[15]，如式(3)：

其中，W*和b*是式(2)中集中式訓(xùn)練時要求解的權(quán)向量和閾值，而Wj和bj是節(jié)點(diǎn)j上要求解的權(quán)向量和閾值。式(2)和式(3)的等價是通過等式約束Wj=W*, bj=b*來保證的。式(3)的分解形式對應(yīng)到每個節(jié)點(diǎn)j上，即每個節(jié)點(diǎn)j上求解的二次規(guī)劃問題形式，如式(4)：

為求解在每個節(jié)點(diǎn)上如式(4)的優(yōu)化問題，利用增廣拉格朗日方法對等式約束Wj=W*(因?yàn)閎j或b*的結(jié)果是由Wj和W*計算得到的)構(gòu)建增廣拉格朗日函數(shù)[16,17]，如式(5)：

其中，由Wj-W*構(gòu)成的二次項是增廣拉格朗日方法中用以保證原目標(biāo)函數(shù)的嚴(yán)格凸性[15]。pj(t )是等式約束Wj=W*上的拉格朗日乘子系數(shù)，c(t)是一個大于零的常數(shù)。對式(5)問題的求解，使用乘子方法[15,16]，該方法采用乘子pj(t+1)的迭代形式，如式(6)所示。其中，W*(t+1)是集中式訓(xùn)練結(jié)果的權(quán)向量，是一個公共的耦合變量，即在每個節(jié)點(diǎn)j上都存在該變量，為此，我們基于當(dāng)變量Wj(t +1)的值越接近W*(t+1)時pj(t +1)的結(jié)果應(yīng)該趨近0的事實(shí)，利用pj(t+1)的迭代形式，對各節(jié)點(diǎn)得到的局部結(jié)果Wj(t), pj(t)求平均來得到W*(t+1)的迭代形式，如式(7)所示。當(dāng)W*(t+1)的值確定后，各個節(jié)點(diǎn)就可以對式(5)的優(yōu)化問題進(jìn)行求解，從而求出Wj(t+1)，如式(8)所示。這樣，對于式(5)問題的求解可以根據(jù)式(6)-式(8)的迭代形式進(jìn)行求解。

其中，式(8)中Wj∈Pj,Pj表示式(5)中的約束條件；各個節(jié)點(diǎn)上對Wj(t +1)的求解，利用拉格朗日對偶理論[13]，構(gòu)建拉格朗日函數(shù)，如式(9)：

其中，jnλ和jnμ為拉格朗日乘子，對偶問題形式如式(10)所示。

在式(11)中， Aj=YjXj,Yj是節(jié)點(diǎn)j上的所有訓(xùn)練樣本的標(biāo)簽列向量，而Xj是對應(yīng)的所有訓(xùn)練樣本的特征向量構(gòu)成的特征矩陣；uj=(1+c(t ))Ip+1, Ip+1是+1p維的單位矩陣。jλ是由該節(jié)點(diǎn)上所有訓(xùn)練樣本的jnλ構(gòu)成的列向量，是未知的。將式(11)，式(12)，式(13)的結(jié)果代入式(10)的目標(biāo)函數(shù)中，可以得到如式(14)所示的目標(biāo)函數(shù)：

這樣，式(10)中的對偶問題可以簡化為：

在式(15)的優(yōu)化問題中，因只含有一個列變量λj，可以利用傳統(tǒng)的二次規(guī)劃問題進(jìn)行求解。當(dāng)求解得到λj后，利用式(11)，就可以求出每個節(jié)點(diǎn)上的Wj(t+1)。至此，WSN中線性SVM分布式協(xié)同訓(xùn)練問題可以按照式(7)、式(15)、式(11)、式(6)的順序進(jìn)行迭代求解。

2.3 分布式線性SVM協(xié)同訓(xùn)練算法

上述線性SVM訓(xùn)練的推導(dǎo)形式式(7)中，公共變量W*(t+1)需要計算所有節(jié)點(diǎn)得到的局部訓(xùn)練結(jié)果Wj(t )和pj(t )的平均值，即各節(jié)點(diǎn)進(jìn)行一次局部訓(xùn)練后就需要對訓(xùn)練結(jié)果Wj(t )和pj(t)進(jìn)行一次全局平均(簡稱“平均一致性”)。因每次迭代都是基于平均一致性來進(jìn)行訓(xùn)練，所以可以保證各節(jié)點(diǎn)能夠收斂到比較優(yōu)的訓(xùn)練結(jié)果，而且也可以加快各節(jié)點(diǎn)的局部收斂速度。為此，提出了基于平均一致性的分布式線性SVM訓(xùn)練算法(Average Consensus based Distributed Supported Vector Machine, AC-DSVM )，具體描述如表1所示。

在AC-DSVM算法中，每迭代一次就要進(jìn)行一次平均一致性的計算。然而，在WSN無數(shù)據(jù)融合中心或特殊節(jié)點(diǎn)的情況下，只依靠相鄰節(jié)點(diǎn)間的協(xié)作來實(shí)現(xiàn)全局平均一致性，會大大增加網(wǎng)絡(luò)的通信開銷。為了使AC-DSVM算法的思想能在無數(shù)據(jù)融合中心的WSN中有效應(yīng)用，降低節(jié)點(diǎn)間通信代價，對其進(jìn)行了改進(jìn)。將AC-DSVM算法中的平均一致性思想應(yīng)用在相鄰節(jié)點(diǎn)間，即在鄰居節(jié)點(diǎn)間進(jìn)行訓(xùn)練結(jié)果的局部平均一致性，以此作為對全局平均一致性的近似，進(jìn)行各節(jié)點(diǎn)的局部訓(xùn)練，直到各個節(jié)點(diǎn)的訓(xùn)練結(jié)果局部收斂。然后通過一次全局的平均一致性計算，得到最優(yōu)訓(xùn)練結(jié)果的近似解?；诖讼敕ǎ岢隽嘶谝淮纹骄恢滦缘姆植际骄€性SVM訓(xùn)練算法(Once Average Consensus based Distributed Supported Vector Machine, 1-ACDSVM)，具體描述如表2所示。

表1 AC-DSVM算法

表2 1-AC-DSVM算法

在上述兩個算法中，都需要求全局平均一致性。但是，在WSN中僅通過相鄰節(jié)點(diǎn)間的相互協(xié)作對各節(jié)點(diǎn)上數(shù)據(jù)求平均一致性，至今還沒有成熟統(tǒng)一的方法[17,18]。為此，本研究使用最簡單的洪泛方法[17]來實(shí)現(xiàn)全局平均一致性，其思想是各節(jié)點(diǎn)將自己的訓(xùn)練結(jié)果和其鄰居節(jié)點(diǎn)傳遞過來的最新訓(xùn)練結(jié)果保存到本地，并將新接收到的訓(xùn)練結(jié)果轉(zhuǎn)發(fā)給其它鄰居節(jié)點(diǎn)，在經(jīng)過與網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)的固定迭代次數(shù)后，各節(jié)點(diǎn)可以得到網(wǎng)絡(luò)中其它所有節(jié)點(diǎn)的數(shù)據(jù)，從而求得全局平均一致。

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

本文以一個由30個節(jié)點(diǎn)構(gòu)成的WSN網(wǎng)絡(luò)為例，使用模擬數(shù)據(jù)和UCI數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。以集中式C-SVM訓(xùn)練結(jié)果為基準(zhǔn)，對AC-DSVM算法，1-AC-DSVM算法和文獻(xiàn)[8]中的MoM-DSVM算法從訓(xùn)練結(jié)果收斂性、收斂速度和數(shù)據(jù)傳輸量3個方面進(jìn)行了對比實(shí)驗(yàn)。

3.1 模擬數(shù)據(jù)實(shí)驗(yàn)

在實(shí)驗(yàn)中使用的模擬數(shù)據(jù)是由2維隨機(jī)向量(X,Y)服從N(2,2,5,5,0)和N(22,2,5,5,0)隨機(jī)產(chǎn)生的兩類訓(xùn)練樣本數(shù)據(jù)，每類訓(xùn)練樣本個數(shù)均為600。將生成的訓(xùn)練數(shù)據(jù)平均分配給WSN中的30個節(jié)點(diǎn)進(jìn)行訓(xùn)練。同時，為了研究不同網(wǎng)絡(luò)結(jié)構(gòu)對算法訓(xùn)練結(jié)果的影響，使用了鏈狀結(jié)構(gòu)和連通度為0.0896的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了實(shí)驗(yàn)。

3.1.1 訓(xùn)練結(jié)果收斂性 從圖1和表3顯示的訓(xùn)練結(jié)果可以看出，AC-DSVM算法和1-AC-DSVM算法得到最優(yōu)決策分類線能夠很好地與集中式C-SVM算法的訓(xùn)練結(jié)果相吻合，尤其是AC-DSVM算法的訓(xùn)練結(jié)果和集中式C-SVM算法的訓(xùn)練結(jié)果完全吻合；而MoM-DSVM算法得到最優(yōu)決策分類線與集中式算法C-SVM的訓(xùn)練結(jié)果吻合得不好，尤其是閾值b差異明顯。從表3還可以看出，不同網(wǎng)絡(luò)結(jié)構(gòu)對算法AC-DSVM和1-AC-DSVM的訓(xùn)練結(jié)果的收斂性影響不明顯，而對MoM-DSVM算法的收斂性略有影響。

表3 4種訓(xùn)練算法得到的最優(yōu)分類決策線的權(quán)向量和閾值

3.1.2 收斂速度 從圖2顯示的結(jié)果可以看出，兩種不同網(wǎng)絡(luò)結(jié)構(gòu)下，算法AC-DSVM, 1-AC-DSVM和MoM-DSVM在網(wǎng)狀結(jié)構(gòu)下收斂迭代次數(shù)，分別比鏈狀結(jié)構(gòu)下收斂迭代次數(shù)少41.2%, 25.5%和52.6%。表明網(wǎng)絡(luò)結(jié)構(gòu)對3種算法的收斂速度影響很明顯，網(wǎng)狀結(jié)構(gòu)比鏈狀結(jié)構(gòu)收斂快；從圖2還可以看出，在鏈狀結(jié)構(gòu)下，AC-DSVM算法比MoM-DSVM的收斂迭代次數(shù)多33.7%; 1-AC-DSVM算法分別比AC-DSVM和MoM-DSVM的收斂迭代次數(shù)少89.2%和82.1%。在網(wǎng)狀結(jié)構(gòu)下，AC-DSVM算法比MoM-DSVM的收斂迭代次數(shù)多65.6%; 1-ACDSVM算法分別比AC-DSVM和MoM- DSVM的收斂迭代次數(shù)少91.5%和88.6%。表明在兩種網(wǎng)絡(luò)結(jié)構(gòu)下，AC-DSVM算法在收斂速度上明顯慢于MoM-DSVM算法，而1-AC-DSVM算法在收斂速度上要明顯快于算法AC-DSVM和MoM-DSVM。

3.1.3 數(shù)據(jù)傳輸量 從圖3顯示的結(jié)果可以看出，兩種不同網(wǎng)絡(luò)結(jié)構(gòu)下，算法AC-DSVM和1-ACDSVM在網(wǎng)狀結(jié)構(gòu)下數(shù)據(jù)傳輸量，分別比鏈狀結(jié)構(gòu)下數(shù)據(jù)傳輸量多3.4%和2.6%，而算法MoM-DSVM在網(wǎng)狀結(jié)構(gòu)下數(shù)據(jù)傳輸量比鏈狀結(jié)構(gòu)下數(shù)據(jù)傳輸量少52.6%。表明算法AC-DSVM和1-AC-DSVM在數(shù)據(jù)傳輸量上受網(wǎng)絡(luò)結(jié)構(gòu)影響不明顯，而算法MoM-DSVM在數(shù)據(jù)傳輸量上受網(wǎng)絡(luò)結(jié)構(gòu)影響明顯；從圖3還可以看出，在鏈狀結(jié)構(gòu)下，AC-DSVM算法比MoM-DSVM的數(shù)據(jù)傳輸量多70.2%，算法1-AC-DSVM分別比AC-DSVM和MoM-DSVM的數(shù)據(jù)傳輸量少92%和86.4%；在網(wǎng)狀結(jié)構(gòu)下，ACDSVM算法比MoM-DSVM的數(shù)據(jù)傳輸量多271%，算法1-AC-DSVM分別比AC-DSVM和MoMDSVM的數(shù)據(jù)傳輸量少92.1%和70.8%。表明在兩種網(wǎng)絡(luò)結(jié)構(gòu)下，AC-DSVM算法在數(shù)據(jù)傳輸量上明顯高于MoM-DSVM算法， 而1-AC-DSVM算法在數(shù)據(jù)傳輸量上明顯低于算法AC-DSVM和MoMDSVM。

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

為了驗(yàn)證算法AC-DSVM和1-AC-DSVM對實(shí)際訓(xùn)練樣本數(shù)據(jù)的有效性，使用UCI數(shù)據(jù)庫中的Wine數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。因Wine數(shù)據(jù)集的樣本數(shù)據(jù)是13維的高維數(shù)據(jù)，訓(xùn)練得到的最優(yōu)分類超平面不易平面表現(xiàn)，所以本實(shí)驗(yàn)只對13維權(quán)向量的分量及閾值的收斂過程和收斂結(jié)果進(jìn)行顯示。本文選取了13維權(quán)向量的分量w1, w3, w5和閾值b在算法AC-DSVM, 1-AC-DSVM, C-SVM和MoM-DSVM下的收斂過程和收斂結(jié)果進(jìn)行顯示，如圖4(a)-4(d)。從圖4中各子圖的顯示結(jié)果可以看出，算法AC- DSVM和1-AC-DSVM可以近似收斂到集中式的訓(xùn)練結(jié)果，算法AC-DSVM收斂過程中呈現(xiàn)的階梯狀收斂趨勢的水平方向和算法1-AC-DSVM收斂過程中最后的直接跳變反映了平均一致性算法的運(yùn)行；從圖4中各子圖的顯示結(jié)果還可以看出，與算法MoM-DSVM相比， 算法AC-DSVM的收斂速度稍慢，而算法1-AC-DSVM明顯快于算法ACDSVM和MoM-DSVM。

4 結(jié)束語

圖1 兩類訓(xùn)練樣本和4種訓(xùn)練算法得到的最優(yōu)分類決策線

圖2 兩種網(wǎng)絡(luò)結(jié)構(gòu)下3種 算法的迭代次數(shù)

圖3 兩種網(wǎng)絡(luò)結(jié)構(gòu)下3種 算法的數(shù)據(jù)傳輸量

圖4 Wine數(shù)據(jù)集下4種算法的收斂過程和收斂結(jié)果

本文在各節(jié)點(diǎn)局部分類器決策變量與集中式?jīng)Q策變量相一致的約束下，利用分布式優(yōu)化方法，研究了僅依靠相鄰節(jié)點(diǎn)間的相互協(xié)作，在網(wǎng)內(nèi)分布式協(xié)同訓(xùn)練線性SVM的方法，提出了基于平均一致性的分布式線性SVM訓(xùn)練算法AC-DSVM和改進(jìn)算法1-AC-DSVM。仿真實(shí)驗(yàn)結(jié)果表明：與算法MoM-DSVM相比，AC-DSVM算法雖然在收斂速度和數(shù)據(jù)傳輸量方面較差，但其可以準(zhǔn)確地收斂到集中式訓(xùn)練結(jié)果；1-AC-DSVM算法具有較好收斂性，而且在收斂速度和數(shù)據(jù)傳輸量上也表現(xiàn)出了顯著優(yōu)勢。此外，不同網(wǎng)絡(luò)結(jié)構(gòu)對兩個算法在收斂性和數(shù)據(jù)傳輸量上的影響不明顯，對收斂速度影響較明顯。1-AC-DSVM算法因其良好的性能為WSN下SVM分布式協(xié)同訓(xùn)練提供了一種非常有效的方法。由于SVM的優(yōu)勢在于解決非線性問題，因此筆者進(jìn)一步的研究工作是將提出的算法擴(kuò)展到非線性問題的求解上。

[1] 呂方旭, 張金成, 郭相科, 等. 基于WSN的戰(zhàn)場聲目標(biāo)多特征聯(lián)合智能分類識別[J]. 科學(xué)技術(shù)與工程, 2013, 13(35): 10713-10721.

Lü Fang-xu, Zhang Jin-cheng, Guo Xiang-ke, et al.. The acoustic target in battlefield intelligent classification and identification with multi-features in WSN[J]. Science Technology and Engineering, 2013, 13(35): 10713-10721.

[2] Taghvaeeyan S and Rajamani R. Portable roadside sensors for vehicle counting, classification, and speed measurement[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(1): 73-83.

[3] Shahid N, Naqvi I H, and Bin Qaisar S B. Quarter-sphere SVM: attribute and spatio-temporal correlations based outlier & event detection in wireless sensor networks[C]. IEEE Wireless Communication and Networking Conference: Mobile and Wireless Networks, Paris, 2012: 2048-2053.

[4] 劉倩, 崔晨, 周杭霞. 改進(jìn)型SVM多類分類算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用[J]. 中國計量學(xué)院學(xué)報, 2013, 24(3): 298-303.

Liu Qian, Cui Chen, and Zhou Hang-xia. Application of a modified SVM multi-class classification algorithm in wireless sensor networks[J]. Journal of China University of Metrology, 2013, 24(3): 298-303.

[5] Raj A B, Ramesh M V, Kulkarni R V, et al.. Security enhancement in wireless sensor networks using machine learning[C]. IEEE 14th International Conference on High Performance Computing and Communications, Liverpool, 2012: 1264-1269.

[6] Flouri K, Beferull-Lozano B, and Tsakalides P. Optimal gossip algorithm for distributed consensus SVM training in wireless sensor networks[C]. Proceedings of the 16th International Conference on Digital Signal Processing (DSP′09), Heraklion, 2009: 886-891.

[7] Flouri K, Beferull-Lozano B, and Tsakalides P. Training a support-vector machine-based classifier in distributed sensor networks[C]. Proceedings of 14th European Signal Processing Conference, Florence, 2006: 1-5.

[8] Forero P A, Cano A, and Giannakis G B. Consensus-based distributed linear support vector machines[C]. Proceedings of the International Conference on Information Processing in Sensor Networks, Stockholm, 2010: 35-46.

[9] Forero P A, Cano A, and Giannakis G B. Consensus-based distributed support vector machines[J]. Journal of Machine Learning Research, 2010, 11(May): 1663-1707.

[10] Lu Y, Roychowdhury V, and Vandenberghe L. Distributed parallel support vector machines in strongly connected networks[J]. IEEE Transactions on Neural Networks, 2008, 19(7): 1167-1178.

[11] Wang Dong-li, Li Jian-xun, and Zhou Yan. Support vector machine for distributed classification: a dynamic consensus approach[C]. IEEE/SP 15th Workshop on Statistical Signal Processing, Wales, 2009: 753-756.

[12] Kim Woo-jin, Yoo Jae-hyun, and Kim H J. Multi-target tracking using distributed SVM training over wireless sensor networks[C]. IEEE International Conference on Robotics and Automation, Saint Paul, 2012: 2439-2444.

[13] Shawe T J and Cristianini N. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods [M]. New York: Cambridge University Press, 2000: 121-130.

[14] Scholkopf B and Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [M]. New York: The MIT Press, 2002: 204-205.

[15] Bertsekas D P and Tsitsiklis J N. Parallel and Distributed Computation: Numerical Methods[M]. Massachusetts: Athena Scientific, 1997: 243-247.

[16] Boyd S, Parikh N, and Chu E. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1): 1-122.

[17] Sardellitti S, Giona M, and Barbarossa S. Fast distributed average consensus algorithms based on advection-diffusion processes[J]. IEEE Transactions on Signal Processing, 2010, 58(2): 826-842.

[18] Sardellitti S, Barbarossa S, and Swami A. Average consensus with minimum energy consumption: optimal topology and power allocation[C]. Proceedings of the European Signal Processing Conference (EUSIPCO 2010), Aalborg, 2010: 189-193.

及歆榮： 女，1978年生，博士生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、分布式機(jī)器學(xué)習(xí).

侯翠琴： 女，1983年生，博士，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、分布式機(jī)器學(xué)習(xí).

侯義斌： 男，1952年生，教授，博士生導(dǎo)師，主要研究方向?yàn)槲锫?lián)網(wǎng)接入技術(shù)、新型人機(jī)交互技術(shù)、嵌入式軟件與系統(tǒng).

Research on the Distributed Training Method for Linear SVM in WSN

Ji Xin-rong①②Hou Cui-qin①Hou Yi-bin①

①(Embedded Software and Systems Institute, Beijing University of Technology, Beijing 100124, China)
②(School of Information and Electrical Engineering, Hebei University of Engineering, Handan 056038, China)

In Wireless Sensor Network (WSN), transferring all training samples distributed across different nodes to a centralized fusion center for training Support Vector Machine (SVM) significantly increases the communication overhead and energy consumption. Therefore, this paper studies the distributed training approach for linear SVM through the collaboration of neighboring nodes within the networks. First, the centralized linear SVM problem is cast as the solution of coupled decentralized convex optimization sub-problems with consensus constraints on the classifier parameters. Second, the distributed linear SVM problem is solved and derived using the augmented Lagrange multipliers method, and a novel distributed training algorithm, called Average Consensus based Distributed Supported Vector Machine (AC-DSVM), is proposed. To decrease the communication overhead of global average consensus, an improved distributed training algorithm, named Once Average Consensus based Distributed Supported Vector Machine (1-AC-DSVM), is presented, which is only based on once global average consensus. Simulation results show that compared with existing algorithms, AC-DSVM has slightly higher iterations and data traffic, but can converge to the centralized training results; 1-AC-DSVM not only has better convergence, but also has remarkable advantage in convergence speed and data traffic.

Wireless Sensor Network (WSN); Support Vector Machine (SVM); Distributed learning; Augmented Lagrange multiplier method; Average consensus

TP393; TP181

A

1009-5896(2015)03-0708-07

10.11999/JEIT140408

2014-03-27 收到，2014-07-07改回

國家自然科學(xué)基金青年基金(61203377)資助課題

*通信作者：侯義斌 yhou@bjut.edu.cn