Nothing Special   »   [go: up one dir, main page]

CN104615881B - 一种基于移动位置应用的用户常态轨迹分析方法 - Google Patents

一种基于移动位置应用的用户常态轨迹分析方法 Download PDF

Info

Publication number
CN104615881B
CN104615881B CN201510050458.2A CN201510050458A CN104615881B CN 104615881 B CN104615881 B CN 104615881B CN 201510050458 A CN201510050458 A CN 201510050458A CN 104615881 B CN104615881 B CN 104615881B
Authority
CN
China
Prior art keywords
cluster
point
core
tracing
clusters
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201510050458.2A
Other languages
English (en)
Other versions
CN104615881A (zh
Inventor
陈磊
李名臣
史波良
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NANJING FIBERHOME INFORMATION DEVELOPMENT Co Ltd
Original Assignee
NANJING FIBERHOME INFORMATION DEVELOPMENT Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NANJING FIBERHOME INFORMATION DEVELOPMENT Co Ltd filed Critical NANJING FIBERHOME INFORMATION DEVELOPMENT Co Ltd
Priority to CN201510050458.2A priority Critical patent/CN104615881B/zh
Publication of CN104615881A publication Critical patent/CN104615881A/zh
Application granted granted Critical
Publication of CN104615881B publication Critical patent/CN104615881B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开了一种基于移动位置应用的用户常态轨迹分析方法，包括以下步骤：步骤1，输入用户轨迹集合P；步骤2，获取轨迹集合P中的一组有序的包含全部Pn个轨迹点的凸多边形轨迹集合Q；步骤3，计算凸多边形Q的面积；步骤4，确定簇半径R和簇密度T；步骤5，记录所有核心簇；步骤6，进行核心簇合并；步骤7，递归执行步骤7，直至所有的核心簇之间无法合并，则判定收敛；步骤8，将未包含在核心簇中的点，判定为噪音点；以簇半径R为阈值，采取就近聚类的原则，将噪音点聚集成若干个噪音簇；步骤9，将核心簇和噪音簇进行簇内轨迹点选举，保证一簇选举出一点。

Description

一种基于移动位置应用的用户常态轨迹分析方法
技术领域
本发明涉及移动数据轨迹分析领域，是一种针对用户活动轨迹数据进行挖掘分析，进而获得用户常态轨迹的方法。
背景技术
随着科技的进步，移动应用已经深深地改变了人们的日常生活，对于应用开发者来说，为了向用户提供更好更人性化的服务，常常需要对各种各样的用户行为数据进行分析挖掘，而用户活动轨迹数据正是这其中重要的一种。
目前，针对于轨迹数据进行挖掘分析的算法较多，聚类算法亦是首选。但是开发者大都基于各自开发需求，对聚类算法的输入因子做了种种特定设置，导致聚类算法的结果适用性不是很广。
发明内容
发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种基于移动位置应用的用户常态轨迹分析方法。
为了解决上述技术问题，本发明公开了一种基于移动位置应用的用户常态轨迹分析方法，包括以下步骤：
步骤1，输入用户轨迹集合P，以及目的聚类簇个数K，轨迹集合P包含轨迹点的原始位置数据；
步骤2，对于轨迹集合P中的Pn个轨迹点，获取轨迹集合P中的一组有序的包含全部Pn个轨迹点的凸多边形轨迹集合Q；
步骤3，计算凸多边形Q的面积；
步骤4，确定簇半径R和簇密度T；
步骤5，以轨迹集合P中任意一个轨迹点M为圆心，簇半径R以内包含的点个数大于T个，则认为M是核心点，以M为圆心，R为半径包含的所有点集合为核心簇C；如果簇半径R以内包含的点个数小于簇密度T，则认为M为普通点；遍历P中所有的点，记录所有核心簇；
步骤6，假设以M1为核心点形成的核心簇C1中包含T1个轨迹点，以M2为核心点形成的核心簇C2中包含T2个轨迹点，如果C1与C2两簇公共轨迹点数超过两簇中最少轨迹点簇的点数50％，则将C1与C2进行合并，形成新的簇C12；
步骤7，递归执行步骤6，直至所有的核心簇之间无法合并，则判定收敛；
步骤8，将未包含在核心簇中的点，判定为噪音点；以簇半径R为阈值，采取就近聚类的原则，将噪音点聚集成若干个噪音簇；
步骤9，将核心簇和噪音簇进行簇内轨迹点选举，保证一簇选举出一点。
本发明中，所述原始位置数据包括：用户账号、经度、纬度以及采集时间。
本发明中，步骤2中，使用开源凸包算法ConvexHull获取轨迹集合P中的一组有序的包含全部Pn个轨迹点的凸多边形轨迹集合Q。
本发明中，步骤3中，计算方法为：将凸多边形Q分割成若干个三角形，计算三角形面积并相加。
本发明中，步骤9中，针对每个簇中的所有轨迹点进行经纬度加权平均，生成簇的虚拟中心点，然后计算簇内所有点到该虚拟中心点的距离，选举距离最小点作为该簇合并后的常态轨迹点，选举出所有簇合并后的常态轨迹点并输出。
本发明在做挖掘分析时采用BA-DBScan(Base area DBscan)算法，根据已有用户轨迹数据，通过轨迹范围进行动态计算簇密度和簇半径的方法，进而实现对用户常态轨迹的提取，大大的提高了算法结果的适用性。
附图说明
下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。
图1为发明总体流程图。
图2为用户A原始轨迹图。
图3为用户A活动范围图。
图4为用户A常态轨迹图。
具体实施方式
本发明从已有用户轨迹数据中，挖掘提取出用户常态活动轨迹。以移动应用搜集的用户活动轨迹数据为样本，采用BA-DBScan作为用户轨迹数据聚类算法，再对聚类成功后的簇进行簇内部轨迹点选举，将选举出的点作为常态轨迹点输出；
算法的输入：轨迹信息集合P，目的聚类簇个数K；
算法的输出：常态轨迹集合；
下面介绍具体步骤：
1>对原始位置数据进行预处理，去除异常经纬度数据后作为输入数据；保证输入数据中包含用户账号、经度、纬度、采集时间等信息。
2>再以其中用户A的轨迹集合P为例，假设P中含轨迹点数为Pn。使用开源凸包算法ConvexHull获取P中的一组有序的凸多边形轨迹集合Q，保证Pn个轨迹点全部被Q包含；
3>计算凸多边形Q的面积。将凸多边形分割成若干个三角形，计算三角形面积并相加；
p是三角形半周长：
p＝(ab+bc+ac)/2；
其中a,b,c分别是三角形三个顶点，ab,bc,ac分别是三角形三边边长，通过两点经纬度转化为墨卡托坐标再计算距离的方式即可计算出边长；
由任意三点a,b,c组成的三角形Sqabc面积计算公式(海伦公式)：
凸多边形面积Q的面积Sqn计算公式：
其中n是指凸多边形Q的顶点数，Q的面积等于n-2个三角形面积累加和；
4>确定聚类算法的簇半径和簇密度：
簇半径：
簇密度：
T＝Pn/K，
5>以用户A的轨迹集合P中任一点M为圆心，半径R以内包含的点个数大于T个，则认为M是核心点，以M为圆心，R为半径包含的所有点集合为核心簇C；如果半径R以内包含的点个数小于T，则认为R为普通点。遍历P中所有的点，记录所有核心簇信息；
6>如果以M1为核心点形成的核心簇C1中包含T1个轨迹点，以M2为核心点形成的核心簇C2中包含T2个轨迹点，同时C1与C2两簇公共轨迹点数超过两簇中最少轨迹点簇的点数50％，则将C1与C2进行合并，形成新的簇C12；
7>递归执行步骤6，直至所有的簇均相对独立，无法合并，则认为算法收敛成功，记录合并之后的核心簇信息；
8>对于未包含在核心簇中的点，称之为噪音点。就近聚类原则为：标记所有的噪音点为“未成簇”，计算任意两个“未成簇”噪音点的距离，如果距离小于簇半径R，则将这两个噪音点聚集成噪音簇，同时标记这两个噪音点为“已成簇”；如果距离大于簇半径R，则继续计算其他“未成簇”噪音点距离，循环计算，直到所有“未成簇”噪音点与所有“已成簇”噪音点的距离均大于簇半径R，循环计算结束。将剩下的“未成簇”噪音点各自独立成噪音簇，记录所有噪音簇信息；
9>将上面产生的核心簇和噪音簇进行簇内轨迹点选举，保证一簇选出一点。选举方法如下：针对每个簇中的所有轨迹点进行经纬度加权平均，生成簇的虚拟中心点，然后计算簇内所有点到该虚拟中心点的距离，选举距离最小点作为该簇合并后的常态轨迹点并输出。
通过以上几个步骤，即可获得用户A的常态轨迹。
实施例1
图1为本发明总体流程图，具体实施流程介绍如下：
1>准备一批已有用户轨迹样本数据，经过清洗后，保证数据中必须包含用户账号、经度、纬度、采集时间等信息；
2>从步骤1中的样本数据中抽取出用户A的原始轨迹数据作为输入轨迹数据，具体的用户A的原始输入轨迹信息如图2所示；
3>获取到用户A的原始轨迹图后，利用开源凸包算法ConvexHull计算得到用户A的活动范围，如图3所示，是一个由A.B.C.D.E坐标点围成的凸五边形。
4>计算用户A的活动范围面积，即凸五边形面积。可以将凸五边形切分为三个三角形。其中三角形边长ab、bc、ac可以通过两顶点经纬度坐标转化为墨卡托坐标计算得出。
三角形半周长:
P＝(ab+bc+ac)/2
三角形面积:
凸五边形面积:
Sabcdef＝Sabc+Sacd+Sade
5>根据活动范围面积计算出BA-DBScan算法的输入因子，即簇半径和簇密度；
4>将用户A原始轨迹数据集合和目的聚类个数K作为算法输入，执行算法，直至算法收敛，输出结果簇，并对结果簇进行簇内选举，得到最终用户A常态轨迹，算法结束。用户A的常态轨迹图如图4，可以发现，本发明较好的保留了用户A的常态轨迹。
本发明提供了一种基于移动位置应用的用户常态轨迹分析方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。

Claims (1)

1.一种基于移动位置应用的用户常态轨迹分析方法，其特征在于，包括以下步骤：
步骤1，输入用户轨迹集合P，以及目的聚类簇个数K，轨迹集合P包含轨迹点的原始位置数据；
步骤2，对于轨迹集合P中的Pn个轨迹点，获取轨迹集合P中的一组有序的包含全部Pn个轨迹点的凸多边形轨迹集合Q；
步骤3，计算凸多边形Q的面积；
步骤4，确定簇半径R和簇密度T；
步骤5，以轨迹集合P中任意一个轨迹点M为圆心，簇半径R以内包含的点个数大于T个，则认为M是核心点，以M为圆心，R为半径包含的所有点集合为核心簇C；如果簇半径R以内包含的点个数小于簇密度T，则认为M为普通点；遍历P中所有的点，记录所有核心簇；
步骤6，假设以M1为核心点形成的核心簇C1中包含T1个轨迹点，以M2为核心点形成的核心簇C2中包含T2个轨迹点，如果C1与C2两簇公共轨迹点数超过两簇中最少轨迹点簇的轨迹点数的50％，则将C1与C2进行合并，形成新的簇C12；
步骤7，递归执行步骤6，直至所有的核心簇之间无法合并，则判定收敛；
步骤8，将未包含在核心簇中的点，判定为噪音点；以簇半径R为阈值，采取就近聚类的原则，将噪音点聚集成若干个噪音簇；
步骤9，将核心簇和噪音簇进行簇内轨迹点选举，保证一簇选举出一点；
所述原始位置数据包括：用户账号、经度、纬度以及采集时间；
步骤2中，使用开源凸包算法ConvexHull获取轨迹集合P中的一组有序的包含全部Pn个轨迹点的凸多边形轨迹集合Q；
步骤3中，计算方法为：将凸多边形Q分割成若干个三角形，计算三角形面积并相加；
步骤9中，针对每个簇中的所有轨迹点进行经纬度加权平均，生成簇的虚拟中心点，然后计算簇内所有点到该虚拟中心点的距离，选举距离最小点作为该簇的常态轨迹点，选举出所有簇合并后的常态轨迹点并输出。
CN201510050458.2A 2015-01-30 2015-01-30 一种基于移动位置应用的用户常态轨迹分析方法 Active CN104615881B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201510050458.2A CN104615881B (zh) 2015-01-30 2015-01-30 一种基于移动位置应用的用户常态轨迹分析方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201510050458.2A CN104615881B (zh) 2015-01-30 2015-01-30 一种基于移动位置应用的用户常态轨迹分析方法

Publications (2)

Publication Number Publication Date
CN104615881A CN104615881A (zh) 2015-05-13
CN104615881B true CN104615881B (zh) 2017-12-22

Family

ID=53150322

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201510050458.2A Active CN104615881B (zh) 2015-01-30 2015-01-30 一种基于移动位置应用的用户常态轨迹分析方法

Country Status (1)

Country Link
CN (1) CN104615881B (zh)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105321341B (zh) * 2015-12-03 2017-10-17 北京航空航天大学 一种基于城市移动模式的资源供应方法
CN107070961B (zh) 2016-09-30 2020-06-23 阿里巴巴集团控股有限公司 基于地理位置数据的热点区域确定方法及装置
CN107369069B (zh) * 2017-07-07 2020-06-05 成都理工大学 一种基于三角形面积计算模式的商品推荐方法
CN108122012B (zh) * 2017-12-28 2020-11-24 百度在线网络技术（北京）有限公司 常驻点中心点的确定方法、装置、设备及存储介质
CN109948070B (zh) * 2019-03-13 2022-08-09 深圳市同行者科技有限公司 一种家和公司位置的分析确定方法、存储介质及终端
CN110245715B (zh) * 2019-06-20 2020-12-22 国网湖南省电力有限公司 用于精准切负荷的用户划分方法
CN110457315A (zh) * 2019-07-19 2019-11-15 国家计算机网络与信息安全管理中心 一种基于用户轨迹数据的群体聚集模式分析方法和系统

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102164405A (zh) * 2010-12-17 2011-08-24 东软集团股份有限公司 快速定位方法及系统
CN102607553A (zh) * 2012-03-06 2012-07-25 北京建筑工程学院 一种基于出行轨迹数据的行程识别方法
CN103218442A (zh) * 2013-04-22 2013-07-24 中山大学 一种基于移动设备传感器数据的生活模式分析方法及系统

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102164405A (zh) * 2010-12-17 2011-08-24 东软集团股份有限公司 快速定位方法及系统
CN102607553A (zh) * 2012-03-06 2012-07-25 北京建筑工程学院 一种基于出行轨迹数据的行程识别方法
CN103218442A (zh) * 2013-04-22 2013-07-24 中山大学 一种基于移动设备传感器数据的生活模式分析方法及系统

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
基于出租车轨迹的并行城市热点区域发现;桂智明等;《华中科技大学学报（自然科学版）》;20121231;第20卷(第增刊I期);第187-190页 *
基于密度的DBSCAN聚类算法的研究及应用;冯少荣等;《计算机工程与应用》;20071231;第43卷(第20期);第216-221页 *

Also Published As

Publication number Publication date
CN104615881A (zh) 2015-05-13

Similar Documents

Publication Publication Date Title
CN104615881B (zh) 一种基于移动位置应用的用户常态轨迹分析方法
Wang et al. PGT: Measuring mobility relationship using personal, global and temporal factors
CN105138779B (zh) 车载gps时空轨迹大数据优选方法及系统
CN104050196B (zh) 一种兴趣点数据冗余检测方法及装置
CN103593430B (zh) 一种基于移动对象时空信息轨迹分段聚类的方法
CN107547633A (zh) 一种用户常驻点的处理方法、装置和存储介质
US11009362B2 (en) Generating trail network maps
CN101848529B (zh) 一种无线传感器网络的多重主成分分析数据压缩方法
CN110609824B (zh) 城市路网环境下基于动态空间网络模型的热点区域检测方法
CN105682097B (zh) 一种伪基站识别定位方法及装置
CN106339716A (zh) 一种基于加权欧氏距离的移动轨迹相似度匹配方法
CN106162544B (zh) 一种地理围栏的生成方法和设备
CN107818534B (zh) 一种具有空间约束的人类活动网络区域划分方法
CN102393926B (zh) 井下应急撤人安全路线智能决策方法
CN105910612A (zh) 一种个性化导航的方法及系统
CN110716935A (zh) 基于网约车出行的轨迹数据分析与可视化方法及系统
CN107609709A (zh) 基于场景分类的路径规划方法及系统
CN104715127B (zh) 一种投诉热点区域识别方法及系统
CN104219760B (zh) 混合定位方法与系统
CN103747419A (zh) 一种基于信号强度差值与动态线性插值的室内定位方法
CN109034187A (zh) 一种用户家庭工作地址挖掘流程
EP3192061B1 (en) Measuring and diagnosing noise in urban environment
Du et al. Group mobility classification and structure recognition using mobile devices
CN106802958A (zh) Cad数据到gis数据的转换方法及系统
CN106412835A (zh) 一种用户出行模式识别的方法及装置

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant