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

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

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

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

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

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

6、维数不同时，就要选择两点属性相同的部分进行计算。即取采集到的wifi信号中AP地址相同的分量进行距离的计算：2/112pXXdpkjkikij15 传统k-means算法 表4-1 k=15时不同初始值的k-means算法仿真结果16 传统k-means算法（a）不同初始值时的簇间距离/簇内距离 （b）不同初始值时的方差 （c）不同初始值时算法的迭代次数 （d）不同初始值时算法的执行时间 图4-1 k=15时不同初始值的k-means算法仿真结果17 传统k-means算法 表4-2 不同k值时k-means算法仿真结果18 传统k-means算法（a）不同k值时的簇间距离/簇内距离 （b）不

7、同k值时的方差图4-2 不同k值时k-means算法仿真结果19 分析得知，传统的k-means算法存在一些缺点或问题：（1）需要提前给定聚类个数k。（2）初始点是随机挑选的。（3）易受噪声或孤立点数据影响。（4）容易产生局部最 优解；（5）当输入数据很多时，算法的时间复杂度会因 此变得很大。 传统k-means算法20 初始点的改进 该改进算法的核心思想是计算所有点到原点的距离，然后利用这些距离对原始数据点排序。再将排序的点均匀分为指定个数的类，取每一类最中间的点当作初始聚类中心。 改进的k-means算法21 改进的k-means算法表5-1 不同k值下初始点改进与k-means算法仿真结

8、果比较22（a）不同k值下的初始点改进与k-means算法的簇间距离/簇内距离比较（b）不同k值下的初始点改进与k-means算法的方差比较图5-2 初始点改进与k-means算法仿真结果比较 改进的k-means算法23 改进的k-means算法 初始点的改进 初始点改进后的算法比传统k-means算法得到的聚类结果好，证明该算法是有效的，可以挑选较好的初始中心，得到唯一且较优的聚类结果，提高了传统k-means算法的性能。24 k值的改进 有人提出了一种基于最大聚类个数的k-means算法。该算法的思想是由用户输入参数：门限dis_m，最小聚类数k1，最大聚类数km。当数据点到聚类中心的距

9、离超过门限时，就增加一个以该数据点为中心的类，若增加的类的个数超过km时，需要合并已存在的类中最相似的两个类，使聚类个数不超过km。 令k1=10，km=25，门限设为1.7。仿真结果如下表5-2和图5-3。 改进的k-means算法25表5-2 门限为1.7时基于最大聚类数的k-means算法仿真结果 改进的k-means算法26图5-3 门限为1.7时基于最大聚类个数的k-means算法仿真结果（a）不同初始值下得到的聚类数 （b）不同初始值下的簇间距离/簇内距离（c）不同初始值下的方差 改进的k-means算法27 改进的k-means算法 k值的改进 相比传统k-means算法，该改进

10、算法的优势在于，该算法在计算过程中可以自动地获得较合适的聚类个数，并且聚类结果较好。由于门限的存在，当距离大于门限后该对象会自成一类，这种方法在一定程度上可以减少孤立点数据的影响，提高了聚类的准确度。28 改进的k-means算法 初始点加k值的改进 表5-3 初始点选取加k值改进与只改进k值的仿真结果比较29 改进的k-means算法 时间复杂度的改进 有作者提出了一种提高的k-means算法，我们计算数据对象到其所属类的当前类中心的距离，若不大于到之前的类中心的距离，数据对象依然属于之前所属的类；否则，我们就得求所有类中心到此对象的距离，归到最近的类中。30 改进的k-means算法 时间复杂度的改进表5-4 改进时间复杂度的算法和传统k-means算法的仿真结果比较31结论与展望 本文介绍了基于位置指纹的WLAN室内定位系统，为了减少匹配时间，我们研究了聚类算法。主要对k-means算法进行分析，针对其问题，提出了三种改进算法，提高了传统算法的性能。 对于时间复杂度的改进算法，是我们未来要深入研究的方向。此外，我们研究的算法还是聚类算法