本发明公开了一种基于贝叶斯‑k均值聚类的室内定位分区方法，包括离线训练阶段和在线定位阶段，离线训练阶段利用k均值聚类算法将定位区域划分为若干子区域，其中初始聚类中心采用AP最近位置的初始聚类中心选择算法；在线定位阶段首先获取若干个距离最小的子区域，然后通过比较被分到每个区域的后验概率，将后验概率最大的子区域作为定位分区的结果。与现有技术相比，本发明提供的定位分区方法，通过结合AP最近位置的初始聚类中心选择算法来解决初始聚类中心选取不当导致局部最优的问题；另外结合贝叶斯算法分区预测算法来解决欧式距离无法很好拟合映射关系的问题。
1.一种基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，包括离线训练阶段和在线定位阶段，其中，离线阶段包括如下步骤：S11、在定位区域内均匀选取若干位置参考点，在每个参考点采集RSS向量，所有RSS向量构成全局指纹库；
S12、对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，并获得与所述k个子区域一一对应的k个聚类中心，其中，k的值为预先选取设定的，对全局指纹库采用k均值聚类算法中的k个初始聚类中心采用如下步骤得到：从全局指纹库中获取离每个AP位置最近的RSS向量，构成位置近似RSS向量集；
将获取的位置近似RSS向量集通过使用k均值聚类算法，得到位置近似RSS向量集的k个聚类中心；
将得到的位置近似RSS向量集的k个聚类中心作为全局指纹库的初始聚类中心；
S21、计算实时RSS向量与全局指纹库的k个聚类中心的欧式距离，选择距离最小的q个全局指纹库的聚类中心对应的子区域，q的值为预先选取设定的；
S22、采用贝叶斯算法计算实时RSS向量被分到q个子区域中每个子区域的后验概率，然后选取后验概率最大的子区域作为定位分区的结果。
2.根据权利要求1所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，步骤S11具体包括如下步骤：在定位区域内均匀选取若干参考点，在每个参考点采集5个RSS向量，所有RSS向量构成全局指纹库。
3.根据权利要求1所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，步骤S12中对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，并获得与所述k个子区域一一对应的k个聚类中心，具体步骤如下：S121、将位置近似RSS向量集的k个聚类中心初始化全局指纹库的K个聚类中心；
S122、计算每个参考点的RSS向量到全局指纹库的k个聚类中心的欧氏距离；
S123、将参考点分配到最近的全局指纹库的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；
S124、重复步骤S122和S123，直到每个聚类中心不再变化或者变化幅度小于预设值，得到k个子区域和与之对应的k个聚类中心。
4.根据权利要求1所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，步骤S12中从全局指纹库中获取离每个AP位置最近的RSS向量的方法为：对于第j个AP，获取所有RSS向量中第j个AP信号最强的所对应的参考点位置作为第j个AP的最近位置，该参考点所对应的RSS向量即为离第j个AP位置最近的RSS向量，该参考点所对应的RSS向量作为第j个AP的位置近似RSS向量。
5.根据权利要求4所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，步骤S12中将获取的所有位置近似RSS向量通过使用k均值聚类算法，得到位置近似RSS向量集的k个聚类中心，具体步骤如下：S125、随机选取k个聚类中心初始化位置近似RSS向量集的k个聚类中心；
S126、计算每个位置近似RSS向量到位置近似RSS向量集的k个聚类中心的欧氏距离；
S127、将位置近似RSS向量分配到最近的位置近似RSS向量集的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；
S128、重复步骤S126和S127，直到每个聚类中心不再变化或者变化幅度小于预设值，得到位置近似RSS向量集的k个聚类中心。
6.根据权利要求1所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，步骤S22中后验概率的计算公式为 其中zi代表第i个子区域，rsst代表采集到的实时RSS向量，P(zi|rsst)表示实时RSS向量被分到第i个子区域的后验概率，P(rsst|zi)是在第i个子区域内某一RSS向量为rsst的先验概率，P(zi)是随机分到第i个子区域的概率，p(rsst)是某一RSS向量为rsst的概率，P(zi)及p(rsst)均为常数。
7.根据权利要求6所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，P(rsst|zi)的计算方式如下， 表示子区域内第j个AP的实时RSS值，m表示RSS向量包含的RSS值的数量。
8.根据权利要求7所述的基于贝叶斯-k均值聚类的室内定位分区方法，其特征在于，的计算方式如下， 其中ui为第i子区域内第j个AP的RSS值的平均值，δi为第i子区域内的第j个AP的RSS值的方差。
基于贝叶斯-k均值聚类的定位分区方法
技术领域
[0001] 本发明涉及计算机技术领域，尤其涉及一种基于贝叶斯-k均值聚类的室内定位分区方法。
背景技术
[0002] 室内位置服务所能带来的巨大的应用和商业潜能促使位置服务的相关技术和产业正向室内发展，以提供无所不在的基于位置的服务。WLAN定位技术作为新兴的定位技术，完全基于现有的网络基础设施，且能实时提供比较精确地定位信息，且随着移动互联终端的发展，绝大多是移动端设备都可以检测到WLAN信号，所以基于WLAN的定位技术非常有利于室内定位技术大规模推广和应用，所以基于WLAN定位技术具有很强的适用性。
[0003] 大型场所的定位场景中，由于定位区域的面积较大，参考的AP数量急剧增多，导致位置指纹库的特征维数也会变得极为庞大，造成维数灾难的问题。目前，研究解决以上问题的方法就是在离线阶段将大型场所预先做人为地分区，然后对每个子区域分别建立区域特征指纹库，在线定位时，先把用户划分到预先设定的子区域，然后在子区域通过定位算法匹配该区域的位置指纹库进行精确定位，这个可以大大降低位置指纹库的维数和数据量。k均值聚类算法的计算简单且时间复杂度低，适合处理向大型室内定位问题中的大数据集，所以本发明基于k均值算法来研究聚类分区算法。
[0004] K均值聚类算法在室内定位分区时，存在以下问题：1、由于RSS信息与物理位置映射关系的是一种复杂的非线性的关系，k均值算法用欧式距离来度量无法很好得拟合这种映射关系。2、另外k均值聚类算法的另外一个显著缺陷就是聚类的结果受初始聚类中心的影响比较严重，若初始聚类中心选取不当，会导致局部最优，无法保证全局最优。
发明内容
[0005] 针对上述现有技术中的不足之处，本发明提供了一种基于贝叶斯-k均值聚类的定位分区方法，以解决现有技术中RSS信息与物理位置映射关系复杂且精度和结果稳定性差的问题。
[0006] 本发明提供了一种基于贝叶斯-k均值聚类的室内定位分区方法，包括离线训练阶段和在线定位阶段，其中，离线阶段包括如下步骤，
[0007] S11、在定位区域内均匀选取若干位置参考点，在每个参考点采集RSS向量，所有RSS向量构成全局指纹库；
[0008] S12、对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，并获得与所述k个子区域一一对应的k个聚类中心，其中，k的值为预先选取设定的，对全局指纹库采用k均值聚类算法中的k个初始聚类中心采用如下步骤得到：
[0009] 从全局指纹库中获取离每个AP位置最近的RSS向量，构成位置近似RSS向量集；
[0010] 将获取的位置近似RSS向量集通过使用k均值聚类算法，得到位置近似RSS向量集的k个聚类中心；
[0011] 将得到的位置近似RSS向量集的k个聚类中心作为全局指纹库的初始聚类中心；
[0012] 在线定位阶段包括如下步骤：
[0013] S21、计算实时RSS向量与全局指纹库的k个聚类中心的欧式距离，选择距离最小的q个全局指纹库的聚类中心对应的子区域，q的值为预先选取设定的；
[0014] S22、采用贝叶斯算法计算实时RSS向量被分到q个子区域中每个子区域的后验概率，然后选取后验概率最大的子区域作为定位分区的结果。
[0015] 进一步地，步骤S11具体包括如下步骤：在定位区域内均匀选取若干参考点，在每个参考点采集5个RSS向量，所有RSS向量构成全局指纹库。
[0016] 进一步地，步骤S12中对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，，并获得与所述k个子区域一一对应的k个聚类中心，具体步骤如下：
[0017] S121、将位置近似RSS向量集的k个聚类中心初始化全局指纹库的K个聚类中心；
[0018] S122、计算每个参考点的RSS向量到全局指纹库的k个聚类中心的欧氏距离；
[0019] S123、将参考点分配到最近的全局指纹库的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；
[0020] S124、重复步骤S122和S123，直到每个聚类中心不再变化或者变化幅度小于预设值，得到k个子区域和与之对应的k个聚类中心。
[0021] 进一步地，步骤S12中从全局指纹库中获取离每个AP位置最近的RSS向量的方法为：对于第j个AP，获取所有RSS向量中第j个AP信号最强的所对应的参考点位置作为第j个AP的最近位置，该参考点所对应的RSS向量即为离第j个AP位置最近的RSS向量，该参考点所对应的RSS向量作为第j个AP的位置近似RSS向量。
[0022] 进一步地，步骤S12中将获取的所有位置近似RSS向量通过使用k均值聚类算法，得到位置近似RSS向量集的k个聚类中心，具体步骤如下：
[0023] S125、随机选取k个聚类中心初始化位置近似RSS向量集的k个聚类中心；
[0024] S126、计算每个位置近似RSS向量到位置近似RSS向量集的k个聚类中心的欧氏距离；
[0025] S127、将位置近似RSS向量分配到最近的位置近似RSS向量集的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；
[0026] S128、重复步骤S126和S127，直到每个聚类中心不再变化或者变化幅度小于预设值，得到位置近似RSS向量集的k个聚类中心。
[0027] 进一步地，步骤S22中后验概率的计算公式为 其中zi代表第i个子区域，rsst代表采集到的实时RSS向量，P(zi|rsst)表示实时RSS向量被分到第i个子区域的后验概率，P(rsst|zi)是在第i个子区域内某一RSS向量为rsst的先验概率，P(zi)是随机分到第i个子区域的概率，p(rsst)是某一RSS向量为rsst的概率，P(zi)及p(rsst)均为常数。
[0028] 进一步地，P(rsst|zi)的计算方式如下，假设每个AP的RSS信号是独立不互相干扰的，那么
[0029] 进一步地， 的计算方式如下，由同一AP发射的无线信号在空间的分布能够近似用高斯分布来表示，通过统计第i个子区域内对于单个AP的RSS值的样本均值与方差，将第i个子区域的RSS信号分布拟合为高斯分布，其中ui为第i子区域内第j个AP的RSS值的平均值，δi为第i子区域内的第j个AP的RSS值的方差, 表示子区域内第j个AP的实时RSS值。
[0030] 有益效果
[0031] 与现有技术相比，本发明提供的定位分区方法，首先选取离每个AP位置最近的RSS向量并构成位置近似RSS向量集，然后使用k均值聚类算法得到位置近似RSS向量集的k个聚类中心来作为全局指纹库的初始聚类中心，从而保证结果全局最优，避免了初始聚类中心选取不当导致局部最优的问题；在定位分区时，首先用实时RSS向量到聚类中心的欧式距离选取聚类最小的q个子区域，进行一次初步筛选，然后结合贝叶斯算法计算实时RSS向量被分配到q个子区域的后验概率，选取后验概率最大的子区域作为定位分区的结果，该方法可更好的拟合RSS向量与物理位置的映射关系，解决了欧式距离无法很好拟合映射关系的问题。
具体实施方式
[0032] 下面结合具体实施方式对本发明作进一步详细的说明。
[0033] 本发明公开了一种基于贝叶斯-k均值聚类的室内定位分区方法，包括离线训练阶段和在线定位阶段，其中，离线阶段包括如下步骤，
[0034] S11、在定位区域内均匀选取若干位置参考点，在每个参考点采集RSS向量，具体实施时，在每个参考点采集5个RSS向量，所有RSS向量构成全局指纹库；
[0035] S12、对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，并获得与所述k个子区域一一对应的k个聚类中心，其中，k的值为预先选取设定的，如，本实施例中k值人为选定为6，对全局指纹库采用k均值聚类算法中k个初始聚类中心采用如下步骤得到：
[0036] 从全局指纹库中获取离每个AP位置最近的RSS向量，构成位置近似RSS向量集；其具体方法为，根据离AP越近RSS信号强度越强的原理，对于第j个AP，获取所有RSS向量中第j个AP信号最强的所对应的参考点位置作为第j个AP的最近位置，该参考点所对应的RSS向量即为离第j个AP位置最近的RSS向量，该参考点所对应的RSS向量作为第j个AP的位置近似RSS向量；j大于等于1且小于等于AP的总个数；
[0037] 将获取的位置近似RSS向量集通过使用k均值聚类算法，得到位置近似RSS向量集的6个聚类中心；
[0038] 将得到的位置近似RSS向量集的6个聚类中心作为全局指纹库的初始聚类中心；
[0039] 在线定位阶段包括如下步骤，
[0040] S21、计算实时RSS向量与全局指纹库的6个聚类中心的欧式距离，选择距离最小的q个全局指纹库的聚类中心对应的子区域，q的值为预先选取设定的，本实施例中q值为3；
[0041] S22、采用贝叶斯算法计算实时RSS向量被分到3个子区域中每个子区域的后验概率，然后选取后验概率最大的子区域作为定位分区的结果。
[0042] 本实施例中，步骤S12中对全局指纹库采用k均值聚类算法，通过无监督学习自动将定位区域划分为k个子区域，并获得与所述k个子区域一一对应的k个聚类中心，具体步骤如下：
[0043] S121、将位置近似RSS向量集的k个聚类中心初始化全局指纹库的K个聚类中心；
[0044] S122、计算每个参考点的RSS向量到全局指纹库的k个聚类中心的欧氏距离；
[0045] S123、将参考点分配到最近的全局指纹库的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；重新计算每个子区域对应的聚类中心的方法为：计算每个子区域内所有的RSS向量的平均值，用该平均值作为该子区域的聚类中心；
[0046] S124、重复步骤S122和S123，直到每个聚类中心不再变化或者变化幅度小于预设值，得到k个子区域和与之对应的k个聚类中心。
[0047] 本实施例中，步骤S12中将获取的所有位置近似RSS向量通过使用k均值聚类算法，得到位置近似RSS向量集的k个聚类中心，具体步骤如下：
[0048] S125、随机选取k个聚类中心初始化位置近似RSS向量集的k个聚类中心；
[0049] S126、计算每个位置近似RSS向量到位置近似RSS向量集的k个聚类中心的欧氏距离；
[0050] S127、将位置近似RSS向量分配到最近的位置近似RSS向量集的聚类中心所在的子区域，重新计算每个子区域对应的聚类中心；重新计算每个子区域对应的聚类中心的方法为：计算每个子区域内所有的位置近似RSS向量的平均值，用该平均值作为该子区域的聚类中心；
[0051] S128、重复步骤S126和S127，直到每个聚类中心不再变化或者变化幅度小于预设值，得到位置近似RSS向量集的k个聚类中心。
[0052] 本实施例中，步骤S22中后验概率的计算公式为 其中zi代表第i个子区域，rsst代表采集到的实时RSS向量，P(zi|rsst)表示实时RSS向量被分到第i个子区域的后验概率，P(rsst|zi)是在第i个子区域内某一RSS向量为rsst的先验概率，P(zi)是随机分到第i个子区域的概率，p(rsst)是某一RSS向量为rsst的概率，P(zi)及p(rsst)均为常数。P(zi)的值为1/q，本实施例中为1/3，p(rsst)的值为1/m，m为全局指纹库中RSS向量的总个数。
[0053] 其中，P(rsst|zi)的计算方式如下，假设每个AP的RSS信号是独立不互相干扰的，那么
[0054] 其中， 的计算方式如下，由同一AP发射的无线信号在空间的分布能够近似用高斯分布来表示，通过统计第i个子区域内对于单个AP的RSS值的样本均值与方差，将第i个子区域的RSS信号分布拟合为高斯分布， 其中ui为第i子区域内第j个AP的RSS值的平均值，δi为第i子区域内的第j个AP的RSS值的方差,表示子区域内第j个AP的实时RSS值。
[0055] 算法的具体实现如下：
[0056]
[0057]
[0058] 统计分区准确率，和经典的k均值算法进行对比。
[0059] 计算聚类效果评估指标Dunn值，Dunn指标值大，意味着存在致密且分离很好的聚类，因为聚类间的距离大，而聚类的直径小，Dunn指标越大也越不会出现局部最优的情况计算公式如下：
[0060]
[0061] 其中，d(Ci,Cj)＝为Ci和Cj之间的不相似函数，如下所示：
[0062]
[0063] diam(c)为聚类C的直径，如下公式所示：
[0064]
[0065] 通过比较聚类分区率和Dunn值，本专利提出的方法的聚类效果均由于经典的k均值算法。
[0066] 以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。
