應用DBSCAN算法簡化人群預測的方法分析

摘要：行人的預測直接影響到自動駕駛系統(tǒng)的安全性和可靠性，尤其是密集人群場景的行人預測。傳統(tǒng)的人群預測方法通過對人群進行優(yōu)先級分類，再按照不同優(yōu)先級對行人逐個預測。但是，在密集人群場景，因為預測目標較多，即使正確劃分了優(yōu)先級，單純依靠這種方法也會帶來很大的處理時延。使用空間密度聚類（Density-BasedSpatialClusteringofApplicationswithNoise，DBSCAN）算法對密集人群場景進行分析，選擇合理的聚類算法參數(shù)，在聚類結果的基礎上，結合傳統(tǒng)優(yōu)先級分類算法，簡化人群的處理，并提出多線程并行處理的方法，以提高聚類算法的效率。通過對DBSCAN算法應用于人群預測的分析，豐富了人群預測的方法，為優(yōu)化自動駕駛行人預測的表現(xiàn)提供了重要參考。

關鍵詞：人群預測空間密度聚類人群聚類算法優(yōu)化

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

傳統(tǒng)的統(tǒng)計方法和機器學習模型如隱馬爾科夫模型、支持向量機等可被用于行人意圖和軌跡的預測，但是，這些方法依賴于人工設置的特征和參數(shù)，然而，這些參數(shù)并不總是能反映人群的運動規(guī)律和行為模式[1]。而基于深度學習的方法，通過大量的數(shù)據(jù)，以及設計相對復雜的網(wǎng)絡結構，例如：采用長短期記憶網(wǎng)絡、卷積神經(jīng)網(wǎng)絡等進行人群的預測，一方面，模型的訓練效果并不總是理想，另一方面，模型的加載和推理都會占用大量的內存并帶來耗時的問題[2]。

本研究提出一種更高效的、易于實施的人群預測方法，即應用空間密度聚類（Density-BasedSpatialClusteringofApplicationswithNoise，DBSCAN）算法來簡化人群預測的過程。該方法不需要人工選擇特征和大量的積累數(shù)據(jù)，也不存在資源占用和耗時方面的問題。通過將DBSCAN算法應用于人群預測領域，筆者期望能夠實現(xiàn)對人群數(shù)據(jù)的快速聚類和分析，再結合優(yōu)先級的設置，對不同類別的人群和行人進行預測，從而簡化預測過程，提高預測精度和效率。為了實現(xiàn)上述目的，需要解決以下一些問題（1）如何有效地將DBSCAN算法應用于人群預測領域；（2）如何處理人群中的噪聲和異常值；（3）如何將DBSCAN的聚類結果和預測任務相結合；（4）如何評估DBSCAN算法應用于人群預測的性能。

綜上，本研究旨在通過應用DBSCAN算法來簡化人群預測的過程，并解決上述關鍵問題。通過深入研究和實踐，為人群預測領域的發(fā)展提供新的思路和方法。

• DBSCAN算法的概述

1.1DBSCAN算法

DBSCAN算法是一種基于密度的空間聚類算法[3]。該算法將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，它基于一組“鄰域”參數(shù)來刻畫樣本分布的緊密程度。DBSCAN先發(fā)現(xiàn)密度較高的點，然后把相近的高密度點逐步連成一片，進而生成各種簇[4]。

1.2算法參數(shù)選擇

DBSCAN算法的兩個必須參數(shù)，分別是鄰域半徑和最少點MinPts[5]。（1）鄰域半徑的選取通過繪制距離曲線得到，距離曲線利用了K最近鄰（k-NearestNeighbor，KNN）算法，在距離曲線明顯拐點位置為對應較好的參數(shù)。若鄰域半徑設置過小，大部分數(shù)據(jù)不能聚類；若參數(shù)設置過大，多個簇和大部分對象會歸并到同一個簇中。（2）最少點MinPts結合指導性原則來確定，即MinPts≥dim+1，其中，dim表示待聚類數(shù)據(jù)的維度[6]。

• 人群預測方法的介紹

2.1預測方法的分類

常見的人群預測方法分為三大類：一是傳統(tǒng)的基于規(guī)則的人群預測算法；二是基于統(tǒng)計和機器學習的方法；三是基于深度學習的方法。

2.2傳統(tǒng)預測方法的局限性

（1）基于規(guī)則的人群預測算法。其對人群的特征和分布沒有進行分析，所有目標按照設定的優(yōu)先級規(guī)則進行分類預測，密集人群場景可能帶來準確性和大時延的問題[7]。

（2）基于統(tǒng)計和機器學習的方法。其需要手工篩選人群的特征、訓練模型參數(shù)，對特征、參數(shù)和數(shù)據(jù)量都有很大依賴，對離散數(shù)據(jù)的處理也不盡如人意[8]。

（3）基于深度學習的方法。其對數(shù)據(jù)量有很大的要求，而且對系統(tǒng)資源占用和性能也有明顯的影響，容易導致很大的資源占用，加大預測耗時，影響系統(tǒng)表現(xiàn)[9]。

綜合來說，傳統(tǒng)預測方法在合理性、效率和工程實現(xiàn)上都有不同程度的局限性。

• DBSCAN算法在人群預測中的應用

3.1方法設計

3.1.1數(shù)據(jù)預處理

需要積累和提取人群信息，提供行人的基本信息如坐標、編號等。從公開數(shù)據(jù)集中選取一定量的行人數(shù)據(jù)并提取行人信息。

3.1.2參數(shù)選擇

DBSCAN算法的性能受到兩個主要參數(shù)和MinPts的影響。筆者根據(jù)對已有數(shù)據(jù)的分析，通過距離曲線集，確定鄰域半徑，結合指導性原則，確定最小點個數(shù)。

3.1.3聚類分析

分別使用不同的參數(shù)對人群進行聚類處理，算法將自動地識別出數(shù)據(jù)中的簇，并將不屬于任何簇的點視為噪聲。通過查看聚類結果，可以發(fā)現(xiàn)不同人群的行為模式，如結伴而行的人群、集體通行過馬路的人群等。

3.1.4特征處理

在聚類分析的基礎上，可以進一步提取與人群預測相關的特征，如人群的簇ID、每個簇的平均位置、核心點、邊界點和離散點等信息，提供給預測任務處理模塊，這些特征結合優(yōu)先級信息作為行人預測的輸入變量來預測其未來的行為。

3.1.5結果可視化

為了方便理解和分析預測結果，可以使用可視化技術將結果以圖形或圖像的形式展示出來，將相同的簇用同一種顏色標識、不同的簇通過顏色進行區(qū)分，以展示人群聚類的結果。

3.2案例分析

為了驗證DBSCAN算法在人群預測中的有效性，筆者從公共數(shù)據(jù)集上選取了若干行人數(shù)據(jù)作為研究對象。這些行人數(shù)據(jù)具有豐富的人車交互場景，包括過馬路人群、散步人群、橫穿和闖紅燈場景等。

首先，利用DBSCAN算法對人群數(shù)據(jù)進行聚類，研究了選取不同聚類參數(shù)時的聚類效果。其次，按照不同簇、簇中的核心對象和邊界對象，以及離群對象，結合優(yōu)先級策略，對人群做簡化處理，包括將ignore級別的人群直接忽略、對normal級別的人群挑選邊界點對象進行處理、對caution級別的目標及其同簇內的所有邊界點對象都進行處理。

通過對比分析發(fā)現(xiàn)，當選擇合適的參數(shù)時，能夠完成人群的合理聚類。結合優(yōu)先級處理策略，一方面減少了要預測的目標，另一方面保證了必要目標能夠得到合理預測。在所選取的行人數(shù)據(jù)場景下，聚類結果和實際應賦予人群的關注度具有較高的吻合度，這表明DBSCAN算法在人群預測中有較好的應用前景和實用價值。

• 實驗結果與分析

4.1實驗設計

如3.1中所述，首先，從公開的實際測試數(shù)據(jù)（包括argoverse數(shù)據(jù)集和D2-city數(shù)據(jù)集）中篩選出500條含有人群的數(shù)據(jù)，通過Python程序，將每條數(shù)據(jù)提取出必要特征，包含ID和坐標信息。然后，對所有數(shù)據(jù)進行統(tǒng)計，繪制距離曲線圖，初步找到備選參數(shù)值，使用不同的參數(shù)對行人數(shù)據(jù)進行聚類處理，統(tǒng)計類別方差，并結合可視化結果，選擇最優(yōu)參數(shù)。在此基礎上，結合優(yōu)先級策略，給出簡化后的人群預測方案，并進行合理性分析。

4.2數(shù)據(jù)獲取

實驗的完整代碼見https：//github.com/yt/dbscan。通過對所有行人數(shù)據(jù)距離進行計算并排序，可以得到距離曲線圖。類似地，其他腳本也都可以在鏈接網(wǎng)站上獲取。

4.3實驗結果

4.3.1距離曲線圖

如圖1所示，圓點是距離值，+表示擬合的結果。可以看到，=4時，拐點處對應的縱軸取值為3.19；=3時，拐點處對應的縱軸取值為2.4，即可以用這兩個統(tǒng)計得到的行人聚類鄰域半徑測試。

4.4結果分析

如圖2所示，若鄰域半徑或最小點設置過小，大部分行人數(shù)據(jù)不能聚類；若鄰域半徑或最小點設置過大，多個簇和大部分行人將歸并到同一個簇中。通過結合距離曲線圖手肘法和實際行人數(shù)據(jù)的聚類效果，選擇對本次實驗來說最優(yōu)的聚類參數(shù)。

因此，對選定的數(shù)據(jù)來說，[，MinPts]=[2.5，3]是更合理的參數(shù)結果。聚類后，得到多個簇，在此聚類的基礎上，結合優(yōu)先級處理策略：對于caution級別的目標，該目標及其所在簇的所有邊界點目標都按照caution級別策略進行處理；對于normal級別的目標，只處理該目標所在簇的邊界點目標；對于ignore級別的目標，其所在簇的所有目標均ignore，即不進行處理。

結合優(yōu)先級的所有人群，繼續(xù)進行預測后續(xù)流程，即聚類和優(yōu)先級分配后的結果正常預測。

• 優(yōu)化與改進

5.1參數(shù)優(yōu)化

如上所述，在選取參數(shù)的過程，一方面參考了距離曲線圖，用手肘法選擇參考值。另一方面，結合實際聚類效果，確定最終的人群聚類參數(shù)。但是，由于數(shù)據(jù)量有限，無法覆蓋所有的人車交互場景，并且不同地方的道路結構設施不一致也會導致人群的不同行為模式。因此，在具體的應用過程中，需要結合應用場景對參數(shù)進行優(yōu)化。本次研究主要探討了DBSCAN算法用于人群預測簡化處理的可行性和有效性，為將來可能的應用提供參考。

5.2算法優(yōu)化

原始的DBSCAN算法步驟計算效率較為低下，在實際應用中（通常是c++代碼），可以使用多線程對聚類過程進行加速[10]，具體的方案設計如下：第一步，分配處理數(shù)據(jù)的線程數(shù)，如numofthreads=N；第二步，當人群人數(shù)大于一定閾值時，如numofpeople=M，采取多線程處理策略；第三步，將數(shù)據(jù)劃分為多個groups，numofgroups=M/N，每個group的行人由一個線程處理；第四步，多線程并行，所有數(shù)據(jù)處理完后，同步簇信息，即線程A得到的簇和線程B得到的簇在理論上屬于同一個簇（通過設置overlap屬性可得到該信息0，那么，和合并為同一個簇c。如此，原始算法的并發(fā)處理策略通過多線程優(yōu)化為并行處理策略，按照此算法優(yōu)化方案，能進一步縮短人群聚類的時間。

• 結論與展望

6.1研究結論

本研究對比了傳統(tǒng)的人群預測方法，發(fā)現(xiàn)這些方法存在對特征和數(shù)據(jù)量依賴、資源占用和時延大等問題，通過將DBSCAN算法應用于人群預測，能夠實現(xiàn)人群的快速聚類，將聚類結果與優(yōu)先級分配策略相結合，對不同優(yōu)先級、不同簇的人群分別進行處理，簡化了預測過程。實驗結果表明：使用合理的聚類參數(shù)，能夠將人群劃分為符合實際人群模式的不同簇，確保了聚類的有效性和準確性；對聚類的噪聲點，使用優(yōu)先級策略作為保底策略，保證這些數(shù)據(jù)能夠得到處理。同時，本研究設計了合理的人群聚類結果與優(yōu)先級策略相結合的方案，將結合的結果傳遞給預測主程序使用；另外，對于DBSCAN聚類算法存在的計算速度慢的問題，進一步提出了多線程并行處理的優(yōu)化方案，達到盡可能小的數(shù)據(jù)處理時延。

綜合來講，本研究完整地進行了將DBSCAN算法應用于簡化人群預測任務的分析，通過詳盡的理論分析、實驗設計、實驗結果記錄算法優(yōu)化，論證了所提出方法的可實施性，為自動駕駛人群預測的簡化處理提供了新的有價值的思路。

6.2研究展望

首先，未來，需要繼續(xù)對更多的人車交互的人群預測場景進行實際的參數(shù)優(yōu)化，以符合實際的預測場景。其次，針對本研究中提出的多線程優(yōu)化DBSCAN聚類算法的方案，在這里只提供了實現(xiàn)的思路，有待進一步實現(xiàn)。最后，人群聚類選擇DBSCAN算法的原因在于其與人群類別擬合的相似度和對離群值的容忍度，這與實際的人群預測任務是相符的。其他聚類算法在人群預測中的應用是未來需要開展的研究。

參考文獻

[1]林若希.現(xiàn)實場景下的行人軌跡預測方法研究[D].四川：電子科技大學，2023.

[2]劉健，趙光哲，楊瀚霆.改進注意力機制和圖卷積網(wǎng)絡的人群軌跡預測[J].計算機仿真，2023，40（10）：274-279.

[3]白竹，馬文慧，秘夢迪，等.基于改進DBSCAN的網(wǎng)約車出行需求預測[J].黑龍江工程學院學報，2024，38（2）：28-36.

[4]王軍，高建杰.基于DBSCAN算法的城市交通小區(qū)劃分[J].智能城市，2023，9（2）：80-82.

[5]宋金玉，郭一平，王斌.DBSCAN聚類算法的參數(shù)配置方法研究[J].計算機技術與發(fā)展，2019，29（5）：44-48.

[6]李文杰，閆世強，蔣瑩，等.自適應確定DBSCAN算法參數(shù)的算法研究[J].計算機工程與應用，2019，55（5）：1-7，148.

[7]杜泉成，王曉，李靈犀，等.行人軌跡預測方法關鍵問題研究：現(xiàn)狀及展望[J].智能科學與技術學報，2023，5（2）：143-162.

[8]杜青松，李慧，劉振渤，等.基于DBSCAN算法的出租車載客熱點分析[J].現(xiàn)代信息科技，2023，7（19）：89-93，98.

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

[10]蔡進國，郭宏，李偉強，等.多核多線程環(huán)境下的程序并行優(yōu)化方法[J].現(xiàn)代計算機（普及版），2014（3）：3-5，14.