基于占空比的聚類算法評價指標研究

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

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

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

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

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

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

1 文獻綜述

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

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

2 研究方法

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

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

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

算法改進的DBSCAN聚類算法

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

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

MaxEps 是兩個平面坐標點之間的最大距離，可以根據(jù)實際意義靈活確定。

MinEps 是兩個平面坐標點之間的最小距離，可以根據(jù)實際意義靈活確定。

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

MaxNum設置了聚類閾值的上限，因為如果聚類的數(shù)量太大，數(shù)據(jù)集可能無法形成有效的聚類。

MinNum 設置集群閾值的下限。如果聚類的數(shù)量太少，可能會導致聚類太多，甚至一個點變成一個類，沒有最終計算結果。

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

（2）輸出參數(shù)

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

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

BestEps是E的最佳值，最初設置為0。

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

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

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

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

（2）生成聚類結果

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

（3）評價聚類結果

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

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

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

2.2 基于占空比的聚類評價指標

通常，選擇聚類評價指標來評價聚類結果的質(zhì)量，也稱為聚類有效性分析。一個好的集群劃分應具有以下特點：不同集群中的樣本盡可能地不同，同一集群中的樣本盡可能地相似。

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

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

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

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

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

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

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

3 案例驗證

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

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

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

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

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

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

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

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

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

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

3.2 參數(shù)選擇對比

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

聚類太少點或太多點都沒有實際意義，因為聚類坐標閾值太小可能是一個噪聲點，很難找到閾值較大的聚類。因此，在本文的實驗中，MinPts的閾值設置在（8，13）以內(nèi)，后續(xù)的實驗測試是基于此范圍的。

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

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

圖3 聚類結果的頻率Fig.3 Frequency of clustering results

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

表2 不同性能參數(shù)實驗結果Table 2 Experimental results of different performance parameters

3.3 評價指標對比

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

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

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

表3 不同評價指標的緊度評價結果Table 3 Compactness results of diffenent evaluation indexes

表4 不同評價指標的分離度評價結果Table 4 Separation results of diffenent evaluation indexes

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

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

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

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

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

圖4 不同性能指標的聚類結果Fig.4 Clustering results of different validity indexes

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

表6 分離度和緊度評價結果Table 6 Evaluation results of compactness and separation

4 結論

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

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

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