黃 鶴，李文龍，楊 瀾，王會峰，王 飚，茹 鋒

（1. 長安大學(xué)，西安 710064；2. 西安市智慧高速公路信息融合與控制重點(diǎn)實(shí)驗(yàn)室，西安 710064）

前言

聚類分析是統(tǒng)計(jì)學(xué)習(xí)領(lǐng)域的常用方法，可以根據(jù)不同對象數(shù)據(jù)之間的內(nèi)在特征，將相似度較大的數(shù)據(jù)樣本劃分到同一簇，已經(jīng)應(yīng)用于許多領(lǐng)域，諸如車輛數(shù)據(jù)、車輛檢測、車輛軌跡等等。K-means 聚類（KMC）是使用最廣泛的聚類算法之一，具有速度快、效果好、思想簡單的特點(diǎn)。但是在實(shí)際的車型數(shù)據(jù)聚類過程中會因?yàn)槌跏键c(diǎn)選取不當(dāng)而導(dǎo)致誤差較大。K-means++、山峰聚類等在一定程度上解決了KMC 初始化方面的缺陷，但優(yōu)化路徑過于簡單，存在受異常點(diǎn)影響大、算法早熟的問題。近年來利用群智能優(yōu)化算法來尋找聚類中心，解決早熟問題成為研究熱點(diǎn)，廣受研究學(xué)者的關(guān)注。文獻(xiàn)［11］中將人工蜂群算法與KMC 雜交迭代，解決了早熟的問題，驗(yàn)證了群智能改進(jìn)KMC 的有效性，但是利用改進(jìn)蜂群算法來改進(jìn)KMC 處理高維數(shù)據(jù)集，存在能力不足和迭代速度慢的問題；文獻(xiàn)［12］中利用螢火蟲算法優(yōu)化KMC 的中心初始化問題，克服了初始聚類中心難選取和噪聲點(diǎn)的影響，但不適合處理大數(shù)據(jù)集；文獻(xiàn)［13］中設(shè)計(jì)了一種準(zhǔn)確率較高的IFOA-K-means 算法，增強(qiáng)了橫向探索能力，但忽略了縱向的挖掘能力；文獻(xiàn)［14］中將改進(jìn)飛蛾撲火算法與KMC 算法交叉迭代實(shí)現(xiàn)聚類，優(yōu)化尋優(yōu)結(jié)果，但飛蛾的更新機(jī)制使得算法的耗時較長。麻雀搜索算法（sparrow search algorithm，SSA）是2020 年 由Xue等提出的一種新的群智能優(yōu)化算法，SSA 模擬了麻雀覓食的過程，具有收斂速度快，適應(yīng)性強(qiáng)，模型易修改等特點(diǎn)，適合用于優(yōu)化聚類。因此，本文設(shè)計(jì)了一種基于擾動因子-領(lǐng)頭雀的SSA 優(yōu)化方法（DHSSA），與KMC 算法互補(bǔ)迭代，有效提高了車型數(shù)據(jù)的聚類精度和迭代速度。

1 KMC和SSA算法特點(diǎn)

1.1 KMC算法

KMC 可以按照不同類別將數(shù)據(jù)集劃分成多個子集，具體步驟如下：

（1）從個數(shù)據(jù)中隨機(jī)選取個對象作為初始聚類中心C（1≤≤）；

（2）計(jì)算每個數(shù)據(jù)到各個初始聚類中心的歐式距離，根據(jù)距離最小原則重新分類數(shù)據(jù)；

（3）計(jì)算聚類簇的各個維度平均值，得到新的中心。

重復(fù)步驟（2）和（3），直到聚類中心不再發(fā)生改變或聚類中心發(fā)生偏移的距離均小于設(shè)定閾值，輸出該數(shù)據(jù)集的聚類中心。從聚類過程可以看出，初始聚類中心選擇不當(dāng)，會陷入局部最優(yōu)。聚類中心C的計(jì)算公式如式（1）所示：

式中n為第個聚類簇樣本個數(shù)，=1，2...，，為聚類中心個數(shù)。聚類中心C與樣本數(shù)據(jù)X的歐式距離計(jì)算式如式（2）所示：

式中=1，2，…，表示數(shù)據(jù)維度。

因此，KMC 的初始化具有隨機(jī)性，每次處理車型數(shù)據(jù)聚類過程中結(jié)果相差較大，容易由于中心選擇不當(dāng)而陷入局部極值，還可能會將離群值誤作為初始中心；同時，根據(jù)均值選取中心的更新過程會導(dǎo)致KMC易受孤立點(diǎn)的影響。

1.2 SSA算法

（1）初始化

SSA中麻雀種群分為覓食發(fā)現(xiàn)者、搶食物的加入者和作為偵察的警戒者3 種。前兩者角色可以互換，而一定比例的偵察警戒者，一有危險便飛向別處。麻雀種群在維空間內(nèi)只麻雀的位置矩陣表示如下：

式中：x為維空間內(nèi)第只麻雀的位置；矩陣F表示麻雀的適應(yīng)度值。

（2）麻雀位置更新機(jī)制

更新機(jī)制主要可分為發(fā)現(xiàn)者的覓食過程、加入者的搶食過程和警戒者的檢測過程。

a. 覓食過程：迭代尋優(yōu)過程中，麻雀種群中的發(fā)現(xiàn)者負(fù)責(zé)覓食和指導(dǎo)整個種群移動，發(fā)現(xiàn)者位置更新如下：

可以看出，當(dāng)＜時，發(fā)現(xiàn)者的每一維都在縮小，這對求解測試函數(shù)非常有效，但對于大多數(shù)求解非0的實(shí)際應(yīng)用反而降低了搜索能力。

b. 搶食過程：加入者為除去發(fā)現(xiàn)者適應(yīng)度較差的一些個體，設(shè)計(jì)位置更新公式為

c. 檢測過程：在麻雀種群隨機(jī)選取20%的個體作為警戒者，則這些個體對全體的影響程度用式（8）表示。

2 擾動因子-領(lǐng)頭雀SSA優(yōu)化策略

綜合SSA 發(fā)現(xiàn)者、加入者和警戒者的更新方式可知，SSA 中的麻雀位置更新具有向原點(diǎn)收斂的趨勢，這對于求解非原點(diǎn)問題存在一定局限性，而聚類中心一般不取0 值。同時，由于SSA 的收斂方式是跳躍式的，容易陷入局部最優(yōu)。因此，尋找聚類中心前必須對SSA作進(jìn)一步改進(jìn)。

2.1 自適應(yīng)領(lǐng)頭雀引導(dǎo)

由更新式（5）可知，發(fā)現(xiàn)者的位置更新是在父代的基礎(chǔ)上尋優(yōu)，跟隨父代更新會導(dǎo)致尋優(yōu)速度減慢，增加聚類迭代時間。而通過作者的研究，自然界中的麻雀群在覓食中通常都會由一個最強(qiáng)壯、基因最優(yōu)秀的個體充當(dāng)領(lǐng)頭雀。鑒于此，設(shè)計(jì)了一種自適應(yīng)領(lǐng)頭雀引導(dǎo)策略來完善SSA 算法，使得迭代更新不僅受父代的影響，還受到領(lǐng)頭雀的影響。加入領(lǐng)頭雀引導(dǎo)在前期會不利于種群全局探索能力的提升。為同時增加算法的前期全局探索和后期局部尋優(yōu)能力，在上述最優(yōu)個體（領(lǐng)頭雀）引導(dǎo)策略的基礎(chǔ)上添加自適應(yīng)權(quán)重，這里新的發(fā)現(xiàn)者更新公式修改為

式中和分別為最大和最小值，取1 和0.01。系數(shù)隨著迭代次數(shù)的增加變化曲線如圖1所示。

圖1 ω系數(shù)變化曲線圖

隨的變化規(guī)律在前中期設(shè)計(jì)為緩慢減小，使得發(fā)現(xiàn)者的更新受父代的影響較大，降低算法早熟的可能性；而后期減小迅速，受領(lǐng)頭雀的影響較大，由此提高算法精度，加快聚類迭代的完成。

2.2 擾動因子

麻雀發(fā)現(xiàn)者的位置更新存在收斂于0 的趨勢，而加入者和警戒者的收斂趨于最優(yōu)解，這導(dǎo)致了SSA 尋找聚類中心時易收斂于0，但是聚類中心的值一般不為0。針對這一問題，一般采用變異操作加強(qiáng)全局搜索能力，最常用的是高斯和柯西算子。而在SSA 尋找聚類中心的過程中為增加種群多樣性，采用分布擾動因子對麻雀個體變異，根據(jù)參數(shù)自由度的大小表現(xiàn)不同，在自由度較小時表現(xiàn)為柯西分布，在自由度較大時表現(xiàn)為高斯分布。將分布的自由度參數(shù)設(shè)為麻雀搜索算法迭代次數(shù)，前期表現(xiàn)為柯西分布，隨著迭代次數(shù)的增加，后期表現(xiàn)高斯分布，加強(qiáng)局部探索能力。通過擾動得到的位置既有利于增加種群多樣性，即尋得聚類中心的可能性增加，又可以增加聚類的迭代速度。分布效果如圖2所示，隨著自由度參數(shù)的增大，的大概率取值范圍越來越小。

圖2 t分布概率密度圖

擾動種群的計(jì)算公式為

式中：為當(dāng)前迭代次數(shù)；（）為自由度參數(shù)為的分布。采用擾動因子求取新解之后，根據(jù)貪婪原則更新得到的新種群如式（12）所示。

式中：（X）為X的適應(yīng)度；（X）為X的適應(yīng)度。

DHSSA優(yōu)化策略具體流程如下：

（1）確定麻雀種群的數(shù)量以及維度，計(jì)算種群適應(yīng)度并排序選出最優(yōu)和最差個體；

（2）開始迭代更新；

（3）發(fā)現(xiàn)者根據(jù)頭雀策略更新坐標(biāo)位置，加入者和警戒者利用SSA更新位置；

（4）利用擾動因子增加種群多樣性，根據(jù)貪婪原則決定是否替換原種群個體；

（5）判斷最優(yōu)適應(yīng)度是否小于迭代上次最優(yōu)適應(yīng)度，小于時就替換最優(yōu)個體，否則繼續(xù)；

（6）判斷是否達(dá)到最大迭代次數(shù)，是則輸出最優(yōu)個體，否則跳回（3）。

2.3 優(yōu)化策略的測試

為了驗(yàn)證算法的性能，DHSSA 與SSA、SOA、HHO進(jìn)行比較，測試函數(shù)如表1 所示。測試中，對于各個測試函數(shù)每種算法運(yùn)行30 次，得到均值和標(biāo)準(zhǔn)差如表2 所示，適應(yīng)度收斂曲線如圖3 所示。設(shè)置種群的規(guī)模為50，迭代次數(shù)為500。

表1 測試函數(shù)

表2和圖3數(shù)據(jù)表明，本文算法在求解各個函數(shù)時都表現(xiàn)出了優(yōu)異的性能。精度方面，對于函數(shù)F1，DHSSA＞SSA＞SOA＞HHO；對于函數(shù)F2 和F4，DHSSA＞SSA＞HHO＞SOA；對于函數(shù)F3，DHSSA＞HHO＞SSA＞SOA；對于函數(shù)F5，DHSSA＞SOA=HHO＞SSA。而對于函數(shù)F6，幾種算法精度相同，收斂速度方面DHSSA＞SSA＞SOA＞HHO。通過6 種測試函數(shù)驗(yàn)證了本文算法在總體上表現(xiàn)出較優(yōu)的性能，可以改善SSA的全局尋優(yōu)能力。

圖3 函數(shù)收斂曲線

表2 算法測試結(jié)果比較

3 DHSSA與KMC的互補(bǔ)迭代

3.1 適應(yīng)度函數(shù)選擇

適應(yīng)度函數(shù)決定了優(yōu)化麻雀群體進(jìn)化的方向，直接影響種群算法的優(yōu)化效果和解的質(zhì)量，且是DHSSA 與KMC 算法的唯一接口。KMC 以每個類別中個體到中心的距離和或個體總數(shù)為適應(yīng)度函數(shù)，距離或點(diǎn)個數(shù)相等時，會存在辨識能力不足而影響更新的問題。利用DHSSA 優(yōu)化聚類中心，結(jié)合距離和個數(shù)，采用如下適應(yīng)度函數(shù)：

式中：腳標(biāo)表示種群的類別數(shù)；（X，C）表示第類內(nèi)的對象到該類的聚類中心點(diǎn)的距離和；n為第類中的種群數(shù)量。從適應(yīng)度函數(shù)可以看出，當(dāng)前聚類結(jié)果的適應(yīng)度不僅與每個類別所有樣本點(diǎn)到該簇聚類中心的距離有關(guān)，也與該類樣本數(shù)有關(guān)，反映的是該簇所有樣本點(diǎn)到聚類中心歐式距離的均值大小。均值越小，適應(yīng)度越小，代表樣本點(diǎn)距離中心更近，該簇樣本更多。

3.2 篩選最大最小距離積初始化

利用最大最小距離積方法（maximum and minimum distance product，MMP）選取KMC 的初始中心，可以使得其代價有所減小，但選擇的第一個初始中心具有隨機(jī)性，有可能會把異常點(diǎn)計(jì)算為中心。同時，最大最小距離積法在計(jì)算的過程中，不考慮樣本數(shù)據(jù)之間相互影響和密集程度的問題，計(jì)算出的兩個中心點(diǎn)或者更多點(diǎn)可能出現(xiàn)在同一個簇中，尤其對于處理車型信息數(shù)據(jù)集這樣的高維數(shù)據(jù)集，初始化聚類中心的能力明顯不足。因此，針對上述問題，本文設(shè)計(jì)了一種篩選最大最小距離積法（screening maximum and minimum distance product，SMMP），計(jì)算所有點(diǎn)之間的距離，建立距離矩陣，然后求出該樣本中離所有點(diǎn)的距離和最小的點(diǎn)作為第一個中心點(diǎn)，避免第一個中心的盲目選擇問題。每個數(shù)據(jù)集分為類，說明有個簇。為了解決多個中心出現(xiàn)在一個簇中的問題，建立一個數(shù)值全為-1 的標(biāo)記矩陣，每選出一個中心，將距離中心的前/個點(diǎn)歸于對應(yīng)的中心，并且在矩陣中標(biāo)記出來，之后計(jì)算的中心只會在矩陣中標(biāo)記為-1 的元素中得到。這樣計(jì)算得到的中心大概率不會落在同一個簇中。SMMP 初始化算法可以有效減小車型信息數(shù)據(jù)之間相互影響和密集程度。

式中_XX表示第個元素到第個元素的距離，、=1，2，…，。對求取每行元素的距離和，即可得到第一個中心。

初始化步驟如下：

（1）計(jì)算數(shù)據(jù)集Data 中所有點(diǎn)之間的距離，建立，從中選取離所有點(diǎn)距離和最短的點(diǎn)作為第一個初始中心點(diǎn)，加入集合中，新建×1 的數(shù)值全為-1 的標(biāo)記矩陣，在中標(biāo)記周圍距離大小為前/的點(diǎn)為1；

（2）選取距離最大且在中標(biāo)記為-1 的元素為；

（3）將加入集合中，在中標(biāo)記周圍距離大小為前的點(diǎn)為2；

（4）分別統(tǒng)計(jì)Data 中標(biāo)記為-1的元素到中各個元素的距離，并存入臨時距離矩陣中；

（5）找出Data中標(biāo)記為-1的元素對應(yīng)中的最大距離和最小距離值，求其乘積，并將最大乘積值對應(yīng)的元素作為中心C（1≤≤），加入集合中，在中標(biāo)記C周圍距離大小為前的點(diǎn)為。若中元素個數(shù)小于，轉(zhuǎn)到步驟（4）；若中元素個數(shù)大于，則初始中心選取結(jié)束，輸出包含個初始點(diǎn)集合，得到初始中心。

通過以上步驟得到的初始聚類中心，可避免隨機(jī)初始化引起的初始誤差過大，有效減少了聚類耗時。選取Aggregation 數(shù)據(jù)集進(jìn)行初始化，圖4為3種初始化方法尋找聚類中心的對比結(jié)果，圖5 為優(yōu)化KMC更新曲線。

圖4 Aggregation數(shù)據(jù)集初始化對比

圖5 Aggregation數(shù)據(jù)集KMC聚類曲線

圖4 中，*為在Aggregation 數(shù)據(jù)集上隨機(jī)選取的聚類中心，初始化中心分布不規(guī)律，且大概率多中心落在同一個簇中；圓圈代表MMP 初始化得到的聚類中心，在左上角的簇中有兩個聚類中心；+代表SMMP 得到的初始化中心，每個中心均勻的分布在相應(yīng)的簇中。由圖5 可以看出，SMMP 的初始化與MMP 和隨機(jī)初始化（random init）相比其迭代速度更快，最優(yōu)適應(yīng)度更小。

3.3 DHSSA與KMC的互補(bǔ)迭代

KMC 通過求各個維度均值獲得新聚類中心，更新方法過于簡單，容易受異常點(diǎn)影響，陷入局部最優(yōu)，導(dǎo)致優(yōu)化精度過低。本文利用DHSSA 尋找聚類中心，實(shí)現(xiàn)與KMC 的互補(bǔ)迭代，擴(kuò)大尋優(yōu)范圍，避免陷入局部最優(yōu)的同時提高搜索精度，流程如圖6所示。

圖6 方法流程圖

基本步驟如下：

（1）輸入數(shù)據(jù)集Data，根據(jù)其類別的個數(shù)確定數(shù)據(jù)集中類的個數(shù)；

（2）利用SMMP初始化中心點(diǎn)；

（3）計(jì)算Data 中的每個樣本點(diǎn)到各個聚類中心的歐式距離，按數(shù)值大小進(jìn)行排序，將樣本點(diǎn)所屬類別歸于最小歐式距離的聚類中心；

（4）在每個類別的麻雀種群中通過DHSSA 進(jìn)行尋優(yōu)操作，得到新的聚類中心；

（5）使用KMC 確定每個樣本的類別，計(jì)算由新中心聚類得到的新類別的適應(yīng)度_new，若其適應(yīng)度優(yōu)于上次迭代的聚類中心，則用新的聚類中心取代。判斷當(dāng)前迭代是否達(dá)到結(jié)束條件，若未達(dá)到結(jié)束條件則執(zhí)行步驟（4），使得DHSSA 與KMC 互補(bǔ)迭代，否則循環(huán)結(jié)束，輸出尋優(yōu)結(jié)果結(jié)束程序。

3.4 輪廓系數(shù)（silhouette index，SI）

輪廓系數(shù)具有相對較好的評價能力，被廣泛使用，它反映了聚類數(shù)據(jù)集的類內(nèi)緊密程度和類間的區(qū)分程度，本文使用SI 指標(biāo)驗(yàn)證各聚類算法的聚類效果。

假設(shè)有一個數(shù)據(jù)集被劃分成了個類，X是其中的一個樣本數(shù)據(jù)，X的SI指標(biāo)為

式中（X）為樣本x與其所屬中心C（1≤≤）中的其他樣本的平均相似度。令（X，C）為樣本x到其他中心C（1≤≤）的所有樣本的平均相似度，則（X）=min｛（X，C）｝。（X）和（X）的計(jì)算公式為

式中：n為X所屬類的數(shù)量；X為X所屬類C的其他樣本。

由（X）可以計(jì)算得到一個類C的所有樣本的平均值（C），進(jìn)而計(jì)算得到一個數(shù)據(jù)集所有樣本的值，值可以反映聚類結(jié)果的好壞，指標(biāo)值越大，代表類別之間分離程度越大，類內(nèi)緊密程度越高。

4 實(shí)驗(yàn)結(jié)果分析與應(yīng)用

4.1 算法性能評價

硬件平臺為Intel Core i5-7300HQ CPU 2.60GHz、8GB 內(nèi)存的計(jì)算機(jī)，計(jì)算軟件為Matlab R2017b。為了評價效果，將DHSSA-KMC 與SSA-KMC、IMFOKMC、KMC++、KMC 在公共數(shù)據(jù)集Wine、Ionosphere、Aggregation、Vowel、Glass、Ecoli 上驗(yàn)證。其中，Wine、Ionosphere 為高維少分類數(shù)據(jù)集，Aggregation、Vowel為低維多分類數(shù)據(jù)集，Glass、Ecoli 為高維多分類數(shù)據(jù)集。最大迭代次數(shù)都設(shè)置為50 次，在上述5 種聚類方法中，KMC++采取算法本身初始化方法，其余算法的初始化皆使用本文的初始化算法。各數(shù)據(jù)集的主要特征如表3 所示，各聚類算法處理各數(shù)據(jù)集的適應(yīng)度收斂曲線如圖7所示。

圖7 不同算法在6種數(shù)據(jù)集上的運(yùn)行結(jié)果

表3 標(biāo)準(zhǔn)數(shù)據(jù)集特征

由圖7可以看出，DHSSA-KMC在聚類精度和收斂速度方面都優(yōu)于其他4 種算法。在數(shù)據(jù)集Wine的測試中，DHSSA-KMC 的適應(yīng)度＜IMFO- KMC＜SSA-KMC＜KMC++＜KMC；在數(shù)據(jù)集Ionosphere 的測試 中，DHSSA-KMC 的 適 應(yīng) 度＜SSA-KMC＜IMFOKMC=KMC++=KMC；在數(shù)據(jù)集Aggregation 和Vowel測 試 中，DHSSA-KMC 的 適 應(yīng) 度＜IMFO-KMC＜KMC++=KMC ＜SSA-KMC；在數(shù)據(jù)集Glass 測試上，DHSSA-KMC 的適應(yīng)度＜SSA-KMC＜KMC ＜KMC++＜IMFO-KMC；在數(shù)據(jù)集Ecoli測試中，DHSSA-KMC 的適應(yīng)度＜IMFO-KMC＜SSA-KMC ＜KMC＜KMC++。

由圖7曲線還可以看出：在Ionosphere、Aggregation、Vowel數(shù)據(jù)集上，KMC和KMC++的適應(yīng)度曲線重合，證明SMMP 初始化方法和KMC++的初始化方法效果相同；在Glass、Ecoli 數(shù)據(jù)集上，KMC 在初始和聚類完成的適應(yīng)度均優(yōu)于KMC++，說明在處理復(fù)雜數(shù)據(jù)上SMMP初始化方法優(yōu)于KMC++的初始化方法。

采用Acc、ARI、NMI 3種評價指標(biāo)對不同聚類算法進(jìn)行評估。其中，Acc 表示聚類準(zhǔn)確率，ARI 衡量兩個數(shù)據(jù)分布的吻合程度，NMI 表示兩組數(shù)據(jù)之間的關(guān)聯(lián)程度。3 個指標(biāo)的范圍都為［0，1］，值越大表示結(jié)果越好。對Wine、Aggregation、Ecoli 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如表4所示。

表4 不同算法對3個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表4中的評價數(shù)據(jù)是由50次獨(dú)立實(shí)驗(yàn)數(shù)據(jù)求均值得到的，在Wine 中，本文算法的Acc 與其它算法相比提高了0.53%～3.6%，ARI提高了1.24%～3.21%，NMI 提高了0.23%～3.81%；在Aggregation 中，本文算法的Acc 相對其它算法提高了3.55%～5.33%，ARI提高了6.1%～8.87%，NMI低于IMFO-KMC1.23%，與其它算法相比提高了2.79%～4.77%。在Ecoli中，本文算法的Acc 與其它算法相比提高了3.55%～5.33%，ARI提高了2.99%～7.99%，NMI提高了1.61%～4.12%。因此，DHSSA-KMC聚類效果指標(biāo)更優(yōu)。

表5 所示為用各聚類算法處理Wine、Aggregation、Ecoli數(shù)據(jù)集計(jì)算指標(biāo)的結(jié)果。

表5 3個數(shù)據(jù)集的SI指標(biāo)

由表5 中指標(biāo)可以看出，在Wine 上，本文算法相對其它算法提高了2.77%～15.01%，在Aggregation 上，本文算法相對其它算法提高了3.25%～12.96%，在Ecoli上，本文算法相對其它算法提高了1.1%～6.37%。在3 個數(shù)據(jù)集上，本文算法的Sav 值最大，表示類別之間分離程度最大，類內(nèi)緊密程度最高。

聚類的迭代融合群體智能算法的迭代，能提高聚類精度，但會增加耗時。當(dāng)最大迭代次數(shù)仍設(shè)為50時，各算法優(yōu)化聚類的時間代價如表6所示。

表6 不同算法對3個數(shù)據(jù)集的時間代價 s

從表6中可以看出，在Wine、Aggregation 和Ecoli中，本文算法分別比IMFO-KMC 降低了0.427、0.635 和0.771 s，比SSA-KMC 降低了0.118、0.060和0.113 s，比經(jīng)典的KMC 提高了0.177、0.498 和0.588 s。綜合來看，本文算法相對于經(jīng)典KMC 的迭代耗時略高，相對于IMFO-KMC 和SSA-KMC 有所減小。這是因?yàn)镮MFO-KMC 受限于飛蛾的更新機(jī)制，收斂速度提高有限，而本文算法繼承了SSA 位置更新更快的優(yōu)點(diǎn)，并且提高了全局尋優(yōu)的能力，能夠在保證精度的同時減少迭代時間。

4.2 車型信息數(shù)據(jù)聚類分析

實(shí)驗(yàn)選取具有代表性的阿里云公開的汽車聚類數(shù)據(jù)集，數(shù)據(jù)為205款車的26個字段，主要包括汽車 的id（car_ID）、風(fēng) 險 等 級（symbolling）、車 型（CarName）、燃油（fueltype）、最大轉(zhuǎn)速（peakrpm）、城市里程（citympg）、高速里程（highwaympg）、價格（price）等參數(shù)。聚類的目的是針對指定的車型，通過數(shù)據(jù)聚類分析可以找到其同類車型即競品車型。原數(shù)據(jù)集存在非數(shù)值型數(shù)據(jù)，需要將非數(shù)值字段轉(zhuǎn)化為數(shù)值，操作方式為獨(dú)熱編碼。轉(zhuǎn)換后的數(shù)據(jù)特征前5 列如表7 所示。對于汽車數(shù)據(jù)集的分類數(shù)量可以通過肘部原則來選擇，本文選擇=5，對于汽車數(shù)據(jù)集的聚類迭代曲線如圖8 所示，對于汽車數(shù)據(jù)集的聚類Silhouette指標(biāo)如表8所示。

圖8 不同算法在車型信息數(shù)據(jù)集上的運(yùn)行結(jié)果

表7 編碼后的汽車聚類數(shù)據(jù)集

從表8 中可以看出，在車型信息數(shù)據(jù)集上，本文算 法 的Sav 值 為0.554 1，比IMFO-KMC 提 高 了0.116 3，比KMC 提高了0.149 6，比SSA-KMC 提高了0.194 3，本文算法在聚類車型信息數(shù)據(jù)集時使得車型同類之間距離更小，類別之間距離更大，聚類效果最佳。

表8 車型信息數(shù)據(jù)集的Silhouette指標(biāo)

通過聚類可以將相似的汽車屬性聚為一類，然后利用聚類結(jié)果分析各個類的差別以及同類汽車屬性的差異。例如：某客戶中意奧迪車，可以找出audi汽車的聚類結(jié)果，如表9 所示。也可以找出audi 品牌下audi 5000 所在的類別5，并統(tǒng)計(jì)出類別為5 和carbody標(biāo)簽為wagon 的所有車輛，然后按價格排序，供消費(fèi)者選擇出最符合需求的汽車，如表10所示。

表9 audi汽車的聚類結(jié)果

表10 按價格排序的audi 5000的競品車型

5 結(jié)論

本文提出了一種DHSSA 優(yōu)化的K 均值互補(bǔ)迭代車型信息數(shù)據(jù)聚類方法。首先設(shè)計(jì)了一種擾動因子-領(lǐng)頭雀優(yōu)化策略，由此提升SSA 的全局尋優(yōu)能力，減小了由于SSA 易陷入局部最優(yōu)造成的時間成本；然后利用篩選最大最小距離積法初始化中心，保證了各個中心最大程度地落在每個簇中；最后將DHSSA與KMC互補(bǔ)迭代，解決了聚類迭代過程中受離群點(diǎn)影響大以及路徑搜索能力不足的問題，減小了迭代次數(shù)，同時提升了搜索效率，得到較好的聚類結(jié)果。最后通過車型信息數(shù)據(jù)集聚類，驗(yàn)證了本文算法的應(yīng)用價值。