基于NGID-DBSCAN算法与最小包围圆模型的基站位置分析

发布时间：2017-05-23 23:05

  本文关键词：基于NGID-DBSCAN算法与最小包围圆模型的基站位置分析，由笔耕文化传播整理发布。

【摘要】：基于位置的服务(Location-based Service, LBS)是移动互联网的重要特点之一，近年来与位置相关的应用大受欢迎，用户通过上传位置信息，获取周边服务。位置信息反映了人的行为特征、兴趣爱好、社交关系等，对位置信息的挖掘对个性化推荐有重要意义，然而位置信息的不确定性带来了离群数据；另一方面，本地化服务，如推荐用户常待基站下的内容，大众更易接受，由于基站位置信息的安全性，获取困难。 本课题基于上述背景，对离群点检测技术和基站位置建模进行研究，为用户画像、个性化服务提供决策支持，主要工作如下： (1)对现有离群点检测技术进行总结，对比分析了适用范围、优缺点，，重点分析了基于密度聚类的离群点检测算法-DBSCAN，针对算法时间复杂度大，通过网格划分技术缩小邻域扫描范围的思想加于改进，提出基于邻近网格的密度聚类算法(NGID-DBSCAN)，仿真实验验证了改进算法的性能。将改进算法应用到基站位置离群点检测上，比较分析了与可视化方法检测位置信息离群数据的优缺点。 (2)研究了平面点集的最小圆求解算法，并针对最远点优先渐近算法中四点画圆问题，在算法实现过程中引入最小圆引理，将四点画圆转换为三点画圆，减小枚举次数，提高算法性能。 (3)提出将基站位置分析转换为大量基站覆盖范围下用户位置的数学建模问题，并通过求解平面点集的最小包围圆圆心代替基站位置，实验结果验证了该模型的可行性。从算法时间复杂度考虑，比较分析了当点集形成一个簇时，可以通过求点集的中心代替最小圆圆心。 本文提出的NGID-DBSCAN算法和最小圆模型具有对已知位置基站数据的自校验、后续基站位置的补充等作用。
【关键词】：位置分析 离群点 密度聚类 最小包围圆 网格
【学位授予单位】：武汉邮电科学研究院
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN929.5;TP393.01
【目录】：

• 摘要3-4
• Abstract4-8
• 第1章 绪论8-13
• 1.1 课题研究的背景与意义8-10
• 1.2 国内外研究现状10-11
• 1.3 本文研究的主要内容与组织结构11-13
• 第2章 离群点分析与平面点集最小包围圆13-29
• 2.1 离群点分析13-20
• 2.1.1 离群点分析背景13-14
• 2.1.2 离群点产生原因14
• 2.1.3 离群点检测方法14-20
• 2.2 平面点集最小包围圆20-23
• 2.2.1 最小包围圆性质20-22
• 2.2.2 最小包围圆算法22-23
• 2.3 其他相关概念23-28
• 2.3.1 球面距离23-24
• 2.3.2 网格划分与地理信息栅格24-25
• 2.3.3 基站编码规则与覆盖范围25-28
• 2.4 本章小结28-29
• 第3章 基于邻近网格的密度聚类算法29-39
• 3.1 NGID-DBSCAN 算法29-30
• 3.2 NGID-DBSCAN 算法描述30-34
• 3.3 实验与性能分析34-37
• 3.3.1 实验测试环境与数据集34-35
• 3.3.2 算法性能测试35-37
• 3.3.3 算法性能分析37
• 3.4 本章小结37-39
• 第4章 基于 NGID-DBSCAN 算法与最小包围圆的基站位置分析39-54
• 4.1 需求分析39
• 4.2 离群点来源39-40
• 4.3 基站位置分析实验40-53
• 4.3.1 实验数据40-41
• 4.3.2 基站离群点检测41-47
• 4.3.3 基站位置分析47-53
• 4.4 本章小结53-54
• 第5章 总结与展望54-56
• 5.1 论文工作总结54-55
• 5.2 存在的问题55
• 5.3 未来工作展望55-56
• 参考文献56-59
• 致谢59-60
• 附录1 攻读硕士学位期间发表的论文60-61
• 附录2 最小圆引理的证明61-62

【参考文献】

中国期刊全文数据库 前4条

1 李红军;张晓鹏;;离散点集最小包围圆算法分析与改进[J];图学学报;2012年02期

2 陈康;黄晓宇;王爱宝;陶彩霞;关迎晖;李磊;;基于位置信息的用户行为轨迹分析与应用综述[J];电信科学;2013年04期

3 周水庚,范晔,周傲英;基于数据取样的DBSCAN算法[J];小型微型计算机系统;2000年12期

4 徐琰;肖基毅;;离群点分析在高校能耗监控系统中的应用[J];南华大学学报(自然科学版);2014年02期

  本文关键词：基于NGID-DBSCAN算法与最小包围圆模型的基站位置分析，由笔耕文化传播整理发布。

本文编号：389285