本发明涉及信息技术领域，尤其涉及一种半监督的基于流形学习的位置指纹库构建方法。
背景技术：
室外环境是多变的，人、车、物体等随意运动，直接利用无线信号进行目标位置定位存在一定的困难。节点之间传输数据会造成大量的多径传播、多址干扰以及非视距传播现象，这些因素严重影响了目标定位技术的精度。除此之外，由于物联网大多数设备放在人烟稀少、环境恶劣的地方，采用人工采集的方式构建位置信息库是不太现实的，采用距离定位的方式误差太高。因此，问题是如何构建网络信号指纹库进而定位节点位置。由于当前带有位置标签的数据很少，该因素会在很大层面影响定位精度。
技术实现要素：
本发明旨在提供一种半监督的基于流形学习的位置指纹库构建方法，采用标签数据的地理位置信息与无标签数据的时间相关性，利用流形学习的方法对大量无标签数据进行标记，实现位置指纹库的构建，解决定位数据库构建需要大量人力物力的问题。
本发明结合低功耗广域网相邻节点信号的相似性特征，通过流形学习获取大量易采集的无标签数据(没有包含位置信息)的时空关联特征，结合少量的标签数据，实现位置指纹库的构建，解决位置标签数据数量少所导致定位不准的问题。
本发明提出的基于流形学习的位置指纹库构建的思路如下：
(1)大量无标记数据的预处理。信号特征与物理空间的准确映射是保证定位系统精度的首要条件。由于无线信号传播会受到各种干扰和随机因素的影响，因此，在信息采集过程，由于信号波动的原因，导致所采集到的信号具有一定误差，因此，不能将采集到的数据作为定位特征数据，需要对采集的数据进行优化。本发明利用物理空间相同或者相近位置上的无线信号强度具有相似性的特点，基于大量具有时间戳的无标签数据，采用时空数据局部相似性的原理，剔除噪音数据，得到可信数据点。
(2)空间定位特征的优化选择。传统k-近邻算法在寻找邻域点时，认为无标签信息与有标签信息的重要性程度是一样的。考虑到标签数据作为物理空间位置信息的先验信息，能够更好反映指纹库的位置特征，因此，本发明优先考虑样本信息与标签数据的相互连接关系，通过相互近邻的理念取代传统knn算法构建的邻域，以标签数据作为邻域图中心，采用信息量最大的相互近邻来构建邻域图。采用邻域图逼近流行映射上的平滑积分，实现采样点与标签数据在流形映射上的平滑，最大限度提高标签数据在邻域图中权重的平滑期望。采样点与标签点之间存在一种流形映射关系，两个点之间由于是一种邻域关系，因此可以实现数据上的平滑。
(3)基于半监督流形学习的指纹库构建方法。利用标签数据的地理位置信息与无标签数据的时间相关性，利用流形学习的方法对大量无标签数据进行标记，实现位置指纹库的构建。本发明基于半监督流形学习的位置指纹库构建流程如图1所示。
本发明的技术方案为：
一种半监督的基于流形学习的位置指纹库构建方法，其步骤包括：
1)获取目标环境中的rp位置集r，其包括有标签rp位置集r1和无标签rp位置集r2；对于r2中每一个无标签rp，结合其邻近有标签的k个rp位置发送的信号被第i个网关接收到的rss值进行三次样条插值，得到对应无标签rp位置发送信号被该第i个网关接收到的rss值，得到初始位置指纹库；其中rp为信号接收点，该目标环境存在n个网关和n个rp；每一个rp采集m个rss序列，共采集nl个带标签的rss序列，nl＝m×n，带标签的rss序列表示为
2)该目标环境中的每一移动设备在其当前位置采集到tp个rss序列
3)基于所述初始位置指纹库和步骤2)所采集数据，构建高维rss样本的权重矩阵、位置权重矩阵和时间戳权重矩阵；
4)基于高维rss样本的权重矩阵wr、位置权重矩阵wlloc和时间戳权重矩阵wut，构建复合拉普拉斯矩阵l；
5)将复合拉普拉斯矩阵l代入公式
6)结合流形学习模型，将无标签数据的物理位置坐标映射为高维向量数据点；然后将无标签数据的高维rss样本和流形学习映射的高维向量数据进行整合，实现指纹库的扩充，得到位置指纹库。
进一步的，构建高维rss样本的权重矩阵wr的方法为：
21)构建初始数据库中采样数据两两之间的欧式距离，得到一距离矩阵d，dij为距离矩阵d中采样第i个采样数据与第j个采样数据之间的欧式距离；
22)对于xl中任意样本xi，通过距离矩阵d，找到ke个近邻数据点；
23)对于xt中任意一个与xi无近邻无标签数据点xj，找到xj的ke个近邻数据点f(j)，如果存在满足dist(xi,xj)≤dist(xj,f(j))，那么当前样本xi与是xj相互近邻，并计算样本xi与xj的相似度sij；
24)查找xj的近邻带标签数据样本
25)重新定义样本xi与xj的距离为
进一步的，所述位置权重矩阵wlloc中的元素为
进一步的，所述时间戳权重矩阵wut中的元素为
进一步的，构建复合拉普拉斯矩阵l的方法为：首先构建带标签数据的权重矩阵的拉普拉斯矩阵ll＝dl-wl、无标签数据的权重矩阵的拉普拉斯矩阵lu＝du-wu以及高维rss样本权重矩阵的拉普拉斯矩阵
本发明的有益效果在于：
本发明提供了一种半监督的基于流形学习的位置指纹库的构建方法，提出一种半监督改进流形学习算法的指纹库构建方法。对传统的流形学习算法进行改进，针对无监督k近邻算法没有考虑带标签数据的重要性问题，提出一种带标签数据的邻域图构建方法构建高维rssi样本建立权重矩阵，利用带标签信息的物理坐标信息的先验性，更好反映系统的特征。除此之外，利用物理空间的相同或者相近位置上的无线信号强度具有相似性的特点，基于大量具有时间戳的无标签数据，采用时空数据局部相似性的原理，剔除噪音数据，提升数据的可信度。
附图说明
图1为基于半监督流形学习的指纹库构建流程图。
图2为带标签数据的邻域图构建方法示意图；
(a)无标签数据邻域及近邻数据，(b)查找无标签数据样本的近邻带标签数据样本，
(c)基于测地距离构建高维rss样本的权重矩阵。
具体实施方式
下面通过具体实施例，并配合附图，对本发明做进一步的说明。
(1)初始数据库构建
在确定样本容量后，由于采用稀疏数据库采集的方法进行建库，因此，采用插值法对未标记的rp点的数据进行插值，以便降低建库的开销。本文采用三次样条插值法，实现未标记点信号的估计，构建初始数据库。
步骤1:将目标环境中所有的rp位置集、有标签的rp位置集和无标签的rp位置集分别表示为r、r1和r2；rp(receivingpoint)为信号接收点。
步骤2:对于每一个无标签的rp，结合其邻近标签的k个(k根据经验取值，一般取3、4即可)rp位置发送的信号被第i个网关接收到的rss值进行三次样条插值，求出每一个无标签rp位置发送信号被第i个网关接收到的rss值。通过上述处理所得的初始位置指纹库为集合r且r中每个rp都具有rss值。
(2)基于流形学习的位置指纹数据库扩展方法
在定位环境中，假设该目标环境存在n个网关和均匀分布n个rp(n＝l×l，即对目标定位环境进行测试时对其进行网格化，l等于目标区域边长除以网格边长。)由于无线传播的信号容易受到环境干扰，因此，在每一个rp需要采集m个rss序列，一共采集nl(n×m)带标签的rss序列，带标签的rss序列可以表示为：
除了采集带标签的数据外，还有一些设备在定位环境内移动，这些移动设备可以采集到该点的tp个rss序列
传统的无监督k近邻算法没有考虑带标签数据的重要性，提出一种带标签数据的邻域图构建方法构建高维rss样本建立权重矩阵，利用带标签信息的物理坐标信息的先验性，更好反映系统的特征。除此之外，利用物理空间的相同或者相近位置上的无线信号强度具有相似性的特点，基于大量具有时间戳的无标签数据，采用时空数据局部相似性的原理，剔除噪音数据，提升数据的可信度。
步骤1:构建高维rss样本的权重矩阵
带标签数据的邻域图构建方法考虑了与标签数据邻近的数据之间的相关关系，利用相互近邻的理念构建数据间的连接关系，使得带标签数据成为了邻域图的中心点，从而提升带标签数据信息在邻域图内不同数据间的传播。因此，计算当前采样数据与带标签数据的最短测地距离的最小化作为目标函数：
其中，sij是当前样本数据xi(xl中数据)与其近邻点无标签数据xj(xt中数据)的相似度，
基于图2，带标签数据的邻域图构建流程如下：
(1)构建初始数据库中采样数据两两之间的欧氏距离，dij为采样第i个采样数据与第j个采样数据之间的欧氏距离。
(2)对于xl中任意样本xi，通过距离矩阵d，找到ke＝5个近邻数据点。
(3)对于xt中任意一个与xi无近邻无标签数据点xj，找到近邻无标签数据点xj的ke＝5个近邻数据点f(j)，如果存在满足dist(xi,xj)≤dist(xj,f(j))，那么当前样本xi与是xj相互近邻，并计算样本xi与xj的相似度sij。
(4)查找无标签样本xj的近邻带标签数据样本
(5)重新定义当前样本xi与xj的距离：
步骤2:利用带标签数据位置坐标构建位置权重矩阵
本专利利用所采样的带标签数据和无标签数据的相关性构建高维rss样本的权重矩阵，还利用带标签数据的地理位置信息构建位置权重矩阵，提升位置数据库构建的精度，位置权重信息表示为：
其中，θr为位置核函数，位置坐标核函数可以根据不同算法确定的，在本申请中利用拉普拉斯算法确定，d(ii,ij)为位置点ii与ij测地距离。核函数作用是把两个维度联系起来：给定一个域中的一个高维变量，核函数就变成低维中的一个基函数。因此，本专利中的位置坐标核函数，是结合带标签数据的地理位置信息和rss样本训练出来的，通过核函数将两个样本的数据联系起来。
步骤3:利用数据时间戳关系构建时间戳的权重矩阵
同理，结合样本数据的时间戳，构建时间戳的权重矩阵：
在这里要说明的是，两点的时间差小于设定的阈值，该设定的阈值是基于网格大小而设定的。比如如果网格大小为30m×30m，那么假设用户从一个网格到邻近网格，结合用户运动的平均速度(如36公里/小时即10米/秒)，用户从一个网格的一端到达另外一个网格一端的平均时间为6s。因此，在上述例子中，采样点之间的时间差小于6s时，则认为用户在邻近网格内活动，则认为用户位置点ii和位置点ij相连。
步骤4:基于流形学习的定位指纹库矩阵扩充
流形学习扩充指纹库的核心是对无标签高维数据进行降维，估计rss的物理位置，得到无标签物理地理位置的集合q。根据流形学习的定位可知，降维后的坐标集合q的精度取决于拉普拉斯算子l。而拉普拉斯算子l则通过权重矩阵w得到。为了得到权重矩阵w，第一步需要对高维rss样本建立权重矩阵进行处理，按照数据是否设置标签，高维rss样本权重矩阵可表示为：
其中，
其中α是一比例系数，根据经验确定取值，wlloc是利用公式2得到的位置权重矩阵，wut是利用公式3得到的时间戳权重矩阵。在此基础上，分别构建带标签数据和无标签数据的权重矩阵的拉普拉斯矩阵，分别是ll和lu；同理，构建高维rss样本权重矩阵的拉普拉斯矩阵
其中dl、du、dlu和dul是带标签数据、无标签数据以及高维rss样本数据的对角矩阵，dlu和dul互为转置矩阵，可通过对应的权重矩阵进行计算，最终得到的复合拉普拉斯矩阵可表示为：
其中，u为权重系数(根据带标签位置数量信息确定取值)，其越大，表示带标签数据与无标签数据间的拉普拉斯矩阵
综合上述采集的有标签和无标签信息，所采集的rss序列可以表示为
其中
其中，第一部分是考虑数据平滑性的目标函数，第二部分是低维空间与真实位置信息的拟合误差。根据上述思路，可以将公式10写为：
其中jq为对角矩阵，可以根据数据的邻接关系可以求出来，γ是一个平衡参数，取值在0-1之间，可按照实际的经验来取值。
然后将公式8复合拉普拉斯矩阵l代入公式12，rss向量(每个信号接收点rp的信号强度值序列构成一rss向量)和位置向量(每个信号接收点rp的经纬度位置构成一位置向量向量)，进行流形对齐，得到无标签数据的物理位置坐标。
在获得无标签数据的物理位置坐标的基础上，结合流形学习模型，将无标签数据的物理位置坐标映射为高维向量数据点。将无标签数据的高维rss样本和流形学习映射的高维向量数据进行整合，通常采用平均法对向量进行整合，最终实现指纹库的扩充，得到位置指纹库。
例如一个lorawan协议的低功耗广域网络中，有不少固定终端，可以在部署时进行信号强度采集和位置标注。同时，新加入的固定终端和移动的终端，没有位置标注。固定终端即可用本发明中的流形学习算法对采集和标注的固定点信息插值所获得的定位指纹库进行扩充和校正。移动的终端根据其时间戳信息，可以对其经过的邻近位置参考点的指纹进行扩充和校正。从而随着网络新节点的加入和移动节点的运动，可以增加指纹库的信息和准确性，提高定位的精度。
以上实施仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。
1.一种半监督的基于流形学习的位置指纹库构建方法，其步骤包括：
1)获取目标环境中的rp位置集r，其包括有标签rp位置集r1和无标签rp位置集r2；对于r2中每一个无标签rp，结合其邻近有标签的k个rp位置发送的信号被第i个网关接收到的rss值进行三次样条插值，得到对应无标签rp位置发送信号被该第i个网关接收到的rss值，得到初始位置指纹库；其中rp为信号接收点，该目标环境存在n个网关和n个rp；每一个rp采集m个rss序列，共采集nl个带标签的rss序列，nl＝m×n，带标签的rss序列表示为
2)该目标环境中的每一移动设备在其当前位置采集到tp个rss序列
3)基于所述初始位置指纹库和步骤2)所采集数据，构建高维rss样本的权重矩阵、位置权重矩阵和时间戳权重矩阵；
4)基于高维rss样本的权重矩阵wr、位置权重矩阵wlloc和时间戳权重矩阵wut，构建复合拉普拉斯矩阵l；
5)将复合拉普拉斯矩阵l代入公式
6)结合流形学习模型，将无标签数据的物理位置坐标映射为高维向量数据点；然后将无标签数据的高维rss样本和流形学习映射的高维向量数据进行整合，实现指纹库的扩充，得到位置指纹库。
2.如权利要求1所述的方法，其特征在于，构建高维rss样本的权重矩阵wr的方法为：
21)构建初始数据库中采样数据两两之间的欧式距离，得到一距离矩阵d，dij为距离矩阵d中采样第i个采样数据与第j个采样数据之间的欧式距离；
22)对于xl中任意样本xi，通过距离矩阵d，找到ke个近邻数据点；
23)对于xt中任意一个与xi无近邻无标签数据点xj，找到xj的ke个近邻数据点f(j)，如果存在满足dist(xi,xj)≤dist(xj,f(j))，那么当前样本xi与是xj相互近邻，并计算样本xi与xj的相似度sij；
24)查找xj的近邻带标签数据样本
25)重新定义样本xi与xj的距离为
3.如权利要求1或2所述的方法，其特征在于，所述位置权重矩阵wlloc中的元素为
4.如权利要求1所述的方法，其特征在于，所述时间戳权重矩阵wut中的元素为
5.如权利要求1所述的方法，其特征在于，构建复合拉普拉斯矩阵l的方法为：首先构建带标签数据的权重矩阵的拉普拉斯矩阵ll＝dl-wl、无标签数据的权重矩阵的拉普拉斯矩阵lu＝du-wu以及高维rss样本权重矩阵的拉普拉斯矩阵
