改进K-means聚类的自适应加权K近邻指纹定位算法

邬春明，齐森南

(东北电力大学 现代电力系统仿真控制与绿色电能新技术教育部重点实验室，吉林省 吉林市 132012)

0 引 言

随着通信技术的发展、移动网络的普及和设备的兴起，人们对室内定位服务(indoor positioning service, IPS)的需求逐渐升高[1-2]。定位服务主要依赖无线通信技术，由于Wi-Fi接入点在室内环境中随处可见，并且几乎所有移动设备都具有内置的Wi-Fi接收模块[3-4]。因此，Wi-Fi室内定位技术已成为现今的热点研究课题[5]。

传统室内定位方法，如三边定位法，虽然其算法理论简单，实现方便，但易受到多径效应以及室内环境的影响导致定位精度偏低[6-7]。近年来，国内外学者多采用接收信号强度指示(received signal strength indication，RSSI)作为指纹信息进行室内定位研究[8-9]。相较于传统室内定位方法，指纹定位技术不受信号多径效应的影响，通过对定位场景的特殊信息进行量化并建立数据集，选用合适的定位匹配算法计算出测试点与特征数据库中最相似的采样点，从而确定目标位置。在多种定位匹配算法中，加权K近邻算法(weighted K-nearest neighbor，WKNN)是目前使用频率较高的一种算法，通过参考点相似度加权计算完成测试点定位[10-11]。

影响指纹定位算法定位效果的关键因素在于如何优化离线指纹数据和WKNN算法中最优K值的选择问题。现有研究多采用K-means聚类算法对离线指纹数据进行优化处理，但是聚类效果受初始中心的选择和聚类数目的影响，算法容易陷入局部最优状态，同时容易导致聚类离散点的出现。为解决以上问题，很多学者进行了研究与改进。文献[12]利用像素强度与距离约束准则联合概率最大化的概念来确定初始参考点间的相似度，降低了算法的聚类时间。文献[13]提出一种基于K均值聚类的区域划分方法，该方法采用高氏距离和处理分类值属性离散需求机制，有效地划分大量的众包数据集，并解决了分类属性不明和聚类离散点的问题。与以往基于优化的方法相比，该方法对分区数据的并行处理和计算更加简化，大大缩短了运行时间。文献[14]在K-means聚类距离计算公式中考虑了信号间属性值的影响，更准确地计算出不同对象之间的差异。通过测试不同信号的信号强度，建立每个房间位置的接入点(access point，AP)。实验结果表明，相对于硬聚类算法来说，改进算法的定位精度有所提高。文献[15]根据距离检测方法对离群点进行剔除，通过搜索相邻子库来缩小匹配范围，解决了RSSI易受信号衰变和环境影响的问题。文献[16]将聚类算法与线性回归相结合，通过缩小数据库和聚类中心之间的差异，确定最优聚类大小。以上对离线指纹数据库进行聚类优化处理的研究，对减少定位阶段的指纹匹配时间和提高定位精度有很大作用。但由于Wi-Fi信号的传播具有对称性，在进行指纹数据聚类预处理的过程中容易将参考点RSSI值相近，但实际物理坐标较远的参考点归为一类，造成最终定位结果的偏差。在关于WKNN算法研究的大部分文献中，K值的选择对于定位结果的影响较为关键。文献[17]将曼哈顿距离引入WKNN算法，以区分不同参考节点的影响。同时，通过调整相邻参考节点的权重，选择合适的参考点参与最终的匹配定位，达到提高定位精度的目的。文献[18]通过参考点间离散程度大小，对各参考点赋予不同权值，并对比K=1，2，3，…，7的不同情况下的定位误差，最终选择了固定值K=4。文献[19]选择固定值K=3进行定位实验。文献[20]根据空间信号的衰减规律提出加权欧氏距离，并与参考点的已知位置信息相结合，设计了近似位置距离，通过在3个数据库上进行的定位实验，并与8种不同的定位算法进行了性能比较，表明算法达到了较好的定位精度。但该算法需要反复实验对比来优选匹配参考点数目，且用于实验的指纹数据库需要以大量的离线采集工作量为代价来获取。以上关于WKNN算法K值的选择问题多采用固定值或实验对比取最优的方法，很难做到针对不同测试点选择合理的匹配参考点数。

针对指纹数据K-means聚类预处理效果受聚类离散点影响，导致预处理效果不佳和WKNN算法采用固定K值进行匹配定位的问题，本文采用基于坐标相似度的K-means算法对离线指纹数据库进行预处理，减少聚类过程中出现参考点RSSI值与所属类相近，但实际物理坐标较远的问题。并结合改进的自适应加权K近邻(adaption weighted k-nearest neighbor，AWKNN)算法，根据每个测试点的匹配参考点间实际距离的相似度特性动态选择K值，提高室内定位精度。

1 位置指纹定位算法原理

假设室内定位环境中随机分布着n个AP和m个参考点(reference point，RP)。对每个RP收集n个AP的RSSI值，表示为

RSSIi=(RSSIi1,RSSIi2,…,RSSIin)

(1)

(1)式中:RSSIi代表第i个RP采集到的指纹信息，i=1,2,3,…,m；RSSIin代表第i个RP采集到的第n个AP的RSSI值。将采集到的参考点的RSSI值与相应的物理坐标相结合，形成唯一的位置指纹信息得

FPi=[xi,yi,RSSIi1,RSSIi2,…,RSSIin]

(2)

(2)式中，(xi,yi)表示第i个参考点的坐标。将采集的所有指纹信息按行向量方式存储，构建离线指纹数据库得

(3)

在位置匹配阶段，WKNN算法计算出测试点实时RSSI值与指纹库参考点处RSSI值之间的相似性。选择K个相似度最大的参考点，完成匹配和定位。测试点采集的实时指纹数据为rssi=(rssi1,rssi2,…,rssin)。

相似度大小与RSSI值间的欧氏距离有关，参考点与测试点欧氏距离越近，此参考点相应的权重因子越高[21]。欧氏距离计算式为

(4)

每个参考点的权重因子与RSSI值的欧氏距离的倒数成正比。测试点位置坐标的计算式为

(5)

位置指纹定位算法原理如图1。

图1 位置指纹定位算法原理Fig.1 Principle of fingerprint location algorithm

2 改进K-means的AWKNN定位算法

2.1 基于坐标相似度的K-means算法

在Wi-Fi室内定位环境中，K-means聚类算法多以信号RSSI值之间的欧氏距离作为相似度测量标准。首先从m个参考点中随机选择k个参考点作为聚类计算的初始聚类中心，分别计算剩余m-k个参考点到各聚类中心点的欧氏距离，传统K-means算法中第i个参考点与第k个聚类中心点的RSSI值相似度计算式为[12]

(6)

计算剩余RP到这k个初始聚类中心产生k个欧氏距离值，取这个k个欧氏距离中最小的值，并将这个RP划归到RSSI距离最小的聚类簇中。对于每一个剩余RP进行相同的遍历计算，直到所有的指纹点聚类完成。

聚类完成后需要重新计算这k个类簇的聚类中心，假设第s个类簇中包含M个指纹点，则计算第s个类簇的新聚类中心点处RSSI值表示为

(7)

(7)式中：RSSIs表示新的聚类中心点处的接收信号强度值；RSSIsp表示第s个类簇中第p个参考点的接收信号强度值。

得到新的聚类中心后，再次对每个RP进行聚类计算，直到新的聚类中心点和前一次迭代产生的聚类中心相同或偏差较小时，则可判定K-means聚类结果趋于稳定，聚类中心不会再发生任何变化，确定最终的k个聚类中心以及各聚类簇中所包含的指纹点。指纹数据库经K-means聚类后如图2。

图2 指纹数据库经K-means聚类算法效果Fig.2 Fingerprint clustering effect of K-means algorithm

图2中，经过K-means聚类处理的某一类簇中存在其他类的参考点，聚类效果不理想。主要原因是传统K-means聚类只计算参考点间RSSI值的相似度，导致部分RSSI值相似度高但实际物理距离远的参考点聚为一类，如果这些远距离参考点在匹配过程中被选中，则会导致定位结果误差增大，所以传统的K-means算法需要进一步改进。

对传统K-means算法的改进，考虑在参考点间相似度计算中引入参考点物理坐标相似度，基于坐标相似度的K-means(coordinate similarity k-means，CS-K-means)算法的相似度计算式为

SIM(RSSIi,RSSIj)=

(8)

(8)式中：RSSIik和RSSIjk表示第i个RP和第j个聚类中心采集k个AP的信号强度；(xi,yi)和(xj,yj)表示第i个参考点和第j个聚类中心的物理坐标；SIM(RSSIi,RSSIj)表示参考点与某一聚类中心点的相似度。

参考点间相似度越高，SIM(RSSIi,RSSIj)值越大[22]。CS-K-means算法在对指纹数据进行聚类时，综合考虑参考点RSSI值和物理位置2种因素对聚类效果的影响，通过计算参考点与已有聚类中心的双重相似度，避免将远距离参考点划为非所属类的现象发生。

2.2 自适应WKNN算法

WKNN算法是应用较广的一种匹配定位算法，它充分考虑了与测试点相似度高的参考点在匹配过程中的贡献，对其坐标赋予不同权重进行定位计算，但是WKNN算法需要进行反复试验对比来选择最近邻匹配点数目K。当K值过小，用于定位的匹配点不足，导致定位结果易受单一参考点影响；当K过大，易选中远距离参考点参与定位，造成定位误差增大，这是选用固定K值的弊端。

由于室内定位环境复杂多变，不同测试点周围的参考点分布情况不尽相同，需对每个测试点自适应地选择最优K值，将与测试点相匹配的K个参考点，按相似度由大到小的顺序排列，K个参考点的坐标分别为(x1,y1),(x2,y2),…(xK,yK)。其中，(x1,y1)为相似度最大的参考点坐标，(xK,yK)为相似度最小的参考点坐标。用d1j表示其他K-1个参考点与最大相似度参考点间坐标的欧氏距离得

(9)

(9)式中，j=2,…,K。将所得K-1个坐标的欧氏距离取均值得

(10)

根据得到的均值计算K-1个d1j的标准差σ得

(11)

图3 基于改进K-means聚类的自适应WKNN算法流程图Fig.3 Flow chart of adaptive WKNN algorithm based on improved k-means clustering

根据已取得标准差σ对选中的K个参考点进行二次筛选，删除d1j大于σ的参考点，保留d1j小于或等于σ的参考点作为最后参与定位的最近邻匹配点。自适应WKNN算法的K值等于所保留的参考点数，对于每个测试点，算法根据参考点间实际距离的均值和标准差而动态变化，计算所需K值并得到一组全新的参考点数据。基于改进K-means聚类的自适应WKNN算法流程如图3。

3 实验对比与分析

3.1 实验环境设置

为验证基于坐标相似度的K-means算法的效果，在10 m×10 m×5 m的室内空间中随机分布有6个Wi-Fi热点信号发射源，实验环境内分布有100个参考点。采集指纹数据时忽略室内障碍物以及人员走动的影响，在每个参考点处分别采集6个Wi-Fi热点的RSSI值，将30次的采样值取平均值后存入指纹数据库。室内定位环境如图4。

图4 室内定位环境图Fig.4 Indoor location environment

3.2 改进的K-means算法实验分析

采用传统K-means聚类算法与CS-K-means聚类算法对离线指纹数据库进行聚类处理，根据各参考点RSSI值和实际物理坐标的双重相似度进行聚类，将指纹库分成若干“子区域”，考虑实际定位环境与参考点个数等因素的影响，设定聚类“子区域”数为4，指纹库聚类优化效果如图5。

对比图5a、图5b可知，经过CS-K-means聚类处理后的指纹库，边界分类明显，该算法将被分到其他类中的远距离参考点强制同化为其他类参考点。如图5a所示，假设在定位阶段，测试点的RSSI值与黑色参考点相近，如果处于其他类中的远距离黑色参考点被选中参与匹配定位，将导致定位精度出现严重误差。而在图5b中，将离散的黑色参考点强制划归到其他类之后，再次进行匹配定位时，离散的黑色参考点将不会对最终定位结果产生影响。因离散参考点数目较少，经过坐标相似度处理后的指纹数据库各聚类中心出现轻微偏移，对整体聚类效果影响不大。

图5 指纹库聚类优化效果图Fig.5 Effect diagram of fingerprint databaseclustering optimization

通过改进聚类算法预处理后，离散参考点将不再出现，在线定位过程的计算量明显减小，定位时间也会在一定程度上降低。随机选取20个待定位点在K-means算法和CS-K-means算法处理过的指纹库下进行定位实验，记录定位结果，进行比对分析，定位算法为WKNN，定位结果如图6。

从图6可以看出，在CS-K-means聚类算法优化后的指纹数据库中进行在线定位的误差远小于传统K-means聚类算法，这是因为CS-K-means算法的指纹聚类效果相对集中，排除了离散参考点的干扰，特别是对误差较大的待定位点有很好的改进效果。

图6 2种聚类算法下定位误差图Fig.6 Location errors of two clustering algorithms

3.3 自适应WKNN算法实验分析

为获取定位效果最佳的WKNN算法的对比实验数据，选用3.2节中经改进的K-means聚类处理后的指纹库进行匹配定位，坐标点之间每间隔1 m进行RSSI值采集，共计100个实测参考点。每个参考点对各无线接入点的RSSI值采集30次，采集时间间隔1 min，最终结果取30次采集值的均值，进行定位实验，进而求得WKNN算法中最近邻样本点数目K最优的情况。WKNN算法定位实验中最近邻样本点数目K对定位误差的影响如图7。

图7 最近邻样本点数目K与定位误差关系Fig.7 Relationship between the point number K of the nearest neighbor sample and the positioning error

如图7所示，当K值小于4时，WKNN算法定位误差较大，因为最近邻样本点数目少，使得用于定位的指纹信息不足，定位精度受某一参考点的影响较大；当K值大于5时，由于选择的最近邻样本点数目过多，使得远距离样本点被选中，造成WKNN算法定位误差增大；当K值为4或5时，WKNN算法定位误差相对较小，说明此时的最近邻样本点数目合理，在此实验环境下算法定位效果最好。综上，选择K=4的WKNN算法进行实验对比。

上一节中，在两种不同聚类算法处理过的指纹数据库上，采用WKNN算法对20个测试点进行定位实验。虽然CS-K-means算法的指纹聚类效果相对集中，排除了离散参考点的干扰，使得实验整体定位效果有所提高，但对于部分测试点的定位误差仍然较大。这是因为WKNN算法选用固定K匹配参考点，造成部分测试点定位误差较大。分别选取上一节中定位误差较大的第2，8，10，14，20个待定位点进行分析。表1为这5个待定位点在WKNN 算法下所匹配的参考点坐标以及最终的定位结果。

表1 基于CS-K-means的WKNN算法匹配参考点坐标

WKNN算法分别为上述5个测试点都分配相同数目的参考点，从最终的定位结果来看，WKNN算法定位误差较大。5个测试点定位误差分别为1.87，2.13，2.21，1.74和1.94 m。在基于CS-K-means聚类处理过的指纹数据库基础上使用AWKNN算法对上述5个测试点重新进行定位计算。表2为AWKNN算法匹配参考点坐标值。

表2 基于AWKNN算法匹配参考点坐标

使用AWKNN算法后，这5个测试点的定位误差分别为1.69，1.83，1.97，1.58和1.73 m。定位精度较基于CS-K-means的WKNN算法分别提高了9.6%，14.1%，10.9%，9.2%和10.8%。可见通过自适应方式选择合适的匹配参考点个数对匹配定位精度有一定的提高。

为验证所提AWKNN算法比其他已有算法在定位精度上的优化效果，选用WKNN(K=4)算法、文献[14]中的离散度加权K近邻(discrete degree weighted K-nearest neighbor，DD-WKNN)算法和AWKNN算法对室内空间中随机分布的100个待定位点进行实验。其中，DD-WKNN算法是从离线指纹库中选取K个与在线实测接入点信号强度信息最相似的位置指纹，比较其离散程度，将离散程度小的位置指纹赋予较高的加权系数。定位算法优化结果对比如表3。

表3 3种算法定位误差分析

对表3的实验结果进行分析:WKNN(K=4)平均定位误差较大；DD-WKNN相较于WKNN(K=4)算法定位精度有所提高；AWKNN算法相对于其他两类算法来说，考虑了匹配参考点间实际距离的均值和标准差，对每个测试点自适应选择所需参考点数目，既避免了远距离参考点的选入，又保证了匹配参考点数目的准确性，因此该算法平均定位误差最小，同时提高了匹配定位时间，解决了因使用固定K值所带来的定位精度差的影响。WKNN(K=4)、DD-WKNN和AWKNN 3种定位算法的误差累计分布函数如图8。

从图8的对比结果可以看出：在同等优化指纹库的基础上，WKNN(K=4)算法的误差累积函数收敛最慢；而DD-WKNN算法的定位精度优于WKNN(K=4)算法；AWKNN算法，定位误差最小，误差累积函数收敛速度快，定位精度比其他两种算法分别提高了44%，25%左右。

为充分验证CS-K-means算法的实际应用性，将图4所示的室内空间中随机分布的6个Wi-Fi热点信号发射源增加到8个，在每个指纹采集参考点处进行50次的独立采样，将50次的采样值取平均值后存入指纹数据库。表4为不同信号采集环境下的定位结果。

图8 定位误差累积分布函数图Fig.8 Cumulative distribution function of location error

表4 不同信号采集环境下的定位结果

由表4中的实验对比数据可知，在Wi-Fi热点信号发射源个数相同的情况下，指纹采样次数的增加，有效减小了信号的多径传播效应和同频干扰对Wi-Fi热点RSSI采样值的影响，使得所求采样平均值更接近于信号实际的RSSI值，保证了指纹数据的可靠性，其最终定位时间和定位误差相对较低，定位效果较好；在指纹采样次数相同的情况下，随着室内Wi-Fi热点信号发射源个数的增加，指纹数据更加丰富，定位信息充足，其定位时间和定位误差也相应降低。30个待定位点在4种不同信号采集环境下的定位误差结果，如图9。

从图9可知，随着Wi-Fi热点信号发射源个数和采样次数的增加，待定位点的定位误差波动范围由黑色折线的0.482～2.012 m逐渐降至红色折线的0.258～1.317 m，误差波动范围不断减小，趋于稳定，由此可以说明，CS-K-means算法适用于Wi-Fi信号热点信号源多，信号传播环境复杂的室内空间，该方法能够有效减小或消除室内环境噪声对指纹数据采集带来的不利影响，保证了指纹数据的稳定性和准确性，有效降低室内定位误差，提高定位精度，更具有实用性。

图9 不同信号采集环境下的定位误差图Fig.9 Positioning error diagram under different signal acquisition environments

4 结 论

Wi-Fi技术的迅猛发展为室内定位研究提供了全新的技术支持，针对指纹数据库在K-means聚类中易将远距离参考点聚为一类的问题，研究采用基于坐标相似度的方法进行改进，在计算聚类相似度过程中加入物理坐标参考因素，将远距离参考点划归其他类中。针对WKNN 算法采用固定K值的问题，本研究可以根据每个测试点的匹配参考点间实际距离的相似度特性动态选择K值。所提改进算法仅需使用现有指纹数据，通过在实际定位环境内所进行的大量数据实验表明，改进算法的定位精度比传统的WKNN算法提高了44%左右。基于以上优点，提出的算法将更适用于实际应用。