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

1、大型室内无线定位指纹匹配算法研究 姓名：逯倩 学号：10052108 班级：信息05 指导教师：廖学文2/33 目录目录 1 绪论 2 基于位置指纹的WLAN室内定位系统 3 聚类分析 4 传统k-means算法 5 改进的k-means算法 6 结论与展望 参考文献 附录1 附录2 致谢3/33 绪论绪论 研究背景 基于位置的服务越来越受到人们的重视 全球定位系统不能在室内得到精准的定位 无线局域网（WLAN）飞速发展 基于位置指纹的WLAN室内定位系统4/33 绪论绪论 研究意义 在基于位置指纹的WLAN室内定位系统中，定位其 实是匹配问题。当数据库中的数据记录非常多，在匹配 时就必须计算

2、很多组数据的相似度，花费很多时间。因 此，本文的工作是研究学习聚类算法，在匹配前先对数 据进行聚类，定位时就可以节减匹配的时间，提高定位 的速度。 5/33 相关工作 K-means算法作为一种经典的聚类算法，广泛应用于多种领域中。但它也存在一些问题，针对这些问题，已有多种方法可以解决。 主要改进方向有初始点的选取、k值的确定、时间复杂度的降低；还有将多种算法结合起来，比如将层次聚类和划分聚类结合起来。 绪论绪论6/33 基本原理 基于位置指纹的室内定位技术的基本原理是终端将待定位点的wifi信号名称及强度值上传给服务器，服务器在数据库中查找与之最相近的数据记录，利用这些记录的位置坐标计算出待

3、定位点的坐标，将坐标返回到客户端。 基于位置指纹的基于位置指纹的WLAN室内定位系统室内定位系统7/33 基于位置指纹的基于位置指纹的WLAN室内定位系统室内定位系统 基本原理 该定位方法分为采样和定位两个阶段，如图2-1所示。 图2-1 基于位置指纹的室内定位方法118/33 系统设计 该定位系统包含客户端、服务器端和室内WLAN环境。 客户端功能：采集AP到所在点的信号强度，并上传到服务器端；显示地图和目标位置。 服务器端功能：接收终端上传的信息；识别并响应终端的定位请求，并能将定位结果返回给客户端。 室内WLAN环境的功能是构建室内空间射频信号的分布，提供位置指纹数据库的数据来源。 基于

4、位置指纹的基于位置指纹的WLAN室内定位系统室内定位系统9/33 基于位置指纹的基于位置指纹的WLAN室内定位系统室内定位系统 系统设计 该定位系统的软件部分（客户端和服务器端）主要用java语言实现，位置指纹数据库用MySQL Workbench 6.0软件创建。用该软件创建了位置指纹数据库wifi_location，数据库中包含以下6种表，如下图2-3所示。 10/33 基于位置指纹的基于位置指纹的WLAN室内定位系统室内定位系统 图2-3 wifi_location位置指纹数据库组成11/33聚类分析 概念介绍 聚类分析就是将一个数据集中的对象分到多个簇或类中，使得数据在同一个簇中相似性

5、高，但是不同簇中的数据相异性高。 聚类分析广泛运用于各种领域，如模式识别、图像分割、信息检索等，此外在生物、市场营销、医学等方面也起到了重要作用。12/33聚类分析 算法分类 聚类分析的算法一般分为以下几类：（1）基于划分的方法。（2）基于层次的方法。（3）基于密度的方法。（4）基于网格的方法。（5）基于模型的方法。13/33 传统k-means算法 算法思想 k-means算法的核心思想是将数据集D按某种标准分为指定个数的集合，该算法包含两个阶段：第一阶段是为每个类随机地挑选最开始的类中心；下一阶段是将数据归入最近的类。 14/33 传统k-means算法 算法仿真及分析 该算法的时间复杂度

6、是O(nkt)。输入数据为在主E实际测量的数据集。对于实际测量的数据，当两个点维数不同时，就要选择两点属性相同的部分进行计算。即取采集到的wifi信号中AP地址相同的分量进行距离的计算：2/112pXXdpkjkikij15/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.29

7、2.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,13

8、9,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-1 k=15时不同初始值的k-means算法仿真结果16/33 传统k-means算法（a）不同初始值时的簇间距离

9、/簇内距离 （b）不同初始值时的方差 （c）不同初始值时算法的迭代次数 （d）不同初始值时算法的执行时间 图4-1 k=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值时的方

10、差图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初始点改进

11、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算法的

12、簇间距离/簇内距离比较（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。当数据点到聚类中心的距离超过门限时，就增加一个以该数据点为中心的类，若

13、增加的类的个数超过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.826237708433377,53,31,454,429,16,151,191,219223.098809837434.286

14、61034139,95,274,164,137,68,512,452,195,119232.99436224940453,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

15、.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算法，该改进算法的优势在于，该算法在计算过程中可以自动地获得较合适的聚类个数，并且聚类结果较好。

16、由于门限的存在，当距离大于门限后该对象会自成一类，这种方法在一定程度上可以减少孤立点数据的影响，提高了聚类的准确度。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室内定位系统，为了减少匹配时间，我们研