無線傳感器節點多特征組合加權K-means聚類算法

吉書瑤， 呂紅芳

(上海電機學院 電氣學院， 上海 201306)

無線傳感器節點多特征組合加權K-means聚類算法

吉書瑤， 呂紅芳

(上海電機學院 電氣學院， 上海 201306)

針對無線傳感器節點能耗不均的問題，研究了一種多特征組合加權的K-means聚類算法。改進了傳統K-means算法中聚類中心隨機選擇的問題，并針對各維度特征對聚類影響的不同，賦予不同特征不同的權值。采用新的算法，并為其構建對應的算法性能衡量指標，與已有算法相比，新算法效果較好，能夠明顯提高數據聚類效果。

無線傳感器；K-means聚類算法； 聚類中心； 組合加權

聚類分析[1-3]又稱群分析，是研究分類問題的一種統計分析方法。聚類分析是將物理或抽象對象的集合分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組數據對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。K-means算法[4-5]是一種很典型的以距離作為相似性指標的、最常用的聚類算法。文獻[6]中通過多次計算每個聚類的均值，不斷更新聚類中心來達到聚類的最優效果；文獻[7]中實現了一種局部優化的K-means算法；文獻[8]中提出了一種運行于大數據平臺上的一種改進的M+K-means聚類算法；文獻[9]中總結了K-means聚類算法存在的問題以及進一步的研究方向。目前的研究中，K-means算法主要存在以下問題：① 聚類個數K為事先給定，且其值難以估計，很多時候，事先并不能確定將給定的數據集分成多少個類別才最合適；② 傳統K-means聚類算法隨機選擇聚類中心會導致不同的聚類結果，影響尋找最優解；③ 不同的特征在聚類過程中往往被賦予平等的地位，而不同的研究中多特征聚類的每個特征對結果的影響程度是不同的。

無線傳感器節點能耗不均問題[10-12]一直是其充電問題研究的熱點。針對充電路徑規劃問題，傳統方法是按照傳感器節點能耗程度分類[13]或所在空間位置分類，但是，單一模型往往難以精確地反映優化對象的特性，從而降低了模型的估計精度和優化能力。在利用移動充電設備對傳感器節點充電的無線傳感器網絡中，移動充電設備充電行為的規劃是影響能量利用率的重要原因;在對充電路徑的規劃過程中重點分析節點能耗與空間位置的特征，可以有效提高充電行為的效率，利用最少的資源獲得最高的網絡效用。

本文針對傳統K-means算法的不足，根據節點能耗和空間位置對充電規劃影響程度的不同，建立基于改進最大最小距離算法來選擇初始聚類中心的K-means的組合加權模型。訓練集樣本數據經上述方法聚類后,按照無線傳感器節點的不同類型特征，利用加權K-means聚類算法計算不同特征的權值，構建新的專家偏好模型，最后利用本文建立的模型，將其利用在無線傳感器節點能耗聚類建模中。經算例驗證，與傳統的算法相比，多特征組合算法可以有效地提高聚類的效果和效率。

1 多特征組合加權K-means聚類算法

1.1網絡結構

一個典型的無線可充電傳感器網絡[13]如圖1所示，其包括若干傳感器節點、一個或多個移動充電設備(Mobile Charger,MC)、基站節點 (Base Station,B)及服務站節點(Service Station,S)4部分。其中,傳感器節點和基站節點組成傳感器網絡,主要負責數據的采集、轉發、存儲及處理；服務站節點和移動充電節點組成充電系統，主要負責提供傳感器網絡的能量供應。

圖1 無線可充電傳感器網絡結構圖

本文假設無線可充電傳感器網絡中所有可充電傳感器節點和基站均分布在一個2D平面內，當移動充電設備在平面內工作時，不僅要給傳感器節點充電，其自身移動也要消耗能量。當移動充電設備移動時，要考慮最小化移動能量消耗；當對傳感器節點進行充電時，由于節點能耗不均、充電設備能量有限，此時,若按貪心充電方案[13]給節點充電，則節點能量低于正常工作需求從而降低整個網絡的生命周期。因此，要實現充電路徑的規劃，充電節點的位置坐標和其本身的能耗程度成為主要研究對象。

1.2樣本數據規格化

數據規格化是指將數據按比例縮放，使之落入(0,1)的區間內。在實際應用中，由于選擇的特征目標包含不同類型的屬性，為消除數據各維度間單位的限制，先將目標數據進行規格化，使不同單位或量級的數據間具有可比性。

常見的規格化方法是Min-Max標準化[14]。設數據集合θ=(θ1,θ2,…,θn)(1≤i≤n)，提取集合中的最大值θi(max)和最小值θi(min)，則線性變換后得到的規格化結果為

(1)

1.3改進最大最小距離法

假設含有n個樣本的樣本集X=(x1,x2,…,xn)，每個樣本有R個特征維度，即樣本xi=(xi1,xi2,…xiR)(1≤r≤R)。聚類算法最常用的計算數據對象間的距離度量是歐氏距離[15]，樣本xi和樣本xj之間的歐式距離為

1≤r≤R, 1≤i≠j≤n

(2)

式中,xir、xjr為樣本xi、xj的r維特征。歐式距離d(xi,xj)越小，樣本xi和xj越相似，差異度越小。

傳統的最大最小距離法方法如下：隨機選擇一個初始樣本對象作為第1聚類中心，然后,選擇一個與第1聚類中心最遠的樣本作為第2聚類中心，同理確定其他聚類中心，直到無新的聚類中心產生;最后,將樣本按最小距離原則歸入最近的類，聚類中心集合記為M=(m1,m2,…,mK),k=1,2,…,K。

(3)

然后，根據圓內數據點的數量排序，選擇圓內數據點最多的樣本中心作為第1聚類中心，其余聚類中心的選擇考慮距離因素，以保證類與類之間有足夠的分散度。

本文優化的最大最小距離算法步驟如下：

(1) 選取第1聚類中心m1。

(2) 計算集合中其他樣本到m1的距離記為D1。若樣本xs到m1的距離dsm=max {D1}，則將樣本xs作為第2聚類中心，標記m2=xs。

(3) 計算集合中剩余樣本到m1和m2的距離分別為D1和D2。若樣本xg到聚類中心mk(k=1,2,…,K)的距離dgm=max{min(D1,D2)}，則樣本xg作為第3聚類中心，標記m3=xg。同理，若dvm=max{min(D1,D2,D3)},則樣本xv作為第4聚類中心，標記m4=xv。以此類推，直到不滿足約束條件[16]

dim>δdsm

停止尋找聚類中心。其中,δ為參數。

(4) 按照最近原則把所有樣本歸屬到最近的聚類中心。

由上述算法可見，初始聚類中心處于樣本集中的區域，且考慮最大距離的因素,有效避免了其余聚類中心也集中在此區域，由此保證了較高質量的初始值選擇。在確定聚類中心的過程中，參數δ是算法的約束參數，其賦值是直接影響算法的約束條件，需要多次仿真實驗才能得到較優的賦值。

1.4特征權值的確定

多特征組合加權指使用一定的方法，根據對象的不同特征反映出對象的總體特征信息，其中,對象特征和權重系數將直接決定最終的結果。一般在綜合考慮各指標間的相互關系后，根據各指標所提供的初始信息量來確定權重系數，能夠達到較為精確的聚類結果。

對于訓練集樣本X=(x1,x2,…,xn)，n∈N，設對應R個特征的權重系數W={w1,w2,…,wR}，R∈N。本文對權重設置說明如下：對于任意兩個屬性特征a、b，若屬性a樣本的離散度較屬性b大，則認為屬性a在聚類中應占有更重要的地位；通過對屬性a賦予較大權值來調整特征空間，可以更準確地反映類內相似度，并得到更佳的聚類結果。本文從聚類的樣本入手，用標準差[15]計算樣本集各個特征的離散程度來確定r維度數據的特征權值wr的大小，即

(4)

加權后的歐式距離更新為

1≤i≠j≤n

(5)

得到的加權組合模型為

xir

(6)

2 算法性能評價指標

樣本數據X1=(x1,x2,…,xn)的聚類中心為M=(m1,m2,…，mK)，即有K個類，則X=(X1,X2,…，XK)，綜合考慮類內、類間聚類效果的想法，要求類內距離越小越好，類間距離越大越好。類內距離主要考察每一類中各點到聚類中心的平均距離，反映了類內數據的緊密性C(Compactness)，

1≤i≤n

(7)

類間距離主要是考慮各聚類中心兩兩之間平均距離，反映了聚類中心的分散度S(Separation)，

(8)

由于緊密性參數未考慮數據的類間效果，分散度參數無法體現類內效果，故針對聚類效果的要求，構造算法性能評價指標為

J=S/C

(9)

J值越大,表示聚類效果準確性越高，同時每個類內的相似度越高。

3 算例分析

本文用MATLAB軟件來仿真驗證的本文多特征組合加權K-means聚類算法的聚類效果，并與傳統K-means聚類算法相比較。將隨機部署在100 m×100 m無線傳感器監測范圍內的150個無線可充電傳感器節點作為研究目標。針對不同區域覆蓋要求不同的情況，會出現監測目標數量多、密度大的“熱點區域”，該區域的傳感器節點對能量的要求相應較大。圖2為區域監測覆蓋率示意圖。其中，無線傳感器監測范圍為100 m×100 m的正方形區域，無線傳感器節點隨機分布在區域內及邊緣上，不同標志的傳感器節點對應不同的能耗程度。

圖2 節點能耗分布圖

假設一個監測區域內傳感器節點的能耗速度是恒定的，在監測行為開始時每個節點電池容量均為E，t為傳感器節點開始工作后、充電設備工作前的任意時刻，則節點i在t時刻的剩余能量為

Ei(t)=E-eit

其中，ei為節點單位時間的能耗。本文針對節點能耗的不同,采用rand隨機函數生成(0，1)之間的任意正數對其賦值，并將ei作為第1個特征目標xi1。

然后，將節點的位置作為第2個特征目標。假設檢測區域內第i個節點的坐標為(ai,bi) 。由于選擇的特征目標包含不同類型的屬性，故將目標數據進行Min-Max規格化，得到

(10)

將此結果記為節點的第2個特征目標的仿真數據xi2。

最后，得到新的樣本集合X=(x1,x2,…,xn)，其中,xi=(xi1,xi2)，將其作為新的樣本數據代入本文算法中進行實驗仿真。

文獻[16]中的K-means聚類算法，與本文算法相同，都是采用最大最小距離法確定所有初始聚類中心，不同的是本文在其基礎上改進了第1聚類中心的選取方法。為了驗證本文算法的效果，將規格化后的樣本數據代入文獻[16]中算法，與本文算法進行比較。

利用本文算法對150個節點數據進行聚類處理，列出部分處理后聚類樣本節點如表1所示。

根據處理后的樣本數據代入式(4)計算得到兩個維度對應的特征權值分別為W1=0.29和W2=0.24，則得到加權組合模型如下：

(11)

實驗中，K的具體取值要求在不同應用領域取不同的值以得到理想的效果。根據選擇聚類中心的約束條件可以看出，δ的賦值和得到的聚類中心個數關系重大，根據經驗一般從0.5開始試探性地逼近δ最優值。本文多次嘗試后得到δ=0.6時聚類中心的個數最為合理，聚類中心個數K=4。

表1 部分節點聚類結果

聚類中，選取初始聚類中心節點為N133，其余聚類中心分別為N43、N46、N129。

本文給出了利用本文算法和文獻[16]中算法聚類結果圖，如圖3所示。

(a) 傳統K-means聚類算法

圖3兩種不同聚類算法的聚類結果

Fig.3 Clustering results of two different clustering algorithms

由圖3(a)可見，文獻[16]中的算法聚類結果類之間沒有明顯界限，不同類數據出現交叉現象，尤其ei在0～0.4范圍內，聚類結果混亂，且類內數據個數相差很大;而這些情況在圖3(b)中有明顯改善，數據聚類結果集中，能夠得到較為明顯的聚類結果，類間界限比較清晰。

根據兩種算法的聚類數據結果,計算得到傳統算法的性能評價指標J1=0.19,本文算法的性能評價指標J2=0.23，可見本文提出的聚類模型聚類效果提高了21%,結合圖3的聚類結果圖，表明本文算法與傳統的同類聚類算法相比，能夠有效地根據數據的相似程度形成更清晰的聚類結果，且分類精度明顯提高。

4 結 語

針對無線可充電傳感器網絡節點能耗不均的問題，研究了一種基于多特征組合加權的K-means聚類算法。該算法采用改進最大最小距離算法尋找到最合適的聚類中心，并根據不同特征目標對聚類效果的重要程度對充電接點進行有效聚類。仿真結果表明，與傳統算法相比,本文算法聚類效果明顯、類間距較大且類內離散程度低,較高保證了初始中心點的質量，解決了K-means算法中初始值造成的局部最優的問題。本文在對無線可充電傳感器節點的模型建立和對整個充電網絡規劃的設計有著重要意義。

[1] 陳路瑩.高維數據的聚類分析方法研究及其應用 [D].廈門：廈門大學,2009.

[2] PETERS G, LAMPART M. A partitive rough clustering algorithm [C]// International Conference on Rough Sets and Current Trends in Computing. Berlin, Heidelberg: Springer-Verlag, 2006: 657-666.

[3] 劉國華.基于K-means算法的學生行為分析系統的設計與實現 [D].石家莊：河北科技大學,2014:15-17.

[4] 李蘇葦.模糊聚類在經濟區域劃分中的應用 [D].成都：西南交通大學,2015:14-16.

[5] 章宦記.改良的K-means與K近鄰算法特性分析 [J].電子產品世界，2016(1):79-80.

[6] 袁方，孟增輝，于戈.K-means聚類算法的改進 [J].計算機工程與應用，2004,40(36):177-178,232.

[7] 雷小鋒，謝昆青，林帆，等. 一種基于K-means局部最優性的高效聚類算法 [J].軟件學報, 2008, 19(7):1683-1692.

[8] 武霞,董增壽,孟曉燕. 基于大數據平臺hadoop的聚類算法K值優化研究 [J].太原科技大學學報, 2015, 36(2):92-96.

[9] 王千，王成，馮振元，等.K-means聚類算法研究綜述 [J].電子設計工程，2012，20(7):21-24.

[10] 顧晶晶,陳松燦,莊毅. 基于無線傳感器網絡拓撲結構的物聯網定位模型 [J].計算機學報,2010,33(9):1548-1556.

[11] 鄧昂. 無線傳感器網絡節點的能耗管理研究 [D]. 長沙：中南大學,2012:23-29.

[12] 張瑞華.基于能量效率的無線傳感器網絡關鍵技術研究 [D].濟南：山東大學，2007:78-80.

[13] 胡誠.無線可充電傳感器網絡中充電規劃及其可調度性研究 [D].南京：東南大學,2015:46-51.

[14] 李天慶, 張毅, 張冰,等. 基于XML的體育數據規格化存儲技術研究 [J]. 計算機工程與應用, 2001, 37(22):6-8,94.

[15] 郭靖. 對K-means聚類算法歐氏距離加權系數的研究 [J].網絡安全技術與應用, 2016(10):74-75.

[16] 周涓, 熊忠陽, 張玉芳,等. 基于最大最小距離法的多中心聚類算法 [J].計算機應用, 2006, 26(6):1425-1427.

[17] HUANG Xiaohui, YE Yunming, GUO Huifeng, et al. DSKmeans: A new kmeans-type approach to discriminative subspace clustering [J].Knowledge-Based Systems, 2014, 70:293-300.

Combined Weighted Multi-FeatureK-means Clustering for Wireless Sensor Nodes

JIShuyao,LüHongfang

(School of Electrical Engineering, Shanghai Dianji University, Shanghai 201306, China)

Aiming at the problem of energy consumption of wireless sensor nodes, we propose a combined weighted multi-featureK-means clustering algorithm. Clustering center is not considered in traditional k-means algorithms. To improve the maximum minimum distance method, weights of different characteristics are given to different characteristics of the clustering based on the characteristics of each dimension. A measurement index is defined to evaluate performance of the proposed algorithm. Compared with existing algorithms, the proposed algorithm is effective and can improve data clustering results.

wireless sensor;K-means clustering; clustering center; combined weighting

TP 212.9；TP 301.6

A

2017 -05 -15

吉書瑤(1992-)，女，碩士生，主要研究方向無線傳感器網絡移動充電規劃，E-mail:1054101382@qq.com

2095 - 0020(2017)04 -0226 - 06