应用DBSCAN算法简化人群预测的方法分析

摘要：行人的预测直接影响到自动驾驶系统的安全性和可靠性，尤其是密集人群场景的行人预测。传统的人群预测方法通过对人群进行优先级分类，再按照不同优先级对行人逐个预测。但是，在密集人群场景，因为预测目标较多，即使正确划分了优先级，单纯依靠这种方法也会带来很大的处理时延。使用空间密度聚类（Density-BasedSpatialClusteringofApplicationswithNoise，DBSCAN）算法对密集人群场景进行分析，选择合理的聚类算法参数，在聚类结果的基础上，结合传统优先级分类算法，简化人群的处理，并提出多线程并行处理的方法，以提高聚类算法的效率。通过对DBSCAN算法应用于人群预测的分析，丰富了人群预测的方法，为优化自动驾驶行人预测的表现提供了重要参考。

关键词：人群预测空间密度聚类人群聚类算法优化

AnalysisoftheMethodofSimplifyingCrowdPredictionApplyingDBSCANAlgorithm

WANGYutong

TianhuaCollege，ShanghaiNormalUniversity，Shanghai，201815China

Abstract：Pedestrianpredictionhasadirectimpactonthesafetyandreliabilityoftheautonomousdrivingsystem，especiallyindensecrowdedscenes.&d536b44bf5706f0e9846841d8f6768e1nbsp;Traditionalcrowdpredictionmethodsclassifycrowdsbasedonpriorityandthenpredictpedestriansonebyoneaccordingtodifferentpriorities.However，indensecrowdscenarios，duetothelargenumberofpredictiontargets，evenifpriorityiscorrectlyassigned，relyingsolelyonthismethodwillbringsignificantprocessingdelays.ThisarticleusesDensity-BasedSpatialClusteringofApplicationswithNoise（DBSCAN）algorithmtoanalyzedensecrowdscenesandselectreasonableclusteringalgorithmparameters.Basedontheclusteringresults，traditionalpriorityclassificationalgorithmsarecombinedtosimplifycrowdprocessing，andamulti-threadedparallelprocessingmethodisproposedtoimprovetheefficiencyofclusteringalgorithms.ByanalyzingtheapplicationofDBSCANalgorithmincrowdprediction，themethodsofcrowdpredictionhavebeenenriched，providingimportantreferencesforoptimizingtheperformanceofautonomousdrivingpedestrianprediction.

KeyWords：Crowdprediction;DBSCAN;Crowdclustering;Algorithmoptimization

传统的统计方法和机器学习模型如隐马尔科夫模型、支持向量机等可被用于行人意图和轨迹的预测，但是，这些方法依赖于人工设置的特征和参数，然而，这些参数并不总是能反映人群的运动规律和行为模式[1]。而基于深度学习的方法，通过大量的数据，以及设计相对复杂的网络结构，例如：采用长短期记忆网络、卷积神经网络等进行人群的预测，一方面，模型的训练效果并不总是理想，另一方面，模型的加载和推理都会占用大量的内存并带来耗时的问题[2]。

本研究提出一种更高效的、易于实施的人群预测方法，即应用空间密度聚类（Density-BasedSpatialClusteringofApplicationswithNoise，DBSCAN）算法来简化人群预测的过程。该方法不需要人工选择特征和大量的积累数据，也不存在资源占用和耗时方面的问题。通过将DBSCAN算法应用于人群预测领域，笔者期望能够实现对人群数据的快速聚类和分析，再结合优先级的设置，对不同类别的人群和行人进行预测，从而简化预测过程，提高预测精度和效率。为了实现上述目的，需要解决以下一些问题（1）如何有效地将DBSCAN算法应用于人群预测领域；（2）如何处理人群中的噪声和异常值；（3）如何将DBSCAN的聚类结果和预测任务相结合；（4）如何评估DBSCAN算法应用于人群预测的性能。

综上，本研究旨在通过应用DBSCAN算法来简化人群预测的过程，并解决上述关键问题。通过深入研究和实践，为人群预测领域的发展提供新的思路和方法。

• DBSCAN算法的概述

1.1DBSCAN算法

DBSCAN算法是一种基于密度的空间聚类算法[3]。该算法将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类，它基于一组“邻域”参数来刻画样本分布的紧密程度。DBSCAN先发现密度较高的点，然后把相近的高密度点逐步连成一片，进而生成各种簇[4]。

1.2算法参数选择

DBSCAN算法的两个必须参数，分别是邻域半径和最少点MinPts[5]。（1）邻域半径的选取通过绘制距离曲线得到，距离曲线利用了K最近邻（k-NearestNeighbor，KNN）算法，在距离曲线明显拐点位置为对应较好的参数。若邻域半径设置过小，大部分数据不能聚类；若参数设置过大，多个簇和大部分对象会归并到同一个簇中。（2）最少点MinPts结合指导性原则来确定，即MinPts≥dim+1，其中，dim表示待聚类数据的维度[6]。

• 人群预测方法的介绍

2.1预测方法的分类

常见的人群预测方法分为三大类：一是传统的基于规则的人群预测算法；二是基于统计和机器学习的方法；三是基于深度学习的方法。

2.2传统预测方法的局限性

（1）基于规则的人群预测算法。其对人群的特征和分布没有进行分析，所有目标按照设定的优先级规则进行分类预测，密集人群场景可能带来准确性和大时延的问题[7]。

（2）基于统计和机器学习的方法。其需要手工筛选人群的特征、训练模型参数，对特征、参数和数据量都有很大依赖，对离散数据的处理也不尽如人意[8]。

（3）基于深度学习的方法。其对数据量有很大的要求，而且对系统资源占用和性能也有明显的影响，容易导致很大的资源占用，加大预测耗时，影响系统表现[9]。

综合来说，传统预测方法在合理性、效率和工程实现上都有不同程度的局限性。

• DBSCAN算法在人群预测中的应用

3.1方法设计

3.1.1数据预处理

需要积累和提取人群信息，提供行人的基本信息如坐标、编号等。从公开数据集中选取一定量的行人数据并提取行人信息。

3.1.2参数选择

DBSCAN算法的性能受到两个主要参数和MinPts的影响。笔者根据对已有数据的分析，通过距离曲线集，确定邻域半径，结合指导性原则，确定最小点个数。

3.1.3聚类分析

分别使用不同的参数对人群进行聚类处理，算法将自动地识别出数据中的簇，并将不属于任何簇的点视为噪声。通过查看聚类结果，可以发现不同人群的行为模式，如结伴而行的人群、集体通行过马路的人群等。

3.1.4特征处理

在聚类分析的基础上，可以进一步提取与人群预测相关的特征，如人群的簇ID、每个簇的平均位置、核心点、边界点和离散点等信息，提供给预测任务处理模块，这些特征结合优先级信息作为行人预测的输入变量来预测其未来的行为。

3.1.5结果可视化

为了方便理解和分析预测结果，可以使用可视化技术将结果以图形或图像的形式展示出来，将相同的簇用同一种颜色标识、不同的簇通过颜色进行区分，以展示人群聚类的结果。

3.2案例分析

为了验证DBSCAN算法在人群预测中的有效性，笔者从公共数据集上选取了若干行人数据作为研究对象。这些行人数据具有丰富的人车交互场景，包括过马路人群、散步人群、横穿和闯红灯场景等。

首先，利用DBSCAN算法对人群数据进行聚类，研究了选取不同聚类参数时的聚类效果。其次，按照不同簇、簇中的核心对象和边界对象，以及离群对象，结合优先级策略，对人群做简化处理，包括将ignore级别的人群直接忽略、对normal级别的人群挑选边界点对象进行处理、对caution级别的目标及其同簇内的所有边界点对象都进行处理。

通过对比分析发现，当选择合适的参数时，能够完成人群的合理聚类。结合优先级处理策略，一方面减少了要预测的目标，另一方面保证了必要目标能够得到合理预测。在所选取的行人数据场景下，聚类结果和实际应赋予人群的关注度具有较高的吻合度，这表明DBSCAN算法在人群预测中有较好的应用前景和实用价值。

• 实验结果与分析

4.1实验设计

如3.1中所述，首先，从公开的实际测试数据（包括argoverse数据集和D2-city数据集）中筛选出500条含有人群的数据，通过Python程序，将每条数据提取出必要特征，包含ID和坐标信息。然后，对所有数据进行统计，绘制距离曲线图，初步找到备选参数值，使用不同的参数对行人数据进行聚类处理，统计类别方差，并结合可视化结果，选择最优参数。在此基础上，结合优先级策略，给出简化后的人群预测方案，并进行合理性分析。

4.2数据获取

实验的完整代码见https：//github.com/yt/dbscan。通过对所有行人数据距离进行计算并排序，可以得到距离曲线图。类似地，其他脚本也都可以在链接网站上获取。

4.3实验结果

4.3.1距离曲线图

如图1所示，圆点是距离值，+表示拟合的结果。可以看到，=4时，拐点处对应的纵轴取值为3.19；=3时，拐点处对应的纵轴取值为2.4，即可以用这两个统计得到的行人聚类邻域半径测试。

4.4结果分析

如图2所示，若邻域半径或最小点设置过小，大部分行人数据不能聚类；若邻域半径或最小点设置过大，多个簇和大部分行人将归并到同一个簇中。通过结合距离曲线图手肘法和实际行人数据的聚类效果，选择对本次实验来说最优的聚类参数。

因此，对选定的数据来说，[，MinPts]=[2.5，3]是更合理的参数结果。聚类后，得到多个簇，在此聚类的基础上，结合优先级处理策略：对于caution级别的目标，该目标及其所在簇的所有边界点目标都按照caution级别策略进行处理；对于normal级别的目标，只处理该目标所在簇的边界点目标；对于ignore级别的目标，其所在簇的所有目标均ignore，即不进行处理。

结合优先级的所有人群，继续进行预测后续流程，即聚类和优先级分配后的结果正常预测。

• 优化与改进

5.1参数优化

如上所述，在选取参数的过程，一方面参考了距离曲线图，用手肘法选择参考值。另一方面，结合实际聚类效果，确定最终的人群聚类参数。但是，由于数据量有限，无法覆盖所有的人车交互场景，并且不同地方的道路结构设施不一致也会导致人群的不同行为模式。因此，在具体的应用过程中，需要结合应用场景对参数进行优化。本次研究主要探讨了DBSCAN算法用于人群预测简化处理的可行性和有效性，为将来可能的应用提供参考。

5.2算法优化

原始的DBSCAN算法步骤计算效率较为低下，在实际应用中（通常是c++代码），可以使用多线程对聚类过程进行加速[10]，具体的方案设计如下：第一步，分配处理数据的线程数，如numofthreads=N；第二步，当人群人数大于一定阈值时，如numofpeople=M，采取多线程处理策略；第三步，将数据划分为多个groups，numofgroups=M/N，每个group的行人由一个线程处理；第四步，多线程并行，所有数据处理完后，同步簇信息，即线程A得到的簇和线程B得到的簇在理论上属于同一个簇（通过设置overlap属性可得到该信息0，那么，和合并为同一个簇c。如此，原始算法的并发处理策略通过多线程优化为并行处理策略，按照此算法优化方案，能进一步缩短人群聚类的时间。

• 结论与展望

6.1研究结论

本研究对比了传统的人群预测方法，发现这些方法存在对特征和数据量依赖、资源占用和时延大等问题，通过将DBSCAN算法应用于人群预测，能够实现人群的快速聚类，将聚类结果与优先级分配策略相结合，对不同优先级、不同簇的人群分别进行处理，简化了预测过程。实验结果表明：使用合理的聚类参数，能够将人群划分为符合实际人群模式的不同簇，确保了聚类的有效性和准确性；对聚类的噪声点，使用优先级策略作为保底策略，保证这些数据能够得到处理。同时，本研究设计了合理的人群聚类结果与优先级策略相结合的方案，将结合的结果传递给预测主程序使用；另外，对于DBSCAN聚类算法存在的计算速度慢的问题，进一步提出了多线程并行处理的优化方案，达到尽可能小的数据处理时延。

综合来讲，本研究完整地进行了将DBSCAN算法应用于简化人群预测任务的分析，通过详尽的理论分析、实验设计、实验结果记录算法优化，论证了所提出方法的可实施性，为自动驾驶人群预测的简化处理提供了新的有价值的思路。

6.2研究展望

首先，未来，需要继续对更多的人车交互的人群预测场景进行实际的参数优化，以符合实际的预测场景。其次，针对本研究中提出的多线程优化DBSCAN聚类算法的方案，在这里只提供了实现的思路，有待进一步实现。最后，人群聚类选择DBSCAN算法的原因在于其与人群类别拟合的相似度和对离群值的容忍度，这与实际的人群预测任务是相符的。其他聚类算法在人群预测中的应用是未来需要开展的研究。

参考文献

[1]林若希.现实场景下的行人轨迹预测方法研究[D].四川：电子科技大学，2023.

[2]刘健，赵光哲，杨瀚霆.改进注意力机制和图卷积网络的人群轨迹预测[J].计算机仿真，2023，40（10）：274-279.

[3]白竹，马文慧，秘梦迪，等.基于改进DBSCAN的网约车出行需求预测[J].黑龙江工程学院学报，2024，38（2）：28-36.

[4]王军，高建杰.基于DBSCAN算法的城市交通小区划分[J].智能城市，2023，9（2）：80-82.

[5]宋金玉，郭一平，王斌.DBSCAN聚类算法的参数配置方法研究[J].计算机技术与发展，2019，29（5）：44-48.

[6]李文杰，闫世强，蒋莹，等.自适应确定DBSCAN算法参数的算法研究[J].计算机工程与应用，2019，55（5）：1-7，148.

[7]杜泉成，王晓，李灵犀，等.行人轨迹预测方法关键问题研究：现状及展望[J].智能科学与技术学报，2023，5（2）：143-162.

[8]杜青松，李慧，刘振渤，等.基于DBSCAN算法的出租车载客热点分析[J].现代信息科技，2023，7（19）：89-93，98.

[9]于展.基于聚类算法的上海轨道交通站点高峰特征分析[J].城市轨道交通研究，2023，26（Z2）：140-144.

[10]蔡进国，郭宏，李伟强，等.多核多线程环境下的程序并行优化方法[J].现代计算机（普及版），2014（3）：3-5，14.