張欣環(huán)，劉宏杰，吳金洪，施俊慶，毛程遠(yuǎn)，孟國連

1.浙江師范大學(xué)道路與交通工程研究中心，浙江 金華 321004

2.西安交通大學(xué)電子信息工程學(xué)院，西安 710049

軌跡挖掘是指以出行者長(zhǎng)期的活動(dòng)軌跡為基礎(chǔ)，將其活動(dòng)軌跡點(diǎn)聚類成一個(gè)個(gè)合適的區(qū)域。城市公共交通系統(tǒng)中，出行者的軌跡數(shù)據(jù)的挖掘是構(gòu)建定制公交網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，也是公交站點(diǎn)選址優(yōu)化的基礎(chǔ)。目前，公交線路及站點(diǎn)的設(shè)置大多以運(yùn)營(yíng)成本最低為目標(biāo)，較少考慮出行者的距離和時(shí)間成本。

本文提出一種改進(jìn)的密度聚類算法（DBSCAN）及其對(duì)應(yīng)的有效性評(píng)價(jià)指標(biāo)，挖掘出行者活動(dòng)軌跡：根據(jù)出行者的起、終點(diǎn)識(shí)別結(jié)果，優(yōu)化站點(diǎn)設(shè)置以減少出行者的步行距離，提升出行體驗(yàn)，提高服務(wù)可靠性，節(jié)約出行成本，并為智慧城市構(gòu)建定制公交網(wǎng)絡(luò)提供數(shù)據(jù)支撐。

根據(jù)改進(jìn)的DBSCAN 算法、全新的軌跡聚類結(jié)果的有效性指標(biāo)來實(shí)現(xiàn)DBSCAN 輸入?yún)?shù)的自動(dòng)選擇。該指標(biāo)平衡了聚內(nèi)凝聚度、聚類間距和聚類內(nèi)密度，計(jì)算出密度聚類模型的最優(yōu)輸入?yún)?shù)值，從而避免了人為設(shè)定參數(shù)的局限性。比對(duì)仿真數(shù)據(jù)和延安市公共交通出行數(shù)據(jù)后，可以看出該有效性評(píng)價(jià)指標(biāo)在基于密度的地理位置信息聚類中優(yōu)于傳統(tǒng)的評(píng)價(jià)指標(biāo)。

1 文獻(xiàn)綜述

軌跡聚類是軌跡模式挖掘的一種，軌跡聚類的目標(biāo)是尋找不同運(yùn)動(dòng)對(duì)象共有的代表性路徑或共同趨勢(shì)[1]。許多文獻(xiàn)都采用了不同的方法來實(shí)現(xiàn)軌跡挖掘的目標(biāo)。Cheng 等[2]將軌跡劃分為子軌跡段，然后應(yīng)用基于密度的聚類算法對(duì)子軌跡進(jìn)行聚類，挖掘出熱點(diǎn)。Wang[3]提出了一種基于網(wǎng)格的移動(dòng)軌跡挖掘算法，首先基于網(wǎng)格劃分?jǐn)?shù)據(jù)，然后使用DBSCAN 對(duì)每個(gè)網(wǎng)格進(jìn)行聚類。由于集群的數(shù)量是FCM 集群所需的輸入，所以Choong 等[4]指定了三個(gè)數(shù)字作為參數(shù)。但是，以上方法只對(duì)軌跡數(shù)據(jù)進(jìn)行切片或網(wǎng)格化，然后將聚類算法應(yīng)用到實(shí)際的軌跡聚類場(chǎng)景中。由于聚類算法本身沒有改進(jìn)，所以聚類參數(shù)不夠精確，不能達(dá)到最優(yōu)結(jié)果。

DBSCAN 由于其簡(jiǎn)單性和檢測(cè)不同大小、形狀的集群的能力，在許多科學(xué)領(lǐng)域得到了廣泛的應(yīng)用。由于傳統(tǒng)的DBSCAN算法在選擇聚類參數(shù)時(shí)嚴(yán)重依賴于用戶的手工經(jīng)驗(yàn)，如果用戶沒有足夠的實(shí)踐經(jīng)驗(yàn)來確定適當(dāng)?shù)膮?shù)值，那么輸入?yún)?shù)的取值不當(dāng)可能會(huì)影響聚類結(jié)果的質(zhì)量。為了克服這一缺陷，一方面，一些研究人員將兩種方法結(jié)合起來確定參數(shù)，Sharma等[5]結(jié)合K-近鄰算法和DBSCAN實(shí)現(xiàn)無參數(shù)聚類技術(shù)，Hou等[6]混合Dsets（優(yōu)勢(shì)集）與DBSCAN 自動(dòng)查找取值，但是這些方法需要至少兩次處理數(shù)據(jù)，復(fù)雜的步驟不適合大規(guī)模的數(shù)據(jù)。另一方面，改進(jìn)聚類算法的有效性指標(biāo)，也可以有效地選擇聚類參數(shù)，提高聚類效果。Duun index（鄧恩指數(shù)）[7]、DBI（Davies-Bouldin index）指數(shù)[8]和輪廓（Silhouette）系數(shù)[9]是評(píng)價(jià)無標(biāo)記聚類算法的三個(gè)基本指標(biāo)。Zhou 等[10]設(shè)計(jì)了一個(gè)新的聚類有效性指標(biāo)，稱為緊-分離比例（compact-separate proportion，CSP）指數(shù)，以評(píng)估AHC 算法產(chǎn)生的聚類結(jié)果，并確定最優(yōu)的聚類數(shù)目。Karo 等[11]提出了一種利用多邊形不相似度函數(shù)（polygon dissimilarity function，PDF）對(duì)Davies Bouldin指數(shù)進(jìn)行修正的空間區(qū)域聚類有效性指標(biāo)。Acharya等[12]在四種已知的聚類效度指標(biāo)的定義中引入了一種新的基于線對(duì)稱的距離效度指標(biāo)。Thomas等[13]用圓柱距離代替了歐幾里德距離，該距離嘗試捕獲沿連接均值線段的數(shù)據(jù)密度，以估計(jì)聚類均值之間的距離。江玉鈴等[14]為挖掘AIS數(shù)據(jù)中有關(guān)船舶運(yùn)動(dòng)規(guī)律有效的、潛在的信息，利用類似DBSCAN算法對(duì)軌跡段進(jìn)行聚類，得出船舶運(yùn)動(dòng)典型軌跡。周培培等[15]針對(duì)現(xiàn)有的異常軌跡檢測(cè)算法往往側(cè)重于檢測(cè)軌跡的空域異常，忽略了對(duì)軌跡時(shí)域異常的檢測(cè)，并且檢測(cè)精確度不高等問題，提出了基于增強(qiáng)聚類的異常軌跡檢測(cè)算法。然而，現(xiàn)有的有效性指標(biāo)一般都是針對(duì)二維人工數(shù)據(jù)集，只關(guān)注聚內(nèi)凝聚度、聚類間距，而忽略了聚類內(nèi)密度。這意味著這些方法的聚類結(jié)果可能會(huì)變成長(zhǎng)條聚類，這在現(xiàn)實(shí)生活中是不合理的。針對(duì)這些指標(biāo)的缺陷，有必要對(duì)DBSCAN 及其有效性指標(biāo)同時(shí)進(jìn)行改進(jìn)，以正確找出出行者位置信息數(shù)據(jù)集的最優(yōu)聚類數(shù)。

2 研究方法

2.1 無參數(shù)的DBSCAN算法

DBSCAN 的應(yīng)用程序需要兩個(gè)重要參數(shù)：給定點(diǎn)在鄰域內(nèi)成為核心對(duì)象的最小鄰域點(diǎn)數(shù)MinPts，鄰域半徑Eps。然而在選擇這兩個(gè)聚類參數(shù)時(shí)，DBSCAN算法依賴于用戶的實(shí)踐經(jīng)驗(yàn)。本節(jié)使用改進(jìn)的DBSCAN聚類算法對(duì)數(shù)據(jù)進(jìn)行聚類，可以自動(dòng)確定輸入?yún)?shù)。

本文提出的改進(jìn)DBSCAN 算法中，將聚類過程產(chǎn)生的聚類結(jié)果作為評(píng)價(jià)函數(shù)的輸入?yún)?shù)，然后得到評(píng)價(jià)結(jié)果，具體表達(dá)如下：

算法改進(jìn)的DBSCAN聚類算法

（1）輸入?yún)?shù)

D是當(dāng)前輸入數(shù)據(jù)集。D1(x1,y1)表示集合中平面坐標(biāo)的x和y。

MaxEps 是兩個(gè)平面坐標(biāo)點(diǎn)之間的最大距離，可以根據(jù)實(shí)際意義靈活確定。

MinEps 是兩個(gè)平面坐標(biāo)點(diǎn)之間的最小距離，可以根據(jù)實(shí)際意義靈活確定。

E表示集合中任意兩點(diǎn)之間的距離，取值范圍為MinEps和MaxEps之間。

MaxNum設(shè)置了聚類閾值的上限，因?yàn)槿绻垲惖臄?shù)量太大，數(shù)據(jù)集可能無法形成有效的聚類。

MinNum 設(shè)置集群閾值的下限。如果聚類的數(shù)量太少，可能會(huì)導(dǎo)致聚類太多，甚至一個(gè)點(diǎn)變成一個(gè)類，沒有最終計(jì)算結(jié)果。

M確定了某個(gè)集群的最優(yōu)數(shù)量閾值，其值范圍在MaxNum和MinNum之間。

（2）輸出參數(shù)

ResultC是聚類結(jié)果，使用不同的輸入?yún)?shù)可以得到不同的聚類結(jié)果。

MinIedci是最小占空比，最初設(shè)置為無窮大。

BestEps是E的最佳值，最初設(shè)置為0。

BestMinPts是M的最佳值，初始值為0。

不同的輸入?yún)?shù)會(huì)產(chǎn)生不同的聚類結(jié)果。為了防止丟失某些參數(shù)，該算法給出了輸入?yún)?shù)的范圍，遍歷該范圍內(nèi)的所有參數(shù)值，然后生成聚類結(jié)果。通過對(duì)聚類結(jié)果的評(píng)價(jià)和計(jì)算，可以得到最優(yōu)的評(píng)價(jià)值，并基于反向傳播法計(jì)算出最優(yōu)的輸入?yún)?shù)。算法流程如下：

（1）構(gòu)建輸入?yún)?shù)范圍

在不同的應(yīng)用場(chǎng)景中，最佳的聚類輸入?yún)?shù)值在一定范圍內(nèi)波動(dòng)。由于輸入?yún)?shù)的范圍決定了算法執(zhí)行的效率和找到最優(yōu)值的可能性，因此在算法執(zhí)行之前建立一個(gè)合適的輸入?yún)?shù)范圍就顯得尤為重要。聚類次數(shù)過多，數(shù)據(jù)集可能無法形成有效的聚類；聚類次數(shù)過少，聚類過于分散，不實(shí)用。此外，聚類點(diǎn)之間的距離會(huì)影響聚類內(nèi)的緊度。如果距離度量太大，聚類太離散，無法有效區(qū)分不同的聚類。如果距離度量太小，則聚類距離太近，可能會(huì)產(chǎn)生太多瑣碎、無價(jià)值的聚類結(jié)果。因此，在聚類的前期，首先要確定Eps 和MinPts 的最大值和最小值，從而構(gòu)建聚類參數(shù)的有效范圍。

（2）生成聚類結(jié)果

以步驟1的鄰域半徑范圍為輸入?yún)?shù)，進(jìn)行循環(huán)密度聚類，完成所有出行者6 個(gè)月內(nèi)軌跡點(diǎn)的聚類計(jì)算，并保存各聚類結(jié)果（resultC）。

（3）評(píng)價(jià)聚類結(jié)果

利用輪廓系數(shù)、DBI 指數(shù)以及本文提出的內(nèi)外占空比指數(shù)IEDCI（internal and external duty cycle index）等評(píng)價(jià)指標(biāo)對(duì)各聚類結(jié)果進(jìn)行評(píng)價(jià)，并將最佳聚類參數(shù)BestEps和BestMinPts保存到評(píng)價(jià)指標(biāo)中。

（4）獲得最優(yōu)聚類結(jié)果

以步驟（3）中的BestEps 和BestMinPts 為輸入?yún)?shù)，計(jì)算最佳聚類結(jié)果。本文的聚類結(jié)果是出行者實(shí)際活動(dòng)軌跡的聚類，是后續(xù)研究中出行者所有可能出行的起、終點(diǎn)。

2.2 基于占空比的聚類評(píng)價(jià)指標(biāo)

通常，選擇聚類評(píng)價(jià)指標(biāo)來評(píng)價(jià)聚類結(jié)果的質(zhì)量，也稱為聚類有效性分析。一個(gè)好的集群劃分應(yīng)具有以下特點(diǎn)：不同集群中的樣本盡可能地不同，同一集群中的樣本盡可能地相似。

通過對(duì)出行者歷史軌跡的研究，發(fā)現(xiàn)影響聚類結(jié)果的因素不僅包括聚類的內(nèi)聚程度和聚類之間的邊界距離，還包括聚類中軌跡點(diǎn)的數(shù)量。傳統(tǒng)的評(píng)價(jià)指標(biāo)由于只考慮了聚類的內(nèi)聚程度和聚類間距等系數(shù)，在軌跡聚類方面存在一定的局限性。在進(jìn)行聚類凝聚度評(píng)價(jià)時(shí)，沒有考慮聚類內(nèi)密度，忽略了聚類內(nèi)部個(gè)數(shù)與聚類大小的關(guān)系。在不規(guī)則聚類中，單個(gè)變量的影響程度往往過大，聚類結(jié)果往往停留在邊界點(diǎn)上，無法實(shí)現(xiàn)參數(shù)的最優(yōu)選擇。

針對(duì)現(xiàn)有的評(píng)價(jià)指標(biāo)不適合基于密度的地理位置信息聚類問題，本文提出了一種基于聚類內(nèi)外占空比的有效性指標(biāo)IEDCI。內(nèi)外占空比公式如下：

根據(jù)公式（1），內(nèi)外占空比涉及三個(gè)區(qū)域（如圖1所示）：si、sj和si+j，其中si、sj為第i、j類中最外層點(diǎn)圍成的區(qū)域，si+j表示兩個(gè)類合并后最外層點(diǎn)圍成的區(qū)域。利用占空比平衡聚類內(nèi)距離和聚類間距離的關(guān)系，解決單點(diǎn)成類或所有點(diǎn)成類的不適當(dāng)情況。面積是一個(gè)二維的標(biāo)準(zhǔn)，可以用來評(píng)估兩個(gè)類的離散程度，從而有效地避免兩個(gè)類中某些點(diǎn)可能存在的線性極值距離。

圖1 占空比系數(shù)示意圖Fig.1 Duty cycle coefficient diagram

在定義了內(nèi)外部占空比的概念后，提出了基于內(nèi)外部占空比的評(píng)價(jià)指標(biāo)IEDCI，公式如下：

為尋找最優(yōu)的輸入?yún)?shù)和最優(yōu)聚類結(jié)果，本文提出了一種基于聚類點(diǎn)和聚類占空比的有效性評(píng)價(jià)指標(biāo)，用于評(píng)估不同輸入?yún)?shù)所產(chǎn)生的聚類結(jié)果，并根據(jù)之前的反饋確定當(dāng)前的最佳輸入?yún)?shù)。

輪廓系數(shù)和DBI 在處理聚類結(jié)果時(shí)只考慮聚內(nèi)凝聚度、聚類間距的關(guān)系，沒有充分考慮單個(gè)聚類結(jié)果中聚類點(diǎn)對(duì)整體聚類效果的影響。因此，本文提出的聚類評(píng)價(jià)優(yōu)于上述評(píng)價(jià)函數(shù)。

3 案例驗(yàn)證

3.1 數(shù)據(jù)集

3.1.1 仿真數(shù)據(jù)集

仿真數(shù)據(jù)集為計(jì)算機(jī)模擬生成的隨機(jī)數(shù)。每個(gè)數(shù)據(jù)集有1 200 個(gè)點(diǎn)，每個(gè)點(diǎn)都以坐標(biāo)的形式表示并劃分為一個(gè)簇。這些數(shù)據(jù)集是清晰簇、模糊簇、暈簇和非簇（如圖2 所示），在這些數(shù)據(jù)集中，清晰簇和模糊簇的結(jié)構(gòu)是凸的，暈簇的結(jié)構(gòu)是環(huán)形的，而非簇的結(jié)構(gòu)是飛濺的。

圖2 二維合成數(shù)據(jù)集Fig.2 2-D synthetic data sets

3.1.2 案例數(shù)據(jù)集

本文使用的案例數(shù)據(jù)來自Yi Bus 手機(jī)APP。Yi Bus是一款手機(jī)APP，可以查詢附近的車站、線路換乘、實(shí)時(shí)到達(dá)預(yù)測(cè)等交通信息。在本文中，使用了延安市近6個(gè)月（2020年1月至2020年6月）的500名用戶的位置信息數(shù)據(jù)。一共獲得了500 個(gè).txt 格式的文件，每個(gè)文件代表每位出行者在這6 個(gè)月的所有位置信息。每位出行者的軌跡數(shù)據(jù)由軌跡點(diǎn)x坐標(biāo)和y坐標(biāo)表示，此外，由于數(shù)據(jù)集代表的是真實(shí)的出行者的軌跡點(diǎn)，因此與計(jì)算機(jī)生成的仿真數(shù)據(jù)集相比，數(shù)據(jù)的結(jié)構(gòu)是多種多樣的，包括線性、環(huán)形、凸形和飛濺形。案例數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)如表1 所示，其中UID 為用戶SIM 卡的唯一標(biāo)識(shí)，LNG 為當(dāng)前用戶位置的經(jīng)度，LAT為當(dāng)前用戶位置的維數(shù)，UP_TIME為坐標(biāo)上傳時(shí)間。

表1 延安市公交出行數(shù)據(jù)結(jié)構(gòu)Table 1 Data structure of bus trip in Yan’an city

由于APP 采集的數(shù)據(jù)存在損壞數(shù)據(jù)、重復(fù)數(shù)據(jù)、無效數(shù)據(jù)等情況，需要對(duì)這些數(shù)據(jù)進(jìn)行預(yù)處理。本文主要采用以下兩種方法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。

（1）數(shù)據(jù)清洗：本文對(duì)數(shù)據(jù)的預(yù)處理主要是刪除不相關(guān)的數(shù)據(jù)和重復(fù)的數(shù)據(jù)，對(duì)有噪聲的數(shù)據(jù)進(jìn)行平滑處理。

（2）數(shù)據(jù)ETL（extract-transform-load）：以用戶唯一識(shí)別編碼，從數(shù)據(jù)實(shí)例中抽取用戶的所有行為軌跡，構(gòu)建一個(gè)用戶的單體數(shù)據(jù)集，循環(huán)遍歷所有用戶，最終形成多個(gè)用戶的單體數(shù)據(jù)集，作為整個(gè)聚類集合的候選集。從候選集合中抽取若干候選人作為實(shí)驗(yàn)對(duì)象，確保單一用戶軌跡數(shù)據(jù)大于1 000，構(gòu)建聚類集合。

3.2 參數(shù)選擇對(duì)比

在出行者軌跡挖掘中，Eps 是出行者的行走距離，MinPts是出行者在一定區(qū)域停留的次數(shù)，兩者都有實(shí)際意義。因此，可以根據(jù)實(shí)際意義來劃定參數(shù)范圍。通過對(duì)現(xiàn)有數(shù)據(jù)的統(tǒng)計(jì)，可以得出出行者的行走半徑大部分在20 m 到110 m 之間，因此，本文實(shí)驗(yàn)中將Eps 閾值設(shè)定在（20，110）以內(nèi)，所有后續(xù)的實(shí)驗(yàn)測(cè)試都是基于此范圍的。

聚類太少點(diǎn)或太多點(diǎn)都沒有實(shí)際意義，因?yàn)榫垲愖鴺?biāo)閾值太小可能是一個(gè)噪聲點(diǎn)，很難找到閾值較大的聚類。因此，在本文的實(shí)驗(yàn)中，MinPts的閾值設(shè)置在（8，13）以內(nèi)，后續(xù)的實(shí)驗(yàn)測(cè)試是基于此范圍的。

為了驗(yàn)證改進(jìn)的DBSCAN算法自動(dòng)選擇的參數(shù)性能，本文使用了案例數(shù)據(jù)集并生成聚類結(jié)果，并與其他參數(shù)進(jìn)行比較，包括經(jīng)驗(yàn)值和統(tǒng)計(jì)值。

對(duì)所有輸入?yún)?shù)的結(jié)果進(jìn)行統(tǒng)計(jì)，找出最常見的聚類數(shù)（如圖3 所示）。圖3 統(tǒng)計(jì)此時(shí)的輸入?yún)?shù)，取當(dāng)前輸入?yún)?shù)的中位數(shù)（60，12）作為統(tǒng)計(jì)輸入?yún)?shù)（Eps值為60，MinPts 值為12）。經(jīng)驗(yàn)值獲得的Eps 和MinPts 值分別為85 和10；改良DBSCAN 得到的Eps 和MinPts 分別為65和12。

圖3 聚類結(jié)果的頻率Fig.3 Frequency of clustering results

案例數(shù)據(jù)集共有500 個(gè)個(gè)體的定位點(diǎn)信息。使用緊度、分離度和DBI來評(píng)價(jià)聚類結(jié)果。緊度和DBI代表類的內(nèi)聚度，分離度代表類之間的距離，緊度和DBI 值越小，分離值越高，聚類效果越好。從表2可以看出，本文提出的方法自動(dòng)生成的參數(shù)在分離度和DBI 上取得了更好的聚類效果，與傳統(tǒng)的經(jīng)驗(yàn)值相比，該方法的性能有了很大的提高。

表2 不同性能參數(shù)實(shí)驗(yàn)結(jié)果Table 2 Experimental results of different performance parameters

3.3 評(píng)價(jià)指標(biāo)對(duì)比

為了驗(yàn)證IEDCI 的性能，本文分別使用仿真數(shù)據(jù)集、案例數(shù)據(jù)集來生成聚類結(jié)果，并將其與其他有效性指標(biāo)進(jìn)行比較，包括DBI和輪廓系數(shù)評(píng)價(jià)。

3.3.1 仿真數(shù)據(jù)集

本文使用緊度和分離來評(píng)估四個(gè)仿真數(shù)據(jù)集的聚類結(jié)果。表3為三個(gè)評(píng)價(jià)指標(biāo)的緊度評(píng)價(jià)結(jié)果，從結(jié)果可以看出，IEDCI 對(duì)數(shù)據(jù)集清晰簇、模糊簇和非簇的評(píng)價(jià)值更好。表4為三個(gè)評(píng)價(jià)指標(biāo)的分離度評(píng)價(jià)結(jié)果，從結(jié)果可以看出，IEDCI對(duì)于清晰簇和非簇的數(shù)據(jù)集有更好的評(píng)價(jià)值。

表3 不同評(píng)價(jià)指標(biāo)的緊度評(píng)價(jià)結(jié)果Table 3 Compactness results of diffenent evaluation indexes

表4 不同評(píng)價(jià)指標(biāo)的分離度評(píng)價(jià)結(jié)果Table 4 Separation results of diffenent evaluation indexes

3.3.2 案例數(shù)據(jù)集

本小節(jié)使用案例數(shù)據(jù)集來評(píng)估算法的性能，整個(gè)評(píng)估過程如下。

（1）最優(yōu)輸入選擇：利用輪廓系數(shù)、DBI和IEDCI這三個(gè)評(píng)價(jià)指標(biāo)來執(zhí)行前文的改進(jìn)DBSCAN算法。遍歷參數(shù)范圍內(nèi)所有可能的值后，算法可以得到三個(gè)評(píng)價(jià)函數(shù)對(duì)應(yīng)的最優(yōu)輸入?yún)?shù)，如表5所示。

表5 最佳MinPts和Eps值Table 5 Best value of MinPts and Eps

（2）聚類結(jié)果：使用三個(gè)評(píng)價(jià)指標(biāo)的最優(yōu)輸入值生成三個(gè)不同的聚類結(jié)果。從圖4中可以看出，對(duì)于相同范圍內(nèi)的聚類點(diǎn)，由輪廓系數(shù)評(píng)價(jià)指標(biāo)產(chǎn)生的結(jié)果將紅色橢圓內(nèi)的離散點(diǎn)聚集成一個(gè)類。然而，從出行者軌跡的實(shí)際情況來看，由于出行者活動(dòng)過多，聚類結(jié)果較差。在DBI 聚類結(jié)果中，將紅色橢圓分為兩部分。同理，圖中A點(diǎn)到B點(diǎn)的距離在圖4（b）中遠(yuǎn)遠(yuǎn)超出了人們活動(dòng)的范圍（500 m）。在本文算法的聚類結(jié)果中，出行者活動(dòng)的范圍小于居民軌跡的半徑。因此，該算法在實(shí)際應(yīng)用中表現(xiàn)良好。

圖4 不同性能指標(biāo)的聚類結(jié)果Fig.4 Clustering results of different validity indexes

（3）聚類評(píng)價(jià)：對(duì)生成的聚類結(jié)果進(jìn)行緊度和分離度評(píng)價(jià)，評(píng)價(jià)結(jié)果如表6所示。在充分考慮聚類密度和聚類間距影響的基礎(chǔ)上，本文提出的方法得到的結(jié)果具有更高的分離性和更小的緊致性，這更符合軌跡聚類中人們活動(dòng)的實(shí)際情況。

表6 分離度和緊度評(píng)價(jià)結(jié)果Table 6 Evaluation results of compactness and separation

4 結(jié)論

本文提出了一種全新的出行者軌跡挖掘方法：使用一種全新的評(píng)價(jià)指標(biāo)對(duì)DBSCAN 的輸入?yún)?shù)進(jìn)行評(píng)價(jià)，該評(píng)價(jià)指標(biāo)平衡了聚類內(nèi)距離和聚類間距離，從而獲得了出行者位置信息聚類的最優(yōu)輸入?yún)?shù)，避免了人工經(jīng)驗(yàn)導(dǎo)致的參數(shù)不準(zhǔn)確的問題。其次，基于延安市城市公交出行數(shù)據(jù)，對(duì)本文提出的方法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)表明，本文提出的算法能夠在彈道數(shù)據(jù)集上找到最優(yōu)的輸入?yún)?shù)值。通過對(duì)聚類結(jié)果的緊實(shí)度和分離度的計(jì)算，并與DBI 和輪廓系數(shù)相比，IEDCI 找到的最優(yōu)參數(shù)值具有較小的內(nèi)聚值和較大的聚類間距值。因此，本文提出的算法在挖掘出行者軌跡方面具有良好的性能。

本文提出的方法不僅可以用于出行者位置信息的聚類（以獲取出行起終點(diǎn)），還可以推廣到物流與供應(yīng)鏈管理、汽車動(dòng)態(tài)路由、加油站規(guī)劃等路由問題。因?yàn)樗羞@些問題都是二維地圖上的點(diǎn)聚類問題，而與其他集群不同的是，由于人或車輛有一定的運(yùn)動(dòng)范圍，集群的大小受到限制。

本研究未來的改進(jìn)包括以下兩個(gè)方面：首先，可將用戶的SIM卡定位信息添加到實(shí)驗(yàn)數(shù)據(jù)中，以豐富數(shù)據(jù)多樣性，APP的使用頻率直接決定了當(dāng)前集群的集群密度；其次，可將計(jì)算步長(zhǎng)引入到計(jì)算過程中，以提高整體計(jì)算效率。