基于室内空间WIFI信号的用户定位分析研究计算机科学与技术专业.docx

《基于室内空间WIFI信号的用户定位分析研究计算机科学与技术专业.docx》由会员分享，可在线阅读，更多相关《基于室内空间WIFI信号的用户定位分析研究计算机科学与技术专业.docx（41页珍藏版）》请在三一办公上搜索。

1、前言3第一章绪论51.1 研究背景及其意义51.2 室内定位技术概述51 3位技研九现状.61.1.1 基于信号传播模型的定位方法61.1.2 基于位置指纹识别的定位方法71.4 研究目标91.5 研究内容91.6 论文结构10第二章相关技术与工具112.1 相关技术112.1.1 KNN112.1.2 RandomForest112.1.3 xgboost122.2 相关工具13第三章问题定义143.1 基本概念143.2 位置指纹定位方法15第四章基于RF和XgbooSt的融合定位算法174.1 基于多分类的定位算法174.1.1 位置指纹库构建174.1.2 12l184.1.3 RF模

2、型训练214.2 基于二分类的定位算法224.2.1 特征工程234.2.2 Xgboost算法244.2.3 Xgboost模型训练254.3 多分类和二分类的融合定位算法271.1 .1训练阶段274.3 2/isyL28第五章实验与结果分析285.1 实验场景295.2 实验数据1.1 .1.训练集295.22 测试集315.23 定位结果315.3 数据分析325.4 实验过程335.6 实验结果34第六章总结与展望356.1 总结366.2 展望36参考文献37致谢错误!未定义书签。摘要如今，随着无线网络和计算技术进入快速发展阶段，在日常生活中人们对于具体位置信息的需求也愈加迫切，基

3、于位置的服务和应用由此应运而生。随着基于位置的服务的流行，定位技术也逐渐成为了科研热点。现阶段，GPS技术被广泛应用于室外定位领域。而室内环境普遍狭窄，障碍物较多，这些都会对GPS造成干扰，使得GPS出现定位错误。因此，GPS无法实现人们对室内定位的需求。与其他定位技术相比，WIFI具有传输速度快，覆盖范围广，部署成本低，便于移动，在非视距的条件下仍然可以传播等优势，这使得WIFI技术在众多无线定位技术中脱颖而出。在日常生活中，当用户在商场中使用支付宝付费时，我们可以通过用户的手机获得用户当前的GPS定位，接收到的WIFI信息以及（二维码）所在的商店信息。在基于这些信息进行必要的数据挖掘和机器

4、学习训练后，利用WlFl定位算法精确定位出用户所在的店铺。在用户付费前向其推送相关的商品或优惠券，这可以有效促进用户的消费，改善用户的购物体验。为实现在商场中对用户的精确定位，本文基于位置指纹识别算法，设计了一个针对性的集成模型。首先利用基于随机森林的多分类模型和基于Xgboost的二分类模型进行定位，然后通过对上述模型的有效融合提出了一个基于随机森林和XgbOOSt的融合定位算法。在基于真实数据集对本文所提出的集成学习模型和融合模型进行评测后，我们发现，本文所提出的WlFl定位算法在静态情况下的定位准确度可以达到91%。相较于传统的定位算法，其定位精度得到了有效的提高。关键字：室内定位；Wl

5、Fl技术；位置指纹；机器学习AbstractToday,wirelessnetworksandcomputingtechnologyaremovingintorapiddevelopment.Atthesametime,peoplesdemandforspecificlocationinformationbecomesmoreandmoreurgentindailylife,thelocation-basedservicesandapplicationsemergeaccordingly.Withthepopularityoflocation-basedservices,positioning

6、technologyhasgraduallybecomearesearchhotspot.Atpresent,GPSiswidelyusedinthefieldofoutdoorpositioning.Theindoorenvironmentisgenerallynarrowandcomplicated,whichinterfereswithGPSandmakesGPSpositioningerror.Therefore,GPScannotmeettheneedsofindoorpositioning.Comparedwithotherpositioningtechnologies,WIFIh

7、asmanyadvantages,suchasfasttransmissionspeed,widecoverage,lowdeploymentcost,easytomove,andcanbetransmittedundernon-visualconditions,whichmakeWIFIbecomeanexcellentchoiceinindoorwirelesspositioningtechnology.Indailylife,whenpeopleusemobilephoneintheshoppingmall,wecangetthecurrentGPSlocationofusers,the

8、WIFIinformationreceivedbythephoneandthestoreinformationinthemall.Afterthenecessarydataminingandmachinelearningtrainingbasedonthisinformation,theWIFIlocationalgorithmisusedtoaccuratelylocatethestorewheretheuseris,andpushrelevantcouponsbeforepayment,whichcaneffectivelypromotetheconsumptionofusersandgr

9、eatlyimprovetheusersshoppingexperience.Inordertorealizeaccuratepositioningofusersinshoppingmalls,thispaperdesignsatargetedintegrationmodelbasedonlocationfingerprintidentification.Firstofall,usingmultipleclassificationmodelbasedonrandomforestandthebinaryclassificationmodelbasedonxgboosttolocate,andaf

10、usionlocalizationalgorithmbasedonRFandxgboostisproposedthrougheffectivefusionoftheabovemodel.Theintegrationlearningmodelandfusionmodelproposedinthispaperareevaluatedbasedonrealdatasets,theexperimentsshowthatthepositioningaccuracyoffusionlocationalgorithmbasedonRFandxgboostcanreach91%instaticconditio

11、n.Comparedwiththetraditionallocalizationalgorithm,thelocalizationaccuracyofthefusionalgorithmproposedinthispaperisimprovedeffectively.Keywords:indoorpositioning;WIFltechnology;Positionfingerprint;Machinelearning如今，无线网络和计算技术进入快速发展阶段，与此同时，在日常生活中人们对于具体的位置信息的需求也愈加的迫切，基于位置的服务和应用由此应运而生。随着基于位置的服务的流行，定位技术也逐

12、渐成为了科研热点。现阶段，GPS技术被广泛应用于室外定位领域。然而，由于室内环境普遍较为狭窄且复杂多变，人员的数量、室内的空间大小、建筑物的稀疏程度以及温度等多种因素都可能会对GPS信号造成干扰，使得GPS定位出错甚至失效。因此，GPS无法实现人们对室内定位的需求。如今，WIFl信号普遍存在于办公室、家庭、商场、机场、医院等室内环境中。因此，基于WlFl的室内定位技术并不需要事先在定位区域内安装任何硬件设备，便可以实现室内定位，这可以有效降低在室内部署定位系统的难度以及建设成本。除此之外，与其他定位技术相比，WIFl技术还具有传输速度快,覆盖范围广，部署成本低，便于移动，在非视距的条件下仍然可

13、以传播等优势。本文对室内定位技术进行了深入探讨，主要分析了现有的三种室内定位方法包括基于特定设备的定位方法、基于移动传感器的定位方法以及基于WlFI信号的定位方法，着重介绍了基于WIFI信号的定位方法中的两个典型方法：“基于信号传播模型的定位和基于位置指纹识别算法的定位”。其中，基于位置指纹识别算法的定位方法由于实现简单，成本低，定位精确度高，可扩展性强等优势在许多室内定位方法中崭露头角，逐渐成为室内定位领域的主流方法。在日常生活中，当用户在商场中使用支付宝付费时，我们可以通过用户的手机获得用户当前的GPS定位，接收到的WIFI信息以及（二维码）所在的商店信息。在基于这些信息进行必要的数据挖掘

14、和机器学习训练后，利用WIFI定位算法精确定位出用户当前所在的店铺。在用户付费前向其推送相关的商品或优惠券，这可以有效促进用户的消费，改善用户的购物体验。为实现在商场中对用户的精确定位，本文基于位置指纹识别算法，设计了一个针对性的集成模型。首先利用基于随机森林的多分类模型和基于Xgboost的二分类模型进行定位，然后通过对上述模型的有效融合进一步提高了定位的精确度。本文的主要工作及创新点如下：(1)深入研究了当前的室内定位技术，着重介绍了三种室内定位方法以及两个典型的WIFl室内定位方法，对WlFl室内定位技术的研究现状进行了分析，为本文的定位算法寻找理论支撑。(2)通过对位置指纹识别算法的研

15、究，针对其存在的局限性，在传统的位置指纹识别算法中，引入机器学习算法，设计了一个针对性的集成模型。首先利用基于随机森林的多分类模型和基于Xgboost的二分类模型进行定位，然后对上述模型进行有效融合，从而进一步提高定位精确度。(3)基于真实数据集对本文所提出的集成学习模型和融合模型进行评测，验证相关算法的有效性。第一章绪论1.1 研究背景及其意义如今，无线网络和计算技术进入快速发展阶段，与此同时，在日常生活中人们对于具体的位置信息的需求也愈加迫切，基于位置的服务和应用由此应运而生。“基于位置的服务(LOCatiOnBasedService,LBS)指的是利用定位技术获取用户的定位信息，根据当前

16、用户的需求，为其提供所需要的特定服务”。现阶段在导航、物流、商铺促销、个人跟踪等领域，LBS均展现了不可忽视的存在。随着基于位置的服务的流行，定位技术也逐渐成为了科研热点。现阶段，GPS技术被广泛应用于室外定位领域，主要应用在室外高层建筑较为稀疏，总体环境较为空旷的地区。虽然可以使用GPS技术定位出移动设备处于哪一建筑内，但当人们处于室内环境下时，希望获得的是更加精确的室内位置。然而，室内环境普遍较为狭窄且复杂多变，人员的数量、室内的空间大小、建筑物的稀疏程度以及温度等多种因素都可能会对GPS信号造成干扰。因此，如果在室内传播GPS信号，可能会发生反射、散射、衍射以及折射现象，由此产生的多径效

17、应和阴影效应在很大程度上会减弱GPS的信号强度，使得GPS定位出错甚至失效，难以对用户进行准确的定位。因此，GPS无法实现人们对室内定位的需求，如何进行准确的室内定位在现阶段仍然是一个有待解决的难题。截至目前为止，相对于发展的较为完善的室外定位技术，室内定位技术还面临着诸多的困难与挑战3L在日常生活中，人们大部分时间都是在办公室、医院、商场、学校等室内环境中进行活动，人们对于室内定位服务的需求与日俱增，与此同时，许多的室内定位技术逐渐进入大众的视线。1.2 室内定位技术概述室内定位技术依据其使用的介质不同，主要分成3类:基于特定设备的定位方法、基于移动传感器的定位方法以及基于WIFI信号的定位

18、方法。基于特定设备的定位方法。基于特定设备的定位方法主要通过收集目标对象所持有的特定设备发送的信号波，根据已知的接收器的位置信息来估计目标对象的位置。特定设备主要指的是可以发送和接收信号，具有计算能力，用于满足用户特定需求的设备，包括超声波发射器，红外线发射器，RFlD设备等。基于移动传感器的定位方法。随着智能手机的迅速发展，移动传感器的种类也逐渐丰富起来。这些移动传感器计算通信能力强，包含的数据丰富，可以为室内定位提供丰富的信息资源。基于移动传感器的定位方法中应用较为广泛的便是丘人航位推算（PedeStrianDeadReckoning,PDR淀位,“首先通过加速度传感器检测行人的步数，并计

19、算出步长，根据典型的计步器原理以及步长可以估算出行人的位移信息。然后通过磁力计或陀螺仪或两者的组合计算出行人的航向角，最后获取人体移动的相对位置，从而实现定位”。基于WIFI信号的定位方法。如今无线网卡是笔记本电脑、智能手机等大部分移动通信设备中必备的配置，这使得WIFI信号普遍存在于办公室、家庭、商场、机场、医院等室内环境中。因此，基于WlFl的室内定位技术并不需要事先在定位区域内安装任何硬件设备，便可以实现室内定位，这样有效降低了在室内部署定位系统的难度以及建设成本。对比分析。基于特定设备的定位方法虽然可以基本满足室内定位的需求,但是，这些设备需要提前在室内进行部署，需要花费额外的设备费用

20、以及安装费用。基于移动传感器的定位技术虽然可以获得较高的定位精度,但需要花费较大的人力，财力，同时可能会涉及用户的隐私数据，不易于推广。与其他定位技术相比，WIFl技术具有传输速度快，覆盖范围广，部署成本低，便于移动，在非视距的条件下仍然可以传播等优势，这使得基于WIFl的定位方法在众多无线定位方法中脱颖而出。1.3 WIFI定位技术研究现状基于WIFI的室内定位方法主要分为两种：基于信号传播模型的定位方法以及基于位置指纹识别的定位方法。1.3.1 基于信号传播模型的定位方法基于信号传播模型的定位方法主要依据WIFI信号在空间中传输时的能量衰减特性，建立相应的WIFI信号传播模型（如对数.距离

21、路径衰减模型）o利用该模型可以建立WlFl信号和距离之间的映射关系，将WIFl信号转换为距离测量值。在定位阶段，将待定位设备接收到的WIFI信号输入到该模型中便可以得到待定位设备与已知位置的多个AP的相对距离，从而推算出待定位设备的位置。由于WlFI信号在传播时并不稳定，通常情况下会产生不对称的衰减。除此之外,障碍物的大小、材质、种类、多路径传播、物体朝向等因素可能会在WlFl信号传输的过程中对其造成影响，使得WIFI信号产生一些折耗，我们无法通过数学模型对这些折耗进行准确的估计。因此，基于信号传播模型的定位方法其定位准确度难以得到有效的保证。1.3.2 基于位置指纹识别的定位方法基于位置指纹

22、识别的定位方法，简称位置指纹定位方法，主要通过学习位置与指纹(这里的指纹指的是任何能够用来区分位置的特征，如WlFI信号强度)之间的映射关系，利用一定的匹配算法来估计目标对象的位置。位置指纹定位方法主要分为离线阶段和在线阶段，如图1-1所示，图中a为离线阶段，b为在线阶段。Ml,ylMtSSUSS12.图1-1位置指纹识别算法流程图(1)离线训练阶段，从待定位区域中的各个参考点采集指纹信息(RSShRSSk,RSSI),在对指纹信息进行预处理后，建立这些指纹信息与位置信息之间的映射关系，并将其存入数据库中，构建相应的位置指纹库；(2)在线定位阶段，需要我们从待定位区域中的某个未知位置实时采集指

23、纹信息(RSShRSSj,RSSI,),通过一定的指纹匹配算法，将其与指纹库中的指纹信息进行匹配，将指纹库中与目标样本最相似的指纹所对应的位置作为预测的位置输出。常见的指纹匹配算法主要分为两类：确定性的定位算法以及概率性的定位算法。(1)确定性的定位算法在确定性的定位方法中，指纹库中的每一个位置对应于一个确定的bool值，表明目标对象是否在这个位置。基本思路：通过计算出待定位地点的RSS观测值与指纹库中存储的指纹向量的欧氏距离,将与其距离最近的一个或K个指纹向量对应的位置坐标进行加权后作为待定位地点的位置坐标。(2)概率性的定位算法在概率性的定位方法中，指纹库中的每一个位置对应于一个后验概率，

24、表明目标对象在这个位置上的概率。基本思路：在离线阶段，从安装在各个位置的AP中采取RSS样本，这些样本组成信号强度向量,利用这些信号强度向量建立相应位置的概率分布模型；在定位阶段,根据待定位点接收到的信号强度向量，采用贝叶斯公式计算这些信号强度在指纹库中不同位置上的后验概率,将后验概率较大的一个或K个位置点加权后作为定位目标的估计位置(3)机器学习算法近年来，许多机器学习算法开始被引入到指纹识别算法中，包括KNN算法，随机森林算法等。下面简要介绍一下三种使用了机器学习算法的WIFl定位方法。基于主成分分析的WlFl室内定位方法。首先对训练数据进行PCA主成分分析，将训练样本从高维空间映射到低维

25、空间。然后再利用KNN算法，从训练样本中找到与目标样本最相似的K个指纹向量。最后对这K个指纹向量对应的位置坐标进行加权后作为目标样本最终的预测位置。实验结果表明，在KNN算法的基础上引入PCA主成分分析后，算法的定位精度有明显提升。基于K-means和KNN的WIFI室内定位方法。在训练阶段，通过K-means算法对指纹库中的所有指纹向量进行聚类，得到每个类的聚类中心以及指纹库中每个指纹向量所属于的类别。在定位阶段，通过计算目标样本与各个聚类中心的距离，将目标样本归入到相应的类中。然后在该类中使用KNN算法，从中找出与目标样本最相似的K个指纹向量。最后对这K个指纹向量所对应的位置加权平均，作为

26、目标样本最终的预测位置。实验结果表明，将K-means和KNN算法进行融合后，在保证定位精度的前提下，有效缩短了定位所需要的时间。基于K-means和RandomForest的WIFI室内定位方法山。在训练阶段，通过K-means算法对指纹库中的所有指纹向量进行聚类,得到每个类的聚类中心以及指纹库中每个指纹向量所属于的类别。基于每一类的数据分别训练出一个最优的随机森林分类器。在定位阶段，通过计算目标样本与各个聚类中心的距离，将目标样本归入到相应的类中。然后使用该类中已训练好的随机森林分类器对目标样本进行二次分类，从而得到目标样本的预测位置。1.4 研究目标在日常生活中，当用户在商场中使用支付宝

27、付费时，通过用户的手机获得用户当前的GPS定位，接收到的WIFI信息以及（二维码）所在的商店信息。在基于这些信息进行必要的数据挖掘和机器学习训练后，利用一定的WIFI定位算法精确定位出用户所在的店铺，在用户付费前向其推送相关的商品或优惠券，从而有效促进用户的消费，改善用户的购物体验。为实现在商场中对用户的精确定位，我们设计一个针对性的集成模型，首先利用基于随机森林的多分类模型和基于Xgboost的二分类模型进行定位，然后对上述模型进行有效融合，从而进一步提高定位精确度。1.5 研究内容本文主要的研究内容如下：（1）深入研究了当前的室内定位技术，着重介绍了三种室内定位方法以及两个典型的WlFl室

28、内定位方法，对WIFl室内定位技术的研究现状进行了分析，为本文的定位算法寻找理论支撑。（2）通过对典型的位置指纹识别算法的研究，针对其存在的局限性，在传统的位置指纹识别算法中，引入机器学习算法，设计了一个针对性的集成模型。首先利用基于随机森林的多分类模型和基于Xgboost的二分类模型进行定位，然后对上述模型进行有效融合，从而进一步提高定位精确度。(3)基于真实数据集对本文所提出的集成学习模型和融合模型进行评测，验证相关算法的有效性。1.6 论文结构第一章，绪论。主要介绍了室内定位技术的研究背景及其意义，现有的三种室内定位技术以及WlFl定位方法的研究现状，论文的研究目标，研究内容以及论文结构

29、。第二章，相关技术与工具。主要介绍了本文所使用的相关技术，包括KNN算法，随机森林算法，XgbooSt以及本文所使用的工具库。第三章，问题定义。主要对接收信号强度(RSS),指纹以及位置指纹库等基本概念进行了符号化定义，并且介绍了如何使用位置指纹定位方法解决商场中的用户定位问题。第四章，基于RF和XgboOSt的融合定位算法。通过对数据以及问题的分析，详细介绍了本文所提出的基于RF和Xgboost的融合定位算法，包括算法提出的过程以及主要思路。第五章，实验与结果分析。主要介绍了本文的实验场景，实验数据，数据分析，实验参数，实验过程以及实验结果。基于真实数据集对本文所提出的集成学习模型和融合模型

30、进行评测，验证了相关算法的有效性。第六章，总结与展望。对本文研究所取得的成果进行了总结，指出本文算法的优势与不足，并对下一步的工作进行展望和分析。第二章相关技术与工具本章主要对本文中所使用到的相关技术，包括KNN,RandomForest,Xgboost以及工具进行简要的介绍。2.1 相关技术2.1.1 KNNKNN是一种常用的监督学习方法，常用于分类，其工作过程非常简单：存在一个训练集，已知训练集中每个数据所对应的标签。给定没有标签的测试样本，将测试样本的特征与训练集中对应的特征进行相互比较，从训练集中找出与测试样本距离最近的K个训练样本，然后基于这K个训练样本的标签信息对测试样本进行预测。

31、对于分类任务，通常使用简单投票法，将这K个训练样本中出现最多的类别作为测试样本最终的类别标记；对于回归任务，通常使用简单平均法，对这K个训练样本的实值输出标记求平均后作为测试样本的预测结果。与其他匹配算法相比，KNN算法简单，便于理解。在训练阶段没有对模型进行显式的训练，只是将训练样本保存起来，因此训练开销为零。2.1.2 RandomForest随机森林是一种多功能的机器学习算法，以决策树为基学习器构建Bagging集成，并在决策树的训练过程中进一步引入了随机属性选择。基本流程如图2-1所示。图2-1随机森林基本流程图在随机森林算法中，首先使用自助采样法,对原始数据集进行有放回的随机采样,每

32、个采样集的采样过程相互独立，然后基于每个采样集训练出一棵决策树。由于每棵决策树基于的采样集相互独立并且互不相同，所以学习到的特征并不完全相同，这样可以有效保证决策树之间的独立性和多样性。同时，由于随机森林中的每棵决策树之间是独立构建的，所以在处理大规模数据时，可以同时并行构建大量的决策树，从而有效提高随机森林的训练效率。随机森林算法在训练决策树的过程中引入了随机属性选择,一方面可以增强决策树之间的差异性，使得最终集成的随机森林模型的泛化性能得到进一步提升。另一方面，在训练样本特征维度很高的时候，通过随机选择部分特征训练决策树，可以使得随机森林模型被很高效的训练。在决策树都训练完毕后，通过投票法

33、或平均法对多个决策树的预测结果进行集成。随机森林，作为集成学习的代表方法，简单，计算开销小，易于实现。通过将多个“好而不同”的决策树进行集成，大大提高了模型的稳定性和泛化能力。随机森林,常被用来解决回归和分类任务。同时.，它还可以用于计算特征的重要性，通过选取重要特征来近似表示原始数据集，从而实现对高维数据的降维。2.1.3 XgboostXgboost（ExtremeGradientBoosting）是提升树（BT）的一种，在梯度提升树（GBDT）的基础上进行了改进和扩展。其中，提升树（BT）是以决策树为基学习器的加法模型，通过前向分步算法逐一训练决策树。首先使用原始训练数据以及真实标签训练

34、决策树，然后使用这棵决策树对训练集进行预测，将当前决策树的预测结果与训练数据的标签值相减得到残差，将残差作为训练数据的标签训练下一棵决策树。以此类推，直到决策树的棵数或某些指标（如验证集上的误差）已满足条件，则停止训练。在提升树（BT）算法中，通过对决策树的训练不断拟合残差，使得每一轮训练过程中拟合的残差逐渐减小，最后将多个决策树的预测结果累加从而得到最终的预测结果。梯度提升树（GBDT）,以CART回归树为基学习器，其训练过程与提升树类似,只是在训练过程中将损失函数的负梯度在当前模型中的值作为残差的近似值,将其作为训练数据的新标签进行下一轮训练。Xgboost是在GBDT的基础上进行了改进与

35、扩展，主要改进了以下几点：(1)传统GBDT只能以CART为基学习器，Xgboost的基学习器既可以是树模型也可以是线性模型“9。(2) XgboOSt允许自定义损失函数，但要求损失函数一阶和二阶可导；(3) XgbOOSt对损失函数进行二阶泰勒展开，有效提高了模型的泛化能力；(4)为了避免过拟合，XgbOOSt在目标函数之外显式的加上了正则项，从整体上有效控制了模型的复杂度；(5)在树结点进行分裂时，Xgboost和GBDT算法都是通过计算分裂带来的增益来选择一个最优分割点对当前结点进行分裂。但与GBDT算法不同的是，Xgboost在对增益的计算公式中添加了阈值7和系数X,前者在树构建的过程

36、中进行了预剪枝从而限制了树的生成，后者对叶子结点的值进行了平滑，这样可以防止过拟合；(6)xgboost在每棵树的训练过程，通过从特征集中随机选取特征对树进行训练,大大减少了计算，同时，也起到了防止过拟合的作用；(7)在对树结点进行分裂时，传统的GBDT算法采用贪心法，枚举出当前结点包含的每个特征的所有潜在分割点，从中选择一个最优分割点对当前树结点进行分割。但当数据量较大，无法一次载入内存时，贪心算法会产生很大的计算开销，算法的效率较低。为了解决这一问题，XgbOOSt提出了一个近似算法，根据百分位法从结点包含的所有潜在的特征分割点中选出候选分割点，然后只需要计算这些候选分割点的增益，从中选择

37、增益最大的分割点作为最佳分割点对当前树结点进行分割；(8)在寻找最佳分割点对当点树结点进行分割时，传统的GBDT算法需要对每个特征值进行排序，并且这一步骤会在每次结点分割时重复进行，耗时耗力。针对这一问题，Xgboost在训练之前，对数据的每个特征进行了预排序，并以块的形式将排序好的特征保存在内存中，在每次选择最佳分割点时重复使用，这样有效减少了因特征排序而带来的计算量。2.2 相关工具本文主要使用了PythOn中的SkIearn模块以及XgbOoSt模块。其中，SldeanI模块中封装了许多用于解决分类，回归，降维等任务的机器学习算法，包括KNN算法，随机森林算法，PCA等。XgbooSt是

38、一个开源的工具包，主要用于构建并行的boostedtree,学习效果优良，训练速度快。第三章问题定义在本章中，主要对接收信号强度（RSS）,指纹以及位置指纹库等基本概念进行了符号化定义，并介绍了如何使用位置指纹定位方法解决商场中的用户定位问题。3.1基本概念定义1接受信号强度RSS：RSS作为信号的强度特征常被应用于定位中，RSS的值越大，表明信号的强度越大。单位是dbm,表示功率的绝对值。假设有一个路由器端在发送WIFI信号，距其不同距离的移动设备接收到的WIFI信号强度RSS可以表示为：（八RSS=L+10nIg+G（式3-1）其中，P。是当移动设备和路由器之间的距离为d0时接收到的Wif

39、i信号强度，称为路径损耗系数，d表示移动设备和路由器之间的真实距离，G是一个取决于环境和频率的常数，与传输距离无关1。定义2指纹：在位置指纹定位算法中，只耍是能够用来区分位置的特征都可以被作为指纹，如某个位置上接收的信号强度（RSS）,接收信号的时间，或者接收的信号结构等，我们也可以对其进行组合一起作为指纹。通常，我们将用户接收到的WlFI信号强度段作为指纹p。出4-115,-30,值越大，信号越强。定义3位置指纹库：在位置指纹定位算法中，我们首先需要建立一个位置指纹库，位置指纹库中包含了指纹信息以及对应的位置信息，通常，一个位置对应一个独特的指纹。下面通过一个具体的例子来详细了解一下位置指纹

40、库的构建过程。如图3-1所示，假设某个商场中安装了2个AP,图中的每个网格点代表一个用户。在矩形网格上建立坐标系，使用局部坐标系中的坐标O=Ky）表示用户当前所在的位置，X为坐标系中的横坐标，y为坐标系中的纵坐标。在商场内购物的用户所持有的移动设备可以接收到这2个AP发送的指纹信息。图3-1商场布局图在图3T所示的网格点区域中采集指纹向量p,此时，指纹向量是一个二维向量P=月,夕。将网格点坐标作为位置坐标，和对应的指纹向量组成位置指纹库表3-1是这个位置指纹库的一个局部。表3-1位置指纹库的局部ExampleFingerprintDatabaseCoordinateofGridPointp夕2

41、(0,0)-65-50(0,1)-64-45(0,2)-60-513.2位置指纹定位方法为了简单直观的展示位置指纹库的构建过程，我们对上述的位置向量。和指纹向量P做了很多的简化。实际上，在本文所使用的数据集中，包含了许多商场信息和用户购物信息，不同的商场通过malLid进行区分。每一个商场内拥有多家店铺，每天会有许多用户到商场内购物。我们以用户的GPS定位，接收到的WlFl信号以及接收时间作为指纹，以用户所在的店铺作为位置。，两者一起组成了位置指纹库。由于一个店铺可能会有多个用户，因此,位置指纹库中的每个定位点会对应多套指纹信息。本文的位置指纹库可以表示为：/=（/71,01）,（夕2,02）

42、,（0,，,（0V,ON）（式3-3）M其中，i=l,2,N,N表示商场内的用户数量，Pi=（Pip,p%）eR表示来自M个AP的指纹向量，凡为来自第1个AP的指纹向量，必为来自第2个AP的指纹向量，依次类推，0”为来自第M个AP的指纹向量；位置向量Oj表示指纹向量Pi对应的店铺。在完成对位置指纹库的构建后，我们便可以基于这个位置指纹库训练相应的WIFl定位模型，并使用该模型对待定位用户进行定位。假设在商场中存在一个待定位的用户，已知该用户的指纹信息夕，包括用户的GPS定位，接收到的WIFI信号以及接收时间。将指纹信息P输入到己训练好的WIFI定位模型中便可以定位出该用户所在的店铺。在下一章中

43、将会对本文所提出的WIFl定位模型进行详细的介绍。第四章基于RF和Xgboost的融合定位算法在商场中定位用户所在的店铺，这是一个典型的分类问题。从用户的视角出发，将每一个店铺作为一个类别，这便是一个多分类问题；从店铺的视角出发，将用户是否在该店铺作为类别标签，这便是一个二分类问题。我们首先利用基于随机森林的多分类算法和基于Xgboost的二分类算法定位用户所在的店铺，然后通过对多分类算法以及二分类算法的有效融合提出了一个基于RF和Xgboost的融合定位算法。下面依次对基于多分类的定位算法，基于二分类的定位算法以及多分类和二分类的融合定位算法进行详细的介绍。4.1 基于多分类的定位算法从用户

44、的视角出发，将每一个店铺作为一个类别，此时，定位用户所在的店铺就变成了一个多分类问题。若使用多分类方法来解决商场内的用户定位问题，通常使用的是KNN模型及其变形。与传统KNN算法相比，随机森林算法能够直接处理具有高维特征的输入样本，并具有良好的抗噪声能力和泛化能力。因此，本文选用随机森林模型作为多分类模型对用户所在的店铺进行定位,这样可以有效提高用户定位的精度，大大缩短定位时间。在使用多分类模型解决问题前，我们首先要基于原始训练集为每个商场构建一个位置指纹库，然后基于相应的位置指纹库训练随机森林模型。下面主要介绍一下位置指纹库的构建以及随机森林的训练过程。4.1.1 位置指纹库构建基于多分类的

45、定位算法，将商场中的所有店铺均作为待定位用户的类别标签，虽然这样使得样本覆盖率高达100%，样本召回率高。但这也同样带来一个问题，就是商场中的店铺数量过多，我们无法对所有商场中的店铺同时进行训练，只能对每一个商场都训练一个多分类模型。因此,我们需要对每个商场都各自构建一个位置指纹库。按照商场号mallJd对训练集进行划分，在每个商场中，统计该商场中每个WlFl的出现次数以及WIFl的信号强度。过滤掉那些信号强度小于90,并且出现次数少于6次的WlFL保留那些对店铺定位有价值的WIFl信号，与用户的GPS以及当前时间一起组成指纹夕=WSE,R,iRSSllJonJatj,将用户当前所在的店铺号S

46、hOP_id作为位置。，指纹与对应的位置。一起组成该商场的位置指纹库。4.1.2 随机森林算法随机森林是一种多功能的机器学习算法，以决策树为基学习器，在对决策树构建Bagging集成的基础上，在决策树的训练过程中进一步引进了随机属性选择。为了更好地理解随机森林算法，下面我们结合具体的数据对Bagging集成以及决策树的构建过程进行详细介绍。现已知商场A的位置指纹库，假设该位置指纹库中包含N个样本，指纹向量p=RSS,RSS2,.,RSSn,lon,lat,tl中包含M个指纹特征。1.BaggingBagging（BootstrapAggregating）1是集成学习方法中最著名的代表，通过不同

47、的结合策略将多个“好而不同”基学习器结合起来，使得最终集成的学习器具有较强的泛化能力。基于商场A的位置指纹库构建Bagging集成。在训练阶段，首先基于自助采样法，在商场A包含N个样本的位置指纹库中进行有放回的随机抽样，得到T个含N个训练样本的采样集，这厂个采样集中的样本各不相同。然后基于每个采样集训练出一个基学习器，每个基学习器具有一定的准确性，彼此又存在差异性。在定位阶段，对于待定位的用户，将该用户的指纹输入到Bagging模型中，通过多数投票法将基学习器中得票最多的店铺作为待定位用户最终的位置。随机森林以决策树为基学习器，对Bagging集成进行了扩展，不仅通过“样本扰动”（对原始数据集进行有放回的自助采样），还通过“属性扰动”（在训练决策树的过程中引入随机属性选择），使得最终集成的模型其泛化性能得到了进一步的提升。因此，在随机森林中，决策树的构建同样至关重要。下面让我们详细了解一下随机森林中决策树的构建过程。2.决策树随机森林中决策树的构建过程与传统决策树不同，在对当前结点进行划分时，首先从当