黃 鶴，李文龍，楊 瀾，王會(huì)峰，王 飚，茹 鋒

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

前言

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

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

1.1 KMC算法

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

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

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

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

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

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

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

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

1.2 SSA算法

（1）初始化

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

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

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

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

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

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

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

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

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

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

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

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

2.2 擾動(dòng)因子

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

圖2 t分布概率密度圖

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

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

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

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

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

（2）開(kāi)始迭代更新；

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

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

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

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

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

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

表1 測(cè)試函數(shù)

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

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

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

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

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

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

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

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

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

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

初始化步驟如下：

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

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

（3）將加入集合中，在中標(biāo)記周?chē)嚯x大小為前的點(diǎn)為2；

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

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

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

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

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

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

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

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

圖6 方法流程圖

基本步驟如下：

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

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

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

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

（5）使用KMC 確定每個(gè)樣本的類(lèi)別，計(jì)算由新中心聚類(lèi)得到的新類(lèi)別的適應(yīng)度_new，若其適應(yīng)度優(yōu)于上次迭代的聚類(lèi)中心，則用新的聚類(lèi)中心取代。判斷當(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ù)具有相對(duì)較好的評(píng)價(jià)能力，被廣泛使用，它反映了聚類(lèi)數(shù)據(jù)集的類(lèi)內(nèi)緊密程度和類(lèi)間的區(qū)分程度，本文使用SI 指標(biāo)驗(yàn)證各聚類(lèi)算法的聚類(lèi)效果。

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

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

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

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

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

4.1 算法性能評(píng)價(jià)

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

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

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

由圖7可以看出，DHSSA-KMC在聚類(lèi)精度和收斂速度方面都優(yōu)于其他4 種算法。在數(shù)據(jù)集Wine的測(cè)試中，DHSSA-KMC 的適應(yīng)度＜IMFO- KMC＜SSA-KMC＜KMC++＜KMC；在數(shù)據(jù)集Ionosphere 的測(cè)試 中，DHSSA-KMC 的 適 應(yīng) 度＜SSA-KMC＜IMFOKMC=KMC++=KMC；在數(shù)據(jù)集Aggregation 和Vowel測(cè) 試 中，DHSSA-KMC 的 適 應(yīng) 度＜IMFO-KMC＜KMC++=KMC ＜SSA-KMC；在數(shù)據(jù)集Glass 測(cè)試上，DHSSA-KMC 的適應(yīng)度＜SSA-KMC＜KMC ＜KMC++＜IMFO-KMC；在數(shù)據(jù)集Ecoli測(cè)試中，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 在初始和聚類(lèi)完成的適應(yīng)度均優(yōu)于KMC++，說(shuō)明在處理復(fù)雜數(shù)據(jù)上SMMP初始化方法優(yōu)于KMC++的初始化方法。

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

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

表4中的評(píng)價(jià)數(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 相對(duì)其它算法提高了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聚類(lèi)效果指標(biāo)更優(yōu)。

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

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

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

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

表6 不同算法對(duì)3個(gè)數(shù)據(jù)集的時(shí)間代價(jià) 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。綜合來(lái)看，本文算法相對(duì)于經(jīng)典KMC 的迭代耗時(shí)略高，相對(duì)于IMFO-KMC 和SSA-KMC 有所減小。這是因?yàn)镮MFO-KMC 受限于飛蛾的更新機(jī)制，收斂速度提高有限，而本文算法繼承了SSA 位置更新更快的優(yōu)點(diǎn)，并且提高了全局尋優(yōu)的能力，能夠在保證精度的同時(shí)減少迭代時(shí)間。

4.2 車(chē)型信息數(shù)據(jù)聚類(lèi)分析

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

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

表7 編碼后的汽車(chē)聚類(lèi)數(shù)據(jù)集

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

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

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

表9 audi汽車(chē)的聚類(lèi)結(jié)果

表10 按價(jià)格排序的audi 5000的競(jìng)品車(chē)型

5 結(jié)論

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