基于半监督SDE算法的WLAN室内定位方法

摘要

基于半监督SDE算法的WLAN室内定位方法，涉及室内定位领域。本发明是为了解决现有WiFi室内定位方法中存在的在线定位复杂度高，移动终端定位实时性差的问题。本发明通过引入半监督SDE降维算法，通过利用易于采集的未标记数据，找出表征位置信息的高维数据的低维流形，在保证WLAN室内定位系统的定位精度的同时有效地减少了定位过程的计算量。同时减少了参考点数据采集的工作量，为数据库的实时更新提供了简便易行的途径。本发明的在线定位复杂度低，移动终端定位实时性强。本发明适用于WLAN室内定位。

说明书

技术领域

本发明涉及室内定位领域，具体涉及一种位置指纹室内定位方法。

背景技术

随着无线网络、移动通信和普适计算的广泛普及，基于位置的服务(LBS， Location-based Services)也越来越受到人们的广泛关注，其中如何确定用户的位置是 实现LBS的关键。众所周知，全球卫星定位(GPS，Global Positioning System)系统 通过接收器测量来自5～24个卫星信号的到达时间差估计位置，可以提供较高精度的 定位估计。但是，GPS在室内和高楼密集的城市由于卫星信号的非视距而无法实现定 位。随着IEEE 802.11标准的提出，无线局域网(WLAN,Wireless Local Area Networks) 已广泛分布在校园、办公大楼及家庭。而基于接收信号强度的室内定位系统因具有部 署方便、成本低、不需添加定位测量专用硬件等特点而受到广泛重视。

在WLAN环境下，通过移动终端的无线网卡及相应软件测量来自无线接入点(AP， Access Point)的接收信号强度(RSS，Received Signal Strength)值，获得与相应位置 有关的信息，进而通过匹配算法来预测移动用户所处位置。其中基于位置指纹的定位 算法因为定位精度高，可充分利用现有设施，升级和维护对用户影响小等优点而得到 广泛应用。位置指纹定位算法分为离线测量阶段和在线定位阶段两个步骤，离线阶段 主要是建立位置与接收信号强度之间的对应关系，即在待定位区域按一定规则设置参 考点，通过测量参考点处接收到的不同AP信号强度值，建立对应的位置指纹数据库 Radio Map。在线定位阶段，通过测试点接收到的RSS值，采用相应的匹配算法，主要 包括最近邻法，K近邻法，概率法和神经网络法。其中K近邻法(KNN，K Nearest  Neighbors)在算法复杂度和定位精度上都具有一定优势，广泛的用于在线定位匹配， 找到位置指纹数据库中与其最接近的位置，作为最终的位置估计结果。离线阶段建立 的Radio Map包含有大量的数据信息，且随着定位区域扩大、参考点的增加，导致Radio  Map信息量呈指数形势增长。

基于位置指纹的WLAN室内定位系统，通过离线阶段采集尽可能多的数据信息， 可以有效地提高系统的定位精度。而在线定位阶段处理大量的数据信息，增加定位过 程的数据运算量，对移动终端来讲其处理能力有限，导致定位算法运行困难。同时某 些特征信息不仅不能提供有效的位置信息，甚至还会影响定位结果的准确性。

当AP数目增加，Radio Map中表示AP数目的维数信息就变成了高维数据，可通 过维数约减来减轻处理高维数据的负担。高维数据可能包含很多特征，这些特征都在 描述同一个事物，这些特征一定程度上是紧密相连的。如当从多个角度对同一个物体 同时拍照时，得到的数据就含有重叠的信息。如果能得到这些数据的一些简化的不重 叠的表达，将会极大地提高数据处理运行的效率并一定程度上提高准确度。降维算法 的目的也正是在于提高高维数据的处理效率。

目前有很多基于不同目的的降维算法，包括线性与非线性降维算法。其中PCA和 LDA是典型的线性降维算法。这一类算法对于具有线性结构的高维数据有很好的降维 结果，但不适用于非线性结构的高维数据。非线性降维算法则以流形学习算法为主。 SDE算法是基于流形学习算法中LDE算法提出的，它是一种典型的基于特征提取的流 形学习算法。

发明内容

本发明是为了解决现有WiFi室内定位方法中存在的在线定位复杂度高，移动终端 定位实时性差的问题，从而提供一种基于半监督SDE算法的WLAN室内定位方法。

基于半监督SDE算法的WLAN室内定位方法，它由以下步骤实现：

步骤一、针对室内环境布置m个接入点AP(AP_j,1≤j≤m)，确保所述室内环境中任 意一点被两个或两个以上的无线接入点AP发出的信号覆盖；m为正整数；

步骤二、在室内环境中均匀设置参考点，选取一个参考点为原点建立直角坐标系， 获得各个参考点在该直角坐标系中的坐标位置，并在每个参考点上利用信号接收机采 集并记录来自每一个AP的接收信号强度RSS值k次，并进行数据处理；k为正整数；

步骤三、根据K均值聚类算法将室内定位环境分成Q个子区域，为每个子区域的 参考点标记各自的类别信息；

步骤四、采集随机的未标记RSS数据，与步骤三获取的各个子区域的特征向量进 行比较，即求取与各子区域的特征向量的距离，将随机数据类别划分在与其特征向量 距离最近的子区域内；

步骤五、对K个子区域中每个子区域采用SDE算法，获得特征变换矩阵；

SDE算法的输入参数，即本征维数的取值，通过已有的本征维数估计算法对Radio  Map分区数据进行估计，给出每个区域数据的本征维数估计值，确定每个区域的特征 变换矩阵，并生成降维后的位置指纹数据库Radio Map^*；

步骤六、将待测点获取的信号强度RSS值与步骤三获取的各个子区域的特征向量 进行比较，即求取测试点的特征向量与各子区域的特征向量的距离，将测试点定位在 与其特征向量距离最近的子区域内；

步骤七、在被定位的子区域内，利用步骤五得出的特征变换矩阵对待测点的RSS 值进行降维，得到低维的RSS^*，与指纹数据库Radio Map^*进行匹配，采用K近邻位置 指纹定位算法对测试点进行精确定位。

步骤二所述的在每个参考点上利用信号接收机采集并记录来自每一个AP的接收 信号强度RSS值k次，并进行数据处理的具体步骤为：

步骤二一、对每个参考点得到一个k×m阶矩阵，矩阵的第i行第j列表示第i次采 集中接收到的来自第j个AP的RSS值；k、m、i、j均为正整数；

步骤二二、将每个参考点得到的k×m阶矩阵列向量里所有的元素相加得到一个 值，再把这个值除以k，则每个参考点都得到了一个1×m的向量，对于每一个参考点， 该向量称为该参考点的特征向量，向量中的第j个元素做为该参考点的第j个特征；如 果一个参考点上某些AP的RSS值检测不到，则将其赋值为该环境下能接收到的最小 信号值-100dBm,故而任意参考点的接收信号强度RSS值v的范围为 -100dBm≤v≤0dBm；这组向量用于实现步骤三的聚类分区。

步骤三所述的根据K均值聚类算法对室内定位环境划分成Q个子区域的具体步骤 为：

步骤三一、输入步骤二二测得的所有参考点的特征向量和子区域个数Q；

步骤三二、随机从步骤二二得到得数据里选取K个参考点的RSS，即：各参考点 的特征向量值作为K个子区域的聚类中心；

步骤三三、计算每个参考点和K个聚类中心特征向量的欧式距离，将各个参考点 分配给与其欧氏距离最小的子区域；

步骤三四、把每个子区域中各个参考点的RSS值求均值，得到新的聚类中心；

步骤三五、重复步骤三三和步骤三四直到每个子区域的中心不再改变；

步骤三六、得到K个子区域及各子区域对应的聚类中心向量，即：一个1×m的向 量，称该向量为这个子区域的特征向量，该向量的第j个元素表示这个子区域的第j个 特征，也是这个子区域获得的来自第j个AP的RSS均值。

步骤四随机RSS数据的类别划分的具体过程为：

步骤四一、输入随机采集的未标记数据，所述未标记数据仅有信号强度值而没有 位置信息；

步骤四二、将未标记数据与步骤三获取的各个子区域的特征向量进行比较，即求 取与各子区域的特征向量的距离，将随机数据分配在与其特征向量距离最近的子区域 内，作为其所属的类别。

步骤五所述的对K个子区域中的每个子区域采用SDE算法进行降维，确定每个区 域的特征变换矩阵，并生成新的位置指纹数据库的具体方法为：

步骤五一、构造邻接图：

根据高维数据点的类标记信息及其近邻关系构造无方向图G及G'；其中近邻关系 是采用KNN算法给出的准则，即选择数据点最近的K个点作为其邻居，G表示当x_i与 x_j的类标记信息y_i＝y_j时且x_i、x_j互为K近邻关系；G'示当x_i与x_j的类标记信息y_i≠y_j时且x_i、x_j互为K近邻关系；

步骤五二、计算权值矩阵：

根据步骤五一构造的邻接图，采用类高斯函数进行权值矩阵的计算，其表达式为 (1)所示：

$\left(\begin{array}{c}{w}_{\mathrm{ij}}=\left(\begin{array}{c}\exp (-{\left|\right|x_i-x_j\left|\right|}^2/t);\\ 0;\end{array}\mathrm{if}{x}_i,x_j\in G\right)\\ w_{\mathrm{ij}}^{\prime }=\left(\begin{array}{c}\exp (-{\left|\right|x_i-x_j\left|\right|}^2/t)\\ 0;\end{array}\right)\mathrm{if}{x}_i,x_j\in G^{\prime }\end{array}\right)---\left(1\right)$

其中：w_ij表示近邻点x_i与x_j之间的权值，||x_i-x_j||²为近邻点x_i与x_j之间的范数距 离，采用矩阵方式计算范数距离，t为权值归一化参数；

步骤五三、确定目标函数及其求解：

根据SDE算法的目标：最大化类间散度的同时最小化类内散度；散度采用表示同 类及非同类数据点的范数距离表示；

由SDE算法的目标得出其相应的优化目标函数，如式(2)所示，特征变换矩阵P 为待求的最优解：

根据式(2)给出的优化目标函数可知：

已知矩阵范数的计算式该式与矩阵的迹的计算式||A||²＝tr(AA^T)一致， 因此式(2)表示为矩阵的迹：

$J\left(V\right)=\underset{i,j}{\Sigma }\left\{\mathrm{tr}\right[(P^T{x}_i-P^T{x}_j){(P^T{x}_i-P^T{x}_j)}^T{w}_{\mathrm{ij}}^{\prime }\left]\right\}---\left(3\right)$

式(3)进一步简化为：

$J\left(V\right)=\underset{i,j}{\Sigma }\left\{\mathrm{tr}\right[P^T(x_i-x_j){(x_i-x_j)}^{T}P\left]w_{\mathrm{ij}}^{\prime }\right\}---\left(4\right)$

由矩阵迹的计算标量性质及权值元素均为实数，将式(4)简化为：

J(V)＝2tr{P^T[X(D′-W′)X^T]P}    (5)

同理，将式(2)简化成：

式(6)中，X为输入高维数据，W、W'分别为G与G'对应的权值矩阵；D及D' 为对角阵，其对角元素由式(7)求得：

$\left(\begin{array}{c}{d}_{\mathrm{ii}}=\underset{j}{\Sigma }{w}_{\mathrm{ij}}\\ d_{\mathrm{ii}}^{\prime }=\underset{j}{\Sigma }{w}_{\mathrm{ij}}^{\prime }\end{array}\right)---\left(7\right)$

对式(6)应用拉格朗日乘数法，得出式(8)所示：

X(D′-W′)X^TP＝λX(D-W)X^TP    (8)

对式(8)进行广义特征值分解，得出其特征值分解的特征值λ＝[λ₁,λ₂,…,λ_n]^T及特 征向量p＝[p₁,p₂,…,p_n]^T；

步骤五四、本征维数估计：

根据步骤五三求出的特征值及其特征向量，按照式(9)估计本征维数：

$\frac{\underset{i=1}{\overset{d}{\Sigma }}{\lambda }_i}{\underset{i=1}{\overset{n}{\Sigma }}{\lambda }_i}\ge {\eta }^{*}---\left(9\right)$

其中：η^*是投影空间保留信息的阈值，通常取值大于80％，即选取前d个最大特 征值之和与全部特征值总和之比不小于80％，即满足对原始数据信息较好的低维嵌入；

步骤五五、计算嵌入结果：

根据步骤五四设定本征维数估计阈值，选取的d个特征值对应的特征向量构成变 换矩阵P＝[p₁,p₂,…,p_d]，在按式(10)计算输入高维数据点x_i降维后的数据Z_i为：

Z_i＝P^Tx_i    (10)

通过SDE算法得出低维的信号指纹数据及特征变换矩阵，分别记为Radio Map^*和 P。

步骤七所述的对K个子区域中的每个子区域，分别利用步骤五求得的低维Radio  Map^*及特征变换矩阵，采用k近邻位置指纹定位算法对测试点进行定位的具体方法为：

步骤七一、步骤六将测试点定位在子区域中，测试点接收的RSS信号为高维实时 信号，表示为R_test＝[r₁,r₂,…,r_n]；与该区域的特征变换矩阵P利用公式(10)相乘，计 算降维后的信号值${\tilde{R}}_{\mathrm{test}}=[{\tilde{r}}_1,{\tilde{r}}_2,...,{\tilde{r}}_d];$

步骤七二、测试点的低维特征向量与该区域低维Radio Map^*中第 i个参考点之间的距离由公式(11)求得：

${\mathrm{Dis}}_i={\left(\underset{j=1}{\overset{d}{\Sigma }}{|{\tilde{r}}_j-{\mathrm{rss}}_{\mathrm{ij}}|}^2\right)}^{\frac{1}{2}}---\left(11\right)$

步骤七三、从结果中从小到大选取k个与测试点特征向量距离最近的参考点，按公 式(12)计算测试点的位置估计坐标

$(\hat{x},\hat{y})=\frac{1}{k}\underset{i=1}{\overset{k}{\Sigma }}(x_{\mathrm{ix}},y_{\mathrm{iy}})---\left(12\right)$

完成对测试点的定位。

本发明通过引入半监督SDE降维算法，通过利用易于采集的未标记数据，找出表 征位置信息的高维数据的低维流形，在保证WLAN室内定位系统的定位精度的同时有 效地减少了定位过程的计算量。同时减少了参考点数据采集的工作量，为数据库的实 时更新提供了简便易行的途径。本发明的在线定位复杂度低，移动终端定位实时性强。

附图说明

图1是是本发明的具体实施方式三中所述的室内场景示意图。

具体实施方式

具体实施方式一、本实施方式所述的半监督SDE算法的WLAN室内定位方法的定 位过程为：

步骤一、针对室内环境布置m个AP(AP_j,1≤j≤m)，确保所述环境中任意一点被两 个或两个以上的AP发出的信号覆盖；

步骤二、在室内环境中均匀设置参考点，选取一个参考点为原点建立直角坐标系， 获得各个参考点在该直角坐标系中的坐标位置，并在每个参考点上利用信号接收机采 集并记录来自每一个AP的接收信号强度RSS值k次并进行相应的数据处理；

步骤三、根据K均值聚类算法将室内定位环境分成Q个子区域，为每个子区域的 参考点标记各自的类别信息。在每个子区域中各个参考点的接收信号强度RSS值具有 相似的特征，即每个参考点的特征向量相似；

步骤四、采集随机的未标记RSS数据(与参考点区别在于仅有信号强度值而没有 位置信息)，与步骤三获取的各个子区域的特征向量进行比较，即求取与各子区域的 特征向量的距离，将随机数据类别划分在与其特征向量距离最近的子区域内；

步骤五、对K个子区域中每个子区域采用SDE算法。作为SDE算法的输入参数： 本征维数(Intrinsic Dimensionality)的取值，通过已有的本征维数估计算法对Radio Map 分区数据进行估计，给出每个区域数据的本征维数估计值。确定每个区域的特征变换 矩阵，并生成降维后的位置指纹数据库(Radio Map^*)；

步骤六、将待测点获取的信号强度RSS值与步骤三获取的各个子区域的特征向量 进行比较，即求取测试点的特征向量与各子区域的特征向量的距离，将测试点定位在 与其特征向量距离最近的子区域内；

步骤七、在被定位的子区域内，利用步骤五得出的特征变换矩阵对待测点的RSS 值进行降维，得到低维的RSS^*，与指纹数据库Radio Map^*进行匹配，采用K近邻位置 指纹定位算法对测试点进行精确定位。

具体实施方式二、本实施方式是对具体实施方式一所述的半监督SDE算法的 WLAN室内定位方法的进一步说明，具体实施方式一中步骤二所述的在每个参考点上 利用信号接收机采集并记录来自每一个AP的接收信号强度RSS值k次并进行相应的数 据处理的具体步骤为：

步骤二一、对每个参考点得到一个k×m阶矩阵，矩阵的第i行第j列表示第i次采 集中接收到的来自第j个AP的RSS值；

步骤二二、将每个参考点得到的k×m阶矩阵列向量里所有的元素相加得到一个值， 再把这个值除以k,这样每个参考点都得到了一个1×m的向量，对于每一个参考点，该 向量称为该参考点的特征向量，向量中的第j个元素(即从AP_j获得的信号强度RSS均 值)可以做为该参考点的第j个特征。有些时候在一个参考点上某些AP的RSS值检测 不到，则将其赋值为该环境下能接收到的最小信号值-100dBm,故而任意参考点的接收 信号强度RSS值v的范围为-100dBm≤v≤0dBm。这组向量将用于实现步骤三的聚类分 区。

本实施方式为后续具体实施方式提供了指纹数据库样本。

具体实施方式三、本实施方式是对具体实施方式一所述的半监督SDE算法的 WLAN室内定位方法的进一步说明，具体实施方式一中步骤三所述的根据K均值聚类 算法对室内定位环境划分成Q个子区域的具体步骤为：

步骤三一、输入步骤二二测得的所有参考点的特征向量和子区域个数Q；

步骤三二、随机从步骤二二得到得数据里选取K个参考点的RSS(即各参考点的 特征向量)值作为K个子区域的聚类中心；

步骤三三、计算每个参考点和K个聚类中心特征向量的欧式距离，将各个参考点 分配给与其欧氏距离最小的子区域；

步骤三四、把每个子区域中各个参考点的RSS值求均值，得到新的聚类中心；

步骤三五、重复步骤三三和步骤三四直到每个子区域的中心不再改变；

步骤三六、得到K个子区域及各子区域对应的聚类中心向量(即一个1×m的向量， 称该向量为这个子区域的特征向量，该向量的第j个元素表示这个子区域的第j个特 征，也是这个子区域获得的来自第j个AP的RSS均值)。

本实施方式能保证对定位环境进行有效的分区，使每个子区域内的参考点接收到 的来自各个AP的信号强度RSS值，即个参考点的特征向量相似程度大于来自两个不 同子区域的参考点的特征向量相似度，这也为步骤四中的随机RSS数据类别划分奠定 基础。

在图1所示的室内场景中进行实验，拥有19个实验室，1个会议室和1个乒乓球 室，表示电梯，墙的材料是砖块，铝合金窗户和金属门，无线接入点AP为Linksys  WAP54G-CN，且用AP1、AP2、……、AP27标示1至27号AP，各AP固定在距地面 2m高度的位置。信号接收机离地面1.2m，图中箭头标志为1至27号AP放置的位置， 选择走廊作为实验场所，即图中的网格状区域，相邻参考点之间间隔为1m，共247个 参考点。

使用Intel PRO/Wireless 3945ABG network connection的无线网卡连接入网，在联 想V450笔记本上安装NetStumbler软件，采集来自27个接入点AP的信号强度RSS 值；离线阶段，在所有参考点的四个不同的方位上，以2个/秒采样频率，连续采样记 录AP的100个RSS值，以及AP的相关信息。将所有的参考点的物理坐标及RSS值 存储为定位过程所调用的数据，建立Radio Map。随机采集定位区域580个点的RSS 数据，方向随机且以2个/秒频率，每个点采样10秒，取均值作为SDE算法中的未标 记数据，这些数据只记录信号强度值而没有具体位置信息。与Radio Map一起作为SDE 算法的输入数据。

具体实施方式四、本实施方式是对具体实施方式一所述的半监督SDE算法的 WLAN室内定位方法的进一步说明，具体实施方式一中步骤四随机RSS数据的类别划 分的具体过程为：

步骤四一、输入随机采集的未标记数据(仅有信号强度值而没有位置信息)；

步骤四二、将未标记数据与步骤三获取的各个子区域的特征向量进行比较，即求 取与各子区域的特征向量的距离，将随机数据分配在与其特征向量距离最近的子区域 内，作为其所属的类别。

本实施方式能划分随机采集的未标记数据所属的类别，为步骤五中的SDE算法构 建全部数据邻接图矩阵提供类别信息。

具体实施方式五、本实施方式是对具体实施方式一所述的半监督SDE算法的 WLAN室内定位方法的进一步说明，具体实施方式一中步骤五所述的对K个子区域中 的每个子区域采用SDE算法进行降维，确定每个区域的特征变换矩阵，并生成新的位 置指纹数据库进行具体说明：

SDE算法是基于类间散度及类内散度最大化的一种流形学习算法。在对SDE算法 进行理论分析之前对输入数据做如下说明：输入高维已标记数据和未标记数 据两类数据主要区别在于：前者对应参考点处采集的数据，含有位置信息 (x_ix,y_iy)及其类标记y_i∈{1,2,…,c}。其中c表示将高维数据划分为c个子流形，即将输 入的高维数据分成c类。未标记数据经过步骤四后也获得相应的类信息。

步骤五一、构造邻接图

根据高维数据点的类标记信息及其近邻关系构造无方向图G及G'。其中近邻关系 是采用KNN算法给出的准则，即选择数据点最近的K个点作为其邻居，G表示当x_i与 x_j的类标记信息y_i＝y_j时且x_i、x_j互为K近邻关系；G'示当x_i与x_j的类标记信息y_i≠y_j时且x_i、x_j互为K近邻关系。

步骤五二、计算权值矩阵

根据步骤五一构造的邻接图，采用类高斯函数进行权值矩阵的计算。其表达式为 (1)所示。公式(1)中w_ij表示近邻点x_i与x_j之间的权值，||x_i-x_j||²为近邻点x_i与x_j之 间的范数距离，采用矩阵方式计算范数距离，t为权值归一化参数。

$\left(\begin{array}{c}{w}_{\mathrm{ij}}=\left(\begin{array}{c}\exp (-{\left|\right|x_i-x_j\left|\right|}^2/t);\\ 0;\end{array}\mathrm{if}{x}_i,x_j\in G\right)\\ w_{\mathrm{ij}}^{\prime }=\left(\begin{array}{c}\exp (-{\left|\right|x_i-x_j\left|\right|}^2/t)\\ 0;\end{array}\right)\mathrm{if}{x}_i,x_j\in G^{\prime }\end{array}\right)---\left(1\right)$

步骤五三、确定目标函数及其求解

根据SDE算法的目标：最大化类间散度的同时最小化类内散度。散度采用表示同 类及非同类数据点的范数距离表示。由SDE算法的目标可以得出其相应的优化目标函 数，如式(2)所示，特征变换矩阵P为待求的最优解。

式中：Maximize表示：最大化，subject to表示：服从；

根据式(2)给出的优化目标函数作以下分析：

已知矩阵范数的计算式该式与矩阵的迹的计算式||A||²＝tr(AA^T)一致， 因此式(2)可以表示为矩阵的迹：

$J\left(V\right)=\underset{i,j}{\Sigma }\left\{\mathrm{tr}\right[(P^T{x}_i-P^T{x}_j){(P^T{x}_i-P^T{x}_j)}^T{w}_{\mathrm{ij}}^{\prime }\left]\right\}---\left(3\right)$

式(3)进一步简化为：

$J\left(V\right)=\underset{i,j}{\Sigma }\left\{\mathrm{tr}\right[P^T(x_i-x_j){(x_i-x_j)}^{T}P\left]w_{\mathrm{ij}}^{\prime }\right\}---\left(4\right)$

由矩阵迹的计算标量性质及权值元素均为实数，可以将式(4)简化为：

J(V)＝2tr{P^T[X(D′-W′)X^T]P}    (5)

同理，将式(2)简化成：

式(6)中，X为输入高维数据，W、W'分别为G与G'对应的权值矩阵。D及D' 为对角阵，其对角元素可以由式(7)求得：

$\left(\begin{array}{c}{d}_{\mathrm{ii}}=\underset{j}{\Sigma }{w}_{\mathrm{ij}}\\ d_{\mathrm{ii}}^{\prime }=\underset{j}{\Sigma }{w}_{\mathrm{ij}}^{\prime }\end{array}\right)---\left(7\right)$

对式(6)应用拉格朗日乘数法，可以得出式(8)所示：

X(D′-W′)X^TP＝λX(D-W)X^TP    (8)

对式(8)进行广义特征值分解，得出其特征值分解的特征值λ＝[λ₁,λ₂,…,λ_n]^T及特 征向量p＝[p₁,p₂,…,p_n]^T。

步骤五四、本征维数估计

本征维数是低维嵌入时保留的特征值及其对应的特征向量的个数。特征向量对应 特征值越大，该方向对应的类间距离越大，也就意味着所保留的特征越具有判别力。 本征维数d是算法的一个重要参数，其值估计准确与否，决定了低维数据所含信息量 的多少，从而影响定位精度。根据步骤五三求出的特征值及其特征向量，按照式(9) 估计本征维数：

$\frac{\underset{i=1}{\overset{d}{\Sigma }}{\lambda }_i}{\underset{i=1}{\overset{n}{\Sigma }}{\lambda }_i}\ge {\eta }^{*}---\left(9\right)$

其中η^*是投影空间保留信息的阈值，通常取值大于80％，即选取前d个最大特征 值之和与全部特征值总和之比不小于80％，即可满足对原始数据信息较好的低维嵌入。

步骤五五、计算嵌入结果

根据步骤四设定本征维数估计阈值，选取的d个特征值对应的特征向量构成变换 矩阵P＝[p₁,p₂,…,p_d]，在按式(10)计算输入高维数据点x_i降维后的数据Z_i为：

Z_i＝P^Tx_i    (10)

由式(2)～(8)给出SDE算法的理论推导。通过SDE算法可以得出低维的信号 指纹数据及特征变换矩阵，分别记为Radio Map^*和P。

具体实施方式六、本实施方式是对具体实施方式一所述的半监督SDE算法的 WLAN室内定位方法的进一步说明，具体实施方式一中步骤七所述的对K个子区域中 的每个子区域，分别利用步骤五求得的低维Radio Map^*及特征变换矩阵，采用k近邻位 置指纹定位算法对测试点进行定位进行具体说明：

步骤七一、步骤六将测试点定位在子区域中，测试点接收的RSS信号为高维实时 信号，表示为R_test＝[r₁,r₂,…,r_n]。与该区域的特征变换矩阵P(步骤五五中已获得)利 用公式(10)相乘，计算降维后的信号值

步骤七二、测试点的低维特征向量与该区域低维Radio Map^*(步 骤五五中获得)中第i个参考点之间的距离可由公式(11)求得：

${\mathrm{Dis}}_i={\left(\underset{j=1}{\overset{d}{\Sigma }}{|{\tilde{r}}_j-{\mathrm{rss}}_{\mathrm{ij}}|}^2\right)}^{\frac{1}{2}}---\left(11\right)$

步骤七三、从结果中从小到大选取k个与测试点特征向量距离最近的参考点，按公 式(12)计算测试点的位置估计坐标

$(\hat{x},\hat{y})=\frac{1}{k}\underset{i=1}{\overset{k}{\Sigma }}(x_{\mathrm{ix}},y_{\mathrm{iy}})---\left(12\right)$

完成对测试点的定位。