蔣 華，季 豐，王慧嬌，王 鑫，羅一迪

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541000)

0 引 言

近十幾年來(lái)我國(guó)海洋監(jiān)測(cè)領(lǐng)域有了長(zhǎng)足發(fā)展，獲取了大量Argo浮標(biāo)監(jiān)測(cè)數(shù)據(jù)。但是據(jù)Argo資料的應(yīng)用研究顯示，Argo浮標(biāo)由于自身所攜帶的電導(dǎo)率傳感器，在運(yùn)行過(guò)程中由于系統(tǒng)漂移而導(dǎo)致出現(xiàn)錯(cuò)誤的監(jiān)測(cè)數(shù)據(jù)，需要在海洋Argo浮標(biāo)監(jiān)測(cè)數(shù)據(jù)處理過(guò)程中盡可能的將異常數(shù)據(jù)剔除。

在“無(wú)監(jiān)督學(xué)習(xí)”(unsupervised learning)中，Kmeans算法是應(yīng)用最廣研究最多的聚類算法之一。研究者們?cè)趥鹘y(tǒng)Kmeans基礎(chǔ)上提出了許多改進(jìn)算法，如MinMaxKmeans算法[1]、KMOR算法[2]、Seeded-KMeans[3]和IWO-KMeans算法[4]等，聚類效果相較于傳統(tǒng)算法有了明顯改善，在此基礎(chǔ)上進(jìn)行的異常值檢效率也更高。文獻(xiàn)[5-10]提出了K模式聚類的兩種不同的初始化算法，但不能保證初始中心點(diǎn)均勻分布，且算法復(fù)雜度較高。文獻(xiàn)[11-13]提出了3種分階段聚類方法，但時(shí)間復(fù)雜度高，人為設(shè)置約束信息使聚類變成有監(jiān)督聚類。聚類和異常檢測(cè)[14,15]作為數(shù)據(jù)挖掘的兩個(gè)重要研究方向，可以很自然地結(jié)合起來(lái)共同研究。

為解決海洋Argo浮標(biāo)數(shù)據(jù)中存在異常值問(wèn)題，第一步，提出DMKmeans算法，通過(guò)計(jì)算給定鄰域范圍內(nèi)數(shù)據(jù)點(diǎn)密度值，按密度值大小降序排列數(shù)據(jù)集，剔除低于平均密度值的數(shù)據(jù)點(diǎn)。排除密度稀疏點(diǎn)，在剩下的數(shù)據(jù)點(diǎn)中選取初始聚類中心點(diǎn)。第二步，基于DMKmeans算法對(duì)海洋監(jiān)測(cè)數(shù)據(jù)進(jìn)行異常檢測(cè)研究，根據(jù)數(shù)據(jù)點(diǎn)距離所在簇簇心的最近距離與平均距離比較，結(jié)合數(shù)學(xué)模型來(lái)判斷異常點(diǎn)。DMKmeans算法優(yōu)化了傳統(tǒng)Kmeans算法選取初始中心點(diǎn)的方法，降低了聚類迭代次數(shù)并達(dá)到全局最優(yōu)結(jié)果，有效提高海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)率。

1 相關(guān)理論研究

1.1 傳統(tǒng)Kmeans算法

傳統(tǒng)的Kmeans算法是“無(wú)監(jiān)督學(xué)習(xí)”算法，即對(duì)未標(biāo)記的數(shù)據(jù)集進(jìn)行聚類分析。算法思想：首先隨機(jī)選取k個(gè)初始聚類中心，每一個(gè)聚類中心代表一類數(shù)據(jù)集簇；然后將數(shù)據(jù)點(diǎn)劃分到最近的數(shù)據(jù)簇；重新計(jì)算數(shù)據(jù)簇中心點(diǎn)，直到聚類準(zhǔn)則函數(shù)收斂。收斂函數(shù)定義請(qǐng)參見(jiàn)文獻(xiàn)[15]，函數(shù)如下

(1)

式中：E為Kmeans算法針對(duì)樣本D={x1,x2,…,xk}聚類所得簇C={C1,C2,…,Ck}劃分的最小化平方誤差，ui表示為

(2)

式中：ui是簇Ci的均值向量。直觀來(lái)看，式(1)在一定程度上刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，通常E值越小則簇內(nèi)樣本相似度越高。

Kmeans算法描述見(jiàn)表1。

表1 Kmeans算法描述

傳統(tǒng)的Kmeans算法對(duì)于大量數(shù)據(jù)集聚類有一定的效果，是研究者廣泛研究的聚類算法之一，仍然存在初始聚類中心點(diǎn)的隨機(jī)選定造成聚類結(jié)果局部最優(yōu)問(wèn)題。

1.2 密度分布函數(shù)

在數(shù)據(jù)空間Rd中，存在數(shù)據(jù)對(duì)象x和x′，數(shù)據(jù)點(diǎn)x′對(duì)數(shù)據(jù)點(diǎn)x的影響函數(shù)定義為DensityB(x,x′)，本質(zhì)上該影響函數(shù)由兩個(gè)數(shù)據(jù)點(diǎn)之間的距離決定，如歐氏距離函數(shù)。高斯函數(shù)是經(jīng)典的影響函數(shù)，其定義如下

(3)

而數(shù)據(jù)點(diǎn)x的密度函數(shù)則是鄰域參數(shù)δ范圍內(nèi)所有最近鄰居對(duì)其影響函數(shù)之和，即若給定n個(gè)數(shù)據(jù)對(duì)象X=(x1,x2,…,xn)對(duì)于數(shù)據(jù)點(diǎn)x的密度函數(shù)可定義如下

(4)

式中：xi∈X,d(x,xi)為數(shù)據(jù)點(diǎn)x到其第i個(gè)最近鄰點(diǎn)的最小距離，直觀的通過(guò)密度函數(shù)式(3)可以看出d(x,xi)值越小Density(x)的值越大則數(shù)據(jù)點(diǎn)x的密度越大。

1.3 貝塞爾公式

貝塞爾公式是常用的標(biāo)準(zhǔn)偏差δ估計(jì)方法，在實(shí)際應(yīng)用常常是對(duì)有限的數(shù)據(jù)樣本量做標(biāo)準(zhǔn)偏差估計(jì)，但由于它并不是一個(gè)總體的標(biāo)準(zhǔn)偏差而只是一個(gè)近似估計(jì)值，因此用s表示

(5)

1.4 拉伊達(dá)準(zhǔn)則

在整理聚類結(jié)果數(shù)據(jù)時(shí)，往往會(huì)發(fā)現(xiàn)總有一些數(shù)據(jù)會(huì)存在偏差較大或者分布較為突出的數(shù)據(jù)，這些數(shù)據(jù)很可能是異常值(Outliers)或噪音數(shù)據(jù)，拉伊達(dá)準(zhǔn)則主要用以判別這些數(shù)據(jù)是否異常值從而可以決定是否保留這些數(shù)據(jù)。若存在一組聚簇樣本D=(x1,x2,…,xn)，算出其在某一準(zhǔn)則如距離簇心最近距離下的平均值x以及待檢測(cè)數(shù)據(jù)元素的值xv，若是能夠符合下列關(guān)系

Tabn=|xv-x|≥3s

(6)

則判斷其為異常值點(diǎn)，其中s值為該樣本的標(biāo)準(zhǔn)偏差估計(jì)，可通過(guò)式(5)計(jì)算得出。

2 基于DMKmeans算法的異常檢測(cè)

2.1 DMKmeans算法

在本文的第二部分相關(guān)理論研究中，對(duì)傳統(tǒng)Kmeans算法進(jìn)行深入研究，該算法快速簡(jiǎn)單容易實(shí)現(xiàn)，對(duì)于大量數(shù)據(jù)集有較好的聚類效果，自行優(yōu)化迭代次數(shù)比較適合大型數(shù)據(jù)集等優(yōu)點(diǎn)。但同時(shí)也存在一些缺點(diǎn)，最主要的是初始聚類中心的隨機(jī)選擇可能使聚類效果受到離群數(shù)據(jù)的影響，造成聚類結(jié)果的局部最優(yōu)而非全局最優(yōu)。針對(duì)Kmeans算法的這些不足提出了DMKmeans算法，計(jì)算Rd空間上數(shù)據(jù)集X中的每一個(gè)數(shù)據(jù)點(diǎn)x在給定鄰域半徑δ范圍內(nèi)的最近鄰居點(diǎn)集合G(x)，計(jì)算數(shù)據(jù)點(diǎn)x的密度函數(shù)Density(x)得到其密度值，并且按照升序放入集合X′中，剔除密度值小于平均密度值的數(shù)據(jù)點(diǎn)，從集合X′中選出密度值最大的數(shù)據(jù)點(diǎn)為聚類中心點(diǎn)，以選定的初始聚類中心點(diǎn)開始聚類，這樣聚類結(jié)果相對(duì)穩(wěn)定并可以保證全局最優(yōu)。

DMKmeans算法步驟如下：

(1)在空間Rd上的數(shù)據(jù)集X={x1,x2,…,xn}中的每一個(gè)數(shù)據(jù)點(diǎn)xi,其中xi∈X，計(jì)算其在給定鄰域半徑δ內(nèi)的最近鄰集合Gk(xi)，即d(xi,xj)≤δ且xj∈Gk(xi)，其中k為xi在鄰域范圍內(nèi)最近鄰數(shù)據(jù)點(diǎn)個(gè)數(shù)；

(2)計(jì)算數(shù)據(jù)點(diǎn)xi的密度函數(shù)值

(7)

式中：xj∈Gk(xi)，當(dāng)xi在鄰域范圍內(nèi)的最近鄰點(diǎn)xij的密度值小于平均密度值時(shí)，即滿足下列條件

(8)

則將數(shù)據(jù)點(diǎn)xij視為稀疏數(shù)據(jù)并剔除掉，從而得到密集點(diǎn)集合X′；

(3)從密集點(diǎn)集合X′中，選取密度值最大的點(diǎn)Densitymax(x)，為第一個(gè)初始聚類中心C1；然后取距離C1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第二個(gè)聚類中心C2；對(duì)于第s個(gè)中心點(diǎn)的選取則是滿足如下條件的數(shù)據(jù)點(diǎn)xs且xs∈X′，取滿足xs與以選中的聚類中心Cs的距離值最小的數(shù)據(jù)點(diǎn)作為中心點(diǎn)，即max(dmin(xs,C1),dmin(xs,C2),…,dmin(xs,Cs-1))其中3≤s≤k，直到最終得到所需k個(gè)初始聚類中心點(diǎn)，并代表k個(gè)類簇ωl,l∈(1,…,k)；

(4)計(jì)算數(shù)據(jù)集X中數(shù)據(jù)點(diǎn)xi至各個(gè)聚類中心點(diǎn)的歐氏距離

(9)

式中：i=1,2,…,n且j=1,2,…,k；如果d(xi,Cj)為最小距離值，則將數(shù)據(jù)點(diǎn)xi歸入中心點(diǎn)Cj所代表的數(shù)據(jù)簇ωj中，重復(fù)該過(guò)程直到最終聚類完成；

DMKmeans算法，使用密度函數(shù)來(lái)計(jì)算出數(shù)據(jù)集中各個(gè)數(shù)據(jù)點(diǎn)的密度值，結(jié)合最遠(yuǎn)距離原則在高密度數(shù)據(jù)集合中選取初始中心保證其均勻分布，避免噪音數(shù)據(jù)對(duì)取定初始聚類中心的影響，使聚類迭代過(guò)程從數(shù)據(jù)高密度區(qū)域出發(fā)，有效提高迭代效率，減少迭代次數(shù)。

2.2 基于DMKmeans算法的異常檢測(cè)

(10)

算法過(guò)程如下：

(1)設(shè)置空間Rd上的數(shù)據(jù)集X中數(shù)據(jù)點(diǎn)的鄰域半徑δ值；

(2)在空間Rd上的數(shù)據(jù)集X={x1,x2,…,xn}中的每一個(gè)數(shù)據(jù)點(diǎn)xi，其中xi∈X，計(jì)算其在給定鄰域半徑δ內(nèi)的最近鄰集合Gk(xi)，即d(xi,xj)≤δ且xj∈Gk(xi)，其中k為xi在鄰域范圍內(nèi)最近鄰數(shù)據(jù)點(diǎn)個(gè)數(shù)；

(3)據(jù)點(diǎn)xi的密度函數(shù)值

(11)

式中：xj∈Gk(xi)，當(dāng)xi在鄰域范圍內(nèi)的最近鄰點(diǎn)xij的密度值小于平均密度值時(shí)，滿足下列條件

(12)

則將數(shù)據(jù)點(diǎn)xij視為稀疏數(shù)據(jù)并剔除掉，從而得到密集點(diǎn)集合X′；

(4)從密集點(diǎn)集合X′中，選取密度值最大的點(diǎn)Densitymax(x)，為第一個(gè)初始聚類中心C1；然后取距離C1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第二個(gè)聚類中心C2；對(duì)于第s個(gè)中心點(diǎn)的選取則是滿足如下條件的數(shù)據(jù)點(diǎn)xs且xs∈X′，即max(dmin(xs,C1),dmin(xs,C2),…,dmin(xs,Cs-1))其中3≤s≤k，直到最終得到所需k個(gè)初始聚類中心點(diǎn)，并代表k個(gè)類簇ωl,l∈(1,…,k)；

(5)計(jì)算數(shù)據(jù)集X中數(shù)據(jù)點(diǎn)xi至各個(gè)聚類中心點(diǎn)的歐氏距離

(13)

式中：i=1,2,…,n且j=1,2,…,k；如果d(xi,Cj)為最小距離值，則將數(shù)據(jù)點(diǎn)xi歸入中心點(diǎn)Cj所代表的數(shù)據(jù)簇ωj中，計(jì)算其最小化平方誤差E，并對(duì)ωj中所有數(shù)據(jù)點(diǎn)計(jì)算距離均值從而得到新的聚類中心點(diǎn)；

(6)重復(fù)過(guò)程(5)直到聚類準(zhǔn)則函數(shù)收斂，即前后兩次迭代所得出式(1)中E的值的差小于等于閾值η即|E-E′|≤η，聚類中心點(diǎn)不再改變，至此聚類過(guò)程結(jié)束，得出聚類結(jié)果；

(7)計(jì)算最終數(shù)據(jù)簇ωp中數(shù)據(jù)點(diǎn)xi到簇心Cp的平均距離

(14)

(8)若待觀察序列U中的數(shù)據(jù)點(diǎn)xa∈U到簇心的距離值da滿足條件

(15)

則判定該數(shù)據(jù)點(diǎn)為異常點(diǎn)，將其保留在數(shù)據(jù)集U中，否則的話將不滿足條件的數(shù)據(jù)點(diǎn)放回原來(lái)聚類數(shù)據(jù)簇中，重復(fù)上述過(guò)程直到最終異常值檢測(cè)完成并輸出異常值點(diǎn)。

基于DMKmeans算法的數(shù)據(jù)異常檢測(cè)算法，在全局最優(yōu)聚類結(jié)果基礎(chǔ)上使用拉伊達(dá)準(zhǔn)則，貝塞爾公式等數(shù)學(xué)模型來(lái)進(jìn)行數(shù)據(jù)異常檢測(cè)，異常檢測(cè)率較高。

3 實(shí)驗(yàn)及結(jié)果分析

通過(guò)DMKmeans算法與傳統(tǒng)Kmeans算法以及MinMaxKmeans算法的海洋監(jiān)測(cè)數(shù)據(jù)仿真實(shí)驗(yàn)對(duì)比，驗(yàn)證算法的可靠性和穩(wěn)定性，實(shí)驗(yàn)評(píng)估指標(biāo)主要有運(yùn)行平均時(shí)間、迭代次數(shù)、聚類準(zhǔn)確率、異常檢測(cè)率等。

實(shí)驗(yàn)環(huán)境：Matlab2016a、Windows7 64 bit、CUP 2.67 GHz、內(nèi)存6 G。所使用數(shù)據(jù)集為海洋Argo浮標(biāo)監(jiān)測(cè)數(shù)據(jù)集，數(shù)據(jù)來(lái)源于中國(guó)Argo實(shí)時(shí)資料中心公開數(shù)據(jù)集。實(shí)驗(yàn)參數(shù)δ=0.5，K=5，η=0.01。

圖1為本文所提DMKmeans算法海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)，圖2為MinMaxKmeans算法海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)，圖3為傳統(tǒng)Kmeans算法海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)，以上3個(gè)實(shí)驗(yàn)圖形中均有5個(gè)聚類數(shù)據(jù)簇，其中‘+’代表檢測(cè)出的異常點(diǎn)。與其它兩種對(duì)比算法相比較，DMKmeans算法在聚類效果上聚類數(shù)據(jù)簇更加緊密清晰，類簇分布更加均勻，基于DMKmeans算法的海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)相比傳統(tǒng)Kmeans算法以及MinMaxKmeans算法準(zhǔn)確率更高。

圖1 DMKmeans算法異常檢測(cè)

圖2 MinMaxKmeans算法異常檢測(cè)

圖3 傳統(tǒng)Kmeans算法異常檢測(cè)

從表2、表3實(shí)驗(yàn)數(shù)據(jù)可以看出，本文提出的DMKmeans算法在迭代次數(shù)和聚類準(zhǔn)確率上都優(yōu)于MinMaxKmeans算法和傳統(tǒng)Kmeans算法，在此基礎(chǔ)之上所做的海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)，平均運(yùn)行時(shí)間比MinMaxKmeans算法以及傳統(tǒng)Kmeans算法更短，異常檢測(cè)率較其它兩種算法要高。結(jié)合以上仿真實(shí)驗(yàn)結(jié)果和數(shù)據(jù)分析可以得出結(jié)論，DMKmeans算法比MinMaxKmeans算法以及傳統(tǒng)Kmeans算法在聚類和異常檢測(cè)方面更加優(yōu)化，可以滿足實(shí)際應(yīng)用的需求，有助于海洋Argo浮標(biāo)數(shù)據(jù)集聚類以及異常檢測(cè)。

表2 聚類實(shí)驗(yàn)結(jié)果對(duì)比

表3 異常檢測(cè)實(shí)驗(yàn)結(jié)果對(duì)比

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

DMKmeans算法解決了傳統(tǒng)Kmeans算法初始聚類中心隨機(jī)選取造成聚類結(jié)果局部最優(yōu)的問(wèn)題，選擇密度分布較高的數(shù)據(jù)點(diǎn)作為初始聚類中心可以有效排除離群點(diǎn)對(duì)初始聚類的干擾，初始聚類中心均勻分布，減少迭代次數(shù)，使最終聚類結(jié)果全局最優(yōu)，基于DMKmeans算法的海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)可以有效檢測(cè)出海洋Argo浮標(biāo)數(shù)據(jù)集中的異常值。

通過(guò)DMKmeans算法與傳統(tǒng)Kmeans算法及MinMaxKmeans算法的海洋監(jiān)測(cè)數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)對(duì)比分析，DMKmeans算法在運(yùn)行時(shí)間、迭代次數(shù)相比傳統(tǒng)Kmeans算法和MinMaxKmeans算法更少，聚類速度更快，對(duì)異常數(shù)據(jù)檢測(cè)更加穩(wěn)定。DMKmeans算法的聚類準(zhǔn)確率和異常檢測(cè)率高于其它兩種對(duì)比算法。本文提出的DMKmeans算法能更好地檢測(cè)出海洋Argo浮標(biāo)數(shù)據(jù)集中的異常數(shù)據(jù)。隨著大數(shù)據(jù)時(shí)代到來(lái)，使用大數(shù)據(jù)平臺(tái)對(duì)更加海量的數(shù)據(jù)集和高維數(shù)據(jù)集的異常檢測(cè)將會(huì)成為本文下一步研究的重點(diǎn)。