基于改进模糊核聚类的室内定位方法研究-杜凯颖.pdf

《基于改进模糊核聚类的室内定位方法研究-杜凯颖.pdf》由会员分享，可在线阅读，更多相关《基于改进模糊核聚类的室内定位方法研究-杜凯颖.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、42 测控技术)2018年第37卷第2期基于改进模糊核聚类的室内定位方法研究杜凯颖，张为公，王东(东南大学仪器科学与工程学院，江苏南京210096)摘要：针对室内定位中，WiFi位置指纹法存在的定位实时性和精度的问题，提出一种基于改进模糊核聚类(KFCM)和加权K近邻(WKNN)结合的室内定位方法，旨在降低定位时间和改善定位精度。首先利用快速搜索和发现峰值聚类(CFSFDP)确定聚类数目和初始聚类中心，克服KFCM算法对初始聚类中心选取的依赖性而导致聚类结果不稳定的缺点，在此基础上，采用WKNN进行定位匹配，提高定位精度。实验表明，所提出方法相较于无聚类的室内定位方法，能在保证一定精度的前提下

2、，减少定位计算量和时间。此外，将所提出方法与基于K均值、KFCM和CFSFDP的方法进行实验对比，结果显示该方法具有更好的聚类效果和定位精度。关键词：室内定位；模糊核聚类；加权K近邻；快速搜索和发现峰值聚类中图分类号：TP391 文献标识码：A 文章编号：10008829(2018)02004205Research on Indoor Localization Based on Improved Kernel Fuzzy CmeansDU Kaiying，ZHANG Weigong，WANG Dong(School of Instrument Science&Engineering，South

3、east University，Nanjing 210096，China)Abstract：An indoor positioning method based on kernel fuzzy Cmeans(KFCM)and weighted Knearestneighbor(WKNN)is proposed to reduce the positioning time and improve the positioning accuracyFirstly，thenumber of clusters and the initial cluster center are determined b

4、y clustering by fast search and find of densitypeaks(CFSFDP)to overcome instability，and then WKNN is used for location matching to improve accuracyThe experimental results show that compared with non-clustering indoor localization，the proposed method canreduce the computation time with satisfied acc

5、uracyIn addition，compared with the method based on K-means，KFCM and CFSFDP，the proposed method has better clustering effect and positioning accuracyKey words：indoor location；kernel fuzzy C-means；weighted K-nearest neighbor；clustering by fast search andfind of density peaks随着人口老龄化问题的日益扩大，老年人，尤其是独居老人的

6、健康与安全问题受到政府及社会的普遍关注，并由此带动了面向老人的智能监控与救护方法的发展。在智能监护系统中，无缝化位置信息监测是保障老人安全的关键技术，它需要在室内和室外都实现高精度定位。在室外，GPS等室外定位技术已经成熟，基本解决了室外空间下的准确定位问题；而在室内，因信号遮挡严重，常规的卫星定位方法无法正常使用。因此，本文提出了一种基于WiFi信号的室内定位解决方案。相比于其他无线技术，WiFi信号因其覆盖范围广，可用于通信等优点，在室内定位和跟踪中备受关收稿日期：20170516作者简介：杜凯颖(1993一)，女，陕西西安人，硕士研究生，主要研究方向为室内定位。注。目前WiFi室内定位大

7、多采用基于信号接收强度(Received Signal Strength Indication，RSSI)的位置指纹法o，离线阶段将RSSI看作“指纹”映射到特定位置，并作为指纹数据存人数据库；定位阶段将实时采集的RSSI与数据库进行匹配，从而得出目标位置。该方法的精度主要依赖指纹数据的密度，大量指纹数据的采集耗时耗力，且计算开销大，影响定位实时性。针对上述问题，文献2首次提出采用聚类分簇来改善定位性能，除了能免去人工划分类的工作量，还能减少定位时间，提高定位效率。基于聚类分析的思想，笔者提出一种改进模糊核聚类(Kernel Fuzzy C-means，KFCM)3 o与加权K近邻(Weigh

8、ted Knearest Neighbor，WKNN)L4j结合的室内定位方法，并运用密度峰值改进KFCM，以提高聚类的万方数据基于改进模糊核聚类的室内定位方法研究 43稳定性和精度。此方法具有以下优点：对采集的位置指纹先做聚类，定位时确定所在类簇后再进行定位解算，缩短了定位时间。因KFCM算法需预先知道聚类数目，提出基于快速搜索和发现密度峰值(Clustering by Fast Search and Find of Density Peaks，CFSFDP)o改进此算法，在自动确定聚类数目的同时初始化聚类中心，克服因随机化聚类中心易陷入局部最优，从而导致聚类结果不同的缺陷，保证系统的可靠性

9、和稳定性。采用K近邻计算局部密度代替CFSFDP中的截断距离，使所提算法适用于任意密度分布的样本集。1 基于改进KFCM的室内定位方法11聚类算法分析基于聚类的位置指纹法中，聚类结果的质量直接影响到在线阶段的精度，因此需选择一种适用于信号强度特征且效果好的聚类算法。目前室内定位中常用的聚类方法有：近邻传播(Affinity Propagation，AP)J、基于密度的带噪声数据应用的空间聚类(DensityBased Spatial Clustering of Applications with Noise，DB-SCAN)7 o、K均值(Kmeans)o等。AP算法无需事先指定聚类个数，但不

10、能发现任意形状的簇，且实现复杂。DBSCAN算法在合理选择参数的条件下，能快速发现含噪声空间中任意形状的簇，但参数设置缺乏理论依据。Kmeans算法实现简单，具有良好的聚类效果，但聚类数目K需事先设定，聚类结果严重依赖初始聚类中心，且对离群点和孤立点很敏感。针对Kmeans的缺陷，文献9提出基于KFCM的室内定位方法，有效解决了K-means对噪声和野值极其敏感的问题。不过依然存在问题：需人为确定聚类数目；随机选取初始聚类中心，会造成选取点不同，则聚类结果不同的问题，这种对于初始聚类中心的依赖性会导致聚类结果的不稳定。2014年6月Alex Rodrigue提出了CFSFDP算法，能自动确定聚

11、类个数和聚类中心，快速发现任意形状的密度峰值点，并具有很好的抗噪性。然而，CFSFDP在数据样本集较小时受截断距离的影响较大。针对上述单一聚类算法在聚类结果上表现出的不足，提出一种KFCM和CFSFDP结合的聚类算法。利用CFSFDP选取聚类数目和聚类中心，再运用KFCM进行迭代聚类，弥补KFCM依赖初始聚类中心的缺陷。12 KFCM算法KFCM算法描述如下：X=，z：，戈。代表rt个数据样本集，xRp；c为聚类数目；秽i(i=1，2，c)为第i个聚类的中心；tt语(i=1，2，C；后=1，2，rt)是第k个样本对第i类的隶属度。KFCM的目标函数为，。(U,v)=uT,o币(X,k)一咖(”

12、i)o 2 (1)算法步骤如下：(1)设定聚类数目c和模糊度参数m。(2)初始化c个聚类中心秽i。(3)重复以下运算，直到各个样本的隶属度稳定：用当前的聚类中心根据式(2)更新隶属度。1K(x，x)+K(vi，口。)2K(xI，i)17一1lK(x)+K(vj，q)一2K(x。，vj)”(2)用当前的聚类中心和隶属度根据式(3)更新各个聚类中心。um。霞(Vi)菇。=生一(3)u：露(钆”。)高斯核函数为K(石，y)=exp(一(髫一)，)2202) (4)对于高斯核函数，有：露(x。，口。)=K(x。，q) (5)对式(1)中的q求导，令其等于0，可得式(5)，具体推导在此不做详述。13 C

13、FSFDP算法以下介绍如何基于CFSFDP的思想得到聚类数目和初始化聚类中心，其中，重新定义局部密度以使算法适用于任意密度分布的样本。具有P维属性的两个样本石。=(戈戈吐，戈，)，戈j=(勺。，豫，)间的欧式距离为d(x。，巧)=V(Xil一)2+(戈。一勘)2+(石，一)2(6)CFSFDP算法中，首先定义了样本点戈。的局部密度Pi，它表示以截断距离d。为半径的区域中样本点的个数：P。=Zx(d。一d(zi，) (7)式中，小，=兰截断距离d，选用的是全局截断距离，对于样本集较小、密度不均匀的情况聚类结果较差。因此，重新定义局部密度Pi为P。=exp(一d(x。，勺) (8)由式(8)可知，

14、样本点戈。到其K近邻的距离越小，万方数据44 测控技术2018年第37卷第2期其密度值P。越大。将密度计算范围缩小为样本的K个近邻，更能反映样本点的局部信息。然后，定义6。为样本点戈。与高密度点间的距离，它表示所有局部密度大于戈。的样本点中，距戈：最近的点与z，之间的距离，则6。=min(d(x。，x，)，iJ (9)，：“Pi特别是当样本点石，具有最大密度时：6。=max(d(戈。，一) (10)J再根据P值和6值计算出两者综合考虑的量y，来确定聚类数目和聚类中心：7。=p6。i=1，2，n (11)显然，7值越大，越有可能是聚类中心，因此对y做降序排列，将排列好的y在坐标系上画出来。可以看

15、到从非聚类中心到聚类中心时，y值有明显的跳跃，从而得出聚类数目和聚类中心。14 KFCMCFSFDP算法输入：待聚类的n个指纹数据。输出：满足目标函数的C个类。KFCMCFSFDP算法流程如图1所示。计算样本两两问的欧式距离d“，一)计算样本点的密度p计算6计算y将降序排列后的y在坐标系中画出，当y值有明显的跳跃时即可确定聚类数目和聚类中心用当前的聚类中心根据式(2)更新隶属度用当前的聚类中心和隶属度根据式(3)更新各个聚类中心重塑变化小型亟刘i图1 KFCMCFSFDP算法流程15 WKNN定位匹配算法采用较为常用的WKNN算法计算最终的定位结果。其中，加权因子考虑到了距离更近的近邻更应该决

16、定最终的位置，因此WKNN较KNN更合适。选择距离平方的倒数作为权重，目标位置(戈，Y。)为(x)=toi(儿)1D；o)i 2F一(1D；)式中，D。为目标与数据库中第i个参考点RSSI间的欧式距离。2实验设计及结果分析21 实验环境为评估所提方法的性能，选择东南大学中心楼三楼西侧作为实验场地进行实验，面积为50 in20 ITI，平面图如图2所示。图2东南大学中心楼三楼西侧平面示意图数据采集设备为红米Note2手机，Android 50版本，实验采用学校在走廊统一部署的SSID为“seuwlan”的接人点(共49个)。使用基于安卓开发的LIPS软件采集位置指纹数据，离线阶段共采集了96个位

17、置点(如图3所示)，WiFi信号扫描间隔为1 S，每个位置采集60组数据，共9660=5760个数据。采集中发现，某些位置的某些接入点信号缺失，缺失处用默认值一1 10代替。在线定位阶段，在实验区域中任意选取了45个测试点，每个测试点采样30次，总共得到4530=1350个测试数据。计算每个测试数据与离线数据库中聚类中心的距离，将测试数据划为距离最近的那一类。若同一位置的分类结果相同则认为聚类正确，不同则认为聚错，由此统计聚类结果的正确率。数据处理，聚类算法和定位匹配均在CPU为IntelCore i3，内存为4 GB的Toshiba笔记本电脑安装的Matlab 2016上进行。l ： ： ：

18、 ：4 卫 12。319罗：325一： ： 生 323l ： ： ：一 间1 lo0 ，J 、r N LI336 楼 1334 330梯图3离线阶段样本数据位置(12) 22聚类数目和初始聚类中心的确定首先利用式(9)求得各样本点的局部密度，其中，(13) 对于K近邻中的K值，此处选取K：210进行实验。实验发现，K值对于选取类簇中心没有影响。虽然K万方数据基于改进模糊核聚类的室内定位方法研究 45值对样本点的局部密度有一定影响，但是对于类簇中心，它是分布在每个类簇最密集的区域，因此K值对局部密度的相对大小影响较小，对选取聚类中心并没有什么影响。将离线数据经算法步骤步骤，可以得到图4所示的P一

19、6决策图和降序排列y值示意图，从决策图并不能清楚地判断出聚类中心与非聚类中心，但是从y值示意图可以看到，从第3个到第4个有明显的跳跃，因此聚类数目定为3，初始的聚类中心选择降序排列后前3个y值所对应的样本点。、cf4i J】：寸#I 4，j一6决策I冬1不1j 7 I：肇i丰l FlJ纠23 KFCM的参数确定KFCM中有两个需要人为确定的参数，分别为高斯核or和模糊度m。or为宽度参数，控制函数的径向作用范围，模糊度m“1，+，但是m过大时，聚类效果并不好。分别选取or=15，31，步长为2，m=15，31，步长为02，进行实验判断聚类效果。在本实验环境下，or=27，m=25时聚类效果最佳

20、。表1给出部分or和m取值时的聚类正确率R。表1不同or值和m值下的聚类正确率高斯核模糊度 聚类正确率 高斯核 模糊度 聚类正确率o- m 肜 口 m RI5 923 15 96220 25 921 27 25 97331 934 31 96315 944 15 96125 25 947 3l 25 96731 946 31 96824聚类结果分析图5为测试数据经CFSFDP-KFCM聚类的结果示意图。不同形状和灰度表示不同类别，从图中可以看出，部分处于类边界的测试点被分错类，造成聚类结果错误。实验发现，用CFSFDP确定初始聚类中心后，不会陷入局部最优而导致类别划分结果不同，使KFCM的聚类

21、结果变得稳定可靠。由表1可以看出，在此实验环境下，所提出的CFSFDPKFCM算法的聚类正确率可以达到97左右。为了评估所提出的方法的优越性，另外采用Kmeans、KFCM和CFSFDP算法进行多次实验，取多次实验聚类正确率的平均值，结果如表2所示，其中CFSFDP算法中采用截断距离作为局部密度。捶，：s测蒿 313 12 319一1 lj二一：一jk。_L。kj j 、J L l318 336 楼 r 330梯表2 4种聚类算法结果比较 单位：算法 聚类正确率肜 算法 聚类正确率肜CFSFDPKFCM 973 KFCM 884Kmeans 867 CFSFDP 826表2表明本文所述方法较其

22、他3种算法有明显精度优势。其中，Kmeans和KFCM的准确度相差不大，KFCM算法较之于Kmeans的优势体现不明显。对于本实验密度分布不均的数据样本集，CFSFDP算法因局部密度由全局截断距离计算得出，造成聚类效果较差。25定位时间及误差分析无聚类时，每进行一次定位，测试点需与数据库中全部样本比较计算出位置，添加聚类后，定位时只需与离线数据库对应类中的样本进行WKNN匹配，确定位置坐标。表3为5种方法的定位结果，其中WKNN算法中的K值依经验取K=4。实验显示，非聚类定位的精度最高，但聚类定位的平均定位时间比非聚类降低了约50。在聚类定位中，CFSFDPKFCM+WKNN方法相较于其他3种

23、聚类定位，具有最优定位精度，其定位误差最大为628 m，平均误差为163 m，其中90的定位误差在4 m以内，83的定位误差在3 m以内，此结果最接近非聚类定位的定位精度。由此可见，所提出的定位方法能够在保证适当精度的前提下，提高定位效率。表3几种定位方法的结果比较万方数据46 测控技术)2018年第37卷第2期3 结束语针对WiFi位置指纹法中定位精度和数据量大影响定位实时性的问题，在聚类分析思想的基础上，提出一种基于改进KFCM与WKNN结合的室内定位方法，在降低定位计算开销的同时提高定位精度。为改进KFCM易陷入局部最优的不足，采用CFSFDP确定KFCM算法中的聚类数目和初始聚类中心，

24、使聚类结果更加稳定，并在CFSFDP中利用K近邻距离作为局部密度，使此算法适用于任意密度分布的样本集，最后通过WKNN定位匹配算法进一步提高精度。经过实验验证，所提出的基于CFSFDP改进KFCM聚类的室内定位方法，对比基于Kmeans、KFCM和CFSFDP的定位方法，能够在保证与无聚类定位具有相近精度的基础上，减少计算量，在一定程度上提高了定位性能。参考文献：1 Moustafa Amin Abdel Azim Yousief Abdel RehimHorus：AWLANbased Indoor Location Determination SystemZUniversity of Mar

25、yland at College Park，20042Swangmuang N，Krishnamuahy P VOn clustering RSS fingerprints for improving scalability of performance predictionof indoor positioning systemsCFirst ACM InternationalWorkshop on Mobile Entity Localization and Tracking inGPSLess Environments2008：6l一663456789Zhang L，Zhou W D，J

26、iao L CKernel clustering algorithmJChinese Journal of Computers，2002，25(6)：587590Dudani S AThe Distanceweighted Knearestneighbor ruleJIEEE Transactions on Systems ManCybernetics，1976，SMC-6(4)：325327Rodriguez A，Laio AClustering by fast search and find ofdensity peaksJScience，2014，344(6191)：14921496Ti

27、an Z S，Tang X M，Zhou M，et a1Fingerprint indoor positioning algorithm based on affinity propagation clusteringJEURASIP Journal on Wireless Communications andNetworking，2013(1)：272Ester M，Kriegel H P，Sander J，et a1A densitybased algo-rithm for discovering clusters in large spatial databases withnoiseC

28、Proceedings of 2nd International Conference onKnowledge Discovery and Data Mining1996Bai S D，Wu TAnalysis of Kmeans algorithm on fingerprintbased indoor localization systemf C2013 5th IEEE Inter-national Symposium on Microwave，Antenna，Propagation andEMC Technologies for Wireless Communications2013：4

29、448杨慧琳，黄智刚，刘久文，等基于核模糊c均值指纹库管理的WIFI室内定位方法J浙江大学学报(工学版)，2016，50(6)：11261133口(上接第41页)改进型的旋转变压器解码算法的滞后时间小于l斗s，占用FPGA的内部资源少。在保证测量精度和测量误差的前提下，避免直接对7r2附近的角度进行测量，通过角度变换和改进后的CORDIC算法来提高测量精度，降低测量误差。从数据输入到角度值输出均是在FPGA内部通过硬件描述语言来实现的，有效增强了系统的抗干扰能力，能够完全匹配旋转变压器所应用的各种对环境要求较高的场合，具有非常好的应用前景。参考文献：1 Chen J Y，Lei Y W，Pen

30、g Y XConfigurable floatingpointF兀accelerator on FPGA based multiplerotation CORDICJChinese Journal of Electronics，2016，25(6)：1063一10702Chung R L，Zhang Y Q，Chen S L Fully pipelined CORDIC-based inverse kinematic FPGA design for biped robotsJElectronics Letters，2015，51(16)：124112433 Shukla R，Ray K CLO

31、w latency hybrid CORDIC algorithm45678910JIEEE Transactions on Computers，2014，63(12)：30663078Lee M W。Yoon J H，Park JReconfigurable CORDIC-basedlowpower DCT architecture based on data PriorityjIEEETransactions on Very Large Scale Integration(VLSI)Systerns，2014，22(5)：10601068郭来功，欧阳名三，蔡俊一种新的快速并行结构的优化CO

32、RDIC算法J电视技术，2012，36(17)：7678王敏，薛忠杰基于改进cordic算法的NCO设计J电视技术，201l，35(1)：3033张朝柱，韩吉南，燕慧智高速高精度固定角度旋转CORDIC算法的设计与实现J电子学报，2016，44(2)：485490宋晓梅，朱辉，王文静基于CORDIC的旋转变压器解码算法研究J电子测量技术，2010，33(6)：3943张勇，马金元基于CORDIC算法的360。角度传感器的设计J工矿自动化，2009，37(1)：2629刘小宁，谢宜壮，陈禾，等CORDIC算法的优化和实现J北京理工大学学报，2015，35(11)：11641170冯文光，刘诗斌改进的MVRCORDIC算法在磁航向测量中的应用J测控技术，2009，28(6)：4042口万方数据