简介面向物联网移动终端设备的用户轨迹异常检测研究论文出自《计算机应用研究》2019年网络首发作者为南京邮电大学的李健、付雄、王俊昌。该研究针对现有异常轨迹检测算法效率低、难以适应物联网海量动态轨迹数据的问题提出基于停留点提取与双层层次聚类的检测方法先在特定空间距离与时间间隔下提取停留点集合划分停留区域并识别异常停留区域再对区域间运动轨迹段二次聚类发现异常轨迹段。实验表明相比传统算法该方法既能更全面地检测异常轨迹又明显加快了检测速度。资源为PDF格式包内共1个文件压缩包约689KB内容包含中英文摘要、关键词、问题背景、方法设计与实验对比等完整论文结构适合物联网、数据挖掘、行为分析方向的研究生和工程师参考学习用于理解轨迹数据预处理、层次聚类应用以及异常检测建模思路。目前已有292人学习。1. 异常轨迹检测为什么先找“停留点”才是破局点拿到几万个 GPS 轨迹点最直接的想法是逐条比较轨迹形状找出和大多数不一样的那一段。但传统算法 TROD、iBAT 这么做有两个硬伤一是只从空间角度比距离几乎不看时间二是轨迹点一多两两比对的距离矩阵直接让计算量爆炸。这篇论文给出的反直觉思路是检测轨迹异常不要先看“动”要先看“不动”——把用户长时间待着的区域压缩成停留点先找异常停留再找停留区域之间的异常运动段。这就是 DCTOD双层聚类异常轨迹检测的核心用一层聚类管“在哪待着”用第二层聚类管“怎么移动”把异常轨迹拆成两类分别检测。理解了这个设计你就明白为什么它比直接对全轨迹做距离匹配既更全面、又更快。2. 停留点生成时空阈值如何把几万个轨迹点折叠成行为锚点2.1 轨迹本质是时间排序的流水不是散点云从移动终端提取的轨迹信息五花八门导航应用里是标准 GPS 坐标序列社交应用打卡里是离散位置记录图片和视频文件里还藏着 EXIF 经纬度。但它们有个共同点——每条记录都至少包含经度、纬度、时间戳。论文把这些数据按时间先后排成一个序列 G (g_1, g_2, …, g_n)其中 g_i (x_i, y_i, t_i)。这一步排序很关键它把无序的记录变成了有时间语义的轨迹流水后面所有的阈值判断都依赖相邻点的时间差。用户日常行为的轨迹有个显著特征大量时间其实花在几个固定区域里。睡觉、上班、吃饭这些行为会在几个小时内让轨迹点密集地落在一个小范围内。如果不做处理直接把这些点拿去聚类或算距离不仅计算量被无限放大还会稀释真正有价值的信息——用户“去了哪、待了多久”。论文把这称作数据量大、分布不均匀的问题对应到工程上就是必须先压缩再分析。2.2 停留点的四元组定义平均坐标加起止时间当一个轨迹段 g_k, g_{k1}, …, g_m 满足两个条件——相邻轨迹点之间的空间距离都小于空间阈值 W_d且段内第一个点和最后一个点的时间差大于时间阈值 W_t——这个段就可以被合并成一个停留点。停留点用一个四元组表示s (x, y, t_start, t_stop)其中 x、y 是段内所有轨迹点经纬度的平均值t_start 由 g_k 的时间决定t_stop 由 g_m 的时间决定。论文里距离公式是标准的欧式距离d(g_i, g_j) sqrt((x_i - x_j)² (y_i - y_j)²)这个定义里有个容易被忽略的细节取平均坐标而不是首尾坐标意味着停留点代表的是一个空间范围的重心而不是某个具体采样时刻的位置。这样后续做聚类时停留点之间的欧式距离才能稳定反映两个活动区域的空间差异不容易被单个漂移点带偏。2.3 生成算法的工程实现与复杂度论文给出了一个遍历式算法核心逻辑是从头到尾扫一遍轨迹序列凡是相邻点距离小于 W_d 就归入当前候选集合同时累计经纬度之和直到遇到距离超过阈值的点就结算——如果累计点数大于 2 且起止时间差超过 W_t就把这个集合生成为一个停留点。按论文语义整理成 Python 风格伪代码def extract_stay_points(G, W_d, W_t): sList [] k 1 sumLat 0.0 sumLon 0.0 startTime None stopTime None for i in range(len(G)): startTime G[i].t # 贪心扩展只要相邻点距离小于空间阈值就吞进当前停留候选 while i 1 len(G) and dist(G[i], G[i 1]) W_d: sumLat G[i 1].x sumLon G[i 1].y stopTime G[i 1].t k 1 i 1 # 点数足够且时间跨度达标才落成一个停留点 if k 2 and (stopTime - startTime) W_t: sList.append((sumLat / k, sumLon / k, startTime, stopTime, k)) # 重置准备收集下一个停留候选 k 1 sumLat 0.0 sumLon 0.0 return sList这段代码有两个机制要点。第一while 循环是贪心扩展只要相邻点距离小于 W_d 就继续吞并这意味着一个停留点可以跨越很长的物理区域比如在大型商场内缓慢移动的轨迹会被合并成一个停留点符合“活动范围”的直觉。第二停止条件卡的是“点数 2 且时间跨度 W_t”点数大于 2 是为了排除短暂停留的噪声点时间阈值 W_t 才是决定“停留”语义的关键参数。论文实验里 W_t 取 30 分钟、W_d 取 100 米这个组合把 248217 个原始轨迹点压缩成了一张与原始轨迹形状基本一致的停留点分布图——说明停留点序列保留了用户的空间活动骨架却把数据量降低了好几个数量级。整个算法只遍历一次序列时间复杂度 O(n)空间复杂度 O(n)对于几十万点的数据这一步几乎是瞬时完成的。3. 第一层聚类层次聚类凭什么比 DBSCAN 更适合稀疏停留点3.1 停留点的分布特性让 DBSCAN 的参数成为玄学停留点提取完之后下一个问题是如何找出“异常停留点”——也就是用户很少去的区域。直觉上这可以用密度聚类 DBSCAN 解决停留点密集的区域是正常活动区稀疏的点是离群点。但论文明确说 DBSCAN 在这里不好用当类与类之间距离过长时确定邻域半径 eps 和邻域内最小点数 MinPts 非常困难。这个批评很实在——DBSCAN 有两个自由参数而且对参数极其敏感eps 设小了会把一个正常活动区域劈成好几片设大了又会把两个距离较远的区域合并。停留点本身是小数据量问题通常是几十到几百个用 DBSCAN 调参的成本远高于收益。层次聚类则没有这个问题。它不需要预设簇的个数也不依赖半径参数只需要一个“集合间距离”的定义然后自底向上不断合并距离最近的两个簇直到全部合并成一个簇。这个过程中每一步合并都对应一种划分方式最后通过评价指标从这些划分里挑一个最优的。停留点数量少这一点很重要直接决定了层次聚类的 O(n³) 复杂度在这里是可接受的。3.2 平均距离定义下的凝聚层次聚类层次聚类首先要确定两个停留点集合 C_i、C_j 之间的距离。论文里用集合间所有停留点对欧式距离的平均值——也就是平均连接average linkage——来定义。公式如下d(C_i, C_j) (1 / (|C_i| * |C_j|)) * Σ_{s_a∈C_i} Σ_{s_b∈C_j} d(s_a, s_b)用平均距离而不是最小距离single linkage或最大距离complete linkage是个谨慎的选择最小距离会把一串首尾相接的区域错误地连成一个大簇最大距离又容易把略微延展的正常活动区拆散。平均距离介于两者之间对停留点这种代表区域重心的对象来说语义最稳。合并过程是标准自底向上每次找距离矩阵里最小的元素把对应的两个簇合并然后重新计算新簇与其他簇的距离更新矩阵循环直到只剩一个簇。合并的每一步都记录当前的划分快照和对应的轮廓系数最后从快照里选最优划分。3.3 轮廓系数从树状图里挑出“最优几类”聚类结束后怎么知道分几类最合理论文采用轮廓系数 R。对每个停留点 s_ia(i) 表示它与同一簇内其他点的平均距离b(i) 表示它与外部所有簇中最近那个簇的平均距离。单个点的轮廓值是 (b(i) - a(i)) / max{a(i), b(i)}整体轮廓系数 R 是所有点轮廓值的平均范围在 [-1, 1] 之间。R 越大说明簇内越紧凑、簇间越分离聚类效果越好。层次聚类的每一次合并都会生成一个新的划分对应一个新的轮廓系数。论文的做法是每次合并后都计算一次整体轮廓系数全部记录起来最终取轮廓系数最大的那次划分作为最优结果。注意正常情况下随着簇数从 n 减到 1轮廓系数会先升后降峰值对应“类间分离、类内紧凑”的平衡点。找到这个峰值后簇数少、样本也少的小簇就是偏离主活动区的那批点——论文里说的离群停留点集。这一步把“哪里异常”从定性判断变成了一个可复现的计算过程。3.4 异常停留点检测的伪代码还原论文给出的异常停留点检测算法可以按语义整理成如下形式def detect_outlier_staypoints(sList): clusters [{s} for s in sList] # 初始每个停留点独立成簇 best_R -1.0 best_clusters None while len(clusters) 1: # 计算当前划分的轮廓系数记录最优快照 R silhouette_score(clusters) if R best_R: best_R R best_clusters [set(c) for c in clusters] # 找距离矩阵中最小的一对簇合并 min_dist float(inf) pair (0, 1) for i in range(len(clusters)): for j in range(i 1, len(clusters)): d avg_linkage_distance(clusters[i], clusters[j]) if d min_dist: min_dist d pair (i, j) # 合并并移除旧簇 merged clusters[pair[0]] | clusters[pair[1]] clusters [clusters[k] for k in range(len(clusters)) if k not in pair] clusters.append(merged) # 最优快照中样本数明显偏少的簇即为离群停留点 sizes sorted(len(c) for c in best_clusters) threshold median(sizes) * 0.5 outliers [p for c in best_clusters if len(c) threshold for p in c] return outliers这段执行里有两个关键机制。第一轮廓系数的计算要在每次合并前做而不是合并后因为合并动作本身会改变划分质量记录的是“当前划分”的质量和“下一步动作”无关。第二离群停留点的判定由簇大小决定——正常停留区域的停留点会反复出现比如每天上下班在同一片区域所以正常簇的样本数明显更大而用户偶尔路过、从未久留的区域生成的停留点很少聚出来的簇只有一两个点用中位数的一半作阈值可以把它们干净地分离出来。整个过程的计算瓶颈在 avg_linkage_distance 的重复计算上论文给出的复杂度是 O(n³) 时间和 O(n³) 空间这是层次聚类在小数据量下的典型代价也是后面要考虑优化的问题。4. 第二层聚类轨迹段距离里的速度、偏转角和 Hausdorff4.1 轨迹段的两类划分区域内段和区域间段有了停留区域整个用户的轨迹就可以按停留点切分。按时间顺序排列的停留点序列 S (s_1, s_2, …, s_n) 把轨迹分成了两段相邻停留点之间的轨迹序列构成一条轨迹线段。这些线段分两类——停留区域内部停留点之间的段和不同停留区域之间的段。论文的处理很有针对性区域内轨迹段被视为同一区域不同时间段的停留行为不具备“移动”语义所以异常运动轨迹的检测主要落在区域间轨迹段上。这个取舍合理因为在理想情况下同一停留区域内部的轨迹也应当被停留点吸收掉残余的少数点要么是区域内部的微小移动要么是噪声不值得作为异常运动的判断依据。区域间轨迹段才是用户“怎么从一个地方到另一个地方”的真实表达。异常的运动轨迹在物理上表现为速度、角度、空间距离与正常轨迹段的偏离。比如每天通勤都是走同一条路线某天突然绕了远路或者正常都是地铁匀速某天出现了长时间高速移动——这些都会让轨迹段的物理特征发生可计算的变化。4.2 轨迹段距离三要素速度、角度、位置怎么合成为一个数要对着这些轨迹段做聚类必须先定义“两条轨迹段有多远”。论文借鉴了已有轨迹聚类方法把轨迹段间距离定义为三个分量的加权和d(p_i, p_j) w_1 * d_v(p_i, p_j) w_2 * d_θ(p_i, p_j) w_3 * d_l(p_i, p_j)其中 d_v 是速度距离两条轨迹段各自所有轨迹点的瞬时速度平均值之差。d_θ 是角度距离每个轨迹点处的偏转角由连续三个点 g_i、g_{i1}、g_{i2} 连接线段的角度决定在两条轨迹段的平均值之差它衡量的是“拐弯方式”的差异。d_l 是位置距离采用单向 Hausdorff 距离每条线段上各点到另一条线段上最近点的距离取最大值。三个权重 w_1、w_2、w_3 在论文实验里统一设置为 1/3即等权。值得说明一下 Hausdorff 距离为什么用来做位置差异。它不像单纯计算两条线段的端点距离那样容易漏掉中间的大弯曲也不像逐点平均距离那样容易低估局部大偏差。Hausdorff 取的是“最坏情况距离”——一条线段上所有点到另一条线段的最近距离里最大的那个所以两条轨迹哪怕大部分重合、只有一小段分叉很远位置距离也会显著拉开这对异常检测来说是优点因为异常恰恰常常表现为局部的偏离。4.3 复用聚类框架异常轨迹段的发现与实验效果异常轨迹段检测的具体做法是把算法 2 的输入换成停留区域之间的轨迹段集合同时把“停留点间欧式距离”替换成上面这条轨迹段距离公式。聚类框架、轮廓系数选择、离群集判定逻辑完全复用。也就是说双层聚类的第二层真正改的不是聚类算法而是“距离的定义”——这是整套方法最具工程移植性的设计框架不动换个距离函数就复用了整个异常检测管线。实验部分选的是某公开 GPS 轨迹数据集中用户编号 002 的数据共 248217 个轨迹点。数据清洗的 V_max 设为 1000停留点提取参数 W_t 30 分钟、W_d 100 米三个距离权重各取 1/3。停留点序列的空间坐标图与原始轨迹的轮廓基本一致说明压缩没有丢掉主要活动空间。运行时间对比中DCTOD 明显快于基于 DBSCAN 的方法。为什么快核心在于停留点压缩把参与二次聚类的对象从几十万个轨迹点降级成了几十个区域间轨迹段——聚类复杂度虽然仍然是 O(n³)但 n 大幅缩小耗时自然断崖式下降。这个“以压缩换规模”的思路是整套方法最值得抄走的设计。另一个好处是全面性双层检测同时覆盖“待在哪”和“怎么走”两类异常TROD 那种只看轨迹段空间距离的做法发现不了“该停不停、绕路去陌生区域”这类行为异常。5. 避坑与排参从数据清洗到轨迹段权重最容易翻车的地方5.1 数据清洗和停留点阈值相关的坑现象一把 V_max 设得太大清洗基本失效轨迹里全是漂移点。原因V_max 是清洗阶段过滤“不合理速度”的阈值论文实验里设了 1000 km/h。这个值对步行、骑行用户来说几乎等于没有过滤——正常走路只有 5 km/hGPS 漂移点却经常模拟出几百甚至上千公里的瞬时速度。解决先按数据集的实际移动方式来定骑行数据集建议 V_max 设在 80 到 120步行数据设在 30 以内如果拿不准可以先按 1000 跑一遍看清洗掉了多少点再逐步下调直到点数变化趋缓。现象二停留点要么几乎没提取出来要么全被并成一个超级大区域。原因W_t 和 W_d 的组合没有和用户活动尺度对齐。W_d 100 米、W_t 30 分钟这套参数适合城市步行通勤场景但用在乡村自驾或物流车辆上100 米的空间阈值会把长时间的堵车、等红灯全部并成停留点30 分钟的时间阈值又会让短暂停车消失。解决理解两个参数一个管“空间多大算原地”一个管“待多久算停留”先统计轨迹点两两距离的分布取 80% 分位数作为 W_d 的参考值再结合业务场景定 W_t——办公场景通常设 30 到 60 分钟物流场景可能 5 分钟就值得记录一次停靠。5.2 聚类效果和离群判定相关的坑现象三按轮廓系数取最大时发现最优划分是“所有点聚成一类”异常停留点一个都没找出来。原因当数据本身分布很均匀时轮廓系数不会出现明显峰值反而可能在簇数极少时取到极大值于是程序机械地选了“全是一类”的快照离群判定自然为空。解决不要只依赖轮廓系数还要配合树状图观察合并距离的跳跃点——某次合并的距离突然远大于之前的合并距离说明该合并点之前就是合理划分边界或者给簇数设置一个搜索上限比如不超过停留点数的十分之一。现象四把停留时间短的簇一律判为异常结果高频中转点全部中招。原因离群判定用“簇大小中位数的一半”作阈值时如果一个用户天天在某个地铁站换乘每次停留只有三五分钟但每天都经过生成的停留点数量其实很多簇并不小反过来用户偶尔去一次的商场停留两小时停留点少却被判为异常。解决把停留总时长或访问频次纳入判定——异常停留区域应该是“低频、短时、孤立”的先按聚类把空间区域分出来再用每个区域停留点的累计停留时长做二次过滤低频且总停留时长短的区域才算异常。5.3 轨迹段距离和工程落地相关的坑现象五三个距离分量直接加权速度距离把其他两项完全淹没。原因速度的量纲是 km/h位置距离的量纲是米角度距离是度数三者数值范围差距悬殊。论文实验里等权 1/3 能 work是因为实验数据的速度和空间差异恰好都在同一个量级换到高速路场景速度差值可能轻松上百而 Hausdorff 距离只有几十米加权后的轨迹段距离几乎等于速度距离位置偏离完全失去作用。解决在实际使用时先对三个分量分别做标准化——比如各自除以数据集内的标准差或做 min-max 归一化到 [0, 1]再配权重。等权只有在归一化之后才具有“三个维度一样重要”的语义。现象六停留点数量一旦上千O(n³) 的距离矩阵直接内存爆炸。原因层次聚类的自底向上过程每一步都要维护全量距离矩阵n 1000 时矩阵就有接近百万个条目且每合并一次都要重算平均值时间开销随 n 成立方增长。论文原文也承认停留点和轨迹段的聚类耗时较长是主要短板。解决先按网格或按时间切片把轨迹分段对每一段分别提取停留点再做聚类最后合并各段的离群结果或者先把停留点按空间网格粗聚到百数量级再用层次聚类细查。提示论文实验设的 V_max 1000、W_t 30min、W_d 100m、权重 1/3都是针对特定数据集的调参结果。迁移到自己的轨迹数据时这些值只能当起点不能当结论。6. 设计取舍O(n³) 的层次聚类值不值以及怎么救整套 DCTOD 方法最值得玩味的取舍是明知层次聚类复杂度是 O(n³)仍然坚持用它而不是换成效率更高的 DBSCAN。这个选择在工程上其实经过了一层精密计算复杂度公式里的 n 不是原始轨迹点数而是停留点数。停留点把几十万条记录压成几十个行为锚点之后O(n³) 的实际执行体量已经降到可以接受的范围。更关键的是层次聚类换来了两个 DBSCAN 给不了的东西无参数调优的自由度以及每一步合并都留下快照的可解释性。在轨迹异常检测这种需要向业务方解释“为什么这个区域是异常”的场景里树状图和轮廓系数曲线就是最直观的证据链。但代价也很清晰——论文实验都说“停留点聚类和轨迹段的聚类时消耗时间较长”。我的理解是这个短板在离线分析场景下不算致命因为停留点提取结果可以缓存层次聚类只在新增数据达到一定量时才重跑但如果要推上实时检测管线O(n³) 的增长曲线会让数据量稍大就直接崩掉。常见的优化思路有几种把平均距离换成 Ward 距离让合并过程更倾向生成紧凑球形簇减少孤立点对合并决策的干扰或者先用 K-means 粗聚类把停留点数量降到百以内再用层次聚类精分对第二层的轨迹段可以先按起止点所在区域做分组只在同一组内部计算轨迹段距离把全连接的复杂度降成分组后的局部聚类。如果让我在这套方法上做工程改造我会保留“双层压缩、两次聚类”的骨架但把每层都换成更经济的实现第一层的停留点提取不变这是整个方法的灵魂第二层用基于距离的快速聚类替代完整层次聚类或者引入采样评估。在实际项目里我一般会先在 2D 平面上画出停留点分布和簇的边界肉眼确认一遍聚类结果符合常识再交给自动化流程去跑——这套“先压缩、再分层、用轮廓系数定簇”的流程跑多了以后你会形成一种直觉看到二维散点图就能预判轮廓系数会怎么走。从那时候起我每接一批新的轨迹数据都会强制自己先做停留点压缩、再看分布、再调阈值而不是急着上模型。这套习惯帮我避掉过很多次数据质量上的暗坑。希望帮到你。本文还有配套的精品资源点击获取