基于改進K-均值聚類算法的合肥市電動客車行駛工況構建＊

孫駿 方濤 張炳力 李傲伽 朱鶴

（1.合肥工業大學，合肥 230009；2.安徽安凱汽車股份有限公司，合肥 230051）

主題詞：合肥市 電動客車 行駛工況 改進K-均值聚類

1 前言

行駛工況是車輛能耗和續航測試的基礎，是研究汽車參數匹配和能量管理策略的依據，具備典型的時域性和地域性特征。近幾年，合肥市汽車保有量大幅度增長，交通情況顯著變化。另外，電動公交車占營運客車的比例越來越大，運行覆蓋的線路也越來越廣。2011年，唐邦強等建立的合肥市純電動公交車行駛工況（Hefei Pure Electric Bus Driver Cycle，HF-PEB-DC）[1]僅選取了18 路公交車作為研究對象，難以較好地反映當下合肥市電動客車的運行情況，需要重新構建合肥市電動公交車的行駛工況。

國內外學者采用K-均值（K-Means）聚類算法進行了區域性汽車行駛工況的研究[2-5]。伊朗科技大學的A.Fotouhi 等人采用K-Means 聚類算法構建了德黑蘭市汽車行駛工況[2]；愛爾蘭都柏林大學的JohnBrady等人基于K-Means 聚類算法構建了愛爾蘭地區電動汽車的行駛工況[3]。曹正策等人采用K-Means 聚類法完成了武漢市電驅動機械式自動變速器（Electric-drive Mechanical Transmission，EMT）純電動公交車行駛工況的構建[4]；李耀華等人采用K-Means 聚類算法完成了西安市純電動城市客車行駛工況（XiBUS）的構建[5]。傳統的K-Means算法需要人工指定K值（分類數）和初始聚類中心點（中心的一般采用隨機數），如果選擇不當，往往會導致聚類的結果陷入局部的最優。另外，文獻[1]、文獻[4]、文獻[5]關于電動公交車的行駛工況構建只選取了1條路線，存在一定的局限性。

本文選取合肥市4 條典型線路的12 輛電動公交車進行連續一周的數據采集，基于短行程分析法分割有效數據，采用主成分分析法和改進的K-Means算法進行分析，依據類中心距離選取類代表短行程，構建出合肥市電動客車的行駛工況。最后，將聚類的結果與其他線路采集的數據及國內外典型行駛工況進行對比。

2 準備工作

本文采用圖1 所示的流程進行合肥市電動客車行駛工況的構建。

圖1 車輛行駛工況構建流程

2.1 確定采集路線

截止到2018年2月，合肥市城市客車的行駛線路達236條，營運線路總里程達3 787.3 km，為了減少處理的數據量，參考相關工況建立過程，選取3～4 條典型公交線路進行工況的構建[6-8]。

篩選的原則是在盡可能覆蓋所有典型路段的基礎上選取分布最廣、客流量最大的線路，涵蓋擁堵的市中心、火車站，以及交通順暢的郊區、城市高架、快速路等。

參照合肥市公交線路運行圖，綜合考慮線路的運行時間和間隔、組成特征和分布情況，選取了以下4 條公交線路：

a.B1 路，合肥市最早開通的快速公交線路，南北走向，經過市中心，客流量大。

b.18路，合肥市最早開始純電動客車示范運行的線路，途徑政務區，部分路段為快速路、支路和次干道，是合肥市西北部地區的典型公交線路。

c.137 路，路線相對較為偏僻，但也途徑火車站、合肥工業大學屯溪路校區，為合肥市東北部地區從市中心到郊區的典型公交線路。

d.226路，合肥市最擁擠的路線之一，從火車站出發，途徑市中心、中國科學技術大學抵達大學城，該線路高校學生較多，出行需求很高，另外，明珠廣場站是合肥市西部的交通樞紐，客流量極大。

上述線路的基本情況如表1所示。

表1 選中線路的基本情況

2.2 數據采集裝置

現有的公交車已裝有車輛數據采集裝置并部署了云端的實時監控和儲存系統，每隔10 s輸出一次狀態信息，因其采集頻率過低，必須添加額外的傳感器獲取所需數據。

本文通過布置高精度差分GPS設備的方法獲取汽車行駛速度和定位信息。選用北斗星通公司的實時動態（Real-Time Kinematic，RTK）定位接收機，如圖2所示。

圖2 數據采集裝置

搭配定位基站后，該接收機每秒可以輸出5次厘米級定位信息和速度信息。考慮到數據量過大對后續的處理不利，同時參考國內外汽車行駛工況的建立過程，將GPS的輸出頻率設置為1 Hz。

3 采樣數據的處理

3.1 數據融合及清洗

采集的數據有2個數據源，分別為公交公司云端監控平臺獲取的頻率為0.1 Hz 的數據和高精度GPS 輸出的1 Hz的數據。前者包括車輛ID、車速、時間、經緯度、站點、轉向盤轉角和荷電狀態（State Of Charge，SOC）等信息，后者通過串口輸出時間、車速、經緯度、定位精度等信息。

高精度GPS 定位設備在使用過程中會出現空值輸出問題、丟星問題和靜態偏移問題。云端監控儲存的信息是從CAN總線讀取的，其來源是汽車的傳動系統，抗干擾性較GPS 設備高。因此，在兩個信息源數據讀取時，以云端監控獲取的數據為基礎，按時間順序將GPS設備輸出的速度和加速度信息以插值的形式插入云端監控儲存的數據完成數據融合。

考慮到數據采集和傳輸過程中可能的異常，參考國內的相關文獻和國外全球統一輕型車測試程序（World Light Vehicle Test Procedure，WLTP）對異常數據的處理方法，以加速度絕對值大于4 m/s2為標準尋找數據尖點，并根據情況對速度進行平滑或刪除[6]。若采集的數據發生缺失且缺失時長小于3 s，則保留此段行程并進行插值，否則刪去這段短行程。除異常值、缺失值外，還存在相同時間下出現2 個不同數值的情況，即“重復值”，對此，本文取重復值的均值。經數據處理，共獲得15 809 669條數據。

3.2 短行程分割及特征參數計算

如圖3 所示，汽車行駛過程中的短行程是指2 次怠速之間的運動行程[9]。經過算法分割，短行程數量為25 430個。

圖3 某典型短行程工況示意

在進行工況構建時，需要用一些特征參數描述短行程的特征，如表2所示。

表3 定義了11 個用于評價聚類結果的統計學特征參數。

表2 短行程描述性特征參數

表3 短行程統計特征參數

3.3 主成分分析及降維

在經過原始數據的融合、清洗、短行程劃分、特征參數計算并按預設規則篩選后得到24 595 條滿足要求的19維數據。由于此時的數據量較大且維度較高，直接聚類會出現計算量大、聚類效果差等問題。實際上，在19個特征參數中，部分特征參數間存在一定的關聯性，如平均加速度和加速時間、減速時間決定了平均減速度。因此須對原數據進行一定程度的處理，再進行聚類。

基于主成分分析的數據降維的具體實現過程為：a.對數據進行標準化并計算數據協方差矩陣，標準化后的數據矩陣記作Z。

b.計算協方差矩陣的特征向量和特征值，降序排序后的特征值記為λ1、λ2、……、λm，其中m為矩陣Z的維度，排序后的特征值記為V。

c.通過特征值計算主成分中各向量的貢獻率p1、p2、……、pm和累計貢獻率。主成分貢獻率是指該主成分的方差在所有主成分的總方差中的比值。第i個向量的貢獻率pi為：

因前文已將特征值排序，這里只需要將計算出的貢獻率進行累加即可計算出前i個主成分的累計貢獻率Pi：

d.根據定義的累計貢獻率限值選擇主成分。參考相關文獻[4，6，10-11]，一般累計貢獻率取80%～90%，這里選擇累計貢獻率大于80%的k個主成分：

e.計算主成分得分。取V中的前k行向量組成矩陣Vk，由Z×Vk得到主成分得分。

f.保存降維結果和對應的短行程特征值。

前8 個主成分的貢獻率及累計貢獻率如圖4 所示，由圖4可知，主成分1～4的累計貢獻率為80.66%，因此，可將19維數據降至4維。

圖4 部分特征值主成分貢獻率及累計貢獻率

3.4 基于改進K-Means算法的數據聚類

K-Means 算法受K值和初始聚類中心點的影響極大，合適的聚類簇數和聚類中心點的選擇十分困難[10]。為了減少初始聚類中心點的影響，引入二分K-Means算法。二分K-Means 算法是對K-Means 算法的優化，其基本思想是將原始簇一分為二，通過引入評價函數平方誤差和（Sum of Squared Error，SSE）來評估聚類結果和指導下一步的二分，直到使得聚類的簇數等于設定的初始值[12]。平方誤差和的計算公式為：

式中，S為平方誤差和；p為簇的個數；q為樣本點的個數；u（j）為第j簇的中心向量；w（i，j）為第i個樣本點與第j個簇中心的歐氏距離。

這種二分K-Means 算法改進了原有的由程序隨機或者由用戶指定初始中心點的局限，通過對數據的循環二分聚類選取中心點，使得各中心點的特征不同，避免初始聚類中心點的“集聚”，減小局部最優的概率。當然，K值依舊需要用戶自行確定。

實際上K值的選取具有典型的肘部特征，隨著K值的增加，平方誤差和的下降速度會在某個臨界點后趨于平緩，該臨界點往往被認為是“理想的K值”。

本文基于“肘部法則”對二分K-Means 算法進行改進，定義平方誤差和的下降比例dSSE為：

隨著n的增大，dSSE小于預設值，即認為此時的n為最優的K值。為了避免簇數超出設定的允許值M，如n≤M-1時均未找到期望的臨界點，則取M作為最優的K值，此時算法的效率最低。

基于“肘部法則”改進K-Means 的輸入為不帶分類標號的數據集X={x1，x1，…，xn}、最大聚類簇數M、預設的最小下降比DSSE，輸出為“最優”K值、分類的標號、每一類的中心點、類內總距離，其流程為：

a.初始化。將目標簇數n初始化為2，運行K-Means 算法隨機選擇中心點，將數據分為2 個簇，并分別計算簇的平方誤差和。

b.將聚類的目標簇數自加1，選擇滿足條件的可以分解的簇。選擇條件主要是綜合考慮簇的元素個數以及聚類代價即數據平方誤差和。當某簇數據點的數量大于規定的最小數量，則認為該簇可以分解。

c.考慮到此時子簇的分解實際仍基于二分均值聚類算法進行，在對要分解的子簇進行分解聚類時，重復進行多次分解，取平方誤差和最小時的分類結果作為當前分類次數的最優結果，計算并記錄dSSE（n）和當前的聚類結果。

d.若dSSE（n）＜DSSE或K=M，則認為此時的K即為“最優”K值，此時的聚類結果為最優結果，則跳過步驟e，執行步驟f，否則執行步驟e。

e.若在近幾次的二分聚類中dSSE（K）突然減小，則認為開始減緩的類簇數（K-1）和對應的聚類結果是最優的。否則，不斷重復步驟b～步驟d。

f.輸出“最優”K值、分類的標號，以及每一類的中心點和類內總距離。

基于上述流程，在Python平臺編寫改進K-Means算法，設M=10、DSSE=30%，運行程序。

3.5 聚類結果分析

表4 給出了基于改進K-Means 聚類后各簇的特征值。第1 類、第2 類的停車比例較大且平均速度較小、短行程時間較短，比較符合十分擁堵和一般擁堵的工況。第3 類、第4 類的停車比例較小且平均速度較快、短行程時間較長，比較符合通行正常和通行暢通的工況。由表4可知，合肥市的交通狀況61%的時間較為暢通，一天當中有20%的時間處于擁堵狀態，這比較符合上、下班高峰期（8：00～9：30、5：00～6：30）占公交車運行時間（一般6：00～22：00）的比例特征。

為了對比改進K-Means 和K-Means 算法的聚類結果，基于K-Means 算法，將聚類的目標簇數分別設置為2、3、……、10，將聚類后的平方誤差和與基于改進K-Means算法結果進行對比，考慮到K-Means算法的隨機性，將K-Means算法運行10次，以最小的平方誤差和作為當前K值的結果。如圖5所示，改進K-Means算法實現了自動識別基于“肘部法則”的最優K值，分類結果更理想。

表4 基于改進K-Means算法的聚類結果

圖5 2種聚類算法的平方誤差和

實際上，改進K-Means 算法的核心機制仍為K-Means 算法，基于二分思想，單步多次劃分取最優解，降低其隨機性，并取分割后平方誤差和降低最大的簇進行劃分使得算法在增加分類數的同時最大程度降低平方誤差和。這些改進使得K-Means 算法的尋優不是通過漫無目的的多次運行，而是在有限次數的子空間內使數據沿著平方誤差和下降速度“最快”的方向進行聚類。這使得改進的K-Means 和原有的K-Means 算法相比，雖然單次的運行時間長，但從聚類結果和運行機制來看，改進K-Means 比K-Means 效果更好。

4 城市客車行駛工況構建及對比

4.1 工況構建

依據類中心距離的大小選取各簇代表運動片段，從而構建車輛的行駛工況。參考相關工況，以及臺架試驗要求，將工況總時間設為1 500 s[4-5，13]。通過分類后各簇的樣本數占總樣本數的時間比例來確定各簇中抽取的片段數量，將選出的片段進行拼接，即可完成工況的構建。最終選取18條代表工況，循環工況時長為1 474 s，形成的合肥市電動公交車行駛循環（Hefei Electric Bus Cycle，HFEB）如圖6所示。

圖6 合肥市電動客車行駛循環

4.2 工況驗證

為了驗證本文建立的行駛工況的代表性，隨機抽取了合肥市30 路、902 路公交線路進行數據采集，將采集到的數據按前面的步驟進行處理，獲得其短行程的特征值，將抽中的樣本與用于構建工況的4條公交線路總樣本、自建行駛工況及文獻[1]建立的早期純電動公交車行駛工況（HF-PEB-DC）的特征值進行對比。受篇幅所限，這里只比較統計特征值，結果如圖7、圖8所示。

圖7 怠速、勻速、加速、減速工況分布情況對比

由圖7、圖8 可知，自建工況與30 路、902 路和原始數據均值間的誤差較小，而HF-PEB-DC 在速度的分布比例上與當前的汽車行駛數據相比存在較大差異。因此，本文建立的行駛工況更能反映合肥市當前的道路交通情況。

圖8 速度分布情況對比

4.3 典型工況對比

如表5 所示，將自建的HFEB 與紐約城市公交循環（The New York Bus cycle，NYBus）[14]、曼哈頓巴士循環（Manhattan Bus Cycle）[14]、中國城市客車行駛工況（CHTC-B）[15]、文獻[4]建立的武漢EMT Bus Cycle、文獻[5]建立的XiBUS、合肥公交車行駛工況[7]以及文獻[1]建立的HF-PEB-DC 工況中的特征參數進行對比。

通過對比可知：

a.HFEB 與NYBus 工 況、Manhattan Bus Cycle 工況在平均速度、駐車情況、加速情況方面都存在較大的差異。

b.HFEB 工況與HF-PEB-DC 相比，最大速度和平均速度較低，表明合肥市整體交通運行情況較2011年差。這反映了城市工況時域性的特征，整體趨勢符合合肥市近年來汽車保有量大幅增加、交通擁堵程度加深的趨勢。同時，HFEB工況與HF-PEB-DC相比最大加、減速度增長，這說明近年來電動公交車的加速度性能較2011年的純電動公交車好。

c.HFEB 工況與XiBUS 和武漢EMT Bus Cycle 在加速度、減速度、時間比例上差異較大，體現了城市工況地域性的特征。

表5 自建HFEB和國內外典型工況的對比

5 結束語

本文以合肥市4 條典型線路12 輛公交車連續一周的運行數據作為研究對象，通過數據的融合、清洗與分割得到25 430 個短行程片段，基于主成分分析和改進K-Means算法將數據聚類成4類，依據類中心距選取各簇的代表工況，構建了合肥市電動客車的行駛工況。

本文提出的基于“肘部法則”和二分K-Means 算法的改進K-Means 算法解決了需用戶指定K值和聚類結果隨機的問題，算法的速度較慢，但其構造出的車輛行駛工況比基于傳統K-Means 算法的精度更高。本文構建的工況與國內外的工況存在顯著差異，驗證了工況的時域性和地域性特征。