基于層次聚類的共享單車維修點規劃模型

毛昊迪，湯鯤

（1.武漢郵電科學研究院，湖北武漢 430000；2.南京烽火天地通信科技有限公司，江蘇南京 210000）

在綠色交通大力發展的現在，以“最后一公里”為設計目標的共享單車系統越來越盛行。早期由政府牽頭設立的共享單車系統有著固定的停車點位，因此維修點設置之后在很長一段時間內都不會發生變化。隨著互聯網的發展，在2014 年出現了通過手機掃碼使用的共享單車，這類共享單車會根據時間和城市地形形成短期的聚集點。因此如何設置維修點是一個很重要的問題。

國內外對于共享單車的研究主要集中在共享單車的投放[1]、調度[2]，回收[3]和騎行數據的分析[4]上，對于維護確少有涉及。層次聚類算法是一種常用的無監督學習算法，具有簡單、結構明了的優點。通過層次聚類算法可以有效地將相近的共享單車聚集點聚集成一個簇，每個簇的聚類中心即為維修點的坐標。單純的層次聚類算法容易受到局部最優解的影響，已有的解決方法通過剪枝[5]和引入隨機矩陣來避免局部最優[6]。蟻群算法是一種啟發式全局優化算法[7]，這種算法通過引入隨機值來解決局部最優問題。根據蟻群算法，該文提出了一種使用蟻群算法機制的層次凝聚聚類方法，該聚類方法通過使用蟻群算法的信息素機制和隨機選擇機制來選擇聚類方向，通過迭代運算的方式避免出現局部最優解。實驗結果表明，相對于層次聚類和k 均值聚類，該算法的聚類效果提升了10%～20%。

1 模型構建

大數量的共享單車會圍繞地鐵站、公交站、公園入口等地點自發聚集，由于城市地形問題，這種聚集點的分布通常是無規律的。對于無規律元素，可以使用無監督學習方法進行處理，因此聚類算法就是一個非常好的選擇。該文基于層次凝聚聚類(AHC)和蟻群算法(ACO)構建規劃模型，該模型以凝聚層次聚類為主，通過引入蟻群算法的隨機性和迭代機制來減少局部最優解的影響，從而在分布無規律的共享單車聚集點中找到設置維修點的最佳位置。

1.1 層次聚類

層次聚類是一種非常直觀的聚類方法。通過一層一層的合并，從下而上或者從上而下一步一步將距離相近的簇進行合并，最終形成一個樹狀結構[8]。

凝聚層次聚類通過各個元素的鄰近度矩陣來計算簇間的距離，從而將距離最近的兩個簇進行合并。

鄰近度矩陣通常有三種計算方式：

1）單鏈：兩個簇中最近點的鄰近度。

2）全鏈：兩個簇中最遠點的鄰近度。

3）組平均：以兩個簇中所有點間的平均鄰近度作為兩個簇間的鄰近度。

前兩種方法能夠在一定程度上減少噪聲點對于合并過程的影響，提高聚類的準確度，對于該文而言，每一個共享單車的聚集點都要考慮在內，因此對于兩個簇使用所有點間距離的組平均作為鄰近度的計算方式。計算公式如下：

其中，d為鄰近度矩陣，C為簇，m為簇中元素的數量。

1.2 蟻群算法

蟻群算法是在1991 年由意大利學者提出的模擬螞蟻覓食行為的一種優化算法，蟻群算法在很多地方都有應用，如路徑優化[9]和電流過載保護[10]，對于聚類算法，蟻群算法同樣可以起到優化的作用[11]。

蟻群算法的核心機制是信息素濃度機制和概率狀態轉移機制，轉移概率由與距離成反比的啟發式信息和與環境相關的信息素濃度來決定。轉移概率計算公式如下：

其中，τ為信息素濃度；η為啟發式信息，與距離成反比；α為信息素濃度因子，α越大，搜索路徑的隨機性就越小，α越小，蟻群搜索的范圍就越小，越容易陷入局部最優；β為啟發式信息因子，β越大，蟻群就越容易選擇局部最短路徑，β越小，蟻群選擇路徑的隨機性就越大。

在每一只螞蟻走完一步后，就會對路線上的信息素作更改，信息素變化公式如下：

其中，ρ為信息素揮發因子，ρ越小，算法的收斂速率就越慢，ρ過大時，有效路徑就有可能被排除掉，影響最佳路徑的選擇。為第k只螞蟻從i到j時釋放的信息素，通常與i到j的距離成反比。m為螞蟻的個數，螞蟻數量越多，得到的最短路徑就越準確，但是同時算法時間復雜度就越高[12]。

1.3 基于蟻群算法的層次凝聚聚類

新的算法基于蟻群算法中的信息素機制和概率狀態轉移機制進行設計，通過引入隨機變量來避免局部最優的出現。通過將兩個簇的合并看作螞蟻從一個點移動到另一個點的過程來引入隨機變量，最后通過模仿蟻群算法的迭代及目標函數選擇出最佳聚類方案。

對于該文需求而言，每個元素的位置信息都應該被考慮在內，因此聚類結果的好壞應該對每個點的位置都進行判斷，為了突出位置信息的影響，且保證每個維修點到所管理的聚集點的距離應該盡可能短，目標函數如下：

其中，Ci為第i個簇的質心；c為所有元素的質心；Cj為第j個簇；D為歐式距離；k為聚類完成后簇的個數。聚類完成后，當各個簇的質心到所有元素集合的質心的距離越遠，且每個簇中的元素到該簇的質心的距離越近，則聚類效果越好。聚類問題被轉化為求得最大目標函數的問題。

在進行聚類時，不僅只考慮位置信息，同時還要引入信息素濃度和概率隨機機制。參考式（1）與式（2），提出了新的轉移概率如下：

其中，μij為簇i和簇j間的平均信息素濃度，計算公式如下：

其中，τkn為點k與點n間的信息素濃度。

算法中需要的參數有螞蟻數量m、信息素濃度因子α、啟發式信息因子β、初始信息素濃度τ0、迭代次數r、信息素揮發因子ρ，算法步驟如下：

1）對于k個點，將每個點視為一個簇，根據式（1）計算鄰近度矩陣，設置初始信息素濃度矩陣。

2）將m只螞蟻隨機投入到k個點中。

3）隨機選一只沒有移動過的螞蟻，根據鄰近度矩陣和信息素濃度矩陣使用式（5）來計算合并概率。

4）使用輪盤賭的方式選擇合并的簇，如果所有的螞蟻都移動過一次，則根據式（3）更新信息素矩陣并返回，執行第2）步，如果合并后剩余簇的數量大于期望值，則返回，重新執行第3）步。

5）根據式（4）計算目標函數。

6）根據式（3）更新信息素矩陣。

7）與當前保存的局部最佳目標函數值對比，輸出局部最佳目標函數值和最優合并方案。

8）若迭代次數少于r次，則返回，執行第2）步。

9）輸出全局最佳目標函數值和最優合并方案。

在聚類的過程中，為了避免螞蟻出現回環現象，要求每只螞蟻都只能向沒有爬到過的點移動，因此對每只螞蟻都建立一個禁忌表[13]，表中儲存的是還沒有爬到的點，當所有的點位都被爬到后，重置禁忌表。

算法中的參數選擇需要根據實際應用進行調整，參數的選擇會直接影響聚類結果的好壞[14]。對于元素數量較少的數據，一般螞蟻數量/元素數量為1.5[15]。

2 數據集與實驗設置

由于共享單車的聚集點受到地形、公共交通點位置等的影響，而UCI Iirs 數據集中有一類與其他兩類線性無關，故實驗使用了西雅圖2015 年自行車租車行公開的租車點位置信息數據集D1和UCI Iirs 數據集兩類作為測試數據集。

圖2 西雅圖車站數據集D1

UCI Iris 數據集的數據維度為四維，需要對數據集做一定的處理[16]，UCI 數據集采集的主要是鳶尾花的花瓣和花萼的長寬,共三種鳶尾花，觀察發現可以根據花瓣和花萼的面積大小將其分為兩類，因此，對UCI 數據做特殊處理：使用花瓣、花萼的面積作為新數據集的特征，將類數由三類合并成兩類。以降維后的UCI 鳶尾花數據集來模擬特殊地形導致共享單車聚集點出現隔斷式分布的情況。

以經緯度為（47.598 488，-122.390 785）為坐標0 點，以500 m 作為比例尺，代入西雅圖的53 個車站點位，最終得到了一個二維數據集D1。

處理后的兩種數據集如圖1-2 所示。

圖1 UCI Iris數據集

處理后的兩種數據集特征如表1 所示。

表1 數據集特征表

經過多次實驗，最終選定實驗參數如表2 所示。

表2 參數設置表

3 實驗結果與分析

為了體現算法的提升效果，最終選定常見的采用組平均規則的層次凝聚聚類和k-means 聚類作為參考進行對比。在設置聚類簇數為2 時，運行20 次后求平均值。對比結果如表3 所示。

表3 聚類準確率

由表3 可知，當聚成兩類時，在西雅圖車站數據集上，三種聚類方法的效果區別不大，該文算法的準確性略高于k-means 算法，與普通層次凝聚聚類相近。但是在降維后的Iris 數據集上，由于右上角三個噪聲點的存在，基于組平均的普通層次凝聚聚類完全無法區分出兩種大小的鳶尾花，聚類效果較差；由于引入了隨機和迭代機制，該文算法的準確率提高了10%，與k-means 的準確性相近。

該文中，實際只聚集成兩個簇意味著只設置兩個維修點，兩個維修點并不一定能滿足實際需求，因此追加對數據集D1聚類成三類以及四類的實驗，此時使用簇中元素到聚類中心的平均距離代替聚類準確率來判斷聚類結果的好壞，公式如下：

運行20 次后求平均值，實驗結果如表4 所示。

從表4 中可以知，對于處理過的Iris 數據集而言，聚集成四個簇時，k-means 算法略優于該文算法，聚集成三個簇時則相反，這是因為該文算法無法對Iris 數據集的右上角的三個噪聲點進行處理所造成的；但在西雅圖車站數據集上，該文算法相比AHC和k-means，各個元素到聚類中心的距離減少了10%。

表4 聚類效果

4 結論

該文提出了一個基于蟻群優化和層次凝聚聚類的共享單車維修點規劃模型，通過使用信息素機制和概率狀態轉移機制對聚集點進行聚類操作，聚類中心即為維修點的位置。

根據實驗結果顯示，該文方法在所有情況下優于AHC 算法，在絕大多數情況下優于k-means 算法，使用該方法規劃的維修點位置到各個點位的平均距離減少了10%。