一種結(jié)合自適應近鄰與密度峰值的加權模糊聚類算法

張春昊,解 濱,2,3,張喜梅,徐童童

1(河北師范大學 計算機與網(wǎng)絡空間安全學院,石家莊 050024)

2(河北師范大學 供應鏈大數(shù)據(jù)分析與數(shù)據(jù)安全河北省工程研究中心,石家莊 050024)

3(河北師范大學 河北省網(wǎng)絡與信息安全重點實驗室,石家莊 050024)

1 引 言

聚類,顧名思義即“物以類聚”,其目的是將相似程度高的樣本劃分到同一個簇中,將相似程度低的樣本劃分到不同的簇中[1].聚類作為無監(jiān)督機器學習領域的重要方法,在數(shù)據(jù)挖掘、模式識別、信息檢索和圖像識別等領域有著廣泛的應用[2,3].由于其適用于無標簽數(shù)據(jù)集,且能取得較好的效果,因此一直受到眾多學者的關注和研究.傳統(tǒng)的聚類方法基本可以分為基于密度的聚類方法、基于網(wǎng)格的聚類方法、基于層次的聚類方法、基于模型的聚類方法和基于劃分的聚類方法[4].其中,以DBSCAN[5](density based spatial clustering of application with noise)和DPC[6](clustering by fast search and find of density peaks)為代表的基于密度的聚類算法泛化能力較強.DBSCAN算法在鄰域半徑參數(shù)和核心對象鄰域包含的最少樣本數(shù)設置適當時,能快速發(fā)現(xiàn)任意形狀的類簇,但是如何設置這兩個參數(shù)缺乏理論依據(jù)[7].DPC算法能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點作為聚類中心,然后將剩余樣本分配給密度比它大的最近鄰樣本所在的簇,該算法無需迭代,適用于大規(guī)模數(shù)據(jù)的聚類分析.然而,DPC算法在樣本密度度量方面沒有統(tǒng)一的度量準則,一旦聚類中心選擇錯誤,在剩余樣本分配時容易發(fā)生連帶錯誤[8].基于網(wǎng)格的聚類方法[9]用不同的網(wǎng)格對空間進行劃分,但如何設置網(wǎng)格的粒度缺乏理論依據(jù).層次聚類算法[10]可解釋性較強,但是計算復雜度較高且容易聚類成鏈狀.K-means算法[11]和FCM算法[12]是基于劃分思想的聚類算法,因其算法簡潔,運行速度快而吸引著眾多學者的關注和研究.在傳統(tǒng)的K-means聚類算法中,認為任意一個樣本和簇的關系是屬于或者不屬于的關系,是對樣本的硬劃分,聚類效果具有局限性,而FCM算法認為任意一個樣本和每一個簇之間的關系是多大程度上屬于,任意一個樣本隸屬于所有簇的程度之和為1.該算法通過迭代來最小化目標函數(shù),直到目標函數(shù)改變量小于閾值或迭代次數(shù)達到設定值,則停止迭代,最后,將隸屬度矩陣去模糊化得到樣本屬于每一個簇的確切劃分.因此,FCM算法是基于軟劃分[13]思想,相對于硬劃分更為合理.然而,在傳統(tǒng)的FCM算法中,由于初始聚類中心選取的隨機性影響了聚類結(jié)果的穩(wěn)定,本文將首先針對該問題對FCM聚類算法進行改進.

XI等人為了改進FCM算法對初始聚類中心敏感和易陷入局部最優(yōu)的缺陷[14],將FCM算法和具有較強全局優(yōu)化能力的人工魚群算法相結(jié)合,引入自適應機制,提出了一種基于人工魚群優(yōu)化的模糊C均值聚類算法(AAFSA-FCM)[15],從而提高了收斂速度和聚類效果.然而該算法引入了大量的超參數(shù),且未給出針對不同數(shù)據(jù)集如何調(diào)參才能達到較好的效果的方法,因此算法的泛化能力較弱.唐成華等人[16]將層次聚類和遺傳算法相結(jié)合提出了一種AGFCM算法,首先通過層次聚類算法改善了FCM算法對初始聚類中心敏感的問題,再利用遺傳算法的全局搜索能力克服了其在迭代時容易陷入局部最優(yōu)的缺點.但是由于層次聚類本身的局限性,聚類中心的選取往往偏差較大且遺傳算法同樣引入了大量的超參數(shù).張煜等人[17]提出了一種基于密度峰值的加權猶豫模糊聚類算法(WHFDP),利用密度峰值聚類算法(DPC)中的密度峰值思想來尋找初始聚類中心,用以解決FCM算法對初始聚類中心敏感的問題,但是,該算法在尋找密度峰值過程中需要主觀選擇截斷距離,且針對不同規(guī)模數(shù)據(jù)集需采用不同的樣本密度度量準則,這導致針對不同規(guī)模的數(shù)據(jù)集如何選擇合適的密度度量方式?jīng)]有明確定論.謝娟英等人[8]針對DPC算法中樣本局部密度定義的缺陷,提出一種基于K近鄰優(yōu)化的密度峰值快速搜索聚類算法,算法利用樣本的K近鄰信息定義樣本的局部密度,搜索和發(fā)現(xiàn)樣本的密度峰值,以密度峰值點樣本作為初始聚類中心.但是K近鄰算法的K值仍需要人為設定,針對不同規(guī)模、不同結(jié)構的數(shù)據(jù)集如何選擇合適的K值未給出有效的說明.因此,本文在現(xiàn)有研究基礎上進一步引入了自適應近鄰,根據(jù)每個樣本局部的稠密程度自適應的選擇該樣本的近鄰集合,結(jié)合密度峰值思想提出了一種自適應近鄰密度峰值算法(adaptive nearest neighbors and density peaks, ANNDP),統(tǒng)一了不同數(shù)據(jù)集樣本局部密度的度量方式,在計算局部密度時由于僅需考慮近鄰樣本減少了計算量,且避免了K值的人為給定,提高了模型的泛化能力.

在傳統(tǒng)的FCM算法中忽視了每個樣本對于最終聚類結(jié)果的影響程度不同.LI等人[18]提出了FWCM算法,引入了加權平均的概念重新定義了FCM算法中聚類中心的計算方式,將每個樣本的重要程度按照它對聚類結(jié)果的影響分別對待.HUNG等人[19]在FWCM算法的基礎上提出了NW-FCM算法,與FWCM算法相比,NW-FCM算法包含每個簇的質(zhì)心以提高穩(wěn)定性,該算法比FCM算法和FWCM算法具有更高的分類精度和穩(wěn)定性.但這兩種方法都忽略了樣本不同特征的重要程度對聚類結(jié)果的影響.因此,本文在NW-FCM的基礎上引入了信息熵對樣本的不同特征賦予不同的權重,改進算法的迭代公式,重新定義模糊聚類中心,利用拉格朗日乘子法交替優(yōu)化得到隸屬度矩陣,最后將隸屬度矩陣去模糊化得到最終的聚類結(jié)果.

綜合初始聚類中心的選取和考慮樣本特征及樣本自身重要度,本文提出了一種結(jié)合自適應近鄰和密度峰值思想的基于信息熵加權的模糊聚類算法(weighted fuzzy clustering algorithm combining adaptive nearest neighbors and density peaks, ANNDP-WFCM).算法的改進工作有如下3個方面:1)針對FCM算法對初始聚類中心敏感的問題,提出了一種結(jié)合自適應近鄰的密度峰值算法(ANNDP)來自動搜索初始聚類中心,利用自適應鄰域集合統(tǒng)一了DPC算法中樣本局部密度的度量方式,不僅減少了計算量且針對不同規(guī)模、不同結(jié)構的數(shù)據(jù)集,可以自適應的找到每個樣本的近鄰集合,根據(jù)近鄰信息定義樣本的局部密度,搜索和發(fā)現(xiàn)數(shù)據(jù)集的密度峰值,以密度峰值點樣本作為初始聚類中心;2)針對不同樣本、同一樣本不同的特征對聚類結(jié)果影響不同的問題.在NW-FCM算法的基礎上引入信息熵進行特征賦權,提出了加權模糊聚類算法(WFCM).通過將ANNDP算法得到的初始聚類中心與WFCM算法相結(jié)合,重新定義目標函數(shù)中的模糊聚類中心,改進算法的目標函數(shù),利用拉格朗日乘子法交替尋優(yōu),對最終的隸屬度矩陣去模糊化得到聚類結(jié)果;3)針對輸入初始聚類中心后,模糊聚類中心的求解方法不適用于包含重復樣本的數(shù)據(jù)集的問題和初始隸屬度矩陣無法賦值的情況,通過對初始聚類中心樣本硬劃分其余樣本軟劃分來優(yōu)化初始隸屬度矩陣,解決了上述問題的同時減少了迭代次數(shù).

2 相關工作

2.1 FCM算法

給定數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N,將第j個樣本xj屬于第i類的程度定義為隸屬值μij,FCM算法[12]通過迭代使目標函數(shù)最小化,然后,將迭代后的隸屬度矩陣去模糊化得到每個樣本屬于某個類簇的確切劃分.FCM算法的目標函數(shù)為:

(1)

其中,μij∈[0,1]是樣本xj隸屬于第i類的程度.ci是第i簇的模糊聚類中心,N是樣本個數(shù),C是樣本的類簇數(shù),m∈(1,∞)是一個模糊值.

FCM算法過程如下:

第1步.初始化隸屬度矩陣

(2)

其中,隨機隸屬值μij滿足第j個樣本隸屬于所有類別的程度之和為1.

第2步.計算模糊聚類中心

(3)

第3步.更新隸屬值

(4)

進而更新隸屬度矩陣U.

第4步.重復執(zhí)行第2步和第3步,直到隸屬值在最新的兩次迭代中的改變量小于給定閾值或迭代次數(shù)達到設定值時停止迭代.將最新的隸屬度矩陣去模糊化,得到聚類結(jié)果.

2.2 FWCM算法

FWCM是一種根據(jù)樣本之間距離的大小進行樣本加權的算法[18].假設樣本xj屬于第i類,計算xj與其他樣本的距離,利用樣本之間距離的倒數(shù)作為權重對樣本進行加權,引入加權平均的概念,重新定義了模糊聚類中心,使目標函數(shù)更容易收斂到最小值.若存在某樣本距離樣本xj很近但是和樣本xj不屬于同一類,隸屬值μij會將其重要性弱化,改進的模糊聚類中心被重新定義為:

(5)

FWCM的目標函數(shù)為:

(6)

FWCM算法過程如下:

第1步.利用公式(2)初始化隸屬度矩陣.

第2步.結(jié)合當前的隸屬值,利用公式(5)計算模糊聚類中心Mij.

第3步.結(jié)合當前的模糊聚類中心Mij和隸屬值μij,更新拉格朗日乘子λj為:

(7)

第4步.結(jié)合當前的模糊聚類中心Mij和拉格朗日乘子λj,更新隸屬值μij為:

(8)

進而更新隸屬度矩陣U.

第5步.重復執(zhí)行第2步～第4步,直到隸屬值在最新的兩次迭代中的改變量小于給定閾值或迭代次數(shù)達到設定值時停止迭代.將最新的隸屬度矩陣去模糊化,得到聚類結(jié)果.

FWCM算法由于考慮到了每個樣本對于聚類中心的貢獻程度不同,用樣本之間距離的倒數(shù)對每個樣本進行加權,距離近的樣本權重大,距離遠的樣本權重小,進而提高了聚類效果.該算法存在兩方面問題:1)由于利用樣本之間距離的倒數(shù)作為權重,對于包含重復樣本的數(shù)據(jù)集會出現(xiàn)分母為零導致改進的模糊聚類中心公式無法使用的情況;2)對于樣本的特征的重要度未加區(qū)分.而在真實的數(shù)據(jù)集中,樣本特征在區(qū)分樣本時的作用是不同的,因此不同特征對于數(shù)據(jù)的聚類結(jié)果影響程度也不同.

2.3 NW-FCM算法

NW-FCM算法[19]與FCM算法相比,主要特點是包含加權平均值以提高精度,與FWCM算法相比,包含每個簇的質(zhì)心以提高穩(wěn)定性.該方法是改進FCM算法和FWCM算法.換言之,NW-FCM算法比FWCM算法更穩(wěn)定,獲得了比FCM算法更高的數(shù)據(jù)分類精度.在FWCM算法中,加權平均值是基于所考慮的點和其余樣本計算的,而在NW-FCM算法中,加權平均值是基于聚類中心和其余樣本計算的.這使得NW-FCM算法在將樣本分配到特定簇時比FWCM算法更精確.由于加權平均值是結(jié)合聚類中心計算得到的,因此該算法比FWCM算法計算量更小.

NW-FCM算法過程如下:

第1步.利用公式(2)初始化隸屬度矩陣.

第2步.結(jié)合當前的隸屬值,利用公式(3)計算模糊聚類中心.

第3步.結(jié)合當前的隸屬值μij和模糊聚類中心ci,計算改進的模糊聚類中心:

(9)

第4步.結(jié)合當前的模糊聚類中心Mij和隸屬值μij,利用公式(7)更新拉格朗日乘子λj.

第5步.結(jié)合當前的模糊聚類中心Mij和拉格朗日乘子λj,利用公式(8)更新隸屬值μij,進而更新隸屬度矩陣U.

第6步.重復執(zhí)行第2步～第5步,直到隸屬值在最新的兩次迭代中的改變量小于給定閾值或迭代次數(shù)達到設定值時停止迭代.將最新的隸屬度矩陣去模糊化,得到聚類結(jié)果.

NW-FCM算法只是將FWCM算法中模糊聚類中心的定義進行了改進,增強了聚類結(jié)果的穩(wěn)定性.但是NW-FCM算法仍然具有FWCM算法的其他缺陷.

2.4 DPC算法

基于快速搜索和發(fā)現(xiàn)密度峰值的聚類算法(DPC)是Rodriguez等人[6]提出的一種聚類算法,該算法能夠自動地發(fā)現(xiàn)任意形狀數(shù)據(jù)集的聚類中心,然后通過將剩余樣本分配到密度比它大的最近鄰樣本所在的簇實現(xiàn)對數(shù)據(jù)集的聚類.由于操作簡單,無需迭代,受到眾多學者的關注和研究.該算法基于兩個基本假設:1)聚類中心(密度峰值點)的局部密度大于圍繞它的鄰居的局部密度;2)不同聚類中心之間的距離相對較遠.為了找到同時滿足這兩個條件的聚類中心,該算法引入了局部密度的定義.

假設樣本xi的局部密度為ρi,樣本xi到局部密度比它大且距離它最近的樣本xj的距離為δi,對于大規(guī)模數(shù)據(jù)集,DPC算法采用截斷函數(shù)定義樣本的局部密度,其局部密度定義為:

(10)

其中,

距離δi定義為:

(11)

其中,dij為樣本xi和樣本xj之間的距離,dc為人為設定的截斷距離.

對于小規(guī)模數(shù)據(jù)集,DPC算法采用高斯核函數(shù)定義樣本的局部密度,其局部密度公式定義為:

(12)

DPC算法對任意兩個數(shù)據(jù)點計算它們之間的距離,并依據(jù)截斷距離dc計算出任意樣本xi的ρi和δi.將ρi×δi相對較高的樣本標記為聚類中心,將ρi相對較低但是δi相對較高的樣本標記為噪聲點.然后,將剩余的樣本分配到距離它最近且密度比它大的樣本所在的簇.該算法對于截斷距離dc的選取受人為影響較大,截斷距離dc的選取不合適將會導致ρi和δi計算出現(xiàn)較大偏差,選出錯誤的聚類中心,進而導致在剩余樣本的分配時會發(fā)生連帶錯誤.同時,該算法對于不同大小的數(shù)據(jù)集采用不同的密度度量方式,但是現(xiàn)實中對于數(shù)據(jù)集大小的界定并沒有精準論斷.

3 自適應加權模糊聚類算法(ANNDP-WFCM)

3.1 結(jié)合自適應近鄰和密度峰值的初始聚類中心選取(ANNDP)

在基于快速搜索和發(fā)現(xiàn)密度峰值的聚類算法(DPC)中,聚類過程可以分為兩部分:第1部分是選取密度峰值點,第2部分是剩余樣本的分配.謝娟英等人針對DPC算法中樣本局部密度定義的缺陷,提出一種基于K近鄰優(yōu)化的密度峰值快速搜索聚類算法,算法利用樣本的K近鄰信息定義樣本的局部密度,搜索和發(fā)現(xiàn)樣本的密度峰值,以密度峰值點樣本作為聚類中心[8].但該方法中的K值仍需要人為設定,針對不同規(guī)模、不同結(jié)構的數(shù)據(jù)集如何選擇合適的K值未給出有效的定論.本文提出一種結(jié)合自適應近鄰與密度峰值的初始聚類中心搜索算法(ANNDP),無需設定K值,根據(jù)樣本局部的稠密情況自適應選擇近鄰數(shù)量,結(jié)合密度峰值快速選出初始聚類中心,有效避免了模糊聚類算法中隨機選擇初始聚類中心導致的聚類結(jié)果不穩(wěn)定性.

圖1隨機生成的數(shù)據(jù)集將K近鄰和自適應近鄰進行對比,以樣本1和樣本2為例,周圍淺色樣本分別為其近鄰.在圖1(a)中,由于K值的固定導致樣本1必須找到距離它最近的3個樣本,即使所處位置較為稀疏.而樣本2即使所處位置較為稠密由于K值的限制只能將最近的3個樣本作為它的近鄰集合.圖1(b)可以根據(jù)樣本局部的稠密情況自適應的找到鄰域集合.

圖1Fig.1

定義1.有序距離序列.給定數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N,任意樣本xi的有序距離序列為:

seq(xi)=(x(i,1),x(i,2),…,x(i,N-1))

其中,對于任意樣本xi∈RD,計算除樣本xi外所有樣本與樣本xi之間的距離,并按距離從小到大將樣本排序并重新編號,形成有序距離序列.其中x(i,1)為距離樣本xi最近的第1個樣本,x(i,2)為距離樣本xi最近的第2個樣本,x(i,N-1)為距離樣本xi最近的第N-1個樣本,即距離樣本xi最遠的樣本.

圖2以5個樣本為例展示了以樣本xi為中心,其他樣本的命名情況,根據(jù)距離樣本xi的距離大小,其余4個樣本依次被命名為x(i,1),x(i,2),x(i,3),x(i,4),則樣本xi的有序距離序列為x(i,1),x(i,2),x(i,3),x(i,4).

圖2 有序距離序列示例Fig.2 Example of ordered distance series

定義2.自適應平均距離.給定數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N,樣本xi的有序距離序列為seq(xi)=(x(i,1),x(i,2),…,x(i,N-1)).稱:

(13)

為樣本xi的自適應平均距離.其中,Δi(xi,x(i,N-1))為樣本xi和距離樣本xi最遠的樣本x(i,N-1)之間的距離,Δi(xi,x(i,1))為樣本xi和距離樣本xi最近的樣本x(i,1)之間的距離.N-2為距離樣本xi最遠的樣本x(i,N-1)和距離樣本xi最近的樣本x(i,1)之間的間隔數(shù).如圖2所示,距離xi最遠的樣本x(i,4)和距離xi最近的樣本x(i,1)之間的間隔為3.

定義3.自適應截斷距離.給定數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N,每個樣本xi的自適應平均距離為Adapt_Dis(xi).稱:

(14)

為自適應截斷距離.其中κ為間隔因子,用于控制自適應鄰域半徑的大小.算法中以κ倍的自適應平均距離的均值作為能夠接受的最大的自適應截斷距離.在該截斷距離內(nèi)的樣本集合稱為樣本xi的自適應近鄰樣本集合ANN(xi),每個樣本xi根據(jù)自身的稠密情況自適應的選擇其近鄰個數(shù)以及近鄰樣本.間隔因子κ一般取大于1的常數(shù),通過大量實驗發(fā)現(xiàn)κ取值范圍為[1.5,3]時可以更好的反映數(shù)據(jù)集局部樣本的稠密情況,超出該范圍容易導致自適應鄰域半徑超過類簇半徑,使得類簇中心的定位出現(xiàn)偏差,影響后續(xù)模糊聚類的收斂速度和聚類精度.在本文算法中,間隔因子取1.5,具體應用中可有一定的調(diào)整.

定義4.自適應局部密度.給定數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N,稱:

(15)

為樣本xi的自適應局部密度.其中,ANN(xi)為樣本xi的自適應近鄰樣本的集合,dij為樣本xi和樣本xj之間的距離,|ANN(xi)|為樣本xi自適應近鄰樣本集合中樣本的個數(shù).

最后利用公式(15)計算ρi,利用公式(11)計算δi,將ρi×δi相對較高的樣本標記為類簇的中心.具體流程如算法1所示.

3.2 基于信息熵加權的模糊聚類算法(WFCM)

利用信息熵[20]對數(shù)據(jù)集中每一個特征進行加權的基本思想是根據(jù)樣本特征信息熵的變化程度來確定權重.若數(shù)據(jù)集的某個特征的信息熵Ej很小,說明該特征可以提供更多的信息量,在聚類分析中所能起到的作用也越大,因此該特征的權重也就越大.反之,某個特征的信息熵Ej很大,提供的信息量也越少,其權重也就越小.

首先,為了減少量綱的影響,由:

(16)

對數(shù)據(jù)進行最大最小歸一化處理.其中xij表示第i個樣本的第j個特征,xj表示樣本的第j個特征構成的向量.

由:

(17)

計算第i個樣本的第j個特征所占的比重.

由:

(18)

計算第j個特征的信息熵,若Pij=0,定義0log(0)=0.

由:

(19)

計算第j個特征的權重.

則WFCM算法的模糊聚類中心改進為:

(20)

其中,wl,l=1,2,…,L為樣本第l個特征的權重.

WFCM算法的目標函數(shù)改進為:

(21)

結(jié)合約束條件引入拉格朗日乘子λj構造拉格朗日函數(shù)為:

(22)

結(jié)合當前的模糊聚類中心Mij和權重w,更新拉格朗日乘子λj為:

(23)

結(jié)合模糊聚類中心Mij和拉格朗日乘子λj,以及權重w,更新隸屬度為:

(24)

其中,具體流程如算法2所示.

3.3 ANNDP-WFCM算法

由于ANNDP算法計算出來的初始聚類中心是數(shù)據(jù)集中的某一個具體樣本,因此在計算改進的模糊聚類中心Mij會出現(xiàn)分母為零的情況,即使在FWCM算法中,若原數(shù)據(jù)集中包含重復的樣本,仍會出現(xiàn)分母為零導致無法計算的情況,因此對Mij進一步改進,使其適用于所有數(shù)據(jù)集.

(25)

由于本算法分兩步進行,在自適應近鄰密度峰值算法(ANNDP)找到初始聚類中心后,將初始聚類中心輸入到加權模糊聚類算法(WFCM)中.因此,首次計算Mij時需提前知道初始聚類中心ci的值以及初始隸屬度矩陣U,若初始隸屬度矩陣仍隨機初始化,便失去了提前尋找初始聚類中心以提高迭代速度的意義.因此,本文在首次計算Mij之前仍需利用初始聚類中心ci計算出當前的初始隸屬度矩陣U,該過程若用傳統(tǒng)FCM算法中求取隸屬度矩陣U的方法也會出現(xiàn)分母為零的情況,本文將數(shù)據(jù)集中與初始聚類中心重合的樣本進行硬劃分,將不與初始聚類中心重合的樣本進行軟劃分.初始隸屬值更新為:

(26)

算法1.結(jié)合自適應近鄰的密度峰值算法(ANNDP)

1.fori=1,2,…,Ndo

2. 計算樣本xi的有序距離序列seq(xi)

3. 根據(jù)公式(13)計算樣本xi的自適應平均距離Adapt_Dis(xi)

4.end for

5.fori=1,2,…,Ndo

6. 根據(jù)公式(14)計算樣本xi的自適應截斷距離ΔAdapt

7. 找出以樣本xi為中心包含在自適應截斷距離內(nèi)的自適應近鄰集合ANN(xi)

8. 利用公式(15)計算樣本xi的局部密度ρi

9.end for

10.fori=1,2,…,Ndo

11. 利用公式(11)計算樣本xi的δi值

12.end for

13.選擇ρi×δi較大的樣本作為初始聚類中心

算法2.基于信息熵加權的模糊聚類算法(ANNDP-WFCM)

輸出：最終聚類結(jié)果

1.根據(jù)算法1得到初始聚類中心C

2.根據(jù)公式(26)計算初始隸屬度矩陣U

3.根據(jù)公式(25)計算改進的模糊聚類中心Mij

4.根據(jù)公式(21)計算目標函數(shù)JANNDP-WFCM的值

7. 根據(jù)公式(23)計算拉格朗日乘子λj

8. 根據(jù)公式(24)更新隸屬度矩陣U

9. 根據(jù)公式(3)更新模糊聚類中心C

10. 根據(jù)公式(20)更新改進的模糊聚類中心Mij

11. 根據(jù)公式(21)更新目標函數(shù)JANNDP-WFCM的值

12.end while

13.將最后的隸屬度矩陣去模糊化,得到樣本屬于某一類簇的確切劃分

4 實驗結(jié)果與分析

本文首先將找到的初始聚類中心在二維數(shù)據(jù)集Aggregation、Flame、4k2_far、D31、G2_2_30、Jain、R15中可視化,驗證了ANNDP算法尋找初始聚類中心的有效性.然后采用真實數(shù)據(jù)集Iris、Wine、Seeds、SPECT、Haberman、Bupa、Leuk72_3k與FCM算法、FWCM算法、NW-FCM算法、FDP-FCM算法[21]、KDPC-FCM算法[22]進行對比實驗,驗證了本文提出的ANNDP-WFCM算法的有效性.本文所提到的算法均采用Python 3.7實現(xiàn),模糊值m=2.所有實驗的環(huán)境均為Windows 10 64bit操作系統(tǒng),PyCharm Community 2020.3.2,12GB內(nèi)存,Intel(R)Core(TM)i5-4210H CPU @ 2.90GHz.

4.1 數(shù)據(jù)集

Iris數(shù)據(jù)集、Wine數(shù)據(jù)集、Seeds數(shù)據(jù)集、Haberman數(shù)據(jù)集和Bupa數(shù)據(jù)集均來自UCI數(shù)據(jù)集(https://archive.ics.uci.edu/),SPECT和Leuk72_3k也為真實數(shù)據(jù)集[23].本文實驗所用人工數(shù)據(jù)集和真實數(shù)據(jù)集如表1和表2所示.

表1 人工數(shù)據(jù)集Table 1 Synthetic datasets

表2 真實數(shù)據(jù)集Table 2 Real-world datasets

4.2 評價指標

實驗結(jié)果采用常用的聚類評價指標[24]準確率(Acc)、調(diào)整蘭德指數(shù)(ARI)、調(diào)整互信息(AMI)、標準化互信息(NMI)以及迭代次數(shù)(Iterations)來進行評價.

ARI常用于聚類算法的評估,它的前身是蘭德系數(shù)(Rand Index, RI).計算RI值需要數(shù)據(jù)集的真實標簽信息.假設數(shù)據(jù)集的真實標簽為U,聚類后的預測標簽為V.則將a表示為在U和V中為同一類的數(shù)據(jù)對象的對數(shù).b表示為在U中為同一類,在V中屬于不同類的數(shù)據(jù)對象的對數(shù).c表示為在U中為不同類,但在V中屬于同類的數(shù)據(jù)對象的對數(shù).d表示為在U和V中屬于不同類的數(shù)據(jù)對象的對數(shù).則RI的計算公式為:

(27)

其中,RI的取值范圍在[0,1]區(qū)間內(nèi),RI值越大,算法的聚類效果越好.RI的問題在于對于兩個隨機的劃分,不能保證使RI值接近于0.基于此提出ARI[25].計算公式為:

(28)

其中,ARI在[-1,1]范圍內(nèi)取值,ARI取值越接近1,表明算法的聚類質(zhì)量越好.

AMI是對互信息(Mutual Information, MI)的一種改進.MI取值范圍為[0,1],但是對于隨機結(jié)果,不能保證MI值接近0.為解決這一問題,提出AMI能更好地反映數(shù)據(jù)分布,計算公式為:

(29)

其中,H(U)為樣本對象的邊緣熵值,E|MI|為互信息的期望值.AMI取值范圍為[-1,1],AMI取值越大說明算法的聚類結(jié)果越好.

NMI[26]取值范圍為[0,1],NMI取值越大說明算法的聚類結(jié)果越好.計算公式為:

(30)

4.3 實驗結(jié)果分析

7個二維人工數(shù)據(jù)集選自不同形狀、不同規(guī)模、不同簇數(shù)和不同稀疏程度的常用人工數(shù)據(jù)集.其中Aggregation[27]包含7個不同大小的簇,部分簇有輕微連接.Flame[28]兩個簇具有不同的大小和形狀,且其中一個簇被另一個簇半包圍.4K2_far是一個經(jīng)典的4類數(shù)據(jù)集.D31[29]具有高達31個簇,包含3100個樣本.G2_2_30是一個高斯聚類數(shù)據(jù)集,具有不同的聚類重疊和維度.Jain兩個簇為月牙形狀,且兩個簇密度不一致,上月牙較為稀疏,下月牙較為稠密,是具有不規(guī)則形狀的經(jīng)典數(shù)據(jù)集.R15[29]將600個樣本劃分為15個簇,其中一個簇位于空間中心,被7個簇緊密包圍.圖3展示了本文提出的ANNDP算法尋找初始類簇中心的效果.雖然在Aggregation數(shù)據(jù)集中有個別簇的聚類中心定位到了簇邊緣,但是由于后續(xù)模糊聚類算法仍需繼續(xù)迭代優(yōu)化聚類中心,因此只要ANNDP算法能準確將初始聚類中心定位到每個簇中就會取得不錯的聚類效果.由實驗結(jié)果可以得知ANNDP算法在整個尋找初始聚類中心過程中根據(jù)數(shù)據(jù)集局部的稠密情況自適應的尋找近鄰樣本集合,且僅需讓近鄰樣本參與計算,降低了計算量,在不同數(shù)據(jù)集中能將初始聚類中心準確的定位到每個簇中.

圖3 ANNDP算法在不同數(shù)據(jù)集上搜索初始聚類中心結(jié)果Fig.3 Result of ANNDP algorithm searching the initial clustering centers on different datasets

在7個真實數(shù)據(jù)集上用上述提到的5個評價指標進行了對比實驗.表3展示了ANNDP-WFCM算法和其他5種算法在每個數(shù)據(jù)集上5個評價指標的實驗結(jié)果.在Seeds、SPECT、Haberman、Bupa、Leuk72_3k數(shù)據(jù)集上5個評價指標均取得了最好的效果,其中,在Iris、SPECT、Haberman和Bupa數(shù)據(jù)集上相比于其他5種算法準確率有較大幅度的提升.雖然在Wine數(shù)據(jù)集中AMI和NMI兩個指標略低于KDPC-FCM算法,但是Acc、ARI和迭代次數(shù)均好于其他5種算法.在迭代次數(shù)的比較上本文提出的算法略優(yōu)于同樣提前獲取初始聚類中心的FDP-FCM算法和KDPC-FCM算法,遠遠優(yōu)于其他3種算法.通過實驗結(jié)果可以發(fā)現(xiàn),本文提出的算法,整體上優(yōu)于其他5種模糊聚類算法,尤其是結(jié)合自適應近鄰和密度峰值的思想引入了初始聚類中心,基于信息熵賦權區(qū)分不同特征的重要程度.不僅使聚類準確率有一個較好的提升,同時使迭代次數(shù)顯著降低,加速了模糊聚類算法的收斂.使其能夠更快更好的迭代到最優(yōu)值.為更直觀的描述本文算法和其他3種算法的比較結(jié)果.圖4采用折線圖直觀描繪了不同的數(shù)據(jù)集、不同算法在同一評價指標上的比較結(jié)果.

5 結(jié) 論

本文針對傳統(tǒng)FCM算法的聚類結(jié)果容易受到隨機選取初始聚類中心的影響,且在聚類過程中忽視了樣本的不同特征和樣本本身的重要程度對聚類結(jié)果產(chǎn)生的影響.提出了一種結(jié)合自適應近鄰與密度峰值思想的基于信息熵加權的模糊聚類算法(ANNDP-WFCM).在7個選自不同形狀、不同規(guī)模、不同簇數(shù)和不同稀疏程度的常用二維人工數(shù)據(jù)集上可視化了本文提出的ANNDP算法尋找初始聚類中心的能力.在7個常用真實數(shù)據(jù)集上驗證本文提出的ANNDP-WFCM算法和FCM算法、FWCM算法、NW-FCM算法、FDP-FCM算法、KDPC-FCM算法相比,在聚類準確性和減少迭代次數(shù)上具有一定的優(yōu)勢.但是,FCM算法通過迭代尋優(yōu),容易陷入局部最優(yōu),本文在這個問題上尚未進行優(yōu)化,因此后續(xù)工作將圍繞提高模糊聚類算法的全局優(yōu)化能力開展研究,從而進一步提高模糊聚類算法的性能.