改進主成分和K-均值聚類算法的行駛工況

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

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

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

通過上述分析，提出一種基于密度的改進K-均值聚類，該算法的關鍵是利用數據對象的密度度量值來確定初始聚類中心，消除對初始中心點噪聲點的影響，然后，結合改進主成分分析，構建一種組合優化的方法來合成行駛工況。

1 數據預處理

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

假設一個含噪聲信號可以描述為

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

(1)

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

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

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

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

(2)

步驟3利用重構算法對近似分量cj,k和詳細分量dj,k進行重構，獲得濾波后的信號。

原始數據和經過小波分解和重構預處理的數據如圖1所示。

圖1 降噪數據結果對比Fig.1 Comparison of noise reduction data results

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

2 行駛工況數據解析

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

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

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

2.2 改進的主成分分析

傳統的主成分分析方法標準化處理時在消除原始數據量綱和數量級影響的同時也把各信息之間的差異性進行了消除[9]。針對以上情況，改進的主成分分析方法如下：

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

(3)

其中：

(4)

j=1,2,…,n

(5)

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

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

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

圖2 碎石圖Fig.2 Lithotripsy

圖3 貢獻率和累積貢獻率Fig.3 Contribution rate and cumulative contribution rate

表1 主成分載荷矩陣

2.3 改進的K-均值聚類分析

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

2.3.1 相關定義

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

d(xi,xj)=

(6)

式(6)中：xi，xj為兩個m維的數據點。

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

(7)

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

(8)

數據點xi的密度參數實際上是一個圓心為xi，半徑為MeanDist的圓內數據對象。

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

(9)

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

(5)對于數據集D中的數據點xi，如果

Dens(xi)<α×MeanDens(D)

(10)

點xi被稱為孤立點，其中0<α<1。

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

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

(11)

2.3.2 算法思想

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

輸出：最好的k值和聚類結果。

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

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

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

圖5 K-均值聚類結果Fig.5 K-means clustering results

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

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

步驟6重復步驟5，直到集合B中的數據對象數量為k。

步驟7基于k聚類中心，采用傳統的K-均值進行聚類。

2.3.3 結果分析

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

(12)

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

為了確定合適的聚類數，采用CH作為評價指標，在不同聚類狀態下CH的處理結果如圖4所示，可觀察到CH最大時聚成了3類。同時，聚類結果如圖5所示，當聚成2、3、4類時，可觀察到聚成3類效果最佳。

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

圖4 聚類數與CH指標關系Fig.4 Relationship between cluster number and CH index

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

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

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

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

3 行駛工況構建分析

3.1 工況構建

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

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

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

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

圖9 時間與加速度關系圖Fig.9 Time and acceleration diagram

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

3.2 工況驗證及油耗分析

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

(13)

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

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

表2 本文方法與傳統K-均值算法結果對比

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

4 結論

采用指標均值法和指標同趨化，在不改變各變量差異信息情況下對傳統主成分分析法無量綱化的方法進行改進。K-均值聚類對初始聚類中心有很大的依賴性，不同的初始聚類中心會導致聚類結果不穩定、不準確。通過優化初始聚類中心，提出了一種改進的K-均值聚類算法，該算法的關鍵是利用數據對象的密度度量值來確定初始聚類中心，消除對初始中心點噪聲點的影響，從而保證了初始聚類中心的合理性。構建一種改進主成分和改進K-均組合的優化方法，合成汽車行駛工況。結果表明，原始數據與構建行駛工況的速度-加速度聯合分布差異值為1.17%。可見，所提方法合成的行駛工況更加接近實際交通路況。