改進K-means聚類算法行駛工況及油耗研究*

蘇小會，張玉西，徐淑萍，尚 煜

(西安工業大學計算機科學與工程學院，陜西 西安 710021)

1 引言

汽車行駛工況也稱運轉周期，是車輛在特定環境中行駛的速度-時間變化規律，主要用于評價車輛污染物排放和能耗，對新車型技術研發與交通控制風險評估等研究具有重要價值[1]。現有許多學者對其進行了研究，Nguyen等人[2]提出基于馬爾可夫鏈理論的行駛循環構建過程。丁一鋒等人[3]用主成分與聚類分析等多元統計方法構建汽車道路工況。劉應吉等人[4]利用運動學片段聯系模糊的特點使用組合主成分和模糊C均值聚類構建工況。大多數學者對行駛工況的研究主要集中在K-means聚類初始中心的選擇上和單一地改進K-means聚類算法，缺乏對主成分分析和聚類組合優化以及執行算法時耗的研究。若要達到理想的聚類效果和時耗，還是要集中在K-means聚類的改進上，張銳等人[5]為了彌補傳統K-means算法聚類效果嚴重依賴于初始聚類中心這一不足，提出了OICC(Optimize Initial Cluster Centers)K-means算法。張琳等人[6]采用密度的思想克服傳統初始中心比較敏感的缺陷。羅軍鋒等人[7]引入信息熵和加權距離，去除孤立點。張琰[8]提出一種基于密度加權的粗糙K-means聚類改進算法，不僅提高了聚類準確率，減少了迭代次數，而且還弱化了聚類時噪聲數據和離群點對結果的干擾。但是，該算法是在犧牲效率代價的前提下，提高了聚類準確率，大多數的時耗用在運算數據對象的密度上，時間復雜度過高。

因此，本文提出一種改進K-means聚類優化算法，引入最大最小距離和加權歐氏距離，依據貢獻因子對聚類特征值增加權重。實驗結果表明本文算法聚類效果穩定、時耗低，所構建的行駛工況適用性強，滿足交通路況的特征。

2 行駛工況數據解析

2.1 數據預處理

本文采集的數據是來源于城市輕型汽車2019年9月份實際道路行駛狀況(采樣頻率1 Hz)，其中，數據信息有時間、GPS測速、經緯度和瞬時油耗等。利用擬合插值法對受到干擾不連續的數據進行插值擬合，小波分解和重構法對污染的數據進行平滑處理[9]，用Matlab預處理后的原始數據由194 511條減少至164 039條。

2.2 特征參數提取及運動學片段劃分

汽車由一個怠速開始到下一個怠速開始前的區間被稱為運動學片段[10]。在分析相關資料并進行相關研究的基礎上，本文定義了12個特征參數來描述運動學片段[11],即片段持續時間T、行駛距離S、平均速度Va、平均行駛速度Vd、怠速時間比Ti、加速時間比Ta、減速時間比Td、巡航時間比Tc、速度標準差Vstd、平均加速度aa、加速度平均標準差astd和平均減速度ad共12個特征參數。

本文利用Python開發了相關程序，采用堆棧和循環遍歷數據進行處理，從164 039條預處理數據中分割出2 445個運動學片段。

3 改進主成分分析

傳統的主成分分析利用線性技術對數據進行降維，消除數量級影響的同時也剔除了各特征因子的差異信息，而實際生活中數據間的關系常常是非線性的，采用方差貢獻率為權重的綜合評價方法不能合理解釋分析結果，甚至會出現評價結果與事實偏差較大的現象[12]。因此，本文采用文獻[13]提出的比重法，改進后的主成分不僅能夠消除量綱的噪聲，還可以在表征較多特征參數信息的同時實現降維，如式(1)所示：

(1)

其中，n為運動學片段數量，ti為第i個片段，tij為第i個片段的第j項特征參數，ZTij為第i個片段的第j項特征參數的標準化比重。

改進的主成分分析在實現降維的情況下，將求出的實驗數據與特征參數組成矩陣， 選取累積貢獻率達到80%以上的主成分進行降維和去相關。從圖1可看出，前4個主成分累計貢獻率已達82.76%，基本代表了該片段12個特征參數的所有信息。

Figure 1 Contribution rate and cumulative contribution rate圖1 貢獻率與累積貢獻率

從圖2可以看出，各主成分的特征值呈逐漸減小趨勢，且變化曲線存在明顯拐點。由圖1可知改進的主成分分析結果中第1主成分包含41.5%的信息，因此達到了用較少主成分表征更多信息的要求。

Figure 2 Gravel map圖2 碎石圖

當選取參數的主成分載荷系數的絕對值越大時，說明某參數與某主成分的相關系數越高[1]。從圖3可以直觀地看出各個特征值相關性的大小，根據表1可得第1主成分M1的特征值有行駛距離、平均減速度和平均行駛速度，從圖3可看出特征值的相關性系數分別為3.15,2.08和3.69，則M1與行駛距離和平均行駛速度的相關性較大；第2主成分M2的特征值有平均速度和巡航時間比，從圖3可看出特征值的相關性系數分別為2.75和3.84，則M2與巡航時間比的相關性較大；第3主成分M3的特征值有怠速時間比和減速時間比，從圖3可看出特征值的相關性系數分別為3.06和2.85，則M3與怠速時間比的相關性較大；第4主成分M4的特征值有片段持續時間，從圖3可看出特征值的相關性系數為2.43，則M3與片段持續時間的相關性較大。

Figure 3 Scatter plot of principal component analysis 圖3 主成分分析散點圖

4 改進的K-means聚類優化算法

4.1 離群點處理

實際測試中總會有一定的干擾，常常產生孤立點或噪聲，影響聚類效果，本節利用剩余數據點距離均值和的方法來消除噪聲和離群點的影響[14]。每一數據點與其他點的距離和為Si，距離均值和為H，當Si>H時,則把點i視為孤立點。

Table 1 Principal component loading matrix表1 主成分載荷矩陣

(2)

(3)

其中，xih和xjh分別為數據樣本xi和xj第h維的值，d為數據維度，n為樣本數量。

4.2 最大最小距離

最大最小距離法是把距離遠的實驗數據點看作聚類中心，避免了K-means聚類算法選取初始值時與聚類中心太過鄰近的情況，如果只依據距離做出判斷，初始中心點中很可能包含有離群點，從而影響聚類準確率。

最大最小距離法的基本思想：首先，在實驗數據中隨機選取數據點v1作為聚類中心點；然后，選擇離v1最遠的數據點v2作為聚類中心點；再選擇與之前中心點的歐氏距離最大的數據點作為下一個中心點，重復該過程依次計算剩余所需要的中心點。

4.3 加權歐氏距離

設有n個實驗數據組成聚類數據集X={x1,x2,…,xn}，其中xi=[xi1,xi2,…,xid]T為d維向量，根據實驗數據中每個分量的特征參數的影響不同，引入權值ω=[ω1,ω2,…,ωn]T∈Rn×d來區分各部分實驗數據與聚類中心的關系。

(4)

(5)

新初始權重為：

(6)

其中，聚類精度為:

(7)

其中，ωj=(ωj1,ωj2,…,ωjd)T為d維向量，xj表示第j個實驗數據，ci表示第i個聚類中心，xjm表示第j個實驗數據的第m個分量，cim表示第i個聚類中心的第m個分量，可以看出ω是一個能體現實驗數據整體分布特征的權值[5]。ncor為正確分類實驗數據數，n為實驗數據數。

4.4 特征加權K-means聚類算法

(1)處理噪聲和孤立點，得到新的數據集，分析得到相關特征列表。

(2)用改進的主成分分析計算每個特征的貢獻因子，以此獲得初始權重。

ω=(w1X1,…，wiXi,…,wnXn)

(8)

其中，Xi為第i個特征的貢獻因子。

(3)利用最大最小距離法產生經過優化的聚類中心，以此確定K個初始聚類中心。

(4)基于加權特征和初始聚類中心，執行K-means以獲得K個簇。

(5)計算初始聚類精度。

(6)對于ω中的每個數據點i，執行沒有該數據點時的K-means聚類，并計聚類精度Ai，若Ai

(7)歸一化權重，基于新權重執行K-means聚類，并計算聚類精度Ainit；

若最終聚類精度Afinal>Ainit，則接受該新權重，并令Ainit=Afinal；否則保持舊的權重不變。

根據本文的工況數據，使用本文改進的K-means算法進行處理，首先對邊緣數據、離群點進行檢測，并剔除異常點，如圖4所示，簇1為正常聚類的點，簇2為邊緣數據離群點。從圖5可以看出，邊緣數據大部分為離群點，可剔除。

Figure 4 Scatter plot of edge data points of working conditions圖4 工況邊緣數據點散點圖

Figure 5 Relative distance comparison of outliers圖5 離群點相對距離對比

根據上述改進主成分分析，使用貢獻因子和相關性較大的特征值繪制三維圖，如圖6所示，本文選用平均速度、行駛距離和巡航時間比代表聚類的每個點。

Figure 6 Three-dimensional scatter plot of working conditions圖6 工況三維散點圖

改進K-means聚類算法把運動學片段聚成4大類，分別由簇1、簇2、簇3和簇4表示。由圖7可知，第1類為鬧市區，汽車頻繁啟停且車速較低，平均速度、巡航時間比和行駛距離都低；第2類為生活區，較為擁堵，啟停次數較多，平均速度、巡航時間比和行駛距離都較低；第3類為郊區，路況較為通暢，啟停次數較少，平均速度、巡航時間比、行駛距離都較高；第4類為高速區，交通順暢，啟停次數少，平均速度、巡航時間比和行駛距離都高。

Figure 7 Working condition cluster analysis scatter plot圖7 工況聚類分析散點圖

5 行駛工況構建與油耗分析

5.1 工況構建與驗證

根據汽車行駛工況中各類時間片段總時間占所有片段集總時間的比例，可得出各工況在最終構建工況中所用的時間[15]。本文截取1 400 s的時間片段合成由低速片段、中速片段、中高速片段和高速片段的車輛行駛工況，如圖8所示。

Figure 8 Synthetic driving conditions圖8 合成行駛工況

用速度和加速度驗證所構建行駛工況與實驗數據之間的差異[11]，這是相對標準的驗證方法。 使用Matlab軟件計算所構建汽車行駛工況數據的速度-加速度聯合分布矩陣，如圖9所示。

Figure 9 Difference between experimental data and synthetic conditions圖9 實驗數據與合成工況的分布差異值

由圖9可見，實驗數據與本文改進聚類算法構建行駛工況的速度-加速度聯合差異分布在±1.2%范圍內，因此,本文構建的行駛工況滿足輕型汽車的行駛特征，符合車輛行駛工況構建的開發要求，具有較強的實用性。

Figure 10 Running time of the four algorithms圖10 4種算法運行時間

本文使用文獻[16，17]的工況構建方法和本文方法在本文數據上進行20次實驗，結果如圖10所示。結果表明，本文改進K-means聚類算法不僅可以弱化噪聲點對初始中心的影響，還在聚類效果穩定的基礎上大大縮短了聚類時間。

表2是在Matlab上運行的結果，本文算法聚類表現較好，其中平均運行時間比傳統K-means聚類算法縮短了44.2%。

Table 2 Experimental results comparsion of the four algorithms表2 四種算法對比實驗結果

5.2 油耗分析

如圖11和圖12所示，在低速、中低和高速時瞬時油耗較大，車輛轉矩波動較高速區大，高速區瞬時油耗比較平穩，而低速區、中速區瞬時油耗率明顯增加。從圖12可觀察到，瞬時油耗除低速時有短暫的升高現象，之后油耗起伏趨勢與行駛速度大致吻合。從圖13可看出，行駛工況發動機轉速主要分布在1 500～2 500 r/min，油門踏板開度集中在0.12～0.18，表明行駛工況為中高速狀態。

Figure 11 Relationship between vehicle driving time and instantaneous fuel consumption圖11 車輛行駛時間與瞬時油耗的關系

由圖14可觀察到，高瞬時油耗大多集中在轉速為1 000～1 500 r/min，扭矩百分比為10%～30%時，說明這部分行駛工況是由高速、中速和低速區組成。

Figure 12 Relationship between vehicle speed and instantaneous fuel consumption圖12 車輛行駛速度與瞬時油耗的關系

Figure 13 Relationship between vehicle running speed and accelerator pedal opening圖13 車輛行駛轉速與油門踏板開度的關系

Figure 14 Relationship among vehicle driving time, speed, and instantaneous fuel consumption圖14 車輛行駛時間、速度和瞬時油耗的關系

6 結束語

本文提出了一種改進的主成分和特征加權K-means聚類組合的優化算法，引入剩余點聚類均值法，剔除離群點，減少聚類時耗。最大最小距離法可優化候選初始中心，使K-means避免陷入局部最優解，從而達到良好的聚類效果。依據特征值的貢獻因子對聚類的貢獻率，獲得初始特征權重，提出一種加權歐氏距離度量。選出貢獻因子較大的巡航時間比、行駛距離和平均速度等特征值，可加大權重進行聚類分析，進而構建車輛行駛工況。本文提出的改進聚類算法仍有改進空間，可在本文算法的基礎上提出加權密度K-means聚類算法，還可以考慮在本文數據預處理部分直接剔除孤立點，減少后續聚類運行時間，也可加入更多維的特征信息。