基于融合聚類的藍牙室內(nèi)定位系統(tǒng)算法優(yōu)化

周向前，張 峰，劉葉楠，張 馳，趙 黎

（西安工業(yè)大學(xué) 電子信息工程學(xué)院，西安710021）

隨著大數(shù)據(jù)和物聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，基于定位導(dǎo)航領(lǐng)域的信息業(yè)務(wù)因其巨大的商業(yè)潛力和工程應(yīng)用價值而備受關(guān)注，定位導(dǎo)航正在由室外走向室內(nèi)，藍牙指紋室內(nèi)定位技術(shù)克服了室內(nèi)GPS 等現(xiàn)有定位方案受到強烈干擾的條件下定位誤差較大的問題，可以滿足人們?nèi)粘５氖覂?nèi)定位需求，廣泛地應(yīng)用在機場、大型商場、醫(yī)院即展館等大型公共場所，具有廣泛的應(yīng)用前景[1]。K-means 聚類算法是一種經(jīng)典的劃分方法，K-means 算法可以有效地利用定位區(qū)域內(nèi)信號的多徑效應(yīng)特征，根據(jù)指紋庫中各指紋點間的相似程度，將相似度高的指紋點劃分到一個簇中，可以提高定位系統(tǒng)的定位精度[2]。為了提高K-means 算法的穩(wěn)定性，在此提出了采用融合聚類的方式改進傳統(tǒng)K-means 算法的初始聚類中心及聚類數(shù)選取隨機性的問題[3]，通過結(jié)合2 種算法的優(yōu)勢，提高定位系統(tǒng)的定位精度和穩(wěn)定性。

1 基于K-means 的藍牙場強室內(nèi)定位算法

1.1 K-means 藍牙場強室內(nèi)定位系統(tǒng)

在藍牙指紋室內(nèi)定位系統(tǒng)中，先建立定位區(qū)域的指紋庫；采用K-means 算法完成對指紋庫的軟劃分；采用位置指紋定位算法估計定位點的坐標(biāo)信息[4]。在離線采集階段，在定位區(qū)域內(nèi)采集各個采樣點的指紋信息[5]，即該指紋點的特征信息（包括該指紋點的信號強度值信息和坐標(biāo)信息）， 建立定位區(qū)域的指紋庫為

式中：m 為定位區(qū)域內(nèi)的采樣點個數(shù)；n 為采樣點接收到iBeacon 信號強度值個數(shù)；x，y 為采樣點的坐標(biāo)信息。采用K-means 聚類算法完成對指紋庫的軟劃分，將指紋庫劃分為k 個簇，同時確定這k 個簇的最終聚類中心；在實時定位階段，計算待定位目標(biāo)與各簇最終聚類中心的相似程度，選取相似度最高的簇，再使用指紋定位算法確定待定位目標(biāo)的坐標(biāo)[6-7]。指紋定位原理如圖1所示。

圖1 指紋定位原理Fig.1 Principle of fingerprint location

1.2 K-means 聚類算法

設(shè)定聚類數(shù)為k（k≤m），即將指紋庫劃分為k個簇。從指紋庫中，隨機選擇k 個指紋點Ci=［c1，c2，…，ck］作為K-means 迭代的初始聚類中心，計算指紋庫中其他指紋點與這k 個初始聚類中心的歐式距離，計算方法為

式中：Dhi為指紋點i 與指紋點h 之間的距離。將這些指紋點劃分到距離最近的簇，不斷地迭代計算聚類中心，直至聚類中心不再變化或達到最小誤差平方準(zhǔn)則。

K-means 聚類算法描述如下：

輸入指紋數(shù)據(jù)庫；

輸出最終聚類結(jié)果。

步驟1在指紋庫中隨機選取k 個指紋數(shù)據(jù)Ci=［c1，c2，…，ck］作為K-means 算法的初始聚類中心；

步驟2將每個指紋點分配到最近的聚類中心所在的簇，形成k 個簇；

步驟3計算這k 個簇的聚類中心；

步驟4重復(fù)步驟2 和步驟3 直至聚類中心不再發(fā)生變化。

1.3 指紋定位算法

實時定位階段，計算待定位目標(biāo)與各個簇最終聚類中心間的歐式距離，選取與待定位目標(biāo)相似度最高的簇，使用指紋定位算法估計定位目標(biāo)的位置坐標(biāo)信息，在此采用K-近鄰算法對定位目標(biāo)位置進行估計。

K-近鄰法K-NN（K-nearst neighbor）在匹配指紋庫時選取與待定位目標(biāo)最近的K（K≥2）個指紋數(shù)據(jù)，再通過計算這K 個指紋信息的平均坐標(biāo)得到定位點坐標(biāo)[8]。計算距離采用歐式距離方法計算，對歐式距離的值從小到大排列，選取前K 個指紋點的坐標(biāo)，計算待定位目標(biāo)的位置坐標(biāo)為

2 基于K-means 的室內(nèi)定位算法優(yōu)化

K-means 算法自身存在天然的缺陷導(dǎo)致定位系統(tǒng)總不是處于最優(yōu)狀態(tài)，初始聚類中心選取的隨機性和聚類數(shù)設(shè)定的經(jīng)驗性，導(dǎo)致對指紋庫的聚類往往不是最優(yōu)聚類，使得定位系統(tǒng)缺乏穩(wěn)定性。針對K-means 算法的這一缺陷， 在此采用了基于融合聚類的指紋定位算法室內(nèi)定位系統(tǒng)。融合聚類流程如圖2所示。

圖2 融合聚類流程Fig.2 Fusion clustering flow chart

改進后的室內(nèi)定位系統(tǒng)， 在離線采集階段：預(yù)聚類階段以基于密度峰值的聚類算法為基礎(chǔ)，對指紋庫進行初步聚類，確定最佳聚類數(shù)k 和初始聚類中心；正式聚類階段采用K-means 算法完成對指紋庫的聚類[9]。實時定位階段：選擇與待定位目標(biāo)相似度最高的聚類中心所在的簇， 采用K-NN 算法估計待定位目標(biāo)的位置坐標(biāo)信息，完成定位。

2.1 基于密度峰值的聚類算法

基于密度峰值的聚類算法（Clustering by Fast Search and Find of Density Peaks，簡稱DPC）是一種基于密度的聚類算法，能夠快速發(fā)現(xiàn)任意形狀數(shù)據(jù)的密度峰值點（即聚類中心），并高效地進行樣本點的分配和離群點的剔除，且參數(shù)容易確定，是一種適用于大規(guī)模的數(shù)據(jù)聚類算法[10]。

DPC 算法的核心思想是：①類簇中心點的密度比其周圍鄰居點大；②類簇中心點與更高密度點間的距離相對較大。當(dāng)類簇中心點確定以后，每一個數(shù)據(jù)點分配給比其密度值大且距離其最近的數(shù)據(jù)點相同的簇，根據(jù)密度值從大到小依次更新所有數(shù)據(jù)點的分類，直至聚類完成[11]。計算任意兩指紋點間的相似度，采用高斯核函數(shù)密度估計方法，估計任意指紋點的局部密度ρi和局部距離δi分別定義為

式中：dij為指紋點i 與指紋點j 之間的歐式距離，使用式（2）計算；dc為截斷距離，為前2%的指紋點間的歐式距離。

為了便于確定聚類中心，結(jié)合DPC 算法的核心思想，計算將ρi和δi值綜合考慮的綜合決策量為

將γi進行降序排序構(gòu)造決策圖，γi值越大則數(shù)據(jù)對象是聚類中心的可能性就越大。從聚類中心的γi值過渡到非聚類中心的γi值時有一個非常明顯的跳躍，選取這些突出的γi值（即跳躍前的γi）所對應(yīng)的指紋點作為初始聚類中心，同時可以確定聚類數(shù)目，將密度值從大到小依次更新所有指紋點分類直至聚類完成，完成聚類。

DPC 算法流程描述如下：

輸入指紋數(shù)據(jù)庫；

輸出最終聚類結(jié)果，最佳聚類數(shù)k。

步驟1計算指紋數(shù)據(jù)庫的歐式距離矩陣，計算截斷距離dc；

步驟2計算指紋數(shù)據(jù)庫中每個數(shù)據(jù)點的局部密度ρi和局部距離δi；

步驟3計算綜合變量γi并進行降序排序，選擇前k 個突出的指紋點作為初始聚類中心；

步驟4根據(jù)密度值從大到小依次更新所有數(shù)據(jù)點的分類直到聚類完成。

2.2 融合聚類算法

融合聚類算法的核心思想是：融合2 種不同的聚類算法，發(fā)揮這2 種算法的長處，優(yōu)勢互補，提高聚類算法的性能和穩(wěn)定性[7]。即先采用基于密度峰值的聚類算法確定最佳聚類數(shù)及初始聚類中心，再采用K-means 算法完成對數(shù)據(jù)庫的劃分。在此，首先計算所有指紋點間的歐式距離， 選取前2%的指紋點間的歐式距離作為高斯核函數(shù)的截斷距離dc，然后利用高斯核函數(shù)計算各指紋點的局部密度，最后確定局部距離的同時計算綜合變量γi。γi由大到小排序后會出現(xiàn)明顯的跳躍點，跳躍點之前的k 個點為初始聚類中心，同時確定最佳聚類數(shù)k，使用K-means算法迭代完成最終的聚類。定位流程如圖3所示。

圖3 融合聚類流程Fig.3 Fusion clustering flow chart

3 算法仿真與試驗分析

3.1 試驗環(huán)境介紹

室內(nèi)定位試驗在通信學(xué)科實驗室中進行，在試驗環(huán)境中對iBeacon 基站進行合理的布局。試驗環(huán)境及iBeacon 基站布局如圖4所示， 試驗環(huán)境參數(shù)見表1。

圖4 試驗環(huán)境及iBeacon 布局Fig.4 Experimental environment and iBeacon layout

表1 試驗環(huán)境參數(shù)Tab.1 Experimental environment parameters

3.2 基于密度峰值的聚類算法應(yīng)用

在融合聚類算法中，利用高斯核函數(shù)計算各指紋點的局部密度，計算局部距離δi繪制出指紋數(shù)據(jù)庫中所有點的局部密度ρi及局部距離δi決策圖。決策圖如圖5所示。

圖5 決策圖Fig.5 Decision diagram

分析圖5可見， 各指紋點間密度的差異化，定位區(qū)域指紋點局部密度和局部距離有明顯的差異化， 然而并不能直觀地分析判斷出最佳聚類中心。為了更加快捷地確定初始聚類中心及最佳聚類數(shù)，對局部密度ρi及局部距離δi進行歸一化處理，使它們保持在同一個數(shù)量級，然后計算綜合變量γi，繪制綜合決策圖曲線。綜合決策如圖6所示。

圖6 綜合決策圖Fig.6 Comprehensive decision diagram

由圖可見，前7 個指紋點與之后的指紋點間有一個明顯的跳躍，將這前7 個指紋點作為K-means算法的初始聚類中心，同時也就確定最佳聚類數(shù)k=7，再使用K-means 算法完成對指紋數(shù)據(jù)庫的聚類，完成對指紋庫的劃分。

3.3 室內(nèi)定位試驗分析

在完成對指紋庫的聚類劃分之后，為了更好地分析和測試未使用K-means 算法的室內(nèi)定位系統(tǒng)、使用傳統(tǒng)K-means 算法的室內(nèi)定位系統(tǒng)及使用融合聚類算法的室內(nèi)定位進行實時定位測試分析。試驗表明，K-NN 算法取K=5 時，定位精度較高，在此取K-NN 算法在K=5 下對使用3 種算法的定位系統(tǒng)進行定位測試分析，可以得到各定位點的定位誤差、這3 種算法的定位精度及誤差累積曲線，進一步比較3 種算法的性能。

各定位點定位誤差如圖7所示，算法定位精度見表2。比較分析結(jié)果表明，未使用K-means 算法的室內(nèi)定位系統(tǒng)的定位波動較大，定位系統(tǒng)的定位誤差較大，平均定位誤差較大，系統(tǒng)穩(wěn)定性較差；使用K-means 算法的室內(nèi)定位系統(tǒng)的定位誤差在一定程度上減小， 平均定位誤差得到一定程度上減小，但是因為K-means 算法的不穩(wěn)定性導(dǎo)致部分點的定位誤差仍然較大；融合聚類算法在一定程度上改善了使用傳統(tǒng)K-means 算法的室內(nèi)定位系統(tǒng)的性能，定位誤差波動減小，平均誤差進一步減小，標(biāo)準(zhǔn)差最小，定位系統(tǒng)的穩(wěn)定性得到改善。

圖7 各定位點定位誤差Fig.7 Positioning error of each positioning point

表2 算法定位精度Tab.2 Algorithm positioning accuracy

誤差累積曲線，如圖8所示，可以反映定位系統(tǒng)在試驗測試中定位誤差的分布情況，進一步反映定位系統(tǒng)的性能。由圖8可見，使用融合聚類算法的室內(nèi)定位系統(tǒng)定位在1.5 m 內(nèi)的概率， 較未使用K-means 算法和使用傳統(tǒng)K-means 算法的室內(nèi)定位系統(tǒng)提高了約9%，算法的性能得到了較大改善，系統(tǒng)的穩(wěn)定性和定位精度得到進一步提高。

圖8 定位誤差累積曲線Fig.8 Positioning error accumulation curve

4 結(jié)語

在此以藍牙指紋室內(nèi)定位系統(tǒng)為研究對象，使用基于密度峰值的聚類算法與K-means 算法融合，解決了使用傳統(tǒng)K-means 算法初始聚類中心和聚類數(shù)選取隨機性的問題，提高了藍牙指紋室內(nèi)定位的定位精度；對未使用K-means 算法的室內(nèi)定位系統(tǒng)、使用傳統(tǒng)K-means 算法的定位系統(tǒng)，以及使用融合聚類算法的室內(nèi)定位系統(tǒng)使用K 近鄰算法進行定位性能比較，進一步判斷了算法的優(yōu)劣以及定位系統(tǒng)的定位性能。理論分析及試驗結(jié)果表明：使用K-means 算法以及使用融合聚類算法的藍牙指紋室內(nèi)定位系統(tǒng)的定位精度及系統(tǒng)性能，優(yōu)于未使用聚類算法的室內(nèi)定位系統(tǒng)；使用融合聚類的室內(nèi)定位的性能優(yōu)于使用傳統(tǒng)K-means 算法的室內(nèi)定位系統(tǒng)；融合聚類算法有效地改善了藍牙室內(nèi)定位系統(tǒng)的性能和穩(wěn)定性，為高精度室內(nèi)定位系統(tǒng)的搭建提供了有效的解決方案，為以后高精度室內(nèi)定位技術(shù)的普及和發(fā)展奠定了基礎(chǔ)。

我國確定四大舉措促進制造業(yè)穩(wěn)增長

1月3日，2020年首次國務(wù)院常務(wù)會議召開，首個議題聚焦制造業(yè)穩(wěn)增長。會議指出，要用改革辦法和市場化措施，充分激發(fā)市場主體活力，增強發(fā)展動能，促進制造業(yè)穩(wěn)增長。多位專家認(rèn)為，制造業(yè)是國家發(fā)展的根基，是國家可持續(xù)發(fā)展能力的保障，穩(wěn)住制造業(yè)發(fā)展是當(dāng)下中國刻不容緩的任務(wù)之一。

制造業(yè)是經(jīng)濟根基所在

穩(wěn)定制造業(yè)，國務(wù)院常務(wù)會議四項舉措齊發(fā)力。會議明確，促進制造業(yè)穩(wěn)增長一要推進改革創(chuàng)新，二要大力發(fā)展先進制造業(yè)，三要擴大制造業(yè)開放，四要深挖內(nèi)需潛力。

高輝清指出，將促進制造業(yè)穩(wěn)增長作為新年首次國務(wù)院常務(wù)會議的首個議題，表明了中國加大力度促進制造業(yè)發(fā)展的堅定決心。國務(wù)院發(fā)展研究中心宏觀經(jīng)濟研究部研究員張立群也表示，制造業(yè)的發(fā)展非常重要，在經(jīng)濟發(fā)展中起到基礎(chǔ)性的作用。

降本提質(zhì)，激發(fā)活力

在推進改革創(chuàng)新方面，會議提出，大力改善營商環(huán)境，繼續(xù)實施以制造業(yè)為重點的減稅降費措施。同時引導(dǎo)金融機構(gòu)創(chuàng)新方式，緩解中小企業(yè)融資難融資貴。會議決定，推動降低制造業(yè)用電成本和企業(yè)電信資費，全部放開規(guī)模以上工業(yè)企業(yè)參與電力市場化交易。實施差異化信貸政策，鼓勵增加制造業(yè)中長期貸款，股權(quán)投資、債券融資等更多向制造業(yè)傾斜。

內(nèi)外結(jié)合，發(fā)展后勁足

發(fā)展制造業(yè)不僅要發(fā)展外需，也要拉動內(nèi)需，既要開放，也要挖掘內(nèi)部潛力。

在擴大制造業(yè)開放方面，會議指出，要清除影響制造業(yè)開放政策落地的各種障礙，鼓勵企業(yè)面向國際市場參與競爭、開展合作；在深挖內(nèi)需潛力方面，會議明確，完善促進汽車產(chǎn)業(yè)改革發(fā)展的措施。推動適應(yīng)國內(nèi)需求的工業(yè)品增品種、提品質(zhì)、創(chuàng)品牌，豐富消費者選擇。

高輝清認(rèn)為，拉動內(nèi)需要從需求端和供給端分兩步走。“提高國內(nèi)需求，實際上要改變我們的收入結(jié)構(gòu)。收入分配更加公平，就能使大家都能享受到經(jīng)濟增長的成果。”高輝清說，“從供給側(cè)而言，過去我們的制造業(yè)嚴(yán)重依賴于中低端產(chǎn)品，因為過去制造業(yè)的發(fā)展主要是面向國內(nèi)和國際上中低端需求的。但是時代已經(jīng)變化，中國有大量中等收入的消費者，急需相對應(yīng)的中高端產(chǎn)品來滿足他們已經(jīng)轉(zhuǎn)型升級的需求。因此，我們應(yīng)借鑒國外經(jīng)驗，結(jié)合自身國情，從供給側(cè)開始轉(zhuǎn)型，生產(chǎn)更多適合中等收入人群的產(chǎn)品。”

張立群表示，從當(dāng)前宏觀經(jīng)濟運行的角度來看，供大于求的問題非常突出。“只有通過增加有效投資，通過積極地擴大國內(nèi)市場需求，有效增加制造業(yè)企業(yè)的訂單，提高制造業(yè)企業(yè)的開工率，企業(yè)才能夠獲得有利的發(fā)展環(huán)境，才能實現(xiàn)企業(yè)的轉(zhuǎn)型升級和提質(zhì)增效。”

高輝清說，“中國擁有強大的經(jīng)濟增長韌性，未來制造業(yè)發(fā)展有可能出現(xiàn)小幅波動，但不會快速下跌，穩(wěn)增長的后勁仍然是十足的。”

來源：中國青年報