改進(jìn)K-means聚類算法行駛工況及油耗研究*

蘇小會(huì)，張玉西，徐淑萍，尚 煜

(西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710021)

1 引言

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

因此，本文提出一種改進(jìn)K-means聚類優(yōu)化算法，引入最大最小距離和加權(quán)歐氏距離，依據(jù)貢獻(xiàn)因子對(duì)聚類特征值增加權(quán)重。實(shí)驗(yàn)結(jié)果表明本文算法聚類效果穩(wěn)定、時(shí)耗低，所構(gòu)建的行駛工況適用性強(qiáng)，滿足交通路況的特征。

2 行駛工況數(shù)據(jù)解析

2.1 數(shù)據(jù)預(yù)處理

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

2.2 特征參數(shù)提取及運(yùn)動(dòng)學(xué)片段劃分

汽車由一個(gè)怠速開(kāi)始到下一個(gè)怠速開(kāi)始前的區(qū)間被稱為運(yùn)動(dòng)學(xué)片段[10]。在分析相關(guān)資料并進(jìn)行相關(guān)研究的基礎(chǔ)上，本文定義了12個(gè)特征參數(shù)來(lái)描述運(yùn)動(dòng)學(xué)片段[11],即片段持續(xù)時(shí)間T、行駛距離S、平均速度Va、平均行駛速度Vd、怠速時(shí)間比Ti、加速時(shí)間比Ta、減速時(shí)間比Td、巡航時(shí)間比Tc、速度標(biāo)準(zhǔn)差Vstd、平均加速度aa、加速度平均標(biāo)準(zhǔn)差astd和平均減速度ad共12個(gè)特征參數(shù)。

本文利用Python開(kāi)發(fā)了相關(guān)程序，采用堆棧和循環(huán)遍歷數(shù)據(jù)進(jìn)行處理，從164 039條預(yù)處理數(shù)據(jù)中分割出2 445個(gè)運(yùn)動(dòng)學(xué)片段。

3 改進(jìn)主成分分析

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

(1)

其中，n為運(yùn)動(dòng)學(xué)片段數(shù)量，ti為第i個(gè)片段，tij為第i個(gè)片段的第j項(xiàng)特征參數(shù)，ZTij為第i個(gè)片段的第j項(xiàng)特征參數(shù)的標(biāo)準(zhǔn)化比重。

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

Figure 1 Contribution rate and cumulative contribution rate圖1 貢獻(xiàn)率與累積貢獻(xiàn)率

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

Figure 2 Gravel map圖2 碎石圖

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

Figure 3 Scatter plot of principal component analysis 圖3 主成分分析散點(diǎn)圖

4 改進(jìn)的K-means聚類優(yōu)化算法

4.1 離群點(diǎn)處理

實(shí)際測(cè)試中總會(huì)有一定的干擾，常常產(chǎn)生孤立點(diǎn)或噪聲，影響聚類效果，本節(jié)利用剩余數(shù)據(jù)點(diǎn)距離均值和的方法來(lái)消除噪聲和離群點(diǎn)的影響[14]。每一數(shù)據(jù)點(diǎn)與其他點(diǎn)的距離和為Si，距離均值和為H，當(dāng)Si>H時(shí),則把點(diǎn)i視為孤立點(diǎn)。

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

(2)

(3)

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

4.2 最大最小距離

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

最大最小距離法的基本思想：首先，在實(shí)驗(yàn)數(shù)據(jù)中隨機(jī)選取數(shù)據(jù)點(diǎn)v1作為聚類中心點(diǎn)；然后，選擇離v1最遠(yuǎn)的數(shù)據(jù)點(diǎn)v2作為聚類中心點(diǎn)；再選擇與之前中心點(diǎn)的歐氏距離最大的數(shù)據(jù)點(diǎn)作為下一個(gè)中心點(diǎn)，重復(fù)該過(guò)程依次計(jì)算剩余所需要的中心點(diǎn)。

4.3 加權(quán)歐氏距離

設(shè)有n個(gè)實(shí)驗(yàn)數(shù)據(jù)組成聚類數(shù)據(jù)集X={x1,x2,…,xn}，其中xi=[xi1,xi2,…,xid]T為d維向量，根據(jù)實(shí)驗(yàn)數(shù)據(jù)中每個(gè)分量的特征參數(shù)的影響不同，引入權(quán)值ω=[ω1,ω2,…,ωn]T∈Rn×d來(lái)區(qū)分各部分實(shí)驗(yàn)數(shù)據(jù)與聚類中心的關(guān)系。

(4)

(5)

新初始權(quán)重為：

(6)

其中，聚類精度為:

(7)

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

4.4 特征加權(quán)K-means聚類算法

(1)處理噪聲和孤立點(diǎn)，得到新的數(shù)據(jù)集，分析得到相關(guān)特征列表。

(2)用改進(jìn)的主成分分析計(jì)算每個(gè)特征的貢獻(xiàn)因子，以此獲得初始權(quán)重。

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

(8)

其中，Xi為第i個(gè)特征的貢獻(xiàn)因子。

(3)利用最大最小距離法產(chǎn)生經(jīng)過(guò)優(yōu)化的聚類中心，以此確定K個(gè)初始聚類中心。

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

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

(6)對(duì)于ω中的每個(gè)數(shù)據(jù)點(diǎn)i，執(zhí)行沒(méi)有該數(shù)據(jù)點(diǎn)時(shí)的K-means聚類，并計(jì)聚類精度Ai，若Ai

(7)歸一化權(quán)重，基于新權(quán)重執(zhí)行K-means聚類，并計(jì)算聚類精度Ainit；

若最終聚類精度Afinal>Ainit，則接受該新權(quán)重，并令A(yù)init=Afinal；否則保持舊的權(quán)重不變。

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

Figure 4 Scatter plot of edge data points of working conditions圖4 工況邊緣數(shù)據(jù)點(diǎn)散點(diǎn)圖

Figure 5 Relative distance comparison of outliers圖5 離群點(diǎn)相對(duì)距離對(duì)比

根據(jù)上述改進(jìn)主成分分析，使用貢獻(xiàn)因子和相關(guān)性較大的特征值繪制三維圖，如圖6所示，本文選用平均速度、行駛距離和巡航時(shí)間比代表聚類的每個(gè)點(diǎn)。

Figure 6 Three-dimensional scatter plot of working conditions圖6 工況三維散點(diǎn)圖

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

Figure 7 Working condition cluster analysis scatter plot圖7 工況聚類分析散點(diǎn)圖

5 行駛工況構(gòu)建與油耗分析

5.1 工況構(gòu)建與驗(yàn)證

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

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

用速度和加速度驗(yàn)證所構(gòu)建行駛工況與實(shí)驗(yàn)數(shù)據(jù)之間的差異[11]，這是相對(duì)標(biāo)準(zhǔn)的驗(yàn)證方法。 使用Matlab軟件計(jì)算所構(gòu)建汽車行駛工況數(shù)據(jù)的速度-加速度聯(lián)合分布矩陣，如圖9所示。

Figure 9 Difference between experimental data and synthetic conditions圖9 實(shí)驗(yàn)數(shù)據(jù)與合成工況的分布差異值

由圖9可見(jiàn)，實(shí)驗(yàn)數(shù)據(jù)與本文改進(jìn)聚類算法構(gòu)建行駛工況的速度-加速度聯(lián)合差異分布在±1.2%范圍內(nèi)，因此,本文構(gòu)建的行駛工況滿足輕型汽車的行駛特征，符合車輛行駛工況構(gòu)建的開(kāi)發(fā)要求，具有較強(qiáng)的實(shí)用性。

Figure 10 Running time of the four algorithms圖10 4種算法運(yùn)行時(shí)間

本文使用文獻(xiàn)[16，17]的工況構(gòu)建方法和本文方法在本文數(shù)據(jù)上進(jìn)行20次實(shí)驗(yàn)，結(jié)果如圖10所示。結(jié)果表明，本文改進(jìn)K-means聚類算法不僅可以弱化噪聲點(diǎn)對(duì)初始中心的影響，還在聚類效果穩(wěn)定的基礎(chǔ)上大大縮短了聚類時(shí)間。

表2是在Matlab上運(yùn)行的結(jié)果，本文算法聚類表現(xiàn)較好，其中平均運(yùn)行時(shí)間比傳統(tǒng)K-means聚類算法縮短了44.2%。

Table 2 Experimental results comparsion of the four algorithms表2 四種算法對(duì)比實(shí)驗(yàn)結(jié)果

5.2 油耗分析

如圖11和圖12所示，在低速、中低和高速時(shí)瞬時(shí)油耗較大，車輛轉(zhuǎn)矩波動(dòng)較高速區(qū)大，高速區(qū)瞬時(shí)油耗比較平穩(wěn)，而低速區(qū)、中速區(qū)瞬時(shí)油耗率明顯增加。從圖12可觀察到，瞬時(shí)油耗除低速時(shí)有短暫的升高現(xiàn)象，之后油耗起伏趨勢(shì)與行駛速度大致吻合。從圖13可看出，行駛工況發(fā)動(dòng)機(jī)轉(zhuǎn)速主要分布在1 500～2 500 r/min，油門(mén)踏板開(kāi)度集中在0.12～0.18，表明行駛工況為中高速狀態(tài)。

Figure 11 Relationship between vehicle driving time and instantaneous fuel consumption圖11 車輛行駛時(shí)間與瞬時(shí)油耗的關(guān)系

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

Figure 12 Relationship between vehicle speed and instantaneous fuel consumption圖12 車輛行駛速度與瞬時(shí)油耗的關(guān)系

Figure 13 Relationship between vehicle running speed and accelerator pedal opening圖13 車輛行駛轉(zhuǎn)速與油門(mén)踏板開(kāi)度的關(guān)系

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

6 結(jié)束語(yǔ)

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