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

張欣環，劉宏杰，吳金洪，施俊慶，毛程遠，孟國連

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

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

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

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

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

1 文獻綜述

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

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

2 研究方法

2.1 無參數的DBSCAN算法

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

本文提出的改進DBSCAN 算法中，將聚類過程產生的聚類結果作為評價函數的輸入參數，然后得到評價結果，具體表達如下：

算法改進的DBSCAN聚類算法

（1）輸入參數

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

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

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

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

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

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

M確定了某個集群的最優數量閾值，其值范圍在MaxNum和MinNum之間。

（2）輸出參數

ResultC是聚類結果，使用不同的輸入參數可以得到不同的聚類結果。

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

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

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

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

（1）構建輸入參數范圍

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

（2）生成聚類結果

以步驟1的鄰域半徑范圍為輸入參數，進行循環密度聚類，完成所有出行者6 個月內軌跡點的聚類計算，并保存各聚類結果（resultC）。

（3）評價聚類結果

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

（4）獲得最優聚類結果

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

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

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

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

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

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

圖1 占空比系數示意圖Fig.1 Duty cycle coefficient diagram

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

為尋找最優的輸入參數和最優聚類結果，本文提出了一種基于聚類點和聚類占空比的有效性評價指標，用于評估不同輸入參數所產生的聚類結果，并根據之前的反饋確定當前的最佳輸入參數。

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

3 案例驗證

3.1 數據集

3.1.1 仿真數據集

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

圖2 二維合成數據集Fig.2 2-D synthetic data sets

3.1.2 案例數據集

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

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

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

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

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

3.2 參數選擇對比

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

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

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

對所有輸入參數的結果進行統計，找出最常見的聚類數（如圖3 所示）。圖3 統計此時的輸入參數，取當前輸入參數的中位數（60，12）作為統計輸入參數（Eps值為60，MinPts 值為12）。經驗值獲得的Eps 和MinPts 值分別為85 和10；改良DBSCAN 得到的Eps 和MinPts 分別為65和12。

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

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

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

3.3 評價指標對比

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

3.3.1 仿真數據集

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

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

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

3.3.2 案例數據集

本小節使用案例數據集來評估算法的性能，整個評估過程如下。

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

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

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

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

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

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

4 結論

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

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

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