應(yīng)用DBSCAN算法簡化人群預(yù)測的方法分析

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

關(guān)鍵詞：人群預(yù)測空間密度聚類人群聚類算法優(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)計(jì)方法和機(jī)器學(xué)習(xí)模型如隱馬爾科夫模型、支持向量機(jī)等可被用于行人意圖和軌跡的預(yù)測，但是，這些方法依賴于人工設(shè)置的特征和參數(shù)，然而，這些參數(shù)并不總是能反映人群的運(yùn)動規(guī)律和行為模式[1]。而基于深度學(xué)習(xí)的方法，通過大量的數(shù)據(jù)，以及設(shè)計(jì)相對復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，例如：采用長短期記憶網(wǎng)絡(luò)、卷積神經(jīng)網(wǎng)絡(luò)等進(jìn)行人群的預(yù)測，一方面，模型的訓(xùn)練效果并不總是理想，另一方面，模型的加載和推理都會占用大量的內(nèi)存并帶來耗時的問題[2]。

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

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

• DBSCAN算法的概述

1.1DBSCAN算法

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

1.2算法參數(shù)選擇

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

• 人群預(yù)測方法的介紹

2.1預(yù)測方法的分類

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

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

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

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

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

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

• DBSCAN算法在人群預(yù)測中的應(yīng)用

3.1方法設(shè)計(jì)

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

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

3.1.2參數(shù)選擇

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

3.1.3聚類分析

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

3.1.4特征處理

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

3.1.5結(jié)果可視化

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

3.2案例分析

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

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

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

• 實(shí)驗(yàn)結(jié)果與分析

4.1實(shí)驗(yàn)設(shè)計(jì)

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

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

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

4.3實(shí)驗(yàn)結(jié)果

4.3.1距離曲線圖

如圖1所示，圓點(diǎn)是距離值，+表示擬合的結(jié)果?？梢钥吹剑?4時，拐點(diǎn)處對應(yīng)的縱軸取值為3.19；=3時，拐點(diǎn)處對應(yīng)的縱軸取值為2.4，即可以用這兩個統(tǒng)計(jì)得到的行人聚類鄰域半徑測試。

4.4結(jié)果分析

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

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

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

• 優(yōu)化與改進(jìn)

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

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

5.2算法優(yōu)化

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

• 結(jié)論與展望

6.1研究結(jié)論

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

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

6.2研究展望

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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