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

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

0 引 言

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

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

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

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

1 相關(guān)知識

1.1 基本概念

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

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

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

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

1.2 FCM算法

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

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

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

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

①初始化隸屬度矩陣uij

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

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

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

②對聚類中心點C進行逐步擴展

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

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

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

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

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

(1)

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

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

(2)

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

2.3 聚類中心點c

通過引入拉格朗日約束條件得到更新的聚類中心點cj公式：

(3)

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

2.4 迭代終止條件

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

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

(4)

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

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

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

(5)

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

2.6 鄰域查詢

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

2.7 基于模糊類中心點最近點擴展聚類算法偽代碼

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

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

Output：C_last，cluster

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

{

//計算最優(yōu)聚類中心點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){

//計算自適應(yīng)半徑eps與鄰近點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 實驗環(huán)境與結(jié)果

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果分析

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

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

圖1 實驗一聚類結(jié)果

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

圖2 實驗二聚類結(jié)果

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

圖3 實驗三聚類結(jié)果

4 結(jié)束語

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