改進(jìn)主成分和K-均值聚類算法的行駛工況

張玉西， 蘇小會， 高廣棵， 尚 煜

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

汽車行駛工況也稱運(yùn)轉(zhuǎn)周期或行駛循環(huán)，是車輛在特定環(huán)境下行駛的速度-時間變化規(guī)律[1]。Zhao等[2]采用模糊C均值(fuzzyC-means，F(xiàn)CM)聚類算法對駕駛段進(jìn)行聚類，根據(jù)三類駕駛段的時間比和特征參數(shù)的相關(guān)系數(shù)，構(gòu)建具有代表性的電動汽車城市行駛周期。目前行駛工況合成中采用較多的是K-均值聚類，而K-均值聚類常常存在對初始聚類中心依賴大和孤立點(diǎn)、噪聲數(shù)據(jù)敏感等問題。馬福民等[3]提出一種局部密度自適應(yīng)度量的方法來描述簇內(nèi)數(shù)據(jù)對象的空間特征，給出了一種基于局部密度自適應(yīng)度量的粗糙K-均值聚類算法。袁逸銘等[4]提出一種基于密度峰值的改進(jìn)K-均值文本聚類算法，選取密度峰值點(diǎn)和初始聚類中心點(diǎn)，在一定程度上避免了K-means 算法隨機(jī)選取初始聚類中心點(diǎn)的缺陷。以上兩種方法雖然在一定程度上優(yōu)化了初始聚類中心，但沒有提及數(shù)據(jù)集中邊緣數(shù)據(jù)、孤立點(diǎn)的影響，包志強(qiáng)等[5]只是采用孤立點(diǎn)移除算法消除數(shù)據(jù)集中的孤立點(diǎn)，但對數(shù)據(jù)集聚類方面依舊是采用傳統(tǒng)的K-means聚類。

通過上述分析，提出一種基于密度的改進(jìn)K-均值聚類，該算法的關(guān)鍵是利用數(shù)據(jù)對象的密度度量值來確定初始聚類中心，消除對初始中心點(diǎn)噪聲點(diǎn)的影響，然后，結(jié)合改進(jìn)主成分分析，構(gòu)建一種組合優(yōu)化的方法來合成行駛工況。

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

采集的數(shù)據(jù)是某城市輕型汽車實(shí)際道路行駛狀況(采樣頻率1 Hz)，數(shù)據(jù)信息有時間、全球定位系統(tǒng)(GPS)測速、經(jīng)緯度、瞬時油耗等。在測試過程中，由于駕駛環(huán)境、干擾信號和建筑物的影響，傳感器收集的原始數(shù)據(jù)經(jīng)常出現(xiàn)失真、噪聲和干擾，原始數(shù)據(jù)中包含著大量的噪聲[6]。因此，數(shù)據(jù)處理的第一步是對原始數(shù)據(jù)進(jìn)行預(yù)處理，利用小波分解和重構(gòu)對原始數(shù)據(jù)進(jìn)行預(yù)處理[2]。基本思路是在保留原始信號小波系數(shù)的同時，去除各頻段與噪聲對應(yīng)的小波系數(shù)，然后對處理后的系數(shù)進(jìn)行小波重構(gòu)，得到純信號。

假設(shè)一個含噪聲信號可以描述為

S(x)=f(x)+n1(x)n2(x)

(1)

式(1)中：S(x)為退化信號；f(x)為原始信號；n1(x)為加性噪聲；n2(x)為乘性噪聲。

基于小波分解和重構(gòu)的去噪過程具體描述如下:

步驟1通過小波分解將帶噪聲的信號f(x)分解為近似分量cj,k和詳細(xì)分量dj,k。

步驟2根據(jù)閾值δj，利用等式(2)對第j層的詳細(xì)分量dj,k進(jìn)行處理。

(2)

步驟3利用重構(gòu)算法對近似分量cj,k和詳細(xì)分量dj,k進(jìn)行重構(gòu)，獲得濾波后的信號。

原始數(shù)據(jù)和經(jīng)過小波分解和重構(gòu)預(yù)處理的數(shù)據(jù)如圖1所示。

圖1 降噪數(shù)據(jù)結(jié)果對比Fig.1 Comparison of noise reduction data results

原始數(shù)據(jù)與預(yù)處理數(shù)據(jù)的對比表明，小波分解與重構(gòu)方法具有良好的去噪效果，能有效地提高信號的信噪比。

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

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

在分析相關(guān)資料并進(jìn)行相關(guān)研究基礎(chǔ)上，定義了12個特征參數(shù)來描述運(yùn)動學(xué)片段[7]。選取了運(yùn)行時間T、行駛距離S、平均速度Va、平均行駛速度Vd、怠速時間比Ti、加速時間比Ta、減速時間比Td、巡航時間比Tc、速度標(biāo)準(zhǔn)差Vstd、平均加速度aa、加速度標(biāo)準(zhǔn)差astd、平均減速度ad12個特征參數(shù)。

汽車由一個怠速開始到下一個怠速開始前的區(qū)間被稱為運(yùn)動學(xué)片段[8]。利用Python語言進(jìn)行處理，從195 815預(yù)處理數(shù)據(jù)中分割出1 655個運(yùn)動學(xué)片段。

2.2 改進(jìn)的主成分分析

傳統(tǒng)的主成分分析方法標(biāo)準(zhǔn)化處理時在消除原始數(shù)據(jù)量綱和數(shù)量級影響的同時也把各信息之間的差異性進(jìn)行了消除[9]。針對以上情況，改進(jìn)的主成分分析方法如下：

采用指標(biāo)均值法和指標(biāo)同趨化對傳統(tǒng)主成分無量綱化的方法進(jìn)行改進(jìn)[10]。假設(shè)評估的整體中有m個對象和n個指標(biāo)，最開始的指標(biāo)可以構(gòu)成矩陣Xij=(xij)m×m。將矩陣均值化就是用原來的指標(biāo)除以所有指標(biāo)的平均值Yij：

(3)

其中：

(4)

j=1,2,…,n

(5)

式(5)中：y′ij為yij同趨化處理后的數(shù)列，這樣的變動不會改變原來指標(biāo)的分布。改進(jìn)的主成分可以表征較多特征參數(shù)信息的同時行駛工況實(shí)現(xiàn)降維。

從圖2可以看出，各主成分的變化曲線存在明顯的拐點(diǎn)，觀察得出選擇前3個主成分，其中M代表主成分。由圖3可知，前3個主成分累積貢獻(xiàn)率已達(dá)到了85%，基本代表了片段12個特征參數(shù)的所有信息，可進(jìn)行聚類分析，其中第1主成分包含的信息45%，因此達(dá)到了較少主成分表征更多信息的要求。

參數(shù)主成分載荷系數(shù)的絕對值越大，則表明某參數(shù)與某主成分的相關(guān)系數(shù)越高，貢獻(xiàn)因子越大。根據(jù)表1可知，第1主成分特征值有行駛距離、片段持續(xù)時間、巡航時間比、平均行駛速度；第2主成分特征值有平均速度；第3主成分特征值有怠速時間比。前3個主成分可以看出，樣本的12個特征參數(shù)矩陣縮減成能代表大多數(shù)樣本信息的6個特征參數(shù)矩陣。

圖2 碎石圖Fig.2 Lithotripsy

圖3 貢獻(xiàn)率和累積貢獻(xiàn)率Fig.3 Contribution rate and cumulative contribution rate

表1 主成分載荷矩陣

2.3 改進(jìn)的K-均值聚類分析

初始聚類中心的選擇對K-均值聚類結(jié)果有很大影響，具有隨機(jī)性，且易受到噪聲點(diǎn)、孤立點(diǎn)的影響，因此，隨機(jī)選取的聚類中心可能是孤立點(diǎn)或離群點(diǎn)，導(dǎo)致聚類結(jié)果達(dá)不到最優(yōu)[11]。在通常的優(yōu)化方法中，為使初始聚類中心優(yōu)于傳統(tǒng)算法中隨機(jī)選取聚類中心的方法，一般選擇相互距離最遠(yuǎn)或密度最大的k個數(shù)據(jù)對象作為初始聚類中心，但如果數(shù)據(jù)集中存在噪聲數(shù)據(jù)，距離優(yōu)化法很可能將噪聲數(shù)據(jù)作為初始聚類中心。而密度法是選擇密度最大的k個數(shù)據(jù)對象作為初始聚類中心，該方法可以去除數(shù)據(jù)的孤立點(diǎn)，但不適用于非凸數(shù)據(jù)集。提出一種距離優(yōu)化法和密度法結(jié)合確定較優(yōu)初始聚類中心的方法，并構(gòu)建一種數(shù)據(jù)集密度度量方法。

2.3.1 相關(guān)定義

(1)空間中兩點(diǎn)間的歐氏距離為

d(xi,xj)=

(6)

式(6)中：xi，xj為兩個m維的數(shù)據(jù)點(diǎn)。

(2)數(shù)據(jù)對象之間的平均距離為

(7)

(3)已知數(shù)據(jù)集D={x1,x2,…,xn}，數(shù)據(jù)點(diǎn)xi的密度度量函數(shù)為

(8)

數(shù)據(jù)點(diǎn)xi的密度參數(shù)實(shí)際上是一個圓心為xi，半徑為MeanDist的圓內(nèi)數(shù)據(jù)對象。

(4)數(shù)據(jù)集的平均密度度量函數(shù)定義為

(9)

式(9)中：n為數(shù)據(jù)集D中數(shù)據(jù)對象的數(shù)量。

(5)對于數(shù)據(jù)集D中的數(shù)據(jù)點(diǎn)xi，如果

Dens(xi)<α×MeanDens(D)

(10)

點(diǎn)xi被稱為孤立點(diǎn)，其中0<α<1。

(6)數(shù)據(jù)對象xi和數(shù)據(jù)集C之間的距離是距離數(shù)據(jù)集C中所有數(shù)據(jù)點(diǎn)最近的距離。

d(xi,C)=min[d(xi,xj),xj∈C]

(11)

2.3.2 算法思想

改進(jìn)K-均值聚類的思想如下：首先計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)對象的密度度量函數(shù)，確定為孤立點(diǎn)，并刪除孤立點(diǎn)數(shù)據(jù)，得到一個高密度度量值的數(shù)據(jù)集。然后，選擇數(shù)據(jù)集中密度度量值最高的數(shù)據(jù)點(diǎn)作為第1個初始聚類中心，之后從其余高密度數(shù)據(jù)集中選擇一個距離第1個初始集群中心最遠(yuǎn)數(shù)據(jù)點(diǎn)作為第2個初始集群中心，以此類推，直到找到k個初始聚類中心。在此k個初始聚類中心的基礎(chǔ)上，采用傳統(tǒng)的k-means算法進(jìn)行聚類。算法描述如下。輸入：包含n數(shù)據(jù)對象的樣本數(shù)據(jù)集D={d1,d2,…,dn}。

輸出：最好的k值和聚類結(jié)果。

步驟1分別用d(xi,xj)和MeanDist計(jì)算數(shù)據(jù)集D中任意兩個數(shù)據(jù)對象之間的距離和平均距離。

步驟2利用Dens(xi)和MeanDens(D)計(jì)算數(shù)據(jù)集D中所有數(shù)據(jù)對象的密度度量函數(shù)和數(shù)據(jù)集D的平均密度度量函數(shù)。

步驟3根據(jù)式(10)，確定孤立的數(shù)據(jù)對象，將其從集合D中刪除，得到具有高密度參數(shù)的集合A。

圖5 K-均值聚類結(jié)果Fig.5 K-means clustering results

步驟4從集合A中選擇一個參數(shù)密度最高的數(shù)據(jù)對象作為第1個初始聚類中心，將其添加到集合B中，并從集合A中移除。

步驟5從集合A中，選擇距離集合B最遠(yuǎn)的數(shù)據(jù)對象作為下一個初始集群中心，將其添加到集合B中，并從集合A中移除。

步驟6重復(fù)步驟5，直到集合B中的數(shù)據(jù)對象數(shù)量為k。

步驟7基于k聚類中心，采用傳統(tǒng)的K-均值進(jìn)行聚類。

2.3.3 結(jié)果分析

CH(Calinski-Harabasz)作為評價指標(biāo)，來判定聚類前的K值最優(yōu)，它是基于全部樣本的類內(nèi)離差矩陣和類間離差矩陣的測度，其越大代表類自身越緊密，類與類之間越分散，此時的聚類結(jié)果相對更好[12]。指標(biāo)定義為

(12)

式(12)中：n為聚類數(shù)；k為當(dāng)前得類，trB(k)為類間離差矩陣的跡；trW(k)為類內(nèi)離差矩陣的跡。

為了確定合適的聚類數(shù)，采用CH作為評價指標(biāo)，在不同聚類狀態(tài)下CH的處理結(jié)果如圖4所示，可觀察到CH最大時聚成了3類。同時，聚類結(jié)果如圖5所示，當(dāng)聚成2、3、4類時，可觀察到聚成3類效果最佳。

文獻(xiàn)[13]選擇平均速度和怠速時間比這兩種常

圖4 聚類數(shù)與CH指標(biāo)關(guān)系Fig.4 Relationship between cluster number and CH index

見的工況特征進(jìn)行聚類分析。選取貢獻(xiàn)因子較高的巡航時間比和平均速度特征參數(shù)進(jìn)行分析，圖6所示原片段點(diǎn)呈現(xiàn)散點(diǎn)分布，紅色圈內(nèi)為孤立點(diǎn)和離群點(diǎn)。

將各運(yùn)動學(xué)片段聚成3類，如圖7所示，第1、2、3類聚類中心分別為(14，38)、(52，45)、(86，54)，考慮一般市區(qū)交通行駛狀況:第1類是比較擁擠的市區(qū)，平均速度和巡航時間比較低，較為頻繁地啟停； 第2類是比較暢通的城市郊區(qū)，平均速度和巡航時間比較高，啟停次數(shù)較少；第3類是暢通的高速片段，平均速度和巡航時間比高，啟停次數(shù)少。

圖6 二維特征空間中片段的散點(diǎn)圖Fig.6 Scatter plot of segments in two-dimensional feature space

圖7 二維特征空間中片段的聚類結(jié)果Fig.7 Clustering results of fragments in two-dimensional feature space

3 行駛工況構(gòu)建分析

3.1 工況構(gòu)建

根據(jù)各類時間片段總時間占所有數(shù)據(jù)集汽車行駛工況的比例，可以計(jì)算出各片段在最終構(gòu)建的工況中所取的時間。圖8所示為按一般典型行駛工況的時間1 200 s構(gòu)建。

從圖9可以看出，工況點(diǎn)大多集中在中低速范圍，而且加速度的分布比較合理，能呈現(xiàn)實(shí)際汽車行駛加速、減速的情況。

由圖10可以看出，加速度主要分布在速度為0～40 km/h和80 km/h的范圍內(nèi)。在低速、高加速度期間，瞬時油耗有明顯凸起，可能是因?yàn)轳{駛員操作不規(guī)范所引起。

圖8 合成行駛工況Fig.8 Synthetic driving conditions

圖9 時間與加速度關(guān)系圖Fig.9 Time and acceleration diagram

圖10 速度與加速度瞬時油耗散點(diǎn)圖Fig.10 Speed and acceleration instantaneous fuel dissipation point diagram

3.2 工況驗(yàn)證及油耗分析

分布差異值SAFDdiff(speed-acceleration frequency distribution)越小，構(gòu)成的工況與實(shí)際數(shù)據(jù)間的共性越高[14]。

(13)

式(13)中：SAFDcycle為一個周期的SAFD；SAFDdata為所有數(shù)據(jù)的SAFD。

速度-加速度聯(lián)合分布是把速度值和加速度值各自按照相等的間隔分隔開，進(jìn)一步統(tǒng)計(jì)不同區(qū)間內(nèi)的工況數(shù)據(jù)的比例大小[15]。如圖11、表2所示，原始數(shù)據(jù)與構(gòu)建的行駛工況速度-加速度聯(lián)合差異分布在±1.2%范圍內(nèi)，且計(jì)算的分布差異值SAFDdiff=1.17%，因此構(gòu)建的行駛工況滿足輕型汽車的行駛特征，具有較強(qiáng)的適用性。

表2 本文方法與傳統(tǒng)K-均值算法結(jié)果對比

圖11 原數(shù)據(jù)與合成工況的SAFD差異值Fig.11 SAFD difference between experimental data and synthetic conditions

4 結(jié)論

采用指標(biāo)均值法和指標(biāo)同趨化，在不改變各變量差異信息情況下對傳統(tǒng)主成分分析法無量綱化的方法進(jìn)行改進(jìn)。K-均值聚類對初始聚類中心有很大的依賴性，不同的初始聚類中心會導(dǎo)致聚類結(jié)果不穩(wěn)定、不準(zhǔn)確。通過優(yōu)化初始聚類中心，提出了一種改進(jìn)的K-均值聚類算法，該算法的關(guān)鍵是利用數(shù)據(jù)對象的密度度量值來確定初始聚類中心，消除對初始中心點(diǎn)噪聲點(diǎn)的影響，從而保證了初始聚類中心的合理性。構(gòu)建一種改進(jìn)主成分和改進(jìn)K-均組合的優(yōu)化方法，合成汽車行駛工況。結(jié)果表明，原始數(shù)據(jù)與構(gòu)建行駛工況的速度-加速度聯(lián)合分布差異值為1.17%?？梢?，所提方法合成的行駛工況更加接近實(shí)際交通路況。