大型室内无线定位指纹匹配

大型室内无线定位指纹匹配算法研究姓名：逯倩学号：10052108班级：信息05指导教师：廖学文2/33目录1绪论2基于位置指纹的WLAN室内定位系统3聚类分析4传统k-means算法5改进的k-means算法6结论与展望参考文献附录1附录2致谢3/33绪论•研究背景基于位置的服务越来越受到人们的重视全球定位系统不能在室内得到精准的定位无线局域网（WLAN）飞速发展基于位置指纹的WLAN室内定位系统4/33绪论•研究意义在基于位置指纹的WLAN室内定位系统中，定位其实是匹配问题。当数据库中的数据记录非常多，在匹配时就必须计算很多组数据的相似度，花费很多时间。因此，本文的工作是研究学习聚类算法，在匹配前先对数据进行聚类，定位时就可以节减匹配的时间，提高定位的速度。5/33•相关工作K-means算法作为一种经典的聚类算法，广泛应用于多种领域中。但它也存在一些问题，针对这些问题，已有多种方法可以解决。主要改进方向有初始点的选取、k值的确定、时间复杂度的降低；还有将多种算法结合起来，比如将层次聚类和划分聚类结合起来。绪论6/33•基本原理基于位置指纹的室内定位技术的基本原理是终端将待定位点的wifi信号名称及强度值上传给服务器，服务器在数据库中查找与之最相近的数据记录，利用这些记录的位置坐标计算出待定位点的坐标，将坐标返回到客户端。基于位置指纹的WLAN室内定位系统7/33基于位置指纹的WLAN室内定位系统•基本原理该定位方法分为采样和定位两个阶段，如图2-1所示。图2-1基于位置指纹的室内定位方法[11]8/33•系统设计该定位系统包含客户端、服务器端和室内WLAN环境。客户端功能：采集AP到所在点的信号强度，并上传到服务器端；显示地图和目标位置。服务器端功能：接收终端上传的信息；识别并响应终端的定位请求，并能将定位结果返回给客户端。室内WLAN环境的功能是构建室内空间射频信号的分布，提供位置指纹数据库的数据来源。基于位置指纹的WLAN室内定位系统9/33基于位置指纹的WLAN室内定位系统•系统设计该定位系统的软件部分（客户端和服务器端）主要用java语言实现，位置指纹数据库用MySQLWorkbench6.0软件创建。用该软件创建了位置指纹数据库wifi_location，数据库中包含以下6种表，如下图2-3所示。10/33基于位置指纹的WLAN室内定位系统图2-3wifi_location位置指纹数据库组成11/33聚类分析•概念介绍聚类分析就是将一个数据集中的对象分到多个簇或类中，使得数据在同一个簇中相似性高，但是不同簇中的数据相异性高。聚类分析广泛运用于各种领域，如模式识别、图像分割、信息检索等，此外在生物、市场营销、医学等方面也起到了重要作用。12/33聚类分析•算法分类聚类分析的算法一般分为以下几类：（1）基于划分的方法。（2）基于层次的方法。（3）基于密度的方法。（4）基于网格的方法。（5）基于模型的方法。13/33传统k-means算法•算法思想k-means算法的核心思想是将数据集D按某种标准分为指定个数的集合，该算法包含两个阶段：第一阶段是为每个类随机地挑选最开始的类中心；下一阶段是将数据归入最近的类。14/33传统k-means算法•算法仿真及分析该算法的时间复杂度是O(nkt)。输入数据为在主E实际测量的数据集。对于实际测量的数据，当两个点维数不同时，就要选择两点属性相同的部分进行计算。即取采集到的wifi信号中AP地址相同的分量进行距离的计算：2/112pXXdpkjkikij15/33传统k-means算法序号初始值总时间/s簇间距离/簇内距离迭代次数方差125,149,75,497,523,481,138,499,359,495,421,17,267,103,21115.9192.6589712921498.0825249213,323,416,365,318,263,157,61,447,506,441,219,314,218,3014.292.46781564116511.28042033174,7,175,327,375,214,282,527,477,45,83,466,90,206,26115.352.4792505722522.07842134496,200,480,224,228,492,158,268,318,70,253,37,513,271,24933.4982.52734858949519.150443584,217,474,21,442,397,415,148,290,117,107,101,346,355,2519.9692.69721581414510.63370536484,242,230,518,139,235,200,420,13,487,523,423,238,73,10411.9132.63376809817514.0641317335,78,223,294,237,495,273,25,254,144,250,156,55,459,1657.7072.47946164411536.465763856,40,527,94,369,197,334,145,46,498,127,464,494,388,50014.8992.42470602521527.1273591表4-1k=15时不同初始值的k-means算法仿真结果16/33传统k-means算法（a）不同初始值时的簇间距离/簇内距离（b）不同初始值时的方差（c）不同初始值时算法的迭代次数（d）不同初始值时算法的执行时间图4-1k=15时不同初始值的k-means算法仿真结果17/33传统k-means算法k簇间距离/簇内距离方差102.336454861626.6493558132.443320084554.4881762152.566120381512.245103182.728067823466.1378931202.750923848446.2649736表4-2不同k值时k-means算法仿真结果18/33传统k-means算法（a）不同k值时的簇间距离/簇内距离（b）不同k值时的方差图4-2不同k值时k-means算法仿真结果19/33分析得知，传统的k-means算法存在一些缺点或问题：（1）需要提前给定聚类个数k。（2）初始点是随机挑选的。（3）易受噪声或孤立点数据影响。（4）容易产生局部最优解；（5）当输入数据很多时，算法的时间复杂度会因此变得很大。传统k-means算法20/33•初始点的改进该改进算法的核心思想是计算所有点到原点的距离，然后利用这些距离对原始数据点排序。再将排序的点均匀分为指定个数的类，取每一类最中间的点当作初始聚类中心。改进的k-means算法21/33改进的k-means算法k簇间距离/簇内距离方差k-means初始点改进k-means初始点改进102.3364548612.340574893626.6493558617.995101132.4433200842.468859364554.4881762560.8128774152.5661203812.697270912512.245103501.530016182.7280678232.762761609466.1378931451.9240563202.7509238482.733773151446.2649736443.9303783表5-1不同k值下初始点改进与k-means算法仿真结果比较22/33（a）不同k值下的初始点改进与k-means算法的簇间距离/簇内距离比较（b）不同k值下的初始点改进与k-means算法的方差比较图5-2初始点改进与k-means算法仿真结果比较改进的k-means算法23/33改进的k-means算法•初始点的改进初始点改进后的算法比传统k-means算法得到的聚类结果好，证明该算法是有效的，可以挑选较好的初始中心，得到唯一且较优的聚类结果，提高了传统k-means算法的性能。24/33•k值的改进有人提出了一种基于最大聚类个数的k-means算法。该算法的思想是由用户输入参数：门限dis_m，最小聚类数k1，最大聚类数km。当数据点到聚类中心的距离超过门限时，就增加一个以该数据点为中心的类，若增加的类的个数超过km时，需要合并已存在的类中最相似的两个类，使聚类个数不超过km。令k1=10，km=25，门限设为1.7。仿真结果如下表5-2和图5-3。改进的k-means算法25/33序号初始中心聚类个数簇间距离/簇内距离方差1353,509,125,473,493,445,152,523,342,40222.905149371434.611723295,519,451,361,14,182,180,476,349,395222.826237708433.18666043259,377,53,31,454,429,16,151,191,219223.098809837434.28661034139,95,274,164,137,68,512,452,195,119232.994362249404.14842625522,53,35,433,138,222,99,339,128,167252.976290834401.34819116183,221,27,494,26,278,187,231,524,6212.929094134429.19432577219,299,368,165,379,166,37,42,82,295212.88207448449.4906448352,501,95,101,298,43,146,427,524,284242.877387455409.09564569495,436,501,381,151,193,107,218,38,490202.884692539438.2033666表5-2门限为1.7时基于最大聚类数的k-means算法仿真结果改进的k-means算法26/33图5-3门限为1.7时基于最大聚类个数的k-means算法仿真结果（a）不同初始值下得到的聚类数（b）不同初始值下的簇间距离/簇内距离（c）不同初始值下的方差改进的k-means算法27/33改进的k-means算法•k值的改进相比传统k-means算法，该改进算法的优势在于，该算法在计算过程中可以自动地获得较合适的聚类个数，并且聚类结果较好。由于门限的存在，当距离大于门限后该对象会自成一类，这种方法在一定程度上可以减少孤立点数据的影响，提高了聚类的准确度。28/33改进的k-means算法•初始点加k值的改进算法聚类个数初始点簇间距离/簇内距离方差两种结合22342,73,37,158,427,508,239,337,452,42.975239004420.0365471改进k值23-------------2.930455401425.9517325表5-3初始点选取加k值改进与只改进k值的仿真结果比较29/33改进的k-means算法•时间复杂度的改进有作者提出了一种提高的k-means算法，我们计算数据对象到其所属类的当前类中心的距离，若不大于到之前的类中心的距离，数据对象依然属于之前所属的类；否则，我们就得求所有类中心到此对象的距离，归到最近的类中。30/33改进的k-means算法•时间复杂度的改进算法执行时间簇间距离/簇内距离方差传统17.74752.555612669522.3001397时间复杂度改进算法17.572952.605510138520.3724691表5-4改进时间复杂度的算法和传统k-means算法的仿真结果比较31/33结论与展望本文介绍了基于位置指纹的WLAN室内定位系统，为了减少匹配时间，我们研究了聚类算法。主要对k-means算法进行分析，针对其问题，提出了三种改进算法，提高了传统算法的性能。对于时间复杂度的改进算法，是我们未来要深入研究的方向。此外，我们研究的算法还是聚类算法的一小部分，而