基于融合聚類的藍牙室內定位系統算法優化

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

（西安工業大學 電子信息工程學院，西安710021）

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

1 基于K-means 的藍牙場強室內定位算法

1.1 K-means 藍牙場強室內定位系統

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

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

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

1.2 K-means 聚類算法

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

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

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

輸入指紋數據庫；

輸出最終聚類結果。

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

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

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

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

1.3 指紋定位算法

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

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

2 基于K-means 的室內定位算法優化

K-means 算法自身存在天然的缺陷導致定位系統總不是處于最優狀態，初始聚類中心選取的隨機性和聚類數設定的經驗性，導致對指紋庫的聚類往往不是最優聚類，使得定位系統缺乏穩定性。針對K-means 算法的這一缺陷， 在此采用了基于融合聚類的指紋定位算法室內定位系統。融合聚類流程如圖2所示。

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

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

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

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

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

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

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

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

DPC 算法流程描述如下：

輸入指紋數據庫；

輸出最終聚類結果，最佳聚類數k。

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

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

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

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

2.2 融合聚類算法

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

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

3 算法仿真與試驗分析

3.1 試驗環境介紹

室內定位試驗在通信學科實驗室中進行，在試驗環境中對iBeacon 基站進行合理的布局。試驗環境及iBeacon 基站布局如圖4所示， 試驗環境參數見表1。

圖4 試驗環境及iBeacon 布局Fig.4 Experimental environment and iBeacon layout

表1 試驗環境參數Tab.1 Experimental environment parameters

3.2 基于密度峰值的聚類算法應用

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

圖5 決策圖Fig.5 Decision diagram

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

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

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

3.3 室內定位試驗分析

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

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

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

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

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

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

4 結語

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

我國確定四大舉措促進制造業穩增長

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

制造業是經濟根基所在

穩定制造業，國務院常務會議四項舉措齊發力。會議明確，促進制造業穩增長一要推進改革創新，二要大力發展先進制造業，三要擴大制造業開放，四要深挖內需潛力。

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

降本提質，激發活力

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

內外結合，發展后勁足

發展制造業不僅要發展外需，也要拉動內需，既要開放，也要挖掘內部潛力。

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

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

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

高輝清說，“中國擁有強大的經濟增長韌性，未來制造業發展有可能出現小幅波動，但不會快速下跌，穩增長的后勁仍然是十足的。”

來源：中國青年報