基于改进HC算法的WiFi室内楼层识别方法*

毛万葵， 吴 飞， 张玉金， 章裕润

(上海工程技术大学 电子电气工程学院，上海 201620)

0 引 言

随着无线局域网(WiFi)技术的成熟，在一些大型的室内场所(比如：大型超市、室内商场、地下车库等)已实现WiFi全覆盖，基于WiFi的室内定位技术，逐渐成为室内定位服务的主要技术之一[1～3]。

但传统的室内定位技术主要还是集中在二维平面上的定位，而现在随着发展，对于二维平面的室内定位信息已经无法满足人们的需求，人们开始越来越关注基于楼层的三维空间上的定位服务，例如商场广告推送、立交高架交通导航、紧急情况下的人员楼层定位等。虽然基于楼层的室内定位服务，具有很好的市场应用价值，但目前却极少有研究者愿意关注这方面的研究。文献[4]提出了一种基于WiFi指纹定位的楼层定位方法，该方法需要借助气压计、加速度计等硬件设备获取定位目标的海拔高度辅助定位。文献[3]提出的基于快速部署的室内多楼层定位算法，可以根据实际的需要对设备进行部署安装，对不同楼层的WiFi信号进行差分计算，实现对楼层的定位。无法进行大范围的推广。文献[6,7]都是基于K均值聚类(K-means)算法的室内定位楼层判别算法，增加了楼层定位的复杂度。文献[8]基于室内地图环境信息的多楼层WiFi定位技术，在离线阶段建立地图环境信息，并且对指纹数据进行聚类，在线阶段采用设置阈值的方法对楼层进行判断，结合地图模型和机器学习的方法算出位置，增加了系统在离线阶段指纹数据库建立的复杂度。

本文通过结合密度分层的思想，对传统的层次聚类算法进行改进，并利用数据切分的方法，将离线阶段的指纹数据进行切分，变成若干较小数据集的聚类，这样不仅提高了楼层识别的准确度，而且降低了楼层定位的计算复杂度。

1 基于WiFi的楼层判别方法

基于WiFi的楼层定位判别方法主要是由离线阶段和在线阶段组成。离线阶段，通过对定位区域网格划分、设置采样点、接收信号强度(received signal strength,RSS)采集、生成标准化的指纹数据库。然后结合具体的楼层指纹信息，对终端接收信号进行聚类，生成楼层指纹数据。在线阶段，将用户实时采集的指纹信息，与指纹数据库进行映射，最后定位出真实楼层信息。楼层定位方案如图1所示。

图1 楼层定位方案图

2 层次聚类算法

层次聚类(hierarchical clustering,HC)算法是比较实用的一种聚类算法，可以将其分为两大类：凝聚聚类和分裂聚类[9]。

HC算法主要是根据两个不同类之间的矩阵相似度进行计算。相似度的计算方式有很多不同的解法。

1)最短距离法：通过计算类中两点之间的距离，然后将最短的两点之间距离作为类的距离

dA,B=min{d(xa-xb)}

(1)

式中dA,B为类A和B类之间的欧氏距离，xa和xb分别是对应两个类中的样本采样点。

2)最长距离法：和最短距离法比较类似，但是不同的是将最长的两点之间的聚类作为类的距离

dA,B=max{d(xa-xb)}

(2)

3)平均距离法：是计算两个类中所有两点之间距离，将距离的平均值当作类之间的距离

dA,B=avg{d(xa-xb)}

(3)

层次聚类算法虽然计算简单、聚类效果好，但是需要计算相似矩阵。时间复杂度较大，为O(n2·logn)，其中，n为数据集大小。普通的HC算法对离群点比较敏感，聚类的精度也比较容易受其影响[10～12]。

3 改进的层次聚类算法

为了减小数据中的离群点对聚类结果的影响，改进的算法通过随机删除密度较小的样本点，只对剩下来的数据进行层次聚类。常用的做法是选取原始数据中的8 %～12 %左右的数据进行剔除[13]。因为密度较大的数据点都分布在类的中心部位，而这些点分类都是比较容易的。而且为了避免对一些整体密度都比较小的类造成误判，改进算法特意将密度较小的点单独筛选出来划分为一层，然后再分层进行聚类计算。

算法的具体实现步骤如下：

1)计算每个数据点的密度值

密度值是依据某个区域内所有点的数目的总和，设数据集为D，密度ρi的计算公式为

(4)

式中x的取值服从二项分布。lij为点i和点j之间的直线距离，d为截断距离。

2)选择偏离点

选出偏离点后，从整体数据中对偏离点进行剔除，剩下的数据组成新的数据集P

(5)

式中ρ0为初始截断密度值，可以初始设定一个值，然后根据公式就可以求出密度小于截断密度的点的个数n即为偏离点的数据集大小。

3)将数据集P中的数据按密度从小大排列，提取出最大的1/4数据，重新组成数据集T，对数据集T进行层次聚类，类别数记为K。

4)同样地，从数据集P中选出最小的1/4数据，组成一个新的数据集S。对数据集S聚类，类别数记为K。

5)经过步骤(3)和步骤(4)处理后，P中还有部分数据，这部分的数据密度是介于T和S之间，记为H。这里将H中的每个数据点都视为一个单独的类，然后结合步骤(3)和步骤(4)的聚类结果，对聚类结果进行合并，使得最终聚类的数目为K/2。

6)将偏离点与P中的类进行比较，分别划分到不同的类中，最终实现对数据集D的聚类。

基于密度的改进HC算法，计算简单，没有复杂的公式推导。算法初始阶段就对偏离点进行剔除，减少了偏离数据对聚类结果的干扰，使得聚类的过程更加的稳定。同时，改进的HC算法将数据集进行划分，分别在不同密度层进行聚类，提高了算法对密度不均匀数据的处理能力。

但改进后的算法和传统聚类算法一样，要将所有数据一次性读入计算机内存，使得算法对内存的要求较高，这样复杂的计算导致该算法无法在大规模的数据集上进行很好的应用。但是生活中，每天的定位数据都是非常庞大的，仅仅依靠密度的聚类方法很难快速的对大规模数据进行处理。所以本文在上一小节基于密度的聚类方法的基础上继续进行改进，加入数据切分的思想，使得算法能够处理大规模的定位数据。

基于数据切分思想的HC算法，是将大的数据集切分成不同的小的数据块。然后通过合并每个数据块的特征元素，得到全局特征，再对原始数据依次聚类[14]。假设初始数据集D的大小为n，将D切分成m个数据块{D1,D2,…,Dm}，但是要满足如下公式

D1∪D2∪,…∪Dm=D,Di≠∅

(6)

Td(n)=max(f(n1),f(n2),…,f(nm))

(7)

因为n>ni，而且f(n)'>0,所以Td(n)

通过上面的分析知道，数据块被切分后可以节省系统的计算开销，但每个数据块切分大小的不同也会影响计算效率。切分的太粗，导致在子数据集中的特征提取耗费更多的时间;切分的太细，系统在全局特征合并的时候，反而会增大时间开销。所以,需要找一个平衡点，使得算法的效率达到最大化。

图2中所示的实验中数据集的大小分别为0.3×103,1×104,1×105,1×106，分类的类别数分别是2,3,6,6。从图中可以看出，不同的切分大小与聚类时间之间都存在一个极值点，极点的范围主要分布在50～80之间。说明数据集的大小和类别数对聚类时间的影响不大，所以,可以按照这样的规律进行数据块大小的切分。

图2 数据块切分与聚类时间关系

如图3是为了说明数据被切分后对最终聚类结果的影响，从图中数据被切分成不同的大小后，其对应的聚类结果都没有太明显的波动。综合以上说明改进算法对数据进行切分是合理有效的。

图3 数据块大小与聚类F值关系

4 仿真与验证

4.1 实验环境

本文通过实验来验证楼层定位方法准确度和效率的提高，选择的实验环境为本校实训楼1号楼，共有4层楼，每层楼的构造基本相同，整栋楼经过统计记录共有68个无线访问节点(access point,AP)，实验用的信号采集设备为联想(Lenovo)天逸310笔记本，通过内置无线网卡和自主开发的信号采集软件进行信号采集。

实验共选取了812个指纹采样点，每个指纹采样点处连续采集120组数据，时间间隔为1 s，以1.5 m×1.5 m作为采样间隔，其中,以3楼为例指纹采样点的平面分布如图4所示。

图4 实验区指纹采样点平面

为了将定位效果更好的量化，定义一个用来判断误差的函数为

(8)

式中 (xi,yi)为实际物理位置，(x'i,y'i)为测估算位置坐标。

4.2 实验结果分析

表1为实验设定的相关参数。

表1 改进HC算法实验参数

如图5(a)所示为各个算法在不同楼层上的平均定位误差，其中经典的CURE和ROCK算法要比传统的K-means算法在定位误差上要好一些，但是改进的层次聚类算法的楼层定位误差要明显小于前面三种算法，误差均值在1.212 m左右，比其他三种算法的平均误差降低了54.7 %,48.16 %,48.78 %。

表2所示为不同算法的楼层识别率，改进HC聚类算法因为采用了密度分层的方法降低了异常值对聚类结果的影响，增大了楼层间的聚类差异性，提高了楼层识别率，准确均值可以达到95.25 %。

表2 不同算法楼层识别率

如图5(b)所示为不同算法的楼层定位时间对比图。可以看出传统的K-means的聚类所花时间最长，CURE和ROCK次之，改进的HC算法聚类时间最短，平均值为16.2 s。综合以上所述，可以说明本文提出的改进的HC算法在楼层判别率和楼层定位效果上都要好于传统K-means、CURE和ROCK聚类算法。

图5 不同算法的平均定位误差与定位时间

5 结 论

通过密度分层的思想对定位数据进行敏感数据剔除、密度大小分层，对不同密度层分别进行不同的层次聚类，解决了普通聚类算法对异常值敏感的缺陷，提高了终端的定位效果。同时为了降低日益增长的大规模定位数据带来的计算复杂度高的问题，结合了数据切分的思想。离线阶段时将定位数据进行切分，将数据集进行细化，降低了计算时间复杂度，节省了楼层判别的时间。从实验结果上来看，与基本的聚类算法相比，改进的HC算法无论在楼层定位效率，还是楼层判别准确度上都有提高。