基于層次聚類的共享單車維修點(diǎn)規(guī)劃模型

毛昊迪，湯鯤

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

在綠色交通大力發(fā)展的現(xiàn)在，以“最后一公里”為設(shè)計(jì)目標(biāo)的共享單車系統(tǒng)越來越盛行。早期由政府牽頭設(shè)立的共享單車系統(tǒng)有著固定的停車點(diǎn)位，因此維修點(diǎn)設(shè)置之后在很長(zhǎng)一段時(shí)間內(nèi)都不會(huì)發(fā)生變化。隨著互聯(lián)網(wǎng)的發(fā)展，在2014 年出現(xiàn)了通過手機(jī)掃碼使用的共享單車，這類共享單車會(huì)根據(jù)時(shí)間和城市地形形成短期的聚集點(diǎn)。因此如何設(shè)置維修點(diǎn)是一個(gè)很重要的問題。

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

1 模型構(gòu)建

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

1.1 層次聚類

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

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

鄰近度矩陣通常有三種計(jì)算方式：

1）單鏈：兩個(gè)簇中最近點(diǎn)的鄰近度。

2）全鏈：兩個(gè)簇中最遠(yuǎn)點(diǎn)的鄰近度。

3）組平均：以兩個(gè)簇中所有點(diǎn)間的平均鄰近度作為兩個(gè)簇間的鄰近度。

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

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

1.2 蟻群算法

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

蟻群算法的核心機(jī)制是信息素濃度機(jī)制和概率狀態(tài)轉(zhuǎn)移機(jī)制，轉(zhuǎn)移概率由與距離成反比的啟發(fā)式信息和與環(huán)境相關(guān)的信息素濃度來決定。轉(zhuǎn)移概率計(jì)算公式如下：

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

在每一只螞蟻?zhàn)咄暌徊胶螅蜁?huì)對(duì)路線上的信息素作更改，信息素變化公式如下：

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

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

新的算法基于蟻群算法中的信息素機(jī)制和概率狀態(tài)轉(zhuǎn)移機(jī)制進(jìn)行設(shè)計(jì)，通過引入隨機(jī)變量來避免局部最優(yōu)的出現(xiàn)。通過將兩個(gè)簇的合并看作螞蟻從一個(gè)點(diǎn)移動(dòng)到另一個(gè)點(diǎn)的過程來引入隨機(jī)變量，最后通過模仿蟻群算法的迭代及目標(biāo)函數(shù)選擇出最佳聚類方案。

對(duì)于該文需求而言，每個(gè)元素的位置信息都應(yīng)該被考慮在內(nèi)，因此聚類結(jié)果的好壞應(yīng)該對(duì)每個(gè)點(diǎn)的位置都進(jìn)行判斷，為了突出位置信息的影響，且保證每個(gè)維修點(diǎn)到所管理的聚集點(diǎn)的距離應(yīng)該盡可能短，目標(biāo)函數(shù)如下：

其中，Ci為第i個(gè)簇的質(zhì)心；c為所有元素的質(zhì)心；Cj為第j個(gè)簇；D為歐式距離；k為聚類完成后簇的個(gè)數(shù)。聚類完成后，當(dāng)各個(gè)簇的質(zhì)心到所有元素集合的質(zhì)心的距離越遠(yuǎn)，且每個(gè)簇中的元素到該簇的質(zhì)心的距離越近，則聚類效果越好。聚類問題被轉(zhuǎn)化為求得最大目標(biāo)函數(shù)的問題。

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

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

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

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

1）對(duì)于k個(gè)點(diǎn)，將每個(gè)點(diǎn)視為一個(gè)簇，根據(jù)式（1）計(jì)算鄰近度矩陣，設(shè)置初始信息素濃度矩陣。

2）將m只螞蟻隨機(jī)投入到k個(gè)點(diǎn)中。

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

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

5）根據(jù)式（4）計(jì)算目標(biāo)函數(shù)。

6）根據(jù)式（3）更新信息素矩陣。

7）與當(dāng)前保存的局部最佳目標(biāo)函數(shù)值對(duì)比，輸出局部最佳目標(biāo)函數(shù)值和最優(yōu)合并方案。

8）若迭代次數(shù)少于r次，則返回，執(zhí)行第2）步。

9）輸出全局最佳目標(biāo)函數(shù)值和最優(yōu)合并方案。

在聚類的過程中，為了避免螞蟻出現(xiàn)回環(huán)現(xiàn)象，要求每只螞蟻都只能向沒有爬到過的點(diǎn)移動(dòng)，因此對(duì)每只螞蟻都建立一個(gè)禁忌表[13]，表中儲(chǔ)存的是還沒有爬到的點(diǎn)，當(dāng)所有的點(diǎn)位都被爬到后，重置禁忌表。

算法中的參數(shù)選擇需要根據(jù)實(shí)際應(yīng)用進(jìn)行調(diào)整，參數(shù)的選擇會(huì)直接影響聚類結(jié)果的好壞[14]。對(duì)于元素?cái)?shù)量較少的數(shù)據(jù)，一般螞蟻數(shù)量/元素?cái)?shù)量為1.5[15]。

2 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

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

圖2 西雅圖車站數(shù)據(jù)集D1

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

以經(jīng)緯度為（47.598 488，-122.390 785）為坐標(biāo)0 點(diǎn)，以500 m 作為比例尺，代入西雅圖的53 個(gè)車站點(diǎn)位，最終得到了一個(gè)二維數(shù)據(jù)集D1。

處理后的兩種數(shù)據(jù)集如圖1-2 所示。

圖1 UCI Iris數(shù)據(jù)集

處理后的兩種數(shù)據(jù)集特征如表1 所示。

表1 數(shù)據(jù)集特征表

經(jīng)過多次實(shí)驗(yàn)，最終選定實(shí)驗(yàn)參數(shù)如表2 所示。

表2 參數(shù)設(shè)置表

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

為了體現(xiàn)算法的提升效果，最終選定常見的采用組平均規(guī)則的層次凝聚聚類和k-means 聚類作為參考進(jìn)行對(duì)比。在設(shè)置聚類簇?cái)?shù)為2 時(shí)，運(yùn)行20 次后求平均值。對(duì)比結(jié)果如表3 所示。

表3 聚類準(zhǔn)確率

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

該文中，實(shí)際只聚集成兩個(gè)簇意味著只設(shè)置兩個(gè)維修點(diǎn)，兩個(gè)維修點(diǎn)并不一定能滿足實(shí)際需求，因此追加對(duì)數(shù)據(jù)集D1聚類成三類以及四類的實(shí)驗(yàn)，此時(shí)使用簇中元素到聚類中心的平均距離代替聚類準(zhǔn)確率來判斷聚類結(jié)果的好壞，公式如下：

運(yùn)行20 次后求平均值，實(shí)驗(yàn)結(jié)果如表4 所示。

從表4 中可以知，對(duì)于處理過的Iris 數(shù)據(jù)集而言，聚集成四個(gè)簇時(shí)，k-means 算法略優(yōu)于該文算法，聚集成三個(gè)簇時(shí)則相反，這是因?yàn)樵撐乃惴o法對(duì)Iris 數(shù)據(jù)集的右上角的三個(gè)噪聲點(diǎn)進(jìn)行處理所造成的；但在西雅圖車站數(shù)據(jù)集上，該文算法相比AHC和k-means，各個(gè)元素到聚類中心的距離減少了10%。

表4 聚類效果

4 結(jié)論

該文提出了一個(gè)基于蟻群優(yōu)化和層次凝聚聚類的共享單車維修點(diǎn)規(guī)劃模型，通過使用信息素機(jī)制和概率狀態(tài)轉(zhuǎn)移機(jī)制對(duì)聚集點(diǎn)進(jìn)行聚類操作，聚類中心即為維修點(diǎn)的位置。

根據(jù)實(shí)驗(yàn)結(jié)果顯示，該文方法在所有情況下優(yōu)于AHC 算法，在絕大多數(shù)情況下優(yōu)于k-means 算法，使用該方法規(guī)劃的維修點(diǎn)位置到各個(gè)點(diǎn)位的平均距離減少了10%。