基于模糊聚類處理月亮型數(shù)據(jù)的研究與實(shí)現(xiàn)

侯冀超 謝成心 孟凡興 溫秀梅,2*

(1.河北建筑工程學(xué)院，河北 張家口 075000；2.張家口市大數(shù)據(jù)技術(shù)創(chuàng)新中心，河北 張家口 075000)

0 引 言

傳統(tǒng)K-Means算法屬于劃分聚類，通過(guò)提前設(shè)定聚類數(shù)目不斷迭代聚類中心直到滿足迭代條件.隨著模糊集理論的發(fā)展，RusPini提出了模糊劃分的概念，針對(duì)不同領(lǐng)域的應(yīng)用，在K-Means算法的基礎(chǔ)上，提出了模糊聚類.模糊聚類應(yīng)用于多個(gè)領(lǐng)域，如天氣預(yù)報(bào)、農(nóng)業(yè)、林業(yè)以及圖像分割等.

模糊聚類與K-Means最大的不同在于K-Means聚類算法嚴(yán)格計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的簇歸屬，非此即彼的關(guān)系體現(xiàn)了硬聚類的思想.但是現(xiàn)實(shí)數(shù)據(jù)中，并非如此，模糊聚類通過(guò)對(duì)聚類中心的不確定描述，更加客觀地反應(yīng)了數(shù)據(jù)的歸屬，在各個(gè)領(lǐng)域的應(yīng)用中，模糊的概念更真實(shí)地反應(yīng)客觀世界，從而成為聚類分析的主流.因此模糊聚類引入了“隸屬度”的概念，使得數(shù)據(jù)中的對(duì)象可以同屬于多個(gè)簇，屬于軟聚類的思想.

FCM聚類算法通過(guò)不斷迭代聚類中心、隸屬度以及目標(biāo)函數(shù)J，得到最優(yōu)的聚類結(jié)果.王玲等人提出了一種基于密度的模糊自適應(yīng)聚類算法(A density-based Fuzzy adaptive clustering algorithm,DFAC)，通過(guò)計(jì)算全局的自適應(yīng)半徑，根據(jù)有效性指標(biāo)(|V(k)-V(k-1)|<ε)確定最優(yōu)的聚類中心個(gè)數(shù)以及聚類中心點(diǎn)的位置.其次通過(guò)分別更新聚類中心和隸屬度矩陣以及目標(biāo)函數(shù)J，直到滿足迭代條件(|J(t)-J(t-1)|<ε)得到更新t次后的最佳聚類結(jié)果.然而，通過(guò)不斷迭代聚類中心以及隸屬度的思想對(duì)處理月亮型數(shù)據(jù)集表現(xiàn)欠佳，故本文提出基于模糊類中心點(diǎn)的近鄰點(diǎn)擴(kuò)展聚類算法，結(jié)合了FCM以及密度聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)的思想.

本文算法設(shè)計(jì)思想為：首先通過(guò)不斷迭代聚類中心以及隸屬度，直到隸屬度不再發(fā)生較大的變化，從而得到最優(yōu)聚類中心以及隸屬度，其次利用DBSCAN的點(diǎn)擴(kuò)展思想，利用最優(yōu)的聚類中心點(diǎn)的近鄰點(diǎn)進(jìn)行鄰域擴(kuò)展，將擴(kuò)展的樣本點(diǎn)劃分到同一簇內(nèi)，最終得到聚類結(jié)果，實(shí)驗(yàn)研究結(jié)果可以成功將月亮型數(shù)據(jù)進(jìn)行劃分，解決了FCM算法以及DFAC算法對(duì)月亮型數(shù)據(jù)表現(xiàn)較差的問(wèn)題.下面圍繞相關(guān)概念以及本文所提思想、操作步驟、實(shí)驗(yàn)結(jié)果進(jìn)行說(shuō)明.

1 相關(guān)知識(shí)

1.1 基本概念

密度聚類以及模糊聚類的基本概念如下所述：

定義①：ε-鄰域是指存在xi∈數(shù)據(jù)集R，其ε-鄰域指數(shù)據(jù)集R中與xi距離小于ε的樣本個(gè)數(shù)，即N-ε(xi)={xi∈R | dist(xi,xj)<=ε，(dist表示兩點(diǎn)之間的距離)}.

定義②：隸屬度是指對(duì)論域內(nèi)，U中的任意對(duì)象x，存在數(shù)A(x)∈[0～1]與對(duì)象相等，則A是U上的模糊集，A(x)為x對(duì)A的隸屬度.A(x)相當(dāng)于函數(shù)，當(dāng)A(x)→1，則隸屬度越高，反之越低.

定義③：密度可達(dá)、相連是指對(duì)xi與xj，存在樣本p1～pn，p1=xi、pn=xj且pi+1由pi密度直達(dá)，則xi由xj密度可達(dá).若有xi和xj均與xk密度可達(dá)，則xi與xj密度相連.

1.2 FCM算法

FCM屬于劃分聚類，主要思想是將對(duì)象劃分到同一簇內(nèi)，同一簇內(nèi)對(duì)象相似度高，反之，相似度小.通過(guò)“隸屬度”判斷對(duì)象的歸屬.模糊聚類FCM首先對(duì)是否超過(guò)最大迭代次數(shù)進(jìn)行判斷，若滿足迭代條件，則返回聚類結(jié)果，若不滿足，則繼續(xù)計(jì)算聚類中心C(k)，以及更新隸屬度矩陣u(k+1)，判斷是否滿足迭代條件，若滿足，返回聚類結(jié)果，若不滿足，則令迭代次數(shù)加一.

2 NNE-FC算法相關(guān)概念

2.1 NNE-FC算法思想設(shè)計(jì)

本文借鑒了FCM和DBSCAN聚類算法的思想，首先不斷迭代聚類中心點(diǎn)Ck與隸屬度矩陣Uk直到滿足迭代條件，其次通過(guò)最優(yōu)的聚類中心點(diǎn)搜尋與類中心點(diǎn)距離最近的對(duì)象，對(duì)搜尋到的對(duì)象進(jìn)行鄰域擴(kuò)展，以聚類中心點(diǎn)到最近點(diǎn)的距離為鄰域半徑(Eps)，將鄰域內(nèi)不小于Minpts的數(shù)據(jù)點(diǎn)進(jìn)行鄰域擴(kuò)展，將擴(kuò)展后的數(shù)據(jù)劃分到同一簇內(nèi)，最終得到聚類結(jié)果，通過(guò)調(diào)整蘭德系數(shù)(Adjusted Rand index)對(duì)模型進(jìn)行性能評(píng)估，蘭德系數(shù)的取值范圍為[0,1]，值越大，聚類結(jié)果與真實(shí)結(jié)果越吻合.基于模糊類中心點(diǎn)最近點(diǎn)擴(kuò)展聚類算法的主要步驟如下：

①初始化隸屬度矩陣uij

(a)更新聚類中心點(diǎn)C(k)；

(b)更新隸屬度矩陣uij(k+1)；

(c)重復(fù)(a)、(b)步驟直到滿足迭代終止條件，得到最終聚類中心點(diǎn)C；

②對(duì)聚類中心點(diǎn)C進(jìn)行逐步擴(kuò)展

(d)計(jì)算聚類中心點(diǎn)與最近點(diǎn)之間的距離εi；

(e)以距離εi為半徑作圓，將ε-鄰域內(nèi)不小于Minpts的對(duì)象進(jìn)行擴(kuò)展，將擴(kuò)展的對(duì)象劃分到同一簇內(nèi)；

(f)重復(fù)(d)、(e)步驟直到聚類中心點(diǎn)C處理完畢.

2.2 初始化隸屬度矩陣以及更新隸屬度u

輸入超參數(shù)提前設(shè)定聚類中心的數(shù)目確定初始化隸屬度矩陣，以每個(gè)數(shù)據(jù)點(diǎn)對(duì)聚類中心點(diǎn)的隸屬度進(jìn)行隨機(jī)分配，其中，每個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的各個(gè)聚類中心點(diǎn)之和為1.公式為：

(1)

式中，m為數(shù)據(jù)點(diǎn)的個(gè)數(shù)，n為聚類中心的個(gè)數(shù).

通過(guò)引入拉格朗日約束條件得到更新的隸屬度uij公式：

(2)

式中，uij為xi與cj更新的隸屬度，m為超參數(shù)，是提前設(shè)定的聚類中心個(gè)數(shù).當(dāng)(xi-cj)越小時(shí)，即點(diǎn)xi距離聚類中心點(diǎn)cj越近時(shí)，分母變小，整體隸屬度uij越大.

2.3 聚類中心點(diǎn)c

通過(guò)引入拉格朗日約束條件得到更新的聚類中心點(diǎn)cj公式：

(3)

式中，n為數(shù)據(jù)集中對(duì)象的個(gè)數(shù)，uij為xi與cj之間的隸屬度，cj為第j個(gè)聚類中心點(diǎn).m為超參數(shù).

2.4 迭代終止條件

在不滿足超參數(shù)所設(shè)置的最大迭代次數(shù)Iter_num(默認(rèn)為100)時(shí)，迭代的終止條件為：

maxij{|uij(k+1)-uij(k)|}≤δ

(4)

式中，δ為超參數(shù)，uij(k)為第k次迭代的隸屬度.

2.5尋找cj的自適應(yīng)半徑

通過(guò)達(dá)到迭代終止條件獲取到最優(yōu)的聚類中心點(diǎn)cj后，計(jì)算與聚類中心點(diǎn)cj距離最近的數(shù)據(jù)點(diǎn)xi，則自適應(yīng)半徑公式為：

(5)

式中，n為數(shù)據(jù)中對(duì)象個(gè)數(shù)，cj為第j個(gè)聚類中心點(diǎn)，xi為數(shù)據(jù)中的對(duì)象，delta為超參數(shù).

2.6 鄰域查詢

以自適應(yīng)半徑作圓，將鄰域內(nèi)不小于Minpts個(gè)數(shù)的對(duì)象放入鄰域內(nèi)，逐步對(duì)鄰域內(nèi)的對(duì)象進(jìn)行擴(kuò)展，將擴(kuò)展得到的對(duì)象劃分到同一簇內(nèi)，直到鄰域內(nèi)的對(duì)象查詢完畢.

2.7 基于模糊類中心點(diǎn)最近點(diǎn)擴(kuò)展聚類算法偽代碼

基于模糊類中心點(diǎn)最近點(diǎn)擴(kuò)展聚類算法偽代碼如下所示.其中，D表示數(shù)據(jù)集，clust_num表示要聚類中心點(diǎn)的數(shù)目，iter_num表示最大迭代次數(shù)，delta表示擴(kuò)充聚類中心點(diǎn)鄰域半徑，Minpts表示核心點(diǎn)的閾值，即形成簇所需的最小核心點(diǎn)數(shù)目，m為計(jì)算uij與cj的超參數(shù)，C_last表示最優(yōu)的聚類中心點(diǎn)，cluster表示對(duì)象所在的簇.

Input：D，clust_num，iter_num，delta，Minpts，m

Output：C_last，cluster

Func NNE-FC(D,clust_num,iter_num,delta,Minpts,m)

{

//計(jì)算最優(yōu)聚類中心點(diǎn)C_last

Initial_U

while there have iter_num to circulated{

cj= Cen_Iter from uijm,xi

uij= U_Iter from xi,cj,ck,m

until maxij{|uijk+1-uijk|}<=δ

} return C_last

while len(C_last){

//計(jì)算自適應(yīng)半徑eps與鄰近點(diǎn)C_last_nearobj

C_last_nearobj = utilizing sklearn.KDTree

eps = (C_last_eps utilizing (sklearn.KDTree,C_last_nearobj) from D , C_last) + delta

expand C_last_nearobj if (points <= eps)

}return cluster

}

end

3 實(shí)驗(yàn)環(huán)境與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

本文提出的NNE-FC是通過(guò)Python語(yǔ)言在Anaconda環(huán)境中實(shí)現(xiàn)的，由matplotlib庫(kù)繪圖與Excel實(shí)現(xiàn)實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)環(huán)境：CPU為Intel(R)Core(TM)I5-7200U@2.5GHZ 2.71 GHZ，RAM為8.00GB(7.88GB可用).實(shí)驗(yàn)結(jié)果分別對(duì)FCM、DFAC算法以及本文算法進(jìn)行了實(shí)驗(yàn)對(duì)比，對(duì)比數(shù)據(jù)在相同、公平且參數(shù)相同的環(huán)境下進(jìn)行實(shí)驗(yàn).

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

實(shí)驗(yàn)為驗(yàn)證本文算法NNE-FC對(duì)數(shù)據(jù)集的通用性以及對(duì)月亮型數(shù)據(jù)集的聚類效果.實(shí)驗(yàn)一驗(yàn)證本文算法對(duì)數(shù)據(jù)集通用性；實(shí)驗(yàn)二驗(yàn)證算法NNE-FC對(duì)數(shù)據(jù)較少的月亮型數(shù)據(jù)集的聚類效果；實(shí)驗(yàn)三驗(yàn)證算法NNE-FC對(duì)數(shù)據(jù)中含有高斯噪聲標(biāo)準(zhǔn)差的月亮型數(shù)據(jù)集的聚類效果.其中，實(shí)驗(yàn)中“黑色圓點(diǎn)(·)”代表原始散點(diǎn)圖，“彩色圓點(diǎn)”代表同一簇內(nèi)的數(shù)據(jù)點(diǎn)，“★”代表聚類中心點(diǎn).

實(shí)驗(yàn)一采用sklearn.make_blobs數(shù)據(jù)集，共50個(gè)數(shù)據(jù)點(diǎn)，真實(shí)標(biāo)簽應(yīng)分為三類.由于DFAC算法因自適應(yīng)確定簇的數(shù)目，故將簇分為兩類，圖1(c)DFAC的蘭德系數(shù)為0.5689，聚類結(jié)果較差.FCM聚類算法與本文NNE-FC算法因輸入超參數(shù)確定簇的數(shù)目，成功將數(shù)據(jù)集識(shí)別為三類，圖1中(b)FCM與(d)NNE-FC的蘭德系數(shù)均為0.9399，聚類效果良好，但仍會(huì)將部分對(duì)象進(jìn)行錯(cuò)誤劃分，見(jiàn)圖1.

圖1 實(shí)驗(yàn)一聚類結(jié)果

實(shí)驗(yàn)二采用sklearn.make_moons數(shù)據(jù)較少的數(shù)據(jù)集，共20個(gè)數(shù)據(jù)點(diǎn)，數(shù)據(jù)中高斯噪聲的標(biāo)準(zhǔn)差“noise”為0，真實(shí)標(biāo)簽應(yīng)分為兩類.FCM算法與DFAC算法對(duì)月亮型數(shù)據(jù)集聚類結(jié)果較差，圖2中(b)FCM與(c)DFAC的蘭德系數(shù)均為0.1133，而本文NNE-FC聚類算法成功將月亮型數(shù)據(jù)集進(jìn)行劃分，圖2中(d)NNE-FC的蘭德系數(shù)為1.0，聚類效果良好，見(jiàn)圖2.

圖2 實(shí)驗(yàn)二聚類結(jié)果

實(shí)驗(yàn)三采用sklearn.make_moons數(shù)據(jù)集，共400個(gè)數(shù)據(jù)點(diǎn)，數(shù)據(jù)中高斯噪聲的標(biāo)準(zhǔn)差“noise”為0.05，真實(shí)標(biāo)簽應(yīng)分為兩類.本文算法與FCM算法進(jìn)行對(duì)比，結(jié)果顯示本文NNE-FC聚類算法能夠?qū)υ铝列蛿?shù)據(jù)進(jìn)行識(shí)別，圖3中(b)FCM算法的蘭德系數(shù)為0.2431，而(c)NNE-FC的蘭德系數(shù)為1.0，聚類結(jié)果良好，見(jiàn)圖3.

圖3 實(shí)驗(yàn)三聚類結(jié)果

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

本文所提出的NNE-FC結(jié)合了FCM算法與DBSCAN算法的思想，繼承了FCM與DBSCAN算法的優(yōu)勢(shì)，不僅可以識(shí)別多密度數(shù)據(jù)集，且對(duì)月亮型數(shù)據(jù)集的處理也有較好的聚類結(jié)果，改進(jìn)了傳統(tǒng)的FCM聚類算法無(wú)法識(shí)別月亮型數(shù)據(jù)集的問(wèn)題.本文算法需要輸入的超參數(shù)較多，對(duì)超參數(shù)的最佳選擇仍有待提高，下一步將重點(diǎn)研究如何通過(guò)自適應(yīng)或決策圖的方式確定超參數(shù)的選擇，進(jìn)一步優(yōu)化超參數(shù)的選擇.