莊麗麗，石鴻雁

(沈陽(yáng)工業(yè)大學(xué)理學(xué)院，遼寧 沈陽(yáng) 110870)

0 引 言

離群點(diǎn)檢測(cè)作為數(shù)據(jù)挖掘的基本任務(wù)之一，該技術(shù)的目的在于通過(guò)分析離群點(diǎn)的分布特征，高效準(zhǔn)確地從海量的數(shù)據(jù)中挖掘出異常的數(shù)據(jù)信息[1-2]。傳統(tǒng)的離群點(diǎn)檢測(cè)方法一般分為4類：基于統(tǒng)計(jì)學(xué)的、基于分類的、基于聚類的和基于密度的[3]。目前，離群點(diǎn)檢測(cè)技術(shù)被應(yīng)用于詐騙檢測(cè)、圖像處理、異常模式檢測(cè)等許多領(lǐng)域。k-means算法作為一種經(jīng)典的聚類算法[4-5]，近年來(lái)被廣泛地應(yīng)用于離群點(diǎn)檢測(cè)領(lǐng)域?；趉-means算法的離群點(diǎn)檢測(cè)方法簡(jiǎn)單、高效，可以快速地檢測(cè)出離群數(shù)據(jù)，但同時(shí)該離群點(diǎn)檢測(cè)算法對(duì)初始聚類中心敏感，導(dǎo)致檢測(cè)結(jié)果出現(xiàn)誤差。為了解決這一問(wèn)題，很多學(xué)者將仿生智能優(yōu)化算法運(yùn)用于傳統(tǒng)k-means算法的離群點(diǎn)檢測(cè)中，產(chǎn)生了許多k-means算法的離群點(diǎn)檢測(cè)的衍生算法。例如:傅濤等人[6]將粒子群優(yōu)化算法(PSO)與k-means算法結(jié)合，用于入侵檢測(cè)，克服了k-means算法容易受到初始聚類中心的影響這一缺點(diǎn)；于佐軍等人[7]將蜂群算法用于k-means算法中，提高了算法的收斂速度，消除了算法受初始聚類中心的影響可能。但粒子群和人工蜂群算法參數(shù)較多，而且與k-means算法結(jié)合后的算法在求解精度方面沒有明顯改善。

而本文提到的布谷鳥搜索算法(Cuckoo Search, CS)作為一種新型啟發(fā)式算法，該算法模擬布谷鳥需要尋找宿主鳥窩孵化鳥蛋這種寄生現(xiàn)象的過(guò)程，具有參數(shù)少、操作簡(jiǎn)單以及全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)。但同時(shí)也存在一些缺點(diǎn)：受萊維飛行隨機(jī)游走的盲目性的影響，在搜索過(guò)程中容易陷入局部最優(yōu)，并且收斂速度慢[8]。為了CS算法的發(fā)展與應(yīng)用，國(guó)內(nèi)外許多學(xué)者對(duì)CS算法進(jìn)行了改進(jìn)研究。例如：Gherboudj等人[9]提出了一種離散二進(jìn)制布谷鳥搜索算法來(lái)處理二進(jìn)制優(yōu)化問(wèn)題；Ouyang等人[10]提出了離散布谷鳥算法，用于解決球形旅行商問(wèn)題；Wang等人[11]將混沌理論引入CS算法，提出了一種新穎的混沌布谷鳥搜索優(yōu)化算法等。但這些改進(jìn)算法并沒有平衡局部搜索與全局搜索之間的關(guān)系。于是，本文首先對(duì)CS算法中的發(fā)現(xiàn)概率Pa和萊維飛行步長(zhǎng)做自適應(yīng)改進(jìn)。通過(guò)實(shí)驗(yàn)，結(jié)果表明改進(jìn)的CS算法在迭代次數(shù)、求解精度、解空間范圍等方面優(yōu)于原始的CS算法。然后將改進(jìn)后的布谷鳥搜索算法(Improved Cuckoo Search, ICS)與傳統(tǒng)的k-means算法的離群點(diǎn)檢測(cè)相結(jié)合，提出一種基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)(Outlier Detection Based on Improved Cuckoo Search k-means Algorithm, ICS-KM-OD)算法，可解決傳統(tǒng)k-means算法的離群點(diǎn)檢測(cè)易受初始聚類中心的影響陷入局部最優(yōu)的問(wèn)題。通過(guò)在3個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文的離群點(diǎn)檢測(cè)算法能夠獲得更好的性能指標(biāo)，其收斂速度和檢測(cè)效果都得到了改善。

1 相關(guān)算法

1.1 基于k-means算法的離群點(diǎn)檢測(cè)

(1)

其中，d為樣本維度，nj為聚類結(jié)果中第j個(gè)類的類內(nèi)樣本個(gè)數(shù)，k為聚類參數(shù)。

1.2 CS算法

CS算法是以布谷鳥的寄巢產(chǎn)卵特點(diǎn)及少部分生物的萊維飛行模式為參照，具有迭代搜索的特征。其主要思想是通過(guò)隨機(jī)行走方式產(chǎn)生候選鳥巢以及偏好隨機(jī)游走策略更新鳥巢位置，最終使鳥巢位置達(dá)到或者接近全局最優(yōu)解[13]。CS算法具體思路如下。

基于文獻(xiàn)[14]中CS算法的3個(gè)理想狀態(tài)，布谷鳥尋找宿主鳥巢的位置和路徑的更新公式如下：

(2)

(3)

通過(guò)公式(2)進(jìn)行位置更新后，生成隨機(jī)數(shù)r(r∈[0,1])。將r與Pa進(jìn)行比較，若r>Pa，則利用萊維飛行偏好游走策略隨機(jī)更新一次鳥巢位置，否則鳥巢位置不變。萊維飛行的偏好隨機(jī)游走策略如下[15]：

(4)

2 改進(jìn)布谷鳥搜索ICS算法及其收斂性分析

2.1 布谷鳥算法的改進(jìn)

經(jīng)過(guò)研究發(fā)現(xiàn)，CS算法中發(fā)現(xiàn)概率和萊維飛行步長(zhǎng)影響著搜索范圍、收斂速度和搜索精度。因此本文對(duì)CS算法的發(fā)現(xiàn)概率和步長(zhǎng)進(jìn)行自適應(yīng)調(diào)整，并給出使發(fā)現(xiàn)概率和步長(zhǎng)隨算法進(jìn)程動(dòng)態(tài)變化的自適應(yīng)策略。

1)發(fā)現(xiàn)概率Pa的自適應(yīng)策略。

CS算法中發(fā)現(xiàn)概率Pa平衡著全局搜索和局部搜索。將Pa取固定值不利于全局搜索與局部搜索之間的平衡，因此有必要給出Pa的自適應(yīng)策略：

(5)

公式(5)實(shí)現(xiàn)了Pa隨算法進(jìn)程由小到大的動(dòng)態(tài)變化，使得改進(jìn)后的算法在運(yùn)行前期能夠保持很好的全局搜索能力，同時(shí)兼顧局部搜索，而在后期，局部搜索逐漸增強(qiáng)，兼顧全局搜索，提高了算法收斂速度，避免陷入局部最優(yōu)。

2)萊維飛行步長(zhǎng)的自適應(yīng)策略。

在萊維飛行機(jī)制中，步長(zhǎng)的大小主要是通過(guò)步長(zhǎng)因子α來(lái)體現(xiàn)。固定步長(zhǎng)因子會(huì)影響算法的搜索速度和精度。本文給出一種步長(zhǎng)的自適應(yīng)策略：

(6)

其中，ti為當(dāng)前迭代次數(shù),tmax為最大迭代次數(shù)。此時(shí)，公式(2)修改為：

(7)

公式(7)實(shí)現(xiàn)了搜索前期范圍擴(kuò)大，收斂速度加快，在搜索后期步長(zhǎng)逐漸減小，局部搜索能力增強(qiáng)，提高了搜索的精度。

改進(jìn)的布谷鳥搜索算法的步驟如下。

步驟3 位置更新后，生成隨機(jī)數(shù)r(r∈[0,1])，并將r與Pa進(jìn)行比較，若r>Pa，就根據(jù)公式(4)隨機(jī)更新一次鳥巢位置，否則鳥巢位置不變。

2.2 ICS算法的收斂性

本節(jié)從隨機(jī)算法全局收斂準(zhǔn)則的角度出發(fā)，并結(jié)合Markov鏈模型，對(duì)ICS算法收斂性進(jìn)行證明和分析[16]。

2.2.1 ICS算法的Markov模型

Markov鏈理論是仿生智能算法收斂性分析的重要手段，已經(jīng)成功應(yīng)用在蟻群算法、遺傳算法、粒子群算法等隨機(jī)收斂性分析中。下面建立ICS算法的Markov鏈模型。

定義1 鳥巢位置的狀態(tài)和狀態(tài)空間。鳥巢位置構(gòu)成了鳥巢狀態(tài)，記作x,x∈A,A為可行解空間。鳥巢位置所有可能狀態(tài)組成的集合構(gòu)成了鳥巢位置的狀態(tài)空間，記為X={x|x∈A}[17]。

定義2 鳥巢位置的群狀態(tài)和群狀態(tài)空間。鳥巢位置群中所有鳥巢的狀態(tài)構(gòu)成了鳥巢位置群狀態(tài)，記作s=(x1,x2,…,xN)，其中xi表示第i個(gè)鳥巢位置的狀態(tài)。鳥巢位置群中所有可能狀態(tài)組成的集合構(gòu)成鳥巢位置群狀態(tài)空間，記為S={s=(x1,x2,…,xN)|xi∈X,1≤i≤N}。

定義3 鳥巢位置的狀態(tài)轉(zhuǎn)移。?xi,xj∈X，在ICS算法迭代中，鳥巢位置的狀態(tài)從xi轉(zhuǎn)移到xj，記為T(xi)=xj。

命題1 在ICS算法中，鳥巢位置狀態(tài)從xi轉(zhuǎn)移到xj的轉(zhuǎn)移概率為P(T(xi)=xj)。其表達(dá)式為P(T(xi)=xj)=P(xi→x′i)P(x′i→xj)，其中P(xi→x′i)是通過(guò)ICS算法中公式(7)的位置轉(zhuǎn)移的概率，P(x′i→xj)表示被發(fā)現(xiàn)后通過(guò)偏好隨機(jī)游走所產(chǎn)生的位置轉(zhuǎn)移概率。

證明：假設(shè)鳥巢位置狀態(tài)從xi轉(zhuǎn)移到xj的過(guò)程中，它們之間有一次的中間轉(zhuǎn)移狀態(tài)x′i,此時(shí)P(T(xi)=xj)為：

P(T(xi)=xj)=P(xi→x′i)P(x′i→xj)

(8)

由位置更新公式(7)可知，鳥巢位置狀態(tài)xi→x′i的轉(zhuǎn)移概率為：

(9)

其中：

(10)

由于x、g是多維數(shù)據(jù)，公式(9)中的絕對(duì)值表示超空間立方體的體積。

由文獻(xiàn)[14]布谷鳥算法的理想狀態(tài)(3)結(jié)合ICS算法的步驟3可知，鳥巢位置狀態(tài)x′i→xj的概率為：

(11)

其中：

(12)

定義4 鳥巢位置群狀態(tài)轉(zhuǎn)移。在ICS算法迭代中，?si=(xi1,xi2,…,xiN)∈S, ?sj=(xj1,xj2,…,xjN)∈S，鳥巢位置的群狀態(tài)從si到sj，記作T(si)=sj。

命題2 在ICS算法中，鳥巢位置的群狀態(tài)從si轉(zhuǎn)移到sj的轉(zhuǎn)移概率為：

(13)

證明：鳥巢位置群狀態(tài)包含了所有鳥巢位置狀態(tài)。當(dāng)鳥巢位置群狀態(tài)從si轉(zhuǎn)移到sj時(shí)，群狀態(tài)中所有位置狀態(tài)都會(huì)同時(shí)轉(zhuǎn)移，即T(xi1)=xj1,T(xi2)=xj2,…,T(xiN)=xjN同時(shí)成立，則鳥巢位置群狀態(tài)轉(zhuǎn)移的概率為：

P(T(si)=sj)=P(T(xi1)=xj1)P(T(xi2)=xj2)…P(T(xiN)=xjN)

(14)

定理1 ICS算法中鳥巢位置群狀態(tài)序列{s(t):t≥0}，是有限齊次Markov鏈。

證明：算法的搜索空間是有限的，鳥巢位置狀態(tài)xi是有限的，因此鳥巢位置狀態(tài)空間X也是有限的。群狀態(tài)s=(x1,x2,…,xN)是由N個(gè)鳥巢位置狀態(tài)組成，N為有限正整數(shù)，則鳥巢位置的群狀態(tài)空間S也是有限的。由命題2可知群狀態(tài)序列{s(t):t≥0}中，?s(t-1),s(t)∈S，其轉(zhuǎn)移概率P(T(s(t-1))=s(t))是由鳥巢群體中所有鳥巢位置的轉(zhuǎn)移概率P(T(x(t-1))=x(t))決定，由命題1可知轉(zhuǎn)移概率與t-1時(shí)刻的狀態(tài)相關(guān)，而與時(shí)間t-1無(wú)關(guān)，即鳥巢的群體狀態(tài)有Markov性和齊次性，而狀態(tài)空間為可列集，因此其構(gòu)成一個(gè)有限齊次Markov鏈[18]。

2.2.2 ICS算法的收斂性分析

定義5 設(shè)優(yōu)化問(wèn)題〈A，f〉全局最優(yōu)解為g*，定義鳥巢位置最優(yōu)狀態(tài)集M={s*=(x)|f(x)=f(g*),x∈A,s∈S}。

引理1 ICS算法中，對(duì)鳥巢位置群狀態(tài)序列{s(t):t≥0}而言，最優(yōu)狀態(tài)集M是群狀態(tài)空間S上的閉集。

證明：?si,sj∈M，對(duì)于任意轉(zhuǎn)移步長(zhǎng)l,l≥1，由Chapman-Kolmogorov方程可得：

P(T(sr1)=sr2)…P(T(sr(l-1))=sj)

(15)

(16)

引理2 鳥巢位置的群狀態(tài)空間S中不存在非空閉集B，使得B∩M=?。

證明：用反證法。假設(shè)鳥巢位置群狀態(tài)空間S中存在非空閉集B，且B∩M=?，則設(shè)si=(g*,g*,…,g*)∈M, ?sj=(xj1,xj2,…,xjN)∈B，有f(xjc)>f(g*)，由命題1和命題2可得，對(duì)每個(gè)P(T(sj)=si)都有P(T(xj)=xi)=P(xj→x′j)P(x′j→xi)，由于P(xj→x′j)P(x′j→xi)>0，則P(T(xj)=xi)≠0，因此B不是閉集，這與假設(shè)矛盾。因此群狀態(tài)空間S中不可能存在M之外的非空閉集。

由上述引理1～引理3可知，當(dāng)群內(nèi)部迭代次數(shù)趨于無(wú)窮時(shí)，群狀態(tài)序列一定會(huì)進(jìn)入最優(yōu)狀態(tài)集M。

定理2 ICS算法收斂到全局最優(yōu)。

證明：由于ICS算法的適應(yīng)度函數(shù)是非遞增的，所以ICS算法滿足文獻(xiàn)[16]中隨機(jī)算法收斂準(zhǔn)則假設(shè)1，由上述結(jié)論可知，ICS算法滿足文獻(xiàn)[16]中隨機(jī)算法收斂準(zhǔn)則假設(shè)2，故ICS算法收斂于全局最優(yōu)。

3 基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)

基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)ICS-KM-OD算法利用ICS算法克服了傳統(tǒng)k-means離群點(diǎn)檢測(cè)容易受到初始聚類中心影響的缺點(diǎn)。該算法首先在原始布谷鳥搜索算法的基礎(chǔ)上，基于發(fā)現(xiàn)概率和步長(zhǎng)進(jìn)行自適應(yīng)改進(jìn)，使其擺脫收斂速度偏慢、求解精度低的缺陷；然后將改進(jìn)后的布谷鳥搜索算法與基于k-means的離群點(diǎn)檢測(cè)算法進(jìn)行并行融合，解決原始k-means算法受初始聚類中心影響陷入局部最優(yōu)問(wèn)題。

在離群點(diǎn)檢測(cè)算法過(guò)程中通常采用適應(yīng)度函數(shù)來(lái)評(píng)價(jià)檢測(cè)結(jié)果，本文采用歐氏距離度量的方法，實(shí)現(xiàn)樣本數(shù)據(jù)的k-means劃分。樣本x與樣本y的距離公式為：

(17)

因此適應(yīng)度函數(shù)為：

(18)

其中，λ為任意實(shí)數(shù)，cj(j=1,2,…,k)為聚類中心。顯然適應(yīng)度值越大，劃分效果越好[21-23]。

3.1 ICS-KM-OD算法步驟

步驟1 給定待檢測(cè)數(shù)據(jù)集和初始聚類參數(shù)k。

步驟2 在待檢測(cè)數(shù)據(jù)集中隨機(jī)選取n個(gè)數(shù)據(jù)樣本作為初始鳥巢位置，并且設(shè)置初始參數(shù)。

步驟3 進(jìn)行k-means聚類劃分，計(jì)算每個(gè)鳥巢的適應(yīng)度值并保留最優(yōu)鳥巢。

步驟4 按照改進(jìn)的布谷鳥搜索算法對(duì)其他的鳥巢進(jìn)行更新。

步驟5 根據(jù)更新后的鳥巢進(jìn)行k-means劃分并求新的適應(yīng)度值，將更新后的鳥巢與上一代鳥巢進(jìn)行對(duì)比，若更好則代替。

步驟6 按發(fā)現(xiàn)概率Pa拋棄鳥巢并重建。

步驟7 進(jìn)行k-means劃分并計(jì)算鳥巢的適應(yīng)度，選出最好的鳥巢，與目前的最優(yōu)鳥巢對(duì)比，若更好，則將此鳥巢置為最優(yōu)鳥巢。

步驟8 如果未達(dá)到最大的迭代次數(shù)或不滿足終止條件則返回步驟4繼續(xù)執(zhí)行；否則輸出最優(yōu)的聚類中心點(diǎn)、簇內(nèi)距離和簇間距離。

3.2 仿真結(jié)果

實(shí)驗(yàn)的仿真環(huán)境為Windows 10操作系統(tǒng)，Intel 2.20 GHz CPU, 4 GB RAM，仿真軟件為Matlab 2017a。

實(shí)驗(yàn)1 改進(jìn)后的布谷鳥搜索算法(ICS)的仿真實(shí)驗(yàn)。

本文選取4個(gè)基準(zhǔn)測(cè)試函數(shù)對(duì)ICS進(jìn)行仿真測(cè)試，將其實(shí)驗(yàn)結(jié)果與原始CS算法進(jìn)行對(duì)比，以驗(yàn)證其收斂性能和尋優(yōu)能力。參數(shù)設(shè)置和測(cè)試函數(shù)如表1和表2所示。

表1 實(shí)驗(yàn)參數(shù)

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

1)為了驗(yàn)證ICS算法的收斂性能，本文選取4個(gè)測(cè)試函數(shù)進(jìn)行試驗(yàn)仿真，將其實(shí)驗(yàn)結(jié)果與原始的CS算法進(jìn)行比較。圖1給出了2種算法對(duì)各測(cè)試函數(shù)的收斂曲線。從圖1(a)～圖1(c)可以看出，對(duì)于測(cè)試函數(shù)f1、f2、f3來(lái)說(shuō)，ICS算法的最小適應(yīng)度值明顯比CS算法下降得快；從圖1(d)可以看出，由于函數(shù)本身比較復(fù)雜，容易陷入局部最優(yōu)，ICS算法的精度雖然不高但還是優(yōu)于CS算法，在迭代500次后，最小適應(yīng)度值明顯比CS算法下降得快。因此，ICS算法在收斂速度上優(yōu)于CS算法，較好地解決了原始CS算法收斂速度慢的問(wèn)題，改善了全局尋優(yōu)能力。

(a) f1

(b) f2

(c) f3

(d) f4

2)為了驗(yàn)證ICS算法的優(yōu)越性，分析其尋優(yōu)效果，將ICS算法與CS算法在不同維度進(jìn)行多次獨(dú)立的實(shí)驗(yàn)，對(duì)比結(jié)果如表3～表5所示。從表3可以看出，在10維的條件下，對(duì)測(cè)試函數(shù)f1和f2，2種算法都能達(dá)到所要求的精度，但I(xiàn)CS算法的運(yùn)行時(shí)間和迭代次數(shù)明顯少于CS算法，對(duì)測(cè)試函數(shù)f3和f4，ICS算法的優(yōu)勢(shì)更加明顯，可以更快地達(dá)到目標(biāo)精度。從表4可以看出，在30維的條件下，對(duì)于測(cè)試函數(shù)f1和f2，ICS算法有更好的搜索精度，并且迭代次數(shù)最少，對(duì)測(cè)試函數(shù)f3，ICS算法以最快的速度收斂至全局最優(yōu)，而此時(shí)CS算法無(wú)法收斂于全局最優(yōu)，對(duì)測(cè)試函數(shù)f4，雖然2種算法的尋優(yōu)能力相差不大，但I(xiàn)CS算法的計(jì)算結(jié)果要優(yōu)于CS算法。從表5可以看出，在50維的條件下，對(duì)于測(cè)試函數(shù)f1，CS算法無(wú)法收斂于全局最優(yōu)，但I(xiàn)CS算法卻以最快的速度收斂于全局最優(yōu)，并且可以較快地達(dá)到目標(biāo)精度，對(duì)測(cè)試函數(shù)f2和f3，2種算法都可以收斂于全局最優(yōu)，但I(xiàn)CS算法在收斂速度和計(jì)算精度上有明顯的優(yōu)勢(shì)，對(duì)測(cè)試函數(shù)f4，雖然ICS算法和CS算法都沒有達(dá)到目標(biāo)精度，但I(xiàn)CS算法具有更快的收斂速度。

表3 10維情況下算法性能比較

表4 30維情況下算法性能比較

表5 50維情況下算法性能比較

實(shí)驗(yàn)2 基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)的仿真實(shí)驗(yàn)。

為了驗(yàn)證基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)的有效性，本文選擇UCI中標(biāo)準(zhǔn)數(shù)據(jù)集Iris、Wine與Synthetic進(jìn)行測(cè)試分析。數(shù)據(jù)集的基本信息如表6所示。

表6 測(cè)試數(shù)據(jù)集

對(duì)基于k-means算法的離群點(diǎn)檢測(cè)(KM-OD算法)、基于布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)(CS-KM-OD算法)和本文的基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)(ICS-KM-OD算法)進(jìn)行仿真實(shí)驗(yàn)。其中CS-KM-OD算法中的鳥巢發(fā)現(xiàn)概率Pa=0.25，步長(zhǎng)因子α=1，鳥巢規(guī)模為20，迭代次數(shù)為20。3種算法分別在各數(shù)據(jù)集上運(yùn)行10次。在此基礎(chǔ)上計(jì)算出各算法在各數(shù)據(jù)集上的適應(yīng)度值、運(yùn)行時(shí)間以及精確度。

由表7可知，從整體分析這3種算法在3個(gè)數(shù)據(jù)集上的收斂性，本文的ICS-KM-OD算法的適應(yīng)度函數(shù)值較大并且波動(dòng)范圍小。與KM-OD算法相比，無(wú)論是在低維數(shù)據(jù)集Iris上還是在高維數(shù)據(jù)集Wine和Synthetic上，本文算法的檢測(cè)效果都有明顯的提高。對(duì)比CS-KM-OD算法，雖然適應(yīng)度函數(shù)值相差不大，但也有所提高，這是由于本文算法在搜索過(guò)程中考慮了鳥巢本身的特性——適應(yīng)度高的鳥巢周圍更容易發(fā)現(xiàn)最優(yōu)鳥巢，在鳥巢的更新過(guò)程中加入了自適應(yīng)發(fā)現(xiàn)概率和步長(zhǎng)，有效地控制了算法前后期的搜索范圍和搜索速度，提高了搜索精度，使得算法的尋優(yōu)能力更好。由表8可以看出，本文的ICS-KM-OD算法在運(yùn)行時(shí)間上和CS-KM-OD算法相當(dāng)，但卻優(yōu)于KM-OD算法，主要是因?yàn)楸疚乃惴ㄟ\(yùn)用了萊維飛行搜索機(jī)制，算法的參數(shù)少，結(jié)構(gòu)簡(jiǎn)單，有更快的計(jì)算速度。

表8 在3個(gè)數(shù)據(jù)集上各算法的平均運(yùn)行時(shí)間對(duì)比 單位：s

表7 在3個(gè)數(shù)據(jù)集上各算法的適應(yīng)度值對(duì)比

由表9可以看出，從3個(gè)數(shù)據(jù)集上的算法精確度的角度分析，本文提出的ICS-KM-OD算法得到了較好的檢測(cè)精確度，相比于KM-OD算法的效果最為明顯，在3個(gè)數(shù)據(jù)集上精確度分別提高了12.1個(gè)百分點(diǎn)、4.6個(gè)百分點(diǎn)和5.3個(gè)百分點(diǎn)。對(duì)比CS-KM-OD算法，在數(shù)據(jù)集Iris上改善效果最好，提高了2.2個(gè)百分點(diǎn)，其次是數(shù)據(jù)集Synthetic，增加了1.2個(gè)百分點(diǎn)。這是由于KM-OD算法容易受到初始聚類中心的影響，導(dǎo)致最終結(jié)果波動(dòng)性大造成的。而本文提出的ICS-KN-OD算法在一定程度上消除了算法對(duì)初始聚類中心的敏感度，從而提高了算法精確度。

表9 算法精確度對(duì)比

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

本文利用布谷鳥搜索解決了傳統(tǒng)k-means算法的離群點(diǎn)檢測(cè)易受初始聚類中心的影響陷入局部最優(yōu)的問(wèn)題。首先，對(duì)原始的布谷鳥搜索進(jìn)行自適應(yīng)改進(jìn)，并且討論了改進(jìn)后的布谷鳥搜索算法的收斂性問(wèn)題，同時(shí)對(duì)改進(jìn)后的布谷鳥搜索算法進(jìn)行實(shí)驗(yàn)仿真，結(jié)果表明，改進(jìn)后的算法有效地均衡了算法運(yùn)行前后期的搜素范圍和精度，提高了算法的收斂速度。其次將改進(jìn)后的布谷鳥搜索算法與傳統(tǒng)的k-means算法的離群點(diǎn)檢測(cè)融合，提出了一種基于改進(jìn)布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)。最后將本文提出的離群點(diǎn)檢測(cè)算法與基于k-means算法的離群點(diǎn)檢測(cè)算法及基于布谷鳥搜索的k-means算法的離群點(diǎn)檢測(cè)算法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)仿真，結(jié)果驗(yàn)證了本文的算法無(wú)論在收斂速度還是檢測(cè)精度上都優(yōu)于其他2種離群點(diǎn)檢測(cè)算法。